K-means clustering in OpenCV

Goals

  • Learn to use the cv.kmeans() function in OpenCV for data clustering

Understanding parameters

Input parameters

  1. samples : Should be of np.float32 data type, each feature should be placed in one column.
  2. nclusters(K): The final number of clusters required
  3. criteria : This is the iteration termination criterion. When this criterion is met, the algorithm iteration stops. Actually, it should be a tuple of 3 parameters. They are ( type, max_iter, epsilon ):
    The type of termination condition.
    a. It has 3 flags as follows:
    cv.TERM_CRITERIA_EPS – Stops algorithm iterations if the specified accuracy epsilon is reached.
    cv.TERM_CRITERIA_MAX_ITER – Stops algorithm iteration after reaching the specified number of iterations (max_iter).
    cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER – Stop iteration when any of the above conditions are met.
    b. max_iter – An integer specifying the maximum number of iterations.
    c. epsilon – required accuracy
  4. attempts: is used to specify the number of times the algorithm is executed using different initial tags. The algorithm returns the label that yields the best compactness. This compactness will be returned as output.
  5. Flags (flags): This flag is used to specify the value method of the initial center. Two flags are commonly used: cv.KMEANS_PP_CENTERS and cv.KMEANS_RANDOM_CENTERS.

Output parameters

  1. Compactness (compactness): This is the sum of the squared distances of each point from the corresponding center.
  2. labels: This is an array of labels (same as the “code” from the previous article) where each element is labeled “0”, “1”…
  3. centers : This is an array of cluster centers.
    Now, we will look at three examples to see how to apply the K-Means algorithm.

1. Data with only one feature

Suppose you have a set of data with only one feature, i.e. one-dimensional data. For example, we could take the T-shirt problem and use only people’s heights to determine T-shirt size.

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
x = np.random.randint(25,100,25)
y = np.random.randint(175,255,25)
z = np.hstack((x,y))
z = z.reshape((50,1))
z = np.float32(z)
plt.hist(z,256,[0,256]),plt.show()

So we have an array “z” of size 50 with values ranging from 0 to 255. I reshape “z” into a column vector. It will be more useful when multiple features are present. Then, I created data of type np.float32.

We get the following image


Now we apply the KMeans function. Before that, we need to specify the criteria. My criteria is to stop the algorithm and return the answer every time it iterates 10 times, or reaches accuracy ε = 1.0.

# Definition criteria = ( type, max_iter = 10 , epsilon = 1.0 )
criteria = (cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER, 10, 1.0)
# Set flag (just to avoid code breaks)
flags = cv.KMEANS_RANDOM_CENTERS
# Apply KMeans
compactness,labels,centers = cv.kmeans(z,2,None,criteria,10,flags)

This gives you compactness, labels, and center points. In this case, I got center points of 60 and 207 respectively. The size of the labels is the same as the size of the test data, and each data will be labeled “0”, “1”, “2”, etc. according to its center point. Now, we divide the data into different clusters based on labels.

A = z[labels==0]
B = z[labels==1]

Now we draw A in red, B in blue, and their center points in yellow.

# Now draw "A" in red, "B" in blue, and "center" in yellow.
plt.hist(A,256,[0,256],color = 'r')
plt.hist(B,256,[0,256],color = 'b')
plt.hist(centers,32,[0,256],color = 'y')
plt.show()

Here is the output we get:

2. Data with multiple characteristics

In the previous example, we only used height to solve the T-shirt problem. Here we will use both height and weight, two features.

Remember, in the previous example, we converted the data into a single-column vector. Each feature is arranged in a column, and each row corresponds to an input test sample.

For example, in this case, we set the test data of size 50×2, which is the height and weight of 50 people. The first column corresponds to the heights of all 50 people, and the second column corresponds to their weights. The first row contains two elements, the first is the height of the first person and the second is his weight. Likewise, the remaining rows correspond to other people’s heights and weights. Check out the image below:

Now I go directly to the code:

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
X = np.random.randint(25,50,(25,2))
Y = np.random.randint(60,85,(25,2))
Z = np.vstack((X,Y))
# Convert to np.float32
Z = np.float32(Z)
# Define criteria and apply kmeans()
criteria = (cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER, 10, 1.0)
ret,label,center=cv.kmeans(Z,2,None,criteria,10,cv.KMEANS_RANDOM_CENTERS)
# Now separate the data, note flatten()
A = Z[label.ravel()==0]
B = Z[label.ravel()==1]
# Plot data
plt.scatter(A[:,0],A[:,1])
plt.scatter(B[:,0],B[:,1],c = 'r')
plt.scatter(center[:,0],center[:,1],s = 80,c = 'y', marker = 's')
plt.xlabel('Height'),plt.ylabel('Weight')
plt.show()

Here is the output we get:

3. Color quantization

Color quantization is the process of reducing the number of colors in an image. One reason for doing this is to reduce memory. Sometimes, some devices may be restricted and can only produce a limited number of colors. In this case, color quantization is also performed. Here, we use k-means clustering for color quantification.

There’s nothing new to explain here. There are 3 features like R, G, B. Therefore, we need to reshape the image into an Mx3 sized array (M is the number of pixels in the image). After clustering, we apply center point values (also R, G, B) to all pixels so that the resulting image will have the specified number of colors. We also need to reshape it into the shape of the original image. code show as below:

import numpy as np
import cv2 as cv
img = cv.imread('home.jpg')
Z = img.reshape((-1,3))
# Convert to np.float32
Z = np.float32(Z)
# Define criteria, number of clusters (K) and apply kmeans()
criteria = (cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER, 10, 1.0)
K = 8
ret,label,center=cv.kmeans(Z,K,None,criteria,10,cv.KMEANS_RANDOM_CENTERS)
# Now convert back to uint8 and generate the original image
center = np.uint8(center)
res = center[label.flatten()]
res2 = res.reshape((img.shape))
cv.imshow('res2',res2)
cv.waitKey(0)
cv.destroyAllWindows()

Please look at the results for K=8 below: