ezwcode.cpp

零树编码源码

// EzwCode.cpp: implementation of the CEzwCode class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "ImageCode.h"
#include "EzwCode.h"

#include <math.h>

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

#define NUL -1
#define IZ  0
#define ZTR 1
#define POS 2
#define NEG 3
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CEzwCode::CEzwCode()
{
	
}

CEzwCode::~CEzwCode()
{
	//HeapFree(GetProcessHeap(),0,EzwDV);
	//HeapFree(GetProcessHeap(),0,EzwSV);
}

bool CEzwCode::EzwQualitition(int minthr,int datheight,int datwidth)
{
	int i,j,thr,tem,num[4]={0,0,0,0},totalnum=0;
	//int *BufIn,*BufBigIn;
	float pro[4];//各个符号出现的概率
	//read data
	//int *ptemp;
	 EzwIn=(int *)HeapAlloc(GetProcessHeap(),0,datheight*datwidth*sizeof(int));
	 EzwBigIn=(int *)HeapAlloc(GetProcessHeap(),0,datheight*datwidth*sizeof(int));
	//ptemp=EzwIn;
	CFile *Dat_File=new CFile();
	LPCTSTR lpszFilter="Disc Wavelet Trans Files(*.dwt)|*.dwt|任何文件|*.*||";
	CFileDialog *OpenDlg=new CFileDialog( TRUE, lpszFilter, "LENA",OFN_HIDEREADONLY|OFN_PATHMUSTEXIST|OFN_OVERWRITEPROMPT|OFN_NOCHANGEDIR, lpszFilter );
    if(OpenDlg->DoModal()==IDOK)
		Dat_File->Open(OpenDlg->GetPathName(),CFile::modeRead|CFile::typeBinary,NULL);
	else
		return 0;
	//int max=0;
	for(i=0;i<datheight;i++)
		for(j=0;j<datwidth;j++)
		{	//把数据读到EzwIn[256][256]中
			Dat_File->Read(&EzwIn[i*datwidth+j],sizeof(int));
			//EzwIn[i*datdidth,j
			//ptemp++;
			EzwBigIn[i*datwidth+j]=0;
			//TRACE("(%d %d)",EzwIn[i+datwidth+j],EzwBigIn[i*datwidth+j]);
			
		}
	delete OpenDlg;
	Dat_File->Close();
	delete Dat_File;
	//Produce DominateChart
	FirstFactor(datheight,datwidth,EzwIn);//找到最大值max,log2(max)向上取整－1
	
	Thresholdnum=TreFstFtr-minthr+1;
	
	BufDv=(int *)HeapAlloc(GetProcessHeap(),0,Thresholdnum*datheight*datwidth*sizeof(int));
		
		//生成对bufSv的二维数组索引：
		EzwDV=new int*[Thresholdnum];
		for(i=0;i<Thresholdnum;i++)
			EzwDV[i]=BufDv+i*datheight*datwidth;
	
	BufSv=(int *)HeapAlloc(GetProcessHeap(),0,Thresholdnum*datheight*datwidth*sizeof(int));
		
		//生成对bufSv的二维数组索引：
		EzwSV=new int*[Thresholdnum];
		
		for(i=0;i<Thresholdnum;i++)
			EzwSV[i]=BufSv+i*datheight*datwidth;
	//EzwDV=new int [Thresholdnum][datheight*datwidth];//初始化主附表
	//EzwSV=new int [Thresholdnum][datheight*datwidth];
	for(thr=TreFstFtr-minthr;thr>=0;thr--)
		for(i=0;i<datheight;i++)
			for(j=0;j<datwidth;j++)//将主附表都置零
			{
				EzwDV[thr][i*datwidth+j]=NUL;
				EzwSV[thr][i*datwidth+j]=NUL;
			}
	for(thr=TreFstFtr-minthr;thr>=0;thr--)
	{
		//处理主表
		for(i=0;i<datheight;i++)
			for(j=0;j<datwidth;j++)
				if(!PrtsIsZTR(thr,i,j,datheight,datwidth))
					//如果不是零树的子孙系数
					if(abs(EzwIn[i*datwidth+j])<(int)pow(2,thr+minthr))
						//如果绝对值小于当前阈值
						if(ChldIsMin(thr+minthr,i,j,datheight,datwidth))
							//如果子孙都小于阈值
						{
							EzwDV[thr][i*datwidth+j]=ZTR;
							//记为零树
							num[ZTR]++;
						}
						else
						{	//如果子孙系数有意义，记为孤立零点
							EzwDV[thr][i*datwidth+j]=IZ;
							num[IZ]++;
						}
					else//如果当前系数绝对值大于阈值
					{
						if(EzwIn[i*datwidth+j]>0)
							//为正数，记为P
						{
							EzwDV[thr][i*datwidth+j]=POS;
							num[POS]++;
						}
						else
						{	//为负数，记为N
							EzwDV[thr][i*datwidth+j]=NEG;
							num[NEG]++;
						}
						//将重要数据转移到EzeBigIn数组中，原数置零
						EzwBigIn[i*datwidth+j]=EzwIn[i*datwidth+j];//if not 0 this piont ready to produce sub-chart
						EzwIn[i*datwidth+j]=0;
					}
		//Produce sub-chart
		//处理附表
		if((thr!=0)||(minthr!=0))
			//不是最后一次，最小阈值不为零
			for(i=0;i<datheight;i++)
				for(j=0;j<datwidth;j++)
					if(EzwBigIn[i*datwidth+j]!=0)
						//对于重要系数表中的非零数，重新计算整个附表
						EzwSV[thr][i*datwidth+j]=CalSV(thr+minthr,i,j,datheight,datwidth);
	}
	
	HeapFree(GetProcessHeap(),0,EzwIn);
	HeapFree(GetProcessHeap(),0,EzwBigIn);
	
	//在记事本中显示主表
	char x;
    if((fp=fopen("EZWData.txt","w"))!=NULL)
	for(thr=TreFstFtr-minthr;thr>=0;thr--)
	{	
		fprintf(fp,"\n\n***threshold=%d***\n",thr);
		for(i=0;i<datheight;i++)
			for(j=0;j<datwidth;j++)
			{	
				switch(EzwDV[thr][i*datwidth+j])
				{
				case POS:	x='P';	break;
				case NEG:	x='N';	break;
				case ZTR:	x='T';	break;
				case IZ:	x='Z';	break;
				case NUL:	x=' ';	break;
				}
				if(j%8==0)
					if(j==0)
						fprintf(fp,"\n%c ",x);
					else
						fprintf(fp,"%c ",x);
				else	
					fprintf(fp,"%c ",x);
	
			}
	}
	fclose(fp);
	//WinExec("Notepad.exe EZWData.txt",SW_MAXIMIZE);
	
	
	//0，1，2，3 -> IZ,ZTR,POS,NEG
	for(i=0;i<4;i++)
		EzwDVOfPro[i]=i;//存放主表中四个符号出现概率的顺序
	for(i=0;i<4;i++)
		totalnum+=num[i];//总符号数
	for(i=0;i<4;i++)
		pro[i]=(float)num[i]/totalnum;//各个符号出现的概率
	//order Probability of dom chart value: IZ,ZTR,POS,NEG
	for(i=0;i<3;i++)
		for(j=i;j<4;j++)
			if(pro[i]<=pro[j])
				//将主表中四个符号的出现顺序从大到小排序
			{
				float temp=pro[i];
				tem=EzwDVOfPro[i];
				pro[i]=pro[j];
				EzwDVOfPro[i]=EzwDVOfPro[j];
				pro[j]=temp;
				EzwDVOfPro[j]=tem;
			}
	for(i=0;i<4;i++)
			TRACE("pro[%d]=%f,EzwDVOfPro[%d]=%d\n",i,pro[i],i,EzwDVOfPro[i]);
	return 1;
}

bool CEzwCode::HuffmanEncode(int minthr,int datheight,int datwidth)
{
	//build  output map:ZTR,POS,IZ,NEG->0,1,2,3
	
	int i,j,k,thr,OrdOfHuff[4];
	//int EzwDVOfPro[4];
	for(i=0;i<4;i++)
		OrdOfHuff[EzwDVOfPro[i]]=i;
	//输出1的个数，概率最大的为0个(ZTR)
	//最小的为3个，合乎huffman编码的规律
	//Write DV SV  to fp,in the sequence of common line and volumn
	mask = 0x80;
	output_byte = 0;
	ones=0;
	zeroes=0;

	
	CFile *pFile=new CFile();
	LPCTSTR lpszFilter="EZW Files(*.ezw)|*.ezw|任何文件|*.*||";
	CFileDialog *SaveDlg=new CFileDialog (FALSE, lpszFilter, "LENA",OFN_HIDEREADONLY|OFN_PATHMUSTEXIST|OFN_OVERWRITEPROMPT|OFN_NOCHANGEDIR,lpszFilter );
    if(SaveDlg->DoModal()==IDOK)
		pFile->Open(SaveDlg->GetPathName(),CFile::modeCreate |CFile::modeWrite|CFile::typeBinary,NULL);
	else
	{
		::AfxMessageBox("cannot open file to write !");
		return 0;
	}
	//if((fp=fopen("Huffman1.ezw","wb"))!=NULL)
	{
		TRACE("open file successfully !\n");
		//头文件
		pFile->Write (&TreFstFtr,sizeof(TreFstFtr));//实际上是int型变量，最大阈值
		//fwrite(&TreFstFtr,sizeof(TreFstFtr),1,fp);
		//for(i=0;i<4;i++)
		//	fwrite(&EzwDVOfPro[i],sizeof(int),1,fp);
		pFile->Write (EzwDVOfPro,4*sizeof(int));
		//四种符号从大到小的顺序，整数表示，参照头文件中的定义
		//文件数据
		for(thr=TreFstFtr-minthr;thr>=0;thr--)
		{
			//主表数据
			for(i=0;i<datheight;i++)
				for(j=0;j<datwidth;j++)
					if((EzwDV[thr][i*datwidth+j]<4)&&(EzwDV[thr][i*datwidth+j]>=0))
					{
						for(k=OrdOfHuff[EzwDV[thr][i*datwidth+j]];k>0;k--)
							PutBit('1',pFile);
						if((OrdOfHuff[EzwDV[thr][i*datwidth+j]]<3)&&(OrdOfHuff[EzwDV[thr][i*datwidth+j]]>=0))
							PutBit('0',pFile);
					}
			//附表数据
			if((thr!=0)||(minthr!=0))
				for(i=0;i<datheight;i++)
					for(j=0;j<datwidth;j++)
					{
						if(EzwSV[thr][i*datwidth+j]==0)
							PutBit('0',pFile);
						if(EzwSV[thr][i*datwidth+j]==1)
							PutBit('1',pFile);
					}
		}
	}
	
	//else
	//{
	//	::AfxMessageBox("can not create file!");
	//	return
	//		FALSE;
	//}


	//fclose(fp);
	
	HeapFree(GetProcessHeap(),0,BufSv);
	HeapFree(GetProcessHeap(),0,BufDv);
	//delete [] EzwSV;
	//delete [] EzwDV;
	delete [] EzwSV;
	delete [] EzwDV;
	//计算压缩率和bpp
	char temp[100];
	float compression,bpp;
	compression=(float)datheight*datwidth*8/(ones+zeroes);
	bpp=(float)(ones+zeroes)/datheight/datwidth;
    sprintf(temp,"compression:%2.2f,bpp: %1.2f",compression,bpp);
	::AfxMessageBox(temp);
	
	delete SaveDlg;
	pFile->Close();
	delete pFile;
	
	return 1;
}

bool CEzwCode::PrtsIsZTR(int thr,int i,int j,int datheight,int datwidth)
{	//判断某结点是否为零树的子孙
	if((i==0)&&(j==0))//根节点，非零树子孙
		return 0;
	int k=(int)floor(i/2);//父节点
	int l=(int)floor(j/2);
	if(EzwDV[thr][k*datwidth+l]==ZTR)//查找主系数表
		return 1;
	else
		return PrtsIsZTR(thr,k,l,datheight,datwidth);//递归调用
}

bool CEzwCode::ChldIsMin(int thr,int i, int j,int datheight,int datwidth)
//用于判定某节点为零树还是孤立零点(子孙是否量化为0)
{
	int k,l,ElgFactor=1;
	while((i<datheight/2)&&(j<datwidth/2))//在倒数第二层上截止