基于动态规划算法的数字图像变位压缩技术探究

(黄淮学院信息工程学院，河南驻马店，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—)，男，汉，硕士，副教授.主要研究方向：数据挖掘与信息技术