低扭曲幾何映射研究

UniversityofScienceandTechnologyofAdissertationfordoctor’sGeometricMapswithLow ChunxueWang Prof.LigangLiuFinishedTime: May,2016新形式，并在曲面造型、計(jì)算機(jī)動(dòng)畫與視覺、地理信息系統(tǒng)、物理仿真、虛機(jī)科學(xué)中的廣泛應(yīng)用，越來越多基于低幾何的工程技術(shù)難題被解決。本對(duì)于虧格為0的封閉三角網(wǎng)格曲面，我們提出了一種盡可能保剛性的球面參數(shù)化方法（ARAP方法。該方法是平面域上盡可能保剛性參數(shù)化在球面域的量保剛性地到該球面上。通過分析二維及三連續(xù)和離散的ARAP能ARAP能量的球面參數(shù)化的優(yōu)化模型。該模型的求解涉及到一個(gè)算法，包括局部/全局算法更新球面頂點(diǎn)坐標(biāo)和迭代更新半徑。該方法克服了以AMIPS能量優(yōu)化的球面參數(shù)化模型。給定一個(gè)初始的有效參數(shù)化，即使初始的比較大，我們通過求解一個(gè)帶有非線性約束的非線性優(yōu)化問題來BlockCoordinateDescent方法的迭代優(yōu)化算法，得到了最優(yōu)半徑球面上的低法得到的球面參數(shù)化結(jié)果均能在保證雙射的基礎(chǔ)上，具有最低的最大和平對(duì)于圖像特征點(diǎn)匹配問題，我們通過構(gòu)造平面網(wǎng)格上低的方法來由SIFT算法1]含有噪音的若干圖像特征點(diǎn)對(duì)應(yīng)，我們希望能從噪音的特征點(diǎn)對(duì)應(yīng)中尋找出盡可能多的具有幾何信息的對(duì)應(yīng)點(diǎn)。針對(duì)該問題，我們提出了基于擬共形函數(shù)空間的過濾方法，將該問題轉(zhuǎn)化成關(guān)于ltrmi系數(shù)和擬共形函數(shù)的帶約束的優(yōu)化問題，并提出了一種基于變量分離方法和迭代最小二乘方射函數(shù)的稀疏線性系統(tǒng)求解問題和關(guān)于Bltrmi系數(shù)的帶有線性約束的凸二次規(guī)劃問題。為了衡量算法的準(zhǔn)確率，我們定義了刻畫特征點(diǎn)匹配準(zhǔn)確性的統(tǒng)計(jì)量Fmeur，并分別在數(shù)據(jù)和真實(shí)圖像上做了測試。實(shí)驗(yàn)結(jié)果表明，我們的方法能夠篩選出的具有幾何一致性的特征點(diǎn)對(duì)應(yīng)，并且對(duì)參數(shù)的選擇和噪音均不敏感。：數(shù)字幾何數(shù)據(jù)低幾何三角網(wǎng)格曲面球面參數(shù)化圖像特征點(diǎn)匹配擬共形Withthedevelopmentof3Dscanningtechnology,digitalgeometricdatahas-eanewtypeofmulti-mediafollowedsound,imageand,andwidelyusedthefieldsofsurfacemodeling,computeranimationandvision,geographicinformationsystem,physicalsimulation,virtualreality,scientificcomputingvisualizationandsoon.Theresearchofthisthesisisbasedonthebasicdigitalgeometricdataoftriangularmesh.Findinggeometricmapswithlowdistortionbetweensurfacesisabasicandimportantproblemincomputergraphics,computervision,medicalimageprocessingandsoon.Amongthem,surfaceparameterizationandregistrationaretwoimportanttechniques.Withthedevelopmentofdigitalgeometryprocessingandthewideapplica-tionofsurfacedifferentialgeometryincomputerscience,moreandmoreengineeringproblemsbasedonthemapswithlowdistortionaresolved.Inthisthesis,basedontriangularmeshes,wefocusontheproblemoffindingmapswithlowdistortion,in-cludingsphericalparametrizationwithlowdistortionandmapswithlowdistortionbetweenplanarmeshes.Forclosedgenus-zerotriangularmeshes, resentanas-rigid-as-possiblespher-icalparametrizationmethod(ARAPmethod),whichisanextensionofplanarARAPparametrizationapproachtospherical.Ouraimistofindanoptimalsphereonwhichparametrizationtrianglescanbeembeddedinarigidity-preservingmanner.WeyzethesmoothanddiscreteARAPenergyandformulateoursphericalparametriza-tionmodelfromthediscreteARAPenergy.Thesolutionisnontrivialastheenergyin-volvesalargesystemofnon-linearequationswithadditionalsphericalconstraints.Tothisend, roposeanefficienttwo-stepiterativealgorithmincludingalocal/globaliterativeschemetocalculatetheparametrizationcoordinatesanditerativeupdatingra-dius.Thismethodoptimizesrigiddistortiondirectly,which esthedrawbacksofpreviousworkoptimizingonlyangledistortionorareadistortion.Experimentalre-sultsshowthatARAPsphericalparametrizationhasthebestrigidity-preservingertycomparedwithpreviousForclosedgenus-zerotriangularmeshes,resentamethodtofindabijectivesphericalparametrizationwithlowdistortion(BLDmethod),includingconformalandisometricsphericalparametrization.Previousmethodsforsphericalparametrizationcannot,ingeneral,controltheworstcasedistortionofalltrianglesnorguaranteebi-jectivity.Tosurmountthesedisadvantages,weformulateoursphericalparametrizationmodelbasedonAMIPSenergy.Givenaninitialbijectivesphericalparametrization,evenwithhighdistortion,wedevelopanon-linearconstrainedoptimizationproblemtorefineit,withobjectivepenalizingthepresenceofdegeneratetrianglesandaldistortion.Byusingadynamicadjustingparameterandaconstrained,iterativeinexactBlockCoordinateDescentoptimizationmethod,weefficientlyandrobustlyachieveabijectiveandlowdistortionparametrizationwithanoptimalsphereradius.Experimen-talresultsshowthat,ourmethodcanachieveboththelowestaldistortionandaveragedistortiononnumerousmodelsundergoingsimpletocomplexshapes.Inad-dition,ourmethodisfast,efficient,robusttoinitialparametrizationandinsensitivetoparameterchoice.Forthefeaturematchingproblemofimages,wefindgeometricallyconsistentcor-respondencesintwoimagesbyconstructingthemapswithlowdistortionbetweenplanarmeshes.GivenasetofcandidatematchesprovidedbySIFTdescriptors[1],whichmayincludemanyoutliers.Ourgoalistoseleubsetofthesematchesretainingmuoregeometricinformation.Tosolvethisproblem,resentafilteringmethodbasedonthespaceofalldiffeomorphisms,formulateaconstrainedoptimizationin-volvingboththeBeltramicoefficienttermandquasi-conformalmap,andsolvedbyanefficientiterativealgorithmbasedonvariablesplittingmethodanditerativereweightedleastsquaresmethod.Ineachiteration,wesolvetwosubproblemsincludingalin-earsystemandalinearlyconstrainedconvexquadraticprogramming.Tomeasurethematchingaccuracy,wedefineastatisticF-measureandtestouralgorithmonbothsyn-theticdataandrealimages.Experimentalresultsshowthatourmethodenablespro-ducingmorecorrectcorrespondencescomparedwiththestate-of-the-artapproaches,isinsensitivetoparameterchoiceandrobusttooutliers.:digitalgeometricdata,geometricmapswithlowdistortion,triangularmeshes,sphericalparametrization,featurematchingofimages,quasi-conformalmaps····························································· 第1章緒 研究背景和研究意 研究問 曲面表 的定 的應(yīng) 研究現(xiàn) 球面參數(shù) 平面三角網(wǎng)格上低···································· 本文內(nèi)容及結(jié)構(gòu)安 第2章連續(xù)及離散形式下曲面上的幾何···················連續(xù)形式下曲面的微分幾何概念和性 曲 曲 曲面之間的············································ 離散曲面上的幾何······································· 三角網(wǎng)格上的基本概 三角網(wǎng)格上的······································· 本章小 第3章盡可能保剛性的球面參數(shù) 引 預(yù)備知 ARAP能 盡可能保剛性的平面參數(shù)化方 基于三維ARAP能量的球面參數(shù)化模 從局部到整體的球面參數(shù)化方 實(shí)驗(yàn)結(jié) 3.5算法分析3.5.1不同初始參數(shù)化的球面參數(shù)化3.5.2不同分辨率網(wǎng)格的球面參數(shù)化3.5.3算法的收斂性 3.5.4復(fù)雜幾何網(wǎng)格的球面參數(shù)化3.6本章小結(jié) 第4章低的有效球面參數(shù)化4.1引言4.2預(yù)備知識(shí)4.2.1MIPS4.2.2AMIPSBlockCoordinateDescent4.34.4數(shù)值實(shí)驗(yàn) 4.4.1保長度的球面參數(shù)化 4.4.2保角度的球面參數(shù)化 4.5算法分析 4.5.1不同初始參數(shù)化的球面參數(shù)化 4.5.2不同分辨率數(shù)據(jù)的球面參數(shù)化 4.5.3參數(shù)的動(dòng)態(tài)調(diào)整 4.5.4算法的收斂性 4.6本章小結(jié) 第5章基于擬共形的圖像特征點(diǎn)匹配5.1引言 5.2相關(guān)工作 5.2.1低維形變空間 5.2.2基于函數(shù)空間的形變空間 5.2.3擬共形 5.3預(yù)備知識(shí) 5.4基于擬共形空間的圖像特征點(diǎn)對(duì)應(yīng)問題的模型5.5數(shù)值實(shí)現(xiàn) 5.5.1三角網(wǎng)格上離散 .25.6數(shù)值實(shí)驗(yàn)5.6.1數(shù)據(jù)算法分析5.8本章小結(jié) 第6章總結(jié)與展望 6.1本文工作總結(jié) 6.2未來工作展望 參考文獻(xiàn) 致謝 在讀期間的學(xué)術(shù)與取得的研究成果圖幾種曲面幾種曲面表示[3]網(wǎng)格參數(shù)化的應(yīng)用 交互式幾何建模 曲面對(duì)應(yīng) 3 插值問題[113]插值問題[113]邊界插值問題[113] 2.1從參數(shù)域?的方向?qū)?shù)ˉ到曲面S上的切方向w的變換 2.2的各向異性 三角網(wǎng)格曲面上不同類型的幾何 極小化不同下的網(wǎng)格變形 f的奇異值分解[147]································ 三角網(wǎng)格曲面的一鄰域及半邊結(jié)構(gòu) 盡可能保剛性的平面參數(shù)化方法 不同意義下的Lτ[161] 盡可能保剛性的球面參數(shù)化的流程 局部求解中的最優(yōu)旋轉(zhuǎn)矩陣Rτ 頂點(diǎn)i的一鄰域四面體及二面角 ARAP球面參數(shù)化在不同模型上的表現(xiàn) 不同初始參數(shù)化下ARAP球面參數(shù)化的表 不同分辨率網(wǎng)格上ARAP球面參數(shù)化的表 圖3.9中各模型的三維ARAP能量曲 復(fù)雜幾何網(wǎng)格的ARAP球面參數(shù)化 4.1參數(shù)化f|t和逆g|t[87] 4.2g的分解 原始三角形及參數(shù)化三角形上的定義 最大和平均關(guān)于s的變化曲線 不同半徑更新策略的比較 簡單模型上Harmonic，Hierarchical，ARAP及BLD的結(jié)果比較 復(fù)雜模型上Harmonic，Hierarchical，ARAP及BLD的結(jié)果比較 頂點(diǎn)數(shù)量大于400K的0虧格封閉網(wǎng)格數(shù)據(jù)的保長度球面參數(shù)化 保角度的球面參數(shù)化比較 不同初始參數(shù)化的結(jié)果比較 不同分辨率數(shù)據(jù)的球面參數(shù)化 網(wǎng)格尺寸差異較大的數(shù)據(jù)上的球面參數(shù) 4.13Cow模型上不同參數(shù)s的結(jié)果比較 4.14能量函數(shù)（單個(gè)三角形上）Beltrami系數(shù)與共形度量RBF數(shù)據(jù)上的結(jié)果比較同一物種的不同動(dòng)物圖像上的特征點(diǎn)匹配5.35.5Beltrami5.35.5的所有例子的能量曲線σ?表不同方法的平均面積和平均角 的比 不同方法的平均剛性（長度 的比 模型統(tǒng)計(jì)及算法表現(xiàn) 不同保長度球面參數(shù)化方法的實(shí)驗(yàn)效果及運(yùn)行時(shí)間 真實(shí)圖像上圖像匹配準(zhǔn)確率的比較 運(yùn)行時(shí)間比較 第1 緒研究背景和研究意隨著三維技術(shù)的不斷發(fā)展，計(jì)算機(jī)性能及能力的持續(xù)提高以及2001SigGraph會(huì)議首次提出以來，數(shù)字幾何處理造離散曲面，然后經(jīng)由三維打印得到產(chǎn)品原型。為了保證離散曲面的近精度，常常通過離散曲面共形映到典范區(qū)域，然后用DelaunayRefinement方法重新三研究問和點(diǎn)云，在眾多的曲面表示中，三角網(wǎng)格因其結(jié)構(gòu)簡單、表達(dá)能力豐富、繪圖 幾種曲面表示的定f，從廣義上來講，定義了兩個(gè)數(shù)據(jù)集/AB（數(shù)域、形狀、圖像等）間的光滑函數(shù)，記作fA→B。對(duì)于A中每個(gè)元素a，按照規(guī)則f，B中有唯一確定的元素b與之對(duì)應(yīng)，則b稱為元素a在f下的象，記作：b=f(a)；a稱為b關(guān)于f的原象。數(shù)據(jù)集/空間A中所有元素的象的集合稱為f(A)Af的定義域。特別地，B中每個(gè)元素都有原象，f建立了數(shù)據(jù)集/A和數(shù)據(jù)集/B的一一對(duì)應(yīng)關(guān)f是數(shù)據(jù)集/空間A到數(shù)據(jù)集/空間B上的一一。當(dāng)A和B都是非空數(shù)集且A到B是一對(duì)一或者多對(duì)一情形，則f恰恰是數(shù)學(xué)領(lǐng)域定義的函數(shù)。基于不同的數(shù)據(jù)集/空間，我們指定f特定性質(zhì)，比如連續(xù)性、插值性等。在定義給出的基礎(chǔ)上，我們定義不同數(shù)據(jù)集/空間上的幾何度量，使得在該度量下f具有極小的變形。圖1.2給出不同數(shù)據(jù)集/空間上f的定義。??:??:?2→??:??→??:??→??:??→??:?3→圖 三角網(wǎng)格曲面（TrianglularMesh）M可表示為集合{VKP}VM的頂點(diǎn)集合；KM上的拓?fù)溥B接關(guān)系的集合（頂點(diǎn)，邊，面PM所有頂點(diǎn)的屬性集合（頂點(diǎn)位置坐標(biāo)，點(diǎn)法向量及點(diǎn)顏色等K{VEF}，其中V={i},E={i,j}，F(xiàn)={i,jk}分別表示M的點(diǎn)集合、邊集合和面集合。如果{ijEij互為鄰居，并記i的一鄰域點(diǎn)N(i)={j|{ijE及頂點(diǎn)i的度|N(i)|。我們以遞歸方式給出im階星形鄰域點(diǎn)：Star0(i)=∪Star1(i)=∪Starm(i)

N對(duì)于邊e={ij}∈E，定義e的一鄰域點(diǎn)和m階星形鄰域點(diǎn)（m≥∪N(e)=N N(j)?{i,∪Star(e)=Star(i)Starm(e)=Starm(i)

∪對(duì)于面f{ijkF，定義f的一鄰域點(diǎn)和m階星形鄰域點(diǎn)（mN(f)=N

N

NStar(f)=

∪

∪Starm(f)=

此外i的一鄰域面T(i){f|iffF}，則邊e的一鄰域面T(e)= T T(j)，面f的一鄰域面T(f)=T(i)T T(k)?{i,j,k}。以此類推分別得到im鄰域面、em鄰域面及fm鄰域面Tm(i)=T∪Tm(e)=TTm(f)=T

T T

Tm(k)?{i,j,MgNv、Ne、NfNbM的頂點(diǎn)數(shù)、邊數(shù)、三角面片數(shù)和邊界數(shù)g=(Ne?Nv?Nf?Nb+M上洞的個(gè)數(shù)。特別地，對(duì)于半球面網(wǎng)格的虧格為0，球面網(wǎng)格的虧格為0。圖1.3給出了不同類型及不同虧格數(shù)的三角 圖 不同類型及不同虧格數(shù)的三角網(wǎng)格曲面：(a)虧格為0的單邊界網(wǎng)格；(b)虧格為)1.1MN的拓?fù)溥B接關(guān)系相同，即存在從KM到KN的一一ΓM?N，則ΓM?N被稱為M到N的同構(gòu)，并且稱M和N是拓?fù)渫瑯?gòu)的。0M的球面參數(shù)化問題就是構(gòu)造一個(gè)與M拓?fù)渫瑯?gòu)的球面網(wǎng)格S，使得KM到KS的是一一的。接下來我們?cè)敿?xì)描述在三角網(wǎng)格上的定義。f給定三角網(wǎng)格MsV{v1v2vnvMnv個(gè)網(wǎng)格頂點(diǎn)，其vi={xiyizi}∈R3。M的拓?fù)潢P(guān)系決定的三角F={f1f2,...,fn}，ft={v0v1v2是三角形t的三個(gè)頂點(diǎn)。M的拓?fù)潢P(guān)系決定的E=f {e1e2ene}，其中el={vlvl是邊l的兩個(gè)頂點(diǎn)。顯然，M={VEF是′連續(xù)曲面S的分片線性近，因此，M上最自然的空間便是分片線性連續(xù)函數(shù)空間（ContinuousPiecewiseLinearMaps，簡稱CPLM。換句話說，M上的每一個(gè)三角形t的三個(gè)頂點(diǎn)分別被到對(duì)應(yīng)三角形的三個(gè)頂點(diǎn)，相鄰三角這樣就定義了三角網(wǎng)格上的全局連續(xù)的一一。特別地，每個(gè)三角形fj經(jīng)過′仿射變換Ajfj，相鄰三角形的不同仿射變換在公共邊上具有相同的對(duì)應(yīng)點(diǎn)，則仿射變換的Jacobian矩陣在每個(gè)三角形上是常數(shù)矩陣。在空間，的好壞一般通過Jacobian矩陣的奇異值刻畫。第二章我們會(huì)詳細(xì)描的應(yīng)數(shù)化的誕生是在公元前2000多年前，由古希臘人和古埃及人最早應(yīng)用在繪圖學(xué)領(lǐng)域。20世紀(jì)90年代，平面參數(shù)化被首次引入計(jì)算機(jī)圖形學(xué)，實(shí)現(xiàn)了三維曲面的二維紋理圖像貼圖[4–6]。在接下來的幾十年中，參數(shù)化[7;8]被不斷地研究，并廣泛地應(yīng)用到數(shù)字幾何處理的其他領(lǐng)域，包括網(wǎng)格編輯[9;10]、細(xì)節(jié)遷移[11–13]、網(wǎng)格修復(fù)（補(bǔ)洞[1416、網(wǎng)格形變[17–22]、曲面擬合[23–26]、重新網(wǎng)格化[27–33]、網(wǎng)格壓縮[21;28]、法向[34]、醫(yī)學(xué)可視化[35–37]，數(shù)據(jù)庫建立[20]、傳感器網(wǎng)絡(luò)[38–40]等，如圖1.4所示。網(wǎng)格編輯 細(xì)節(jié)遷移 網(wǎng)格修復(fù) 網(wǎng)格形變 曲面擬合 重新網(wǎng)格化 網(wǎng)格壓縮法向 醫(yī)學(xué)可視化 數(shù)據(jù)庫建立 傳感器網(wǎng)絡(luò)圖 法。不同的參數(shù)域不同的求解問題，因此也會(huì)導(dǎo)致不同的參數(shù)化質(zhì)量，例如球面參數(shù)化針對(duì)虧格為0的封閉曲面，加之球面域的非凸非線性的球面約束，相對(duì)。幾點(diǎn)：（1）局部性，即對(duì)小范圍區(qū)域網(wǎng)格頂點(diǎn)的修改，不引起整個(gè)網(wǎng)格頂點(diǎn)的變列舉了幾類交互式幾何建模的方法，如圖1.5所示。復(fù)重心坐標(biāo)復(fù)重心坐標(biāo)有界調(diào)和權(quán)多層次變形保剛性形變 均值坐標(biāo) 格林坐標(biāo) 局部重心坐標(biāo)圖 并且該插值用戶指定的一組稀疏對(duì)應(yīng)關(guān)系。一般地，該應(yīng)該滿足以下幾個(gè)條件：（1）雙射（一一（2）特征點(diǎn)對(duì)應(yīng)（滿足用戶指定的稀疏對(duì)應(yīng)關(guān)題[14;35;61–70]；(c)基于曲面間內(nèi)在的幾何量（Gromov-Hausdorff距嵌入、測地一致性等[54;71–78]1.6所示。Delaunay三角化得到。因此，圖形處理中的圖像匹配問題完全可以轉(zhuǎn)化成曲面對(duì)應(yīng)問題來求解。圖像特征點(diǎn)匹配問題，是指給定兩圖像{piqi}NiSIFT算法[1]想法是，從兩圖像出發(fā)，定義關(guān)于圖像像素值的匹配函數(shù)、像素值的約束函數(shù)此外，基于圖的譜方法[83;84]巧妙地將該問題轉(zhuǎn)化成線性代數(shù)中的矩陣問題，對(duì)于數(shù)據(jù)量不是很大的情形，也具有很好的效果，如圖1.7所示。 圖 曲面對(duì)低維變形空間 譜方法 基于圖像像素值圖 研究現(xiàn)球面參數(shù)應(yīng)用提供了基本工具，例如重新網(wǎng)格化、曲面擬合、曲面重建及曲面等。對(duì)（剛性）等幾何度量能盡量保持跟原始網(wǎng)格一樣。文獻(xiàn)[85–87綜述了部分比較流行1.8展示 圖1.8 幾種典型的球面參數(shù)化結(jié)果：(a)Isenburg等人的方法[88]；(b)Gotsman等人的方法[89]；(c)Gu等人的方法[35]；(d)Friedel等人的方法[90]；(e)Zayer等人的方法[91]；(f)等人的方法[92]；(g)Shen等人的方法[93]；(h)Wan等人的方法[94]不考慮量的球面參數(shù)格的拓?fù)渫瑯?gòu)。Kent等人采用類似吹氣球的方法將三角網(wǎng)格頂點(diǎn)到球面上，但并不能保證一一[95]。Kobbelt等人[96]和Alexa[19]等人采用球面松弛策略，Isenburg等人[88]提出了由拓?fù)溥B接信息生成球面網(wǎng)格的算法，由于該算法需要把個(gè)算法的缺點(diǎn)是生成的球面參數(shù)化很不均勻。Shapiro等人[98]采用累進(jìn)網(wǎng)格[99]的下來通過頂點(diǎn)操作將之前刪除的頂點(diǎn)依次添加到當(dāng)前球面上。該算法能保證2003年，Gotsman等人[89]首次將平面凸組合方法[97;100]推廣到球面參數(shù)化αixi

ωijxj= i=1,...,

∥xi∥2= i=1,...,ωij{i,j}∈Enegative {i,j}∈ωij ?

i= {i,j}/αixii=1nv是待求解的量。他們利用譜圖理論（SpectralGraphTheory[101]）及ColindeVerdiere理論[102]分析了該系一存在的條件。特別地，ωij取保角權(quán)重[103]或者中值權(quán)重[104]時(shí)，均可得到保角度球面參數(shù)化。但是2005年，Saba等人[105]提出了一種快速有效求解(1.1)的算法，首先利用由Isenburg等人[88]算法得到一個(gè)初始有效的球面參數(shù)化，在此結(jié)果基礎(chǔ)之避免了直接求解(1.1)而導(dǎo)致的解的出現(xiàn)?；贕otsman等人[89]平面的凸組合在球面域的推廣，等人[106]提出了一種新的算法，僅僅需要求解一個(gè)線性系統(tǒng)即可得到。 [107]將該問題轉(zhuǎn)化成極坐標(biāo)系下求解，大大降低了該問題的非線性程度。Haker等人[36]極投影到球面上的過程，并不能保證參數(shù)化的有效性。為減小該方法的變形，Kharevych等人[108]采用基于圓模式的邊界保 極投影依然不能避免三角形的翻轉(zhuǎn)。Sheffer等人[109]ABF平面參數(shù)化方法[110]組變?yōu)榍蠼庖粋€(gè)非線性方程組，因此算法的效率大大降低，僅僅適合規(guī)模較小的網(wǎng)格。Gu等人[35]推廣了平面域保角參數(shù)化方和能量，采用分層的共軛梯度方法優(yōu)化。該算法對(duì)于規(guī)模較大細(xì)節(jié)較多的網(wǎng)格，收斂非常慢。2007年，等人[112]改進(jìn)了之前的算法[111]，采用基于Lagrange-Newton方法的球面參數(shù)化算法，效率明顯提高。由于保角度球面參數(shù)化結(jié)果會(huì)產(chǎn)生很大的面積，越來越多的研究學(xué)者保面積。Prun等人[33]推廣了平拉能至面域與Shpiro等人[98]算法類似，采用累進(jìn)網(wǎng)格的算法[99]，通過優(yōu)化球面上拉伸度量的非線將的頂點(diǎn)添加到球面上。累進(jìn)網(wǎng)格的算法同樣被等人[92]使用，不同的是，他們?cè)趯⒌捻旤c(diǎn)添加到面時(shí)首局采保使該落一域，后局球面拉能。206年Sn等[3]采網(wǎng)平滑算優(yōu)化保積能量和保角度能量。Friedl等人[0]量的無約束問題，并解釋了拉伸能量如何在保角度能量和保面積能量之間Zyr人1]在坐標(biāo)優(yōu)保積量和角能量平，并法首先需要用戶輸入一個(gè)周期切割線，將原始網(wǎng)格沿著該線切割成拓?fù)渫瑯?gòu)于戶輸入的周期切割線較敏感，即不合適的周期切割線可能引入非常大的。2013Praun等人[33]的方法類似，Wan等人[94]采用累進(jìn)網(wǎng)格的算法[99]優(yōu)化保面積能量和保角度能量的平均，逐次添加點(diǎn)的過程采用拉格朗日乘子法可以嚴(yán)格保證能量的下降。由于該算法添加點(diǎn)的過程是局部操作的，得到的球面參數(shù)化很容易陷入局部最優(yōu)解，在幾何較復(fù)雜的區(qū)域依然會(huì)很大平面三角網(wǎng)格上（配準(zhǔn)）問題而提出。平面三角網(wǎng)格曲面的問題，是指給定平面上形狀A(yù)和BA{pi}B{qi}，AB之間的f。本質(zhì)上來說，平面三角網(wǎng)格曲面的問題是平面三角網(wǎng)格曲面界插值問題。圖1.9和圖1.10分別給出了兩種插值問題的示意圖。下面分別介紹 圖 插值問題，Bookstein[114]（Thin-platesplines）的彎曲能量（Bendingenergy）的優(yōu)化問題，給出了插值函但是由于圖像匹配中特征的匹配本身具有確性，Rohr等人[115]提出了不精確薄板樣條的 問題中，大大提高了匹配的準(zhǔn)確率。除了薄板樣條被作為重要工具廣泛應(yīng)用之外，Rueckert等人[116]利用 圖 邊界插值問題FFD模型（Free-FormDeformations）來求解該問題，Sorzano等人[117則采用了向量樣條的正最近，很多研究學(xué)者將目光轉(zhuǎn)移到如何找到可以顯示控制局部單射性和扭量，出了量研成。于面角格特性復(fù)上24年，m等利用擬共形求解平面三角網(wǎng)格上的插值問題，并且能夠處理插值點(diǎn)變形較大的情形。體來說，是迭代求滿足插點(diǎn)約束的擬形f和lif)i等人9]eier（-p）的eier嚴(yán)格滿足對(duì)應(yīng)點(diǎn)約束。2015年，ui和Ng[10]提出了一種基型f和 量的顯示控制，Weber等人[121]提出利用局部 求解平面三角網(wǎng)格上的極 [122]，并將其推廣至非平面的三角網(wǎng)格曲面情形。但是上述Shllr等人123]通過添加懲罰能量項(xiàng)改進(jìn)了以往旋轉(zhuǎn)不變的變形能量41124–126]不能保證無翻轉(zhuǎn)的情形。ipmn127]首次提出了通過構(gòu)造有界的最大子空間來實(shí)現(xiàn)函數(shù)量的有界性及單射性質(zhì)，但是由于用戶給定的上界決定127]Pornne和ipmn53]提出了求解復(fù)平面上不同連續(xù)函數(shù)空間有界量的局部單射的算法。針對(duì)不同空間的基函數(shù)，該算法在理論上給出了Chen和Weber[128]利用平面的特殊性及復(fù)分析理論[129]，在平面（1）C滿足用戶輸入的上界。該方法處理的情況恰恰是Lipman[127]的一種特殊情況，因此繼承了Lipman[127]的缺點(diǎn)。不同于上述幾種算法，Chen[130]利用連續(xù)情形下平面上黎曼度量矩陣的性質(zhì)，實(shí)現(xiàn)了平面上角度有界的形狀變形，并且該 ，Levi和 優(yōu) 上界 ，Levi和 [132]通過修改網(wǎng)格的拓?fù)溥B接關(guān)系，來求解固定邊界的平面三角網(wǎng)格上的單射問題。Fu等人并不能保證的單射性質(zhì)。于此同時(shí)，Weber和在邊界插值問題中，重心坐標(biāo)（BarycentricCoordinates）是一個(gè)很重要的工具，已經(jīng)被廣泛研究和使用。在平面三角網(wǎng)格的插值中，函數(shù)一般被寫成實(shí)可以被預(yù)先計(jì)算好，在交互過程中，只要計(jì)算對(duì)應(yīng)的系數(shù)即可，方便高效。因此，能力及插值能力等。Wachspress和Eugene[134]首次將關(guān)于凸多邊形的Wachspress坐標(biāo)應(yīng)用到有限元計(jì)算中，并被推廣到更的凸多面體[43;135;136]。HormannFloater[137]利用中值坐標(biāo)（MeanValueCoordinates）處理任意平面多邊形的插值問題，并且具有連續(xù)、局部單射、易于實(shí)現(xiàn)的性質(zhì)。Lipman等人[47]使用格林坐標(biāo)（GreenCoordinates）得到了具有嚴(yán)格插值性質(zhì)的保形，后來Weber等人[52]提出了格林坐標(biāo)的更一般形式，并應(yīng)用到平面形狀插值問題中。Weber和Gotsman[138]計(jì)算了復(fù)空間的C∞連續(xù)的保角，但是并不能嚴(yán)格滿足插值條件。針對(duì)該問題，Weber等人[139]提出了基于雙調(diào)和方程解的(BiharmonicCoordinates)，自然插值邊界條件，但是該方法并沒有給射性質(zhì)[140]，一個(gè)例外情形是凸多邊形區(qū)域的Wachspress坐標(biāo)[141]。Weber等人[142]從復(fù)分析的角度分析了上述提到的幾種坐標(biāo)的性質(zhì)。Schneider等人[143]利組合幾種均值坐標(biāo)的方法求解了兩個(gè)簡單平面多邊形區(qū)域的雙射，但是并不能得C∞連續(xù)及上界的局部單射，但是該方法解的存在性強(qiáng)烈依賴于用本文內(nèi)容及結(jié)構(gòu)安本文圍繞低幾何問題，以三角網(wǎng)格數(shù)據(jù)為基礎(chǔ)，對(duì)低的球面參參數(shù)化作為數(shù)字幾何處理的一個(gè)基本問題，越來越多的應(yīng)用要求參數(shù)化的盡可能小針對(duì)虧格為0的封閉網(wǎng)格本文提出了一種盡可能保剛性（s-iidoble（AAP方法后給出針對(duì)該優(yōu)化模型的兩步迭代算法。算法的開始需要用戶輸入一個(gè)有效的全局（ol/lbl）思想求解得到每個(gè)頂點(diǎn)在球面上的坐標(biāo)；第二步，給定每個(gè)頂點(diǎn)在球面上的坐標(biāo)，我們更新球面半徑盡可能使每個(gè)三角形保形地從原始網(wǎng)格到當(dāng)前半徑的球面上。與現(xiàn)有的均衡角度和面積的球面參數(shù)化方法比該方得的均長（性）最。AP保剛性球面參數(shù)化不控制最大剛性的問題，我們提出了最大和平均均比較小的球面參數(shù)化方法（BD方法，包括保角度和保長度兩種類型。我們的模型是基于改進(jìn)的PS（otIometricCoordinateDescent方法優(yōu)化得到每個(gè)頂點(diǎn)的球面參數(shù)化坐標(biāo)；第二步，給定當(dāng)前基于平面三角網(wǎng)格上低幾何的研究，該應(yīng)用到圖像特征點(diǎn)匹配問題中。給定具有若干對(duì)特征點(diǎn)對(duì)應(yīng)的兩圖像，其中的噪對(duì)應(yīng)。采用擬共形函數(shù)空間作為匹配空間，建立了基于該空間的匹配模Beltrami系數(shù)的線性約束的凸二次規(guī)F-measure評(píng)估算法的準(zhǔn)第一章首先介紹了低幾何的研究意義和背景，然后給出了該課題以往方法采用的優(yōu)化角度能量和面積能量的方式，介紹了盡可能保剛性的球面參數(shù)化方法（ARAP方法。第四章中針對(duì)球面參數(shù)化中最大不可控的問題，介紹了如何將AMIPS能量應(yīng)用到球面參數(shù)化問題中，從而得到了最大和平均都比較小的有效球面參數(shù)化方法（BLD方法。第2 其在離散曲面上相應(yīng)的離散形式及在該離散形式下幾何的各種定義。連續(xù)形式下曲面的微分幾何概念和性曲CR3r(t)=(x(t),y(t),z(t)),t∈[a,或r=r(t),t∈[a,r(t)kCk類曲線。特別地，C1類曲線定義 我們稱Ck類曲線C:r(t)是正則的，當(dāng)且僅R3

{r(t),r(t),...,r(m)(t)},?t∈[a,b],m≤C1′r(t)?=0,?t∈[a, 其中，r′(t)稱為曲線在r(t)處的切向 若以l(c,d)表示曲線C:r(t)在區(qū)間[c,d]?[ab]的弧長，則l(c,d)

∫′∥r c接下來，我們利用曲線C:r(t)r(s)處的切向量對(duì)弧長的旋轉(zhuǎn)速度來定義曲線在r(s)的曲率：κ(s):=∥r′′ 因此κ(s)將切向量的導(dǎo)數(shù)r′′(s)和法n(s)緊密聯(lián)系在了一起，即r′′(s)= 其中，n(s=r′()⊥(s)⊥∥⊥是指逆時(shí)針旋轉(zhuǎn)90?C:r(t)，我們可以定義一組正交向量：{αβαβ} Cr(tFrenet標(biāo)架。其中αr()/(s)∥βr()/(s)∥。一個(gè)定義2.2我們稱Ckr1I1R3r2I2R3是等價(jià)的，如果存在一個(gè)Ck?:I1→I2，使得r1(t)=r2(?(t)),?t∈且′?(t)?=0,?t∈r2r1Ck曲線集合的一種等價(jià)曲線的微分幾何性質(zhì)（弦長、Frenet標(biāo)架和曲率）在重新參數(shù)化下不變從而滿足等價(jià)類性質(zhì)，這恰恰也是我們?cè)诘蛶缀窝芯恐幸玫降暮苤匾男郧鶶?R3x(u,v)=(x(u,v),y(u,v),z(u,v)),(u,v)∈??x(u,vkkCk類曲面。特別地，C1定義 我們稱Ck類曲面x(u,v)是正則的，如果滿足以下條件x(uvCkx(uv)、y(uvz(uv具有直k階的連續(xù)偏x(u,v)是同胚，即逆S→?存在且連續(xù)對(duì)于任意xu(u0v0)∈S，xu(u0v0)=?x(u0v0)，xv(u0v0)=?x(u0 xuxv?=0給出曲S:x=x(u,v)上的C:u=u(t),v=或x=x[u(t), du+

=xu vdx=xudu+ ds2=dx2=(x +x

=x

+2xxdudv+xdv u u 定義2.4 我們稱(2.6)式中關(guān)于微分du，dv的二次形式為曲面S的第一基本形式，用I表示：I=Edu2+2Fdudv+ E=xu·xu,F=xu·xv,G=xv· 假設(shè)曲線CA(t0)，B(t1)AB表示

∫ ∫t√ 1

du s dt= E( )2+2F +G( dt S:x=x(uv)(uv)∈??R2決定的。給定參數(shù)(u0v0)處的方向?qū)?shù)ˉ=(uwvw)T，考慮(u0v0)的直線(uv)=(u0v0tˉ在曲面上的對(duì)應(yīng)曲線Cw(t)=x(u0+tuw,v0+x(u0,v0)處的方向w=?Cw(t)t0。通過鏈?zhǔn)椒▌t，我們可以w=JˉJx(u0v0)J

=[x,x 雅克比矩陣非常直觀地刻畫了從參數(shù)域ˉ到曲面S2.1圖 從參數(shù)域?的方向?qū)?shù)ˉ到曲面S上的切方向w的變換(2.8)(2.10SIJTJˉ1dudvˉ2δuδv是參數(shù)域上的兩個(gè)單位方向?qū)?shù)，則ˉ1ˉ2的夾角：θˉ=arccos(ˉTˉ2)=arccos(duδu+Sw1w2wTw2=(Jw1)T(Jw2)=ˉTIˉ w1w2θ=

wT 1·2Eduδu+F(duδv+dvδu)+= √ Edu2+2Fdudv+ Eδu2+2Fδuδv+w1w2∥w1∥

)ˉ1

Edu2+2Fdudv+ ∥w2∥ )ˉ2 ∫∫σ dσ

|xu× D(u,v)u(xu×xv)2=x2x2?(xuxv)2=EG?F2>u ∫∫σ EG?F DS的(u0,v0)ˉ=(uw,vw)TS上對(duì)應(yīng)的x(u0,v0)處的方向?qū)?shù)w，則(u0,v0)附近的圓區(qū)域被到曲面上 橢圓的兩個(gè)正交軸的長度分σ1=λ1σ2=λ2，即正交σ1和σ2恰恰是雅克比矩陣J的兩個(gè)奇異值。det(I?σId)=√ σ1σ2

1/2(E+G) (E?G)2+4F√ 1/2(E+G) (E?G)2+4FE、F、G圖 的各向異性曲面之間定義 假設(shè)兩個(gè)曲S1:x1=x1(u1, (u1,v1)∈D1?S2:x2=x2(u2, (u2,v2)∈D2?u2=u2(u1,v2=v2(u1,其中函數(shù)u2(u1,v1)，v2(u1,v1)?(u,v

2=

?=?(u1,

則S1和S2之間的一一對(duì)應(yīng)關(guān)系稱為S1到S2的=u2=u2(u1,v2=v2(u1,使x2=x2[u2(u1,v1),v2(u1,v1)]=x2(u1,S1S2具有相同的參數(shù)(u1v1)S1S2S1x1(u1v1與S2上的點(diǎn)x2[u2(u1,v1),v2(u1,v1)]S1上的曲線u1=u1(t),v1=v1(t)(t0≤t≤t1)與曲面S2上的曲線x2[u2(u1(t),v1(t)),v2(u1(t),v1(t))](t0≤t≤t1)對(duì)應(yīng)。因此，參數(shù)變換建立了兩曲面上的點(diǎn)和曲線的一一對(duì)應(yīng)關(guān)系。接下來定義2.6曲面S1與曲面S2之間的一個(gè)（變換）F稱為等距（變換）或保長（變換如果F能夠保持曲面上任意曲線長度不變。定理2.1曲面S1與曲面S2之間的一個(gè)（變換）F是等距的充要條件I1= 定義2.7曲面S1與曲面S2之間的一個(gè)（變換）F稱為保角（變換F能夠保持曲面上對(duì)應(yīng)曲線的夾角不變。定理2.2曲面S1與曲面S2之間的一個(gè)（變換）F是保角的充要條件I2=c(u2,v2)I1,c(u2,v2)> 定義2.8曲面S1與曲面S2之間的一個(gè)（變換）F稱為保面積（變換F能夠保持曲面上對(duì)應(yīng)區(qū)域的面積不變。定理2.3曲面S1與曲面S2之間的一個(gè)（變換）F是保面積的充要條 F1G G其中Ei，F(xiàn)i，Gi分別是曲面Si(i12的第一類基定理2.4 曲面S1與曲面S2之間的一個(gè)（變換）F是等距（變換）的充要條件是F既是保角（變換）又是保面積（變換，即面的內(nèi)蘊(yùn)量（曲線的弧長、夾角及曲面域的面積，因此，等距是曲面間最拓?fù)渫瑯?gòu)于球的曲面倒球面上，除了球面本身之外的曲面均不存在等距。離散曲面上的幾何論和研究定義在三角網(wǎng)格曲面上的各種幾何。三角網(wǎng)格上的基本概定義 給定兩個(gè)拓?fù)渫叩娜蔷W(wǎng)格曲面M1和M2，則原象M1和M2之間的對(duì)應(yīng)關(guān)系稱為M1到M2的特別地，三角網(wǎng)格的參數(shù)化是一種特殊的，即從參數(shù)域D到三角網(wǎng)格曲面M的一一。定理 給定兩個(gè)拓?fù)渫叩娜蔷W(wǎng)格曲面M1和M2，M1到M2的定理 給定兩個(gè)拓?fù)渫叩娜蔷W(wǎng)格曲面M1和M2，M1到M2的FM2上的每個(gè)三角形定向一致（無翻轉(zhuǎn)三角形定理 給定兩個(gè)拓?fù)渫叩娜蔷W(wǎng)格曲面M1和M2，M1到M2的FM1M2在幾何的應(yīng)用中，的局部單射性質(zhì)和全局雙射性質(zhì)是該問題求解向排列（無翻轉(zhuǎn)出現(xiàn)，因?yàn)榈难趴吮染仃囀蔷植慷x的，因此，局部l數(shù)化及平面網(wǎng)格形變的求解過程中，大部分科研成果都是利用雅克比矩陣考慮（）素圖2.3展示了三角網(wǎng)格曲面上不類型的幾何。 （A）全局雙 （B）局部單 （C）局部翻圖 （MetricDistortion。這些幾何度量一般是通過幾何前后兩個(gè)曲面上對(duì)應(yīng)元素的面積、角度和長度來描述。因此，對(duì)于兩個(gè)拓?fù)渫叩娜蔷W(wǎng)格曲面M1和M2，我們除了要求M1到M2的F是局部單射或者全局雙射，還需要極小化該的。例如，圖2.4中展示了極小化不同的下的網(wǎng)格變形結(jié)果。(A)展示了變形要求，其中紅色的點(diǎn)代表固定不動(dòng)，綠色的點(diǎn)代表被強(qiáng)制移動(dòng)至箭頭方向；(B)和(C)分別是滿足以上位置約束的角度極小和長度極小（A）網(wǎng)格變形 （B）角度極圖 極小化不同下的網(wǎng)格變形三角網(wǎng)格上

（C）長 在數(shù)字幾何處理的很多應(yīng)用中，要求的量越低越好，例如紋理映射，曲面對(duì)應(yīng)等。因此，三角網(wǎng)格曲面上質(zhì)量的好壞主要取決于的大 假設(shè)原始三角網(wǎng)格曲面M1上的三角形Ti經(jīng)過f的作用變?yōu)槿蔷W(wǎng)格曲面M2上的τi，即f(Ti)=fJf=[fu,fv]。特別地，如fM1JfTi2.1.2節(jié)對(duì)雅克比矩陣各向異性的介紹可知，對(duì)Jf做奇異值分解（SVD）可得 Jf=UΣVT= VT UV分別是R3×3R2×2的正交矩陣，且對(duì)應(yīng)的列向量分別U1，U2，U3V1，V2?？紤]三Ti上的任(uv附近處的圓域經(jīng)過f的作用變?yōu)闄E圓區(qū)域，式子(2.15)恰恰刻畫了f的作用過程，其分解成三步來介紹，具體分解2.5。圖 f的奇異值分解[147]VT旋轉(zhuǎn)(uvu-v-V1V2Σu-v-σ1σ1，此時(shí)圓域變成了橢圓U(u,v)V1V2U1U2f是保角當(dāng)且僅當(dāng)σ1=f是保面積當(dāng)且僅當(dāng)σ1σ2=f是保長度當(dāng)且僅當(dāng)σ1=σ2=1 不同的問題中。為了方便描述，我們用σ1和σ2表示f的最大奇異值和最小奇異值?；趦?yōu)化的目標(biāo)不同，能量函數(shù)可分為如下3類。調(diào)和E(σ, 1σ2+ 2)=2( 往往邊界對(duì)應(yīng)已經(jīng)引入了非常大的，即使Dirichlet能量達(dá)到了極小值，但是并性質(zhì)（σ2可能取到0。保角保角作為一種特殊的調(diào)和[147]，主要有幾種能量表達(dá)形式。其中MIPS能量E(σ,σ)=σ1+σ2 σ1=σ2時(shí)，EM(σ1,σ2)2σ2→0時(shí)，EM→∞，因此，該能一種保角能量LSCM（LeastSquaresConformalMaps[30;1481ELSCM(σ1,σ2) 2固定邊界上兩個(gè)點(diǎn)，LSCM即可通過求解一個(gè)線性系統(tǒng)得到。但是并不能排除σ1=σ2=0情形的出現(xiàn)，即并不能保證得到保角局部單射。此外，該能量的優(yōu)保長tiontensor[5]定義的EG(σ,σ)=(σ2?1)2+(σ2? 以及后來類似格林-拉格朗日變形量的、被稱作AR EARAP(σ1,σ2)=(σ1?1)2+(σ2? 以上兩種能量形式均能在σ1σ2=1時(shí)取得最優(yōu)值0，但是并不能避免σ2=0，即不能保證局部單射性質(zhì)。為了避免三角形的出現(xiàn)（σ1→∞），L∞拉伸能量和L2拉伸能量應(yīng)運(yùn)而生[149]EL∞=EL

(σ2+1

為了保證的有界性，對(duì)稱的L∞拉伸能量被定義Esym=max{σ1, σ1σ20這兩種情形，保證了局部單射性質(zhì)，但類似于MIPS能量的定義，保長度的能量被定義為Eisometric(σ1,σ2)=σ2+σ2+σ?2+ σ1=σ2=1時(shí)，Eisometric2σ1σ2→0這兩種情形，保證了局部單射性質(zhì)。為了保證全局雙射性質(zhì)，采用懲罰邊界自交的技術(shù)[151]，進(jìn)而保證最后得到的的全局雙射性質(zhì)。為了衡量和比較的，我們一般定義三角形τ上的以下三種類型：角或

(τ)=

+σ2,τ

(τ)=σ1,τ σ面σ

Darea(τ)=σ1,τσ2,τ

σ1,τ或1長度（剛性

Darea(τ)=max{σ1,τσ2,τ,

1σDiso(τ)=max{σ1,τσ或

Diso(τ)=(σ1,τ?1)2+(σ2,τ? 其中σ1,τ和σ2,τ分別是f在三角形τ上的雅克比矩陣Jf的最大奇異值和最 平

DDDD

∑ ωτDangle(τ ωτDarea(τ

ωτDiso(τ∑其中，三角形τ的權(quán)重ωτ=Aτ τ∈MAτ，Aτ是指三角形τ的面積最DD

=maxDangle(τDmax=maxDarea(τ Dmax=maxDiso(τ標(biāo)準(zhǔn)

DD

√ 1

angle(τ)?D

Darea

(Darea(τ)?Davg τDdev

(τ)?

nτM本章小三角網(wǎng)格曲面上幾何不同形式的的定義。第3 本章我們了一種盡可能保剛性的球面參數(shù)化方法，該方法是平面域上盡可能保剛性的參數(shù)化方法在球面域上的推廣。對(duì)于虧格為0的封閉三角網(wǎng)格，我射到該球面上。我們首先分析了二維及三連續(xù)和離散的AR-Rigid-引網(wǎng)格參數(shù)化是數(shù)字幾何處理領(lǐng)域非常基礎(chǔ)且非常重要的一項(xiàng)技術(shù)，在計(jì)算機(jī)圖學(xué)域有廣的用比紋理及理細(xì)遷、格補(bǔ)域和三網(wǎng)曲之間一。據(jù)數(shù)的不，格數(shù)化要為平0極小化不同幾何的球面參數(shù)化的研究已經(jīng)很多，包括保角度的球面參數(shù)化[35;36;88–90;106–108;110–112]、保長度的球面參數(shù)化[33;90–94;98;99]。其中，保長度的球面參化一般是通過優(yōu)化保角度能量和保面積能量的。此外，基于曲面流的方法也被廣泛地應(yīng)用于球面參數(shù)化。Kazhdan等人[152]修改了傳統(tǒng)的平均曲率流，0本章內(nèi)容主要來自于WangCLiuZLiuL.：As-rigid-as-possiblesphericalparametrization.中的一部的Ricci能量的嚴(yán)格非凸性質(zhì)，該能量的優(yōu)化只能收斂到局部的最優(yōu)解[155]Chen等人[156Ricci能量并提出了一個(gè)求解球面參數(shù)化及曲面問題的有效算法。類似平面參數(shù)化方法，考慮曲面網(wǎng)格上每個(gè)三角形的剛性性質(zhì)，直接將虧格為0的封閉三角網(wǎng)格曲面到球面網(wǎng)格上不失為一種有效的思路。在本章中，我們推廣平面上盡可能保剛性的參數(shù)化方法[125]至球面域，即盡可能保剛性地將虧格為0的封閉三角網(wǎng)格曲面的每個(gè)三角形到一個(gè)最優(yōu)半徑的球即迭代更新球面半徑和球面頂點(diǎn)位置。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的球面參數(shù)化算法[35;89;94;111]相比，我們的算法可以給出最低的平均剛性（長度）預(yù)備知ARAP能ARAP能量在數(shù)字幾何處理中有著非常廣泛的應(yīng)用，包括網(wǎng)格編輯[41]、網(wǎng)格形變[157;158]、仿真[126]以及平面參數(shù)化[125;159]等。該能量度量了函數(shù)的一為網(wǎng)格參數(shù)化和網(wǎng)格形變提供了重要的準(zhǔn)則。Chao等人[126]分析了ARAP能量與傳統(tǒng)方陣中的彈的關(guān)系， 了二維和 中ARAP能量在網(wǎng)格形變和參數(shù)化中的應(yīng)用。Sorkine等人[41]在網(wǎng)格形變中利用該則去保持頂點(diǎn)一鄰域的局部細(xì)節(jié)。在網(wǎng)格插值[157;158]問題 形狀和目標(biāo)形狀，因此該準(zhǔn)則同樣起著重要的作用。Liu等人[125]利用該準(zhǔn)則處理拓?fù)渫瑯?gòu)圓盤網(wǎng)格的平面參數(shù)化，盡可能保剛性地將每個(gè)三角形參數(shù)化到平面上。MylesZorin[159推廣了該思想到多虧格曲面上無縫的全局保剛性的平面參數(shù)ARAP能量去優(yōu)化的一階微商和旋轉(zhuǎn)矩陣之間的距離，實(shí)現(xiàn)了全局的盡可能保剛性的無縫參數(shù)化。接下來，給出ARAP能量的連續(xù)變分表達(dá)形式及二維和三維情形對(duì)應(yīng)的離散表達(dá)形式?？紤]連續(xù)f:M→N，f(v)=u描述了參考曲面M?Rn到變形曲N?Rn的一一對(duì)應(yīng)關(guān)系。同樣地，微分向量dv被到變形函數(shù)的一階微df，因此我們得到以下能量∫E(f)=

d?R| M式子(3.1)描述的能量度量了一階微商dfR之間的距離，即刻畫了函數(shù)f到底有多接近全等。E(f)fdδgEf=d?0E(+?g)=∫δgEf

<dg?δg,df?R

<dg,df?R 其中，<AB>=tr(ATB)是指AB的內(nèi)積算子R∈SO(n)使得E(f)取得最優(yōu)值且不依賴于變量df。上式的推導(dǎo)基于這樣的假設(shè)，即E(f)僅僅關(guān)于f的函數(shù)，因此(df?R)⊥在實(shí)際計(jì)算中，旋轉(zhuǎn)矩陣R是依賴于連續(xù)f的，即R=R(f)，上式中Euler-Lagrange方程δgEf=0便轉(zhuǎn)化成了下列非線性的Poisson方程：?f=divR(f R3空間的二維流形的單純復(fù)形和三維假設(shè)二維流形的單MVEF)，其V={vii=0Nv1}、E{ell0Ne1}、F{τjj0Nτ1分別是三角網(wǎng)M的頂點(diǎn) τ可以表達(dá)xτ{x0x1x2}，對(duì)應(yīng)的參數(shù)化網(wǎng)格曲面的三角形 uτ={u0u1 在二維情形，式子(3.1)對(duì)應(yīng)的離散表達(dá)式恰恰是分片線性的Dirichlet能 E(f)=1∑∑cot(θi)∥(ui?ui+1)?R(xi?12, 4 4τ=1

其中θi是三角形xτ(xixi+1的對(duì)角，這里的ii3后的值 δE(f)

1{

[cot(θ)+cot(θ)](u?u ∑

[cot(θij)Rτ(i,j)+cot(θji)Rτ(j,i)](xi? xiuii的坐標(biāo)，τ(i,j)圖 (i,j)θij(i,j)3.1所示。該式子中的第一項(xiàng)表示Laplace-Beltramiuii的一鄰域三角ui的面積梯度和。由式子(3.3)i的 TuT={u0u1u2u3}

E(f)= T=1 ∥xT?xT∥∥(uT?uT)?RT(xT?xT)∥{kl={0123ij}，θi,j是四xT(xi,Txj)T對(duì)應(yīng)的二面角。ui(3.2)M上的離散δE(f)= {(w+w)(u?u)?(w +w )(x?x

T T 盡可能保剛性的平面參數(shù)化方這里主要介紹盡可能保剛性的平面參數(shù)化方法[125]從局部到整體的思想。具體來說，第一步是將三角網(wǎng)格曲面M上的每個(gè)三角形τ全等 到一個(gè)局部的平面坐標(biāo)系，該步驟一般稱為局部攤平過程，如圖3.2中(a)到(b)中紅色標(biāo)記的三角形，該過程 假設(shè)三角形τ在局部坐標(biāo)系下的三個(gè)頂點(diǎn)坐標(biāo)分別為{p0,p1, R2i012，對(duì)應(yīng)的初始參數(shù)化坐標(biāo)分別為{q0q1q2}，qi∈R2i=0 (2.10τJτ，也可以通過下列協(xié)方差矩陣[41]得到： Jτ(q) cot(θi)(qi?q1? 圖 盡可能保剛性的平面參數(shù)化方法為了方便研究Jτ的，我們假設(shè)Lτ?是滿足與Jτ在某種意義下距離最近Lτ?=argmin{Lτ|d(Lτ,Jτ Fd(Lτ,Jτ)=∥Lτ?JτFLτJτ 圖 不同意義下的Lτ圖3.3展示了不同意義下的。其中，(a)和(b)中的黑色三角形分別LτLτ作用下的三角形及保剛性變換Lτ作用下的三角形。3.2(c)?；诘?.2.1節(jié)對(duì)ARAP能量的介紹，我們不難想到，在三角網(wǎng)格曲面M上極小化ARAP能量(3.4即可，即求解線性系統(tǒng)δiE(f0，i12Nv。δiE(u)的定義見公式(3.5)，這里不再一一敘述。盡可能保剛性的球面參數(shù)的球面參數(shù)化結(jié)果，如圖3.4所示。圖3.4 三角形至合適半徑上；(右)盡可能保剛性的球面參數(shù)化結(jié)果?；谌SARAP能量的球面參數(shù)化模v 攤平三維原始網(wǎng)格曲面上的每個(gè)三角形至“合適”的球面上且不考慮任何圖3.4中（中所。們記攤ττ={0,1,2τ定攤平的徑，將攤的三角格曲面縫一個(gè)保持向一致圖3.4中的右所示顯，部分格在縫合的過程中發(fā)生了很大的形變。本章中，我們要求每個(gè)三角形做球面上可能保剛性的球面半徑。綜上所述，我們的目的是尋找從原始網(wǎng)格到分片線性的三維球面網(wǎng)格的盡可能保剛性的，并記該三維球面網(wǎng)格坐標(biāo)集合為f(u={0,1,N?1}，ui∈3，i=,,vv τ，我們記它對(duì)應(yīng)的球面參數(shù)化坐f(xτuτ{u0u1 τ的攤平的三角網(wǎng)格坐標(biāo)xτ和對(duì)應(yīng)的參數(shù)化坐標(biāo)uτ，并不能找到一個(gè)唯一的3的雅克比矩陣（dfO={000}，使得每個(gè)三角形構(gòu)成對(duì)應(yīng)的四面體，此時(shí)該原始網(wǎng)格曲面變xτxT={xτO {xτxτxτO}，三角形uτ對(duì)應(yīng)著四uT={uτO}={uτuτuτO}3.6所示。利用輔助頂點(diǎn)，我們可以很容易地計(jì)算出xT和uT之間的fτ，并且計(jì)算這兩個(gè)四面體之間的常數(shù)3×3雅克比矩陣。TuTminE(uT,RT,r)=

FVT∥J(uT)?RT∥2FT

Ts.t.∥ui∥2=r2,i=0,1,TVT是四面體T的體積，J(uTxTuT33的雅克比矩陣，r是uTRTRτARAP能(3.6)(3.10)中的能量函數(shù)重寫成關(guān)于球面參數(shù)化坐標(biāo)u和攤平網(wǎng)格坐標(biāo)x的形式：E(u,R,Nτ1=

ii

i+112

)∥

—O∥∥(uτ?u

τ(xτ?xτ+c(βo)?2(u?O)?Rτ(xi? 1∑=

(xi?1)12τ=1

)? +o(βo?+2∥∥?R 其中αi,i+1是邊(xixi+1)的對(duì)角，βi,o是邊(xiO)的對(duì)角。注意到約束 從局部到整體的球面參數(shù)化方為了避免直接優(yōu)化非線性約束問題，我們采用兩步迭代的算法將球面參數(shù)ur(3.1)uR巧妙地分離開來。保剛性的球面參數(shù)化結(jié)果，如圖3.5所示。3.5Cube模型為例，給定一個(gè)有效的球面度）（各個(gè)的定義見第2.2.2節(jié)中等式(2.26)、等式(2.24)及等式(2.29)），rrr固定時(shí)，我們采用局部/u用奇異值分解（SVD分解）計(jì)算出每個(gè)四面體的最優(yōu)旋轉(zhuǎn)矩陣（RTRτ到球面參數(shù)化坐標(biāo)u。]陣。與此不同的是，我們這里通過求解xTuT之間的最優(yōu)旋轉(zhuǎn)矩陣RTxτuτRτ=RT，如圖3.6所示。由式圖 ∑Ex

其中{kl{0123ij}，θi,j是邊(xixj)在攤平四面體xT中的 w?∥e′?RT2

5∑Sx

e′T=UxDxVT ii U。則最優(yōu)旋轉(zhuǎn)矩陣RT= U。RTxT上，得到的三角網(wǎng)格可3.4（中）所示。因此，我們需要通過全局求解將所有的三角形縫一個(gè)拓?fù)潢P(guān)系正確的有效參數(shù)化結(jié)果。rRT(3.11)E(uR1[∑E(u,R,r) w∥u—

x

+

wij∥(ui?uj)?

(xi?xj)∥2點(diǎn)i的坐標(biāo)T(i,j)是含有半邊(i,j)的四面體；wij和wio分別是邊((ij)和(io))對(duì)應(yīng)的權(quán)重；vei的鄰域數(shù)量;Tve(i,O)所有四面體；RTveTve對(duì)應(yīng)的旋轉(zhuǎn)矩陣；Nve是集合ve所含元素的個(gè)數(shù)，如圖3.7所示。矩陣群R固定時(shí)，僅需要式子(3.7)中的一階變分滿足δiE(u)=圖 頂點(diǎn)i的一鄰域四面體及二面 (wij+wji)(ui?uj) wioui ∑(wijRT(i,j)+wjiRT(j,i))(xi

wioRTve(k)半徑為r的球面上。r在這里，我們一下如何尋找到最優(yōu)的球面半徑r。正如前面提到的，球面半徑r的選擇非常重要，因?yàn)樗苯佑绊懙角蛎鎱?shù)化的剛性（長度）。盡量保持三角形的面積。為此，我們?cè)O(shè)置初始的球面半徑r0為：ττr0Aττ的面積。在迭代的過程中，并不能保證三角形的面積始終等 Sk+1

rkrk步迭代的值，Skk步迭代投影之前參數(shù)化曲面的面積。 輸入:0M={VEF輸出:第一步}第二步實(shí)驗(yàn)結(jié)我們?cè)谒暮耍?.16GHz）2GB內(nèi)存的微機(jī)上使用實(shí)現(xiàn)了上述SVD分解算法（矩陣的極分解）求解局部最優(yōu)旋轉(zhuǎn)矩陣，全局求解采用自帶的稀疏矩陣求解來得到縫合的參了提高算法的效率，固定一個(gè)球面半徑rCholesky矩陣分解。 。我們首先將原始網(wǎng)格曲面和參數(shù)化曲面的每個(gè)三角形τ分別攤平到同一個(gè)平面上，然后計(jì)算它們之間的雅克比矩陣Jτ的奇異值σ1和σ2，且σ1>σ2，并利用第二章中定義的角度、面積及剛性（長度）,分別見式子(2.24)、(2.26)及Conformal參數(shù)化[35]、Harmonic參數(shù)化[111]、Convex參數(shù)化[89Hierarchical參數(shù)化[94]。為了方便比較，我們歸一數(shù)化[89]、Harmonic參數(shù)化[111]Conformal參數(shù)化[35]結(jié)果均縮放至我們優(yōu)化的球面半徑大小，結(jié)果見圖3.83.9。3.8Max-Planck模型的球面參數(shù)化結(jié)果。(a)Harmonic參數(shù)化結(jié)果[111]；(b)Conformal參數(shù)化結(jié)果[35]；(c)Hierarchical參數(shù)化結(jié)果[94]；(d)我們的結(jié)果。括號(hào)中的數(shù)據(jù)分別代3.9ARAP球面參數(shù)化在不同模型上的表現(xiàn)。括號(hào)中的數(shù)據(jù)分別代表平均面積、平均角度和平均剛性（長度），r是我們計(jì)算得到的最優(yōu)半徑。參數(shù)化[111]方法不能保持角度和面積 ；ofmal參化結(jié)3]方直優(yōu)角度即具較的均角度，是面積損較大因此均剛（長度也大；irrhil參數(shù)化結(jié)果[94]雖然同時(shí)考慮了角度和面積，但是從結(jié)果上看，他們的結(jié)果具有更好的保面積性質(zhì)，因此，特征區(qū)域的三角形變得狹長，從而損失了大量從度（長度）表 -/-/-/-/-/表3.2 /////相比于Conformal方法[35]，我們的平均角 除此之外，我們也計(jì)算了情形的剛性（長度），見表3.2算法分不同初始參數(shù)化的球面參數(shù)由第3.3.2節(jié)的介紹可知，我們的算法需要一個(gè)有效的球面參數(shù)化結(jié)果作為Conformal方法[35]Harmonic方法[111]。給定不同的初始球面參數(shù)化結(jié)果，我們即好的初始參數(shù)化能夠使算法很快地收斂到最優(yōu)值。表3.3統(tǒng)計(jì)了不同初始參數(shù)表3.3 模型統(tǒng)計(jì)及算法表現(xiàn)。v代表頂點(diǎn)數(shù)量，f代表三角形數(shù)量，Radius代表最優(yōu)半徑及Time(s)代表運(yùn)行時(shí)間（以秒為單位。我們使用不同的初始值，包括Convex參數(shù)化[89],Harmonic參數(shù)化[111]及Conformal參數(shù)化[35]，及不同初值下的運(yùn)行時(shí)（秒 Radius Max-Planck// // // // // //// ////不同分辨率網(wǎng)格的球面參數(shù)會(huì)千差萬別？為此，我們測試了我們的方法對(duì)不同分辨率網(wǎng)格的敏感性。圖3.11Skull模型為例，展示了不同分辨率下我們算法的結(jié)果。其中，(a)3.10ARAP球面參數(shù)化的表現(xiàn)。(a)Convex參數(shù)化[89](b)Harmonic參數(shù)化[111為初始值；(c)Conformal參數(shù)化[35]為初始值。括號(hào)中的數(shù)據(jù)分別代表平均面積、平均角度及平均剛性（長度），r代表最優(yōu)球面的網(wǎng)格數(shù)據(jù)具有明顯的各向異性，(b)中的網(wǎng)格數(shù)據(jù)較為均勻。從實(shí)驗(yàn)數(shù)據(jù)可知，對(duì)于不同分辨率的虧格為0的網(wǎng)格曲面，我們的方法返回的值相差并不大。算法的收能量的優(yōu)化得到的。為了證明我們兩步迭代算法的有效性和收斂性，我們繪制了圖3.9中各模型的ARAP能量曲線，見圖3.12。從各條能量曲線可以看復(fù)雜幾何網(wǎng)格的球面參數(shù)圖3.11 不同分辨率網(wǎng)格上ARAP球面參數(shù)化的表現(xiàn)。(a)各向異性的Skull模型及它的ARAP球面參數(shù)化結(jié)果；(b)各向同性的Skull模型及它的ARAP球面參數(shù)化結(jié)果。括號(hào)中的數(shù)據(jù)分別代表平均面積、平均角度及平均剛性（長度），r代表最優(yōu)（長度）來保證該區(qū)域參數(shù)化的有效性。具體來說，對(duì)于我們的方法輸出使用調(diào)和能量[111]來重新優(yōu)化該翻轉(zhuǎn)或折疊區(qū)域的頂點(diǎn)位置，直到?jīng)]有翻轉(zhuǎn)三角改變了特征區(qū)域的值，因此，其他區(qū)域仍然較好地保持了剛性（長度）。本章中除了圖3.13BunnyHand模型之外，其他模型的球面參數(shù)化圖 圖3.9中各模型的三維ARAP能量曲本章小針對(duì)虧格為0的封閉三角網(wǎng)格曲面的低球面參數(shù)化問題，本章提出了ARAP能量，從而找到三角網(wǎng)格曲面的每個(gè)三步，我們根據(jù)當(dāng)前計(jì)算的球面參數(shù)化坐標(biāo)，更新球面半徑使得該球面逐漸的球面參數(shù)化方法相比，我們的結(jié)果具有最低的平均剛性（長度）。ARAP能量，并不能保證球面參圖3.13 復(fù)雜幾何網(wǎng)格的ARAP球面參數(shù)