Compression - Wavelets and Reflection image question

Author

Wavelets and Reflection image question

Jerzie.Klenchier@gmail.com

2008-03-25, 7:56 am

Hi all,

I've recently begun trying to understand the fundamentals of
lossy image compression via transforms such as DCT and Wavelets
(CDF9/7).

In a paper I was reading it suggested that prior to applying a
forward transform that a "reflection image" of the original image
be created.

This involves flipping the image vertically and horizontally and
copy those flipped variants above, below and to the left and right
hand-side, ending up with a larger image that is 3xwidth and 3xheight
of the original. then applying the forward transform and then the
inverse transform leads to a much higher PSNR than when the image
itself is forward then inverse transformed.

My questions are:

1. What is this method called? as I can't find anything else in the
literature I have that comments about this

2. Why does it provide a better result? is this some kind of Gibbs
effect on the border areas? I find that a great deal of the nose
when only using the original image comes from around the borders.

Any help would be greatly appreciated,

Rgds,

Jerzie

Thomas Richter

2008-03-25, 6:57 pm

Jerzie.Klenchier@gmail.com wrote:
> Hi all,
>
> I've recently begun trying to understand the fundamentals of
> lossy image compression via transforms such as DCT and Wavelets
> (CDF9/7).
>
> In a paper I was reading it suggested that prior to applying a
> forward transform that a "reflection image" of the original image
> be created.
>
> This involves flipping the image vertically and horizontally and
> copy those flipped variants above, below and to the left and right
> hand-side, ending up with a larger image that is 3xwidth and 3xheight
> of the original. then applying the forward transform and then the
> inverse transform leads to a much higher PSNR than when the image
> itself is forward then inverse transformed.
>
> My questions are:
>
> 1. What is this method called? as I can't find anything else in the
> literature I have that comments about this

Dependent on how precisely the flipping is done, this is called WSS or
HSS (whole sample symmetric resp. half sample symmetric) extensions. For
the odd-length wavelets in JPEG2000 (CDF9/7,5/3), you need the WSS.

> 2. Why does it provide a better result? is this some kind of Gibbs
> effect on the border areas? I find that a great deal of the nose
> when only using the original image comes from around the borders.

The reason why WSS works so nice with the 9/7 and the 5/3 is the
symmetry of the wavelet. That is, the symmetric extension of the wavelet
creates after filtering wavelet coefficients that are symmetric again.
You can, thus, on the backwards transformation, just mirror-extend the
wavelet data, and filter it, to go back to the original image, i.e.
mirroring in the wavelet domain and in the image domain are equivalent.
That said, you do not need to keep any reference to data outside of the
image, and you get back the *identical* result.

For DCT, for example, you need to keep DCT coefficients at the boundary
that belong to "invented" data, namely those belonging to coefficients
outside the image. This is not the case here.

A good reference for this is probably the Marcellin/Taubman book on
JPEG2000.

So long,
Thomas

Jerzie.Klenchier@gmail.com

2008-03-27, 3:57 am

Hi Thomas,

Thank-you for the reply, it was very informative, and has led to
more questions from me. :>

> Dependent on how precisely the flipping is done, this is called WSS or
> HSS (whole sample symmetric resp. half sample symmetric) extensions. For
> the odd-length wavelets in JPEG2000 (CDF9/7,5/3), you need the WSS.
>

I did a google and the only difference I could find between HSS and
WSS is that one includes the boundry where as the other does not in
the reflection.

eg: if the data was 12345 then
WSS is 543211234554321
HSS is 5432123454321

Is this correct?

> The reason why WSS works so nice with the 9/7 and the 5/3 is the
> symmetry of the wavelet. That is, the symmetric extension of the wavelet
> creates after filtering wavelet coefficients that are symmetric again.
> You can, thus, on the backwards transformation, just mirror-extend the
> wavelet data, and filter it, to go back to the original image, i.e.
> mirroring in the wavelet domain and in the image domain are equivalent.
> That said, you do not need to keep any reference to data outside of the
> image, and you get back the *identical* result.
>

Could you please provide some more information about how the
reflection is done. As I can't see how the intuitive method (the same
as
the one used for spatial-time images) applies because the coefficients
are at different scales/orientations for example if we recieve the
following 2d set of wavelet coefficients:

LL HL HL HL
LH HH HL HL
LH LH HH HH
LH LH HH HH

would the reflection you speak of be the following:

?? ?? ?? ?? LH LH HH HH ?? ?? ?? ??
?? ?? ?? ?? LH LH HH HH ?? ?? ?? ??
?? ?? ?? ?? LH HH HL HL ?? ?? ?? ??
?? ?? ?? ?? LL HL HL HL ?? ?? ?? ??
HL HL HL LL LL HL HL HL HL HL HL LL
HL HL HH LH LH HH HL HL HL HL HH LH
HH HH LH LH LH LH HH HH HH HH LH LH
HH HH LH LH LH LH HH HH HH HH LH LH
?? ?? ?? ?? LH LH HH HH ?? ?? ?? ??
?? ?? ?? ?? LH LH HH HH ?? ?? ?? ??
?? ?? ?? ?? LH HH HL HL ?? ?? ?? ??
?? ?? ?? ?? LL HL HL HL ?? ?? ?? ??

If so what should the values of the "??" be? zero perhaps?

Also when the inverse transform is done, and a spatial-time
representation is produced where will the image lie - in the center? a
boundingbox with upper and lower coordingates (w,h) (2w,2h)
respectively?

Rgds,

Jerzie

Thomas Richter

2008-03-27, 6:56 pm

Jerzie.Klenchier@gmail.com wrote:
> Hi Thomas,
>
> Thank-you for the reply, it was very informative, and has led to
> more questions from me. :>
>
>
> I did a google and the only difference I could find between HSS and
> WSS is that one includes the boundry where as the other does not in
> the reflection.
>
> eg: if the data was 12345 then
> WSS is 543211234554321
> HSS is 5432123454321
>
> Is this correct?

Just the other way 'round. For HSS, the point at which data is reflected
is "half between" the samples (gaphically 54321|12345) whereas for WSS,
the reflection point is *at* the whole sample, i.e. inside the "1".

>
> Could you please provide some more information about how the
> reflection is done.

Algorithmically? Well, it clearly does not matter whether you first
extend horizontally or vertically, the order doesn't matter. Thus, if
your data extends from s to e, including s, excluding e, you copy the
sample at position s+1 to s-1, then the sample at e-2 to e, then the
sample at s+2 to s-2, then the sample at e-3 to e+1 and so on, until
enough data is there. This procedure works, even if only two samples are
there (try it!). It does not work for a single sample, in which case
JPEG2000 employs a special rule for filtering (namely, only the identity
transform for low-pass and multiplication by two for high-pass).

> As I can't see how the intuitive method (the same
> as
> the one used for spatial-time images) applies because the coefficients
> are at different scales/orientations for example if we recieve the
> following 2d set of wavelet coefficients:
>
>
> LL HL HL HL
> LH HH HL HL
> LH LH HH HH
> LH LH HH HH
>
>
> would the reflection you speak of be the following:
>
>
> ?? ?? ?? ?? LH LH HH HH ?? ?? ?? ??
> ?? ?? ?? ?? LH LH HH HH ?? ?? ?? ??
> ?? ?? ?? ?? LH HH HL HL ?? ?? ?? ??
> ?? ?? ?? ?? LL HL HL HL ?? ?? ?? ??
> HL HL HL LL LL HL HL HL HL HL HL LL
> HL HL HH LH LH HH HL HL HL HL HH LH
> HH HH LH LH LH LH HH HH HH HH LH LH
> HH HH LH LH LH LH HH HH HH HH LH LH
> ?? ?? ?? ?? LH LH HH HH ?? ?? ?? ??
> ?? ?? ?? ?? LH LH HH HH ?? ?? ?? ??
> ?? ?? ?? ?? LH HH HL HL ?? ?? ?? ??
> ?? ?? ?? ?? LL HL HL HL ?? ?? ?? ??
>
> If so what should the values of the "??" be? zero perhaps?

No, they are reflected over from the extended parts, really blindly
following the algorithm above. For the 9/7, you need WSS, thus:

LL HL
LH HH

first becomes (by horizontal extension):

LL HL | LL HL | LL HL
LH HH | LH HH | LH HH

and then by vertical extension:

LL HL | LL HL | LL HL
LH HH | LH HH | LH HH
------+-------+-------
LL HL | LL HL | LL HL
LH HH | LH HH | LH HH
------+-------+-------
LL HL | LL HL | LL HL
LH HH | LH HH | LH HH

which is the same as first doing vertical and then horizontal (try it!).

The reason why this is the right thing to do is that the 2D wavelet
transformation is just a tensor product of two 1-d transforms, and as
such, in an (ideal, infinite precision) implementation the order of the
transforms itself does not matter. You can also first extend
horizontally, filter horizontally, extend vertically, filter vertically.

> Also when the inverse transform is done, and a spatial-time
> representation is produced where will the image lie - in the center? a
> boundingbox with upper and lower coordingates (w,h) (2w,2h)
> respectively?

Well, using which definition of "center"? If you extend by the same
amount of samples to each side, the image will clearly be in the
"center" of the then created extended image (this is because you extend
by the same amount of data). You do not need to extend the image by two
in each dimension. For the 9/7 wavelet, you only need four pixels on
either side (9 = 4*2 + 1 is the length of the filter). However, this
extension does not change the canvas coordinates, i.e. you do not shift
the image. If the image starts at coordinate zero, the extended/mirrored
pixels are at -1,-2,-3 and -4. (In this sense, the image is not centered
around the origin.)

So long,
Thomas

Sponsored Links