Image diffing code

image_diff.dart

import 'dart:math' as Math;
import 'dart:typed_data' show Uint8List;

int pixelmatch(
    Uint8List img1, Uint8List img2, Uint8List output, int width, int height,
    {double threshold = 0.1, bool includeAA = true}) {
  if (img1.length != img2.length) {
    throw new FormatException('Cannot compare images of differing sizes.');
  }

  // maximum acceptable square distance between two colors;
  // 35215 is the maximum possible value for the YIQ difference metric
  double maxDelta = 35215 * threshold * threshold;
  int diff = 0;

  // compare each pixel of one image against the other one
  for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
      int pos = (y * width + x) * 4;

      // squared YUV distance between colors at this pixel position
      double delta = colorDelta(img1, img2, pos, pos);

      // the color difference is above the threshold
      if (delta > maxDelta) {
        // check it's a real rendering difference or just anti-aliasing
        if (!includeAA &&
            (antialiased(img1, x, y, width, height, img2) ||
                antialiased(img2, x, y, width, height, img1))) {
          // one of the pixels is anti-aliasing; draw as yellow and do not count as difference
          if (output != null) drawPixel(output, pos, 255, 255, 0);
        } else {
          // found substantial difference not caused by anti-aliasing; draw it as red
          if (output != null) drawPixel(output, pos, 255, 0, 0);
          diff++;
        }
      } else if (output != null) {
        // pixels are similar; draw background as grayscale image blended with white
        int val = blend(grayPixel(img1, pos), 0.1).toInt();
        drawPixel(output, pos, val, val, val);
      }
    }
  }

  // return the number of different pixels
  return diff;
}

// check if a pixel is likely a part of anti-aliasing;
// based on "Anti-aliased Pixel and Intensity Slope Detector" paper by V. Vysniauskas, 2009

bool antialiased(
    Uint8List img, int x1, int y1, int width, int height, Uint8List img2) {
  int x0 = Math.max(x1 - 1, 0),
      y0 = Math.max(y1 - 1, 0),
      x2 = Math.min(x1 + 1, width - 1),
      y2 = Math.min(y1 + 1, height - 1),
      pos = (y1 * width + x1) * 4,
      zeroes = 0,
      positives = 0,
      negatives = 0,
      minX,
      minY,
      maxX,
      maxY;
  double min = 0.0, max = 0.0;

  // go through 8 adjacent pixels
  for (int x = x0; x <= x2; x++) {
    for (int y = y0; y <= y2; y++) {
      if (x == x1 && y == y1) continue;

      // brightness delta between the center pixel and adjacent one
      double delta = colorDelta(img, img, pos, ((y * width + x) * 4), true);

      // count the number of equal, darker and brighter adjacent pixels
      if (delta == 0)
        zeroes++;
      else if (delta < 0)
        negatives++;
      else if (delta > 0) positives++;

      // if found more than 2 equal siblings, it's definitely not anti-aliasing
      if (zeroes > 2) return false;

      if (img2?.isEmpty == true) continue;

      // remember the darkest pixel
      if (delta < min) {
        min = delta;
        minX = x;
        minY = y;
      }
      // remember the brightest pixel
      if (delta > max) {
        max = delta;
        maxX = x;
        maxY = y;
      }
    }
  }

  if (img2?.isEmpty == true) return true;

  // if there are no both darker and brighter pixels among siblings, it's not anti-aliasing
  if (negatives == 0 || positives == 0) return false;

  // if either the darkest or the brightest pixel has more than 2 equal siblings in both images
  // (definitely not anti-aliased), this pixel is anti-aliased
  return (!antialiased(img, minX, minY, width, height, null) &&
          !antialiased(img2, minX, minY, width, height, null)) ||
      (!antialiased(img, maxX, maxY, width, height, null) &&
          !antialiased(img2, maxX, maxY, width, height, null));
}

// calculate color difference according to the paper "Measuring perceived color difference
// using YIQ NTSC transmission color space in mobile applications" by Y. Kotsarenko and F. Ramos

double colorDelta(Uint8List img1, Uint8List img2, int k, int m,
    [bool yOnly = false]) {
  double a1 = img1[k + 3] / 255,
      a2 = img2[m + 3] / 255,
      r1 = blend(img1[k + 0].toDouble(), a1),
      g1 = blend(img1[k + 1].toDouble(), a1),
      b1 = blend(img1[k + 2].toDouble(), a1),
      r2 = blend(img2[m + 0].toDouble(), a2),
      g2 = blend(img2[m + 1].toDouble(), a2),
      b2 = blend(img2[m + 2].toDouble(), a2),
      y = rgb2y(r1, g1, b1) - rgb2y(r2, g2, b2);

  if (yOnly) return y; // brightness difference only

  var i = rgb2i(r1, g1, b1) - rgb2i(r2, g2, b2),
      q = rgb2q(r1, g1, b1) - rgb2q(r2, g2, b2);

  return 0.5053 * y * y + 0.299 * i * i + 0.1957 * q * q;
}

double rgb2y(r, g, b) => r * 0.29889531 + g * 0.58662247 + b * 0.11448223;
double rgb2i(r, g, b) => r * 0.59597799 - g * 0.27417610 - b * 0.32180189;
double rgb2q(r, g, b) => r * 0.21147017 - g * 0.52261711 + b * 0.31114694;

// blend semi-transparent color with white
double blend(double c, double a) => 255 + (c - 255) * a;

void drawPixel(Uint8List output, int pos, int r, int g, int b) {
  output[pos + 0] = r;
  output[pos + 1] = g;
  output[pos + 2] = b;
  output[pos + 3] = 255;
}

double grayPixel(Uint8List img, int i) {
  double a = img[i + 3] / 255,
      r = blend(img[i + 0].toDouble(), a),
      g = blend(img[i + 1].toDouble(), a),
      b = blend(img[i + 2].toDouble(), a);
  return rgb2y(r, g, b);
}