I want to apply the k-means algorithm on an RGB image data-set. I don't know how to proceed. You can mention basic step by step flow to proceed. I do know basics of Image Processing & OpenCV.
-
3It's already on the OpenCV tutorial– rwongMar 30, 2016 at 6:15
-
You mean you want to cluster images based on their similarity? And you are looking how to implement "similarity" metric between images?– EuphoricMar 30, 2016 at 6:22
-
@rwong That is image quantization, not image clustering.– EuphoricMar 30, 2016 at 6:26
-
@Euphoric Yes I want to cluster images based on their similarity. Now this similarity may be based on features. I want to classify images.– yogesh_desaiMar 30, 2016 at 7:01
-
2There are too many ways similarity between images can be calculated. Searching "image similarity" on google should give you basic overview.– EuphoricMar 30, 2016 at 7:06
1 Answer
You can readily apply the k-means algorithm to the RGB image data set. An image data set is in no way special, except that each data vector is three dimensional (R, G and B) and the values are bounded integers in the [0, 255] range.
The standard k-means algorithm just needs to compute the distance between two as well as the mean of several data points.
For more information on the k-means algorithm, see for example here.
Naive RGB color distance: If you have two elements i and j with RGB values (ri, gi, bi) and (rj, gj, bj), respectively, then the distance d between image points i and j equals:
d = sqrt((ri-rj)^2+(gi-gj)^2+(bi-bj)^2)
And the mean of several colors points would then be the mean of the RGB values separately.
For an implementation of this in OpenCV see example for color quantization on the OpenCV tutorial.
More realistic color distance: The RGB color space is not a good model for color distance unfortunately (see excellent comment by John Forkosh). However, the CIE-L*ab colorspace and some associated color distance model seem to be suited better.
Step 1: Conversion of RGB to CIE-L*ab (RGB is device dependent, so it may need to be transformed before to some absolute colorspace RGB values).
Very probably the platform you are using already has an RGB to CIE-L*ab conversion (Matlab, Java, Python or C++ using OpenCV). Otherwise you would have to write your own (Help).
Step 2: Calculate the distance in the k-means algorithm.
Delta E* from there seems simple to calculate:
(l1,a1,b1) are the Lab values of data point 1 and (l2,a2,b2) are the Lab values of data point 2
d = sqrt((l1 - l2)^2 + (a1 - a2)^2 + (b1 - b2)^2)
The mean of several colors in the CIE-Lab space would again be the mean of each Lab component separately.
But you also may want to try others distances and see what works best.
Summary: The k-means algorithm doesn't need to be modified except for the distance and the mean calculation. For a better suited distance, the conversion to another color space (CIE-L*ab) and the computation of a distance in that color space are recommended.
-
2That distance formula probably isn't qualitatively right for colorspaces, because r,g,b just isn't a good model for color "distance". What's typically used is the CIE-L*ab colorspace model, e.g., en.wikipedia.org/wiki/Lab_color_space And then some frequently used distance formulas using that space are at easyrgb.com/index.php?X=DELT And an on-line color distance calculator using these kinds of formulas is at brucelindbloom.com/index.html?ColorDifferenceCalc.html So, if you convert r,g,b-values to corresponding Lab values, distances are very different. Mar 30, 2016 at 8:01
-
@JohnForkosh Thanks for that comment. I added information about it in the answer. Mar 30, 2016 at 8:55