1、1979年，这项无损伤诊断技术获得了诺贝尔奖，说明它对人类作出了划时代的奉献。与此同时，图像处理技术在多应用领域受到广泛重视并取得了重大的开拓性成就，属于这些领域的有航空航天、生物医学工程、工业检测、机器人视觉、公安司法、军事制导、文化艺术等，使图像处理成为一门引人注目、前景远大的新型学科.图像理解虽然在理论法研究上已取得不小的进展，但它本身是一个比拟难的研究领域，存在不少困难，因人类本身对自己的视觉过程还了解甚少，因此计算机视觉是一个有待人们进一步探索的新领域。1.2数字图像处理主要研究的容数字图像处理主要研究的容有以下几个面：1） 图像变换由于图像阵列很大，直接在空间域中进展处理，涉及计算
2、量很大。因此，往往采用各种图像变换的法，如傅立叶变换、沃尔什变换、离散余弦变换等间接处理技术，将空间域的处理转换为变换域处理，不仅可减少计算量，而且可获得更有效的处理如傅立叶变换可在频域中进展数字滤波处理。目前新兴研究的小波变换在时域和频域中都具有良好的局部化特性，它在图像处理中也有着广泛而有效的应用。2）图像编码压缩技术可减少描述图像的数据量即比特数，以便节省图像传输、处理时间和减少所占用的存储器容量。压缩可以在不失真的前提下获得，也可以在允的失真条件下进展。编码是压缩技术中最重要的法，它在图像处理技术中是开展最早且比拟成熟的技术。3）图像增强和复原的目的是为了提高图像的质量，如去除噪声，提
3、高图像的清晰度等。图像增强不考虑图像降质的原因，突出图像中所感兴趣的局部。如强化图像高频分量，可使图像中物体轮廓清晰，细节明显；如强化低频分量可减少图像中噪声影响。图像复原要求对图像降质的原因有一定的了解，一般讲应根据降质过程建立降质模型，再采用某种滤波法，恢复或重建原来的图像。4）图像分割是数字图像处理中的关键技术之一。图像分割是将图像中有意义的特征局部提取出来，其有意义的特征有图像中的边缘、区域等，这是进一步进展图像识别、分析和理解的根底。虽然目前已研究出不少边缘提取、区域分割的法，但还没有一种普遍适用于各种图像的有效法。因此，对图像分割的研究还在不断深入之中，是目前图像处理中研究的热点之
4、一。5）图像描述是图像识别和理解的必要前提。作为最简单的二值图像可采用其几特性描述物体的特性，一般图像的描述法采用二维形状描述，它有边界描述和区域描述两类法。对于特殊的纹理图像可采用二维纹理特征描述。随着图像处理研究的深入开展，已经开场进展三维物体描述的研究，提出了体积描述、外表描述、广义圆柱体描述等法。6）图像分类识别属于模式识别的畴，其主要容是图像经过某些预处理增强、复原、压缩后，进展图像分割和特征提取，从而进展判决分类。图像分类常采用经典的模式识别法，有统计模式分类和句法构造模式分类，近年来新开展起来的模糊模式识别和人工神经网络模式分类在图像识别中也越来越受到重视。2图像压缩2.1图像数
5、据压缩原理由于图像数据之间存在这一定的冗余，所以使得数据的压缩成为可能。信息论的创始人Shannon 提出把数据看作是信息和冗余度redundancy的组合。所谓冗余度是由于一副图像的各像素之间存在着很大的相关性，可利用一些编码的法删去它们，从而到达减少冗余压缩数据的目的。为了去掉数据中的冗余，常常要考虑信号源的统计特性，或建立信号源的统计模型。图像的冗余包括以下几种：空间冗余：像素点之间的相关性；时间冗余：活动图像两个连续帧之间的冗余；信息熵冗余：单位信息量大于其熵；构造冗余：区域上存在非常强的纹理构造；知识冗余：有固定的构造，如人的头像；视觉冗余：某些图像的失真是人眼不易觉察的。对数字图像
6、进展压缩通常利用两个根本原理:一是数字图像的相关性。在图像的同一行相邻象素之间，相邻象素之间，活动图像的相邻帧的对应象素之间往往存在很强的相关性，去除或减少这些相关性，也即去除或减少图像信息中的冗余度也就实现了对数字图像的压缩。帧象素的相关称做空域相关性。相邻帧间对应象素之间的相关性称做时域相关性。二是人的视觉心理特征。人的视觉对于边缘急剧变化不敏感（视觉掩盖效应），对颜色分辨力弱，利用这些特征可以在相应局部适当降低编码精度而使人从视觉上并不感觉到图像质量的下降，从而到达对数字图像压缩的目的。2.2霍夫曼编码Huffman编码在无损压缩的编码法中，它是一种有效的编码法。它是霍夫曼博士在1952
7、 年根据可变长最正确编码定理提出的。依据信源数据中各信号出现的频率分配不同长度的编码。其根本思想是在编码过程中，对出现频率越高的值，分配越短的编码长度，相应地对出现频率越低的值那么分配较长的编码长度，它是一种无损编码法。采用霍夫曼编码法的实质是针对统计结果对字符本身重新编码，而不是对重复字符或重复子串编码，得到的单位像素的比特数最接近图像的实际熵值。例如，在英文中，e的出现概率很高，而z的出现概率那么最低。当利用哈夫曼编码对一篇英文进展压缩时，e极有可能用一个位（bit）来表示，而z那么可能花去25个位不是26。用普通的表示法时，每个英文字母均占用一个字节byte，即8个位。二者相比，e使用了
8、一般编码的1/8的长度，z那么使用了3倍多。倘假设我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。例如：假设信源符号为【a、b、c、d、e、f、g】，其出现的概率相应的为【0.25、0.025、0.025、0.05、0.35、0.25、0.05】，一共7个字符，对其进展huffman 编码，算法如下：首先按照每个字符出现的频率大小从左到右排列：0.35、0.25、0.25、0.05、0.05、0.025、0.025；选出最小的两个值作为叶子节点构成一棵二叉树，值较大的叶子节点在左，两个叶子节点对应的频率之和作为根节点。把原排列中最小的两个节点删除，新的根节点
9、插入排列保持大小从左到右的排列顺序不变；重复执行2，直到最后得到值为1 的根节点。得到一棵huffman 树，如下列图所示： 图 2.1在得到的huffman 树上左分支标记1，右分支标记0，所有的字符根据其频率标记到对应的叶子节点上，从根节点到叶子节点路径上遇到的0、1 字符串即为对应叶子节点所在字符的编码。a、b、c、d、e、f、g七个字符的huffman 编码分别是：10、0001、0000、0011、11、01、0010，可以看到,符号只能出现在树叶上,任一个字符的路径都不会是另一字符路径的前缀路径。3 哈夫曼编码的图像压缩3.1 需求分析设计目标是实现Huffman压缩的编码器。编码
10、器的工作过程呢个如下；首先读入待压缩的源文件，为保证与源文件信息完全一致，对文件的读写操作都用二进制文件的式进展。与这只偶那个式对应的是ASCII式读写。然后建立并分析字母表，对读入存的源文件我们以字节为单元进展分析，将类型表示，其用C+建的，最多将有中可能的字符。我们对每种字符的出现频度进展统计，以频度作为建立uffman树的权值。频度表建好之后，就可以根据前述算法建立Huffman树，对出现的每种字符进展Huffman编码。此入时，再次读入源文件，逐字节编码，将得到的编码流写入到磁盘文件。可以看出编码的核心是Huffman树，它也是连接编码的纽带。考虑到Huffman树节点的设计。编码时从
11、叶节点逐步构建中间节点，到整颗树。树的节点应该应该包括的信息有：节点表示的字符，子字节的位置，字符出现的频度，父节点的位置等，这些都是构造Huffman所需要的。而解码时，我们只需要能够根据位序列从树的根节点循次遍历到叶节点，叶节点保存其表示的字符，这就足够了。3.2 设计流程图本设计目的是为了实现图像压缩，霍夫曼算法是实现此目的关键步骤。因此本设计流程图是以霍夫曼为中心展开表达的。流程图如图3-1所示。需求分析构建Huffman树设计 Huffman压缩类结果显示测试及分析图3-1流程图3.3 Huffman树的构造基类设计如下：/ NIL 表示一个空子树const short NIL =
12、-1;/ 压缩文件中Huffman树的节点对象class DiskHuffNodepublic:/ 存储的字符unsigned char ch;/ 子节点的指针索引short left;short right;DiskHuffNode （unsigned char c = 0, short lptr = NIL, short rptr = NIL）:ch（c）, left（lptr）, right（rptr）;/ 单个字符的最大位码大小const int MAXBITSIZE = 255;typedef bitset BitCode;/ 构建Huffman树的节点/ 压缩算法使用这些属性以及基
13、类DiskHuffNode建立节点/ 此类中的属性在解压缩算法中并不需要class HuffNode: public DiskHuffNodeint freq; / f字符ch的出现频度int index; / 自身节点在树中的索引int parent; / 自身节点的父节点int numberOfBits; / ch的Huffman编码的bit数目BitCode bits; / 放置Huffman码的bitset容器HuffNode （unsigned char c = 0, short lptr = NIL, short rptr = NIL,int f = 0, int indx = N
14、IL, int p = 0,int numBits = 0, int maxSizeOfBits = MAXBITSIZE）:DiskHuffNode（c, lptr, rptr）, freq（f）, index（indx）,parent（p）, numberOfBits（numBits）, bits（0）/ “运算符是构建最大优先级队列和最小优先级队列必须的friend bool operator （const HuffNode& lhs, const HuffNode& rhs）return lhs.freq return lhs.freq 3.4 图像压缩的具体实现3.4.1压缩类的实现
15、1.press（）成员函数是控制文件压缩的关键模块，Huffman树的构造是算法的核心功能所在。本设计就从这两点出发考虑Huffman压缩类得实现。press（）成员函数的定义如下：void Hpress:press（） int i; DiskHuffNode tmp; if （verbose） cout 源文件字符集频度分析中 . endl; / 执行频度分析 freqAnalysis（）;if （verbose）构造Huffman树中 . / 构建Huffman树 buildTree（）;生成Huffman码中 . endl / 为每个字符生成Huffman码，并计算压缩字符中的总字符数目
16、 generateCodes（）; / 如果选择verbose，此时树已生成，可以输出树数据 treeData（）;生成压缩文件中 . / 输出树大小 dest.write（char *）&treeSize, sizeof（short）;/ 输出树：注意我们只输出HuffNode对象的基类局部， / 解压缩Huffman所需要的仅是字符和子节点指针 for （i=0; i treeSize; i+） tmp = （DiskHuffNode）treei; dest.write（char *） &tmp, sizeof（DiskHuffNode）; / 对于仅含有单个字符的源文件， / 删除由于附
17、加叶节点所添加到总体代价的多余位 if （oneChar） totalBits-; / 输出Huffman压缩文件的比特总数目totalBits, sizeof（unsigned long）; / 完整读入源文件，在Huffman树中查找对应每个字符的Huffman码 / 写入到dest文件中 writepressedData（）;/ 关闭源文件和目的文件 source.close（）; dest.close（）; filesOpen = false;它的执行过程如下：（1）调用freeAnalysis（）读取源文件，列出文件中每个字符出现的个数。当首次读到一个字符时，将叶节点计数数目numb
18、erLeaves加1。算法利用叶节点数目来分配Huffman树。另外函数也计算文件的大小，以支持下面计算压缩比的需要。2调用bulidTree （） 为文件构造Huffman树。为了将Huffman树写入到压缩文件，如前面的需求分析中所描述那样，我们采用基于vector实现的数。这时指针是整数索引，可任意把它理解为相对地址，而不是基于链表的数构造的动 态生成的存地址。动态的存地址指向程序特定的一次运行中的存，写它到文件将毫无意义。基于vector的树使用相对地址作为指针，就回避了动态存地址的问题。3调用generateCode（） 对于每个叶节点，顺着到根节点的路径，可以判断每个字符的bit码
19、。在此过程中，确定树的代价，它是生成的位码的总位数。4完成所有数据收集Huffman树的最大节点数目为2*256-1=511。将此数值以16位整数写入到压缩文件中。5将Huffman树的基类以字符流的形式写入到压缩文件中。6将位码总数写入到压缩文件中7调用writepressData（）再次读取源文件。对每个字符，将它对应的位码写入到压缩文件中。2.构造Huffman树前面局部已经设计好了树节点的集成层次类，并详述了构造Huffman树的原理，现在我们从freeAnalysis的分析结果出发，构造Huffman树。buildTree（） / 顺序遍历Huffman树节点 int i, node
20、Index; / 捕捉从优先级队列中出来的节点 HuffNode x, y; / 最小优先级队列，用于构建Huffman树 priority_queueHuffNode, vector, greater pq;/ 处理文件仅有一个独特字符的特殊情形 if （numberLeaves = 1） / 设置叶节点数目为2， / 并在索引0或1位置添加1个叶节点 / 因为在这些位置的字符不出现在文件中 numberLeaves = 2; if （charFreq0 != 0） charFreq1 = 1; else charFreq0 = 1;/ 记录我们已经添加了填充节点 oneChar = tru
21、e; else oneChar = false;/ 树的大小为2*numberLeaves-1 treeSize = 2*numberLeaves - 1; tree.resize（treeSize）;/ 检索我们构造中的树 nodeIndex = 0;/ 开场构造各个叶节点 / value = char（i） / left/right = NIL, / frequency = charFreqi / index = nodeIndex / parent, numberOfBits, maxSizeOfBits 为默认值 / 在charLoc中记录叶节点的位置，将节点插入到最小优先级队列中 M
22、AXCHARS; if （charFreqi ! treenodeIndex = HuffNode（unsigned char）（i）, NIL, NIL, charFreqi, nodeIndex）; pq.push（treenodeIndex）; / 记录该叶节点的索引，用于 / writepressedData（）函数 charLoci = nodeIndex; / 准备构造下一个节点 nodeIndex+; / 对于 numberLeaves-1 次迭代, 移除节点对, / 生成父节点, 并将父节点插入树中 for （i=1;= numberLeaves-1; / 移除频率最低的两个节点。它们在向量树中对应节点的副本 / 位置为x.index和y.index x = pq.top（）; pq.pop（）; y = pq.top（）;/ 生成父节点部节点，它的子节点 / 在数组树中的索引位置为x.index和y.index， / 它的频度为x和y的频度和 / 这个节点的索引为nodeIndex， / 其父节点暂时设为0 treenodeIndex = HuffNode（char（0）, x.index, y.index, x.freq + y.freq, nodeIndex, 0, 0, 0）;/ 使用x.index和y.index
