Fast tracking of near-duplicate keyframes in broadcast domain with transitivity propagation

ABSTRACT

The identification of near-duplicate keyframe (NDK) pairs is a useful task for a variety of applications such as news story threading and content-based video search. In this paper, we propose a novel approach for the discovery and tracking of NDK pairs and threads in the broadcast domain. The detection of NDKs in a large data set is a challenging task due to the fact that when the data set increases linearly, the computational cost increases in a quadratic speed, and so does the number of false alarms. This paper explores the symmetric and transitive nature of near-duplicate for the effective detection and fast tracking of NDK pairs based upon the matching of local keypoints in frames. In the detection phase, we propose a robust measure, namely pattern entropy (PE), to measure the coherency of symmetric keypoint matching across the space of two keyframes. This measure is shown to be effective in discovering the NDK identity of a frame. In the tracking phase, the NDK pairs and threads are rapidly propagated and linked with sitivity without the need of detection. This step ends up a significant boost in speed efficiency. We evaluate proposed approach against a month of the 2004 broadcast videos. The experimental results indicate our approach outperforms other techniques in terms of recall and precision with a large margin. In addition, by considering the transitivity and the underlying distribution of NDK pairs along time span, a speed up of 3 to 5 times is achieved when keeping the performance close enough to the optimal one obtained by exhaustive evaluation.

REFERENCES

• 1: C. Chang, J. Wang, C. Li, and G. Wiederhold. RIME: A replicated image detector for the world-wide web. In Multimedia Storage and Archiving Systems 1998.
• 2: S.F. Chang, W. Hsu, L. Kennedy, L. Xie, A. Yanagawa, E. Zavesky, and D.-Q. Zhang. Columbia university trecvid-2005 video search and high-level feature extraction. In TRECVID 2005.
• 3: Pinar Duygulu , Jia-Yu Pan , David A. Forsyth, Towards auto-documentary: tracking the evolution of news stories, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027719]
• 4: Y. Ke and R. Sukthankar. PCA-SIFT: A more distinctive representation for local image descriptors. In CVPR volume 2, pages 506--513, 2004.
• 5: Yan Ke , Rahul Sukthankar , Larry Huston, An efficient parts-based near-duplicate and sub-image retrieval system, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027729]
• 6: David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004 [doi>10.1023/B:VISI.0000029664.99615.94]
• 7: Y. Meng, E. Chang, and B. Li. Enhancing dpf for near-replica image recognition. In CVPR 2003.
• 8: K. Mikolajczyk , C. Schmid, An Affine Invariant Interest Point Detector, Proceedings of the 7th European Conference on Computer Vision-Part I, p.128-142, May 28-31, 2002
• 9: Krystian Mikolajczyk , Cordelia Schmid, A Performance Evaluation of Local Descriptors, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.10, p.1615-1630, October 2005 [doi>10.1109/TPAMI.2005.188]
• 10: K. Mikolajczyk , T. Tuytelaars , C. Schmid , A. Zisserman , J. Matas , F. Schaffalitzky , T. Kadir , L. Van Gool, A Comparison of Affine Region Detectors, International Journal of Computer Vision, v.65 n.1-2, p.43-72, November 2005 [doi>10.1007/s11263-005-3848-x]
• 11: M. Schneider and S.F. Chang. A robust content based digital signature for image authentication. In Int. Conf. on Image Processing 1996.
• 12: J.S. Seo, J. Haitsma, T. Kalker, and C.D. Yoo. A robust image fingerprinting system using Randon transform. Signal Processing: Image Communication 19:325--339, 2004.
• 13: M. Steinbach, G. Karypis, and V. Kumar. A comparison of document clustering techniques. In KDD Workshop on Text Mining 2000.
• 14: X. Wu, C.-W. Ngo, and Q. Li. Threading and autodocumenting news videos. Signal Processing Magazine 23(2):59--68, Mar 2006.
• 15: Dong-Qing Zhang , Shih-Fu Chang, Detecting image near-duplicate by stochastic attributed relational graph matching with learning, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027730]
• 16: W. Zhao, Y.G. Jiang, and C.W. Ngo. Keyframe retrieval by keypoints: Can point-to-point matching help? In Conf. on Image and Video Retrieval 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Video analysis

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining; Image databases

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Perceptual reasoning

General Terms:
Algorithms, Design, Experimentation

Keywords:
keyframe tracking, keypoint matching, near-duplicate detection, pattern entropy, transitivity propagation