FISH: a practical system for fast interactive image search in huge databases

ABSTRACT

The problem of search and retrieval of images using relevance feedback has attracted tremendous attention in recent years from the research community. A real-world-deployable interactive image retrieval system must (1) be accurate, (2) require minimal user-interaction, (3) be efficient, (4) be scalable to large collections (millions) of images, and (5) support multi-user sessions. For good accuracy, we need effective methods for learning the relevance of image features based on user feedback, both within a user-session and across sessions. Efficiency and scalability require a good index structure for retrieving results. The index structure must allow for the relevance of image features to continually change with fresh queries and user-feedback. The state-of-the-art methods available today each address only a subset of these issues. In this paper, we build a complete system FISH - Fast Image Search in Huge databases. In FISH, we integrate selected techniques available in the literature, while adding a few of our own. We perform extensive experiments on real datasets to demonstrate the accuracy, efficiency and scalability of FISH. Our results show that the system can easily scale to millions of images while maintaining interactive response time.

REFERENCES

• 1: Airliners.net aviation photo search engine at http://www.airliners.net/search/.
• 2: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 3: Chad Carson , Megan Thomas , Serge Belongie , Joseph M. Hellerstein , Jitendra Malik, Blobworld: A System for Region-Based Image Indexing and Retrieval, Proceedings of the Third International Conference on Visual Information and Information Systems, p.509-516, June 02-04, 1999
• 4: P. Cord, M.; Gosselin. Image retrieval using long-term semantic learning. Intl Conf on Image Processing, pages 2909--2912, 8-11 Oct. 2006.
• 5: C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
• 6: J. Fournier and M. Cord. Long-term similarity learning in content-based image retrieval. In Intl Conf on Image Processing, Rochester, New-York, USA, September 2002.
• 7: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 8: D. Heisterkamp. Building a latent semantic index of an image database from patterns of relevance feedback. Pattern Recognition, 2002. Proc. 16th Intl Conf on, 4:134--137 vol.4, 2002.
• 9: Chu-Hong Hoi , Michael R. Lyu, A novel log-based relevance feedback technique in content-based image retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027533]
• 10: T. Huang and X. S. Zhou. Image retrieval with relevance feedback: from heuristic weight adjustment to optimal learning methods. Proc. of the Intl Conf on Image Processing, 3:2--5 vol.3, 2001.
• 11: N. Jammalamadaka, V. Pudi, and C. V. Jawahar. Efficient search with changing similarity measures on large multimedia datasets. In Intl Multimedia Modeling Conf, pages 206--215, 2007.
• 12: E. Kasutani and A. Yamada. The mpeg-7 color layout descriptor: a compact image feature description for high-speed image/video segment retrieval. In Intl Conf on Image Processing, pages I: 674--677, 2001.
• 13: Ruth Kurniawati , Jesse S. Jin , John Shepherd, Efficient Nearest-Neighbour Searches Using Weighted Euclidean Metric, Proceedings of the 16th British National Conferenc on Databases: Advances in Databases, p.64-76, July 06-08, 1998
• 14: Jorma Laaksonen , Markus Koskela , Sami Laakso , Erkki Oja, PicSOM—content-based image retrieval with self-organizing maps, Pattern Recognition Letters, v.21 n.13-14, p.1199-1207, Dec. 2000 [doi>10.1016/S0167-8655(00)00082-9]
• 15: E. Louupias and S. Bres. Key points-based indexing for pre-attentive similarities: The kiwi system. PAA, 4(2/3 2001):200--214, 2001.
• 16: Wei-Ying Ma , B. S. Manjunath, NeTra: a toolbox for navigating large image databases, Multimedia Systems, v.7 n.3, p.184-198, May 1999 [doi>10.1007/s005300050121]
• 17: IEEE MultiMedia, MPEG-7: Overview of MPEG-7 Description Tools, Part 2, IEEE MultiMedia, v.9 n.3, p.83-93, July 2002 [doi>10.1109/MMUL.2002.1022862]
• 18: D. Messing, P. van Beek, and J. Errico. The mpeg-7 colour structure descriptor: Image description using colour and local spatial information. In Intl Conf on Image Processing, pages I: 670--673, 2001.
• 19: H. Muller, W. Muller, D. Squire, S. Marchand-Maillet, and T. Pun. Long-term learning from user behavior in content-based image retrieval. Tech. Rep. 00.04.
• 20: W. Niblack, R. Barber, W. Equitz, M. Flickner, E. H. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, and G. Taubin. The qbic project: Querying images by content, using color, texture, and shape. In Storage and Retrieval for Image and Video Databases, pages 173--187, 1993.
• 21: Michael Ortega , Yong Rui , Kaushik Chakrabarti , Sharad Mehrotra , Thomas S. Huang, Supporting similarity queries in MARS, Proceedings of the fifth ACM international conference on Multimedia, p.403-413, November 09-13, 1997, Seattle, Washington, United States [doi>10.1145/266180.266394]
• 22: R. W. Picard, T. P. Minka, and M. Szummer. Modeling user subjectivity in image libraries. In IEEE Int. Conf. On Image Processing, volume 2, pages 777--780, Lausanne, Switzerland, 1996.
• 23: Y. Rui, T. Huang, M. Ortega, and S. Mehrotra. Relevance feedback: a power tool for interactive content-based image retrieval. Circuits and Systems for Video Technology, IEEE Transactions on, 8(5):644--655, Sep 1998.
• 24: Eugenio Di Sciascio , G. Mingolla , Marina Mongiello, Content-Based Image Retrieval over the Web Using Query by Sketch and Relevance Feedback, Proceedings of the Third International Conference on Visual Information and Information Systems, p.123-130, June 02-04, 1999
• 25: David A. White , Ramesh Jain, Similarity Indexing with the SS-tree, Proceedings of the Twelfth International Conference on Data Engineering, p.516-523, February 26-March 01, 1996
• 26: Tomohiro YOSHIZAWA , Haim SCHWEITZER, Long-term learning of semantic grouping from relevance-feedback, Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval, October 15-16, 2004, New York, NY, USA [doi>10.1145/1026711.1026739]
• 27: Junqi Zhang , Xiangdong Zhou , Wei Wang , Baile Shi , Jian Pei, Using high dimensional indexes to support relevance feedback based interactive images retrieval, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 28: X. S. Zhou and T. S. Huang. Relevance feedback in image retrieval: A comprehensive review. Multimedia Systems, 8(6):536--544, April 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Relevance feedback; Query formulation; Information filtering; Selection process; Retrieval models

General Terms:
Algorithms, Design, Experimentation, Human Factors, Performance, Verification

Keywords:
content extraction, dynamic indexing, image retrieval, long term learning, relevance feedback, scalability, short term learning