多媒體原理與系統(tǒng)設(shè)計(jì)第4章：無(wú)損數(shù)據(jù)壓縮編碼

多媒體原理與系統(tǒng)設(shè)計(jì)第四章無(wú)損數(shù)據(jù)壓縮編碼

1熵編碼1.1算術(shù)編碼（ArithmeticCoding）設(shè)s=(a1,a2,a3,a4)p=(0.10.40.20.3)message=a3a1a4a1a3a4a2編碼過(guò)程①將區(qū)間[0.0,1.0)按照碼元的概率分成4個(gè)部分碼元概率初始子區(qū)間a1a2a3a40.10.40.20.3[0.0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1.0)1熵編碼1.1算術(shù)編碼（ArithmeticCoding）②輸入消息的第1個(gè)字符a3，將其對(duì)應(yīng)的初始子區(qū)間作為它的編碼區(qū)間，即編碼區(qū)間為[0.5,0.7)。10.70.50.10.00.70.5Δ0.20.520.5Δ0.020.520.514Δ0.0060.51460.514Δ0.00060.514420.5143Δ0.000120.514420.514384Δ0.0000360.5144020.5143876a3a1a4a1a3a4a21熵編碼1.1算術(shù)編碼（ArithmeticCoding）③輸入消息的第2個(gè)字符a1，在上一步得到的編碼區(qū)間中取第1個(gè)十分之一作為a3a1串的編碼區(qū)間，即[0.5,0.52)。10.70.50.10.00.70.5Δ0.20.520.5Δ0.020.520.514Δ0.0060.51460.514Δ0.00060.514420.5143Δ0.000120.514420.514384Δ0.0000360.5144020.5143876a3a1a4a1a3a4a21熵編碼1.1算術(shù)編碼（ArithmeticCoding）④輸入第3個(gè)字符

a4

，在上一步得到的編碼區(qū)間中取第7個(gè)十分之一開(kāi)始的3個(gè)十分之一作為a3a1a4串的編碼區(qū)間，即[0.514,0.52)。10.70.50.10.00.70.5Δ0.20.520.5Δ0.020.520.514Δ0.0060.51460.514Δ0.00060.514420.5143Δ0.000120.514420.514384Δ0.0000360.5144020.5143876a3a1a4a1a3a4a21熵編碼1.1算術(shù)編碼（ArithmeticCoding）⑤

對(duì)后續(xù)輸入字符a1a3a4a2，重復(fù)上述處理過(guò)程。10.70.50.10.00.70.5Δ0.20.520.5Δ0.020.520.514Δ0.0060.51460.514Δ0.00060.514420.5143Δ0.000120.514420.514384Δ0.0000360.5144020.5143876a3a1a4a1a3a4a21熵編碼1.1算術(shù)編碼（ArithmeticCoding）⑥當(dāng)所有輸入字符處理完畢，最后所得的編碼區(qū)間的下界值或者上界值即為消息串的編碼輸出，該輸出值為一個(gè)實(shí)數(shù)：0.5143876。10.70.50.10.00.70.5Δ0.20.520.5Δ0.020.520.514Δ0.0060.51460.514Δ0.00060.514420.5143Δ0.000120.514420.514384Δ0.0000360.5144020.5143876a3a1a4a1a3a4a21熵編碼1.1算術(shù)編碼（ArithmeticCoding）

解碼過(guò)程

①輸入待解碼的編碼實(shí)數(shù)，檢查其落入的初始子區(qū)間，該區(qū)間對(duì)應(yīng)的字符即為第一個(gè)譯碼字符。0.5143876a30.50.71熵編碼1.1算術(shù)編碼（ArithmeticCoding）

②按照所有信源字符概率大小，將上一步譯碼字符對(duì)應(yīng)的區(qū)間分成幾個(gè)子區(qū)間，在這些子區(qū)間中，輸入數(shù)值落入的區(qū)間對(duì)應(yīng)的字符即為第二個(gè)譯碼字符：a1。0.5143876a30.50.70.50.520.50.520.60.64a11熵編碼1.1算術(shù)編碼（ArithmeticCoding）③重復(fù)上述過(guò)程，直到譯碼完畢。0.5143876a30.50.7a10.50.52a40.5140.520.5020.510.514……1熵編碼1.2行程編碼

基本思想給定如下消息

abcdddddddddffffgggg(20chars)則可用如下的索引+索引對(duì)象（重復(fù)對(duì)象）方式代表之a(chǎn)bc9d4f4g(consume9chars)RLE:index+indexedobject=codecunit

應(yīng)用

BMP文件：RLE_4&RLE_8編碼;JPEG等。2詞典編碼2.1詞典編碼分類

第一類字詞編碼基本思想：用指向早期曾經(jīng)出現(xiàn)過(guò)的字符串的指針來(lái)表示當(dāng)前被編碼字符串。ABCBCBCBCABCPBCPBCBC

2詞典編碼2.1詞典編碼分類

第二類字詞編碼從輸入的數(shù)據(jù)流中創(chuàng)建一個(gè)短語(yǔ)詞典，后續(xù)數(shù)據(jù)流中若出現(xiàn)詞典中的短語(yǔ)，則可用該短語(yǔ)在詞典中的索引表示該短語(yǔ)，而不需要輸出短語(yǔ)本身。ABCBCABCBDictionaryBC2ABCABC12B2詞典編碼2.2第一類詞典編碼算法

LZ77算法(byAbrahamLempelandJakob

Ziv)DatacodedDatawaitingcodeMax-Win-SizeLenOffLenNextcharCodingposition……2詞典編碼LZ77算法描述①Setthecodingpositionatthestartplace②Findthemaxlengthstringinslidewindowforthedatawaitingcode③Iffoundoutput(Off,Len,Nextchar);slidethewindowaheadLen+1;return②ifunfinishedcoding;elseoutput(0,0,Nextchar);slidethewindowahead1;return②ifunfinishedcoding;endif2詞典編碼LZ77算法舉例給定一個(gè)報(bào)文:abcdbbccaaabaeaaabaeeMAX-WIN-SIZEis10則算法處理過(guò)程如下：abcdbbccaaabaeaaabaeeCodingpositionOutput:(0,0,a)(0,0,b)(0,0,c)(0,0,d)(3,1,b)(4,1,c)(8,1,a)(10,2,a)(0,0,e)(6,6,e)2詞典編碼LZ77算法的特點(diǎn)①Outputdataincludessomeunnecessarydata②Codeddatapreviouslymaydecreasethecodingeffectlater③Theslidewindowsizehasinfluenceontheeffectofthewholecodingprocessing;butitisdifficulttomakethedecisionwhatlengthofthesizewillbebetter2詞典編碼2.2第一類詞典編碼的改進(jìn)

LZSS算法AsadevelopmentofLZ77,itrequiresthattheLenhastomorethanaconstantMIN-LENGTH①Setthecodingpositionatthestartplace②Findthemaxlengthstringinslidewindowforthedatawaitingcode③IfLen>=MIN-LENGTHoutput(Off,Len);slidethewindowaheadLen;return②ifunfinishedcoding;elseoutputNextchar;slidethewindowahead1;return②ifunfinishedcoding;endif2詞典編碼LZSS算法舉例給定一報(bào)文：AABBCBBAABCMIN_LENGTH=2,WIN_SIZE=10則算法處理過(guò)程如下：AABBCBBAABCOutput:AABBC(3,2)(7,3)C2詞典編碼2.3第二類詞典編碼算法LZ78算法描述①Dictionary=NULL;P=NULL;②C=Nextchar;③Ifp+CinDictionaryP=P+C;elseoutputtheindexofPinDictionaryandC;Dictionary=P+C;P=NULL;endif④Ifthe