6_Line_Segment_Detector.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Parameters used by the notebook\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "from __future__ import division, print_function\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.rcParams['image.cmap'] = 'gray'\n",
    "plt.rcParams['image.interpolation'] = 'none'\n",
    "plt.rcParams['figure.figsize'][:] = [5, 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Line Segment Detector\n",
    "\n",
    "Dans cette section, nous vous proposons d'appliquer ce que vous avez appris sur Python pour implémenter une version simplifiée du **Line Segment Detector** proposé par *R. Grompone von Gioi et al.* en 2012.  \n",
    "\n",
    "Nous vous renvoyons vers la page IPOL du détecteur contenant une démo en ligne, les codes sources ainsi qu'un papier d'analyse des performances de ce détecteur :\n",
    "http://www.ipol.im/pub/art/2012/gjmr-lsd/\n",
    "\n",
    "## Fonctions utiles\n",
    "Dans cette partie nous définissons plusieurs fonctions qui nous serons utiles pour le reste du TP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def generate_synthetic_data(alpha=0.):\n",
    "    \"\"\"Generate a synthetic image to test the LSD detector.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    alpha: float\n",
    "        Noise intensity between [0. 1.]\n",
    "    \n",
    "    Returns\n",
    "    ------\n",
    "    im_out: array-like, shape (101, 101) \n",
    "        Floating image containing a white square in the middle corrupted by a random noise\n",
    "    \"\"\"\n",
    "    im_out = alpha * np.random.rand(101, 111)\n",
    "    im_out[24:76, 24:86] += 1. - alpha\n",
    "    return im_out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def imshow(im):\n",
    "    \"\"\"Plot the image.\"\"\"\n",
    "    plt.figure(figsize=(5,5))\n",
    "    plt.imshow(im)\n",
    "    plt.axis('off')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def plt_gradient(vertical_gradient, horizontal_gradient):\n",
    "    gradient = np.sqrt(vertical_gradient**2 + horizontal_gradient**2)\n",
    "    theta = np.arctan2(vertical_gradient, horizontal_gradient)\n",
    "    \n",
    "    # Plot the gradient norm\n",
    "    plt.figure(figsize=(10,10))\n",
    "    ax = plt.subplot(121)\n",
    "    ax.imshow(gradient, cmap='viridis')\n",
    "    ax = plt.subplot(122)\n",
    "    ax.imshow(theta, cmap='hsv')\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "im = generate_synthetic_data()\n",
    "imshow(im)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calcul du gradient de l'image\n",
    "\n",
    "Pour détecter les contours, nous allons avoir besoin de calculer le vecteur gradient associé à chaque pixels de l'image. \n",
    "\n",
    "**Exercice :** Complétez la fonction suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from scipy.ndimage import convolve\n",
    "\n",
    "def compute_gradient(im):\n",
    "    \"\"\"Compute the gradient vector of an image.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    \n",
    "    im: array-like, shape (width, length)\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    vertical_gradient: array-like, shape (widht, length)\n",
    "        Gradient values for the vertical direction.\n",
    "    \n",
    "    horizont_gradient: arrya-like, shape (widht, length)\n",
    "        Gradient values for the horizontal direction.\n",
    "    \"\"\"\n",
    "#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercice : **Pour être sur que `compute_gradient` se comporte correctement, tester la fonction pour différentes images."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Tester la fonction compute_gradient pour différentes images et valeurs de sigma.\n",
    "from skimage import data\n",
    "from skimage.io import imread\n",
    "\n",
    "#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Detection de lignes\n",
    "Pour minimiser l'impact du bruit sur le calcul du gradient, nous allons filtrer l'image avec un filtre gaussien de variance `sigma` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from skimage import filters\n",
    "\n",
    "im_orig = generate_synthetic_data()\n",
    "    \n",
    "sigma = 1.\n",
    "gradient = compute_gradient(filters.gaussian(im_orig, sigma=sigma))\n",
    "plt_gradient(*gradient)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une ligne dans LSD est définie comme un groupe de pixels voisin possédant une orientation du gradient proche. Bien évidemment un pixel ne peut appartenir qu'à une seule et unique ligne. \n",
    "\n",
    "**Exercice :** Implémenter la fonction `compute_line_group` qui groupe les pixels appartenant à une même ligne. \n",
    "- Nous utiliserons le tableau `checked` pour s'assurer que le pixel n'a pas déjà été utilisé.\n",
    "- Nous supposerons que nous connaissons la position `init_pos` d'un pixel de la ligne pour initier la recherche. \n",
    "- Nous considèrerons comme potentiels candidats uniquement les pixels qui ont une valeur supérieure à `grad min`.\n",
    "(Voir l'article [IPOL](http://www.ipol.im/pub/art/2012/gjmr-lsd/) pour plus d'informations sur le choix de `grad min`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def neighbors_in_line(pos, norm, theta, checked, tau, grad_min):\n",
    "    \"\"\"Define the neighbors positions which are in the same Line.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    pos: tuple\n",
    "        \n",
    "    norm: array-like\n",
    "        Gradient norm.\n",
    "    \n",
    "    theta: array-like\n",
    "        Gradient orientaiont.\n",
    "        \n",
    "    checked: array-like\n",
    "        Array of boolean telling if the pixel has been already checked.\n",
    "        \n",
    "    tau: float\n",
    "        \n",
    "    grad_min: float\n",
    "        \n",
    "    Returns\n",
    "    -------\n",
    "    selected_position: tuple of array-like\n",
    "        Coordinate of all the neighbors selected\n",
    "    \n",
    "    \"\"\"\n",
    "#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def compute_line_group(init_pos, norm, theta, checked, tau, q=2.):\n",
    "    \"\"\"Compute the pixels\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    init_pos: tuple\n",
    "    \n",
    "    norm: array-like\n",
    "        Gradient norm.\n",
    "    \n",
    "    theta: array-like\n",
    "        Gradient orientaiont.\n",
    "        \n",
    "    checked: array-like\n",
    "        Array of boolean telling if the pixel has been already checked.\n",
    "        \n",
    "    tau: float   \n",
    "    \n",
    "    q: float, optionnal\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    pos_queue : list of tuple\n",
    "        list of all the coordinate of pixels in the line group\n",
    "    \"\"\"\n",
    "#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Verification de la fonction \n",
    "init_pos = (50, 25)\n",
    "#init_pos = (25, 50)\n",
    "\n",
    "checked = np.zeros(im_orig.shape)\n",
    "norm, theta = gradient[0] ** 2 + gradient[1] ** 2, np.arctan2(*gradient)\n",
    "\n",
    "edge = compute_line_group(init_pos, norm, theta, checked, tau=.1)\n",
    "\n",
    "plt.imshow(checked)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Groupe de lignes\n",
    "Nous allons désormais calculer l'ensemble des lignes de l'image. Pour se faire le LSD propose de sélectionner les plus grandes valeurs de la norme du gradient comme point d'initialisation des lignes.\n",
    "\n",
    "**Exercice :** Implémentez la fonction `compute_lines` qui détermine l'ensemble des groupes de lignes de l'image."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compute_lines(gradient, tau, grad_max):\n",
    "    # Calcul de la norme et de l'orientation du gradient\n",
    "    \n",
    "    # Calcul des pixels de norme de gradient élevées\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Fonction d'affichage des groupes de lignes\n",
    "tau, grad_max = .1, .01\n",
    "\n",
    "_, width = im_orig.shape\n",
    "res = np.zeros((im_orig.shape))\n",
    "\n",
    "lines = compute_lines(gradient, tau=tau, grad_max=grad_max)\n",
    "print('Number of line: %d' %len(lines))\n",
    "for k, line in enumerate(lines):\n",
    "    pos = [l[0]* width + l[1] for l in line]\n",
    "    res.ravel()[pos] = np.random.rand()#k+10\n",
    "\n",
    "plt.figure(figsize=(10,10))\n",
    "plt.imshow(res, cmap='viridis')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calculs des paramètre de lignes\n",
    "\n",
    "Pour définir les paramètres de la lignes le *LSD* utilise la valeur des gradients.\n",
    "- Les centres sont définis comme la moyenne des pixels pondérés par la norm des gradients.\n",
    "- La direction de la ligne par le vecteur propre associé à la plus petite valeur propre de la matrice de covariance pondéré par les gradient de l'image.\n",
    "- La taille de sorte que tout les pixels du groupe soient inclus dans la ligne\n",
    "\n",
    "Complétez les fonctions suivantes :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from scipy import linalg \n",
    "\n",
    "def compute_lines_parameters(lines, norm):\n",
    "    centers = np.empty((len(lines), 2))\n",
    "    alphas = np.empty((len(lines), 1))\n",
    "    sizes = np.empty((len(lines), 2))\n",
    "    \n",
    "    # Completer le calcul de centers, alphas et sizes\n",
    "    \n",
    "    return centers, alphas, sizes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Complétez les fonctions suivantes de sortes à afficher les lignes et les rectangles détectés :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.patches as patches\n",
    "from matplotlib.transforms import Affine2D\n",
    "\n",
    "def draw_rectangle(ax, center, angle, length, width):\n",
    "    rect = patches.Rectangle((-length // 2, -width // 2), length, width, ec=np.random.rand(3,1), lw=3, fill=False)\n",
    "    rect.set_transform(Affine2D().rotate(np.pi/2 - angle) + \n",
    "                       Affine2D().translate(center[1], center[0]) + \n",
    "                       ax.transData)\n",
    "    ax.add_patch(rect) \n",
    "    \n",
    "def plot_rectangles(im, centers, alphas, sizes):\n",
    "#\n",
    "\n",
    "def plot_lines(im, centers, alphas, sizes):\n",
    "#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Afficher le résultat de votre détecteur de lignes :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "lines = compute_lines(gradient, tau=tau, grad_max=grad_max)\n",
    "params = compute_lines_parameters(lines, norm)\n",
    "plot_rectangles(norm, *params)\n",
    "plot_lines(im_orig, *params)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Critère de bruit\n",
    "Le premier résultat obtenue est plutôt de bonne qualité quand il n'y a pas de bruit. Néanmoins, en présence de bruit, les performances de l'algorithmes chutent rapidement. Pour résoudre ce problème, le LSD utilise un critère a contrario lui permettant de déterminer si l'alignement de points est du au bruit.\n",
    "\n",
    "Vous pouvez trouver la formule du critère NFA sur :\n",
    "http://www.ipol.im/pub/art/2012/gjmr-lsd/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from scipy.special import gammaln\n",
    "from scipy.misc import logsumexp\n",
    "\n",
    "def nfa(im_numel, k, n, tau):\n",
    "    p = tau / np.pi\n",
    "#\n",
    "\n",
    "def select_lines_nfa(lines, centers, alphas, sizes, tau):\n",
    "#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Resultats\n",
    "Maintenant que le critère est programmé, nous vous proposons de reprendre ici toutes les étapes de l'algorithmes et ainsi observer le résultats pour différentes images ou jeux de paramètres :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Bonus\n",
    "Maintenant, nous vous proposons de définir un module de détection LSD. \n",
    "Pour cela, vous pouvez :\n",
    "- Intégrer les différentes fonctions précédentes dans un même module.\n",
    "- Ajouter les fonctions unitaires et vérifier que les tests passent avec `PyTest`.\n",
    "- Faire une analyse de ces performances du LSD.\n",
    "- Optimiser les performances du module en utilisant Cython pour les parties critiques."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}