[發(fā)明專利]KD-Tree數(shù)據(jù)結(jié)構(gòu)的雙閾值搜索方法

無效

• 申請?zhí)枺?/td>: 201210100504.1
• 申請日: 2012-04-09
• 公開（公告）號: CN102737107A
• 公開（公告）日: 2012-10-17
• 發(fā)明（設(shè)計）人: 程欣宇
• 申請（專利權(quán)）人: 貴州拙人信息技術(shù)有限公司;程欣宇
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 貴陽中新專利商標(biāo)事務(wù)所 52100
• 代理人: 李亮;程新敏

技術(shù)領(lǐng)域

本發(fā)明涉及模式識別領(lǐng)域，尤其是一種數(shù)據(jù)結(jié)構(gòu)的搜索方法。?

背景技術(shù)

在模式識別領(lǐng)域，待識別的對象會被提取一個或者多個特征向量，然后再通過分類器進行模式分類。在海量的模式數(shù)據(jù)庫中，如圖像、聲音、視頻的特征向量數(shù)據(jù)庫中，模式的匹配速度是整個系統(tǒng)的性能瓶頸。?

近年來提出的SIFT、SURF等穩(wěn)定性非常好的圖像特征提取和描述方法，在圖像融合、全景圖像生成、圖像和視頻的超分辨和去噪、圖像和視頻搜索、增強現(xiàn)實、目標(biāo)識別等多種應(yīng)用場合中均有采用。特別是在圖像搜索中，海量圖像的產(chǎn)生海量的圖像特征向量（特征點），所以特征向量的搜索效率直接和圖像的搜索效率相關(guān)。?

設(shè)被檢索的庫中有n個特征向量，每個特征向量為k維。對于被搜索圖像中提取的m個特征向量，需要對比和模式庫哪些特征向量相似。兩個特征向量p和q相似是一個模糊的概念，在各個維度均歸一化的情況下，常使用如歐式距離來度量兩個特征向量的相似程度：?

?????????????????????（1）

在模式檢索系統(tǒng)中，我們還需要設(shè)置一個閾值來判斷相似或者不相似，設(shè)這個閾值為r，dist（p,q）<=r1時認(rèn)為p和q相似，dist（p,q）>r1時p和q不相似。r的取值在不同的應(yīng)用系統(tǒng)中，不同的設(shè)計者會根據(jù)準(zhǔn)確率和速度的需求進行設(shè)置。

最樸素地，使用順序遍歷式的搜索，將花費O(n)的時間，如圖1中的直線所示。如果采用無閾值完全精確匹配的二分搜索，只花費O(log₂(n))的時間，如圖1最低的一棵曲線所示，但在模式識別領(lǐng)域要搜索的對象，往往受各種變形和噪聲影響，無法使用無閾值完全精確匹配的二分搜索。針對這種情況，1975年J.L.?Bentley在Communications?of?the?ACM發(fā)表了文章Multidimensional?Binary?Search?Trees?Used?for?Associative?Searching，提出了被稱為KD-Tree數(shù)據(jù)結(jié)構(gòu)的多維二叉樹，。?

KD-Tree數(shù)據(jù)結(jié)構(gòu)仍然是一棵二叉樹，這棵二叉樹的每個結(jié)點有一個分割維度s，使得這個結(jié)點的左子樹中每個結(jié)點的s維值都小于這個結(jié)點的s維，右子樹中每個結(jié)點的s維值都大于這個結(jié)點的s維。?

在KD-Tree數(shù)據(jù)結(jié)構(gòu)樹上定義的搜索操作有三種：最近鄰搜索、k近鄰搜索和范圍搜索。本發(fā)明專利針對其中的范圍搜索，即利用類似（1）式定義某種相似性測度，根據(jù)閾值進行排除的搜索，搜索結(jié)果為庫中距離目標(biāo)特征向量的距離小于閾值的所有特征向量。?

以圖2和圖3中的KD-Tree數(shù)據(jù)結(jié)構(gòu)為例，k=2，n=6，如果要搜索距離p點（6,3）點不超過r=2的所有點，則應(yīng)該返回（7,2）一個點。按照現(xiàn)有的搜索算法（參考文獻資料和源碼如Intel公司的計算機視覺庫Open?CV的最新版本2.3.1中的kdTree.hpp），其搜索過程是：?

a、以根結(jié)點（7,2）為當(dāng)前結(jié)點；

b、計算和判斷dist（?（7,2）,（6,3）?）?<t，（7,2）加入結(jié)果集；

c、判斷（7,2）的分割維度為X，按X維計算距離7-6=1<2，則（7,2）的左右子樹均可能存在和（6,3）相似的結(jié)點；

d、（7,2）的左子樹根結(jié)點（5,4）以Y為分割維，Y=4比3小1，則同時需用搜索其左右子樹。

e、（7,2）的左子樹根結(jié)點（9,6）以Y為分割維，Y=6比3大2，則只需用搜索其左子樹；?

直至完成，所有6個點均和（6,3）比較過，由此可見，在閾值較大的情況下，KD-Tree數(shù)據(jù)結(jié)構(gòu)的范圍搜索和非KD-Tree數(shù)據(jù)結(jié)構(gòu)的順序遍歷搜索性能接近甚至相當(dāng)。

有次可以看出，在KD-Tree數(shù)據(jù)結(jié)構(gòu)范圍搜索中，閾值越小，越容易過濾掉搜索分支，搜索速度越快，越接近二分搜索；閾值越大，越難過濾分支，搜索速度越慢，越接近順序遍歷，而單純的降低閾值，則模式匹配的抗干擾性又急劇下降。?

發(fā)明內(nèi)容

本發(fā)明的目的是：提供一種KD-Tree數(shù)據(jù)結(jié)構(gòu)的雙閾值搜索方法，它能有效提高KD-Tree數(shù)據(jù)結(jié)構(gòu)的搜索效率，并使模式匹配的抗干擾性沒有很大的下降，以克服現(xiàn)有技術(shù)的不足。?