基于凸包算法和抗差最小二乘法的激光掃描儀圓形標(biāo)靶中心定位

何 華，李宗春，阮煥立，付永健

(信息工程大學(xué) 地理空間信息學(xué)院，河南 鄭州 450001)

平面標(biāo)靶是地面激光掃描儀的重要附件之一，在多視點(diǎn)云數(shù)據(jù)拼接、點(diǎn)云數(shù)據(jù)坐標(biāo)轉(zhuǎn)換和激光掃描儀精度檢校中發(fā)揮了重要作用[1]。由于測量環(huán)境復(fù)雜、標(biāo)靶表面污損、殘缺和障礙物遮擋等因素，會(huì)造成平面標(biāo)靶點(diǎn)云數(shù)據(jù)的缺失或冗余，此時(shí)使用重心法解算平面標(biāo)靶中心精度不高，故研究穩(wěn)健的平面標(biāo)靶中心定位算法十分必要。

Lichti等[2]利用標(biāo)準(zhǔn)平面標(biāo)靶的反射特性提取平面標(biāo)靶中心，但沒有考慮噪聲和粗差的影響；王力等[3]和劉燕萍[4]采用回光強(qiáng)度加權(quán)法計(jì)算平面標(biāo)靶中心，但沒有考慮標(biāo)靶存在殘缺的情形；陳俊杰[5]對比了重心類和幾何類平面標(biāo)靶中心定位算法，得出了重心法可獲得較高的中心定位精度的結(jié)論；陳西江等[6]對標(biāo)靶點(diǎn)云進(jìn)行分帶，然后以每帶的K-均值聚類中心均值作為標(biāo)靶中心坐標(biāo)，算法在一定程度上能減弱數(shù)據(jù)缺失的影響，但無法消除粗差的影響；朱寧寧[7]基于點(diǎn)云分布特征提取標(biāo)靶點(diǎn)云邊緣點(diǎn)，用最小二乘法求出標(biāo)靶中心，該算法可解決殘缺標(biāo)靶的定位問題但無法準(zhǔn)確定位冗余標(biāo)靶中心；官云蘭[1]基于模糊均值聚類和距離過濾提取平面標(biāo)靶點(diǎn)云，再用重心法求解標(biāo)靶中心坐標(biāo)，該算法沒有考慮標(biāo)靶殘缺和冗余的情形。薛曉璐[8]提出了基于RANSAC的殘缺平面標(biāo)靶中心定位算法，該算法能準(zhǔn)確定位缺失和冗余標(biāo)靶中心，但算法效率比較低。

針對完整的高質(zhì)量標(biāo)靶點(diǎn)云數(shù)據(jù)，標(biāo)靶中心定位算法可以獲得較高精度的標(biāo)靶中心坐標(biāo)，但當(dāng)標(biāo)靶點(diǎn)云數(shù)據(jù)缺失或冗余時(shí)，定位精度會(huì)極大地降低。本文提出一種基于凸包算法和抗差最小二乘法的中心定位算法，為提高中心定位精度，先剔除標(biāo)靶點(diǎn)云的粗差數(shù)據(jù)，再進(jìn)行最佳平面擬合把所有點(diǎn)云投影到同一平面上，然后旋轉(zhuǎn)標(biāo)靶最佳平面與xoy坐標(biāo)面平行簡化數(shù)據(jù)處理，最后用凸包算法提取標(biāo)靶邊緣點(diǎn)，并利用抗差最小二乘擬合的邊緣點(diǎn)中心作為標(biāo)靶的中心坐標(biāo)。

1 標(biāo)靶點(diǎn)云預(yù)處理

1.1 標(biāo)靶點(diǎn)云提取

平面標(biāo)靶的有效反射區(qū)域一般采用高反光材料(如玻璃微珠型或微晶棱鏡型反光材料)制成，其反射系數(shù)比普通白色材料高出數(shù)百倍甚至上千倍，故可利用回光強(qiáng)度信息將標(biāo)靶點(diǎn)云從周圍背景中提取出來[9]。分兩步提取標(biāo)靶點(diǎn)云：

1)人工大致選擇包含標(biāo)靶數(shù)據(jù)的點(diǎn)云區(qū)域，得到粗略標(biāo)靶點(diǎn)云。

2)依據(jù)回光強(qiáng)度信息精確提取平面標(biāo)靶點(diǎn)云。

1.2 標(biāo)靶最佳平面擬合

由于激光光斑效應(yīng)，在掃描線與目標(biāo)邊緣相切的區(qū)域會(huì)存在拖尾現(xiàn)象[10]，使得數(shù)據(jù)中存在粗差。同時(shí)由于掃描儀的測距誤差以及外界環(huán)境的干擾，平面標(biāo)靶點(diǎn)云不是嚴(yán)格位于一個(gè)平面上[11]，而是具有一定的厚度，如圖 1所示。設(shè)標(biāo)靶平面方程表達(dá)式為

ax+by+cz+e=0.

(1)

式中：a，b，c為平面的法向量元素。

(2)

(3)

若|di|>2δ，則認(rèn)為該點(diǎn)是粗差點(diǎn)，刪除該點(diǎn)。剔除粗差前后標(biāo)靶點(diǎn)云如圖 1所示。對剩余的點(diǎn)云進(jìn)行最佳平面擬合。最后把所有的點(diǎn)云沿平面法向投影到標(biāo)靶最佳平面，如圖2所示。

圖1 剔除粗差前后標(biāo)靶點(diǎn)云

圖2 標(biāo)靶最佳平面

1.3 坐標(biāo)旋轉(zhuǎn)

為了在二維平面對三維面狀信息進(jìn)行提取和計(jì)算，將標(biāo)靶最佳平面旋轉(zhuǎn)至與xoy平面平行。標(biāo)靶最佳平面上的點(diǎn)云旋轉(zhuǎn)到平行于xoy坐標(biāo)面的平面的旋轉(zhuǎn)矩陣為[12]

(4)

則標(biāo)靶點(diǎn)云在平行于xoy坐標(biāo)面的平面S上的坐標(biāo)為

(5)

2 標(biāo)靶中心定位

2.1 邊緣點(diǎn)提取

精掃的平面標(biāo)靶點(diǎn)云數(shù)據(jù)量較大，能夠準(zhǔn)確地反映標(biāo)靶的幾何信息，但是其中大部分的點(diǎn)云是冗余的。而標(biāo)靶的邊緣點(diǎn)包含足夠的標(biāo)靶幾何信息，且數(shù)據(jù)量又小，故本文用邊緣點(diǎn)計(jì)算標(biāo)靶中心坐標(biāo)。

為提高邊緣點(diǎn)提取的效率和準(zhǔn)確度，本文引入凸包算法。凸包是計(jì)算幾何中的概念，若平面上包含有限個(gè)點(diǎn)的點(diǎn)集為Q，則其凸包是包含Q的最小凸多邊形[13]。平面標(biāo)靶的幾何形狀為標(biāo)準(zhǔn)的圓形，標(biāo)靶的邊緣點(diǎn)可以看成標(biāo)靶點(diǎn)云凸包點(diǎn)的集合。用凸包算法提取標(biāo)靶邊緣點(diǎn)時(shí)不受標(biāo)靶內(nèi)部點(diǎn)云缺失的影響，且可以自動(dòng)濾除掉因標(biāo)靶邊緣數(shù)據(jù)缺失而產(chǎn)生的非邊緣點(diǎn)。凸包算法提取的標(biāo)靶凸包點(diǎn)如圖3所示。

圖3 點(diǎn)云凸包示意圖

2.2 抗差最小二乘圓擬合

本文處理的平面標(biāo)靶考慮數(shù)據(jù)缺失和冗余的情形，傳統(tǒng)的最小二乘不能抵抗粗差影響，不能實(shí)現(xiàn)標(biāo)靶的穩(wěn)健定位。RANSAC雖然具有較強(qiáng)的抗差性，但是算法的可靠性和效率不能保證。為增強(qiáng)結(jié)果的穩(wěn)定性和可靠性，本文采用基于IGG3權(quán)函數(shù)的抗差最小二乘法。

二維平面上，設(shè)圓上的點(diǎn)為p(xi,yi)，則有

(xi-x0)2+(yi-y0)2=r2.

(6)

式中：r為半徑；x0，y0為圓心。則誤差方程為

vi=f(x0,y0,r)=

(7)

上式是非線性方程，不能直接求解，利用泰勒級數(shù)展開，省略二次以上項(xiàng)，可得線性化方程

(8)

寫成矩陣形式為

(9)

(10)

為“充分利用有效信息，限制利用有害信息，排除有害信息”，提高平面圓參數(shù)求解的精度，抗差權(quán)函數(shù)選擇為IGG3函數(shù)，即

(11)

3 實(shí)驗(yàn)及分析

測試算法效果，用Riegl VZ400掃描儀及其配套的平面標(biāo)靶進(jìn)行實(shí)驗(yàn)。在實(shí)驗(yàn)室墻壁粘貼平面標(biāo)靶，架設(shè)掃描儀。先對整個(gè)實(shí)驗(yàn)室進(jìn)行粗掃，然后對標(biāo)靶所在區(qū)域進(jìn)行精掃，最后對精掃的標(biāo)靶點(diǎn)云進(jìn)行中心定位。實(shí)驗(yàn)過程中IGG3權(quán)函數(shù)中驗(yàn)前單位權(quán)中誤差取經(jīng)驗(yàn)值為0.001 m，根據(jù)多次試驗(yàn)k0，k1分別取值為1.5和5，取標(biāo)靶點(diǎn)云坐標(biāo)均值為中心坐標(biāo)的初值。

3.1 完整標(biāo)靶中心定位

當(dāng)標(biāo)靶點(diǎn)云數(shù)據(jù)完整且密集時(shí)，重心法求解的標(biāo)靶中心坐標(biāo)精度高且穩(wěn)定可靠[1,5, 8,14]，本文以剔除粗差后的完整標(biāo)靶點(diǎn)云重心坐標(biāo)為基準(zhǔn)值。選取5個(gè)掃描質(zhì)量較高的標(biāo)靶點(diǎn)云，分別用重心法、文獻(xiàn)[8]算法和本文算法計(jì)算標(biāo)靶中心坐標(biāo)以及標(biāo)靶中心坐標(biāo)與基準(zhǔn)值之間的偏差Δd，結(jié)果如表 1所示。

從表1可知，對于一般情況下的完整標(biāo)靶點(diǎn)云數(shù)據(jù)，本文算法、文獻(xiàn)[8]算法與重心法中心定位結(jié)果相比差值均在亞毫米級，最大的差值分別為0.5 mm和0.6 mm，且文獻(xiàn)[8]算法和本文算法的中心定位精度都能達(dá)到0.4 mm。表明當(dāng)平面標(biāo)靶數(shù)據(jù)完整時(shí)，本文算法正確有效，且可以認(rèn)為本文算法、文獻(xiàn)[8]算法和重心法的中心定位精度一致。

本文算法中心定位耗時(shí)包括標(biāo)靶點(diǎn)云旋轉(zhuǎn)、邊緣點(diǎn)提取以及標(biāo)靶中心擬合耗時(shí)，而文獻(xiàn)[8]算法主要包括邊緣點(diǎn)提取和圓心擬合耗時(shí)。用本文算法和文獻(xiàn)[8]算法定位上述5個(gè)標(biāo)靶中心，時(shí)間消耗如表2所示。

表1 完整平面標(biāo)靶中心坐標(biāo)

表2 中心定位耗時(shí)統(tǒng)計(jì) s

從表 2可知，本文算法在標(biāo)靶點(diǎn)云旋轉(zhuǎn)時(shí)需要遍歷所有點(diǎn)，故此階段時(shí)間消耗較長，是總耗時(shí)的主要組成部分，而在邊緣提取和圓心擬合時(shí)只有少部分的標(biāo)靶點(diǎn)參與計(jì)算，故時(shí)間消耗很短。文獻(xiàn)[8]算法提取邊緣點(diǎn)時(shí)需要把所有標(biāo)靶點(diǎn)的空間直角坐標(biāo)轉(zhuǎn)換成極坐標(biāo)，且要再次遍歷所有點(diǎn)才能求出分列點(diǎn)云的極值，故耗時(shí)較長；在圓心擬合階段，需要先找到滿足閾值的局內(nèi)點(diǎn)，否則就要多次迭代，最后還需用所有的局內(nèi)點(diǎn)擬合圓心，故該階段耗時(shí)也比本文算法圓心擬合耗時(shí)長。從中心定位總時(shí)間來看，本文算法耗時(shí)較文獻(xiàn)[8]降低了一個(gè)數(shù)量級，算法效率得到提高。

3.2 低質(zhì)量標(biāo)靶中心定位

為了分析標(biāo)靶點(diǎn)云數(shù)據(jù)缺失或冗余時(shí)本文算法的定位結(jié)果，以1號標(biāo)靶點(diǎn)云為基礎(chǔ)，刪除標(biāo)靶部分點(diǎn)云或者增加多余點(diǎn)云，得到7種類型的標(biāo)靶點(diǎn)云，以此來模擬實(shí)際掃描時(shí)獲取的低質(zhì)量平面標(biāo)靶數(shù)據(jù)。各種低質(zhì)量標(biāo)靶類型，以及文獻(xiàn)[8]算法(第二行)和本文算法(第三行)提取的邊緣點(diǎn)如圖4所示(圖中實(shí)心圓表示參與圓心擬合的邊緣點(diǎn)，空心圓表示未參與圓心擬合的邊緣點(diǎn))。

圖4 不同類型標(biāo)靶及其邊緣點(diǎn)

從圖4可知，本文算法和文獻(xiàn)[8]算法都可準(zhǔn)確地提取標(biāo)靶邊緣點(diǎn)。本文算法可以自動(dòng)過濾掉因?yàn)閿?shù)據(jù)缺失而產(chǎn)生的“偽”邊緣點(diǎn)，能夠剔除邊緣點(diǎn)中的部分粗差數(shù)據(jù)，因?yàn)槿哂帱c(diǎn)云而遺漏掉少數(shù)邊緣點(diǎn)。文獻(xiàn)[8]邊緣點(diǎn)提取算法不能剔除粗差，邊緣點(diǎn)中的粗差點(diǎn)多于本文算法，而且提取的邊緣點(diǎn)隨分列參數(shù)的變化而變化，圖中結(jié)果為分列參數(shù)設(shè)置為20時(shí)的結(jié)果。雖然兩者提取的邊緣點(diǎn)都含有粗差點(diǎn)，但由于圓心擬合算法的抗差性，這些粗差點(diǎn)并未參與圓心擬合。

用文獻(xiàn)[8]算法和本文算法計(jì)算的上面7種類型的低質(zhì)量平面標(biāo)靶中心坐標(biāo)、與基準(zhǔn)值(1.373 1,0.465 1，-0.320 4)的差值以及時(shí)間消耗如表3所示。

表3 低質(zhì)量平面標(biāo)靶中心坐標(biāo)

當(dāng)標(biāo)靶點(diǎn)云數(shù)據(jù)缺失或冗余時(shí)，重心法不能準(zhǔn)確計(jì)算標(biāo)靶中心坐標(biāo)。但是從表 3可知，不管平面標(biāo)靶點(diǎn)云數(shù)據(jù)在標(biāo)靶內(nèi)部或邊緣缺失，還是在標(biāo)靶邊緣存在冗余點(diǎn)云，亦或邊緣點(diǎn)云既有缺失又有冗余，由于本文算法和文獻(xiàn)[8]算法具有抗差性，可以剔除邊緣點(diǎn)中的粗差，故仍可以準(zhǔn)確計(jì)算出標(biāo)靶中心坐標(biāo)。兩種算法定位精度相當(dāng)，計(jì)算結(jié)果與基準(zhǔn)值差值均在亞毫米級。但文獻(xiàn)[8]算法耗時(shí)較長，算法效率有待進(jìn)一步提高。同時(shí)文獻(xiàn)[8]算法隨機(jī)選取局內(nèi)點(diǎn)，其計(jì)算結(jié)果具有一定的隨機(jī)性。因此本文算法效率高，計(jì)算結(jié)果穩(wěn)定可靠。

4 結(jié)束語

本文研究激光掃描儀圓形平面標(biāo)靶點(diǎn)云數(shù)據(jù)缺失或冗余時(shí)的中心定位算法，提出一種穩(wěn)健的標(biāo)靶中心定位算法。算法先提取標(biāo)靶邊緣點(diǎn)，再用抗差最小二乘法計(jì)算標(biāo)靶中心坐標(biāo)。實(shí)驗(yàn)結(jié)果表明，當(dāng)平面標(biāo)靶點(diǎn)云數(shù)據(jù)完整時(shí)，本文算法定位結(jié)果與重心法和文獻(xiàn)[8]精度相當(dāng)；當(dāng)平面標(biāo)靶點(diǎn)云缺失或者冗余時(shí)，本文仍然能準(zhǔn)確計(jì)算標(biāo)靶中心坐標(biāo)；同時(shí)本文算法耗時(shí)小于文獻(xiàn)[8]算法。但是標(biāo)靶點(diǎn)云提取需要人工操作，下一步需要研究標(biāo)靶點(diǎn)云的自動(dòng)提取，同時(shí)本文算法只適用于圓形平面標(biāo)靶，尚不能定位矩形類等非圓形標(biāo)靶中心。

[1] 官云蘭, 程效軍, 陳曉勇,等. 地面Lidar平面標(biāo)靶穩(wěn)健定位[J]. 激光雜志，2015, 36(1): 13-16.

[2] LICHIT D D, STEWART M P, SAKIRI M. Benchmark Tests on a Three-dimensional Laser Scanning System [J]. Geomertrics' Research Australasia. 2000, 72: 1-23.

[3] 王力, 李廣云, 張洪新. 基于回光強(qiáng)度的平面標(biāo)靶自動(dòng)識別方法[J]. 紅外激光與工程,2010, 40(10): 1910-1913.

[4] 劉燕萍, 賈東峰. 基于點(diǎn)云屬性信息的平面標(biāo)靶特征提取[J]. 中國圖象圖形學(xué)報(bào),2015, 20(6): 815-821.

[5] 陳俊杰, 閆偉濤. 基于激光點(diǎn)云的平面標(biāo)靶中心坐標(biāo)提取方法研究[J]. 工程勘察,2013(8): 53-57.

[6] 陳西江, 花向紅, 楊榮華, 等. 分帶K-均值聚類的平面標(biāo)靶定位[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2013, 38(2): 167-170.

[7] 朱寧寧, 盧小平, 李向陽, 等. 一種平面靶心的提取算法[J]. 大地測量與地球動(dòng)力學(xué),2014, 34(3): 173-177.

[8] 薛曉璐, 林歡. 基于RANSAC的殘缺平面標(biāo)靶穩(wěn)健定位方法[J]. 測繪工程,2016, 25(4): 51-54.

[9] 張啟福. 地面三維激光掃描儀性能測試方法研究[D]. 鄭州: 信息工程大學(xué), 2012.

[10] 王力. 車載三維激光掃描系統(tǒng)集成與QA/QC技術(shù)研究[D]. 鄭州: 信息工程大學(xué), 2014.

[11] 蘇曉蓓, 郝剛. 地面三維激光掃描標(biāo)靶中心識別算法研究[J]. 城市勘測,2010(3): 68-70.

[12] 王果. 不同平臺(tái)激光點(diǎn)云數(shù)據(jù)面狀信息自動(dòng)提取研究[D]. 北京: 中國礦業(yè)大學(xué), 2011.

[13] 汪嘉業(yè), 王文平, 屠長河, 等. 計(jì)算幾何及應(yīng)用[M]. 北京: 科學(xué)出版社, 2011.

[14] 孫鵬, 閆陽陽, 牛路標(biāo), 等. 地面激光掃描儀自制平面標(biāo)靶中心識別算法研究[J]. 河南城建學(xué)院學(xué)報(bào),2014, 23(2): 54-57.