張 鈺， 李瑞梅， 章 田

(杭州電子科技大學(xué) 電子信息學(xué)院，國家級電工電子實(shí)驗(yàn)教學(xué)示范中心，杭州 310018)

0 引 言

在機(jī)器學(xué)習(xí)[1]、圖像分類[2]、圖像處理[3]和模式識別[4-5]等應(yīng)用中，原始數(shù)據(jù)的維數(shù)如高于2維，存儲(chǔ)和計(jì)算成本較高，這就是所謂的“維數(shù)詛咒”。多維數(shù)據(jù)維數(shù)約簡是解決這個(gè)問題的有效途徑[6-10]。

為盡可能多地保留原始數(shù)據(jù)信息，基于主成分分析(Principal Component Analysis，PCA)的維數(shù)約簡方法[6]通過線性變換將高維數(shù)據(jù)映射到低維空間中表示，將方差最大的低維空間作為投影空間。然而，這種維數(shù)約簡方法處理后的圖像方向是隨機(jī)的，需要進(jìn)行方向調(diào)整才能保證較高的識別率。文獻(xiàn)[7]中提出了基于線性判別分析(Linear Discriminant Analysis，LDA)的維數(shù)約簡方法,其基本思想是將高維的模式樣本投影到最佳鑒別矢量空間，以達(dá)到抽取分類信息和壓縮特征空間維數(shù)的效果，投影后保證模式樣本在新的子空間有最大的類間距離和最小的類內(nèi)距離，即模式在該空間中有最佳的可分離性。與基于PCA的維數(shù)約簡方法盡量多保留原始數(shù)據(jù)不同，基于LDA的維數(shù)約簡方法是為數(shù)據(jù)分類服務(wù)的，最多只能將原始數(shù)據(jù)投影在C-1維度上[8](C是類的數(shù)量)。文獻(xiàn)[9]中基于局部線性嵌入(Locally Linear Embedding，LLE)的維數(shù)約簡方法能夠使得維數(shù)約簡之后的數(shù)據(jù)較好地保留原始數(shù)據(jù)的局部幾何結(jié)構(gòu)關(guān)系，卻不能保留原始數(shù)據(jù)的全局結(jié)構(gòu)信息。文獻(xiàn)[10]中提出基于局部保留投影(Locality Preserving Projections，LPP)的維數(shù)約簡方法，通過構(gòu)建空間中各樣本對之間的遠(yuǎn)近親疏關(guān)系，并在投影中保持這種關(guān)系，能在維數(shù)約簡的同時(shí)保留空間樣本的局部鄰域結(jié)構(gòu)。與基于LLE的維數(shù)約簡方法類似，基于LPP的維數(shù)約簡方法不能保留原始數(shù)據(jù)的全局結(jié)構(gòu)。

本文提出一種新的基于最長軌跡投影的維數(shù)約簡算法，維數(shù)約簡后的數(shù)據(jù)不僅保留了原始數(shù)據(jù)的全局結(jié)構(gòu)信息，而且具有固定的方向，提高了3D空間手寫字符的識別率。

1 基于最長軌跡投影的維數(shù)約簡方法

算法的流程圖如圖1所示。首先將手放到Leap Motion[11]的有效區(qū)域進(jìn)行手寫字符輸入；然后，獲取運(yùn)動(dòng)指尖的3D坐標(biāo)，并依次連接指尖的3D坐標(biāo)點(diǎn)生成3D運(yùn)動(dòng)軌跡；接下來，將3D軌跡上所有的點(diǎn)投影到XOY，XOZ，YOZ標(biāo)準(zhǔn)平面，并依次連接每個(gè)平面上的投影點(diǎn)形成2D軌跡；最后，分別計(jì)算3個(gè)平面內(nèi)的2D軌跡上相鄰點(diǎn)的長度和，選擇長度和最大的平面作為最佳投影平面。

圖1 基于最長軌跡投影的維數(shù)約簡算法流程圖

1.1 3D軌跡生成

Leap Motion控制器以超過200幀/s的速度追蹤全部手指的移動(dòng)，提供空間運(yùn)動(dòng)指尖的3D坐標(biāo)，精度高達(dá)1/100 mm[12]。利用Leap Motion獲取運(yùn)動(dòng)指尖在空間中的3D坐標(biāo)，3D坐標(biāo)用Ai(x,y,z)表示，i=1,2,…,n，n為Leap Motion獲取的指尖在空間中運(yùn)動(dòng)點(diǎn)。

獲取運(yùn)動(dòng)指尖的3D坐標(biāo)后，依次連接指尖的3D坐標(biāo)點(diǎn)生成線段AiAi+1(i=1,2,…,n-1),得到指尖的3D運(yùn)動(dòng)軌跡。

1.2 形成2D投影軌跡

基于Leap Motion體感控制器內(nèi)建的三維空間直角坐標(biāo)系統(tǒng)，分別把三維坐標(biāo)Ai(x,y,z)投影到3個(gè)標(biāo)準(zhǔn)的平面XOY、XOZ、YOZ上。在XOY平面上，投影之后的點(diǎn)用Bi(x,y)表示；在XOZ平面上，投影之后的點(diǎn)用Ci(x,z)表示；在YOZ平面上，投影之后的點(diǎn)用Di(y,z)表示，i=1,2,…,n。并依次連接每個(gè)平面上的投影點(diǎn)，從而生成3條2D投影軌跡。

1.3 最佳投影平面選取

分別計(jì)算3條2D投影軌跡的長度，并選擇最長投影軌跡所在的平面為最佳投影平面。2D投影軌跡長度的計(jì)算有3種情況。

(1) 一般情況下，2D軌跡的長度近似等于由相鄰點(diǎn)組成的線段的長度和，如圖2所示。Bi表示2D軌跡上的點(diǎn)，i=1,2,…,5;虛線表示2D投影軌跡;實(shí)線表示2D投影軌跡的近似長度，用L表示：

(1)

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

圖2 2D軌跡上點(diǎn)的一般分布

(2) 如果2D軌跡上的相鄰點(diǎn)重合，那么相鄰點(diǎn)組成的線段長度為0。

(3) 2D軌跡上重合部分的長度只計(jì)算1次。在圖3中，虛線表示2D投影軌跡,Bi表示2D投影軌跡上的點(diǎn),i=1,2,3。B1和B2所在的直線方程由L1表示。通過將B3的坐標(biāo)點(diǎn)代入直線方程L1中，可以得到B3是L1上的點(diǎn)。那么B1和B2所在的直線與B2和B3所在的直線有重合的部分，2D軌跡的長度,

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

圖3 2D軌跡上點(diǎn)的特殊分布

根據(jù)2D軌跡上點(diǎn)的分布情況計(jì)算投影軌跡的長度，擁有最長投影軌跡的平面即為最佳投影平面。2D投影軌跡的長度最大與3D軌跡的長度相等。

2 最長軌跡投影的理論證明

3D軌跡上點(diǎn)的分布有兩種情況：①3個(gè)點(diǎn)在1條直線上;②3個(gè)點(diǎn)不在1條直線上。

2.1 3D軌跡上的點(diǎn)位于同1條直線

當(dāng)3個(gè)點(diǎn)在1條直線上時(shí)，3D軌跡以及其投影如圖4所示。A、B、C表示3D軌跡上的點(diǎn)；A′、A″、A?分別代表點(diǎn)A在XOY、XOZ、YOZ平面上的投影點(diǎn)；B′、B″、B?分別代表點(diǎn)B在XOY、XOZ、YOZ平面上的投影點(diǎn)；C′、C″、C?分別代表點(diǎn)C在XOY、XOZ、YOZ平面上的投影點(diǎn)。

圖4 3D軌跡以及其投影

Lk=Licosθ

(2)

式中:Li表示3D軌跡i的長度;Lk表示2D投影軌跡k的長度;θ表示Li和Lk之間的角度

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

角度之間的關(guān)系如下：

(3)

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

(4)

圖5 3D軌跡以及其在XOY平面上的投影

從上述分析可以得出以下結(jié)論：在3個(gè)點(diǎn)位于1條直線的前提下，當(dāng)3D軌跡上的線段與XOY平面的夾角越小時(shí)，2D投影軌跡的長度就越大，就越接近于3D軌跡的長度，那么3D軌跡與2D投影軌跡的形狀就越相似，所代表的3D軌跡的信息就越多。當(dāng)2D投影軌跡的長度與3D軌跡的長度相等時(shí)，2D投影軌跡可以最大程度地反映3D軌跡的信息。

2.2 3D軌跡上的點(diǎn)不在同1條直線

當(dāng)3D軌跡上的3個(gè)點(diǎn)不在同1條直線上時(shí)，具體情況如圖6所示。A、B、C表示3D軌跡上的點(diǎn)，A′、B′、C′分別代表點(diǎn)A、B、C在XOY平面上的投影點(diǎn)；A″、B″、C″分別代表點(diǎn)A、B、C在XOZ平面上的投影點(diǎn)；A?、B?、C?分別代表點(diǎn)A、B、C在YOZ平面上的投影點(diǎn)。

圖6 3D軌跡以及其投影

可以從兩個(gè)方面來證明最長軌跡投影算法的可行性與合理性。

(1) 從2D投影軌跡的長度出發(fā)，進(jìn)行理論證明。在XOY平面上，以3D軌跡上的線段與XOY平面的夾角發(fā)生變化時(shí),2D投影軌跡的長度變化情況來代表3個(gè)平面上的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)

從上述分析可以得出以下結(jié)論：在3個(gè)點(diǎn)不在1條直線上的前提下，當(dāng)3D軌跡上的線段與XOY平面的夾角越小時(shí)，其對應(yīng)的2D投影軌跡的長度就越大，就越接近于3D軌跡的長度，所代表的3D軌跡的信息就越多。當(dāng)2D投影軌跡的長度與3D軌跡的長度相等時(shí)，2D投影軌跡可以最大程度地反映3D軌跡的信息。

(8)

圖8 3D軌跡在XOY平面上的投影

假設(shè)∠B′AC等于∠B′CA，式(8)簡化為以下公式：

(9)

根據(jù)三角形角度公式：

(10)

(11)

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

(12)

綜上所述：2D投影軌跡的長度越長，越接近于3D軌跡的長度，3D軌跡的形狀與2D軌跡的形狀就會(huì)越相似，并且可以反映更多的原始軌跡信息。當(dāng)2D投影軌跡的長度與3D軌跡的長度相等時(shí)，它可以最大程度地反映3D軌跡的信息。因此，當(dāng)3D軌跡選擇投影平面時(shí)，要選擇具有最長投影軌跡的平面作為最佳投影平面。

2.3 3D軌跡上分布多個(gè)點(diǎn)

基于上述分析，當(dāng)3D軌跡上有多個(gè)點(diǎn)時(shí)，3D軌跡在一個(gè)平面的投影情況如圖9所示。圖中Ai表示3D軌跡上的點(diǎn);Bi表示2D軌跡上的點(diǎn)。假設(shè)2D投影軌跡上沒有重合的線段，2D投影軌跡的長度計(jì)算如下：

(13)

式中:L表示2D投影軌跡的長度;Bi表示2D投影軌跡上的點(diǎn)，i=1,2,…,n-1。然后比較3個(gè)平面上的投影長度，將2D軌跡最長的平面定義為3D軌跡的最佳投影平面。

圖9 3D軌跡及其在一個(gè)平面上的投影

3 仿真實(shí)驗(yàn)

為了驗(yàn)證所提算法的視覺處理效果，本文分別在數(shù)字?jǐn)?shù)據(jù)庫和小寫字母數(shù)據(jù)庫中對3D字符軌跡進(jìn)行處理[13]。數(shù)字?jǐn)?shù)據(jù)庫和小寫字母數(shù)據(jù)庫中的數(shù)據(jù)是從5名實(shí)驗(yàn)者收集來的，每名實(shí)驗(yàn)者會(huì)把每個(gè)符號(0～9和a～z)記錄50次。

首先，從數(shù)字?jǐn)?shù)據(jù)庫中選取10組不同字符軌跡數(shù)據(jù)，分別使用本文提出的維數(shù)約簡算法和基于PCA的維數(shù)約簡算法對數(shù)據(jù)進(jìn)行維數(shù)約簡[14]，不同方法處理后的圖像如圖10所示。圖10(a)為Leap Motion提取的3D坐標(biāo)連接得到的3D空間手寫數(shù)字軌跡，分別為數(shù)字0～9；圖10(b)為通過基于PCA的維數(shù)約簡算法處理得到2D投影圖像；圖10(c)為通過基于最長軌跡投影的維數(shù)約簡算法處理得到2D圖像；圖10(b)和(c)中的每張圖像與圖10(a)中的字符是一一對應(yīng)的。

(b) 基于PCA的維數(shù)約簡算法處理后圖像

(c) 所提維數(shù)約簡算法處理后的圖像

圖10 不同算法處理結(jié)果對比

然后在小寫字母數(shù)據(jù)庫中選取26組不同字符軌跡的數(shù)據(jù)，分別使用基于PCA的維數(shù)約簡方法和本文提出的維數(shù)約簡方法對數(shù)據(jù)進(jìn)行維數(shù)約簡，不同方法處理后的圖像如圖11所示。圖11(a)為3D空間手寫字符軌跡，分別為小寫字母a～z；圖11(b)為通過基于PCA的維數(shù)約簡算法處理得到的2D圖像；圖11(c)為通過本文提出的維數(shù)約簡算法處理得到的2D圖像。

最后，使用基于PCA的維數(shù)約簡算法對多個(gè)3D空間手寫數(shù)字“3”和小寫字母“a”進(jìn)行維數(shù)約簡，處理結(jié)果如圖12所示。顯然，基于PCA的維數(shù)約簡算法處理后的2D字符圖像方向是隨機(jī)的。

(a) 3D空中手寫字符軌跡“3”和“a”

從以上分析可以看出，基于PCA的維數(shù)約簡算法處理后的2D字符圖像方向是隨機(jī)的，而所提算法得到的2D字符投影軌跡，有一個(gè)明確的方向和比較穩(wěn)定的結(jié)果。

為了進(jìn)一步對實(shí)驗(yàn)結(jié)果進(jìn)行驗(yàn)證，使用基于SVM[15-16]的手寫字符識別方法對兩種維數(shù)約簡方法得到的圖像進(jìn)行識別。在3D空間手寫字符識別中，數(shù)字?jǐn)?shù)據(jù)庫中有2 500個(gè)樣本，小寫字母數(shù)據(jù)庫有6 500個(gè)樣本，其中數(shù)據(jù)樣本的25%用于測試，75%用于訓(xùn)練。然后計(jì)算數(shù)字?jǐn)?shù)據(jù)庫中單個(gè)字符的平均識別率和所有字符的平均識別率、小寫字母數(shù)據(jù)庫中單個(gè)字符的平均識別率和所有字符的平均識別率。

單個(gè)字符的平均識別率表示為單個(gè)字符識別正確的數(shù)目與單個(gè)字符的總和的比值，即

P1=n1/N1

(14)

式中:P1即單個(gè)字符的識別率;n1表示單個(gè)字符識別正確的數(shù)目;N1表示單個(gè)字符的所有數(shù)目

所有字符的平均識別率表示的是所有字符中識別正確的數(shù)目與所有字符的總和的比值，即

P2=n2/N2

(15)

式中:P2即數(shù)據(jù)庫中所有字符的識別率;n2表示數(shù)據(jù)庫中識別正確的字符數(shù)目;N2表示數(shù)據(jù)庫中所有字符的數(shù)目。

針對數(shù)字?jǐn)?shù)據(jù)庫和小寫字母數(shù)據(jù)庫中的所有樣本，不同維數(shù)約簡算法處理后的單個(gè)字符和所有字符的平均識別率如表1所示。從表1可以看出，所提維數(shù)約簡算法得到的單個(gè)字符的平均識別率都大于或者等于基于PCA的維數(shù)約簡算法得到的單個(gè)字符的平均識別率；而所有數(shù)字的平均識別率和所有字母的平均識別率分別為96.2%和92.3%，這明顯高于基于PCA的維數(shù)約簡得到的所有數(shù)字的平均識別率和所有字母的平均識別率。

所以，綜上分析可以看出：所提算法可以得到固定方向的2D圖像，不需要方向調(diào)整算法，就能夠使3D空間手寫字符的平均識別率達(dá)到96.2%。

表1 不同算法處理后的單個(gè)字符和所有字符的平均識別率

4 結(jié) 語

本文提出了一種基于最長軌跡投影的3D空間手寫字符維數(shù)約簡方法。首先，獲取運(yùn)動(dòng)指尖的3D坐標(biāo)，依次連接指尖的3D坐標(biāo)點(diǎn)生成3D運(yùn)動(dòng)軌跡；然后，將3D軌跡上所有的點(diǎn)投影到XOY，XOZ，YOZ標(biāo)準(zhǔn)平面上，并依次連接每個(gè)平面上的投影點(diǎn)形成2D軌跡；最后，分別計(jì)算3個(gè)平面內(nèi)的2D軌跡上相鄰點(diǎn)形成的線段的長度和，選擇長度和最大的平面作為最佳投影平面。與現(xiàn)有保持全局結(jié)構(gòu)的維數(shù)約簡算法相比，所提算法可以得到固定方向的2D圖像，不需要方向調(diào)整算法，就能夠使3D空間手寫字符的識別率達(dá)到96.2%。所提維數(shù)約簡算法可為3D空間手寫字符識別提供較好的維數(shù)約簡處理方案。