📄 ezwdos.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 subordinate pass.
*/
void subordinate_pass(element_type threshold)
{
list_type d;
int i;
char found;
if (threshold>0) {
for (i=0; i<list_length; i++) {
d = get_list_element(i,&found);
if (found==1) {
if ((d.x&threshold)!=0) output_code(ONE);
else output_code(ZERO);
}
}
}
}
/*
* EZW-codes matrix m, returns initial threshold.
*/
void EZW_code(matrix_2d *m, element_type threshold)
{
while (threshold!=0) {
dominant_pass(m,threshold);
#ifdef debug
printf("\n");
#endif
subordinate_pass(threshold>>1);
#ifdef debug
printf("\n");
#endif
threshold >>= 1;
}
}
/*
* Main.
*/
int main(void)
{
printf("\n");
/*
* Build work matrix.
*/
header.height = 8;
header.width = 8;
M = matrix_2d_create(header.height,header.width);
if (M==NULL) exit(1);
load_data(M);
#ifdef debug
matrix_2d_write(M);
#endif
/*
* Prepare output file.
*/
header.threshold = 1 << (int)(floor(log10(matrix_2d_abs_max(M))/log10(2)));
if ((ezw_file=fopen("out.ezw","wb"))==NULL) {
printf("Could not open output file.\n");
exit(1);
};
fwrite(&header,sizeof(header),1,ezw_file);
/*
* Do the EZW coding.
*/
zeroes = 0;
ones = 0;
output_byte = 0;
mask = 0x80;
EZW_code(M,header.threshold);
/*
* Flush output.
*/
if (mask!=0) {
fwrite(&output_byte,sizeof(output_byte),1,ezw_file);
}
#ifdef debug
printf("\n");
printf(" bits: %d, %d zeroes, %d ones.\n",zeroes+ones,zeroes,ones);
#endif
/*
* Cleanup.
*/
fclose(ezw_file);
matrix_2d_destroy(M);
destroy_fifo();
destroy_list();
/*
* Clean exit.
*/
return 0;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -