Img2Num C++ (Internal Developer Docs) dev
API Documentation
Loading...
Searching...
No Matches
kmeans_gpu.cpp
1
2#include "internal/kmeans_gpu.h"
3
4#include "img2num.h"
5#include "internal/cielab.h"
7#include "internal/Image.h"
8#include "internal/LABAPixel.h"
9#include "internal/PixelConverters.h"
10#include "internal/RGBAPixel.h"
11
12#include <algorithm>
13#include <cmath>
14#include <cstddef>
15#include <cstdint>
16#include <cstring>
17#include <limits>
18#include <random>
19#include <type_traits>
20#include <vector>
21
22// Packed struct definitions matching WGSL std140 layout — unchanged from original
23#ifdef _MSC_VER
24#pragma pack(push, 1)
25#endif
26struct Params {
27 uint32_t numPoints;
28 uint32_t numCentroids;
29 uint32_t pad[2];
30}
31#ifndef _MSC_VER
32__attribute__((packed))
33#endif
34;
35#ifdef _MSC_VER
36#pragma pack(pop)
37#endif
38
39#ifdef _MSC_VER
40#pragma pack(push, 1)
41#endif
43 int32_t sumR;
44 int32_t sumG;
45 int32_t sumB;
46 uint32_t count;
47}
48#ifndef _MSC_VER
49__attribute__((packed))
50#endif
51;
52#ifdef _MSC_VER
53#pragma pack(pop)
54#endif
55
56#ifdef _MSC_VER
57#pragma pack(push, 1)
58#endif
60 float r, g, b, a;
61 uint32_t width;
62 uint32_t pad[3]; // Padding to align to 16 bytes
63}
64#ifndef _MSC_VER
65__attribute__((packed))
66#endif
67;
68#ifdef _MSC_VER
69#pragma pack(pop)
70#endif
71
83template <typename PixelT>
84void kMeansPlusPlusInitGpu(
85 const ImageLib::Image<PixelT>& pixels, ImageLib::Image<PixelT>& out_centroids, int k,
86 const uint8_t color_space
87) {
88 if (k <= 0)
89 return;
90
91 size_t width = pixels.getWidth();
92 size_t height = pixels.getHeight();
93 size_t num_pixels = width * height;
94 uint32_t w = static_cast<uint32_t>(width);
95 uint32_t h = static_cast<uint32_t>(height);
96
97 std::vector<PixelT> centroids;
98
99 // 1. Upload image as RGBA32Float texture
100 gpu::Texture inputTexture(
101 w, h, wgpu::TextureFormat::RGBA32Float,
102 wgpu::TextureUsage::TextureBinding | wgpu::TextureUsage::CopyDst
103 );
104
105 std::vector<float> gpu_pixels;
106 gpu_pixels.reserve(num_pixels * 4);
107 for (size_t i = 0; i < num_pixels; i++) {
108 PixelT p = pixels[i];
109 if constexpr (std::is_same_v<PixelT, ImageLib::LABAPixel<float>>) {
110 gpu_pixels.push_back(p.l / 255.0f);
111 gpu_pixels.push_back(p.a / 255.0f);
112 gpu_pixels.push_back(p.b / 255.0f);
113 gpu_pixels.push_back(p.alpha / 255.0f);
114 } else {
115 gpu_pixels.push_back(p.red / 255.0f);
116 gpu_pixels.push_back(p.green / 255.0f);
117 gpu_pixels.push_back(p.blue / 255.0f);
118 gpu_pixels.push_back(p.alpha / 255.0f);
119 }
120 }
121 inputTexture.write(gpu_pixels.data(), gpu_pixels.size() * sizeof(float), 16);
122
123 // 2. MinDist buffer (initialized to FLT_MAX so first centroid overwrites everything)
124 std::vector<float> initial_dists(num_pixels, std::numeric_limits<float>::max());
125 gpu::Buffer<float> minDistBuffer(
126 num_pixels,
127 wgpu::BufferUsage::Storage | wgpu::BufferUsage::CopySrc | wgpu::BufferUsage::CopyDst
128 );
129 minDistBuffer.write(initial_dists);
130
131 // 3. Uniform buffer for passing new centroid color
132 gpu::Buffer<CentroidParams> paramBuffer(
133 1, wgpu::BufferUsage::Uniform | wgpu::BufferUsage::CopyDst
134 );
135
136 // 4. Pipeline and bind group
137 wgpu::ComputePipeline pipeline = gpu::cached_pipeline("dist_shader", "updateDistShader");
138
139 wgpu::BindGroup bindGroup = gpu::make_bind_group(
140 pipeline, 0,
141 {
142 gpu::BindEntry::texture(0, inputTexture),
143 gpu::BindEntry::buffer_entry(1, minDistBuffer),
144 gpu::BindEntry::buffer_entry(2, paramBuffer),
145 }
146 );
147
148 // RNG Setup
149 std::random_device rd;
150 std::mt19937 gen(rd());
151
152 // Step 1: Choose the first centroid randomly
153 std::uniform_int_distribution<> dis(0, num_pixels - 1);
154 int first_index = dis(gen);
155 centroids.push_back(pixels[first_index]);
156
157 // Step 2 & 3: Iteratively select remaining centroids
158 for (int i = 1; i < k; ++i) {
159 // A. Upload current centroid to GPU
160 PixelT c = centroids.back();
161 CentroidParams params;
162 if constexpr (std::is_same_v<PixelT, ImageLib::LABAPixel<float>>) {
163 params = CentroidParams {
164 c.l / 255.0f, c.a / 255.0f, c.b / 255.0f, 1.0f, static_cast<uint32_t>(width)
165 };
166 } else {
167 params = CentroidParams {
168 c.red / 255.0f, c.green / 255.0f, c.blue / 255.0f, 1.0f,
169 static_cast<uint32_t>(width)
170 };
171 }
172 paramBuffer.write(&params, 1);
173
174 // B. Dispatch shader (updates min_dist buffer on GPU)
175 gpu::dispatch(pipeline, bindGroup, gpu::workgroup_count(w), gpu::workgroup_count(h));
176
177 // C. Read distances back to CPU
178 std::vector<float> dists = minDistBuffer.read();
179
180 // D. CPU-side roulette wheel selection
181 double sum_dist_sq = 0.0;
182 for (size_t j = 0; j < num_pixels; ++j) {
183 sum_dist_sq += dists[j];
184 }
185
186 std::uniform_real_distribution<> dist_selector(0.0, sum_dist_sq);
187 double random_value = dist_selector(gen);
188 double current_sum = 0.0;
189 int selected_index = -1;
190
191 for (size_t j = 0; j < num_pixels; ++j) {
192 current_sum += dists[j];
193 if (current_sum >= random_value) {
194 selected_index = j;
195 break;
196 }
197 }
198
199 if (selected_index == -1)
200 selected_index = num_pixels - 1;
201
202 centroids.push_back(pixels[selected_index]);
203
204#if defined(__EMSCRIPTEN__)
205 emscripten_sleep(10);
206#endif
207 }
208
209 std::copy(centroids.begin(), centroids.end(), out_centroids.begin());
210
211#if defined(__EMSCRIPTEN__)
212 emscripten_sleep(50);
213#endif
214 // All textures/buffers destroyed automatically by RAII
215}
216
231void kmeans_gpu(
232 const uint8_t* data, uint8_t* out_data, int32_t* out_labels, const int32_t width,
233 const int32_t height, const int32_t k, const int32_t max_iter, const uint8_t color_space
234) {
236 pixels.loadFromBuffer(data, width, height, ImageLib::RGBA_CONVERTER<float>);
237 const int32_t num_pixels {pixels.getSize()};
238
240 ImageLib::Image<ImageLib::LABAPixel<float>> centroids_lab {k, 1};
241 std::vector<int32_t> labels(num_pixels, -1);
242
243 ImageLib::Image<ImageLib::LABAPixel<float>> lab(pixels.getWidth(), pixels.getHeight());
244
245 if (color_space == gpu::COLOR_SPACE_CIELAB) {
246 for (int i {0}; i < pixels.getSize(); ++i) {
247 rgb_to_lab<float, float>(pixels[i], lab[i]);
248 }
249 }
250
251 IMG2NUM_LOG_DEBUG("starting");
252
253 // Step 2: Initialize centroids via K-Means++
254 switch (color_space) {
255 case gpu::COLOR_SPACE_RGB:
256 kMeansPlusPlusInitGpu<ImageLib::RGBAPixel<float>>(pixels, centroids, k, color_space);
257 break;
259 kMeansPlusPlusInitGpu<ImageLib::LABAPixel<float>>(lab, centroids_lab, k, color_space);
260 break;
261 }
262
263 IMG2NUM_LOG_DEBUG("kmeans++ init done");
264
265 // =========================================================================
266 // GPU resource setup (previously in setup() function)
267 // =========================================================================
268 const uint32_t w = static_cast<uint32_t>(width);
269 const uint32_t h = static_cast<uint32_t>(height);
270 constexpr uint32_t bpp = 16; // RGBA32Float = 16 bytes per pixel
271
272 // Input texture
273 gpu::Texture inputTexture(
274 w, h, wgpu::TextureFormat::RGBA32Float,
275 wgpu::TextureUsage::TextureBinding | wgpu::TextureUsage::CopyDst
276 );
277
278 std::vector<float> pixels_;
279 pixels_.reserve(num_pixels * 4);
280 for (int i = 0; i < num_pixels; i++) {
281 switch (color_space) {
282 case gpu::COLOR_SPACE_RGB: {
283 auto p = pixels[i];
284 pixels_.push_back(p.red / 255.0f);
285 pixels_.push_back(p.green / 255.0f);
286 pixels_.push_back(p.blue / 255.0f);
287 pixels_.push_back(p.alpha / 255.0f);
288 break;
289 }
291 auto p = lab[i];
292 pixels_.push_back(p.l / 255.0f);
293 pixels_.push_back(p.a / 255.0f);
294 pixels_.push_back(p.b / 255.0f);
295 pixels_.push_back(p.alpha / 255.0f);
296 break;
297 }
298 }
299 }
300 inputTexture.write(pixels_.data(), pixels_.size() * sizeof(float), bpp);
301
302 // Centroid texture (k x 1)
303 gpu::Texture centroidTexture(
304 static_cast<uint32_t>(k), 1, wgpu::TextureFormat::RGBA32Float,
305 wgpu::TextureUsage::TextureBinding | wgpu::TextureUsage::StorageBinding |
306 wgpu::TextureUsage::CopyDst | wgpu::TextureUsage::CopySrc
307 );
308
309 std::vector<float> centroids_;
310 centroids_.reserve(k * 4);
311 switch (color_space) {
312 case gpu::COLOR_SPACE_RGB:
313 for (int i = 0; i < k; i++) {
314 auto p = centroids[i];
315 centroids_.push_back(p.red / 255.0f);
316 centroids_.push_back(p.green / 255.0f);
317 centroids_.push_back(p.blue / 255.0f);
318 centroids_.push_back(p.alpha / 255.0f);
319 }
320 break;
322 for (int i = 0; i < k; i++) {
323 auto p = centroids_lab[i];
324 centroids_.push_back(p.l / 255.0f);
325 centroids_.push_back(p.a / 255.0f);
326 centroids_.push_back(p.b / 255.0f);
327 centroids_.push_back(p.alpha / 255.0f);
328 }
329 break;
330 }
331 centroidTexture.write(centroids_.data(), centroids_.size() * sizeof(float), bpp);
332
333 // Label texture
334 gpu::Texture labelTexture(
335 w, h, wgpu::TextureFormat::RGBA32Uint,
336 wgpu::TextureUsage::TextureBinding | wgpu::TextureUsage::StorageBinding |
337 wgpu::TextureUsage::CopyDst | wgpu::TextureUsage::CopySrc
338 );
339
340 // Params uniform buffer
341 gpu::Buffer<Params> paramBuffer(1, wgpu::BufferUsage::Uniform | wgpu::BufferUsage::CopyDst);
342 Params params = {static_cast<uint32_t>(num_pixels), static_cast<uint32_t>(k)};
343 paramBuffer.write(&params, 1);
344
345 // Cluster accumulator storage buffer
346 std::vector<ClusterAccumulator> reset_centroids(k, {0, 0, 0, 0});
348 k, wgpu::BufferUsage::Storage | wgpu::BufferUsage::CopyDst
349 );
350 accBuffer.write(reset_centroids);
351
352 // Pipelines
353 wgpu::ComputePipeline pipeline1 =
354 gpu::cached_pipeline("assign_update_shader", "assignUpdateShader");
355 wgpu::ComputePipeline pipeline2 = gpu::cached_pipeline("resolve_shader", "resolveShader");
356
357 // Bind groups
358 wgpu::BindGroup bindGroup1 = gpu::make_bind_group(
359 pipeline1, 0,
360 {
361 gpu::BindEntry::texture(0, inputTexture),
362 gpu::BindEntry::texture(1, centroidTexture),
363 gpu::BindEntry::texture(2, labelTexture),
364 gpu::BindEntry::buffer_entry(3, paramBuffer),
365 gpu::BindEntry::buffer_entry(4, accBuffer),
366 }
367 );
368
369 wgpu::BindGroup bindGroup2 = gpu::make_bind_group(
370 pipeline2, 0,
371 {
372 gpu::BindEntry::buffer_entry(0, accBuffer),
373 gpu::BindEntry::texture(1, centroidTexture),
374 }
375 );
376
377 // =========================================================================
378 // Main K-Means loop — all iterations batched into one submission
379 // =========================================================================
380 IMG2NUM_LOG_DEBUG("start iterations");
381 uint32_t wgX = gpu::workgroup_count(w);
382 uint32_t wgY = gpu::workgroup_count(h);
383
384 wgpu::CommandEncoder encoder = GPU::getClassInstance().get_device().CreateCommandEncoder();
385 for (int32_t iter {0}; iter < max_iter; ++iter) {
386 gpu::encode_pass(encoder, pipeline1, bindGroup1, wgX, wgY);
387 gpu::encode_pass(encoder, pipeline2, bindGroup2, gpu::workgroup_count(k, 256));
388 }
389 wgpu::CommandBuffer commands = encoder.Finish();
390 GPU::getClassInstance().get_queue().Submit(1, &commands);
391 IMG2NUM_LOG_DEBUG("done iterations");
392
393 // =========================================================================
394 // Readback — alignment stripping handled automatically
395 // =========================================================================
396
397 // Read labels (RGBA32Uint, 16 bytes/pixel — extract R channel as label)
398 IMG2NUM_LOG_DEBUG("read out");
399 std::vector<uint8_t> labelData = labelTexture.read(bpp);
400
401 IMG2NUM_LOG_DEBUG("mapping labels");
402 for (int32_t i = 0; i < num_pixels; ++i) {
403 uint32_t r = 0;
404 std::memcpy(&r, &labelData[i * bpp], sizeof(uint32_t));
405 labels[i] = static_cast<int32_t>(r);
406 }
407
408 // Read centroids (RGBA32Float, k x 1 texture)
409 std::vector<uint8_t> centroidData = centroidTexture.read(bpp);
410 const float* centroidFloats = reinterpret_cast<const float*>(centroidData.data());
411
412 IMG2NUM_LOG_DEBUG("mapping centroids");
413 for (int i = 0; i < k; i++) {
414 float cr = centroidFloats[i * 4];
415 float cg = centroidFloats[i * 4 + 1];
416 float cb = centroidFloats[i * 4 + 2];
417 float ca = centroidFloats[i * 4 + 3];
418 switch (color_space) {
419 case gpu::COLOR_SPACE_RGB:
420 centroids[i] =
421 ImageLib::RGBAPixel<float>(cr * 255.f, cg * 255.f, cb * 255.f, ca * 255.f);
422 break;
424 centroids_lab[i] =
425 ImageLib::LABAPixel<float>(cr * 255.f, cg * 255.f, cb * 255.f, ca * 255.f);
426 break;
427 }
428 }
429
430 // =========================================================================
431 // Post-processing — LAB→RGB conversion and output
432 // =========================================================================
433 if (color_space == gpu::COLOR_SPACE_CIELAB) {
434 for (int32_t i {0}; i < k; ++i) {
435 lab_to_rgb<float, float>(centroids_lab[i], centroids[i]);
436 }
437 }
438
439 for (int32_t i = 0; i < num_pixels; ++i) {
440 const int32_t cluster = labels[i];
441 out_data[i * 4 + 0] = static_cast<uint8_t>(std::round(centroids[cluster].red));
442 out_data[i * 4 + 1] = static_cast<uint8_t>(std::round(centroids[cluster].green));
443 out_data[i * 4 + 2] = static_cast<uint8_t>(std::round(centroids[cluster].blue));
444 out_data[i * 4 + 3] = 255;
445 }
446
447 // Write labels to out_labels
448 IMG2NUM_LOG_DEBUG("copying labels out");
449 std::memcpy(out_labels, labels.data(), labels.size() * sizeof(int32_t));
450
451#if defined(__EMSCRIPTEN__)
452 emscripten_sleep(50);
453#endif
454 // All textures, buffers destroyed automatically by RAII destructors
455}
RAII wrapper around a wgpu::Buffer with compile-time type safety.
Definition gpu_utils.h:131
RAII wrapper around a wgpu::Texture with upload and aligned readback.
Definition gpu_utils.h:257
Reusable RAII helpers for WebGPU/Dawn compute work.
static constexpr uint8_t COLOR_SPACE_CIELAB
Color space selector constants previously duplicated in each kernel.
Definition gpu_utils.h:45
void encode_pass(wgpu::CommandEncoder &encoder, const wgpu::ComputePipeline &pipeline, const wgpu::BindGroup &bind_group, uint32_t groups_x, uint32_t groups_y=1, uint32_t groups_z=1)
Encode a compute pass into an existing command encoder.
Definition gpu_utils.h:502
void dispatch(const wgpu::ComputePipeline &pipeline, const wgpu::BindGroup &bind_group, uint32_t groups_x, uint32_t groups_y=1, uint32_t groups_z=1)
Encode, finish, and submit a single compute dispatch.
Definition gpu_utils.h:523
uint32_t workgroup_count(uint32_t total_size, uint32_t workgroup_size=16)
Compute the number of workgroups needed to cover total_size with workgroups of workgroup_size.
Definition gpu_utils.h:541
wgpu::ComputePipeline cached_pipeline(const std::string &shader_id, const std::string &label)
Get or create a compute pipeline, caching by shader ID.
Definition gpu_utils.h:62
wgpu::BindGroup make_bind_group(const wgpu::ComputePipeline &pipeline, uint32_t group_index, const std::vector< BindEntry > &entries)
Build a wgpu::BindGroup from a pipeline layout and a list of entries.
Definition gpu_utils.h:459
Core image processing functions for img2num project.
static BindEntry buffer_entry(uint32_t binding, const Buffer< T > &buf)
Create a buffer entry (storage or uniform).
Definition gpu_utils.h:435
static BindEntry texture(uint32_t binding, const Texture &tex)
Create a texture-view entry.
Definition gpu_utils.h:419