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