001package imagingbook.pub.color.quantize;
002
003import java.awt.image.IndexColorModel;
004
005import ij.process.ByteProcessor;
006import ij.process.ColorProcessor;
007
008public abstract class ColorQuantizer {
009        
010        protected final static int MAX_RGB = 255;
011        
012        /**
013         * Retrieves the color map produced by this color quantizer.
014         * The returned array is in the format int[idx][rgb], where
015         * rgb = 0 (red), 1 (green), 2 (blue) and  0 ≤ idx < nColors.
016         * This method must be implemented by any derived concrete class.
017         * 
018         * @return The table of quantization colors.
019         */
020        public abstract int[][] getColorMap();
021        
022        // ---------------------------------------------------------------
023        
024        /**
025         * Performs color quantization on the given full-color RGB image
026         * and creates an indexed color image.
027         * 
028         * @param cp The original full-color RGB image.
029         * @return The quantized (indexed color) image.
030         */
031        public ByteProcessor quantize(ColorProcessor cp) {
032                int[][] colormap = this.getColorMap();
033                if (colormap.length > 256) 
034                        throw new Error("cannot index to more than 256 colors");
035                int w = cp.getWidth();
036                int h = cp.getHeight();
037                int[]  rgbPixels = (int[]) cp.getPixels();
038                byte[] idxPixels = new byte[rgbPixels.length];
039
040                for (int i = 0; i < rgbPixels.length; i++) {
041                        idxPixels[i] = (byte) this.findColorIndex(rgbPixels[i]);
042                }
043
044                IndexColorModel idxCm = makeIndexColorModel(colormap);
045                return new ByteProcessor(w, h, idxPixels, idxCm);
046        }
047        
048        private IndexColorModel makeIndexColorModel(int[][] colormap) {
049                final int nColors = colormap.length;
050                byte[] rMap = new byte[nColors];
051                byte[] gMap = new byte[nColors];
052                byte[] bMap = new byte[nColors];
053                for (int i = 0; i < nColors; i++) {
054                        rMap[i] = (byte) colormap[i][0];
055                        gMap[i] = (byte) colormap[i][1];
056                        bMap[i] = (byte) colormap[i][2];
057                }
058                return new IndexColorModel(8, nColors, rMap, gMap, bMap);
059        }
060        
061        /**
062         * Performs color quantization on the given sequence of
063         * ARGB-encoded color values and returns a new sequence 
064         * of quantized colors.
065         * 
066         * @param origPixels The original ARGB-encoded color values.
067         * @return The quantized ARGB-encoded color values.
068         */
069        public int[] quantize(int[] origPixels) {
070                int[] qantPixels = new int[origPixels.length];
071                for (int i = 0; i < origPixels.length; i++) {
072                        qantPixels[i] = quantize(origPixels[i]);
073                }
074                return qantPixels;
075        }
076        
077        /**
078         * Performs color quantization on the given ARGB-encoded color 
079         * value and returns the associated quantized color. 
080         * @param p The original ARGB-encoded color value.
081         * @return The quantized ARGB-encoded color value.
082         */
083        public int quantize(int p) {
084                int[][] colormap = getColorMap();
085                int idx = findColorIndex(p);
086                int red = colormap[idx][0];
087                int grn = colormap[idx][1];
088                int blu = colormap[idx][2];
089                return rgbToInt(red, grn, blu);
090        }
091        
092        /**
093         * Finds the color table index of the color that is "closest" to the supplied
094         * RGB color (minimum Euclidean distance in color space). 
095         * This method may be overridden by inheriting classes, for example, to use
096         * quick indexing in the octree method.
097         *  
098         * @param p Original color, encoded as an ARGB integer.
099         * @return The associated color table index.
100         */
101        protected int findColorIndex(int p) {
102                int[][] colormap = getColorMap();
103                int[] rgb = intToRgb(p);
104                int n = colormap.length;
105                int minD2 = Integer.MAX_VALUE;
106                int minIdx = -1;
107                for (int i = 0; i < n; i++) {
108                        final int red = colormap[i][0];
109                        final int grn = colormap[i][1];
110                        final int blu = colormap[i][2];
111                        int d2 = sqr(red - rgb[0]) + sqr(grn - rgb[1]) + sqr(blu - rgb[2]);     // dist^2
112                        if (d2 < minD2) {
113                                minD2 = d2;
114                                minIdx = i;
115                        }
116                }
117                return minIdx;
118        }
119        
120        public void listColorMap() {
121                int[][] colormap = getColorMap();
122                int n = colormap.length;
123                for (int i = 0; i < n; i++) {
124                        int red = 0xff & colormap[i][0];
125                        int grn = 0xff & colormap[i][1];
126                        int blu = 0xff & colormap[i][2];
127                        System.out.println(String.format("i=%3d: r=%3d g=%3d b=%3d", i, red, grn, blu));
128                }
129        }
130        
131        // -----------------------------------------------------------------------------
132        
133        protected int log2(int n){
134                if(n <= 0) throw new IllegalArgumentException();
135                return 31 - Integer.numberOfLeadingZeros(n);
136        }
137        
138        protected int sqr(int k) {
139                return k * k;
140        }
141        
142        protected int[] intToRgb(int rgb) {
143                int red   = ((rgb >> 16) & 0xFF);
144                int grn = ((rgb >> 8) & 0xFF);
145                int blu  = (rgb & 0xFF);
146                return new int[] {red, grn, blu};
147        }
148
149        protected int rgbToInt(int red, int grn, int blu) {
150                return ((red & 0xff)<<16) | ((grn & 0xff)<<8) | blu & 0xff;
151        }
152
153}