第二章數(shù)字技術22游程編碼算術預測

§2.2.2游程編碼游程編碼(Run-Lengthcoding，RLC)的基本思想，是將具有相同數(shù)值的、連續(xù)出現(xiàn)的信源符號構(gòu)成的符號串用其數(shù)值及串的長度表示。二值圖像游程編碼的基本思想是，當按照二值圖像從左到右的掃描順序觀察每一行時發(fā)現(xiàn)，二值圖像的每一掃描行均由交替出現(xiàn)的白像素游程(稱作白長)和黑像素游程(稱作黑長)組成。白游程的后面必然是黑游程，反之亦然，黑游程的后面必然是白游程。因而只要知道了各掃描線的頭一個游程是黑還是白，就不再需要指示游程黑白的信息了。進一步對不同長度的白長和黑長按其出現(xiàn)概率的不同分別配以不同長度的碼字，就是二值圖像的RLC。一維游程編碼圖

游程編碼示意圖圖像的游程熵：其中，黑游程熵的估計值H0，白游程熵的估計值H0，黑游程長度的平均值L0，白游程長度的平均值L1。其中，令符號aj代表長度為j的1個黑色游程，用圖像中長度為j的黑色游程數(shù)去除圖像中所有黑色游程的總數(shù)就可近似得到黑色游程源的熵的估計H0二維游程編碼

二維游程編碼方法，不是直接對游程長度本身進行編碼，而是對掃描行之間游程長度變化的差值進行編碼。由于圖像所存在的相關性。這種編碼的數(shù)碼率一定會下降。

圖

二維游程編碼示意圖對各個?’和?”以及黑白區(qū)域的起點和終點分別進行編碼?’:相鄰行間游程起點的差值；?”：相鄰行間游程長度的差值

游程編碼綜述游程編碼的優(yōu)點是算法簡單、易于實現(xiàn)，由于是將信源符號序列中的相同字符轉(zhuǎn)換成一個計數(shù)字段再加上一個重復字符標志，所以對于二值圖像最為有效；缺點是對于特定的不連續(xù)符號序列，會出現(xiàn)編碼后數(shù)據(jù)量增加的情況。此外，變長碼的固有缺點仍然存在，即需要較大容量的緩沖和較低誤碼的優(yōu)質(zhì)信道。§2.2.3算術編碼

算術編碼的基本思路：從序列出發(fā)，將各信源序列的概率映射到[0,1]區(qū)間上，使得每個序列對應該區(qū)間內(nèi)的一個點，即一個二進制的小數(shù)。這些點將[0,1]區(qū)間分成許多小段，每段的長度等于某一序列的概率，整個編碼過程就是單位區(qū)間[0,1]內(nèi)的子分過程。算術編碼是一種從整個符號系列出發(fā)，采用遞推形式連續(xù)編碼的方法。在算術編碼中，字母表中的符號和碼字間不再存在一一對應關系，一個算術碼字要賦給整個信源符號序列（即不是一次編一個號），而碼字本身確定0和1之間的一個實數(shù)區(qū)間。1、算術編碼原理算術編碼和上述霍夫曼塊編碼的區(qū)別就在于：在算術編碼中，輸入序列（即被賦給單個碼字的符號塊）的長度，是可變的，可以說，算術編碼是將可變長碼字賦給可變長符號塊。正是由于算術編碼不需要為定長符號塊分配整數(shù)長的碼字，理論上能達到無損編碼定理所規(guī)定的最低限。1、算術編碼原理在編碼過程中，盡管在計算時有乘法運算，但可以通過移位實現(xiàn)，即通過加法和移位實現(xiàn)算術運算。在解碼時，要除以符號區(qū)間概率，也可以通過移位實現(xiàn)，即通過減法和移位實現(xiàn)算術解碼。這正是把這種編碼方法稱為算術碼的原因。2、

算術碼分析算術編碼跳出了分組編碼的范疇，從全序列出發(fā)，采用遞推形式的連續(xù)編碼，它不是將單個的信源符號映射成一個碼字，而是將整個符號序列映射為實數(shù)軸上[0,1）區(qū)間內(nèi)的一個小區(qū)間，其長度等于該序列的概率。從小區(qū)間內(nèi)選擇一個代表性的二進制小數(shù)，作為實際的編碼輸出，從而達到高效編碼的目的。不論是否是二元信源，也不論數(shù)據(jù)的概率分布如何，其平均碼長均能逼近信源的熵。隨著輸入符號越來越多，子區(qū)間分割越來越精細，因此表示其左端點的數(shù)值的有效位數(shù)也越來越多。如果等整個符號序列輸入完畢后再將最終得到的左端點輸出，將遇到兩個問題：第一，當符號序列很長時，將不能實時編解碼；第二，有效位太長的數(shù)難以表示。

為了解決這個問題，通常采用兩個有限精度的移位寄存器存放碼字的最新部分，隨著序列中符號的不斷輸入，不斷地將其中的高位移出到信道上，以實現(xiàn)實時編解碼。

3.算術編碼例題例１：設信源符號表｛a1,a2,a3,a4｝，其各符號出現(xiàn)的概率分別是｛0.2,0.1,0.4,0.3｝，試按照符號序列a2a1a4a3,為其信源進行算術編碼。解：教材P63算術編碼的步驟

算數(shù)編碼是從整個符號序列出發(fā)，采用遞推式連續(xù)編碼的方法。算數(shù)編碼的原理是將一個算數(shù)碼字賦給整個信源符號序列，而碼字是在0和1之間的一個實數(shù)區(qū)間。解碼時，根據(jù)該區(qū)間判斷信源各個符號出現(xiàn)的順序和類型。算數(shù)編碼的主要步驟為：（1）首先定義算法空間為［０１）。（2）確定各個字符的區(qū)間分配。（3）對輸入的每個信源符號s，重復如下步驟：算術碼編碼步驟①將該信源符號s出現(xiàn)的概率空間擴展為新的算法子空間，將當前區(qū)間分割為長度正比于信源集內(nèi)各個符號概率的區(qū)間。②確定新算法子空間的左端為：前子區(qū)間左端+前子區(qū)間左端×當前子區(qū)間長度；③確定新子區(qū)間的寬度為：當前子區(qū)間寬度×pi（第i個被編碼符號的概率）。解碼過程是對按照當前的編碼進行識別的過程。當?shù)玫揭粋€圖像的編碼后，根據(jù)其各個信源符號的概率進行分析，找到當前編碼所符合的概率空間，逐步求精，即可得到原始符號序列信息。4、

算術編碼的效率算術編碼的最大優(yōu)點之一在于它具有自適應性和高編碼效率。算術編碼的模式選擇直接影響編碼效率。其模式有固定模式和自適應模式兩種。固定模式是基于概率分布模型的，而在自適應模式中，其各符號的初始概率都相同，但隨著符號順序的出現(xiàn)而改變，在無法進行信源概率模型統(tǒng)計的條件下，非常適于使用自適應模式的算術編碼。在信道符號概率比較均勻的情況下，算術編碼的編碼效率高于Huffman編碼。但在實現(xiàn)上，比Huffman編碼的計算過程復雜。算術碼也是變長碼，編碼過程中的移位和輸出都不均勻，也需要有緩沖存儲器。在誤差擴散方面，也比分組碼更嚴重。在分組碼中，由于誤碼而破壞分組，過一段時間后常能自動恢復；但在算術碼中，卻往往會一直延續(xù)下去，因為它是從全序列出發(fā)來編碼的。因而算術碼流的傳輸也要求高質(zhì)量的信道，或采用檢錯反饋重發(fā)的方式。§2.2.4預測編碼1、基本思想——通過對每個像素新增的信息進行提取和編碼，來消除在空間上較為接近像素之間的冗余信息：圖像相鄰像素間存在很強的相關性，通過觀察其相鄰像素取值，可以預測一個像素的大概情況；一個像素的新增信息被定義為此像素實際值和預測值之間的差異；預測誤差的方差必然比原圖像像素的方差小，因此對預測誤差進行編碼必然壓縮其平均碼長。2.2.4補充：圖像的統(tǒng)計特性1.圖像的空間域統(tǒng)計特性按照隨機過程理論，圖像可以看作是一個隨機場，也具有相應的隨機特性.在空間域中，數(shù)字圖像表現(xiàn)為空間上分布的點陣，其統(tǒng)計特性主要用體現(xiàn)像素取值的概率分布函數(shù)和標志像素間關系的相關函數(shù)或條件概率來表示。

灰度圖像的直方圖僅用直方圖不能完整地描述一幅圖像，因為一幅圖像對應一個直方圖，但一個直方圖不一定對應一幅圖像，幾幅圖像只要灰度分配密度相同，它們的直方圖是相同的。圖

幾個具有相同直方圖的圖像實例盡管直方圖不能表示出某灰度級的像素在什么位置，更不能直接反映出圖像內(nèi)容，但是具有統(tǒng)計特性的直方圖卻能描述該圖像的灰度分布特性，并能夠得到一些反映圖像特點的有用特征，作為圖像處理方法的重要依據(jù)。

2.圖像的頻率域統(tǒng)計特性在頻率域上，圖像表現(xiàn)為不同頻率分量系數(shù)的分布。按照空間域和頻率域的對應關系，空間域中的強相關性，即圖像存在大量的平坦區(qū)域，反映在頻率域中，就是圖像的能量集中于低頻部分，其傅立葉頻譜集中在直流附近，這就是說，圖像在頻率域中呈現(xiàn)低通特性。圖

電視信號的功率譜對電視信號大量測量的統(tǒng)計平均結(jié)果表明，電視信號的大部分能量集中在直流和低頻部分，具有類似于低通的特性。

3.圖像差值信號的統(tǒng)計特性

相鄰像素差值信號如果將圖像中相鄰的兩個像素相減，所得差值的概率分布集中在0附近，如圖2-22所示。圖2-22像素差值概率分布示意圖由圖看出，差值信號絕對值較小者所對應的概率大，且差值為零所對應的概率最大。所得差值的概率分布集中在0附近。對水平差值和垂直差值均有類似的特性。§2.2.4預測編碼設有一幅8×8圖像，其灰度級分布見圖所示§2.2.4預測編碼2、無損預測基本組成預測器的設計是重點§2.2.4預測編碼一般生成方法——由前m個像素線性組合生成3、預測器設計一維線性預測編碼——僅是當前行上前幾個像素的函數(shù)；§2.2.4預測編碼

二維預測——從左到右從上到下掃描圖像前幾個像素函數(shù)；

三維預測——以這些像素和前面幾幀像素為基礎。

圖4-4一階預測編碼器和解碼器框圖§2.2.4預測編碼例：預測編碼利用一階線性預測器對圖像進行編碼（前像素預測器）得到預測誤差圖像α=1>>im0=imread('D:\ProgramFiles\MATLAB\R2008a\work\images\barbara.png');>>im0=double(im0);>>[m,n]=size(im0);>>im1=zeros(m,n);>>im1(:,2:n)=im0(:,1:n-1);>>en=im0-im1;>>subplot(131);imshow(im0,[]);>>subplot(132);imshow(im1,[]);>>subplot(133);imshow(en,[]);§2.2.4預測編碼

預測誤差的熵的一階估計小于對應原圖的一階估計；反映通過預測編碼消除了大量像素間冗余?！?.2.4預測編碼4、有損預測基本組成——差分脈沖編碼調(diào)制（DPCM）§2.2.4預測編碼尋找使預測器的均方預測誤差為最小的線性預測器；5、最佳預測器——差分脈沖編碼調(diào)制（DPCM）限制條件為：§2.2.4預測編碼

選擇m個預測系數(shù)，這些系數(shù)使上式最??；對上式求導，令導數(shù)為零求解αi；要求預測