## Tuesday, May 31, 2016

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

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<>();
}

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   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.