基于正交匹配追蹤及加速近端梯度的人體三維重建

汪亞明 翟俊鵬 莫 燕 韓永華 蔣明峰

(浙江理工大學信號與信息處理研究所，杭州 310018)

基于正交匹配追蹤及加速近端梯度的人體三維重建

汪亞明 翟俊鵬 莫 燕*韓永華 蔣明峰

(浙江理工大學信號與信息處理研究所，杭州 310018)

為提高人體三維結構的重建精度，針對重建過程中字典中原子的最佳選擇和結構矩陣的優(yōu)化問題，結合稀疏表示和低秩約束，提出一種正交匹配追蹤追蹤及加速近端梯度(OMP-APG)算法，以此為醫(yī)學領域提供豐富的信息，以輔助醫(yī)生快速精確地制定出治療方案。首先，對特征點觀測矩陣進行奇異值分解(SVD)分解，利用列文伯格-馬夸爾特(LM)算法得到唯一確定的相機旋轉(zhuǎn)矩陣；其次，利用稀疏表示中“最大化逼近”思想，通過正交匹配追蹤算法對軌跡基系數(shù)進行求解，結合預定義的軌跡基求解出人體三維結構矩陣；最后，根據(jù)結構矩陣是一個低秩矩陣，將其秩優(yōu)化問題轉(zhuǎn)化為核范數(shù)最小化問題，利用加速近端梯度算法對人體結構矩陣進一步優(yōu)化處理。將該算法與稀疏逼近算法進行比較，對伸懶腰、瑜伽、拾物、喝水和跳舞等5組不同的人體運動模型進行三維重建，通過其三維重建效果圖和三維重建誤差的結果顯示，其重建精度更高且穩(wěn)定性更好。在該算法下喝水運動的重建效果最佳，其1 102幀圖像序列41個特征點的重建誤差為0.030 3，而在稀疏算法下的重建誤差為0.017 8。因此，該算法可以有效地提高人體三維結構的重建精度，為醫(yī)學領域輔助治療提供相應的技術支持。

三維重建；人體運動重建；稀疏表示；加速近端梯度

引言

利用二維圖像序列來恢復人體三維結構成為近幾年的研究熱點，即尋找合適的算法從已知的二維序列觀測點中恢復人體的三維結構[1-2]。在先前的研究中，Tomasz和Kanata提出利用觀測矩陣的秩約束對觀測矩陣進行因式分解(SVD分解)[3]，即在正交投影模型下結合觀測矩陣的秩約束條件，對其進行SVD分解，利用非線性優(yōu)化迭代方法求解矯正矩陣，進而恢復出目標物體的三維結構矩陣和相機旋轉(zhuǎn)矩陣。隨著研究的不斷深入，Bregler 等人將SVD分解拓展到非剛性的三維重建上，提出形狀基模型理論[4]。通過預定義形狀基的線性組合來恢復非剛性運動的結構矩陣，從而將求解問題轉(zhuǎn)化為求解形狀基線性組合系數(shù)的問題。Akhter等人對形狀基和形狀空間進行了研究和擴展，結合非剛性運動的連續(xù)性和平滑特性，提出軌跡基模型[5]。同時，他們也對形狀基和軌跡基之間存在的對偶性進行了論證，即形狀基、形狀基系數(shù)和軌跡基、軌跡基系數(shù)之間可以交換，其中形狀基對應軌跡基系數(shù)，形狀基系數(shù)與軌跡基相對應。人體三維重建從形狀基到軌跡基的轉(zhuǎn)變使得其研究更加進步。近期研究中，將信號恢復領域中稀疏思想[6-7]應用于三維重建，即利用稀疏思想來稀疏化表示軌跡基系數(shù)矩陣，然后再尋找一種求解稀疏度函數(shù)的算法來求解得到精確的軌跡基系數(shù)，從而提高三維結構矩陣的重建精度。但仍有不足之處，存在軌跡基中最優(yōu)原子的選擇問題和結構矩陣的優(yōu)化問題，即盡量選擇最佳的原子組合來表示軌跡曲線，以及進一步優(yōu)化結構矩陣。本研究中所提及的OMP-APG算法，解決了軌跡基中原子的最佳選擇和結構矩陣的最優(yōu)恢復問題。

由于人體運動表現(xiàn)出非剛性，因此本研究是在軌跡空間[8-9]中展開研究的。首先，利用稀疏表示思想來稀疏化系數(shù)矩陣來降低大矩陣的求解難度。根據(jù)正交匹配算法(OMP)對軌跡基的系數(shù)進行求解，然后結合預先定義原子字典恢復出人體運動三維結構矩陣。求解得到的三維人體結構矩陣是一個低秩矩陣，由于秩函數(shù)穩(wěn)定性不好，將其轉(zhuǎn)化為秩的最小化問題。通常情況下，秩的最小化求解問題是一個NP難問題，因此將其放寬為核范數(shù)的最小化求解問題，可采用加速近端梯度算法來求解核范數(shù)最小化的問題，就是用正交匹配追蹤算法求得的三維結構矩陣作為APG算法的迭代初值進行優(yōu)化，經(jīng)過迭代重建出精度更高的三維人體結構。

1 方法

1.1 人體三維重建結構

假設M表示人體運動圖像的幀數(shù)，N代表每幀圖像中人體上所取得的特征點數(shù)，則二維觀測矩陣W可以表示為維數(shù)為2M×N的矩陣，形式如下：

(1)

式中：W矩陣是二維觀測矩陣，是一個2M×N的矩陣；uij代表第i幀第j個點二維序列中的x坐標，vij代表第i幀第j個點二維序列中的y坐標。

根據(jù)因式分解理論以及軌跡基理論模型可以將人體重建的結構矩陣[10-11]表示為

(2)

式中，R是相機的旋轉(zhuǎn)矩陣，Θ是預定義的原子字典，A是軌跡基系數(shù)，K表示軌跡線性組合個數(shù)。

結合SVD分解以及式(2)，可以得到人體三維結構矩陣的表達式為

(3)

式中，S代表人體運動的三維結構矩陣，K表示線性組合的軌跡基個數(shù)，Θ是經(jīng)過函數(shù)變換得到的基，A表示對應的軌跡基系數(shù)。

1.2 OMP-APG算法

1.2.1 正交匹配追蹤算法

稀疏表示[12]這一概念源自信號與系統(tǒng)領域，從一個給定的過完備集合中自適應的選出若干原子對原始信號進行逼近。根據(jù)稀疏定義和表示理論，可以列出稀疏表示的優(yōu)化問題如下：

(4)

式中，f是任意信號，D是用于稀疏分解的過完備字典，范數(shù)‖c‖0定義為向量c中非零的個數(shù)。

由于l0范數(shù)是非凸范數(shù)，上述求解過程一個NP問題，故將優(yōu)化問題轉(zhuǎn)化為某種稀疏度函數(shù)進行求解。在信號系統(tǒng)領域稀疏表示的算法很多，如基追蹤算法、正交匹配追蹤算法、FOCUSS算法等。正交匹配追蹤算法的優(yōu)化問題是通過貪婪算法轉(zhuǎn)化為求單個有限項的逼近問題。

(5)

(6)

有關定理[14]證明，正交匹配算法可以使逼近誤差在有限迭代次數(shù)內(nèi)(小于等于H空間的維數(shù))衰減到零，而基本的匹配追蹤算法不能保證這一點。

1.2.2 系數(shù)求解

對人體三維運動重建，需要首先確定相機旋轉(zhuǎn)矩陣R[15]，才能進一步求解軌跡基系數(shù)。將W矩陣進行SVD分解，得到

(7)

因為一個非奇異Q矩陣的存在，使得式(7)分解出來不唯一的結果，即

(8)

式中，Λ=RΘ，A為軌跡基系數(shù)。

令Si=[Tx(i),Ty(i),Tz(i)],Si∈RM×3，表示在連續(xù)變化的M幀圖像中的第i個特征點的運動軌跡在x、y、z各個方向上的坐標，即重建物體結構矩陣S中第i個連續(xù)的3列，故有

[Tx(i),Ty(i),Tz(i)]=

(9)

式中，Tx(i)、Ty(i)、Tx(i)分別代表第i個特征點在X、Y、Z三個方向上的軌跡集合，θi代表由函數(shù)產(chǎn)生的軌跡基，αi代表對應的軌跡基系數(shù)。

式(9)也能寫成

(10)

結合式(2)中的W=RS和稀疏優(yōu)化表達式(4)以及稀疏度函數(shù)概念，可以將軌跡基系數(shù)求解的稀疏優(yōu)化問題轉(zhuǎn)化為求解l1范數(shù)[16]，即

(11)

式中：wi表示人體運動的第i個特征點在M幀序列圖像中的二維坐標，αi是相對應的軌跡基系數(shù)；Π=RΘ，其中R是相機的旋轉(zhuǎn)矩陣，Θ是預先定義的原子字典。

本研究采用DCT基作為原子字典，結合估計出旋轉(zhuǎn)矩陣R，利用正交匹配算法、根據(jù)式(11)求解出軌跡基系數(shù)A。該算法具體求解過程及算法步驟如文獻[17]所示。

1.2.3 結構優(yōu)化

基于正交追蹤算法求解出軌跡基系數(shù)之后，結合預定義的原子字典，利用(10)恢復出人體三維結構矩陣S。由于S矩陣是一個低秩矩陣，因此可以利用秩約束對其進行優(yōu)化求解。由于秩函數(shù)數(shù)值穩(wěn)定性不好，所以將其轉(zhuǎn)化成秩的最小化問題[18]，即

(12)

然而，秩的最小化求解通常是一個NP難問題。因此將秩的最小化放寬到核范數(shù)最小化，即min‖S‖*。再利用APG算法來求解核范數(shù)最小化問題[19]。將核范數(shù)優(yōu)化最小化問題寫成拉格朗日表示為

(13)

所以，式(13)可轉(zhuǎn)化為

(14)

將上面求得的人體三維結構矩陣作為APG算法[20-21]的迭代初值，進一步優(yōu)化得到高精度的人體三維結構矩陣。

1.3 算法步驟

如上所述，已知二維觀測矩陣W∈R2M×N，根據(jù)因式分解理論以及稀疏表示思想等基礎知識，整個人體三維重建過程以及算法步驟如下：

1)初始化。利用相機投影模型和真實三維結構矩陣初始化觀測矩陣W，預定義DCT基作為軌跡基Θ。

2)求解旋轉(zhuǎn)矩陣。利用SVD(因式分解法)對觀測矩陣W進行分解，然后再結合相機旋轉(zhuǎn)矩陣的正交約束條件，利用LM算法求得唯一確定的矯正矩陣Q，再根據(jù)式(8)求解出相機旋轉(zhuǎn)矩陣R。

3)求解特征點運動軌跡系數(shù)。將特征點坐標按照幀序數(shù)依次排列，以某個特征點為單元，結合式(11)的稀疏表示思想，利用OMP貪婪算法順序，尋找該特征點在軌跡基Θ下使得重構誤差最小時的最佳軌跡線性組合系數(shù)矩陣Ai。

4)重建人體三維結構。結合預定義軌跡基Θ和上一步求得的系數(shù)矩陣Ai，利用式(10)恢復出第i個特征點的三維結構矩陣Si，經(jīng)過N次迭代后求解整個運動所有特征點的三維結構矩陣S。

5)優(yōu)化三維人體結構矩陣。求解時無需直接求解式(14)，而是求解其在某點處的一個二階近似。具體將第4步求得的結構矩陣S作為APG算法迭代初值，優(yōu)化得到更加精確的人體三維結構矩陣S。

1.4 算法評估準則

本算法性能主要由三維重建結構誤差來衡量重建效果的好壞，也是重建后的結構矩陣與真實的三維結構之間的誤差。為了對重建誤差進行精確的評估，計算公式定義[22]為

(15)

(16)

(17)

(18)

(19)

式中：σtx、σty、σtz分別三維結構中第t幀對應的所有結構點X、Y、Z坐標的標準差(t=1,2,…,M；j=1,2,…,N)；etj表示第t幀第j個三維結構點的誤差，即重構點與實際點間的歐氏距離；Sr代表重建出的三維結構矩陣，S0代表實際的空間結構矩陣，兩者的維度和排列方式均完全相同。

(20)

1.5 驗證方法

本研究所用實驗數(shù)據(jù)來源于網(wǎng)站(http://cvlab.lums.edu.pk/nrsfm)中提供的5種人體運動，具體為包含370幀圖像(每幀有41個特征點)的伸懶腰運動；包含307幀圖像(每幀有41個特征點)的瑜伽運動；包含1 102幀圖像(每幀有41個特征點)的喝水運動；包含357幀圖像(每幀有41個特征點)的拾物運動；包含264幀圖像(每幀有75個特征點)的跳舞運動。

為了驗證所提出算法的有效性和可靠性，通過編程實驗對上述5種人體運動進行三維重建。實驗所用硬件配置為處理器Inter(R)@3.40 GHz 3.40 GHz，內(nèi)存4 GB；軟件環(huán)境為Window7，Matlab2010b。通過編程實驗恢復出人體三維結構矩陣，然后利用公式(15)和公式(20)分別計算該算法下的重建點與真實點之間的重建誤差和幀均誤差，并繪制三維重建效果圖對其進行算法評估和有效性分析。在實驗中，將本算法與其他4種研究算法進行比較，對比的算法包括：MP[22]算法、PTA[5]算法、APG[21]算法和稀疏[15]算法，且以上4種算法所用實驗數(shù)據(jù)與本算法來源于同一網(wǎng)站。

首先，對PTA算法、稀疏算法與本研究算法的重建幀均誤差曲線進行比較，幀均誤差曲線在圖中所在的位置越低，說明該算法下的幀均誤差越小，以此證明算法的有效性。其次，利用柱狀圖對5種人體運動在PTA算法、稀疏算法和本文算法下的重建誤差進行對比分析。主要通過柱狀塊的高低來判斷重建算法的可靠性，柱狀塊越低說明其重建誤差數(shù)值越小，反映該算法下三維重建效果越好。然后，從視覺角度分析，繪制伸懶腰運動、跳舞運動和瑜伽運動在本研究算法與稀疏算法下的三維重建效果圖。由于稀疏方法重建效果優(yōu)于DCT方法，故僅列出本算法與稀疏算法的重建效果圖進行比較。主要通過觀察真實三維點與重建三維點之間的距離和吻合度來驗證算法的有效性，真實點與重建點之間越吻合，說明該算法下的重建效果越好。最后，列出上述5種運動在不同算法下的三維重建誤差數(shù)據(jù)對比表，表中數(shù)據(jù)數(shù)值越小，說明其重建誤差越小，重建精度越高。通過對比重建誤差表中數(shù)據(jù)的大小，驗證本算法的有效可行性。

2 結果

圖1為DCT方法、稀疏方法和本研究算法下的重建幀均誤差曲線。可以看出，隨著幀數(shù)變化，本算法下大多數(shù)幀的幀均誤差曲線均在PTA算法和稀疏算法幀均誤差曲線之下，僅有一小部分幀均誤差曲線高于以上兩種算法，說明該算法下的三維重建誤差相比于其他兩種算法大部分幀下都有所降低，驗證了該算法具有一定的可行性。

圖1 Stretch運動不同算法下重建的均方誤差Fig.1 MSE of stretch motion under the different algorithms

圖2為PTA算法、稀疏算法和本研究算法下對5種人體運動的重建誤差柱狀圖。可以看出，對于不同的運動模型本算法的三維重建誤差柱狀塊均低于前面兩種算法，即該算法下的重建誤差最小，證明該算法具有有效可行性。

圖2 不同算法下五種運動的重構誤差柱狀圖Fig.2 The reconstruction error histogram of five motions by different algorithms

圖3～5分別為人體伸懶腰運動、跳舞運動和瑜伽運動的三維重建效果。可以看出，本算法下重建坐標點與真實坐標點之間的距離更近，說明其重建效果優(yōu)于稀疏算法的重建效果，因此證明該算法的有效性和可靠性。

表1為5種人體運動在MP算法、PTA算法、APG算法、稀疏算法和本研究算法下重建的三維結構矩陣重建誤差對比，其中括號中的數(shù)字表示最佳重建時所需軌跡基個數(shù)。由于MP算法、稀疏算法和本研究算法屬于追蹤算法，其每個特征點重建過程中都可以自適應選擇軌跡基個數(shù)，且每個特征點尋找到的軌跡基個數(shù)不盡相同，因此此處無法對整體的重建列出軌跡基個數(shù)。可以看出，本算法的重建誤差數(shù)值小于其他4種算法的重建誤差數(shù)值，對伸懶腰運動、瑜伽運動和喝水運動重建誤差相對較小，相比于稀疏方法分別提高了17.69%、14.12%、41.25%；對跳舞運動和撿物運動重建誤差相對較大，與稀疏方法比較分別提高了9.58%和9.73%。以上數(shù)據(jù)說明該算法能夠有效地降低重建誤差和具有提高重建精度的能力。

圖3 不同算法伸懶腰運動的三維重建效果(上為Sparse方法，下為本算法；“·”表示真實的三維結構點坐標，“°”代表重建出的三維結構點坐標；方框中為重建效果較好的特征點)。(a)第20幀; (b)第130幀; (c)第260幀; (d)第310幀F(xiàn)ig.3 3D reconstruction renderings of stretch motion with different methods(The above is sparse method, the below is this algorithm; “·”represents the real 3D structure point coordinates, “°”represents the reconstruction 3D structure point coordinates. The point in box is the better features of reconstruction). (a) The 20th frames; (b)The 130th frames; (c)The 260th frames; (d)The 310th frames

圖4 不同算法跳舞運動的三維重建效果(上為Sparse方法，下為本算法；“·”表示真實的三維結構點坐標，“°”代表重建出的三維結構點坐標；方框中為重建效果較好的特征點)。(a)第10幀; (b)第60幀; (c)第130幀; (d)第210幀F(xiàn)ig.4 3D reconstruction renderings of dance motion with different methods(The above is sparse method, the below is this algorithm; “·”represents the real 3D structure point coordinates, “°”represents the reconstruction 3D structure point coordinates. The point in box is the better features of reconstruction). (a)The 10th frames; (b)The 60th frames; (c)The 130th frames;(d)The 210th frames

圖5 不同算法瑜伽運動的三維重建效果(上為Sparse方法，下為本算法；“·”表示真實的三維結構點坐標，“°”代表重建出的三維結構點坐標；方框中為重建效果較好的特征點)。(a)第50幀; (b)第100幀; (c)第225幀; (d)第280幀F(xiàn)ig.5 3D reconstruction renderings of yoga motion with different methods(The above is sparse method, the below is this algorithm; “·”represents the real 3D structure point coordinates, “°”represents the reconstruction 3D structure point coordinates. The point in box is the better features of reconstruction). (a)The 50th frames; (b)The 100th frames; (c)The 225th frames; (d)The 280th frames

表1 不同算法對各種人體運動的重建誤差(其中括號中的數(shù)字表示最佳重建時所需軌跡基個數(shù))

Tab.1 Error table of various human motion in different algorithms (The number in parentheses indicates the number of trajectories needed for optimal reconstruction)

實驗模型MPDCTAPGSparse本方法伸懶腰0.85490.1088(12)0.1071(12)0.08930.0735瑜伽0.80390.1622(11)0.1620(11)0.15580.1338拾物0.43320.2369(12)0.2341(12)0.22450.2030喝水0.46040.0250(13)0.0219(13)0.03030.0178跳舞0.26390.2958(5)0.2669(5)0.25190.2274

3 討論和結論

本研究利用正交匹配追蹤及加速近端梯度算法對人體三維運動進行重建，根據(jù)幀均誤差、重建誤差和重建效果對實驗進行分析。由表1中重建誤差的數(shù)據(jù)顯示，本算法下5組人體運動的重建誤差均有不同程度的減小，由此可見，本算法最優(yōu)，PTA算法最差，稀疏算法次優(yōu)。其根本原因在于PTA算法中，主要利用偽逆法求解軌跡系數(shù)，整個過程是純粹的矩陣運算，這樣不僅加大了計算的復雜度，而且增加了求解大矩陣過程中未知參數(shù)的個數(shù)，并且其求解所得到的系數(shù)是稠密的，還存在需要人為嘗試確定軌跡基個數(shù)的缺點，因此其重建效果最差。在稀疏算法中，雖然可以自適應選擇基原子去擬合運動軌跡，重建出效果較好的人體三維結構，但求解系數(shù)過程中所用基追蹤算法相對復雜，并未考慮結構矩陣自身是低秩矩陣的這個約束條件，因此該算法仍然存在不足。本算法繼承了稀疏逼近算法中的自適應選擇原子的優(yōu)勢，通過正交匹配追蹤算法去順序選擇基原子來“最大化逼近”特征點運動軌跡，克服了人為確定軌跡基個數(shù)和計算復雜的缺點；同時結合三維結構矩陣低秩約束條件，將其秩最小化問題轉(zhuǎn)化為核范數(shù)最小化問題，利用APG算法對結構矩陣進行優(yōu)化處理。由實驗效果可知，針對同一種運動模型本研究算法效果最佳，特別是人體手臂和腿部等細節(jié)部位的重建效果優(yōu)于文獻[5]中PTA算法和文獻[15]中稀疏算法(見圖3～5)，這是因為本算法具有自適應選擇基原子和低制約束的雙重制約，具有一定處理復雜運動的能力，使重建出的三維結構矩陣與真實的三維結構矩陣更加接近。根據(jù)上述對3種算法的分析和討論，可以看出，影響人體三維重建精度的兩大重要因素是原子字典的選擇和軌跡系數(shù)的求解。選擇合適的原子字典不僅可以減少計算復雜度，同時也可以提高重建的精度；同樣，求解精確的軌跡系數(shù)，也可以達到降低重建誤差的目的。本算法可以自適應在字典中選擇最優(yōu)原子，盡最大限度去逼近真實的三維結構，尤其對復雜運動和細節(jié)部位的恢復具有較好的穩(wěn)定性。與文獻[21-22]相比，其重建效果和重建誤差均表明了本算法的優(yōu)越性，但是由于DCT基自身原子種類不足的限制，只能在該基下選擇最佳的原子進行逼近，從而無法最大逼近特征點的真實軌跡。因此，尋找更加完善的原子字典和求解更加精確的軌跡基系數(shù)，成為進一步深入研究的問題。

為了更好地提高人體三維結構的重建精度，本研究提出了一種正交匹配追蹤加速近端梯度算法來解決人體三維運動重建問題，主要解決系數(shù)的求解和結構矩陣的優(yōu)化問題。利用OMP算法對系數(shù)進行稀疏求解，從而達到基原子的最佳選擇和利用APG算法對人體三維結構矩陣進行優(yōu)化。通過相關實驗數(shù)據(jù)，以Drink運動為例，用Sparse重建出的人體三維結構矩陣重構誤差為0.030 3，通過本研究算法重建的重構誤差為0.017 8。并且該算法同樣適用于其他人體運動，結果表明，該算法具有良好的穩(wěn)定性且可以有效提高重建精度，具有有效可行性。由于本研究是在固定原子字典的基礎上研究的，字典中的原子數(shù)量和種類均受到限制。為了更加完整地表示特征點運動軌跡，今后將研究重心轉(zhuǎn)移到原子字典的類型選擇和優(yōu)化上。

(致謝：在此對實驗室成員張靜、童朝凱和周志湖表示感謝，感謝他們在研究中對參考文獻選擇給予的指導，感謝他們在論文撰寫中對寫作思路給出的建議，還要感謝他們與我一起解決研究中的疑難問題和理論難題)

[1] Fabio R. 3-D reconstruction of static human body shape from image sequence[J]. Computer Vision and Image Understanding, 2004, 93(1): 65-85.

[2] Moeslund TB, Granum E. A survey of computer vision-based human motion capture[J]. Computer Vision and Image Understanding, 2001, 81(3): 231-268.

[3] Tmoasi C, Kanade T. Shape and motion from image streams under orthography: a factorization method[J]. International Journal of Computer Vision, 1992, 9(2): 137-154.

[4] Bregler C, Hertzmann A, Biermann H. Recovering non-rigid 3D shape from image streams[C] //Proceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR). Hilton Head: IEEE, 2000, 2: 690-696.

[5] Akhter I, Sheikh Y, Khan S, et al. Trajectory space: A dual representation for nonrigid structure from motion[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(7): 1442-1456.

[6] Barthelemy Q, Larue A, Mars J. Decomposition and dictionary learning for 3D trajectories[J]. Signal Processing, 2014, 98: 423-437.

[7] Zhu Yingying, Simon L. Convolutional sparse coding for trajectory reconstruction[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(3): 529-540.

[8] Park HS, Shiratori T, Matthews I, et al. 3D reconstruction of a moving point from a series of 2D projections[C] //2010 IEEE European Conference on Computer Vision. Berlin: Springer-Verlag, 2010, 6313: 158-171.

[9] Park SH,Shiratori T, Matthews I, et al. 3D trajectory reconstruction under perspective projection[J]. International Journal of Computer Vision, 2015, 115(2): 115-135.

[10] Bue AD, Smeraldi F, Agapito L. Non-rigid structure from motion using non-parametric tracking and non-linear optimization[C] //2004 Conference on Computer Vision and Pattern Recognition Workshop(CVPRW). Washington: IEEE, 2004: 8-8.

[11] Zhu Yingying, Cox M, Simon L. 3D motion reconstruction for real-world camera motion[C] //2011 IEEE Conference on Computer Vision and Pattern Recognition(CVPR). Colorado Springs: IEEE, 2011, 8: 1-8.

[12] Vore D, Ronald A. Nonlinear approximation[J]. Acta Numerica, 1998, 7: 51-150.

[13] Mallat S, Zhang Zhifeng. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1993, 41(12): 3397-3415.

[14] Pati Y, Rezaiifar R, Krishnaprasad PS. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[C] //Proceedings of 27th Asilomar Conference on Signals, Systems and Computers. Los Alamitos: IEEE, 1993: 40-44.

[15] Wang Yaming, Yan Xiaomeng, ZhengJ B, et al. Sparse approximation for nonrigid structure from motion[J]. Journal of Robotics, 2015, 3: 1-8.

[16] Chen Mingyu, Alergib G, Juang BH. Trajectory triangulation: 3D motion reconstruction with1 optimization[C] //2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). Prague: IEEE, 2011: 4020-4023.

[17] Sahoo S, Makur A. Signal recovery from random measurements via extended orthogonal matching pursuit[J]. IEEE Transactions on Signal Processing, 2015, 63(10): 2572-2581.

[18] Silvia G, Isao Y. Alternating minimization techniques for the efficient recovery of a sparsely corrupted low-rank matrix[C] //2010 IEEE International Conference on Acoustics, Speech and Signal Processing. Dallas: IEEE, 2010, 6: 3638-3641.

[19] Trémoulhéac B, Atkinson D, Arridge SR. Fast dynamic MRI via nuclear norm minimization and accelerated proximal gradient[C] //2013 IEEE 10th International Symposium on Biomedical Imaging. San Francisco: IEEE, 2013: 322-325.

[20] Yue Lu, Zhang Liwei. The augmented Lagrangian method based on the APG strategy for an inverse damped gyroscopic eigenvalue problem[J]. Computational Optimization and Applications, 2015, 62(3): 815-850.

[21] Wang Yaming, Tong Lingling, Jiang Mingfeng, et al. Non-rigid structure estimation in trajectory space from monocular vision[J]. Sensors, 2015, 15(10): 25730-25745.

[22] Paladini M, Del Bue A, Stosic M, et al. Factorization for non-rigid and articulated structure using metric projections[C] //2009 IEEE Conference on Computer Vision and Pattern Recognition(CVPR). Miami: IEEE, 2009: 2898-2905.

3D Reconstruction of Human Body Based on Orthogonal Matching Pursuit and Accelerated Proximal Gradient

Wang Yaming Zhai Junpeng Mo Yan*Han Yonghua Jiang Mingfeng

(ResearchInstituteofSignalandInformationProcessing,ZhejiangSci-techUniversity,Hangzhou310018,China)

In order to improve the reconstruction accuracy of the 3D structure of human body, the optimal selection of atoms and the optimization of structure matrix in the process of reconstruction were investigated in this work. On the basis of the sparse representation and low-rank constraint, we proposed an orthogonal matching pursuit and accelerated proximal gradient (OMP-APG) algorithm to provide a wealth information to assist medical doctors to work out the treatment plan quickly and accurately. First of all, the feature matrix was decomposed by singular value decomposition (SVD), and the uniquely determined camera rotation matrix was obtained by LM (Levenberg-Marquardt) algorithm. Secondly, according to the idea of “maximization approximation” in sparse representation, the trajectory basis coefficients were solved by orthogonal matching pursuit algorithm, combined with a predefined trajectory basis to solve the 3D structure of the human body matrix. Finally, considering that the structure matrix was a low rank matrix, the rank optimization problem was transformed into the nuclear norm minimization problem, and the human body structure matrix was further optimized by the accelerated proximal gradient algorithm. The algorithm and sparse approximation algorithms were compared in five motion models including stretch, yoga, pick up, drink and dance in 3D reconstruction with the 3D reconstruction renderings and 3D reconstruction errors. The results showed that the reconstruction accuracy was higher and had better stability. In this algorithm, the reconstruction of drink motion was the best, and the reconstruction error of the 41 feature points of the 1102 frame image sequence was about 0.0303, while the reconstruction error under the sparse algorithm was about 0.0178. In conclusion, the algorithm improved the reconstruction accuracy of the human three-dimensional structure.

3D reconstruction; human motion reconstruction; sparse representation; accelerated proximal gradient

10.3969/j.issn.0258-8021. 2017. 04.001

2016-09-27， 錄用日期:2017-01-08

國家自然科學基金項目(61672466)；浙江省自然科學基金(LZ15F020004，LY1720034)；浙江理工大學521項目

R318

A

0258-8021(2017) 04-0385-09

*通信作者(Corresponding author)，E-mail: moyan@zstu.edu.cn