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