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

高 閣，李 鵬

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

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

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

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

1 原理與方法

1.1 空間投影和柵格建立

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

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

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

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

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

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

1.2 邊緣點篩選

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

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

圖2 鄰域空柵格對應(yīng)的值

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

表1 邊緣點位置判斷

1.3 邊緣點排序

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

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

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

圖3 邊緣點排序

2 實驗結(jié)果與分析

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

2.1 邊緣點的提取效果測試

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

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

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

2.2 邊緣點的提取速度測試

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

表2 邊緣點位置判斷

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

3 結(jié)束語

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