Near-duplicate keyframe retrieval by nonrigid image matching

ABSTRACT

Near-duplicate image retrieval plays an important role in many real-world multimedia applications. Most previous approaches have some limitations. For example, conventional appearance-based methods may suffer from the illumination variations and occlusion issue, and local feature correspondence-based methods often do not consider local deformations and the spatial coherence between two point sets. In this paper, we propose a novel and effective Nonrigid Image Matching (NIM) approach to tackle the task of near-duplicate keyframe retrieval from real-world video corpora. In contrast to previous approaches, the NIM technique can recover an explicit mapping between two near-duplicate images with a few deformation parameters and find out the correct correspondences from noisy data effectively. To make our technique applicable to large-scale applications, we suggest an effective multi-level ranking scheme that filters out the irrelevant results in a coarse-to-fine manner. In our ranking scheme, to overcome the extremely small training size challenge, we employ a semi-supervised learning method for improving the performance using unlabeled data. To evaluate the effectiveness of our solution, we have conducted extensive experiments on two benchmark testbeds extracted from the TRECVID2003 and TRECVID2004 corpora. The promising results show that our proposed method is more effective than other state-of-the-art approaches for near-duplicate keyframe retrieval.

REFERENCES

• 1: http://vireo.cs.cityu.edu.hk/research/NDK/ndk.html.
• 2: http://www.cse.cuhk.edu.hk/~jkzhu/dup_detect.html.
• 3: H. Bay, T. Tuytelaars, and L. J. V. Gool. Surf: Speeded up robust features. In Proc. European Conf. Computer Vision, pages 404--417, 2006.
• 4: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 5: J Canny, A computational approach to edge detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.6, p.679-698, Nov. 1986 [doi>10.1109/TPAMI.1986.4767851]
• 6: Ondrej Chum , Jiri Matas, Matching with PROSAC " Progressive Sample Consensus, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.220-226, June 20-26, 2005 [doi>10.1109/CVPR.2005.221]
• 7: Martin A. Fischler , Robert C. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, v.24 n.6, p.381-395, June 1981 [doi>10.1145/358669.358692]
• 8: P. Fua , Y. G. Leclerc, Object-centered surface reconstruction: combining multi-image stereo and shading, International Journal of Computer Vision, v.16 n.1, p.35-55, Sept. 1995 [doi>10.1007/BF01428192]
• 9: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 10: C.-H. Hoi, W. Wang, and M. R. Lyu. A novel scheme for video similarity detection. In CIVR, pages 373--382, 2003.
• 11: S. C. Hoi and M. R. Lyu. A multi-modal and multi-level ranking framework for content-based video retrieval. To appear in IEEE Transactions on Multimedia, 2008.
• 12: M. Kass, A. Witkin, and D. Terzopoulos. Snakes: Active contour models. Int'l J. Computer Vision, 1(4):321--331, Jan. 1988.
• 13: 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]
• 14: M. Lades , J. C. Vorbruggen , J. Buhmann , J. Lange , C. von der Malsburg , R. P. Wurtz , W. Konen, Distortion Invariant Object Recognition in the Dynamic Link Architecture, IEEE Transactions on Computers, v.42 n.3, p.300-311, March 1993 [doi>10.1109/12.210173]
• 15: 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]
• 16: 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]
• 17: Chong-Wah Ngo , Wan-Lei Zhao , Yu-Gang Jiang, Fast tracking of near-duplicate keyframes in broadcast domain with transitivity propagation, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA [doi>10.1145/1180639.1180827]
• 18: T. Ojala, M. Pietikainen, and D. Harwood. A comparative study of texture measures with classification based on feature distributions. 29(1):51--59, January 1996.
• 19: Julien Pilet , Vincent Lepetit , Pascal Fua, Fast Non-Rigid Surface Detection, Registration and Realistic Augmentation, International Journal of Computer Vision, v.76 n.2, p.109-122, February 2008 [doi>10.1007/s11263-006-0017-9]
• 20: Arun Qamra , Yan Meng , Edward Y. Chang, Enhanced Perceptual Distance Functions and Indexing for Image Replica Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.379-391, March 2005 [doi>10.1109/TPAMI.2005.54]
• 21: Vikas Sindhwani , Partha Niyogi , Mikhail Belkin, Beyond the point cloud: from transductive to semi-supervised learning, Proceedings of the 22nd international conference on Machine learning, p.824-831, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102455]
• 22: Josef Sivic , Andrew Zisserman, Video Google: A Text Retrieval Approach to Object Matching in Videos, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.1470, October 13-16, 2003
• 23: TRECVID. TREC video retrieval evaluation. In http://www-nlpir.nist.gov/projects/trecvid/.
• 24: V. N. Vapnik. Statistical Learning Theory. John Wiley & Sons, 1998.
• 25: Xiao Wu , Alexander G. Hauptmann , Chong-Wah Ngo, Novelty detection for cross-lingual news stories with visual duplicates and speech transcripts, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291274]
• 26: Xiao Wu , Alexander G. Hauptmann , Chong-Wah Ngo, Practical elimination of near-duplicates from web video search, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291280]
• 27: Xiao Wu , Wan-Lei Zhao , Chong-Wah Ngo, Near-duplicate keyframe retrieval with visual keywords and semantic context, Proceedings of the 6th ACM international conference on Image and video retrieval, p.162-169, July 09-11, 2007, Amsterdam, The Netherlands [doi>10.1145/1282280.1282309]
• 28: Z. Xu, R. Jin, J. Zhu, I. King, and M. R. Lyu. Efficient convex relaxation for transductive support vector machine. In NIPS'2007, 2007.
• 29: Rong Yan , Alexander G. Hauptmann , Rong Jin, Negative pseudo-relevance feedback in content-based video retrieval, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957087]
• 30: 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]
• 31: W. Zhao, Y. Jiang, and C. Ngo. Keyframe retrieval by keypoints: Can point-to-point matching help? In CIVR06, pages 72--81, 2006.
• 32: W.-L. Zhao, C.-W. Ngo, H. K. Tan, and X. Wu. Near-duplicate keyframe identification with interest point matching and pattern learning. IEEE Trans. on Multimedia, 9(5):1037--1048, 2007.
• 33: J. Zhu. Semi-supervised learning literature survey. Technical report, Carnegie Mellon University, 2005.
• 34: J. Zhu, S. C. Hoi, and M. R. Lyu. Face annotation by transductive kernel fisher discriminant. IEEE Trans. on Multimedia, 10(1):86--96, 2008.
• 35: J. Zhu and M. R. Lyu. Progressive finite newton approach to real-time nonrigid surface detection. In Proc. Conf. Computer Vision and Pattern Recognition, pages 1--8, 2007.
• 36: J. Zhu, M. R. Lyu, and T. S. Huang. A fast 2d shape recovery approach by fusing features and appearance. To appear in IEEE Trans. Pattern Anal. Mach. Intell., 2008.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.9 Applications

General Terms:
Algorithms, Experimentation, Performance

Keywords:
image copy detection, near-duplicate keyframe, nonrigid image matching, semi-supervised learning