The use of temporal, semantic and visual partitioning model for efficient near-duplicate keyframe detection in large scale news corpus

ABSTRACT

Near-duplicate keyframes (NDKs) are important visual cues to link news stories from different TV channel, time, language, etc. However, the quadratic complexity required for NDK detection renders it intractable in large-scale news video corpus. To address this issue, we propose a temporal, semantic and visual partitioning model to divide the corpus into small overlapping partitions by exploiting domain knowledge and corpus characteristics. This enables us to efficiently detect NDKs in each partition separately and then link them together across partitions. We divide the corpus temporally into sequential partitions and semantically into news story genre groups; and within each partition, we visually group potential NDKs by using asymmetric hierarchical k-means clustering on our proposed semi-global image features. In each visual group, we detect NDK pairs by exploiting our proposed SIFT-based fast keypoint matching scheme based on local color information of keypoints. Finally, the detected NDK groups in each partition are linked up via transitivity propagation of NDKs shared by different partitions. The testing on TRECVID 06 corpus with 62k keyframes shows that our proposed approach could result in multifold increase in speed as compared to the best reported approach and complete the NDK detection in a manageable time with satisfactory accuracy.

References

1. 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 TREC Video Retrieval Evaluation Proceedings, March 2006.
2. T.-S. Chua, S.-Y. Neo, Y.-T Zheng, H.-K. Goh, Y. Xiao, S. Tang, and M. Zhao. Trecvid-2006 by nus-i2r. In TREC Video Retrieval Evaluation Proceedings, March 2006.
3. P. Duygulu, J.-Y. Pan, and D. A. Forsyth. Towards auto-documentary: Tracking the evolution of news stories. In Proceedings of the ACM Multimedia Conference, pages 820--827, 2004.
4. C. Herley. Argos: automatically extracting repeating objects from multimedia streams. IEEE Transactions on Multimedia, 8(1):115--129, 2006.
5. W. Hsu and S.-F. Chang. Topic tracking across broadcast news videos with visual duplicates and semantic concepts. In Proceedings of International Conference on Image Processing, Atlanta, USA, 2006.
6. J. Huang, S. Kumar, M. Mitra, W. Zhu, and R. Zabih. Image indexing using color correlograms. In Proceedings of Conference on Computer Vision and Pattern Recognition, pages 762--768, 1997.
7. I. T. Joliffe. Principal Component Analysis. Springer-Verlag, 1986.
8. Y. Ke and R. Sukthankar. CA-SIFT: a more distinctive representation for local image descriptors. In Proceedings of Conference on Computer Vision and Pattern Recognition 2004, volume 2, pages II-506--II-513 Vol.2, 2004.
9. Y. Ke, R. Sukthankar, and L. Huston. Efficient near-duplicate detection and sub-image retrieval. In Proceedings of ACM International Conference on Multimedia, pages 869--876, New York City, USA, October 2004.
10. D. Lowe. Distinctive image features from scale-invariant keypoints. In International Journal of Computer Vision, volume 20, pages 91--110, 2003.
11. K. Mikolajczyk and C. Schmid. A performance evaluation of local descriptors. IEEE Trans. Pattern Anal. Mach. Intell., 27(10):1615-1630, 2005.
12. K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, J. Matas, F. Schaffalitzky, T. Kadir, and L. Van Gool. A comparison of affine region detectors. Int. J. Comput. Vision, 65(1--2):43-72, 2005.
13. F. Mindru, T. Tuytelaars, L. Van Gool, and T. Moons. Moment invariants for recognition under changing viewpoint and illumination. Computer Vision and Image Understanding, 94(1--3):3--27, 2004.
14. S.-Y. Neo, J. Zhao, M.-Y. Kan, and T.-S. Chua. Video retrieval using high level features: Exploiting query matching and confidence-based weighting. In Proceedings of ACM International Conference on Image and Video Retrieval, pages 143--152, 2006.
15. C.-W. Ngo, W.-L. Zhao, and Y.-G. Jiang. Fast tracking of near-duplicate keyframes in broadcast domain with transitivity propagation. In Proceedings of ACM International Conference on Multimedia, pages 845--854, Santa Barbara, USA, 2006.
16. J. Sivic and A. Zisserman. Video google: A text retrieval approach to object matching in videos. In Proceedings of the Ninth IEEE International Conference on Computer Vision, page 1470, 2003.
17. TRECV. TREC Video retrieval evaluation. http://www.nlpir.nist.gov/projects/trecvid.
18. D.-Q. Zhang and S.-F. Chang. Detecting image near-duplicate by stochastic attributed relational graph matching with learning. In Proceedings of ACM International Conference on Multimedia, pages 877--884, New York City, USA, October 2004.
19. Y.-T. Zheng, S.-Y. Neo, T.-S. Chua, and Q. Tian. Fast near-duplicate keyframes identification in large-scale corpus for video search. In Proceedings of International Workshop on Advanced Image Processing (IWAIT), Bangkok, Thailand, 2007.

Index Terms

• Information systems

  • Information retrieval

    • Document representation