{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Kompresija slike korišćenjem algoritma k-sredina"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sledeći primer ilustruje korišćenje algoritma k-sredina u kompresiji slika. Ideja je redukovati broj boja koje se koriste za prikaz same slike, a time i memoriju koju ona zahteva. \n",
    "\n",
    "Primer je motivisan primerom sa [zvaničnog sajta biblioteke scikit-learn](https://scikit-learn.org/stable/auto_examples/cluster/plot_color_quantization.html#sphx-glr-auto-examples-cluster-plot-color-quantization-py)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from time import time\n",
    "\n",
    "from sklearn.cluster import KMeans\n",
    "from sklearn.metrics import pairwise_distances_argmin\n",
    "from sklearn.datasets import load_sample_image\n",
    "from sklearn.utils import shuffle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eksperiment ćemo izdvoditi nad slikom `chine.jpg` koju ćemo učitatiti iz `datasets` paketa korišćenjem funkcije `load_sample_image`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "image = load_sample_image(\"china.jpg\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 192876 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.imshow(image)\n",
    "plt.title('Originalna slika: 96 615 boja')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Slika je dimenzija 427x640 piksela i ima 3 kanala boja (RGB)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(427, 640, 3)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "image.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "819840"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "image.nbytes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Za zapis jednog piksela koristi se jedan bajt - njime se može opisati 256 različitih nijansi boja."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dtype('uint8')"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "image.dtype"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Parametar `n_colors` će označavati broj boja koje će biti korišćene u kompresovanoj slici, a ujedno i broj klastera koje će algoritam tražiti. Za zapis jedne ovakve boje biće potrebno  bita."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_colors = 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pre obrade, izvrišićemo normalizaciju piskela slike i transformaciju u 2D vektor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "image = image.astype(np.float64) / 255"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "image_width, image_height, image_depth = image.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "image_2D = np.reshape(image, (image_width*image_height, image_depth))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(273280, 3)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "image_2D.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sada ćemo iskoristiti k-means algoritam za kreiranje klastera. Model ćemo naučiti nad 10000 proizvoljno odabranih piksela slike, a potom ćemo ga iskoristiti za dalje bojenje slike."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "kmeans_start = time()\n",
    "\n",
    "image_2D_sample = shuffle(image_2D, random_state=0)[:10000]\n",
    "\n",
    "kmeans = KMeans(n_clusters=n_colors, random_state=0)\n",
    "kmeans.fit(image_2D_sample)\n",
    "kmeans_end = time()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Algoritma se izvrsavao ukupno :  0.2889277935028076  sekunde\n"
     ]
    }
   ],
   "source": [
    "print('Algoritma se izvrsavao ukupno : ', kmeans_end-kmeans_start, ' sekunde')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "kmeans_prediction_start = time()\n",
    "image_labels = kmeans.predict(image_2D)\n",
    "kmeans_prediction_end = time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Algoritma se izvrsavao ukupno :  0.016986608505249023  sekunde\n"
     ]
    }
   ],
   "source": [
    "print('Algoritma se izvrsavao ukupno : ', kmeans_prediction_end-kmeans_prediction_start, ' sekunde')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(273280,)"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "image_labels.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Centroide izdvojenih klastera ćemo zvati paletom boja (engl. codebook). Funkciju `recreate_image` ćemo koristi za kreiranje slike na osnovu prosleđene palete boja, labela piksela i dimenzija slike.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recreate_image(codebook, labels, image_width, image_height):\n",
    "    \n",
    "    # broj kanala slike\n",
    "    depth = codebook.shape[1]\n",
    "    \n",
    "    # nova slika je inicijalno matrica nula dimenzije image_width x image_height x depth\n",
    "    image = np.zeros((image_width, image_height, depth))\n",
    "    \n",
    "    # za svaku labelu piksela nove slike očitavamo boju koja joj je pridružena prilikom klasterovanja\n",
    "    label_idx = 0\n",
    "    for i in range(image_width):\n",
    "        for j in range(image_height):\n",
    "            image[i][j] = codebook[labels[label_idx]]\n",
    "            label_idx += 1\n",
    "    \n",
    "    # kao rezultat vraćamo kreiranu sliku\n",
    "    return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "kmeans_image = recreate_image(kmeans.cluster_centers_, image_labels, image_width, image_height)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 193556 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 140280 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.imshow(image)\n",
    "plt.title('Originalna slika: 96 615 boja')\n",
    "plt.show()\n",
    "\n",
    "plt.axis('off')\n",
    "plt.title('Modifikovana slika, algoritam k-sredina: 64 boje')\n",
    "plt.imshow(kmeans_image)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6558720"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kmeans_image.nbytes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Možemo da istražimo i kakva slika bi se dobila nasumičnim izborom palete boja sa 64 boje. Svakom pikselu slike bi se u ovom slučaju pridružila boja njemu najbližeg obeležja."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "codebook_random = shuffle(image_2D, random_state=0)[:n_colors]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "labels_random = pairwise_distances_argmin(codebook_random, image_2D, axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 139604 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.axis('off')\n",
    "plt.title('Modifikovana slika, random izbor boja: 64 boje')\n",
    "plt.imshow(recreate_image(codebook_random, labels_random, image_width, image_height))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
