點云模型上測地線的計算

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

2、行迭代 優(yōu)化,計 算得到點云模型上給定 2點間的一條樣條表示的精確測地線文中算法只需局部擬 合拋物曲面，無需對點云模型進行三角化或曲面重建，適合大規(guī)模點云數(shù)據(jù)模型上測地線的計算關(guā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月計算機輔助設計與圖形學學報JOURNAL OF COMPUTER Al DED DESIGN & COMPUTER GRAPHICSVol 18, No 3Mar , 2006第18卷第3期2006年3月計算機輔助設計與圖形學學報JOURNAL OF COMPUTER Al DED DESIGN & COMPUTER GRAPHICSVol 18, No 3Mar , 2006收稿日期：2005- 04 29;修回日期：2005- 07- 14基金項目：國家自然科學基金 (60473127) 194-2010 Chi na Academic Journal El

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、模型的距離是我們進一步 要研究的工作 在對目標函數(shù) F的迭代過程中，如 何自動確定一個最優(yōu)的能量權(quán)因子！ 一直以來是一個難以解決的問題,!值過大或過小都會影響活 動曲線的收斂速度和效果另外，根據(jù)點云模型的局部特性對點云模型進行非均勻單元剖分，在算法效率和精確性方面會有一定的改善，這也是需要進一步研究的工作之一參考文獻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方法的點采樣 曲面測地線計算及區(qū)域分解 J計算機學報，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