数字图像处理第八章.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "数字图像处理第八章.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6J0yUat6Ow51",
        "colab_type": "text"
      },
      "source": [
        "### 数字图像处理第八章\n",
        "\n",
        "Input an original image with no any compressed formats ( e.g. BMP), Program for implementing following compress coding for this image, \n",
        "\n",
        "(1) Huffman coding compression\n",
        "\n",
        "(2) Arithmetic coding\n",
        "\n",
        "And compute their average coding length respectively and have a comparison analysis."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dFYVk9jjNfty",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import cv2\n",
        "import os\n",
        "import numpy as np"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OYGLc2RTN_CA",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Node:\n",
        "    def __init__(self, name, weight):\n",
        "        self.name = name\n",
        "        self.weight = weight\n",
        "        self.left = None\n",
        "        self.right = None\n",
        "        self.father = None\n",
        "\n",
        "    def is_left_child(self):\n",
        "        return self.father.left == self"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mA5VHWqDOAAy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def create_prim_nodes(data_set, labels):\n",
        "    nodes = []\n",
        "    for i in range(len(labels)):\n",
        "        nodes.append( Node(labels[i],data_set[i]) )\n",
        "    return nodes"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hSekQQLGOC8x",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def my_create_HF_tree(nodes):\n",
        "    tree_nodes = nodes.copy()\n",
        "    while len(tree_nodes) > 1:\n",
        "        tree_nodes.sort(key=lambda node: node.weight)\n",
        "        new_left = tree_nodes.pop(0)\n",
        "        new_right = tree_nodes.pop(0)\n",
        "        new_node = Node(None, (new_left.weight + new_right.weight))\n",
        "        new_node.left = new_left\n",
        "        new_node.right = new_right\n",
        "        new_left.father = new_right.father = new_node\n",
        "        tree_nodes.append(new_node)\n",
        "    tree_nodes[0].father = None\n",
        "    return tree_nodes[0]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "boVdXqb8OHej",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def my_get_huffman_code(nodes):\n",
        "    codes = {}\n",
        "    for node in nodes:\n",
        "        code=''\n",
        "        name = node.name\n",
        "        while node.father != None:\n",
        "            if node.is_left_child():\n",
        "                code = '0' + code\n",
        "            else:\n",
        "                code = '1' + code\n",
        "            node = node.father\n",
        "        codes[name] = code\n",
        "    return codes"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1d2QiiqnOLtP",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def my_huffman_coding(src_path):\n",
        "    img = cv2.imread(src_path, cv2.IMREAD_GRAYSCALE)\n",
        "    labels = [i for i in range(256)]\n",
        "    data_set = [0 for i in range(256)]\n",
        "    rows, cols = np.shape(img)\n",
        "    for i in range(rows):\n",
        "        for j in range(cols):\n",
        "            data_set[img[i, j]] += 1\n",
        "\n",
        "    nodes = create_prim_nodes(data_set,labels)\n",
        "    root = my_create_HF_tree(nodes)\n",
        "    codes = my_get_huffman_code(nodes)\n",
        "\n",
        "    L_sum = 0\n",
        "    n1 = rows * cols * 8\n",
        "    n2 = 0.0\n",
        "    for key in codes.keys():\n",
        "        L_sum += (data_set[key] * len(codes[key]))\n",
        "    n2 += L_sum\n",
        "    C_R = n1 / n2\n",
        "    print(\"Huffman coding compression: \")\n",
        "    print(\"\\tCompression Ratio: \", C_R)\n",
        "    R_D = 1 - 1 / C_R\n",
        "    print(\"\\tRedundancy: \", R_D)\n",
        "    L_avg = L_sum / (rows * cols)\n",
        "    print(\"\\tAverage coding length: \", L_avg)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "k9Ae8LYbOPWC",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        },
        "outputId": "6c9285c9-e8df-4552-fbd9-8e349100cbee"
      },
      "source": [
        "if __name__ == '__main__':\n",
        "    src_path = \"/content/drive/My Drive/数字图像处理/Image/Lenna.jpg\"\n",
        "    my_huffman_coding(src_path)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Huffman coding compression: \n",
            "\tCompression Ratio:  1.0741564452237333\n",
            "\tRedundancy:  0.0690369131549432\n",
            "\tAverage coding length:  7.447704694760455\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4w0VxuzMOZC7",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}