www.pudn.com > ezw_davis.rar > 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,
Created : 04/09/1999
Last update: 29/09/1999
*/
#define debug
#include "ezw.h"
#include "fifo.h" //包括fifo的初始化，清空fifo链表
//向fifo中输入数据,向fifo中取数
#include "list.h" //list中包含有组成LIS,LIP,LSP链表的基本输入
//输出操作
#include "matrix2d.h" //matrix2d文件中包含对二维矩阵的建立，删除，
//清0，打印矩阵的值，输出矩阵的绝对值的最大值
#include
#include
#include
/*
* 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)//将example中的数据放到二维矩阵m->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)//向位平面输出bit流
{
if (bit=='1') {
output_byte |= mask;//将ouput_byte与mask按位与操作，从而达到位平面
//传输的目的
ones++;
}
else zeroes++;
mask >>= 1;
if (mask==0) {
fwrite(&output_byte,sizeof(output_byte),1,ezw_file);
output_byte = 0;//
mask = 0x80; //这两条语句相当于初始化output_byte和mask
}
}
/*
* 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; im[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)//如果子树中没有
//大于阈值的则返回1，若子树中有大于阈值的则返回0
{
int i, j, min_x, max_x, min_y, max_y;
element_type temp, max;
char stop;//stop中存放1或0表示是否有最大值超过阈值
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; im[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);//最大值大于阈值且为正，则输出POS
else return (NEG); //最大值大于阈值且为负，则输出NEG
}
else {
/* if ((max_descendant(m,x,y)code = code(m,s->x,s->y,threshold); //得到输出的代码
if ((s->code==POS) || (s->code==NEG)) { //说明元素本身大于阈值
to_sub_list(m->m[s->y][s->x]); //将该元素放入LSP中
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);//将(0,0)树根节点输出它的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); //上面的三组语句说明将带有子树的树根节点放入fifo中
s = get_from_fifo();
if (fifo_empty==0) output_code(s.code);//将fifo中的第一个元素输出它的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.y0) {
for (i=0; i>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);//将头文件写入ezw_file中，其中头文件包括矩阵的行列
//以及初始的阈值大小
/*
* Do the EZW coding.
*/
zeroes = 0;
ones = 0;
output_byte = 0;//
mask = 0x80; //这两句说明bit流的初始化操作
EZW_code(M,header.threshold);//这是本ezw算法的核心函数***********************
/*
* 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;
}