【文章內(nèi)容簡(jiǎn)介】 55,后面的項(xiàng)為空白 .為方便起見 ,我們管字典中的每一項(xiàng)叫 模式 . (2) 開始對(duì)圖像文件編碼 ,圖像文件從左向右掃描 ,把掃描得到的數(shù)據(jù)與字典中的模式進(jìn)行比較 . 如果相同 ,就把這個(gè) 模index(在數(shù)組中的位置 )作為碼字輸出 .如果在字典中找不到與之匹配的模式 ,則在字典中創(chuàng)建一個(gè)新的模式 (從第 256項(xiàng)開始 ). 原始碼流 35 76 67 35 76 78 90 33 35 76 78 37 ? 開始編碼 : a 因?yàn)榈谝粋€(gè)數(shù)字是 35,我們必然可以從字典中找到與之匹配的模式 (也就是第 35個(gè) ),但我們不急著用第 35個(gè)模式與之匹配 ,先看看第二個(gè)數(shù)字是 76, 希望在字典中能找到一個(gè)更長(zhǎng)的模式35 76這樣的模式 ,與之匹配 , 但不幸的是我們沒有找到 ,所以只對(duì)第一個(gè)數(shù)字 35編碼 , 結(jié)果輸出 35。 同時(shí)把 35 76加入字典的第 256項(xiàng) ,希望以后能碰到它 . b 同理 ,對(duì) 76編碼 , 輸出 76, 同時(shí)把 76 67加入字典的第257項(xiàng) . c 同理 ,對(duì) 67編碼 , 輸出 67, 同時(shí)把 67 35加入字典的第258項(xiàng) . d 這時(shí)注意了 : 對(duì) 35編碼 , 是不是現(xiàn)在還輸出 35呢 ? 當(dāng)然不是 ,我們發(fā)現(xiàn) 35后面跟著 76,掃描字典 ,可以發(fā)現(xiàn)第 256個(gè)模式與之匹配 , 輸出 256. 同時(shí) ,將模式 35 76 78加入到字典的第 259項(xiàng) . e 同理 ,接下來輸出 78, 90, 33, 259, 37. ? 所以輸出的碼流為 35 76 67 256 78 90 33 259 37. 參考文獻(xiàn) ? [1]楊國(guó)梁 ,張光年 .無損 LZW壓縮算法及實(shí)現(xiàn) .首都師范大學(xué)學(xué)報(bào) (自然科學(xué)版 ).， 1113 ? [2]董雪豐 ,嚴(yán)閃 .LZW壓縮算法 .福建電腦 .,2627 ? [3]林小竹，籍俊偉 .一種改進(jìn)的 LZW 壓縮算法 .計(jì)算機(jī)工程 .,第 31卷， 199201 ? 有損編碼是以丟失部分信息為代價(jià)來換取高壓縮比 。 ? 有損壓縮方法主要有有損預(yù)測(cè)編碼方法 、 變換編碼方法等 。 ? 在預(yù)測(cè)編碼中 ， 對(duì)差值信號(hào)進(jìn)行量化后再進(jìn)行編碼就稱之為有損預(yù)測(cè)編碼 。 ? 有損預(yù)測(cè)方法有多種 ， 其中差分脈沖編碼調(diào)制(Differential Pulse Code Modulation， 簡(jiǎn)稱DPCM)， 是一種具有代表性的編碼方法 。 DPCM系統(tǒng)由編碼器和解碼器組成 ， 它們各有一個(gè)相同的預(yù)測(cè)器 。 DPCM系統(tǒng)的工作原理如下圖所示 : 量化器 編碼器 預(yù)測(cè)器 信道傳輸 解碼器 輸入 輸出 預(yù)測(cè)器 ( , )f i j ( , )e i j 39。( , )e i j39。( , )f i j39。( , )f i j39。( , )f i j39。( , )e i j39。( , )f i j? 系統(tǒng)包括發(fā)送 、 接收和信道傳輸三個(gè)部分 。 發(fā)送端由編碼器 、 量化器 、 預(yù)測(cè)器和加減法器組成；接收端包括解碼器和預(yù)測(cè)器等；信道傳送以虛線表示 。圖中輸入信號(hào) f(i,j)是坐標(biāo) (i,j) 處的像素的實(shí)際灰度值 ， 是由已出現(xiàn)先前相鄰像素點(diǎn)的灰度值對(duì)該像素的預(yù)測(cè)灰度值 。 e(i,j)是預(yù)測(cè)誤差 。 ? DPCM包含量化器 ， 這時(shí)編碼器對(duì)編碼 ， 量化器導(dǎo)致了不可逆的信息損失 ， 這時(shí)接收端經(jīng)解碼恢復(fù)出的灰度信號(hào)不是真正的 f(i,j)， 而是重建信號(hào) 。 可見引入量化器會(huì)引起一定程度的信息損失 ， 使圖像質(zhì)量受損 。 但是可以利用人眼的視覺特性 ， 丟失不易覺察的圖像信息 ， 不會(huì)引起明顯失真 。 ),( jif? ? 變換編碼不是直接對(duì)空域圖像信號(hào)編碼 ，而是首先將圖像數(shù)據(jù)經(jīng)過某種正交變換 （ 如傅立葉變換 （ DFT） ， 離散余弦變換 （ DCT） ， KL變換等等 ） 另一個(gè)正交矢量空間 (稱之為變換域 )， 產(chǎn)生一批變換系數(shù) ， 然后對(duì)這些變換系數(shù)進(jìn)行編碼處理 ， 從而達(dá)到壓縮圖像數(shù)據(jù)的目的 。 ? 變換編碼的原理 如下圖： ? 圖像數(shù)據(jù)經(jīng)過正交變換后 ， 空域中的總能量在變換域中得到保持 ， 但像素之間的相關(guān)性下降 ， 能量將會(huì)重新分布 ， 并集中在變換域中少數(shù)的變換系數(shù)上 ，因此 ， 選擇少數(shù) F(u,v)來重建圖像就可以達(dá)到壓縮數(shù)據(jù)的目的 ， 并且重建圖像僅引入較小誤差 。 ? 變換多采用正交函數(shù)為基礎(chǔ)的變換 。 f(x,y) 重建 f(x,y) 圖象 正交 變換 樣本 選擇 量化 編碼 F(u,v) ( , )Fuv? ( , )F u v( , )F u v反正交 變換 補(bǔ)零 解碼 數(shù)字信道 ? 卡胡南 列夫變換 （ KL） 對(duì)于 N?N的矩陣 T，有 N個(gè)標(biāo)量 λi ， i=1,2,… ,N,能使 |TλiI|=0 則 λi 叫做矩陣 T的特征值。另外， N個(gè)滿足 的向量 Vi叫做 T的特征向量，這些特征向量構(gòu)成一個(gè)正交基集。 設(shè) X是一個(gè) N?1的隨機(jī)向量，也就是說， X的每個(gè)分量都是 xi隨機(jī)變量。 X的均值（平均向量）可以由L個(gè)樣本向量來估計(jì)向量 Mx： iii VTV ?????Lllx XLM11（ 732） ? Mx協(xié)方差矩陣可以由 來估計(jì)。協(xié)方差矩陣是實(shí)對(duì)稱的。對(duì)角元素是個(gè)隨機(jī)變量的方差，非對(duì)角元素是它們的協(xié)方差。 ? 定義一個(gè)線性變換 T，它可由任何 X向量產(chǎn)生一個(gè)新向量 Y： ? ? 式中， T的各行是 Mx的特征向量，即 T的行向量就是 Mx的特征向量。 ?? ?????? Ll TllTllTxxMx MMXXLMXMXE 11}))({()( xMXTY ??（ 733） （ 734） ? 變換得到的 Y是期望為零的隨機(jī)向量 。 Y的協(xié)方差矩陣可以由 X的協(xié)方差矩陣決定： 因?yàn)?T的各行是 Φx 的特征向量，故 Φy 是一個(gè)對(duì)角陣，對(duì)角元素是的 Φx 特征值。因此 這些也是的 Φx 特征值。 ? 隨機(jī)向量 Y是由互不相關(guān)的隨機(jī)變量組成的，因此線性變換 T起到了消除變量間的相關(guān)性的作用。 TXY TT ???Φx＝ λ 1 0 0 λ N （ 735） ? 特征向量變換是可逆的。 ? 要實(shí)現(xiàn)對(duì)信號(hào)進(jìn)行 K—L變換，首先要求出矢量x的協(xié)方差短陣 Φx ，再求協(xié)方差矩陣 Φx 的特征值 λi ，然后求 λ 對(duì)應(yīng)的 Φx 的特征向量，再用 Φx 的特征向量構(gòu)成正交矩陣 T。 ? 例 :若已知隨機(jī)矢量 x的協(xié)方差矩陣為 求其正交矩陣 T？ Φx＝ 6 2 0 2 2 － 1 0 － 1 1 1) 按 , 求 Φx 的特征值 λi : 得 : 則可解得 : = =2 = 2) 求 λi 對(duì)應(yīng)的特征向量。將 λ1 ， λ2 ， λ3 代入(731)中分別求得如下三個(gè)特征向量： = = = 0|| ??? xI?0110122026000000???????????????????????????0110122026???????????????????1? 2? 3?1V 2V 3V??????????????????????????? 用 V1， V2， V3的轉(zhuǎn)置向量作為正交矩陣 T的行向量，那么，對(duì)于任一均值為 0的向量 X=(2，1， )的 KL變換為 : 則 Y的協(xié)方差矩陣 Φy 為 : Y=TX= － － － 2 1 － = － ΦY =TΦXTT = 0 0 0 2 0 0 0 離散余弦變換 (DCT) ? 在數(shù)字圖像壓縮編碼中 ， 最佳變換 KL計(jì)算復(fù)雜 ， 一般不采用 。 ? 由于 DCT與 KL變換壓縮性能和誤差很接近 ， 而 DCT計(jì)算復(fù)雜度適中 ， 又具有可分離特性 ， 還有快速算法等特點(diǎn) ， 所以近年來在圖像數(shù)據(jù)壓縮中 ， 采用離散余弦變換編碼的方案很多 。 ? JPEG、 MPEG、 ， 都用到離散余弦變換編碼進(jìn)行數(shù)據(jù)壓縮 。 ? 余弦變換是傅立葉變換的一種特殊情況 。 在傅立葉級(jí)數(shù)展開式中 ， 如果被展開的函數(shù)是實(shí)偶函數(shù) ， 那么 ，其傅立葉級(jí)數(shù)中只包含余弦項(xiàng) ， 再將其離散化由此可導(dǎo)出余弦變換 ， 或稱之為離散余弦變換 DCT(Discrete Cosine Transform)。 ? 二維離散偶余弦正變換公式為： 式中 ， x,y,u,v＝ 0， 1…… ， N1。 當(dāng) u=v=0時(shí) 。 當(dāng) u=1， 2， … ， N1； v=1，2， … ， N1時(shí) 。 ?????? ???????? ??? ? ??????? vNyuNxyxfNvEuEvuC NxNy 212c os212c os),(2)()(),( 10102/1)()( ?vEuE1)()( ?vEuE（ 738） ? 二維離散偶余弦逆變換公式為： 式中 x,y,u,v＝ 0， 1…… ， N1。 當(dāng) u=v=0時(shí) 。 當(dāng) u=1， 2， … ， N1； v=1，2， … ， N1時(shí) 。 2/1)()( ?vEuE1)()( ?vEuE?????? ???????? ??? ? ??????? vNyuNxvuCvEuENyxf NuNv 212c os212c os),()()(2),( 1010（ 739） 二維離散余弦變換核具有可分離特性 ， 所以 ， 其正變換和逆變換均可將二維變換分解成系列一維變換 (行 、列 )進(jìn)行計(jì)算 。 在 DCT為主要方法的變換編碼中 ， 一般不直接對(duì)整個(gè)圖像進(jìn)行變換 ， 而是首先對(duì)圖像分塊 ， 將 M N的一幅圖像分成不重疊的 M/K N/K個(gè) K K塊分別進(jìn)行變換 。 這樣做的好處主要體現(xiàn)在： 第一 ， 降低運(yùn)算量 ， 如對(duì)一幅 512 512圖像 ， 分塊變換僅需約 1／ 3的運(yùn)算量； 其次 ， 后續(xù)的量化和掃描處理可以得到明顯的簡(jiǎn)化； 第三 ， 容易將傳輸誤差引起的錯(cuò)誤控制在一個(gè)塊內(nèi) ，而不是整個(gè)圖像擴(kuò)散