    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.imaging.palette;
    018
    019import java.awt.color.ColorSpace;
    020import java.awt.image.BufferedImage;
    021import java.awt.image.ColorModel;
    022import java.util.ArrayList;
    023import java.util.Arrays;
    024import java.util.Collections;
    025import java.util.HashSet;
    026import java.util.List;
    027import java.util.Set;
    028import java.util.logging.Level;
    029import java.util.logging.Logger;
    030
    031import org.apache.commons.imaging.ImageWriteException;
    032
    033/**
    034 * Factory for creating palettes.
    035 */
    036public class PaletteFactory {
    037
    038    private static final Logger LOGGER = Logger.getLogger(PaletteFactory.class.getName());
    039
    040    public static final int COMPONENTS = 3; // in bits
    041
    042    /**
    043     * Builds an exact complete opaque palette containing all the colors in {@code src},
    044     * using an algorithm that is faster than {@linkplain #makeExactRgbPaletteSimple} for large images
    045     * but uses 2 mebibytes of working memory. Treats all the colors as opaque.
    046     * @param src the image whose palette to build
    047     * @return the palette
    048     */
    049    public Palette makeExactRgbPaletteFancy(final BufferedImage src) {
    050        // map what rgb values have been used
    051
    052        final byte[] rgbmap = new byte[256 * 256 * 32];
    053
    054        final int width = src.getWidth();
    055        final int height = src.getHeight();
    056
    057        for (int y = 0; y < height; y++) {
    058            for (int x = 0; x < width; x++) {
    059                final int argb = src.getRGB(x, y);
    060                final int rggbb = 0x1fffff & argb;
    061                final int highred = 0x7 & (argb >> 21);
    062                final int mask = 1 << highred;
    063                rgbmap[rggbb] |= mask;
    064            }
    065        }
    066
    067        int count = 0;
    068        for (final byte element : rgbmap) {
    069            final int eight = 0xff & element;
    070            count += Integer.bitCount(eight);
    071        }
    072
    073        if (LOGGER.isLoggable(Level.FINEST)) {
    074            LOGGER.finest("Used colors: " + count);
    075        }
    076
    077        final int[] colormap = new int[count];
    078        int mapsize = 0;
    079        for (int i = 0; i < rgbmap.length; i++) {
    080            final int eight = 0xff & rgbmap[i];
    081            int mask = 0x80;
    082            for (int j = 0; j < 8; j++) {
    083                final int bit = eight & mask;
    084                mask >>>= 1;
    085
    086                if (bit > 0) {
    087                    final int rgb = i | ((7 - j) << 21);
    088
    089                    colormap[mapsize++] = rgb;
    090                }
    091            }
    092        }
    093
    094        Arrays.sort(colormap);
    095        return new SimplePalette(colormap);
    096    }
    097
    098    private int pixelToQuantizationTableIndex(int argb, final int precision) {
    099        int result = 0;
    100        final int precisionMask = (1 << precision) - 1;
    101
    102        for (int i = 0; i < COMPONENTS; i++) {
    103            int sample = argb & 0xff;
    104            argb >>= 8;
    105
    106            sample >>= (8 - precision);
    107            result = (result << precision) | (sample & precisionMask);
    108        }
    109
    110        return result;
    111    }
    112
    113    private int getFrequencyTotal(final int[] table, final int[] mins, final int[] maxs,
    114            final int precision) {
    115        int sum = 0;
    116
    117        for (int blue = mins[2]; blue <= maxs[2]; blue++) {
    118            final int b = (blue << (2 * precision));
    119            for (int green = mins[1]; green <= maxs[1]; green++) {
    120                final int g = (green << (1 * precision));
    121                for (int red = mins[0]; red <= maxs[0]; red++) {
    122                    final int index = b | g | red;
    123
    124                    sum += table[index];
    125                }
    126            }
    127        }
    128
    129        return sum;
    130    }
    131
    132    private DivisionCandidate finishDivision(final ColorSpaceSubset subset,
    133            final int component, final int precision, final int sum, final int slice) {
    134        if (LOGGER.isLoggable(Level.FINEST)) {
    135            subset.dump("trying (" + component + "): ");
    136        }
    137
    138        final int total = subset.total;
    139
    140        if ((slice < subset.mins[component])
    141                || (slice >= subset.maxs[component])) {
    142            return null;
    143        }
    144
    145        if ((sum < 1) || (sum >= total)) {
    146            return null;
    147        }
    148
    149        final int remainder = total - sum;
    150        if ((remainder < 1) || (remainder >= total)) {
    151            return null;
    152        }
    153
    154        final int[] sliceMins = new int[subset.mins.length];
    155        System.arraycopy(subset.mins, 0, sliceMins, 0, subset.mins.length);
    156        final int[] sliceMaxs = new int[subset.maxs.length];
    157        System.arraycopy(subset.maxs, 0, sliceMaxs, 0, subset.maxs.length);
    158
    159        sliceMaxs[component] = slice;
    160        sliceMins[component] = slice + 1;
    161
    162        if (LOGGER.isLoggable(Level.FINEST)) {
    163            LOGGER.finest("total: " + total);
    164            LOGGER.finest("first total: " + sum);
    165            LOGGER.finest("second total: " + (total - sum));
    166            // System.out.println("start: " + start);
    167            // System.out.println("end: " + end);
    168            LOGGER.finest("slice: " + slice);
    169
    170        }
    171
    172        final ColorSpaceSubset first = new ColorSpaceSubset(sum, precision, subset.mins, sliceMaxs);
    173        final ColorSpaceSubset second = new ColorSpaceSubset(total - sum, precision, sliceMins, subset.maxs);
    174
    175        return new DivisionCandidate(first, second);
    176
    177    }
    178
    179    private List<DivisionCandidate> divideSubset2(final int[] table,
    180            final ColorSpaceSubset subset, final int component, final int precision) {
    181        if (LOGGER.isLoggable(Level.FINEST)) {
    182            subset.dump("trying (" + component + "): ");
    183        }
    184
    185        final int total = subset.total;
    186
    187        final int[] sliceMins = new int[subset.mins.length];
    188        System.arraycopy(subset.mins, 0, sliceMins, 0, subset.mins.length);
    189        final int[] sliceMaxs = new int[subset.maxs.length];
    190        System.arraycopy(subset.maxs, 0, sliceMaxs, 0, subset.maxs.length);
    191
    192        int sum1 = 0;
    193        int slice1;
    194        int last = 0;
    195
    196        for (slice1 = subset.mins[component]; slice1 != subset.maxs[component] + 1; slice1++) {
    197            sliceMins[component] = slice1;
    198            sliceMaxs[component] = slice1;
    199
    200            last = getFrequencyTotal(table, sliceMins, sliceMaxs, precision);
    201
    202            sum1 += last;
    203
    204            if (sum1 >= (total / 2)) {
    205                break;
    206            }
    207        }
    208
    209        final int sum2 = sum1 - last;
    210        final int slice2 = slice1 - 1;
    211
    212        final DivisionCandidate dc1 = finishDivision(subset, component, precision, sum1, slice1);
    213        final DivisionCandidate dc2 = finishDivision(subset, component, precision, sum2, slice2);
    214
    215        final List<DivisionCandidate> result = new ArrayList<>();
    216
    217        if (dc1 != null) {
    218            result.add(dc1);
    219        }
    220        if (dc2 != null) {
    221            result.add(dc2);
    222        }
    223
    224        return result;
    225    }
    226
    227    private DivisionCandidate divideSubset2(final int[] table,
    228            final ColorSpaceSubset subset, final int precision) {
    229        final List<DivisionCandidate> dcs = new ArrayList<>();
    230
    231        dcs.addAll(divideSubset2(table, subset, 0, precision));
    232        dcs.addAll(divideSubset2(table, subset, 1, precision));
    233        dcs.addAll(divideSubset2(table, subset, 2, precision));
    234
    235        DivisionCandidate bestV = null;
    236        double bestScore = Double.MAX_VALUE;
    237
    238        for (final DivisionCandidate dc : dcs) {
    239            final ColorSpaceSubset first = dc.dst_a;
    240            final ColorSpaceSubset second = dc.dst_b;
    241            final int area1 = first.total;
    242            final int area2 = second.total;
    243
    244            final int diff = Math.abs(area1 - area2);
    245            final double score = ((double) diff) / ((double) Math.max(area1, area2));
    246
    247            if (bestV == null) {
    248                bestV = dc;
    249                bestScore = score;
    250            } else if (score < bestScore) {
    251                bestV = dc;
    252                bestScore = score;
    253            }
    254
    255        }
    256
    257        return bestV;
    258    }
    259
    260    private static class DivisionCandidate {
    261        // private final ColorSpaceSubset src;
    262        private final ColorSpaceSubset dst_a;
    263        private final ColorSpaceSubset dst_b;
    264
    265        DivisionCandidate(final ColorSpaceSubset dst_a, final ColorSpaceSubset dst_b) {
    266            // this.src = src;
    267            this.dst_a = dst_a;
    268            this.dst_b = dst_b;
    269        }
    270    }
    271
    272    private List<ColorSpaceSubset> divide(final List<ColorSpaceSubset> v,
    273            final int desiredCount, final int[] table, final int precision) {
    274        final List<ColorSpaceSubset> ignore = new ArrayList<>();
    275
    276        while (true) {
    277            int maxArea = -1;
    278            ColorSpaceSubset maxSubset = null;
    279
    280            for (final ColorSpaceSubset subset : v) {
    281                if (ignore.contains(subset)) {
    282                    continue;
    283                }
    284                final int area = subset.total;
    285
    286                if (maxSubset == null) {
    287                    maxSubset = subset;
    288                    maxArea = area;
    289                } else if (area > maxArea) {
    290                    maxSubset = subset;
    291                    maxArea = area;
    292                }
    293            }
    294
    295            if (maxSubset == null) {
    296                return v;
    297            }
    298            if (LOGGER.isLoggable(Level.FINEST)) {
    299                LOGGER.finest("\t" + "area: " + maxArea);
    300            }
    301
    302            final DivisionCandidate dc = divideSubset2(table, maxSubset,
    303                    precision);
    304            if (dc != null) {
    305                v.remove(maxSubset);
    306                v.add(dc.dst_a);
    307                v.add(dc.dst_b);
    308            } else {
    309                ignore.add(maxSubset);
    310            }
    311
    312            if (v.size() == desiredCount) {
    313                return v;
    314            }
    315        }
    316    }
    317
    318    /**
    319     * Builds an inexact opaque palette of at most {@code max} colors in {@code src}
    320     * using a variation of the Median Cut algorithm. Accurate to 6 bits per component,
    321     * and works by splitting the color bounding box most heavily populated by colors
    322     * along the component which splits the colors in that box most evenly.
    323     * @param src the image whose palette to build
    324     * @param max the maximum number of colors the palette can contain
    325     * @return the palette of at most {@code max} colors
    326     */
    327    public Palette makeQuantizedRgbPalette(final BufferedImage src, final int max) {
    328        final int precision = 6; // in bits
    329
    330        final int tableScale = precision * COMPONENTS;
    331        final int tableSize = 1 << tableScale;
    332        final int[] table = new int[tableSize];
    333
    334        final int width = src.getWidth();
    335        final int height = src.getHeight();
    336
    337        List<ColorSpaceSubset> subsets = new ArrayList<>();
    338        final ColorSpaceSubset all = new ColorSpaceSubset(width * height, precision);
    339        subsets.add(all);
    340
    341        if (LOGGER.isLoggable(Level.FINEST)) {
    342            final int preTotal = getFrequencyTotal(table, all.mins, all.maxs, precision);
    343            LOGGER.finest("pre total: " + preTotal);
    344        }
    345
    346        // step 1: count frequency of colors
    347        for (int y = 0; y < height; y++) {
    348            for (int x = 0; x < width; x++) {
    349                final int argb = src.getRGB(x, y);
    350
    351                final int index = pixelToQuantizationTableIndex(argb, precision);
    352
    353                table[index]++;
    354            }
    355        }
    356
    357        if (LOGGER.isLoggable(Level.FINEST)) {
    358            final int allTotal = getFrequencyTotal(table, all.mins, all.maxs, precision);
    359            LOGGER.finest("all total: " + allTotal);
    360            LOGGER.finest("width * height: " + (width * height));
    361        }
    362
    363        subsets = divide(subsets, max, table, precision);
    364
    365        if (LOGGER.isLoggable(Level.FINEST)) {
    366            LOGGER.finest("subsets: " + subsets.size());
    367            LOGGER.finest("width*height: " + width * height);
    368        }
    369
    370        for (int i = 0; i < subsets.size(); i++) {
    371            final ColorSpaceSubset subset = subsets.get(i);
    372
    373            subset.setAverageRGB(table);
    374
    375            if (LOGGER.isLoggable(Level.FINEST)) {
    376                subset.dump(i + ": ");
    377            }
    378        }
    379
    380        Collections.sort(subsets, ColorSpaceSubset.RGB_COMPARATOR);
    381
    382        return new QuantizedPalette(subsets, precision);
    383    }
    384
    385    /**
    386     * Builds an inexact possibly translucent palette of at most {@code max} colors in {@code src}
    387     * using the traditional Median Cut algorithm. Color bounding boxes are split along the
    388     * longest axis, with each step splitting the box. All bits in each component are used.
    389     * The Algorithm is slower and seems exact than {@linkplain #makeQuantizedRgbPalette(BufferedImage, int)}.
    390     * @param src the image whose palette to build
    391     * @param transparent whether to consider the alpha values
    392     * @param max the maximum number of colors the palette can contain
    393     * @return the palette of at most {@code max} colors
    394     * @throws ImageWriteException if it fails to process the palette
    395     */
    396    public Palette makeQuantizedRgbaPalette(final BufferedImage src, final boolean transparent, final int max) throws ImageWriteException {
    397        return new MedianCutQuantizer(!transparent).process(src, max,
    398                new LongestAxisMedianCut());
    399    }
    400
    401    /**
    402     * Builds an exact complete opaque palette containing all the colors in {@code src},
    403     * and fails by returning {@code null} if there are more than {@code max} colors necessary to do this.
    404     * @param src the image whose palette to build
    405     * @param max the maximum number of colors the palette can contain
    406     * @return the complete palette of {@code max} or less colors, or {@code null} if more than {@code max} colors are necessary
    407     */
    408    public SimplePalette makeExactRgbPaletteSimple(final BufferedImage src, final int max) {
    409        // This is not efficient for large values of max, say, max > 256;
    410        final Set<Integer> rgbs = new HashSet<>();
    411
    412        final int width = src.getWidth();
    413        final int height = src.getHeight();
    414
    415        for (int y = 0; y < height; y++) {
    416            for (int x = 0; x < width; x++) {
    417                final int argb = src.getRGB(x, y);
    418                final int rgb = 0xffffff & argb;
    419
    420                if (rgbs.add(rgb) && rgbs.size() > max) {
    421                    return null;
    422                }
    423            }
    424        }
    425
    426        final int[] result = new int[rgbs.size()];
    427        int next = 0;
    428        for (final int rgb : rgbs) {
    429            result[next++] = rgb;
    430        }
    431        Arrays.sort(result);
    432
    433        return new SimplePalette(result);
    434    }
    435
    436    public boolean isGrayscale(final BufferedImage src) {
    437        final int width = src.getWidth();
    438        final int height = src.getHeight();
    439
    440        if (ColorSpace.TYPE_GRAY == src.getColorModel().getColorSpace().getType()) {
    441            return true;
    442        }
    443
    444        for (int y = 0; y < height; y++) {
    445            for (int x = 0; x < width; x++) {
    446                final int argb = src.getRGB(x, y);
    447
    448                final int red = 0xff & (argb >> 16);
    449                final int green = 0xff & (argb >> 8);
    450                final int blue = 0xff & (argb >> 0);
    451
    452                if (red != green || red != blue) {
    453                    return false;
    454                }
    455            }
    456        }
    457        return true;
    458    }
    459
    460    public boolean hasTransparency(final BufferedImage src) {
    461        return hasTransparency(src, 255);
    462    }
    463
    464    public boolean hasTransparency(final BufferedImage src, final int threshold) {
    465        final int width = src.getWidth();
    466        final int height = src.getHeight();
    467
    468        if (!src.getColorModel().hasAlpha()) {
    469            return false;
    470        }
    471
    472        for (int y = 0; y < height; y++) {
    473            for (int x = 0; x < width; x++) {
    474                final int argb = src.getRGB(x, y);
    475                final int alpha = 0xff & (argb >> 24);
    476                if (alpha < threshold) {
    477                    return true;
    478                }
    479            }
    480        }
    481        return false;
    482    }
    483
    484    public int countTrasparentColors(final int[] rgbs) {
    485        int first = -1;
    486
    487        for (final int rgb : rgbs) {
    488            final int alpha = 0xff & (rgb >> 24);
    489            if (alpha < 0xff) {
    490                if (first < 0) {
    491                    first = rgb;
    492                } else if (rgb != first) {
    493                    return 2; // more than one transparent color;
    494                }
    495            }
    496        }
    497
    498        if (first < 0) {
    499            return 0;
    500        }
    501        return 1;
    502    }
    503
    504    public int countTransparentColors(final BufferedImage src) {
    505        final ColorModel cm = src.getColorModel();
    506        if (!cm.hasAlpha()) {
    507            return 0;
    508        }
    509
    510        final int width = src.getWidth();
    511        final int height = src.getHeight();
    512
    513        int first = -1;
    514
    515        for (int y = 0; y < height; y++) {
    516            for (int x = 0; x < width; x++) {
    517                final int rgb = src.getRGB(x, y);
    518                final int alpha = 0xff & (rgb >> 24);
    519                if (alpha < 0xff) {
    520                    if (first < 0) {
    521                        first = rgb;
    522                    } else if (rgb != first) {
    523                        return 2; // more than one transparent color;
    524                    }
    525                }
    526            }
    527        }
    528
    529        if (first < 0) {
    530            return 0;
    531        }
    532        return 1;
    533    }
    534
    535}