基于鄰域柵格篩選的點云邊緣點提取方法*

高 閣，李 鵬

（滁州學院 地理信息與旅游學院，安徽 滁州239001）

隨著近年來激光掃描技術的發展，三維點云技術也得到了飛速發展。由于可以快速獲取被測物體豐富的三維空間信息，且不需要與目標物體進行接觸。因此被越來越多的領域所青睞。點云邊緣作為描述物體的重要特征，能夠用較少的數據點對物體進行清晰的描述。在建筑特征提取[1-2]，逆向工程[3-5]，空洞修復[6]，數據精簡[7]等方面都有著廣泛的應用。

許多學者對邊緣點的提取做出了研究：張志佳等[8]首先對數據進行柵格組織，通過比較柵格內投影點所對應深度的平均值與其八鄰域柵格的深度差判斷柵格內是否存在邊緣點，再對柵格內的投影點進行升序排列篩選出其中的邊緣點。王宗躍等[9]通過對點集進行格網組織，在排除掉非邊緣格網后再使用Alpha shape算法[10]進行邊緣點提取，提升了Alpha shape算法在提取邊緣點時的效率。丁承君等[11]借助PCL點云庫實現了對點云邊緣的提取，通過對待測點與k個鄰近點組成向量的夾角進行排序，大于連續夾角的最大差值的點即為邊緣點。朱漢華等[12]通過對數據進行三角化構成三角網，最終得到邊緣點的連線。這些方法往往傾向于對點云邊緣進行更為精細的提取，花費的時間較高。在實際應用時，過于精細的邊緣點反而可能會導致擬合出的輪廓線偏離實際位置[1]。

針對這些問題，本文提出了一種快速邊緣點提取方法，首先將數據投影到二維平面，再通過四鄰域分析篩選出包含邊緣點的柵格并判斷出邊緣點在柵格中的位置，最終得到數據的邊緣點。同時，通過追蹤包含有邊緣點的柵格，還可以實現對邊緣點的快速排序，得到邊緣點的順序關系。試驗結果證明，本方法可以實現對點云數據邊緣的快速提取，并可以根據使用需要對邊緣點的精細程度進行控制。

1 原理與方法

1.1 空間投影和柵格建立

點云數據包含的坐標信息有三個維度，為了提高計算效率，本文首先對三維點云進行“偽投影”。通過在后續計算中忽略數據中的其中一個維度，將原本使用的三維坐標系更改為對應的二維坐標系，完成對數據的“偽投影”。這樣既可以達到投影的效果，又不需要改變原始點云數據。具體步驟如下：

首先計算點云在三個維度間的最大和最小值之差Dx、Dy和Dz，選取差值最小的維度方向作為投影方向。以Dz的數值最小為例，在后續處理計算中忽略每個點的Z坐標值，并將計算時使用的坐標系更改為X-Y系，在效果上相當于將數據中的所有點都投影到了XOY平面中。

由于投影會造成投影方向上的長度壓縮，為了避免提取出的邊緣點的間隔不均勻，在進行柵格劃分前先通過式（1）計算x維度相對于y維度在投影后產生的長度壓縮比例R，隨后根據DX、Dy的值，在XOY平面中建立矩形柵格空間，柵格空間的行數L和列數W通過對式（2）取整得到，式中的常數項保證了柵格空間在進行點云填充后仍然能夠在四周保留空柵格用于后續處理，

最后將投影中的點云依次填充到柵格空間中的對應位置，每個點在填充時所對應的柵格空間的行列數Gl和Gw通過對式（3）取整后得到，

圖1 展示了偽投影和柵格填充效果。

圖1 偽投影和柵格填充效果

1.2 邊緣點篩選

在進行邊緣點篩選時，需要先確定柵格內是否包含有邊緣點，再將其中最靠近邊緣的點取出。在上文建立的柵格空間中，可以根據是否包含數據點將其中的柵格分為實柵格和空柵格，根據是否包含邊緣點將實柵格分為邊緣點柵格和非邊緣點柵格。由于空柵格會有規律的存在于邊緣柵格的周圍，因此可以將實柵格鄰域的空柵格的分布情況作為判斷依據，判斷其是否為邊緣柵格，以及邊緣點在其中的位置。

每個實柵格都有四個由邊連接的相鄰柵格和四個由點連接的相鄰柵格，由于邊緣點的分布在空間上是連續的，所以通過由邊連接的四個鄰域就可以有效的對邊緣柵格以及邊緣點在其中的位置進行判斷。以圖2為例，N為待判斷的實柵格，設置四個由邊連接的鄰域柵格Nu、Nd、Nl、Nr為空柵格時，對應的值分別為1、2、4、8，而為實柵格時，對應的值為0。

圖2 鄰域空柵格對應的值

設置常數J=Nu+Nd+Nl+Nr用于表示柵格周圍空柵格的分布情況。當J等于1時，代表當前實柵格僅有上鄰域柵格為空柵格，判定該柵格為邊緣柵格，取最靠近邊緣位置的數據點作為邊緣點提??；當J等于5時，代表當前實柵格的左方和上方為空柵格，選取最靠近左上角的點作為邊緣點提取。同理，表1展示了所有J值對應的邊緣點位置情況。

表1 邊緣點位置判斷

1.3 邊緣點排序

由于所有邊緣柵格在空間分布上是連續的，且每個柵格只會提取出一個點，因此在使用本方法提取邊緣點后可以很容易對這些邊緣點排序。具體操作如下：

標記所有含有邊緣點的柵格為待排序柵格，任意選取一個包含邊緣點的柵格，標記該柵格為初始柵格，沿順時針方向依次對該柵格周圍的八個柵格進行判斷，當發現待排序的邊緣柵格時，將其設置為新的中心柵格繼續進行上述判斷，同時刪除上一個中心柵格的待排序標記。以此類推，當中心柵格回到初始柵格位置時，排序結束。為了避免數據中有多個邊緣環，還需要查看在一次排序后是否仍留有沒有排序的邊緣點，若有，則需要在剩余的點中再進行一次排序操作，直到沒有邊緣點存在。

以圖3為例，N為當前判斷柵格，圖中數字為判斷順序，圖3左N位置為初始柵格，沿順時針方向依次對N的八個鄰域柵格進行判斷，在4號柵格發現了邊緣柵格，于是4號柵格成為了新的待判斷柵格，產生了圖3中的情況。當N在圖3右位置時，在2號柵格找到了初始柵格，說明在排序過程中邊緣點已經形成閉環，排序完成。由于每一個柵格都對應一個邊緣點，上述過程中中心柵格的轉移順序即為邊緣點的排列順序。

圖3 邊緣點排序

2 實驗結果與分析

為了驗證本文方法的有效性，使用C++語言對本文方法進行了實現。實驗使用Visual Studio 2019編譯器，CPU為英特爾i5-8300H。為了測試方法的效果和速度，本文設置了兩組實驗分別對本文方法的提取效果和提取速度進行了測試。

2.1 邊緣點的提取效果測試

為了測試算法對邊緣點的提取效果，選取了四種不同類型的數據，分別由大到小對柵格長度進行設置，提取效果如圖4所示。

圖4 不同柵格長度下邊緣點的提取效果

從圖4中可以看出，本方法可以對多種類型數據的邊緣點進行有效提取，且對象中出現的空洞邊緣也能夠得到識別與處理。同時提取的邊緣點間隔均勻，貼近與真實物體的邊緣。此外，針對所需邊緣點的細節情況不同，設置不同的柵格大小，可以對邊緣點的數量和精細程度進行控制。圖4下數據中有兩個大小不同的間隙，在對柵格的邊長由小到大依次進行調整后，可以看到兩個寬度不同的間隙隨著柵格邊長的增加而依次消失了。在實際使用中，可以根據這一特性對柵格的大小進行控制，從而對不需要的細節進行剔除。

2.2 邊緣點的提取速度測試

為了驗證本方法的效率，在保證邊緣提取質量的前提下采用不同大小的數據分別使用本文方法和文獻[11]方法進行對比。表2為邊緣點位置判斷。

表2 邊緣點位置判斷

可以看出，本文方法在時間消耗上明顯優于文獻[11]方法，并且隨著數據量的增加優勢會更加明顯。由于本文方法的時間復雜度僅為O（n），相較現有的大部分方法在時間花費上更有優勢，且這一優勢會隨著數據量的增加而增加。

3 結束語

文章提出的這種能夠快速精準提取點云邊緣的方法，通過對數據進行柵格劃分，利用邊緣柵格與空柵格的空間分布關系，篩選出包含有邊緣點的柵格并從中提取出對應的邊緣點。根據邊緣柵格的分布特點，能夠快速地完成邊緣點的排序。實驗結果表明，本方法具有有效性和快速性。雖然本方法難以嚴格地提取所有的邊緣點，但由于每個提取出的每個邊緣點都是所處柵格內最靠近邊緣位置的點，更能反映出物體輪廓的真實情況。