content: /*
   * 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;
      }
  }
  