游程編碼課程設計說明書

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

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

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

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

3.基于游程編碼的信源編/解碼的MATLAB仿真設計3.1壓縮前的準備在壓縮之前，須將圖像轉換為灰度圖，此程序作用即將輸入路徑的三維彩色RGB圖像轉換為二維的灰度圖像。path=input('請輸入要轉換的圖像路徑\n','s');image1=imread(path);%讀入圖像[M,N]=size(image1)%計算圖像行列大小figure,imshow(image1);title('原圖像');image2=rgb2gray(image1);%轉換為灰度圖像[M,N]=size(image2)figure,imshow(image2);title('灰度圖');path1=input('請輸入要存儲的圖像路徑\n','s');imwrite(image2,path1);%存為灰度圖像效果如下：圖3.1彩色圖轉換為灰度圖本程序運行之后，要在MATLAB命令窗口中輸入將要轉換的圖像路徑，這里我的彩色圖像在“D:\tu3.jpg”，讀取圖像后可得出當前圖像的矩陣行列大小為154*615，利用rgb2gray函數(shù)可以將當前彩色圖像轉換為灰度圖像，為了方便之后的壓縮，此處將轉換后的圖像用imwrite命令將之存儲在“D:\tu31.jpg”，并能顯示轉換后的圖像行列大小為154*205，可以知道，轉換后的圖像比之原圖像縮小了3倍，這正是因為彩色圖像一個像素點由RGB三個灰度值描述，而灰度圖像一個像素點只由一個灰度值表示，因而彩色圖像經(jīng)轉換后會變?yōu)橹挥泻诎壮潭炔煌膱D像，這就達到了為下一步轉換為二值圖像的前提條件，即圖像矩陣中一個元素表示一個像素的灰度值。3.2進行游程編碼讀取灰度圖像路徑，先轉換為二值圖然后進行游程編碼，得出壓縮率。(也可將轉換二值圖的程序單列出來)path=input('請輸入要讀取的灰度圖像路徑\n','s');image1=imread(path);%讀入圖像[M,N]=size(image1);%計算圖像行列大小figure,subplot(211);imshow(image1);%顯示原圖像title('原圖像');IM1=image1(:);%將圖像轉換為一維數(shù)組IM1length=length(IM1);%計算轉換為一維數(shù)組的長度fori=1:1:IM1length%for循環(huán)，目的在于轉換為二值圖像ifIM1(i)>=127%灰度值大于127轉換為255，反之為0IM1(i)=255;elseIM1(i)=0;endendimage2=reshape(IM1,M,N);%重組圖像subplot(212),imshow(image2);%顯示重組后的圖像title('手動轉換后的二值圖像');%{level=graythresh(image1);%獲取二值圖閾值imgbw=im2bw(image1,level);%利用內(nèi)部函數(shù)轉換為二值圖subplot(222);imshow(imgbw);%顯示內(nèi)部函數(shù)轉換出的二值圖像title('內(nèi)部函數(shù)轉換的圖像');%}j=1;counter(j)=1;%游程序列碼初始化forz=1:1:(length(IM1)-1)ifIM1(z)==IM1(z+1)counter(j)=counter(j)+1;%每遇相等的灰度值，將當前的重合度加1elsedata(j)=IM1(z);%否則，將當前的序列碼加1j=j+1;counter(j)=1;endenddata(j)=IM1(length(IM1));%Comp=[data;counter]%查看編碼后的矩陣%{counterlength=length(counter);%編碼后的序列長度s=1:1:counterlength;figure,plot3(s,counter(s),data(s));%編碼后的序列函數(shù)關系title('編碼后的序列函數(shù)關系圖（三維圖）');xlabel('游程序列碼');ylabel('像素重合度');zlabel('灰度值');gridon;%}counterlength=length(counter);%編碼后的序列長度s=1:1:counterlength;figure,plot(s,counter(s));title('壓縮后的序列函數(shù)關系圖');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壓縮流程圖開始將原圖像矩陣重構為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]結束否是Z=IM1length是否開始讀入counter,data初始化k=1,m=1,n=1m<counterlengthn<counter(m)IM2(k)=data(m)k++將列向量IM2重構為原圖像結束否是圖3.3解壓流程圖圖3.2壓縮流程圖開始將原圖像矩陣重構為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]結束否是Z=IM1length是否開始讀入counter,data初始化k=1,m=1,n=1m<counterlengthn<counter(m)IM2(k)=data(m)k++將列向量IM2重構為原圖像結束否是是否本程序將選擇圖像的權利交給用戶，用戶可以通過輸入圖像在計算機中的路徑去讀取將要壓縮的圖像，程序將用戶輸入的路徑賦給path，并通過imread(path)命令讀取圖像。圖像矩陣會存儲在變量image1中，再通過image1(:)命令將圖像矩陣轉換為長度為IM1length的列向量IM1。初始化j,z兩個變量為1，建立一維矩陣counter并初始化counter(j)，此矩陣將接收壓縮中所得的灰度值的各個游程寬度，建立一維矩陣data，此矩陣將接收壓縮中所得灰度值序列。接著遍歷整個IM1的數(shù)值，用if語句判斷IM1(z)是否與IM1(z+1)相等，即判斷相鄰灰度值是否相等，若是相等，則初始化data(j)并將此灰度值賦給data(j)，以及將counter(j)累加，如果相鄰灰度值并不相等，則使j加1，即進入下一次游程的壓縮。當遍歷完整個IM1數(shù)值后，就可以將data,counter合并為一個二維矩陣Comp，此矩陣即壓縮后得到的碼字。對比原圖像矩陣的長度，就可以得到壓縮率CRatio。解壓流程：讀取data,counter兩個一維矩陣，初始化k，m，n為1，求得counter矩陣的長度counterlength，并遍歷整個counter矩陣中的數(shù)值，可以從壓縮流程中知道counter(m)即代表各個灰度值的寬度，data(m)代表相應的灰度值，兩相組合就能知道整個圖像矩陣的灰度序列，因而初始化一個一維矩陣IM2，并在循環(huán)體中賦值IM2(k)=data(m)，即可得到一個包含原圖像矩陣所有灰度值的矩陣IM2，將IM2用reshape(IM2,M,N)命令重組此矩陣為一個二維的矩陣，其中M,N是求得的原圖像的行列大小，這樣得出的矩陣即原圖像的二值矩陣，用imshow命令顯示出來即可對比。無論壓縮還是解壓，核心都在于循環(huán)體中遍歷數(shù)值時的賦值，將矩陣的數(shù)值打散并按照相應的順序排列，就能得到相應的壓縮效果。此程序也可以直接遍歷原圖像的二維矩陣，不過計算量會變大，鑒于在MATLAB中轉換一維矩陣的簡單易行，完全可以將原圖像矩陣轉換為一維矩陣再進行壓縮，這樣的效率無疑要高上許多。另外，針對二值圖像時，可以考慮只統(tǒng)計其中一個灰度值，這樣會減少壓縮過程的繁瑣，在此實例中為了原理的闡述清楚，將兩個灰度值都進行了統(tǒng)計。游程編碼本身可以對任何數(shù)值序列進行統(tǒng)計，不過只有對數(shù)值重復率較高的序列壓縮較理想，尤以二值圖為最，讀者可以通過附錄中的灰度圖像的游程編碼程序進行對比。

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

3.4游程編碼的簡單實現(xiàn)以上是游程編碼常用的二值圖編碼壓縮，其原理是將一個數(shù)矩陣轉換為列向量并對列向量中重復的數(shù)值進行統(tǒng)計，最后得出較為精簡的數(shù)矩陣，重復的數(shù)越緊密，壓縮率也就越大。下面由手動輸入的一組數(shù)矩陣實現(xiàn)的MATLAB仿真代碼:F=input('請輸入行程碼\n');j=1;counter(j)=1; %游程序列碼初始化forz=1:1:(length(F)-1)ifF(z)==F(z+1)counter(j)=counter(j)+1;%每遇相等的灰度值，將當前的重合度加1elsedata(j)=F(z);%否則，將當前的序列碼加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);%編碼后的序列長度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)壓縮后應得到：1321234534125334壓縮率為64%，可見游程編碼對重復率較高的碼字序列擁有較為優(yōu)秀的壓縮效率。

其效果如下：圖3.8簡單游程編碼實例從圖中不難看出，對于一維矩陣[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)計其各個數(shù)值的重復度（即游程寬度），可以得出壓縮矩陣Comp為[(1,3),(3,4),(2,1),(1,2),(2,5),(3,3),(4,3),(5,4)]。得出壓縮率為64%，可見對于有著不同元素的矩陣壓縮并不高（相對于二值圖的壓縮率）。

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