計算機輔助拓撲設計——持續同調在幾何設計和處理中的應用

董哲同，藺宏偉

計算機輔助拓撲設計——持續同調在幾何設計和處理中的應用

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

(1. 浙江大學數學科學學院，浙江 杭州 310027；2. 浙江大學CAD&CG國家重點實驗室，浙江 杭州 310058)

持續同調是一種計算不同尺度拓撲特征的有效方法。其從一簇向后包含的單純復形序列中提取出拓撲特征的出現和消失時刻，并使用拓撲特征的“生命周期”來量化地衡量該特征的幾何尺度和重要程度。拓撲特征的提取與應用在幾何設計中扮演著重要角色，催生出了一些基于持續同調的幾何設計研究。從持續同調特征的提取與基于持續同調的建模和優化兩方面進行綜述，在持續同調特征的提取方面，介紹了從點云和三角網格數據中提取拓撲特征的不同方法，總結了拓撲特征在部分幾何設計問題中的應用路徑。在建模和優化方面，綜述了基于拓撲變換的單純復形重建方法、拓撲可感知的曲面重建方法與基于持續同調的拓撲去噪和優化方法。

持續同調；拓撲特征提??；形狀重建；去噪與優化；幾何設計；拓撲設計

1 緒 論

持續同調以計算幾何和代數拓撲為主要數學工具，從一簇向后包含的單純復形序列中計算各維同調等價類出現和消失的時刻，并將出現-消失點對作為復形序列拓撲特征。持續同調的提出和發展可以追溯到20世紀90年代?！俺掷m性”(persistence)的概念獨立地出現在了幾乎處于同一時期的3組研究項目中，即學者Frosini，Ferri及其合作者的工作，學者Robins的博士論文和學者EDELSBRUNNER的項目[1]。2000年，美國Duke大學的學者EDELSBRUNNER等[2]系統地提出了持續同調的定義和算法，此后持續同調理論和計算方面的研究不斷涌現，如文獻[3-4]分別給出了持續同調和多維度持續同調的理論和計算方法。2009年，CARLSSON[5]的奠基性工作使得拓撲數據分析(topological data analysis)作為新興的研究領域得以誕生。值得一提的是，持續同調與Morse理論有著緊密的聯系，如持續性可以用于簡化Morse-Smale復形的拓撲結構[6]，Morse理論也可加速持續同調的計算[7]。持續同調可用于從采樣點云推斷采樣流形可能的拓撲結構，從定義在單純復形上的一類標量函數導出的單純復形序列中提取各維度的拓撲特征。該方法能定量地反映拓撲特征的幾何尺度，區分重要拓撲特征和噪聲特征，對輸入數據中的微小噪聲和擾動不敏感?；谝陨蟽烖c，持續同調在解決分子結構分析[8]、腦與神經科學[9]、醫學圖像處理[10]等領域的一些科學問題上獲得了成功的應用。

計算機輔助幾何設計是一門由微分幾何、數值計算等數學分支與計算機交叉而產生的學科，主要以三維物體表示、建模、處理、分析和模擬為研究重點。從20世紀70年代以來，自由曲線曲面的表示、設計、顯示、分析和處理等是計算機輔助幾何設計的主要研究對象和內容[11]，并取得的豐富研究成果，為三維建模軟件的開發應用建立了理論基礎。然而，由于缺乏有效的計算工具，在幾何設計和處理中出現的一些拓撲問題，無法得到有效的系統解決方法。隨著以持續同調(persistent homology)[2-3,5]為代表的計算拓撲技術的發展，三維形狀的拓撲特征可以被量化地估計和表達，從而方便地應用于形狀分析、分類與檢索、拓撲可控的優化與建模等幾何設計問題中。持續同調的成功應用為眾多的代數拓撲理論走向應用提供了潛在的可能性，為解決幾何設計和處理中的拓撲問題提供可能的解決方案，從而為計算機輔助拓撲設計這一新興研究領域提供了潛在的理論支持。

近十年以來，持續同調被系統應用于幾何設計和幾何處理，主要解決三維形狀的拓撲特征提取、分析以及形狀建模中遇到的拓撲相關問題，逐漸形成了計算機輔助拓撲設計這一研究領域。在三維形狀拓撲特征提取方面，持續同調采用持續圖(persistence diagram)[2]或持續條碼(persistence barcode)[5]編碼同調特征，研究者們將這些特征轉化為關于持續圖度量穩定且易于使用的向量化形式，以便進一步應用于形狀分析、分類和檢索等問題中。在三維形狀建模方面，如何使用提取的拓撲特征恢復三維形狀是近年來研究的一個熱點問題之一。持續同調可以用于區分重要的拓撲特征和噪聲特征，在保拓撲尖銳特征的優化中也發揮了重要作用。另外，通過持續同調構造的持續逆映射(persistence inverse mapping)[12]使得拓撲可控的建模技術得到了發展。

2 預備知識：持續同調

持續同調致力于從一簇向后包含的單純復形序列中提取不同尺度和不同維度的拓撲特征，如連通分支(0維特征)、獨立環結構(1維特征)和獨立空腔結構(2維特征)等，并且反映這些特征隨尺度參數變化的出現和消失情況，以此衡量這些拓撲特征的幾何尺度和重要程度。單純復形是用于計算持續同調的基本組合結構，一個單純復形通常是指由點(0-單形)、線(1-單形)、三角面(2-單形)和四面體(3-單形)等不同維度的單形按照以下規則組合而成的復合結構：①單純復形中任意單形的面(face)屬于該單純復形；②任意2個單形的交要么為空，要么為公共面。

為了從采樣點云中推斷采樣形狀的拓撲結構，需要依托點云建立一系列向后包含的單純復形，也稱過濾(filtration)。建立過濾的方法有很多，如文獻[13-15]所示方法，其中Vietoris-Rips復形[13]較為常用。該方法的基本思想是在每一點上放置一個閉球，所有球的半徑參數逐漸增加。在某一參數下，若存在個點，滿足其閉球兩兩相交，則這個點構成一個(-1)-單形。另外，將定義在形狀上的標量函數做線性逼近生成定義在對應單純復形上的分片線性函數也能生成過濾，用于提取按該標量函數數值大小排列時單純復形的拓撲結構變化信息。通?？梢詫渭儚托伟凑辗制€性標量函數數值從小到大或從大到小排列分別生成下水平過濾或上水平過濾。值得一提的是，Zig-zag持續方法[16]的出現使得過濾不再局限于向后包含的單純復形序列。

代數拓撲是持續同調采用的主要數學工具，其將單純復形中的單形視為代數運算的算術元素。在單純同調的簡單情形下，第維的所有單形按照模2加法構成-鏈群C，其中的元素由一些-單形的算術組合構成，稱為-鏈。為了反映從C到C-1元素的邊界關系，定義邊界算子?:C→C-1，該算子將一個-鏈映射為其中每個單形所有(-1)-面的代數和形式，稱為-鏈的邊界。對于任意1，相鄰2個維度的邊界算子的復合為零算子，即?°?-1=0。為了代數地表示獨立孔洞結構，定義邊界算子?的零空間Z={?C:?=0}為閉鏈群，邊界算子?+1的像空間B={?C:$?C+1s.t.?+1=c}為邊緣鏈群。直觀地，一個獨立環結構是一類非邊界閉鏈，即不是任何高維鏈邊界的閉鏈。由于相鄰邊界算子復合為零，所以可以用商群Z/B定義同調群H，同調群中的元素表示獨立環結構的等價類，是一類重要的拓撲特征。同調群的階(rank)稱為Betti數，反映拓撲特征的個數，如0維Betti數指示單純復形中連通分支的個數，1維Betti數指示獨立環結構的個數。文獻[17-18]提供了更多同調和計算同調的細節。

在過濾中，獨立孔洞結構會隨著參數變化而出現、存在和消失，持續同調能從過濾中計算同調特征的出現和消失對應的參數時刻，采用出生-死亡(birth-death)點對表示對應的同調特征。定義死亡值與出生值的差為持續值，該指標衡量拓撲特征的生命周期，以便推測該特征是否為采樣形狀的重要特征，并且衡量該特征的幾何尺度。如圖1所示，隨著“時間參數”的增加，復形序列中陸續有拓撲特征出現和消失。圖1(a)藍色和橙黃色線段分別表示連通分支(0維拓撲特征)和獨立環結構(1維拓撲特征)的生命周期，這些嵌入到平面中的線段構成了一個拓撲特征表示，稱為持續條碼。進一步，將出生-死亡點對嵌入到平面得到持續圖，如圖1(b)所示。持續圖和持續條碼為持續同調提供了緊湊的拓撲特征表示。另外，Wasserstein距離和bottleneck距離[14]可以用于度量2個持續圖或持續條碼之間的相似性。進一步，在滿足不同條件時，持續同調具有一些穩定性結論[13,19-21]，即當點云或形狀上的標量函數發生擾動時，在這些距離的意義下，持續圖或持續條碼的擾動可以被該擾動的常數倍控制。這些穩定性結論說明了持續同調對數據中的噪聲不敏感，在實踐中具有重要的意義。

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

過濾過程可以視作單形依參數大小依次添加到單純復形中，單形的添加往往會對應某一拓撲特征的出現或消失。拓撲特征的出生值和死亡值分別對應2個不同的單形。文獻[12]據此提出了拓撲逆映射來追蹤持續點對對應的單形對，在形成過濾的標量函數滿足一定條件時，可以構造良好定義的拓撲逆映射，該映射也可將持續點對映射為對應的臨界點對。該映射是基于持續同調的拓撲可控方法的重要工具，據此可以計算有關持續圖的目標函數關于標量場中各參數的梯度。如圖2所示(虛線箭頭給出了持續圖上的點到拓撲空間上點對的映射關系)，是定義在拓撲空間上的標量函數，按生成的下水平過濾計算持續圖。持續逆映射將持續圖上的點((),())映射到臨界值點對(,)，其含義是將對應的連通分支的出現追溯到點對應的單形在下水平過濾中的出現，將該連通分支的消失追溯到點對應的單形在下水平過濾中的出現[22]。

圖2 持續逆映射的示意圖[22]

3 持續同調拓撲特征及其應用

從幾何形狀中盡可能完整地提取形狀某一方面或某幾方面的特征是形狀分析、分類和檢索等幾何處理問題中的重要步驟。傳統的拓撲不變量，如Betti數、虧格和歐拉示性數等，雖然能提供拓撲特征的數量信息且便于計算，但是卻不能具體地反映拓撲結構的幾何尺度，對幾何數據中的噪聲非常敏感，即使局部擾動也會導致這些傳統拓撲不變量的較大變化。持續同調能通過點云估計采樣形狀的拓撲結構，計算三維形狀按某一標量函數生成過濾的拓撲特征。計算所得的持續圖能將拓撲特征與形狀的幾何進行關聯，提供幾何尺度的量化指標，且對輸入數據的噪聲不敏感。本節綜述使用持續同調從點云和空間網格中提取拓撲特征的相關方法，并總結拓撲特征表示在幾何設計和處理中的應用。

3.1 點云的持續同調特征提取方法

空間點云是在三維空間中的一個點集，通常通過掃描或采樣三維物體獲得，是幾何設計中一種常用的形狀表示。一些幾何設計任務需要提取點云中的拓撲特征進行分析，為了重建拓撲結構滿足預期的三維形狀，也需要從點云中提取拓撲先驗信息。持續同調通過建立復形過濾的方式計算持續圖，其中的點對分別表示復形序列中對應拓撲特征的出現和消失的參數時刻，而構造復形過濾有諸多方法。與Vietoris-Rips 復形類似，?ech復形[13]要求在單形的所有頂點對應的閉球有非空公共交集。Alpha復形[23]則通過Delaunay三角化生成關于點云的一組子復形。而當點云數據規模較大時，為了減少過濾中單純復形的單形數量且反映單純復形的主要拓撲結構，Witness復形[14]通過保留關鍵點和采樣的方式構造近似復形過濾。另外，在構造Vietoris-Rips復形的過程中，可以通過點云下采樣或設置最大半徑參數的方式來近似地計算持續圖[24]。

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

在點云處理中，往往只需要通過點云估算采樣形狀的大致拓撲特征，持續值較小的拓撲特征往往被視為噪聲。因此，采用搭建神經網絡來估計持續圖成為了提升持續同調計算效率的一個新途徑。SOM等[29]在提取圖像特征時率先提出了一種基于卷積神經網絡的架構估算持續圖的向量化表示。在三維點云處理領域，文獻[25]基于EdgeConv 卷積層[30]提出了一種快速估計點云Vietoris-Rips 復形過濾的持續圖向量化表示持續圖像(persistence images)[31]的網絡架構。該神經網絡使用大量點云數據及對應的持續圖向量化表示作為訓練數據，能端到端高效地估計持續同調特征。實驗表明，估計所得的持續圖像與真實持續圖像偏差較小。但是該網絡架構依賴于在點云上建立圖結構，在理論上未說明關于點云數據的噪聲和擾動具有穩定性。DE SURREL等[32]基于Deep sets[33]提出了一種快速估計點云的Vietoris-Rips復形過濾的持續圖的網絡架構。該方法借助Deep sets的理論結果可以簡潔地推導出估計持續圖的穩定性結論，且估計過程高效，計算結果也較為精確。由于在評估實驗中，此類方法多使用點云標準數據集或合成數據集，因此尚不清楚此類方法在真實、復雜數據集上的表現。

3.2 三角網格的持續同調特征提取方法

空間三角網格表示的三維形狀可以視為嵌入到空間的單純復形。除了使用單純同調計算Betti數或同調生成元或使用點云采樣并計算持續同調獲得拓撲特征以外，還有一些方法可用于提取三角網格的拓撲特征，如基于網格測地距離的持續同調方法，基于特征函數過濾的持續同調方法和拓撲變換方法。

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

基于特征函數過濾的持續同調方法是提取網格模型特征的一類方法，即利用定義在這個網格上的標量函數按函數值大小生成復形過濾，計算持續同調。由于所選擇的標量函數通常反映三維形狀的局部特征，因此稱這類標量函數為“特征函數”[35]。這類函數的選擇往往依賴于實際應用，標量函數中參數的調整也多是經驗性的。一般地，可以選擇熱核函數 (heat kernel signature)[36]或波核函數(wave kernel signature)[37]作為特征函數。如DONG等[38]使用熱核函數設計多尺度拓撲描述子來分類多孔結構。文獻[35, 39]也利用熱核函數作為特征函數，以便將不同時間參數下的持續圖組合為多尺度的描述子。

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

3.3 拓撲特征在幾何處理中的應用

持續同調從三維點云和三角網格中提取拓撲特征，并以持續圖的方式展示這些不同幾何尺度的特征。然而，計算2個持續圖之間的Wasserstein距離或bottleneck距離是比較耗時的，特別是當持續圖中有大量的點對時，這是因為距離的計算依賴于點對集合之間的最優匹配的求解[45]。另外，諸多統計分析工具，如求平均值等，以及支持向量機等用于分類或聚類的機器學習常用工具不能以持續圖作為輸入，因此需要將持續圖進行向量化，以便將這些拓撲特征應用于幾何處理的相關問題中。

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

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

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

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

4 基于持續同調的建模和優化

三維形狀的拓撲是一類重要的性質，也是幾何設計關注的重要目標之一。相比于基于經典的離散拓撲不變量的拓撲可感知建模方法，持續同調為形狀建模和優化提供了新思路。

4.1 基于拓撲特征的單純復形重建

計算持續圖是一個提取特征的過程，持續圖是一組幾何多尺度的拓撲特征，被應用于形狀分類等幾何設計問題中，而使用這些拓撲特征恢復和重建三維形狀是一個逆向工程。PHT將一個單純復形按照不同方向投影，產生一簇持續圖。文獻[41]從理論上證明了PHT在二維和三維空間上的單射性，即一簇持續圖至多只與一個單純復形對應。CURRY等[63]與GHRIST等[64]進一步推廣了該結論，分別獨立證明了在任意維度的歐氏空間中的可構造子集上，ECT具有單射性，并由此導出PHT的單射性。這意味著可以嘗試從PHT產生的一簇持續圖中恢復單純復形。

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

4.2 拓撲可感知的三維建模

幾何設計的一個重要研究課題是建模具有正確或理想的拓撲的三維形狀。在部分研究中，往往采用后處理[68]或人機交互[69]的方式移除或修改生成形狀上的拓撲錯誤，這些方式依賴于用戶對形狀進行局部修正。而部分研究[70-73]則通過使用虧格和Betti數等經典拓撲不變量設計約束條件，通過定義能量函數的方式優化組合單元，從而重建出拓撲正確的幾何形狀，如曲面。這類方法能保證生成具有拓撲不變量的形狀，然而經典拓撲不變量不能描述拓撲特征的幾何尺度，優化過程多采用動態規劃，在一些復雜的算例中，算法的時間和空間復雜度會呈指數級。

基于持續同調的拓撲可感知方法利用文獻[12]提出的持續逆映射建立一套基于梯度下降的連續優化框架。相比于基于經典拓撲不變量的離散優化框架，這類方法易于理解和實現，且可以使用能描述拓撲特征幾何尺度的持續圖作為重建和優化的先驗信息。BRüEL-GABRIELSSON等[74]提出了一種基于持續逆映射的拓撲可感知的從點云重建曲線和曲面的方法，根據持續圖上點對的相對位置設計拓撲損失函數，并采用梯度下降的連續優化框架進行優化。具體而言，首先以點云中的點為中心的多元高斯函數構造似然函數，并將空間離散為自適應的單純復形；使用該似然函數為每一個單形分配一個兼容的單形值；然后構造上水平過濾，計算持續圖。最小化拓撲損失函數，計算損失函數關于似然函數中參數的梯度，使用梯度下降的方式更新參數；最后從優化后的似然函數對應的底復形中提取提升的同調表示元作為重建的曲線或曲面。由于該方法使用從似然函數中提取的同調表示元作為重建形狀，所以曲線、曲面的光滑性不高。

為了提高重建曲面的光滑性并同時保障目標曲面具有預期的拓撲，文獻[22]提出了一種基于持續逆映射的拓撲可控的隱式曲面重建方法。該方法首先計算點云的符號距離函數，離散包圍盒為立方復形，并使用B樣條函數擬合離散符號距離值；將重建目標對應的持續圖作為拓撲預期用于設計拓撲目標函數；同樣采用梯度下降的連續優化框架，最小化目標函數并優化B樣條函數中的控制系數；最后根據優化后的持續圖上主要特征點對的位置決定提取的等值面。該方法的優點在于可以通過優化控制水平集中較為顯著的拓撲結構的幾何尺度。如圖4所示，通過最小化持續圖上持續值第二大的點(綠色點)對應的持續值，該優化框架消除了較小尺度的環柄圈，且生成的隱式曲面具有較好的光滑性。該方法也有一些缺陷，如與其他基于梯度下降的連續優化框架類似，該優化方法可能會收斂到局部最優解，且每次優化迭代都需要計算持續圖；不能很好地區分和優化較小的拓撲特征。

4.3 拓撲去噪與優化

圖像與信號處理中的一個重要問題是研究如何在保留重要特征的同時去除數據中的噪聲。同樣地，拓撲去噪旨在保留拓撲尖銳點和尖銳邊等特征，并且去除數據中的拓撲噪聲。如CARR和SNOEYINK[75]通過提取輸入數據的輪廓樹并做簡化以去除一些不必要的細微的拓撲特征，但該方法不能保證去除一些小的噪聲環結構。另外一類常用的方法是基于Morse-Smale復形[76]的拓撲去噪和簡化方法。如BREMER等[77]利用Morse-Smale復形消除(cancellation)技術簡化復形結構，并在每次迭代過程中光滑單純復形中單形內部的標量函數，從而保證調整后的單純復形遵循一定的拓撲結構，并且生成光滑的二維標量場。然而該方法不能區分拓撲尖銳特征并進行保留。

圖4 文獻[22]方法

為了保留重要拓撲特征并去除噪聲，GüNTHER等[78]利用持續同調為拓撲特征進行分級，將文獻[79-80]提出的二維標量函數重建方法擴展到解決三維標量函數的去噪問題上。該方法首先計算標量場中的極值，從上/下水平過濾中計算持續圖并按照持續值大小給極值點分級，確定拓撲尖銳點。再將拓撲去噪問題建模為離散優化問題，選定需要保留的拓撲尖銳點且避免新的尖銳點出現。采用線性化約束和凸化可行域的技術將優化問題轉化為二次規劃，并進一步轉化為錐規劃問題求解。在求解過程中，采用區域分解技術使得計算更加高效，內存使用更少，可快速地處理大規模標量場的去噪。但該方法是一種啟發式算法，不能保證優化問題的解是全局最優解甚至局部最優解。

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

圖5 文獻[82]方法

5 總結與展望

一方面，自2000年文獻[2]提出持續同調的基本概念以來，持續同調的理論體系得到了完善，并結合統計學和數據科學等其他學科，發展出了拓撲數據分析這一門新興的交叉學科。另一方面，由于持續同調的發展建立在計算幾何和計算拓撲的基礎之上，所以在幾何設計和處理領域也涌現出了大量持續同調的應用研究。本文首先簡要地介紹了持續同調的發展歷程和核心概念。在拓撲特征的提取和應用方面，綜述了使用持續同調提取采樣形狀的點云和三角網格模型拓撲特征的方法，并總結了持續同調特征在形狀分類、分析、匹配和檢索等幾何處理問題中的應用。另外，還從基于拓撲變換的單純復形重建、拓撲可感知的三維曲面重建和拓撲去噪和優化3個方面綜述了持續同調在形狀建模和優化中的已有研究。

雖然持續同調在理論和應用方面取得了長足的發展和進步，但仍然有一些問題值得研究。文獻[84-85]中列舉了有關持續同調理論的公開問題。在應用方面，持續同調的高效和快速計算問題也值得研究。由于多維度持續同調[4]不存在緊湊的拓撲特征表示[86]，如何提取和組織多層次拓撲特征是一個值得研究的問題。另外，基于持續同調的連續優化框架的理論也不斷在完善[81, 87]，更多的優化思路被不斷地提出[88]，為持續同調在幾何設計中的應用奠定了堅實的基礎。因此，基于持續同調的幾何設計技術具有廣闊的發展前景，并正在促進“計算機輔助拓撲設計”這一新興研究領域的發展。

[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] 梁友棟, 劉鼎元, 金通洸. 計算幾何的現狀與趨勢[C]//1982年計算幾何討論會. 杭州: 浙江大學學報, 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

國家自然科學基金項目(61872316，61932018)

董哲同(1995-)，男，博士研究生。主要研究方向幾何與拓撲設計。E-mail：ztdong@zju.edu.cn

藺宏偉(1973-)，男，教授，博士。主要研究方向為計算機輔助幾何設計、計算機輔助拓撲設計、量子圖形學等。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