spihtcoder.cpp

可用的基于小波的spiht算法

// 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 = "E:\\out.spiht";
	strFileNameIn = "E:\\out.spiht";
	pNewlyAppended = NULL;
	SPIHTFile = NULL;
	MR = NULL;
	M = NULL;
	LIS = NULL;
	LIP = NULL;
	LSP = NULL;
	CompressedFileInfo.pFirstByte = 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;

}


void CSPIHTCoder::PutBit(char bit)
{	
    if (bit==1)
	{ 
		outputbyte|= mask;
		ones++;
	}
	else
		zeroes++;
	mask >>= 1;
	static long lByteCount = -1;
	if (mask==0)
	{
		lByteCount++;
		fwrite(&outputbyte,sizeof(unsigned char),1,SPIHTFile);
		counts++;
		outputbyte = 0;
		mask = 0x80;
	}
}

void CSPIHTCoder::DumpBuffer()
{
	if(mask!=0)
	fwrite(&outputbyte,sizeof(unsigned char),1,SPIHTFile);
	counts++;
}

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();

		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();
		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);
}

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;
   }

}




char CSPIHTCoder::GetBit()
{
	char bit;
	static long lByteCount = -1;
	if (mask==0) 
	{
		lByteCount++;
        fread(&inputbyte,sizeof(unsigned char),1,SPIHTFile);
   		mask = 0x80;
	}

	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::SetImageSize(int x, int y)
{
   nXDim = x;
   nYDim = y;
}


void CSPIHTCoder::Losslessencode(ElementType *example, int width, int height)
{
  SPIHTFile=fopen(strFileNameOut,"wb");
  SetImageSize(height, width);
  M = new CMatrix2D<ElementType>;
  M->Create(height,width);
  if (M==NULL)
  {
	  MessageBox(NULL,"Failed to create matrix!","Warning!",MB_OK);
	  return;
  }
  M->LoadData(example,height,width);
  
  /*计算阈值*/
  int nInit = (int)(floor(log10(M->MaxMagnitude())/log10(2)));
  threshold = 1 << nInit;
  
  outputbyte = 0;
  counts=0;
  mask = 0x80;
  stop = 0;
  zeroes = 0;
  ones = 0;

  /*初始化*/
  Initialization();

  while(threshold!=0)
  {
     SortingPass1(M,threshold);
	 RefinementPass1(M,threshold);
     threshold >>= 1;
	 
  }
 
  DumpBuffer();
   fclose(SPIHTFile);
   
   threshold = 1 << nInit;
   M->Destroy();
   LIP->Destroy();
   LIS->Destroy();
   LSP->Destroy();
}

void CSPIHTCoder::Losslessdecoder(int width, int height, int threshold)
{
  SPIHTFile=fopen(strFileNameIn,"rb");
  SetImageSize(height,width);
  
  MR = new CMatrix2D<ElementType>;
  MR->Create(height,width);
  if (MR==NULL) 
	  MessageBox(NULL,"Failed to create matrix!!","Warning!",MB_OK);
  MR->Clear();

  inputbyte = 0;
  mask = 0;
  BitCount = 0;
  zeroes = 0;
  ones = 0;
  stop = 0;

  Initialization();
  while(threshold!=0) 
  {
     SortingPass2(MR,threshold);
	 RefinementPass2(MR,threshold);
	 threshold >>= 1;
  }
  
  fclose(SPIHTFile);
  LIP->Destroy();
  LIS->Destroy();
  LSP->Destroy();
}