7
$\begingroup$

Original image:

original image before transformation and filtering

(Images included are .png images, so no additional distortion was added in save/upload for viewing)

I have used the D4 transform from page 20 of "Ripples in mathematics", which is basically these 5 steps:

Forward d4:

c1 = √3 / 4.0 ;
c2 = (√3 - 2) / 4.0 ;
s[ IEVEN ] += √3 * s[ IODD ] ;
s[ IODD ] -= c1*s[ IEVEN ] + c2*s[ IPREVEVEN ] ;
s[ IEVEN ] -= s[ INEXTODD ] ;
s[ IEVEN ] *= ( √3 - 1 ) / √2 ;
s[ IODD ] *= ( √3 + 1 ) / √2 ;

The inverse:

c1 = √3 / 4.0 ;
c2 = (√3 - 2) / 4.0 ;
s[ IODD ] *= ( √3 - 1 ) / √2 ;
s[ IEVEN ] *= ( √3 + 1 ) / √2  ;
s[ IEVEN ] += s[INEXTODD] ;
s[ IODD ] += c1*s[ IEVEN ] + c2*s[IPREVEVEN] ;
s[ IEVEN ] -= √3 * s[ IODD ] ;

I'm compiling and running this using double precision values from C++. I run this on the rows of the image, then the columns. I use a crude filtration algorithm to remove the lowest 90% of the difference coefficients in the image.

The filtration algorithm is:

  • Run through entire transformed image (as a set of numbers)
  • Find the largest difference coefficient (maxVal) (in entire 2d image)
  • Choose minValToSurvive as 1% of maxVal.
  • If a difference coefficient has a magnitude less than minValToSurvive, it is zeroed.

Here's my problem is. When I remove only 83% of the lowest difference coefficients from the image (minValToSurvive=0.01*maxVal), you get this:

normalized

d4 83% reduction normalized

If I remove the normalization steps:

s[ IEVEN ] *= ( √3 - 1 ) / √2 ; // REMOVE
s[ IODD ] *= ( √3 + 1 ) / √2 ;

(in both the fwd and reverse transforms), the result after removing 90% of the components is much better (much less noise)

90% reduction, not normalized

So I can think of 1 of 2 problems:

  • Normalizing the image by the ( √3 - 1 ) / √2 factors is killing precision
  • I'm not filtering correctly

Or am I wrong? If I'm filtering (removing insignificant components) incorrectly, what is a better way to filter? If it's the floating point precision, then should I not normalize the transform at every step?

$\endgroup$
3
$\begingroup$

The right answer is you have to perform each of the Update/Predict steps on the input signal completely before doing the next Update/Predict. What I was doing was walking through the signal, and performing each Update/Predict as I go.

On page 158 of "Ripples", there is a reference implementation.

// s is the signal
#define IEVEN (2*j)
#define IODD (2*j + i)
for( int i = 1 ; i <= n/2 ; i *= 2 )
{
  for( int j = 0 ; j <= n/2 - i ; j += i ) // Must do this Predict step COMPLETLEY
    s[ IEVEN ] += √3 * s[ IODD ] ;

  for( int j = 0 ; j <= n/2 - i ; j += i ) // Then this one..
  {
    int prevEvenIndex = IPREVEVEN ;
    s[ IODD ] -= d4c1*s[ IEVEN ] + d4c2*SAFE_PREV(s,prevEvenIndex) ;
  }

  for( int j = 0 ; j <= n/2 - i ; j += i )
  {
    int nextOddIndex = INEXTODD ;
    s[ IEVEN ] -= SAFE_NEXT(s,nextOddIndex) ;
  }

  for( int j = 0 ; j <= n/2 - i ; j += i )
  {
    s[ IEVEN ] *= d4normEvens ;
    s[ IODD ] *= d4normOdds ;
  }
}

The 98% 0's D4 transform:

d4 98%

$\endgroup$
  • $\begingroup$ Kudos for posting the update on your research! This site hasn't gathered a great variety of experts yet, so not every question can be answered, but it's great that you've come back and shared your findings. I'm sure it will be useful to others looking for similar info. $\endgroup$ – Phonon Mar 12 '12 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.