侯培，田慶國(guó)，葛寶臻

1.天津大學(xué)精密儀器與光電子工程學(xué)院，天津 300072

2.光電信息技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，天津 300072

基于優(yōu)化DRG的三維人體點(diǎn)云骨架提取方法

侯培1，2，田慶國(guó)1，2，葛寶臻1，2

1.天津大學(xué)精密儀器與光電子工程學(xué)院，天津 300072

2.光電信息技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，天津 300072

三維模型的骨架通常指模型的中軸，它是一組位于物體中心位置的曲線(xiàn)集合，是物體的一種很重要的拓?fù)湫螤蠲枋龇鸞1]，能夠清晰地呈現(xiàn)模型的形狀信息和拓?fù)涮匦?，提供模型的語(yǔ)義學(xué)信息。因此在模型動(dòng)畫(huà)[2]、模型重建[3]、圖形檢索[4]、圖像分割[5-6]和醫(yī)學(xué)圖像[7]等很多方面得到廣泛的應(yīng)用和研究。

傳統(tǒng)的骨架提取方法一般基于三維體素模型，而由三維掃描儀得到的點(diǎn)云模型散亂且無(wú)語(yǔ)義特征，在骨架提取前需要進(jìn)行處理，變成體素或網(wǎng)格模型。這個(gè)過(guò)程不僅花費(fèi)更多時(shí)間，而且容易引入噪聲，若模型存在漏洞則會(huì)給體素化帶來(lái)一定難度。故諸多學(xué)者開(kāi)始研究直接在散亂的點(diǎn)云模型上提取骨架的方法。

基于Morse[8]理論和Reeb圖原理[9]可以提取點(diǎn)云模型的骨架。Verroust A.等人提出了計(jì)算3D散亂點(diǎn)云模型的Reeb圖，將其作為曲線(xiàn)骨架的算法，該方法適用于具有樹(shù)狀分支的模型[10]；Xiao Yijun將這種在點(diǎn)云模型上提取的Reeb圖定義為離散Reeb圖（DRG）并應(yīng)用于人模型的肢體分割[5]；Natali等人將DRG推廣為任意維度空間，可以應(yīng)用在任何形狀、任何質(zhì)量的點(diǎn)云模型上[11]。DRG計(jì)算簡(jiǎn)單，能直接操作由三維掃描儀掃描得到的點(diǎn)云數(shù)據(jù)模型，得到的結(jié)果與原模型的拓?fù)湟恢滦院谩５湓诿枋瞿Ｐ椭黧w與分支連接區(qū)域的骨架時(shí)，出現(xiàn)分支部分骨架曲線(xiàn)偏離中軸的問(wèn)題。

為了改進(jìn)上述問(wèn)題，得到更加準(zhǔn)確的骨架曲線(xiàn)，本文提出了一種優(yōu)化方法：提取人體模型的DRG作為初始骨架模型，建立初始骨架的能量函數(shù)，在點(diǎn)云模型距離場(chǎng)梯度驅(qū)使下不斷迭代調(diào)整曲線(xiàn)位置直到骨架的能量達(dá)到最小，最終將其調(diào)整到中軸位置，得到準(zhǔn)確的人體點(diǎn)云模型骨架曲線(xiàn)。本文方法得到的骨架曲線(xiàn)能保持較好的連續(xù)性和與原模型的拓?fù)湟恢滦?，且位置十分?zhǔn)確。將本文算法應(yīng)用于各種不同姿勢(shì)的人體模型，結(jié)果表明所得骨架曲線(xiàn)更接近模型中軸位置。

1 基于優(yōu)化DRG的骨架提取算法

本文算法中提取人體點(diǎn)云模型骨架的過(guò)程為：提取點(diǎn)云模型的DRG，將其作為初始骨架線(xiàn)；對(duì)初始骨架曲線(xiàn)進(jìn)行預(yù)處理，去除一些噪聲點(diǎn)帶來(lái)的“毛刺”等錯(cuò)誤分叉，并對(duì)初始曲線(xiàn)進(jìn)行修正；將預(yù)處理后的骨架曲線(xiàn)中分支部位的曲線(xiàn)作為目標(biāo)段骨架線(xiàn)，建立點(diǎn)云模型的距離場(chǎng)和骨架曲線(xiàn)的能量函數(shù)，在模型距離場(chǎng)梯度驅(qū)使下不斷調(diào)整目標(biāo)段骨架線(xiàn)位置，直到能量函數(shù)值最小，從而得到更接近中軸位置的優(yōu)化DRG骨架曲線(xiàn)。

1.1 點(diǎn)云模型DRG提取

離散Reeb圖可以看做是經(jīng)典Reeb圖連續(xù)曲線(xiàn)的離散化，由離散節(jié)點(diǎn)和連接節(jié)點(diǎn)的線(xiàn)段來(lái)近似表示曲線(xiàn)。在模型拓?fù)浣Y(jié)構(gòu)發(fā)生分支的部分，細(xì)節(jié)信息較多，在節(jié)點(diǎn)離散化過(guò)程中會(huì)缺失這些細(xì)節(jié)表示，從而使得這部分曲線(xiàn)偏離中軸位置。圖1為采用本實(shí)驗(yàn)室三維人體掃描儀得到的三維人體點(diǎn)云模型，圖中的曲線(xiàn)為點(diǎn)云模型的DRG經(jīng)過(guò)預(yù)處理后的初始骨架線(xiàn)，曲線(xiàn)上各點(diǎn)為DRG的節(jié)點(diǎn)。圖1中三個(gè)橢圓區(qū)域由上到下依次為頭部、肩部和胯部的部分區(qū)域放大圖。頭部放大區(qū)域顯示了由點(diǎn)云模型上噪聲引起的一系列毛刺和孤立錯(cuò)誤點(diǎn)，這些點(diǎn)使骨架拓?fù)湫源嬖谡`差，可能導(dǎo)致分支部位的誤判，需要將其去除；肩部和胯部放大區(qū)域分別顯示了分支部位曲線(xiàn)偏離中軸的情況。這些偏離使得骨架曲線(xiàn)位置不準(zhǔn)確，因此需要在保持骨架曲線(xiàn)拓?fù)湫缘幕A(chǔ)上找到分支部位偏離中軸的骨架曲線(xiàn)段進(jìn)行優(yōu)化，調(diào)整偏離骨架線(xiàn)的位置，提高骨架提取精度。綜上所述，為了得到更準(zhǔn)確的骨架，需要對(duì)DRG初始骨架進(jìn)行預(yù)處理去除毛刺噪聲，然后再對(duì)預(yù)處理后的骨架曲線(xiàn)優(yōu)化。預(yù)處理后骨架線(xiàn)如圖2所示。

圖1 人體三維點(diǎn)云模型DRG

圖2 預(yù)處理后骨架線(xiàn)

1.2 初始骨架線(xiàn)預(yù)處理

在優(yōu)化之前，先對(duì)DRG骨架曲線(xiàn)進(jìn)行預(yù)處理，包括去除毛刺和修正骨架兩部分。由1.1節(jié)的分析可知，對(duì)分支部位的偏離骨架線(xiàn)進(jìn)行優(yōu)化前，需要根據(jù)DRG中節(jié)點(diǎn)連接情況判斷分支部位，如DRG上存在圖1中頭部的毛刺現(xiàn)象，將影響判斷的準(zhǔn)確性。因此在優(yōu)化前，需要去除這些噪聲點(diǎn)帶來(lái)的毛刺。去除的過(guò)程為：首先，去除沒(méi)有與其他節(jié)點(diǎn)相連接的孤立節(jié)點(diǎn)；然后查找分叉節(jié)點(diǎn)，如果連接在這個(gè)分叉節(jié)點(diǎn)上的分支骨架線(xiàn)長(zhǎng)度小于某閾值，去掉這個(gè)分支骨架線(xiàn)，并重新計(jì)算該區(qū)間剩余分支線(xiàn)的位置。

骨架預(yù)處理的另一個(gè)內(nèi)容是修正骨架線(xiàn)，將曲線(xiàn)中位于體外的部分調(diào)整到體內(nèi)。修正骨架原因有二：對(duì)曲線(xiàn)段優(yōu)化時(shí)，需要迭代地移動(dòng)目標(biāo)曲線(xiàn)段直到中軸位置，初始目標(biāo)曲線(xiàn)越接近中軸，需要迭代的次數(shù)將越少；由于體內(nèi)位置距離場(chǎng)值為正，體外位置距離場(chǎng)值為負(fù)，迭代過(guò)程中要不斷判斷曲線(xiàn)是否位于體內(nèi)，這將降低算法的效率。為了減少迭代次數(shù)并且減少迭代過(guò)程中判斷體內(nèi)體外狀態(tài)的次數(shù)，在初始骨架線(xiàn)預(yù)處理階段就將體外曲線(xiàn)調(diào)整到體內(nèi)從而提高優(yōu)化算法的運(yùn)算效率，而且調(diào)整目標(biāo)骨架線(xiàn)的初始位置并不改變骨架最終移動(dòng)到中軸上這一結(jié)果。調(diào)整骨架線(xiàn)的方法為：找到分叉點(diǎn)，根據(jù)分叉部位拓?fù)涮卣鳑Q定分叉點(diǎn)調(diào)整方向，沿此方向調(diào)整一段位移后判斷分叉點(diǎn)上連接的分支骨架線(xiàn)是否都在體內(nèi)，若沒(méi)有到達(dá)體內(nèi)則循環(huán)移動(dòng)分叉點(diǎn)，直到所有分支骨架線(xiàn)都位于體內(nèi)時(shí)停止。判斷空間某點(diǎn)是否在體內(nèi)的方法為：過(guò)該點(diǎn)的平面在人體點(diǎn)模型上截得一個(gè)二維圖形，在這個(gè)二維平面上，判斷該點(diǎn)是否在二維圖形內(nèi)部，則可知此點(diǎn)是否在三維模型內(nèi)部。圖2為將圖1結(jié)果進(jìn)行預(yù)處理之后的結(jié)果，此時(shí)的結(jié)果沒(méi)有雜散點(diǎn)和毛刺的影響，骨架線(xiàn)全部調(diào)整到了體內(nèi)，優(yōu)化過(guò)程中將不需要考慮體外的情況。

1.3 基于能量最小化的骨架曲線(xiàn)優(yōu)化

對(duì)于預(yù)處理后的骨架線(xiàn)，自動(dòng)找取人體分支部位的多段骨架線(xiàn)作為待優(yōu)化目標(biāo)線(xiàn)段，用υ(s)表示其中一段待優(yōu)化曲線(xiàn)，通過(guò)變換曲線(xiàn)形狀將定義在該曲線(xiàn)上的能量函數(shù)（1）最小化，就能得到更為優(yōu)化的骨架曲線(xiàn)，能量函數(shù)表示為：

其中，L(υ)為待優(yōu)化曲線(xiàn)的長(zhǎng)度，它控制骨架線(xiàn)的形狀，使其具有一定的彈性；P(υ)是由能夠體現(xiàn)點(diǎn)云模型性質(zhì)的數(shù)據(jù)構(gòu)成的函數(shù)，它約束骨架線(xiàn)的位置，其最小值所對(duì)應(yīng)的位置為中軸部位。α、β分別代表各部分權(quán)重，根據(jù)實(shí)驗(yàn)可以確定一個(gè)經(jīng)驗(yàn)值。外力推動(dòng)初始骨架線(xiàn)發(fā)生形變，使其慢慢靠近中軸部位，直至能量函數(shù)（1）達(dá)到局部極小值，從而得到優(yōu)化的骨架曲線(xiàn)。

基于上述原理，本文需要找到一個(gè)P(υ)表達(dá)式，使得當(dāng)骨架線(xiàn)向中軸位置移動(dòng)時(shí)，其函數(shù)值逐漸減小。按照文獻(xiàn)[12]中的定義，模型中某點(diǎn)到模型上的最短距離為該點(diǎn)距離場(chǎng)。越接近模型中軸，距離場(chǎng)值越大，距離場(chǎng)的局部極值為模型的中軸所在位置。因此，如果定義距離場(chǎng)的倒數(shù)作為P(υ)，則當(dāng)曲線(xiàn)越靠近中軸，該函數(shù)值越小，符合上述要求。

要得到函數(shù)P(υ)的表達(dá)式，首先需要得到點(diǎn)云模型中任意位置的距離場(chǎng)。在三維體素模型中，文獻(xiàn)[13]給出通過(guò)距離場(chǎng)變換得到模型中任意位置的距離場(chǎng)值。連續(xù)空間中某一點(diǎn)υk的距離場(chǎng)值D(υk)為點(diǎn)υk到模型表面上的最短距離。而在本文的點(diǎn)云模型中，若點(diǎn)云足夠密，即點(diǎn)云模型中相鄰點(diǎn)之間的距離遠(yuǎn)小于空間點(diǎn)υk到模型表面的距離時(shí)，υk的距離場(chǎng)值近似等于該點(diǎn)與點(diǎn)云模型上最近點(diǎn)的距離值，即

pi為點(diǎn)云模型上第i個(gè)頂點(diǎn)。

用MATLAB按照上述方法計(jì)算點(diǎn)云模型空間中的距離場(chǎng)值從而證明該方法的正確性。用平面截取圖1中點(diǎn)云模型得到一個(gè)二維截面，圖3（a）中點(diǎn)為所截得大腿部位二維點(diǎn)云，根據(jù)本文所述點(diǎn)云模型距離場(chǎng)構(gòu)造方法，求得平面上各位置的距離場(chǎng)的大小及其梯度值，圖3（a）中箭頭所示為距離場(chǎng)梯度，可以看出，在模型內(nèi)部，距離場(chǎng)增大的方向指向中心。圖3（b）為對(duì)應(yīng)距離場(chǎng)的三維表示，高度代表距離場(chǎng)的絕對(duì)值，高度最低的環(huán)形對(duì)應(yīng)圖3（a）中點(diǎn)云所在位置。由圖3（b）可直觀看到，距離場(chǎng)大小分布呈“花蕊狀”，在模型內(nèi)部，越遠(yuǎn)離點(diǎn)云模型，距離場(chǎng)值越大，距離場(chǎng)值在中軸部位達(dá)到最大值；在模型外部，越遠(yuǎn)離模型，距離場(chǎng)的大小也將增大。初始骨架線(xiàn)經(jīng)過(guò)預(yù)處理后，都將位于體內(nèi)，因此不需要考慮體外情況。由圖3可知根據(jù)本文方法構(gòu)造的距離場(chǎng)最大值位于中軸部位。

圖3 點(diǎn)云模型距離場(chǎng)

越接近中軸，曲線(xiàn)上各點(diǎn)的距離場(chǎng)值越大，則P(υ)值越小。選取合適的α、β值，在曲線(xiàn)長(zhǎng)度L(υ)的約束下，能量函數(shù)（1）最小時(shí)將得到較為準(zhǔn)確的骨架。

目標(biāo)線(xiàn)段的起點(diǎn)和尾點(diǎn)固定，所有插入點(diǎn)在距離場(chǎng)梯度的推動(dòng)下逐漸移動(dòng)，插入點(diǎn)υi的坐標(biāo)為(υx，υy，υz)，每次移動(dòng)的位移矢量為(Gx，Gy，Gz)，其中：δ為單位長(zhǎng)度，其大小與點(diǎn)云模型相鄰點(diǎn)之間的平均距離值為同一數(shù)量級(jí)。

下面是優(yōu)化算法的具體描述：

（1）根據(jù)初始骨架線(xiàn)上各節(jié)點(diǎn)的連接情況，找到分支部位的節(jié)點(diǎn)，定位人體模型的分支部位。

（2）找到分支部位所有偏離中軸的目標(biāo)線(xiàn)段，記錄目標(biāo)線(xiàn)段個(gè)數(shù)N。

（3）以目標(biāo)線(xiàn)段的兩端點(diǎn)為首尾點(diǎn)，在其中均勻地插入n個(gè)插入點(diǎn)。

（4）按公式（1）計(jì)算初始曲線(xiàn)的能量E0。

（5）按公式（4）計(jì)算插入點(diǎn)的移動(dòng)矢量，將每個(gè)插入點(diǎn)移動(dòng)到新的位置，形成新曲線(xiàn)。

（6）按照公式（1）計(jì)算新曲線(xiàn)的能量E1，比較E0和E1的大小。

（7）如果E1≤E0，則將當(dāng)前E1賦給E0，并循環(huán)執(zhí)行（5）～（6）步驟直到E1>E0為止。

（8）對(duì)每條目標(biāo)線(xiàn)段執(zhí)行步驟（3）～（7），共執(zhí)行N次。

經(jīng)過(guò)上面步驟后，目標(biāo)線(xiàn)段最終成為一條更接近中軸的骨架曲線(xiàn)。圖4為應(yīng)用上述算法對(duì)于圖1所示人體點(diǎn)云模型肩部各段目標(biāo)骨架線(xiàn)的優(yōu)化過(guò)程，圖4（a）為預(yù)處理后的初始曲線(xiàn)，圖4（b），（c）分別為優(yōu)化過(guò)程中曲線(xiàn)經(jīng)過(guò)的位置，圖4（b）為循環(huán)執(zhí)行20次步驟（5）～（6）后的曲線(xiàn)，圖4（c）為循環(huán)執(zhí)行30次的曲線(xiàn)，圖4（d）為曲線(xiàn)移動(dòng)到中軸完成優(yōu)化的結(jié)果。圖5為人體胯部各段初始骨架線(xiàn)的優(yōu)化過(guò)程，圖5（a）為預(yù)處理后的初始曲線(xiàn)，圖5（b），（c）分別為優(yōu)化過(guò)程中曲線(xiàn)經(jīng)過(guò)的位置，圖5（b）為循環(huán)移動(dòng)20次的結(jié)果，圖5（c）為循環(huán)移動(dòng)40次的結(jié)果，圖5（d）為完成優(yōu)化后的結(jié)果。圖4和圖5形象地展示了對(duì)于偏離中軸曲線(xiàn)優(yōu)化的過(guò)程。

圖4 肩部骨架線(xiàn)優(yōu)化過(guò)程

圖5 胯部骨架線(xiàn)優(yōu)化過(guò)程

2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)中三維圖像文件的讀取和顯示采用本實(shí)驗(yàn)室開(kāi)發(fā)的激光三維表面數(shù)字化系統(tǒng)軟件包完成。采用的三維人體點(diǎn)云模型是由天津大學(xué)自主研制的“激光掃描三維數(shù)字化儀”[14]掃描得到。該掃描儀掃描范圍為1 m（直徑）×2 m（高），分辨率為1 mm（水平）×2 mm（深度）× 2～4 mm（豎直方向可調(diào)整），掃描時(shí)間為16.7～33.4 s。

2.1 優(yōu)化前后結(jié)果對(duì)比

為了驗(yàn)證本文的優(yōu)化算法所得骨架位置的準(zhǔn)確性，對(duì)圖1所示的點(diǎn)云模型進(jìn)行實(shí)驗(yàn)。選擇點(diǎn)云上的測(cè)地距離作為標(biāo)量函數(shù)，計(jì)算模型的DRG，圖1為計(jì)算結(jié)果。將所得DRG曲線(xiàn)進(jìn)行預(yù)處理，相鄰兩個(gè)節(jié)點(diǎn)間的骨架弦長(zhǎng)度作為判斷毛刺的閾值，剪除“毛刺”分支，以相鄰節(jié)點(diǎn)作為移動(dòng)單位，修正骨架線(xiàn)以提高算法的效率，得到圖2所示預(yù)處理后的骨架曲線(xiàn)。根據(jù)節(jié)點(diǎn)連接情況找到分支部位曲線(xiàn)段作為目標(biāo)曲線(xiàn)，對(duì)每段目標(biāo)線(xiàn)段均勻插入5個(gè)節(jié)點(diǎn)來(lái)代表離散化的曲線(xiàn)，優(yōu)化過(guò)程中參數(shù)的設(shè)置為α:β≈33且小范圍浮動(dòng)不影響優(yōu)化結(jié)果，經(jīng)多次迭代后得到優(yōu)化的骨架曲線(xiàn)。圖6（a）為DRG曲線(xiàn)，圖6（b）和圖6（c）分別為優(yōu)化后的骨架曲線(xiàn)的正面視圖和側(cè)面視圖，相較于圖6（a），圖6（b）中曲線(xiàn)位置更加準(zhǔn)確，說(shuō)明本文算法在DRG基礎(chǔ)上有效地提高了骨架曲線(xiàn)的中軸性。

圖6 針對(duì)圖1中模型進(jìn)行骨架提取結(jié)果

2.2 同一模特的不同姿勢(shì)模型骨架提取對(duì)比

圖7 大臂平舉姿勢(shì)模型骨架提取

圖8 下肢彎曲姿勢(shì)模型骨架提取

為了說(shuō)明本文算法在不同姿勢(shì)下的適用性，在相同環(huán)境中對(duì)同一個(gè)模特掃描了不同姿勢(shì)的人體點(diǎn)云模型，按照以上過(guò)程進(jìn)行計(jì)算并對(duì)比結(jié)果，圖7～圖10列出其中四種具有典型特征姿勢(shì)的實(shí)驗(yàn)結(jié)果，其中圖7～圖10的（a）分別為對(duì)應(yīng)姿勢(shì)模型優(yōu)化后骨架的正面視圖，圖7～圖10中的（b）為對(duì)應(yīng)優(yōu)化骨架的側(cè)面視圖。

圖9 邁左腿姿勢(shì)模型骨架提取

圖10 雙臂上舉姿勢(shì)模型骨架提取

圖7模特姿勢(shì)的特點(diǎn)是模型中包含一段與身體拓?fù)浞较虼怪钡耐負(fù)浣Y(jié)構(gòu)，即平舉的大臂；圖8中姿勢(shì)的特點(diǎn)是下肢包含較大的彎曲角度；圖9中姿勢(shì)的特點(diǎn)是模型左右腿不對(duì)稱(chēng)，左腿向前邁一大步；圖10中姿勢(shì)的特點(diǎn)是上肢拓?fù)浞种蛏稀D7～圖10中四種不同姿勢(shì)的模型進(jìn)行骨架提取所得結(jié)果進(jìn)行對(duì)比說(shuō)明：算法能自動(dòng)判斷不同的分叉類(lèi)型，準(zhǔn)確找到分叉部位中需要優(yōu)化的目標(biāo)線(xiàn)段并進(jìn)行優(yōu)化；在肢體彎曲角度很大時(shí)仍能很好地提取其中軸；能識(shí)別較為復(fù)雜的拓?fù)浣Y(jié)構(gòu)，并正確提取其骨架；算法不局限于對(duì)稱(chēng)模型。因此本文算法對(duì)不同姿勢(shì)的人體模型具有較高的穩(wěn)定性。

2.3 不同模特同一姿勢(shì)模型骨架提取對(duì)比

為了驗(yàn)證本文算法對(duì)于不同體型模特點(diǎn)云模型的適應(yīng)性，本文采集了不同體型的模特的多種姿勢(shì)的點(diǎn)云模型并進(jìn)行骨架提取。圖11為不同體型模特的點(diǎn)云模型骨架提取結(jié)果，且模特姿勢(shì)與圖9相同。圖11中模特（a）為偏瘦高型的男性，圖11（b）模特為偏胖高型的男性，圖11（c）模特為偏瘦高型的女性，圖11（d）模特為偏胖矮型的女性。由圖可以看出，不同體型的模特骨架提取結(jié)果略有差異：較瘦的人更容易區(qū)分出其胯部和腋下分支，因此提取效果更好，較胖人的骨架在分支部位中軸性略差，但整體來(lái)說(shuō)，提取效果有了較大的提高。結(jié)果表明，本文算法能夠很好地適應(yīng)模特體型的變化，提取出中軸性較好的骨架曲線(xiàn)。

圖11 不同體型模型的骨架提取結(jié)果

2.4 與其他方法對(duì)比

基于拉普拉斯算子的點(diǎn)云收縮的骨架提取方法[15]是近年來(lái)較為流行的一種點(diǎn)云模型骨架提取算法。該算法魯棒性高，受模型的噪聲和數(shù)據(jù)缺失的影響較小，可以廣泛地應(yīng)用在各種模型上。而本文提出的算法主要針對(duì)人體點(diǎn)云模型，為了驗(yàn)證本文算法的有效性，將本文算法與近年流行的基于拉普拉斯算子的點(diǎn)云收縮方法進(jìn)行對(duì)比，圖12所示為采用拉普拉斯算子的點(diǎn)云收縮方法對(duì)圖6～圖10所示姿勢(shì)的點(diǎn)云模型處理結(jié)果，圖12（a）～（e）分別對(duì)應(yīng)圖6（a）～圖10（a），比較兩組結(jié)果可以看出：（1）兩種算法都能正確地得到模型的拓?fù)浣Y(jié)構(gòu)；（2）觀察五個(gè)模型的肩部和胯部分支部位骨架線(xiàn)，文獻(xiàn)[15]算法所得肩部骨架線(xiàn)偏低，基于本文算法的骨架線(xiàn)經(jīng)過(guò)優(yōu)化后，分叉部位更貼合模型表面的變化，中軸性更好；（3）由于本文算法的提取結(jié)果較依賴(lài)測(cè)地距離源點(diǎn)的選擇，根據(jù)本文算法，圖10（a）測(cè)地距離源點(diǎn)位于人體左腳部位，導(dǎo)致骨架線(xiàn)上胯部分叉的中心點(diǎn)略有偏移，而圖12（e）所得結(jié)果提取曲線(xiàn)較為對(duì)稱(chēng)，但在人體末端，如頭頂部、腳部和手部，文獻(xiàn)[15]算法所得骨架線(xiàn)終點(diǎn)沒(méi)有到達(dá)肢體末端，而本文算法所得骨架線(xiàn)在肢體末端更完整。因此，本文算法主要針對(duì)人體點(diǎn)云模型，能夠準(zhǔn)確提取出中軸性較好的骨架曲線(xiàn)。

兩種算法所需時(shí)間均較為依賴(lài)迭代次數(shù)，與模型的姿勢(shì)、形狀和算法中參數(shù)的設(shè)置等因素緊密相關(guān)。文獻(xiàn)[15]作者給出其算法的MATLAB程序，用該程序?qū)D7模型進(jìn)行處理提取出骨架線(xiàn)所需時(shí)間為2 943.765 s，用MATLAB實(shí)現(xiàn)本文算法對(duì)該模型的處理，運(yùn)行時(shí)間為2 214.299 s。

圖12 文獻(xiàn)[15]算法對(duì)各種姿勢(shì)模型進(jìn)行骨架提取的結(jié)果

3 結(jié)束語(yǔ)

本文基于Morse原理和三維點(diǎn)云模型的DRG提取方法，研究了對(duì)DRG骨架線(xiàn)進(jìn)行優(yōu)化的方法。本文方法可以直接應(yīng)用在三維掃描儀得到的點(diǎn)云模型上，省去了對(duì)點(diǎn)云進(jìn)行重建等處理的步驟。該方法通過(guò)對(duì)模型的DRG曲線(xiàn)位置進(jìn)行調(diào)整，采用能量最小化方法將分叉部位骨架線(xiàn)移動(dòng)到中軸位置，從而得到優(yōu)化骨架線(xiàn)。實(shí)驗(yàn)證明，相比于模型的DRG來(lái)說(shuō)，使用本文方法優(yōu)化后的骨架曲線(xiàn)更符合人的直觀理解，位置更加準(zhǔn)確，且本文算法對(duì)于三維人體點(diǎn)云模型的變化有較高的適應(yīng)性。

[1]Wu Jiangui，Duan Hong，Qi Zhong.3D image skeleton algorithms[C]//2011 IEEE International Conference on Anti-Counterfeiting，Security and Identification，Xiamen，China，2011：97-100.

[2]于勇，王兆其，夏時(shí)洪，等.一種姿態(tài)無(wú)關(guān)的人體模型骨骼提取方法[J].計(jì)算機(jī)研究與發(fā)展，2008，45（7）：1249-1258.

[3]Serino L，Arcelli C.On the computation of the<3，4，5> curve skeleton of 3D objects[J].Pattern Recognition Letters，2011，32（9）：1406-1414.

[4]Hilaga M，Shinagawa Y，Kohmura T，et al.Topology matching for fully automatic similarity estimation of 3D shapes[C]// Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques.New York：ACM，2001：203-212.

[5]Xiao Yijun，Siebert P，Werghi N.A discrete Reeb graph approach for the segmentation of human body scans[C]// Proceedings of the Fourth International Conference on 3-D Digital Imaging and Modeling，2003：378-385.

[6]Werghi，Xiao Yijun，Siebert J P.A functional-based segmentation of human body scans in arbitrary postures[J].IEEE Transactions on Systems，Man，and Cybernetics-Part B：Cybernetics，2006，36（1）：153-165.

[7]Ding M，Tong R，Liao Shenghui，et al.An extension to 3D topological thinning method based on LUT for colon centerline extraction[J].Computer Methods and Programs in Biomedicine，2009，94（1）：39-47.

[8]Milnor J.Morse theory[M].Princeton：Princeton University Press，1963：1-5.

[9]Reeb G.Sur les points singuliers d’une forme de pfaff completement integrable ou d’une fonction numerique[J]. Comptes Randus Acad Sci，1946，222：847-849.

[10]Verroust A，Lazarus F.Extracting skeletal curves from 3D scattered data[J].The Visual Computer，2000，16（1）：15-25.

[11]Natali M，Biasotti S，Patane G，et al.Graph-based representations of point clouds[J].Graphical Models，2011，73（5）：151-164.

[12]Harry B.A transformation for extracting new descriptors of shape[J].Models for the Perception of Speech and Visual Form，1967，19（5）：362-380.

[13]Wang Jun，Tan Ying.Efficient euclidean distance transform algorithm of binary images in arbitrary dimensions[J].Pattern Recognition，2013，46：230-242.

[14]葛寶臻，孫宇臣.激光三維彩色掃描數(shù)字化方法及數(shù)字化儀：中國(guó)，ZL200510013085.8[P].2005-07-27.

[15]Cao Junjie，Andrea T，Matt O，et al.Point cloud skeletons via Laplacian-based contraction[C]//Shape Modeling International Conference（SMI），2010：187-197.

HOU Pei1，2,TIAN Qingguo1，2,GE Baozhen1，2

1.School of Precision Instrument and Opto-Electronics Engineering,Tianjin University,Tianjin 300072,China
2.Key Laboratory of Opto-Electronics Information Technology of Ministry of Education,Tianjin 300072,China

By minimizing the energy function,the optimization algorithm on the Discrete Reeb Graph（DRG）is put forward to reduce the deviation of the branch skeletal curves from the medial axis.The proposed method takes the DRG of the model as the initial skeleton curve,and later defines an energy function to deal with deviation.The distance field gradient of the scanning data leads the initial skeleton curve to the axis position step by step through iteratively adjusting positions of target curve,and the optimized skeletal curves can be realized when the energy value of the curves is minimized.In the experiments,the proposed method is applied to the scanning data of the same model under four different postures and four different models with the same posture respectively,and it also compares this algorithm with curve skeleton extraction via Laplacian-based contraction.The results verify that the optimized algorithm proposed can adapt to different postures and different body types,and ensure that ultimate curves are closest to the medial axis.Moreover,better descriptions on features of furcation curves can also be obtained.

Discrete Reeb Graph（DRG）;three dimensional human scanning data;extract skeletal curves;minimizing the energy function

針對(duì)離散Reeb圖（Discrete Reeb Graph，DRG）描述人體骨架時(shí)分支部位骨架線(xiàn)偏離中軸的問(wèn)題，采用了能量函數(shù)最小化的方法對(duì)DRG曲線(xiàn)進(jìn)行優(yōu)化。將人體模型的DRG曲線(xiàn)作為初始骨架，定義其能量函數(shù)，在點(diǎn)云模型的距離場(chǎng)梯度的作用下，迭代地調(diào)整偏離中軸目標(biāo)段的曲線(xiàn)位置使其逐漸逼近中軸，能量函數(shù)最小時(shí)得到優(yōu)化的骨架。將該算法應(yīng)用于同一模特四個(gè)不同姿勢(shì)和四個(gè)不同模特同一姿勢(shì)的人體點(diǎn)云模型，并與基于拉普拉斯算子的點(diǎn)云收縮的骨架提取方法進(jìn)行了比較。結(jié)果表明，該算法能夠很好地適應(yīng)各種不同姿勢(shì)和體型，模型分叉部位的特征得到更加完善的描述，得到的骨架曲線(xiàn)更接近模型的中軸。

離散Reeb圖；三維人體點(diǎn)云模型；骨架提??；能量函數(shù)最小化

A

TP391

10.3778/j.issn.1002-8331.1210-0243

HOU Pei,TIAN Qingguo,GE Baozhen.Research on method of extracting skeletal curves of 3D human scanning data based on optimizing DRG.Computer Engineering and Applications,2014,50（18）：182-187.

國(guó)家自然科學(xué)基金（No.61027012，No.61177002）。

侯培（1987—），女，碩士研究生，主要研究方向?yàn)槿S數(shù)字化技術(shù)；田慶國(guó)（1973—），男，博士，講師，主要研究方向?yàn)闄C(jī)器視覺(jué)、圖像處理；葛寶臻（1964—），通訊作者，男，博士，教授，主要研究方向?yàn)楣怆姍z測(cè)與處理、激光粒子測(cè)量、激光三維彩色數(shù)字化技術(shù)、數(shù)字全息。E-mail：gebz@tju.edu.cn

2012-10-24

2013-05-07

1002-8331（2014）18-0182-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-05-24，http://www.cnki.net/kcms/detail/11.2127.TP.20130524.1509.001.html