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

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

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

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

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

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

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

三維重建；人體運(yùn)動(dòng)重建；稀疏表示；加速近端梯度

引言

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

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

1 方法

1.1 人體三維重建結(jié)構(gòu)

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

(1)

式中：W矩陣是二維觀測矩陣，是一個(gè)2M×N的矩陣；uij代表第i幀第j個(gè)點(diǎn)二維序列中的x坐標(biāo)，vij代表第i幀第j個(gè)點(diǎn)二維序列中的y坐標(biāo)。

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

(2)

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

結(jié)合SVD分解以及式(2)，可以得到人體三維結(jié)構(gòu)矩陣的表達(dá)式為

(3)

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

1.2 OMP-APG算法

1.2.1 正交匹配追蹤算法

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

(4)

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

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

(5)

(6)

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

1.2.2 系數(shù)求解

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

(7)

因?yàn)橐粋€(gè)非奇異Q矩陣的存在，使得式(7)分解出來不唯一的結(jié)果，即

(8)

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

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

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

(9)

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

式(9)也能寫成

(10)

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

(11)

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

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

1.2.3 結(jié)構(gòu)優(yōu)化

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

(12)

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

(13)

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

(14)

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

1.3 算法步驟

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

1)初始化。利用相機(jī)投影模型和真實(shí)三維結(jié)構(gòu)矩陣初始化觀測矩陣W，預(yù)定義DCT基作為軌跡基Θ。

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

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

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

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

1.4 算法評估準(zhǔn)則

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

(15)

(16)

(17)

(18)

(19)

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

(20)

1.5 驗(yàn)證方法

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

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

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

2 結(jié)果

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

圖1 Stretch運(yùn)動(dòng)不同算法下重建的均方誤差Fig.1 MSE of stretch motion under the different algorithms

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

圖2 不同算法下五種運(yùn)動(dòng)的重構(gòu)誤差柱狀圖Fig.2 The reconstruction error histogram of five motions by different algorithms

圖3～5分別為人體伸懶腰運(yùn)動(dòng)、跳舞運(yùn)動(dòng)和瑜伽運(yùn)動(dòng)的三維重建效果?？梢钥闯?，本算法下重建坐標(biāo)點(diǎn)與真實(shí)坐標(biāo)點(diǎn)之間的距離更近，說明其重建效果優(yōu)于稀疏算法的重建效果，因此證明該算法的有效性和可靠性。

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

圖3 不同算法伸懶腰運(yùn)動(dòng)的三維重建效果(上為Sparse方法，下為本算法；“·”表示真實(shí)的三維結(jié)構(gòu)點(diǎn)坐標(biāo)，“°”代表重建出的三維結(jié)構(gòu)點(diǎn)坐標(biāo)；方框中為重建效果較好的特征點(diǎn))。(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 不同算法跳舞運(yùn)動(dòng)的三維重建效果(上為Sparse方法，下為本算法；“·”表示真實(shí)的三維結(jié)構(gòu)點(diǎn)坐標(biāo)，“°”代表重建出的三維結(jié)構(gòu)點(diǎn)坐標(biāo)；方框中為重建效果較好的特征點(diǎn))。(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 不同算法瑜伽運(yùn)動(dòng)的三維重建效果(上為Sparse方法，下為本算法；“·”表示真實(shí)的三維結(jié)構(gòu)點(diǎn)坐標(biāo)，“°”代表重建出的三維結(jié)構(gòu)點(diǎn)坐標(biāo)；方框中為重建效果較好的特征點(diǎn))。(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 不同算法對各種人體運(yùn)動(dòng)的重建誤差(其中括號中的數(shù)字表示最佳重建時(shí)所需軌跡基個(gè)數(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)

實(shí)驗(yàn)?zāi)Ｐ蚆PDCTAPGSparse本方法伸懶腰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 討論和結(jié)論

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

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

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

[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

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

R318

A

0258-8021(2017) 04-0385-09

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