Img2Num C++ (Internal Developer Docs) dev
API Documentation
Loading...
Searching...
No Matches
kmeans.cpp
1#include "img2num.h"
2#include "internal/cielab.h"
3#include "internal/gpu.h"
4#include "internal/Image.h"
5#include "internal/kmeans_gpu.h"
6#include "internal/LABAPixel.h"
7#include "internal/PixelConverters.h"
8#include "internal/RGBAPixel.h"
9
10#include <algorithm>
11#include <cmath>
12#include <cstdlib>
13#include <cstring>
14#include <ctime>
15#include <functional>
16#include <limits>
17#include <numeric>
18#include <random>
19#include <vector>
20
21static constexpr uint8_t COLOR_SPACE_OPTION_CIELAB {0};
22static constexpr uint8_t COLOR_SPACE_OPTION_RGB {1};
23
24// The K-Means++ Initialization Function
25template <typename PixelT>
26void kMeansPlusPlusInit(
27 const ImageLib::Image<PixelT>& pixels, ImageLib::Image<PixelT>& out_centroids, int k
28) {
29 std::vector<PixelT> centroids;
30
31 int num_pixels = pixels.getSize();
32 // Random number generator setup
33 std::random_device rd;
34 std::mt19937 gen(rd());
35
36 // --- Step 1: Choose the first centroid uniformly at random ---
37 std::uniform_int_distribution<> dis(0, num_pixels - 1);
38 int first_index = dis(gen);
39 centroids.push_back(pixels[first_index]);
40
41 // Vector to store the squared distance of each pixel to its NEAREST existing
42 // centroid. Initialize with max double so the first distance calculation
43 // always updates it.
44 std::vector<double> min_dist_sq(num_pixels, std::numeric_limits<double>::max());
45
46 // --- Step 2 & 3: Repeat until we have k centroids ---
47 for (int i = 1; i < k; ++i) {
48 double sum_dist_sq = 0.0;
49
50 // Update distances relative to the LAST added centroid (centroids.back())
51 // We don't need to recheck previous centroids; min_dist_sq already holds
52 // the best distance to them.
53 for (int j = 0; j < num_pixels; ++j) {
54 double d = PixelT::colorDistance(pixels[j], centroids.back());
55
56 // If this new centroid is closer than the previous best, update the min
57 // distance
58 if (d < min_dist_sq[j]) {
59 min_dist_sq[j] = d;
60 }
61 sum_dist_sq += min_dist_sq[j];
62 }
63
64 // --- Step 3: Choose new center with probability proportional to D(x)^2 ---
65 // We use a weighted random selection (Roulette Wheel Selection)
66 std::uniform_real_distribution<> dist_selector(0.0, sum_dist_sq);
67 double random_value = dist_selector(gen);
68
69 double current_sum = 0.0;
70 int selected_index = -1;
71
72 // Iterate to find the pixel corresponding to the random_value
73 for (int j = 0; j < num_pixels; ++j) {
74 current_sum += min_dist_sq[j];
75 if (current_sum >= random_value) {
76 selected_index = j;
77 break;
78 }
79 }
80
81 // Fallback for floating point rounding errors (pick last one if loop
82 // finishes)
83 if (selected_index == -1) {
84 selected_index = num_pixels - 1;
85 }
86
87 centroids.push_back(pixels[selected_index]);
88 }
89
90 std::copy(centroids.begin(), centroids.end(), out_centroids.begin());
91}
92
94void kmeans_cpu(
95 const uint8_t* data, uint8_t* out_data, int32_t* out_labels, const int32_t width,
96 const int32_t height, const int32_t k, const int32_t max_iter, const uint8_t color_space
97) {
99 pixels.loadFromBuffer(data, width, height, ImageLib::RGBA_CONVERTER<float>);
100 const int32_t num_pixels {pixels.getSize()};
101
102 // width = k, height = 1
103 // k centroids, initialized to rgba(0,0,0,255)
104 // Init of each pixel is from default in Image constructor
106 ImageLib::Image<ImageLib::LABAPixel<float>> centroids_lab {k, 1};
107 std::vector<int32_t> labels(num_pixels, max_iter > 0 ? -1 : 0);
108
109 ImageLib::Image<ImageLib::LABAPixel<float>> lab(pixels.getWidth(), pixels.getHeight());
110 if (color_space == COLOR_SPACE_OPTION_CIELAB) {
111 for (int i {0}; i < pixels.getSize(); ++i) {
112 rgb_to_lab<float, float>(pixels[i], lab[i]);
113 }
114 }
115
116 // Step 2: Initialize centroids randomly
117
118 switch (color_space) {
119 case COLOR_SPACE_OPTION_RGB: {
120 kMeansPlusPlusInit<ImageLib::RGBAPixel<float>>(pixels, centroids, k);
121 break;
122 }
123 case COLOR_SPACE_OPTION_CIELAB: {
124 kMeansPlusPlusInit<ImageLib::LABAPixel<float>>(lab, centroids_lab, k);
125 break;
126 }
127 }
128
129 // Step 3: Run k-means iterations
130
131 // Assignment step
132 for (int32_t iter {0}; iter < max_iter; ++iter) {
133 bool changed {false};
134
135 // Iterate over pixels
136 for (int32_t i {0}; i < num_pixels; ++i) {
137 float min_color_dist {std::numeric_limits<float>::max()};
138 int32_t best_cluster {0};
139
140 // Iterate over centroids to find centroid with most similar color to
141 // pixels[i]
142 float dist;
143 for (int32_t j {0}; j < k; ++j) {
144 switch (color_space) {
145 case COLOR_SPACE_OPTION_RGB: {
146 dist = ImageLib::RGBAPixel<float>::colorDistance(pixels[i], centroids[j]);
147 break;
148 }
149 case COLOR_SPACE_OPTION_CIELAB: {
150 dist = ImageLib::LABAPixel<float>::colorDistance(lab[i], centroids_lab[j]);
151 break;
152 }
153 }
154 if (dist < min_color_dist) {
155 min_color_dist = dist;
156 best_cluster = j;
157 }
158 }
159
160 if (labels[i] != best_cluster) {
161 changed = true;
162 labels[i] = best_cluster;
163 }
164 }
165
166 // Stop if no changes
167 if (!changed) {
168 break;
169 }
170
171 // Update step
172 ImageLib::Image<ImageLib::RGBAPixel<float>> new_centroids(k, 1, 0);
173 ImageLib::Image<ImageLib::LABAPixel<float>> new_centroids_lab(k, 1, 0);
174 std::vector<int32_t> counts(k, 0);
175
176 for (int32_t i = 0; i < num_pixels; ++i) {
177 int32_t cluster = labels[i];
178 switch (color_space) {
179 case COLOR_SPACE_OPTION_RGB: {
180 new_centroids[cluster].red += pixels[i].red;
181 new_centroids[cluster].green += pixels[i].green;
182 new_centroids[cluster].blue += pixels[i].blue;
183 break;
184 }
185 case COLOR_SPACE_OPTION_CIELAB: {
186 new_centroids_lab[cluster].l += lab[i].l;
187 new_centroids_lab[cluster].a += lab[i].a;
188 new_centroids_lab[cluster].b += lab[i].b;
189 break;
190 }
191 }
192 counts[cluster]++;
193 }
194
195 for (int32_t j = 0; j < k; ++j) {
196 /*
197 A centroid may become a dead centroid if it never gets pixels assigned
198 to it. May be good idea to reinitialize these dead centroids.
199 */
200 if (counts[j] > 0) {
201 switch (color_space) {
202 case COLOR_SPACE_OPTION_RGB: {
203 centroids[j].red = new_centroids[j].red / counts[j];
204 centroids[j].green = new_centroids[j].green / counts[j];
205 centroids[j].blue = new_centroids[j].blue / counts[j];
206 break;
207 }
208 case COLOR_SPACE_OPTION_CIELAB: {
209 centroids_lab[j].l = new_centroids_lab[j].l / counts[j];
210 centroids_lab[j].a = new_centroids_lab[j].a / counts[j];
211 centroids_lab[j].b = new_centroids_lab[j].b / counts[j];
212 break;
213 }
214 }
215 }
216 }
217 }
218
219 if (color_space == COLOR_SPACE_OPTION_CIELAB) {
220 for (int32_t i {0}; i < k; ++i) {
221 lab_to_rgb<float, float>(centroids_lab[i], centroids[i]);
222 }
223 }
224
225 // Write the final centroid values to each pixel in the cluster
226 for (int32_t i = 0; i < num_pixels; ++i) {
227 const int32_t cluster = labels[i];
228 out_data[i * 4 + 0] =
229 static_cast<uint8_t>(std::clamp(centroids[cluster].red, 0.0f, 255.0f));
230 out_data[i * 4 + 1] =
231 static_cast<uint8_t>(std::clamp(centroids[cluster].green, 0.0f, 255.0f));
232 out_data[i * 4 + 2] =
233 static_cast<uint8_t>(std::clamp(centroids[cluster].blue, 0.0f, 255.0f));
234 out_data[i * 4 + 3] = 255;
235 }
236
237 // Write labels to out_labels
238 std::memcpy(out_labels, labels.data(), labels.size() * sizeof(int32_t));
239}
240
241namespace img2num {
243 const uint8_t* data, uint8_t* out_data, int32_t* out_labels, const int32_t width,
244 const int32_t height, const int32_t k, const int32_t max_iter, const uint8_t color_space
245) {
246 GPU::getClassInstance().init_gpu();
247
248 if (GPU::getClassInstance().is_initialized()) {
249 kmeans_gpu(data, out_data, out_labels, width, height, k, max_iter, color_space);
250 } else {
251 kmeans_cpu(data, out_data, out_labels, width, height, k, max_iter, color_space);
252 }
253}
254} // namespace img2num
Core image processing functions for img2num project.
void kmeans(const uint8_t *data, uint8_t *out_data, int32_t *out_labels, const int32_t width, const int32_t height, const int32_t k, const int32_t max_iter, const uint8_t color_space)
Perform k-means clustering on image data.
Definition kmeans.cpp:242