一种具有RST不变性的2D∕3D轨迹相似性度量

2017，53（11）1引言随着轨迹获取技术的发展与普及，如何根据轨迹数据判断与之相关目标的类别信息已逐步成为研究热点，如手语识别[1]、步态识别、出行交通模式识别[2]等。作为典型的时间序列数据，轨迹数据的长度不确定，因此不能直接将其用作分类特征。简单地从轨迹中提取速度、加速度、归零率、曲率、不变矩等统计特征进行分类往往准确率不高[1-2]，因此研究者一般基于距离度量获取待分类对象的相似轨迹，并借助相似轨迹的标签进行最终判决。距离度量的优劣直接关系到轨迹数据的分类效果，欧氏距离（EuclideanDistance，ED）是最常用的度量方法，计算简单，但欧氏距离要求两个序列的长度一致，且不能解决轨迹数据局部时间尺度不一致的问题。针对这一问题，研究者相继提出了动态时间规整（DynamicTimeWarping，DTW）[3-5]、最长公共子序列（LongestCommonSub-Sequences，LCSS）[6]、实补偿编辑距离（EditDistancewithRealPenalty，ERP）[7]、实序列编辑距离（EditDistanceonRealsequence，EDR）[8]等度量方法。除了局部时间尺度，视角变化等因素导致采集的轨迹数据可在2D/3D空间内自由地旋转、缩放、平移，称之为RST（Rotation，Scaling，Translation）变换。一般期望轨迹数据的分类结果不受RST变换影响，但上述距离度量不具备RST不变性。为解决RST变换问题，Yang等提出基于曲率、挠率、中心距离等组成混合指纹来描述轨迹的不变特征[9-10]，Wu等提出将轨迹点相对距离作为轨迹数据的RST不变完备度量[11]。上述方法的计算过程均需计算一种具有RST不变性的2D/3D轨迹相似性度量曹卫权CAOWeiquan盲信号处理重点实验室，成都610041NationalKeyLaboratoryofScienceandTechnologyonBlindSignalProcessing,Chengdu610041,ChinaCAOWeiquan.RST-invariantsimilaritymeasurefor2D/3Dtrajectories.ComputerEngineeringandApplications,2017,53（11）：13-17.Abstract:ThetrajectorysimilaritymeasurethatisinvarianttoRotation,ScalingandTranslation（RST）operationsiscru-cialtoapplicationssuchasprecisesignlanguagerecognition,similartrajectoryindexetc.However,traditionalsimilaritymeasuresdonotmeetthisrequirements,especiallytherotationinvariant.ThispaperproposesanRSTinvariantmeasure.Thismethodbeginsbyfiltering,normalizingandresamplingthetrajectory,whichisfollowedbyanoptimalestimationofrotationmatrixbetweenanytwotrajectories.Afterthat,theinterferenceofuncertainrotationisreliablyremoved.Thepro-posedmethodhastimecomplexityofO()Nandappliestoboth2Dand3Dtrajectories.Comparedwithinvariantslikecurvatureandtorsion,thismethodisquiteinsensitivetonoises.Keywords:trajectorydata;distancemeasure;Rotation,ScalingandTranslation（RST）invariant;optimalrotationmatrix摘要：具有旋转、缩放、平移不变性的轨迹相似性度量是实现精准手语识别、相似轨迹检索等的关键环节，常规的相似性度量往往不满足这一要求，特别是不具备旋转不变性。提出一种具有旋转、缩放、平移不变性的轨迹相似性度量方法，该方法首先对轨迹进行滤波、归一化、等间距重采样等预处理操作，然后对任意两条待比较的轨迹估计最优旋转矩阵，从而消除旋转对距离度量的干扰。该方法对二维、三维轨迹数据均适用，计算复杂度为O()N，与曲率、挠率等不变量相比，该方法对轨迹噪声不敏感。关键词：轨迹数据；距离度量；旋转、缩放、平移（RST）不变性；最优旋转矩阵文献标志码：A中图分类号：TP391doi：10.3778/j.issn.1002-8331.1701-0002基金项目：国家自然科学基金（No.U1536105）。作者简介：曹卫权（1989—），男，博士，研究领域为时空轨迹模式挖掘、机器学习，E-mail：[e-mail]。收稿日期：2017-01-03修回日期：2017-03-15文章编号：1002-8331（2017）11-0013-05ComputerEngineeringandApplications计算机工程与应用13ComputerEngineeringandApplications计算机工程与应用2017，53（11）轨迹点间的差分，因此所得的特征往往对噪声很敏感。Alicia等通过计算二维轨迹在不同方向的投影来解决RST变换条件下的手写体识别问题[12]，Michail等通过计算轨迹相对位移来消除旋转的影响[13]，但这两类方法均不能直接推广到三维轨迹的情形。本文利用归一化方法来消除轨迹数据的缩放与平移影响，并依据最优准则估计两条轨迹之间的旋转矩阵，用以对齐轨迹，最终给出一种RST无关的轨迹相似性度量方法。理论和实验分析表明，本文方法具有不受RST变换干扰、对噪声不敏感、计算复杂度较低、同时适用于二维与三维轨迹等优点。2RST不变相似性度量由于传统轨迹距离主要关注轨迹的局部时间尺度问题[3-8]，未考虑轨迹距离的旋转、平移、缩放不变性。曲率等RST不变量[9-10]涉及高阶微分操作，对噪声十分敏感。因此本文从轨迹间的最优旋转矩阵出发，设计了一种鲁棒的旋转矩阵估计方法，旋转矩阵估计过程不涉及微分操作，配合归一化、重采样等预处理环节，能够可靠地消除RST变换对轨迹相似性的干扰。2.1算法流程不考虑时间分量，轨迹数据的定义如式（1）所示。尽管提出的度量对二维、三维轨迹均适用，但为保证描述的一致性，以三维轨迹为例说明。T={}pi=()xi,yi,zi|i=1,2,…,N（1）对于任意轨迹T1、T2，本文RST不变度量计算过程如图1所示，具体步骤如下：（1）对T1、T2进行滤波，压制噪声。（2）将T1、T2零均值化以消除平移影响，并基于平均中心距离来消除缩放影响。（3）对T1、T2进行重采样，确保两者长度一致。（4）基于最优准则估计T1、T2间的旋转矩阵R，利用R将两者对齐。（5）基于已有距离度量，如DTW、LCSS等，计算轨迹对齐后的距离。在上述步骤中，滤波操作可选择采取Kalman滤波[14]、中值滤波、小波滤波[15]等，不同滤波方法对结果影响很小，不再赘述。2.2基于平均中心距离的归一化为消除平移对轨迹相似性的影响，需首先对轨迹数据零均值化，即p′i=pi-1N∑jpj（2）为消除缩放的影响，传统的Z-Score用各分量的标准差来归一化数据，如式（3）所示。x″i=x′i/σxy″i=y′i/σyz″i=z′i/σz（3）这种归一化方法不具有旋转不变性，如图2所示，图2（a）的两条形状完全相同仅大小不同的矩形轨迹T1、T2，采用Z-Score归一化后得到图2（b），由于旋转的存在，两者并未调整到同等尺寸，轨迹形状也发生了变化，因此并未有效消除缩放影响。令ri表示点pi距轨迹几何中心的距离，即ri=‖‖xi-μx,yi-μy,zi-μz=‖‖x′i,y′i,z′i（4）本文用ri的均值μr来归一化轨迹，如式（5）所示，可得到图2（c）所示的规整轨迹。pi=p′i/μr（5）易证，式（5）的归一化方法不受旋转变换干扰，能够有效消除缩放对轨迹形态的影响。2.3等间隔重采样由于下节最优旋转矩阵估计的计算过程要求轨迹T1、T2具有同等长度，因此需对两者进行重采样以保证长度一致。本文参照文献[11]的做法，根据指定的采样点数量N，对轨迹按照等间隔距离的原则采样。假定轨迹长度为L，则任意两个相邻采样点间的距离近似为L()N-1。2.4最优旋转矩阵估计等间隔采样后，将轨迹数据用3×N的矩阵（二维轨迹则为2×N）表示，如式（6）所示。P=[]p1,p2,...,pN（6）本节的目标是求解轨迹P1、P2的最优旋转矩阵R，使得P1与旋转后的轨迹RP2距离最小，如式（7）所示，其中‖‖·F表示Frobenius范数。R*=argminR‖‖P1-RP22F,s.t.RRT=I（7）注意到：‖‖P1-RP22F=tr()()P1-RP2T()P1-RP2=滤波归一化重采样滤波归一化重采样基于最优旋转矩阵对齐T1T2DTW/LCSSetc距离图1算法流程210-1-2012-2-1YXT1T2210-1-2012-2-1YXT1T2X-4-2024Y-4-2024420-2-4024-4-2YXT1T2（b）Z-Score归一化（a）原始零均值轨迹T1、T2（c）本文方法归一化图2Z-Score方法不能正确处理的情况142017，53（11）tr()PT1P1+PT2P2-PT1RP2-PT2RTP1=c-2tr()PT1RP2=c-2tr()P2PT1R=c-2tr()UΣVTRs.t.P2PT1=UΣVT=c-2tr()VTRUΣ=c-2tr()QΣs.t.Q=VTRU（8）其中U、Σ、V为P2PT1的奇异值分解[16]。联立式（7）与（8）可知，R的最优解与式（9）所示的最优Q相对应。argmaxQtr()QΣs.t.QQT=I（9）考虑到Q同样为正交矩阵，其元素||Qi,j≤1，而Σ为非负对角阵，故Q的最优解为单位阵I，从而可得R的最优解，如式（10）所示。R*=VUTs.t.P2PT1=UΣVT（10）以Auslan手语数据库[17]的单词“innocent”为例，两个样本的三维轨迹经过2.1~2.3节预处理后如图3（a）所示。依据式（10）计算R*并以此旋转T2，得到的轨迹如图3（b）所示。无论采用何种已有的距离度量[3，6-8]，相比于图3（a），在旋转不变的意义下，图3（b）所示的两条对齐轨迹间的距离总是能够更好地刻画T1与T2的相似程度。2.5相似度计算参照图1流程，轨迹T1与T2旋转对齐后，即可利用DTW、LCSS等距离来衡量两者的相似程度，根据本节所采用的度量方法的差异，总体的RST不变性度量分别用MDTW、MLCSS、MED等表示。不失一般性，本文默认基于MDTW来表征轨迹相似程度。2.6小结综上所述，以MDTW为例，将本文算法的计算过程汇总如下所示。其中，FIX_LEN表示轨迹重采样后的点数，一般可简单设为固定值，如60。01Procedured=RST_INV_DIST（T1，T2）02P′1=Preprocess（T1,FIX_LEN）03P'2=Preprocess（T2,FIX_LEN）04R*=VUTs.t.P′2P′T1=UΣVT05d=DTW（P′1,R*P′2）06ProcedureP=Preprocess（T,FIX_LEN）07FOREACHpiINT08p′i=()pi-μp/μr09ENDFOR10T′={}p′1,p′2,…11T″=Resample（T′,FIX_LEN）12P=(