The implementation of the algorithm k-means (k-average) on the example of working with pixels

Hello! Recently, it was necessary to write code to implement image segmentation using the k-means method. Well, google first thing to help. I found a lot of information, as well as from a mathematical point of view (all sorts of complex mathematical scribbles there, you will understand what the fuck is written there), and some software implementations that exist on the English Internet. Of course, these codes are beautiful - no doubt, but the very essence of the idea is hard to catch. Somehow it’s all complicated there, confusing, and as long as you don’t write the code with your hands, you don’t understand anything. In this article I want to show a simple, not productive, but, I hope, understandable implementation of this wonderful algorithm. Okay, drove!

So what is clustering in terms of our perception? I will give an example, for example, there is a cute image with flowers from your grandmother’s dacha.



The question is: to determine how many areas of this photo are filled with approximately one color. Well, it’s not at all difficult: white petals - once, yellow centers - two (I am not a biologist, as they are called, I don’t know), greenery - three. These areas are called clusters. Cluster - combining data with common characteristics (color, position, etc.). The process of determining and placing each component of any data in such clusters - areas is called clustering.
')
There are many clustering algorithms, but the simplest of them is k-means, which will be discussed further. K-means is a simple and efficient algorithm that is easy to implement using a software method. The data that we will distribute across clusters is pixels. As you know, a color pixel has three components - red, green and blue. The overlay of these components creates a palette of existing colors.



In the computer's memory, each component of a color is characterized by a number from 0 to 255. That is, by combining different values ​​of red, green and blue, we get a color palette on the screen.

On the example of pixels, we implement our algorithm. K-means is an iterative algorithm, that is, it will give the correct result, after a certain number of repetitions of some mathematical calculations.

Algorithm

1. You need to know in advance how many clusters you need to distribute the data. This is a significant disadvantage of this method, but this problem is solved by improved implementations of the algorithm, but this is said to be a completely different story.
2. We need to choose the initial centers of our clusters. How? Yes, at random. What for? To be able to bind each pixel to the center of the cluster. The center is like a King, around which his subjects are gathered - pixels. It is the “distance” from the center to the pixel that determines who will obey each pixel.
3. Calculate the distance from each center to each pixel. This distance is considered as the Euclidean distance between points in space, and in our case - as the distance between the three color components:

   $$$$ display $$ \ sqrt {(R_ {2} -R_ {1}) ^ 2 + (G_ {2} -G_ {1}) ^ 2 + (B_ {2} -B_ {1}) ^ 2} . $$ display $$

   We count the distance from the first pixel to each center and determine the smallest distance between this pixel and the centers. For the center, the distance to which is the smallest, recalculate the coordinates, as the arithmetic average between each component of the pixel - the king and the pixel - the subject. Our center is shifted in space, according to calculations.
4. After recalculating all the centers, we distribute the pixels into clusters, comparing the distance from each pixel to the centers. A pixel is placed in a cluster, to the center of which it is located closer than to the other centers.
5. It all starts over again, as long as the pixels remain in the same clusters. Often this may not happen, since with a large amount of data the centers will move in a small radius, and the pixels on the edges of the clusters will jump to one or another cluster. To do this, determine the maximum number of iterations.

Implementation

I will implement this project in C ++. The first file is “k_means.h”, in it I defined the main data types, constants, and the main class for work is “K_means”.
To characterize each pixel, we will create a structure that consists of three pixel components, for which I chose the double type for more accurate calculations, and also defined some constants for the program to work:

const int KK = 10; //  const int max_iterations = 100; //   typedef struct { double r; double g; double b; } rgb; 

The K_means class itself:

 class K_means { private: std::vector<rgb> pixcel; int q_klaster; int k_pixcel; std::vector<rgb> centr; void identify_centers(); inline double compute(rgb k1, rgb k2) { return sqrt(pow((k1.r - k2.r),2) + pow((k1.g - k2.g), 2) + pow((k1.b - k2.b), 2)); } inline double compute_s(double a, double b) { return (a + b) / 2; }; public: K_means() : q_klaster(0), k_pixcel(0) {}; K_means(int n, rgb *mas, int n_klaster); K_means(int n_klaster, std::istream & os); void clustering(std::ostream & os); void print()const; ~K_means(); friend std::ostream & operator<<(std::ostream & os, const K_means & k); }; 

Let's run through the class components:

vectorpixcel - vector for pixels;
q_klaster - the number of clusters;
k_pixcel - the number of pixels;
vectorcentr - vector for clustering centers, the number of elements in it is determined by q_klaster;
identify_centers () is a method for randomly selecting initial centers among input pixels;
compute () and compute_s () built-in methods for calculating the distance between pixels and recalculating centers, respectively;
three constructors: the first by default, the second for initializing pixels from an array, the third for initializing pixels from a text file (in my implementation, first the file is randomly filled with data, and then pixels are read from this file for the program to work, why not directly into a vector just need in my case);
clustering (std :: ostream & os) - clustering method;
method and operator output overload for publishing results.

Implementation methods:

 void K_means::identify_centers() { srand((unsigned)time(NULL)); rgb temp; rgb *mas = new rgb[q_klaster]; for (int i = 0; i < q_klaster; i++) { temp = pixcel[0 + rand() % k_pixcel]; for (int j = i; j < q_klaster; j++) { if (temp.r != mas[j].r && temp.g != mas[j].g && temp.b != mas[j].b) { mas[j] = temp; } else { i--; break; } } } for (int i = 0; i < q_klaster; i++) { centr.push_back(mas[i]); } delete []mas; } 

This is a method for selecting initial clustering centers and adding them to the centers vector. A check is made on the repetition of centers and their replacement in these cases.

 K_means::K_means(int n, rgb * mas, int n_klaster) { for (int i = 0; i < n; i++) { pixcel.push_back(*(mas + i)); } q_klaster = n_klaster; k_pixcel = n; identify_centers(); } 

Implement a constructor to initialize pixels from an array.

 K_means::K_means(int n_klaster, std::istream & os) : q_klaster(n_klaster) { rgb temp; while (os >> temp.r && os >> temp.g && os >> temp.b) { pixcel.push_back(temp); } k_pixcel = pixcel.size(); identify_centers(); } 

In this constructor, we pass an input object for the ability to enter data from both the file and the console.

 void K_means::clustering(std::ostream & os) { os << "\n\n :" << std::endl; /*             :        ,    -  ,    ,   ,        .*/ std::vector<int> check_1(k_pixcel, -1); std::vector<int> check_2(k_pixcel, -2); int iter = 0; /* .*/ while(true) { os << "\n\n----------------  №" << iter << " ----------------\n\n"; { for (int j = 0; j < k_pixcel; j++) { double *mas = new double[q_klaster]; /*  :          .      ,   .*/ for (int i = 0; i < q_klaster; i++) { *(mas + i) = compute(pixcel[j], centr[i]); os << "   " << j << "   #" << i << ": " << *(mas + i) << std::endl; } /*     m_k      .*/ double min_dist = *mas; int m_k = 0; for (int i = 0; i < q_klaster; i++) { if (min_dist > *(mas + i)) { min_dist = *(mas + i); m_k = i; } } os << "    #" << m_k << std::endl; os << "  #" << m_k << ": "; centr[m_k].r = compute_s(pixcel[j].r, centr[m_k].r); centr[m_k].g = compute_s(pixcel[j].g, centr[m_k].g); centr[m_k].b = compute_s(pixcel[j].b, centr[m_k].b); os << centr[m_k].r << " " << centr[m_k].g << " " << centr[m_k].b << std::endl; delete[] mas; } /*   .*/ int *mass = new int[k_pixcel]; os << "\n  : "<< std::endl; for (int k = 0; k < k_pixcel; k++) { double *mas = new double[q_klaster]; /*    .*/ for (int i = 0; i < q_klaster; i++) { *(mas + i) = compute(pixcel[k], centr[i]); os << "   №" << k << "   #" << i << ": " << *(mas + i) << std::endl; } /*  .*/ double min_dist = *mas; int m_k = 0; for (int i = 0; i < q_klaster; i++) { if (min_dist > *(mas + i)) { min_dist = *(mas + i); m_k = i; } } mass[k] = m_k; os << " №" << k << "     #" << m_k << std::endl; } /*            .*/ os << "\n    : \n"; for (int i = 0; i < k_pixcel; i++) { os << mass[i] << " "; check_1[i] = *(mass + i); } os << std::endl << std::endl; os << " : " << std::endl; int itr = KK + 1; for (int i = 0; i < q_klaster; i++) { os << " #" << i << std::endl; for (int j = 0; j < k_pixcel; j++) { if (mass[j] == i) { os << pixcel[j].r << " " << pixcel[j].g << " " << pixcel[j].b << std::endl; mass[j] = ++itr; } } } delete[] mass; /*    .*/ os << " : \n" ; for (int i = 0; i < q_klaster; i++) { os << centr[i].r << " " << centr[i].g << " " << centr[i].b << " - #" << i << std::endl; } } /*         –  .*/ iter++; if (check_1 == check_2 || iter >= max_iterations) { break; } check_2 = check_1; } os << "\n\n ." << std::endl; } 

The main clustering method.

 std::ostream & operator<<(std::ostream & os, const K_means & k) { os << " : " << std::endl; for (int i = 0; i < k.k_pixcel; i++) { os << k.pixcel[i].r << " " << k.pixcel[i].g << " " << k.pixcel[i].b << " - №" << i << std::endl; } os << std::endl << "   : " << std::endl; for (int i = 0; i < k.q_klaster; i++) { os << k.centr[i].r << " " << k.centr[i].g << " " << k.centr[i].b << " - #" << i << std::endl; } os << "\n : " << k.q_klaster << std::endl; os << " : " << k.k_pixcel << std::endl; return os; } 

The output of the initial data.

Sample output

This example is planned in advance, the pixels are selected specifically for demonstration. The program needs two iterations to group the data into three clusters. Looking at the centers of the last two iterations, you can see that they almost stayed in place.

More interesting cases with random pixel generation. Having generated 50 points that need to be divided into 10 clusters, I got 5 iterations. Having generated 50 points that need to be divided into 3 clusters, I got all 100 maximum allowed iterations. You can see that the more clusters, the easier it is for the program to find the most similar pixels and combine them into smaller groups, and vice versa - if there are few clusters and many points, the algorithm often ends only by exceeding the maximum allowed number of iterations, since some pixels constantly jump from one cluster to another. Nevertheless, the bulk is still defined in their clusters finally.

Well, now let's check the result of clustering. Taking the result of some clusters from the example of 50 points on 10 clusters, I hammered the result of this data into Illustrator and this is what happened:



It can be seen that in each cluster any shades of color prevail, and here you need to understand that the pixels were chosen randomly; an analogue of such an image in real life is some kind of picture that was randomly sprinkled with all colors and it is difficult to isolate areas of similar colors.

Suppose we have such a photo. We can define an island as one cluster, but with an increase we see that it consists of different shades of green.



And this is the 8th cluster, but in a smaller version, the result is similar:



The full version of the program can be viewed on my GitHub .