尹相寶，花向紅，劉金標(biāo)，龔子楨，郝旦

(1.武漢大學(xué)測(cè)繪學(xué)院，湖北武漢 430079； 2.武漢大學(xué)災(zāi)害監(jiān)測(cè)與防治研究中心，湖北 武漢 430079；3.武漢市勘測(cè)設(shè)計(jì)研究院，湖北武漢 430022)

基于掃描數(shù)據(jù)線線間關(guān)系的曲率壓縮新算法

尹相寶1，2?，花向紅1，2，劉金標(biāo)3，龔子楨1，2，郝旦1，2

(1.武漢大學(xué)測(cè)繪學(xué)院，湖北武漢 430079； 2.武漢大學(xué)災(zāi)害監(jiān)測(cè)與防治研究中心，湖北 武漢 430079；3.武漢市勘測(cè)設(shè)計(jì)研究院，湖北武漢 430022)

針對(duì)線型掃描點(diǎn)云數(shù)據(jù)，本文分析比較了多種壓縮算法，提出了一種基于掃描數(shù)據(jù)線線間關(guān)系的曲率壓縮新算法，并用VC＋＋編程進(jìn)行試驗(yàn)分析，取得了較好的壓縮效果。

三維點(diǎn)云；掃描線線間關(guān)系；曲率壓縮新算法

1 引 言

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

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

2 基于掃描數(shù)據(jù)線線間關(guān)系的曲率壓縮新算法

2.1 算法基本原理

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

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

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

根據(jù)高等代數(shù)的知識(shí)，利用公式(3)求出2點(diǎn)的曲率。

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

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

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

2.2 算法實(shí)現(xiàn)

為了評(píng)價(jià)該新算法的壓縮效果，本文采用VC＋＋語言進(jìn)行了編程實(shí)現(xiàn)，其偽代碼流程大致如下:

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

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

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

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

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

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

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

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

3 實(shí)例效果分析

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

圖2 原始點(diǎn)云

圖3 角度弦高法壓縮后點(diǎn)云，壓縮率36%

圖4 曲率壓縮新算法壓縮后點(diǎn)云，壓縮率31%

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

4 結(jié) 論

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

[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]許捍衛(wèi)，周衛(wèi)娟.一種新的等值線數(shù)據(jù)壓縮算法[J].河海大學(xué)，理論研究:5～7

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

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

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

[6]李珂珍，婁小平，呂乃光.用于點(diǎn)云曲面重構(gòu)的數(shù)據(jù)精簡(jiǎn)方法研究[J].北京機(jī)械工業(yè)學(xué)院學(xué)報(bào)，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—)，男，在讀碩士研究生，主要研究三維激光掃描點(diǎn)云數(shù)據(jù)處理、精密工程測(cè)量理論與方法等。

國家自然科學(xué)基金資助項(xiàng)目40901214(項(xiàng)目批準(zhǔn)號(hào))，Project 40901214 supported by NSFC；精密工程與工業(yè)測(cè)量國家測(cè)繪局重點(diǎn)實(shí)驗(yàn)室開放基金項(xiàng)目資助(PF2009－2)。