src_math_scissors.js

import {BucketQueue} from './bucketQueue';

// Pre-created to reduce allocation in inner loops
const __twothirdpi = (2 / (3 * Math.PI));

/**
 * Compute grey scale.
 *
 * @param {Array} data The input data.
 * @param {number} width The width of the output.
 * @param {number} height The height of the output.
 * @returns {object} A greyscale object.
 */
function computeGreyscale(data, width, height) {
  // Returns 2D augmented array containing greyscale data
  // Greyscale values found by averaging colour channels
  // Input should be in a flat RGBA array, with values between 0 and 255
  const greyscale = {
    data: []
  };

  // Compute actual values
  for (let y = 0; y < height; y++) {
    greyscale.data[y] = [];

    for (let x = 0; x < width; x++) {
      const p = (y * width + x) * 4;
      greyscale.data[y][x] = (data[p] + data[p + 1] + data[p + 2]) / (3 * 255);
    }
  }

  // Augment with convenience functions
  greyscale.dx = function (x, y) {
    if (x + 1 === this.data[y].length) {
      // If we're at the end, back up one
      x--;
    }
    return this.data[y][x + 1] - this.data[y][x];
  };

  greyscale.dy = function (x, y) {
    if (y + 1 === this.data.length) {
      // If we're at the end, back up one
      y--;
    }
    return this.data[y][x] - this.data[y + 1][x];
  };

  greyscale.gradMagnitude = function (x, y) {
    const dx = this.dx(x, y);
    const dy = this.dy(x, y);
    return Math.sqrt(dx * dx + dy * dy);
  };

  greyscale.laplace = function (x, y) {
    // Laplacian of Gaussian
    let lap = -16 * this.data[y][x];
    lap += this.data[y - 2][x];
    lap += this.data[y - 1][x - 1] +
      2 * this.data[y - 1][x] +
      this.data[y - 1][x + 1];
    lap += this.data[y][x - 2] +
      2 * this.data[y][x - 1] +
      2 * this.data[y][x + 1] +
      this.data[y][x + 2];
    lap += this.data[y + 1][x - 1] +
      2 * this.data[y + 1][x] +
      this.data[y + 1][x + 1];
    lap += this.data[y + 2][x];

    return lap;
  };

  return greyscale;
}

/**
 * Compute gradient.
 *
 * @param {object} greyscale The input greyscale.
 * @returns {object} A gradient object.
 */
function computeGradient(greyscale) {
  // Returns a 2D array of gradient magnitude values for greyscale. The values
  // are scaled between 0 and 1, and then flipped, so that it works as a cost
  // function.
  const gradient = [];

  let max = 0; // Maximum gradient found, for scaling purposes

  let x = 0;
  let y = 0;

  for (y = 0; y < greyscale.data.length - 1; y++) {
    gradient[y] = [];

    for (x = 0; x < greyscale.data[y].length - 1; x++) {
      gradient[y][x] = greyscale.gradMagnitude(x, y);
      max = Math.max(gradient[y][x], max);
    }

    gradient[y][greyscale.data[y].length - 1] =
      gradient[y][greyscale.data.length - 2];
  }

  gradient[greyscale.data.length - 1] = [];
  for (let i = 0; i < gradient[0].length; i++) {
    gradient[greyscale.data.length - 1][i] =
      gradient[greyscale.data.length - 2][i];
  }

  // Flip and scale.
  for (y = 0; y < gradient.length; y++) {
    for (x = 0; x < gradient[y].length; x++) {
      // @ts-ignore
      gradient[y][x] = 1 - (gradient[y][x] / max);
    }
  }

  return gradient;
}

/**
 * @param {object} greyscale The input greyscale.
 * @returns {object} A laplace object.
 */
function computeLaplace(greyscale) {
  // Returns a 2D array of Laplacian of Gaussian values
  const laplace = [];

  // Make the edges low cost here.

  laplace[0] = [];
  laplace[1] = [];
  for (let i = 1; i < greyscale.data.length; i++) {
    // Pad top, since we can't compute Laplacian
    laplace[0][i] = 1;
    laplace[1][i] = 1;
  }

  for (let y = 2; y < greyscale.data.length - 2; y++) {
    laplace[y] = [];
    // Pad left, ditto
    laplace[y][0] = 1;
    laplace[y][1] = 1;

    for (let x = 2; x < greyscale.data[y].length - 2; x++) {
      // Threshold needed to get rid of clutter.
      laplace[y][x] = (greyscale.laplace(x, y) > 0.33) ? 0 : 1;
    }

    // Pad right, ditto
    laplace[y][greyscale.data[y].length - 2] = 1;
    laplace[y][greyscale.data[y].length - 1] = 1;
  }

  laplace[greyscale.data.length - 2] = [];
  laplace[greyscale.data.length - 1] = [];
  for (let j = 1; j < greyscale.data.length; j++) {
    // Pad bottom, ditto
    laplace[greyscale.data.length - 2][j] = 1;
    laplace[greyscale.data.length - 1][j] = 1;
  }

  return laplace;
}

/**
 * Compute the X gradient.
 *
 * @param {object} greyscale The values.
 * @returns {Array} The gradient.
 */
function computeGradX(greyscale) {
  // Returns 2D array of x-gradient values for greyscale
  const gradX = [];

  for (let y = 0; y < greyscale.data.length; y++) {
    gradX[y] = [];

    for (let x = 0; x < greyscale.data[y].length - 1; x++) {
      gradX[y][x] = greyscale.dx(x, y);
    }

    gradX[y][greyscale.data[y].length - 1] =
      gradX[y][greyscale.data[y].length - 2];
  }

  return gradX;
}

/**
 * Compute the Y gradient.
 *
 * @param {object} greyscale The values.
 * @returns {Array} The gradient.
 */
function computeGradY(greyscale) {
  // Returns 2D array of y-gradient values for greyscale
  const gradY = [];

  for (let y = 0; y < greyscale.data.length - 1; y++) {
    gradY[y] = [];

    for (let x = 0; x < greyscale.data[y].length; x++) {
      gradY[y][x] = greyscale.dy(x, y);
    }
  }

  gradY[greyscale.data.length - 1] = [];
  for (let i = 0; i < greyscale.data[0].length; i++) {
    gradY[greyscale.data.length - 1][i] = gradY[greyscale.data.length - 2][i];
  }

  return gradY;
}

/**
 * Compute the gradient unit vector.
 *
 * @param {Array} gradX The X gradient.
 * @param {Array} gradY The Y gradient.
 * @param {number} px The point X.
 * @param {number} py The point Y.
 * @param {object} out The result.
 */
function gradUnitVector(gradX, gradY, px, py, out) {
  // Returns the gradient vector at (px,py), scaled to a magnitude of 1
  const ox = gradX[py][px];
  const oy = gradY[py][px];

  let gvm = Math.sqrt(ox * ox + oy * oy);
  gvm = Math.max(gvm, 1e-100); // To avoid possible divide-by-0 errors

  out.x = ox / gvm;
  out.y = oy / gvm;
}

/**
 * Compute the gradient direction.
 *
 * @param {Array} gradX The X gradient.
 * @param {Array} gradY The Y gradient.
 * @param {number} px The point X.
 * @param {number} py The point Y.
 * @param {number} qx The q X.
 * @param {number} qy The q Y.
 * @returns {number} The direction.
 */
function gradDirection(gradX, gradY, px, py, qx, qy) {
  const __dgpuv = {x: -1, y: -1};
  const __gdquv = {x: -1, y: -1};
  // Compute the gradiant direction, in radians, between to points
  gradUnitVector(gradX, gradY, px, py, __dgpuv);
  gradUnitVector(gradX, gradY, qx, qy, __gdquv);

  let dp = __dgpuv.y * (qx - px) - __dgpuv.x * (qy - py);
  let dq = __gdquv.y * (qx - px) - __gdquv.x * (qy - py);

  // Make sure dp is positive, to keep things consistant
  if (dp < 0) {
    dp = -dp;
    dq = -dq;
  }

  if (px !== qx && py !== qy) {
    // We're going diagonally between pixels
    dp *= Math.SQRT1_2;
    dq *= Math.SQRT1_2;
  }

  return __twothirdpi * (Math.acos(dp) + Math.acos(dq));
}

/**
 * Compute the sides.
 *
 * @param {number} dist The distance.
 * @param {Array} gradX The X gradient.
 * @param {Array} gradY The Y gradient.
 * @param {object} greyscale The value.
 * @returns {object} The sides.
 */
function computeSides(dist, gradX, gradY, greyscale) {
  // Returns 2 2D arrays, containing inside and outside greyscale values.
  // These greyscale values are the intensity just a little bit along the
  // gradient vector, in either direction, from the supplied point. These
  // values are used when using active-learning Intelligent Scissors

  const sides = {};
  sides.inside = [];
  sides.outside = [];

  const guv = {x: -1, y: -1}; // Current gradient unit vector

  for (let y = 0; y < gradX.length; y++) {
    sides.inside[y] = [];
    sides.outside[y] = [];

    for (let x = 0; x < gradX[y].length; x++) {
      gradUnitVector(gradX, gradY, x, y, guv);

      //(x, y) rotated 90 = (y, -x)

      let ix = Math.round(x + dist * guv.y);
      let iy = Math.round(y - dist * guv.x);
      let ox = Math.round(x - dist * guv.y);
      let oy = Math.round(y + dist * guv.x);

      ix = Math.max(Math.min(ix, gradX[y].length - 1), 0);
      ox = Math.max(Math.min(ox, gradX[y].length - 1), 0);
      iy = Math.max(Math.min(iy, gradX.length - 1), 0);
      oy = Math.max(Math.min(oy, gradX.length - 1), 0);

      sides.inside[y][x] = greyscale.data[iy][ix];
      sides.outside[y][x] = greyscale.data[oy][ox];
    }
  }

  return sides;
}

/**
 * Gaussian blur an input buffer.
 *
 * @param {Array} buffer The input buffer.
 * @param {Array} out The result.
 */
function gaussianBlur(buffer, out) {
  // Smooth values over to fill in gaps in the mapping
  out[0] = 0.4 * buffer[0] + 0.5 * buffer[1] + 0.1 * buffer[1];
  out[1] = 0.25 * buffer[0] + 0.4 * buffer[1] + 0.25 * buffer[2] +
    0.1 * buffer[3];

  for (let i = 2; i < buffer.length - 2; i++) {
    out[i] = 0.05 * buffer[i - 2] + 0.25 * buffer[i - 1] +
      0.4 * buffer[i] + 0.25 * buffer[i + 1] + 0.05 * buffer[i + 2];
  }

  const len = buffer.length;
  out[len - 2] = 0.25 * buffer[len - 1] + 0.4 * buffer[len - 2] +
    0.25 * buffer[len - 3] + 0.1 * buffer[len - 4];
  out[len - 1] = 0.4 * buffer[len - 1] + 0.5 * buffer[len - 2] +
    0.1 * buffer[len - 3];
}

/**
 * Scissors.
 *
 * Ref: Eric N. Mortensen, William A. Barrett, Interactive Segmentation with
 *   Intelligent Scissors, Graphical Models and Image Processing, Volume 60,
 *   Issue 5, September 1998, Pages 349-384, ISSN 1077-3169,
 *   DOI: 10.1006/gmip.1998.0480.
 *
 * See: {@link http://www.sciencedirect.com/science/article/B6WG4-45JB8WN-9/2/6fe59d8089fd1892c2bfb82283065579}.
 *
 * Highly inspired from: {@link http://code.google.com/p/livewire-javascript/}.
 */
export class Scissors {

  constructor() {
    this.width = -1;
    this.height = -1;

    this.curPoint = null; // Corrent point we're searching on.
    this.searchGranBits = 8; // Bits of resolution for BucketQueue.
    this.searchGran = 1 << this.searchGranBits; //bits.
    this.pointsPerPost = 500;

    // Precomputed image data. All in ranges 0 >= x >= 1 and
    //   all inverted (1 - x).
    this.greyscale = null; // Greyscale of image
    this.laplace = null; // Laplace zero-crossings (either 0 or 1).
    this.gradient = null; // Gradient magnitudes.
    this.gradX = null; // X-differences.
    this.gradY = null; // Y-differences.

    // Matrix mapping point => parent along shortest-path to root.
    this.parents = null;

    this.working = false; // Currently computing shortest paths?

    // Begin Training:
    this.trained = false;
    this.trainingPoints = null;

    this.edgeWidth = 2;
    this.trainingLength = 32;

    this.edgeGran = 256;
    this.edgeTraining = null;

    this.gradPointsNeeded = 32;
    this.gradGran = 1024;
    this.gradTraining = null;

    this.insideGran = 256;
    this.insideTraining = null;

    this.outsideGran = 256;
    this.outsideTraining = null;
  }
  // End Training


  // Begin training methods //
  getTrainingIdx(granularity, value) {
    return Math.round((granularity - 1) * value);
  }

  getTrainedEdge(edge) {
    return this.edgeTraining[this.getTrainingIdx(this.edgeGran, edge)];
  }

  getTrainedGrad(grad) {
    return this.gradTraining[this.getTrainingIdx(this.gradGran, grad)];
  }

  getTrainedInside(inside) {
    return this.insideTraining[this.getTrainingIdx(this.insideGran, inside)];
  }

  getTrainedOutside(outside) {
    return this.outsideTraining[this.getTrainingIdx(this.outsideGran, outside)];
  }
  // End training methods //

  setWorking(working) {
    // Sets working flag
    this.working = working;
  }

  setDimensions(width, height) {
    this.width = width;
    this.height = height;
  }

  setData(data) {
    if (this.width === -1 || this.height === -1) {
      // The width and height should have already been set
      throw new Error('Dimensions have not been set.');
    }

    this.greyscale = computeGreyscale(data, this.width, this.height);
    this.laplace = computeLaplace(this.greyscale);
    this.gradient = computeGradient(this.greyscale);
    this.gradX = computeGradX(this.greyscale);
    this.gradY = computeGradY(this.greyscale);

    const sides = computeSides(
      this.edgeWidth, this.gradX, this.gradY, this.greyscale);
    this.inside = sides.inside;
    this.outside = sides.outside;
    this.edgeTraining = [];
    this.gradTraining = [];
    this.insideTraining = [];
    this.outsideTraining = [];
  }

  findTrainingPoints(p) {
    // Grab the last handful of points for training
    const points = [];

    if (this.parents !== null) {
      for (let i = 0; i < this.trainingLength && p; i++) {
        points.push(p);
        p = this.parents[p.y][p.x];
      }
    }

    return points;
  }

  resetTraining() {
    this.trained = false; // Training is ignored with this flag set
  }

  doTraining(p) {
    // Compute training weights and measures
    this.trainingPoints = this.findTrainingPoints(p);

    if (this.trainingPoints.length < 8) {
      return; // Not enough points, I think. It might crash if length = 0.
    }

    const buffer = [];
    this.calculateTraining(
      buffer, this.edgeGran, this.greyscale, this.edgeTraining);
    this.calculateTraining(
      buffer, this.gradGran, this.gradient, this.gradTraining);
    this.calculateTraining(
      buffer, this.insideGran, this.inside, this.insideTraining);
    this.calculateTraining(
      buffer, this.outsideGran, this.outside, this.outsideTraining);

    if (this.trainingPoints.length < this.gradPointsNeeded) {
      // If we have two few training points, the gradient weight map might not
      // be smooth enough, so average with normal weights.
      this.addInStaticGrad(this.trainingPoints.length, this.gradPointsNeeded);
    }

    this.trained = true;
  }

  calculateTraining(
    buffer, granularity, input, output) {
    let i = 0;
    // Build a map of raw-weights to trained-weights by favoring input values
    buffer.length = granularity;
    for (i = 0; i < granularity; i++) {
      buffer[i] = 0;
    }

    let maxVal = 1;
    for (i = 0; i < this.trainingPoints.length; i++) {
      const p = this.trainingPoints[i];
      const idx = this.getTrainingIdx(granularity, input[p.y][p.x]);
      buffer[idx] += 1;

      maxVal = Math.max(maxVal, buffer[idx]);
    }

    // Invert and scale.
    for (i = 0; i < granularity; i++) {
      buffer[i] = 1 - buffer[i] / maxVal;
    }

    // Blur it, as suggested. Gets rid of static.
    gaussianBlur(buffer, output);
  }

  addInStaticGrad(have, need) {
    // Average gradient raw-weights to trained-weights map with standard weight
    // map so that we don't end up with something to spiky
    for (let i = 0; i < this.gradGran; i++) {
      this.gradTraining[i] = Math.min(
        this.gradTraining[i],
        1 - i * (need - have) / (need * this.gradGran)
      );
    }
  }

  gradDirection(px, py, qx, qy) {
    return gradDirection(this.gradX, this.gradY, px, py, qx, qy);
  }

  dist(px, py, qx, qy) {
    // The grand culmunation of most of the code: the weighted distance function
    let grad = this.gradient[qy][qx];

    if (px === qx || py === qy) {
      // The distance is Euclidean-ish; non-diagonal edges should be shorter
      grad *= Math.SQRT1_2;
    }

    const lap = this.laplace[qy][qx];
    const dir = this.gradDirection(px, py, qx, qy);

    if (this.trained) {
      // Apply training magic
      const gradT = this.getTrainedGrad(grad);
      const edgeT = this.getTrainedEdge(this.greyscale.data[py][px]);
      const insideT = this.getTrainedInside(this.inside[py][px]);
      const outsideT = this.getTrainedOutside(this.outside[py][px]);

      return 0.3 * gradT + 0.3 * lap + 0.1 * (dir + edgeT + insideT + outsideT);
    } else {
      // Normal weights
      return 0.43 * grad + 0.43 * lap + 0.11 * dir;
    }
  }

  adj(p) {
    const list = [];

    const sx = Math.max(p.x - 1, 0);
    const sy = Math.max(p.y - 1, 0);
    const ex = Math.min(p.x + 1, this.greyscale.data[0].length - 1);
    const ey = Math.min(p.y + 1, this.greyscale.data.length - 1);

    let idx = 0;
    for (let y = sy; y <= ey; y++) {
      for (let x = sx; x <= ex; x++) {
        if (x !== p.x || y !== p.y) {
          list[idx++] = {x: x, y: y};
        }
      }
    }

    return list;
  }

  #costFunction = (p) => {
    return Math.round(this.searchGran * this.cost[p.y][p.x]);
  };

  setPoint(sp) {
    this.setWorking(true);

    this.curPoint = sp;

    let x = 0;
    let y = 0;

    this.visited = [];
    for (y = 0; y < this.height; y++) {
      this.visited[y] = [];
      for (x = 0; x < this.width; x++) {
        this.visited[y][x] = false;
      }
    }

    this.parents = [];
    for (y = 0; y < this.height; y++) {
      this.parents[y] = [];
    }

    this.cost = [];
    for (y = 0; y < this.height; y++) {
      this.cost[y] = [];
      for (x = 0; x < this.width; x++) {
        this.cost[y][x] = Number.MAX_VALUE;
      }
    }
    this.cost[sp.y][sp.x] = 0;

    this.pq = new BucketQueue(this.searchGranBits, this.#costFunction);
    this.pq.push(sp);
  }

  doWork() {
    if (!this.working) {
      return;
    }

    this.timeout = null;

    let pointCount = 0;
    const newPoints = [];
    while (!this.pq.isEmpty() && pointCount < this.pointsPerPost) {
      const p = this.pq.pop();
      newPoints.push(p);
      newPoints.push(this.parents[p.y][p.x]);

      this.visited[p.y][p.x] = true;

      const adjList = this.adj(p);
      for (let i = 0; i < adjList.length; i++) {
        const q = adjList[i];

        const pqCost = this.cost[p.y][p.x] + this.dist(p.x, p.y, q.x, q.y);

        if (pqCost < this.cost[q.y][q.x]) {
          if (this.cost[q.y][q.x] !== Number.MAX_VALUE) {
            // Already in PQ, must remove it so we can re-add it.
            this.pq.remove(q);
          }

          this.cost[q.y][q.x] = pqCost;
          this.parents[q.y][q.x] = p;
          this.pq.push(q);
        }
      }

      pointCount++;
    }

    return newPoints;
  }

} // Scissors class