Discrete Wavelet Transform on images and watermark embedding in LL band coefficients, data is lost when IDWT-DWT is performed again?

Question

0.00/5 (No votes)

See more:

0 down vote favorite

I'm writing an image watermarking system to hide a watermark in an image's low frequency band by transforming the image's luminance channel with a Discrete Wavelet Transform, then modifying coefficients in the LL band of the DWT output. I then do an Inverse DWT and rebuild my image.

The problem I'm having is when I modify coefficients in the DWT output, then inverse-DWT, and then DWT again, the modified coefficients are radically different.

For example, one of the output coefficients in the LL band of the 2-scale DWT was -0.10704, I modified this coefficient to be 16.89, then performed the IDWT on my data. I then took the output of the IDWT and performed a DWT on it again, and my coefficient which was modified to be 16.89 became 0.022.

I'm fairly certain that the DWT and IDWT code is correct because I've tested it against other libraries and the output from each transform matches when the filter coefficients and other parameters are the same. (Within what can be expected due to rounding error)

The main problem I have is that I perhaps don't understand the DWT all that well, I thought DWT and IDWT were supposed to be reasonably lossless (Aside from rounding error and such), yet this doesn't seem to be the case here.

I'm hoping someone more familiar with the transform can point me at a possible issue, is it possible that because the coefficients in my other subbands (LH, HL, HH) for that position are insignificant I'm losing data? If so, how can I determine which coefficients this may happen to?

I can post pieces of code if it will be helpful but the entire embedding process is several hundred lines and doesn't really seem relevant to the question as I've tested modifying the array of coefficients by hand, then doing the IDWT on it, then doing a DWT again, and the coefficients I modified are different.

Posted 12-Jul-11 13:08pm

Member 7912941

Updated 13-Jul-11 7:37am

v2

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

TRK3 · Answer 1 · 2011-07-12T14:09:00

Solution 1

I'm not that familiar with IDWT/DWT either.

But from what I know IDWT - DWT is not a strictly loss-less conversion.

Here's a somewhat approachable reference:

http://polyvalens.pagesperso-orange.fr/clemens/wavelets/wavelets.html[^]

For your purposes the key point is that the DWT is essentially a band-pass filter. It throws away frequency information that is above or below certain limits. If all your data is within the frequency band, then the conversion is reasonablly reversible (within the limits of sampling and rounding). Any data outside that frequency band is lost.

It's pretty obvious if you made a huge change to one pixel in the original image you'd have introduced a very high frequency component which would get thrown away. (Much as happens when you save a jpeg image.)

Similarly when you are making a huge change in the wavelet domain, you've just added a huge amount of energy at a single wavelet frequency and when you transform that back into the space domain, that energy probably gets lost off the edges of your image, so that not all your information is retained.

I guess theoretically you could increase the size (number of wavelets) of the DWT / IDWT so that the bandwidth of your transform is large enough to handle the magnitude of changes you are making, but I don't have any good intuition about how big it would have to be.

Posted 12-Jul-11 14:09pm

TRK3

Comments

Member 7912941 13-Jul-11 13:36pm

Thanks for the insight, I'll have a look at the reference as well, I had considered this, and I've tried making smaller changes, for example, the mean value of the other 3 bands at a certain location is ~45, so I changed the LL band coefficient for that location to 18, and still it was lost, even though that is clearly not outside the frequency range I'm expecting.

The amount I modify a coefficient by does not seem to be relevant, even relatively minor changes to coefficient values seem to be lost and this is what confuses me most.

TRK3 13-Jul-11 14:43pm

Hmmm...

It's been too long since I dealt with math at that level, I'd need to read up on it more.

If you google:

http://www.google.com/search?q=applying+watermark+in+the+discrete+wavelet+domain&sourceid=ie7&rls=com.microsoft:en-us:IE-SearchBox&ie=&oe=

You get a bunch of references of people who are doing something similar. I looked at a couple of them briefly. The first link:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.66.1361&rep=rep1&type=pdf

sounds like they are doing something very similar. In that case they are embedding watermarks in several different bands of the transform. On page 5 of the paper they show the result of extracting the watermark back out. They seem to be able to get back the LL band watermark exactly -- the watermarks in the other bands don't come back exactly, but come back slightly degraded. So, it looks like in some bands with at least some transforms, you won't expect the process to be lossless.

It looks like all the watermarking techniques are modifying a bunch of coefficients is some recognizable way and then using a statistcal method of recognizing the watermark rather than relying on a single coefficient to come back the same way.

I don't know if they are doing that because they expect some loss in the tranform process, or if they are doing that because they want to still identify the watermark even if the image has undergone lossy compression or been re-scaled or color balanced, or...

Member 7912941 13-Jul-11 16:04pm

I did extensive research before writing this, I read the paper you linked and many others, I'm of course not relying on a single coefficient, I'm embedding a 32x32 (1 bit per pixel) image as a binary watermark in 1024 coefficients in the LL band, the problem I have is that MANY of the coefficients change or are zeroed and this makes it impossible to retrieve the mark, I'm seeing less than 50% correlation in some cases, and never over 60%, since this is 1 bit I have to assume a ~50% correlation out of an image with no watermark present since each position has a 50/50 chance of being extracted with the watermark value.

TRK3 13-Jul-11 16:25pm

Damn... Seems like you are doing the right thing.

Which seems to bring us back to the DWT / IDWT implementation itself.

You mentioned you compared your DWT against other library implementations, can you substitute those library implementations for yours in your watermarking algorithm to see if the minor discrepencies are actually significant?

Is there a different DWT (different coefficient length, different wavelet, ... ?) that gives better results?

Not sure I can be much help at this point.

Let me know when you figure out what the problem was.

Member 7912941 13-Jul-11 17:27pm

Unfortunately the other wavelet implementations I have are in C++ or Java, whereas my code is all C#, I could use the C++ as a library I suppose, though I was hoping to avoid having to do that.

I could change the wavelet filter, I've tried a few different ones but haven't seen much of a difference...what do you mean by difference coefficient length? the number of coefficients I get is tied to the wavelet I use as well as the scale of the transform, but I'm only using a 2 scale transform here and increasing the number of decompositions generally reduces the number of coefficients, I'm not aware of how to increase it?

TRK3 13-Jul-11 20:54pm

I meant higher frequency resolution, or longer transform (synonymous concepts I think), but I don't think that's really your issue.

Can you do a test with one of the other implementations? If you have some sort of existing DWT / IDWT utility you could manually do the DWT, the change the coefficients by hand and do the IDWT and see if the utility exhibits the same phenonmenon or not -- then at least you know if there is something odd about your DWT / IDWT implementation or if the problem is something else.