【文章內(nèi)容簡(jiǎn)介】 換 定義：圖像中一條直線經(jīng)變換后仍為一條直線，且變換前后直線保持平行關(guān)系的變換稱為仿射變換。 滿足條件：平移、旋轉(zhuǎn)、縮放 數(shù)學(xué)表達(dá)：二維空間中，點(diǎn) (, )xy 變換到 ( 39。, 39。)xy 的公式為： 1 1 1 22 1 2 239。39。 xytaaxx taayy? ????? ? ???? ????? ? ?? ? ??? ??? (1 5) 其中 11 1221 22aaaa??????為實(shí)數(shù)矩陣， xytt??????指平移量 。 （ 3） 射影變換 定義：圖像中一條直線經(jīng)變換后仍為直線，但變換前后的兩條直線基本不保持平行關(guān)系的變換稱為射影變換。 滿足條件：平移、旋轉(zhuǎn)、縮放、投影 數(shù)學(xué) 表達(dá)：高維空間中， (, )xy 變換到 ( 39。, 39。)xy 的變換公式為： 11 12 1321 22 2339。39。 1xa a axxya a ayy??? ??? ? ? ????? ??? ? ? ??? ? ???????? (1 6) 其中 11 12 1321 22 23a a aa a a??????為實(shí)數(shù)矩陣 。 （ 4） 非線性變換 定義：圖像中一條直線經(jīng)變換后不再是直線的變換稱為非線性變換。 滿足條件：平移、旋轉(zhuǎn)、縮放、投影、扭曲 數(shù)學(xué)表達(dá)：二維空間中，點(diǎn) (, )xy 變換 到 ( 39。, 39。)xy 的變換公式為： ( 39。, 39。) ( , )x y F x y? (1 7) 其中 F 指任意函數(shù)形式。 北京化工大學(xué)畢業(yè)設(shè)計(jì)（論文） 9 第 節(jié) 圖像配準(zhǔn)方法簡(jiǎn)介 圖像配準(zhǔn)作為圖像處理的基礎(chǔ)，源自于許許多多不同領(lǐng)域的實(shí)際問(wèn)題，應(yīng)用領(lǐng)域的不同也導(dǎo)致了圖像配準(zhǔn)方法的多種多樣。 如何對(duì)各種各樣的配準(zhǔn)方法分類？ Brown根據(jù)變換模型的復(fù)雜程度 提出了三個(gè)范疇 ：搜索空間 類型 、特征空間 類型 、搜索策略類型 [1]，用 三個(gè)類型 來(lái)對(duì)圖像配準(zhǔn)方法分類 。 搜索空間類型是指圖像 配準(zhǔn) 過(guò)程中可以配準(zhǔn)圖像的變換操作的集合，其中 幾何變換為主要的因素 。 配準(zhǔn)圖像的變換操作一般可以分為：全局與局部。全局的變換一般可以通過(guò)一個(gè)參數(shù)矩陣來(lái)描述。局部的變換一般對(duì)變換參數(shù)有位置的依賴性，不同的位置計(jì)算不同的變換參數(shù)。 特征空間類型是指 圖像配準(zhǔn)過(guò)程中需要使用的具有重要實(shí)際意義的圖像特征 。一般用空間坐標(biāo)對(duì)同種屬性的圖像進(jìn)行特征表示。 搜索策略類型是指圖像配準(zhǔn)過(guò)程歐諾個(gè)需要運(yùn)用的一些優(yōu)化準(zhǔn)則和優(yōu)化算法的策略集合。常用到的策略如：松弛 匹配、最速下降法、牛頓法、共軛梯度法等等。 Paul 等人根據(jù)利用圖像中的信息配準(zhǔn)將圖像配準(zhǔn)方法分為兩大類：基于像素的圖像配準(zhǔn)和基于特征的圖像配準(zhǔn)。 [3] （ 1） 基于像素的圖像配準(zhǔn)方法 基于像素的圖像配準(zhǔn)方法是根據(jù)兩幅圖像的像素信息，直接計(jì)算圖像之間的相似程度。首先選定一個(gè)與圖像特點(diǎn)相應(yīng)的相似度量函數(shù)，采用適當(dāng)?shù)乃阉魉惴?，找到使其相似度最大的幾?變換參數(shù)，達(dá)到配準(zhǔn)的目的。這類方法的優(yōu)點(diǎn)在于實(shí)現(xiàn)簡(jiǎn)單，缺點(diǎn)在于應(yīng)用面比較狹窄。 （ 2） 基于特征的圖像配準(zhǔn)方法 基于特征的圖像配準(zhǔn)方法是指通過(guò)對(duì)兩幅圖像中的相同、重要 的特征進(jìn)行匹配來(lái)確定配準(zhǔn)映射變換。首先對(duì)兩幅圖像進(jìn)行特征提取，這些特征可能是：點(diǎn)、線、邊緣、閉合區(qū)域等等，再建立特征之間的對(duì)應(yīng)關(guān)系，最后估計(jì)出兩幅圖像間的幾何變換參數(shù)，完成圖像配準(zhǔn)。這類方法的優(yōu)點(diǎn)在于計(jì)算復(fù)雜度比較低，可適用的范圍廣。缺點(diǎn)在于相比較于基于像素的圖像配準(zhǔn)方法，配準(zhǔn)的精度較低。 這樣的分類包含了大部分的圖像配準(zhǔn)方法，下文中介紹的點(diǎn)云配準(zhǔn)方法思想上也屬于基于特征的圖像配準(zhǔn)方法。圖像配準(zhǔn)的方法還有很多，像文獻(xiàn) [4]介紹的圖像配準(zhǔn)北京化工大學(xué)畢業(yè)設(shè)計(jì)（論文） 10 的小波分解方法就是以后總基于變換域信息的圖像配準(zhǔn)方法。更加簡(jiǎn)單、便捷的圖 像配準(zhǔn)方法還等待著后人去探索。 第 節(jié) 點(diǎn)云配準(zhǔn) 點(diǎn)云簡(jiǎn)介 上文 主要對(duì)圖像配準(zhǔn)的定義和圖像配準(zhǔn)的方法作了簡(jiǎn)單的介紹。當(dāng)參考圖像和配準(zhǔn)圖像變成了三維空間中的點(diǎn)云數(shù)據(jù)的時(shí)候，配準(zhǔn)的方法和過(guò)程是否會(huì)變得不同呢？本節(jié)給出了答案。 文獻(xiàn) [5]中告訴我們，點(diǎn)云數(shù)據(jù)是指通過(guò)激光或者雷達(dá)掃描、立體攝像機(jī)等設(shè)備三維測(cè)量出的海量的表現(xiàn)出目標(biāo)表面特征的點(diǎn)的集合。點(diǎn)云的處理技術(shù)廣泛應(yīng)用于立體3D 影響、虛擬現(xiàn)實(shí)、 CAD/CAM、逆向工程等領(lǐng)域。舉個(gè)簡(jiǎn)單的例子，在汽車制造業(yè)中，零件的生產(chǎn)制造是根據(jù) 于 三維 CAD 模 型 ，但可能由于設(shè)計(jì)多次更改或者數(shù)據(jù)丟失等原因無(wú)法獲得零件的要生產(chǎn)的零件的幾何模型，這時(shí)可以通過(guò)逆向工程技術(shù)對(duì)油泥模型或者其他實(shí)物進(jìn)行測(cè)繪，獲取龐大的點(diǎn)云數(shù)據(jù)，從而提取重建的模型的幾何參數(shù)，或者從點(diǎn)云數(shù)據(jù)中獲取模型的曲面模型，最終完成零件的生產(chǎn)。 點(diǎn)云配準(zhǔn)的定義 點(diǎn)云配準(zhǔn)技術(shù)的產(chǎn)生來(lái)源于實(shí)際問(wèn)題，如上小節(jié)例子中提到的逆向工程技術(shù)，對(duì)實(shí)物模型進(jìn)行三維測(cè)繪產(chǎn)生，獲得龐大的點(diǎn)云數(shù)據(jù)，但得到的點(diǎn)云數(shù)據(jù)可能由于平移錯(cuò)位或旋轉(zhuǎn)錯(cuò)位等原因不完整，無(wú)法獲得想要得到的完整的數(shù)字模型。為了使點(diǎn)云完整，就必須對(duì)局部 點(diǎn)云數(shù)據(jù)進(jìn)行圖像配準(zhǔn)。 點(diǎn)云配準(zhǔn)問(wèn)題可以簡(jiǎn)單地概括成將各種重疊的三維點(diǎn)云數(shù)據(jù)視圖 一致對(duì)準(zhǔn)，形成一個(gè)完整的模型（在一個(gè)剛性的意義上）的問(wèn)題 [6]。點(diǎn)云配準(zhǔn)技術(shù)是通過(guò)一定的算法來(lái)計(jì)算兩塊點(diǎn)云之間的錯(cuò)位，從而達(dá)到配準(zhǔn)的效果。它的實(shí)質(zhì)在于確定一個(gè)合適的坐標(biāo)變換，將從不同視角獲得的點(diǎn)云數(shù)據(jù)合并到一個(gè)統(tǒng)一的坐標(biāo)系中，形成完整的點(diǎn)云。解決問(wèn)題的關(guān)鍵在于找到最優(yōu)的坐標(biāo)變換參數(shù)（旋轉(zhuǎn)矩陣 R 以及平移向量 T），使兩個(gè)點(diǎn)云數(shù)據(jù)經(jīng)坐標(biāo)變換后重疊區(qū)域?qū)?yīng)點(diǎn)之間的距離最小。 北京化工大學(xué)畢業(yè)設(shè)計(jì)（論文） 11 點(diǎn)云配準(zhǔn)方法簡(jiǎn)介 點(diǎn)云配準(zhǔn)的方法思想上都屬于基 于特征的圖像配準(zhǔn)方法。下圖簡(jiǎn)單介紹了一堆點(diǎn)云數(shù)據(jù)配準(zhǔn)時(shí)的主要步驟： 圖 1 1 點(diǎn)云配準(zhǔn)流程 至今比較流行的配準(zhǔn)方法為迭代最近點(diǎn)算法（ Iterative Closest Point，簡(jiǎn)稱 ICP 算法 ） [3][7]和采樣一致性初始配準(zhǔn)算法（簡(jiǎn)稱 SACIA 算法） [6],下面對(duì)兩種算法進(jìn)行簡(jiǎn)單介紹： （ 1） 迭代最近點(diǎn)算法（ ICP 算法） 對(duì)兩個(gè)含有重疊區(qū)域的點(diǎn)云數(shù)據(jù)使用 ICP 算法配準(zhǔn)的主要步驟為： ① 對(duì)兩個(gè)點(diǎn)云數(shù)據(jù)進(jìn)行采樣。 ② 根據(jù)一定準(zhǔn)則確定對(duì)應(yīng)點(diǎn)集 P 和 Q，其對(duì)應(yīng)點(diǎn)對(duì)的個(gè)數(shù)為 n 北京化工大學(xué)畢業(yè)設(shè)計(jì)（論文） 12 ③ 去除錯(cuò)誤的對(duì)應(yīng)點(diǎn)對(duì) ④ 通過(guò)最小二乘法迭代計(jì) 算得出最優(yōu)的坐標(biāo)變換（旋轉(zhuǎn)矩陣 R 和平移向量 T），使得誤差函數(shù)最小。 ICP 算法的優(yōu)點(diǎn)在于計(jì)算簡(jiǎn)單直觀，具有較好的精度。它的缺點(diǎn)在算法對(duì)于初始變換估計(jì)和迭代過(guò)程中確立的對(duì)應(yīng)關(guān)系具有較大程度的依賴性，影響算法的收斂和運(yùn)行速度。 （ 2） 采樣一致性初始配準(zhǔn)算法（ SACIA 算法） SACIA 算法在精度上屬于一種初始的變換矩陣的粗略估計(jì)的方法，相比于 ICP算法的擁有精確的變換矩陣估計(jì)，這類算法需要查看所有可能的對(duì)應(yīng)點(diǎn)對(duì)關(guān)系，計(jì)算復(fù)雜度較高。所以 SACIA 算法采用了采樣一致性方法，可以不必查看有限對(duì)應(yīng)關(guān)系的所有組合，并保 持相同的對(duì)應(yīng)點(diǎn)對(duì)的幾何關(guān)系。主要步驟為： ① 從點(diǎn)集 P 中選擇 s 個(gè)樣本點(diǎn)，確定其成對(duì)的距離大于用戶給定的最小值 mind 。 ② 對(duì)每個(gè)樣本點(diǎn)，在 Q 中找到特征描述與樣本點(diǎn)特征描述相似的點(diǎn)組成集合，從集合中隨機(jī)選擇點(diǎn)與樣本形成點(diǎn)對(duì)代表樣本點(diǎn)對(duì)的對(duì)應(yīng)關(guān)系。 ③ 計(jì)算通過(guò)樣本點(diǎn)定義的剛體變換及其對(duì)應(yīng)變換，通過(guò)計(jì)算誤差度量評(píng)價(jià)變換質(zhì)量。 ④ 重復(fù)上述 3 個(gè) 步 驟 得 出 誤 差 度 量 最 佳 的 變 換 ， 最 后 使 用 一 個(gè)LevenbergMarquardt 算法驚醒非線性局部?jī)?yōu)化。 SACIA 算大相比貪婪的初始配準(zhǔn)方法 大大降低了計(jì)算的復(fù)雜度。 北京化工大學(xué)畢業(yè)設(shè)計(jì)（論文） 13 第 2 章 點(diǎn)云特征的描述及提取 引言 3D 點(diǎn)云的特征描述及提取是三維點(diǎn)云配準(zhǔn)技術(shù)的基礎(chǔ)，同時(shí)也是最關(guān)鍵的一部分。點(diǎn)云配準(zhǔn)必須根據(jù)相似的點(diǎn)特征描述正確的估計(jì)其對(duì)應(yīng)關(guān)系，從而估算剛體變換公式完成配準(zhǔn)。同時(shí)點(diǎn)云特征描述及提取也在點(diǎn)云信息處理其他方面發(fā)揮著巨大的作用，如：點(diǎn)云的識(shí)別、點(diǎn)云的分割、點(diǎn)云的曲面重建等算法都以來(lái)提取的特征描述結(jié)果。 原始的表示形式中，一個(gè)點(diǎn)是通過(guò)笛卡爾坐標(biāo)系的坐標(biāo) X,Y,Z 來(lái)表示的，但是三維映射系統(tǒng)中，假設(shè)給定一個(gè)原點(diǎn)，這個(gè)原點(diǎn)是不隨時(shí)間而改變的。若分別在時(shí) 間 12,tt捕獲點(diǎn)云數(shù)據(jù)中點(diǎn) 1P 和 2P ，且點(diǎn) 1P 和 2P 擁有相同的坐標(biāo)，但他們?nèi)佑谀Ｐ偷牟煌砻?，所以?dāng)把他們和鄰近環(huán)境中的點(diǎn)放在一起時(shí)，他們表達(dá)的幾何信息故不相同。因此單一的實(shí)體三維點(diǎn)概念和笛卡爾坐標(biāo)在描述局部特征時(shí)被淘汰了，一個(gè)新的概念出現(xiàn)并取其位置：點(diǎn)特征表示 [5]。點(diǎn)特 征表示能夠表現(xiàn)出采樣表面的幾何性質(zhì)特征，幫助解決估算對(duì)應(yīng)關(guān)系的問(wèn)題。本章介紹了三個(gè)點(diǎn)特征表示以及分別提取其點(diǎn)特征的方法。 第 節(jié) 法線估計(jì) 點(diǎn)云數(shù)據(jù)中點(diǎn)所在處的相關(guān)法線是表現(xiàn)這一點(diǎn)所在表面的幾何性質(zhì)的重要屬性。對(duì)一個(gè)已知的幾何表面來(lái)說(shuō)，一個(gè)點(diǎn)的法線方向即為垂直于點(diǎn)表面的矢量，計(jì)算比較簡(jiǎn)單，而在點(diǎn)云數(shù)據(jù)中不存在真實(shí)的表面，它的表現(xiàn)僅僅是一組點(diǎn)。因此想要得到點(diǎn)的法線方向可以通過(guò)下面兩種方法： （ 1） 通過(guò)曲面重建技術(shù)得到樣本點(diǎn)對(duì)應(yīng)的曲面，計(jì)算垂直于曲面的矢量。 （ 2） 直接從點(diǎn)云數(shù)據(jù)中近似估算表面法線。 本節(jié)主要對(duì)第 二種方法進(jìn)行介紹。 估計(jì)發(fā)現(xiàn)的方法有很多，其中比較簡(jiǎn)單的一個(gè)表述如下：想要求得一個(gè)點(diǎn)的表面法線，即要求得點(diǎn)所在的近似估計(jì)表面的相切面的法線，所以我們可以把這一問(wèn)題轉(zhuǎn)換成一個(gè)最小二乘法的平面擬合的問(wèn)題，因此求解估計(jì)法線的過(guò)程可歸納為： 北京化工大學(xué)畢業(yè)設(shè)計(jì)（論文） 14 （ 1） 對(duì)樣本點(diǎn)進(jìn)行鄰近元素查詢，搜索確定樣本點(diǎn)的 k 鄰域。 （ 2） 估計(jì)樣本點(diǎn)鄰近元素的三維質(zhì)心坐標(biāo)。 （ 3） 利用公式計(jì)算樣本點(diǎn)以及鄰近點(diǎn)組成點(diǎn)集對(duì)應(yīng)的協(xié)方差矩陣，并計(jì)算協(xié)方差矩陣的特征值和特征向量： 11 ( ) ( ) , , { 0 , 1 , 2 }k Ti i j i iiC P P P P C v v jk ??? ? ? ? ? ? ?? (2 1) 其中 k 是點(diǎn) iP 鄰近點(diǎn)的數(shù)目， P 表示鄰近元素的三維質(zhì)心， i? 是協(xié)方差矩陣的第 i 個(gè)特征值， iv 是第 i 個(gè)特征向量。 （ 4） 分析協(xié)方差矩陣的特征值和特征向量，將最大的特征值對(duì)應(yīng)的特征向量作為樣本點(diǎn)的估計(jì)法線。 查看通過(guò)上述步驟得到的法線向量后，我們會(huì)發(fā)現(xiàn)法線向量的方向有正有負(fù)，無(wú)法保證同一表面的點(diǎn)的法線方向朝向同一個(gè)方向。為了解決這一問(wèn)題，我們還需要進(jìn)行一個(gè)同一法線方向的操作。 統(tǒng)一法線方向的操作原理十分簡(jiǎn)單。單一的點(diǎn)云數(shù)據(jù)是從一個(gè)單一的視角獲得的，因此我們可以定義一個(gè)視點(diǎn)，令其為 sP ，只要令所有法線 in 朝向視點(diǎn)方向即可做到方向一致， 故只需滿足方程： ( ) 0i s in P P? ? ? (2 2) 可得到方向一致的法線向量。 對(duì)一個(gè)點(diǎn)云數(shù)據(jù)分別對(duì)個(gè)點(diǎn)求得估計(jì)法線的結(jié)果將會(huì)在下一章展示。 第 節(jié) 點(diǎn)特征直方圖（ PFH） 對(duì)一個(gè)復(fù)雜的幾何表面來(lái)說(shuō)，單單給出一個(gè)樣本點(diǎn)的估計(jì)法線無(wú)法很準(zhǔn)確地描述這一樣本點(diǎn)周圍的局部幾何特征信息，因此 Radu等人提出了點(diǎn)特征直方圖（ Point Feature Histograms，簡(jiǎn)稱 PFH） [8]， 它可以作為一個(gè)點(diǎn)特征來(lái)描述這一點(diǎn) 周圍的局部幾何特征。 什么是點(diǎn)特征直方圖呢？我的理解 點(diǎn)特征直方圖是將一個(gè)樣本點(diǎn)鄰近的局部區(qū)域的幾何特征信息以統(tǒng)計(jì)分布的形式展示在一個(gè)直方圖中?？梢?、比較兩個(gè)點(diǎn)云數(shù)據(jù)中點(diǎn)的 PFH，然后通過(guò)相似度確定點(diǎn)云之間的點(diǎn)對(duì)的對(duì)應(yīng)關(guān)系。 北京化工大學(xué)畢業(yè)設(shè)計(jì)（論文） 15 PFH描述周圍幾何特征的方法是考慮樣本點(diǎn)與其 k鄰域之間的關(guān)系和他們之間的估計(jì)法線之間的關(guān)系。下圖中展示的是一個(gè)樣本點(diǎn)qP與其 k鄰域內(nèi)所有點(diǎn)（與qP的距離小于半徑 r的點(diǎn)）之間互相連接在一起的網(wǎng)絡(luò) 圖。 [6] 圖 2 1 點(diǎn) qP 的 PFH計(jì)算影響區(qū)域 具體的計(jì)算方法如下： （ 1） 對(duì)樣本點(diǎn) P ，查詢其 k 鄰域內(nèi)所有鄰近點(diǎn)。 （ 2） 對(duì)點(diǎn) P 鄰域 k 中每對(duì)點(diǎn) sp 和 tp （ st? ）和他們對(duì)應(yīng)的估計(jì)法線 sn , tn ,定義一個(gè)固定的局部 UVW 坐標(biāo)系： sun? ()tstsppu pp? ??? ? (2