Wavelet Image Compression

Graphics and GPU Programming Programming

Started by Formski February 12, 2008 08:21 AM

3 comments, last by Formski 16 years, 1 month ago

138

Author

February 12, 2008 08:21 AM

Hi all, I am currently trying to implement a wavelet compressed image class (i.e. compress image using wavelets and store as such) in C++. I'm taking an original image, breaking it up into blocks of 256 x 256 coefficients (using 16 bit signed shorts here) and applying wavelet transforms on each block using the wavelet code below:


void cTerrainData::DWT(double *X, double *Y, int N)
{
	int n;
	for (n=0;n<N;n++)
		Y[n]=X[n];

	for (n=0;2*n+3<N;n++)
		Y[2*n+2]=X[2*n+2]+a*(X[2*n+1]+X[2*n+3]);		
	for (n=1;2*n+2<N;n++)
		Y[2*n+1]=X[2*n+1]+b*(Y[2*n]+Y[2*n+2]);
	for (n=0;2*n+3<N;n++)
		Y[2*n+2]=Y[2*n+2]+g*(Y[2*n+1]+Y[2*n+3]);
	for (n=1;2*n+2<N;n++)
		Y[2*n+1]=Y[2*n+1]+p*(Y[2*n]+Y[2*n+2]);
	for (n=0;2*n+2<N;n++)
		Y[2*n+2]=-K*Y[2*n+2];
	for (n=0;2*n+1<N;n++)
		Y[2*n+1]=(1/K)*Y[2*n+1];
}

and


void cTerrainData::IDWT(double *Y, double *X, int N)
{
	int n;
	for (n=0;n<N;n++)
		X[n]=Y[n];

	for (n=0;2*n+1<N;n++)
		X[2*n+1]=K*Y[2*n+1];
	for (n=0;2*n+2<N;n++)
		X[2*n+2]=-(1/K)*Y[2*n+2];
	for (n=1;2*n+2<N;n++)
		X[2*n+1]=X[2*n+1]-p*(X[2*n]+X[2*n+2]);
	for (n=0;2*n+3<N;n++)
		X[2*n+2]=X[2*n+2]-g*(X[2*n+1]+X[2*n+3]);
	for (n=1;2*n+2<N;n++)
		X[2*n+1]=X[2*n+1]-b*(X[2*n]+X[2*n+2]);
	for (n=0;2*n+3<N;n++)
		X[2*n+2]=X[2*n+2]-a*(X[2*n+1]+X[2*n+3]);
}

(note X and Y are declared and memory allocated before calling these methods) I have run into a problem however at each of the 'seams' where the 256x256 blocks meet. There is a run of between 1-4 pixel width lines spanning the entire seam when I spit out an output file of the decompressed image. Is there a way around this that anyone knows about? Thanks, Formski

Formski

138

Author

February 12, 2008 11:42 PM

As a follow up, I've found the problem seems to relate to my quantizevalue fed into the following code:

	// Quantize and write out data	for (int i=0; i < Width * Height;i++)	{		double v = 0;		if (dblData > QuantizeValue ||			dblData < -QuantizeValue)		{			if (dblData < 0)				v = -(-dblData / QuantizeValue);			else				v = dblData / QuantizeValue;		}		else		{			v = 0;		}				//assert(v<32768 && v > -32768);		RAWData = (short)v;// * QuantizeValue);	}

where QuantizeValue is an int, dblData is the Wavelet Coefficients in a Width x Height array of double numbers and RAWData is the final resultant data that will be passed to a coder.

When I set QuantizeValue to 1, there is no issue with the resultant output image. When I set QuantizeValue to 100 there is significant lines between each block. I'm guessing that it is related to the Wavelet transform on the border coefficients, but I'm at a bit of a loss on it.

Formski

Antheus

2,410

February 13, 2008 03:29 AM

Quote:Original post by Formski

When I set QuantizeValue to 1, there is no issue with the resultant output image. When I set QuantizeValue to 100 there is significant lines between each block. I'm guessing that it is related to the Wavelet transform on the border coefficients, but I'm at a bit of a loss on it.

Formski

I believe it's an off-by-one error.

for (n=0;2*n+3<N;n++)

This looks like a single pass across entire block. But when calculating the coefficients you don't take into account that although your image data is continuous, image itself isn't, and is composed of scanlines.

This means that right-most pixels will be calculated as difference between right-most and left-most-of-next-row pixels.

If you still choose to go with 256x256 initial blocks, then you'll need to handle edge cases specifically, either by padding an extra pixel to right and bottom, or by stopping one row and one column early.

Still, you could probably just feed your original image into compressor without breaking it up first. They you could just pad the up to nearest multiple of two, or terminate your pass early. This doesn't solve problem as such, but allows you a more uniform approach, the algorithm doesn't care about initial size.

Formski

138

Author

February 14, 2008 07:55 AM

Thanks Antheus,

That seems to have fixed the problem, at least for a single level wavelet decomposition.

I cheated by encoding (BlockDimension+2)x(BlockDimension+2) blocks (i.e. if wanting 256x256 blocks I encoded 258x258 blocks) then simply grabbed the inner 256x256 area for the output. The blocks obviously overlapped.

Now just to tidy up the additional level decompositions.

Formski

Formski

138

Author

February 26, 2008 06:44 AM

I stand corrected on this - the problem has not been resolved.

First off, the reason I am using 256x256 blocks is so that I can uncompress only those areas of the heightmap I want access too. This is because I want to feed it into a geoclipmap system, which means that I will only want subsections of the original image at any one time (centred around the viewer)

I have reverted back to my original sized blocks. What I am noticing is that the lines are appearing at the LHS of the block. When I decompress I find corrupted lines at column 256-258, 512-514 etc. The following is the new compression code:

void cTerrainData::DWT(double *X, double *Y, int wid, int hgt){	int n;	int y;	for (y=0;y<hgt;y++)	{		//filter_vector(&X[y*wid], &Y[y*wid], wid);		for (n=0;n<wid;n++)			Y[y*wid+n]=X[y*wid+n];		for (n=0;2*n+2<wid;n++)			Y[y*wid+2*n+2]=X[y*wid+2*n+2]+a*(X[y*wid+2*n+1]+X[y*wid+2*n+3]);		Y[y*wid]=X[y*wid]+a*(X[y*wid+1]+X[y*wid+1]);		for (n=1;2*n+1<wid;n++)			if (2*n+2 >= wid)				Y[y*wid+2*n+1]=X[y*wid+2*n+1]+2*b*(Y[y*wid+2*n]);			else				Y[y*wid+2*n+1]=X[y*wid+2*n+1]+b*(Y[y*wid+2*n]+Y[y*wid+2*n+2]);		for (n=0;2*n+2<wid;n++)			Y[y*wid+2*n+2]=Y[y*wid+2*n+2]+g*(Y[y*wid+2*n+1]+Y[y*wid+2*n+3]);		Y[y*wid]=Y[y*wid]+g*(Y[y*wid+1]+Y[y*wid+1]);		for (n=1;2*n+1<wid;n++)			if (2*n+2 >= wid)				Y[y*wid+2*n+1]=Y[y*wid+2*n+1]+2*p*(Y[y*wid+2*n]);			else				Y[y*wid+2*n+1]=Y[y*wid+2*n+1]+p*(Y[y*wid+2*n]+Y[y*wid+2*n+2]);				for (n=0;2*n+2<wid;n++)			Y[y*wid+2*n+2]=-K*Y[y*wid+2*n+2];		Y[y*wid]=-K*Y[y*wid];		for (n=0;2*n+1<wid;n++)			Y[y*wid+2*n+1]=(1/K)*Y[y*wid+2*n+1];	}}void cTerrainData::IDWT(double *Y, double *X, int wid, int hgt){	int n;	int y;	for (y=0;y<hgt;y++)	{		//inverse_filter_vector(&Y[y*wid], &X[y*wid], wid);		for (n=0;n<wid;n++)			X[y*wid+n]=Y[y*wid+n];				for (n=0;2*n+1<wid;n++)			X[y*wid+2*n+1]=K*Y[y*wid+2*n+1];				for (n=0;2*n+2<wid;n++)			X[y*wid+2*n+2]=-(1/K)*Y[y*wid+2*n+2];		X[y*wid]=-(1/K)*Y[y*wid];		for (n=1;2*n+1<wid;n++)			if (2*n+2 >= wid)				X[y*wid+2*n+1]=X[y*wid+2*n+1]-2*p*(X[y*wid+2*n]);			else				X[y*wid+2*n+1]=X[y*wid+2*n+1]-p*(X[y*wid+2*n]+X[y*wid+2*n+2]);		X[y*wid]=X[y*wid]-g*(X[y*wid+1]+X[y*wid+1]);		for (n=0;2*n+2<wid;n++)			X[y*wid+2*n+2]=X[y*wid+2*n+2]-g*(X[y*wid+2*n+1]+X[y*wid+2*n+3]);				for (n=1;2*n+1<wid;n++)			if (2*n+2 >= wid)				X[y*wid+2*n+1]=X[y*wid+2*n+1]-2*b*(X[y*wid+2*n]);			else				X[y*wid+2*n+1]=X[y*wid+2*n+1]-b*(X[y*wid+2*n]+X[y*wid+2*n+2]);		X[y*wid]=X[y*wid]-a*(X[y*wid+1]+X[y*wid+1]);		for (n=0;2*n+2<wid;n++)			X[y*wid+2*n+2]=X[y*wid+2*n+2]-a*(X[y*wid+2*n+1]+X[y*wid+2*n+3]);	}}

It seems to be the value of the far LHS column that is the issue (i.e. the y*wid values) The RHS seems fine so I suspect an error in my equations.

Anyone?

Formski

Wavelet Image Compression

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Wavelet Image Compression

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines