人脸识别增强的 LowPoly 图像风格化（其二）

/∗ Initialization ∗/
Initialize cluster centers Ck = [lk, ak, bk, xk, yk]T by
sampling pixels at regular grid steps S.
Move cluster centers to the lowest gradient position in a
3×3 neighborhood.
Set label l(i) = −1 for each pixel i.
Set distance d(i) = ∞ for each pixel i.
repeat
  /∗ Assignment ∗/
  for each cluster center Ck do
    for each pixel i in a 2S ×2S region around Ck do
      Compute the distance D between Ck and i.
      if D < d(i) then
        set d(i) = D
        set l(i) = k
      end if
    end for
  end for
  /∗ Update ∗/
  Compute new cluster centers.
  Compute residual error E.
until E ≤threshold

// the base class for superpixel algorithms
// TODO: generating polygons @reference: [pySNIC](https://github.com/MoritzWillig/pysnic)
const rgb2lab = require('../../share/color/rgb2lab');
const lab2rgb = require('../../share/color/lab2rgb');

class ClusteringSuperpixels {
  constructor(mat, step = 20, m = 25/* [1, 40] */, iters = 15) {
    // source Mat
    step = Math.round(step);
    m = Math.round(m);
    this.rgbMat = mat; // RGB
    const { cols, rows } = mat;
    // console.log(`image size: ${cols} x ${rows}`);
    this.width = cols;
    this.height = rows;
    this.size = cols * rows;
    // CIELab Mat
    this.labArray = Array(rows).fill().map(() => Array(cols).fill([]));
    this._rgb2lab(); // NOTICE this is much faster than cv.cvtColor
    // clustering parameters
    this.step = step; // center sampling step, for k-means iterates, k is loosely (with * height / step)
    this.m = m; // the constant m, for adjusting influence of LAB weight and xy weight, check the paper for details
    this.m_2 = m * m;
    this.compactness = m;
    this.step_2 = step * step;
    this.iters = iters;
  }

  computeContours() {
    const {
      height,
      width,
      clusters,
    } = this;
    const dx8 = [-1, -1, 0, 1, 1, 1, 0, -1];
    const dy8 = [0, -1, -1, -1, 0, 1, 1, 1];
    const contours = [];
    const isTaken = Array(height).fill().map(() => Array(width).fill(false));

    // contours
    for (let i = 0; i < height; i++) {
      for (let j = 0; j < width; j++) {
        let nr_p = 0;
        // Compare the pixel to its 8 neighbors
        for (let k = 0; k < 8; k++) {
          const x = j + dx8[k];
          const y = i + dy8[k];
          if (x >= 0 && x < width && y >= 0 && y < height) {
            // console.log(y, isTaken[y], clusters[y]);
            if (isTaken[y][x] === false && clusters[i][j] !== clusters[y][x]) {
              nr_p += 1;
            }
          }
        }
        // Add the pixel to the contour list if desired
        if (nr_p >= 2) {
          const p = { x: j, y: i };
          contours.push(p);
          isTaken[i][j] = true;
        }
      }
    }
    this.contours = contours;
    // console.log(`we have ${contours.length} edge points`);
  }

  _rgb2lab() {
    const {
      rgbMat,
      labArray,
      width,
      height
    } = this;
    for (let x = 0; x < width; x++) {
      for (let y = 0; y < height; y++) {
        const rgb = rgbMat.ucharPtr(y, x);
        labArray[y][x] = rgb2lab(rgb);
      }
    }
  }

  _setColor2Points(mat, points, color = [255, 255, 255]) {
    for (let i = 0; i < points.length; i++) this._setColor2Point(mat, points[i], color);
  }

  _setColor2Point(mat, point, color = [255, 255, 255]) {
    const [r, g, b] = color;
    const { x, y } = point;
    const data = mat.ucharPtr(y, x);
    data[0] = r;
    data[1] = g;
    data[2] = b;
  }

  _normalizeCenterChannels() {
    const { centers } = this;
    for (let j = 0; j < centers.length; j++) {
      const center = centers[j];
      const count = center.count;
      // eslint-disable-next-line no-continue
      if (count === 0) continue;
      // NOTICE int is much faster in this case
      // center.l = Math.round(center.l / count);
      // center.a = Math.round(center.a / count);
      // center.b = Math.round(center.b / count);
      center.l /= count;
      center.a /= count;
      center.b /= count;
      center.x = Math.round(center.x / count);
      center.y = Math.round(center.y / count);
    }
  }

  _clearCentersAndFillRGBChannels() {
    let { centers } = this;
    // removes invalid centers
    centers = centers.filter((c) => c.count);
    // get rgb colors
    centers.forEach((c) => {
      const [r, g, b] = lab2rgb([c.l, c.a, c.b]);
      c.r = r;
      c.g = g;
      c.b = b;
    });
    this.centers = centers;
  }

  _findLocalMinimum(x, y) {
    // NOTICE simplified, not totally the same as the algorithm in the paper
    let minGrad = Number.MAX_VALUE;
    const localMin = {};
    const {
      labArray
    } = this;
    for (let i = x - 1; i <= x + 1; i++) {
      for (let j = y - 1; j <= y + 1; j++) {
        const i1 = labArray[j + 1][i][0]; // bottom
        const i2 = labArray[j][i + 1][0]; // right
        const i3 = labArray[j][i][0];
        // Euclidean distance
        const min = Math.sqrt((i1 - i3) ** 2 + (i2 - i3) ** 2);
        if (min < minGrad) {
          minGrad = min;
          localMin.x = i;
          localMin.y = j;
        }
      }
    }
    return localMin;
  }

  findSeeds() {
    const {
      width,
      height,
      labArray,
      step,
    } = this;
    const centers = [];
    // Initialize cluster centers by grid step (block size)
    const widthEdge = width - 2; // for the next step counting local minimum
    const heightEdge = height - 2;
    for (let i = step; i < widthEdge; i += step) {
      for (let j = step; j < heightEdge; j += step) {
        const center = this._findLocalMinimum(i, j);
        const color = labArray[center.y][center.x];
        center.l = color[0];
        center.a = color[1];
        center.b = color[2];
        centers.push(center);
      }
    }
    return centers;
  }

  getCenter(x, y) {
    const centerId = this.clusters[y][x];
    const center = this.centers[centerId];
    return center;
  }

  drawCenters(mat, color = [255, 0, 0]) {
    if (!mat) mat = new cv.Mat(this.height, this.width, cv.CV_8UC3, new cv.Scalar(0, 0, 0));
    this._setColor2Points(mat, this.centers, color);
    return mat;
  }

  drawContours(mat, color = [0, 255, 0]) {
    if (!mat) mat = new cv.Mat(this.height, this.width, cv.CV_8UC3, new cv.Scalar(0, 0, 0));
    if (!this.contours) this.computeContours();
    this._setColor2Points(mat, this.contours, color);
    return mat;
  }

  drawSuperPixels(mat) {
    if (!mat) mat = new cv.Mat(this.height, this.width, cv.CV_8UC3, new cv.Scalar(0, 0, 0));
    const { width, height } = this;
    for (let x = 0; x < width; x++) {
      for (let y = 0; y < height; y++) {
        const center = this.getCenter(x, y);
        // FIXME if there are error points, code below will throw an error
        if (center) this._setColor2Point(mat, { x, y }, [center.r, center.g, center.b]);
      }
    }
    return mat;
  }
}

module.exports = ClusteringSuperpixels;

/*
* from paper:
* SLIC Superpixels Compared to State-of-the-art Superpixel Methods 2011
*/
const ClusteringSuperpixels = require('./ClusteringSuperPixels');

class SLIC extends ClusteringSuperpixels {
  computeDist(centerId, pixX, pixY) {
    // NOTICE not the same as the original paper, mainly cancels Math.sqrt() calls for better performance
    const center = this.centers[centerId];
    const color = this.labArray[pixY][pixX];
    // lab distance
    const dl = center.l - color[0];
    const da = center.a - color[1];
    const db = center.b - color[2];
    // NOTICE (x * x) is much faster than Math.pow(x, 2) and (x ** 2)
    const dc = dl * dl + da * da + db * db;
    // xy distance
    const dx = center.x - pixX;
    const dy = center.y - pixY;
    const ds = dx * dx + dy * dy;
    return dc + (ds / this.step_2) * this.m_2;
  }

  generateSuperpixels() {
    const {
      width,
      height,
      labArray,
      step,
    } = this;
    // k-means clustering
    // console.time('new2DArray');
    this.clusters = Array(height).fill().map(() => Array(width).fill(-1)); // 2D
    // distances is initialized before each iteration
    this.distances = Array(height).fill().map(() => Array(width));
    // NOTICE multiple small size arrays perform better than a single large array
    // console.timeEnd('new2DArray');
    // console.time('new1DArray');
    // this.clusterId1D = Array(this.height * this.width).fill(-1);
    // console.timeEnd('new1DArray');
    this.centers = this.findSeeds();

    const { clusters, distances } = this;

    // iterations
    for (let i = 0; i < this.iters; i++) {
      const { centers } = this;
      // initialize distances
      distances.forEach((arr) => arr.fill(Number.MAX_VALUE));
      for (let j = 0; j < centers.length; j++) {
        // FIXME only compares to pixels in a 2 x step by 2 x step region
        for (let k = centers[j].x - step; k < centers[j].x + step; k++) {
          for (let l = centers[j].y - step; l < centers[j].y + step; l++) {
            if (k >= 0 && k < width && l >= 0 && l < height) {
              const d = this.computeDist(j, k, l);
              // Update cluster allocation if the cluster minimizes the distance
              if (d <= distances[l][k]) {
                distances[l][k] = d;
                clusters[l][k] = j;
              }
            }
          }
        }
      }
      // Clear the center values
      for (let j = 0; j < centers.length; j++) {
        const center = centers[j];
        center.l = 0;
        center.a = 0;
        center.b = 0;
        center.x = 0;
        center.y = 0;
        center.count = 0;
      }
      // Compute new cluster centers
      for (let j = 0; j < width; j++) {
        for (let k = 0; k < height; k++) {
          const cId = clusters[k][j];
          const center = centers[cId];
          if (center) {
            const color = labArray[k][j];
            center.l += color[0];
            center.a += color[1];
            center.b += color[2];
            center.x += j;
            center.y += k;
            center.count += 1;
          }
        }
      }
      // normalize the clusters
      this._normalizeCenterChannels();
    }
    this._clearCentersAndFillRGBChannels();
    // console.log(`we have ${this.centers.length} superpixels`);
  }
}

module.exports = SLIC;