无损数据压缩的典型算法

多媒体技术基础

实验报告

院系：自动化学院 班级：11102003 姓名：胡嘉懿 学号：1110200302

·实验名称：无损压缩编码实验

·实验内容：任选一种无损编码方式，通过C++编程实现。 ·实验要求：

1) 字符串的输入是手工输入的；

2) 2) 通过程序实现编码，最终在屏幕上显示编码结果，例如，如果选用huffman编码，则要显示字符串的编码以及平均码长；

3) 3) 每人交一份实验报告电子版，以学号作为文件夹的名称，其中包括源程序。

·算法思想

按输入字符Ascii码值递增的顺序生成Hash表，并进行权重统计； 将Hash表中元素生成为Huffman树叶子节点； 对于所有无父的节点进行搜索，将次小和最小的节点作为子节点创建父节点（规定最小的总是右子节点，并总是标记为1）；

直到只剩下一个没有父节点的根节点；

对huffman树进行编码,采用递归的方法进行扫描，同时计算码长； 最后将叶子节点数据写回Hash表；

用Hash表的编码数据对原数据进行编码；

统计各叶子节点的码长来进行平均码长的计算。

Hash数组为一个长为128（ASCii）的数组，每个元素存储对应字符出现的频率和编码 元素结构： 统计权重 对应编

数据压缩算法的综述

S14050428 许申益

摘要：数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机通讯领域中的出现，使数据压缩技术的研究越来越引起人们的注意。本文综述了在数据压缩算法上一些已经取得的成果，其中包括算术编码、字典式压缩方法以及Huffman码及其改进。

关键字：数据压缩；数据存储；计算机通讯；多媒体技术

1.引言

数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。在数据的存储和表示中常常存在一定的冗余度，一些研究者提出了不同的理论模型和编码技术降低了数据的冗余度。Huffman 提出了一种基于统计模型的压缩方法，Ziv Jacob 提出了一种基于字典模型的压缩方法。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机和通讯两个领域中的出现，使数据压缩技术的研究越来越引起人们的注意。本文综述了在数据压缩算法上的一些已经取得的成果。

本文主要介绍了香农范诺编码以及哈弗曼算法的基本思想，运用其算法

第三章 多媒体数据压缩

数字化了的视频和音频信号的数据量是非常大的，一幅具有中等分辨率(640象素×480象素)，彩色(24bit/象素)数字图象的数据量约 7.37Mbit/帧，帧速率为25帧/秒，那么这种视频信号的传送速率大约为184Mbit/秒。对于音频信号，假如采样率为44.1KHz，每个采样点以16bit量化，存储10分钟二通道立体声的录音，大约需要100MB的存储空间。由此可见，高效实时地压缩视频和音频的数据量是多媒体通信中不可回避的关键技术问题。

虽然为了传输和存储的目的需要进行数据压缩，但是数据压缩是否有可能呢? 回答是肯定的。数据压缩之所以可实现，是因为原始信源数据(视频图象和音频信号)存在着很大的冗余度，比如电视图象帧内邻近象素之间空域相关性及前后帧之间的时域相关性都很大，因而可以进行数据压缩减少或消除冗余。另一方面，在多媒体应用领域中，人是主要接收者，眼睛是图象信息的接收端，耳朵是声音信息的接收端。这样就有可能利用人的视觉对于图象边缘急剧变化不敏感, 对图象的亮度信息敏感和对色彩的分辨力弱的特点，以及听觉的生理特性实现数据压缩。数据压缩技术亦称数据编码技术，从1948年Oliver 提出PCM编码理论开始

第三章 多媒体数据压缩

数字化了的视频和音频信号的数据量是非常大的，一幅具有中等分辨率(640象素×480象素)，彩色(24bit/象素)数字图象的数据量约 7.37Mbit/帧，帧速率为25帧/秒，那么这种视频信号的传送速率大约为184Mbit/秒。对于音频信号，假如采样率为44.1KHz，每个采样点以16bit量化，存储10分钟二通道立体声的录音，大约需要100MB的存储空间。由此可见，高效实时地压缩视频和音频的数据量是多媒体通信中不可回避的关键技术问题。

虽然为了传输和存储的目的需要进行数据压缩，但是数据压缩是否有可能呢? 回答是肯定的。数据压缩之所以可实现，是因为原始信源数据(视频图象和音频信号)存在着很大的冗余度，比如电视图象帧内邻近象素之间空域相关性及前后帧之间的时域相关性都很大，因而可以进行数据压缩减少或消除冗余。另一方面，在多媒体应用领域中，人是主要接收者，眼睛是图象信息的接收端，耳朵是声音信息的接收端。这样就有可能利用人的视觉对于图象边缘急剧变化不敏感, 对图象的亮度信息敏感和对色彩的分辨力弱的特点，以及听觉的生理特性实现数据压缩。数据压缩技术亦称数据编码技术，从1948年Oliver 提出PCM编码理论开始

第一章

填空题：

1、信源编码主要解决传输的 问题，信道编码主要解决传输的 问题。 2、数据压缩的信号空间包括 、 、 。 3、数据压缩按其压缩后是否产生失真可划分为 和 两大类。

第二章

填空题：

1、脉冲编码调制包括 、 、 三个步骤。

2、连续信号的多种离散表示法中，我们最常用的取样方法是 。 3、若要将取样信号准确地恢复成原信号，取样频率必须满足 定理。 4、黑白电视信号的带宽大约为5MHz，若按256级量化，则按奈奎斯特准则取样时的数据速率为 。如果电视节目按25帧/s发送，则存储一帧黑白电视节目数据需 内存容量。

5、量化器可分为 和 两大类。 6、量化器的工作特性可分为 、 、 三个区域。

6、按照处理方法是否线性来判断，我们认为量化过程本身是

《数据压缩》实验指导书（24学时）

实验一 图像输入与输出基本操作（2学时） 实验二 图像预测编码（3学时） 实验三 图像熵编码与压缩（3学时） 实验四 图像DCT变换编码与压缩（4学时） 实验五 图像小波变换编码与压缩（4学时） 实验六 JPEG编解码（4学时） 实验七 矢量量化图像压缩（4学时）

实验一 图像输入与输出基本操作

一、实验题目：

图像输入与输出操作

二、实验目的

学习在MATLAB环境下对图像文件的I/O操作，为读取各种格式的图像文

件和后续进行图像处理打下基础。

三、实验内容

利用MATLAB为用户提供的专门函数从图像格式的文件中读/写图像数据、显示图像，以及查询图像文件的信息。 四、预备知识

熟悉MATLAB开发环境。

五、实验原理

（1）图像文件的读取

利用imread函数可以完

多媒体数据压缩技术（共16题，当前为第1题）

1、MPEG标准包括MPEG视频，是运动图像数字压缩标准的有（BC ）。 A、MPEG-3 B、MPEG-4 C、MPEG-1 D、MPEG-6

2、下列不是运动图像数字压缩标准的有（C ）。 A、MPEG-4 B、MPEG-6 C、MPEG-3 D、MPEG-1

3、在已知的MPEG标准中，被兼并到HDTV的标准是（B ）。

A、MPEG-4 B、MPEG-6 C、MPEG-1 D、MPEG-3

4、条件：1）运动图像数字压缩标准2）多媒体应用标准，同时满足以上两个条件的MPEG标准是（A）。

A、MPEG-7 B、MPEG-6 C、MPEG-5 D、MPEG-4

5、在MPEG-4中，若要提高压缩比，采用的方法是（A ）。 A、帧内压缩与帧间压缩 B、帧内压缩或帧间压缩 C、空间压缩或时间压缩 D、空间压缩 6、关于压缩编码，下列说法正确的是（D ）.

A、有损压缩法是一种常用的压缩编码，也就是熵编码

B、常用的压缩编码方法分为，无损压缩法、有损压缩法两种

C、常用的压缩编码方法分为：冗余压

第4章信源编码与数据压缩 通信系统中的核心问题: ? 有效性 ? 可靠性 ? 安全性

具体到移动通信：

? 有效性、可靠性与安全性是一个全系统概念，是一个很复杂的问题；

? 实现这3类指标的环境与条件更加恶劣，因而达到目标也就更加困难；

? 提高效率的问题更加突出。[特别是由于移动通信的频率资源是有限的] 实际实现中的关联性：

? 与移动通信系统中的3个层次——物理层、网络层和网络规划层都有关系，特别是与蜂窝网的拓扑结构密切相关。 ? 涉及方面：仅从物理层来探讨，具体有： ? 有效性:涉及到信源编码与数据压缩、调制与信道编码技术、多址方式、信号分集接收、天线方向性等诸多因素。

本章仅讨论在物理层决定有效性的最主要因素之一：信源编码和数据压缩技术。 信源编码

? 作用：压缩信源输出的信息率，提高系统有效性

? 实现原理：主要是利用信源的统计特性，解除信源相关性，去掉信源冗余信息。

? 发展过程：

? 第二代(2G)数字式移动通信系统：语音压缩编码：[语音业务]。

? 第三代(2G)数字式移动通信系统：语音压缩编码 + 各类图像压缩编码和多媒体数据压缩等方面[包含语音、数据和图像在内的多媒体业务]

本课在本章仅讨论以压缩算法为核心的原理与技

6.3 典型例题

一、单项选择题

[例6-1] 数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是 ( ① )的有穷集合，R是D上( ② )的有限集合。

①A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 ②A. 操作 B. 映像 C. 存储 D．关系

解析：由数据结构的集合形式化定义可知，本题答案为：①B； ②D。 [例6-2] 数据的常用存储结构中不包括( )。

A．顺序存储结构 B．线性结构 C．索引存储结构 D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。

[例6-3] 算法指的是( ① )，它必须具备( ② )这三个特性。

①A．计算方法 B．排序方法 C．解决问题的步骤序列 D．调度方法 ②A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性

6.3 典型例题

一、单项选择题

[例6-1] 数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是 ( ① )的有穷集合，R是D上( ② )的有限集合。

①A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 ②A. 操作 B. 映像 C. 存储 D．关系

解析：由数据结构的集合形式化定义可知，本题答案为：①B； ②D。 [例6-2] 数据的常用存储结构中不包括( )。

A．顺序存储结构 B．线性结构 C．索引存储结构 D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。

[例6-3] 算法指的是( ① )，它必须具备( ② )这三个特性。

①A．计算方法 B．排序方法 C．解决问题的步骤序列 D．调度方法 ②A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性