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