1、中國機械工程第17卷第16期2006年8月下半月一種新的空間曲線匹配算法王堅周來水張麗艷南京航空航天大學,南京,210016摘要:提出一種新的空間曲線匹配算法。該算法對離散的曲線進行光順、擬合和采樣,使用空間曲線微分幾何性質計算各采樣點的曲率和弗朗內特標架。通過曲率計算匹配點對列表,通過對齊匹配點對的弗朗內特標架進行曲線匹配,得到一個匹配矩陣集。從匹配矩陣集中選出一個最優匹配的匹配矩陣,使得空間曲線的對應點匹配窗口內的距離平方和最小。實驗結果證明,算法效率高、魯棒性好。關鍵詞:空間曲線匹配;弗朗內特標架對齊;參數三次樣條;匹配點對列表;匹配窗口;匹配矩陣中圖分類號:TP391文章編號:1004

2、132X(2006)16174404ANovelAlgorithmonSpaceWangJianZhouLaishuiLiyanNanjingUniversityofAbstract:AnovelspaceAftersmoothing,fittingandsamplingtheFrenetframeandcurvatureforeachsam2plingtopairthesamplingpoints.ThenbyregistratingtheFrenetframesfor,asetofmatchmatrixwasobtained.Weselectedtheoptimalmatchmatrixf

3、romit,whichminimizedthecorrespondingpointdistancesquaresumwithinthematchwindow.Experi2mentalresultsdemonstratethealgorithmisefficientandrobust.Keywords:spacecurvematching;Frenetframeregistration;parametriccubicspline;matchpointpairlist;matchwindow;matchmatrix0引言空間曲線匹配的研究具有理論價值和實際意義,是計算機視覺、文物復原、納米技術、

4、模式識別、形狀檢索、現代醫藥等研究領域中的一個重要問題,國內外學術界對此進行了廣泛的研究。綜合起來,基本可以將算法分為以下三類:通過迭代優化曲線的相對位置,得到最佳匹配。如Besl等1提出了可以進行空間曲線匹配的最近點迭代(ICP)算法,該方法具有單調收斂的優點,但對初值的選取十分敏感,并易陷入局部極值。通過檢測特征點,將曲線分割成子段來完成整條曲線的匹配。Zhu等2將曲率和撓率相結合作為全曲率,使用全曲率來檢測輪廓的特征點,為進一步的匹配做好準備。通過計算空間曲線的局部形狀標簽,得到相似矩陣,檢測出最優匹配段,完成匹配。Ucoluk等3運用差分法計算曲率和撓率作收稿日期:20050805基金

5、項目:國家自然科學基金資助項目(60273097);高等學校優秀青年教師教學科研獎勵基金資助項目;南京航空航天大學創新科研基金資助項目(S0272054)為局部形狀標簽,構成相似矩陣,檢測出最長匹配序列,作為最優匹配,但檢測算法復雜度高,算法僅使用了理想曲線。Leitao等4使用多尺度曲率,結合動態規劃算法精確搜索匹配序列,找出平面曲線的最優匹配,但算法參數配置復雜,不易實現,難以推廣到空間曲線。Kong等5將動態規劃和能量方法相結合來計算匹配誤差,完成曲線匹配。Thomas等6也使用動態規劃的方法對相似矩陣進行分析,完成了對二維手寫字體的匹配。本文針對封閉輪廓曲線,計算各采樣點的弗朗內特標架

6、和曲率值,將曲率值作為局部形狀標簽來匹配點對,形成匹配點對列表。對列表中的每一點對,通過對齊它們的弗朗內特標架得到所有的候選匹配矩陣。設置合適的匹配窗口,采用對應點的匹配窗口內的距離平方和作為匹配誤差,從候選匹配矩陣集合中選擇匹配誤差最小的矩陣作為最優匹配。實驗表明,通過合理設置匹配窗口的大小,算法可以適用全局曲線匹配和部分曲線匹配。1744一種新的空間曲線匹配算法王堅周來水張麗艷1空間曲線的擬合1.1空間離散曲線的獲得和光順圖1所示是程序計算的空間曲線的弗朗內特標架,由圖1可以很直觀地看到弗朗內特標架的準確性和連續性。由流動式光學測量儀(ATOS)進行實際測量得到碎片模型,碎片模型以STL文

7、件格式7存儲。將STL文件讀入內存,去除冗余頂點,建立拓撲結構8,通過基于種子三角片的區域增長算法對模型進行分割,得到彼此相鄰的塊,提取塊的邊界作為待匹配的空間輪廓數據。由于碎片的不規則,得到的曲線比較粗糙,本文先用高斯光順算法進行光順處理。高斯算法9如下:w圖1空間曲線弗朗內特標架計算結果的局部放大圖Pi=j=-wPi jGjGj=w2)-i2/(22空間曲線的匹配2.1匹配點對列表112已知空間曲線C1=P1=0,P1,Pm,C222122P0,P1,Pn,曲i、jiPj的曲率。i=0,1,nj=-we2)-j2/(2式中,Pi為曲線C上的第i點; 表示模n和,即i j表示(i+j)mod

8、n;Gj為高斯核;w為濾波帶寬;為濾波的標準差。原則,距離Pi大于3參考3順起不到良好的作用,本文將/3。,1.2,:12|i-j|<(1),為閾值。本文采用下式確定的值:=12210,1研究空間離散輪廓線的微分特性有兩種方法:一種采用差分,這種方法易于計算,具有近似性,但一般需要相當密度且分布均勻的點列;另一種采用函數擬合。參數三次樣條曲線10是可以表示有凹凸形狀的平面曲線以及帶有拐點的空間曲線的最低次數的參數曲線,本文選用周期參數三次樣條曲線作為插值擬合曲線,使之順序通過給定的有序輪廓數據點Pi。采樣的原則是在盡可能不損失原始形狀信息的情況下,減少采樣數據點的數量,本文采用等間隔采樣

9、,因參數曲線是累計弦長參數化的,所以也是等參數間隔的采樣。這種采樣的好處是可以在后續的匹配中容易將不同曲線上的數據點等間隔對應起來。1.3空間曲線的弗朗內特標架計算和曲率計算計算空間曲線的切矢時需要一階導矢,計算曲率時需要二階導矢,計算撓率時需要三階導矢,而計算弗朗內特標架時只需要二階導矢。弧長參數化下有以下計算公式:t=Pb=¨11221式中,C2上的曲率的最max、min、max、min分別為曲線C、大值和最小值。若取值1,則匹配列表包括所有的點對,若取0,則列表為空。本文中取014。如果式(1)成立,P1i和Pj可能是真實匹配的,對齊這兩點的弗朗內特標架就對齊了整體曲線,但也可

10、能不是真實匹配的,只是局部形狀相似。它們得到的匹配誤差必然很大,容易被排除在最優匹配之外。所有滿足式(1)匹配點對的點對12序號(i,j)和相應的平均曲率k=(i+j)/2被加入到匹配點對候選列表pair_list中。2.2弗朗內特標架的對齊設全局坐標系為O;e1,e2,e3,e1、e2、e3分別是X、Y、Z軸上的單位矢量。空間曲線C1的局部1112坐標系為P1i;tj,nj,bj,空間曲線C的局部坐標系為P2j;t2j;n2j,b2j,坐標和坐標軸矢量均在全局坐標系中定義,且坐標軸矢量已單位化。弗朗內特標架的對齊就是空間局部坐標系的對齊,如圖2所示。旋轉矩陣設為R,平移矩陣設為T,則坐標系的

11、對齊矩陣為M=TR。這種方法比較麻煩,涉及歐拉角的使用。本文采用另一種對齊的思路:首先將全局坐標系下的曲線C1變化到局部坐標系下,然后再從局部坐標系變化到全局坐標系下,完成C1和C2的對齊。1745¨¨|P×P|n=b×t=¨|(P×P)×P|=|PרP|式中,t為切矢;n為曲率矢;b為副法矢;P為矢量點;為曲率。中國機械工程第17卷第16期2006年8月下半月等,匹配窗口的大小可以等于采樣點數。在部分曲線匹配的情況下,設置滿足局部形狀需要的大小可變的匹配窗口,在匹配窗口外的采樣點不用來計算匹配誤差。本

12、文中w的設置由對應點的平均曲率k決定。k從pair_list中得到。將平均曲率k映(a)未對齊的空間曲線C1、C2射為w的函數為w=(1-kr)min(m,n)kr0,1式中,kr為k的歸一化曲率;為調整權值,本文取值110。容易看出,對于曲率值高的點,局部形狀比較突出,使用較小的匹配窗口,而對于曲率值小的點,局部形狀比較平坦,使用較大的匹配窗口。(b)對齊后的空間曲線C1、C2圖2空間曲線對齊示意圖3應用實例與分析實例1是陶瓷罐碎片,。實例,整,。實例數據,用以驗證本。實例1對陶瓷罐碎片進行分塊的結果見圖3a,從陶瓷罐碎片分塊結果中提取出離散點組成的初始輪廓曲線見圖3b,光順擬合采樣后的陶瓷

13、罐碎片輪廓曲線見圖3c,兩條待匹配陶瓷罐碎片輪廓曲線的初始位置見圖3d,運用本文算法進行匹配后的陶瓷罐碎片匹配結果見圖3e。將三維曲線的最優匹配矩陣運用到陶瓷罐碎片的拼合,結果如圖4所示。如果將全局坐標系到局部坐標系的坐標變換矩陣設為M1,將局部坐標系到全局坐標系的坐標變換矩陣設為M2,那么將C2對齊到C1的變換矩陣M=M2M1。M1、M2分別為a11M1=a21a31a12a22a13a23a12a311b31b3213b23b33b2b301000其中,amn(m=1,2,3,n=1,2,3)和am(m=1,2,3)由下式求得:t1iP1a2a3n1iO=a1ib1ie1a11=a21a3

14、1a12a22a32a13a23a33t1in1ib1ie2e3bmn和bm由下式求得:e1OP2b2b3e2j=b1e3t2jb11=b21b31b12b22b32b13b23b33e1e2e3n2jb2j2其中,P1iO和OPj以及各全局坐標向量和局部坐標向量均為已知量。2.3匹配誤差與最優匹配(a)陶瓷罐碎片(b)初始輪廓曲線本文采用對應點距離平方和作為匹配誤差的度量,計算公式為D=w2w+1k=-w(M(P1i k)-P2)2j ki=0,1,m;j=0,1,n1式中,P1P2C2上的點;M為匹配矩i、j分別為空間曲線C、(c)光順擬合采樣(d)初始位置(e)匹配結果陣;i、j、m、n

15、分別為空間曲線C1、C2上的點序號和采樣點長度;k為對應點的編號;為兩點之間的距離; 為模和,i k為(i+k)modm,j k為(j+k)modn;w為匹配窗口大小控制參數;2w+1為窗口內采樣點的數量。圖3陶瓷罐碎片的全局輪廓曲線匹配實例2部分匹配的磚塊碎片的初始輪廓曲線見圖5a,光順擬合采樣后的磚塊碎片輪廓曲線見圖5b,待匹配磚塊碎片輪廓曲線的初始位置見圖5c,運用本文算法后得到的磚塊碎片匹配結果見圖5d。下面分析匹配誤差。理想狀態下的匹配誤差應為0,但由于采用的是實際測量例子,輪廓曲線設置不同的窗口參數w,可以將算法應用到全局曲線匹配或者部分曲線匹配。在全局曲線匹2配的情況下,空間曲線

16、C1、C的采樣點數m、n相1746一種新的空間曲線匹配算法王堅周來水張麗艷不可避免地存在缺失、磨損等情況,所以匹配誤差不可能為0。通過實驗數據可知,實例1中全局匹配情況下的匹配誤差為1018,實例2中局部匹配情況下的匹配誤差為61307,達圖4將最優匹配運用到陶瓷罐碎片得到的拼合結果應于部分曲線的匹配。實驗結果表明,匹配的效率高、誤差小、適應性好。參考文獻:1BeslPJ,McKayND.AMethodforRegistrationof3-DShapesJ.IEEETransactionsonPatternAnalysisandMachineIntelligence,1992,14(2):23

17、9256.2ZhuYanjuan,ZhouLaishui,WangJian.ContourExtractionandFeaturePointDetectionfor3DFrag2mentReassemblyJ.TransactionsofNanjingUni2versityofAeronautics&Astronautics,2005,22(1):2329.3UcolukG,TorosluIH.Reconstructionof3-DSurfaceObjectfromItsPiecesProc.ofthe9thGeometry.H,J.MethodfortheTwo-Dimensiona

18、lFragmentedOb2jectsJ.IEEETransactionsandPatternAnalysisandMachineIntelligence,2002,24(9):12391251.5KongWeixin,KimiaBB.OnSolving2Dand3DPuzzlesUsingCurveMatchingC/Proc.oftheIEEEConferenceonComputerVisionandPatternRecognition.2001:583590.6ThomasBS,PhilipNK,KimiaBB.OnAligningCurvesJ.IEEETransactionsonPa

19、tternAnalysisandMachineIntelligence,2003,25(1):116125.7Szilvsi-NagyM,MatyasiG.AnalysisofSTLFilesJ.MathematicalandComputerModelling,2003,38(7/9),945960.8ShinHayong,ParkJC,ChoiBK,etal.EfficientTopologyConstructionfromTriangleSoupC/Proc.oftheGeometricModelingandProcessing.Beijing:IEEEComputerSociety,2004:359364.9PapaioannouG,KarabassiAE.OntheAutomaticAssemblageofArbitraryBrokenSolidArtifactsJ.ImageandVisionComputing,2003,21(5):401412.10施法中.計算機輔助幾何設計與非均勻有理B樣Hawaii:IEEEComputerSociety,(a)初始輪