{
 "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",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "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"
   ]
  },
  {
   "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",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "n = 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "img = np.random.randint(size=(n, n), \n",
    "                        low=0, high=3)"
   ]
  },
  {
   "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",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g = nx.grid_2d_graph(n, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Let's create two functions to display the image and the corresponding graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def show_image(img, **kwargs):\n",
    "    plt.imshow(img, origin='lower',interpolation='none',\n",
    "               **kwargs);\n",
    "    plt.axis('off');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "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);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "cmap = plt.cm.Blues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. Here is the original image superimposed with the underlying graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.figure(figsize=(5,5));\n",
    "show_image(img, cmap=cmap, vmin=-1);\n",
    "show_graph(g, cmap=cmap, vmin=-1);"
   ]
  },
  {
   "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",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g2 = g.subgraph(zip(*np.nonzero(img==2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.figure(figsize=(5,5));\n",
    "show_image(img, cmap=cmap, vmin=-1);\n",
    "show_graph(g2, cmap=cmap, vmin=-1);"
   ]
  },
  {
   "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",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "components = [np.array(comp)\n",
    "              for comp in nx.connected_components(g2)\n",
    "              if len(comp)>=3]\n",
    "len(components)"
   ]
  },
  {
   "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",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 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')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.figure(figsize=(5,5));\n",
    "show_image(img_bis, cmap=cmap2);"
   ]
  },
  {
   "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": {
  "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.4.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}