Frame-level matching of near duplicate videos based on ternary frame descriptor and iterative refinement

A frame-level video matching algorithm, which achieves dense frame matching between near-duplicate videos, is proposed in this work. First, we propose a ternary frame descriptor for the near-duplicate video matching. The ternary descriptor partitions a frame into patches and uses ternary digits to represent relations between pairs of patches. Second, we formulate the frame-level matching problem as the minimization of a cost function, which consists of matching costs and adaptive unmatching costs. We develop an iterative refinement scheme that converges to a local minimum of the cost function. The iterative scheme performs competitively with the global optimization techniques while demands a significantly lower computational complexity. Experimental results show that the proposed algorithm achieves effective frame description and efficient frame matching of near duplicate videos.