基于掃描數據線線間關系的曲率壓縮新算法

尹相寶，花向紅，劉金標，龔子楨，郝旦

(1.武漢大學測繪學院，湖北武漢 430079； 2.武漢大學災害監測與防治研究中心，湖北 武漢 430079；3.武漢市勘測設計研究院，湖北武漢 430022)

基于掃描數據線線間關系的曲率壓縮新算法

尹相寶1，2?，花向紅1，2，劉金標3，龔子楨1，2，郝旦1，2

(1.武漢大學測繪學院，湖北武漢 430079； 2.武漢大學災害監測與防治研究中心，湖北 武漢 430079；3.武漢市勘測設計研究院，湖北武漢 430022)

針對線型掃描點云數據，本文分析比較了多種壓縮算法，提出了一種基于掃描數據線線間關系的曲率壓縮新算法，并用VC＋＋編程進行試驗分析，取得了較好的壓縮效果。

三維點云；掃描線線間關系；曲率壓縮新算法

1 引 言

三維激光掃描技術以其具有的速度快、精度高、無接觸等優點，在現階段獲得了廣泛的應用，而其數據的海量性造成了后續數據處理的繁瑣和效率低下，因此，如何在保證模型精度的前提下有效壓縮三維激光掃描點云數據，以更少的點精確表征地面、地物特征，降低數據儲存和后處理的難度，成為眾多國內外學者研究的熱點。

針對線型掃描點云數據的壓縮，目前國內主要的壓縮算法就是基于角度、距離、斜率和曲率等的壓縮，許捍衛，周衛娟[2]提出的四點法，吳杭彬，劉春[3]在2006年提出的基于斜率變化的壓縮法，王玉國，周來水，安魯陵[4]在2006年提出的基于曲率的自由曲線自適應壓縮法，以及李海英[5]在2008年提出的曲率壓縮法等，均是此類壓縮算法。可以清楚地發現，在這些針對掃描線點云數據壓縮的算法中，往往考慮的只是在掃描剖面上各點之間的關系，考慮的只是在一條掃描線上各點反映的物體表面特征的情況，而并沒有考慮到相鄰掃描線之間各點的關系，并沒有考慮到在垂直于掃描剖面方向上各點反映的物體表面特征的情況，這雖然在掃描線方向上可以取得不錯的壓縮效果，能很好地反映物體的形狀，但在垂直于掃描線方向上就會喪失一些物體的表面特征，從而影響建模精度。針對這種情況，本文在試驗了多種想法后，在充分考慮了基于曲率的壓縮條件的基礎上，提出了一種基于數據掃描線線間關系的曲率壓縮新算法。

2 基于掃描數據線線間關系的曲率壓縮新算法

2.1 算法基本原理

對于三維激光掃描點云數據的壓縮，最理想的效果就是所保留的點能很好地反映物體的表面特征，表面變化劇烈處保留較多的點，表面變化平緩處則保留較少的點。對于點云數據掃描線，相對于角度、距離等，曲率能更好地反映其變化狀況，可以用來作為線變化的特征量。為了顧及到垂直于掃描線方向上各點之間的關系，該新的壓縮算法的基本原理就是，首先利用導數知識計算出各個點(除第一個點和最后一個點)的曲率，然后順次搜索各點的K鄰域，在K鄰域內比較各個點的曲率大小，將曲率最大的點保留，其余點刪除。

基于掃描線的點云數據是按照鄰接關系存儲的，根據相鄰3個點的平面坐標可以計算中間點的曲率。如圖1所示，假設1、2、3點的平面坐標分別為:1(x1，y1)，2(x2，y2)和3(x3，y3)，不妨設該3點擬合出的掃描曲線方程為y＝ax2＋bx＋c，將點1，點2和點3的平面坐標代入，得一三元方程組:

求解方程組(1)，得系數a，b，c的值，進而根據公式(2)計算掃描曲線在2點的一階和二階導數:

根據高等代數的知識，利用公式(3)求出2點的曲率。

同理，可計算出除第一個點和最后一個點之外的其余所有點的曲率，一般情況下，掃描線的第一個點和最后一個點反映了物體的邊界信息，需要保留。

圖1 掃描線曲率求解示意圖

在求出每個點(除第一個點和最后一個點)的曲率后，從第二個點開始，順次搜索至該點距離為d的所有點，比較這些點的曲率大小，曲率最大的點保留，其余點刪除，然后再進行下一點的判斷。一般情況下，為了能很好地保留物體的表面特征點，避免信息缺失，根據壓縮經驗，d取掃描線間距的1倍～3倍。

2.2 算法實現

為了評價該新算法的壓縮效果，本文采用VC＋＋語言進行了編程實現，其偽代碼流程大致如下:

(1)將點云數據讀入數組中，為了后續計算方便，點的x，y和z值分別讀入一維數組Xin[]，Yin[]和Zin[]中，并將點的總數賦予變量znum。

(2)自定義求解方程組的函數fgroup，計算相鄰3點擬合出的掃描曲線方程y＝ax2＋bx＋c。

(3)From i＝2 To znum－1，調用函數fgroup，獲得系數a和b的值，計算變量y′＝2ax＋b和y″＝2a的值，從而根據公式計算出i點的曲率k，并將其賦予給一維數組K[]。

(4)提示“輸入閾值d:”，將對話框中數據賦予變量d。

(5)自定義尋找最大曲率的函數max。

(6)From i＝2 To znum－1，遍歷尋找距離i點小于d的所有點，并將其加入到數組 L[]中，調用函數max，尋找出曲率最大的點，賦予到數組Xout[]，Yout[]和Zout[]中，并將個數賦予給變量num，其余點刪除。

(7)定義變量yasuolv＝num/znum。

(8)輸出數組Xout[]，Yout[]，Zout[]至文件outfile，返回變量yasuolv。

3 實例效果分析

為了比較驗證該曲率壓縮新算法的壓縮效果，本文采用了云南省昆明市的金剛塔點云數據，由于數據量過于龐大，為節省壓縮時間，只采用了整座塔的60%的點云數據。同時，采用了角度弦高法對其進行了壓縮，以達到相互比較的目的。圖2、圖3、圖4分別為原始點云，角度弦高法壓縮后的點云和曲率壓縮新算法壓縮后的點云。

圖2 原始點云

圖3 角度弦高法壓縮后點云，壓縮率36%

圖4 曲率壓縮新算法壓縮后點云，壓縮率31%

從圖2、圖3和圖4中可以看出，在壓縮率大致相同的情況下，角度弦高法雖然也較好地保留了物體的特征點，在變化劇烈的地方保留了較多的點，在變化平緩的地方保留了較少的點，但由于沒有考慮到掃描線之間的關系，壓縮后的點云分布很不均勻，并且在有些地方出現了信息缺失；曲率壓縮新算法在點云的分布上和保留物體的特征點上相對合理一些，提取的點無論在掃描線方向上，還是在垂直于掃描線方向上都很好地反映了物體的表面特征，但由于采用了比較傳統的K鄰域搜索法，其壓縮效率要相對低一點。

4 結 論

曲率作為反映點云數據掃描線變化情況的特征量，在許多壓縮算法中起著至關重要作用。本文在以往的曲率壓縮算法的基礎上，充分考慮了掃描數據線之間的關系，提出了這種新的壓縮算法，并通過昆明市的金剛塔點云數據的驗證，與角度弦高壓縮法進行比較，取得了很好的壓縮效果，但壓縮效率相對低一點。如何改進點的K鄰域搜索算法，如何在保證壓縮效果的前提下提高壓縮效率，仍是今后研究解決的重點。

[1]S.－M.Hur，H.－C.Kim，S.－H.Lee.STL file generation with data reduction by the delaunay triangulation method in reverse engineering[J].The International Journal of Advanced Manufacturing Technology，2002，19:669～678

[2]許捍衛，周衛娟.一種新的等值線數據壓縮算法[J].河海大學，理論研究:5～7

[3]吳杭彬，劉春.三維激光掃描點云數據的空間壓縮[J].遙感信息(理論研究)，2006，2:22～24

[4]王玉國，周來水，安魯陵.一種基于曲線擬合與采樣的點云數據壓縮方法[J].機械科學與技術，2006，25(8):989～992

[5]李海英，花向紅，陳遠.三維激光點云掃描線曲率壓縮算法研究[J].測繪信息與工程，2009，34(5):43～45

[6]李珂珍，婁小平，呂乃光.用于點云曲面重構的數據精簡方法研究[J].北京機械工業學院學報，2009，24(1):17～20

A New Compressing Method of Curvature Based on the Relationship Among Scanning Lines

Yin XiangBao1，2，Hua XiangHong1，2，Liu JinBiao3，Gong ZiZhen1，2，Hao Dan1，2
(1.School of Geodesy and Geomatics，Wuhan University，Wuhan 430079，China；2.Hazard Monitoring and Prevention Research Center，Wuhan University，Wuhan 430079，China；3.Wuhan Geotechnical Engineering and Surveying Institute，Wuhan 430022，China)

On account of scanning line point cloud data，kinds of reducing methods are analyzed.On the basis of the analysis，a new compressing method of curvature based on the relationship among scanning lines is put forward，which aims at point clouds on scanning lines and is tested on data about Jingang tower.

3D point clouds；relationship among scanning lines；new compressing method of curvature

1672－8262(2010)04－100－03

P234.4

A

2010—04—16

尹相寶(1985—)，男，在讀碩士研究生，主要研究三維激光掃描點云數據處理、精密工程測量理論與方法等。

國家自然科學基金資助項目40901214(項目批準號)，Project 40901214 supported by NSFC；精密工程與工業測量國家測繪局重點實驗室開放基金項目資助(PF2009－2)。