src/px/ciq.c

/* Copyright 1988 Regents of the University of California */

#ifndef lint
static char SCCSid[] = "$SunId$ LBL";
#endif

/*
CIQ - main program for color image quantization
options for Floyd-Steinberg dithering by minimization of accumulated error
or undithered quantization

Paul Heckbert   16 April 82, cleaned up 8 June 86
Greg Ward       1 March 88, modified for arbitrary picture sizes
*/

#include "standard.h"
#include "ciq.h"

#define table(m,r,g,b) hist[m[0][r]|m[1][g]|m[2][b]]  /* histogram/pvtable */

int hist[len];          /* list of frequencies or pixelvalues for coded color */

colormap color;         /* quantization colormap */
int n;                  /* number of colors in it */

#define ERRMAX 20       /* maximum allowed propagated error,
                           if >=255 then no clamping */

/*----------------------------------------------------------------------*/

ciq(dith,nw,synth,cm)
int dith;               /* is dithering desired? 0=no, 1=yes */
int nw;                 /* number of colors wanted in output image */
int synth;              /* synthesize colormap? 0=no, 1=yes */
colormap cm;            /* quantization colormap */
                        /* read if synth=0; always written */
{
    int na,i;
    colormap ocm;

    picreadcm(ocm);     /* read original picture's colormap (usually identity)*/
    sample(ocm);        /* find histogram */

    if (synth)
        n = makecm(nw,&na);     /* analyze histogram and synthesize colormap */
    else {
        bcopy((char *)cm,(char *)color,sizeof color);
        n = nw;
        na = 0;
        for (i=0; i<len; i++) if (hist[i]) na++;
        /*printf("from %d to %d colors\n",na,n);*/
    }
    picwritecm(color);

    initializeclosest();
    if (dith)
        draw_dith(ocm);
    else {
        for (i=0; i<len; i++)
            if (hist[i]) hist[i] = closest(red(i),gre(i),blu(i));
        draw_nodith(ocm);
    }

    bcopy((char *)color,(char *)cm,sizeof color);
    /*endclosest();*/
}

/*----------------------------------------------------------------------*/

sample(ocm)             /* make color frequency table (histogram) */
colormap ocm;
{
    register int x,y;
    register rgbpixel *lp;
    rgbpixel *line;
    colormap map;

    for (x = 0; x < len; x++)   /* clear histogram */
        hist[x] = 0;

    line = line3alloc(xmax);
    convertmap(ocm,map);

    for (y=0; y<ymax; y++) {
        picreadline3(y,line);
        for (lp=line, x=0; x<xmax; x++, lp++)
            table(map,lp->r,lp->g,lp->b)++;
    }
    free((char *)line);
}

convertmap(in,out)              /* convert to shifted color map */
register colormap in,out;
{
    register int j;

    for (j=0; j<256; j++) {
        out[0][j] = (in[0][j]&0xf8)<<7;
        out[1][j] = (in[1][j]&0xf8)<<2;
        out[2][j] = (in[2][j]&0xf8)>>3;
    }
}

draw_nodith(ocm)        /* quantize without dithering */
colormap ocm;                   /* colormap for orig */
{
    register int x,y;
    register rgbpixel *lp;
    rgbpixel *iline;
    pixel *oline;
    colormap map;

    iline = line3alloc(xmax);
    oline = linealloc(xmax);
    convertmap(ocm,map);

    for (y=0; y<ymax; y++) {
        picreadline3(y,iline);
        for (lp=iline, x=0; x<xmax; x++, lp++)
            oline[x] = table(map,lp->r,lp->g,lp->b);
        picwriteline(y,oline);
    }
    free((char *)iline);
    free((char *)oline);
}

draw_dith(ocm)                  /* quantize with dithering */
colormap ocm;                   /* colormap for orig */
{
    register int *p,*q,rr,gg,bb,v,x,y,*P,*Q,*R;
    int *buf;
    rgbpixel *iline;            /* input scanline */
    pixel *oline;               /* output scanline */

    buf = (int *)ecalloc(2,3*sizeof(int)*(xmax+1));
    iline = line3alloc(xmax);
    oline = linealloc(xmax);
    /* reuse hist array as quantization table */
    for (v=0; v<len; v++) hist[v] = -1;

    P = &buf[0];
    Q = &buf[3*(xmax+1)];
    for (y=0; y<ymax; y++, R=P, P=Q, Q=R) {
        Q[0] = Q[1] = Q[2] = 0;
        picreadline3(y,iline);
        for (p=P, q=Q, x=0; x<xmax; x++, p+=3, q+=3) {
            rr = p[0];
            if (rr<-ERRMAX) rr = -ERRMAX; else if (rr>ERRMAX) rr = ERRMAX;
            gg = p[1];
            if (gg<-ERRMAX) gg = -ERRMAX; else if (gg>ERRMAX) gg = ERRMAX;
            bb = p[2];
            if (bb<-ERRMAX) bb = -ERRMAX; else if (bb>ERRMAX) bb = ERRMAX;
            /* now rr,gg,bb is propagated color */
            rr += ocm[0][iline[x].r];
            gg += ocm[1][iline[x].g];   /* ideal */
            bb += ocm[2][iline[x].b];
            if (rr<0) rr = 0; else if (rr>255) rr = 255;
            if (gg<0) gg = 0; else if (gg>255) gg = 255;
            if (bb<0) bb = 0; else if (bb>255) bb = 255;
            v = (rr&0xf8)<<7 | (gg&0xf8)<<2 | (bb&0xf8)>>3;
            if (hist[v]<0)
                hist[v] = closest(rr,gg,bb);    /* nearest to ideal */
            oline[x] = v = hist[v];
            rr -= color[0][v];
            gg -= color[1][v];                  /* error */
            bb -= color[2][v];
            v = rr*3>>3; p[3] += v; q[0] += v; q[3] = rr-(v<<1);
            v = gg*3>>3; p[4] += v; q[1] += v; q[4] = gg-(v<<1);
            v = bb*3>>3; p[5] += v; q[2] += v; q[5] = bb-(v<<1);
        }
        picwriteline(y,oline);
    }
    free((char *)iline);
    free((char *)oline);
    free((char *)buf);
}
Revision:	1.6
Committed:	Tue Dec 4 11:25:45 1990 UTC (33 years, 5 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.5:	+1 -0 lines
Log Message:	added standard.h to take care of bcopy() incompatibilities
#	User	Rev	Content
1	greg	1.2	/* Copyright 1988 Regents of the University of California */
2	greg	1.1
3			#ifndef lint
4			static char SCCSid[] = "$SunId$ LBL";
5			#endif
6	greg	1.2
7			/*
8	greg	1.1	CIQ - main program for color image quantization
9			options for Floyd-Steinberg dithering by minimization of accumulated error
10			or undithered quantization
11
12			Paul Heckbert 16 April 82, cleaned up 8 June 86
13			Greg Ward 1 March 88, modified for arbitrary picture sizes
14			*/
15
16	greg	1.6	#include "standard.h"
17	greg	1.1	#include "ciq.h"
18
19			#define table(m,r,g,b) hist[m[0][r]\|m[1][g]\|m[2][b]] /* histogram/pvtable */
20
21			int hist[len]; /* list of frequencies or pixelvalues for coded color */
22
23			colormap color; /* quantization colormap */
24			int n; /* number of colors in it */
25
26	ph	1.4	#define ERRMAX 20 /* maximum allowed propagated error,
27			if >=255 then no clamping */
28
29	greg	1.1	/----------------------------------------------------------------------/
30
31			ciq(dith,nw,synth,cm)
32			int dith; /* is dithering desired? 0=no, 1=yes */
33			int nw; /* number of colors wanted in output image */
34			int synth; /* synthesize colormap? 0=no, 1=yes */
35			colormap cm; /* quantization colormap */
36			/* read if synth=0; always written */
37			{
38			int na,i;
39			colormap ocm;
40
41			picreadcm(ocm); /* read original picture's colormap (usually identity)*/
42			sample(ocm); /* find histogram */
43
44			if (synth)
45			n = makecm(nw,&na); /* analyze histogram and synthesize colormap */
46			else {
47	greg	1.5	bcopy((char )cm,(char )color,sizeof color);
48	greg	1.1	n = nw;
49			na = 0;
50			for (i=0; i<len; i++) if (hist[i]) na++;
51			/printf("from %d to %d colors\n",na,n);/
52			}
53			picwritecm(color);
54
55	ph	1.4	initializeclosest();
56	greg	1.1	if (dith)
57			draw_dith(ocm);
58			else {
59			for (i=0; i<len; i++)
60			if (hist[i]) hist[i] = closest(red(i),gre(i),blu(i));
61			draw_nodith(ocm);
62			}
63
64	greg	1.5	bcopy((char )color,(char )cm,sizeof color);
65	greg	1.1	/endclosest();/
66			}
67
68			/----------------------------------------------------------------------/
69
70			sample(ocm) /* make color frequency table (histogram) */
71			colormap ocm;
72			{
73			register int x,y;
74			register rgbpixel *lp;
75			rgbpixel *line;
76			colormap map;
77
78	greg	1.3	for (x = 0; x < len; x++) /* clear histogram */
79			hist[x] = 0;
80
81	greg	1.1	line = line3alloc(xmax);
82			convertmap(ocm,map);
83
84			for (y=0; y<ymax; y++) {
85			picreadline3(y,line);
86			for (lp=line, x=0; x<xmax; x++, lp++)
87			table(map,lp->r,lp->g,lp->b)++;
88			}
89			free((char *)line);
90			}
91
92			convertmap(in,out) /* convert to shifted color map */
93			register colormap in,out;
94			{
95			register int j;
96
97			for (j=0; j<256; j++) {
98			out[0][j] = (in[0][j]&0xf8)<<7;
99			out[1][j] = (in[1][j]&0xf8)<<2;
100			out[2][j] = (in[2][j]&0xf8)>>3;
101			}
102			}
103
104			draw_nodith(ocm) /* quantize without dithering */
105			colormap ocm; /* colormap for orig */
106			{
107			register int x,y;
108			register rgbpixel *lp;
109			rgbpixel *iline;
110			pixel *oline;
111			colormap map;
112
113			iline = line3alloc(xmax);
114			oline = linealloc(xmax);
115			convertmap(ocm,map);
116
117			for (y=0; y<ymax; y++) {
118			picreadline3(y,iline);
119			for (lp=iline, x=0; x<xmax; x++, lp++)
120			oline[x] = table(map,lp->r,lp->g,lp->b);
121			picwriteline(y,oline);
122			}
123			free((char *)iline);
124			free((char *)oline);
125			}
126
127			draw_dith(ocm) /* quantize with dithering */
128			colormap ocm; /* colormap for orig */
129			{
130			register int p,q,rr,gg,bb,v,x,y,P,Q,*R;
131			int *buf;
132			rgbpixel iline; / input scanline */
133			pixel oline; / output scanline */
134
135			buf = (int )ecalloc(2,3sizeof(int)*(xmax+1));
136			iline = line3alloc(xmax);
137			oline = linealloc(xmax);
138			/* reuse hist array as quantization table */
139			for (v=0; v<len; v++) hist[v] = -1;
140
141			P = &buf[0];
142			Q = &buf[3*(xmax+1)];
143			for (y=0; y<ymax; y++, R=P, P=Q, Q=R) {
144			Q[0] = Q[1] = Q[2] = 0;
145			picreadline3(y,iline);
146			for (p=P, q=Q, x=0; x<xmax; x++, p+=3, q+=3) {
147	ph	1.4	rr = p[0];
148			if (rr<-ERRMAX) rr = -ERRMAX; else if (rr>ERRMAX) rr = ERRMAX;
149			gg = p[1];
150			if (gg<-ERRMAX) gg = -ERRMAX; else if (gg>ERRMAX) gg = ERRMAX;
151			bb = p[2];
152			if (bb<-ERRMAX) bb = -ERRMAX; else if (bb>ERRMAX) bb = ERRMAX;
153			/* now rr,gg,bb is propagated color */
154			rr += ocm[0][iline[x].r];
155			gg += ocm[1][iline[x].g]; /* ideal */
156			bb += ocm[2][iline[x].b];
157	greg	1.1	if (rr<0) rr = 0; else if (rr>255) rr = 255;
158			if (gg<0) gg = 0; else if (gg>255) gg = 255;
159			if (bb<0) bb = 0; else if (bb>255) bb = 255;
160			v = (rr&0xf8)<<7 \| (gg&0xf8)<<2 \| (bb&0xf8)>>3;
161			if (hist[v]<0)
162			hist[v] = closest(rr,gg,bb); /* nearest to ideal */
163			oline[x] = v = hist[v];
164			rr -= color[0][v];
165			gg -= color[1][v]; /* error */
166			bb -= color[2][v];
167			v = rr*3>>3; p[3] += v; q[0] += v; q[3] = rr-(v<<1);
168			v = gg*3>>3; p[4] += v; q[1] += v; q[4] = gg-(v<<1);
169			v = bb*3>>3; p[5] += v; q[2] += v; q[5] = bb-(v<<1);
170			}
171			picwriteline(y,oline);
172			}
173			free((char *)iline);
174			free((char *)oline);
175			free((char *)buf);
176			}