quantize static method

Implementation

static QuantizerResult quantize(
  Iterable<int> inputPixels,
  int maxColors, {
  List<int> startingClusters = const [],
  PointProvider pointProvider = const PointProviderLab(),
  int maxIterations = 5,
  bool returnInputPixelToClusterPixel = false,
}) {
  final pixelToCount = <int, int>{};
  final points = <List<double>>[];
  final pixels = <int>[];
  var pointCount = 0;
  inputPixels.forEach((inputPixel) {
    final pixelCount = pixelToCount.update(inputPixel, (value) => value + 1,
        ifAbsent: () => 1);
    if (pixelCount == 1) {
      pointCount++;
      points.add(pointProvider.fromInt(inputPixel));
      pixels.add(inputPixel);
    }
  });

  final counts = List<int>.filled(pointCount, 0);
  for (var i = 0; i < pointCount; i++) {
    final pixel = pixels[i];
    final count = pixelToCount[pixel]!;
    counts[i] = count;
  }

  var clusterCount = math.min(maxColors, pointCount);

  final clusters =
      startingClusters.map((e) => pointProvider.fromInt(e)).toList();
  final additionalClustersNeeded = clusterCount - clusters.length;
  if (additionalClustersNeeded > 0) {
    final random = math.Random(0x42688);
    final indices = <int>[];
    for (var i = 0; i < additionalClustersNeeded; i++) {
      // Use existing points rather than generating random centroids.
      //
      // KMeans is extremely sensitive to initial clusters. This quantizer
      // is meant to be used with a Wu quantizer that provides initial
      // centroids, but Wu is very slow on unscaled images and when extracting
      // more than 256 colors.
      //
      // Here, we can safely assume that more than 256 colors were requested
      // for extraction. Generating random centroids tends to lead to many
      // "empty" centroids, as the random centroids are nowhere near any pixels
      // in the image, and the centroids from Wu are very refined and close
      // to pixels in the image.
      //
      // Rather than generate random centroids, we'll pick centroids that
      // are actual pixels in the image, and avoid duplicating centroids.

      var index = random.nextInt(points.length);
      while (indices.contains(index)) {
        index = random.nextInt(points.length);
      }
      indices.add(index);
    }

    indices.forEach((index) {
      clusters.add(points[index]);
    });
  }
  debugLog(
    'have ${clusters.length} starting clusters, ${points.length} points',
  );
  final clusterIndices =
      List<int>.generate(pointCount, (index) => index % clusterCount);
  final indexMatrix = List<List<int>>.generate(
      clusterCount, (_) => List.filled(clusterCount, 0));

  final distanceToIndexMatrix = List<List<DistanceAndIndex>>.generate(
      clusterCount,
      (index) => List<DistanceAndIndex>.generate(
          clusterCount, (index) => DistanceAndIndex(0, index)));

  final pixelCountSums = List<int>.filled(clusterCount, 0);
  for (var iteration = 0; iteration < maxIterations; iteration++) {
    if (debug) {
      for (var i = 0; i < clusterCount; i++) {
        pixelCountSums[i] = 0;
      }
      for (var i = 0; i < pointCount; i++) {
        final clusterIndex = clusterIndices[i];
        final count = counts[i];
        pixelCountSums[clusterIndex] += count;
      }
      var emptyClusters = 0;
      for (var cluster = 0; cluster < clusterCount; cluster++) {
        if (pixelCountSums[cluster] == 0) {
          emptyClusters++;
        }
      }
      debugLog(
        'starting iteration ${iteration + 1}; $emptyClusters clusters are empty of $clusterCount',
      );
    }

    var pointsMoved = 0;
    for (var i = 0; i < clusterCount; i++) {
      for (var j = i + 1; j < clusterCount; j++) {
        final distance = pointProvider.distance(clusters[i], clusters[j]);
        distanceToIndexMatrix[j][i].distance = distance;
        distanceToIndexMatrix[j][i].index = i;
        distanceToIndexMatrix[i][j].distance = distance;
        distanceToIndexMatrix[i][j].index = j;
      }
      distanceToIndexMatrix[i].sort();
      for (var j = 0; j < clusterCount; j++) {
        indexMatrix[i][j] = distanceToIndexMatrix[i][j].index;
      }
    }

    for (var i = 0; i < pointCount; i++) {
      final point = points[i];
      final previousClusterIndex = clusterIndices[i];
      final previousCluster = clusters[previousClusterIndex];
      final previousDistance = pointProvider.distance(point, previousCluster);
      var minimumDistance = previousDistance;
      var newClusterIndex = -1;
      for (var j = 0; j < clusterCount; j++) {
        if (distanceToIndexMatrix[previousClusterIndex][j].distance >=
            4 * previousDistance) {
          continue;
        }
        final distance = pointProvider.distance(point, clusters[j]);
        if (distance < minimumDistance) {
          minimumDistance = distance;
          newClusterIndex = j;
        }
      }
      if (newClusterIndex != -1) {
        pointsMoved++;
        clusterIndices[i] = newClusterIndex;
      }
    }

    if (pointsMoved == 0 && iteration > 0) {
      debugLog('terminated after $iteration k-means iterations');
      break;
    }

    debugLog('iteration ${iteration + 1} moved $pointsMoved');
    final componentASums = List<double>.filled(clusterCount, 0);
    final componentBSums = List<double>.filled(clusterCount, 0);
    final componentCSums = List<double>.filled(clusterCount, 0);

    for (var i = 0; i < clusterCount; i++) {
      pixelCountSums[i] = 0;
    }
    for (var i = 0; i < pointCount; i++) {
      final clusterIndex = clusterIndices[i];
      final point = points[i];
      final count = counts[i];
      pixelCountSums[clusterIndex] += count;
      componentASums[clusterIndex] += (point[0] * count);
      componentBSums[clusterIndex] += (point[1] * count);
      componentCSums[clusterIndex] += (point[2] * count);
    }
    for (var i = 0; i < clusterCount; i++) {
      final count = pixelCountSums[i];
      if (count == 0) {
        clusters[i] = [0.0, 0.0, 0.0];
        continue;
      }
      final a = componentASums[i] / count;
      final b = componentBSums[i] / count;
      final c = componentCSums[i] / count;
      clusters[i] = [a, b, c];
    }
  }

  final clusterArgbs = <int>[];
  final clusterPopulations = <int>[];
  for (var i = 0; i < clusterCount; i++) {
    final count = pixelCountSums[i];
    if (count == 0) {
      continue;
    }

    final possibleNewCluster = pointProvider.toInt(clusters[i]);
    if (clusterArgbs.contains(possibleNewCluster)) {
      continue;
    }

    clusterArgbs.add(possibleNewCluster);
    clusterPopulations.add(count);
  }
  debugLog(
    'kmeans finished and generated ${clusterArgbs.length} clusters; $clusterCount were requested',
  );

  final inputPixelToClusterPixel = <int, int>{};
  if (returnInputPixelToClusterPixel) {
    final stopwatch = Stopwatch()..start();
    for (var i = 0; i < pixels.length; i++) {
      final inputPixel = pixels[i];
      final clusterIndex = clusterIndices[i];
      final cluster = clusters[clusterIndex];
      final clusterPixel = pointProvider.toInt(cluster);
      inputPixelToClusterPixel[inputPixel] = clusterPixel;
    }
    debugLog(
      'took ${stopwatch.elapsedMilliseconds} ms to create input to cluster map',
    );
  }

  return QuantizerResult(
    Map.fromIterables(clusterArgbs, clusterPopulations),
    inputPixelToClusterPixel: inputPixelToClusterPixel,
  );
}