基于小波变换的嵌入式图像压缩的C语言实现程序

/* EZWDOS.C Example of Embedded Zerotree Wavelet encoding in ANSI-C. This file is part of my Embedded Zerotree Wavelet Encoder Tutorial. Based on "Embedded Image Coding Using Zerotrees of Wavelet Coefficients" by Jerome M. Shapiro, IEEE Transactions on Signal Processing, Vol.41, No.12, December 1993, pp 3445-3462. A fifo is used in the dominant pass which results in a so-called Morton order scan instead of Shapiro's raster scan (see figure 2 in "Analysis Based Coding of Image Transform and Subband Coefficients" by V. Ralph Algazi and Robert R. Estes, Jr.). Morton order scan: ================== 1 | 2 | 5 6 | 17 18 21 22 ---+---| | 3 | 4 | 7 8 | 19 20 23 24 -------+--------| 9 10 | 13 14 | 25 26 29 30 | | 11 12 | 15 16 | 27 28 31 32 ----------------+--------------- 33 34 37 38 | 49 50 53 54 | 35 36 39 40 | 51 52 55 56 | 41 42 45 46 | 57 58 61 62 | 43 44 47 48 | 59 60 63 64 Raster scan: ============ 1 | 2 | 5 6 | 17 18 19 20 ---+---| | 3 | 4 | 7 8 | 21 22 23 24 -------+--------| 9 10 | 13 14 | 25 26 27 28 | | 11 12 | 15 16 | 29 30 31 32 ----------------+--------------- 33 34 35 36 | 49 50 51 52 | 37 38 39 40 | 53 54 55 56 | 41 42 43 44 | 57 58 59 60 | 45 46 47 48 | 61 62 63 64 Subband distribution: ===================== LL | HL | HL HL | HL HL HL HL ---+--- | | LH | HH | HL HL | HL HL HL HL --------+---------| LH LH | HH HH | HL HL HL HL | | LH LH | HH HH | HL HL HL HL ------------------+------------------ LH LH LH LH | HH HH HH HH | LH LH LH LH | HH HH HH HH | LH LH LH LH | HH HH HH HH | LH LH LH LH | HH HH HH HH (C) C. Valens, <c.valens@mindless.com> Created : 04/09/1999 Last update: 29/09/1999 */ #define debug #include "ezw.h" #include "fifo.h" #include "list.h" #include "matrix2d.h" #include <stdio.h> #include <stdlib.h> #include <math.h> /* * Global data. */ matrix_2d *M; char error; int zeroes, ones; FILE *ezw_file; unsigned char output_byte, mask; ezw_file_header header; /* * Copy the example data into a work matrix. */ void load_data(matrix_2d *m) { int row, col; for (row=0; row<8; row++) { for (col=0; col<8; col++) { m->m[row][col] = example[row][col]; } } } /* * Puts a bit in the output stream. */ void put_bit(char bit) { if (bit=='1') { output_byte |= mask; ones++; } else zeroes++; mask >>= 1; if (mask==0) { fwrite(&output_byte,sizeof(output_byte),1,ezw_file); output_byte = 0; mask = 0x80; } } /* * Puts dominant-pass and subordinate-pass codes in the output stream. */ void output_code(int code) { switch (code) { case ZERO: put_bit('0'); #ifdef debug printf("0"); #endif break; case ONE: put_bit('1'); #ifdef debug printf("1"); #endif break; case POS: put_bit('0'); put_bit('1'); #ifdef debug printf("p"); #endif break; case NEG: put_bit('1'); put_bit('1'); #ifdef debug printf("n"); #endif break; case ZTR: put_bit('0'); put_bit('0'); #ifdef debug printf("t"); #endif break; case IZ: put_bit('1'); put_bit('0'); #ifdef debug printf("z"); #endif break; } } /* * Returns the largest value in a descendance tree. */ element_type max_descendant(matrix_2d *m, int x, int y) { int i, j, min_x, max_x, min_y, max_y; element_type temp, max; if ((x==0) && (y==0)) { temp = m->m[0][0]; m->m[0][0] = min_element_type; max = matrix_2d_abs_max(m); m->m[0][0] = temp; } else { min_x = x << 1; min_y = y << 1; max_x = (x+1) << 1; max_y = (y+1) << 1; if ((min_x==m->col) || (min_y==m->row)) { return (0); } max = 0; while ((max_y<=m->row) && (max_x<=m->col)) { for (i=min_y; i<max_y; i++) { for (j=min_x; j<max_x; j++) { temp = abs(m->m[i][j]); if (temp>max) max = temp; } } min_x <<= 1; max_x <<= 1; min_y <<= 1; max_y <<= 1; } } return (max); } /* * Returns 1 if descendance tree is a zerotree. */ char zerotree(matrix_2d *m, int x, int y, int threshold) { int i, j, min_x, max_x, min_y, max_y; element_type temp, max; char stop; stop = 0; if ((x==0) && (y==0)) { temp = m->m[0][0]; m->m[0][0] = min_element_type; max = matrix_2d_abs_max(m); m->m[0][0] = temp; if (max>=threshold) stop = 1; } else { min_x = x << 1; min_y = y << 1; max_x = (x+1) << 1; max_y = (y+1) << 1; if ((min_x==m->col) || (min_y==m->row)) { return (1); } max = 0; while ((max_y<=m->row) && (max_x<=m->col)) { for (i=min_y; i<max_y; i++) { for (j=min_x; j<max_x; j++) { temp = abs(m->m[i][j]); if (temp>=threshold) { stop = 1; break; } } if (stop==1) break; } if (stop==1) break; min_x <<= 1; max_x <<= 1; min_y <<= 1; max_y <<= 1; } } if (stop==1) return (0); return (1); } /* * Returns a dominant-pass code from the alphabet [POS,NEG,ZTR,IZ]. */ int code(matrix_2d *m, int x, int y, element_type threshold) { element_type temp; temp = m->m[y][x]; if (abs(temp)>=threshold) { if (temp>=0) return (POS); else return (NEG); } else { /* if ((max_descendant(m,x,y)<threshold)) code = ZTR*/ if (zerotree(m,x,y,threshold)==1) return (ZTR); else return (IZ); } } /* * Appends a value to the subordinate list. */ void to_sub_list(element_type value) { list_type d; /* * Put only coefficient magnitude in list, sign is allready coded. */ d.x = abs(value); d.y = 0; append_to_list(d); } /* * Builds a dominant pass EZW-element from a matrix element and a threshold. */ void process_element(matrix_2d *m, element_type threshold, ezw_element *s) { s->code = code(m,s->x,s->y,threshold); if ((s->code==POS) || (s->code==NEG)) { to_sub_list(m->m[s->y][s->x]); m->m[s->y][s->x] = 0; } } /* * Performs one complete dominant pass. Dominant-pass-codes are sent to the * output stream and the subordinate list is updated. */ void dominant_pass(matrix_2d *m, element_type threshold) { ezw_element s; int min_x, max_x, min_y, max_y; /* int level;*/ s.x = 0; s.y = 0; process_element(m,threshold,&s); output_code(s.code); s.x = 1; s.y = 0; process_element(m,threshold,&s); put_in_fifo(s); s.x = 0; s.y = 1; process_element(m,threshold,&s); put_in_fifo(s); s.x = 1; s.y = 1; process_element(m,threshold,&s); put_in_fifo(s); s = get_from_fifo(); if (fifo_empty==0) output_code(s.code); while (fifo_empty==0) { if (s.code!=ZTR) { min_x = s.x << 1; max_x = min_x+1; min_y = s.y << 1; max_y = min_y+1; if ((max_x<=m->col) && (max_y<=m->row)) { for (s.y=min_y; s.y<max_y+1; s.y++) { for (s.x=min_x; s.x<max_x+1; s.x++) { process_element(m,threshold,&s); put_in_fifo(s); } } } } s = get_from_fifo(); if (fifo_empty==0) output_code(s.code); } } /* * Performs one s