Detecting image near-duplicate by stochastic attributed relational graph matching with learning

ABSTRACT

Detecting Image Near-Duplicate (IND) is an important problem in a variety of applications, such as copyright infringement detection and multimedia linking. Traditional image similarity models are often difficult to identify IND due to their inability to capture scene composition and semantics. We present a part-based image similarity measure derived from stochastic matching of Attributed Relational Graphs that represent the compositional parts and part relations of image scenes. Such a similarity model is fundamentally different from traditional approaches using low-level features or image alignment. The advantage of this model is its ability to accommodate spatial attributed relations and support supervised and unsupervised learning from training data. The experiments compare the presented model with several prior similarity models, such as color histogram, local edge descriptor, etc. The presented model outperforms the prior approaches with large margin.

REFERENCES

• 1: http://www-nlpir.nist.gov/projects/trecvid/. Web site 2004.
• 2: J. Allan, J. Carbonell, G. Doddington, J. Yamron, and Y. Yang. Topic detection and tracking pilot study: Final report. In Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop, 1998. 1998.
• 3: E. Chang, J. Wang, C. Li, and G. Wiederhold. Rime: A replicated image detector for the world wide web. In Proceedings of SPIE Mulimedia Storage and Archiving Systems III IEEE, Nov. 1998.
• 4: Shi-Kuo Chang, Principles of pictorial information systems design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 5: R. Fergus, P. Perona, and A. Zisserman. Object class recognition by unsupervised scale-invariant learning. In Proceedings of the IEEE Computer Vision and Pattern Recognition Conference pages 66--73. IEEE, 2003.
• 6: A. Hampapur. Comparison of distance measures for video copy detection. In Proceedings of ICME 2001 pages 188--192. IEEE, August 2001.
• 7: H. G. Barrow and R. Popplestone. Relational descriptions in picture processing. Machine Intelligence 6:377--396, 1971.
• 8: Alejandro Jaimes , Shih-Fu Chang, Conceptual structures and computational methods for indexing and organization of visual information, 2003
• 9: N. Jojic, N. Petrovic, and T. Huang. Scene generative models for adaptive video fast forward. In International Conference on Image Processing (ICIP), Barcelona, Spain, 2003 IEEE, 2003.
• 10: C.-Y. Lin, B.L. Tseng, M. Naphade, A. Natsev, and J. R. Smith. Videoal: A novel end-to-end mpeg-7 automatic labeling system. In IEEE Intl. Conf. on Image Processing (ICIP) IEEE, September 2003.
• 11: Richard C. Wilson , Edwin R. Hancock, Structural Matching by Discrete Relaxation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.6, p.634-648, June 1997 [doi>10.1109/34.601251 ]
• 12: J. R. Smith, M. Naphade, and A. Natsev. Multimedia semantic indexing using model vectors. In IEEE Intl. Conf. on Multimedia and Expo (ICME) IEEE, 2003.
• 13: Jianbo Shi , Jitendra Malik, Self Inducing Relational Distance and Its Application to Image Segmentation, Proceedings of the 5th European Conference on Computer Vision-Volume I, p.528-543, June 02-06, 1998
• 14: John R. Smith , Chung-Sheng Li, Image classification and querying using composite region templates, Computer Vision and Image Understanding, v.75 n.1-2, p.165-174, July/Aug. 1999 [doi>10.1006/cviu.1999.0771 ]
• 15: S. Smith. A new class of corner finder. In Proc. 3rd British Machine Vision Conference pages 139--148, 1992.
• 16: Jonathan S. Yedidia , William T. Freeman , Yair Weiss, Understanding belief propagation and its generalizations, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 17: D.-Q. Zhang and S.-F. Chang. Stochastic attributed relational graph matching for image near-duplicate detection. DVMM Techinical Report, Dept. of E. E., Columbia University July 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS; Statistical databases; Image databases

General Terms:
Algorithms, Measurement, Theory

Keywords:
attributed relational graph matching, image near-duplicate detection, part-based image similarity measure