1
2 #include "libimagequant.h"
3 #include "pam.h"
4 #include "nearest.h"
5 #include "mempool.h"
6 #include <stdlib.h>
7
8 struct sorttmp
9 {
10 float radius;
11 unsigned int index;
12 };
13
14 struct head
15 {
16 // colors less than radius away from vantage_point color will have best match in candidates
17 f_pixel vantage_point;
18 float radius;
19 unsigned int num_candidates;
20 f_pixel *candidates_color;
21 unsigned short *candidates_index;
22 };
23
24 struct nearest_map
25 {
26 const colormap *map;
27 float nearest_other_color_dist[256];
28 mempool mempool;
29 struct head heads[];
30 };
31
32 static float
distance_from_nearest_other_color(const colormap * map,const unsigned int i)33 distance_from_nearest_other_color (const colormap * map, const unsigned int i)
34 {
35 float second_best = MAX_DIFF;
36 for (unsigned int j = 0; j < map->colors; j++) {
37 float diff;
38
39 if (i == j)
40 continue;
41
42 diff = colordifference (map->palette[i].acolor, map->palette[j].acolor);
43 if (diff <= second_best) {
44 second_best = diff;
45 }
46 }
47 return second_best;
48 }
49
50 static int
compareradius(const void * ap,const void * bp)51 compareradius (const void *ap, const void *bp)
52 {
53 float a = ((const struct sorttmp *) ap)->radius;
54 float b = ((const struct sorttmp *) bp)->radius;
55 return a > b ? 1 : (a < b ? -1 : 0);
56 }
57
58 static struct head
build_head(f_pixel px,const colormap * map,unsigned int num_candidates,mempool * m,float error_margin,bool skip_index[],unsigned int * skipped)59 build_head (f_pixel px, const colormap * map, unsigned int num_candidates,
60 mempool * m, float error_margin, bool skip_index[], unsigned int *skipped)
61 {
62 struct sorttmp *colors = g_alloca (sizeof (struct sorttmp) * map->colors);
63 unsigned int colorsused, i;
64 struct head h;
65
66 colorsused = 0;
67
68 for (i = 0; i < map->colors; i++) {
69 if (skip_index[i])
70 continue; // colors in skip_index have been eliminated already in previous heads
71 colors[colorsused].index = i;
72 colors[colorsused].radius = colordifference (px, map->palette[i].acolor);
73 colorsused++;
74 }
75
76 qsort (colors, colorsused, sizeof (colors[0]), compareradius);
77 assert (colorsused < 2 || colors[0].radius <= colors[1].radius); // closest first
78
79 num_candidates = MIN (colorsused, num_candidates);
80
81 h.candidates_color =
82 mempool_alloc (m, num_candidates * sizeof (h.candidates_color[0]), 0);
83 h.candidates_index =
84 mempool_alloc (m, num_candidates * sizeof (h.candidates_index[0]), 0);
85 h.vantage_point = px;
86 h.num_candidates = num_candidates;
87
88 for (i = 0; i < num_candidates; i++) {
89 h.candidates_color[i] = map->palette[colors[i].index].acolor;
90 h.candidates_index[i] = colors[i].index;
91 }
92 // if all colors within this radius are included in candidates, then there cannot be any other better match
93 // farther away from the vantage point than half of the radius. Due to alpha channel must assume pessimistic radius.
94 h.radius = min_colordifference (px, h.candidates_color[num_candidates - 1]) / 4.0f; // /4 = half of radius, but radius is squared
95
96 for (i = 0; i < num_candidates; i++) {
97 // divide again as that's matching certain subset within radius-limited subset
98 // - 1/256 is a tolerance for miscalculation (seems like colordifference isn't exact)
99 if (colors[i].radius < h.radius / 4.f - error_margin) {
100 skip_index[colors[i].index] = true;
101 (*skipped)++;
102 }
103 }
104 return h;
105 }
106
107 static colormap *
get_subset_palette(const colormap * map)108 get_subset_palette (const colormap * map)
109 {
110 unsigned int subset_size, i;
111 colormap *subset_palette;
112
113 if (map->subset_palette) {
114 return map->subset_palette;
115 }
116
117 subset_size = (map->colors + 3) / 4;
118 subset_palette = pam_colormap (subset_size, map->malloc, map->free);
119
120 for (i = 0; i < subset_size; i++) {
121 subset_palette->palette[i] = map->palette[i];
122 }
123
124 return subset_palette;
125 }
126
127 LIQ_PRIVATE struct nearest_map *
nearest_init(const colormap * map,bool fast)128 nearest_init (const colormap * map, bool fast)
129 {
130 colormap *subset_palette = get_subset_palette (map);
131 const unsigned int num_vantage_points =
132 map->colors > 16 ? MIN (map->colors / (fast ? 4 : 3),
133 subset_palette->colors) : 0;
134 const unsigned long heads_size = sizeof (struct head) * (num_vantage_points + 1); // +1 is fallback head
135
136 const unsigned long mempool_size =
137 (sizeof (f_pixel) +
138 sizeof (unsigned int)) * subset_palette->colors * map->colors / 5 +
139 (1 << 14);
140 mempool m = NULL;
141 struct nearest_map *centroids = mempool_create (&m,
142 sizeof (*centroids) + heads_size /* heads array is appended to it */ ,
143 mempool_size, map->malloc, map->free);
144 unsigned int skipped;
145 const float error_margin = fast ? 0 : 8.f / 256.f / 256.f;
146 unsigned int h, i, j;
147 bool *skip_index;
148
149 centroids->mempool = m;
150
151 for (i = 0; i < map->colors; i++) {
152 const float dist = distance_from_nearest_other_color (map, i);
153 centroids->nearest_other_color_dist[i] = dist / 4.f; // half of squared distance
154 }
155
156 centroids->map = map;
157
158 skipped = 0;
159 assert (map->colors > 0);
160
161 skip_index = g_alloca (sizeof (bool) * map->colors);
162
163 for (j = 0; j < map->colors; j++)
164 skip_index[j] = false;
165
166 // floats and colordifference calculations are not perfect
167 for (h = 0; h < num_vantage_points; h++) {
168 unsigned int num_candiadtes =
169 1 + (map->colors - skipped) / ((1 + num_vantage_points - h) / 2);
170
171 centroids->heads[h] =
172 build_head (subset_palette->palette[h].acolor, map, num_candiadtes,
173 ¢roids->mempool, error_margin, skip_index, &skipped);
174 if (centroids->heads[h].num_candidates == 0) {
175 break;
176 }
177 }
178
179 // assumption that there is no better color within radius of vantage point color
180 // holds true only for colors within convex hull formed by palette colors.
181 // The fallback must contain all colors, since there are too many edge cases to cover.
182 if (!fast)
183 for (j = 0; j < map->colors; j++) {
184 skip_index[j] = false;
185 }
186
187 centroids->heads[h] = build_head ((f_pixel) {
188 0, 0, 0, 0}
189 , map, map->colors, ¢roids->mempool, error_margin,
190 skip_index, &skipped);
191 centroids->heads[h].radius = MAX_DIFF;
192
193 // get_subset_palette could have created a copy
194 if (subset_palette != map->subset_palette) {
195 pam_freecolormap (subset_palette);
196 }
197
198 return centroids;
199 }
200
201 LIQ_PRIVATE unsigned int
nearest_search(const struct nearest_map * centroids,const f_pixel px,int likely_colormap_index,const float min_opaque_val,float * diff)202 nearest_search (const struct nearest_map *centroids, const f_pixel px,
203 int likely_colormap_index, const float min_opaque_val, float *diff)
204 {
205 const bool iebug = px.a > min_opaque_val;
206 const struct head *const heads = centroids->heads;
207 float guess_diff;
208 unsigned int i;
209
210 assert (likely_colormap_index < centroids->map->colors);
211
212 guess_diff =
213 colordifference (centroids->map->palette[likely_colormap_index].acolor,
214 px);
215 if (guess_diff < centroids->nearest_other_color_dist[likely_colormap_index]) {
216 if (diff)
217 *diff = guess_diff;
218 return likely_colormap_index;
219 }
220
221 for (i = 0; /* last head will always be selected */ ; i++) {
222 float vantage_point_dist = colordifference (px, heads[i].vantage_point);
223
224 if (vantage_point_dist <= heads[i].radius) {
225 unsigned int ind = 0;
226 float dist;
227
228 assert (heads[i].num_candidates);
229
230 dist = colordifference (px, heads[i].candidates_color[0]);
231
232 /* penalty for making holes in IE */
233 if (iebug && heads[i].candidates_color[0].a < 1) {
234 dist += 1.f / 1024.f;
235 }
236
237 for (unsigned int j = 1; j < heads[i].num_candidates; j++) {
238 float newdist = colordifference (px, heads[i].candidates_color[j]);
239
240 /* penalty for making holes in IE */
241 if (iebug && heads[i].candidates_color[j].a < 1) {
242 newdist += 1.f / 1024.f;
243 }
244
245 if (newdist < dist) {
246 dist = newdist;
247 ind = j;
248 }
249 }
250 if (diff)
251 *diff = dist;
252 return heads[i].candidates_index[ind];
253 }
254 }
255 }
256
257 LIQ_PRIVATE void
nearest_free(struct nearest_map * centroids)258 nearest_free (struct nearest_map *centroids)
259 {
260 mempool_destroy (centroids->mempool);
261 }
262