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

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

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

中圖分類號： TN911.73?34 文獻標識碼： A 文章編號： 1004?373X（2016）03?0013?05

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， Fuzhou 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

0 引 言

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

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

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

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

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

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

1.1 兩幀差分法

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

[FD（x，y）=Fk（x，y）-Fk-1（x，y）] （1）

式中[FD（x，y）]為得到的目標區域的變化量，再通過簡單的數學形態學開閉運算使得運動目標區域連續，同時去掉背景中的噪聲，最后選取合適的閾值[T，]對結果圖像進行二值化，其公式為：

[BD（x，y）=1，BDx，y≥T0，BDx，y

1.2 三幀差分法

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

[FD（x，y）=Fk（x，y）-Fk-1（x，y）]

[FD+1（x，y）=Fk+1（x，y）-Fk（x，y）] （3）

[FDD（x，y）=FD（x，y）+FD+1（x，y）]

1.3 幀差分法的不足之處

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

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

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

2.1 圖像分割介紹

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

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

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

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

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

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

2.2.1 最小生成樹方法

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

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

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

[ω（T）=（u，v）∈Tω（u，v）] （4）

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

[Int（C）=maxe∈MST（C，E）ω（e）] （5）

集合[C1，C2]之間的差異（Difference，Dif）為連接這兩個集合邊的最小權重，即：

[Dif（C1，C2）=minvi∈C1，vj∈C2，（vi，vj）∈E[ω（vi，vj）]] （6）

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

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

[D（C1，C2）=true， Dif（C1，C2）>MInt（C1，C2）1， 其他] （7）

其中：[MInt（C1，C2）=min[Int（C1）+τ（C1），Int（C2）+τ（C2）]，τ（C）=KC；]

閾值函數[τ（C）]是一個關于連通分量大小的函數；[C]表示連通分量的大小，也可以認為是[C]集合中的元素數目；[K]是一個供輸入的參數（常數）。閾值函數[τ（C）]是用來控制該算法可能會引起過分割產生的小區域。常數[K]越大，則抑制小區域的效果越明顯，也即分割后的區域面積較大；反之，則分割后的小區域較多。

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

3 圖像分割與三幀差分相結合的運動目標檢測

方法

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

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

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

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

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

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

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

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

3.2 運動目標檢測系統流程

圖7為目標檢測系統的流程圖。

該流程如下：

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

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

（3） 輸出結果，并根據程序運行需要決定是否結束檢測或繼續進行循環檢測。

4 實 驗

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

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

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

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

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

5 結 語

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

參考文獻

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

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

[3] DUBUISSON M P， JAIN A K. Object contour extraction using color and motion [C]// Proceedings of 1993 IEEE Computer Society 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 International Conference on Wavelet Analysis and Pattern Recognition. Tianjin， China： IEEE， 2013： 96?102.

[5] 肖本賢，陸誠，陳昊，等.基于幀間差分法和不變矩特征的運動目標檢測與識別[C]//第二十七屆中國控制會議論文集.昆明：中國自動化學會控制理論專業委員會，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].計算機輔助設計與圖形學學報，2010（2）：352?360.

[12] WASSENBERG J， MIDDELMANN W， SANDERS P. An efficient 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.