一種改進的立體柵格K鄰域搜索算法

摘 要：文章針對利用規則柵格進行K鄰域搜索容易遺漏點云局部特征點以及自動化程度不高的問題，對K鄰域搜索算法進行了改進。該算法是在規則立體柵格的基礎上融入八叉樹思想，根據點云閾值查找點云特征柵格，對特征柵格按此柵格點云數與閾值的關系自動計算棱長并進行精劃分，并采用自適應空間動態球算法擴展并搜索采樣點的K鄰域點集。實驗表明，與其他算法相比，該算法不僅具有較高的自動化能力和較強的穩定性，還能快速、準確搜索采樣點的K鄰域。

關鍵詞：立體柵格；八叉樹；動態空間球；K鄰域

中圖分類號：TP301.6 文獻標志碼：A 文章編號：2095-2945（2017）29-0005-02

引言

鄰域是散亂點云中各點與其相鄰點間建立的拓撲關系，能有效的提高點云數據處理的速度和效率[1]。點云的數據處理和曲面重構都受點云鄰域的搜索效率的影響[2]。K鄰域能同時處理均勻分布和非均勻分布的點云，且搜索速度快[1]。

本文的K鄰域搜索算法是在規則立體柵格法中融入八叉樹思想，使獲得的小立體柵格中包含數目適中的采樣點；再以改進的自適應空間動態球算法實現對完成了空間劃分點云數據的K鄰域搜索，增強搜索的自動化程度和穩定性，并提高搜索的速度。

1 點云空間劃分

空間劃分是將點云模型的空間包圍區域按一定的邊長進行規則劃分，從而獲得多個完全相同的小立體柵格，完成K鄰域搜索的第一步。點云空間劃分分為點云初劃分和點云精劃分。由此獲得的每個小立體柵格中都具有類似的曲面空間信息。

1.1 點云初劃分

點云模型的初劃分是將點云模型的空間包圍盒按照合適的邊長劃分成m×n×l個小立體柵格[3][4]，并完成對每個柵格中點云的標號，同時對每個柵格進行掃描并記錄柵格中是否含有點云，并對無點云柵格進行標記為已訪問，其效果如圖1所示。

1.2 點云精劃分

針對復雜的點云模型，若只采用規則立體柵格劃分所得的小立體柵格，因其點云分布不均，使得所獲柵格內所含有的空間曲面信息具有非常大的差異，假如此時便進行K鄰域搜索，那么將極易漏掉模型的某些關鍵特征點，使得K鄰域的搜索結果不正確。在初劃分后，利用點云閾值查找出具有特征信息的特征柵格，并對此類柵格根據點云密度與再劃分柵格邊長成反比的關系進行精劃分[4]，并對所有小柵格進行標號。此時每個小柵格內的點云數量相對均勻。

2 動態球K鄰域搜索

搜索算法采用了改進的自適應動態空間球算法完成。根據采樣點的近似密度自動算出其動態球的初始半徑r，接著使用動態球的外切立方體向外擴展且搜索K鄰域點集[2]，動態球擴展方式如圖2所示。

（1）根據采樣點P的局部近似密度、所處子空間內采樣點數目、子空間體積以及k值確定動態半徑。

（2）以步驟2為依據建立的動態球Pi的外切立方體內的

點為K鄰域候選點。

（3）設置點云閾值k，若K鄰域候選點小于閾值，則持續更新動態球，計算其外切立方體，尋找鄰域候選點并搜索。

當動態球的外切立方體中點云數達到閾值k時，只需再擴展一次便可確保完成K鄰域搜索。本算法提高了算法的效率并減少了動態球的擴展次數。

3 實驗分析

本文根據上述理論設計K鄰域算法（如圖3所示）并編寫程序，且以模型cat（n=10000）和bunny（n=31607）（如圖4所示）作為實驗對象，并在本人電腦上按以上算法完成對點云的K鄰域搜索，所得時間為完成點云模型內每點K鄰域搜索的平均時間。

對于本文的算法，主要的影響參數是由空間劃分中的調節因子α決定的空間球搜索時子塊內點云的數目Ns，調控因子α由點云密度ρ決定，本文取調控因子α的值為0.20、0.26、0.30，K取值為10、20、30、50、100分別對以上模型進行K鄰域搜索，結果如表1所示。

由表1可知是本文算法對cat和bunny點云模型平均每點K鄰域的搜索時間結果，根據公式σ=■計算搜索時間標準差進行分析可知本算法對α具有較好的穩定性；對于相同模型在相同α的情況下，搜索時間隨著K值的增大而增大，但增幅很??；對于不同模型在相同α和K值時，搜索時間隨模型的復雜度和點云數的增大而增大，但其變化處于相對穩定狀況。該算法分別與經典算法（八叉樹、KD樹）以及文獻[2]中的算法進行比較，把α設為0.26，其K鄰域搜索結果如表2所示。由實驗結果可知，本文算法相對其他算法對點云模型的K鄰域搜索所用時間較短。綜上，本算法對點云K鄰域的搜索不僅速度較快，針對不同復雜程度的模型其對每個點的K鄰域搜索耗時也較穩定，且對α也有較好的穩定性。

4 結束語

本文算法在規則立體柵格法的基礎上加入八叉樹的思維，使得每個柵格內包含相對均勻的點云，即含有相似的空間曲面信息，在對點云進行K鄰域搜索時可及時并正確的獲取其局部特征點，利用動態空間球的外切立方體擴展動態球并搜索K鄰域，減少了計算量并提高了搜索速度。實驗表明，本算法對調控因子具有較強的穩定性，并且針對不同數量的點云模型其搜索時間也較為穩定，與其他算法相比在搜索速度上具有相對的優勢。

參考文獻：

[1]孫金虎.點云模型分割與融合關鍵技術研究[D].南京航空航天大學，2013.

[2]楊軍，林巖龍，王小鵬，等.基于自適應空間球的k最近鄰域快速搜索算法[J].計算機工程，2014，40（10）：270-275.

[3]趙儉輝，龍成江，丁乙華，等.一種基于立方體小柵格的K鄰域快速搜索算法[J].武漢大學學報（信息科學版），2009，34（5）：114-117.

[4]張蓉.散亂點云的數據分割與特征提取技術研究[D].南昌大學，2016.endprint