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

This document is currently not available here.

Share

COinS