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

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

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

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

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