001 /* 002 * OctreeColorQuantizer 003 * 004 * Copyright (c) 2001, 2002, 2003 Marco Schmidt. 005 * All rights reserved. 006 */ 007 008 package net.sourceforge.jiu.color.quantization; 009 010 import net.sourceforge.jiu.color.quantization.RGBQuantizer; 011 import net.sourceforge.jiu.data.MemoryPaletted8Image; 012 import net.sourceforge.jiu.data.Palette; 013 import net.sourceforge.jiu.data.Paletted8Image; 014 import net.sourceforge.jiu.data.PixelImage; 015 import net.sourceforge.jiu.data.RGB24Image; 016 import net.sourceforge.jiu.data.RGBIndex; 017 import net.sourceforge.jiu.ops.ImageToImageOperation; 018 import net.sourceforge.jiu.ops.MissingParameterException; 019 import net.sourceforge.jiu.ops.WrongParameterException; 020 import net.sourceforge.jiu.util.Sort; 021 022 /** 023 * Performs the octree color quantization algorithm for a given RGB truecolor image. 024 * The quality is usually somewhat inferior to the results of {@link MedianCutQuantizer}. 025 * Note that you can improve the quality by applying a dithering algorithm. 026 * See {@link net.sourceforge.jiu.color.dithering.ErrorDiffusionDithering}. 027 * 028 * <h3>Usage example</h3> 029 * This reduces some RGB24Image image to a 16 color paletted image: 030 * <pre> 031 * MemoryRGB24Image image = ...; // initialize 032 * OctreeColorQuantizer ocq = new OctreeColorQuantizer(); 033 * ocq.setInputImage(image); 034 * ocq.setPaletteSize(16); 035 * ocq.process(); 036 * PixelImage quantizedImage = ocq.getOutputImage(); 037 * </pre> 038 * 039 * <h3>Credits</h3> 040 * 041 * @author Marco Schmidt 042 * @since 0.6.0 043 */ 044 public class OctreeColorQuantizer extends ImageToImageOperation implements RGBIndex, RGBQuantizer 045 { 046 /** 047 * The default number of colors in the palette. 048 * Will be used when no other value is specified via {@link #setPaletteSize}. 049 */ 050 public static final int DEFAULT_PALETTE_SIZE = 256; 051 052 private int paletteSize = DEFAULT_PALETTE_SIZE; 053 private OctreeNode root; 054 private Palette palette; 055 private int[] redValues; 056 private int[] greenValues; 057 private int[] blueValues; 058 059 /** 060 * If node is a leaf node, this method assigns palette index values 061 * and determines the representative color, otherwise it simply 062 * recursively calls itself for all child nodes. 063 * The updated index value is returned. 064 * It is increased whenever a leaf is assigned that index value. 065 * 066 * @param node the node of the octree that will itself (and its children) be processed 067 * @param index the current index in the palette index assignment procedure 068 * @return updated index value; may have been increased while node or its child(ren) - 069 * were assigned index values 070 */ 071 private int assignPaletteIndexValues(OctreeNode node, int index) 072 { 073 if (node == null) 074 { 075 return index; 076 } 077 if (node.isLeaf()) 078 { 079 node.setPaletteIndex(index); 080 node.determineRepresentativeColor(); 081 return index + 1; 082 } 083 else 084 { 085 OctreeNode[] children = node.getChildren(); 086 if (children != null) 087 { 088 for (int i = 0; i < 8; i++) 089 { 090 if (children[i] != null) 091 { 092 index = assignPaletteIndexValues(children[i], index); 093 } 094 } 095 } 096 return index; 097 } 098 } 099 100 public Palette createPalette() 101 { 102 if (palette == null) 103 { 104 int numValues = assignPaletteIndexValues(root, 0); 105 palette = new Palette(numValues); 106 initPalette(root, palette); 107 redValues = new int[numValues]; 108 greenValues = new int[numValues]; 109 blueValues = new int[numValues]; 110 for (int i = 0; i < numValues; i++) 111 { 112 redValues[i] = palette.getSample(INDEX_RED, i); 113 greenValues[i] = palette.getSample(INDEX_GREEN, i); 114 blueValues[i] = palette.getSample(INDEX_BLUE, i); 115 } 116 return palette; 117 } 118 else 119 { 120 return (Palette)palette.clone(); 121 } 122 } 123 124 /** 125 * Creates an octree and prepares this quantizer so that colors can be mapped to 126 * palette index values. 127 * If you use {@link #process()} you must not call this method. 128 * On the other hand, if you want to do the mapping yourself - maybe if you 129 * want to do mapping and dithering interchangeably - call this method first, 130 * then do the mapping yourself. 131 * @throws MissingParameterException if parameters like the input image are missing 132 * @throws WrongParameterException if parameters exist but are of the wrong type 133 */ 134 public void init() throws 135 MissingParameterException, 136 WrongParameterException 137 { 138 PixelImage pi = getInputImage(); 139 if (pi == null) 140 { 141 throw new MissingParameterException("Input image needed."); 142 } 143 if (!(pi instanceof RGB24Image)) 144 { 145 throw new WrongParameterException("Input image must be of type RGB24Image."); 146 } 147 int numUniqueColors = initOctree(); 148 //System.out.println("# of unique colors=" + numUniqueColors); 149 pruneOctree(); 150 } 151 152 private int initOctree() 153 { 154 int numUniqueColors = 0; 155 root = new OctreeNode(); 156 RGB24Image in = (RGB24Image)getInputImage(); 157 for (int y = 0; y < in.getHeight(); y++) 158 { 159 for (int x = 0; x < in.getWidth(); x++) 160 { 161 int red = in.getSample(INDEX_RED, x, y); 162 int green = in.getSample(INDEX_GREEN, x, y); 163 int blue = in.getSample(INDEX_BLUE, x, y); 164 if (OctreeNode.add(root, red, green, blue, 8)) 165 { 166 numUniqueColors++; 167 } 168 } 169 } 170 root.copyChildSums(); 171 return numUniqueColors; 172 } 173 174 private void initPalette(OctreeNode node, Palette palette) 175 { 176 if (node == null) 177 { 178 return; 179 } 180 if (node.isLeaf()) 181 { 182 int index = node.getPaletteIndex(); 183 palette.put(index, node.getRed(), node.getGreen(), node.getBlue()); 184 return; 185 } 186 OctreeNode[] children = node.getChildren(); 187 if (children == null) 188 { 189 return; 190 } 191 for (int i = 0; i < children.length; i++) 192 { 193 OctreeNode child = children[i]; 194 if (child != null) 195 { 196 initPalette(child, palette); 197 } 198 } 199 } 200 201 /** 202 * Maps an RGB color <code>origRgb</code> to one of the colors in the 203 * color map; that color will be written to <code>quantizedRgb</code> 204 * and its palette index will be returned. 205 * @param origRgb the color to be mapped to the best-possible counterpart in the 206 * palette; the array is indexed by the constants from {@link RGBIndex} 207 * @param quantizedRgb the resulting color from the palette will be written 208 * to this array; it is also indexed by the constants from {@link RGBIndex} 209 * @return index of the found color in the palette 210 */ 211 public int map(int[] origRgb, int[] quantizedRgb) 212 { 213 int result = root.map(origRgb, quantizedRgb); 214 if (result == -1) 215 { 216 int minIndex = 0; 217 int minDistance = Integer.MAX_VALUE; 218 int i = 0; 219 int red = origRgb[INDEX_RED]; 220 int green = origRgb[INDEX_GREEN]; 221 int blue = origRgb[INDEX_BLUE]; 222 while (i < redValues.length) 223 { 224 int v = (redValues[i] - red); 225 int sum = v * v; 226 v = (greenValues[i] - green); 227 sum += v * v; 228 v = (blueValues[i] - blue); 229 sum += v * v; 230 if (sum < minDistance) 231 { 232 minIndex = i; 233 minDistance = sum; 234 } 235 i++; 236 } 237 quantizedRgb[INDEX_RED] = redValues[minIndex]; 238 quantizedRgb[INDEX_GREEN] = greenValues[minIndex]; 239 quantizedRgb[INDEX_BLUE] = blueValues[minIndex]; 240 return minIndex; 241 } 242 else 243 { 244 // quantizedRgb was filled with values in root.map 245 return result; 246 } 247 } 248 249 private void mapImage() 250 { 251 RGB24Image in = (RGB24Image)getInputImage(); 252 Palette palette = createPalette(); 253 Paletted8Image out = new MemoryPaletted8Image(in.getWidth(), in.getHeight(), palette); 254 int[] origRgb = new int[3]; 255 int[] quantizedRgb = new int[3]; 256 for (int y = 0; y < in.getHeight(); y++) 257 { 258 for (int x = 0; x < in.getWidth(); x++) 259 { 260 origRgb[INDEX_RED] = in.getSample(INDEX_RED, x, y); 261 origRgb[INDEX_GREEN] = in.getSample(INDEX_GREEN, x, y); 262 origRgb[INDEX_BLUE] = in.getSample(INDEX_BLUE, x, y); 263 int index = map(origRgb, quantizedRgb); 264 out.putSample(0, x, y, index); 265 } 266 } 267 setOutputImage(out); 268 } 269 270 /** 271 * Initializes an octree, reduces it have as many leaves (or less) as 272 * the desired palette size and maps the original image to the newly-created 273 * palette. 274 */ 275 public void process() throws 276 MissingParameterException, 277 WrongParameterException 278 { 279 init(); 280 mapImage(); 281 } 282 283 /** 284 * Reduces the octree until it has as many leaves (or less) than specified 285 * by the <code>paletteSize</code> argument in the constructor 286 * {@link #OctreeColorQuantizer(int)}. 287 */ 288 private void pruneOctree() 289 { 290 // create an array for as many palette entries as specified by paletteSize 291 OctreeNode[] a = new OctreeNode[paletteSize]; 292 // initial length is 1, the only element is the root 293 a[0] = root; 294 int length = 1; 295 // create a comparator that will be used to sort the nodes by their pixel count, 296 // in ascending order 297 OctreeNode comparator = new OctreeNode(); 298 // loop and split leaves as long as the number of nodes (length) is smaller 299 // than the desired palette size 300 while (length < paletteSize) 301 { 302 Sort.sort(a, 0, length - 1, comparator); 303 int index = length - 1; 304 while (index >= 0) 305 { 306 OctreeNode node = a[index]; 307 int numChildren = node.getNumChildren(); 308 // check if current length minus the node which may be split 309 // plus the number of its children does not exceed the desired palette size 310 if (numChildren > 0 && length - 1 + numChildren < paletteSize) 311 { 312 // child nodes fit in here 313 if (index < length - 1) 314 { 315 System.arraycopy(a, index + 1, a, index, length - index - 1); 316 } 317 length--; 318 OctreeNode[] children = node.getChildren(); 319 for (int i = 0; i < children.length; i++) 320 { 321 if (children[i] != null) 322 { 323 a[length++] = children[i]; 324 } 325 } 326 break; 327 } 328 else 329 { 330 index--; 331 } 332 } 333 if (index == -1) 334 { 335 // we could not find a node to be split 336 break; 337 } 338 } 339 // in some cases it is not possible to get exactly paletteSize leaves; 340 // adjust paletteSize to be equal to the number of leaves 341 // note that length will never be larger than paletteSize, only smaller 342 // in some cases 343 paletteSize = length; 344 // make all found nodes leaves by setting their child nodes to null 345 for (int i = 0; i < length; i++) 346 { 347 a[i].setChildren(null); 348 } 349 } 350 351 public void setPaletteSize(int newPaletteSize) 352 { 353 if (newPaletteSize < 1) 354 { 355 throw new IllegalArgumentException("Palette size must be 1 or larger."); 356 } 357 if (newPaletteSize > 256) 358 { 359 throw new IllegalArgumentException("Palette size must be 256 or smaller."); 360 } 361 paletteSize = newPaletteSize; 362 } 363 }