Keyframe Extraction from Human Motion Capture Databy Simplex Hybrid Genetic Algorithm
LIU Xian-Mei1,2, HAO Ai-Min1, ZHAO Dan2
1.State Key Laboratory of Virtual Reality Technology and System, Beihang University, Beijing 100083 2.School of Computer and Information Technology, Northeast Petroleum University, Daqing 163318
Abstract：To obtain a compact representation of human motion based on keyframes, a method for keyframes extracting of the captured human motion data by simplex hybrid genetic algorithm is presented, which combines genetic algorithm with a local search technique to converge faster and produce the optimal solution. Firstly, the fitness function is defined to evaluate the availability of keyframe with the goals of minimal reconstruction error and optimal compression rate. Then, the reconstruction error is computed between the original motion and the reconstruction one by the weighted differences of joint positions and velocities. The velocity term helps to preserve the dynamics of motion. Finally, the individuals of initial population are optimized by the knowledge to assure the evolutionary efficiency and the population diversity. Experimental results show that the proposed method can effectively extract keyframes, produce remarkable results in terms of quality and compression ratio, and reconstruct all other non-keyframes of an animation with these keyframes.
[1] Liu Xianmei, Zhao Dan, Zhao Ya. Survey on Keyframe Technology of Data-Driven Human Animation. Computer Engineering Design, 2011, 32(3): 1006-1009 (in Chinese) (刘贤梅,赵 丹,赵 娅. 数据驱动人体动画的关键帧技术研究综述.计算机工程与设计, 2011, 32(3): 1006-1009) [2] Liu Feng, Zhuang Yueting, Wu Fei, et al. 3D Motion Retrieval with Motion Index Tree. Computer Vision and Image Understanding, 2003, 92(2/3): 265-284 [3] Park M J, Shin S Y. Example-Based Motion Cloning. Computer Animation and Virtual Worlds, 2004, 15(3/4): 245-257. [4] Lim I S, Thalmann D. Key-Posture Extraction out of Human Motion Data by Curve Simplification // Proc of the 23rd Annual International Conference of the IEEE Engineering in Medicine and Biology Society. Istanbul, Turkey, 2001, II: 1167-1169 [5] Shen Junxing, Sun Shouqian, Pan Yunhe. Key-Frame Extraction from Motion Capture Data. Journal of Computer-Aided Design Computer Graphics, 2004, 16(5): 719-723 (in Chinese) (沈军行,孙守迁,潘云鹤.从运动捕获数据中提取关键帧.计算机辅助设计与图形学学报, 2004, 16(5): 719-723) [6] Yang Tao, Xiao Jun, Wu Fei, et al. Extraction of Keyframe of Motion Capture Data Based on Layered Curve Simplification. Journal of Computer-Aided Design Computer Graphics, 2006, 18(11): 1691-1697 (in Chinese) (杨 涛,肖 俊,吴 飞,等.基于分层曲线简化的运动捕获数据关键帧提取.计算机辅助设计与图形学学报, 2006, 18(11): 1691-1697) [7] Bulut E, Capin T. Key Frame Extraction from Motion Capture Data by Curve Saliency // Proc of the International Conference on Computer Animation and Social Agents. Hasselt, Belgium, 2007: 63-67 [8] Gong Yihong, Liu Xin. Video Summarization Using Singular Value Decomposition // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Hilton Head Island, USA, 2000, II: 174-180 [9] Cooper M, Foote J. Summarizing Video Using Non-Negative Similarity Matrix Factorization // Proc of the IEEE Workshop on Multimedia Signal Processing. Saint Thomas, USA, 2002: 25-28 [10] Huang Kesen, Chang Chunfa, Hsu Y Y, et al. Key Probe: A Technique for Animation Keyframe Extraction. Visual Computation, 2005, 21(8/9/10): 532-541 [11] Lee T Y, Lin C H, Wang Y S, et al. Animation Key-Frame Extraction and Simplification Using Deformation Analysis. IEEE Trans on Circuits and Systems for Video Technology, 2008, 18(4): 478-486 [12] Xue Baoju, Xie Jiancang, Zhang Xiaohong. Application of the Simplex Hybrid Genetic Algorithm into the Optimal Operation of Reservoir. Journal of Water Resources Water Engineering, 2008, 19(5): 42-45 (in Chinese) (薛保菊,解建仓,张晓红.单纯形混合遗传算法在水库优化调度中的应用研究.水资源与水工程学报, 2008, 19(5): 42-45) [13] Shen Hao, Wang Xin. Application of Improved Simplex Genetic Algorithm Hybrid in Automatic Optical Fiber Alignment. Opto-Electronic Engineering, 2006, 33(10): 67-71 (in Chinese) (沈 浩,王 昕.改进遗传单纯形混合算法在光纤对接中的应用.光电工程, 2006, 33(10): 67-71) [14] Xiao Hongfeng, Tan Guanzheng. Niche Hybrid Genetic Algorithm Based on Simplex. Journal of Chinese Computer Systems, 2008, 29(9): 1719-1725 (in Chinese) (肖宏峰,谭冠政.基于单纯形的小生境混合遗传算法.小型微型计算机系统, 2008, 29(9): 1719-1725) [15] Wang Jianping, Cheng Shengtong. Application of Genetic Algorithm and Simplex Method in Parameter Identification of Complicated Environmental Model. Journal of Hydraulic Engineering, 2005, 36(6): 674-679 (in Chinese) (王建平,程声通.遗传单纯形混合算法在复杂环境模型参数识别中的应用.水利学报, 2005, 36(6): 674-679) [16] Zheng Zhaobao. Classification of Image Texture by Combination of Genetic Algorithm and Simplex Method. Acta Geodaetica et Cartographica Sinica, 2003, 32(4): 325-329 (in Chinese) (郑肇葆.遗传算法与单纯形法组合的影像纹理分类方法.测绘学报, 2003, 32(4): 325-329) [17] Yen J, Liao J C, Lee B, et al. A Hybrid Approach to Modeling Metabolic Systems Using Genetic Algorithm and Simplex Method. IEEE Trans on Systems, Man and Cybernetics, 1998, 28(2): 173-191 [18] Rem Ziwu, San Ye, Chen Junfeng. Hybrid Simplex-Improved Genetic Algorithm for Global Numerical Optimization. Acta Automatica Sinica, 2007, 33(1): 91-96 (in Chinese) (任子武,伞 冶,陈俊风.全局数值寻优的一种混合遗传算法.自动化学报, 2007, 33(1): 91-96) [19] Zhu Dengming, Wang Zhaoqi. Extraction of Keyframe from Motion Capture Data Based on Motion Sequence Segmentation. Journal of Computer-Aided Design Computer Graphics, 2008, 20(6): 787-792 (in Chinese) (朱登明,王兆其.基于运动序列分割的运动捕获数据关键帧提取.计算机辅助设计与图形学学报, 2008, 20(6): 787-792) [20] Barbic J, Safonova A, Pan Jiayu, et al. Segmenting Motion Capture Data into Distinct Behaviors // Proc of the Conference on Graphics Interface. Ontario, Canada, 2004: 185-194 [21] Yin Wei. Research of the 3D Key-Frame Animation Production Extraction System. Ph.D Dissertation. Dalian, China: Dalian University of Technology, 2008: 32-37 (in Chinese) (尹 伟.三维关键帧动画的生成与压缩系统的研究.博士学位论文.大连:大连理工大学, 2008: 32-37) [22] Zhang Qiaosheng. Research on Date-Driven Character Animations Techniques. Ph.D Dissertation. Daqing, China: Daqing Petroleum Institute, 2010: 34-38 (in Chinese) (张巧生.数据驱动的角色动画关键技术研究.博士学位论文.大庆:大庆石油学院, 2010: 34-38) [23] Liu Yungen, Liu Jingang. Keyframe Extraction from Motion Capture Data by Optimal Reconstruction Error. Journal of Computer-Aided Design Computer Graphics, 2010, 22(4): 670-675 (in Chinese) (刘云根,刘金刚.重建误差最优化的运动捕获数据关键帧提取.计算机辅助设计与图形学学报, 2010, 22(4): 670-675)
2011, Vol. 24 
