【正文】 散像素序列來表示，白紙黑字的二值文件 采用二元碼進(jìn)行編碼，即表示背景（白色）時像素為碼元“ 0 ”，表示內(nèi)容（黑字）時像素 為碼元“ 1 ”。 傳真文件中連“ 0 ”和連“ 1 ”較多，這些連“ 0 ”或連“ 1 ”的字符串稱為游程，對游 程長度進(jìn)行霍夫曼編碼或其他的編碼處理就可以達(dá)到壓縮數(shù)據(jù)的目的。 以一幅 10 50 黑白二值圖像為例，如圖 4 . 7 所示。 圖 二值圖像 第 4章 無失真信源編碼 通過觀察可以發(fā)現(xiàn)：白像素的數(shù)目比黑像素多，并且無論是黑像素還是白像素都經(jīng)常連續(xù) 的出現(xiàn)，形成一個一個的游程，這樣給我們一個啟示：即對大量出現(xiàn)的連“ 0 ”或連“ 1 ”像素 序列，在輸出時，可通過像素類別（黑或白像素）加重復(fù)次數(shù)的方式來表示，這種思路構(gòu)成的 編碼方式即稱為游程編碼（ RL C ），而重復(fù)出現(xiàn)的同類像素的長度稱為游程長度（ Run L e n g t h ）。 信源符號中重復(fù)出現(xiàn)的連“ 0 ”或“ 1 ”像素序列，通過游程編碼后，可以寫成統(tǒng)一的編碼 單元，其單元結(jié)構(gòu)如圖 4 . 8 所示： 符 號 碼 標(biāo) 識 碼 游 程 長 度 圖 游程編碼單元格式 其中：符號碼表示當(dāng)前的像素類別是“ 0 ”（白像素）或“ 1 ”（黑像素），標(biāo)識碼是一種有 別于符號碼的區(qū)分符號，如： 符號。 第 4章 無失真信源編碼 例題： 若信源的字符序列為： B B B B B B B B B B X X X X X X X X X A A A A A A UU U UU UU UU UU UU 寫出游程編碼的格式。 解： 出現(xiàn) B 的次數(shù)為 10 ，則 B 游程長度為 10 ，出現(xiàn) X 的次數(shù)為 9 ，則 X 游程長度為 9 ，出 現(xiàn) A 的次數(shù)為 6 ，則 A 游程長度為 6 ，出現(xiàn) U 的次數(shù)為 13 ，則 U 游程長度為 13 ，標(biāo)識碼采用 符 號，游程編碼的格式表達(dá)式為： B 10 X 9 A 6 U 1 3 由此看出，字符的數(shù)量由原來的 38 個減少到現(xiàn)在的 13 個?？梢姡纬叹幋a可以縮短數(shù)據(jù)， 其效率的高低取決于信源 符號的重復(fù)率，重復(fù)率越高，則壓縮效果就越好。 在實(shí)際的文件的行掃描中，由于文件的二值性，其黑、白像素序列總是交替出現(xiàn)，即黑、白 游程交替出現(xiàn)，這樣只要知道了第一個游程的類型，則隨后各個游程的類型也就可以一一確定下 來。 在實(shí)際的行掃描中，通常規(guī)定第一游程為白游程，對于第一游程為黑游程的行信號，可以通 過在黑游程前插入一個游程長度為 0 的白游程的方法，來滿足規(guī)定。 2. MH 碼 M H 編碼是一種實(shí)用的游程編碼算法，應(yīng)用于黑、白傳真數(shù)據(jù)的壓縮編碼，它也是 國際電話咨詢委員會提出的文件、傳真類一維數(shù)據(jù)壓縮編碼的國際標(biāo)準(zhǔn)。根據(jù)不同的黑、 白游程長度有兩張結(jié)尾碼表和兩張組合碼表。 M H 編碼基本的編碼規(guī)范為： ( 1 ) 游程長度在 0 ~ 6 3 時，直接查表用相應(yīng)的結(jié)尾碼作為碼字； ( 2 ) 游程長度在 6 4 ~ 1 7 2 8 范圍內(nèi)時，用組合碼加上結(jié)尾碼作為相應(yīng)的碼字； ( 3 ) 每行的第一個游程規(guī)定為白游程（長度可以為零），每行用一個結(jié)束碼（ E O L ） 終止； ( 4 ) 在傳輸時，每頁數(shù)據(jù)之前加一個結(jié)束碼，每頁尾部連續(xù)實(shí)用 6 個結(jié)束碼。 第 4章 無失真信源編碼 第 4章 無失真信源編碼 例題： 設(shè)有一頁傳真數(shù)據(jù)中某一行上的像素點(diǎn)如下分布： | ← 73 白→ | ← 7 黑→ | ← 11 白→ | ← 18 黑→ | ← 1 6 1 9 白→ | 求：（ 1 ）該行圖像的 MH 編碼； （ 2 ）編碼后該行的總比特?cái)?shù)； （ 3 ）該行的編碼壓縮率。 解： （ 1 ）根據(jù) MH 碼表可得該行圖像的 MH 碼為 : 64 白 +9 白 7 黑 1 1 白 1 8 黑 1 6 0 0 白 + 1 9 白 E O L 1 1 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 （ 2 ）編碼后該行的總比特?cái)?shù)為 58 位。 （ 3 ）該行的壓縮率為： 1 728 ： 58 ≈ 2 9 . 8 。 第 4章 無失真信源編碼 算術(shù)編碼 對于符號表很小的信源來說，只有采用較長的分組長度時才能得到較高的編碼 效率，因此需要一個有效的算法來處理較長的信源符號序列，霍夫曼編碼在這方面 做的不夠好，因?yàn)樗仨氼A(yù)先計(jì)算所有可能的信源符號序列的概率，然后才能進(jìn)行 編碼。 算術(shù)編碼依然是一種概率統(tǒng)計(jì)匹配編碼，它是建立在全部符號序列的累積概率 基礎(chǔ)之上的，并采用遞推形式來進(jìn)行連續(xù)編碼。 將積累概率（小于 1 ）映射到 [ 0 , 1 ] 區(qū)間上，使每個序列對應(yīng)于這個區(qū)間內(nèi)的一 點(diǎn)，也就是一個二進(jìn)位的小數(shù)，這些點(diǎn)把 [ 0 , 1 ] 區(qū)間分成許多小段，每段的長度等于 某一序列的概率。再在段內(nèi)取一個二進(jìn)位小數(shù)，其長度可與該序列的概率匹配，已 達(dá)到提高編碼效率的目的，這種編碼方法稱為算術(shù)編碼。 1 積累概率 先從信源符號的積累概率開始，設(shè)信源符號集為： ? ?1210 , ?? maaaaA ? 第 4章 無失真信源編碼 相應(yīng)的概率為1 , 2 , 1 , 0, ?? mrp r ?，定義各符號的積累概率為： ????10riir pP (4 1 8 ) 顯然，式 （ 4 18 ） 可得102022 ,0 ppPpPP ????等，而且存在 rrr PPp ?? ? 1 (4 1 9 ) 由于1?rP和rP都是小于 1 的正數(shù)，可用 [ 0 , 1 ] 區(qū)間內(nèi)的兩個點(diǎn)來表示，則rp就是這兩 個點(diǎn)間的小區(qū)間長度。不同的符號有不同的小區(qū)間，它們互不重疊，也就是在這種小區(qū)間 內(nèi)任一個點(diǎn)可作為該符號的代碼，最后將計(jì)算這個代碼所需的長度，使能與其概率匹配。 再來計(jì)算序列的積累概率。為了簡單起見，先以獨(dú)立二元序列為例來計(jì)算，所得結(jié)果 很容易推廣到一般情況。設(shè)有一序列0 1 1?S，這種 3 個二元符號的序列可按自然二進(jìn)制數(shù) 排列，如 0 0 0 ， 0 0 1 ， 0 1 0 ， ? ，則 S 的積累概率為： )0 1 0()0 0 1()0 0 0()( pppSP ??? 第 4章 無失真信源編碼 若 S 的后面接一個“ 0 ”，積累概率就成為： )0110()0 1 0 0()0 0 1 1()0 1 00()0 0 0 1()0 0 0 0()0( ppppppSP ?????? )()010()001()000( SPppp ???? 因?yàn)?2 個四元符號的最后一位是“ 0 ”和“ 1 ”時，根據(jù)歸一律，它們的概率和應(yīng) 該等于前 3 位的概率，即)000()0 0 0 1()0 0 0 0( ppp ??等。 若 S 的后面接一個“ 1 ”，積累概率就成為： )0 1 1 0()0110()0 1 0 0()0 0 1 1()0 1 00()0 0 0 1()0 0 0 0()1( pppppppSP ??????? )0 1 1 0()( pSP ?? 0)()( pSpSP ?? 第 4章 無失真信源編碼 由于二元序列的積累概率為010 ,0 pPP ??，所以)0( SP和)1( SP可寫成： 1 , 0,)()()( ??? rPSPSPSP rr 這個式子很容易推廣到多元序列，即可得積累概率的遞推公式為： rr PSPSPSaP )()()( ?? (4 20 ) 序列的概率公式為： rr PSPSaP )()( ? (4 21 ) 從以上關(guān)于積累概率)( SP的計(jì)算中可以看出，)( SP把區(qū)間 [ 0 , 1 ] 分割成許多小區(qū)間，每個 小區(qū)間的長度等于各序列的概率)( Sp，而這小區(qū)間內(nèi)的任一點(diǎn)可用來代表這序列?，F(xiàn)在來討論 如何選擇這一點(diǎn)。 2. 區(qū)間內(nèi)點(diǎn)的選取 令 ???????)(1lbSpL (4 22 ) 把積累概率)( SP寫成二進(jìn)制的小數(shù)，取其前L位，以后若有尾數(shù)，就進(jìn)位到第L位，這樣得 到一個數(shù)C。 例如0 1 1 0 0 0 )( ?SP，且/71)( ?Sp，則3]7lb[ ??L位，可得?C，這個C就可以作 為S的碼字。 這樣構(gòu)成的碼字，編碼效率是很高的，因?yàn)橐芽蛇_(dá)到概率匹配，尤其是當(dāng)序列很長時。對于長 序列)( Sp必然很小，也就是取整數(shù)造成的差別很小，平均代碼長度將接近于信源熵。 3. 實(shí)際編碼過程 先制定兩個存儲器，起始時一個為“ 0 ”，另一個為“ 1 ”，分別代表空集的積累概率和概率。每 輸入一個信源符號更新一次，得到)( SP值后，按前述方法得到碼字C，將其暫存起來，這個C值 也隨輸入符號而更新，直到序列結(jié)束，就可作為該序列的碼字輸出。 由于)( SP是遞增的，而這個增量隨序列的增長而減小，因?yàn)檫@個增量是序列的概率與信源符 號的積累概率的乘積，所以C的 前面幾位一般是固定的，在以后計(jì)算中不會被更新，因而可以輸出。 第 4章 無失真信源編碼 例題： 設(shè)二元獨(dú)立序列：1 1 1 1 1 1 0 0?S，已知其符號概率為4/1)0( ?p，4/3)1( ?p，求用算術(shù) 編碼進(jìn)行編碼后的碼字和效率。 解： 由上述公式和編碼規(guī)則，可得該序列的概率為： 26 )4/1()4/3()( ?Sp 選取位為： 7)(1lb ????????SpL位 積累概率為： )1 1 1 1 0 1 11()0 1 000 0 0 0()0 0 0 10 0 0 0()0 0 0 0 0 0 0 0()( ppppSP ????? ? )1 1 1 1 1 1 0 0()1 1 1 1 1 1 0 1()1 1 1 1 1 1 1 0()1 1 1 1 1 1 11(1 pppp ????? 第 4章 無失真信源編碼 按歸一律，取前 6 位得： 111 1 0 1 0 0 1 0 0 )4/3(1)1 1 1 1 1 1(1)( 6 ????? pSP 根據(jù)選取位，最后得碼字為： ?C 信源熵為：8 1 )(l o g)()( ??? ? SpSpSH 編碼效率為：%)8/7/( ??η 第 4章 無失真信源編碼