|
/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[8][8];
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[0].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[][]) {
269 int primenum = 1;
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 {
275 if (itsprime = isprime(primenum))
276 in[i][j] = primenum; // we have a prime, store it.
277 primenum++;
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[0].length][a.length];
301 for (int x = 0; x < a.length; x++)
302 for (int y = 0; y < a[0].length; y++)
303 b[y][x] = a[x][y];
304 return b;
305 }
306 }