一種基于Graham掃描算法的空間點云結構化算法研究

王凱 支煜 陳浩 張毅坤

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

關鍵詞： 過度包裝； 散亂點云； Graham掃描算法； Denaunay三角化； 凸包算法； 點云結構化

中圖分類號： TN919.2?34 文獻標識碼： 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 引 言

在過度包裝檢測的過程中，首先對商品和商品包裝進行掃描，得到空間散亂點云[1?2]，完成空間重建；然后利用本文提出的方法對散亂點云進行結構化處理，明確拓撲信息；最后進行空隙率計算，得到是否過度包裝的結論。所謂點云，是指在逆向工程中通過測量儀器得到的產品外觀表面的點數據集合。由于獲取方便、表示簡單、靈活等優勢、點云逐漸成為常用的三維模型表示方法[3]。點云數據通常會攜帶著坐標信息和其他拓撲信息，所以目前絕大多數的三維建模使用的都是點云數據。散亂點云指的是點與點之間的拓撲關系尚未明確的點云。

尋找拓撲關系是三維重建必不可少的過程，目前使用的是基于德勞內（Delaunay）[4?5]結構化方法和基于凸包[6?8]的結構化方法。基于德勞內三角化法的結構化處理中的逐點插入法是一個傳統的方法，由于要花費大量的時間在點的查詢及三角形的定位查詢上，逐點插入法的時間復雜度較大，特別是如果每次查詢插入點都是對整個點集里的所有點，則算法的時間復雜度將進一步增大。

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

基于Graham掃描法改進型構造算法，兼容了上述兩種方法的優點，避免了不足，為后面體積計算的實驗數據精度提供了有力保障。

1 Graham掃描法

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

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

2） 線段[]。該線段一定存在于凸包上，然后加入[C]。假定線段[]恰好也在凸包上，因為對[H]，[K]，[C]三點來說，凸包就是由這三點組成的。接下來給初始凸包加入[D]點時發現，此時線段[]才會在凸包上，然后將線段[]排除，所以[C]點不是凸包上的點。

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

4） 在圖1中，當加入[K]點時，由于[]需要旋轉到[]時的角度是順時針轉動，所以[C]點確定不在凸包的邊緣上，予以刪除，但保留[K]點。然后繼續加入[D]，因為線段[]要旋轉到[]的角度，是逆時針轉動，所以[D]保留。按照上面的步驟進行繼續掃描，直到遍歷所有的點即可。

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

假設一個有三個或者以上點的點集[Q]，Graham掃描法的過程如下：

1） p0為[Q]中x?y坐標系下排序值最小的點；

2） 設S是對其余以p0點為中心的極角進行逆時針排序得到的點集；

3） p0進棧S；

4） p1進棧S；

5） p2進棧S；

6） 直至所有的點全部壓入棧S；

7） 由S的棧頂元素和棧頂元素的下一個元素，和p1構成的折線只拐向右側；

8） 對S彈棧；

9） 壓pi進棧S；

10） 返回棧S。

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

2 基于Graham掃描法改進型構造算法

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

2.1 初始點的選擇及構造掃描線

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

構造包含所有點的最小包圍盒，構造規則的包圍盒，是為了在選擇初始點的時候計算更加的方便，通過數據點中的幾個最大最小目標點就可以確定初始點。

以該點為出發點，構造射線，以射線與x軸夾角為0時為初始掃描線，進行逆時針旋轉掃描，如圖5所示。

2.2 數據點的篩選排序和存儲

對所有的點云數據點與初始點連線按照角度由小到大進行排序；假設坐標原點[o]，初始掃描線上的某點[pa] ，和數據點處于當前掃描線上的位置點[pb]。于是極角大小[A]為：

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

可以根據極角[A]的大小對所有點進行排序。

使用掃描線進行掃描，當同一角度的射線上含有2個或者含有2個以上的點，選擇最外側的點（可以用距離進行判斷），只保留最外側的點，將其余的點舍棄。

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

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

將篩選后的點一次進行壓棧操作，便可以存儲相互的拓撲信息。從A點開始，按照掃描線掃描的順序依次連接篩選后的坐標點。結果如圖7所示。

3 基于Graham掃描改進型算法的體積計算

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

4 實驗分析

實驗物體是石膏制的維尼熊，瓦楞板紙箱和叮當貓，分別有41 000個，57 900個和35 200個數據點，通過對上述兩種方法的測試得到以下數據。

4.1 處理時間比較

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

4.2 體積計算時間

在切片大小不變，數據點逐漸減小的基礎上，對基于兩種方法的體積計算運行時間進行比對，如圖9所示。通過對規則輪廓（杯子外包裝）和不規則輪廓（維尼熊藝術品）的體積計算驗證基于Graham掃描算法和基于改進型構造算法的點云體積計算算法的計算精度、準確性和效率，通過實驗，驗證結果如表1所示。

5 結 語

本文提出了一種基于Graham掃描法的改進型點云體積構造算法。該算法是對已有的Graham掃描算法的有效補充和改進。該算法的關鍵在于對于初始點的選擇，和對大量數據的預篩選。實驗表明，改進型點云構造算法可以完全滿足過度包裝檢測系統對計算體積的實時性和精度需求。與Graham掃描算法相比，該算法具有更高的精度同時擁有更短的運行時間。

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

參考文獻

[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].現代電子技術，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].大地測量與地球動力學，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.