改進的Hough變換提取點云數據球面特征

安　麗,游俊甫,官云蘭

(東華理工大學 測繪工程學院，江西 南昌 330000)

?

改進的Hough變換提取點云數據球面特征

安麗,游俊甫,官云蘭

(東華理工大學 測繪工程學院，江西 南昌 330000)

摘要：提出一種改進的Hough變換用于提取點云數據中的球面特征。該方法運用“4點定位法”與Hough變換基本方法相結合，可以快速定位球心坐標和球半徑并提取出球面點。為驗證方法的有效性，通過Matlab建立含噪點云仿真模型，對基本方法和改進算法進行比較。實驗結果表明，提取點云數據的球面特征采用改進Hough變換算法速度更快、效率更高。

關鍵詞：點云；Hough變換；噪聲；克拉默法則；球面特征提取

在逆向工程中,從點云數據中進行特征提取成為模型重建的一個重要環節。1962年，Paul Hough提出一種從圖像空間到參數空間的變換方法，即Hough變換，該方法對于提取直線特征有著較好的容錯性和魯棒性[1]，并且有很多改進算法[2-3]。在三維點云數據中提取平面特征、擬合平面方法上有一些研究[4-10]。本文基于Hough變換進行球面特征點提取的基本方法，提出一種改進方法，通過試驗驗證該方法的優越性。

1基于Hough變換方法提取球面特征

1.1基本Hough變換

1.1.1　基礎理論

借鑒二維平面中基于Hough變換方法提取直線的思想，可得基于Hough變換(HT)的點云數據球面特征提取的基本方法。對于球面上的每一個點Pi(xi,yi,zi)，在已知半徑的情況下進行Hough變換，點云數據空間映射為一系列球體集，即點云數據中某個點Pi(xi,yi,zi)對應于多個球心位置，即Pi(xi,yi,zi)?{Om1,n1,k1(am1,bn1,ck1)，Om2,n2,k2(am2,bn2,ck2)，…}，反之，某個球心坐標與一個點集存在對應關系，即

由于不完整球面點云空間不一定包括球心位置，擴展球心活動空間后，球心在范圍內遍歷，計算每個球心與點云中各點的距離值，與半徑值比較，給定一個球面厚度，記錄符合條件的點個數為峰值函數，通過峰值檢測得到峰值函數的極大值，提取出對應的球心坐標，然后在得到的球心位置附近繼續采用Hough變換提取新的球心坐標提高準確性，輸出球面點。首次提取球面點步驟：

Step1球心空間擴展及量化，空間大小為m×n×k;

Step2計算每個球心點Om,n,k(am,bn,ck)的對應的峰值函數A(m,n,k)。使用球面厚度為2ε，判斷條件為|disi-r|<ε;

Step3檢測A(m,n,k)的極大值;

Step4輸出對應的球面參數以及相應的點集

1.1.2　基本Hough變換的特點

基本算法可以在點云數據充足的情況下有效地提取出球面特征，但運算量比較大、耗時較長，球心坐標值需分別在各自坐標范圍內遍歷，在已知半徑并且在三維激光掃描儀獲取的點云基本達到半球(50%)的情況，才具備可行性，否則需要一定的經驗對點云空間拓展到包含球心可能的范圍。在半徑未知時，需要再加一重循環，計算量進一步加大。

1.2改進Hough變換

1.2.1　快速計算a,b,c,r數組

針對基本算法的不足，提出一種快速定位球心坐標和計算半徑值的“4點定位法”。設P1(x1,y1,z1),P2(x2,y2,z2),P3(x3,y3,z3),P4(x4,y4,z4)為點云中隨機點，構成的球面方程為

將4點坐標代入球面方程，得

處理后：

式(4)是一組以a,b,c為未知數的齊次線性方程組，通過克拉默法則進行求解。在點云數據的計算機處理中，鑒于被采集物不是絕對規則、采集時存在一定偏差、計算機處理數據時不是無限精確等因素，認為式(4)只存在唯一解。求出a,b,c值之后，代入某一點坐標即可解算出r值。多次隨機取數得到a,b,c,r數組。

1.2.2　輸出球面參數及特征點

隨機從點云數據中取出4點一組，取出多組(可能重復)，對每一組點分別計算a,b,c和r值,“投票”統計相同(接近相同)a,b,c,r值對應的組數N，取出N的最大值(Nmax)對應的a,b,c,r值。

2實驗及結果

驗證本文提出方法的正確性，采用仿真數據進行驗證。

2.1建立仿真點云模型

通過Matlab生成720點的標準球面(x2+y2+z2=1)點云，分別生成點數量為30、50、100不同的噪聲與標準球面點云分別合并成一個不同信噪比(SNR)的點云，稱為含噪球面點云。幾種點云通過Geomagic可視化，如圖1所示。

圖1　4種點云圖

2.2提取結果

基本Hough變換算法中，設定球面半徑值固定為1.000，球心活動空間a,b,c∈[-1,1]，a,b,c分辨率為0.06，只進行SNR=720∶30點云的首次提取，提取結果如表1所示；改進Hough變換算法對于每種點云，各選取10 000組“4點”，基于Matlab 2009軟件平臺，解算出了a,b,c,r值的數組，a,b,c,r值分布情況如圖2所示(以SNR=720∶30為例，縱坐標為出現的頻數)。

表1　基本Hough變換算法在點云仿真模型的提取結果(首次)

圖2　改進算法提取球面參數分布(以SNR=720∶30為例)

圖2中可以看出，各參數值非常集中，直接輸出中位數為參數值，結果見表2，3種含噪聲點云(左、中、右依次對應720∶30、720∶50、720∶100)提取結果和擬合結果如圖3、圖4所示。

表2　改進Hough變換算法在不同點云仿真模型的提取結果

圖3　基于改進Hough變換的輸出點云

圖4　基于改進Hough變換的擬合球面

從圖3可以看出，改進的Hough變換完整還原出了球面點，但仍有個別噪聲點沒有剔除，這是因為這幾個噪聲點正好落在球面上，圖4中出現的尖角是沒有剔除的個別噪聲點干擾的結果。

3結束語

在提取點云數據中的球特征時，基于Matlab平臺，通過仿真實驗對比了基本Hough變換算法和改進Hough變換算法的差異。實驗結果證明，基本Hough變換算法可以從含有噪聲點云中解算出球面參數值，但擴展球心空間需要一定經驗，耗時較長(首次解算在固定半徑值時就花費幾近三倍于改進Hough變換的時間)，偏差較大，很難同時平衡計算量和量化分辨率；改進后Hough變換算法能克服基本算法中的不足，提取結果更為精準，更加有效地提取球面參數及特征點，抗噪性能優越。

參考文獻：

[1]DUDA R O,Hart P E.Use of the HT to detect lines and curves in pictures[J].Comm.ACM,1972,(15):11-15.

[2]劉春閣.基于Hough變換的直線提取與匹配[D].阜新：遼寧工程技術大學,2009.

[3]葉峰,陳燦杰,賴乙宗,等.基于有序Hough變換的快速圓檢測算法[J].光學精密工程,2014(4):1105-1111.

[4]官云蘭,程效軍,施貴剛.一種穩健的點云數據平面擬合方法[J].同濟大學學報(自然科學版),2008(7):981-984.

[5]鄧少平,張繼賢,李平湘，等.霍夫域極化相干性的雷達影像電力線檢測[J].測繪科學，2015，40(2)：66-71.

[6]馬宏斌,王柯,馬團學.基于LiDAR點云數據的可視域計算研究[J].測繪與空間地理信息，2015，38(1)：37-40.

[7]譚敏.基于車載激光點云數據的路面檢測與重建[J].測繪與空間地理信息，2015，38(7)：115-117.

[8]BORRMANN D,ELSEBERG J,LINGEMANN K,et al.The 3D Hough Transform for Plane Detection in Point Clouds：A Review and a new Accumulator Design[J].3D Research Center and Springer 2011.3D Res.02,02003 (2011).

[9]浮丹丹,周紹光,徐洋,等.基于主成分分析的點云平面擬合技術研究[J].測繪工程,2014,23(4):20-23.

[10] YANG M Y,FORSTNER W.Plane Detection in Point Cloud Data[J].Department of Photogrammetry Institute of Geodesy and Geoinformation University of Bonn.2010.TR-IGG-P-2010-01.

[責任編輯：李銘娜]

The extraction of spherical characteristics from point cloud based on improved hough transformAN Li,YOU Junfu,GUAN Yunlan

(College of Geomatics,East China Institute of Technology,Nanchang 330000,China)

Abstract：This paper introduces a kind of method that extracts spherical characteristics from point cloud based on an improved Hough Transform (HT).The method can quickly calculate the coordinates of spherical center and the value of radius,and distilled spherical points through combining the “Four Points Calculate Parameters” and the basic HT method.In order to prove the validity of the method,the simulation data are built.Then the random noise develops from Matlab into the point cloud data.From the point cloud data,the centre coordinate values and radius value have been extracted by using the method of basic and improved HT algorithm.The experimental results show that the improved HT algorithm，which reflects the advantage of quick speed and high efficiency,is a good method to extract the spherical feature points from the point cloud data.

Key words：point cloud;Hough;noise；Cramer’s Rule；extraction of spherical surface

中圖分類號：P208

文獻標識碼：A

文章編號：1006-7949(2016)05-0074-04

作者簡介：安麗(1990-)，女，碩士研究生.

基金項目：國家自然科學基金資助項目(1401437)

收稿日期：2015-02-20；修回日期：2015-2015-08-20