基于最长轨迹投影的3D空间手写字符维数约简

张 钰， 李瑞梅， 章 田

(杭州电子科技大学 电子信息学院，国家级电工电子实验教学示范中心，杭州 310018)

0 引 言

在机器学习[1]、图像分类[2]、图像处理[3]和模式识别[4-5]等应用中，原始数据的维数如高于2维，存储和计算成本较高，这就是所谓的“维数诅咒”。多维数据维数约简是解决这个问题的有效途径[6-10]。

为尽可能多地保留原始数据信息，基于主成分分析(Principal Component Analysis，PCA)的维数约简方法[6]通过线性变换将高维数据映射到低维空间中表示，将方差最大的低维空间作为投影空间。然而，这种维数约简方法处理后的图像方向是随机的，需要进行方向调整才能保证较高的识别率。文献[7]中提出了基于线性判别分析(Linear Discriminant Analysis，LDA)的维数约简方法,其基本思想是将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性。与基于PCA的维数约简方法尽量多保留原始数据不同，基于LDA的维数约简方法是为数据分类服务的，最多只能将原始数据投影在C-1维度上[8](C是类的数量)。文献[9]中基于局部线性嵌入(Locally Linear Embedding，LLE)的维数约简方法能够使得维数约简之后的数据较好地保留原始数据的局部几何结构关系，却不能保留原始数据的全局结构信息。文献[10]中提出基于局部保留投影(Locality Preserving Projections，LPP)的维数约简方法，通过构建空间中各样本对之间的远近亲疏关系，并在投影中保持这种关系，能在维数约简的同时保留空间样本的局部邻域结构。与基于LLE的维数约简方法类似，基于LPP的维数约简方法不能保留原始数据的全局结构。

本文提出一种新的基于最长轨迹投影的维数约简算法，维数约简后的数据不仅保留了原始数据的全局结构信息，而且具有固定的方向，提高了3D空间手写字符的识别率。

1 基于最长轨迹投影的维数约简方法

算法的流程图如图1所示。首先将手放到Leap Motion[11]的有效区域进行手写字符输入；然后，获取运动指尖的3D坐标，并依次连接指尖的3D坐标点生成3D运动轨迹；接下来，将3D轨迹上所有的点投影到XOY，XOZ，YOZ标准平面，并依次连接每个平面上的投影点形成2D轨迹；最后，分别计算3个平面内的2D轨迹上相邻点的长度和，选择长度和最大的平面作为最佳投影平面。

图1 基于最长轨迹投影的维数约简算法流程图

1.1 3D轨迹生成

Leap Motion控制器以超过200帧/s的速度追踪全部手指的移动，提供空间运动指尖的3D坐标，精度高达1/100 mm[12]。利用Leap Motion获取运动指尖在空间中的3D坐标，3D坐标用Ai(x,y,z)表示，i=1,2,…,n，n为Leap Motion获取的指尖在空间中运动点。

获取运动指尖的3D坐标后，依次连接指尖的3D坐标点生成线段AiAi+1(i=1,2,…,n-1),得到指尖的3D运动轨迹。

1.2 形成2D投影轨迹

基于Leap Motion体感控制器内建的三维空间直角坐标系统，分别把三维坐标Ai(x,y,z)投影到3个标准的平面XOY、XOZ、YOZ上。在XOY平面上，投影之后的点用Bi(x,y)表示；在XOZ平面上，投影之后的点用Ci(x,z)表示；在YOZ平面上，投影之后的点用Di(y,z)表示，i=1,2,…,n。并依次连接每个平面上的投影点，从而生成3条2D投影轨迹。

1.3 最佳投影平面选取

分别计算3条2D投影轨迹的长度，并选择最长投影轨迹所在的平面为最佳投影平面。2D投影轨迹长度的计算有3种情况。

(1) 一般情况下，2D轨迹的长度近似等于由相邻点组成的线段的长度和，如图2所示。Bi表示2D轨迹上的点，i=1,2,…,5;虚线表示2D投影轨迹;实线表示2D投影轨迹的近似长度，用L表示：

(1)

式中:|BiBi+1|表示线段BiBi+1的长度，i=1,2,3,4。

图2 2D轨迹上点的一般分布

(2) 如果2D轨迹上的相邻点重合，那么相邻点组成的线段长度为0。

(3) 2D轨迹上重合部分的长度只计算1次。在图3中，虚线表示2D投影轨迹,Bi表示2D投影轨迹上的点,i=1,2,3。B1和B2所在的直线方程由L1表示。通过将B3的坐标点代入直线方程L1中，可以得到B3是L1上的点。那么B1和B2所在的直线与B2和B3所在的直线有重合的部分，2D轨迹的长度,

L=|B1B2|+|B2B3|=|B1B2|

图3 2D轨迹上点的特殊分布

根据2D轨迹上点的分布情况计算投影轨迹的长度，拥有最长投影轨迹的平面即为最佳投影平面。2D投影轨迹的长度最大与3D轨迹的长度相等。

2 最长轨迹投影的理论证明

3D轨迹上点的分布有两种情况：①3个点在1条直线上;②3个点不在1条直线上。

2.1 3D轨迹上的点位于同1条直线

当3个点在1条直线上时，3D轨迹以及其投影如图4所示。A、B、C表示3D轨迹上的点；A′、A″、A‴分别代表点A在XOY、XOZ、YOZ平面上的投影点；B′、B″、B‴分别代表点B在XOY、XOZ、YOZ平面上的投影点；C′、C″、C‴分别代表点C在XOY、XOZ、YOZ平面上的投影点。

图4 3D轨迹以及其投影

Lk=Licosθ

(2)

式中:Li表示3D轨迹i的长度;Lk表示2D投影轨迹k的长度;θ表示Li和Lk之间的角度

(i,θ,k)∈((AC,∠CAC′,AC′),

角度之间的关系如下：

(3)

从式(2)、(3)可得：

(4)

图5 3D轨迹以及其在XOY平面上的投影

从上述分析可以得出以下结论：在3个点位于1条直线的前提下，当3D轨迹上的线段与XOY平面的夹角越小时，2D投影轨迹的长度就越大，就越接近于3D轨迹的长度，那么3D轨迹与2D投影轨迹的形状就越相似，所代表的3D轨迹的信息就越多。当2D投影轨迹的长度与3D轨迹的长度相等时，2D投影轨迹可以最大程度地反映3D轨迹的信息。

2.2 3D轨迹上的点不在同1条直线

当3D轨迹上的3个点不在同1条直线上时，具体情况如图6所示。A、B、C表示3D轨迹上的点，A′、B′、C′分别代表点A、B、C在XOY平面上的投影点；A″、B″、C″分别代表点A、B、C在XOZ平面上的投影点；A‴、B‴、C‴分别代表点A、B、C在YOZ平面上的投影点。

图6 3D轨迹以及其投影

可以从两个方面来证明最长轨迹投影算法的可行性与合理性。

(1) 从2D投影轨迹的长度出发，进行理论证明。在XOY平面上，以3D轨迹上的线段与XOY平面的夹角发生变化时,2D投影轨迹的长度变化情况来代表3个平面上的2D投影轨迹的长度变化情况，如图7所示。

图7 3D轨迹以及其在XOY平面上的投影

Lt=Lmcosθ

(5)

式中:Lm表示3D轨迹上线段m的长度;Lt表示2D平面上投影线段t的长度;θ表示Lm和Lt之间的夹角

(m,θ,t)∈((AB,∠BAB′,AB′),

夹角之间的大小比较如下：

(6)

由式(5)、(6)可得：

(7)

从上述分析可以得出以下结论：在3个点不在1条直线上的前提下，当3D轨迹上的线段与XOY平面的夹角越小时，其对应的2D投影轨迹的长度就越大，就越接近于3D轨迹的长度，所代表的3D轨迹的信息就越多。当2D投影轨迹的长度与3D轨迹的长度相等时，2D投影轨迹可以最大程度地反映3D轨迹的信息。

(8)

图8 3D轨迹在XOY平面上的投影

假设∠B′AC等于∠B′CA，式(8)简化为以下公式：

(9)

根据三角形角度公式：

(10)

(11)

将式(10)、(11)代入式(9)，可得

(12)

综上所述：2D投影轨迹的长度越长，越接近于3D轨迹的长度，3D轨迹的形状与2D轨迹的形状就会越相似，并且可以反映更多的原始轨迹信息。当2D投影轨迹的长度与3D轨迹的长度相等时，它可以最大程度地反映3D轨迹的信息。因此，当3D轨迹选择投影平面时，要选择具有最长投影轨迹的平面作为最佳投影平面。

2.3 3D轨迹上分布多个点

基于上述分析，当3D轨迹上有多个点时，3D轨迹在一个平面的投影情况如图9所示。图中Ai表示3D轨迹上的点;Bi表示2D轨迹上的点。假设2D投影轨迹上没有重合的线段，2D投影轨迹的长度计算如下：

(13)

式中:L表示2D投影轨迹的长度;Bi表示2D投影轨迹上的点，i=1,2,…,n-1。然后比较3个平面上的投影长度，将2D轨迹最长的平面定义为3D轨迹的最佳投影平面。

图9 3D轨迹及其在一个平面上的投影

3 仿真实验

为了验证所提算法的视觉处理效果，本文分别在数字数据库和小写字母数据库中对3D字符轨迹进行处理[13]。数字数据库和小写字母数据库中的数据是从5名实验者收集来的，每名实验者会把每个符号(0～9和a～z)记录50次。

首先，从数字数据库中选取10组不同字符轨迹数据，分别使用本文提出的维数约简算法和基于PCA的维数约简算法对数据进行维数约简[14]，不同方法处理后的图像如图10所示。图10(a)为Leap Motion提取的3D坐标连接得到的3D空间手写数字轨迹，分别为数字0～9；图10(b)为通过基于PCA的维数约简算法处理得到2D投影图像；图10(c)为通过基于最长轨迹投影的维数约简算法处理得到2D图像；图10(b)和(c)中的每张图像与图10(a)中的字符是一一对应的。

(b) 基于PCA的维数约简算法处理后图像

(c) 所提维数约简算法处理后的图像

图10 不同算法处理结果对比

然后在小写字母数据库中选取26组不同字符轨迹的数据，分别使用基于PCA的维数约简方法和本文提出的维数约简方法对数据进行维数约简，不同方法处理后的图像如图11所示。图11(a)为3D空间手写字符轨迹，分别为小写字母a～z；图11(b)为通过基于PCA的维数约简算法处理得到的2D图像；图11(c)为通过本文提出的维数约简算法处理得到的2D图像。

最后，使用基于PCA的维数约简算法对多个3D空间手写数字“3”和小写字母“a”进行维数约简，处理结果如图12所示。显然，基于PCA的维数约简算法处理后的2D字符图像方向是随机的。

(a) 3D空中手写字符轨迹“3”和“a”

从以上分析可以看出，基于PCA的维数约简算法处理后的2D字符图像方向是随机的，而所提算法得到的2D字符投影轨迹，有一个明确的方向和比较稳定的结果。

为了进一步对实验结果进行验证，使用基于SVM[15-16]的手写字符识别方法对两种维数约简方法得到的图像进行识别。在3D空间手写字符识别中，数字数据库中有2 500个样本，小写字母数据库有6 500个样本，其中数据样本的25%用于测试，75%用于训练。然后计算数字数据库中单个字符的平均识别率和所有字符的平均识别率、小写字母数据库中单个字符的平均识别率和所有字符的平均识别率。

单个字符的平均识别率表示为单个字符识别正确的数目与单个字符的总和的比值，即

P1=n1/N1

(14)

式中:P1即单个字符的识别率;n1表示单个字符识别正确的数目;N1表示单个字符的所有数目

所有字符的平均识别率表示的是所有字符中识别正确的数目与所有字符的总和的比值，即

P2=n2/N2

(15)

式中:P2即数据库中所有字符的识别率;n2表示数据库中识别正确的字符数目;N2表示数据库中所有字符的数目。

针对数字数据库和小写字母数据库中的所有样本，不同维数约简算法处理后的单个字符和所有字符的平均识别率如表1所示。从表1可以看出，所提维数约简算法得到的单个字符的平均识别率都大于或者等于基于PCA的维数约简算法得到的单个字符的平均识别率；而所有数字的平均识别率和所有字母的平均识别率分别为96.2%和92.3%，这明显高于基于PCA的维数约简得到的所有数字的平均识别率和所有字母的平均识别率。

所以，综上分析可以看出：所提算法可以得到固定方向的2D图像，不需要方向调整算法，就能够使3D空间手写字符的平均识别率达到96.2%。

表1 不同算法处理后的单个字符和所有字符的平均识别率

4 结 语

本文提出了一种基于最长轨迹投影的3D空间手写字符维数约简方法。首先，获取运动指尖的3D坐标，依次连接指尖的3D坐标点生成3D运动轨迹；然后，将3D轨迹上所有的点投影到XOY，XOZ，YOZ标准平面上，并依次连接每个平面上的投影点形成2D轨迹；最后，分别计算3个平面内的2D轨迹上相邻点形成的线段的长度和，选择长度和最大的平面作为最佳投影平面。与现有保持全局结构的维数约简算法相比，所提算法可以得到固定方向的2D图像，不需要方向调整算法，就能够使3D空间手写字符的识别率达到96.2%。所提维数约简算法可为3D空间手写字符识别提供较好的维数约简处理方案。