基于動(dòng)態(tài)規(guī)劃法的數(shù)字圖像壓縮算法研究

［摘要］文章論述用動(dòng)態(tài)規(guī)劃算法對(duì)數(shù)字圖像進(jìn)行壓縮的基本原理和步驟，給出動(dòng)態(tài)規(guī)劃算法，并對(duì)該算法進(jìn)行分析和探討。

［關(guān)鍵詞］動(dòng)態(tài)規(guī)劃算法；數(shù)字圖像；遞歸；壓縮

［作者簡(jiǎn)介］畢傳林，九江職業(yè)技術(shù)學(xué)院計(jì)算機(jī)教研室講師，研究方向：計(jì)算機(jī)軟件，江西九江， 332007；陳禮芳，九江職業(yè)技術(shù)學(xué)院信息中心實(shí)驗(yàn)師，研究方向：計(jì)算機(jī)應(yīng)用，江西九江， 332007；陳小秀，江西財(cái)經(jīng)大學(xué)碩士研究生 ，江西南昌，330013

［中圖分類號(hào)］ TP391.41［文獻(xiàn)標(biāo)識(shí)碼］ A［文章編號(hào)］ 1007-7723（2008）08-0047-0002

一、問題的提出

動(dòng)態(tài)規(guī)劃建立在最優(yōu)原則基礎(chǔ)上，它可高效解決許多算法無法解決的問題。在動(dòng)態(tài)規(guī)劃中，可將一個(gè)問題解決方案視為一系列決策的結(jié)果。每個(gè)最優(yōu)決策序列包含一系列最優(yōu)子序列。動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干個(gè)子問題。先求解子問題，然后從這些子問題的解得到原問題的解。對(duì)于適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是相互獨(dú)立的。動(dòng)態(tài)規(guī)劃算法適用于求最優(yōu)化問題。

數(shù)字圖像往往占用大量空間，在數(shù)字通信中占用大量信道帶寬，一直是通信過程的瓶頸，為了節(jié)省空間，提高數(shù)據(jù)傳輸效率，非常有必要對(duì)圖像進(jìn)行相應(yīng)的壓縮處理。

設(shè)一個(gè)數(shù)字化圖像是m×m的像素陣列，且每個(gè)像素有0~255的灰度值，那么存儲(chǔ)一個(gè)像素則至少需8位二進(jìn)制，若每個(gè)像素存儲(chǔ)都用8位表示，則總的存儲(chǔ)空間為8×m2位。為了減少存儲(chǔ)空間，我們將像素采用變長(zhǎng)存儲(chǔ)模式，即不同的像素用不同的位數(shù)來存儲(chǔ)。如像素值為0，1，則只需1位存儲(chǔ)；值為2，3，各需2位，……像素值為128，160，187，200等時(shí)需8位，依此類推。采用這種變長(zhǎng)的存儲(chǔ)模式，可以達(dá)到節(jié)省存儲(chǔ)空間的目的。

二、算法分析

設(shè)用像素點(diǎn)表示圖像的灰度值的序列{p1，p2…pn}。其中整數(shù)pi，1≤i≤n，表示像素點(diǎn)的灰度值。通?；叶戎档姆秶?～255。因此，需要用8位二進(jìn)制表示像素。

采用動(dòng)態(tài)規(guī)劃設(shè)計(jì)算法時(shí)，通常可以按以下步驟設(shè)計(jì)：

1.找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；

2.遞歸的定義最優(yōu)值；

3.以自底向上的方式計(jì)算出最優(yōu)值；

4.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。

三、算法設(shè)計(jì)

圖像壓縮問題要求確定像素序列{p1，p2…pn}的最優(yōu)分段，使得依此分段所需的存儲(chǔ)空間最少。其中，0?燮pi?燮256，1?燮i?燮n。每個(gè)分段的長(zhǎng)度不超過256位。根據(jù)以上思路步驟如下：

（一）子結(jié)構(gòu)性質(zhì)

設(shè)l[i]，b[i]，1≤i≤m是{p1，p2…pn}的最優(yōu)分段。顯而易見，l[i]，b[i]是{p1，…pl[1]}的最優(yōu)分段，且l[i]，b[i]，2≤i≤m是{pl[1]+1，…pn}的最優(yōu)分段。即圖像壓縮問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。

（二）遞歸計(jì)算最優(yōu)值

設(shè)s[I]，1?燮i?燮n是圖像序列{p1，p2…pi}的最優(yōu)分段所需的存儲(chǔ)位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)而知：

int lmax=256;

int header=11;

int m;

void compress(int p[]，int n，int s[]，int l[]，int b[])

{ int i，j，bmax;

s[0]=0;

for(i=1;i

{

b[i]=lenth(p[i]);

bmax=b[i];

s[i]=s[i-1]+bmax;

l[i]=1;

for(j=2;j<=ij<=lmax;j++

{

if(bmax

if(s[i]>s[i-j]+j*bmax)

{

s[i]=s[i-j]+j*bmax;

l[i]=j;

}

}

s[i]+=header;

}

}

int lenth(int i)

{ int k=1;

i=i/2;

while(i>0)

{ k++;

i=i/2;

}

return k;

}

（三）構(gòu)造最優(yōu)解

算法compress中用l[i]， b[i]記錄了最優(yōu)分段所需的信息。最優(yōu)分段的最后一段的段長(zhǎng)度和像素位數(shù)分別存儲(chǔ)于l[n]，b[n] 中。取前一段的段長(zhǎng)度和像素位數(shù)存儲(chǔ)于l[n-l[n]]和b[n-l[n]]中，依此類推。由算法計(jì)算出的l和b可在O(n)時(shí)間內(nèi)構(gòu)造出相應(yīng)的最優(yōu)解，具體算法可實(shí)現(xiàn)如下：

void traceback(int n，int s[ ]，int l[ ])

{

if(n==0) return ;

traceback(n-l[n]，s，l);

s[m++]=n-l[n];

}

void output(int s[ ]，int lenth，int l[ ]，int b[ ])

{

int n=lenth-1，j;

printf(\"The optimal value is%d \"，s[n]);

m=0;

traceback(n，s，l);

printf(\"Decomposed into%d segments\" ，m);

for(j=1;j<=m;j++)

printf(\"%d，%d\\"，l[j]，b[j]);

}

四、結(jié)語

在通信和計(jì)算機(jī)中，圖像信息經(jīng)常占用了大量的資源，如何對(duì)圖像信息進(jìn)行有效的“瘦身”，達(dá)到提高通信效率和節(jié)省計(jì)算機(jī)的存儲(chǔ)空間的目的，一直是一個(gè)值得研究和探討的問題。實(shí)踐證明，采用動(dòng)態(tài)規(guī)劃法進(jìn)行圖像的壓縮，壓縮率可以達(dá)到不錯(cuò)的效果。因此，采用動(dòng)態(tài)規(guī)劃法對(duì)圖像進(jìn)行壓縮是一種有效的方法。

［參考文獻(xiàn)］

［1］王曉東.算法設(shè)計(jì)與分析［M］.北京:清華大學(xué)出版社，2003.

［2］姚新，陳國(guó)良，等.進(jìn)化算法研究進(jìn)展［J］.計(jì)算機(jī)學(xué)報(bào)，1995，18(9).

［3］盧開澄.計(jì)算機(jī)算法導(dǎo)引［M］.北京:清華大學(xué)出版社，1998.