一種新的空間曲線匹配算法

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

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

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

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

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

6、和曲率值,將曲率值作為局部形狀標(biāo)簽來(lái)匹配點(diǎn)對(duì),形成匹配點(diǎn)對(duì)列表。對(duì)列表中的每一點(diǎn)對(duì),通過(guò)對(duì)齊它們的弗朗內(nèi)特標(biāo)架得到所有的候選匹配矩陣。設(shè)置合適的匹配窗口,采用對(duì)應(yīng)點(diǎn)的匹配窗口內(nèi)的距離平方和作為匹配誤差,從候選匹配矩陣集合中選擇匹配誤差最小的矩陣作為最優(yōu)匹配。實(shí)驗(yàn)表明,通過(guò)合理設(shè)置匹配窗口的大小,算法可以適用全局曲線匹配和部分曲線匹配。1744一種新的空間曲線匹配算法王堅(jiān)周來(lái)水張麗艷1空間曲線的擬合1.1空間離散曲線的獲得和光順圖1所示是程序計(jì)算的空間曲線的弗朗內(nèi)特標(biāo)架,由圖1可以很直觀地看到弗朗內(nèi)特標(biāo)架的準(zhǔn)確性和連續(xù)性。由流動(dòng)式光學(xué)測(cè)量?jī)x(ATOS)進(jìn)行實(shí)際測(cè)量得到碎片模型,碎片模型以STL文

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

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

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

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

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

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

13、罐碎片輪廓曲線見(jiàn)圖3c,兩條待匹配陶瓷罐碎片輪廓曲線的初始位置見(jiàn)圖3d,運(yùn)用本文算法進(jìn)行匹配后的陶瓷罐碎片匹配結(jié)果見(jiàn)圖3e。將三維曲線的最優(yōu)匹配矩陣運(yùn)用到陶瓷罐碎片的拼合,結(jié)果如圖4所示。如果將全局坐標(biāo)系到局部坐標(biāo)系的坐標(biāo)變換矩陣設(shè)為M1,將局部坐標(biāo)系到全局坐標(biāo)系的坐標(biāo)變換矩陣設(shè)為M2,那么將C2對(duì)齊到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以及各全局坐標(biāo)向量和局部坐標(biāo)向量均為已知量。2.3匹配誤差與最優(yōu)匹配(a)陶瓷罐碎片(b)初始輪廓曲線本文采用對(duì)應(yīng)點(diǎn)距離平方和作為匹配誤差的度量,計(jì)算公式為D=w2w+1k=-w(M(P1i k)-P2)2j ki=0,1,m;j=0,1,n1式中,P1P2C2上的點(diǎn);M為匹配矩i、j分別為空間曲線C、(c)光順擬合采樣(d)初始位置(e)匹配結(jié)果陣;i、j、m、n

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

16、C1、C的采樣點(diǎn)數(shù)m、n相1746一種新的空間曲線匹配算法王堅(jiān)周來(lái)水張麗艷不可避免地存在缺失、磨損等情況,所以匹配誤差不可能為0。通過(guò)實(shí)驗(yàn)數(shù)據(jù)可知,實(shí)例1中全局匹配情況下的匹配誤差為1018,實(shí)例2中局部匹配情況下的匹配誤差為61307,達(dá)圖4將最優(yōu)匹配運(yùn)用到陶瓷罐碎片得到的拼合結(jié)果應(yīng)于部分曲線的匹配。實(shí)驗(yàn)結(jié)果表明,匹配的效率高、誤差小、適應(yīng)性好。參考文獻(xiàn):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施法中.計(jì)算機(jī)輔助幾何設(shè)計(jì)與非均勻有理B樣Hawaii:IEEEComputerSociety,(a)初始輪