1 package com.bumptech.glide.gifencoder; 2 3 /* 4 * NeuQuant Neural-Net Quantization Algorithm 5 * ------------------------------------------ 6 * 7 * Copyright (c) 1994 Anthony Dekker 8 * 9 * NEUQUANT Neural-Net quantization algorithm by Anthony Dekker, 1994. See 10 * "Kohonen neural networks for optimal colour quantization" in "Network: 11 * Computation in Neural Systems" Vol. 5 (1994) pp 351-367. for a discussion of 12 * the algorithm. 13 * 14 * Any party obtaining a copy of these files from the author, directly or 15 * indirectly, is granted, free of charge, a full and unrestricted irrevocable, 16 * world-wide, paid up, royalty-free, nonexclusive right and license to deal in 17 * this software and documentation files (the "Software"), including without 18 * limitation the rights to use, copy, modify, merge, publish, distribute, 19 * sublicense, and/or sell copies of the Software, and to permit persons who 20 * receive copies from any such party to do so, with the only requirement being 21 * that this copyright notice remain intact. 22 */ 23 24 // Ported to Java 12/00 K Weiner 25 class NeuQuant { 26 27 protected static final int netsize = 256; /* number of colours used */ 28 29 /* four primes near 500 - assume no image has a length so large */ 30 /* that it is divisible by all four primes */ 31 protected static final int prime1 = 499; 32 33 protected static final int prime2 = 491; 34 35 protected static final int prime3 = 487; 36 37 protected static final int prime4 = 503; 38 39 protected static final int minpicturebytes = (3 * prime4); 40 41 /* minimum size for input image */ 42 43 /* 44 * Program Skeleton ---------------- [select samplefac in range 1..30] [read 45 * image from input file] pic = (unsigned char*) malloc(3*width*height); 46 * initnet(pic,3*width*height,samplefac); learn(); unbiasnet(); [write output 47 * image header, using writecolourmap(f)] inxbuild(); write output image using 48 * inxsearch(b,g,r) 49 */ 50 51 /* 52 * Network Definitions ------------------- 53 */ 54 55 protected static final int maxnetpos = (netsize - 1); 56 57 protected static final int netbiasshift = 4; /* bias for colour values */ 58 59 protected static final int ncycles = 100; /* no. of learning cycles */ 60 61 /* defs for freq and bias */ 62 protected static final int intbiasshift = 16; /* bias for fractions */ 63 64 protected static final int intbias = (((int) 1) << intbiasshift); 65 66 protected static final int gammashift = 10; /* gamma = 1024 */ 67 68 protected static final int gamma = (((int) 1) << gammashift); 69 70 protected static final int betashift = 10; 71 72 protected static final int beta = (intbias >> betashift); /* beta = 1/1024 */ 73 74 protected static final int betagamma = (intbias << (gammashift - betashift)); 75 76 /* defs for decreasing radius factor */ 77 protected static final int initrad = (netsize >> 3); /* 78 * for 256 cols, radius 79 * starts 80 */ 81 82 protected static final int radiusbiasshift = 6; /* at 32.0 biased by 6 bits */ 83 84 protected static final int radiusbias = (((int) 1) << radiusbiasshift); 85 86 protected static final int initradius = (initrad * radiusbias); /* 87 * and 88 * decreases 89 * by a 90 */ 91 92 protected static final int radiusdec = 30; /* factor of 1/30 each cycle */ 93 94 /* defs for decreasing alpha factor */ 95 protected static final int alphabiasshift = 10; /* alpha starts at 1.0 */ 96 97 protected static final int initalpha = (((int) 1) << alphabiasshift); 98 99 protected int alphadec; /* biased by 10 bits */ 100 101 /* radbias and alpharadbias used for radpower calculation */ 102 protected static final int radbiasshift = 8; 103 104 protected static final int radbias = (((int) 1) << radbiasshift); 105 106 protected static final int alpharadbshift = (alphabiasshift + radbiasshift); 107 108 protected static final int alpharadbias = (((int) 1) << alpharadbshift); 109 110 /* 111 * Types and Global Variables -------------------------- 112 */ 113 114 protected byte[] thepicture; /* the input image itself */ 115 116 protected int lengthcount; /* lengthcount = H*W*3 */ 117 118 protected int samplefac; /* sampling factor 1..30 */ 119 120 // typedef int pixel[4]; /* BGRc */ 121 protected int[][] network; /* the network itself - [netsize][4] */ 122 123 protected int[] netindex = new int[256]; 124 125 /* for network lookup - really 256 */ 126 127 protected int[] bias = new int[netsize]; 128 129 /* bias and freq arrays for learning */ 130 protected int[] freq = new int[netsize]; 131 132 protected int[] radpower = new int[initrad]; 133 134 /* radpower for precomputation */ 135 136 /* 137 * Initialise network in range (0,0,0) to (255,255,255) and set parameters 138 * ----------------------------------------------------------------------- 139 */ 140 public NeuQuant(byte[] thepic, int len, int sample) { 141 142 int i; 143 int[] p; 144 145 thepicture = thepic; 146 lengthcount = len; 147 samplefac = sample; 148 149 network = new int[netsize][]; 150 for (i = 0; i < netsize; i++) { 151 network[i] = new int[4]; 152 p = network[i]; 153 p[0] = p[1] = p[2] = (i << (netbiasshift + 8)) / netsize; 154 freq[i] = intbias / netsize; /* 1/netsize */ 155 bias[i] = 0; 156 } 157 } 158 159 public byte[] colorMap() { 160 byte[] map = new byte[3 * netsize]; 161 int[] index = new int[netsize]; 162 for (int i = 0; i < netsize; i++) 163 index[network[i][3]] = i; 164 int k = 0; 165 for (int i = 0; i < netsize; i++) { 166 int j = index[i]; 167 map[k++] = (byte) (network[j][0]); 168 map[k++] = (byte) (network[j][1]); 169 map[k++] = (byte) (network[j][2]); 170 } 171 return map; 172 } 173 174 /* 175 * Insertion sort of network and building of netindex[0..255] (to do after 176 * unbias) 177 * ------------------------------------------------------------------------------- 178 */ 179 public void inxbuild() { 180 181 int i, j, smallpos, smallval; 182 int[] p; 183 int[] q; 184 int previouscol, startpos; 185 186 previouscol = 0; 187 startpos = 0; 188 for (i = 0; i < netsize; i++) { 189 p = network[i]; 190 smallpos = i; 191 smallval = p[1]; /* index on g */ 192 /* find smallest in i..netsize-1 */ 193 for (j = i + 1; j < netsize; j++) { 194 q = network[j]; 195 if (q[1] < smallval) { /* index on g */ 196 smallpos = j; 197 smallval = q[1]; /* index on g */ 198 } 199 } 200 q = network[smallpos]; 201 /* swap p (i) and q (smallpos) entries */ 202 if (i != smallpos) { 203 j = q[0]; 204 q[0] = p[0]; 205 p[0] = j; 206 j = q[1]; 207 q[1] = p[1]; 208 p[1] = j; 209 j = q[2]; 210 q[2] = p[2]; 211 p[2] = j; 212 j = q[3]; 213 q[3] = p[3]; 214 p[3] = j; 215 } 216 /* smallval entry is now in position i */ 217 if (smallval != previouscol) { 218 netindex[previouscol] = (startpos + i) >> 1; 219 for (j = previouscol + 1; j < smallval; j++) 220 netindex[j] = i; 221 previouscol = smallval; 222 startpos = i; 223 } 224 } 225 netindex[previouscol] = (startpos + maxnetpos) >> 1; 226 for (j = previouscol + 1; j < 256; j++) 227 netindex[j] = maxnetpos; /* really 256 */ 228 } 229 230 /* 231 * Main Learning Loop ------------------ 232 */ 233 public void learn() { 234 235 int i, j, b, g, r; 236 int radius, rad, alpha, step, delta, samplepixels; 237 byte[] p; 238 int pix, lim; 239 240 if (lengthcount < minpicturebytes) 241 samplefac = 1; 242 alphadec = 30 + ((samplefac - 1) / 3); 243 p = thepicture; 244 pix = 0; 245 lim = lengthcount; 246 samplepixels = lengthcount / (3 * samplefac); 247 delta = samplepixels / ncycles; 248 alpha = initalpha; 249 radius = initradius; 250 251 rad = radius >> radiusbiasshift; 252 if (rad <= 1) 253 rad = 0; 254 for (i = 0; i < rad; i++) 255 radpower[i] = alpha * (((rad * rad - i * i) * radbias) / (rad * rad)); 256 257 // fprintf(stderr,"beginning 1D learning: initial radius=%d\n", rad); 258 259 if (lengthcount < minpicturebytes) 260 step = 3; 261 else if ((lengthcount % prime1) != 0) 262 step = 3 * prime1; 263 else { 264 if ((lengthcount % prime2) != 0) 265 step = 3 * prime2; 266 else { 267 if ((lengthcount % prime3) != 0) 268 step = 3 * prime3; 269 else 270 step = 3 * prime4; 271 } 272 } 273 274 i = 0; 275 while (i < samplepixels) { 276 b = (p[pix + 0] & 0xff) << netbiasshift; 277 g = (p[pix + 1] & 0xff) << netbiasshift; 278 r = (p[pix + 2] & 0xff) << netbiasshift; 279 j = contest(b, g, r); 280 281 altersingle(alpha, j, b, g, r); 282 if (rad != 0) 283 alterneigh(rad, j, b, g, r); /* alter neighbours */ 284 285 pix += step; 286 if (pix >= lim) 287 pix -= lengthcount; 288 289 i++; 290 if (delta == 0) 291 delta = 1; 292 if (i % delta == 0) { 293 alpha -= alpha / alphadec; 294 radius -= radius / radiusdec; 295 rad = radius >> radiusbiasshift; 296 if (rad <= 1) 297 rad = 0; 298 for (j = 0; j < rad; j++) 299 radpower[j] = alpha * (((rad * rad - j * j) * radbias) / (rad * rad)); 300 } 301 } 302 // fprintf(stderr,"finished 1D learning: final alpha=%f 303 // !\n",((float)alpha)/initalpha); 304 } 305 306 /* 307 * Search for BGR values 0..255 (after net is unbiased) and return colour 308 * index 309 * ---------------------------------------------------------------------------- 310 */ 311 public int map(int b, int g, int r) { 312 313 int i, j, dist, a, bestd; 314 int[] p; 315 int best; 316 317 bestd = 1000; /* biggest possible dist is 256*3 */ 318 best = -1; 319 i = netindex[g]; /* index on g */ 320 j = i - 1; /* start at netindex[g] and work outwards */ 321 322 while ((i < netsize) || (j >= 0)) { 323 if (i < netsize) { 324 p = network[i]; 325 dist = p[1] - g; /* inx key */ 326 if (dist >= bestd) 327 i = netsize; /* stop iter */ 328 else { 329 i++; 330 if (dist < 0) 331 dist = -dist; 332 a = p[0] - b; 333 if (a < 0) 334 a = -a; 335 dist += a; 336 if (dist < bestd) { 337 a = p[2] - r; 338 if (a < 0) 339 a = -a; 340 dist += a; 341 if (dist < bestd) { 342 bestd = dist; 343 best = p[3]; 344 } 345 } 346 } 347 } 348 if (j >= 0) { 349 p = network[j]; 350 dist = g - p[1]; /* inx key - reverse dif */ 351 if (dist >= bestd) 352 j = -1; /* stop iter */ 353 else { 354 j--; 355 if (dist < 0) 356 dist = -dist; 357 a = p[0] - b; 358 if (a < 0) 359 a = -a; 360 dist += a; 361 if (dist < bestd) { 362 a = p[2] - r; 363 if (a < 0) 364 a = -a; 365 dist += a; 366 if (dist < bestd) { 367 bestd = dist; 368 best = p[3]; 369 } 370 } 371 } 372 } 373 } 374 return (best); 375 } 376 377 public byte[] process() { 378 learn(); 379 unbiasnet(); 380 inxbuild(); 381 return colorMap(); 382 } 383 384 /* 385 * Unbias network to give byte values 0..255 and record position i to prepare 386 * for sort 387 * ----------------------------------------------------------------------------------- 388 */ 389 public void unbiasnet() { 390 391 int i, j; 392 393 for (i = 0; i < netsize; i++) { 394 network[i][0] >>= netbiasshift; 395 network[i][1] >>= netbiasshift; 396 network[i][2] >>= netbiasshift; 397 network[i][3] = i; /* record colour no */ 398 } 399 } 400 401 /* 402 * Move adjacent neurons by precomputed alpha*(1-((i-j)^2/[r]^2)) in 403 * radpower[|i-j|] 404 * --------------------------------------------------------------------------------- 405 */ 406 protected void alterneigh(int rad, int i, int b, int g, int r) { 407 408 int j, k, lo, hi, a, m; 409 int[] p; 410 411 lo = i - rad; 412 if (lo < -1) 413 lo = -1; 414 hi = i + rad; 415 if (hi > netsize) 416 hi = netsize; 417 418 j = i + 1; 419 k = i - 1; 420 m = 1; 421 while ((j < hi) || (k > lo)) { 422 a = radpower[m++]; 423 if (j < hi) { 424 p = network[j++]; 425 try { 426 p[0] -= (a * (p[0] - b)) / alpharadbias; 427 p[1] -= (a * (p[1] - g)) / alpharadbias; 428 p[2] -= (a * (p[2] - r)) / alpharadbias; 429 } catch (Exception e) { 430 } // prevents 1.3 miscompilation 431 } 432 if (k > lo) { 433 p = network[k--]; 434 try { 435 p[0] -= (a * (p[0] - b)) / alpharadbias; 436 p[1] -= (a * (p[1] - g)) / alpharadbias; 437 p[2] -= (a * (p[2] - r)) / alpharadbias; 438 } catch (Exception e) { 439 } 440 } 441 } 442 } 443 444 /* 445 * Move neuron i towards biased (b,g,r) by factor alpha 446 * ---------------------------------------------------- 447 */ 448 protected void altersingle(int alpha, int i, int b, int g, int r) { 449 450 /* alter hit neuron */ 451 int[] n = network[i]; 452 n[0] -= (alpha * (n[0] - b)) / initalpha; 453 n[1] -= (alpha * (n[1] - g)) / initalpha; 454 n[2] -= (alpha * (n[2] - r)) / initalpha; 455 } 456 457 /* 458 * Search for biased BGR values ---------------------------- 459 */ 460 protected int contest(int b, int g, int r) { 461 462 /* finds closest neuron (min dist) and updates freq */ 463 /* finds best neuron (min dist-bias) and returns position */ 464 /* for frequently chosen neurons, freq[i] is high and bias[i] is negative */ 465 /* bias[i] = gamma*((1/netsize)-freq[i]) */ 466 467 int i, dist, a, biasdist, betafreq; 468 int bestpos, bestbiaspos, bestd, bestbiasd; 469 int[] n; 470 471 bestd = ~(((int) 1) << 31); 472 bestbiasd = bestd; 473 bestpos = -1; 474 bestbiaspos = bestpos; 475 476 for (i = 0; i < netsize; i++) { 477 n = network[i]; 478 dist = n[0] - b; 479 if (dist < 0) 480 dist = -dist; 481 a = n[1] - g; 482 if (a < 0) 483 a = -a; 484 dist += a; 485 a = n[2] - r; 486 if (a < 0) 487 a = -a; 488 dist += a; 489 if (dist < bestd) { 490 bestd = dist; 491 bestpos = i; 492 } 493 biasdist = dist - ((bias[i]) >> (intbiasshift - netbiasshift)); 494 if (biasdist < bestbiasd) { 495 bestbiasd = biasdist; 496 bestbiaspos = i; 497 } 498 betafreq = (freq[i] >> betashift); 499 freq[i] -= betafreq; 500 bias[i] += (betafreq << gammashift); 501 } 502 freq[bestpos] += beta; 503 bias[bestpos] -= betagamma; 504 return (bestbiaspos); 505 } 506 } 507
