Approach for shot retrieval by optimal matching in the bipartite graph
Publication Type
Journal Article
Publication Date
7-2004
Abstract
Shot retrieval plays a critical role in content-based video retrieval. Motivated by the theory of optimal matching in bipartite graph, we propose a novel approach based on the Kuhn-Munkres algorithm for shot retrieval. In contrast to existing algorithms, the proposed approach emphasizes one-to-one mapping among frames between two shots for effective similarity measure. A weighted bipartite graph is constructed to model the similarity between two shots: every vertex in a bipartite graph represents one frame in a shot, and the weight of every edge represents the similarity value for a pair of frames between two shots. Then Kuhn-Munkres algorithm is employed to compute the maximum weight of a constructed bipartite graph as the similarity value between two shots by guaranteeing the one-to-one mapping among frames. To improve the speed efficiency, we also propose two improved algorithms. Experimental results indicate that the proposed approach achieves superior performance than some existing methods.
Keywords
Content-based shot retrieval, Improved algorithm, Kuhn-Munkres algorithm, Optimal matching
Discipline
Computer Sciences | Graphics and Human Computer Interfaces
Research Areas
Intelligent Systems and Optimization
Publication
Tien Tzu Hsueh Pao/Acta Electronica Sinica
Volume
32
Issue
7
First Page
1135
Last Page
1139
ISSN
0372-2112
Publisher
Zhongguo Dianzi Xuehui,Chinese Institute of Electronics
Citation
PENG, Yu-Xin; NGO, Chong-wah; and XIAO, Jian-Guo.
Approach for shot retrieval by optimal matching in the bipartite graph. (2004). Tien Tzu Hsueh Pao/Acta Electronica Sinica. 32, (7), 1135-1139.
Available at: https://ink.library.smu.edu.sg/sis_research/6423