魏瀟然,耿國華,張雨禾

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

幾何信息預(yù)測的三角網(wǎng)格模型拓撲壓縮

魏瀟然,耿國華,張雨禾

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

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

拓撲壓縮;預(yù)測編碼;三角網(wǎng)格;剖切圖

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

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

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

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

1 幾何信息預(yù)測的拓撲壓縮算法

1.1 算法概述

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

圖1 壓縮流程示意

表1 術(shù)語定義

對壓縮方案證明如下:

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

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

1.2 算法實現(xiàn)

1.2.1 生成剖切頂點樹

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

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

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

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

圖2 構(gòu)造頂點生成樹

1.2.2 剖切圖表示與編碼

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

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

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

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

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

1.2.3 三角帶預(yù)測與編碼

三角網(wǎng)格模型中的三角面片滿足delaunay三角剖分原則,即最小內(nèi)角最大,根據(jù)這一原則進行預(yù)測.

圖3 圖的生成樹及其劃分

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

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

圖4 后繼帶節(jié)點兩種情況

2 幾何信息預(yù)測的拓撲解壓算法

2.1 算法概述

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

2.2 算法實現(xiàn)

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

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

3 實驗結(jié)果與分析

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

圖5 實驗?zāi)Ｐ?/p>

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

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

實驗結(jié)果顯示,文中算法壓縮率為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算法壓縮率均值.

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

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

4 結(jié)束語

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

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

[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]劉迎,劉學慧,吳恩華.基于可變模版的三角網(wǎng)格拓撲壓縮[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]張潔,吳佳澤,鄭昌文.應(yīng)用哈密頓回路的三角網(wǎng)格拓撲壓縮[J].計算機輔助設(shè)計與圖形學學報,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