3D 平面拟合算法 [英] 3D Plane fitting algorithms
问题描述
所以我正在做一个项目，我和我的一个朋友使用 KINECTv2 扫描了一个房间并用它制作了一个 3D 模型.目标是可以实时添加不同种类家具的 3d 模型.为了这个目标，我正在尝试不同的平面拟合算法，以便找到最快的算法.有人有什么建议吗?到目前为止，我只研究了PCL中包含的基本RANSAC算法的用法.
平面拟合的两种常用方法是 RANSAC 和 Hough.这是一项性能比较:
https://www.researchgate.net/publication/259519997_Continuous_data_point_ondetect_a_continuous_data_on_Hough_A/p> 与计算几何和图像处理中的许多问题一样，与其考虑最快"，不如考虑在性能、开发工作和成本方面最适合您的应用程序.寻找最快的算法可能会让你走上一条成本和复杂性都令人震惊的道路，而你可能能够实现一个由相对简单的算法组成的数据处理链，这些算法运行得足够快，为用户提供流畅和愉快的体验. 长话短说，我建议从 Hough 平面贴合开始.霍夫变换算法相对容易编写(一旦掌握了基础知识)，调整参数也很直观. https://en.wikipedia.org/wiki/Hough_transform 编写自己的算法的原因之一是，一旦(而不是如果)发现点云数据比原先的数据更嘈杂且表现不佳，您将能够更好地了解需要进行哪些更改喜欢. 实现良好的速度将取决于许多因素，包括: 预处理.您不需要将任意大小的平面拟合到任意点云:相反，您需要拟合墙壁，也许还有地板和天花板.对于 Hough 算法，这意味着您可以限制测试参数的范围，从而加快处理速度. 与其尝试为完整的原始点云找到所有平面拟合，不如找到将点云分解为子云集群的方法，从而可以更有效地运行平面拟合测试. PCL 可以为您计算表面法线.如果您可以识别指向大致相同方向的表面法线簇，然后尝试对各个簇进行平面拟合，您应该能够大大加快速度. 此外，对于您的第一次通过，您可能希望对数据进行下采样并尝试在相对较少的点上拟合.这类似于为 2D 处理创建图像金字塔". 八叉树是一种很好的、简单的划分查询、碰撞测试等空间的方法.八叉树将空间划分为八个节点或八分圆".这可以想象为将一个立方体切成八个更小的立方体.然后将每个八分圆进一步划分为八个八分圆，以此类推.如果八分圆(一个节点)不包含点，则不需要进一步划分它. 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/) 开发了与您非常相似的东西描述.如果不出意外，您可以尝试一下他们的软件，并考虑可以改进/适应您的需求的内容. 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: 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屋！
