Dynamic Time Warping( DTW DTW 30 k-d tree Forebes [1] 2. DTW[2] DTW DTW DTW Forbes[1] k-d tree DTW Hsu[3] DTW Zhu[4] K-SVD Sun[5] Self-S

Transcription

1 情報処理学会インタラクション 2015 IPSJ Interaction 2015 A /3/5 1,a) Natapon Pantuwong Dynamic Time Warping 2 DTW DTW 30 k-d tree [1] A Rapid Motion Retrieval Technique using Simple and Discrete Representation of Feature Vector Takahara Kensuke 1,a) Natapon Pantuwong 2 Yoshikawa Takeshi 1 Nonaka Hidetoshi 1 Sugimoto Masanori 1 Abstract: In this paper, we propose a rapid motion retrieval technique using Dynamic Time Warping. Frames of motions are represented by feature vectors whose elements are integer values. The number of the feature vector dimension is reduced by using the Principal Component Analysis method and values of elements in the vector are quantized into two bits. The similarity matrix between frames of motions represented by the feature vectors is generated for rapid calculation of Dynamic Time Warping. Preliminary experiments are conducted to find the optimum dimension number of the feature vector by evaluating the motion retrieval performance. Comparative experiments with existing methods have proved that our proposed technique can complete retrieval tasks more than 30 times faster than the traditional Dynamic Time Warping method and shown almost the same level of precision and rapid calculation time as the method described in [1] using the k-d tree algorithm DCG 3DCG 1 2 King Mongkut s Institute of Technology Ladkrabang a) takahara@main.ist.hokudai.ac.jp 3D Kinect 2015 Information Processing Society of Japan 390

2 Dynamic Time Warping( DTW DTW 30 k-d tree Forebes [1] 2. DTW[2] DTW DTW DTW Forbes[1] k-d tree DTW Hsu[3] DTW Zhu[4] K-SVD Sun[5] Self-Similarity Matrix Krüger[6] k-d tree k DTW DTW Huang[7] ( ) Qi[8] K Kapadia[9] Trie Chao[10] CG Zhou[11] Sparse Representation 2 Müller[12] 3 DTW Chen[13] Choi[14] Information Processing Society of Japan 391

3 0 1 x 2 3 n ( ) dist( ) n 0 dist( 4 1,1) 0 dist 1,0 4 1,0 D= 0 DTW DTW (x,y) D (1,1) X Y 1 3 Oshita[15] 1 DTW Sakoe[16] 2 DTW Keogh[17] 3. DTW , 1, 2, DTW 3.1 ( ) CMU [18] Müller[12] n 2 n i i (1 i n) a ji j i µ i i σ i j g j = (g j1,, g jn ) i j g ji (1) 0 a ji < µ i σ i 1 µ i σ i < a ji < µ i g ji = (1) 2 µ i < a ji < µ i + σ i 3 a ji > µ i + σ i g ji 2 0, 1, 2, 3 4 (2) g j m j 0 4 n n m j = g ji 4 i 1 (2) i=1 3.2 DTW i c i j k g j, g k i 2015 Information Processing Society of Japan 392

4 g ji g ki (2) g j g k m j m k (3)(4) g ji g ki c i weighteddiff j k dist n dist(m j, m k ) = weighteddiff(g ji, g ki ) (3) i=1 0 g ji g ki = 0 c i g ji g ki = 1 weighteddiff(g ji, g ki ) = c i 4 g ji g ki = 2 c i 4 2 g ji g ki = 3 (4) n (2) 2 n 0 4 n 1 DTW (3) (4) 4 n D D 0 D (5) m (5) j k m j m k 0 dist(1, 0) dist(2, 0) dist(4 n 2, 0) dist(4 n 1, 0) 0 dist(2, 1) dist(4 n 2, 1) dist(4 n 1, 1) D = dist(4 n 1, 4 n 2) 3.3 DTW DTW 2 x y Step 1 Step 2 x y 2 (5) (1, 1) (x, y) DTW Step 1 D DTW 2 Step 1 0 (5) 4. Windows 7 C++ AeroStream RM5J-B41/S Intel Core i GHz 4.00 GB memory CMU [18] 5 jump, walk, run, dance, kick % % 80% Müller [12] 2015 Information Processing Society of Japan 393

5 X Step 1 x Y (x,y) Step 2 y (x,y) dist(2,57) = D(57,2) dist(15,12) = D(15,12) Y Y dist(15,27) = D(27,15) (1,1) X (1,1) X 2 DTW 3 17 DTW 2 Forbes[1] k-d tree CMU[18] DTW Forbes ( ) ( ) DTW Forbes ( ) ( ) DTW Forbes 30 Forbes Forbes k-d tree k-d tree Forbes DTW Forbes 2015 Information Processing Society of Japan 394

6 Forbes DTW Forbes k-d tree [1] Forbes, K., & Fiume, E. (2005). An efficient search algorithm for motion data using weighted PCA. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation (pp ). [2] Rabiner, L. R., & Juang, B. H. (1993). Fundamentals of speech recognition (Vol. 14). [3] Hsu, E., da Silva, M., & Popoviċ, J. (2007). Guided time warping for motion editing. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation (pp ). [4] Zhu, M., Sun, H., & Deng, Z. (2012). Quaternion space sparse decomposition for motion compression and retrieval. In Proceedings of the ACM SIG- GRAPH/Eurographics Symposium on Computer Animation (pp ). [5] Sun, C., Junejo, I., & Foroosh, H. (2011). Motion Retrieval Using Low Rank Subspace Decomposition of Motion Volume. In Computer Graphics Forum (Vol. 30, Issue. 7, pp ). [6] Krüger, B., Tautges, J., Weber, A., & Zinke, A. (2010). Fast local and global similarity searches in large motion capture databases. In Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (pp. 1-10). [7] Huang, T., Liu, H., & Ding, G. (2012). Motion retrieval based on kinetic features in large motion database. In Proceedings of the 14th ACM international conference on Multimodal interaction (pp ). [8] Qi, T., Feng, Y., Xiao, J., Zhuang, Y., Yang, X., & Zhang, J. (2013). A semantic feature for human motion retrieval. Computer Animation and Virtual Worlds (Vol. 24, Issue. 3-4, pp ). [9] Kapadia, M., Chiang, I. K., Thomas, T., Badler, N. I., & Kider Jr, J. T. (2013). Efficient motion retrieval in large motion databases. In Proceedings of the ACM SIG- GRAPH Symposium on Interactive 3D Graphics and Games (pp ). [10] Chao, M. W., Lin, C. H., Assa, J., & Lee, T. Y. (2012). Human motion retrieval from hand-drawn sketch. Visualization and Computer Graphics, IEEE Transactions on (Vol.18, Issue. 5, pp ). [11] Zhou, L., Lu, Z., Leung, H., & Shang, L. (2014). Spatial temporal pyramid matching using temporal sparse representation for human motion retrieval. The Visual Computer (Vol. 30, Issue. 6-8, pp ). [12] Müller, M., & Röder, T. (2006, September). Motion templates for automatic classification and retrieval of motion capture data. In Proceedings of the 2006 ACM SIG- GRAPH/Eurographics symposium on Computer animation (pp ). [13] Chen, S., Sun, Z., Li, Y., & Li, Q. (2012, November). Partial similarity human motion retrieval based on relative geometry features. In Digital Home (ICDH), 2012 Fourth International Conference (pp ). [14] Choi, M. G., Yang, K., Igarashi, T., Mitani, J., & Lee, J. (2012, September). Retrieval and visualization of human motion data via stick figures. In Computer Graphics Forum (Vol. 31, Issue. 7, pp ). [15] Oshita, M. (2012). Multi-Touch Interface for Character Motion Control Using Example-Based Posture Synthesis, 20th International Conference on Computer Graphics. Visualization and Computer Vision 2012 (pp ). [16] Sakoe, H. & Chiba, S. (1978), Dynamic programming algorithm optimization for spoken word recognition. Trans. on ASSP (Vol. 26, Issue. 1, pp ). [17] Keogh, E., & Ratanamahatana, C. A. (2005). Exact indexing of dynamic time warping. Knowledge and information systems (Vol. 7, Issue. 3, pp ). [18] C. G. Lab. CMU Graphics Lab Motion Capture Database Information Processing Society of Japan 395