dlghuffman.cpp

是一种采用哈夫曼算法的图像压缩算法

// DlgHuffman.cpp : implementation file
//

#include "stdafx.h"
#include "ImageProcess.h"
#include "ImageProcessDoc.h"
#include "DlgHuffman.h"
#include "dibapi.h"
#include <math.h>
#include <iostream.h>

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

/////////////////////////////////////////////////////////////////////////////
// CDlgHuffman dialog


CDlgHuffman::CDlgHuffman(CWnd* pParent /*=NULL*/)
	: CDialog(CDlgHuffman::IDD, pParent)
{	
	//{{AFX_DATA_INIT(CDlgHuffman)
	m_dEntropy=0.0;
	m_dAvgCodeLen=0.0;
	m_dEfficiency=0.0;
	//}}AFX_DATA_INIT

}


void CDlgHuffman::DoDataExchange(CDataExchange* pDX)
{

	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CDlgHuffman)
	DDX_Control(pDX,IDC_LST_TABLE,m_lstTable);
	DDX_Text(pDX,IDC_EDIT1,m_dEntropy);
	DDX_Text(pDX,IDC_EDIT2,m_dAvgCodeLen);
	DDX_Text(pDX,IDC_EDIT3,m_dEfficiency);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CDlgHuffman, CDialog)
	//{{AFX_MSG_MAP(CDlgHuffman)
		// NOTE: the ClassWizard will add message map macros here
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDlgHuffman message handlers

BOOL CDlgHuffman::OnInitDialog()
{ CString str;//字符串变量
  
  unsigned int i,j; //循环变量
  
  float leastFreq1=1,leastFreq2=1;//进行哈夫曼编码时存放概率最小的两个
  unsigned int leastNum1=0,leastNum2=0;    //存放概率最小的两个的下标
  int temp;     //哈夫曼编码时的中间变量，记载各个结点的父亲

  LV_ITEM lvitem;
  int iActualItem;

  CDialog::OnInitDialog ();

  m_dEntropy=0.0;//初始化变量
  m_dAvgCodeLen=0.0;
  

  for(i=1;i<=m_iColorNum;i++)//计算图像熵
	  m_dEntropy-=m_fFreq[i].freq *log(m_fFreq[i].freq )/log(2.0);

  
  for(i=m_iColorNum+1;i<2*m_iColorNum;i++)
  { //以下在前1-（i-1）个元素中查找概率最小的两个
    for(j=1;j<i;j++)
	{ if(m_fFreq[j].freq <leastFreq1 && m_fFreq[j].parent ==0)
		{
		  leastFreq1=m_fFreq[j].freq ;
		  leastNum1=j;
		}
	}
	for(j=1;j<i;j++)
	{ if(m_fFreq[j].freq<leastFreq2 && m_fFreq[j].parent ==0 && j!=leastNum1)
		{ leastFreq2=m_fFreq[j].freq ;
		  leastNum2=j;
		}
	}
    
	m_fFreq[leastNum1].parent =i;
	m_fFreq[leastNum2].parent =i;
	m_fFreq[i].lchild =leastNum1;
	m_fFreq[i].rchild =leastNum2;
	m_fFreq[i].freq =m_fFreq[leastNum1].freq +m_fFreq[leastNum2].freq;
	leastFreq1=1;
  	leastFreq2=1;
	leastNum1=0;
  	leastNum2=0;
  }

  
  m_strCode=new CString[m_iColorNum];  //对灰度值开始编码
  
  
  for(i=1;i<=m_iColorNum;i++)  
  { for(j=i,temp=m_fFreq[i].parent; temp!=0; j=temp,temp=m_fFreq[temp].parent)
	{ 
	  if(m_fFreq[temp].lchild ==j)
		  m_strCode[i-1]="0"+m_strCode[i-1];
	  else if(m_fFreq[temp].rchild ==j)
		      m_strCode[i-1]="1"+m_strCode[i-1];
	}
  }
  
  for(i=1;i<=m_iColorNum;i++)//计算平均码长
      m_dAvgCodeLen+=m_fFreq[i].freq *m_strCode[i-1].GetLength();
  
   m_dEfficiency=m_dEntropy/m_dAvgCodeLen;//计算编码效率
   UpdateData(FALSE); //保存变动
 
   //输出编码结果

   //设置List控件样式
   m_lstTable.ModifyStyle(LVS_TYPEMASK,LVS_REPORT);

   //给List控件添加Header
   m_lstTable.InsertColumn(0,"灰度值",LVCFMT_LEFT,60,0);
   m_lstTable.InsertColumn(1,"出现频率",LVCFMT_LEFT,78,0);
   m_lstTable.InsertColumn(2,"哈夫曼编码",LVCFMT_LEFT,110,1);
   m_lstTable.InsertColumn(3,"码字长度",LVCFMT_LEFT,78,2);
   
   //设置样式为文本
   lvitem.mask=LVIF_TEXT;

   //计算平均码字长度
   for(i=0;i<m_iColorNum;i++)
   { //添加一项
	 lvitem.iItem=m_lstTable.GetItemCount( );
	 str.Format("%u",m_fFreq[i+1].GrayValue );
	 lvitem.iSubItem=0;
	 lvitem.pszText=(LPSTR)(LPCTSTR)str;
	 iActualItem=m_lstTable.InsertItem(&lvitem);

	 //添加其他列
	 lvitem.iItem=iActualItem;

	 //添加灰度值出现的概率
	 lvitem.iSubItem=1;
	 str.Format("%f",m_fFreq[i+1].freq );
	 lvitem.pszText=(LPTSTR)(LPCTSTR)str;
	 m_lstTable.SetItem(&lvitem);

	 //添加哈夫曼编码
	 lvitem.iSubItem=2;
	 lvitem.pszText=(LPTSTR)(LPCTSTR)m_strCode[i];
	 m_lstTable.SetItem (&lvitem);

	 //添加码字长度
	 lvitem.iSubItem=3;
	 str.Format("%u",m_strCode[i].GetLength ());
	 lvitem.pszText=(LPTSTR)(LPCTSTR)str;
	 m_lstTable.SetItem(&lvitem);
   }
   return TRUE;
}