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,
}) {
if (pointProvider is PointProviderLab) {
return _quantizeLab(
inputPixels,
maxColors,
startingClusters: startingClusters,
maxIterations: maxIterations,
returnInputPixelToClusterPixel: returnInputPixelToClusterPixel,
);
}
final pixelToIndex = HashMap<int, int>();
final points = <List<double>>[];
final pixels = <int>[];
final countValues = <int>[];
for (var inputPixel in inputPixels) {
final index = pixelToIndex[inputPixel];
if (index == null) {
pixelToIndex[inputPixel] = pixels.length;
points.add(pointProvider.fromInt(inputPixel));
pixels.add(inputPixel);
countValues.add(1);
} else {
countValues[index]++;
}
}
final pointCount = pixels.length;
final counts = countValues;
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.
// Safeguard: if we've exhausted all unique points, stop adding clusters.
if (indices.length >= points.length) {
break;
}
var index = random.nextInt(points.length);
while (indices.contains(index)) {
index = random.nextInt(points.length);
}
indices.add(index);
}
for (var index in indices) {
clusters.add(points[index]);
}
}
debugLog(
'have ${clusters.length} starting clusters, ${points.length} points',
);
final clusterIndices = List<int>.generate(
pointCount,
(index) => index % clusterCount,
);
final clusterDistanceMatrix = Float64List(clusterCount * clusterCount);
final neighborIndexMatrix = Int32List(clusterCount * clusterCount);
for (var i = 0; i < clusterCount; i++) {
final rowOffset = i * clusterCount;
for (var j = 0; j < clusterCount; j++) {
neighborIndexMatrix[rowOffset + j] = j;
}
}
final neighborDistanceMatrix = Float64List(clusterCount * clusterCount);
final neighborLimits = Int32List(clusterCount);
final previousDistances = Float64List(pointCount);
final maxPreviousDistancesByCluster = Float64List(clusterCount);
final pixelCountSums = List<int>.filled(clusterCount, 0);
final componentASums = List<double>.filled(clusterCount, 0);
final componentBSums = List<double>.filled(clusterCount, 0);
final componentCSums = List<double>.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++) {
maxPreviousDistancesByCluster[i] = 0;
}
for (var i = 0; i < pointCount; i++) {
final clusterIndex = clusterIndices[i];
final distance = pointProvider.distance(
points[i],
clusters[clusterIndex],
);
previousDistances[i] = distance;
if (distance > maxPreviousDistancesByCluster[clusterIndex]) {
maxPreviousDistancesByCluster[clusterIndex] = distance;
}
}
if (iteration == 0) {
for (var i = 0; i < pointCount; i++) {
final point = points[i];
final previousClusterIndex = clusterIndices[i];
var minimumDistance = previousDistances[i];
var newClusterIndex = -1;
for (
var candidateClusterIndex = 0;
candidateClusterIndex < clusterCount;
candidateClusterIndex++
) {
if (candidateClusterIndex == previousClusterIndex) {
continue;
}
final distance = pointProvider.distance(
point,
clusters[candidateClusterIndex],
);
if (distance <= minimumDistance) {
minimumDistance = distance;
newClusterIndex = candidateClusterIndex;
}
}
if (newClusterIndex != -1) {
pointsMoved++;
clusterIndices[i] = newClusterIndex;
}
}
} else {
for (var i = 0; i < clusterCount; i++) {
final distanceRowOffset = i * clusterCount;
for (var j = i + 1; j < clusterCount; j++) {
final distance = pointProvider.distance(clusters[i], clusters[j]);
clusterDistanceMatrix[j * clusterCount + i] = distance;
clusterDistanceMatrix[distanceRowOffset + j] = distance;
}
final neighborLimit = _partitionNeighborRow(
neighborIndexMatrix,
neighborDistanceMatrix,
distanceRowOffset,
clusterDistanceMatrix,
distanceRowOffset,
clusterCount,
4 * maxPreviousDistancesByCluster[i],
);
neighborLimits[i] = neighborLimit;
_sortNeighborRow(
neighborIndexMatrix,
neighborDistanceMatrix,
distanceRowOffset,
neighborLimit,
);
}
for (var i = 0; i < pointCount; i++) {
final point = points[i];
final previousClusterIndex = clusterIndices[i];
final previousDistance = previousDistances[i];
final neighborDistanceThreshold = 4 * previousDistance;
var minimumDistance = previousDistance;
var newClusterIndex = -1;
final previousClusterNeighborRowOffset =
previousClusterIndex * clusterCount;
final neighborLimit = neighborLimits[previousClusterIndex];
for (var j = 0; j < neighborLimit; j++) {
final neighborOffset = previousClusterNeighborRowOffset + j;
final candidateClusterIndex = neighborIndexMatrix[neighborOffset];
if (neighborDistanceMatrix[neighborOffset] >=
neighborDistanceThreshold) {
break;
}
if (candidateClusterIndex == previousClusterIndex) {
continue;
}
final distance = pointProvider.distance(
point,
clusters[candidateClusterIndex],
);
if (distance <= minimumDistance) {
minimumDistance = distance;
newClusterIndex = candidateClusterIndex;
}
}
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');
for (var i = 0; i < clusterCount; i++) {
pixelCountSums[i] = 0;
componentASums[i] = 0;
componentBSums[i] = 0;
componentCSums[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,
lstarToCount: {},
);
}
