Codage Golomb-Rice.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.6.6"
    },
    "colab": {
      "name": "Codage Golomb-Rice.ipynb",
      "provenance": [],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/gabilodeau/INF8770/blob/master/Codage%20Golomb-Rice.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GgTtqH_Ffpm9",
        "colab_type": "text"
      },
      "source": [
        "INF8770 Technologies multimédias\n",
        "\n",
        "Polytechnique Montréal\n",
        "\n",
        "Exemple de codage Golomb-Rice"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lM-m-P6Jfpm_",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import numpy as np"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tjdpkSWDfpnI",
        "colab_type": "text"
      },
      "source": [
        "Message à coder"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gXa13nD1fpnJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "Message = [1,1,3,2,5,5,6,1,1,2,3,5,6,7,5,4,9,8,3,6,11,2,4,3,5,6,7]"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pyDqqmRufpnO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "MessageTrie = sorted(Message)"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "O-_TrWNWfpnS",
        "colab_type": "text"
      },
      "source": [
        "Recherche de la valeur médiane M. Il est possible d'utiliser la fonction median de numpy"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xN0K6X7cfpnS",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "fb72424e-05c1-4a88-b662-6b5bb899bf33"
      },
      "source": [
        "elem = int(np.floor(len(MessageTrie)/2.0))\n",
        "if len(MessageTrie)%2 == 0:\n",
        "    M = round((MessageTrie[elem-1]+MessageTrie[elem])/2.0)\n",
        "else :\n",
        "    M = MessageTrie[elem]\n",
        "    \n",
        "print(\"M =\",M)"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "M = 5\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "collapsed": true,
        "id": "LBNqVxGmfpnZ",
        "colab_type": "text"
      },
      "source": [
        "Création des tables: 1) Unaire. Pour coder i, il faut i '1' suivi d'un '0'"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wzfUgpR0fpna",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "4830c797-e4b2-4a24-aa1e-d7f986bc485d"
      },
      "source": [
        "symboleMax = int(max(Message)/M)\n",
        "unaire = ['0']*(symboleMax+1)\n",
        "for i in range(1,symboleMax+1):\n",
        "        unaire[i] = '1' + unaire[i-1] \n",
        "        \n",
        "print(unaire)"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "['0', '10', '110']\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "O911trxlfpne",
        "colab_type": "text"
      },
      "source": [
        "Création des tables: 1) Binaire tronqué. 2^k-b code de longueur k et 2b code de longueur k+1"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mjeuuRzEfpnf",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        },
        "outputId": "a7359897-4b4b-42f0-de0f-73778fe42da1"
      },
      "source": [
        "bintronque = ['0']*M\n",
        "k = int(np.floor(np.log2(M)))\n",
        "b=M-2**k\n",
        "print(\"k={0} et b={1}\".format(k,b))\n",
        "for i in range(M):\n",
        "    if i < 2**k-b : \n",
        "        bintronque[i]=\"{:b}\".format(i).zfill(k)\n",
        "    else :\n",
        "        bintronque[i]=\"{:b}\".format(i+2**k-b).zfill(k+1) \n",
        "\n",
        "print(bintronque)"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "k=2 et b=1\n",
            "['00', '01', '10', '110', '111']\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rPRYKWhsfpnl",
        "colab_type": "text"
      },
      "source": [
        "Codage du message et mesure de la longueur en bits du message codé"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qOylcwIhfpnm",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 88
        },
        "outputId": "de445a6d-fafc-4c9f-c3a1-81e7088fd760"
      },
      "source": [
        "MessageCode = []\n",
        "longueur = 0\n",
        "for i in range(len(Message)):\n",
        "    quotient = int(Message[i]/M)\n",
        "    reste = int(Message[i]%M)\n",
        "    MessageCode+=[[unaire[quotient],bintronque[reste]]]\n",
        "    longueur = longueur + len(unaire[quotient]) + len(bintronque[reste])\n",
        "    \n",
        "longueurOriginale = np.ceil(np.log2(max(Message)))*len(Message)    \n",
        "print(MessageCode)\n",
        "print(\"Longueur = {0}\".format(longueur))\n",
        "print(\"Longueur original = {0}\".format(longueurOriginale))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[['0', '01'], ['0', '01'], ['0', '110'], ['0', '10'], ['10', '00'], ['10', '00'], ['10', '01'], ['0', '01'], ['0', '01'], ['0', '10'], ['0', '110'], ['10', '00'], ['10', '01'], ['10', '10'], ['10', '00'], ['0', '111'], ['10', '111'], ['10', '110'], ['0', '110'], ['10', '01'], ['110', '01'], ['0', '10'], ['0', '111'], ['0', '110'], ['10', '00'], ['10', '01'], ['10', '10']]\n",
            "Longueur = 104\n",
            "Longueur original = 108.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Gtbq6wIqfpnr",
        "colab_type": "text"
      },
      "source": [
        "La compression sera meilleure si les quotients sont petits et si la distribution des symboles du message est plutôt géométrique."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "76NvsjyLfpns",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}