Extreme video retrieval: joint maximization of human and computer performance

ABSTRACT

We present an efficient system for video search that maximizes the use of human bandwidth, while at the same time exploiting the machine's ability to learn in real-time from user selected relevant video clips. The system exploits the human capability for rapidly scanning imagery augmenting it with an active learning loop, which attempts to always present the most relevant material based on the current information. Two versions of the human interface were evaluated, one with variable page sizes and manual paging, the other with a fixed page size and automatic paging. Both require absolute attention and focus of the user for optimal performance. In either case, as users search and find relevant results, the system can invisibly re-rank its previous best guesses using a number of knowledge sources, such as image similarity, text similarity, and temporal proximity. Experimental evidence shows a significant improvement using the combined extremes of human and machine power over either approach alone.

REFERENCES

• 1: Chang, E.Y., Tong, S., and Goh, K.-S. Support Vector Machine Concept-Dependent Active Learning for Image Retrieval. IEEE Transactions on Multimedia (anticipated 2005), http://mmdb2.ece.ucsb.edu/~echang/mm000540.pdf.
• 2: Shih-Fu Chang , Gwendal Auffret , Jonathan Foote , Chung-Shen Li , Behzad Shahraray , Tanveer Syeda-Mahmood , HongJiang Zhang, Multimedia access and retrieval (panel session): the state of the art and future directions, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.443-445, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319684]
• 3: Chen, M-Y., and Hauptmann, A., Searching for a Specific Person in Broadcast News Video, International Conference on Acoustics, Speech, and Signal Processing (ICASSP'04), Montreal, Canada, May 17-21, 2004
• 4: Mark Derthick, Interfaces for palmtop image search, Proceedings of the 2nd ACM/IEEE-CS joint conference on Digital libraries, July 14-18, 2002, Portland, Oregon, USA [doi>10.1145/544220.544304]
• 5: David A. Forsyth , Jean Ponce, Computer Vision: A Modern Approach, Prentice Hall Professional Technical Reference, 2002
• 6: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504 ]
• 7: Gosselin, P.H., and Cord, M. RETIN AL: An active learning strategy for image category retrieval. In Proc. IEEE Conf. Image Processing (Singapore, October 2004), 2219--2222.
• 8: Hastie, T., Tibshirani, R., and Friedman, J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, 2001.
• 9: 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]
• 10: Hauptmann, A. G., Christel, M., Conescu, R., Gao, J., Jin Q., Lin, W.-H., Pan, J.-Y., Stevens, S. M., Yan, R., Yang, J., and Zhang, Y. CMU Informedia's TRECVID 2005 Skirmishes, in TRECVid 2005 - Text REtrieval Conference TRECVID Workshop, Gaithersburg, MD, 14-15 Nov. 2005.
• 11: Lee, H. and Smeaton, A.F. Designing the User Interface for the Fischlar Digital Video Library, J. Digital Info. 2(4), http://jodi.ecs.soton.ac.uk/Articles/v02/i04/Lee/, May 2002.
• 12: Andrew McCallum , Kamal Nigam, Employing EM and Pool-Based Active Learning for Text Classification, Proceedings of the Fifteenth International Conference on Machine Learning, p.350-358, July 24-27, 1998
• 13: Naphade, M., and Smith, J.R. Active Learning for Simultaneous Annotation of Multiple Binary Concepts. In Proc. IEEE Intl. Conf. on Multimedia and Expo (ICME) (Taipei, Taiwan, June, 2004), 77-80.
• 14: Milind R. Naphade , John R. Smith, On the detection of semantic concepts at TRECVID, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027680]
• 15: Hieu T. Nguyen , Arnold Smeulders, Active learning using pre-clustering, Proceedings of the twenty-first international conference on Machine learning, p.79, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015349]
• 16: Over P, Kraaij W and Smeaton A.F. TRECVID 2005 - An Introduction. TRECVid 2005 - Text REtrieval Conference TRECVID Workshop, Gaithersburg, MD, 14-15 Nov. 2005.
• 17: H. Schneiderman , T. Kanade, Probabilistic Modeling of Local Appearance and Spatial Relationships for Object Recognition, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.45, June 23-25, 1998
• 18: Robert Spence, Rapid, serial and visual: a presentation technique with potential, Information Visualization, v.1 n.1, p.13-19, March 2002 [doi>10.1057/palgrave/ivs/9500008]
• 19: Simon Tong , Edward Chang, Support vector machine active learning for image retrieval, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500159]
• 20: Wang, L., Chan, K.L., and Zhang, Z. Bootstrapping SVM Active Learning by Incorporating Unlabelled Images for Image Retrieval. In Conf. Computer Vision and Pattern Recognition (CVPR '03) (Madison, WI, June, 1998). IEEE Computer Society, 2003, 629--634.
• 21: Rong Yan , Jun Yang , Alexander G. Hauptmann, Learning query-class dependent weights in automatic video retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027661]
• 22: Snoek, C. G. M., van Gemert, J. C.,Geusebroek, J. M., Huurnink, B., Koelma, D. C., Nguyen, G. P., De Rooij, O., Seinstra F. J., Smeulders, A. W. M., Veenman, C. J., Worring, M., The MediaMill TRECVID 2005 Semantic Video Search Engine. In Proceedings of the 3rd TRECVID Workshop , Gaithersburg, USA, November 2005
• 23: Yan, R., and Hauptmann, A.G., Efficient Margin-Based Rank Learning Algorithms for Information Retrieval. Conference on Image and Video Retrieval (CIVR 2006), pp. 113--122 Tempe, AZ, July 2006.
• 24: Ming-yu Chen , Michael Christel , Alexander Hauptmann , Howard Wactlar, Putting active learning into multimedia applications: dynamic definition and refinement of concept classifiers, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101342]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Video (e.g., tape, disk, DVI)

General Terms:
Algorithms, Experimentation, Human Factors

Keywords:
active learning, human performance optimization, relevance feedback, video retrieval