Forward discrete wavelet transform: implement periodic symmetric extension at boundaries

[gcode-importer]

Originally reported on Google Code with ID 452

According to the final draft
of 15444-1, section F.2 (normative), the inverse wavelet transform must
use periodic symmetric extension at boundaries. 

I assume that this is also required for the forward wavelet.

However, openjpeg code truncates at the boundaries:

#define OPJ_S_(i) ((i)<0?OPJ_S(0):((i)>=sn?OPJ_S(sn-1):OPJ_S(i)))
#define OPJ_D_(i) ((i)<0?OPJ_D(0):((i)>=dn?OPJ_D(dn-1):OPJ_D(i)))

Symmetric extension should reduce boundary artifacts.

Reported by boxerab on 2014-12-18 21:35:09

[gcode-importer]

Since part 1 uses full-sample symmetric wavelets, the symmetric border extension operation
commutes with the transform operation. 

So, if S is the symmetric extension operation, F is the forward transform, and R is
the reverse transform, then we have the standard requiring

Decoded Image =  R(S(F(Original Image)))

Because S and F are commutative, and S * S = S, we get

Decoded Image = R(S(F(S(Original Image))))

So, we must use the symmetric extension in the forward transform as well.

Therefore, if my reading of the standard is correct, we should not be clamping the
image at the border, as we are doing in the above macros. We should use symmetric extension.

Reported by boxerab on 2014-12-20 15:07:51

• Labels added: Type-Defect
• Labels removed: Type-Enhancement

[gcode-importer]

This being related to the standard, i'll cc antonin.

Reported by mayeut on 2014-12-20 15:15:43

[gcode-importer]

By the way, this is not a conformance issue after all: encoder conformance relates completely
to the syntax of the code stream, and not the encoded pixels. 

See ISO/IEC 15444-4 Annex F.1
http://www.openjpeg.org/conformance/T.803e.pdf

Nevertheless, clamping at the boundary still does introduce artifacts at the boundary.
So, this is not a desirable feature;

Reported by boxerab on 2014-12-21 05:05:13

[gcode-importer]

The code below implements symmetric border extension for forward and reverse 5/3 wavelet,
and forward 9/7 wavelet. (Inverse 9/7 wavelet transform doesn't seem to use these macros)

#define OPJ_S(i) a[(i)<<1]
#define OPJ_D(i) a[(1+((i)<<1))]
#define OPJ_S_(i) ((i)<0?OPJ_S(-(i)):((i)>=sn?OPJ_S((sn<<1)-2 - (i)):OPJ_S(i)))
#define OPJ_D_(i) ((i)<0?OPJ_D(-(i)):((i)>=dn?OPJ_D((dn<<1)-2 - (i)):OPJ_D(i)))
#define OPJ_SS_(i) ((i)<0?OPJ_S(-(i)):((i)>=dn?OPJ_S((dn<<1)-2 - (i)):OPJ_S(i)))
#define OPJ_DD_(i) ((i)<0?OPJ_D(-(i)):((i)>=sn?OPJ_D((sn<<1)-2 - (i)):OPJ_D(i)))

Reported by boxerab on 2015-05-10 20:36:38

[boxerab]

The above macros implement clamping on odd/even samples at each lifting step -this is equivalent to symmetric extension past the boundaries. Please close this issue.

[detonin]

Thanks Aaron for digging into this yourself (and special thanks to Prof Taubman for having explained this on the kakadu list :-)). So OpenJPEG is (still) conformant to JPEG 2000 standard, good news !
@malaterre: openjpeg correctly implements symetric extension.