An Approach for Shot Retrieval by Optimal Matchingin the Bipartite Graph
Peng Yu · 2004
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.