基于最長軌跡投影的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空間手寫字符識別提供較好的維數約簡處理方案。