Building DWT Lifting Networks: Programmatic Note 19 on Ripples in Mathematics

Vladimir Kulyukin

---

Problem
  

This is my programmatic note 19 on Ch. 3, p. 13-20, 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 for plotting 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 all, fellow travelers on the wavelet road, get better and more beautiful results.

This programmatic note is the programmatic continuation of my conceptual note 5 on Sections 3.2 - 3.4 of Chapter 3 in "Ripples in Mathematics."  That note described how one could conceptualize forward and inverse DWT via lifting networks.This note describes my programmatic implementation of that conceptualization.

---

Forward DWT via Lifting in JAVA
  

Let us start again with the definition of basic forward DWT via lifting is given in Fig. 1. You can read the explanation of symbols in conceptual note 5. This network implements the two forward DWT equations given in the bottom of Fig. 1. In equation 1, the difference vector, i.e., the wavelets, are computed by subtracting the predicted events from the odds. In equation 2, the evens and the updated odds are added to obtain the coarser signal.

Figure 1. Basic forward DWT network

To implement this network I conceptualized it in terms of the following classes: Node.java, Wire.java, Splitter.java, Predictor.java, Updater.java, Plus.java, and Storage.java. The node is the top of the class hierarchy. Every other class, except Wire.java, extends it. The Wire class connects two Nodes and has the public method transfer() that transmits the signal from one Node to the other.

The forward DTW lifting network in Fig. 1 is implemented in ForwardDWTNetwork.java. The class declares the member variables and then, in the constructor, instantiates the Node objects and nine Wire objects that connect them exactly as they are connected in Fig. 1. The network is defined as an ArrayList of Wire objects. The processSignal() method sets the input and output of the Storage object on the left (i.e., S1) and then loops through the ArrayList of Wires calling the transfer() method on each Wire object. The output of the network is the output of the S0 and D0 Storage objects.

public class ForwardDWTNetwork {
   
    Storage D1; Storage S0; Storage D0;
    Splitter SPLITTER1; Predictor PREDICTOR1;
    Updater UPDATER1; Minus MINUS1; Plus PLUS1;
    Wire WIRE1; Wire WIRE2; Wire WIRE3;
    Wire WIRE4; Wire WIRE5; Wire WIRE6;
    Wire WIRE7; Wire WIRE8; Wire WIRE9;
    ArrayList<Wire> NETWORK;
   
    public ForwardDWTNetwork() {
        D1 = new Storage(); S0 = new Storage(); D0 = new Storage();
        SPLITTER1 = new Splitter(); PREDICTOR1 = new Predictor(); UPDATER1 = new Updater();
        MINUS1  = new Minus(); PLUS1 = new Plus();
        WIRE1 = new Wire(D1, SPLITTER1);
        WIRE2 = new Wire(SPLITTER1, PREDICTOR1);
        WIRE3 = new Wire(SPLITTER1, MINUS1);
        WIRE4 = new Wire(PREDICTOR1, MINUS1);
        WIRE5 = new Wire(MINUS1, UPDATER1);
        WIRE6 = new Wire(MINUS1, D0);
        WIRE7 = new Wire(SPLITTER1, PLUS1);
        WIRE8 = new Wire(UPDATER1, PLUS1);
        WIRE9 = new Wire(PLUS1, S0);
       
        NETWORK = new ArrayList<>();
        NETWORK.add(WIRE1); NETWORK.add(WIRE2); NETWORK.add(WIRE3);
        NETWORK.add(WIRE4); NETWORK.add(WIRE5); NETWORK.add(WIRE6);
        NETWORK.add(WIRE7); NETWORK.add(WIRE8); NETWORK.add(WIRE9);
    }

public Storage processSignal(Storage storage) {
        D1.setInput(storage.getInput()); D1.setOutput(storage.getOutput());
       
        for(Wire w: NETWORK) { w.transfer(); }
       
        System.out.print("Samples:\t");
        for(double d: S0.getOutput()) { System.out.print(d + " "); }
        System.out.println();
       
        System.out.print("Wavelets:\t");
        for(double d: D0.getOutput()) { System.out.print(d + " "); }
        System.out.println();
        return S0;
    }
}
   
Fig. 2 gives an example of how the basic forward DWT network works on (11, 3).

Figure 2. Basic forward DWT network processing (11, 3)

We can test our forward DWT network in (11, 3), as shown in Fig. 2, and also on (5, 1, 2, 8) as follows:

public static void test1() {
        final double[] signal = {11, 3};
        final double[] signal2 = {5, 1, 2, 8};
       
        ForwardDWTNetwork net1 = new ForwardDWTNetwork();
       
        Storage storage1 = new Storage();
        storage1.setInput(signal); storage1.setOutput(signal);
        Storage output1 = net1.processSignal(storage1);
       
        double[] output_signal = output1.getOutput();
        for(int i = 0; i < output_signal.length; i++) {
            System.out.print(output_signal[i] + " ");
        }
        System.out.println();
       
        storage1.setInput(signal2); storage1.setOutput(signal2);
        output1 = net1.processSignal(storage1);
       
        output_signal = output1.getOutput();
        for(int i = 0; i < output_signal.length; i++) {
            System.out.print(output_signal[i] + " ");
        }
        System.out.println();
    }
 
The output of running test1() in the main() is as follows:

Samples:    7.0
Wavelets:    -8.0
7.0
Samples:    3.0 5.0
Wavelets:    -4.0 6.0
3.0 5.0 

As discussed in in conceptual note 5,   basic forward DWT networks can be layered, as shown in Fig. 3 where two basic forward DWT networks  are layered to implement two scales of forward DWT.  Fig. 4 gives a concrete example of the layered network in Fig. 3 on the signal (5, 1, 2, 8). The network results in one coarser signal (4) and two wavelet vectors (2) and (-4, 6). Note that the coarser signal (4) gives the mean of the original signal (5, 1, 2, 8). 

Figure 3. Two layered forward basic DWT networks

We can construct and test a two-layer forward DWT on (5, 1, 2, 8) as follows:

    public static void test2() {
        final double[] signal2 = {5, 1, 2, 8};
       
        ForwardDWTNetwork net1 = new ForwardDWTNetwork();
        ForwardDWTNetwork net2 = new ForwardDWTNetwork();
       
        Storage storage2 = new Storage();
        storage2.setInput(signal2);
        storage2.setOutput(signal2);
        Storage output2 = net1.processSignal(storage2);
        double[] output2_signal = output2.getOutput();
        for(int i = 0; i < output2_signal.length; i++) {
            System.out.print(output2_signal[i] + " ");
        }
        System.out.println();
        Storage output3 = net2.processSignal(output2);
        double[] output3_signal = output3.getOutput();
        for(int i = 0; i < output3_signal.length; i++) {
            System.out.print(output3_signal[i] + " ");
        }
        System.out.println();
    }

Running test2() in the main() gives us the output below, which is the same as the output in Fig. 4.

Samples:    3.0 5.0
Wavelets:    -4.0 6.0
3.0 5.0
Samples:    4.0
Wavelets:    2.0
4.0 
  

Figure 4. Layered forward DWT network processing (5, 1, 2, 8)

---

Inverse DWT via Lifting in JAVA

I implemented the basic inverse DWT  in InverseDWTNetwork.java. This network takes the coarser signal and the corresponding wavelets and synthesizes from them the more refined signal at the previous scale, as shown in Fig. 5 to the right of the red dash line in the middle. 

Figure 5. Basic forward DWT and its inverse

The main() method below constructs a basic inverse DWT network and tests it on the signal (7) and the wavelet array (-8), i.e., the output of the forward DWT network in Fig. 2. 

public static void main(String[] args) {
        final double[] s0 = {7};
        final double[] d0 = {-8};
       
        InverseDWTNetwork net1 = new InverseDWTNetwork();

        Storage ss0 = new Storage();
        ss0.setInput(s0);
        ss0.setOutput(s0);
        Storage dd0 = new Storage();
        dd0.setInput(d0);
        dd0.setOutput(d0);
        Storage output2 = net1.processSignal(ss0, dd0);
        double[] output2_signal = output2.getOutput();
        for(int i = 0; i < output2_signal.length; i++) {
            System.out.print(output2_signal[i] + " ");
        }
        System.out.println();
       
    }

The output is the signal (11, 3), which is the input signal to the forward DWT network.

Inversed samples:    11.0 3.0
11.0 3.0

The inverse DWT networks can also be layered like their forward counterparts.

---

Building DWT Lifting Networks: Conceptual Note 5 on Ripples in Mathematics

Vladimir Kulyukin

---

Problem
  

This is my conceptual note 5 on Ch. 3, p. 13-20, 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 for plotting 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 all, fellow travelers on the wavelet road, get better and more beautiful results.

Sections 3.2 - 3.4 in Ch. 3 explain the principles of lifting. Lifting, conceptually speaking, is used to split signals into coarser signals and wavelets for forward DWTs and synthesize wavelets and coarser signals into more refined signals. Usually, lifting is implemented through array manipulation. But there is no reason for us to implement it in hardware. The disadvantage, of course, is that we are limited to a specific number of forward and backward sweeps. In this post, I will describe how we can conceptualize forward and inverse DWT via lifting networks.

---

Forward DWT via Lifting
  

The definition of basic forward DWT via lifting is given in Fig. 1. The green database symbols denote some storage devices. They can be as simple as arrays. The input signal at scale j comes from the storage device on the left. The signal is split into an array of evenly indexed samples, i.e., evens, and an array of oddly indexed signals, i.e., odds. The evens are fed into the predictor box. The odds and the predicted samples are given into the minus node where the predicted evens are subtracted from the evens. The output of the minus node are stored in the bottom storage device on the right and are also fed into the plus node where the are added to the unchanged evens. The output of the plus node are stored in the top storage device on the right. The top storage device on the right saves the coarser signal at the next scale. The bottom storage device on the right saves the wavelet coefficients or the differences. Mathematically, this network implements the two forward DWT equations given in the bottom of Fig. 1. In equation 1, the difference vector, i.e., the wavelets, are computed by subtracting the predicted events from the odds. In equation 2, the evens and the updated odds are added to obtain the coarser signal.

Figure 1. Basic forward DWT network

 
The predict and update boxes can implement various functions. For example, the predictor may implement the identify function and the updater may multiply each the input vector by 0.5. Fig. 2 gives an example of how the basic forward DWT network works on (11, 3).

Figure 2. Basic forward DWT network processing (11, 3)

 In Fig. 2, the input signal (11, 3) is split into the evens, i.e., (11), and the odds, i.e., (3), in the SPLIT box. The evens is fed into the PREDICT box. Since the PREDICT box implements the identify function, the evens leaves the PREDICT box unchanged and is fed to the MINUS node below where the predicted evens are subtracted from the odds. The output of the predicted nodes, i.e, (-8), which is saved in the bottom storage. This wavelet coefficient, i.e., -8, measures the change from the first half of the signal, i.e., 11, to the second half of the signal, i.e., 3. The wavelet vector (-8) goes into the UPDATE box and comes out as (-4). The updated wavelets and evens go into the PLUS node where they are summed and stored as the coarser signal in the top storage place as the coarser signal (7). Note that coarser sample 7 is the mean value of the first sample on the previous scale, i.e., 11, and the second sample of the previous scale, i.e., 3. 

Basic forward DWT networks can be layered. In software simulations, we can layer them as many times as we want. If we implement DWT in hardware, there will be physical constraints. Fig. 3 shows how two basic forward DWT networks can be layered to implement two scales of forward DWT. The input to the second forward DWT network is the coarser signal obtained from the first basic forward DWT network. Note that the wavelet coefficients from the first network are saved. They are not used in the second network. The outputs of the second network are the even coarser signal saved in the top storage device on the right  and the even coarser wavelets that are saved into the bottom storage device on the right.

Figure 3. Two layered forward basic DWT networks

 Fig. 4 gives a concrete example of the layered network in Fig. 3 on the signal (5, 1, 2, 8). The network results in one coarser signal (4) and two wavelet vectors (2) and (-4, 6). Note that the coarser signal (4) gives the mean of the original signal (5, 1, 2, 8).

Figure 4. Layered forward DWT network processing (5, 1, 2, 8)

---

Inverse DWT via Lifting

The basic inverse DWT takes the coarser signal and the corresponding wavelets and synthesizes from them the more refined signal at the previous scale.  In Fig. 5, the DWT network to the left of the dashed line is the basic forward DWT network whereas the DWT network to the right of the dashed line is the basic inverse DWT network. In the inverse network, the operations of the forward DWT are inversed. In other words, the Update is applied first, the prediction is applied second. Then the evens and odds are merged to restore the original signal. The two equations for the inverse DWT are given in the bottom right corner of Fig. 5. The are obtained algebraically from the two forward equations.

Figure 5. Basic forward DWT and its inverse

---