{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# A demo of structured Ward hierarchical clustering on an image of coins\n\nCompute the segmentation of a 2D image with Ward hierarchical\nclustering. The clustering is spatially constrained in order\nfor each segmented region to be in one piece.\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 data\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from skimage.data import coins\n\norig_coins = coins()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Resize it to 20% of the original size to speed up the processing\nApplying a Gaussian filter for smoothing prior to down-scaling\nreduces aliasing artifacts.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import numpy as np\nfrom scipy.ndimage import gaussian_filter\nfrom skimage.transform import rescale\n\nsmoothened_coins = gaussian_filter(orig_coins, sigma=2)\nrescaled_coins = rescale(\n    smoothened_coins,\n    0.2,\n    mode=\"reflect\",\n    anti_aliasing=False,\n)\n\nX = np.reshape(rescaled_coins, (-1, 1))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Define structure of the data\n\nPixels are connected to their neighbors.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.feature_extraction.image import grid_to_graph\n\nconnectivity = grid_to_graph(*rescaled_coins.shape)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Compute clustering\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import time as time\n\nfrom sklearn.cluster import AgglomerativeClustering\n\nprint(\"Compute structured hierarchical clustering...\")\nst = time.time()\nn_clusters = 27  # number of regions\nward = AgglomerativeClustering(\n    n_clusters=n_clusters, linkage=\"ward\", connectivity=connectivity\n)\nward.fit(X)\nlabel = np.reshape(ward.labels_, rescaled_coins.shape)\nprint(f\"Elapsed time: {time.time() - st:.3f}s\")\nprint(f\"Number of pixels: {label.size}\")\nprint(f\"Number of clusters: {np.unique(label).size}\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Plot the results on an image\n\nAgglomerative clustering is able to segment each coin however, we have had to\nuse a ``n_cluster`` larger than the number of coins because the segmentation\nis finding a large in the background.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import matplotlib.pyplot as plt\n\nplt.figure(figsize=(5, 5))\nplt.imshow(rescaled_coins, cmap=plt.cm.gray)\nfor l in range(n_clusters):\n    plt.contour(\n        label == l,\n        colors=[\n            plt.cm.nipy_spectral(l / float(n_clusters)),\n        ],\n    )\nplt.axis(\"off\")\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
}