001 /* 002 * ArbitraryPaletteQuantizer 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 021 /** 022 * A color quantizer that maps an {@link net.sourceforge.jiu.data.RGBImage} 023 * to any given palette. 024 * This operation is restricted to RGB24Image and palettes with up to 256 colors. 025 * It picks the color from the palette which is closest to the 026 * color to be quantized (with the minimum distance). 027 * This is a rather naive implementation which, for any given color 028 * to be quantized, computes the distance between it and each color 029 * in the palette (read: this operation is rather slow with a large palette and input image). 030 * <p> 031 * It uses <a target="_top" href="http://hissa.nist.gov/dads/HTML/manhttndstnc.html">Manhattan distance</a> (L<sub>1</sub>) 032 * instead of <a target="_top" href="http://hissa.nist.gov/dads/HTML/euclidndstnc.html">Euclidean distance</a> (L<sub>2</sub>). 033 * This saves a square root operation per distance computation. 034 * <p> 035 * There are more sophisticated <a target="_top" 036 * href="http://www.cs.sunysb.edu/~algorith/files/nearest-neighbor.shtml">nearest 037 * neighbor</a> algorithms available, left for future extensions. 038 * 039 * <h3>Usage example</h3> 040 * <p>This example maps an RGB truecolor image to some palette 041 * we create.</p> 042 * <pre> 043 * RGB24Image image = ...; // initialize this 044 * // create some Palette object that you want to map the image to 045 * Palette palette = new Palette(3); // create palette with three entries 046 * palette.put(0, 33, 00, 244); // set first color 047 * palette.put(1, 0, 240, 193); // set second color 048 * palette.put(2, 245, 126, 136); // set third color 049 * ArbitraryPaletteQuantizer quantizer = new ArbitraryPaletteQuantizer(palette); 050 * quantizer.setInputImage(image); 051 * quantizer.process(); 052 * PixelImage quantizedImage = quantizer.getOutputImage(); 053 * </pre> 054 * 055 * @author Marco Schmidt 056 * @since 0.5.0 057 */ 058 public class ArbitraryPaletteQuantizer extends ImageToImageOperation implements RGBIndex, RGBQuantizer 059 { 060 private final int[] RED; 061 private final int[] GREEN; 062 private final int[] BLUE; 063 private Palette palette; 064 private int numEntries; 065 066 /** 067 * Creates a quantizer that will be able to map pixels (or a complete image) 068 * to the argument palette. 069 */ 070 public ArbitraryPaletteQuantizer(Palette palette) 071 { 072 this.palette = palette; 073 numEntries = palette.getNumEntries(); 074 // create 1D lookup tables for the three components and fill them with 075 // the palette entry data 076 RED = new int[numEntries]; 077 GREEN = new int[numEntries]; 078 BLUE = new int[numEntries]; 079 for (int i = 0; i < numEntries; i++) 080 { 081 RED[i] = palette.getSample(INDEX_RED, i); 082 GREEN[i] = palette.getSample(INDEX_GREEN, i); 083 BLUE[i] = palette.getSample(INDEX_BLUE, i); 084 } 085 } 086 087 /** 088 * Returns a copy of the palette that was given to the 089 * constructor of this class. 090 * @return new copy of the palette this quantizer works on 091 */ 092 public Palette createPalette() 093 { 094 return (Palette)palette.clone(); 095 } 096 097 public int map(int[] origRgb, int[] quantizedRgb) 098 { 099 int r = origRgb[INDEX_RED]; 100 int g = origRgb[INDEX_GREEN]; 101 int b = origRgb[INDEX_BLUE]; 102 int minIndex = 0; 103 int minDistance = Integer.MAX_VALUE; 104 for (int index = 0; index < numEntries; index++) 105 { 106 int v = r - RED[index]; 107 int distance = v * v; 108 v = g - GREEN[index]; 109 distance += v * v; 110 v = b - BLUE[index]; 111 distance += v * v; 112 if (distance < minDistance) 113 { 114 minDistance = distance; 115 minIndex = index; 116 } 117 } 118 quantizedRgb[INDEX_RED] = RED[minIndex]; 119 quantizedRgb[INDEX_GREEN] = GREEN[minIndex]; 120 quantizedRgb[INDEX_BLUE] = BLUE[minIndex]; 121 return minIndex; 122 } 123 124 /** 125 * Finds the best match for the argument color in the palette and returns 126 * its index. 127 * Similar to {@link #map(int[], int[])}, the quantized color is not required 128 * and thus a few assignemnts are saved by this method. 129 * @param red red sample of the pixel to be quantized 130 * @param green green sample of the pixel to be quantized 131 * @param blue blue sample of the pixel to be quantized 132 * @return index of the color in the palette that is closest to the argument color 133 */ 134 public int map(int red, int green, int blue) 135 { 136 int minIndex = 0; 137 int minDistance = Integer.MAX_VALUE; 138 for (int index = 0; index < numEntries; index++) 139 { 140 int v = red - RED[index]; 141 int distance = v * v; 142 v = green - GREEN[index]; 143 distance += v * v; 144 v = blue - BLUE[index]; 145 distance += v * v; 146 if (distance < minDistance) 147 { 148 minDistance = distance; 149 minIndex = index; 150 } 151 } 152 return minIndex; 153 } 154 155 private void process(RGB24Image in, Paletted8Image out) 156 { 157 final int WIDTH = in.getWidth(); 158 final int HEIGHT = in.getHeight(); 159 if (out == null) 160 { 161 out = new MemoryPaletted8Image(WIDTH, HEIGHT, createPalette()); 162 } 163 for (int y = 0; y < HEIGHT; y++) 164 { 165 for (int x = 0; x < WIDTH; x++) 166 { 167 out.putSample(0, x, y, map(in.getSample(INDEX_RED, x, y), in.getSample(INDEX_GREEN, x, y), in.getSample(INDEX_BLUE, x, y))); 168 } 169 setProgress(y, HEIGHT); 170 } 171 setOutputImage(out); 172 } 173 174 /** 175 * Maps the input image to an output image, using the palette given to the constructor. 176 */ 177 public void process() throws 178 MissingParameterException, 179 WrongParameterException 180 { 181 ensureInputImageIsAvailable(); 182 PixelImage in = getInputImage(); 183 if (!(in instanceof RGB24Image)) 184 { 185 throw new WrongParameterException("Input image must be of type RGB24Image."); 186 } 187 PixelImage out = getOutputImage(); 188 if (out != null && !(out instanceof Paletted8Image)) 189 { 190 throw new WrongParameterException("Output image must be of type Paletted8Image."); 191 } 192 process((RGB24Image)in, (Paletted8Image)out); 193 } 194 }