基于移動平臺的快速相似臉檢索

鄧健康，楊靜，王蒙，劉青山

(南京信息工程大學 信息與控制學院，南京210044)

隨著手機、平板電腦等移動設備計算與存儲性能的提升，移動設備的智能化也成了學術界與工業界的研究熱點.移動智能終端上圖像傳感器的改進也給移動平臺上的視覺應用提供了更好的硬件條件支撐［1］.同時，隨著人臉分析技術的進步，移動終端的人臉識別、表情識別、屬性分析等移動應用在人們的生活中已經嶄露頭角.另外，基于內容的圖像信息檢索技術也逐漸成熟，各大搜索引擎也加入了“以圖搜圖”的功能.人臉識別技術和基于內容的信息檢索技術的進步，使得自動化的相似臉檢索成為可能.相似臉檢索在娛樂搜索、犯罪監視等方面具有很高的應用價值.本文基于移動平臺在大規模人臉數據庫上實現快速的相似臉檢索.然而，移動平臺的計算和存儲能力畢竟有限.所以，如何設計時間復雜度和空間復雜度低的算法成為解決移動平臺上相似臉檢索的關鍵問題.

基于精確的人臉配準，建立了級聯形狀和紋理特征的高效的相似臉檢索模型，核心技術包括人臉配準、人臉特征提取與壓縮、檢索算法.

人臉配準是在一幅人臉圖像中自動地定位出人臉各個器官的準確位置以及人臉的外輪廓，是人臉圖像處理與分析的基礎與前提，不精確的關鍵點定位往往會引起“誤配準災難”［2］.近年來，國內外學者提出了各種人臉配準方法，大體上可以分為基于參數化模型的方法［3-7］和基于回歸的方法［8-12］.基于級聯回歸的方法在自然條件下的人臉庫上配準精度高，且模型簡單、速度快，備受研究者的關注.該方法主要依賴局部描述子穩健的性能，通過級聯的弱回歸器擬合復雜的非線性映射，能夠有效定位人臉關鍵點的坐標.文獻［10］采用快速SIFT(Scale Invariant Feature Transform)特征，通過最小二乘回歸實現關鍵點快速定位.文獻［11］通過利用二值特征，進一步提高了配準速度.文獻［12］通過顯式的回歸遮擋信息，增強了模型在局部遮擋情況下的魯棒性.在級聯回歸模型中引入稀疏約束，可以增強模型的魯棒性，同時壓縮模型的存儲空間.

文獻［13］指出了高維人臉特征對人臉識別的重要意義，并采用旋轉稀疏投影的方式進行了高效的特征降維.基于精確的人臉配準，可以提取關鍵點周圍的高維紋理特征，并通過稀疏投影高效降維.

高效的索引機制是圖像檢索的關鍵，圖像哈希［14］作為一種優良的圖像單向壓縮技術，是近年來圖像檢索領域的研究熱點，但哈希算法必須有足夠的散布空間以降低沖突率.通過級聯形狀和局部紋理特征，可以不斷縮小檢索空間，進行高效的相似臉檢索.由于形狀和局部紋理的特征維度均較低，可以采用基于稀疏重構的方式高效地檢索相似臉，最終獲得臉型和五官紋理均相似的人臉圖像.

對 LFW(Labeled Face in Wild)［15］進行擴展，建立了近百萬級的人臉數據庫，采用級聯形狀和紋理特征的方法實現高效的相似臉檢索.該模型對移動端的計算和存儲資源要求較低，具有精度高、速度快、模型小的特點.在三星Note 3智能手機上，每幅人臉圖像的配準時間在10 ms左右，相似臉檢索時間在1.5 s左右，整個模型大小僅 5.4 MB.

1 級聯形狀和紋理的相似臉檢索

為了在移動平臺上進行快速的相似臉檢索，基于精確的人臉配準，采用級聯形狀和紋理的相似臉檢索模型，方法流程如圖1所示.

首先，通過基于稀疏約束的級聯回歸模型進行人臉配準，估計人臉姿態［16］，進行圖像規范化以消除旋轉、平移、縮放差異.稀疏約束的級聯回歸能夠篩選魯棒的特征，高效地壓縮模型的存儲空間.

然后，在對應的人臉姿態子集中進行基于稀疏形狀重構的相似臉型檢索.同時，提取測試人臉圖像的局部紋理特征，并通過稀疏投影進行高效降維.

最后，將低維紋理特征在臉型相似的子集中進行基于稀疏紋理重構的相似臉檢索.通過級聯形狀和紋理的檢索，檢索效率明顯提升，且返回的結果在臉型和五官紋理上均具有很強的相似性.

圖1 相似臉檢索示意圖Fig.1 Schematic of similar face retrieval

圖2 基于移動平臺的相似臉檢索Fig.2 Similar face retrieval on mobile platform

圖2展示了基于移動平臺的相似臉檢索的交互過程，移動端先將人臉形狀發送到服務器端，接著對內部的某些關鍵點提取高維紋理特征，并進行基于稀疏投影的特征降維，然后將低維紋理特征發送至服務器端.在移動端進行紋理特征提取的時候，服務器端同步完成基于稀疏形狀重構的相似臉型檢索.服務器端基于稀疏紋理重構的相似臉檢索在臉型相似的人臉子集中完成，檢索效率較高，最終服務器端向移動端返回相似度最高的5個人臉圖像.相似臉檢索過程中移動端和服務器端的通信主要有:移動端發送136維人臉形狀，500維人臉紋理特征，服務器端返回5幅相似臉圖像(稀疏重構支持增量傳輸，稀疏系數可作為相似度指標).移動端的模型存儲主要是稀疏級聯回歸模型(約1.56 MB)和高維紋理特征的稀疏投影矩陣(約3.80 MB).移動端的計算主要集中在特征提取、級聯回歸，紋理特征稀疏投影.整個交互過程在近百萬級人臉數據庫上進行，硬件條件為三星Note 3，Wifi環境(或者3G)，IBM 服務器(12 核，3.4 GHz，128 GB內存)，相似臉檢索的時間大約1.5 s.

1.1 基于稀疏級聯回歸的人臉配準

級聯回歸模型通過級聯簡單的回歸器不斷擬合配準殘差完成人臉配準.通過級聯T個回歸器(R1，R2，…，RT)不斷擬合配準殘差:

式中，Ii為人臉圖像;N為訓練集人臉圖像的數目;Xi*為標定的人臉形狀;Xit為迭代過程中的人臉形狀;Rt為每步迭代的回歸矩陣;Φ(Ii，Xit)為圖像Ii在形狀Xit位置下的SIFT特征描述，每一步回歸的目標都是減少殘差，該優化問題可以通過最小二乘求解，存在閉式解.迭代過程中的形狀更新按照累加的形式完成:

在實際的應用過程中，迭代步數在4或5次即可收斂.由訓練的目標函數可知，迭代過程中的形狀實際上是在人臉形狀的線性子空間中，由此，引入了隱性的人臉形狀約束，這種約束相對于參數化模型靈活性較高，能夠適應姿態變化和夸張表情.

從迭代過程中的形狀增量RtΦ(Ii，Xit)可知，對于每個關鍵點迭代過程中位置的變化，都與所有關鍵點的特征相關，因此，參數維度較高，容易過擬合.可以對回歸矩陣Rt引入稀疏約束，即假設某個關鍵點的位置變化僅僅與一部分關鍵點的特征相關.

式中，ΔXit=Xi*－Xit，該優化問題可由 Lasso［17］求解;λ1為正則系數，控制回歸矩陣Rt的稀疏度.

通過交叉驗證確定λ1=0.1，此時，Rt每行的非零元素約為300左右，遠小于8704(68×128)，Rt可以獲得5%左右的壓縮率，大大縮小了模型的存儲空間.同時，稀疏的回歸矩陣對應著稀疏的特征選擇，相對于最小二乘的求解方法，稀疏約束抑制了過擬合傾向，篩選了魯棒的特征.基于稀疏級聯回歸的人臉配準過程如圖3所示，配準過程迭代5次.

圖3 基于稀疏級聯回歸的人臉配準Fig.3 Face alignment based on sparse cascade regression

1.2 人臉特征提取與壓縮

基于人臉關鍵點的準確定位，對人臉圖像進行了歸一化以消除旋轉、平移以及縮放的差異.如圖4所示，基于每幅人臉圖像構建5層的圖像金字塔(瞳孔距250，100，150，100，50 像素)，并在一些人臉內部關鍵點位置(40像素×40像素)提取人臉的局部多尺度特征.采用LBP，HoG和Gabor特征描述子，最終形成高維的人臉紋理特征.

圖4 基于稀疏投影的特征降維Fig.4 Feature dimension reduction based on sparse projection

由于移動平臺計算和存儲能力有限，需要對高維特征進行壓縮.然而，傳統的特征降維方法對計算和存儲要求較高.例如，采用主成分分析法將10萬維的高維特征降到1000維，每次投影需要1億次浮點乘法運算，投影矩陣占用存儲空間400MB.通過學習稀疏投影矩陣，能夠對高維的人臉紋理特征進行高效降維.如圖4所示，X是高維特征，即每幅人臉圖像每個關鍵點的多尺度聯合特征.通過PCA將原始高維特征降維，為了降低計算和存儲復雜度，采用稀疏投影矩陣擬合該降維過程.

考慮到子空間對旋轉具有不變性，通過在最終的低維特征Y前引入旋轉矩陣R，可以近一步提升投影矩陣B的稀疏度.

上述優化問題在給定R的情況下，可以通過Lasso［17］求解，并且B的每列求解可以并行加速.在給定B的情況下，R存在閉式解，R=UVT，其中UVT來自YXTB的SVD分解UσVT.最終通過迭代求解得到稀疏投影矩陣B，在測試過程中，降維過程就是BTX.

1.3 基于分層匹配的相似臉檢索

在百萬級的人臉數據庫上直接進行相似臉檢索往往效率較低，可以結合人臉形狀和局部紋理進行分層匹配，整個過程如圖1所示.

首先，通過人臉關鍵點估計人臉姿態［16］，進行人臉的規范化，人臉側轉的角度用來選擇相應的人臉檢索庫的子集.同時也可以通過性別、年齡、種族等屬性對檢索庫進行分組進一步縮小檢索空間.

然后，將測試圖片的人臉形狀向量在樣本的形狀字典上進行稀疏重構，獲取臉型相似的人臉樣本.

最后，將測試圖片的低維紋理向量在樣本的紋理字典上進行稀疏重構，獲取臉型和五官紋理均相似的人臉圖像.

式中，T(X，β)為將測試的人臉形狀X與字典中的人臉形狀D消除旋轉、平移、縮放的相似變換;α為稀疏重構系數.

同理進行稀疏紋理重構，差異僅僅在于紋理特征向量不需要進行相似變換.

2 人臉配準的實驗結果

2.1 實驗數據與定位結果評價

采用300-W人臉配準比賽［18］的標注數據進行訓練和測試，其中包括AFW(337)，iBug(135)，XM2VTS(2 360)，LFPW(811+224)，HELEN(2000+330)，關鍵點的定義如圖5所示.LFPW和Helen的測試集用來進行測試，其余圖像都用于訓練.為了進一步擴充數據集，對訓練數據進行鏡像操作，對初始化的平均形狀進行擾動以產生更多的訓練數據，最終獲得了112860(5643×2×10)的訓練數據.

圖5 關鍵點的定義Fig.5 Definition of landmarks

在人臉關鍵點定位的精度評價方面，關鍵點的平均定位誤差定義為

2.2 LFPW和Helen實驗結果

LFPW和Helen都是自然場景下的人臉數據庫，其中姿態、光照、表情變化比較大，并且存在一定程度的遮擋.作為對比的方法是4層級聯回歸的SDM［10］模型.測試結果如圖6所示，本文的方法比SDM略好一些，主要是因為稀疏約束可以提取魯棒的特征，對局部遮擋適應性更強.圖6同時顯示了每個關鍵點的定位誤差，每個關鍵點上圓的半徑代表平均定位誤差的大小，由圖可知，眼睛上的關鍵點定位比較準確，而人臉外輪廓和眉毛上的關鍵點定位誤差較大.表1、表2給出了各種級聯回歸方法在LFPW和Helen上的平均定位誤差，其他方法的平均定位誤差來自文獻［11］.表3給出了稀疏度與模型大小的關系，圖7給出了Android平臺人臉配準示意圖.

圖6 LFPW和Helen配準結果Fig.6 Alignment results on LFPW and Helen

表1 LFPW歸一化平均誤差Table1 Normalized mean error on LFPW

表2 Helen歸一化平均誤差Table2 Normalized mean error on Helen

表3 稀疏度與模型大小的關系Table3 Relationship between sparsity and model size

圖7 Android平臺人臉配準結果Fig.7 Results of face alignment on Android platform

3 相似臉檢索的實驗結果

3.1 實驗數據

原始的LFW［15］數據庫包含5 749個公眾人物的13233張人臉圖像，通過這5749個人名，在搜索引擎上整理得到617430張人臉圖像，每個人對應的人臉圖像數目從200到2000不等.同時整理出包含1 540人的中國名人列表，并相應地搜索得到186985張人臉圖像.數據庫整理時的人臉檢測方法來自文獻［19］，大約10%左右漏檢的人臉圖像采用手工方式標注人臉框，人臉配準采用稀疏級聯回歸，姿態估計方法來自文獻［16］.相似臉檢索庫的規模大約是75萬，每個人的人臉圖像集大約包括3%～5%的其他人臉.對庫中的人臉按性別(男/女)、種族(黑人/白人/黃種人)、姿態(側角)進行分組，按樹的形式重新整理了數據庫.

為了比較基于分層匹配的相似臉檢索方法和基于哈希的相似臉檢索方法，從每個名人庫中抽出5張人臉圖像，一共36445(7289×5)張人臉圖像.對這些人臉圖像進行配準規范化，提取LBP，HoG和 Gabor聯合特征，通過 k-means聚成1000類.然后，通過人工篩選的方式，將每一類中視覺上不相似的人臉圖像刪除，最終形成相似臉檢索測試庫.

3.2 高維特征的稀疏投影

在原始的LFW數據庫上確定最佳的特征提取方式、關鍵點數目、圖像金字塔層數、特征投影的稀疏度.原始高維人臉特征通過PCA降維到500維，稀疏投影擬合該降維過程，低維特征用來進行基于最近鄰的人臉識別.如圖8所示，通過控制變量法逐一調節參數，最終權衡速度與精度，選取LBP特征，關鍵點的數目為13(不包括人臉外輪廓和眉毛上的關鍵點)，圖像金字塔層數為5層，特征投影的稀疏度為99%，在LFW數據庫上的識別精度為81.42%.

圖8 關鍵點數目、金字塔層數、投影矩陣稀疏度對識別精度的影響Fig.8 Effects of number of landmarks，layer of pyramids and sparsity of projection matrixes on recognition accuracy

3.3 相似臉檢索

首先，在相似臉檢索測試庫上比較基于分層匹配的相似臉檢索和基于哈希的相似臉檢索.基于哈希的相似臉檢索在原始高維人臉特征上進行，哈希編碼的方式參考了文獻［20］.實驗結果如表4所示，基于哈希的相似臉檢索方式在速度上有一定的優勢，然而，基于分層匹配的方式能夠在保證實時的情況下，準確率高出很多.

表4 速度和準確率的比較Table4 Comparison of speed and accuracy

然后，在擴展的LFW數據庫上進行大規模相似臉檢索測試.對于用戶輸入的人臉圖像，首先進行快速人臉配準，給出性別、種族信息.當服務器端接收到這些信息的時候，在相應的子庫中進行基于稀疏形狀重構的相似臉型檢索，稀疏重構的正則參數設為0.01.當服務器端完成相似臉型的檢索，客戶端的人臉低維紋理特征也發送到服務器端，于是服務器端繼續完成基于稀疏紋理重構的相似臉檢索，稀疏重構的正則參數設為0.1，最后稀疏系數最大的5個人臉圖像作為相似度最高的圖像返回給客戶端.圖9分析了整個算法的效率，通常在1.3～1.5s之間即可返回與輸入人臉圖像最相似的5個相似臉，圖10展示了檢索返回的相似臉.

圖9 基于移動平臺的相似臉檢索耗時分析Fig.9 Time consuming analysis of similar face retrieval based on mobile platform

圖10 級聯形狀和紋理的相似臉檢索結果Fig.10 Results of similar face retrieval based on cascade shape and appearance

4 結論

主要研究了基于移動平臺的快速相似臉檢索問題，基于精確的人臉配準，建立了級聯形狀和紋理的相似臉檢索模型.

1)在人臉檢測的基礎上進行基于稀疏約束的級聯回歸配準，回歸器的訓練通過引入稀疏約束，增強了模型的魯棒性，同時可以將模型的大小壓縮到原來的5%左右.提出的配準模型在LFPW和Helen等自然場景的人臉數據庫上取得了很好的配準結果，具有速度快、精度高、模型小的特點.

2)在人臉配準的基礎上，級聯人臉形狀和局部紋理特征進行基于稀疏重構的高效的相似臉檢索，其中局部紋理特征采用稀疏投影的方式壓縮高維特征.提出的相似臉檢索方法在接近百萬級的數據庫上能夠實時檢索相似臉，且臉型結合五官紋理的相似度衡量標準符合人們的視覺感受.

3)目前的配準算法對于夸張表情、嚴重遮擋等情況的配準精度還有待提高，服務器端的相似臉檢索效率也可以繼續提升.在今后的工作中，將進一步提高配準精度，融合圖像哈希等方法進一步加速檢索.

References)

［1］ Hua G，Fu Y，Turk M，et al.Introduction to the special issue on mobile vision［J］.International Journal of Computer Vision，2012，96(3):277-279.

［2］ 山世光，高文，唱軼鉦，等.人臉識別中的“誤配準災難”問題研究［J］.計算機學報，2005，28(5):783-791.Shan S G，Gao W，Chang Y Z，et al.“Curse of Mis-alignment”problem in face recognition［J］.Chinese Journal of Computers，2005，28(5):783-791(in Chinese).

［3］ Cootes T F，Taylor C J，Cooper D H，et al.Active shape modelstheir training and application［J］.Computer Vision and Image Understanding，1995，61(1):38-59.

［4］ Cootes T F，Edwards G J，Taylor C J.Active appearance models［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23(6):681-685.

［5］ Cristinacce D，Cootes T.Automatic feature localisation with constrained local models［J］.Pattern Recognition，2008，41(10):3054-3067.

［6］ Zhu X X，Ramanan D.Face detection，pose estimation，and landmark localization in the wild［C］//Proceeding of the Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2012:2879-2886.

［7］ Zhou F，Brandt J，Lin Z.Exemplar-based graph matching for robust facial landmark localization［C］//Proceedings of the IEEE International Conference on Computer Vision.Piscataway，NJ:IEEE，2013:1025-1032.

［8］ Sun Y，Wang X G，Tang X O.Deep convolutional network cascade for facial point detection［C］//Proceeding of the Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2013:3476-3483.

［9］ Cao X D，Wei Y C，Wen F，et al.Face alignment by explicit shape regression［C］//Proceeding of the Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2012:2887-2894.

［10］ Xiong X H，De la Torre F.Supervised descent method and its applications to face alignment［C］//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2013:532-539.

［11］ Ren S Q，Cao X D，Wei Y C，et al.Face alignment at 3000 FPS via regressing local binary features［C］//Proceeding of the Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2014:1232-1240.

［12］ Burgos-Artizzu X P，Perona P，Dollar P.Robust face landmark estimation under occlusion［C］//Proceeding of the International Conference on Computer Vision.Piscataway，NJ:IEEE，2013:1513-1520.

［13］ Chen D，Cao X，Wen F，et al.Blessing of dimensionality:highdimensional feature and its efficient compression for face verification［C］//Proceeding of the Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2013:3025-3032.

［14］ Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing［J］.VLDB，1999，99(6):518-529.

［15］ Huang G B，Mattar M，Berg T，et al.Labeled faces in the wild:a database for studying face recognition in unconstrained environments［J］.International Journal of Computer Vision，2007，96(3):277-279.

［16］ Asthana A，Zafeiriou S，Cheng S，et al.Robust discriminative response map fitting with constrained local models［C］//Proceeding of the Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2013:3444-3451.

［17］ Tibshirani R.Regression shrinkage and selection via the lasso［J］.Journal of the Royal Statistical Society，1996，24(3):267-288.

［18］ Sagonas C，Tzimiropoulos G，Zafeiriou S，et al.300 faces in-thewild challenge:the first facial landmark localization challenge［C］//Proceedings of the IEEE International Conference on Computer Vision.Piscataway，NJ:IEEE，2013:397-403.

［19］ Yan J J，Zhang X C，Lei Z，et al.Structural models for face detection［C］//Proceeding of the Automatic Face and Gesture Recognition.Washington:IEEE Computer Society，2013:1-6.

［20］ Cheng J，Leng C，Wu J X，et al.Fast and accurate image matching with cascade hashing for 3D reconstruction［C］//Proceeding of the Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2014:1-8.