wjc@XN.LL.MIT.EDU (William J. Chiarchiaro) (03/11/88)
Does anyone know of an algorithm for doing the following:
Take a digitized, color image composed of 24-bit pixels
(8 bits red, 8 bits green, 8 bits blue), and convert it to
an 8-bit-per-pixel color image along with a suitable
256-entry colormap (each entry has 8 bits of red, 8 of green,
and 8 of blue).
Thanks,
Bill
(reachable on Internet at wjc@xn.ll.mit.edu)jec@iuvax.cs.indiana.edu (James E. Conley) (03/11/88)
I'd also be interested in seeing this algorithm. What we've done is
fairly crude (striped off the high bits of each color)-- it works, but isn't
what we are after.
III Usenet: iuvax!jec
UUU I UUU ARPANet: jec@iuvax.cs.indiana.edu
U I U Phone: (812) 335-7729
U I U U.S. Mail: Indiana University
U I U Dept. of Computer Science
UUUIUUU 021-E Lindley Hall
I Bloomington, IN. 47405
III (Home of the Indiana Hoosiers-- 1987 NCAA Basketball Champions)fnf@fishpond.UUCP (Fred Fish) (03/11/88)
In article <927@xn.LL.MIT.EDU> wjc@XN.LL.MIT.EDU (William J. Chiarchiaro) writes: >Does anyone know of an algorithm for doing the following: > > Take a digitized, color image composed of 24-bit pixels > (8 bits red, 8 bits green, 8 bits blue), and convert it to > an 8-bit-per-pixel color image along with a suitable > 256-entry colormap (each entry has 8 bits of red, 8 of green, > and 8 of blue). Many of the 256-color images for the Mac-II currently making the rounds were generated precisely this way. The were digitized on a Commodore Amiga using a Digiview digitizer, and dumped into a file in 24-bit color (1 byte each of RGB), transfered to a Mac-II, and then converted to 256 color images using a program written by Steve Blackstock called "quantize". The resulting images were written in a format called GIF, defined and promoted by Compuserve, and displayable by another program of Steve's called "giffer". I believe that both the quantizer and giffer programs are available on Compuserve, and Steve can also be contacted there. -Fred -- # Fred Fish hao!noao!mcdsun!fishpond!fnf (602) 921-1113 # Ye Olde Fishpond, 1346 West 10th Place, Tempe, AZ 85281 USA
kyriazis@pawl17.pawl.rpi.edu (George Kyriazis) (03/11/88)
In article <927@xn.LL.MIT.EDU> wjc@XN.LL.MIT.EDU (William J. Chiarchiaro) writes: >Does anyone know of an algorithm for doing the following: > > Take a digitized, color image composed of 24-bit pixels > (8 bits red, 8 bits green, 8 bits blue), and convert it to > an 8-bit-per-pixel color image along with a suitable > 256-entry colormap (each entry has 8 bits of red, 8 of green, > and 8 of blue). > >Thanks, >Bill >(reachable on Internet at wjc@xn.ll.mit.edu) I have written two different programs that do the thing that you ask for. They are written for color SUNs that they have a colormap of 256 entries. The first method is a bit stupid. You define, for example, 3 bits for red, 3 bits for green and 2 bits for blue (unfortunately 256 is 2^8 and not 2^9), take the 3 (or 2) most significant bits of the primary colors, create a byte out of it and index it to the colormap. In other words, the colormap is fixed. The other method is a bit smarter, but it depends on the size and the number of original colors of the image. You start with an empty colormap, and check each incoming pixel if its color is in the colormap. If it is, use that index as its color, else add it to the end of the colormap. Unfortunately for pictures bigger than 128*128 the colormap runs out pretty quickly, so you can try eliminating the 1,2 or how many you want least significant bits of the input data, until everything fits in the colormap. Of course you can elimimate a different number of bits for different primary colors. Hope that I helped you.. ******************************************************* *George C. Kyriazis * Gravity is a myth *userfe0e@mts.rpi.edu or userfe0e@rpitsmts.bitnet * \ / *Electrical and Computer Systems Engineering Dept. * \ / *Rensselear Polytechnic Institute, Troy, NY 12180 * || ******************************************************* Earth sucks.
dwight@akelei.UUCP (Dwight Melcher) (03/12/88)
I've implemented slight variations on the algorithm presented in
Heckbert, "Color Image Quantization for Frame Buffer Display",
Computer Graphics, V16 #3 (July 1982).
It gives quite good results, was fairly easy to implement, and the
performance is reasonable on SUN3 machines. If you're interested in
having the code, and not too picky about dealing with grungy stuff
(this was a Saturday afternoon quick-hack special), send me a note and I
can mail you a copy of the C source.
--
Dwight Melcher
Columbine Data Systems, Inc.
3300 Mitchell Lane Suite 380
Boulder, CO 80301 { hao!boulder , sun!sunpeaks }!akelei!dwightkurtk@tekcae.TEK.COM (Kurt Krueger) (03/12/88)
It seems to me that the real question is how to represent a 24bit deep image on a device that is only 8 bits deep without throwing away any more information than necessary. The solutions I've seen so far throw away more info than needed, and indeed, can run into some severe problems if you run out of color map before you run out of colors. Some solutions that work very well are to divide up the available color map as well as possible. Something to remember is that the human eye has poor spacial resolution with blue light, but very good color resolution (you can't see much detail in blue areas but you can sure tell the difference between shades of blue). You then either dither to the available colors or use an error difusion method. With 256 shades of grey I've been able to error diffuse images and not be able to see any color steps. Having ~1300 pixels across, of course, helps. A warning on dither techniques: If your output display is not "gamma corrected" you will have to include this correction in your rendering code. A device that is not gamma corrected will not have equally perceived brightness changes across the available range (i.e. you ask for 2x change and you actually get 3x or 1.5x).
jbm@eos.UUCP (Jeffrey Mulligan) (03/15/88)
From article <1528@tekcae.TEK.COM>, by kurtk@tekcae.TEK.COM (Kurt Krueger): > A warning on dither techniques: If your output display is not "gamma corrected" > you will have to include this correction in your rendering code. A device that > is not gamma corrected will not have equally perceived brightness changes > across the available range (i.e. you ask for 2x change and you actually get > 3x or 1.5x). It can get worse that; since very few displays themselves are linear, gamma correction must be done in software to compensate for the physical nonlinearity. This is fine. A separate problem is the failure of spatial independence. When this rears its ugly head, it can cause a 50% density of black and white dots to be darker that the (gamma corrected) mean of the white and black levels. It should be emphasized that without gamma correction, the dithered pattern would be brighter than the mid-level setting, since the gamma nonlinearity is positively accelerating. My theory about this is that it reflects inadequate video bandwidth; i.e. the monitor can be modeled as a low pass filter followed by a nonlinearity (the gamma function). A simple way to measure this is to put up alternating black and white lines, either horizontal or vertical. The vertical line pattern can have a substantially lower mean luminance. If anyone is interested, Lee Stone and myself are working on a manuscript which contains a section on this topic.
ksbooth@watcgl.waterloo.edu (Kelly Booth) (03/16/88)
In article <927@xn.LL.MIT.EDU> wjc@XN.LL.MIT.EDU (William J. Chiarchiaro) writes: > >Does anyone know of an algorithm for doing the following: > > Take a digitized, color image composed of 24-bit pixels > (8 bits red, 8 bits green, 8 bits blue), and convert it to > an 8-bit-per-pixel color image along with a suitable > 256-entry colormap (each entry has 8 bits of red, 8 of green, > and 8 of blue). Paul Heckbert had a paper on this in SIGGRAPH '82. No, this is not a joke. He really did have a (serious) paper. This is another of the semi-monthly items that appear in comp.graphics. It's been beaten to death. Read the original paper then check the literature for subsequent work. P.S. The work was done while Paul was an undergrad at M.I.T., I think as an honors thesis. Your school should have a copy :).
anc@camcon.uucp (Adrian Cockcroft) (03/23/88)
>Does anyone know of an algorithm for doing the following: > > Take a digitized, color image composed of 24-bit pixels > (8 bits red, 8 bits green, 8 bits blue), and convert it to > an 8-bit-per-pixel color image along with a suitable > 256-entry colormap (each entry has 8 bits of red, 8 of green, > and 8 of blue). > >Thanks, >Bill >(reachable on Internet at wjc@xn.ll.mit.edu) I did this as well. We have a CRS 512 by 512 frame grabber and I grabbed a picture of a Ferrari 308GTO via red, green, blue filters and wanted to see a red ferrari. The camera was B&W with auto gain control (yuk) so my algorithm let me balance the red, green, blue. It is a better algorithm than taking the top few bits but not the best. It takes about 15 minutes to run on a SUN 3/160. First histogram the rgb combinations. Second take the top 256 entries in the histogram and remap all other entries to the nearest one in the top. I use a primitive notion of nearest, the best algorithms are more sophisticated. Remap all the pixels in the picture using the top 256 entries and write out the combined picture as a lookup table and an 8 bit deep picture. Since we need to sort the histogram at the end it makes sense to sort it a few times while histograming so that we don't have to search so far. Its only ~200 lines so here it is. A few mods for SUN rasterfiles will be needed. Note that this was hacked together for my own use and anyone can do anything with it. #!/bin/sh # Archived: Tue Mar 22 18:10:20 GMT 1988 # # Contents: # image.c # echo x - image.c sed 's/^X//' >image.c <<'*-*-END-of-image.c-*-*' X/* combine r,g,b and produce lut table 28/1/87 anc */ X X#include "stdio.h" X XFILE *fred,*fgreen,*fblue; XFILE *fout,*flut; X Xstruct clr X { X unsigned red:8; X unsigned green:8; X unsigned blue:8; X }; X Xstruct clr histval[512*512]; /* could be up to 512*512 different colours */ Xint histcnt[512*512]; Xint histsize = 0; X X#define abs(x) ((x)>=0?(x):-(x)) X Xmain(argc,argv) X int argc; X char *argv[]; X { X char oname[20]; X char lname[20]; X int i,n; X struct clr col; X short rmul,gmul,bmul; X short notfound; X if (argc < 4) X { X printf("image red*256 green*256 blue*256\n"); X exit(0); X } X rmul = atoi(argv[1]); X gmul = atoi(argv[2]); X bmul = atoi(argv[3]); X sprintf(oname,"f%d%d%d.I",rmul,gmul,bmul); X sprintf(lname,"f%d%d%d.OUT",rmul,gmul,bmul); X printf("Using red=%d/256 green=%d/256 blue=%d/256\n",rmul,gmul,bmul); X fred = fopen("fred.I","r"); X fgreen = fopen("fgreen.I","r"); X fblue = fopen("fblue.I","r"); X fout = fopen(oname,"w"); X flut = fopen(lname,"w"); X if (fred==0 || fgreen==0 || fblue==0) X { X printf("cant open input files\n"); X exit(0); X } X /* histogram the input files */ X for(n=0;n < 512*512; ++n) X { X /* make weighted 24 bit colour */ X col.red = (fgetc(fred)*rmul)>>8; X col.green = (fgetc(fgreen)*gmul)>>8; X col.blue = (fgetc(fblue)*bmul)>>8; X notfound = 1; X#ifdef DEBUG X printf("r=%x g=%x b=%x col=%x",col.red,col.green,col.blue,col); X#endif X for(i=0; i<histsize; ++i) /* search existing colours */ X { X if (col == histval[i]) X { X ++histcnt[i]; /* existing colour */ X notfound = 0; X break; X } X } X if (notfound) X { X#ifdef DEBUG X printf(" notfound "); X#endif X histval[histsize] = col; /* new colour */ X histcnt[histsize++] = 1; X } X#ifdef DEBUG X printf(" histsize=%d\n",histsize); X#endif X /* sort the histogram every now and again */ X if ((n & 0x000007FF) == 0) /* every 2048 pixels */ X#ifdef DEBUGS X sort(1); X#else X sort(0); X#endif X } X printf("histsize = %d\n",histsize); X sort(1); /* print out the table */ X remap(); /* collapse the lut to 256 entries */ X printf("remapped:\n"); X for(i=256;i<histsize;++i) X printf("val=%x lut=%d\n",histval[i],histcnt[i]); X /* write the output file */ X rewind(fred); X rewind(fgreen); X rewind(fblue); /* run through image again */ X for(n=0;n < 512*512; ++n) X { X notfound = 1; X /* make weighted 24 bit colour */ X col.red = (fgetc(fred)*rmul)>>8; X col.green = (fgetc(fgreen)*gmul)>>8; X col.blue = (fgetc(fblue)*bmul)>>8; X for(i=0; i<histsize; ++i) /* search existing colours */ X { X if (col == histval[i]) X { X if (i<256) X fputc(i,fout); /* true entry */ X else X fputc(histcnt[i],fout); /* remapped */ X notfound = 0; X break; X } X } X if (notfound) X { X printf("panic: pixel %d not found\n",n); X } X } X X } X Xsort(print) X int print; X/* bubble sort histogram to put most common at top */ X { X register int i=1; X register int tmp; X struct clr ctmp; X while(i < histsize) X { X if (histcnt[i] > histcnt[i-1]) X { X /* swap */ X tmp = histcnt[i]; X histcnt[i] = histcnt[i-1]; X histcnt[i-1] = tmp; X ctmp = histval[i]; X histval[i] = histval[i-1]; X histval[i-1] = ctmp; X if (i > 1) X --i; X } X else X ++i; X } X if (print) X for(i=0; i<histsize; ++i) X printf("%d count=%d val=%x\n",i,histcnt[i],histval[i]); X } X X#define MUL 4 /* brighten result by 4, for use with mults of 0-63 */ X Xremap() X/* collapse lut to 256 entries and write to file */ X { X int i,n,diff,mindiff,minno; X for(n=256; n<histsize; ++n) X { X minno = 0; X mindiff = coldiff(histval[n],histval[0]); X for(i=1; i<256; ++i) X { X diff = coldiff(histval[n],histval[i]); X if (diff < mindiff) X { X mindiff = diff; X minno = i; X } X } X histcnt[n] = minno; /* reuse cnt with nearest clut index */ X } X /* clut now remapped - write it out */ X for(i=0; i<256;++i) X { X putc(0,flut); /* 16 bit values with top byte zero */ X putc(histval[i].red*MUL,flut); /* red */ X } X for(i=0; i<256;++i) X { X putc(0,flut); X putc(histval[i].green*MUL,flut); /* green */ X } X for(i=0; i<256;++i) X { X putc(0,flut); X putc(histval[i].blue*MUL,flut); /* blue */ X } X } X Xint coldiff(c1,c2) X struct clr c1,c2; X { X return abs(c1.red - c2.red) + X abs(c1.green - c2.green) + X abs(c1.blue - c2.blue); X } X X *-*-END-of-image.c-*-* echo End of Archive exit -- | Adrian Cockcroft anc@camcon.uucp ..!seismo!mcvax!ukc!camcon!anc -[T]- Cambridge Consultants Ltd, Science Park, Cambridge CB4 4DW, | England, UK (0223) 358855 (You are in a maze of twisty little C004's, all alike...)
michael@orcisi.UUCP (Michael Herman) (03/27/88)
An interesting way to histogram a raster image is to load it into a frame buffer, quicksort it and then run-length encode it. The RLE output is your histogram. It's also visually interesting to watch.