第五章序列圖像編碼及運(yùn)動(dòng)估計(jì)

第五章

序列圖像編碼及運(yùn)動(dòng)估計(jì)中國礦業(yè)大學(xué)信電學(xué)院主要內(nèi)容

5.1概述

5.2視頻信號的數(shù)字化5.3二維運(yùn)動(dòng)估計(jì)

5.4采用時(shí)間預(yù)測和變換編碼的視

頻編碼5.1概述概念：活動(dòng)圖像信號，也稱為數(shù)字序列圖像或連續(xù)幀圖像，指由多幅尺寸相同的靜止圖像組成的圖像序列。例如數(shù)字化后的電視或視頻信號。其中的每幅靜止圖像稱為一個(gè)幀。

活動(dòng)圖像與靜止圖像相比，可以認(rèn)為多了一個(gè)時(shí)間軸，成為三維信號，因此活動(dòng)圖像也被稱為三維圖像?；顒?dòng)圖像都是一幀一幀地傳輸，看作一個(gè)沿時(shí)間軸分布的圖像序列，統(tǒng)稱為序列圖像。這里主要討論序列圖像中的視頻圖像的壓縮編碼視頻圖像壓縮編碼分類：

幀內(nèi)編碼：也稱為空間壓縮。利用每幅(單幀)圖像內(nèi)部的相關(guān)性進(jìn)行幀內(nèi)壓縮編碼。當(dāng)壓縮一幀圖像時(shí)，僅考慮本幀的數(shù)據(jù)而不考慮相鄰幀之間的冗余信息。幀內(nèi)一般采用有損壓縮算法。壓縮后的視頻數(shù)據(jù)仍可以以幀為單位進(jìn)行編輯。幀內(nèi)壓縮一般達(dá)不到很高的壓縮。

幀間編碼：也稱為時(shí)間壓縮。利用時(shí)間軸上相鄰幀之間的相關(guān)性(前后兩幀信息變化很小)進(jìn)行幀間壓縮編碼。幀間壓縮一般是無損的。

混合編碼：為不同的編碼方法組合在一起相結(jié)合的編碼方法。如變換編碼和幀間預(yù)測編碼。視頻圖像編碼要求：

實(shí)時(shí)性：圖像傳輸系統(tǒng)必須能實(shí)時(shí)地對活動(dòng)電視

圖像進(jìn)行編碼傳輸。

高效性：必須能使數(shù)字視頻信號以一定目標(biāo)碼率

傳輸。如視頻信號8bit/像素，數(shù)碼率高

達(dá)216Mbit/s。視頻圖像編碼目的：在保證一定重建質(zhì)量前提下，以盡量少數(shù)據(jù)量來表征視頻信息，以減少視頻序列的碼率，便于能夠在給定的通信信道上實(shí)時(shí)傳輸視頻信號。5.2視頻信號的數(shù)字化5.2.1電視制式幀：一段視頻中的每一幅圖像稱為一幀。根據(jù)視覺暫留原理，要使人的視覺產(chǎn)生連續(xù)的動(dòng)態(tài)感覺，每秒鐘圖像的播放幀數(shù)要在24～30（幀頻）幀頻：每秒播放的幀數(shù)。電視制式：即電視的播放標(biāo)準(zhǔn)（掃描分辨率、幀頻、色彩空間的轉(zhuǎn)換關(guān)系不同）。目前國際上有三種不同的電視制式:①NTSC;②PAL;③SECAMNTSC(nationaltelevisionsystemcommittee),

是國家電視制式委員會(huì)的縮寫。美國研制的一種與黑白電視兼容的彩色電視制式。幀頻：每秒播放30幀畫面掃描行數(shù)（掃描分辨率）：每幀有526行像素美國、加拿大、日本、韓國、菲律賓、臺灣等

NTSC制式優(yōu)點(diǎn)：在信號傳輸無失真情況下，具有比較高彩色圖像質(zhì)量；兼容性好；重現(xiàn)的彩色圖像無明顯的“爬行”和亮度閃爍現(xiàn)象；較易于實(shí)現(xiàn)信號處理；色度信號的形成和分離都比較簡單。PAL(PhaseAlternationLine),

是相位逐行交替的縮寫。西德在1962年研制的一種與黑白電視兼容的彩色電視制式。幀頻：每秒播放25幀畫面掃描行數(shù)（掃描分辨率）：每幀有625行像素西歐國家、新加坡、澳大利亞、中國大陸以及香港等

PAL制式基本原理：采用逐行倒相正交平衡調(diào)幅的色度信號，解調(diào)時(shí)先經(jīng)過逐行梳狀濾波器將色度信號分離后再同步檢波；最后利用視覺平均作用補(bǔ)償小幅度串色所引起的彩色偏差。

PAL制式優(yōu)點(diǎn)：對相位失真不敏感，多徑接收對PAL信號影響小。SECAM(SequentialCouleurAvecMemoire)

是順序與存儲(chǔ)彩色電視系統(tǒng)的縮寫。法國研制的一種與黑白電視兼容的彩色電視制式；幀頻：每秒播放25幀畫面掃描行數(shù)（掃描分辨率）：每幀有625行像素

法國、俄羅斯等東歐國家和中東一帶

SECAM制式優(yōu)點(diǎn)：傳輸失真對色度信號影響小，大面積彩色圖像幾乎不受微分增益和微分相位失真的影響，受傳輸通道頻率特性和多徑接收的影響也不大。SECAM是一種順序同時(shí)制。是采用錯(cuò)開傳輸時(shí)間的方法（時(shí)分原則）來避免串色以及造成的彩色失真。SECAM編碼解碼方式與PAL制式完全不同。不同電視制式的技術(shù)指標(biāo)TV制式NTSCPALSECAM幀頻/Hz302525行/幀525625625亮度帶寬/MHz4.26.06.0彩色幅載波/MHz3.584.434.25色度帶寬/MHz1.3(I)，0.6(Q)1.3(U)，1.3(V)>1.0(U)，>1.0(V)聲音載波/MHz4.56.56.55.2.2視頻信號的數(shù)字化（1）復(fù)合數(shù)字化：先用高速模/數(shù)轉(zhuǎn)換器對彩色全電視信號進(jìn)行數(shù)字化，然后在數(shù)字域中進(jìn)行分離亮度和色度，以獲得所希望的YUV（PAL，SECAM制）分量或YIQ（NTSC制）分量，最后轉(zhuǎn)換成RGB分量數(shù)據(jù)。此種方法稱為復(fù)合數(shù)字化。（2）分量數(shù)字化：從復(fù)合彩色電視圖像中分離出彩色分量的亮度和色度，得到Y(jié)UV或YIQ分量，然后用3個(gè)模/數(shù)轉(zhuǎn)換器對3個(gè)分量分別進(jìn)行數(shù)字化，最后再轉(zhuǎn)換成RGB空間，此種方法稱為分量數(shù)字化。

分量數(shù)字化是視頻信號數(shù)字化的主流。1．視頻信號數(shù)字化方法分類2．視頻信號采樣結(jié)構(gòu)的選擇

概念：采樣結(jié)構(gòu)是指采樣點(diǎn)在空間與時(shí)間上的相對位置。

采樣結(jié)構(gòu)分類：正交結(jié)構(gòu)：在圖像平面上沿著水平方向采樣點(diǎn)等間隔排列，沿垂直方向采樣點(diǎn)上下對齊排列。行交叉結(jié)構(gòu)：每行內(nèi)采樣點(diǎn)數(shù)為整數(shù)加半個(gè)。（a）正交結(jié)構(gòu)（b）行交叉結(jié)構(gòu)3．?dāng)?shù)字視頻的采樣格式

在復(fù)合電視信號中，亮度信號的帶寬是色度信號帶寬的兩倍。因此其數(shù)字化時(shí)可采用對信號的色差分量的采樣率低于對亮度分量的采樣率。用Y:U:V來表示YUV三分量的采樣比例，則數(shù)字視頻的采樣格式有如下4種：

（1）Y:U:V=4:4:4

指在每條掃描線上在水平和垂直方向上每4個(gè)連續(xù)的取樣點(diǎn)取4個(gè)亮度Y樣本、4個(gè)紅色差Cr樣本和4個(gè)藍(lán)色差Cb樣本，相當(dāng)于每個(gè)像素包含3個(gè)樣本。即對每個(gè)采樣點(diǎn)，亮度Y、色差U和V各取一個(gè)樣本，也就是每個(gè)像素用3個(gè)樣本表示。

采樣格式××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××4:4:4采樣格式4:2:2采樣格式×表示亮度Y采樣點(diǎn)○表示色度UV采樣點(diǎn)

（2）Y:U:V=4:2:2

這種方式指在每條掃描線上，在每4個(gè)連續(xù)的采樣點(diǎn)上，取4個(gè)亮度Y的樣本值，而色差U、V分別取其第一點(diǎn)和第三點(diǎn)的樣本值，共8個(gè)樣本，平均每個(gè)像素用2個(gè)樣本表示。這種方式能給信號的轉(zhuǎn)換留有一定余量，效果更好一些。這是通常所用的方式，每4個(gè)連續(xù)的采樣點(diǎn)取4個(gè)亮度Y樣本、2個(gè)紅色差Cr樣本和2個(gè)藍(lán)色差Cb樣本，結(jié)果相當(dāng)于平均每個(gè)像素用2個(gè)樣本表示。

色度信號在水平方向上采樣點(diǎn)數(shù)為亮度信號的一半，而在垂直方向上的采樣點(diǎn)數(shù)相同。

（3）Y:U:V=4:1:1這種方式是在每4個(gè)連續(xù)的采樣點(diǎn)上，取4個(gè)亮度Y的樣本值，而色差U、V分別取其第一點(diǎn)的樣本值，共6個(gè)樣本，每個(gè)像素用1.5個(gè)樣本表示。

色差信號在在水平方向上采樣點(diǎn)數(shù)為亮度信號的1/4，而在垂直方向上的采樣點(diǎn)數(shù)相同。采樣格式××××××××××××××××××××××××××××××4:1:1采樣格式×表示亮度Y采樣點(diǎn)○表示色度UV采樣點(diǎn)（4）Y:U:V=4:2:04:2:0子采樣格式是指分別在水平和垂直方向上每2個(gè)連續(xù)的采樣點(diǎn)上取2個(gè)亮度Y樣本、1個(gè)紅色差Cr樣本和1個(gè)藍(lán)色差Cb樣本，平均每個(gè)像素用1.5個(gè)樣本表示。色差信號分別在水平方向和垂直方向上采樣點(diǎn)數(shù)為亮度信號的1/2。采樣格式4:2:0采樣格式4:2:0采樣格式×表示亮度Y采樣點(diǎn)○表示色度UV采樣點(diǎn)MPEG1、H.261支持MPEG2支持掃描方式小結(jié)電視圖像既是空間的函數(shù)，也是時(shí)間的函數(shù)，而且又是隔行掃描式，所以其采樣方式比掃描儀掃描圖像的方式要復(fù)雜得多。分量采樣時(shí)采到的是隔行樣本點(diǎn)，要把隔行樣本組合成逐行樣本，然后進(jìn)行樣本點(diǎn)的量化，YUV到RGB色彩空間的轉(zhuǎn)換等，最后才能得到數(shù)字視頻數(shù)據(jù)。

4．?dāng)?shù)字視頻標(biāo)準(zhǔn)為了在PAL、NTSC和SECAM電視制式之間確定共同的數(shù)字化參數(shù)，國際無線電咨詢委員會(huì)（CCIR）制訂了廣播級質(zhì)量的數(shù)字電視編碼標(biāo)準(zhǔn)，稱為CCIR601標(biāo)準(zhǔn)。該標(biāo)準(zhǔn)規(guī)定了彩色電視圖像轉(zhuǎn)換成數(shù)字圖像時(shí)使用的采樣頻率，彩色空間之間的轉(zhuǎn)換關(guān)系等。（1）采樣頻率ITU-RBT.601標(biāo)準(zhǔn)為三種電視制式規(guī)定了共同的電視圖像采樣頻率。其基本的計(jì)算方法是：對PAL制、SECAM制，采樣頻率fs為：fs=625×25×N=15625×N=13.5MHz，N=864其中：N為每一掃描行上的采樣數(shù)目。在PAL制、SECAM制中，625是指行數(shù)，25表示每秒幀數(shù)。

（2）有效顯示分辨率對PAL制和SECAM制的亮度信號，每一條掃描行采樣864個(gè)樣本；對NTSC制的亮度信號，每一條掃描行采樣858個(gè)樣本。為了使這些制式的采樣點(diǎn)兼容，規(guī)定每一掃描行的有效樣本數(shù)均為720個(gè)。（3）數(shù)據(jù)量CCIR601規(guī)定，每個(gè)樣本點(diǎn)都按8位數(shù)字化，即有256個(gè)等級。但實(shí)際上亮度信號占220級、色度信號占225級，其他位作同步、編碼等控制用。如果按fs的采樣率和4:2:2的格式采樣，則數(shù)字視頻的數(shù)據(jù)量為：

13.5(MHz)×8(bit)+2×6.75(MHz)×8(bit)=27MB/s

（4）CIF、QCIF和SQCIF為了兼容625行的電視圖像和525行的電視圖像，CCITT定義了公用中分辨率格式CIF（CommonIntermediateFormat），1/4公用中分辨率格式（Quarter-CIF，QCIF）和（Sub-QuarterCommonIntermediateFormat，SQCIF）格式。CIF格式具有如下特性：

電視圖像的空間分辨率為352×288。

使用非隔行掃描（Non-InterlacedScan）。

使用NTSC幀速率，電視圖像的最大幀速率為30000/1001≈29.97幅/秒。CIFQCIFSQCIF行數(shù)/幀像素/行行數(shù)/幀像素/行行數(shù)/幀像素/行亮度（Y）288360(352)144180(176)96128色度（Cb）144180(176)7290(88)4864色度（Cr）144180(176)7290(88)4864下表是CIF、QCIF和SQCIF圖像格式參數(shù)。5.3視頻信號編碼方法一、視頻信號編碼的依據(jù)：1、視頻信號編碼的出發(fā)點(diǎn)：

對于活動(dòng)圖像，相鄰幀的時(shí)間間隔很短(1/251/30s),在景物運(yùn)動(dòng)不很劇烈場合，相鄰幀間相關(guān)性很強(qiáng)。編碼時(shí)充分利用活動(dòng)圖像的相鄰幀(在時(shí)間軸方向)的相關(guān)性進(jìn)行預(yù)測。2、視頻信號編碼的依據(jù)：

依據(jù)1：從信源角度看，自然景物大多都處于相對不變或緩變狀態(tài)，為幀間相關(guān)性存在前提條件。5.3.1視頻信號編碼基礎(chǔ)幀間預(yù)測典型情況：可視電話圖像可視電話圖像內(nèi)容通常為一個(gè)細(xì)節(jié)不十分復(fù)雜背景前，有一個(gè)活動(dòng)量不大的單個(gè)人物的頭-肩像。假定人位置在第k幀與第k-1幀相比有一定x方向位移,可將畫面分為3個(gè)各具特點(diǎn)區(qū)域：背景區(qū)、運(yùn)動(dòng)物體區(qū)、暴露區(qū)背景區(qū)：指攝像機(jī)不動(dòng)而攝取人物后面的背景。一般背景區(qū)是靜止的，若外界條件不變，則這兩幀背景區(qū)絕大部分?jǐn)?shù)據(jù)相同，意味著兩幀背景區(qū)之間幀間相關(guān)性很強(qiáng)。運(yùn)動(dòng)物體區(qū)：若將物體運(yùn)動(dòng)近似看作簡單平移，則第k幀與第k-1幀的運(yùn)動(dòng)區(qū)的數(shù)據(jù)也基本相同。簡單平移看作只有x方向位移量Dx，則可采用某種位移估值方法對位移量進(jìn)行“運(yùn)動(dòng)補(bǔ)償”。暴露區(qū)：指在運(yùn)動(dòng)后所暴露出的原來曾被物體遮蓋住區(qū)域。若有存儲(chǔ)器將這暴露區(qū)的數(shù)據(jù)暫時(shí)存儲(chǔ)，則再次經(jīng)遮蓋后再暴露出來的數(shù)據(jù)與原先存儲(chǔ)數(shù)據(jù)相同，這為一幀間相關(guān)性。注意：如果將整個(gè)畫面從一類景物切換為另一類景物時(shí)，則談不上幀間相關(guān)性利用。因?yàn)檎麄€(gè)畫面內(nèi)容數(shù)據(jù)全部改變了。這三類區(qū)域的幀間相關(guān)性是幀間壓縮編碼的重要依據(jù)。

依據(jù)2：利用人眼視覺特性，在活動(dòng)圖像編碼中針對圖像內(nèi)容在清晰度和活動(dòng)性(幀頻)適當(dāng)調(diào)整碼率，可使重建圖像在視覺上保持一致主觀效果。保證對于傳輸序列圖像的靜止部分的較高空間分辨率。同時(shí)，可降低時(shí)間軸分辨率，通過抽幀或跳幀減少傳輸幀數(shù)，在接收端依靠幀存儲(chǔ)器把未傳輸幀補(bǔ)充?？山档托蛄袌D像中的運(yùn)動(dòng)物體部分的分辨率。物體的運(yùn)動(dòng)速度愈高，可用更低清晰度進(jìn)行傳輸。二、視頻信號編碼的關(guān)鍵問題：對于序列圖像中大量存在的靜止或緩變區(qū)域，如何把運(yùn)動(dòng)區(qū)域和靜止或緩變區(qū)域分割開來？？對于靜止區(qū)域如何壓縮編碼？？對于運(yùn)動(dòng)區(qū)域如何壓縮編碼？？如何把運(yùn)動(dòng)區(qū)域和靜止或緩變區(qū)域分割？設(shè)第k幀圖像位于位置z=(x,y)的像素采樣值為Ik(z)。其預(yù)測值為第k-1幀圖像(前一幀圖像)的相對應(yīng)同一位置處像素復(fù)原值I’k-1(z)。則有：定義一閾值TH，則有：若|FDk(z)|TH

，認(rèn)為Ik(z)位于圖像相對靜止部分

(背景區(qū))

若|FDk(z)|TH

，認(rèn)為Ik(z)位于圖像運(yùn)動(dòng)區(qū)域。幀間差如何對于靜止或緩變區(qū)域壓縮編碼？幀（場）重復(fù)工作形式：通常用在可視電話等傳輸碼率很低應(yīng)用場合。在序列圖像傳輸中進(jìn)行抽幀，使少傳一些幀。在接收端可以采用對前幀重復(fù)讀出方式補(bǔ)滿。如何對于運(yùn)動(dòng)區(qū)域壓縮編碼？運(yùn)動(dòng)估計(jì)與補(bǔ)償預(yù)測方法：相鄰畫面高度相似，其中差別變化是由于物體運(yùn)動(dòng)或攝象機(jī)運(yùn)動(dòng)所引起的。畫面中物體或像素的運(yùn)動(dòng)是可以估計(jì)的。因此，可以從前面的畫面預(yù)測當(dāng)前畫面，編碼器只對預(yù)測誤差進(jìn)行編碼。不能進(jìn)行預(yù)測的畫面或區(qū)域使用JPEG進(jìn)行編碼（利用畫面內(nèi)部相關(guān)性）。相鄰幀間的主要變化是由于構(gòu)成景物的各物體的運(yùn)動(dòng)引起的。5.3.2運(yùn)動(dòng)估計(jì)與補(bǔ)償?shù)幕靖拍?/p>

定義：將活動(dòng)圖像分為若干個(gè)塊，檢測出當(dāng)前幀中每個(gè)塊在前一幀(參考幀)圖像中的對應(yīng)位置，從而可以估計(jì)出這個(gè)塊的位移，用運(yùn)動(dòng)矢量表示。這個(gè)過程叫做運(yùn)動(dòng)估計(jì)。

運(yùn)動(dòng)估計(jì)通常以宏塊為單位進(jìn)行，計(jì)算被壓縮圖像與參考圖像在對應(yīng)位置處的宏塊間的位置偏移。該位置偏移是以運(yùn)動(dòng)矢量描述，代表水平和垂直兩個(gè)方向的位移。1.運(yùn)動(dòng)估計(jì)場景中物體運(yùn)動(dòng)反映在畫面中，表現(xiàn)為當(dāng)前畫面部分內(nèi)容是前一畫面部分內(nèi)容的位移運(yùn)動(dòng)。2.運(yùn)動(dòng)補(bǔ)償

定義：就是根據(jù)求出的運(yùn)動(dòng)矢量，找到當(dāng)前幀的像素（或像素塊）是從前一幀的哪個(gè)位置移動(dòng)過來的，從而得到當(dāng)前幀像素（或像素塊）的預(yù)測值。由于用當(dāng)前幀在前一幀圖像中對應(yīng)部分來對當(dāng)前幀進(jìn)行預(yù)測，而相鄰兩幀中對應(yīng)的運(yùn)動(dòng)部分圖像信息會(huì)有所不同，所以一般會(huì)產(chǎn)生補(bǔ)償殘差。

運(yùn)動(dòng)估計(jì)及補(bǔ)償?shù)幕驹恚豪脦g運(yùn)動(dòng)估計(jì)得到待編碼圖像塊的一個(gè)（或多個(gè)）參考塊，然后用這個(gè)參考塊進(jìn)行運(yùn)動(dòng)補(bǔ)償，將補(bǔ)償后殘差進(jìn)行DCT變換和可變長編碼。3.運(yùn)動(dòng)補(bǔ)償幀間預(yù)測編碼定義：對于運(yùn)動(dòng)的物體，如果能估計(jì)出物體在相鄰幀內(nèi)的相對位移，那么用上一幀中物體的對應(yīng)區(qū)域?qū)Ξ?dāng)前幀物體進(jìn)行預(yù)測，編碼傳輸預(yù)測誤差部分，就可壓縮這部分區(qū)域的碼率。這種考慮了運(yùn)動(dòng)物體對應(yīng)區(qū)域的位移或運(yùn)動(dòng)的預(yù)測方式稱為運(yùn)動(dòng)補(bǔ)償幀間預(yù)測編碼。幀間運(yùn)動(dòng)估計(jì)與補(bǔ)償預(yù)測的基本過程運(yùn)動(dòng)補(bǔ)償幀間預(yù)測編碼原理框圖：+-熵編碼幀間預(yù)測器運(yùn)動(dòng)補(bǔ)償壓縮圖像塊輸入圖像塊enfnfn運(yùn)動(dòng)補(bǔ)償預(yù)測幀間誤差圖像運(yùn)動(dòng)補(bǔ)償預(yù)測圖像其中：fn為輸入圖像塊；fn為運(yùn)動(dòng)補(bǔ)償預(yù)測圖像運(yùn)動(dòng)補(bǔ)償幀間預(yù)測編碼技術(shù)的組成：物體的劃分：劃分靜止區(qū)域和運(yùn)動(dòng)區(qū)域。這里假設(shè)運(yùn)動(dòng)物體僅作平移。

運(yùn)動(dòng)估計(jì)：對每一個(gè)運(yùn)動(dòng)物體進(jìn)行位移估計(jì)。

運(yùn)動(dòng)補(bǔ)償：由位移估值建立同一運(yùn)動(dòng)物體在不同幀空間位置對應(yīng)關(guān)系，建立預(yù)測關(guān)系。

補(bǔ)償后的預(yù)測信息編碼：對運(yùn)動(dòng)物體的補(bǔ)償后的位移幀差信號DFD，以及運(yùn)動(dòng)矢量等進(jìn)行編碼傳輸。5.3.3基于塊的運(yùn)動(dòng)估計(jì)—塊匹配算法塊匹配算法通過對圖像序列中相鄰兩幀圖像間的子塊匹配來進(jìn)行運(yùn)動(dòng)估計(jì)。前提條件：在塊匹配算法中，圖像被分割為子塊，把子塊分成靜止和運(yùn)動(dòng)兩類，運(yùn)動(dòng)子塊中的所有像素的運(yùn)動(dòng)矢量被認(rèn)為相同，都只作相等的平移?；舅枷耄簩τ趲琸(當(dāng)前幀)中像素(n1,n2)的位移，通過考慮一個(gè)中心定位在(n1,n2)的塊，搜索幀來找出同樣大小的最佳匹配塊的位置來確定。1.基本思想

初始搜索點(diǎn)的選擇。①直接選擇參考幀對應(yīng)塊中心位置；②選擇預(yù)測的起點(diǎn)。

匹配準(zhǔn)則。一般方法有均方誤差函數(shù)和平均絕對誤差函數(shù)等準(zhǔn)則。

搜索方法。有全搜索、三步搜索、交叉搜索、分層運(yùn)動(dòng)估計(jì)算法等。

塊的大小選擇。塊的大小應(yīng)滿足下列要求：每一個(gè)塊幾乎都只具有單一運(yùn)動(dòng)或者沒有運(yùn)動(dòng)。塊不能過小，以保證可以搜索到正確的塊。目前塊大小用較多為16，有時(shí)也取4，8。2.提高搜索效率的主要技術(shù)常用的匹配準(zhǔn)則給定兩個(gè)圖像塊Bi和Bi-1，均方誤差絕對誤差求這兩個(gè)誤差函數(shù)對應(yīng)最小值時(shí)(?x,?y)為最佳運(yùn)動(dòng)估計(jì)⑴全搜索算法（FS）基本思想：要估計(jì)一個(gè)像素的位移(運(yùn)動(dòng))時(shí)，在當(dāng)前幀中取以該像素為中心的一個(gè)子塊，然后在前一幀圖像中所有可能位置尋找一個(gè)與之最匹配(相關(guān)最大)的子塊，則匹配子塊中心與當(dāng)前幀中子塊中心的位移即為估計(jì)的位移(運(yùn)動(dòng))矢量。匹配準(zhǔn)則：最小平均絕對誤差函數(shù)（MAD)設(shè)將當(dāng)前幀中劃分為NN像素子塊，A為待處理的子塊。水平和垂直方向最大位移均為dm。3.典型的塊匹配算法塊匹配算法就是在其前一幀以A為中心的搜索區(qū)SR:

(N+2dm)(N+2dm)內(nèi)尋找一個(gè)與A相關(guān)性最大的同樣大小的子塊B，B與A的坐標(biāo)偏移量即為估計(jì)的子塊A的運(yùn)動(dòng)矢量設(shè)B與A的坐標(biāo)偏移量為(i，j)，則：平均絕對

誤差MAD第k幀灰度值則在某一個(gè)位置偏移(i，j)下有最小誤差minij，選定一閾值T，則有：當(dāng)minij

T，說明在一定誤差范圍內(nèi)達(dá)到匹配，運(yùn)動(dòng)矢量為dx=i，dy=j當(dāng)minij

>T，說明不能匹配。應(yīng)該對該子塊直接幀內(nèi)編碼。在全搜索條件下，塊匹配算法達(dá)到全局最優(yōu)，但缺點(diǎn)為運(yùn)算量大，總共要計(jì)算(1+2dm)(1+2dm)次匹配運(yùn)算，且搜索算法時(shí)間占到整個(gè)編碼時(shí)間的50%~80%。⑵二維對數(shù)算法（TDL）開創(chuàng)了快速算法的先例。基本思想：從原點(diǎn)開始，以“十”字形分布的五個(gè)點(diǎn)構(gòu)成每次搜索的點(diǎn)群，通過快速搜索跟蹤最匹配點(diǎn)。算法步驟：從原點(diǎn)開始，選取一定的步長，在以“十”字形分布的五個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算并比較若最匹配點(diǎn)在邊緣四個(gè)點(diǎn)處，則以該點(diǎn)作為中心點(diǎn)，保持步長不變，重新搜索“十”字形分布的五個(gè)點(diǎn)若最匹配點(diǎn)位于中心點(diǎn)，則保持中心點(diǎn)位置不變，將步長減半，構(gòu)成“十”字形點(diǎn)群，在五個(gè)點(diǎn)處計(jì)算若步長為1，在中心及周圍8個(gè)點(diǎn)處找出最匹配點(diǎn)，該點(diǎn)所在位置即對應(yīng)最佳運(yùn)動(dòng)矢量，算法結(jié)束；否則，重復(fù)第2步算法搜索過程圖示：11111222223333344444-7-6-5-4-3-2-101234567-7-6-5-4-3-2-1012345674444算法搜索過程圖示：起初步長=2⑶三步搜索法（TSS）基本思想：搜索范圍為7。即在上一幀以當(dāng)前子塊為原點(diǎn)，將當(dāng)前子塊在其上下左右距離為7范圍內(nèi)按一定規(guī)則移動(dòng)，每移動(dòng)到一個(gè)位置，取出同樣大小的子塊與當(dāng)前子塊進(jìn)行匹配計(jì)算。匹配準(zhǔn)則：最小均方誤差函數(shù)(MSE)或最小平均絕

對誤差函數(shù)（MAD)具體方法：第一步：在搜索范圍內(nèi)，以當(dāng)前子塊為中心，以4為步幅。選擇標(biāo)記為“1”的9個(gè)點(diǎn)分別為中心位置的子塊與當(dāng)前子塊進(jìn)行匹配，求出最佳匹配的子塊中心位置，然后把中心位置移到該點(diǎn)。如果在某點(diǎn)找到最小的MSE或MAD，則表示在該點(diǎn)一定范圍內(nèi)達(dá)到最佳匹配。第二步：以第一步求出最佳子塊為中心，以2為步幅。選擇9個(gè)標(biāo)記為“2”點(diǎn)分別為中心位置的子塊與當(dāng)前子塊進(jìn)行匹配，求出最佳匹配的子塊中心位置，然后把中心位置移到該點(diǎn)。第三步：以第二步求出最佳子塊為中心，以1為步幅。選擇9個(gè)標(biāo)記為“3”點(diǎn)分別為中心位置的子塊與當(dāng)前子塊進(jìn)行匹配，求出最佳匹配的子塊中心位置。則它與當(dāng)前子塊中心位置偏移量為估計(jì)的位移量。結(jié)論：在dm=7時(shí)，三步法僅需要39-7=25次匹配，比全搜索算法匹配次數(shù)少很多。三步搜索算法111111111222222222333333333搜索9+8+8＝25次-7-6-5-4-3-2-101234567-7-6-5-4-3-2-101234567

⑷交叉法（CSA）是在TDL、TSS基礎(chǔ)上為進(jìn)一步減少計(jì)算量發(fā)展起來的基本思想：從原點(diǎn)開始，以“×”字形分布的五個(gè)點(diǎn)構(gòu)成搜索點(diǎn)群，以TDL的搜索方式搜索最匹配點(diǎn)，僅在最后一步采用“十”字形點(diǎn)群算法描述：從原點(diǎn)開始，選取最大搜索長度的一半作為步長，在以“×”字形分布的五個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算并比較以上一步的最匹配點(diǎn)為中心，步長減半，繼續(xù)進(jìn)行“×”字形五點(diǎn)搜索，若步長大于1，重復(fù)本步；若步長為1，則進(jìn)行第三步若上一步最匹配點(diǎn)處于中心點(diǎn)、左下角或右上角，做“十”字形搜索；若上一步最匹配點(diǎn)處于左上角或右下角，則做“×”字形搜索。搜索到的最匹配點(diǎn)為最佳運(yùn)動(dòng)矢量，算法結(jié)束交叉法搜索過程圖示：111112222233333搜索5+4+4＝13次-7-6-5-4-3-2-101234567-7-6-5-4-3-2-101234567

⑸四步搜索法（FSS）基本思路現(xiàn)實(shí)中序列圖像的運(yùn)動(dòng)矢量大多都是中心分布的，從而在5×5大小的搜索窗口上構(gòu)造了有9個(gè)檢測點(diǎn)的搜索模板步驟以搜索區(qū)域原點(diǎn)為中心選定5×5的搜索窗，然后在9個(gè)檢測點(diǎn)處進(jìn)行匹配計(jì)算若最匹配點(diǎn)位于中心點(diǎn)，跳到第3步，即縮小搜索窗口為3×3最匹配點(diǎn)不在中心點(diǎn)，跳到第2步窗口保持5×5，搜索模式改變上一步最匹配點(diǎn)位于窗口4個(gè)角上，則另外再搜索5個(gè)檢測點(diǎn)上一步最匹配點(diǎn)位于窗口的4邊中心點(diǎn)處，則需再搜索3個(gè)檢測點(diǎn)若這一次的最匹配點(diǎn)在窗口中心，則跳到第3步，否則，重復(fù)本步將窗口縮小到3×3，計(jì)算出最匹配點(diǎn)的位置即對應(yīng)最佳運(yùn)動(dòng)矢量四步搜索法過程圖示1111111112222333333444444444-7-6-5-4-3-2-101234567-7-6-5-4-3-2-101234567最匹配點(diǎn)分別為：(0,-2)(2,-4)(2,-4)(3,-4),搜索共分4步。

⑹菱形搜索法（DS）本算法經(jīng)過多次改進(jìn)，已成為目前快速匹配算法中性能最優(yōu)異的算法之一；1999年10月，DS算法被MPEG-4國際標(biāo)準(zhǔn)采用并收入驗(yàn)證模型?；舅枷耄菏褂脙煞N搜索模板，9個(gè)檢測點(diǎn)的大模板LDSP和5個(gè)檢測點(diǎn)的SDSP

搜索時(shí)，先用大模板計(jì)算，當(dāng)最匹配塊出現(xiàn)在中心點(diǎn)處時(shí)，換大模板為小模板，再進(jìn)行匹配計(jì)算，5個(gè)點(diǎn)中的最匹配點(diǎn)即為最優(yōu)點(diǎn)。大模板LDSP小模板SDSP算法步驟：用LDSP在搜索區(qū)域中心及周圍8個(gè)點(diǎn)處進(jìn)行匹配計(jì)算，若最匹配點(diǎn)位于中心，則進(jìn)行

Step3；否則，到Step2

以上一次找到的最匹配點(diǎn)為中心點(diǎn)，用新的LDSP來計(jì)算，若最匹配點(diǎn)位于中心點(diǎn)，則進(jìn)行Step3；否則，重復(fù)本步以上一次找到的最匹配點(diǎn)為中心點(diǎn)，將LDSP換為SDSP，在5個(gè)點(diǎn)處計(jì)算，找到最匹配點(diǎn)，該點(diǎn)所在位置即為最佳運(yùn)動(dòng)矢量。菱形搜索算法過程圖示1111111112222223333344444-7-6-5-4-3-2-101234567-7-6-5-4-3-2-101234567最匹配點(diǎn)分別為：(2,0)(2,-2)(2,-2)(2,-3),使用３次LDSP和１次SDSP,搜索共分5步。菱形搜索算法分析選用了大小兩種形狀的搜索模板，先用LDSP搜索，步長大，搜索范圍廣，進(jìn)行粗定位，避免搜索窗口太小時(shí)，陷入局部最優(yōu)；粗定位后，再用SDSP準(zhǔn)確定位，保證匹配精度從前圖中可看出，搜索時(shí)各步之間相關(guān)性強(qiáng)，模板移動(dòng)只需要在幾個(gè)新的檢測點(diǎn)處進(jìn)行匹配計(jì)算，提高了搜索速度復(fù)習(xí)：視頻信號編碼技術(shù)————

運(yùn)動(dòng)補(bǔ)償幀間預(yù)測編碼技術(shù)物體的劃分：劃分靜止區(qū)域和運(yùn)動(dòng)區(qū)域。這里假設(shè)運(yùn)動(dòng)物體僅作平移。

運(yùn)動(dòng)估計(jì)：對每一個(gè)運(yùn)動(dòng)物體進(jìn)行位移估計(jì)。

運(yùn)動(dòng)補(bǔ)償：由位移估值建立同一運(yùn)動(dòng)物體在不同幀空間位置對應(yīng)關(guān)系，建立預(yù)測關(guān)系。

補(bǔ)償后的預(yù)測信息編碼：對運(yùn)動(dòng)物體的補(bǔ)償后的位移幀差信號，以及運(yùn)動(dòng)矢量等進(jìn)行編碼傳輸。②③④抽幀或跳幀復(fù)習(xí)：如何實(shí)現(xiàn)運(yùn)動(dòng)矢量估計(jì)？——塊匹配算法

初始搜索點(diǎn)的選擇。①直接選擇參考幀對應(yīng)塊中心位置；②選擇預(yù)測的起點(diǎn)。

匹配準(zhǔn)則。一般方法有均方誤差函數(shù)和平均絕對誤差函數(shù)等準(zhǔn)則。

搜索方法。有全搜索、三步搜索、交叉搜索等。

塊的大小選擇。塊的大小應(yīng)滿足下列要求：每一個(gè)塊幾乎都只具有單一運(yùn)動(dòng)或者沒有運(yùn)動(dòng)。塊不能過小，以保證可以搜索到正確的塊。目前塊大小用較多為16，有時(shí)也取4，8。復(fù)習(xí)：塊匹配方法全搜索算法二維對數(shù)搜索算法三步搜索算法交叉法四步搜索算法菱形（鉆石形）搜索算法②以“十”字形分布的五個(gè)點(diǎn)構(gòu)成每次搜索的點(diǎn)群，若步長為1，周圍8鄰域匹配。③搜索范圍為7—“4-2-1”④以“×”字形的五個(gè)點(diǎn)構(gòu)成搜索點(diǎn)群，若步長為1，上一步最匹配點(diǎn)處于中心點(diǎn)、左下角或右上角，“十”字形搜索；若處于左上角或右下角，則“×”字形搜索。⑤“5×5”的搜索窗口，若步長為1，則“3×3”的搜索窗口⑥9個(gè)檢測點(diǎn)的大模板LDSP和5個(gè)檢測點(diǎn)的SDSP大模板LDSP小模板SDSP整像素運(yùn)動(dòng)估計(jì)

⑺

亞像素搜索法（DS）前幾種運(yùn)動(dòng)估計(jì)算法，得到的運(yùn)動(dòng)矢量為整數(shù)值，稱之為整像素精度運(yùn)動(dòng)估計(jì)。在塊匹配算法中，搜索相應(yīng)塊的步長不一定是整數(shù)。也就是實(shí)際圖像的運(yùn)動(dòng)并不一定是整像素，所以，整像素運(yùn)動(dòng)估計(jì)有一定的誤差。為進(jìn)一步提高精度，希望估計(jì)到的運(yùn)動(dòng)矢量為分?jǐn)?shù)像素?cái)?shù)，或稱亞像素。使用亞像素步長的一個(gè)問題是對于當(dāng)前幀里給定的一個(gè)采樣點(diǎn)，在參考幀里可能沒有相應(yīng)的采樣點(diǎn)，必須由可利用的樣點(diǎn)內(nèi)插得到。對圖像進(jìn)行插值運(yùn)算，得到整像素點(diǎn)之間的分?jǐn)?shù)像素點(diǎn)的值，然后再進(jìn)行運(yùn)動(dòng)估計(jì)。塊匹配搜索移動(dòng)時(shí)，塊中心點(diǎn)可以和分?jǐn)?shù)像素點(diǎn)對準(zhǔn)，使得到更精確的運(yùn)動(dòng)矢量。

MPEG和H.263均采用了1/2像素精度運(yùn)動(dòng)估計(jì)，證實(shí)了比整數(shù)運(yùn)動(dòng)估計(jì)更有效。

H.264采用了1/4像素精度運(yùn)動(dòng)估計(jì).插值算法：一般采用雙線性插值?！痢痢痢痢琳袼匚恢谩癜胂袼匚恢貌捎秒p線性內(nèi)插法實(shí)現(xiàn)半像素精度預(yù)測5.3.4基于像素的運(yùn)動(dòng)估計(jì)在基于像素的運(yùn)動(dòng)估計(jì)中，對每個(gè)像素估計(jì)其運(yùn)動(dòng)矢量，顯然這個(gè)問題難以處理：如果使用恒定亮度假設(shè)，對于參考幀的每個(gè)像素，在目標(biāo)幀里將會(huì)有許多完全相同亮度的像素在圖像編碼的發(fā)展過程中，該辦法曾起過重要作用，但沒有被標(biāo)準(zhǔn)所采用。實(shí)驗(yàn)研究也表明，它的有效性不如塊匹配