encode.cpp

一种无损图象压缩算法,可用于珍贵图象的保存.

//Encode.c
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
//Header Files
#include "const.h"
extern void init_bcoder  ();
extern void init_scoder  ();
extern void init_mycoder ();
extern void stop_mycoder (); 
extern void encode_symbol (int,int);
extern void bencode_symbol (int,int);
extern unsigned int bytes_output;
//Constant Definitions
//Options included in the encoder
#define OPTION_NEARLY_LOSSLESS
//Misc. constants
#define N_SEQ     NUM_CONTEXT     //Number of coding histograms
#define N_BSEQ    NUM_BCONTEXT    //Number of binary coding histograms 
#define UPPER     255             //Largest possible pixel value 
#define ERR_SPAN  (UPPER + 1)
//Macro Definitions
#define ABS(X)      (((X) < 0)   ? -(X) : (X))
#define MIN(X,Y)    (((X) < (Y)) ?  (X) : (Y))
#define MAX(X,Y)    (((X) < (Y)) ?  (Y) : (X))
//NEARLY LOSSLESS COMPRESSION 
#ifdef OPTION_NEARLY_LOSSLESS
//Variable Definitions
int tolerance = 7;
int mask      = 15;
int recon;
int MaxError = 0;
int QT[8];
int QS[8];
#endif
//NEARLY LOSSLESS COMPRESSION

//Misc. operations 
//Function : nh
//static int T0 =   5 + 2;
//static int T1 =  15 + 2;
//static int T2 =  25 + 3;
//static int T3 =  42 + 4;
//static int T4 =  60 + 5;
//static int T5 =  85 + 6;
//static int T6 = 140 + 8;
static int T0 =   5-1;
static int T1 =  15-5;
static int T2 =  25-4;
static int T3 =  42;
static int T4 =  60;
static int T5 =  85;
static int T6 = 140;

int nh (int k)
{
	if (k <= T0)      return (0);
	else if (k <= T1) return (1);
	else if (k <= T2) return (2);
	else if (k <= T3) return (3);
	else if (k <= T4) return (4);
	else if (k <= T5) return (5);
	else if (k <= T6) return (6);
	else return (7);
}

//Function : nremap
int nremap (int err, int p)
{
	register int aerr;
	if (err == 0) return (0);
	//NEARLY LOSSLESS COMPRESSION
	#ifdef OPTION_NEARLY_LOSSLESS
	{
		if (err > 0) err = (err + tolerance)/mask;
		else         err = (err - tolerance)/mask;
		if (err == 0) return (0);
		aerr = ABS (err);
		if (p <= (UPPER/2))
		{
			if ((mask*aerr) <= (p + tolerance))
			{
				if (err < 0) err = -(err << 1);
				else         err =  (err << 1) - 1;
			}
			else err = (p + tolerance)/mask + aerr;
		}
		else
		{
			if ((mask*aerr) <= (UPPER - p + tolerance))
			if (err < 0) err = -(err << 1);
			else         err =  (err << 1) - 1;
			else
			err = (UPPER - p + tolerance)/mask + aerr;
		}
	}
	#else
	aerr = ABS (err);
	if (p <= (UPPER/2))
	{
		if (aerr <= p)
			if (err < 0) err = -(err << 1);
			else         err =  (err << 1) - 1;
		else
			err = p + aerr;
	}
	else
	{
		if (aerr <= (UPPER - p))
			if (err < 0) err = -(err << 1);
			else         err =  (err << 1) - 1;
		else
			err = UPPER - p + aerr;
	}
	#endif
	//NEARLY LOSSLESS COMPRESSION 
	return (err);
}

//NEARLY LOSSLESS COMPRESSION
#ifdef OPTION_NEARLY_LOSSLESS
//Function : quant2 
//Mapping to quantized label and then to reconstructed value
int quant2 (int diff)
{
	if (diff == 0) return (diff);
	if (diff > 0) diff = (diff + tolerance)/mask;
	else          diff = (diff - tolerance)/mask;
	diff = diff*mask;
	return (diff);
}

#endif
//NEARLY LOSSLESS COMPRESSION 
//Operations for loading images  
FILE *infile;
FILE *outfile; 

//Function : create_buffer
void create_buffer (unsigned char **u0, unsigned char **u1, unsigned char **u2, int width, char *filename)
{
	//Open the input file
	//ZN: if (!(infile = fopen (filename, "r")))
	if (!(infile = fopen (filename, "rb")))
	{
		fprintf (stderr, "ERROR : cannot open input file %s!\n", filename);
		exit    (1);
	}
	//Load the first line of the image
	if ((*u2 = (unsigned char *) calloc (width + 2, sizeof (unsigned char))) == NULL)
	{
		fprintf (stderr, "ERROR : not enough space for buffer!\n");
		exit    (1);
	}
	if ((fread (*u2 + 1, sizeof (unsigned char), width, infile)) !=(unsigned int)width)
	{
		fprintf (stderr, "ERROR : in reading image!\n");
		exit    (1);
	}
	(*u2)[0]       = (*u2)[1];        /* Duplicate the first pixel */
	(*u2)[width+1] = (*u2)[width];    /* Duplicate the last  pixel */
	//Load the second line of the image
	if ((*u1 = (unsigned char *) calloc (width + 2, sizeof (unsigned char))) == NULL)
	{
		fprintf (stderr, "ERROR : not enough space for buffer!\n");
		exit    (1);
	}
	if ((fread (*u1 + 1, sizeof (unsigned char), width, infile)) !=(unsigned int)width)
	{
		fprintf (stderr, "ERROR : in reading image!\n");
		exit    (1);
	}
	(*u1)[0]       = (*u1)[1];        /* Duplicate the first pixel */
	(*u1)[width+1] = (*u1)[width];    /* Duplicate the last  pixel */
	//Load the third line of the image
	if ((*u0 = (unsigned char *) calloc (width + 2, sizeof (unsigned char))) == NULL)
	{
		fprintf (stderr, "ERROR : not enough space for buffer!\n");
		exit    (1);
	}
	if ((fread (*u0 + 1, sizeof (unsigned char), width, infile)) !=(unsigned int)width)
	{
		fprintf (stderr, "ERROR : in reading image!\n");
		exit    (1);
	}
	(*u0)[0]       = (*u0)[1];        /* Duplicate the first pixel */
	(*u0)[width+1] = (*u0)[width];    /* Duplicate the last  pixel */
}

//Function : update_buffer
void update_buffer (unsigned char **u0, unsigned char **u1, unsigned char **u2, int width)
{
	unsigned char *temp;
	temp = *u2;
	*u2  = *u1;
	*u1  = *u0;
	*u0  = temp;
	//Load a new line from the image
	if ((fread (*u0 + 1, sizeof (unsigned char), width, infile)) !=(unsigned int)width)
	{
		fprintf (stderr, "ERROR : in reading image!\n");
		exit    (1);
	}
	(*u0)[0]       = (*u0)[1];        /* Duplicate the first pixel */
	(*u0)[width+1] = (*u0)[width];    /* Duplicate the last  pixel */
}

//Function : destory_buffer 
void destory_buffer (unsigned char **u0, unsigned char **u1, unsigned char **u2)
{
	free (*u0);  *u0 = NULL;
	free (*u1);  *u1 = NULL;
	free (*u2);  *u2 = NULL;
	//Close the input file
	fclose (infile);
}

//Function : encode_buffer
void encode_buffer (unsigned char *u0, unsigned char *u1, unsigned char *u2, int width, int height)
{
	register unsigned short ptn, ptn0, ptn1, ptn2;
	int *N1, *N2; 
	int *S1, *S2;
	int *Pr;
	int *Dh, *Dv;
	int *E0, err, aerr;
	int H[N_SEQ][ERR_SPAN], BH[N_BSEQ][3];
	register int dh, dv, max, min, adjust, temp;
	register int symb1, symb2, bflag;
	register int nnww, nnw, nn, nne, nww, nw, n, ne, nee, www, ww, w, curr;
	register int x, j, k;
   
	//Allocate space ("Gradient")
	if ((Dh = (int *) calloc (width + 2, sizeof (int))) == NULL)
	{
		fprintf (stderr, "ERROR : no enough space for Dh\n");
		exit    (1);
	}
	if ((Dv = (int *) calloc (width + 2, sizeof (int))) == NULL)
	{
		fprintf (stderr, "ERROR : no enough space for Dv\n");
	exit    (1);
	}
	memset (Dh, 0, (width + 2)*sizeof (int));
	memset (Dv, 0, (width + 2)*sizeof (int));
	
	//Allocate space ("Prediction Error")
	if ((E0 = (int *) calloc (width + 2, sizeof (int))) == NULL)
	{
		fprintf (stderr, "ERROR : no enough space for E0\n");
		exit    (1);
	}
	aerr = err = 0;
	memset (E0, 0, (width + 2)*sizeof (int));
	if ((Pr = (int *) calloc (width + 2, sizeof (int))) == NULL)
	{
		fprintf (stderr, "ERROR : no enough space for E0\n");
		exit    (1);
	}
	memset (Pr, 0, (width + 2)*sizeof (int));
	
	//Allocate space ("Context Modeling")
	if ((N1 = (int *) calloc (4096, sizeof (int))) == NULL)
	{
		fprintf (stderr, "ERROR : no enough space for N1\n");
		exit    (1);
	}
	if ((S1 = (int *) calloc (4096, sizeof (int))) == NULL)
	{
		fprintf (stderr, "ERROR : no enough space for S1\n");
		exit    (1);
	}
	if ((N2 = (int *) calloc (4096, sizeof (int))) == NULL)
	{
		fprintf (stderr, "ERROR : no enough space for N2\n");
		exit    (1);
	}
	if ((S2 = (int *) calloc (4096, sizeof (int))) == NULL)
	{
		fprintf (stderr, "ERROR : no enough space for S2\n");
		exit    (1);
	}
	ptn = ptn0 = ptn1 = ptn2 = 0;
	ptn = ptn0 = ptn1 = ptn2= 0;
	memset (N1, 0, 4096*sizeof (int));
	memset (S1, 0, 4096*sizeof (int));
	memset (N2, 0, 4096*sizeof (int));
	memset (S2, 0, 4096*sizeof (int));
	
	//Initialize variables
	for (k = 0; k < N_SEQ; ++k) 
		for (j = 0; j < ERR_SPAN; ++j) H[k][j] = 0;
	for (k = 0; k < N_BSEQ; ++k) 
		for (j = 0; j < 3; ++j) BH[k][j] = 0;

	//First pixel in the first row
	curr = u2[1];
	temp = UPPER/4;
	err  = curr - temp;
	//NEARLY LOSSLESS COMPRESSION 
	#ifdef OPTION_NEARLY_LOSSLESS
	{
		err   = quant2 (err);
		recon = temp + err;
		if (recon < 0)     recon = 0;
		if (recon > UPPER) recon = UPPER;
		if (ABS (MaxError) < ABS (curr - recon)) MaxError = curr - recon;
		u2[0] = u2[1] = curr = recon;
	}
	#endif
	//NEARLY LOSSLESS COMPRESSION
	aerr = ABS (err);
	++H[3][nremap (err, temp)];
	encode_symbol (3, nremap (err, temp));

	//Second pixel in the first row
	w    = u2[1];
	curr = u2[2];
	temp = w;
	k = nh (aerr << 2);
	err  = curr - temp;
	//NEARLY LOSSLESS COMPRESSION
	#ifdef OPTION_NEARLY_LOSSLESS
	{
		err   = quant2 (err);
		recon = temp + err;
		if (recon < 0)     recon = 0;
		if (recon > UPPER) recon = UPPER;
		if (ABS (MaxError) < ABS (curr - recon)) MaxError = curr - recon;
		u2[2] = curr = recon;
	}
	#endif
	//NEARLY LOSSLESS COMPRESSION
	aerr = ABS (err);
	++H[k][nremap (err, temp)];
	encode_symbol (k, nremap (err, temp));

	//Rest of the first row
	for (x = 3; x <= width; ++x)
	{
		ww   = u2[x-2];
		w    = u2[x-1];
		curr = u2[x];
		temp = w;
		if (temp > UPPER)  temp = UPPER; 
		else if (temp < 0) temp = 0;
		k = nh ((aerr + ABS (ww - w)) << 2);
		err  = curr - temp;
		//NEARLY LOSSLESS COMPRESSION
		#ifdef OPTION_NEARLY_LOSSLESS
		{
			err   = quant2 (err);
			recon = temp + err;
			if (recon < 0)     recon = 0;
			if (recon > UPPER) recon = UPPER;
			if (ABS (MaxError) < ABS (curr - recon)) MaxError = curr - recon;
			u2[x] = curr = recon;
		}
		#endif
		//NEARLY LOSSLESS COMPRESSION
		aerr = ABS (err);
		++H[k][nremap (err, temp)];
		encode_symbol (k, nremap (err, temp));
	}
	//NEARLY LOSSLESS COMPRESSION
	#ifdef OPTION_NEARLY_LOSSLESS
	{
		u2[width+1] = u2[width];
	}
	#endif
	//NEARLY LOSSLESS COMPRESSION

	//Second row first pixel
	n    = u2[1];
	curr = u1[1];
	temp = n;
	//NEARLY LOSSLESS COMPRESSION
	#ifdef OPTION_NEARLY_LOSSLESS
	{
		err = curr - temp;
		err   = quant2 (err);
		recon = temp + err;
		if (recon < 0)     recon = 0;
		if (recon > UPPER) recon = UPPER;
		if (ABS (MaxError) < ABS (curr - recon)) MaxError = curr - recon;
		u1[0] = u1[1] = curr = recon;
		E0[1] = err;
	}
	#else
	E0[1] = err = curr - temp;
	#endif
	//NEARLY LOSSLESS COMPRESSION
	aerr  = ABS (err);
	++H[2][nremap (err, temp)];
	encode_symbol (2, nremap (err, temp));

	//Second row second pixel
	nw   = u2[1];
	n    = u2[2];
	ne   = u2[3];
	w    = u1[1];
	curr = u1[2];
	temp = (w + n + 1)/2 + (ne - nw)/4;
	if (temp > UPPER)  temp = UPPER; 
	else if (temp < 0) temp = 0;
	k = nh (aerr + ABS (n - nw) + ABS (n - ne) + 2*ABS (w - nw));
	//NEARLY LOSSLESS COMPRESSION
	#ifdef OPTION_NEARLY_LOSSLESS
	{
		err = curr - temp;
		err   = quant2 (err);
		recon = temp + err;
		if (recon < 0)     recon = 0;
		if (recon > UPPER) recon = UPPER;
		if (ABS (MaxError) < ABS (curr - recon)) MaxError = curr - recon;
		u1[2] = curr = recon;
		E0[2] = err;
	}
	#else
		E0[2] = err = curr - temp;
	#endif
	//NEARLY LOSSLESS COMPRESSION
	aerr  = ABS (err);
	++H[k][nremap (err, temp)];
	encode_symbol (k, nremap (err, temp));
	Dh[2] = ABS (curr - w);
	Dv[2] = ABS (curr - n);

	//2nd row
	for (x = 3; x <= width - 1; ++x)
	{
		nw   = u2[x-1];
		n    = u2[x];
		ne   = u2[x+1];
		ww   = u1[x-2];
		w    = u1[x-1];
		curr = u1[x];
		temp = (w + n + 1)/2 + (ne - nw)/4;
		if (temp > UPPER)  temp = UPPER; 
		else if (temp < 0) temp = 0;
		k = nh (aerr + ABS (ww - w) + ABS (n - nw) + ABS (n - ne) + 2*ABS (w - nw));
		//NEARLY LOSSLESS COMPRESSION
		#ifdef OPTION_NEARLY_LOSSLESS
		{
			err = curr - temp;
			err   = quant2 (err);
			recon = temp + err;
			if (recon < 0)     recon = 0;
			if (recon > UPPER) recon = UPPER;
			if (ABS (MaxError) < ABS (curr - recon)) MaxError = curr - recon;
			u1[x] = curr = recon;
			E0[x] = err;
		}
		#else
			E0[x] = err = curr - temp;

		#endif
		//NEARLY LOSSLESS COMPRESSION 
		aerr  = ABS (err);
		++H[k][nremap (err, temp)];
		encode_symbol (k, nremap (err, temp));
		Dh[x] = ABS (curr - w);
		Dv[x] = ABS (curr - n);
	}

	//Second row last pixel
	nw   = u2[width-1];
	n    = u2[width];
	ww   = u1[width-2];
	w    = u1[width-1];
	curr = u1[width];
	temp = (w + n + 1)/2;
	if (temp > UPPER)  temp = UPPER; 
	else if (temp < 0) temp = 0;
	k = nh (aerr + 2*ABS (ww - w) + 2*ABS (w - nw));
	//NEARLY LOSSLESS COMPRESSION
	#ifdef OPTION_NEARLY_LOSSLESS
	{
		err = curr - temp;
		err   = quant2 (err);
		recon = temp + err;
		if (recon < 0)     recon = 0;
		if (recon > UPPER) recon = UPPER;