3.1 运动捕获数据检索算法中的关键问题

作为检索算法的基础，骨架的层次结构分解、特征的选取、索引的构建是需要重点关注的问题。同时，也需要关注运动数据中数值相似性（numerical similar）与逻辑相似性（logical similar）的定义与区别。

3.1.1 数值相似性与逻辑相似性

运动的相似性有数值相似性与逻辑相似性两种判断标准。数值相似是指两个运动每时每刻都有着相似的运动轨迹（所有关节的轨迹）。数值相似性能严格判断两个运动是否为逐帧相似，但某些帧不相似或某些关节的运动轨迹不相似，不一定不是相似的运动。运动的逻辑相似性是指运动之间有相同的动作语义，但是在具体动作上稍有差别[31~33]。这种差别可能是时间域内的，也可能是空间域内的。如图3.1所示[31]，图3.1（a）和图3.1（c）是一个“向前踢”和一个“侧面踢”的对比。需要注意的是，这两个运动在手臂、躯干姿态以及“踢”轨迹上都是不同的，但是它们属于一个动作语义，是逻辑相似性的运动。图3.1（b）和图3.1（d）的“伸手”运动，尽管有相似的骨架姿态，但却是指向完全相反的两个方向。对这种运动如果用基于DTW等的数值相似性的比较算法，则不能检索出逻辑相似性的运动。

图3.1 逻辑相似的运动不一定数值相似

在本书中，将运动检索算法分为基于数值相似性的方法和基于逻辑相似性的方法。

3.1.2 骨架的层次结构分解

人体数据是多维数据，为了克服“维数灾难”，需要对数据进行降维，虽然已有PCA和ICA等降维方法，但将数据的骨架结构进行分解，无疑是最好的一种降维方式。如在Wu等[34]的方法中，将人体骨骼分成3个块，分别是躯干分区（torso partition）、手臂分区（arm partition）和腿部分区（leg partition），如图3.2所示[34]。

对骨架进行分解不但有利于数据降维，而且很多算法利用这种人体骨架分解，能实现对人体某些部分的检索，如只检索手、头的运动等。这方面典型的有Deng等[32]和Pradhan等[35]的工作。其中，Deng等[32]将人体分成4个层次，每个层次对应不同分割粒度，如图3.3所示[32]。在检索时，可以由用户指定对层次结构中的任何层的任何部分进行检索。

图3.2 人体骨骼结构的一种切分方法

Liu等[36]采用基于近邻的动态聚类算法构建一个5层的运动索引树。这5个层次从上到下分别是{Root}、{Lhip, Rhip, Chest}、{Lknee, Rknee, Neck, Lshoulder,Rshoulder}、{Lankle, Rankle, Head, Lelbow, Relbow}和{Lwrist, Rwrist}。在实时检索时，这些层次索引结构可以有效地分流检索结果集，从而加快检索速度。

3.1.3 索引的构建

传统时间序列数据的检索多依赖于索引结构的支持，这些结构大多数是树状结构，如R*-tree结构[37, 38]等。对运动捕获数据这种时间序列数据来说，也需要索引的支持，典型的索引结构有运动索引树[36]、二叉树[34]等。Muller等[33]根据定义的几何特征，以对应运动序列的二进制串为索引。Chiu等[39]利用SOM（self-orgamizing map）构建了索引图（index map）。Keogh等[30]基于Uniform scaling和Bounding envelopes建立层次索引结构，从而能够显著加速搜索。

图3.3 人体骨骼的层次结构

3.1.4 特征的选取

很多方法采用原始的joint数据作为特征，也有些方法定义了几何特征，最典型的是Muller定义的布尔几何特征[33]。