Path: utzoo!mnetor!uunet!mcvax!ukc!stl!stc!idec!camcon!anc
From: anc@camcon.uucp (Adrian Cockcroft)
Newsgroups: comp.graphics
Subject: Re: The 24-bit question.
Message-ID: <1343@titan.camcon.uucp>
Date: 22 Mar 88 18:20:12 GMT
Organization: Cambridge Consultants Ltd., Cambridge, UK
Lines: 254
Keywords: color, colormaps
Summary: code to do it

>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...)