Tuesday, February 16, 2016

Signal Reconstruction with CDF(4, 4) Using Top N Coefficients: Programmatic Note 12 on Ripples in Mathematics




Introduction
  
This is my programmatic note 12 on Ch. 04, p. 32, in "Ripples in Mathematics" by A. Jensen & A. la Cour-Harbo. These notes document my programmatic journey, sometimes easy, sometimes painful but always joyful, through this great text. My notes are for those who want to use Java as a programming investigation tool of various wavelet algorithms and Octave to plot the results. You can find my previous notes by searching my blog on "ripples in mathematics." If you are on the same journey, let me know of any bugs in my code or improvements you have found that let us get the results in a better way.

In this note, I document my reconstruction of the multiresolution analysis in Fig. 4.11, p. 32 with CDF(4, 4), not CDF(2, 2), as done in the book. As stated in the text, Fig. 4. 11, p. 32, reconstructs from the transformed signal the sinusoid y = sin(4*pi*t), for t in [0, 1], sampled at 512 equidistant points. The value of the 200th sample is set to 2, and some random noise is added into the sample.   

Keeping Top N Coefficients


I implemented an auxiliary static method keepTopNPercentInRange() in RipplesInMathCh04.java. The method applies takes a signal, a range specification (range_start and range_end), and a percent coefficient. The method keeps the top percent coefficients in [range_start, range_end] in the signal. Since the range boundaries are discretized, i.e., converted to integers, there is some loss of precision.

static void keepTopNPercentInRange(double[] signal, int range_start, int range_end, double percent) {
        if ( percent < 0.0 || percent > 100.0 ) throw new IllegalArgumentException("percent < 0 or > 100");
        if ( percent == 100.0 ) return; // no need to do anything
      
        final int range_length = range_end - range_start + 1;
        double[] sorted_range = new double[range_length];
        // copy the signal segment into sorted_range
        System.arraycopy(signal, range_start, sorted_range, 0, range_length);
        Arrays.sort(sorted_range); // sort the range
        final int percent_len = (int) (range_length * (percent/100.0));
        // 100 - 90 = 10
        final int sorted_range_min_index = Math.max(0, Math.min(range_length - percent_len, range_length - 1));
      
        if ( sorted_range_min_index > range_length - 1 ) {
            throw new IllegalArgumentException("Range cannot be discretized: "
                    + range_start + ", " + range_end + ", " + percent);
        }
                       
        final double sorted_range_min = Math.abs(sorted_range[sorted_range_min_index]);
        // set all values in signal less than the abs(sorted_range_min) to 0.0
        for(int i = range_start; i < range_end; i++) {
            if ( Math.abs(signal[i]) < sorted_range_min ) {
                signal[i] = 0.0;
            }
        }
    }

The method fig_4_11_p32_top_n() below generates the signal in Fig. 4.7, p. 32 in the book with a spike at 200 and random noise. Then the signal is transformed by applying 3 scales of CD(4, 4) and keeping the top n percent of coefficients in each scale. This is how I interpreted the formulation of this problem on p. 31.

   static void fig_4_11_p32_top_n(double percent) {
        for(int i = 0; i < 512; i++)  {
            sRange[i] = sRipples_F_p25.v(sDomain[i]);
        }

        sRange[200] = 2; // spike at 200
        addNoiseToSignal(sRange);
        System.out.println("=========================");
        System.out.println("Signal with Noise:");
        display_signal(sRange);
      
        CDF44.orderedDWTForNumIters(sRange, 3, false);
      
        keepTopNPercentInRange(sRange, D8_START_512, D8_END_512, percent);
        keepTopNPercentInRange(sRange, D7_START_512, D7_END_512, percent);
        keepTopNPercentInRange(sRange, D6_START_512, D6_END_512, percent);
        keepTopNPercentInRange(sRange, S6_START_512, S6_END_512, percent);
      
        System.out.println("=========================");
        System.out.println("Processed Signal with Noise:");
        display_signal(sRange);
        System.out.println("=========================");
        System.out.println("Inversed Signal with Noise:");
        CDF44.orderedInverseDWTForNumIters(sRange, 3, false);
        display_signal(sRange);
        System.out.println("=========================");
    }


Graphing Signals Reconstructed from Transformed Signals with Top N% of Coefficients


The graphs below show the signals reconstructed from the transformed signal with top 10%, 20%, 30%, 40%, and 50%. coefficients. All graphs were done in Octave 4 by copying and pasting the coefficients from the Java console into graphing Octave scripts. Each graph is given below the call to the Java method that computes the reconstructed signal's samples.

   static void fig_4_11_top_10_p32() { fig_4_11_p32_top_n(10.0); }
    

Figure 1. Signal reconstruction with top 10% coefficients

   static void fig_4_11_top_20_p32() { fig_4_11_p32_top_n(20.0); }



Figure 2. Signal reconstruction with top 20% coefficients
  
   
   static void fig_4_11_top_30_p32() { fig_4_11_p32_top_n(30.0); }

Figure 3. Signal reconstruction with top 30% coefficients
  
    static void fig_4_11_top_40_p32() { fig_4_11_p32_top_n(40.0); }
 

Figure 4. Signal reconstruction with top 40% coefficients

    static void fig_4_11_top_50_p32()  { fig_4_11_p32_top_n(50.0); }


Figure 5. Signal reconstruction with top 50% coefficients