当前位置：文档之家 › 实验2图像的哈夫曼编码实现

实验2图像的哈夫曼编码实现

  • 格式：doc
  • 大小：139.50 KB
  • 文档页数：15

实验二 图像的哈夫曼编码实现 实验目的： 使学生掌握图像的哈夫曼编码及哈夫曼编码的实现过程。 实验环境： 具有多媒体处理功能的计算安装有Windows操作系统，安装有Visual c++6.0程序设计软件。

实验要求： 学习相关理论指导，掌握相关程序设计知识；按照实验步骤要求完成程序设计任务，书写实验报告，试验报告中要求包含程序实现的主要程序代码和程序运行结果或结果说明。

实验内容和实验步骤： 1、使用应用程序向导生成哈夫曼编码程序框架和用于数据显示的界面。

1）创建多文档应用程序:HuffmanExp （1）使用资源管理制作对话框IDD_DLG_HUFFMAN 资源号分别为：IDC_LST_Table，IDC_EDIT1，IDC_EDIT2，IDC_EDIT3 （2）对应的数据成员定义为： CListCtrl m_lstTable; double m_dEntropy; double m_dAvgCodeLen; double m_dEfficiency; （3）为该对话框定义类CDlgHuffman class CDlgHuffman : public CDialog { // Construction public: CDlgHuffman(CWnd* pParent = NULL); // standard constructor

// Dialog Data //{{AFX_DATA(CDlgHuffman) enum { IDD = IDD_DLG_HUFFMAN }; CListCtrl m_lstTable; double m_dEntropy; double m_dAvgCodeLen; double m_dEfficiency; //}}AFX_DATA

public: // 灰度级别数目 int m_iColorNum;

// 各个灰度值出现频率 FLOAT * m_fFreq;

// 哈夫曼编码表 CString * m_strCode; // Overrides // ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CDlgHuffman) protected: virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support //}}AFX_VIRTUAL

// Implementation protected:

// Generated message map functions //{{AFX_MSG(CDlgHuffman) virtual BOOL OnInitDialog(); //}}AFX_MSG DECLARE_MESSAGE_MAP() }; 3）使用文件菜单打开位图文件，实现参考代码为重载文档类的Serialize(CArchive& ar)函数 void CHuffmanExpDoc::Serialize(CArchive& ar) { m_pDib->Serialize(ar);------不理解 if (ar.IsStoring()) { // TODO: add storing code here } else { // TODO: add loading code here } } 其中m_pDib为CDib类型对象。 4）重载视图类的OnInitialUpdate()函数，用于获取DIB文件的信息来设置滚动显示范围。----视图类中缺少Inintial函数 void CHuffmanExpView::OnInitialUpdate() { CScrollView::OnInitialUpdate(); CHuffmanExpDoc* pDoc = GetDocument(); CSize sizeTotal(pDoc->m_pDib->GetWidth(), pDoc->m_pDib->GetHeight()); SetScrollSizes(MM_TEXT, sizeTotal);

CMainFrame* pAppFrame = (CMainFrame*) AfxGetApp()->m_pMainWnd; ASSERT_KINDOF(CMainFrame, pAppFrame); CRect rc; pAppFrame->GetClientRect(&rc); if (rc.Width() >= sizeTotal.cx && rc.Height() >= sizeTotal.cy && (sizeTotal.cx>0 || sizeTotal.cy>0)) ResizeParentToFit(FALSE);

} 5）重载视图类的OnDraw(CDC* pDC)函数实现图像显示。 void CHuffmanExpView::OnDraw(CDC* pDC) { CHuffmanExpDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); // TODO: add draw code for native data here if (! pDoc->m_pDib->IsEmpty()) pDoc->m_pDib->Display(pDC, 0, 0); } 其中CDib类的各成员函数为： class CDib : public CObject { DECLARE_SERIAL(CDib)

// Public member function public: // constructor CDib(); // create BOOL Create(DWORD dwWidth, DWORD dwHeight); BOOL Create(DWORD dwWidth, DWORD dwHeight, WORD wBitCount); BOOL Create(LPBYTE lpDIB); BOOL Create(LPBYTE lpDIB, // DIB pointer WORD wBitCount); // bits/pixel BOOL Create(HBITMAP hBitmap); // DIBSection BOOL Create(HBITMAP hBitmap, // DIBSection WORD wBitCount); // bits/pixel BOOL Create(HBITMAP hBitmap, // Bitmap handle HPALETTE hPalette); // Palette handle BOOL Create(HBITMAP hBitmap, // Bitmap handle HPALETTE hPalette, // Palette handle WORD wBitCount); // bits/pixel BOOL Create(CRect rcScreen); BOOL Create(HWND hWnd, WORD fPrintArea); BOOL Create(HWND hWnd, CRect rcClientArea); // load/save BOOL Load(UINT uIDS, LPCTSTR lpszDibType); BOOL Load(LPCTSTR lpszDibRes, LPCTSTR lpszDibType); BOOL Load(LPCTSTR lpszDibFile); BOOL Save(LPCTSTR lpszDibFile); BOOL Read(CFile *pFile); BOOL Write(CFile *pFile);

// clone CDib * Clone();

// deconstructor virtual ~CDib(); // destroy void Destroy();

// overlaying Serialize virtual void Serialize(CArchive &ar);

// display BOOL Display(CDC * pDC, int xDest, int yDest, int nWidthDest, int nHeightDest, int xSrc, int ySrc, DWORD dwRop=SRCCOPY); BOOL Display(CDC * pDC, int xDest, int yDest, int nWidthDest, int nHeightDest, int xSrc, int ySrc, int nWidthSrc, int nHeightSrc, DWORD dwRop=SRCCOPY); BOOL Display(CDC* pDC, int x, int y, DWORD dwRop=SRCCOPY); BOOL Display(CDC* pDC, CRect rcDest, CRect rcSrc,DWORD dwRop=SRCCOPY); BOOL DisplayPalette(CDC* pDC, CRect rc);

// DC for modify DIB CDC* BeginPaint(CDC *pDC); void EndPaint();

// DDB and palette BOOL BuildBitmap(); BOOL BuildPalette();

// attributes BOOL IsEmpty();

合集下载

图像处理课程设计——熵编码研究

图像处理课程设计——熵编码研究

图像处理课程设计报告设计题目：熵编码研究专业班级：学生姓名：熵编码研究摘要哈夫曼是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。

Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。

以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。

在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。

这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。

这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。

这种方法是由David.A.Huffman发展起来的。

例如，在英文中，e的出现概率很高，而z的出现概率则最低。

当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。

用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。

二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。

倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0 ≤n < 1.0)的小数n。

在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。

使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。

这个估计越准，编码结果就越接近最优的结果。

AbstractHuffman coding is a way of Huffman coding is a variable word length coding (VLC) of the kind. Huffman coding in 1952 proposed a method based on the character completely different probability to construct the shortest average length of prefix code words, sometimes called the best code, generally known as Huffman coding. ─ the optimal Huffman tree to tree, the right path with the minimum length of binary trees, often used in data compression. Information processing in the computer, "Huffman coding" is a consistency of coding method (also known as "entropy coding method") for lossless data compression. The term refers to the use of a specific character encoding table source (for example, a symbol of a file) for encoding. This code table is special because it is based on characters appear each source estimates the probability of the set up (with high probability using a shorter encoding of characters, otherwise there is a low probability of the use of longer codes, which the encoded string will be the average expected length of the lower, so as to achieve the purpose lossless data compression). This method is developed by the David.A.Huffman. For example, in English, e the probability is high, and z, the lowest probability. When using Huffman compression on the one conducted in English, e is likely to use a bit (bit) to represent, and z may be spent in 25-bit (not 26). The ordinary representation, each letter occupies one byte are (byte), or 8 bits. Compared the two, e use of a general code of 1 / 8 length, z is used 3 times. If we can achieve all the English letters in the probability of more accurate estimates can dramatically improve the lossless compression ratio.Entropy coding methods, and other difference is that, other entropy coding methods are usually divided into the input message symbol, and then encode each symbol, and arithmetic coding is the message directly to the input code as a number, a meet (0.0 ≤ n <1.0) fractional n.In a given symbol set and symbol probability case, arithmetic coding can give near optimal coding results. Arithmetic coding compression algorithm used is usually first on the probability of input symbol estimates, and then encoding. This estimate is more accurate, the closer the results of the optimal coding results.一、设计目的、任务与要求1、提高分析问题、解决问题的能力，进一步巩固数字图像处理系统中的基本原理与方法；2、熟悉掌握一门计算机语言，可以进行数字图像的应用处理的开发设计；3、理解Huffman编码以及算术编码，并学会计算平均码长。

第5章-图象编码技术2

第5章-图象编码技术2


如果平均比特数不能达到最小，就说明存在编码冗余。
6
例：自然码与变长码
sk
0
1 2 3 4 5 6 7
Ps(sk) 自然码
0.02
0.05 0.09 0.12 0.14 0.20 0.22 0.16
自然码长
3
3 3 3 3 3 3 3
变长码
00111
00110 0010 011 010 11 10 000
i 1
Jn
L’avg代表对应单符号信源n阶扩展信源的码字平均长度。
上式除以n后，可以获得：
lim
n
L'avg H (u ) n
零记忆信源的无失真编码定理
25
零记忆信源的无失真编码定理
通过对信源的无穷长扩展的编码，可以使L’avg/n任意接近H(u).
B ' {1 , 2 ,..., J n }
产生的概率
i 为其中的一个块变量（n个符号组成），信源
P(i ) P(bj1 )P(bj2 )...P(bjn )
信源的熵：
H (u' ) P(i ) log P(i ) nH (u)
i 1
Jn
可从产生n个符号的自信息考虑。
变长码长
5
5 4 3 3 2 2 3
000
001 010 011 100 101 110 111
定长码 平均码长 3 变长码 平均码长 2.81 压缩比 3/2.81 = 1.068
7
3、心理视觉冗余 人们对视觉信息不是有相同的关心程度。 具体与人们的观察方式有关。 心理视觉冗余与实在的视觉信息密切相连，消除视觉冗余导致定量 信息的损失，因此这个过程也称作量化 电视中的各行扫描 ----- 视觉冗余的具体事例 编码器 输入图 映射器 量化器 符号编码器
哈夫曼编码的解码过程

哈夫曼编码的解码过程

哈夫曼编码的解码过程哈夫曼编码是一种被广泛应用于数据压缩领域的编码算法。

它通过构建一棵特殊的二叉树来实现对源数据的编码和解码。

在编码过程中，哈夫曼编码根据源数据的频率分配较短的编码给出现频率较高的字符，相反地，给出现频率较低的字符分配较长的编码，从而有效地减小编码后的数据长度。

而解码过程则是将编码后的数据转换为原始数据的过程。

一、哈夫曼编码的基本原理哈夫曼编码的基本原理是根据字符出现的频率来构建一棵哈夫曼树，以实现对字符的编码和解码。

具体步骤如下：1. 统计字符的频率：首先，需要对待编码的源数据进行扫描，并统计每个字符的出现频率。

通常可以使用哈希表等数据结构来记录字符及其对应的频率。

2. 构建哈夫曼树：根据字符的频率，构建一棵哈夫曼树。

构建哈夫曼树的算法可以采用贪心策略，即每次选择频率最小的两个节点合并，直到所有节点合并完毕，最终形成哈夫曼树。

3. 生成编码表：按照哈夫曼树的结构，为每个字符生成对应的编码。

从哈夫曼树的根节点开始，向左子树路径走一步表示编码位为0，向右子树路径走一步表示编码位为1，直到叶子节点，即可得到该字符的编码。

编码表可以使用哈希表等数据结构来存储字符和对应的编码。

4. 进行编码：将待编码的源数据字符根据编码表进行编码，生成对应的哈夫曼编码序列。

编码后的数据长度通常会显著减小，实现数据的压缩。

二、哈夫曼编码的解码过程哈夫曼编码的解码过程是将编码后的数据序列转换回原始数据的过程。

具体步骤如下：1. 读取编码序列：从编码后的数据中逐个读取编码位，直到读取到一个有效的编码。

2. 遍历哈夫曼树：从哈夫曼树的根节点开始，根据读取到的编码位，按照0表示左子树，1表示右子树的规则，不断遍历哈夫曼树，直到达到叶子节点。

3. 生成解码字符：在遍历过程中，若到达叶子节点，则表示找到了一个字符，将该字符输出。

然后重置遍历位置，继续读取编码序列，重复上述步骤，直至解码完成。

通过以上步骤，哈夫曼编码的解码过程完成，将编码后的数据序列转换回原始数据。

c语言哈夫曼树的构造及编码

c语言哈夫曼树的构造及编码

c语言哈夫曼树的构造及编码一、哈夫曼树概述哈夫曼树是一种特殊的二叉树，它的构建基于贪心算法。

它的主要应用是在数据压缩和编码中，可以将频率高的字符用较短的编码表示，从而减小数据存储和传输时所需的空间和时间。

二、哈夫曼树的构造1. 哈夫曼树的定义哈夫曼树是一棵带权路径长度最短的二叉树。

带权路径长度是指所有叶子节点到根节点之间路径长度与其权值乘积之和。

2. 构造步骤(1) 将待编码字符按照出现频率从小到大排序。

(2) 取出两个权值最小的节点作为左右子节点，构建一棵新的二叉树。

(3) 将新构建的二叉树加入到原来排序后队列中。

(4) 重复上述步骤，直到队列只剩下一个节点，该节点即为哈夫曼树的根节点。

3. C语言代码实现以下代码实现了一个简单版哈夫曼树构造函数：```ctypedef struct TreeNode {int weight; // 权重值struct TreeNode *leftChild; // 左子节点指针struct TreeNode *rightChild; // 右子节点指针} TreeNode;// 构造哈夫曼树函数TreeNode* createHuffmanTree(int* weights, int n) {// 根据权值数组构建节点队列，每个节点都是一棵单独的二叉树TreeNode** nodes = (TreeNode**)malloc(sizeof(TreeNode*) * n);for (int i = 0; i < n; i++) {nodes[i] = (TreeNode*)malloc(sizeof(TreeNode));nodes[i]->weight = weights[i];nodes[i]->leftChild = NULL;nodes[i]->rightChild = NULL;}// 构建哈夫曼树while (n > 1) {int minIndex1 = -1, minIndex2 = -1;for (int i = 0; i < n; i++) {if (nodes[i] != NULL) {if (minIndex1 == -1 || nodes[i]->weight < nodes[minIndex1]->weight) {minIndex2 = minIndex1;minIndex1 = i;} else if (minIndex2 == -1 || nodes[i]->weight < nodes[minIndex2]->weight) {minIndex2 = i;}}}TreeNode* newNode =(TreeNode*)malloc(sizeof(TreeNode));newNode->weight = nodes[minIndex1]->weight + nodes[minIndex2]->weight;newNode->leftChild = nodes[minIndex1];newNode->rightChild = nodes[minIndex2];// 将新构建的二叉树加入到原来排序后队列中nodes[minIndex1] = newNode;nodes[minIndex2] = NULL;n--;}return nodes[minIndex1];}```三、哈夫曼编码1. 哈夫曼编码的定义哈夫曼编码是一种前缀编码方式，它将每个字符的编码表示为二进制串。