顧險峰, 雷 娜
(1.紐約州立大學石溪分校計算機系, 紐約11794; 2.大連理工大學軟件學院, 遼寧大連116620)
?
計算共形幾何簡介
顧險峰1, 雷娜2
(1.紐約州立大學石溪分校計算機系, 紐約11794;2.大連理工大學軟件學院, 遼寧大連116620)
計算共形幾何是數(shù)學與計算機科學的交叉領(lǐng)域.本文介紹了計算共形幾何中理論基礎,計算方法及其在工程領(lǐng)域中的應用等.基本理論概念包括共形映射,單值化定理,共形模,擬共形映射,??臻g等.基本計算方法包括調(diào)和映照方法,基于黎曼面理論的全純微分方法,基于幾何分析的曲面Ricci流方法.基本應用涵蓋了醫(yī)學圖像,機械制造,數(shù)字媒體和虛擬/增強現(xiàn)實等領(lǐng)域.
共形幾何; 黎曼面; 單值化; 調(diào)和映照; 全純微分; 曲面Ricci流
幾何是自然的語言,大自然亙古不變的偉大樂章是由幾何譜寫而成.對于深邃奧妙的幾何真理的不懈追求是人類社會永恒的主旋律之一.幾何理論和方法為人類提供了認識自然、改造自然的強有力的工具.依隨人類對于幾何真理的持續(xù)探索,基礎理論的提煉和深化,人類認識到她的巨大審美價值,越來越多的人認識和體會到幾何內(nèi)在的優(yōu)美和深刻.依隨幾何計算手段的建立和發(fā)展,人類認識到她的巨大實用價值,幾何方法已經(jīng)被廣泛應用到社會實踐的各個方面,極大地推動了生產(chǎn)力的發(fā)展.本文簡單介紹共形幾何的理論和方法在醫(yī)療和工程中的應用,使讀者得以領(lǐng)略共形幾何的簡潔優(yōu)美,和她解決實際問題的威力.
計算共形幾何是一個交叉學科,根植于純數(shù)學領(lǐng)域,例如黎曼面理論,復分析,微分幾何,代數(shù)拓撲,偏微分方程等.計算共形幾何已經(jīng)被應用于計算機科學中的諸多領(lǐng)域,包括計算機圖形學,計算機視覺,幾何建模,醫(yī)學圖像和計算幾何等.
歷史上,計算共形幾何也被廣泛應用于工程領(lǐng)域[1],例如在電磁學,聲學振動膜,彈性力學,熱傳導與流體力學等.這些應用絕大多數(shù)基于平面區(qū)域之間的共形變換.近來,隨著三維掃描技術(shù)的發(fā)展,計算能力的提升,以及數(shù)學理論的進一步發(fā)展,人們已經(jīng)把計算共形幾何理論和算法從平面區(qū)域推廣到了具有任意拓撲的度量曲面.
所謂共形幾何就是研究保角變換下不變量的一門學問,她為研究曲面間的變換和映射提供了理想的理論工具,而曲面比較和匹配在諸多工程和醫(yī)療領(lǐng)域中具有根本的重要性.圖1顯示了人臉曲面的保角映射的實例.左幅三維人臉曲面由三維掃描儀獲取,右幅是保角映射的二維平面像.從圖中可以看出,保角映射局部上是相似變換,雖然整體上具有很大的畸變,局部上是保持形狀不變的.因此,保角變換又被稱為是保形變換,或共形變換.
圖1 人臉曲面的保角映射
圖2顯示了保角變換(共形變換)的幾何特性.我們在二維圓盤中鋪上不同的圖案(稱為紋理),由圖1中的共形映射拉回到三維人臉曲面上,得到人臉曲面上不同的紋理貼圖.如果紋理為黑白相間的棋盤格,如左幅圖所示,棋盤格的四個角在人臉上依然是直角,這顯示了共形映射保持角度不變.如果紋理為由許多彼此相切的微小圓形構(gòu)成的模式,微圓在人臉上的像依然是微圓,這顯示了共形映射保持無窮小圓不變.保角性和保圓性都是共形映射的本質(zhì)特性.作為對比,圖3顯示了一個非共形映射的實例.同樣的人臉,經(jīng)由一般的微分同胚映到二維圓盤.圓盤上的微圓域被拉回成人臉上的橢圓域.人臉的幾何特征沒有被映射所保持,局部幾何發(fā)生了很大的畸變.
圖2 共形映射的保角和保圓特性
圖3 非共形映射既不保圓,又不保形
人臉曲面到平面圓盤的共形映射并不唯一,兩個共形映射之間相差一個莫比烏斯變換.單位圓盤到自身的所有共形映射都是莫比烏斯變換,所有的莫比烏斯變換構(gòu)成一個三維的李群.圖4展示了另一共形變換的實例,一張女孩的臉被共形地映到平面單位圓盤,不同的映射之間相差莫比烏斯變換.
圖4 莫比烏斯變換
固定一個拓撲曲面,我們考察曲面上所有可能的黎曼度量.如果兩個黎曼度量彼此相差一個標量函數(shù),則這兩個度量彼此共形等價.每個黎曼度量的共形等價類被稱為是曲面的一個共形結(jié)構(gòu).拓撲曲面上所有的共形結(jié)構(gòu)構(gòu)成所謂的??臻g.帶有共形結(jié)構(gòu)的曲面被稱為是黎曼面.一個共形結(jié)構(gòu)的全系不變量被稱為是黎曼面的共形模.
人臉曲面是單聯(lián)通的曲面,拓撲非常簡單.對于一般曲面,其拓撲由是否可定向,環(huán)柄數(shù)目(虧格),邊界數(shù)目所決定.單值化定理斷言:所有帶有黎曼度量的可定向曲面都可以共形地變換到三種標準空間中的一種:球面,歐氏平面和二維雙曲空間.如圖5所示,第一列為虧格為0的女孩雕塑表面,共形地映到球面上;第二列是虧格為1的小貓雕塑,它被周期性地共形地映到歐氏平面上.任意兩個周期之間相差一個平移.第三列是高虧格的曲面,我們姑且稱之為扭曲的雙耳花瓶,它被周期性地共形地映到雙曲平面上,任意兩個周期之間相差一個莫比烏斯變換.莫比烏斯變換保持雙曲長度不變,亦被稱為雙曲剛體變換.單值化定理在曲面幾何理論中占據(jù)中心地位.
圖5 封閉曲面單值化定理
帶邊界曲面的單值化定理如圖6所示,曲面被共形映到標準空間去掉一些圓盤.大千世界,各種曲面千變?nèi)f化,難以盡訴,但是萬變不離其中.這一理論對于工程實踐意義重大,這意味著所有三維幾何處理的問題都可以轉(zhuǎn)換為三種標準空間中的二維問題,這一轉(zhuǎn)換極大地簡化了問題的難度,增加了效率.
一般的微分同胚將無窮小圓映成無窮小橢圓,橢圓的偏心率(長短軸之比)和方向定義了Beltrami系數(shù).基本上,映射和其Beltrami系數(shù)彼此相互決定.Beltrami系數(shù)的模有界的映射被稱為是擬共形映射.擬共形映射給出了曲面間微分同胚的理論基礎.
圖6 帶邊界曲面單值化定理
計算共形幾何的計算方法豐富多彩,涉及到的數(shù)學分支非常廣泛.我們以圖5的單值化定理為例,來解釋基本的計算方法.
調(diào)和映照曲面間的映射所誘導的彈性形變能量被表示成調(diào)和能量,使調(diào)和能量達到最優(yōu)的映射被稱為是調(diào)和映照.對于虧格為0的封閉曲面,調(diào)和映射必為共形映射.我們從一個微分同胚出發(fā),運用非線性熱流方法,逐步改變映射,使得調(diào)和能量逐漸減小,直至達到調(diào)和映照.
Hodge分解共形映射的導數(shù)是全純微分,由一對彼此共軛的實調(diào)和微分形式構(gòu)成.Hodge定理斷言:流形的每一個de Rham上同調(diào)類中有且僅有一個調(diào)和微分形式.因此我們計算曲面的上同調(diào)群,然后用橢圓型偏微分方程求解調(diào)和微分形式,再由調(diào)和形式構(gòu)成全純微分,通過積分得到共形映射.圖5中,虧格為1的曲面的單值化就是由此算出的.
Ricci流Ricci 曲率流由Hamilton發(fā)明,用來證明龐加萊猜測.Ricci流的基本思想是將黎曼度量變形,其變形程度正比于當前的Ricci曲率,使得Ricci曲率依隨時間演化,其演化規(guī)律滿足反應-擴散方程,最后曲率處處成為常數(shù).圖5中,高虧格曲面的單值化就是由離散曲率流的方法計算出來.目前,不存在其他可以替代的方法.
下面的計算問題,是計算共形幾何中的基本任務.這些問題本質(zhì)上是相關(guān)的:
(i) 共形結(jié)構(gòu)給定一個帶有黎曼度量的曲面,計算其內(nèi)蘊共形結(jié)構(gòu)的各種表示.一種方法是計算阿貝爾微分群,另一種方法是計算標準黎曼度量.
(ii) 共形模完整的共形不變量被稱為黎曼面的共形模. 對于給定的黎曼面,計算其共形模.
(iii) 標準黎曼度量拓撲曲面上的所有黎曼度量可以根據(jù)共形等價來進行分類.一個基本的定義是單值化定理,每個黎曼度量都共形于一個由常值高斯曲率誘導的黎曼度量.計算單值化度量是計算共形幾何中的根本重要問題.
(iv) 共形映射計算給定兩個共形等價的曲面之間的共形映射.這可以被歸結(jié)為計算每個曲面到標準空間上的共形映射,例如球面,平面或者雙曲空間上的圓域.
(v) 擬共形映射黎曼面之間的絕大多數(shù)微分同胚都不是共形的.它們將無窮小圓映為無窮小橢圓.如果橢圓的長短軸之比有一致的界,那么這個微分同胚被稱為擬共形映射. 黎曼面上的擬共形映射的微分由Beltrami系數(shù)表示.根據(jù)Beltrami系數(shù)可以恢復擬共形映射(可相差一個共形映射).如何從Beltrami微分計算擬共形映射是一個基本問題,并有著廣泛應用.
我們在非常廣泛的工程和醫(yī)學領(lǐng)域中展示了計算共形幾何的價值,主要原因如下:
(i) 標準域所有的度量曲面都可以被共形地映射為三種標準域之一:球面,平面或雙曲圓盤.因此我們可以把三維幾何處理問題轉(zhuǎn)化為二維問題. 這極大地簡化了算法設計和工程計算.例如某些偏微分方程的解在標準域上有封閉形式,比如單位圓盤上的泊松公式.
(ii) 根據(jù)曲率設計度量每種共形結(jié)構(gòu)都有著帶有常曲率的標準黎曼度量.這種度量在幾何處理問題中具有重要的作用.例如,在雙曲度量下,非平凡的閉圈的每個同倫類中具有唯一的閉測地線.進一步,對于給定的曲率,我們可以設計度量,這在幾何建模中起到至關(guān)重要的作用.
(iii) 一般的幾何結(jié)構(gòu)構(gòu)造其它幾何結(jié)構(gòu),往往要借助共形幾何的方法,例如仿射結(jié)構(gòu),射影結(jié)構(gòu)等等.這些結(jié)構(gòu)在很多工程領(lǐng)域中起到了根本作用.
(iv)構(gòu)造微分同胚共形映射和擬共形映射可被用于構(gòu)造曲面間的微分同胚.曲面配準和比較是計算機視覺和醫(yī)學圖像領(lǐng)域的最本質(zhì)問題.
(v)等溫坐標共形結(jié)構(gòu)可被看作是一種特殊的圖冊,使得所有的局部坐標都是等溫坐標.在這種坐標之下,黎曼度量具有最簡單的形式.因此,所有的微分算子,例如Laplace-Beltrami算子,在這種坐標下可以被很好地表示.這有助于簡化偏微分方程.等溫坐標保持局部形狀,如圖7所示,這在可視化和紋理映射中非常重要.
(a) 圓盤填充(b) 棋盤格 圖7 等溫坐標
5.1醫(yī)學圖像中的應用
依隨核磁共振技術(shù)(MRI)和CT斷層掃描技術(shù)的發(fā)展,醫(yī)學圖像被日益廣泛地應用于醫(yī)療實踐之中.例如,利用核磁共振技術(shù),病患的大腦灰質(zhì)皮層可以被迅速獲取下來.通過對灰質(zhì)皮層曲面形狀的分析,醫(yī)生可以診斷病人腦神經(jīng)系統(tǒng)存在的隱患,對于病情發(fā)展加以監(jiān)控.這一手段被廣泛應用于有關(guān)老年癡呆癥,帕金森氏綜合癥等疾病的診斷.人類大腦皮層的形狀非常復雜,不同的人之間大腦皮層曲面幾何非常不同,即便是同一個人,不同時期的大腦皮層的形狀也不相同.如何建立不同大腦皮層曲面間的映射,對不同皮層曲面加以比較,是一個非常具有挑戰(zhàn)性的問題.共形幾何提供了一種優(yōu)雅而有效的解決方法.
如圖8所示,人的大腦皮層是虧格為零的拓撲球面,可以被共形地映到單位球面上.這樣,我們?yōu)榇竽X皮層上的每一點賦予唯一的球面坐標,從而實現(xiàn)精確地定位.另一方面,不同大腦皮層之間的映射可以由球面之間的自同構(gòu)映射建立.相比于復雜曲面間的映射,球面到自身的映射非常容易建立.
圖8 共形腦圖 [4]
人的大腦皮層上的溝回具有非常重要的神經(jīng)生理學的意義.如圖9所示,重要的溝回用黃色曲線勾勒出來.中間的溝回在人的胚胎期形成,負責人的基本情感.在建立大腦皮層間的映射時,這些重要溝回需要對齊.我們沿著這些溝回將曲面切開,再共形地將曲面映到平面帶圓形孔洞的圓盤.在建立圓盤間映射的時候,我們刻意將圓形孔洞對齊,這樣就保證了原來大腦皮層曲面間映射將重要的溝回對齊.
直腸癌是人類的第四號殺手.直腸癌是由直腸息肉經(jīng)過不斷的摩擦而發(fā)生癌變轉(zhuǎn)換而來.如果在早期,通過腸鏡檢查,及時發(fā)現(xiàn)直腸息肉,并對較大的息肉進行剪除,直腸癌可以避免.因此,腸鏡檢查對于中老年人群而言非常重要.但是,傳統(tǒng)的腸鏡檢查需要對病人進行麻醉處理,病人需要承擔一定風險,對醫(yī)生的手工操作具有很高要求,費時費力,對病患具有一定的侵犯性.
圖10 基于共形幾何的虛擬腸鏡[5]
病患的直腸曲面可以由CT斷層掃描技術(shù)獲取,如圖10所示.直腸壁曲面有許多皺褶,直腸息肉有可能隱藏在這些皺褶中.傳統(tǒng)腸鏡方法無法檢查皺褶中的息肉,因此具有一定的誤診漏診率.一個自然的想法在于展平所有直腸曲面的皺褶,從而揭示所有隱藏其中的息肉和潛在病灶.我們利用共形幾何的方法,將直腸曲面周期性地映到平面,每一個周期是個長方形.所有直腸曲面的幾何信息一目了然.這種虛擬腸鏡的方法,病人不需要做麻醉,和病人無肢體接觸,不具有侵犯性.無復雜手工操作,簡便易行,提高了診斷準確率和效率.目前,這種虛擬腸鏡技術(shù)已經(jīng)廣泛應用于北美臨床診斷實踐之中.
5.2機械制造工業(yè)中的應用
汽車,輪船,飛機,火車,幾乎所有的機械設備都由數(shù)控機床加工制造.曲面幾何在制造工業(yè)中的數(shù)字表示形式是所謂的樣條曲面.樣條曲面由分片有理多項式組成.通常情況下,樣條曲面需要二階光滑可導.比如大家都希望轎車的車體光可鑒人, 并且車體表面的反射圖像也是光滑連續(xù)的.在幾何上,這意味著車殼表面應當曲率連續(xù).數(shù)控機床以樣條曲面為輸入,計算刀具運行的軌跡,力度,速度等等,將金屬毛坯加工成光滑的曲面.
設計師利用石膏雕塑出所設計的款式,三維掃描儀可將現(xiàn)實中的曲面數(shù)字化,輸出稠密的點云.應用三維Delaunay三角剖分的算法,點云可以被轉(zhuǎn)化為多面體曲面.將多面體曲面轉(zhuǎn)換成光滑樣條曲面是饒有興味的問題.傳統(tǒng)樣條曲面的構(gòu)造方法是基于仿射幾何不變量的.對于拓撲簡單的曲面,我們可以只用一個整體的參數(shù)域來覆蓋全部曲面,并在參數(shù)域上構(gòu)造樣條.
圖11 曲面的共形參數(shù)化
如圖11所示,我們將米開朗基羅的大衛(wèi)王的頭像雕塑曲面共形地映射到平面,從而得到曲面的共形參數(shù).圖12展示了由這種方法得到的樣條曲面.我們在幾何復雜的區(qū)域,如眼睛,前額處的頭發(fā),增加了控制點的密度;在相對平滑的區(qū)域,如面頰,前額,控制點相對稀疏.這樣,我們能夠利用有限的控制點達到對曲面形狀最好的刻畫.
圖12 米開朗基羅的大衛(wèi)頭像的樣條曲面[6]
對于曲面具有復雜拓撲的情形,構(gòu)造全局光滑的樣條曲面等價于構(gòu)造原曲面的仿射結(jié)構(gòu).根據(jù)示性類理論,由于拓撲障礙,全局仿射結(jié)構(gòu)很多時候并不存在.樣條曲面上不可避免存在奇異點.在奇異點,曲率不連續(xù),曲面的反射圖像在奇異點有可能間斷.所以,實際生產(chǎn)中,我們應當盡量減少奇異點的個數(shù),并且將奇異點盡量隱藏在不為人注意的地方.因此出于工程需要,奇異點的位置一般由用戶指定.構(gòu)造曲面帶有指定奇異點的仿射結(jié)構(gòu)是相對復雜的問題.我們的解決方案是構(gòu)造一個特殊的黎曼度量,使得所有的曲率集中在奇異點上面.這個特殊的度量自然地引發(fā)一個仿射結(jié)構(gòu).圖13顯示了一個樣條曲面的實例,其上的奇異點由用戶指定.
圖13 帶有指定奇異點的樣條曲面
5.3無線網(wǎng)絡方面的應用
無線傳感器網(wǎng)絡是一個近些年來迅猛發(fā)展的方向,它能夠協(xié)同地實時監(jiān)測、感知和采集網(wǎng)絡覆蓋區(qū)域中各種環(huán)境或監(jiān)測對象的信息,并對其進行處理,處理后的信息通過無線方式發(fā)送給觀察者.無線傳感器網(wǎng)絡由稱為“微塵”的微型計算機構(gòu)成.這些微型計算機通??梢酝ㄟ^自我重組形成網(wǎng)絡,彼此通信,并交換有關(guān)現(xiàn)實世界的信息.
每個微塵只有有限的計算和存儲能力,和有限的電池能量儲備,特別是所有的微塵只有局部的信息,只能和直接的鄰居通訊.網(wǎng)絡中通常沒有一個掌握全局信息的中樞機構(gòu).消息的傳遞一般由簡單的路由協(xié)議實現(xiàn).如圖14所示,左圖的網(wǎng)絡中每一個節(jié)點都是一個微塵,若兩個節(jié)點之間存在一條邊,則它們可以直接通訊.網(wǎng)絡中的每一個節(jié)點具有唯一的坐標,坐標可以由GPS設備得到的真實坐標,也可以是虛擬坐標.網(wǎng)絡中信息的傳遞多由所謂“貪婪”算法實現(xiàn).假設網(wǎng)絡中一個節(jié)點得到了一個消息,這個信息包括其目的地節(jié)點的坐標,那么當前網(wǎng)絡節(jié)點將此信息傳遞給它的一個鄰居,使得鄰居到目標節(jié)點的距離小于當前節(jié)點到目標節(jié)點的距離.通常情況下,每一次信息傳遞都使得當前節(jié)點到目標節(jié)點的距離減小,如果信息能夠順利傳遞,最終它會抵達目標節(jié)點.
圖14 基于幾何方法的無線傳感器網(wǎng)絡路由設計[7]
“貪婪”算法簡單實用,但是具有致命的缺陷.如圖14(a)所示,假設網(wǎng)絡中有一些障礙物,例如水塘,建筑物等,這些障礙物會在網(wǎng)絡中產(chǎn)生孔洞,如果孔洞不是凸形狀,“貪婪”算法會失敗.比如信息傳到了某個非凸孔洞邊緣的角點,非常有可能角點到目標節(jié)點的距離小于其任意鄰居到目標節(jié)點的距離,從而“貪婪”算法無法將信息進一步傳遞.利用共形幾何的方法,我們將原始網(wǎng)絡變形,從而所有的邊界都成為圓形,如圖14(b)所示.那么,可以證明“貪婪”算法在新的網(wǎng)絡中保證會成功.換言之,通過改換網(wǎng)絡的黎曼度量,我們可以提高網(wǎng)絡的性能和效率.
“貪婪”算法所得到的信息傳遞路徑都是網(wǎng)絡中鏈接起點和終點的最短路徑.如圖14(b)所示,大量的最短路徑會貼著網(wǎng)絡的孔洞邊緣,因此處于網(wǎng)絡孔洞邊緣的節(jié)點的負擔會很繁重,電力消耗會比其它節(jié)點更快.我們利用幾何中的“覆蓋空間”的概念來均衡節(jié)點的負擔.如圖14(c)所示,我們將網(wǎng)絡關(guān)于它所有的內(nèi)邊界“反演”,這樣會增加孔洞的數(shù)目,縮小孔洞的總面積.我們可以再次將整個網(wǎng)絡關(guān)于它新的內(nèi)邊界反演,從而進一步縮小所有孔洞的總面積.這樣所得到的網(wǎng)絡可以多重覆蓋原始的網(wǎng)絡,即新的網(wǎng)絡是舊網(wǎng)絡的“覆蓋空間”.信息傳遞在覆蓋空間中由貪婪算法完成.這樣,所有節(jié)點的負載基本均衡.
5.4電影動漫,數(shù)字游戲中的應用
紋理貼圖在數(shù)字游戲中,所有的三維物體的表示都可以分為兩部分:幾何和紋理.幾何表征了物體的形狀,由三維空間中的三角網(wǎng)格(離散曲面)表示;紋理表征了物體的材料,質(zhì)地,顏色,和光學特性,由二維圖像表示.將二維紋理圖像貼在三維離散曲面的過程被稱為“紋理貼圖”.紋理貼圖需要將三維曲面映射到平面上.如圖15所示,在左圖中,三維曲面被共形地映射到平面上,在右圖中,紋理圖像被這映射“拉回”到三維曲面上面.這樣,我們看到大理石雕塑的大衛(wèi)王的頭像.
圖15 紋理貼圖
圖16 計算機模仿藝術(shù)家的素描圖[8]
非真實感渲染很多時候,人們需用計算機模仿藝術(shù)家作畫.如圖16所示,特殊的計算機渲染算法可以產(chǎn)生鉛筆素描的藝術(shù)效果.藝術(shù)家在素描寫生過程中,運筆的走向基本上是沿著明暗色調(diào)變化最劇烈的方向,和變化最緩慢的方向.這兩個方向彼此垂直,被稱為曲面的主曲率方向.在幾何上,計算機算法等價于如何在曲面上設計光滑矢量場,同時,矢量場的走向盡量與曲面的主曲率方向場保持一致.根據(jù)拓撲障礙理論,一般曲面上不存在處處非零的光滑矢量場,矢量場的零點被稱為是奇異點.首先,我們可以構(gòu)造一個新的黎曼度量,使得所有的曲率集中在零點上,換言之,我們生成零點之外的平直度量.在平直空間生成矢量場相對容易許多.然后我們計算曲面的主曲率方向場,通過幾何手段融合一些零點.最后根據(jù)光照條件計算曲面的明暗色調(diào),在渲染過程中,矢量的密度正比于色調(diào)強度.
表情捕捉在今天的CG電影(計算機生成電影), 表情的建模和生成是最具挑戰(zhàn)性的問題之一.人類對于表情極其敏感.根據(jù)心理認知理論,人類用于識別表情的大腦區(qū)域不同于識別一般形狀的區(qū)域.因此,對于微妙表情的建模和模擬非常困難.人類所有可能的肢體動作構(gòu)成一個有限維空間,因為人類只有有限個關(guān)節(jié),每個關(guān)節(jié)只有有限個自由度.但是人類所有可能的表情構(gòu)成了無窮維空間.因此,表情生成具有根本的難度.
近些年來興起的表情捕捉技術(shù)為表情的建模和生成帶來了根本性的突破.基于光波干涉原理的高速三維相機可以實時獲取表情的動態(tài)變化.如圖17所示,目前的技術(shù)可以達到每秒上百幀的速度,每幀具有上百萬采樣點;但是,所有得到的掃描曲面都是相互獨立的,曲面之間的映射關(guān)系需要被建立起來.我們將每幀曲面共形映射到平面上,在平面像上計算特征點,利用優(yōu)化方法尋找平面圓盤間的映射,如圖18所示.平面像之間的映射建立了三維人臉曲面間的映射.我們用統(tǒng)一的網(wǎng)格基于所得的映射貼到所有的人臉曲面上,如圖19所示,這樣我們可以追蹤人臉上每一點變化的軌跡,從而達到表情自動跟蹤的目的.
圖17 三維動態(tài)相機可以實時捕捉人臉表情的動態(tài)變化
圖18 動態(tài)人臉曲面被共形映射到平面圓盤[9]
圖20顯示了“虛擬明星”的概念.明星的面部幾何和紋理,以及各種動態(tài)表情被掃描下來,保存在數(shù)據(jù)庫中.導演根據(jù)劇情需要,選擇合適的表情,視角,嘴型,以及場景,用計算機合成CG電影.這樣,真正的明星不需要出演電影,只需要提供各種標準的表情.或者,真人演員的表情被提取出來,轉(zhuǎn)移到卡通人物臉上,從而用表情捕捉技術(shù)取代目前的表情建模和合成,提高表情的逼真度和復雜性.
圖19 表情自動跟蹤[10]
圖20 虛擬明星:明星的面部幾何和紋理、動態(tài)表情被記錄下來,保存在數(shù)據(jù)庫中,導演根據(jù)劇情需要選擇合適的表情,合成CG電影
5.5虛擬/增強現(xiàn)實中的應用
在虛擬現(xiàn)實和增強現(xiàn)實的應用中,如何將光滑曲面離散化是一個基本問題.在離散化的過程中,我們希望能夠保證離散曲面足夠好地逼近光滑曲面,例如拓撲一致,位置接近,測地距離收斂,曲率測度收斂.我們提出了一種高效而嚴謹?shù)姆椒▽崿F(xiàn)離散化,同時保證曲率測度收斂.通過單值化,我們將曲面共形映到標準空間,然后在標準空間上采樣,使得采樣密度和曲率成正比,計算Delaunay三角剖分,再拉回到原來曲面.圖21顯示了這樣的一個算例.
圖21 曲面采樣離散化[11]
另一方面,虛擬現(xiàn)實和增強現(xiàn)實的應用中,需要對幾何數(shù)據(jù)進行壓縮,力圖保持幾何質(zhì)量的同時增大壓縮比.利用單值化定理,我們將曲面映到標準空間,那么面積變化率函數(shù)加上平均曲率就可以完全復制原來曲面.圖22顯示了一個離散曲面簡化壓縮的實例.
圖22 離散曲面簡化
從以上的實例可以看到,共形幾何不但具有深邃和諧的美學價值,更具有無可比擬的實用價值.幾何知識的廣泛傳播和深入應用,日益促進了生產(chǎn)力的發(fā)展,根本地改變了人類社會的日常生活.我們期待幾何的進一步發(fā)展將為人類帶來更多革命性的變革.
同時,作為一個新興學科,計算共形幾何依然有大量尚未解決的問題,面臨許多挑戰(zhàn).這些基本的公開問題,需要用更加深刻的理解以及更加精致和準確的算法去解決.下面這些問題在理論和應用上都有非常重要的意義:
(i) Teichmüller映射給定兩個度量曲面和它們之間的映射同倫類,計算唯一的具有最小Beltrami系數(shù)模的擬共形映射,即所謂的Teichmüller映射.
(ii) Abel Differential計算不同類型的Abel微分群,尤其是全純二次微分群.
(iii) 逼近理論盡管已經(jīng)有了計算共形不變量的算法,但是逼近理論的結(jié)果還沒有充分的發(fā)展. 對于平面區(qū)域間的共形映射,不同離散方法的收斂性已經(jīng)被建立. 而對于曲面間的共形映射,收斂性分析仍然是公開問題.
(iv) 精確性和穩(wěn)定性雙曲幾何計算對數(shù)值誤差非常敏感.提高計算的精確度很具有挑戰(zhàn)性.計算幾何中的精確算法有望攻克這個難題.
我們希望更多的有志年輕人投身到這一領(lǐng)域之中,在理論和工程領(lǐng)域中大展身手,為科學和實踐的發(fā)展做出歷史性的貢獻.
[1]Gu X and Yau S-T. Computational Conformal Geometry [M]. Cambridge: International Press and Higher Education Press, 2007.
[2]Luo F, Gu X and Dai J. Variational Principles for Discrete Surfaces [M]. Cambridge: International Press and Higher Education Press, 2007.
[3]Zeng W, Gu X. Ricci Flow for Shape Analysis and Surface Registration -Theories, Algorithms and Applications [M]. New York: Springer, 2013.
[4]Gu X, Wang Y, Chan T F, Thompson P M and Yau S-T. Genus Zero Surface Conformal Mapping and Its Application to Brain Surface Mapping [J]. IEEE Transaction on Medical Imaging (TMI), 2004, 23(8): 949-958.
[5]Zeng W, Marino J, Gurijala K, Gu X and Kaufman A. Supine and Prone Colon Registration Using Quasi-Conformal Mapping[J]. IEEE Transactions on Visualization and Computer Graphics (IEEE TVCG), 2010, 16(6): 1348-1357.
[6]Gu X, He Y, and Qin H. Manifold Splines[J]. Graphical Models, 2006, 68(3):237-254.
[7]Sarkar R, Yin X, Gao J, and Gu X. Greedy Routing with Guaranteed Delivery Using Ricci Flows[C]. Proc. of the 8th International Symposium on Information Processing in Sensor Networks (IPSN’09), 2009:121-132.
[8]Lai Y, Jin M, Xie X, He Y, Palacios J, Zhang E, Hu S and Gu X. Metric-Driven RoSy Fields Design[J]. IEEE Transaction on Visualization and Computer Graphics (TVCG), 2010, 15(3): 95-108.
[9]Zeng W, Samaras D and Gu X. Ricci Flow for 3D Shape Analysis[J]. IEEE Transaction of Pattern Analysis and Machine Intelligence (PAMI), 2010, 32(4): 662-677.
[10]Zeng X, Wang C-H, Gu X. Higher-order Graph Principles towards Nonrigid Surface Registration[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2015, 1:1-14.
[11]Li H, Zeng W, Morvan J-M, Chen L, Gu X. Surface Meshing with Curvature Convergence[J]. IEEE Transaction on Visualization and Computer Graphics (TVCG), 2014, 20(6):919-93.
Introduction to Computational Conformal Geometry
GUXian-feng1,LEINa2
(1.Computer Science Department,State University of New York at Stony Brook,Stony Brook NY 11794, USA;2. School of Software, Dalian University of Technology, Dalian Liaoning 116620, China)
Computational Conformal Geometry is an interdisciplinary field between pure mathematics and computer science. This work introduces the fundamental theories, computational algorithms and applications in engineering fields of computational conformal geometry. Basic theoretic concepts include conformal mapping, uniformization, conformal module, quasi-conformal mapping, and moduli space and so on. Major computational algorithms include harmonic mapping, holomorphic differential methods based on Riemann surface theory, surface Ricci curvature flow in geometric analysis. Conformal geometry can be applied in many fields, such as medical imaging, mechanical manufacture, digital media and virtual/augmented reality and so on.
conformal geometry; Riemann surface; uniformization; harmonic map; holomorphic differential; surface Ricci flow
2016-05-10;[修改日期]2016-06-13
國家自然科學基金(11271156)
顧險峰(1970-),男,博士,終身教授,從事計算幾何研究.Email:gu@cs.stonybrook.edu
雷娜(1977-),女,博士,教授,從事計算幾何研究. Email:nalei@outlook.com
O186
B
1672-1454(2016)03-0001-13