第3章數(shù)字視頻編碼原理第3章數(shù)字視頻編碼原理了解圖像和視頻編碼技術的發(fā)展歷程，熟悉視頻編碼的各種方法。重點掌握哈夫曼編碼、算術編碼、預測編碼和基于DCT的變換編碼基本原理。掌握運動估計和運動補償預測編碼的基本原理。本章學習目標了解圖像和視頻編碼技術的發(fā)展歷程，熟悉視頻編碼的各種方法。本3.1數(shù)字視頻編碼概述3.2熵編碼3.3預測編碼3.4變換編碼第3章數(shù)字視頻編碼原理3.1數(shù)字視頻編碼概述第3章數(shù)字視頻編碼原理3.1.1數(shù)字視頻壓縮的必要性和可能性數(shù)據壓縮的理論基礎是信息論。從信息論的角度來看，壓縮就是去掉數(shù)據中的冗余，即保留不確定的信息，去掉確定的信息（可推知的），也就是用一種更接近信息本質的描述來代替原有冗余的描述。在一般的圖像和視頻數(shù)據中，主要存在以下幾種形式的冗余。3.1.1數(shù)字視頻壓縮的必要性和可能性數(shù)據壓縮的理論基礎是空間冗余：也稱為空域冗余，是一種與像素間相關性直接聯(lián)系的數(shù)據冗余。

例:圖像中包含許多規(guī)則物體，它們的亮度、飽和度及顏色可能都一樣，因此，圖像在空間上具有很強的相關性。例如Lenna圖像的臉部和肩部。3.1.1數(shù)字視頻壓縮的必要性和可能性空間冗余：也稱為空域冗余，是一種與像素間相關性直接聯(lián)系的數(shù)據時間冗余：也稱為時域冗余，它是針對視頻序列圖像而言的。

視頻序列每秒有25~30幀圖像，相鄰幀之間的時間間隔很??；同時實際生活中的運動物體具有運動一致性，使得視頻序列圖像之間有很強的相關性。

3.1.1數(shù)字視頻壓縮的必要性和可能性時間冗余：也稱為時域冗余，它是針對視頻序列圖像而言的。3.1統(tǒng)計冗余

信源熵：如果將信源所有可能事件的信息量進行平均，就得到了信源熵(entropy)。熵就是平均信息量。

當xj等概率時，H(X)最大。當xj

非等概率時，H(X)不是最大，就存在冗余。

采用可變長編碼技術，對出現(xiàn)概率大的符號用短碼字表示，對出現(xiàn)概率小的符號用長碼字表示，則可去除符號冗余，從而節(jié)約碼字，這就是熵編碼的思想。3.1.1數(shù)字視頻壓縮的必要性和可能性統(tǒng)計冗余當xj等概率時，H(X)最大。結構冗余：在有些圖像的部分區(qū)域內有著很相似的紋理結構，或是圖像的各個部分之間存在著某種關系，例如自相似性等，這些都是結構冗余的表現(xiàn)。

分形圖像編碼的基本思想就是利用了結構的自相似性。3.1.1數(shù)字視頻壓縮的必要性和可能性結構冗余：在有些圖像的部分區(qū)域內有著很相似的紋理結構，或是圖知識冗余：在某些特定的應用場合，編碼對象中包含的信息與某些先驗的基本知識有關。例如:人臉的圖像有同樣的結構：嘴的上方有鼻子，鼻子上方有眼睛，鼻子在中線上……

可以利用這些先驗知識為編碼對象建立模型。通過提取模型參數(shù)，對參數(shù)進行編碼而不是對圖像像素值直接進行編碼，可以達到非常高的壓縮比。這是模型基編碼（或稱知識基編碼、語義基編碼）的基本思想。3.1.1數(shù)字視頻壓縮的必要性和可能性知識冗余：在某些特定的應用場合，編碼對象中包含的信息與某些先人眼的視覺冗余

視覺冗余度是相對于人眼的視覺特性而言的。壓縮視覺冗余的核心思想是去掉那些相對人眼而言是看不到的或可有可無的圖像數(shù)據。對視覺冗余的壓縮通常反映在各種具體的壓縮編碼過程中。3.1.1數(shù)字視頻壓縮的必要性和可能性人眼的視覺冗余3.1.1數(shù)字視頻壓縮的必要性和可能性1948年提出電視信號的數(shù)字化，人們開始了對圖像壓縮編碼的研究工作。1952年哈夫曼給出最優(yōu)變長碼的構造方法。3.1.2數(shù)字視頻編碼技術的進展1948年提出電視信號的數(shù)字化，人們開始了對圖像壓縮編碼的研預測編碼1952年，貝爾實驗室的奧利弗等人開始研究線性預測編碼理論1958年，格雷哈姆用計算機模擬法研究圖像的DPCM方法1966年，奧尼爾通過理論分析和計算模擬比較了PCM和DPCM對電視信號進行編碼傳輸?shù)男阅?0世紀70年代開始進行了幀間預測編碼的研究20世紀80年代初開始對作運動補償預測所用的運動估值進行研究3.1.2數(shù)字視頻編碼技術的進展預測編碼3.1.2數(shù)字視頻編碼技術的進展變換編碼首先討論了包括K-L（Karhunen-Loeve）變換、傅立葉變換等正交變換1968年安德魯斯等人采用二維離散傅立葉變換（2D-DFT）提出了變換編碼此后相繼出現(xiàn)了沃爾什-哈達瑪（Walsh-Hadamard）變換、斜（Slant）變換、K-L變換、離散余弦變換（DCT）等3.1.2數(shù)字視頻編碼技術的進展變換編碼3.1.2數(shù)字視頻編碼技術的進展子帶編碼1976年美國貝爾系統(tǒng)的克勞切等人提出了話音的子帶編碼。1985年奧尼爾將子帶編碼引入到圖像編碼。3.1.2數(shù)字視頻編碼技術的進展子帶編碼3.1.2數(shù)字視頻編碼技術的進展算術編碼1960年，P.Elias提出了算術編碼的概念。1976年，R.Pasco和J.Rissanen分別用定長的寄存器實現(xiàn)了有限精度的算術編碼。1979年Rissanen和G.G.Langdon一起將算術編碼系統(tǒng)化，并于1981年實現(xiàn)了二進制編碼。1987年Witten等人發(fā)表了一個實用的算術編碼程序，即CACM87（后被ITU-T的H.263視頻壓縮標準采用）。同期，IBM公司發(fā)表了著名的Q-編碼器（后被JPEG建議的擴展系統(tǒng)和JBIG二值圖像壓縮標準采用）。3.1.2數(shù)字視頻編碼技術的進展算術編碼3.1.2數(shù)字視頻編碼技術的進展基于模型編碼1983年瑞典的Forchheimer和Fahlander提出了基于模型編碼（Model-BasedCoding）的思想。3.1.2數(shù)字視頻編碼技術的進展基于模型編碼3.1.2數(shù)字視頻編碼技術的進展小波變換編碼1986年，Meyer在理論上證明了一維小波函數(shù)的存在。1987年Mallat提出了多尺度分析的思想及多分辨率分析的概念，提出了相應的快速小波算法——Mallat算法，并把它有效地應用于圖像分解和重構。1989年，小波變換開始用于多分辨率圖像描述。3.1.2數(shù)字視頻編碼技術的進展小波變換編碼3.1.2數(shù)字視頻編碼技術的進展分層可分級編碼20世紀90年代中后期，Internet迅猛發(fā)展，移動通信也迅速在全球普及，因此人們開始有了在網絡上傳輸視頻和圖像的愿望。在網絡上傳輸視頻和圖像等多媒體信息除了要解決誤碼問題之外，最大的挑戰(zhàn)在于用戶可以獲得的帶寬在不停地變化。為了適應網絡帶寬的變化，提出了分層（layered）、可分級（scalable）編碼的思想。3.1.2數(shù)字視頻編碼技術的進展分層可分級編碼3.1.2數(shù)字視頻編碼技術的進展壓縮編碼技術無損編碼有損編碼哈夫曼編碼游程編碼算術編碼有損預測編碼

變換編碼

其他編碼3.1.2數(shù)字視頻編碼技術的進展壓縮編碼技術無損編碼有損編碼哈夫曼編碼游程編碼算術編碼有損預無失真編碼

無失真編碼又稱無損編碼、信息保持編碼、熵編碼。熵編碼是純粹基于信號統(tǒng)計特性的一種編碼方法，它利用信源概率分布的不均勻性，通過變長編碼來減少信源數(shù)據冗余，解碼后還原的數(shù)據與壓縮編碼前的原始數(shù)據完全相同而不引入任何失真。

無失真編碼的壓縮比較低，可達到的最高壓縮比受到信源熵的理論限制，一般為2∶1到5∶1。最常用的無失真編碼方法有哈夫曼(Huffman)編碼、算術編碼和游程編碼(Run-LengthEncoding，RLE)等。3.1.2數(shù)字視頻編碼技術的進展無失真編碼3.1.2數(shù)字視頻編碼技術的進展限失真編碼

限失真編碼也稱有損編碼、非信息保持編碼、熵壓縮編碼。

限失真編碼方法利用了人類視覺的感知特性，允許壓縮過程中損失一部分信息，雖然在解碼時不能完全恢復原始數(shù)據，但是如果把失真控制在視覺閾值以下或控制在可容忍的限度內，則不影響人們對圖像的理解，卻換來了高壓縮比。在限失真編碼中，允許的失真愈大，則可達到的壓縮比愈高。

常見的限失真編碼方法有：預測編碼、變換編碼、矢量量化、基于模型的編碼等。3.1.2數(shù)字視頻編碼技術的進展限失真編碼3.1.2數(shù)字視頻編碼技術的進展3.1數(shù)字視頻編碼概述3.2熵編碼3.3預測編碼3.4變換編碼第3章數(shù)字視頻編碼原理3.1數(shù)字視頻編碼概述第3章數(shù)字視頻編碼原理3.2熵編碼

熵編碼的基本原理就是去除圖像信源在空間和時間上的相關性，去除圖像信源像素值的概率分布不均勻性，使編碼碼字的平均碼長接近信源的熵而不產生失真。由于這種編碼完全基于圖像的統(tǒng)計特性，因此，有時也稱其為統(tǒng)計編碼。哈夫曼(Huffman)編碼算術編碼游程編碼(Run-LengthEncoding，RLE)3.2熵編碼熵編碼的基本原理就是去除圖像信

哈夫曼(Huffman)于1952年提出一種編碼方法，完全依據符號出現(xiàn)概率來構造異字頭（前綴）的平均長度最短的碼字，有時稱之為最佳編碼。哈夫曼編碼是一種可變長度編碼（VariableLengthCoding，VLC），各符號與碼字一一對應，是一種分組碼。3.2.1哈夫曼編碼哈夫曼(Huffman)于1952年提出一種

Huffman編碼過程（1）

把信源符號按概率大小順序排列，并設法按逆次序分配碼字的長度。在分配碼字的長度時，首先將出現(xiàn)概率最小的兩個符號的概率相加，合成一個概率；第二步把這個合成概率看成是一個新組合符號的概率，重復上述操作，直到最后只剩下兩個符號的概率為止。3.2.1哈夫曼編碼Huffman編碼過程（1）把信源符號按概率大小順序排

完成以上概率相加順序排列后，再反過來逐步向前進行編碼，每一步有兩個分支，各賦予一個二進制碼，可以對概率大的編碼賦予0，概率小的編碼賦予1。反之，也可以對概率大的編碼賦予1，概率小的編碼賦予0。

Huffman編碼過程（2）3.2.1哈夫曼編碼完成以上概率相加順序排列后，再反過來逐步向前進行Huf

Huffman編碼舉例編碼過程cbafe7/225/224/222/2210f=01e=11a=10b=001c=0001d=0000d1/223/226/2222/2213/229/223/2210101010aaaa

bbb

cc

d

eeeee

fffffffHuffman編碼舉例編碼過程cbafe7/225/224輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04

Huffman編碼舉例輸入輸入概率Huffman編碼舉例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1

Huffman編碼舉例輸入輸入概率第一步Huffman編碼舉例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1

Huffman編碼舉例輸入輸入概率第一步第二步Huffman編碼舉例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3

Huffman編碼舉例輸入輸入概率第一步第二步第三步Huffman編碼舉例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步Huffman編碼舉例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000Huffma輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S1=1

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S1=1Hu輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S2=00H輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S3=011

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S3=011輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S4=0100輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S5=01010

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S5=0101輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S6=0101例：信源有四個符號：

Xa1a2a3a41/21/41/81/8信源熵：Huffman（二進制編碼）a1a2a3a4010110111

平均碼長：Iav=(1/2)1+(1/4)2+(1/8)6=1.75bit/字符編碼效率：=1.75/1.75=100%

編碼冗余：R=0a11/2a21/4a31/8a41/800011/211/41010110111例：信源有四個符號：Huffman（二進制編碼）4個符號的等長碼：

B=log24=2bita1a2a3a400011011L=2

編碼效率：=H(X)/L=1.75/2=87.5%Huffman編碼舉例：原信源輸出序列：a1

a2a1a3a2

a1a1

a4…..

編碼后的序列：01001101000111...4個符號的等長碼：Huffman編碼舉例：Huffman碼解碼Huffman碼是非歧義的，在解碼過程中，對某個碼字的解釋是唯一的。原信源輸出序列：a1a2a1a3a2a1a1a4…..，編碼后的序列：01001101000111...當接收端收到碼流01001101000111……時，按照碼表，以0開頭的碼字只有0，因此，解出第1個符號為a1；去掉已解碼的0后，碼流剩下1001101000111，以1開頭，第2比特是0，因此，碼字是10，因此，解出第2個符號為a2；……..順著碼樹解碼，樹根→樹干→樹枝→樹葉00010a110a211110a3111a4碼樹結構00010a110a2110a3111a411Huffman碼解碼Huffman碼是非歧義的，在解碼過哈夫曼編碼的特點哈夫曼編碼的算法是確定的，但編出的碼并非是唯一的。由于哈夫曼編碼的依據是信源符號的概率分布，故其編碼效率取決于信源的統(tǒng)計特性。哈夫曼碼沒有錯誤保護功能。哈夫曼碼是可變長度碼，碼字字長參差不齊，輸出碼率是變化的。因此，對于恒定碼率信道，需要增加輸出緩存器來平滑。對信源進行哈夫曼編碼后，形成了一個哈夫曼編碼表，解碼時，必須參照這一哈夫編碼表才能正確解碼。3.2.1哈夫曼編碼哈夫曼編碼的特點3.2.1哈夫曼編碼3.2.1哈夫曼編碼3.2.1哈夫曼編碼從理論上分析，采用哈夫曼編碼可以獲得最佳信源字符編碼效果;實際應用中，由于信源字符出現(xiàn)的概率并非滿足2的負冪次方，因此往往無法達到理論上的編碼效率和壓縮比。3.2.2算術編碼從理論上分析，采用哈夫曼編碼可以獲得最佳信源字符編碼效果;3設字符序列{x，y}對應的概率為{1/3，2/3}，Nx和Ny分別表示字符x和y的最佳碼長，則根據信息論有：

3.2.2算術編碼設字符序列{x，y}對應的概率為{1/3，2/3}，Nx和N字符x、y的最佳碼長分別為1.58bit和0.588bit;這表明，要獲得最佳編碼效果，需要采用小數(shù)碼字長度,這是不可能實現(xiàn)的;即采用哈夫曼方法對{x，y}的碼字分別為0和1，也就是兩個符號信息的編碼長度都為1。對于出現(xiàn)概率大的字符y并未能賦予較短的碼字;實際編碼效果往往不能達到理論效率;為提高編碼效率，Elias等人提出了算術編碼算法。3.2.2算術編碼字符x、y的最佳碼長分別為1.58bit和0.588bit;

算術編碼是一種非分組編碼，它用一個浮點數(shù)值表示整個信源符號序列。算術編碼將被編碼的信源符號序列表示成實數(shù)半開區(qū)間［0，1）中的一個數(shù)值間隔。這個間隔隨著信源符號序列中每一個信源符號的加入逐步減小，每次減小的程度取決于當前加入的信源符號的先驗概率。3.2.2算術編碼算術編碼是一種非分組編碼，它用一個浮點數(shù)值表符號序列S3S3S2S4……為例S1S2S3S4S1S2S3S4S1S2S3S401/83/87/81.000.0010.0110.1111.00.0110.1110.01110.10010.1101在算術編碼中通常采用二進制分數(shù)表示概率，每個符號所對應的概率區(qū)間都是半開區(qū)間，即該區(qū)間包括左端點，而不包括右端點，如S1對應[0,0.001)，S2

對應[0.001,0.01)等。3.2.2算術編碼符號序列S3S3S2S4……為例S1S2S3S4S1S2游程編碼，也稱行程編碼或游程（行程）長度編碼（RunLengthEncoding，RLE）游程：具有相同灰度值的像素序列。游程長度：灰度值相同的相鄰像素的數(shù)目。游程編碼思想：去除像素冗余。用游程的灰度和游程的長度代替游程本身。例：設重復次數(shù)為iC,重復像素值為iP

編碼為：iPiCiPiCiPiC

編碼前：aaaaaaabbbbbbcccccccc

編碼后：a7b6c83.2.3游程編碼游程編碼，也稱行程編碼或游程（行程）長度編碼（RunLen由于一幅圖像中有許多顏色相同的圖塊，用一整數(shù)對存儲一個像素的顏色值及相同顏色像素的數(shù)目（長度）。例如：（G，L）

長度顏色值編碼時采用從左到右，從上到下的排列，每當遇到一串相同數(shù)據時就用該數(shù)據及重復次數(shù)代替原來的數(shù)據串。000000003333333333222222222226666666111111111111111111111111555555555555888888888888888888555555555555553333222222222222222222(0,8)(3,10)(2,11)(6,7)(1,18)(1,6)(5,12)(8,18)(5,14)(3,4)(2,18)18*7的像素顏色僅用11對數(shù)據3.2.3游程編碼由于一幅圖像中有許多顏色相同的圖塊，用一整數(shù)對存儲一個像素的3.1數(shù)字視頻編碼概述3.2熵編碼3.3預測編碼3.4變換編碼第3章數(shù)字視頻編碼原理3.1數(shù)字視頻編碼概述第3章數(shù)字視頻編碼原理3.3預測編碼

預測編碼的基本原理就是利用圖像數(shù)據的相關性，利用已傳輸?shù)南袼刂祵Ξ斍靶枰獋鬏數(shù)南袼刂颠M行預測，然后對當前像素的實際值與預測值的差值（即預測誤差）進行編碼傳輸，而不是對當前像素值本身進行編碼傳輸，以去除圖像數(shù)據中的空間相關冗余或時間相關冗余。3.3預測編碼預測編碼的基本原理就是利用圖預測編碼：根據某一模型，利用信號以往的樣本值對新樣本值進行預測，對預測誤差進行編碼。對于相關性較強的信號，如果建立合適的模型，預測誤差的幅值將遠遠小于原始信號，從而可以用較少的量化級對其誤差信號進行量化，得到較大的數(shù)據壓縮效果。3.3.1幀內預測編碼預測編碼：根據某一模型，利用信號以往的樣本值對新樣本值進行預問題：能否精確地預測數(shù)據源輸出？答案：否數(shù)據源是不確定的幾乎沒有一個實際的系統(tǒng)能找到可以精確預測輸出的模型能找到的最優(yōu)預測模型是以某種最小誤差意義下的預測模型。3.3.1幀內預測編碼問題：能否精確地預測數(shù)據源輸出？3.3.1幀內預測編碼對于靜止圖像，由于相鄰像素具有很強的相關性，這樣當前像素的灰度（顏色）值可用前面已經出現(xiàn)的像素值進行預測，得到一個預測值，對實際值與預測值的差值進行編碼，3.3.1幀內預測編碼對于靜止圖像，由于相鄰像素具有很強的相關性，這樣當前像素的灰3.3.1幀內預測編碼1.DPCM系統(tǒng)的基本原理

DPCM(DifferentialPulseCodeModulation，差分脈沖編碼調制)3.3.1幀內預測編碼1.DPCM系統(tǒng)的基本原理2.預測模型

設時刻之前的樣本值與預測值之間的關系呈現(xiàn)某種函數(shù)形式線性預測編碼器非線性預測編碼器3.3.1幀內預測編碼2.預測模型3.3.1幀內預測編碼

在圖像數(shù)據壓縮中，常用如下幾種線性預測方案：前值預測，即一維預測，即采用同一掃描行中前面已知的若干個樣值來預測。二維預測，即不但用同一掃描行中的前面幾個樣值，而且還要用以前幾行掃描行中樣值來預測。

3.3.1幀內預測編碼在圖像數(shù)據壓縮中，常用如下幾種線性預測方案：3.3.2幀間預測編碼序列圖像在時間上的冗余情況可分為如下幾種：對于靜止不動的場景，當前幀和前一幀的圖像內容是完全相同的。對于運動的物體，只要知道其運動規(guī)律，就可以從前一幀圖像推算出它在當前幀中的位置。攝像機對著場景的橫向移動、焦距變化等操作會引起整個圖像的平移、放大或縮小。對于這種情況，只要攝像機的運動規(guī)律和鏡頭改變的參數(shù)已知，圖像隨時間所產生的變化也是可以推算出來的。

3.3.2幀間預測編碼序列圖像在時間上的冗余情況可分為如下幀間預測的依據：圖像序列在時間軸方向的相關性；物體的背景或物體的一部分相對不變或變化緩慢；人類的視覺特性：人類的視覺對靜止圖像有較高的空間分辨率，但是可以減少傳輸幀數(shù)來降低時間軸分辨率，未傳輸?shù)膸梢酝ㄟ^計算補出來；對運動圖像分辨率低，可以對這一部分圖像降低清晰度。3.3.2幀間預測編碼幀間預測的依據：3.3.2幀間預測編碼為什么進行運動補償預測？對于活動圖像編碼，幀間預測是主要的手段；基本幀間預測方法對于存在大量靜止區(qū)域或緩變區(qū)域的圖像，預測效果不錯；對于活動的物體，預測效果不理想；對于一些發(fā)生運動的圖像進行預測編碼，采用運動補償預測的方法。3.3.2幀間預測編碼為什么進行運動補償預測？3.3.2幀間預測編碼運動補償預測

3.3.2幀間預測編碼運動補償預測3.3.2幀間預測編碼運動補償預測的基本原理：自然場景的視頻圖像只有其中的部分區(qū)域在運動，同一場景相鄰的兩幀圖像之間差異也不會太大，編碼器無需將視頻序列中每幀圖像的所有信息都進行編碼后傳輸給解碼器端，只要將當前幀中目標的運動信息告知解碼器端，解碼器可根據運動信息和前一幀圖像內容來更新當前幀圖像，獲得當前幀的真實數(shù)據。（可有效降低編碼所需數(shù)據量）從序列圖像中提取有關物體運動的信息的過程——運動估計（如何快速、有效的獲得足夠精度的運動矢量）；把前一幀相應的運動部分信息根據運動矢量補償過來的過程——運動補償（MotionCompensation,MC）。3.3.2幀間預測編碼運動補償預測的基本原理：3.3.2幀間預測編碼

運動估計——將當前幀活動圖像分為若干局部結構（像素塊），檢測出每個局部結構在前一幀圖像中的位置，從而可以估計出這個結構的位移。即對運動物體從前一幀到當前幀位移的方向和像素數(shù)作出估計，也就是求出運動矢量。

運動補償——根據求出的運動矢量，找到當前幀的像素（或像素塊）是從前一幀的哪個位置移動過來的，從而得到當前幀像素（或像素塊）的預測值。3.3.2幀間預測編碼運動估計——將當前幀活動圖像分為若干局部結構（像素塊），檢運動估計與運動補償預測編碼步驟：分割圖像為若干局部結構——劃分靜止和運動區(qū)域；最簡單方法：分塊運動估計——對每一個運動物體進行位移估計；運動補償——由位移估計建立同一運動物體在不同幀空間位置對應關系，建立預測關系；對于運動補償后的位移幀差信號、運動矢量進行編碼傳輸。3.3.2幀間預測編碼運動估計與運動補償預測編碼步驟：3.3.2幀間預測編碼運動估計方法：像素遞歸法：根據像素間亮度的變化和梯度，通過遞歸修正的方法來估計每個像素的運動矢量。接收端在與發(fā)送端同樣的條件下，用與發(fā)送端相同的方法進行運動估值。像素遞歸法估計精度高，可以滿足運動補償幀內插的要求。但接收端較復雜，不利于一發(fā)多收（如數(shù)字電視廣播等）的應用。塊匹配算法：塊匹配算法對當前幀圖像的每一子塊，在前一幀（第K-1幀）的一定范圍內搜索最優(yōu)匹配，并認為本圖像子塊就是從前一幀最優(yōu)匹配塊位置處平移過來的。塊匹配算法雖然作了一定假設（假設位于同一圖像子塊內的所有像素都作相同的運動，且只作平移運動），但滿足了計算復雜度和實時實現(xiàn)的要求。3.3.2幀間預測編碼運動估計方法：3.3.2幀間預測編碼塊匹配算法(BMA)：3.3.2幀間預測編碼塊匹配算法(BMA)：3.3.2幀間預測編碼運動矢量的算法框圖3.3.2幀間預測編碼運動矢量的算法框圖3.3.2幀間預測編碼方塊大小的選取

塊大時，一個方塊可能包含多個作不同運動的物體，塊內各像素作相同平移運動的假設難以成立，影響估計精度。

若塊太小，則估計精度容易受噪聲干擾的影響，不夠可靠，而且傳送運動矢量所需的附加比特數(shù)過多，不利于數(shù)據壓縮。 一般都用16×16像素的塊作為匹配單元。塊匹配算法(BMA)方塊大小的選取塊匹配算法(BMA)最優(yōu)匹配準則絕對差均值（MAD，MeanAbsoluteDifference）最小準則

均方誤差（MSE，MeanSquaredError）最小準則歸一化互相關函數(shù)最大準則

塊匹配算法(BMA)最優(yōu)匹配準則塊匹配算法(BMA)最優(yōu)匹配點的搜索方法窮盡搜索（fullsearch，也稱全搜索）快速搜索：其算法共同之處在于它們把使準則函數(shù)（例如，MAD）趨于極小的方向視同為最小失真方向，并假定準則函數(shù)在偏離最小失真方向時是單調遞增的，即認為它在整個搜索區(qū)內是(i,j)的單極點函數(shù)，有唯一的極小值，而快速搜索是從任一猜測點開始沿最小失真方向進行的。分級搜索：先通過對原始圖像濾波和亞采樣得到一個圖像序列的低分辨率表示，再對所得低分辨率圖像進行全搜索。由于分辨率降低，使得搜索次數(shù)成倍減少，這一步可以稱為粗搜索。然后，再以低分辨率圖像搜索的結果作為下一步細搜索的起始點。經過粗、細兩級搜索，便得到了最終的運動矢量估值。塊匹配算法(BMA)最優(yōu)匹配點的搜索方法塊匹配算法(BMA)BMA常用搜索算法——三步搜索法：BMA常用搜索算法——三步搜索法：BMA常用搜索算法——二維對數(shù)搜索法：BMA常用搜索算法——二維對數(shù)搜索法：在視頻幀序列中設置參照幀，且第1幀總是參照幀。對于當前的編碼幀，首先在該幀的前一幀和/或后一幀（參照幀）中尋找與該幀的一個圖像方塊最優(yōu)匹配的圖像方塊。如果找到這樣的最優(yōu)匹配塊，則進行下列計算：計算當前塊的像素值與參照幀中最優(yōu)匹配塊（稱參照塊）的像素值之間的差值，即預測誤差；計算當前塊相對于參照塊在水平（x）和垂直（y）兩個方向上的位移，即運動矢量。如果找不到最優(yōu)匹配塊，則必須進行幀內編碼，即對當前塊的像素樣本值進行編碼傳輸。

運動補償幀間預測編碼過程在視頻幀序列中設置參照幀，且第1幀總是參照幀。運動補償幀間預幀間預測編碼原理圖幀間預測編碼原理圖單向運動補償預測：只使用前參照幀或后參照幀中的一個來進行預測。雙向運動補償預測：使用前、后兩個幀作為參照幀來計算各塊的運動矢量，最后只選用與具有最小匹配誤差的參照幀相關的運動矢量值。插值運動補償預測：取前參照幀預測值與后參照幀預測值的平均值。這時，需要對兩個運動矢量分別進行編碼傳輸。運動補償幀間預測類型單向運動補償預測：只使用前參照幀或后參照幀中的一個來進行預測雙向預測B幀的壓縮編碼原理雙向預測B幀的壓縮編碼原理3.1數(shù)字視頻編碼概述3.2熵編碼3.3預測編碼3.4變換編碼第3章數(shù)字視頻編碼原理3.1數(shù)字視頻編碼概述第3章數(shù)字視頻編碼原理預測編碼希望通過對信源建模盡可能精確地預測數(shù)據，然后對預測誤差進行編碼。變換編碼的思路：將原始數(shù)據從時間域或者空間域“變換”到另一個更為緊湊表示、適合于壓縮的變換域（通常為頻域），從而得到比預測編碼更高效率的數(shù)據表示（壓縮）。預測編碼消除相關性的能力有限，變換編碼是一種更高效的壓縮編碼。3.4.1變換編碼的基本原理3.4.1變換編碼的基本原理3.4.2

基于DCT的圖像編碼3.4.2基于DCT的圖像編碼8×8二維DCT變換8×8二維DCT反變換當時，當u、v為其他值時3.4.2

基于DCT的圖像編碼8×8二維DCT變換3.4.2基于DCT的圖像編碼

8×8二維DCT反變換的變換核函數(shù)為

按u，v分別展開后得到64個8×8像素的圖像塊組，稱為基圖像。3.4.2

基于DCT的圖像編碼3.4.2基于DCT的圖像編碼8×8二維DCT變換基圖像8×8二維DCT變換基圖像量化

量化處理是一個多到一的映射，它是造成DCT編解碼信息損失的根源。

根據人眼的視覺特性，對不同的變換系數(shù)設置不同的量化步長。3.4.2

基于DCT的圖像編碼量化3.4.2基于DCT的圖像編碼JPEG標準中亮度DCT系數(shù)的量化步長3.4.2

基于DCT的圖像編碼JPEG標準中亮度DCT系數(shù)的量化步長3.4.2基于DCJPEG標準中色度DCT系數(shù)的量化步長3.4.2

基于DCT的圖像編碼JPEG標準中色度DCT系數(shù)的量化步長3.4.2基于DCZig-Zag（或稱“Z”字形，“之”字形）掃描

DC直流系數(shù)AC01交流系數(shù)掃描開始交流系數(shù)掃描結束AC07AC70AC77變換系數(shù)熵編碼3.4.2

基于DCT的圖像編碼Zig-Zag（或稱“Z”字形，“之”字形）掃描DC直流系數(shù)直流分量（DC）：相鄰圖像子塊的直流分量（圖像子塊的平均樣值）也存在著相關性，所以對DC的量化系數(shù)用DPCM編碼較合適，即對當前塊和前一塊的DC系數(shù)的差值進行編碼。交流分量（AC）：把數(shù)值為0的連續(xù)長度（即0游長）和非0值結合起來構成一個事件（Run，Level），然后再對事件（Run，Level）進行熵編碼。

變換系數(shù)熵編碼3.4.2

基于DCT的圖像編碼變換系數(shù)熵編碼3.4.2基于DCT的圖像編碼8×8亮度子塊DCT第一步：DCT變換

3.4.2

基于DCT的圖像編碼8×8亮DCT第一步：DCT變換3.4.2基于DCT的第二步：量化。將DCT系數(shù)矩陣［F(u,v)］中的每個元素與量化步長矩陣［S(u,v)］中的對應元素相除后,進行四舍五入運算。3.4.2

基于DCT的圖像編碼第二步：量化。將DCT系數(shù)矩陣［F(u,v)］中的每個元素與量化結果第三步：Zig-Zag掃描第四步：編碼傳輸游程編碼：本例為（39，-3，2，1，

-1，1，0，0，0，0，0，

-1，EOB）。EOB表示塊結束，接收端收到EOB后自動將64個元素中余下的元素補零。3.4.2

基于DCT的圖像編碼量化結果第三步：Zig-Zag掃描第四步：編碼傳輸3.4.DCT解碼復原第一步：恢復量化系數(shù)矩陣，將EOB后的元素自動補零。第二步：反量化（IQ）3.4.2

基于DCT的圖像編碼DCT解碼復原第一步：恢復量化系數(shù)矩陣，將EOB后的元素自動第三步：IDCT主要原因是量化所致。重建后的信號與原信號相差很小

第三步：DCT反變換（IDCT）第三步：IDCT主要原因是量化所致。重建后的信號與原信號相差Question?Question?第3章數(shù)字視頻編碼原理第3章數(shù)字視頻編碼原理了解圖像和視頻編碼技術的發(fā)展歷程，熟悉視頻編碼的各種方法。重點掌握哈夫曼編碼、算術編碼、預測編碼和基于DCT的變換編碼基本原理。掌握運動估計和運動補償預測編碼的基本原理。本章學習目標了解圖像和視頻編碼技術的發(fā)展歷程，熟悉視頻編碼的各種方法。本3.1數(shù)字視頻編碼概述3.2熵編碼3.3預測編碼3.4變換編碼第3章數(shù)字視頻編碼原理3.1數(shù)字視頻編碼概述第3章數(shù)字視頻編碼原理3.1.1數(shù)字視頻壓縮的必要性和可能性數(shù)據壓縮的理論基礎是信息論。從信息論的角度來看，壓縮就是去掉數(shù)據中的冗余，即保留不確定的信息，去掉確定的信息（可推知的），也就是用一種更接近信息本質的描述來代替原有冗余的描述。在一般的圖像和視頻數(shù)據中，主要存在以下幾種形式的冗余。3.1.1數(shù)字視頻壓縮的必要性和可能性數(shù)據壓縮的理論基礎是空間冗余：也稱為空域冗余，是一種與像素間相關性直接聯(lián)系的數(shù)據冗余。

例:圖像中包含許多規(guī)則物體，它們的亮度、飽和度及顏色可能都一樣，因此，圖像在空間上具有很強的相關性。例如Lenna圖像的臉部和肩部。3.1.1數(shù)字視頻壓縮的必要性和可能性空間冗余：也稱為空域冗余，是一種與像素間相關性直接聯(lián)系的數(shù)據時間冗余：也稱為時域冗余，它是針對視頻序列圖像而言的。

視頻序列每秒有25~30幀圖像，相鄰幀之間的時間間隔很??；同時實際生活中的運動物體具有運動一致性，使得視頻序列圖像之間有很強的相關性。

3.1.1數(shù)字視頻壓縮的必要性和可能性時間冗余：也稱為時域冗余，它是針對視頻序列圖像而言的。3.1統(tǒng)計冗余

信源熵：如果將信源所有可能事件的信息量進行平均，就得到了信源熵(entropy)。熵就是平均信息量。

當xj等概率時，H(X)最大。當xj

非等概率時，H(X)不是最大，就存在冗余。

采用可變長編碼技術，對出現(xiàn)概率大的符號用短碼字表示，對出現(xiàn)概率小的符號用長碼字表示，則可去除符號冗余，從而節(jié)約碼字，這就是熵編碼的思想。3.1.1數(shù)字視頻壓縮的必要性和可能性統(tǒng)計冗余當xj等概率時，H(X)最大。結構冗余：在有些圖像的部分區(qū)域內有著很相似的紋理結構，或是圖像的各個部分之間存在著某種關系，例如自相似性等，這些都是結構冗余的表現(xiàn)。

分形圖像編碼的基本思想就是利用了結構的自相似性。3.1.1數(shù)字視頻壓縮的必要性和可能性結構冗余：在有些圖像的部分區(qū)域內有著很相似的紋理結構，或是圖知識冗余：在某些特定的應用場合，編碼對象中包含的信息與某些先驗的基本知識有關。例如:人臉的圖像有同樣的結構：嘴的上方有鼻子，鼻子上方有眼睛，鼻子在中線上……

可以利用這些先驗知識為編碼對象建立模型。通過提取模型參數(shù)，對參數(shù)進行編碼而不是對圖像像素值直接進行編碼，可以達到非常高的壓縮比。這是模型基編碼（或稱知識基編碼、語義基編碼）的基本思想。3.1.1數(shù)字視頻壓縮的必要性和可能性知識冗余：在某些特定的應用場合，編碼對象中包含的信息與某些先人眼的視覺冗余

視覺冗余度是相對于人眼的視覺特性而言的。壓縮視覺冗余的核心思想是去掉那些相對人眼而言是看不到的或可有可無的圖像數(shù)據。對視覺冗余的壓縮通常反映在各種具體的壓縮編碼過程中。3.1.1數(shù)字視頻壓縮的必要性和可能性人眼的視覺冗余3.1.1數(shù)字視頻壓縮的必要性和可能性1948年提出電視信號的數(shù)字化，人們開始了對圖像壓縮編碼的研究工作。1952年哈夫曼給出最優(yōu)變長碼的構造方法。3.1.2數(shù)字視頻編碼技術的進展1948年提出電視信號的數(shù)字化，人們開始了對圖像壓縮編碼的研預測編碼1952年，貝爾實驗室的奧利弗等人開始研究線性預測編碼理論1958年，格雷哈姆用計算機模擬法研究圖像的DPCM方法1966年，奧尼爾通過理論分析和計算模擬比較了PCM和DPCM對電視信號進行編碼傳輸?shù)男阅?0世紀70年代開始進行了幀間預測編碼的研究20世紀80年代初開始對作運動補償預測所用的運動估值進行研究3.1.2數(shù)字視頻編碼技術的進展預測編碼3.1.2數(shù)字視頻編碼技術的進展變換編碼首先討論了包括K-L（Karhunen-Loeve）變換、傅立葉變換等正交變換1968年安德魯斯等人采用二維離散傅立葉變換（2D-DFT）提出了變換編碼此后相繼出現(xiàn)了沃爾什-哈達瑪（Walsh-Hadamard）變換、斜（Slant）變換、K-L變換、離散余弦變換（DCT）等3.1.2數(shù)字視頻編碼技術的進展變換編碼3.1.2數(shù)字視頻編碼技術的進展子帶編碼1976年美國貝爾系統(tǒng)的克勞切等人提出了話音的子帶編碼。1985年奧尼爾將子帶編碼引入到圖像編碼。3.1.2數(shù)字視頻編碼技術的進展子帶編碼3.1.2數(shù)字視頻編碼技術的進展算術編碼1960年，P.Elias提出了算術編碼的概念。1976年，R.Pasco和J.Rissanen分別用定長的寄存器實現(xiàn)了有限精度的算術編碼。1979年Rissanen和G.G.Langdon一起將算術編碼系統(tǒng)化，并于1981年實現(xiàn)了二進制編碼。1987年Witten等人發(fā)表了一個實用的算術編碼程序，即CACM87（后被ITU-T的H.263視頻壓縮標準采用）。同期，IBM公司發(fā)表了著名的Q-編碼器（后被JPEG建議的擴展系統(tǒng)和JBIG二值圖像壓縮標準采用）。3.1.2數(shù)字視頻編碼技術的進展算術編碼3.1.2數(shù)字視頻編碼技術的進展基于模型編碼1983年瑞典的Forchheimer和Fahlander提出了基于模型編碼（Model-BasedCoding）的思想。3.1.2數(shù)字視頻編碼技術的進展基于模型編碼3.1.2數(shù)字視頻編碼技術的進展小波變換編碼1986年，Meyer在理論上證明了一維小波函數(shù)的存在。1987年Mallat提出了多尺度分析的思想及多分辨率分析的概念，提出了相應的快速小波算法——Mallat算法，并把它有效地應用于圖像分解和重構。1989年，小波變換開始用于多分辨率圖像描述。3.1.2數(shù)字視頻編碼技術的進展小波變換編碼3.1.2數(shù)字視頻編碼技術的進展分層可分級編碼20世紀90年代中后期，Internet迅猛發(fā)展，移動通信也迅速在全球普及，因此人們開始有了在網絡上傳輸視頻和圖像的愿望。在網絡上傳輸視頻和圖像等多媒體信息除了要解決誤碼問題之外，最大的挑戰(zhàn)在于用戶可以獲得的帶寬在不停地變化。為了適應網絡帶寬的變化，提出了分層（layered）、可分級（scalable）編碼的思想。3.1.2數(shù)字視頻編碼技術的進展分層可分級編碼3.1.2數(shù)字視頻編碼技術的進展壓縮編碼技術無損編碼有損編碼哈夫曼編碼游程編碼算術編碼有損預測編碼

變換編碼

其他編碼3.1.2數(shù)字視頻編碼技術的進展壓縮編碼技術無損編碼有損編碼哈夫曼編碼游程編碼算術編碼有損預無失真編碼

無失真編碼又稱無損編碼、信息保持編碼、熵編碼。熵編碼是純粹基于信號統(tǒng)計特性的一種編碼方法，它利用信源概率分布的不均勻性，通過變長編碼來減少信源數(shù)據冗余，解碼后還原的數(shù)據與壓縮編碼前的原始數(shù)據完全相同而不引入任何失真。

無失真編碼的壓縮比較低，可達到的最高壓縮比受到信源熵的理論限制，一般為2∶1到5∶1。最常用的無失真編碼方法有哈夫曼(Huffman)編碼、算術編碼和游程編碼(Run-LengthEncoding，RLE)等。3.1.2數(shù)字視頻編碼技術的進展無失真編碼3.1.2數(shù)字視頻編碼技術的進展限失真編碼

限失真編碼也稱有損編碼、非信息保持編碼、熵壓縮編碼。

限失真編碼方法利用了人類視覺的感知特性，允許壓縮過程中損失一部分信息，雖然在解碼時不能完全恢復原始數(shù)據，但是如果把失真控制在視覺閾值以下或控制在可容忍的限度內，則不影響人們對圖像的理解，卻換來了高壓縮比。在限失真編碼中，允許的失真愈大，則可達到的壓縮比愈高。

常見的限失真編碼方法有：預測編碼、變換編碼、矢量量化、基于模型的編碼等。3.1.2數(shù)字視頻編碼技術的進展限失真編碼3.1.2數(shù)字視頻編碼技術的進展3.1數(shù)字視頻編碼概述3.2熵編碼3.3預測編碼3.4變換編碼第3章數(shù)字視頻編碼原理3.1數(shù)字視頻編碼概述第3章數(shù)字視頻編碼原理3.2熵編碼

熵編碼的基本原理就是去除圖像信源在空間和時間上的相關性，去除圖像信源像素值的概率分布不均勻性，使編碼碼字的平均碼長接近信源的熵而不產生失真。由于這種編碼完全基于圖像的統(tǒng)計特性，因此，有時也稱其為統(tǒng)計編碼。哈夫曼(Huffman)編碼算術編碼游程編碼(Run-LengthEncoding，RLE)3.2熵編碼熵編碼的基本原理就是去除圖像信

哈夫曼(Huffman)于1952年提出一種編碼方法，完全依據符號出現(xiàn)概率來構造異字頭（前綴）的平均長度最短的碼字，有時稱之為最佳編碼。哈夫曼編碼是一種可變長度編碼（VariableLengthCoding，VLC），各符號與碼字一一對應，是一種分組碼。3.2.1哈夫曼編碼哈夫曼(Huffman)于1952年提出一種

Huffman編碼過程（1）

把信源符號按概率大小順序排列，并設法按逆次序分配碼字的長度。在分配碼字的長度時，首先將出現(xiàn)概率最小的兩個符號的概率相加，合成一個概率；第二步把這個合成概率看成是一個新組合符號的概率，重復上述操作，直到最后只剩下兩個符號的概率為止。3.2.1哈夫曼編碼Huffman編碼過程（1）把信源符號按概率大小順序排

完成以上概率相加順序排列后，再反過來逐步向前進行編碼，每一步有兩個分支，各賦予一個二進制碼，可以對概率大的編碼賦予0，概率小的編碼賦予1。反之，也可以對概率大的編碼賦予1，概率小的編碼賦予0。

Huffman編碼過程（2）3.2.1哈夫曼編碼完成以上概率相加順序排列后，再反過來逐步向前進行Huf

Huffman編碼舉例編碼過程cbafe7/225/224/222/2210f=01e=11a=10b=001c=0001d=0000d1/223/226/2222/2213/229/223/2210101010aaaa

bbb

cc

d

eeeee

fffffffHuffman編碼舉例編碼過程cbafe7/225/224輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04

Huffman編碼舉例輸入輸入概率Huffman編碼舉例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1

Huffman編碼舉例輸入輸入概率第一步Huffman編碼舉例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1

Huffman編碼舉例輸入輸入概率第一步第二步Huffman編碼舉例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3

Huffman編碼舉例輸入輸入概率第一步第二步第三步Huffman編碼舉例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步Huffman編碼舉例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000Huffma輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S1=1

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S1=1Hu輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S2=00H輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S3=011

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S3=011輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S4=0100輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S5=01010

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S5=0101輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011

Huffman編碼舉例輸入輸入概率第一步第二步第三步第四步00000S6=0101例：信源有四個符號：

Xa1a2a3a41/21/41/81/8信源熵：Huffman（二進制編碼）a1a2a3a4010110111

平均碼長：Iav=(1/2)1+(1/4)2+(1/8)6=1.75bit/字符編碼效率：=1.75/1.75=100%

編碼冗余：R=0a11/2a21/4a31/8a41/800011/211/41010110111例：信源有四個符號：Huffman（二進制編碼）4個符號的等長碼：

B=log24=2bita1a2a3a400011011L=2

編碼效率：=H(X)/L=1.75/2=87.5%Huffman編碼舉例：原信源輸出序列：a1

a2a1a3a2

a1a1

a4…..

編碼后的序列：01001101000111...4個符號的等長碼：Huffman編碼舉例：Huffman碼解碼Huffman碼是非歧義的，在解碼過程中，對某個碼字的解釋是唯一的。原信源輸出序列：a1a2a1a3a2a1a1a4…..，編碼后的序列：01001101000111...當接收端收到碼流01001101000111……時，按照碼表，以0開頭的碼字只有0，因此，解出第1個符號為a1；去掉已解碼的0后，碼流剩下1001101000111，以1開頭，第2比特是0，因此，碼字是10，因此，解出第2個符號為a2；……..順著碼樹解碼，樹根→樹干→樹枝→樹葉00010a110a211110a3111a4碼樹結構00010a110a2110a3111a411Huffman碼解碼Huffman碼是非歧義的，在解碼過哈夫曼編碼的特點哈夫曼編碼的算法是確定的，但編出的碼并非是唯一的。由于哈夫曼編碼的依據是信源符號的概率分布，故其編碼效率取決于信源的統(tǒng)計特性。哈夫曼碼沒有錯誤保護功能。哈夫曼碼是可變長度碼，碼字字長參差不齊，輸出碼率是變化的。因此，對于恒定碼率信道，需要增加輸出緩存器來平滑。對信源進行哈夫曼編碼后，形成了一個哈夫曼編碼表，解碼時，必須參照這一哈夫編碼表才能正確解碼。3.2.1哈夫曼編碼哈夫曼編碼的特點3.2.1哈夫曼編碼3.2.1哈夫曼編碼3.2.1哈夫曼編碼從理論上分析，采用哈夫曼編碼可以獲得最佳信源字符編碼效果;實際應用中，由于信源字符出現(xiàn)的概率并非滿足2的負冪次方，因此往往無法達到理論上的編碼效率和壓縮比。3.2.2算術編碼從理論上分析，采用哈夫曼編碼可以獲得最佳信源字符編碼效果;3設字符序列{x，y}對應的概率為{1/3，2/3}，Nx和Ny分別表示字符x和y的最佳碼長，則根據信息論有：

3.2.2算術編碼設字符序列{x，y}對應的概率為{1/3，2/3}，Nx和N字符x、y的最佳碼長分別為1.58bit和0.588bit;這表明，要獲得最佳編碼效果，需要采用小數(shù)碼字長度,這是不可能實現(xiàn)的;即采用哈夫曼方法對{x，y}的碼字分別為0和1，也就是兩個符號信息的編碼長度都為1。對于出現(xiàn)概率大的字符y并未能賦予較短的碼字;實際編碼效果往往不能達到理論效率;為提高編碼效率，Elias等人提出了算術編碼算法。3.2.2算術編碼字符x、y的最佳碼長分別為1.58bit和0.588bit;

算術編碼是一種非分組編碼，它用一個浮點數(shù)值表示整個信源符號序列。算術編碼將被編碼的信源符號序列表示成實數(shù)半開區(qū)間［0，1）中的一個數(shù)值間隔。這個間隔隨著信源符號序列中每一個信源符號的加入逐步減小，每次減小的程度取決于當前加入的信源符號的先驗概率。3.2.2算術編碼算術編碼是一種非分組編碼，它用一個浮點數(shù)值表符號序列S3S3S2S4……為例S1S2S3S4S1S2S3S4S1S2S3S401/83/87/81.000.0010.0110.1111.00.0110.1110.01110.10010.1101在算術編碼中通常采用二進制分數(shù)表示概率，每個符號所對應的概率區(qū)間都是半開區(qū)間，即該區(qū)間包括左端點，而不包括右端點，如S1對應[0,0.001)，S2

對應[0.001,0.01)等。3.2.2算術編碼符號序列S3S3S2S4……為例S1S2S3S4S1S2游程編碼，也稱行程編碼或游程（行程）長度編碼（RunLengthEncoding，RLE）游程：具有相同灰度值的像素序列。游程長度：灰度值相同的相鄰像素的數(shù)目。游程編碼思想：去除像素冗余。用游程的灰度和游程的長度代替游程本身。例：設重復次數(shù)為iC,重復像素值為iP

編碼為：iPiCiPiCiPiC

編碼前：aaaaaaabbbbbbcccccccc

編碼后：a7b6c83.2.3游程編碼游程編碼，也稱行程編碼或游程（行程）長度編碼（RunLen由于一幅圖像中有許多顏色相同的圖塊，用一整數(shù)對存儲一個像素的顏色值及相同顏色像素的數(shù)目（長度）。例如：（G，L）

長度顏色值編碼時采用從左到右，從上到下的排列，每當遇到一串相同數(shù)據時就用該數(shù)據及重復次數(shù)代替原來的數(shù)據串。000000003333333333222222222226666666111111111111111111111111555555555555888888888888888888555555555555553333222222222222222222(0,8)(3,10)(2,11)(6,7)(1,18)(1,6)(5,12)(8,18)(5,14)(3,4)(2,18)18*7的像素顏色僅用11對數(shù)據3.2.3游程編碼由于一幅圖像中有許多顏色相同的圖塊，用一整數(shù)對存儲一個像素的3.1數(shù)字視頻編碼概述3.2熵編碼3.3預測編碼3.4變換編碼第3章數(shù)字視頻編碼原理3.1數(shù)字視頻編碼概述第3章數(shù)字視頻編碼原理3.3預測編碼

預測編碼的基本原理就是利用圖像數(shù)據的相關性，利用已傳輸?shù)南袼刂祵Ξ斍靶枰獋鬏數(shù)南袼刂颠M行預測，然后對當前像素的實際值與預測值的差值（即預測誤差）進行編碼傳輸，而不是對當前像素值本身進行編碼傳輸，以去除圖像數(shù)據中的空間相關冗余或時間相關冗余。3.3預測編碼預測編碼的基本原理就是利用圖預測編碼：根據某一模型，利用信號以往的樣本值對新樣本值進行預測，對預測誤差進行編碼。對于相關性較強的信號，如果建立合適的模型，預測誤差的幅值將遠遠小于原始信號，從而可以用較少的量化級對其誤差信號進行量化，得到較大的數(shù)據壓縮效果。3.3.