基于頂點重要性骨架圖的視點快速選擇算法

金 凱，石振鋒，牛夏牧

(1.哈爾濱工業大學建筑學院，150001哈爾濱;2.哈爾濱工業大學數學系，150001哈爾濱;3.哈爾濱工業大學計算機科學與技術學院，150001哈爾濱)

近年來，形狀分析與處理技術一直是計算機圖形學等領域的研究熱點，其主要應用包括在計算機三維動畫［1-2］、三維模型分割［3］、形狀配準與檢索［4-5］、骨架提?。?］和曲面重構等.形狀的描述與表達是計算機圖形學和三維模型可視化研究中的核心問題.然而，給出一種用于定義形狀和描述形狀的簡單而又有效的方法卻是非常難的.線形骨架是三維模型的幾何與拓撲結構的一維簡潔表示方式，已被廣泛應用于三維模型的形狀分析和處理.

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

本文首先根據三維模型的骨架定義了一種新的骨架圖，用于描述每個頂點相對于最終骨架的重要性度量，然后定義了視點信息量用于視點選擇的優先級度量，最后提出了一種基于迭代式子分方式快速選擇最佳和最差視點的計算方法.實驗結果表明，本文提出的骨架圖方法是合理的，基于骨架圖的視點信息量度量是可行的，迭代式子分方式能準確、快速地實現最佳和最差視點的選擇.

1 三維網格頂點重要性模型

1.1 三維網格模型骨架提取算法

線形骨架為三維模型全局形狀和拓撲結構的描述提供了非常有利的一種表示方法.從人類視覺感知理論出發，根據拓撲知覺理論中人類視覺的整體優先原則［11］，線形骨架用于視點選擇、形狀分析及處理等是可行的.現有的骨架提取方法可以分為兩種主要類型:基于體積的和基于幾何的骨架提取方法.

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

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

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

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

1.2 三維網格頂點重要性

對于任意給定的頂點vi∈V，第j次收縮變換后的位置為S=Skel(M0)}為頂點v(j)i與最終線形骨架之間的最短距離.在骨架提取過程中，每個頂點將形成距離序列一般來說，該序列是降序并收斂的，因為最終每個頂點都將收斂和變換到線形骨架上，即最終的距離應為0.然而，在迭代變換過程中，頂點vi在源網格M0中的位置對于最終的線形骨架具有非常重要的影響.顯然所有頂點vi的相對位置關系即為源模型的拓撲結構，而這種相對位置關系在迭代收縮變換下將收斂到線形骨架.因此，在本文中，定義頂點的重要性為源網格頂點與最終骨架的最短距離，也稱為頂點相對于骨架的的初始位移.記頂點vi相對于骨架的重要度為Sig(vi)，則

2 三維網格模型視點快速選擇算法

2.1 視點信息量

通常可以認為一個好的視點應該盡可能地提供場景的最大信息，最佳視點將承載該場景中的最大信息量.

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

其中:最佳視點vpbest和最不利視點vpworst分別定義為

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

2.2 三維網格模型視點快速選擇算法

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

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

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

顯然，最終的最佳視點和最不利視點都將分別在v(0)best和v(0)worst的周圍.設N(v(0)best)和N(v(0)worst)分別為v(0)best和v(0)worst1-鄰域，則最佳視點和最不利視點必將落在N(v(0)best)和N(v(0)worst)所圍成的區域內或其區域的鄰域內.

3)考慮到視點信息量在三維空間中是連續變化的(因為三維空間的連續相關性)，因此，當視點從v(0)best移至最佳視點vpbest和從v(0)worst移至最不利視點vpworst時，視點信息量不會發生突變，而是平滑的過渡.因此，對中的每個三角形進行剖分，剖分規則采用Loop子分模板［13］.

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

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

3 實驗結果及分析

3.1 三維網格模型骨架圖

由三維模型頂點相對于其骨架的重要性表示的骨架圖提供了非常重要的拓撲知覺信息，圖4給出了恐龍和馬模型的拓撲知覺骨架圖和相應的骨架.其中:圖4(a)為原始模型;圖4(b)為原始模型相對于線形骨架而言;圖4(c)為相應模型的線形骨架，由原始模型頂點的骨架重要性構成的骨架圖譜.在圖4中陰影部分表示該頂點相對于骨架而言具有較重要的意義，相對于骨架的位移較大，黑色部分則相反.顯然，依據拓撲知覺理論關于整體優先的論斷來看，不同頂點相對于骨架的位移是空間拓撲知覺在一維的一種表達，這種表達是合理的.本文將在以下試驗中進一步從視點選擇的角度驗證骨架圖譜的合理性和準確性.

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

3.2 三維網格模型最佳與最不利視點選擇

為了驗證骨架圖譜的合理性和準確性，本文實現了基于顯著度的視點選擇和提出的基于骨架圖譜的視點選擇.圖5描述了從不同視點角度可觀測到的視點信息量，該信息量通過視點球線框圖進行描述.

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

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

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

圖6 基于顯著圖和骨架圖的最佳視點比較

圖7 基于顯著圖和骨架圖的最不利視點比較

3.3 三維網格模型視點快速選擇運行時間分析

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

表1 基于骨架圖的視點快速選擇方法運行時間分析s

4 結論

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

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

3)基于Loop子分模板，實現了最佳視點和最不利視點的快速選擇，實驗結果表明本文的方法要優于基于顯著圖的視點選擇方法.

［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，FEIXAS 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.