文獻下載鏈接：https://download.csdn.net/download/m0_37957160/12543541

摘要：

? ? ? ? 本文提出了一種非常簡單有效的算法，從大規模無序點云中進行3維線段的分割檢測算法。與傳統的方法先提取3D邊緣點，然后再擬合三維線段的算法不同，我們提出了一種基于點云分割和2維線段檢測為基礎的能夠快速實現3D線段檢測的算法。在輸入無序點云的情況下，對三維線段進行三步檢測。首先，通過區域生長和區域合并將點云分割成3D平面。其次，對于每一個三維平面，將其自身所屬的所有點投影到自身平面上形成二維圖像，然后進行二維輪廓提取和最小二乘擬合得到二維線段。然后將這些二維線段重新投影到三維平面上，以獲得相應的三維線段。最后，提出了一種剔除異常點和合并相鄰三維線段的后處理方法，在多個公共數據集上的實驗證明了該方法的有效性和魯棒性。更多的結果和C++源代碼的公開在https://github.com/xiaohulugo/3DLineDetection。

I. INTRODUCTION?

? ? ? ? 線段可以很好地代表場景，尤其是在城市中，那里有許多規則形狀的人造結構。在過去的十年中，對2D圖像的線段檢測進行了深入研究，并提出了幾種有效的算法[1] – [3]，包括廣泛使用的LSD [1]。但是，解決3D線段檢測的工作仍然不足，一般可分為三類：基于點，基于平面和基于圖像。

? ? ? ? 基于點的方法通常先檢測最小邊界點，然后通過最小二乘擬合法確定3D線段的邊界點。給定輸入點云，我們可以通過凸包方法[4]，[5]獲得邊界點，或通過設計特征將整個點云分類為邊界/非邊界類別。原始的凸包算法可以有效地找到凸的邊界點，但不適合提取凹輪廓。[6]改進了凸包，允許在提取的形狀中有一些凹陷。但是，基于凸包的方法仍然“由于點云中的點分布不均勻而未被發現特別有用” [5]。另一方面，邊界/非邊界點云的分類具有多種特征，包括曲率或表面變化[7]，高斯圖[8]，多尺度正態差異[9]，基于特征值和特征向量[10]。在[9]的工作中，每個點的法線以不同的比例來計算，然后將法線差較大的法線歸類為邊界點。在最近的工作[10]中，使用二值分類器使用從該點的鄰域中提取的一組特征來預測每個點的輪廓分數。給定提取的邊界點，我們可以構建八叉樹，然后通過區域增長和最小二乘擬合來擬合3D線段。這些基于點的方法的最大問題在于特征點本身，該特征點對噪聲魯棒性不強。

? ? ? ??基于平面的方法也是合理的選擇，因為3D線段也可以視為兩個3D平面的交點。然而，基于平面的方法更常用于機載LiDAR [11]的建筑建模中，其中點通常不是很密集。例如，在[11]的工作中，首先將平面點與非平面點區分開，然后根據其法線將其聚集成單個屋頂段，最后檢測相鄰的段并將其與頂點和邊界線段相交。在另一項工作中[12]，將通過平面相交從點云中提取的3D線段與它們的2D對應線段組合起來，用來校準距離和圖像傳感器的外部參數。基于平面的方法的一個常見缺點是，通常很難確定相交線的端點，此外，這種方法不適用于小平面。

? ? ? ? 基于圖像的方法首先將輸入點云轉換為圖像，然后應用線段檢測器提取圖像上的2D線段，最后將這些2D線段重新投影到點云上來獲得最終3D線段。將點云轉換為圖像是點云處理中經常使用的一種策略，例如，在最近的工作[13]中，將點云分割為多個橫截面，然后將每個橫截面中的點云投影到 特定平面，然后從不同的2D圖像中提取特征點。在最近的工作[14]中，輸入點云被轉換為具有不同視點的投影圖像的集合，這些具有不同視點的圖像均勻地放置在圍繞點云的球體上。然后，應用LSD算法[1]在這些投影圖像的每一個上提取2D線段，再將其反投影到原始點云中以獲得初始3D線段。這些基于圖像的方法的關鍵問題在于圖像生成策略，難以確定這些投影圖像的數量，分辨率和視點。

? ? ? ? 本文提出的方法屬于基于圖像的類別。為了克服傳統基于圖像的方法的不足，我們提出了一種簡單而有效的3D線段檢測方法，該方法包含以下三個步驟：?

? ? ? ??（1）點云分割：通過區域生成的和區域合并的方法，將輸入的點云分割成三維平面。

? ? ?? （2）基于平面的三維直線的檢測：對于每個點云平面，所有屬于該平面的點云投影到平面上形成二維圖像，然后基于二維圖像進行輪廓提取和最小二乘擬合，得到每個平面的二維線段。最后將這些二維線段重影映射到三維平面上，就可以獲得三維線段點云數據。

? ? ?? （3）通過場景的三維結構信息，去除三維平面和三維線段的異常點云，最后合并所有三維線段點云數據。

II. ALGORITHM?

A. Point Cloud Segmentation

? ? ? ? 分割是自動處理點云的最重要的預處理步驟之一，在過去的幾十年中已經進行了深入研究。通常，所提出的點云分割方法可以分為三大類：基于邊緣/邊界，基于區域增長和混合（請參閱[15]以進行閱讀）。為了從點云中獲得平面分割，像[16]這樣的傳統方法僅在點云水平上執行區域增長會對參數過于敏感。（新的方法）一種魯棒性很好的方法是先提取小的緊湊區域，然后合并這些區域以獲得最終結果。基于此，我們的方法分三個步驟將輸入點云分割成多個平面：法線計算，區域增長和區域合并。

? ?? 法線計算：給定一些無序點云集，使用KNN（K Nearest Neighbour）算法去查找每一個點的近鄰并使用PCA算法估計近鄰表面的法線[17]，首先通過使用nanoflann庫建立k-d tree，然后對于每一個點我們使用下列公式計算他的協方差矩陣：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

上式中Σ表示3x3的協方差矩陣，是臨近的數據點，表示KNNs的平均向量（每一個P都是三維XYZ）。通過奇異值分解（SVD）求解以下標準特征值方程，最終可以得到該點的法線，該法線是在特征向量V矩陣中的第三個特征向量（此處應該是進行排序后的特征值所對應的特征向量）。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

上式中V是特征向量矩陣，λ是特征值矩陣。需要注意的是矩陣λ中的表示點的曲率值，的值越小，對應該點的的曲率值就越小。此外，因為數據點的KNNs已經獲得，我們能很簡單估計在鄰域范圍內點的分布尺度，簡單的來說，我們定義的尺度為和它的第三個近鄰點之間的距離。（第三個近鄰點）我們分別用、、和表示法線、曲率、尺度和和點的KNNS點集。

區域生長：給定每一個點點Pi的{npi，λpi，spi，Ipi}，區域增長過程旨在提取輸入點云中的所有平面，其執行過程如下：（1）將所有點按照曲率進行升序排列。（2）從曲率最小的排在前邊的未處理的點Ps開始，我們創建一個列表T來存儲所有和Ps共面的點，其中Ps是第一個。在T中對于每一個未處理的點Pi，在他的鄰域Ipi中我們遍歷每一個未處理的點Pj，如果滿足以下條件，將Pj添加到列表T中：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
在上述式子中，θ=15°是一個常量角度閾值，tho=Sps是正交距離閾值，thp=50Sps是平行距離閾值。tho和thp都根據Ps的大小進行自適應。第一個和第二個條件確保Pj與Ps共面，而第三個條件確保區域緊緊圍繞Ps（即該區域緊密的位于Ps周圍。）一旦Ipi內所有的點都被遍歷，我們將Pi標記為已處理。該區域逐點增長，直到處理了列表T中的所有點，其結果是一個平面區域，其所有點都存儲在列表T中。（3）重復執行第二步，直到處理完所有點。 所獲得的所有平面區域的集合表示為R。

? ? ? ? 區域合并：提出的區域合并策略包含以下三步。（1）首先，對于每一個區域Ri如法線計算中所介紹的，我們以相同的方式使用其所有點為其擬合一個平面，法線，曲率，Ri的分布規模分別表示為npi，λpi，spi。另外，對于點云中的每個點，我們為其分配一個標簽，這是它所屬區域的一個索引。（2）之后，我們遍歷每一個區域，來獲得他的鄰域區域。在一個區域Ri中的每一個點Pm，我們遍歷該點的鄰域IPm中的所有點。如果在Ipm中有一個點PN他的標簽不同于Pm所屬的標簽（意思就是自己的鄰域點標簽跟自己的標簽不同）（這里的標簽怎么設置的），我們就認為Pn是一個邊界點，把Pn所在的那個平面作為一個鄰接區域Ri。按照這樣的方式，對于R中的每一個區域，我們都獲得他的臨界區域。（3）最后，最后，類似于上面介紹的區域生長過程，我們嘗試以相同的方式聚合共面區域，這與以前的區域生長過程在以下兩個方面有所不同：（1）使用相鄰區域而不是每個點的鄰域；（2）第三個條件不再使用。 之后，我們以第一步中所介紹的，使用相同的方式為每個合并區域擬合一個平面。

點云分割程序的結果是個平面集合，其中平面的法線nΠ和每個平面中的所屬點都可以獲得。

B.基于平面的3D線段檢測

? ? ? ? 給定提取的3D平面，我們執行以下三步來提取3D線段（如圖2所示）。（1）3D到2D的投影：對于每一個平面，將屬于他的點正射的投影到它自身的平面上，然后通過網格化過程將其平面所屬點通過平面自身確定的自適應參數轉換為二進制圖像。（2）2D線段檢測：首先從二值圖像中提取輪廓，然后通過最小二乘法擬合線段。（3）2D-3D重新投影：將檢測到的2D線段重新投影到3D平面上以獲得對應的3D線段。（下面就是括號123的具體展開解釋）

1）3D到2D的投影：對于在上述獲得的3D平面Π，我們的目標旨在將其從3D轉換為2D，以形成二進制圖像，從中可以有效地檢測2D線段。 3D-2D投影按以下方式進行，圖3中也對此進行了說明。

首先，計算屬于該平面的所有點的平均值作為平面Π的中心點Pc，然后在TΠ（屬于平面Π的所有點）中我們投影第一個點（第一個點表示為P0）到平面上，并將相應的投影點表示為P0'。之后，我們將向量PcP0'設定為x軸，從Pc到P0'標記為正方向，x軸的正方向表示為Vx，這樣y軸我們就可以計算出來，vy=vx x nΠ。具有了中心點，Pc，x軸和y軸的正方向，按照如下某一個點Pi在二維平面中的坐標就很容易計算出來：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

對于TΠ中的每一個點，我們都可以通過公式4計算他的2D平面坐標，我們也能夠獲得這個平面的尺度SΠ，我們還可以得到平面的比例尺sΠ，根據經驗將其定義為0.75 {Sp} 0.9，其中{Sp}是在TΠ中點升序排列的規模集合，{Sp} 0.9表示在這個集合中第90%的值。給定二維平面點{(xi,yi)}和平面規模，然后，我們可以通過網格化將這些點轉換為二進制圖像，方法如下。

對于一個平面，首先，可以獲得所有2D平面點的x和y坐標的最小值和最大值，將其分別表示為xmin，xmax，ymin，ymax。然后我們可以用公式寬[(xmax-xmin)/SΠ]+1，公式高[(ymax-ymin)/SΠ]+1創建一個二值影像。可以通過以下計算每一個2D平面點(xi,yi)的像素坐標（ui,vi）：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

對于從2D平面點轉換得到的像素，我們將灰度值設置為255，其余像素的灰度值設置為0。通過這種方式，我們實現了3D平面到2D二值影像轉換的目標。在實際應用中，原始二值圖像上可能會存在一些小孔，這是由于某些點之間的距離可能大于sΠ。增大sΠ的值可以在很大程度上消除這些孔，但是，這將降低二進制圖像的分辨率。經過大量實驗，我們發現一種更合理的方法是在原始二值圖像上應用膨脹，然后使用默認的3×3內核進行腐蝕。 圖2（a）顯示了膨脹和腐蝕后的結果，它不僅保持了原始圖像的分辨率，而且彌補了大多數孔洞。

? ? ? ? ? ? ? ? ? ? ??

2）2D線檢測：像圖2(a)一樣給定二值影像，然后，我們可以使用線段檢測器（例如LSD [1]和CannyLines [3]）輕松地從中提取2D線段。 兩者都可以產生良好的線段檢測結果，但是，在實踐中，我們發現外形輪廓檢測后再進行最小二乘線段擬合程序是最靈活有效的方法。首先，對于線段擬合的誤差可以調整。 此外，可以保留平面上線段之間的拓撲信息，這對于接下來的后期處理以消除線段離群值非常有用。 因此，我們通過以下步驟檢測2D線段：

首先，通過調用OpenCV中的finndContours函數可以找到外形輪廓。然后，由于一些外形信息不可能含有有用的線段，因此將輪廓小于40像素的那些外形輪廓刪除。之后，按照[3]中介紹的相同方式將每個有用的輪廓劃分為直線段，然后通過最小二乘擬合方法進行擬合線段。圖2（b）示出了圖2（a）的線段檢測結果，其中不同的線段以不同的顏色標記。

3）2D-3D的重新投影：給定從二進制圖像中提取的2D線段，我們就可以通過2D-3D重新投影獲得相應的3D線段，這是3D-2D投影的逆過程，包含以下兩個步驟：（下面是從3D到2D，再從2D到pixel）（1）就是從圖像Pixel到2D平面點：從圖像像素到2D平面點：對于每個末端坐標為像素（ui，vi）的線段，我們通過等式5的逆過程將它們轉換為2D平面坐標（xi，yi）。（3）從2D平面點到3D點：對于每一個2D平面點（xi,yi），我們可以通過公式4的逆過程計算2D點對應的3D點坐標，用這樣的方法，我們就可以獲得3D平面上的所有3D線段如圖3（c）所示。最后，對每個3D平面執行此過程，我們可以在輸入點云中獲得所有3D線段。

C.后期處理

? ? ?? 在上述過程中，為確保沒有有用的場景信息丟失，(為確保有用的場景信息都被保留)，在Section Ⅱ-B2中，只有短的外形輪廓被消除。因此，獲得的初始3D線段包含許多離群值（因為只是刪除了一些短的線段）。為了去除這些離群點，確保檢測結果是完整的。因此本節將介紹魯棒性和有效性的后處理程序。

? ? ? ? 正如我們上述所介紹的，對于2D線段的檢測，我們首先提取外形輪廓，然后從每一個外形輪廓上擬合線段，來代替直接從輸入圖像上進行線段檢測。這種策略保留了線段的拓撲結構信息，這種策略保留了線段的拓撲信息，也就是說，我們可以從平面→輪廓→線段獲得層次關系。基于這個層次關系，我們提出了后處理策略，該策略比在單個線段上處理的方法要魯棒性強大得多。 我們的后處理包含兩個步驟：離群點去除和線段合并。

離群點去除：基于觀察法線內點線段通常顯示出例如平行度和正交性之類的結構信息，我們提出去利用局部結構信息來去除離群點，其操作如下。（1）首先，我們剔除3D平面的離群點。對于每一個3D平面Π，該平面內所有的3D線段根據他們的長度進行降序排列，最長線段被認為是第一個集群參考線。然后，從最前面的未聚類線段開始，如果他的參考線對于Li有一個10°以內的方向偏差，每個未聚類的3D線段（表示為Li）被認為屬于該聚類。如果Li與任何參考線段之間的方向偏差都大于30°，則我們將創建一個新的聚類，并以Li作為其參考線段。重復執行此過程，直到平面Π上的所有3D線段都被處理。 計算每個聚類的線段長之和，然后用于對這些聚類進行降序排列。通常，如果3D平面是常規平面，例如建筑物的外墻和窗戶，則會有很強的結構信息，例如平行度和正交性，而那些離群的平面（例如樹和蔬菜）通常不會顯示此類結構信息。 因此，我們提出了一個標準來輕松判斷一個3D平面是否為外點：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

在上述公式中，其中l（c1）和l（c2）分別是最前面的簇和第二個簇的線長之和，l（all）是在平面Π上所有的3D線段長度。應該注意的是，將最前邊的和第二個聚類的方向定義為平面Π的結構方向。

（2）然后，我們通過3D線段所屬的外形輪廓來去除其外點。我們的策略基于以下觀察結果：如果輪廓是結構化的，那么丟棄異常值的長度閾值thl應該很小，否則如果非結構化應使用較大的長度閾值。因此，對于一個平面Π，首先，我們遍歷其所有的3D線段來查找出結構線段，這些線段定義為方向相對于Π的任何一種結構方向都在誤差（使用10°）范圍內。然后，將輪廓外形的結構線比率t定義為結構線的長度除以輪廓外形上所有線的長度。給定結構線比t和平面的尺度（SΠ），我們的策略如下：

線段合并：建議使用線合并程序來合并彼此距離過近的3D線段，這樣最終結果將更加清晰。線段合并步驟如下。 首先，按照asin（z）計算3D線段每個線段內點的緯度，其中z是線段的歸一化方向還是法線方向的z分量。然后使用bin步長為6°為所有內點構建直方圖。之后，所有的inlier根據它們的長度排序。從最前邊的未經處理的3D線段Li開始，我們在Li bin中沿著左bin和右bin去遍歷每個3D線段Lj去找到滿足以下條件的線假設：

Ⅲ.實驗結果

我還得回頭再看看。

?

?

?

總結

以上是生活随笔為你收集整理的Paper2：Fast 3D Line Segment Detection From Unorganized Point Cloud的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。