| 1 |
|
| /* quant.c - provides general image quantization |
| 2 |
|
| currently only used by gif.c, but maybe we'll support producing |
| 3 |
|
| 8-bit (or bigger indexed) png files at some point |
| 4 |
|
| */ |
| 5 |
|
| #include "imager.h" |
| 6 |
|
| #include "imageri.h" |
| 7 |
|
| |
| 8 |
|
| static void makemap_webmap(i_quantize *); |
| 9 |
|
| static void makemap_addi(i_quantize *, i_img **imgs, int count); |
| 10 |
|
| static void makemap_mediancut(i_quantize *, i_img **imgs, int count); |
| 11 |
|
| static void makemap_mono(i_quantize *); |
| 12 |
|
| static void makemap_gray(i_quantize *, int step); |
| 13 |
|
| |
| 14 |
|
| static int makemap_palette(i_quantize *, i_img **imgs, int count); |
| 15 |
|
| |
| 16 |
|
| static |
| 17 |
|
| void |
| 18 |
1140 |
| setcol(i_color *cl,unsigned char r,unsigned char g,unsigned char b,unsigned char a) { |
| 19 |
1140 |
| cl->rgba.r=r; |
| 20 |
1140 |
| cl->rgba.g=g; |
| 21 |
1140 |
| cl->rgba.b=b; |
| 22 |
1140 |
| cl->rgba.a=a; |
| 23 |
1140 |
| } |
| 24 |
|
| |
| 25 |
|
| |
| 26 |
|
| |
| 27 |
|
| /* make a colour map overwrites mc_existing/mc_count in quant Note |
| 28 |
|
| that i_makemap will be called once for each image if mc_perimage is |
| 29 |
|
| set and the format support multiple colour maps per image. |
| 30 |
|
| |
| 31 |
|
| This means we don't need any special processing at this level to |
| 32 |
|
| handle multiple colour maps. |
| 33 |
|
| */ |
| 34 |
|
| |
| 35 |
|
| /* |
| 36 |
|
| =item i_quant_makemap(C<quant>, C<imgs>, C<count>) |
| 37 |
|
| |
| 38 |
|
| =category Image quantization |
| 39 |
|
| |
| 40 |
|
| Analyzes the C<count> images in C<imgs> according to the rules in |
| 41 |
|
| C<quant> to build a color map (optimal or not depending on |
| 42 |
|
| C<< quant->make_colors >>). |
| 43 |
|
| |
| 44 |
|
| =cut |
| 45 |
|
| */ |
| 46 |
|
| |
| 47 |
|
| void |
| 48 |
22 |
| i_quant_makemap(i_quantize *quant, i_img **imgs, int count) { |
| 49 |
|
| |
| 50 |
22 |
▶ | if (quant->translate == pt_giflib) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (quant->translate == pt_giflib) { |
0 |
22 |
22 |
|
| 51 |
|
| /* giflib does it's own color table generation */ |
| 52 |
|
| /* previously we used giflib's quantizer, but it didn't handle multiple |
| 53 |
|
| images, which made it hard to build a global color map |
| 54 |
|
| We've implemented our own median cut code so we can ignore |
| 55 |
|
| the giflib version */ |
| 56 |
0 |
| makemap_mediancut(quant, imgs, count); |
| 57 |
0 |
| return; |
| 58 |
|
| } |
| 59 |
|
| |
| 60 |
22 |
| switch (quant->make_colors & mc_mask) { |
| 61 |
7 |
| case mc_none: |
| 62 |
|
| /* use user's specified map */ |
| 63 |
7 |
| break; |
| 64 |
4 |
| case mc_web_map: |
| 65 |
4 |
| makemap_webmap(quant); |
| 66 |
4 |
| break; |
| 67 |
|
| |
| 68 |
5 |
| case mc_median_cut: |
| 69 |
5 |
| makemap_mediancut(quant, imgs, count); |
| 70 |
5 |
| break; |
| 71 |
|
| |
| 72 |
3 |
| case mc_mono: |
| 73 |
3 |
| makemap_mono(quant); |
| 74 |
3 |
| break; |
| 75 |
|
| |
| 76 |
1 |
| case mc_gray: |
| 77 |
1 |
| makemap_gray(quant, 1); |
| 78 |
1 |
| break; |
| 79 |
|
| |
| 80 |
1 |
| case mc_gray4: |
| 81 |
1 |
| makemap_gray(quant, 85); |
| 82 |
1 |
| break; |
| 83 |
|
| |
| 84 |
1 |
| case mc_gray16: |
| 85 |
1 |
| makemap_gray(quant, 17); |
| 86 |
1 |
| break; |
| 87 |
|
| |
| 88 |
0 |
| case mc_addi: |
| 89 |
|
| default: |
| 90 |
0 |
| makemap_addi(quant, imgs, count); |
| 91 |
0 |
| break; |
| 92 |
|
| } |
| 93 |
|
| } |
| 94 |
|
| |
| 95 |
|
| static void translate_closest(i_quantize *, i_img *, i_palidx *); |
| 96 |
|
| static int translate_errdiff(i_quantize *, i_img *, i_palidx *); |
| 97 |
|
| static void translate_addi(i_quantize *, i_img *, i_palidx *); |
| 98 |
|
| |
| 99 |
|
| /* |
| 100 |
|
| =item i_quant_translate(C<quant>, C<img>) |
| 101 |
|
| |
| 102 |
|
| =category Image quantization |
| 103 |
|
| |
| 104 |
|
| Quantize the image given the palette in C<quant>. |
| 105 |
|
| |
| 106 |
|
| On success returns a pointer to a memory block of C<< img->xsize * |
| 107 |
|
| img->ysize >> C<i_palidx> entries. |
| 108 |
|
| |
| 109 |
|
| On failure returns NULL. |
| 110 |
|
| |
| 111 |
|
| You should call myfree() on the returned block when you're done with |
| 112 |
|
| it. |
| 113 |
|
| |
| 114 |
|
| This function will fail if the supplied palette contains no colors. |
| 115 |
|
| |
| 116 |
|
| =cut |
| 117 |
|
| */ |
| 118 |
|
| i_palidx * |
| 119 |
18 |
| i_quant_translate(i_quantize *quant, i_img *img) { |
| 120 |
|
| i_palidx *result; |
| 121 |
|
| size_t bytes; |
| 122 |
|
| |
| 123 |
18 |
| mm_log((1, "quant_translate(quant %p, img %p)\n", quant, img)); |
| 124 |
|
| |
| 125 |
|
| /* there must be at least one color in the paletted (though even that |
| 126 |
|
| isn't very useful */ |
| 127 |
18 |
▶ | if (quant->mc_count == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (quant->mc_count == 0) { |
1 |
17 |
18 |
|
| 128 |
1 |
| i_push_error(0, "no colors available for translation"); |
| 129 |
1 |
| return NULL; |
| 130 |
|
| } |
| 131 |
|
| |
| 132 |
17 |
| bytes = (size_t)img->xsize * (size_t)img->ysize; |
| 133 |
17 |
▶ | if (bytes / img->ysize != (size_t)img->xsize) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (bytes / img->ysize != (size_t)img->xsize) { |
0 |
17 |
17 |
|
| 134 |
0 |
| i_push_error(0, "integer overflow calculating memory allocation"); |
| 135 |
0 |
| return NULL; |
| 136 |
|
| } |
| 137 |
17 |
| result = mymalloc(bytes); |
| 138 |
|
| |
| 139 |
17 |
| switch (quant->translate) { |
| 140 |
12 |
| case pt_closest: |
| 141 |
|
| case pt_giflib: |
| 142 |
12 |
| translate_closest(quant, img, result); |
| 143 |
12 |
| break; |
| 144 |
|
| |
| 145 |
5 |
| case pt_errdiff: |
| 146 |
5 |
▶ | if (!translate_errdiff(quant, img, result)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!translate_errdiff(quant, img, result)) { |
0 |
5 |
5 |
|
| 147 |
0 |
| myfree(result); |
| 148 |
0 |
| return NULL; |
| 149 |
|
| } |
| 150 |
5 |
| break; |
| 151 |
|
| |
| 152 |
0 |
| case pt_perturb: |
| 153 |
|
| default: |
| 154 |
0 |
| translate_addi(quant, img, result); |
| 155 |
0 |
| break; |
| 156 |
|
| } |
| 157 |
|
| |
| 158 |
17 |
| return result; |
| 159 |
|
| } |
| 160 |
|
| |
| 161 |
12 |
| static void translate_closest(i_quantize *quant, i_img *img, i_palidx *out) { |
| 162 |
12 |
| quant->perturb = 0; |
| 163 |
12 |
| translate_addi(quant, img, out); |
| 164 |
12 |
| } |
| 165 |
|
| |
| 166 |
|
| #define PWR2(x) ((x)*(x)) |
| 167 |
|
| |
| 168 |
|
| typedef int (*cmpfunc)(const void*, const void*); |
| 169 |
|
| |
| 170 |
|
| typedef struct { |
| 171 |
|
| unsigned char r,g,b; |
| 172 |
|
| char fixed; |
| 173 |
|
| char used; |
| 174 |
|
| int dr,dg,db; |
| 175 |
|
| int cdist; |
| 176 |
|
| int mcount; |
| 177 |
|
| } cvec; |
| 178 |
|
| |
| 179 |
|
| typedef struct { |
| 180 |
|
| int cnt; |
| 181 |
|
| int vec[256]; |
| 182 |
|
| } hashbox; |
| 183 |
|
| |
| 184 |
|
| typedef struct { |
| 185 |
|
| int boxnum; |
| 186 |
|
| int pixcnt; |
| 187 |
|
| int cand; |
| 188 |
|
| int pdc; |
| 189 |
|
| } pbox; |
| 190 |
|
| |
| 191 |
|
| static void prescan(i_img **im,int count, int cnum, cvec *clr, i_sample_t *line); |
| 192 |
|
| static void reorder(pbox prescan[512]); |
| 193 |
|
| static int pboxcmp(const pbox *a,const pbox *b); |
| 194 |
|
| static void boxcenter(int box,cvec *cv); |
| 195 |
|
| static float frandn(void); |
| 196 |
|
| static void boxrand(int box,cvec *cv); |
| 197 |
|
| static void bbox(int box,int *r0,int *r1,int *g0,int *g1,int *b0,int *b1); |
| 198 |
|
| static void cr_hashindex(cvec clr[256],int cnum,hashbox hb[512]); |
| 199 |
|
| static int mindist(int boxnum,cvec *cv); |
| 200 |
|
| static int maxdist(int boxnum,cvec *cv); |
| 201 |
|
| |
| 202 |
|
| /* Some of the simpler functions are kept here to aid the compiler - |
| 203 |
|
| maybe some of them will be inlined. */ |
| 204 |
|
| |
| 205 |
|
| static int |
| 206 |
296878 |
| pixbox(i_color *ic) { return ((ic->channel[0] & 224)<<1)+ ((ic->channel[1]&224)>>2) + ((ic->channel[2] &224) >> 5); } |
| 207 |
|
| |
| 208 |
|
| static int |
| 209 |
0 |
| pixbox_ch(i_sample_t *chans) { return ((chans[0] & 224)<<1)+ ((chans[1]&224)>>2) + ((chans[2] &224) >> 5); } |
| 210 |
|
| |
| 211 |
|
| static unsigned char |
| 212 |
270300 |
| g_sat(int in) { |
| 213 |
270300 |
▶ | if (in>255) { return 255; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (in>255) { return 255; } |
22380 |
247920 |
270300 |
|
| 214 |
247920 |
▶ | else if (in>0) return in; |
Branch: 1 branch
| Branch | True | False | Total |
| else if (in>0) return in; |
43265 |
204655 |
247920 |
|
| 215 |
204655 |
| return 0; |
| 216 |
|
| } |
| 217 |
|
| |
| 218 |
|
| static |
| 219 |
|
| float |
| 220 |
0 |
| frand(void) { |
| 221 |
0 |
| return rand()/(RAND_MAX+1.0); |
| 222 |
|
| } |
| 223 |
|
| |
| 224 |
|
| #ifdef NOTEF |
| 225 |
|
| static |
| 226 |
|
| int |
| 227 |
|
| eucl_d(cvec* cv,i_color *cl) { return PWR2(cv->r-cl->channel[0])+PWR2(cv->g-cl->channel[1])+PWR2(cv->b-cl->channel[2]); } |
| 228 |
|
| #endif |
| 229 |
|
| |
| 230 |
|
| static |
| 231 |
|
| int |
| 232 |
0 |
| eucl_d_ch(cvec* cv,i_sample_t *chans) { |
| 233 |
0 |
| return PWR2(cv->r - chans[0]) + PWR2(cv->g - chans[1]) |
| 234 |
0 |
| + PWR2(cv->b - chans[2]); |
| 235 |
|
| } |
| 236 |
|
| |
| 237 |
|
| static int |
| 238 |
2192846 |
| ceucl_d(i_color *c1, i_color *c2) { |
| 239 |
2192846 |
| return PWR2(c1->channel[0]-c2->channel[0]) |
| 240 |
2192846 |
| +PWR2(c1->channel[1]-c2->channel[1]) |
| 241 |
2192846 |
| +PWR2(c1->channel[2]-c2->channel[2]); |
| 242 |
|
| } |
| 243 |
|
| |
| 244 |
|
| static const int |
| 245 |
|
| gray_samples[] = { 0, 0, 0 }; |
| 246 |
|
| |
| 247 |
|
| /* |
| 248 |
|
| |
| 249 |
|
| This quantization algorithm and implementation routines are by Arnar |
| 250 |
|
| M. Hrafnkelson. In case any new ideas are here they are mine since |
| 251 |
|
| this was written from scratch. |
| 252 |
|
| |
| 253 |
|
| The algorithm uses local means in the following way: |
| 254 |
|
| |
| 255 |
|
| For each point in the colormap we find which image points |
| 256 |
|
| have that point as it's closest point. We calculate the mean |
| 257 |
|
| of those points and in the next iteration it will be the new |
| 258 |
|
| entry in the colormap. |
| 259 |
|
| |
| 260 |
|
| In order to speed this process up (i.e. nearest neighbor problem) We |
| 261 |
|
| divied the r,g,b space up in equally large 512 boxes. The boxes are |
| 262 |
|
| numbered from 0 to 511. Their numbering is so that for a given vector |
| 263 |
|
| it is known that it belongs to the box who is formed by concatenating the |
| 264 |
|
| 3 most significant bits from each component of the RGB triplet. |
| 265 |
|
| |
| 266 |
|
| For each box we find the list of points from the colormap who might be |
| 267 |
|
| closest to any given point within the box. The exact solution |
| 268 |
|
| involves finding the Voronoi map (or the dual the Delauny |
| 269 |
|
| triangulation) and has many issues including numerical stability. |
| 270 |
|
| |
| 271 |
|
| So we use this approximation: |
| 272 |
|
| |
| 273 |
|
| 1. Find which point has the shortest maximum distance to the box. |
| 274 |
|
| 2. Find all points that have a shorter minimum distance than that to the box |
| 275 |
|
| |
| 276 |
|
| This is a very simple task and is not computationally heavy if one |
| 277 |
|
| takes into account that the minimum distances from a pixel to a box is |
| 278 |
|
| always found by checking if it's inside the box or is closest to some |
| 279 |
|
| side or a corner. Finding the maximum distance is also either a side |
| 280 |
|
| or a corner. |
| 281 |
|
| |
| 282 |
|
| This approach results 2-3 times more than the actual points needed but |
| 283 |
|
| is still a good gain over the complete space. Usually when one has a |
| 284 |
|
| 256 Colorcolor map a search over 30 is often obtained. |
| 285 |
|
| |
| 286 |
|
| A bit of an enhancement to this approach is to keep a seperate list |
| 287 |
|
| for each side of the cube, but this will require even more memory. |
| 288 |
|
| |
| 289 |
|
| Arnar M. Hrafnkelsson (addi@umich.edu); |
| 290 |
|
| |
| 291 |
|
| */ |
| 292 |
|
| /* |
| 293 |
|
| Extracted from gifquant.c, removed dependencies on gif_lib, |
| 294 |
|
| and added support for multiple images. |
| 295 |
|
| starting from 1nov2000 by TonyC <tony@develop-help.com>. |
| 296 |
|
| |
| 297 |
|
| */ |
| 298 |
|
| |
| 299 |
|
| static void |
| 300 |
0 |
| makemap_addi(i_quantize *quant, i_img **imgs, int count) { |
| 301 |
|
| cvec *clr; |
| 302 |
0 |
| int cnum, i, bst_idx=0, ld, cd, iter, currhb, img_num; |
| 303 |
|
| i_img_dim x, y; |
| 304 |
|
| i_sample_t *val; |
| 305 |
|
| float dlt; |
| 306 |
|
| hashbox *hb; |
| 307 |
|
| i_mempool mp; |
| 308 |
0 |
| i_img_dim maxwidth = 0; |
| 309 |
|
| i_sample_t *line; |
| 310 |
|
| const int *sample_indices; |
| 311 |
|
| |
| 312 |
0 |
| mm_log((1, "makemap_addi(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n", |
| 313 |
|
| quant, quant->mc_count, quant->mc_colors, imgs, count)); |
| 314 |
|
| |
| 315 |
0 |
▶ | if (makemap_palette(quant, imgs, count)) |
Branch: 1 branch
| Branch | True | False | Total |
| if (makemap_palette(quant, imgs, count)) |
0 |
0 |
0 |
|
| 316 |
0 |
| return; |
| 317 |
|
| |
| 318 |
0 |
| i_mempool_init(&mp); |
| 319 |
|
| |
| 320 |
0 |
| clr = i_mempool_alloc(&mp, sizeof(cvec) * quant->mc_size); |
| 321 |
0 |
| hb = i_mempool_alloc(&mp, sizeof(hashbox) * 512); |
| 322 |
0 |
▶ | for (i=0; i < quant->mc_count; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i=0; i < quant->mc_count; ++i) { |
0 |
0 |
0 |
|
| 323 |
0 |
| clr[i].r = quant->mc_colors[i].rgb.r; |
| 324 |
0 |
| clr[i].g = quant->mc_colors[i].rgb.g; |
| 325 |
0 |
| clr[i].b = quant->mc_colors[i].rgb.b; |
| 326 |
0 |
| clr[i].fixed = 1; |
| 327 |
0 |
| clr[i].mcount = 0; |
| 328 |
|
| } |
| 329 |
|
| /* mymalloc doesn't clear memory, so I think we need this */ |
| 330 |
0 |
▶ | for (; i < quant->mc_size; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (; i < quant->mc_size; ++i) { |
0 |
0 |
0 |
|
| 331 |
|
| /*clr[i].r = clr[i].g = clr[i].b = 0;*/ |
| 332 |
0 |
| clr[i].dr = 0; |
| 333 |
0 |
| clr[i].dg = 0; |
| 334 |
0 |
| clr[i].db = 0; |
| 335 |
0 |
| clr[i].fixed = 0; |
| 336 |
0 |
| clr[i].mcount = 0; |
| 337 |
|
| } |
| 338 |
0 |
| cnum = quant->mc_size; |
| 339 |
0 |
| dlt = 1; |
| 340 |
|
| |
| 341 |
0 |
▶ | for (img_num = 0; img_num < count; ++img_num) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (img_num = 0; img_num < count; ++img_num) { |
0 |
0 |
0 |
|
| 342 |
0 |
▶ | if (imgs[img_num]->xsize > maxwidth) |
Branch: 1 branch
| Branch | True | False | Total |
| if (imgs[img_num]->xsize > maxwidth) |
0 |
0 |
0 |
|
| 343 |
0 |
| maxwidth = imgs[img_num]->xsize; |
| 344 |
|
| } |
| 345 |
0 |
| line = i_mempool_alloc(&mp, 3 * maxwidth * sizeof(*line)); |
| 346 |
|
| |
| 347 |
0 |
| prescan(imgs, count, cnum, clr, line); |
| 348 |
0 |
| cr_hashindex(clr, cnum, hb); |
| 349 |
|
| |
| 350 |
0 |
▶ | for(iter=0;iter<3;iter++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(iter=0;iter<3;iter++) { |
0 |
0 |
0 |
|
| 351 |
0 |
▶ | for (img_num = 0; img_num < count; ++img_num) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (img_num = 0; img_num < count; ++img_num) { |
0 |
0 |
0 |
|
| 352 |
0 |
| i_img *im = imgs[img_num]; |
| 353 |
0 |
▶ | sample_indices = im->channels >= 3 ? NULL : gray_samples; |
Branch: 1 branch
| Branch | True | False | Total |
| sample_indices = im->channels >= 3 ? NULL : gray_samples; |
0 |
0 |
0 |
|
| 354 |
0 |
▶ | for(y=0;y<im->ysize;y++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(y=0;y<im->ysize;y++) { |
0 |
0 |
0 |
|
| 355 |
0 |
| i_gsamp(im, 0, im->xsize, y, line, sample_indices, 3); |
| 356 |
0 |
| val = line; |
| 357 |
0 |
▶ | for(x=0;x<im->xsize;x++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(x=0;x<im->xsize;x++) { |
0 |
0 |
0 |
|
| 358 |
0 |
| ld=196608; |
| 359 |
|
| /*i_gpix(im,x,y,&val);*/ |
| 360 |
0 |
| currhb=pixbox_ch(val); |
| 361 |
|
| /* printf("box = %d \n",currhb); */ |
| 362 |
0 |
▶ | for(i=0;i<hb[currhb].cnt;i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(i=0;i<hb[currhb].cnt;i++) { |
0 |
0 |
0 |
|
| 363 |
|
| /* printf("comparing: pix (%d,%d,%d) vec (%d,%d,%d)\n",val.channel[0],val.channel[1],val.channel[2],clr[hb[currhb].vec[i]].r,clr[hb[currhb].vec[i]].g,clr[hb[currhb].vec[i]].b); */ |
| 364 |
|
| |
| 365 |
0 |
| cd=eucl_d_ch(&clr[hb[currhb].vec[i]],val); |
| 366 |
0 |
▶ | if (cd<ld) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (cd<ld) { |
0 |
0 |
0 |
|
| 367 |
0 |
| ld=cd; /* shortest distance yet */ |
| 368 |
0 |
| bst_idx=hb[currhb].vec[i]; /* index of closest vector yet */ |
| 369 |
|
| } |
| 370 |
|
| } |
| 371 |
|
| |
| 372 |
0 |
| clr[bst_idx].mcount++; |
| 373 |
0 |
| clr[bst_idx].dr+=val[0]; |
| 374 |
0 |
| clr[bst_idx].dg+=val[1]; |
| 375 |
0 |
| clr[bst_idx].db+=val[2]; |
| 376 |
|
| |
| 377 |
0 |
| val += 3; /* next 3 samples (next pixel) */ |
| 378 |
|
| } |
| 379 |
|
| } |
| 380 |
|
| } |
| 381 |
|
| |
| 382 |
0 |
▶ | for(i=0;i<cnum;i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for(i=0;i<cnum;i++) |
0 |
0 |
0 |
|
| 383 |
0 |
▶ | if (clr[i].mcount) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (clr[i].mcount) { |
0 |
0 |
0 |
|
| 384 |
0 |
| clr[i].dr/=clr[i].mcount; |
| 385 |
0 |
| clr[i].dg/=clr[i].mcount; |
| 386 |
0 |
| clr[i].db/=clr[i].mcount; |
| 387 |
|
| } |
| 388 |
|
| |
| 389 |
|
| /* for(i=0;i<cnum;i++) printf("vec(%d)=(%d,%d,%d) dest=(%d,%d,%d) matchcount=%d\n", |
| 390 |
|
| i,clr[i].r,clr[i].g,clr[i].b,clr[i].dr,clr[i].dg,clr[i].db,clr[i].mcount); */ |
| 391 |
|
| |
| 392 |
|
| /* printf("total error: %.2f\n",sqrt(accerr)); */ |
| 393 |
|
| |
| 394 |
0 |
▶ | for(i=0;i<cnum;i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(i=0;i<cnum;i++) { |
0 |
0 |
0 |
|
| 395 |
0 |
▶ | if (clr[i].fixed) continue; /* skip reserved colors */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (clr[i].fixed) continue; /* skip reserved colors */ |
0 |
0 |
0 |
|
| 396 |
|
| |
| 397 |
0 |
▶ | if (clr[i].mcount) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (clr[i].mcount) { |
0 |
0 |
0 |
|
| 398 |
0 |
| clr[i].used = 1; |
| 399 |
0 |
| clr[i].r=clr[i].r*(1-dlt)+dlt*clr[i].dr; |
| 400 |
0 |
| clr[i].g=clr[i].g*(1-dlt)+dlt*clr[i].dg; |
| 401 |
0 |
| clr[i].b=clr[i].b*(1-dlt)+dlt*clr[i].db; |
| 402 |
|
| } else { |
| 403 |
|
| /* let's try something else */ |
| 404 |
0 |
| clr[i].used = 0; |
| 405 |
|
| /* the " & 0xFF" prevents "uncontrolled value" warnings from CodeQL */ |
| 406 |
0 |
| clr[i].r = rand() & 0xFF; |
| 407 |
0 |
| clr[i].g = rand() & 0xFF; |
| 408 |
0 |
| clr[i].b = rand() & 0xFF; |
| 409 |
|
| } |
| 410 |
|
| |
| 411 |
0 |
| clr[i].dr=0; |
| 412 |
0 |
| clr[i].dg=0; |
| 413 |
0 |
| clr[i].db=0; |
| 414 |
0 |
| clr[i].mcount=0; |
| 415 |
|
| } |
| 416 |
0 |
| cr_hashindex(clr,cnum,hb); |
| 417 |
|
| } |
| 418 |
|
| |
| 419 |
|
| |
| 420 |
|
| #ifdef NOTEF |
| 421 |
|
| for(i=0;i<cnum;i++) { |
| 422 |
|
| cd=eucl_d(&clr[i],&val); |
| 423 |
|
| if (cd<ld) { |
| 424 |
|
| ld=cd; |
| 425 |
|
| bst_idx=i; |
| 426 |
|
| } |
| 427 |
|
| } |
| 428 |
|
| #endif |
| 429 |
|
| |
| 430 |
|
| /* if defined, we only include colours with an mcount or that were |
| 431 |
|
| supplied in the fixed palette, giving us a smaller output palette */ |
| 432 |
|
| #define ONLY_USE_USED |
| 433 |
|
| #ifdef ONLY_USE_USED |
| 434 |
|
| /* transfer the colors back */ |
| 435 |
0 |
| quant->mc_count = 0; |
| 436 |
0 |
▶ | for (i = 0; i < cnum; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < cnum; ++i) { |
0 |
0 |
0 |
|
| 437 |
0 |
▶ | if (clr[i].fixed || clr[i].used) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (clr[i].fixed || clr[i].used) { |
0 |
0 |
0 |
| if (clr[i].fixed || clr[i].used) { |
0 |
0 |
0 |
|
| 438 |
|
| /*printf("Adding %d (%d,%d,%d)\n", i, clr[i].r, clr[i].g, clr[i].b);*/ |
| 439 |
0 |
| quant->mc_colors[quant->mc_count].rgb.r = clr[i].r; |
| 440 |
0 |
| quant->mc_colors[quant->mc_count].rgb.g = clr[i].g; |
| 441 |
0 |
| quant->mc_colors[quant->mc_count].rgb.b = clr[i].b; |
| 442 |
0 |
| ++quant->mc_count; |
| 443 |
|
| } |
| 444 |
|
| } |
| 445 |
|
| #else |
| 446 |
|
| /* transfer the colors back */ |
| 447 |
|
| for (i = 0; i < cnum; ++i) { |
| 448 |
|
| quant->mc_colors[i].rgb.r = clr[i].r; |
| 449 |
|
| quant->mc_colors[i].rgb.g = clr[i].g; |
| 450 |
|
| quant->mc_colors[i].rgb.b = clr[i].b; |
| 451 |
|
| } |
| 452 |
|
| quant->mc_count = cnum; |
| 453 |
|
| #endif |
| 454 |
|
| |
| 455 |
|
| #if 0 |
| 456 |
|
| mm_log((1, "makemap_addi returns - quant.mc_count = %d\n", quant->mc_count)); |
| 457 |
|
| for (i = 0; i < quant->mc_count; ++i) |
| 458 |
|
| mm_log((5, " map entry %d: (%d, %d, %d)\n", i, clr[i].r, clr[i].g, clr[i].b)); |
| 459 |
|
| #endif |
| 460 |
|
| |
| 461 |
0 |
| i_mempool_destroy(&mp); |
| 462 |
|
| |
| 463 |
0 |
| mm_log((1, "makemap_addi() - %d colors\n", quant->mc_count)); |
| 464 |
|
| } |
| 465 |
|
| |
| 466 |
|
| typedef struct { |
| 467 |
|
| i_sample_t rgb[3]; |
| 468 |
|
| i_img_dim count; |
| 469 |
|
| } quant_color_entry; |
| 470 |
|
| |
| 471 |
|
| #define MEDIAN_CUT_COLORS 32768 |
| 472 |
|
| |
| 473 |
|
| #define MED_CUT_INDEX(c) ((((c).rgb.r & 0xF8) << 7) | \ |
| 474 |
|
| (((c).rgb.g & 0xF8) << 2) | (((c).rgb.b & 0xF8) >> 3)) |
| 475 |
|
| |
| 476 |
|
| #define MED_CUT_GRAY_INDEX(c) ((((c).rgb.r & 0xF8) << 7) | \ |
| 477 |
|
| (((c).rgb.r & 0xF8) << 2) | (((c).rgb.r & 0xF8) >> 3)) |
| 478 |
|
| |
| 479 |
|
| /* scale these to cover the whole range */ |
| 480 |
|
| #define MED_CUT_RED(index) ((((index) & 0x7C00) >> 10) * 255 / 31) |
| 481 |
|
| #define MED_CUT_GREEN(index) ((((index) & 0x3E0) >> 5) * 255 / 31) |
| 482 |
|
| #define MED_CUT_BLUE(index) (((index) & 0x1F) * 255 / 31) |
| 483 |
|
| |
| 484 |
|
| typedef struct { |
| 485 |
|
| i_sample_t min[3]; /* minimum for each channel */ |
| 486 |
|
| i_sample_t max[3]; /* maximum for each channel */ |
| 487 |
|
| i_sample_t width[3]; /* width for each channel */ |
| 488 |
|
| int start, size; /* beginning and size of the partition */ |
| 489 |
|
| i_img_dim pixels; /* number of pixels represented by this partition */ |
| 490 |
|
| } medcut_partition; |
| 491 |
|
| |
| 492 |
|
| /* |
| 493 |
|
| =item calc_part(part, colors) |
| 494 |
|
| |
| 495 |
|
| Calculates the new color limits for the given partition. |
| 496 |
|
| |
| 497 |
|
| Giflib assumes that the limits for the non-split channels stay the |
| 498 |
|
| same, but this strikes me as incorrect, especially if the colors tend |
| 499 |
|
| to be color ramps. |
| 500 |
|
| |
| 501 |
|
| Of course this could be optimized by not recalculating the channel we |
| 502 |
|
| just sorted on, but it's not worth the effort right now. |
| 503 |
|
| |
| 504 |
|
| =cut |
| 505 |
|
| */ |
| 506 |
0 |
| static void calc_part(medcut_partition *part, quant_color_entry *colors) { |
| 507 |
|
| int i, ch; |
| 508 |
|
| |
| 509 |
0 |
▶ | for (ch = 0; ch < 3; ++ch) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (ch = 0; ch < 3; ++ch) { |
0 |
0 |
0 |
|
| 510 |
0 |
| part->min[ch] = 255; |
| 511 |
0 |
| part->max[ch] = 0; |
| 512 |
|
| } |
| 513 |
0 |
▶ | for (i = part->start; i < part->start + part->size; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = part->start; i < part->start + part->size; ++i) { |
0 |
0 |
0 |
|
| 514 |
0 |
▶ | for (ch = 0; ch < 3; ++ch) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (ch = 0; ch < 3; ++ch) { |
0 |
0 |
0 |
|
| 515 |
0 |
▶ | if (part->min[ch] > colors[i].rgb[ch]) |
Branch: 1 branch
| Branch | True | False | Total |
| if (part->min[ch] > colors[i].rgb[ch]) |
0 |
0 |
0 |
|
| 516 |
0 |
| part->min[ch] = colors[i].rgb[ch]; |
| 517 |
0 |
▶ | if (part->max[ch] < colors[i].rgb[ch]) |
Branch: 1 branch
| Branch | True | False | Total |
| if (part->max[ch] < colors[i].rgb[ch]) |
0 |
0 |
0 |
|
| 518 |
0 |
| part->max[ch] = colors[i].rgb[ch]; |
| 519 |
|
| } |
| 520 |
|
| } |
| 521 |
0 |
▶ | for (ch = 0; ch < 3; ++ch) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (ch = 0; ch < 3; ++ch) { |
0 |
0 |
0 |
|
| 522 |
0 |
| part->width[ch] = part->max[ch] - part->min[ch]; |
| 523 |
|
| } |
| 524 |
0 |
| } |
| 525 |
|
| |
| 526 |
|
| /* simple functions to sort by each channel - we could use a global, but |
| 527 |
|
| that would be bad */ |
| 528 |
|
| |
| 529 |
|
| static int |
| 530 |
0 |
| color_sort_red(void const *left, void const *right) { |
| 531 |
0 |
| return ((quant_color_entry *)left)->rgb[0] - ((quant_color_entry *)right)->rgb[0]; |
| 532 |
|
| } |
| 533 |
|
| |
| 534 |
|
| static int |
| 535 |
0 |
| color_sort_green(void const *left, void const *right) { |
| 536 |
0 |
| return ((quant_color_entry *)left)->rgb[1] - ((quant_color_entry *)right)->rgb[1]; |
| 537 |
|
| } |
| 538 |
|
| |
| 539 |
|
| static int |
| 540 |
0 |
| color_sort_blue(void const *left, void const *right) { |
| 541 |
0 |
| return ((quant_color_entry *)left)->rgb[2] - ((quant_color_entry *)right)->rgb[2]; |
| 542 |
|
| } |
| 543 |
|
| |
| 544 |
|
| static int (*sorters[])(void const *, void const *) = |
| 545 |
|
| { |
| 546 |
|
| color_sort_red, |
| 547 |
|
| color_sort_green, |
| 548 |
|
| color_sort_blue, |
| 549 |
|
| }; |
| 550 |
|
| |
| 551 |
|
| static void |
| 552 |
5 |
| makemap_mediancut(i_quantize *quant, i_img **imgs, int count) { |
| 553 |
|
| quant_color_entry *colors; |
| 554 |
|
| i_mempool mp; |
| 555 |
|
| int imgn, i, ch; |
| 556 |
|
| i_img_dim x, y, max_width; |
| 557 |
|
| i_color *line; |
| 558 |
|
| int color_count; |
| 559 |
|
| i_img_dim total_pixels; |
| 560 |
|
| medcut_partition *parts; |
| 561 |
|
| int part_num; |
| 562 |
|
| int in, out; |
| 563 |
|
| /* number of channels we search for the best channel to partition |
| 564 |
|
| this isn't terribly efficient, but it should work */ |
| 565 |
|
| int chan_count; |
| 566 |
|
| |
| 567 |
5 |
| mm_log((1, "makemap_mediancut(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n", |
| 568 |
|
| quant, quant->mc_count, quant->mc_colors, imgs, count)); |
| 569 |
|
| |
| 570 |
5 |
▶ | if (makemap_palette(quant, imgs, count)) |
Branch: 1 branch
| Branch | True | False | Total |
| if (makemap_palette(quant, imgs, count)) |
0 |
5 |
5 |
|
| 571 |
0 |
| return; |
| 572 |
|
| |
| 573 |
5 |
| i_mempool_init(&mp); |
| 574 |
|
| |
| 575 |
5 |
| colors = i_mempool_alloc(&mp, sizeof(*colors) * MEDIAN_CUT_COLORS); |
| 576 |
163845 |
▶ | for (i = 0; i < MEDIAN_CUT_COLORS; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < MEDIAN_CUT_COLORS; ++i) { |
163840 |
5 |
163845 |
|
| 577 |
163840 |
| colors[i].rgb[0] = MED_CUT_RED(i); |
| 578 |
163840 |
| colors[i].rgb[1] = MED_CUT_GREEN(i); |
| 579 |
163840 |
| colors[i].rgb[2] = MED_CUT_BLUE(i); |
| 580 |
163840 |
| colors[i].count = 0; |
| 581 |
|
| } |
| 582 |
|
| |
| 583 |
5 |
| max_width = -1; |
| 584 |
10 |
▶ | for (imgn = 0; imgn < count; ++imgn) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (imgn = 0; imgn < count; ++imgn) { |
5 |
5 |
10 |
|
| 585 |
5 |
▶ | if (imgs[imgn]->xsize > max_width) |
Branch: 1 branch
| Branch | True | False | Total |
| if (imgs[imgn]->xsize > max_width) |
5 |
0 |
5 |
|
| 586 |
5 |
| max_width = imgs[imgn]->xsize; |
| 587 |
|
| } |
| 588 |
5 |
| line = i_mempool_alloc(&mp, sizeof(i_color) * max_width); |
| 589 |
|
| |
| 590 |
|
| /* build the stats */ |
| 591 |
5 |
| total_pixels = 0; |
| 592 |
5 |
| chan_count = 1; /* assume we just have grayscale */ |
| 593 |
10 |
▶ | for (imgn = 0; imgn < count; ++imgn) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (imgn = 0; imgn < count; ++imgn) { |
5 |
5 |
10 |
|
| 594 |
5 |
| total_pixels += imgs[imgn]->xsize * imgs[imgn]->ysize; |
| 595 |
452 |
▶ | for (y = 0; y < imgs[imgn]->ysize; ++y) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (y = 0; y < imgs[imgn]->ysize; ++y) { |
447 |
5 |
452 |
|
| 596 |
447 |
| i_glin(imgs[imgn], 0, imgs[imgn]->xsize, y, line); |
| 597 |
447 |
▶ | if (imgs[imgn]->channels > 2) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (imgs[imgn]->channels > 2) { |
447 |
0 |
447 |
|
| 598 |
447 |
| chan_count = 3; |
| 599 |
58121 |
▶ | for (x = 0; x < imgs[imgn]->xsize; ++x) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (x = 0; x < imgs[imgn]->xsize; ++x) { |
57674 |
447 |
58121 |
|
| 600 |
57674 |
| ++colors[MED_CUT_INDEX(line[x])].count; |
| 601 |
|
| } |
| 602 |
|
| } |
| 603 |
|
| else { |
| 604 |
|
| /* a gray-scale image, just use the first channel */ |
| 605 |
0 |
▶ | for (x = 0; x < imgs[imgn]->xsize; ++x) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (x = 0; x < imgs[imgn]->xsize; ++x) { |
0 |
0 |
0 |
|
| 606 |
0 |
| ++colors[MED_CUT_GRAY_INDEX(line[x])].count; |
| 607 |
|
| } |
| 608 |
|
| } |
| 609 |
|
| } |
| 610 |
|
| } |
| 611 |
|
| |
| 612 |
|
| /* eliminate the empty colors */ |
| 613 |
5 |
| out = 0; |
| 614 |
163845 |
▶ | for (in = 0; in < MEDIAN_CUT_COLORS; ++in) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (in = 0; in < MEDIAN_CUT_COLORS; ++in) { |
163840 |
5 |
163845 |
|
| 615 |
163840 |
▶ | if (colors[in].count) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (colors[in].count) { |
374 |
163466 |
163840 |
|
| 616 |
374 |
| colors[out++] = colors[in]; |
| 617 |
|
| } |
| 618 |
|
| } |
| 619 |
|
| /*printf("out %d\n", out); |
| 620 |
|
| |
| 621 |
|
| for (i = 0; i < out; ++i) { |
| 622 |
|
| if (colors[i].count) { |
| 623 |
|
| printf("%d: (%d,%d,%d) -> %d\n", i, colors[i].rgb[0], colors[i].rgb[1], |
| 624 |
|
| colors[i].rgb[2], colors[i].count); |
| 625 |
|
| } |
| 626 |
|
| }*/ |
| 627 |
|
| |
| 628 |
5 |
▶ | if (out < quant->mc_size) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (out < quant->mc_size) { |
5 |
0 |
5 |
|
| 629 |
|
| /* just copy them into the color table */ |
| 630 |
379 |
▶ | for (i = 0; i < out; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < out; ++i) { |
374 |
5 |
379 |
|
| 631 |
1496 |
▶ | for (ch = 0; ch < 3; ++ch) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (ch = 0; ch < 3; ++ch) { |
1122 |
374 |
1496 |
|
| 632 |
1122 |
| quant->mc_colors[i].channel[ch] = colors[i].rgb[ch]; |
| 633 |
|
| } |
| 634 |
374 |
| quant->mc_colors[i].rgba.a = 255; |
| 635 |
|
| } |
| 636 |
5 |
| quant->mc_count = out; |
| 637 |
|
| } |
| 638 |
|
| else { |
| 639 |
|
| /* build the starting partition */ |
| 640 |
0 |
| parts = i_mempool_alloc(&mp, sizeof(*parts) * quant->mc_size); |
| 641 |
0 |
| parts[0].start = 0; |
| 642 |
0 |
| parts[0].size = out; |
| 643 |
0 |
| parts[0].pixels = total_pixels; |
| 644 |
0 |
| calc_part(parts, colors); |
| 645 |
0 |
| color_count = 1; |
| 646 |
|
| |
| 647 |
0 |
▶ | while (color_count < quant->mc_size) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (color_count < quant->mc_size) { |
0 |
0 |
0 |
|
| 648 |
|
| /* initialized to avoid compiler warnings */ |
| 649 |
0 |
| int max_index = 0, max_ch = 0; /* index/channel with biggest spread */ |
| 650 |
|
| int max_size; |
| 651 |
|
| medcut_partition *workpart; |
| 652 |
|
| i_img_dim cum_total; |
| 653 |
|
| i_img_dim half; |
| 654 |
|
| |
| 655 |
|
| /* find the partition with the most biggest span with more than |
| 656 |
|
| one color */ |
| 657 |
0 |
| max_size = -1; |
| 658 |
0 |
▶ | for (i = 0; i < color_count; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < color_count; ++i) { |
0 |
0 |
0 |
|
| 659 |
0 |
▶ | for (ch = 0; ch < chan_count; ++ch) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (ch = 0; ch < chan_count; ++ch) { |
0 |
0 |
0 |
|
| 660 |
0 |
▶ | if (parts[i].width[ch] > max_size |
Branch: 1 branch
| Branch | True | False | Total |
| if (parts[i].width[ch] > max_size |
0 |
0 |
0 |
|
| 661 |
0 |
▶ | && parts[i].size > 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| && parts[i].size > 1) { |
0 |
0 |
0 |
|
| 662 |
0 |
| max_index = i; |
| 663 |
0 |
| max_ch = ch; |
| 664 |
0 |
| max_size = parts[i].width[ch]; |
| 665 |
|
| } |
| 666 |
|
| } |
| 667 |
|
| } |
| 668 |
|
| |
| 669 |
|
| /* nothing else we can split */ |
| 670 |
0 |
▶ | if (max_size == -1) |
Branch: 1 branch
| Branch | True | False | Total |
| if (max_size == -1) |
0 |
0 |
0 |
|
| 671 |
0 |
| break; |
| 672 |
|
| |
| 673 |
0 |
| workpart = parts+max_index; |
| 674 |
|
| /*printf("splitting partition %d (pixels %ld, start %d, size %d)\n", max_index, workpart->pixels, workpart->start, workpart->size);*/ |
| 675 |
0 |
| qsort(colors + workpart->start, workpart->size, sizeof(*colors), |
| 676 |
|
| sorters[max_ch]); |
| 677 |
|
| |
| 678 |
|
| /* find the median or something like it we need to make sure both |
| 679 |
|
| sides of the split have at least one color in them, so we don't |
| 680 |
|
| test at the first or last entry */ |
| 681 |
0 |
| i = workpart->start; |
| 682 |
0 |
| cum_total = colors[i].count; |
| 683 |
0 |
| ++i; |
| 684 |
0 |
| half = workpart->pixels / 2; |
| 685 |
0 |
| while (i < workpart->start + workpart->size - 1 |
| 686 |
0 |
▶ | && cum_total < half) { |
Branch: 2 branches
| Branch | True | False | Total |
| && cum_total < half) { |
0 |
0 |
0 |
| && cum_total < half) { |
0 |
0 |
0 |
|
| 687 |
0 |
| cum_total += colors[i++].count; |
| 688 |
|
| } |
| 689 |
|
| /*printf("Split at %d to make %d (half %ld, cumtotal %ld)\n", i, color_count, half, cum_total);*/ |
| 690 |
|
| |
| 691 |
|
| /* found the spot to split */ |
| 692 |
0 |
| parts[color_count].start = i; |
| 693 |
0 |
| parts[color_count].size = workpart->start + workpart->size - i; |
| 694 |
0 |
| workpart->size = i - workpart->start; |
| 695 |
0 |
| parts[color_count].pixels = workpart->pixels - cum_total; |
| 696 |
0 |
| workpart->pixels = cum_total; |
| 697 |
|
| |
| 698 |
|
| /* recalculate the limits */ |
| 699 |
0 |
| calc_part(workpart, colors); |
| 700 |
0 |
| calc_part(parts+color_count, colors); |
| 701 |
0 |
| ++color_count; |
| 702 |
|
| } |
| 703 |
|
| |
| 704 |
|
| /* fill in the color table - since we could still have partitions |
| 705 |
|
| that have more than one color, we need to average the colors */ |
| 706 |
0 |
▶ | for (part_num = 0; part_num < color_count; ++part_num) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (part_num = 0; part_num < color_count; ++part_num) { |
0 |
0 |
0 |
|
| 707 |
|
| double sums[3]; |
| 708 |
|
| medcut_partition *workpart; |
| 709 |
|
| |
| 710 |
0 |
| workpart = parts+part_num; |
| 711 |
0 |
▶ | for (ch = 0; ch < 3; ++ch) |
Branch: 1 branch
| Branch | True | False | Total |
| for (ch = 0; ch < 3; ++ch) |
0 |
0 |
0 |
|
| 712 |
0 |
| sums[ch] = 0; |
| 713 |
|
| |
| 714 |
0 |
▶ | for (i = workpart->start; i < workpart->start + workpart->size; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = workpart->start; i < workpart->start + workpart->size; ++i) { |
0 |
0 |
0 |
|
| 715 |
0 |
▶ | for (ch = 0; ch < 3; ++ch) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (ch = 0; ch < 3; ++ch) { |
0 |
0 |
0 |
|
| 716 |
0 |
| sums[ch] += (int)(colors[i].rgb[ch]) * colors[i].count; |
| 717 |
|
| } |
| 718 |
|
| } |
| 719 |
0 |
▶ | for (ch = 0; ch < 3; ++ch) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (ch = 0; ch < 3; ++ch) { |
0 |
0 |
0 |
|
| 720 |
0 |
| quant->mc_colors[part_num].channel[ch] = sums[ch] / workpart->pixels; |
| 721 |
|
| } |
| 722 |
0 |
| quant->mc_colors[part_num].rgba.a = 255; |
| 723 |
|
| } |
| 724 |
0 |
| quant->mc_count = color_count; |
| 725 |
|
| } |
| 726 |
|
| /*printf("out %d colors\n", quant->mc_count);*/ |
| 727 |
5 |
| i_mempool_destroy(&mp); |
| 728 |
|
| |
| 729 |
5 |
| mm_log((1, "makemap_mediancut() - %d colors\n", quant->mc_count)); |
| 730 |
|
| } |
| 731 |
|
| |
| 732 |
|
| static void |
| 733 |
3 |
| makemap_mono(i_quantize *quant) { |
| 734 |
3 |
| quant->mc_colors[0].rgba.r = 0; |
| 735 |
3 |
| quant->mc_colors[0].rgba.g = 0; |
| 736 |
3 |
| quant->mc_colors[0].rgba.b = 0; |
| 737 |
3 |
| quant->mc_colors[0].rgba.a = 255; |
| 738 |
3 |
| quant->mc_colors[1].rgba.r = 255; |
| 739 |
3 |
| quant->mc_colors[1].rgba.g = 255; |
| 740 |
3 |
| quant->mc_colors[1].rgba.b = 255; |
| 741 |
3 |
| quant->mc_colors[1].rgba.a = 255; |
| 742 |
3 |
| quant->mc_count = 2; |
| 743 |
3 |
| } |
| 744 |
|
| |
| 745 |
|
| static void |
| 746 |
3 |
| makemap_gray(i_quantize *quant, int step) { |
| 747 |
3 |
| int gray = 0; |
| 748 |
3 |
| int i = 0; |
| 749 |
|
| |
| 750 |
279 |
▶ | while (gray < 256) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (gray < 256) { |
276 |
3 |
279 |
|
| 751 |
276 |
| setcol(quant->mc_colors+i, gray, gray, gray, 255); |
| 752 |
276 |
| ++i; |
| 753 |
276 |
| gray += step; |
| 754 |
|
| } |
| 755 |
3 |
| quant->mc_count = i; |
| 756 |
3 |
| } |
| 757 |
|
| |
| 758 |
|
| static void |
| 759 |
4 |
| makemap_webmap(i_quantize *quant) { |
| 760 |
|
| int r, g, b; |
| 761 |
|
| |
| 762 |
4 |
| int i = 0; |
| 763 |
28 |
▶ | for (r = 0; r < 256; r+=0x33) |
Branch: 1 branch
| Branch | True | False | Total |
| for (r = 0; r < 256; r+=0x33) |
24 |
4 |
28 |
|
| 764 |
168 |
▶ | for (g = 0; g < 256; g+=0x33) |
Branch: 1 branch
| Branch | True | False | Total |
| for (g = 0; g < 256; g+=0x33) |
144 |
24 |
168 |
|
| 765 |
1008 |
▶ | for (b = 0; b < 256; b += 0x33) |
Branch: 1 branch
| Branch | True | False | Total |
| for (b = 0; b < 256; b += 0x33) |
864 |
144 |
1008 |
|
| 766 |
864 |
| setcol(quant->mc_colors+i++, r, g, b, 255); |
| 767 |
4 |
| quant->mc_count = i; |
| 768 |
4 |
| } |
| 769 |
|
| |
| 770 |
|
| static int |
| 771 |
0 |
| in_palette(i_color *c, i_quantize *quant, int size) { |
| 772 |
|
| int i; |
| 773 |
|
| |
| 774 |
0 |
▶ | for (i = 0; i < size; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < size; ++i) { |
0 |
0 |
0 |
|
| 775 |
0 |
▶ | if (c->channel[0] == quant->mc_colors[i].channel[0] |
Branch: 1 branch
| Branch | True | False | Total |
| if (c->channel[0] == quant->mc_colors[i].channel[0] |
0 |
0 |
0 |
|
| 776 |
0 |
▶ | && c->channel[1] == quant->mc_colors[i].channel[1] |
Branch: 1 branch
| Branch | True | False | Total |
| && c->channel[1] == quant->mc_colors[i].channel[1] |
0 |
0 |
0 |
|
| 777 |
0 |
▶ | && c->channel[2] == quant->mc_colors[i].channel[2]) { |
Branch: 1 branch
| Branch | True | False | Total |
| && c->channel[2] == quant->mc_colors[i].channel[2]) { |
0 |
0 |
0 |
|
| 778 |
0 |
| return i; |
| 779 |
|
| } |
| 780 |
|
| } |
| 781 |
|
| |
| 782 |
0 |
| return -1; |
| 783 |
|
| } |
| 784 |
|
| |
| 785 |
|
| /* |
| 786 |
|
| =item makemap_palette(quant, imgs, count) |
| 787 |
|
| |
| 788 |
|
| Tests if all the given images are paletted and have a common palette, |
| 789 |
|
| if they do it builds that palette. |
| 790 |
|
| |
| 791 |
|
| A possible improvement might be to eliminate unused colors in the |
| 792 |
|
| images palettes. |
| 793 |
|
| |
| 794 |
|
| =cut |
| 795 |
|
| */ |
| 796 |
|
| |
| 797 |
|
| static int |
| 798 |
5 |
| makemap_palette(i_quantize *quant, i_img **imgs, int count) { |
| 799 |
5 |
| int size = quant->mc_count; |
| 800 |
|
| int i; |
| 801 |
|
| int imgn; |
| 802 |
|
| char used[256]; |
| 803 |
|
| int col_count; |
| 804 |
|
| |
| 805 |
5 |
| mm_log((1, "makemap_palette(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n", |
| 806 |
|
| quant, quant->mc_count, quant->mc_colors, imgs, count)); |
| 807 |
|
| /* we try to build a common palette here, if we can manage that, then |
| 808 |
|
| that's the palette we use */ |
| 809 |
5 |
▶ | for (imgn = 0; imgn < count; ++imgn) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (imgn = 0; imgn < count; ++imgn) { |
5 |
0 |
5 |
|
| 810 |
|
| int eliminate_unused; |
| 811 |
5 |
▶ | if (imgs[imgn]->type != i_palette_type) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (imgs[imgn]->type != i_palette_type) { |
5 |
0 |
5 |
|
| 812 |
5 |
| mm_log((1, "makemap_palette() -> 0 (non-palette image)\n")); |
| 813 |
5 |
| return 0; |
| 814 |
|
| } |
| 815 |
|
| |
| 816 |
0 |
▶ | if (!i_tags_get_int(&imgs[imgn]->tags, "gif_eliminate_unused", 0, |
Branch: 1 branch
| Branch | True | False | Total |
| if (!i_tags_get_int(&imgs[imgn]->tags, "gif_eliminate_unused", 0, |
0 |
0 |
0 |
|
| 817 |
|
| &eliminate_unused)) { |
| 818 |
0 |
| eliminate_unused = 1; |
| 819 |
|
| } |
| 820 |
|
| |
| 821 |
0 |
▶ | if (eliminate_unused) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (eliminate_unused) { |
0 |
0 |
0 |
|
| 822 |
0 |
| i_palidx *line = mymalloc(sizeof(i_palidx) * imgs[imgn]->xsize); |
| 823 |
|
| i_img_dim x, y; |
| 824 |
0 |
| memset(used, 0, sizeof(used)); |
| 825 |
|
| |
| 826 |
0 |
▶ | for (y = 0; y < imgs[imgn]->ysize; ++y) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (y = 0; y < imgs[imgn]->ysize; ++y) { |
0 |
0 |
0 |
|
| 827 |
0 |
▶ | i_gpal(imgs[imgn], 0, imgs[imgn]->xsize, y, line); |
Branch: 1 branch
| Branch | True | False | Total |
| i_gpal(imgs[imgn], 0, imgs[imgn]->xsize, y, line); |
0 |
0 |
0 |
|
| 828 |
0 |
▶ | for (x = 0; x < imgs[imgn]->xsize; ++x) |
Branch: 1 branch
| Branch | True | False | Total |
| for (x = 0; x < imgs[imgn]->xsize; ++x) |
0 |
0 |
0 |
|
| 829 |
0 |
| used[line[x]] = 1; |
| 830 |
|
| } |
| 831 |
|
| |
| 832 |
0 |
| myfree(line); |
| 833 |
|
| } |
| 834 |
|
| else { |
| 835 |
|
| /* assume all are in use */ |
| 836 |
0 |
| memset(used, 1, sizeof(used)); |
| 837 |
|
| } |
| 838 |
|
| |
| 839 |
0 |
▶ | col_count = i_colorcount(imgs[imgn]); |
Branch: 1 branch
| Branch | True | False | Total |
| col_count = i_colorcount(imgs[imgn]); |
0 |
0 |
0 |
|
| 840 |
0 |
▶ | for (i = 0; i < col_count; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < col_count; ++i) { |
0 |
0 |
0 |
|
| 841 |
|
| i_color c; |
| 842 |
|
| |
| 843 |
0 |
▶ | i_getcolors(imgs[imgn], i, &c, 1); |
Branch: 1 branch
| Branch | True | False | Total |
| i_getcolors(imgs[imgn], i, &c, 1); |
0 |
0 |
0 |
|
| 844 |
0 |
▶ | if (used[i]) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (used[i]) { |
0 |
0 |
0 |
|
| 845 |
0 |
▶ | if (in_palette(&c, quant, size) < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (in_palette(&c, quant, size) < 0) { |
0 |
0 |
0 |
|
| 846 |
0 |
▶ | if (size < quant->mc_size) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (size < quant->mc_size) { |
0 |
0 |
0 |
|
| 847 |
0 |
| quant->mc_colors[size++] = c; |
| 848 |
|
| } |
| 849 |
|
| else { |
| 850 |
0 |
| mm_log((1, "makemap_palette() -> 0 (too many colors)\n")); |
| 851 |
0 |
| return 0; |
| 852 |
|
| } |
| 853 |
|
| } |
| 854 |
|
| } |
| 855 |
|
| } |
| 856 |
|
| } |
| 857 |
|
| |
| 858 |
0 |
| mm_log((1, "makemap_palette() -> 1 (%d total colors)\n", size)); |
| 859 |
0 |
| quant->mc_count = size; |
| 860 |
|
| |
| 861 |
0 |
| return 1; |
| 862 |
|
| } |
| 863 |
|
| |
| 864 |
|
| #define pboxjump 32 |
| 865 |
|
| |
| 866 |
|
| /* Define one of the following 4 symbols to choose a colour search method |
| 867 |
|
| The idea is to try these out, including benchmarking, to see which |
| 868 |
|
| is fastest in a good spread of circumstances. |
| 869 |
|
| I'd expect IM_CFLINSEARCH to be fastest for very small palettes, and |
| 870 |
|
| IM_CFHASHBOX for large images with large palettes. |
| 871 |
|
| |
| 872 |
|
| Some other possibilities include: |
| 873 |
|
| - search over entries sorted by luminance |
| 874 |
|
| |
| 875 |
|
| Initially I was planning on testing using the macros and then |
| 876 |
|
| integrating the code directly into each function, but this means if |
| 877 |
|
| we find a bug at a late stage we will need to update N copies of |
| 878 |
|
| the same code. Also, keeping the code in the macros means that the |
| 879 |
|
| code in the translation functions is much more to the point, |
| 880 |
|
| there's no distracting colour search code to remove attention from |
| 881 |
|
| what makes _this_ translation function different. It may be |
| 882 |
|
| advisable to move the setup code into functions at some point, but |
| 883 |
|
| it should be possible to do this fairly transparently. |
| 884 |
|
| |
| 885 |
|
| If IM_CF_COPTS is defined then CFLAGS must have an appropriate |
| 886 |
|
| definition. |
| 887 |
|
| |
| 888 |
|
| Each option needs to define 4 macros: |
| 889 |
|
| CF_VARS - variables to define in the function |
| 890 |
|
| CF_SETUP - code to setup for the colour search, eg. allocating and |
| 891 |
|
| initializing lookup tables |
| 892 |
|
| CF_FIND - code that looks for the color in val and puts the best |
| 893 |
|
| matching index in bst_idx |
| 894 |
|
| CF_CLEANUP - code to clean up, eg. releasing memory |
| 895 |
|
| */ |
| 896 |
|
| #ifndef IM_CF_COPTS |
| 897 |
|
| /*#define IM_CFLINSEARCH*/ |
| 898 |
|
| #define IM_CFHASHBOX |
| 899 |
|
| /*#define IM_CFSORTCHAN*/ |
| 900 |
|
| /*#define IM_CFRAND2DIST*/ |
| 901 |
|
| #endif |
| 902 |
|
| |
| 903 |
|
| /* return true if the color map contains only grays */ |
| 904 |
|
| static int |
| 905 |
5 |
| is_gray_map(const i_quantize *quant) { |
| 906 |
|
| int i; |
| 907 |
|
| |
| 908 |
11 |
▶ | for (i = 0; i < quant->mc_count; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < quant->mc_count; ++i) { |
10 |
1 |
11 |
|
| 909 |
10 |
▶ | if (quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.g |
Branch: 1 branch
| Branch | True | False | Total |
| if (quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.g |
8 |
2 |
10 |
|
| 910 |
8 |
▶ | || quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.b) { |
Branch: 1 branch
| Branch | True | False | Total |
| || quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.b) { |
2 |
6 |
8 |
|
| 911 |
4 |
| mm_log((1, " not a gray map\n")); |
| 912 |
4 |
| return 0; |
| 913 |
|
| } |
| 914 |
|
| } |
| 915 |
|
| |
| 916 |
1 |
| mm_log((1, " is a gray map\n")); |
| 917 |
1 |
| return 1; |
| 918 |
|
| } |
| 919 |
|
| |
| 920 |
|
| #ifdef IM_CFHASHBOX |
| 921 |
|
| |
| 922 |
|
| /* The original version I wrote for this used the sort. |
| 923 |
|
| If this is defined then we use a sort to extract the indices for |
| 924 |
|
| the hashbox */ |
| 925 |
|
| #define HB_SORT |
| 926 |
|
| |
| 927 |
|
| /* assume i is available */ |
| 928 |
|
| #define CF_VARS hashbox *hb = mymalloc(sizeof(hashbox) * 512); \ |
| 929 |
|
| int currhb; \ |
| 930 |
|
| long ld, cd |
| 931 |
|
| |
| 932 |
|
| #ifdef HB_SORT |
| 933 |
|
| |
| 934 |
|
| static long *gdists; /* qsort is annoying */ |
| 935 |
|
| /* int might be smaller than long, so we need to do a real compare |
| 936 |
|
| rather than a subtraction*/ |
| 937 |
3787328 |
| static int distcomp(void const *a, void const *b) { |
| 938 |
3787328 |
| long ra = gdists[*(int const *)a]; |
| 939 |
3787328 |
| long rb = gdists[*(int const *)b]; |
| 940 |
3787328 |
▶ | if (ra < rb) |
Branch: 1 branch
| Branch | True | False | Total |
| if (ra < rb) |
1740270 |
2047058 |
3787328 |
|
| 941 |
1740270 |
| return -1; |
| 942 |
2047058 |
▶ | else if (ra > rb) |
Branch: 1 branch
| Branch | True | False | Total |
| else if (ra > rb) |
1944402 |
102656 |
2047058 |
|
| 943 |
1944402 |
| return 1; |
| 944 |
|
| else |
| 945 |
102656 |
| return 0; |
| 946 |
|
| } |
| 947 |
|
| |
| 948 |
|
| #endif |
| 949 |
|
| |
| 950 |
|
| /* for each hashbox build a list of colours that are in the hb or is closer |
| 951 |
|
| than other colours |
| 952 |
|
| This is pretty involved. The original gifquant generated the hashbox |
| 953 |
|
| as part of it's normal processing, but since the map generation is now |
| 954 |
|
| separated from the translation we need to do this on the spot. |
| 955 |
|
| Any optimizations, even if they don't produce perfect results would be |
| 956 |
|
| welcome. |
| 957 |
|
| */ |
| 958 |
17 |
| static void hbsetup(i_quantize *quant, hashbox *hb) { |
| 959 |
|
| long *dists, mind, maxd; |
| 960 |
|
| int cr, cb, cg, hbnum, i; |
| 961 |
|
| i_color cenc; |
| 962 |
|
| #ifdef HB_SORT |
| 963 |
17 |
| int *indices = mymalloc(quant->mc_count * sizeof(int)); |
| 964 |
|
| #endif |
| 965 |
|
| |
| 966 |
17 |
| dists = mymalloc(quant->mc_count * sizeof(long)); |
| 967 |
153 |
▶ | for (cr = 0; cr < 8; ++cr) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (cr = 0; cr < 8; ++cr) { |
136 |
17 |
153 |
|
| 968 |
1224 |
▶ | for (cg = 0; cg < 8; ++cg) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (cg = 0; cg < 8; ++cg) { |
1088 |
136 |
1224 |
|
| 969 |
9792 |
▶ | for (cb = 0; cb < 8; ++cb) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (cb = 0; cb < 8; ++cb) { |
8704 |
1088 |
9792 |
|
| 970 |
|
| /* centre of the hashbox */ |
| 971 |
8704 |
| cenc.channel[0] = cr*pboxjump+pboxjump/2; |
| 972 |
8704 |
| cenc.channel[1] = cg*pboxjump+pboxjump/2; |
| 973 |
8704 |
| cenc.channel[2] = cb*pboxjump+pboxjump/2; |
| 974 |
8704 |
| hbnum = pixbox(&cenc); |
| 975 |
8704 |
| hb[hbnum].cnt = 0; |
| 976 |
|
| /* order indices in the order of distance from the hashbox */ |
| 977 |
662528 |
▶ | for (i = 0; i < quant->mc_count; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < quant->mc_count; ++i) { |
653824 |
8704 |
662528 |
|
| 978 |
|
| #ifdef HB_SORT |
| 979 |
653824 |
| indices[i] = i; |
| 980 |
|
| #endif |
| 981 |
653824 |
| dists[i] = ceucl_d(&cenc, quant->mc_colors+i); |
| 982 |
|
| } |
| 983 |
|
| #ifdef HB_SORT |
| 984 |
|
| /* it should be possible to do this without a sort |
| 985 |
|
| but so far I'm too lazy */ |
| 986 |
8704 |
| gdists = dists; |
| 987 |
8704 |
| qsort(indices, quant->mc_count, sizeof(int), distcomp); |
| 988 |
|
| /* any colors that can match are within mind+diagonal size of |
| 989 |
|
| a hashbox */ |
| 990 |
8704 |
| mind = dists[indices[0]]; |
| 991 |
8704 |
| i = 0; |
| 992 |
8704 |
| maxd = (sqrt(mind)+pboxjump)*(sqrt(mind)+pboxjump); |
| 993 |
50213 |
▶ | while (i < quant->mc_count && dists[indices[i]] < maxd) { |
Branch: 2 branches
| Branch | True | False | Total |
| while (i < quant->mc_count && dists[indices[i]] < maxd) { |
49753 |
460 |
50213 |
| while (i < quant->mc_count && dists[indices[i]] < maxd) { |
41509 |
8244 |
49753 |
|
| 994 |
41509 |
| hb[hbnum].vec[hb[hbnum].cnt++] = indices[i++]; |
| 995 |
|
| } |
| 996 |
|
| #else |
| 997 |
|
| /* work out the minimum */ |
| 998 |
|
| mind = 256*256*3; |
| 999 |
|
| for (i = 0; i < quant->mc_count; ++i) { |
| 1000 |
|
| if (dists[i] < mind) mind = dists[i]; |
| 1001 |
|
| } |
| 1002 |
|
| /* transfer any colours that might be closest to a colour in |
| 1003 |
|
| this hashbox */ |
| 1004 |
|
| maxd = (sqrt(mind)+pboxjump)*(sqrt(mind)+pboxjump); |
| 1005 |
|
| for (i = 0; i < quant->mc_count; ++i) { |
| 1006 |
|
| if (dists[i] < maxd) |
| 1007 |
|
| hb[hbnum].vec[hb[hbnum].cnt++] = i; |
| 1008 |
|
| } |
| 1009 |
|
| #endif |
| 1010 |
|
| } |
| 1011 |
|
| } |
| 1012 |
|
| } |
| 1013 |
|
| #ifdef HB_SORT |
| 1014 |
17 |
| myfree(indices); |
| 1015 |
|
| #endif |
| 1016 |
17 |
| myfree(dists) ; |
| 1017 |
17 |
| } |
| 1018 |
|
| #define CF_SETUP hbsetup(quant, hb) |
| 1019 |
|
| |
| 1020 |
|
| #define CF_FIND \ |
| 1021 |
|
| currhb = pixbox(&val); \ |
| 1022 |
|
| ld = 196608; \ |
| 1023 |
|
| for (i = 0; i < hb[currhb].cnt; ++i) { \ |
| 1024 |
|
| cd = ceucl_d(quant->mc_colors+hb[currhb].vec[i], &val); \ |
| 1025 |
|
| if (cd < ld) { ld = cd; bst_idx = hb[currhb].vec[i]; } \ |
| 1026 |
|
| } |
| 1027 |
|
| |
| 1028 |
|
| #define CF_CLEANUP myfree(hb) |
| 1029 |
|
| |
| 1030 |
|
| #endif |
| 1031 |
|
| |
| 1032 |
|
| #ifdef IM_CFLINSEARCH |
| 1033 |
|
| /* as simple as it gets */ |
| 1034 |
|
| #define CF_VARS long ld, cd |
| 1035 |
|
| #define CF_SETUP /* none needed */ |
| 1036 |
|
| #define CF_FIND \ |
| 1037 |
|
| ld = 196608; \ |
| 1038 |
|
| for (i = 0; i < quant->mc_count; ++i) { \ |
| 1039 |
|
| cd = ceucl_d(quant->mc_colors+i, &val); \ |
| 1040 |
|
| if (cd < ld) { ld = cd; bst_idx = i; } \ |
| 1041 |
|
| } |
| 1042 |
|
| #define CF_CLEANUP |
| 1043 |
|
| #endif |
| 1044 |
|
| |
| 1045 |
|
| #ifdef IM_CFSORTCHAN |
| 1046 |
|
| static int gsortchan; |
| 1047 |
|
| static i_quantize *gquant; |
| 1048 |
|
| static int chansort(void const *a, void const *b) { |
| 1049 |
|
| return gquant->mc_colors[*(int const *)a].channel[gsortchan] - |
| 1050 |
|
| gquant->mc_colors[*(int const *)b].channel[gsortchan]; |
| 1051 |
|
| } |
| 1052 |
|
| #define CF_VARS int *indices, sortchan, diff; \ |
| 1053 |
|
| long ld, cd; \ |
| 1054 |
|
| int vindex[256] /* where to find value i of chan */ |
| 1055 |
|
| |
| 1056 |
|
| static void chansetup(i_img *img, i_quantize *quant, int *csortchan, |
| 1057 |
|
| int *vindex, int **cindices) { |
| 1058 |
|
| int *indices, sortchan, chan, i, chval; |
| 1059 |
|
| int chanmins[MAXCHANNELS], chanmaxs[MAXCHANNELS], maxrange; |
| 1060 |
|
| |
| 1061 |
|
| /* find the channel with the maximum range */ |
| 1062 |
|
| /* the maximum stddev would probably be better */ |
| 1063 |
|
| for (chan = 0; chan < img->channels; ++chan) { |
| 1064 |
|
| chanmins[chan] = 256; chanmaxs[chan] = 0; |
| 1065 |
|
| for (i = 0; i < quant->mc_count; ++i) { |
| 1066 |
|
| if (quant->mc_colors[i].channel[chan] < chanmins[chan]) |
| 1067 |
|
| chanmins[chan] = quant->mc_colors[i].channel[chan]; |
| 1068 |
|
| if (quant->mc_colors[i].channel[chan] > chanmaxs[chan]) |
| 1069 |
|
| chanmaxs[chan] = quant->mc_colors[i].channel[chan]; |
| 1070 |
|
| } |
| 1071 |
|
| } |
| 1072 |
|
| maxrange = -1; |
| 1073 |
|
| for (chan = 0; chan < img->channels; ++chan) { |
| 1074 |
|
| if (chanmaxs[chan]-chanmins[chan] > maxrange) { |
| 1075 |
|
| maxrange = chanmaxs[chan]-chanmins[chan]; |
| 1076 |
|
| sortchan = chan; |
| 1077 |
|
| } |
| 1078 |
|
| } |
| 1079 |
|
| indices = mymalloc(quant->mc_count * sizeof(int)) ; |
| 1080 |
|
| for (i = 0; i < quant->mc_count; ++i) { |
| 1081 |
|
| indices[i] = i; |
| 1082 |
|
| } |
| 1083 |
|
| gsortchan = sortchan; |
| 1084 |
|
| gquant = quant; |
| 1085 |
|
| qsort(indices, quant->mc_count, sizeof(int), chansort) ; |
| 1086 |
|
| /* now a lookup table to find entries faster */ |
| 1087 |
|
| for (chval=0, i=0; i < quant->mc_count; ++i) { |
| 1088 |
|
| while (chval < 256 && |
| 1089 |
|
| chval < quant->mc_colors[indices[i]].channel[sortchan]) { |
| 1090 |
|
| vindex[chval++] = i; |
| 1091 |
|
| } |
| 1092 |
|
| } |
| 1093 |
|
| while (chval < 256) { |
| 1094 |
|
| vindex[chval++] = quant->mc_count-1; |
| 1095 |
|
| } |
| 1096 |
|
| *csortchan = sortchan; |
| 1097 |
|
| *cindices = indices; |
| 1098 |
|
| } |
| 1099 |
|
| |
| 1100 |
|
| #define CF_SETUP \ |
| 1101 |
|
| chansetup(img, quant, &sortchan, vindex, &indices) |
| 1102 |
|
| |
| 1103 |
|
| int chanfind(i_color val, i_quantize *quant, int *indices, int *vindex, |
| 1104 |
|
| int sortchan) { |
| 1105 |
|
| int i, bst_idx, diff, maxdiff; |
| 1106 |
|
| long ld, cd; |
| 1107 |
|
| |
| 1108 |
|
| i = vindex[val.channel[sortchan]]; |
| 1109 |
|
| bst_idx = indices[i]; |
| 1110 |
|
| ld = 196608; |
| 1111 |
|
| diff = 0; |
| 1112 |
|
| maxdiff = quant->mc_count; |
| 1113 |
|
| while (diff < maxdiff) { |
| 1114 |
|
| if (i+diff < quant->mc_count) { |
| 1115 |
|
| cd = ceucl_d(&val, quant->mc_colors+indices[i+diff]); |
| 1116 |
|
| if (cd < ld) { |
| 1117 |
|
| bst_idx = indices[i+diff]; |
| 1118 |
|
| ld = cd; |
| 1119 |
|
| maxdiff = sqrt(ld); |
| 1120 |
|
| } |
| 1121 |
|
| } |
| 1122 |
|
| if (i-diff >= 0) { |
| 1123 |
|
| cd = ceucl_d(&val, quant->mc_colors+indices[i-diff]); |
| 1124 |
|
| if (cd < ld) { |
| 1125 |
|
| bst_idx = indices[i-diff]; |
| 1126 |
|
| ld = cd; |
| 1127 |
|
| maxdiff = sqrt(ld); |
| 1128 |
|
| } |
| 1129 |
|
| } |
| 1130 |
|
| ++diff; |
| 1131 |
|
| } |
| 1132 |
|
| |
| 1133 |
|
| return bst_idx; |
| 1134 |
|
| } |
| 1135 |
|
| |
| 1136 |
|
| #define CF_FIND \ |
| 1137 |
|
| bst_idx = chanfind(val, quant, indices, vindex, sortchan) |
| 1138 |
|
| |
| 1139 |
|
| |
| 1140 |
|
| #define CF_CLEANUP myfree(indices) |
| 1141 |
|
| |
| 1142 |
|
| #endif |
| 1143 |
|
| |
| 1144 |
|
| #ifdef IM_CFRAND2DIST |
| 1145 |
|
| |
| 1146 |
|
| /* This is based on a method described by Addi in the #imager channel |
| 1147 |
|
| on the 28/2/2001. I was about 1am Sydney time at the time, so I |
| 1148 |
|
| wasn't at my most cogent. Well, that's my excuse :) |
| 1149 |
|
| |
| 1150 |
|
| <TonyC> what I have at the moment is: hashboxes, with optimum hash box |
| 1151 |
|
| filling; simple linear search; and a lookup in the widest channel |
| 1152 |
|
| (currently the channel with the maximum range) |
| 1153 |
|
| <Addi> There is one more way that might be simple to implement. |
| 1154 |
|
| <Addi> You want to hear? |
| 1155 |
|
| <TonyC> what's that? |
| 1156 |
|
| <purl> somebody said that was not true |
| 1157 |
|
| <Addi> For each of the colors in the palette start by creating a |
| 1158 |
|
| sorted list of the form: |
| 1159 |
|
| <Addi> [distance, color] |
| 1160 |
|
| <Addi> Where they are sorted by distance. |
| 1161 |
|
| <TonyC> distance to where? |
| 1162 |
|
| <Addi> Where the elements in the lists are the distances and colors of |
| 1163 |
|
| the other colors in the palette |
| 1164 |
|
| <TonyC> ok |
| 1165 |
|
| <Addi> So if you are at color 0 |
| 1166 |
|
| <Addi> ok - now to search for the closest color when you are creating |
| 1167 |
|
| the final image is done like this: |
| 1168 |
|
| <Addi> a) pick a random color from the palette |
| 1169 |
|
| <Addi> b) calculate the distance to it |
| 1170 |
|
| <Addi> c) only check the vectors that are within double the distance |
| 1171 |
|
| in the list of the color you picked from the palette. |
| 1172 |
|
| <Addi> Does that seem logical? |
| 1173 |
|
| <Addi> Lets imagine that we only have grayscale to make an example: |
| 1174 |
|
| <Addi> Our palette has 1 4 10 20 as colors. |
| 1175 |
|
| <Addi> And we want to quantize the color 11 |
| 1176 |
|
| <Addi> lets say we picked 10 randomly |
| 1177 |
|
| <Addi> the double distance is 2 |
| 1178 |
|
| <Addi> since abs(10-11)*2 is 2 |
| 1179 |
|
| <Addi> And the list at vector 10 is this: |
| 1180 |
|
| <Addi> [0, 10], [6 4], [9, 1], [10, 20] |
| 1181 |
|
| <Addi> so we look at the first one (but not the second one since 6 is |
| 1182 |
|
| at a greater distance than 2. |
| 1183 |
|
| <Addi> Any of that make sense? |
| 1184 |
|
| <TonyC> yes, though are you suggesting another random jump to one of |
| 1185 |
|
| the colours with the possible choices? or an exhaustive search? |
| 1186 |
|
| <Addi> TonyC: It's possible to come up with a recursive/iterative |
| 1187 |
|
| enhancement but this is the 'basic' version. |
| 1188 |
|
| <Addi> Which would do an iterative search. |
| 1189 |
|
| <Addi> You can come up with conditions where it pays to switch to a new one. |
| 1190 |
|
| <Addi> And the 'random' start can be switched over to a small tree. |
| 1191 |
|
| <Addi> So you would have a little index at the start. |
| 1192 |
|
| <Addi> to get you into the general direction |
| 1193 |
|
| <Addi> Perhaps just an 8 split. |
| 1194 |
|
| <Addi> that is - split each dimension in half. |
| 1195 |
|
| <TonyC> yep |
| 1196 |
|
| <TonyC> I get the idea |
| 1197 |
|
| <Addi> But this would seem to be a good approach in our case since we |
| 1198 |
|
| usually have few codevectors. |
| 1199 |
|
| <Addi> So we only need 256*256 entries in a table. |
| 1200 |
|
| <Addi> We could even only index some of them that were deemed as good |
| 1201 |
|
| candidates. |
| 1202 |
|
| <TonyC> I was considering adding paletted output support for PNG and |
| 1203 |
|
| TIFF at some point, which support 16-bit palettes |
| 1204 |
|
| <Addi> ohh. |
| 1205 |
|
| <Addi> 'darn' ;) |
| 1206 |
|
| |
| 1207 |
|
| |
| 1208 |
|
| */ |
| 1209 |
|
| |
| 1210 |
|
| |
| 1211 |
|
| typedef struct i_dists { |
| 1212 |
|
| int index; |
| 1213 |
|
| long dist; |
| 1214 |
|
| } i_dists; |
| 1215 |
|
| |
| 1216 |
|
| #define CF_VARS \ |
| 1217 |
|
| i_dists *dists; |
| 1218 |
|
| |
| 1219 |
|
| static int dists_sort(void const *a, void const *b) { |
| 1220 |
|
| return ((i_dists *)a)->dist - ((i_dists *)b)->dist; |
| 1221 |
|
| } |
| 1222 |
|
| |
| 1223 |
|
| static void rand2dist_setup(i_quantize *quant, i_dists **cdists) { |
| 1224 |
|
| i_dists *dists = |
| 1225 |
|
| mymalloc(sizeof(i_dists)*quant->mc_count*quant->mc_count); |
| 1226 |
|
| int i, j; |
| 1227 |
|
| long cd; |
| 1228 |
|
| for (i = 0; i < quant->mc_count; ++i) { |
| 1229 |
|
| i_dists *ldists = dists + quant->mc_count * i; |
| 1230 |
|
| i_color val = quant->mc_colors[i]; |
| 1231 |
|
| for (j = 0; j < quant->mc_count; ++j) { |
| 1232 |
|
| ldists[j].index = j; |
| 1233 |
|
| ldists[j].dist = ceucl_d(&val, quant->mc_colors+j); |
| 1234 |
|
| } |
| 1235 |
|
| qsort(ldists, quant->mc_count, sizeof(i_dists), dists_sort); |
| 1236 |
|
| } |
| 1237 |
|
| *cdists = dists; |
| 1238 |
|
| } |
| 1239 |
|
| |
| 1240 |
|
| #define CF_SETUP \ |
| 1241 |
|
| bst_idx = rand() % quant->mc_count; \ |
| 1242 |
|
| rand2dist_setup(quant, &dists) |
| 1243 |
|
| |
| 1244 |
|
| static int rand2dist_find(i_color val, i_quantize *quant, i_dists *dists, int index) { |
| 1245 |
|
| i_dists *cdists; |
| 1246 |
|
| long cd, ld; |
| 1247 |
|
| long maxld; |
| 1248 |
|
| int i; |
| 1249 |
|
| int bst_idx; |
| 1250 |
|
| |
| 1251 |
|
| cdists = dists + index * quant->mc_count; |
| 1252 |
|
| ld = 3 * 256 * 256; |
| 1253 |
|
| maxld = 8 * ceucl_d(&val, quant->mc_colors+index); |
| 1254 |
|
| for (i = 0; i < quant->mc_count && cdists[i].dist <= maxld; ++i) { |
| 1255 |
|
| cd = ceucl_d(&val, quant->mc_colors+cdists[i].index); |
| 1256 |
|
| if (cd < ld) { |
| 1257 |
|
| bst_idx = cdists[i].index; |
| 1258 |
|
| ld = cd; |
| 1259 |
|
| } |
| 1260 |
|
| } |
| 1261 |
|
| return bst_idx; |
| 1262 |
|
| } |
| 1263 |
|
| |
| 1264 |
|
| #define CF_FIND bst_idx = rand2dist_find(val, quant, dists, bst_idx) |
| 1265 |
|
| |
| 1266 |
|
| #define CF_CLEANUP myfree(dists) |
| 1267 |
|
| |
| 1268 |
|
| |
| 1269 |
|
| #endif |
| 1270 |
|
| |
| 1271 |
12 |
| static void translate_addi(i_quantize *quant, i_img *img, i_palidx *out) { |
| 1272 |
|
| i_img_dim x, y, k; |
| 1273 |
12 |
| int i, bst_idx = 0; |
| 1274 |
|
| i_color val; |
| 1275 |
12 |
| int pixdev = quant->perturb; |
| 1276 |
12 |
| CF_VARS; |
| 1277 |
|
| |
| 1278 |
12 |
| CF_SETUP; |
| 1279 |
|
| |
| 1280 |
12 |
▶ | if (img->channels >= 3) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (img->channels >= 3) { |
12 |
0 |
12 |
|
| 1281 |
12 |
▶ | if (pixdev) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (pixdev) { |
0 |
12 |
12 |
|
| 1282 |
0 |
| k=0; |
| 1283 |
0 |
▶ | for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
Branch: 2 branches
| Branch | True | False | Total |
| for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
0 |
0 |
0 |
| for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
0 |
0 |
0 |
|
| 1284 |
0 |
| i_gpix(img,x,y,&val); |
| 1285 |
0 |
| val.channel[0]=g_sat(val.channel[0]+(int)(pixdev*frandn())); |
| 1286 |
0 |
| val.channel[1]=g_sat(val.channel[1]+(int)(pixdev*frandn())); |
| 1287 |
0 |
| val.channel[2]=g_sat(val.channel[2]+(int)(pixdev*frandn())); |
| 1288 |
0 |
▶ | CF_FIND; |
Branch: 2 branches
| Branch | True | False | Total |
| CF_FIND; |
0 |
0 |
0 |
| CF_FIND; |
0 |
0 |
0 |
|
| 1289 |
0 |
| out[k++]=bst_idx; |
| 1290 |
|
| } |
| 1291 |
|
| } else { |
| 1292 |
12 |
| k=0; |
| 1293 |
199445 |
▶ | for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
Branch: 2 branches
| Branch | True | False | Total |
| for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
198074 |
1359 |
199433 |
| for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
1359 |
12 |
1371 |
|
| 1294 |
198074 |
| i_gpix(img,x,y,&val); |
| 1295 |
1357746 |
▶ | CF_FIND; |
Branch: 2 branches
| Branch | True | False | Total |
| CF_FIND; |
317121 |
842551 |
1159672 |
| CF_FIND; |
1159672 |
198074 |
1357746 |
|
| 1296 |
198074 |
| out[k++]=bst_idx; |
| 1297 |
|
| } |
| 1298 |
|
| } |
| 1299 |
|
| } |
| 1300 |
|
| else { |
| 1301 |
0 |
▶ | if (pixdev) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (pixdev) { |
0 |
0 |
0 |
|
| 1302 |
0 |
| k=0; |
| 1303 |
0 |
▶ | for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
Branch: 2 branches
| Branch | True | False | Total |
| for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
0 |
0 |
0 |
| for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
0 |
0 |
0 |
|
| 1304 |
0 |
| i_gpix(img,x,y,&val); |
| 1305 |
0 |
| val.channel[1] = val.channel[2] = |
| 1306 |
0 |
| val.channel[0]=g_sat(val.channel[0]+(int)(pixdev*frandn())); |
| 1307 |
0 |
▶ | CF_FIND; |
Branch: 2 branches
| Branch | True | False | Total |
| CF_FIND; |
0 |
0 |
0 |
| CF_FIND; |
0 |
0 |
0 |
|
| 1308 |
0 |
| out[k++]=bst_idx; |
| 1309 |
|
| } |
| 1310 |
|
| } else { |
| 1311 |
0 |
| k=0; |
| 1312 |
0 |
▶ | for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
Branch: 2 branches
| Branch | True | False | Total |
| for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
0 |
0 |
0 |
| for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { |
0 |
0 |
0 |
|
| 1313 |
0 |
| i_gpix(img,x,y,&val); |
| 1314 |
0 |
| val.channel[1] = val.channel[2] = val.channel[0]; |
| 1315 |
0 |
▶ | CF_FIND; |
Branch: 2 branches
| Branch | True | False | Total |
| CF_FIND; |
0 |
0 |
0 |
| CF_FIND; |
0 |
0 |
0 |
|
| 1316 |
0 |
| out[k++]=bst_idx; |
| 1317 |
|
| } |
| 1318 |
|
| } |
| 1319 |
|
| } |
| 1320 |
12 |
| CF_CLEANUP; |
| 1321 |
12 |
| } |
| 1322 |
|
| |
| 1323 |
|
| static int floyd_map[] = |
| 1324 |
|
| { |
| 1325 |
|
| 0, 0, 7, |
| 1326 |
|
| 3, 5, 1 |
| 1327 |
|
| }; |
| 1328 |
|
| |
| 1329 |
|
| static int jarvis_map[] = |
| 1330 |
|
| { |
| 1331 |
|
| 0, 0, 0, 7, 5, |
| 1332 |
|
| 3, 5, 7, 5, 3, |
| 1333 |
|
| 1, 3, 5, 3, 1 |
| 1334 |
|
| }; |
| 1335 |
|
| |
| 1336 |
|
| static int stucki_map[] = |
| 1337 |
|
| { |
| 1338 |
|
| 0, 0, 0, 8, 4, |
| 1339 |
|
| 2, 4, 8, 4, 2, |
| 1340 |
|
| 1, 2, 4, 2, 1 |
| 1341 |
|
| }; |
| 1342 |
|
| |
| 1343 |
|
| struct errdiff_map { |
| 1344 |
|
| int *map; |
| 1345 |
|
| int width, height, orig; |
| 1346 |
|
| }; |
| 1347 |
|
| |
| 1348 |
|
| static struct errdiff_map maps[] = |
| 1349 |
|
| { |
| 1350 |
|
| { floyd_map, 3, 2, 1 }, |
| 1351 |
|
| { jarvis_map, 5, 3, 2 }, |
| 1352 |
|
| { stucki_map, 5, 3, 2 }, |
| 1353 |
|
| }; |
| 1354 |
|
| |
| 1355 |
|
| typedef struct errdiff_tag { |
| 1356 |
|
| int r, g, b; |
| 1357 |
|
| } errdiff_t; |
| 1358 |
|
| |
| 1359 |
|
| /* perform an error diffusion dither */ |
| 1360 |
|
| static int |
| 1361 |
5 |
| translate_errdiff(i_quantize *quant, i_img *img, i_palidx *out) { |
| 1362 |
|
| int *map; |
| 1363 |
|
| int mapw, maph, mapo; |
| 1364 |
|
| int i; |
| 1365 |
|
| errdiff_t *err; |
| 1366 |
|
| i_img_dim errw; |
| 1367 |
|
| int difftotal; |
| 1368 |
|
| i_img_dim x, y, dx, dy; |
| 1369 |
5 |
| int bst_idx = 0; |
| 1370 |
5 |
| int is_gray = is_gray_map(quant); |
| 1371 |
5 |
| CF_VARS; |
| 1372 |
|
| |
| 1373 |
5 |
▶ | if ((quant->errdiff & ed_mask) == ed_custom) { |
Branch: 1 branch
| Branch | True | False | Total |
| if ((quant->errdiff & ed_mask) == ed_custom) { |
0 |
5 |
5 |
|
| 1374 |
0 |
| map = quant->ed_map; |
| 1375 |
0 |
| mapw = quant->ed_width; |
| 1376 |
0 |
| maph = quant->ed_height; |
| 1377 |
0 |
| mapo = quant->ed_orig; |
| 1378 |
|
| } |
| 1379 |
|
| else { |
| 1380 |
5 |
| int index = quant->errdiff & ed_mask; |
| 1381 |
5 |
▶ | if (index >= ed_custom) index = ed_floyd; |
Branch: 1 branch
| Branch | True | False | Total |
| if (index >= ed_custom) index = ed_floyd; |
0 |
5 |
5 |
|
| 1382 |
5 |
| map = maps[index].map; |
| 1383 |
5 |
| mapw = maps[index].width; |
| 1384 |
5 |
| maph = maps[index].height; |
| 1385 |
5 |
| mapo = maps[index].orig; |
| 1386 |
|
| } |
| 1387 |
|
| |
| 1388 |
5 |
| difftotal = 0; |
| 1389 |
35 |
▶ | for (i = 0; i < maph * mapw; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < maph * mapw; ++i) { |
30 |
5 |
35 |
|
| 1390 |
30 |
▶ | if (map[i] < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (map[i] < 0) { |
0 |
30 |
30 |
|
| 1391 |
0 |
| i_push_errorf(0, "errdiff_map values must be non-negative, errdiff[%d] is negative", i); |
| 1392 |
0 |
| goto fail; |
| 1393 |
|
| } |
| 1394 |
30 |
| difftotal += map[i]; |
| 1395 |
|
| } |
| 1396 |
|
| |
| 1397 |
5 |
▶ | if (!difftotal) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!difftotal) { |
0 |
5 |
5 |
|
| 1398 |
0 |
| i_push_error(0, "error diffusion map must contain some non-zero values"); |
| 1399 |
0 |
| goto fail; |
| 1400 |
|
| } |
| 1401 |
|
| |
| 1402 |
5 |
| errw = img->xsize+mapw; |
| 1403 |
5 |
| err = mymalloc(sizeof(*err) * maph * errw); |
| 1404 |
|
| /*errp = err+mapo;*/ |
| 1405 |
5 |
| memset(err, 0, sizeof(*err) * maph * errw); |
| 1406 |
|
| |
| 1407 |
|
| /*printf("map:\n"); |
| 1408 |
|
| for (dy = 0; dy < maph; ++dy) { |
| 1409 |
|
| for (dx = 0; dx < mapw; ++dx) { |
| 1410 |
|
| printf("%2d", map[dx+dy*mapw]); |
| 1411 |
|
| } |
| 1412 |
|
| putchar('\n'); |
| 1413 |
|
| }*/ |
| 1414 |
|
| |
| 1415 |
5 |
| CF_SETUP; |
| 1416 |
|
| |
| 1417 |
615 |
▶ | for (y = 0; y < img->ysize; ++y) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (y = 0; y < img->ysize; ++y) { |
610 |
5 |
615 |
|
| 1418 |
90710 |
▶ | for (x = 0; x < img->xsize; ++x) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (x = 0; x < img->xsize; ++x) { |
90100 |
610 |
90710 |
|
| 1419 |
|
| i_color val; |
| 1420 |
|
| errdiff_t perr; |
| 1421 |
90100 |
| i_gpix(img, x, y, &val); |
| 1422 |
90100 |
▶ | if (img->channels < 3) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (img->channels < 3) { |
0 |
90100 |
90100 |
|
| 1423 |
0 |
| val.channel[1] = val.channel[2] = val.channel[0]; |
| 1424 |
|
| } |
| 1425 |
90100 |
▶ | else if (is_gray) { |
Branch: 1 branch
| Branch | True | False | Total |
| else if (is_gray) { |
100 |
90000 |
90100 |
|
| 1426 |
100 |
| int gray = 0.5 + color_to_grey(&val); |
| 1427 |
100 |
| val.channel[0] = val.channel[1] = val.channel[2] = gray; |
| 1428 |
|
| } |
| 1429 |
90100 |
| perr = err[x+mapo]; |
| 1430 |
90100 |
▶ | perr.r = perr.r < 0 ? -((-perr.r)/difftotal) : perr.r/difftotal; |
Branch: 1 branch
| Branch | True | False | Total |
| perr.r = perr.r < 0 ? -((-perr.r)/difftotal) : perr.r/difftotal; |
9002 |
81098 |
90100 |
|
| 1431 |
90100 |
▶ | perr.g = perr.g < 0 ? -((-perr.g)/difftotal) : perr.g/difftotal; |
Branch: 1 branch
| Branch | True | False | Total |
| perr.g = perr.g < 0 ? -((-perr.g)/difftotal) : perr.g/difftotal; |
18200 |
71900 |
90100 |
|
| 1432 |
90100 |
▶ | perr.b = perr.b < 0 ? -((-perr.b)/difftotal) : perr.b/difftotal; |
Branch: 1 branch
| Branch | True | False | Total |
| perr.b = perr.b < 0 ? -((-perr.b)/difftotal) : perr.b/difftotal; |
17780 |
72320 |
90100 |
|
| 1433 |
|
| /*printf("x %3d y %3d in(%3d, %3d, %3d) di(%4d,%4d,%4d)\n", x, y, val.channel[0], val.channel[1], val.channel[2], perr.r, perr.g, perr.b);*/ |
| 1434 |
90100 |
| val.channel[0] = g_sat(val.channel[0]-perr.r); |
| 1435 |
90100 |
| val.channel[1] = g_sat(val.channel[1]-perr.g); |
| 1436 |
90100 |
| val.channel[2] = g_sat(val.channel[2]-perr.b); |
| 1437 |
469450 |
▶ | CF_FIND; |
Branch: 2 branches
| Branch | True | False | Total |
| CF_FIND; |
104242 |
275108 |
379350 |
| CF_FIND; |
379350 |
90100 |
469450 |
|
| 1438 |
|
| /* save error */ |
| 1439 |
90100 |
| perr.r = quant->mc_colors[bst_idx].channel[0] - val.channel[0]; |
| 1440 |
90100 |
| perr.g = quant->mc_colors[bst_idx].channel[1] - val.channel[1]; |
| 1441 |
90100 |
| perr.b = quant->mc_colors[bst_idx].channel[2] - val.channel[2]; |
| 1442 |
|
| /*printf(" out(%3d, %3d, %3d) er(%4d, %4d, %4d)\n", quant->mc_colors[bst_idx].channel[0], quant->mc_colors[bst_idx].channel[1], quant->mc_colors[bst_idx].channel[2], perr.r, perr.g, perr.b);*/ |
| 1443 |
360400 |
▶ | for (dx = 0; dx < mapw; ++dx) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (dx = 0; dx < mapw; ++dx) { |
270300 |
90100 |
360400 |
|
| 1444 |
810900 |
▶ | for (dy = 0; dy < maph; ++dy) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (dy = 0; dy < maph; ++dy) { |
540600 |
270300 |
810900 |
|
| 1445 |
540600 |
| err[x+dx+dy*errw].r += perr.r * map[dx+mapw*dy]; |
| 1446 |
540600 |
| err[x+dx+dy*errw].g += perr.g * map[dx+mapw*dy]; |
| 1447 |
540600 |
| err[x+dx+dy*errw].b += perr.b * map[dx+mapw*dy]; |
| 1448 |
|
| } |
| 1449 |
|
| } |
| 1450 |
90100 |
| *out++ = bst_idx; |
| 1451 |
|
| } |
| 1452 |
|
| /* shift up the error matrix */ |
| 1453 |
1220 |
▶ | for (dy = 0; dy < maph-1; ++dy) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (dy = 0; dy < maph-1; ++dy) { |
610 |
610 |
1220 |
|
| 1454 |
610 |
| memcpy(err+dy*errw, err+(dy+1)*errw, sizeof(*err)*errw); |
| 1455 |
|
| } |
| 1456 |
610 |
| memset(err+(maph-1)*errw, 0, sizeof(*err)*errw); |
| 1457 |
|
| } |
| 1458 |
5 |
| CF_CLEANUP; |
| 1459 |
5 |
| myfree(err); |
| 1460 |
|
| |
| 1461 |
5 |
| return 1; |
| 1462 |
|
| |
| 1463 |
0 |
| fail: |
| 1464 |
0 |
| CF_CLEANUP; |
| 1465 |
|
| |
| 1466 |
0 |
| return 0; |
| 1467 |
|
| } |
| 1468 |
|
| /* Prescan finds the boxes in the image that have the highest number of colors |
| 1469 |
|
| and that result is used as the initial value for the vectores */ |
| 1470 |
|
| |
| 1471 |
|
| |
| 1472 |
0 |
| static void prescan(i_img **imgs,int count, int cnum, cvec *clr, i_sample_t *line) { |
| 1473 |
|
| int i,k,j; |
| 1474 |
|
| i_img_dim x,y; |
| 1475 |
|
| i_sample_t *val; |
| 1476 |
|
| const int *chans; |
| 1477 |
|
| |
| 1478 |
|
| pbox prebox[512]; |
| 1479 |
0 |
▶ | for(i=0;i<512;i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(i=0;i<512;i++) { |
0 |
0 |
0 |
|
| 1480 |
0 |
| prebox[i].boxnum=i; |
| 1481 |
0 |
| prebox[i].pixcnt=0; |
| 1482 |
0 |
| prebox[i].cand=1; |
| 1483 |
|
| } |
| 1484 |
|
| |
| 1485 |
|
| /* process each image */ |
| 1486 |
0 |
▶ | for (i = 0; i < count; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < count; ++i) { |
0 |
0 |
0 |
|
| 1487 |
0 |
| i_img *im = imgs[i]; |
| 1488 |
0 |
▶ | chans = im->channels >= 3 ? NULL : gray_samples; |
Branch: 1 branch
| Branch | True | False | Total |
| chans = im->channels >= 3 ? NULL : gray_samples; |
0 |
0 |
0 |
|
| 1489 |
0 |
▶ | for(y=0;y<im->ysize;y++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(y=0;y<im->ysize;y++) { |
0 |
0 |
0 |
|
| 1490 |
0 |
| i_gsamp(im, 0, im->xsize, y, line, chans, 3); |
| 1491 |
0 |
| val = line; |
| 1492 |
0 |
▶ | for(x=0;x<im->xsize;x++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(x=0;x<im->xsize;x++) { |
0 |
0 |
0 |
|
| 1493 |
0 |
| prebox[pixbox_ch(val)].pixcnt++; |
| 1494 |
|
| } |
| 1495 |
|
| } |
| 1496 |
|
| } |
| 1497 |
|
| |
| 1498 |
0 |
▶ | for(i=0;i<512;i++) prebox[i].pdc=prebox[i].pixcnt; |
Branch: 1 branch
| Branch | True | False | Total |
| for(i=0;i<512;i++) prebox[i].pdc=prebox[i].pixcnt; |
0 |
0 |
0 |
|
| 1499 |
0 |
| qsort(prebox,512,sizeof(pbox),(cmpfunc)pboxcmp); |
| 1500 |
|
| |
| 1501 |
0 |
▶ | for(i=0;i<cnum;i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(i=0;i<cnum;i++) { |
0 |
0 |
0 |
|
| 1502 |
|
| /* printf("Color %d\n",i); |
| 1503 |
|
| for(k=0;k<10;k++) { printf("box=%03d %04d %d %04d \n",prebox[k].boxnum,prebox[k].pixcnt,prebox[k].cand,prebox[k].pdc); } |
| 1504 |
|
| printf("\n\n"); */ |
| 1505 |
0 |
| reorder(prebox); |
| 1506 |
|
| } |
| 1507 |
|
| |
| 1508 |
|
| /* for(k=0;k<cnum;k++) { printf("box=%03d %04d %d %04d \n",prebox[k].boxnum,prebox[k].pixcnt,prebox[k].cand,prebox[k].pdc); } */ |
| 1509 |
|
| |
| 1510 |
0 |
| k=0; |
| 1511 |
0 |
| j=1; |
| 1512 |
0 |
| i=0; |
| 1513 |
0 |
▶ | while(i<cnum) { |
Branch: 1 branch
| Branch | True | False | Total |
| while(i<cnum) { |
0 |
0 |
0 |
|
| 1514 |
|
| /* printf("prebox[%d].cand=%d\n",k,prebox[k].cand); */ |
| 1515 |
0 |
▶ | if (clr[i].fixed) { i++; continue; } /* reserved go to next */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (clr[i].fixed) { i++; continue; } /* reserved go to next */ |
0 |
0 |
0 |
|
| 1516 |
0 |
▶ | if (j>=prebox[k].cand) { k++; j=1; } else { |
Branch: 1 branch
| Branch | True | False | Total |
| if (j>=prebox[k].cand) { k++; j=1; } else { |
0 |
0 |
0 |
|
| 1517 |
0 |
▶ | if (prebox[k].cand == 2) boxcenter(prebox[k].boxnum,&(clr[i])); |
Branch: 1 branch
| Branch | True | False | Total |
| if (prebox[k].cand == 2) boxcenter(prebox[k].boxnum,&(clr[i])); |
0 |
0 |
0 |
|
| 1518 |
0 |
| else boxrand(prebox[k].boxnum,&(clr[i])); |
| 1519 |
|
| /* printf("(%d,%d) %d %d -> (%d,%d,%d)\n",k,j,prebox[k].boxnum,prebox[k].pixcnt,clr[i].r,clr[i].g,clr[i].b); */ |
| 1520 |
0 |
| j++; |
| 1521 |
0 |
| i++; |
| 1522 |
|
| } |
| 1523 |
|
| } |
| 1524 |
0 |
| } |
| 1525 |
|
| |
| 1526 |
|
| |
| 1527 |
0 |
| static void reorder(pbox prescan[512]) { |
| 1528 |
|
| int nidx; |
| 1529 |
|
| pbox c; |
| 1530 |
|
| |
| 1531 |
0 |
| nidx=0; |
| 1532 |
0 |
| c=prescan[0]; |
| 1533 |
|
| |
| 1534 |
0 |
| c.cand++; |
| 1535 |
0 |
| c.pdc=c.pixcnt/(c.cand*c.cand); |
| 1536 |
|
| /* c.pdc=c.pixcnt/c.cand; */ |
| 1537 |
0 |
▶ | while(nidx < 511 && c.pdc < prescan[nidx+1].pdc) { |
Branch: 2 branches
| Branch | True | False | Total |
| while(nidx < 511 && c.pdc < prescan[nidx+1].pdc) { |
0 |
0 |
0 |
| while(nidx < 511 && c.pdc < prescan[nidx+1].pdc) { |
0 |
0 |
0 |
|
| 1538 |
0 |
| prescan[nidx]=prescan[nidx+1]; |
| 1539 |
0 |
| nidx++; |
| 1540 |
|
| } |
| 1541 |
0 |
| prescan[nidx]=c; |
| 1542 |
0 |
| } |
| 1543 |
|
| |
| 1544 |
|
| static int |
| 1545 |
0 |
| pboxcmp(const pbox *a,const pbox *b) { |
| 1546 |
0 |
▶ | if (a->pixcnt > b->pixcnt) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (a->pixcnt > b->pixcnt) return -1; |
0 |
0 |
0 |
|
| 1547 |
0 |
▶ | if (a->pixcnt < b->pixcnt) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (a->pixcnt < b->pixcnt) return 1; |
0 |
0 |
0 |
|
| 1548 |
0 |
| return 0; |
| 1549 |
|
| } |
| 1550 |
|
| |
| 1551 |
|
| static void |
| 1552 |
0 |
| boxcenter(int box,cvec *cv) { |
| 1553 |
0 |
| cv->r=15+((box&448)>>1); |
| 1554 |
0 |
| cv->g=15+((box&56)<<2); |
| 1555 |
0 |
| cv->b=15+((box&7)<<5); |
| 1556 |
0 |
| } |
| 1557 |
|
| |
| 1558 |
|
| static void |
| 1559 |
0 |
| bbox(int box,int *r0,int *r1,int *g0,int *g1,int *b0,int *b1) { |
| 1560 |
0 |
| *r0=(box&448)>>1; |
| 1561 |
0 |
| *r1=(*r0)|31; |
| 1562 |
0 |
| *g0=(box&56)<<2; |
| 1563 |
0 |
| *g1=(*g0)|31; |
| 1564 |
0 |
| *b0=(box&7)<<5; |
| 1565 |
0 |
| *b1=(*b0)|31; |
| 1566 |
0 |
| } |
| 1567 |
|
| |
| 1568 |
|
| static void |
| 1569 |
0 |
| boxrand(int box,cvec *cv) { |
| 1570 |
0 |
| cv->r=6+(rand()%25)+((box&448)>>1); |
| 1571 |
0 |
| cv->g=6+(rand()%25)+((box&56)<<2); |
| 1572 |
0 |
| cv->b=6+(rand()%25)+((box&7)<<5); |
| 1573 |
0 |
| } |
| 1574 |
|
| |
| 1575 |
|
| static float |
| 1576 |
0 |
| frandn(void) { |
| 1577 |
|
| |
| 1578 |
|
| float u1,u2,w; |
| 1579 |
|
| |
| 1580 |
0 |
| w=1; |
| 1581 |
|
| |
| 1582 |
0 |
▶ | while (w >= 1 || w == 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| while (w >= 1 || w == 0) { |
0 |
0 |
0 |
| while (w >= 1 || w == 0) { |
0 |
0 |
0 |
|
| 1583 |
0 |
| u1 = 2 * frand() - 1; |
| 1584 |
0 |
| u2 = 2 * frand() - 1; |
| 1585 |
0 |
| w = u1*u1 + u2*u2; |
| 1586 |
|
| } |
| 1587 |
|
| |
| 1588 |
0 |
| w = sqrt((-2*log(w))/w); |
| 1589 |
0 |
| return u1*w; |
| 1590 |
|
| } |
| 1591 |
|
| |
| 1592 |
|
| /* Create hash index */ |
| 1593 |
|
| static |
| 1594 |
|
| void |
| 1595 |
0 |
| cr_hashindex(cvec clr[256],int cnum,hashbox hb[512]) { |
| 1596 |
|
| |
| 1597 |
|
| int bx,mind,cd,i; |
| 1598 |
|
| /* printf("indexing... \n");*/ |
| 1599 |
|
| |
| 1600 |
0 |
▶ | for(bx=0; bx<512; bx++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(bx=0; bx<512; bx++) { |
0 |
0 |
0 |
|
| 1601 |
0 |
| mind=196608; |
| 1602 |
0 |
▶ | for(i=0; i<cnum; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(i=0; i<cnum; i++) { |
0 |
0 |
0 |
|
| 1603 |
0 |
| cd = maxdist(bx,&clr[i]); |
| 1604 |
0 |
▶ | if (cd < mind) { mind=cd; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (cd < mind) { mind=cd; } |
0 |
0 |
0 |
|
| 1605 |
|
| } |
| 1606 |
|
| |
| 1607 |
0 |
| hb[bx].cnt=0; |
| 1608 |
0 |
▶ | for(i=0;i<cnum;i++) if (mindist(bx,&clr[i])<mind) hb[bx].vec[hb[bx].cnt++]=i; |
Branch: 2 branches
| Branch | True | False | Total |
| for(i=0;i<cnum;i++) if (mindist(bx,&clr[i])<mind) hb[bx].vec[hb[bx].cnt++]=i; |
0 |
0 |
0 |
| for(i=0;i<cnum;i++) if (mindist(bx,&clr[i])<mind) hb[bx].vec[hb[bx].cnt++]=i; |
0 |
0 |
0 |
|
| 1609 |
|
| /*printf("box %d -> approx -> %d\n",bx,hb[bx].cnt); */ |
| 1610 |
|
| /* statbox(bx,cnum,clr); */ |
| 1611 |
|
| } |
| 1612 |
|
| |
| 1613 |
|
| /* printf("Average search space: %d\n",cumcnt/512); */ |
| 1614 |
0 |
| } |
| 1615 |
|
| |
| 1616 |
|
| static int |
| 1617 |
0 |
| maxdist(int boxnum,cvec *cv) { |
| 1618 |
|
| int r0,r1,g0,g1,b0,b1; |
| 1619 |
|
| int r,g,b,mr,mg,mb; |
| 1620 |
|
| |
| 1621 |
0 |
| r=cv->r; |
| 1622 |
0 |
| g=cv->g; |
| 1623 |
0 |
| b=cv->b; |
| 1624 |
|
| |
| 1625 |
0 |
| bbox(boxnum,&r0,&r1,&g0,&g1,&b0,&b1); |
| 1626 |
|
| |
| 1627 |
0 |
| mr=i_max(abs(b-b0),abs(b-b1)); |
| 1628 |
0 |
| mg=i_max(abs(g-g0),abs(g-g1)); |
| 1629 |
0 |
| mb=i_max(abs(r-r0),abs(r-r1)); |
| 1630 |
|
| |
| 1631 |
0 |
| return PWR2(mr)+PWR2(mg)+PWR2(mb); |
| 1632 |
|
| } |
| 1633 |
|
| |
| 1634 |
|
| static int |
| 1635 |
0 |
| mindist(int boxnum,cvec *cv) { |
| 1636 |
|
| int r0,r1,g0,g1,b0,b1; |
| 1637 |
|
| int r,g,b,mr,mg,mb; |
| 1638 |
|
| |
| 1639 |
0 |
| r=cv->r; |
| 1640 |
0 |
| g=cv->g; |
| 1641 |
0 |
| b=cv->b; |
| 1642 |
|
| |
| 1643 |
0 |
| bbox(boxnum,&r0,&r1,&g0,&g1,&b0,&b1); |
| 1644 |
|
| |
| 1645 |
|
| /* printf("box %d, (%d,%d,%d)-(%d,%d,%d) vec (%d,%d,%d) ",boxnum,r0,g0,b0,r1,g1,b1,r,g,b); */ |
| 1646 |
|
| |
| 1647 |
0 |
▶ | if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; |
Branch: 6 branches
| Branch | True | False | Total |
| if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; |
0 |
0 |
0 |
| if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; |
0 |
0 |
0 |
| if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; |
0 |
0 |
0 |
| if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; |
0 |
0 |
0 |
| if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; |
0 |
0 |
0 |
| if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; |
0 |
0 |
0 |
|
| 1648 |
|
| |
| 1649 |
0 |
| mr=i_min(abs(b-b0),abs(b-b1)); |
| 1650 |
0 |
| mg=i_min(abs(g-g0),abs(g-g1)); |
| 1651 |
0 |
| mb=i_min(abs(r-r0),abs(r-r1)); |
| 1652 |
|
| |
| 1653 |
0 |
| mr=PWR2(mr); |
| 1654 |
0 |
| mg=PWR2(mg); |
| 1655 |
0 |
| mb=PWR2(mb); |
| 1656 |
|
| |
| 1657 |
0 |
▶ | if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb; |
Branch: 4 branches
| Branch | True | False | Total |
| if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb; |
0 |
0 |
0 |
| if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb; |
0 |
0 |
0 |
| if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb; |
0 |
0 |
0 |
| if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb; |
0 |
0 |
0 |
|
| 1658 |
0 |
▶ | if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg; |
Branch: 4 branches
| Branch | True | False | Total |
| if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg; |
0 |
0 |
0 |
| if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg; |
0 |
0 |
0 |
| if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg; |
0 |
0 |
0 |
| if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg; |
0 |
0 |
0 |
|
| 1659 |
0 |
▶ | if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr; |
Branch: 4 branches
| Branch | True | False | Total |
| if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr; |
0 |
0 |
0 |
| if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr; |
0 |
0 |
0 |
| if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr; |
0 |
0 |
0 |
| if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr; |
0 |
0 |
0 |
|
| 1660 |
|
| |
| 1661 |
0 |
▶ | if (r0<=r && r<=r1) return mg+mb; |
Branch: 2 branches
| Branch | True | False | Total |
| if (r0<=r && r<=r1) return mg+mb; |
0 |
0 |
0 |
| if (r0<=r && r<=r1) return mg+mb; |
0 |
0 |
0 |
|
| 1662 |
0 |
▶ | if (g0<=g && g<=g1) return mr+mb; |
Branch: 2 branches
| Branch | True | False | Total |
| if (g0<=g && g<=g1) return mr+mb; |
0 |
0 |
0 |
| if (g0<=g && g<=g1) return mr+mb; |
0 |
0 |
0 |
|
| 1663 |
0 |
▶ | if (b0<=b && b<=b1) return mg+mr; |
Branch: 2 branches
| Branch | True | False | Total |
| if (b0<=b && b<=b1) return mg+mr; |
0 |
0 |
0 |
| if (b0<=b && b<=b1) return mg+mr; |
0 |
0 |
0 |
|
| 1664 |
|
| |
| 1665 |
0 |
| return mr+mg+mb; |
| 1666 |
|
| } |
| 1667 |
|
| |
| 1668 |
|
| static void transparent_threshold(i_quantize *, i_palidx *, i_img *, i_palidx); |
| 1669 |
|
| static void transparent_errdiff(i_quantize *, i_palidx *, i_img *, i_palidx); |
| 1670 |
|
| static void transparent_ordered(i_quantize *, i_palidx *, i_img *, i_palidx); |
| 1671 |
|
| |
| 1672 |
|
| /* |
| 1673 |
|
| =item i_quant_transparent(C<quant>, C<data>, C<img>, C<trans_index>) |
| 1674 |
|
| |
| 1675 |
|
| =category Image quantization |
| 1676 |
|
| |
| 1677 |
|
| Dither the alpha channel on C<img> into the palette indexes in |
| 1678 |
|
| C<data>. Pixels to be transparent are replaced with C<trans_pixel>. |
| 1679 |
|
| |
| 1680 |
|
| The method used depends on the tr_* members of C<quant>. |
| 1681 |
|
| |
| 1682 |
|
| =cut |
| 1683 |
|
| */ |
| 1684 |
|
| |
| 1685 |
|
| void |
| 1686 |
0 |
| i_quant_transparent(i_quantize *quant, i_palidx *data, i_img *img, |
| 1687 |
|
| i_palidx trans_index) |
| 1688 |
|
| { |
| 1689 |
0 |
| switch (quant->transp) { |
| 1690 |
0 |
| case tr_none: |
| 1691 |
0 |
| break; |
| 1692 |
|
| |
| 1693 |
0 |
| default: |
| 1694 |
0 |
| quant->tr_threshold = 128; |
| 1695 |
|
| /* fall through */ |
| 1696 |
0 |
| case tr_threshold: |
| 1697 |
0 |
| transparent_threshold(quant, data, img, trans_index); |
| 1698 |
0 |
| break; |
| 1699 |
|
| |
| 1700 |
0 |
| case tr_errdiff: |
| 1701 |
0 |
| transparent_errdiff(quant, data, img, trans_index); |
| 1702 |
0 |
| break; |
| 1703 |
|
| |
| 1704 |
0 |
| case tr_ordered: |
| 1705 |
0 |
| transparent_ordered(quant, data, img, trans_index); |
| 1706 |
0 |
| break; |
| 1707 |
|
| } |
| 1708 |
0 |
| } |
| 1709 |
|
| |
| 1710 |
|
| static void |
| 1711 |
0 |
| transparent_threshold(i_quantize *quant, i_palidx *data, i_img *img, |
| 1712 |
|
| i_palidx trans_index) |
| 1713 |
|
| { |
| 1714 |
|
| i_img_dim x, y; |
| 1715 |
0 |
| i_sample_t *line = mymalloc(img->xsize * sizeof(i_sample_t)); |
| 1716 |
0 |
▶ | int trans_chan = img->channels > 2 ? 3 : 1; |
Branch: 1 branch
| Branch | True | False | Total |
| int trans_chan = img->channels > 2 ? 3 : 1; |
0 |
0 |
0 |
|
| 1717 |
|
| |
| 1718 |
0 |
▶ | for (y = 0; y < img->ysize; ++y) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (y = 0; y < img->ysize; ++y) { |
0 |
0 |
0 |
|
| 1719 |
0 |
| i_gsamp(img, 0, img->xsize, y, line, &trans_chan, 1); |
| 1720 |
0 |
▶ | for (x = 0; x < img->xsize; ++x) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (x = 0; x < img->xsize; ++x) { |
0 |
0 |
0 |
|
| 1721 |
0 |
▶ | if (line[x] < quant->tr_threshold) |
Branch: 1 branch
| Branch | True | False | Total |
| if (line[x] < quant->tr_threshold) |
0 |
0 |
0 |
|
| 1722 |
0 |
| data[y*img->xsize+x] = trans_index; |
| 1723 |
|
| } |
| 1724 |
|
| } |
| 1725 |
0 |
| myfree(line); |
| 1726 |
0 |
| } |
| 1727 |
|
| |
| 1728 |
|
| static void |
| 1729 |
0 |
| transparent_errdiff(i_quantize *quant, i_palidx *data, i_img *img, |
| 1730 |
|
| i_palidx trans_index) |
| 1731 |
|
| { |
| 1732 |
|
| int *map; |
| 1733 |
|
| int index; |
| 1734 |
|
| int mapw, maph, mapo; |
| 1735 |
|
| int errw, *err, *errp; |
| 1736 |
|
| int difftotal, out, error; |
| 1737 |
|
| i_img_dim x, y, dx, dy; |
| 1738 |
|
| int i; |
| 1739 |
|
| i_sample_t *line; |
| 1740 |
0 |
▶ | int trans_chan = img->channels > 2 ? 3 : 1; |
Branch: 1 branch
| Branch | True | False | Total |
| int trans_chan = img->channels > 2 ? 3 : 1; |
0 |
0 |
0 |
|
| 1741 |
|
| |
| 1742 |
|
| /* no custom map for transparency (yet) */ |
| 1743 |
0 |
| index = quant->tr_errdiff & ed_mask; |
| 1744 |
0 |
▶ | if (index >= ed_custom) index = ed_floyd; |
Branch: 1 branch
| Branch | True | False | Total |
| if (index >= ed_custom) index = ed_floyd; |
0 |
0 |
0 |
|
| 1745 |
0 |
| map = maps[index].map; |
| 1746 |
0 |
| mapw = maps[index].width; |
| 1747 |
0 |
| maph = maps[index].height; |
| 1748 |
0 |
| mapo = maps[index].orig; |
| 1749 |
|
| |
| 1750 |
0 |
| errw = img->xsize+mapw-1; |
| 1751 |
0 |
| err = mymalloc(sizeof(*err) * maph * errw); |
| 1752 |
0 |
| errp = err+mapo; |
| 1753 |
0 |
| memset(err, 0, sizeof(*err) * maph * errw); |
| 1754 |
|
| |
| 1755 |
0 |
| line = mymalloc(img->xsize * sizeof(i_sample_t)); |
| 1756 |
0 |
| difftotal = 0; |
| 1757 |
0 |
▶ | for (i = 0; i < maph * mapw; ++i) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < maph * mapw; ++i) |
0 |
0 |
0 |
|
| 1758 |
0 |
| difftotal += map[i]; |
| 1759 |
0 |
▶ | for (y = 0; y < img->ysize; ++y) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (y = 0; y < img->ysize; ++y) { |
0 |
0 |
0 |
|
| 1760 |
0 |
| i_gsamp(img, 0, img->xsize, y, line, &trans_chan, 1); |
| 1761 |
0 |
▶ | for (x = 0; x < img->xsize; ++x) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (x = 0; x < img->xsize; ++x) { |
0 |
0 |
0 |
|
| 1762 |
0 |
| line[x] = g_sat(line[x]-errp[x]/difftotal); |
| 1763 |
0 |
▶ | if (line[x] < 128) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (line[x] < 128) { |
0 |
0 |
0 |
|
| 1764 |
0 |
| out = 0; |
| 1765 |
0 |
| data[y*img->xsize+x] = trans_index; |
| 1766 |
|
| } |
| 1767 |
|
| else { |
| 1768 |
0 |
| out = 255; |
| 1769 |
|
| } |
| 1770 |
0 |
| error = out - line[x]; |
| 1771 |
0 |
▶ | for (dx = 0; dx < mapw; ++dx) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (dx = 0; dx < mapw; ++dx) { |
0 |
0 |
0 |
|
| 1772 |
0 |
▶ | for (dy = 0; dy < maph; ++dy) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (dy = 0; dy < maph; ++dy) { |
0 |
0 |
0 |
|
| 1773 |
0 |
| errp[x+dx-mapo+dy*errw] += error * map[dx+mapw*dy]; |
| 1774 |
|
| } |
| 1775 |
|
| } |
| 1776 |
|
| } |
| 1777 |
|
| /* shift up the error matrix */ |
| 1778 |
0 |
▶ | for (dy = 0; dy < maph-1; ++dy) |
Branch: 1 branch
| Branch | True | False | Total |
| for (dy = 0; dy < maph-1; ++dy) |
0 |
0 |
0 |
|
| 1779 |
0 |
| memcpy(err+dy*errw, err+(dy+1)*errw, sizeof(*err)*errw); |
| 1780 |
0 |
| memset(err+(maph-1)*errw, 0, sizeof(*err)*errw); |
| 1781 |
|
| } |
| 1782 |
0 |
| myfree(err); |
| 1783 |
0 |
| myfree(line); |
| 1784 |
0 |
| } |
| 1785 |
|
| |
| 1786 |
|
| /* builtin ordered dither maps */ |
| 1787 |
|
| static unsigned char |
| 1788 |
|
| orddith_maps[][64] = |
| 1789 |
|
| { |
| 1790 |
|
| { /* random |
| 1791 |
|
| this is purely random - it's pretty awful |
| 1792 |
|
| */ |
| 1793 |
|
| 48, 72, 196, 252, 180, 92, 108, 52, |
| 1794 |
|
| 228, 176, 64, 8, 236, 40, 20, 164, |
| 1795 |
|
| 120, 128, 84, 116, 24, 28, 172, 220, |
| 1796 |
|
| 68, 0, 188, 124, 184, 224, 192, 104, |
| 1797 |
|
| 132, 100, 240, 200, 152, 160, 244, 44, |
| 1798 |
|
| 96, 204, 144, 16, 140, 56, 232, 216, |
| 1799 |
|
| 208, 4, 76, 212, 136, 248, 80, 168, |
| 1800 |
|
| 156, 88, 32, 112, 148, 12, 36, 60, |
| 1801 |
|
| }, |
| 1802 |
|
| { |
| 1803 |
|
| /* dot8 |
| 1804 |
|
| perl spot.perl '($x-3.5)*($x-3.5)+($y-3.5)*($y-3.5)' |
| 1805 |
|
| */ |
| 1806 |
|
| 240, 232, 200, 136, 140, 192, 228, 248, |
| 1807 |
|
| 220, 148, 100, 76, 80, 104, 152, 212, |
| 1808 |
|
| 180, 116, 56, 32, 36, 60, 120, 176, |
| 1809 |
|
| 156, 64, 28, 0, 8, 44, 88, 160, |
| 1810 |
|
| 128, 92, 24, 12, 4, 40, 68, 132, |
| 1811 |
|
| 184, 96, 48, 20, 16, 52, 108, 188, |
| 1812 |
|
| 216, 144, 112, 72, 84, 124, 164, 224, |
| 1813 |
|
| 244, 236, 196, 168, 172, 204, 208, 252, |
| 1814 |
|
| }, |
| 1815 |
|
| { /* dot4 |
| 1816 |
|
| perl spot.perl \ |
| 1817 |
|
| 'min(dist(1.5, 1.5),dist(5.5,1.5),dist(1.5,5.5),dist(5.5,5.5))' |
| 1818 |
|
| */ |
| 1819 |
|
| 196, 72, 104, 220, 200, 80, 112, 224, |
| 1820 |
|
| 76, 4, 24, 136, 84, 8, 32, 144, |
| 1821 |
|
| 108, 28, 52, 168, 116, 36, 56, 176, |
| 1822 |
|
| 216, 140, 172, 244, 228, 148, 180, 248, |
| 1823 |
|
| 204, 92, 124, 236, 192, 68, 96, 208, |
| 1824 |
|
| 88, 12, 44, 156, 64, 0, 16, 128, |
| 1825 |
|
| 120, 40, 60, 188, 100, 20, 48, 160, |
| 1826 |
|
| 232, 152, 184, 252, 212, 132, 164, 240, |
| 1827 |
|
| }, |
| 1828 |
|
| { /* hline |
| 1829 |
|
| perl spot.perl '$y-3' |
| 1830 |
|
| */ |
| 1831 |
|
| 160, 164, 168, 172, 176, 180, 184, 188, |
| 1832 |
|
| 128, 132, 136, 140, 144, 148, 152, 156, |
| 1833 |
|
| 32, 36, 40, 44, 48, 52, 56, 60, |
| 1834 |
|
| 0, 4, 8, 12, 16, 20, 24, 28, |
| 1835 |
|
| 64, 68, 72, 76, 80, 84, 88, 92, |
| 1836 |
|
| 96, 100, 104, 108, 112, 116, 120, 124, |
| 1837 |
|
| 192, 196, 200, 204, 208, 212, 216, 220, |
| 1838 |
|
| 224, 228, 232, 236, 240, 244, 248, 252, |
| 1839 |
|
| }, |
| 1840 |
|
| { /* vline |
| 1841 |
|
| perl spot.perl '$x-3' |
| 1842 |
|
| */ |
| 1843 |
|
| 180, 100, 40, 12, 44, 104, 184, 232, |
| 1844 |
|
| 204, 148, 60, 16, 64, 128, 208, 224, |
| 1845 |
|
| 212, 144, 76, 8, 80, 132, 216, 244, |
| 1846 |
|
| 160, 112, 68, 20, 84, 108, 172, 236, |
| 1847 |
|
| 176, 96, 72, 28, 88, 152, 188, 228, |
| 1848 |
|
| 200, 124, 92, 0, 32, 116, 164, 240, |
| 1849 |
|
| 168, 120, 36, 24, 48, 136, 192, 248, |
| 1850 |
|
| 196, 140, 52, 4, 56, 156, 220, 252, |
| 1851 |
|
| }, |
| 1852 |
|
| { /* slashline |
| 1853 |
|
| perl spot.perl '$y+$x-7' |
| 1854 |
|
| */ |
| 1855 |
|
| 248, 232, 224, 192, 140, 92, 52, 28, |
| 1856 |
|
| 240, 220, 196, 144, 108, 60, 12, 64, |
| 1857 |
|
| 216, 180, 148, 116, 76, 20, 80, 128, |
| 1858 |
|
| 204, 152, 104, 44, 16, 72, 100, 160, |
| 1859 |
|
| 164, 96, 68, 24, 56, 112, 168, 176, |
| 1860 |
|
| 124, 40, 8, 36, 88, 136, 184, 212, |
| 1861 |
|
| 84, 4, 32, 120, 156, 188, 228, 236, |
| 1862 |
|
| 0, 48, 132, 172, 200, 208, 244, 252, |
| 1863 |
|
| }, |
| 1864 |
|
| { /* backline |
| 1865 |
|
| perl spot.perl '$y-$x' |
| 1866 |
|
| */ |
| 1867 |
|
| 0, 32, 116, 172, 184, 216, 236, 252, |
| 1868 |
|
| 56, 8, 72, 132, 136, 200, 228, 240, |
| 1869 |
|
| 100, 36, 12, 40, 92, 144, 204, 220, |
| 1870 |
|
| 168, 120, 60, 16, 44, 96, 156, 176, |
| 1871 |
|
| 180, 164, 112, 48, 28, 52, 128, 148, |
| 1872 |
|
| 208, 192, 152, 88, 84, 20, 64, 104, |
| 1873 |
|
| 232, 224, 196, 140, 108, 68, 24, 76, |
| 1874 |
|
| 248, 244, 212, 188, 160, 124, 80, 4, |
| 1875 |
|
| }, |
| 1876 |
|
| { |
| 1877 |
|
| /* tiny |
| 1878 |
|
| good for display, bad for print |
| 1879 |
|
| hand generated |
| 1880 |
|
| */ |
| 1881 |
|
| 0, 128, 32, 192, 8, 136, 40, 200, |
| 1882 |
|
| 224, 64, 160, 112, 232, 72, 168, 120, |
| 1883 |
|
| 48, 144, 16, 208, 56, 152, 24, 216, |
| 1884 |
|
| 176, 96, 240, 80, 184, 104, 248, 88, |
| 1885 |
|
| 12, 140, 44, 204, 4, 132, 36, 196, |
| 1886 |
|
| 236, 76, 172, 124, 228, 68, 164, 116, |
| 1887 |
|
| 60, 156, 28, 220, 52, 148, 20, 212, |
| 1888 |
|
| 188, 108, 252, 92, 180, 100, 244, 84, |
| 1889 |
|
| }, |
| 1890 |
|
| }; |
| 1891 |
|
| |
| 1892 |
|
| static void |
| 1893 |
0 |
| transparent_ordered(i_quantize *quant, i_palidx *data, i_img *img, |
| 1894 |
|
| i_palidx trans_index) |
| 1895 |
|
| { |
| 1896 |
|
| unsigned char *spot; |
| 1897 |
|
| i_img_dim x, y; |
| 1898 |
|
| i_sample_t *line; |
| 1899 |
0 |
▶ | int trans_chan = img->channels > 2 ? 3 : 1; |
Branch: 1 branch
| Branch | True | False | Total |
| int trans_chan = img->channels > 2 ? 3 : 1; |
0 |
0 |
0 |
|
| 1900 |
0 |
▶ | if (quant->tr_orddith == od_custom) |
Branch: 1 branch
| Branch | True | False | Total |
| if (quant->tr_orddith == od_custom) |
0 |
0 |
0 |
|
| 1901 |
0 |
| spot = quant->tr_custom; |
| 1902 |
|
| else |
| 1903 |
0 |
| spot = orddith_maps[quant->tr_orddith]; |
| 1904 |
|
| |
| 1905 |
0 |
| line = mymalloc(img->xsize * sizeof(i_sample_t)); |
| 1906 |
0 |
▶ | for (y = 0; y < img->ysize; ++y) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (y = 0; y < img->ysize; ++y) { |
0 |
0 |
0 |
|
| 1907 |
0 |
| i_gsamp(img, 0, img->xsize, y, line, &trans_chan, 1); |
| 1908 |
0 |
▶ | for (x = 0; x < img->xsize; ++x) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (x = 0; x < img->xsize; ++x) { |
0 |
0 |
0 |
|
| 1909 |
0 |
▶ | if (line[x] < spot[(x&7)+(y&7)*8]) |
Branch: 1 branch
| Branch | True | False | Total |
| if (line[x] < spot[(x&7)+(y&7)*8]) |
0 |
0 |
0 |
|
| 1910 |
0 |
| data[x+y*img->xsize] = trans_index; |
| 1911 |
|
| } |
| 1912 |
|
| } |
| 1913 |
0 |
| myfree(line); |
| 1914 |
0 |
| } |
| 1915 |
|
| |