一種支持海量人臉圖片快速檢索的索引結(jié)構(gòu)

汪 昀,朱 明,馮偉國(guó)

(中國(guó)科學(xué)技術(shù)大學(xué)自動(dòng)化系,合肥230027)

一種支持海量人臉圖片快速檢索的索引結(jié)構(gòu)

汪 昀,朱 明,馮偉國(guó)

(中國(guó)科學(xué)技術(shù)大學(xué)自動(dòng)化系,合肥230027)

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

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

1 概述

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

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

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

2 背景介紹

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

3 索引結(jié)構(gòu)原理

3.1 索引結(jié)構(gòu)框架

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

3.2 圖片特征表示方法

本文采用LBP［8］描述人臉圖片,LBP特征是一種局部二值模型特征,它是一種用來描述圖像局部紋理特征的算子,具有旋轉(zhuǎn)不變性和灰度不變性的優(yōu)點(diǎn),且計(jì)算簡(jiǎn)單、紋理判別能力強(qiáng),已經(jīng)廣泛用于圖像檢索領(lǐng)域之中。

首先將人臉劃分成若干個(gè)小區(qū)域,對(duì)每個(gè)區(qū)域統(tǒng)計(jì)出LBP直方圖,最后將所有區(qū)域的LBP直方圖進(jìn)行拼接后生成人臉的LBP特征。

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

圖1 LBP算子示意圖

以圓周上的某一像素點(diǎn)為起點(diǎn),以順時(shí)針或逆時(shí)針將經(jīng)過0和1標(biāo)記后的圓周上的k個(gè)像素點(diǎn)的標(biāo)記值串接在一起,本例中取最上方的點(diǎn)為起點(diǎn),順時(shí)針將這些值串接在一起得到11101010,需要注意的是起點(diǎn)和方向的選取是任意的,但要保證對(duì)所有

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

LBP算法復(fù)雜度低,消耗內(nèi)存小,原理簡(jiǎn)單,適用于需要快速提取特征及檢索的場(chǎng)合。

3.3 特征降維編碼

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

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

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

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

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

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

(1)確定投影后向量的每一維zij量化結(jié)果比特?cái)?shù)q,得到2q個(gè)可選量化值,q=1時(shí)等同于式(1)中的二值量化,q=2時(shí)量化可選結(jié)果為00,01,10,11,以此類推。

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

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

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

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

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

3.4 索引構(gòu)建

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

圖2 q=2時(shí)索引表集合示意圖

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

3.5 查詢方法

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

按降序排列圖片i和庫中各圖片的相似度值,輸出最相似的Top-K張圖片。實(shí)驗(yàn)表明,該索引結(jié)構(gòu)能夠迅速返回查找結(jié)果,滿足檢索對(duì)實(shí)時(shí)性的要求。

4 實(shí)驗(yàn)結(jié)果與分析

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

圖3 不同q及人臉庫規(guī)模下的平均檢索時(shí)間

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

表1 準(zhǔn)確率和檢索時(shí)間對(duì)比

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

下面考慮該索引結(jié)構(gòu)的內(nèi)存消耗:存儲(chǔ)代價(jià)主要來源于將索引讀入內(nèi)存,索引表主要存放索引的單詞和圖片編號(hào),由于圖片編號(hào)數(shù)量遠(yuǎn)大于索引單詞條目,因此索引單詞條目占用的內(nèi)存可以忽略不計(jì),也即在一定范圍內(nèi)增大q并不會(huì)帶來內(nèi)存的增

加,消耗內(nèi)存的大小應(yīng)與圖片數(shù)量、T的取值以及索引表數(shù)目有關(guān)。圖片編號(hào)若以整形保存,索引表的個(gè)數(shù)為dp,對(duì)于T=0,dp=64時(shí)的200 000張圖片構(gòu)建的索引表共消耗內(nèi)存200 000×4 Byte×64= 48.8 MB,而T=2時(shí)最多消耗內(nèi)存48.8 MB×5= 244 MB,很容易進(jìn)行分布式擴(kuò)展,支持百萬數(shù)量級(jí)圖片的檢索。

最后將本文的索引結(jié)構(gòu)(q=4,T=2)與文獻(xiàn)［3］中提出的索引結(jié)構(gòu)進(jìn)行比較,文獻(xiàn)［3］中的聚類索引結(jié)構(gòu)對(duì)圖片庫規(guī)模為4 000時(shí)的檢索時(shí)間約為0.09 s,本文對(duì)圖片庫規(guī)模為200 000張時(shí)的檢索時(shí)間為0.143 s,圖片庫規(guī)模為文獻(xiàn)［3］的20倍而檢索時(shí)間僅為其1.5倍,并且本文的索引結(jié)構(gòu)可以針對(duì)不同需求的情形調(diào)節(jié)參數(shù),靈活性更強(qiáng),圖片庫更新后僅需針對(duì)變動(dòng)的圖片對(duì)索引表進(jìn)行插入或刪除操作,簡(jiǎn)單快捷。

綜上,本文提出的索引結(jié)構(gòu)在保證準(zhǔn)確率的前提下,加快了檢索速度,并具有良好的擴(kuò)展性和靈活性,因此,針對(duì)大規(guī)模人臉數(shù)據(jù)庫,本文方法有效地實(shí)現(xiàn)了海量人臉快速檢索。

5 結(jié)束語

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

［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]史習(xí)云,薛安榮,劉艷紅.改進(jìn)k-means聚類算法在圖像檢索中的應(yīng)用研究［J］.計(jì)算機(jī)工程與應(yīng)用,2011, 47(10):193-196.

［4]何周燦,王 慶,楊 恒.一種面向快速圖像匹配的擴(kuò)展LSH算法［J］.四川大學(xué)學(xué)報(bào):自然科學(xué)版,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

汪 昀,朱 明,馮偉國(guó).一種支持海量人臉圖片快速檢索的索引結(jié)構(gòu)［J］.計(jì)算機(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

中國(guó)科學(xué)院先導(dǎo)專項(xiàng)課題基金資助項(xiàng)目“網(wǎng)絡(luò)視頻傳播與控制”(XDA06030900)。

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

2014-03-14

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