Client-centered multimedia content adaptation

ABSTRACT

The design and implementation of a client-centered multimedia content adaptation system suitable for a mobile environment comprising of resource-constrained handheld devices or clients is described. The primary contributions of this work are: (1) the overall architecture of the client-centered content adaptation system, (2) a data-driven multi-level Hidden Markov model (HMM)-based approach to perform both video segmentation and video indexing in a single pass, and (3) the formulation and implementation of a Multiple-choice Multidimensional Knapsack Problem (MMKP)-based video personalization strategy. In order to segment and index video data, a video stream is modeled at both the semantic unit level and video program level. These models are learned entirely from training data and no domain-dependent knowledge about the structure of video programs is used. This makes the system capable of handling various kinds of videos without having to manually redefine the program model. The proposed MMKP-based personalization strategy is shown to include more relevant video content in response to the client's request than the existing 0/1 knapsack problem and fractional knapsack problem-based strategies, and is capable of satisfying multiple client-side constraints simultaneously. Experimental results on CNN news videos and Major League Soccer (MLS) videos are presented and analyzed.

REFERENCES

• 1: M. Mostofa Akbar , Eric G. Manning , Gholamali C. Shoja , Shahadat Khan, Heuristic Solutions for the Multiple-Choice Multi-dimension Knapsack Problem, Proceedings of the International Conference on Computational Science-Part II, p.659-668, May 28-30, 2001
• 2: Adrien Bartoli , Navneet Dalal , Radu Horaud, Motion Panoramas: Research Articles, Computer Animation and Virtual Worlds, v.15 n.5, p.501-517, December 2004 [doi>10.1002/cav.v15:5]
• 3: Baum, L. E., Peterie, T., Souled, G., and Weiss, N. 1970. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. Ann. Math. Statist, 164--171.
• 4: Suchendra M. Bhandarkar , Yashodhan S. Warke , Aparna A. Khombhadia, Integrated Parsing of Compressed Video, Proceedings of the Third International Conference on Visual Information and Information Systems, p.269-276, June 02-04, 1999
• 5: Boreczky, J. S. and Wilcox. L. D. 1998. A hidden Markov model framework for video segmentation using audio and image features. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP).
• 6: Peter F. Brown , Peter V. deSouza , Robert L. Mercer , Vincent J. Della Pietra , Jenifer C. Lai, Class-based n-gram models of natural language, Computational Linguistics, v.18 n.4, p.467-479, December 1992
• 7: Chen, M. J., Chu, M. C., and Pan, C. W. 2002. Efficient motion estimation algorithm for reduced frame-rate video transcoder. IEEE Trans. Circ. Syst. Video Technol. 12, 4, 269--275.
• 8: S. Eickeler , S. Muller, Content-based video indexing of TV broadcast news using hidden Markov models, Proceedings of the Acoustics, Speech, and Signal Processing, 1999. on 1999 IEEE International Conference, p.2997-3000, March 15-19, 1999 [doi>10.1109/ICASSP.1999.757471]
• 9: S. Eickeler , G. Rigoll, A novel error measure for the evaluation of video indexing systems, Proceedings of the Acoustics, Speech, and Signal Processing, 2000. on IEEE International Conference, p.1991-1994, June 05-09, 2000 [doi>10.1109/ICASSP.2000.859222]
• 10: Eleftheriadis, A. and Batra, P. 2006. Dynamic rate shaping of compressed digital video. IEEE Trans. Multimedia 8, 2, 297--314.
• 11: Fellbaum, C., Ed. 1998. WordNet—An Electronic Lexical Database. The MIT Press, Cambridge, MA.
• 12: 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]
• 13: Forney, G. D. 1973. The Viterbi algorithm. Proceedings of the IEEE, vol. 61, No. 3, 268-278.
• 14: Hernandez, R. P. and Nikitas, N. J. 2005. A new heuristic for solving the multiple-choice multidimensional knapsack problem. IEEE Trans. Syst. Man Cybernetics, Part A 35, 5, 708--717.
• 15: Huang, J., Liu, Z., and Wang, Y. 2005. Joint scene classification and segmentation based on hidden Markov model. IEEE Trans. Multimedia 7, 3, 538--550.
• 16: Irani, M., Hsu, S., and Anandan, P. 1995. Mosaic-based video compression. In Proceedings of the SPIE Conference on Electronic Imaging, Digital Video Compression: Algorithms and Technologies, vol. 2419, 242--253.
• 17: Irani, M., Anandan, P., Bergen, J., Kumar, R., and Hsu, S. 1996. Efficient representations of video sequences and their applications. Signal Process. Image Commun. Special Issue on Image Video Semantics: Processing, Analysis, Appl. 8, 4, 327--351.
• 18: Md. Shahadatullah Khan , Kin F. Li , Eric G. Manning, Quality adaptation in a multisession multimedia system: model, algorithms, and architecture, University of Victoria, Victoria, B.C., Canada, 1998
• 19: Leacock, C. and Chodorow, M. 1998. Combining local context and wordnet similarity for word sense identification. In WordNet: An Electronic Lexical Database, Fellbaum C. (Ed.), MIT Press, Cambridge, MA, 265--283.
• 20: Baoxin Li , M. Ibrahim Sezan, Event Detection and Summarization in Sports Video, Proceedings of the IEEE Workshop on Content-based Access of Image and Video Libraries (CBAIVL'01), p.132, December 14-14, 2001
• 21: Li, C. S., Mohan, R., and Smith, J. R. 1998. Multimedia content description in the Info-Pyramid. In Proceedings of the ICASSP'98, Special Session on Signal Processing in Modern Multimedia Standards, vol.6, 3789--3792.
• 22: Bernard Merialdo , Kyung Tak Lee , Dario Luparello , Jeremie Roudaire, Automatic construction of personalized TV news programs, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.323-331, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319637]
• 23: Y. Nakajima , H. Hori , T. Kanoh, Rate conversion of MPEG coded video by re-quantization process, Proceedings of the 1995 International Conference on Image Processing (Vol. 3)-Volume 3, p.3408, October 23-26, 1995
• 24: Ney, H. and Ortmanns, S. 1999. Progress on dynamic programming search for continuous speech recognition. IEEE Signal Proc. Mag. 16, 5, 64--83.
• 25: Papoulis, A. 1984. Probability, Random Variables, and Stochastic Processes, 2nd Ed. McGraw-Hill, New York, 104, 148.
• 26: Rabiner, L. R. 1989. A tutorial on hidden Markov models and selected applications in speech recognition. In Proceedings of the IEEE 77, 2, 257--286.
• 27: Shinoda, K., Bach, N. H., Furui, S., and Kawai, N. 2005. Scene recognition using hidden Markov models for video database. In Proceedings of the Symposium on Large-Scale Knowledge Resources (LKR'05), 107--110.
• 28: C. G. M. Snoek , M. Worring, Time interval maximum entropy based event indexing in soccer video, Proceedings of the 2003 International Conference on Multimedia and Expo - Volume 3 (ICME '03), p.481-484, July 06-09, 2003
• 29: Sun, H., Kwok, W., and Zdepski, J. 1996. Architectures for MPEG compressed bitstream scaling. IEEE Trans. Circ. Syst. Video Technol. 6, 191--199.
• 30: Tamura, H., Mori, S., and Yamawaki, T. 1978. Textural features corresponding to visual perception. IEEE Trans. Syst. Man Cybernetics 8, 460--472.
• 31: Belle L. Tseng , Ching-Yung Lin , John R. Smith, Using MPEG-7 and MPEG-21 for Personalizing Video, IEEE MultiMedia, v.11 n.1, p.42-53, January 2004 [doi>10.1109/MMUL.2004.1261105]
• 32: Tseng, B. L. and Smith, J. R. 2003. Hierarchical video summarization based on context clustering. In Proceedings of the SPIE, 5242, 14--25.
• 33: Tseng, B. L., Lin, C. Y., and Smith, J. R. 2002. Video personalization and summarization system. In Proceedings of the IEEE Workshop on Multimedia Signal Processing, 424--427.
• 34: Z. Uykan , H. N. Koivo, Unsupervised learning of sigmoid perceptron, Proceedings of the Acoustics, Speech, and Signal Processing, 2000. on IEEE International Conference, p.3486-3489, June 05-09, 2000 [doi>10.1109/ICASSP.2000.860152]
• 35: Vanderbei, R. J. 1997. Linear Programming: Foundations and Extensions. Kluwer Academic, Norwell, MA.
• 36: Paul Viola , Michael J. Jones, Robust Real-Time Face Detection, International Journal of Computer Vision, v.57 n.2, p.137-154, May 2004 [doi>10.1023/B:VISI.0000013087.49260.fb]
• 37: Yong Wei , Hongyu Wang , Suchendra M. Bhandarkar , Kang Li, Parallel Algorithms for Motion Panorama Construction, Proceedings of the 2006 International Conference Workshops on Parallel Processing, p.82-92, August 14-18, 2006 [doi>10.1109/ICPPW.2006.59]
• 38: Wheeler, E. S. 2002. Zipf's law and why it works everywhere. Glottometrics, 4, 45--48.
• 39: Zhu, W., Yang, K., and Beacken, M. 1998. CIF-to-QCIF video bitstream down conversion in the DCT domain. Bell Labs Tech. J. 3, 3, 21--29.

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

Keywords:
Video personalization, hidden Markov models, multiple choice multidimensional knapsack problem, video indexing