海量點云Out-of-CoreR樹構(gòu)建及拓撲近鄰查詢.pdf

1、性能良好的R樹空間索引與局部型面特征參考數(shù)據(jù)對于曲面重建具有極其重要的意義。目前主流的R樹因構(gòu)建參數(shù)單目標串行優(yōu)化導致子樹選取與結(jié)點分裂結(jié)果并不理想，當點云非均勻分布、k值過小時，k近鄰點集作為局部參考數(shù)據(jù)并不能有效體現(xiàn)局部型面特征，且由于點云數(shù)據(jù)規(guī)模趨于海量，甚至超出主存容限，目前的R樹構(gòu)建及k近鄰查詢機制將無法使用。本文基于多目標優(yōu)化改進R樹中的子樹選取與結(jié)點分裂算法，利用主元分析擴展搜索包圍球?qū)近鄰點集優(yōu)化以獲取拓撲近鄰點集，并

2、基于Out-of-Core策略，結(jié)合數(shù)據(jù)庫SQLite實現(xiàn)R樹索引Out-of-Core分級存儲機制與拓撲近鄰Out-of-Core查詢機制。主要研究內(nèi)容如下：
　　(1)提出R樹形位多目標聚類構(gòu)建算法，將子樹選取視為多目標優(yōu)化，其中將周長增量、重疊度增量優(yōu)化指標作為決策向量，根據(jù)上溢結(jié)點子結(jié)點在各軸向的形位分布選取分裂軸，對候選分裂解以重疊度為指標進行聚類過濾，并將周長之和最小解作為結(jié)點分裂結(jié)果，從而避免了指標因單目標串行優(yōu)化而

3、導致 R樹性能下降的情況，使得結(jié)點分布與數(shù)據(jù)分布更具一致性，R樹性能有所提高。
　　(2)提出R樹索引的Out-of-Core構(gòu)建策略，將數(shù)據(jù)庫SQLite與R樹構(gòu)建相結(jié)合實現(xiàn)索引結(jié)點存儲于主存與數(shù)據(jù)點存儲于輔存的分級存儲機制，從而有效解決了因點云數(shù)據(jù)規(guī)模過大甚至超出主存限制的情況。
　　(3)提出主元分析導向自適應擴展的拓撲近鄰查詢算法，利用過目標點的第二主元平面分割k近鄰點集，根據(jù)小點集與近鄰點集點數(shù)比例與預設閾值的大小

4、確定是否擴展搜索包圍球，使得每個目標點實現(xiàn)自適應拓撲近鄰查詢，從而有效提高查詢效率，并設置搜索包圍球半徑的上限值，從而避免邊界、棱邊處點的無限查詢與相鄰曲面點的越界查詢，使得獲取的拓撲近鄰點集能夠有效體現(xiàn)局部型面特征。
　　(4)提出拓撲近鄰的Out-of-Core查詢策略，首先在主存中獲取近鄰葉結(jié)點，然后利用數(shù)據(jù)庫 SQLite從輔存中將近鄰葉結(jié)點包含的數(shù)據(jù)點讀入主存，繼而獲取目標點的近鄰點。對于空間近鄰葉結(jié)點查詢，以目標點與結(jié)