基于人臉卡口數據的行人共現關系圖譜構建①

屈詩琪, 劉宇寧, 范冰冰

(華南師范大學 計算機學院, 廣州 510631)

1 引言

隨著人臉識別技術的不斷突破和完善, 可以提取到人臉在不同光影、姿態、表情和成像條件下的魯棒的特征, 進而通過人的臉部特征信息進行身份識別, 因此大范圍地部署人臉卡口是現在安防領域的重要發展目標. 人臉卡口即智能人臉抓拍攝像機, 主要部署在非機動車道, 比如一些重要的道路的人行道或者一些場所的出入口上, 只關注行人信息, 可以有效地采集經過的行人人臉圖片, 形成人臉圖像庫. 由此, 當鎖定某個案件嫌疑人時, 可以實現人臉檢索功能, 得出嫌疑人被拍到的圖片、地點和時間信息, 大致可以還原該人的行動軌跡; 還可以實現實時人臉比對功能, 當人臉被抓拍到時, 實時比對布控庫中的人臉, 抓捕在逃人員等.

但在偵察團伙犯罪案件時, 對人臉卡口數據已經不滿足只能實現人臉檢索、人臉比對和人臉驗證等功能. 如何從這樣一個海量的未知人員人臉圖像庫獲得更深層的信息, 比如除了獲取嫌疑人的個人信息之外,還想知道與嫌疑人有密切來往關系的人有哪些, 即構建嫌疑人社交網絡, 這將會是公共安全領域關注的熱點問題. 人的社交一般分為虛擬和現實, 虛擬比如手機通話、微信等的社交軟件, 這一類數據可以通過網絡監管獲取. 但現實的社交是比較難獲取的, 現有的方法主要還是靠人工操作, 通過調取海量的監控視頻進行反復查看才能建立行人之間的關系, 效率低下. 利用人臉卡口數據, 自動構建行人共現關系圖譜, 能夠給解決這一類問題提供思路和線索.

隨著多媒體技術的快速發展, 圖像、視頻等多媒體數據的大量涌現, 基于圖像和視頻信息的社交關系理解研究也在進一步發展. Wu 等人[1]通過人們的相冊集發現人們現實的社交關系, 其中根據個體在同一張照片的次數和距離來判定關系的緊密程度建立無向加權圖, 再使用一種圖聚類算法, 來檢測社交集群; 周麗麗[2]將影視視頻關鍵幀作為事務, 使用FP-Growth 對其進行頻繁項集挖掘來判定兩個人物之間有無關系,當共同出現次數超過閾值則存在關系, 以此構建人物關系網絡; 周檬[3]利用DBSCAN 進行人臉聚類, 再通過統計監控視頻關鍵幀中行人與行人間的共現關系、人與攝像頭的出現關系構建視頻圖譜.

在大多社交關系的研究中, 缺乏人物節點(關系圖上的頂點)識別的具體論述, 使用的聚類算法沒有經過比較并對其進行有效性驗證. 人臉卡口的人臉類別數量相對于相冊集或者影視劇中的實驗數據集更為復雜多樣, 作為關系網絡構建的基礎, 準確地進行人物節點識別才能構建可用的行人共現關系圖譜; 在目前研究人物之間的社交關系中, 其中關系存在判定, 即有無關系, 主要是基于共現的方法, 關系程度則取決于共現頻度. 對此, 本文基于行人節點識別和共現關系抽取兩個方面完成行人共現關系圖譜的構建流程: 首先提出基于Chinese Whispers 的行人節點識別的算法, 在此基礎上使用Faiss 加速鄰接邊的構建, 提高行人節點識別效率, 并與其他算法做比較驗證了其優越性. 其次, 在共現頻次的基礎上增加其置信度來挖掘行人的關系, 最后以圖形界面的形式展示圖譜.

2 相關知識

2.1 人臉聚類評價方法

使用有標簽的人臉數據集并根據兩種聚類評價指標對聚類結果進行評價: 1)采用scikit-learn 庫中的聚類效果評價指標: 同質性(homogeneity): 每個集群只包含單個類的成員; 完整性(completeness): 同類的所有成員都分配在同一集群中; 同質性和完整性的加權平均F-measure. 以人臉聚類為例, 同質性即同一個類中是否都是同一個人的照片, 完整性即是否將一個人的所有照片都聚集在一個類中. 2)采用文獻[4]中的成對準確率P_pairwise, 成對召回率R_pairwise指標. 如式(1)、式(2)所示:

其中,TP表示同一個人的人臉被正確地聚在同一類中的對數;FP表示不是同一個人的人臉被錯誤地聚在同一個類中的對數;TN表示不是同一個人的人被正確地聚到不同的類中;FN表示同一個人的人臉被錯誤地聚到不同的類中. 其中, 成對F均值度量F_pairwise:

2.2 DBSCAN

DBSCAN (density-based spatial clustering of applications with noise)是一種很典型的密度聚類算法,這類密度聚類算法一般假定類別可以通過樣本分布的緊密程度決定. 算法通過參數(Eps,MinPts)用來描述樣本分布緊密程度, 其中,Eps描述任意樣本的鄰域距離閾值(距離度量一般使用歐式距離、曼哈頓距離等),MinPts描述了任意樣本的Eps鄰域中樣本個數的閾值. (Eps,MinPts)參數是影響聚類效果的兩個很重要的參數,Eps過小會導致原本是一個類簇卻被分割成多個小的類簇,Eps過大會導致不是一個類簇的多個距離相近的簇聚成一個大簇.MinPts越大, 形成類簇的條件就越苛刻, 那么樣本集的噪聲點就越多, 當MinPts=1 時,樣本集中就沒有噪聲點, 所有的樣本都能在類簇中.

2.3 Approximate Rank Order

Approximate Rank Order[4]聚類是根據Rank Order[5]聚類改進的. 與絕對距離(比如歐氏距離)不同, Rank Order 聚類發現了來自同一個人的兩個臉往往有許多共享的鄰居, 但是來自不同人的兩個臉的鄰居通常差別很大這一特點, 提出一個新的人臉相似度量方法Rank Order 距離, 它通過比較兩個樣本之間的鄰域結構得到樣本之間的相似度. 后來, 為了使其能應用在大規模人臉數據中, 提高聚類效率, Approximate Rank Order 算法重新定義距離的度量方式, 不需要計算每個人臉的所有最近鄰而是k個最近鄰, 從而得出人臉之間的非對稱秩序距離之后, 就可以逐步地將低于距離閾值threshold 的人臉合并為一個類簇.k和threshold是該算法的兩個需要指定的參數.k是選取每個人臉最近鄰的數量, 而且Approximate Rank Order 使用FLANN庫的隨機k-d tree 算法求出每個人臉圖片的k個最近鄰圖片排序, 聚類的效率顯著地提高.

3 行人共現關系圖譜構建

人臉卡口主要采集經過的行人的人臉圖像、被抓拍到的時間戳以及卡口自身的編號, 其中卡口的編號就代表行人被抓拍時的位置信息. 基于人臉卡口的行人共現關系圖譜構建的整體流程如圖1 所示, 其中最主要的兩個步驟: 一是基于聚類的行人節點識別, 由于人臉卡口中出現的人是未知的, 沒有模板人臉庫讓其去一一對應來標明行人的身份, 所以使用基于聚類的方法標注人臉卡口中的人臉圖像, 從而得到圖譜中的行人節點; 二是行人共現關系抽取, 通過人臉卡口數據的特性, 定義共現關系的有無和共現關系的強度來共同抽取行人間的共現關系, 從而得到圖譜中節點之間的邊.

圖1 行人共現關系圖譜構建流程

3.1 基于聚類的行人節點識別

基于聚類的行人節點識別, 也可稱作人臉聚類, 旨在把相似的人臉圖像歸為一類, 即把屬于同一個人的人臉打上同一個標簽[6], 如圖2 所示. 人臉聚類效果的好壞主要取決人臉特征的提取(人臉的向量表示)和聚類算法的選擇[7], 人臉特征的提取要保證具有高精度的可分性, 這里使用目前效果較好的CNN+ArcFace Loss方法提取人臉特征向量. 適用于人臉聚類的聚類算法是不需要預先設定類別的數量的, 如傳統的K-means就不行, 因為我們對人臉卡口數據集是沒有預先的認識, 其具體包含多少個類別是未知的. 文獻[3]使用CNN+ArcFace Loss 方法提取人臉特征, 直接使用DBSCAN作為人臉聚類算法, 標識監控視頻中出現的行人; 文獻[8]使用FaceNet 提取人臉特征, 在LFW 數據集上驗證了DBSCAN 相較于其他聚類方法(如譜聚類和Rank Order); 文獻[9]使用附加間隔Softmax 提取人臉特征,分別在LFW 和LFW+模糊視頻上實驗結果都證明Approximate Rank Order 比DBSCAN 更加適合處理較大規模的復雜人臉數據; 文獻[10]使用Chinese Whispers對人臉聚類獲取同一個人的人臉圖像, 結合人臉質量評估算法從而達到在一段視頻中人臉圖像去重的目的.可見, 適用于人臉聚類的聚類算法是需要根據人臉特征提取算法和人臉數據擇優選擇的, 常用來做人臉聚類的算法主要是DBSCAN, Approximate Rank Order和Chinese Whispers.

圖2 行人節點識別

3.1.1 Chinese Whispers 算法

Chinese Whispers[11]最早是被用在自然語言處理如文本聚類中, 后來也廣泛應用于人臉聚類, 它不需要預先設定類別數量, 是一種可以自動查找類別個數的高效圖形聚類算法. 該算法分為兩個步驟: 第一步是構建無向加權圖G=(V,E). 把數據集中的每一個樣本當作圖上的一個點v_i∈V, 并且初始化每一個節點的類別屬性為當前節點順序編號. 接著就是構造無向圖的邊, 當節點v_i和v_j(其中v_i

該算法需要事先定義兩個超參數threshold 和iterations. threshold 是節點之間的相似度閾值, 只有大于這個閾值, 節點與節點之間才有邊, 消息才得以互相傳遞. 形式上, 該算法并不會收斂, 所以要指定iterations迭代次數, 但是對于加權圖, 只需要幾次迭代就能達到穩定狀態. 它的不足之處在于因為其隨機性(對小圖來說從哪個節點開始迭代很重要), 所以對于處理小圖具有不確定性, 但是在大圖中這種不確定性將會消失, 適合處理稍大數據的聚類.

3.1.2 改進的基于Chinese Whispers 的行人節點識別

雖然原始的Chinese Whispers 算法是適合處理稍大數據的聚類, 但是由于人臉特征向量512 維是高維向量, 算法需要計算不同節點之間的相似度, 其時間復雜度為O(n2), 當處理大規模人臉聚類時, 會導致算法的第一步驟即圖的初始化緩慢. 文獻[7]使用增量聚類的思想提出基于Chinese Whispers 的人臉動態聚類, 其時間效率雖然稍有提高, 但是準確率都稍有下降, 并且對于類別數較多的數據集, 時間提升效果不明顯. 本文使用Faiss (Facebook AI similarity search)[12,13]加速圖中節點的邊的構建, 把判斷兩節點是否相似問題, 轉化為對節點的限定半徑鄰居查詢問題, 提高聚類速度.Faiss 為稠密向量提供高效相似度搜索, 是目前最為成熟的近似鄰搜索庫. Faiss 提供了許多不同應用場景下的索引供選擇, 由于Chinese Whispers 算法需要計算每個樣本節點之間的相似度, 即余弦相似度, 提取的人臉特征是經過L2 范數歸一化的, 人臉特征余弦相似度的值等同于人臉特征內積的值, 所以選擇Faiss 中的IndexFlatIP 為人臉特征構建索引. 其中詳細的行人節點識別步驟如算法1 所示.

算法1. 改進的基于Chinese Whispers 的行人節點識別算法輸入: 行人人臉圖像數據集D, 相似度閾值t, 迭代次數iterations輸出: 行人身份標簽列表labels 1) 使用CNN+ArcFace Loss 提取數據集D 中所有人臉圖像的人臉特征, 保存到feats;2) 根據feats 構建Faiss 中的IndexFlatIP 特征索引;3) 使用特征索引, 一次性查詢所有人臉特征feats 的限定半徑t 鄰域的最近鄰居, 保存到res;4) 構造節點列表nodes, 初始化每個節點的label 為0 到len(feats)–1;5) 根據res 構造邊列表edges, 其中邊的權重為兩個節點的余弦相似度;6) 根據nodes 和edges 完成對無向圖G 的初始化;7) n=0;8) while n

3.1.3 實驗

(1) 實驗環境與數據集: 實驗在CentOS 7 系統,CPU 為Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20 GHz,內存為128 GB 的服務器上進行. 使用LFW[14]和CASIAWebFace[15]數據集的部分數據. 其中LFW 數據據分布很不均勻, 大多數人只有1 張圖像, 所以只選取LFW 中有2 張及以上的數據集. CASIA-WebFace 的圖片比較多,由于實驗室設備的限制, 只選取了一部分數據集, 如表1.

表1 實驗數據集

(2)人臉特征提取: 使用RetinaFace[16]人臉檢測算法對兩個數據集進行數據清洗, 刪除無法檢測到人臉的圖片. 接著使用RetinaFace 進行人臉檢測, 由于有些圖片中可能不止一人出現, 對這些圖片僅選擇中心坐標的人臉作為目標對應其標簽. 為了更好地提取人臉特征, 對RetinaFace 人臉檢測算法得到的人臉5 個關鍵點進行仿射變換擺正人臉位置, 再使用CNN+ArcFace Loss方法[17]提取512 維人臉特征.

(3)實驗結果與分析: 在人臉聚類中, 我們往往會更加在意聚類評價指標中的同質性和準確性, 因為如果某一個人臉的聚簇中出現大量別人的人臉, 人臉聚類結果的應用就會失去它的意義, 所以本文實驗結果中的F-measure 和F_pairwise都是在同質性和準確率大的情況下取它們的最大值.

如表2 所示, 在LFW 數據集的表現上, 4 個算法聚類效果差距不大, 但是Chinese Whisper 的得分最高,并且簇數是最接近真值的, 且經過改進的Chinese Whispers 與原始Chinese Whispers 算法的結果是一樣的, 時間效率卻提高了不少.

表2 在LFW 子集(真實簇數=1680)上的實驗結果對比

但是在CASIA-WebFace 數據集的表現上差距就顯現出來了, CASIA-WebFace 數據集中的圖片相較于LFW 數據集, 同一個人的照片時間跨度更大、造型差異大、模糊度高等, 人臉聚類的難度比LFW 數據集大很多. 如表3 所示, Chinese Whispers 算法的表現最好,兩個平均度量指標得分最高, 且聚類簇數最接近真實簇數, 說明其人臉聚類的魯棒性, 更適應稍復雜的人臉數據, 而且經過改進后的Chinese Whispers 使得其可以應用在大規模的數據集上. 繼續對我們的方法的實驗結果進行詳細分析, 7257 個聚簇中有5015 個孤立點, 這5012 個孤立節點是在圖上沒有鄰接邊的點, 即跟樣本集中的所有樣本的相似度都小于相似度閾值. 這些孤立節點大多是數據集采集時的錯誤標記或是遮擋、模糊等原因無法正確人臉識別. 去掉孤立節點之后, 完整性和成對召回率提高,F-measure 得分0.98,F_pairwise得分0.96. 所以, 將其應用在人臉卡口數據上的聚類效果應該會更好.

表3 在CAISA-WebFace 子集(真實簇數=1727)上的實驗結果對比

3.2 行人共現關系抽取

行人共現關系抽取算法基于前面已有的基于Chinese Whispers 的行人節點識別方法, 對每張臉進行聚類, 將屬于同一人的人臉分配同樣的編號, 即id_label,作為不同行人的身份辨識. 當行人節點識別完成后, 本文涉及到的數據存儲字段如表4 所示. id 表示抓拍到的人臉編號, id_label 是聚類之后的編號, 相同身份的行人的id_label 與id 是一對多的關系. 人臉圖片使用SeaweedFS[18]存儲, 使用fid 存儲圖片鏈接, 極大地減少了存儲空間, 且直接通過http 協議訪問該鏈接, 能夠提高圖片的訪問速度.

表4 存儲字段描述

在文獻計量研究領域中, 共同出現的特征項之間存在著某種關聯, 關聯程度可以使用共現頻次來評估.所以, 在圖像或視頻的社交關系挖掘中, 也是在共現的基礎上發現社交關系的, 大都是統計圖像或視頻關鍵幀中的共現次數. 人臉卡口數據與圖像和視頻數據不同, 共現不是體現在一同出現在一個畫面中, 而是體現在一定時間間隔內被同一個人臉攝像機抓拍到. 當基于人臉卡口的行人共現關系網絡G=(V,E), 關系如公式(4)所示:

其中,support(i,j)是行人i,j共同出現的次數,sup_min是設置的共現關系的最低閾值,Eij=1 表示行人i,j之間有邊連接, 即認為i,j之間有關系. 反之, 則認為i,j之間無邊連接, 即i,j之間無關系. 一般情況下, 我們把只共現一次視為偶然情況, 所以sup_min要大于或等于2.

行人對之間的關聯程度除了用共現頻次來表示以外, 本文引入Apriori 關聯規則算法中置信度概念[19]來計算共現關系的置信度, 如式(5)所示:

其中,confidence(i?j)得到的是i出現, 則j也一同出現的概率, 反映了在i方面, 認為j的重要程度. 我們還可以得到其平均置信度, 如式(6)所示:

其中,confidence(j?i)是式(5) 中i,j互換位置的結果. 使用置信度來體現行人對之間的關聯緊密程度更具有說服力, 比如當行人a, b 分別被拍到了2 次, 且他們也正好共現了2 次, 那么他們共現的置信度就是1;而行人c, d 分別被拍到了10 次和15 次, 共現了3 次,那么他們共現的置信度是0.25. 如果僅根據共現頻次,c 和d 之間的關聯程度要大于a 和b, 但是從現實角度,我們會認為a 和b 的關聯程度要大于c 和d. 所以, 人臉卡口中行人對滿足最小支持度和最小置信度的共現關系, 被認為是強關聯關系, 其中共現關系抽取的詳細步驟如算法2 所示.

算法2. 行人共現關系抽取算法輸入: 人臉卡口數據集D, 卡口列表L, 時間間隔t, 最小支持度sup_min, 最小置信度conf_min輸出: 共現關系結果集合R 1)掃描人臉卡口數據集, 統計每一個ID 出現的總次數, 保存到字典id_to_counts;2) for L_i in L:3) S 為在L_i 被抓拍的人臉集4) 對S 中出現的人臉按照時間戳從小到大排序5) for Sk in S[0:]:6) Sj in [k+1:]:7) if (T_Sj – T_Sk > t): break;8) //在時間間隔內9) if (IDk > IDj): 交換IDk 和IDj 10) R[(IDk, IDj)] +=1//記錄一次共現11) 把R 中記錄的共現次數小于sup_min 的行人對過濾掉;12) for R_i in R:

13) 根據id_to_count 分別計算R_i 中行人對的置信度conf1, conf2;14) if (avg(conf1, conf2)

3.3 實體、關系存儲

選擇Neo4j 作為圖譜的圖數據庫存儲, Neo4j 能夠高效地存儲節點、關系和屬性, 同時, Neo4j 支持Cypher查詢語言, 關系查詢靈活高效, 支持增刪改查功能. 基于人臉卡口數據的行人共現關系圖譜的實體和關系存儲的屬性如表5 所示.

表5 Neo4j 存儲描述

表5 中, 行人節點的id_label 作為唯一性約束,img_url 是該ID 行人人臉圖像, paths 是一個列表, 存儲了該行人的(kakou_id, timestamp), 即行動軌跡. 關系屬性中的conf 是共現置信度, times 是共現頻數.

4 圖譜可視化

根據公開的人臉數據集LFW 和CASIA-WebFace隨機+人為制造了人臉卡口數據集作為樣例, 構建行人共現圖譜. 最后, 采用Web 頁面作為前端展示頁面, 使用D3.js 作為前端展示框架, 借助D3.js 的力學導向圖,將數據以網絡的形式展現. 如圖3 所示, 展示了數據集中部分數據, 生動地反映行人之間的共現關系, 其中節點之間邊的長度取決于共現關系的置信度的大小, 置信度越高, 節點相距就越近, 更能顯示緊密的關系.

圖3 基于人臉卡口數據的行人共現關系圖譜展示界面

5 結論

本文針對偵察團伙犯罪案件時人臉卡口數據應用的局限性以及對人的現實社交關系難以辨認的問題,實現了一種基于人臉卡口數據的行人共現關系圖譜的構建流程. 該流程首先使用Faiss 加速Chinese Whispers算法中初始圖的鄰接邊的構建, 使其能夠完成大規模人臉聚類的任務, 得到人臉卡口數據這一未知人員庫中行人的潛在身份id, 然后再根據人臉卡口記錄挖掘行人的共現關系, 通過共現頻次和置信度來體現關系強度, 最后使用前端框架展示圖譜交互式界面.