1 /* dither.c:
2 *
3 * routine for dithering a color image to monochrome based on color
4 * intensity. this is loosely based on an algorithm which barry shein
5 * (bzs@std.com) used in his "xf" program.
6 *
7 * jim frost 07.10.89
8 *
9 * Copyright 1989, 1990 Jim Frost.
10 * See included file "copyright.h" for complete copyright information.
11 */
12
13 #include "copyright.h"
14 #include "image.h"
15
16 /* RGB intensity tables. red is (val * 0.30), green is (val * 0.59), blue
17 * is (val * .11), where val is intensity >> 8. these are used by the
18 * colorIntensity() macro in images.h.
19 */
20
21 unsigned short RedIntensity[256]= {
22 0, 76, 153, 230, 307, 384, 460, 537,
23 614, 691, 768, 844, 921, 998, 1075, 1152,
24 1228, 1305, 1382, 1459, 1536, 1612, 1689, 1766,
25 1843, 1920, 1996, 2073, 2150, 2227, 2304, 2380,
26 2457, 2534, 2611, 2688, 2764, 2841, 2918, 2995,
27 3072, 3148, 3225, 3302, 3379, 3456, 3532, 3609,
28 3686, 3763, 3840, 3916, 3993, 4070, 4147, 4224,
29 4300, 4377, 4454, 4531, 4608, 4684, 4761, 4838,
30 4915, 4992, 5068, 5145, 5222, 5299, 5376, 5452,
31 5529, 5606, 5683, 5760, 5836, 5913, 5990, 6067,
32 6144, 6220, 6297, 6374, 6451, 6528, 6604, 6681,
33 6758, 6835, 6912, 6988, 7065, 7142, 7219, 7296,
34 7372, 7449, 7526, 7603, 7680, 7756, 7833, 7910,
35 7987, 8064, 8140, 8217, 8294, 8371, 8448, 8524,
36 8601, 8678, 8755, 8832, 8908, 8985, 9062, 9139,
37 9216, 9292, 9369, 9446, 9523, 9600, 9676, 9753,
38 9830, 9907, 9984, 10060, 10137, 10214, 10291, 10368,
39 10444, 10521, 10598, 10675, 10752, 10828, 10905, 10982,
40 11059, 11136, 11212, 11289, 11366, 11443, 11520, 11596,
41 11673, 11750, 11827, 11904, 11980, 12057, 12134, 12211,
42 12288, 12364, 12441, 12518, 12595, 12672, 12748, 12825,
43 12902, 12979, 13056, 13132, 13209, 13286, 13363, 13440,
44 13516, 13593, 13670, 13747, 13824, 13900, 13977, 14054,
45 14131, 14208, 14284, 14361, 14438, 14515, 14592, 14668,
46 14745, 14822, 14899, 14976, 15052, 15129, 15206, 15283,
47 15360, 15436, 15513, 15590, 15667, 15744, 15820, 15897,
48 15974, 16051, 16128, 16204, 16281, 16358, 16435, 16512,
49 16588, 16665, 16742, 16819, 16896, 16972, 17049, 17126,
50 17203, 17280, 17356, 17433, 17510, 17587, 17664, 17740,
51 17817, 17894, 17971, 18048, 18124, 18201, 18278, 18355,
52 18432, 18508, 18585, 18662, 18739, 18816, 18892, 18969,
53 19046, 19123, 19200, 19276, 19353, 19430, 19507, 19584
54 };
55
56 unsigned short GreenIntensity[256]= {
57 0, 151, 302, 453, 604, 755, 906, 1057,
58 1208, 1359, 1510, 1661, 1812, 1963, 2114, 2265,
59 2416, 2567, 2718, 2869, 3020, 3171, 3322, 3473,
60 3624, 3776, 3927, 4078, 4229, 4380, 4531, 4682,
61 4833, 4984, 5135, 5286, 5437, 5588, 5739, 5890,
62 6041, 6192, 6343, 6494, 6645, 6796, 6947, 7098,
63 7249, 7400, 7552, 7703, 7854, 8005, 8156, 8307,
64 8458, 8609, 8760, 8911, 9062, 9213, 9364, 9515,
65 9666, 9817, 9968,10119,10270,10421,10572,10723,
66 10874,11025,11176,11328,11479,11630,11781,11932,
67 12083,12234,12385,12536,12687,12838,12989,13140,
68 13291,13442,13593,13744,13895,14046,14197,14348,
69 14499,14650,14801,14952,15104,15255,15406,15557,
70 15708,15859,16010,16161,16312,16463,16614,16765,
71 16916,17067,17218,17369,17520,17671,17822,17973,
72 18124,18275,18426,18577,18728,18880,19031,19182,
73 19333,19484,19635,19786,19937,20088,20239,20390,
74 20541,20692,20843,20994,21145,21296,21447,21598,
75 21749,21900,22051,22202,22353,22504,22656,22807,
76 22958,23109,23260,23411,23562,23713,23864,24015,
77 24166,24317,24468,24619,24770,24921,25072,25223,
78 25374,25525,25676,25827,25978,26129,26280,26432,
79 26583,26734,26885,27036,27187,27338,27489,27640,
80 27791,27942,28093,28244,28395,28546,28697,28848,
81 28999,29150,29301,29452,29603,29754,29905,30056,
82 30208,30359,30510,30661,30812,30963,31114,31265,
83 31416,31567,31718,31869,32020,32171,32322,32473,
84 32624,32775,32926,33077,33228,33379,33530,33681,
85 33832,33984,34135,34286,34437,34588,34739,34890,
86 35041,35192,35343,35494,35645,35796,35947,36098,
87 36249,36400,36551,36702,36853,37004,37155,37306,
88 37457,37608,37760,37911,38062,38213,38364,38515
89 };
90
91 unsigned short BlueIntensity[256]= {
92 0, 28, 56, 84, 112, 140, 168, 197,
93 225, 253, 281, 309, 337, 366, 394, 422,
94 450, 478, 506, 535, 563, 591, 619, 647,
95 675, 704, 732, 760, 788, 816, 844, 872,
96 901, 929, 957, 985, 1013, 1041, 1070, 1098,
97 1126, 1154, 1182, 1210, 1239, 1267, 1295, 1323,
98 1351, 1379, 1408, 1436, 1464, 1492, 1520, 1548,
99 1576, 1605, 1633, 1661, 1689, 1717, 1745, 1774,
100 1802, 1830, 1858, 1886, 1914, 1943, 1971, 1999,
101 2027, 2055, 2083, 2112, 2140, 2168, 2196, 2224,
102 2252, 2280, 2309, 2337, 2365, 2393, 2421, 2449,
103 2478, 2506, 2534, 2562, 2590, 2618, 2647, 2675,
104 2703, 2731, 2759, 2787, 2816, 2844, 2872, 2900,
105 2928, 2956, 2984, 3013, 3041, 3069, 3097, 3125,
106 3153, 3182, 3210, 3238, 3266, 3294, 3322, 3351,
107 3379, 3407, 3435, 3463, 3491, 3520, 3548, 3576,
108 3604, 3632, 3660, 3688, 3717, 3745, 3773, 3801,
109 3829, 3857, 3886, 3914, 3942, 3970, 3998, 4026,
110 4055, 4083, 4111, 4139, 4167, 4195, 4224, 4252,
111 4280, 4308, 4336, 4364, 4392, 4421, 4449, 4477,
112 4505, 4533, 4561, 4590, 4618, 4646, 4674, 4702,
113 4730, 4759, 4787, 4815, 4843, 4871, 4899, 4928,
114 4956, 4984, 5012, 5040, 5068, 5096, 5125, 5153,
115 5181, 5209, 5237, 5265, 5294, 5322, 5350, 5378,
116 5406, 5434, 5463, 5491, 5519, 5547, 5575, 5603,
117 5632, 5660, 5688, 5716, 5744, 5772, 5800, 5829,
118 5857, 5885, 5913, 5941, 5969, 5998, 6026, 6054,
119 6082, 6110, 6138, 6167, 6195, 6223, 6251, 6279,
120 6307, 6336, 6364, 6392, 6420, 6448, 6476, 6504,
121 6533, 6561, 6589, 6617, 6645, 6673, 6702, 6730,
122 6758, 6786, 6814, 6842, 6871, 6899, 6927, 6955,
123 6983, 7011, 7040, 7068, 7096, 7124, 7152, 7180
124 };
125
126 /* 4x4 arrays used for dithering, arranged by nybble
127 */
128
129 #define GRAYS 17 /* ((4 * 4) + 1) patterns for a good dither */
130 #define GRAYSTEP ((unsigned long)(65536 / GRAYS))
131
132 static byte DitherBits[GRAYS][4] = {
133 {0xf, 0xf, 0xf, 0xf},
134 {0xe, 0xf, 0xf, 0xf},
135 {0xe, 0xf, 0xb, 0xf},
136 {0xa, 0xf, 0xb, 0xf},
137 {0xa, 0xf, 0xa, 0xf},
138 {0xa, 0xd, 0xa, 0xf},
139 {0xa, 0xd, 0xa, 0x7},
140 {0xa, 0x5, 0xa, 0x7},
141 {0xa, 0x5, 0xa, 0x5},
142 {0x8, 0x5, 0xa, 0x5},
143 {0x8, 0x5, 0x2, 0x5},
144 {0x0, 0x5, 0x2, 0x5},
145 {0x0, 0x5, 0x0, 0x5},
146 {0x0, 0x4, 0x0, 0x5},
147 {0x0, 0x4, 0x0, 0x1},
148 {0x0, 0x0, 0x0, 0x1},
149 {0x0, 0x0, 0x0, 0x0}
150 };
151
152 /* simple dithering algorithm, really optimized for the 4x4 array
153 */
154
halftone(cimage,verbose)155 Image *halftone(cimage, verbose)
156 Image *cimage;
157 unsigned int verbose;
158 { Image *image;
159 unsigned char *sp, *dp, *dp2; /* data pointers */
160 unsigned int dindex; /* index into dither array */
161 unsigned int spl; /* source pixel length in bytes */
162 unsigned int dll; /* destination line length in bytes */
163 Pixel color; /* pixel color */
164 unsigned int *index; /* index into dither array for a given pixel */
165 unsigned int a, x, y; /* random counters */
166
167 goodImage(cimage, "dither");
168 if (BITMAPP(cimage))
169 return(NULL);
170
171 /* set up
172 */
173
174 if (verbose) {
175 printf(" Halftoning image...");
176 fflush(stdout);
177 }
178 image= newBitImage(cimage->width * 4, cimage->height * 4);
179 if (cimage->title) {
180 image->title= (char *)lmalloc(strlen(cimage->title) + 13);
181 sprintf(image->title, "%s (halftoned)", cimage->title);
182 }
183 spl= cimage->pixlen;
184 dll= (image->width / 8) + (image->width % 8 ? 1 : 0);
185
186 /* if the number of possible pixels isn't very large, build an array
187 * which we index by the pixel value to find the dither array index
188 * by color brightness. we do this in advance so we don't have to do
189 * it for each pixel. things will break if a pixel value is greater
190 * than (1 << depth), which is bogus anyway. this calculation is done
191 * on a per-pixel basis if the colormap is too big.
192 */
193
194 if (RGBP(cimage) && (cimage->depth <= 16)) {
195 index= (unsigned int *)lmalloc(sizeof(unsigned int) * cimage->rgb.used);
196 for (x= 0; x < cimage->rgb.used; x++) {
197 *(index + x)=
198 ((unsigned long)colorIntensity(*(cimage->rgb.red + x),
199 *(cimage->rgb.green + x),
200 *(cimage->rgb.blue + x))) / GRAYSTEP;
201 if (*(index + x) >= GRAYS) /* rounding errors can do this */
202 *(index + x)= GRAYS - 1;
203 }
204 }
205 else
206 index= NULL;
207
208 /* dither each pixel
209 */
210
211 sp= cimage->data;
212 dp= image->data;
213 for (y= 0; y < cimage->height; y++) {
214 for (x= 0; x < cimage->width; x++) {
215 dp2= dp + (x >> 1);
216 color= memToVal(sp, spl);
217 if (RGBP(cimage)) {
218 if (index)
219 dindex= *(index + color);
220 else {
221 dindex=
222 ((unsigned long)colorIntensity(cimage->rgb.red[color],
223 cimage->rgb.green[color],
224 cimage->rgb.blue[color])) / GRAYSTEP;
225 }
226 }
227 else {
228 dindex=
229 ((unsigned long)colorIntensity((TRUE_RED(color) << 8),
230 (TRUE_GREEN(color) << 8),
231 (TRUE_BLUE(color) << 8))) / GRAYSTEP;
232 }
233 if (dindex >= GRAYS) /* rounding errors can do this */
234 dindex= GRAYS - 1;
235
236 /* loop for the four Y bits in the dither pattern, putting all
237 * four X bits in at once. if you think this would be hard to
238 * change to be an NxN dithering array, you're right, since we're
239 * banking on the fact that we need only shift the mask based on
240 * whether x is odd or not. an 8x8 array wouldn't even need that,
241 * but blowing an image up by 64x is probably not a feature.
242 */
243
244 if (x & 1)
245 for (a= 0; a < 4; a++, dp2 += dll)
246 *dp2 |= DitherBits[dindex][a];
247 else
248 for (a= 0; a < 4; a++, dp2 += dll)
249 *dp2 |= (DitherBits[dindex][a] << 4);
250 sp += spl;
251 }
252 dp += (dll << 2); /* (dll * 4) but I like shifts */
253 }
254 if (verbose)
255 printf("done\n");
256 return(image);
257 }
258