{
 "metadata": {
  "name": "",
  "signature": "sha256:cc465fa68bd01c7455b38a604a2038004ec499cd3a32e271dcfa5a2dfa426bdd"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": [],
     "source": [
      "> This is one of the 100 recipes of the [IPython Cookbook](http://ipython-books.github.io/), the definitive guide to high-performance scientific computing and data science in Python.\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# 14.4. Computing connected components in an image"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "1. Let's import the packages."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import itertools\n",
      "import numpy as np\n",
      "import networkx as nx\n",
      "import matplotlib.colors as col\n",
      "import matplotlib.pyplot as plt\n",
      "%matplotlib inline\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "2. We create a $10 \\times 10$ image where each pixel can take one of three possible labels (or colors)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 10"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "img = np.random.randint(size=(n, n), \n",
      "                        low=0, high=3)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "3. Now, we create the underlying 2D grid graph encoding the structure of the image. Each node is a pixel, and a node is connected to its nearest neighbors. NetworkX defines a function `grid_2d_graph` for generating this graph."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "g = nx.grid_2d_graph(n, n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "4. Let's create two functions to display the image and the corresponding graph."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def show_image(img, **kwargs):\n",
      "    plt.imshow(img, origin='lower',interpolation='none',\n",
      "               **kwargs);\n",
      "    plt.axis('off');"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def show_graph(g, **kwargs):\n",
      "    nx.draw(g,\n",
      "            pos={(i, j): (j, i) for (i, j) in g.nodes()},\n",
      "            node_color=[img[i, j] for (i, j) in g.nodes()],\n",
      "            linewidths=1, edge_color='w', with_labels=False,\n",
      "            node_size=30, **kwargs);"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "cmap = plt.cm.Blues"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "5. Here is the original image superimposed with the underlying graph."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "plt.figure(figsize=(5,5));\n",
      "show_image(img, cmap=cmap, vmin=-1);\n",
      "show_graph(g, cmap=cmap, vmin=-1);"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "6. We are now going to find all the contiguous regions of the image in dark blue containing more than three pixels. The first step is to consider the *subgraph* corresponding to all dark blue pixels."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "g2 = g.subgraph(zip(*np.nonzero(img==2)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "plt.figure(figsize=(5,5));\n",
      "show_image(img, cmap=cmap, vmin=-1);\n",
      "show_graph(g2, cmap=cmap, vmin=-1);"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "7. We see that the requested contiguous regions correspond to the *connected components* containing more than three nodes in the subgraph. We can use the `connected_components` function of NetworkX to find those components."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "components = [np.array(comp)\n",
      "              for comp in nx.connected_components(g2)\n",
      "              if len(comp)>=3]\n",
      "len(components)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "8. Finally, let's assign a new color to each of these components, and let's display the new image."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# We copy the image, and assign a new label\n",
      "# to each found component.\n",
      "img_bis = img.copy()\n",
      "for i, comp in enumerate(components):\n",
      "    img_bis[comp[:,0], comp[:,1]] = i + 3"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# We create a new discrete color map extending\n",
      "# the previous map with new colors.\n",
      "colors = [cmap(.5), cmap(.75), cmap(1.), \n",
      "          '#f4f235', '#f4a535', '#f44b35']\n",
      "cmap2 = col.ListedColormap(colors, 'indexed')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "plt.figure(figsize=(5,5));\n",
      "show_image(img_bis, cmap=cmap2);"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> You'll find all the explanations, figures, references, and much more in the book (to be released later this summer).\n",
      "\n",
      "> [IPython Cookbook](http://ipython-books.github.io/), by [Cyrille Rossant](http://cyrille.rossant.net), Packt Publishing, 2014 (500 pages)."
     ]
    }
   ],
   "metadata": {}
  }
 ]
}