點(diǎn)云模型上測地線的計(jì)算

1、第18卷第3期2006年3月計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)JOURNAL OF COMPUTER Al DED DESIGN & COMPUTER GRAPHICSVol 18, No 3Mar , 2006點(diǎn)云模型上測地線的計(jì)算1)杜培林1) 1,2)屠長河王文平1) (山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院濟(jì)南 250061)2) (香港大學(xué)計(jì)算機(jī)科學(xué)系香港)(dplcfan hotmail com)摘 要 給定點(diǎn)云模型上2點(diǎn)，將點(diǎn)云數(shù)據(jù)沿與xyz三坐標(biāo)軸垂直方向進(jìn)行單元剖分后，采用Dijkstra算法求岀2 點(diǎn)間的最短路徑作為初始測地線；然后通過帶弧長 最短約束的平方距離最 小化方法對 初始測地 線進(jìn)

2、行迭代 優(yōu)化,計(jì) 算得到點(diǎn)云模型上給定 2點(diǎn)間的一條樣條表示的精確測地線文中算法只需局部擬 合拋物曲面，無需對點(diǎn)云模型進(jìn)行三角化或曲面重建，適合大規(guī)模點(diǎn)云數(shù)據(jù)模型上測地線的計(jì)算關(guān)鍵詞測地線；點(diǎn)云；Dijkstra算法;平方距離最小化中圖法分類號TP391Computing Geodesics on Point Clouds1) 1) 1 2)Du Peilin T u Cha ngheWang Wen pi ng 1) ( School of Computer Scie nee, Sha ndo ng Uni v ersity, Ji nan 250100)2) ( Department of

3、 Computer Scienee, the Universityof Hong Kong, Hong Kong)Abstract Given two points on an object represented by point cloud, we first obtain an approximately shortest path betweenthe two points as an initial active curve by using Dijkstra s algorithm, then we use square distanee minim ization method

4、to compute the active curve iteratively to be the geodesicbetween the tw o points on the point cloud We define the objective function to be constraints of the distanee betweenthe active curve and the point cloud aswell as the arc len gth of the active curve, an d the n mini mize the objective functi

5、on step by step by relocati ng the con trol points of the active curve un til a con verge nee result is achieved The method avoids tria ngulat ing or recon struct ing the point cloud to be a surface model so that it is practicable for dealing with the point cloud with a huge number of scattered poin

6、ts第18卷第3期2006年3月計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)JOURNAL OF COMPUTER Al DED DESIGN & COMPUTER GRAPHICSVol 18, No 3Mar , 2006第18卷第3期2006年3月計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)JOURNAL OF COMPUTER Al DED DESIGN & COMPUTER GRAPHICSVol 18, No 3Mar , 2006收稿日期：2005- 04 29;修回日期：2005- 07- 14基金項(xiàng)目：國家自然科學(xué)基金 (60473127) 194-2010 Chi na Academic Journal El

7、ectronic Publishing House. All rights reserved. httpKey words geodesiccurves; point cloud; Dijkstra s0引 言點(diǎn)云模型由于具備表示三維細(xì)節(jié)能力強(qiáng)、存儲(chǔ)簡單等特點(diǎn)，成為CAD CG最常用的三維物體表示 模型之一對點(diǎn)云模型的處理已成為近年來研究的 熱點(diǎn),如研究針對點(diǎn)云數(shù)據(jù)的曲面重建、分割、布爾操作等 點(diǎn)云模型上2點(diǎn)間的測地線計(jì)算作為點(diǎn)云algorithm; square distanee minim ization模型處理的基礎(chǔ)之一，受到越來越多的關(guān)注測地線計(jì)算在計(jì)算機(jī)圖形學(xué)、圖像處理、計(jì)算幾 何、

8、計(jì)算機(jī)視覺等領(lǐng)域有著廣泛的應(yīng)用，測地線計(jì)算 算法已有很多 文獻(xiàn)1 2給出了在三角面片模型上 計(jì)算折線表示的離散測地線方法；Memoli等3提出了隱式曲面上測地線的計(jì)算方法，但其不能直接應(yīng) 用到點(diǎn)云模型上；肖春霞等4提出了利用Level Set 計(jì)算點(diǎn)云模型上2點(diǎn)間測地線的方法，它首先采用3期杜培林等：點(diǎn)云模型上測地線的計(jì)算443移動(dòng)最小平方對點(diǎn)云進(jìn)行均勻重采樣和去噪聲處理,并計(jì)算出一條虛擬的測地線，然后通過計(jì)算點(diǎn)云 模型上到虛擬測地線距離最短的點(diǎn)得到模型上的測 地線,因此給出的測地線是離散的近似結(jié)果Pottmann等5提出了一種參 數(shù)曲面上2點(diǎn)間 測地線的計(jì) 算方法，該方法將一條 活動(dòng)的B s

9、pline 曲線采用平方距離最小化樣條逼近 (square distanee minimization, SDM) 6快速迭代優(yōu)化，求得曲面上 一條樣條表示的精確測地線本文把SDM框架應(yīng)用到點(diǎn)云模型上2點(diǎn)間測地線的計(jì)算上 SDM方法避免了早期樣條逼近算 法【78對目標(biāo)數(shù)據(jù)點(diǎn)的參數(shù)化，并且因?yàn)椴捎?了較好的目標(biāo)平方距離度量方法使得迭代收斂快且穩(wěn)定,這些特點(diǎn)為點(diǎn)云數(shù)據(jù)的逼近提供了很大便利但正如文獻(xiàn)5中指出的那樣，利用SDM進(jìn)行樣條 逼近要求初始活動(dòng)曲線與目標(biāo)曲線比較接近才能得 到滿意的結(jié)果為了滿足這一要求，本文首 先采用Dijkstra最短路徑算法求出初始的一條 B spline活 動(dòng)曲線，然后將

10、SDM目標(biāo) 函數(shù)中平方距離項(xiàng) 定義 為活動(dòng)曲線到曲面的平方距離，能量項(xiàng)用作活動(dòng)曲 線弧長最短約束，迭代使目標(biāo)函數(shù)最小，計(jì)算得到點(diǎn) 云模型上2點(diǎn)間的測地線1預(yù)備知識1 1測地線微分幾何中對測地線定義如下9:對曲面 上 一條曲線，如果其上每點(diǎn)的測地曲率都等于0,則稱它為曲面上的測地線 直觀地說，曲面 上的一條非直線的曲線是測地線的充要條件為曲線上每點(diǎn)的主法線向量平行于曲面的法向量測地線的一個(gè)顯然的性質(zhì)是其上所有點(diǎn)都在曲面上；另外,類似于平面上的直線，曲面上連接2點(diǎn)之間距離最 短的路徑是測地線91 2 SDM樣條逼近SDM方法的主要思想是利用了一種加入垂足 點(diǎn)的曲率信息的平方距離度量函數(shù)，使得樣條逼

11、近過程收斂快而穩(wěn)定為敘述簡單，下面以平面上一條樣條曲線逼近目標(biāo)曲線為例，對SDM方法簡要概括如下：樣條逼近中一個(gè)重要的問題是如何定義目標(biāo)曲 線外一點(diǎn)到目標(biāo)曲線的平方距離SDM方法中定義目標(biāo)曲線外一點(diǎn) X到目標(biāo)曲線C的平方距離如標(biāo)曲線C的局部Frenet標(biāo)架，原點(diǎn)為0,其2個(gè)坐 標(biāo)軸分別為目標(biāo)曲線C在0點(diǎn)的主法向量 N和切向量T令d = X- 0，設(shè)X點(diǎn)在該局部標(biāo)架下的坐標(biāo)為(xi, x 2)，則在局部坐標(biāo)系下點(diǎn)(0，d)到 0點(diǎn)平方距離d 2的二次逼近可表示為一+d22Fd( X1, X 2)=X1 + X 2( 1)d+1|將式(i)中定義的平方距離函數(shù)Fd用于一條活動(dòng)B spline曲線逼

12、近目標(biāo)曲線從當(dāng)前活動(dòng)曲線上取適當(dāng)數(shù)目采樣點(diǎn)Sk,由式(1)計(jì)算所有Sk到目Nk標(biāo)曲線的平方距離和 I Fd ,得到目標(biāo)函數(shù)k= 1NkF = I Fd( L k( di + ci, ? , dn + en) ) + I Fsk= i(2) 其中，di為活動(dòng)B spline曲線的控制頂點(diǎn)，e為每次 迭代后控制頂點(diǎn)的增量特別指出的是，F(xiàn)s為能量函數(shù)，I為能量權(quán)因子；要求Fs為di的二次函數(shù)， Fs具有使曲線光順等作用F作為關(guān)于控制頂點(diǎn)的二次函數(shù)，由最小二乘法求解得到B spline曲線新的控制頂點(diǎn)，從而得到一條新的B spline活動(dòng)曲線，迭代使活動(dòng)曲 線離目標(biāo)曲線的平方距離和越來越小,并最終收斂

13、到目標(biāo)曲線上2點(diǎn)云模型上測地線的計(jì)算將第1 2節(jié)中SDM方法推廣，可用于點(diǎn)云模型 上測地線的計(jì)算 假設(shè)點(diǎn)云數(shù)據(jù)代表空間中一個(gè)曲 面,將預(yù)先計(jì)算出一條初始曲線作為活動(dòng)曲線，將曲面上測地線作為理想的目標(biāo)曲線，定義與式(2)形式相同的目標(biāo)函數(shù)，由于目標(biāo)曲線此時(shí)只是理想上存 在著,并沒有具體表示形式，因此我們將目標(biāo)函數(shù)中 平方距離改為活動(dòng)曲線到曲面的平方距離；將Fs定義為對活動(dòng)曲線弧長約束利用第1 2節(jié)中同樣的迭代計(jì)算使目標(biāo)函數(shù)最小：一方面,使活動(dòng)曲線到曲 面距離最小，即活動(dòng)曲線落在曲面上，以滿足測地線 的第1個(gè)性質(zhì)；另一方面，F(xiàn)s對活動(dòng)曲線弧長約束 為最短，滿足測地線的第2個(gè)性質(zhì) 由于SDM方法 是

14、一種局部優(yōu)化技術(shù)，故使本文最終求得的測地線 是局部極小的測地線56,10假設(shè)點(diǎn)云數(shù)據(jù)表示的曲面為S(u, v),在曲面下:設(shè)X在C上的垂足為0,則在垂足0處建立目向量N，主方向T1和T2,原點(diǎn)為p(uo, vo)令ki上某點(diǎn)p( uo, vo)處構(gòu)造一個(gè)右手局部笛卡兒坐標(biāo) 系，其3個(gè)坐標(biāo)軸分別為曲面在點(diǎn) p ( uo, vo)處的法 為關(guān)于主方向T的主曲率,且令i = 1 ki, i= 1,2, 則在局部坐標(biāo)系下 點(diǎn)(0, 0, d )到原點(diǎn) 的平方距 離 d的二次逼近表示為+d2d2 2Fd(X1,X2,X3)=X1 +x 2+ X3d + | 1|d+ |2|(3)目標(biāo)函數(shù)形式同式(2),

15、只是此時(shí)Fs定義為Fs=# c(t)2dt(4)本文點(diǎn)云模型上測地線算法(簡稱PCG算法)的主要步驟如下：Stepl給定點(diǎn)云模型上2點(diǎn)，采用圖的Dijkstra最短路 徑算法求出一條初始的B spline活動(dòng)曲線c(t)Step2在當(dāng)前活動(dòng)曲 線c( t)上適當(dāng)采樣,得到點(diǎn)Sk = c(tk)(k= 1,? ,N),N為采樣點(diǎn)數(shù)目；并對所有Sk找出其 在點(diǎn)云上的垂足NkStep3 構(gòu)造目標(biāo)函 數(shù) F =! Fd(Lk(d1+C1,?,dn +k= 1Cn) + !FsStep4對目標(biāo)函數(shù)F運(yùn)用最小二乘法求 解得到新的活 動(dòng)曲線c(t)Step5重復(fù)Step2Step4,直到滿足預(yù)定的閾值條件為

16、止 2 1 Dijkstra算法求初始活動(dòng)曲線SDM迭代優(yōu)化算法要求初始的活動(dòng)曲線與目 標(biāo)曲線比較接近，初始活動(dòng)曲線的好壞影響了算法 最終的結(jié)果如何求得一條較好的初始活動(dòng)曲線成 為我們要解決的問題由于2點(diǎn)之間的最短路徑一定是2點(diǎn)間的測地線，因此我們先求出給定2點(diǎn)間的近似最短路徑(路徑上可能有些點(diǎn)沒有落在模型 上)作為初始活動(dòng)曲線本文采用Dijkstra最短路徑算法計(jì)算給定2點(diǎn)間的近似最短路徑，步驟如下：Step1點(diǎn)云數(shù)據(jù)的單 元網(wǎng)格剖分 用分別垂直于x , y 和z 3個(gè)坐標(biāo)軸的3組平行平面對點(diǎn) 云數(shù)據(jù)進(jìn)行 均勻剖分， x,y和z方向剖分的步長不同，得到若干長方體盒子 其中 包含點(diǎn)云散亂點(diǎn)的盒

17、子定義為有效盒子，通過將盒子排序， 給每個(gè)盒子一個(gè)序號 設(shè)給定測地線起始點(diǎn)所在盒子的序 號N 0,終點(diǎn)所在盒子序號為 N1Step2將所有有效盒子作為 圖的頂點(diǎn)，相鄰的有效盒子 間建立一條邊,并建立一個(gè)無向圖結(jié)構(gòu),定義邊的權(quán)為2個(gè) 有效盒子中心點(diǎn)的歐氏距離盒子間分為面相鄰、邊相鄰和頂點(diǎn)相鄰3種情況Step3采用Dijkstra算法在圖上求出N 0到2的最短 路徑path ,路徑上每點(diǎn)對應(yīng)一個(gè)有效盒子Step4在path上間隔合適數(shù)目的盒子采樣得到一個(gè)有 效盒子序列，將序列中有效盒子的中心點(diǎn)連接作為初始的活動(dòng)曲線c( t)的控制頂點(diǎn)可以看出，上述步驟其時(shí)間復(fù)雜度為0( k2), k 為有效盒子數(shù)

18、目2 2目標(biāo)函數(shù)的計(jì)算由式(3)可知，目標(biāo)函數(shù) F需要求出當(dāng)前活動(dòng) 曲線c( t)上采樣點(diǎn)Sk到點(diǎn)云上的垂足的距離d和垂足處的曲率信息首先,對每個(gè) S找到點(diǎn)云數(shù)據(jù)中離 Sk距離最 近的點(diǎn)O,又由于對點(diǎn)云數(shù)據(jù)進(jìn)行了單元剖分，因此 可快速地找到O點(diǎn)的若干相鄰點(diǎn)組成鄰域點(diǎn)集在O點(diǎn)附近利用平面片 ？擬合O點(diǎn)的鄰域點(diǎn)集，將平 面片？的法向作為O點(diǎn)法向的一種近似以此法向?yàn)閦軸,以O(shè)點(diǎn)切平面為xq平面建立局部坐標(biāo) 系,從而構(gòu)造出該點(diǎn)所在的局部拋物面112 2Z(x,y) = b1 x + b2xy+ b3y + b4x + bsy + b6, 其中b= b1, b2, b3, b4, b5, b6 T為拋物

19、面方程系 數(shù),可由最小二乘法求出將Sk到局部拋物面在O點(diǎn)的切平面的距離作 為式(3)中的d,計(jì)算O點(diǎn)處局部拋物面的法向量 N,主曲率半徑 1, 2和對應(yīng)的主方向 T1, T2等信 息，具體作法可參考文獻(xiàn)12需要指出的是，此時(shí) 上面求得的向量 N,和T2都為局部坐標(biāo)值，應(yīng)把 它們再轉(zhuǎn)成全局坐標(biāo)值至此我們可以求出 c( t)上N所有采樣點(diǎn) 2到點(diǎn)云模型的平方距離和| Fkk= 1由PCG算法的5個(gè)步驟可知，除去預(yù)處理, PCG算法主要時(shí)間花費(fèi)在Step2,在第2 2節(jié)中已提到找垂足采用的方法是找點(diǎn)云上距離活動(dòng)曲線采 樣點(diǎn)Sk最近的一點(diǎn)作為垂足，利用模型已有的單元 網(wǎng)格剖分可以快速地剔除距離較遠(yuǎn)的盒

20、子中的點(diǎn) ， 從而改進(jìn)算法的時(shí)間復(fù)雜性 另外，由于本文PCG 算法只需構(gòu)造出垂足點(diǎn)處的局部拋物面，利用最小二乘法解一個(gè)線性方程組即可，不需要對點(diǎn)云模型 進(jìn)行三角化或曲面重建，計(jì)算量小且內(nèi)存占用少，因 而算法快并容易實(shí)現(xiàn)3實(shí)驗(yàn)結(jié)果與比較為了說明PCG算法對點(diǎn)云模型的精確性，我們 對球上面的點(diǎn) 隨機(jī)均勻采樣得到一個(gè)球的點(diǎn)云模型,在此點(diǎn)云模型 上，利用PCG算法計(jì)算 得到的2 點(diǎn)間的測地線與球上 2點(diǎn)之間真正的測地線 (即2 點(diǎn)間的大圓弧)作了比較 另外，通過在復(fù)雜模型上 的實(shí)驗(yàn)結(jié)果表明，PCG算法對有復(fù)雜細(xì)節(jié)模型上2點(diǎn)間的測地線的計(jì)算是非常有效和穩(wěn)定的如圖1所示，用來模擬球的點(diǎn)云數(shù)據(jù)共360000

21、個(gè)散亂點(diǎn) 藍(lán)色曲線為球上大 圓弧即真實(shí)測地線，長度為3 141593;紅色曲線為 PCG算法求得的測 地線,長度為3 141595:可見2條測地線長度相差 無幾除兩者長度對比外，我們還對比了它們到球 面的距離：從曲線上離散得到的若干點(diǎn)，計(jì)算這些點(diǎn) 到球心的距離與球半徑的差的平均值，記作Average,明顯地，真實(shí)測地線 Aver age= 0實(shí)驗(yàn)表明，本 文算法中僅采 用Dijkstra算法求得的 初始活動(dòng) 曲 線,其Average= 0 015617,而將初始活動(dòng)曲線采用 SDM迭代7步后，最終得到的測地曲線Average =0 000026由以上數(shù)字對比及圖1中紅藍(lán)2條測地線重合程度可見，

22、PCG算法在點(diǎn)云模型上求得的測地線是比較準(zhǔn)確的1車七斡袪踣果紅找）與b去掉球馬虹週2殺真蜜測地踐藍(lán)址比較裁地跋的放大圖1球點(diǎn)云模型上的測地線圖2中彌勒佛的點(diǎn)云模型，共543 652個(gè)點(diǎn)，紅 藍(lán)2條測地線均由PCG算法求得 其中，藍(lán)色測地 線始終沿著腰部凹進(jìn)去的部分，紅色測地線沒有穿 透模型表面的細(xì)小隆起，表明了 PCG算法對復(fù)雜點(diǎn) 云模型的有效性圖2復(fù)雜細(xì)節(jié)模型上的測地線圖3, 4中龍的點(diǎn)云模型 包含437 645個(gè)點(diǎn) 其 中，圖3所示為未加Dijkstra算法預(yù)處理，初始曲線為2點(diǎn)之間的直線段；圖4所示為采用Dijkstra算法預(yù)處理得到初始活動(dòng)曲線后又進(jìn)行迭代的結(jié)果可以看出，初始曲線對算法

23、結(jié)果的影響是非常大的圖3初始活動(dòng)曲線為2點(diǎn)間的直線圖4初始活動(dòng)曲線為2點(diǎn)間近似最短路徑4結(jié)論與進(jìn)一步工作本文算法通過將點(diǎn)云模型進(jìn)行單元剖分后，利用Dijkstra算法求出2點(diǎn)間的近似最短路徑作為初 始活動(dòng)曲線，通過定義目標(biāo)函數(shù)約束活動(dòng)曲線到點(diǎn) 云模型的距離以及活動(dòng)曲線的弧長，經(jīng)過迭代優(yōu)化計(jì)算得到最終的測地線該算法不需要對模型三角化或進(jìn)行曲面重建來建立點(diǎn)云的拓?fù)溥B接信息，因而適合處理大規(guī)模點(diǎn)云數(shù)據(jù)模型計(jì)算活動(dòng)曲線上一點(diǎn)到點(diǎn)云模型的距離是本文 方法的關(guān)鍵，算法在實(shí)現(xiàn)中簡單地采用了點(diǎn)到模型 上最近點(diǎn)的距離作為此距離，容易受到點(diǎn)云采樣噪 聲或采樣稀疏的影響因此，如何更加精確地找到垂足,從而計(jì)算點(diǎn)到點(diǎn)云

24、模型的距離是我們進(jìn)一步 要研究的工作 在對目標(biāo)函數(shù) F的迭代過程中，如 何自動(dòng)確定一個(gè)最優(yōu)的能量權(quán)因子！ 一直以來是一個(gè)難以解決的問題,!值過大或過小都會(huì)影響活 動(dòng)曲線的收斂速度和效果另外，根據(jù)點(diǎn)云模型的局部特性對點(diǎn)云模型進(jìn)行非均勻單元剖分，在算法效率和精確性方面會(huì)有一定的改善，這也是需要進(jìn)一步研究的工作之一參考文獻(xiàn)1 Kumar GV V Ravi, Srinivasan Prabha, Holla V Devaraja, et al Geodesic curve computations on surfaces J Computer Aided Geometric Design, 2003

25、, 20(2) : 119- 1332 Kimmel R, Sethian J Computing geodesic paths on manifoldsJ Proceedings of National Academy of Sciences, 1998, 95 ( 15): 8431- 84353 M emoli Facundo, Sapiro G Fast computation of weighted dis tance functions and geodescs on implicit hyper surfaces J Journal of Computational Physic

26、s, 2001, 173( 2): 730 7644 Xiao Chunxia, Feng Jieqing, Miao Yongw ei, et al Geodesic path computation and region decomposition of point basedsur face based on level set method J Chinese Journal of Comput ers, 2005, 28( 2): 250- 258 (in Chinese)(肖春霞，馮結(jié)青，繆永偉，等 基于Level Set方法的點(diǎn)采樣 曲面測地線計(jì)算及區(qū)域分解 J計(jì)算機(jī)學(xué)報(bào)，200

27、5, 28( 2): 250- 258)5 Pottmann H , Leopoldseder S, H ofer M Approximation with active b spline curves and surfacesC Proceedings of Pacific Graphics 2002, Beijing, 2002: 8- 256 Pottmann H , Hofer M Geometry of the squared distancefunc tion to curves and surfaces M Hege H, Polthier K Visual ization an

28、d Mathematics III New York: Springer, 2003: 223-2447 Hoschek J, Lasser D Fundamentals of computer aided geomet ric design M Natick, MA: AK Peters Ltd, 19938 Lee E T Y Choosing nodes in parametric curve interpolationJ Com puter Aided Design, 1989, 21( 6) : 363- 3709 Do Carmo M P Differential geometry of curves and