三維點云邊緣檢測和直線段提取進展與展望

倪　歡，張繼賢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.