File: | home/HaikuArchives/ArtPaint/addons/AddOns/ColorReducer/color_mapper.cpp |
Warning: | line 336, column 12 Value stored to 'color_index' during its initialization is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* |
2 | * Copyright 2003, Heikki Suhonen |
3 | * Distributed under the terms of the MIT License. |
4 | * |
5 | * Authors: |
6 | * Heikki Suhonen <heikki.suhonen@gmail.com> |
7 | * |
8 | */ |
9 | |
10 | |
11 | /* |
12 | Contents: Functions that map an image to a palette while reducing |
13 | artifacts caused by reduction of colors. |
14 | |
15 | Notes: Currently all returned bitmaps are in B_CMAP8 mode. The |
16 | indices in the image are to the palette that is provided as |
17 | a parameter. |
18 | */ |
19 | |
20 | #include <Bitmap.h> |
21 | #include <stdio.h> |
22 | |
23 | #include "BitmapAnalyzer.h" |
24 | #include "color_mapper.h" |
25 | #include "ImageProcessingLibrary.h" |
26 | #include "RandomNumberGenerator.h" |
27 | #include "Selection.h" |
28 | |
29 | BBitmap* nearest_color_mapper(BBitmap * inSource, const rgb_color * inPalette, int inPaletteSize) |
30 | { |
31 | int32 *map_function = new int32[32768]; // using 15 bit colors to do the mapping |
32 | for (int i=0;i<32768;i++) { |
33 | map_function[i] = -1; // the nearest color is not yet found |
34 | } |
35 | |
36 | |
37 | BBitmap *outDestination = new BBitmap(inSource->Bounds(),B_CMAP8,false); |
38 | |
39 | |
40 | uint32 *source_bits = (uint32*)inSource->Bits(); |
41 | uint32 source_bpr = inSource->BytesPerRow()/4; |
42 | |
43 | uint8 *destination_bits = (uint8*)outDestination->Bits(); |
44 | uint32 destination_bpr = outDestination->BytesPerRow(); |
45 | |
46 | |
47 | int32 width = inSource->Bounds().IntegerWidth(); |
48 | int32 height = inSource->Bounds().IntegerHeight(); |
49 | |
50 | int32 source_padding = source_bpr - width - 1; |
51 | int32 destination_padding = destination_bpr - width - 1; |
52 | |
53 | |
54 | // Use this union to guarantee endianness compatibility. |
55 | union { |
56 | uint8 bytes[4]; |
57 | uint32 word; |
58 | } bgra32; |
59 | |
60 | for (int32 y=0;y<=height;y++) { |
61 | for (int32 x=0;x<=width;x++) { |
62 | bgra32.word = *source_bits++; |
63 | // squeeze the 32-bit color to 15 bit index. See BeBook |
64 | // BScreen chapter for the reference on this. |
65 | uint16 rgb15 = ((bgra32.bytes[2] & 0xf8) << 7) | |
66 | ((bgra32.bytes[1] & 0xf8) << 2) | |
67 | ((bgra32.bytes[0] & 0xf8) >> 3); |
68 | if (map_function[rgb15] < 0) { |
69 | // The mapping for the color has not yet been found. |
70 | map_function[rgb15] = find_palette_index(bgra32.word,inPalette,inPaletteSize); |
71 | } |
72 | *destination_bits++ = (uint8)map_function[rgb15]; |
73 | } |
74 | destination_bits += destination_padding; |
75 | source_bits += source_padding; |
76 | } |
77 | |
78 | delete[] map_function; |
79 | |
80 | return outDestination; |
81 | } |
82 | |
83 | |
84 | /* |
85 | This function maps the colors by using Floyd-Steinberg error diffusion dithering. |
86 | The main idea is to distribute the quantization error to the neighbouring |
87 | (unprocessed) pixels. The following weights are used in this version: |
88 | |
89 | X 7/16 |
90 | |
91 | 3/16 5/16 1/16 |
92 | |
93 | Every other scanline is processed from left to right and every other from right to left. |
94 | This reduces the dithering artifacts and helps with the cache on big images. Currently |
95 | this is not the case and every scanline is processed from left to right. |
96 | |
97 | Note that Floyd-Steinberg (or any other EDD) is almost impossible to parellelize properly. |
98 | This is because error propagates through image from pixel to pixel. Any attemp to divide the |
99 | image in blocks and dither them separately leads to unwanted visible lines between the |
100 | different parts. |
101 | */ |
102 | BBitmap* floyd_steinberg_edd_color_mapper(BBitmap * inSource, const rgb_color * inPalette, int inPaletteSize) |
103 | { |
104 | int32 *map_function = new int32[32768]; // using 15 bit colors to do the mapping |
105 | for (int i=0;i<32768;i++) { |
106 | map_function[i] = -1; // the nearest color is not yet found |
107 | } |
108 | |
109 | |
110 | BBitmap *outDestination = new BBitmap(inSource->Bounds(),B_CMAP8,false); |
111 | |
112 | uint32 *source_bits = (uint32*)inSource->Bits(); |
113 | uint32 source_bpr = inSource->BytesPerRow()/4; |
114 | |
115 | uint8 *destination_bits = (uint8*)outDestination->Bits(); |
116 | uint32 destination_bpr = outDestination->BytesPerRow(); |
117 | |
118 | int32 width = inSource->Bounds().IntegerWidth(); |
119 | int32 height = inSource->Bounds().IntegerHeight(); |
120 | |
121 | int32 source_padding = source_bpr - width - 1; |
122 | int32 destination_padding = destination_bpr - width - 1; |
123 | |
124 | |
125 | // We use three error arrays and three side error variables. |
126 | // The error arrays are a little bit wider than the image to |
127 | // avoid cheking for border conditions |
128 | int32 *red_error = new int32[width + 1 + 2]; |
129 | red_error = &red_error[1]; // Allow index of -1 too. |
130 | int16 red_side_error = 0; |
131 | |
132 | int32 *green_error = new int32[width + 1 + 2]; |
133 | green_error = &green_error[1]; // Allow index of -1 too. |
134 | int16 green_side_error = 0; |
135 | |
136 | int32 *blue_error = new int32[width + 1 + 2]; |
137 | blue_error = &blue_error[1]; // Allow index of -1 too. |
138 | int16 blue_side_error = 0; |
139 | |
140 | // Initialize the errors to 0. |
141 | for (int32 i=-1;i<=width + 1;i++) { |
142 | red_error[i] = green_error[i] = blue_error[i] = 0; |
143 | } |
144 | |
145 | |
146 | // We use fixed point arithmetic to avoid type conversions. |
147 | int32 one_sixteenth = (1.0/16.0)*32768; |
148 | int32 three_sixteenth = (3.0/16.0)*32768; |
149 | int32 five_sixteenth = (5.0/16.0)*32768; |
150 | int32 seven_sixteenth = (7.0/16.0)*32768; |
151 | |
152 | // Use this union to guarantee endianness compatibility. |
153 | union { |
154 | uint8 bytes[4]; |
155 | uint32 word; |
156 | } bgra32; |
157 | |
158 | for (int32 y=0;y<=height;y++) { |
159 | red_side_error = green_side_error = blue_side_error = 0; |
160 | if (true/*y % 2 == 0*/) { |
161 | // Go from left to right. |
162 | for (int32 x=0;x<=width;x++) { |
163 | bgra32.word = *source_bits++; |
164 | // Add the error. |
165 | bgra32.bytes[0] = min_c(255,max_c(0,bgra32.bytes[0]-blue_side_error))((255)>(((0)>(bgra32.bytes[0]-blue_side_error)?(0):(bgra32 .bytes[0]-blue_side_error)))?(((0)>(bgra32.bytes[0]-blue_side_error )?(0):(bgra32.bytes[0]-blue_side_error))):(255)); |
166 | bgra32.bytes[1] = min_c(255,max_c(0,bgra32.bytes[1]-green_side_error))((255)>(((0)>(bgra32.bytes[1]-green_side_error)?(0):(bgra32 .bytes[1]-green_side_error)))?(((0)>(bgra32.bytes[1]-green_side_error )?(0):(bgra32.bytes[1]-green_side_error))):(255)); |
167 | bgra32.bytes[2] = min_c(255,max_c(0,bgra32.bytes[2]-red_side_error))((255)>(((0)>(bgra32.bytes[2]-red_side_error)?(0):(bgra32 .bytes[2]-red_side_error)))?(((0)>(bgra32.bytes[2]-red_side_error )?(0):(bgra32.bytes[2]-red_side_error))):(255)); |
168 | |
169 | // squeeze the 32-bit color to 15 bit index. See BeBook |
170 | // BScreen chapter for the reference on this. |
171 | uint16 rgb15 = ((bgra32.bytes[2] & 0xf8) << 7) | |
172 | ((bgra32.bytes[1] & 0xf8) << 2) | |
173 | ((bgra32.bytes[0] & 0xf8) >> 3); |
174 | |
175 | if (map_function[rgb15] < 0) { |
176 | // The mapping for the color has not yet been found. |
177 | map_function[rgb15] = find_palette_index(bgra32.word,inPalette,inPaletteSize); |
178 | } |
179 | |
180 | uint8 color_index = *destination_bits++ = (uint8)map_function[rgb15]; |
181 | |
182 | int32 red_total_error = inPalette[color_index].red - bgra32.bytes[2]; |
183 | int32 green_total_error = inPalette[color_index].green - bgra32.bytes[1]; |
184 | int32 blue_total_error = inPalette[color_index].blue - bgra32.bytes[0]; |
185 | |
186 | red_side_error = (red_error[x+1] + (red_total_error * seven_sixteenth)) >> 15; |
187 | blue_side_error = (blue_error[x+1] + (blue_total_error * seven_sixteenth)) >> 15; |
188 | green_side_error = (green_error[x+1] + (green_total_error * seven_sixteenth)) >> 15; |
189 | |
190 | red_error[x+1] = (red_total_error * one_sixteenth); |
191 | green_error[x+1] = (green_total_error * one_sixteenth); |
192 | blue_error[x+1] = (blue_total_error * one_sixteenth); |
193 | |
194 | red_error[x] += (red_total_error * five_sixteenth); |
195 | green_error[x] += (green_total_error * five_sixteenth); |
196 | blue_error[x] += (blue_total_error * five_sixteenth); |
197 | |
198 | red_error[x-1] += (red_total_error * three_sixteenth); |
199 | green_error[x-1] += (green_total_error * three_sixteenth); |
200 | blue_error[x-1] += (blue_total_error * three_sixteenth); |
201 | } |
202 | destination_bits += destination_padding; |
203 | source_bits += source_padding; |
204 | } |
205 | } |
206 | |
207 | delete[] map_function; |
208 | |
209 | return outDestination; |
210 | } |
211 | |
212 | |
213 | |
214 | BBitmap* preserve_solids_fs_color_mapper(BBitmap * inSource, const rgb_color * inPalette, int inPaletteSize) |
215 | { |
216 | int32 *map_function = new int32[32768]; // using 15 bit colors to do the mapping |
217 | for (int i=0;i<32768;i++) { |
218 | map_function[i] = -1; // the nearest color is not yet found |
219 | } |
220 | |
221 | |
222 | BBitmap *outDestination = new BBitmap(inSource->Bounds(),B_CMAP8,false); |
223 | |
224 | uint32 *source_bits = (uint32*)inSource->Bits(); |
225 | uint32 source_bpr = inSource->BytesPerRow()/4; |
226 | |
227 | uint8 *destination_bits = (uint8*)outDestination->Bits(); |
228 | uint32 destination_bpr = outDestination->BytesPerRow(); |
229 | |
230 | int32 width = inSource->Bounds().IntegerWidth(); |
231 | int32 height = inSource->Bounds().IntegerHeight(); |
232 | |
233 | int32 source_padding = source_bpr - width - 1; |
234 | int32 destination_padding = destination_bpr - width - 1; |
235 | |
236 | |
237 | // We use three error arrays and three side error variables. |
238 | // The error arrays are a little bit wider than the image to |
239 | // avoid cheking for border conditions |
240 | int32 *red_error = new int32[width + 1 + 2]; |
241 | red_error = &red_error[1]; // Allow index of -1 too. |
242 | int16 red_side_error = 0; |
243 | |
244 | int32 *green_error = new int32[width + 1 + 2]; |
245 | green_error = &green_error[1]; // Allow index of -1 too. |
246 | int16 green_side_error = 0; |
247 | |
248 | int32 *blue_error = new int32[width + 1 + 2]; |
249 | blue_error = &blue_error[1]; // Allow index of -1 too. |
250 | int16 blue_side_error = 0; |
251 | |
252 | // Initialize the errors to 0. |
253 | for (int32 i=-1;i<=width + 1;i++) { |
254 | red_error[i] = green_error[i] = blue_error[i] = 0; |
255 | } |
256 | |
257 | |
258 | // We use fixed point arithmetic to avoid type conversions. |
259 | int32 one_sixteenth = (1.0/16.0)*32768; |
260 | int32 three_sixteenth = (3.0/16.0)*32768; |
261 | int32 five_sixteenth = (5.0/16.0)*32768; |
262 | int32 seven_sixteenth = (7.0/16.0)*32768; |
263 | |
264 | // Use this union to guarantee endianness compatibility. |
265 | union { |
266 | uint8 bytes[4]; |
267 | uint32 word; |
268 | } bgra32; |
269 | |
270 | // Make the blurred bitmap |
271 | BBitmap *blurred = new BBitmap(inSource); |
272 | ImageProcessingLibrary iplib; |
273 | iplib.gaussian_blur(blurred,10); |
274 | BitmapAnalyzer *analyzer = new BitmapAnalyzer(inSource); |
275 | |
276 | |
277 | for (int32 y=0;y<=height;y++) { |
278 | red_side_error = green_side_error = blue_side_error = 0; |
279 | if (true/*y % 2 == 0*/) { |
280 | // Go from left to right. |
281 | for (int32 x=0;x<=width;x++) { |
282 | if (analyzer->GradientMagnitude(x,y) > 0) { |
283 | bgra32.word = *source_bits++; |
284 | // Add the error. |
285 | bgra32.bytes[0] = min_c(255,max_c(0,bgra32.bytes[0]-blue_side_error))((255)>(((0)>(bgra32.bytes[0]-blue_side_error)?(0):(bgra32 .bytes[0]-blue_side_error)))?(((0)>(bgra32.bytes[0]-blue_side_error )?(0):(bgra32.bytes[0]-blue_side_error))):(255)); |
286 | bgra32.bytes[1] = min_c(255,max_c(0,bgra32.bytes[1]-green_side_error))((255)>(((0)>(bgra32.bytes[1]-green_side_error)?(0):(bgra32 .bytes[1]-green_side_error)))?(((0)>(bgra32.bytes[1]-green_side_error )?(0):(bgra32.bytes[1]-green_side_error))):(255)); |
287 | bgra32.bytes[2] = min_c(255,max_c(0,bgra32.bytes[2]-red_side_error))((255)>(((0)>(bgra32.bytes[2]-red_side_error)?(0):(bgra32 .bytes[2]-red_side_error)))?(((0)>(bgra32.bytes[2]-red_side_error )?(0):(bgra32.bytes[2]-red_side_error))):(255)); |
288 | |
289 | // squeeze the 32-bit color to 15 bit index. See BeBook |
290 | // BScreen chapter for the reference on this. |
291 | uint16 rgb15 = ((bgra32.bytes[2] & 0xf8) << 7) | |
292 | ((bgra32.bytes[1] & 0xf8) << 2) | |
293 | ((bgra32.bytes[0] & 0xf8) >> 3); |
294 | |
295 | if (map_function[rgb15] < 0) { |
296 | // The mapping for the color has not yet been found. |
297 | map_function[rgb15] = find_palette_index(bgra32.word,inPalette,inPaletteSize); |
298 | } |
299 | |
300 | uint8 color_index = *destination_bits++ = (uint8)map_function[rgb15]; |
301 | |
302 | int32 red_total_error = inPalette[color_index].red - bgra32.bytes[2]; |
303 | int32 green_total_error = inPalette[color_index].green - bgra32.bytes[1]; |
304 | int32 blue_total_error = inPalette[color_index].blue - bgra32.bytes[0]; |
305 | |
306 | red_side_error = (red_error[x+1] + (red_total_error * seven_sixteenth)) >> 15; |
307 | blue_side_error = (blue_error[x+1] + (blue_total_error * seven_sixteenth)) >> 15; |
308 | green_side_error = (green_error[x+1] + (green_total_error * seven_sixteenth)) >> 15; |
309 | |
310 | red_error[x+1] = (red_total_error * one_sixteenth); |
311 | green_error[x+1] = (green_total_error * one_sixteenth); |
312 | blue_error[x+1] = (blue_total_error * one_sixteenth); |
313 | |
314 | red_error[x] += (red_total_error * five_sixteenth); |
315 | green_error[x] += (green_total_error * five_sixteenth); |
316 | blue_error[x] += (blue_total_error * five_sixteenth); |
317 | |
318 | red_error[x-1] += (red_total_error * three_sixteenth); |
319 | green_error[x-1] += (green_total_error * three_sixteenth); |
320 | blue_error[x-1] += (blue_total_error * three_sixteenth); |
321 | } |
322 | else { |
323 | bgra32.word = *source_bits++; |
324 | |
325 | // squeeze the 32-bit color to 15 bit index. See BeBook |
326 | // BScreen chapter for the reference on this. |
327 | uint16 rgb15 = ((bgra32.bytes[2] & 0xf8) << 7) | |
328 | ((bgra32.bytes[1] & 0xf8) << 2) | |
329 | ((bgra32.bytes[0] & 0xf8) >> 3); |
330 | |
331 | if (map_function[rgb15] < 0) { |
332 | // The mapping for the color has not yet been found. |
333 | map_function[rgb15] = find_palette_index(bgra32.word,inPalette,inPaletteSize); |
334 | } |
335 | |
336 | uint8 color_index = *destination_bits++ = (uint8)map_function[rgb15]; |
Value stored to 'color_index' during its initialization is never read | |
337 | |
338 | |
339 | red_side_error = red_error[x+1] >> 15; |
340 | blue_side_error = blue_error[x+1] >> 15; |
341 | green_side_error = green_error[x+1] >> 15; |
342 | |
343 | red_error[x+1] = 0; |
344 | green_error[x+1] = 0; |
345 | blue_error[x+1] = 0; |
346 | } |
347 | } |
348 | destination_bits += destination_padding; |
349 | source_bits += source_padding; |
350 | } |
351 | } |
352 | |
353 | delete[] map_function; |
354 | delete analyzer; |
355 | delete blurred; |
356 | |
357 | return outDestination; |
358 | } |
359 | |
360 | |
361 | BBitmap* n_candidate_color_mapper(BBitmap * inSource, const rgb_color * inPalette, int inPaletteSize, int maxCandidates) |
362 | { |
363 | RandomNumberGenerator *generator = new RandomNumberGenerator(10111071,10000); |
364 | |
365 | struct Candidate { |
366 | int32 index; |
367 | float prob; |
368 | }; |
369 | |
370 | struct CandidateList { |
371 | int32 *candidate_count; |
372 | Candidate **candidate_table; |
373 | }; |
374 | |
375 | CandidateList candidates; |
376 | candidates.candidate_table = new Candidate*[32768]; |
377 | candidates.candidate_count = new int32[32768]; |
378 | |
379 | for (int i=0;i<32768;i++) { |
380 | candidates.candidate_table[i] = new Candidate[maxCandidates]; |
381 | candidates.candidate_count[i] = 0; // the candidates have not yet been found |
382 | } |
383 | |
384 | |
385 | BBitmap *outDestination = new BBitmap(inSource->Bounds(),B_CMAP8,false); |
386 | |
387 | |
388 | uint32 *source_bits = (uint32*)inSource->Bits(); |
389 | uint32 source_bpr = inSource->BytesPerRow()/4; |
390 | |
391 | uint8 *destination_bits = (uint8*)outDestination->Bits(); |
392 | uint32 destination_bpr = outDestination->BytesPerRow(); |
393 | |
394 | |
395 | int32 width = inSource->Bounds().IntegerWidth(); |
396 | int32 height = inSource->Bounds().IntegerHeight(); |
397 | |
398 | int32 source_padding = source_bpr - width - 1; |
399 | int32 destination_padding = destination_bpr - width - 1; |
400 | |
401 | |
402 | // Use this union to guarantee endianness compatibility. |
403 | union { |
404 | uint8 bytes[4]; |
405 | uint32 word; |
406 | } bgra32; |
407 | |
408 | for (int32 y=0;y<=height;y++) { |
409 | for (int32 x=0;x<=width;x++) { |
410 | bgra32.word = *source_bits++; |
411 | // squeeze the 32-bit color to 15 bit index. See BeBook |
412 | // BScreen chapter for the reference on this. |
413 | uint16 rgb15 = ((bgra32.bytes[2] & 0xf8) << 7) | |
414 | ((bgra32.bytes[1] & 0xf8) << 2) | |
415 | ((bgra32.bytes[0] & 0xf8) >> 3); |
416 | if (candidates.candidate_count[rgb15] <= 0) { |
417 | // The candidates for the color have not yet been found. |
418 | // map_function[rgb15] = find_palette_index(bgra32.word,inPalette,inPaletteSize); |
419 | float max_error = -1; |
420 | float inverse_error_sum = 0; |
421 | int32 number_of_candidates = 0; |
422 | for (int32 i=0;i<maxCandidates;i++) { |
423 | float distance; |
424 | candidates.candidate_table[rgb15][i].index = find_candidate(bgra32.word,inPalette,inPaletteSize,i+1,&distance); |
425 | candidates.candidate_table[rgb15][i].prob = distance; |
426 | if (max_error < 0) { |
427 | max_error = 5.0 * distance; |
428 | number_of_candidates++; |
429 | if (distance > 0) |
430 | inverse_error_sum += 1.0 / distance; |
431 | printf("color:\t%d\t%d\t%d\n",bgra32.bytes[2],bgra32.bytes[1],bgra32.bytes[0]); |
432 | rgb_color pc = inPalette[candidates.candidate_table[rgb15][i].index]; |
433 | printf("\tcandidate:\t%d\t%d\t%d\n",pc.red,pc.green,pc.blue); |
434 | } |
435 | else if (distance <= max_error) { |
436 | number_of_candidates++; |
437 | rgb_color pc = inPalette[candidates.candidate_table[rgb15][i].index]; |
438 | printf("\tcandidate:\t%d\t%d\t%d\n",pc.red,pc.green,pc.blue); |
439 | if (distance > 0) |
440 | inverse_error_sum += 1.0 / distance; |
441 | } |
442 | } |
443 | |
444 | // calculate the probabilities |
445 | candidates.candidate_count[rgb15] = number_of_candidates; |
446 | for (int32 i=0;i<number_of_candidates;i++) { |
447 | float dist = candidates.candidate_table[rgb15][i].prob; |
448 | if (dist > 0) { |
449 | candidates.candidate_table[rgb15][i].prob = (1.0 / dist) / inverse_error_sum; |
450 | if (i>0) { |
451 | candidates.candidate_table[rgb15][i].prob += candidates.candidate_table[rgb15][i-1].prob; |
452 | } |
453 | } |
454 | else { |
455 | candidates.candidate_table[rgb15][i].prob = 1.0; |
456 | } |
457 | } |
458 | } |
459 | |
460 | // Here take a random number and select the proper candidate. |
461 | float random_number = generator->UniformDistribution(0,1.0); |
462 | int i = 0; |
463 | while ((candidates.candidate_table[rgb15][i].prob < random_number) && (i<(candidates.candidate_count[rgb15]-1))) { |
464 | i++; |
465 | } |
466 | *destination_bits++ = candidates.candidate_table[rgb15][i].index; |
467 | } |
468 | destination_bits += destination_padding; |
469 | source_bits += source_padding; |
470 | } |
471 | |
472 | |
473 | return outDestination; |
474 | } |
475 |