采用離散小波變換和游程長(zhǎng)度編碼的圖像壓縮與恢復(fù)*

蔣正金， 張長(zhǎng)江， 端木春江

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

0 引言

信息時(shí)代的到來(lái)，數(shù)據(jù)量呈現(xiàn)爆炸式增長(zhǎng)，無(wú)論傳輸或存儲(chǔ)這些海量數(shù)據(jù)都需要對(duì)數(shù)據(jù)進(jìn)行有效的壓縮．在遙感技術(shù)中，各種航天探測(cè)器采用壓縮編碼技術(shù)，將獲取的巨大信息送回地面．圖像壓縮就是數(shù)據(jù)壓縮技術(shù)在數(shù)字圖像上的應(yīng)用，它的目的是減少圖像數(shù)據(jù)中的冗余信息，從而能采用更加高效的格式存儲(chǔ)和傳輸圖像［1］．

常用的圖像壓縮編碼方法有熵編碼、預(yù)測(cè)編碼、變換編碼和混合編碼等［2］．隨著圖像編碼技術(shù)的發(fā)展，許多新的壓縮方法被提出，如利用人工神經(jīng)網(wǎng)絡(luò)的壓縮編碼、分形編碼、基于對(duì)象壓縮編碼和基于模型的壓縮編碼及小波圖像編碼方法等［3］．

離散小波變換(discrete wavelet transform，DWT)具有頻率分解的特點(diǎn)，能把圖像信號(hào)的能量聚集于某些頻帶中．由于離散小波變換具有聚能特性和位平面碼流中有大量的連“0”，所以游程長(zhǎng)度編碼(run length encoding，RLN)是適應(yīng)該情況的有效編碼［4］．

本文在研究離散小波變換和游程長(zhǎng)度編碼的基礎(chǔ)上，提出了一種采用離散小波變換先對(duì)圖像進(jìn)行3層分解，并對(duì)分解后的圖像進(jìn)行游程長(zhǎng)度編碼實(shí)現(xiàn)圖像壓縮，然后進(jìn)行游程長(zhǎng)度解碼和離散小波逆變換實(shí)現(xiàn)圖像恢復(fù)的方法．

1 離散小波變換

1．1 定義

一維離散小波的定義可由下式表示:

式(1)中，一般m，n取整數(shù)．為了便于計(jì)算機(jī)處理，對(duì)平移時(shí)間也進(jìn)行離散化處理，且保證小波函數(shù)生成的小波為標(biāo)準(zhǔn)正交基，選擇a0=2，b0=1，則得到二進(jìn)離散小波變換如下式所示:

習(xí)慣上簡(jiǎn)稱式(2)為離散小波變換．進(jìn)一步推廣可以得到二維離散小波變換．而且小波變換要可逆，即要存在逆變換．

1．2 特點(diǎn)

離散小波變換具有多分辨率(也叫多尺度)的特點(diǎn)，可由粗及細(xì)地逐步觀察信號(hào)．通過(guò)其定義式可以看出，其變換過(guò)程可以看成用基本頻率特性為ψ(ω)的帶通濾波器在不同尺度a下對(duì)信號(hào)進(jìn)行濾波處理．這樣，通過(guò)適當(dāng)?shù)剡x擇基小波，使ψ(t)在時(shí)域上為有限支撐，ψ(ω)在頻域上也比較集中，這樣就可以使小波變換在時(shí)域、頻域上都具有表征信號(hào)局部特征的能力，有利于檢測(cè)信號(hào)的瞬態(tài)或奇異點(diǎn)［5］．

借助于離散小波變換的這種分析工具，可將信號(hào)分解成許多具有不同的分辨率、頻率特性和方向特性的子帶信號(hào)，實(shí)現(xiàn)同時(shí)處理低頻長(zhǎng)時(shí)特征和高頻短時(shí)特征．而小波基，在關(guān)于伸縮平移的特性上與分形幾何的全局與局部的自相似性以及小尺度下的精細(xì)結(jié)構(gòu)間存在許多內(nèi)在的聯(lián)系［6］，這是本文中將離散小波變換與游程長(zhǎng)度編碼結(jié)合起來(lái)用于圖像壓縮與恢復(fù)的理論基礎(chǔ)．

因?yàn)槿魧?duì)圖像作j層離散小波分解，則小波分解的尺度a=2j．所以，當(dāng)離散小波變換用于圖像分解時(shí)，圖像的尺寸M×N必須滿足M=2p，N=2q(p，q∈1，2，…)，即圖像尺寸必須是2的整數(shù)次方．

2 游程長(zhǎng)度編碼與解碼

2．1 基本原理

游程長(zhǎng)度編碼是一種能夠有效消除或減小像素間冗余的編碼算法，僅存儲(chǔ)一個(gè)像素的灰度或顏色值以及具有相同灰度或顏色值的像素?cái)?shù)目，尤其是對(duì)某些相同灰度值成片連續(xù)出現(xiàn)的圖像非常有效．游程長(zhǎng)度編碼尤其適用于計(jì)算機(jī)生成的圖形圖像，對(duì)減少存儲(chǔ)容量效果明顯．

一幅圖像中往往有許多灰度或顏色相同的圖塊．在這些圖塊中，許多連續(xù)的掃描行都具有同一種灰度或顏色值，或者同一掃描行上有許多連續(xù)的像素都具有相同的灰度或顏色值．在這種情況下就可以不需要存儲(chǔ)每一個(gè)像素的顏色值，而僅僅存儲(chǔ)一個(gè)像素的灰度或顏色值以及具有相同灰度或顏色值的像素?cái)?shù)目．其壓縮率的大小取決于圖像本身．若圖像中具有相同灰度或顏色值的橫向色塊越大，則這樣的圖像塊數(shù)目越多，壓縮率就越大，反之就越小．

例如，一個(gè)數(shù)組為［10，10，10，24，24，33，33，33，33］，這個(gè)數(shù)組的長(zhǎng)度為 9 個(gè)數(shù)字，如果采用游程長(zhǎng)度編碼為［3，10，2，24，4，33］，則將長(zhǎng)度壓縮成了6個(gè)數(shù)字．因此，圖像中相鄰像素的灰度或顏色值越接近，壓縮的效果就越好，故游程長(zhǎng)度編解碼比較適合于此類圖像．但對(duì)于實(shí)際的場(chǎng)景圖片，例如另一個(gè)數(shù)組為［1，2，3，3，5，7，7，8，9］，這個(gè)數(shù)組的長(zhǎng)度也為 9 個(gè)數(shù)字，若采用游程編碼為［1，1，1，2，2，3，1，5，2，7，1，8，1，9］，則可以看到編碼后成了14個(gè)數(shù)字，比編碼前更長(zhǎng)，不但沒(méi)有壓縮效果，而且增加了冗余數(shù)據(jù)．解碼的過(guò)程相對(duì)容易，直接根據(jù)像素灰度或顏色值和對(duì)應(yīng)的個(gè)數(shù)一次性地填充到原來(lái)的圖像中去即可．

2．2 具體實(shí)現(xiàn)

經(jīng)典的游程長(zhǎng)度編碼是橫向掃描．本文以4張標(biāo)準(zhǔn)測(cè)試圖像 lena．bmp，dollar．bmp，bridge．bmp和aerial．bmp為例進(jìn)行實(shí)驗(yàn)仿真．編碼過(guò)程首先讀入圖像，圖像采用二維矩陣保存，每個(gè)像素的灰度作為矩陣對(duì)應(yīng)的取值．確定圖片尺寸就可以確定行、列循環(huán)的終點(diǎn)．讀取第一個(gè)像素的灰度值后開(kāi)始橫向掃描，掃描時(shí)若灰度值相同，則計(jì)數(shù)器加1，累計(jì)下去直到不相同灰度值的像素出現(xiàn)為止，此時(shí)計(jì)數(shù)器清0，保存新的灰度數(shù)值繼續(xù)進(jìn)行上述操作，直到整個(gè)圖像被掃描完畢．

解碼過(guò)程首先讀取編碼后的灰度值，根據(jù)相同灰度值的像素個(gè)數(shù)依次還原或者填充到解碼矩陣中．還愿一個(gè)像素計(jì)數(shù)器減1，直到計(jì)數(shù)器減為0，重新讀取一次新的灰度值分量和對(duì)應(yīng)的像素個(gè)數(shù)，一直進(jìn)行類似的操作，直到整個(gè)解碼矩陣填充完畢結(jié)束．從上述過(guò)程可以看出，關(guān)鍵的2個(gè)信息就是灰度值分量和掃描過(guò)程中相鄰相同灰度值的像素個(gè)數(shù)．這兩部分信息在編碼和解碼中起了至關(guān)重要的作用．

若要實(shí)現(xiàn)無(wú)損壓縮與恢復(fù)，則解碼矩陣必須和原始圖像完全一致．本文是對(duì)3層分解后的離散小波的圖像進(jìn)行編碼和解碼，因此，它屬于有損壓縮．

3 實(shí)驗(yàn)仿真與結(jié)果分析

3．1 實(shí)驗(yàn)仿真

為了檢驗(yàn)經(jīng)過(guò)離散小波變換和游程長(zhǎng)度編碼對(duì)圖像進(jìn)行壓縮和恢復(fù)的性能，本文選取了4張尺寸為512 ×512 的標(biāo)準(zhǔn)測(cè)試圖像 lena．bmp，dollar．bmp，bridge．bmp 和 aerial．bmp 的灰度圖像進(jìn)行 MATLAB實(shí)驗(yàn)仿真．實(shí)驗(yàn)仿真環(huán)境為:Intel?Dual-CoreTM2．00 GHz，CPU，1．50 GB RAM，MATLAB 7．8．0(R2009a)．

實(shí)驗(yàn)仿真結(jié)果見(jiàn)圖 1 ～ 圖8，圖1、圖3、圖5、圖 7 分別是測(cè)試圖像 lena．bmp，dollar．bmp，bridge．bmp和aerial．bmp的仿真結(jié)果，其中:(a)為原始圖像;(b)為經(jīng)過(guò)離散小波作3層分解后的圖像;(c)為經(jīng)過(guò)游程長(zhǎng)度編解碼且由離散小波逆變換后恢復(fù)的圖像;(d)為原始圖像與恢復(fù)圖像的誤差圖．圖2、圖4、圖 6、圖8 分別是 lena．bmp，dollar．bmp，bridge．bmp 和 aerial．bmp 圖像仿真結(jié)果圖對(duì)應(yīng)的直方圖，其中:(a)為原始圖像的直方圖;(b)為經(jīng)過(guò)離散小波作3層分解后的圖像的直方圖;(c)為經(jīng)過(guò)游程長(zhǎng)度編解碼且由離散小波逆變換后恢復(fù)的圖像的直方圖;(d)為原始圖像與恢復(fù)圖像的誤差圖的直方圖．

3．2 結(jié)果分析

從圖1及圖2可以看出，lena．bmp圖像由于灰度值相同且相鄰的像素點(diǎn)多，或者說(shuō)圖像的相鄰像素灰度值的相關(guān)性高，所以采用游程長(zhǎng)度編碼的情況下，編碼解碼情況良好，恢復(fù)圖像與原始圖像誤差較小，壓縮率也較高．

從圖3及圖4可以看出，dollar．bmp圖像由于灰度值相同且相鄰的像素點(diǎn)相對(duì)較少，或者說(shuō)圖像的相鄰像素灰度值的相關(guān)性低，所以采用游程長(zhǎng)度編碼的情況下，編碼解碼情況稍差，恢復(fù)的圖像與原始圖像的誤差偏大，壓縮率也較低．

圖1 測(cè)試圖像lena．bmp的仿真結(jié)果圖

圖2 測(cè)試圖像lena．bmp仿真結(jié)果圖的直方圖

圖3 測(cè)試圖像dollar．bmp的仿真結(jié)果圖

圖4 測(cè)試圖像dollar．bmp仿真結(jié)果圖的直方圖

從圖5及圖6可以看出，bridge．bmp圖像由于灰度值相同且相鄰的像素點(diǎn)相對(duì)更少，或者說(shuō)圖像的相鄰像素灰度值的相關(guān)性更低，所以采用游程長(zhǎng)度編碼的情況下編碼解碼情況更差，恢復(fù)的圖像與原始圖像的誤差更大，壓縮率也更低．

從圖7及圖8可以看出，aerial．bmp圖像與dollar．bmp圖像類似，由于灰度值相同且相鄰的像素點(diǎn)相對(duì)較少，或者說(shuō)圖像的相鄰像素灰度值的相關(guān)性低，所以采用游程長(zhǎng)度編碼的情況下編碼解碼情況稍差，恢復(fù)的圖像與原始圖像的誤差偏大，壓縮率也較低．

對(duì)標(biāo)準(zhǔn)測(cè)試圖像lena．bmp和dollar．bmp進(jìn)行壓縮與恢復(fù)的性能對(duì)比見(jiàn)表1;對(duì)標(biāo)準(zhǔn)測(cè)試圖像bridge．bmp和aerial．bmp進(jìn)行壓縮與恢復(fù)的性能對(duì)比見(jiàn)表2．

表1 標(biāo)準(zhǔn)測(cè)試圖像lena．bmp和dollar．bmp壓縮與恢復(fù)的性能對(duì)比

表2 標(biāo)準(zhǔn)測(cè)試圖像bridge．bmp和aerial．bmp壓縮與恢復(fù)的性能對(duì)比

從表1及表2可以看出:對(duì)標(biāo)準(zhǔn)測(cè)試圖像lena．bmp壓縮與恢復(fù)的性能明顯好于對(duì)標(biāo)準(zhǔn)測(cè)試圖像dollar．bmp，bridge．bmp和aerial．bmp的壓縮與恢復(fù)性能，前者壓縮率高，而且誤差小、耗時(shí)短，后面三者壓縮率低，誤差大、耗時(shí)長(zhǎng)．由此可以看出，該方法處理圖像像素灰度值相對(duì)集中和相關(guān)性高的圖像能取得較好的效果，但對(duì)于圖像像素灰度值相對(duì)分散和相關(guān)性差的圖像效果不是很理想．

4 結(jié)束語(yǔ)

本文提出將離散小波變換與游程長(zhǎng)度編解碼相結(jié)合實(shí)現(xiàn)圖像的壓縮與恢復(fù)的方法，通過(guò)對(duì)標(biāo)準(zhǔn)測(cè)試圖像 lena．bmp，dollar．bmp，bridge．bmp 和 aerial．bmp 進(jìn)行 MATLAB 實(shí)驗(yàn)仿真，證明了該方法的可行性，尤其是對(duì)于像lena．bmp這種像素灰度值相同且相關(guān)性高的圖像，不但能夠?qū)崿F(xiàn)較好的壓縮與恢復(fù)，而且具有壓縮率高、誤差小、耗時(shí)短等優(yōu)點(diǎn)．

與目前廣泛使用的JPEG算法相比較，本文提出的算法實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單，因?yàn)镴PEG算法中必須經(jīng)過(guò)顏色模式轉(zhuǎn)換及采樣、離散余弦變換(discrete cosine transform，DCT)、量化和編碼．當(dāng)然，本文的方法在處理像dollar．bmp，bridge．bmp和aerial．bmp這種像素灰度值相同且相鄰和相關(guān)性不高的圖像時(shí)，雖然能夠?qū)崿F(xiàn)壓縮與恢復(fù)，但性能有所下降，要提高對(duì)任意圖像的壓縮與恢復(fù)性能，需要進(jìn)一步研究改進(jìn)編解碼算法．

［1］趙婷婷．基于游程編碼的圖像處理系統(tǒng)設(shè)計(jì)［J］．經(jīng)營(yíng)管理者，2010(11):280．

［2］Haritaoglu I，Harwood D，Davis L S．W4:Real-time surveillance of people and their activities［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22(8):809-830．

［3］Tao Zhao，Nevatia R．Tracking multiple humans in complex situations［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(9):1208-1221．

［4］祝本明，劉桂華．基于小波游程編碼的改進(jìn)算法［J］．火力與指揮控制，2009，34(6):4-6．

［5］婁莉，劉天時(shí)．基于小波與分形相結(jié)合的圖像壓縮優(yōu)化算法［J］．微電子學(xué)與計(jì)算機(jī)，2010，27(6):145-148．

［6］Star k H G．Fractal graphs and wavelet series［J］．Physics Letters A，1990，143(9):443-447．