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

Fulls）、計算獄洛尼三角剖分（DelaunayTriangulation）和計算阿爾法形狀（cshape）等代表性算法。顯式建模算法主體上通過連接采樣點構建三角形，是對采樣點的精確插值。第二類是隱式建模算法，這類算法假設采樣點云中隱含一種能夠近似表達幾何表面模型的隱函數。該類算法將空間區域假設為一個標量場，即由采樣點云構造一個函數值分布空間。三維表面網格模型】9第三類算法是利用先導模式化結構對目標進行建模，是一種自上而下的建模算法。在第6章中介紹基于模型的場景結構分割的理論時，對模式化的結構有所定義，可以說這里的模式化建模就是在點云模型化分割的基礎上形成網格的一種后處理?；谀０寤蛘呦闰災Ｊ降闹亟ǚ椒梢约毞殖龈喾N類、更復雜的子類，隨應用場景的不同而可以有多種多樣的設計形式。三維表面網格模型紋理模式紋理模式是用于三維模型的真實可視化的直觀表達方式，紋理是讓三維模型看起來接近現實物體的一個最基本的要素。最簡單形式的紋理貼圖涉及將單個紋理（如照片或正射影像）映射到由一個或多個多邊形組成的表面多邊形上。當將影像映射到對象上時，每個對象的多邊形顏色都將由從紋理派生的相應顏色進行修改。01三維表面網格模型陰影模式陰影模式（ShadingModel）是基于光學理論（蘭伯特余弦定理）設計的，該理論指出，基于完美散射起伏表面的任何小區域（多邊形）的亮度都會隨著入射平行光角度的余弦而增大。該算法中，最廣為人知的是平面陰影和平滑陰影。平面陰影和平滑陰影之間的主要區別在于使用法線的方式。02三維表面網格模型光照模式要為真實場景創建這樣一個完整的模型，需要使用大量的視圖。這些視圖可以視為具有相應顏色值的光線集合，它們是一個完全連續函數的離散樣本?？紤]到物理限制的附加信息，必須從記錄的光線中插入未表示的光線。03三維表面網格模型01壓縮數據的幾何形狀：這類算法試圖改善網格的數字信息（頂點的位置、法線、顏色等）的存儲，或者尋求對網格拓撲進行有效編碼的方法。02控制細節層次(LOD)：出于可視化目的，軟件可以用LOD技術在整個場景中平滑變化，不同位置的渲染的細膩程度取決于觀察者所在的當前位置。03網格濾波（Filtering）優化和簡化(Decimation）：這些算法簡化了網格，去掉了冗余的頂點、邊和三角形基元，可以選代地移除不符合特定距離/角度標準的頂點，或將邊折疊成唯一的項點。04點渲染：特別適用于點云可視化，并且通過是示較少數量的圖元來工作。QSplat是一個基于點的渲染系統，能夠使用不同復雜形狀的濺斑（Splat）圖元和不同的透明度米渲染相同的對象，以避免鋸齒邊緣，在實時性和渲染方面是示出良好的效果?；诰W格模型的幾何信息和拓撲結構這兩個信息，學者們針對三角形網格模型提出了許多壓縮算法。三維表面網格模型02顯式建模方法凸集有兩種定義方式。第一種：如果對任意兩點2.9ES，線段P9CS，則集合S是凸的。第二種：如果集合5是(可能無限多個）半空間的交集，則S是凸的。圖8.7給出了凸集和非凸集的二維示例。顯式建模方法顯式建模方法二維空間的Delaunay三角剖分Delaunay三角剖分是一種標準，己有許多計算Delaunay三角剖分的算法，它們主要依賴于檢測點是否在三角形的外接圓內，需要設計快速存儲三角形的有效數據結構。增量式的枸網算法是最直接有效地計算Delaunay三角剖分的算法。這類算法通過逐點添加的形式插入新頂點，確定圖形受影響的部分，僅對一部分區域進行三角剖分約束判斷和優化調整。顯式建模方法二維空間的Delaunay三角剖分01顯式建模方法三維點云數據的Delaunay三角剖分02把Delaunay三角剖分的屈性從二維擴展到更高的三維，其背后的原理是一致的。三維點云的Delaunay三角剖分的約束是四個點組成的四面體（4個三角形）的外接球不包含其他的點，即要生成符合空外接球規則的四面體組成。顯式建模方法三維點云數據的Delaunay三角剖分對三維點云處理，依然適用增量式的Delaunay三角劑分算法。首先，初始化一個大的四面體，能夠將場景中的所有三維點都包含在內，大四面體的頂點不一定是輸入數據的點。然后，依次逐點向其中插入新的頂點，進行判斷和構網。每次插入新頂點p時，需要判斷點p是落在哪一個四面體的內部，這個四面體被視為一個父節點，新的頂點會將父節點四面體剖分重組，父節點四面體進而被標注為無效。新生成的四面體被視為子節點。尋找父節點的方法可以是遍歷己經生成的列表中的所有四面體，也可以是通過設計數據結構加速檢索。顯式建模方法】9顯式建模方法03隱式建模方法】9隱式建模方法】9隱函數表達式：隱式建模方法徑向基函數（RadialBasisFunctions,RBF）是一種常用的對離散數據插值的函數方法。對于一組給定采樣數據，RBF方法使用一組徑向對稱的基函數的線性組合生成高度平滑的擬合結果。隱式建模方法隱式建模方法移動最小二乘（MovingLeastSquares,MIS）算法將重建表面近似為一個空間變化的低階多項式。如8.3.1節所達，隱式表面建模對應的是一個插值問題，MLS算法用局部多項式f(x)逼近表面F。用移動最小二乘算法將插值問題變為一個函數優化問題，f(x)被選為對數據點x的最佳名項式逼近。隱式建模方法隱式建模方法】9泊松表面重建方法（PoissonReconstruction）是KazhdanM等人在2006年提出的種隱函數建模方法143，并且提供了開源代碼，是目前廣為使用的一種表面建模方法。泊松表面重建方法利用Poisson兩數來解決有向點云的表面擬合問題。它結合了全局擬合和局部擬合兩類方法的特點，因此在速度和精度兩個方面有較好的效果。由于全局優化的特性，在形成鄰近區域、選擇面片類型和調整權重時不涉及啟發式的決策。另外，基函數是和周圍空間相關的而不僅是和數據點相關的，有一個局部層次支持的結構，從而產生稀疏的優良表現。隱式建模方法】9隱式建模方法01下面介紹用MC算法構建網格模型的步驟：將三維空間規則地進行體素化，離散后的每個體素單元都包含8個頂點{v1,…,v8}，每個頂點都能夠由隱函數計算出對應的函數值，即計算出f(vi）。02對體素的頂點進行標記。如果f(vi)的值大于或等于零等值面的值，則認為該頂點位于等值面之外，標記為“0”03根據8個頂點的二進制標記值計算體素的素31號index。隱式建模方法04根據體素的索引號index，在預先構建好的查找表中找到體素內的網格的連接方式。05盡管知道了等值面會穿過哪條邊，如邊（VaVb），但具體在邊上會經過的點位置還沒有確定。此時，需要通過插值計算找到，可以使用邊的兩個頂點位置由簡單的線性插值計算。06消除歧義。在算法中設計了根據體素頂點的法向量消除這樣的不連貫歧義。在整體的體素劃分空間中，每個頂點有上、下、左、右、前、后6個相鄰的頂點，采用中心差分方