一種改進(jìn)的立體柵格K鄰域搜索算法

摘 要：文章針對(duì)利用規(guī)則柵格進(jìn)行K鄰域搜索容易遺漏點(diǎn)云局部特征點(diǎn)以及自動(dòng)化程度不高的問(wèn)題，對(duì)K鄰域搜索算法進(jìn)行了改進(jìn)。該算法是在規(guī)則立體柵格的基礎(chǔ)上融入八叉樹(shù)思想，根據(jù)點(diǎn)云閾值查找點(diǎn)云特征柵格，對(duì)特征柵格按此柵格點(diǎn)云數(shù)與閾值的關(guān)系自動(dòng)計(jì)算棱長(zhǎng)并進(jìn)行精劃分，并采用自適應(yīng)空間動(dòng)態(tài)球算法擴(kuò)展并搜索采樣點(diǎn)的K鄰域點(diǎn)集。實(shí)驗(yàn)表明，與其他算法相比，該算法不僅具有較高的自動(dòng)化能力和較強(qiáng)的穩(wěn)定性，還能快速、準(zhǔn)確搜索采樣點(diǎn)的K鄰域。

關(guān)鍵詞：立體柵格；八叉樹(shù)；動(dòng)態(tài)空間球；K鄰域

中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：2095-2945（2017）29-0005-02

引言

鄰域是散亂點(diǎn)云中各點(diǎn)與其相鄰點(diǎn)間建立的拓?fù)潢P(guān)系，能有效的提高點(diǎn)云數(shù)據(jù)處理的速度和效率[1]。點(diǎn)云的數(shù)據(jù)處理和曲面重構(gòu)都受點(diǎn)云鄰域的搜索效率的影響[2]。K鄰域能同時(shí)處理均勻分布和非均勻分布的點(diǎn)云，且搜索速度快[1]。

本文的K鄰域搜索算法是在規(guī)則立體柵格法中融入八叉樹(shù)思想，使獲得的小立體柵格中包含數(shù)目適中的采樣點(diǎn)；再以改進(jìn)的自適應(yīng)空間動(dòng)態(tài)球算法實(shí)現(xiàn)對(duì)完成了空間劃分點(diǎn)云數(shù)據(jù)的K鄰域搜索，增強(qiáng)搜索的自動(dòng)化程度和穩(wěn)定性，并提高搜索的速度。

1 點(diǎn)云空間劃分

空間劃分是將點(diǎn)云模型的空間包圍區(qū)域按一定的邊長(zhǎng)進(jìn)行規(guī)則劃分，從而獲得多個(gè)完全相同的小立體柵格，完成K鄰域搜索的第一步。點(diǎn)云空間劃分分為點(diǎn)云初劃分和點(diǎn)云精劃分。由此獲得的每個(gè)小立體柵格中都具有類(lèi)似的曲面空間信息。

1.1 點(diǎn)云初劃分

點(diǎn)云模型的初劃分是將點(diǎn)云模型的空間包圍盒按照合適的邊長(zhǎng)劃分成m×n×l個(gè)小立體柵格[3][4]，并完成對(duì)每個(gè)柵格中點(diǎn)云的標(biāo)號(hào)，同時(shí)對(duì)每個(gè)柵格進(jìn)行掃描并記錄柵格中是否含有點(diǎn)云，并對(duì)無(wú)點(diǎn)云柵格進(jìn)行標(biāo)記為已訪問(wèn)，其效果如圖1所示。

1.2 點(diǎn)云精劃分

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

2 動(dòng)態(tài)球K鄰域搜索

搜索算法采用了改進(jìn)的自適應(yīng)動(dòng)態(tài)空間球算法完成。根據(jù)采樣點(diǎn)的近似密度自動(dòng)算出其動(dòng)態(tài)球的初始半徑r，接著使用動(dòng)態(tài)球的外切立方體向外擴(kuò)展且搜索K鄰域點(diǎn)集[2]，動(dòng)態(tài)球擴(kuò)展方式如圖2所示。

（1）根據(jù)采樣點(diǎn)P的局部近似密度、所處子空間內(nèi)采樣點(diǎn)數(shù)目、子空間體積以及k值確定動(dòng)態(tài)半徑。

（2）以步驟2為依據(jù)建立的動(dòng)態(tài)球Pi的外切立方體內(nèi)的

點(diǎn)為K鄰域候選點(diǎn)。

（3）設(shè)置點(diǎn)云閾值k，若K鄰域候選點(diǎn)小于閾值，則持續(xù)更新動(dòng)態(tài)球，計(jì)算其外切立方體，尋找鄰域候選點(diǎn)并搜索。

當(dāng)動(dòng)態(tài)球的外切立方體中點(diǎn)云數(shù)達(dá)到閾值k時(shí)，只需再擴(kuò)展一次便可確保完成K鄰域搜索。本算法提高了算法的效率并減少了動(dòng)態(tài)球的擴(kuò)展次數(shù)。

3 實(shí)驗(yàn)分析

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

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

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

4 結(jié)束語(yǔ)

本文算法在規(guī)則立體柵格法的基礎(chǔ)上加入八叉樹(shù)的思維，使得每個(gè)柵格內(nèi)包含相對(duì)均勻的點(diǎn)云，即含有相似的空間曲面信息，在對(duì)點(diǎn)云進(jìn)行K鄰域搜索時(shí)可及時(shí)并正確的獲取其局部特征點(diǎn)，利用動(dòng)態(tài)空間球的外切立方體擴(kuò)展動(dòng)態(tài)球并搜索K鄰域，減少了計(jì)算量并提高了搜索速度。實(shí)驗(yàn)表明，本算法對(duì)調(diào)控因子具有較強(qiáng)的穩(wěn)定性，并且針對(duì)不同數(shù)量的點(diǎn)云模型其搜索時(shí)間也較為穩(wěn)定，與其他算法相比在搜索速度上具有相對(duì)的優(yōu)勢(shì)。

參考文獻(xiàn)：

[1]孫金虎.點(diǎn)云模型分割與融合關(guān)鍵技術(shù)研究[D].南京航空航天大學(xué)，2013.

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

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

[4]張蓉.散亂點(diǎn)云的數(shù)據(jù)分割與特征提取技術(shù)研究[D].南昌大學(xué)，2016.endprint