游程編碼課程設(shè)計(jì)說明書

******************實(shí)踐教學(xué)*******************蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院2014年春季學(xué)期通信系統(tǒng)仿真訓(xùn)練題目：基于游程編碼的信源編/解碼系統(tǒng)設(shè)計(jì)及仿真專業(yè)班級(jí)：通信2011級(jí)3班姓名：黃亮學(xué)號(hào)：11250309指導(dǎo)教師：晏燕成績(jī)：目錄TOC\o"1-2"\h\u4253摘要 摘要本課題主要是針對(duì)于游程編碼信源編解碼的數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)，游程編碼非常簡(jiǎn)單，編碼、解碼速度快，應(yīng)用廣泛。游程編碼是針對(duì)于二元序列的一種編碼方法，對(duì)于二值圖像而言是一種具有高壓縮比的無損數(shù)據(jù)壓縮技術(shù)，它是應(yīng)用游程編碼的原理對(duì)二值圖像進(jìn)行數(shù)據(jù)壓縮的編碼技術(shù)，對(duì)連續(xù)的黑、白像素?cái)?shù)(游程)以不同的碼字進(jìn)行編碼。游程編碼是一種簡(jiǎn)單的非破壞性資料壓縮法，其好處是加壓縮和解壓縮都非?？欤浞椒ㄊ怯?jì)算連續(xù)出現(xiàn)的資料長(zhǎng)度壓縮之，其缺點(diǎn)是對(duì)于不重復(fù)的資料反而加大容量且需大量的緩沖和優(yōu)質(zhì)信道來實(shí)現(xiàn)。游程編碼在MATLAB中的實(shí)現(xiàn)主要體現(xiàn)在對(duì)二值圖像的壓縮上，一張二值圖像其實(shí)就是兩個(gè)灰度值所組成的一個(gè)圖像矩陣，而設(shè)計(jì)程序首先就要考慮到遍歷圖像所有的灰度值，并按照游程的原理，即（灰度值，游程寬度）的形式依次記錄。由于純粹的二值圖較少的原因，可以先將灰度圖轉(zhuǎn)換為二值圖進(jìn)行壓縮，在設(shè)計(jì)的過程中，壓縮矩陣的初始化與終止位置是尤為重要的，即游程寬度在編碼之前是置為1的（其中也有MATLAB的下標(biāo)不同于其他高級(jí)語言是從0開始的原因），并且在游程寬度初始化時(shí)，也要將此矩陣中第一個(gè)灰度值給相應(yīng)的數(shù)組向量。在壓縮過程中，只需要不斷將游程寬度與灰度值所在的數(shù)組向量累加就行，而到了將截止時(shí)，應(yīng)該將最后一個(gè)灰度值手動(dòng)賦給灰度值的數(shù)組向量中，這是因?yàn)樵谘h(huán)體中不能出現(xiàn)超出下標(biāo)值的值，所以循環(huán)次數(shù)一般定為圖像矩陣的像素?cái)?shù)-1，這樣循環(huán)截止時(shí)還剩下最后一個(gè)灰度值沒有被循環(huán)體被遍歷上，因而需要手動(dòng)將之添加進(jìn)去。為了反映游程編碼后的成效，可以繪制一個(gè)以游程序列為橫軸，游程寬度為豎軸的函數(shù)圖像，從此圖像中也可以看出一幅二值圖中哪些地方的灰度值較為集中。而解壓縮，其實(shí)就是一個(gè)壓縮的逆過程，同樣地也要注意遺漏的問題。本文首先簡(jiǎn)要介紹了信源編碼的原理，然后重點(diǎn)介紹游程編碼的原理和實(shí)現(xiàn)技術(shù)，對(duì)游程編碼技術(shù)做了較為全面的研究。包括游程壓縮過程、數(shù)據(jù)壓縮、解壓縮過程，并給出了相應(yīng)的二值圖像游程編碼MATLAB仿真程序，一般字符進(jìn)行游程壓縮的MATLAB仿真程序以及附錄了一段壓縮灰度圖像的仿真程序以用來對(duì)比驗(yàn)證。關(guān)鍵字：信源編碼壓縮游程編碼MATLAB

1.信源編碼1.1信源編碼簡(jiǎn)介編碼實(shí)質(zhì)上就是對(duì)信源的原始符號(hào)按一定規(guī)則進(jìn)行的一種變換。編碼可分為信源編碼和信道編碼。由于信源符號(hào)之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。具體的說就是針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找一定的方法把信源輸出符號(hào)序列變換為最短碼字序列的方法。信源編碼的基本途徑有兩個(gè)：使序列中的各個(gè)符號(hào)盡可能地相互獨(dú)立，即解除相關(guān)性；使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。即同樣多的信息用較少的碼率傳送,使單位時(shí)間內(nèi)傳送的平均信息量增加,從而提高通信的有效性。為了減少信源輸出符號(hào)序列中的剩余度、提高符號(hào)的平均信息量，對(duì)所施行的變換。具體說，就是針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性來尋找某種方法，把信源輸出符號(hào)序列變換為最短的碼字序列，使后者的各碼元所載荷的平均信息量最大，同時(shí)又能保證無失真地恢復(fù)原來的符號(hào)序列。既然信源編碼的基本目的是提高碼字序列中碼元的平均信息量，那么，一切旨在減少剩余度而對(duì)信源輸出符號(hào)序列所施行的變換或處理，都可以在這種意義下歸入信源編碼的范疇，例如過濾、預(yù)測(cè)、域變換和數(shù)據(jù)壓縮等。當(dāng)然，這些都是廣義的信源編碼。一般來說，減少信源輸出符號(hào)序列中的剩余度、提高符號(hào)平均信息量的基本途徑有兩個(gè)： ①使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立；②使序列中各個(gè)符號(hào)的出現(xiàn)概率盡可能地相等。前者稱為解除相關(guān)性，后者稱為概率均勻化。信源編碼的一般問題可以表述如下：若某信源的輸出為長(zhǎng)度等于M的符號(hào)序列集合式中符號(hào)A為信源符號(hào)表，它包含著K個(gè)不同的符號(hào)，A={ɑk|k=1,…,K}，這個(gè)信源至多可以輸出KM個(gè)不同的符號(hào)序列。記‖U‖=KM。所謂對(duì)這個(gè)信源的輸出進(jìn)行編碼，就是用一個(gè)新的符號(hào)表B的符號(hào)序列集合V來表示信源輸出的符號(hào)序列集合U。若V的各個(gè)序列的長(zhǎng)度等于N，即式中新的符號(hào)表B共含L個(gè)符號(hào)，B={bl|l=1,…,L}。它總共可以編出LN個(gè)不同的碼字。類似地,記‖V‖=LN。為了使信源的每個(gè)輸出符號(hào)序列都能分配到一個(gè)獨(dú)特的碼字與之對(duì)應(yīng)，至少應(yīng)滿足關(guān)系‖V‖=LN≥‖U‖=KM或者N/M≥logK/logL。假若編碼符號(hào)表B的符號(hào)數(shù)L與信源符號(hào)表A的符號(hào)數(shù)K相等，則編碼后的碼字序列的長(zhǎng)度N必須大于或等于信源輸出符號(hào)序列的長(zhǎng)度M；反之，若有N=M，則必須有L≥K。只有滿足這些條件，才能保證無差錯(cuò)地還原出原來的信源輸出符號(hào)序列(稱為碼字的唯一可譯性)?？墒?，在這些條件下，碼字序列的每個(gè)碼元所載荷的平均信息量不但不能高于，反而會(huì)低于信源輸出序列的每個(gè)符號(hào)所載荷的平均信息量。這與編碼的基本目標(biāo)是直接相矛盾的。下面的幾個(gè)編碼定理，提供了解決這個(gè)矛盾的方法。它們既能改善信息載荷效率，又能保證碼字唯一可譯。1.2信源編碼的理論基礎(chǔ)信源編碼理論是信息論的一個(gè)重要分支,其理論基礎(chǔ)是信源編碼的兩個(gè)定理。無失真信源編碼定理：是離散信源/數(shù)字信號(hào)編碼的基礎(chǔ)；將信源消息分成若干組，即符號(hào)序列Xi,Xi=(X1,X2…Xl…XL),序列的每個(gè)符號(hào)取自符號(hào)集A，Xl∈{a1,a2,?,ai,?an}。而每個(gè)符號(hào)序列Xi依照固定的碼表映射成一個(gè)碼字Yi，這樣的碼稱為分組碼，有時(shí)也叫塊碼。只有分組碼才有對(duì)應(yīng)的碼表，而非分組碼中則不存在碼表。如圖2-1所示的信源編碼器，如果信源輸出的符號(hào)序列長(zhǎng)度為1，即信源符號(hào)集源概率空間為一元信道是常用的一種信道，他的信道基本符號(hào)集為{0，1}。若將信源X通過一個(gè)二元信道傳輸，就必須把信源符號(hào)xi變成符號(hào)組成的碼字序列，即編碼?？捎貌煌拇a字符號(hào)序列，如表1.2.1所示。表1.2.1信源符號(hào)Xi信源符號(hào)出現(xiàn)概率p(xi)碼表信源符號(hào)Xi信源符號(hào)出現(xiàn)概率p(xi)碼表碼1碼2碼1碼2X1P(X1)000X3P(X3)10001X2P(X2)0101X4P(X4)11111一般情況下，碼可分為兩類：一類是固定長(zhǎng)度的碼，碼中所有碼字長(zhǎng)度都相同，如表1.2.1中的碼就是定長(zhǎng)碼。另一類是可變碼，碼中的碼字長(zhǎng)短不一，如表中碼2就變長(zhǎng)碼。限失真信源編碼定理：是連續(xù)信源/模擬信號(hào)編碼的基礎(chǔ)。信息率失真函數(shù)R(D)是滿足保真度準(zhǔn)則R(D)時(shí)所必須具有的最小信息率，在進(jìn)行信源壓縮之類的處理時(shí)，R(D)就成為一個(gè)界限，不能讓實(shí)際的信息率低于R(D)。把相關(guān)的結(jié)論用定理的形式給出，即限失真信源編碼定理，也就是通常所說的香農(nóng)第三編碼定理。定義：設(shè)離散無記憶平穩(wěn)信源的信息率失真函數(shù)為R(D)，只要滿足R<R(D)，當(dāng)信源系列長(zhǎng)度L足夠長(zhǎng)時(shí)，一定存在一種編碼方法，其譯碼失真小于或等于D+ε，其中ε是任意小的正數(shù)；反過來，若R<R(D)，則無論采用什么樣的編碼方法，其譯碼失真必大于D。該定理包含兩部分：R>R(D)的情形稱為正定理，R<R(D)的情形稱為逆定理。該定理是對(duì)離散無記憶信源給出的，對(duì)于連續(xù)無記憶平穩(wěn)信源有類似結(jié)論。另外，該定理與香農(nóng)第二編碼定理（即信道編碼定理）一樣，只是碼的存在性定理。正定理告訴我們，R>R(D)時(shí)，譯碼失真小于或等于D+ε的碼肯定存在，但定理本身并未告知碼的具體構(gòu)造方法。一般來說，要找到滿足條件的碼，只能用優(yōu)化的思路去尋求，迄今為止，尚無合適的系統(tǒng)編碼方法來接近香農(nóng)給出的界R(D)。反定理告訴我們，R<R(D)時(shí)，譯碼失真必大于D，肯定找不到滿足條件的碼，因此用不著浪費(fèi)時(shí)間和精力。在實(shí)際應(yīng)用中，該定理主要存在以下兩大類問題：第一，符合實(shí)際信源的R(D)函數(shù)計(jì)算相當(dāng)困難。首先：對(duì)信源的統(tǒng)計(jì)特性要有確切的數(shù)學(xué)描述。其次：失真測(cè)度要符合主關(guān)實(shí)際，例如可以采用方差來表示平均失真度，但是對(duì)于圖像編碼來說，均方差小的方法，人們視覺感到失真較大。所以，人們采用主觀觀察來評(píng)價(jià)編碼方法的好壞。所以，這點(diǎn)是比較困難。第二，即便求得了符合實(shí)際的信息率失真函數(shù)，還需要研究采用何種實(shí)用的最佳編碼才能達(dá)到R(D)。第三：即便前兩條得到滿足，但是R(D)函數(shù)計(jì)算還是相當(dāng)困難（數(shù)學(xué)）?？偨Y(jié)起來，香農(nóng)信息論的三個(gè)基本概念——信源熵、信道容量和信息率失真函數(shù)，都是臨界值，是從理論上衡量通信能否滿足要求的重要界限。對(duì)應(yīng)這三個(gè)基本概念的是香農(nóng)的三個(gè)基本編碼定理——無失真信源編碼定理、信道編碼定理和限失真信源編碼定理，分別又稱為香農(nóng)第一、第二和第三編碼定理，或第一、第二、第三極限定理。這是三個(gè)理想編碼的存在性定理。信源編碼的基礎(chǔ)是信息論中的兩個(gè)編碼定理：無失真編碼定理和限失真編碼定理。前者是可逆編碼的基礎(chǔ)?？赡媸侵府?dāng)信源轉(zhuǎn)換成代碼后，可以從代碼無失真地恢復(fù)原信源符號(hào)。無失真編碼或可逆編碼只適用于離散信源。信源編碼定理出現(xiàn)后，編碼方法就趨于合理化。本章討論離散信源無失真編碼，從無失真編碼定理出發(fā)，重點(diǎn)討論以香農(nóng)碼，費(fèi)諾碼，哈夫曼碼和算術(shù)碼為代表的最佳碼。

1.3信源編碼的分類及作用信源編碼的分類：離散信源編碼：獨(dú)立信源編碼,可做到無失真編碼；連續(xù)信源編碼：獨(dú)立信源編碼,只能做到限失真信源編碼；相關(guān)信源編碼：非獨(dú)立信源編碼。編碼的作用：信源編碼的作用之一是設(shè)法減少碼元數(shù)目和降低碼元速率，即通常所說的數(shù)據(jù)壓縮：作用之二是將信源的模擬信號(hào)轉(zhuǎn)化成數(shù)字信號(hào)，以實(shí)現(xiàn)模擬信號(hào)的數(shù)字化傳輸。常見的信源編碼方式：霍夫曼編碼霍夫曼編碼（HuffmanCoding）是一種編碼方式，是一種用于無損數(shù)據(jù)壓縮的熵編碼（權(quán)編碼）算法。也稱“哈夫曼編碼”，“赫夫曼編碼”。1952年，DavidA.Huffman在麻省理工攻讀博士時(shí)所發(fā)明的，并發(fā)表于《一種構(gòu)建極小多余編碼的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）一文。在計(jì)算機(jī)數(shù)據(jù)處理中，霍夫曼編碼使用變長(zhǎng)編碼表對(duì)源符號(hào)（如文件中的一個(gè)字母）進(jìn)行編碼，其中變長(zhǎng)編碼表是通過一種評(píng)估來源符號(hào)出現(xiàn)機(jī)率的方法得到的，出現(xiàn)機(jī)率高的字母使用較短的編碼，反之出現(xiàn)機(jī)率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均長(zhǎng)度、期望值降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的。例如，在英文中，e的出現(xiàn)機(jī)率最高，而z的出現(xiàn)概率則最低。當(dāng)利用霍夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)，e極有可能用一個(gè)比特來表示，而z則可能花去25個(gè)比特（不是26）。用普通的表示方法時(shí)，每個(gè)英文字母均占用一個(gè)字節(jié)（byte），即8個(gè)比特。二者相比，e使用了一般編碼的1/8的長(zhǎng)度，z則使用了3倍多。倘若我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無損壓縮的比例?；舴蚵鼧溆址Q最優(yōu)二叉樹，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹。所謂樹的帶權(quán)路徑長(zhǎng)度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)）。樹的路徑長(zhǎng)度是從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和，記為WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個(gè)權(quán)值Wi（i=1,2,...n）構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i（i=1,2,...n）?？梢宰C明霍夫曼樹的WPL是最小的。算術(shù)編碼算術(shù)編碼是一種無損數(shù)據(jù)壓縮方法，也是一種熵編碼的方法。和其它熵編碼方法不同的地方在于，其他的熵編碼方法通常是把輸入的消息分區(qū)為符號(hào)，然后對(duì)每個(gè)符號(hào)進(jìn)行編碼，而算術(shù)編碼是直接把整個(gè)輸入的消息編碼為一個(gè)數(shù)，一個(gè)滿足（0.0≤n<1.0）的小數(shù)n。在給定符號(hào)集和符號(hào)概率的情況下，算術(shù)編碼可以給出接近最優(yōu)的編碼結(jié)果。使用算術(shù)編碼的壓縮算法通常先要對(duì)輸入符號(hào)的概率進(jìn)行估計(jì)，然后再編碼。這個(gè)估計(jì)越準(zhǔn)，編碼結(jié)果就越接近最優(yōu)的結(jié)果。例:對(duì)一個(gè)簡(jiǎn)單的信號(hào)源進(jìn)行觀察，得到的統(tǒng)計(jì)模型如下：60%的機(jī)會(huì)出現(xiàn)符號(hào)中性20%的機(jī)會(huì)出現(xiàn)符號(hào)陽性10%的機(jī)會(huì)出現(xiàn)符號(hào)陰性10%的機(jī)會(huì)出現(xiàn)符號(hào)數(shù)據(jù)結(jié)束符.(出現(xiàn)這個(gè)符號(hào)的意思是該信號(hào)源'內(nèi)部中止'，在進(jìn)行數(shù)據(jù)壓縮時(shí)這樣的情況是很常見的。當(dāng)?shù)谝淮我彩俏ㄒ坏囊淮慰吹竭@個(gè)符號(hào)時(shí)，解碼器就知道整個(gè)信號(hào)流都被解碼完成了。)算術(shù)編碼可以處理的例子不止是這種只有四種符號(hào)的情況，更復(fù)雜的情況也可以處理，包括高階的情況。所謂高階的情況是指當(dāng)前符號(hào)出現(xiàn)的概率受之前出現(xiàn)符號(hào)的影響，這時(shí)候之前出現(xiàn)的符號(hào)，也被稱為上下文。比如在英文文檔編碼的時(shí)候，例如，在字母Q或者q出現(xiàn)之后，字母u出現(xiàn)的概率就大大提高了。這種模型還可以進(jìn)行自適應(yīng)的變化，即在某種上下文下出現(xiàn)的概率分布的估計(jì)隨著每次這種上下文出現(xiàn)時(shí)的符號(hào)而自適應(yīng)更新，從而更加符合實(shí)際的概率分布。不管編碼器使用怎樣的模型，解碼器也必須使用同樣的模型。一個(gè)簡(jiǎn)單的例子以下用一個(gè)符號(hào)串行怎樣被編碼來作一個(gè)例子：假如有一個(gè)以A、B、C三個(gè)出現(xiàn)機(jī)會(huì)均等的符號(hào)組成的串行。若以簡(jiǎn)單的分組編碼會(huì)十分浪費(fèi)地用2bits來表示一個(gè)符號(hào)：其中一個(gè)符號(hào)是可以不用傳的（下面可以見到符號(hào)B正是如此）。為此，這個(gè)串行可以三進(jìn)制的0和2之間的有理數(shù)表示，而且每位數(shù)表示一個(gè)符號(hào)。例如，“ABBCAB”這個(gè)串行可以變成0.011201（base3，即0為A,1為B,2為C）。用一個(gè)定點(diǎn)二進(jìn)制數(shù)字去對(duì)這個(gè)數(shù)編碼使之在恢復(fù)符號(hào)表示時(shí)有足夠的精度，譬如0.001011001(base2)–只用了9個(gè)bit，比起簡(jiǎn)單的分組編碼少（1–9/12）x100%=25%。這對(duì)于長(zhǎng)串行是可行的因?yàn)橛懈咝У?、適當(dāng)?shù)乃惴ㄈゾ_地轉(zhuǎn)換任意進(jìn)制的數(shù)字。編碼過程的每一步，除了最后一步，都是相同的。編碼器通常需要考慮下面三種數(shù)據(jù)：下一個(gè)要編碼的符號(hào)當(dāng)前的區(qū)間（在編第一個(gè)符號(hào)之前，這個(gè)區(qū)間是[0,1）,但是之后每次編碼區(qū)間都會(huì)變化)模型中在這一步可能出現(xiàn)的各個(gè)符號(hào)的概率分布（像前面提到的一樣，高階或者自適應(yīng)的模型中，每一步的概率并不必須一樣）編碼器將當(dāng)前的區(qū)間分成若干子區(qū)間，每個(gè)子區(qū)間的長(zhǎng)度與當(dāng)前上下文下可能出現(xiàn)的對(duì)應(yīng)符號(hào)的概率成正比。當(dāng)前要編碼的符號(hào)對(duì)應(yīng)的子區(qū)間成為在下一步編碼中的初始區(qū)間。游程編碼游程編碼（RLE，run-lengthencoding），又譯行程長(zhǎng)度編碼，又稱變動(dòng)長(zhǎng)度編碼法（runcoding），在控制論中對(duì)于二值圖像而言是一種編碼方法，對(duì)連續(xù)的黑、白像素?cái)?shù)（游程）以不同的碼字進(jìn)行編碼。游程編碼是一種簡(jiǎn)單的非破壞性資料壓縮法，其好處是加壓縮和解壓縮都非?？?。其方法是計(jì)算連續(xù)出現(xiàn)的資料長(zhǎng)度壓縮之，其缺點(diǎn)是對(duì)于不重復(fù)的資料反而加大容量。后文有比較詳細(xì)的介紹，這里不再贅述。1.4信源編碼的歷史最原始的信源編碼就是莫爾斯電碼，另外還有ASCII碼和電報(bào)碼都是信源編碼。但現(xiàn)代通信應(yīng)用中常見的信源編碼方式有：Huffman編碼、算術(shù)編碼、L-Z編碼，這三種都是無損編碼，另外還有一些有損的編碼方式。信源編碼的目標(biāo)就是使信源減少冗余，更加有效、經(jīng)濟(jì)地傳輸，最常見的應(yīng)用形式就是壓縮。另外，在數(shù)字電視領(lǐng)域，信源編碼包括通用的MPEG—2編碼和H.264（MPEG—Part10AVC）編碼等相應(yīng)地，信道編碼是為了對(duì)抗信道中的噪音和衰減，通過增加冗余，如校驗(yàn)碼等，來提高抗干擾能力以及糾錯(cuò)能力。

2.游程編碼2.1游程長(zhǎng)度游程長(zhǎng)度RL(Run-Length)，簡(jiǎn)稱游程或游長(zhǎng)，指的是由字符(或信號(hào)取樣值)構(gòu)成的數(shù)據(jù)流中各個(gè)字符重復(fù)出現(xiàn)而形成的字符的長(zhǎng)度。如果給出了形成串的字符，串的長(zhǎng)度以及串的位置，就能恢復(fù)出原來的數(shù)據(jù)流，游程長(zhǎng)度編碼(RLC)就是用二進(jìn)制碼字給出這些信息的一類方法。2.2游程編碼算法游程編碼的基本原理是：用一個(gè)符號(hào)值或串長(zhǎng)代替具有相同值的連續(xù)符號(hào)（連續(xù)符號(hào)構(gòu)成了一段連續(xù)的“游程”，游程編碼因此而得名），使符號(hào)長(zhǎng)度少于原始數(shù)據(jù)的長(zhǎng)度。只在各行或者各列數(shù)據(jù)的代碼發(fā)生變化時(shí)，一次記錄該代碼及相同代碼重復(fù)的個(gè)數(shù)，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。在二元序列中，只有兩種符號(hào)，即“0”和“1”，這些符號(hào)可連續(xù)出現(xiàn)，連“0”這一段稱為“0”游程，連“1”這一段稱為“1”游程。它們的長(zhǎng)度分別稱為游程長(zhǎng)度L(0)和L(l)?！?”游程和“l(fā)”游程總是交替出現(xiàn)的。如果規(guī)定二元序列是以“0”開始，第一個(gè)游程是“0”游程，第二個(gè)必為“1”游程，第三個(gè)又是“0”游程等等。對(duì)于隨機(jī)的二元序列，各游程長(zhǎng)度將是隨機(jī)變量，其取值可為1，2，3，?，直到無限。將任何(二元)序列變換成一一對(duì)應(yīng)的游程長(zhǎng)度序列，再按哈夫曼編碼或其他方法處理以達(dá)到壓縮碼率的目的。游程長(zhǎng)度編碼的主要思想是將一個(gè)相同值的連續(xù)申用其值和申長(zhǎng)(重復(fù)的個(gè)數(shù))的數(shù)對(duì)二元組來替代．例如，在圖像編碼中，可以定義沿特定方向上具有相同灰度值的相鄰像素為一輪，其延續(xù)的長(zhǎng)度稱之為延續(xù)的行程，即游程．游程終點(diǎn)位置由前一游程終點(diǎn)的相對(duì)距離確定，這樣就可以由灰度游程串來表示圖像數(shù)據(jù)．例如，若沿水平方向有一串M個(gè)像素具有相同的灰度N，則按游程長(zhǎng)度編碼后，只傳遞兩個(gè)值(N，M)就可以代替這M個(gè)像素的M個(gè)灰度值NJ簡(jiǎn)單來說，游程長(zhǎng)度編碼的主要任務(wù)是統(tǒng)計(jì)連續(xù)相同字符的個(gè)數(shù)，解碼時(shí)要根據(jù)字符及連續(xù)相同字符的個(gè)數(shù)，恢復(fù)原來的數(shù)據(jù)。游程編碼記錄方式有兩種：①逐行記錄每個(gè)游程的終點(diǎn)列號(hào)：②逐行記錄每個(gè)游程的長(zhǎng)度（像元數(shù)）。如有柵格圖形如下：AAABBACCCA第一種方式記為：A,3，B,5A,1，C,4，A,5第二種就記作：A,3，B,2A,1，C,3，A,12.3游程編碼特點(diǎn)游程編碼仍是變長(zhǎng)碼，有其固有的缺點(diǎn)，及需要大量的緩沖和優(yōu)質(zhì)的信道。此外，編程長(zhǎng)度可以從一直到無限，這在碼字的選擇和碼表的建立方面都有困難，實(shí)際應(yīng)用是尚需采用某些措施來改進(jìn)。一般情況下游程長(zhǎng)度越長(zhǎng)，其概率越小，這在以前的計(jì)算中也可以看見，而且將隨著長(zhǎng)度的增大漸進(jìn)向零。對(duì)于小概率的碼字，其長(zhǎng)度為達(dá)到概率匹配或較長(zhǎng)，損失不會(huì)太大，也就是對(duì)平均碼字長(zhǎng)度影響較小。再按哈夫曼編碼或其他方法處理以達(dá)到壓縮碼率的目的。游程長(zhǎng)度編碼在游程加密時(shí)，數(shù)據(jù)量沒有明顯增加，壓縮效率較高，且易于檢索，疊加合并等操作，運(yùn)算簡(jiǎn)單，適用于機(jī)器存貯容量小，數(shù)據(jù)需大量壓縮，而又要避免復(fù)雜的編碼解碼運(yùn)算增加處理和操作時(shí)間的情況。2.4游程編碼算法示例例如：5555557777733322221111111行程編碼為：（5，6）（7，5）（3，3）（2，4）（1，7）?？梢?，行程編碼的位數(shù)遠(yuǎn)遠(yuǎn)少于原始字符串的位數(shù)。例如有一張圖片，以W表示白色，B表示黑色：WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW使用這個(gè)壓縮法便可得到12W1B12W3B24W1B14W更先進(jìn)的算法如DEFLATE都是基于將重復(fù)出現(xiàn)的資料“壓縮”的想法。常見的游程編碼格式包括TGA，Packbits，PCX以及ILBM。游程長(zhǎng)度編碼是一種無損數(shù)據(jù)壓縮，非常適合基于調(diào)色板的圖標(biāo)圖像。但是它并不適用于連續(xù)色調(diào)圖像的壓縮，例如日常生活中的照片；JPEG格式是一個(gè)反例，JPEG在對(duì)圖像進(jìn)行轉(zhuǎn)換和離散化后有效地使用了游程長(zhǎng)度壓縮。游程長(zhǎng)度編碼還用于傳真機(jī)（并和其他技巧一起組成了修改過的huffman編碼）。相對(duì)而言，游程長(zhǎng)度編碼是比較有效的，因?yàn)閭髡娴奈臋n主要是黑白的（二值文檔）。

3.基于游程編碼的信源編/解碼的MATLAB仿真設(shè)計(jì)3.1壓縮前的準(zhǔn)備在壓縮之前，須將圖像轉(zhuǎn)換為灰度圖，此程序作用即將輸入路徑的三維彩色RGB圖像轉(zhuǎn)換為二維的灰度圖像。path=input('請(qǐng)輸入要轉(zhuǎn)換的圖像路徑\n','s');image1=imread(path);%讀入圖像[M,N]=size(image1)%計(jì)算圖像行列大小figure,imshow(image1);title('原圖像');image2=rgb2gray(image1);%轉(zhuǎn)換為灰度圖像[M,N]=size(image2)figure,imshow(image2);title('灰度圖');path1=input('請(qǐng)輸入要存儲(chǔ)的圖像路徑\n','s');imwrite(image2,path1);%存為灰度圖像效果如下：圖3.1彩色圖轉(zhuǎn)換為灰度圖本程序運(yùn)行之后，要在MATLAB命令窗口中輸入將要轉(zhuǎn)換的圖像路徑，這里我的彩色圖像在“D:\tu3.jpg”，讀取圖像后可得出當(dāng)前圖像的矩陣行列大小為154*615，利用rgb2gray函數(shù)可以將當(dāng)前彩色圖像轉(zhuǎn)換為灰度圖像，為了方便之后的壓縮，此處將轉(zhuǎn)換后的圖像用imwrite命令將之存儲(chǔ)在“D:\tu31.jpg”，并能顯示轉(zhuǎn)換后的圖像行列大小為154*205，可以知道，轉(zhuǎn)換后的圖像比之原圖像縮小了3倍，這正是因?yàn)椴噬珗D像一個(gè)像素點(diǎn)由RGB三個(gè)灰度值描述，而灰度圖像一個(gè)像素點(diǎn)只由一個(gè)灰度值表示，因而彩色圖像經(jīng)轉(zhuǎn)換后會(huì)變?yōu)橹挥泻诎壮潭炔煌膱D像，這就達(dá)到了為下一步轉(zhuǎn)換為二值圖像的前提條件，即圖像矩陣中一個(gè)元素表示一個(gè)像素的灰度值。3.2進(jìn)行游程編碼讀取灰度圖像路徑，先轉(zhuǎn)換為二值圖然后進(jìn)行游程編碼，得出壓縮率。(也可將轉(zhuǎn)換二值圖的程序單列出來)path=input('請(qǐng)輸入要讀取的灰度圖像路徑\n','s');image1=imread(path);%讀入圖像[M,N]=size(image1);%計(jì)算圖像行列大小figure,subplot(211);imshow(image1);%顯示原圖像title('原圖像');IM1=image1(:);%將圖像轉(zhuǎn)換為一維數(shù)組IM1length=length(IM1);%計(jì)算轉(zhuǎn)換為一維數(shù)組的長(zhǎng)度fori=1:1:IM1length%for循環(huán)，目的在于轉(zhuǎn)換為二值圖像ifIM1(i)>=127%灰度值大于127轉(zhuǎn)換為255，反之為0IM1(i)=255;elseIM1(i)=0;endendimage2=reshape(IM1,M,N);%重組圖像subplot(212),imshow(image2);%顯示重組后的圖像title('手動(dòng)轉(zhuǎn)換后的二值圖像');%{level=graythresh(image1);%獲取二值圖閾值imgbw=im2bw(image1,level);%利用內(nèi)部函數(shù)轉(zhuǎn)換為二值圖subplot(222);imshow(imgbw);%顯示內(nèi)部函數(shù)轉(zhuǎn)換出的二值圖像title('內(nèi)部函數(shù)轉(zhuǎn)換的圖像');%}j=1;counter(j)=1;%游程序列碼初始化forz=1:1:(length(IM1)-1)ifIM1(z)==IM1(z+1)counter(j)=counter(j)+1;%每遇相等的灰度值，將當(dāng)前的重合度加1elsedata(j)=IM1(z);%否則，將當(dāng)前的序列碼加1j=j+1;counter(j)=1;endenddata(j)=IM1(length(IM1));%Comp=[data;counter]%查看編碼后的矩陣%{counterlength=length(counter);%編碼后的序列長(zhǎng)度s=1:1:counterlength;figure,plot3(s,counter(s),data(s));%編碼后的序列函數(shù)關(guān)系title('編碼后的序列函數(shù)關(guān)系圖（三維圖）');xlabel('游程序列碼');ylabel('像素重合度');zlabel('灰度值');gridon;%}counterlength=length(counter);%編碼后的序列長(zhǎng)度s=1:1:counterlength;figure,plot(s,counter(s));title('壓縮后的序列函數(shù)關(guān)系圖');xlabel('游程序列碼');ylabel('游程寬度');gridon;display('壓縮率');CRatio=counterlength*2/IM1length%壓縮率%還原數(shù)組k=1;form=1:1:counterlengthforn=1:1:counter(m)IM2(k)=data(m);k=k+1;endendimage3=reshape(IM2,M,N);%重組數(shù)組為二值圖figure,imshow(image3);title('解壓后的圖像');

3.3算法流程圖3.3解壓流程圖圖3.2壓縮流程圖開始將原圖像矩陣重構(gòu)為1*IM1length的列向量IM1初始化j=1，z=1IM1(z)==IM1(z+1)counter(j)++data(j)=IM1(z)j++,z++counter(j)=1輸入圖像路徑并讀取圖像輸出壓縮后矩陣Comp=[data;counter]結(jié)束否是Z=IM1length是否開始讀入counter,data初始化k=1,m=1,n=1m<counterlengthn<counter(m)IM2(k)=data(m)k++將列向量IM2重構(gòu)為原圖像結(jié)束否是圖3.3解壓流程圖圖3.2壓縮流程圖開始將原圖像矩陣重構(gòu)為1*IM1length的列向量IM1初始化j=1，z=1IM1(z)==IM1(z+1)counter(j)++data(j)=IM1(z)j++,z++counter(j)=1輸入圖像路徑并讀取圖像輸出壓縮后矩陣Comp=[data;counter]結(jié)束否是Z=IM1length是否開始讀入counter,data初始化k=1,m=1,n=1m<counterlengthn<counter(m)IM2(k)=data(m)k++將列向量IM2重構(gòu)為原圖像結(jié)束否是是否本程序?qū)⑦x擇圖像的權(quán)利交給用戶，用戶可以通過輸入圖像在計(jì)算機(jī)中的路徑去讀取將要壓縮的圖像，程序?qū)⒂脩糨斎氲穆窂劫x給path，并通過imread(path)命令讀取圖像。圖像矩陣會(huì)存儲(chǔ)在變量image1中，再通過image1(:)命令將圖像矩陣轉(zhuǎn)換為長(zhǎng)度為IM1length的列向量IM1。初始化j,z兩個(gè)變量為1，建立一維矩陣counter并初始化counter(j)，此矩陣將接收壓縮中所得的灰度值的各個(gè)游程寬度，建立一維矩陣data，此矩陣將接收壓縮中所得灰度值序列。接著遍歷整個(gè)IM1的數(shù)值，用if語句判斷IM1(z)是否與IM1(z+1)相等，即判斷相鄰灰度值是否相等，若是相等，則初始化data(j)并將此灰度值賦給data(j)，以及將counter(j)累加，如果相鄰灰度值并不相等，則使j加1，即進(jìn)入下一次游程的壓縮。當(dāng)遍歷完整個(gè)IM1數(shù)值后，就可以將data,counter合并為一個(gè)二維矩陣Comp，此矩陣即壓縮后得到的碼字。對(duì)比原圖像矩陣的長(zhǎng)度，就可以得到壓縮率CRatio。解壓流程：讀取data,counter兩個(gè)一維矩陣，初始化k，m，n為1，求得counter矩陣的長(zhǎng)度counterlength，并遍歷整個(gè)counter矩陣中的數(shù)值，可以從壓縮流程中知道counter(m)即代表各個(gè)灰度值的寬度，data(m)代表相應(yīng)的灰度值，兩相組合就能知道整個(gè)圖像矩陣的灰度序列，因而初始化一個(gè)一維矩陣IM2，并在循環(huán)體中賦值IM2(k)=data(m)，即可得到一個(gè)包含原圖像矩陣所有灰度值的矩陣IM2，將IM2用reshape(IM2,M,N)命令重組此矩陣為一個(gè)二維的矩陣，其中M,N是求得的原圖像的行列大小，這樣得出的矩陣即原圖像的二值矩陣，用imshow命令顯示出來即可對(duì)比。無論壓縮還是解壓，核心都在于循環(huán)體中遍歷數(shù)值時(shí)的賦值，將矩陣的數(shù)值打散并按照相應(yīng)的順序排列，就能得到相應(yīng)的壓縮效果。此程序也可以直接遍歷原圖像的二維矩陣，不過計(jì)算量會(huì)變大，鑒于在MATLAB中轉(zhuǎn)換一維矩陣的簡(jiǎn)單易行，完全可以將原圖像矩陣轉(zhuǎn)換為一維矩陣再進(jìn)行壓縮，這樣的效率無疑要高上許多。另外，針對(duì)二值圖像時(shí)，可以考慮只統(tǒng)計(jì)其中一個(gè)灰度值，這樣會(huì)減少壓縮過程的繁瑣，在此實(shí)例中為了原理的闡述清楚，將兩個(gè)灰度值都進(jìn)行了統(tǒng)計(jì)。游程編碼本身可以對(duì)任何數(shù)值序列進(jìn)行統(tǒng)計(jì)，不過只有對(duì)數(shù)值重復(fù)率較高的序列壓縮較理想，尤以二值圖為最，讀者可以通過附錄中的灰度圖像的游程編碼程序進(jìn)行對(duì)比。

3.4程序運(yùn)行效果及分析圖3.4灰度圖轉(zhuǎn)換為二值圖將灰度圖像轉(zhuǎn)換為二值圖像是必要的，游程編碼在灰度圖像中的應(yīng)用并不廣泛（可用附錄中的代碼進(jìn)行實(shí)驗(yàn)對(duì)比），因?yàn)榛叶戎涤?56個(gè)，導(dǎo)致其相鄰的重復(fù)灰度值并不會(huì)太緊密，特別是在一些著色較講究的灰度圖像中，灰度的變化十分細(xì)微，如本實(shí)例的原圖像，在明暗值上有相當(dāng)豐富的表現(xiàn)，即代表著此圖像矩陣相鄰數(shù)值的重復(fù)概率較小，而事實(shí)上，如果就原圖像這樣的灰度圖像用游程編碼壓縮后，得出的壓縮率在160%左右，即比原來還大了不少，自然不能稱之為壓縮了，其他灰度圖像雖說并不如本實(shí)例中的圖像明暗豐富，但也相差不多，壓縮后的大小都在原圖像之上。本程序的二值轉(zhuǎn)換是將灰度圖像矩陣中，大于127的灰度值全部重構(gòu)為255，而小于或者等于127的灰度值全部重構(gòu)為0，這樣轉(zhuǎn)換后，圖像就會(huì)變得黑白分明，整張圖像中只會(huì)存在黑白兩種顏色，圖像矩陣中也只會(huì)存在0,255兩種數(shù)值，即所謂的“二值圖”。為了后面表示函數(shù)關(guān)系的方便，這里也一并將二維的圖像矩陣轉(zhuǎn)換為一維的列向量IM1，即將圖像矩陣按列的順序組成一個(gè)新的一維矩陣。 圖3.5編碼后游程寬度關(guān)于序列的函數(shù)圖這一步驟要點(diǎn)在于實(shí)現(xiàn)壓縮，此程序中將變量IM1作為一維的列向量，并用for,if等命令將IM1中的值進(jìn)行統(tǒng)計(jì)，得出data與counter兩個(gè)新的一維矩陣，前者是代表冗余的數(shù)值，后者則表示冗余度。例如IM1=[1,1,2,3,3,3,1]，那么data=[1,2,3,1]，counter=[2,1,3,1]，而事實(shí)上IM1中只有0與255兩種數(shù)值，這就使統(tǒng)計(jì)的難度大大降低。此處可以再進(jìn)一步簡(jiǎn)化，只將0或者255其中一個(gè)值的冗余度求得，另一個(gè)值的冗余度自然就可得出，不過出于兩種數(shù)值都表現(xiàn)出來較為全面明了的考慮，這里是將兩者做了統(tǒng)計(jì)，最后的壓縮率高達(dá)5.19%，這種高壓縮率正好說明了游程編碼在二值圖中強(qiáng)大的優(yōu)勢(shì)。壓縮的原理較為簡(jiǎn)單，即先為data,counter兩個(gè)矩陣初始化，然后遍歷整個(gè)IM1即圖像矩陣的灰度值，相鄰灰度值相等，則counter累加1，并由data記錄當(dāng)前灰度值，若相鄰灰度值不同，則使counter初始化計(jì)數(shù)，data初始化其中數(shù)值，如此反復(fù)，最后就能得出data中的灰度值，與counter的冗余度。不難看出，兩上一維矩陣的長(zhǎng)度是相等的，于是壓縮率便可由此兩矩陣中的任何一個(gè)矩陣的長(zhǎng)度的2倍比上原二值圖像的大小得出。由上圖也可以看出此二值圖像最高的冗余度在140左右，這也是壓縮率高的原因。 圖3.6解壓后的二值圖 圖3.7程序中的各變量值

3.4游程編碼的簡(jiǎn)單實(shí)現(xiàn)以上是游程編碼常用的二值圖編碼壓縮，其原理是將一個(gè)數(shù)矩陣轉(zhuǎn)換為列向量并對(duì)列向量中重復(fù)的數(shù)值進(jìn)行統(tǒng)計(jì)，最后得出較為精簡(jiǎn)的數(shù)矩陣，重復(fù)的數(shù)越緊密，壓縮率也就越大。下面由手動(dòng)輸入的一組數(shù)矩陣實(shí)現(xiàn)的MATLAB仿真代碼:F=input('請(qǐng)輸入行程碼\n');j=1;counter(j)=1; %游程序列碼初始化forz=1:1:(length(F)-1)ifF(z)==F(z+1)counter(j)=counter(j)+1;%每遇相等的灰度值，將當(dāng)前的重合度加1elsedata(j)=F(z);%否則，將當(dāng)前的序列碼加1j=j+1;counter(j)=1;endenddata(j)=F(length(F));disp('編碼后的碼字');Comp=[data;counter]%輸出編碼后的行程碼disp('壓縮率')CRatio=length(Comp)*2/length(F)counterlength=length(counter);%編碼后的序列長(zhǎng)度k=1;form=1:1:counterlengthforn=1:1:counter(m)G(k)=data(m);k=k+1;endenddisp('解壓后的碼字');G現(xiàn)輸入一列向量如:[1,1,1,3,3,3,3,2,1,1,2,2,2,2,2,3,3,3,4,4,4,5,5,5,5]那么經(jīng)壓縮后應(yīng)得到：1321234534125334壓縮率為64%，可見游程編碼對(duì)重復(fù)率較高的碼字序列擁有較為優(yōu)秀的壓縮效率。

其效果如下：圖3.8簡(jiǎn)單游程編碼實(shí)例從圖中不難看出，對(duì)于一維矩陣[1,1,1,3,3,3,3,2,1,1,2,2,2,2,2,3,3,3,4,4,4,5,5,5,5]的游程編碼，統(tǒng)計(jì)其各個(gè)數(shù)值的重復(fù)度（即游程寬度），可以得出壓縮矩陣Comp為[(1,3),(3,4),(2,1),(1,2),(2,5),(3,3),(4,3),(5,4)]。得出壓縮率為64%，可見對(duì)于有著不同元素的矩陣壓縮并不高（相對(duì)于二值圖的壓縮率）。

設(shè)計(jì)總結(jié)此次課程設(shè)計(jì)是對(duì)于信源編碼中較為簡(jiǎn)單的游程編碼進(jìn)行MATLAB的仿真設(shè)計(jì)。游程編碼的原理是利用壓縮資料的重復(fù)冗余進(jìn)行簡(jiǎn)化，整個(gè)壓縮過程即一個(gè)遍歷數(shù)矩陣并統(tǒng)計(jì)重復(fù)數(shù)值將重復(fù)度與重復(fù)的數(shù)值分別存入兩個(gè)行向量中，然后將兩個(gè)行向量合為一個(gè)二維數(shù)組，即最后的壓縮矩陣的過程，對(duì)比原矩陣與壓縮矩陣的大小，即可得出壓縮率。而解壓縮過程即壓縮過程的逆運(yùn)行，即將壓縮矩陣中的元素按原圖像像素下標(biāo)值的順序排列。經(jīng)過此次課程設(shè)計(jì)，讓我理解了信源編碼的基本原理，尤其是游程編碼的原理，雖然簡(jiǎn)單，但在做MATLAB仿真設(shè)計(jì)卻遇到諸多問題，主要在于兩個(gè)方面，一是許多繪圖命令的不熟悉，顯示不出相應(yīng)效果的圖像，二是雖然明白原理，卻難以用代碼準(zhǔn)確地表達(dá)出來。一番查閱資料與熟悉命令后，才能用MATALB真正實(shí)現(xiàn)圖片或者數(shù)矩陣的壓縮?？梢娎碚撆c實(shí)踐必須同時(shí)進(jìn)行，否則只會(huì)眼高手低，不能真正解決實(shí)際問題。此次課程設(shè)計(jì)總體成功，除必要的要求外，我還另外設(shè)計(jì)了兩段壓縮灰度圖像與彩色圖像的代碼，（附錄中有壓縮灰度圖像的代碼）在以驗(yàn)證游程編碼在二值圖像中的優(yōu)勢(shì)。附錄對(duì)于灰度圖像的壓縮基于游程編碼的MATLAB實(shí)現(xiàn)：path=input('請(qǐng)輸入要讀取的灰度圖像路徑\n','s');image1=imread(path);%讀入圖像[M,N]=size(image1);