huffman coding.txt

有关图像处理的程序

// HuffmanCoding.cpp : implementation file
//

#include "stdafx.h"
#include "dimageprocess.h"
#include "HuffmanCoding.h"
#include "math.h"

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

/////////////////////////////////////////////////////////////////////////////
// CHuffmanCoding dialog


CHuffmanCoding::CHuffmanCoding(CWnd* pParent /*=NULL*/)
	: CDialog(CHuffmanCoding::IDD, pParent)
{
	//{{AFX_DATA_INIT(CHuffmanCoding)
	m_effection = 0.0;//初始化
	m_length = 0.0;	//初始化
	m_shang = 0.0;//初始化
	//}}AFX_DATA_INIT
}


void CHuffmanCoding::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CHuffmanCoding)
	DDX_Control(pDX, IDC_CODINGLIST, m_codinglist);
	DDX_Text(pDX, IDC_EFFECT, m_effection);
	DDX_Text(pDX, IDC_LENGTH, m_length);
	DDX_Text(pDX, IDC_SHANG, m_shang);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CHuffmanCoding, CDialog)
	//{{AFX_MSG_MAP(CHuffmanCoding)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHuffmanCoding message handlers

BOOL CHuffmanCoding::OnInitDialog() 
{
	CDialog::OnInitDialog(); //调用默认的对话框初始化函数
	int	i;			// 循环变量
	int	j;			// 循环变量
	int	k;			// 循环变量
	double *	temp;// 图像灰度出现概率中间结果的数组	
	int	*	turn;	// 数组用来存放灰度值和其位置之间的对应关系		
	m_strCode = new CString[graygrade];	// 分配内存
	turn  = new int[graygrade];	// 分配内存
	temp = new double[graygrade];	// 分配内存
	for (i = 0; i < graygrade; i ++)
	{
		temp[i] = grayfreq[i]; //将grayfreq的值传给temp
		turn[i] = i;			//记录灰度位置
	}	
		
	double te;// 中间变量
	// 用冒泡法对进行灰度值出现的概率排序从小到大
	// 同时改变灰度值位置的映射关系
	for (j = 0; j < graygrade - 1; j ++)
	{
		for (i = 0; i < graygrade - j - 1; i ++)
		{
			if (temp[i] > temp[i + 1])//如果前面的值大于后面的值
			{
				te = temp[i];
				temp[i] = temp[i + 1];//二者的值互换
				temp[i + 1] = te;
				
				// 将i和i+1灰度的位置值互换
				for (k = 0; k < graygrade; k ++)
				{				
					if (turn[k] == i)
						turn[k] = i + 1;
					else if (turn[k] == i + 1)
						turn[k] = i;
				}
			}
		}
	}
	
	
	// 从灰度概率大于0处开始编码
	for (i = 0; i < graygrade - 1; i ++)
	{
		if (temp[i] > 0)
			break;
	}
	
	for (; i < graygrade - 1; i ++)
	{
		// 更新m_strCode
		for (k = 0; k < graygrade; k ++)
		{
			// 灰度值是否i
			if (turn[k] == i)
			{
				// 灰度值较小的码字加1
				m_strCode[k] = "1" + m_strCode[k];
			}
			else if (turn[k] == i + 1)
			{
				// 灰度值较大的码字加0
				m_strCode[k] = "0" + m_strCode[k];
			}
		}
		
		// 概率最小的两个概率相加，保存在temp[i + 1]中
		temp[i + 1] = temp[i]+temp[i + 1];
		
		// 改变映射关系
		for (k = 0; k < graygrade; k ++)
		{
			// 将位置为i的灰度值i改为灰度值i+1
			if (turn[k] == i)
			{
				turn[k] = i + 1;
			}
		}
		
		// 重新排序 从i＋1开始
		for (j = i + 1; j < graygrade - 1; j ++)
		{
			if (temp[j] > temp[j + 1])
			{
				// 互换
				te = temp[j];
				temp[j] = temp[j + 1];
				temp[j + 1] = te;
				
				// // 将i和i+1灰度的位置值互换
				for (k = 0; k < graygrade; k ++)
				{
					if (turn[k] == j)
					{
						turn[k] = j + 1;
					}
					else if (turn[k] == j + 1)
					{
						turn[k] = j;
					}
				}
			}
			else
				// 退出循环
				break;
		}
	}
	
	// 计算图像熵
	for (i = 0; i < graygrade; i ++)
	{
		if (grayfreq[i] > 0)
		{
			// 计算图像熵
			m_shang -= grayfreq[i] * log(grayfreq[i]) / log(2.0);
		}
	}

	// 计算平均码字长度
	for (i = 0; i < graygrade; i ++)
	{
		// 累加
		m_length += grayfreq[i] * m_strCode[i].GetLength();
	}
	
	// 计算编码效率
	m_effection = m_shang / m_length;
	
	// 保存变动
	UpdateData(FALSE);
	// 字符串变量，列表项目的显示
	CString	listname;
	// 控件CodingList的ITEM
	LV_ITEM codingItem;
	// 保存控件ListCtrl中添加的ITEM编号
	int		nItem2View;	
	// 设置CListCtrl控件样式
	m_codinglist.ModifyStyle(LVS_TYPEMASK, LVS_REPORT);
	
	// 给List控件添加Header
	m_codinglist.InsertColumn(0, "像素灰度", LVCFMT_LEFT, 70, 0);
	m_codinglist.InsertColumn(1, "灰度概率", LVCFMT_LEFT, 70, 0);
	m_codinglist.InsertColumn(2, "编码码字", LVCFMT_LEFT, 90, 1);
	m_codinglist.InsertColumn(3, "码字长度", LVCFMT_LEFT, 60, 2);

	// 设置样式为文本
	codingItem.mask = LVIF_TEXT;
	// 添加显示
	for (i = 0; i < graygrade; i ++)
	{
		// 第一列显示
		codingItem.iItem = m_codinglist.GetItemCount();
		listname.Format("%u",i);
		codingItem.iSubItem = 0;
		codingItem.pszText= (LPTSTR)(LPCTSTR)listname;//显示像素灰度
		nItem2View = m_codinglist.InsertItem(&codingItem);
		codingItem.iItem = nItem2View;	
		// 第二列显示
		codingItem.iSubItem = 1;
		listname.Format("%f",grayfreq[i]);
		codingItem.pszText = (LPTSTR)(LPCTSTR)listname;
		m_codinglist.SetItem(&codingItem);
		
		// 第三列显示
		codingItem.iSubItem = 2;
		codingItem.pszText = (LPTSTR)(LPCTSTR)m_strCode[i];
		m_codinglist.SetItem(&codingItem);
		
		// 第四列显示
		codingItem.iSubItem = 3;
		listname.Format("%u",m_strCode[i].GetLength());
		codingItem.pszText = (LPTSTR)(LPCTSTR)listname;
		m_codinglist.SetItem(&codingItem);
	}	

	//  内存释放
	delete turn;
	delete temp;
	
	// 返回TRUE
	return TRUE;

}