華中科技大學(xué)碩士學(xué)位論文 摘要 。近年來，隨著計算機網(wǎng)絡(luò)和通信等技術(shù)的發(fā)展，多媒體得到了越來越多的重 視和應(yīng)用。視頻壓縮技術(shù)是現(xiàn)代多媒體編碼技術(shù)中最重要的研究領(lǐng)域。本文開展 了這方面的初步研究，重點集中在視頻壓縮中相當(dāng)關(guān)鍵的運動估計算法上。少7 數(shù)據(jù)壓縮原理在于原始數(shù)據(jù)中存在著各種冗余。多媒體中的視頻編碼技術(shù)主 要是通過消除幀內(nèi)的空間冗余和幀間的時間冗余來實現(xiàn)數(shù)據(jù)的壓縮。在消除時間 冗余方面，幀間塊匹配技術(shù)是比較完善的，其原理是用前一幀中的一個圖像塊來 最大地近似當(dāng)前編碼塊。如何盡快地找到這個最佳塊便是快速搜索算法所要完成 的工作， 針對視頻編碼系統(tǒng)運動估計的幾種常用編碼方法，包括三步法、正交共軛法、 象限法等，我們分析了它們的優(yōu)缺點。我們對正交共軛法進(jìn)行了改進(jìn)，提高了原 有算法最佳匹配點的命中率。 上述快速算法因為搜索區(qū)域有空白區(qū)而可能在搜索時會遺漏全局極值點而陷 入局部極值區(qū)域。本文又提出了預(yù)測起始搜索點的運動估計算法，對搜索的起始 位置進(jìn)行修訂來盡可能地接近全局最優(yōu)點，同時也在一定程度上將多極值問題變 成單極值問題。另外該算法還對門限值的選取進(jìn)行了改進(jìn)，進(jìn)一步加快了搜索匹 配的速度。實驗表明，該算法能在大幅度減少搜索步數(shù)的同時還能保持較高的信 噪比。與傳統(tǒng)的三步法和正交共軛法相比，改進(jìn)算法由于搜索路徑固定且前后點 無關(guān)，因此適合用硬件實現(xiàn)多線程的搜索。 關(guān)鍵詞：視頻編碼，運動估計，快速搜索算法，多極值，起始搜索點 華中科技大學(xué)碩士學(xué)位論文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft e c h n o l o g yo fc o m p u t e rn e t w o r ka n dc o m m u n i c a t i o n ， m u l t i m e d i ah a v eb e e no b t a i n i n gm o r ea n dm o r ee m p h a s i s a n da p p l i c a t i o n t h e t e c h n o l o g yo fv i d e oe n c o d i n gi st h em o s ti m p o r t a n tr e s e a r c hd o m a i n i nt h em u l t i m e d i a a c c o r d i n gt ot h i ss i t u a t i o n ，w ed i ds o m er e s e a r c ha n df o c u s e do nt h ev i d e om o t i o n e s t i m a t i o ni nt h ev i d e oc o d i n gs y s t e m t h et h e o r yo fd a t ac o m p r e s s i o ni sd e p e n d e do nt h er e d u n d a n c i e si nt h eo r i g i n a l d a t a t h ev i d e oc o d i n gt e c h n i q u eo ft h em u l t i m e d i ae m p h a s i z ep a r t i c u l a r l yo nt h e l o s i n gc o m p r e s s i o n i t sc o m p r e s s i o n i sr e a l i z e db ye l i m i n a t i n gt h es p a t i a la n dt e m p o r a l r e d u n d a n c i e s b l o c k b a s e dm o t i o ne s t i m a t i o nt e c h n i q u ei st h ef a i r l ym a t u r eo n e i t u s e sa ni m a g eb l o c ki nt h ep r e v i o u sf l a m et or e p l a c et h ec u r r e n tb l o c ka n dt r i e st of i n d t h em o s ts i m i l a ro n e h o wt of i n dt h eb e s to n ea sf a s ta n dg o o da sp o s s i b l ei sw h a tt h e f a s ts e a r c h i n ga l g o r i t h m sd o a f t e r d i s c u s s i n gt h em o s t u s e df a s ts e a r c h i n ga l g o r i t h m so f t h em o t i o ne s t i m a t i o n w h i c hi n c l u d e st h r e es t e ps e a r c h ，c o n j u g a t ed i r e c t i o ns e a r c h ，q u a d r a n ts e a r c h ，w e t h e ne v a l u a t e dt h e m a n dw e b r i n gu p a ni m p r o v e dc d s a l g o r i t h m ，i ti sb e t t e rt h a nt h e o l do n ei nf i n d i n gt h eb e s tm a t c h i n gp o i n t t h e s ea l g o r i t h m sm i g h tl o s st h eb e s tm a t c h i n gp o i n tb e c a u s et h e i rs e a r c ha r e a s h a v eb l a n kp a r t s w ep r e s e n ta ne s t i m a t i o na l g o r i t h mt h a tp r e d i c t st h eb e s tb e g i n n i n g s e a r c hp o i n tt oa p p r o a c ht h eb e s tm a t c h i n gp o i n ta sc l o s ea sp o s s i b l e i tc a ns o m e w h a t t r a n s l a t et h em u l t i e x t r e m u mp r o b l e mi n t o s i n g l ee x t r e m u mp r o b l e m a n dw ea l s o b r i n gu p at h r e s h o l dv a l u e p i c k i n g u pa l g o r i t h mt oa c c e l e r a t et h es e a r c h i n gs p e e d t h e t e s t ss h o w e dt h a tt h e s ea l g o r i t h m sc a nr e d u c et h es e a r c h i n gs t e p sw h i l eg u a r a n t e e i n g t h ef a i r l yh i g hp s n r v a l u e c o m p a r e d w i t ht h et r a d i t i o n a la l g o r i t h m s ，t h i sa l g o r i t h m s s e a r c hp a t hi sf i x e da n dt h es e a r c h i n gp o i n t sa r ei n d e p e n d e n tt oe a c ho t h e r , s ot h e s e m a k ei te a s i e rt ob eu s e di nm u l t i t h r e a d s e a r c h i n g k e y w o r d ：v i d e oc o d i n g ，m o t i o ne s t i m a t i o n ，f a s t s e a r c h i n ga l g o r i t h m ， m u l t i e x t r e m u m ，i n i t i a ls e a r c h i n gp o i n t i i 華中科技大學(xué)碩士學(xué)位論文 1 緒論 1 1 引言 世界文明的發(fā)展始于人類相互之間能夠進(jìn)行復(fù)雜細(xì)致的交流之時，因為交流 才能使個體凝聚成群體也才能夠產(chǎn)生高于個體的智慧?？v觀人類文明的發(fā)展，幾 個高峰期的開始總是伴隨著更先進(jìn)的通訊方式的誕生。語言，文字，印刷術(shù)，電 視以及如今短短幾年就征服了全球的國際互聯(lián)網(wǎng)無不印證了這個規(guī)律。如今，人 類已經(jīng)踏入信息時代的快速增長期，代表這一時期的最先進(jìn)的通訊方式是數(shù)字化 通信、計算機網(wǎng)絡(luò)以及多媒體技術(shù)。電子郵件、文件共享、遠(yuǎn)程辦公等技術(shù)在大 大加快了人們工作的效率的同時還降低了通訊交流的成本；b b s 、即時通訊的q q 和各種網(wǎng)站論壇極大地豐富了人們的娛樂生活。但是集語音、數(shù)據(jù)、圖像和文字 為一體的交互式多媒體通信方式卻始終未能浮出水面?，F(xiàn)在，人們的需求已經(jīng)不 僅僅停留在每天回家后在電視機這種專一設(shè)備上欣賞由電視臺統(tǒng)一傳送的廣播式 節(jié)目、在互聯(lián)網(wǎng)上同網(wǎng)友只能通過文字溝通以及在電話中僅能聽到親友的聲音這 么簡單的通訊方式。通訊發(fā)展的趨勢要求符合人類信息交換方式的多媒體通信技 術(shù)能夠盡快出臺。 網(wǎng)絡(luò)上的f l a s h 動畫受到眾多網(wǎng)民的喜愛并己成為一種標(biāo)準(zhǔn)。f l a s h 的特色就 是集矢量動畫、音樂、語音和交互于一身，它的迅速發(fā)展體現(xiàn)了如今的通訊領(lǐng)域 對交互媒體的渴望也反映了對如今互聯(lián)網(wǎng)狹窄的帶寬和多媒體龐大的數(shù)據(jù)量之間 的矛盾的一種無奈。在實際效果上，f l a s h 無法取代真實的視頻。但要采用一般視 頻而視頻數(shù)據(jù)不進(jìn)行壓縮的話，數(shù)據(jù)量將會變得很大，對于活動視頻圖像序列更 是如此川，如表1 1 所示。 表1 1 常見的視頻信號 i 華中科技大學(xué)碩士學(xué)位論文 h d t v 1 2 8 0 x 7 2 05 9 9 41 26 2 2 9 m b s 可見，視頻的信息數(shù)據(jù)量非常巨大，以c i f ( c o m m o ni n t e r m e d i a t ef o r m a t ) 格式為例，假定在5 6 km o d e m 這種常用的上網(wǎng)設(shè)備上以5 6 k b p s 的信道傳輸這樣 的彩色視頻信號，則視頻數(shù)據(jù)的壓縮比需高達(dá)1 ：3 2 5 。即使采用q c i f ( q u a r t e r c o m m o ni n t e r m e d i a t ef o r m a t ) 格式，壓縮比仍需有1 ：8 1 。達(dá)到這樣高的壓縮比且 要保持較好的視頻質(zhì)量則必須要有一種高效的視頻壓縮技術(shù)。盡管通信網(wǎng)絡(luò)和存 儲媒體也正在向高帶寬、大容量方向發(fā)展，如a d s l 和光纖通訊等技術(shù)，但是隨 著社會信息交互的日益廣泛和新型的多媒體業(yè)務(wù)不斷出現(xiàn)，個人通信量會成指數(shù) 增長，信道的容量永遠(yuǎn)不會綽綽有余。因此對視頻信息進(jìn)行壓縮處理，使它能在 較低速率的信道上實時傳輸是人們多年來孜孜以求的目標(biāo)。 1 2 數(shù)據(jù)壓縮原理 c e s h a n n o n 在創(chuàng)立信息論時，提出把數(shù)據(jù)看作是信息和冗余的組合。這些 冗余數(shù)據(jù)對于信息的表達(dá)從信息的完備性角度來看是沒有意義的，只要能夠把能 表達(dá)全部意義的部分保存下來即可保留所有有效信息。所以，去除數(shù)據(jù)冗余的部 分就成為多媒體數(shù)據(jù)壓縮的目標(biāo)。 目前各種數(shù)據(jù)壓縮技術(shù)都是與數(shù)據(jù)中數(shù)據(jù)冗余類型有關(guān)。壓縮技術(shù)分為無損 壓縮和有損壓縮兩類。前者是嚴(yán)格遵循去數(shù)據(jù)相關(guān)性這條規(guī)則的，換言之即在壓 縮的過程中將有效信息一視同仁。而有損壓縮則遵循按用戶要求在單位數(shù)據(jù)量一 定的情況下保留盡可能多的有用信息。由此可見，有損壓縮要比無損壓縮復(fù)雜靈 活的多，壓縮比和單位有意義信息量也高得多。多媒體數(shù)據(jù)本身正好具有數(shù)據(jù)信 息是非均勻的，被人類感官察覺的靈敏度不同等因素，因此特別適合于有損壓縮。 如今流行的多媒體壓縮格式有視頻方面的m p e g 系列，流媒體有r m ，音頻有r a 、 m p 3 ，圖像有j p g 等。這些重要的壓縮格式無- - f r o t h 的都是有損壓縮。 視頻有損壓縮有兩方面問題要解決：一是如何判定信息各部分的重要性，二 是如何在一定的信息量下保留最多意義的信息。 一般多媒體數(shù)據(jù)中存在著以下幾種數(shù)據(jù)冗余 2 - 4 1 ： ( 1 ) 空間冗余 用來表示圖像的數(shù)據(jù)中存在著相當(dāng)大的空間相關(guān)性。例如大面積的均勻背景 中就有很大的空間冗余性，因為所有這些點都可以用幾種顏色來表示。原始圖像 的逐點描述明顯不是最佳存儲方案。 華中科技大學(xué)碩士學(xué)位論文 f 2 ) 時間冗余 這是序列圖像和語音數(shù)據(jù)中因連續(xù)變化而包含的冗余，自然界的視頻基本上 平滑變化的，這也就意味著圖像序列中前一幅圖像和后一幅圖像之間變化緩慢， 變化差異只占兩者的一小部分，故存在有較大的相關(guān)性。 ( 3 ) 信息熵冗余( 編碼冗余) 信息熵冗余是一組數(shù)據(jù)所攜帶的信息量編碼冗余。信息熵冗余是在信息在信 源的符號表示過程中，由于未遵循信息論意義下最優(yōu)編碼而造成的冗余性，這種 冗余性可以通過熵編碼來進(jìn)行壓縮。 ( 4 ) 知識冗余 許多圖像的理解與某些基礎(chǔ)知識有相當(dāng)大的相關(guān)性，這類規(guī)律性的結(jié)構(gòu)可由 先驗知識和背景知識得到，我們稱之為知識冗余。 ( 6 ) 視覺冗余。 人類的視覺系統(tǒng)對于圖像場是非均勻和非線性的，特別是視覺系統(tǒng)并不是對 圖像場的任何變化都能察覺。圖像在編碼和解碼處理時盡管由于壓縮和量化截斷 引入了噪聲而使圖像發(fā)生了一定變化，但這些變化如果是不能被視覺所察覺得話， 我們?nèi)哉J(rèn)為圖像是完好的或是足夠好的。像這樣的冗余，我們稱之為視覺冗余。 1 3 視頻編碼技術(shù)概述 對圖像壓縮編碼的研究始于5 0 年代，迄今已有五、六十年的歷史。隨著計算 機、多媒體、網(wǎng)絡(luò)、通信等技術(shù)的發(fā)展，圖像編碼也得到了相應(yīng)的發(fā)展，并且它 的地位越來越重要。 一般人們把視頻編碼技術(shù)分成兩個階段，把1 9 4 8 年至1 9 8 8 年間主要研究的 圖像編碼方法稱為“經(jīng)典圖像編碼技術(shù)”，而后的稱為“第二代編碼技術(shù)”。 經(jīng)典圖像編碼技術(shù)是只利用基于波形的圖像編碼方法進(jìn)行圖像壓縮，它是以 像素和像素塊作為編碼的基本對象進(jìn)行操作，在設(shè)計編碼器的時候沒有或較少的 考慮了人眼的視覺系統(tǒng)( h v s ) 。最初圖像壓縮編碼是對幀內(nèi)預(yù)測法和亞取樣內(nèi)插 復(fù)原法進(jìn)行研究。8 0 年代初開始對運動補償( m c ) 所用的運動估計( m e ) 進(jìn)行 研究a 變換編碼是1 9 6 8 年h c a n d r e w s 等人提出的，采用的是二維離散傅里葉 變換。此后相繼出現(xiàn)了其他方式的變換編碼，包括二維d c t 、小波等。 到了八十年代末，經(jīng)典圖像編碼技術(shù)的發(fā)展開始達(dá)到飽和，在極低比特率視 頻編碼( v l b v ) 應(yīng)用中表現(xiàn)出了極大的局限性。圖像的最終接受器是人眼的視 3 華中科技大學(xué)碩士學(xué)位論文 覺系統(tǒng)，因此圖像質(zhì)量的好壞要由人的主觀感覺來判定。第二代編碼技術(shù)是相對 于經(jīng)典編碼技術(shù)而言更高效的技術(shù)，它充分考慮了人眼的視覺特性，并將人眼視 覺系統(tǒng)作為編解碼器中的基本組成部分。克服了第一代編碼技術(shù)的不足，它最早 是由k u n t 5 1 在1 9 8 5 年提出的。如果把圖像和視頻編碼分成兩個步驟，第一步為 把圖像數(shù)據(jù)轉(zhuǎn)化成某個消息序列，第二步為對這個消息序列分配碼字，我們可以 很容易地區(qū)分經(jīng)典編碼技術(shù)和第二代編碼技術(shù)：經(jīng)典編碼技術(shù)著重考慮第二步， 而第二代編碼方法重點考慮的是第一步并把其結(jié)果用于第二步。第二代方法把圖 像看成是由不同對象組成的，這意味著圖像序列必須先經(jīng)過分解或分割來找到待 處理的對象。第二代視頻編碼技術(shù)主要有基于分割的方法、模型基方法和基于分 形的方法。 1 3 1 經(jīng)典編碼技術(shù) 經(jīng)典編碼技術(shù)主要有預(yù)測編碼、脈沖編碼調(diào)制、變換編碼、矢量量化【6 。7 】、子 帶編碼喁】和小波編碼 9 1 等。 預(yù)測編碼是利用信號間的相關(guān)性將每個像素用其前值( 前像素、前行或前一 幀) 做預(yù)測，并傳輸實際信號與預(yù)測信號差值。實際信號與預(yù)測信號的差值越小， 對其編碼后的比特數(shù)可相應(yīng)減少，這就是預(yù)測編碼實現(xiàn)壓縮的機制。 變換編碼是6 0 年代末提出并于7 0 年代發(fā)展起來的，它將圖像分割成若干子 塊，通過對其正交變換把時間域信號變換到頻域上使變換后各系數(shù)的統(tǒng)計分布比 較集中，能量集中在低頻域，并使變換域中各系數(shù)間的相關(guān)性大大降低，然后對 其分配比特。對于方差大的分配以較多的比特，反之，分配較少的比特數(shù)進(jìn)而實 現(xiàn)總比特率的壓縮。 矢量量化是用矢量量化器代替標(biāo)量量化器做量化，從而降低碼率的方法。 子帶編碼先將原圖用若干數(shù)字濾波器分解成不同頻率成分的分量，再對這些 分量進(jìn)行亞抽樣，形成子帶圖像，最后對不同的子帶圖像分別用與其相匹配的方 法進(jìn)行編碼。在接受端，將解碼后的子帶圖像補零、放大，并經(jīng)合成濾波器的內(nèi) 插，將各子帶信號進(jìn)行相加，進(jìn)行圖像恢復(fù)。 經(jīng)典圖像和視頻編碼技術(shù)通過減少圖像數(shù)據(jù)的相關(guān)性來壓縮數(shù)據(jù)量。它將圖 像看成是需要進(jìn)行解相關(guān)的像素組成的集合，采用了波形編碼。利用率失真定理， 在給定編碼速率的條件下得到最小的波形失真，或者在達(dá)到最小編碼速率的條件 下得到可接受的波形失真。 4 華中科技大學(xué)碩士學(xué)位論文 132 第二代編碼技術(shù) 第二代圖像和視頻編碼技術(shù)在設(shè)計圖像和視頻編碼器時更多地考察人眼的主 觀視覺特性。常見的第二代編碼技術(shù)主要有：基于分割的方法、模型基方法和基 于分形的方法等。 基于分割的圖像和視頻編碼是把圖像和視頻分割成若干個對象，對每個對象 進(jìn)行編碼。例如基于內(nèi)容的視頻編碼【1 0 】、輪廓紋理( t e x t u r e ) i n 編碼、分裂( s p l i t ) 和合并( m e r g e ) 編碼 1 2 】等。早期的輪廓紋理編碼是根據(jù)灰度等信息把圖像分成同 態(tài)( h o m o g e n e o u s ) 區(qū)域，每個區(qū)域作為對象進(jìn)行編碼，相比較基于內(nèi)容的編碼而言， 這種劃分是一種低層次的劃分。近幾年發(fā)展起來的基于內(nèi)容的m p e g 4 編碼對編 碼對象的劃分是一種有意義的劃分( 如，人物、地球儀、桌子等) ，而不是簡單的 圖像區(qū)域劃分。 模型基編碼f 1 3 - 1 6 j ( m o d e l b a s e dc o d i n g ) 把圖像看作3 d 真實物體的2 d 投影，充 分利用了圖像中目標(biāo)和景物的結(jié)構(gòu)化特征和知識。首先編碼器利用編解碼端共有的 圖像模型，通過圖像分析提取景物參數(shù)，例如形狀參數(shù)、運動參數(shù)等，然后解碼器 利用編碼器傳來的參數(shù)借助圖像合成技術(shù)重建圖像。此過程如圖1 1 所示。模型基 編碼在更深層次上研究了圖像的冗余性，可以達(dá)到更高的編碼效率。研究資料表明， 動畫效果的面部僅需要5 0 0 一1 0 0 0 b p s ，更逼真的面部表示可能需要5 - l o k b p s ，c i f 和0 c i f 彩色頭肩序列可達(dá)到1 6 6 4 k b p s 。模型基編碼的三個關(guān)鍵技術(shù)是模型匹配 ( 利用2 d 圖像序列重構(gòu)3 d 或2 d 模型) 、圖像分析( 提取模型參數(shù)和運動參數(shù)) 和圖像合成。 圖1 1 模型基編碼系統(tǒng)原理框圖 分形編碼( 廳a c t a i b a s e dc o d i n g ) t 1 7 - 1 9 1 起步較晚，但其壓縮比的潛力令人矚目。 分形圖像編碼主要利用自相似性的特點，通過迭代函數(shù)系統(tǒng)( i f s ：i t e r a t e df u n c t o n 5 華中科技大學(xué)碩士學(xué)位論文 s v s t e r n ) 來實現(xiàn)壓縮。自相似性是指無論幾何尺度怎么變化，景物任何一小部分 的形狀都與較大部分的形狀極其相似。自相似有些是確定性的，但大量存在的是 統(tǒng)計自相似及隨機自相似性。分形編碼正是利用圖像了局部與局部、局部與整體 間的自相似性冗余來進(jìn)行壓縮，不僅消除了圖像中的近程相關(guān)性，而且有效的消 除了自然圖像中的遠(yuǎn)程相關(guān)性，因而能夠獲得相當(dāng)高的壓縮比，特別是在高壓縮 比的情況下，分形編碼的恢復(fù)圖像質(zhì)量要優(yōu)于其他編碼方法如j p e g 。目前常見 的自動分形圖像壓縮編碼方法都是以j a c q u i n 的方法為基礎(chǔ)，這類方法用仿射變 換( a f f i n et r a n s f o r m a t i o n ) 來消除圖像塊中間的確定自相似性冗余。在編碼時將 圖像分為互不重疊的子塊，通常稱這些子塊為值域塊，對每一值域塊編碼時都要 用搜索的方法在圖像中尋找與其相似的定義域塊，并按照某種誤差準(zhǔn)則確定一個 相應(yīng)的收縮仿射變換，使得編碼誤差滿足給定要求。目前分形編碼最主要的問題 在于計算耗時太長，不適合視頻編碼的實時性要求，仍然有待進(jìn)一步的深入研究。 1 4 論文的選題和主要工作 本文的選題主要是針對視頻壓縮中的運動估計算法的研究。視頻壓縮中決定 其壓縮后的數(shù)據(jù)碼流大小的關(guān)鍵因素在于能否較好的去除其時間相關(guān)性。傳統(tǒng)方 法已經(jīng)能很好的進(jìn)行圖像匹配，但是是以犧牲速度來獲得最好的預(yù)測效果的。雖 然現(xiàn)在的計算機運算能力已經(jīng)很強大，但是相對于視頻文件的數(shù)據(jù)量和一般個人 使用的計算機系統(tǒng)而言仍遠(yuǎn)遠(yuǎn)不夠。在較流行的視頻壓縮軟件的使用中，經(jīng)常會 遇到壓縮一段普通電影長度的視頻需要一天甚至好幾天的情況。這對于普通應(yīng)用 來說是不可忍受的。本文就是本人對視頻編碼技術(shù)中的運動估計的快速算法的研 究和其算法實現(xiàn)的總結(jié)。 本論文共分五章，主要結(jié)構(gòu)與內(nèi)容如下： 第一章為綜述，提出問題，介紹了視頻壓縮編碼技術(shù)的發(fā)展與現(xiàn)狀。 第二章對基于對象的m p e g 一4 視頻編碼系統(tǒng)進(jìn)行描述，對m p e g 一4 中的形狀 編碼、紋理編碼、可伸縮性編碼和碼率控制技術(shù)進(jìn)行的詳細(xì)的探討。 第三章著重討論了m p e g - 4 視頻編碼系統(tǒng)運動估計的幾種編碼方法，并對常 用的快速算法如三步法、共軛方向法、象限法等，詳細(xì)分析了它們的優(yōu)缺點，并 對正交共軛法進(jìn)行了改進(jìn)，提供了相應(yīng)的實驗數(shù)據(jù)。 第四章根據(jù)上述算法編碼因為搜索區(qū)域存在多極值而可能導(dǎo)致漏選最佳匹配 點這一缺陷，提出了預(yù)測起始搜索點的預(yù)測算法。另外還對門限值的選取進(jìn)行了 6 華中科技大學(xué)碩士學(xué)位論文 分析，進(jìn)步加快了搜索匹配的速度。實驗表明，該算法與傳統(tǒng)的運動估計算法 相比在大幅度減少搜索步數(shù)的同時還能保持較高的信噪比，且算法簡單能直接嵌 入到大多數(shù)編碼系統(tǒng)。 最后章對全文工作進(jìn)行了總結(jié)，并針對下一步的研究工作做出了初步設(shè)想。 7 華中科技大學(xué)碩士學(xué)位論文 2 基于對象的m p e g 4 視頻編碼技術(shù)分析 本章首先對現(xiàn)有的視頻編碼標(biāo)準(zhǔn)進(jìn)行簡要介紹，然后對m p e g 一4 視頻編碼系 統(tǒng)的框架結(jié)構(gòu)進(jìn)行描述，最后對m p e g 4 中的形狀編碼、紋理編碼、運動估計和 補償、可伸縮性編碼和碼率控制技術(shù)等進(jìn)行詳細(xì)的探討。 2 1 現(xiàn)有視頻編碼技術(shù)國際標(biāo)準(zhǔn) 視頻編碼的研究成果集中體現(xiàn)在相應(yīng)的標(biāo)準(zhǔn)中，目前已經(jīng)制定出的比較重要 的視頻編碼標(biāo)準(zhǔn)有：i t u t h 2 6 1 h 2 6 3 h 2 6 3 + ，i s o i e c m p e g 1 2 4 系列。下 面將分別介紹。 2 1 1i t u th 2 6 1 、h 2 6 3 、h 2 6 3 + 于1 9 8 8 年形成草案、1 9 9 0 年1 2 月完成和通過的c c i t t 建議書 l 2 6 l ，是視 頻編碼技術(shù)走向?qū)嵱没睦锍瘫蛔u為“圖像編碼4 0 年經(jīng)驗之總結(jié)”。h 2 6 1 支持實時動態(tài)圖像的壓縮編解碼。它采用的主要視頻編碼技術(shù)有d c t 編碼、幀間 預(yù)測、運動補償?shù)然旌暇幋a技術(shù)。 在1 9 9 5 和1 9 9 6 年，i t u t 制定了用于低比特流通信的h 2 6 3 1 2 0 - 2 2 視頻編碼 標(biāo)準(zhǔn)。視頻信源編碼器原理框圖如圖2 1 所示，主要由運動補償預(yù)測、離散余弦 變換、量化、熵編碼和編碼控制幾部分組成。 注：q 一量化器q - 1 一逆量化器p 一幀內(nèi)幀間標(biāo)識 8 華中科技大學(xué)碩士學(xué)位論文 t 一傳輸與否標(biāo)識q z 一量化級q 一量化后的變換系數(shù)v 一運動矢量 圖2 1h 2 6 3 視頻信源編碼器 最初的h 2 6 3 草案主要是為了支持6 4 k b p s 以下視頻數(shù)據(jù)流編碼，但不久這個 限制叉被取消了，使得h 2 6 3 可以支持大范圍變化的視頻比特流編碼，從而可以 完全取代h 2 6 l 。h 2 6 3 使用的算法同h 2 6 1 以及m p e g 一2 相似，都采用了d c t 加運動補償( m c d c t ) 的編碼方法，但h 2 6 3 做出了以下改進(jìn)： ( 1 ) 運動補償采用了半像素精度并使用了環(huán)形濾波器； ( 2 ) 數(shù)據(jù)流的一些層次結(jié)構(gòu)內(nèi)容是可選的，使編碼器的參數(shù)配置達(dá)到最優(yōu)，以 取得更低的碼流，并能進(jìn)行有效的差錯掩蓋和恢復(fù)； ( 3 ) 增加了四種可選擇的編碼模式以提高執(zhí)行效率：自由運動向量模式，基于 語法的算術(shù)編碼模式，高級預(yù)測編碼，p b 幀模式； f 4 ) h 2 6 3 支持五種分辨率的圖像格式：q c i f ( 1 7 6 1 4 4 ) ，c i f ( 3 5 2 2 8 8 ) ， s u b q c i f ( 1 2 8 x 9 6 ) ，4 c i f ( 7 0 4 5 7 6 ) ，1 6 c i f ( 1 4 0 8 1 1 5 2 ) 。 h 2 6 3 + 是h 2 6 3 的擴展，它的整體結(jié)構(gòu)和基本算法與h 2 6 3 相同。同時在 h 2 6 3 的基礎(chǔ)上做了一些新的改進(jìn)。比如，h 2 6 3 只支持5 種圖像格式，而h 2 6 3 + 支持更多種的自定義圖像格式，并且圖像尺寸、寬高比和時鐘頻率等都可以作為 h 2 6 3 + 數(shù)據(jù)流的一部分。與h 2 6 3 相比，它增加了1 2 個可選的編碼模式：先進(jìn) 的幀內(nèi)編碼、除塊濾波、片( s l i c e ) 結(jié)構(gòu)、附加增強信息、改進(jìn)的p b 幀、參考圖像 選擇、時空及s n r 可擴展性( s c a l a b i l i t y ) 、參考圖像再抽樣、減少分辨率更新、獨 立分段解碼、可替換的幀內(nèi)v l c 、修改的量化模式。h 2 6 3 + 中的無限制運動矢量 模式與h 2 6 3 中的無限制運動矢量模式也有所不同。 2 1 2l s o i e c m p e g 一1 、m p e g - 2 、m p e g - 4 成立于1 9 8 8 的活動圖像專家組m p e g ( m o v i n g p i c t u r e se x p e r t s g r o u p ) 【2 3 之5 1 是 國際標(biāo)準(zhǔn)化組織國際電工委員會( i s o t e c ) t 屬的負(fù)責(zé)制定開發(fā)運動圖像和音頻 的壓縮、解壓縮、處理和編碼的國際標(biāo)準(zhǔn)的一個工作組。該專家組先后制定了 m p e g l 、m p e g - 2 和m p e g 一4 ，并正在致力于制定m p f g - 7 和m p e g 一2 l 。 m p e g 1 制定于1 9 9 3 年8 月，是針對1 5 m b i t s 數(shù)據(jù)傳輸率下的數(shù)字存儲媒 質(zhì)運動圖像及其伴音編碼的國際標(biāo)準(zhǔn)。它的視頻部分與h 2 6 1 及h 2 6 3 原理圖大 致相同。然而，m p e g - 1 主要是針對存儲媒體的視頻編碼標(biāo)準(zhǔn)，而h 2 6 1 和h 2 6 3 主要是針對傳輸?shù)囊曨l編碼標(biāo)準(zhǔn)。故m p e g 1 應(yīng)當(dāng)在顧及圖像質(zhì)量和壓縮比的情 _ _ - - _ _ _ _ _ _ _ _ _ _ - _ 一一 華中科技大學(xué)碩士學(xué)位論文 況下要考慮對序列圖像進(jìn)行隨機訪問和編輯的方便。m p e g l 加人了雙向預(yù)測 幀一b 幀，從而加大了壓縮比。對隨機訪問及編輯的支持由每秒2 個i 幀來支持， 它不需依賴p 幀和b 幀而獨立解碼。因而利于實現(xiàn)m p e g 比特流的編輯與隨機訪 問。m p e g 1 對色差分量采用4 ：l ：l 的二次采樣率。其視頻壓縮率為2 6 ：1 。 1 9 9 5 年制定的m p e g 一2 主要是針對數(shù)字視頻廣播( d v b ) 、高清晰度電視 ( h d t v ) 、數(shù)字視盤( d v d ) 等制定的高于1 5 m b i f f s 運動圖像及其伴音的編碼 標(biāo)準(zhǔn)2 “。m p e g 一2 綜合采用了利用運動補償?shù)膸g預(yù)測、空間域離散余弦變換、 自適應(yīng)量化和可變字長編碼的混合算法，該標(biāo)準(zhǔn)為了適應(yīng)不同碼率和不同場合， 僅對比特流語法和相應(yīng)的解碼方法做了規(guī)定，而在編碼器的設(shè)計上留有很大自由 度，如運動估計的搜索算法和匹配函數(shù)的選擇，利用人視覺特性的自適應(yīng)量化等。 1 9 9 4 年，m p e g 活動圖像專家組開始制定m p e g 一4 2 7 - 3 3 標(biāo)準(zhǔn)。它的目的是尋 求支持?jǐn)?shù)字音頻視頻數(shù)據(jù)通信、存取和管理的新途徑，提供一個可以實現(xiàn)交互性 和高壓縮比，以及具有很高靈活性和可延展性的新的視頻音頻編碼標(biāo)準(zhǔn)。較之前 幾個m p e g 標(biāo)準(zhǔn)，m p e g 一4 為多媒體數(shù)據(jù)壓縮提供了一個更為廣闊的平臺，它更 多定義的是一種格式和框架，而不是具體的算法，以支持各種各樣新穎的和高效 的功能。 m p e g 4 最顯著的特點是基于內(nèi)容的編碼，即場景由幾個音視頻對象( a u d i o v i d e oo b j e c t ) 組成，如背景圖片或音樂、處在焦點區(qū)的視音頻內(nèi)容、文本和圖形 等，對場景的編解碼建立在這些音視頻對象上，這樣用戶可以對這些對象分別進(jìn) 行解碼和重建，使得使用者對原始場景能夠以一種靈活的方式來操作。 基于對象的分級功能是m p e g 一4 提供的又一個新的功能，同時兼容于 m p e g 2 標(biāo)準(zhǔn)中的圖像分級功能，分級工具主要用于互聯(lián)網(wǎng)和無線網(wǎng)等窄帶的視 頻通信、多質(zhì)量視頻服務(wù)和多媒體數(shù)據(jù)庫預(yù)覽等服務(wù)。m p e g - 4 提供了兩種基本 的分級工具：時域分級和空域分級，時域分級是降低原視頻序列的幀率，空域分 級是降低原視頻序列的分辨率。在每類分級工具中，視頻序列都可以分為基層和 增強層兩層，基層提供了視頻序列的基本信息，增強層提供了視頻序列更高的分 辨率和細(xì)節(jié)。基層可以單獨傳輸和解碼，而增強層則必須與基層一起傳輸和解碼。 m p e g 4 也支持時域和空域的混合分級。 基于對象的編碼除了能提高數(shù)據(jù)的壓縮比，還能實現(xiàn)許多基于內(nèi)容的交互性 功能，如基于內(nèi)容的多媒體數(shù)據(jù)存取、游戲或多媒體家庭編輯、網(wǎng)上購物和電子 商店、遠(yuǎn)程監(jiān)控、醫(yī)療和教學(xué)等。 1 0 華中科技大學(xué)碩士學(xué)位論文 m p e g - 4 編碼標(biāo)準(zhǔn)的基本概念 茜饕藩i 卜 l l 匾卜u 岡 在實際應(yīng)用中，一個用戶對不同的視頻對象可以選擇不同的參數(shù)、編碼方式 或者甚至不對某些對象進(jìn)行編碼來滿足其需要。圖2 _ 3 是m p e g 4 視頻校驗?zāi)Ｐ?的解碼方塊圖，它的結(jié)構(gòu)同編碼器正好相反。合成器所采用的方法由用戶和系統(tǒng) l l 華中科技大學(xué)碩士學(xué)位論文 及所采用的匯接方法來決定。不同視頻對象之間的同步和視頻對象于其他實體， 如音頻對象之間的同步由m p e g 4 的系統(tǒng)層來處理。 岡玎 一 燮叫言卜圓一徽卜 i卜fl l l p u i 用戶l l 奎里i 圖2 3m p e g - 4 視頻校驗?zāi)Ｐ偷耐ㄓ媒獯a框架 m p e g 一4 的視頻校驗?zāi)Ｐ吞峁┑目蛇x工具有：形狀編碼、紋理編碼、運動編 碼( 運動估計與補償) 、錯誤恢復(fù)、可分級性編碼、s p r i t e 編碼、紋理編碼模式。 在第三節(jié)我們將詳細(xì)介紹以上概念。 m p e g 4 視頻標(biāo)準(zhǔn)支持以下三類新功能：基于內(nèi)容的交互性、高壓縮率和通 用訪問3 7 - 4 1 1 。 1 基于內(nèi)容的交互性 m p e g 一4 允許在編碼數(shù)據(jù)級上對壓縮域中的視頻物體進(jìn)行存取和操縱，其目 的是以高度靈活的方式使用和表示它們。尤其是將來的多媒體應(yīng)用與計算機游戲 以及相關(guān)的應(yīng)用將得益于對視聽內(nèi)容目益增加的交互性。 ( 1 ) 基于內(nèi)容的多媒體數(shù)據(jù)訪問工具 m p e g 4 通過使用各種數(shù)據(jù)訪問工具，提供基于音視頻內(nèi)容的數(shù)據(jù)訪問，如 索引、超鏈接、查詢、瀏覽、上載、下載以及刪除等工具。 ( 2 ) 基于內(nèi)容的操縱與數(shù)碼流編輯 m p e g 一4 允許對景物中不同的視頻物體分別進(jìn)行靈活的解碼與表示，并通過 對數(shù)碼流的簡單操作來控制原始景物的形狀、透明性、空間坐標(biāo)以及描述物體伸 縮、旋轉(zhuǎn)等相關(guān)參數(shù)。 ( 3 ) 自然數(shù)據(jù)與合成數(shù)據(jù)混合編碼 m p e g 一4 支持解碼器可控的將合成數(shù)據(jù)和原始音視頻組合在一起的方法。其 應(yīng)用范例有：在游戲中用自然的音頻和視頻結(jié)合人工產(chǎn)生的多媒體對象生成虛擬 的場景，用戶可以隨意控制媒體對象，從不同的角度觀察和描繪視頻和聲音。 華中科技大學(xué)碩士學(xué)位論文 1 4 t 改進(jìn)的時蚓隨機存馭 2 高壓縮率 ：丕一功能實噴上是針對需要肘現(xiàn)聽信息進(jìn)行有效存儲( 或傳輸) 的應(yīng)用，這將 增強如i n t e m e t 上的信息瀏覽、虛擬現(xiàn)實等一些已有的i 立用： ( 1 ) 改進(jìn)的編碼效率 提高編碼效率，尤其是在甚低數(shù)碼率( 小于6 4 k b i t s ) 的應(yīng)用，m p e g 一4 視頻際 準(zhǔn)：降提供更好的主觀視覺質(zhì)量。這一功能可望在迅速發(fā)展的移動通迅中得到應(yīng)用， 目前的c d m a 標(biāo)準(zhǔn)為此提供了通訊協(xié)議平臺，相信會成為無線通訊中最重要的業(yè) 務(wù)領(lǐng)域。 ( 2 ) 對多路并存數(shù)據(jù)流的編碼 m p e g 一4 可以對景物進(jìn)行有效的多視角編瑪，對于立體視頻的應(yīng)用，m p e g 一4 能充分利用從多個視角對同一景物進(jìn)行觀察所造成的信息冗余度，提取該景物的 3 d 模型。其應(yīng)用范圍包括：虛擬現(xiàn)實游戲、三維動畫、工程建模等， 3 通用訪問 m p e g 4 標(biāo)準(zhǔn)涉及到在多媒體應(yīng)用方面( 尤其在無線通信和數(shù)據(jù)庫存取) 能預(yù) 見的各種不同類型的網(wǎng)絡(luò)環(huán)境，要求視頻壓縮算法能適應(yīng)噪聲環(huán)境、時變帶寬以 及不同的解碼器可用資源， 容易出錯環(huán)境中的健壯性 m p e g 4 將提供對差錯的健壯性，以允許直用于各種無線、有線網(wǎng)絡(luò)以及存 儲媒介。在惡劣的差錯條件下，對于低數(shù)碼率的應(yīng)用，應(yīng)提供足夠的抗錯能力。 f 2 1 基于內(nèi)容的可伸縮性 m p e g m 將提供在內(nèi)容、質(zhì)量( 例如空間域分辨率和時間域分辨率) 以及復(fù)雜 度方面可伸縮的能力，允許對特定物體在時間域和空間域分辨率方面按不同的質(zhì) 量要求對編碼數(shù)據(jù)進(jìn)行存取，以便具有不同復(fù)雜度的解碼器能對編碼數(shù)據(jù)進(jìn)行解 碼。用戶能夠選擇或自動選擇景物中各物體的解碼質(zhì)量，能按不同的內(nèi)容等級、 比例、分辨率和質(zhì)量進(jìn)行數(shù)據(jù)庫的瀏覽。 通過以上對m p e g 一4 視頻編碼標(biāo)準(zhǔn)新功能的總結(jié)，我們可以看出m p e g 4 提 供了一個高度靈活的框架和個開放的工具集，以方便地吸納新的思想、新的軟 硬件技術(shù)，具有長久的生命力與廣泛的適用性。 22 2m p e 6 4 的視頻編碼模式分類 1 3 華中科技大學(xué)碩士學(xué)位論文 m p e g 一4 h 2 j 鰷完全支持m p e g 1 ，2 己提供的全郎況頻功能，包括在不同輸 少、珞式、幀室、比特率下對標(biāo)準(zhǔn)矩形區(qū)域圖像亭列進(jìn)行有效編碼外t 還增加了新 日i j 基于內(nèi)容的視頻編碼功能。圖2 4 表示m p e g 一4 視頻編碼模型提供的摸式和比 特率的關(guān)系 圖2 4b l p e g 一4 圖像和視頻編碼算法與工具分類 甚低比特率視頻核( v l b vc o r e ) 提供了從5 k b i t s 到6 4 k b i t s 的甚低比特率業(yè)務(wù) 的算法和工具，它支持甚低分辨率( 從每行每列幾個像素到c i f 級分辨率，即每 幀2 8 8 行，每行3 5 2 個像素) 和甚低幀速率( 從0 h z 到1 5 h z ) 的圖像序列。 高比特率核( h b r vc o r e ) i j 提供了支持從6 4 k b i t s 到1 0 m b i s 的高比特率圖像 傳輸?shù)墓ぞ吆退惴?，這些工具和算法與v l b 、，c o r e 所提供的相同。h b r vc o r e 的 主要應(yīng)用對象是多媒體廣播、數(shù)字電視圖像級別的交互信號傳遞。 附加的基于內(nèi)容的功能其核心在于支持視頻按內(nèi)容進(jìn)行編解碼，擴展的 m p e g 一4 基于內(nèi)容的算法和工具可以看作是v l b v 核和h b v 核的超集。與標(biāo)準(zhǔn) 的m p e g 1 和m p e g 一2 對長方形圖像序列進(jìn)行編碼不同，m p e g 4 的視頻通常被 認(rèn)為是任意形狀的，m p e g 4 基于內(nèi)容的方法可以看作是m p e g 4 v l b v 和h b r v 核編碼方法向任意形狀的輸入視頻方向邏輯擴展的結(jié)果，只有當(dāng)原始圖像序列沒 有被分割成任意形狀的視頻對象時，才用傳統(tǒng)的矩形圖像序列進(jìn)行編碼。因此， m p e g 4 視頻標(biāo)準(zhǔn)同時支持傳統(tǒng)的以矩形幀為基礎(chǔ)和現(xiàn)在的以具有任意形狀的對 象內(nèi)容為基礎(chǔ)的兩種編碼方式。 2 23 視頻校驗?zāi)Ｐ偷臄?shù)據(jù)結(jié)構(gòu) 為了支持前面提到的各種功能：高效壓縮、基于內(nèi)容交互f 操作、編輯、訪問 1 4 華中科技大學(xué)碩士學(xué)位論文 m p e g4 等) 以及基于內(nèi)容分級擴展( 空域分級、時域分級) ，必然要求 一費以基十 ：ide。oo b m j e c ：t s e q u e n c e 。3 太5 ”州奠弋 v i d e o0 b j e c tl a y e r v o l l 鈾”吖如0 0 “忡“”硝0 g o v i v i d e o0 b j ?！皃 l a n e v o p 0 v o p nv o p n t l v o p m 圖2 5m p e g 一4 視頻校驗?zāi)Ｐ偷恼Z法層次結(jié)構(gòu) 視頻對象序列v i d e oo b j e c ts e q u e n c e ( v o s ) ：一個完整的視頻序列可以由幾 個v o s 組成。視頻對象序列是指輸入的一個實驗序列，可以看成是一段畫面。它 包含一個或幾個視頻對象( v 0 ) 的集合。 視頻對象v i d e oo b j e c t ( v o ) ：如前所述，是場景中的某個物體，它是有生命 期的，由時間上連續(xù)的許多幀構(gòu)成。物體可伸縮性就是通過使用v o 類實現(xiàn)。每 個v o 有三類信息來描述：形狀信息、運動信息、紋理信息。一個視頻對象可以 包含一個或幾含層，這些層可以是視頻一視頻對象層( v o l ) 或紋理內(nèi)容一紋理對 象層( s o l ) 。 視頻對象層v i d e oo b j e c tl a y e r ( v o l ) 或者是紋理對象層t e x t u r eo b j e c tl a y e r ( t o l ) ：v o 的三種屬性信息編碼于這個類中，它是一個增強v o 的時間域或空 間域分辨率的類。這個類的引入主要用來擴展v o 的時域或空域分辨率。每個視 頻對象層( v o l ) 包含一隊由時間快照一視頻對象平面( v o p ) 組成的序列。 視頻對象平面v i d e oo b j e c tp l a n e ( v o p ) ：v o p 是一個v o 在某一給定時刻 華中科技大學(xué)碩士學(xué)位論文 發(fā)生的一個事例，即某一幀v o 。兩個不同的v o p 可能屬于兩個不同時刻的同一 個視頻物體，而不一定屬于兩個不同的視頻物體。v o p 相當(dāng)于傳統(tǒng)編碼方式的一 幀，它可以是任意形狀的。 視頻對象平面組g r o u po f v i d e oo b j e c tp l a n e s ( g o v ) ：視頻對象平面組( g o v ) 是一個可選層，它的主要功能是用來提供隨機接入和錯誤恢復(fù)，因為g o v 頭包 含著絕對時間信息。在一些應(yīng)用輪廓，g o v 頭后跟隨的是i - v o p 。 視頻校驗?zāi)Ｐ偷耐ㄓ镁幋a器流程：第一步是v o 的形成，先要從原始視頻流 中分割出v o ，之后由編碼控制機制為不同的v o 以及各個v o 的三類信息分配 碼率，之后各個v o 分別獨立編碼，最后將各個v o 的碼流與場景描述信息和其 它同步控制信息合成比特流，經(jīng)過m p e g 的多媒體繼承傳輸框架d m i f 包裝后， 復(fù)合( m u x ) 成一個位流。其中，在編碼控制和復(fù)合階段可以加入用戶的交互控制 或由智能化的算法進(jìn)行控制。d m i f 對不同的傳輸媒體提供了共同的接口并提供 q o s 服務(wù)。在解碼端復(fù)合的比特流被分解，然后視頻對象被解碼并根據(jù)場景描述 合成場景。視頻校驗?zāi)Ｐ偷耐ㄓ媒獯a器流程基本上為編碼器的反過程。 2 3m p e g - 4 視頻編碼關(guān)鍵技術(shù)分析 基于內(nèi)容的視頻編碼系統(tǒng)主要由形狀編碼、運動編碼和紋理編碼等模塊構(gòu)成， 具體的編碼算法則作為實現(xiàn)系統(tǒng)中各個功能模塊的工具，可以根據(jù)實際需要選取 組合。盡管m p e g 4 的視頻校驗?zāi)Ｐ椭饕槍θ我庑螤畹膶ο?，但?dāng)前采用的工 具大多是基于宏塊的，這有利于同其他視頻編碼標(biāo)準(zhǔn)的兼容。當(dāng)然，在不需要形 狀信息的應(yīng)用中( 如基于幀的視頻編碼) ，形狀編碼要被禁用。對于每一個視頻對 象平面( v o p ) 的編碼流程可見圖2 6 。 首先對輸入的原圖像序列進(jìn)行場景分析和對象分割，以劃分不同的v o p ，得 到各個v o p 的形狀和位置信息。v o p 的形狀和位置信息可以用一個二值的a l p h a 平面來表示。 對運動和紋理信息編碼仍然采用類似m p e g 和h 2 6 l 3 標(biāo)準(zhǔn)的預(yù)測運動補償 法，該方法以被認(rèn)為是四十年來