計(jì)算機(jī)輔助拓?fù)湓O(shè)計(jì)——持續(xù)同調(diào)在幾何設(shè)計(jì)和處理中的應(yīng)用

董哲同，藺宏偉

計(jì)算機(jī)輔助拓?fù)湓O(shè)計(jì)——持續(xù)同調(diào)在幾何設(shè)計(jì)和處理中的應(yīng)用

董哲同1,2，藺宏偉1,2

(1. 浙江大學(xué)數(shù)學(xué)科學(xué)學(xué)院，浙江 杭州 310027；2. 浙江大學(xué)CAD&CG國家重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310058)

持續(xù)同調(diào)是一種計(jì)算不同尺度拓?fù)涮卣鞯挠行Х椒?。其從一簇向后包含的單純?fù)形序列中提取出拓?fù)涮卣鞯某霈F(xiàn)和消失時(shí)刻，并使用拓?fù)涮卣鞯摹吧芷凇眮砹炕睾饬吭撎卣鞯膸缀纬叨群椭匾潭取Ｍ負(fù)涮卣鞯奶崛∨c應(yīng)用在幾何設(shè)計(jì)中扮演著重要角色，催生出了一些基于持續(xù)同調(diào)的幾何設(shè)計(jì)研究。從持續(xù)同調(diào)特征的提取與基于持續(xù)同調(diào)的建模和優(yōu)化兩方面進(jìn)行綜述，在持續(xù)同調(diào)特征的提取方面，介紹了從點(diǎn)云和三角網(wǎng)格數(shù)據(jù)中提取拓?fù)涮卣鞯牟煌椒?，總結(jié)了拓?fù)涮卣髟诓糠謳缀卧O(shè)計(jì)問題中的應(yīng)用路徑。在建模和優(yōu)化方面，綜述了基于拓?fù)渥儞Q的單純復(fù)形重建方法、拓?fù)淇筛兄那嬷亟ǚ椒ㄅc基于持續(xù)同調(diào)的拓?fù)淙ピ牒蛢?yōu)化方法。

持續(xù)同調(diào)；拓?fù)涮卣魈崛?；形狀重建；去噪與優(yōu)化；幾何設(shè)計(jì)；拓?fù)湓O(shè)計(jì)

1 緒 論

持續(xù)同調(diào)以計(jì)算幾何和代數(shù)拓?fù)錇橹饕獢?shù)學(xué)工具，從一簇向后包含的單純復(fù)形序列中計(jì)算各維同調(diào)等價(jià)類出現(xiàn)和消失的時(shí)刻，并將出現(xiàn)-消失點(diǎn)對(duì)作為復(fù)形序列拓?fù)涮卣?。持續(xù)同調(diào)的提出和發(fā)展可以追溯到20世紀(jì)90年代?！俺掷m(xù)性”(persistence)的概念獨(dú)立地出現(xiàn)在了幾乎處于同一時(shí)期的3組研究項(xiàng)目中，即學(xué)者Frosini，F(xiàn)erri及其合作者的工作，學(xué)者Robins的博士論文和學(xué)者EDELSBRUNNER的項(xiàng)目[1]。2000年，美國Duke大學(xué)的學(xué)者EDELSBRUNNER等[2]系統(tǒng)地提出了持續(xù)同調(diào)的定義和算法，此后持續(xù)同調(diào)理論和計(jì)算方面的研究不斷涌現(xiàn)，如文獻(xiàn)[3-4]分別給出了持續(xù)同調(diào)和多維度持續(xù)同調(diào)的理論和計(jì)算方法。2009年，CARLSSON[5]的奠基性工作使得拓?fù)鋽?shù)據(jù)分析(topological data analysis)作為新興的研究領(lǐng)域得以誕生。值得一提的是，持續(xù)同調(diào)與Morse理論有著緊密的聯(lián)系，如持續(xù)性可以用于簡(jiǎn)化Morse-Smale復(fù)形的拓?fù)浣Y(jié)構(gòu)[6]，Morse理論也可加速持續(xù)同調(diào)的計(jì)算[7]。持續(xù)同調(diào)可用于從采樣點(diǎn)云推斷采樣流形可能的拓?fù)浣Y(jié)構(gòu)，從定義在單純復(fù)形上的一類標(biāo)量函數(shù)導(dǎo)出的單純復(fù)形序列中提取各維度的拓?fù)涮卣鳌Ｔ摲椒芏康胤从惩負(fù)涮卣鞯膸缀纬叨?，區(qū)分重要拓?fù)涮卣骱驮肼曁卣鳎瑢?duì)輸入數(shù)據(jù)中的微小噪聲和擾動(dòng)不敏感。基于以上優(yōu)點(diǎn)，持續(xù)同調(diào)在解決分子結(jié)構(gòu)分析[8]、腦與神經(jīng)科學(xué)[9]、醫(yī)學(xué)圖像處理[10]等領(lǐng)域的一些科學(xué)問題上獲得了成功的應(yīng)用。

計(jì)算機(jī)輔助幾何設(shè)計(jì)是一門由微分幾何、數(shù)值計(jì)算等數(shù)學(xué)分支與計(jì)算機(jī)交叉而產(chǎn)生的學(xué)科，主要以三維物體表示、建模、處理、分析和模擬為研究重點(diǎn)。從20世紀(jì)70年代以來，自由曲線曲面的表示、設(shè)計(jì)、顯示、分析和處理等是計(jì)算機(jī)輔助幾何設(shè)計(jì)的主要研究對(duì)象和內(nèi)容[11]，并取得的豐富研究成果，為三維建模軟件的開發(fā)應(yīng)用建立了理論基礎(chǔ)。然而，由于缺乏有效的計(jì)算工具，在幾何設(shè)計(jì)和處理中出現(xiàn)的一些拓?fù)鋯栴}，無法得到有效的系統(tǒng)解決方法。隨著以持續(xù)同調(diào)(persistent homology)[2-3,5]為代表的計(jì)算拓?fù)浼夹g(shù)的發(fā)展，三維形狀的拓?fù)涮卣骺梢员涣炕毓烙?jì)和表達(dá)，從而方便地應(yīng)用于形狀分析、分類與檢索、拓?fù)淇煽氐膬?yōu)化與建模等幾何設(shè)計(jì)問題中。持續(xù)同調(diào)的成功應(yīng)用為眾多的代數(shù)拓?fù)淅碚撟呦驊?yīng)用提供了潛在的可能性，為解決幾何設(shè)計(jì)和處理中的拓?fù)鋯栴}提供可能的解決方案，從而為計(jì)算機(jī)輔助拓?fù)湓O(shè)計(jì)這一新興研究領(lǐng)域提供了潛在的理論支持。

近十年以來，持續(xù)同調(diào)被系統(tǒng)應(yīng)用于幾何設(shè)計(jì)和幾何處理，主要解決三維形狀的拓?fù)涮卣魈崛?、分析以及形狀建模中遇到的拓?fù)湎嚓P(guān)問題，逐漸形成了計(jì)算機(jī)輔助拓?fù)湓O(shè)計(jì)這一研究領(lǐng)域。在三維形狀拓?fù)涮卣魈崛》矫?，持續(xù)同調(diào)采用持續(xù)圖(persistence diagram)[2]或持續(xù)條碼(persistence barcode)[5]編碼同調(diào)特征，研究者們將這些特征轉(zhuǎn)化為關(guān)于持續(xù)圖度量穩(wěn)定且易于使用的向量化形式，以便進(jìn)一步應(yīng)用于形狀分析、分類和檢索等問題中。在三維形狀建模方面，如何使用提取的拓?fù)涮卣骰謴?fù)三維形狀是近年來研究的一個(gè)熱點(diǎn)問題之一。持續(xù)同調(diào)可以用于區(qū)分重要的拓?fù)涮卣骱驮肼曁卣?，在保拓?fù)浼怃J特征的優(yōu)化中也發(fā)揮了重要作用。另外，通過持續(xù)同調(diào)構(gòu)造的持續(xù)逆映射(persistence inverse mapping)[12]使得拓?fù)淇煽氐慕＜夹g(shù)得到了發(fā)展。

2 預(yù)備知識(shí)：持續(xù)同調(diào)

持續(xù)同調(diào)致力于從一簇向后包含的單純復(fù)形序列中提取不同尺度和不同維度的拓?fù)涮卣?，如連通分支(0維特征)、獨(dú)立環(huán)結(jié)構(gòu)(1維特征)和獨(dú)立空腔結(jié)構(gòu)(2維特征)等，并且反映這些特征隨尺度參數(shù)變化的出現(xiàn)和消失情況，以此衡量這些拓?fù)涮卣鞯膸缀纬叨群椭匾潭?。單純?fù)形是用于計(jì)算持續(xù)同調(diào)的基本組合結(jié)構(gòu)，一個(gè)單純復(fù)形通常是指由點(diǎn)(0-單形)、線(1-單形)、三角面(2-單形)和四面體(3-單形)等不同維度的單形按照以下規(guī)則組合而成的復(fù)合結(jié)構(gòu)：①單純復(fù)形中任意單形的面(face)屬于該單純復(fù)形；②任意2個(gè)單形的交要么為空，要么為公共面。

為了從采樣點(diǎn)云中推斷采樣形狀的拓?fù)浣Y(jié)構(gòu)，需要依托點(diǎn)云建立一系列向后包含的單純復(fù)形，也稱過濾(filtration)。建立過濾的方法有很多，如文獻(xiàn)[13-15]所示方法，其中Vietoris-Rips復(fù)形[13]較為常用。該方法的基本思想是在每一點(diǎn)上放置一個(gè)閉球，所有球的半徑參數(shù)逐漸增加。在某一參數(shù)下，若存在個(gè)點(diǎn)，滿足其閉球兩兩相交，則這個(gè)點(diǎn)構(gòu)成一個(gè)(-1)-單形。另外，將定義在形狀上的標(biāo)量函數(shù)做線性逼近生成定義在對(duì)應(yīng)單純復(fù)形上的分片線性函數(shù)也能生成過濾，用于提取按該標(biāo)量函數(shù)數(shù)值大小排列時(shí)單純復(fù)形的拓?fù)浣Y(jié)構(gòu)變化信息。通常可以將單純復(fù)形按照分片線性標(biāo)量函數(shù)數(shù)值從小到大或從大到小排列分別生成下水平過濾或上水平過濾。值得一提的是，Zig-zag持續(xù)方法[16]的出現(xiàn)使得過濾不再局限于向后包含的單純復(fù)形序列。

代數(shù)拓?fù)涫浅掷m(xù)同調(diào)采用的主要數(shù)學(xué)工具，其將單純復(fù)形中的單形視為代數(shù)運(yùn)算的算術(shù)元素。在單純同調(diào)的簡(jiǎn)單情形下，第維的所有單形按照模2加法構(gòu)成-鏈群C，其中的元素由一些-單形的算術(shù)組合構(gòu)成，稱為-鏈。為了反映從C到C-1元素的邊界關(guān)系，定義邊界算子?:C→C-1，該算子將一個(gè)-鏈映射為其中每個(gè)單形所有(-1)-面的代數(shù)和形式，稱為-鏈的邊界。對(duì)于任意1，相鄰2個(gè)維度的邊界算子的復(fù)合為零算子，即?°?-1=0。為了代數(shù)地表示獨(dú)立孔洞結(jié)構(gòu)，定義邊界算子?的零空間Z={?C:?=0}為閉鏈群，邊界算子?+1的像空間B={?C:$?C+1s.t.?+1=c}為邊緣鏈群。直觀地，一個(gè)獨(dú)立環(huán)結(jié)構(gòu)是一類非邊界閉鏈，即不是任何高維鏈邊界的閉鏈。由于相鄰邊界算子復(fù)合為零，所以可以用商群Z/B定義同調(diào)群H，同調(diào)群中的元素表示獨(dú)立環(huán)結(jié)構(gòu)的等價(jià)類，是一類重要的拓?fù)涮卣鳌Ｍ{(diào)群的階(rank)稱為Betti數(shù)，反映拓?fù)涮卣鞯膫€(gè)數(shù)，如0維Betti數(shù)指示單純復(fù)形中連通分支的個(gè)數(shù)，1維Betti數(shù)指示獨(dú)立環(huán)結(jié)構(gòu)的個(gè)數(shù)。文獻(xiàn)[17-18]提供了更多同調(diào)和計(jì)算同調(diào)的細(xì)節(jié)。

在過濾中，獨(dú)立孔洞結(jié)構(gòu)會(huì)隨著參數(shù)變化而出現(xiàn)、存在和消失，持續(xù)同調(diào)能從過濾中計(jì)算同調(diào)特征的出現(xiàn)和消失對(duì)應(yīng)的參數(shù)時(shí)刻，采用出生-死亡(birth-death)點(diǎn)對(duì)表示對(duì)應(yīng)的同調(diào)特征。定義死亡值與出生值的差為持續(xù)值，該指標(biāo)衡量拓?fù)涮卣鞯纳芷?，以便推測(cè)該特征是否為采樣形狀的重要特征，并且衡量該特征的幾何尺度。如圖1所示，隨著“時(shí)間參數(shù)”的增加，復(fù)形序列中陸續(xù)有拓?fù)涮卣鞒霈F(xiàn)和消失。圖1(a)藍(lán)色和橙黃色線段分別表示連通分支(0維拓?fù)涮卣?和獨(dú)立環(huán)結(jié)構(gòu)(1維拓?fù)涮卣?的生命周期，這些嵌入到平面中的線段構(gòu)成了一個(gè)拓?fù)涮卣鞅硎?，稱為持續(xù)條碼。進(jìn)一步，將出生-死亡點(diǎn)對(duì)嵌入到平面得到持續(xù)圖，如圖1(b)所示。持續(xù)圖和持續(xù)條碼為持續(xù)同調(diào)提供了緊湊的拓?fù)涮卣鞅硎尽Ａ硗?，Wasserstein距離和bottleneck距離[14]可以用于度量2個(gè)持續(xù)圖或持續(xù)條碼之間的相似性。進(jìn)一步，在滿足不同條件時(shí)，持續(xù)同調(diào)具有一些穩(wěn)定性結(jié)論[13,19-21]，即當(dāng)點(diǎn)云或形狀上的標(biāo)量函數(shù)發(fā)生擾動(dòng)時(shí)，在這些距離的意義下，持續(xù)圖或持續(xù)條碼的擾動(dòng)可以被該擾動(dòng)的常數(shù)倍控制。這些穩(wěn)定性結(jié)論說明了持續(xù)同調(diào)對(duì)數(shù)據(jù)中的噪聲不敏感，在實(shí)踐中具有重要的意義。

圖1 使用持續(xù)同調(diào)從一簇向后包含的單純復(fù)形序列中計(jì)算持續(xù)圖的示意圖((a)過濾與持續(xù)條碼；(b)持續(xù)圖)

過濾過程可以視作單形依參數(shù)大小依次添加到單純復(fù)形中，單形的添加往往會(huì)對(duì)應(yīng)某一拓?fù)涮卣鞯某霈F(xiàn)或消失。拓?fù)涮卣鞯某錾岛退劳鲋捣謩e對(duì)應(yīng)2個(gè)不同的單形。文獻(xiàn)[12]據(jù)此提出了拓?fù)淠嬗成鋪碜粉櫝掷m(xù)點(diǎn)對(duì)對(duì)應(yīng)的單形對(duì)，在形成過濾的標(biāo)量函數(shù)滿足一定條件時(shí)，可以構(gòu)造良好定義的拓?fù)淠嬗成?，該映射也可將持續(xù)點(diǎn)對(duì)映射為對(duì)應(yīng)的臨界點(diǎn)對(duì)。該映射是基于持續(xù)同調(diào)的拓?fù)淇煽胤椒ǖ闹匾ぞ?，?jù)此可以計(jì)算有關(guān)持續(xù)圖的目標(biāo)函數(shù)關(guān)于標(biāo)量場(chǎng)中各參數(shù)的梯度。如圖2所示(虛線箭頭給出了持續(xù)圖上的點(diǎn)到拓?fù)淇臻g上點(diǎn)對(duì)的映射關(guān)系)，是定義在拓?fù)淇臻g上的標(biāo)量函數(shù)，按生成的下水平過濾計(jì)算持續(xù)圖。持續(xù)逆映射將持續(xù)圖上的點(diǎn)((),())映射到臨界值點(diǎn)對(duì)(,)，其含義是將對(duì)應(yīng)的連通分支的出現(xiàn)追溯到點(diǎn)對(duì)應(yīng)的單形在下水平過濾中的出現(xiàn)，將該連通分支的消失追溯到點(diǎn)對(duì)應(yīng)的單形在下水平過濾中的出現(xiàn)[22]。

圖2 持續(xù)逆映射的示意圖[22]

3 持續(xù)同調(diào)拓?fù)涮卣骷捌鋺?yīng)用

從幾何形狀中盡可能完整地提取形狀某一方面或某幾方面的特征是形狀分析、分類和檢索等幾何處理問題中的重要步驟。傳統(tǒng)的拓?fù)洳蛔兞浚鏐etti數(shù)、虧格和歐拉示性數(shù)等，雖然能提供拓?fù)涮卣鞯臄?shù)量信息且便于計(jì)算，但是卻不能具體地反映拓?fù)浣Y(jié)構(gòu)的幾何尺度，對(duì)幾何數(shù)據(jù)中的噪聲非常敏感，即使局部擾動(dòng)也會(huì)導(dǎo)致這些傳統(tǒng)拓?fù)洳蛔兞康妮^大變化。持續(xù)同調(diào)能通過點(diǎn)云估計(jì)采樣形狀的拓?fù)浣Y(jié)構(gòu)，計(jì)算三維形狀按某一標(biāo)量函數(shù)生成過濾的拓?fù)涮卣?。?jì)算所得的持續(xù)圖能將拓?fù)涮卣髋c形狀的幾何進(jìn)行關(guān)聯(lián)，提供幾何尺度的量化指標(biāo)，且對(duì)輸入數(shù)據(jù)的噪聲不敏感。本節(jié)綜述使用持續(xù)同調(diào)從點(diǎn)云和空間網(wǎng)格中提取拓?fù)涮卣鞯南嚓P(guān)方法，并總結(jié)拓?fù)涮卣鞅硎驹趲缀卧O(shè)計(jì)和處理中的應(yīng)用。

3.1 點(diǎn)云的持續(xù)同調(diào)特征提取方法

空間點(diǎn)云是在三維空間中的一個(gè)點(diǎn)集，通常通過掃描或采樣三維物體獲得，是幾何設(shè)計(jì)中一種常用的形狀表示。一些幾何設(shè)計(jì)任務(wù)需要提取點(diǎn)云中的拓?fù)涮卣鬟M(jìn)行分析，為了重建拓?fù)浣Y(jié)構(gòu)滿足預(yù)期的三維形狀，也需要從點(diǎn)云中提取拓?fù)湎闰?yàn)信息。持續(xù)同調(diào)通過建立復(fù)形過濾的方式計(jì)算持續(xù)圖，其中的點(diǎn)對(duì)分別表示復(fù)形序列中對(duì)應(yīng)拓?fù)涮卣鞯某霈F(xiàn)和消失的參數(shù)時(shí)刻，而構(gòu)造復(fù)形過濾有諸多方法。與Vietoris-Rips 復(fù)形類似，?ech復(fù)形[13]要求在單形的所有頂點(diǎn)對(duì)應(yīng)的閉球有非空公共交集。Alpha復(fù)形[23]則通過Delaunay三角化生成關(guān)于點(diǎn)云的一組子復(fù)形。而當(dāng)點(diǎn)云數(shù)據(jù)規(guī)模較大時(shí)，為了減少過濾中單純復(fù)形的單形數(shù)量且反映單純復(fù)形的主要拓?fù)浣Y(jié)構(gòu)，Witness復(fù)形[14]通過保留關(guān)鍵點(diǎn)和采樣的方式構(gòu)造近似復(fù)形過濾。另外，在構(gòu)造Vietoris-Rips復(fù)形的過程中，可以通過點(diǎn)云下采樣或設(shè)置最大半徑參數(shù)的方式來近似地計(jì)算持續(xù)圖[24]。

在大規(guī)模空間點(diǎn)云數(shù)據(jù)上計(jì)算持續(xù)同調(diào)是一個(gè)具有挑戰(zhàn)性的任務(wù)，其主要困難在于隨著點(diǎn)云中點(diǎn)個(gè)數(shù)的增加，計(jì)算較高維的持續(xù)同調(diào)特征需要考慮的單形個(gè)數(shù)將以指數(shù)增加。如按照Vietoris-Rips復(fù)形構(gòu)造過濾，對(duì)一個(gè)含有5 000個(gè)點(diǎn)的空間點(diǎn)云，計(jì)算1維持續(xù)圖須構(gòu)造約107個(gè)1-單形和2×1010個(gè)2-單形[25]。持續(xù)同調(diào)算法的時(shí)間復(fù)雜度與單形個(gè)數(shù)成比例，即經(jīng)典的持續(xù)同調(diào)算法在實(shí)例中具有擬線性的復(fù)雜度，而對(duì)于最壞情況，則具有關(guān)于單形個(gè)數(shù)的三次方的時(shí)間復(fù)雜度[2-3]。因此，需要通過設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)、優(yōu)化存儲(chǔ)空間和并行計(jì)算等提高實(shí)際計(jì)算持續(xù)同調(diào)的效率[26]，如Ripser[24]工具包提供了高效計(jì)算Vietoris-Rips復(fù)形序列的算法，文獻(xiàn)[27-28]給出了高效構(gòu)造單純復(fù)形的數(shù)據(jù)結(jié)構(gòu)，并簡(jiǎn)化了高維的單純復(fù)形。

在點(diǎn)云處理中，往往只需要通過點(diǎn)云估算采樣形狀的大致拓?fù)涮卣鳎掷m(xù)值較小的拓?fù)涮卣魍灰暈樵肼?。因此，采用搭建神?jīng)網(wǎng)絡(luò)來估計(jì)持續(xù)圖成為了提升持續(xù)同調(diào)計(jì)算效率的一個(gè)新途徑。SOM等[29]在提取圖像特征時(shí)率先提出了一種基于卷積神經(jīng)網(wǎng)絡(luò)的架構(gòu)估算持續(xù)圖的向量化表示。在三維點(diǎn)云處理領(lǐng)域，文獻(xiàn)[25]基于EdgeConv 卷積層[30]提出了一種快速估計(jì)點(diǎn)云Vietoris-Rips 復(fù)形過濾的持續(xù)圖向量化表示持續(xù)圖像(persistence images)[31]的網(wǎng)絡(luò)架構(gòu)。該神經(jīng)網(wǎng)絡(luò)使用大量點(diǎn)云數(shù)據(jù)及對(duì)應(yīng)的持續(xù)圖向量化表示作為訓(xùn)練數(shù)據(jù)，能端到端高效地估計(jì)持續(xù)同調(diào)特征。實(shí)驗(yàn)表明，估計(jì)所得的持續(xù)圖像與真實(shí)持續(xù)圖像偏差較小。但是該網(wǎng)絡(luò)架構(gòu)依賴于在點(diǎn)云上建立圖結(jié)構(gòu)，在理論上未說明關(guān)于點(diǎn)云數(shù)據(jù)的噪聲和擾動(dòng)具有穩(wěn)定性。DE SURREL等[32]基于Deep sets[33]提出了一種快速估計(jì)點(diǎn)云的Vietoris-Rips復(fù)形過濾的持續(xù)圖的網(wǎng)絡(luò)架構(gòu)。該方法借助Deep sets的理論結(jié)果可以簡(jiǎn)潔地推導(dǎo)出估計(jì)持續(xù)圖的穩(wěn)定性結(jié)論，且估計(jì)過程高效，計(jì)算結(jié)果也較為精確。由于在評(píng)估實(shí)驗(yàn)中，此類方法多使用點(diǎn)云標(biāo)準(zhǔn)數(shù)據(jù)集或合成數(shù)據(jù)集，因此尚不清楚此類方法在真實(shí)、復(fù)雜數(shù)據(jù)集上的表現(xiàn)。

3.2 三角網(wǎng)格的持續(xù)同調(diào)特征提取方法

空間三角網(wǎng)格表示的三維形狀可以視為嵌入到空間的單純復(fù)形。除了使用單純同調(diào)計(jì)算Betti數(shù)或同調(diào)生成元或使用點(diǎn)云采樣并計(jì)算持續(xù)同調(diào)獲得拓?fù)涮卣饕酝?，還有一些方法可用于提取三角網(wǎng)格的拓?fù)涮卣?，如基于網(wǎng)格測(cè)地距離的持續(xù)同調(diào)方法，基于特征函數(shù)過濾的持續(xù)同調(diào)方法和拓?fù)渥儞Q方法。

與嵌入到空間的點(diǎn)云使用歐氏距離構(gòu)造Vietoris-Rips復(fù)形類似，在三角網(wǎng)格上可以通過測(cè)地距離生成復(fù)形序列。CARRIèRE等[34]提出了基于測(cè)地距離的持續(xù)同調(diào)方法來提取網(wǎng)格模型的拓?fù)涮卣?。選擇網(wǎng)格模型上的一點(diǎn)為圓心，以可變參數(shù)為半徑作測(cè)地圓盤，可以得到在給定半徑參數(shù)下完全包含在測(cè)地圓盤中的子復(fù)形。隨著半徑參數(shù)逐漸增加，得到一列向后包含的子復(fù)形序列，使用持續(xù)同調(diào)可以計(jì)算該復(fù)形過濾中持續(xù)圖。對(duì)于三角網(wǎng)格上的任意一點(diǎn)，均可采取以上方法計(jì)算持續(xù)圖，作為該三維形狀的局部描述子。該方法提取的拓?fù)涮卣麝P(guān)于噪聲不敏感，但需要定義相似性度量來比較2個(gè)三維模型對(duì)應(yīng)的持續(xù)圖簇之間的差異。

基于特征函數(shù)過濾的持續(xù)同調(diào)方法是提取網(wǎng)格模型特征的一類方法，即利用定義在這個(gè)網(wǎng)格上的標(biāo)量函數(shù)按函數(shù)值大小生成復(fù)形過濾，計(jì)算持續(xù)同調(diào)。由于所選擇的標(biāo)量函數(shù)通常反映三維形狀的局部特征，因此稱這類標(biāo)量函數(shù)為“特征函數(shù)”[35]。這類函數(shù)的選擇往往依賴于實(shí)際應(yīng)用，標(biāo)量函數(shù)中參數(shù)的調(diào)整也多是經(jīng)驗(yàn)性的。一般地，可以選擇熱核函數(shù) (heat kernel signature)[36]或波核函數(shù)(wave kernel signature)[37]作為特征函數(shù)。如DONG等[38]使用熱核函數(shù)設(shè)計(jì)多尺度拓?fù)涿枋鲎觼矸诸惗嗫捉Y(jié)構(gòu)。文獻(xiàn)[35, 39]也利用熱核函數(shù)作為特征函數(shù)，以便將不同時(shí)間參數(shù)下的持續(xù)圖組合為多尺度的描述子。

拓?fù)渥儞Q是一類將三維形狀從形狀空間轉(zhuǎn)換到特征空間的方法。受啟發(fā)于積分幾何(integral geometry)[40]在曲面和隨機(jī)場(chǎng)建模以及點(diǎn)云處理上的應(yīng)用，TURNER等[41]提出持續(xù)同調(diào)變換(persistent homology transform，PHT)和歐拉示性變換(euler characteristic transform，ECT)提取網(wǎng)格的拓?fù)涮卣?。PHT與ECT分別將網(wǎng)格模型(單純復(fù)形)轉(zhuǎn)換為一簇與不同投影方向相關(guān)的持續(xù)圖與持續(xù)歐拉示性數(shù)，即使用不同的投影向量定義高度函數(shù)，再使用該函數(shù)構(gòu)造復(fù)形過濾從而得到持續(xù)拓?fù)涮卣?。持續(xù)歐拉示性數(shù)可以由持續(xù)圖導(dǎo)出，因此PHT包含了ECT的全部信息?；赑HT的拓?fù)涮卣魈崛》椒梢詰?yīng)用于網(wǎng)格對(duì)比與分類。根據(jù)PHT可以定義不同網(wǎng)格形狀間的距離，即計(jì)算各方向上持續(xù)圖的距離，并將距離值沿投影方向進(jìn)行數(shù)值積分，以便度量網(wǎng)格的相似性。在ECT的基礎(chǔ)上，CRAWFORD等[42]提出了光滑歐拉特征變換提取拓?fù)涮卣?，并?yīng)用于癌癥診斷以及針對(duì)形狀的統(tǒng)計(jì)推斷。KIRVESLAHTI和MUKHERJEE[43]將網(wǎng)格上的ECT推廣到標(biāo)量場(chǎng)上。對(duì)于一般的度量空間，OUDOT和SOLOMON[44]提出內(nèi)蘊(yùn)持續(xù)同調(diào)變換(intrinsic persistent homology transform，IPHT)提取特征。具體地，通過在度量空間中不同的點(diǎn)上定義距離場(chǎng)，IPHT利用距離場(chǎng)的下水平過濾生成持續(xù)圖。與PHT的不同之處在于，IPHT與三維形狀的嵌入空間無關(guān)，只與形狀本身有關(guān)。

3.3 拓?fù)涮卣髟趲缀翁幚碇械膽?yīng)用

持續(xù)同調(diào)從三維點(diǎn)云和三角網(wǎng)格中提取拓?fù)涮卣?，并以持續(xù)圖的方式展示這些不同幾何尺度的特征。然而，計(jì)算2個(gè)持續(xù)圖之間的Wasserstein距離或bottleneck距離是比較耗時(shí)的，特別是當(dāng)持續(xù)圖中有大量的點(diǎn)對(duì)時(shí)，這是因?yàn)榫嚯x的計(jì)算依賴于點(diǎn)對(duì)集合之間的最優(yōu)匹配的求解[45]。另外，諸多統(tǒng)計(jì)分析工具，如求平均值等，以及支持向量機(jī)等用于分類或聚類的機(jī)器學(xué)習(xí)常用工具不能以持續(xù)圖作為輸入，因此需要將持續(xù)圖進(jìn)行向量化，以便將這些拓?fù)涮卣鲬?yīng)用于幾何處理的相關(guān)問題中。

持續(xù)圖的向量化可以分為將持續(xù)圖轉(zhuǎn)換為顯式向量表示和隱式向量表示2類方法。持續(xù)圖向量化的要點(diǎn)是轉(zhuǎn)換得到的向量關(guān)于持續(xù)圖的距離度量是穩(wěn)定的，即持續(xù)圖上的小擾動(dòng)也對(duì)應(yīng)著向量表示上的小擾動(dòng)。顯式向量化方法即將一個(gè)持續(xù)圖映射到有限維向量空間的一個(gè)向量。這一類方法通常在持續(xù)圖上構(gòu)造特征曲面，使用與其等價(jià)的函數(shù)表示或?qū)⒊掷m(xù)圖嵌入到代數(shù)空間等，再進(jìn)行離散化從而得到有限維向量表示。常用的特征曲面構(gòu)造方法包括持續(xù)曲面[31]和持續(xù)B樣條曲面[46]；常用的持續(xù)圖等價(jià)形式有持續(xù)Betti數(shù)函數(shù)[47]和持續(xù)景觀 (persistence landscapes)[48]。離散化特征構(gòu)造也有多種方式，如CANG等[49]通過直接劃分持續(xù)圖為均勻網(wǎng)格，并統(tǒng)計(jì)每個(gè)網(wǎng)格中持續(xù)點(diǎn)對(duì)的個(gè)數(shù)作為對(duì)應(yīng)向量元素的值。文獻(xiàn)[31]通過劃分持續(xù)曲面的定義域并對(duì)每個(gè)曲面片積分得到向量中每一位的數(shù)值。另外，如Tropical坐標(biāo)表示法[50]、持續(xù)詞匯袋[51]和持續(xù)路徑簽名表示[52]等方法也是持續(xù)圖向量化的有效方法。

持續(xù)圖的隱式向量化通過非線性映射將持續(xù)圖嵌入到合適的內(nèi)積空間中，再在新的嵌入空間中訓(xùn)練線性模型來處理數(shù)據(jù)，該方法的核心是構(gòu)造合適的核函數(shù)，因此又稱此類方法為核方法。核方法不產(chǎn)生顯式的向量化表示，也不顯性地構(gòu)造非線性映射。REININGHAUS等[53]提出持續(xù)尺度空間核函數(shù)，該核函數(shù)來源于一個(gè)熱擴(kuò)散問題，是一個(gè)多尺度的核函數(shù)。該向量化方法具有1階Wasserstein穩(wěn)定性，但不具備高階Wasserstein穩(wěn)定性。文獻(xiàn)[21]提出持續(xù)加權(quán)高斯核，將持續(xù)圖映射為希爾伯特空間中的元素。該向量化方法具有關(guān)于原始點(diǎn)云數(shù)據(jù)Hausdorff距離的穩(wěn)定性。類似的核方法還有切Wasserstein核方法[54]和持續(xù)Fisher核方法[55]。最后，PUN等[56]對(duì)持續(xù)圖向量化做了詳細(xì)的綜述。

圖3總結(jié)了使用持續(xù)同調(diào)解決幾何處理中的形狀分析、分類和檢索等問題的思路與流程。通過Vietoris-Rips復(fù)形等方法構(gòu)造復(fù)形過濾，可以從點(diǎn)云中計(jì)算各維度的持續(xù)圖；通過定義“特征函數(shù)”生成水平集過濾或者采用向各方向投影的PHT方法，可以計(jì)算持續(xù)圖。將計(jì)算所得的持續(xù)圖向量化的方法，使之與統(tǒng)計(jì)方法或機(jī)器學(xué)習(xí)方法兼容。最后，持續(xù)圖的相關(guān)向量化表示被應(yīng)用于形狀比較[57-58]、形狀匹配[12, 59]、形狀檢索[38, 60]、形狀識(shí)別[61]、形狀分類和分析[31, 62]中。

圖3 從三維模型中提取持續(xù)同調(diào)特征并用于解決幾何處理中一些問題的示意圖

4 基于持續(xù)同調(diào)的建模和優(yōu)化

三維形狀的拓?fù)涫且活愔匾男再|(zhì)，也是幾何設(shè)計(jì)關(guān)注的重要目標(biāo)之一。相比于基于經(jīng)典的離散拓?fù)洳蛔兞康耐負(fù)淇筛兄７椒?，持續(xù)同調(diào)為形狀建模和優(yōu)化提供了新思路。

4.1 基于拓?fù)涮卣鞯膯渭儚?fù)形重建

計(jì)算持續(xù)圖是一個(gè)提取特征的過程，持續(xù)圖是一組幾何多尺度的拓?fù)涮卣?，被?yīng)用于形狀分類等幾何設(shè)計(jì)問題中，而使用這些拓?fù)涮卣骰謴?fù)和重建三維形狀是一個(gè)逆向工程。PHT將一個(gè)單純復(fù)形按照不同方向投影，產(chǎn)生一簇持續(xù)圖。文獻(xiàn)[41]從理論上證明了PHT在二維和三維空間上的單射性，即一簇持續(xù)圖至多只與一個(gè)單純復(fù)形對(duì)應(yīng)。CURRY等[63]與GHRIST等[64]進(jìn)一步推廣了該結(jié)論，分別獨(dú)立證明了在任意維度的歐氏空間中的可構(gòu)造子集上，ECT具有單射性，并由此導(dǎo)出PHT的單射性。這意味著可以嘗試從PHT產(chǎn)生的一簇持續(xù)圖中恢復(fù)單純復(fù)形。

文獻(xiàn)[41]給出了PHT單射性的證明是構(gòu)造性的，即從0維單形開始，逐步重建整個(gè)單純復(fù)形。這事實(shí)上給出了重建單純復(fù)形的算法，但該方法考慮的是從無窮多方向的持續(xù)圖簇中重建單純復(fù)形，因此這驅(qū)動(dòng)了通過有限方向的持續(xù)圖簇重建單純復(fù)形的研究。文獻(xiàn)[63]證明了有限個(gè)方向的持續(xù)圖可以唯一確定形狀，并給出了方向個(gè)數(shù)的上界。BELTON和TERESE[65]提出了從3個(gè)方向得到的拓展持續(xù)圖出發(fā)，以多項(xiàng)式時(shí)間復(fù)雜度重建平面上的一維單純復(fù)形(嵌入平面的圖)的算法。算法通過搜索3組投影線的交點(diǎn)確定頂點(diǎn)，由頂點(diǎn)的“度”確定邊。該算法的不足在于3個(gè)投影方向需由單純復(fù)形本身確定，這使得該算法不具備通用性。進(jìn)一步地，BELTON等[66]將算法從平面推廣到任意維度歐氏空間，利用更多不同方向的持續(xù)圖重建嵌入到任意維歐氏空間的一維單純復(fù)形。FASY等[67]提出了增廣持續(xù)同調(diào)變換(augmented PHT)的離散化方法，通過在單形上推廣“入度”并研究單形預(yù)測(cè)技術(shù)，從而將這些方法擴(kuò)展到從有限多個(gè)方向持續(xù)圖重建任意維度的單純復(fù)形。然而，上述方法缺乏在大型數(shù)據(jù)集上重建的實(shí)驗(yàn)結(jié)果。

4.2 拓?fù)淇筛兄娜S建模

幾何設(shè)計(jì)的一個(gè)重要研究課題是建模具有正確或理想的拓?fù)涞娜S形狀。在部分研究中，往往采用后處理[68]或人機(jī)交互[69]的方式移除或修改生成形狀上的拓?fù)溴e(cuò)誤，這些方式依賴于用戶對(duì)形狀進(jìn)行局部修正。而部分研究[70-73]則通過使用虧格和Betti數(shù)等經(jīng)典拓?fù)洳蛔兞吭O(shè)計(jì)約束條件，通過定義能量函數(shù)的方式優(yōu)化組合單元，從而重建出拓?fù)湔_的幾何形狀，如曲面。這類方法能保證生成具有拓?fù)洳蛔兞康男螤?，然而?jīng)典拓?fù)洳蛔兞坎荒苊枋鐾負(fù)涮卣鞯膸缀纬叨龋瑑?yōu)化過程多采用動(dòng)態(tài)規(guī)劃，在一些復(fù)雜的算例中，算法的時(shí)間和空間復(fù)雜度會(huì)呈指數(shù)級(jí)。

基于持續(xù)同調(diào)的拓?fù)淇筛兄椒ɡ梦墨I(xiàn)[12]提出的持續(xù)逆映射建立一套基于梯度下降的連續(xù)優(yōu)化框架。相比于基于經(jīng)典拓?fù)洳蛔兞康碾x散優(yōu)化框架，這類方法易于理解和實(shí)現(xiàn)，且可以使用能描述拓?fù)涮卣鲙缀纬叨鹊某掷m(xù)圖作為重建和優(yōu)化的先驗(yàn)信息。BRüEL-GABRIELSSON等[74]提出了一種基于持續(xù)逆映射的拓?fù)淇筛兄膹狞c(diǎn)云重建曲線和曲面的方法，根據(jù)持續(xù)圖上點(diǎn)對(duì)的相對(duì)位置設(shè)計(jì)拓?fù)鋼p失函數(shù)，并采用梯度下降的連續(xù)優(yōu)化框架進(jìn)行優(yōu)化。具體而言，首先以點(diǎn)云中的點(diǎn)為中心的多元高斯函數(shù)構(gòu)造似然函數(shù)，并將空間離散為自適應(yīng)的單純復(fù)形；使用該似然函數(shù)為每一個(gè)單形分配一個(gè)兼容的單形值；然后構(gòu)造上水平過濾，計(jì)算持續(xù)圖。最小化拓?fù)鋼p失函數(shù)，計(jì)算損失函數(shù)關(guān)于似然函數(shù)中參數(shù)的梯度，使用梯度下降的方式更新參數(shù)；最后從優(yōu)化后的似然函數(shù)對(duì)應(yīng)的底復(fù)形中提取提升的同調(diào)表示元作為重建的曲線或曲面。由于該方法使用從似然函數(shù)中提取的同調(diào)表示元作為重建形狀，所以曲線、曲面的光滑性不高。

為了提高重建曲面的光滑性并同時(shí)保障目標(biāo)曲面具有預(yù)期的拓?fù)?，文獻(xiàn)[22]提出了一種基于持續(xù)逆映射的拓?fù)淇煽氐碾[式曲面重建方法。該方法首先計(jì)算點(diǎn)云的符號(hào)距離函數(shù)，離散包圍盒為立方復(fù)形，并使用B樣條函數(shù)擬合離散符號(hào)距離值；將重建目標(biāo)對(duì)應(yīng)的持續(xù)圖作為拓?fù)漕A(yù)期用于設(shè)計(jì)拓?fù)淠繕?biāo)函數(shù)；同樣采用梯度下降的連續(xù)優(yōu)化框架，最小化目標(biāo)函數(shù)并優(yōu)化B樣條函數(shù)中的控制系數(shù)；最后根據(jù)優(yōu)化后的持續(xù)圖上主要特征點(diǎn)對(duì)的位置決定提取的等值面。該方法的優(yōu)點(diǎn)在于可以通過優(yōu)化控制水平集中較為顯著的拓?fù)浣Y(jié)構(gòu)的幾何尺度。如圖4所示，通過最小化持續(xù)圖上持續(xù)值第二大的點(diǎn)(綠色點(diǎn))對(duì)應(yīng)的持續(xù)值，該優(yōu)化框架消除了較小尺度的環(huán)柄圈，且生成的隱式曲面具有較好的光滑性。該方法也有一些缺陷，如與其他基于梯度下降的連續(xù)優(yōu)化框架類似，該優(yōu)化方法可能會(huì)收斂到局部最優(yōu)解，且每次優(yōu)化迭代都需要計(jì)算持續(xù)圖；不能很好地區(qū)分和優(yōu)化較小的拓?fù)涮卣鳌?/p>

4.3 拓?fù)淙ピ肱c優(yōu)化

圖像與信號(hào)處理中的一個(gè)重要問題是研究如何在保留重要特征的同時(shí)去除數(shù)據(jù)中的噪聲。同樣地，拓?fù)淙ピ胫荚诒Ａ敉負(fù)浼怃J點(diǎn)和尖銳邊等特征，并且去除數(shù)據(jù)中的拓?fù)湓肼暋Ｈ鏑ARR和SNOEYINK[75]通過提取輸入數(shù)據(jù)的輪廓樹并做簡(jiǎn)化以去除一些不必要的細(xì)微的拓?fù)涮卣?，但該方法不能保證去除一些小的噪聲環(huán)結(jié)構(gòu)。另外一類常用的方法是基于Morse-Smale復(fù)形[76]的拓?fù)淙ピ牒秃?jiǎn)化方法。如BREMER等[77]利用Morse-Smale復(fù)形消除(cancellation)技術(shù)簡(jiǎn)化復(fù)形結(jié)構(gòu)，并在每次迭代過程中光滑單純復(fù)形中單形內(nèi)部的標(biāo)量函數(shù)，從而保證調(diào)整后的單純復(fù)形遵循一定的拓?fù)浣Y(jié)構(gòu)，并且生成光滑的二維標(biāo)量場(chǎng)。然而該方法不能區(qū)分拓?fù)浼怃J特征并進(jìn)行保留。

圖4 文獻(xiàn)[22]方法

為了保留重要拓?fù)涮卣鞑⑷コ肼暎珿üNTHER等[78]利用持續(xù)同調(diào)為拓?fù)涮卣鬟M(jìn)行分級(jí)，將文獻(xiàn)[79-80]提出的二維標(biāo)量函數(shù)重建方法擴(kuò)展到解決三維標(biāo)量函數(shù)的去噪問題上。該方法首先計(jì)算標(biāo)量場(chǎng)中的極值，從上/下水平過濾中計(jì)算持續(xù)圖并按照持續(xù)值大小給極值點(diǎn)分級(jí)，確定拓?fù)浼怃J點(diǎn)。再將拓?fù)淙ピ雴栴}建模為離散優(yōu)化問題，選定需要保留的拓?fù)浼怃J點(diǎn)且避免新的尖銳點(diǎn)出現(xiàn)。采用線性化約束和凸化可行域的技術(shù)將優(yōu)化問題轉(zhuǎn)化為二次規(guī)劃，并進(jìn)一步轉(zhuǎn)化為錐規(guī)劃問題求解。在求解過程中，采用區(qū)域分解技術(shù)使得計(jì)算更加高效，內(nèi)存使用更少，可快速地處理大規(guī)模標(biāo)量場(chǎng)的去噪。但該方法是一種啟發(fā)式算法，不能保證優(yōu)化問題的解是全局最優(yōu)解甚至局部最優(yōu)解。

持續(xù)同調(diào)除了被用作優(yōu)化過程中量化分級(jí)拓?fù)浼怃J特征的工具外，還可以被用于設(shè)計(jì)保證拓?fù)浣Y(jié)構(gòu)正確的優(yōu)化中。BRüEL-GABRIELSSON等[81]將在文獻(xiàn)[72]中提出的基于持續(xù)同調(diào)的拓?fù)淇筛兄獌?yōu)化框架進(jìn)行進(jìn)一步推廣，與機(jī)器學(xué)習(xí)技術(shù)相結(jié)合，應(yīng)用于優(yōu)化點(diǎn)云和體素的拓?fù)浣Y(jié)構(gòu)。對(duì)于三維體素?cái)?shù)據(jù)，該方法并未給出過于復(fù)雜的算例，需要探索該框架在復(fù)雜拓?fù)鋽?shù)據(jù)場(chǎng)景下的應(yīng)用。GAO等[82]提出了一種基于持續(xù)同調(diào)優(yōu)化框架的保證連通性的多孔結(jié)構(gòu)生成方法。該工作解決了通過多孔結(jié)構(gòu)樣本合成大尺寸多孔結(jié)構(gòu)過程中不連通的問題。由于采用二值化體素建模多孔結(jié)構(gòu)，無法直接使用梯度下降方法設(shè)計(jì)連續(xù)優(yōu)化問題，因此該工作將基于距離場(chǎng)(distance to measure，DTM)的持續(xù)同調(diào)方法[83]推廣到體素空間。DTM在空間位置上的取值與該位置與實(shí)體材料之間的距離呈正比，可以反映實(shí)體材料與空間位置的位置關(guān)系。該方法利用從DTM下水平過濾中計(jì)算得到的0維持續(xù)圖設(shè)計(jì)優(yōu)化目標(biāo)，使得DTM中具有較小距離值的水平集具有一個(gè)連通分支，最終提取連通的立方復(fù)形作為優(yōu)化后的多孔結(jié)構(gòu)。圖5展示了該方法使用持續(xù)同調(diào)優(yōu)化框架優(yōu)化多孔結(jié)構(gòu)體素?cái)?shù)據(jù)的實(shí)驗(yàn)結(jié)果。然而，與其他基于持續(xù)同調(diào)的拓?fù)淇筛兄獌?yōu)化框架類似，該方法在每次迭代中均需要計(jì)算持續(xù)圖，這增加了計(jì)算時(shí)間。

圖5 文獻(xiàn)[82]方法

5 總結(jié)與展望

一方面，自2000年文獻(xiàn)[2]提出持續(xù)同調(diào)的基本概念以來，持續(xù)同調(diào)的理論體系得到了完善，并結(jié)合統(tǒng)計(jì)學(xué)和數(shù)據(jù)科學(xué)等其他學(xué)科，發(fā)展出了拓?fù)鋽?shù)據(jù)分析這一門新興的交叉學(xué)科。另一方面，由于持續(xù)同調(diào)的發(fā)展建立在計(jì)算幾何和計(jì)算拓?fù)涞幕A(chǔ)之上，所以在幾何設(shè)計(jì)和處理領(lǐng)域也涌現(xiàn)出了大量持續(xù)同調(diào)的應(yīng)用研究。本文首先簡(jiǎn)要地介紹了持續(xù)同調(diào)的發(fā)展歷程和核心概念。在拓?fù)涮卣鞯奶崛『蛻?yīng)用方面，綜述了使用持續(xù)同調(diào)提取采樣形狀的點(diǎn)云和三角網(wǎng)格模型拓?fù)涮卣鞯姆椒ǎ⒖偨Y(jié)了持續(xù)同調(diào)特征在形狀分類、分析、匹配和檢索等幾何處理問題中的應(yīng)用。另外，還從基于拓?fù)渥儞Q的單純復(fù)形重建、拓?fù)淇筛兄娜S曲面重建和拓?fù)淙ピ牒蛢?yōu)化3個(gè)方面綜述了持續(xù)同調(diào)在形狀建模和優(yōu)化中的已有研究。

雖然持續(xù)同調(diào)在理論和應(yīng)用方面取得了長(zhǎng)足的發(fā)展和進(jìn)步，但仍然有一些問題值得研究。文獻(xiàn)[84-85]中列舉了有關(guān)持續(xù)同調(diào)理論的公開問題。在應(yīng)用方面，持續(xù)同調(diào)的高效和快速計(jì)算問題也值得研究。由于多維度持續(xù)同調(diào)[4]不存在緊湊的拓?fù)涮卣鞅硎綶86]，如何提取和組織多層次拓?fù)涮卣魇且粋€(gè)值得研究的問題。另外，基于持續(xù)同調(diào)的連續(xù)優(yōu)化框架的理論也不斷在完善[81, 87]，更多的優(yōu)化思路被不斷地提出[88]，為持續(xù)同調(diào)在幾何設(shè)計(jì)中的應(yīng)用奠定了堅(jiān)實(shí)的基礎(chǔ)。因此，基于持續(xù)同調(diào)的幾何設(shè)計(jì)技術(shù)具有廣闊的發(fā)展前景，并正在促進(jìn)“計(jì)算機(jī)輔助拓?fù)湓O(shè)計(jì)”這一新興研究領(lǐng)域的發(fā)展。

[1] EDELSBRUNNER H, HARER J. Persistent homology-a survey[J]. Contemporary Mathematics, 2008, 453: 257-282.

[2] EDELSBRUNNER H, LETSCHER D, ZOMORODIAN A. Topological persistence and simplification[C]//The 41st Annual Symposium on Foundations of Computer Science. New York: IEEE Press, 2002: 454-463.

[3] ZOMORODIAN A, CARLSSON G. Computing persistent homology[J]. Discrete & Computational Geometry, 2005, 33(2): 249-274.

[4] CARLSSON G, ZOMORODIAN A. The theory of multidimensional persistence[J]. Discrete & Computational Geometry, 2009, 42(1): 71-93.

[5] CARLSSON G. Topology and data[J]. Bulletin of the American Mathematical Society, 2009, 46(2): 255-308.

[6] ZOMORODIAN A J. Topology for computing[M]. Cambridge: Cambridge University Press, 2005.

[7] MISCHAIKOW K, NANDA V. Morse theory for filtrations and efficient computation of persistent homology[J]. Discrete & Computational Geometry, 2013, 50(2): 330-353.

[8] XIA K L, WEI G W. Multidimensional persistence in biomolecular data[J]. Journal of Computational Chemistry, 2015, 36(20): 1502-1520.

[9] LEE H, KANG H, CHUNG M K, et al. Persistent brain network homology from the perspective of dendrogram[J]. IEEE Transactions on Medical Imaging, 2012, 31(12): 2267-2277.

[10] QAISER T, TSANG Y W, TANIYAMA D, et al. Fast and accurate tumor segmentation of histology images using persistent homology and deep convolutional features[J]. Medical Image Analysis, 2019, 55: 1-14.

[11] 梁友棟, 劉鼎元, 金通洸. 計(jì)算幾何的現(xiàn)狀與趨勢(shì)[C]//1982年計(jì)算幾何討論會(huì). 杭州: 浙江大學(xué)學(xué)報(bào), 1982: 17-25.

LIANG Y D, LIU D Y, JIN T G. Current status and trends in computational geometry[C]//Computational Geometry Symposium, 1982. Hangzhou: Journal of Zhejiang University, 1982: 17-25 (in Chinese).

[12] POULENARD A, SKRABA P, OVSJANIKOV M. Topological function optimization for continuous shape matching[J]. Computer Graphics Forum, 2018, 37(5): 13-25.

[13] EDELSBRUNNER H, HARER J. Computational Topology[M]. Providence, Rhode Island: American Mathematical Society, 2009.

[14] GUIBAS L J, OUDOT S Y. Reconstruction using witness complexes[J]. Discrete & Computational Geometry, 2008, 40(3): 325-356.

[15] ZOMORODIAN A. The tidy set: a minimal simplicial set for computing homology of clique complexes[C]//The 26th Annual Symposium on Computational Geometry. New York: ACM Press, 2010: 257-266.

[16] CARLSSON G, DE SILVA V. Zigzag persistence[J]. Foundations of Computational Mathematics, 2010, 10(4): 367-405.

[17] HATCHER A. Algebraic topology[M]. New York: Cambridge University Press, 2002.

[18] KACZYNSKI T, MISCHAIKOW K, MROZEK M. Computational Homology[M]. New York: Springer New York, 2004.

[19] COHEN-STEINER D, EDELSBRUNNER H, HARER J. Stability of persistence diagrams[J]. Discrete & Computational Geometry, 2007, 37(1): 103-120.

[20] CHAZAL F, DE SILVA V, OUDOT S. Persistence stability for geometric complexes[J]. Geometriae Dedicata, 2014, 173(1): 193-214.

[21] GENKI K, KENJI F, YASUAKI H. Kernel method for persistence diagrams via kernel embedding and weight factor[J]. Journal of Machine Learning Research, 2018, 18: 1-41.

[22] DONG Z T, CHEN J H, LIN H W. Topology-controllable implicit surface reconstruction based on persistent homology[J]. Computer-Aided Design, 2022, 150: 103308.

[23] EDELSBRUNNER H, MüCKE E P. Three-dimensional alpha shapes[J]. ACM Transactions on Graphics, 1994, 13(1): 43-72.

[24] TRALIE C, SAUL N, BAR-ON R. Ripser.py: a lean persistent homology library for python[J]. Journal of Open Source Software, 2018, 3(29): 925.

[25] ZHOU C, DONG Z T, LIN H W. Learning persistent homology of 3D point clouds[J]. Computers & Graphics, 2022, 102: 269-279.

[26] OTTER N, PORTER M A, TILLMANN U, et al. A roadmap for the computation of persistent homology[J]. EPJ Data Science, 2017, 6(1): 17.

[27] ATTALI D, LIEUTIER A, SALINAS D. Efficient data structure for representing and simplifying simplicial complexes in high dimensions[C]//The 27th Annual Symposium on Computational Geometry. New York: ACM Press, 2011: 501-509.

[28] BOISSONNAT J D, MARIA C. The simplex tree: an efficient data structure for general simplicial complexes[J]. Algorithmica, 2014, 70(3): 406-427.

[29] SOM A, CHOI H, RAMAMURTHY K N, et al. PI-net: a deep learning approach to extract topological persistence images[C]//2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops. New York: IEEE Press, 2020: 3639-3648.

[30] WANG Y, SUN Y B, LIU Z W, et al. Dynamic graph CNN for learning on point clouds[J]. ACM Transactions on Graphics, 2019, 38(5): 1-12.

[31] HENRY A, TEGAN E, MICHAEL K, et al. Persistence images: a stable vector representation of persistent homology[J]. Journal of Machine Learning Research, 2017, 18: 1-35.

[32] DE SURREL T, HENSEL F, CARRIèRE M, et al. RipsNet: a general architecture for fast and robust estimation of the persistent homology of point clouds[EB/OL]. [2022-01-25]. https://arxiv.org/abs/2202.01725.

[33] ZAHEER M, KOTTUR S, RAVANBAKHSH S, et al. Deep sets[EB/OL]. [2022-05-10]. https://arxiv.org/abs/1703.06114.

[34] CARRIèRE M, OUDOT S Y, OVSJANIKOV M. Stable topological signatures for points on 3D shapes[J]. Computer Graphics Forum, 2015, 34(5): 1-12.

[35] LI C Y, OVSJANIKOV M, CHAZAL F. Persistence-based structural recognition[C]//2014 IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2014: 2003-2010.

[36] G?BAL K, B?RENTZEN J A, AAN?S H, et al. Shape analysis using the auto diffusion function[C]//Proceedings of the Symposium on Geometry Processing. New York: ACM Press, 2009: 1405-1413.

[37] AUBRY M, SCHLICKEWEI U, CREMERS D. The wave kernel signature: a quantum mechanical approach to shape analysis[C]//2011 IEEE International Conference on Computer Vision Workshops. New York: IEEE Press, 2012: 1626-1633.

[38] DONG Z T, PU J Y, LIN H W. Multiscale persistent topological descriptor for porous structure retrieval[J]. Computer Aided Geometric Design, 2021, 88: 102004.

[39] DEY T K, LI K, LUO C, et al. Persistent heat signature for pose-oblivious matching of incomplete models[J]. Computer Graphics Forum, 2010, 29(5): 1545-1554.

[40] KLAIN D A, ROTA G C. Introduction to geometric probability[M]. Cambridge: Cambridge University Press, 1997.

[41] TURNER K, MUKHERJEE S, BOYER D M. Persistent homology transform for modeling shapes and surfaces[J]. Information and Inference: A Journal of the IMA, 2014, 3(4): 310-344.

[42] CRAWFORD L, MONOD A, CHEN A X, et al. Predicting clinical outcomes in glioblastoma: an application of topological and functional data analysis[J]. Journal of the American Statistical Association, 2020, 115(531): 1139-1150.

[43] KIRVESLAHTI H, MUKHERJEE S. Representing fields without correspondences: the lifted Euler characteristic transform[EB/OL]. [2022-06-27]. https://arxiv.org/abs/2111.04788.

[44] OUDOT S, SOLOMON E. Barcode embeddings for metric graphs[J]. Algebraic & Geometric Topology, 2021, 21(3): 1209-1266.

[45] KERBER M, MOROZOV D, NIGMETOV A. Geometry helps to compare persistence diagrams[J]. ACM Journal of Experimental Algorithmics, 2017, 22: 1-20.

[46] DONG Z T, LIN H W, ZHOU C. Persistence B-spline grids: stable vector representation of persistence diagrams based on data fitting[EB/OL]. [2022-06-17]. https://arxiv.org/abs/1909.08417.

[47] FROSINI P, LANDI C. Persistent Betti numbers for a noise tolerant shape-based approach to image retrieval[J]. Pattern Recognition Letters, 2013, 34(8): 863-872.

[48] BUBENIK P. Statistical topological data analysis using persistence landscapes[J]. Journal of Machine Learning Research, 2015, 16: 77-102.

[49] CANG Z X, MU L, WU K D, et al. A topological approach for proteinclassification[J]. Computational and Mathematical Biophysics, 2015, 3(1): 140-162.

[50] KALI?NIK S. Tropical coordinates on the space of persistence barcodes[J]. Foundations of Computational Mathematics, 2019, 19(1): 101-129.

[51] ZIELI?SKI B, LIPI?SKI M, JUDA M, et al. Persistence bag-of-words for topological data analysis[C]//The 28th International Joint Conference on Artificial Intelligence. New York: ACM Press, 2019: 4489-4495.

[52] CHEVYREV I, NANDA V, OBERHAUSER H. Persistence paths and signature features in topological data analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020, 42(1): 192-202.

[53] REININGHAUS J, HUBER S, BAUER U, et al. A stable multi-scale kernel for topological machine learning[C]//2015 IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2015: 4741-4748.

[54] CARRIèRE M, CUTURI M, OUDOT S. Sliced Wasserstein kernel for persistence diagrams[C]//The 34th International Conference on Machine Learning - Volume 70. New York: ACM Press, 2017: 664-673.

[55] LE T, YAMADA M. Persistence fisher kernel: a Riemannian manifold kernel for persistence diagrams[C]//The 32nd International Conference on Neural Information Processing Systems. New York: ACM Press, 2018: 10028-10039.

[56] PUN C S, LEE S X, XIA K L. Persistent-homology-based machine learning: a survey and a comparative study[J].Artificial Intelligence Review, 2022, 55(7): 5169-5213.

[57] FROSINI P, JAB?O?SKI G. Combining persistent homology and invariance groups for shape comparison[J]. Discrete & Computational Geometry, 2016, 55(2): 373-409.

[58] DI FABIO B, LANDI C. Persistent homology and partial similarity of shapes[J]. Pattern Recognition Letters, 2012, 33(11): 1445-1450.

[59] DEY T K, LI K, LUO C, et al. Persistent heat signature for pose-oblivious matching of incomplete models[J]. Computer Graphics Forum, 2010, 29(5): 1545-1554.

[60] ZEPPELZAUER M, ZIELI?SKI B, JUDA M, et al. A study on topological descriptors for the analysis of 3D surface texture[J]. Computer Vision and Image Understanding, 2018, 167: 74-88.

[61] BONIS T, OVSJANIKOV M, OUDOT S, et al. Persistence-based pooling for shape pose recognition[M]//Computational Topology in Image Context. Cham: Springer International Publishing, 2016: 19-29.

[62] ZHOU Z, HUANG Y Z, WANG L, et al. Exploring generalized shape analysis by topological representations[J]. Pattern Recognition Letters, 2017, 87: 177-185.

[63] CURRY J, MUKHERJEE S, TURNER K. How many directions determine a shape and other sufficiency results for two topological transforms[EB/OL]. [2022-05-19]. https://arxiv.org/abs/1805.09782.

[64] GHRIST R, LEVANGER R, MAI H. Persistent homology and Euler integral transforms[J]. Journal of Applied and Computational Topology, 2018, 2(1): 55-60.

[65] BELTON R L, TERESE B. Learning Simplicial Complexes from Persistence Diagrams[EB/OL]. [2022-05-08]. https://par. nsf.gov/biblio/10073868.

[66] BELTON R L, FASY B T, MERTZ R, et al. Reconstructing embedded graphs from persistence diagrams[J]. Computational Geometry, 2020, 90: 101658.

[67] FASY B T, MICKA S, MILLMAN D L, et al. The first algorithm for reconstructing simplicial complexes of arbitrary dimension from persistence diagrams[EB/OL]. [2022-05-29].https://arxiv.org/abs/1912.12759v2.

[68] ATTENE M, CAMPEN M, KOBBELT L. Polygon mesh repairing: an application perspective[J]. ACM Computing Surveys, 2013, 45(2): 15.

[69] YIN K X, HUANG H, ZHANG H, et al. Morfit: interactive surface reconstruction from incomplete point clouds with curve-driven topology and geometry control[J]. ACM Transactions on Graphics, 2014, 33(6): 202.

[70] SHARF A, LEWINER T, SHAMIR A, et al. Competing fronts for coarse–to–fine surface reconstruction[J]. Computer Graphics Forum, 2006, 25(3): 389-398.

[71] ZHOU S Z, JIANG C Y, LEFEBVRE S. Topology-constrained synthesis of vector patterns[J]. ACM Transactions on Graphics, 2014, 33(6): 215.

[72] HUANG Z Y, ZOU M, CARR N, et al. Topology-controlled reconstruction of multi-labelled domains from cross-sections[J]. ACM Transactions on Graphics, 2017, 36(4): 1-12.

[73] LAZAR R, DYM N, KUSHINSKY Y, et al. Robust optimization for topological surface reconstruction[J]. ACM Transactions on Graphics, 2018, 37(4): 46.

[74] BRüEL-GABRIELSSON R, GANAPATHI-SUBRAMANIAN V, SKRABA P, et al. Topology-aware surface reconstruction for point clouds[J]. Computer Graphics Forum, 2020, 39(5): 197-207.

[75] CARR H, SNOEYINK J. Path seeds and flexible isosurfaces - using topology for exploratory visualization[EB/OL]. [2022-06-20]. https://dl.acm.org/doi/abs/10.5555/769922. 769927.

[76] DE FLORIANI L, FUGACCI U, IURICICH F, et al. Morse complexes for shape segmentation and homological analysis: discrete models and algorithms[J]. Computer Graphics Forum, 2015, 34(2): 761-785.

[77] BREMER P T, HAMANN B, EDELSBRUNNER H, et al. A topological hierarchy for functions on triangulated surfaces[J]. IEEE Transactions on Visualization and Computer Graphics, 2004, 10(4): 385-396.

[78] GüNTHER D, JACOBSON A, REININGHAUS J, et al. Fast and memory-efficienty topological denoising of 2D and 3D scalar fields[J]. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(12): 2585-2594.

[79] JACOBSON A, WEINKAUF T, SORKINE O. Smooth shape-aware functions with controlled extrema[J]. Computer Graphics Forum, 2012, 31(5): 1577-1586.

[80] WEINKAUF T, GINGOLD Y, SORKINE O. Topology-based smoothing of 2D scalar fields with C1-continuity[J]. Computer Graphics Forum, 2010, 29(3): 1221-1230.

[81] BRüEL-GABRIELSSON R B, NELSON B J, DWARAKNATH A, et al. A topology layer for machine learning[EB/OL]. [2022-06-19]. http://proceedings.mlr.press/v108/gabrielsson20a. html.

[82] GAO D P, CHEN J H, DONG Z T, et al. Connectivity-guaranteed porous synthesis in free form model by persistent homology[J]. Computers & Graphics, 2022, 106: 33-44.

[83] ANAI H, CHAZAL F, GLISSE M, et al. DTM-based filtrations[M]//Topological Data Analysis. Cham: Springer International Publishing, 2020: 33-66.

[84] FERRI M. Persistent topology for natural data analysis—a survey[M]//Towards Integrative Machine Learning and Knowledge Extraction. Cham: Springer International Publishing, 2017: 117-133.

[85] GASARCH W, FASY B T, WANG B. Open problems in computational topology[J]. ACM SIGACT News, 2017, 48(3): 32-36.

[86] CERRI A, FROSINI P. Necessary conditions for discontinuities of multidimensional persistent Betti numbers[J]. Mathematical Methods in the Applied Sciences, 2015, 38(4): 617-629.

[87] LEYGONIE J, OUDOT S, TILLMANN U. A framework for differential calculus on persistence barcodes[J]. Foundations of Computational Mathematics, 2022, 22(4): 1069-1131.

[88] SOLOMON E, WAGNER A, BENDICH P. A fast and robust method for global topological functional optimization[EB/OL]. [2022-05-17]. https://arxiv.org/abs/2009.08496.

Computer aided topological design——survey on geometric design and processing based on persistent homology

DONG Zhe-tong1,2, LIN Hong-wei1,2

(1. School of Mathematical Sciences, Zhejiang University, Hangzhou Zhejiang 310027, China; 2. State Key Laboratory of CAD&CG, Zhejiang University, Hangzhou Zhejiang 310058, China)

Persistent homology is an effective method to compute topological features with different scales. It captures the birth and death time from a nested sequence of simplicial complexes, and employs the life span of a topological feature to measure its geometric scale and significance. The extraction and application of topological features play an important role in geometric design, spawning some studies on geometric design based on persistent homology. In this paper, we introduced the application studies in two aspects, i.e., the feature extraction of persistent homology and the persistent homology-based modeling and optimization. In the feature extraction of persistent homology, we introduced various methods for topological feature extraction from point clouds and triangular meshes, respectively. Meanwhile, the pipeline for applying topological features to some geometric design problems was summarized. In the persistent homology-based modeling and optimization, we reviewed the simplicial complex reconstruction methods based on topology transform, topology-aware surface reconstruction methods, and topological denoising and optimization based on persistent homology.

persistent homology; topological feature extraction; shape reconstruction; denoising and optimization; geometric design; topological design

TP 391

10.11996/JG.j.2095-302X.2022060957

A

2095-302X(2022)06-0957-10

2022-07-31；

：2022-10-16

國家自然科學(xué)基金項(xiàng)目(61872316，61932018)

董哲同(1995-)，男，博士研究生。主要研究方向幾何與拓?fù)湓O(shè)計(jì)。E-mail：ztdong@zju.edu.cn

藺宏偉(1973-)，男，教授，博士。主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)、計(jì)算機(jī)輔助拓?fù)湓O(shè)計(jì)、量子圖形學(xué)等。E-mail：hwlin@zju.edu.cn

31 July，2022；

16 October，2022

National Natural Science Foundation of China (61872316, 61932018)

DONG Zhe-tong (1995-), PhD candidate. His main research interests cover geometric and topological design. E-mail：ztdong@zju.edu.cn

LIN Hong-wei (1973-), professor, Ph.D. His main research interests cover geometric and topological design, quantum graphics, etc. E-mail：hwlin@zju.edu.cn