5.1 Python影像處理之影像編碼-哈夫曼編碼

1 演算法原理

哈夫曼編碼是一種根據詞頻變化的變長二進制編碼方式，多用于壓縮演算法，將信源符號按出現概率從大到小排列,然后選2個最小的結合,依次類推,直到剩下2個符號為止，使用哈夫曼編碼，結果不唯一，平均碼長相同，接近信源熵，方法容易簡單，但是對于接近等概率分布的信源編碼效率低，

設某信源產生有五種符號u1、u2、u3、u4和u5，對應概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1，首先，將符號按照概率由大到小排隊，如圖所示，編碼時，從最小概率的兩個符號開始，可選其中一個支路為0，另一支路為1，這里，我們選上支路為0，下支路為1，再將已編碼的兩支路的概率合并，并重新排隊，多次重復使用上述方法直至合并概率歸一時為止，從圖（a）和（b）可以看出，兩者雖平均碼長相等，但同一符號可以有不同的碼長，即編碼方法并不唯一，其原因是兩支路概率合并后重新排隊時，可能出現幾個支路概率相等，造成排隊方法不唯一，一般，若將新合并后的支路排到等概率的最上支路，將有利于縮短碼長方差，且編出的碼更接近于等長碼，這里圖（a）的編碼比（b）好，

2 代碼

運行代碼說明

1.要改變代碼中的圖片地址（地址不能有中文）

更改put(path)函式中的路徑put(r'../image/image1.jpg')

2.注意最后的plt.savefig('1.new.jpg')是保存plt影像，如果不使用可以注釋掉

注意本次代碼實驗是對圖片進行壓縮后再解壓，顯示解壓前后的圖片是否有變化，

import os

import cv2
from queue import PriorityQueue
import numpy as np
import math
import struct
import matplotlib.pyplot as plt
'''
對影像哈夫曼編碼/解碼
根據哈夫曼編碼灰度影像，保存到檔案中；讀取哈夫曼編碼的檔案，解碼成影像，與原影像對比，
'''


class HuffmanNode(object):
    '''
    哈夫曼樹的節點類
    '''

    def __init__(self, value, key=None, symbol='', left_child=None, right_child=None):
        '''
        初始化哈夫曼樹的節點
        :param value: 節點的值，i.e. 元素出現的頻率
        :param key: 節點代表的元素，非葉子節點為None
        :param symbol: 節點的哈夫曼編碼，初始化必須為空字串
        :param left_child: 左子節點
        :param right_child: 右子節點
        '''
        self.left_child = left_child
        self.right_child = right_child
        self.value = value
        self.key = key
        assert symbol == ''
        self.symbol = symbol

    def __eq__(self, other):
        '''
        用于比較兩個HuffmanNode的大小，等于號，根據value的值比較
        :param other:
        :return:
        '''
        return self.value == other.value

    def __gt__(self, other):
        '''
        用于比較兩個HuffmanNode的大小，大于號，根據value的值比較
        :param other:
        :return:
        '''
        return self.value > other.value

    def __lt__(self, other):
        '''
        用于比較兩個HuffmanNode的大小，小于號，根據value的值比較
        :param other:
        :return:
        '''
        return self.value < other.value


def createTree(hist_dict: dict) -> HuffmanNode:
    '''
    構造哈夫曼樹
    可以寫一個HuffmanTree的類
    :param hist_dict: 影像的直方圖，dict = {pixel_value: count}
    :return: HuffmanNode, 哈夫曼樹的根節點
    '''
    # 借助優先級佇列實作直方圖頻率的排序，取出和插入元素很方便
    q = PriorityQueue()

    # 根據傳入的像素值和頻率字典構造哈夫曼節點并放入佇列中
    for k, v in hist_dict.items():
        # 這里放入的都是之后哈夫曼樹的葉子節點，key都是各自的元素
        q.put(HuffmanNode(value=v, key=k))

    # 判斷條件，直到佇列中只剩下一個根節點
    while q.qsize() > 1:
        # 取出兩個最小的哈夫曼節點，佇列中這兩個節點就不在了
        l_freq, r_freq = q.get(), q.get()
        # 增加他們的父節點，父節點值為這兩個哈夫曼節點的和，但是沒有key值；左子節點是較小的，右子節點是較大的
        node = HuffmanNode(value=l_freq.value + r_freq.value, left_child=l_freq, right_child=r_freq)
        # 把構造的父節點放在佇列中，繼續排序和取放、構造其他的節點
        q.put(node)

    # 佇列中只剩下根節點了，回傳根節點
    return q.get()


def walkTree_VLR(root_node: HuffmanNode, symbol=''):
    '''
    前序遍歷一個哈夫曼樹，同時得到每個元素(葉子節點)的編碼，保存到全域的Huffman_encode_dict
    :param root_node: 哈夫曼樹的根節點
    :param symbol: 用于對哈夫曼樹上的節點進行編碼，遞回的時候用到，為'0'或'1'
    :return: None
    '''
    # 為了不增加變數復制的成本，直接使用一個dict型別的全域變數保存每個元素對應的哈夫曼編碼
    global Huffman_encode_dict

    # 判斷節點是不是HuffmanNode，因為葉子節點的子節點是None
    if isinstance(root_node, HuffmanNode):
        # 編碼操作，改變每個子樹的根節點的哈夫曼編碼，根據遍歷程序是逐漸增加編碼長度到完整的
        root_node.symbol += symbol
        # 判斷是否走到了葉子節點，葉子節點的key!=None
        if root_node.key != None:
            # 記錄葉子節點的編碼到全域的dict中
            Huffman_encode_dict[root_node.key] = root_node.symbol

        # 訪問左子樹，左子樹在此根節點基礎上賦值'0'
        walkTree_VLR(root_node.left_child, symbol=root_node.symbol + '0')
        # 訪問右子樹，右子樹在此根節點基礎上賦值'1'
        walkTree_VLR(root_node.right_child, symbol=root_node.symbol + '1')

    return


def encodeImage(src_img: np.ndarray, encode_dict: dict):
    '''
    用已知的編碼字典對影像進行編碼
    :param src_img: 原始影像資料，必須是一個向量
    :param encode_dict: 編碼字典，dict={element:code}
    :return: 影像編碼后的字串，字串中只包含'0'和'1'
    '''
    img_encode = ""
    assert len(src_img.shape) == 1, '`src_img` must be a vector'
    for pixel in src_img:
        img_encode += encode_dict[pixel]
    return img_encode


def writeBinImage(img_encode: str, huffman_file: str):
    '''
    把編碼后的二進制影像資料寫入到檔案中
    :param img_encode: 影像編碼字串，只包含'0'和'1'
    :param huffman_file: 要寫入的影像編碼資料檔案的路徑
    :return:
    '''
    # 檔案要以二進制打開
    with open(huffman_file, 'wb') as f:
        # 每8個bit組成一個byte
        for i in range(0, len(img_encode), 8):
            # 把這一個位元組的資料根據二進制翻譯為十進制的數字
            img_encode_dec = int(img_encode[i:i + 8], 2)
            # 把這一個位元組的十進制資料打包為一個unsigned char，大端（可省略）
            img_encode_bin = struct.pack('>B', img_encode_dec)
            # 寫入這一個位元組資料
            f.write(img_encode_bin)


def readBinImage(huffman_file: str, img_encode_len: int):
    '''
    從二進制的編碼檔案讀取資料，得到原來的編碼資訊，為只包含'0'和'1'的字串
    :param huffman_file: 保存的編碼檔案
    :param img_encode_len: 原始編碼的長度，必須要給出，否則最后一個位元組對不上
    :return: str，只包含'0'和'1'的編碼字串
    '''
    code_bin_str = ""
    with open(huffman_file, 'rb') as f:
        # 從檔案讀取二進制資料
        content = f.read()
        # 從二進制資料解包到十進制資料，所有資料組成的是tuple
        code_dec_tuple = struct.unpack('>' + 'B' * len(content), content)
        for code_dec in code_dec_tuple:
            # 通過bin把解壓的十進制資料翻譯為二進制的字串，并填充為8位，否則會丟失高位的0
            # 0 -> bin() -> '0b0' -> [2:] -> '0' -> zfill(8) -> '00000000'
            code_bin_str += bin(code_dec)[2:].zfill(8)
        # 由于原始的編碼最后可能不足8位，保存到一個位元組的時候會在高位自動填充0，讀取的時候需要去掉填充的0，否則讀取出的編碼會比原來的編碼長
        # 計算讀取的編碼字串與原始編碼字串長度的差，差出現在讀取的編碼字串的最后一個位元組，去掉高位的相應數量的0就可以
        len_diff = len(code_bin_str) - img_encode_len
        # 在讀取的編碼字串最后8位去掉高位的多余的0
        code_bin_str = code_bin_str[:-8] + code_bin_str[-(8 - len_diff):]
    return code_bin_str


def decodeHuffman(img_encode: str, huffman_tree_root: HuffmanNode):
    '''
    根據哈夫曼樹對編碼資料進行解碼
    :param img_encode: 哈夫曼編碼資料，只包含'0'和'1'的字串
    :param huffman_tree_root: 對應的哈夫曼樹，根節點
    :return: 原始影像資料展開的向量
    '''
    img_src_val_list = []

    # 從根節點開始訪問
    root_node = huffman_tree_root
    # 每次訪問都要使用一位編碼
    for code in img_encode:
        # 如果編碼是'0'，說明應該走到左子樹
        if code == '0':
            root_node = root_node.left_child
        # 如果編碼是'1'，說明應該走到右子樹
        elif code == '1':
            root_node = root_node.right_child
        # 只有葉子節點的key才不是None，判斷當前走到的節點是不是葉子節點
        if root_node.key != None:
            # 如果是葉子節點，則記錄這個節點的key，也就是哪個原始資料的元素
            img_src_val_list.append(root_node.key)
            # 訪問到葉子節點之后，下一次應該從整個數的根節點開始訪問了
            root_node = huffman_tree_root
    return np.asarray(img_src_val_list)


def decodeHuffmanByDict(img_encode: str, encode_dict: dict):
    '''
    另外一種解碼策略是先遍歷一遍哈夫曼樹得到所有葉子節點編碼對應的元素，可以保存在字典中，再對字串的子串逐個與字典的鍵進行比對，就得到相應的元素是什么，
    用C語言也可以這么做，
    這里不再對哈夫曼樹重新遍歷了，因為之前已經遍歷過，所以直接使用之前記錄的編碼字典就可以，
    :param img_encode: 哈夫曼編碼資料，只包含'0'和'1'的字串
    :param encode_dict: 編碼字典dict={element:code}
    :return: 原始影像資料展開的向量
    '''
    img_src_val_list = []
    decode_dict = {}
    # 構造一個key-value互換的字典，i.e. dict={code:element}，后邊方便使用
    for k, v in encode_dict.items():
        decode_dict[v] = k
    # s用來記錄當前字串的訪問位置，相當于一個指標
    s = 0
    # 只要沒有訪問到最后
    while len(img_encode) > s + 1:
        # 遍歷字典中每一個鍵code
        for k in decode_dict.keys():
            # 如果當前的code字串與編碼字串前k個字符相同，k表示code字串的長度，那么就可以確定這k個編碼對應的元素是什么
            if k == img_encode[s:s + len(k)]:
                img_src_val_list.append(decode_dict[k])
                # 指標移動k個單位
                s += len(k)
                # 如果已經找到了相應的編碼了，就可以找下一個了
                break
    return np.asarray(img_src_val_list)


def put(path):
    
    # 即使原影像是灰度圖，也需要加入GRAYSCALE標志
    src_img = cv2.imread(path, cv2.IMREAD_GRAYSCALE)
    # 記錄原始影像的尺寸，后續還原影像要用到
    src_img_w, src_img_h = src_img.shape[:2]
    # 把影像展開成一個行向量
    src_img_ravel = src_img.ravel()

    # {pixel_value:count}，保存原始影像每個像素對應出現的次數，也就是直方圖
    hist_dict = {}

    # 得到原始影像的直方圖，出現次數為0的元素(像素值)沒有加入
    for p in src_img_ravel:
        if p not in hist_dict:
            hist_dict[p] = 1
        else:
            hist_dict[p] += 1

    # 構造哈夫曼樹
    huffman_root_node = createTree(hist_dict)
    # 遍歷哈夫曼樹，并得到每個元素的編碼，保存到Huffman_encode_dict,這是全域變數
    walkTree_VLR(huffman_root_node)
    global Huffman_encode_dict
    print('哈夫曼編碼字典：', Huffman_encode_dict)
    # 根據編碼字典編碼原始影像得到二進制編碼資料字串
    img_encode = encodeImage(src_img_ravel, Huffman_encode_dict)
    # 把二進制編碼資料字串寫入到檔案中，后綴為bin
    writeBinImage(img_encode, 'huffman_bin_img_file.bin')

    # 讀取編碼的檔案，得到二進制編碼資料字串
    img_read_code = readBinImage('huffman_bin_img_file.bin', len(img_encode))
    # 解碼二進制編碼資料字串，得到原始影像展開的向量
    # 這是根據哈夫曼樹進行解碼的方式
    img_src_val_array = decodeHuffman(img_read_code, huffman_root_node)
    # 這是根據編碼字典進行解碼的方式，更慢一些
    # img_src_val_array = decodeHuffmanByDict(img_read_code, Huffman_encode_dict)

    # 確保解碼的資料與原始資料大小一致
    assert len(img_src_val_array) == src_img_w * src_img_h
    # 恢復原始二維影像
    img_decode = np.reshape(img_src_val_array, [src_img_w, src_img_h])


    # 計算平均編碼長度和編碼效率
    total_code_len = 0
    total_code_num = sum(hist_dict.values())
    avg_code_len = 0
    I_entropy = 0
    for key in hist_dict.keys():
        count = hist_dict[key]
        code_len = len(Huffman_encode_dict[key])
        prob = count / total_code_num
        avg_code_len += prob * code_len
        I_entropy += -(prob * math.log2(prob))
    S_eff = I_entropy / avg_code_len
    print("平均編碼長度為：{:.3f}".format(avg_code_len))
    print("編碼效率為：{:.6f}".format(S_eff))

    # 壓縮率
    ori_size = src_img_w*src_img_h*8/ (1024*8)
    comp_size = len(img_encode)/(1024*8)
    comp_rate = 1 - comp_size/ori_size
    print('原圖灰度圖大小', ori_size, 'KB  壓縮后大小', comp_size, 'KB  壓縮率',comp_rate, '%')

    plt.rcParams['font.sans-serif'] = ['SimHei']
    plt.subplot(121), plt.imshow(src_img, plt.cm.gray), plt.title('原圖灰度影像'), plt.axis('off')
    plt.subplot(122), plt.imshow(img_decode, plt.cm.gray), plt.title('解壓后'), plt.axis('off')
    # plt.savefig('1.1new.jpg')
    plt.show()


if __name__ == '__main__':
    # 哈夫曼編碼字典{pixel_value:code}，在函式中作為全域變數用到了
    Huffman_encode_dict = {}

    # 影像處理函式，要傳入路徑
    put(r'../image/image3.jpg')

3 效果

本文使用的壓縮率是 1- 壓縮后大小/壓縮前大小

而且不是使用檔案格式對比，而是比較圖片像素占用的bit