2 * This file is part of FFmpeg.
4 * FFmpeg is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
9 * FFmpeg is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with FFmpeg; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21 * Generate one palette for a whole video stream.
24 #include "libavutil/avassert.h"
25 #include "libavutil/opt.h"
29 /* Reference a color and how much it's used */
35 /* Store a range of colors */
37 uint32_t color; // average color
38 int64_t variance; // overall variance of the box (how much the colors are spread)
39 int start; // index in PaletteGenContext->refs
40 int len; // number of referenced colors
41 int sorted_by; // whether range of colors is sorted by red (0), green (1) or blue (2)
45 struct color_ref *entries;
50 STATS_MODE_ALL_FRAMES,
51 STATS_MODE_DIFF_FRAMES,
56 #define HIST_SIZE (1<<(3*NBITS))
62 int reserve_transparent;
65 AVFrame *prev_frame; // previous frame used for the diff stats_mode
66 struct hist_node histogram[HIST_SIZE]; // histogram/hashtable of the colors
67 struct color_ref **refs; // references of all the colors used in the stream
68 int nb_refs; // number of color references (or number of different colors)
69 struct range_box boxes[256]; // define the segmentation of the colorspace (the final palette)
70 int nb_boxes; // number of boxes (increase will segmenting them)
71 int palette_pushed; // if the palette frame is pushed into the outlink or not
74 #define OFFSET(x) offsetof(PaletteGenContext, x)
75 #define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
76 static const AVOption palettegen_options[] = {
77 { "max_colors", "set the maximum number of colors to use in the palette", OFFSET(max_colors), AV_OPT_TYPE_INT, {.i64=256}, 4, 256, FLAGS },
78 { "reserve_transparent", "reserve a palette entry for transparency", OFFSET(reserve_transparent), AV_OPT_TYPE_INT, {.i64=1}, 0, 1, FLAGS },
79 { "stats_mode", "set statistics mode", OFFSET(stats_mode), AV_OPT_TYPE_INT, {.i64=STATS_MODE_ALL_FRAMES}, 0, NB_STATS_MODE, FLAGS, "mode" },
80 { "full", "compute full frame histograms", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_ALL_FRAMES}, INT_MIN, INT_MAX, FLAGS, "mode" },
81 { "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, "mode" },
85 AVFILTER_DEFINE_CLASS(palettegen);
87 static int query_formats(AVFilterContext *ctx)
89 static const enum AVPixelFormat in_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
90 static const enum AVPixelFormat out_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
91 AVFilterFormats *in = ff_make_format_list(in_fmts);
92 AVFilterFormats *out = ff_make_format_list(out_fmts);
96 return AVERROR(ENOMEM);
98 ff_formats_ref(in, &ctx->inputs[0]->out_formats);
99 ff_formats_ref(out, &ctx->outputs[0]->in_formats);
103 typedef int (*cmp_func)(const void *, const void *);
105 #define DECLARE_CMP_FUNC(name, pos) \
106 static int cmp_##name(const void *pa, const void *pb) \
108 const struct color_ref * const *a = pa; \
109 const struct color_ref * const *b = pb; \
110 return ((*a)->color >> (8 * (2 - (pos))) & 0xff) \
111 - ((*b)->color >> (8 * (2 - (pos))) & 0xff); \
114 DECLARE_CMP_FUNC(r, 0)
115 DECLARE_CMP_FUNC(g, 1)
116 DECLARE_CMP_FUNC(b, 2)
118 static const cmp_func cmp_funcs[] = {cmp_r, cmp_g, cmp_b};
121 * Simple color comparison for sorting the final palette
123 static int cmp_color(const void *a, const void *b)
125 const struct range_box *box1 = a;
126 const struct range_box *box2 = b;
127 return box1->color - box2->color;
130 static av_always_inline int diff(const uint32_t a, const uint32_t b)
132 const uint8_t c1[] = {a >> 16 & 0xff, a >> 8 & 0xff, a & 0xff};
133 const uint8_t c2[] = {b >> 16 & 0xff, b >> 8 & 0xff, b & 0xff};
134 const int dr = c1[0] - c2[0];
135 const int dg = c1[1] - c2[1];
136 const int db = c1[2] - c2[2];
137 return dr*dr + dg*dg + db*db;
141 * Find the next box to split: pick the one with the highest variance
143 static int get_next_box_id_to_split(PaletteGenContext *s)
145 int box_id, i, best_box_id = -1;
146 int64_t max_variance = -1;
148 if (s->nb_boxes == s->max_colors - s->reserve_transparent)
151 for (box_id = 0; box_id < s->nb_boxes; box_id++) {
152 struct range_box *box = &s->boxes[box_id];
154 if (s->boxes[box_id].len >= 2) {
156 if (box->variance == -1) {
157 int64_t variance = 0;
159 for (i = 0; i < box->len; i++) {
160 const struct color_ref *ref = s->refs[box->start + i];
161 variance += diff(ref->color, box->color) * ref->count;
163 box->variance = variance;
165 if (box->variance > max_variance) {
166 best_box_id = box_id;
167 max_variance = box->variance;
177 * Get the 32-bit average color for the range of RGB colors enclosed in the
178 * specified box. Takes into account the weight of each color.
180 static uint32_t get_avg_color(struct color_ref * const *refs,
181 const struct range_box *box)
184 const int n = box->len;
185 uint64_t r = 0, g = 0, b = 0, div = 0;
187 for (i = 0; i < n; i++) {
188 const struct color_ref *ref = refs[box->start + i];
189 r += (ref->color >> 16 & 0xff) * ref->count;
190 g += (ref->color >> 8 & 0xff) * ref->count;
191 b += (ref->color & 0xff) * ref->count;
199 return 0xffU<<24 | r<<16 | g<<8 | b;
203 * Split given box in two at position n. The original box becomes the left part
204 * of the split, and the new index box is the right part.
206 static void split_box(PaletteGenContext *s, struct range_box *box, int n)
208 struct range_box *new_box = &s->boxes[s->nb_boxes++];
209 new_box->start = n + 1;
210 new_box->len = box->start + box->len - new_box->start;
211 new_box->sorted_by = box->sorted_by;
212 box->len -= new_box->len;
214 av_assert0(box->len >= 1);
215 av_assert0(new_box->len >= 1);
217 box->color = get_avg_color(s->refs, box);
218 new_box->color = get_avg_color(s->refs, new_box);
220 new_box->variance = -1;
224 * Write the palette into the output frame.
226 static void write_palette(const PaletteGenContext *s, AVFrame *out)
228 int x, y, box_id = 0;
229 uint32_t *pal = (uint32_t *)out->data[0];
230 const int pal_linesize = out->linesize[0] >> 2;
231 uint32_t last_color = 0;
233 for (y = 0; y < out->height; y++) {
234 for (x = 0; x < out->width; x++) {
235 if (box_id < s->nb_boxes) {
236 pal[x] = s->boxes[box_id++].color;
237 if ((x || y) && pal[x] == last_color)
238 av_log(NULL, AV_LOG_WARNING, "Dupped color: %08X\n", pal[x]);
241 pal[x] = 0xff000000; // pad with black
247 if (s->reserve_transparent) {
248 av_assert0(s->nb_boxes < 256);
249 pal[out->width - pal_linesize - 1] = 0x0000ff00; // add a green transparent color
254 * Crawl the histogram to get all the defined colors, and create a linear list
255 * of them (each color reference entry is a pointer to the value in the
256 * histogram/hash table).
258 static struct color_ref **load_color_refs(const struct hist_node *hist, int nb_refs)
261 struct color_ref **refs = av_malloc_array(nb_refs, sizeof(*refs));
266 for (j = 0; j < HIST_SIZE; j++) {
267 const struct hist_node *node = &hist[j];
269 for (i = 0; i < node->nb_entries; i++)
270 refs[k++] = &node->entries[i];
277 * Main function implementing the Median Cut Algorithm defined by Paul Heckbert
278 * in Color Image Quantization for Frame Buffer Display (1982)
280 static AVFrame *get_palette_frame(AVFilterContext *ctx)
283 PaletteGenContext *s = ctx->priv;
284 AVFilterLink *outlink = ctx->outputs[0];
287 struct range_box *box;
289 /* reference only the used colors from histogram */
290 s->refs = load_color_refs(s->histogram, s->nb_refs);
292 av_log(ctx, AV_LOG_ERROR, "Unable to allocate references for %d different colors\n", s->nb_refs);
296 /* create the palette frame */
297 out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
302 /* set first box for 0..nb_refs */
303 box = &s->boxes[box_id];
304 box->len = s->nb_refs;
306 box->color = get_avg_color(s->refs, box);
310 while (box && box->len > 1) {
312 uint64_t median, box_weight = 0;
314 /* compute the box weight (sum all the weights of the colors in the
315 * range) and its boundings */
316 uint8_t min[3] = {0xff, 0xff, 0xff};
317 uint8_t max[3] = {0x00, 0x00, 0x00};
318 for (i = box->start; i < box->start + box->len; i++) {
319 const struct color_ref *ref = s->refs[i];
320 const uint32_t rgb = ref->color;
321 const uint8_t r = rgb >> 16 & 0xff, g = rgb >> 8 & 0xff, b = rgb & 0xff;
322 min[0] = FFMIN(r, min[0]), max[0] = FFMAX(r, max[0]);
323 min[1] = FFMIN(g, min[1]), max[1] = FFMAX(g, max[1]);
324 min[2] = FFMIN(b, min[2]), max[2] = FFMAX(b, max[2]);
325 box_weight += ref->count;
328 /* define the axis to sort by according to the widest range of colors */
329 rr = max[0] - min[0];
330 gr = max[1] - min[1];
331 br = max[2] - min[2];
332 longest = 1; // pick green by default (the color the eye is the most sensitive to)
333 if (br >= rr && br >= gr) longest = 2;
334 if (rr >= gr && rr >= br) longest = 0;
335 if (gr >= rr && gr >= br) longest = 1; // prefer green again
337 av_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" ranges:[%2x %2x %2x] sort by %c (already sorted:%c) ",
338 box_id, box->start, box->start + box->len - 1, box->len, box_weight,
339 rr, gr, br, "rgb"[longest], box->sorted_by == longest ? 'y':'n');
341 /* sort the range by its longest axis if it's not already sorted */
342 if (box->sorted_by != longest) {
343 qsort(&s->refs[box->start], box->len, sizeof(*s->refs), cmp_funcs[longest]);
344 box->sorted_by = longest;
347 /* locate the median where to split */
348 median = (box_weight + 1) >> 1;
350 /* if you have 2 boxes, the maximum is actually #0: you must have at
351 * least 1 color on each side of the split, hence the -2 */
352 for (i = box->start; i < box->start + box->len - 2; i++) {
353 box_weight += s->refs[i]->count;
354 if (box_weight > median)
357 av_dlog(ctx, "split @ i=%-6d with w=%-6"PRIu64" (target=%6"PRIu64")\n", i, box_weight, median);
358 split_box(s, box, i);
360 box_id = get_next_box_id_to_split(s);
361 box = box_id >= 0 ? &s->boxes[box_id] : NULL;
364 av_log(ctx, AV_LOG_DEBUG, "%d%s boxes generated out of %d colors\n",
365 s->nb_boxes, s->reserve_transparent ? "(+1)" : "", s->nb_refs);
367 qsort(s->boxes, s->nb_boxes, sizeof(*s->boxes), cmp_color);
369 write_palette(s, out);
375 * Hashing function for the color.
376 * It keeps the NBITS least significant bit of each component to make it
377 * "random" even if the scene doesn't have much different colors.
379 static inline unsigned color_hash(uint32_t color)
381 const uint8_t r = color >> 16 & ((1<<NBITS)-1);
382 const uint8_t g = color >> 8 & ((1<<NBITS)-1);
383 const uint8_t b = color & ((1<<NBITS)-1);
384 return r<<(NBITS*2) | g<<NBITS | b;
388 * Locate the color in the hash table and increment its counter.
390 static int color_inc(struct hist_node *hist, uint32_t color)
393 const unsigned hash = color_hash(color);
394 struct hist_node *node = &hist[hash];
397 for (i = 0; i < node->nb_entries; i++) {
398 e = &node->entries[i];
399 if (e->color == color) {
405 e = av_dynarray2_add((void**)&node->entries, &node->nb_entries,
406 sizeof(*node->entries), NULL);
408 return AVERROR(ENOMEM);
415 * Update histogram when pixels differ from previous frame.
417 static int update_histogram_diff(struct hist_node *hist,
418 const AVFrame *f1, const AVFrame *f2)
420 int x, y, ret, nb_diff_colors = 0;
422 for (y = 0; y < f1->height; y++) {
423 const uint32_t *p = (const uint32_t *)(f1->data[0] + y*f1->linesize[0]);
424 const uint32_t *q = (const uint32_t *)(f2->data[0] + y*f2->linesize[0]);
426 for (x = 0; x < f2->width; x++) {
429 ret = color_inc(hist, p[x]);
432 nb_diff_colors += ret;
435 return nb_diff_colors;
439 * Simple histogram of the frame.
441 static int update_histogram_frame(struct hist_node *hist, const AVFrame *f)
443 int x, y, ret, nb_diff_colors = 0;
445 for (y = 0; y < f->height; y++) {
446 const uint32_t *p = (const uint32_t *)(f->data[0] + y*f->linesize[0]);
448 for (x = 0; x < f->width; x++) {
449 ret = color_inc(hist, p[x]);
452 nb_diff_colors += ret;
455 return nb_diff_colors;
459 * Update the histogram for each passing frame. No frame will be pushed here.
461 static int filter_frame(AVFilterLink *inlink, AVFrame *in)
463 AVFilterContext *ctx = inlink->dst;
464 PaletteGenContext *s = ctx->priv;
465 const int ret = s->prev_frame ? update_histogram_diff(s->histogram, s->prev_frame, in)
466 : update_histogram_frame(s->histogram, in);
471 if (s->stats_mode == STATS_MODE_DIFF_FRAMES) {
472 av_frame_free(&s->prev_frame);
482 * Returns only one frame at the end containing the full palette.
484 static int request_frame(AVFilterLink *outlink)
486 AVFilterContext *ctx = outlink->src;
487 AVFilterLink *inlink = ctx->inputs[0];
488 PaletteGenContext *s = ctx->priv;
491 r = ff_request_frame(inlink);
492 if (r == AVERROR_EOF && !s->palette_pushed) {
493 r = ff_filter_frame(outlink, get_palette_frame(ctx));
494 s->palette_pushed = 1;
501 * The output is one simple 16x16 squared-pixels palette.
503 static int config_output(AVFilterLink *outlink)
505 outlink->w = outlink->h = 16;
506 outlink->sample_aspect_ratio = av_make_q(1, 1);
507 outlink->flags |= FF_LINK_FLAG_REQUEST_LOOP;
511 static av_cold void uninit(AVFilterContext *ctx)
514 PaletteGenContext *s = ctx->priv;
516 for (i = 0; i < HIST_SIZE; i++)
517 av_freep(&s->histogram[i].entries);
519 av_freep(&s->prev_frame);
522 static const AVFilterPad palettegen_inputs[] = {
525 .type = AVMEDIA_TYPE_VIDEO,
526 .filter_frame = filter_frame,
531 static const AVFilterPad palettegen_outputs[] = {
534 .type = AVMEDIA_TYPE_VIDEO,
535 .config_props = config_output,
536 .request_frame = request_frame,
541 AVFilter ff_vf_palettegen = {
542 .name = "palettegen",
543 .description = NULL_IF_CONFIG_SMALL("Find the optimal palette for a given stream."),
544 .priv_size = sizeof(PaletteGenContext),
546 .query_formats = query_formats,
547 .inputs = palettegen_inputs,
548 .outputs = palettegen_outputs,
549 .priv_class = &palettegen_class,