Cast indexing for videos by NCuts and page ranking

ABSTRACT

Cast indexing is an important video mining technique which provides audience the capability to efficiently retrieve interested scenes, events, and stories from a long video. This paper proposes a novel cast indexing approach based on Normalized Graph Cuts (NCuts) and Page Ranking. The system first adopts face tracker to group face images in each shot into face sets, and then extract local SIFT feature as the feature representation. There are two key problems for cast indexing. One is to find an optimal partition to cluster face sets into main cast. The other is how to exploit the latent relationships among characters to provide a more accurate cast ranking. For the first problem, we model each face set as a graph node, and adopt Normalized Graph Cuts (NCuts) to realize an optimal graph partition. A novel local neighborhood distance is proposed to measure the distance between face sets for NCuts, which is robust to outliers. For the second problem, we build a relation graph for characters by their co-occurrence information, and then adopt the PageRank algorithm to estimate the Important Factor (IF) of each character. The PageRank IF is fused with the content based retrieval score for final ranking. Extensive experiments are carried out on movies, TV series and home videos. Promising results demonstrate the effectiveness of proposed methods.

REFERENCES

• 1: Ognjen Arandjelovic , Gregory Shakhnarovich , John Fisher , Roberto Cipolla , Trevor Darrell, Face Recognition with Image Sets Using Manifold Density Divergence, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.581-588, June 20-26, 2005 [doi>10.1109/CVPR.2005.151]
• 2: Ognjen Arandjelovic , Andrew Zisserman, Automatic Face Recognition for Film Character Retrieval in Feature-Length Films, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.860-867, June 20-26, 2005 [doi>10.1109/CVPR.2005.81]
• 3: Mark Everingham , Andrew Zisserman, Identifying Individuals in Video by Combining "Generative" and Discriminative Head Models, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1103-1110, October 17-20, 2005 [doi>10.1109/ICCV.2005.116]
• 4: Yuan J. H., Zheng W. J., Chen L., et. al. Tsinghua University a TRECVID 2004: shot boundary detection and high-level feature extraction, In NIST workshop of TRECVID 2004.
• 5: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 6: Lawrence, P. and Sergey, B. The PageRank Citation Ranking: Bringing Order to the Web. Stanford Digital Library Technologies Project, 1998
• 7: Kuang-Chih Lee , David Kriegman, Online Learning of Probabilistic Appearance Manifolds for Video-Based Recognition and Tracking, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.852-859, June 20-26, 2005 [doi>10.1109/CVPR.2005.260]
• 8: Zhang L., Ai HZ, Lao SH, Robust Face Alignment Based On Hierarchical Classifier Network, T. S. Huang et al. (Eds.): HCI/ECCV 2006, LNCS 3979, pp.1--11, 2006. Springer-Verlag Berlin Heidelberg 2006.
• 9: David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004 [doi>10.1023/B:VISI.0000029664.99615.94]
• 10: Rasheed, Z., Shah, M., Detection and representation of scenes in videos. IEEE Transactions on Multimedia, Volume 7, Issue 6, Dec. 2005, 1097--1105.
• 11: Anil K. Jain , Stan Z. Li, Handbook of Face Recognition, Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 12: Studholme, C., Hill, D. and Hawkes, D. An overlap invariant entropy measure of 3D medical image alignment. Pattern recognition. 1999, 712--721.
• 13: Fan W., Wang T., Bouguet, J. Y., Hu W., et. al. Semi-supervised Cast Indexing for Feature-Length Films. In Proeedings of the 13^th International MultiMedia Modelling Conference (MMM 2007).
• 14: Li Y., Ai HZ, Huang C., Lao SH, Robust Head Tracking with Particles Based on Multiple Cues Fusion, T. S. Huang et al. (Eds.): HCI/ECCV 2006, LNCS 3979, pp.29--39, 2006. Springer-Verlag Berlin Heidelberg 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

General Terms:
Algorithms, Design, Experimentation, Management

Keywords:
NCuts, cast indexing, cast ranking, local neighbor distance, main cast detection, page ranking