| /* |
| * Copyright (C) 2017 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.util.Log; |
| |
| import com.android.internal.graphics.ColorUtils; |
| import com.android.internal.ml.clustering.KMeans; |
| |
| import java.util.ArrayList; |
| import java.util.List; |
| import java.util.Random; |
| |
| /** |
| * A quantizer that uses k-means |
| */ |
| public class VariationalKMeansQuantizer implements Quantizer { |
| |
| private static final String TAG = "KMeansQuantizer"; |
| private static final boolean DEBUG = false; |
| |
| /** |
| * Clusters closer than this value will me merged. |
| */ |
| private final float mMinClusterSqDistance; |
| |
| /** |
| * K-means can get stuck in local optima, this can be avoided by |
| * repeating it and getting the "best" execution. |
| */ |
| private final int mInitializations; |
| |
| /** |
| * Initialize KMeans with a fixed random state to have |
| * consistent results across multiple runs. |
| */ |
| private final KMeans mKMeans = new KMeans(new Random(0), 30, 0); |
| |
| private List<Palette.Swatch> mQuantizedColors; |
| |
| public VariationalKMeansQuantizer() { |
| this(0.25f /* cluster distance */); |
| } |
| |
| public VariationalKMeansQuantizer(float minClusterDistance) { |
| this(minClusterDistance, 1 /* initializations */); |
| } |
| |
| public VariationalKMeansQuantizer(float minClusterDistance, int initializations) { |
| mMinClusterSqDistance = minClusterDistance * minClusterDistance; |
| mInitializations = initializations; |
| } |
| |
| /** |
| * K-Means quantizer. |
| * |
| * @param pixels Pixels to quantize. |
| * @param maxColors Maximum number of clusters to extract. |
| * @param filters Colors that should be ignored |
| */ |
| @Override |
| public void quantize(int[] pixels, int maxColors, Palette.Filter[] filters) { |
| // Start by converting all colors to HSL. |
| // HLS is way more meaningful for clustering than RGB. |
| final float[] hsl = {0, 0, 0}; |
| final float[][] hslPixels = new float[pixels.length][3]; |
| for (int i = 0; i < pixels.length; i++) { |
| ColorUtils.colorToHSL(pixels[i], hsl); |
| // Normalize hue so all values go from 0 to 1. |
| hslPixels[i][0] = hsl[0] / 360f; |
| hslPixels[i][1] = hsl[1]; |
| hslPixels[i][2] = hsl[2]; |
| } |
| |
| final List<KMeans.Mean> optimalMeans = getOptimalKMeans(maxColors, hslPixels); |
| |
| // Ideally we should run k-means again to merge clusters but it would be too expensive, |
| // instead we just merge all clusters that are closer than a threshold. |
| for (int i = 0; i < optimalMeans.size(); i++) { |
| KMeans.Mean current = optimalMeans.get(i); |
| float[] currentCentroid = current.getCentroid(); |
| for (int j = i + 1; j < optimalMeans.size(); j++) { |
| KMeans.Mean compareTo = optimalMeans.get(j); |
| float[] compareToCentroid = compareTo.getCentroid(); |
| float sqDistance = KMeans.sqDistance(currentCentroid, compareToCentroid); |
| // Merge them |
| if (sqDistance < mMinClusterSqDistance) { |
| optimalMeans.remove(compareTo); |
| current.getItems().addAll(compareTo.getItems()); |
| for (int k = 0; k < currentCentroid.length; k++) { |
| currentCentroid[k] += (compareToCentroid[k] - currentCentroid[k]) / 2.0; |
| } |
| j--; |
| } |
| } |
| } |
| |
| // Convert data to final format, de-normalizing the hue. |
| mQuantizedColors = new ArrayList<>(); |
| for (KMeans.Mean mean : optimalMeans) { |
| if (mean.getItems().size() == 0) { |
| continue; |
| } |
| float[] centroid = mean.getCentroid(); |
| mQuantizedColors.add(new Palette.Swatch(new float[]{ |
| centroid[0] * 360f, |
| centroid[1], |
| centroid[2] |
| }, mean.getItems().size())); |
| } |
| } |
| |
| private List<KMeans.Mean> getOptimalKMeans(int k, float[][] inputData) { |
| List<KMeans.Mean> optimal = null; |
| double optimalScore = -Double.MAX_VALUE; |
| int runs = mInitializations; |
| while (runs > 0) { |
| if (DEBUG) { |
| Log.d(TAG, "k-means run: " + runs); |
| } |
| List<KMeans.Mean> means = mKMeans.predict(k, inputData); |
| double score = KMeans.score(means); |
| if (optimal == null || score > optimalScore) { |
| if (DEBUG) { |
| Log.d(TAG, "\tnew optimal score: " + score); |
| } |
| optimalScore = score; |
| optimal = means; |
| } |
| runs--; |
| } |
| |
| return optimal; |
| } |
| |
| @Override |
| public List<Palette.Swatch> getQuantizedColors() { |
| return mQuantizedColors; |
| } |
| } |