Video search reranking via information bottleneck principle

ABSTRACT

We propose a novel and generic video/image reranking algorithm, IB reranking, which reorders results from text-only searches by discovering the salient visual patterns of relevant and irrelevant shots from the approximate relevance provided by text results. The IB reranking method, based on a rigorous Information Bottleneck (IB) principle, finds the optimal clustering of images that preserves the maximal mutual information between the search relevance and the high-dimensional low-level visual features of the images in the text search results. Evaluating the approach on the TRECVID 2003-2005 data sets shows significant improvement upon the text search baseline, with relative increases in average performance of up to 23%. The method requires no image search examples from the user, but is competitive with other state-of-the-art example-based approaches. The method is also highly generic and performs comparably with sophisticated models which are highly tuned for specific classes of queries, such as named-persons. Our experimental analysis has also confirmed the proposed reranking method works well when there exist sufficient recurrent visual patterns in the search results, as often the case in multi-source news videos.

REFERENCES

• 1: A. Amir et al. IBM Research TRECVID-2005 video retrieval system. In TRECVID Workshop, Waishington DC, 2005.
• 2: Alias-i. Lingpipe named entity tagger. In http://www.alias-i.com/lingpipe/.
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: K. M. Donald and A. F. Smeaton. A comparison of score, rank and probability-based fusion methods for video shot retrieval. In CIVR, Singapore, 2005.
• 5: R. Fergus, P. Perona, and A. Zisserman. A visual category filter for google images. In CVPR, May 2004.
• 6: Shiri Gordon , Hayit Greenspan , Jacob Goldberger, Applying the Information Bottleneck Principle to Unsupervised Clustering of Discrete and Continuous Image Representations, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.370, October 13-16, 2003
• 7: Alexander G. Hauptmann , Michael G. Christel, Successful approaches in the TREC video retrieval evaluations, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027681]
• 8: W. H. Hsu and S.-F. Chang. Visual cue cluster construction via information bottleneck principle and kernel density estimation. In CIVR, Singapore, 2005.
• 9: W. H. Hsu and S.-F. Chang. Topic tracking across broadcast news videos with visual duplicates and semantic concepts. In ICIP, Atlanta, GA, USA, 2006.
• 10: J. G. Carbonell et al. Translingual information retrieval: A comparative evaluation. In International Joint Conference on Artificial Intelligence, 1997.
• 11: Lyndon S. Kennedy , Apostol (Paul) Natsev , Shih-Fu Chang, Automatic discovery of query-class-dependent models for multimodal search, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101339]
• 12: H. Liu. Montylingua: An end-to-end natural language processor with common sense. In http://web.media.mit.edu/$\sim$hugo/montylingua.
• 13: Xiaoyong Liu , W. Bruce Croft, Cluster-based retrieval using language models, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009026]
• 14: Noam Slonim , Nir Friedman , Naftali Tishby, Unsupervised document classification using sequential information maximization, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564401]
• 15: Apostol (Paul) Natsev , Milind R. Naphade , Jelena TešiĆ, Learning the semantics of multimedia queries and concepts from a small number of examples, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101288]
• 16: S. E. Robertson et al. Okapi at TREC4. In Text REtrieval Conference, pages 21--30, 1992.
• 17: S.-F. Chang et al. Columbia University TRECVID 2005 video search and high-level feature extraction. In TRECVID Workshop, Waishington DC, 2005.
• 18: D. W. Scott. Multivariate Density Estimation: Theory, Practice, and Visualization. Wiley-Interscience, 1992.
• 19: N. Slonim and N. Tishby. Agglomerative information bottleneck. In NIPS, 1999.
• 20: T.-C. Chang et al. TRECVID 2004 search and feature extraction task by NUS PRIS. In TRECVID Workshop, Waishington DC, 2004.
• 21: TRECVID. TREC Video Retrieval Evaluation. In http://www-nlpir.nist.gov/projects/trecvid/.
• 22: R. Yan, A. Hauptmann, and R. Jin. Multimedia search with pseudo-relevance feedback. In CIVR, Urbana-Champaign, IL, 2003.

INDEX TERMS

Primary 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:
information bottleneck principle, multimodal fusion, video search