# Part 5: Studying Digital Image Processing with OpenCV-Python

Here we apply Machine learning to Digital Image Processing
1. K-Nearest Neighbor (kNN)
1.1 Concept
kNN is a classification algorithm of supervised learning. The idea is to search for closest match of the test data in feature space.
A feature space is a space where all data are projected. Ex: in 2D coordinate space. each data has two features according to x and y coordinates. N features need N-dimensional space.
Figure: knn example from OpenCV
There are 2 classes: Blue Squares and Red Triangles. Now there is new Green circle. How it should be classify to one of these Blue/Red classes.
One method is to check which is its nearest neighbour. From the image, it is the Red Triangle. So it should be added into Red Triangle class. This method is called simply Nearest Neighbour. But if there are lot of Blue Squares near to it. So Blue Squares have more strength in that locality than Red Triangle. So just checking nearest one is not sufficient. We have to check some k nearest classes. Consider 3 cases:
+ k=3, there are two Red and one Blue. So it should be added to Red class.
+ k=7, there are 2 Red and 5 Blue. Now it should be added to Blue class.
+ k = 4, there are 2 Red and 2 Blue. It is confused. So we should take k as an odd number.
In case k=4, it is confused. In order to solve it, we can consider the 2 Red are more closer to Green than the 2 Blue. It means we give weights to each class depending on their distance to the Green. So those are near to Green has higher weights and vice versa. So which class gets highest total weights, Green will be added to that class.
1.2 kNN in OpenCV
Let 's apply kNN for the image above:
Figure: input image for kNN
We just aplly some known techniques so here are steps to do:
- Separate Red, Blue and Green objects into 3 classes.
- Assign co-ordinate for each object in each class using its contour and centroid.
- Apply kNN for training data and test it with the Green object.
Here label "0" is stand for Red object and label "1" stand for Blue object. And we have to test label of Green object is "0" or "1".
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 import cv2 as cv import matplotlib.pyplot as plt import numpy as np trainData = [] responses = [] #load the image img = cv.imread('images/knn_theory.png') gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY) hsv = cv.cvtColor(img, cv.COLOR_BGR2HSV) # define threshold range of red color in HSV lower_red = np.array([0, 100, 100]) upper_red = np.array([10,255,255]) lower_green = np.array([50,100,100]) upper_green = np.array([70,255,255]) lower_blue = np.array([110,100,100]) upper_blue = np.array([130,255,255]) #masks mask_red = cv.inRange(hsv, lower_red, upper_red) mask_green = cv.inRange(hsv, lower_green, upper_green) mask_blue = cv.inRange(hsv, lower_blue, upper_blue) #get Red mask = mask_red res = cv.bitwise_and(gray,gray, mask= mask) ret,thresh = cv.threshold(res,0,255,cv.THRESH_BINARY+cv.THRESH_OTSU) _, contours, hierarchy = cv.findContours(thresh,cv.RETR_TREE,cv.CHAIN_APPROX_NONE) #for each Red object calculate centroid as coordinate for cnt in contours: M = cv.moments(cnt) cx = float(M['m10']/M['m00']) cy = float(M['m01']/M['m00']) trainData.append([cx, cy]) #Red object with label 0 responses.append(0) #get Blue mask = mask_blue res = cv.bitwise_and(gray,gray, mask= mask) ret,thresh = cv.threshold(res,0,255,cv.THRESH_BINARY+cv.THRESH_OTSU) _, contours, hierarchy = cv.findContours(thresh,cv.RETR_TREE,cv.CHAIN_APPROX_NONE) #for each Blue object calculate centroid as coordinate for cnt in contours: M = cv.moments(cnt) cx = float(M['m10']/M['m00']) cy = float(M['m01']/M['m00']) trainData.append([cx, cy]) #Blue object with label 1 responses.append(1) #convert data to numpy for calculation trainData = np.array(trainData, dtype=np.float32) responses = np.array(responses, dtype=np.float32) #plot it red = trainData[responses.ravel()==0] plt.scatter(red[:,0],red[:,1],80,'r','^') blue = trainData[responses.ravel()==1] plt.scatter(blue[:,0],blue[:,1],80,'b','s') #get Green mask = mask_green res = cv.bitwise_and(gray,gray, mask= mask) ret,thresh = cv.threshold(res,0,255,cv.THRESH_BINARY+cv.THRESH_OTSU) _, contours, hierarchy = cv.findContours(thresh,cv.RETR_TREE,cv.CHAIN_APPROX_NONE) M = cv.moments(contours) new_comerx = float(M['m10']/M['m00']) new_comery = float(M['m01']/M['m00']) plt.scatter(new_comerx,new_comery,80,'g','o') newcomer = np.array([[new_comerx, new_comery]]).astype(np.float32) #Apply kNN knn = cv.ml.KNearest_create() knn.train(trainData, cv.ml.ROW_SAMPLE, responses) ret, results, neighbours ,dist = knn.findNearest(newcomer, 3) print( "result: {}\n".format(results) ) print( "neighbours: {}\n".format(neighbours) ) print( "distance: {}\n".format(dist) ) plt.show() 
Figure: for k=3, Green object belongs to to Red
2. Support Vector Machine (SVM)
2.1 Concept
The concept of SVM can be refered here.
2.2 SVM in OpenCV
Let 's apply SVM for image below:
Figure: input image for SVM
We do similar steps as for kNN.
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 import cv2 as cv import matplotlib.pyplot as plt import numpy as np trainData = [] responses = [] #load the image img = cv.imread('images/svm.png') gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY) hsv = cv.cvtColor(img, cv.COLOR_BGR2HSV) # define threshold range of red color in HSV lower_red = np.array([0, 100, 100]) upper_red = np.array([10,255,255]) lower_green = np.array([50,100,100]) upper_green = np.array([70,255,255]) lower_blue = np.array([110,100,100]) upper_blue = np.array([130,255,255]) #masks mask_red = cv.inRange(hsv, lower_red, upper_red) mask_green = cv.inRange(hsv, lower_green, upper_green) mask_blue = cv.inRange(hsv, lower_blue, upper_blue) #get Red mask = mask_red res = cv.bitwise_and(gray,gray, mask= mask) ret,thresh = cv.threshold(res,0,255,cv.THRESH_BINARY+cv.THRESH_OTSU) _, contours, hierarchy = cv.findContours(thresh,cv.RETR_TREE,cv.CHAIN_APPROX_NONE) #for each Red object calculate centroid as coordinate for cnt in contours: M = cv.moments(cnt) cx = float(M['m10']/M['m00']) cy = float(M['m01']/M['m00']) trainData.append([cx, cy]) #Red object with label 0 responses.append(0) #get Blue mask = mask_blue res = cv.bitwise_and(gray,gray, mask= mask) ret,thresh = cv.threshold(res,0,255,cv.THRESH_BINARY+cv.THRESH_OTSU) _, contours, hierarchy = cv.findContours(thresh,cv.RETR_TREE,cv.CHAIN_APPROX_NONE) #for each Blue object calculate centroid as coordinate for cnt in contours: M = cv.moments(cnt) cx = float(M['m10']/M['m00']) cy = float(M['m01']/M['m00']) trainData.append([cx, cy]) #Blue object with label 1 responses.append(1) #convert data to numpy for calculation trainData = np.array(trainData, dtype=np.float32) responses = np.array(responses, dtype=np.int) #plot it red = trainData[responses.ravel()==0] plt.scatter(red[:,0],red[:,1],80,'r','^') blue = trainData[responses.ravel()==1] plt.scatter(blue[:,0],blue[:,1],80,'b','s') #get Green mask = mask_green res = cv.bitwise_and(gray,gray, mask= mask) ret,thresh = cv.threshold(res,0,255,cv.THRESH_BINARY+cv.THRESH_OTSU) _, contours, hierarchy = cv.findContours(thresh,cv.RETR_TREE,cv.CHAIN_APPROX_NONE) M = cv.moments(contours) new_comerx = float(M['m10']/M['m00']) new_comery = float(M['m01']/M['m00']) plt.scatter(new_comerx,new_comery,80,'g','o') newcomer = np.array([[new_comerx, new_comery]]).astype(np.float32) #Apply kNN svm = cv.ml.SVM_create() svm.setKernel(cv.ml.SVM_LINEAR) svm.setType(cv.ml.SVM_C_SVC) svm.setC(2.67) svm.setGamma(5.383) svm.train(trainData, cv.ml.ROW_SAMPLE, responses) #predict result = svm.predict(newcomer) print( "result: {}".format(result)) #support vectors print(svm.getUncompressedSupportVectors()) plt.show() 
Figure: Green object belongs to Blue
3. K-Means Clustering
3.1 Concept
Let 's see an example. There is a company that is going to release a new T-shirt to market. So they manufacture it in different sizes. The company make a graph of data of people's height and weight, as below:
Figure: chart of weight-height-T-shirt size
Instead of manufacturing all the sizes of T-shirts, using k-means clustering, they divide the sizes to 3 groups Small, Medium and Large that can fit into all the people. The algorithm gives best 3 group sizes. And if it doesn't fit all, company can divide to more groups, as below:
Figure: chart of weight-height-T-shirt groups
3.2 K-Means Clustering Algorithm
Consider data below:
Figure: dataset for K-Means Clustering
The algorithm do steps:
Step 1 - Algorithm randomly chooses two centroids (it can take 2 data as the centroids), C1 and C2
Step 2 - It calculates the distance from each point to both centroids. If a test data is more closer to C1, then that data is labelled with '0'. If it is closer to C2, then labelled as '1' (If more centroids are there, labelled as '2','3', ...).
Figure: '0' labelled with red, and '1' labelled with blue
Step 3 - Next calculate the new centroids (average) of all blue points and red points separately. C1 and C2 are shifted to new centroids.
Figure: new centroids
Repeat Step 2 and Step 3 until both centroids are converged to fixed points or maximum number of iterations is reached, or a specific accuracy is reached.
The objective is to minimize the function that represent sum of distances between C1<->Red_Points and C2<->Blue_Points.
Figure: optimal centroids
3.3 K-Means Clustering in OpenCV
Inputs:
+ samples : each feature should be put in a single column and its data type is np.float32
+ nclusters(K) : Number of clusters required.
+ criteria : termination condition. It is a tuple of 3 parameters ( type, max_iter, epsilon ):
++ type of termination condition. It has 3 flags:
+++ cv.TERM_CRITERIA_EPS - stop the iteration if required accuracy-epsilon is reached.
+++ cv.TERM_CRITERIA_MAX_ITER - stop the iteration if maximum number of iterations is reached.
+++ cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER - combination of 2 conditions.
++ max_iter - An integer specifying maximum number of iterations.
++ epsilon - Required accuracy
+ attempts : Flag to specify the number of times the algorithm is executed using different initial labellings.
+ flags : specify how initial centers are taken. Normally two flags are used for this : cv.KMEANS_PP_CENTERS and cv.KMEANS_RANDOM_CENTERS.
Outputs:
+ compactness : It is the sum of squared distance from each point to their corresponding centers.
+ labels : This is an array of labels
+ centers : This is an array of centroids.
Apply K-means Clustering for T-shirt chart image above:
Figure: input for K-Means clustering
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import cv2 as cv import matplotlib.pyplot as plt import numpy as np trainData = [] #load the image img = cv.imread('images/kclus.png') gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY) ret,thresh = cv.threshold(gray,0,255,cv.THRESH_BINARY+cv.THRESH_OTSU) _, contours, hierarchy = cv.findContours(thresh,cv.RETR_TREE,cv.CHAIN_APPROX_NONE) #for each object calculate centroid as coordinate for cnt in contours: M = cv.moments(cnt) cx = float(M['m10']/M['m00']) cy = float(M['m01']/M['m00']) trainData.append([cx, cy]) #convert data to numpy for calculation trainData = np.array(trainData, dtype=np.float32) #plot it plt.scatter(trainData[:,0],trainData[:,1],80,'b','o'),plt.xlabel('Height'),plt.ylabel('Weight'),plt.show() # define criteria and apply kmeans() criteria = (cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER, 10, 1.0) #define 3 clusters ret,label,center=cv.kmeans(trainData,3,None,criteria,10,cv.KMEANS_RANDOM_CENTERS) # Now separate the data, Note the flatten() A = trainData[label.ravel()==0] B = trainData[label.ravel()==1] C = trainData[label.ravel()==2] # Plot the result for each cluster plt.scatter(A[:,0],A[:,1],c = 'y') plt.scatter(B[:,0],B[:,1],c = 'r') plt.scatter(C[:,0],C[:,1],c = 'b') plt.scatter(center[:,0],center[:,1],s = 80,c = 'y', marker = 's') plt.show() 
Figure: result of clustering into 3 clusters
3.4 Color Quantization
Color Quantization reduces number of colors in an image. So it reduces the memory. K-means clustering is used for color quantization.
There are 3 features (R,G,B), we do:
+ Reshape the image to an array of Mx3 size (M is number of pixels in image).
+ Apply K-means clustering.
+ Apply centroid values (it is also R,G,B) to all pixels. So result image will have specified number of colors.
+ Reshape it back to the shape of original image.
Apply for the image below in case K=2:

Figure: input image for color quantization
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import numpy as np import cv2 as cv img = cv.imread('images/rose.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 = 2 ret,label,center=cv.kmeans(Z,K,None,criteria,10,cv.KMEANS_RANDOM_CENTERS) # Now convert back into uint8, and make original image center = np.uint8(center) #number of colors reduce to number of centroid colors res = center[label.flatten()] #reconstruct image res2 = res.reshape((img.shape)) cv.imshow('res2',res2) cv.waitKey(0) cv.destroyAllWindows() 
Figure: output image only has 2 color