From d1bc261d8dcf00e894dfd07e46a3232081448266 Mon Sep 17 00:00:00 2001 From: James O'Leary Date: Wed, 9 Jun 2021 13:32:19 -0400 Subject: Quantizer improvements The original versions of these quantizers landed a couple months back, and they were fine. Since then, we've had several opportunities to iterate on them. This change lands improvements from those iterations. TL;DR: 18% faster, big bug fix to WSMeans, code is cleaner (hopefully) - QuantizerMap indexes an image's pixels, 'unique-ing' them by reducing the pixel array to a map with keys of colors, and values of population. This allows other quantizers to operate much more quickly: instead of working on each pixel individually, they're able to operate in bulk. - QuantizerWu uses flat arrays instead of 3D arrays and is more understandable IMHO. - QuantizerWsmeans has speed improvements, most importantly, it has a big bug fix. When a Kmeans-based quantizer algo starts, it must first assign the pixels to any one of the starting clusters. The original implementation decided what cluster to assign a pixel to by finding the cluster closest to the pixel. However, the algo terminates if no pixels moved after one iteration of the algorithm, and since the pixels were already in the cluster closest to them, the algo would immediately terminate before it actually figured out where the cluster moved to after pixels were assigned to it, and had a chance to move pixels around based on that. - Funnily enough, even though this _should_ mean Wsmeans got a lot slower since it has to do more iterations, it is actually 16% faster Additionally, during review of this CL: An accidental dependency on iteration order of a Set was introduced, causing inconsistent initialization of the mPoints array, creating inconsistent results from the quantizer. Removing the dependency on hashes of float[], and avoiding Maps altogether, removes a dependency on hash codes of pointers that existed during review, making it easier to have verifiable consistency across iterations. This also improves speed slightly, from 55 ms to 39 ms (tested on sunfish, first 9 wallpapers in Landscapes, City Scapes, and Art categories, and averaged) Bug: 189931209 Test: ran performance tests with VariationalKMeansQuantizer, the previous Celebi = Wu + Wsmeans quantizer, and the new Celebi = new Wu + new Wsmeans quantizers, over 100 iterations. Wu speed is roughly the same, Wsmeans is 18%. Verified quantizer output is stable for the same input pixels, run 100,000 times for each of two wallpapers. Change-Id: I3324d29860c098ea1fd602b8d4197837e732f4f1 --- core/java/android/app/WallpaperColors.java | 110 +++- .../internal/graphics/palette/CelebiQuantizer.java | 28 +- .../graphics/palette/CentroidProvider.java | 38 -- .../internal/graphics/palette/LABCentroid.java | 67 -- .../graphics/palette/LABPointProvider.java | 67 ++ .../android/internal/graphics/palette/Mean.java | 44 -- .../internal/graphics/palette/MeanBucket.java | 42 -- .../internal/graphics/palette/PointProvider.java | 35 + .../internal/graphics/palette/QuantizerMap.java | 62 ++ .../graphics/palette/WSMeansQuantizer.java | 398 ++++++------ .../internal/graphics/palette/WuQuantizer.java | 716 +++++++++++---------- 11 files changed, 837 insertions(+), 770 deletions(-) delete mode 100644 core/java/com/android/internal/graphics/palette/CentroidProvider.java delete mode 100644 core/java/com/android/internal/graphics/palette/LABCentroid.java create mode 100644 core/java/com/android/internal/graphics/palette/LABPointProvider.java delete mode 100644 core/java/com/android/internal/graphics/palette/Mean.java delete mode 100644 core/java/com/android/internal/graphics/palette/MeanBucket.java create mode 100644 core/java/com/android/internal/graphics/palette/PointProvider.java create mode 100644 core/java/com/android/internal/graphics/palette/QuantizerMap.java diff --git a/core/java/android/app/WallpaperColors.java b/core/java/android/app/WallpaperColors.java index fab9e02f5873..e7df3efde4d5 100644 --- a/core/java/android/app/WallpaperColors.java +++ b/core/java/android/app/WallpaperColors.java @@ -30,6 +30,7 @@ import android.util.Log; import android.util.Size; import com.android.internal.graphics.ColorUtils; +import com.android.internal.graphics.cam.Cam; import com.android.internal.graphics.palette.CelebiQuantizer; import com.android.internal.graphics.palette.Palette; import com.android.internal.graphics.palette.VariationalKMeansQuantizer; @@ -43,7 +44,7 @@ import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; -import java.util.stream.Collectors; +import java.util.Set; /** * Provides information about the colors of a wallpaper. @@ -278,7 +279,7 @@ public final class WallpaperColors implements Parcelable { /** * Constructs a new object from a set of colors, where hints can be specified. * - * @param populationByColor Map with keys of colors, and value representing the number of + * @param colorToPopulation Map with keys of colors, and value representing the number of * occurrences of color in the wallpaper. * @param colorHints A combination of color hints. * @hide @@ -286,20 +287,105 @@ public final class WallpaperColors implements Parcelable { * @see WallpaperColors#fromBitmap(Bitmap) * @see WallpaperColors#fromDrawable(Drawable) */ - public WallpaperColors(@NonNull Map populationByColor, + public WallpaperColors(@NonNull Map colorToPopulation, @ColorsHints int colorHints) { - mAllColors = populationByColor; - - ArrayList> mapEntries = new ArrayList( - populationByColor.entrySet()); - mapEntries.sort((a, b) -> - b.getValue().compareTo(a.getValue()) - ); - mMainColors = mapEntries.stream().map(entry -> Color.valueOf(entry.getKey())).collect( - Collectors.toList()); + mAllColors = colorToPopulation; + + final Map colorToCam = new HashMap<>(); + for (int color : colorToPopulation.keySet()) { + colorToCam.put(color, Cam.fromInt(color)); + } + final double[] hueProportions = hueProportions(colorToCam, colorToPopulation); + final Map colorToHueProportion = colorToHueProportion( + colorToPopulation.keySet(), colorToCam, hueProportions); + + final Map colorToScore = new HashMap<>(); + for (Map.Entry mapEntry : colorToHueProportion.entrySet()) { + int color = mapEntry.getKey(); + double proportion = mapEntry.getValue(); + double score = score(colorToCam.get(color), proportion); + colorToScore.put(color, score); + } + ArrayList> mapEntries = new ArrayList(colorToScore.entrySet()); + mapEntries.sort((a, b) -> b.getValue().compareTo(a.getValue())); + + List colorsByScoreDescending = new ArrayList<>(); + for (Map.Entry colorToScoreEntry : mapEntries) { + colorsByScoreDescending.add(colorToScoreEntry.getKey()); + } + + List mainColorInts = new ArrayList<>(); + findSeedColorLoop: + for (int color : colorsByScoreDescending) { + Cam cam = colorToCam.get(color); + for (int otherColor : mainColorInts) { + Cam otherCam = colorToCam.get(otherColor); + if (hueDiff(cam, otherCam) < 15) { + continue findSeedColorLoop; + } + } + mainColorInts.add(color); + } + List mainColors = new ArrayList<>(); + for (int colorInt : mainColorInts) { + mainColors.add(Color.valueOf(colorInt)); + } + mMainColors = mainColors; mColorHints = colorHints; } + private static double hueDiff(Cam a, Cam b) { + return (180f - Math.abs(Math.abs(a.getHue() - b.getHue()) - 180f)); + } + + private static double score(Cam cam, double proportion) { + return cam.getChroma() + (proportion * 100); + } + + private static Map colorToHueProportion(Set colors, + Map colorToCam, double[] hueProportions) { + Map colorToHueProportion = new HashMap<>(); + for (int color : colors) { + final int hue = wrapDegrees(Math.round(colorToCam.get(color).getHue())); + double proportion = 0.0; + for (int i = hue - 15; i < hue + 15; i++) { + proportion += hueProportions[wrapDegrees(i)]; + } + colorToHueProportion.put(color, proportion); + } + return colorToHueProportion; + } + + private static int wrapDegrees(int degrees) { + if (degrees < 0) { + return (degrees % 360) + 360; + } else if (degrees >= 360) { + return degrees % 360; + } else { + return degrees; + } + } + + private static double[] hueProportions(@NonNull Map colorToCam, + Map colorToPopulation) { + final double[] proportions = new double[360]; + + double totalPopulation = 0; + for (Map.Entry entry : colorToPopulation.entrySet()) { + totalPopulation += entry.getValue(); + } + + for (Map.Entry entry : colorToPopulation.entrySet()) { + final int color = (int) entry.getKey(); + final int population = colorToPopulation.get(color); + final Cam cam = colorToCam.get(color); + final int hue = wrapDegrees(Math.round(cam.getHue())); + proportions[hue] = proportions[hue] + ((double) population / totalPopulation); + } + + return proportions; + } + public static final @android.annotation.NonNull Creator CREATOR = new Creator() { @Override public WallpaperColors createFromParcel(Parcel in) { diff --git a/core/java/com/android/internal/graphics/palette/CelebiQuantizer.java b/core/java/com/android/internal/graphics/palette/CelebiQuantizer.java index de6bf2044dbc..454fd00a841c 100644 --- a/core/java/com/android/internal/graphics/palette/CelebiQuantizer.java +++ b/core/java/com/android/internal/graphics/palette/CelebiQuantizer.java @@ -19,26 +19,32 @@ package com.android.internal.graphics.palette; import java.util.List; /** - * An implementation of Celebi's WSM quantizer, or, a Kmeans quantizer that starts with centroids - * from a Wu quantizer to ensure 100% reproducible and quality results, and has some optimizations - * to the Kmeans algorithm. - * + * An implementation of Celebi's quantization method. * See Celebi 2011, “Improving the Performance of K-Means for Color Quantization” + * + * First, Wu's quantizer runs. The results are used as starting points for a subsequent Kmeans + * run. Using Wu's quantizer ensures 100% reproducible quantization results, because the starting + * centroids are always the same. It also ensures high quality results, Wu is a box-cutting + * quantization algorithm, much like medican color cut. It minimizes variance, much like Kmeans. + * Wu is shown to be the highest quality box-cutting quantization algorithm. + * + * Second, a Kmeans quantizer tweaked for performance is run. Celebi calls this a weighted + * square means quantizer, or WSMeans. Optimizations include operating on a map of image pixels + * rather than all image pixels, and avoiding excess color distance calculations by using a + * matrix and geometrical properties to know when there won't be any cluster closer to a pixel. */ public class CelebiQuantizer implements Quantizer { private List mSwatches; - public CelebiQuantizer() { } + public CelebiQuantizer() { + } @Override public void quantize(int[] pixels, int maxColors) { - WuQuantizer wu = new WuQuantizer(pixels, maxColors); + WuQuantizer wu = new WuQuantizer(); wu.quantize(pixels, maxColors); - List wuSwatches = wu.getQuantizedColors(); - LABCentroid labCentroidProvider = new LABCentroid(); - WSMeansQuantizer kmeans = - new WSMeansQuantizer(WSMeansQuantizer.createStartingCentroids(labCentroidProvider, - wuSwatches), labCentroidProvider, pixels, maxColors); + WSMeansQuantizer kmeans = new WSMeansQuantizer(wu.getColors(), new LABPointProvider(), + wu.inputPixelToCount()); kmeans.quantize(pixels, maxColors); mSwatches = kmeans.getQuantizedColors(); } diff --git a/core/java/com/android/internal/graphics/palette/CentroidProvider.java b/core/java/com/android/internal/graphics/palette/CentroidProvider.java deleted file mode 100644 index 5fcfcbab3159..000000000000 --- a/core/java/com/android/internal/graphics/palette/CentroidProvider.java +++ /dev/null @@ -1,38 +0,0 @@ -/* - * Copyright (C) 2021 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package com.android.internal.graphics.palette; - -import android.annotation.ColorInt; - -interface CentroidProvider { - /** - * @return 3 dimensions representing the color - */ - float[] getCentroid(@ColorInt int color); - - /** - * @param centroid 3 dimensions representing the color - * @return 32-bit ARGB representation - */ - @ColorInt - int getColor(float[] centroid); - - /** - * Distance between two centroids. - */ - float distance(float[] a, float[] b); -} diff --git a/core/java/com/android/internal/graphics/palette/LABCentroid.java b/core/java/com/android/internal/graphics/palette/LABCentroid.java deleted file mode 100644 index 408cf1fe9193..000000000000 --- a/core/java/com/android/internal/graphics/palette/LABCentroid.java +++ /dev/null @@ -1,67 +0,0 @@ -/* - * Copyright (C) 2021 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package com.android.internal.graphics.palette; - -import android.graphics.Color; -import android.graphics.ColorSpace; - -/** - * Allows quantizers to operate in the L*a*b* colorspace. - * L*a*b* is a good choice for measuring distance between colors. - * Better spaces, and better distance calculations even in L*a*b* exist, but measuring distance - * in L*a*b* space, also known as deltaE, is a universally accepted standard across industries - * and worldwide. - */ -public class LABCentroid implements CentroidProvider { - final ColorSpace.Connector mRgbToLab; - final ColorSpace.Connector mLabToRgb; - - public LABCentroid() { - mRgbToLab = ColorSpace.connect( - ColorSpace.get(ColorSpace.Named.SRGB), - ColorSpace.get(ColorSpace.Named.CIE_LAB)); - mLabToRgb = ColorSpace.connect(ColorSpace.get(ColorSpace.Named.CIE_LAB), - ColorSpace.get(ColorSpace.Named.SRGB)); - } - - @Override - public float[] getCentroid(int color) { - float r = Color.red(color) / 255.f; - float g = Color.green(color) / 255.f; - float b = Color.blue(color) / 255.f; - - float[] transform = mRgbToLab.transform(r, g, b); - return transform; - } - - @Override - public int getColor(float[] centroid) { - float[] rgb = mLabToRgb.transform(centroid); - int color = Color.rgb(rgb[0], rgb[1], rgb[2]); - return color; - } - - @Override - public float distance(float[] a, float[] b) { - // Standard v1 CIELAB deltaE formula, 1976 - easily improved upon, however, - // improvements do not significantly impact the Palette algorithm's results. - double dL = a[0] - b[0]; - double dA = a[1] - b[1]; - double dB = a[2] - b[2]; - return (float) (dL * dL + dA * dA + dB * dB); - } -} diff --git a/core/java/com/android/internal/graphics/palette/LABPointProvider.java b/core/java/com/android/internal/graphics/palette/LABPointProvider.java new file mode 100644 index 000000000000..21a2212d6c77 --- /dev/null +++ b/core/java/com/android/internal/graphics/palette/LABPointProvider.java @@ -0,0 +1,67 @@ +/* + * Copyright (C) 2021 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.internal.graphics.palette; + +import android.graphics.Color; +import android.graphics.ColorSpace; + +/** + * Allows quantizers to operate in the L*a*b* colorspace. + * L*a*b* is a good choice for measuring distance between colors. + * Better spaces, and better distance calculations even in L*a*b* exist, but measuring distance + * in L*a*b* space, also known as deltaE, is a universally accepted standard across industries + * and worldwide. + */ +public class LABPointProvider implements PointProvider { + final ColorSpace.Connector mRgbToLab; + final ColorSpace.Connector mLabToRgb; + + public LABPointProvider() { + mRgbToLab = ColorSpace.connect( + ColorSpace.get(ColorSpace.Named.SRGB), + ColorSpace.get(ColorSpace.Named.CIE_LAB)); + mLabToRgb = ColorSpace.connect(ColorSpace.get(ColorSpace.Named.CIE_LAB), + ColorSpace.get(ColorSpace.Named.SRGB)); + } + + @Override + public float[] fromInt(int color) { + float r = Color.red(color) / 255.f; + float g = Color.green(color) / 255.f; + float b = Color.blue(color) / 255.f; + + float[] transform = mRgbToLab.transform(r, g, b); + return transform; + } + + @Override + public int toInt(float[] centroid) { + float[] rgb = mLabToRgb.transform(centroid); + int color = Color.rgb(rgb[0], rgb[1], rgb[2]); + return color; + } + + @Override + public float distance(float[] a, float[] b) { + // Standard v1 CIELAB deltaE formula, 1976 - easily improved upon, however, + // improvements do not significantly impact the Palette algorithm's results. + double dL = a[0] - b[0]; + double dA = a[1] - b[1]; + double dB = a[2] - b[2]; + return (float) (dL * dL + dA * dA + dB * dB); + } +} diff --git a/core/java/com/android/internal/graphics/palette/Mean.java b/core/java/com/android/internal/graphics/palette/Mean.java deleted file mode 100644 index bde036349d3b..000000000000 --- a/core/java/com/android/internal/graphics/palette/Mean.java +++ /dev/null @@ -1,44 +0,0 @@ -/* - * Copyright (C) 2021 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package com.android.internal.graphics.palette; - -import java.util.Random; - -/** - * Represents a centroid in Kmeans algorithms. - */ -public class Mean { - public float[] center; - - /** - * Constructor. - * - * @param upperBound maximum value of a dimension in the space Kmeans is optimizing in - * @param random used to generate a random center - */ - Mean(int upperBound, Random random) { - center = - new float[]{ - random.nextInt(upperBound + 1), random.nextInt(upperBound + 1), - random.nextInt(upperBound + 1) - }; - } - - Mean(float[] center) { - this.center = center; - } -} diff --git a/core/java/com/android/internal/graphics/palette/MeanBucket.java b/core/java/com/android/internal/graphics/palette/MeanBucket.java deleted file mode 100644 index ae8858a8107c..000000000000 --- a/core/java/com/android/internal/graphics/palette/MeanBucket.java +++ /dev/null @@ -1,42 +0,0 @@ -/* - * Copyright (C) 2021 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package com.android.internal.graphics.palette; - -import java.util.HashSet; -import java.util.Set; - -class MeanBucket { - float[] mTotal = {0.f, 0.f, 0.f}; - int mCount = 0; - Set mColors = new HashSet<>(); - - void add(float[] colorAsDoubles, int color, int colorCount) { - assert (colorAsDoubles.length == 3); - mColors.add(color); - mTotal[0] += (colorAsDoubles[0] * colorCount); - mTotal[1] += (colorAsDoubles[1] * colorCount); - mTotal[2] += (colorAsDoubles[2] * colorCount); - mCount += colorCount; - } - - float[] getCentroid() { - if (mCount == 0) { - return null; - } - return new float[]{mTotal[0] / mCount, mTotal[1] / mCount, mTotal[2] / mCount}; - } -} diff --git a/core/java/com/android/internal/graphics/palette/PointProvider.java b/core/java/com/android/internal/graphics/palette/PointProvider.java new file mode 100644 index 000000000000..017adeb3ef27 --- /dev/null +++ b/core/java/com/android/internal/graphics/palette/PointProvider.java @@ -0,0 +1,35 @@ +/* + * Copyright (C) 2021 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.internal.graphics.palette; + +import android.annotation.ColorInt; + +/** + * Interface that allows quantizers to have a plug-and-play interface for experimenting with + * quantization in different color spaces. + */ +public interface PointProvider { + /** Convert a color to 3 coordinates representing the color in a color space. */ + float[] fromInt(@ColorInt int argb); + + /** Convert 3 coordinates in the color space into a color */ + @ColorInt + int toInt(float[] point); + + /** Find the distance between two colosrin the color space */ + float distance(float[] a, float[] b); +} diff --git a/core/java/com/android/internal/graphics/palette/QuantizerMap.java b/core/java/com/android/internal/graphics/palette/QuantizerMap.java new file mode 100644 index 000000000000..6b60f61b91f5 --- /dev/null +++ b/core/java/com/android/internal/graphics/palette/QuantizerMap.java @@ -0,0 +1,62 @@ +/* + * Copyright (C) 2021 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.internal.graphics.palette; + +import android.annotation.NonNull; +import android.annotation.Nullable; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * Converts a set of pixels/colors into a map with keys of unique colors, and values of the count + * of the unique color in the original set of pixels. + * + * This allows other quantizers to get a significant speed boost by simply running this quantizer, + * and then performing operations using the map, rather than for each pixel. + */ +public final class QuantizerMap implements Quantizer { + private HashMap mColorToCount; + private Palette mPalette; + + @Override + public void quantize(@NonNull int[] pixels, int colorCount) { + final HashMap colorToCount = new HashMap<>(); + for (int pixel : pixels) { + colorToCount.merge(pixel, 1, Integer::sum); + } + mColorToCount = colorToCount; + + List swatches = new ArrayList<>(); + for (Map.Entry entry : colorToCount.entrySet()) { + swatches.add(new Palette.Swatch(entry.getKey(), entry.getValue())); + } + mPalette = Palette.from(swatches); + } + + @Override + public List getQuantizedColors() { + return mPalette.getSwatches(); + } + + @Nullable + public Map getColorToCount() { + return mColorToCount; + } +} diff --git a/core/java/com/android/internal/graphics/palette/WSMeansQuantizer.java b/core/java/com/android/internal/graphics/palette/WSMeansQuantizer.java index 1d865c2513cf..19ed8d07394e 100644 --- a/core/java/com/android/internal/graphics/palette/WSMeansQuantizer.java +++ b/core/java/com/android/internal/graphics/palette/WSMeansQuantizer.java @@ -16,18 +16,20 @@ package com.android.internal.graphics.palette; +import android.annotation.NonNull; +import android.annotation.Nullable; +import android.util.Log; + import java.util.ArrayList; import java.util.Arrays; -import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Random; import java.util.Set; - /** - * A color quantizer based on the Kmeans algorithm. + * A color quantizer based on the Kmeans algorithm. Prefer using QuantizerCelebi. * * This is an implementation of Kmeans based on Celebi's 2011 paper, * "Improving the Performance of K-Means for Color Quantization". In the paper, this algorithm is @@ -36,253 +38,237 @@ import java.util.Set; * well as indexing colors by their count, thus minimizing the number of points to move around. * * Celebi's paper also stabilizes results and guarantees high quality by using starting centroids - * from Wu's quantization algorithm. See CelebiQuantizer for more info. + * from Wu's quantization algorithm. See QuantizerCelebi for more info. */ -public class WSMeansQuantizer implements Quantizer { - Mean[] mMeans; - private final Map mCountByColor = new HashMap<>(); - private final Map mMeanIndexByColor = new HashMap<>(); - private final Set mUniqueColors = new HashSet<>(); - private final List mSwatches = new ArrayList<>(); - private final CentroidProvider mCentroidProvider; - - public WSMeansQuantizer( - float[][] means, CentroidProvider centroidProvider, int[] pixels, int maxColors) { - if (pixels == null) { - pixels = new int[]{}; - } - mCentroidProvider = centroidProvider; - mMeans = new Mean[maxColors]; - for (int i = 0; i < means.length; i++) { - mMeans[i] = new Mean(means[i]); - } +public final class WSMeansQuantizer implements Quantizer { + private static final String TAG = "QuantizerWsmeans"; + private static final boolean DEBUG = false; + private static final int MAX_ITERATIONS = 10; + // Points won't be moved to a closer cluster, if the closer cluster is within + // this distance. 3.0 used because L*a*b* delta E < 3 is considered imperceptible. + private static final float MIN_MOVEMENT_DISTANCE = 3.0f; - if (maxColors > means.length) { - // Always initialize Random with the same seed. Ensures the results of quantization - // are consistent, even when random centroids are required. - Random random = new Random(0x42688); - int randomMeansToCreate = maxColors - means.length; - for (int i = 0; i < randomMeansToCreate; i++) { - mMeans[means.length + i] = new Mean(100, random); - } - } + private final PointProvider mPointProvider; + private @Nullable Map mInputPixelToCount; + private float[][] mClusters; + private int[] mClusterPopulations; + private float[][] mPoints; + private int[] mPixels; + private int[] mClusterIndices; + private int[][] mIndexMatrix = {}; + private float[][] mDistanceMatrix = {}; - for (int pixel : pixels) { - // These are pixels from the bitmap that is being quantized. - // Depending on the bitmap & downscaling, it may have pixels that are less than opaque - // Ignore those pixels. - /// - // Note: they don't _have_ to be ignored, for example, we could instead turn them - // opaque. Traditionally, including outside Android, quantizers ignore transparent - // pixels, so that strategy was chosen. - int alpha = (pixel >> 24) & 0xff; - if (alpha < 255) { - continue; - } - Integer currentCount = mCountByColor.get(pixel); - if (currentCount == null) { - currentCount = 0; - mUniqueColors.add(pixel); - } - mCountByColor.put(pixel, currentCount + 1); - } - for (int color : mUniqueColors) { - int closestMeanIndex = -1; - double closestMeanDistance = -1; - float[] centroid = mCentroidProvider.getCentroid(color); - for (int i = 0; i < mMeans.length; i++) { - double distance = mCentroidProvider.distance(centroid, mMeans[i].center); - if (closestMeanIndex == -1 || distance < closestMeanDistance) { - closestMeanIndex = i; - closestMeanDistance = distance; - } - } - mMeanIndexByColor.put(color, closestMeanIndex); - } + private Palette mPalette; - if (pixels.length == 0) { - return; + public WSMeansQuantizer(int[] inClusters, PointProvider pointProvider, + @Nullable Map inputPixelToCount) { + mPointProvider = pointProvider; + + mClusters = new float[inClusters.length][3]; + int index = 0; + for (int cluster : inClusters) { + float[] point = pointProvider.fromInt(cluster); + mClusters[index++] = point; } - predict(maxColors, 0); + mInputPixelToCount = inputPixelToCount; } - /** Create starting centroids for K-means from a set of colors. */ - public static float[][] createStartingCentroids(CentroidProvider centroidProvider, - List swatches) { - float[][] startingCentroids = new float[swatches.size()][]; - for (int i = 0; i < swatches.size(); i++) { - startingCentroids[i] = centroidProvider.getCentroid(swatches.get(i).getInt()); - } - return startingCentroids; + @Override + public List getQuantizedColors() { + return mPalette.getSwatches(); } - /** Create random starting centroids for K-means. */ - public static float[][] randomMeans(int maxColors, int upperBound) { - float[][] means = new float[maxColors][]; + @Override + public void quantize(@NonNull int[] pixels, int maxColors) { + assert (pixels.length > 0); - // Always initialize Random with the same seed. Ensures the results of quantization - // are consistent, even when random centroids are required. - Random random = new Random(0x42688); + if (mInputPixelToCount == null) { + QuantizerMap mapQuantizer = new QuantizerMap(); + mapQuantizer.quantize(pixels, maxColors); + mInputPixelToCount = mapQuantizer.getColorToCount(); + } + + mPoints = new float[mInputPixelToCount.size()][3]; + mPixels = new int[mInputPixelToCount.size()]; + int index = 0; + for (int pixel : mInputPixelToCount.keySet()) { + mPixels[index] = pixel; + mPoints[index] = mPointProvider.fromInt(pixel); + index++; + } + if (mClusters.length > 0) { + // This implies that the constructor was provided starting clusters. If that was the + // case, we limit the number of clusters to the number of starting clusters and don't + // initialize random clusters. + maxColors = Math.min(maxColors, mClusters.length); + } + maxColors = Math.min(maxColors, mPoints.length); + + initializeClusters(maxColors); + for (int i = 0; i < MAX_ITERATIONS; i++) { + calculateClusterDistances(maxColors); + if (!reassignPoints(maxColors)) { + break; + } + recalculateClusterCenters(maxColors); + } + + List swatches = new ArrayList<>(); for (int i = 0; i < maxColors; i++) { - means[i] = new Mean(upperBound, random).center; + float[] cluster = mClusters[i]; + int colorInt = mPointProvider.toInt(cluster); + swatches.add(new Palette.Swatch(colorInt, mClusterPopulations[i])); } - return means; + mPalette = Palette.from(swatches); } - @Override - public void quantize(int[] pixels, int maxColors) { + private void initializeClusters(int maxColors) { + boolean hadInputClusters = mClusters.length > 0; + if (!hadInputClusters) { + int additionalClustersNeeded = maxColors - mClusters.length; + if (DEBUG) { + Log.d(TAG, "have " + mClusters.length + " clusters, want " + maxColors + + " results, so need " + additionalClustersNeeded + " additional clusters"); + } - } + Random random = new Random(0x42688); + List additionalClusters = new ArrayList<>(additionalClustersNeeded); + Set clusterIndicesUsed = new HashSet<>(); + for (int i = 0; i < additionalClustersNeeded; i++) { + int index = random.nextInt(mPoints.length); + while (clusterIndicesUsed.contains(index) + && clusterIndicesUsed.size() < mPoints.length) { + index = random.nextInt(mPoints.length); + } + clusterIndicesUsed.add(index); + additionalClusters.add(mPoints[index]); + } - @Override - public List getQuantizedColors() { - return mSwatches; + float[][] newClusters = (float[][]) additionalClusters.toArray(); + float[][] clusters = Arrays.copyOf(mClusters, maxColors); + System.arraycopy(newClusters, 0, clusters, clusters.length, newClusters.length); + mClusters = clusters; + } + + mClusterIndices = new int[mPixels.length]; + mClusterPopulations = new int[mPixels.length]; + Random random = new Random(0x42688); + for (int i = 0; i < mPixels.length; i++) { + int clusterIndex = random.nextInt(maxColors); + mClusterIndices[i] = clusterIndex; + mClusterPopulations[i] = mInputPixelToCount.get(mPixels[i]); + } } - private void predict(int maxColors, int iterationsCompleted) { - double[][] centroidDistance = new double[maxColors][maxColors]; + void calculateClusterDistances(int maxColors) { + if (mDistanceMatrix.length != maxColors) { + mDistanceMatrix = new float[maxColors][maxColors]; + } + for (int i = 0; i <= maxColors; i++) { for (int j = i + 1; j < maxColors; j++) { - float[] meanI = mMeans[i].center; - float[] meanJ = mMeans[j].center; - double distance = mCentroidProvider.distance(meanI, meanJ); - centroidDistance[i][j] = distance; - centroidDistance[j][i] = distance; + float distance = mPointProvider.distance(mClusters[i], mClusters[j]); + mDistanceMatrix[j][i] = distance; + mDistanceMatrix[i][j] = distance; } } - // Construct a K×K matrix M in which row i is a permutation of - // 1,2,…,K that represents the clusters in increasing order of - // distance of their centers from ci; - int[][] distanceMatrix = new int[maxColors][maxColors]; + if (mIndexMatrix.length != maxColors) { + mIndexMatrix = new int[maxColors][maxColors]; + } + for (int i = 0; i < maxColors; i++) { - double[] distancesFromIToAnotherMean = centroidDistance[i]; - double[] sortedByDistanceAscending = distancesFromIToAnotherMean.clone(); - Arrays.sort(sortedByDistanceAscending); - int[] outputRow = new int[maxColors]; + ArrayList distances = new ArrayList<>(maxColors); + for (int index = 0; index < maxColors; index++) { + distances.add(new Distance(index, mDistanceMatrix[i][index])); + } + distances.sort( + (a, b) -> Float.compare(a.getDistance(), b.getDistance())); + for (int j = 0; j < maxColors; j++) { - outputRow[j] = findIndex(distancesFromIToAnotherMean, sortedByDistanceAscending[j]); + mIndexMatrix[i][j] = distances.get(j).getIndex(); } - distanceMatrix[i] = outputRow; } + } + + boolean reassignPoints(int maxColors) { + boolean colorMoved = false; + for (int i = 0; i < mPoints.length; i++) { + float[] point = mPoints[i]; + int previousClusterIndex = mClusterIndices[i]; + float[] previousCluster = mClusters[previousClusterIndex]; + float previousDistance = mPointProvider.distance(point, previousCluster); - // for (i=1;i≤N′;i=i+ 1) do - // Let Sp be the cluster that xi was assigned to in the previous - // iteration; - // p=m[i]; - // min_dist=prev_dist=jjxi−cpjj2; - boolean anyColorMoved = false; - for (int intColor : mUniqueColors) { - float[] color = mCentroidProvider.getCentroid(intColor); - int indexOfCurrentMean = mMeanIndexByColor.get(intColor); - Mean currentMean = mMeans[indexOfCurrentMean]; - double minDistance = mCentroidProvider.distance(color, currentMean.center); + float minimumDistance = previousDistance; + int newClusterIndex = -1; for (int j = 1; j < maxColors; j++) { - int indexOfClusterFromCurrentToJ = distanceMatrix[indexOfCurrentMean][j]; - double distanceBetweenJAndCurrent = - centroidDistance[indexOfCurrentMean][indexOfClusterFromCurrentToJ]; - if (distanceBetweenJAndCurrent >= (4 * minDistance)) { + int t = mIndexMatrix[previousClusterIndex][j]; + if (mDistanceMatrix[previousClusterIndex][t] >= 4 * previousDistance) { + // Triangle inequality proves there's can be no closer center. break; } - double distanceBetweenJAndColor = mCentroidProvider.distance(mMeans[j].center, - color); - if (distanceBetweenJAndColor < minDistance) { - minDistance = distanceBetweenJAndColor; - mMeanIndexByColor.remove(intColor); - mMeanIndexByColor.put(intColor, j); - anyColorMoved = true; + float distance = mPointProvider.distance(point, mClusters[t]); + if (distance < minimumDistance) { + minimumDistance = distance; + newClusterIndex = t; } } - } - - List buckets = new ArrayList<>(); - for (int i = 0; i < maxColors; i++) { - buckets.add(new MeanBucket()); - } - - for (int intColor : mUniqueColors) { - int meanIndex = mMeanIndexByColor.get(intColor); - MeanBucket meanBucket = buckets.get(meanIndex); - meanBucket.add(mCentroidProvider.getCentroid(intColor), intColor, - mCountByColor.get(intColor)); - } - - List swatches = new ArrayList<>(); - boolean done = !anyColorMoved && iterationsCompleted > 0 || iterationsCompleted >= 100; - if (done) { - for (int i = 0; i < buckets.size(); i++) { - MeanBucket a = buckets.get(i); - if (a.mCount <= 0) { - continue; - } - List bucketsToMerge = new ArrayList<>(); - for (int j = i + 1; j < buckets.size(); j++) { - MeanBucket b = buckets.get(j); - if (b.mCount == 0) { - continue; - } - float[] bCentroid = b.getCentroid(); - assert (a.mCount > 0); - assert (a.getCentroid() != null); - - assert (bCentroid != null); - if (mCentroidProvider.distance(a.getCentroid(), b.getCentroid()) < 5) { - bucketsToMerge.add(b); - } - } - - for (MeanBucket bucketToMerge : bucketsToMerge) { - float[] centroid = bucketToMerge.getCentroid(); - a.add(centroid, mCentroidProvider.getColor(centroid), bucketToMerge.mCount); - buckets.remove(bucketToMerge); + if (newClusterIndex != -1) { + float distanceChange = (float) + Math.abs((Math.sqrt(minimumDistance) - Math.sqrt(previousDistance))); + if (distanceChange > MIN_MOVEMENT_DISTANCE) { + colorMoved = true; + mClusterIndices[i] = newClusterIndex; } } + } + return colorMoved; + } - for (MeanBucket bucket : buckets) { - float[] centroid = bucket.getCentroid(); - if (centroid == null) { - continue; - } + void recalculateClusterCenters(int maxColors) { + mClusterPopulations = new int[maxColors]; + float[] aSums = new float[maxColors]; + float[] bSums = new float[maxColors]; + float[] cSums = new float[maxColors]; + for (int i = 0; i < mPoints.length; i++) { + int clusterIndex = mClusterIndices[i]; + float[] point = mPoints[i]; + int pixel = mPixels[i]; + int count = mInputPixelToCount.get(pixel); + mClusterPopulations[clusterIndex] += count; + aSums[clusterIndex] += point[0] * count; + bSums[clusterIndex] += point[1] * count; + cSums[clusterIndex] += point[2] * count; - int rgb = mCentroidProvider.getColor(centroid); - swatches.add(new Palette.Swatch(rgb, bucket.mCount)); - mSwatches.clear(); - mSwatches.addAll(swatches); - } - } else { - List emptyBuckets = new ArrayList<>(); - for (int i = 0; i < buckets.size(); i++) { - MeanBucket bucket = buckets.get(i); - if ((bucket.getCentroid() == null) || (bucket.mCount == 0)) { - emptyBuckets.add(bucket); - for (Integer color : mUniqueColors) { - int meanIndex = mMeanIndexByColor.get(color); - if (meanIndex > i) { - mMeanIndexByColor.put(color, meanIndex--); - } - } - } - } + } + for (int i = 0; i < maxColors; i++) { + int count = mClusterPopulations[i]; + float aSum = aSums[i]; + float bSum = bSums[i]; + float cSum = cSums[i]; + mClusters[i][0] = aSum / count; + mClusters[i][1] = bSum / count; + mClusters[i][2] = cSum / count; + } + } - Mean[] newMeans = new Mean[buckets.size()]; - for (int i = 0; i < buckets.size(); i++) { - float[] centroid = buckets.get(i).getCentroid(); - newMeans[i] = new Mean(centroid); - } + private static class Distance { + private final int mIndex; + private final float mDistance; - predict(buckets.size(), iterationsCompleted + 1); + int getIndex() { + return mIndex; } - } + float getDistance() { + return mDistance; + } - private static int findIndex(double[] list, double element) { - for (int i = 0; i < list.length; i++) { - if (list[i] == element) { - return i; - } + Distance(int index, float distance) { + mIndex = index; + mDistance = distance; } - throw new IllegalArgumentException("Element not in list"); } } diff --git a/core/java/com/android/internal/graphics/palette/WuQuantizer.java b/core/java/com/android/internal/graphics/palette/WuQuantizer.java index a2652ea6d5e1..1cd0d721bce4 100644 --- a/core/java/com/android/internal/graphics/palette/WuQuantizer.java +++ b/core/java/com/android/internal/graphics/palette/WuQuantizer.java @@ -16,431 +16,447 @@ package com.android.internal.graphics.palette; +import static java.lang.System.arraycopy; + +import android.annotation.NonNull; +import android.annotation.Nullable; +import android.graphics.Color; + import java.util.ArrayList; import java.util.List; +import java.util.Map; +import java.util.Set; -// All reference Wu implementations are based on the original C code by Wu. -// Comments on methods are the same as in the original implementation, and the comment below -// is the original class header. /** - * Wu's Color Quantizer (v. 2) (see Graphics Gems vol. II, pp. 126-133) Author: Xiaolin Wu + * Wu's quantization algorithm is a box-cut quantizer that minimizes variance. It takes longer to + * run than, say, median color cut, but provides the highest quality results currently known. + * + * Prefer `QuantizerCelebi`: coupled with Kmeans, this provides the best-known results for image + * quantization. * - *

Algorithm: Greedy orthogonal bipartition of RGB space for variance minimization aided by - * inclusion-exclusion tricks. For speed no nearest neighbor search is done. Slightly better - * performance can be expected by more sophisticated but more expensive versions. + * Seemingly all Wu implementations are based off of one C code snippet that cites a book from 1992 + * Graphics Gems vol. II, pp. 126-133. As a result, it is very hard to understand the mechanics of + * the algorithm, beyond the commentary provided in the C code. Comments on the methods of this + * class are avoided in favor of finding another implementation and reading the commentary there, + * avoiding perpetuating the same incomplete and somewhat confusing commentary here. */ -public class WuQuantizer implements Quantizer { - private static final int MAX_COLORS = 256; - private static final int RED = 2; - private static final int GREEN = 1; - private static final int BLUE = 0; - - private static final int QUANT_SIZE = 33; - private final List mSwatches = new ArrayList<>(); +public final class WuQuantizer implements Quantizer { + // A histogram of all the input colors is constructed. It has the shape of a + // cube. The cube would be too large if it contained all 16 million colors: + // historical best practice is to use 5 bits of the 8 in each channel, + // reducing the histogram to a volume of ~32,000. + private static final int BITS = 5; + private static final int MAX_INDEX = 32; + private static final int SIDE_LENGTH = 33; + private static final int TOTAL_SIZE = 35937; + + private int[] mWeights; + private int[] mMomentsR; + private int[] mMomentsG; + private int[] mMomentsB; + private double[] mMoments; + private Box[] mCubes; + private Palette mPalette; + private int[] mColors; + private Map mInputPixelToCount; @Override public List getQuantizedColors() { - return mSwatches; + return mPalette.getSwatches(); } - private static final class Box { - int mR0; /* min value, exclusive */ - int mR1; /* max value, inclusive */ - int mG0; - int mG1; - int mB0; - int mB1; - int mVol; + @Override + public void quantize(@NonNull int[] pixels, int colorCount) { + assert (pixels.length > 0); + + QuantizerMap quantizerMap = new QuantizerMap(); + quantizerMap.quantize(pixels, colorCount); + mInputPixelToCount = quantizerMap.getColorToCount(); + // Extraction should not be run on using a color count higher than the number of colors + // in the pixels. The algorithm doesn't expect that to be the case, unexpected results and + // exceptions may occur. + Set uniqueColors = mInputPixelToCount.keySet(); + if (uniqueColors.size() <= colorCount) { + mColors = new int[mInputPixelToCount.keySet().size()]; + int index = 0; + for (int color : uniqueColors) { + mColors[index++] = color; + } + } else { + constructHistogram(mInputPixelToCount); + createMoments(); + CreateBoxesResult createBoxesResult = createBoxes(colorCount); + mColors = createResult(createBoxesResult.mResultCount); + } + + List swatches = new ArrayList<>(); + for (int color : mColors) { + swatches.add(new Palette.Swatch(color, 0)); + } + mPalette = Palette.from(swatches); } - private final int mSize; /* image size, in bytes. */ - private int mMaxColors; - private int[] mQadd; - private final int[] mPixels; + @Nullable + public int[] getColors() { + return mColors; + } - private final double[][][] mM2 = new double[QUANT_SIZE][QUANT_SIZE][QUANT_SIZE]; - private final long[][][] mWt = new long[QUANT_SIZE][QUANT_SIZE][QUANT_SIZE]; - private final long[][][] mMr = new long[QUANT_SIZE][QUANT_SIZE][QUANT_SIZE]; - private final long[][][] mMg = new long[QUANT_SIZE][QUANT_SIZE][QUANT_SIZE]; - private final long[][][] mMb = new long[QUANT_SIZE][QUANT_SIZE][QUANT_SIZE]; + /** Keys are color ints, values are the number of pixels in the image matching that color int */ + @Nullable + public Map inputPixelToCount() { + return mInputPixelToCount; + } - public WuQuantizer(int[] pixels, int maxColorCount) { - if (pixels == null) { - pixels = new int[]{}; - } - this.mPixels = pixels; - this.mSize = pixels.length; + private static int getIndex(int r, int g, int b) { + return (r << 10) + (r << 6) + (g << 5) + r + g + b; } - @Override - public void quantize(int[] colors, int maxColorCount) { - // All of the sample Wu implementations are reimplementations of a snippet of C code from - // the early 90s. They all cap the maximum # of colors at 256, and it is impossible to tell - // if this is a requirement, a consequence of QUANT_SIZE, or arbitrary. - // - // Also, the number of maximum colors should be capped at the number of pixels - otherwise, - // If extraction is run on a set of pixels whose count is less than max colors, - // then colors.length < max colors, and accesses to colors[index] throw an - // ArrayOutOfBoundsException. - this.mMaxColors = Math.min(Math.min(MAX_COLORS, maxColorCount), colors.length); - Box[] cube = new Box[mMaxColors]; - int red, green, blue; - - int next, i, k; - long weight; - double[] vv = new double[mMaxColors]; - double temp; - - compute3DHistogram(mWt, mMr, mMg, mMb, mM2); - computeMoments(mWt, mMr, mMg, mMb, mM2); - - for (i = 0; i < mMaxColors; i++) { - cube[i] = new Box(); + private void constructHistogram(Map pixels) { + mWeights = new int[TOTAL_SIZE]; + mMomentsR = new int[TOTAL_SIZE]; + mMomentsG = new int[TOTAL_SIZE]; + mMomentsB = new int[TOTAL_SIZE]; + mMoments = new double[TOTAL_SIZE]; + + for (Map.Entry pair : pixels.entrySet()) { + int pixel = pair.getKey(); + int count = pair.getValue(); + int red = Color.red(pixel); + int green = Color.green(pixel); + int blue = Color.blue(pixel); + int bitsToRemove = 8 - BITS; + int iR = (red >> bitsToRemove) + 1; + int iG = (green >> bitsToRemove) + 1; + int iB = (blue >> bitsToRemove) + 1; + int index = getIndex(iR, iG, iB); + mWeights[index] += count; + mMomentsR[index] += (red * count); + mMomentsG[index] += (green * count); + mMomentsB[index] += (blue * count); + mMoments[index] += (count * ((red * red) + (green * green) + (blue * blue))); } + } - cube[0].mR0 = cube[0].mG0 = cube[0].mB0 = 0; - cube[0].mR1 = cube[0].mG1 = cube[0].mB1 = QUANT_SIZE - 1; - next = 0; + private void createMoments() { + for (int r = 1; r < SIDE_LENGTH; ++r) { + int[] area = new int[SIDE_LENGTH]; + int[] areaR = new int[SIDE_LENGTH]; + int[] areaG = new int[SIDE_LENGTH]; + int[] areaB = new int[SIDE_LENGTH]; + double[] area2 = new double[SIDE_LENGTH]; + + for (int g = 1; g < SIDE_LENGTH; ++g) { + int line = 0; + int lineR = 0; + int lineG = 0; + int lineB = 0; + + double line2 = 0.0; + for (int b = 1; b < SIDE_LENGTH; ++b) { + int index = getIndex(r, g, b); + line += mWeights[index]; + lineR += mMomentsR[index]; + lineG += mMomentsG[index]; + lineB += mMomentsB[index]; + line2 += mMoments[index]; + + area[b] += line; + areaR[b] += lineR; + areaG[b] += lineG; + areaB[b] += lineB; + area2[b] += line2; + + int previousIndex = getIndex(r - 1, g, b); + mWeights[index] = mWeights[previousIndex] + area[b]; + mMomentsR[index] = mMomentsR[previousIndex] + areaR[b]; + mMomentsG[index] = mMomentsG[previousIndex] + areaG[b]; + mMomentsB[index] = mMomentsB[previousIndex] + areaB[b]; + mMoments[index] = mMoments[previousIndex] + area2[b]; + } + } + } + } - for (i = 1; i < mMaxColors; ++i) { - if (cut(cube[next], cube[i])) { - vv[next] = (cube[next].mVol > 1) ? getVariance(cube[next]) : 0.0f; - vv[i] = (cube[i].mVol > 1) ? getVariance(cube[i]) : 0.0f; + private CreateBoxesResult createBoxes(int maxColorCount) { + mCubes = new Box[maxColorCount]; + for (int i = 0; i < maxColorCount; i++) { + mCubes[i] = new Box(); + } + double[] volumeVariance = new double[maxColorCount]; + Box firstBox = mCubes[0]; + firstBox.r1 = MAX_INDEX; + firstBox.g1 = MAX_INDEX; + firstBox.b1 = MAX_INDEX; + + int generatedColorCount = 0; + int next = 0; + + for (int i = 1; i < maxColorCount; i++) { + if (cut(mCubes[next], mCubes[i])) { + volumeVariance[next] = (mCubes[next].vol > 1) ? variance(mCubes[next]) : 0.0; + volumeVariance[i] = (mCubes[i].vol > 1) ? variance(mCubes[i]) : 0.0; } else { - vv[next] = 0.0f; + volumeVariance[next] = 0.0; i--; } + next = 0; - temp = vv[0]; - for (k = 1; k <= i; ++k) { - if (vv[k] > temp) { - temp = vv[k]; + + double temp = volumeVariance[0]; + for (int k = 1; k <= i; k++) { + if (volumeVariance[k] > temp) { + temp = volumeVariance[k]; next = k; } } - if (temp <= 0.0f) { + generatedColorCount = i + 1; + if (temp <= 0.0) { break; } } - for (k = 0; k < mMaxColors; ++k) { - weight = getVolume(cube[k], mWt); + return new CreateBoxesResult(maxColorCount, generatedColorCount); + } + + private int[] createResult(int colorCount) { + int[] colors = new int[colorCount]; + int nextAvailableIndex = 0; + for (int i = 0; i < colorCount; ++i) { + Box cube = mCubes[i]; + int weight = volume(cube, mWeights); if (weight > 0) { - red = (int) (getVolume(cube[k], mMr) / weight); - green = (int) (getVolume(cube[k], mMg) / weight); - blue = (int) (getVolume(cube[k], mMb) / weight); - colors[k] = (255 << 24) | (red << 16) | (green << 8) | blue; - } else { - colors[k] = 0; + int r = (volume(cube, mMomentsR) / weight); + int g = (volume(cube, mMomentsG) / weight); + int b = (volume(cube, mMomentsB) / weight); + int color = Color.rgb(r, g, b); + colors[nextAvailableIndex++] = color; } } + int[] resultArray = new int[nextAvailableIndex]; + arraycopy(colors, 0, resultArray, 0, nextAvailableIndex); + return resultArray; + } - int bitsPerPixel = 0; - while ((1 << bitsPerPixel) < mMaxColors) { - bitsPerPixel++; - } + private double variance(Box cube) { + int dr = volume(cube, mMomentsR); + int dg = volume(cube, mMomentsG); + int db = volume(cube, mMomentsB); + double xx = + mMoments[getIndex(cube.r1, cube.g1, cube.b1)] + - mMoments[getIndex(cube.r1, cube.g1, cube.b0)] + - mMoments[getIndex(cube.r1, cube.g0, cube.b1)] + + mMoments[getIndex(cube.r1, cube.g0, cube.b0)] + - mMoments[getIndex(cube.r0, cube.g1, cube.b1)] + + mMoments[getIndex(cube.r0, cube.g1, cube.b0)] + + mMoments[getIndex(cube.r0, cube.g0, cube.b1)] + - mMoments[getIndex(cube.r0, cube.g0, cube.b0)]; + + int hypotenuse = (dr * dr + dg * dg + db * db); + int volume2 = volume(cube, mWeights); + double variance2 = xx - ((double) hypotenuse / (double) volume2); + return variance2; + } - List swatches = new ArrayList<>(); - for (int l = 0; l < k; l++) { - int pixel = colors[l]; - if (pixel == 0) { - continue; + private boolean cut(Box one, Box two) { + int wholeR = volume(one, mMomentsR); + int wholeG = volume(one, mMomentsG); + int wholeB = volume(one, mMomentsB); + int wholeW = volume(one, mWeights); + + MaximizeResult maxRResult = + maximize(one, Direction.RED, one.r0 + 1, one.r1, wholeR, wholeG, wholeB, wholeW); + MaximizeResult maxGResult = + maximize(one, Direction.GREEN, one.g0 + 1, one.g1, wholeR, wholeG, wholeB, wholeW); + MaximizeResult maxBResult = + maximize(one, Direction.BLUE, one.b0 + 1, one.b1, wholeR, wholeG, wholeB, wholeW); + Direction cutDirection; + double maxR = maxRResult.mMaximum; + double maxG = maxGResult.mMaximum; + double maxB = maxBResult.mMaximum; + if (maxR >= maxG && maxR >= maxB) { + if (maxRResult.mCutLocation < 0) { + return false; } - swatches.add(new Palette.Swatch(pixel, 0)); + cutDirection = Direction.RED; + } else if (maxG >= maxR && maxG >= maxB) { + cutDirection = Direction.GREEN; + } else { + cutDirection = Direction.BLUE; } - mSwatches.clear(); - mSwatches.addAll(swatches); - } - /* Histogram is in elements 1..HISTSIZE along each axis, - * element 0 is for base or marginal value - * NB: these must start out 0! - */ - private void compute3DHistogram( - long[][][] vwt, long[][][] vmr, long[][][] vmg, long[][][] vmb, double[][][] m2) { - // build 3-D color histogram of counts, r/g/b, and c^2 - int r, g, b; - int i; - int inr; - int ing; - int inb; - int[] table = new int[256]; - - for (i = 0; i < 256; i++) { - table[i] = i * i; + two.r1 = one.r1; + two.g1 = one.g1; + two.b1 = one.b1; + + switch (cutDirection) { + case RED: + one.r1 = maxRResult.mCutLocation; + two.r0 = one.r1; + two.g0 = one.g0; + two.b0 = one.b0; + break; + case GREEN: + one.g1 = maxGResult.mCutLocation; + two.r0 = one.r0; + two.g0 = one.g1; + two.b0 = one.b0; + break; + case BLUE: + one.b1 = maxBResult.mCutLocation; + two.r0 = one.r0; + two.g0 = one.g0; + two.b0 = one.b1; + break; + default: + throw new IllegalArgumentException("unexpected direction " + cutDirection); } - mQadd = new int[mSize]; + one.vol = (one.r1 - one.r0) * (one.g1 - one.g0) * (one.b1 - one.b0); + two.vol = (two.r1 - two.r0) * (two.g1 - two.g0) * (two.b1 - two.b0); - for (i = 0; i < mSize; ++i) { - int rgb = mPixels[i]; - // Skip less than opaque pixels. They're not meaningful in the context of palette - // generation for UI schemes. - if ((rgb >>> 24) < 0xff) { - continue; - } - r = ((rgb >> 16) & 0xff); - g = ((rgb >> 8) & 0xff); - b = (rgb & 0xff); - inr = (r >> 3) + 1; - ing = (g >> 3) + 1; - inb = (b >> 3) + 1; - mQadd[i] = (inr << 10) + (inr << 6) + inr + (ing << 5) + ing + inb; - /*[inr][ing][inb]*/ - ++vwt[inr][ing][inb]; - vmr[inr][ing][inb] += r; - vmg[inr][ing][inb] += g; - vmb[inr][ing][inb] += b; - m2[inr][ing][inb] += table[r] + table[g] + table[b]; - } + return true; } - /* At conclusion of the histogram step, we can interpret - * wt[r][g][b] = sum over voxel of P(c) - * mr[r][g][b] = sum over voxel of r*P(c) , similarly for mg, mb - * m2[r][g][b] = sum over voxel of c^2*P(c) - * Actually each of these should be divided by 'size' to give the usual - * interpretation of P() as ranging from 0 to 1, but we needn't do that here. - * - * We now convert histogram into moments so that we can rapidly calculate - * the sums of the above quantities over any desired box. - */ - private void computeMoments( - long[][][] vwt, long[][][] vmr, long[][][] vmg, long[][][] vmb, double[][][] m2) { - /* compute cumulative moments. */ - int i, r, g, b; - int line, line_r, line_g, line_b; - int[] area = new int[QUANT_SIZE]; - int[] area_r = new int[QUANT_SIZE]; - int[] area_g = new int[QUANT_SIZE]; - int[] area_b = new int[QUANT_SIZE]; - double line2; - double[] area2 = new double[QUANT_SIZE]; - - for (r = 1; r < QUANT_SIZE; ++r) { - for (i = 0; i < QUANT_SIZE; ++i) { - area2[i] = area[i] = area_r[i] = area_g[i] = area_b[i] = 0; + private MaximizeResult maximize( + Box cube, + Direction direction, + int first, + int last, + int wholeR, + int wholeG, + int wholeB, + int wholeW) { + int baseR = bottom(cube, direction, mMomentsR); + int baseG = bottom(cube, direction, mMomentsG); + int baseB = bottom(cube, direction, mMomentsB); + int baseW = bottom(cube, direction, mWeights); + + double max = 0.0; + int cut = -1; + for (int i = first; i < last; i++) { + int halfR = baseR + top(cube, direction, i, mMomentsR); + int halfG = baseG + top(cube, direction, i, mMomentsG); + int halfB = baseB + top(cube, direction, i, mMomentsB); + int halfW = baseW + top(cube, direction, i, mWeights); + + if (halfW == 0) { + continue; + } + double tempNumerator = halfR * halfR + halfG * halfG + halfB * halfB; + double tempDenominator = halfW; + double temp = tempNumerator / tempDenominator; + + halfR = wholeR - halfR; + halfG = wholeG - halfG; + halfB = wholeB - halfB; + halfW = wholeW - halfW; + if (halfW == 0) { + continue; } - for (g = 1; g < QUANT_SIZE; ++g) { - line2 = line = line_r = line_g = line_b = 0; - for (b = 1; b < QUANT_SIZE; ++b) { - line += vwt[r][g][b]; - line_r += vmr[r][g][b]; - line_g += vmg[r][g][b]; - line_b += vmb[r][g][b]; - line2 += m2[r][g][b]; - - area[b] += line; - area_r[b] += line_r; - area_g[b] += line_g; - area_b[b] += line_b; - area2[b] += line2; - vwt[r][g][b] = vwt[r - 1][g][b] + area[b]; - vmr[r][g][b] = vmr[r - 1][g][b] + area_r[b]; - vmg[r][g][b] = vmg[r - 1][g][b] + area_g[b]; - vmb[r][g][b] = vmb[r - 1][g][b] + area_b[b]; - m2[r][g][b] = m2[r - 1][g][b] + area2[b]; - } + tempNumerator = halfR * halfR + halfG * halfG + halfB * halfB; + tempDenominator = halfW; + temp += (tempNumerator / tempDenominator); + if (temp > max) { + max = temp; + cut = i; } } + return new MaximizeResult(cut, max); } - private long getVolume(Box cube, long[][][] mmt) { - /* Compute sum over a box of any given statistic */ - return (mmt[cube.mR1][cube.mG1][cube.mB1] - - mmt[cube.mR1][cube.mG1][cube.mB0] - - mmt[cube.mR1][cube.mG0][cube.mB1] - + mmt[cube.mR1][cube.mG0][cube.mB0] - - mmt[cube.mR0][cube.mG1][cube.mB1] - + mmt[cube.mR0][cube.mG1][cube.mB0] - + mmt[cube.mR0][cube.mG0][cube.mB1] - - mmt[cube.mR0][cube.mG0][cube.mB0]); + private static int volume(Box cube, int[] moment) { + return (moment[getIndex(cube.r1, cube.g1, cube.b1)] + - moment[getIndex(cube.r1, cube.g1, cube.b0)] + - moment[getIndex(cube.r1, cube.g0, cube.b1)] + + moment[getIndex(cube.r1, cube.g0, cube.b0)] + - moment[getIndex(cube.r0, cube.g1, cube.b1)] + + moment[getIndex(cube.r0, cube.g1, cube.b0)] + + moment[getIndex(cube.r0, cube.g0, cube.b1)] + - moment[getIndex(cube.r0, cube.g0, cube.b0)]); } - /* The next two routines allow a slightly more efficient calculation - * of Vol() for a proposed subbox of a given box. The sum of Top() - * and Bottom() is the Vol() of a subbox split in the given direction - * and with the specified new upper bound. - */ - private long getBottom(Box cube, int dir, long[][][] mmt) { - /* Compute part of Vol(cube, mmt) that doesn't depend on r1, g1, or b1 */ - /* (depending on dir) */ - switch (dir) { + private static int bottom(Box cube, Direction direction, int[] moment) { + switch (direction) { case RED: - return (-mmt[cube.mR0][cube.mG1][cube.mB1] - + mmt[cube.mR0][cube.mG1][cube.mB0] - + mmt[cube.mR0][cube.mG0][cube.mB1] - - mmt[cube.mR0][cube.mG0][cube.mB0]); + return -moment[getIndex(cube.r0, cube.g1, cube.b1)] + + moment[getIndex(cube.r0, cube.g1, cube.b0)] + + moment[getIndex(cube.r0, cube.g0, cube.b1)] + - moment[getIndex(cube.r0, cube.g0, cube.b0)]; case GREEN: - return (-mmt[cube.mR1][cube.mG0][cube.mB1] - + mmt[cube.mR1][cube.mG0][cube.mB0] - + mmt[cube.mR0][cube.mG0][cube.mB1] - - mmt[cube.mR0][cube.mG0][cube.mB0]); + return -moment[getIndex(cube.r1, cube.g0, cube.b1)] + + moment[getIndex(cube.r1, cube.g0, cube.b0)] + + moment[getIndex(cube.r0, cube.g0, cube.b1)] + - moment[getIndex(cube.r0, cube.g0, cube.b0)]; case BLUE: - return (-mmt[cube.mR1][cube.mG1][cube.mB0] - + mmt[cube.mR1][cube.mG0][cube.mB0] - + mmt[cube.mR0][cube.mG1][cube.mB0] - - mmt[cube.mR0][cube.mG0][cube.mB0]); + return -moment[getIndex(cube.r1, cube.g1, cube.b0)] + + moment[getIndex(cube.r1, cube.g0, cube.b0)] + + moment[getIndex(cube.r0, cube.g1, cube.b0)] + - moment[getIndex(cube.r0, cube.g0, cube.b0)]; default: - return 0; + throw new IllegalArgumentException("unexpected direction " + direction); } } - private long getTop(Box cube, int dir, int pos, long[][][] mmt) { - /* Compute remainder of Vol(cube, mmt), substituting pos for */ - /* r1, g1, or b1 (depending on dir) */ - switch (dir) { + private static int top(Box cube, Direction direction, int position, int[] moment) { + switch (direction) { case RED: - return (mmt[pos][cube.mG1][cube.mB1] - - mmt[pos][cube.mG1][cube.mB0] - - mmt[pos][cube.mG0][cube.mB1] - + mmt[pos][cube.mG0][cube.mB0]); + return (moment[getIndex(position, cube.g1, cube.b1)] + - moment[getIndex(position, cube.g1, cube.b0)] + - moment[getIndex(position, cube.g0, cube.b1)] + + moment[getIndex(position, cube.g0, cube.b0)]); case GREEN: - return (mmt[cube.mR1][pos][cube.mB1] - - mmt[cube.mR1][pos][cube.mB0] - - mmt[cube.mR0][pos][cube.mB1] - + mmt[cube.mR0][pos][cube.mB0]); + return (moment[getIndex(cube.r1, position, cube.b1)] + - moment[getIndex(cube.r1, position, cube.b0)] + - moment[getIndex(cube.r0, position, cube.b1)] + + moment[getIndex(cube.r0, position, cube.b0)]); case BLUE: - return (mmt[cube.mR1][cube.mG1][pos] - - mmt[cube.mR1][cube.mG0][pos] - - mmt[cube.mR0][cube.mG1][pos] - + mmt[cube.mR0][cube.mG0][pos]); + return (moment[getIndex(cube.r1, cube.g1, position)] + - moment[getIndex(cube.r1, cube.g0, position)] + - moment[getIndex(cube.r0, cube.g1, position)] + + moment[getIndex(cube.r0, cube.g0, position)]); default: - return 0; + throw new IllegalArgumentException("unexpected direction " + direction); } } - private double getVariance(Box cube) { - /* Compute the weighted variance of a box */ - /* NB: as with the raw statistics, this is really the variance * size */ - double dr, dg, db, xx; - dr = getVolume(cube, mMr); - dg = getVolume(cube, mMg); - db = getVolume(cube, mMb); - xx = - mM2[cube.mR1][cube.mG1][cube.mB1] - - mM2[cube.mR1][cube.mG1][cube.mB0] - - mM2[cube.mR1][cube.mG0][cube.mB1] - + mM2[cube.mR1][cube.mG0][cube.mB0] - - mM2[cube.mR0][cube.mG1][cube.mB1] - + mM2[cube.mR0][cube.mG1][cube.mB0] - + mM2[cube.mR0][cube.mG0][cube.mB1] - - mM2[cube.mR0][cube.mG0][cube.mB0]; - return xx - (dr * dr + dg * dg + db * db) / getVolume(cube, mWt); + private enum Direction { + RED, + GREEN, + BLUE } - /* We want to minimize the sum of the variances of two subboxes. - * The sum(c^2) terms can be ignored since their sum over both subboxes - * is the same (the sum for the whole box) no matter where we split. - * The remaining terms have a minus sign in the variance formula, - * so we drop the minus sign and MAXIMIZE the sum of the two terms. - */ - private double maximize( - Box cube, - int dir, - int first, - int last, - int[] cut, - long wholeR, - long wholeG, - long wholeB, - long wholeW) { - long half_r, half_g, half_b, half_w; - long base_r, base_g, base_b, base_w; - int i; - double temp, max; - - base_r = getBottom(cube, dir, mMr); - base_g = getBottom(cube, dir, mMg); - base_b = getBottom(cube, dir, mMb); - base_w = getBottom(cube, dir, mWt); - - max = 0.0f; - cut[0] = -1; - - for (i = first; i < last; ++i) { - half_r = base_r + getTop(cube, dir, i, mMr); - half_g = base_g + getTop(cube, dir, i, mMg); - half_b = base_b + getTop(cube, dir, i, mMb); - half_w = base_w + getTop(cube, dir, i, mWt); - /* now half_x is sum over lower half of box, if split at i */ - if (half_w == 0) /* subbox could be empty of pixels! */ { - continue; /* never split into an empty box */ - } - temp = (half_r * half_r + half_g * half_g + half_b * half_b) / (double) half_w; - half_r = wholeR - half_r; - half_g = wholeG - half_g; - half_b = wholeB - half_b; - half_w = wholeW - half_w; - if (half_w == 0) /* subbox could be empty of pixels! */ { - continue; /* never split into an empty box */ - } - temp += (half_r * half_r + half_g * half_g + half_b * half_b) / (double) half_w; + private static class MaximizeResult { + // < 0 if cut impossible + final int mCutLocation; + final double mMaximum; - if (temp > max) { - max = temp; - cut[0] = i; - } + MaximizeResult(int cut, double max) { + mCutLocation = cut; + mMaximum = max; } - - return max; } - private boolean cut(Box set1, Box set2) { - int dir; - int[] cutr = new int[1]; - int[] cutg = new int[1]; - int[] cutb = new int[1]; - double maxr, maxg, maxb; - long whole_r, whole_g, whole_b, whole_w; - - whole_r = getVolume(set1, mMr); - whole_g = getVolume(set1, mMg); - whole_b = getVolume(set1, mMb); - whole_w = getVolume(set1, mWt); - - maxr = maximize(set1, RED, set1.mR0 + 1, set1.mR1, cutr, whole_r, whole_g, whole_b, - whole_w); - maxg = maximize(set1, GREEN, set1.mG0 + 1, set1.mG1, cutg, whole_r, whole_g, whole_b, - whole_w); - maxb = maximize(set1, BLUE, set1.mB0 + 1, set1.mB1, cutb, whole_r, whole_g, whole_b, - whole_w); - - if (maxr >= maxg && maxr >= maxb) { - dir = RED; - if (cutr[0] < 0) return false; /* can't split the box */ - } else if (maxg >= maxr && maxg >= maxb) { - dir = GREEN; - } else { - dir = BLUE; - } - - set2.mR1 = set1.mR1; - set2.mG1 = set1.mG1; - set2.mB1 = set1.mB1; + private static class CreateBoxesResult { + final int mRequestedCount; + final int mResultCount; - switch (dir) { - case RED: - set2.mR0 = set1.mR1 = cutr[0]; - set2.mG0 = set1.mG0; - set2.mB0 = set1.mB0; - break; - case GREEN: - set2.mG0 = set1.mG1 = cutg[0]; - set2.mR0 = set1.mR0; - set2.mB0 = set1.mB0; - break; - case BLUE: - set2.mB0 = set1.mB1 = cutb[0]; - set2.mR0 = set1.mR0; - set2.mG0 = set1.mG0; - break; + CreateBoxesResult(int requestedCount, int resultCount) { + mRequestedCount = requestedCount; + mResultCount = resultCount; } - set1.mVol = (set1.mR1 - set1.mR0) * (set1.mG1 - set1.mG0) * (set1.mB1 - set1.mB0); - set2.mVol = (set2.mR1 - set2.mR0) * (set2.mG1 - set2.mG0) * (set2.mB1 - set2.mB0); + } - return true; + private static class Box { + public int r0 = 0; + public int r1 = 0; + public int g0 = 0; + public int g1 = 0; + public int b0 = 0; + public int b1 = 0; + public int vol = 0; } } + + -- cgit v1.2.3-59-g8ed1b