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