潘 明，唐 寧

（中國航天科工集團第二研究院 北京航天長峰科技工業(yè)集團有限公司，北京100854）

0 引 言

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

1 相關(guān)工作

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

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

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

圖1 行人重檢

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

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

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

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

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

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

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

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

2 提取特征

2.1 人體的分割

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

圖3 基于對稱性和非對稱性劃分人體輪廓

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

2.2 MSCR特征檢測

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

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

定義兩個像素點x和y的色彩距離為

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

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

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

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

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

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

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

3 行人重檢

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

3.1 詞典的構(gòu)建

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

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

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

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

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

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

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

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

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

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

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

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

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

倒排索引如圖4所示。

圖4 倒排索引

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

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

3.3 目標檢索

檢索一幅新的目標圖像時步驟如下:

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

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

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

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

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

4 實驗結(jié)果

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

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

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

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

對于檢索速度，我們的衡量標準為平均時間消耗，即每一個待檢測目標圖像重檢過程耗費的時間。將傳統(tǒng)的逐一對比的方式與K取不同值時的快速檢索方法進行時間消耗比較，結(jié)果如表1所示。

圖5 CMC對比

表1 平均時間消耗比較

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

5 結(jié)束語

相比于目前已有的技術(shù)，本文提出的基于MSCR的快速行人重檢方法具備較好的準確性，并且在檢索速度方面有較大的改進，該方法對于應(yīng)用在海量視頻數(shù)據(jù)時具有重要的參考價值，能夠很好的滿足公安業(yè)務(wù)中對于特定目標人員進行快速檢索的需求。在進一步的研究中，希望能引入更加有效的特征描述子，以提高檢索準確性；此外本文方法容易受到行人姿態(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.