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.image.BufferedImage; 020import java.util.ArrayList; 021import java.util.HashMap; 022import java.util.List; 023import java.util.Map; 024 025import org.apache.commons.imaging.ImagingException; 026import org.apache.commons.imaging.common.Allocator; 027import org.apache.commons.imaging.internal.Debug; 028 029public class MedianCutQuantizer { 030 private final boolean ignoreAlpha; 031 032 public MedianCutQuantizer(final boolean ignoreAlpha) { 033 this.ignoreAlpha = ignoreAlpha; 034 } 035 036 public Map<Integer, ColorCount> groupColors(final BufferedImage image, final int maxColors) { 037 final int max = Integer.MAX_VALUE; 038 039 for (int i = 0; i < 8; i++) { 040 int mask = 0xff & 0xff << i; 041 mask = mask | mask << 8 | mask << 16 | mask << 24; 042 043 Debug.debug("mask(" + i + "): " + mask + " (" + Integer.toHexString(mask) + ")"); 044 045 final Map<Integer, ColorCount> result = groupColors1(image, max, mask); 046 if (result != null) { 047 return result; 048 } 049 } 050 throw new IllegalArgumentException(); 051 } 052 053 private Map<Integer, ColorCount> groupColors1(final BufferedImage image, final int max, final int mask) { 054 final Map<Integer, ColorCount> colorMap = new HashMap<>(); 055 056 final int width = image.getWidth(); 057 final int height = image.getHeight(); 058 059 final int[] row = Allocator.intArray(width); 060 for (int y = 0; y < height; y++) { 061 image.getRGB(0, y, width, 1, row, 0, width); 062 for (int x = 0; x < width; x++) { 063 int argb = row[x]; 064 065 if (ignoreAlpha) { 066 argb &= 0xffffff; 067 } 068 argb &= mask; 069 070 ColorCount color = colorMap.get(argb); 071 if (color == null) { 072 color = new ColorCount(argb); 073 colorMap.put(argb, color); 074 if (colorMap.size() > max) { 075 return null; 076 } 077 } 078 color.count++; 079 } 080 } 081 082 return colorMap; 083 } 084 085 public Palette process(final BufferedImage image, final int maxColors, final MedianCut medianCut) throws ImagingException { 086 final Map<Integer, ColorCount> colorMap = groupColors(image, maxColors); 087 088 final int discreteColors = colorMap.size(); 089 if (discreteColors <= maxColors) { 090 Debug.debug("lossless palette: " + discreteColors); 091 092 final int[] palette = Allocator.intArray(discreteColors); 093 final List<ColorCount> colorCounts = new ArrayList<>(colorMap.values()); 094 095 for (int i = 0; i < colorCounts.size(); i++) { 096 final ColorCount colorCount = colorCounts.get(i); 097 palette[i] = colorCount.argb; 098 if (ignoreAlpha) { 099 palette[i] |= 0xff000000; 100 } 101 } 102 103 return new SimplePalette(palette); 104 } 105 106 Debug.debug("discrete colors: " + discreteColors); 107 108 final List<ColorGroup> colorGroups = new ArrayList<>(); 109 final ColorGroup root = new ColorGroup(new ArrayList<>(colorMap.values()), ignoreAlpha); 110 colorGroups.add(root); 111 112 while (colorGroups.size() < maxColors) { 113 if (!medianCut.performNextMedianCut(colorGroups, ignoreAlpha)) { 114 break; 115 } 116 } 117 118 final int paletteSize = colorGroups.size(); 119 Debug.debug("palette size: " + paletteSize); 120 121 final int[] palette = Allocator.intArray(paletteSize); 122 123 for (int i = 0; i < colorGroups.size(); i++) { 124 final ColorGroup colorGroup = colorGroups.get(i); 125 126 palette[i] = colorGroup.getMedianValue(); 127 128 colorGroup.paletteIndex = i; 129 130 if (colorGroup.getColorCounts().isEmpty()) { 131 throw new ImagingException("Empty colorGroup: " + colorGroup); 132 } 133 } 134 135 if (paletteSize > discreteColors) { 136 throw new ImagingException("paletteSize > discreteColors"); 137 } 138 139 return new MedianCutPalette(root, palette); 140 } 141}