Comparing discriminating transformations and SVM for learning during multimedia retrieval

ABSTRACT

On-line learning or "relevance feedback" techniques for multimedia information retrieval have been explored from many different points of view: from early heuristic-based feature weighting schemes to recently proposed optimal learning algorithms, probabilistic/Bayesian learning algorithms, boosting techniques, discriminant-EM algorithm, support vector machine, and other kernel-based learning machines. Based on a careful examination of the problem and a detailed analysis of the existing solutions, we propose several discriminating transforms as the learning machine during the user interaction. We argue that relevance feedback problem is best represented as a biased classification problem, or a (1+x)-class classification problem. Biased Discriminant Transform (BDT) is shown to outperform all the others. A kernel form is proposed to capture non-linearity in the class distributions.

REFERENCES

• 1: G. Baudat , F. Anouar, Generalized Discriminant Analysis Using a Kernel Approach, Neural Computation, v.12 n.10, p.2385-2404, October 2000 [doi>10.1162/089976600300014980]
• 2: G. Cauwenberghs and T. Poggio, "incremental and decremental support vector machine learning", in T. K Lea, T.G. Dietterich, and V. Trap, editors, Advances in Neural Information Processing Systems 13, MIT Press, 2001
• 3: J-Y. Chew C. A. Bouman, and J. C. Dalton, "Hierarchical Browsing and Search of Large Image Databases," IEEE Trans. on Image Processing, vol. 9, no. 3, pp. 442-455, March 2000.
• 4: Y. Chen, X. S. Zhou, T. S. Huang, "One-class SVM for Learning in Image Retrieval", submitted to IEEE Int'l Conf. on Image Proc. (ICIP'2001). Thessaloniki, Greece, October 7.10,2001
• 5: D. Comaniciu, P. Mea, "Distribution free decomposition of multivariate data," Pattern Analysis and Applications, 2, 22. 30,1999
• 6: I. J. Cox , M. L. Miller , T. P. Minka , P. N. Yianilos, An Optimized Interaction Strategy for Bayesian Relevance Feedback, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.553, June 23-25, 1998
• 7: R.O. Duda and P.E. Hart. Pattern Classification and Scene Analysis. John Wiley & Sons, Inc., New York, 1973
• 8: Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146]
• 9: Y. Freund and R. E. Schapire. "A short introduction to boosting", Journal of Japanese Society for Artificial Intelligence, 14(5):771-780, September, 1999
• 10: J. Friedman, "Regularized Discriminant Analysis," Journal of American Statistical Association, vol 84, no. 405, pp. 165 1751989
• 11: P. Hong, Q. Tian, T. S. Huang, "Incorporate Support Vector Machines to Content-Based Image Retrieval with Relevance Feedback", IEEE Int'l Conf. on Image Proc. (ICIP'2000), Vancouver, Canada, Sep lo-13,200O.
• 12: Yoshiharu Ishikawa , Ravishankar Subramanya , Christos Faloutsos, MindReader: Querying Databases Through Multiple Examples, Proceedings of the 24rd International Conference on Very Large Data Bases, p.218-227, August 24-27, 1998
• 13: J. Laaksonen, M. Koskela, and E. Oja. "PicSOM: Self- Organizing Maps for Content-Based Image Retrieval," Proc. of IJCNN'99. Washington, DC. July 1999
• 14: C. Meilhac and C. Nastar. "Relevance feedback and category search in image databases," In IEEE International Conference on Multimedia Computing and Systems, Florence, Italy, June 1999
• 15: S. Mika, G. Ratsch, and K.-R. Muller. "A mathematical programming approach to the Kernel Fisher algorithm," In Advances in Neural Information Processing Systems 13, 2001 (accepted)
• 16: M. Naphades, R. Wang, T. Huang, "Multimodal pattern matching for audio/visual query and retrieval," SPIE Photonics West, Storage and Retrieval for Media Databases, San Jose, CA. Jan 2001.
• 17: C. Nastar , M. Mitschke , C. Meilhac, Efficient Query Refinement for Image Retrieval, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.547, June 23-25, 1998
• 18: Jing Peng , Bir Bhanu , Shan Qing, Probabilistic feature relevance learining for content-based image retrieval, Computer Vision and Image Understanding, v.75 n.1-2, p.150-164, July/Aug. 1999 [doi>10.1006/cviu.1999.0770]
• 19: R. W. Picard, T. P. Minka, and M. Szummer, 'Modeling User Subjectivity in Image Libraries", IEEE Int'l Conf. Image Processing (ICIP'96), Lausanne, Sept. 1996.
• 20: Kriengkrai Porkaew , Sharad Mehrotra , Michael Ortega, Query Reformulation for Content Based Multimedia Retrieval in MARS, Proceedings of the IEEE International Conference on Multimedia Computing and Systems Volume II-Volume 2, p.747, June 07-11, 1999
• 21: Y. Rui, T. S. Huang, M. Ortega, and S. Mehrotra, "Relevance Feedback: A Power Tool in Interactive Content- Based Image Retrieval", IEEE Tran on Circuits and Systems for Video Technology, Vol 8, No. 5: 644-655, Sept., 1998,
• 22: Y. Rui, T. S. Huang, "Optimizing learning in image retrieval", Proc. IEEE Conf. Computer Vision and Pattern Recognition, Hilton Head Island, South Carolina, June, 2000
• 23: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 24: Simone Santini , Ramesh Jain, Integrated Browsing and Querying for Image Databases, IEEE MultiMedia, v.7 n.3, p.26-39, July 2000 [doi>10.1109/93.879766]
• 25: R. Schettini, G. Ciocca, and I. Gagliardi, 'Content-based Color Image Retrieval with Relevance Feedback", IEEE Int'l Conf. Image Processing (ICIP'99), Kobe, 1999.
• 26: John R. Smith , Shih-Fu Chang, VisualSEEk: a fully automated content-based image query system, Proceedings of the fourth ACM international conference on Multimedia, p.87-98, November 18-22, 1996, Boston, Massachusetts, United States [doi>10.1145/244130.244151]
• 27: J. R. Smith and S. F. Chang, Transform features for texture classification and discrimination in large image databases, Proc. IEEE Int'l Conf. Image Processing, Austin, Texas, Oct. 1994
• 28: Stephen W. Smoliar , HongJiang Zhang, Content-Based Video Indexing and Retrieval, IEEE MultiMedia, v.1 n.2, p.62-72, June 1994 [doi>10.1109/93.311653]
• 29: K. Tieu and P. Viola, 'Boosting Image Retrieval", Proc. IEEE Conf. Computer Vision and Pattern Recognition, Hilton Head Island, SC, June, 2000.
• 30: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 31: Nuno Vasconcelos , Andrew Lippman, Bayesian Relevance Feedback for Content-Based Image Retrieval, Proceedings of the IEEE Workshop on Content-based Access of Image and Video Libraries (CBAIVL'00), p.63, June 16-16, 2000
• 32: Erling Wold , Thom Blum , Douglas Keislar , James Wheaton, Content-Based Classification, Search, and Retrieval of Audio, IEEE MultiMedia, v.3 n.3, p.27-36, September 1996 [doi>10.1109/93.556537]
• 33: M. E. J. Wood , B. T. Thomas , N. W. Campbell, Iterative refinement by relevance feedback in content-based digital image retrieval, Proceedings of the sixth ACM international conference on Multimedia, p.13-20, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290750]
• 34: Marcel Worring , Arnold W. M. Smeulders , Simone Santini, Interaction in Content-Based Image Retrieval: The Evaluation of the State-of-the-Art Review, Proceedings of the 4th International Conference on Advances in Visual Information Systems, p.26-36, November 02-04, 2000
• 35: Y. Wu, Q. Tian, T. S. Huang, "Discriminant EM Algorithm with Application to Image Retrieval", Proc. IEEE Conf. Computer Vision and Pattern Recognition, Hilton Head Island, SC, June, 2000.
• 36: Xiang Sean Zhou , Thomas S. Huang, Image Retrieval: Feature Primitives, Feature Representation, and Relevance Feedback, Proceedings of the IEEE Workshop on Content-based Access of Image and Video Libraries (CBAIVL'00), p.10, June 16-16, 2000
• 37: Xiang Sean Zhou , Thomas S. Huang, Edge-based structural features for content-based image retrieval, Pattern Recognition Letters, v.22 n.5, p.457-468, April 2001 [doi>10.1016/S0167-8655(00)00124-0]
• 38: X. S. Zhou, T. S. Hunag, "A generalized relevance feedback scheme for image retrieval", Proceedings of SPIE Vol. 4210: Internet Multimedia Management Systems, Boston, MA. November 6-7,200

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; Search process; Query formulation

General Terms:
Algorithms, Design, Experimentation, Human Factors, Theory

Keywords:
discriminating transform, kernel method, multimedia retrieval, relevance feedback, support vector machine