(黃淮學(xué)院信息工程學(xué)院，河南駐馬店，463000)

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

魏長寶

(黃淮學(xué)院信息工程學(xué)院，河南駐馬店，463000)

在眾多數(shù)字圖像的壓縮編碼技術(shù)中，變位壓縮編碼技術(shù)是基于動(dòng)態(tài)規(guī)劃算法，它可高效解決許多算法無法解決的問題。在用動(dòng)態(tài)規(guī)劃算法解決實(shí)際問題時(shí)，把相互關(guān)聯(lián)的重疊子問題只求解一次，把其狀態(tài)存入一個(gè)二維表中，如果有相同或相似的問題可以直接從二維表中取出結(jié)果，減少了重復(fù)，提高了效率。

動(dòng)態(tài)規(guī)劃算法；數(shù)字圖像；變位壓縮技術(shù)

0 引言

在航天、航海、軍事、醫(yī)療、氣象技術(shù)日益發(fā)展的今天，微電子、計(jì)算機(jī)、傳感器和多媒體數(shù)字化技術(shù)等呈現(xiàn)突飛猛進(jìn)的態(tài)勢(shì)。數(shù)字圖像信息的存儲(chǔ)、傳送、顯示等技術(shù)也獲得了極大的成功。但是，如果我們直接把未經(jīng)任何加工、處理的大量圖像數(shù)據(jù)直接進(jìn)行交換和存儲(chǔ)，那么，數(shù)據(jù)的大小還是會(huì)遠(yuǎn)遠(yuǎn)超出已有的存儲(chǔ)技術(shù)和網(wǎng)絡(luò)帶寬。于是，人們希望在有限的空間和帶寬資源上，存儲(chǔ)和傳輸?shù)拇罅繑?shù)字圖像信息的質(zhì)量、大小和應(yīng)用能夠有所提高。于是，圖像壓縮編碼技術(shù)得到了應(yīng)用。通過提高圖像數(shù)據(jù)壓縮效率，對(duì)圖像進(jìn)行壓縮，使圖像數(shù)據(jù)大大減小。再根據(jù)不同的實(shí)際需要，通過一定的重構(gòu)技術(shù)，獲得不同分辨率或質(zhì)量的圖像。顯然，數(shù)字圖像壓縮技術(shù)有著廣闊的發(fā)展前景和重大的實(shí)用價(jià)值。

1 變位壓縮算法的提出

解決圖像占用空間和通信信道帶寬大的的問題，是解決制約圖像應(yīng)用問題的當(dāng)務(wù)之急。變位壓縮算法是基于動(dòng)態(tài)規(guī)劃算法，動(dòng)態(tài)規(guī)劃算法適于求最優(yōu)化問題，它建立在最優(yōu)原則基礎(chǔ)上，解決許多算法無法解決的難題。從理論上講，任何拓?fù)溆行虻碾[式圖中的搜索算法都可以改寫成動(dòng)態(tài)規(guī)劃算法。將問題的大實(shí)例變換為等價(jià)的最優(yōu)化小實(shí)例，自底向上遞推求解，把求出的最小實(shí)例的解存為備用數(shù)據(jù)，將一系列決策的結(jié)果作為一個(gè)問題的解決方案。每個(gè)最優(yōu)決策序列包含一系列最優(yōu)子序列，先求解子問題，然后從這些子問題的解得到原問題的解。適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是相互獨(dú)立的。

數(shù)字圖像壓縮采用動(dòng)態(tài)規(guī)劃算法雖然是一種高效率算法，但是，在數(shù)字化圖像存儲(chǔ)中，如果每個(gè)像素都至少用8位二進(jìn)制數(shù)存儲(chǔ)表示，那么，一個(gè)m×m像素陣列的數(shù)字化圖像，一個(gè)像素的灰度值范圍為0～255，如果采用定長存儲(chǔ)模式，需要8×m2位的存儲(chǔ)空間。巨大的存儲(chǔ)容量和通信帶寬的占用，給存儲(chǔ)空間和數(shù)字圖像信息傳輸效率帶來了不小的壓力。況且動(dòng)態(tài)規(guī)劃算法是多步驟策略，每個(gè)階段形成的決策結(jié)果，組合成一個(gè)決策結(jié)果序列，其中，最終的最優(yōu)結(jié)果取決于以后每個(gè)階段的決策，當(dāng)然，由于決策過程的每階段結(jié)果序列都必須進(jìn)行存儲(chǔ)。因此，直接進(jìn)行動(dòng)態(tài)規(guī)劃又是“高消費(fèi)”的算法。

假如，我們將不同的像素采用不同的位數(shù)，以變長的存儲(chǔ)模式存儲(chǔ)。如像素值為0，1，用1位存儲(chǔ)；值為2，3用2位存儲(chǔ)，……像素值為128，……，255等時(shí)用8位，依此類推。那么，采用變位壓縮存儲(chǔ)算法模式，不同的圖像用不同的位數(shù)進(jìn)行壓縮存儲(chǔ)，可以大大節(jié)約存儲(chǔ)空間。“高效率、高消費(fèi)”的動(dòng)態(tài)規(guī)劃算法就會(huì)成為弱化“高消費(fèi)”，強(qiáng)化“高效率”的基于動(dòng)態(tài)規(guī)劃的變位壓縮算法。

2 變位壓縮算法分析

真實(shí)世界的場(chǎng)景中，數(shù)字圖像包含著廣泛的像素點(diǎn)灰度值范圍，在計(jì)算機(jī)中常用{p1,p2,…,pn}序列表示。其中，整數(shù)Pi(1≤i≤n)表示像素點(diǎn)i的灰度值。通常圖像像素點(diǎn)的灰度值在0～255的范圍內(nèi)，因此，用8位二進(jìn)制表示一個(gè)像素點(diǎn)就可以了。

一個(gè)相對(duì)比較標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)，一般分以下幾個(gè)步驟：

(1)劃分階段：把問題按照時(shí)間或空間特征，分為若干個(gè)有序的或者可排序的(即無后向性)階段。

(2)選擇狀態(tài)：用各種不同的狀態(tài)，表示各個(gè)發(fā)展階段所處的各種滿足無后效性情況。

(3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：決策一旦確立，狀態(tài)轉(zhuǎn)移方程就出來了，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)，它們兩者既獨(dú)立又緊密聯(lián)系。實(shí)際上，我們是根據(jù)相鄰兩狀態(tài)間的關(guān)系來確定決策。

(4)寫出規(guī)劃方程(包括邊界條件)：用通用形式化表達(dá)式表示動(dòng)態(tài)規(guī)劃的基本方程。

在實(shí)際應(yīng)用中，動(dòng)態(tài)規(guī)劃算法適用于解最優(yōu)化問題，一般不用顯式方法表述，而是按以上步驟歸納如下：

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

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

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

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

圖像的變位壓縮存儲(chǔ)格式將所給的像素點(diǎn)序列{p1,p2,…,pn}分割成m個(gè)連續(xù)段S1,S2,…,Sm。第i個(gè)像素段Si(1≤i≤m)中，有l(wèi)[i]個(gè)像素，且該段中每個(gè)像素都只用b[i]位表示。設(shè)t[i]=，1≤i≤m，則第i個(gè)像素段Si為：

設(shè)hi=，則hi≤b[i]≤8。因此需要用3位表示b[i]，1≤i≤m，如果限制1≤l[i]≤255，則需要8為表示l[i]，1≤i≤m。因此，第i個(gè)像素所需的存儲(chǔ)空間為：l[i]*b[i]+11位。按此格式存儲(chǔ)像素序列{p1,p2,…,pn}，需要位的存儲(chǔ)空間。

3 變位壓縮算法設(shè)計(jì)

根據(jù)圖像壓縮的要求，對(duì)圖像{p1,p2,…,pn} (0≤pi≤256,1≤i≤n)像素序列最優(yōu)分段，其中，每個(gè)分段的長度不超過256位，所需存儲(chǔ)空間最少。據(jù)此思路設(shè)計(jì)步驟如下：

(1)子結(jié)構(gòu)性質(zhì)

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

(2)遞歸計(jì)算最優(yōu)值

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

S[i]= ,式中，bmax(i,j)=[]

根據(jù)分析設(shè)計(jì)圖像壓縮的動(dòng)態(tài)規(guī)劃算法如下：

static final int lmax=256;

static final int header=11;

static intm;

public static void compress(int p[],int s[],int 1[],int b[])

{

int i,j,bmax,n=p.length-1;

s[0]=0;

for(i=1;i<=n;i++) {

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

bmax=b[i];

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

l[i]=1;

for(j=2;j<=i &&j<=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;

}

}

4 最優(yōu)解構(gòu)造

算法compress中用l[i]，b[i]記錄了最優(yōu)分段所需的信息。最優(yōu)分段的最后一段的段長度和像素位數(shù)分別存儲(chǔ)丁l[n]，b[n]中。取前一段的段長度和像素位數(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];

}

public static void output(int s[],int l[],int b[])

{

int n=s.length-1;

System.out.println(“The optimal value is”+s[n]);

m=O;

traceback(n,s,l);

System.out.println (“Decomposed into”+m+”segments”);

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

l[j]=l[s[j]];

b[j]=bs[j]];

}

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

System.out.println(l[j]+”,”+b[j]);

}

5 結(jié)束語

圖像信息在使用中，經(jīng)常占用通信和計(jì)算機(jī)大量的資源，如何對(duì)圖像進(jìn)行有效壓縮，提高和節(jié)省計(jì)算機(jī)資源，既是我們不斷追求的目標(biāo)，也是一直研究和探討的問題。實(shí)事證明，采用基于動(dòng)態(tài)規(guī)劃算法的變位壓縮技術(shù)，可以達(dá)到圖像“瘦身”的不錯(cuò)效果，也是一種有效的方法。

[1] SahaS.Image Compression from DCT to Wavalets[J]. AReview ACM Crossroads Student Magazine. 2000, 6.

[2] Kenneth R Castlema n.數(shù)字圖像處理[M].北京: 清華大學(xué)出版社,2001.

[3] 趙楠楠等.基于小波變換和 SVM 的圖像壓縮仿真研究[J].系統(tǒng)仿真學(xué)報(bào),2006,18(11):3034-3037.

[4] 王曉東.算法設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社,2O10．

Compression technology based on dynamic programming algorithm digital image displacement

Wei Changbao
(Information Engineering College of Huanghuai University,Zhumadian，463000,china,)

In many digital image compression technology,the displacement compression coding technology is based on dynamic programming algorithm that can efficiently solve many algorithms can not solve the problem. When using a dynamic programming algorithm to solve practical problems,the overlapping sub-problem solving interrelated only once,put their state into a two-dimensional table,if you have the same or similar problems can be taken directly from the results of a two-dimensional table,reducing duplication and improve efficiency.

dynamic programming algorithm;digital image;displacement compression technology

TP391.41

A

魏長寶(1972—)，男，漢，碩士，副教授.主要研究方向：數(shù)據(jù)挖掘與信息技術(shù)