人臉偵測與辨識的研究發展至今已累積了相當多的方法，傳統方法大多數著重於開發各種不同的低階臉部特徵進行分析，但以這個觀點出發的研究成果逐漸趨於極限，尤其用於情況複雜的真實影像中（如照片或電影資料），其面臨著難以將辨識準確率向上提升的瓶頸。檢視近幾年電腦視覺與圖形辨識以及多媒體領域的研究趨勢，許多文獻引進了潛藏語義情境（Latent Semantic Context）或是概念分析（Concept Analysis）的高階特徵來輔助低階的特徵，期望可以藉此突破傳統方法的瓶頸以增進辨識效能，並試圖縮短電腦機器與人類認知之間的語義間隙 （Semantic Gap）。本研究以具有角色互動關係的電影為實驗對象，著手於發展一個非監督式（Unsupervised）自動化的方法在電影中建立角色的社群網路（Roles’ Social Network）這類型的高階資料結構。利用臉部的低階特徵來進行相似性傳遞（Affinity Propagation）分群演算法，將相同角色的人臉軌跡群聚在一起。並提出一個新的方式 － 基於鏡頭交錯切換的線索（Shot Alternation Cues）來量化角色之間的互動程度以完成社群網路的建立。這個方法在我們所建立的社群網路中，更適合用來描述角色之間的關係。最後，我們將極大集團（Maximal Clique）的概念應用於從自動化所建立的社群網路中找出群體（Community）。針對真實的電影資料進行實驗，驗證了我們所提出的方法之有效性。

A vast amount of researches have been conducted on the subject of face detection and face recognition in the past decades. Most existing methods develop low-level features to tackle these problems. However, approaches based on low-level audiovisual features can rarely achieve promising recognition performances given real-world, complex data. Reviewing the literatures in the fields of computer vision, pattern recognition and multimedia computing, many studies have introduced high-level features, such as latent semantic context and concept analysis, based on which complementary solutions have been proposed to the problem. These high-level feature based approaches are shown to be able to more effectively bridge the semantic gap between machine and human perspective, and, thus, improve the recognition performance. In this thesis, we develop an automatic, unsupervised method to construct roles’ social network in movies. The resulting social network is useful for extracting high level features (e.g. the leading roles and the roles’ communities) for the movie’s contents. We first apply the affinity propagation clustering algorithm on preprocessed face tracks and generate face clusters for the roles. Next, we propose a new method that quantifies the interactions between roles based on shot alternation cues. This method is more appropriate to describe the relationship between roles and based on which we construct the roles’ social network. Finally, we use the maximal clique concept to identify communities from our automatically constructed social network. Experiments on real-world data validate the effectiveness of the proposed method.

[01]M. E. J. Newman and M. Girvan, “Finding and Evaluating Community Structure in Network”, Physical Reviwe E, vol. 69 no. 2, Aug., 2003.
[02]Elmagarmid, Ahmed K., Managing and Mining Graph Data, Springer US, 2010.
[03]Chung-Yi Weng, Wei-Ta Chu and Ja-Ling Wu, “Movie analysis based on roles’ social network,” Proc. IEEE ICME, Beijing, China, 2007.
[04]Jae-Ho Lee and Whoi-Yul Kim, “Video Summarization and Retrieval System Using Face Recognition and MPEG-7 Descriptors,” Proc. ACM CIVR, pp.170-178, 2004.
[05]W.-H. Cheng, Y.-Y. Chuang, B.-Y. Chen, J.-L. Wu, S.-Y. Fang, Y.-T. Lin C.-C. Hsieh, C.-M. Pan, W.-T. Chu, and M.-C. Tien, “Semantic-Event Based Analysis and Segmentation of Wedding Ceremony Videos”, Proc. ACM MIR, Step. 2007.
[06]Chung-Yi Weng, Wei-Ta Chu and Ja-Ling Wu, “RoleNet: Treat a Movie as a small society,” Proc. ACM MIR, pp.51-60, 2007.
[07]Chung-Yi Weng, Wei-Ta Chu and Ja-Ling Wu, “RoleNet: Movie analysis from the perspective of social network,” IEEE Trans. on Multimedia, vol.11, no. 2, pp.256-271, February, 2009.
[08]T. Cour, B. Sapp, A. Nagle, and B. Taskar, “Talking Pictures: Temporal Grouping and Dialog-Supervised Person Recognition”, CVPR, 2010
[09]T. Cour, B. Sapp, A. Nagle, and B. Taskar, “Learning from Ambiguously Labeled Images”, CVPR, 2009
[10]Kun Yuan, Hongxun Yao, Rongrong Ji, and Xiaoshuai Sun, “Ming Actor Correlations With Hierarchical Concurrence Parsing”, Proc. IEEE ICASSP, 2010.
[11]Yi-Fan Zhang, Changsheng Xu, Hanqing Lu, and Yeh-Min Huang, “Character Identification in Feature-Length Films Using Global Face-Name Matching” , IEEE Trans. On Multimedia, vol. 11, no. 7, pp. 1276-1288, Nov. 2009.
[12]Chao Liang, Yifan Zhang, Jian Cheng, Changsheng Xu and Hanqing Lu, “A Novel Role-Based Movie Scene Segmentation Method,” Proc. PCM, pp. 917-922, 2009
[13]Liangliang Cao, Jiebo Luo and Thomas S. Huang, “Annotating Photo Collection by Label Propagation According to Multiple Similarity Cues,” Proc. ACM Multimedia, 2008.
[14]Peng Wu and Dan Tretter, “Close & Closer: Social Cluster and Closeness form Photo Collections,” Proc. ACM Multimedia, 2009.
[15]Peng Wu and Feng Tang, “Improving face clustering using social context,” Proc. ACM Multimedia, 2010.
[16]Michel Plantie and Michel Crampes, “From Photo Networks to Social Networks, Creation and Use of a Social Network Derived with Photos,” Proc. ACM Multimedia, 2010.
[17]T.Ahonen, A. Hadid and M. Pietikäinen, “Face Recognition with Local Binary Patterns”, ECCV, 2004
[18]T.Ahonen, A. Hadid and M. Pietikäinen, “Face description with local binary pattern: Application to face recognition,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 28, no. 12, pp. 2037-2041, Dec. 2006.
[19]M. Heikkilä, M. Pietikäinen and C. Schmid, “Description of interest regions with local binary patterns,” Pattern Recognition, vol. 42, no. 3. pp. 425-436, 2009.
[20]Brendan J. Frey and Delbert Dueck, “Clustering by Passing Messages Between Data Points,” Science, pp. 972-976, Feb. 2007.
[21]http://www.psi.toronto.edu/index.php?q=affinity%20propagation
[22]Bron Coen and Kerbosch Joep, “Algorithm 457: finding all cliques of an undirected graph,” Communications of the ACM, 1973, vol. 16, pp.575-577, 1973.
[23]Open Source Computer Vision Library. http://www.intel.com/technology/computing/opencv
[24]http://connect.in.com/storyboard/photos-1883385-15099153.html
[25]http://accad.osu.edu/womenandtech/Storyboard%20Resource/
[26]http://www.googlelabs.com/