在醫學圖像分析中使用ICP算法進行點雲配準

作者：天啦嚕

來源：公眾號

論文標題：3D Registration of the Point Cloud Data Using ICP Algorithm in Medical Image Analysis

論文地址：在公眾號「3D視覺工坊」，後臺回復「點雲配準」，即可直接下載。

1.摘要

在本文中，我們結合了ICP算法（一種基於3D尺度不變特徵變換的方法），對3D自由形式閉合的曲面（人類頭骨的3D模型）進行配準。不同於點和表面的配準，我們提出的基於ICP算法的方法可以更好地捕獲數據的整體性質，例如骨骼厚度。文中提出的ICP算法主要分為3個步驟：3D特徵提取、歐氏距離的整體一致性比對以及ICP增強。整個系統的輸入是生物醫學數據（CT，MRI）。我們提出的方法首先進行圖像分割，然後對人類的頭骨進行三維重建。此外，點雲的3D 模型也被創建。最後，3D模型點雲之間的差異也是可視化的。我們對比了3中不同的算法，包括它們的精度以及魯棒性。和傳統醫學圖像領域中的重建和配準算法相比，文中提出的方法更快、精度更高。我們將算法應用於研究顱骨畸形，骷髏模型的實驗證明了這種方法的有效性和魯棒性。

2.背景知識

配準是解決計算機視覺以及計算機圖形學中各種問題的關鍵。總體目標是找到兩個對象之間或者同一對象的幾個實例之間的最佳對齊方式，以便把形狀數據引入到同一參考系統下。為了解決3D配準問題（位姿估計，對齊和運動估）計），我們決定使用一種著名的方法來配準2個點集（在2D或3D中），是由Bssl和Mskay提出的迭代最近鄰算法（ICP）。它一直以來都被用於計算機視覺的諸多實際應用中，比如3D掃描，3D映射以及3D定位中。因為其概念上的簡單性及其在實踐中表現的優越性 ，ICP是最受歡迎的配準算法之一，

3.本文的工作

3.1 3D特徵檢測

SIFT算法對於局部失真和特徵檢測中的錯誤很魯棒，被認為是當前可用的最有效的描述子。對於每個識別到的特徵，都會創建局部標記。SIFT 3D描述符的特點是以檢出的特徵點為中心選16x16x16的區域作為local patch，這個區域又可以均分為4x4x4個子區域，每個子區域中各個像素的梯度都可以分到8個bin裡面，這樣就得到了4x4x4x8=512維的特徵向量。3D SIFT結構的示例如圖1所示。

圖1.3D SIFT描述子的構造

3D SIFT描述子覆蓋了16x16x16的體素區域（該區域分為4×4×4個子區域）。

3.2 多模型配準

多模型配準的目標是對齊在多種視野中的同一個目標，該目標可能來源於不同類型的圖像採集系統。在我們的實驗中，採用3D SIFT描述子的迭代最近鄰算法ICP將被用來配準輸入的醫學圖像數據。

1）ICP配準

ICP是一種3D幾何模型對齊的方法，被廣泛用於配準3D掃描的輸出。本文的基本思路是通過重定義以下步驟改善這種方法和最小化誤差：

• 減少每個點雲上的點數（增加處理速度）；
• 確定對應點對（計算最近的點）
• 最小化點對之間的距離；
• 計算點集之間的均方差；

圖2.ICP算法配準模型的框圖結構

首先，ICP算法是基於尋找點集之間的最近點對；其次，創建一個優化的剛體變換來對齊兩組數據；最後，將變換應用於實際場景的數據點中。重複該過程，直到收斂。

ICP輸入：兩個n維的點集

• 模型設置：
• 數據設置：

ICP輸出：

• 將D映射到M的旋轉矩陣R和平移矩陣∆t
• 當成一個優化問題解決⇒ 最小化映射矩陣E中的誤差

在ICP處理過程中，搜索半徑會影響到計算時間，每次迭代都會使用特定的搜索半徑。最佳搜索半逕取決於點雲密度和初始位置估計。最近鄰比對是根據歐式距離定義的：

儘管ICP已被成功應用於許多配準問題，但是還有很多難題亟待解決。特別是ICP在以下假設滿足的情況下運行得很好：

• 兩個視圖必須彼此都很接近，如果不是的話，ICP算法可能會陷入局部最小值；
• 兩個視圖必須完全重疊，或者顯示的D數據能作為模型視圖M的子集。

ICP計算的速度和精度非常依賴於相關的處理過程，當ICP算法用來配準2個點雲文件，Delaunay三角剖分算法用來加速點的搜索（速度以及改善配準效率），四個點構成一個點集。

2） ICP 配準k-D樹

k-D樹（k維樹）是每個節點都為k維點的二叉樹，所有非葉子節點可以視作用一個超平面把空間分割成兩個半空間。在兩個半空間中搜索到的點是兩個節點子單元，生成的k-D樹能被用於有效地搜索P點的最近鄰域。

• 首先，通過從樹的根部以對數時間開始遞歸進行初始估計（選擇一個圍繞P所在的半空間的子樹直到到達葉子的節點）；
• 然後，遞歸過程中使用前一階段的估計值（包含一個比第一次估計低的距離為P的點）。

最近點的搜索算法是迭代的，點和分割平面是相對的，這決定了搜索路徑的機制。

4. 實驗結果

在這部分，我們將評估所提出算法的性能。文中提出的配準算法是基於迭代最近鄰（ICP）和3D SIFT算法，所有的測試方法均通過MATLAB程式語言驗證。ICP算法的輸入是原始點雲和目標點雲，具體如圖3所示。

圖3. 基於ICP的配準算法

首先，得到固定點雲和移動點雲。然後，做點雲配準。這些處理流程都可以在圖4中點雲配準的工作流中看到。第一步是清除兩幅點雲中的異常值和噪聲，下一步是做下採樣，這是關鍵一步。因為配準是否成功依賴於配準的點雲中點的個數。我們用pcddownsample函數執行下採樣，這個函數用了三種不同的下採樣方法。第一種，隨機標記，隨機劃分點雲而不需要替換點。使用這種方法的時候，只有輸入百分比和期望點的輸出個數需要設置。第二種方法稱為「gridAverage」，它使用標有「 gridStep」的類似於網格濾波的方式做下採樣，我們使用這種方法來減少點雲中的點。另外通過實驗，我們確定了網格濾波的理想步長是5。

圖4.模型配準的流程

完成以上這些過程後，就可以用ICP算法做剛體變換，通過循環的方式迭代執行以下幾步：

• 匹配移動和固定點雲
• 通過過濾異常值來消除不正確的匹配
• 恢復平移和旋轉（最小化誤差）。

實驗對比如下：

5.總結

本文提出了（ICP+SIFT）算法進行高精度的配準，只處理迭代轉換計算。在醫學圖像配準和重建領域，通過對比三種不同算法的精度和魯棒性，ICP，ICP+k-d 樹，以及文中所提的算法，本問題提出的算法是快速且精度更高的。

參考文獻:

[1] P. J. Besl and N.D. Mckay, 「A method for registration of 3-D shapes,」 IEEE Transactions on Pattern Analysis and Machine Intelligence[online]. 1992, 14(2), 239-256. DOI: 10.1109/34.121791. ISSN 0162-8828.

[2] Y. Chen and G. Medioni, 「Object modelling by registration of multiple range images,」 Image and vision computing, 1992, 10.3: 145-155.

[3] S. Rusinkiewicz and M. Levoy, 「Efficient variants of the ICP algorithm,」 In: 3-D Digital Imaging and Modeling, 2001. Proceedings.Third International Conference on. IEEE, 2001. p. 145-152.

[4] D. Chetverikov, D. Stepanov and P. Krsek, 「Robust Euclidean alignment of 3D point sets: the trimmed iterative closest point algorithm,」 Image and Vision Computing, 2005, 23.3: 299-309.

[5] P. Markelj, 「A review of 3D/2D registration methods for image-guided interventions,」 Medical image analysis, 2012, 16.3: 642-661.

[6] J. Santamaría, O. Cordón and S. Damas, 「A comparative study of stateof-the-art evolutionary image registration methods for 3D modeling,」Computer Vision and Image Understanding, 2011, 115.9: 1340-1354.

[7] J. Yang, H. Li and Y. Jia, 「Go-ICP: Solving 3d registration efficiently and globally optimally,」 In: Proceedings of the IEEE International Conference on Computer Vision. 2013. p. 1457-1464.

[8] Y. Sahillioglu and L. Kavan, 「Skuller: A volumetric shape registration algorithm for modeling skull deformities,」 Medical image analysis,2015, 23.1: 15-27.

[9] P. Scovanner, S. Ali, and M. Shah, 「A 3-dimensional sift descriptor and its application to action recognition,」 In Proceedings of the 15th International Conference on Multimedia (ACM 』07), pp. 357–360, New York, NY, USA, September 2007.

[10] B. Lee and D.D. Lee, 「Learning anisotropic ICP (LA-ICP) for robust and efficient 3D registration,」 In: Robotics and Automation (ICRA),2016 IEEE International Conference on. IEEE, 2016, p. 5040-5045.

[11] A. Nuchter, K. Lingemann and J. Hertzberg, 「Cached k-d tree search for ICP algorithms,」 Sixth International Conference

本文僅做學術分享，如有侵權，請聯繫刪文。

下載1

在「3D視覺工坊」公眾號後臺回覆：3D視覺，即可下載 3D視覺相關資料乾貨，涉及相機標定、三維重建、立體視覺、SLAM、深度學習、點雲後處理、多視圖幾何等方向。

下載2

在「3D視覺工坊」公眾號後臺回覆：3D視覺github資源匯總，即可下載包括結構光、標定源碼、缺陷檢測源碼、深度估計與深度補全源碼、點雲處理相關源碼、立體匹配源碼、單目、雙目3D檢測、基於點雲的3D檢測、6D姿態估計匯總等。

下載3

在「3D視覺工坊」公眾號後臺回覆：相機標定，即可下載獨家相機標定學習課件與視頻網址；後臺回覆：立體匹配，即可下載獨家立體匹配學習課件與視頻網址。