一種基于蟻群優(yōu)化的網(wǎng)格分割方法

張耀楠,周 升,牛樂(lè)川,王元一

(1.西安思源學(xué)院 電子信息工程學(xué)院,西安 710038; 2.東北大學(xué) 中荷生物醫(yī)學(xué)與信息工程學(xué)院,沈陽(yáng) 110169)

0 概述

近年來(lái),由于數(shù)碼照相機(jī)、數(shù)碼攝像機(jī)、醫(yī)學(xué)成像、遙感成像、工程成像等技術(shù)的快速發(fā)展和普遍應(yīng)用,產(chǎn)生了大量的三維圖像和影像數(shù)據(jù)。通過(guò)圖像處理和分析會(huì)形成大量的自然物體和人體器官的三維網(wǎng)格數(shù)據(jù)。一般而言,這些三維網(wǎng)格數(shù)據(jù)還需要做進(jìn)一步的處理才能被特定的應(yīng)用使用。 網(wǎng)格分割是其中重要的一步,它將三維網(wǎng)格數(shù)據(jù)按照一定的標(biāo)準(zhǔn)分離成部件或曲面片,為以后的壓縮、識(shí)別、檢索、分類等提供基礎(chǔ)。

圖像分割領(lǐng)域現(xiàn)已存在較多方法,但網(wǎng)格分割研究相對(duì)文獻(xiàn)較少。文獻(xiàn)[1]從分割類型及策略、算法復(fù)雜度及范圍等方面對(duì)典型的網(wǎng)格分割算法進(jìn)行了比較。文獻(xiàn)[2]提出一種基于高斯映射的法向聚類CAD網(wǎng)格分割方法。文獻(xiàn)[3]通過(guò)熱核函數(shù)來(lái)描述曲面的屬性。文獻(xiàn)[4]通過(guò)近似矩陣來(lái)比較2塊曲面,然后通過(guò)聚類進(jìn)行分割。文獻(xiàn)[5]對(duì)形狀比較的度量方法進(jìn)行了綜述。文獻(xiàn)[6]中方法是完全無(wú)監(jiān)督的,并可表示為一個(gè)整數(shù)二次規(guī)劃的聯(lián)合分割問(wèn)題。文獻(xiàn)[7]中引入一組無(wú)監(jiān)督的協(xié)同層次分析,目的在于發(fā)現(xiàn)分層結(jié)構(gòu)和揭示形狀部件之間的關(guān)系。文獻(xiàn)[8]以過(guò)分割結(jié)果作為起點(diǎn),然后通過(guò)統(tǒng)計(jì)聚類來(lái)描述集群,同時(shí)采用多標(biāo)簽優(yōu)化改善共分割。文獻(xiàn)[9]提出使用深度學(xué)習(xí)分割3D形狀。文獻(xiàn)[10]使用Student-t混合模型與變分貝葉斯近似,提出了一個(gè)網(wǎng)格聚類算法。文獻(xiàn)[11]則將先驗(yàn)知識(shí)與基于幾何相似性的內(nèi)容驅(qū)動(dòng)分析相結(jié)合。

本文使用蟻群優(yōu)化(Ant Colony Optimization,ACO)[12]算法進(jìn)行網(wǎng)格分割。ACO算法模擬螞蟻在自然界中覓食的行為:在地上行走時(shí)遺留激素而被其他螞蟻探測(cè),進(jìn)而用來(lái)尋找巢穴和食物來(lái)源之間的最有效路線。ACO最初被成功地應(yīng)用于旅行商問(wèn)題,后被用于許多工程問(wèn)題如網(wǎng)絡(luò)路徑優(yōu)化、圖像處理等[13]。筆者在早期的工作中已成功地將蟻群優(yōu)化應(yīng)用到圖像序列的移動(dòng)矢量估計(jì)上[14],在本文中則將蟻群優(yōu)化應(yīng)用到三維網(wǎng)格的分割中。

1 網(wǎng)格分割模型與方法

1.1 基于蟻群優(yōu)化的網(wǎng)格分割模型

網(wǎng)格分割的目的是將每個(gè)網(wǎng)格賦予一個(gè)標(biāo)簽,并且使屬于同一標(biāo)簽的相鄰網(wǎng)格滿足分割條件。將待分割網(wǎng)格的每個(gè)網(wǎng)格視為一個(gè)螞蟻,每個(gè)螞蟻可以選擇Γ個(gè)標(biāo)簽,通過(guò)蟻群優(yōu)化機(jī)制對(duì)每個(gè)網(wǎng)格的標(biāo)簽不斷更新。在迭代過(guò)程中,每個(gè)螞蟻?zhàn)罴训臉?biāo)簽由式(1)決定。

(1)

其中:p(u)是一個(gè)候選標(biāo)簽u的轉(zhuǎn)移概率。

轉(zhuǎn)移概率按式(2)計(jì)算。

(2)

其中:τ(u)被稱為殘留信息濃度,在迭代過(guò)程中,每個(gè)螞蟻都保留在所有標(biāo)簽下的殘留信息;η(u)為啟發(fā)值,它反映了螞蟻對(duì)于某個(gè)標(biāo)簽的趨向;α和β是控制τ(u)和η(u)相對(duì)平衡的2個(gè)因子系數(shù)。

η(u)的計(jì)算公式如式(3)所示。

(3)

其中:ε(u)是本螞蟻對(duì)應(yīng)于u標(biāo)簽的特征值,其計(jì)算方法將在下文描述。

1.2 殘留信息濃度的更新

在迭代過(guò)程中,每個(gè)螞蟻的每個(gè)標(biāo)簽的殘留信息濃度都要更新。設(shè)τ(u)第一次迭代前的初始值為τ0,并在每次迭代結(jié)束時(shí)被更新,如式(4)所示。

τ(u)←ρ·τ(u)+γ·Δτ(u)

(4)

其中:ρ為遺傳系數(shù),它代表螞蟻當(dāng)前殘留信息濃度對(duì)下次迭代的影響程度;Δτ(u)為殘留信息濃度增量的空間約束分量,它由計(jì)算相鄰螞蟻的平均殘留信息濃度而得。

相鄰螞蟻的平均殘留信息按式(5)計(jì)算。

(5)

其中:假設(shè)當(dāng)前的螞蟻為b,b′為鄰域中符合分割條件的螞蟻之一;NS為鄰域大小。

1.3 螞蟻的特征值

對(duì)于網(wǎng)格,可以計(jì)算網(wǎng)格的一些屬性,如曲率、形狀直徑函數(shù)(Shape Diameter Function,SDF)[15]等。本文選用SDF。形狀直徑函數(shù)是一個(gè)定義在網(wǎng)格表面上的標(biāo)量函數(shù),它表示在網(wǎng)格表面每一點(diǎn)附近的物體體積的直徑。

在式(3)中,ε(u)是本螞蟻對(duì)應(yīng)于u標(biāo)簽的特征值,這是驅(qū)動(dòng)網(wǎng)格分割的主要標(biāo)準(zhǔn)。本文計(jì)算特征值的辦法是計(jì)算某個(gè)螞蟻鄰域內(nèi)網(wǎng)格點(diǎn)SDF的標(biāo)準(zhǔn)差。

1.4 網(wǎng)格標(biāo)簽初始化與種子點(diǎn)產(chǎn)生

圖1顯示了網(wǎng)格初始化的過(guò)程。所有的網(wǎng)格先賦予一個(gè)背景標(biāo)簽(如Γ+1)。然后對(duì)于每一個(gè)種子點(diǎn)(每一個(gè)種子點(diǎn)對(duì)應(yīng)一個(gè)唯一的標(biāo)簽),其周圍的網(wǎng)格點(diǎn)賦予和種子點(diǎn)一樣的標(biāo)簽。產(chǎn)生種子點(diǎn)可以采取隨機(jī)的方法產(chǎn)生。隨著蟻群優(yōu)化的迭代,種子點(diǎn)的標(biāo)簽向外擴(kuò)散,直到迭代標(biāo)準(zhǔn)滿足。圖1中V1和V2是2個(gè)種子點(diǎn),而V3是背景標(biāo)簽。

圖1 網(wǎng)格初始化

1.5 分割條件

下面以SDF為網(wǎng)格屬性為例說(shuō)明分割條件。對(duì)于一個(gè)待更新螞蟻b,其目前的最佳標(biāo)簽為M,假設(shè)其鄰域含有若干個(gè)非背景標(biāo)簽。對(duì)于其中一個(gè)候選標(biāo)簽u,其分割條件如式(6)所示。

(6)

并且:

|mean(SDF[Ω(b,M)])-

(7)

圖2 網(wǎng)格鄰域示意圖

2 基于蟻群優(yōu)化的網(wǎng)格分割算法

基于蟻群優(yōu)化的網(wǎng)格分割算法描述如下:

輸入標(biāo)簽個(gè)數(shù)Γ、迭代次數(shù)、待處理三維網(wǎng)格數(shù)據(jù)

計(jì)算網(wǎng)格屬性如SDF

數(shù)據(jù)預(yù)處理:準(zhǔn)備每個(gè)螞蟻的數(shù)據(jù)結(jié)構(gòu)、計(jì)算每個(gè)螞蟻的鄰域、將屬性歸一化

產(chǎn)生種子點(diǎn)

初始化網(wǎng)格標(biāo)簽(背景標(biāo)簽和種子點(diǎn)鄰域標(biāo)簽)

Loop/*蟻群優(yōu)化迭代*/

Loop/*對(duì)每個(gè)螞蟻,挑選最佳標(biāo)簽*/

IF檢查這個(gè)螞蟻是否需要被更新,如果是,執(zhí)行以下步驟(參見(jiàn)下文注1)

Loop/*對(duì)每個(gè)候選標(biāo)簽u,計(jì)算其轉(zhuǎn)移概率*/

計(jì)算候選標(biāo)簽u的特征值

計(jì)算轉(zhuǎn)移概率p(u)(式(2))

End/*完成所有候選標(biāo)簽的計(jì)算*/

根據(jù)式(1)選取最佳標(biāo)簽并記錄

End

End

Loop/*對(duì)每個(gè)螞蟻,更新其殘留信息濃度*/

IF檢查這個(gè)螞蟻是否需要被更新,如果是,執(zhí)行以下步驟

Loop/*對(duì)每個(gè)候選標(biāo)簽u進(jìn)行更新*/

根據(jù)式(4)和式(5),更新τ(u)

End

End

End

End/*最大迭代次數(shù)達(dá)到或迭代標(biāo)準(zhǔn)完成*/

區(qū)域合并(參見(jiàn)下文注2)

輸出分割結(jié)果

注1:在螞蟻更新過(guò)程中,有一個(gè)判斷標(biāo)準(zhǔn)。這一步有以下目的;1)保證背景標(biāo)簽不做不必要的更新;2)種子點(diǎn)及其鄰域只有在滿足分割條件的情況下才能擴(kuò)散。一個(gè)螞蟻只有在下面情況下才能更新:1)鄰域含有足夠的非背景標(biāo)簽;2)至少有一個(gè)候選標(biāo)簽滿足分割條件。

注2:蟻群迭代完成后,相鄰的區(qū)域在滿足分割條件的情況下進(jìn)行合并。

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

對(duì)本文算法用MATLAB(版本2012a)進(jìn)行實(shí)現(xiàn),并對(duì)Princeton網(wǎng)格數(shù)據(jù)集(http://segeval.cs.princeton.edu/)的一些例子進(jìn)行實(shí)驗(yàn)。所用計(jì)算機(jī)處理器為Intel i5-4590 CPU @3.30 GHz,內(nèi)存4 GB,64位操作系統(tǒng)。

3.1 參數(shù)選擇

關(guān)于式(2)中α和β的選擇,根據(jù)多數(shù)數(shù)蟻群優(yōu)化的文獻(xiàn)以及筆者的相關(guān)研究,2個(gè)參數(shù)均可選1。關(guān)于式(4)中ρ和γ的選擇,根據(jù)筆者多次實(shí)驗(yàn),選用ρ=0.7及γ=0.2可以達(dá)到較好的結(jié)果。

圖3(a)顯示了蟻群優(yōu)化的迭代次數(shù)和標(biāo)簽更新率的關(guān)系,此結(jié)果是對(duì)Princeton網(wǎng)格數(shù)據(jù)集第180例數(shù)據(jù)上實(shí)驗(yàn)得到的。標(biāo)簽更新率指一次迭代時(shí)標(biāo)簽發(fā)生更新的網(wǎng)格頂點(diǎn)數(shù)與總網(wǎng)格頂點(diǎn)數(shù)之比。從中可以看出,迭代次數(shù)在20次左右之后,標(biāo)簽更新率基本穩(wěn)定,這種現(xiàn)象在測(cè)試其他例子時(shí)也是如此。圖3(b)顯示了蟻群優(yōu)化的迭代次數(shù)和標(biāo)簽更新率在第130例數(shù)據(jù)的關(guān)系。

圖3 蟻群優(yōu)化迭代次數(shù)與標(biāo)簽更新率的關(guān)系

可以看出,標(biāo)簽更新率在開(kāi)始迭代后幾次達(dá)到高峰,然后迅速下降,再達(dá)到基本穩(wěn)定。這一點(diǎn)和將蟻群優(yōu)化用于移動(dòng)矢量估計(jì)結(jié)果有所不同[13]。在那種情況下,在約第10幀之前,移動(dòng)矢量仍然大幅度振蕩,當(dāng)經(jīng)過(guò)一定數(shù)量的幀數(shù)之后,移動(dòng)矢量才開(kāi)始趨于穩(wěn)定。由此可以看出,應(yīng)用不同,蟻群優(yōu)化的收斂結(jié)果是不同的。

3.2 實(shí)驗(yàn)結(jié)果

圖4顯示對(duì)Princeton網(wǎng)格數(shù)據(jù)集第91例網(wǎng)格數(shù)據(jù)的處理結(jié)果。 這個(gè)例子有8 640個(gè)頂點(diǎn)、17 276個(gè)網(wǎng)面。圖4(a)是原始網(wǎng)格,圖4(b)顯示了種子點(diǎn),共有40個(gè),圖4(c)顯示了蟻群優(yōu)化的結(jié)果,也是區(qū)域合并前結(jié)果,而圖4(d)顯示了區(qū)域合并后結(jié)果,即最后分割結(jié)果。分割結(jié)果含有11個(gè)區(qū)域,正確率100%。

圖4 Princeton網(wǎng)格數(shù)據(jù)集第91例分割結(jié)果

圖5顯示對(duì)第130例網(wǎng)格數(shù)據(jù)的處理結(jié)果。該例有7 747個(gè)頂點(diǎn)、15 490個(gè)網(wǎng)面。分割結(jié)果包含9個(gè)區(qū)域,正確率為100%。

圖5 Princeton網(wǎng)格數(shù)據(jù)集第130例分割結(jié)果

圖6顯示對(duì)第180例網(wǎng)格數(shù)據(jù)的處理結(jié)果。該例有9 548個(gè)頂點(diǎn)、19 092個(gè)網(wǎng)面。分割結(jié)果包含7個(gè)區(qū)域,正確率為100%。

圖6 Princeton網(wǎng)格數(shù)據(jù)集第180例分割結(jié)果

3.3 與圖割方法的比較

圖割是圖像分割的熱門研究方向,也有將圖割用于網(wǎng)格分割的研究[16-18]。將本文方法和圖割方法進(jìn)行比較。在圖割方法中,首先,用高斯混合模型將k個(gè)高斯函數(shù)擬合SDF直方圖,此過(guò)程通過(guò)EM(Expectation Maximization)算法完成。通過(guò)這個(gè)聚類過(guò)程可以得到三維網(wǎng)格每個(gè)網(wǎng)格點(diǎn)SDF值在各個(gè)高斯函數(shù)下的概率,也就是該網(wǎng)格點(diǎn)屬于各個(gè)區(qū)域的概率。然后通過(guò)α-擴(kuò)張圖割算法取得最后分割結(jié)果。這一步優(yōu)化將高斯混合模型擬合的結(jié)果和其他平滑條件結(jié)合形成一個(gè)能量函數(shù)。圖7顯示了利用圖割方法的分割結(jié)果:圖7(a)中分割出15個(gè)區(qū)域,正確率73%;圖7(b)中分割出20個(gè)區(qū)域,正確率35%;圖7(c)中分割出11個(gè)區(qū)域,正確率82%。通過(guò)比較可以看出本文方法的分割結(jié)果較好。

圖7 圖割方法分割結(jié)果

4 結(jié)束語(yǔ)

本文將蟻群優(yōu)化算法應(yīng)用到三維網(wǎng)格的分割上,利用MATLAB進(jìn)行實(shí)現(xiàn),并通過(guò)Princeton網(wǎng)格數(shù)據(jù)集的例子進(jìn)行實(shí)驗(yàn)。本文方法具有簡(jiǎn)單、靈活的優(yōu)點(diǎn),可以根據(jù)具體問(wèn)題靈活構(gòu)造,本文特征值使用的是SDF值,對(duì)于其他應(yīng)用,可以使用其他特征值或者多個(gè)特征值。此外,蟻群優(yōu)化具有潛在的平行處理特性,可以加快處理速度,這需要進(jìn)一步研究。后續(xù)工作是將本文方法用在其他應(yīng)用上,如在生物醫(yī)學(xué)工程領(lǐng)域,在醫(yī)學(xué)圖像分割之后,可以通過(guò)網(wǎng)格分割進(jìn)一步劃分出人體結(jié)構(gòu)的許多子結(jié)構(gòu)。此外,筆者也擬將本文方法與其他方法相結(jié)合,以提高分割質(zhì)量。

[1] 董洪偉.三角網(wǎng)格分割綜述[J].中國(guó)圖象圖形學(xué)報(bào),2010,15(2):181-193.

[2] 易 兵,劉振宇,譚建榮.基于高斯映射的CAD網(wǎng)格法向聚類分割方法[J].機(jī)械工程學(xué)報(bào),2015,51(7):115-122.

[3] FANG Y,SUN M,KIM M,et al.Heat-mapping:A Robust Approach Toward Perceptually Consistent Mesh Segmentation[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington D.C.,USA:IEEE Press,2011:2145-2152.

[4] HU Ruizhen,FAN Lubin,LIU Ligang.Co-segmentation of 3D Shapes via Subspace Clustering[J].Computer Graphics Forum,2012,31(5):1703-1713.

[5] BIASOTTI S,CERRI A,BRONSTEIN A,et al.Recent Trends,Applications,and Perspectives in 3D Shape Similarity Assessment[J].Computer Graphics Forum,2016,35(6):87-119.

[6] HUANG Qixing,KOLTUN V,GUIBAS L.Joint Shape Segmentation with Linear Programming[J].ACM Transactions on Graphics,2011,30(6).

[7] van KAICK O,XU Kai,ZHANG Hao,et al.Co-hierarchical Analysis of Shape Structures[J].ACM Transactions on Graphics,2013,32(4).

[8] MENG Min,XIA Jiazhi,LUO Jun,et al.Unsupervised Co-segmentation for 3D Shapes Using Iterative Multi-label Optimization[J].CAD Computer Aided Design,2013,45(2):312-320.

[9] SHU Zhenyu,QI Chengwu,XIN Shiqing,et al.Unsupervised 3D Shape Segmentation and Co-segmentation via Deep Learning[J].Computer Aided Geometric Design,2016,43(3):39-52.

[10] TSUCHIE S,HOSINO T,HIGASHI M.High-quality Vertex Clustering for Surface Mesh Segmentation Using Student-t Mixture Model[J].CAD Computer Aided Design,2014,46(1):69-78.

[11] van KAICK O,TAGLIASACCHI A,SIDI O,et al.Prior Knowledge for Part Correspondence[J].Computer Graphics Forum,2011,30(2):553-562.

[12] DORIGO M,GAMBARDELLA L.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[13] 魏 東,吳良杰,佐 丹,等.基于混合蟻群算法的網(wǎng)格任務(wù)調(diào)度[J].計(jì)算機(jī)工程,2010,36(3):215-217.

[14] 張耀楠,楊 樂(lè),康 雁.蟻群優(yōu)化在超聲圖像運(yùn)動(dòng)矢量估計(jì)中的應(yīng)用[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,33(3):327-331.

[15] SHAPIRA L,SHAMIR A,COHEN-OR D.Consistent Mesh Partitioning and Skeletonisation Using the Shape Diameter Function[J].Visual Computer,2008,24(4):249-259.

[16] UGAIL H,LIU Lei,SHENG Yun,et al.Graph Cut Based Mesh Segmentation Using Feature Points and Geodesic Distance[C]//Proceedings of 2015 International Con-ference on Cyberworlds.Visby,Sweden:[s.n.],2015:115-120.

[17] LI Guodong,CHEN Xinjian,SHI Fei,et al.Automatic Liver Segmentation Based on Shape Constraints and Deformable Graph Cut in CT Images[J].IEEE Transactions on Image Processing,2015,24(12):5315-5329.

[18] SHI Zhenfeng,LE Dan,YU Liyang,et al.3D Mesh Segmentation Based on Markov Random Fields and Graph Cuts[J].IEICE Transactions on Information and Systems,2012,E95-D(2):703-706.