/Users/lyon/j4p/src/ip/transforms/Wavelet.java
```
1    /****************************************************************
2     *                   CS410X  - JAVA Programming                 *
3     *                                                              *
4     *                        Assignment #4                         *
5     *                                                              *
6     *                      Haar - Wavelet 2D CODEC                 *
7     *                                                              *
8     *      Programmer: Matanya Elchanani, SID:0280923              *
9     *      Date: Nov. 1st 1997                                     *
10    *                                                              *
11    *      File: Wavelet.java                                      *
12    *                                                              *
13    ****************************************************************
14    This program is a 2D form of the previous homework assignment.
15    I have used the same code (I think it is quite nifty to expend
16    on a previous work) with minor changes:
17    1. The prime matrix filler now works on a 2D matrix.
18    2. The multilevel Forward and Inverse Haar-Wavelet methods were
19    revised so they iterate through a 2D array, applying the
20    transform to each row at a time.
21    3. An overloaded 2D show method was added to be able to present
22    the whole 2D array at the beginning.
23
24    The rest of this remark is taken from the previous code:
25
26    This program will fill an array with prime numbers. It will then
27    Apply the Haar-Wavelet algorithm to the data and extract averages
28    and difference coefficients repeatedly, until all data has been
29    converted, and a single "father of all data" value is left as the
30    first member of the array. The rest of the array will contain
31    growing sets of difference coefficients.
32
33    The above array is then operated over with an inverse Haar-Wavelet
34    algorithm, which uses the "father of all data" and the difference
35    coefficients to gradually reconstruct the the original data.
36
37    Author's remark: Instead of using a set of matrices to hold the
38    resulting coefficients (as the assignment suggested), I have chosen
39    to use an overwrite of the original data in a vector. This is
40    possible because for N data points, N/2 averages and N/2
41    coefficients are written, so we can safely overwrite the old N data
42    points. This method is much more efficient from a memory usage
43    point, and keeps the data in a single dimension orientation (which
44    is recommended as this is a single dimension CODEC).
45
46    As can be seen from the results, the usage of integers introduces
47    rounding errors which eventually cause "noise" in the reconstructed
48    data. Using floats to hold the averages and coefficients will solve
49    the problem on the expence of wasting memory for holding floats.
50    */
51
52   package ip.transforms;
53
54   public class Wavelet {
55       public static void main(String args[]) {
56           int x[][] =
57                   {
58                       {9, 7, 5, 3},
59                       {3, 5, 7, 9},
60                       {2, 4, 6, 8},
61                       {4, 6, 8, 10}
62                   };
63           demo(x);
64           int y[][] =
65                   {
66                       {1, 2, 3, 4},
67                       {4, 3, 2, 1},
68                       {1, 2, 3, 4},
69                       {4, 3, 2, 1}
70                   };
71           demo(y);
72
73       }
74
75       public static void demo(int x[][]) {
76           show(x, x.length);
77           System.out.println("Running Forward Haar Wavelet on the matrix:");
78           fhw(x);
79           //x=transpose(x);
80           //fhw(x);
81           //System.out.println("Here is what you transmit");
82           //show(x);
83           System.out.println("Running Inverse Haar Wavelet on the matrix:");
84           ihw(x);
85           //x=transpose(x);
86           //ihw(x);
87
88       }
89
90       public static void demo2d(int x[][]) {
91           show(x, x.length);
92           System.out.println("Running Forward Haar Wavelet on the matrix:");
93           fhw(x);
94           x = transpose(x);
95           fhw(x);
96           System.out.println("Here is what you transmit");
97           show(x);
98           System.out.println("Running Inverse Haar Wavelet on the matrix:");
99           ihw(x);
100          x = transpose(x);
101          ihw(x);
102      }
103
104      static boolean printing = true;
105
106      public static void fihw2d(int x[][]) {
107          printing = false;
108          fhw(x);
109          x = transpose(x);
110          fhw(x);
111          System.out.println("Here is what you transmit");
112          show(x);
113          ihw(x);
114          x = transpose(x);
115          ihw(x);
116      }
117
118      public static void fhw(int x[][]) {
119          fhw(x, x.length, log2(x.length));
120      }
121
122      public static void ihw(int x[][]) {
123          ihw(x, x.length, log2(x.length));
124      }
125
126      public static int log2(int n) {
127          return (int) (Math.log(n) / Math.log(2));
128      }
129
130      public static void main2(String args[]) {
131
132
133  /* Create the 2D data array and fill it with prime numbers */
134          int x[][] = new int;
135          fillprime(x);
136
137  /* Show our original data (resolution level 1) */
138          System.out.println("The original Data:");
139          show(x, 8);
140
141  /* Now gui.run the multilevel forward haar wavelet transform on the
142     data, replacing the original array members with their averages
143     and difference coefficients */
144          System.out.println("Running Forward Haar Wavelet on the matrix:");
145          fhw(x, 8, 3);
146
147  /* Now gui.run the multilevel inverse haar wavelet transform on the
148     data, replacing the averages and difference coefficients with
149     the reconstructed data */
150          System.out.println("Running Inverse Haar Wavelet on the matrix:");
151          ihw(x, 8, 3);
152          System.out.println("That's all folks.");
153      }
154
155
156      /**
157       * Print an array (or part of it) given the size to print.
158       * This is an overloaded method for showing up a whole 2D
159       * array.
160       */
161      public static void show(int in[][]) {
162          show(in, in.length);
163      }
164
165      public static void show(int in[][], int size) {
166
167          for (int i = 0; i < in.length; i++) {
168              for (int j = 0; j < size; j++)
169                  System.out.print(in[i][j] + "\t");
170              System.out.println("");
171          }
172          System.out.println("-------------------");
173      }
174
175      /**
176       * Print an array (or part of it) given the size to print.
177       * If colon is true, a coma will be printed half way between
178       * the members (separating the avereges from the coefficients).
179       */
180      public static void show(int in[], int size, boolean colon) {
181          if (!printing) return;
182
183          for (int i = 0; i < size; i++) {
184              if ((size / 2 == i) && colon)
185                  System.out.print(", ");
186              System.out.print(in[i] + "\t");
187          }
188          System.out.println("");
189      }
190
191
192      /**
193       * Single level Forward Haar Wavelet transform.
194       */
195      public static void fhw(int in[], int size) {
196          int tmp[] = new int[size];
197
198          for (int i = 0; i < size; i += 2) {
199              tmp[i / 2] = (in[i] + in[i + 1]) / 2;   //compute the average
200              tmp[size / 2 + i / 2] = (in[i] - in[i + 1]) / 2; // compute the coeff.
201          }
202
203          for (int i = 0; i < size; i++) //put data back to the array
204              in[i] = tmp[i];
205          show(in, size, true); // and show it
206      }
207
208
209      /**
210       * Multilevel 2D forward haar wavelet transform.
211       * This is an overloaded "fhw" method for applying forward
212       * haar wavelet "level" times on the matrix, each time with
213       * half the range, and doing that on each row in the 2D matrix.
214       */
215      public static void fhw(int in[][], int size, int level) {
216          int range = size;
217          for (int j = 0; j < level; j++) {
218              for (int i = 0; i < size; i++) {
219                  fhw(in[i], range);  // Apply fhw to each row
220              }
221              System.out.println("-------------------");
222              range /= 2;  // next resolution level
223          }
224      }
225
226
227      /**
228       * Single level Inverse Haar Wavelet transform.
229       */
230      public static void ihw(int in[], int size) {
231          int tmp[] = new int[size];
232
233          for (int i = 0; i < size; i += 2) {  // reconstruct two members
234              tmp[i] = in[i / 2] + in[size / 2 + i / 2];
235              tmp[i + 1] = in[i / 2] - in[size / 2 + i / 2];
236          }
237
238          for (int i = 0; i < size; i++)  // put it in the array
239              in[i] = tmp[i];
240          show(in, size, false);  // and show the results
241      }
242
243
244      /**
245       * Multilevel 2D inverse haar wavelet transform.
246       * This is an overloaded "ihw" method for applying inverse
247       * haar wavelet "level" times on the matrix, each time with
248       * double the range.
249       */
250
251      public static void ihw(int in[][], int size, int level) {
252          int range = size >> (level - 1);
253          for (int j = 0; j < level; j++) {
254              for (int i = 0; i < size; i++) {
255                  ihw(in[i], range);  // Apply ihw on each row
256              }
257              if (printing)
258                  System.out.println("-------------------");
259              range *= 2;  // Next resolution level
260          }
261      }
262
263
264      /**
265       * Fill a 2D matrix with prime numbers.
266       *
267       */
268      public static void fillprime(int in[][]) {
270          boolean itsprime;
271
272          for (int i = 0; i < in.length; i++) {  // fill the whole matrix
273              for (int j = 0; j < in[i].length; j++)
274                  do {
276                          in[i][j] = primenum;  // we have a prime, store it.
278                  } while (!itsprime);  // loop as long as it's not a prime
279          }
280      }
281
282
283      /**
284       * Check if a number is prime.
285       *
286       */
287      public static boolean isprime(int x) {
288          boolean prime = true;  // assume it is
289          int div;
290
291          div = x / 2;  // check only half the range
292          while ((div > 1) && prime) {
293              prime = ((x % div) != 0);
294              div--;
295          }
296          return (prime);
297      }
298
299      public static int[][] transpose(int a[][]) {
300          int b[][] = new int[a.length][a.length];
301          for (int x = 0; x < a.length; x++)
302              for (int y = 0; y < a.length; y++)
303                  b[y][x] = a[x][y];
304          return b;
305      }
306  }```