基于MATLAB的图像Huffman编码研究.docx

中国矿业大学2015-2016学年第二学期

《数字视频技术》课程小设计考核

图像的Huffman编码研究

专业班级：信息13-04班

学生姓名：王振宇、龙航、王一鸣

学生学号：04131407、04131403、04131406

本人郑重声明：本人认真、独立完成了查找资料、完成作业、编写程序等考核任务，无抄袭行为。

签字：

日期：2016.05.17

1.引言

1.1图像数据压缩的目的

数字图像通常要求很大的比特数，这给图像的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。一般原始图像存在很大的冗余度。所以，对图像数据压缩显得非常重要。

1.2图像数据压缩的原理

对数字图像压缩主要运用两个基本原理：一是图像的相关性。在图像同一相邻像素之间，活动图像的相邻帧的对应像素之间往往存在很强的相关性，去除或减少这些相关性，也就除去或减少图像信息中的冗余度，继而实现对数字图像的压缩。二是人的视觉心理特征，人的视觉对于边缘急剧变化不敏感，对颜色分辨力弱，利用这些特征在相应部分降低编码精度而使人从视觉上感觉不到图像质量的下降，从而达到对数字图像压缩的目的。

1.3Huffman编码

Huffman编码是一种编码方式，是一种用于无损数据压缩的熵编码算法。它是Huffman 在1952年根据Shannon在1948年和Fano在1949年阐述的这种编码思想下提出的一种不定长编码的方法，有时也称之为最佳编码。依据信源数据中各信号出现的频率分配不同长度的编码。其基本思想是在编码过程中，对出现频率越高的值，分配越短的编码长度，相应地对出现频率越低的值则分配较长的编码长度，完全依据字符出现概率来构造异字头的平均长度最短的码字。哈夫曼编码方法的实质是针对统计结果对字符本身重新编码，而不是对重复字符或重复子串编码，得到的单位像素的比特数最接近图像的实际熵值。

2.设计任务

2.1设计任务

研究实现灰度图像的Huffman编码和解码恢复。

2.2设计目的

(1)了解Huffman编码的基本原理及其特点；

(2)理解并熟练对图像进行哈夫曼编码的算法；

(3)学习和熟悉MA TLAB图像处理工具箱；

(4)熟悉和掌握MA TLAB程序设计方法；

2.3设计要求

现灰度图像的Huffman编码和解码恢复图像；处理结果要求最终图像显示，且计算图像的信息熵，平均码字长度，编码效率，压缩比。

3.总体设计方案

3.1系统运行环境

Windows 8.1/10系统

3.2编程软件平台

MATLAB R2013a/R2014a

3.3Huffman编码算法原理

哈夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的哈夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。

(1)计算信源符号出现的概率；

(2)将信源符号按其出现的概率，由小到大顺序排列，并从左至右排列为叶节点[1]；

(3)将两个概率最小的顶层节点进行组合相加，组成一个父节点，并在到左右子节点的两条

连线上分别标记0和1；

(4)重复上一步骤，直到得到根节点，形成一颗二叉树；

(5)从根节点开始到相应于每个符号的叶节点的0/1串，就是该符号的二进制哈夫曼编码。

3.4Huffman编码算法的特点

(1)编出来的码都是异字头码，保证了码的唯一可译性。

(2)由于编码长度可变。因此译码时间较长，使得哈夫曼编码的压缩与还原相当费时。

(3)编码长度不统一，硬件实现有难度。

(4)对不同信源的编码效率不同，当信源的符号概率为2的负幂次方时，达到100％的编码

效率；若信源符号的概率相等，则编码效率最低。

(5)由于符号按概率大小排列既可以从右到左也可以从左到右，即0与1的指定是任意的，

故最后的编码结果可能不唯一，但仅仅是分配的代码不同，其平均码长是一样的，故不影响编码效率与数据压缩性能。

3.5算法流程图设计

3.5.1主流程图

开始

加载图像，并将其灰度化

将灰度图像转换成无符号

的8位整数矩阵

调用Huffman编码程序进行压缩

调用Huffman解码程序进行解码

显示原始图像、灰度图像

和经编码解码后的图像

显示平均码长、压缩比、信息

熵及编码效率

结束

3.5.2编码流程图

3.5.3解码流程图

开始

计算各符号（灰度值）出现概率按照概率从小到大排序

生成Huffman树

得到二进制哈夫曼编码码字对图像（图像矩阵）进行编码

计算编码参数

（平均码长、信息熵等）

计算二进制码字对应的十进制数，并存入矩阵中，得到码字与灰度值的对应关系表，即码表

结束

开始

结束

读取压缩矩阵，并存入行向量中

解码后的矩阵按图像矩阵尺寸重排，得到解码矩阵

解码，按位读取行向量中的编码并进行相应灰度值匹配

3.6组员任务分工

王振宇：编写主要程序，编码解码函数程序及相关子程序，修改报告及演示文稿。

龙航：编写部分主程序及部分函数程序，撰写报告。

王一鸣：编写部分程序，进行程序调试完善，制作演示文稿。

4.程序实现

4.1函数主程序

clc;clear;close all;

X=imread('peppers.JPG');

%图像灰度化

R=X(:,:,1);

G=X(:,:,2);

B=X(:,:,3);

Y=0.299*R+0.587*G+0.114*B;

subplot(1,3,1);imshow(X);title('原始图像');

data=uint8(Y);

[zipped,info]=huffencode(data);%调用Huffman编码程序进行压缩

unzipped=huffdecode(zipped,info);%调用Huffman编码程序进行解码

%显示原始图像，灰度化图像和经编码解码后的图像

subplot(1,3,2);imshow(data);title('灰度化图像');

subplot(1,3,3);imshow(unzipped);title('Huffman编码并解码后图像');

disp('平均码长');L=info.avalen

disp('压缩比');CR=info.ratio

disp('信息熵');H=info.h

disp('编码效率');CE=info.ce

4.2编码程序

%huffencode函数对输入矩阵vector进行Huffman编码，返回编码后的数据及相关信息function [zipped,info]=huffencode(vector)

if ~isa(vector,'uint8')%确定输入矩阵是uint8格式

error('input argument must be a uint8 vector');

end

[m,n]=size(vector);%求输入矩阵的行列数

vector=vector(:)';%将矩阵按列转换成一列后转至，成为一个行向量(其中存放灰度值) f=frequency(vector);%计算各符号出现的概率

symbols=find(f~=0);%返回概率矩阵中非零元素的位置向量，作为符号向量

f=f(symbols);%非零概率位置上的概率值组成非零概率行向量

[f,sortindex]=sort(f);%将符号按照出现的概率从小到大排序，并保留非零概率向量位置索引

fs=f;

symbols=symbols(sortindex);%读出原位置向量中的值（即概率向量中的位置），得到按概率排序后的符号向量

len=length(symbols);%读取位置向量的长度

symbols_index=num2cell(1:len);%生成从1开始以1递增，1行len列的细胞型矩阵

codeword_tmp=cell(len,1);%创建一个len行1列的细胞型变量用于存放码字

while length(f)>1 %生成Huffman树，得到二进制码字编码表

index1=symbols_index{1};

index2=symbols_index{2};

codeword_tmp(index1)=addnode(codeword_tmp(index1),uint8(0));%添加节点且该分支按0标记

codeword_tmp(index2)=addnode(codeword_tmp(index2),uint8(1));%添加节点且该分支按1标记

f=[sum(f(1:2)) f(3:end)];%求出两个最小概率之和，列出其他概率，组成一个新的行向量

symbols_index=[{[index1,index2]} symbols_index(3:end)];%合并已编码的符号索引

[f,sortindex]=sort(f);%将新的概率向量按照概率从小到大排序

symbols_index=symbols_index(sortindex);%得到新的索引表

end

codeword=cell(256,1);

codeword(symbols)=codeword_tmp;%各符号二进制码字按原符号位存入细胞型矩阵

len=0;

for i=1:length(symbols)%得到各符号码长矩阵

wordlen(i)=length(codeword_tmp{i});

end

avawordlen=fs*wordlen';%计算平均码长

Hlog=log2(fs)';

H=-(fs*Hlog);%计算信息熵

for index=1:length(vector)%得到整个图像各点灰度值转化为二进制码字后的总比特数 len=len+length(codeword{double(vector(index))+1});

end

string=repmat(uint8(0),1,len);%创建元素数与总比特数一致的行向量

pointer=1;%定义指针变量

for index=1:length(vector) %对输入图像进行编码

code=codeword{double(vector(index))+1};%对应符号的二进制码字给code len=length(code);%读取码字长度

string(pointer+(0:len-1))=code;%将二进制码字存入行向量中

pointer=pointer+len;%指针移移位

end

% 将二进制编码按照每8位生成一个新字符。

len=length(string);

zp=8-mod(len,8);

if zp>0

string=[string uint8(zeros(1,zp))];%不足8位的在后补零

end

codeword=codeword(symbols);%码字按符号概率放入列向量中

codelen=zeros(size(codeword));%创建与列向量元素数相同的列向量

weights=2.^(0:23);

哈夫曼编码资料

哈夫曼编码译码系统 一、需求分析 1、程序的基本功能： ①构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n个字符以及n个对应的权 值，建立哈夫曼树；利用已将建好的哈弗曼树求每个叶结点的哈夫曼编码，并保存。 ②编码：利用已构造的哈弗曼编码对“明文”文件中的正文进行编码，然后将结果存 入“密文”文件中。 ③译码：将“密文”文件中的0、1代码序列进行译码。 ④打印“密文”文件：将文件以紧凑格式显示在终端上，同时，将此字符形式的编码 保存。 ⑤打印哈夫曼树:将已在内存中的哈夫曼以凹入表形式显示在终端上。 2、输入输出要求： ①从键盘接收字符集大小n、以及n个字符和n个权值； ②构造哈夫曼树：将HFMTree数组中的各个位置的各个域都添上相关的值，并将结构 体数组存入文件HTree.txt中。 ③打印哈夫曼树：从HFMTree数组读取相关的结点信息，以凹入表方式将各个结点画 出来； ④构造哈夫曼编码：先从文件HTree.txt中读入相关的字符信息进行哈夫曼编码，将字 符与其对应的编码存入文件HNode.txt中； ⑤编码：利用已构造的哈夫曼树对文件进行编码，打印结果，并将结果存入新建文件 中； ⑥译码：将密文文件中的内容利用HNode.txt中建立的编码规则进行翻译，打印结果， 并将结果存入新建文件中。 3、测试数据： 输入叶子结点个数为4，权值集合为{1,3,5,7}，字符集合为{A,B,C,D}，且字符集与权值集合一一对应。 二、概要设计 1、抽象数据类型的定义： ①采用静态链表作为哈夫曼树的存储结构； ②求哈夫曼编码时使用一维数组HCode作为哈夫曼编码信息的存储。 2、主模块的流程及各子模块的主要功能： ①int main() { 主菜单； swich语句结构选择； return 0; } ②in_park() { 输入车牌号； 若停车场已满，停入便道中，否则停入停车场； } ③output()

基于matlab的图像识别与匹配

基于matlab的图像识别与匹配 摘要 图像的识别与匹配是立体视觉的一个重要分支，该项技术被广泛应用在航空测绘，星球探测机器人导航以及三维重建等领域。 本文意在熟练运用图像的识别与匹配的方法，为此本文使用一个包装袋并对上面的数字进行识别与匹配。首先在包装袋上提取出来要用的数字，然后提取出该数字与包装袋上的特征点，用SIFT方法对两幅图进行识别与匹配，最终得到对应匹配数字的匹配点。仿真结果表明，该方法能够把给定数字与包装袋上的相同数字进行识别与匹配，得到了良好的实验结果，基本完成了识别与匹配的任务。

1 研究内容 图像识别中的模式识别是一种从大量信息和数据出发，利用计算机和数学推理的方法对形状、模式、曲线、数字、字符格式和图形自动完成识别、评价的过程。 图形辨别是图像识别技术的一个重要分支，图形辨别指通过对图形的图像采用特定算法，从而辨别图形或者数字，通过特征点检测，精确定位特征点，通过将模板与图形或数字匹配，根据匹配结果进行辨别。 2 研究意义 数字图像处理在各个领域都有着非常重要的应用，随着数字时代的到来，视频领域的数字化也必将到来，视频图像处理技术也将会发生日新月异的变化。在多媒体技术的各个领域中，视频处理技术占有非常重要的地位，被广泛的使用于农业，智能交通，汽车电子，网络多媒体通信，实时监控系统等诸多方面。因此，现今对技术领域的研究已日趋活跃和繁荣。而图像识别也同样有着更重要的作用。 3 设计原理 3.1 算法选择 Harris 角点检测器对于图像尺度变化非常敏感，这在很大程度上限制了它的应用范围。对于仅存在平移、旋转以及很小尺度变换的图像，基于Harris 特征点的方法都可以得到准确的配准结果，但是对于存在大尺度变换的图像，这一类方法将无法保证正确的配准和拼接。后来，研究人员相继提出了具有尺度不变性的特征点检测方法，具有仿射不变性的特征点检测方法，局部不变性的特征检测方法等大量的基于不变量技术的特征检测方法。 David.Lowe 于2004年在上述算法的基础上，总结了现有的基于不变量技术的特征检测方法，正式提出了一种基于尺度空间的，对图像平移、旋转、缩放、甚至仿射变换保持不变性的图像局部特征，以及基于该特征的描述符。并将这种方法命名为尺度不变特征变换（Scale Invariant Feature Transform），以下简称SIFT 算法。SIFT 算法首先在尺度空间进行特征检测，并确定特征点的位置和特征点所处的尺度，然后使用特征点邻域梯度的主方向作为该特征点的方向特征，以实现算子对尺度和方向的无关性。利用SIFT 算法从图像中提取出的特征可用于同一个物体或场景的可靠匹配，对图像尺度和旋转具有不变性，对光照变化、

Huffman编码报告

《数据结构》课程设计上机实习报告 课设题目Huffman编码和解码 班级 学生姓名 学号 指导教师 时间2015.12-2015.1

一、设计目的 1.进一步熟悉C语言开发环境，熟悉用C语言完成一个应用程序的设计过程，掌握有关编辑、调试和整合程序的方法和技巧。 2.通过此设计，了解《数据结构》课程中霍夫曼编码的的有关内容，明确其操作，熟悉其设计，同时学习到有关位向量的内容，对文件掌握加深 二、设计内容 Huffman编码与解码 (必做)（Huffman编码、二叉树） [问题描述] 对一篇英文文章（大于2000个英文字符），统计各字符出现的次 数，实现Huffman编码，以及对编码结果的解码。 [基本要求] （1）输出每个字符出现的次数和编码，其中求最小权值要求用堆实 现。 （2）在Huffman编码后，要将编码表和英文文章编码结果保存到文 件中，编码结果必须是二进制形式，即0 1的信息用比特位表示，不 能用字符’0’和’1’表示。 （3）提供读编码文件生成原文件的功能。 三、数据结构说明 在该程序中我仅仅使用了两个结构体来完成编码，用位域来实现bite流存储：const int MAXSIZE=300;//定义一次分配的Huffman储存单词最大量为500 const int OVERFLOW = 0; const int ERROR = 0; const int LineCountNum=500; typedef struct WordCount {

char Word;//存放字符 int freq; int parent , lchild , rchild;//存放亲子节点位置 int place;//用来保存第一次堆排序后，建立霍夫曼表前的相对位置 char *HuffmanCode;//存放霍夫曼编码 }WordCount , *WC;//存放单词结点的结构体 typedef struct HuffmanTree { WC w; int Number;//存储有多少数据存入 }HuffmanTree , *HTree; typedef struct { unsigned int a:1; }bite;//设置位段，存储一个bite //**************操作函数声明*********** void InitHuffmanTree(HTree &H);//初始化霍夫曼树 void HeapSort(WC &W , int Number , int choice);//堆排序核心函数 void HeapAdjust(WC &W , int down , int up , int choice);//堆排序调整函数,实现两种排序 void HuffmanCoding(HTree &H , WC &HT); //求霍夫曼树和霍夫曼编码表 void ShowHuffmanTree(HTree H);//输出霍夫曼树 void Select(WC &W , int i , int &s1 , int &s2);//选择1-i-1之间最小的两个数，且parent为0，用s1,s2返回 void GetTheDeCode(HTree H);//将编码结果写入函数 void PutTheDeCode(FILE *fp1 , FILE *fp2);//将编码结果解码得到文章 void CountTheWord(HTree &H , FILE *fp);//记录单词权值 void ShowTheEassy(FILE *wp);//展示文章 四、详细设计 1.首先我给出了编码和解码的菜单供其选择 2.在编码功能中，我先通过CountTheWord（）函数进行单词权值记录，然后 进入编码功能，值得一提的是，编码时我给堆排序设计了两种排序形式——对权值的排序和对位置的排序，以达到选择两个最小的权值结点的最优时间复杂度的目的，此功能通过switch实现，但要给编码结构体中放置一个place 空间，这也从侧面反映了时间和空间矛盾的地方(值得一提的是，有些编码并不可见且有特殊含义，如换行符，所以将字符放入文件中时，并不对其进行处理，读出是进行顺序读出) 3.编码结束后将编码结果，对应字符分别存放在文件中，然后对整篇文章进行 编码

数字图像处理考试

1. 对下列信源符号进行Huffman 编码，并计算其冗余度和压缩率。 符号 a1 a2 a3 a4 a5 a6 概率 0.1 0.4 0.06 0.1 0.04 0.3 原始信源 信源简化 符号 概率 1 2 3 4 a2 0.4 0.4 0.4 0.4 0.6 a6 0.3 0.3 0.3 0.3 0.4 a1 0.1 0.1 0.2 0.3 a4 0.1 0.1 0.1 a3 0.06 0.1 a5 0.04 从最小的信源开始一直到原始的信源 编码的平均长度： 压缩率：13 1.3642.2 R avg n C L ==≈ 冗余度：11110.26691.364D R R C =- =-≈ (0.4)(1)(0.3)(2)(0.1)3(0.1)(4)(0.06)(5)(0.04)(5) 2.2/avg L bit =+++++=（）符号

1. 简述灰度分辨率、空间分辨率与图像质量的关系。: 空间分辨率是看原图像转化为数字图像的像素点数，越多图像质量越高；灰度分辨率，即每一个像素点的灰度级数，灰度级越大，图像越清晰. 2. 简述采样和量化的一般原则: 空间坐标的离散化叫做空间采样，而灰度的离散化叫做灰度量化。图像的空间分辨率主要由采样所决定，而图像的幅度分辨率主要由量化所决定。 3. 图像锐化与图像平滑有何区别与联系？: 图象锐化是用于增强边缘，导致高频分量增强，会使图象清晰；图象平滑用于去噪，对图象高频分量即图象边缘会有影响。都属于图象增强，改善图象效果。 4. 伪彩色增强与假彩色增强有何异同点？: 伪彩色增强是对一幅灰度图象经过三种变换得到三幅图象，进行彩色合成得到一幅彩色图像；假彩色增强则是对一幅彩色图像进行处理得到与原图象不同的彩色图像；主要差异在于处理对象不同。 1. 对于椒盐噪声，为什么中值滤波效果比均值滤波效果好？：均值滤波器是一种最常用的线性低通平滑滤波器，可抑制图像中的加性噪声，但同时也使图像变得模糊；中值滤波器是一种最常用的非线性平滑滤波器，可消除图像中孤立的噪声点，又可产生较少的模糊。一般情况下中值滤波的效果要比邻域平均处理的低通滤波效果好，主要特点是滤波后图像中的轮廓比较清晰。因此，滤除图像中的椒盐噪声采用中值滤波。 2.什么是区域？什么是图像分割？:图像分割就是把图像分成若干个特定 的、具有独特性质的区域并提出感兴趣目标的技术和过程。它是由图像处理到图像分析的关键步骤。 3.写出颜色RGB模型转换到HIS模型的变换公式；并说明HSI模型各分 量的含义及取值围对应的颜色信息。书上 4.灰度图像：当点足够小，观察距离足够远时，人眼就不容易分开各个小 点，从而得到比较连续，平滑的灰度图像。 5.GIF格式：GIF格式是一种公用的图像文件格式，它是8位文件格式， 所以最多只能存储256色图像，不支持24位的真彩色图像。GIF文件中的图像数据均经过压缩，采用的压缩算法是改进的LZW算法，所提供的压缩率通常在1：1到1：3之间，当图像中有随机噪声时效果不好

霍夫曼编码表

附录二 表1. 传真用的修正霍夫曼编码表 构造码 64 11011 0000001111 960 011010100 0000001110011 128 10010 000011001000 1024 011010101 0000001110100 192 010111 000011001001 1088 011010110 0000001110101 256 0110111 000001011011 1152 011010111 0000001110110 320 00110110 000000110011 1216 011011000 0000001110111 384 00110111 000000110100 1280 011011001 0000001010010 448 01100100 000000110101 1344 011011010 0000001010011 512 01100101 0000001101100 1448 011011011 0000001010100 576 01101000 0000001101101 1472 010011000 0000001010101 640 01100111 0000001001010 1536 010011001 0000001011010 704 011001100 0000001001011 1600 010011010 0000001011011 768 011001101 0000001001100 1664 011000 0000001100100 832 011010010 0000001001101 1728 010011011 0000001100101 896 011010011 0000001110010 EOL 000000000001 000000000001 结尾码 游程长度 白游程编码 黑游程编码 游程长度白游程编码 黑游程编码 0 00110101 0000110111 32 000111011 000001101010 1 000111 010 33 00010010 000001101011 2 0111 11 34 00010011 000011010010 3 1000 10 35 00010100 000011010011 4 1011 011 36 00010101 000011010100 5 1100 0011 37 00010110 000011010101 6 1110 0010 38 00010111 000011010110 7 1111 00011 39 00101000 000011010111 8 10011 000101 40 00101001 000001101100 9 10100 000100 41 00101010 000001101101 10 00111 0000100 42 00101011 000011011010 11 01000 0000101 43 00101100 000011011011 12 001000 0000111 44 00101101 000001010100 13 000011 00000100 45 00000100 000001010101 14 110100 00000111 46 00000101 000001010110 15 110101 000011000 47 00001010 000001010111 16 101010 0000010111 48 00001011 000001100100 17 101011 0000011000 49 01010010 000001100101 18 0100111 0000001000 50 01010011 000001010010 19 0001100 00001100111 51 01010100 000001010011 20 0001000 00001101000 52 01010101 000000100100 21 0010111 00001101100 53 00100100 000000110111 22 0000011 00000110111 54 00100101 000000111000 23 0000100 00000101000 55 01011000 000000100111 24 0101000 00000010111 56 01011001 000000101000 25 0101011 00000011000 57 01011010 000001011000 26 0010011 000011001010 58 01011011 000001011001 27 0100100 000011001011 59 01001010 000000101011 28 0011000 000011001100 60 01001011 000000101100 29 00000010 000011001101 61 00110010 000001011010 30 00000011 000001101000 62 00110011 000001100110 31 00011010 000001101001 63 00110100 000001100111 205

基于MATLAB的图像处理字母识别

数字图像处理 报告名称：字母识别 学院：信息工程与自动化学院专业：物联网工程 学号：201310410149 学生姓名：廖成武 指导教师：王剑 日期：2015年12月28日 教务处制

目录 字母识别 1.---------------------测试图像预处理及连通区域提取 2.---------------------样本库的建立采集feature 3.---------------------选择算法输入测试图像进行测试 4.---------------------总结

字母识别 1.imgPreProcess（联通区域提取）目录下 conn.m：连通区域提取分割（在原图的基础上进行了膨胀、腐蚀、膨胀的操作使截取的图像更加接近字母） %%提取数字的边界，生成新的图 clear; clc; f=imread('5.jpg'); f=imadjust(f,[0 1],[1 0]); SE=strel('square',5); %%膨胀、腐蚀、膨胀 A2=imdilate(f,SE); SE=strel('disk',3) f=imerode(A2,SE) SE=strel('square',3); f=imdilate(f,SE); gray_level=graythresh(f); f=im2bw(f,gray_level); [l,n]=bwlabel(f,8) %%8连接的连接分量标注 imshow(f) hold on for k=1:n %%分割字符子句 [r,c]=find(l==k); rbar=mean(r); cbar=mean(c); plot(cbar,rbar,'Marker','o','MarkerEdgeColor','g','MarkerFaceColor',' y','MarkerSize',10); % plot(cbar,rbar,'Marker','*','MarkerEdgecolor','w'); row=max(r)-min(r) col=max(c)-min(c) for i=1:row for j=1:col seg(i,j)=1; end

霍夫曼编码

霍夫曼编码 霍夫曼编码(Huffman Coding)是一种编码方法，霍夫曼编码是可变字长编码(VLC)的一种。1952年，David A. Huffman在麻省理工攻读博士时所提出一种编码方法，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。 该方法完全依据字符出现概率来构造异字头的平均长度最短的 码字，有时称之为最佳编码，一般就叫作Huffman编码。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。1951年，霍夫曼和他 在MIT信息论的同学需要选择是完成学期报告还是期末考试。 导师Robert M. Fano给他们的学期报告的题目是，查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者克劳德·香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。 霍夫曼（Huffman）编码是一种统计编码。属于无损（lossless）压缩编码。

以霍夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 ←根据给定数据集中各元素所出现的频率来压缩数据的 一种统计压缩编码方法。这些元素(如字母)出现的次数越 多，其编码的位数就越少。 ←广泛用在JPEG, MPEG, H.2X等各种信息编码标准中。霍夫曼编码的步骤 霍夫曼编码的具体步骤如下： １）将信源符号的概率按减小的顺序排队。 ２）把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在上部，直到最后变成概率１。 3）将每对组合的上边一个指定为1，下边一个指定为0（或相反）。４）画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。 信源熵的定义： 概率空间中每个事件所含有的自信息量的数学期望称信源熵或简称熵(entropy)，记为： 例：现有一个由5个不同符号组成的30个符号的字 符串：BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的平均码长

基于matlab的人脸识别算法(PCA)

3.基于matlab的人脸识别算法 3.1 问题描述 对于一幅图像可以看作一个由像素值组成的矩阵，也可以扩展开，看成一个矢量，如一幅 N*N 象素的图像可以视为长度为N2 的矢量，这样就认为这幅图像是位于N2 维空间中的一个点，这种图像的矢量表示就是原始的图像空间，但是这个空间仅是可以表示或者检测图像的许多个空间中的一个。不管子空间的具体形式如何，这种方法用于图像识别的基本思想都是一样的，首先选择一个合适的子空间，图像将被投影到这个子空间上，然后利用对图像的这种投影间的某种度量来确定图像间的相似度，最常见的就是各种距离度量。因此，本次试题采用PCA算法并利用GUI实现。 对同一个体进行多项观察时，必定涉及多个随机变量X1，X2，…，Xp，它们都是的相关性, 一时难以综合。这时就需要借助主成分分析来概括诸多信息的主要方面。我们希望有一个或几个较好的综合指标来概括信息，而且希望综合指标互相独立地各代表某一方面的性质。 任何一个度量指标的好坏除了可靠、真实之外，还必须能充分反映个体间的变异。如果有一项指标，不同个体的取值都大同小异，那么该指标不能用来区分不同的个体。由这一点来看，一项指标在个体间的变异越大越好。因此我们把“变异大”作为“好”的标准来寻求综合指标。3.1.1 主成分的一般定义 设有随机变量X1，X2，…，Xp，其样本均数记为，，…，，样本标准差记为S1，S2，…，Sp。首先作标准化变换，我们有如下的定义： (1) 若C1=a11x1+a12x2+ … +a1pxp，…，且使 Var(C1)最大，则称C1为第一主成分； (2) 若C2=a21x1+a22x2+…+a2pxp，…，(a21，a22，…，a2p)垂直于(a11，a12，…，a1p)，且使Var(C2)最大，则称C2为第二主成分； (3) 类似地，可有第三、四、五…主成分，至多有p个。 3.1.2 主成分的性质 主成分C1，C2，…，Cp具有如下几个性质： （1) 主成分间互不相关，即对任意i和j，Ci 和Cj的相关系数 Corr(Ci，Cj)=0 i j (2) 组合系数(ai1，ai2，…，aip)构成的向量为单位向量， (3) 各主成分的方差是依次递减的，即 Var(C1)≥Var(C2)≥…≥Var(Cp)

huffman编码的matlab实现

Huffman编码的matlab实现 一、信源编码介绍 为了减少信源输出符号序列中的剩余度、提高符号的平均信息量，对所施行的变换。具体说，就是针对信源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列。 既然信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。当然，这些都是广义的信源编码。 一般来说，减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个：①使序列中的各个符号尽可能地互相独立；②使序列中各个符号的出现概率尽可能地相等。前者称为解除相关性，后者称为概率均匀化。 信源编码的一般问题可以表述如下： 信源编码 若某信源的输出为长度等于M的符号序列集合式中符号A为信源符号表，它包含着K个不同的符号，A={ɑk|k=1,…,K}，这个信源至多可以输出K M个不同的符号序列。记‖U‖=KM。所谓对这个信源的输出 信源编码 进行编码，就是用一个新的符号表B的符号序列集合V来表示信源输出的符号序列集合U。若V的各个序列的长度等于 N，即式中新的符号表B共含L个符号，B={b l|l=1,…,L}。它总共可以编出L N个不同的码字。类似地,记‖V‖=LN。为了使信源的每个输出符号序列都能分配到一个独特的码字与之对应，至少应满足关系‖V‖=L N≥‖U‖=KM或者N/M≥log K/log L 下面的几个编码定理，提供了解决这个矛盾的方法。它们既能改善信息载荷效率，又能保证码字唯一可译。 离散无记忆信源的定长编码定理 对于任意给定的ε>0，只要满足条件N/M≥(H(U)+ε)/log L 那么，当M足够大时，上述编码几乎没有失真;反之,若这个条件不满足，就不可能实现无失真的编码。式中H(U)是信源输出序列的符号熵。 信源编码 通常，信源的符号熵H(U)

基于MATLAB的人脸识别

基于ＭATＬAB的人脸识别

————————————————————————————————作者: ————————————————————————————————日期:

图像识别 题目:基于MＡTＬAB的人脸识别 院系:计算机科学与应用系 班级: 姓名： 学号： 日期：

设计题目基于MAＴLAＢ的人脸识别设 计技术参数 测试数据库图片10张训练数据库图片20张图片大小１02４×7６8 特征向量提取阈值 1 设计要求综合运用本课程的理论知识,并利用MAＴＬAB作为工具实现对人脸图片的预处理,运用ＰCA算法进行人脸特征提取，进而进行人脸匹配识别。 工作量 两周的课程设计时间，完成一份课程设计报告书，包括设计的任务书、基本原理、设计思路与设计的基本思想、设计体会以及相关的程序代码； 熟练掌握Maｔlab的使用。 工作计划第1-2天按要求查阅相关资料文献,确定人脸识别的总体设计思路； 第３-4天分析设计题目，理解人脸识别的原理同时寻求相关的实现算法；第５-８天编写程序代码，创建图片数据库,运用ＰCＡ算法进行特征提取并编写特征脸，上机进行调试； 第9-12天编写人脸识别程序,实现总体功能； 第13-1４天整理思路,书写课程设计报告书。 参考资料1 黄文梅，熊佳林,杨勇编著．信号分析与处理——MATAＬB语言及应用.国防科技大学出版社，2000 2 钱同惠编著.数字信号处理.北京:机械工业出版社，２004 3 姚天任,江太辉编著.数字信号处理．第2版.武汉:武汉理工大学出版社,200０ 4 谢平，林洪彬，王娜.信号处理原理及应用．机械工业出版社，２00４ 5刘敏，魏玲.Mａｔｌａb.通信仿真与应用.国防工业出版社，20０5 6 楼顺天.基于Ｍatlab7．x 的系统分析与设计.西安电子科技大学,200２ 7孙洪.数字信号处理.电子工业出版社，２001 目录 引言?错误!未定义书签。 1 人脸识别技术?错误!未定义书签。 1.1人脸识别的研究内容?错误!未定义书签。 1.1.1人脸检测(Faｃe Dｅｔection）........... 错误!未定义书签。

数字图像处理代码大全

1.图像反转 MATLAB程序实现如下： I=imread('xian.bmp'); J=double(I); J=-J+(256-1); %图像反转线性变换 H=uint8(J); subplot(1,2,1),imshow(I); subplot(1,2,2),imshow(H); 2.灰度线性变换 MATLAB程序实现如下： I=imread('xian.bmp'); subplot(2,2,1),imshow(I); title('原始图像'); axis([50,250,50,200]); axis on; %显示坐标系 I1=rgb2gray(I); subplot(2,2,2),imshow(I1); title('灰度图像'); axis([50,250,50,200]); axis on; %显示坐标系 J=imadjust(I1,[0.1 0.5],[]); %局部拉伸，把[0.1 0.5]的灰度拉伸为[0 1]

subplot(2,2,3),imshow(J); title('线性变换图像[0.1 0.5]'); axis([50,250,50,200]); grid on; %显示网格线 axis on; %显示坐标系 K=imadjust(I1,[0.3 0.7],[]); %局部拉伸，把[0.3 0.7]的灰度拉伸为[0 1] subplot(2,2,4),imshow(K); title('线性变换图像[0.3 0.7]'); axis([50,250,50,200]); grid on; %显示网格线 axis on; %显示坐标系 3.非线性变换 MATLAB程序实现如下： I=imread('xian.bmp'); I1=rgb2gray(I); subplot(1,2,1),imshow(I1); title('灰度图像'); axis([50,250,50,200]); grid on; %显示网格线 axis on; %显示坐标系 J=double(I1);

哈夫曼编码算法实现完整版

实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include #include #include #include typedef struct{ char data; int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char * * HuffmanCode; void Select(HuffmanTree &HT,int n,int m) {HuffmanTree p=HT; int tmp; for(int j=n+1;j<=m;j++) {int tag1,tag2,s1,s2; tag1=tag2=32767; for(int x=1;x<=j-1;x++) { if(p[x].parent==0&&p[x].weights2) //将选出的两个节点中的序号较小的始终赋给s1 { tmp=s1; s1=s2; s2=tmp;} p[s1].parent=j;

基于matlab数字图像处理与识别系统含程序

目录 第一章绪论 (2) 1.1 研究背景 (2) 1.2 人脸图像识别的应用前景 (3) 1.3 本文研究的问题 (4) 1.4 识别系统构成 (4) 1.5 论文的内容及组织 (5) 第二章图像处理的Matlab实现 (6) 2.1 Matlab简介 (6) 2.2 数字图像处理及过程 (6) 2.2.1图像处理的基本操作 (6) 2.2.2图像类型的转换 (7) 2.2.3图像增强 (7) 2.2.4边缘检测 (8) 2.3图像处理功能的Matlab实现实例 (8) 2.4 本章小结 (11) 第三章人脸图像识别计算机系统 (11) 3.1 引言 (11) 3.2系统基本机构 (12) 3.3 人脸检测定位算法 (13) 3.4 人脸图像的预处理 (18) 3.4.1 仿真系统中实现的人脸图像预处理方法 (19) 第四章基于直方图的人脸识别实现 (21) 4.1识别理论 (21) 4.2 人脸识别的matlab实现 (21) 4.3 本章小结 (22) 第五章总结 (22) 致谢 (23) 参考文献 (24) 附录 (25)

第一章绪论 本章提出了本文的研究背景及应用前景。首先阐述了人脸图像识别意义；然后介绍了人脸图像识别研究中存在的问题；接着介绍了自动人脸识别系统的一般框架构成；最后简要地介绍了本文的主要工作和章节结构。 1.1 研究背景 自70年代以来.随着人工智能技术的兴起.以及人类视觉研究的进展.人们逐渐对人脸图像的机器识别投入很大的热情，并形成了一个人脸图像识别研究领域，.这一领域除了它的重大理论价值外，也极具实用价值。 在进行人工智能的研究中，人们一直想做的事情就是让机器具有像人类一样的思考能力，以及识别事物、处理事物的能力，因此从解剖学、心理学、行为感知学等各个角度来探求人类的思维机制、以及感知事物、处理事物的机制，并努力将这些机制用于实践，如各种智能机器人的研制。人脸图像的机器识别研究就是在这种背景下兴起的，因为人们发现许多对于人类而言可以轻易做到的事情，而让机器来实现却很难，如人脸图像的识别，语音识别，自然语言理解等。如果能够开发出具有像人类一样的机器识别机制，就能够逐步地了解人类是如何存储信息，并进行处理的，从而最终了解人类的思维机制。 同时，进行人脸图像识别研究也具有很大的使用价依。如同人的指纹一样，人脸也具有唯一性，也可用来鉴别一个人的身份。现在己有实用的计算机自动指纹识别系统面世，并在安检等部门得到应用，但还没有通用成熟的人脸自动识别系统出现。人脸图像的自动识别系统较之指纹识别系统、DNA鉴定等更具方便性，因为它取样方便，可以不接触目标就进行识别，从而开发研究的实际意义更大。并且与指纹图像不同的是，人脸图像受很多因素的干扰:人脸表情的多样性;以及外在的成像过程中的光照，图像尺寸，旋转，姿势变化等。使得同一个人，

基于MATLAB数字图像处理杂草识别

基于MATLAB数字图像处理杂草识别

基于数字图像处理的杂草识别 班级：信息5班 组员：李辉李少杰李港深胡欣阳 学号：04141394 04141395 04141393 0414139 指导教师：蔡利梅 组员分工： 李辉：部分程序，查找资料 李少杰：实验报告，PPT，演讲 李港深：部分程序，实验报告 胡欣阳：部分程序，实验报告

摘要 杂草同农田作物争夺阳光和养分，严重影响了农作物的生长。为了达到除草的目的，人们开始喷洒大量的除草剂来进行除草。可是却忽略了除草剂的不当使用给人、畜以及环境造成的危害。本文从实际应用出发，设计了一个基于数字图像处理的杂草图像特征提取及识别设计方案。运行在参考了前人研究成果的基础上，不断将算法改进，找出适合于MATLAB杂草识别的可行性方法。本文对杂草图像的处理和识别方法进行研究。采集来的图像经常会有模糊现象的发生，对模糊图像的恢复处理做了大量的研究试验，得出维纳滤波具有较好的恢复效果；绿色植物和土壤背景的分割试验中，提出了一种基于彩色图像的二值化方法，可以不经过彩色图像灰度化就能够直接把绿色植物与土壤背景分割开，和以往的分割方法相比处理速度快，分割效果好，更加满足实时性；杂草和作物的分割主要研究了行间杂草和作物的分割，参考国内外资料，并进行研究试验，表明运用位置特征识别法有很好的分割效果，寻找作物中心行采用了简单快速的像素位置直方图法，采用了区域生长，和其他方法相比减少了重复操作，节省了时间，满足实时处理的要求；分割后的图像为只含有杂草的二值图像，通常会有一些残余的叶片和颗粒的噪声，通过形态学滤波或中值滤波去除噪声。 1、研究目的及意义 杂草是生态系统中的一员,农田杂草是农业生态系统中的

数字图像处理练习题

1、考虑如下所示图像子集： （1）令V={0,1}，计算p和q之间的4，8，m通路的最短长度；（2）令V={1，2}，仍计算上述3个长度。 2、对于离散的数字图像，则变换函数T(rk)的离散形式可表示为: ∑ ∑ = = - = - = = k j j k j j r k k n MN L r p L r T s 1 ) ( ) 1 ( ) ( 上式表明，均衡后各像素的灰度值sk可直接由原图像的直方图算出。 例假定有一幅总像素为n=64×64的图像，灰度级数为8，各灰度级分布列于表中。对其均衡化计算过程如下。若在原图像一行上连续8个像素的灰度值分别为：0、1、2、3、4、5、6、7，则均衡后，他们的灰度值为多少 3、

4、在位图切割中，就8比特图像的位平面抽取而言 （1）通常，如果将低阶比特面设为零值，对一幅图像的直方图有何影响 （2）如果将高阶比特面设为零值将对直方图有何影响 答：（1）如果将低阶比特面设为零，图像的不同灰度级的个数会减少，即某些灰度级的像素数会丢失，而像素总数是不变的，丢失的像素转移到其它未丢失的灰度级上，从而图像的直方图密度变低； （2）当图像高阶比特面设为零，高灰度级的像素会丢失，丢失的像素都转移到低灰度级上，从而导致图象直方图只有低灰度区，高灰度区直方图均为零。

5、有一数字序列为： （106，114，109，145，177，186，188，182，187） 1）利用一维三点平滑模板(1/3,1/3,1/3)对数据进行平滑。 2）利用一维拉普拉斯算子（1,-2,1）对数据进行锐化。 （边缘处理方式自定义，写出如何定义） 答：边缘处理方式为边缘灰度由相邻灰度（处理过的）替代。 1）平滑后的序列为 （110，110，123，144，170，184，186，186） 2）锐化算子 （-13，-13，41，-4，-23，-7，-8，11，11） 锐化后的序列为 （119，127，68，149，180，193，196，171，176） 6、近似一个离散导数的基本方法是对f(x+1,y)-f(x,y)取差分。试找到空域一阶微分滤波器传递函数在频域中进行等价的操作H(u,v) 。

基于matlab的形状识别

1、设计目的 基于Maltab或者C语言对图像进行识别。编写摄像头采集图像程序，对采集的图像进行预处理，如图像增强、图像分割等处理，对于处理的图像进行特征提取，根据特征进行模式识别，如对三角形、正方形与圆形的识别。 2、设计正文 2.1设计分析 1)编写摄像头采集图像程序 2)对采集的图像进行预处理 3)对于处理的图像进行特征提取 4)进行模式识别，区分各种形状 2.2设计原理 2.2.1图像预处理 彩色图像包含着大量的颜色信息，不但在存储上开销很大，而且在处理上也会降低系统的执行速度，因此在对图像进行识别等处理中经常将彩色图像转变为灰度图像，以加快处理速度。由彩色转换为灰度的过程叫做灰度化处理。选择的标准是经过灰度变换彩色图像包含着大量的颜色信息，不但在存储上开销很大，而且在处理上也会降低系统的执行速度，因此在对图像进行识别

等处理中经常将彩色图像转变为灰度图像，以加快处理速度。由彩色转换为灰度的过程叫做灰度化处理。选择的标准是经过灰度变换。 2.2.2对于处理的图像进行特征值提取 二值图像是指整幅图像画面内仅黑、白二值的图像。在实际的车牌处理系统中，进行图像二值变换的关键是要确定合适的阀值，使得字符与背景能够分割开来，二值变换的结果图像必须要具备良好的保形性，不丢掉有用的形状信息，不会产生额外的空缺等等。车牌识别系统要求处理的速度高、成本低、信息量大，采用二值图像进行处理，能大大地提高处理效率。阈值处理的操作过程是先由用户指定或通过算法生成一个阈值，如果图像中某中像素的灰度值小于该阈值，则将该像素的灰度值设置为0或255，否则灰度值设置为255或0。 两个具有不同灰度值的相邻区域之间总存在边缘，边缘就是灰度值不连续的结果，是图像分割、纹理特征提取和形状特征提取等图像分析的基础。为了对有意义的边缘点进行分类，与这个点相联系的灰度级必须比在这一点的背景上变换更有效，我们通过门限方法来决定一个值是否有效。所以，如果一个点的二维一阶导数比指定的门限大，我们就定义图像中的次点是一个边缘点，一组这样的依据事先定好的连接准则相连的边缘点就定义为一条边缘。经过一阶的导数的边缘检测，所求的一阶导数高于某个阈

哈夫曼编码的方法

1．哈夫曼编码的方法 编码过程如下: (1) 将信源符号按概率递减顺序排列; (2) 把两个最小的概率加起来, 作为新符号的概率; (3) 重复步骤(1) 、(2), 直到概率和达到1 为止; (4) 在每次合并消息时，将被合并的消息赋以1和0或0和1； (5) 寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0； (6) 对每个符号写出"1"、"0"序列（从码数的根到终节点）。 2．哈夫曼编码的特点 ①哈夫曼方法构造出来的码不是唯一的。 原因 ·在给两个分支赋值时, 可以是左支( 或上支) 为0, 也可以是右支( 或下支) 为0, 造成编码的不唯一。 ·当两个消息的概率相等时, 谁前谁后也是随机的, 构造出来的码字就不是唯一的。 ②哈夫曼编码码字字长参差不齐, 因此硬件实现起来不大方便。 ③哈夫曼编码对不同的信源的编码效率是不同的。 ·当信源概率是2 的负幂时, 哈夫曼码的编码效率达到100%; ·当信源概率相等时, 其编码效率最低。 ·只有在概率分布很不均匀时, 哈夫曼编码才会收到显著的效果, 而在信源分布均匀的情况下, 一般不使用哈夫曼编码。 ④对信源进行哈夫曼编码后, 形成了一个哈夫曼编码表。解码时, 必须参照这一哈夫编码表才能正确译码。 ·在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果时, 必须考虑哈夫曼编码表占有的比特数。在某些应用场合, 信源概率服从于某一分布或存在一定规律

使用缺省的哈夫曼编码表有

解：为了进行哈夫曼编码, 先把这组数据由大到小排列, 再按上方法处理 （1）将信源符号按概率递减顺序排列。 （2）首先将概率最小的两个符号的概率相加，合成一个新的数值。 （3）把合成的数值看成是一个新的组合符号概率，重复上述操作，直到剩下最后两个符号。 5．4．2 Shannon-Famo编码 Shannon-Famo(S-F) 编码方法与Huffman 的编码方法略有区别, 但有时也能编 出最佳码。 1．S－F码主要准则 符合即时码条件; 在码字中,1 和0 是独立的, 而且是( 或差不多是)等概率的。 这样的准则一方面能保证无需用间隔区分码字,同时又保证每一位码字几乎有 1位的信息量。 2．S－F码的编码过程 信源符号按概率递减顺序排列; 把符号集分成两个子集, 每个子集的概率和相等或近似相等;