{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Spectral clustering for image segmentation\n\nIn this example, an image with connected circles is generated and\nspectral clustering is used to separate the circles.\n\nIn these settings, the `spectral_clustering` approach solves the problem\nknow as 'normalized graph cuts': the image is seen as a graph of\nconnected voxels, and the spectral clustering algorithm amounts to\nchoosing graph cuts defining regions while minimizing the ratio of the\ngradient along the cut, and the volume of the region.\n\nAs the algorithm tries to balance the volume (ie balance the region\nsizes), if we take circles with different sizes, the segmentation fails.\n\nIn addition, as there is no useful information in the intensity of the image,\nor its gradient, we choose to perform the spectral clustering on a graph\nthat is only weakly informed by the gradient. This is close to performing\na Voronoi partition of the graph.\n\nIn addition, we use the mask of the objects to restrict the graph to the\noutline of the objects. In this example, we are interested in\nseparating the objects one from the other, and not from the background.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "# Authors: The scikit-learn developers\n# SPDX-License-Identifier: BSD-3-Clause"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Generate the data\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import numpy as np\n\nl = 100\nx, y = np.indices((l, l))\n\ncenter1 = (28, 24)\ncenter2 = (40, 50)\ncenter3 = (67, 58)\ncenter4 = (24, 70)\n\nradius1, radius2, radius3, radius4 = 16, 14, 15, 14\n\ncircle1 = (x - center1[0]) ** 2 + (y - center1[1]) ** 2 < radius1**2\ncircle2 = (x - center2[0]) ** 2 + (y - center2[1]) ** 2 < radius2**2\ncircle3 = (x - center3[0]) ** 2 + (y - center3[1]) ** 2 < radius3**2\ncircle4 = (x - center4[0]) ** 2 + (y - center4[1]) ** 2 < radius4**2"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Plotting four circles\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "img = circle1 + circle2 + circle3 + circle4\n\n# We use a mask that limits to the foreground: the problem that we are\n# interested in here is not separating the objects from the background,\n# but separating them one from the other.\nmask = img.astype(bool)\n\nimg = img.astype(float)\nimg += 1 + 0.2 * np.random.randn(*img.shape)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Convert the image into a graph with the value of the gradient on the\nedges.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.feature_extraction import image\n\ngraph = image.img_to_graph(img, mask=mask)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Take a decreasing function of the gradient resulting in a segmentation\nthat is close to a Voronoi partition\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "graph.data = np.exp(-graph.data / graph.data.std())"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Here we perform spectral clustering using the arpack solver since amg is\nnumerically unstable on this example. We then plot the results.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import matplotlib.pyplot as plt\n\nfrom sklearn.cluster import spectral_clustering\n\nlabels = spectral_clustering(graph, n_clusters=4, eigen_solver=\"arpack\")\nlabel_im = np.full(mask.shape, -1.0)\nlabel_im[mask] = labels\n\nfig, axs = plt.subplots(nrows=1, ncols=2, figsize=(10, 5))\naxs[0].matshow(img)\naxs[1].matshow(label_im)\n\nplt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Plotting two circles\nHere we repeat the above process but only consider the first two circles\nwe generated. Note that this results in a cleaner separation between the\ncircles as the region sizes are easier to balance in this case.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "img = circle1 + circle2\nmask = img.astype(bool)\nimg = img.astype(float)\n\nimg += 1 + 0.2 * np.random.randn(*img.shape)\n\ngraph = image.img_to_graph(img, mask=mask)\ngraph.data = np.exp(-graph.data / graph.data.std())\n\nlabels = spectral_clustering(graph, n_clusters=2, eigen_solver=\"arpack\")\nlabel_im = np.full(mask.shape, -1.0)\nlabel_im[mask] = labels\n\nfig, axs = plt.subplots(nrows=1, ncols=2, figsize=(10, 5))\naxs[0].matshow(img)\naxs[1].matshow(label_im)\n\nplt.show()"
      ]
    }
  ],
  "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.9.21"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}