基于曲率圖的三維點(diǎn)云數(shù)據(jù)配準(zhǔn)

葛寶臻 ，彭 博 ，田慶國(guó)

(1. 天津大學(xué)精密儀器與光電子工程學(xué)院，天津 300072；2. 光電信息技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，天津 300072)

三維點(diǎn)云數(shù)據(jù)的配準(zhǔn)與融合是計(jì)算機(jī)視覺(jué)領(lǐng)域一個(gè)基本而重要的問(wèn)題．其研究成果在醫(yī)學(xué)、逆向工程、虛擬現(xiàn)實(shí)、計(jì)算機(jī)視覺(jué)等領(lǐng)域得到了廣泛的應(yīng)用[1]．根據(jù)不同視圖點(diǎn)云數(shù)據(jù)間是否存在畸變，現(xiàn)有的配準(zhǔn)算法大致可以分為基于剛性變換的配準(zhǔn)和非剛性配準(zhǔn)兩類．本文只討論基于剛性變換的配準(zhǔn)算法．給定具有重疊部分的三維點(diǎn)云數(shù)據(jù)，其任務(wù)是求取點(diǎn)云數(shù)據(jù)間的最佳剛性變換，使不同視圖的點(diǎn)云數(shù)據(jù)準(zhǔn)確地融合在一起[2-4]．

迭代最近點(diǎn)(iterative closest point，ICP)算法[5]是當(dāng)前最流行的剛性配準(zhǔn)算法，該算法以相對(duì)位置經(jīng)過(guò)粗略配準(zhǔn)的兩片點(diǎn)云數(shù)據(jù)為基礎(chǔ)，迭代求取兩片點(diǎn)云數(shù)據(jù)間的對(duì)應(yīng)點(diǎn)及相應(yīng)的剛性變換，直到對(duì)應(yīng)點(diǎn)之間的距離誤差評(píng)價(jià)函數(shù)最?。撍惴ǜ鶕?jù)兩點(diǎn)云數(shù)據(jù)點(diǎn)之間的距離來(lái)確定對(duì)應(yīng)點(diǎn)，所以需要待配準(zhǔn)的兩點(diǎn)云數(shù)據(jù)之間基本已經(jīng)配準(zhǔn)．實(shí)際上待配準(zhǔn)的點(diǎn)云數(shù)據(jù)間的相對(duì)位置往往未知，怎樣利用粗略配準(zhǔn)算法將點(diǎn)云數(shù)據(jù)間的相對(duì)位置變換到ICP 算法的收斂域成為問(wèn)題的關(guān)鍵．

目前普遍的解決方法是通過(guò)不依賴于三維旋轉(zhuǎn)和平移變換的點(diǎn)云特征信息來(lái)建立點(diǎn)云數(shù)據(jù)間的對(duì)應(yīng)關(guān)系．這些特征信息包括法向[6]、曲率[7]、體積分[8]等簡(jiǎn)單的一維特征描述函數(shù)，還包括旋轉(zhuǎn)圖像[9]、形狀內(nèi)容[10]等高維特征描述函數(shù)，有的甚至還包括顏色、強(qiáng)度值等輔助信息．但存在的問(wèn)題是，低維特征描述函數(shù)計(jì)算簡(jiǎn)單，但所包含的特征信息較少，且對(duì)噪聲敏感；高維特征函數(shù)能很好地反映特征信息，但計(jì)算復(fù)雜，時(shí)間、空間開(kāi)銷較大，且怎樣合理地進(jìn)行特征比較是一個(gè)難題．

筆者致力于通過(guò)新穎的特征信息和匹配算法快速、準(zhǔn)確地得到點(diǎn)云數(shù)據(jù)間的對(duì)應(yīng)關(guān)系．受Gatzke等[11]的啟發(fā)，在以點(diǎn)幾何表示的三維點(diǎn)云數(shù)據(jù)中引入曲率圖的概念，并將其作為三維點(diǎn)云數(shù)據(jù)的特征描述函數(shù)．該描述函數(shù)的優(yōu)點(diǎn)在于通過(guò)選擇不同的環(huán)數(shù)及各環(huán)半徑值可得到不同的曲率圖，很容易實(shí)現(xiàn)多比例空間的特征保持分析．有了曲率圖的概念以后，本文的主要算法思想是通過(guò)一維曲率圖粗選特征點(diǎn)和潛在對(duì)應(yīng)點(diǎn)，然后對(duì)特征點(diǎn)和潛在對(duì)應(yīng)點(diǎn)進(jìn)行高維曲率圖計(jì)算，并再次通過(guò)高維曲率圖進(jìn)一步精簡(jiǎn)潛在對(duì)應(yīng)點(diǎn)．這樣既保證了豐富的特征信息以獲得正確的對(duì)應(yīng)點(diǎn)，也大大減小了由于對(duì)整片點(diǎn)云進(jìn)行高維曲率圖計(jì)算所花費(fèi)的時(shí)間和空間開(kāi)銷．在特征點(diǎn)的匹配算法上，對(duì)已有的Mitra 貪婪算法[12]進(jìn)行了改進(jìn)，大大提高了其穩(wěn)定性．最后通過(guò)對(duì)真實(shí)三維點(diǎn)云數(shù)據(jù)進(jìn)行配準(zhǔn)，驗(yàn)證了該算法的有效性．

1 三維點(diǎn)云數(shù)據(jù)的曲率及曲率圖

在微分幾何中，對(duì)于三維歐幾里得空間中可微曲面上的任一點(diǎn)A，給定了兩個(gè)主曲率 1k 、2k[13]來(lái)衡量該點(diǎn)在不同方向上的彎曲程度．三維點(diǎn)云數(shù)據(jù)是對(duì)真實(shí)物體表面進(jìn)行掃描采樣獲得的離散數(shù)據(jù)，點(diǎn)云數(shù)據(jù)中的每個(gè)頂點(diǎn)同樣具有主曲率，不但如此，它還是點(diǎn)云數(shù)據(jù)的一項(xiàng)重要特性．經(jīng)常提及和主曲率相關(guān)的幾個(gè)曲率概念還有高斯曲率 K = k1k2、均值曲率

對(duì)于三維點(diǎn)云數(shù)據(jù)，估算其頂點(diǎn)主曲率 1k 、2k 的方法有很多，具代表性的有多項(xiàng)式擬合(polynomial fitting)法[15]、主成分分析(principal component analysis)法[16]以及移動(dòng)最小二乘(moving least-squares)法[17]等．其中多項(xiàng)式擬合法對(duì)噪聲敏感程度最小，穩(wěn)定性高，但計(jì)算相對(duì)復(fù)雜；主成分分析法求解過(guò)程相對(duì)簡(jiǎn)單，但只適用于采樣點(diǎn)稠密的大型點(diǎn)云；移動(dòng)最小二乘法具有較好的法向估算精度，但需要求解非線性方程．本文根據(jù)不同的點(diǎn)云數(shù)據(jù)采取與之相適合的主曲率估算方法．但僅利用單一點(diǎn)的均方根曲率C 并不能很好地反映該點(diǎn)周?chē)c(diǎn)的特征，并且對(duì)噪聲比較敏感．曲率圖利用該點(diǎn)及其周?chē)c(diǎn)的曲率信息分布，能夠準(zhǔn)確地反映特征信息的同時(shí)有效地抑制噪聲．下面分別介紹以點(diǎn)幾何表示的三維點(diǎn)云數(shù)據(jù)中一維曲率圖和高維曲率圖的構(gòu)造方式．這里以降采樣后的點(diǎn)云數(shù)據(jù)Stanford bunny00[18]為例，對(duì)其表面上的任意一頂點(diǎn)A，一維曲率圖的構(gòu)造比較簡(jiǎn)單，如圖1(a)所示，以目標(biāo)點(diǎn)A 為球心，對(duì)半徑為R 的球體內(nèi)所有頂點(diǎn)的均方根曲率 Ci進(jìn)行平均，得到的平均值即為該點(diǎn)的一維曲率圖．

圖1 曲率圖的概念示意Fig.1 Sketch of curvature map

式中n 為距離A 點(diǎn)的距離小于R 的頂點(diǎn)個(gè)數(shù)．對(duì)于高維曲率圖，如圖1(b)所示，同樣以目標(biāo)點(diǎn)A 為球心，利用半徑為 rj(0 ＜ j ≤m)的同心球?qū)⑧徲蚩臻g劃分為m 個(gè)球殼層，然后對(duì)每個(gè)球殼內(nèi)的所有頂點(diǎn)的均方根曲率進(jìn)行平均得到 f(rj)(0＜ j≤m)，高維曲率圖 kmap即為 f(rj)隨 rj的變化關(guān)系．用向量表示為

2 基于一維曲率圖提取特征點(diǎn)

有了曲率圖的概念以后，對(duì)三維點(diǎn)云數(shù)據(jù)的每個(gè)頂點(diǎn)進(jìn)行一維曲率圖運(yùn)算．根據(jù)所有頂點(diǎn)的一維曲率圖分布情況進(jìn)行特征點(diǎn)的提?。@里采用的思想是對(duì)所有頂點(diǎn)的一維曲率圖進(jìn)行統(tǒng)計(jì)分析，求取一維曲率圖的平均值μ和方差σ，選取一維曲率圖 f(R)處于μ± kσ之外的點(diǎn)作為特征點(diǎn)．一片點(diǎn)云的數(shù)據(jù)量很大，使得一維曲率圖往往近似服從正太分布，實(shí)驗(yàn)中發(fā)現(xiàn) k = 1時(shí)，獲得的特征點(diǎn)數(shù)量大致為點(diǎn)云總數(shù)的10%，通過(guò)調(diào)整系數(shù)k 可選擇不同程度的特征點(diǎn)．為了使選取的特征點(diǎn)能更好地反映點(diǎn)云的特征信息，抑制噪聲，對(duì)每個(gè)頂點(diǎn)選取不同的鄰域范圍做多比例空間的特征分析．這里通過(guò)改變一維曲率圖的構(gòu)造半徑R ，例如對(duì)于半徑為 Ri和 Ri+1時(shí)的鄰域范圍分別做特征分析得到特征點(diǎn)集 Pi和 Pi+1，選取 Pi和Pi+1的交集作為特征點(diǎn)．最后的特征點(diǎn)集為

式中n 為做多比例空間特征分析選取的半徑個(gè)數(shù)．對(duì)Stanford bunny00 進(jìn)行了基于一維曲率圖的特征點(diǎn)提取及特征保持分析．算法流程為：采用空間包圍盒法將三維點(diǎn)云數(shù)據(jù)結(jié)構(gòu)化；在此基礎(chǔ)上按歐式距離進(jìn)行點(diǎn)云的K 鄰域搜索；采用主成分分析法估算主曲率及均方根曲率(K＝20)；對(duì)每個(gè)半徑R 分別計(jì)算每個(gè)頂點(diǎn)的一維曲率圖 f(R)(R ＝0.000 5、0.001、0.002、0.005,mm)；對(duì)每個(gè)半徑R 分別進(jìn)行曲率圖統(tǒng)計(jì)分析，選取 f(R)處于μ± kσ之外的點(diǎn)作為該曲率圖半徑下的特征點(diǎn)集(k ＝1)；對(duì)上述4 個(gè)曲率圖半徑R進(jìn)行多比例空間的特征保持分析，得到特征保持點(diǎn)集；對(duì)特征保持點(diǎn)集按一定間隔距離值(0.005,mm)進(jìn)行采樣．

圖2所示為該算法的特征點(diǎn)提取過(guò)程．圖2(a)為R ＝0.000 5,mm 時(shí)提取到的特征點(diǎn)，可以看到，通過(guò)一維曲率圖提取到的特征點(diǎn)基本上都是處在兔子的耳朵、脖子、腿等輪廓特征比較明顯的部位，驗(yàn)證了一維曲率圖提取特征點(diǎn)的有效性；圖2(b)顯示了通過(guò)多比例空間的特征保持分析后得到的特征保持點(diǎn)集，對(duì)比圖2(a)可知，特征保持分析能有效去除一些非特征點(diǎn)或特征不夠顯著的點(diǎn)；圖 2(c)為按0.005,mm 間隔對(duì)特征保持點(diǎn)集采樣的結(jié)果，對(duì)特征保持點(diǎn)集按一定距離采樣是為了進(jìn)一步減少特征點(diǎn)數(shù)量，且讓特征點(diǎn)間有一定的距離，為后面的配準(zhǔn)算法打下了基礎(chǔ)．

圖2 特征點(diǎn)的提取過(guò)程Fig.2 Process of extracting feature points

3 高維曲率圖精簡(jiǎn)潛在對(duì)應(yīng)點(diǎn)

對(duì)于要配準(zhǔn)的兩片點(diǎn)云數(shù)據(jù)，通常稱之為源點(diǎn)集和目標(biāo)點(diǎn)集．理論上，只要在源點(diǎn)集和目標(biāo)點(diǎn)集之間至少找出3 對(duì)對(duì)應(yīng)點(diǎn)，就能夠計(jì)算出這兩片點(diǎn)云數(shù)據(jù)間的剛性變換關(guān)系，從而將這兩片點(diǎn)云數(shù)據(jù)配準(zhǔn)到一起．因此，準(zhǔn)確找到點(diǎn)集間的對(duì)應(yīng)點(diǎn)成為配準(zhǔn)的關(guān)鍵．

本文的思想是對(duì)源點(diǎn)集進(jìn)行基于一維曲率圖的特征點(diǎn)提取，然后對(duì)目標(biāo)點(diǎn)集進(jìn)行相應(yīng)的一維曲率圖運(yùn)算，一維曲率圖半徑為R ．對(duì)源點(diǎn)集中的每個(gè)特征點(diǎn)根據(jù)半徑為R 時(shí)一維曲率圖的相似性在目標(biāo)點(diǎn)集中求取相應(yīng)的對(duì)應(yīng)點(diǎn)，即選取 fp(R) ? fq(R )≤Δ的點(diǎn)作為該特征點(diǎn)的潛在對(duì)應(yīng)點(diǎn)，Δ為設(shè)定閾值，設(shè)定原則是保證理論上具有對(duì)應(yīng)點(diǎn)的特征點(diǎn)都能在潛在對(duì)應(yīng)點(diǎn)中找到正確的對(duì)應(yīng)點(diǎn)．通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，該值設(shè)為所有源點(diǎn)集中特征點(diǎn)的一維曲率圖平均值的10%時(shí)，基本能夠滿足上述要求．此時(shí)源點(diǎn)集中的一點(diǎn) pi往往對(duì)應(yīng)目標(biāo)點(diǎn)集中的多個(gè)點(diǎn) qi1，qi2，…，qik．為進(jìn)一步減少潛在對(duì)應(yīng)點(diǎn)的數(shù)量，有效去除錯(cuò)誤對(duì)應(yīng)點(diǎn)，對(duì)pi及其潛在對(duì)應(yīng)點(diǎn) qi1，qi2，…，qik進(jìn)行高維曲率圖運(yùn)算，高維曲率圖的半徑大小及環(huán)數(shù)根據(jù)點(diǎn)云采樣密度決定．然后將 pi的高維曲率圖分別與 qi1，qi2，…，qik的高維曲率圖做比較，比較的方式直接采用高維空間的歐式距離，即E2中選擇與 ie 沒(méi)有交集的2 點(diǎn)對(duì) je ，使得 ie 、je 組成的4 點(diǎn)對(duì)的距離均方差dRMS 最小．每構(gòu)成一個(gè)新的4 點(diǎn)對(duì)，便從E2中刪除包含這4 點(diǎn)對(duì)中任意一點(diǎn)的2 點(diǎn)對(duì)，遍歷直到E2為空．最后得到4 點(diǎn)對(duì)集E4，同樣按照距離均方差的值對(duì)E4升序排列．這里距離均方差dRMS 的定義為

(3) 粗略匹配對(duì)應(yīng)點(diǎn)．同理可以對(duì)E4進(jìn)行組合，得到8 點(diǎn)對(duì)集E8，乃至16 點(diǎn)對(duì)集E16等．在對(duì)應(yīng)點(diǎn)對(duì)不是太多的情況下一般得到E4、E8即可．選擇E4或E8中距離均方差最小的4 點(diǎn)對(duì)或8 點(diǎn)對(duì)作為粗略的對(duì)應(yīng)點(diǎn)．

(4) 精確匹配對(duì)應(yīng)點(diǎn)．在目標(biāo)點(diǎn)集中以粗略對(duì)應(yīng)點(diǎn)為球心，半徑為 CR 做球，處于球內(nèi)的點(diǎn)作為潛在對(duì)應(yīng)點(diǎn)，遍歷所有的對(duì)應(yīng)點(diǎn)組合，選擇使dRMS 最小的點(diǎn)對(duì)組合作為最終的對(duì)應(yīng)點(diǎn)．CR 的選取值越大得到的結(jié)果更精確，但耗時(shí)也越大．

對(duì)Stanford bunny00 和Stanford bunny45 進(jìn)行上述匹配算法，點(diǎn)對(duì)組合至E4，CR 取0.005,mm，得到4對(duì)對(duì)應(yīng)點(diǎn)，如圖3 所示．從圖中可以看到，兩視圖間的對(duì)應(yīng)點(diǎn)對(duì)基本上處于兔子的同一個(gè)位置，證實(shí)了該匹配算法的有效性．

式中：m 為高維曲率圖的維數(shù)；fp(rj)、fq(ri)分別為點(diǎn) pi、qi的高維曲率圖分量．對(duì) pi的所有潛在對(duì)應(yīng)點(diǎn)按d 的大小進(jìn)行升序排列，選取靠前的M 個(gè)對(duì)應(yīng)的 qi作為 pi最終的潛在對(duì)應(yīng)點(diǎn)．M 的選取原則是盡量保證正確的對(duì)應(yīng)點(diǎn)包括在其中，而且值還不能過(guò)大，不然會(huì)給后面的匹配算法帶來(lái)困難．經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證M 值選取為10，即一個(gè)點(diǎn)具有10 個(gè)對(duì)應(yīng)點(diǎn)時(shí)，點(diǎn)云重疊部分的特征點(diǎn)基本都能找到正確的對(duì)應(yīng)點(diǎn)，而且對(duì)后續(xù)的匹配算法不會(huì)增加太多負(fù)擔(dān)．

4 精確匹配對(duì)應(yīng)點(diǎn)

目前主要匹配算法思想是利用形狀的空間變換不變性來(lái)有效匹配對(duì)應(yīng)點(diǎn)．在眾多的算法中，Mitra的貪婪算法雖然不能保證找到最佳的對(duì)應(yīng)點(diǎn)，但它能高效快速地找到接近最佳匹配的對(duì)應(yīng)點(diǎn)對(duì)．為了較為精確地匹配對(duì)應(yīng)點(diǎn)，筆者提出下面的兩步匹配算法：首先，通過(guò)貪婪算法粗略匹配對(duì)應(yīng)點(diǎn)，然后同樣利用形狀空間變換不變性，遍歷這些點(diǎn)某個(gè)鄰域范圍內(nèi)的所有點(diǎn)對(duì)組合，找出最佳對(duì)應(yīng)點(diǎn)．具體算法有如下4 個(gè)步驟．

(1) 構(gòu)造點(diǎn)對(duì)．對(duì)于源特征點(diǎn)集中的每個(gè)點(diǎn)對(duì)組合 pi和 pj，從其潛在對(duì)應(yīng)點(diǎn)中選擇 qik和 qjl，使得

圖3 精確匹配對(duì)應(yīng)點(diǎn)Fig.3 Accurately matching of corresponding points

5 結(jié)果與討論

(2) 組合點(diǎn)對(duì)．順序從E2中取出2 點(diǎn)對(duì) ei，再?gòu)?/p>

針對(duì)Stanford bunny00 和Stanford bunny45，配準(zhǔn)前如圖4(a)所示，利用匹配算法得到對(duì)應(yīng)點(diǎn)以后，運(yùn)用奇異值分解(SVD)法[19]直接求取剛性變換，將Stanford bunny45 粗略配準(zhǔn)到Stanford bunny00 上，得到圖4(b)所示結(jié)果，可以看到兩片點(diǎn)云數(shù)據(jù)基本上被配準(zhǔn)在一起，但仍出現(xiàn)大片單一視圖的點(diǎn)云數(shù)據(jù)，需要進(jìn)一步的精確配準(zhǔn)．

為此，將粗配準(zhǔn)后的兩片點(diǎn)云數(shù)據(jù)作為輸入，利用經(jīng)典ICP 算法進(jìn)一步精配準(zhǔn)，ICP 算法的具體算法流程為：

(1) 通過(guò)隨機(jī)采樣的方式從源點(diǎn)集中選擇一部分點(diǎn)集P；

中日醫(yī)院呼吸中心煙草病學(xué)與戒煙中心主任肖丹教授指出，無(wú)論吸什么樣的煙，只要吸煙就是有害健康的。大量研究表明，煙草煙霧中有超過(guò)7000種化學(xué)物質(zhì)，包括69種致癌物，依然含有尼古丁、丙二醇、丙三醇、重金屬等有害物質(zhì)，會(huì)增加患慢性阻塞性肺疾病、肺癌、心血管疾病的風(fēng)險(xiǎn)，可以引起人體中多個(gè)器官的損害。

(2) 對(duì)點(diǎn)集P 中的任何一點(diǎn)，在目標(biāo)點(diǎn)集中找尋與之歐式距離最近的點(diǎn)作為對(duì)應(yīng)點(diǎn)，得到點(diǎn)集P的對(duì)應(yīng)點(diǎn)集Q；

(3) 從對(duì)應(yīng)點(diǎn)集P 和Q 中刪除距離值大于平均距離的點(diǎn)，剩下的點(diǎn)作為最后的對(duì)應(yīng)點(diǎn)；

(4) 通過(guò)對(duì)應(yīng)點(diǎn)求取坐標(biāo)變換矩陣(四元素法或SVD)；

(5) 構(gòu)造并計(jì)算誤差評(píng)價(jià)函數(shù)，其實(shí)就是第4 節(jié)提到的距離均方差；

(6) 判斷誤差評(píng)價(jià)函數(shù)的大小是否滿足精度要求，如果滿足則算法終止，返回結(jié)果；如不滿足，迭代進(jìn)入步驟(1)，此時(shí)的目標(biāo)點(diǎn)集為原始目標(biāo)點(diǎn)集經(jīng)過(guò)步驟(4)獲得的變換后的結(jié)果．

通過(guò)ICP 算法的精配準(zhǔn)得到最終的配準(zhǔn)結(jié)果如圖4(c)所示，可以看到兩片點(diǎn)云數(shù)據(jù)交錯(cuò)有致，達(dá)到了較好的配準(zhǔn)效果．

圖4 兔子點(diǎn)云的配準(zhǔn)過(guò)程Fig.4 Process of registration for Stanford bunny

為了驗(yàn)證本文配準(zhǔn)算法的通用性和適應(yīng)性，利用本實(shí)驗(yàn)室的掃描系統(tǒng)，對(duì)圖5 所示的人頭模型進(jìn)行掃描實(shí)驗(yàn)．但這次掃描條件比較特殊，只利用其中的一個(gè)攝像機(jī)，分別從不同角度進(jìn)行掃描，得到一系列具有重疊部分的三維點(diǎn)云視圖．

圖5 人頭模型Fig.5 Model of head

圖 6 所示為以任意兩角度拍攝的兩點(diǎn)云視圖．運(yùn)用本文的配準(zhǔn)算法模塊，對(duì)這兩點(diǎn)云視圖進(jìn)行配準(zhǔn)，得到如圖7 所示的結(jié)果．圖7(a)為配準(zhǔn)前的兩點(diǎn)云視圖在同一坐標(biāo)系中的表示，可以看出兩點(diǎn)云的視圖旋轉(zhuǎn)了一定的角度，且存在少量的平移；圖7(b)所示為本文算法粗配準(zhǔn)后的點(diǎn)云視圖，這時(shí)兩點(diǎn)云數(shù)據(jù)已經(jīng)相當(dāng)接近配準(zhǔn)狀態(tài)；圖7(c)為經(jīng)過(guò)ICP 精配準(zhǔn)的結(jié)果，可以看到視圖間的點(diǎn)云交錯(cuò)有致，達(dá)到了良好的配準(zhǔn)效果，驗(yàn)證了本文算法的有效性．

為說(shuō)明該算法的抗噪性能，對(duì)Stanford bunny00和Stanford bunny45 加入不同程度的白高斯噪聲．噪聲方差δ分別設(shè)為原始點(diǎn)云相鄰頂點(diǎn)間平均距離的0.1、0.3 和1.0 倍．為了和同類算法進(jìn)行比較，在1.0倍噪聲時(shí)，分別利用旋轉(zhuǎn)圖像算法[6]和本文的算法進(jìn)行粗配準(zhǔn)．圖8(a)、8(b)分別表示在0.1 倍和0.3 倍噪聲下本文算法的配準(zhǔn)結(jié)果，圖8(c)、8(d)分別表示在1.0 倍噪聲下利用本文算法和旋轉(zhuǎn)圖像算法的粗配準(zhǔn)結(jié)果．從圖中可以看到，本文的配準(zhǔn)算法具有很好的抗噪性，即使在1.0 倍噪聲下也能達(dá)到不錯(cuò)的配準(zhǔn)效果，遠(yuǎn)遠(yuǎn)優(yōu)越于旋轉(zhuǎn)圖像算法．

圖6 不同角度的兩點(diǎn)云視圖Fig.6 Two views of head with different angles

圖7 人頭點(diǎn)云的配準(zhǔn)過(guò)程Fig.7 Process of registration for the head

圖8 不同高斯噪聲下的點(diǎn)云配準(zhǔn)結(jié)果Fig.8 Results of registration for Stanford bunny with different noise levels

為了進(jìn)一步說(shuō)明該算法在尋找對(duì)應(yīng)點(diǎn)上的時(shí)間復(fù)雜度，以體積分(integral volume descriptors)算法[4]作對(duì)比．針對(duì)點(diǎn)云數(shù)據(jù)Bunny、Chicken、Dragon[15]，以Bunny000、Chicken_view1 和Dragonstandright_0作為源點(diǎn)集，Bunny045、Chicken_view2 和Dragonstandright_24 作為目標(biāo)點(diǎn)集．在相同硬件條件下，在源點(diǎn)集中選取相同的100 個(gè)特征點(diǎn)，然后分別利用曲率圖和體積分算子在對(duì)應(yīng)的目標(biāo)點(diǎn)集中尋找對(duì)應(yīng)點(diǎn)，每個(gè)特征點(diǎn)的對(duì)應(yīng)點(diǎn)數(shù)量設(shè)定為20，實(shí)驗(yàn)結(jié)果如表1所示．由于本文的匹配算法是通過(guò)兩步法的思想尋找對(duì)應(yīng)點(diǎn)，只對(duì)很少的部分點(diǎn)集進(jìn)行了高維曲率圖計(jì)算，所以耗費(fèi)的時(shí)間也大大少于體積分算子．

表1 曲率圖和體積分算子找到對(duì)應(yīng)點(diǎn)的耗時(shí)對(duì)比Tab.1 Comparison of the point matching time for some models

6 結(jié) 語(yǔ)

本文在點(diǎn)幾何表示的三維點(diǎn)云數(shù)據(jù)中，構(gòu)造了一維、高維曲率圖．并利用曲率圖分兩步確立了具有重疊部分的三維點(diǎn)云數(shù)據(jù)間的對(duì)應(yīng)點(diǎn)．先利用一維曲率圖粗略找對(duì)應(yīng)點(diǎn)，然后對(duì)找出的點(diǎn)進(jìn)行高維曲率圖運(yùn)算，剔除大量錯(cuò)誤對(duì)應(yīng)點(diǎn)．在此基礎(chǔ)上，通過(guò)改進(jìn)的貪婪算法實(shí)現(xiàn)了對(duì)應(yīng)點(diǎn)之間的精確匹配．找到匹配點(diǎn)對(duì)后，通過(guò)SVD 求解剛性變換，將兩片點(diǎn)云數(shù)據(jù)粗略配準(zhǔn)到ICP 算法的收斂域，最后借助經(jīng)典ICP算法實(shí)現(xiàn)了點(diǎn)云數(shù)據(jù)的精確配準(zhǔn)．通過(guò)各種配準(zhǔn)實(shí)驗(yàn)，體現(xiàn)了該算法不但具有很強(qiáng)的抗噪性，在計(jì)算時(shí)間上也大大優(yōu)于其他基于特征點(diǎn)的配準(zhǔn)算法．

致 謝：

特別感謝卡內(nèi)基美隆大學(xué)機(jī)器人研究所的Daniel Huber 教授提供了利用旋轉(zhuǎn)圖像進(jìn)行三維點(diǎn)云數(shù)據(jù)配準(zhǔn)的可執(zhí)行代碼．同時(shí)感謝斯坦福大學(xué)的計(jì)算機(jī)圖形學(xué)實(shí)驗(yàn)室提供的三維點(diǎn)云數(shù)據(jù)．

2006.

［9］Johnson A，Hebert M. Using spin images for efficient object recognition in cluttered 3D scenes [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1999，21(5)：674-686.

［10］Frome A，Huber D，Kolluri R，et al. Recognizing objects in range data using regional point descriptors[J].Computer Vision-ECCV，2004，3023：224-237.

［11］Gatzke T，Grimm C，Garland M，et al. Curvature maps for local shape comparison[C]//IEEE International Conference on Shape Modeling and Applications. 2005：244-253.

［12］Mitra N J，Gelfand N，Pottmann H，et al. Guibas registration of point cloud data from a geometric optimization perspective [C]//Proc Symposium on Geometry Processing. 2004：23-32.

［13］Gray A. Modern Differential Geometry of Curves and Surfaces[M]. Boca Raton，F(xiàn)L，USA：CRC Press，1993.

［14］Huy Tho Ho，Gibbins Danny. Multi-scale feature extraction for 3D models using local surface curvature [C]//Digital Image Computing：Techniques and Applications.2008：16-23.

［15］Cazals F，Pouget M. Estimating differential quantities using polynomial fitting of osculating jets[J]. Computer Aided Geometric Design，2005，22(2)：121-146.

［16］Lange C，Polthier K. Anisotropic smoothing of point sets[J]. Compute Aided Geometric Design ， 2005 ，22(7)：680-692.

［17］Alexa M，Behr J，Cohen-Or D，et al. Point set surfaces[C]// Proceedings of IEEE Visualization. 2001：21-28.

［18］Stanford University. Stanford 3D Scanning Repository[EB/OL]. http：//www-graphics. stanford. edu/data/3Dscanrep/.

［19］Arun K S，Huang T S，Blostein S D. Least-squares fitting of two 3-D point sets[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence ， 1987 ，9(5)：698-700.