对一幅BMP格式的灰度图像进行二元霍夫曼编码和译码
信息论的实验终于结束了,才开始写python,写的比较乱,仅供参考
主要思想
霍夫曼编码关键在于树的构造，其构造要达到的目的为权重越大越靠近叶子结点，权重越小越靠近根，即使出现次数越多的值的码长越短。
构造时每次去权重最小的两个点合并为一个点n，这两个点为点n的左右子结点，这两个点的权重的和为结点n的权重，然后重复上述操作直至剩下一个点。如：
程序说明
1、还原程序直接将图像大小写死了为256* 256
2、程序中编码效率的计算为信源熵除以平均码长 3、了解了python中的pillow库 Image.open(图像)打开图像 getpixel((x,y))得到图像x,y处像素值 Image.fromarry(数组,astype('uint8')).convert('L')将一个数组还原为图像，其中L表示灰度图 show()展示图像 save()保存图像 4、统计一个列表中各数值的个数#需要导入from collections import Counterc = Counter()for num in list: c[num] = c[num] + 1#list为一个列表，比如list=[11,11,22,22,22,33],则运行结果c={11:2,22:3,33:1} 5、np.arrry(矩阵)可以将矩阵变为数组
需要导入import numpy as np 程序还原时发现图像是镜像的，不知哪有问题，后来干脆把得到的二维数组转置一下，发现可以 转置有两种方法： （1）T: 数组.T （2）reshape：np.reshape(数组)编码程序
import osimport mathfrom PIL import Imagefrom collections import Counter#定义树的结构class BinaryTree: def __init__(self,weight,name=None): self.name=name self.weight = weight self.leftChild = None self.rightChild = None#读取图像,将像素存入一个列表im_listimage_name=input('请输入需要编码的图像')im = Image.open(image_name)width = im.widthheight = im.heightim_list = []for x in range(width): raw_list = [] for y in range(height): pixel = im.getpixel((x, y)) raw_list.append(pixel) im_list.extend(raw_list)sum=len(im_list)#计算像素个数总和#统计各像素的的个数,将像素及对应次数存入字典cc = Counter()for num in im_list: c[num] = c[num] + 1sum_v=[]#各像素的概率H=0#信源熵for i in range(0,256): if i in c: sum_v.append(c[i]/sum) H=H+c[i]/sum*math.log(sum/c[i],2) else: sum_v.append(0)#先将字典c中的各对元素转化为Binarytree类，即将各对元素变为结点，并存到Node列表中node=[]for i in range(0,len(c)): temp_key=min(c,key=c.get) temp_num=c[temp_key] node.append(BinaryTree(temp_num,temp_key)) del c[temp_key]#对表内元素按照权重排序的函数def sort_weight(elem): return elem.weightnode.sort(key=sort_weight)#构造哈夫曼树while len(node)!=1: small_1=node.pop(0) small_2=node.pop(0) newnode=BinaryTree(0) newnode.weight=small_1.weight+small_2.weight newnode.rightChild=small_1 newnode.leftChild=small_2 node.append(newnode) node.sort(key=sort_weight)tree=node.pop(0)#进行编码huffcode={}#最后像素和所对应的的字典都存放在这里bin_str=[]#想当于一个栈结构，用于存放编码bin_str.append('')#迭代遍历函数def coding (tree): Left(tree) Right(tree) bin_str.pop(-1)#左树遍历def Left(tree): tree1=tree.leftChild bin_str.append(bin_str[-1] + '0') if tree1.name!=None: huffcode[tree1.name] = bin_str.pop(-1) return coding(tree1)#右树遍历def Right(tree): tree2 = tree.rightChild bin_str.append(bin_str[-1] + '1') if tree2.name != None: huffcode[tree2.name]=bin_str.pop(-1) return coding(tree2)#对各像素编码,并将得到的编码表写入文件coding(tree)filehuff=open('huffcode.txt',mode='w')filehuff.write(str(huffcode))#对图像进行编码，并将编码写入文件imcode.txtim_code=[]while len(im_list)!=0 : im_code.append(huffcode[im_list.pop(0)])filecode=open('imcode.txt',mode='w')filecode.write(str(im_code))print('编码成功!')sum_l=[]#各像素码长for i in range(0,256): if i in huffcode: sum_l.append(len(huffcode[i])) else: sum_l.append(0)L=0#平均码长while(len(sum_l)!=0): L=sum_l.pop(0)*sum_v.pop(0)+Lprint('编码效率为')print(H/L) 还原程序
import osimport reimport numpy as npfrom PIL import Image#定义树的结构class BinaryTree: def __init__(self,name=None): self.name=name self.leftChild = None self.rightChild = None#得到哈夫曼编码表,保存为一个列表file=open('huffcode.txt')c={}for each_word in file: a=re.split(r'[\{\}\:\,\'\s+]+', each_word)a.pop(0)a.pop(-1)#构造哈夫曼编码的树def encode(nodeser,tree_leave,strlen,str_len): if str[strlen] == '0': if str_len==1: nodeser.leftChild=tree_leave return elif nodeser.leftChild==None: newnode=BinaryTree() nodeser.leftChild =newnode encode(nodeser.leftChild,tree_leave,strlen+1,str_len-1) else: if str_len == 1: nodeser.rightChild = tree_leave return elif nodeser.rightChild == None: newnode = BinaryTree() nodeser.rightChild = newnode encode(nodeser.rightChild, tree_leave, strlen + 1, str_len - 1) returntree=BinaryTree()while len(a)!=0: name=a.pop(0) str=a.pop(0) tree_leave=BinaryTree(name) encode(tree,tree_leave,0,len(str))#读取经过哈夫曼编码后的图片的文档file2=open('imcode.txt')for each_word in file2: im=re.split(r'[\[\]\,\'\s+]+', each_word)im.pop(0)im.pop(-1)strcode=''#先转化为一串01串while len(im)!=0: strcode=strcode+im.pop(0)tree_copy=treereimg=[]#遍历树，得到相对应的像素值for i in range(0,len(strcode)): if strcode[i]=='0': tree_copy=tree_copy.leftChild else: tree_copy=tree_copy.rightChild if tree_copy.name!=None: reimg.append(tree_copy.name) tree_copy=tree#变为二维列表存储reimage=[]for i in range(0,256): reimage.append([]) for j in range(0,256): reimage[i].append(reimg.pop(0))#变为数组形式，并转置iii=np.array(reimage)iii=iii.T#变为图像image=Image.fromarray(iii.astype('uint8')).convert('L')#展示并保存为dd.bmpimage.show()image.save('dd.bmp') 运行结果
对如下图像编码(大小为256* 256,因为不能上传bmp图像，所以示例如下)
得到的两个文件，一个是像素值与编码的对应关系，一个为图像的编码结果
