幾何信息預測的三角網格模型拓撲壓縮

魏瀟然,耿國華,張雨禾

(西北大學信息科學與技術學院,陜西西安 710127)

幾何信息預測的三角網格模型拓撲壓縮

魏瀟然,耿國華,張雨禾

(西北大學信息科學與技術學院,陜西西安 710127)

為進一步優化三角網格模型拓撲編碼壓縮率,提出一種無損拓撲壓縮算法.該算法首先將三角網格模型剖切成圖,然后將剖切圖表示成三角節點樹,將剖切圖中的三角帶間拓撲結構內蘊在葉子節點、分支節點的鄰接關系中,減少了模型壓縮時需要編碼存儲的網格拓撲信息;最后使用頂點的幾何信息和最小內角最大原則對三角帶內拓撲結構預測,僅對預測錯誤的元素編碼,進一步減少了需要編碼存儲的網格拓撲信息.與已有的壓縮算法對三角網格的遍歷編碼方式相比,該算法不需要遍歷三角網格編碼存儲,僅需要存儲少量網格拓撲結構和預測信息.實驗結果表明,該算法處理各類三角網格模型時壓縮率有較大降低.

拓撲壓縮;預測編碼;三角網格;剖切圖

隨著三維掃描技術的發展和三維模型在各行各業中的廣泛應用,三維模型數據規模和精度日益提高,數據量增長迅速,高精度大型三維模型存儲占用空間大和網絡傳輸緩慢等問題成為了三維模型廣泛應用的瓶頸之一,單純依靠存儲設備擴容以及網絡傳輸技術的不斷更新,不足以從根本上解決問題.因此,必須對三維模型數據進行壓縮,而三角網格模型作為三維模型中最廣泛的表達方式之一,其壓縮技術是數字幾何處理的經典問題.

三角網格模型的壓縮可分為拓撲信息壓縮、幾何信息壓縮與屬性信息壓縮.其中拓撲壓縮算法一直是人們關注的研究問題,已取得了很大進展.在虛擬現實建模語言(Virtual Reality Modeling Language,VRML)標準[1]中,對頂點索引編碼,設模型頂點數為V,頂點平均占用lb V位,三角網格平均占用3 lb V位.為了減少重復頂點引用,文獻[2]將給定的模型沿著選定的邊切割成平面多邊形,然后對切割邊和多邊形進行編碼,該算法不足是在解壓時需要占用大量內存空間.文獻[3]提出EdgeBreaker算法(簡稱EB算法),用CLERS 5種操作符標記流形網格中的三角形,通過對操作符序列進行熵編碼完成壓縮,但其解壓時復雜度非常高.文獻[4]通過分析EB算法獲得操作符之間的關系,用可變模版的算術編碼進一步降低了壓縮率.文獻[5]提出利用頂點度的編碼(簡稱VD算法),利用頂點度的輸出流來存儲拓撲信息,但其只適用于定向流形網格.文獻[6]利用主平面分析將模型分割,對分割后各區域進行編碼,將拓撲壓縮與幾何壓縮結合起來,壓縮率較高,但其分割算法并不總能取得優異的分割區域.文獻[7-9]采用環狀數據結構來表示三角網格模型,以近似漢密爾頓路徑遍歷點,并存儲對應三角形,但其需要實時查詢鄰接三角,其空間復雜度過高.文獻[10]沿哈密頓回路對網格進行以面為單位的拓撲壓縮,采用HETS 4種操作符表示三維模型網格的拓撲信息.文獻[11]將模型壓縮與簡化結合,使得壓縮編碼后的模型更能適應漸進式傳輸的需求.也有學者針對多視點視頻等特定應用對模型進行壓縮編碼[12].

以上各類算法都是以區域生長的方式對拓撲信息進行編碼的,雖然采用了不同的生長策略,但其實質都是以三角網格頂點深度優先遍歷次序訪問網格上的基本元素(點、線或面),需要對網格模型上的每個基本元素進行編碼,阻礙了壓縮率的進一步降低.

為解決這一問題,筆者提出一種利用幾何信息預測的三角網格模型拓撲壓縮算法.該算法將三角網格轉化為剖切圖,并進一步轉化為剖切圖生成樹,將剖切圖中的三角帶間拓撲信息內蘊在樹中,減少了需要存儲的網格拓撲信息,然后利用頂點的幾何信息對三角帶內拓撲結構進行預測,在預測正確率較高的情況下,僅需對少量預測錯誤的網格元素編碼存儲.該算法不需對三角網格所有元素遍歷編碼存儲,大量減少了需要遍歷編碼存儲的拓撲信息.實驗結果表明,文中算法的壓縮率與已有拓撲壓縮算法[3,5]相比,優化效果顯著.

1 幾何信息預測的拓撲壓縮算法

1.1 算法概述

首先構造三角網格模型的頂點生成樹,如圖1(b)所示,之后沿生成樹將模型剖切為一幅有邊界的連通圖,如圖1(c)和圖1(d)所示,將這幅連通圖劃分為三角帶和連接三角帶的分支、葉子節點,以二叉樹的形式表示分支節點與葉子節點,二叉樹任意兩個父子節點之間均可能內蘊一個三角帶,以三角帶鄰接的二叉樹父子節點信息記錄這些三角帶,并利用幾何信息預測三角帶內拓撲結構,最后分別將分支、葉子節點生成的二叉樹和預測三角帶編碼存儲,完成壓縮.表1對文中術語進行定義.

圖1 壓縮流程示意

表1 術語定義

對壓縮方案證明如下:

證明1剖切圖包含原模型所有拓撲信息.沿頂點生成樹切割模型,并沒有切割模型中的任何一條邊,故拓撲信息的邊集沒有刪減,模型所有頂點均為邊上頂點,頂點集也沒有刪減,故剖切圖包含原模型上所有頂點與邊.

證明2獨立三角網格模型剖分圖可劃分為葉子節點、帶節點與分支節點.原模型是獨立模型,不存在孤立三角面片,剖切后圖由一組三角面片組成.若三角形的三條邊都在循環邊界上,那么這個三角形自成為一個封閉的圖,這種三角在頂點生成樹上存在一個回路,而樹不可能存在回路,故不存在這種三角節點.由此可知,利用頂點生成樹剖切網格模型所生成的剖切圖是由葉子節點、帶節點和分支節點組成的.

1.2 算法實現

1.2.1 生成剖切頂點樹

頂點生成樹直接決定剖切圖.由于文中對帶節點預測編碼,故帶節點壓縮比遠高于分支節點和葉子節點.頂點生成樹分支數量決定了葉子節點、分支節點和帶節點數量,故算法需要生成一棵分支盡量少的頂點生成樹.這就將頂點生成樹算法轉化為求解漢密爾頓路徑問題.由于該問題為多項式復雜程度的非確定性完全問題(Non-deterministic Polynomial Complete,NPC),時間復雜度為O(n!×n),沒有快速求解方法,故文中算法僅獲取一棵較優生成樹.文中頂點樹生成算法分為如下步驟:

(1)分層.首先任取模型一頂點作為第1層根頂點,取該頂點所有1鄰域頂點加入第2層,之后取每一層所有頂點的1鄰域中未加入層次的頂點加入下一層,直到所有頂點均加入到層次中.

(2)層次內頂點構造路徑.任取層次內一點根據其與層次內其他點的連接信息生長,生成一條路徑;若層次內還有其他頂點未加入路徑內,則繼續在這些未加入路徑的頂點中選取一點生長路徑,直到層次內所有頂點均加入路徑內,如圖2(b)所示,圖中數字表示路徑所屬層次.

(3)逐層構造頂點生成樹:逐層將每層路徑端點連接至上一層,每條路徑兩個端點存在多種連接方式,取各連接方式中連接上層后生成樹分支最少的,最終連接所有路徑,如圖2(c)所示,構造完成頂點生成樹.

圖2 構造頂點生成樹

1.2.2 剖切圖表示與編碼

頂點生成樹剖切模型生成剖切圖,對剖切圖編碼存儲.其步驟如下:

(1)根據頂點生成樹剖切模型生成剖切圖樹,并添加頂點索引.首先遍歷整個三維模型,將三維模型所有三角網格分類成葉子節點、帶節點與分支節點.之后,從任一葉子節點N出發,搜索與該節點邊相鄰的三角節點.若相鄰所有節點均已在剖分樹中,則停止搜索.相鄰三角節點為帶節點時,若該三角節點與葉子節點N在頂點生成樹上存在相鄰邊,則將其加為后繼節點;相鄰三角節點為葉子節點時,若該三角節點與葉子節點N在頂點生成樹上存在兩條相鄰邊,則將其加為后繼節點;相鄰三角節點為分支節點時,直接將其加入后繼節點.不斷向后搜索,直到所有節點均加入到剖分樹中或所有搜索分支均達到停止條件.生成樹圖如圖3(c)所示.

先序遍歷生成樹,同時為每個三角節點中的頂點添加索引.遍歷時,首先對根節點的頂點依次添加索引,之后對每個三角節點中的未索引頂點依次添加索引.

(2)提取剖切圖樹中分支節點、葉子節點生成二叉樹,對此二叉樹編碼,提取剖切圖樹中帶節點生成三角帶集合.每個葉子節點僅存在一個后繼節點或一個前繼節點,每個分支節點存在兩個后繼節點,故除去所有帶節點后的剖分圖生成樹,是由根節點與連接根節點的一棵二叉樹組成的,如圖3(b)所示,對此二叉樹用前序遍歷方式編碼存儲,每個節點存儲其3個頂點索引.

葉子、分支,分支、分支,葉子、葉子節點兩兩間可能且僅可能存在一條三角帶.根據前序遍歷順序對三角帶編號,如圖3(b)中三角帶編號所示.依次將三角帶加入三角帶集,并存儲三角帶.存儲三角帶時,記錄三角帶兩端相鄰節點和三角帶左右兩邊上的頂點數量.

1.2.3 三角帶預測與編碼

三角網格模型中的三角面片滿足delaunay三角剖分原則,即最小內角最大,根據這一原則進行預測.

圖3 圖的生成樹及其劃分

三角帶中每一個后繼帶節點存在兩種可能的結構,即沿三角帶左邊擴展和沿三角帶右邊擴展,如圖4中的△ABC與△ABD.預測時,比較兩三角形的最小內角.由圖4可知,β′恒小于α,β恒小于α′,故α,α′不可能為最小內角,只需比較β,λ,β′,λ′這4個內角.利用余弦公式計算,取余弦值最大的角為最小內角.不包含最小內角的三角形預測為后繼帶節點.如果預測情況與三角帶中實際連接一致,則預測正確;否則,預測錯誤.預測錯誤標記該節點位置.編碼時只記錄預測錯誤的帶節點所在位置.

沿三角帶一端出發,逐一對三角帶中的帶節點預測編碼,完成三角帶預測.在三角帶預測算法中,對余弦值進行計算時,可將頂點坐標保留若干位小數進行計算,以減少計算量.

圖4 后繼帶節點兩種情況

2 幾何信息預測的拓撲解壓算法

2.1 算法概述

解壓算法的思想是利用剖切圖壓縮信息將拓撲信息還原出來,解壓算法分為以下3步:根據剖切圖生成樹還原分支節點和葉子節點包含的拓撲信息;根據預測三角帶還原所有帶節點的拓撲信息;合并,步提取的拓撲信息,刪除重復拓撲信息,輸出模型.

2.2 算法實現

首先獲取剖切二叉生成樹中蘊含的拓撲信息,將二叉樹中每個節點中的三條邊的拓撲信息記錄即可.然后獲取三角預測帶蘊含的拓撲信息.獲取一條三角帶,根據其索引在二叉樹中搜索其兩端相鄰節點,將兩端相鄰節點加入三角帶.之后從兩端相鄰節點頂點索引小的一端開始,根據預測信息解碼三角帶.根據1.2.3節描述,首先構造其兩個后繼三角,檢查該帶節點的預測信息.若預測正確,則取后繼三角中最小內角大的三角形為后繼帶節點;若預測錯誤,則取后繼三角中最小內角小的三角形為后繼帶節點.后繼節點未索引頂點的索引值為其前繼節點頂點最大索引值加1.

合并提取到的所有拓撲信息,刪除其中重復信息.至此,三角網格模型拓撲信息解壓完成.相較于壓縮流程,解壓流程短,算法簡單,計算量少.

3 實驗結果與分析

將文中算法與VD算法和EB算法進行比較,其中VD算法是目前為止壓縮率最低的算法,EB算法具有低壓縮上限,并且是一種處理各類模型時能得到較穩定壓縮率的算法.實驗選擇了150個三角網格模型,這些模型可以分為4類:規則模型(圖5中bunny,hand),有邊界模型(圖5中head),多虧格模型(圖5中terracotta)和多柄狀結構模型(圖5中dragon).為了便于對比,對實驗模型進行了簡化,模型頂點數為5 000或50 000.

圖5 實驗模型

圖5中列舉其中10個模型,實驗結果如表2所示.表中V表示頂點數,F表示三角面片數,n表示頂點生成樹的分支數量,p表示三角帶預測錯誤率.

表2 各種壓縮算法性能比較

實驗結果顯示,文中算法壓縮率為1.34～2.12 bit/點,均值為1.73 bit/點;VD算法壓縮率為1.48～2.73 bit/點,均值為2.1 bit/點;EB算法壓縮率為2.16～3.23 bit/點,均值為2.56 bit/點.文中算法處理各模型壓縮率均值低于VD和EB算法壓縮率均值.

實驗結果中,n與V的比值很小(5 000頂點時比值分布在0.01～0.02范圍,50 000頂點時比值分布在0.004～0.008范圍),并且隨頂點總數增大而減小.這表明隨著頂點數量增加,文中算法壓縮效果將提高.實驗中,V為5 000時,n分布在50～100之間;V為50 000時,n分布在200～400之間.頂點數為5 000時,實驗壓縮率為1.52～2.12;頂點數為50 000時,實驗壓縮率為1.34～2.06.實驗結果證明,隨著模型精度提升,頂點增多,文中算法壓縮效果也會隨著提升.

相較規則模型與有邊界模型,多虧格和多柄狀結構模型n較大,壓縮效果略差,但壓縮率仍低于VD和EB算法.針對各類模型算法預測錯誤率集中在3%～8%之間,實驗結果統計表明,各類模型三角帶預測錯誤率沒有明顯傾向性變化.

4 結束語

文中提出了一種三角網格模型無損拓撲壓縮算法,用剖切圖生成樹表示模型,將三角帶內蘊在剖切圖生成樹中,并利用幾何信息預測三角帶中的拓撲結構.與傳統壓縮算法遍歷三角網格編碼方式相比,文中算法無需遍歷編碼所有三角網格,僅需編碼少量三角網格.實驗結果表明,算法對各類模型均能夠獲得較低的壓縮率.該算法有以下優點:不需要遍歷三角網格編碼存儲,壓縮率低;三角帶預測編碼時預測正確率高,大量減少了需存儲的拓撲信息;大量拓撲信息內蘊在剖切圖二叉樹結構中,避免了拓撲信息的重復存儲.

頂點生成樹的分支數量是影響壓縮率的一個重要因素,另外,頂點生成樹也可表達各頂點間的位置鄰近關系,故下一步的工作可以如下展開:尋求更優的建立頂點生成樹算法;利用算法中生成的頂點生成樹,對幾何信息進行預測,降低幾何信息壓縮率.

[1]Carey R,Bell G,Marrin C.ISO/IEC 14772-1:1997 Virtual Reality Modeling Language(VRML97)[S].The VRML Consortium Incorporated,1997:34.

[2]Taubin G,Rossignac J.Geometric Compression through Topological Surgery[J].ACM Transactions on Graphics, 1998,17(2):84-115.

[3]Rossignac J.Edgebreaker:Connectivity Compression for Triangle Meshes[J].IEEE Transactions on Visualization and Computer Graphics,1999,5(1):47-61.

[4]劉迎,劉學慧,吳恩華.基于可變模版的三角網格拓撲壓縮[J].軟件學報,2008,19(04):1015-1025. Liu Ying,Liu Xuehui,Wu Enhua.Variable-code-mode-based Connectivity Compression for Triangular Meshes[J]. Journal of Software,2008,19(4):1015-1025.

[5]Alliez P,Desbrun M.Valence-driven Connectivity Encoding for 3D Meshes[J].Computer Graphics Forum,2001,20 (3):480-489.

[6]Cheng S C,Kuo C T,Wu D C.A Novel 3D Mesh Compression Using Mesh Segmentation with Multiple Principal Plane Analysis[J].Pattern Recognition,2010,43(1):267-279.

[7]Gurung T,Luffel M,Lindstrom P,et al.LR:Compact Connectivity Representation for Triangle Meshes[J].ACM Transactions on Graphics,2011,30(4):1-8.

[8]Gurung T,Luffel M,Lindstrom P,et al.Zipper:A Compact Connectivity Data Structure for Triangle Meshes[J]. Computer-Aided Design,2013,45(2):262-269.

[9]Luffel M,Gurung T,Lindstrom P,et al.Grouper:A Compact,Streamable Triangle Mesh Data Structure[J].IEEE Transactions on Visualization and Computer Graphics,2014,20(1):84-98.

[10]張潔,吳佳澤,鄭昌文.應用哈密頓回路的三角網格拓撲壓縮[J].計算機輔助設計與圖形學學報,2013,25(5):697-707. Zhang Jie,Wu Jiaze,Zheng Changwen.Connectivity Compression of Thriangle Meshes Based on Hamilton Cycle[J]. Journal of Computer-Aided Design&Computer Graphics,2013,25(5):697-707.

[11]Maglo A,Grimstead I,Hudelot C.POMAR:Compression of Progressive Oriented Meshes Accessible Randomly[J]. Computers&Graphics,2013,37(6):743-752.

[12]Vetro A,Frossard P,Lee S,et al.Introduction to the Special Section on 3D Representation,Compression,and Rendering[J].IEEE Transactions on Image Processing,2013,22(9):3513-3516.

(編輯:李恩科)

Connectivity compression of triangle meshes based on geometric parameter predict

WEI Xiaoran,GENG Guohua,ZHANG Yuhe
(School of Information Science and Technology,Northwestern Univ.,Xi’an 710127,China)

An efficient encoding algorithm for lossless compression of triangle mesh connectivity is presented to further optimize the compression ratio.The algorithm firstly cuts a given mesh into a cutaway graph,then uses a triangle nodes tree to present the graph,containing the triangle strips topology information on the graph in the adjacency relationships between the leaf nodes and the branch nodes, reducing the mesh topology information needed to be encoded.Finally,we use the minimum interior angle maximum principle to predict the internal topology of the triangle strips,only encoding the prediction error elements,thus further reducing the information needed to be encoded.Compared with the current compression algorithms,this algorithm does not traverse the triangular mesh,only encoding and storing a small amount of mesh topology information and prediction information.Experimental results show that the algorithm can greatly reduce the compression ratios and process various triangle meshes.

connectivity compression;predictive encoding;triangle mesh;cutaway graph

TP391

A

1001-2400(2015)05-0194-06

2014-12-25

國家自然科學基金資助項目(61373117,61172170)

魏瀟然(1987-),男,西北大學博士研究生,E-mail:155259476@qq.com.

10.3969/j.issn.1001-2400.2015.05.032