一種基于Graham掃描算法的空間點(diǎn)云結(jié)構(gòu)化算法研究

王凱 支煜 陳浩 張毅坤

摘 要： 在過度包裝檢測過程中，針對商品三維重建后的散亂點(diǎn)云無法進(jìn)行后續(xù)空隙率判定的問題，提出一種基于Denaunay三角化和凸包算法的散亂點(diǎn)云結(jié)構(gòu)化方法。首先，因?yàn)榭臻g點(diǎn)云結(jié)構(gòu)復(fù)雜，所以將空間點(diǎn)云進(jìn)行切片和投影操作，也就是降維操作；其次，對投影數(shù)據(jù)點(diǎn)進(jìn)行結(jié)構(gòu)化處理，尋找初始點(diǎn)，依次對投影點(diǎn)按照極角大小進(jìn)行排序；最后利用所構(gòu)造的掃描線對數(shù)據(jù)點(diǎn)進(jìn)行篩選和結(jié)構(gòu)化。實(shí)驗(yàn)表明，基于Denaunay三角化和凸包算法的散亂點(diǎn)云結(jié)構(gòu)化方法處理時間短，穩(wěn)定性和精度高、適用性強(qiáng)，完全滿足過度包裝檢測系統(tǒng)。與目前方法相比，該方法有更好的適用性，能夠滿足大多數(shù)平臺的需求。

關(guān)鍵詞： 過度包裝； 散亂點(diǎn)云； Graham掃描算法； Denaunay三角化； 凸包算法； 點(diǎn)云結(jié)構(gòu)化

中圖分類號： TN919.2?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2018）14?0139?04

Research on space point cloud structuring algorithm

based on Graham scanning algorithm

WANG Kai1，2， ZHI Yu2， CHEN Hao2， ZHANG Yikun2

（1. Xian Institute of Measurement and Testing Technology， Xian 710068， China； 2. Xian University of Technology， Xian 710048， China）

Abstract： In allusion to the problem that the subsequent voidage judgment cannot be performed due to the scattered point cloud after 3D reconstruction of commodities during the excessive packaging detection process， a scattered point cloud structuring method based on Denaunay triangularization and convex hull algorithm is proposed. As the structure of the space point cloud is complex， the slicing and projection operations （also called dimensionality reduction operations） are conducted. The projected data points are structured， the initial point is searched out， and the projected points are orderly ranked according to the size of the polar angle. The data points are filtered and structured by using the constructed scanning line. The experimental results show that the scattered point cloud structuring method based on Denaunay triangularization and convex hull algorithm has short processing time， high stability and accuracy， and strong applicability， and can fully satisfy the excessive packaging detection system. In comparison with the current method， the method has better applicability， and can meet the needs of most platforms.

Keywords： excessive packaging； scattered point cloud； Graham scanning algorithm； Denaunay triangularization； convex hull algorithm； point cloud structuring

0 引 言

在過度包裝檢測的過程中，首先對商品和商品包裝進(jìn)行掃描，得到空間散亂點(diǎn)云[1?2]，完成空間重建；然后利用本文提出的方法對散亂點(diǎn)云進(jìn)行結(jié)構(gòu)化處理，明確拓?fù)湫畔ⅲ蛔詈筮M(jìn)行空隙率計算，得到是否過度包裝的結(jié)論。所謂點(diǎn)云，是指在逆向工程中通過測量儀器得到的產(chǎn)品外觀表面的點(diǎn)數(shù)據(jù)集合。由于獲取方便、表示簡單、靈活等優(yōu)勢、點(diǎn)云逐漸成為常用的三維模型表示方法[3]。點(diǎn)云數(shù)據(jù)通常會攜帶著坐標(biāo)信息和其他拓?fù)湫畔ⅲ阅壳敖^大多數(shù)的三維建模使用的都是點(diǎn)云數(shù)據(jù)。散亂點(diǎn)云指的是點(diǎn)與點(diǎn)之間的拓?fù)潢P(guān)系尚未明確的點(diǎn)云。

尋找拓?fù)潢P(guān)系是三維重建必不可少的過程，目前使用的是基于德勞內(nèi)（Delaunay）[4?5]結(jié)構(gòu)化方法和基于凸包[6?8]的結(jié)構(gòu)化方法。基于德勞內(nèi)三角化法的結(jié)構(gòu)化處理中的逐點(diǎn)插入法是一個傳統(tǒng)的方法，由于要花費(fèi)大量的時間在點(diǎn)的查詢及三角形的定位查詢上，逐點(diǎn)插入法的時間復(fù)雜度較大，特別是如果每次查詢插入點(diǎn)都是對整個點(diǎn)集里的所有點(diǎn)，則算法的時間復(fù)雜度將進(jìn)一步增大。

基于Graham掃描法[9]是通過尋找一個起始點(diǎn)，對所有點(diǎn)與初始點(diǎn)形成的極角逆時針排序，利用壓棧操作對外圍的點(diǎn)存儲和排序。凸包通常都是顯示著物體的大致輪廓，且比實(shí)際的面積略微擴(kuò)大，顯然不適合處理體積大小的問題。

基于Graham掃描法改進(jìn)型構(gòu)造算法，兼容了上述兩種方法的優(yōu)點(diǎn)，避免了不足，為后面體積計算的實(shí)驗(yàn)數(shù)據(jù)精度提供了有力保障。

1 Graham掃描法

Graham掃描法[10]過程描述如下：

1） 在所有點(diǎn)中選取[y] 坐標(biāo)最小的一點(diǎn)H，當(dāng)作基點(diǎn)。如果存在多個點(diǎn)的[y]坐標(biāo)都為最小值，則選取x坐標(biāo)最小的一點(diǎn)。坐標(biāo)相同的點(diǎn)應(yīng)排除。然后按照其它各點(diǎn)[p]和基點(diǎn)構(gòu)成的向量[]與x軸的夾角，根據(jù)夾角大小進(jìn)行排序，進(jìn)行順時針的掃描，如果夾角從小到大排序則進(jìn)行逆時針的掃描。最終求解過程中無需求出夾角大小，只需要根據(jù)余弦定理求出向量夾角的余弦值即可。圖1中，基點(diǎn)為[H]，根據(jù)夾角的大小由小至大依次排序后為H，K，C，D，L，F(xiàn)，G，E，I，B，A，J，接下來進(jìn)行逆時針的掃描。

2） 線段[]。該線段一定存在于凸包上，然后加入[C]。假定線段[]恰好也在凸包上，因?yàn)閷H]，[K]，[C]三點(diǎn)來說，凸包就是由這三點(diǎn)組成的。接下來給初始凸包加入[D]點(diǎn)時發(fā)現(xiàn)，此時線段[]才會在凸包上，然后將線段[]排除，所以[C]點(diǎn)不是凸包上的點(diǎn)。

3） 在加入一點(diǎn)時，必須首先考慮前面線段有沒有出現(xiàn)在凸包上。掃描從基點(diǎn)處開始，凸包上的每條鄰接線段的旋轉(zhuǎn)方向相同，并且和掃描的方向應(yīng)該相反。當(dāng)發(fā)現(xiàn)新加入的點(diǎn)使新線段和上線段的轉(zhuǎn)動方向發(fā)生了變化，便可以判定之前的點(diǎn)肯定沒有在凸包上。實(shí)現(xiàn)時可用向量叉積進(jìn)行判斷，假設(shè)加入的一點(diǎn)為pn+1，之前點(diǎn)為pn，再上一點(diǎn)是pn -1。在進(jìn)行順時針掃描的時候，當(dāng)向量與的叉積值為正（在逆時針掃描的時候判斷恰好相反），此時把上一點(diǎn)刪除。整個刪除過程都要回溯，把之前計算出的全部叉積符號是相反的點(diǎn)全部刪除，最后把新點(diǎn)加入到凸包。

4） 在圖1中，當(dāng)加入[K]點(diǎn)時，由于[]需要旋轉(zhuǎn)到[]時的角度是順時針轉(zhuǎn)動，所以[C]點(diǎn)確定不在凸包的邊緣上，予以刪除，但保留[K]點(diǎn)。然后繼續(xù)加入[D]，因?yàn)榫€段[]要旋轉(zhuǎn)到[]的角度，是逆時針轉(zhuǎn)動，所以[D]保留。按照上面的步驟進(jìn)行繼續(xù)掃描，直到遍歷所有的點(diǎn)即可。

圖2中外圍形狀表示的多邊形就是點(diǎn)集[Q]={p0， p1，…，p12}的凸包。

假設(shè)一個有三個或者以上點(diǎn)的點(diǎn)集[Q]，Graham掃描法的過程如下：

1） p0為[Q]中x?y坐標(biāo)系下排序值最小的點(diǎn)；

2） 設(shè)S是對其余以p0點(diǎn)為中心的極角進(jìn)行逆時針排序得到的點(diǎn)集；

3） p0進(jìn)棧S；

4） p1進(jìn)棧S；

5） p2進(jìn)棧S；

6） 直至所有的點(diǎn)全部壓入棧S；

7） 由S的棧頂元素和棧頂元素的下一個元素，和p1構(gòu)成的折線只拐向右側(cè)；

8） 對S彈棧；

9） 壓pi進(jìn)棧S；

10） 返回棧S。

經(jīng)過上述過程的執(zhí)行，棧S由棧底至棧頂元素就是[Q]凸包的頂點(diǎn)按照逆時針排序所得出的。在對點(diǎn)按極角大小按照逆時針來排序的時候，不需求出極角的值，只需要求出次序就可以。這個步驟通常可以使用矢量叉積性質(zhì)實(shí)現(xiàn)。該算法在對二維點(diǎn)云進(jìn)行結(jié)構(gòu)化處理時，只可能出現(xiàn)凸多邊形，而本文所研究的系統(tǒng)中物體輪廓會出現(xiàn)凹槽，這就導(dǎo)致在精度上該算法會出現(xiàn)一定的損失。

2 基于Graham掃描法改進(jìn)型構(gòu)造算法

針對存在的問題，提出了基于Delaunay三角化法和Graham掃描法的改進(jìn)算法。基于Graham掃描法改進(jìn)型構(gòu)造算法流程如圖3所示。

2.1 初始點(diǎn)的選擇及構(gòu)造掃描線

在所有的二維投影點(diǎn)數(shù)據(jù)中，分別搜索出點(diǎn)云水平方向的最小值和垂直方向上的最大值和最小值，構(gòu)造包含所有點(diǎn)的正方形，初始點(diǎn)為兩條對角線的交點(diǎn)，同時找出最左下方的點(diǎn)，記作p0，如圖4所示。

構(gòu)造包含所有點(diǎn)的最小包圍盒，構(gòu)造規(guī)則的包圍盒，是為了在選擇初始點(diǎn)的時候計算更加的方便，通過數(shù)據(jù)點(diǎn)中的幾個最大最小目標(biāo)點(diǎn)就可以確定初始點(diǎn)。

以該點(diǎn)為出發(fā)點(diǎn)，構(gòu)造射線，以射線與x軸夾角為0時為初始掃描線，進(jìn)行逆時針旋轉(zhuǎn)掃描，如圖5所示。

2.2 數(shù)據(jù)點(diǎn)的篩選排序和存儲

對所有的點(diǎn)云數(shù)據(jù)點(diǎn)與初始點(diǎn)連線按照角度由小到大進(jìn)行排序；假設(shè)坐標(biāo)原點(diǎn)[o]，初始掃描線上的某點(diǎn)[pa] ，和數(shù)據(jù)點(diǎn)處于當(dāng)前掃描線上的位置點(diǎn)[pb]。于是極角大小[A]為：

[A=（xpa-xo）×（ypb-yo）-（xpb-xo）（ypa-yo）] （1）

可以根據(jù)極角[A]的大小對所有點(diǎn)進(jìn)行排序。

使用掃描線進(jìn)行掃描，當(dāng)同一角度的射線上含有2個或者含有2個以上的點(diǎn)，選擇最外側(cè)的點(diǎn)（可以用距離進(jìn)行判斷），只保留最外側(cè)的點(diǎn)，將其余的點(diǎn)舍棄。

[pi=max（dis（o，pk））， i，k=1，2，3，…] （2）

[pi]為需要存儲的點(diǎn)，[pk]為掃描線上的點(diǎn)。[dis（o，pk）]為求解距離函數(shù)，約簡示意圖如圖6所示。

將篩選后的點(diǎn)一次進(jìn)行壓棧操作，便可以存儲相互的拓?fù)湫畔ⅰ腁點(diǎn)開始，按照掃描線掃描的順序依次連接篩選后的坐標(biāo)點(diǎn)。結(jié)果如圖7所示。

3 基于Graham掃描改進(jìn)型算法的體積計算

在過度包裝檢測系統(tǒng)中，采用的是切片法來計算體積，對于每一個切片的投影需要進(jìn)行二維層面的結(jié)構(gòu)化處理。首先將商品的空間點(diǎn)云進(jìn)行切割，然后對切片進(jìn)行投影，其次對每一個切片投影進(jìn)行結(jié)構(gòu)化處理，再利用矢量乘法求得投影面積，最終求得體積。切片的大小直接影響著體積計算精度，切片越大，精度越低，切片越小，精度越高。

4 實(shí)驗(yàn)分析

實(shí)驗(yàn)物體是石膏制的維尼熊，瓦楞板紙箱和叮當(dāng)貓，分別有41 000個，57 900個和35 200個數(shù)據(jù)點(diǎn)，通過對上述兩種方法的測試得到以下數(shù)據(jù)。

4.1 處理時間比較

基于Graham掃描算法的改進(jìn)型算法在和Graham掃描法在處理同樣數(shù)據(jù)的情況下，改進(jìn)型算法具有更短的運(yùn)行時間。處理的時間如圖8所示。

4.2 體積計算時間

在切片大小不變，數(shù)據(jù)點(diǎn)逐漸減小的基礎(chǔ)上，對基于兩種方法的體積計算運(yùn)行時間進(jìn)行比對，如圖9所示。通過對規(guī)則輪廓（杯子外包裝）和不規(guī)則輪廓（維尼熊藝術(shù)品）的體積計算驗(yàn)證基于Graham掃描算法和基于改進(jìn)型構(gòu)造算法的點(diǎn)云體積計算算法的計算精度、準(zhǔn)確性和效率，通過實(shí)驗(yàn)，驗(yàn)證結(jié)果如表1所示。

5 結(jié) 語

本文提出了一種基于Graham掃描法的改進(jìn)型點(diǎn)云體積構(gòu)造算法。該算法是對已有的Graham掃描算法的有效補(bǔ)充和改進(jìn)。該算法的關(guān)鍵在于對于初始點(diǎn)的選擇，和對大量數(shù)據(jù)的預(yù)篩選。實(shí)驗(yàn)表明，改進(jìn)型點(diǎn)云構(gòu)造算法可以完全滿足過度包裝檢測系統(tǒng)對計算體積的實(shí)時性和精度需求。與Graham掃描算法相比，該算法具有更高的精度同時擁有更短的運(yùn)行時間。

注：本文通訊作者為張毅坤。

參考文獻(xiàn)

[1] ZHANG X， LI G， ZHAO J， et al. New triangulation method for surface scattered points [C]// Proceedings of IEEE International Conference on Mechatronics and Automation. Tianjin： IEEE， 2014： 541?546.

[2] HE X， NI M， XUE Y， et al. An algorithm for topology reconstruction of scattered point cloud in reverse engineering [J]. Intelligent control and automation， 2010， 20（1）： 3126?3131.

[3] 王凱，支煜，張毅坤，等.一種檢測攝像機(jī)與被測物間三維軸線求解方法[J].現(xiàn)代電子技術(shù)，2015，38（18）：22?25.

WANG Kai， ZHI Yu， ZHANG Yikun， et al. A method to calculate three?dimensional axis between detecting camera and object under test [J]. Modern electronics technique， 2015， 38（18）： 22?25.

[4] SONG D， LI Z. A fast surface reconstruction algorithm based on Delaunay [C]// Proceedings of International Conference on Computer Science and Information Processing. Xian： IEEE， 2012： 981?984.

[5] ZHAO M， AN B， WU Y， et al. A robust Delaunay triangulation matching for multispectral/multidate remote sensing image registration [J]. IEEE geoscience & remote sensing letters， 2015， 12（4）： 711?715.

[6] KLETTE G. A recursive algorithm for calculating the relative convex hull [C]// Proceedings of 25th International Conference of Image and Vision Computing. Queenstown： IEEE， 2010： 1?7.

[7] 劉人午，楊德宏，李燕，等.一種改進(jìn)的最小凸包生成算法[J].大地測量與地球動力學(xué)，2011，31（3）：130?133.

LIU Renwu， YANG Dehong， LI Yan， et al. An improved algorithm for producing minimum convex hull [J]. Journal of geodesy and geodynamics， 2011， 31（3）： 130?133.

[8] LIU Guanghui， CHEN Chuanbo. A new algorithm for computing the convex hull of a planar point set [J]. Journal of Zhejiang University： Science A， 2007， 8（8）： 1210?1217.

[9] TERESHCHENKO V， TERESHCHENKO Y， KOTSUR D. Point triangulation using Graham′s scan [C]// Proceedings of 5th International Conference on the Innovative Computing Technology. Pontevedra： IEEE， 2015： 148?151.

[10] MAHMOOD M T， CHOI Y K， SHIM S O， et al. Estimating shape from focus by Gaussian process regression [C]// Proceedings of IEEE International Conference on Systems， Man， and Cybernetics. Seoul： IEEE， 2012： 1345?1350.