計(jì)算機(jī)視覺(jué)三維測(cè)量與建模 課件 【ch07】點(diǎn)云特征提取和三維配準(zhǔn)

第七章計(jì)算機(jī)視覺(jué)三維測(cè)量與建模點(diǎn)云特征提取和三維配準(zhǔn)南京航空航天大學(xué)研究生教育教學(xué)改革專項(xiàng)（優(yōu)質(zhì)教學(xué)資源建設(shè)）項(xiàng)目資助01點(diǎn)云特征提取將不同時(shí)刻或不同視角由影像重建或激光雷達(dá)掃描的點(diǎn)云數(shù)據(jù),根據(jù)數(shù)據(jù)重疊區(qū)域的關(guān)聯(lián)，找到一組轉(zhuǎn)換參數(shù)，使不同組數(shù)據(jù)能夠統(tǒng)一到相同的坐標(biāo)系統(tǒng)下，這個(gè)過(guò)程叫作點(diǎn)云配準(zhǔn)。配準(zhǔn)算法的本質(zhì)是在全局坐標(biāo)系中找到不同視圖之間的相對(duì)位置姿態(tài)，使對(duì)應(yīng)點(diǎn)云的相交區(qū)域完全重合(如圖7.1所示)。將點(diǎn)云配準(zhǔn)融合成一個(gè)點(diǎn)云結(jié)構(gòu)，可以便于進(jìn)行后續(xù)的內(nèi)容分割和對(duì)象表面建模。點(diǎn)云特征提取點(diǎn)云特征提取三維數(shù)據(jù)的特征表達(dá)能力是目標(biāo)特性分析的主要依據(jù)。當(dāng)前的研究趨勢(shì)正在從以點(diǎn)為單元向著以體素和對(duì)象等為單元的處理方式發(fā)展,它們是點(diǎn)的再組織形式。這類單元的上下文信息更豐富，能夠適應(yīng)不同的數(shù)據(jù)質(zhì)量；而且降低了數(shù)據(jù)量，可以明顯提高特征表達(dá)的效率。點(diǎn)云特征提取點(diǎn)云配準(zhǔn)算法的總體流程包含兩個(gè)階段：全局粗配準(zhǔn)和局部精配準(zhǔn)，也可叫作粗配準(zhǔn)和精配準(zhǔn)。粗配準(zhǔn)是在兩組點(diǎn)云沒(méi)有相對(duì)位置的先驗(yàn)信息的情況下，找到兩組點(diǎn)云的初始配準(zhǔn)參數(shù)；精配準(zhǔn)是在有先驗(yàn)初始配準(zhǔn)參數(shù)的條件下,進(jìn)一步優(yōu)化調(diào)整參數(shù)，提高匹配精度。點(diǎn)云特征提取】9特征描述子的數(shù)學(xué)形式是一類特征向量，用量化的方式記錄了空間結(jié)構(gòu)的某些特性，反映指定點(diǎn)、局部鄰域集合或全局結(jié)構(gòu)的形狀特征。通過(guò)在特征空間中度量向量的相似性，建立不同曲面點(diǎn)的對(duì)應(yīng)關(guān)系。點(diǎn)云特征提取】9點(diǎn)特征直方圖（PointFeatureFtistogram，PFH）是對(duì)鄰域范團(tuán)內(nèi)空間差異的一種量化，通過(guò)數(shù)理統(tǒng)計(jì)的方法獲得一個(gè)用于描達(dá)中心點(diǎn)鄰域點(diǎn)集合幾何信息的直方圖。PFH是將一個(gè)點(diǎn)的鄰域均值、曲率、幾何特性編碼到多維的直方圖中，這樣的高維數(shù)據(jù)提供了大信,息量的特征表達(dá)。PFH特征不僅在旋轉(zhuǎn)和平移六自由度變換下具有不變性，還能很好地適應(yīng)不同程度的采樣密度和噪聲影響，屬于一個(gè)整體尺度和姿態(tài)不變的多值特征。點(diǎn)云特征提取快速點(diǎn)特征直方圖(FastPointFeatureFistogram,FPFH)）是PFH的快速版本，與PFH特征的大部分特性和原理相同。區(qū)別在于，F(xiàn)PFH簡(jiǎn)化了PFH計(jì)算特征元素的過(guò)程，降低了算法的復(fù)雜度，同時(shí)保留了PFH的大部分判別能力?？焖侔姹静扇∫恍┖?jiǎn)化和優(yōu)化措施來(lái)提升計(jì)算速度。需要再次強(qiáng)調(diào)，點(diǎn)云的法向量質(zhì)量對(duì)于FPFH特征的質(zhì)量有很大影響。點(diǎn)云特征提取首先，F(xiàn)PFH將原有的4個(gè)特征簡(jiǎn)化為3個(gè)特征，只保留了3個(gè)角度特征。其次，在PFH中，求查詢點(diǎn)p的特征直方圖需要計(jì)算P和飛鄰域內(nèi)所有點(diǎn){Pk}組成的集合poUip.了中的所有兩兩點(diǎn)之間的特征，這無(wú)形中添加了很多冗余的計(jì)算。在FPFH中，只計(jì)算中心點(diǎn)和鄰域點(diǎn)的點(diǎn)對(duì)（P0，Pk）之問(wèn)的特征，與中心點(diǎn)p0。無(wú)關(guān)的點(diǎn)對(duì)就不再計(jì)算，這樣就構(gòu)成了一個(gè)新的簡(jiǎn)化點(diǎn)特征直方圖(SimplePointFeatureFtistogram,SPFE)。然后，使用中心點(diǎn)p0和{pk}中每個(gè)點(diǎn)的SPFH加權(quán)求和構(gòu)成了所謂的FPFH。點(diǎn)云特征提取Harris角點(diǎn)最早被應(yīng)用手二維影像特征提取，3.3.1節(jié)內(nèi)容已經(jīng)對(duì)其做了介紹。后來(lái)，Harris角點(diǎn)提取算法被拓展到三維數(shù)據(jù)處理中。三維Harris特征方法基于三維點(diǎn)云的局部鄰域形狀的可求導(dǎo)性研究，用一個(gè)函數(shù)對(duì)鄰域點(diǎn)進(jìn)行擬合，并將該函數(shù)的導(dǎo)數(shù)較大的點(diǎn)提取并作為特征點(diǎn)。與影像不同，三維數(shù)據(jù)可能具有任意的拓?fù)浣Y(jié)構(gòu)和采樣密度，這使得導(dǎo)數(shù)的計(jì)算復(fù)雜化。點(diǎn)云特征提取基于投影的方法0102基于體素的方法03基于點(diǎn)的方法基于深度學(xué)習(xí)的分割而設(shè)計(jì)的點(diǎn)特征提取技術(shù)，通常需要依靠計(jì)算昂貴的內(nèi)核化或圖形構(gòu)造，概括起來(lái)的技術(shù)分類有：點(diǎn)云特征提取02點(diǎn)云精配準(zhǔn)就解決具體問(wèn)題的過(guò)程而言，粗配準(zhǔn)操作要在精配準(zhǔn)操作之前完成。然而從理論知識(shí)的介紹而言，首先介紹精配準(zhǔn)更具有意義。如果提供了良好的粗配準(zhǔn)結(jié)果作為精配準(zhǔn)的初始值，那么通常算法可以保證配準(zhǔn)結(jié)果的收斂。但是,在一個(gè)完全陌生的觀測(cè)場(chǎng)景，粗配準(zhǔn)是一項(xiàng)更具有挑戰(zhàn)性的工作，這項(xiàng)工作目前仍是一個(gè)研究熱點(diǎn)。遵循由簡(jiǎn)入難的原則，本節(jié)先對(duì)精配準(zhǔn)算法進(jìn)行介紹。點(diǎn)云精配準(zhǔn)】9迭代最鄰近點(diǎn)（IterativeClosestPoint,ICP）算法被認(rèn)為是當(dāng)今應(yīng)用最廣泛的一種精配準(zhǔn)參數(shù)優(yōu)化算法，該算法由BeslPJ和MckayHD在1992年提出1，是一種高層次的基于自由形態(tài)曲面的配準(zhǔn)方法。ICP算法不僅能夠處理點(diǎn)云與點(diǎn)云之間的配準(zhǔn)問(wèn)題，而且對(duì)點(diǎn)云到模型、模型到模型的配準(zhǔn)問(wèn)題同樣具有一定的效果。點(diǎn)云精配準(zhǔn)01基于統(tǒng)計(jì)學(xué)的方法參與配準(zhǔn)的兩組觀測(cè)數(shù)據(jù)必須彼此接近。否則，ICP算法可能會(huì)陷入局部極小值。這個(gè)問(wèn)題通常通過(guò)兩組點(diǎn)云的預(yù)對(duì)齊來(lái)解決，也稱為粗配準(zhǔn)。02基于表面重采樣的方法兩組觀測(cè)數(shù)據(jù)的視場(chǎng)范團(tuán)必須基本一致，或者待配準(zhǔn)視圖數(shù)據(jù)衛(wèi)必須是參考視圖數(shù)據(jù)的子集。算法中，ICP為每個(gè)待配準(zhǔn)的數(shù)據(jù)點(diǎn)都分配一個(gè)最近的參考數(shù)據(jù)點(diǎn)。雖然ICP算法己經(jīng)可以成功地解決許多配準(zhǔn)問(wèn)題，但仍有幾個(gè)關(guān)鍵問(wèn)題需要注意，特別是以下情況需要考感。點(diǎn)云精配準(zhǔn)提高配準(zhǔn)速度(1)降采樣方法。降采樣可以僅作用于待配準(zhǔn)的目標(biāo)點(diǎn)云數(shù)據(jù)，也可以同時(shí)應(yīng)用于參考點(diǎn)云數(shù)據(jù)和待配準(zhǔn)點(diǎn)云數(shù)據(jù)。隨機(jī)和均勻的采樣策略都是常見(jiàn)的方法。(2)最近點(diǎn)計(jì)算。早期的最近點(diǎn)計(jì)算策略是用KD樹對(duì)參考點(diǎn)云進(jìn)行組織，可以將最近點(diǎn)搜索的復(fù)雜度降低到O(glogn)。最近點(diǎn)緩存也加快了ICP的速度，緩存方法是指在點(diǎn)對(duì)應(yīng)搜索時(shí)僅在上一次選代中最近點(diǎn)的周圍點(diǎn)子集中進(jìn)行搜索。(3)距離定義。點(diǎn)到面的距離是根據(jù)點(diǎn)投影計(jì)算的，點(diǎn)云表面模型的知識(shí)將在第8章中介紹。盡管距離公式的復(fù)雜度增大，但收斂所需的ICP迭代次數(shù)減少了。點(diǎn)云精配準(zhǔn)提高配準(zhǔn)精度(1)可以使用最簡(jiǎn)單的策略剔除異常值。(2)可以借助其他輔助信息（如顏色和紋理或局部幾何特性等）來(lái)提高精度。(3)基于概率的方法是提高精度的一類有效方法。點(diǎn)云精配準(zhǔn)將觀測(cè)場(chǎng)景的二維空間規(guī)則地細(xì)分為大小不變的矩陣單元格，使用單元格內(nèi)的所有點(diǎn)計(jì)算一個(gè)概率密度函數(shù)（ProbabilityDensityFunction,PDF），執(zhí)行以下操作。下面具體介紹二維掃描數(shù)據(jù)的NDT配準(zhǔn)算法的步聚。點(diǎn)云精配準(zhǔn)點(diǎn)云精配準(zhǔn)配準(zhǔn)目標(biāo)是找到一組轉(zhuǎn)換參數(shù)，最大化所有的待配準(zhǔn)的掃描點(diǎn)位于參考點(diǎn)云中的位置的概率值，即最大似然函數(shù)。最大概率值是通過(guò)評(píng)估每個(gè)映射點(diǎn)的分布并對(duì)結(jié)果求積來(lái)確定的。最大化的目標(biāo)函數(shù)為：點(diǎn)云精配準(zhǔn)01固定尺寸劃分。固定尺寸是最常見(jiàn)的劃分方式之，初始化操作簡(jiǎn)單，而且能容易找到每個(gè)點(diǎn)對(duì)應(yīng)的網(wǎng)格。02八叉樹劃分。如何快速找到每個(gè)點(diǎn)對(duì)應(yīng)的網(wǎng)格是搜索速度的關(guān)鍵，八叉樹結(jié)構(gòu)是常見(jiàn)的三維搜索樹。三維NDT算法最重要的參數(shù)是單元格的尺寸。尺寸太大，容易導(dǎo)致?lián)p失一些局部特征；尺寸太小則會(huì)增加很多計(jì)算量。點(diǎn)個(gè)數(shù)很少的單元格會(huì)失去統(tǒng)計(jì)的意義，少數(shù)數(shù)據(jù)對(duì)結(jié)果影響過(guò)大。對(duì)空間進(jìn)行單元格劃分的方法有以下幾種。點(diǎn)云精配準(zhǔn)03尺寸細(xì)化選代劃分。好的初始位置可以加快收斂過(guò)程，一種常見(jiàn)的方法就是迭代起始位置，將上一次的終點(diǎn)位姿作為本次的起點(diǎn)位姿。04自適應(yīng)聚類劃分。對(duì)點(diǎn)云數(shù)據(jù)采用聚類算法（如區(qū)均值聚類）劃分為多個(gè)聚類，每個(gè)聚類都作為一個(gè)NDT單元。05連接單元格。之前提到少于5個(gè)點(diǎn)的單元格會(huì)被舍棄，導(dǎo)致出現(xiàn)一些空的單元格，因而損失了數(shù)據(jù)的完整性。06三線性插值。由于固定尺寸劃分的單元格計(jì)算的PDF在單元格邊界出現(xiàn)不連續(xù)的情況，插值的方法相當(dāng)于做了平滑。點(diǎn)云精配準(zhǔn)03點(diǎn)云粗配準(zhǔn)點(diǎn)云數(shù)據(jù)的自動(dòng)化粗配準(zhǔn)目前來(lái)說(shuō)還是一個(gè)難點(diǎn)。針對(duì)不同的數(shù)據(jù)，有許多不同的方法被提出。粗配準(zhǔn)算法求出的位置姿態(tài)參數(shù)結(jié)果可以用作精配準(zhǔn)的初始值，從而在局部進(jìn)行優(yōu)化配準(zhǔn)。在實(shí)踐中，粗配準(zhǔn)預(yù)對(duì)齊技術(shù)不是搜索密集的點(diǎn)對(duì)點(diǎn)對(duì)應(yīng)，而是從視圖中提取出稀疏的特征點(diǎn)之間的最佳關(guān)聯(lián)對(duì)應(yīng)。點(diǎn)云粗配準(zhǔn)簡(jiǎn)單來(lái)說(shuō)，特征可以是全局的，也可以是局部的。前者是一種緊湊的表示,有效而簡(jiǎn)潔地描述了整個(gè)觀測(cè)視圖；后者基于觀測(cè)視圖的一部分子集計(jì)算出局部的和具有區(qū)分能力的描述符集合。全局特征描述難以捕捉細(xì)節(jié)的細(xì)微變化，對(duì)物體遮擋敏感。如7.1節(jié)所介紹的特征提取的內(nèi)容，局部幾何特征一般是點(diǎn)云局部結(jié)構(gòu)上的關(guān)鍵點(diǎn)，提取這些三維關(guān)鍵點(diǎn)的方式與從影像中提取二維特征的方式類似。點(diǎn)云粗配準(zhǔn)】9點(diǎn)云粗配準(zhǔn)】9四點(diǎn)一致集（4-PointCongruentSet,4PCS）配準(zhǔn)算法是由AigerD等人在2008年提出來(lái)的適用于各種點(diǎn)云的一種快速搜索關(guān)聯(lián)點(diǎn)對(duì)的算法，4PCS不需要先驗(yàn)信息的搜索策路。點(diǎn)云粗配準(zhǔn)超級(jí)四點(diǎn)(Super4-PointCongruentSet,Super4PCS)算法。Super4PCS算法是對(duì)4PCS配淮算法拓展的加速方案。這種算法在4PCS配準(zhǔn)算法的基礎(chǔ)上額外記錄兩條直線相交的角度，判斷角度是否在一定范圍內(nèi)。0102普適四點(diǎn)一致集(Generalized4-PointCongruentSet,G-4PCS)算法。G-4PCS算法是對(duì)Super4PCS算法的進(jìn)一步擴(kuò)展132，此時(shí)提取的4個(gè)點(diǎn)不再要求共面。點(diǎn)云粗配準(zhǔn)超點(diǎn)SP實(shí)質(zhì)上就是由部分點(diǎn)組成的一個(gè)點(diǎn)集合，并將這個(gè)集合當(dāng)作整體處理流程的基本單元。下面介紹LORAX粗配準(zhǔn)算法的基本流程。（1）隨機(jī)選擇球包絡(luò)內(nèi)點(diǎn)集合(RandomSphereCoverSet,RSCS)。為了能夠覆蓋點(diǎn)云的絕大部分，采用以下的迭代步驟來(lái)定義這些超點(diǎn)。（2）為每個(gè)SP建立一個(gè)歸一化的局部坐標(biāo)系。（3）投影獲得深度圖。（4）顯著性檢測(cè)和SP篩選。（5）深度自動(dòng)編碼器(DeepAuto-Encoder,DAE)降維。（6）選擇候選匹配。（7）迭代尋優(yōu)配準(zhǔn)。點(diǎn)云粗配準(zhǔn)04異源三維數(shù)據(jù)的配準(zhǔn)融合異源配準(zhǔn)算法是將點(diǎn)云的其他屬性信息(比如顏色、強(qiáng)度和幾何信息)相結(jié)合進(jìn)行配準(zhǔn)的方法，或者將影像重建的點(diǎn)云與LiDAR掃描的點(diǎn)云進(jìn)行跨模態(tài)方式的配準(zhǔn)。例如，將RGBD深度圖基于顏色的配準(zhǔn)方案和基于幾何位置的配準(zhǔn)方案相結(jié)合，并推廣到無(wú)序點(diǎn)云中用于點(diǎn)云配準(zhǔn)。異源三維數(shù)據(jù)的配準(zhǔn)融合】9異源三維數(shù)據(jù)的配準(zhǔn)融合】9異源三維數(shù)據(jù)的配準(zhǔn)融合05應(yīng)用舉例】9應(yīng)用舉例】9本章所列的配準(zhǔn)算法都是針對(duì)兩組觀測(cè)數(shù)據(jù)設(shè)計(jì)的配準(zhǔn)算法。觀測(cè)數(shù)據(jù)是序列化的多組，可以在連續(xù)的觀測(cè)數(shù)據(jù)之間成對(duì)地執(zhí)行配準(zhǔn)。一般來(lái)說(shuō)，即使所有的成對(duì)數(shù)據(jù)都能明顯地被很好地配準(zhǔn)，由于存在配準(zhǔn)誤差的累積和傳播，在所有數(shù)據(jù)整合后，重構(gòu)完整模型時(shí)依然會(huì)出現(xiàn)一些失準(zhǔn)。應(yīng)用舉例為了解決全局配準(zhǔn)問(wèn)題，多視點(diǎn)配準(zhǔn)技術(shù)利用多視點(diǎn)之間的相互依賴性，引入額外的約束，以減少全局錯(cuò)誤。PulliK提出了一種全局方法，首先將掃描數(shù)據(jù)兩兩對(duì)齊，然后在多視圖匹配步驟中使用兩兩對(duì)齊作為約束。其目的是均勻地分配兩兩配準(zhǔn)的誤差，但該方法本身仍然是基于兩兩對(duì)齊的。通常減小累計(jì)誤差的方法都是在所有視圖中均勻地分配誤差。另外，有研究基于著名的廣義普羅科斯特斯分析（GeneralizedProcrustesAnalysis）方法來(lái)設(shè)計(jì)新算法，將數(shù)學(xué)理論無(wú)縫嵌入ICP框架。該方法的一種變體是使用基于曲率的相似性度量對(duì)配準(zhǔn)的對(duì)應(yīng)關(guān)系進(jìn)行非均勻加權(quán)，實(shí)現(xiàn)誤差的分配。應(yīng)用舉例01基于優(yōu)化技術(shù)的配準(zhǔn)算法02基于概率統(tǒng)計(jì)的配準(zhǔn)算法利用概率方法，可通過(guò)采用最大似然估計(jì)來(lái)解決場(chǎng)景目標(biāo)柔性變換的不確定性。概率方法的基礎(chǔ)是通過(guò)核密度函數(shù)對(duì)每個(gè)點(diǎn)集進(jìn)行建模。通過(guò)引入適當(dāng)?shù)木嚯x函數(shù)來(lái)計(jì)算這些密度函數(shù)之間的差異。配準(zhǔn)是在沒(méi)有明確建立匹配點(diǎn)對(duì)應(yīng)的情況下進(jìn)行的。實(shí)際上，該類算法通過(guò)優(yōu)化一個(gè)聯(lián)合概率模型來(lái)配準(zhǔn)兩組數(shù)據(jù)，該數(shù)據(jù)模型覆蓋了它們之間的所有點(diǎn)到點(diǎn)對(duì)應(yīng)關(guān)系。應(yīng)用舉例06小結(jié)三維數(shù)據(jù)的配準(zhǔn)融合是一個(gè)十分活躍的研究方向,仍有許多問(wèn)題需要解決。普適性、穩(wěn)定性、精準(zhǔn)性和自動(dòng)化程度是評(píng)價(jià)一種配準(zhǔn)算法的性能優(yōu)劣的主要指標(biāo)項(xiàng)。為了避免窮舉搜索，許多算法利用