Line | Branch | Exec | Source |
---|---|---|---|
1 | /* | ||
2 | * Copyright (c) 2015 Stupeflix | ||
3 | * Copyright (c) 2022 Clément Bœsch <u pkh me> | ||
4 | * | ||
5 | * This file is part of FFmpeg. | ||
6 | * | ||
7 | * FFmpeg is free software; you can redistribute it and/or | ||
8 | * modify it under the terms of the GNU Lesser General Public | ||
9 | * License as published by the Free Software Foundation; either | ||
10 | * version 2.1 of the License, or (at your option) any later version. | ||
11 | * | ||
12 | * FFmpeg is distributed in the hope that it will be useful, | ||
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
15 | * Lesser General Public License for more details. | ||
16 | * | ||
17 | * You should have received a copy of the GNU Lesser General Public | ||
18 | * License along with FFmpeg; if not, write to the Free Software | ||
19 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | ||
20 | */ | ||
21 | |||
22 | /** | ||
23 | * @file | ||
24 | * Generate one palette for a whole video stream. | ||
25 | */ | ||
26 | |||
27 | #include "libavutil/avassert.h" | ||
28 | #include "libavutil/internal.h" | ||
29 | #include "libavutil/mem.h" | ||
30 | #include "libavutil/opt.h" | ||
31 | #include "libavutil/intreadwrite.h" | ||
32 | #include "avfilter.h" | ||
33 | #include "formats.h" | ||
34 | #include "internal.h" | ||
35 | #include "palette.h" | ||
36 | #include "video.h" | ||
37 | |||
38 | /* Reference a color and how much it's used */ | ||
39 | struct color_ref { | ||
40 | uint32_t color; | ||
41 | struct Lab lab; | ||
42 | int64_t count; | ||
43 | }; | ||
44 | |||
45 | /* Store a range of colors */ | ||
46 | struct range_box { | ||
47 | uint32_t color; // average color | ||
48 | struct Lab avg; // average color in perceptual OkLab space | ||
49 | int major_axis; // best axis candidate for cutting the box | ||
50 | int64_t weight; // sum of all the weights of the colors | ||
51 | int64_t cut_score; // how likely the box is to be cut down (higher implying more likely) | ||
52 | int start; // index in PaletteGenContext->refs | ||
53 | int len; // number of referenced colors | ||
54 | int sorted_by; // whether range of colors is sorted by red (0), green (1) or blue (2) | ||
55 | }; | ||
56 | |||
57 | struct hist_node { | ||
58 | struct color_ref *entries; | ||
59 | int nb_entries; | ||
60 | }; | ||
61 | |||
62 | enum { | ||
63 | STATS_MODE_ALL_FRAMES, | ||
64 | STATS_MODE_DIFF_FRAMES, | ||
65 | STATS_MODE_SINGLE_FRAMES, | ||
66 | NB_STATS_MODE | ||
67 | }; | ||
68 | |||
69 | #define HIST_SIZE (1<<15) | ||
70 | |||
71 | typedef struct PaletteGenContext { | ||
72 | const AVClass *class; | ||
73 | |||
74 | int max_colors; | ||
75 | int reserve_transparent; | ||
76 | int stats_mode; | ||
77 | |||
78 | AVFrame *prev_frame; // previous frame used for the diff stats_mode | ||
79 | struct hist_node histogram[HIST_SIZE]; // histogram/hashtable of the colors | ||
80 | struct color_ref **refs; // references of all the colors used in the stream | ||
81 | int nb_refs; // number of color references (or number of different colors) | ||
82 | struct range_box boxes[256]; // define the segmentation of the colorspace (the final palette) | ||
83 | int nb_boxes; // number of boxes (increase will segmenting them) | ||
84 | int palette_pushed; // if the palette frame is pushed into the outlink or not | ||
85 | uint8_t transparency_color[4]; // background color for transparency | ||
86 | } PaletteGenContext; | ||
87 | |||
88 | #define OFFSET(x) offsetof(PaletteGenContext, x) | ||
89 | #define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM | ||
90 | static const AVOption palettegen_options[] = { | ||
91 | { "max_colors", "set the maximum number of colors to use in the palette", OFFSET(max_colors), AV_OPT_TYPE_INT, {.i64=256}, 2, 256, FLAGS }, | ||
92 | { "reserve_transparent", "reserve a palette entry for transparency", OFFSET(reserve_transparent), AV_OPT_TYPE_BOOL, {.i64=1}, 0, 1, FLAGS }, | ||
93 | { "transparency_color", "set a background color for transparency", OFFSET(transparency_color), AV_OPT_TYPE_COLOR, {.str="lime"}, 0, 0, FLAGS }, | ||
94 | { "stats_mode", "set statistics mode", OFFSET(stats_mode), AV_OPT_TYPE_INT, {.i64=STATS_MODE_ALL_FRAMES}, 0, NB_STATS_MODE-1, FLAGS, .unit = "mode" }, | ||
95 | { "full", "compute full frame histograms", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_ALL_FRAMES}, INT_MIN, INT_MAX, FLAGS, .unit = "mode" }, | ||
96 | { "diff", "compute histograms only for the part that differs from previous frame", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_DIFF_FRAMES}, INT_MIN, INT_MAX, FLAGS, .unit = "mode" }, | ||
97 | { "single", "compute new histogram for each frame", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_SINGLE_FRAMES}, INT_MIN, INT_MAX, FLAGS, .unit = "mode" }, | ||
98 | { NULL } | ||
99 | }; | ||
100 | |||
101 | AVFILTER_DEFINE_CLASS(palettegen); | ||
102 | |||
103 | 2 | static int query_formats(AVFilterContext *ctx) | |
104 | { | ||
105 | static const enum AVPixelFormat in_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE}; | ||
106 | static const enum AVPixelFormat out_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE}; | ||
107 | int ret; | ||
108 | |||
109 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
|
2 | if ((ret = ff_formats_ref(ff_make_format_list(in_fmts) , &ctx->inputs[0]->outcfg.formats)) < 0) |
110 | ✗ | return ret; | |
111 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
|
2 | if ((ret = ff_formats_ref(ff_make_format_list(out_fmts), &ctx->outputs[0]->incfg.formats)) < 0) |
112 | ✗ | return ret; | |
113 | 2 | return 0; | |
114 | } | ||
115 | |||
116 | typedef int (*cmp_func)(const void *, const void *); | ||
117 | |||
118 | #define DECLARE_CMP_FUNC(k0, k1, k2) \ | ||
119 | static int cmp_##k0##k1##k2(const void *pa, const void *pb) \ | ||
120 | { \ | ||
121 | const struct color_ref * const *a = pa; \ | ||
122 | const struct color_ref * const *b = pb; \ | ||
123 | const int c0 = FFDIFFSIGN((*a)->lab.k0, (*b)->lab.k0); \ | ||
124 | const int c1 = FFDIFFSIGN((*a)->lab.k1, (*b)->lab.k1); \ | ||
125 | const int c2 = FFDIFFSIGN((*a)->lab.k2, (*b)->lab.k2); \ | ||
126 | return c0 ? c0 : c1 ? c1 : c2; \ | ||
127 | } | ||
128 | |||
129 |
4/4✓ Branch 0 taken 19743 times.
✓ Branch 1 taken 872344 times.
✓ Branch 2 taken 19711 times.
✓ Branch 3 taken 32 times.
|
892087 | DECLARE_CMP_FUNC(L, a, b) |
130 |
4/4✓ Branch 0 taken 14185 times.
✓ Branch 1 taken 385091 times.
✓ Branch 2 taken 14183 times.
✓ Branch 3 taken 2 times.
|
399276 | DECLARE_CMP_FUNC(L, b, a) |
131 |
4/4✓ Branch 0 taken 2244 times.
✓ Branch 1 taken 127244 times.
✓ Branch 2 taken 2240 times.
✓ Branch 3 taken 4 times.
|
129488 | DECLARE_CMP_FUNC(a, L, b) |
132 |
4/4✓ Branch 0 taken 3596 times.
✓ Branch 1 taken 221279 times.
✓ Branch 2 taken 2886 times.
✓ Branch 3 taken 710 times.
|
224875 | DECLARE_CMP_FUNC(a, b, L) |
133 |
3/4✓ Branch 0 taken 3083 times.
✓ Branch 1 taken 91466 times.
✓ Branch 2 taken 3083 times.
✗ Branch 3 not taken.
|
94549 | DECLARE_CMP_FUNC(b, L, a) |
134 |
4/4✓ Branch 0 taken 9979 times.
✓ Branch 1 taken 319698 times.
✓ Branch 2 taken 9052 times.
✓ Branch 3 taken 927 times.
|
329677 | DECLARE_CMP_FUNC(b, a, L) |
135 | |||
136 | enum { ID_XYZ, ID_XZY, ID_ZXY, ID_YXZ, ID_ZYX, ID_YZX }; | ||
137 | static const char * const sortstr[] = { "Lab", "Lba", "bLa", "aLb", "baL", "abL" }; | ||
138 | |||
139 | static const cmp_func cmp_funcs[] = { | ||
140 | [ID_XYZ] = cmp_Lab, | ||
141 | [ID_XZY] = cmp_Lba, | ||
142 | [ID_ZXY] = cmp_bLa, | ||
143 | [ID_YXZ] = cmp_aLb, | ||
144 | [ID_ZYX] = cmp_baL, | ||
145 | [ID_YZX] = cmp_abL, | ||
146 | }; | ||
147 | |||
148 | /* | ||
149 | * Return an identifier for the order of x, y, z (from higher to lower), | ||
150 | * preferring x over y and y over z in case of equality. | ||
151 | */ | ||
152 | 764 | static int sort3id(int64_t x, int64_t y, int64_t z) | |
153 | { | ||
154 |
2/2✓ Branch 0 taken 400 times.
✓ Branch 1 taken 364 times.
|
764 | if (x >= y) { |
155 |
2/2✓ Branch 0 taken 209 times.
✓ Branch 1 taken 191 times.
|
400 | if (y >= z) return ID_XYZ; |
156 |
2/2✓ Branch 0 taken 130 times.
✓ Branch 1 taken 61 times.
|
191 | if (x >= z) return ID_XZY; |
157 | 61 | return ID_ZXY; | |
158 | } | ||
159 |
2/2✓ Branch 0 taken 118 times.
✓ Branch 1 taken 246 times.
|
364 | if (x >= z) return ID_YXZ; |
160 |
2/2✓ Branch 0 taken 138 times.
✓ Branch 1 taken 108 times.
|
246 | if (y >= z) return ID_YZX; |
161 | 108 | return ID_ZYX; | |
162 | } | ||
163 | |||
164 | /** | ||
165 | * Simple color comparison for sorting the final palette | ||
166 | */ | ||
167 | 2462 | static int cmp_color(const void *a, const void *b) | |
168 | { | ||
169 | 2462 | const struct range_box *box1 = a; | |
170 | 2462 | const struct range_box *box2 = b; | |
171 | 2462 | return FFDIFFSIGN(box1->color, box2->color); | |
172 | } | ||
173 | |||
174 | 764 | static void compute_box_stats(PaletteGenContext *s, struct range_box *box) | |
175 | { | ||
176 | 764 | int64_t er2[3] = {0}; | |
177 | |||
178 | /* Compute average color */ | ||
179 | 764 | int64_t sL = 0, sa = 0, sb = 0; | |
180 | 764 | box->weight = 0; | |
181 |
2/2✓ Branch 0 taken 418470 times.
✓ Branch 1 taken 764 times.
|
419234 | for (int i = box->start; i < box->start + box->len; i++) { |
182 | 418470 | const struct color_ref *ref = s->refs[i]; | |
183 | 418470 | sL += ref->lab.L * ref->count; | |
184 | 418470 | sa += ref->lab.a * ref->count; | |
185 | 418470 | sb += ref->lab.b * ref->count; | |
186 | 418470 | box->weight += ref->count; | |
187 | } | ||
188 | 764 | box->avg.L = sL / box->weight; | |
189 | 764 | box->avg.a = sa / box->weight; | |
190 | 764 | box->avg.b = sb / box->weight; | |
191 | |||
192 | /* Compute squared error of each color channel */ | ||
193 |
2/2✓ Branch 0 taken 418470 times.
✓ Branch 1 taken 764 times.
|
419234 | for (int i = box->start; i < box->start + box->len; i++) { |
194 | 418470 | const struct color_ref *ref = s->refs[i]; | |
195 | 418470 | const int64_t dL = ref->lab.L - box->avg.L; | |
196 | 418470 | const int64_t da = ref->lab.a - box->avg.a; | |
197 | 418470 | const int64_t db = ref->lab.b - box->avg.b; | |
198 | 418470 | er2[0] += dL * dL * ref->count; | |
199 | 418470 | er2[1] += da * da * ref->count; | |
200 | 418470 | er2[2] += db * db * ref->count; | |
201 | } | ||
202 | |||
203 | /* Define the best axis candidate for cutting the box */ | ||
204 | 764 | box->major_axis = sort3id(er2[0], er2[1], er2[2]); | |
205 | |||
206 | /* The box that has the axis with the biggest error amongst all boxes will but cut down */ | ||
207 | 764 | box->cut_score = FFMAX3(er2[0], er2[1], er2[2]); | |
208 | 764 | } | |
209 | |||
210 | /** | ||
211 | * Find the next box to split: pick the one with the highest cut score | ||
212 | */ | ||
213 | 381 | static int get_next_box_id_to_split(PaletteGenContext *s) | |
214 | { | ||
215 | 381 | int best_box_id = -1; | |
216 | 381 | int64_t max_score = -1; | |
217 | |||
218 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 379 times.
|
381 | if (s->nb_boxes == s->max_colors - s->reserve_transparent) |
219 | 2 | return -1; | |
220 | |||
221 |
2/2✓ Branch 0 taken 40511 times.
✓ Branch 1 taken 379 times.
|
40890 | for (int box_id = 0; box_id < s->nb_boxes; box_id++) { |
222 | 40511 | const struct range_box *box = &s->boxes[box_id]; | |
223 |
3/4✓ Branch 0 taken 40511 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1490 times.
✓ Branch 3 taken 39021 times.
|
40511 | if (s->boxes[box_id].len >= 2 && box->cut_score > max_score) { |
224 | 1490 | best_box_id = box_id; | |
225 | 1490 | max_score = box->cut_score; | |
226 | } | ||
227 | } | ||
228 | 379 | return best_box_id; | |
229 | } | ||
230 | |||
231 | /** | ||
232 | * Split given box in two at position n. The original box becomes the left part | ||
233 | * of the split, and the new index box is the right part. | ||
234 | */ | ||
235 | 381 | static void split_box(PaletteGenContext *s, struct range_box *box, int n) | |
236 | { | ||
237 | 381 | struct range_box *new_box = &s->boxes[s->nb_boxes++]; | |
238 | 381 | new_box->start = n + 1; | |
239 | 381 | new_box->len = box->start + box->len - new_box->start; | |
240 | 381 | new_box->sorted_by = box->sorted_by; | |
241 | 381 | box->len -= new_box->len; | |
242 | |||
243 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 381 times.
|
381 | av_assert0(box->len >= 1); |
244 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 381 times.
|
381 | av_assert0(new_box->len >= 1); |
245 | |||
246 | 381 | compute_box_stats(s, box); | |
247 | 381 | compute_box_stats(s, new_box); | |
248 | 381 | } | |
249 | |||
250 | /** | ||
251 | * Write the palette into the output frame. | ||
252 | */ | ||
253 | 2 | static void write_palette(AVFilterContext *ctx, AVFrame *out) | |
254 | { | ||
255 | 2 | const PaletteGenContext *s = ctx->priv; | |
256 | 2 | int box_id = 0; | |
257 | 2 | uint32_t *pal = (uint32_t *)out->data[0]; | |
258 | 2 | const int pal_linesize = out->linesize[0] >> 2; | |
259 | 2 | uint32_t last_color = 0; | |
260 | |||
261 |
2/2✓ Branch 0 taken 32 times.
✓ Branch 1 taken 2 times.
|
34 | for (int y = 0; y < out->height; y++) { |
262 |
2/2✓ Branch 0 taken 512 times.
✓ Branch 1 taken 32 times.
|
544 | for (int x = 0; x < out->width; x++) { |
263 |
2/2✓ Branch 0 taken 383 times.
✓ Branch 1 taken 129 times.
|
512 | if (box_id < s->nb_boxes) { |
264 | 383 | pal[x] = s->boxes[box_id++].color; | |
265 |
5/6✓ Branch 0 taken 24 times.
✓ Branch 1 taken 359 times.
✓ Branch 2 taken 22 times.
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 381 times.
|
383 | if ((x || y) && pal[x] == last_color) |
266 | ✗ | av_log(ctx, AV_LOG_WARNING, "Duped color: %08"PRIX32"\n", pal[x]); | |
267 | 383 | last_color = pal[x]; | |
268 | } else { | ||
269 | 129 | pal[x] = last_color; // pad with last color | |
270 | } | ||
271 | } | ||
272 | 32 | pal += pal_linesize; | |
273 | } | ||
274 | |||
275 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
|
2 | if (s->reserve_transparent) { |
276 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
|
1 | av_assert0(s->nb_boxes < 256); |
277 | 1 | pal[out->width - pal_linesize - 1] = AV_RB32(&s->transparency_color) >> 8; | |
278 | } | ||
279 | 2 | } | |
280 | |||
281 | /** | ||
282 | * Crawl the histogram to get all the defined colors, and create a linear list | ||
283 | * of them (each color reference entry is a pointer to the value in the | ||
284 | * histogram/hash table). | ||
285 | */ | ||
286 | 2 | static struct color_ref **load_color_refs(const struct hist_node *hist, int nb_refs) | |
287 | { | ||
288 | 2 | int k = 0; | |
289 | 2 | struct color_ref **refs = av_malloc_array(nb_refs, sizeof(*refs)); | |
290 | |||
291 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
|
2 | if (!refs) |
292 | ✗ | return NULL; | |
293 | |||
294 |
2/2✓ Branch 0 taken 65536 times.
✓ Branch 1 taken 2 times.
|
65538 | for (int j = 0; j < HIST_SIZE; j++) { |
295 | 65536 | const struct hist_node *node = &hist[j]; | |
296 | |||
297 |
2/2✓ Branch 0 taken 44830 times.
✓ Branch 1 taken 65536 times.
|
110366 | for (int i = 0; i < node->nb_entries; i++) |
298 | 44830 | refs[k++] = &node->entries[i]; | |
299 | } | ||
300 | |||
301 | 2 | return refs; | |
302 | } | ||
303 | |||
304 | 2 | static double set_colorquant_ratio_meta(AVFrame *out, int nb_out, int nb_in) | |
305 | { | ||
306 | char buf[32]; | ||
307 | 2 | const double ratio = (double)nb_out / nb_in; | |
308 | 2 | snprintf(buf, sizeof(buf), "%f", ratio); | |
309 | 2 | av_dict_set(&out->metadata, "lavfi.color_quant_ratio", buf, 0); | |
310 | 2 | return ratio; | |
311 | } | ||
312 | |||
313 | /** | ||
314 | * Main function implementing the Median Cut Algorithm defined by Paul Heckbert | ||
315 | * in Color Image Quantization for Frame Buffer Display (1982) | ||
316 | */ | ||
317 | 2 | static AVFrame *get_palette_frame(AVFilterContext *ctx) | |
318 | { | ||
319 | AVFrame *out; | ||
320 | 2 | PaletteGenContext *s = ctx->priv; | |
321 | 2 | AVFilterLink *outlink = ctx->outputs[0]; | |
322 | double ratio; | ||
323 | 2 | int box_id = 0; | |
324 | struct range_box *box; | ||
325 | |||
326 | /* reference only the used colors from histogram */ | ||
327 | 2 | s->refs = load_color_refs(s->histogram, s->nb_refs); | |
328 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
|
2 | if (!s->refs) { |
329 | ✗ | av_log(ctx, AV_LOG_ERROR, "Unable to allocate references for %d different colors\n", s->nb_refs); | |
330 | ✗ | return NULL; | |
331 | } | ||
332 | |||
333 | /* create the palette frame */ | ||
334 | 2 | out = ff_get_video_buffer(outlink, outlink->w, outlink->h); | |
335 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
|
2 | if (!out) |
336 | ✗ | return NULL; | |
337 | 2 | out->pts = 0; | |
338 | |||
339 | /* set first box for 0..nb_refs */ | ||
340 | 2 | box = &s->boxes[box_id]; | |
341 | 2 | box->len = s->nb_refs; | |
342 | 2 | box->sorted_by = -1; | |
343 | 2 | compute_box_stats(s, box); | |
344 | 2 | s->nb_boxes = 1; | |
345 | |||
346 |
3/4✓ Branch 0 taken 381 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 381 times.
✗ Branch 3 not taken.
|
383 | while (box && box->len > 1) { |
347 | int i; | ||
348 | int64_t median, weight; | ||
349 | |||
350 | ff_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" sort by %s (already sorted:%c) ", | ||
351 | box_id, box->start, box->start + box->len - 1, box->len, box->weight, | ||
352 | sortstr[box->major_axis], box->sorted_by == box->major_axis ? 'y':'n'); | ||
353 | |||
354 | /* sort the range by its major axis if it's not already sorted */ | ||
355 |
2/2✓ Branch 0 taken 248 times.
✓ Branch 1 taken 133 times.
|
381 | if (box->sorted_by != box->major_axis) { |
356 | 248 | cmp_func cmpf = cmp_funcs[box->major_axis]; | |
357 | 248 | qsort(&s->refs[box->start], box->len, sizeof(struct color_ref *), cmpf); | |
358 | 248 | box->sorted_by = box->major_axis; | |
359 | } | ||
360 | |||
361 | /* locate the median where to split */ | ||
362 | 381 | median = (box->weight + 1) >> 1; | |
363 | 381 | weight = 0; | |
364 | /* if you have 2 boxes, the maximum is actually #0: you must have at | ||
365 | * least 1 color on each side of the split, hence the -2 */ | ||
366 |
1/2✓ Branch 0 taken 200876 times.
✗ Branch 1 not taken.
|
200876 | for (i = box->start; i < box->start + box->len - 2; i++) { |
367 | 200876 | weight += s->refs[i]->count; | |
368 |
2/2✓ Branch 0 taken 381 times.
✓ Branch 1 taken 200495 times.
|
200876 | if (weight > median) |
369 | 381 | break; | |
370 | } | ||
371 | ff_dlog(ctx, "split @ i=%-6d with w=%-6"PRIu64" (target=%6"PRIu64")\n", i, weight, median); | ||
372 | 381 | split_box(s, box, i); | |
373 | |||
374 | 381 | box_id = get_next_box_id_to_split(s); | |
375 |
2/2✓ Branch 0 taken 379 times.
✓ Branch 1 taken 2 times.
|
381 | box = box_id >= 0 ? &s->boxes[box_id] : NULL; |
376 | } | ||
377 | |||
378 | 2 | ratio = set_colorquant_ratio_meta(out, s->nb_boxes, s->nb_refs); | |
379 | 2 | av_log(ctx, AV_LOG_INFO, "%d%s colors generated out of %d colors; ratio=%f\n", | |
380 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
|
2 | s->nb_boxes, s->reserve_transparent ? "(+1)" : "", s->nb_refs, ratio); |
381 | |||
382 |
2/2✓ Branch 0 taken 383 times.
✓ Branch 1 taken 2 times.
|
385 | for (int i = 0; i < s->nb_boxes; i++) |
383 | 383 | s->boxes[i].color = 0xffU<<24 | ff_oklab_int_to_srgb_u8(s->boxes[i].avg); | |
384 | |||
385 | 2 | qsort(s->boxes, s->nb_boxes, sizeof(*s->boxes), cmp_color); | |
386 | |||
387 | 2 | write_palette(ctx, out); | |
388 | |||
389 | 2 | return out; | |
390 | } | ||
391 | |||
392 | /** | ||
393 | * Locate the color in the hash table and increment its counter. | ||
394 | */ | ||
395 | 4329458 | static int color_inc(struct hist_node *hist, uint32_t color) | |
396 | { | ||
397 | 4329458 | const uint32_t hash = ff_lowbias32(color) & (HIST_SIZE - 1); | |
398 | 4329458 | struct hist_node *node = &hist[hash]; | |
399 | struct color_ref *e; | ||
400 | |||
401 |
2/2✓ Branch 0 taken 4990540 times.
✓ Branch 1 taken 44830 times.
|
5035370 | for (int i = 0; i < node->nb_entries; i++) { |
402 | 4990540 | e = &node->entries[i]; | |
403 |
2/2✓ Branch 0 taken 4284628 times.
✓ Branch 1 taken 705912 times.
|
4990540 | if (e->color == color) { |
404 | 4284628 | e->count++; | |
405 | 4284628 | return 0; | |
406 | } | ||
407 | } | ||
408 | |||
409 | 44830 | e = av_dynarray2_add((void**)&node->entries, &node->nb_entries, | |
410 | sizeof(*node->entries), NULL); | ||
411 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 44830 times.
|
44830 | if (!e) |
412 | ✗ | return AVERROR(ENOMEM); | |
413 | 44830 | e->color = color; | |
414 | 44830 | e->lab = ff_srgb_u8_to_oklab_int(color); | |
415 | 44830 | e->count = 1; | |
416 | 44830 | return 1; | |
417 | } | ||
418 | |||
419 | /** | ||
420 | * Update histogram when pixels differ from previous frame. | ||
421 | */ | ||
422 | 70 | static int update_histogram_diff(struct hist_node *hist, | |
423 | const AVFrame *f1, const AVFrame *f2) | ||
424 | { | ||
425 | 70 | int x, y, ret, nb_diff_colors = 0; | |
426 | |||
427 |
2/2✓ Branch 0 taken 12600 times.
✓ Branch 1 taken 70 times.
|
12670 | for (y = 0; y < f1->height; y++) { |
428 | 12600 | const uint32_t *p = (const uint32_t *)(f1->data[0] + y*f1->linesize[0]); | |
429 | 12600 | const uint32_t *q = (const uint32_t *)(f2->data[0] + y*f2->linesize[0]); | |
430 | |||
431 |
2/2✓ Branch 0 taken 4032000 times.
✓ Branch 1 taken 12600 times.
|
4044600 | for (x = 0; x < f1->width; x++) { |
432 |
2/2✓ Branch 0 taken 3849742 times.
✓ Branch 1 taken 182258 times.
|
4032000 | if (p[x] == q[x]) |
433 | 3849742 | continue; | |
434 | 182258 | ret = color_inc(hist, p[x]); | |
435 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 182258 times.
|
182258 | if (ret < 0) |
436 | ✗ | return ret; | |
437 | 182258 | nb_diff_colors += ret; | |
438 | } | ||
439 | } | ||
440 | 70 | return nb_diff_colors; | |
441 | } | ||
442 | |||
443 | /** | ||
444 | * Simple histogram of the frame. | ||
445 | */ | ||
446 | 72 | static int update_histogram_frame(struct hist_node *hist, const AVFrame *f) | |
447 | { | ||
448 | 72 | int x, y, ret, nb_diff_colors = 0; | |
449 | |||
450 |
2/2✓ Branch 0 taken 12960 times.
✓ Branch 1 taken 72 times.
|
13032 | for (y = 0; y < f->height; y++) { |
451 | 12960 | const uint32_t *p = (const uint32_t *)(f->data[0] + y*f->linesize[0]); | |
452 | |||
453 |
2/2✓ Branch 0 taken 4147200 times.
✓ Branch 1 taken 12960 times.
|
4160160 | for (x = 0; x < f->width; x++) { |
454 | 4147200 | ret = color_inc(hist, p[x]); | |
455 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4147200 times.
|
4147200 | if (ret < 0) |
456 | ✗ | return ret; | |
457 | 4147200 | nb_diff_colors += ret; | |
458 | } | ||
459 | } | ||
460 | 72 | return nb_diff_colors; | |
461 | } | ||
462 | |||
463 | /** | ||
464 | * Update the histogram for each passing frame. No frame will be pushed here. | ||
465 | */ | ||
466 | 142 | static int filter_frame(AVFilterLink *inlink, AVFrame *in) | |
467 | { | ||
468 | 142 | AVFilterContext *ctx = inlink->dst; | |
469 | 142 | PaletteGenContext *s = ctx->priv; | |
470 | int ret; | ||
471 | |||
472 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 142 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
142 | if (in->color_trc != AVCOL_TRC_UNSPECIFIED && in->color_trc != AVCOL_TRC_IEC61966_2_1) |
473 | ✗ | av_log(ctx, AV_LOG_WARNING, "The input frame is not in sRGB, colors may be off\n"); | |
474 | |||
475 | 70 | ret = s->prev_frame ? update_histogram_diff(s->histogram, s->prev_frame, in) | |
476 |
2/2✓ Branch 0 taken 70 times.
✓ Branch 1 taken 72 times.
|
142 | : update_histogram_frame(s->histogram, in); |
477 |
2/2✓ Branch 0 taken 137 times.
✓ Branch 1 taken 5 times.
|
142 | if (ret > 0) |
478 | 137 | s->nb_refs += ret; | |
479 | |||
480 |
2/2✓ Branch 0 taken 71 times.
✓ Branch 1 taken 71 times.
|
142 | if (s->stats_mode == STATS_MODE_DIFF_FRAMES) { |
481 | 71 | av_frame_free(&s->prev_frame); | |
482 | 71 | s->prev_frame = in; | |
483 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 71 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
71 | } else if (s->stats_mode == STATS_MODE_SINGLE_FRAMES && s->nb_refs > 0) { |
484 | AVFrame *out; | ||
485 | int i; | ||
486 | |||
487 | ✗ | out = get_palette_frame(ctx); | |
488 | ✗ | out->pts = in->pts; | |
489 | ✗ | av_frame_free(&in); | |
490 | ✗ | ret = ff_filter_frame(ctx->outputs[0], out); | |
491 | ✗ | for (i = 0; i < HIST_SIZE; i++) | |
492 | ✗ | av_freep(&s->histogram[i].entries); | |
493 | ✗ | av_freep(&s->refs); | |
494 | ✗ | s->nb_refs = 0; | |
495 | ✗ | s->nb_boxes = 0; | |
496 | ✗ | memset(s->boxes, 0, sizeof(s->boxes)); | |
497 | ✗ | memset(s->histogram, 0, sizeof(s->histogram)); | |
498 | } else { | ||
499 | 71 | av_frame_free(&in); | |
500 | } | ||
501 | |||
502 | 142 | return ret; | |
503 | } | ||
504 | |||
505 | /** | ||
506 | * Returns only one frame at the end containing the full palette. | ||
507 | */ | ||
508 | 146 | static int request_frame(AVFilterLink *outlink) | |
509 | { | ||
510 | 146 | AVFilterContext *ctx = outlink->src; | |
511 | 146 | AVFilterLink *inlink = ctx->inputs[0]; | |
512 | 146 | PaletteGenContext *s = ctx->priv; | |
513 | int r; | ||
514 | |||
515 | 146 | r = ff_request_frame(inlink); | |
516 |
6/8✓ Branch 0 taken 4 times.
✓ Branch 1 taken 142 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
|
146 | if (r == AVERROR_EOF && !s->palette_pushed && s->nb_refs && s->stats_mode != STATS_MODE_SINGLE_FRAMES) { |
517 | 2 | r = ff_filter_frame(outlink, get_palette_frame(ctx)); | |
518 | 2 | s->palette_pushed = 1; | |
519 | 2 | return r; | |
520 | } | ||
521 | 144 | return r; | |
522 | } | ||
523 | |||
524 | /** | ||
525 | * The output is one simple 16x16 squared-pixels palette. | ||
526 | */ | ||
527 | 2 | static int config_output(AVFilterLink *outlink) | |
528 | { | ||
529 | 2 | outlink->w = outlink->h = 16; | |
530 | 2 | outlink->sample_aspect_ratio = av_make_q(1, 1); | |
531 | 2 | return 0; | |
532 | } | ||
533 | |||
534 | 4 | static int init(AVFilterContext *ctx) | |
535 | { | ||
536 | 4 | PaletteGenContext* s = ctx->priv; | |
537 | |||
538 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
|
4 | if (s->max_colors - s->reserve_transparent < 2) { |
539 | ✗ | av_log(ctx, AV_LOG_ERROR, "max_colors=2 is only allowed without reserving a transparent color slot\n"); | |
540 | ✗ | return AVERROR(EINVAL); | |
541 | } | ||
542 | |||
543 | 4 | return 0; | |
544 | } | ||
545 | |||
546 | 4 | static av_cold void uninit(AVFilterContext *ctx) | |
547 | { | ||
548 | int i; | ||
549 | 4 | PaletteGenContext *s = ctx->priv; | |
550 | |||
551 |
2/2✓ Branch 0 taken 131072 times.
✓ Branch 1 taken 4 times.
|
131076 | for (i = 0; i < HIST_SIZE; i++) |
552 | 131072 | av_freep(&s->histogram[i].entries); | |
553 | 4 | av_freep(&s->refs); | |
554 | 4 | av_frame_free(&s->prev_frame); | |
555 | 4 | } | |
556 | |||
557 | static const AVFilterPad palettegen_inputs[] = { | ||
558 | { | ||
559 | .name = "default", | ||
560 | .type = AVMEDIA_TYPE_VIDEO, | ||
561 | .filter_frame = filter_frame, | ||
562 | }, | ||
563 | }; | ||
564 | |||
565 | static const AVFilterPad palettegen_outputs[] = { | ||
566 | { | ||
567 | .name = "default", | ||
568 | .type = AVMEDIA_TYPE_VIDEO, | ||
569 | .config_props = config_output, | ||
570 | .request_frame = request_frame, | ||
571 | }, | ||
572 | }; | ||
573 | |||
574 | const AVFilter ff_vf_palettegen = { | ||
575 | .name = "palettegen", | ||
576 | .description = NULL_IF_CONFIG_SMALL("Find the optimal palette for a given stream."), | ||
577 | .priv_size = sizeof(PaletteGenContext), | ||
578 | .init = init, | ||
579 | .uninit = uninit, | ||
580 | FILTER_INPUTS(palettegen_inputs), | ||
581 | FILTER_OUTPUTS(palettegen_outputs), | ||
582 | FILTER_QUERY_FUNC(query_formats), | ||
583 | .priv_class = &palettegen_class, | ||
584 | }; | ||
585 |