Java > Open Source Codes > org > apache > batik > ext > awt > image > rendered > IndexImage


1 /*
2
3    Copyright 2002-2003 The Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16
17  */
18 package org.apache.batik.ext.awt.image.rendered;
19
20 import java.awt.Graphics2D ;
21 import java.awt.Point ;
22 import java.awt.RenderingHints ;
23 import java.awt.image.BufferedImage ;
24 import java.awt.image.ColorModel ;
25 import java.awt.image.DataBuffer ;
26 import java.awt.image.IndexColorModel ;
27 import java.awt.image.MultiPixelPackedSampleModel ;
28 import java.awt.image.Raster ;
29 import java.awt.image.SampleModel ;
30 import java.awt.image.WritableRaster ;
31 import java.util.Iterator ;
32 import java.util.Vector ;
33
34 import org.apache.batik.ext.awt.image.GraphicsUtil;
35
36 /**
37  * This implements an adaptive pallete generator to reduce images to a
38  * specified number of colors.
39  *
40  * Ideally this would also support a better dither option than just
41  * the JDK's pattern dither.
42  *
43  * @author <a HREF="mailto:deweese@apache.org">Thomas DeWeese</a>
44  * @author <a HREF="mailto:jun@oop-reserch.com">Jun Inamori</a>
45  * @version $Id: IndexImage.java,v 1.7 2004/08/18 07:14:08 vhardy Exp $ */
46 public class IndexImage{
47
48     /**
49      * Used to track a color and the number of pixels of that colors
50      */
51     private static class Counter {
52         public int val;
53         public int count=1;
54         public Counter(int val) { this.val = val; }
55         public boolean add(int val) {
56             // See if the value matches us...
57 if (this.val != val)
58                 return false;
59             count++;
60             return true;
61         }
62     }
63
64     /**
65      * Used to define a cube of the colorspace. The cube can be split
66      * approximagely in half to generate two cubes.
67      */
68     private static class Cube {
69         int []min={0, 0, 0}, max={255,255,255};
70
71         boolean done = false;
72         
73         Vector []colors = null;
74         int count=0;
75         static final int RED = 0;
76         static final int GRN = 1;
77         static final int BLU = 2;
78
79         /**
80          * Define a new cube.
81          * @param colors contains the 3D color histogram to be subdivided
82          * @param count the total number of pixels in the 3D histogram.
83          */
84         public Cube(Vector []colors, int count) {
85             this.colors = colors;
86             this.count = count;
87         }
88
89         /**
90          * If this returns true then the cube can not be subdivided any
91          * further
92          */
93         public boolean isDone() { return done; }
94         /**
95          * Splits the cube into two parts. This cube is
96          * changed to be one half and the returned cube is the other half.
97          * This tries to pick the right channel to split on.
98          */
99         public Cube split() {
100             int dr = max[0]-min[0]+1;
101             int dg = max[1]-min[1]+1;
102             int db = max[2]-min[2]+1;
103             int c0, c1, splitChannel;
104
105             // Figure out which axis is the longest and split along
106 // that axis (this tries to keep cubes square-ish).
107 if (dr >= dg) {
108                 c0 = GRN;
109                 if (dr >= db) { splitChannel = RED; c1=BLU; }
110                 else { splitChannel = BLU; c1=RED; }
111             } else if (dg >= db) {
112                 splitChannel = GRN;
113                 c0=RED;
114                 c1=BLU;
115             } else {
116                 splitChannel = BLU;
117                 c0=RED;
118                 c1=GRN;
119             }
120
121             Cube ret;
122             ret = splitChannel(splitChannel, c0, c1);
123             if (ret != null ) return ret;
124
125             ret = splitChannel(c0, splitChannel, c1);
126             if (ret != null ) return ret;
127
128             ret = splitChannel(c1, splitChannel, c0);
129             if (ret != null) return ret;
130             
131             done = true;
132             return null;
133         }
134
135         /**
136          * Splits the image according to the parameters. It tries
137          * to find a location where half the pixels are on one side
138          * and half the pixels are on the other.
139          */
140         public Cube splitChannel(int splitChannel, int c0, int c1) {
141             if (min[splitChannel] == max[splitChannel]) return null;
142             
143             int splitSh4 = (2-splitChannel)*4;
144             int c0Sh4 = (2-c0)*4;
145             int c1Sh4 = (2-c1)*4;
146
147             int half = count/2;
148             // Each entry is the number of pixels that have that value
149 // in the split channel within the cube (so pixels
150 // that have that value in the split channel aren't counted
151 // if they are outside the cube in the other color channels.
152 int counts [] = new int[256];
153             int tcount = 0;
154
155             // System.out.println("Cube: [" +
156 // min[0] + "-" + max[0] + "] [" +
157 // min[1] + "-" + max[1] + "] [" +
158 // min[2] + "-" + max[2] + "]");
159
160             int [] minIdx = {min[0]>>4, min[1]>>4, min[2]>>4};
161             int [] maxIdx = {max[0]>>4, max[1]>>4, max[2]>>4};
162             int minR=min[0], minG=min[1], minB=min[2];
163             int maxR=max[0], maxG=max[1], maxB=max[2];
164             int val = 0;
165             int [] vals = {0, 0, 0};
166             for (int i=minIdx[splitChannel]; i<=maxIdx[splitChannel]; i++) {
167                 int idx1 = i<<splitSh4;
168                 for (int j=minIdx[c0]; j<=maxIdx[c0]; j++) {
169                     int idx2 = idx1 | (j<<c0Sh4);
170                     for (int k=minIdx[c1]; k<=maxIdx[c1]; k++) {
171                         int idx = idx2 | (k<<c1Sh4);
172                         Vector v = colors[idx];
173                         if (v==null) continue;
174                         Iterator itr = v.iterator();
175                         Counter c;
176                         while (itr.hasNext()) {
177                             c = (Counter)itr.next();
178                             val = c.val;
179                             vals[0] = (val&0xFF0000)>>16;
180                             vals[1] = (val&0xFF00)>>8;
181                             vals[2] = (val&0xFF);
182                             if (((vals[0] >= minR) && (vals[0] <= maxR))&&
183                                 ((vals[1] >= minG) && (vals[1] <= maxG))&&
184                                 ((vals[2] >= minB) && (vals[2] <= maxB))) {
185                                 // The val lies within this cube so count it.
186 counts[vals[splitChannel]] += c.count;
187                                 tcount += c.count;
188                             }
189                         }
190                     }
191                 }
192                 // We've found the half way point. Note that the
193 // rest of counts is not filled out.
194 if (tcount >= half) break;
195             }
196
197             tcount=0;
198             int lastAdd=-1;
199             // These indicate what the top value for the low cube and
200 // the low value of the high cube should be in the split channel
201 // (they may not be one off if there are 'dead' spots in the
202 // counts array.
203 int splitLo=min[splitChannel], splitHi=max[splitChannel];
204             for (int i=min[splitChannel]; i<=max[splitChannel]; i++) {
205                 int c = counts[i];
206                 if (c == 0) {
207                     // No counts below this so move up bottom of cube.
208 if ((tcount == 0) && (i < max[splitChannel]))
209                         this.min[splitChannel] = i+1;
210                     continue;
211                 }
212
213                 if (tcount+c < half) {
214                     lastAdd = i;
215                     tcount+=c;
216                     continue;
217                 }
218                 if ((half-tcount) <= ((tcount+c)-half)) {
219                     // Then lastAdd is a better top idx for this then i.
220 if (lastAdd == -1) {
221                         // No lower place to break.
222 if (c == this.count) {
223                             // All pixels are at this value so make min/max
224 // reflect that.
225 this.max[splitChannel] = i;
226                             return null; // no split to make.
227 } else {
228                             // There are values about this one so
229 // split above.
230 splitLo = i;
231                             splitHi = i+1;
232                             break;
233                         }
234                     }
235                     splitLo = lastAdd;
236                     splitHi = i;
237                 } else {
238                     if (i == this.max[splitChannel]) {
239                         if ( c == this.count) {
240                             // would move min up but that should
241 // have happened already.
242 return null; // no split to make.
243 } else {
244                             // Would like to break between i and i+1
245 // but no i+1 so use lastAdd and i;
246 splitLo = lastAdd;
247                             splitHi = i;
248                             break;
249                         }
250                     }
251                     // Include c in counts
252 tcount += c;
253                     splitLo = i;
254                     splitHi = i+1;
255                 }
256                 break;
257             }
258
259             // System.out.println("Split: " + splitChannel + "@"
260 // + splitLo + "-"+splitHi +
261 // " Count: " + tcount + " of " + count +
262 // " LA: " + lastAdd);
263
264             // Create the new cube and update everone's bounds & counts.
265 Cube ret = new Cube(colors, tcount);
266             this.count = this.count-tcount;
267             ret.min[splitChannel] = this.min[splitChannel];
268             ret.max[splitChannel] = splitLo;
269             this.min[splitChannel] = splitHi;
270             ret.min[c0] = this.min[c0];
271             ret.max[c0] = this.max[c0];
272             ret.min[c1] = this.min[c1];
273             ret.max[c1] = this.max[c1];
274             return ret;
275         }
276
277         /**
278          * Returns the average color for this cube
279          */
280         public int averageColor() {
281             if (this.count == 0) return 0;
282
283             float red=0, grn=0, blu=0;
284
285             int minR=min[0], minG=min[1], minB=min[2];
286             int maxR=max[0], maxG=max[1], maxB=max[2];
287             int [] minIdx = {minR>>4, minG>>4, minB>>4};
288             int [] maxIdx = {maxR>>4, maxG>>4, maxB>>4};
289             int val, ired, igrn, iblu;
290             float weight;
291             for (int i=minIdx[0]; i<=maxIdx[0]; i++) {
292                 int idx1 = i<<8;
293                 for (int j=minIdx[1]; j<=maxIdx[1]; j++) {
294                     int idx2 = idx1 | (j<<4);
295                     for (int k=minIdx[2]; k<=maxIdx[2]; k++) {
296                         int idx = idx2 | k;
297                         Vector v = colors[idx];
298                         if (v==null) continue;
299                         Iterator itr = v.iterator();
300                         Counter c;
301                         while (itr.hasNext()) {
302                             c = (Counter)itr.next();
303                             val = c.val;
304                             ired = (val&0xFF0000)>>16;
305                             igrn = (val&0x00FF00)>>8;
306                             iblu = (val&0x0000FF);
307                             if (((ired >= minR) && (ired <= maxR))&&
308                                 ((igrn >= minG) && (igrn <= maxG))&&
309                                 ((iblu >= minB) && (iblu <= maxB))) {
310                                 weight = (c.count/(float)this.count);
311                                 red += (ired*weight);
312                                 grn += (igrn*weight);
313                                 blu += (iblu*weight);
314                             }
315                         }
316                     }
317                 }
318             }
319             // System.out.println("RGB: [" + red + ", " +
320 // grn + ", " + blu + "]");
321 return (((int)(red+0.5))<<16 |
322                     ((int)(grn+0.5))<<8 |
323                     ((int)(blu+0.5)));
324         }
325     }
326
327     /**
328      * Converts the input image (must be TYPE_INT_RGB or
329      * TYPE_INT_ARGB) to an indexed image. Generating an adaptive
330      * palette with number of colors specified.
331      * @param bi the image to be processed.
332      * @param nColors number of colors in the palette
333      */
334     static public BufferedImage getIndexedImage
335         (BufferedImage bi, int nColors) {
336         int w=bi.getWidth();
337         int h=bi.getHeight();
338
339         // Using 4 bits from RG & B.
340 Vector [] colors = new Vector [1<<12];
341
342         int rgb=0;
343         for(int i_w=0; i_w<w; i_w++){
344             for(int i_h=0; i_h<h; i_h++){
345                 rgb=(bi.getRGB(i_w,i_h) & 0xFFFFFF);
346                 // Get index from high four bits of each component.
347 int idx = (((rgb&0xF00000)>>> 12) |
348                            ((rgb&0x00F000)>>> 8) |
349                            ((rgb&0x0000F0)>>> 4));
350
351                     // Get the 'hash vector' for that key.
352 Vector v = colors[idx];
353                 if (v == null) {
354                     // No colors in this bin yet so create vector and
355 // add color.
356 v = new Vector ();
357                     v.add(new Counter(rgb));
358                     colors[idx] = v;
359                 } else {
360                     // find our color in the bin or create a counter for it.
361 Iterator i = v.iterator();
362                     while (true) {
363                         if (i.hasNext()) {
364                             // try adding our color to each counter...
365 if (((Counter)i.next()).add(rgb)) break;
366                         } else {
367                             v.add(new Counter(rgb));
368                             break;
369                         }
370                     }
371                 }
372             }
373         }
374
375         int nCubes=1;
376         int fCube=0;
377         Cube [] cubes = new Cube[nColors];
378         cubes[0] = new Cube(colors, w*h);
379         
380         while (nCubes < nColors) {
381             while (cubes[fCube].isDone()) {
382                 fCube++;
383                 if (fCube == nCubes) break;
384             }
385             if (fCube == nCubes) break;
386             Cube c = cubes[fCube];
387             Cube nc = c.split();
388             if (nc != null) {
389                 if (nc.count > c.count) {
390                     Cube tmp = c; c= nc; nc = tmp;
391                 }
392                 int j = fCube;
393                 int cnt = c.count;
394                 for (int i=fCube+1; i<nCubes; i++) {
395                     if (cubes[i].count < cnt)
396                         break;
397                     cubes[j++] = cubes[i];
398                 }
399                 cubes[j++] = c;
400
401                 cnt = nc.count;
402                 while (j<nCubes) {
403                     if (cubes[j].count < cnt)
404                         break;
405                     j++;
406                 }
407                 for (int i=nCubes; i>j; i--)
408                     cubes[i] = cubes[i-1];
409                 cubes[j++] = nc;
410                 nCubes++;
411             }
412         }
413
414         byte [] r = new byte[nCubes];
415         byte [] g = new byte[nCubes];
416         byte [] b = new byte[nCubes];
417         for (int i=0; i<nCubes; i++) {
418             int val = cubes[i].averageColor();
419             r[i] = (byte)((val>>16)&0xFF);
420             g[i] = (byte)((val>> 8)&0xFF);
421             b[i] = (byte)((val )&0xFF);
422
423             // System.out.println("Color [" + i + "]: #" +
424 // (((val>>16)<16)?"0":"") +
425 // Integer.toHexString(val));
426 }
427         BufferedImage indexed;
428
429
430         // The JDK doesn't seem to dither the image correctly if I go
431 // below 8bits per pixel. So I dither to an 8bit pallete
432 // image that only has nCubes colors. Then I copy the data to
433 // a lower bit depth image that I return.
434 IndexColorModel icm=new IndexColorModel (8,nCubes,r,g,b);
435         indexed =new BufferedImage
436             (w, h, BufferedImage.TYPE_BYTE_INDEXED, icm);
437         Graphics2D g2d=indexed.createGraphics();
438         g2d.setRenderingHint
439             (RenderingHints.KEY_DITHERING,
440              RenderingHints.VALUE_DITHER_ENABLE);
441         g2d.drawImage(bi, 0, 0, null);
442         g2d.dispose();
443
444
445         int bits;
446         for (bits=1; bits <=8; bits++) {
447             if ((1<<bits) >= nCubes) break;
448         }
449         // System.out.println("Bits: " + bits + " Cubes: " + nCubes);
450
451         if (bits > 4)
452             // 8 bit image we are done...
453 return indexed;
454
455         // Create our low bit depth image...
456 if (bits ==3) bits = 4;
457         ColorModel cm=new IndexColorModel (bits,nCubes,r,g,b);
458         SampleModel sm = new MultiPixelPackedSampleModel
459             (DataBuffer.TYPE_BYTE, w, h, bits);
460         WritableRaster ras = Raster.createWritableRaster
461             (sm, new Point (0,0));
462
463         // Copy the data to the low bitdepth image.
464 bi = indexed;
465         indexed = new BufferedImage (cm, ras,
466                                     bi.isAlphaPremultiplied(), null);
467         GraphicsUtil.copyData(bi, indexed);
468         return indexed;
469     }
470 }
471

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags