一種基于空間分塊策略的快速搜索算法

一種基于空間分塊策略的快速搜索算法

1快速快速算法隨著激光掃描儀設(shè)備的發(fā)展，將包含測(cè)量對(duì)象更詳細(xì)的個(gè)人信息數(shù)據(jù)采集到能夠，成為高精細(xì)測(cè)量建模的發(fā)展方向?；诖罅繑?shù)據(jù)的海面重建技術(shù)已成為研究的熱點(diǎn)問題。在基于大量數(shù)據(jù)的數(shù)據(jù)分析中，如基于磁盤面積和信息系統(tǒng)的數(shù)據(jù)分析，通常需要頻繁搜索點(diǎn)k的下一個(gè)點(diǎn)。例如，在重建磁盤面積時(shí)，需要使用k附近相鄰零的最小平方來計(jì)算測(cè)量點(diǎn)的切面，并且需要替換k附近相鄰零的二乘數(shù)。在搜索點(diǎn)和切割點(diǎn)的下一個(gè)點(diǎn)時(shí)，需要使用k附近的信息。因此，附近相鄰點(diǎn)的檢測(cè)算法的速度直接影響到重建曲線的速度。設(shè)X={x1,x2,…xn}是未知曲面M上的空間采樣點(diǎn)集,點(diǎn)集X中與某一測(cè)點(diǎn)xi的直線距離最短的k個(gè)點(diǎn),稱為xi的k近鄰,記為Nbhd(xi),k近鄰中的每個(gè)測(cè)點(diǎn)稱為xi的鄰近點(diǎn).通常,計(jì)算某點(diǎn)的k個(gè)近鄰的方法是求出測(cè)點(diǎn)與其余n-1個(gè)點(diǎn)的直線距離,并按從小到大的順序排列,前面的k個(gè)點(diǎn)即為測(cè)點(diǎn)的k近鄰,這種方法很簡(jiǎn)單,但是當(dāng)數(shù)據(jù)量達(dá)到上萬甚至幾十萬個(gè)點(diǎn)的時(shí)候,用此方法來計(jì)算數(shù)據(jù)點(diǎn)的k近鄰必然會(huì)花費(fèi)很多時(shí)間.許多學(xué)者針對(duì)此問題進(jìn)行了一些快速算法的研究,文獻(xiàn)利用點(diǎn)集Voronoi圖來進(jìn)行k個(gè)最近點(diǎn)的搜索,但點(diǎn)集的Voronoi圖計(jì)算量非常大;文獻(xiàn)基于空間索引樹的遍歷,適合于空間實(shí)體對(duì)象的查詢,不適合于大量的空間點(diǎn)云數(shù)據(jù);文獻(xiàn)利用空間分塊策略進(jìn)行k近鄰搜索,但文獻(xiàn)只研究了平面點(diǎn)集的k近鄰搜索問題,文獻(xiàn)將文獻(xiàn)的算法推廣到三維空間數(shù)據(jù)點(diǎn)集,并綜合考慮了數(shù)據(jù)集的范圍、點(diǎn)的總數(shù)及最近點(diǎn)數(shù)目k,通過實(shí)驗(yàn)得出了接近于最佳搜索速度的子立方體大小的參數(shù)值范圍,但是文獻(xiàn)只考慮了數(shù)據(jù)集的范圍,沒有充分考慮到子立方體的劃分與空間數(shù)據(jù)點(diǎn)密度的關(guān)系,如果不同密度的點(diǎn)云數(shù)據(jù)劃分的子立方體邊長(zhǎng)接近,子立方體內(nèi)包含的點(diǎn)數(shù)是不同的,查找k近鄰的速度就會(huì)受到影響.針對(duì)上述問題本文提出一種快速有效的K近鄰的搜索算法,本算法采用空間分塊策略,把包含數(shù)據(jù)的最小長(zhǎng)方體劃分成多個(gè)子立方體,綜合考慮了空間數(shù)據(jù)的范圍、點(diǎn)的數(shù)量、近鄰點(diǎn)數(shù)k以及空間數(shù)據(jù)點(diǎn)的密度,給出了一種新的估算立方體邊長(zhǎng)的方法;通過實(shí)驗(yàn)得出了不同點(diǎn)集的情況下,子立方體的邊長(zhǎng)與近鄰點(diǎn)數(shù)目k的關(guān)系,在內(nèi)存分配策略、搜索終止條件上進(jìn)行了改進(jìn),進(jìn)一步提高k近鄰的搜索速度.2子方位空間和數(shù)據(jù)點(diǎn)首先根據(jù)子立方體邊長(zhǎng)的計(jì)算值,把數(shù)據(jù)空間分成多個(gè)子立方體空間;然后記錄子立方體內(nèi)包含的數(shù)據(jù)點(diǎn);最后利用子立方體內(nèi)點(diǎn)的信息對(duì)每個(gè)測(cè)點(diǎn)進(jìn)行k近鄰的搜索.2.1生成項(xiàng)目由來typedefstructtagOBJECT{intnOHSum;//結(jié)構(gòu)中具有的句柄個(gè)數(shù)DWORDlOElementSum;//圖形元素結(jié)構(gòu)數(shù)目HANDLEhOElement;//圖形元素塊頭句柄DWORDlOCubeSum;//立方體結(jié)構(gòu)數(shù)目HANDLEhOCube;//立方體內(nèi)存塊頭句柄DWORDlOPolylineSum;//多邊形結(jié)構(gòu)數(shù)目HANDLEhOPolyline;//多邊形內(nèi)存塊頭句柄charcOUse;//使用標(biāo)記charcODelete;//刪除標(biāo)記}OBJECT;圖形元素的數(shù)據(jù)結(jié)構(gòu):typedefstructtagELEMENT{intnEHSum;//結(jié)構(gòu)中具有的句柄個(gè)數(shù)doublefE1,fE2,fE3,fE4,fE5,fE6;//坐標(biāo)intcEDeleteFlag;//刪除標(biāo)記intcETypeFlag;//點(diǎn),邊標(biāo)記intcEEdgeFlag;//邊界點(diǎn)、邊標(biāo)志:intcEProcFlag;//處理標(biāo)記intcECubeIndexNo;//點(diǎn)所屬的立方體編號(hào)HANDLEhPKNEIHANDLE;//點(diǎn)的K近鄰內(nèi)存塊的頭句柄intnKPcount;//點(diǎn)的近鄰數(shù)}ELEMENT;子立方體結(jié)構(gòu)的定義typedefstructtagCube{intCubeNo;//元素編號(hào)POINTSETCoVex;//立方體左下角、右上角坐標(biāo)intPointCount;//立方體中點(diǎn)的數(shù)量intDeleteF;//刪除標(biāo)記KNCUBEKNCubes;//立方體的27個(gè)近鄰(包括自身)HANDLEhPHANDLE;//立方體中包含的點(diǎn)的內(nèi)存塊的頭句柄}CUBE;2.2子：子：子：子：子：子：子快速識(shí)別的可擴(kuò)張性算法速度的快慢取決于子立方體劃分的是否合理,如果子立方體劃分的過大,子立方體數(shù)少,計(jì)算某子立方體的近鄰時(shí),查找速度快,但是一旦在本立方體中不能成功的找到測(cè)點(diǎn)的k近鄰,到近鄰立方體中查找時(shí)數(shù)據(jù)量會(huì)大大增加,又降低查找速度;如果子立方體劃分的小,子立方體數(shù)多,計(jì)算某子立方體的近鄰時(shí),查找速度慢,但是一旦在本立方體中查找k近鄰不能成功,那么到近鄰立方體中查找時(shí)數(shù)據(jù)量會(huì)減小,也會(huì)提高查找速度,兩者相互制約,所以如何來確定子立方體的邊長(zhǎng),得到一個(gè)最佳的搜索速度,是本算法的關(guān)鍵.空間數(shù)據(jù)點(diǎn)集的總數(shù)、近鄰數(shù)k、數(shù)據(jù)范圍、數(shù)據(jù)點(diǎn)的密度等信息都將制約著子立方體的邊長(zhǎng)L的確定,本算法綜合考慮了這些因素,通過兩次劃分子立方體調(diào)整邊長(zhǎng).設(shè)空間數(shù)據(jù)點(diǎn)集的總數(shù):N需要查找的近鄰數(shù):k點(diǎn)集的密度:d子立方體的邊長(zhǎng):L不包含任何數(shù)據(jù)點(diǎn)的小立方體稱為空小立方體空間:vkong首先計(jì)算包含所有數(shù)據(jù)的最小長(zhǎng)方體空間的體積vzongvzong=(xmax-xmin)×(ymax-ymin)×(zmax-zmin)(1)將最小長(zhǎng)方體空間進(jìn)行指定邊長(zhǎng)l的劃分,計(jì)算所有空的小立方體空間的體積和包含數(shù)據(jù)點(diǎn)的有效小立方體的體積vyx:其中l(wèi)=(vzong×1.5k/N)1/3,n為空子立方體數(shù).d=vyx/N(3)假設(shè)子立方體包含的點(diǎn)數(shù)是近鄰點(diǎn)數(shù)k的α倍,則有:L3/d=α×k(4)整理(2)、(3)、(4)式得:L=C·α1/3(5)其中C=(vyx×k/N)1/3在k,N,vyx確定后,通過調(diào)整α值就可以調(diào)整子立方體邊長(zhǎng),通過實(shí)驗(yàn)分析,不同疏密程度的海量空間數(shù)據(jù),都可以給出一個(gè)近似統(tǒng)一的接近于最佳k近鄰搜索速度的α值,使本搜索算法具有更強(qiáng)的適應(yīng)性.立方體邊長(zhǎng)L確定后,最小長(zhǎng)方體空間在x,y,z方向上的分辨率分別為:LX=(xmax-xmin)/LLy=(ymax-ymin)/LLy=(zmax-zmin)/L則子立方體的總數(shù)為:NCUBE=LX×LY×LZ;然后把每個(gè)數(shù)據(jù)點(diǎn)分配到相應(yīng)的子立方體空間,記錄點(diǎn)所在的子立方體的編號(hào),以便后續(xù)的查詢操作.由于每個(gè)子空間內(nèi)含有數(shù)據(jù)點(diǎn)的個(gè)數(shù)是未知的,為了節(jié)省存儲(chǔ)空間,提高運(yùn)算速度,本文采用圖元數(shù)據(jù)結(jié)構(gòu),動(dòng)態(tài)地分配內(nèi)存空間,采用指針變量存儲(chǔ)方式.一個(gè)圖元為多個(gè)基本圖形元素的集合,點(diǎn)、邊、面、體稱為基本圖形元素.3計(jì)算測(cè)點(diǎn)到當(dāng)前子部分的距離利用上面的圖元數(shù)據(jù)結(jié)構(gòu),對(duì)每個(gè)測(cè)點(diǎn)進(jìn)行k近鄰的搜索步驟如下:第1步.計(jì)算子立方體邊長(zhǎng),劃分子立方體,并按編號(hào)存入內(nèi)存,記錄每個(gè)立方體所包含的數(shù)據(jù)點(diǎn)及每個(gè)點(diǎn)所屬的子立方體編號(hào);第2步.計(jì)算候選點(diǎn)到當(dāng)前子立方體到六個(gè)側(cè)面的最短距離ds;第3步.根據(jù)測(cè)點(diǎn)所在的子立方體編號(hào),判斷當(dāng)前子立方體內(nèi)的點(diǎn)數(shù)是否大于所要搜索的近鄰數(shù)k,如果不大于,則進(jìn)入第四步,如果大于則計(jì)算當(dāng)前子立方體內(nèi)所有點(diǎn)與測(cè)點(diǎn)的距離,按距離升序的方式,如果第k個(gè)近鄰點(diǎn)與測(cè)點(diǎn)的距離小于ds,則查找成功,記錄k個(gè)近鄰點(diǎn),否則進(jìn)入第四步;第4步.找出當(dāng)前子立方體的26個(gè)近鄰,計(jì)算測(cè)點(diǎn)到26個(gè)近鄰立方體中心的距離,排序后從最近的子立方體中查找測(cè)點(diǎn)的K近鄰,查找成功,記錄k個(gè)鄰近點(diǎn);否則,進(jìn)行外圍擴(kuò)展迭代,繼續(xù)查找,直到查找成功,記錄k個(gè)鄰近點(diǎn).4算法的有效性驗(yàn)證為了驗(yàn)證本文算法的正確性和有效性,我們?cè)谌?.5GHz的筆記本PC機(jī)上進(jìn)行了下述3組實(shí)驗(yàn).實(shí)驗(yàn)數(shù)據(jù)為真實(shí)物體的空間點(diǎn)云數(shù)據(jù),圖2～6所示,分別給出了兔子、龍、馬、彩陶壺、瓶蓋的點(diǎn)數(shù)據(jù)模型,在VC++6.0環(huán)境下,用OpenGL顯示.表1～3中給出了不同物體20個(gè)點(diǎn)的k近鄰搜索的實(shí)驗(yàn)數(shù)據(jù).測(cè)試時(shí)間為搜索20個(gè)點(diǎn)k近鄰的CPU運(yùn)行時(shí)間,用API函數(shù)GetSystemTime()得到,單位為ms.實(shí)驗(yàn)1.從不同算法的對(duì)比研究發(fā)現(xiàn)本算法的搜索速度大大提高.從實(shí)驗(yàn)數(shù)據(jù)分析可以發(fā)現(xiàn)搜索k近鄰算法速度的快慢主要受到子立方體數(shù)與子立方體內(nèi)包含的點(diǎn)數(shù)的影響,從表1中可以看出,在測(cè)點(diǎn)所在的子立方體中搜索到k近鄰的情況是很少的,因此需要合理的劃分子立方體,協(xié)調(diào)兩者的關(guān)系.本算法由于在計(jì)算子立方體邊長(zhǎng)時(shí),計(jì)算了立方體的有效空間,考慮了點(diǎn)云數(shù)據(jù)的密度,數(shù)據(jù)的范圍,點(diǎn)云的數(shù)量,近鄰點(diǎn)數(shù),通過調(diào)整系數(shù)α,即子立方體內(nèi)包含的點(diǎn)數(shù)與近鄰點(diǎn)數(shù)k的倍數(shù)關(guān)系,使得子立方體數(shù)目不至于太多和太少,子立方體的劃分更加合理,從而可以得到接近最佳搜索速度的子立方體邊長(zhǎng).在到近鄰子立方體搜索測(cè)點(diǎn)的k近鄰時(shí),文獻(xiàn)向外擴(kuò)展一圈,而本算法只是擴(kuò)展了7個(gè)最近鄰的子立方體,它的測(cè)點(diǎn)在一個(gè)子立方體內(nèi)的角上,所處位置最差,需要到近鄰子立方體中查找k近鄰時(shí)所需的子立方體數(shù)最多的情況,因此改善了搜索的終止條件,使本算法速度大大提高.實(shí)驗(yàn)2:驗(yàn)證本文算法對(duì)不同物體的點(diǎn)云數(shù)據(jù)的適應(yīng)性.對(duì)每個(gè)物體分別設(shè)置不同的k、α值的組合進(jìn)行實(shí)驗(yàn),結(jié)果如表2所示:從表3中可以得出本文算法對(duì)于不同數(shù)量的點(diǎn)云數(shù)據(jù)和不同近鄰個(gè)數(shù)k的最快搜索速度的α值范圍比較集中,在1-4之間,當(dāng)k值較小時(shí),α值應(yīng)取大些,如3、4,即子立方體內(nèi)包含的點(diǎn)數(shù)是k的3或4倍,當(dāng)k值較大時(shí),α值應(yīng)取小些,如1、2,這樣可控制子立方體邊長(zhǎng)不會(huì)過大或過小.實(shí)驗(yàn)3:數(shù)據(jù)是對(duì)圖2所示兔模型點(diǎn)云數(shù)據(jù)進(jìn)行二次采樣,使其數(shù)據(jù)點(diǎn)總數(shù)分別為35947、17974、7190和3595,對(duì)α、k值的不同組合進(jìn)行測(cè)試,結(jié)果如表3所示,從表中可以看出,本文算法于不同密度的點(diǎn)云數(shù)據(jù)和不同鄰域個(gè)數(shù)的k近鄰搜索速度的α值范圍比較集中,在1-4之間,類似于實(shí)驗(yàn)2的結(jié)果,并且α值在此范圍內(nèi)搜索時(shí),搜索時(shí)間差很小.這說明了本文算法對(duì)處理不同的點(diǎn)云數(shù)據(jù)具有很好的適應(yīng)性.5海量空間數(shù)據(jù)測(cè)試本文算法在