Sign in to follow this  

Wavelet Image Compression

This topic is 3581 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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[i] > QuantizeValue ||
dblData[i] < -QuantizeValue)
{
if (dblData[i] < 0)
v = -(-dblData[i] / QuantizeValue);
else
v = dblData[i] / QuantizeValue;
}
else
{
v = 0;
}

//assert(v<32768 && v > -32768);
RAWData[i] = (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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

This topic is 3581 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this