Color quantization, Image compression and clustering via k-means

Clustering is a technique which is used to partition data into groups (or clusters). Clusters are defined as groups of data objects similar to other objects in their cluster than they are to other data objects in other clusters. Clustering helps us identify two qualities of data: Meaningfulness & Usefulness

Meaningful clusters expand domain knowledge. For example, in the medical field, researchers applied clustering to gene expression experiments. The clustering results identified groups of patients who respond differently to medical treatments.

Useful clusters, on the other hand, serve as an intermediate step in a data pipeline. For example, businesses use clustering for customer segmentation. The clustering results segment customers into groups with similar purchase histories, which businesses can then use to create targeted advertising campaigns.

The k-means clustering method is an unsupervised ML (machine learning) technique which is used to identify clusters of data (objects) in our targeted dataset. There are a lot of different types of clustering methods available, but k-means is one of the oldest and highly used. The k-means clustering is reasonably straightforward to implement in Python.

At odds with other traditional supervised ML algorithms, k-means attempts to classify data without having first been trained with labeled data. Once the algorithm is run and the groups are identified, any new incoming target data can easily be assigned to its most relevant group.

There are some real-world scenarios where k-means algorithm can be applied. This approach can be applied for Customer profiling, search engines, identifying market segments, image compression etc.

How k-means clustering works?

Step 1: Select random points ‘K’ as cluster centers called centroid.

Step 2: Assign each data point to its closest cluster by calculating the distance from each centroid.

Step 3: Determine the new cluster center by computing the average of the above assigned points.

Step 4: Repeat steps 2 and 3 until the centroid position doesn’t change.

Problem Statement: Compressing Images and color quantization for effective storage management

Internet is flooded with huge amounts of data in the form of images and videos. People present on social media upload millions of pictures every day on sites like Instagram, Facebook and cloud platforms like dropbox, Amazon Photos etc. With this huge amount of data uploaded everyday, image compression techniques become important to reduce storage space. Color quantization is also used for low memory devices.

In this article, I will be utilizing k-means clustering algorithm for image compression. An image is made up of numerous Pixels. In a colored image, each pixel is constituted of 24 bits (or 3 bytes) containing RGB (Red-Blue-Green).

Using k-means clustering, I will try to group similar colors together into ‘k’ clusters of different colors having RGB values. A cluster’s centroid will be representative of the color vector in RGB color space of its respective cluster.

These ‘k’ cluster centroids will be used to replace all the color vectors in their respective clusters. As such, we need to only store the label for each pixel which tells the cluster to which this pixel belongs. Additionally, we keep the record of color vectors of each cluster center.

Import Libraries and Read the Image:

import numpy as np
import imageio
import matplotlib.pyplot as plt
import matplotlib.image as img
from matplotlib.pyplot import imread
from scipy.io import loadmat
from scipy import misc
from skimage import img_as_ubyte

Read & Display the Image Data

global img
import matplotlib.pyplot
# code to read the image for compression
def read_image():
  img = matplotlib.pyplot.imread('bird_small.png')
  return img
# code to view the loaded image
plt.imshow(img) # plotting the image
plt.show()

Input Image

def initialize_means(img, clusters):
# reshaping it or flattening it into a 2d matrix
points = np.reshape(img, (img.shape[0] * img.shape[1],
                    img.shape[2]))
m, n = points.shape
# clusters is the number of colors that we choose.
# means is the array of assumed means or centroids.
means = np.zeros((clusters, n))

# random initialization of means.
for i in range(clusters):
  rand1 = int(np.random.random(1)*10)
  rand2 = int(np.random.random(1)*8)
  means[i, 0] = points[rand1, 0]
  means[i, 1] = points[rand2, 1]
return points, means

Euclidean Distance: The Euclidean distance between two points in Euclidean space is the length of a line segment between the two points.

# Calculating the Euclidean distance
def distance(x1, y1, x2, y2):
dist = np.square(x1 - x2) + np.square(y1 - y2)
dist = np.sqrt(dist)
return dist
def k_means(points, means, clusters):
iterations = 10 # the number of iterations
m, n = points.shape
# setting index value corresponding to cluster to which pixel belong
index = np.zeros(m)
# k-means algorithm
while(iterations > 0):
for j in range(len(points)):
# initialize minimum value to a large value
minv = 1000
temp = None
for k in range(clusters):
x1 = points[j, 0]
y1 = points[j, 1]
x2 = means[k, 0]
y2 = means[k, 1]
if(distance(x1, y1, x2, y2) < minv):
minv = distance(x1, y1, x2, y2)
temp = k
index[j] = k
for k in range(clusters):
sumx = 0
sumy = 0
count = 0
for j in range(len(points)):
if(index[j] == k):
sumx += points[j, 0]
sumy += points[j, 1]
count += 1
if(count == 0):
count = 1
means[k, 0] = float(sumx / count)
means[k, 1] = float(sumy / count)
iterations -= 1
return means, index

Recovering compressed image:

def compress_image(means, index, img):
# recovering compressed image by assigning each pixel to its #corresponding centroid.
centroid = np.array(means)
recovered = centroid[index.astype(int), :]
# getting back the 3d matrix (row, col, rgb(3))
recovered = np.reshape(recovered, (img.shape[0], img.shape[1],                img.shape[2]))
# plotting the compressed image.
plt.imshow(recovered)
plt.show()
# saving the compressed image.
imageio.imwrite('compressed_' + str(clusters) +
                '_colors.png', img_as_ubyte(recovered))

Reshaping compressed image

if __name__ == '__main__':
img = read_image()
clusters = 16
clusters = int(input('Enter the number of colors in the compressed image. default = 16\n'))
points, means = initialize_means(img, clusters)
means, index = k_means(points, means, clusters)
compress_image(means, index, img)

I selected the number of colors to be displayed as ‘4’ and then ‘2’. Below are the output compressed images. This technique is also referred to as Color Quantization. It is the process of reducing number of colors in an image. This helps in reduction of memory usage when devices may have limitation such that they can produce only a limited number of colors. Here we use k-means clustering for color quantization.

Image Color Quantization with 4 colors

Image Color Quantization with 2 colors

As it is clearly evident that with an increase in the number of colors selected, the image becomes clearer and distinct because the algorithm can classify more cluster of colors. It can segment objects in images and also give better results. But when it is applied on large datasets (more number of images), it looks at all the samples in one iteration which leads to a lot of time being taken up.

While this is an interesting application of k-means, there are definitely better way to compress images. But this example shows the power related to unsupervised methods like k-means.

References:

Euclidean Distance: https://en.wikipedia.org/wiki/Euclidean_distance

k-mean: https://en.wikipedia.org/wiki/K-means_clustering

https://www.thepythoncode.com/article/kmeans-for-image-segmentation-opencv-python