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

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

魏長寶

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

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

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

0 引言

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

1 變位壓縮算法的提出

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

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

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

2 變位壓縮算法分析

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

一個相對比較標準的動態(tài)規(guī)劃算法的設(shè)計，一般分以下幾個步驟：

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

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

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

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

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

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

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

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

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

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

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

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

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

(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)遞歸計算最優(yōu)值

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

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

根據(jù)分析設(shè)計圖像壓縮的動態(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ù)分別存儲丁l[n]，b[n]中。取前一段的段長度和像素位數(shù)存儲于l[n-l[n]] b[n-l[n]]中，依此類推。由算法計算出的l和b可在O(n)時間內(nèi)構(gòu)造出相應(yīng)的最優(yōu)解，具體算法可實現(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)常占用通信和計算機大量的資源，如何對圖像進行有效壓縮，提高和節(jié)省計算機資源，既是我們不斷追求的目標，也是一直研究和探討的問題。實事證明，采用基于動態(tài)規(guī)劃算法的變位壓縮技術(shù)，可以達到圖像“瘦身”的不錯效果，也是一種有效的方法。

[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é)報,2006,18(11):3034-3037.

[4] 王曉東.算法設(shè)計與分析[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ù)