一種支持海量人臉圖片快速檢索的索引結構

汪 昀,朱 明,馮偉國

(中國科學技術大學自動化系,合肥230027)

一種支持海量人臉圖片快速檢索的索引結構

汪 昀,朱 明,馮偉國

(中國科學技術大學自動化系,合肥230027)

為了在大規模的人臉數據庫中準確快速地檢索到所需圖像,提出一種相似人臉檢索方法。提取人臉圖片的局部二值模式特征,通過建立投影矩陣將特征從歐幾里德空間映射到漢明空間實現降維,再采用改進的多比特編碼方法對降維后的特征進行編碼,并生成圖片簽名,以曼哈頓距離取代漢明距離衡量簽名之間的相似度,根據圖片簽名集合構建倒排索引表,通過倒排索引表高效地查找相似圖片。包含20萬張人臉圖片的實驗數據集的結果表明,該方法在保證檢索精度的前提下,檢索時間控制在0.15 s以內,能夠滿足海量人臉圖片檢索的準確性與實時性要求。

海量人臉圖片;局部二值模式特征;圖片簽名;多比特編碼;倒排索引;快速檢索

1 概述

隨著互聯網的快速發展和實際應用,人類的生產生活已經邁入信息化的時代?；ヂ摼W應用一方面為人們帶來諸多便利,提供大量資訊,另一方面信息化的社會生活正產生指數級的信息量增長。面對互聯網信息的爆炸式增長,如何有效、快速地尋找有價值的資訊是目前計算機研究的熱點問題。這其中多媒體技術的發展尤為快速,互聯網中圖像的使用不斷在擴大,據統計視覺信息的比重已占到互聯網信息的25%以上。圖像以其所含有的豐富信息量在日常生活中發揮著無法替代的信息媒介作用,而人臉圖片的比重約占所有圖片的60%以上［1］,面向海量的人臉圖片進行快速有效的相似性檢索逐漸成為一個研究熱點。

本文提出一種支持海量人臉圖片快速檢索方法。該方法對高維的特征向量進行降維處理,相似的原始特征向量降維之后得到的編碼仍能夠保持相

似性,通過對降維后的編碼建立倒排索引表以供檢索,滿足檢索的實時性要求。

2 背景介紹

人臉圖片的檢索一般先檢測圖片中的人臉并進行預處理工作,然后對標準化后的人臉圖片提取特征生成特征向量,將相似人臉的檢索問題轉化為特征向量之間的距離匹配問題。由于圖片特征往往是高維向量,計算高維向量之間的距離有著極大的時間復雜度,通常會陷入維度災難之中,因此需要研究一種快速有效的檢索結構避免上述問題。文獻［1］采用人物屬性編碼作為圖片的特征,利用人臉圖片的低層次特征獲取人物的一組屬性編碼,如性別、膚色、年齡等,并用這些屬性構建倒排索引,提高檢索效率。然而,從圖片的特征獲取人物的屬性存在較大的不確定性,特別是性別、年齡等屬性的判斷仍是目前難以解決的問題,屬性標記錯誤直接影響了檢索的準確率。文獻［2］提出了一種基于身份量化的人臉檢索方法,這種方法將人臉關鍵部位分為175個子塊,對每個子塊提取局部特征,之后選取若干個人物的圖片作為標準字典庫,人臉數據庫中每張圖片的每一個子塊用標準字典中最相似的相應子塊所屬的人物ID表示,圖片特征被量化為175個身份ID值,并以身份ID作為索引實現快速檢索,同時利用LE方法提取人臉的全局特征并進行哈希獲得圖片的簽名,根據圖片簽名的漢明距離大小對檢索的結果重新排序。該方法雖然實現了海量人臉圖片的快速檢索,但步驟繁瑣、系統復雜,特別是標準字典庫更新之后需要重新對人臉數據庫的圖片進行身份量化,離線操作工作量龐大。文獻［3］采用改進的kmeans聚類算法對圖片庫的圖片進行聚類,提出了平均面積直方圖和圖像密度的概念,增強不相似圖片之間的區分度,通過圖像密度分布解決聚類初始中心不穩定以及聚類類別數目難以確定的問題,縮小了查詢范圍,提高檢索的速度和精度,不過圖片庫更新后需要重新進行聚類操作,特別是在圖片數據庫龐大的情況下聚類操作時間復雜度更高。文獻［4］提出了擴展的位置敏感哈希(Locality Sensitive Hashing,LSH)算法投影高維的圖片特征向量,該投影空間具有更高的局部敏感性以提高圖片的匹配度和檢索性能。文獻［5］采用了反饋學習的方法,首先建立LSH索引結構對輸入的圖片進行檢索獲得初步結果,之后用戶根據結果標記出檢索正確與檢索錯誤的圖片,通過用戶的反饋信息訓練支持向量機分類器生成符合用戶期望的新的檢索結果。文獻［6］闡述了二值模式特征(Local Binary Pattern,LBP)不能準確反映圖片內容的空間信息的問題,改用局部灰度變化共生矩陣描述了每個像素點周邊4個不同方向上相鄰像素點的灰度變化信息,考慮了空間分布信息,提高了特征描述的準確性。文獻［7］綜合考慮了圖像的顏色、紋理、形狀特征。將它們結合起來作為圖像的整體特征表示,這種從多方面描述圖像的方法更細致地表達了圖像的信息,保證了檢索的高效性。

3 索引結構原理

3.1 索引結構框架

本文提出的海量人臉圖片快速檢索系統分為離線操作和在線操作2個流程。離線操作中,首先提取人臉庫中圖片的二值模式特征(LBP),然后按照投影方法對特征向量進行降維編碼,最后依據整個人臉庫各張圖片編碼特征構建倒排索引;在線操作過程也即圖片檢索過程如下:對輸入的查詢圖片提取LBP特征并降維編碼后通過倒排索引結構獲得最相似的TOP-K張人臉圖片。

3.2 圖片特征表示方法

本文采用LBP［8］描述人臉圖片,LBP特征是一種局部二值模型特征,它是一種用來描述圖像局部紋理特征的算子,具有旋轉不變性和灰度不變性的優點,且計算簡單、紋理判別能力強,已經廣泛用于圖像檢索領域之中。

首先將人臉劃分成若干個小區域,對每個區域統計出LBP直方圖,最后將所有區域的LBP直方圖進行拼接后生成人臉的LBP特征。

LBP直方圖計算方法如下:對于人臉的灰度圖片,選取其中某一像素點為圓心,以r為半徑畫圓,并在圓周上等間隔選取k個像素點,分別計算出圓心處的像素點和圓周上k個像素點的灰度值,將圓周上的k個像素點的灰度值依次與圓心處像素點的灰度值比較,若圓周上的像素點灰度值大于等于圓心處像素點的灰度值,則將圓周上該處標記為1,否則標記為0,如圖1所示。

圖1 LBP算子示意圖

以圓周上的某一像素點為起點,以順時針或逆時針將經過0和1標記后的圓周上的k個像素點的標記值串接在一起,本例中取最上方的點為起點,順時針將這些值串接在一起得到11101010,需要注意的是起點和方向的選取是任意的,但要保證對所有

的人臉圖片的每一個采樣像素點都采取相同的起點和方向。將串接后的值轉換為十進制數值,得到中心像素點處的LBP值。對人臉各個分塊區域中的每一個采樣點做上述處理,得到各個分塊區域的LBP直方圖,將各個區域的LBP直方圖進行拼接之后生成整個人臉圖片的LBP特征。

LBP算法復雜度低,消耗內存小,原理簡單,適用于需要快速提取特征及檢索的場合。

3.3 特征降維編碼

對高維特征向量進行直接檢索通常會面臨維度災難［9］的問題而導致檢索速度過慢,無法滿足檢索的實時性要求,通過將高維特征向量從歐幾里德空間映射到漢明空間中可以有效地實現特征的降維,降低檢索的時間復雜度。為了保證在歐幾里德空間中距離相近的高維向量在投影到漢明空間后仍保持距離的相近,本文借鑒文獻［10］中的映射投影方法對生成的高維圖片特征向量作如下處理:

(1)假設原始圖片特征xi為1×d維(本文實驗中d=1 770),投影后的特征zi為1×dp維且dp?d(本文實驗中dp=64)。隨機生成d×d維的矩陣G,G中的每一個元素取自隨機變量Y,Y服從期望μ= 0,方差σ2=1的高斯分布。

(2)對矩陣G做QR分解,滿足QR=G,QTQ=I且R為上三角矩陣,得到d×d維的Q矩陣。

(3)取Q矩陣的前dp行構成dp×d維投影矩陣P,對原始圖片特征xi進行投影得到降維后的特征zi,其中,zi=xiPT=(zi1,zi2,…,zidp)。

傳統方法對降維后的特征進行量化編碼一般采用如下方法:獲取投影后的特征集合每一維的中值為mj,j∈［1,dp］,按式(1)進行中值量化［11］得到二值編碼的結果為bi=(bi1,bi2,…,bidp),以下稱該結果為圖片的簽名,利用不同圖片簽名之間的漢明距離衡量圖片的相似度,2張圖片簽名的漢明距離越小則說明這2張圖片越相似,反之越不相似。

這種將降維后的特征量化為二值編碼并利用漢明距離衡量相似度的方法存在精度不高的缺點,例如中值為50,極為相近的2個數值49和51被量化成不同的值0和1,而距離較大的2個數值1和99也被量化為0和1,這2組數值經量化后的漢明距離均為1,但原始數值之間的距離卻相差甚遠,這就引入了很大的量化誤差。本文對量化過程做出改進,并采用曼哈頓距離［12］代替漢明距離作為衡量相似度的標準:

(1)確定投影后向量的每一維zij量化結果比特數q,得到2q個可選量化值,q=1時等同于式(1)中的二值量化,q=2時量化可選結果為00,01,10,11,以此類推。

(2)根據選擇的q,將降維后的特征集合的各維按升序排列,平均分為2q等份,得到2q-1個分隔值,用mkj表示第j維的第k個分隔值,k∈［1,2q-1］,j∈［1,dp］。

(3)按式(2)進行量化得到編碼結果為bi= (bi1,bi2,…,bidp),即圖片的簽名。

采用曼哈頓距離代替漢明距離衡量簽名之間的距離,曼哈頓距離定義如下:對每一維為qbit的簽名b1=(b11,b12,…,b1dp)和簽名b2=(b21,b22,…,b2dp),對應維如b11和b21的曼哈頓距離為:

其中,dd(b11)和dd(b21)分別表示b11和b21的十進制值。按此定義,b1和b2這2個簽名的曼哈頓距離為:

2張圖片的曼哈頓距離越小代表這2張圖片越相似,反之越不相似。上述處理避免了量化誤差過大的情況出現,以q=2為例,此時有3個量化分隔值,假設分別為25,50,75,那么數值49和51分別被量化為01和10,數值1和99分別被量化為00和11,這2組數值經量化后的曼哈頓距離分別為1和3,相比采用前述式(1)的量化方法及漢明距離衡量相似度,曼哈頓距離具有更好的區分度,減小了量化誤差,且q越大,量化的結果越精確。當q=1時,式(2)等價于式(1),曼哈頓距離退化為漢明距離。

3.4 索引構建

依次計算查詢圖片和海量庫中各圖片簽名距離的時間復雜度過高,檢索的實時性差,因此,需要一種有效的索引結構實現相似人臉圖片的快速檢索。圖片簽名有dp維,每一維有qbit,故每個圖片簽名bi=(bi1,bi2,…,bidp)可視為由dp個單詞組成,本文以圖片簽名的各單詞構建索引,實現快速檢索。根據簽名的單詞數dp,生成dp個索引表,分別由簽名集合的第1維～第dp維對應的單詞構建,索引表的單詞后排列出包含該單詞的圖片序號,如圖2示意了q=2時的索引表集合。

圖2 q=2時索引表集合示意圖

結合前述曼哈頓距離的概念,這里使用距離閾值T來表示與簽名的某一單詞bij曼哈頓距離不大于T的單詞具有相似性,也可理解為考慮到量化誤差的存在,簽名的單詞bij也可量化［bij–T,bij+T］范圍內的各單詞。此時,對于圖片i的簽名bi= (bi1,bi2,…,bidp),將圖片的序號i分別插入第1個索引表的［bi1–T,bi1+T］范圍內的各個單詞后、第2個索引表的［bi2–T,bi2+T］范圍內的各個單詞后,以此類推,直到插入第dp個索引表的［bidp–T,bidp+T］范圍內的各個單詞后。對圖片庫所有圖片簽名做相同的插入操作之后便完成了索引構建。采用本文的索引構建方法的優點在于:當圖片庫更新之后,只需將更新的圖片簽名插入索引表或從索引表中刪除即可完成索引表更新操作,簡單快速。

3.5 查詢方法

對查詢圖片i的簽名bi=(bi1,bi2,…,bidp),分別于索引表1,2,…,dp中查找單詞bi1,bi2,…,bidp,獲取圖片序號的集合,統計集合中各個圖片序號的出現次數,設序號為j的圖片在集合中出現了y次,則圖片i和j的相似度由式(5)確定:

按降序排列圖片i和庫中各圖片的相似度值,輸出最相似的Top-K張圖片。實驗表明,該索引結構能夠迅速返回查找結果,滿足檢索對實時性的要求。

4 實驗結果與分析

為了驗證本文提出方法的有效性,以YouTube Faces人臉數據庫作為數據源,該數據庫的人臉圖片提取自YouTube視頻網站上的1 595個不同人物的3 425個視頻之中,選取其中的200 000張人臉圖片進行實驗,實驗硬件環境為Intel Core i3-2120 3.30 GHz CPU,4 GB內存。測試時隨機從庫中選取1 000張圖片作為查詢圖片,分別對T=0,q取不同值的情況下,圖片庫大小為50 000,100 000, 150 000,200 000張時的檢索時間做了測試,求出平均的檢索時間,實驗結果如圖3所示。

圖3 不同q及人臉庫規模下的平均檢索時間

實驗結果表明,采用本文的索引結構,在20萬張圖片庫中檢索一次的最大時間不超過0.3 s,且q越大,檢索速度越快,q=4時的檢索時間僅為0.027 s,即在本文的索引結構之上采用多比特量化的方法可以有效地提升檢索速度。當q增大時,索引單詞項增多,使得其后的圖片編號數量減少,從而減少了在索引表中進行一次查詢所得的圖片編號數,降低了統計次數,提高了檢索速度。但是由于人臉圖片受光照、角度、姿態等影響,相同的人在這些不同環境下的圖片提取出的原始特征本身會存在差異,導致編碼后的特征也存在差異。此時,若選取T=0,會造成相似判斷條件過為苛刻,準確率會有所下降。通過提高T的值,彌補準確率降低的缺點,雖然一定程度上增加了索引單詞后的圖片編號數造成檢索時間稍有增加,但仍快于q=1,T=0時的傳統漢明距離檢索方法。實驗統計如下:在圖片庫為200 000張的情形下,隨機選取1 000張圖片作為查詢圖片,分別對q=4,T取不同值的情況做檢索,對前10張檢索結果的平均準確率及檢索時間做出統計并與q=1,T=0時的平均準確率和檢索時間做出對比,如表1所示。

表1 準確率和檢索時間對比

從表1可以看出,增大T值有效地提高了準確率,q=4,T=2時的準確率已經高于q=1,T=0時的準確率,且檢索時間僅為其一半。綜合圖3和表1的實驗結果,可見本文提出的采用改進的多比特編碼方法并利用曼哈頓距離衡量圖片相似度的索引結構可以在保證精度的前提下實現快速檢索。

下面考慮該索引結構的內存消耗:存儲代價主要來源于將索引讀入內存,索引表主要存放索引的單詞和圖片編號,由于圖片編號數量遠大于索引單詞條目,因此索引單詞條目占用的內存可以忽略不計,也即在一定范圍內增大q并不會帶來內存的增

加,消耗內存的大小應與圖片數量、T的取值以及索引表數目有關。圖片編號若以整形保存,索引表的個數為dp,對于T=0,dp=64時的200 000張圖片構建的索引表共消耗內存200 000×4 Byte×64= 48.8 MB,而T=2時最多消耗內存48.8 MB×5= 244 MB,很容易進行分布式擴展,支持百萬數量級圖片的檢索。

最后將本文的索引結構(q=4,T=2)與文獻［3］中提出的索引結構進行比較,文獻［3］中的聚類索引結構對圖片庫規模為4 000時的檢索時間約為0.09 s,本文對圖片庫規模為200 000張時的檢索時間為0.143 s,圖片庫規模為文獻［3］的20倍而檢索時間僅為其1.5倍,并且本文的索引結構可以針對不同需求的情形調節參數,靈活性更強,圖片庫更新后僅需針對變動的圖片對索引表進行插入或刪除操作,簡單快捷。

綜上,本文提出的索引結構在保證準確率的前提下,加快了檢索速度,并具有良好的擴展性和靈活性,因此,針對大規模人臉數據庫,本文方法有效地實現了海量人臉快速檢索。

5 結束語

隨著互聯網海量人臉圖片的出現,快速有效的人臉圖片檢索方法變得越來越重要。本文提出一種支持海量人臉圖片快速檢索的索引結構,首先將人臉圖片數字化表示為LBP特征,之后對特征進行投影并降維,采用多比特的編碼方法生成圖片簽名,通過簽名的曼哈頓距離判別圖片的相似度,以簽名中的單詞構建索引,實現快速檢索。在海量人臉數據庫上進行的實驗結果表明,對于規模為200 000張圖片的人臉數據庫,在保證檢索精度的前提下,檢索一次的時間僅需0.143 s,并且具有著良好擴展性,通過調節參數可以適應不同規模數據庫下的檢索,靈活性強。下一步工作將研究不同光照、姿態、表情下人臉特征的準確表示方法,克服環境變化對相同人物的人臉圖片造成的特征提取誤差,以求從數據源頭提高特征提取的準確性,進一步提高檢索的準確率。

［1]Chen Bor-Chun,Chen Yan-Ying,Kuo Yin-Hsi,et al.Scalable Face Image Retrieval Using Attribute-enhanced SparseCodewords［J］.IEEETransactionson Multimedia,2013,15(5):1163-1173.

［2]Wu Zhong,Ke Qifa,Sun Jian,et al.Scalable Face Image RetrievalwithIdentity-basedQuantizationand Multireference Reranking［J］.IEEE Transactions on PatternAnalysisandMachineIntelligence,2011, 33(10):1991-2001.

［3]史習云,薛安榮,劉艷紅.改進k-means聚類算法在圖像檢索中的應用研究［J］.計算機工程與應用,2011, 47(10):193-196.

［4]何周燦,王 慶,楊 恒.一種面向快速圖像匹配的擴展LSH算法［J］.四川大學學報:自然科學版,2010, 47(2):269-274.

［5]Dong Tingting,Zhao Zhicheng.A NovelInteractive Image Retrieval Method Based on LSH and SVM［C］// Proceedings of the 3rd International Conference on Network Infrastructure and Digital Content.Washington D.C.,USA:IEEE Press,2012:482-486.

［6]Farag A A,Yang Jian,Jiao Feng.A New Texture Direction Feature Descriptor and Its Application in Content-based Image Retrieval［C］//Proceedings of the 3rd International Conference on Multimedia Technology.Berlin,Germany:Springer,2014:143-151.

［7]Lande M V,Bhanodiya P,Jain P.An Effective Contentbased Image Retrieval Using Color,Texture and Shape Feature［C］//Proceedings of Conference on Intelligent Computing,Networking,andInformatics.Berlin, Germany:Springer,2014:1163-1170.

［8]Ahonen T,Hadid A,Pietik?inen M.Face Recognition with Local Binary Patterns［C］//Proceedings of IEEE Workshop on Applications of Computer Vision.Berlin, Germany:Springer,2004:469-481.

［9]Hinneburg A,KeimDA.OptimalGrid-clustering: Towards Breaking the Curse of Dimensionality in Highdimensional Clustering［C］//Proceedings of the 25th Conference on Very Large Databases.Berlin,Germany: Springer,1999:506-517.

［10]Jegou H,Douze M,Schmid C.Hamming Embedding and Weak Geometric Consistency forLarge Scale Image Search［C］//Proceedings of the 10th European Conference on Computer Vision.Marseille,France:［s.n.］,2008: 304-317.

［11]Naturel X,GrosP.DetectingRepeatsforVideo Structuring［J］.Multimedia Tools Applications,2008, 38(2):233-252.

［12]Kong Weihao,Li Wjun,Guo Minyi.Manhattan Hashing for Large-scale Image Retrieval［C］//Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval.［S.l.］: ACM Press,2012:45-54.

編輯 顧逸斐

An Index Structure of Fast Retrieval for Massive Face Image

WANG Yun,ZHU Ming,FENG Weiguo
(Department of Automation,University of Science and Technology of China,Hefei 230027,China)

In order to quickly and correctly retrieve the desired image from massive face image database,this paper proposes an efficient fast method for similar face image retrieval.It extracts Local Binary Pattern(LBP)features of face images and does dimensionality reduction by mapping the features from Euclidean space into Hamming space.A signature for each image is constructed by encoding dimensionality reduced features,using enhanced multi-bit encoding method.The similarity between each signature is judged by Manhattan distance instead of Hamming distance.It constructs inverted indexes from image signatures and fast retrieval is accomplished by using efficient inverted indexes.Experimental results on dataset containing 200 000 face images show that the retrieval time is less than 0.15 s,which satisfies the retrieval precision as well as the accuracy and real-time of large-scale face image retrieval.

massive;Local Binary Pattern(LBP)feature;image signature;multi-bit encoding;inverted index; fast retrieval

汪 昀,朱 明,馮偉國.一種支持海量人臉圖片快速檢索的索引結構［J］.計算機工程,2015, 41(3):186-190.

英文引用格式:Wang Yun,Zhu Ming,Feng Weiguo.An Index Structure of Fast Retrieval for Massive Face Image［J］.Computer Engineering,2015,41(3):186-190.

1000-3428(2015)03-0186-05

:A

:TP391.41

10.3969/j.issn.1000-3428.2015.03.036

中國科學院先導專項課題基金資助項目“網絡視頻傳播與控制”(XDA06030900)。

汪 昀(1988-),男,碩士研究生,主研方向:多媒體檢索;朱 明,教授、博士;馮偉國,博士研究生。

2014-03-14

:2014-04-17E-mail:shinichi@mail.ustc.edu.cn