[發(fā)明專利]基于凸包不變性的點云配準(zhǔn)方法

有效

• 申請?zhí)枺?/td>: 201210485248.2
• 申請日: 2012-11-26
• 公開（公告）號: CN103020960A
• 公開（公告）日: 2013-04-03
• 發(fā)明（設(shè)計）人: 楊健;王涌天;劉越;范敬凡
• 申請（專利權(quán)）人: 北京理工大學(xué)
• 主分類號: G06T7/00
• 分類號: G06T7/00
• 代理公司: 北京理工大學(xué)專利中心 11120
• 代理人: 高燕燕

技術(shù)領(lǐng)域

本發(fā)明涉及一種基于凸包不變性的點云配準(zhǔn)方法，可用于物體跟蹤、三維模型拼接和三維重建等領(lǐng)域。

背景技術(shù)

點云配準(zhǔn)主要用于解決兩個或多個三維物體間的位姿或配準(zhǔn)估計問題。其在許多領(lǐng)域均得到廣泛的應(yīng)用，包括物體的跟蹤、三維模型拼合和三維重建等。點云配準(zhǔn)的過程一般可描述為建立目標(biāo)點云和參考點云之間的匹配關(guān)系。

在過去的幾十年中，大量的算法被提出以解決點云的匹配。Besl等人提出迭代最鄰近點(Iterative?Closest?Point,ICP)算法，該算法在六個自由度上均單調(diào)性收斂到鄰近的最小值。該算法可有效的匹配自由曲線和自由曲面，及配準(zhǔn)具有理想幾何原型的點云數(shù)據(jù)。ICP的廣泛應(yīng)用因其對點云空間分布的敏感而存在局限性。ICP算法只能配準(zhǔn)具有某些特定初始位姿的點云，當(dāng)噪聲點、雜亂點或者異常點存在時，該算法失效；另外，ICP的時間復(fù)雜度隨待配準(zhǔn)點云數(shù)目的增大而顯著增大。

為解決ICP存在的缺陷，從該算法中衍生出多種改進(jìn)算法。為降低系統(tǒng)對初始位姿的依賴，大量的學(xué)者引入不同的描述子對點云進(jìn)行描述，或者通過不同的優(yōu)化算法求取點云的匹配關(guān)系。另一方面，為降低算法的復(fù)雜度，大量的學(xué)者將點云子塊化或者通過GPU一系列集成環(huán)境進(jìn)行算法本身的加速。雖然目前提出的算法可在一定程度上有效解決原始點云配準(zhǔn)算法的缺陷，但未從數(shù)據(jù)層次獲得有效的解決措施，尚不能滿足實際應(yīng)用的要求。

因此需要一種有效的點云配準(zhǔn)算法，能夠計算目標(biāo)點云和參考點云間的最優(yōu)三維坐標(biāo)變換關(guān)系并滿足：（1）不依賴點云的初始位姿，具備較強(qiáng)的自適應(yīng)性；（2）計算速度快，盡可能滿足點云配準(zhǔn)實際應(yīng)用中的時間要求。

發(fā)明內(nèi)容

為克服現(xiàn)有點云配準(zhǔn)算法中存在的不足，本發(fā)明提供一種基于凸包不變性的點云配準(zhǔn)方法,通過提取點云的凸包進(jìn)行點云間的配準(zhǔn)，旨在降低算法的計算復(fù)雜度及對點云初始位姿的依賴性。

該基于凸包不變性的點云配準(zhǔn)方法，包括以下步驟：

第一步：提取可包含整個點云的最大凸多面體，其中凸多面體的頂點全部由點云中一系列滿足預(yù)設(shè)條件的點構(gòu)成；

第二步：將凸包表面分解為一系列三角形，三角形之間無重疊，且三角形頂點p_A,p_B,p_C的定義滿足以下關(guān)系：在右手坐標(biāo)系中，差積Dir＝(p_B-p_A)×(p_C-p_B)指向點云內(nèi)部；

第三步：基于三維點云在歐式空間剛性變換中的凸包不變性，設(shè)定判斷三角形全等判定閾值，提取兩組凸包表面滿足匹配關(guān)系的三角形對；

第四步：在滿足條件的三角形配對中，設(shè)定三角形的四個特征點，包括三個頂點及沿過三角形重心指向點云內(nèi)部的法線方向，距三角形平面單位距離的點；

第五步：根據(jù)三角形提取的四個特征點，建立歐式空間中幾何變換關(guān)系的方程組，利用非線性阻尼最小二乘法優(yōu)化變換參數(shù)，獲得匹配三角形對之間的變換關(guān)系；

第六步：求取原始點云在第五步中獲得的變換關(guān)系下的變換點云，求解變換點云和目標(biāo)點云之間的相似性測度，選擇最大相似性測度對應(yīng)的變換參數(shù)描述點云間的最優(yōu)變換。

本發(fā)明的有益效果：

與現(xiàn)有方法相比，本方法的優(yōu)點在于利用歐式空間點云的凸包不變性進(jìn)行點云的剛性配準(zhǔn)，對點云本身初始位姿不具有依賴性，且可自適應(yīng)校正初始位姿。本發(fā)明通過提取兩組三維點云的凸包，以有向三角形描述凸包表面，獲取兩組凸包上全等三角形對的變換關(guān)系，確定點云之間具有最大相似性測度的匹配關(guān)系，即實現(xiàn)配準(zhǔn)過程。實現(xiàn)簡單，效率高，配準(zhǔn)精度高。

附圖說明

圖1為本發(fā)明具體實施例的流程圖。

具體實施方式

下面結(jié)合具體實施例和附圖詳細(xì)說明本發(fā)明，但本發(fā)明并不僅限于此。

步驟S101，對于一個有限大小的點云P∈R³，Conv(P)是在R³空間中包含P的相應(yīng)的最小凸多面體，其中Conv(P)被定義為：

即任意空間點p∈P滿足時，則可稱其為Conv(P)上的一個頂點。□³空間中這些頂點對應(yīng)的凸多面體構(gòu)成了P的凸包。