以掃描線為單位的背景提取與更新算法研究

張全法，李宏成，楊海彬，任朝棟

（鄭州大學 物理工程學院，鄭州450001）

以掃描線為單位的背景提取與更新算法研究

張全法，李宏成，楊海彬，任朝棟

（鄭州大學 物理工程學院，鄭州450001）

基于背景差分法的視頻車輛監(jiān)控系統(tǒng)實時性與準確性的設計要求，提出了一種新的背景提取與更新算法.該算法以掃描線為單位進行運算處理，簡單易行.在背景提取和背景更新階段，分別利用幀間差分和背景差分檢測運動前景，再配合適當?shù)倪\動區(qū)域判定條件，很好地消除了運動前景的影響，提高了準確性.通過將背景更新任務分解到多幀中處理，大大縮短了處理一幀圖像的耗時，提高了系統(tǒng)實時性.實踐證明該方法可行.

背景提取；背景更新；掃描線；運動檢測；任務分解

在基于視頻的車輛監(jiān)控系統(tǒng)中，通常利用背景差分法來檢測運動車輛，背景提取是其關鍵技術［1］.一個優(yōu)良的背景應該能夠根據(jù)外界環(huán)境的變化實時地更新［2］.在進行系統(tǒng)設計的時候，除了要求背景提取與更新的準確度足夠高之外，還要求背景更新的耗時盡量短.因為系統(tǒng)在實際工作過程中，不僅需要進行背景更新，還需要對視頻中的每幀圖像進行很多環(huán)節(jié)的實時處理，包括灰度化、平滑濾波、抖動消除、背景差分、圖像分割、陰影消除、車輛識別與跟蹤、違章判定和交通參數(shù)計算等.

目前，國內(nèi)外常用的背景提取與更新算法及其改進算法主要有多幀圖像平均法、連續(xù)幀差法、直方圖分析法、統(tǒng)計中值法、高斯模型法、IIR濾波法、卡爾曼濾波器法等.這些方法存在著諸如準確性欠佳、受運動前景影響大、占用內(nèi)存多等缺點.它們的共同缺點是當以像素或塊為單位對整幅圖像進行處理時，處理一幀圖像的耗時太長.本文通過對常用背景提取與更新算法的分類分析，提出了一種新的以掃描線為單位的背景提取與更新算法.

1 算法的提出

1.1 背景提取算法的提出

主要的背景提取算法可以分為2類：

（1）完整提取法，是指通過一次處理提取出完整的背景.此方法也可以分為2類：① 將第一幀圖像作為背景的方法，此方法在單高斯模型法等算法中有應用，但是其準確性欠佳，因為第一幀圖像通常都是包含前景的［1］；② 通過考察視頻中最前面的多幀圖像，根據(jù)某種規(guī)律對背景進行估計，此方法在直方圖分析法等算法中有應用，其缺點是所得背景受車流量的影響比較大［3］.

（2）拼湊提取法，是指對于每幀圖像僅提取部分像素或圖像塊作為背景，經(jīng)過一段時間的拼湊得到完整背景.此方法在連續(xù)幀差法等算法中有應用.這類方法需要確定運動區(qū)域，若當前幀中非運動區(qū)域所對應的背景尚未提取，就提取其數(shù)據(jù)作為初始背景，反之就更新背景，所以它也屬于背景更新算法.其缺點是容易把相鄰兩幀之間的相似前景交疊區(qū)誤認為背景［4］.文獻［5］通過填充連通區(qū)域中的空洞來減小相似前景交疊區(qū)的影響，算法復雜性增加了許多，但是效果不太明顯.因為前景常常被分割成多個連通區(qū)域，甚至出現(xiàn)大面積斷續(xù)現(xiàn)象（如圖1所示），其上難免有地方被誤認為背景.圖1（a）是一段視頻中的第47幀圖像，圖1（b）和圖1（c）分別是監(jiān)控區(qū)域內(nèi)該幀與上一幀及背景的二值化差分圖像.

如果有前景混入背景，在其影響消除之前，將導致交通參數(shù)的誤算、交通違章的誤判和漏判等.其影響又很難通過后續(xù)的迭代更新消除，甚至會持續(xù)積累［2］.目前，對于靜止前景尚沒有很好的檢測方法.在得到可靠的背景之前，幀間差分法可以較好地檢測出運動前景，但是需要更好的方法來消除相似前景交疊區(qū)的影響.通過分析圖1（b）可知，對于圖中的每個白點，其上下左屬于前景.于是提出以掃描線為單位，只要其二值化幀間差分圖像上存在白點，其上下一定范圍內(nèi)的掃描線皆被看作運動區(qū)域，對每幀圖像僅提取非運動區(qū)域作為背景，經(jīng)過一段時間的拼湊提取出完整背景.

新算法存在將部分非運動區(qū)域判定為運動區(qū)域的情況，以致須較長時間的拼湊才能夠提取出完整背景.但是，只要參數(shù)設置合理，就不會將運動區(qū)域判定為非運動區(qū)域，將部分非運動區(qū)域判定為運動區(qū)域，背景提取的準確度將大大提高.

1.2 背景更新算法的提出

主要的背景更新算法分為2類：

（1）盲目更新法，即將增加的所有新的像素給背景而不管它是否屬于背景.此方法又可以分為2類：① 非迭代更新法，通過考察當前幀之前的多幀圖像，根據(jù)某種規(guī)律對當前幀的背景進行估計，此方法在多幀圖像平均法等算法中均有應用.在實際程序設計中初次選擇的即為完整提取法的背景提取算法，其具有占用內(nèi)存多、速度慢等缺點［4］；② 迭代更新法，通過將上一幀的背景與當前幀進行加權平均，從而對當前幀的背景進行估計.此方法在IIR濾波法等算法中有應用.它無需大的存儲空間，但更新效果受限于加權系數(shù)，不能有效地濾除運動前景和跟蹤環(huán)境光的改變［2］.

（2）選擇更新法，是指將像素加入背景時根據(jù)它是否屬于背景而采取不同的措施.如果所選判據(jù)不合適，任何誤檢都將持續(xù)影響后續(xù)工作［1］.此方法可以分為3類：① 基于概率分布的，根據(jù)像素灰度值的歷史數(shù)據(jù)，計算當前幀中像素值的概率，用來決定它是否屬于背景，例如混合高斯模型法等；② 通過時域低通濾波將視頻中的快速變化過程分離出去，從而預測緩變的背景圖像，例如卡爾曼濾波器法等；③ 基于運動檢測的，僅將非運動區(qū)域加入背景，其又分為3種：方法一，通過背景差分進行運動檢測；方法二，通過幀間差分進行運動檢測；方法三，結合背景差分與幀間差分進行運動檢測.

設計背景更新算法時，考慮到盲目更新法的準確度比較低而不采用，更新法中①、②兩種方法因計算太復雜也不采用.比較圖1（b）和圖1（c）可知，背景差分比幀間差分檢測出的前景更加準確和完整.因此，選擇更新法中③的各個方法相比較可知：方法一比方法二具有較高的準確度，比方法三具有更快的速度.不過它仍然有可能將部分前景混入背景，速度也不夠快，因為它是以像素為單位對整幅圖像進行處理的.而以掃描線為單位，只有當某條掃描線的二值化背景差分圖像上不存在白點、其上下一定范圍內(nèi)的掃描線上也不存在白點的時候，才將它作為新的背景，且每幀僅更新一條掃描線，通過循環(huán)不斷地更新背景.

新算法完成一次背景更新需要的時間比較長，但是它大大縮短了處理一幀圖像的耗時，將更多的時間留給了其他不能分解到多幀圖像之間進行處理的環(huán)節(jié).而且，由于其準確度大大提高，在一定程度上彌補了更新速度慢的不足.從另一角度看，一般情況下環(huán)境光變化緩慢，按照這樣的速度來更新背景是足夠的；對于極少數(shù)情況（如閃電造成的環(huán)境光急劇改變），可以采取不處理對應幀的方法，這樣對系統(tǒng)整體性能的影響并不大.

2 算法描述

背景提取與更新算法皆是針對灰度圖像進行的.當彩色圖像灰度化時，采用文獻［6］中的快速算法，灰度化之后進行平滑濾波處理，然后采用文獻［7］中的快速算法進行防抖動處理.在系統(tǒng)剛開始運行時，進行背景提取，提取出完整背景之后再進行背景更新及后續(xù)處理.背景提取與更新算法描述如下：

2.1 背景提取算法描述

（1）對于第k（k≥2）幀圖像，按照下式求其與第k－1幀圖像的二值化差分圖像：式中：d（x，y）為二值化差分圖像上坐標為（x，y）的點的像素值（取值為1，對應白點；取值為0，對應黑點）；fk（x，y）和fk－1（x，y）分別為第k和第k－1幀圖像上同一點的灰度值；T為灰度閾值，當某點的灰度變化大于T時認為它屬于運動區(qū)域，T越小，準確度越高、提取時間越長.

（2）按照下式確定哪些掃描線上存在白點、哪些掃描線上不存在白點

式中：l（y）取值為1、0時分別表示第y條掃描線上存在和不存在白點；W 為每條掃描線上的像素數(shù).

（3）按照從小到大的順序，根據(jù)背景提取的歷史數(shù)據(jù)查找尚未提取背景的掃描線.假設查找到第y0條掃描線時尚未提取背景，按照下式確定其能否提取背景：

式中：y1＝max（0，y0－h(huán)），y2＝min（H，y0＋h）；e（y0）取值為1、0時分別表示能和不能提取第y0條掃描線作為背景；h為范圍閾值，表示在y0上下多大范圍內(nèi)不存在白點時才能夠提取背景，h越大，準確度越高、提取時間越長；H為掃描線的條數(shù).

（4）若e（y0）＝1，則提取第k幀圖像上第y0條掃描線作為背景，并修改第y0條掃描線的背景提取歷史數(shù)據(jù)為已經(jīng)提取，否則不提取也不修改.

（5）若y0＜H，返回步驟（3），以便對每幀圖像提取盡量多的掃描線，從而縮短拼湊時間.這樣做是允許的，因為此時系統(tǒng)尚未真正開始工作，背景提取環(huán)節(jié)耗時長一些沒有關系.若y0≥H，令k＝k＋1，返回步驟（1），進入下一幀圖像的處理，直至提取出完整背景.

2.2 背景更新算法描述

（1）二值化第m幀圖像與背景的差分圖像.為了在后續(xù)環(huán)節(jié)中能夠準確地檢測出車輛，在二值化時采用文獻［8］中的多閾值圖像分割法以消除陰影的影響，

式中：fm（x，y）和b（x，y）分別為第m 幀圖像和背景上坐標為（x，y）的點的灰度值；T1、T2為大小和符號皆不相同的2個灰度閾值，并且按照文獻［8］中的方法根據(jù)環(huán)境光的變化進行自適應調(diào)整.

（2）根據(jù)背景更新歷史數(shù)據(jù)查找最需要更新的掃描線.假設應該從第Y條掃描線開始查找，則利用循環(huán)隊列從Y處開始查找尚未更新的掃描線，若掃描線皆更新過，清除背景更新歷史數(shù)據(jù)并令Y＝0，以便重新開始逐線更新；若長時間未清除過歷史數(shù)據(jù)，說明出現(xiàn)了車輛停留等現(xiàn)象，將未更新的掃描線上各像素的灰度值乘以比例系數(shù)r，之后清除歷史數(shù)據(jù)并令Y＝0（r等于第m幀圖像的平均灰度與背景平均灰度之商）.

（3）假設所得掃描線序號為y0，根據(jù)式（3）求e（y0），用來確定能否更新背景，所用l（y）根據(jù)式（2）求得.

（4）若e（y0）＝1，提取第m幀圖像上第y0條掃描線，用以替代背景中的第y0條掃描線，并修改其背景更新歷史數(shù)據(jù)為已經(jīng)更新，否則不替代也不修改.無論這條掃描線更新與否，令Y＝（y0＋1）%H，使得再次查找的時候從下一條掃描線開始，以防車輛停留處不能更新造成其他地方也不能更新.

（5）令m＝m＋1，返回步驟（1），以便縮短處理時間.如此不停地更新背景，直至系統(tǒng)停止運行.

3 實驗結果

實驗所用視頻圖像大小為320×240像素，程序用Visual C＋＋6.0編寫，背景提取與更新過程如圖2所示.為了減小各種干擾的影響，所有處理皆在監(jiān)控區(qū)域內(nèi)進行.從第2幀開始提取背景，到第20幀完成背景提取.由圖2可以看出，所提取的背景非常準確，不受運動前景的影響.之后進入背景更新，到第815幀時背景更新效果已經(jīng)很明顯，從圖上可以看出背景灰度整體上減小了，而且也不受運動前景的影響.

通過對各種測試條件下拍攝的視頻片段進行處理，也證明了其可行性.測試條件包括不同的十字或丁字路口與非交叉路口、不同的車道數(shù)、全天的不同時段、不同的天氣等.

4 結 語

以掃描線為單位的背景提取與更新算法，通過合理地設置參數(shù)，能夠準確地消除運動前景的影響，提高背景提取與更新算法的準確度，而且該方法具有算法簡單、易于實現(xiàn)等優(yōu)點.特別是通過任務分解將每幀圖像的背景更新耗時降到最低，為保證系統(tǒng)的整體實時性作出了重要貢獻.該方法已經(jīng)在設計的視頻車輛監(jiān)控系統(tǒng)中得到了應用，并且已經(jīng)對該系統(tǒng)進行了全面的現(xiàn)場測試，能夠滿足對實時性和準確性的設計要求.

［1］ 楊珺，史忠科.基于改進單高斯模型法的交通背景提取［J］.光子學報，2009，38（5）：1293－1296.

［2］ 何云，許建龍，孫樹森，等.一種改進的視頻監(jiān)控背景更新算法［J］.浙江理工大學學報，2010，27（4）：585－589.

［3］ 吳亮，馬宏興.交通信息的背景提取技術分析［J］.西安科技大學學報，2010，30（1）：117－122.

［4］ 吳眾山，雷蘊奇，吳綠芳，等.一種實用的背景提取與更新算法［J］.廈門大學學報（自然科學版），2008，47（3）：348－352.

［5］ 袁偉才，徐向民.一種有效的動態(tài)背景提取及更新方法［J］.計算機工程與應用，2010，46（4）：191－192.

［6］ 張全法，楊海彬，任朝棟，等.彩色圖像的快速高保真灰度化方法研究［J］.鄭州大學學報（理學版），2011，43（3）：66－69.

［7］ 張全法，任朝棟，李煥，等.視頻車輛監(jiān)控系統(tǒng)圖像抖動快速消除算法研究［J］.鄭州大學學報（理學版），2011，43（4）：44－47.

［8］ 任朝棟，張全法，李煥，等.快速消除車輛陰影的多閾值圖像分割法［J］.應用光學，2010，31（6）：961－964.

Study on New Algorithm for Background Extraction and Updating in Unit of Scan Line

ZHANG Quan－fa，LI Hong－cheng，YANG Hai－bin，REN Chao－dong
（
Zhengzhou University，Zhengzhou 450001，China）

To meet the requirements for real－time and accuracy of a video－based vehicle monitoring system based on background subtraction，a new background extraction and updating algorithm is proposed.In the algorithm，both the extraction and updating in unit of scan line are carried out，which was simply and easy.In the stage of extraction and updating，moving objects by frame difference and background subtraction separately are detected，and influence with appropriate moving region criterions is removed，thus raised the accuracy.Through dividing updating tasks of one frame into several frames，greatly reduced the one frame processing time，thus raised the real－time property of the whole system.Experiments demonstrates that the algorithm is available for practice.

background extraction；background updating；scan line；moving object detection；task dividing

TP391.41

A

10.3969／j.issn.1671－6906.2012.01.012

1671－6906（2012）02－0054－04

2012－02－23

張全法（1966－），男，河南安陽人，副教授，碩士.