金 凱，石振鋒，牛夏牧

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

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

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

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

三維網(wǎng)格線形骨架提取的本質(zhì)就是源網(wǎng)格上的每個(gè)頂點(diǎn)都將在一定變換下最終變換并聚集到線形骨架上的過程.設(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).記最終的線形骨架為S=Skel(M0)，則基于收縮變換的線形骨架提取技術(shù)的目標(biāo)就是設(shè)計(jì)變換C實(shí)現(xiàn)快速的提取線形骨架.圖1描述了迭代式線形骨架的提取過程.

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

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

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

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

對(duì)于任意給定的頂點(diǎn)vi∈V，第j次收縮變換后的位置為S=Skel(M0)}為頂點(diǎn)v(j)i與最終線形骨架之間的最短距離.在骨架提取過程中，每個(gè)頂點(diǎn)將形成距離序列一般來說，該序列是降序并收斂的，因?yàn)樽罱K每個(gè)頂點(diǎn)都將收斂和變換到線形骨架上，即最終的距離應(yīng)為0.然而，在迭代變換過程中，頂點(diǎn)vi在源網(wǎng)格M0中的位置對(duì)于最終的線形骨架具有非常重要的影響.顯然所有頂點(diǎn)vi的相對(duì)位置關(guān)系即為源模型的拓?fù)浣Y(jié)構(gòu)，而這種相對(duì)位置關(guān)系在迭代收縮變換下將收斂到線形骨架.因此，在本文中，定義頂點(diǎn)的重要性為源網(wǎng)格頂點(diǎn)與最終骨架的最短距離，也稱為頂點(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)該盡可能地提供場景的最大信息，最佳視點(diǎn)將承載該場景中的最大信息量.

給定視點(diǎn)vp，設(shè)F(vp)為該視點(diǎn)下所有可見頂點(diǎn)集合，則F(vp)中所有頂點(diǎn)相對(duì)于骨架的重要度之和定義為該視點(diǎn)vp可從場景中獲得的最大信息量.記最大信息量為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的周圍.設(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ā)生突變，而是平滑的過渡.因此，對(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)迭代初始值，類似于步驟2)中關(guān)于最佳視點(diǎn)的描述，重復(fù)執(zhí)行步驟3)和步驟4).最不利視點(diǎn)的獲取方法類似，不再贅述.圖3給出了基于Loop子分模板的最佳視點(diǎn)迭代求精過程.

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

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

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

由三維模型頂點(diǎn)相對(duì)于其骨架的重要性表示的骨架圖提供了非常重要的拓?fù)渲X信息，圖4給出了恐龍和馬模型的拓?fù)渲X骨架圖和相應(yīng)的骨架.其中:圖4(a)為原始模型;圖4(b)為原始模型相對(duì)于線形骨架而言;圖4(c)為相應(yīng)模型的線形骨架，由原始模型頂點(diǎn)的骨架重要性構(gòu)成的骨架圖譜.在圖4中陰影部分表示該頂點(diǎn)相對(duì)于骨架而言具有較重要的意義，相對(duì)于骨架的位移較大，黑色部分則相反.顯然，依據(jù)拓?fù)渲X理論關(guān)于整體優(yōu)先的論斷來看，不同頂點(diǎn)相對(duì)于骨架的位移是空間拓?fù)渲X在一維的一種表達(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)角度可觀測到的視點(diǎn)信息量，該信息量通過視點(diǎn)球線框圖進(jìn)行描述.

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

為了更清晰地比較基于顯著圖和基于骨架圖的視點(diǎn)選擇，圖6分別給出了3種不同類型的模型在兩種特征下的最佳視點(diǎn)的比較.顯然，基于骨架圖的最佳視點(diǎn)要比基于顯著圖的更有效，能提供更多的信息.在圖6(a)的對(duì)比中，基于顯著圖的最佳視點(diǎn)，由于左前腳對(duì)恐龍的腹部的遮擋，使得該視點(diǎn)對(duì)恐龍的腹部信息不夠豐富.在圖6(b)的對(duì)比中，兩種方式下的最佳視點(diǎn)均提供了較好的視覺信息，圖6(c)中兩種方式下的最佳視點(diǎn)均選擇了人臉的側(cè)面，因?yàn)閭?cè)面的確能提供最大的信息量，但由于該人臉模型的右嘴唇處有一處疤痕，基于顯著圖的最佳視點(diǎn)并不能很好地反映這一事實(shí)，相反的是，基于骨架圖的最佳視點(diǎn)卻很好地提供了這個(gè)重要信息.因此，最佳視點(diǎn)的選擇上，基于骨架圖的視點(diǎn)選擇相比于基于顯著圖的方法能提供更多的視覺信息內(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)提供的視覺信息明顯少于基于顯著圖的方式，也就是說，根據(jù)本文提出的方法得到的最不利視點(diǎn)在視覺內(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)基于三維模型線形骨架，提出了相對(duì)于線形骨架的頂點(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.