一種排除鄰域的雙向最近鄰相似比算法 技術(shù)領(lǐng)域 [0001] 本發(fā)明涉及圖像數(shù)據(jù)處理技術(shù)領(lǐng)域，具體為一種排除鄰域的雙向最近鄰相似比算法。 背景技術(shù) [0002] 在三維計(jì)算機(jī)視覺領(lǐng)域，構(gòu)建點(diǎn)云中對(duì)應(yīng)關(guān)系被廣泛應(yīng)用于三維重建、三維對(duì)象識(shí)別、點(diǎn)云配準(zhǔn)、形狀檢索和定位等方向。構(gòu)建一個(gè)較好的對(duì)應(yīng)關(guān)系對(duì)后續(xù)成功估計(jì)兩片或多片點(diǎn)云間的轉(zhuǎn)換關(guān)系至關(guān)重要。 [0003] 現(xiàn)有的對(duì)應(yīng)點(diǎn)對(duì)構(gòu)建方法主要包括相似性得分(similarity?score，簡(jiǎn)稱SS)、雙向相似性得分(double?similarity?score，簡(jiǎn)稱BSS)、最近鄰相似比(nearest?neighbor?similarity?ratio，簡(jiǎn)稱NNSR)算法。SS通過計(jì)算兩個(gè)點(diǎn)云上特征描述子之間的相似度，并選擇其中相似度高的對(duì)應(yīng)點(diǎn)對(duì)來建立對(duì)應(yīng)關(guān)系。相似度通過描述子之間的特征距離進(jìn)行確定。但SS易被噪聲、遮擋和重疊區(qū)域等干擾影響，從而輸出錯(cuò)誤對(duì)應(yīng)關(guān)系。BSS與SS類似，不同之處在于BSS算法對(duì)初始對(duì)應(yīng)關(guān)系實(shí)施了一種雙向約束。該約束保留模型和場(chǎng)景特征描述子之間互為最佳匹配的對(duì)應(yīng)關(guān)系，再從保留的對(duì)應(yīng)關(guān)系中選擇相似度高的對(duì)應(yīng)點(diǎn)對(duì)來建立對(duì)應(yīng)關(guān)系。但是BSS算法則又過于嚴(yán)格，很容易排除正確對(duì)應(yīng)關(guān)系。為了獲得獨(dú)特性高的對(duì)應(yīng)關(guān)系，NNSR通過特征空間中最近和第二近距離的比率來懲罰對(duì)應(yīng)關(guān)系，使得選擇出的點(diǎn)對(duì)具有較為獨(dú)特的特征，不易被干擾影響。但是NNSR不能很好地判斷第一和第二特征近鄰點(diǎn)較接近的對(duì)應(yīng)關(guān)系的正確性。由于現(xiàn)有方法的局限性，使得構(gòu)建準(zhǔn)確的對(duì)應(yīng)關(guān)系集合仍是一個(gè)具有挑戰(zhàn)性的任務(wù)。 [0004] 現(xiàn)有的對(duì)應(yīng)點(diǎn)對(duì)構(gòu)建算法，要么容易誤排除正確的對(duì)應(yīng)關(guān)系，要么在應(yīng)對(duì)噪聲、雜亂和遮擋等干擾時(shí)魯棒性不足，難以全面適應(yīng)不同類型的點(diǎn)云數(shù)據(jù)。這些局限性在一定程度上影響了算法在復(fù)雜環(huán)境中的適應(yīng)性和穩(wěn)定性。 發(fā)明內(nèi)容 [0005] 本發(fā)明提出一種基于NNSR的改進(jìn)最近鄰相似比方法，稱為排除鄰域的最近鄰相似比(nearest?neighbor?similarity?ratio?on?non?adjacent?region，簡(jiǎn)稱Nannsr)算法。 通過對(duì)場(chǎng)景和模型關(guān)鍵點(diǎn)分別實(shí)施Nannsr算法，提取場(chǎng)景和模型上都具獨(dú)特性的點(diǎn)對(duì)，作為最終的輸出對(duì)應(yīng)點(diǎn)對(duì)。通過實(shí)施雙向鄰域約束和雙向Nannsr算法，形成一種穩(wěn)健的對(duì)應(yīng)點(diǎn)對(duì)構(gòu)建方法，稱為排除鄰域的雙向最近鄰相似比? (double?nearest?neighbor?similarity?ratio?on?non?adjacent?region，簡(jiǎn)稱NaDnnsr)算法，避免了點(diǎn)對(duì)的獨(dú)特性無法被正確判斷的問題，以解決現(xiàn)有算法要么容易誤排除正確的對(duì)應(yīng)關(guān)系，要么在應(yīng)對(duì)噪聲、雜亂和遮擋等干擾時(shí)魯棒性不足，難以全面適應(yīng)不同類型的點(diǎn)云數(shù)據(jù)的不足。 [0006] 為解決上述技術(shù)問題，本發(fā)明采用的一個(gè)技術(shù)方案是： [0007] 一種排除鄰域的雙向最近鄰相似比算法，用于構(gòu)建模型點(diǎn)云和場(chǎng)景點(diǎn)云之間的對(duì)應(yīng)關(guān)系，包括以下步驟： [0008] S1、輸入關(guān)鍵點(diǎn)及描述子：創(chuàng)建模型點(diǎn)云對(duì)象P和場(chǎng)景點(diǎn)云對(duì)象Q， ?和分別為模型點(diǎn)云對(duì)象P和場(chǎng)景對(duì)象Q上的關(guān)鍵點(diǎn)集合， 和 分別為模型關(guān)鍵點(diǎn)集合 和場(chǎng)景關(guān)鍵點(diǎn)集合 中的關(guān)鍵點(diǎn)對(duì)應(yīng)的局部特征 描述子集合； [0009] S2、初步匹配對(duì)應(yīng)關(guān)系：通過相似度匹配模型點(diǎn)云和場(chǎng)景點(diǎn)云的特征描述子來生成初始的對(duì)應(yīng)關(guān)系，構(gòu)建一個(gè)模型?場(chǎng)景之間的初始對(duì)應(yīng)點(diǎn)對(duì)集合 ； [0010] S3、施加雙向鄰域約束：對(duì)初始對(duì)應(yīng)關(guān)系實(shí)施一種松弛的鄰域約束，對(duì)初始對(duì)應(yīng)點(diǎn)對(duì)集合 進(jìn)行初步驗(yàn)證，排除明顯錯(cuò)誤的對(duì)應(yīng)點(diǎn)對(duì)，得到初步排除錯(cuò)誤對(duì)應(yīng)點(diǎn)對(duì)的對(duì)應(yīng)關(guān)系集合 ；這種鄰域約束方法不要求反向搜索對(duì)應(yīng)點(diǎn)時(shí)嚴(yán)格對(duì)應(yīng)上原來的點(diǎn)，而是保證在原來點(diǎn)的一定鄰域范圍內(nèi)。相較于BSS算法中的雙向約束，這種鄰域約束方法減少了正確對(duì)應(yīng)點(diǎn)對(duì)的誤排除。 [0011] S4、雙向?qū)嵤㎞annsr算法：將經(jīng)初步排除的對(duì)應(yīng)關(guān)系集合 作為輸入，對(duì)集合中的場(chǎng)景點(diǎn)和模型點(diǎn)分別實(shí)施Nannsr算法，計(jì)算出每個(gè)點(diǎn)對(duì)的獨(dú)特性分?jǐn)?shù)，并輸出分?jǐn)?shù)相對(duì)較優(yōu)的對(duì)應(yīng)點(diǎn)對(duì)獲得最終對(duì)應(yīng)點(diǎn)對(duì)集合 ；Nannsr算法利用一定鄰域范圍外的特征近鄰點(diǎn)取代NNSR算法中的第二特征近鄰點(diǎn)，避免NNSR算法中因第一和第二特征近鄰點(diǎn)的空間距離過近，導(dǎo)致無法判斷對(duì)應(yīng)關(guān)系正確性的問題。 [0012] S5、輸出對(duì)應(yīng)點(diǎn)對(duì)：以所提取出的雙向都具獨(dú)特性的最終對(duì)應(yīng)點(diǎn)對(duì)集合 為輸出，重新構(gòu)建模型點(diǎn)云與場(chǎng)景點(diǎn)云之間的對(duì)應(yīng)關(guān)系。輸出的對(duì)應(yīng)點(diǎn)對(duì)具有高的獨(dú)特性，不易被干擾影響，提高后續(xù)估計(jì)兩片或多片點(diǎn)云間轉(zhuǎn)換關(guān)系的準(zhǔn)確率。

1.一種排除鄰域的雙向最近鄰相似比算法，用于構(gòu)建模型點(diǎn)云和場(chǎng)景點(diǎn)云之間的對(duì)應(yīng)關(guān)系，其特征在于，包括以下步驟： S1、輸入關(guān)鍵點(diǎn)及描述子：創(chuàng)建模型點(diǎn)云對(duì)象P和場(chǎng)景點(diǎn)云對(duì)象Q， 和分別為模型點(diǎn)云對(duì)象P和場(chǎng)景對(duì)象Q上的關(guān)鍵點(diǎn)集合， 和 分別為模型關(guān)鍵點(diǎn)集合 和場(chǎng)景關(guān)鍵點(diǎn)集合 中的關(guān)鍵點(diǎn)對(duì)應(yīng)的局部特征描述子集合； S2、初步匹配對(duì)應(yīng)關(guān)系：通過相似度匹配模型點(diǎn)云和場(chǎng)景點(diǎn)云的特征描述子來生成初始的對(duì)應(yīng)關(guān)系，構(gòu)建一個(gè)模型?場(chǎng)景之間的初始對(duì)應(yīng)點(diǎn)對(duì)集合 ； S3、施加雙向鄰域約束：對(duì)初始對(duì)應(yīng)關(guān)系實(shí)施一種松弛的鄰域約束，對(duì)初始對(duì)應(yīng)點(diǎn)對(duì)集合 進(jìn)行初步驗(yàn)證，排除明顯錯(cuò)誤的對(duì)應(yīng)點(diǎn)對(duì)，得到初步排除錯(cuò)誤對(duì)應(yīng)點(diǎn)對(duì)的對(duì)應(yīng)關(guān)系集合 ； S4、雙向?qū)嵤㎞annsr算法：將經(jīng)初步排除的對(duì)應(yīng)關(guān)系集合 作為輸入，對(duì)集合中的場(chǎng)景點(diǎn)和模型點(diǎn)分別實(shí)施Nannsr算法，計(jì)算出每個(gè)點(diǎn)對(duì)的獨(dú)特性分?jǐn)?shù)，并輸出分?jǐn)?shù)相對(duì)較優(yōu)的對(duì)應(yīng)點(diǎn)對(duì)獲得最終對(duì)應(yīng)點(diǎn)對(duì)集合 ； S5、輸出對(duì)應(yīng)點(diǎn)對(duì)：以所提取出的雙向都具獨(dú)特性的最終對(duì)應(yīng)點(diǎn)對(duì)集合 為輸出，重新構(gòu)建模型點(diǎn)云與場(chǎng)景點(diǎn)云之間的對(duì)應(yīng)關(guān)系。 2.根據(jù)權(quán)利要求1所述的一種排除鄰域的雙向最近鄰相似比算法，其特征在于：步驟S2中，構(gòu)建初始對(duì)應(yīng)點(diǎn)對(duì)集合 的具體方法為：對(duì)于每個(gè)模型關(guān)鍵點(diǎn) ，從場(chǎng)景關(guān)鍵點(diǎn)集合 中搜索特征相似度由高到低排列的k個(gè)場(chǎng)景關(guān)鍵點(diǎn) ，對(duì)應(yīng)的描述子為，其中k為正整數(shù)，模型關(guān)鍵點(diǎn) 和場(chǎng)景關(guān)鍵點(diǎn) 組成初始對(duì)應(yīng)點(diǎn)對(duì) ，所有模型關(guān)鍵點(diǎn)上構(gòu)建的初始對(duì)應(yīng)點(diǎn)對(duì) 即為初始對(duì)應(yīng)點(diǎn)對(duì)集合 。 3.根據(jù)權(quán)利要求2所述的一種排除鄰域的雙向最近鄰相似比算法，其特征在于：模型關(guān)鍵點(diǎn)與場(chǎng)景關(guān)鍵點(diǎn)的初始對(duì)應(yīng)關(guān)系根據(jù)關(guān)鍵點(diǎn)上對(duì)應(yīng)的局部特征描述子的相似度來確定，對(duì)于兩個(gè)局部特征描述子 和 ，相似度 表示為： ??????????????????（1） 其中， 表示L2范數(shù)。 4.根據(jù)權(quán)利要求2所述的一種排除鄰域的雙向最近鄰相似比算法，其特征在于：步驟S3中，得到初步排除錯(cuò)誤對(duì)應(yīng)點(diǎn)對(duì)的對(duì)應(yīng)關(guān)系集合 的具體步驟為： S3.1、對(duì)于初始對(duì)應(yīng)點(diǎn)對(duì) ，定義以模型關(guān)鍵點(diǎn) 為球心、半徑為r1的雙向鄰域約束空間區(qū)域； S3.2、通過反向搜索，找到場(chǎng)景關(guān)鍵點(diǎn) 在模型點(diǎn)云上的對(duì)應(yīng)點(diǎn) ； S3.3、若 和 的空間距離在不大于r1，保留該初始對(duì)應(yīng)點(diǎn)對(duì) ，否則予以排除。