基于頂點(diǎn)重要性骨架圖的視點(diǎn)快速選擇算法

金 凱，石振鋒，牛夏牧

(1.哈爾濱工業(yè)大學(xué)建筑學(xué)院，150001哈爾濱;2.哈爾濱工業(yè)大學(xué)數(shù)學(xué)系，150001哈爾濱;3.哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱)

近年來(lái)，形狀分析與處理技術(shù)一直是計(jì)算機(jī)圖形學(xué)等領(lǐng)域的研究熱點(diǎn)，其主要應(yīng)用包括在計(jì)算機(jī)三維動(dòng)畫(huà)［1-2］、三維模型分割［3］、形狀配準(zhǔn)與檢索［4-5］、骨架提?。?］和曲面重構(gòu)等.形狀的描述與表達(dá)是計(jì)算機(jī)圖形學(xué)和三維模型可視化研究中的核心問(wèn)題.然而，給出一種用于定義形狀和描述形狀的簡(jiǎn)單而又有效的方法卻是非常難的.線(xiàn)形骨架是三維模型的幾何與拓?fù)浣Y(jié)構(gòu)的一維簡(jiǎn)潔表示方式，已被廣泛應(yīng)用于三維模型的形狀分析和處理.

選擇一個(gè)好的視點(diǎn)將對(duì)三維模型的形狀分析與處理、圖形繪制、場(chǎng)景理解、場(chǎng)景優(yōu)化布局等具有非常重要的意義.近年來(lái)，視點(diǎn)選擇已經(jīng)成為計(jì)算機(jī)圖形學(xué)研究中一個(gè)非常重要和活躍的分支.國(guó)內(nèi)外許多研究者提出了自動(dòng)選擇視點(diǎn)或視點(diǎn)集序列的方法.Gooch等［7］提出了一個(gè)可計(jì)算的顯著度模型，并用于自動(dòng)計(jì)算三維模型的初始視點(diǎn)集.Vázquez等［8］利用香農(nóng)熵定義了視點(diǎn)熵，并利用它來(lái)評(píng)價(jià)一個(gè)視點(diǎn)的好壞，提出了選擇N個(gè)最佳視點(diǎn)構(gòu)成最小最佳視點(diǎn)集，并用于場(chǎng)景理解等應(yīng)用.受人類(lèi)視覺(jué)系統(tǒng)低層線(xiàn)索的啟發(fā)，基于人類(lèi)視覺(jué)系統(tǒng)注意力機(jī)制.Lee等［9］基于高斯平均曲率，利用中心-周?chē)鷻C(jī)制構(gòu)造濾波器，提出了一種顯著度計(jì)算模型，用于構(gòu)建三維模型的感知重要性區(qū)域.對(duì)于給定的視點(diǎn)，研究者們將在該視點(diǎn)下三維模型中所有可見(jiàn)頂點(diǎn)的顯著度之和定義為該視點(diǎn)的重要性.利用基于梯度下降的啟發(fā)式優(yōu)化方法，快速地根據(jù)視點(diǎn)的重要性來(lái)選擇最佳視點(diǎn).Feixas等［10］在已有研究基礎(chǔ)上，定義了一種新的基于多邊形互信息的三維模型顯著度，并建立了統(tǒng)一的信息論框架用于視點(diǎn)選擇和顯著度應(yīng)用.然而，網(wǎng)格模型顯著度僅能從視覺(jué)注意力的角度刻畫(huà)三維模型局部視覺(jué)重要性.因此，顯著度不足以描述三維目標(biāo)的整體拓?fù)涮匦?，基于顯著圖的視點(diǎn)選擇也不足以用于三維模型的形狀分析.

本文首先根據(jù)三維模型的骨架定義了一種新的骨架圖，用于描述每個(gè)頂點(diǎn)相對(duì)于最終骨架的重要性度量，然后定義了視點(diǎn)信息量用于視點(diǎn)選擇的優(yōu)先級(jí)度量，最后提出了一種基于迭代式子分方式快速選擇最佳和最差視點(diǎn)的計(jì)算方法.實(shí)驗(yàn)結(jié)果表明，本文提出的骨架圖方法是合理的，基于骨架圖的視點(diǎn)信息量度量是可行的，迭代式子分方式能準(zhǔn)確、快速地實(shí)現(xiàn)最佳和最差視點(diǎn)的選擇.

1 三維網(wǎng)格頂點(diǎn)重要性模型

1.1 三維網(wǎng)格模型骨架提取算法

線(xiàn)形骨架為三維模型全局形狀和拓?fù)浣Y(jié)構(gòu)的描述提供了非常有利的一種表示方法.從人類(lèi)視覺(jué)感知理論出發(fā)，根據(jù)拓?fù)渲X(jué)理論中人類(lèi)視覺(jué)的整體優(yōu)先原則［11］，線(xiàn)形骨架用于視點(diǎn)選擇、形狀分析及處理等是可行的.現(xiàn)有的骨架提取方法可以分為兩種主要類(lèi)型:基于體積的和基于幾何的骨架提取方法.

三維網(wǎng)格線(xiàn)形骨架提取的本質(zhì)就是源網(wǎng)格上的每個(gè)頂點(diǎn)都將在一定變換下最終變換并聚集到線(xiàn)形骨架上的過(guò)程.設(shè)源網(wǎng)格M0有N個(gè)頂點(diǎn)組成，記為V={vi｜vi∈R3，1≤i≤N}.設(shè):C為變換;Cj為第j次迭代變換.因此，每個(gè)頂點(diǎn)vi在每次變換下都將得到新的坐標(biāo)，記為網(wǎng)格變換序列記為{Mj={Cj(Mj-1).記最終的線(xiàn)形骨架為S=Skel(M0)，則基于收縮變換的線(xiàn)形骨架提取技術(shù)的目標(biāo)就是設(shè)計(jì)變換C實(shí)現(xiàn)快速的提取線(xiàn)形骨架.圖1描述了迭代式線(xiàn)形骨架的提取過(guò)程.

圖1 基于迭代收縮操作的三維網(wǎng)格模型骨架提取方法

Laplacian收縮變換提供了一種快速有效的工具.文獻(xiàn)［1］對(duì)三維網(wǎng)格模型實(shí)施隱式Laplacian光滑化收縮操作獲得最終的線(xiàn)形骨架.Cao等［12］基于文獻(xiàn)［1］的基礎(chǔ)上，在點(diǎn)云數(shù)據(jù)上提出了一種線(xiàn)形骨架提取算法.本文實(shí)現(xiàn)了這兩種線(xiàn)形骨架提取算法，圖2給出了基于Laplacian光滑化收縮操作得到最終骨架的過(guò)程.在本文中選擇文獻(xiàn)［12］提出的線(xiàn)形骨架提取算法.

圖2 基于Laplacian迭代收縮的三維網(wǎng)格模型骨架提取過(guò)程

1.2 三維網(wǎng)格頂點(diǎn)重要性

對(duì)于任意給定的頂點(diǎn)vi∈V，第j次收縮變換后的位置為S=Skel(M0)}為頂點(diǎn)v(j)i與最終線(xiàn)形骨架之間的最短距離.在骨架提取過(guò)程中，每個(gè)頂點(diǎn)將形成距離序列一般來(lái)說(shuō)，該序列是降序并收斂的，因?yàn)樽罱K每個(gè)頂點(diǎn)都將收斂和變換到線(xiàn)形骨架上，即最終的距離應(yīng)為0.然而，在迭代變換過(guò)程中，頂點(diǎn)vi在源網(wǎng)格M0中的位置對(duì)于最終的線(xiàn)形骨架具有非常重要的影響.顯然所有頂點(diǎn)vi的相對(duì)位置關(guān)系即為源模型的拓?fù)浣Y(jié)構(gòu)，而這種相對(duì)位置關(guān)系在迭代收縮變換下將收斂到線(xiàn)形骨架.因此，在本文中，定義頂點(diǎn)的重要性為源網(wǎng)格頂點(diǎn)與最終骨架的最短距離，也稱(chēng)為頂點(diǎn)相對(duì)于骨架的的初始位移.記頂點(diǎn)vi相對(duì)于骨架的重要度為Sig(vi)，則

2 三維網(wǎng)格模型視點(diǎn)快速選擇算法

2.1 視點(diǎn)信息量

通?？梢哉J(rèn)為一個(gè)好的視點(diǎn)應(yīng)該盡可能地提供場(chǎng)景的最大信息，最佳視點(diǎn)將承載該場(chǎng)景中的最大信息量.

給定視點(diǎn)vp，設(shè)F(vp)為該視點(diǎn)下所有可見(jiàn)頂點(diǎn)集合，則F(vp)中所有頂點(diǎn)相對(duì)于骨架的重要度之和定義為該視點(diǎn)vp可從場(chǎng)景中獲得的最大信息量.記最大信息量為Sigsum(vp)，則

其中:最佳視點(diǎn)vpbest和最不利視點(diǎn)vpworst分別定義為

求解最佳視點(diǎn)vpbest和最不利視點(diǎn)vpworst的方法很多，其中一種可能就是枚舉所有視點(diǎn)后，從中選擇最大和最小值分別對(duì)應(yīng)的視點(diǎn)作為最佳和最不利視點(diǎn).然而，這將非常費(fèi)時(shí)，尤其是三維模型的頂點(diǎn)數(shù)較多時(shí).在本文中提出了基于迭代求精方式快速獲取最佳和最不利視點(diǎn)的方法.

2.2 三維網(wǎng)格模型視點(diǎn)快速選擇算法

為提高獲取最佳視點(diǎn)和最不利視點(diǎn)的計(jì)算效率，本文基于迭代方式逐步求精地選擇最佳視點(diǎn)和最不利視點(diǎn).算法具體描述為:

1)在三維模型的三角化包圍球或立方體包圍盒上任意采樣N個(gè)頂點(diǎn)作為初始視點(diǎn).如果以包圍球采樣，則通常盡可能保證初始視點(diǎn)的采樣均勻.如果是立方體包圍盒，則直接以包圍盒的8個(gè)頂點(diǎn)作為初始視點(diǎn).

2)記N個(gè)視點(diǎn)集合為vp，依次計(jì)算vp中N個(gè)視點(diǎn)的信息量.假設(shè)v(0)best和v(0)worst分別為N個(gè)視點(diǎn)中的最佳視點(diǎn)和最不利視點(diǎn)，即

顯然，最終的最佳視點(diǎn)和最不利視點(diǎn)都將分別在v(0)best和v(0)worst的周?chē)?設(shè)N(v(0)best)和N(v(0)worst)分別為v(0)best和v(0)worst1-鄰域，則最佳視點(diǎn)和最不利視點(diǎn)必將落在N(v(0)best)和N(v(0)worst)所圍成的區(qū)域內(nèi)或其區(qū)域的鄰域內(nèi).

3)考慮到視點(diǎn)信息量在三維空間中是連續(xù)變化的(因?yàn)槿S空間的連續(xù)相關(guān)性)，因此，當(dāng)視點(diǎn)從v(0)best移至最佳視點(diǎn)vpbest和從v(0)worst移至最不利視點(diǎn)vpworst時(shí)，視點(diǎn)信息量不會(huì)發(fā)生突變，而是平滑的過(guò)渡.因此，對(duì)中的每個(gè)三角形進(jìn)行剖分，剖分規(guī)則采用Loop子分模板［13］.

4)記~Nv0為剖分后的新鄰域頂點(diǎn)集合，則對(duì)中的每個(gè)頂點(diǎn)計(jì)算視點(diǎn)信息量.以最佳視點(diǎn)為例，如果所有新領(lǐng)域頂點(diǎn)的視點(diǎn)信息量均則將作為新的最佳視點(diǎn)迭代初始值，重復(fù)執(zhí)行步驟3)和步驟4).否則，設(shè)作為視點(diǎn)時(shí)取得最大視點(diǎn)信息量，則將作為新的最佳視點(diǎn)迭代初始值，類(lèi)似于步驟2)中關(guān)于最佳視點(diǎn)的描述，重復(fù)執(zhí)行步驟3)和步驟4).最不利視點(diǎn)的獲取方法類(lèi)似，不再贅述.圖3給出了基于Loop子分模板的最佳視點(diǎn)迭代求精過(guò)程.

5)設(shè)當(dāng)前第k次迭代求精時(shí)的最佳視點(diǎn)位置為下一次迭代求精后的最佳視點(diǎn)位置為則給定閾值ε，當(dāng)時(shí)，則可以終止最佳視點(diǎn)的迭代過(guò)程.最不利視點(diǎn)的情況類(lèi)似.

3 實(shí)驗(yàn)結(jié)果及分析

3.1 三維網(wǎng)格模型骨架圖

由三維模型頂點(diǎn)相對(duì)于其骨架的重要性表示的骨架圖提供了非常重要的拓?fù)渲X(jué)信息，圖4給出了恐龍和馬模型的拓?fù)渲X(jué)骨架圖和相應(yīng)的骨架.其中:圖4(a)為原始模型;圖4(b)為原始模型相對(duì)于線(xiàn)形骨架而言;圖4(c)為相應(yīng)模型的線(xiàn)形骨架，由原始模型頂點(diǎn)的骨架重要性構(gòu)成的骨架圖譜.在圖4中陰影部分表示該頂點(diǎn)相對(duì)于骨架而言具有較重要的意義，相對(duì)于骨架的位移較大，黑色部分則相反.顯然，依據(jù)拓?fù)渲X(jué)理論關(guān)于整體優(yōu)先的論斷來(lái)看，不同頂點(diǎn)相對(duì)于骨架的位移是空間拓?fù)渲X(jué)在一維的一種表達(dá)，這種表達(dá)是合理的.本文將在以下試驗(yàn)中進(jìn)一步從視點(diǎn)選擇的角度驗(yàn)證骨架圖譜的合理性和準(zhǔn)確性.

圖4 三維模型骨架圖及骨架

3.2 三維網(wǎng)格模型最佳與最不利視點(diǎn)選擇

為了驗(yàn)證骨架圖譜的合理性和準(zhǔn)確性，本文實(shí)現(xiàn)了基于顯著度的視點(diǎn)選擇和提出的基于骨架圖譜的視點(diǎn)選擇.圖5描述了從不同視點(diǎn)角度可觀(guān)測(cè)到的視點(diǎn)信息量，該信息量通過(guò)視點(diǎn)球線(xiàn)框圖進(jìn)行描述.

圖5 恐龍模型基于顯著度和骨架圖譜的視點(diǎn)信息量線(xiàn)框圖

為了更清晰地比較基于顯著圖和基于骨架圖的視點(diǎn)選擇，圖6分別給出了3種不同類(lèi)型的模型在兩種特征下的最佳視點(diǎn)的比較.顯然，基于骨架圖的最佳視點(diǎn)要比基于顯著圖的更有效，能提供更多的信息.在圖6(a)的對(duì)比中，基于顯著圖的最佳視點(diǎn)，由于左前腳對(duì)恐龍的腹部的遮擋，使得該視點(diǎn)對(duì)恐龍的腹部信息不夠豐富.在圖6(b)的對(duì)比中，兩種方式下的最佳視點(diǎn)均提供了較好的視覺(jué)信息，圖6(c)中兩種方式下的最佳視點(diǎn)均選擇了人臉的側(cè)面，因?yàn)閭?cè)面的確能提供最大的信息量，但由于該人臉模型的右嘴唇處有一處疤痕，基于顯著圖的最佳視點(diǎn)并不能很好地反映這一事實(shí)，相反的是，基于骨架圖的最佳視點(diǎn)卻很好地提供了這個(gè)重要信息.因此，最佳視點(diǎn)的選擇上，基于骨架圖的視點(diǎn)選擇相比于基于顯著圖的方法能提供更多的視覺(jué)信息內(nèi)容，要優(yōu)于基于顯著圖的視點(diǎn)選擇方法.

在本文中，也實(shí)現(xiàn)了最不利視點(diǎn)的選擇，圖7給出了兩種方式下的最不利視點(diǎn)的比較，其中圖7(a)，(b)分別為基于顯著圖和基于骨架圖的最不利視點(diǎn)的選擇結(jié)果.從圖7上可以看出，對(duì)于恐龍模型和人臉模型而言，兩種方法選擇的最不利視點(diǎn)均相同，但對(duì)于CAD模型，基于骨架圖的最不利視點(diǎn)提供的視覺(jué)信息明顯少于基于顯著圖的方式，也就是說(shuō)，根據(jù)本文提出的方法得到的最不利視點(diǎn)在視覺(jué)內(nèi)容信息上提供得比基于顯著圖的更少，即本文的方法能選擇更為不利的視點(diǎn).

圖6 基于顯著圖和骨架圖的最佳視點(diǎn)比較

圖7 基于顯著圖和骨架圖的最不利視點(diǎn)比較

3.3 三維網(wǎng)格模型視點(diǎn)快速選擇運(yùn)行時(shí)間分析

為了驗(yàn)證和分析本文提出的基于Loop子分模板以迭代求精方式獲取最佳視點(diǎn)的運(yùn)行時(shí)間，在本實(shí)驗(yàn)中選擇了立方體包圍盒，即初始視點(diǎn)有8個(gè)頂點(diǎn)構(gòu)成，設(shè)定迭代子分終止時(shí)的閾值為0.1.算法運(yùn)行的操作系統(tǒng)為Windows7，處理器為Pentium?雙核T4400，2.2 GHz，內(nèi)存為4 GB.表1給出了本文算法的具體運(yùn)行時(shí)間，從表1中數(shù)據(jù)可以看出本文提出的基于Loop子分模板迭代求精的視點(diǎn)選擇算法運(yùn)行時(shí)間效率高，能快速實(shí)現(xiàn)最佳視點(diǎn)或最不利視點(diǎn)的選擇.

表1 基于骨架圖的視點(diǎn)快速選擇方法運(yùn)行時(shí)間分析s

4 結(jié)論

1)基于三維模型線(xiàn)形骨架，提出了相對(duì)于線(xiàn)形骨架的頂點(diǎn)重要性的定義，并以此定義為三維模型的骨架圖譜.

2)基于骨架圖譜，定義了視點(diǎn)信息量，并以此作為視點(diǎn)選擇的依據(jù).

3)基于Loop子分模板，實(shí)現(xiàn)了最佳視點(diǎn)和最不利視點(diǎn)的快速選擇，實(shí)驗(yàn)結(jié)果表明本文的方法要優(yōu)于基于顯著圖的視點(diǎn)選擇方法.

［1］AU O K C，TAI C L，CHU H K，et al.Skeleton extraction by mesh contraction［J］.ACM Transactions on Graphics，2008，27(3):44.

［2］WADE L，PARENT R E.Automated generation of control skeletons for use in animation［J］.Visual Computer，2002，18(2):97-110.

［3］DEY T K，SUN J.Defining and computing curve-skeletons with medial geodesic function［C］//Proceedings of the Fourth Eurographics Symposium on Geometry Processing.Switzerland:Eurographics Association Aire-la-Ville，2006:143-152.

［4］BIASOTTI S，MARINI S，MORTARA M，et al.3D shape matching through topological structures［J］.Discrete Geometry for Computer Imagery，2003，2886:194-203.

［5］SUNDAR H，SILVER D，GAGVANI N，et al.Skeleton based shape matching and retrieval［C］//Proceedings of the Shape Modeling International.Washington，DC:IEEE Computer Society，2003:130-139.

［6］TAGLIASACCHI A，ZHANG H，COHEN-OR D.Curve skeleton extraction from incomplete point cloud［J］.ACM Transactions on Graphics，2009，28(3):71.

［7］GOOCH B，REINHARD E，MOULDING C，et al.Artistic composition for image creation［C］//Proceedings of the 12th Eurographics Workshop on Rendering Techniques.London UK:Springer-Verlag，2001:83-88.

［8］VáZQUEZ P P，F(xiàn)EIXAS M，SBERT M，et al.Viewpoint selection using viewpoint entropy［C］//Proceedings of the Vision Modeling and Visualization Conference.［S.l.］:Aka GmbH，2001:273-280.

［9］LEE C H，VARSHNEY A，JACOBS D W.Mesh saliency［J］.ACM Transactions on Graphics，2005，24(3):659-666.

［10］FEIXAS M，SBERT M，GONZáLEZ F.A unified information-theoretic framework for viewpoint selection and mesh saliency［J］.ACM Transactions on Applied Perception，2009，6(1):1.

［11］NAVON D.Forest before trees:the procedence of global features in visual perception［J］.Cognitive Psychology，1977，9(3):353-383.

［12］CAO J，TAGLIASACCHI A，OLSON M，et al.Point cloud skeletons via laplacian-based contraction［C］//Proceedings of Shape Modeling International.Washington，DC:IEEE Computer Society，2010:187-197.

［13］LOOP C T.Smooth subdivision surface based on triangle［D］.Salt Lake City:University of Utah，1987.