基于MSCR的快速行人重檢方法

潘 明，唐 寧

（中國(guó)航天科工集團(tuán)第二研究院 北京航天長(zhǎng)峰科技工業(yè)集團(tuán)有限公司，北京100854）

0 引 言

近年來(lái)，伴隨著視頻監(jiān)控系統(tǒng)建設(shè)規(guī)模的不斷擴(kuò)大，人們對(duì)視頻監(jiān)控系統(tǒng)的高效應(yīng)用和管理也提出了越來(lái)越高的要求。智能化的視頻監(jiān)控系統(tǒng)利用計(jì)算機(jī)替代人工來(lái)對(duì)監(jiān)控視頻數(shù)據(jù)進(jìn)行智能處理，將人們感興趣的關(guān)鍵信息從海量的視頻數(shù)據(jù)中快速自動(dòng)提取出來(lái)。作為智能化視頻監(jiān)控的一個(gè)熱門主題，行人重檢 （person re－identification）實(shí)現(xiàn)從多個(gè)非重疊性的攝像頭所獲取的不同圖像中檢索出包含某個(gè)特定目標(biāo)行人的圖像。行人重檢在公安業(yè)務(wù)能夠起到十分重要作用，當(dāng)視頻監(jiān)控中出現(xiàn)值得公安關(guān)注的目標(biāo)行人時(shí)，希望在其他攝像頭中對(duì)該目標(biāo)行人進(jìn)行檢索，以了解該特定目標(biāo)行人是否在其他攝像頭也出現(xiàn)過(guò)。這一點(diǎn)可以輔助公安機(jī)關(guān)確定嫌疑人的行走動(dòng)向，便于抓捕破案，也可用作案情記錄，在公安業(yè)務(wù)中能夠起到十分重要的作用。

1 相關(guān)工作

行人重檢的主要問(wèn)題是如何更好地克服光照、視角、姿態(tài)、背景、遮擋等因素的變化，計(jì)算兩個(gè)圖像中行人的相似度，以判定是否為同一個(gè)人，如圖1所示。

要從不同攝像頭視頻的大量候選圖像中搜索包含目標(biāo)行人的圖像，以下兩點(diǎn)比較關(guān)鍵:第一，提取候選圖像以及目標(biāo)圖像中的行人特征，并對(duì)得到的特征進(jìn)行表示和描述；第二，計(jì)算候選圖像和目標(biāo)人員圖像的相似度，以判斷候選圖像是否包含目標(biāo)圖像中的行人[1]。

目前，大部分研究都是從第一點(diǎn)入手，在人員外觀上選取一種比較有效可靠的特征描述，文獻(xiàn)[2]為了消除由于人數(shù)增加時(shí)行人之間外觀的模糊性，提取了一組基于顏色、紋理和邊緣的高維融合特征，并采用偏最小二乘法（partial least squares，PLS）對(duì)特征空間做降維處理。文獻(xiàn)[3]提出了旋轉(zhuǎn)不變快速特征 （rotation－invariant fast features，RIFF）。文獻(xiàn)[4]利用Gabor特征和局部二次模式（local binary pattern，LBP）構(gòu)建協(xié)方差描述符。文獻(xiàn)[5]利用行人外觀整體和局部統(tǒng)計(jì)特征描述的互補(bǔ)。

圖1 行人重檢

也有一些研究從行人檢索的第二步，也就是從計(jì)算相似度上下功夫，在文獻(xiàn)[6]中利用周圍行人的視覺(jué)環(huán)境知識(shí)將人從時(shí)間和空間上關(guān)聯(lián)成組提出了一種基于行人組的匹配算法，很好的克服了光照和視角的變化。文獻(xiàn)[7]通過(guò)學(xué)習(xí)一種最佳相似度度量以在量化和區(qū)分特征時(shí)更可能找到正確的匹配，提出了一種相對(duì)距離比較模型 （relative distance comparison，RDC），此模型通過(guò)軟判別方式增大相對(duì)距離更小的圖像匹配對(duì)正確匹配的可能性。

這些研究從在行人重檢性能方面取得了較好的效果，但是卻忽略了檢索的效率問(wèn)題，他們?cè)谶M(jìn)行特征匹配時(shí)，大多采用目標(biāo)圖像和數(shù)據(jù)庫(kù)的候選圖像逐一比較的方式，固然這樣準(zhǔn)確性較高，但是在實(shí)際應(yīng)用中，每個(gè)視頻中有大量的圖像幀，每一幀中也有多個(gè)行人，數(shù)據(jù)庫(kù)容量很大，這就導(dǎo)致在目標(biāo)匹配時(shí)計(jì)算量大，匹配時(shí)間過(guò)長(zhǎng)，檢索效率低下。

當(dāng)行人重檢用于公安行業(yè)時(shí)，檢索的速度十分重要，公安機(jī)關(guān)希望能在最短的時(shí)間內(nèi)獲取關(guān)注目標(biāo)的行動(dòng)走向。因此本文從行人重檢的速度方面入手，在盡量保證檢索準(zhǔn)確性的前提下提高檢索效率，提出了一種基于MSCR的快速行人重檢方法，并在數(shù)據(jù)庫(kù)i－LIDS中進(jìn)行實(shí)驗(yàn)驗(yàn)證了該方法在檢索速度方面的優(yōu)勢(shì)，方法具體流程如圖2所示。

圖2 基于MSCR的快速行人重檢流程

（1）提取特征。利用對(duì)稱性和非對(duì)稱性的感知原則分割人體為四部分[8]，對(duì)于每一部分利用MSCR檢測(cè)局部特征區(qū)域；

（2）構(gòu)建詞典。以所有候選圖像中人體的每一部分為一組，基于詞袋模型，對(duì)各組中所提取出來(lái)的MSCR特征描述子分別進(jìn)行K－means聚類，并標(biāo)記每幅圖像所映射的聚類中心；

（3）構(gòu)建倒排索引表。其中關(guān)鍵詞為各組的所有聚類中心，索引值為映射到相應(yīng)聚類中心的圖像及出現(xiàn)次數(shù)；

（4）目標(biāo)檢索。根據(jù)目標(biāo)圖像所有描述子所映射的聚類中心查詢倒排索引表，統(tǒng)計(jì)候選圖像出現(xiàn)次數(shù)之和，按照其大小確定檢索結(jié)果。

2 提取特征

2.1 人體的分割

借鑒文獻(xiàn)[8]中的方法，依據(jù)對(duì)稱性和非對(duì)稱性的感知原則將人體分為4個(gè)顯著的部分。首先計(jì)算兩條非對(duì)稱性的水平軸線將人體分為3個(gè)部分，分別為頭、軀干和腿，濾除頭這一部分，因?yàn)槠浒男畔?nèi)容很少；然后對(duì)于軀干和腿，再分別計(jì)算一條對(duì)稱性的豎直軸線，如圖3所示，水平軸線iHL和iTL為非對(duì)稱軸，豎直軸線jLR1和jLR2為對(duì)稱軸。

圖3 基于對(duì)稱性和非對(duì)稱性劃分人體輪廓

這種人體劃分方法主要依據(jù)衣服的視覺(jué)和位置信息，對(duì)于姿態(tài)和視角的變化具有很好的魯棒性。

2.2 MSCR特征檢測(cè)

J.Matas等[9]提出一種灰度圖像中的最大穩(wěn)定極值區(qū)域 （maximally stable extremal regions，MSER）。MSER即當(dāng)使用不同的灰度閾值對(duì)圖像進(jìn)行二值化劃分區(qū)域時(shí)，區(qū)域面積不隨閾值的改變而改變，或者區(qū)域面積變化緩慢達(dá)到局部極小值的區(qū)域。MSER具有良好的仿射不變性和穩(wěn)定性。Per－Erik Forssen[10]將其推廣到彩色圖像中，提出了最大 穩(wěn) 定 色 彩 區(qū) 域 （maximally stable color regions，MSCR）。與MSER方法相比，MSCR能檢測(cè)出的區(qū)域更多，而且可重現(xiàn)性和可匹配性更好。

MSCR采用凝聚層次聚類 （agglomerative clustering）算法對(duì)圖像像素聚類，并以此檢測(cè)特征區(qū)域，聚類的依據(jù)主要為顏色的相似度。

定義兩個(gè)像素點(diǎn)x和y的色彩距離為

式中μk（x）為k個(gè)顏色通道的顏色分量值，k＝1，2，3。

類似于MSER算法里的閾值圖像，MSCR算法中定義標(biāo)簽圖像Et，其中t為時(shí)間步長(zhǎng)且t∈[0，T]。Et標(biāo)簽圖像中包含多個(gè)標(biāo)簽，每個(gè)獨(dú)立的標(biāo)簽都代表一個(gè)連通的區(qū)域R Ω，區(qū)域中任何兩個(gè)鄰接像素點(diǎn)之間的色彩距離 （1）都小于該時(shí)間步長(zhǎng)的距離閾值dthr（t）。

標(biāo)簽圖像E0為全零點(diǎn)，Et依據(jù)色彩距離小于dthr（t）的所有像素對(duì)分配新區(qū)域從而得到Et＋1。此時(shí)如果像素對(duì)中一個(gè)已經(jīng)屬于某個(gè)區(qū)域了，那另一個(gè)沒(méi)有指派的像素被加到這個(gè)區(qū)域中，如果兩個(gè)像素都已經(jīng)被指派，那么將它們所屬的區(qū)域合并。

距離閾值dthr（t）隨著時(shí)間步長(zhǎng)的變化而變化，在聚類過(guò)程中如果某些區(qū)域的面積不變或者變化很小，這些區(qū)域則被定義為穩(wěn)定區(qū)域。

上面所述方法會(huì)產(chǎn)生大量的區(qū)域，需要做刪減處理。記m＝dt－dt－1，其中dt表示時(shí)間步長(zhǎng)為t時(shí)設(shè)置的距離閾值，保留m＞mmin（典型設(shè)為0.003）的區(qū)域。接下來(lái)再刪減那些面積比較小的不穩(wěn)定區(qū)域，只保留面積a＞amin（典型設(shè)為60）的區(qū)域。

最后，對(duì)檢測(cè)到的區(qū)域利用協(xié)方差矩陣進(jìn)行橢圓調(diào)整，并丟棄掉短軸小于1.5的橢圓，以方便計(jì)算。

對(duì)于MSCR檢測(cè)到的區(qū)域，利用HSV顏色空間構(gòu)建直方圖，其中H、S、V這3個(gè)通道量化級(jí)數(shù)分別取16、8、8，經(jīng)過(guò)歸一化處理后構(gòu)成32維向量，再串聯(lián)區(qū)域中心位置，將這個(gè)34維向量作為區(qū)域特征描述子。

3 行人重檢

在檢索圖像時(shí)如果通過(guò)直接利用兩幅圖像的MSCR特征描述子來(lái)計(jì)算距離，以判定其相似度，會(huì)有較高的檢索準(zhǔn)確性，但遇到數(shù)據(jù)庫(kù)中圖像過(guò)多的情況時(shí)勢(shì)必會(huì)增加算法的時(shí)間復(fù)雜度。受到Bag of words模型和倒排索引的啟發(fā)，我們采用K－means聚類算法構(gòu)建基于特征描述子聚類中心的視覺(jué)詞匯詞典和基于聚類中心的倒排索引，在檢索目標(biāo)圖像的時(shí)候，利用目標(biāo)圖像的每個(gè)特征描述子所映射的聚類中心去查詢倒排索引表，并利用候選圖像出現(xiàn)次數(shù)之和對(duì)匹配結(jié)果進(jìn)行排序。

3.1 詞典的構(gòu)建

詞袋模型 （Bag of words）是信息檢索領(lǐng)域常用的文檔表示方法。在信息檢索中，BOW模型假定對(duì)于一個(gè)文檔，忽略它的單詞順序和語(yǔ)法、句法等要素，將其僅僅看作是若干個(gè)詞匯的集合，文檔中每個(gè)單詞的出現(xiàn)都是獨(dú)立的，不依賴于其它單詞是否出現(xiàn)。BOW也被應(yīng)用于圖像處理領(lǐng)域中[11，12]。本文基于詞袋模型構(gòu)建視覺(jué)詞匯詞典。

經(jīng)過(guò)2.1節(jié)的對(duì)稱性和非對(duì)稱性分割，把人體分為4個(gè)部分，分別為左軀干，右軀干，左腿和右腿。從圖像的4個(gè)部分分別提取MSCR特征，然后把所有圖像中位于相同身體部分的MSCR特征描述子歸為一組，對(duì)于這四組描述子分別進(jìn)行K－means聚類，并將得到的4K個(gè)聚類中心Cij（i＝1，2，3，4，分別代表左軀干，右軀干，左腿和右腿4個(gè)組；j＝1，2，…，K）作為視覺(jué)詞匯。聚類流程如下（以第一組為例）:

（1）從第一組內(nèi)選取K個(gè)描述子向量作為初始聚類中心，C11，…，C1j，…，C1K；

（2）計(jì)算第一組內(nèi)所有描述子向量Fu與當(dāng)前聚類中心的距離duj；

（3）對(duì)于所有的Fu，若duM＝min1≤j≤K（duj），則將Fu歸入到第M個(gè)聚類；

（4）計(jì)算各個(gè)聚類中所有描述子的均值，并將計(jì)算結(jié)果作為新的聚類中心；

（5）新聚類中心和舊聚類中心的標(biāo)準(zhǔn)測(cè)度函數(shù)是否收斂，若是則結(jié)束，若否則返回第2步。

這樣，迭代結(jié)束后的所得到的聚類中心便是最終結(jié)果。在選取初始聚類中心時(shí)隨機(jī)選取，但保證每個(gè)初始聚類中心來(lái)自不同的圖像。計(jì)算特征描述子距離時(shí)采用式 （2）作為距離函數(shù)

其中dH為描述子中32維HSV直方圖向量的歐氏距離；dC為區(qū)域中心位置的歐氏距離；β∈[0，1]，在實(shí)驗(yàn)中取0.4。

這樣分別對(duì)四組描述子進(jìn)行聚類便得到總4K個(gè)聚類中心，也就是詞典里的視覺(jué)詞匯。至此，所有圖像的每個(gè)MSCR特征描述子都被映射到其所在組的一個(gè)聚類中心。用i和j標(biāo)記MSCR特征描述子，表示該描述子被映射到第i組的第j個(gè)聚類中心Cij。

3.2 倒排索引的構(gòu)建

倒排索引 （inverted index），也稱為反向索引，是文檔檢索系統(tǒng)的一種數(shù)據(jù)結(jié)構(gòu)，不同于正向索引，倒排索引利用關(guān)鍵詞來(lái)查找其位置信息。

在本文的方案中，我們將第3.1節(jié)中所得到的視覺(jué)詞匯，也就是4K個(gè)聚類中心Cij作為關(guān)鍵詞來(lái)構(gòu)建倒排索引表，關(guān)鍵詞索引的內(nèi)容則為存在MSCR特征描述子映射到該聚類中心的圖像編號(hào)。

倒排索引如圖4所示。

圖4 倒排索引

建立詞典過(guò)后圖像的所有MSCR特征描述子都被標(biāo)記了i和j，對(duì)應(yīng)于聚類中心Cij，那么在構(gòu)建倒排索引表時(shí)，就把該圖像的編號(hào)加入到關(guān)鍵詞Cij的索引列表中。由于圖像可能存在多個(gè)MSCR特征描述子被映射到同一個(gè)聚類中心，因此還需要在索引列表中加上出現(xiàn)次數(shù)的信息，如圖4中方括號(hào)內(nèi)的數(shù)字所示。

這樣遍歷所有圖像的描述子標(biāo)記，并將圖像編號(hào)及其出現(xiàn)次數(shù)加入到相應(yīng)關(guān)鍵詞的索引列表中，就建好了整個(gè)聚類中心倒排索引表。

3.3 目標(biāo)檢索

檢索一幅新的目標(biāo)圖像時(shí)步驟如下:

（1）按照第2章的步驟分割人體，檢測(cè)各個(gè)MSCR特征區(qū)域，提取區(qū)域特征描述子；

（2）將目標(biāo)圖像中的MSCR特征描述子與該組 （依據(jù)MSCR所處的身體分割部分）的各個(gè)聚類中心計(jì)算距離，找出距離最小者并將描述子放入該聚類里，通過(guò)查詢倒排索引獲取該聚類中心索引值里所記錄的圖像編號(hào)及出現(xiàn)次數(shù)信息；

（3）對(duì)目標(biāo)圖像中的所有描述子都執(zhí)行步驟2，并將查詢的具有相同圖像編號(hào)的出現(xiàn)次數(shù)相加；

（4）設(shè)置閾值丟棄出現(xiàn)次數(shù)之和較小的圖像編號(hào)，最后將圖像編號(hào)按照出現(xiàn)次數(shù)之和從大到小排序。

出現(xiàn)次數(shù)之和越大表示該圖像中的行人與目標(biāo)圖像的行人越相似。

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

給出了本文方法與文獻(xiàn)[8]中的SDALF方法在數(shù)據(jù)庫(kù)i－LIDS上的實(shí)驗(yàn)結(jié)果對(duì)比。實(shí)驗(yàn)環(huán)境為普通PC，Intel（R）Core（TM）2Duo，2.99GHz處理器芯片，4.00G內(nèi)存，Windows7系統(tǒng) （32位）。

i－LIDS數(shù)據(jù)庫(kù)總共包含119個(gè)人的476幅圖像，是在繁忙時(shí)間的機(jī)場(chǎng)大廳利用多個(gè)攝像頭獲取的數(shù)據(jù)，都規(guī)范化到128×64像素。數(shù)據(jù)庫(kù)中的圖像存在較大的光照變化和遮擋情況。我們分別提取每幅圖像作為目標(biāo)圖像進(jìn)行重檢實(shí)驗(yàn)。

采用CMC （cumulative matching characteristic）曲線測(cè)試準(zhǔn)確性，CMC曲線是指累積匹配曲線，表示在前n個(gè)匹配結(jié)果中存在正確結(jié)果的概率，當(dāng)n＝1時(shí)表示最佳匹配結(jié)果即為正確結(jié)果的概率。我們將SDALF方法和本文方法中K取不同值時(shí)進(jìn)行CMC對(duì)比，結(jié)果如圖5所示。

從圖5可以看出，本文方法在準(zhǔn)確性上略低于SDALF方法，隨著K值的增大，準(zhǔn)確性會(huì)略微下降，但是下降幅度不大，可以滿足性能需求。

對(duì)于檢索速度，我們的衡量標(biāo)準(zhǔn)為平均時(shí)間消耗，即每一個(gè)待檢測(cè)目標(biāo)圖像重檢過(guò)程耗費(fèi)的時(shí)間。將傳統(tǒng)的逐一對(duì)比的方式與K取不同值時(shí)的快速檢索方法進(jìn)行時(shí)間消耗比較，結(jié)果如表1所示。

圖5 CMC對(duì)比

表1 平均時(shí)間消耗比較

從表1可以看出，隨著K值的增大平均時(shí)間消耗有少量的增加，但是利用本文方法進(jìn)行加速后重檢的平均時(shí)間消耗比以往方法中用目標(biāo)圖像與數(shù)據(jù)庫(kù)中候選圖像逐一比對(duì)的方法低了一個(gè)數(shù)量級(jí)，大大加快了檢索速度。

5 結(jié)束語(yǔ)

相比于目前已有的技術(shù)，本文提出的基于MSCR的快速行人重檢方法具備較好的準(zhǔn)確性，并且在檢索速度方面有較大的改進(jìn)，該方法對(duì)于應(yīng)用在海量視頻數(shù)據(jù)時(shí)具有重要的參考價(jià)值，能夠很好的滿足公安業(yè)務(wù)中對(duì)于特定目標(biāo)人員進(jìn)行快速檢索的需求。在進(jìn)一步的研究中，希望能引入更加有效的特征描述子，以提高檢索準(zhǔn)確性；此外本文方法容易受到行人姿態(tài)變化的影響，還需要尋求更好的解決方法以提高魯棒性。

[1]Zheng Weishi，Gong Shaogang，Xiang Tao.Re－identification by relative distance comparison[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35 （3）:653－668.

[2]Schwartz W R，Davis L S.Learning discriminative appearancebased models using partial least squares[C]／／Rio de Janiero:XXII Brazilian Symposium on Computer Graphics and Image Processing，2009:322－329.

[3]Gabriel Takacs，Vijay Chandrasekhar，Sam Tsai，et al.Unified real－time tracking and recognition with rotation－invariant fast features[C]／／San Francisco，CA:IEEE Conference on Computer Vision and Pattern Recognition，2010:934－941.

[4]Zhang Ying，Li Shutao.Gabor－LBP based region covariance descriptor for person re－identification[C]／／Hefei，Anhui:Sixth International Conference on Image and Graphics，2011:368－371.

[5]Bazzani L，Cristani M，Perina A，et al.Multiple－shot person re－identification by HPE signature[C]／／Istanbul:20th International Conference on Pattern Recognition，2012:1413－1416.

[6]Zheng Weishi，Gong Shaogang，Xiang Tao.Associating groups of people[C]／／London:British Machine Vision Conference，2009:1－23.

[7]Markus Enzweiler，Angela Eigenstetter，Bernt Schiele，Dariu M Gavrila.Multi－cue pedestrian classification with partial occlusion handling[C]／／San Francisco，CA:IEEE Conference on Computer Vision and Pattern Recognition，2010:990－997.

[8]Farenzena M，Bazzani L，Perina A，et al.Person re－identification by symmetry－driven accumulation of local features[C]／／San Francisco，CA:IEEE Conference on Computer Vision and Pattern Recognition，2010:2360－2367.

[9]Matas J，Chum O.Robust wide baseline stereo from maximally stable extremal regions[C]／／London:British Machine Vision Conference，2002:384－396.

[10]Forssen P E.Maximally stable colour regions for recognition and matching[C]／／Minneapolis:IEEE Conference on Computer Vision and Pattern Recognition，2007:1－8.

[11]Wu L，Hoi S C，Yu N.Semantics－preserving bag－of－words models and applications[J].IEEE Transactions on Image Processing，2010，19 （7）:1908－1920.

[12]Kobayashi T，Otsu N.Bag of hierarchical co－occurrence features for image classification[C]／／Istanbul:20th International Conference on Pattern Recognition，2010:3882－3885.