圖像無(wú)損壓縮算法綜述

圖像無(wú)損壓縮算法綜述【摘要】本文介紹了常見(jiàn)的圖像無(wú)損壓縮方法：靜態(tài)及動(dòng)態(tài)霍夫曼(Huffman)編碼算法、算術(shù)編碼算法、LZW(lanpel-ziv-velch)編碼及其改良算法、行程編碼〔又稱游程編碼，RLE〕及改良自適應(yīng)游程編碼算法、費(fèi)諾-香農(nóng)編碼算法和一種改良的編碼方法。簡(jiǎn)要分析了各種算法的優(yōu)缺點(diǎn)?！娟P(guān)鍵詞】霍夫曼算術(shù)編碼LZW行程編碼費(fèi)諾-香農(nóng)編碼1前言隨著技術(shù)的不斷開(kāi)展，多媒體技術(shù)和通訊技術(shù)等對(duì)信息數(shù)據(jù)的存儲(chǔ)和傳輸也提出了更高的要求，給現(xiàn)有的有限帶寬帶來(lái)更嚴(yán)峻的考驗(yàn)，尤其是具有龐大數(shù)據(jù)量的數(shù)字圖像通信。存儲(chǔ)和傳輸?shù)母唠y度極大地制約了圖像通信的開(kāi)展，因此對(duì)圖像信息壓縮技術(shù)的研究受到了越來(lái)越多的關(guān)注。壓縮數(shù)據(jù)量是圖像壓縮的首要目的，但保證壓縮后圖像的質(zhì)量也是非常重要的，無(wú)損壓縮是指能精確恢復(fù)原始圖像數(shù)據(jù)的壓縮方法，其在編碼壓縮過(guò)程中沒(méi)有圖像信號(hào)的損失。本文介紹了常見(jiàn)的無(wú)損壓縮方法：靜態(tài)及動(dòng)態(tài)霍夫曼(Huffman)編碼算法、算術(shù)編碼算法、LZW(lanpel-ziv-velch)編碼及其改良算法、行程編碼〔又稱游程編碼，RLE〕及改良自適應(yīng)游程編碼算法、費(fèi)諾-香農(nóng)編碼算法和一種改良的編碼方法。2常見(jiàn)圖像無(wú)損壓縮算法2.1霍夫曼算法Huffman算法是一種用于數(shù)據(jù)壓縮的算法，由D.A.Huffman最先提出。它完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造平均長(zhǎng)度最短的編碼，有時(shí)稱之為最正確編碼，一般叫做Huffman編碼。頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長(zhǎng)的代碼代替，每個(gè)數(shù)據(jù)的代碼各不相同。這些代碼都是二進(jìn)制碼，且碼的長(zhǎng)度是可變的。2.1.1靜態(tài)霍夫曼編碼步驟：〔1〕將信號(hào)源的符號(hào)出現(xiàn)的概率〔在此稱為權(quán)值〕{w1，w2，...，wn}構(gòu)造成n棵二叉樹(shù)集合F={T1，T2，...，Tn}，其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹(shù)均為空?！?〕在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和〔3〕在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)參加F中。〔4〕重復(fù)〔2〕和〔3〕，直到F只含一棵樹(shù)為止，這棵樹(shù)便是霍夫曼〔Huffman〕樹(shù)?！?〕在合并中約定權(quán)值小的根結(jié)點(diǎn)在左子樹(shù)上，權(quán)值大的在右子樹(shù)上，然后在每個(gè)左分支上標(biāo)記為“0〞，右分支上標(biāo)記為“1〞，最后記錄從霍夫曼〔Huffman〕樹(shù)的根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)過(guò)的分支上的“0〞或“1〞的序列，從而得到每個(gè)符號(hào)的Huffman編碼。2.1.2自適應(yīng)霍夫曼編碼這種方案在不需要事先構(gòu)造Huffman樹(shù)，而是隨著編碼的進(jìn)行，逐步構(gòu)造Huffman樹(shù)。同時(shí)，這種編碼方案對(duì)符號(hào)的統(tǒng)計(jì)也動(dòng)態(tài)進(jìn)行，隨著編碼的進(jìn)行，同一個(gè)符號(hào)的編碼可能發(fā)生改變〔變得更長(zhǎng)或更短〕。在構(gòu)造動(dòng)態(tài)霍夫曼編碼樹(shù)的過(guò)程中，需要遵循兩條重要原那么：〔1〕權(quán)重值大的節(jié)點(diǎn)，節(jié)點(diǎn)編號(hào)也較大?！?〕父節(jié)點(diǎn)的節(jié)點(diǎn)編號(hào)總是大于子節(jié)點(diǎn)的節(jié)點(diǎn)編號(hào)。以上兩點(diǎn)稱為兄弟屬性〔siblingproperty〕。在每一次調(diào)整節(jié)點(diǎn)權(quán)重值時(shí)，都需要相應(yīng)的調(diào)整節(jié)點(diǎn)編號(hào)，以防止兄弟屬性被破壞。在對(duì)某一個(gè)節(jié)點(diǎn)權(quán)重值進(jìn)行“加一操作〞時(shí)，應(yīng)該首先檢查該節(jié)點(diǎn)是否具有所在的塊中的最大節(jié)點(diǎn)編號(hào)，如果不是，那么應(yīng)該將該節(jié)點(diǎn)與所在塊中具有最大節(jié)點(diǎn)編號(hào)的節(jié)點(diǎn)交換位置。然后再對(duì)節(jié)點(diǎn)的權(quán)重值加。這樣，由于該節(jié)點(diǎn)的節(jié)點(diǎn)編號(hào)已經(jīng)處于原來(lái)所屬塊中的最大值，因此權(quán)重值加一之后兄弟屬性仍然得到滿足。最后，由于節(jié)點(diǎn)的權(quán)重發(fā)生了變化，必須遞歸地對(duì)節(jié)點(diǎn)的父節(jié)點(diǎn)進(jìn)行加一操作。在需要插入一個(gè)新符號(hào)時(shí)，總是先構(gòu)造一個(gè)新的子樹(shù)，子樹(shù)包含NYT符號(hào)與新符號(hào)兩個(gè)葉節(jié)點(diǎn)，然后將舊的NYT節(jié)點(diǎn)由這個(gè)子樹(shù)替代。由于包含NYT符號(hào)的節(jié)點(diǎn)權(quán)重值為0，而包含新符號(hào)的葉節(jié)點(diǎn)的權(quán)重值為1，因此最終效果相當(dāng)于原NYT節(jié)點(diǎn)位置的權(quán)重值由0變?yōu)?。因此，下一步將試圖對(duì)其父節(jié)點(diǎn)執(zhí)行權(quán)重值“加一操作〞。對(duì)符號(hào)編碼的方法與靜態(tài)霍夫曼編碼一致，每次符號(hào)編碼完成以后，也將對(duì)包含符號(hào)的節(jié)點(diǎn)權(quán)值進(jìn)行加一操作。將一個(gè)新的符號(hào)插入編碼樹(shù)或者輸出某一個(gè)已編碼符號(hào)后，相應(yīng)的符號(hào)的出現(xiàn)次數(shù)增加了1，繼而編碼樹(shù)中各種符號(hào)的出現(xiàn)頻率發(fā)生了改變，不一定符合兄弟屬性，按照上述方法進(jìn)行調(diào)整，使其符合要求。2.2算術(shù)編碼算法算術(shù)編碼完全拋棄了用特殊字符代替輸入字符的思想。在算術(shù)編碼中，輸入的字符信息用0到1之間的數(shù)字進(jìn)行編碼，它用到兩個(gè)根本的參數(shù):符號(hào)的頻率及其編碼間隔。對(duì)于輸入的字符信息，算術(shù)編碼后形成一個(gè)唯一的浮點(diǎn)數(shù)。算術(shù)編碼的效率一般要優(yōu)于哈夫曼編碼，但實(shí)現(xiàn)要比哈夫曼編碼復(fù)雜。2.2.1算術(shù)編碼原理圖1算術(shù)編碼流程圖固定模式編碼需要預(yù)先對(duì)符號(hào)序列中的符號(hào)進(jìn)行預(yù)掃描，根據(jù)統(tǒng)計(jì)符號(hào)的概率來(lái)列出編碼概率表。引入幾個(gè)變量：low為編碼間隔的低端，rang為編碼間隔的長(zhǎng)度,ranglow為編碼字符的間隔的低端,ranghigh為編碼字符的間隔的高端。在固定模式編碼中，ranglow和ranghigh的編碼概率不變。計(jì)算流程如圖1。用例子說(shuō)明算術(shù)編碼編解碼原理，采用固定模式符號(hào)概率分配表見(jiàn)表1。假設(shè)要編碼字符串’eai’，那么編碼過(guò)程如圖2。表1算術(shù)編碼字符概率分配表圖2算術(shù)編碼示意圖2.2.2算術(shù)編碼解碼原理圖3解碼流程圖從原理上講，解碼的過(guò)程是編碼的逆過(guò)程，只要保證編碼和解碼使用同樣的字符概率分配表，解碼后的字符就不會(huì)出現(xiàn)誤差。根據(jù)編碼時(shí)所使用的字符概率區(qū)間分配表和壓縮后的數(shù)值代碼所在的范圍，可以很容易確定第一個(gè)字符。設(shè)法去掉第一個(gè)符號(hào)對(duì)區(qū)間的影響，找到下一個(gè)符號(hào)。重復(fù)以上操作，直到完成解碼過(guò)程。計(jì)算流程如圖3。2.3LZW編碼算法LZW編碼的根本思想是建立一個(gè)字典，將輸入字符串編碼成定長(zhǎng)的碼流輸出(通常為12位)，并在編碼過(guò)程中動(dòng)態(tài)生成字典，算法是自適應(yīng)的。但傳統(tǒng)LZW算法存在占用大量的字典容量、生成的字典項(xiàng)較多時(shí)查找效率低等缺陷。故討論一種改良LZW編碼壓縮算法進(jìn)，將字典初始化為16位，采用散列法和拉鏈法進(jìn)行詞條檢索，采用閾值判斷和LRU淘汰機(jī)制改良條目更新的方式，編碼時(shí)采用自適應(yīng)變碼長(zhǎng)方式。經(jīng)測(cè)試，相比于傳統(tǒng)LZW編碼數(shù)據(jù)壓縮算法，改良的算法對(duì)不同碼長(zhǎng)的數(shù)據(jù)的適應(yīng)性更好，并且壓縮比提高了約8%。2.3.1LZW編譯碼LZW編碼是一種基于字典模型的無(wú)損數(shù)據(jù)壓縮方法，由Lempel-Ziv-Welch共同提出。通過(guò)建立一個(gè)字符字典，用較短的碼字表示較長(zhǎng)的字符串，到達(dá)數(shù)據(jù)壓縮的目的。在動(dòng)態(tài)的建立字典的同時(shí)，字符串和碼字之間逐漸建立關(guān)系。后續(xù)的字符串與字典進(jìn)行比擬，不斷完善和壯大字典。生成的字典不需要隨著數(shù)據(jù)一塊存儲(chǔ)和傳輸，在解壓縮的過(guò)程中仍然能夠重建一個(gè)完全相同的字典，從而進(jìn)一步地提高壓縮效率。在介紹LZW編碼流程之前，首先定義幾個(gè)在LZW編碼、解碼過(guò)程中出現(xiàn)的概念:P:當(dāng)前前綴，表示在編碼算法中正在被處理的前綴C:當(dāng)前字符，表示在編碼算法中當(dāng)前確定的字符。cW:當(dāng)前碼字，當(dāng)前被處理字符串對(duì)應(yīng)的碼字。pW:先前碼字，先前被處理字符串對(duì)應(yīng)的碼字。String.cW:當(dāng)前碼字對(duì)應(yīng)的字符串。String.pW:先前碼字對(duì)應(yīng)的字符串。LZW編碼過(guò)程:建立初始字典，該初始字典中包含待處理字符數(shù)據(jù)流中所有可能出現(xiàn)的字符。同時(shí)，設(shè)置前綴P為空；讀取字符串?dāng)?shù)據(jù)流中的下一個(gè)字符作為當(dāng)前字符，送至C中；判斷P+C是否已經(jīng)存在字典之中，假設(shè)存在:P=P+C，用C來(lái)擴(kuò)展P，假設(shè)不存在：把表示前綴P的碼字cW輸出到編碼數(shù)據(jù)流中。將字符串P+C按照順序參加字典中，同時(shí)使P=C；判斷字符數(shù)據(jù)流是否編碼完畢，假設(shè)編碼完畢:編碼完成，輸出P所對(duì)應(yīng)的碼字cW到編碼數(shù)據(jù)流結(jié)尾處，假設(shè)未完成，那么繼續(xù)編碼。圖4LZW編碼流程圖LZW譯碼過(guò)程:建立初始字典，該初始字典中包含待處理字符數(shù)據(jù)流中所有可能出現(xiàn)的字符。讀取編碼數(shù)據(jù)流中的第一個(gè)碼字cW。輸出cW所對(duì)應(yīng)的字符串String.cW到字符數(shù)據(jù)流中。pW=cW，讀入編碼數(shù)據(jù)流中的下一個(gè)碼字cW。判斷cW對(duì)應(yīng)的字符串String.cW是否在字典中?假設(shè)在字典中:將String.cW輸出到字符數(shù)據(jù)流，P=String.pW，C=String.pW字符串中的第一個(gè)字符，P+C添加到字典；假設(shè)不在字典中:P=String.pW，C=String.cW中的第一個(gè)字符，輸出P+C到字符數(shù)據(jù)流，然后將P+C添加至字典。判斷碼字流中是否還有待譯碼字?是:返回步驟pW=cW；否:譯碼結(jié)束。圖5LZW解碼流程圖2.3.2改良的LZW編碼LZW壓縮算法的執(zhí)行速度依賴于字典查找的速度。在LZW壓縮算法中，假設(shè)直接檢索字典，編碼的速度很低，同時(shí)時(shí)間復(fù)雜度較高，為O(n2)。因此，選擇一種效率較高的字典存儲(chǔ)和遍歷索引的方式是提高LZW編碼效率的主要途徑。為了提高字典的存儲(chǔ)和索引效率，引入散列表(HashTable)來(lái)存儲(chǔ)字典，只需通過(guò)關(guān)鍵字就可以確定結(jié)點(diǎn)的存儲(chǔ)位置，這樣能有效提高字符串表的檢索效率。為了提高編碼的效率，采用可變長(zhǎng)度的編碼方法。在系統(tǒng)中，使用的可變編碼位數(shù)從8位開(kāi)始，當(dāng)編碼長(zhǎng)度超過(guò)了8位的表示范圍，那么自動(dòng)增加到9位編碼，依次遞增編碼位數(shù)。但增加編碼位數(shù)使得算法性能和執(zhí)行效率都受到影響，因此，設(shè)定編碼長(zhǎng)度的最大范圍為12位，當(dāng)編碼超出12位(4096)表示范圍，需要重新開(kāi)始字典的生成和編碼。當(dāng)詞條數(shù)目過(guò)多導(dǎo)致字典容量飽和時(shí)，需要重新生成字典，clear操作會(huì)嚴(yán)重影響壓縮編碼的壓縮比和執(zhí)行效率，因此，為了解決傳統(tǒng)的LZW編碼壓縮效率低的問(wèn)題，現(xiàn)作出以下改良:當(dāng)字典中串表填滿之后，不立即輸出clear信號(hào)，刪除字典表，而是繼續(xù)輸入一定長(zhǎng)度的數(shù)據(jù)流，使用現(xiàn)有的字典表表對(duì)其進(jìn)行壓縮編碼，同時(shí)計(jì)算出這時(shí)被壓縮的數(shù)據(jù)流的壓縮比，如果所得到的壓縮比擬低，滿足系統(tǒng)要求即(其中為當(dāng)前計(jì)算的壓縮比，為系統(tǒng)給定的一個(gè)閥值)，那么繼續(xù)先前的操作;如果所得到的壓縮比時(shí)，表示現(xiàn)在的字典表無(wú)法滿足當(dāng)前數(shù)據(jù)壓縮的要求，那么進(jìn)行刪除和重建字典表的操作。這樣可以有效抑制那些突發(fā)的數(shù)據(jù)對(duì)整體壓縮性能的影響，使得系統(tǒng)不會(huì)由于一些數(shù)據(jù)毛刺的影響導(dǎo)致屢次刪除和重建字典表，提高了LZW壓縮算法的壓縮比和執(zhí)行效率。改良的LZW編碼算法的軟件流程圖如下列圖6所示：圖6改良的LZW算法實(shí)現(xiàn)流程圖可以通過(guò)流程圖看出，改良的LZW編碼方式主要在添加新詞條字符串時(shí)，需要判斷碼長(zhǎng)是否滿足要求，同時(shí)當(dāng)系統(tǒng)碼長(zhǎng)到達(dá)最大，即12位碼長(zhǎng)之后，是否輸出clear信號(hào)需要通過(guò)判斷一段數(shù)據(jù)流的壓縮比后決定。2.4游程編碼算法行程編碼RLE又稱游程編碼，這種壓縮方法廣泛的應(yīng)用于各種圖像格式的數(shù)據(jù)壓縮處理中，是壓縮圖像最簡(jiǎn)單的方法之一。2.4.1傳統(tǒng)游程編碼游程編碼技術(shù)是在給定的圖像數(shù)據(jù)中尋找連續(xù)重復(fù)的數(shù)值，然后用兩個(gè)字符取代這些連續(xù)值。傳統(tǒng)的游程編碼是由兩個(gè)元素的序?qū)M成，其中表示編碼符號(hào)，表示游程長(zhǎng)度，等于有相同編碼符號(hào)的相同元素的數(shù)目。這種方法在處理包含大量重復(fù)信息的數(shù)據(jù)時(shí)可以獲得很好的壓縮效率。但是如果連續(xù)重復(fù)的數(shù)據(jù)很少，那么難獲得較好的壓縮比，甚至可能會(huì)導(dǎo)致壓縮后的編碼字節(jié)數(shù)大于處理前的圖像字節(jié)數(shù)。2.4.2改良自適應(yīng)游程編碼算法固定格式的常規(guī)游程編碼與實(shí)際游程長(zhǎng)度的適應(yīng)能力差。因此，需要一種靈活的游程編碼方式：遇到短游程用較短的字長(zhǎng)描述，遇到長(zhǎng)游程時(shí)自動(dòng)用較長(zhǎng)的碼子描述。從二進(jìn)制的表達(dá)方式可以得到啟發(fā)：二進(jìn)制計(jì)數(shù)方法的實(shí)質(zhì)是對(duì)不同位置的比特分配不同的權(quán)重，而這些權(quán)重的分配能夠描述任何一個(gè)整數(shù)。因此，最為理想的游程編碼的的字長(zhǎng)應(yīng)當(dāng)?shù)扔谟纬痰膶?shí)際長(zhǎng)度對(duì)應(yīng)的二進(jìn)制數(shù)的比特總數(shù)。但是游程的實(shí)際長(zhǎng)度是隨機(jī)的，因此解碼器無(wú)法確切知道當(dāng)前的字長(zhǎng)是多少。為此提出一種改良的游程編碼算法。仍然采用兩個(gè)元素的序?qū)M成，其中等于原始碼流長(zhǎng)度對(duì)應(yīng)的二進(jìn)制數(shù)的比特，表示對(duì)應(yīng)比特?cái)?shù)的長(zhǎng)度。設(shè)定一個(gè)游程指針(簡(jiǎn)稱游針)和兩個(gè)碼表(O碼表和1碼表)。0碼表適合對(duì)連0編碼，1碼表適合對(duì)連l編碼。由統(tǒng)計(jì)特性知，連0遠(yuǎn)遠(yuǎn)大于連1，對(duì)于0碼表來(lái)說(shuō)，往往比擬長(zhǎng)，因此也相應(yīng)比擬大，考慮最大連0，把取為4位。而對(duì)于1碼表來(lái)說(shuō)，比擬短，因此也相應(yīng)比擬小，考慮最大連1，把取為3位。首先根據(jù)游針探測(cè)輸入碼元極性，判斷是采用0碼表還是1碼表。選中碼表后，游針通過(guò)計(jì)數(shù)器方式探測(cè)連續(xù)碼流，得到連續(xù)碼流長(zhǎng)度n；然后將碼流長(zhǎng)度轉(zhuǎn)化為二進(jìn)制碼，得到,同時(shí)計(jì)算的長(zhǎng)度，并轉(zhuǎn)化為二進(jìn)制碼得到；設(shè)原始碼長(zhǎng)為，那么。轉(zhuǎn)化為二進(jìn)制可以采用如下運(yùn)算：依次把就得到，同理可得到。最后合并，得到最終編碼。2.5費(fèi)諾-香農(nóng)編碼算法由于霍夫曼編碼法需要屢次排序，當(dāng)元素很多時(shí)不方便，為此費(fèi)諾和香農(nóng)分別單獨(dú)提出類似的方法，使編碼方法更簡(jiǎn)單。具體編碼方法如下：把按概率由大到小，從上到下排成一列，然后把分成兩組和并使得：給兩組中的賦值，將概率大的一組賦為0，概率小的一組賦為1。這是該方法的賦值原那么。把兩組分別按〔1〕、〔2〕分組賦值，不斷重復(fù)，直到每組只有一種輸入元素為止。將每個(gè)所賦的值依次排列起來(lái)就是費(fèi)諾-香農(nóng)編碼。2.6一種新的無(wú)損圖像壓縮算法本方法是一種新的二進(jìn)制(位級(jí))無(wú)損圖像壓縮方法——將錯(cuò)誤糾正BCH碼引入到圖像壓縮算法中；將圖像的二進(jìn)制分為大小為7的碼字，這些塊進(jìn)入到BCH解碼器，消除了校驗(yàn)位后，使得原來(lái)的塊的大小減少到4位。BCH編碼方式是將大小為K位的塊，通過(guò)增加m位的校驗(yàn)位，形成—個(gè)長(zhǎng)度為n的碼字。在本方法中，我們將n的大小定義為7。這個(gè)值被選中后進(jìn)行屢次實(shí)驗(yàn)，得到較好的結(jié)果。圖7示出了BCH算法系統(tǒng)的框架。圖7BCH算法系統(tǒng)構(gòu)造圖2.6.1壓縮步驟第一步：預(yù)處理步驟，將圖像轉(zhuǎn)換成二進(jìn)制數(shù)字圖像。第二步：使用(7，4)BCH碼解碼器，將這些二進(jìn)制數(shù)轉(zhuǎn)換成一個(gè)由4位數(shù)據(jù)產(chǎn)生的長(zhǎng)度為7的塊。請(qǐng)注意，并非所有的長(zhǎng)度為7位的塊都是碼字，也有長(zhǎng)度為7的塊是非編碼字。因此，我們使用—個(gè)額外的位來(lái)區(qū)分碼字和非碼字。第三步：生成二進(jìn)制數(shù)的Huffman編碼壓縮圖像文件。第四步：添加位文件應(yīng)用兩種不同的算法：執(zhí)行長(zhǎng)度編碼(RLE)算法嘲和哈夫曼編碼算法。然后，將該文件添加到壓縮的二進(jìn)制文件中。圖8為該方法的流程圖。圖8算法流程圖2.6.2解壓步驟第一步：讀壓縮文件的標(biāo)題，并從中提取補(bǔ)充位文件，然后通過(guò)應(yīng)用哈夫曼解碼器解碼提取的文件，申請(qǐng)的RLE解碼器，以增加位的方式使得文件返回其原來(lái)的形式。第二步：對(duì)使用哈夫曼算法壓縮的圖像文件進(jìn)行解碼。第三步：使用BCH編碼。在這個(gè)過(guò)程中，將讀取文件的所有位的信息。添加位的值決定了當(dāng)前塊K的大小，如果添加位當(dāng)前的值是1，那么塊的大小是4位，否那么塊的大小是7位。BCH編碼器返回的塊大小為4位到7位的原始大小，并返回BCH解碼刪除奇偶位。第四步：圖像沒(méi)有任何數(shù)據(jù)喪失返回其原始狀態(tài)。3常見(jiàn)無(wú)損壓縮算法的總結(jié)本文介紹了常見(jiàn)的無(wú)損壓縮方法：靜態(tài)及動(dòng)態(tài)霍夫曼(Huf}nan)編碼算法、算術(shù)編碼算法、LZW(lanpel-ziv-velch)編碼及其改良算法、行程編碼〔又稱游程編碼，RLE〕及改良自適應(yīng)游程編碼算法、費(fèi)諾-香農(nóng)編碼算法和一種改良的編碼方法。3.1Huffman編碼算法分析Huffman的編碼方法充分利用了短碼，編碼效率比擬高，且對(duì)編碼設(shè)備的要求也比擬簡(jiǎn)單，是綜合性能較高的一種編碼方法。但是，它也存在工作量大、編解碼時(shí)問(wèn)較長(zhǎng)等缺陷，給實(shí)際應(yīng)用帶來(lái)很大困難。自適應(yīng)霍夫曼編碼方案在不需要對(duì)數(shù)據(jù)掃描兩遍，而是隨著編碼的進(jìn)行，逐步構(gòu)造Huffman樹(shù)。同時(shí)，這種編碼方案對(duì)符號(hào)的統(tǒng)計(jì)也動(dòng)態(tài)進(jìn)行，隨著編碼的進(jìn)行，同一個(gè)符號(hào)的編碼可能發(fā)生改變。3.2算術(shù)編碼算法分析算術(shù)編碼完全拋棄了用特殊字符代替輸入字符的思想。在算術(shù)編碼中，輸入的字符信息用0到1之間的數(shù)字進(jìn)行編碼，它用到兩個(gè)根本的參數(shù):符號(hào)的頻率及其編碼間隔。對(duì)于輸入的字符信息，算術(shù)編碼后形成一個(gè)唯一的浮點(diǎn)數(shù)。算術(shù)編碼的效率一般要優(yōu)于哈夫曼編碼，但實(shí)現(xiàn)要比哈夫曼編碼復(fù)雜。算術(shù)編碼能最大限度地減小信息的冗余度，與Huffman編碼方法相比，在同樣的計(jì)算機(jī)系統(tǒng)上，算術(shù)編碼可以得到更好的壓縮效果，但卻要消耗也許幾十倍的計(jì)算時(shí)間，因此無(wú)法成為日常使用的壓縮方法。3.3LZW編碼算法分析LZW編碼屬于字典編碼，其原理是利用字典把每個(gè)字符串編碼為一個(gè)標(biāo)識(shí)，利用查字典的方法找出重復(fù)出現(xiàn)的字符串，以標(biāo)識(shí)來(lái)代替字符串，從而到達(dá)壓縮的目的。LZW編碼實(shí)現(xiàn)的根本思想是：讀取字符串；如果在字典中找到匹配，那么用字典地址代替該字符串，并繼續(xù)下一個(gè)查找，直到查找不到，那么把未查找的字符串參加字典；讀入下一個(gè)字符，循環(huán)上述過(guò)程，直到結(jié)束。LZW壓縮算法也存在著一些缺乏之處，故討論一種改良的LZW編碼數(shù)據(jù)壓縮算法，對(duì)傳統(tǒng)LZW編碼數(shù)據(jù)壓縮算法進(jìn)行了改良，將字典初始化為16位，采用散列法和拉鏈法進(jìn)行詞條檢索，采用閾值判斷和LRU淘汰機(jī)制改良條目更新的方式，編碼時(shí)采用自適應(yīng)變碼長(zhǎng)方式。相比于傳統(tǒng)LZW編碼數(shù)據(jù)壓縮算法，改良的算法對(duì)不同碼長(zhǎng)的數(shù)據(jù)的適應(yīng)性更好，并且壓縮比提高了約8%。3.4游程編碼算法分析游程編碼(run-lengthencoding)是把一串連續(xù)的重復(fù)值(如圖像的像素值)用一個(gè)單獨(dú)的值和一個(gè)計(jì)數(shù)值來(lái)取代。對(duì)有大面積的連續(xù)陰影或者顏色相同子塊的圖像，使用這種方法實(shí)現(xiàn)簡(jiǎn)單，壓縮效果很好。傳統(tǒng)的游程編碼方法，往往導(dǎo)致較短游程的編碼位數(shù)大于較短游程長(zhǎng)度的自然位數(shù)，當(dāng)二元序列中較短游程較多時(shí)，較短游程重新編碼所導(dǎo)致的數(shù)據(jù)膨脹會(huì)嚴(yán)重影響二元序列的壓縮效能。自適應(yīng)游程編碼是一種對(duì)小波域經(jīng)數(shù)學(xué)形態(tài)學(xué)處理得到的小波顯著系數(shù)的有效編碼方式。圖像小波分解。經(jīng)數(shù)學(xué)形態(tài)學(xué)膨脹處理后，位平面將出現(xiàn)大量極長(zhǎng)的連“0〞，利用游程編碼將是非常有效的。改良的自適應(yīng)游程編碼算法最突出的新特點(diǎn)是其可以將原始比特流轉(zhuǎn)換成碼長(zhǎng)的二進(jìn)制編碼。實(shí)驗(yàn)結(jié)果說(shuō)明，當(dāng)連續(xù)碼流相等的情況下，改良的算法可以有效減少編碼長(zhǎng)度。3.5費(fèi)諾-香農(nóng)編碼算法分析費(fèi)諾-香農(nóng)編碼算法與霍夫曼編碼有類似之處，但霍夫曼編碼法需要屢次排序，當(dāng)元素很多時(shí)不方便，費(fèi)諾-香農(nóng)編碼算法使編碼方法更簡(jiǎn)單。3.6新的無(wú)損壓縮算法分析本文中，詳細(xì)介紹了一種新的無(wú)損圖像壓縮方案。新的二進(jìn)制(位級(jí))無(wú)損圖像壓縮方法——將錯(cuò)誤糾正BcH碼引入到圖像壓縮算法中；將圖像的二進(jìn)制分為大小為7的碼字，這些塊進(jìn)入到BCH解碼器，消除了校驗(yàn)位后，使得原來(lái)的塊的大小減少到4位。實(shí)驗(yàn)結(jié)果說(shuō)明，此壓縮算法是有效的，并給出了一個(gè)很好的壓縮比，而且不喪失數(shù)據(jù)。BC