視頻中目標(biāo)快速檢測算法

劉 松，王紫一文，魏 東，楊洪臣

（1. 四川警察學(xué)院,四川 瀘州646000；2.深圳市公安局，廣東 深圳 518000；3.中國刑事警察學(xué)院，沈陽 110035）

隨著經(jīng)濟(jì)社會的發(fā)展及科學(xué)技術(shù)的進(jìn)步，傳統(tǒng)的偵查手段及模式逐漸被多警種合成作戰(zhàn)的大偵查模式所取代。要實(shí)現(xiàn)多警種的有力配合、相互支撐，就需要利用好現(xiàn)有科技成果，并創(chuàng)造性地將這些科技成果移植應(yīng)用到公安科技創(chuàng)新改革中來。以技術(shù)作為支撐和保障，才能更好地發(fā)揮不同偵查手段在合成作戰(zhàn)中的作用，激發(fā)大偵查合成作戰(zhàn)的真正威力。

作為合成作戰(zhàn)中的關(guān)鍵一環(huán)，視頻偵查在一定程度上直接關(guān)系到大偵查合成作戰(zhàn)的效果。以人工觀看分析監(jiān)控視頻為主的傳統(tǒng)視頻偵查方式完全不能適應(yīng)大偵查合成作戰(zhàn)模式下對視頻偵查快速高效的要求，將現(xiàn)有技術(shù)成果加以創(chuàng)新改進(jìn)，應(yīng)用于公安工作中解決公安工作實(shí)際需求，這就是本算法探究的出發(fā)點(diǎn)和背景。

1 算法介紹

本算法主要通過固定攝像頭下監(jiān)控視頻變化背景的自適應(yīng)、視頻中多目標(biāo)定位及圖像匹配等算法實(shí)現(xiàn)視頻目標(biāo)快速檢測，幫助偵查人員快速高效地發(fā)現(xiàn)海量視頻信息中與案件目標(biāo)相關(guān)的信息。

2 背景提取算法

通過算法提取視頻實(shí)時(shí)背景的目的在于提取視頻運(yùn)動目標(biāo)。視頻中運(yùn)動目標(biāo)提取算法主要包括光流法、相鄰幀差法及背景差值法。其中光流法算法較為復(fù)雜，且硬件依賴性較高；相鄰幀差法算法簡單，實(shí)時(shí)性強(qiáng)，但是容易在運(yùn)動目標(biāo)提取中產(chǎn)生殘影現(xiàn)象；背景差值法與光流法相比有算法更為簡單、硬件依賴小、實(shí)時(shí)性較高的優(yōu)點(diǎn)，較之相鄰幀差法又不會產(chǎn)生殘影現(xiàn)象，故在運(yùn)動目標(biāo)提取上采用了背景差值法。背景差值法實(shí)現(xiàn)的關(guān)鍵在于背景的提取。為適應(yīng)固定監(jiān)控設(shè)備不同環(huán)境下監(jiān)控視頻目標(biāo)快速檢測的要求，采用背景自適應(yīng)算法實(shí)現(xiàn)背景提取。背景自適應(yīng)算法大致可以分為兩類：1）基于背景建模的背景自適應(yīng)算法；2）基于像素灰度統(tǒng)計(jì)的背景自適應(yīng)算法。

基于背景建模的背景自適應(yīng)算法主要以高斯建模為主，可分為單高斯模型和混合高斯模型，其中單高斯模型較為簡單，但是需要多次迭代才能實(shí)現(xiàn)對簡單背景的刻畫；而混合高斯模型利用多個(gè)不同參數(shù)高斯模型對背景加以刻畫，具有算法復(fù)雜，運(yùn)算量較大的特點(diǎn)?；谙袼鼗叶冉y(tǒng)計(jì)的背景自適應(yīng)算法是通過隨機(jī)抽取一段時(shí)間內(nèi)視頻幀，并對不同像素位置灰度值變化進(jìn)行統(tǒng)計(jì)，選取出現(xiàn)頻次較高的灰度值作為該像素灰度。該方法算法簡單實(shí)時(shí)性較強(qiáng)，故本研究在該類算法基礎(chǔ)上加以改進(jìn)實(shí)現(xiàn)不同環(huán)境下的視頻背景自適應(yīng)。

采用的基于灰度統(tǒng)計(jì)的背景自適應(yīng)算法主要包括背景重構(gòu)和背景自適應(yīng)兩個(gè)部分。背景重構(gòu)是在t0時(shí)刻隨機(jī)選擇視頻中n幀圖像，并將像素點(diǎn)(x,y)每ξ灰度分為一類進(jìn)行背景重構(gòu)，有：

其中，f0i (x, y)為t0時(shí)刻i幀圖像在(x,y)處的灰度值，grayi( x, y)為t0時(shí)刻i幀圖像在(x,y)處經(jīng)過灰度分類后的灰度值。(經(jīng)試驗(yàn)確定ξ=25時(shí)重構(gòu)效果較為理想)?；叶确诸惡髮幀(x,y)像素的灰度值保存在數(shù)組GRAY中，有：

然后將數(shù)組GRAY中出現(xiàn)頻次最高的灰度級grayi( x, y)定義為(x,y)處的灰度值。對較短且背景變化小的視頻，做到背景重構(gòu)就已經(jīng)足夠了，但針對背景變化復(fù)雜的視頻，提取視頻背景就需要實(shí)現(xiàn)視頻背景自適應(yīng)，用到的方法可以參看筆者相關(guān)文章[1]，在此不再贅述。

3 多目標(biāo)定位算法

多目標(biāo)定位算法實(shí)現(xiàn)主要分為圖像優(yōu)化處理及多目標(biāo)定位兩個(gè)步驟。算法流程圖如圖1所示。

多目標(biāo)定位算法具體實(shí)現(xiàn)步驟如下：步驟1：圖像優(yōu)化處理

多目標(biāo)定位算法[2]是在背景自適應(yīng)算法取得較好視頻的背景bg(x,y)的基礎(chǔ)上，運(yùn)用背景差值法得到每幀視頻frame(x,y)差分圖像diff(x,y)，有：

圖1 多目標(biāo)定位流程圖Fig.1 Flow chart for multi-target location

再對差分圖像diff(x,y)設(shè)定閾值threshold進(jìn)行二值化處理得到binary(x,y)，有：

步驟2：多目標(biāo)定位

二值化處理后運(yùn)用形態(tài)學(xué)處理優(yōu)化二值圖像binary(x,y)得到rows*cols數(shù)組mat(x,y)。再用matlab邊緣查找算法bwtraceboundary對mat(x,y)進(jìn)行遍歷得到邊緣像素(x,y)集合T，有：

根據(jù)邊緣像素索引T刻畫的目標(biāo)邊緣查找當(dāng)前目標(biāo)的最小外接矩陣，有：

其中[x1 y1 x2 y2]刻畫了當(dāng)前目標(biāo)的最小外接矩陣。根據(jù)[x1 y1 x2 y2]定義rows*cols的矩陣m，有：

如式（7），將矩陣m與mat進(jìn)行與運(yùn)算后，消除mat中已被檢測目標(biāo)區(qū)域，重復(fù)步驟2進(jìn)行目標(biāo)定位，直到遍歷結(jié)束。

4 圖像匹配算法

視頻中運(yùn)動目標(biāo)主要通過目標(biāo)的紋理和顏色特征進(jìn)行匹配。朱英麗等[4]提出利用運(yùn)動目標(biāo)顏色布局和邊緣直方圖等特征進(jìn)行匹配實(shí)現(xiàn)視頻中目標(biāo)的檢索。顏色布局能很好表現(xiàn)視覺信號的顏色空間分布。通過將RGB圖像映射到Y(jié)CrCb空間并將圖像分割為64塊，并計(jì)算每一塊中像素在（Y,Cr,Cb）三顏色分量的均值，作為該塊的顏色。再進(jìn)一步對64塊均值顏色進(jìn)行DCT變換，選取DCT變換后三組顏色的低頻分量作為圖像的顏色布局描述子。邊緣直方圖是一種對圖像邊緣像素梯度方向進(jìn)行統(tǒng)計(jì)而得到的描述圖像邊緣空間分布的直方圖。邊緣直方圖能較好反映圖像的紋理信息，可以用于圖像間的匹配。

本研究將圖像劃分為16個(gè)不重疊的矩形區(qū)域。對各個(gè)區(qū)域中0°、45°、90°、135°及無方向信息五類邊緣信息進(jìn)行統(tǒng)計(jì)，得出各區(qū)域邊緣直方圖。通過將顏色布局和邊緣直方圖等圖像特征作為圖像匹配的描述子，利用歐式距離進(jìn)行圖像匹配，能夠?qū)崿F(xiàn)視頻中運(yùn)動目標(biāo)的檢索，且結(jié)果較為準(zhǔn)確。感知哈希匹配算法在圖像匹配中運(yùn)用廣泛，效果顯著，常運(yùn)用在圖片搜索應(yīng)用中。感知哈希算法可以分為感知哈希均值算法和pHash算法。這兩種哈希算法的實(shí)現(xiàn)原理都是通過對圖片進(jìn)行處理，去除圖片高頻細(xì)節(jié)信息，通過低頻輪廓信息生成圖片hash值，通過圖片間hash值漢明距離來刻畫圖片相似程度。感知哈希均值算法實(shí)現(xiàn)主要包括三步：

步驟1：尺度歸一化

將待對比的兩幅圖片都?xì)w一化為8×8大小的圖片，既方便了不同大小圖片的比對又去除了圖像高頻信息。

步驟2：圖像二值化

通過計(jì)算8×8圖片image(x,y) 64位像素均值并以之為二值化閾值對圖片進(jìn)行二值化處理得到二值化圖像binary(x,y)，有：

步驟3：計(jì)算圖片hash值和圖片間漢明距離

將步驟2得到的64位二值信息組合在一起就構(gòu)成了圖片的hash值；通過計(jì)算兩張圖片hash值不同位個(gè)數(shù)得到兩張8×8圖片的漢明距離，一般漢明距離小于5可以斷定兩張圖片高度相似，而漢明距離大于10可以斷定兩張圖片完全不同。兩張圖片的二值化圖像如果分別用binary1(x,y)和binary2(x,y)來表示，兩張圖片的漢明距離hammin_distance可用公式(9)加以計(jì)算：

可以看到哈希均值算法是十分簡單的，所以其運(yùn)算速度非?？?，同時(shí)圖片匹配也比較準(zhǔn)確，不失為一種十分有效且好用的圖像匹配算法。當(dāng)然哈希均值算法也存在一些問題，其在圖片匹配上比較死板、僵硬。比如在對圖像進(jìn)行伽馬校正后，圖片的均值發(fā)生改變就會使圖片hash信息發(fā)生較大變化，導(dǎo)致匹配時(shí)漢明距離變大，使相似圖片不能被匹配，發(fā)生漏檢現(xiàn)象。故有了基于DCT處理的pHash算法，pHash算法較哈希均值算法更為健壯，匹配結(jié)果更為精準(zhǔn)，能在一定程度上消除圖片微弱變化的影響。在圖片變化幅度小于25%時(shí)pHash算法效果顯著。pHash算法是在哈希均值算法步驟1之前先將圖片縮小為32×32大小并進(jìn)行DCT處理，選取DCT變換后左上角8×8區(qū)域低頻信息作為處理對象，之后運(yùn)用哈希均值算法步驟2、步驟3對DCT得到的圖像低頻信息進(jìn)行處理。

5 算法實(shí)現(xiàn)及性能分析

5.1 算法實(shí)現(xiàn)

通過背景自適應(yīng)算法實(shí)時(shí)提取視頻背景，通過多目標(biāo)定位算法鎖定背景差值法二值化后提取的運(yùn)動目標(biāo)位置，最后通過圖像匹配算法實(shí)現(xiàn)待檢測目標(biāo)和視頻中運(yùn)動目標(biāo)比對[3]，最終實(shí)現(xiàn)基于背景自適應(yīng)的視頻多目標(biāo)快速檢測。算法具體流程圖見圖2：

在圖像匹配模塊，分別對1.3節(jié)介紹的各類匹配算法加以實(shí)現(xiàn)，并對各個(gè)算法性能做了簡要分析。

5.2 算法性能比較及分析

圖2 算法流程圖Fig.2 Flow chart for veri fi cation of algorithm performance

性能測試實(shí)驗(yàn)是在一臺配置2.3GHz i5處理器，4G內(nèi)存并裝載window7 64位系統(tǒng)和matlab2015a+軟件的筆記本電腦上分別利用不同算法對時(shí)長為15 min 3s的視頻中三個(gè)不同目標(biāo)進(jìn)行檢索，最終得到反映不同算法在匹配精度及運(yùn)行效率上的實(shí)驗(yàn)數(shù)據(jù)。

實(shí)驗(yàn)一 基于顏色布局和邊緣直方圖描述子匹配算法的目標(biāo)檢索實(shí)驗(yàn)（結(jié)果見表1）。實(shí)驗(yàn)表明基于顏色布局和邊緣直方圖描述子特征匹配實(shí)現(xiàn)的目標(biāo)檢索算法能夠匹配并命中檢索目標(biāo)，但該類匹配算法因?yàn)槠ヅ溥^程中對圖像的多色彩通道進(jìn)行了復(fù)雜的運(yùn)算，導(dǎo)致其檢索時(shí)間都超過了1200 s，效率欠佳；同時(shí)，該類匹配算法的匹配精準(zhǔn)度（命中/匹配）在各檢測目標(biāo)的檢測測試上也不是十分理想。

實(shí)驗(yàn)二 基于哈希均值和增強(qiáng)哈希算法的目標(biāo)檢索實(shí)驗(yàn)。從表2可以看出在實(shí)驗(yàn)中，哈希均值算法的命中、匹配及運(yùn)行時(shí)間都較增強(qiáng)哈希算法好。但是在匹配精準(zhǔn)度（命中/匹配）上哈希均值算法不如增強(qiáng)哈希算法。總體來說兩類哈希算法在圖像匹配上性能差距不大。

表1 實(shí)驗(yàn)一性能測試分析表Table 1 Result of experiment 1 by performing one algorithm

表 2 實(shí)驗(yàn)二性能測試分析表Table 2 Result of experiment 2 by performing a/pHash

實(shí)驗(yàn)三 對比表1和表2中的參數(shù)，不難發(fā)現(xiàn)利用哈希算法進(jìn)行圖像匹配時(shí)，無論在執(zhí)行效率還是匹配效果上都較基于顏色布局和邊緣直方圖描述子實(shí)現(xiàn)的匹配算法有較大優(yōu)勢。但哈希算法在圖像匹配精準(zhǔn)度（命中/匹配）上依然有提升的空間?？紤]到基于顏色布局和邊緣直方圖描述子的匹配算法在匹配中利用到了圖像更多的色彩信息，如果在哈希算法初步判定圖像相似后，再利用基于顏色布局和邊緣直方圖描述子的匹配算法進(jìn)一步對匹配目標(biāo)進(jìn)行相似度度量，可能會提升算法的圖像匹配精準(zhǔn)度（命中/匹配）。為驗(yàn)證這一點(diǎn)，進(jìn)行了實(shí)驗(yàn)三，結(jié)合顏色布局、邊緣直方圖描述子的哈希匹配算法目標(biāo)檢索實(shí)驗(yàn)，匹配算法的流程圖見圖3，結(jié)果見表3。

圖3 實(shí)驗(yàn)三匹配算法流程圖Fig.3 Flow chart of experiment 3 from new matching algorithm

表3 實(shí)驗(yàn)三性能測試分析表Table 3 Result of experiment 3 from new matching algorithm

可以看到表3中對不同目標(biāo)匹配耗時(shí)均在200 s左右，匹配效率較高，較哈希匹配算法無較大劣勢；但改進(jìn)后的算法對不同匹配目標(biāo)匹配精準(zhǔn)度（命中/匹配）均提升到了100%，較傳統(tǒng)的圖像匹配算法有了較大的提升。

6 總結(jié)

通過對視頻中多目標(biāo)快速檢測算法探究，本文發(fā)現(xiàn)將哈希圖像匹配算法和基于顏色布局、邊緣直方圖描述子的匹配算法相結(jié)合后用于視頻中目標(biāo)檢測，無論在運(yùn)行效率還是在檢測精準(zhǔn)度上都有較好的效果，較傳統(tǒng)的圖像匹配算法有了較大的性能提升。