基于動態規劃算法的數字圖像變位壓縮技術探究

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

基于動態規劃算法的數字圖像變位壓縮技術探究

魏長寶

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

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

動態規劃算法；數字圖像；變位壓縮技術

0 引言

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

1 變位壓縮算法的提出

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

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

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

2 變位壓縮算法分析

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

一個相對比較標準的動態規劃算法的設計，一般分以下幾個步驟：

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

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

(3)確定決策并寫出狀態轉移方程：決策一旦確立，狀態轉移方程就出來了，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態，它們兩者既獨立又緊密聯系。實際上，我們是根據相鄰兩狀態間的關系來確定決策。

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

在實際應用中，動態規劃算法適用于解最優化問題，一般不用顯式方法表述，而是按以上步驟歸納如下：

(1)找出最優解的性質，并刻畫其結構特征；

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

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

(4)根據計算最優值時得到的信息，構造最優解。

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

設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 變位壓縮算法設計

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

(1)子結構性質

設l[i]，b[i]，1≤i≤m是{p1,p2,…,pn}的最優分段。顯而易見，l[i]，b[i]是{p1,…,pl[i]}的最優分段，且l[i]，b[i]，2≤i≤m是{pl[i]+1…pn}的最優分段。即圖像壓縮問題滿足最優子結構性質。

(2)遞歸計算最優值

設圖像最優分段序列{p1,p2,…,pi}所需的存儲位數Si(1≤i≤n)。由最優子結構性質而知：

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

根據分析設計圖像壓縮的動態規劃算法如下：

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 最優解構造

算法compress中用l[i]，b[i]記錄了最優分段所需的信息。最優分段的最后一段的段長度和像素位數分別存儲丁l[n]，b[n]中。取前一段的段長度和像素位數存儲于l[n-l[n]] b[n-l[n]]中，依此類推。由算法計算出的l和b可在O(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 結束語

圖像信息在使用中，經常占用通信和計算機大量的資源，如何對圖像進行有效壓縮，提高和節省計算機資源，既是我們不斷追求的目標，也是一直研究和探討的問題。實事證明，采用基于動態規劃算法的變位壓縮技術，可以達到圖像“瘦身”的不錯效果，也是一種有效的方法。

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

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

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

[4] 王曉東.算法設計與分析[M].北京:清華大學出版社,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—)，男，漢，碩士，副教授.主要研究方向：數據挖掘與信息技術