一種基于幀差分法與快速圖分割相結(jié)合的運動目標檢測方法

陳　佳，朱長仁，錢智明

（1.國防科學技術(shù)大學 電子科學與工程學院 ATR重點實驗室，湖南 長沙　410073；2.武警福建總隊直屬支隊，福建 福州　350001）

?

一種基于幀差分法與快速圖分割相結(jié)合的運動目標檢測方法

陳佳1，2，朱長仁1，錢智明1

（1.國防科學技術(shù)大學 電子科學與工程學院 ATR重點實驗室，湖南 長沙410073；2.武警福建總隊直屬支隊，福建 福州350001）

摘要：針對在處理復雜場景情況時，幀差分法在預(yù)處理后獲取的目標區(qū)域往往會空洞化或者分裂成多個互不相連的部分，計算機難以實時判斷多個部分是否同屬于一個目標，為此，提出一種基于三幀差分法與快速圖分割相結(jié)合的運動目標檢測方法。首先對序列圖像做三幀差分運算及基于圖的快速分割；然后通過定義融合判定規(guī)則，將幀差分結(jié)果同圖像分割的區(qū)域塊進行互相補充和約束；再對符合判定規(guī)則的子區(qū)域塊進行合并，最終精確提取出運動目標的位置及輪廓。實驗結(jié)果表明該方法能夠有效提高目標檢測的完整性。

關(guān)鍵詞：目標檢測；幀差分；圖像分割；最小生成樹；視頻監(jiān)控

0　引言

運動目標檢測一直是視覺應(yīng)用視覺領(lǐng)域一個重要的研究課題，無論在軍用還是民用領(lǐng)域都有著廣泛的應(yīng)用[1]，盡管不同的運動目標檢測算法已經(jīng)廣泛地應(yīng)用于多個行業(yè)，但其仍然存在各種不足，其精確性和有效性還在不斷改進和完善之中。常用的運動目標檢測方法有光流法、背景減除法、幀差分法等[2]。光流法的檢測效果比較好，但計算復雜度高，對系統(tǒng)硬件要求比較高，常用于對錄制后的視頻進行分析。背景減除法通過對視頻背景預(yù)先建模，在對運動目標進行檢測時，采用預(yù)存的背景模版減去當前幀的方法，從而提取出運動目標，但該方法對背景更新算法提出了較高的要求，如背景變化較大則難以達到預(yù)期效果。幀差分法計算簡單、實時性高，在實際應(yīng)用中實現(xiàn)起來最為便捷，但是其往往提取出的目標輪廓精確性及穩(wěn)定性不夠，難以達到目標檢測要求。

早在2004年，文獻[3]就針對道路上的車輛識別提出了把幀差分同彩色圖像分割相結(jié)合的運動目標提取方法，該方法采用聚類分割并通過設(shè)立一個閾值對分割后的子區(qū)域進行合并，最終形成完整的目標輪廓，但是該方法無法確保子分割區(qū)域能夠剛好合并成完整的目標圖像，且計算量大、穩(wěn)定性不高。文獻[4]提出了把三幀差分法同圖像邊緣檢測相結(jié)合來提取運動目標的方法，但是邊緣檢測往往得到的是不連續(xù)的邊緣，甚至出現(xiàn)虛假邊緣，給最終檢測結(jié)果帶來不確定性。文獻[5]提出了基于幀差法與不變矩特征相結(jié)合的運動目標檢測方法，但是該方法要求首先定義擬跟蹤的目標類型并提取其不變矩特征，在復雜情況下難以對未知目標進行檢測。文獻[6]提出了幀差分法同光流法相結(jié)合的運動目標檢測算法，但是對于重疊目標處理能力不足。文獻[7]通過設(shè)定一個融合規(guī)則，度量幀差分圖上每個目標區(qū)域之間的距離、運動方向、速度等參數(shù)，進而判定多個分裂區(qū)域是否同屬于一個獨立目標，但是該方法計算復雜且建立在長時域分析的基礎(chǔ)上。

盡管有各種方法試圖解決上述問題，然而，迄今為止，基于幀差分同區(qū)域分割相結(jié)合的運動目標檢測方法及其研究論述一直比較少見，主要原因有兩點：一是圖像區(qū)域分割方法理論及研究雖然豐富，但是絕大部分方法都是針對特定情況下解決特定的問題，沒有一個通用的準則，分割精度越高，硬件系統(tǒng)的計算開銷越大；二是大多數(shù)分割方法僅僅從圖像的顏色、紋理相似性出發(fā)，或者結(jié)合局部區(qū)域特征來考慮問題，缺少基于人的視覺、理解、心理認知等因素，導致機器判斷的分割區(qū)域往往同人的肉眼判斷有較大的差異。

針對幀差分法的不足之處，本文提出了一種基于三幀差分法與基于圖的快速分割相結(jié)合的運動目標檢測方法。在對目標進行檢測時，可以有效地提高檢測結(jié)果的完整性。

1　基于幀差分法的運動目標檢測方法

幀差分法（Frame?difference）是一種最簡單的運動目標檢測方法，它能快速地發(fā)現(xiàn)并提取出運動目標所在區(qū)域，其原理介紹如下。

1.1兩幀差分法

兩幀差分法的原理如下：在視頻圖像序列中任選取連續(xù)的兩幀圖像，將當前幀圖像表示為Fk(x,y)，(x,y)表示圖像上點的橫坐標與縱坐標，前一幀圖像表示為Fk-1(x,y)。首先計算當前幀與前一幀的差分圖像，其公式為：

式中FD(x,y)為得到的目標區(qū)域的變化量，再通過簡單的數(shù)學形態(tài)學開閉運算使得運動目標區(qū)域連續(xù)，同時去掉背景中的噪聲，最后選取合適的閾值T，對結(jié)果圖像進行二值化，其公式為：

1.2三幀差分法

三幀差分算法（Three Frame Difference）是一種在兩幀差分方法上改進的算法，其原理是利用連續(xù)三幀圖像前后兩兩相減，再把所得的兩幅幀差分結(jié)果做邏輯與運算，最后再通過形態(tài)學運算去噪并進行二值化。下面分別用Fk-1(x,y),Fk(x,y),Fk+1(x,y)表示連續(xù)的三幀圖像，其原理用公式表示如下：

1.3幀差分法的不足之處

三幀差分法得到的目標檢測區(qū)域圖，如圖1所示。可以看到，在三幀差分法中，預(yù)處理后的圖片目標區(qū)域被分成了多個互不連通的區(qū)域，在進行實時目標檢測時，計算機難以判斷多個區(qū)域是否同屬于一個目標。

圖1　序列圖像三幀差分結(jié)果

無論是兩幀差分法還是三幀差分法，在實際應(yīng)用中都存在不足之處：兩幀差分法得到的目標輪廓往往大于目標的真實輪廓，運動目標速度過快或過慢時，會存在重影或空洞現(xiàn)象；三幀差分法通常能夠比二幀差分法更精確地得到運動目標的位置，但是在目標速度過慢或目標內(nèi)部顏色紋理比較平均的情況下，其提取出來的輪廓區(qū)域仍然會空洞化并割裂為多個互不相連的部分，為圖像的后續(xù)處理增加了難度。針對此，提出了基于圖像區(qū)域分割與幀差分結(jié)果相結(jié)合的辦法（詳見第4節(jié)內(nèi)容），進行目標完整性的有效判斷。

2　基于圖理論的圖像快速分割方法

2.1圖像分割介紹

圖像分割[1]是圖像處理領(lǐng)域和計算機視覺中的一個基本而關(guān)鍵的問題，它是將圖像分成各具特性的區(qū)域并將人們感興趣的目標（或運動目標）提取出來的過程，可為后續(xù)的分析、理解、分類、跟蹤、識別、處理等提供依據(jù)。

圖像分割的形式多種多樣，有時需要將一幅圖像分割成一個個可識別的目標，類似于人對圖像的感覺一樣，而有時需要將它劃分成若干具有某種一致性的區(qū)域，如色彩的一致性，紋理的一致性等，作為底層視覺處理的一部分。實際對圖像分割時，圖像的哪些部分重要，人們又對哪些部分感興趣，需要根據(jù)具體的應(yīng)用而定。

圖像分割方法[8]大致可以劃分為三個類別：基于特征空間（Feature?space based）的方法、基于圖像空間（Im?age?domainbased）的方法以及基于物理特征（Physics based）的方法，每個類別可以繼續(xù)細分。本文主要介紹基于圖理論的快速圖像分割方法。

2.2基于圖劃分理論的圖像分割方法

基于圖理論的分割算法近年來發(fā)展很快[9]，特別在實際應(yīng)用中，無論在靈活性上還是計算復雜度上都不斷改善，顯示出越來越大的適應(yīng)性?；趫D劃分理論的圖像分割方法使用加權(quán)圖G(V,E)，其中V為圖的有限節(jié)點Vi的集合，E為有限邊Ei的集合，Eij表示具體連接兩個節(jié)點的邊，Wij表示邊的屬性（邊上的權(quán)重），即對應(yīng)像素之間的差別或相似性（顏色、強度等）。圖像到圖的映射，如圖2所示。

圖2　圖像到圖的映射

在把圖像映射到圖之后，可以把圖論中很多成熟的理論和數(shù)學工具應(yīng)用在圖像分割上，比如基于最小生成樹（MST?based）、最小割/最大流（MinimumCut/Maximum Flow）、歸一化切割（Normalized Cut）、圖譜（Spectral Graph）以及能量最小化的理論。單從使用理論方法的角度看，可以將基于圖劃分理論的分割方法分為基于最小生成樹方法、最小割/最大流方法、譜方法等。

2.2.1最小生成樹方法

最小生成樹法是通過計算圖像中的最小生成樹來尋找差異最小的連通區(qū)域的分割算法。該算法將整幅圖像按相鄰邊的像素差生成一棵MST，再用動態(tài)規(guī)劃的方法將MST劃分成像素值較為均一的幾部分。最小生成樹的實現(xiàn)算法通常有Kruskal算法、Prim算法、Boruv?ka算法以及混合算法等。

2.2.2基于圖理論的快速分割方法

基于圖的快速分割方法（Efficient Graphic based Segment）是Felzenszwalb P F于2004年提出的[10]，屬于最小生成樹方法之一。該算法優(yōu)點在于既具有超像素分割的精確性，分割時不僅能夠區(qū)分同質(zhì)區(qū)域，比如顏色、紋理等，又能夠依據(jù)人的視覺感官原理，對中間擁有平緩過渡部分的兩種顏色作出歸一化劃分的判斷。該算法的原理為：設(shè)帶權(quán)圖G(V,E)，圖G中生成樹T上的權(quán)重和為ω(T)，公式如下：

式中：ω(T)最小生成樹為圖G的最小生成樹。若C是分類集森林中的任一集合，其對應(yīng)的最小生成樹記為MST（C，E），則集合C的內(nèi)部差異（Internal Difference，Int）被定義為最小生成樹中最大的權(quán)值，即：

集合C1,C2之間的差異（Difference，Dif）為連接這兩個集合邊的最小權(quán)重，即：

為了定量描述且評價兩個鄰域間是否存在邊界，該算法定義了區(qū)域比較謂詞D（Region Comparison Predi?cate，D）這個概念。D通過對區(qū)域內(nèi)部差異和區(qū)域間差異進行比較，使得最終的分割結(jié)果能夠自適應(yīng)圖像數(shù)據(jù)的局部特征。若Dif（C1，C2）大于Int（C1），Int（C2）中的任何一個，則認為C1,C2之間差異較大，應(yīng)將C1,C2對應(yīng)的圖像區(qū)域視為不同區(qū)域；否則，應(yīng)將C1,C2對應(yīng)的圖像區(qū)域合并。

為控制判決門限，即Dif（C1，C2）與Int（C1），Int（C2）到底差別在多大量時，才認為是區(qū)域間存在著明顯的差異，該方法引入了一個閾值函數(shù)r（C），定義的分割判決式為：

其中：MInt(C1,C2)=min[Int(C1)+τ(C1),Int(C2)+τ(C2)],τ(C)=;閾值函數(shù)τ(C)是一個關(guān)于連通分量大小的函數(shù)；表示連通分量的大小，也可以認為是C集合中的元素數(shù)目；K是一個供輸入的參數(shù)（常數(shù)）。閾值函數(shù)τ(C)是用來控制該算法可能會引起過分割產(chǎn)生的小區(qū)域。常數(shù)K越大，則抑制小區(qū)域的效果越明顯，也即分割后的區(qū)域面積較大；反之，則分割后的小區(qū)域較多。

運動目標場景分割效果，如圖3所示?？梢钥闯?，基于圖的快速分割算法（Efficient Graph?based Segment）能夠把自然場景中各種物體的區(qū)域塊及相似部分很好地提取出來，在分割精度和計算效率上都能夠達到令人滿意的要求。雖然計算機無法直接從分割結(jié)果中獨立判斷出運動目標，但是其清晰的區(qū)域劃分及完整的局部輪廓為結(jié)合其他方法進行更高層次機器視覺分析工作提供了一個良好的基礎(chǔ)。

圖3　運動目標場景圖分割效果，分割區(qū)域隨機上色

3　圖像分割與三幀差分相結(jié)合的運動目標檢測方法

幀差分法容易確定運動目標的精確位置，但是往往得到斷裂的目標區(qū)域輪廓，無法有效判定目標的完整性或數(shù)量，圖像分割的方法雖能夠精確地標示出圖像中的同質(zhì)區(qū)域，但是無法獨立從中提取出擬觀察的目標，針對它們各自的優(yōu)點和不足之處，本文提出一種基于兩者相結(jié)合的運動目標檢測方法。

3.1圖像分割與三幀差分相結(jié)合的運動目標檢測方法

本文提出的方法是結(jié)合圖像分割和幀差分信息，對割裂的目標進行有效的完整性識別，步驟具體如下：

（1）對原視頻序列中間一幀的原始圖像采用圖割方法做區(qū)域分割，分割的區(qū)域標記為An（A1，A2，A3，…），如圖4所示。

圖4　圖分割區(qū)域標注及幀差分區(qū)域標注

（2）用三幀差分法求得的所有目標變化區(qū)域，區(qū)域標記為Bn（B1，B2，B3，…）

（3）求出An中所有包含Bn的相交區(qū)域（即任取Bn，它所對應(yīng)的從屬于An的區(qū)域）用Cn來表示。公式表示為Cn=An（當且僅當Bi∈Ai時），如圖5所示。

（4）計算Cn內(nèi)所有區(qū)域兩兩之間的鄰接性，對存在任一鄰接關(guān)系的區(qū)域進行區(qū)域合并，最終得到的獨立區(qū)域的數(shù)量為目標存在的數(shù)量，如圖6所示。至此，目標判定結(jié)束，通過完整性識別，最終無法合并的獨立區(qū)域的個數(shù)即為目標的個數(shù)。

該算法主要是針對三幀差分法和圖像分割方法各自的優(yōu)勢和不足，通過將兩者結(jié)合起來，在信息上互相補充及約束，以實現(xiàn)對運動目標的完整性識別。下面選擇三幀差分法進行算法實驗比對，圖6（a）為三幀差分法目標檢測結(jié)果，圖6（b）為采用本文判定規(guī)則后得到的目標檢測結(jié)果，從中容易看出三幀差分法把一個目標分割成多個子塊，而提出的算法能夠提取完整目標。

圖5　計算交集區(qū)域及區(qū)域合并

圖6　三幀差分同本文算法目標檢測對比

3.2運動目標檢測系統(tǒng)流程

圖7為目標檢測系統(tǒng)的流程圖。

圖7　目標檢測系統(tǒng)流程圖

該流程如下：

（1）進行圖像預(yù)處理，包括幀差分運算及第二幀圖像的分割運算；

（2）運用本文給出的算法進行完整性判斷，求出目標的輪廓區(qū)域；

（3）輸出結(jié)果，并根據(jù)程序運行需要決定是否結(jié)束檢測或繼續(xù)進行循環(huán)檢測。

4　實　驗

本實驗旨在證明一種幀差分同區(qū)域分割方法相結(jié)合的目標檢測方法的有效性，為此隨機選取了30組基于固定攝像頭的運動目標場景視頻進行測試（部分數(shù)據(jù)集選自changing detection國際會議2014年公開數(shù)據(jù)集，部分選自視頻網(wǎng)站），包括室內(nèi)環(huán)境，室外環(huán)境，近景，遠景，夜間紅外條件，對象包括大型機械，動物，人等。實驗環(huán)境為 Dell PC，intel i7?3770處理器，8 GB內(nèi)存，Windows XP操作系統(tǒng)，VC 2008平臺，其中4組視頻實驗流程及結(jié)果展示如下。

圖8（a）為原視頻圖像序列中第二幀圖像，圖8（b）為原視頻圖像序列三幀差分結(jié)果，圖8（c）為第二幀圖像進行快速圖分割的結(jié)果，圖8（d）為用本文提出的方法求得的相交區(qū)域，圖8（e）為最終區(qū)域合并的結(jié)果，圖8（f）為Matlab中用連通區(qū)域檢測函數(shù)確定的目標（用外接矩形框表示）。

圖8　4組隨機視頻序列圖實驗

為了評估檢測效果[11]，圖9（a）中定義目標真實區(qū)域為S，本文算法檢測到的區(qū)域為T，真實有效檢測區(qū)域為R（R=S∩T），單個目標檢測有效率表示為，30組序列圖像評估結(jié)果如圖9（b）所示，平均檢測有效率大于90%。對所有測試視頻，本文提出的算法均能對運動目標進行良好識別，但是也存在一些不足之處：在進行完整性判定時，運動目標的陰影部分無法自動排除在外，當背景顏色同運動目標過于接近時，有可能把部分背景區(qū)域誤判為運動目標輪廓區(qū)域，導致檢測到的面積大于運動目標的實際面積。此外，幀差分的結(jié)果中，如果運動目標斷裂的區(qū)域面積顯示不足或分布不均勻，會導致最終檢測到的目標區(qū)域小于目標的真實區(qū)域。

不同尺寸序列圖像用本文算法的平均處理時間，如圖10所示，圖像越大所需計算時間越多，但是對于450× 375的視頻圖像，處理速度在2 s左右，這就為接近實時的智能應(yīng)用系統(tǒng)的開發(fā)提供了可能，限于實驗條件，本文僅給出將來進一步改進本算法可采取的方案：提升現(xiàn)有硬件配置；對算法進行改造，采用多核或分布式運算[12]；根據(jù)特定場合的需求在檢測運算中縮小視頻圖像尺寸以檢測速度。

對于圖像分割來說，K,M等參數(shù)的選取對本文算法效率也有直接影響，首先對分割運算時間有直接影響，但是這種影響是非線性的，選取不同K,M參數(shù)對圖像分割時間影響的波動范圍通常小于圖像分割總時間的10%，其次，因K,M取值導致過細或過粗的分割會影響到最終檢測區(qū)域面積小于或大于目標的真實面積，但是對于特定場景，特定的視角，特定焦距的監(jiān)控視頻，一般能夠通過實地測試篩選合適的K,M參數(shù)，使得在該參數(shù)下分割能取得最適宜的效果，以便于后續(xù)進行目標完整性識別的計算。

圖9　目標檢測有效率評估

圖10　算法平均運行時間統(tǒng)計

5　結(jié)　語

本文主要探討了利用幀差分方法與圖像分割相結(jié)合的一種運動目標檢測方法，該方法針對幀差分法的不足，能夠較好地對運動目標輪廓進行完整提取。但是目前該算法在使用效率及在不同場合下的自適應(yīng)性有待進一步加強，這是下一步研究工作的重點。

參考文獻

[1]孫即祥.數(shù)字圖像處理[M].石家莊：河北教育出版社，1993.

[2]伏思華，張小虎.基于序列圖像的運動目標實時檢測方法[J].光學技術(shù)，2004（2）：215?218.

[3]DUBUISSON M P，JAIN A K.Object contour extraction using color and motion[C]//Proceedings of 1993 IEEE Computer So?ciety Conference on Computer Vision and Pattern Recognition. New York：IEEE，1993：471?476.

[4]LIU Gang，NING Shangkun，YOU Yugan，et al.An improved moving objects detection algorithm[C]//Proceedings of 2013 In?ternational Conference on Wavelet Analysis and Pattern Recog?nition.Tianjin，China：IEEE，2013：96?102.

[5]肖本賢，陸誠，陳昊，等.基于幀間差分法和不變矩特征的運動目標檢測與識別[C]//第二十七屆中國控制會議論文集.昆明：中國自動化學會控制理論專業(yè)委員會，2008：578?581.

[6]李建，藍金輝，李杰.一種新型快速運動目標檢測算法[J].中南大學學報（自然科學版），2013（3）：978?984.

[7]TU Jilin，DEL AMO A，XU Yi，et al.A fuzzy bounding box merging technique for moving object detection[C]//Procee?dings of 2012 Annual Meeting of the North America on Fuzzy Information Processing Society.Berkeley：IEEE，2012：1?6.

[8]章毓晉.圖像分割[M].北京：科學出版社，2001.

[9]許新征，丁世飛，史忠植，等.圖像分割的新理論和新方法[J].電子學報，2010（1）：76?82.

[10]FELZENSZWALB P F，HUTTENLOCHER D P.Efficient graph?based image segmentation[J].International Journal of Computer Vision，2004，59（2）：167?181.

[11]李鵬飛，陳朝武，李曉峰.智能視頻算法評估綜述[J].計算機輔助設(shè)計與圖形學學報，2010（2）：352?360.

[12]WASSENBERG J，MIDDELMANN W，SANDERS P.An effi?cient parallel algorithm for graph?based image segmentation [C]//Proceedings of 2009 13th International Conference on Computer Analysis of Images and Patterns.[S.l.]：Springer，2009：1003?1010.

朱長仁（1968—），男，浙江淳安人，副教授，碩士生導師，博士。主要研究方向為圖像分析與理解、遙感圖像智能解譯、信息融合。

錢智明（1986—），男，江蘇南通人，在讀博士。主要研究方向為圖像理解與目標識別。

中圖分類號：TN911.73?34

文獻標識碼：A

文章編號：1004?373X（2016）03?0013?05

doi：10.16652/j.issn.1004?373x.2016.03.004

收稿日期：2015?07?22

基金項目：國防科大ATR重點實驗室項目資助；國防科大創(chuàng)新論文資助

作者簡介：陳佳（1983—），男，福建福州人，在讀碩士。主要研究方向為圖像分析與理解。

A moving target detection method based on integration of frame difference method and fast image segmentation

CHEN Jia1，2，ZHU Changren1，QIAN Zhiming1
（1.Key Laboratory of ATR，College of Electronic Science and Engineering，National University of Defense Technology，Changsha 410073，China；2.Directly Under Detachment，The Fujian Province Armed Police Corps，F(xiàn)uzhou 350001，China）

Abstract：The target area acquired by the frame difference method after pretreatment becomes hollowing or is split into several disconnected parts，and it is difficult for computer to judge whether the multiple parts belong to one object，so a moving target detection method based on integration of three?frame difference method and fast image segmentation is proposed.The three?frame difference operation and image?based fast segmentation for sequential images are conducted，and then the decision rule is fused by definition to carry out mutual supplementation and restraint of the difference results and image segmentation region block，after that，the sub?region blocks corresponding to the decision rule are combined，and the position and outline of the moving target are extracted precisely.The experimental results show this method can effectively improve the integrity of the moving target detection.

Keywords:：target detection;；frame difference;；image segmentation;；minimum spanning tree;；video surveillance