改進視覺詞袋模型的快速圖像檢索方法①

張禎偉, 石朝俠

(南京理工大學 計算機科學與工程學院, 南京 210094)

改進視覺詞袋模型的快速圖像檢索方法①

張禎偉, 石朝俠

(南京理工大學 計算機科學與工程學院, 南京 210094)

視覺詞袋模型在基于內容的圖像檢索中已經得到了廣泛應用, 傳統的視覺詞袋模型一般采用SIFT描述子進行特征提取. 針對SIFT描述子的高復雜度、特征提取時間較長的缺點, 本文提出采用更加快速的二進制特征描述子ORB來對圖像進行特征提取, 建立視覺詞典, 用向量間的距離來比較圖像的相似性, 從而實現圖像的快速檢索. 實驗結果表明, 本文提出的方法在保持較高魯棒性的同時, 明顯高了圖像檢索的效率.

視覺詞袋模型; 局部特征; ORB; 圖像檢索

圖像檢索技術是機器視覺領域中關注對大規模數字圖像進行檢索和匹配的研究分支. 它是圖像拼接、目標跟蹤、運動分析、對象識別、視覺導航等研究方向的研究基礎. 近些年伴隨著嵌入式系統處理能力及存儲容量的 快速提升, 智能終端、機器人等嵌入式系統對大數據量圖像檢索需求日益增加, 從海量數據中快速檢索和匹配到所需的信息已具有很大的研究價值.

在基于內容的圖像檢索中, 視覺詞袋模型(Bag of Visual Word, BoVW)[1]已經成為一種比較常見的方法.詞袋模型(Bag of Words, BoW)最初應用于文檔處理領域, 將文檔表示成順序無關的關鍵詞的組合, 通過統計文檔中關鍵詞出現的頻率來進行匹配. 作為一種源自文本檢索的模型, 視覺詞袋模型近年來在計算機視覺研究領域表現出良好的適用性, 成為計算機視覺研究的通用模型. BoVW首先在視頻檢索的研究中被系統地闡述與應用, 近幾年來, 計算機視覺領域的研究者們成功地將該模型的思想移植到圖像處理領域, 通過對圖像進行特征提取和描述, 得到大量特征進行處理, 從而得到用來表示圖像的關鍵詞, 并在此基礎上構建視覺詞典進而圖像可以類似于文本的表示方法即統計基本詞匯出現的頻數, 將圖像表示成一個向量,利用該向量進行圖像的檢索. 傳統的詞袋模型一般采用SIFT(Scale-Invariant Feature Transform)特征描述子[2], SIFT算法可以適應圖像縮放、旋轉、平移等變化, 并且能克服噪聲光照變化的影響. 但是SIFT算法的計算量比較大, 無法滿足系統實時性的要求. 針對SIFT描述子的高復雜度問題本文提出了采用更加快速的二進制特征描述子ORB[3]來對圖像進行特征抽取, 然后利用BoVW模型進行建模, 將每一副圖像用一個二進制串來表示, 進行圖像的檢索. 實驗表明, 該方法不僅保持了較高的圖像檢索準確率, 而且大大提高了圖像的檢索速度.

1 視覺詞袋模型

BOW算法起源于基于語義的文本檢索算法, 是一種有效的基于語義特征提取和描述的識別算法. 該算法忽略文本的結構信息和語法信息, 僅僅將其看做是若干個詞匯的集合, 文本內的每個詞的出現都是獨立的, 提取其中的語義特征, 構建單詞詞匯表, 根據每個文本與詞匯表的關系, 統計文本中相應單詞的出現頻率, 形成一個詞典維度大小的單詞直方圖, 經過這樣文本到向量運算問題的轉化, 最后實現文本檢索.將對文本處理的詞袋模型過渡到圖像處理領域, 便形成了視覺詞袋模型.

1.1 算法流程

其實現過程大致分為四個步驟: 首先提取圖像中的特征描述子; 然后通過聚類算法將訓練圖片得到特征描述子進行相似點聚類, 每個聚類中心代表一個視覺單詞; 將圖像的局部視覺特征映射到視覺單詞表并用一個特征向量表示, 特征向量的每一維對應一個視覺單詞的權重之和. 最后利用圖像生成的向量進行圖像檢索. 算法流程如圖1所示.

圖1 視覺詞袋模型流程

根據圖1, 應用詞袋模型進行圖像檢索的具體實現過程可以描述如下:

(1) 特征提取和描述.

視覺詞袋模型往往選取圖像底層的SIFT特征, 該特征具有旋轉、尺度、平移等不變性, 同時對仿射變換, 噪聲存在一定的穩定性. SIFT特征計算主要分為圖像特征點的選取和圖像特征區域的描述兩個部分.圖像特征點的選取步驟如下: 首先對圖像建立一個圖像金字塔模型, 然后對圖像在相鄰尺度空間上做差分,選取尺度空間中的極值點, 最后將極值點周圍的一定范圍的區域作為特征區域.

(2) 視覺詞典構造.

BOW算法通常采用k-means算法對提取的特征進行聚類生成視覺詞典. k-means算法是一種經典的聚類算法, 是典型的基于原型的目標函數聚類方法的代表, 它是數據點到原型的某種距離作為優化的目標函數, 利用函數求極值的方法得到迭代運算的調整規則.

視覺詞典構造主要步驟如下:

① 給定待聚類的圖像SIFT描述子數據集,隨機選取K 個對象作為初始聚類中心.

② 求出SIFT描述子數據集中的每個數據與各個聚類中心的距離, 按照最小化原則將數據點劃入最近鄰聚類中心所在的類簇.

③ 重新計算每個類簇的中心.

④ 重復步驟2、3, 當各個聚類中心不再改變時算法結束.

(3) 生成視覺直方圖

該過程是將每幅圖像所有的SIFT特征描述子分配到視覺詞典的各個維度上, 生成各自的視覺單詞直方圖. 在分配的過程中, 采用最近鄰算法, 每幅圖像中的每個SIFT特征向量與哪一個視覺詞距離最近,就將該視覺詞對應的維度高度加1, 直到將所有的SIFT描述子向量分配完為止, 經過這一系列處理后,每一幅圖像都能用一個k維的視覺詞直方圖表示, 將所有圖像的視覺詞直方圖歸一化處理后就可以進行下一步的.

1.2 權值的計算

在文本信息檢索中, TF-IDF[4]是一種常用的加權方案. TF-IDF的主要思想是: 如果某個詞或短語在一篇文章中出現的頻率TF高, 并且在其他文章中很少出現, 則認為此詞或者短語具有很好的類別區分能力,適合用來分類. TF表示詞條在文檔d中出現的頻率,如果一個詞條在一個類的文檔中頻繁出現, 則說明該詞條能夠很好代表這個類的文本的特征, 這樣的詞條應該給它們賦予較高的權重, 并選來作為該類文本的特征詞以區別與其它類文檔.

IDF的主要思想是: 如果包含單詞Fi的文檔越少,也就是ni越小, IDF越大, 則說明單詞Fi具有很好的類別區分能力. 假設訓練集中的圖片總數為N,ni表示包含單詞Fi的圖片數目. 類似于文本檢索當中的逆文檔頻率idf, 定義為:

即該單詞被賦予的權值, 它表明了該單詞對于區分不同圖像時作用的大小.

2 基于ORB特征的視覺詞袋模型

視覺詞袋模型通常選取圖像底層的SIFT特征, 該特征具有旋轉、尺度、平移等不變性, 同時對仿射變換, 噪聲存在一定的穩定性. 為了進一步提高算法實時性, 本文采用ORB算法進行特征提取. ORB算子基于BRIEF算子提出, 是對BRIEF算子的改進. 文獻[3]指出, ORB算法的速度比SIFT 要快兩個數量級, 同時在不考慮圖像尺度變化的情況下, 其匹配性能并不遜色于SIFT.

2.1 圖像特征提取和描述

構建視覺詞匯表之前, 首先要從圖像中提取出具有代表性的全局特征或局部特征, 作為對該圖像的“描述”. 這些被提取的特征應該具有較強的穩定性,能夠抵抗光照、視角尺度等因素帶來的不利影響. BOW通常采用局部特征來生成視覺詞匯表的候選特征, 在圖像識別和物體匹配的過程中, 由于ORB描述子計算速度上的優勢, 本文采用ORB描述子來提取和描述圖像的特征點.

2.1.1 特征點提取

ORB(oriented FAST and rotated BRIEF) 是基于FAST[5]特征檢測和BRIEF描述子[6]改良的. 該算法使用FAST角點檢測來提取特征點, FAST算法的角點定義為在像素點周圍鄰域內有足夠多的像素點與該點處于不同的區域, 在灰度圖像中, 即為有足夠多的像素點的灰度值與該點灰度值差別夠大. 以候選特征D為中心, 比較中心點D的灰度值與以D點為中心的圓周上所有點灰度值之間的大小, 如果圓周上與D點灰度值相差足夠大的點個數超過一定數值, 則認為候選點D為特征點. FAST角點檢測僅僅比較灰度值大小, 具有計算簡單、速度較快的優點, 但其檢測出的特征點既不具備尺度不變性也不具備旋轉不變性.

FAST不提供角點的度量, 對邊緣的響應較大, 因此ORB采用Harris角點度量的方法按照FAST特征點的Harris角點響應值對FAST特征點進行排序. 如需要提取N個特征點, 首先將閾值設置的足夠大以得到更多的特征點, 然后根據Harris響應值排序, 最后選出響應值最大的N個特征點.

由于FAST 特征點是不帶有方向性的, ORB的論文中提出了一種利用灰度質心法來解決這個問題, 灰度質心法假設角點的灰度與質心之間存在一個偏移,這個向量可以用于表示一個方向. 對于任意一個特征點O來說, 我們定義O的鄰域像素的矩為:

其中I(x,y)為點(x,y)處的灰度值. 那么我們可以得到圖像的質心為:

為了提高方法的旋轉不變性, 需要確保x和y在半徑為r的圓形區域內, 即x,y∈[-r,r], r等于鄰域半徑.

2.1.2 特征點描述

ORB中使用BRIEF描述子對檢測到的特征點進行描述, 并解決了BRIEF本身不具有旋轉不變性的首要缺陷. 在以關鍵點為中心的圖像塊內比較采樣點對的灰度值, 得到一個n 位二進制數, 該n 位二進制數即為關鍵點的特征描述子, n的典型值為256.

ORB采用的是BRIEF描述子, 它的基本思想是是圖像特征點鄰域可以用相對少量的灰度對比來表達,每個圖像塊由一系列二進制測試構成的位串來表示,其計算簡單、快速. 考慮一個平滑的圖像塊p, 一個二進制測試τ定義為:

其中p(x)是圖像塊p在點x處的灰度值. 特征點被定義為一個由n個二進制測試構成的向量:

BRIEF中圖像鄰域的準則僅考慮單個像素, 所以對噪聲敏感. 為了解決這個缺陷, ORB中每個測試點采用的是31×31像素鄰域中的5×5子窗口, 其中子窗口的選擇服從高斯分布, 再采用積分圖像加速計算.

ORB選擇了BRIEF作為特征描述方法, 但是BRIEF是沒有旋轉不變性的, 所以需要給BRIEF加上旋轉不變性, 把這種方法稱為“Steered BREIF”. 對于任何一個特征點來說, 它的BRIEF描述子是一個長度為n的二值碼串, 這個二值串是由特征點周圍n個點對(2n個點)生成的, 將這n個點對(xi,yi)組成一個矩陣S

使用鄰域方向θ和對應的旋轉矩陣Rθ, 構建S的一個校正版本Sθ

其中

此時Steered BRIEF描述子變為:

ORB根據式(8)中求得的方向參數提取BRIEF描述子. 但是由于環境的因素和噪聲的引入, 特征點方向會發生變化, 隨機像素塊對的相關性會比較大, 從而降低描述子的判別性. ORB采取貪心算法尋找相關性較低的隨機像素塊對, 一般選取256個相關性最低像素塊對, 構成一個256bit的特征描述子.

由于生成的特征點描述子為二進制碼串形式, 因此使用Hamming距離對特征點匹配較為簡單. 計算機中計算漢明距離可以簡單地通過異或進行計算. 漢明距離計算效率非常高.

假設上節得到ORB特征256bit二進制描述子K1、K2兩個特征點的描述子分別為:

通過漢明距離之間的異或之和表征兩個ORB 特征描述子的相似程度, 用D(K1,K2)表示:D(K1,K2)越小代表相似程度越高, 反之相似程度低.

2.2 生成視覺單詞

在提取到圖像的ORB描述子之后, 需要進行視覺詞典的構建. 該過程通常分為兩步來完成. 首先將代表圖像局部特征的描述子轉換為視覺詞, 一個視覺單詞可以看作圖像中相似的特征點的集中代表, 該過程是通過聚類算法實現的. 最終得到的聚類中心就是我們所期望的視覺單詞, 聚類中心的個數就是視覺詞典的大小. 根據聚類的視覺單詞來建立每張圖像的視覺詞直方圖, 該過程稱為映射.

視覺詞袋模型中單詞數目的選取出現在特征描述的量化過程中, 常見的量化方法是k-means聚類, 詞匯數目即對應的聚類數目. 但是由于ORB描述子產生的是二進制描述向量, 無法直接采用傳統的基于歐氏距離的k-means方法進行聚類, 因此, 本文采用Hamming距離計算各個特征之間的距離, 使用k-majority算法[7]來求二進制描述向量的聚類中心. 具體算法流程如下:

假設從圖像中提取到的ORB特征描述子集合D.

步驟1. 隨機生成k個二進制聚類中心記為集合C.

步驟2. 計算D中各描述子到各個聚類中心的距離, 并劃分到個類中.

步驟3. 重新計算各類的聚類中心.

重復步驟2、3, 當各個聚類中心不再改變時算法結束.

其中步驟3中聚類中心的計算方法如下:

假設某一具有n個特征描述子的集合D

其聚類中心為c=c1c2LcjLc256, 其中

即對于集合中所有特征描述子的每一個bit, 統計所有特征的對應bit上的0、1的數量, 并取高者作為該bit的值. 這樣得到的聚類中心向量也是二進制表示,在進行距離計算時可以利用漢明距離進行快速計算.

通過聚類最終得到的k個聚類中心即為所求的視覺單詞. 圖像特征聚類過程如圖2所示.

圖2 圖像特征聚類

2.3 圖片的向量表示

對于訓練集中每一個圖像, 累計圖片中的特征在單詞表中的每一個單詞Fi(1≤i≤t)當中出現的頻率mi, t為視覺單詞總數. 由于在訓練階段已得到該單詞的權值, 即, 同樣根據TF-IDF的原理, 計算出該圖像在單詞Fi維度上的值:

最終, 每一副圖像dj都可以用關于單詞的權值向量表示:

2.4 圖片間的相似度測量

訓練集中圖像dj=(w1,j,w2,j,L ,wt,j), 待查詢圖像也轉換為向量q=(w1,w2,L,wt)表示.

定義訓練圖像與查詢圖像之間的差異程度為:

這里采用的是2-范數. 比較查詢圖像與訓練圖像之間的差異程度S(di,q),(1≤i≤N), 選取差異程度最小的前n個作為查詢結果返回.

3 實驗結果與分析

為了驗證本文提出的方法的圖像檢索效果, 我們選取標準Corel庫中1000張圖片和Caltech101庫中部分圖片共2400多張圖片作為圖像檢索庫, 圖像大小為384×256像素, 部分樣圖如圖3所示.

圖3 部分訓練集圖像

待檢索圖像直接從圖像庫中選取, 隨機從圖像數據庫中選取不同類別的圖像, 每次在查詢結果中將按相似度排序后前10幅圖像作為檢索結果. 檢索結果示例如圖4所示, 每行為一次檢索結果, 每行10幅圖像均為檢索結果, 由于待檢索圖像直接從圖像庫中選取,且檢索結果按相似度排序, 所以檢索結果中的第一幅圖像就是原待檢索圖像本身, 從左到右按圖片與待檢索圖像的相似度由高到低排序.

圖4 圖像檢索結果示例

首先對單個圖像分別進行SIFT特征跟ORB特征提取, 每種特征分別提取300和500個特征點, 由表可以看出, 在特征提取速度方面ORB算法的速度是明顯比SIFT快得多.

表1 特征提取時間對比

為了驗證本文算法的檢索效果, 實驗以查準率作為評價標準, 即檢索結果中用戶滿意的圖像數目與檢索結果返回中所有圖像數目之比. 同時為了準確衡量本文算法的檢索效率, 分別使用不同數量的視覺單詞進行圖像檢索實驗, 最后計算平均查準率并計算平均檢索時間. 實驗結果數據如表2所示. 當視覺單詞數量取值為400時, 按類圖像平均查準率如表3所示.

表2 圖像檢索實驗結果

表3 按類別檢索結果統計

由表2可以看出, 隨著視覺單詞數量的增加, 平均查準率越來越高, 但是平均檢索時間也呈線性增長趨勢. 結合表1中的實驗結果數據可以看出, 僅僅是SIFT的特性提取階段的耗時已相當于本文方法的平均檢索時間. 雖然圖像檢索的查準率偏低, 但是檢索時間快, 能夠滿足系統實時性的要求.

4 結語

本文提出了一種使用ORB特征的視覺詞袋模型的快速圖像檢索的方法, 利用ORB特征替代SIFT對圖像提取局部特征后進行聚類, 生成得到一個視覺單詞“字典”, 然后對于每幅圖像, 統計圖像特征中各個視覺詞匯出現的頻數, 得到一個圖像的描述向量, 并對向量進行歸一化處理, 用該一維向量來表示圖像,其維數為視覺單詞的數目. 進行圖像檢索時, 對待檢索圖像ORB特征, 經過視覺詞袋的映射之后, 待檢索圖像也會用一個向量來表示, 通過計算該向量與圖像庫中的圖像向量的歐式距離, 求取距離最小的圖像,即是與查詢圖像最相似的結果.

實驗結果表明, 本文提出的方法在保持了傳統視覺詞袋模型算法的魯棒性的同時, 由于采用了更加快速的二進制特征ORB, 因此很大程度地縮短了圖像檢索時間, 提高了圖像檢索效率. 本文只是將ORB特征應用到視覺詞袋模型中, 沒有考慮圖像的顏色特征,在未來的工作中可以與圖像的顏色特征相結合, 進一步提高圖像檢索的準確率.

1 Sivic J. Video Google: A text retrieval approach to object matching in videos. Proc. of the International Conf. on Computer Vision. Nice, France. IEEE Press. 2003.

2 Lowe D. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 2004: 91–110.

3 Rublee E, Rabaud V, Konolige K, et al. ORB: An efficient alternative to SIFT or SURF. IEEE International Conference on Computer Vision(ICCV), 2011. IEEE. 2011. 2564–2571.

4 David L. Naive(Bayes) at forty: The independence assumption in information retrieval. European Conference on Machine Learning, 1998: 4–15.

5 Rosten E, Drummond T. Machine learning for high-speed corner detection. Computer Vision-ECCV 2006. Springer Berlin Heidelberg, 2006. 430–443.

6 Calonder M, Lepetit V, Strecha C, et al. Brief: Binary robust independent elementary features. Computer Vision-ECCV 2010, 2010: 778–792.

7 Grana C, Borghesani D, Manfredi M, et al. A fast approach for integrating ORB descriptors in the bag of words model. IS&T/SPIE Electronic Imaging. International Society for Optics and Photonics, 2013: 866709–866709-8.

8 Mansoori NS, Nejati M, Razzaghi P, et al. Bag of visual words approach for image retrieval using color information. 2013 21st Iranian Conference on Electrical Engineering (ICEE). IEEE. 2013. 1–6.

9 黃超,劉利強,周衛東.改進的二進制特征圖像檢索算法.計算機工程與應用,2015,14:23–27.

10 霍華,趙剛.基于改進視覺詞袋模型的圖像標注方法.計算機工程,2012,22:276–278,282.

11 Mansoori NS, Nejati M, Razzaghi P, et al. Bag of visual words approach for image retrieval using color information. 2013 21st Iranian Conference on Electrical Engineering (ICEE). IEEE. 2013. 1–6.

12 董坤,王倪傳.基于視覺詞袋模型的人耳識別.計算機系統應用,2014,23(12):176–181.

13 Zhu L, Jin H, Zheng R, et al. Weighting scheme for image retrieval based on bag-of-visual-words. Image Processing, IET, 2014, 8(9): 509–518.

Fast Image Retrieval Method Using Improved Bag of Visual Words Model

ZHANG Zhen-Wei, SHI Chao-Xia
(School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China)

Bag of visual words model based on content-based image retrieval has been widely used, traditional bag of visual words model generally uses the SIFT descriptors for feature extraction. In view of the high complexity of SIFT descriptors and the long time of feature extraction, this paper proposes to use a faster binary feature descriptor ORB for the image feature extraction, creating visual dictionary, using the distance between two vectors to compare the image similarity, so as to achieve fast image retrieval. Experimental results show that the method proposed in this paper can improve the efficiency of image retrieval obviously, while maintains a relatively high robustness.

bag of visual words; local features; ORB; image retrieval

國家自然科學基金(61371040)

2016-03-14;收到修改稿時間:2016-04-14

10.15888/j.cnki.csa.005464