FFmpeg
vf_palettegen.c
Go to the documentation of this file.
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/opt.h"
30 #include "libavutil/intreadwrite.h"
31 #include "avfilter.h"
32 #include "internal.h"
33 #include "palette.h"
34 
35 /* Reference a color and how much it's used */
36 struct color_ref {
37  uint32_t color;
38  struct Lab lab;
39  int64_t count;
40 };
41 
42 /* Store a range of colors */
43 struct range_box {
44  uint32_t color; // average color
45  struct Lab avg; // average color in perceptual OkLab space
46  int major_axis; // best axis candidate for cutting the box
47  int64_t weight; // sum of all the weights of the colors
48  int64_t cut_score; // how likely the box is to be cut down (higher implying more likely)
49  int start; // index in PaletteGenContext->refs
50  int len; // number of referenced colors
51  int sorted_by; // whether range of colors is sorted by red (0), green (1) or blue (2)
52 };
53 
54 struct hist_node {
55  struct color_ref *entries;
57 };
58 
59 enum {
64 };
65 
66 #define HIST_SIZE (1<<15)
67 
68 typedef struct PaletteGenContext {
69  const AVClass *class;
70 
74 
75  AVFrame *prev_frame; // previous frame used for the diff stats_mode
76  struct hist_node histogram[HIST_SIZE]; // histogram/hashtable of the colors
77  struct color_ref **refs; // references of all the colors used in the stream
78  int nb_refs; // number of color references (or number of different colors)
79  struct range_box boxes[256]; // define the segmentation of the colorspace (the final palette)
80  int nb_boxes; // number of boxes (increase will segmenting them)
81  int palette_pushed; // if the palette frame is pushed into the outlink or not
82  uint8_t transparency_color[4]; // background color for transparency
84 
85 #define OFFSET(x) offsetof(PaletteGenContext, x)
86 #define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
87 static const AVOption palettegen_options[] = {
88  { "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 },
89  { "reserve_transparent", "reserve a palette entry for transparency", OFFSET(reserve_transparent), AV_OPT_TYPE_BOOL, {.i64=1}, 0, 1, FLAGS },
90  { "transparency_color", "set a background color for transparency", OFFSET(transparency_color), AV_OPT_TYPE_COLOR, {.str="lime"}, 0, 0, FLAGS },
91  { "stats_mode", "set statistics mode", OFFSET(stats_mode), AV_OPT_TYPE_INT, {.i64=STATS_MODE_ALL_FRAMES}, 0, NB_STATS_MODE-1, FLAGS, "mode" },
92  { "full", "compute full frame histograms", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_ALL_FRAMES}, INT_MIN, INT_MAX, FLAGS, "mode" },
93  { "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" },
94  { "single", "compute new histogram for each frame", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_SINGLE_FRAMES}, INT_MIN, INT_MAX, FLAGS, "mode" },
95  { NULL }
96 };
97 
98 AVFILTER_DEFINE_CLASS(palettegen);
99 
101 {
102  static const enum AVPixelFormat in_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
103  static const enum AVPixelFormat out_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
104  int ret;
105 
106  if ((ret = ff_formats_ref(ff_make_format_list(in_fmts) , &ctx->inputs[0]->outcfg.formats)) < 0)
107  return ret;
108  if ((ret = ff_formats_ref(ff_make_format_list(out_fmts), &ctx->outputs[0]->incfg.formats)) < 0)
109  return ret;
110  return 0;
111 }
112 
113 typedef int (*cmp_func)(const void *, const void *);
114 
115 #define DECLARE_CMP_FUNC(k0, k1, k2) \
116 static int cmp_##k0##k1##k2(const void *pa, const void *pb) \
117 { \
118  const struct color_ref * const *a = pa; \
119  const struct color_ref * const *b = pb; \
120  const int c0 = FFDIFFSIGN((*a)->lab.k0, (*b)->lab.k0); \
121  const int c1 = FFDIFFSIGN((*a)->lab.k1, (*b)->lab.k1); \
122  const int c2 = FFDIFFSIGN((*a)->lab.k2, (*b)->lab.k2); \
123  return c0 ? c0 : c1 ? c1 : c2; \
124 }
125 
132 
134 static const char * const sortstr[] = { "Lab", "Lba", "bLa", "aLb", "baL", "abL" };
135 
136 static const cmp_func cmp_funcs[] = {
137  [ID_XYZ] = cmp_Lab,
138  [ID_XZY] = cmp_Lba,
139  [ID_ZXY] = cmp_bLa,
140  [ID_YXZ] = cmp_aLb,
141  [ID_ZYX] = cmp_baL,
142  [ID_YZX] = cmp_abL,
143 };
144 
145 /*
146  * Return an identifier for the order of x, y, z (from higher to lower),
147  * preferring x over y and y over z in case of equality.
148  */
149 static int sort3id(int64_t x, int64_t y, int64_t z)
150 {
151  if (x >= y) {
152  if (y >= z) return ID_XYZ;
153  if (x >= z) return ID_XZY;
154  return ID_ZXY;
155  }
156  if (x >= z) return ID_YXZ;
157  if (y >= z) return ID_YZX;
158  return ID_ZYX;
159 }
160 
161 /**
162  * Simple color comparison for sorting the final palette
163  */
164 static int cmp_color(const void *a, const void *b)
165 {
166  const struct range_box *box1 = a;
167  const struct range_box *box2 = b;
168  return FFDIFFSIGN(box1->color, box2->color);
169 }
170 
171 static void compute_box_stats(PaletteGenContext *s, struct range_box *box)
172 {
173  int64_t er2[3] = {0};
174 
175  /* Compute average color */
176  int64_t sL = 0, sa = 0, sb = 0;
177  box->weight = 0;
178  for (int i = box->start; i < box->start + box->len; i++) {
179  const struct color_ref *ref = s->refs[i];
180  sL += ref->lab.L * ref->count;
181  sa += ref->lab.a * ref->count;
182  sb += ref->lab.b * ref->count;
183  box->weight += ref->count;
184  }
185  box->avg.L = sL / box->weight;
186  box->avg.a = sa / box->weight;
187  box->avg.b = sb / box->weight;
188 
189  /* Compute squared error of each color channel */
190  for (int i = box->start; i < box->start + box->len; i++) {
191  const struct color_ref *ref = s->refs[i];
192  const int64_t dL = ref->lab.L - box->avg.L;
193  const int64_t da = ref->lab.a - box->avg.a;
194  const int64_t db = ref->lab.b - box->avg.b;
195  er2[0] += dL * dL * ref->count;
196  er2[1] += da * da * ref->count;
197  er2[2] += db * db * ref->count;
198  }
199 
200  /* Define the best axis candidate for cutting the box */
201  box->major_axis = sort3id(er2[0], er2[1], er2[2]);
202 
203  /* The box that has the axis with the biggest error amongst all boxes will but cut down */
204  box->cut_score = FFMAX3(er2[0], er2[1], er2[2]);
205 }
206 
207 /**
208  * Find the next box to split: pick the one with the highest cut score
209  */
211 {
212  int best_box_id = -1;
213  int64_t max_score = -1;
214 
215  if (s->nb_boxes == s->max_colors - s->reserve_transparent)
216  return -1;
217 
218  for (int box_id = 0; box_id < s->nb_boxes; box_id++) {
219  const struct range_box *box = &s->boxes[box_id];
220  if (s->boxes[box_id].len >= 2 && box->cut_score > max_score) {
221  best_box_id = box_id;
222  max_score = box->cut_score;
223  }
224  }
225  return best_box_id;
226 }
227 
228 /**
229  * Split given box in two at position n. The original box becomes the left part
230  * of the split, and the new index box is the right part.
231  */
232 static void split_box(PaletteGenContext *s, struct range_box *box, int n)
233 {
234  struct range_box *new_box = &s->boxes[s->nb_boxes++];
235  new_box->start = n + 1;
236  new_box->len = box->start + box->len - new_box->start;
237  new_box->sorted_by = box->sorted_by;
238  box->len -= new_box->len;
239 
240  av_assert0(box->len >= 1);
241  av_assert0(new_box->len >= 1);
242 
243  compute_box_stats(s, box);
244  compute_box_stats(s, new_box);
245 }
246 
247 /**
248  * Write the palette into the output frame.
249  */
251 {
252  const PaletteGenContext *s = ctx->priv;
253  int box_id = 0;
254  uint32_t *pal = (uint32_t *)out->data[0];
255  const int pal_linesize = out->linesize[0] >> 2;
256  uint32_t last_color = 0;
257 
258  for (int y = 0; y < out->height; y++) {
259  for (int x = 0; x < out->width; x++) {
260  if (box_id < s->nb_boxes) {
261  pal[x] = s->boxes[box_id++].color;
262  if ((x || y) && pal[x] == last_color)
263  av_log(ctx, AV_LOG_WARNING, "Duped color: %08"PRIX32"\n", pal[x]);
264  last_color = pal[x];
265  } else {
266  pal[x] = last_color; // pad with last color
267  }
268  }
269  pal += pal_linesize;
270  }
271 
272  if (s->reserve_transparent) {
273  av_assert0(s->nb_boxes < 256);
274  pal[out->width - pal_linesize - 1] = AV_RB32(&s->transparency_color) >> 8;
275  }
276 }
277 
278 /**
279  * Crawl the histogram to get all the defined colors, and create a linear list
280  * of them (each color reference entry is a pointer to the value in the
281  * histogram/hash table).
282  */
283 static struct color_ref **load_color_refs(const struct hist_node *hist, int nb_refs)
284 {
285  int k = 0;
286  struct color_ref **refs = av_malloc_array(nb_refs, sizeof(*refs));
287 
288  if (!refs)
289  return NULL;
290 
291  for (int j = 0; j < HIST_SIZE; j++) {
292  const struct hist_node *node = &hist[j];
293 
294  for (int i = 0; i < node->nb_entries; i++)
295  refs[k++] = &node->entries[i];
296  }
297 
298  return refs;
299 }
300 
301 static double set_colorquant_ratio_meta(AVFrame *out, int nb_out, int nb_in)
302 {
303  char buf[32];
304  const double ratio = (double)nb_out / nb_in;
305  snprintf(buf, sizeof(buf), "%f", ratio);
306  av_dict_set(&out->metadata, "lavfi.color_quant_ratio", buf, 0);
307  return ratio;
308 }
309 
310 /**
311  * Main function implementing the Median Cut Algorithm defined by Paul Heckbert
312  * in Color Image Quantization for Frame Buffer Display (1982)
313  */
315 {
316  AVFrame *out;
317  PaletteGenContext *s = ctx->priv;
318  AVFilterLink *outlink = ctx->outputs[0];
319  double ratio;
320  int box_id = 0;
321  struct range_box *box;
322 
323  /* reference only the used colors from histogram */
324  s->refs = load_color_refs(s->histogram, s->nb_refs);
325  if (!s->refs) {
326  av_log(ctx, AV_LOG_ERROR, "Unable to allocate references for %d different colors\n", s->nb_refs);
327  return NULL;
328  }
329 
330  /* create the palette frame */
331  out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
332  if (!out)
333  return NULL;
334  out->pts = 0;
335 
336  /* set first box for 0..nb_refs */
337  box = &s->boxes[box_id];
338  box->len = s->nb_refs;
339  box->sorted_by = -1;
340  compute_box_stats(s, box);
341  s->nb_boxes = 1;
342 
343  while (box && box->len > 1) {
344  int i;
345  int64_t median, weight;
346 
347  ff_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" sort by %s (already sorted:%c) ",
348  box_id, box->start, box->start + box->len - 1, box->len, box->weight,
349  sortstr[box->major_axis], box->sorted_by == box->major_axis ? 'y':'n');
350 
351  /* sort the range by its major axis if it's not already sorted */
352  if (box->sorted_by != box->major_axis) {
353  cmp_func cmpf = cmp_funcs[box->major_axis];
354  qsort(&s->refs[box->start], box->len, sizeof(struct color_ref *), cmpf);
355  box->sorted_by = box->major_axis;
356  }
357 
358  /* locate the median where to split */
359  median = (box->weight + 1) >> 1;
360  weight = 0;
361  /* if you have 2 boxes, the maximum is actually #0: you must have at
362  * least 1 color on each side of the split, hence the -2 */
363  for (i = box->start; i < box->start + box->len - 2; i++) {
364  weight += s->refs[i]->count;
365  if (weight > median)
366  break;
367  }
368  ff_dlog(ctx, "split @ i=%-6d with w=%-6"PRIu64" (target=%6"PRIu64")\n", i, weight, median);
369  split_box(s, box, i);
370 
371  box_id = get_next_box_id_to_split(s);
372  box = box_id >= 0 ? &s->boxes[box_id] : NULL;
373  }
374 
375  ratio = set_colorquant_ratio_meta(out, s->nb_boxes, s->nb_refs);
376  av_log(ctx, AV_LOG_INFO, "%d%s colors generated out of %d colors; ratio=%f\n",
377  s->nb_boxes, s->reserve_transparent ? "(+1)" : "", s->nb_refs, ratio);
378 
379  for (int i = 0; i < s->nb_boxes; i++)
380  s->boxes[i].color = 0xffU<<24 | ff_oklab_int_to_srgb_u8(s->boxes[i].avg);
381 
382  qsort(s->boxes, s->nb_boxes, sizeof(*s->boxes), cmp_color);
383 
385 
386  return out;
387 }
388 
389 /**
390  * Locate the color in the hash table and increment its counter.
391  */
392 static int color_inc(struct hist_node *hist, uint32_t color)
393 {
394  const uint32_t hash = ff_lowbias32(color) & (HIST_SIZE - 1);
395  struct hist_node *node = &hist[hash];
396  struct color_ref *e;
397 
398  for (int i = 0; i < node->nb_entries; i++) {
399  e = &node->entries[i];
400  if (e->color == color) {
401  e->count++;
402  return 0;
403  }
404  }
405 
406  e = av_dynarray2_add((void**)&node->entries, &node->nb_entries,
407  sizeof(*node->entries), NULL);
408  if (!e)
409  return AVERROR(ENOMEM);
410  e->color = color;
412  e->count = 1;
413  return 1;
414 }
415 
416 /**
417  * Update histogram when pixels differ from previous frame.
418  */
419 static int update_histogram_diff(struct hist_node *hist,
420  const AVFrame *f1, const AVFrame *f2)
421 {
422  int x, y, ret, nb_diff_colors = 0;
423 
424  for (y = 0; y < f1->height; y++) {
425  const uint32_t *p = (const uint32_t *)(f1->data[0] + y*f1->linesize[0]);
426  const uint32_t *q = (const uint32_t *)(f2->data[0] + y*f2->linesize[0]);
427 
428  for (x = 0; x < f1->width; x++) {
429  if (p[x] == q[x])
430  continue;
431  ret = color_inc(hist, p[x]);
432  if (ret < 0)
433  return ret;
434  nb_diff_colors += ret;
435  }
436  }
437  return nb_diff_colors;
438 }
439 
440 /**
441  * Simple histogram of the frame.
442  */
443 static int update_histogram_frame(struct hist_node *hist, const AVFrame *f)
444 {
445  int x, y, ret, nb_diff_colors = 0;
446 
447  for (y = 0; y < f->height; y++) {
448  const uint32_t *p = (const uint32_t *)(f->data[0] + y*f->linesize[0]);
449 
450  for (x = 0; x < f->width; x++) {
451  ret = color_inc(hist, p[x]);
452  if (ret < 0)
453  return ret;
454  nb_diff_colors += ret;
455  }
456  }
457  return nb_diff_colors;
458 }
459 
460 /**
461  * Update the histogram for each passing frame. No frame will be pushed here.
462  */
464 {
465  AVFilterContext *ctx = inlink->dst;
466  PaletteGenContext *s = ctx->priv;
467  int ret;
468 
470  av_log(ctx, AV_LOG_WARNING, "The input frame is not in sRGB, colors may be off\n");
471 
472  ret = s->prev_frame ? update_histogram_diff(s->histogram, s->prev_frame, in)
473  : update_histogram_frame(s->histogram, in);
474  if (ret > 0)
475  s->nb_refs += ret;
476 
477  if (s->stats_mode == STATS_MODE_DIFF_FRAMES) {
478  av_frame_free(&s->prev_frame);
479  s->prev_frame = in;
480  } else if (s->stats_mode == STATS_MODE_SINGLE_FRAMES && s->nb_refs > 0) {
481  AVFrame *out;
482  int i;
483 
485  out->pts = in->pts;
486  av_frame_free(&in);
487  ret = ff_filter_frame(ctx->outputs[0], out);
488  for (i = 0; i < HIST_SIZE; i++)
489  av_freep(&s->histogram[i].entries);
490  av_freep(&s->refs);
491  s->nb_refs = 0;
492  s->nb_boxes = 0;
493  memset(s->boxes, 0, sizeof(s->boxes));
494  memset(s->histogram, 0, sizeof(s->histogram));
495  } else {
496  av_frame_free(&in);
497  }
498 
499  return ret;
500 }
501 
502 /**
503  * Returns only one frame at the end containing the full palette.
504  */
505 static int request_frame(AVFilterLink *outlink)
506 {
507  AVFilterContext *ctx = outlink->src;
508  AVFilterLink *inlink = ctx->inputs[0];
509  PaletteGenContext *s = ctx->priv;
510  int r;
511 
513  if (r == AVERROR_EOF && !s->palette_pushed && s->nb_refs && s->stats_mode != STATS_MODE_SINGLE_FRAMES) {
514  r = ff_filter_frame(outlink, get_palette_frame(ctx));
515  s->palette_pushed = 1;
516  return r;
517  }
518  return r;
519 }
520 
521 /**
522  * The output is one simple 16x16 squared-pixels palette.
523  */
524 static int config_output(AVFilterLink *outlink)
525 {
526  outlink->w = outlink->h = 16;
527  outlink->sample_aspect_ratio = av_make_q(1, 1);
528  return 0;
529 }
530 
532 {
533  PaletteGenContext* s = ctx->priv;
534 
535  if (s->max_colors - s->reserve_transparent < 2) {
536  av_log(ctx, AV_LOG_ERROR, "max_colors=2 is only allowed without reserving a transparent color slot\n");
537  return AVERROR(EINVAL);
538  }
539 
540  return 0;
541 }
542 
544 {
545  int i;
546  PaletteGenContext *s = ctx->priv;
547 
548  for (i = 0; i < HIST_SIZE; i++)
549  av_freep(&s->histogram[i].entries);
550  av_freep(&s->refs);
551  av_frame_free(&s->prev_frame);
552 }
553 
554 static const AVFilterPad palettegen_inputs[] = {
555  {
556  .name = "default",
557  .type = AVMEDIA_TYPE_VIDEO,
558  .filter_frame = filter_frame,
559  },
560 };
561 
562 static const AVFilterPad palettegen_outputs[] = {
563  {
564  .name = "default",
565  .type = AVMEDIA_TYPE_VIDEO,
566  .config_props = config_output,
567  .request_frame = request_frame,
568  },
569 };
570 
572  .name = "palettegen",
573  .description = NULL_IF_CONFIG_SMALL("Find the optimal palette for a given stream."),
574  .priv_size = sizeof(PaletteGenContext),
575  .init = init,
576  .uninit = uninit,
580  .priv_class = &palettegen_class,
581 };
request_frame
static int request_frame(AVFilterLink *outlink)
Returns only one frame at the end containing the full palette.
Definition: vf_palettegen.c:505
ff_get_video_buffer
AVFrame * ff_get_video_buffer(AVFilterLink *link, int w, int h)
Request a picture buffer with a specific set of permissions.
Definition: video.c:101
AVFrame::color_trc
enum AVColorTransferCharacteristic color_trc
Definition: frame.h:592
AV_LOG_WARNING
#define AV_LOG_WARNING
Something somehow does not look correct.
Definition: log.h:186
AVPixelFormat
AVPixelFormat
Pixel format.
Definition: pixfmt.h:64
r
const char * r
Definition: vf_curves.c:126
AVERROR
Filter the word “frame” indicates either a video frame or a group of audio as stored in an AVFrame structure Format for each input and each output the list of supported formats For video that means pixel format For audio that means channel sample they are references to shared objects When the negotiation mechanism computes the intersection of the formats supported at each end of a all references to both lists are replaced with a reference to the intersection And when a single format is eventually chosen for a link amongst the remaining all references to the list are updated That means that if a filter requires that its input and output have the same format amongst a supported all it has to do is use a reference to the same list of formats query_formats can leave some formats unset and return AVERROR(EAGAIN) to cause the negotiation mechanism toagain later. That can be used by filters with complex requirements to use the format negotiated on one link to set the formats supported on another. Frame references ownership and permissions
opt.h
ff_make_format_list
AVFilterFormats * ff_make_format_list(const int *fmts)
Create a list of supported formats.
Definition: formats.c:380
config_output
static int config_output(AVFilterLink *outlink)
The output is one simple 16x16 squared-pixels palette.
Definition: vf_palettegen.c:524
out
FILE * out
Definition: movenc.c:54
ID_YXZ
@ ID_YXZ
Definition: vf_palettegen.c:133
color
Definition: vf_paletteuse.c:509
sort3id
static int sort3id(int64_t x, int64_t y, int64_t z)
Definition: vf_palettegen.c:149
ff_filter_frame
int ff_filter_frame(AVFilterLink *link, AVFrame *frame)
Send a frame of data to the next filter.
Definition: avfilter.c:978
AVERROR_EOF
#define AVERROR_EOF
End of file.
Definition: error.h:57
palette.h
inlink
The exact code depends on how similar the blocks are and how related they are to the and needs to apply these operations to the correct inlink or outlink if there are several Macros are available to factor that when no extra processing is inlink
Definition: filter_design.txt:212
av_frame_free
void av_frame_free(AVFrame **frame)
Free the frame and any dynamically allocated objects in it, e.g.
Definition: frame.c:116
AVFrame
This structure describes decoded (raw) audio or video data.
Definition: frame.h:330
AVFrame::pts
int64_t pts
Presentation timestamp in time_base units (time when frame should be shown to user).
Definition: frame.h:437
AVFrame::width
int width
Definition: frame.h:402
PaletteGenContext::max_colors
int max_colors
Definition: vf_palettegen.c:71
range_box::cut_score
int64_t cut_score
Definition: vf_palettegen.c:48
av_dynarray2_add
void * av_dynarray2_add(void **tab_ptr, int *nb_ptr, size_t elem_size, const uint8_t *elem_data)
Add an element of size elem_size to a dynamic array.
Definition: mem.c:351
AVOption
AVOption.
Definition: opt.h:251
b
#define b
Definition: input.c:41
AVCOL_TRC_UNSPECIFIED
@ AVCOL_TRC_UNSPECIFIED
Definition: pixfmt.h:561
FILTER_QUERY_FUNC
#define FILTER_QUERY_FUNC(func)
Definition: internal.h:167
get_palette_frame
static AVFrame * get_palette_frame(AVFilterContext *ctx)
Main function implementing the Median Cut Algorithm defined by Paul Heckbert in Color Image Quantizat...
Definition: vf_palettegen.c:314
cmp_color
static int cmp_color(const void *a, const void *b)
Simple color comparison for sorting the final palette.
Definition: vf_palettegen.c:164
update_histogram_diff
static int update_histogram_diff(struct hist_node *hist, const AVFrame *f1, const AVFrame *f2)
Update histogram when pixels differ from previous frame.
Definition: vf_palettegen.c:419
ff_request_frame
int ff_request_frame(AVFilterLink *link)
Request an input frame from the filter at the other end of the link.
Definition: avfilter.c:410
hist_node::entries
struct color_ref * entries
Definition: vf_palettegen.c:55
AVFilter::name
const char * name
Filter name.
Definition: avfilter.h:175
load_color_refs
static struct color_ref ** load_color_refs(const struct hist_node *hist, int nb_refs)
Crawl the histogram to get all the defined colors, and create a linear list of them (each color refer...
Definition: vf_palettegen.c:283
hash
uint8_t hash[HASH_SIZE]
Definition: movenc.c:57
HIST_SIZE
#define HIST_SIZE
Definition: vf_palettegen.c:66
Lab::a
int32_t a
Definition: palette.h:31
AVFrame::data
uint8_t * data[AV_NUM_DATA_POINTERS]
pointer to the picture/channel planes.
Definition: frame.h:351
PaletteGenContext::refs
struct color_ref ** refs
Definition: vf_palettegen.c:77
ID_ZYX
@ ID_ZYX
Definition: vf_palettegen.c:133
AVFILTER_DEFINE_CLASS
AVFILTER_DEFINE_CLASS(palettegen)
filter_frame
static int filter_frame(AVFilterLink *inlink, AVFrame *in)
Update the histogram for each passing frame.
Definition: vf_palettegen.c:463
ff_oklab_int_to_srgb_u8
uint32_t ff_oklab_int_to_srgb_u8(struct Lab c)
OkLab to sRGB (non-linear) conversion.
Definition: palette.c:194
PaletteGenContext::prev_frame
AVFrame * prev_frame
Definition: vf_palettegen.c:75
AVCOL_TRC_IEC61966_2_1
@ AVCOL_TRC_IEC61966_2_1
IEC 61966-2-1 (sRGB or sYCC)
Definition: pixfmt.h:572
Lab::b
int32_t b
Definition: palette.h:31
color_ref::count
int64_t count
Definition: vf_palettegen.c:39
AVFilterPad
A filter pad used for either input or output.
Definition: internal.h:49
FFDIFFSIGN
#define FFDIFFSIGN(x, y)
Comparator.
Definition: macros.h:45
avassert.h
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:180
av_cold
#define av_cold
Definition: attributes.h:90
init
static int init(AVFilterContext *ctx)
Definition: vf_palettegen.c:531
FLAGS
#define FLAGS
Definition: vf_palettegen.c:86
ID_YZX
@ ID_YZX
Definition: vf_palettegen.c:133
ID_XYZ
@ ID_XYZ
Definition: vf_palettegen.c:133
intreadwrite.h
s
#define s(width, name)
Definition: cbs_vp9.c:256
ff_formats_ref
int ff_formats_ref(AVFilterFormats *f, AVFilterFormats **ref)
Add *ref as a new reference to formats.
Definition: formats.c:596
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
ctx
AVFormatContext * ctx
Definition: movenc.c:48
OFFSET
#define OFFSET(x)
Definition: vf_palettegen.c:85
ff_lowbias32
uint32_t ff_lowbias32(uint32_t x)
Definition: palette.c:211
sortstr
static const char *const sortstr[]
Definition: vf_palettegen.c:134
uninit
static av_cold void uninit(AVFilterContext *ctx)
Definition: vf_palettegen.c:543
FILTER_INPUTS
#define FILTER_INPUTS(array)
Definition: internal.h:190
compute_box_stats
static void compute_box_stats(PaletteGenContext *s, struct range_box *box)
Definition: vf_palettegen.c:171
AVClass
Describe the class of an AVClass context structure.
Definition: log.h:66
NULL
#define NULL
Definition: coverity.c:32
cmp_func
int(* cmp_func)(const void *, const void *)
Definition: vf_palettegen.c:113
query_formats
static int query_formats(AVFilterContext *ctx)
Definition: vf_palettegen.c:100
AV_OPT_TYPE_COLOR
@ AV_OPT_TYPE_COLOR
Definition: opt.h:240
hist_node
Definition: vf_palettegen.c:54
PaletteGenContext::palette_pushed
int palette_pushed
Definition: vf_palettegen.c:81
double
double
Definition: af_crystalizer.c:132
PaletteGenContext::nb_refs
int nb_refs
Definition: vf_palettegen.c:78
weight
static int weight(int i, int blen, int offset)
Definition: diracdec.c:1561
write_palette
static void write_palette(AVFilterContext *ctx, AVFrame *out)
Write the palette into the output frame.
Definition: vf_palettegen.c:250
ff_dlog
#define ff_dlog(a,...)
Definition: tableprint_vlc.h:28
PaletteGenContext::boxes
struct range_box boxes[256]
Definition: vf_palettegen.c:79
color_ref::color
uint32_t color
Definition: vf_palettegen.c:37
f
f
Definition: af_crystalizer.c:122
NULL_IF_CONFIG_SMALL
#define NULL_IF_CONFIG_SMALL(x)
Return NULL if CONFIG_SMALL is true, otherwise the argument without modification.
Definition: internal.h:115
range_box::start
int start
Definition: vf_palettegen.c:49
for
for(k=2;k<=8;++k)
Definition: h264pred_template.c:425
DECLARE_CMP_FUNC
#define DECLARE_CMP_FUNC(k0, k1, k2)
Definition: vf_palettegen.c:115
Lab
Definition: palette.h:30
color
static const uint32_t color[16+AV_CLASS_CATEGORY_NB]
Definition: log.c:94
av_make_q
static AVRational av_make_q(int num, int den)
Create an AVRational.
Definition: rational.h:71
AV_RB32
uint64_t_TMPL AV_WL64 unsigned int_TMPL AV_WL32 unsigned int_TMPL AV_WL24 unsigned int_TMPL AV_WL16 uint64_t_TMPL AV_WB64 unsigned int_TMPL AV_RB32
Definition: bytestream.h:96
range_box::len
int len
Definition: vf_palettegen.c:50
PaletteGenContext::reserve_transparent
int reserve_transparent
Definition: vf_palettegen.c:72
range_box::weight
int64_t weight
Definition: vf_palettegen.c:47
get_next_box_id_to_split
static int get_next_box_id_to_split(PaletteGenContext *s)
Find the next box to split: pick the one with the highest cut score.
Definition: vf_palettegen.c:210
AV_PIX_FMT_RGB32
#define AV_PIX_FMT_RGB32
Definition: pixfmt.h:432
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:41
color_ref::lab
struct Lab lab
Definition: vf_palettegen.c:38
palettegen_options
static const AVOption palettegen_options[]
Definition: vf_palettegen.c:87
PaletteGenContext
Definition: vf_palettegen.c:68
AV_LOG_INFO
#define AV_LOG_INFO
Standard information.
Definition: log.h:191
internal.h
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:269
hist_node::nb_entries
int nb_entries
Definition: vf_palettegen.c:56
internal.h
range_box::avg
struct Lab avg
Definition: vf_palettegen.c:45
av_malloc_array
#define av_malloc_array(a, b)
Definition: tableprint_vlc.h:31
palettegen_outputs
static const AVFilterPad palettegen_outputs[]
Definition: vf_palettegen.c:562
ID_XZY
@ ID_XZY
Definition: vf_palettegen.c:133
AVFilterPad::name
const char * name
Pad name.
Definition: internal.h:55
AVFilter
Filter definition.
Definition: avfilter.h:171
update_histogram_frame
static int update_histogram_frame(struct hist_node *hist, const AVFrame *f)
Simple histogram of the frame.
Definition: vf_palettegen.c:443
ret
ret
Definition: filter_design.txt:187
range_box
Definition: vf_palettegen.c:43
color_ref
Definition: vf_palettegen.c:36
range_box::color
uint32_t color
Definition: vf_palettegen.c:44
AVFrame::height
int height
Definition: frame.h:402
STATS_MODE_ALL_FRAMES
@ STATS_MODE_ALL_FRAMES
Definition: vf_palettegen.c:60
cmp_funcs
static const cmp_func cmp_funcs[]
Definition: vf_palettegen.c:136
PaletteGenContext::histogram
struct hist_node histogram[HIST_SIZE]
Definition: vf_palettegen.c:76
AV_PIX_FMT_NONE
@ AV_PIX_FMT_NONE
Definition: pixfmt.h:65
AV_OPT_TYPE_INT
@ AV_OPT_TYPE_INT
Definition: opt.h:225
avfilter.h
palettegen_inputs
static const AVFilterPad palettegen_inputs[]
Definition: vf_palettegen.c:554
ref
static int ref[MAX_W *MAX_W]
Definition: jpeg2000dwt.c:112
L
#define L(x)
Definition: vpx_arith.h:36
STATS_MODE_SINGLE_FRAMES
@ STATS_MODE_SINGLE_FRAMES
Definition: vf_palettegen.c:62
AVFilterContext
An instance of a filter.
Definition: avfilter.h:402
AVMEDIA_TYPE_VIDEO
@ AVMEDIA_TYPE_VIDEO
Definition: avutil.h:201
split_box
static void split_box(PaletteGenContext *s, struct range_box *box, int n)
Split given box in two at position n.
Definition: vf_palettegen.c:232
range_box::sorted_by
int sorted_by
Definition: vf_palettegen.c:51
AV_OPT_TYPE_BOOL
@ AV_OPT_TYPE_BOOL
Definition: opt.h:244
FILTER_OUTPUTS
#define FILTER_OUTPUTS(array)
Definition: internal.h:191
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:34
av_dict_set
int av_dict_set(AVDictionary **pm, const char *key, const char *value, int flags)
Set the given entry in *pm, overwriting an existing entry.
Definition: dict.c:86
NB_STATS_MODE
@ NB_STATS_MODE
Definition: vf_palettegen.c:63
color_inc
static int color_inc(struct hist_node *hist, uint32_t color)
Locate the color in the hash table and increment its counter.
Definition: vf_palettegen.c:392
STATS_MODE_DIFF_FRAMES
@ STATS_MODE_DIFF_FRAMES
Definition: vf_palettegen.c:61
FFMAX3
#define FFMAX3(a, b, c)
Definition: macros.h:48
AVFrame::linesize
int linesize[AV_NUM_DATA_POINTERS]
For video, a positive or negative value, which is typically indicating the size in bytes of each pict...
Definition: frame.h:375
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:27
ff_vf_palettegen
const AVFilter ff_vf_palettegen
Definition: vf_palettegen.c:571
PaletteGenContext::stats_mode
int stats_mode
Definition: vf_palettegen.c:73
PaletteGenContext::transparency_color
uint8_t transparency_color[4]
Definition: vf_palettegen.c:82
set_colorquant_ratio_meta
static double set_colorquant_ratio_meta(AVFrame *out, int nb_out, int nb_in)
Definition: vf_palettegen.c:301
int
int
Definition: ffmpeg_filter.c:156
range_box::major_axis
int major_axis
Definition: vf_palettegen.c:46
AV_OPT_TYPE_CONST
@ AV_OPT_TYPE_CONST
Definition: opt.h:234
snprintf
#define snprintf
Definition: snprintf.h:34
PaletteGenContext::nb_boxes
int nb_boxes
Definition: vf_palettegen.c:80
ID_ZXY
@ ID_ZXY
Definition: vf_palettegen.c:133
ff_srgb_u8_to_oklab_int
struct Lab ff_srgb_u8_to_oklab_int(uint32_t srgb)
sRGB (non-linear) to OkLab conversion
Definition: palette.c:170
Lab::L
int32_t L
Definition: palette.h:31