图象压缩.cpp

算法分析部分

#include<iostream>
using namespace std;
/*
在计算机中常用象素点灰度值序列{p1,p2,...,pn}表示图象。其中整数pi,1<=i<=n,表示象素
点i的灰度值。通常灰度值的范围是0~255。因此，需要用8位表示一个象素。

图象的变位压缩存储格式将所给的像素点序列{p1,p2,...,pn}分割成m个连续段S1,S2,...,Sm。
第i个像素段Si中(1<=i<=m)，有l[i]个像素，且该段中每个像素都只用b[i]位来表示。设
t[i]={1<=k<=i-1}l[k]{1<=i<=m}，则第i个像素段Si为：
Si = { p(t[i]+1),...,p(t[i]+l[i]) },1<=i<=m
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}需要{1<=i<=m}l[i]*b[i] + 11*m位的存储空间。
图象压缩问题要求确定像素序列{p1,p2,...,pn}的一个最优分段，使得依此分段所需的存储空间最少。
其中，0<=pi<=256,1<=i<=n,每个分段的长度不超过256位。
*/

/*
最优子结构：
设l[i],b[i],1<=i<=m是{p1,p2,...,pn}的一个最优分段。显而易见，l[1]，b[1]是
{p1,...,pl[1]}的一个最优分段，且l[i],b[i],2<=i<=m是{pl[1]+1,...,pn}的一个最
优分段。即图象压缩问题满足最优子结构性质。
*/

/*
递归计算最优值：
设s[i],1<=i<=n是像素序列{p1,...,pi}的最优分段所需的存储位数。由最优子结构性质易知：
s[i] = MIN{1<=k<=min(i,256)}{s[i-k]+k*bmax(i-k+1,i)}+11
*/

void Compress( int n, int p[], int s[], int l[], int b[] )
{
	int Lmax = 256,header = 11;
	s[0] = 0;
	for( int i = 1; i <= n; ++i )
	{
		b[i] = length(p[i]);
		int bmax = b[i];
		s[i] = s[i-1] + bmax;
		l[i] = 1;
		for( int j = 2; j <= i && j <= Lmax; ++j )
		{
			if ( bmax < b[i-j+1] )
			{
				bmax = b[i-j+1];
			}
			if ( s[i] > s[i-j] + j * bmax )
			{
				s[i] = s[i-j] + j * bmax;
				l[i] = j;
			}
		}
		s[i] += header;
	}
}

int length( int i )
{
	int k = 1;
	i = i / 2;
	while( i > 0 )
	{
		++k;
		i /= 2;
	}
	return k;
}

void Traceback( int n, int& i, int s[], int l[] )
{
	if ( n == 0 )
	{
		return;
	}
	Traceback( n - l[n], i, s, l );
	s[i++] = n - l[n];
}

void OutPut( int s[], int l[], int b[], int n )
{
	cout<<"the optimal value is "<<s[n]<<endl;
	int m = 0;
	Traceback( n, m, s, l );
	s[m] = n;
	cout<<"Decompose into "<<m<<"segments"<<endl;
	for( int j = 1; j <= m; ++j )
	{
		l[j] = l[s[j]];
		b[j] = b[s[j]];
	}
	for( int j = 1; j <= m; ++j )
	{
		cout<<l[j]<<' '<<b[j]<<endl;
	}
}
int main()
{
	return 0;
}