三維點(diǎn)云邊緣檢測和直線段提取進(jìn)展與展望

倪　歡，張繼賢1，林祥國1

（1.中國測繪科學(xué)研究院攝影測量與遙感研究所，北京100830；2.武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北武漢430079）

三維點(diǎn)云邊緣檢測和直線段提取進(jìn)展與展望

倪歡1，2，張繼賢1，林祥國1

（1.中國測繪科學(xué)研究院攝影測量與遙感研究所，北京100830；2.武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北武漢430079）

從圖像中提取邊緣和直線段是計(jì)算機(jī)視覺研究的熱門主題，近年來，隨著三維點(diǎn)云數(shù)據(jù)質(zhì)量的不斷提高，從三維點(diǎn)云數(shù)據(jù)中提取邊緣和直線段得到了很多學(xué)者的關(guān)注，已取得了一些研究成果。本文探討了從三維點(diǎn)云數(shù)據(jù)中檢測邊緣和提取直線段的基本思想，對已有的方法和研究現(xiàn)狀進(jìn)行了較全面的綜述，介紹了具有代表性的三維點(diǎn)云邊緣檢測與直線段提取方法，并對各個方法的特點(diǎn)和缺陷進(jìn)行了分析，最后對三維點(diǎn)云邊緣檢測與直線段提取研究的前景進(jìn)行了展望。

三維點(diǎn)云；邊緣檢測；直線段提??；總結(jié)；展望

特征提取作為圖像分析和計(jì)算機(jī)視覺的重要研究領(lǐng)域，已經(jīng)得到了很多學(xué)者的關(guān)注和研究［1］。邊緣和直線段作為這些特征的重要組成部分，不僅廣泛存在于二維圖像中，還存在于各種場景（尤其是含有大量人工建筑物的城市場景）和單個地物的三維點(diǎn)云數(shù)據(jù)中。相比于點(diǎn)云，圖像是一種更常見的數(shù)據(jù)類型；另外，由于受到傳感器硬件的限制，過去的三維點(diǎn)云數(shù)據(jù)中地物的細(xì)節(jié)結(jié)構(gòu)，尤其是邊緣，通常有所缺失或模糊不清［2］。因此，目前大部分邊緣檢測與直線段提取方法是基于圖像的，而且相關(guān)的方法已經(jīng)相對成熟。

在二維圖像處理領(lǐng)域，邊緣被定義為“兩個連續(xù)像素亮度區(qū)域的相交位置”［3］或“圖像像素屬性（一般指亮度）的突變”［4］。學(xué)者們已經(jīng)提出了大量的邊緣檢測算法，如 Canny算子［5］和 Edison算子［6］。經(jīng)典的邊緣檢測算法的綜述文章可參考文獻(xiàn)［1］。另外，二維圖像直線段提取方面，文獻(xiàn)［7］利用Hough變換提取直線段；文獻(xiàn)［8—9］首先確定直線支撐區(qū)域，進(jìn)而提取直線段。

近年來，隨著激光雷達(dá)傳感器硬件水平的飛速發(fā)展，點(diǎn)云的密度和空間分辨率得到了顯著提高，可以充分反映地物的細(xì)節(jié)結(jié)構(gòu)信息，使從三維點(diǎn)云數(shù)據(jù)中提取三維邊緣及直線段成為可能，三維點(diǎn)云邊緣檢測和直線段提取成為一個新興的研究方向。但是目前，由于相關(guān)研究處于起步階段，一些方法尚處于探索階段，且三維點(diǎn)云數(shù)據(jù)邊緣的定義也不明確。因此，有必要對三維點(diǎn)云數(shù)據(jù)邊緣進(jìn)行定義。本文結(jié)合現(xiàn)有文獻(xiàn)中有關(guān)三維點(diǎn)云中邊緣的論述，以及圖像處理中邊緣的定義，將三維點(diǎn)云邊緣定義為如下兩類邊緣:①表面輪廓:包括深度不連續(xù)邊緣線［10］、地物表面輪廓線（如建筑物屋頂輪廓）等；②表面相交邊緣:包括面相交線［10］、封閉銳利邊緣［11］等由不同表面相交形成的邊緣。

由此可見，從本質(zhì)上講，二維圖像邊緣與三維點(diǎn)云邊緣對應(yīng)的地物目標(biāo)是相同的。但是二維圖像邊緣檢測算法并不能直接應(yīng)用于三維點(diǎn)云數(shù)據(jù)，主要有以下原因:

1）三維點(diǎn)云數(shù)據(jù)通常只具備 X、Y、Z坐標(biāo)信息。

2）三維點(diǎn)云數(shù)據(jù)所包含的空間信息多于二維圖像，其對應(yīng)幾何結(jié)構(gòu)更復(fù)雜。

3）無組織三維點(diǎn)云數(shù)據(jù)鄰域結(jié)構(gòu)非常復(fù)雜，且因檢索方式不同而存在很大差別。

雖然三維邊緣檢測遇到以上難題，但三維點(diǎn)云相比于圖像而言，具備更多的空間維度信息。本文以三維點(diǎn)云數(shù)據(jù)的特點(diǎn)為線索，對三維點(diǎn)云數(shù)據(jù)邊緣檢測及直線段提取的基本思想和方法進(jìn)行探討，對近年來三維邊緣與直線段提取的研究現(xiàn)狀進(jìn)行分析和總結(jié)，并針對該研究的進(jìn)一步發(fā)展加以分析和展望。

一、相關(guān)研究

三維點(diǎn)云中進(jìn)行邊緣檢測及直線段提取的方法可以分為兩類:第一類方法借助于與點(diǎn)云相對應(yīng)的二維圖像或?qū)⑷S點(diǎn)云轉(zhuǎn)化為圖像，再利用圖像處理提取二維邊緣或直線段，進(jìn)一步與三維點(diǎn)云數(shù)據(jù)相對應(yīng)，從而提取三維邊緣或直線段特征，稱為“間接法”；第二類方法則直接作用于三維點(diǎn)云數(shù)據(jù)來提取三維邊緣或直線段特征，稱為“直接法”。以下對兩類特征的兩類提取方法進(jìn)行詳細(xì)討論。由于目前提出的邊緣檢測算法較多，本文利用圖1來進(jìn)行輔助描述。

圖1　三維點(diǎn)云邊緣檢測方法

1.三維邊緣檢測

（1）間接法

該類方法首先在圖像中提取二維邊緣，再與相應(yīng)三維點(diǎn)云數(shù)據(jù)對應(yīng)以提取三維邊緣［12-16］。其中，文獻(xiàn)［12］首先在三維點(diǎn)云對應(yīng)的二維圖像以及由點(diǎn)云生成的距離圖像中檢測二維邊緣，然后與原三維點(diǎn)云數(shù)據(jù)相對應(yīng)，再合并多組邊緣點(diǎn)，作為檢測到的三維點(diǎn)云邊緣；文獻(xiàn)［13］利用三維點(diǎn)云對應(yīng)的二維圖像進(jìn)行邊緣檢測，并利用三維點(diǎn)云中提取的屋頂模型來確定圖像邊緣追蹤區(qū)域，然后與三維點(diǎn)云對應(yīng)以確定初始邊緣點(diǎn)，再通過數(shù)學(xué)形態(tài)學(xué)方法優(yōu)化并提取三維點(diǎn)云邊緣；文獻(xiàn)［14］首先在三維點(diǎn)云中利用高程差異來提取粗糙邊緣，然后將這些粗糙邊緣投影到圖像空間進(jìn)行精細(xì)邊緣提取，進(jìn)而提取三維點(diǎn)云中的精細(xì)邊緣；文獻(xiàn)［15］利用單景三維點(diǎn)云數(shù)據(jù)和單幅圖像進(jìn)行匹配，然后在圖像中進(jìn)行邊緣檢測并與點(diǎn)云對應(yīng)；文獻(xiàn)［16］將機(jī)載激光點(diǎn)云中的建筑物屋頂點(diǎn)轉(zhuǎn)化為二值圖像，再利用二值圖像邊界檢測方法提取屋頂輪廓。

從該類中不同學(xué)者所提出的方法和思想來看，該類方法又可以細(xì)分為兩個子類:第一子類方法以文獻(xiàn)［12—13，16］為代表，需要將三維點(diǎn)云數(shù)據(jù)轉(zhuǎn)化成二維圖像；第二子類方法以文獻(xiàn)［14—15］為代表，無需將三維點(diǎn)云向二維圖像轉(zhuǎn)化，但需要將圖像與三維點(diǎn)云數(shù)據(jù)進(jìn)行配準(zhǔn)以確定精確的特征對應(yīng)關(guān)系。

由于從圖像中進(jìn)行邊緣檢測的方法比較成熟，可以提取各類邊緣特征，而且精度較高，因此，間接法具備一定優(yōu)勢。但是，三維點(diǎn)云中所包含的幾何信息要多于圖像，用圖像邊緣來表征點(diǎn)云邊緣，勢必忽略了三維點(diǎn)云的幾何優(yōu)勢。再者，一些方法需要將三維點(diǎn)云轉(zhuǎn)化為二維圖像，這樣三維到二維的轉(zhuǎn)換所造成的信息損失會格外嚴(yán)重。

（2）直接法

該類方法直接從三維點(diǎn)云中提取邊緣［10-11，17-22］。其中，文獻(xiàn)［10］利用點(diǎn)云分割面片相交和深度不連續(xù)特征來檢測面相交邊緣與深度不連續(xù)邊緣；文獻(xiàn)［11］利用點(diǎn)云分割方法以及圖理論檢測封閉銳利邊緣；文獻(xiàn)［17］利用凸包算法檢測建筑物屋頂輪廓；文獻(xiàn)［18］利用橢圓鄰域搜索來改進(jìn)凸包算法從而提取更加緊致的多種形狀建筑物輪廓；文獻(xiàn)［19］利用高程差異來提取機(jī)載激光掃描點(diǎn)云數(shù)據(jù)邊緣；文獻(xiàn)［20］利用夾角限制來提取三維點(diǎn)云中建筑物立面邊緣；文獻(xiàn)［21］利用Gibbs能量模型、馬爾科夫過程及數(shù)學(xué)形態(tài)學(xué)算子來提取三維點(diǎn)云中建筑物屋頂輪廓；文獻(xiàn)［22］利用矩形來近似表達(dá)三維點(diǎn)云中建筑物屋頂輪廓。

參考三維點(diǎn)云數(shù)據(jù)中邊緣的定義不難發(fā)現(xiàn)，在以上關(guān)于三維點(diǎn)云數(shù)據(jù)邊緣檢測的方法中，大部分是針對某一特定邊緣而設(shè)計(jì)的。其中，一些方法旨在提取機(jī)載三維激光掃描點(diǎn)云中的建筑物屋頂輪廓［13-18，21-22］。文獻(xiàn)［20］的方法旨在提取車載或地面激光掃描三維點(diǎn)云數(shù)據(jù)建筑物立面輪廓，文獻(xiàn)［10］的方法旨在提取三維點(diǎn)云中的深度不連續(xù)邊緣以及平面相交邊緣。

此外，按不同的數(shù)據(jù)源展開分析，大部分研究均針對機(jī)載或地面三維激光掃描數(shù)據(jù)。對于工業(yè)逆向工程或小尺度物體模型的點(diǎn)云數(shù)據(jù)，學(xué)者們同樣提出了一些邊緣檢測方法，如文獻(xiàn)［23］從物體的表面網(wǎng)格數(shù)據(jù)中提取光滑特征線，文獻(xiàn)［11］提取工業(yè)設(shè)備點(diǎn)云數(shù)據(jù)中的封閉銳利邊緣，文獻(xiàn)［24］利用傅里葉變換方法提取小尺度物體表面邊緣。

目前，該類方法的自動化程度均很低，大多需要對原始的三維點(diǎn)云數(shù)據(jù)進(jìn)行分割、目標(biāo)識別等步驟，再根據(jù)某一特定目標(biāo)檢測邊緣。

2.三維直線段提取

目前，從三維點(diǎn)云數(shù)據(jù)中提取直線段的研究還非常少見，僅有文獻(xiàn)［10，25—27］以此為主題進(jìn)行了探討，4種方法的思路截然不同，但是，就是否借助圖像處理方法而言，同樣可以分為間接法與直接法兩類。

（1）間接法

該類方法需要借助于圖像處理［26-27］。文獻(xiàn)［26］方法定義直線段為兩個平面的相交線，進(jìn)而定義直線支撐區(qū)域，并將三維點(diǎn)云數(shù)據(jù)根據(jù)不同的視點(diǎn)投影成多視圖像，在多視圖像中檢測直線段并與三維點(diǎn)云數(shù)據(jù)相對應(yīng)，從而提取直線段。然而，該方法提取的直線段不全面，只能提取平面相交線，對于規(guī)則平面的輪廓線則無能為力。文獻(xiàn)［27］利用球面投影將三維點(diǎn)云數(shù)據(jù)轉(zhuǎn)換成二維圖像，利用二維圖像邊緣檢測方法提取邊緣，再利用霍夫變換提取直線段。

（2）直接法

該類方法無需借助圖像處理方法，直接從三維點(diǎn)云數(shù)據(jù)中提取直線段［10，25］。文獻(xiàn)［10］首先從三維點(diǎn)云數(shù)據(jù)中提取兩類邊緣，即深度不連續(xù)邊緣和平面相交邊緣，然后對邊緣點(diǎn)利用協(xié)方差矩陣特征值分析方法進(jìn)行分割，從而追蹤到直線段邊緣點(diǎn)，再擬合直線方程并提取直線段；該方法相對全面地給出了直接從三維點(diǎn)云數(shù)據(jù)中提取邊緣以及直線段的處理流程，但是邊緣檢測不全面，并且，在邊緣點(diǎn)追蹤過程中，不能很好區(qū)分方向相同的臨近直線，從而導(dǎo)致直線段提取錯誤和漏檢現(xiàn)象。文獻(xiàn)［25］結(jié)合RANSAC和馬氏距離來檢測三維直線段，但是，該方法只能檢測出很少的直線段，不能滿足后續(xù)研究的需要［26］。

3.存在的問題

通過以上對目前方法的總結(jié)與描述，其中邊緣檢測研究存在的問題如下:

1）很多方法要借助二維圖像處理方法來提取點(diǎn)云邊緣。然而，三維到二維的轉(zhuǎn)換或利用二維表示三維會損失大量空間信息，會漏檢一些三維邊緣。

2）現(xiàn)有的大部分方法僅僅針對一種或兩種邊緣進(jìn)行提取，大大限制了方法的應(yīng)用。

3）很多方法僅適用于小尺度規(guī)則點(diǎn)云數(shù)據(jù)，對于大尺度、無組織、不規(guī)則且含有噪聲的點(diǎn)云數(shù)據(jù)不能發(fā)揮效力。

4）現(xiàn)有方法的自動化程度較低，很多方法需要借助三維點(diǎn)云分割、目標(biāo)提取等處理，然后針對特定目標(biāo)提取邊緣。

對于三維直線段提取，目前相關(guān)文獻(xiàn)并不多見，需要進(jìn)行探索的內(nèi)容很多。并且，有些方法的提取效果很大程度上取決于邊緣檢測效果的優(yōu)劣，加之三維點(diǎn)云數(shù)據(jù)邊緣檢測存在問題，因此漏檢現(xiàn)象嚴(yán)重。

二、展 望

三維點(diǎn)云數(shù)據(jù)邊緣檢測與直線段提取已經(jīng)取得了一定研究成果，但是仍然存在上述問題亟待解決。總體而言，在檢測與提取過程中，自動化程度、算法效率、普適性、精確性等方面都有待提高。

特征提取的發(fā)展，向來離不開計(jì)算機(jī)視覺、模式識別和計(jì)算幾何領(lǐng)域的相關(guān)研究。針對三維點(diǎn)云數(shù)據(jù)，計(jì)算幾何領(lǐng)域的經(jīng)典算法已經(jīng)在邊緣檢測過程中得到了充分應(yīng)用，如凸包算法［18］、圖理論［11］等。此外，邊緣與直線段特征通常與相應(yīng)的三維幾何結(jié)構(gòu)相關(guān)聯(lián)，這些三維幾何結(jié)構(gòu)的分解與表示在計(jì)算機(jī)視覺和模式識別領(lǐng)域已有相關(guān)研究，且已取得很大進(jìn)展。如果充分利用這些相關(guān)學(xué)科領(lǐng)域的最新研究成果，必將大力推動三維點(diǎn)云邊緣檢測與直線段提取的發(fā)展。

［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］ 張帆，高云龍，黃先鋒，等.基于球面投影的單站地面激光點(diǎn)云直線段提取方法［J］.測繪學(xué)報(bào)，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

國家自然科學(xué)基金（41371405）；基礎(chǔ)測繪項(xiàng)目（A1506）

倪 歡（1989—），男，博士生，從事三維點(diǎn)云與遙感圖像目標(biāo)識別研究。E-mail:nih2015@yeah.net

引文格式：倪歡，張繼賢，林祥國.三維點(diǎn)云邊緣檢測和直線段提取進(jìn)展與展望［J］.測繪通報(bào)，2016（7）:1-4.