一種圖像檢索方法

2024-04-10 14:14:05 1

專利名稱：一種圖像檢索方法
技術領域：
本發明涉及一種圖像檢索方法，特別涉及一種在圖像資料庫中基於特徵點提取的 無指導圖像檢索方法。
背景技術：
隨著計算機技術和多媒體技術等的飛速發展，人們獲取數字圖像的途徑越來越 多，獲取數字圖像的能力也越來越強。大量圖片的獲取和存儲，使得對圖片庫進行有效的管 理成為難題。其中，在給定待檢索圖片的情況下，如何快速、準確地從圖像庫中找到用戶想 要的圖片是最基本卻最常用的問題之一。解決這個問題的有效手段便是圖像檢索技術。常 用的圖像檢索技術是主要可分為基於文本的和基於內容的二種。其中，基於文本的圖像檢 索技術通常通過在對比圖像庫中各圖像的特徵描述與待檢索圖片特徵描述來查找符合要 求的圖像。這種技術存在二個明顯不足首先，圖像特徵描述的複雜性使得對大量圖片進行 特徵描述成為一種異常繁瑣的工作。其次，圖像特徵描述的主觀性使得描述與圖片內容具 有一定的不一致性，必然導致檢索結果中存在大量不相關的結果。基於內容的圖像檢索技 術主要是對圖像本身的各種特徵進行分析和檢索的技術。目前常用的圖像特徵有顏色、紋 理和形狀等。但基於顏色直方圖的檢索方法過於依賴圖像的顏色，使得檢索結果的精度不 高。而基於紋理或形狀的檢索方法存在分析和描述困難的問題，使得檢索的精度和效率也 都不夠好。還有些圖像檢索方法採用了半監督的反饋技術，通過與用戶的交互來改善檢索 的結果，直到用戶滿意。這種方法通常會給用戶帶來較大的負擔和時間開銷。

發明內容
發明目的本發明所要解決的技術問題是針對現有技術的不足，提供一種圖像檢 索方法。技術方案本發明公開了一種圖像檢索方法，包括訓練和檢索兩個部分；所述訓練部分包括以下步驟步驟1，特徵點的提取對待檢索的圖像資料庫中的每一幅圖像進行特徵點的檢 測和描述，得到一組特徵點集；特徵點集中每一個特徵點包含點在圖像中的位置坐標和 一個128維的描述子矢量；步驟2，特徵點的補充和匹配關係的確定對基於同一場景的各圖像的特徵點集 進行補充，並找到同一場景中不同圖像特徵點間的匹配關係，具有匹配關係的點對應不同 圖像中的同一物理點；步驟3，同類點集的生成將所述在不同圖像中且對應同一場景的同一物理點的 特徵點放入一個同類特徵點集中；步驟4，特徵點集聚類對同類特徵點集的描述子矢量進行聚類，並確定各個聚類 中心；步驟5，圖像資料庫中每幅圖像特徵矢量的生成確定每幅圖像特徵點集的描述
5子矢量所屬的聚類，統計各個聚類的頻數，根據所述頻數生成一個長度為聚類數的特徵矢 量；所述步驟2具體包括以下步驟步驟21，在同一場景的所有圖像點集中，對於N個屬於同一場景的圖像點集，選取 一個特徵點最多的圖像點集作為基準特徵點集Na ；步驟22，對基準特徵點集Na之外的每個圖像特徵點集隊中的每個特徵點Fp在基 準特徵點集Na中求取該特徵點&基於描述子矢量歐拉距離的最近鄰特徵點F/和次近鄰 特徵點F/』;將特徵點&和基準特徵點集隊中的最近鄰特徵點F/的對應關係(FyF/ )作 為新的匹配關係加入特徵點集隊和基準特徵點集隊的匹配關係集中；再用特徵點&與基 準特徵點點集Na中的最近鄰特徵點F/及次近鄰特徵點F/』的描述子矢量歐拉距離的比值 閾值(本發明中一般設定比值閾值<0.8，當然也可以根據精度需求選取其他數值，一般範 圍在<0.8士0. 2)過濾超出閾值範圍的匹配關係；步驟23，對步驟22中得到的特徵點集隊和基準特徵點集隊的匹配關係集中各 匹配特徵點對所對應的各坐標對，確定準確的匹配坐標子集和變換對應的線性映射關係矩 陣，其中，準確的匹配坐標是指匹配的坐標點所指示的不同圖像上的位置對應物理上同一 物體或同一場景上的同一點；步驟24，對所述圖像點集隊中未匹配到的特徵點G」使用所述線性映射矩陣計算 其在基準特徵點集Na對應圖像中的匹配坐標點。如果該匹配坐標超出圖像大小，則表示在 基準特徵點集Na對應的圖像中找不到特徵點&對應的匹配，否則計算匹配坐標的特徵點描 述子矢量，形成新的特徵點G/;如果求得的描述子矢量與當前圖像點集隊中的特徵點&的 描述子矢量的歐拉距離小於設定的閾值(本發明中一般設定該閾值< 350.當然也可以根 據精度需求選取其他數值，一般範圍在< 350士 10)，則將所述新生成特徵點Gi』點加入基 準特徵點集Na中並將已知的圖像點集M中的特徵點&和新生成的特徵點G/的對應關係 (&，G/ )作為新的匹配關係放入圖像點集隊和基準特徵點集隊的匹配關係集中，否則特 徵點&的匹配特徵點在基準特徵點集隊對應的圖像中不存在，捨棄新的特徵點G/ ；步驟25，對每個所述圖像點集隊中所有未匹配特徵點返回執行步驟24，最後得到 基準特徵點集Na基於特徵點隊補充後的特徵點集Nai和更新的匹配關係集；步驟26，將所述基準特徵點集Na基於特徵點集&至特徵點集隊補充後的特徵點 集Nal至特徵點集Nai合併為最終基準特徵點集Na』，並且使相似的特徵點只保留一個在最終 基準特徵點集Na』中；相似特徵點通過二個條件來判定其一是兩個特徵點的沿x或y方向 的坐標差均不超過2個像素，其二是它們的描述子矢量距離小於指定的閾值(本發明中一 般設定該閾值< 50，當然也可以根據精度需求選取其他數值，一般範圍在< 50士 10)；將步 驟22至步驟25中得到的所述各圖像特徵點集隊與原基準特徵點集Na的匹配關係集更新 為各圖像點集隊與新的基準特徵點集Na』的匹配關係集；步驟27，對在每個所述圖像點集隊中未找到匹配點的最終基準特徵點集Na』中的 特徵點Mp返回步驟24求得其在圖像點集隊對應圖像中的對應坐標和相應的特徵點描述 子矢量，生成新的特徵點M/ ；將該特徵點M/加入圖像點集隊並將它和新基準特徵點集Na』 中的特徵點虯的對應關係(M/，M》保存到圖像點集隊和基準特徵點集Na』的匹配關係集 中；
步驟28，基於步驟23至步驟27得到的匹配關係集，找到同一場景的幾幅圖像中對 應同一物理點的特徵點，即同類點；如果經過步驟23至步驟27，最終基準特徵點集Na』中的 特徵點ma分別同圖像點集隊中的特徵點叫匹配，即得到的匹配關係為OvnO，…，Ovp ma), (ma+1，ma)，貝U nv m^, ma, ma+1,…為同類點，否貝U nv m^, ma, ma+1,...不為同 類佔.所述步驟4具體包括以下步驟步驟41，計算各個同類點集的描述子矢量的質心向量^和其包含的點的個數叫；步驟42，對集合(Ci，m,)用加權的聚類方法進行聚類，確定各聚類的聚類中心；步驟43，設定質心為向量^的同類特徵點所屬聚類為質心向量(^所屬聚類；步驟44，對圖像資料庫中的每幅圖像計算其特徵點所屬各聚類的頻數ni ；步驟45，計算每個聚類在圖像資料庫中出現的概率對數Wi，Wi = lr^N/X)，其中N 為圖像總數，Ni為當前聚類所出現的圖像的個數；步驟46，對圖像資料庫中每幅圖像，基於特徵點所屬聚類的頻數ni和各聚類的概 率對數生成一個特徵矢量並單位化；所述檢索部分包括以下步驟步驟6，提取待檢索圖片的特徵點，生成特徵點集；步驟7，計算各個特徵點描述子向量到各個聚類中心的距離，以最小距離確定當前 特徵點所屬聚類；步驟8，計算待檢索圖片的特徵點所屬各個聚類的頻數ni ；步驟9，基於待檢索圖片的特徵點所屬聚類的頻數ni和所述的各聚類的概率對數 w,生成一個特徵矢量並單位化；步驟10，計算待檢索圖片的特徵矢量到圖片庫各圖像特徵矢量的歐拉距離，選取 距離最小的圖像輸出為檢索結果。本發明步驟1中，使用SIFT算法對圖像進行特徵點的檢測和描述，得到圖像的所 有特徵點位置和描述子矢量。SIFT算法的具體內容可參見維基百科關於尺度不變特徵轉換 的闡述或作者David Lowe的原論文。本發明步驟23中利用隨機採樣一致性算法魯棒地確定準確的匹配坐標子集和 變換對應的線性映射關係矩陣，具體步驟是首先隨機地選取坐標對中選取的四對坐標點 ((x」 yj), (x/ , y/ )), ((x2, y2), (x2，，y2' )), ((x3, y3), (x3，, y3' )), ((x4, y4), (x4，, y4')), 四對坐標在各自圖像中的任三點都不處在同一條直線上。假設四對坐標點滿足映射關係 H*[Xi，yi，l]T= [Xi』，yi』，l]T，其中H是3X3的係數矩陣，為待求解的線性映射矩陣；將上述 四對匹配坐標代入映射關係求解出矩陣H ；再將除上述四對坐標外的其他匹配坐標對一一 代入映射關係，確定是否符合當前矩陣H的映射關係；如果符合，標記為正確匹配；否則，標 記為錯誤匹配；重新選取四對坐標點，執行上述過程，得到一個新的線性映射矩陣H和對應 的匹配關係。如此循環n(n = 10)次，選出正確匹配對數目最多的線性映射矩陣H並保存 對應的正確的匹配關係。本發明步驟4中，使用加權k-means的聚類方法把同類特徵點集的描述子矢量聚 成k類，其具體步驟是步驟42a，在所有的初始同類特徵點集描述子質心矢量Ci的集合中隨機選取一個矢量作為第一個聚類中心C1;步驟42b，在選取第i個聚類中心Q時，首先在初始質心矢量集合中隨機 抽取m(本發明中可以選取m= 10，當然，也可以根據需求選擇其他任意數量)個矢 量Xl，X2，…，xm，分別計算各個矢量到已選取聚類中心集合IA，C2，…，(VJ的最 小歐拉距離，再選擇該最小距離中的最大值對應的抽取矢量為新的聚類中心Q ；即
其中 Ci 為最後確定的第 i 個聚類中心，xi，x2，…，
Xm為當前隨機抽取的m個初始同類特徵點集描述子的質心矢量，(^，(2，為已選取的 聚類中心；minj = i, ..., ^dist (xk, Cj)求取了隨機抽取的質心矢量xk到各已選出的聚類中心 的最小距離，
選出質心矢量Xl，X2，…，Xm中到聚類中心 Q, C2,…，C^最小距離的最大者；步驟42c，重複步驟42b選取k個聚類中心；步驟42d，計算各初始同類特徵點集描述子質心矢量到聚類中心的歐拉距離，以最 小距離確定當前質心矢量所屬聚類；步驟42e，計算新生成的各聚類的質心矢量，假設當前的第i個聚類是矢量集 {(cn,wn), (ci2,wi2),，(、，、)，…}，則其質心計算公式為
中是初始同類特徵點集質心矢量，WiJ是對應同類特徵點集所包含特徵點的個數；步驟42f，循環執行步驟42e直到計算出所有聚類的質心矢量C/，再將每個聚類 計算所得的質心矢量C/同對應聚類的中心Ci做比較，如果全部k個聚類的比較結果均相 等或聚類過程超過最大迭代次數，則聚類過程結束，否則以計算所得各聚類的質心矢量作 為對應聚類的中心重新執行步驟42d。有益效果本發明的顯著優點是檢索方法具有很好的效率並且檢索結果具有很高 的精度。具體而言，本發明將分別從算法的精度和效率方面來闡述(1)算法的精度保證 尺度不變特徵變換(Scale-invirant Feature Transform, SIFT)是一種圖像局部特徵的檢 測和描述算法，其生成的描述子對圖像的平移、旋轉、縮放、亮度變化及噪聲等都具有良好 的不變性，對視角的變換和仿射變換也具有一定程度的穩定性。一幅圖像的SIFT特徵點描 述子集合是對圖像本質內容的縮略描述。不同內容的圖像的SIFT特徵描述子集合具有很 好的區分性。因此，SIFT被廣泛應用於物體的識別、圖像的匹配等實際應用中。本發明的 主要思想是將SIFT特徵點提取方法應用到圖像檢索中，用以提高檢索算法的精度。其基本 思想是先用SIFT算子對圖像中的圖像進行特徵提取和描述，再對所有提取的特徵點集進 行聚類，並基於得到的聚類為每幅圖像和待檢索圖像計算一個特徵矢量。最後比較待檢索 圖像和庫中各圖像的特徵矢量，選出最後結果。在此基礎上，為進一步提高精度，還著重解 決了二個問題1)由於需對大量的圖片做統一的特徵檢測，SIFT算法的各項參數需統一取 值，因此在檢測過程中各圖像必然存在不同程度的特徵點缺失。2)對於同一場景的不同圖 像的特徵點集合，必存在一些物理上屬於同一點的同類點。由於受到特徵描述和聚類算法 等誤差的影響，這些同類點在聚類完成後，可能屬於不同的聚類。以上二點都必然對檢索結 果的正確性產生影響。本發明的解決辦法是1)在對圖像資料庫的特徵點提取完成後，本 發明用隨機採樣一致性(RANdom SAmple Consensus, RANSAC)算法找出了同一場景不同圖 像之間的變換關係。基於該變換關係，對各圖像的特徵點集進行了補充，並找出了屬於物理上同一點的同類點。2)本發明採用了基於點集的聚類方法，保證了所有的同類點在聚類之 後都屬於同一個聚類。(2)算法的效率保證本發明包括二個階段訓練和檢索。訓練階段 主要是對圖像資料庫中的圖片作一次性的預處理。這一階段可作為離線操作而不增加真正 的檢索時間。真正的檢索只發生在檢索階段。在此階段，本發明將只對待檢索圖片(結合 訓練階段的結果)作處理。因此，本發明能更好地保證檢索的效率，滿足實時響應的需求。


下面結合附圖和具體實施方式
對本發明做更進一步的具體說明，本發明的上述和 /或其他方面的優點將會變得更加清楚。圖1為本發明方法的基本流程圖。圖2為本發明所述SIFT特徵點的補充和同類點集的生成流程圖。圖3為圖像資料庫各圖像特徵矢量生成流程圖。
具體實施例方式如圖1所示，在訓練階段，首先對給定的圖像資料庫中的每一幅圖像用實現的 SIFT算法進行特徵點的檢測和描述，得到一組特徵點集。每一個特徵點將包含以下信息 點在圖像中的位置坐標、所描述區域的尺度、所描述區域的主梯度方向和描述子矢量。對每 一張圖像，基於其相同場景的其他圖像補充特徵點並生成同類點集，如圖2所示。再基於同 類點集進行聚類並確定所有特徵點所屬聚類，統計每幅圖像所屬各聚類的頻數進而形成圖 像的特徵矢量，如圖3的流程。在檢索階段，首先對待檢索圖片用SIFT算法提取特徵點，得 到一組特徵點集。對每個特徵點求取其描述子向量與訓練階段生成的各聚類中的歐拉距 離，選取距離最小的聚類作為當前特徵點所屬聚類。統計每個聚類包含的特徵點的個數rv 結合訓練階段得到的各聚類的概率對數Wi，生成待檢索圖像的特徵矢量，具體為[nlWl，…， niWi,…]。為了保證檢索結果不受各圖像具體特徵點個數的影響，需對特徵矢量進行單位 化。即最後的特徵矢量為[nlWl/E niWi，…，niWi/E niWi，…]。最後計算該特徵矢量與 圖像資料庫各圖像特徵矢量的歐拉距離，選取其中最小的一幅或幾幅作為檢索結果。具體地說，如圖1所示，本發明公開了一種圖像檢索方法，包括訓練和檢索兩個部 分；所述訓練部分包括以下步驟步驟1，特徵點的提取對圖像資料庫中的每一幅圖像進行特徵點的檢測和描述， 得到一組特徵點集；特徵點集中每一個特徵點包含點在圖像中的位置坐標和一個128維 的描述子矢量；步驟2，特徵點的補充和匹配關係的確定對基於同一場景的各圖像的特徵點集 進行補充，並找到同一場景中不同圖像特徵點間的匹配關係，具有匹配關係的點對應不同 圖像中的同一物理點；步驟3，同類點集的生成將所述在不同圖像中且對應同一場景的同一物理點的 特徵點放入一個同類特徵點集中；步驟4，特徵點集聚類對同類特徵點集的描述子矢量進行聚類，並確定各個聚類 中心；
步驟5，圖像資料庫中每幅圖像特徵矢量的生成確定每幅圖像特徵點集的描述 子矢量所屬的聚類，統計各個聚類的頻數，根據所述頻數生成一個長度為聚類數的特徵矢 量；如圖2所示，所述步驟2具體包括以下步驟步驟21，在同一場景的所有圖像點集中，對於N個屬於同一場景的圖像點集，選取 一個特徵點最多的圖像點集作為基準特徵點集Na ；步驟22，對基準特徵點集Na之外的每個圖像特徵點集隊中的每個特徵點&，在基 準特徵點集Na中求取該特徵點&基於描述子矢量歐拉距離的最近鄰特徵點F/和次近鄰 特徵點F/』;將特徵點&和基準特徵點集隊中的最近鄰特徵點F/的對應關係(FyF/ )作 為新的匹配關係加入特徵點集隊和基準特徵點集隊的匹配關係集中；再用該特徵點&與 基準特徵點點集隊中的最近鄰特徵點F/和次近鄰特徵點F/』的描述子矢量歐拉距離的比 值閾值過濾超出閾值範圍的匹配關係；步驟23，對步驟22中得到的特徵點集隊和基準特徵點集Na的匹配關係集中各 匹配特徵點對所對應的各坐標對，確定準確的匹配坐標子集和變換對應的線性映射關係矩 陣，其中，準確的匹配坐標是指匹配的坐標點所指示的不同圖像上的位置對應物理上同一 物體或同一場景上的同一點；步驟24，對所述圖像點集隊中每一個未匹配到的特徵點G」使用所述線性映射矩 陣計算其在基準特徵點集Na對應圖像中的匹配坐標點。如果該匹配坐標超出圖像大小，則 表示在基準特徵點集Na對應的圖像中找不到特徵點&對應的匹配，否則計算匹配坐標的特 徵點描述子矢量，形成新的特徵點G/;如果求得的描述子矢量與當前圖像點集隊中的特徵 點&的描述子矢量的歐拉距離小於設定的閾值，則將所述新生成特徵點G/點加入基準特 徵點集Na中並將已知的圖像點集隊中的特徵點&和新生成的特徵點G/的對應關係(Gp G/ )作為新的匹配關係放入圖像點集隊和基準特徵點集隊的匹配關係集中，否則特徵點 &的匹配特徵點在基準特徵點集隊對應的圖像中不存在，捨棄新的特徵點G/ ；步驟25，對每個所述圖像點集隊中所有未匹配特徵點返回執行步驟24，最後得到 基準特徵點集Na基於特徵點隊補充後的特徵點集Nai和更新的匹配關係集；步驟26，將所述基準特徵點集Na基於特徵點集&至特徵點集隊補充後的特徵點 集Nal至特徵點集Nai合併為最終基準特徵點集Na』，並且使相似的特徵點只保留一個在最終 基準特徵點集Na』中；相似特徵點通過特徵點的坐標差閾值和描述子矢量的距離小於設定 的閾值來判定；將步驟22 步驟25中得到的所述各圖像特徵點集隊與原基準特徵點集Na 的匹配關係集更新為各圖像點集隊與新的基準特徵點集Na』的匹配關係集；步驟27，對在每個所述圖像點集隊中未找到匹配點的最終基準特徵點集Na』中的 特徵點Mp返回步驟24求得其在圖像點集隊對應圖像中的對應坐標和相應的特徵點描述 子矢量，生成新的特徵點M/ ；將該特徵點M/加入圖像點集隊並將它和新基準特徵點集Na』 中的特徵點虯的對應關係(MyM/ )保存到圖像點集隊和基準特徵點集Na』的匹配關係集 中；步驟28，基於步驟23 步驟27得到的匹配關係集，找到同一場景的幾幅圖像中對 應同一物理點的特徵點，即同類點；如果經過步驟23 步驟27，最終基準特徵點集Na』中的 特徵點ma分別同圖像點集隊中的特徵點叫匹配，即得到的匹配關係為OvnO，…，Ovp
10ma), (ma+1，ma)，貝U nv m^, ma, ma+1,…為同類點，否貝U nv m^, ma, ma+1,...不為同 類佔.如圖3所示，所述步驟4具體包括以下步驟步驟41，計算各個同類點集的描述子矢量的質心向量^和其包含的點的個數％ ；步驟42，對集合(Ci，mi)用加權的聚類方法進行聚類，確定各聚類的聚類中心；步驟43，設定質心為向量^的同類特徵點所屬聚類為質心向量(^所屬聚類；步驟44，對圖像資料庫中的每幅圖像計算其特徵點所屬各聚類的頻數ni ；步驟45，計算每個聚類在圖像資料庫中出現的概率對數Wi，Wi = lr^N/X)，其中N 為圖像總數，Ni為當前聚類所出現的圖像的個數；步驟46，對圖像資料庫中每幅圖像，基於特徵點所屬聚類的頻數ni和各聚類的概 率對數生成一個特徵矢量並單位化；所述檢索部分包括以下步驟步驟6，提取待檢索圖片的特徵點，生成特徵點集；步驟7，計算各個特徵點描述子向量到各個聚類中心的距離，以最小距離確定當前 特徵點所屬聚類；步驟8，計算待檢索圖片的特徵點所屬各個聚類的頻數^步驟9，基於待檢索圖片的特徵點所屬聚類的頻數ni和所述的各聚類的概率對數 w,生成一個特徵矢量並單位化；步驟10，計算待檢索圖片的特徵矢量到圖片庫各圖像特徵矢量的歐拉距離，選取 距離最小的圖像輸出為檢索結果。本發明步驟1中，使用SIFT算法對圖像進行特徵點的檢測和描述，得到圖像的所 有特徵點位置和描述子矢量。本發明步驟23中利用隨機採樣一致性算法魯棒地確定準確的匹配坐標子集和 變換對應的線性映射關係矩陣，具體步驟是首先隨機地選取坐標對中選取的四對坐標點 ((x」 yj), (x/ , y/ )), ((x2, y2), (x2，，y2' )), ((x3, y3), (x3，, y3' )), ((x4, y4), (x4，, y4')), 四對坐標在各自圖像中的任三點都不處在同一條直線上。假設四對坐標點滿足映射關係 H*[Xi，yi，l]T= [Xi』，yi』，l]T，其中H是3X3的係數矩陣，為待求解的線性映射矩陣；將上述 四對匹配坐標代入映射關係求解出矩陣H ；再將除上述四對坐標外的其他匹配坐標對一一 代入映射關係，確定是否符合當前矩陣H的映射關係；如果符合，標記為正確匹配；否則，標 記為錯誤匹配；重新選取四對坐標點，執行上述過程，得到一個新的線性映射矩陣H和對應 的匹配關係。如此循環n(n = 10)次，選出正確匹配對數目最多的線性映射矩陣H並保存 對應的正確的匹配關係。本發明步驟4中，使用加權k-means的聚類方法把同類特徵點集的描述子矢量聚 成k類，其具體步驟是步驟42a，在所有的初始同類特徵點集描述子質心矢量Ci的集合中隨機選取一個 矢量作為第一個聚類中心C1;步驟42b，在選取第i個聚類中心Q時，首先在初始質心矢量集合中隨機抽取 m個矢量Xl，x2,…，xm，分別計算各個矢量到已選取聚類中心集合IA，C2，…，(VJ的 最小歐拉距離，再選擇該最小距離中的最大值對應的抽取矢量為新的聚類中心Q ；即Ci=argmaxXi，...，Xmminj=1，..,i_1dist(xk,Cj)，其中 Ci 為最後確定的第 i 個聚類中心，xi，x2，…，
xm為當前隨機抽取的m個初始同類特徵點集描述子的質心矢量，(^，(2，為已選取的 聚類中心；mirijM,...^ dist(xk,CJ)求取了隨機抽取的質心矢量xk到各已選出的聚類中心 的最小距離，argmaxx,，. ■ .』Xm j=l,. ■ .，i一1
disKx^Cj)選出質心矢量Xl，X2，…，Xm中到聚類中心
Q, c2,…，c^最小距離的最大者；步驟42c，重複步驟42b選取k個聚類中心；步驟42d，計算各初始同類特徵點集描述子質心矢量到聚類中心的歐拉距離，以最 小距離確定當前質心矢量所屬聚類；步驟42e，計算新生成的各聚類的質心矢量，假設當前的第i個聚類是矢量集 {(cn,Wn) , (ci2, wi2),…，(Cij, Wij) , ...},則其質心計算公式為 C/ =E jCij^Wij/ E jWij,其 中是初始同類特徵點集質心矢量，WiJ是對應同類特徵點集所包含特徵點的個數；步驟42f，循環執行步驟42e直到計算出所有聚類的質心矢量C/，再將每個聚類 計算所得的質心矢量C/同對應聚類的中心Q做比較，如果全部k個聚類的比較結果均相 等或聚類過程超過最大迭代次數，則聚類過程結束，否則以計算所得各聚類的質心矢量作 為對應聚類的中心重新執行步驟42d。實施例圖2以三幅同一場景的不同圖像為例，給出了對圖像資料庫中各圖像初始特徵點 集進行補充以及生成同類點集的流程。步驟20是初始動作。步驟21選取了特徵點最多的 點集C作為匹配的基準特徵點集。步驟22對特徵點集A中的每一個特徵點求其在基準特 徵點集C中基於描述子矢量歐拉距離的最近鄰匹配，得到初始匹配集，並用最近鄰和次緊 鄰的比率閾值(0.8)過濾掉大於閾值的匹配關係。步驟23對經22的得到的匹配點集的所 有坐標對，利用RANSAC算法魯棒地確定其準確的坐標匹配子集和變換對應的線性映射關 系矩陣。RANSAC的執行過程是每次隨機地在初始匹配對中選取4對坐標點，要求這4對坐 標在特徵點集A和C對應的圖像中的點都不在同一條直線上。求解出符合這4個匹配關係 的線性映射矩陣。將其它坐標匹配對代入並查看其是否具有當前的線性映射矩陣的映射關 系。如果有，標記為正確匹配。否則，標記為錯誤匹配。循環地執行上述過程多次，選出正 確匹配對最多的線性映射矩陣MAc並保存正確的匹配關係。步驟24a首先選取一個特徵點 集A中未正確匹配的特徵點，用MAe計算其在基準特徵點集C對應圖像中的坐標點。如果該 坐標超出了特徵點集C對應圖像的範圍，則表示該失配特徵點在特徵點集C對應的圖像中 沒有匹配點，在特徵點集A中選取下一個未處理的失配特徵點返回步驟24a進行處理。否 則，在求得的匹配坐標處用SIFT求得對應的描述子矢量並判斷該描述子矢量與當前A中的 特徵點描述子矢量的歐拉距離是否小於設定的閾值350。如果是，則進行步驟24b將該新 生成的特徵點加入特徵點集C中並將當前匹配關係放入匹配集。否則同樣表示該失配特徵 點在特徵點集C對應的圖像中不存在匹配點。處理完當前失配特徵點後，繼續在特徵點集 A中選取下一個未處理的失配特徵點返回步驟24a處理。當對特徵點集A中所有失配特徵 點進行完上述過程後，步驟24b中得到了補充後的基準特徵點集C』，和新的匹配集。同樣 的方法，步驟25a 25e獲得了補充後的特徵點集C』B和對應的匹配集。步驟2f將特徵點 C』 A和特徵點集C』 B合併為最終基準特徵點集C』，並保證相似的特徵點只保留一個在最終 基準特徵點C』中。相似特徵點通過二個條件來判定其一是兩個特徵點的沿x或y方向的坐標差均不超過2，其二是它們的描述子矢量距離小於指定的閾值50。步驟27a，27b分別 對基準特徵點集C』中尚未在特徵點集A、B中找到匹配的點，生成新的匹配點用於補充A和 B，方法同步驟24。步驟28基於以上得到的所有的匹配關係找到同一場景的幾幅圖像中對 應同一物理點的特徵點，並把它們放入一個同類特徵點集中。具體地，假設a、b、c分別是特 徵點集A、B、C中的三個特徵點。現確定他們的匹配關係為化與(匹配，b與c也匹配。那 麼，可將a、b、c視為同類點並放入一個同類點集中。步驟29是圖2的結束步驟。圖3給出了圖像資料庫中各圖像的特徵矢量的生成流程圖。步驟40為初始動作。 步驟41計算了各個同類點集的描述子矢量的質心向量Ci和其包含的點的個數％ ；步驟42 對集合(c」 m,)用加權k-means的聚類方法進行聚類。所述加權k-平均聚類方法的具體 過程是(42a)在所有的初始矢量Ci的集合中隨機選取一個矢量作為第一個聚類中心q ； (42b)在選取第i個聚類中心Q時，首先在初始矢量Ci集合中隨機抽取m(m= 10)個矢量 Xl，X2，…，Xm，分別計算它們到集合{A，C2，的最小歐拉距離，再選擇該最小距離中 的最大值對應的抽取矢量為新的聚類中心C」即fpargmax》，...,Xm minj=1 .^distCx^Cj)； (42c)重複(42b)選取k個聚類中心；(42d)計算各初始矢量到聚類中心的歐拉距離，以最 小距離確定當前質心矢量所屬聚類；(42e)計算新生成的各聚類的質心矢量作為新的聚類 中心。由於初始矢量(^是有權值的，因此質心的計算需將權值考慮在內。假設當前的第 i個聚類是矢量集Kcn，wn)，(ci2, wi2),…，(CiJ, WiJ),…}，則其質心計算公式為C/ = E jc.j^j/ E jWiJO (42f)循環執行步驟(42e)直到計算出所有聚類的質心矢量C/，再將 每個聚類計算所得的質心矢量C/同對應聚類的中心Q做比較，如果全部k個聚類的比較 結果均相等或聚類過程超過最大迭代次數，則聚類過程結束，執行步驟42g，否則以計算所 得各聚類的質心矢量作為對應聚類的中心重新執行步驟42d ； (42g)聚類結束；步驟43設 定質心為Q的同類特徵點所屬聚類為Q所屬聚類；步驟44對圖像資料庫中的每幅圖像計 算其特徵點所屬各聚類的頻數1^ ；步驟45計算每個聚類在圖像資料庫中出現的概率對數Wi =ln(N/Ni)，其中N為圖像總數，隊為當前聚類所出現的圖像的個數；步驟46對計算圖像 資料庫中每幅圖像，基於其特徵點所屬聚類的頻數和各聚類的概率對數生成一個特徵矢量 並單位化，具體為[nlWl/ E niWi,…，niWi/ E niWi,…]；步驟47是流程的結束步驟。表1給出了用本發明的方法進行相關測試的結果。用於測試的硬體環境是 Intel-Core2Duo 2. 93GHz 3G 內存。軟體環境是 Visual Studio2005 和 Window XP。本發 明用C++語言實現了本發明提出的方法。測試圖像來源於University of Kentucky的 Uft^MM^M^fu^^ (Center for Visualization and Virtual Environments)白勺 RecognitionBenchmark Images0本發明從中抽取了 2組數據進行了測試，分別包含400張 和1112張圖片。各組數據中，每4張圖片是關於同一場景的。本發明分別選取其中3張用 於形成圖像資料庫的訓練，另外1張用於檢索測試。因此每組數據均分為訓練和檢索二部 分，數據量比率為3 1。在進行檢索測試時，每幅圖像最多有3幅相同場景的正確檢索結 果。本發明通過返回結果的正確率來判斷算法的好壞。表中「第一返回正確率」指的是第一 張檢索結果圖像的正確率。「第一、二返回正確率」表示頭二張返回結果均正確的概率。「第 一、二、三返回正確率」表示頭三張返回結果均正確的概率。將本發明的方法同只用k-平均 聚類的方法(即沒有特徵點補充和加權k-平均)進行了對比。由圖可見，本發明的方法具 有很高的檢索精度。在檢索效率方面，當給定一幅待檢索圖像後，本發明的方法能在1秒內給出結果，保證了搜索的實時性。表 1 本發明提供了一種圖像檢索方法的思路及方法，具體實現該技術方案的方法和途 徑很多，以上所述僅是本發明的優選實施方式，應當指出，對於本技術領域的普通技術人員 來說，在不脫離本發明原理的前提下，還可以做出若干改進和潤飾，這些改進和潤飾也應視 為本發明的保護範圍。本實施例中未明確的各組成部分均可用現有技術加以實現。
權利要求
一種圖像檢索方法，其特徵在於，包括訓練和檢索兩個部分；所述訓練部分包括以下步驟步驟1，特徵點的提取對圖像資料庫中的每一幅圖像進行特徵點的檢測和描述，得到一組特徵點集；特徵點集中每一個特徵點包含點在圖像中的位置坐標和一個128維的描述子矢量；步驟2，特徵點的補充和匹配關係的確定對基於同一場景的各圖像的特徵點集進行補充，並找到同一場景中不同圖像特徵點間的匹配關係，具有匹配關係的點對應不同圖像中的同一物理點；步驟3，同類點集的生成將所述在不同圖像中且對應同一場景的同一物理點的特徵點放入一個同類特徵點集中；步驟4，特徵點集聚類對同類特徵點集的描述子矢量進行聚類，並確定各個聚類中心；步驟5，圖像資料庫中每幅圖像特徵矢量的生成確定每幅圖像特徵點集的描述子矢量所屬的聚類，統計各個聚類的頻數，根據所述頻數生成一個長度為聚類數的特徵矢量；所述步驟2具體包括以下步驟步驟21，在同一場景的所有圖像點集中，對於N個屬於同一場景的圖像點集，選取一個特徵點最多的圖像點集作為基準特徵點集Na；步驟22，對基準特徵點集Na之外的每個圖像特徵點集Ni中的每個特徵點Fi，在基準特徵點集Na中求取該特徵點Fi基於描述子矢量歐拉距離的最近鄰特徵點Fi』和次近鄰特徵點Fi」；將特徵點Fi和基準特徵點集Na中的最近鄰特徵點Fi』的對應關係(Fi，Fi』)作為新的匹配關係加入特徵點集Ni和基準特徵點集Na的匹配關係集中；並用特徵點Fi與基準特徵點點集Na中的最近鄰特徵點Fi』及次近鄰特徵點Fi」的描述子矢量歐拉距離的比值閾值過濾超出閾值範圍的匹配關係；步驟23，對步驟22中得到的特徵點集Ni和基準特徵點集Na的匹配關係集中各匹配特徵點對所對應的各坐標對，確定匹配坐標子集和對應的線性映射關係矩陣，匹配坐標指匹配的坐標點所指示的不同圖像上的位置對應物理上同一物體或同一場景上的同一點；步驟24，對所述圖像點集Ni中每一個未匹配到的特徵點Gi，使用所述線性映射矩陣計算其在基準特徵點集Na對應圖像中的匹配坐標點，如果該匹配坐標超出圖像大小，則表示在基準特徵點集Na對應的圖像中找不到特徵點Gi對應的匹配，否則計算匹配坐標的特徵點描述子矢量，形成新的特徵點Gi』；如果所述新的特徵點Gi』的描述子矢量與特徵點Gi的描述子矢量的歐拉距離小於設定的閾值，則將所述新的特徵點Gi』點加入基準特徵點集Na中並將已知的圖像點集Ni中的特徵點Gi和新的特徵點Gi』的對應關係(Gi，Gi』)作為新的匹配關係放入圖像點集Ni和基準特徵點集Na的匹配關係集中，否則特徵點Gi的匹配特徵點在基準特徵點集Na對應的圖像中不存在，捨棄新的特徵點Gi』；步驟25，對每個所述圖像點集Ni中所有未匹配特徵點返回執行步驟24，得到基準特徵點集Na基於特徵點Ni補充後的特徵點集Nai和更新的匹配關係集；步驟26，將所述基準特徵點集Na基於特徵點集N1至特徵點集Ni補充後的特徵點集Na1至特徵點集Nai合併為最終基準特徵點集Na』，並且使相似的特徵點只保留一個在最終基準特徵點集Na』中；相似特徵點通過特徵點的坐標差閾值和描述子矢量的距離小於設定的閾值來判定；將步驟22至步驟25中得到的所述各圖像特徵點集Ni與原基準特徵點集Na的匹配關係集更新為各圖像點集Ni與新的基準特徵點集Na』的匹配關係集；步驟27，對在每個所述圖像點集Ni中未找到匹配點的最終基準特徵點集Na』中的特徵點Mi，返回步驟24求得其在圖像點集Ni對應圖像中的對應坐標和相應的特徵點描述子矢量，生成新的特徵點Mi』；將該特徵點Mi』加入圖像點集Ni並將它和新基準特徵點集Na』中的特徵點Mi的對應關係(Mi』，Mi)保存到圖像點集Ni和基準特徵點集Na』的匹配關係集中；步驟28，基於步驟23至步驟27得到的匹配關係集，找到同一場景的幾幅圖像中對應同一物理點的特徵點，即同類點；如果經過步驟23至步驟27，基準特徵點集Na』中的特徵點ma分別同圖像點集Ni中的特徵點mi匹配，即得到的匹配關係為(m1，ma)，…，(ma-1，ma)，(ma+1，ma)…，則m1，…，ma-1，ma，ma+1，…為同類點，否則m1，…，ma-1，ma，ma+1，…不為同類點；所述步驟4具體包括以下步驟步驟41，計算各個同類點集的描述子矢量的質心向量ci和其包含的點的個數mi；步驟42，對集合(ci，mi)用加權的聚類方法進行聚類，確定各聚類的聚類中心；步驟43，設定質心為向量ci的同類特徵點所屬聚類為質心向量ci所屬聚類；步驟44，對圖像資料庫中的每幅圖像計算其特徵點所屬各聚類的頻數ni；步驟45，計算每個聚類在圖像資料庫中出現的概率對數wi，wi＝ln(N/Ni)，其中N為圖像總數，Ni為當前聚類所出現的圖像的個數；步驟46，對圖像資料庫中每幅圖像，基於特徵點所屬聚類的頻數ni和各聚類的概率對數wi生成一個特徵矢量並單位化；所述檢索部分包括以下步驟步驟6，提取待檢索圖片的特徵點，生成特徵點集；步驟7，計算各個特徵點描述子向量到各個聚類中心的距離，以最小距離確定當前特徵點所屬聚類；步驟8，計算待檢索圖片的特徵點所屬各個聚類的頻數ni；步驟9，基於待檢索圖片的特徵點所屬聚類的頻數ni和所述的各聚類的概率對數wi生成一個特徵矢量並單位化；步驟10，計算待檢索圖片的特徵矢量到圖片庫各圖像特徵矢量的歐拉距離，選取距離最小的圖像輸出為檢索結果。
2.根據權利要求1所述的一種圖像檢索方法，其特徵在於，步驟1中，使用SIFT算法對 圖像進行特徵點的檢測和描述，得到圖像的所有特徵點位置和描述子矢量。
3.根據權利要求1所述的一種圖像檢索方法，其特徵在於，步驟23中利用隨機採樣一 致性算法確定匹配坐標子集和對應的線性映射關係矩陣，包括以下步驟首先隨機地選取 坐標對中選取的四對坐標點，四對坐標在各自圖像中的任三點都不處在同一條直線上；如 果四對坐標點滿足線性映射關係，則求出對應的線性映射矩陣H;再將除上述四對坐標外 的其他匹配坐標對一一代入線性映射關係，確定是否符合當前矩陣的線性映射關係；如果 符合，則標記為正確匹配；否則，標記為錯誤匹配；不斷重新選取四對坐標點，執行上述過 程，求出每個新的線性映射矩陣和對應的匹配關係；選出正確匹配對數目最多的線性映射 矩陣H，並保存該線性映射矩陣對應的匹配關係。
4.根據權利要求1所述的一種圖像檢索方法，其特徵在於，步驟4中，使用加權k-means的聚類方法把同類特徵點集的描述子矢量聚成k類，其具體步驟是步驟42a，在所有的初始同類特徵點集描述子質心矢量Ci的集合中隨機選取一個矢量 作為第一個聚類中心C1;步驟42b，在選取第i個聚類中心Q時，首先在初始質心矢量集合中隨機抽取m個 矢量Xl，X2，…，xm，分別計算各個矢量到已選取聚類中心集合IA，C2，…，Cg}的最 小歐拉距離，再選擇該最小距離中的最大值對應的抽取矢量為新的聚類中心Q ；即 C;= argmaxX) Xm minj=i,...,i-i dist(xk，Cj)，其中Ci為最後確定的第i個聚類中心，Xl，X2，…， xm為當前隨機抽取的m個初始同類特徵點集描述子的質心矢量，(^，(2，為已選取的 聚類中心；minj = i, ..., ^dist (xk, Cj)求取了隨機抽取的質心矢量xk到各已選出的聚類中心 的最小距離，minj = 1, ..ndistO^Cj)選出質心矢量xi，x2，…，xm中到聚類中心CpQ，…， Ch最小距離的最大者；步驟42c，重複步驟42b選取k個聚類中心；步驟42d，計算各初始同類特徵點集描述子質心矢量到聚類中心的歐拉距離，以最小距 離確定當前質心矢量所屬聚類；步驟42e，計算新生成的各聚類的質心矢量，假設當前的第i個聚類是矢量集{(cn， Wn)，(Ci2，Wi2)，…，(CiJ, WiJ)，…}，則其質心計算公式為 ，其中CiJ 是初始同類特徵點集質心矢量，WiJ是對應同類特徵點集所包含特徵點的個數；步驟42f，循環執行步驟42e直到計算出所有聚類的質心矢量C/，再將每個聚類計算 所得的質心矢量C/同對應聚類的中心Q做比較，如果全部k個聚類的比較結果均相等或 聚類過程超過最大迭代次數，則聚類過程結束，否則以計算所得各聚類的質心矢量作為對 應聚類的中心重新執行步驟42d。
全文摘要
本發明公開了一種圖像檢索方法，包括訓練和檢索兩個部分；所述訓練部分包括以下步驟特徵點的提取；特徵點的補充和匹配關係的確定；同類點集的生成；特徵點集聚類；圖像資料庫中每幅圖像特徵矢量的生成；所述檢索部分包括以下步驟提取待檢索圖片的特徵點，生成特徵點集；計算各個特徵點描述子向量到各個聚類中心的距離，以最小距離確定當前特徵點所屬聚類；計算待檢索圖片的特徵點所屬各個聚類的頻數ni；基於待檢索圖片的特徵點所屬聚類的頻數ni和所述的各聚類的概率對數wi生成一個特徵矢量並單位化；計算待檢索圖片的特徵矢量到圖片庫各圖像特徵矢量的歐拉距離，選取距離最小的圖像輸出為檢索結果。
文檔編號G06F17/30GK101859326SQ201010195710
公開日2010年10月13日 申請日期2010年6月9日 優先權日2010年6月9日
發明者汪粼波, 郭延文 申請人:南京大學