楊 軍,林巖龍,王小鵬,張瑞峰

(蘭州交通大學(xué)電子與信息工程學(xué)院,蘭州730070)

基于自適應(yīng)空間球的k最近鄰域快速搜索算法

楊 軍,林巖龍,王小鵬,張瑞峰

(蘭州交通大學(xué)電子與信息工程學(xué)院,蘭州730070)

利用空間球搜索大規(guī)模點(diǎn)云數(shù)據(jù)k鄰域存在速率慢和穩(wěn)定性差的問題,為此,提出一種新的k鄰域快速搜索算法。利用與k無關(guān)的分塊策略對點(diǎn)云進(jìn)行分塊,使用候選點(diǎn)所在子塊內(nèi)采樣點(diǎn)的近似密度自適應(yīng)確定候選點(diǎn)的初始動(dòng)態(tài)球半徑,應(yīng)用動(dòng)態(tài)球的外切立方體搜索k鄰域候選點(diǎn)。當(dāng)候選點(diǎn)數(shù)目不滿足要求或搜索不成功時(shí),采用候選點(diǎn)動(dòng)態(tài)球外切立方體的外接球擴(kuò)大搜索范圍。實(shí)驗(yàn)結(jié)果表明,與已有算法相比,該算法的k鄰域搜索效率明顯提高,而且當(dāng)子塊內(nèi)預(yù)設(shè)點(diǎn)數(shù)變化、采樣密度提高時(shí)具有較強(qiáng)穩(wěn)定性,自動(dòng)化程度較高。

k最近鄰域;曲面重建;點(diǎn)變化云;空間球;分塊策略;候選點(diǎn)

1 概述

三維散亂點(diǎn)數(shù)據(jù)的重建是逆向工程、虛擬現(xiàn)實(shí)、醫(yī)學(xué)圖像處理等領(lǐng)域的重要研究內(nèi)容。隨著三維激光掃描技術(shù)的發(fā)展,基于散亂點(diǎn)(也稱點(diǎn)云)的曲面重建技術(shù)成為國內(nèi)外學(xué)者研究的熱點(diǎn)。k鄰域的搜索效率直接影響模型的重建速度以及曲面光滑等后續(xù)處理,對其搜索算法進(jìn)行研究具有重要的理論和實(shí)際價(jià)值。

k鄰域搜索的傳統(tǒng)方法是計(jì)算任一點(diǎn)到其余各點(diǎn)的歐氏距離,然后升序排序,前面的k個(gè)點(diǎn)即為此點(diǎn)的k鄰域點(diǎn)。這種方法簡單直觀,易于實(shí)現(xiàn),但其時(shí)間復(fù)雜度較高,在點(diǎn)云規(guī)模較小時(shí),此算法能取得較好的結(jié)果。然而,隨著三維掃描設(shè)備的發(fā)展以及建模精度的不斷提高,點(diǎn)云數(shù)據(jù)的規(guī)模也不斷增大,這種方法的耗時(shí)驚人。國內(nèi)外眾多學(xué)者對此問題提出了一些比較快速的搜索算法,大致分為3類:

(1)利用樹的層級結(jié)構(gòu)對點(diǎn)云進(jìn)行k鄰域搜索[1-2],但是這些方法思想比較復(fù)雜,不易實(shí)現(xiàn),而且若鄰近點(diǎn)和待搜索點(diǎn)處于不同層時(shí)會(huì)造成搜索范圍擴(kuò)大,降低搜索效率。同時(shí),樹結(jié)構(gòu)的創(chuàng)建也具有一定的時(shí)間消耗。此外,此類方法不適合大規(guī)模點(diǎn)云數(shù)據(jù)的k鄰域搜索[3-4]。

(2)利用 Voronoi圖對數(shù)據(jù)集進(jìn)行鄰域搜索[5-6],但是在構(gòu)建點(diǎn)集 Voronoi圖時(shí)需進(jìn)行較多的浮點(diǎn)運(yùn)算,計(jì)算量仍然較大。

(3)利用立方體柵格或球空間縮小k鄰域的搜索范圍,然后按傳統(tǒng)方法搜索。文獻(xiàn)[7]在點(diǎn)云分塊后進(jìn)行搜索,但是每個(gè)子塊內(nèi)邊界點(diǎn)的k鄰域需要搜索與其最近的26個(gè)子空間,浪費(fèi)了較多的時(shí)間。文獻(xiàn)[8]在文獻(xiàn)[7]的基礎(chǔ)上,推廣了文獻(xiàn)[9]中只能解決二維問題的搜索方法,提出一種新的搜索算法,該算法利用子塊擴(kuò)張方法避免搜索相鄰子空間,但是如果點(diǎn)云分布不均勻,可能會(huì)造成某個(gè)子空間內(nèi)的采樣點(diǎn)特別多,在進(jìn)行k鄰域搜索時(shí)會(huì)進(jìn)行大量的浮點(diǎn)運(yùn)算,降低了搜索效率。文獻(xiàn)[10]采用二次分塊策略,利用多個(gè)小立方體柵格逐步縮小k鄰域的搜索范圍以提高搜索效率,不過該算法仍然存在分塊不均勻問題,而且算法的穩(wěn)定性不是很理想。文獻(xiàn)[11]將點(diǎn)云進(jìn)行微小分塊,雖然算法預(yù)想每個(gè)子塊內(nèi)點(diǎn)數(shù)在2～5之間,但是由于模型的多樣性和采樣的不均勻性,實(shí)際和預(yù)想有一定差距。文獻(xiàn)[12]利用點(diǎn)的三維坐標(biāo)序號(hào)形成一個(gè)動(dòng)態(tài)網(wǎng)格縮小k鄰域的搜索范圍,算法視角獨(dú)特,搜索效率得到了一定的提高,但是不能有效保證搜索結(jié)果的正確性,限制了算法的應(yīng)用。文獻(xiàn)[13]在文獻(xiàn)[12]的基礎(chǔ)上,利用自身小立方體有效解決算法搜索結(jié)果不正確的問題,而且采用分塊策略,在較大程度上降低了算法的搜索范圍和排序算法的復(fù)雜度,提高了搜索效率。文獻(xiàn)[14]對參數(shù)k進(jìn)行了研究,提出了依據(jù)最小分類樣本尺寸確定參數(shù)k的方法,并將其應(yīng)用到聚類分析中,但該方法中參數(shù)k對噪聲非常敏感。

本文針對大規(guī)模散亂點(diǎn)云數(shù)據(jù),提出一種新的k鄰域快速搜索算法。采用與k無關(guān)的分塊策略對整個(gè)點(diǎn)云空間分塊;以候選點(diǎn)所在子塊的采樣點(diǎn)近似密度確定初始動(dòng)態(tài)球半徑;以球的外切立方體搜索k鄰域候選點(diǎn);當(dāng)k鄰域候選點(diǎn)數(shù)目不滿足要求或搜索不成功時(shí),以外切立方體的外接球擴(kuò)大搜索范圍,直至滿足要求或鄰域搜索成功。

2 算法描述

2.1 點(diǎn)云空間分塊

設(shè)點(diǎn)云數(shù)據(jù)集合內(nèi)采樣點(diǎn)總數(shù)為N,其最小包圍盒的體積為V,點(diǎn)云空間中采樣點(diǎn)分布均勻,且每個(gè)子塊內(nèi)點(diǎn)云數(shù)目為num。將包圍盒劃分為若干個(gè)子空間,則子空間的邊長L為[11]:其中,xmax,xmin分別為點(diǎn)云空間中在x方向的最大值和最小值;ymax,ymin分別為點(diǎn)云空間中在y方向的最大值和最小值;zmax,zmin分別為點(diǎn)云空間中在z方向的最大值和最小值。

根據(jù)點(diǎn)集中采樣點(diǎn)坐標(biāo)值計(jì)算其所處的子空間序號(hào),將采樣點(diǎn)歸入相應(yīng)的子空間中。

2.2 初始動(dòng)態(tài)球半徑的計(jì)算

在完成點(diǎn)云空間分塊后,對任意子空間S內(nèi)任一采樣點(diǎn)p,其初始動(dòng)態(tài)球半徑計(jì)算方法如下:假設(shè)p所在的子空間內(nèi)采樣點(diǎn)分布均勻,以此子空間內(nèi)點(diǎn)的分布密度作為采樣點(diǎn)局部的近似采樣密度,根據(jù)近似密度和k值自適應(yīng)計(jì)算初始動(dòng)態(tài)球半徑r,其計(jì)算公式如下:

其中,Ns為空間S內(nèi)采樣點(diǎn)數(shù)目;Vs為空間S的體積。由式(2)可知,本文算法初始r的確定僅和子塊內(nèi)點(diǎn)云數(shù)目num相關(guān),減少了參數(shù)控制,提高了算法的自動(dòng)化程度。

2.3 k鄰域快速搜索算法

2.3.1 k鄰域候選點(diǎn)的計(jì)算

首先,以任一點(diǎn)p為圓心,r為半徑確定p的動(dòng)態(tài)球O,根據(jù)動(dòng)態(tài)球O確定其覆蓋的子空間范圍;其次,計(jì)算O的外切立方體,從覆蓋的子空間內(nèi)搜索位于外切立方體內(nèi)的點(diǎn),這些點(diǎn)即為k鄰近候選點(diǎn)。

2.3.2 動(dòng)態(tài)球的擴(kuò)充

若外切立方體內(nèi)的k鄰近候選點(diǎn)數(shù)目不滿足要求,即小于k,或搜索不成功,則擴(kuò)充動(dòng)態(tài)球,并根據(jù)新動(dòng)態(tài)球的外切立方體重新計(jì)算k鄰近候選點(diǎn)或重新搜索。擴(kuò)充方法如圖1所示。

由圖1可知,O0和Cube0為p的當(dāng)前動(dòng)態(tài)球和動(dòng)態(tài)球的外切立方體,灰色區(qū)域?yàn)閯?dòng)態(tài)球覆蓋的子空間范圍。當(dāng)需要擴(kuò)充時(shí),計(jì)算Cube0的外接球O1,并計(jì)算O1的外切立方體Cube1,O1和Cube1即為擴(kuò)充后p的新的動(dòng)態(tài)球和動(dòng)態(tài)球的外切立方體。如果Cube1內(nèi)的點(diǎn)云數(shù)目滿足要求,或p的k鄰域搜索成功,則停止擴(kuò)充,否則繼續(xù)擴(kuò)充。本文算法在采樣點(diǎn)動(dòng)態(tài)球的外切立方體內(nèi)點(diǎn)云數(shù)目K滿足要求的情況下,至多擴(kuò)充一次即能保證p的k鄰域搜索成功,這在一定程度上減少了擴(kuò)充次數(shù),提高了算法效率。

圖1 動(dòng)態(tài)球擴(kuò)充方法

2.3.3k鄰域搜索

按2.1節(jié)的方法完成點(diǎn)集的劃分后,對子空間中任一點(diǎn)p完成k鄰域搜索的步驟如下:

(1)利用式(2)計(jì)算p的初始動(dòng)態(tài)球半徑,并根據(jù)2.3.1節(jié)中方法從球覆蓋的子空間中搜索位于外切立方體內(nèi)的點(diǎn),即k鄰域候選點(diǎn)。

(2)計(jì)算k鄰域候選點(diǎn)數(shù)目K,若K＜k,則按2.3.2節(jié)方法擴(kuò)大動(dòng)態(tài)球O,并重新計(jì)算k鄰域候選點(diǎn)和點(diǎn)數(shù)K,若K滿足要求則停止,否則繼續(xù)擴(kuò)大p的動(dòng)態(tài)球,直至其點(diǎn)數(shù)滿足要求。

(3)若K滿足要求,則分別計(jì)算K個(gè)點(diǎn)和p的距離d,將其保存至數(shù)組并標(biāo)記,重新搜索時(shí)已標(biāo)記的點(diǎn)不再計(jì)算。若d≤r,則將其保存至數(shù)組array中,否則不保存。若array內(nèi)點(diǎn)數(shù)m＜k,說明k鄰域搜索不成功,則按2.3.2節(jié)方法重新擴(kuò)充O和計(jì)算其外切立方體,計(jì)算其內(nèi)未計(jì)算過的點(diǎn)和p的距離d,并和新動(dòng)態(tài)球的半徑r進(jìn)行比較,若d≤r則保存至array,直至array內(nèi)點(diǎn)數(shù)m≥k。若m≥k,則對其排序,前k個(gè)點(diǎn)即為p的k鄰近點(diǎn)。其中,r為當(dāng)前p的動(dòng)態(tài)球半徑。

2.4 整體算法流程

輸入散亂數(shù)據(jù)點(diǎn)集合P,輸出任意點(diǎn)的k鄰域。算法整體實(shí)現(xiàn)框架如下:

Step 1 按2.1節(jié)方法對點(diǎn)云空間分塊。

Step 2 對子空間內(nèi)任一點(diǎn)p,按2.2節(jié)方法計(jì)算其初始動(dòng)態(tài)球。

Step 3 按2.3.3節(jié)方法完成p的k鄰域搜索,直至整個(gè)子空間內(nèi)所有采樣點(diǎn)搜索完成。

Step 4 對點(diǎn)云空間中所有子空間進(jìn)行搜索。

Step 5 結(jié)束。

算法的流程如圖2所示。

圖2 k鄰域快速搜索算法流程

3 實(shí)驗(yàn)結(jié)果與分析

在實(shí)驗(yàn)中,點(diǎn)云數(shù)據(jù)均為真實(shí)物體的掃描數(shù)據(jù),如圖3、圖4所示。

圖3 常用點(diǎn)云模型

圖4 Cat重采樣模型

所有實(shí)驗(yàn)均在酷睿雙核CPU,主頻2.20 GHz,內(nèi)存2 GB的個(gè)人筆記本電腦上完成,測量時(shí)間為1個(gè)點(diǎn)的k鄰域搜索的平均 CPU時(shí)間,單位為ms。

實(shí)驗(yàn)1 不同子塊預(yù)設(shè)值num對算法效率的影響。實(shí)驗(yàn)?zāi)Ｐ筒捎脠D3(a)、圖3(d),實(shí)驗(yàn)結(jié)果如表1所示,其中,n表示該模型總共包含的點(diǎn)數(shù)。由表1中數(shù)據(jù)可知,對本文算法來說,當(dāng)k分別取10,50和100時(shí),Cat模型搜索時(shí)間的標(biāo)準(zhǔn)差分別為0.003 15, 0.007 84和0.040 46,Bunny模型搜索時(shí)間的標(biāo)準(zhǔn)差分別為0.036 85,0.034 57和0.108 44;對文獻(xiàn)[11]算法來說,當(dāng)k分別取10,50和100時(shí),Cat模型搜索時(shí)間的標(biāo)準(zhǔn)差分別為 0.018 56,0.043 61和0.064 41,Bunny模型搜索時(shí)間的標(biāo)準(zhǔn)差分別為0.099 78,0.175 87和0.263 48。由實(shí)驗(yàn)數(shù)據(jù)的標(biāo)準(zhǔn)差可知,本文算法比文獻(xiàn)[11]算法對num的穩(wěn)定性更好。由表1中數(shù)據(jù)可知,對同一模型,相同的k和num,本文算法在搜索效率上明顯高于文獻(xiàn)[11]算法,隨著k的增加,本文算法的搜索時(shí)間增加幅度較小,而且對相同k值,不同num值,算法的穩(wěn)定性也高于文獻(xiàn)[11]算法。對同一模型,隨著k值的增加,或者對同一k值,隨著模型的增大,本文算法和文獻(xiàn)[11]算法的穩(wěn)定性都有所降低,但是本文算法的幅度更小。至于本文算法穩(wěn)定性降低的原因可能是因?yàn)樵趉值較大的情況下估算的局部采樣點(diǎn)密度信息對k值的有效性降低,造成num的穩(wěn)定性有所下降。

表1 不同子塊點(diǎn)數(shù)預(yù)設(shè)值num時(shí)的算法效率

實(shí)驗(yàn)2 同一模型不同采樣密度和不同num值對算法效率的影響。實(shí)驗(yàn)?zāi)Ｐ筒捎脠D4(a)、圖4(d),實(shí)驗(yàn)結(jié)果如表2所示。對本文算法來說,當(dāng)k分別取10,50和100時(shí),Cat20%重采樣模型搜索時(shí)間的標(biāo)準(zhǔn)差分別為0.016 56,0.010 80和0.013 98,Cat60%重采樣模型搜索時(shí)間的標(biāo)準(zhǔn)差分別為0.002 87,0.009 06和 0.021 08;對文獻(xiàn)[11]算法來說,當(dāng)k分別取10,50和100時(shí), Cat20%重采樣模型搜索時(shí)間的標(biāo)準(zhǔn)差分別為0.032 01,0.040 18和0.073 70,Cat60%重采樣模型搜索時(shí)間的標(biāo)準(zhǔn)差分別為0.023 03,0.044 49和0.061 85。由實(shí)驗(yàn)數(shù)據(jù)標(biāo)準(zhǔn)差可知,在模型的相同采樣密度和相同k值的情況下,本文算法的穩(wěn)定性明顯高于文獻(xiàn)[11]算法。由表2中數(shù)據(jù)可知,對相同采樣密度、num和k時(shí),本文算法搜索效率高于文獻(xiàn)[11]算法。當(dāng)k值較小時(shí)(取k=10或50),本文算法隨著采樣密度的提高穩(wěn)定性增強(qiáng),而文獻(xiàn)[11]算法的穩(wěn)定性降低;當(dāng)k值較大時(shí)(取k=100),本文算法的穩(wěn)定性略微有所降低,但仍高于文獻(xiàn)[11]算法。

為了和已有算法的搜索效率進(jìn)行比較,本文算法取num=3進(jìn)行實(shí)驗(yàn)3。同時(shí),根據(jù)已有算法的實(shí)驗(yàn)結(jié)果,文獻(xiàn)[11]算法取初始動(dòng)態(tài)球半徑調(diào)節(jié)因子β=0.3,半徑的擴(kuò)展倍數(shù)設(shè)為1.1,文獻(xiàn)[10]算法調(diào)節(jié)因子α=0.25,文獻(xiàn)[13]算法左側(cè)控制閾值a=2,右側(cè)控制閾值β=20,初始搜索半徑l=100,搜索半徑增量Δl=100,子空間擴(kuò)張?jiān)隽咳?(和文獻(xiàn)[13]實(shí)驗(yàn)取值相同)進(jìn)行實(shí)驗(yàn)3。

表2 同一模型不同采樣密度對不同num值時(shí)的算法效率

實(shí)驗(yàn)3 不同點(diǎn)云模型對算法效率的影響。實(shí)驗(yàn)結(jié)果如表3所示,實(shí)驗(yàn)?zāi)Ｐ筒捎脠D3。本文算法在k=10時(shí),搜索時(shí)間偏大,這是因?yàn)閷θ我饽Ｐ偷谝淮芜M(jìn)行k鄰域搜索時(shí)要對其進(jìn)行分塊,但是其搜索效率仍然高于文獻(xiàn)[10]算法、文獻(xiàn)[11]算法和文獻(xiàn)[13]算法,這是因?yàn)槲墨I(xiàn)[10]算法利用采樣點(diǎn)的不同立方體柵格縮小k鄰域候選點(diǎn)的搜索范圍,然后利用球空間進(jìn)行k鄰域搜索,但是在采樣點(diǎn)曲率較高的部分可能會(huì)造成球空間內(nèi)點(diǎn)云數(shù)目過大,需進(jìn)行大量的數(shù)值計(jì)算,而且隨著k值和模型規(guī)模增加,搜索效率相差更加明顯。而文獻(xiàn)[11]算法利用與k無關(guān)的分塊策略,并對計(jì)算過的球空間進(jìn)行點(diǎn)標(biāo)記,這在較大程度上降低了時(shí)間消耗,不過算法需要計(jì)算動(dòng)態(tài)球覆蓋小立方體柵格內(nèi)的所有點(diǎn)與候選點(diǎn)的距離,如果小立方體內(nèi)點(diǎn)過多會(huì)進(jìn)行過多的浮點(diǎn)計(jì)算,在一定程度上降低了算法的搜索效率,而且需要較多的參數(shù)控制。文獻(xiàn)[13]算法在每個(gè)子空間內(nèi)采用候選點(diǎn)的三維坐標(biāo)排序序號(hào)形成的小立方體來縮小點(diǎn)的k鄰域搜索范圍,很大程度上降低了浮點(diǎn)運(yùn)算的計(jì)算量,在計(jì)算合適候選點(diǎn)數(shù)目或k鄰域搜索失敗時(shí)動(dòng)態(tài)改變搜索半徑加快算法的收斂速度,提高了搜索效率,但是算法在計(jì)算合適的候選點(diǎn)時(shí)多次進(jìn)行搜索,在一定程度上增大了搜索時(shí)間消耗。另外,文獻(xiàn)[13]算法沒有針對不同的模型給出比較合適的子空間擴(kuò)張?jiān)隽看笮〉淖赃m應(yīng)計(jì)算方法,僅通過實(shí)驗(yàn)手段很難獲得適合不同模型的增量值。相反,本文算法首先采用與k無關(guān)的分塊策略,然后利用候選點(diǎn)所在立方體柵格的采樣點(diǎn)近似密度作為候選點(diǎn)局部的采樣密度,并結(jié)合k值自適應(yīng)確定候選點(diǎn)的初始動(dòng)態(tài)球半徑;其次,當(dāng)動(dòng)態(tài)球外切立方體內(nèi)的點(diǎn)數(shù)不符合要求,或者搜索不成功時(shí),利用外切立方體的外接球擴(kuò)大搜索范圍,并對計(jì)算過的點(diǎn)進(jìn)行標(biāo)記,盡量減少采樣點(diǎn)的計(jì)算次數(shù),提高算法效率。這樣算法不僅考慮了候選點(diǎn)的局部密度,而且避免了文獻(xiàn)[11]中半徑的擴(kuò)展倍數(shù)和β值的參數(shù)控制,提高了算法的自動(dòng)化程度。隨著模型規(guī)模和k值的增加,本文算法的優(yōu)勢更加明顯。由表3實(shí)驗(yàn)結(jié)果可以看出本文算法的效率明顯優(yōu)于其他相關(guān)算法。

表3 不同點(diǎn)云模型時(shí)的算法效率

4 結(jié)束語

本文算法利用候選點(diǎn)所在的小立方體柵格的估算密度作為候選點(diǎn)的局部密度,結(jié)合k值自適應(yīng)計(jì)算候選點(diǎn)的初始動(dòng)態(tài)球半徑。當(dāng)初始動(dòng)態(tài)球內(nèi)的點(diǎn)數(shù)不滿足要求或搜索不成功時(shí),根據(jù)候選點(diǎn)當(dāng)前動(dòng)態(tài)球外切立方體的外接球擴(kuò)大搜索范圍。實(shí)驗(yàn)結(jié)果表明,本文算法不僅對num、采樣密度具有較強(qiáng)的穩(wěn)定性,而且自動(dòng)化程度較高(僅需一個(gè)參數(shù)),和已有算法相比在搜索速度上有明顯的優(yōu)勢,有較高的理論參考價(jià)值和實(shí)用性。但是,本文算法也存在一定不足,如分塊不均勻等,這將是下一步要研究和解決的主要問題。

[1] Sarkar M,Leong T Y.Application of k-nearest NeighborsAlgorithm on BreastCancerDiagnosis Problem[C]//Proc.of American Medical Informatics Association Annual Symposium.Los Angeles,USA: IEEE Computer Society Press,2000:759-763.

[2] Procopiuc O,Agarwal P K,Arge L,et al.Bkd-tree:A Dynamic Scalable kd-tree[C]//Proc.of International Symposium on Spatial and Temporal Databases.Berlin, Germany:Springer,2003:46-65.

[3] Sankaranarayanan J,Samet H,Varshney A.A Fast All Nearest Neighbor Algorithm for Applications Involving Large Point-clouds[J].Computers&Graph,2007,31 (2):157-174.

[4] Connor M,Kumar P.Fast Construction of k-nearest Neighbor Graphs for Point Clouds[J].IEEE Transactions on Visualization&Computer Graphics, 2010,16(4):599-608.

[5] Dickerson M T,Drysdale R L S,Sack J R.Simple Algorithms for Enumerating Interpoint Distance and Finding k Nearest Neighbors[J].International Journal of Computational Geometry and Applications,1992,2(3): 221-239.

[6] Goodsell G.On Finding p-th Nearest Neighbors of Scattered Points in Two Dimensions for Small p[J]. Computer Aided Geometric Design,2000,17(4): 387-392.

[7] 周儒榮,張麗艷,蘇 旭,等.海量散亂點(diǎn)的曲面重建算法研究[J].軟件學(xué)報(bào),2001,12(2):249-255.

[8] 熊邦書,何明一,余華璟.三維散亂數(shù)據(jù)的k個(gè)最近鄰域快速搜索算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2004,16(7):909-912.

[9] Piegl L A,Tiller W.Algorithm for Finding All k Nearest Neighbors[J].Computer-aided Design,2002,34(2): 167-172.

[10] 趙儉輝,龍成江,丁乙華,等.一種基于立方體小柵格的k鄰域快速搜索算法[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2009,34(5):615-618.

[11] 馬 娟,方源敏,趙文亮,等.利用空間微分塊與動(dòng)態(tài)球策略的k鄰域搜索算法研究[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2011,36(3):358-362.

[12] 馬驪溟,徐 毅,李澤湘.基于動(dòng)態(tài)網(wǎng)格劃分的散亂點(diǎn)k鄰域快速搜索算法[J].計(jì)算機(jī)工程,2008,34(8): 10-11.

[13] 楊 軍,林巖龍,王陽萍,等.大規(guī)模散亂點(diǎn)的k鄰域快速搜索算法[J].中國圖象圖形學(xué)報(bào),2013,18(4): 399-406.

[14] Jivani A G.The Novel k Nearest Neighbor Algorithm [C]//Proc.of International Conference on Computer Communicationand Informatics.Coimbatore,India: IEEE Computer Society Press,2013:1-4.

編輯 顧逸斐

Fast Algorithm for k-nearest Neighbor Serch Based on Adaptive Spatial Sphere

YANG Jun,LIN Yan-long,WANG Xiao-peng,ZHANG Rui-feng
(School of Electronic&Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

To solve the problem of low efficiency and weak stability in searching k-nearest neighbor of large-scale scattered point cloud by using sphere space,a fast algorithm for finding k-nearest neighbor is presented.Point cloud data is divided into different sub-space by using partition strategy without considering k.The radius of the initial dynamic sphere is determined adaptively based on the approximate density of sampling points in a sub-space.The k-nearest candidate points are searched by the circumscribed cube of a dynamic sphere.When the number of k-nearest candidate points does not meet the requirement,or the search fails,the expanding extent is ensured by a circumsphere of the circumscribed cube.Experimental results show that the proposed method obtains not only a better performance and automation than the existing algorithms,but also a quite stability for the anticipated point number of the sub-space and sampling density.

k-nearest neighbor;surface reconstruction;point cloud;spatial sphere;partition strategy;candidate point

1000-3428(2014)10-0264-06

A

TP391.4

10.3969/j.issn.1000-3428.2014.10.049

國家自然科學(xué)基金資助項(xiàng)目(61261029);中國博士后科學(xué)基金資助面上項(xiàng)目(2013M542396);甘肅省自然科學(xué)基金資助項(xiàng)目(1208RJZA243);隴原青年創(chuàng)新人才扶持計(jì)劃基金資助項(xiàng)目(201182)。

楊 軍(1973-),男,教授、博士,主研方向:計(jì)算機(jī)圖形學(xué),虛擬現(xiàn)實(shí),數(shù)字圖像處理;林巖龍,碩士研究生;王小鵬,教授、博士;張瑞峰,碩士研究生。

2013-10-11

2013-12-09E-mail:tom.jun.yang@gmail.com

中文引用格式:楊 軍,林巖龍,王小鵬,等.基于自適應(yīng)空間球的k最近鄰域快速搜索算法[J].計(jì)算機(jī)工程,2014, 40(10):264-269.

英文引用格式:Yang Jun,Lin Yanlong,Wang Xiaopeng,et al.Fast Algorithm for k-nearest Neighbor Search Based on Adaptive Spatial Sphere[J].Computer Engineering,2014,40(10):264-269.