三维点云边缘检测和直线段提取进展与展望

倪　欢，张继贤1，林祥国1

（1.中国测绘科学研究院摄影测量与遥感研究所，北京100830；2.武汉大学资源与环境科学学院，湖北武汉430079）

三维点云边缘检测和直线段提取进展与展望

倪欢1，2，张继贤1，林祥国1

（1.中国测绘科学研究院摄影测量与遥感研究所，北京100830；2.武汉大学资源与环境科学学院，湖北武汉430079）

从图像中提取边缘和直线段是计算机视觉研究的热门主题，近年来，随着三维点云数据质量的不断提高，从三维点云数据中提取边缘和直线段得到了很多学者的关注，已取得了一些研究成果。本文探讨了从三维点云数据中检测边缘和提取直线段的基本思想，对已有的方法和研究现状进行了较全面的综述，介绍了具有代表性的三维点云边缘检测与直线段提取方法，并对各个方法的特点和缺陷进行了分析，最后对三维点云边缘检测与直线段提取研究的前景进行了展望。

三维点云；边缘检测；直线段提取；总结；展望

特征提取作为图像分析和计算机视觉的重要研究领域，已经得到了很多学者的关注和研究［1］。边缘和直线段作为这些特征的重要组成部分，不仅广泛存在于二维图像中，还存在于各种场景（尤其是含有大量人工建筑物的城市场景）和单个地物的三维点云数据中。相比于点云，图像是一种更常见的数据类型；另外，由于受到传感器硬件的限制，过去的三维点云数据中地物的细节结构，尤其是边缘，通常有所缺失或模糊不清［2］。因此，目前大部分边缘检测与直线段提取方法是基于图像的，而且相关的方法已经相对成熟。

在二维图像处理领域，边缘被定义为“两个连续像素亮度区域的相交位置”［3］或“图像像素属性（一般指亮度）的突变”［4］。学者们已经提出了大量的边缘检测算法，如 Canny算子［5］和 Edison算子［6］。经典的边缘检测算法的综述文章可参考文献［1］。另外，二维图像直线段提取方面，文献［7］利用Hough变换提取直线段；文献［8—9］首先确定直线支撑区域，进而提取直线段。

近年来，随着激光雷达传感器硬件水平的飞速发展，点云的密度和空间分辨率得到了显著提高，可以充分反映地物的细节结构信息，使从三维点云数据中提取三维边缘及直线段成为可能，三维点云边缘检测和直线段提取成为一个新兴的研究方向。但是目前，由于相关研究处于起步阶段，一些方法尚处于探索阶段，且三维点云数据边缘的定义也不明确。因此，有必要对三维点云数据边缘进行定义。本文结合现有文献中有关三维点云中边缘的论述，以及图像处理中边缘的定义，将三维点云边缘定义为如下两类边缘:①表面轮廓:包括深度不连续边缘线［10］、地物表面轮廓线（如建筑物屋顶轮廓）等；②表面相交边缘:包括面相交线［10］、封闭锐利边缘［11］等由不同表面相交形成的边缘。

由此可见，从本质上讲，二维图像边缘与三维点云边缘对应的地物目标是相同的。但是二维图像边缘检测算法并不能直接应用于三维点云数据，主要有以下原因:

1）三维点云数据通常只具备 X、Y、Z坐标信息。

2）三维点云数据所包含的空间信息多于二维图像，其对应几何结构更复杂。

3）无组织三维点云数据邻域结构非常复杂，且因检索方式不同而存在很大差别。

虽然三维边缘检测遇到以上难题，但三维点云相比于图像而言，具备更多的空间维度信息。本文以三维点云数据的特点为线索，对三维点云数据边缘检测及直线段提取的基本思想和方法进行探讨，对近年来三维边缘与直线段提取的研究现状进行分析和总结，并针对该研究的进一步发展加以分析和展望。

一、相关研究

三维点云中进行边缘检测及直线段提取的方法可以分为两类:第一类方法借助于与点云相对应的二维图像或将三维点云转化为图像，再利用图像处理提取二维边缘或直线段，进一步与三维点云数据相对应，从而提取三维边缘或直线段特征，称为“间接法”；第二类方法则直接作用于三维点云数据来提取三维边缘或直线段特征，称为“直接法”。以下对两类特征的两类提取方法进行详细讨论。由于目前提出的边缘检测算法较多，本文利用图1来进行辅助描述。

图1　三维点云边缘检测方法

1.三维边缘检测

（1）间接法

该类方法首先在图像中提取二维边缘，再与相应三维点云数据对应以提取三维边缘［12-16］。其中，文献［12］首先在三维点云对应的二维图像以及由点云生成的距离图像中检测二维边缘，然后与原三维点云数据相对应，再合并多组边缘点，作为检测到的三维点云边缘；文献［13］利用三维点云对应的二维图像进行边缘检测，并利用三维点云中提取的屋顶模型来确定图像边缘追踪区域，然后与三维点云对应以确定初始边缘点，再通过数学形态学方法优化并提取三维点云边缘；文献［14］首先在三维点云中利用高程差异来提取粗糙边缘，然后将这些粗糙边缘投影到图像空间进行精细边缘提取，进而提取三维点云中的精细边缘；文献［15］利用单景三维点云数据和单幅图像进行匹配，然后在图像中进行边缘检测并与点云对应；文献［16］将机载激光点云中的建筑物屋顶点转化为二值图像，再利用二值图像边界检测方法提取屋顶轮廓。

从该类中不同学者所提出的方法和思想来看，该类方法又可以细分为两个子类:第一子类方法以文献［12—13，16］为代表，需要将三维点云数据转化成二维图像；第二子类方法以文献［14—15］为代表，无需将三维点云向二维图像转化，但需要将图像与三维点云数据进行配准以确定精确的特征对应关系。

由于从图像中进行边缘检测的方法比较成熟，可以提取各类边缘特征，而且精度较高，因此，间接法具备一定优势。但是，三维点云中所包含的几何信息要多于图像，用图像边缘来表征点云边缘，势必忽略了三维点云的几何优势。再者，一些方法需要将三维点云转化为二维图像，这样三维到二维的转换所造成的信息损失会格外严重。

（2）直接法

该类方法直接从三维点云中提取边缘［10-11，17-22］。其中，文献［10］利用点云分割面片相交和深度不连续特征来检测面相交边缘与深度不连续边缘；文献［11］利用点云分割方法以及图理论检测封闭锐利边缘；文献［17］利用凸包算法检测建筑物屋顶轮廓；文献［18］利用椭圆邻域搜索来改进凸包算法从而提取更加紧致的多种形状建筑物轮廓；文献［19］利用高程差异来提取机载激光扫描点云数据边缘；文献［20］利用夹角限制来提取三维点云中建筑物立面边缘；文献［21］利用Gibbs能量模型、马尔科夫过程及数学形态学算子来提取三维点云中建筑物屋顶轮廓；文献［22］利用矩形来近似表达三维点云中建筑物屋顶轮廓。

参考三维点云数据中边缘的定义不难发现，在以上关于三维点云数据边缘检测的方法中，大部分是针对某一特定边缘而设计的。其中，一些方法旨在提取机载三维激光扫描点云中的建筑物屋顶轮廓［13-18，21-22］。文献［20］的方法旨在提取车载或地面激光扫描三维点云数据建筑物立面轮廓，文献［10］的方法旨在提取三维点云中的深度不连续边缘以及平面相交边缘。

此外，按不同的数据源展开分析，大部分研究均针对机载或地面三维激光扫描数据。对于工业逆向工程或小尺度物体模型的点云数据，学者们同样提出了一些边缘检测方法，如文献［23］从物体的表面网格数据中提取光滑特征线，文献［11］提取工业设备点云数据中的封闭锐利边缘，文献［24］利用傅里叶变换方法提取小尺度物体表面边缘。

目前，该类方法的自动化程度均很低，大多需要对原始的三维点云数据进行分割、目标识别等步骤，再根据某一特定目标检测边缘。

2.三维直线段提取

目前，从三维点云数据中提取直线段的研究还非常少见，仅有文献［10，25—27］以此为主题进行了探讨，4种方法的思路截然不同，但是，就是否借助图像处理方法而言，同样可以分为间接法与直接法两类。

（1）间接法

该类方法需要借助于图像处理［26-27］。文献［26］方法定义直线段为两个平面的相交线，进而定义直线支撑区域，并将三维点云数据根据不同的视点投影成多视图像，在多视图像中检测直线段并与三维点云数据相对应，从而提取直线段。然而，该方法提取的直线段不全面，只能提取平面相交线，对于规则平面的轮廓线则无能为力。文献［27］利用球面投影将三维点云数据转换成二维图像，利用二维图像边缘检测方法提取边缘，再利用霍夫变换提取直线段。

（2）直接法

该类方法无需借助图像处理方法，直接从三维点云数据中提取直线段［10，25］。文献［10］首先从三维点云数据中提取两类边缘，即深度不连续边缘和平面相交边缘，然后对边缘点利用协方差矩阵特征值分析方法进行分割，从而追踪到直线段边缘点，再拟合直线方程并提取直线段；该方法相对全面地给出了直接从三维点云数据中提取边缘以及直线段的处理流程，但是边缘检测不全面，并且，在边缘点追踪过程中，不能很好区分方向相同的临近直线，从而导致直线段提取错误和漏检现象。文献［25］结合RANSAC和马氏距离来检测三维直线段，但是，该方法只能检测出很少的直线段，不能满足后续研究的需要［26］。

3.存在的问题

通过以上对目前方法的总结与描述，其中边缘检测研究存在的问题如下:

1）很多方法要借助二维图像处理方法来提取点云边缘。然而，三维到二维的转换或利用二维表示三维会损失大量空间信息，会漏检一些三维边缘。

2）现有的大部分方法仅仅针对一种或两种边缘进行提取，大大限制了方法的应用。

3）很多方法仅适用于小尺度规则点云数据，对于大尺度、无组织、不规则且含有噪声的点云数据不能发挥效力。

4）现有方法的自动化程度较低，很多方法需要借助三维点云分割、目标提取等处理，然后针对特定目标提取边缘。

对于三维直线段提取，目前相关文献并不多见，需要进行探索的内容很多。并且，有些方法的提取效果很大程度上取决于边缘检测效果的优劣，加之三维点云数据边缘检测存在问题，因此漏检现象严重。

二、展 望

三维点云数据边缘检测与直线段提取已经取得了一定研究成果，但是仍然存在上述问题亟待解决。总体而言，在检测与提取过程中，自动化程度、算法效率、普适性、精确性等方面都有待提高。

特征提取的发展，向来离不开计算机视觉、模式识别和计算几何领域的相关研究。针对三维点云数据，计算几何领域的经典算法已经在边缘检测过程中得到了充分应用，如凸包算法［18］、图理论［11］等。此外，边缘与直线段特征通常与相应的三维几何结构相关联，这些三维几何结构的分解与表示在计算机视觉和模式识别领域已有相关研究，且已取得很大进展。如果充分利用这些相关学科领域的最新研究成果，必将大力推动三维点云边缘检测与直线段提取的发展。

［1］ ANDO S.Image Field Categorization and Edge/Corner Detection from Gradient Covariance［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（2）:179-190.

［2］ FROME A，HUBER D，KOLLURI R.Recognizing Objects in Range Data Using Regional Point Descriptors ［C］∥8th European Conference on Computer Vision. Prague:Czech republic，2004.

［3］ FREI W，CHEN C C.Fast Boundary Detection:A Generalized and a New Algorithm［J］.IEEE Transactions on Computers，1977，26（10）:988-998.

［4］ SHANMUGAM K S，DICKEY F M，GREEN J A.An Optimal Frequency Domain Filter for Edge Detection in Digital Pictures［J］.IEEE Transactions on Pattern A-nalysis and Machine Intelligence，1979，1（1）:37-49.

［5］ CANNY J.A Computational Approach to Edge Detection ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1986，8（6）:679-698.

［6］ MEER P，GEORGESCU B.Edge Detection with Embedded Confidence［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（12）: 1351-1365.

［7］ BALLARD D H.Generalizing the Hough Transform to Detect Arbitrary Shapes［J］.Pattern Recognition，1981，13（2）:111-122.

［8］ BURNS J B，HANSON A R，RISEMAN E M.Extracting Straight Lines［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1986，8（4）:425-455.

［9］ VON GIOI R G，JAKUBOWICZ J，MOREL J M，et al. LSD:A Fast Line Segment Detector with a False Detection Control［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（4）:722-732.

［10］ BORGES P，ZLOT R，BOSSE M，et al.Vision-based Localization Using an Edge Map Extracted from 3D Laser Range Data［C］∥ICRA.Anchorage，Alaska: ［s.n.］，2010.

［11］ DEMARSIN K，VAN DERSTRAETEN D，VOLODINE T，et al.Detection of Closed Sharp Edges in Point Clouds Using Normal Estimation and Graph Theory［J］.Computer-aided Design，2007（39）:276-283.

［12］ WANG Y，EWERT D，SCHILBERG D.Edge Extraction by Merging 3D Point Cloud and 2D Image Data［C］∥10th International Conference and Expo on Emerging Technologies for a Smarter World（CEWIT）.Melville，NY:［s.n.］，2013.

［13］ LI H，ZHONG C，HU X G.New Methodologies for Precise Building Boundary Extraction from LiDAR Data and High Resolution Image［J］.Sensor Review，2013，33 （2）:157-165.

［14］ LI Y，WU H，AN R.An Improved Building Boundary Extraction Algorithm Based on Fusion of Optical Imagery and LiDAR Data［J］.OPTIK，2013，124（22）:5357-5362.

［15］ CHEN Y M，ZHANG W M，ZHOU G Q.A Novel Building Boundary Reconstruction Method Based on Li-DAR Data and Images［C］∥5th International Symposium on Photoelectronic Detection and Imaging-Laser Sensing and Imaging and Applications.Beijing，China: ［s.n.］，2013.

［16］ POULLIS C.A Framework for Automatic Modeling from Point Cloud Data［J］.IEEE Transactions on Pattern A-nalysis and Machine Intelligence，2013，35（11）:2563-2575.

［17］ SAMPATH A，SHAN J.Building Boundary Tracing and Regularization from Airborne LiDAR Point Clouds［J］. PhotogrammetricEngineeringandRemoteSensing，2007，73（7）:805-812.

［18］ LEE J，HAN S，BYUN Y.Extraction and Regularization of Various Building Boundaries with Complex Shapes U-tilizing Distribution Characteristics of Airborne LiDAR Points［J］.ETRI Journal，2011，33（4）:547-557.

［19］ WANG R R，LAI X D，HOU W G.Study on Edge Detection of LiDAR Point Cloud［C］∥2011 International Conference on Intelligent Computation and Bio-Medical Instrumentation.Wuhan:［s.n.］，2011.

［20］ TRUONG-HONG L，LAEFER D F，HINKS T.Combining an Angle Criterion with Voxelization and the Flying Voxel Method in Reconstructing Building Models from LiDAR Data［J］.Computer-aided Civil and Infrastructure Engineering，2013，28（2）:112-129.

［21］ YANG B S，XU W X，DONG Z.Automated Extraction of Building Outlines from Airborne Laser Scanning Point Clouds［J］.IEEE Geoscience and Remote Sensing Letters，2013，10（6）:1399-1403.

［22］ SEO S Y，LEE J，KIM Y.Extraction of Boundaries of Rooftop Fenced Buildings from Airborne Laser Scanning Data Using Rectangle Models［J］.IEEE Geoscience and remote sensing letters，2014，11（2）:404-408.

［23］ HILDEBRANDT K，POLTHIER K，WARDETZKY M. Smooth Feature Lines on Surface Meshes［C］∥Proceedings of the Third Eurographics Symposium on Geometry Processing.Switzerland:［s.n.］，2005.

［24］ ALTANTSETSEG E，MURAKI Y，MATSUYAMA K，et al.Feature Line Extraction from Unorganized Noisy Point Clouds Using Truncated Fourier Series［J］.Visual Computer，2013，29（6-8）:617-626.

［25］ LU Z J，BAEK S，LEE S.Robust 3D Line Extraction from Stereo Point Clouds［C］∥IEEE Conference on Robotics，Automation，andMechatronics.Chengdu: ［s.n.］，2008.

［26］ LIN Y B，WANG C，CHENG J.Line Segment Extraction for Large Scale Unorganized Point Clouds［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2015（102）:172-183.

［27］ 张帆，高云龙，黄先锋，等.基于球面投影的单站地面激光点云直线段提取方法［J］.测绘学报，2015，44 （6）:655-662.

Edge Detection and Straight Line Segment Extraction from 3D-Point Clouds: Review and Prospect

NI Huan，ZHANG Jixian，LIN Xiangguo

10.13474/j.cnki.11-2246.2016. 0211.

P237

B

0494-0911（2016）07-0001-04

2015-07-15

国家自然科学基金（41371405）；基础测绘项目（A1506）

倪 欢（1989—），男，博士生，从事三维点云与遥感图像目标识别研究。E-mail:nih2015@yeah.net

引文格式：倪欢，张继贤，林祥国.三维点云边缘检测和直线段提取进展与展望［J］.测绘通报，2016（7）:1-4.