大規模人臉檢索系統設計與實現

余若晟 徐 超 張 帆

(復旦大學計算機科學技術學院 上海 200433)

0 引 言

21世紀以來，許多城市開始搭建城市監控網絡，通過監控攝像頭輔助取證，以保障并提升城市安全。在很長一段時間，城市監控系統只具備拍攝與存儲功能，即只能實現“看得見”。當需要利用監控視頻尋找犯罪證據時，通常會調動大量人力翻看同一時間段內不同攝像頭拍攝的海量視頻。隨著機器學習技術的發展與監控攝像機清晰度不斷提升，視頻智能化處理技術逐漸應用于生產實踐中。人們越來越不滿足于監控系統只能提供單一的拍攝和存儲功能，更希望監控系統能夠自己“找出”候選目標，從而提升城市安全管理效率，降低人力成本。因此，“找得到”已經成為智能城市監控的主要目標。

人物是城市監控系統的主要關注目標之一，而人臉因其獨特性與便利性，在身份認證與識別領域得到了深入的研究。以人臉識別為基礎的各類應用，如刷臉支付等也極大地方便了人們的日常生活。近年來，隨著深度學習的逐漸發展，基于深度學習的人臉識別方法使得人臉識別準確率大幅提升。2014年，FaceBook提出了DeepFace[1]，使用一個深度卷積神經網絡，在LFW數據集上的準確率達到了97.35%，達到人類水平。在隨后的幾年里，以FaceNet[2]、SphereFace[3]、ArcFace[4]為代表的一系列利用表示學習思想對人臉識別的改進使得人臉識別算法不僅在LFW[5]數據集上達到了逼近100%的準確率，并且大幅提升了諸如大姿態、模糊圖像等場景下的人臉識別準確率。

另外，近年來也有許多學者致力于提升大規模高維度特征向量最近鄰檢索的速度與召回率。近似最近鄰檢索的方法主要有哈希與量化兩個不同的思路。文獻[6-7]都是基于卷積神經網絡的哈希方法。文獻[6]利用卷積神經網絡編碼了圖像間的相似信息，將圖像特征提取與哈希編碼融合起來，實現了端到端的圖像哈希編碼。文獻[7]利用柯西交叉熵損失函數和柯西量化損失函數進一步增強了二進制特征捕捉圖像特征的能力。向量量化方法，即將一個向量空間中的點用其中的一個有限子集來進行編碼。這類方法中，乘積量化最為典型，文獻[8]提出了乘積量化的思路，將高維空間劃分為互斥的子空間，然后通過聚類算法得到各子空間的中心點，使得位于子空間內部的向量能被此聚類中心表示。文獻[9-10]為乘積量化的最新進展。文獻[9]改進了查詢階段尋找最近鄰聚類中心的策略，基于最近鄰概率而非聚類中心距離尋找候選子空間，從而提升了查詢召回率。文獻[10]提出了一種基于矢量量化和線量化的分層倒排索引結構，通過減少搜索空間和增加索引區域數量，在可控內存使用下實現了基于GPU的高效查找。

盡管人臉識別算法與最近鄰查找算法在近年來都有顯著發展，但是將其應用于智能化城市視頻監控系統之中時通常還會面臨許多困難。考慮在已知某犯罪分子姓名與外貌信息的情況下，利用城市監控攝像頭捕捉的視頻信息，找出其在城市中的活動軌跡的應用場景。該場景需要設計一個人臉檢索系統，支持對給定的人臉查詢圖片，在海量視頻庫中找到與該查詢圖片人物身份一致的視頻幀，并據此最終查詢得到視頻幀對應的元數據，如攝像頭編號、攝像頭所在位置、視頻幀對應的自然時間等。

不同于人臉識別系統，人臉檢索系統要求要盡可能多地找出圖像或視頻庫中匹配的人臉，因此相比準確率，人臉檢索系統更關注召回率。與人臉識別系統相同之處在于，兩者都要求查詢速度盡可能快。因此當我們把人臉識別算法應用于人臉檢索系統時，通常會面臨以下問題：

(1) 特征數量大導致檢索時間長，無法快速響應查詢。2 000個監控攝像頭，24小時不間斷錄制監控視頻，理論上會產出43.2億幅視頻圖像，需要大約4 TB空間存儲這些圖像。假設需要在這些視頻中找出特定人物，由于視頻幀與人臉并非一一對應關系，系統需要在超過43.2億幅圖像的特征中找到滿足要求的特征并獲取對應的元數據。如果簡單采用暴力搜索的方式對上十億特征進行比對，通常會耗費大量時間。

(2) 特征維數高使得傳統樹形索引結構失靈，而基于神經網絡的哈希方法需要較大算力。在傳統方法中，特征向量維數較低，特征向量各維度間相關性較弱，因此可以使用以K-D樹為代表的索引結構來加速特征的查詢和匹配。但是基于深度卷積神經網絡得到的特征向量維度通常較高，而且特征向量各維度之間相關性強，K-D樹在特征維度大于20之后性能急劇惡化。

因此，本文設計并實現一種大規模人臉檢索系統，基于ArcFace算法提取人臉特征，通過正軸體LSH算法[11]和VLH算法[12]構建高維人臉特征索引，加速人臉查找，通過基于LRU的熱點特征置換算法支持快速十億級特征檢索。

1 總體設計

考慮到2 000個攝像頭24小時產生的視頻幀對應的人臉特征數已經超過十億，而真實場景下攝像頭數量可能更多，因此本文系統設計時考慮在單一機器上支持盡可能大的查詢負載。本文系統的設計目標是：支持十億級高維度深度人臉特征的高速查詢，單次查詢時間不超過10秒。并且該系統應支持單機部署，GPU數量不超過1塊，內存大小不超過32 GB。

系統架構如圖1所示，總體采用B/S模式。用戶使用瀏覽器與后臺系統進行交互，用戶界面基于React與Redux庫，后臺Web層基于Flask框架，系統層采用C++進行編寫。Web層與檢索系統通過Thrift RPC進行遠程過程調用，實現了語言層面的解耦。

圖1 系統結構圖

本文系統的工作流程分為兩個階段：離線特征庫構建階段和在線人臉查詢階段。人臉檢索流程如圖2所示。

圖2 人臉檢索流程示意圖

離線特征庫構建階段，系統首先讀取視頻相應的元數據，并將視頻元數據存入數據庫。視頻讀取完成后，視頻幀將被轉換成圖像矩陣提供給特征提取模塊。特征提取模塊設計了統一的接口，接收圖像矩陣作為輸入，提供特征向量作為輸出。一旦發現性能更好的特征提取算法，系統可以在不修改原有代碼的情況下替換新的算法，實現人臉特征提取算法配置化與插件化。獲得圖像特征后，高速特征查詢器模塊首先將高維浮點數特征經過正軸體LSH轉換成高維二進制特征。然后，基于VLH算法計算得到的分段，將本圖像特征編號與其對應的哈希簇哈希桶信息交給存儲模塊。存儲模塊首先在內存中暫存高維浮點數向量以及圖像特征編號與哈希簇哈希桶信息，待積累到一定文件尺寸后，按規則將內存中暫存的高維浮點數向量持久化到磁盤上。

在線人臉查詢階段，系統接收一幅人臉圖像(待查詢圖像)作為輸入，在經過與離線特征庫構建階段類似的人臉特征向量提取、特征向量二進制轉換后，進入由粗到精的兩階段查找流程。第一階段粗查找，將二進制向量根據VLH分段算法進行分段，找到對應的哈希簇與哈希桶的編號后，提取所有哈希桶中保存的特征編號，構成第一階段粗查找的候選集。第二階段，根據特征編號讀取對應的二進制浮點數向量，此時數量較整體已極大減少，使用暴力搜索法找到所有滿足相似度條件的特征向量構成第二階段精細查找結果。最后，利用精細查找結果獲取圖像視頻元數據，返回給用戶。

2 主要算法

本文系統基于ArcFace構建人臉特征提取器。為了提高特征提取與查詢速度，本文略微減少了ArcFace輸出層的特征維度，并減少了部分卷積層FeatureMap數量。另外，本文引入LSH和VLH作為特征索引。前者可以將原始連續浮點數特征轉化為二進制特征，而后者可以通過將二進制特征分段，加速二進制特征查詢。

2.1 人臉特征提取

人臉特征提取器負責從圖像中找出人臉圖像，矯正人臉位置，并將人臉特征表征為高維空間中的特征向量。好的特征提取器需要又快又準地找到人臉，同時編碼辨識度高的人臉特征向量。

本文基于MTCNN算法進行人臉檢測與人臉關鍵點對齊。MTCNN是一個由粗到精的人臉檢測與人臉關鍵點檢測算法，用了三個復雜度不同的卷積神經網絡篩選圖像中的候選人臉區域。前兩個卷積神經網絡結構簡單、速度快，能排除掉大部分不是人臉的區域，最后將極可能是人臉的區域交給最后一個較復雜的卷積神經網絡，同時得到人臉關鍵點。根據MTCNN計算的人臉區域與關鍵點，將人臉圖像進行仿射變換，使得不同圖像的人臉五官經過形變后基本位于圖像相同區域，減少由于平移、旋轉給特征帶來的干擾。

本文基于ArcFace算法提取人臉圖像高維特征。ArcFace通過在訓練階段對傳統分類網絡的Softmax損失函數增加角度邊緣的方式進行改進，使得經過ResNet全連接層的圖像特征在余弦角度空間上，同類更近，不同類更遠，增加了網絡對于圖像顯著特征的捕捉能力，增加了特征辨識度。為了進一步提升檢索速度，將ArcFace的特征層維度降低到了128維，并使用自己構建的數據集混合公開數據集CASIA-WebFace重新進行了訓練。

2.2 高速索引

哈希是提升高維特征檢索速度廣泛使用的手段，能將高維浮點數向量映射到漢明空間，從而獲得高維二進制向量，降低向量距離計算的時間。考慮到ArcFace得到的特征需要基于余弦距離進行特征距離度量，我們選擇正軸體LSH作為哈希方法。

正軸體LSH將浮點數特征向量轉化為二進制向量在一定程度上減少了查詢時間，但由于系統中庫向量數量龐大，僅利用正軸體LSH依舊無法滿足快速檢索的需求，因此引入VLH來加速給定漢明距離閾值與召回率的條件下二進制向量的查找。VLH能夠在保證召回率的情況下，高速地篩選出滿足漢明距離閾值的候選向量集合，符合查詢系統對于召回率的需求。

3 實現細節

3.1 正軸體LSH計算加速

正軸體LSH分為兩步：(1) 生成一個d×d的隨機矩陣A；(2) 執行一次矩陣A與向量x的乘法運算。分析正軸體LSH的過程可知，生成d2個隨機數的時間復雜度為O(d2)，Ax運算的時間復雜度為O(d2)，存儲矩陣A所需的空間復雜度O(d2)。考慮本文系統向量維度與向量規模，需要從空間和時間兩個角度對其進行優化。

空間上，使用偽隨機旋轉來代替隨機旋轉：將隨機變換Ax，替換為線性變換HD3HD2HD1x，其中:矩陣H是d維Hadamard矩陣，矩陣Di(i∈{1,2,3})是由隨機值±1構成的d維對角矩陣。盡管目前沒有理論證明此線性變換相當于完全的隨機變換，但實驗數據表明，經過三次HDi變換HD3HD2HD1x，其效果等同于一次真正的隨機變換Ax。因此，對于每一次正軸體LSH，只需要存儲三個隨機對角矩陣Di即可。

使用旋轉后，每次計算依然需要進行矩陣與向量的相乘，其時間復雜度依然為O(d2)；但由于Hadamard矩陣H是固定的，無須每次存儲，只存儲對角陣Di，空間復雜度為O(d)，降低了空間需求。時間上，采用快速Hadamard變換加速這一運算過程，將時間復雜度從O(d2)縮減到O(dlogd)。從實現上，我們采用Eigen高速C++矩陣庫來執行計算，該庫能夠充分利用CPU的向量運算指令集來加速矩陣運算，進一步提升算法運行速度。

3.2 VLH存儲結構設計

為了盡可能降低查找流程中的時間開銷與空間開銷，同時充分利用VLH多哈希索引的特點，本文設計了針對VLH索引的存儲結構與訪問機制。

二進制向量經過VLH分段算法分成i段后，對應產生i個哈希簇。每個哈希簇有且僅有一個哈希桶存儲二進制向量對應的id。對于128維二進制向量，在給定VLH召回率為0.9，漢明距離20的條件下，VLH分段算法將產生12個哈希簇，對應二進制向量各段長度為13、11、10、10、10、10、10、10、10、10、10、10。假設庫向量的數量為10億個，則需要12×109×4≈45.8 GB空間存儲VLH索引，超出了設計時評估的內存需求(32 GB)。

因此，本文設計將VLH索引中每個哈希簇的哈希桶內存儲的所有向量id以連續塊的形式持久化到磁盤上，并將持久化的文件以“哈希簇號_哈希桶號.bin”的方式命名。如第1哈希簇第154號桶，將其命名為1_154.bin。為了盡可能保證響應時間，當系統冷啟動時，預先加載8 GB大小的索引文件到內存中。若后續查詢命中內存中的哈希桶，則可直接返回結果，若后續查詢未命中，按照LRU算法置換掉內存中的哈希桶。借此，在保證內存使用不超過設計上限的條件下本文實現了大規模高速查詢索引。

4 用戶界面

本系統應用界面如圖3、圖4所示。圖3展示了用戶上傳圖片的頁面，待后臺檢索完成后，跳轉到如圖4所示的結果頁面。

圖3 圖片上傳頁面

圖4 檢索結果顯示

結果頁面分為三個部分，左上角展示了用戶上傳的查詢圖像，左下區域以視頻幀縮略圖形式展現了系統查詢到的視頻幀圖片。點擊視頻幀圖片，可以在結果頁右側看到視頻幀大圖，同時元數據將在視頻幀大圖下展示。

5 實 驗

本文按照設計實現了原型系統，并測試了系統的人臉識別性能與索引訪問性能。

本文的實驗部署環境為：Intel?CoreTMi7 5960x;32 GB內存;1 TB SSD;NVIDIA GeForce Titan X;操作系統為 Windows 10。

為了測試索引性能，本文使用CASIA-WebFace、LFW等人臉數據集合成了約1 000萬幅圖像。選取總時長大約5 000小時的電視劇，將電視劇中視頻幀解碼成圖像，然后在圖像上隨機貼上0～5幅不同的人臉，構建了一個約有11.2億幅人臉的圖像庫。然后從人臉數據集中挑選了100幅人臉圖像作為查詢集，測試索引查詢性能。測試過程中，VLH閾值設置為32，以保證召回率高于90%，在此條件下，一階段粗查找得到約10萬個向量編號。從這些向量中進行二階段篩選，得到最后結果，總計耗時約7.9 s，達到了預期的設計目標(單次查詢10 s以內)。

6 結 語

本文通過分析大規模深度特征人臉檢索系統的特點，設計并實現一種大規模人臉檢索系統，支持在10 s內對十億級高維深度人臉特征進行檢索。系統基于ArcFace算法提取人臉特征，基于正軸體LSH算法和VLH算法構建高維人臉深度特征索引，加速特征的查詢過程。系統通過優化正軸體LSH的時空復雜度以及針對VLH索引特點設計存儲結構與訪問機制的方式，降低了部署上的硬件要求。

本文設計的大規模人臉檢索系統可應用于城市智能監控，為刑偵與安保工作提供助力。通過高效人臉檢索與元數據分析，使得監控系統不僅“看得見”，并且初步實現“找得到”，減輕篩選監控視頻的人力負擔。