spihtcoder.cpp

小波图像编码中SPIHT算法的C++实现源码

// SPIHTCoder.cpp: implementation of the CSPIHTCoder class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "SPIHTCoder.h"
#include "mainfrm.h"
#include "ImgPro.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CSPIHTCoder::CSPIHTCoder()
{
	strFileNameOut = "c:\\out.spi";
	strFileNameIn = "c:\\out.spi";
	pNewlyAppended = NULL;
	cAction = TO_DISK;
	SPIHTFile = NULL;
	MR = NULL;
	M = NULL;
	LIS = NULL;
	LIP = NULL;
	LSP = NULL;
	CompressedFileInfo.pFirstByte = NULL;
	pByte = NULL;
}

CSPIHTCoder::~CSPIHTCoder()
{
	if(LSP!=NULL)
		delete LSP;
	if(LIP!=NULL)
		delete LIP;
	if(LIS!=NULL)
		delete LIS;
	if(M!=NULL)
		delete M;
	if(MR!=NULL)
		delete MR;
/*	if(pByte!=NULL){
		delete[] pByte;
		pByte = NULL;
	}*/
}


void CSPIHTCoder::PutBit(char bit)
{	
    static unsigned long lTotalBits = (unsigned long)(nYDim*nXDim*BitRate);
	if((zeroes+ones)>lTotalBits){
		stop = 1; 
		return;
	}
	
	if (bit==1){ 
		outputbyte |= mask;
		ones++;
	}
	else
		zeroes++;
	mask >>= 1;
	static long lByteCount = -1;
	if (mask==0) {
		lByteCount++;
		*pByte = outputbyte;
		pByte++;
		outputbyte = 0;
		mask = 0x80;
	}
}

void CSPIHTCoder::DumpBuffer()
{
	if(mask!=0)
		*pByte = outputbyte; 
	
}

void CSPIHTCoder::Initialization()
{
	/* Create and initialize list LSP */
	CLinkList::ListType d;
	LSP = new CLinkList;
	LSP->Create();

    /* Create and initialize list LIP
	LIP = new CLinkList;
	LIP->Create();
	int i,j;
	for(j=0;j<(nYDim>>level);j++)
		for(i=0;i<(nXDim>>level);i++){
			d.x = i;
			d.y = j;
			LIP->Append(d);
		}	 */
		/* Create and initialize list LIP*/
	LIP = new CLinkList;
	LIP->Create();

		d.x = 0;
		d.y = 0;
		LIP->Append(d);
		d.x = 1;
		d.y = 0;
		LIP->Append(d);
		d.x = 0;
		d.y = 1;
		LIP->Append(d);
		d.x = 1;
		d.y = 1;
		LIP->Append(d); 
		
		
		/* Create and initialize list LIS
		LIS = new CLinkList;
		LIS->Create();
		
		for(j=0;j<(nYDim>>(level+1));j++){
			for(i=(nXDim>>(level+1));i<(nXDim>>level);i++){
				d.x = i;
				d.y = j;
				d.type = TYPE_A;
				LIS->Append(d);
			}
		}
		
		for(j=(nYDim>>(level+1));j<(nYDim>>level);j++){
			for(i=0;i<(nXDim>>(level+1));i++){
				d.x = i;
				d.y = j;
				d.type = TYPE_A;		
				LIS->Append(d);
			}
		}
		
		for(j=(nYDim>>(level+1));j<(nYDim>>level);j++){
			for(i=(nXDim>>(level+1));i<(nXDim>>level);i++){
				d.x = i;
				d.y = j;
				d.type = TYPE_A;	
				LIS->Append(d);
			}
		} */
		
		/* Create and initialize list LIS */
		LIS = new CLinkList;
		LIS->Create();
		d.x = 1;
		d.y = 0;
		d.type = TYPE_A;
		LIS->Append(d);
		d.x = 0;
		d.y = 1;
		LIS->Append(d);
		d.x = 1;
		d.y = 1;
		LIS->Append(d);  

		
}

BOOL CSPIHTCoder::ZeroTree(CMatrix2D<ElementType> *m, int x, int y, int threshold)
{
	int i, j, min_x, max_x, min_y, max_y;
	ElementType temp, max;
	char stop;
	
	stop = 0;
	if ((x==0) && (y==0)) {
		temp = m->m[0][0];
		m->m[0][0] = 0;
		max = m->MaxMagnitude();
		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);//original
	//return (0);
}

BOOL CSPIHTCoder::TestSubset(CMatrix2D<ElementType> *m, int x, int y, int threshold, unsigned char type)
{
    int i, j, stop;
	stop = 0;
	if(type==TYPE_A)
	   return(!ZeroTree(m,x,y,threshold));
	else
	{
		for(i=2*x; i<2*x+2; i++)
		{
		  for(j=2*y; j<2*y+2; j++)
		  {
		      if(!ZeroTree(m,i,j,threshold))
			  {
				  stop = 1;
				  break;
			  }
		  }
		  if(stop==1)
			  break;
		}
	  if(stop==1)
		 return 1;
	  else
		 return 0;
	}
}

void CSPIHTCoder::SortingPass1(CMatrix2D<ElementType> *m, int threshold)
{
	int temp, s, i, j;
	char found;
	CLinkList::ListType d, d1;
	if(stop==1)
		return;
    pNewlyAppended = LSP->end;

	/* Deal with elements in the LIP */
	LIP->Reset();
	while(LIP->current!=NULL)
	{
		d = LIP->GetCurrentElement(&found);
		if(found==0){
			MessageBox(NULL,"Can't retrieve current list element..",
				"Warning!",MB_OK);
			return;
		}
		temp = m->m[d.y][d.x];
		if(abs(temp)<threshold) {
			PutBit(0);
			if(stop==1)
				return;
			LIP->current = LIP->current->next;
		}
		else
		{
			PutBit(1);
			if(temp>0)
				PutBit(1);
			else
				PutBit(0);
			if(stop==1)
				return;
			LIP->RemoveCurrentElement();
			LSP->Append(d);
		}
	}
	LIP->Reset();
	
	/* Deal with elements in the LIS */
	LIS->Reset();
	while(LIS->current!=NULL)
	{
		d = LIS->GetCurrentElement(&found);
		if(found==0){
			MessageBox(NULL,"Can't retrieve current list element.",
				NULL,MB_OK);
			return;
		}
		s = TestSubset(m,d.x,d.y,threshold,d.type);
		if(d.type==TYPE_A)
		{
			PutBit((char)s);
			if(stop==1)
				return;
			if(s==1)
			{
				for(j=2*d.y; j<2*d.y+2; j++) {
					for(i=2*d.x; i<2*d.x+2; i++)
					{
						d1.x = i;
						d1.y = j;
						temp = m->m[j][i];
						if(abs(temp)>=threshold)
						{
							PutBit(1);
							if(stop==1)
								return;
							LSP->Append(d1);
							if(temp>0)
								PutBit(1);
							else
								PutBit(0);
							if(stop==1)
								return;

						}
						else {
							PutBit(0);
							if(stop==1)
								return;
							LIP->Append(d1);
						}
					}
				}
				if(4*d.x+4<=m->col && 4*d.y+4<=m->row)
				{
					d1 = d;
					d1.type = TYPE_B;
					LIS->Append(d1);
				}
				LIS->RemoveCurrentElement();
			}
			else
				LIS->current =  LIS->current->next;
		}
		else
		{
			PutBit((char)s);
			if(stop==1)
				return;
			if(s==1)
			{
				for(j=2*d.y;j<2*d.y+2;j++)
					for(i=2*d.x;i<2*d.x+2;i++)
					{
						d1.x = i;
						d1.y = j;
						d1.type = TYPE_A;
						LIS->Append(d1);
					}
					LIS->RemoveCurrentElement();
			}
			else
				LIS->current = LIS->current->next;
		}
	}
	LIS->Reset();
	
}

void CSPIHTCoder::RefinementPass1(CMatrix2D<ElementType> *m, int threshold)
{
   CLinkList::ListElement *p;
   int temp;
   if(pNewlyAppended==NULL)
	   return;
   p = LSP->head;
   while(p!=pNewlyAppended->next)
   {  
	  temp = threshold & abs(m->m[p->data.y][p->data.x]);
	  if(temp==0)
	     PutBit(0);
	  else
		 PutBit(1);
	  if(stop==1)
		  return;
	  p = p->next;
   }

}

void CSPIHTCoder::Encode(ElementType *example)
{
  int threshold, pass_count;
  /*
   * Build work matrix.
   */
  header.height = nXDim;
  header.width = nYDim;
  header.BitRate = BitRate;
  header.level = level;
  header.selection = selection;
  M = new CMatrix2D<ElementType>;
  M->Create(header.height,header.width);
  if (M==NULL) {
	  MessageBox(NULL,"Failed to create matrix!","Warning!",MB_OK);
	  return;
  }
  M->LoadData(example,nYDim,nXDim);
  /*
   * Prepare output file.
   */
  int nInit = (int)(floor(log10(M->MaxMagnitude())/log10(2)));
  header.threshold = 1 << nInit;
  threshold = header.threshold;
 
  CompressedFileInfo.header = header;
  CompressedFileInfo.lCounts = int(ceil(BitRate*nXDim*nYDim/8.0));


  CompressedFileInfo.pFirstByte = new unsigned char[CompressedFileInfo.lCounts];

  pByte = CompressedFileInfo.pFirstByte;

  outputbyte = 0;
  mask = 0x80;
  pass_count = 0;
  stop = 0;
  zeroes = 0;
  ones = 0;

  /*
   * Do the SPIHT coding.
   */
  Initialization();

  while(threshold!=0)
  {
     pass_count++;
	 SortingPass1(M,threshold);
	 RefinementPass1(M,threshold);
     	 threshold >>= 1;
	 if(stop==1)
		 break;
  }
   DumpBuffer();
   
   if(cAction ==TO_DISK)
   {
	   SPIHTFile=fopen(strFileNameOut,"wb");
	   ASSERT(SPIHTFile);
	   pByte = CompressedFileInfo.pFirstByte;
	   fwrite(&CompressedFileInfo,1,sizeof(CompressedFileInfo),SPIHTFile);
	   fwrite(pByte,1,CompressedFileInfo.lCounts,SPIHTFile);
	   fclose(SPIHTFile);
   }
   M->Destroy();
   LIP->Destroy();
   LIS->Destroy();
   LSP->Destroy();
}


void CSPIHTCoder::Decode()
{
  int threshold, pass_count;

  /*
  * Read the file header.
  */
  if(cAction ==	FROM_DISK){ 
	  SPIHTFile = fopen(strFileNameIn,"rb");
	  ASSERT(SPIHTFile);
	  fread(&CompressedFileInfo,sizeof(CSPIHTFileInfo),1,SPIHTFile);
	  header = CompressedFileInfo.header;
	  SetLevel(header.level);
	  SetBitRate(header.BitRate);
	  SetImageSize(header.height,header.width);

	  CompressedFileInfo.pFirstByte = new unsigned char[CompressedFileInfo.lCounts];
	  fread(CompressedFileInfo.pFirstByte,1,CompressedFileInfo.lCounts,SPIHTFile);
  }
  else{
  	  SetLevel(level);
	  SetBitRate(BitRate);
	  SetImageSize(nXDim,nYDim);
  }
  pByte = CompressedFileInfo.pFirstByte;
  selection = CompressedFileInfo.header.selection;
  /*
  * Parepare matrix which contains data reconstructed.
  */
  MR = new CMatrix2D<ElementType>;
  MR->Create(header.height,header.width);
  if (MR==NULL) 
	  MessageBox(NULL,"Failed to create matrix!!","Warning!",MB_OK);
  MR->Clear();

  /*
   * Prepare to decoding input file.
   */
  threshold = header.threshold;
  inputbyte = 0;
  mask = 0;
  BitCount = 0;
  zeroes = 0;
  ones = 0;
  stop = 0;


  /*
   * Do the SPIHT decoding.
   */
  Initialization();
  pass_count = 0;
  while(threshold!=0) 
  {
	 pass_count++;
     SortingPass2(MR,threshold);
	 RefinementPass2(MR,threshold);
	 threshold >>= 1;
  }

  if(cAction == FROM_DISK)
	  fclose(SPIHTFile);

  /*
  * Release memory used.
  */
   LIP->Destroy();
   LIS->Destroy();
   LSP->Destroy();
   pByte = CompressedFileInfo.pFirstByte;
}

char CSPIHTCoder::GetBit()
{
	char bit;
	static long lByteCount = -1;
	static unsigned long lTotalBits = (unsigned long)ceil(nYDim*nXDim*m_fDecomBitRate);
	if (mask==0) {
		lByteCount++;
        inputbyte = *pByte;
		pByte++;
		mask = 0x80;
		
	}

	if(BitCount>lTotalBits){
		stop = 1;
		return 0;
	}

	if ((inputbyte&mask)==0)
		bit = 0;
	else
		bit = 1;
	mask >>= 1;
	BitCount++;
	
	return (bit);
}

void CSPIHTCoder::SortingPass2(CMatrix2D<ElementType> *m, int threshold)
{
	int temp, s, i, j;
	char found;
	CLinkList::ListType d, d1;

	pNewlyAppended = LSP->end;
	/* Deal with elements in the LIP */
	if(stop==1)
		return;
	while(LIP->current!=NULL)
	{
		d = LIP->GetCurrentElement(&found);
		if(found==0){
			MessageBox(NULL,"error!can't get list element!\n",
				"Warning!",MB_OK);
			return;
		}
		s = GetBit();
		if(stop==1)
			return;
		if(s==0) {
			LIP->current = LIP->current->next;
		}
		else
		{
			LIP->RemoveCurrentElement();
			LSP->Append(d);
			s = GetBit();
			if(stop==1)
				return;
			temp = threshold+(threshold>>1);
			if(s==1)
				m->m[d.y][d.x] = temp;
			else
				m->m[d.y][d.x] = -temp;
			
		}
	}
	LIP->Reset();
	
	/* Deal with elements in the LIS */
	while(LIS->current!=NULL)
	{
		d = LIS->GetCurrentElement(&found);
		if(found==0) {
			MessageBox(NULL,"error!can't get list element!\n",
				"Warning!",MB_OK);
			return;
		}
		if(d.type==TYPE_A)
		{
			s = GetBit();
			if(stop==1)
				return;
			if(s==1)
			{
				for(j=2*d.y; j<2*d.y+2; j++) {
					for(i=2*d.x; i<2*d.x+2; i++){
						d1.x = i;
						d1.y = j;
						s = GetBit();
						if(stop==1)
							return;
						if(s==1){
							LSP->Append(d1);
							s = GetBit();
						    if(stop==1)
							  return;
							temp = threshold+(threshold>>1); 
							if(s==1)
								m->m[j][i] = temp;
							else
								m->m[j][i] = -temp;
							
						}
						else{
							LIP->Append(d1);
						}				  
					}
				}
				if(4*d.x+4<=m->col && 4*d.y+4<=m->row)
				{
					d1 = d;
					d1.type = TYPE_B;
					LIS->Append(d1);
				}
				LIS->RemoveCurrentElement();
			}
			else
				LIS->current =  LIS->current->next;
		}
		else
		{
			s = GetBit();
			if(stop==1)
				return;
			if(s==1)
			{
				for(j=2*d.y;j<2*d.y+2;j++)
					for(i=2*d.x;i<2*d.x+2;i++)
					{
						d1.x = i;
						d1.y = j;
						d1.type = TYPE_A;
						LIS->Append(d1);
					}
					LIS->RemoveCurrentElement();
			}
			else
				LIS->current = LIS->current->next;
		}
	}
	LIS->Reset();
}

void CSPIHTCoder::RefinementPass2(CMatrix2D<ElementType> *m, int threshold)
{
	CLinkList::ListElement *p;
	int s, i, j,temp;
	if(pNewlyAppended==NULL)
	  return;
	p = LSP->head;

	while(p!=pNewlyAppended->next)
	{  
		s = GetBit();
		if(stop==1)
			return;
		i = p->data.x;
		j = p->data.y;
		temp = abs(m->m[j][i]);
		if(s==1)
			temp |= (threshold>>1);
		else{
			temp &= (~threshold);
			temp |= (threshold>>1);
		}
		if(m->m[j][i]>=0)
			m->m[j][i] = temp;
		else
			m->m[j][i] = -temp;
		p = p->next;
	}
}

void CSPIHTCoder::SetBitRate(float b)
{
   BitRate = b;
}

void CSPIHTCoder::SetLevel(char l)
{
    level = l;
}

void CSPIHTCoder::SetImageSize(int x, int y)
{
   nXDim = x;
   nYDim = y;
}