Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 298 lines (254 sloc) 8.63 kb
5b56b7ec »
2011-05-30 Bam!
1
2 #include <stdio.h>
3 #include <stdlib.h>
c9be566a »
2011-09-24 -d argument
4 #include <string.h>
5b56b7ec »
2011-05-30 Bam!
5 #include <assert.h>
6 #include <math.h>
7 #include "png.h"
8 #include "rwpng.h"
9
38723c61 »
2011-12-13 Static function linkage
10 static void interpolate_palette_front(int palette[], int dither);
986036fb »
2011-12-13 Palette proto
11
5b56b7ec »
2011-05-30 Bam!
12 struct box {
333392f0 »
2011-12-12 Switched to doubles
13 double sum, variance;
14 int start, end;
5b56b7ec »
2011-05-30 Bam!
15 };
16
38723c61 »
2011-12-13 Static function linkage
17 static double weighted_avg(struct box box, double histogram[])
5b56b7ec »
2011-05-30 Bam!
18 {
333392f0 »
2011-12-12 Switched to doubles
19 double weight=0,sum=0;
5b56b7ec »
2011-05-30 Bam!
20 for(int val=box.start; val < box.end; val++) {
21 weight += histogram[val];
22 sum += val*histogram[val];
23 }
24 return weight ? sum/weight : 0.0f;
25 }
26
38723c61 »
2011-12-13 Static function linkage
27 static double variance(struct box box, double histogram[])
5b56b7ec »
2011-05-30 Bam!
28 {
333392f0 »
2011-12-12 Switched to doubles
29 double avg = weighted_avg(box,histogram);
5b56b7ec »
2011-05-30 Bam!
30
333392f0 »
2011-12-12 Switched to doubles
31 double weight=0,sum=0;
5b56b7ec »
2011-05-30 Bam!
32 for(int val=box.start; val < box.end; val++) {
33 weight += histogram[val];
34 sum += (avg-val)*(avg-val)*histogram[val];
35 }
36 return weight ? sum/weight : 0.0f;
37 }
38
38723c61 »
2011-12-13 Static function linkage
39 static double palette_mse(double histogram[], int palette[])
e1432f5e »
2011-12-12 Voronoi iteration
40 {
41 int tmp[256];
42 memcpy(tmp, palette, 256*sizeof(palette[0]));
43 interpolate_palette_front(tmp, 0);
44
45 double mse=0, hist_total=0;
46 for (int i=0; i < 256; i++) {
47 int best = tmp[i];
48 mse += (i-best)*(i-best) * histogram[i];
49
50 hist_total += histogram[i];
51 }
52 return mse / hist_total;
53 }
54
38723c61 »
2011-12-13 Static function linkage
55 static void palette_from_boxes(struct box boxes[], int numboxes, double histogram[], int palette[])
091f163e »
2011-12-12 Extracted palette build
56 {
57 memset(palette, 0, 256*sizeof(palette[0]));
58
59 for(int box=0; box < numboxes; box++) {
60 int value = round(weighted_avg(boxes[box],histogram));
61 palette[value] = value;
62 }
63 }
64
5b56b7ec »
2011-05-30 Bam!
65 /*
66 1-dimensional median cut, using variance for "largest" box
67 */
38723c61 »
2011-12-13 Static function linkage
68 static void reduce(const int maxcolors, double histogram[], int palette[])
5b56b7ec »
2011-05-30 Bam!
69 {
70 int numboxes=1;
71 struct box boxes[256];
72
a498ea87 »
2011-09-24 Formatting
73 boxes[0].start=1; // skip first and last entry, as they're always included
74 boxes[0].end=255;
75 boxes[0].sum=0;
76 for(int i=boxes[0].start; i < boxes[0].end; i++) boxes[0].sum += histogram[i];
5b56b7ec »
2011-05-30 Bam!
77 boxes[0].variance = variance(boxes[0], histogram);
78
77a06ed3 »
2011-12-13 Off by 1
79 while(numboxes < maxcolors) {
5b56b7ec »
2011-05-30 Bam!
80 int boxtosplit=-1;
81 int largest=0;
82 for(int box=0; box < numboxes; box++) {
83 if (boxes[box].variance > largest && (boxes[box].end-boxes[box].start)>=2) {
84 largest = boxes[box].variance;
85 boxtosplit=box;
86 }
87 }
88 if (boxtosplit < 0) {
89 break;
90 }
333392f0 »
2011-12-12 Switched to doubles
91 double sum=0;
5b56b7ec »
2011-05-30 Bam!
92 int val=boxes[boxtosplit].start;
93 for(; val < boxes[boxtosplit].end-1; val++) {
94 sum += histogram[val];
95 if (sum >= boxes[boxtosplit].sum/2.0) {
96 break;
97 }
98 }
99
100 boxes[numboxes].start = boxes[boxtosplit].start;
101 boxes[numboxes].end = val+1;
102 boxes[numboxes].sum = sum;
103 boxes[numboxes].variance = variance(boxes[numboxes], histogram);
104 boxes[boxtosplit].start = val+1;
105 boxes[boxtosplit].sum -= boxes[numboxes].sum;
106 boxes[boxtosplit].variance = variance(boxes[boxtosplit], histogram);
107 numboxes++;
108 }
109
091f163e »
2011-12-12 Extracted palette build
110 palette_from_boxes(boxes, numboxes, histogram, palette);
5b56b7ec »
2011-05-30 Bam!
111 }
112
38723c61 »
2011-12-13 Static function linkage
113 static void remap(read_info img, const int *palette1, const int *palette2)
ccab4569 »
2011-09-24 Extracted remap
114 {
115 for(int i=0; i < img.height; i++) {
7436b185 »
2011-09-24 Remapping with dithering
116 for(int j=0; j < img.width; j++) {
117 int x = j*4;
118 const int *palette = (i^j)&1 ? palette1 : palette2;
119
ccab4569 »
2011-09-24 Extracted remap
120 int a = palette[img.row_pointers[i][x+3]];
121 if (a) {
122 img.row_pointers[i][x] = palette[img.row_pointers[i][x]];
123 img.row_pointers[i][x+1] = palette[img.row_pointers[i][x+1]];
124 img.row_pointers[i][x+2] = palette[img.row_pointers[i][x+2]];
125 img.row_pointers[i][x+3] = a;
126 } else {
127 // clear "dirty alpha"
128 img.row_pointers[i][x] = 0;
129 img.row_pointers[i][x+1] = 0;
130 img.row_pointers[i][x+2] = 0;
131 img.row_pointers[i][x+3] = 0;
132 }
133 }
134 }
135 }
136
38723c61 »
2011-12-13 Static function linkage
137 static void intensity_histogram(read_info img, double histogram[])
7ae46499 »
2011-09-24 Extracted histogram
138 {
139 for(int i=0; i < img.height; i++) {
140 for(int x=0; x < img.width*4; x+=4) {
333392f0 »
2011-12-12 Switched to doubles
141 double a = 1.0-img.row_pointers[i][x+3]/255.0;
7ae46499 »
2011-09-24 Extracted histogram
142 a = 1.0-a*a;
143
144 // opaque colors get more weight
145 histogram[img.row_pointers[i][x]] += a;
146 histogram[img.row_pointers[i][x+1]] += a;
147 histogram[img.row_pointers[i][x+2]] += a;
148 histogram[img.row_pointers[i][x+3]] += 0.9;
149 }
150 }
151 }
152
38723c61 »
2011-12-13 Static function linkage
153 static void interpolate_palette_front(int palette[], int dither)
7436b185 »
2011-09-24 Remapping with dithering
154 {
c2edf113 »
2011-12-12 Split dither function
155 int nextval=0, lastval=0;
c9b503c3 »
2011-12-12 Fixed initialisation
156 palette[0]=0;
157 palette[255]=255; // 0 and 255 are always included
7436b185 »
2011-09-24 Remapping with dithering
158
c2edf113 »
2011-12-12 Split dither function
159 for(int val=0; val < 256; val++) {
7436b185 »
2011-09-24 Remapping with dithering
160 if (palette[val]==val) {
161 lastval = val;
162 for(int j=val+1; j < 256; j++) {
163 if (palette[j]==j) {nextval=j; break;}
164 }
165 }
166 if (!dither) {
167 palette[val] = (val - lastval) < (nextval - val) ? lastval : nextval;
168 } else {
169 palette[val] = (val - lastval)/2 < (nextval - val) ? lastval : nextval;
170 }
171 }
c2edf113 »
2011-12-12 Split dither function
172 }
7436b185 »
2011-09-24 Remapping with dithering
173
38723c61 »
2011-12-13 Static function linkage
174 static void interpolate_palette_back(int palette2[], int dither)
c2edf113 »
2011-12-12 Split dither function
175 {
176 int nextval=255, lastval=255;
c9b503c3 »
2011-12-12 Fixed initialisation
177 palette2[0]=0;
178 palette2[255]=255; // 0 and 255 are always included
179
c2edf113 »
2011-12-12 Split dither function
180 for(int val=255; val >=0; val--) {
7436b185 »
2011-09-24 Remapping with dithering
181 if (palette2[val]==val) {
182 lastval = val;
183 for(int j=val-1; j >= 0; j--) {
184 if (palette2[j]==j) {nextval=j; break;}
185 }
186 }
187 if (!dither) {
188 palette2[val] = (val - lastval) >= (nextval - val) ? lastval : nextval;
189 } else {
190 palette2[val] = (val - lastval)/2 >= (nextval - val) ? lastval : nextval;
191 }
192 }
193 }
194
38723c61 »
2011-12-13 Static function linkage
195 static void dither_palette(int palette[], int palette2[], int dither)
c2edf113 »
2011-12-12 Split dither function
196 {
197 memcpy(palette2, palette, sizeof(int)*256);
198
199 // front to back. When dithering, it's biased towards nextval
200 interpolate_palette_front(palette, dither);
201
202 // back to front, so dithering bias is the other way.
203 interpolate_palette_back(palette2, dither);
204 }
205
38723c61 »
2011-12-13 Static function linkage
206 static void usage(const char *exepath)
c9be566a »
2011-09-24 -d argument
207 {
208 const char *name = strrchr(exepath, '/');
209 if (name) name++; else name = exepath;
63663101 »
2011-12-12 Version bump
210 fprintf(stderr, "Median Cut PNG Posterizer 1.2 (2011).\n" \
c9be566a »
2011-09-24 -d argument
211 "Usage: %s [-d] levels\n\n" \
212 "Specify number of levels 2-255 as an argument. -d enables dithering\n" \
213 "Image is always read from stdin and written to stdout.\n"
214 "%s -d 16 < in.png > out.png\n", name, name);
215 }
216
38723c61 »
2011-12-13 Static function linkage
217 static void voronoi(double histogram[], int palette[])
e1432f5e »
2011-12-12 Voronoi iteration
218 {
219 interpolate_palette_front(palette, 0);
220
221 double counts[256] = {0};
222 double sums[256] = {0};
223
224 // remap palette
225 for (int i=0; i < 256; i++) {
226 int best = palette[i];
227 counts[best] += histogram[i];
228 sums[best] += histogram[i] * (double)i;
229 }
230
231 memset(palette, 0, 256*sizeof(palette[0]));
232
233 // rebuild palette from remapped averages
234 for(int i=0; i < 256; i++) {
235 if (counts[i]) {
236 int value = round(sums[i]/counts[i]);
237 palette[value] = value;
238 }
239 }
240 }
241
5b56b7ec »
2011-05-30 Bam!
242 int main(int argc, char *argv[])
243 {
c9be566a »
2011-09-24 -d argument
244 int argn=1;
7436b185 »
2011-09-24 Remapping with dithering
245 int dither=0;
c9be566a »
2011-09-24 -d argument
246 if (argc==3 && 0==strcmp("-d", argv[1])) {
247 dither=1;
248 argn++;
249 }
250 int maxcolors=0;
251 if (argc==(argn+1)) {
252 maxcolors=atoi(argv[argn]);
253 argn++;
254 }
5b56b7ec »
2011-05-30 Bam!
255
c9be566a »
2011-09-24 -d argument
256 if (argc != argn || maxcolors < 2 || maxcolors > 255) {
257 usage(argv[0]);
5b56b7ec »
2011-05-30 Bam!
258 return 1;
259 }
260
261 read_info img;
4357b571 »
2011-09-24 IO error handling
262 pngquant_error retval;
263 if ((retval = rwpng_read_image(stdin, &img))) {
5b56b7ec »
2011-05-30 Bam!
264 fprintf(stderr, "Error: cannot read PNG from stdin\n");
4357b571 »
2011-09-24 IO error handling
265 return retval;
5b56b7ec »
2011-05-30 Bam!
266 }
267
333392f0 »
2011-12-12 Switched to doubles
268 double histogram[256]={0};
7ae46499 »
2011-09-24 Extracted histogram
269 intensity_histogram(img, histogram);
5b56b7ec »
2011-05-30 Bam!
270
97313d91 »
2011-09-24 Reserved black and white
271 // reserve colors for black and white
f38c74ae »
2011-12-13 Removed 0 and 255 from histogram
272 // and omit them from histogram to avoid confusing median cut
273 if (histogram[0] && maxcolors>2) {maxcolors--; histogram[0]=0;}
274 if (histogram[255] && maxcolors>2) {maxcolors--; histogram[255]=0;}
97313d91 »
2011-09-24 Reserved black and white
275
091f163e »
2011-12-12 Extracted palette build
276 int palette[256], palette2[256];
5b56b7ec »
2011-05-30 Bam!
277 reduce(maxcolors, histogram, palette);
278
e1432f5e »
2011-12-12 Voronoi iteration
279 double last_mse = INFINITY;
280 for(int j=0; j < 100; j++) {
281 voronoi(histogram, palette);
282 double new_mse = palette_mse(histogram, palette);
283 if (new_mse == last_mse) break;
284 last_mse = new_mse;
285 }
286
7436b185 »
2011-09-24 Remapping with dithering
287 dither_palette(palette, palette2, dither);
6828c027 »
2011-09-24 Moved palette code
288
7436b185 »
2011-09-24 Remapping with dithering
289 remap(img, palette, palette2);
ccab4569 »
2011-09-24 Extracted remap
290
4357b571 »
2011-09-24 IO error handling
291 if ((retval = rwpng_write_image_init(stdout, &img)) ||
292 (retval = rwpng_write_image_whole(&img))) {
293 fprintf(stderr, "Error: cannot write PNG to stdout\n");
294 return retval;
295 }
5b56b7ec »
2011-05-30 Bam!
296
297 return 0;
298 }
Something went wrong with that request. Please try again.