Themes: Add palettized icon background support

This feature allows a theme to supply a single icon background,
usually a white or gray scale image, which will then be tinted using
a color from a palette of six color styles.

To use this new feature a theme designer will need to include the
new <paletteback /> tag which has the following syntax:

<paletteback
    img="name_of_png_drawable"
    swatchType=["vibrant" | "vibrantLight" | "vibrantDark" | "muted" | "mutedLight" | "mutedDark"]
    defaultSwatchColor1="hex_color"
    defaultSwatchColor2="hex_color"
    ⋮
    defaultSwatchColorN="hex_color"
    />

ex:
<paletteback
    img="iconback_palette"
    swatchType="vibrantDark"
    defaultSwatchColor1="#009688"
    defaultSwatchColor2="#cc0000"
    defaultSwatchColor3="#ff8800"
    />

You should specify some default swatch colors for those cases when
the original icon did not have any colors to match the swatchType
you requested. If no default swatch colors are defined, the original
un-tinted background will be used.

Change-Id: Ifd6dd65cc34ad4cd966fa9670f68704ac5671960

6 files changed, 1675 insertions, 13 deletions

diff --git a/core/java/android/app/ComposedIconInfo.java b/core/java/android/app/ComposedIconInfo.java
index 7fab852..81d9da9 100644
--- a/core/java/android/app/ComposedIconInfo.java
+++ b/core/java/android/app/ComposedIconInfo.java
@@ -27,8 +27,15 @@ public class ComposedIconInfo implements Parcelable {
     public int iconSize;
     public float[] colorFilter;
 
+    // Palettized background items
+    public int iconPaletteBack;
+    public SwatchType swatchType;
+    public int[] defaultSwatchColors;
+
     public ComposedIconInfo() {
         super();
+        iconPaletteBack = 0;
+        swatchType = SwatchType.None;
     }
 
     private ComposedIconInfo(Parcel source) {
@@ -51,6 +58,15 @@ public class ComposedIconInfo implements Parcelable {
                 colorFilter[i] = source.readFloat();
             }
         }
+        iconPaletteBack = source.readInt();
+        swatchType = SwatchType.values()[source.readInt()];
+        int numDefaultColors = source.readInt();
+        if (numDefaultColors > 0) {
+            defaultSwatchColors = new int[numDefaultColors];
+            for (int i = 0; i < numDefaultColors; i++) {
+                defaultSwatchColors[i] = source.readInt();
+            }
+        }
     }
 
     @Override
@@ -79,6 +95,16 @@ public class ComposedIconInfo implements Parcelable {
         } else {
             dest.writeInt(0);
         }
+        dest.writeInt(iconPaletteBack);
+        dest.writeInt(swatchType.ordinal());
+        if (defaultSwatchColors != null) {
+            dest.writeInt(defaultSwatchColors.length);
+            for (int color : defaultSwatchColors) {
+                dest.writeInt(color);
+            }
+        } else {
+            dest.writeInt(0);
+        }
     }
 
     public static final Creator<ComposedIconInfo> CREATOR
@@ -93,4 +119,14 @@ public class ComposedIconInfo implements Parcelable {
             return new ComposedIconInfo[0];
         }
     };
+
+    public enum SwatchType {
+        None,
+        Vibrant,
+        VibrantLight,
+        VibrantDark,
+        Muted,
+        MutedLight,
+        MutedDark
+    }
 }
diff --git a/core/java/android/app/IconPackHelper.java b/core/java/android/app/IconPackHelper.java
index 057633f..ac30d5c 100644
--- a/core/java/android/app/IconPackHelper.java
+++ b/core/java/android/app/IconPackHelper.java
@@ -34,6 +34,7 @@ import android.graphics.ColorMatrixColorFilter;
 import android.graphics.Paint;
 import android.graphics.PaintFlagsDrawFilter;
 import android.graphics.PorterDuff;
+import android.graphics.PorterDuffColorFilter;
 import android.graphics.PorterDuffXfermode;
 import android.graphics.Rect;
 import android.graphics.drawable.BitmapDrawable;
@@ -43,6 +44,7 @@ import android.os.RemoteException;
 import android.os.ServiceManager;
 import android.util.Log;
 import android.util.TypedValue;
+import com.android.internal.util.cm.palette.Palette;
 import org.xmlpull.v1.XmlPullParser;
 import org.xmlpull.v1.XmlPullParserException;
 import org.xmlpull.v1.XmlPullParserFactory;
@@ -63,12 +65,28 @@ import android.util.DisplayMetrics;
 /** @hide */
 public class IconPackHelper {
     private static final String TAG = IconPackHelper.class.getSimpleName();
+
+    private static final boolean DEBUG = false;
+
     private static final String ICON_MASK_TAG = "iconmask";
     private static final String ICON_BACK_TAG = "iconback";
     private static final String ICON_UPON_TAG = "iconupon";
     private static final String ICON_SCALE_TAG = "scale";
     private static final String ICON_BACK_FORMAT = "iconback%d";
 
+    // Palettized icon background constants
+    private static final String ICON_PALETTIZED_BACK_TAG = "paletteback";
+    private static final String IMG_ATTR = "img";
+    private static final String SWATCH_TYPE_ATTR = "swatchType";
+    private static final String DEFAULT_SWATCH_COLOR_ATTR = "defaultSwatchColor";
+    private static final String VIBRANT_VALUE = "vibrant";
+    private static final String VIBRANT_LIGHT_VALUE = "vibrantLight";
+    private static final String VIBRANT_DARK_VALUE = "vibrantDark";
+    private static final String MUTED_VALUE = "muted";
+    private static final String MUTED_LIGHT_VALUE = "mutedLight";
+    private static final String MUTED_DARK_VALUE = "mutedDark";
+    private static final int NUM_PALETTE_COLORS = 32;
+
     private static final ComponentName ICON_BACK_COMPONENT;
     private static final ComponentName ICON_MASK_COMPONENT;
     private static final ComponentName ICON_UPON_COMPONENT;
@@ -168,9 +186,10 @@ public class IconPackHelper {
     }
 
     private boolean isComposedIconComponent(String tag) {
-        return tag.equalsIgnoreCase(ICON_MASK_TAG) ||
-                tag.equalsIgnoreCase(ICON_BACK_TAG) ||
-                tag.equalsIgnoreCase(ICON_UPON_TAG);
+        return ICON_MASK_TAG.equalsIgnoreCase(tag) ||
+                ICON_BACK_TAG.equalsIgnoreCase(tag) ||
+                ICON_UPON_TAG.equalsIgnoreCase(tag) ||
+                ICON_PALETTIZED_BACK_TAG.equalsIgnoreCase(tag);
     }
 
     private boolean parseComposedIconComponent(XmlPullParser parser,
@@ -182,13 +201,15 @@ public class IconPackHelper {
         }
 
         if (parser.getAttributeCount() >= 1) {
-            if (tag.equalsIgnoreCase(ICON_BACK_TAG)) {
+            if (ICON_BACK_TAG.equalsIgnoreCase(tag)) {
                 mIconBackCount = parser.getAttributeCount();
                 for (int i = 0; i < mIconBackCount; i++) {
                     tag = String.format(ICON_BACK_FORMAT, i);
                     icon = parser.getAttributeValue(i);
                     iconPackResources.put(new ComponentName(tag, ""), icon);
                 }
+            } else if (ICON_PALETTIZED_BACK_TAG.equalsIgnoreCase(tag)) {
+                parsePalettizedBackground(parser, mComposedIconInfo);
             } else {
                 icon = parser.getAttributeValue(0);
                 iconPackResources.put(new ComponentName(tag, ""),
@@ -200,6 +221,62 @@ public class IconPackHelper {
         return false;
     }
 
+    private void parsePalettizedBackground(XmlPullParser parser, ComposedIconInfo iconInfo) {
+        int attrCount = parser.getAttributeCount();
+        ArrayList<Integer> convertedColors = new ArrayList<Integer>();
+        for (int i = 0; i < attrCount; i++) {
+            String name = parser.getAttributeName(i);
+            String value = parser.getAttributeValue(i);
+            if (TextUtils.isEmpty(name)) {
+                Log.w(TAG, "Attribute name cannot be empty or null");
+                continue;
+            }
+            if (TextUtils.isEmpty(value)) {
+                Log.w(TAG, "Attribute value cannot be empty or null");
+                continue;
+            }
+            if (IMG_ATTR.equalsIgnoreCase(name)) {
+                iconInfo.iconPaletteBack = getResourceIdForDrawable(value);
+                if (DEBUG) {
+                    Log.d(TAG, String.format("img=%s, resId=%d", value,
+                            iconInfo.iconPaletteBack));
+                }
+            } else if (SWATCH_TYPE_ATTR.equalsIgnoreCase(name)) {
+                ComposedIconInfo.SwatchType type = ComposedIconInfo.SwatchType.None;
+                if (VIBRANT_VALUE.equalsIgnoreCase(value)) {
+                    type = ComposedIconInfo.SwatchType.Vibrant;
+                } else if (VIBRANT_LIGHT_VALUE.equalsIgnoreCase(value)) {
+                    type = ComposedIconInfo.SwatchType.VibrantLight;
+                } else if (VIBRANT_DARK_VALUE.equalsIgnoreCase(value)) {
+                    type = ComposedIconInfo.SwatchType.VibrantDark;
+                } else if (MUTED_VALUE.equalsIgnoreCase(value)) {
+                    type = ComposedIconInfo.SwatchType.Muted;
+                } else if (MUTED_LIGHT_VALUE.equalsIgnoreCase(value)) {
+                    type = ComposedIconInfo.SwatchType.MutedLight;
+                } else if (MUTED_DARK_VALUE.equalsIgnoreCase(value)) {
+                    type = ComposedIconInfo.SwatchType.MutedDark;
+                }
+                if (type != ComposedIconInfo.SwatchType.None) {
+                    iconInfo.swatchType = type;
+                    if (DEBUG) Log.d(TAG, "PaletteType=" + type);
+                }
+            } else if (name.startsWith(DEFAULT_SWATCH_COLOR_ATTR)) {
+                try {
+                    // ensure alpha is always 0xff
+                    convertedColors.add(Color.parseColor(value) | 0xff000000);
+                } catch (IllegalArgumentException e) {
+                    Log.w(TAG, "Invalid color format", e);
+                }
+            }
+            if (convertedColors.size() > 0) {
+                iconInfo.defaultSwatchColors = new int[convertedColors.size()];
+                for (int j = 0; j < convertedColors.size(); j++) {
+                    iconInfo.defaultSwatchColors[j] = convertedColors.get(j);
+                }
+            }
+        }
+    }
+
     public void loadIconPack(String packageName) throws NameNotFoundException {
         if (packageName == null) {
             mLoadedIconPackResource = null;
@@ -208,12 +285,14 @@ public class IconPackHelper {
             mComposedIconInfo.iconMask = mComposedIconInfo.iconUpon = 0;
             mComposedIconInfo.iconScale = 0;
             mComposedIconInfo.colorFilter = null;
+            mComposedIconInfo.iconPaletteBack = 0;
+            mComposedIconInfo.swatchType = ComposedIconInfo.SwatchType.None;
         } else {
             mIconBackCount = 0;
             Resources res = createIconResource(mContext, packageName);
-            mIconPackResourceMap = getIconResMapFromXml(res, packageName);
             mLoadedIconPackResource = res;
             mLoadedIconPackName = packageName;
+            mIconPackResourceMap = getIconResMapFromXml(res, packageName);
             loadComposedIconComponents();
             ColorMatrix cm = mFilterBuilder.build();
             if (cm != null) {
@@ -454,11 +533,19 @@ public class IconPackHelper {
                 ComposedIconInfo iconInfo) {
             if (iconInfo == null) return icon;
             int back = 0;
-            if (iconInfo.iconBacks != null && iconInfo.iconBacks.length > 0) {
+            int defaultSwatchColor = 0;
+            if (iconInfo.swatchType != ComposedIconInfo.SwatchType.None) {
+                back = iconInfo.iconPaletteBack;
+                if (iconInfo.defaultSwatchColors.length > 0) {
+                    defaultSwatchColor = iconInfo.defaultSwatchColors[
+                            sRandom.nextInt(iconInfo.defaultSwatchColors.length)];
+                }
+            } else if (iconInfo.iconBacks != null && iconInfo.iconBacks.length > 0) {
                 back = iconInfo.iconBacks[sRandom.nextInt(iconInfo.iconBacks.length)];
             }
             Bitmap bmp = createIconBitmap(icon, res, back, iconInfo.iconMask, iconInfo.iconUpon,
-                    iconInfo.iconScale, iconInfo.iconSize, iconInfo.colorFilter);
+                    iconInfo.iconScale, iconInfo.iconSize, iconInfo.colorFilter,
+                    iconInfo.swatchType, defaultSwatchColor);
             return bmp != null ? new BitmapDrawable(res, bmp): null;
         }
 
@@ -470,18 +557,28 @@ public class IconPackHelper {
             outValue.assetCookie = COMPOSED_ICON_COOKIE;
             outValue.data = resId & (COMPOSED_ICON_COOKIE << 24 | 0x00ffffff);
             outValue.string = getCachedIconPath(pkgName, resId, outValue.density);
+            int hashCode = outValue.string.hashCode() & 0x7fffffff;
+            int defaultSwatchColor = 0;
 
             if (!(new File(outValue.string.toString()).exists())) {
                 // compose the icon and cache it
                 final ComposedIconInfo iconInfo = res.getComposedIconInfo();
                 int back = 0;
-                if (iconInfo.iconBacks != null && iconInfo.iconBacks.length > 0) {
-                    back = iconInfo.iconBacks[(outValue.string.hashCode() & 0x7fffffff)
-                            % iconInfo.iconBacks.length];
+                if (iconInfo.swatchType != ComposedIconInfo.SwatchType.None) {
+                    back = iconInfo.iconPaletteBack;
+                    if (iconInfo.defaultSwatchColors.length > 0) {
+                        defaultSwatchColor =iconInfo.defaultSwatchColors[
+                                hashCode % iconInfo.defaultSwatchColors.length];
+                    }
+                } else if (iconInfo.iconBacks != null && iconInfo.iconBacks.length > 0) {
+                    back = iconInfo.iconBacks[hashCode % iconInfo.iconBacks.length];
+                }
+                if (DEBUG) {
+                    Log.d(TAG, "Composing icon for " + pkgName);
                 }
                 Bitmap bmp = createIconBitmap(baseIcon, res, back, iconInfo.iconMask,
                         iconInfo.iconUpon, iconInfo.iconScale, iconInfo.iconSize,
-                        iconInfo.colorFilter);
+                        iconInfo.colorFilter, iconInfo.swatchType, defaultSwatchColor);
                 if (!cacheComposedIcon(bmp, getCachedIconName(pkgName, resId, outValue.density))) {
                     Log.w(TAG, "Unable to cache icon " + outValue.string);
                     // restore the original TypedValue
@@ -491,7 +588,8 @@ public class IconPackHelper {
         }
 
         private static Bitmap createIconBitmap(Drawable icon, Resources res, int iconBack,
-                int iconMask, int iconUpon, float scale, int iconSize, float[] colorFilter) {
+                int iconMask, int iconUpon, float scale, int iconSize, float[] colorFilter,
+                ComposedIconInfo.SwatchType swatchType, int defaultSwatchColor) {
             if (iconSize <= 0) return null;
 
             final Canvas canvas = new Canvas();
@@ -499,6 +597,7 @@ public class IconPackHelper {
                     Paint.FILTER_BITMAP_FLAG));
 
             int width = 0, height = 0;
+            int backTintColor = 0;
             if (icon instanceof PaintDrawable) {
                 PaintDrawable painter = (PaintDrawable) icon;
                 painter.setIntrinsicWidth(iconSize);
@@ -529,6 +628,32 @@ public class IconPackHelper {
                     width = iconSize;
                     height = iconSize;
                 }
+                if (swatchType != ComposedIconInfo.SwatchType.None) {
+                    Palette palette = Palette.generate(bitmap, NUM_PALETTE_COLORS);
+                    switch (swatchType) {
+                        case Vibrant:
+                            backTintColor = palette.getVibrantColor(defaultSwatchColor);
+                            break;
+                        case VibrantLight:
+                            backTintColor = palette.getLightVibrantColor(defaultSwatchColor);
+                            break;
+                        case VibrantDark:
+                            backTintColor = palette.getDarkVibrantColor(defaultSwatchColor);
+                            break;
+                        case Muted:
+                            backTintColor = palette.getMutedColor(defaultSwatchColor);
+                            break;
+                        case MutedLight:
+                            backTintColor = palette.getLightMutedColor(defaultSwatchColor);
+                            break;
+                        case MutedDark:
+                            backTintColor = palette.getDarkMutedColor(defaultSwatchColor);
+                            break;
+                    }
+                    if (DEBUG) {
+                        Log.d(TAG, String.format("palette tint color=0x%08x", backTintColor));
+                    }
+                }
             } else if (icon instanceof VectorDrawable) {
                 width = height = iconSize;
             }
@@ -572,8 +697,13 @@ public class IconPackHelper {
                 Drawable back = res.getDrawable(iconBack);
                 if (back != null) {
                     back.setBounds(icon.getBounds());
-                    ((BitmapDrawable) back).getPaint().setXfermode(
+                    Paint paint = ((BitmapDrawable) back).getPaint();
+                    paint.setXfermode(
                             new PorterDuffXfermode(PorterDuff.Mode.DST_OVER));
+                    if (backTintColor != 0) {
+                        paint.setColorFilter(new PorterDuffColorFilter(backTintColor,
+                                PorterDuff.Mode.MULTIPLY));
+                    }
                     back.draw(canvas);
                 }
             }
diff --git a/core/java/com/android/internal/util/cm/palette/ColorCutQuantizer.java b/core/java/com/android/internal/util/cm/palette/ColorCutQuantizer.java
new file mode 100644
index 0000000..ab5aef7
--- /dev/null
+++ b/core/java/com/android/internal/util/cm/palette/ColorCutQuantizer.java
@@ -0,0 +1,449 @@
+/*
+ * Copyright 2014 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.util.cm.palette;
+
+import android.graphics.Bitmap;
+import android.graphics.Color;
+import android.util.SparseIntArray;
+
+import com.android.internal.util.cm.palette.Palette.Swatch;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.List;
+import java.util.PriorityQueue;
+
+/**
+ * An color quantizer based on the Median-cut algorithm, but optimized for picking out distinct
+ * colors rather than representation colors.
+ *
+ * The color space is represented as a 3-dimensional cube with each dimension being an RGB
+ * component. The cube is then repeatedly divided until we have reduced the color space to the
+ * requested number of colors. An average color is then generated from each cube.
+ *
+ * What makes this different to median-cut is that median-cut divided cubes so that all of the cubes
+ * have roughly the same population, where this quantizer divides boxes based on their color volume.
+ * This means that the color space is divided into distinct colors, rather than representative
+ * colors.
+ *
+ * @hide
+ */
+final class ColorCutQuantizer {
+
+    private static final String LOG_TAG = ColorCutQuantizer.class.getSimpleName();
+
+    private final float[] mTempHsl = new float[3];
+
+    private static final float BLACK_MAX_LIGHTNESS = 0.05f;
+    private static final float WHITE_MIN_LIGHTNESS = 0.95f;
+
+    private static final int COMPONENT_RED = -3;
+    private static final int COMPONENT_GREEN = -2;
+    private static final int COMPONENT_BLUE = -1;
+
+    private final int[] mColors;
+    private final SparseIntArray mColorPopulations;
+
+    private final List<Swatch> mQuantizedColors;
+
+    /**
+     * Factory-method to generate a {@link ColorCutQuantizer} from a {@link Bitmap} object.
+     *
+     * @param bitmap Bitmap to extract the pixel data from
+     * @param maxColors The maximum number of colors that should be in the result palette.
+     */
+    static ColorCutQuantizer fromBitmap(Bitmap bitmap, int maxColors) {
+        final int width = bitmap.getWidth();
+        final int height = bitmap.getHeight();
+
+        final int[] pixels = new int[width * height];
+        bitmap.getPixels(pixels, 0, width, 0, 0, width, height);
+
+        return new ColorCutQuantizer(new com.android.internal.util.cm.palette.ColorHistogram(pixels), maxColors);
+    }
+
+    /**
+     * Private constructor.
+     *
+     * @param colorHistogram histogram representing an image's pixel data
+     * @param maxColors The maximum number of colors that should be in the result palette.
+     */
+    private ColorCutQuantizer(com.android.internal.util.cm.palette.ColorHistogram colorHistogram, int maxColors) {
+        final int rawColorCount = colorHistogram.getNumberOfColors();
+        final int[] rawColors = colorHistogram.getColors();
+        final int[] rawColorCounts = colorHistogram.getColorCounts();
+
+        // First, lets pack the populations into a SparseIntArray so that they can be easily
+        // retrieved without knowing a color's index
+        mColorPopulations = new SparseIntArray(rawColorCount);
+        for (int i = 0; i < rawColors.length; i++) {
+            mColorPopulations.append(rawColors[i], rawColorCounts[i]);
+        }
+
+        // Now go through all of the colors and keep those which we do not want to ignore
+        mColors = new int[rawColorCount];
+        int validColorCount = 0;
+        for (int color : rawColors) {
+            if (!shouldIgnoreColor(color)) {
+                mColors[validColorCount++] = color;
+            }
+        }
+
+        if (validColorCount <= maxColors) {
+            // The image has fewer colors than the maximum requested, so just return the colors
+            mQuantizedColors = new ArrayList<Swatch>();
+            for (final int color : mColors) {
+                mQuantizedColors.add(new Swatch(color, mColorPopulations.get(color)));
+            }
+        } else {
+            // We need use quantization to reduce the number of colors
+            mQuantizedColors = quantizePixels(validColorCount - 1, maxColors);
+        }
+    }
+
+    /**
+     * @return the list of quantized colors
+     */
+    List<Swatch> getQuantizedColors() {
+        return mQuantizedColors;
+    }
+
+    private List<Swatch> quantizePixels(int maxColorIndex, int maxColors) {
+        // Create the priority queue which is sorted by volume descending. This means we always
+        // split the largest box in the queue
+        final PriorityQueue<Vbox> pq = new PriorityQueue<Vbox>(maxColors, VBOX_COMPARATOR_VOLUME);
+
+        // To start, offer a box which contains all of the colors
+        pq.offer(new Vbox(0, maxColorIndex));
+
+        // Now go through the boxes, splitting them until we have reached maxColors or there are no
+        // more boxes to split
+        splitBoxes(pq, maxColors);
+
+        // Finally, return the average colors of the color boxes
+        return generateAverageColors(pq);
+    }
+
+    /**
+     * Iterate through the {@link java.util.Queue}, popping
+     * {@link ColorCutQuantizer.Vbox} objects from the queue
+     * and splitting them. Once split, the new box and the remaining box are offered back to the
+     * queue.
+     *
+     * @param queue {@link PriorityQueue} to poll for boxes
+     * @param maxSize Maximum amount of boxes to split
+     */
+    private void splitBoxes(final PriorityQueue<Vbox> queue, final int maxSize) {
+        while (queue.size() < maxSize) {
+            final Vbox vbox = queue.poll();
+
+            if (vbox != null && vbox.canSplit()) {
+                // First split the box, and offer the result
+                queue.offer(vbox.splitBox());
+                // Then offer the box back
+                queue.offer(vbox);
+            } else {
+                // If we get here then there are no more boxes to split, so return
+                return;
+            }
+        }
+    }
+
+    private List<Swatch> generateAverageColors(Collection<Vbox> vboxes) {
+        ArrayList<Swatch> colors = new ArrayList<Swatch>(vboxes.size());
+        for (Vbox vbox : vboxes) {
+            Swatch color = vbox.getAverageColor();
+            if (!shouldIgnoreColor(color)) {
+                // As we're averaging a color box, we can still get colors which we do not want, so
+                // we check again here
+                colors.add(color);
+            }
+        }
+        return colors;
+    }
+
+    /**
+     * Represents a tightly fitting box around a color space.
+     */
+    private class Vbox {
+        // lower and upper index are inclusive
+        private int mLowerIndex;
+        private int mUpperIndex;
+
+        private int mMinRed, mMaxRed;
+        private int mMinGreen, mMaxGreen;
+        private int mMinBlue, mMaxBlue;
+
+        Vbox(int lowerIndex, int upperIndex) {
+            mLowerIndex = lowerIndex;
+            mUpperIndex = upperIndex;
+            fitBox();
+        }
+
+        int getVolume() {
+            return (mMaxRed - mMinRed + 1) * (mMaxGreen - mMinGreen + 1) *
+                    (mMaxBlue - mMinBlue + 1);
+        }
+
+        boolean canSplit() {
+            return getColorCount() > 1;
+        }
+
+        int getColorCount() {
+            return mUpperIndex - mLowerIndex + 1;
+        }
+
+        /**
+         * Recomputes the boundaries of this box to tightly fit the colors within the box.
+         */
+        void fitBox() {
+            // Reset the min and max to opposite values
+            mMinRed = mMinGreen = mMinBlue = 0xFF;
+            mMaxRed = mMaxGreen = mMaxBlue = 0x0;
+
+            for (int i = mLowerIndex; i <= mUpperIndex; i++) {
+                final int color = mColors[i];
+                final int r = Color.red(color);
+                final int g = Color.green(color);
+                final int b = Color.blue(color);
+                if (r > mMaxRed) {
+                    mMaxRed = r;
+                }
+                if (r < mMinRed) {
+                    mMinRed = r;
+                }
+                if (g > mMaxGreen) {
+                    mMaxGreen = g;
+                }
+                if (g < mMinGreen) {
+                    mMinGreen = g;
+                }
+                if (b > mMaxBlue) {
+                    mMaxBlue = b;
+                }
+                if (b < mMinBlue) {
+                    mMinBlue = b;
+                }
+            }
+        }
+
+        /**
+         * Split this color box at the mid-point along it's longest dimension
+         *
+         * @return the new ColorBox
+         */
+        Vbox splitBox() {
+            if (!canSplit()) {
+                throw new IllegalStateException("Can not split a box with only 1 color");
+            }
+
+            // find median along the longest dimension
+            final int splitPoint = findSplitPoint();
+
+            Vbox newBox = new Vbox(splitPoint + 1, mUpperIndex);
+
+            // Now change this box's upperIndex and recompute the color boundaries
+            mUpperIndex = splitPoint;
+            fitBox();
+
+            return newBox;
+        }
+
+        /**
+         * @return the dimension which this box is largest in
+         */
+        int getLongestColorDimension() {
+            final int redLength = mMaxRed - mMinRed;
+            final int greenLength = mMaxGreen - mMinGreen;
+            final int blueLength = mMaxBlue - mMinBlue;
+
+            if (redLength >= greenLength && redLength >= blueLength) {
+                return COMPONENT_RED;
+            } else if (greenLength >= redLength && greenLength >= blueLength) {
+                return COMPONENT_GREEN;
+            } else {
+                return COMPONENT_BLUE;
+            }
+        }
+
+        /**
+         * Finds the point within this box's lowerIndex and upperIndex index of where to split.
+         *
+         * This is calculated by finding the longest color dimension, and then sorting the
+         * sub-array based on that dimension value in each color. The colors are then iterated over
+         * until a color is found with at least the midpoint of the whole box's dimension midpoint.
+         *
+         * @return the index of the colors array to split from
+         */
+        int findSplitPoint() {
+            final int longestDimension = getLongestColorDimension();
+
+            // We need to sort the colors in this box based on the longest color dimension.
+            // As we can't use a Comparator to define the sort logic, we modify each color so that
+            // it's most significant is the desired dimension
+            modifySignificantOctet(longestDimension, mLowerIndex, mUpperIndex);
+
+            // Now sort... Arrays.sort uses a exclusive toIndex so we need to add 1
+            Arrays.sort(mColors, mLowerIndex, mUpperIndex + 1);
+
+            // Now revert all of the colors so that they are packed as RGB again
+            modifySignificantOctet(longestDimension, mLowerIndex, mUpperIndex);
+
+            final int dimensionMidPoint = midPoint(longestDimension);
+
+            for (int i = mLowerIndex; i <= mUpperIndex; i++)  {
+                final int color = mColors[i];
+
+                switch (longestDimension) {
+                    case COMPONENT_RED:
+                        if (Color.red(color) >= dimensionMidPoint) {
+                            return i;
+                        }
+                        break;
+                    case COMPONENT_GREEN:
+                        if (Color.green(color) >= dimensionMidPoint) {
+                            return i;
+                        }
+                        break;
+                    case COMPONENT_BLUE:
+                        if (Color.blue(color) > dimensionMidPoint) {
+                            return i;
+                        }
+                        break;
+                }
+            }
+
+            return mLowerIndex;
+        }
+
+        /**
+         * @return the average color of this box.
+         */
+        Swatch getAverageColor() {
+            int redSum = 0;
+            int greenSum = 0;
+            int blueSum = 0;
+            int totalPopulation = 0;
+
+            for (int i = mLowerIndex; i <= mUpperIndex; i++) {
+                final int color = mColors[i];
+                final int colorPopulation = mColorPopulations.get(color);
+
+                totalPopulation += colorPopulation;
+                redSum += colorPopulation * Color.red(color);
+                greenSum += colorPopulation * Color.green(color);
+                blueSum += colorPopulation * Color.blue(color);
+            }
+
+            final int redAverage = Math.round(redSum / (float) totalPopulation);
+            final int greenAverage = Math.round(greenSum / (float) totalPopulation);
+            final int blueAverage = Math.round(blueSum / (float) totalPopulation);
+
+            return new Swatch(redAverage, greenAverage, blueAverage, totalPopulation);
+        }
+
+        /**
+         * @return the midpoint of this box in the given {@code dimension}
+         */
+        int midPoint(int dimension) {
+            switch (dimension) {
+                case COMPONENT_RED:
+                default:
+                    return (mMinRed + mMaxRed) / 2;
+                case COMPONENT_GREEN:
+                    return (mMinGreen + mMaxGreen) / 2;
+                case COMPONENT_BLUE:
+                    return (mMinBlue + mMaxBlue) / 2;
+            }
+        }
+    }
+
+    /**
+     * Modify the significant octet in a packed color int. Allows sorting based on the value of a
+     * single color component.
+     *
+     * @see Vbox#findSplitPoint()
+     */
+    private void modifySignificantOctet(final int dimension, int lowerIndex, int upperIndex) {
+        switch (dimension) {
+            case COMPONENT_RED:
+                // Already in RGB, no need to do anything
+                break;
+            case COMPONENT_GREEN:
+                // We need to do a RGB to GRB swap, or vice-versa
+                for (int i = lowerIndex; i <= upperIndex; i++) {
+                    final int color = mColors[i];
+                    mColors[i] = Color.rgb((color >> 8) & 0xFF, (color >> 16) & 0xFF, color & 0xFF);
+                }
+                break;
+            case COMPONENT_BLUE:
+                // We need to do a RGB to BGR swap, or vice-versa
+                for (int i = lowerIndex; i <= upperIndex; i++) {
+                    final int color = mColors[i];
+                    mColors[i] = Color.rgb(color & 0xFF, (color >> 8) & 0xFF, (color >> 16) & 0xFF);
+                }
+                break;
+        }
+    }
+
+    private boolean shouldIgnoreColor(int color) {
+        com.android.internal.util.cm.palette.ColorUtils.RGBtoHSL(Color.red(color), Color.green(color), Color.blue(color), mTempHsl);
+        return shouldIgnoreColor(mTempHsl);
+    }
+
+    private static boolean shouldIgnoreColor(Swatch color) {
+        return shouldIgnoreColor(color.getHsl());
+    }
+
+    private static boolean shouldIgnoreColor(float[] hslColor) {
+        return isWhite(hslColor) || isBlack(hslColor) || isNearRedILine(hslColor);
+    }
+
+    /**
+     * @return true if the color represents a color which is close to black.
+     */
+    private static boolean isBlack(float[] hslColor) {
+        return hslColor[2] <= BLACK_MAX_LIGHTNESS;
+    }
+
+    /**
+     * @return true if the color represents a color which is close to white.
+     */
+    private static boolean isWhite(float[] hslColor) {
+        return hslColor[2] >= WHITE_MIN_LIGHTNESS;
+    }
+
+    /**
+     * @return true if the color lies close to the red side of the I line.
+     */
+    private static boolean isNearRedILine(float[] hslColor) {
+        return hslColor[0] >= 10f && hslColor[0] <= 37f && hslColor[1] <= 0.82f;
+    }
+
+    /**
+     * Comparator which sorts {@link Vbox} instances based on their volume, in descending order
+     */
+    private static final Comparator<Vbox> VBOX_COMPARATOR_VOLUME = new Comparator<Vbox>() {
+        @Override
+        public int compare(Vbox lhs, Vbox rhs) {
+            return rhs.getVolume() - lhs.getVolume();
+        }
+    };
+
+}
diff --git a/core/java/com/android/internal/util/cm/palette/ColorHistogram.java b/core/java/com/android/internal/util/cm/palette/ColorHistogram.java
new file mode 100644
index 0000000..741982d
--- /dev/null
+++ b/core/java/com/android/internal/util/cm/palette/ColorHistogram.java
@@ -0,0 +1,127 @@
+/*
+ * Copyright 2014 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.util.cm.palette;
+
+import java.util.Arrays;
+
+/**
+ * Class which provides a histogram for RGB values.
+ *
+ * @hide
+ */
+final class ColorHistogram {
+
+    private final int[] mColors;
+    private final int[] mColorCounts;
+    private final int mNumberColors;
+
+    /**
+     * A new {@link ColorHistogram} instance.
+     *
+     * @param pixels array of image contents
+     */
+    ColorHistogram(final int[] pixels) {
+        // Sort the pixels to enable counting below
+        Arrays.sort(pixels);
+
+        // Count number of distinct colors
+        mNumberColors = countDistinctColors(pixels);
+
+        // Create arrays
+        mColors = new int[mNumberColors];
+        mColorCounts = new int[mNumberColors];
+
+        // Finally count the frequency of each color
+        countFrequencies(pixels);
+    }
+
+    /**
+     * @return number of distinct colors in the image.
+     */
+    int getNumberOfColors() {
+        return mNumberColors;
+    }
+
+    /**
+     * @return an array containing all of the distinct colors in the image.
+     */
+    int[] getColors() {
+        return mColors;
+    }
+
+    /**
+     * @return an array containing the frequency of a distinct colors within the image.
+     */
+    int[] getColorCounts() {
+        return mColorCounts;
+    }
+
+    private static int countDistinctColors(final int[] pixels) {
+        if (pixels.length < 2) {
+            // If we have less than 2 pixels we can stop here
+            return pixels.length;
+        }
+
+        // If we have at least 2 pixels, we have a minimum of 1 color...
+        int colorCount = 1;
+        int currentColor = pixels[0];
+
+        // Now iterate from the second pixel to the end, counting distinct colors
+        for (int i = 1; i < pixels.length; i++) {
+            // If we encounter a new color, increase the population
+            if (pixels[i] != currentColor) {
+                currentColor = pixels[i];
+                colorCount++;
+            }
+        }
+
+        return colorCount;
+    }
+
+    private void countFrequencies(final int[] pixels) {
+        if (pixels.length == 0) {
+            return;
+        }
+
+        int currentColorIndex = 0;
+        int currentColor = pixels[0];
+
+        mColors[currentColorIndex] = currentColor;
+        mColorCounts[currentColorIndex] = 1;
+
+        if (pixels.length == 1) {
+            // If we only have one pixel, we can stop here
+            return;
+        }
+
+        // Now iterate from the second pixel to the end, population distinct colors
+        for (int i = 1; i < pixels.length; i++) {
+            if (pixels[i] == currentColor) {
+                // We've hit the same color as before, increase population
+                mColorCounts[currentColorIndex]++;
+            } else {
+                // We've hit a new color, increase index
+                currentColor = pixels[i];
+
+                currentColorIndex++;
+                mColors[currentColorIndex] = currentColor;
+                mColorCounts[currentColorIndex] = 1;
+            }
+        }
+    }
+
+}
diff --git a/core/java/com/android/internal/util/cm/palette/ColorUtils.java b/core/java/com/android/internal/util/cm/palette/ColorUtils.java
new file mode 100644
index 0000000..c081cf6
--- /dev/null
+++ b/core/java/com/android/internal/util/cm/palette/ColorUtils.java
@@ -0,0 +1,232 @@
+/*
+ * Copyright 2014 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.util.cm.palette;
+
+import android.graphics.Color;
+
+/** @hide */
+final class ColorUtils {
+
+    private static final int MIN_ALPHA_SEARCH_MAX_ITERATIONS = 10;
+    private static final int MIN_ALPHA_SEARCH_PRECISION = 10;
+
+    private ColorUtils() {}
+
+    /**
+     * Composite two potentially translucent colors over each other and returns the result.
+     */
+    private static int compositeColors(int fg, int bg) {
+        final float alpha1 = Color.alpha(fg) / 255f;
+        final float alpha2 = Color.alpha(bg) / 255f;
+
+        float a = (alpha1 + alpha2) * (1f - alpha1);
+        float r = (Color.red(fg) * alpha1) + (Color.red(bg) * alpha2 * (1f - alpha1));
+        float g = (Color.green(fg) * alpha1) + (Color.green(bg) * alpha2 * (1f - alpha1));
+        float b = (Color.blue(fg) * alpha1) + (Color.blue(bg) * alpha2 * (1f - alpha1));
+
+        return Color.argb((int) a, (int) r, (int) g, (int) b);
+    }
+
+    /**
+     * Returns the luminance of a color.
+     *
+     * Formula defined here: http://www.w3.org/TR/2008/REC-WCAG20-20081211/#relativeluminancedef
+     */
+    private static double calculateLuminance(int color) {
+        double red = Color.red(color) / 255d;
+        red = red < 0.03928 ? red / 12.92 : Math.pow((red + 0.055) / 1.055, 2.4);
+
+        double green = Color.green(color) / 255d;
+        green = green < 0.03928 ? green / 12.92 : Math.pow((green + 0.055) / 1.055, 2.4);
+
+        double blue = Color.blue(color) / 255d;
+        blue = blue < 0.03928 ? blue / 12.92 : Math.pow((blue + 0.055) / 1.055, 2.4);
+
+        return (0.2126 * red) + (0.7152 * green) + (0.0722 * blue);
+    }
+
+    /**
+     * Returns the contrast ratio between two colors.
+     *
+     * Formula defined here: http://www.w3.org/TR/2008/REC-WCAG20-20081211/#contrast-ratiodef
+     */
+    private static double calculateContrast(int foreground, int background) {
+        if (Color.alpha(background) != 255) {
+            throw new IllegalArgumentException("background can not be translucent");
+        }
+        if (Color.alpha(foreground) < 255) {
+            // If the foreground is translucent, composite the foreground over the background
+            foreground = compositeColors(foreground, background);
+        }
+
+        final double luminance1 = calculateLuminance(foreground) + 0.05;
+        final double luminance2 = calculateLuminance(background) + 0.05;
+
+        // Now return the lighter luminance divided by the darker luminance
+        return Math.max(luminance1, luminance2) / Math.min(luminance1, luminance2);
+    }
+
+    /**
+     * Finds the minimum alpha value which can be applied to {@code foreground} so that is has a
+     * contrast value of at least {@code minContrastRatio} when compared to background.
+     *
+     * @return the alpha value in the range 0-255.
+     */
+    private static int findMinimumAlpha(int foreground, int background, double minContrastRatio) {
+        if (Color.alpha(background) != 255) {
+            throw new IllegalArgumentException("background can not be translucent");
+        }
+
+        // First lets check that a fully opaque foreground has sufficient contrast
+        int testForeground = modifyAlpha(foreground, 255);
+        double testRatio = calculateContrast(testForeground, background);
+        if (testRatio < minContrastRatio) {
+            // Fully opaque foreground does not have sufficient contrast, return error
+            return -1;
+        }
+
+        // Binary search to find a value with the minimum value which provides sufficient contrast
+        int numIterations = 0;
+        int minAlpha = 0;
+        int maxAlpha = 255;
+
+        while (numIterations <= MIN_ALPHA_SEARCH_MAX_ITERATIONS &&
+                (maxAlpha - minAlpha) > MIN_ALPHA_SEARCH_PRECISION) {
+            final int testAlpha = (minAlpha + maxAlpha) / 2;
+
+            testForeground = modifyAlpha(foreground, testAlpha);
+            testRatio = calculateContrast(testForeground, background);
+
+            if (testRatio < minContrastRatio) {
+                minAlpha = testAlpha;
+            } else {
+                maxAlpha = testAlpha;
+            }
+
+            numIterations++;
+        }
+
+        // Conservatively return the max of the range of possible alphas, which is known to pass.
+        return maxAlpha;
+    }
+
+    static int getTextColorForBackground(int backgroundColor, int textColor, float minContrastRatio) {
+        final int minAlpha = ColorUtils
+                .findMinimumAlpha(textColor, backgroundColor, minContrastRatio);
+
+        if (minAlpha >= 0) {
+            return ColorUtils.modifyAlpha(textColor, minAlpha);
+        }
+
+        // Didn't find an opacity which provided enough contrast
+        return -1;
+    }
+
+    static void RGBtoHSL(int r, int g, int b, float[] hsl) {
+        final float rf = r / 255f;
+        final float gf = g / 255f;
+        final float bf = b / 255f;
+
+        final float max = Math.max(rf, Math.max(gf, bf));
+        final float min = Math.min(rf, Math.min(gf, bf));
+        final float deltaMaxMin = max - min;
+
+        float h, s;
+        float l = (max + min) / 2f;
+
+        if (max == min) {
+            // Monochromatic
+            h = s = 0f;
+        } else {
+            if (max == rf) {
+                h = ((gf - bf) / deltaMaxMin) % 6f;
+            } else if (max == gf) {
+                h = ((bf - rf) / deltaMaxMin) + 2f;
+            } else {
+                h = ((rf - gf) / deltaMaxMin) + 4f;
+            }
+
+            s =  deltaMaxMin / (1f - Math.abs(2f * l - 1f));
+        }
+
+        hsl[0] = (h * 60f) % 360f;
+        hsl[1] = s;
+        hsl[2] = l;
+    }
+
+    static int HSLtoRGB (float[] hsl) {
+        final float h = hsl[0];
+        final float s = hsl[1];
+        final float l = hsl[2];
+
+        final float c = (1f - Math.abs(2 * l - 1f)) * s;
+        final float m = l - 0.5f * c;
+        final float x = c * (1f - Math.abs((h / 60f % 2f) - 1f));
+
+        final int hueSegment = (int) h / 60;
+
+        int r = 0, g = 0, b = 0;
+
+        switch (hueSegment) {
+            case 0:
+                r = Math.round(255 * (c + m));
+                g = Math.round(255 * (x + m));
+                b = Math.round(255 * m);
+                break;
+            case 1:
+                r = Math.round(255 * (x + m));
+                g = Math.round(255 * (c + m));
+                b = Math.round(255 * m);
+                break;
+            case 2:
+                r = Math.round(255 * m);
+                g = Math.round(255 * (c + m));
+                b = Math.round(255 * (x + m));
+                break;
+            case 3:
+                r = Math.round(255 * m);
+                g = Math.round(255 * (x + m));
+                b = Math.round(255 * (c + m));
+                break;
+            case 4:
+                r = Math.round(255 * (x + m));
+                g = Math.round(255 * m);
+                b = Math.round(255 * (c + m));
+                break;
+            case 5:
+            case 6:
+                r = Math.round(255 * (c + m));
+                g = Math.round(255 * m);
+                b = Math.round(255 * (x + m));
+                break;
+        }
+
+        r = Math.max(0, Math.min(255, r));
+        g = Math.max(0, Math.min(255, g));
+        b = Math.max(0, Math.min(255, b));
+
+        return Color.rgb(r, g, b);
+    }
+
+    /**
+     * Set the alpha component of {@code color} to be {@code alpha}.
+     */
+    static int modifyAlpha(int color, int alpha) {
+        return (color & 0x00ffffff) | (alpha << 24);
+    }
+
+}
diff --git a/core/java/com/android/internal/util/cm/palette/Palette.java b/core/java/com/android/internal/util/cm/palette/Palette.java
new file mode 100644
index 0000000..d0a62f0
--- /dev/null
+++ b/core/java/com/android/internal/util/cm/palette/Palette.java
@@ -0,0 +1,688 @@
+/*
+ * Copyright 2014 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.util.cm.palette;
+
+import android.graphics.Bitmap;
+import android.graphics.Color;
+import android.os.AsyncTask;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * A helper class to extract prominent colors from an image.
+ * <p>
+ * A number of colors with different profiles are extracted from the image:
+ * <ul>
+ *     <li>Vibrant</li>
+ *     <li>Vibrant Dark</li>
+ *     <li>Vibrant Light</li>
+ *     <li>Muted</li>
+ *     <li>Muted Dark</li>
+ *     <li>Muted Light</li>
+ * </ul>
+ * These can be retrieved from the appropriate getter method.
+ *
+ * <p>
+ * Instances can be created with the synchronous factory methods {@link #generate(Bitmap)} and
+ * {@link #generate(Bitmap, int)}.
+ * <p>
+ * These should be called on a background thread, ideally the one in
+ * which you load your images on. Sometimes that is not possible, so asynchronous factory methods
+ * have also been provided: {@link #generateAsync(Bitmap, PaletteAsyncListener)} and
+ * {@link #generateAsync(Bitmap, int, PaletteAsyncListener)}. These can be used as so:
+ *
+ * <pre>
+ * Palette.generateAsync(bitmap, new Palette.PaletteAsyncListener() {
+ *     public void onGenerated(Palette palette) {
+ *         // Do something with colors...
+ *     }
+ * });
+ * </pre>
+ *
+ * @hide
+ */
+public final class Palette {
+
+    /**
+     * Listener to be used with {@link #generateAsync(Bitmap, PaletteAsyncListener)} or
+     * {@link #generateAsync(Bitmap, int, PaletteAsyncListener)}
+     */
+    public interface PaletteAsyncListener {
+
+        /**
+         * Called when the {@link Palette} has been generated.
+         */
+        void onGenerated(Palette palette);
+    }
+
+    private static final int CALCULATE_BITMAP_MIN_DIMENSION = 100;
+    private static final int DEFAULT_CALCULATE_NUMBER_COLORS = 16;
+
+    private static final float TARGET_DARK_LUMA = 0.26f;
+    private static final float MAX_DARK_LUMA = 0.45f;
+
+    private static final float MIN_LIGHT_LUMA = 0.55f;
+    private static final float TARGET_LIGHT_LUMA = 0.74f;
+
+    private static final float MIN_NORMAL_LUMA = 0.3f;
+    private static final float TARGET_NORMAL_LUMA = 0.5f;
+    private static final float MAX_NORMAL_LUMA = 0.7f;
+
+    private static final float TARGET_MUTED_SATURATION = 0.3f;
+    private static final float MAX_MUTED_SATURATION = 0.4f;
+
+    private static final float TARGET_VIBRANT_SATURATION = 1f;
+    private static final float MIN_VIBRANT_SATURATION = 0.35f;
+
+    private static final float WEIGHT_SATURATION = 3f;
+    private static final float WEIGHT_LUMA = 6f;
+    private static final float WEIGHT_POPULATION = 1f;
+
+    private static final float MIN_CONTRAST_TITLE_TEXT = 3.0f;
+    private static final float MIN_CONTRAST_BODY_TEXT = 4.5f;
+
+    private final List<Swatch> mSwatches;
+    private final int mHighestPopulation;
+
+    private Swatch mVibrantSwatch;
+    private Swatch mMutedSwatch;
+
+    private Swatch mDarkVibrantSwatch;
+    private Swatch mDarkMutedSwatch;
+
+    private Swatch mLightVibrantSwatch;
+    private Swatch mLightMutedColor;
+
+    /**
+     * Generate a {@link Palette} from a {@link Bitmap} using the default number of colors.
+     */
+    public static Palette generate(Bitmap bitmap) {
+        return generate(bitmap, DEFAULT_CALCULATE_NUMBER_COLORS);
+    }
+
+    /**
+     * Generate a {@link Palette} from a {@link Bitmap} using the specified {@code numColors}.
+     * Good values for {@code numColors} depend on the source image type.
+     * For landscapes, a good values are in the range 12-16. For images which are largely made up
+     * of people's faces then this value should be increased to 24-32.
+     *
+     * @param numColors The maximum number of colors in the generated palette. Increasing this
+     *                  number will increase the time needed to compute the values.
+     */
+    public static Palette generate(Bitmap bitmap, int numColors) {
+        checkBitmapParam(bitmap);
+        checkNumberColorsParam(numColors);
+
+        // First we'll scale down the bitmap so it's shortest dimension is 100px
+        final Bitmap scaledBitmap = scaleBitmapDown(bitmap);
+
+        // Now generate a quantizer from the Bitmap
+        ColorCutQuantizer quantizer = ColorCutQuantizer.fromBitmap(scaledBitmap, numColors);
+
+        // If created a new bitmap, recycle it
+        if (scaledBitmap != bitmap) {
+            scaledBitmap.recycle();
+        }
+
+        // Now return a ColorExtractor instance
+        return new Palette(quantizer.getQuantizedColors());
+    }
+
+    /**
+     * Generate a {@link Palette} asynchronously. {@link PaletteAsyncListener#onGenerated(Palette)}
+     * will be called with the created instance. The resulting {@link Palette} is the same as
+     * what would be created by calling {@link #generate(Bitmap)}.
+     *
+     * @param listener Listener to be invoked when the {@link Palette} has been generated.
+     *
+     * @return the {@link AsyncTask} used to asynchronously generate the instance.
+     */
+    public static AsyncTask<Bitmap, Void, Palette> generateAsync(
+            Bitmap bitmap, PaletteAsyncListener listener) {
+        return generateAsync(bitmap, DEFAULT_CALCULATE_NUMBER_COLORS, listener);
+    }
+
+    /**
+     * Generate a {@link Palette} asynchronously. {@link PaletteAsyncListener#onGenerated(Palette)}
+     * will be called with the created instance. The resulting {@link Palette} is the same as what
+     * would be created by calling {@link #generate(Bitmap, int)}.
+     *
+     * @param listener Listener to be invoked when the {@link Palette} has been generated.
+     *
+     * @return the {@link AsyncTask} used to asynchronously generate the instance.
+     */
+    public static AsyncTask<Bitmap, Void, Palette> generateAsync(
+            final Bitmap bitmap, final int numColors, final PaletteAsyncListener listener) {
+        checkBitmapParam(bitmap);
+        checkNumberColorsParam(numColors);
+        checkAsyncListenerParam(listener);
+
+        AsyncTask<Bitmap, Void, Palette> task = new AsyncTask<Bitmap, Void, Palette>() {
+            @Override
+            protected Palette doInBackground(Bitmap... params) {
+                return generate(params[0], numColors);
+            }
+
+            @Override
+            protected void onPostExecute(Palette colorExtractor) {
+                listener.onGenerated(colorExtractor);
+            }
+        };
+        task.executeOnExecutor(AsyncTask.THREAD_POOL_EXECUTOR, bitmap);
+
+        return task;
+    }
+
+    /**
+     * Generate a {@link Palette} from the pre-generated list of {@link Palette.Swatch} swatches.
+     * This is useful for testing, or if you want to resurrect a {@link Palette} instance from a
+     * list of swatches. Will return null if the {@code swatches} is null.
+     */
+    public static Palette from(List<Swatch> swatches) {
+        if (swatches == null) {
+            return null;
+        }
+        return new Palette(swatches);
+    }
+
+    private Palette(List<Swatch> swatches) {
+        mSwatches = swatches;
+        mHighestPopulation = findMaxPopulation();
+
+        mVibrantSwatch = findColor(TARGET_NORMAL_LUMA, MIN_NORMAL_LUMA, MAX_NORMAL_LUMA,
+                TARGET_VIBRANT_SATURATION, MIN_VIBRANT_SATURATION, 1f);
+
+        mLightVibrantSwatch = findColor(TARGET_LIGHT_LUMA, MIN_LIGHT_LUMA, 1f,
+                TARGET_VIBRANT_SATURATION, MIN_VIBRANT_SATURATION, 1f);
+
+        mDarkVibrantSwatch = findColor(TARGET_DARK_LUMA, 0f, MAX_DARK_LUMA,
+                TARGET_VIBRANT_SATURATION, MIN_VIBRANT_SATURATION, 1f);
+
+        mMutedSwatch = findColor(TARGET_NORMAL_LUMA, MIN_NORMAL_LUMA, MAX_NORMAL_LUMA,
+                TARGET_MUTED_SATURATION, 0f, MAX_MUTED_SATURATION);
+
+        mLightMutedColor = findColor(TARGET_LIGHT_LUMA, MIN_LIGHT_LUMA, 1f,
+                TARGET_MUTED_SATURATION, 0f, MAX_MUTED_SATURATION);
+
+        mDarkMutedSwatch = findColor(TARGET_DARK_LUMA, 0f, MAX_DARK_LUMA,
+                TARGET_MUTED_SATURATION, 0f, MAX_MUTED_SATURATION);
+
+        // Now try and generate any missing colors
+        generateEmptySwatches();
+    }
+
+    /**
+     * Returns all of the swatches which make up the palette.
+     */
+    public List<Swatch> getSwatches() {
+        return Collections.unmodifiableList(mSwatches);
+    }
+
+    /**
+     * Returns the most vibrant swatch in the palette. Might be null.
+     */
+    public Swatch getVibrantSwatch() {
+        return mVibrantSwatch;
+    }
+
+    /**
+     * Returns a light and vibrant swatch from the palette. Might be null.
+     */
+    public Swatch getLightVibrantSwatch() {
+        return mLightVibrantSwatch;
+    }
+
+    /**
+     * Returns a dark and vibrant swatch from the palette. Might be null.
+     */
+    public Swatch getDarkVibrantSwatch() {
+        return mDarkVibrantSwatch;
+    }
+
+    /**
+     * Returns a muted swatch from the palette. Might be null.
+     */
+    public Swatch getMutedSwatch() {
+        return mMutedSwatch;
+    }
+
+    /**
+     * Returns a muted and light swatch from the palette. Might be null.
+     */
+    public Swatch getLightMutedSwatch() {
+        return mLightMutedColor;
+    }
+
+    /**
+     * Returns a muted and dark swatch from the palette. Might be null.
+     */
+    public Swatch getDarkMutedSwatch() {
+        return mDarkMutedSwatch;
+    }
+
+    /**
+     * Returns the most vibrant color in the palette as an RGB packed int.
+     *
+     * @param defaultColor value to return if the swatch isn't available
+     */
+    public int getVibrantColor(int defaultColor) {
+        return mVibrantSwatch != null ? mVibrantSwatch.getRgb() : defaultColor;
+    }
+
+    /**
+     * Returns a light and vibrant color from the palette as an RGB packed int.
+     *
+     * @param defaultColor value to return if the swatch isn't available
+     */
+    public int getLightVibrantColor(int defaultColor) {
+        return mLightVibrantSwatch != null ? mLightVibrantSwatch.getRgb() : defaultColor;
+    }
+
+    /**
+     * Returns a dark and vibrant color from the palette as an RGB packed int.
+     *
+     * @param defaultColor value to return if the swatch isn't available
+     */
+    public int getDarkVibrantColor(int defaultColor) {
+        return mDarkVibrantSwatch != null ? mDarkVibrantSwatch.getRgb() : defaultColor;
+    }
+
+    /**
+     * Returns a muted color from the palette as an RGB packed int.
+     *
+     * @param defaultColor value to return if the swatch isn't available
+     */
+    public int getMutedColor(int defaultColor) {
+        return mMutedSwatch != null ? mMutedSwatch.getRgb() : defaultColor;
+    }
+
+    /**
+     * Returns a muted and light color from the palette as an RGB packed int.
+     *
+     * @param defaultColor value to return if the swatch isn't available
+     */
+    public int getLightMutedColor(int defaultColor) {
+        return mLightMutedColor != null ? mLightMutedColor.getRgb() : defaultColor;
+    }
+
+    /**
+     * Returns a muted and dark color from the palette as an RGB packed int.
+     *
+     * @param defaultColor value to return if the swatch isn't available
+     */
+    public int getDarkMutedColor(int defaultColor) {
+        return mDarkMutedSwatch != null ? mDarkMutedSwatch.getRgb() : defaultColor;
+    }
+
+    /**
+     * @return true if we have already selected {@code swatch}
+     */
+    private boolean isAlreadySelected(Swatch swatch) {
+        return mVibrantSwatch == swatch || mDarkVibrantSwatch == swatch ||
+                mLightVibrantSwatch == swatch || mMutedSwatch == swatch ||
+                mDarkMutedSwatch == swatch || mLightMutedColor == swatch;
+    }
+
+    private Swatch findColor(float targetLuma, float minLuma, float maxLuma,
+                             float targetSaturation, float minSaturation, float maxSaturation) {
+        Swatch max = null;
+        float maxValue = 0f;
+
+        for (Swatch swatch : mSwatches) {
+            final float sat = swatch.getHsl()[1];
+            final float luma = swatch.getHsl()[2];
+
+            if (sat >= minSaturation && sat <= maxSaturation &&
+                    luma >= minLuma && luma <= maxLuma &&
+                    !isAlreadySelected(swatch)) {
+                float thisValue = createComparisonValue(sat, targetSaturation, luma, targetLuma,
+                        swatch.getPopulation(), mHighestPopulation);
+                if (max == null || thisValue > maxValue) {
+                    max = swatch;
+                    maxValue = thisValue;
+                }
+            }
+        }
+
+        return max;
+    }
+
+    /**
+     * Try and generate any missing swatches from the swatches we did find.
+     */
+    private void generateEmptySwatches() {
+        if (mVibrantSwatch == null) {
+            // If we do not have a vibrant color...
+            if (mDarkVibrantSwatch != null) {
+                // ...but we do have a dark vibrant, generate the value by modifying the luma
+                final float[] newHsl = copyHslValues(mDarkVibrantSwatch);
+                newHsl[2] = TARGET_NORMAL_LUMA;
+                mVibrantSwatch = new Swatch(ColorUtils.HSLtoRGB(newHsl), 0);
+            }
+        }
+
+        if (mDarkVibrantSwatch == null) {
+            // If we do not have a dark vibrant color...
+            if (mVibrantSwatch != null) {
+                // ...but we do have a vibrant, generate the value by modifying the luma
+                final float[] newHsl = copyHslValues(mVibrantSwatch);
+                newHsl[2] = TARGET_DARK_LUMA;
+                mDarkVibrantSwatch = new Swatch(ColorUtils.HSLtoRGB(newHsl), 0);
+            }
+        }
+    }
+
+    /**
+     * Find the {@link Swatch} with the highest population value and return the population.
+     */
+    private int findMaxPopulation() {
+        int population = 0;
+        for (Swatch swatch : mSwatches) {
+            population = Math.max(population, swatch.getPopulation());
+        }
+        return population;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (o == null || getClass() != o.getClass()) {
+            return false;
+        }
+
+        Palette palette = (Palette) o;
+
+        if (mSwatches != null ? !mSwatches.equals(palette.mSwatches) : palette.mSwatches != null) {
+            return false;
+        }
+        if (mDarkMutedSwatch != null ? !mDarkMutedSwatch.equals(palette.mDarkMutedSwatch)
+                : palette.mDarkMutedSwatch != null) {
+            return false;
+        }
+        if (mDarkVibrantSwatch != null ? !mDarkVibrantSwatch.equals(palette.mDarkVibrantSwatch)
+                : palette.mDarkVibrantSwatch != null) {
+            return false;
+        }
+        if (mLightMutedColor != null ? !mLightMutedColor.equals(palette.mLightMutedColor)
+                : palette.mLightMutedColor != null) {
+            return false;
+        }
+        if (mLightVibrantSwatch != null ? !mLightVibrantSwatch.equals(palette.mLightVibrantSwatch)
+                : palette.mLightVibrantSwatch != null) {
+            return false;
+        }
+        if (mMutedSwatch != null ? !mMutedSwatch.equals(palette.mMutedSwatch)
+                : palette.mMutedSwatch != null) {
+            return false;
+        }
+        if (mVibrantSwatch != null ? !mVibrantSwatch.equals(palette.mVibrantSwatch)
+                : palette.mVibrantSwatch != null) {
+            return false;
+        }
+
+        return true;
+    }
+
+    @Override
+    public int hashCode() {
+        int result = mSwatches != null ? mSwatches.hashCode() : 0;
+        result = 31 * result + (mVibrantSwatch != null ? mVibrantSwatch.hashCode() : 0);
+        result = 31 * result + (mMutedSwatch != null ? mMutedSwatch.hashCode() : 0);
+        result = 31 * result + (mDarkVibrantSwatch != null ? mDarkVibrantSwatch.hashCode() : 0);
+        result = 31 * result + (mDarkMutedSwatch != null ? mDarkMutedSwatch.hashCode() : 0);
+        result = 31 * result + (mLightVibrantSwatch != null ? mLightVibrantSwatch.hashCode() : 0);
+        result = 31 * result + (mLightMutedColor != null ? mLightMutedColor.hashCode() : 0);
+        return result;
+    }
+
+    /**
+     * Scale the bitmap down so that it's smallest dimension is
+     * {@value #CALCULATE_BITMAP_MIN_DIMENSION}px. If {@code bitmap} is smaller than this, than it
+     * is returned.
+     */
+    private static Bitmap scaleBitmapDown(Bitmap bitmap) {
+        final int minDimension = Math.min(bitmap.getWidth(), bitmap.getHeight());
+
+        if (minDimension <= CALCULATE_BITMAP_MIN_DIMENSION) {
+            // If the bitmap is small enough already, just return it
+            return bitmap;
+        }
+
+        final float scaleRatio = CALCULATE_BITMAP_MIN_DIMENSION / (float) minDimension;
+        return Bitmap.createScaledBitmap(bitmap,
+                Math.round(bitmap.getWidth() * scaleRatio),
+                Math.round(bitmap.getHeight() * scaleRatio),
+                false);
+    }
+
+    private static float createComparisonValue(float saturation, float targetSaturation,
+            float luma, float targetLuma,
+            int population, int highestPopulation) {
+        return weightedMean(
+                invertDiff(saturation, targetSaturation), WEIGHT_SATURATION,
+                invertDiff(luma, targetLuma), WEIGHT_LUMA,
+                population / (float) highestPopulation, WEIGHT_POPULATION
+        );
+    }
+
+    /**
+     * Copy a {@link Swatch}'s HSL values into a new float[].
+     */
+    private static float[] copyHslValues(Swatch color) {
+        final float[] newHsl = new float[3];
+        System.arraycopy(color.getHsl(), 0, newHsl, 0, 3);
+        return newHsl;
+    }
+
+    /**
+     * Returns a value in the range 0-1. 1 is returned when {@code value} equals the
+     * {@code targetValue} and then decreases as the absolute difference between {@code value} and
+     * {@code targetValue} increases.
+     *
+     * @param value the item's value
+     * @param targetValue the value which we desire
+     */
+    private static float invertDiff(float value, float targetValue) {
+        return 1f - Math.abs(value - targetValue);
+    }
+
+    private static float weightedMean(float... values) {
+        float sum = 0f;
+        float sumWeight = 0f;
+
+        for (int i = 0; i < values.length; i += 2) {
+            float value = values[i];
+            float weight = values[i + 1];
+
+            sum += (value * weight);
+            sumWeight += weight;
+        }
+
+        return sum / sumWeight;
+    }
+
+    private static void checkBitmapParam(Bitmap bitmap) {
+        if (bitmap == null) {
+            throw new IllegalArgumentException("bitmap can not be null");
+        }
+        if (bitmap.isRecycled()) {
+            throw new IllegalArgumentException("bitmap can not be recycled");
+        }
+    }
+
+    private static void checkNumberColorsParam(int numColors) {
+        if (numColors < 1) {
+            throw new IllegalArgumentException("numColors must be 1 of greater");
+        }
+    }
+
+    private static void checkAsyncListenerParam(PaletteAsyncListener listener) {
+        if (listener == null) {
+            throw new IllegalArgumentException("listener can not be null");
+        }
+    }
+
+    /**
+     * Represents a color swatch generated from an image's palette. The RGB color can be retrieved
+     * by calling {@link #getRgb()}.
+     */
+    public static final class Swatch {
+        private final int mRed, mGreen, mBlue;
+        private final int mRgb;
+        private final int mPopulation;
+
+        private boolean mGeneratedTextColors;
+        private int mTitleTextColor;
+        private int mBodyTextColor;
+
+        private float[] mHsl;
+
+        public Swatch(int color, int population) {
+            mRed = Color.red(color);
+            mGreen = Color.green(color);
+            mBlue = Color.blue(color);
+            mRgb = color;
+            mPopulation = population;
+        }
+
+        Swatch(int red, int green, int blue, int population) {
+            mRed = red;
+            mGreen = green;
+            mBlue = blue;
+            mRgb = Color.rgb(red, green, blue);
+            mPopulation = population;
+        }
+
+        /**
+         * @return this swatch's RGB color value
+         */
+        public int getRgb() {
+            return mRgb;
+        }
+
+        /**
+         * Return this swatch's HSL values.
+         *     hsv[0] is Hue [0 .. 360)
+         *     hsv[1] is Saturation [0...1]
+         *     hsv[2] is Lightness [0...1]
+         */
+        public float[] getHsl() {
+            if (mHsl == null) {
+                // Lazily generate HSL values from RGB
+                mHsl = new float[3];
+                ColorUtils.RGBtoHSL(mRed, mGreen, mBlue, mHsl);
+            }
+            return mHsl;
+        }
+
+        /**
+         * @return the number of pixels represented by this swatch
+         */
+        public int getPopulation() {
+            return mPopulation;
+        }
+
+        /**
+         * Returns an appropriate color to use for any 'title' text which is displayed over this
+         * {@link Swatch}'s color. This color is guaranteed to have sufficient contrast.
+         */
+        public int getTitleTextColor() {
+            ensureTextColorsGenerated();
+            return mTitleTextColor;
+        }
+
+        /**
+         * Returns an appropriate color to use for any 'body' text which is displayed over this
+         * {@link Swatch}'s color. This color is guaranteed to have sufficient contrast.
+         */
+        public int getBodyTextColor() {
+            ensureTextColorsGenerated();
+            return mBodyTextColor;
+        }
+
+        private void ensureTextColorsGenerated() {
+            if (!mGeneratedTextColors) {
+                // First check white, as most colors will be dark
+                final int lightBody = ColorUtils.getTextColorForBackground(
+                        mRgb, Color.WHITE,  MIN_CONTRAST_BODY_TEXT);
+                final int lightTitle = ColorUtils.getTextColorForBackground(
+                        mRgb, Color.WHITE, MIN_CONTRAST_TITLE_TEXT);
+
+                if (lightBody != -1 && lightTitle != -1) {
+                    // If we found valid light values, use them and return
+                    mBodyTextColor = lightBody;
+                    mTitleTextColor = lightTitle;
+                    mGeneratedTextColors = true;
+                    return;
+                }
+
+                final int darkBody = ColorUtils.getTextColorForBackground(
+                        mRgb, Color.BLACK, MIN_CONTRAST_BODY_TEXT);
+                final int darkTitle = ColorUtils.getTextColorForBackground(
+                        mRgb, Color.BLACK, MIN_CONTRAST_TITLE_TEXT);
+
+                if (darkBody != -1 && darkBody != -1) {
+                    // If we found valid dark values, use them and return
+                    mBodyTextColor = darkBody;
+                    mTitleTextColor = darkTitle;
+                    mGeneratedTextColors = true;
+                    return;
+                }
+
+                // If we reach here then we can not find title and body values which use the same
+                // lightness, we need to use mismatched values
+                mBodyTextColor = lightBody != -1 ? lightBody : darkBody;
+                mTitleTextColor = lightTitle != -1 ? lightTitle : darkTitle;
+                mGeneratedTextColors = true;
+            }
+        }
+
+        @Override
+        public String toString() {
+            return new StringBuilder(getClass().getSimpleName())
+                    .append(" [RGB: #").append(Integer.toHexString(getRgb())).append(']')
+                    .append(" [HSL: ").append(Arrays.toString(getHsl())).append(']')
+                    .append(" [Population: ").append(mPopulation).append(']')
+                    .append(" [Title Text: #").append(Integer.toHexString(mTitleTextColor)).append(']')
+                    .append(" [Body Text: #").append(Integer.toHexString(mBodyTextColor)).append(']')
+                    .toString();
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (this == o) {
+                return true;
+            }
+            if (o == null || getClass() != o.getClass()) {
+                return false;
+            }
+
+            Swatch swatch = (Swatch) o;
+            return mPopulation == swatch.mPopulation && mRgb == swatch.mRgb;
+        }
+
+        @Override
+        public int hashCode() {
+            return 31 * mRgb + mPopulation;
+        }
+    }
+
+}