Interactive objects retrieval with efficient boosting

ABSTRACT

This paper presents an efficient local features boosting strategy for interactive objects retrieval tasks such as on-line supervised learning or relevance feedback. The prediction time complexity of most existing methods is indeed usually linear in dataset size since the retrieval works by applying a trained classifier on the images of the dataset one by one. In our method, the trained classifier can be computed directly on the whole dataset in sublinear time thanks to distance-based weak classifiers. The idea is to speed-up drastically the prediction of each weak classifier on the whole dataset by performing approximate range queries with an efficient similarity search structure. Experiments on Caltech 256 dataset show that the technique is up to 250 times faster than the naive exhaustive method. Thanks to this efficiency improvement, we developed a relevance feedback mechanism on image regions freely selected by the user and we show how it improves the effectiveness of the retrieval.

REFERENCES

• 1: M. Crucianu, D. Estevez, V. Oria, and J.-P. Tarel. Speeding up active relevance feedback with approximate knn retrieval for hyperplane queries. Int. J. Imaging Syst. Technol., 18(2-3):150--159, 2008.
• 2: M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proc. of Symposium on Computational geometry, pages 253--262, 2004.
• 3: H. Z. B. Z. F Jing, M Li. Relevance feedback in region-based image retrieval. IEEE Transactions on Circuits and Systems for Video Technology, 14(5):672--681, 2004.
• 4: Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. In 2nd European Conference on Computational Learning Theory (EuroCOLT'95), pages 23--37, 1995.
• 5: K. Grauman and T. Darrell. The pyramid match kernel: Efficient learning with sets of features. J. Mach. Learn. Res., 8:725--760, 2007.
• 6: G. Griffin, A. Holub, and P. Perona. Caltech-256 object category dataset. Technical Report 7694, California Institute of Technology, 2007.
• 7: A. Joly and O. Buisson. A posteriori multi-probe locality sensitive hashing. In Proceedings of ACM international conference on Multimedia, 2008.
• 8: S. Lazebnik, C. Schmid, and J. Ponce. Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories. In CVPR '06: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 2169--2178, Washington, DC, USA, 2006. IEEE Computer Society.
• 9: D. G. Lowe. Object recognition from local scale-invariant features. In Proc. of Int. Conf. on Computer Vision, pages 1150--1157, 1999.
• 10: Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li. Multi-probe lsh: efficient indexing for high-dimensional similarity search. In Proc. of Conf. on Very Large Data Bases, pages 253--262, 2007.
• 11: V. Mezaris, I. Kompatsiaris, and M. G. Strintzis. Region-based image retrieval using an object ontology and relevance feedback. EURASIP J. Appl. Signal Process., 2004:886--901, 2004.
• 12: A. Opelt, M. Fussenegger, and P. Auer. Generic object recognition with boosting. IEEE Trans. Pattern Anal. Mach. Intell., 28(3):416--431, 2006.
• 13: N. Panda and E. Y. Chang. Efficient top-k hyperplane query processing for multimedia information retrieval. In MULTIMEDIA '06: Proceedings of the 14th annual ACM international conference on Multimedia, pages 317--326, New York, NY, USA, 2006. ACM.

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
LSH, boosting, efficiency, local features, object retrieval, relevance feedback, scalability