一種在ＭＰＥＧ－４編碼過程中提高實時性的算法

摘要：文章提出了一種新的在MPEG-4編碼過程中提高實時性的算法。算法采用雙重篩選機制，充分利用了運動估計的結果提取運動對象。首先在運動估計過程中加入背景優先準則進行第一重篩選；然后根據運動估計后宏塊的最小平均絕對差值利用區域自適應門限進行第二重篩選，從而獲得運動區域掩模；最后對掩模進行形態濾波和填充消除噪聲點，最終得到運動區域。算法分別在硬件和軟件平臺上進行測試，結果表明提出的算法得到了理想的分割效果，較傳統的在編碼前進行運動對象提取的方法實時性大大提高。

關鍵詞：運動對象；運動估計；自適應門限；形態濾波

Abstract:A new algorithm is proposed， which improves the real-time capability in the process of MPFG-4 coding. The algorithm uses diplex-filtration mechanism， and takes full advantage of the result of motion estimation. First， some relevant rules are added to the process of motion estimation for the first filtration. Then the self-adapting filtration is carried through according to the minimum Sum of Absolute Difference (SAD)， and the mask of the moving region is obtained. Finally， after the morphology filtering and noise removing， the accurate matrix of the motion regions is obtained， and the moving video object is thereby gained. The experimental results show this algorithm gets perfect segmentation， and improves the real-time capability greatly when compared with the traditional method of extracting the moving video object before coding.

Key words: moving video object; motion estimation; self-adapting threshold; morphology filter

自基于對象的視頻壓縮編碼標準MPEG-4提出之后，人們加緊了對視頻對象分割的研究，因為它是基于對象的視頻檢索、面向對象的視頻壓縮和編輯等應用的基礎。

近年來提出的視頻分割算法大體上可以分為基于運動的分割算法和時空分割算法兩種：基于運動的分割算法又可以分為基于光流法的分割[1]和基于變化檢測的分割[2-3]兩大類，它們計算量都比較大，實時性不太好；時空分割算法又可分為時域分割和空域分割，時域分割檢測相鄰幀間的運動區域、空域分割檢測幀內邊界和邊緣信息，時空結合才能達到滿意的效果。在時空分割法中分水嶺算法[4]得到了廣泛的應用，但是容易產生過分割現象，需要后處理，即根據某些規則對相似區域合并，而且無論是區域分割還是合并過程，計算量都非常大。

文獻[3]在分割過程中通過從視頻序列中建立最新的背景信息并將每幀與之比較，任何與背景明顯不同的像素都認為是運動區域，所以要取得運動物體就必須等待背景建立完善后才能進行，這在一定程度上損害了實時性。文獻[4]中涉及到分水嶺算法分割、時空合并以及分級運動估計等一些算法，并將大量的計算集中到全局運動估計上，文獻[5]提出的算法是基于4×4塊大小，從一定程度上減少了運算量，但是算法中模糊聚類的使用增加了運算復雜度。文獻[6]提出的算法能取得非常好的分割效果，但算法中Gibbs(一種隨機場分布的名稱)勢能函數的引入，利用迭代條件模式(ICM)方法求解得到最小化能量在一定程度上損害了實時性。

從上面可以看出，提出的算法要想取得好的分割效果，或多或少都增加了計算或者邏輯上的復雜度，即在注重分割效果的同時損害了實時性。

本文針對上述情況提出了一種在MPEG-4編碼過程中快速提取運動對象的算法，適用于一些不需要完美分割效果的場合中，如視頻會議、視頻電話、實時監控等。該方法利用在MPEG-4編碼過程中的運動估計的結果來進行視頻對象的分割。在本文中視頻序列的背景都假設為靜止的(如果背景不是靜止的可以首先采用全局運動估計取得全景圖)。算法首先在運動估計過程中加入背景優先準則；然后根據運動估計的結果能進行第一重篩選，將屬于運動物體的宏塊和屬于靜止背景的宏塊粗略地區分開來；再根據運動估計后宏塊的最小平均絕對差值利用自適應門限進行第二次篩選，篩選出運動矢量為零但實際屬于運動區域的宏塊；最后經過適當的形態濾波和填充，消除噪聲點和空洞，獲得運動區域的掩模，從而獲得運動對象。

1 分割算法

1.1 預處理

為了更好地獲得運動估計的效果，減少圖像中噪聲點對運動估計結果的影響，在編碼之前先對視頻序列進行平滑濾波。中值濾波是一種抑制噪聲的非線性處理方法，該方法運算簡單，易于實現，而且能較好地保護邊界。

1.2 第一重篩選

本文采用的分割算法是在編碼過程中實現的，以編碼過程中運動估計為基礎。在運動估計中選用大小8×8的宏塊。為了提高運動估計的搜索效率和搜索效果，采用搜索效率較高的鉆石形搜索法[7]，匹配準則為最小平均絕對差值函數(SAD)：

式中 (i，j )-x’(i，j )分別為當前幀中待估計宏塊和參考幀中候選宏塊中像素點的亮度值，N為宏塊大小。

為了減少后期處理中背景和運動區域宏塊的誤判，在運動估計過程中加一個限定準則：背景優先準則。具體如下：在搜索過程中如果當前待估計宏塊和參考宏塊的相對位移為零，且SAD

1.3 第二重篩選

第二重篩選是利用編碼過程中運動估計產生的最小SAD值來進行的，將一幀中滿足運動矢量為零，且所對應最小SAD值小于某一個門限的宏塊劃歸靜止背景區域，不滿足條件的篩去。

首先對本文涉及到的一些參數做如下描述：

設視頻序列中每一幀圖像I 的大小為M×N，I(i，j )代表圖像中像素點的亮度值，其中i，j 分別是像素點垂直和水平方向坐標(0≤i

1.3.1自適應門限的計算

由于搜索算法采用搜索效率較高的菱形搜索算法，得出的搜索結果只是局部最優，這樣就使得運動矢量為零的宏塊不一定真正屬于背景區域。而這樣類型的宏塊，匹配程度相對于真正屬于背景區域的宏塊要差，也就是它們的MinSAD值要比真正屬于背景區域宏塊的MinSAD值要大，因此要從所有運動矢量為零宏塊的MinSAD值中通過計算門限來對它們進行篩選。所有這些MinSAD值可以大致分為兩個區域，一個是背景區域宏塊對應的值比較小的區域，另一個是運動區域對應的比較大的區域，因此可以采取基于統計直方圖求閾值的方法來計算門限，分開這兩個區域。

由于幀間編碼宏塊的MinSAD<128，所以MinSAD值得取值范圍為0～128。圖1(a)是從選取Sign_irene序列(一種隨機場分布)的第4幀計算得出運動矢量為零宏塊的MinSAD值對應的直方圖。

傳統全局閾值的計算方法只對在直方圖中會出現兩個波峰，且波谷比較明顯的情況有效[8]，由于視頻圖像中亮度分布的不均勻性，也就是說在一幀圖像中不同的區域亮度變化是不一樣的。那么用傳統的單一的全局閾值來區分整個圖像中所有的運動矢量為零的宏塊是不合理的。從圖1中可以看出這樣的直方圖只出現一個尖峰，給分離造成了困難。

針對這樣的情況，本文在文獻[8]中所描述的自適應閾值的計算方法的基礎上提出了適用的基于分區域的自適應閾值篩選方法：

(1)將所有運動矢量不為零的宏塊的MinSAD值置為最大值128。

(2)計算所有宏塊MinSAD值的數學期望值E。

(3)將圖像劃分成為大小相等的16個子區域，每個區域均包含99個宏塊。

(4)分別計算這16個子區域內宏塊MinSAD值的數學期望和方差。

(5)挑選方差大于500的區域，對這些區域分別進行全局閾值計算，那么這些區域中MinSAD值小于閾值的宏塊則確定屬于背景區域。

(6)挑選方差小于100，數學期望小于E 的區域，符合這樣條件區域中的宏塊全部確定為屬于背景區域。

(7)將經過兩次挑選剩下的宏塊組成一個大的區域，這個組合的大區域中的MinSAD 值對應的直方圖如圖1(b)所示，可以看出圖1(b)中有兩個波峰，對這個大區域進行全局閾值計算，MinSAD 值小于閾值的宏塊屬于背景區域。

其中全局閾值計算方法如下：

(1)將所有運動矢量為零的宏塊的MinSAD 值按從小到大排序。

(2)選取一個T 的初始估計值。

(3)這樣將這些MinSAD值分為兩組，G 1由所有大于T 的MinSAD值組成，G 2由所有小于T 的MinSAD值組成。

(4)對區域G 1、G 2中的所有MinSAD值計算出平均MinSAD值μ1和μ2。

(5)計算新的門限值：T =1/2(μ1+μ2)。

(6)重復步驟3到4，直到逐次迭代所得的T 值之差小于事先定義的參數T 。

1.3.2 獲取運動區域的掩模矩陣

用二值矩陣C作為運動區域的掩模矩陣，C的大小和一幀圖像分割出的宏塊數相等，該矩陣行數為M /8，列數為N /8，C(m，n)代表C中第m行n列的元素的值。根據上一節篩選的結果就可以得出：

由公式(2)得出的C 就是運動區域的掩模矩陣。當C (m，n)=1時block (m，n)就屬于運動區域，反之則屬于背景區域。

由在MPEG-4標準中幀可以采用雙向運動估計，所以在B 幀中可以有前向運動估計和后向運動估計兩個運動估計產生的結果，因此可以利用這兩個運動估計的結果分別求得相應運動區域的掩模矩陣。設求得的兩個矩陣為C₁、C₂，將C₁、C₂做“或”運算有：

C (m，n)=C1 (m，n)|C2 (m，n)

(0

經過公式(3)處理后只要當前幀中的宏塊相對前一幀發生運動了就作為運動區域，因此B 幀能獲得更準確的運動區域。

1.4 形態學操作及填充

由上述處理得到的運動區域掩模難免會存在一些噪聲點，這些噪聲點可能導致背景區域的雜點和運動區域的一些空洞，因此要進行必要的形態濾波[8]首先用開運算濾除主要由噪聲引起的離散的小區域，接著用閉運算填充一些小“空洞”或者掩模圖像中小的細縫。

經過形態濾波之后能消除運動區域的一些小的空洞，但是對一些大的空洞有時候無法消除，所以還需要對這些大的空洞進行填充。本文采用的二次掃描方法[2]簡單易行，而且可以進行有效填充。對掩模矩陣按橫坐標掃描(按行掃描)，得到每行的第一個和最后一個屬于運動區域的元素，實際上是運動區域的邊界。第一個和最后一個元素之間的元素就屬于運動區域，用“１”填充這些區域得到水平方向上的候選運動區域。由于按行掃描所得運動區域不精確，再按縱坐標(按列)掃描，同樣可以得到一個垂直方向上的候選分割區域。將兩個候選運動區域進行“與”操作，即可得到分割的運動區域，由二進制“1”表示。

設經過填充之后的掩模矩陣為

C₃，那么由C₃中為“1”的元素所對應的宏塊組成的就是運動區域。

2 實驗分析

使用Visual C++6.0語言，用Sign_irene、MaD兩組測試序列分別對本算法進行測試，這兩組測試序列都是具有靜止背景的視頻格式——CIF格式(352×288)，序列分別如圖2(a)和圖2(b)所示。

圖3為經過第一重篩選的運動區域，由圖3可以看出運動區域的很多宏塊都被誤判為背景，尤其對于運動不為明顯的MaD序列。

圖4為經過第二重篩選之后的運動區域，從結果中可以看出和圖3相比運動區域宏塊的誤判明顯減少了，但是還是存在一些噪聲點的干擾，所以還要進行形態濾波進一步消除噪聲點。

形態濾波之后的掩模所對應的運動區域結果如圖5所示。從圖中可以看出經過形態濾波之后背景區域的雜點已經基本消除。

由形態濾波之后的掩模矩陣所對應的運動區域有可能還存在些較大的空洞，從圖5(b)中可以看出運動區域還有些空洞，所以還要進行填充操作。填充操作之后的運動區域如圖6所示，從圖6中可以看出這些空洞基本消除。

圖7是從兩個測試序列得出結果中抽取的部分圖像。

我們還在MPEG-4編碼器中使用該算法進行了測試，測試的硬件平臺是DAM6416P圖像處理平臺，測試結果表明使用該算法的編碼器平均處理一幀所需的時間為0.037 s，幀格式為CIF格式，其效果具有很好的實時性，而如果在編碼前采用速度相對較快的對稱差分法進行分割然后再進行編碼，處理同樣一幀所需的時間為0.09 s。

從對比中可以看出本文所采用的算法具有較高的實時性。

3 結束語

針對現有視頻分割算法為了獲取好的效果不便實時處理的情況，本文提出了上述算法。本算法的特點是避開在視頻編碼前花大量處理時間進行視頻對象的分割，而在編碼過程中利用運動估計的結果進行運動物體的分割。

在分割得到運動物體之后，無需再重新進行運動估計，只需將原先用于分割的運動估計的結果，根據分割出運動區域中心點的坐標位置，做相應的坐標變換即可。

從實驗的結果中可以看出分割效果比較理想。另外本文的運動區域掩模矩陣的計算基于宏塊，處理的數據量與基于像素的掩模矩陣的計算相比大為減少，僅為基于像素的掩模矩陣計算的1/64，從而使處理速度相應提高了很多，適合實時應用。在對視頻會議、視頻電話、視頻監控這些具有靜止背景特點的視頻壓縮編碼時，通過本文的方法可以快速有效地只對感興趣的運動區域進行編碼，而不對背景編碼，在解碼端再進行背景和前景的合成，這樣能較大地提高編碼效率。

4 參考文獻

[1] Arnell F， Petersson L. Fast object segmentation from a moving camera [C]//Proceedings of2005 Intelligent Vehicles Symposium， Jun 6-8，2005，Las Vegas， NV， USA. Piscataway， NJ，USA: IEEE， 2005:136-141.

[2] KIM Changick， Hwang Jenq-Neng. Fast and automatic video object segmentation and tracking for content-based applications [J]. IEEE Transactions on Circuits and Systems for Video Technology， 2002， 12 (2): 122-129.

[3] Chien Shao-Yi， MA Shyh-Yih， CHEN Liang-Gee. Efficient moving object segmentation algorithm using background registration technique [J]. IEEE Transactions on Circuits and Systems for Video Technology， 2002， 12(7):577-586.

[4] Tsaig Y， Averbush A. Automatic segmentation of moving object in video sequences: a region labeling approach [J]. IEEE Transactions on Circuits and Systems for Video Technology， 2002， 12(7):5972612.

[5] 黃波， 楊勇， 王橋， 等. 基于模糊聚類和時域跟蹤的視頻分割 [J]. 通信學報， 2001，22(12):22-28.

[6] 包紅強， 張兆揚. 一種基于區域Gibbs 勢能函數的視頻運動對象分割算法 [J]. 通信學報， 2005， 26(6):57-61.

[7] 張旭東， 盧國棟， 馮健. 圖像編碼基礎和小波壓縮技術 [M]. 北京:清華大學出版社， 2004.

[8] Gonzalez R C， Woods R E. Digital image processing [M]. Second Edition. 北京: 電子工業出版社， 2004.

收稿日期：2007-01-17

鞠鳴，南京郵電大學通信與信息工程學院在讀碩士研究生，研究方向為IP與寬帶網絡中語音與圖像處理。

何鴻，江蘇大學計算機科學與通信工程學院在讀碩士研究生，研究方向為圖像處理。