基于鄰域柵格篩選的點(diǎn)云邊緣點(diǎn)提取方法*

高 閣，李 鵬

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

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

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

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

1 原理與方法

1.1 空間投影和柵格建立

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

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

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

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

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

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

1.2 邊緣點(diǎn)篩選

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

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

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

設(shè)置常數(shù)J=Nu+Nd+Nl+Nr用于表示柵格周?chē)諙鸥竦姆植记闆r。當(dāng)J等于1時(shí)，代表當(dāng)前實(shí)柵格僅有上鄰域柵格為空柵格，判定該柵格為邊緣柵格，取最靠近邊緣位置的數(shù)據(jù)點(diǎn)作為邊緣點(diǎn)提取；當(dāng)J等于5時(shí)，代表當(dāng)前實(shí)柵格的左方和上方為空柵格，選取最靠近左上角的點(diǎn)作為邊緣點(diǎn)提取。同理，表1展示了所有J值對(duì)應(yīng)的邊緣點(diǎn)位置情況。

表1 邊緣點(diǎn)位置判斷

1.3 邊緣點(diǎn)排序

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

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

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

圖3 邊緣點(diǎn)排序

2 實(shí)驗(yàn)結(jié)果與分析

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

2.1 邊緣點(diǎn)的提取效果測(cè)試

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

圖4 不同柵格長(zhǎng)度下邊緣點(diǎn)的提取效果

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

2.2 邊緣點(diǎn)的提取速度測(cè)試

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

表2 邊緣點(diǎn)位置判斷

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

3 結(jié)束語(yǔ)

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