基于球心點(diǎn)互斥的球目標(biāo)識(shí)別方法

李子寬，廖 威，藍(lán)秋萍

?

基于球心點(diǎn)互斥的球目標(biāo)識(shí)別方法

李子寬1，廖 威2，藍(lán)秋萍1

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

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

球目標(biāo)識(shí)別；球面點(diǎn)響應(yīng)函數(shù)；球心點(diǎn)互斥；聚類；球面覆蓋率

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

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

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

1 方法

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

1.1 映射球心點(diǎn)

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

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

其中，代表取絕對(duì)值。

1.2 球心點(diǎn)互斥

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

1.2.1 球心點(diǎn)互斥樹(shù)

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

以圖2所示的32個(gè)映射球心點(diǎn)分布為例，按照上述方法建立球心點(diǎn)互斥樹(shù)，如圖3所示?；コ鈽?shù)上一個(gè)節(jié)點(diǎn)代表一個(gè)球心點(diǎn)，節(jié)點(diǎn)圓圈中記錄了球心點(diǎn)編號(hào)和對(duì)應(yīng)的球目標(biāo)半徑，例如根節(jié)點(diǎn)記錄了1號(hào)球心點(diǎn)和其對(duì)應(yīng)的半徑為1.92?；コ鈽?shù)中每一條邊都連接著兩個(gè)節(jié)點(diǎn)，其中上層節(jié)點(diǎn)是下層節(jié)點(diǎn)的父節(jié)點(diǎn)，即：上層節(jié)點(diǎn)是與之相連的下層節(jié)點(diǎn)的最近且密度更高的球心點(diǎn)。每條邊都具有一個(gè)距離屬性值，記錄了其所連接的兩個(gè)點(diǎn)之間的距離，例如1號(hào)點(diǎn)與31號(hào)點(diǎn)的連接邊記錄了其之間的距離為4.16。

圖2 映射球心點(diǎn)分布圖

圖3 球心點(diǎn)互斥樹(shù)

1.2.2 球心點(diǎn)互斥

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

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

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

圖4 經(jīng)互斥計(jì)算后的球心點(diǎn)互斥樹(shù)

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

1.3 確認(rèn)球目標(biāo)

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

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

2 實(shí)驗(yàn)與分析

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

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

圖6 實(shí)驗(yàn)場(chǎng)景照片以及映射球心點(diǎn)分布

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

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

圖7 映射球心點(diǎn)密度降序排列及識(shí)別出的目標(biāo)球分布

表1 各個(gè)球目標(biāo)的相關(guān)參數(shù)統(tǒng)計(jì)值

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

圖8 包含5個(gè)球目標(biāo)的桌面場(chǎng)景掃描點(diǎn)云

表2 本文MutEx聚類與文獻(xiàn)[9]HAC聚類實(shí)驗(yàn)結(jié)果

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

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

表3 本文方法各步驟計(jì)算耗時(shí)

3 結(jié) 論

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

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

[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]. 圖學(xué)學(xué)報(bào), 2012, 33(2): 68-71.

[9] 李嘉, 阿依古麗?阿曼, 鄭德華. 復(fù)雜場(chǎng)景三維點(diǎn)云中未知球形目標(biāo)的自動(dòng)識(shí)別方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2013, 25(10): 1489-1495.

[10] 李勝男, 林曉, 陳言, 等. 基于點(diǎn)云的球面三維逆向建模[J]. 圖學(xué)學(xué)報(bào), 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

國(guó)家自然科學(xué)基金項(xiàng)目(41301406，41201439)；江蘇省自然科學(xué)基金項(xiàng)目(BK20130829)

李子寬(1995–)，男，山西汾陽(yáng)人，本科生。主要研究方向?yàn)辄c(diǎn)云數(shù)據(jù)處理與應(yīng)用。E-mail：lzkcqz@163.com

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