{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "%matplotlib inline"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Color Quantization using K-Means\n\n\nPerforms a pixel-wise Vector Quantization (VQ) of an image of the summer palace\n(China), reducing the number of colors required to show the image from 96,615\nunique colors to 64, while preserving the overall appearance quality.\n\nIn this example, pixels are represented in a 3D-space and K-means is used to\nfind 64 color clusters. In the image processing literature, the codebook\nobtained from K-means (the cluster centers) is called the color palette. Using\na single byte, up to 256 colors can be addressed, whereas an RGB encoding\nrequires 3 bytes per pixel. The GIF file format, for example, uses such a\npalette.\n\nFor comparison, a quantized image using a random codebook (colors picked up\nrandomly) is also shown.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "# Authors: Robert Layton <robertlayton@gmail.com>\n#          Olivier Grisel <olivier.grisel@ensta.org>\n#          Mathieu Blondel <mathieu@mblondel.org>\n#\n# License: BSD 3 clause\n\nprint(__doc__)\nimport numpy as np\nimport matplotlib.pyplot as plt\nfrom sklearn.cluster import KMeans\nfrom sklearn.metrics import pairwise_distances_argmin\nfrom sklearn.datasets import load_sample_image\nfrom sklearn.utils import shuffle\nfrom time import time\n\nn_colors = 64\n\n# Load the Summer Palace photo\nchina = load_sample_image(\"china.jpg\")\n\n# Convert to floats instead of the default 8 bits integer coding. Dividing by\n# 255 is important so that plt.imshow behaves works well on float data (need to\n# be in the range [0-1])\nchina = np.array(china, dtype=np.float64) / 255\n\n# Load Image and transform to a 2D numpy array.\nw, h, d = original_shape = tuple(china.shape)\nassert d == 3\nimage_array = np.reshape(china, (w * h, d))\n\nprint(\"Fitting model on a small sub-sample of the data\")\nt0 = time()\nimage_array_sample = shuffle(image_array, random_state=0)[:1000]\nkmeans = KMeans(n_clusters=n_colors, random_state=0).fit(image_array_sample)\nprint(\"done in %0.3fs.\" % (time() - t0))\n\n# Get labels for all points\nprint(\"Predicting color indices on the full image (k-means)\")\nt0 = time()\nlabels = kmeans.predict(image_array)\nprint(\"done in %0.3fs.\" % (time() - t0))\n\n\ncodebook_random = shuffle(image_array, random_state=0)[:n_colors]\nprint(\"Predicting color indices on the full image (random)\")\nt0 = time()\nlabels_random = pairwise_distances_argmin(codebook_random,\n                                          image_array,\n                                          axis=0)\nprint(\"done in %0.3fs.\" % (time() - t0))\n\n\ndef recreate_image(codebook, labels, w, h):\n    \"\"\"Recreate the (compressed) image from the code book & labels\"\"\"\n    d = codebook.shape[1]\n    image = np.zeros((w, h, d))\n    label_idx = 0\n    for i in range(w):\n        for j in range(h):\n            image[i][j] = codebook[labels[label_idx]]\n            label_idx += 1\n    return image\n\n# Display all results, alongside original image\nplt.figure(1)\nplt.clf()\nplt.axis('off')\nplt.title('Original image (96,615 colors)')\nplt.imshow(china)\n\nplt.figure(2)\nplt.clf()\nplt.axis('off')\nplt.title('Quantized image (64 colors, K-Means)')\nplt.imshow(recreate_image(kmeans.cluster_centers_, labels, w, h))\n\nplt.figure(3)\nplt.clf()\nplt.axis('off')\nplt.title('Quantized image (64 colors, Random)')\nplt.imshow(recreate_image(codebook_random, labels_random, w, h))\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.6.7"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}