李子寬，廖 威，藍秋萍

?

基于球心點互斥的球目標識別方法

李子寬1，廖 威2，藍秋萍1

(1. 河海大學地球科學與工程學院，江蘇 南京 211100；2. 寧波市規(guī)劃設計研究院，浙江 寧波 315042)

提出了一種基于球心點互斥的球目標識別方法，用于從大場景三維點云中自動識別未知個數(shù)和未知半徑的球目標。首先，根據(jù)專門設計的球面點響應函數(shù)濾除大量非球面點，并根據(jù)法向與曲率將剩余的球面點映射到球心位置；然后，構建用以描述局部密度漸變規(guī)律的球心點互斥樹，通過剪枝操作將其分裂成若干子樹，其分別對應不同球目標的球心點聚類；最后，根據(jù)球心點局部密度和球面點覆蓋率估計值確認真實存在的球目標。實驗結果表明：基于球心點互斥的球目標識別方法能夠有效解決大場景三維點云中球目標的識別問題，即使是存在嚴重遮擋的情況下，暴露表面不足整個球面6%的球目標也都能夠被識別出來。

球目標識別；球面點響應函數(shù)；球心點互斥；聚類；球面覆蓋率

球形具有良好的幾何特性[1]，在光學相機標定[2]、機器人手臂引導[3]、骨外科手術[4]等基于目標識別的應用中，被廣泛用作合作目標的首選形狀。因此，利用二維影像識別和定位球形目標或表面的方法研究已經取得了許多應用成果。隨著三維激光掃描和立體視覺技術的持續(xù)發(fā)展，三維點云中球目標識別方法也開始受到越來越多的關注。

受到二維影像邊緣檢測方法的啟發(fā)，WANG等[5]和BENLAMRI[6]將三維點云中球目標識別轉化為二維深度圖像上的圓形邊緣檢測問題，通過尋找深度不連續(xù)的邊緣來識別場景中的球目標。但是，該方法要求目標邊緣完全暴露，不能被遮擋。為了能夠在雜亂場景中準確定位被遮擋的目標，MARSHALL等[7]設計了直接針對三維點云的試探性擬合方法，并根據(jù)擬合結果挑選最匹配模型完成點云分割。文獻[8]則采用隨機采樣一致性(random sample consensus，RANSAC)算法分割橢球面，即：在三維點云中反復選取不同采樣點，根據(jù)每次采樣點構建假設模型及評價模型與點云的一致性，并依據(jù)一致性從高到低的順序逐步完成點云分割。這兩種通過反復試探和檢驗尋找目標的方法，能夠解決小規(guī)模點云的分割問題，卻并不適用于大場景中小目標的識別問題。

本文提出了一種根據(jù)映射球心點局部密度變化規(guī)律的球目標識別方法。該方法不需要預先假設場景中球目標的個數(shù)和尺寸，能夠準確識別雜亂環(huán)境中被嚴重遮擋的球目標。識別過程只需要若干僅憑直覺即可設置的簡單參數(shù)，并且能夠自動適應不同密度的三維點云，高效率地完成大場景中多個球目標的識別任務。

1 方法

與其他的幾何形狀均不同，球形具有唯一的中心，并且依據(jù)法向和曲率，球面上的每一個點都能夠映射到球心點上[9]。針對這一特性，本文提出了一種讓真實球目標的球心位置出現(xiàn)顯著高密度映射點的方法；并專門設計了一種描述映射球心點密度變化規(guī)律的樹形結構，根據(jù)鄰近球心點之間的互斥特性將樹分割成若干子樹，且每個子樹對應一個球目標；最后根據(jù)原始點云在球面上的覆蓋率確認場景中真實存在的球目標。

1.1 映射球心點

為了使正確的球心位置能夠產生密度顯著高于其他位置的映射球心點分布，本文設計了一種有效的球面點響應函數(shù)，如式(1)，其中主曲率1和2為輸入量；為球面響應值，即

球面點存在穩(wěn)定的映射關系：法線所在直線經過球心，且兩個主曲率相等且倒數(shù)等于球面點到對應球心點的距離。據(jù)此，設計了從疑似球面點至球心點映射的方法。如圖1所示，對于一個疑似球面點，沿著法向的相反方向，計算映射球心點，即

其中，代表取絕對值。

1.2 球心點互斥

球面響應函數(shù)僅對局部形狀類似于球面的點輸出正值，因此能夠濾除大部分非球面點，使球面以外的區(qū)域被顯著稀釋；而隨后的球心點映射計算可使剩余點中真正的球面點進一步向各自的球心匯聚。因此，真實球目標的球心位置會出現(xiàn)比其他位置更加顯著的映射點聚集現(xiàn)象。不同于一般空間點，映射點是位于球心位置的假想點，只有當兩球心點之間的距離大于各自對應球目標的半徑之和時，其才能夠同時存在。針對該特征，本文設計了一種球心點互斥方法，能夠快速找出高密度的球心點聚類，每一個聚類對應一個可能的目標球，而聚類中心則是最有可能的球心點位置。

1.2.1 球心點互斥樹

其中，d是c與另一個球心點c之間的距離；與分別為點c與c的局部密度。本文采用一種簡便的局部密度計算方法，統(tǒng)計與c的距離小于指定值dc的球心點個數(shù)，將其作為c的局部密度。

以圖2所示的32個映射球心點分布為例，按照上述方法建立球心點互斥樹，如圖3所示?；コ鈽渖弦粋€節(jié)點代表一個球心點，節(jié)點圓圈中記錄了球心點編號和對應的球目標半徑，例如根節(jié)點記錄了1號球心點和其對應的半徑為1.92?；コ鈽渲忻恳粭l邊都連接著兩個節(jié)點，其中上層節(jié)點是下層節(jié)點的父節(jié)點，即：上層節(jié)點是與之相連的下層節(jié)點的最近且密度更高的球心點。每條邊都具有一個距離屬性值，記錄了其所連接的兩個點之間的距離，例如1號點與31號點的連接邊記錄了其之間的距離為4.16。

圖2 映射球心點分布圖

圖3 球心點互斥樹

1.2.2 球心點互斥

從下往上看，互斥樹中的邊-連接了一個下層點c和一個上層點c，c是距離c最近的更高密度點。如果c與c的距離非常近，則可以認定其對應同一個球目標，由于<，c比c更加靠近真實的球心位置，于是可排除c是真實球心的可能性；如果c與c的距離較遠，例如大于其半徑之和，那么c與c很可能來自于兩個不同的球目標，可以共存，與其各自代表一個球目標的可能性不能被排除。這種距離近則相互排斥的現(xiàn)象類似于同性電荷互斥的現(xiàn)象，因此，可將其稱為球心點互斥。

基于互斥樹的球心點互斥算法可描述為：當邊-的距離屬性d小于其所連接的兩個球心點半徑之和(r+r)時，即：d<r+r，認定c與c來自同一個球，且上層點c比下層點c更靠近球心，c作為c的父節(jié)點是非常合理的，邊-被保留下來；當d≥r+r時，c和c很可能來自兩個不同的球，c作為c的父節(jié)點不再合理，斷開邊-?？紤]到球心點坐標和球半徑都會存在估計誤差，所以設定一個調節(jié)因子，當d<×(r+r)時，保留該邊；當d≥×(r+r)時，則斷開該邊。本文實驗取=0.7。

經過球心點互斥后，圖3中的15-1、31-1、23-1、30-15、29-23這5條連接邊會被斷開，如圖4中的虛線邊?；コ鈽浔环殖?個子樹，其根節(jié)點分別是1、15、23、29、30、31，如圖4中灰色填充的節(jié)點。每個子樹對應著同一個球目標，其根節(jié)點的局部密度在該子樹的所有節(jié)點中最高，所以根節(jié)點所對應的球目標估計參數(shù)具有最高的可信度。其中，節(jié)點1、15和23的確是圖2中3個顯著聚類的聚類中心，而29、30、31則是由于距離這3個聚類較遠，位于安全距離之外，所以在互斥計算中才被保留了下來。

圖4 經互斥計算后的球心點互斥樹

球面點向球心點的映射，使真實球心位置的局部密度顯著高于原始點云的點密度；而球面響應函數(shù)會顯著稀釋非球面點，從而致使非球面位置的映射球心點密度低于原始點云密度。所以，以原始點云的平均點密度0作為閾值，能夠進一步排除那些孤立點形成假性聚類中心，如圖2中29、30、31號球心點。

1.3 確認球目標

除了真正的球面之外，雜亂場景中大量不規(guī)則表面也會偶然引起映射點的聚集現(xiàn)象，所以針對上一步得到的聚類中心點，還需要進一步確認對應球目標是否真實存在。本文根據(jù)原始點云在球目標表面的覆蓋率確認球目標，具體做法是：從原始點云中找出位于球目標表面且與球面法向一致的點，計算這些點覆蓋面積占整個球面的比率，將覆蓋率較低的球目標排除掉。

為一個百分比數(shù)值，其值越大說明目標球存在的概率越大。而且，非常容易被人類感知，即使不知道點云密度和球目標半徑的精確數(shù)據(jù)，通過在掃描儀視角上的簡單觀察，就可以輕松地給出一個合適的閾值，用以最終確認球目標。即使是毫無先驗知識的未知場景，為了確保球目標識別結果的可靠性，也可以給出一個與球目標半徑和掃描密度無關的閾值。例如：為了進一步提高球目標的定位精度，可以根據(jù)這個球面點重新進行球面擬合計算[10]，得到更加精確的幾何參數(shù)，為了確保擬合計算結果的精確性，可以在密度閾值0的基礎上設置更加嚴格的覆蓋率閾值，即：只有大于10%的球目標才被認定為可靠的球目標，其重新擬合的計算結果才具有較高的可信度。

2 實驗與分析

在閱覽室布置了如圖6(a)所示的實驗場景。場景中放置了8個不同半徑的球目標，其中，2#、3#和7#球都存在較嚴重的遮擋，5#和6#球彼此接觸。利用TrimbleGX200三維激光掃描儀在拍攝照片的位置掃描場景，采集到約141萬個點，其中真實球面點在整幅點云中的比例少于0.4%。

采用文獻[9]中的方法計算點云中每一個點的法向、高斯曲率和平均曲率。設定=0.15，=0.0001，根據(jù)式(2)計算每個點的球面響應值，并濾除超過94%的非球面點，剩余84404個疑似球面點。針對疑似球面點利用式(3)計算映射球心點坐標，將映射球心點疊加顯示到原始點云中，如圖6(b)所示，可以觀察到在8個真實球心附近出現(xiàn)了較為明顯的聚類現(xiàn)象，同時在桌椅的棱角位置也出現(xiàn)了一些高密度球心點。

圖6 實驗場景照片以及映射球心點分布

通過球心點互斥計算，又有超過98%的點被排除掉，剩余1447個聚類中心點。將其按照局部密度由高至底排序，局部密度最高的前50個點如圖7(a)所示，其中有18個點的局部密度高于原始掃描點云密度0=52.4。根據(jù)這些聚類中心建球模型，其在空間中的分布如圖7(b)所示，密度最高的8個聚類中心在空間上位于8個真實球目標的球心附近，其余10個高密度聚類中心則分布于桌角、椅背頂端等可能引起映射點聚集的易混淆區(qū)域上。觀察圖7(a)可以發(fā)現(xiàn)，除了遮擋非常嚴重的3#球之外，7個球目標的聚類中心密度都在原始點云平均密度的3倍以上，3#球的暴露面積不足整個球面的6%，對應映射球心點的局部密度為70。而在所有聚類中心點中，另外1439個非球心點的平均密度只有5.29，約為原始點云密度的1/10，標準差為8.24。因此，以原始點云的平均密度作為閾值能夠有效地排除大量非球心點，并且確保真實球心點不會被錯誤地排除掉。

最后，針對18個高于0的高密度聚類中心點利用式(5)計算球面點覆蓋率。設定1=3 cm，2=5°，為每一個聚類中心點找出可靠地球面點。場景中8個真實球目標的實際半徑、識別出的球面點個數(shù)、覆蓋率都記錄在表1中。其中2#和3#球遮擋較為嚴重，分別為8.7%和5.6%，其余真實球目標的均在25%以上。而另外10個桌椅棱角附近的高密度聚類中心，由于找不到足夠多的可靠球面點，覆蓋率均小于0.1%，所以很容易與真實球目標區(qū)分開來。對分割出的可靠球面點重新擬合球面，得到精確的球心點坐標和半徑，其與真實值的偏差值見表1。由于遮擋較為嚴重的2#和3#球，覆蓋率在8個真實球目標中也最低，半徑與球心點坐標的估計誤差都明顯大于其他球。所以，對于識別出的球目標，如果球面點覆蓋率較小，例如小于10%，那么其重新擬合后的半徑估計值和球心定位值的可靠性會較低，在后續(xù)應用中建議慎重考慮這些球目標。

圖7 映射球心點密度降序排列及識別出的目標球分布

表1 各個球目標的相關參數(shù)統(tǒng)計值

考慮到本文球目標識別方法與文獻[9]有相似地執(zhí)行策略，所以可利用文獻[9]的桌面場景，對比兩種方法的計算效率和球目標識別精確性。桌面場景掃描點云如圖8所示，掃描得到51896個點，場景中布置了5個球目標，落在球面上的掃描點約占整幅點云的30%。采用相同方法估計點云的法向和曲率，然后利用本文響應函數(shù)和文獻[9]的主曲率比較方法分別識別出14088個和14736個可能的球面點，并推算可能的球心點。應用本文的球心點互斥聚類方法(mutual exclusion semaphores, MutEx)和文獻[9]的層次聚類方法(hierarchical agglomerative clustering, HAC)針對各自的推算球心點計算聚類中心。MutEx聚類耗時15.75 s，得到10個聚類中心；而HAC聚類耗時749.1 s，得到104個聚類。對應5個真實球目標的聚類計算結果見表2，其中Δ與Δ的含義與表1相同，SN/total代表“在聚類結果中的排序/聚類結果總數(shù)”，本文的MutEx聚類根據(jù)聚類密度排序，HAC聚類根據(jù)類內點個數(shù)排序。

圖8 包含5個球目標的桌面場景掃描點云

表2 本文MutEx聚類與文獻[9]HAC聚類實驗結果

由于MutEx依據(jù)局部密度對聚類結果排序，并利用原始點云密度作為閾值排除低密度聚類，所以僅得到10個聚類結果，且對應于5個真實球目標的聚類依據(jù)局部密度均排在最前面。而HAC僅以類內點個數(shù)作為判別聚類結果可靠性的依據(jù)，所以除了2#球對應聚類排在聚類結果第1位之外，其他4個球目標都未獲得區(qū)別于其他錯誤聚類的顯著性優(yōu)勢。MutEx直接采用聚類最高密度點的坐標和半徑作為對應球目標的球心點坐標和半徑，不容易受到類內大誤差點的影響；而HAC采用了類內求平均的方法，位于聚類邊緣位置的大誤差點會影響球目標參數(shù)的精度。因此，除了無遮擋的3#球之外，其余4個球目標的HAC球心定位與半徑估計精度均低于本文MutEx方法。另嘗試利用文獻[9]的方法識別本文閱覽室場景中的8個球目標，在經歷超過1.5 h的運算后得到超過1810個聚類，由于嚴重地遮擋和太少的球面點個數(shù)，最終未能在其中找到能夠正確對應8個球目標的聚類。

本文實驗所使用計算機配置了Inteli7-6700HQ型號CPU(主頻2.6 GHz)和16 GB內存，計算程序由C++語言編寫，編譯為64位Release版可執(zhí)行程序，程序對輸入點云建立八叉樹空間索引，點云微分屬性計算與球心點互斥聚類皆利用八叉樹優(yōu)化鄰近點查詢效率。針對上述兩幅實驗點云圖，本文方法各步驟計算耗時見表3。

表3 本文方法各步驟計算耗時

3 結 論

為了解決大場景中球目標的識別問題，本文設計了一個以曲率為輸入量的球面點響應函數(shù)，能夠快速排除大部分非球面點；而與這種非球面點的稀釋作用相反，利用法向和曲率的球心點映射過程卻讓球面點大量匯聚于球心位置，從而使真實球目標的中心位置產生顯著高于周圍的映射點聚集現(xiàn)象。為正確識別這些聚類，還提出了球心點互斥的映射球心點自動聚類算法。與現(xiàn)有聚類方法不同，其構建了一個用以描述最鄰近高密度點的樹狀結構，根據(jù)球心點之間的互斥特性對樹進行快速剪枝，剪枝形成的子樹即為球心點的自動聚類結果，而子樹的根節(jié)點則是最有可能的球心點位置。通過對球心點局部密度和原始點云在對應球目標表面的覆蓋率估計，最終確認場景中的球目標。這種聚類方法僅以原始點云的自然密度作為閾值，能夠自動適應不同密度的點云，聚類結果與實際球目標的分布相一致。

利用真實場景掃描點云的實驗結果證明，與現(xiàn)有的基于球心點聚類的球目標識別方法相比，在解決小場景中大占比球目標的識別問題時，本文方法具有更高地識別準確率和定位精度；而在解決大場景中小目標的識別問題時，更表現(xiàn)出突出的效率優(yōu)勢；同時，具有極強的敏感性，即使是在嚴重遮擋的情況下，場景中的小型球目標也都能夠被準確地識別出來。

[1] YUN D, KIM S, HEO H, et al. Automated registration of multi-view point clouds using sphere targets [J]. Advanced Engineering Informatics, 2015, 29(4): 930-939.

[2] HUNTLEY J M. Fast Hough transform for automated detection of spheres in three-dimensional point clouds [J]. Optical Engineering, 2007, 46(5): 051002-1-051002-11.

[3] KHARBAT M, AOUF N, TSOURDOS A, et al. Sphere detection and tracking for a space capturing operation [C]// IEEE Conference on Advanced Video and Signal Based Surveillance. Los Alamitos: IEEE Computer Society Press, 2007: 182-187.

[4] MARJOLEIN V D G, FRANS M V, CHARL P B, et al. Determination of position and radius of ball joints [C]// Medical Imaging 2002 Conference. Bellingham: SPIE- International Society for Optical Engineering, 2002: 1571-1577.

[5] WANG A Y, SHI H, ZHANG Y, et al. Automatic registration of laser point cloud using precisely located sphere targets [J]. Journal of Applied Remote Sensing, 2014, 8(1): 5230-5237.

[6] BENLAMRI R. Curved shapes construction for object recognition [C]//Geometric Modeling and Processing — Theory and Applications. Los Alamitos: IEEE Computer Society Press, 2002: 197.

[7] MARSHALL D, LUKACS G, MARTIN R. Robust segmentation of primitives from range data in the presence of geometric degeneracy [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2001, 23(3): 304-314.

[8] 程志全, 葉永凱, 李寶. 一種基于RANSAC框架的橢球提取算法[J]. 圖學學報, 2012, 33(2): 68-71.

[9] 李嘉, 阿依古麗?阿曼, 鄭德華. 復雜場景三維點云中未知球形目標的自動識別方法[J]. 計算機輔助設計與圖形學學報, 2013, 25(10): 1489-1495.

[10] 李勝男, 林曉, 陳言, 等. 基于點云的球面三維逆向建模[J]. 圖學學報, 2013, 34(3): 49-52.

Spherical Target Recognition Method Based on Mutual Exclusion of Spherical Centers

LI Zikuan1, LIAO Wei2, LAN Qiuping1

(1. School of Earth Sciences and Engineering, Hohai University, Nanjing Jiangsu 211100, China; 2. Ningbo Urban Planning and Design Institute, Ningbo Zhejiang 315042, China)

A new spherical target recognition method based on mutual exclusion of sphere centers is proposed to solve the automatically identification problems of unknown number and unknown radius targets in large-scale 3D point clouds. First, an effective spherical point response function is specially designed to remove most of aspheric points, and every remaining spherical point is mapped to a sphere center by taking advantage of its normal and curvatures. Then, a novel tree-like structure for describing distribution and local density change rules of these centers is constructed, through a series of pruning operation complying with the mutually exclusion relationships between different sphere centers, the tree is split into several sub-trees, and a sub-tree correspond to a possible sphere target. Finally, the real sphere is confirmed by the local density of the root node of sub-tree and the coverage rate of points on the sphere surface. The experimental results demonstrate that the proposed sphere recognition method based on the mutual exclusion of sphere centers can effectively identify and precisely loc ate various spherical targets in a large and cluttered scene. Even in the case of serious occlusion, such as the exposed surface is less than 6%, the sphere can also be robustly identified.

spherical target recognition; spherical point response function; spherical center mutual exclusion; clustering; spherical coverage

TP 391

10.11996/JG.j.2095-302X.2018010050

A

2095-302X(2018)01-0050-07

2017-05-23；

2017-06-24

國家自然科學基金項目(41301406，41201439)；江蘇省自然科學基金項目(BK20130829)

李子寬(1995–)，男，山西汾陽人，本科生。主要研究方向為點云數(shù)據(jù)處理與應用。E-mail：lzkcqz@163.com

藍秋萍(1982–)，女，浙江衢州人，講師，博士。主要研究方向為三維點云數(shù)據(jù)處理與三維建模。E-mail：lanqiuping@hhu.edu.cn