<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Image compression with K-means
K-means is a clustering algorithm which defines K cluster centroids in the feature space and, by making use of an appropriate distance function, iteratively assigns each example to the closest cluster centroid and each cluster centroid to the mean of points previously assigned to it.
In the following example we will make use of K-means clustering to reduce the number of colors contained in an image stored using 24-bit RGB encoding.
Overview
The RGB color model is an additive color model in which red, green and blue light are added together in various ways to reproduce a broad array of colors. In a 24-bit encoding, each pixel is represented as three 8-bit unsigned integers (ranging from 0 to 255) that specify the red, green and blue intensity values, resulting in a total of 256*256*256=16,777,216 possible colors.
To compress the image, we will reduce this number to 16, assign each color to an index and then each pixel to an index. This process will significantly decrease the amount of space occupied by the image, at the cost of introducing some computational effort.
For a 128x128 image
Step1:  Note that PIL (or Pillow) library is also needed to successfully import the image, so pip install it if you have not it installed.
Now let's take a look at the image by plotting it with matplotlib
Step2:  The image is stored in a 3-dimensional matrix, where the first and second dimension represent the pixel location on the 2-dimensional plan and the third dimension the RGB intensities
Step3:  Preprocessing
We want to flatten the matrix, in order to give it to the clustering algorithm
Step4:  Fitting
Now by fitting the KMeans estimator in scikit-learn we can identify the best clusters for the flattened matrix
Step5:  We can verify that each pixel has been assigned to a cluster
Step6:  And we can visualize each cluster centroid
Step7:  Note that cluster centroids are computed as the mean of the features, so we easily end up on decimal values, which are not admitted in a 24 bit representation (three 8-bit unsigned integers ranging from 0 to 255) of the colors. We decide to round them with a floor operation. Furthermore we have to invert the sign of the clusters to visualize them
Step8:  Reconstructing
Step9:  The data contained in clusters and labels define the compressed image and should be stored in a proper format, in order to effectively realize the data compression
Step10:  At the cost of a deterioriation in the color quality, the space occupied by the image will be significantly lesser. We can compare the original and the compressed image in the following figure
<ASSISTANT_TASK:>
Python Code:
from scipy import misc
pic = misc.imread('media/irobot.png')
Explanation: Image compression with K-means
K-means is a clustering algorithm which defines K cluster centroids in the feature space and, by making use of an appropriate distance function, iteratively assigns each example to the closest cluster centroid and each cluster centroid to the mean of points previously assigned to it.
In the following example we will make use of K-means clustering to reduce the number of colors contained in an image stored using 24-bit RGB encoding.
Overview
The RGB color model is an additive color model in which red, green and blue light are added together in various ways to reproduce a broad array of colors. In a 24-bit encoding, each pixel is represented as three 8-bit unsigned integers (ranging from 0 to 255) that specify the red, green and blue intensity values, resulting in a total of 256*256*256=16,777,216 possible colors.
To compress the image, we will reduce this number to 16, assign each color to an index and then each pixel to an index. This process will significantly decrease the amount of space occupied by the image, at the cost of introducing some computational effort.
For a 128x128 image:
* Uncompressed format: 16,384 px * 24 bits/px = 393,216 bits
* Compressed format: 16,384 px * 4 bits/px + 16 clusters * 24 bits/cluster = 65,536 + 385 bits = 65,920 bits (17%)
Note that we won't implement directly the K-means algorithm, as we are primarily interested in showing its application in a common scenario, but we'll delegate it to the scikit-learn library.
Implementation
Import
First, let's import the image with scipy:
End of explanation
import matplotlib.pyplot as plt
%matplotlib inline
plt.imshow(pic)
Explanation: Note that PIL (or Pillow) library is also needed to successfully import the image, so pip install it if you have not it installed.
Now let's take a look at the image by plotting it with matplotlib:
End of explanation
pic.shape
Explanation: The image is stored in a 3-dimensional matrix, where the first and second dimension represent the pixel location on the 2-dimensional plan and the third dimension the RGB intensities:
End of explanation
w = pic.shape[0]
h = pic.shape[1]
X = pic.reshape((w*h,3))
X.shape
Explanation: Preprocessing
We want to flatten the matrix, in order to give it to the clustering algorithm:
End of explanation
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=16)
kmeans.fit(X)
Explanation: Fitting
Now by fitting the KMeans estimator in scikit-learn we can identify the best clusters for the flattened matrix:
End of explanation
kmeans.labels_
np.unique(kmeans.labels_)
Explanation: We can verify that each pixel has been assigned to a cluster:
End of explanation
kmeans.cluster_centers_
Explanation: And we can visualize each cluster centroid:
End of explanation
import numpy as np
plt.imshow(np.floor(kmeans.cluster_centers_.reshape((1,16,3))) * (-1))
Explanation: Note that cluster centroids are computed as the mean of the features, so we easily end up on decimal values, which are not admitted in a 24 bit representation (three 8-bit unsigned integers ranging from 0 to 255) of the colors. We decide to round them with a floor operation. Furthermore we have to invert the sign of the clusters to visualize them:
End of explanation
labels = kmeans.labels_
clusters = np.floor(kmeans.cluster_centers_) * (-1)
Explanation: Reconstructing
End of explanation
# Assigning RGB to clusters and reshaping
pic_recovered = clusters[labels,:].reshape((w,h,3))
plt.imshow(pic_recovered)
Explanation: The data contained in clusters and labels define the compressed image and should be stored in a proper format, in order to effectively realize the data compression:
* clusters: 16 clusters * 24 bits/cluster
* labels: (width x height) px * 4 bits/px
To reconstruct the image we assign RGB values of the cluster centroids to the pixels and we reshape the matrix in the original form:
End of explanation
fig, axes = plt.subplots(nrows=1, ncols=2,figsize=(10,5))
axes[0].imshow(pic)
axes[1].imshow(pic_recovered)
Explanation: At the cost of a deterioriation in the color quality, the space occupied by the image will be significantly lesser. We can compare the original and the compressed image in the following figure:
End of explanation
<END_TASK>