3D平面拟合算法 [英] 3D Plane fitting algorithms
问题描述
因此，我正在一个项目中，我和我的一个好友使用KINECTv2扫描了一个房间，并从中制作了3D模型。目的是使实时添加各种家具的3D模型成为可能。为了达到这个目标，我正在尝试不同的平面拟合算法，以便找到一种最快的算法。有人有什么建议吗？到目前为止，我仅研究了PCL中包含的基本RANSAC算法的用法。
平面拟合的两种常见方法是RANSAC和霍夫。这是一项性能比较：
与计算几何和图像处理中的许多问题一样，与其考虑最快， 从性能，开发工作量和成本方面考虑最适合您的应用的方案。搜索可能最快的算法可能会导致您走下一条令人恐惧的成本和复杂性的道路，而您也许能够实现相对简单的算法的数据处理链，这些算法的运行速度足够快，可以为用户提供流畅愉悦的体验。 p>
长话短说，我建议从霍夫飞机飞度开始。霍夫变换算法相对容易编写（只要您掌握了基础知识），并且调整参数很直观。
https://en.wikipedia.org/wiki/Hough_transform
写原因之一您自己的算法是，您一旦发现点云数据噪声较大且行为不如人们希望的那样，就可以更好地了解需要进行哪些更改（而不是如果发生一次）。
达到良好的速度将取决于许多因素，包括：
- 处理。寻找将点云分解为可以更快处理的块的方法。
- 参数化。预处理数据后，您可以为平面拟合算法定义更窄的搜索范围。例如，仅尝试在几度的垂直范围内进行平面拟合。您还需要选择参数以在速度和贴合质量之间找到平衡。
- 3D数据的质量。就其本身而言，这是一个很大的话题，您越早仔细研究数据中的问题越好。
- 实时的含义。即使对于涉及用户交互的3D图形应用程序，也要严格按照规范（以N帧/秒的速度进行更新）来实现实时性，而不是呈现一个流畅而简单的界面。
- 3D显示。另一个大话题。
预处理。
您不需要将任意大小的平面容纳到任意点云：相反，您需要调整墙壁以及地板和天花板的大小。对于霍夫算法，这意味着您可以限制测试参数的范围，从而加快处理速度。
与其尝试找到完整的原始点云的所有平面拟合，不如设法将点云分解为平面适合性测试可以将其细分为多个子云更有效地运行。
PCL可以为您计算表面法线。如果您可以识别出指向法线方向大致相同的聚类，然后尝试对各个聚类进行平面拟合，则应该可以使速度大大提高。
，对于您的第一次通过，您可能需要对数据进行下采样，然后尝试在相对较少的点进行拟合。这类似于为2D处理创建图像金字塔。
Octrees是很好的简单方法，可以为查询，碰撞测试等分配空间。八叉树将空间划分为八个节点或八分圆。可以想象这是将一个立方体切成八个较小的立方体。然后将每个八分圆进一步划分为八个八分圆，依此类推。如果八分圆（一个节点）不包含点，则无需进一步分割。
https://en.wikipedia.org/ Wiki / Octree
参数化。
上面的描述应该清楚地表明，如果可以通过以下方式预处理数据，简化和/或分解原始的原始点云，那么您将能够测试定义更狭窄的搜索，这些搜索将更快地运行。
您可能不需要平面拟合的高精度。您可以生成合理的拟合，然后调整这些拟合以生成彼此成直角的天花板，墙壁和地板。
3D数据质量。
strong>Kinect v2是一款飞行时间设备，存在一些固有的测量精度问题。例如，如果您拍摄一幅平坦的墙的图像，然后检查深度值，则会在图像的角落看到一些非平面的糊涂现象。如果您查看多幅图像中每个（x，y）像素的深度值的范围（或标准差），那么您还会注意到中心像素和边缘像素之间的噪点差异。
一旦执行了平面拟合，就生成对拟合质量的度量。这需要返回数据以计算用于计算的点的点到平面距离。 （为加快速度，仅使用每N个点或随机采样点。）在修改参数时，您会看到速度和拟合质量方面的效果。
实时vs.平滑平滑。
如果您只需要用户实时移动家具，则可以花更长的时间生成初始平面拟合。
多线程/并行性
要处理数据输入，平面拟合和用户界面，您几乎必须确定要认真考虑多线程。要测试算法，您确实需要在UI线程上工作，但这只是一个限制。
像这样的应用程序乞求CUDA或OpenCL。对于3D显示器，您还是要使用图形卡。尽管您不需要立即进入GPU编程，但要记住如何并行化算法会很有帮助。
3D显示。
您是否打算使用Direct3D或OpenGL进行3D显示和交互？实施允许用户实时添加各种家具的3D模型的软件，建议您必须依赖图形卡。
如果可以的话在3D视图中显示点云，也许您甚至不需要平面拟合。您甚至可以避开碰撞检测：如果椅子的3D模型撞到一簇点（即一堵墙），那么您可能只检测到该碰撞，而不是尝试拟合平面来定义边界。八分圆和其他空间划分技术将有助于加速碰撞测试。
Matterport公司（ http://matterport.com/ ）开发的内容非常类似于您所描述的内容。如果没有别的，您可以尝试使用他们的软件，并考虑可以针对您的需求进行改进/调整的地方。
So I'm working on a project where me and a buddy of mine scanned a room using the KINECTv2 and made a 3D model out of it. The goal is to make it possible to add 3d models of different kinds of furniture in real time. To that goal I'm trying out different plane-fitting algorithms in order to find wich one would work the fastest. Does anybody have any suggestions? So far I've only researched the usage of the basic RANSAC algorithm included in PCL.
Two common approaches for plane fitting are RANSAC and Hough. Here's one performance comparison:
As with many problems in computational geometry and image processing, rather than consider what is "fastest," consider what is optimal for your application in terms of performance, development effort, and cost. Searching for the fastest possible algorithm could lead you down a path of horrifying cost and complexity, whereas you may able to implement a data processing chain of relatively simpler algorithms that run just fast enough to present a smooth and pleasant experience to the user.
Long story short, I recommend starting with a Hough plane fit. Hough transform algorithms are relatively easy to write (once you grasp the basics), and tweaking parameters is intuitive.
https://en.wikipedia.org/wiki/Hough_transform
One of the reasons to write your own algorithm is that you'll be in a better position to understand what changes need to be made once (not if) you discover the point cloud data is noisier and less well behaved than one would like.
Achieving good speed is going to rely on a number of factors, including these:
- Point cloud pre-processing. Look for ways to break up the point cloud into chunks that can be processed more quickly.
- Parameterization. Once data is preprocessed, you can define narrower search bounds for your plane fit algorithm. For example, only try plane fits within a few degrees of vertical. You'll also need to choose parameters to find a balance between speed and quality of fit.
- Quality of the 3D data. That's a big topic by itself, and the sooner you can take a close look at the problems in the data the better.
- What "real time" means. Even for 3D graphics applications that involve user interaction, achieving real time based strictly on specs (updates at N frames/second) may be less important than presenting a smooth and simple interface.
- Multithreading and parallelism.
- 3D display. Another big topic.
Pre-processing. You don't need to fit planes of arbitrary size to arbitrary point clouds: instead, you need to fit walls and maybe floors and ceilings. For Hough algorithms this means you can limit the range over which parameters are tested, and hence speed up processing.
Rather than try to find all the plane fits for the complete, original point cloud, find ways to break up the point cloud into clusters of subclouds to which plane fit tests can be run more efficiently.
PCL can calculate surface normals for you. If you can identify clusters of surface normals pointed in roughly the same direction, and then try plane fits for individual clusters, you should be able to speed things up considerably.
Also, for your first pass you'll probably want to downsample your data and try fits on relatively fewer points. This is analogous to creating an "image pyramid" for 2D processing.
Octrees are nice, simple means of dividing up space for queries, collision tests, and so on. An octree divides a space into eight nodes or "octants." This can be imagined as cutting a cube into eight smaller cubes. Then each octant is further divided into eight octants, and so on. If an octant (a node) doesn't contain points, you don't need to divide it further.
https://en.wikipedia.org/wiki/Octree
Parameterization. The descriptions above should make it clear that if you can preprocess the data by simplifying and/or breaking up the original raw point cloud, then you'll be able to test much more narrowly defined searches that will run more quickly.
For that matter, you probably don't need high accuracy in plane fits. You can generate reasonably good fits, then tweak those fits to generate ceilings, walls, and floors at right angles to each other.
3D data quality. The Kinect v2 is a time-of-flight device with some inherent measurement accuracy problems. For example, if you take a single image of a flat wall and then check the depth values, you'll notice some non-planar goofiness in the corners of the image. If you take a look at the range (or standard deviation) of depth values at each (x,y) pixel over multiple images, then you'll also notice differences in noisiness between center pixels and edge pixels.
Once you perform a plane fit, generate a measure of the fit quality. This requires going back through the data to calculate point-to-plane distances for the points used for calculation. (To speed this up, only use every Nth point or randomly sample the points.) As you tinker with parameters you'll see the effects in terms of speed and fit quality.
Real time vs. Perceptibly smooth. If you only need the user to move furniture around in real time, it should be okay to spend longer generating the initial plane fits.
Multithreading/Parallelism To handle data input, plane fitting, and user interface you'll almost certain have to think hard about multithreading. To test algorithms you do work on the UI thread just to get started, but this is limiting.
An application like this begs for CUDA or OpenCL. For the 3D display you'll be using the graphics card anyway. Although you don't need to jump into GPU programming right away, it's helpful to keep in mind how algorithms could be parallelized.
3D display. Were you planning to use Direct3D or OpenGL for 3D display and interaction? Implementing software to allow the user to "add 3d models of different kinds of furniture in real time" suggests you'll have to rely on the graphics card.
If you can display the point cloud in a 3D view, maybe you don't even need plane fits. You might even get away with collision detection: if the 3D model of a chair bumps into a cluster of points (i.e. a wall), then you might just detect that collision rather than try to fit planes to define bounds. Octants and other space-dividing techniques will help speed up collision tests.
The company Matterport (http://matterport.com/) has developed something very much like what you're describing. If nothing else you can give their software a try and consider what might be improved/adapted for your needs.
这篇关于3D平面拟合算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
