src/px/ciq.c

#ifndef lint
static const char       RCSid[] = "$Id: ciq.c,v 2.5 2004/03/28 20:33:13 schorsch Exp $";
#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 <string.h>

#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 */

static void sample(colormap ocm);
static void convertmap(colormap in, colormap out);
static void draw_nodith(colormap ocm);
static void draw_dith(colormap ocm);


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

void
ciq(
        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 {
        memcpy((void *)color,(void *)cm,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);
    }

    memcpy((void *)cm,(void *)color,sizeof color);
    /*endclosest();*/
}

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

static void
sample(         /* 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((void *)line);
}

static void
convertmap(             /* convert to shifted color map */
        register colormap in,
        register colormap 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;
    }
}

static void
draw_nodith(    /* 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((void *)iline);
    free((void *)oline);
}

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