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

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