SLIC_Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "from skimage import io, color\n",
    "from skimage.transform import resize\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# function which returns an object of class SuperPixel\n",
    "def make_superPixel(h, w,img):\n",
    "    return SuperPixels(h, w,img[h,w][0],img[h,w][1],img[h,w][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# To define the initial cluster centers distanced at S\n",
    "def initial_cluster_center(S,img,img_h,img_w,clusters):\n",
    "    h = S // 2\n",
    "    w = S // 2\n",
    "    while h < img_h:\n",
    "        while w < img_w:\n",
    "            clusters.append(make_superPixel(h, w,img))\n",
    "            w += S\n",
    "        w = S // 2\n",
    "        h += S\n",
    "    return clusters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# function to calculate gradient at each pixel \n",
    "def calc_gradient(h, w,img,img_w,img_h):\n",
    "    if w + 1 >= img_w:\n",
    "        w = img_w - 2\n",
    "    if h + 1 >= img_h:\n",
    "        h = img_h - 2\n",
    "    grad = img[w + 1, h + 1][0] - img[w, h][0] + img[w + 1, h + 1][1] - img[w, h][1] + img[w + 1, h + 1][2] - img[w, h][2]\n",
    "    return grad"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# function which reassign the cluster center to the pixel having the lowest gradient\n",
    "def reassign_cluster_center_acc_to_grad(clusters,img):\n",
    "    for c in clusters:\n",
    "        cluster_gradient = calc_gradient(c.h, c.w,img,img_w,img_h)\n",
    "        for dh in range(-1, 2):\n",
    "            for dw in range(-1, 2):\n",
    "                H = c.h + dh\n",
    "                W = c.w + dw\n",
    "                new_gradient = calc_gradient(H,W, img,img_w,img_h)\n",
    "                if new_gradient < cluster_gradient:\n",
    "                    c.update(H, W,img[H,W][0], img[H,W][1],img[H,W][2])\n",
    "                    c_gradient = new_gradient\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "function to assign pixels to the nearest cluster using the Euclidean distance involving both color and spatial\n",
    "proximity.\n",
    "'''\n",
    "def assign_pixels_to_cluster(clusters,S,img,img_h,img_w,tag,dis):\n",
    "    for c in clusters:\n",
    "        for h in range(c.h - 2 * S, c.h + 2 * S):\n",
    "            if h < 0 or h >= img_h: continue\n",
    "            for w in range(c.w - 2 * S, c.w + 2 * S):\n",
    "                if w < 0 or w >= img_w: continue\n",
    "                l, a, b = img[h,w]\n",
    "                Dc = math.sqrt(math.pow(l - c.l, 2) + math.pow(a - c.a, 2) + math.pow(b - c.b, 2))\n",
    "                Ds = math.sqrt(math.pow(h - c.h, 2) + math.pow(w - c.w, 2))\n",
    "                D = math.sqrt(math.pow(Dc / m, 2) + math.pow(Ds /S, 2))\n",
    "                if D < dis[h,w]:\n",
    "                    if (h, w) not in tag:\n",
    "                        tag[(h, w)] = c\n",
    "                        c.pixels.append((h, w))\n",
    "                    else:\n",
    "                        tag[(h, w)].pixels.remove((h, w))\n",
    "                        tag[(h, w)] = c\n",
    "                        c.pixels.append((h, w))\n",
    "                    dis[h, w] = D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# function to replace the cluster center with the mean of the pixels contained in the cluster\n",
    "def update_cluster_mean(clusters):\n",
    "    for c in clusters:\n",
    "        sum_h = sum_w = number = 0\n",
    "        #print(\"c.pixels\",c.pixels)\n",
    "        for p in c.pixels:\n",
    "            sum_h += p[0]\n",
    "            sum_w += p[1]\n",
    "            number += 1\n",
    "            H = sum_h // number\n",
    "            W = sum_w // number\n",
    "            c.update(H, W,img[H, W][0], img[H, W][1], img[H, W][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# replace the color of each pixel in a cluster by the color of the cluster's center\n",
    "def avg_color_cluster(img,name,clusters):\n",
    "    image = np.copy(img)\n",
    "    for c in clusters:\n",
    "        for p in c.pixels:\n",
    "            image[p[0],p[1]][0] = c.l\n",
    "            image[p[0],p[1]][1] = c.a\n",
    "            image[p[0],p[1]][2] = c.b\n",
    "        # To change the color of cluster center to Black\n",
    "        image[c.h, c.w][0] = 0\n",
    "        image[c.h, c.w][1] = 0\n",
    "        image[c.h, c.w][2] = 0\n",
    "    lab2rgb(name, image)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# function for the Simple Linear Iterative Clustering\n",
    "def slic(S,img,img_h,img_w,clusters,tag,dis):\n",
    "    clusters = initial_cluster_center(S,img,img_h,img_w,clusters)\n",
    "    reassign_cluster_center_acc_to_grad(clusters,img)\n",
    "    for i in range(10): # usually the algortihm converges within 10 iterations\n",
    "        assign_pixels_to_cluster(clusters,S,img,img_h,img_w,tag,dis)\n",
    "        update_cluster_mean(clusters)\n",
    "        if i == 9 : # to print the output after 10 iterations\n",
    "            name = 'out_m{m}_k{k}.png'.format(loop=i, m=m, k=k)\n",
    "            avg_color_cluster(img,name, clusters)\n",
    "    return clusters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# function to convert LAB images back to RGB and save it\n",
    "def lab2rgb(path, lab_arr):\n",
    "    rgb_arr = color.lab2rgb(lab_arr)\n",
    "    io.imsave(path, rgb_arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A class to initialize the super pixels, of the form - [h,y,l,a,b].\n",
    "class SuperPixels(object):\n",
    "\n",
    "    def __init__(self, h, w, l=0, a=0, b=0):\n",
    "        self.update(h, w, l, a, b)\n",
    "        self.pixels = []\n",
    "\n",
    "    def update(self, h, w, l, a, b):\n",
    "        self.h = h\n",
    "        self.w = w\n",
    "        self.l = l\n",
    "        self.a = a\n",
    "        self.b = b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(321, 481, 3)\n",
      "(400, 400, 3)\n"
     ]
    }
   ],
   "source": [
    "# read the input RGB image\n",
    "rgb = io.imread(\"5.jpg\",plugin='matplotlib')\n",
    "print(rgb.shape)\n",
    "\n",
    "# input images are resized to (400 x 400) for processing\n",
    "img = resize(rgb, (400,400),anti_aliasing=True)\n",
    "print(img.shape)\n",
    "\n",
    "# convert RGB to LAB\n",
    "img = color.rgb2lab(img)\n",
    "\n",
    "k = 100   # Number of Super pixels\n",
    "m = 20    # Constant for normalizing the color proximity, range of m = [1,40]\n",
    "\n",
    "img_h = img.shape[0] # Image Height\n",
    "img_w = img.shape[1] # Image Width\n",
    "\n",
    "N = img_h * img_w  # Total number of pixels in the image\n",
    "S = int(math.sqrt(N /k)) # average size of each superpixel\n",
    "\n",
    "clusters = []\n",
    "tag = {}\n",
    "# initialize the distance between pixels and cluster center as infinity\n",
    "dis = np.full((img_h, img_w), np.inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Lossy conversion from float64 to uint8. Range [0, 1]. Convert image to uint8 prior to saving to suppress this warning.\n"
     ]
    }
   ],
   "source": [
    "cluster = slic(S,img,img_h,img_w,clusters,tag,dis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "H 17 : W 19, l 26.624612309335646, a -7.555476278732015, b -18.36127581443251\n",
      "H 17 : W 60, l 29.742577647829464, a -5.7333135352195255, b -20.94942563172557\n",
      "H 20 : W 100, l 30.299035663980256, a -5.060061487556611, b -22.04339806733544\n",
      "H 21 : W 141, l 28.278086337704337, a -5.119762298112784, b -22.494872912684517\n",
      "H 20 : W 180, l 26.531990295621654, a -4.659974101382996, b -22.93653719366302\n",
      "H 19 : W 219, l 25.21553562700327, a -6.375656347522963, b -19.534097487257153\n",
      "H 20 : W 258, l 22.264862753686373, a -4.585857590572756, b -20.020351158220663\n",
      "H 19 : W 299, l 19.261394434492686, a -2.310421557983, b -19.794964158440777\n",
      "H 19 : W 339, l 15.720734012079397, a 0.035569428150583615, b -18.90257335662071\n",
      "H 18 : W 379, l 13.356037025539312, a 1.2330054913388122, b -17.87692557147318\n",
      "H 49 : W 18, l 29.811076565106646, a -6.390554280545663, b -19.02547078764233\n",
      "H 50 : W 58, l 31.965636697709186, a -6.035789452814161, b -20.048645782698536\n",
      "H 68 : W 85, l 88.30157383425691, a -25.413269509755253, b 12.79871322322752\n",
      "H 63 : W 130, l 55.13867907704102, a -12.819968195685316, b -19.369436265130858\n",
      "H 60 : W 175, l 30.167240483047834, a -4.58263987778576, b -23.26750298900332\n",
      "H 59 : W 219, l 28.09265955335858, a -6.095625876486599, b -21.741049417813695\n",
      "H 61 : W 260, l 25.268782768042854, a -4.818126504608084, b -21.848912099893035\n",
      "H 59 : W 301, l 22.15831738070502, a -5.423545201521662, b -18.86355535820997\n",
      "H 61 : W 341, l 18.298388778396273, a -2.0401422562652813, b -19.730486734135045\n",
      "H 58 : W 380, l 15.748363788006689, a 0.6218141813871536, b -19.973607781836932\n",
      "H 90 : W 24, l 55.911459866961366, a -15.471638427211332, b -15.26194504401619\n",
      "H 106 : W 58, l 52.58157812361614, a -12.800568143912505, b -17.548169991387997\n",
      "H 103 : W 105, l 56.268237530345345, a -12.782579833358454, b -19.950279653373325\n",
      "H 97 : W 142, l 51.40314096869825, a -10.535536321965132, b -21.643773269632515\n",
      "H 102 : W 174, l 51.785897793582706, a -10.395945880890379, b -21.692401679056506\n",
      "H 99 : W 216, l 30.956506468354164, a -4.2052110456632095, b -24.717852582692768\n",
      "H 100 : W 259, l 27.988901632311062, a -4.6085114416616335, b -23.5333916058461\n",
      "H 99 : W 299, l 25.42509751325897, a -4.865945125191007, b -21.84494900160514\n",
      "H 101 : W 339, l 22.261168637378454, a -4.584747606812045, b -20.02044571575138\n",
      "H 99 : W 379, l 18.759925443215828, a -1.3872506098314419, b -20.66262824498071\n",
      "H 143 : W 15, l 70.35594761639369, a -21.451806149103803, b -7.963172701796606\n",
      "H 141 : W 53, l 60.29557154901538, a -16.649556512966125, b -15.355498523427169\n",
      "H 138 : W 97, l 54.261283010901906, a -11.615306386856982, b -20.88408711680083\n",
      "H 140 : W 137, l 63.30301558659497, a -15.231182621679274, b -18.534554210350084\n",
      "H 145 : W 177, l 56.81393079491224, a -12.089175339448754, b -22.095824180753777\n",
      "H 142 : W 220, l 33.19569472399035, a -2.815397723770902, b -26.28837644073051\n",
      "H 138 : W 259, l 31.28872008472831, a -3.310347168134331, b -26.11605182248796\n",
      "H 139 : W 300, l 28.432255447840483, a -4.791045928694032, b -23.773128461484283\n",
      "H 139 : W 340, l 24.64503668231039, a -5.365463943460547, b -20.68951057062087\n",
      "H 140 : W 380, l 22.18898536143564, a -2.9893473430038506, b -21.6703426013965\n",
      "H 181 : W 18, l 92.93531702668551, a -27.54646463466448, b 13.753169659620745\n",
      "H 176 : W 60, l 96.81846149452046, a -17.499658801012785, b 13.696035902296044\n",
      "H 181 : W 101, l 54.4865280984057, a -11.631193369355032, b -20.876126877016766\n",
      "H 185 : W 144, l 66.15831629557263, a -17.238871623896646, b -15.377423693633908\n",
      "H 174 : W 188, l 75.51294809851771, a -21.998786613143196, b -7.715327225398982\n",
      "H 192 : W 203, l 64.36967734612915, a -17.459794563921214, b -15.034349679182935\n",
      "H 177 : W 253, l 34.071791051821556, a -2.5985954041416184, b -27.313784253509443\n",
      "H 178 : W 298, l 31.926637414827454, a -3.474078139626857, b -26.08551616357422\n",
      "H 177 : W 338, l 27.622933685422794, a -5.591432661379237, b -22.502189653017744\n",
      "H 180 : W 378, l 25.556215446417113, a -5.757338893272207, b -20.706971043652743\n",
      "H 218 : W 20, l 95.46709062933785, a -24.14705542010881, b 14.227377739963298\n",
      "H 226 : W 60, l 60.941552242161904, a -16.755455697244127, b -14.679951469266083\n",
      "H 215 : W 94, l 57.5003009694953, a -13.42305608858213, b -19.436597462347137\n",
      "H 222 : W 134, l 49.16176414366245, a -9.404631130418672, b -21.619172340352733\n",
      "H 220 : W 181, l 48.67380152658592, a -8.431146334702488, b -23.374056892333762\n",
      "H 211 : W 227, l 37.66057792871024, a -3.5636481450163906, b -26.083673034464073\n",
      "H 217 : W 261, l 36.34906065033402, a -2.581843052688826, b -27.238672738019286\n",
      "H 217 : W 299, l 34.76673176838722, a -4.602582770957181, b -25.391625513343175\n",
      "H 218 : W 338, l 30.600434915218827, a -5.31375222945249, b -23.44377254003236\n",
      "H 219 : W 379, l 28.927221054923734, a -6.586482615713763, b -21.735425811054487\n",
      "H 255 : W 21, l 79.11740772636544, a -25.73233325215851, b 6.057168555775205\n",
      "H 267 : W 59, l 75.88966208546728, a -23.762138128686104, b 8.461704249454804\n",
      "H 251 : W 99, l 51.54601068599307, a -11.533847898756221, b -19.956457563434803\n",
      "H 257 : W 143, l 49.31275814254484, a -10.64566448420634, b -20.265128567566993\n",
      "H 264 : W 181, l 47.16867954649942, a -8.266898614153417, b -22.18524233650234\n",
      "H 254 : W 219, l 50.89330147133367, a -10.696504831334385, b -19.860566928476086\n",
      "H 251 : W 268, l 39.15236546218783, a -4.5740825614007665, b -25.586998982673336\n",
      "H 256 : W 300, l 37.07865278113919, a -4.2022379555697595, b -25.041237368430114\n",
      "H 257 : W 339, l 33.879161472919414, a -5.1407604411276004, b -23.700198689787555\n",
      "H 260 : W 379, l 32.611107107564656, a -6.377981153937395, b -22.574096169615654\n",
      "H 294 : W 16, l 54.986433394030755, a -16.8878302894544, b -4.533689945650088\n",
      "H 306 : W 54, l 65.91755752994449, a -16.434429639893, b -4.238263070527615\n",
      "H 292 : W 100, l 73.95308342788174, a -20.062683074998645, b -2.074823666766812\n",
      "H 297 : W 137, l 88.46066615337179, a -25.06344775398689, b 9.719403227847767\n",
      "H 304 : W 178, l 92.57517218301047, a -22.483944357548246, b 9.988290571429781\n",
      "H 289 : W 228, l 48.193531182288396, a -10.074416952764675, b -19.756659015602796\n",
      "H 288 : W 263, l 47.59754438009056, a -9.50331287304451, b -18.77259811360201\n",
      "H 294 : W 299, l 60.06733384540095, a -18.19576100917558, b -8.756182967274695\n",
      "H 294 : W 337, l 37.60809399462254, a -6.0270263856384565, b -21.950531441639942\n",
      "H 307 : W 377, l 22.26769484850687, a -15.812513316447397, b 8.573907481577947\n",
      "H 347 : W 21, l 83.05723724479815, a -24.147628271678766, b 11.09196647298556\n",
      "H 340 : W 59, l 90.86936786779609, a -22.00603379384347, b 12.507079473986238\n",
      "H 335 : W 100, l 88.0885917802095, a -22.072657389106688, b 6.286051302031459\n",
      "H 336 : W 139, l 91.83060866334003, a -23.861395512583762, b 14.956941452503392\n",
      "H 346 : W 179, l 76.32335145633427, a -20.402640964216733, b 1.1771102163232516\n",
      "H 336 : W 221, l 92.68695133429726, a -21.77077068366129, b 9.35655687151531\n",
      "H 345 : W 256, l 71.50799205912314, a -18.471517168129058, b -0.5073047222058813\n",
      "H 339 : W 295, l 92.12552435204779, a -21.354810719226126, b 9.328607112318842\n",
      "H 335 : W 341, l 82.2367559740631, a -20.678387349187922, b 5.835877178354298\n",
      "H 338 : W 380, l 66.04609086620758, a -20.85955464466155, b 1.6855616223878434\n",
      "H 383 : W 18, l 83.24868487592158, a -24.57280622559316, b 11.043679265747407\n",
      "H 383 : W 68, l 83.38954737253786, a -22.057853277402618, b 11.619806907413711\n",
      "H 369 : W 93, l 40.107027313470724, a -14.703162263853791, b -2.5315614903552497\n",
      "H 377 : W 134, l 77.72146984432621, a -20.459588415761786, b 7.0206910651862575\n",
      "H 383 : W 178, l 94.95206457084151, a -20.66204744828315, b 18.318787617949827\n",
      "H 380 : W 219, l 85.12371257862965, a -21.793976447236464, b 9.706261139307305\n",
      "H 379 : W 260, l 92.32937919663767, a -21.548459619962212, b 13.770492411628465\n",
      "H 381 : W 302, l 88.97815986280865, a -21.544030204819485, b 16.794451725927082\n",
      "H 379 : W 335, l 66.441500322234, a -19.461679007795773, b 5.865658542305363\n",
      "H 378 : W 379, l 74.8013430922828, a -20.445364939651768, b 6.20746315697871\n"
     ]
    }
   ],
   "source": [
    "# superpixels\n",
    "for c in cluster:\n",
    "    print(\"H {} : W {}, l {}, a {}, b {}\".format(c.h,c.w,c.l,c.a,c.b))"
   ]
  },
  {
   "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.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}