Skip to content

Interactive interface for browsing global, full-resolution satellite imagery

12.1 KB
Raw Blame
/*
  NeuQuant.js
  ===========
*/

/*
 * NeuQuant Neural-Net Quantization Algorithm
 * ------------------------------------------
 *
 * Copyright (c) 1994 Anthony Dekker
 *
 * NEUQUANT Neural-Net quantization algorithm by Anthony Dekker, 1994. See
 * "Kohonen neural networks for optimal colour quantization" in "Network:
 * Computation in Neural Systems" Vol. 5 (1994) pp 351-367. for a discussion of
 * the algorithm.
 *
 * Any party obtaining a copy of these files from the author, directly or
 * indirectly, is granted, free of charge, a full and unrestricted irrevocable,
 * world-wide, paid up, royalty-free, nonexclusive right and license to deal in
 * this software and documentation files (the "Software"), including without
 * limitation the rights to use, copy, modify, merge, publish, distribute,
 * sublicense, and/or sell copies of the Software, and to permit persons who
 * receive copies from any such party to do so, with the only requirement being
 * that this copyright notice remain intact.
 */

/*
 * This class handles Neural-Net quantization algorithm
 * @author Kevin Weiner (original Java version - [email protected])
 * @author Thibault Imbert (AS3 version - bytearray.org)
 * @version 0.1 AS3 implementation
 * @version 0.2 JS->AS3 "translation" by antimatter15
 * @version 0.3 JS clean up + using modern JS idioms by sole - http://soledadpenades.com
 * Also implement fix in color conversion described at http://stackoverflow.com/questions/16371712/neuquant-js-javascript-color-quantization-hidden-bug-in-js-conversion
 */

export default function NeuQuant() {
  const netsize = 256; // number of colours used

  // four primes near 500 - assume no image has a length so large
  // that it is divisible by all four primes
  const prime1 = 499;
  const prime2 = 491;
  const prime3 = 487;
  const prime4 = 503;

  // minimum size for input image
  const minpicturebytes = 3 * prime4;

  // Network Definitions

  const maxnetpos = netsize - 1;
  const netbiasshift = 4; // bias for colour values
  const ncycles = 100; // no. of learning cycles

  // defs for freq and bias
  const intbiasshift = 16; // bias for fractions
  const intbias = 1 << intbiasshift;
  const gammashift = 10; // gamma = 1024
  const gamma = 1 << gammashift;
  const betashift = 10;
  const beta = intbias >> betashift; // beta = 1/1024
  const betagamma = intbias << (gammashift - betashift);

  // defs for decreasing radius factor
  // For 256 colors, radius starts at 32.0 biased by 6 bits
  // and decreases by a factor of 1/30 each cycle
  const initrad = netsize >> 3;
  const radiusbiasshift = 6;
  const radiusbias = 1 << radiusbiasshift;
  const initradius = initrad * radiusbias;
  const radiusdec = 30;

  // defs for decreasing alpha factor
  // Alpha starts at 1.0 biased by 10 bits
  const alphabiasshift = 10;
  const initalpha = 1 << alphabiasshift;
  let alphadec;

  // radbias and alpharadbias used for radpower calculation
  const radbiasshift = 8;
  const radbias = 1 << radbiasshift;
  const alpharadbshift = alphabiasshift + radbiasshift;
  const alpharadbias = 1 << alpharadbshift;

  // Input image
  let thepicture;
  // Height * Width * 3
  let lengthcount;
  // Sampling factor 1..30
  let samplefac;

  // The network itself
  let network;
  const netindex = [];

  // for network lookup - really 256
  const bias = [];

  // bias and freq arrays for learning
  const freq = [];
  const radpower = [];

  function NeuQuantConstructor(thepic, len, sample) {
    let i;
    let p;

    thepicture = thepic;
    lengthcount = len;
    samplefac = sample;

    network = new Array(netsize);

    for (i = 0; i < netsize; i++) {
      network[i] = new Array(4);
      p = network[i];
      p[0] = p[1] = p[2] = ((i << (netbiasshift + 8)) / netsize) | 0;
      freq[i] = (intbias / netsize) | 0; // 1 / netsize
      bias[i] = 0;
    }
  }

  function colorMap() {
    const map = [];
    const index = new Array(netsize);
    for (let i = 0; i < netsize; i++) index[network[i][3]] = i;
    let k = 0;
    for (let l = 0; l < netsize; l++) {
      const j = index[l];
      map[k++] = network[j][0];
      map[k++] = network[j][1];
      map[k++] = network[j][2];
    }
    return map;
  }

  // Insertion sort of network and building of netindex[0..255]
  // (to do after unbias)
  function inxbuild() {
    let i;
    let j;
    let smallpos;
    let smallval;
    let p;
    let q;
    let previouscol;
    let startpos;

    previouscol = 0;
    startpos = 0;

    for (i = 0; i < netsize; i++) {
      p = network[i];
      smallpos = i;
      smallval = p[1]; // index on g
      // find smallest in i..netsize-1
      for (j = i + 1; j < netsize; j++) {
        q = network[j];

        if (q[1] < smallval) {
          // index on g
          smallpos = j;
          smallval = q[1]; // index on g
        }
      }

      q = network[smallpos];

      // swap p (i) and q (smallpos) entries
      if (i != smallpos) {
        j = q[0];
        q[0] = p[0];
        p[0] = j;
        j = q[1];
        q[1] = p[1];
        p[1] = j;
        j = q[2];
        q[2] = p[2];
        p[2] = j;
        j = q[3];
        q[3] = p[3];
        p[3] = j;
      }

      // smallval entry is now in position i
      if (smallval != previouscol) {
        netindex[previouscol] = (startpos + i) >> 1;

        for (j = previouscol + 1; j < smallval; j++) {
          netindex[j] = i;
        }

        previouscol = smallval;
        startpos = i;
      }
    }

    netindex[previouscol] = (startpos + maxnetpos) >> 1;
    for (j = previouscol + 1; j < 256; j++) {
      netindex[j] = maxnetpos; // really 256
    }
  }

  // Main Learning Loop

  function learn() {
    let i;
    let j;
    let b;
    let g;
    let r;
    let radius;
    let rad;
    let alpha;
    let step;
    let delta;
    let samplepixels;
    let p;
    let pix;
    let lim;

    if (lengthcount < minpicturebytes) {
      samplefac = 1;
    }

    alphadec = 30 + (samplefac - 1) / 3;
    p = thepicture;
    pix = 0;
    lim = lengthcount;
    samplepixels = lengthcount / (3 * samplefac);
    delta = (samplepixels / ncycles) | 0;
    alpha = initalpha;
    radius = initradius;

    rad = radius >> radiusbiasshift;
    if (rad <= 1) {
      rad = 0;
    }

    for (i = 0; i < rad; i++) {
      radpower[i] = alpha * (((rad * rad - i * i) * radbias) / (rad * rad));
    }

    if (lengthcount < minpicturebytes) {
      step = 3;
    } else if (lengthcount % prime1 !== 0) {
      step = 3 * prime1;
    } else if (lengthcount % prime2 !== 0) {
      step = 3 * prime2;
    } else if (lengthcount % prime3 !== 0) {
      step = 3 * prime3;
    } else {
      step = 3 * prime4;
    }

    i = 0;

    while (i < samplepixels) {
      b = (p[pix + 0] & 0xff) << netbiasshift;
      g = (p[pix + 1] & 0xff) << netbiasshift;
      r = (p[pix + 2] & 0xff) << netbiasshift;
      j = contest(b, g, r);

      altersingle(alpha, j, b, g, r);

      if (rad !== 0) {
        // Alter neighbours
        alterneigh(rad, j, b, g, r);
      }

      pix += step;

      if (pix >= lim) {
        pix -= lengthcount;
      }

      i++;

      if (delta === 0) {
        delta = 1;
      }

      if (i % delta === 0) {
        alpha -= alpha / alphadec;
        radius -= radius / radiusdec;
        rad = radius >> radiusbiasshift;

        if (rad <= 1) {
          rad = 0;
        }

        for (j = 0; j < rad; j++) {
          radpower[j] = alpha * (((rad * rad - j * j) * radbias) / (rad * rad));
        }
      }
    }
  }

  // Search for BGR values 0..255 (after net is unbiased) and return colour index
  function map(b, g, r) {
    let i;
    let j;
    let dist;
    let a;
    let bestd;
    let p;
    let best;

    // Biggest possible distance is 256 * 3
    bestd = 1000;
    best = -1;
    i = netindex[g]; // index on g
    j = i - 1; // start at netindex[g] and work outwards

    while (i < netsize || j >= 0) {
      if (i < netsize) {
        p = network[i];

        dist = p[1] - g; // inx key

        if (dist >= bestd) {
          i = netsize; // stop iter
        } else {
          i++;

          if (dist < 0) {
            dist = -dist;
          }

          a = p[0] - b;

          if (a < 0) {
            a = -a;
          }

          dist += a;

          if (dist < bestd) {
            a = p[2] - r;

            if (a < 0) {
              a = -a;
            }

            dist += a;

            if (dist < bestd) {
              bestd = dist;
              best = p[3];
            }
          }
        }
      }

      if (j >= 0) {
        p = network[j];

        dist = g - p[1]; // inx key - reverse dif

        if (dist >= bestd) {
          j = -1; // stop iter
        } else {
          j--;
          if (dist < 0) {
            dist = -dist;
          }
          a = p[0] - b;
          if (a < 0) {
            a = -a;
          }
          dist += a;

          if (dist < bestd) {
            a = p[2] - r;
            if (a < 0) {
              a = -a;
            }
            dist += a;
            if (dist < bestd) {
              bestd = dist;
              best = p[3];
            }
          }
        }
      }
    }

    return best;
  }

  function process() {
    learn();
    unbiasnet();
    inxbuild();
    return colorMap();
  }

  // Unbias network to give byte values 0..255 and record position i
  // to prepare for sort
  function unbiasnet() {
    let i;
    let j;

    for (i = 0; i < netsize; i++) {
      network[i][0] >>= netbiasshift;
      network[i][1] >>= netbiasshift;
      network[i][2] >>= netbiasshift;
      network[i][3] = i; // record colour no
    }
  }

  // Move adjacent neurons by precomputed alpha*(1-((i-j)^2/[r]^2))
  // in radpower[|i-j|]
  function alterneigh(rad, i, b, g, r) {
    let j;
    let k;
    let lo;
    let hi;
    let a;
    let m;

    let p;

    lo = i - rad;
    if (lo < -1) {
      lo = -1;
    }

    hi = i + rad;

    if (hi > netsize) {
      hi = netsize;
    }

    j = i + 1;
    k = i - 1;
    m = 1;

    while (j < hi || k > lo) {
      a = radpower[m++];

      if (j < hi) {
        p = network[j++];

        try {
          p[0] -= ((a * (p[0] - b)) / alpharadbias) | 0;
          p[1] -= ((a * (p[1] - g)) / alpharadbias) | 0;
          p[2] -= ((a * (p[2] - r)) / alpharadbias) | 0;
        } catch (e) {}
      }

      if (k > lo) {
        p = network[k--];

        try {
          p[0] -= ((a * (p[0] - b)) / alpharadbias) | 0;
          p[1] -= ((a * (p[1] - g)) / alpharadbias) | 0;
          p[2] -= ((a * (p[2] - r)) / alpharadbias) | 0;
        } catch (e) {}
      }
    }
  }

  // Move neuron i towards biased (b,g,r) by factor alpha
  function altersingle(alpha, i, b, g, r) {
    // alter hit neuron
    const n = network[i];
    const alphaMult = alpha / initalpha;
    n[0] -= (alphaMult * (n[0] - b)) | 0;
    n[1] -= (alphaMult * (n[1] - g)) | 0;
    n[2] -= (alphaMult * (n[2] - r)) | 0;
  }

  // Search for biased BGR values
  function contest(b, g, r) {
    // finds closest neuron (min dist) and updates freq
    // finds best neuron (min dist-bias) and returns position
    // for frequently chosen neurons, freq[i] is high and bias[i] is negative
    // bias[i] = gamma*((1/netsize)-freq[i])

    let i;
    let dist;
    let a;
    let biasdist;
    let betafreq;
    let bestpos;
    let bestbiaspos;
    let bestd;
    let bestbiasd;
    let n;

    bestd = ~(1 << 31);
    bestbiasd = bestd;
    bestpos = -1;
    bestbiaspos = bestpos;

    for (i = 0; i < netsize; i++) {
      n = network[i];
      dist = n[0] - b;

      if (dist < 0) {
        dist = -dist;
      }

      a = n[1] - g;

      if (a < 0) {
        a = -a;
      }

      dist += a;

      a = n[2] - r;

      if (a < 0) {
        a = -a;
      }

      dist += a;

      if (dist < bestd) {
        bestd = dist;
        bestpos = i;
      }

      biasdist = dist - (bias[i] >> (intbiasshift - netbiasshift));

      if (biasdist < bestbiasd) {
        bestbiasd = biasdist;
        bestbiaspos = i;
      }

      betafreq = freq[i] >> betashift;
      freq[i] -= betafreq;
      bias[i] += betafreq << gammashift;
    }

    freq[bestpos] += beta;
    bias[bestpos] -= betagamma;
    return bestbiaspos;
  }

  NeuQuantConstructor.apply(this, arguments);

  const exports = {};
  exports.map = map;
  exports.process = process;

  return exports;
}