3D平面擬合算法

Question

因此，我正在開展一個項目，在該項目中，我和我的一個好友使用KINECTv2掃描了一個房間，並製作了一個3D模型。目標是使實時添加不同種類傢俱的三維模型成爲可能。爲了達到這個目標，我嘗試了不同的平面擬合算法，以便找到最適合的算法。有人有任何建議嗎？到目前爲止，我只研究了PCL中包含的基本RANSAC算法的用法。

Answer 1

平面擬合的兩種常見方法是RANSAC和Hough。這裏有一個性能對比：

https://www.researchgate.net/publication/259519997_Continuous_plane_detection_in_point-cloud_data_based_on_3D_Hough_Transform

與計算幾何和圖像處理許多問題，而不是考慮什麼是「最快的，」考慮什麼是最適合在性能，開發難度方面的應用，併成本。搜索儘可能快的算法可能會導致成本和複雜性降低，而您可能會實現一個相對簡單的算法的數據處理鏈，其運行速度足以爲用戶帶來流暢愉快的體驗。長話短說，我建議先從哈夫飛機起飛。 Hough變換算法相對容易編寫（一旦掌握了基礎知識），並且調整參數是直觀的。

https://en.wikipedia.org/wiki/Hough_transform

一個寫自己的算法的原因是，你可以更好地瞭解需要進行一次（如果沒有），你發現的點雲數據是嘈雜和什麼樣的變化表現不如人意。

實現良好的速度將依賴於多種因素，其中包括：

• 點雲預處理。尋找方法將點雲分解成可以更快處理的塊。
• 參數化。一旦數據被預處理，您可以爲您的平面擬合算法定義更窄的搜索範圍。例如，只有嘗試平面適合幾度垂直。您還需要選擇參數以在速度和適合質量之間找到平衡點。
• 3D數據的質量。這本身就是一個很大的話題，你越早可以更好地仔細研究數據中的問題。
• 「實時」意味着什麼。即使對於涉及用戶交互的3D圖形應用程序，嚴格按照規格實現實時（以N幀/秒更新）也可能不如呈現平滑和簡單的界面那麼重要。
• 多線程和並行。
• 3D顯示。另一個重大話題。

預處理。 您不需要將任意大小的平面適合任意點雲：相反，您需要適合牆壁，也許需要地板和天花板。對於Hough算法，這意味着您可以限制參數測試的範圍，從而加快處理速度。

與其試圖找到完整的原始點雲的所有平面擬合，不如找到將點雲分解爲可以更有效地運行平面擬合測試的子云的羣集的方法。

PCL可以爲您計算表面法線。如果您可以識別指向大致相同方向的表面法線集羣，然後嘗試對單個集羣進行平面擬合，則您應該可以大幅提高速度。

另外，爲了您的第一遍，您可能需要對數據進行縮減採樣，並嘗試使用相對較少的點。這與爲2D處理創建「圖像金字塔」類似。

Octrees很好，簡單的方法是分隔查詢空間，碰撞測試等等。八叉樹將空間分成八個節點或「八分圓」。這可以想象爲將立方體切割成八個較小的立方體。然後每個八分圓被進一步分成八個八分圓，等等。如果八分圓（節點）不包含點，則不需要進一步分割它。

https://en.wikipedia.org/wiki/Octree

參數。 上面的描述應該清楚地表明，如果您可以通過簡化和/或分解原始原始雲來預處理數據，那麼您將能夠測試更加狹義定義的搜索，從而更快地運行。

對於這個問題，你可能不需要高精度的平面擬合。你可以產生相當好的配合，然後調整那些適合產生彼此成直角的天花板，牆壁和地板。

3D數據質量。 Kinect v2是一款飛行時間設備，具有一些固有的測量精度問題。例如，如果您拍攝單一平面牆的圖像，然後檢查深度值，則會在圖像的角落發現一些不平整的陰影。如果您查看多個圖像上每個（x，y）像素的深度值範圍（或標準差），則您還會注意到中心像素和邊緣像素之間的噪聲差異。

一旦您執行了平面擬合，生成一個適合質量的度量。這需要通過數據回溯計算用於計算的點的點到面距離。 （爲了加快速度，只能使用每個第N個點或隨機抽樣點。）當您修改參數時，您將看到速度和適合質量方面的效果。

實時與平穩對比。 如果您只需要用戶實時移動傢俱，則可以花費更長時間來生成初始平面配合。

多線程/並行 要處理的數據輸入，平面擬合，以及用戶界面你幾乎一定要好好想想多線程。要測試你在UI線程上工作的算法，只是爲了開始，但這是有限的。

像這樣的應用程序需要CUDA或OpenCL。對於3D顯示器，您仍將使用圖形卡。雖然您不需要立即跳入GPU編程，但請記住算法是如何並行化的，這很有幫助。

3D顯示。 您是否打算使用Direct3D或OpenGL進行3D顯示和交互？實施軟件以允許用戶「實時添加不同種類傢俱的3D模型」表明您必須依賴顯卡。

如果您可以在3D視圖中顯示點雲，也許您甚至不需要平面擬合。你甚至可能逃避碰撞檢測：如果椅子的3D模型撞到一組點（即牆），那麼你可能只是檢測到碰撞，而不是試圖擬合平面來定義邊界。八分器和其他空間分割技術將有助於加速碰撞測試。

公司Matterport（http://matterport.com/）已經開發出非常類似於您所描述的內容。如果沒有別的，你可以試試他們的軟件，並考慮哪些可以改進/適應你的需求。

Answer 2

我很欣賞Rethunk的詳細評論，並提供了局部霍夫變換的變體。但首先，讓我指出在平面檢測或相交平面檢測中存在一堆stackoverflow/stackexchange帖子。他們有些是：

• Fit a plane to a 3D point cloud in C++
• difference between plane segmentation and plane fitting
• Plane fitting in a 3d point cloud
• Fit a plane to 3D point cloud using RANSAC
• Fast plane fitting to many points
• https://math.stackexchange.com/questions/1657030/fit-plane-to-3d-data-using-least-squares
• Best fit plane for 3D data

我會建議的方法進行了詳細的解釋publication at 3DV 2015：

局部Hough變換的3D原始檢測， 伯特倫·德羅斯特，斯洛博丹·伊利奇，IEEE的3D Vision 2015年

這個想法是基於選擇兩個面向對的點。比較這些點的方向，以確定點是否共同位於飛機上。所有這些點對的貢獻被組合在局部投票空間中，其中飛機在0維投票空間中被參數化（一個定向點完全確定飛機）。該技術可擴展到不同的基元。

RANSAC一般不如霍夫變換，但所提出的方法可以被看作是全局投票方案和RANSAC之間的混合。雖然RANSAC選擇多個隨機點，足以擬合目標基元，但所提出的方法僅選擇一個點即參考點。

我也有another stackexchange post解釋如何可能開發一個類似的方法正交飛機。