一種基於拓撲特徵的點雲配準算法的製作方法

2023-04-25 04:45:16 1

專利名稱：一種基於拓撲特徵的點雲配準算法的製作方法
技術領域：
本發明涉及計算機視覺技術，特別涉及基於拓撲特徵實現三維點雲配準的算法。
背景技術：
三維模型在虛擬仿真訓練、文物保護、醫學等領域都具有重要的意義。隨著現代三維掃描技術的發展，對點雲模型的處理已成為近年來研究的熱點。點雲處理中一個重要的方面就是對同一場景的得到的兩個點雲數據配準。對點雲的配準按照配準過程可分為:粗配準、精確配準。粗配準是通過提取不同視角數據集的相對應的控制點，來計算配準變換參數。但由於無法獲得精確的對應控制點，所以粗配準精度無法滿足要求。精確配準的主要思想是迭代思想，通過迭代來逐漸逼近最佳結果。但精確配準需要一個迭代的起始位置，來增大收斂到最佳結果的概率，這個起始位置可由粗配準提供。綜述所述，配準過程為先由粗配準得到一個迭代的起始位置，在通過精確配準得到最終配準結果。粗配準:目前常用的選取原始點雲的方法有:均勻採樣、隨機採樣和基於局部幾何特徵的採樣。其中均勻採樣和隨機採樣並沒有考慮其中均勻採樣與隨機採樣簡便易行，但並沒有考慮選取出來的特徵點所包含的點的信息，這樣可能會丟失點雲的關鍵特徵。基於局部幾何特徵的採樣通過提取數據集的局部特徵，作為數據配準的控制點。然而，這種基於物體局部幾何特徵的配準方法，對於不同視角獲取的三維點雲配準的魯棒性不高。精確配準:目前最常用的精確配準方法是ICP算法。它是由Besl和McKay提出來的。其本思想是先在一個點集中搜索另一個點集中點的點的最近點來得到對應點集，並計算使對應點之間的歐式距離差平方和最小的剛體變換。然後將得到的變換作用於點集，再不斷重複以上過程直到滿足收斂條件或達到最大迭代次數。ICP算法可以獲得比較精確的配準結果，使用非常廣泛，但也存在許多不足:算法假設其中一個點集是另一個點集的子集，這一要求在很多時候難以滿足；算法在搜索對應點的過程中，計算代價非常的大；在基本的ICP算法中，在尋找最近點的時候，算法搜索的是歐式距離的最近點，這種假設是比較武斷的，它會產生錯誤對應點。近年來許多研究者針對以上不足提出了各種改進方法。對ICP算法的改進有以下三個方向:配準元素的選擇、配準策略的確定和誤差函數的求解，其中大部分改進方法都是對前兩個方向的改進。配準元素的選擇:在標準ICP算法中，點集中的所有點都參與對應的點的計算,這使得計算量非常的龐大。所以研究者提出了許多配準元素選擇的方法，運用一些具有明顯特徵的點集來進行配準，從而減少配準點集的數量減少計算量。最初使用的式隨機採樣方法，後來發展到基於幾何特徵的採樣方法。配準策略的確定:在標準ICP算法中，確立對應點時採用的是點到點的歐氏距離。在後續的研究中，研究者提出了點到面、點到投影等方法來確立對應點。有些研究者不僅考慮了距離，在確立特徵點時加入了其他對幾何特徵的考慮，如:法向量、曲率等。在確立對應點後，研究者還提出了去除錯誤對應點的方法。這些方法主要是基於點雲自身的幾何特性與剛性運動一致性的。

發明內容
為了克服標準配準算法計算量大、錯誤對應點多的不足，本發明提出了一種基於拓撲特徵的點雲配準算法。該算法不僅減少了計算量，還保證了配準效果。本算法解決其技術問題所採用的技術方案是:粗配準階段:採用了點雲的拓撲特徵(邊界特徵和突出特徵點)選取控制點，從而減小了計算量。精確配準階段:配準元素選擇邊界特徵點和突出特徵點，從而減少提取特徵點的數量，減少了計算量。精確配準階段:確定對應點集時，採用的策略是選取鄰域重心的最近點為對應點，由於加入了對鄰域特徵的考慮，提高了算法對噪聲的魯棒性。本算法的有益效果是，利拓撲特徵在點雲配準過程中減少了配準元素、去除了錯誤對應點。從而在減少了點雲配準的計算量的同時、提高了配準算法的魯棒性。


圖為本發明算法流程圖。
具體實施例方式1.粗配準:本算法採用基於拓撲特徵的點雲粗配準算法，分別計算平移向量和旋轉矩陣。1.1平移向量計算:分別計算各點雲的重心，將各點雲的重心重合得到粗配準的平移向量。1.2旋轉矩陣計算:首先採用弦值法得到各點雲的三個拓撲點，具體做法是:遍歷點雲的所有點得到兩個距離最遠的點P1、，Pn遍歷其餘點，得到離P1、Pn連線最遠的點pm。然後通過三點間的距離確定各點雲三個拓撲點的對應關係，得到三對特徵點對。最後帶入公式R.Xi = YiQ=I，2,3),求解R旋轉向量。2.精確配準精確配準算法採用的是ICP算法，算法步驟如下:2.1配準元素選擇:同粗匹配的拓撲點提取一樣，採用弦值法:遍歷點雲的所有點得到兩個距離最遠的點PpPn，連接PpPn，以此為基線遍歷其餘點，得到離此基線線最遠的點Pm。記錄Pm再連接PpPm及Pn、Pm，再以此為基線尋找弦值最大的點並記錄，不斷重複以上過程直到最大弦值滿足閾值條件。所有記錄下來的即為點雲的拓撲特徵點，作為配準元素。2.2確定對應點集:確定對應點集的方法是:對於數據集中的配準元素點，在參考集中尋找鄰域重心最近點與其對應。具體做法是:首先遍歷數據集合參考集，得到數據集中各配準元素點和參考集中各點的鄰域和鄰域重心。然後對數據集中各配準元素點，在參考集中搜索其鄰域重心最近對應點，得到對應點集。2.3平移向量和旋轉矩陣計算:本算法計算旋轉矩陣才用的是四元素法，過程如下:旋轉矩陣R可以用一個單位四元數q來表示:R = R(q)
權利要求
1.一種基於拓撲特徵的點雲配準算法，其特徵在於，將點雲配準過程分為粗配準和精確配準兩個階段，在初始配準階段，利用基於拓撲特徵的粗配準算法，以提高整體算法的效率；在精確配準階段，利用的基於拓撲特徵的點雲ICP精確配準算法，以提高點雲配準的準確度。
2.根據權利要求1所述的方法，其特徵在於，利用基於拓撲特徵的點雲粗配準算法，首先計算點雲的重心，將各點雲的重心重合得到粗配準的平移向量，其次提取了各點雲的兩對最遠距離拓撲特徵點(邊界特徵和突出特徵點)，對得到的拓撲特徵點對匹配，最後通過特徵點對計算得到粗配準的旋轉矩陣。
3.根據權利要求1所述的方法，其特徵在於，利用基於拓撲特徵的點雲ICP精確配準算法進行點雲的最終配準，首先提取了拓撲特徵點；其次根據鄰域重心計算數據集中特徵點與參考集的最近點確定對應點集；最後，根據對應點集採用四元素法計算出變換參數，並根據變換參數變換數據集。算法重複以上過程，直到滿足結束條件。
4.根據權力要求2所述的方法，其特徵在於，計算初始旋轉矩陣時，提取了各點雲的兩對最遠距離拓撲特徵點，通過四個特徵點計算為後面的精確配準提供了一個良好的初始旋轉矩陣。
5.根據權力要求3所述的方法，其特徵在於，精確配準階段，配準元素選擇拓撲特徵點，確定對應點集時採用的策略是選取鄰域重心的最近點為對應點，加入了對鄰域特徵的考慮。
全文摘要
本發明是一種基於拓撲特徵的點雲配準算法。在算法的初始點雲配準階段，提取了點雲的拓撲特徵點(邊界特徵點和突出特徵點)用於計算初始的旋轉矩陣和平移向量。算法的精確配準階段採用的是ICP算法的基本思想，對配準元素的選擇和確定對應點集方法進行了改進。配準元素選擇的是拓撲特徵點，確定對應點集時採用的策略是選取鄰域重心的最近點為對應點。本算法引入了拓撲特徵，由於拓撲特徵包涵了豐富的點雲特徵，所以可以減少提取點的數量同時保證了匹配效果。本算法中確定對應點時考慮了鄰域特徵，從而提高了算法對噪聲的魯棒性。
文檔編號G06T15/00GK103150747SQ201210488409
公開日2013年6月12日 申請日期2012年11月16日 優先權日2012年11月16日
發明者馮琰一, 汪剛, 高峰 申請人:佳都新太科技股份有限公司