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/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;
60 };
61 
62 enum {
67 };
68 
69 #define HIST_SIZE (1<<15)
70 
71 typedef struct PaletteGenContext {
72  const AVClass *class;
73 
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
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 
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  if ((ret = ff_formats_ref(ff_make_format_list(in_fmts) , &ctx->inputs[0]->outcfg.formats)) < 0)
110  return ret;
111  if ((ret = ff_formats_ref(ff_make_format_list(out_fmts), &ctx->outputs[0]->incfg.formats)) < 0)
112  return ret;
113  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 
135 
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 static int sort3id(int64_t x, int64_t y, int64_t z)
153 {
154  if (x >= y) {
155  if (y >= z) return ID_XYZ;
156  if (x >= z) return ID_XZY;
157  return ID_ZXY;
158  }
159  if (x >= z) return ID_YXZ;
160  if (y >= z) return ID_YZX;
161  return ID_ZYX;
162 }
163 
164 /**
165  * Simple color comparison for sorting the final palette
166  */
167 static int cmp_color(const void *a, const void *b)
168 {
169  const struct range_box *box1 = a;
170  const struct range_box *box2 = b;
171  return FFDIFFSIGN(box1->color, box2->color);
172 }
173 
174 static void compute_box_stats(PaletteGenContext *s, struct range_box *box)
175 {
176  int64_t er2[3] = {0};
177 
178  /* Compute average color */
179  int64_t sL = 0, sa = 0, sb = 0;
180  box->weight = 0;
181  for (int i = box->start; i < box->start + box->len; i++) {
182  const struct color_ref *ref = s->refs[i];
183  sL += ref->lab.L * ref->count;
184  sa += ref->lab.a * ref->count;
185  sb += ref->lab.b * ref->count;
186  box->weight += ref->count;
187  }
188  box->avg.L = sL / box->weight;
189  box->avg.a = sa / box->weight;
190  box->avg.b = sb / box->weight;
191 
192  /* Compute squared error of each color channel */
193  for (int i = box->start; i < box->start + box->len; i++) {
194  const struct color_ref *ref = s->refs[i];
195  const int64_t dL = ref->lab.L - box->avg.L;
196  const int64_t da = ref->lab.a - box->avg.a;
197  const int64_t db = ref->lab.b - box->avg.b;
198  er2[0] += dL * dL * ref->count;
199  er2[1] += da * da * ref->count;
200  er2[2] += db * db * ref->count;
201  }
202 
203  /* Define the best axis candidate for cutting the box */
204  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  box->cut_score = FFMAX3(er2[0], er2[1], er2[2]);
208 }
209 
210 /**
211  * Find the next box to split: pick the one with the highest cut score
212  */
214 {
215  int best_box_id = -1;
216  int64_t max_score = -1;
217 
218  if (s->nb_boxes == s->max_colors - s->reserve_transparent)
219  return -1;
220 
221  for (int box_id = 0; box_id < s->nb_boxes; box_id++) {
222  const struct range_box *box = &s->boxes[box_id];
223  if (s->boxes[box_id].len >= 2 && box->cut_score > max_score) {
224  best_box_id = box_id;
225  max_score = box->cut_score;
226  }
227  }
228  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 static void split_box(PaletteGenContext *s, struct range_box *box, int n)
236 {
237  struct range_box *new_box = &s->boxes[s->nb_boxes++];
238  new_box->start = n + 1;
239  new_box->len = box->start + box->len - new_box->start;
240  new_box->sorted_by = box->sorted_by;
241  box->len -= new_box->len;
242 
243  av_assert0(box->len >= 1);
244  av_assert0(new_box->len >= 1);
245 
246  compute_box_stats(s, box);
247  compute_box_stats(s, new_box);
248 }
249 
250 /**
251  * Write the palette into the output frame.
252  */
254 {
255  const PaletteGenContext *s = ctx->priv;
256  int box_id = 0;
257  uint32_t *pal = (uint32_t *)out->data[0];
258  const int pal_linesize = out->linesize[0] >> 2;
259  uint32_t last_color = 0;
260 
261  for (int y = 0; y < out->height; y++) {
262  for (int x = 0; x < out->width; x++) {
263  if (box_id < s->nb_boxes) {
264  pal[x] = s->boxes[box_id++].color;
265  if ((x || y) && pal[x] == last_color)
266  av_log(ctx, AV_LOG_WARNING, "Duped color: %08"PRIX32"\n", pal[x]);
267  last_color = pal[x];
268  } else {
269  pal[x] = last_color; // pad with last color
270  }
271  }
272  pal += pal_linesize;
273  }
274 
275  if (s->reserve_transparent) {
276  av_assert0(s->nb_boxes < 256);
277  pal[out->width - pal_linesize - 1] = AV_RB32(&s->transparency_color) >> 8;
278  }
279 }
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 static struct color_ref **load_color_refs(const struct hist_node *hist, int nb_refs)
287 {
288  int k = 0;
289  struct color_ref **refs = av_malloc_array(nb_refs, sizeof(*refs));
290 
291  if (!refs)
292  return NULL;
293 
294  for (int j = 0; j < HIST_SIZE; j++) {
295  const struct hist_node *node = &hist[j];
296 
297  for (int i = 0; i < node->nb_entries; i++)
298  refs[k++] = &node->entries[i];
299  }
300 
301  return refs;
302 }
303 
304 static double set_colorquant_ratio_meta(AVFrame *out, int nb_out, int nb_in)
305 {
306  char buf[32];
307  const double ratio = (double)nb_out / nb_in;
308  snprintf(buf, sizeof(buf), "%f", ratio);
309  av_dict_set(&out->metadata, "lavfi.color_quant_ratio", buf, 0);
310  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  */
318 {
319  AVFrame *out;
320  PaletteGenContext *s = ctx->priv;
321  AVFilterLink *outlink = ctx->outputs[0];
322  double ratio;
323  int box_id = 0;
324  struct range_box *box;
325 
326  /* reference only the used colors from histogram */
327  s->refs = load_color_refs(s->histogram, s->nb_refs);
328  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  out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
335  if (!out)
336  return NULL;
337  out->pts = 0;
338 
339  /* set first box for 0..nb_refs */
340  box = &s->boxes[box_id];
341  box->len = s->nb_refs;
342  box->sorted_by = -1;
343  compute_box_stats(s, box);
344  s->nb_boxes = 1;
345 
346  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  if (box->sorted_by != box->major_axis) {
356  cmp_func cmpf = cmp_funcs[box->major_axis];
357  qsort(&s->refs[box->start], box->len, sizeof(struct color_ref *), cmpf);
358  box->sorted_by = box->major_axis;
359  }
360 
361  /* locate the median where to split */
362  median = (box->weight + 1) >> 1;
363  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  for (i = box->start; i < box->start + box->len - 2; i++) {
367  weight += s->refs[i]->count;
368  if (weight > median)
369  break;
370  }
371  ff_dlog(ctx, "split @ i=%-6d with w=%-6"PRIu64" (target=%6"PRIu64")\n", i, weight, median);
372  split_box(s, box, i);
373 
374  box_id = get_next_box_id_to_split(s);
375  box = box_id >= 0 ? &s->boxes[box_id] : NULL;
376  }
377 
378  ratio = set_colorquant_ratio_meta(out, s->nb_boxes, s->nb_refs);
379  av_log(ctx, AV_LOG_INFO, "%d%s colors generated out of %d colors; ratio=%f\n",
380  s->nb_boxes, s->reserve_transparent ? "(+1)" : "", s->nb_refs, ratio);
381 
382  for (int i = 0; i < s->nb_boxes; i++)
383  s->boxes[i].color = 0xffU<<24 | ff_oklab_int_to_srgb_u8(s->boxes[i].avg);
384 
385  qsort(s->boxes, s->nb_boxes, sizeof(*s->boxes), cmp_color);
386 
388 
389  return out;
390 }
391 
392 /**
393  * Locate the color in the hash table and increment its counter.
394  */
395 static int color_inc(struct hist_node *hist, uint32_t color)
396 {
397  const uint32_t hash = ff_lowbias32(color) & (HIST_SIZE - 1);
398  struct hist_node *node = &hist[hash];
399  struct color_ref *e;
400 
401  for (int i = 0; i < node->nb_entries; i++) {
402  e = &node->entries[i];
403  if (e->color == color) {
404  e->count++;
405  return 0;
406  }
407  }
408 
409  e = av_dynarray2_add((void**)&node->entries, &node->nb_entries,
410  sizeof(*node->entries), NULL);
411  if (!e)
412  return AVERROR(ENOMEM);
413  e->color = color;
415  e->count = 1;
416  return 1;
417 }
418 
419 /**
420  * Update histogram when pixels differ from previous frame.
421  */
422 static int update_histogram_diff(struct hist_node *hist,
423  const AVFrame *f1, const AVFrame *f2)
424 {
425  int x, y, ret, nb_diff_colors = 0;
426 
427  for (y = 0; y < f1->height; y++) {
428  const uint32_t *p = (const uint32_t *)(f1->data[0] + y*f1->linesize[0]);
429  const uint32_t *q = (const uint32_t *)(f2->data[0] + y*f2->linesize[0]);
430 
431  for (x = 0; x < f1->width; x++) {
432  if (p[x] == q[x])
433  continue;
434  ret = color_inc(hist, p[x]);
435  if (ret < 0)
436  return ret;
437  nb_diff_colors += ret;
438  }
439  }
440  return nb_diff_colors;
441 }
442 
443 /**
444  * Simple histogram of the frame.
445  */
446 static int update_histogram_frame(struct hist_node *hist, const AVFrame *f)
447 {
448  int x, y, ret, nb_diff_colors = 0;
449 
450  for (y = 0; y < f->height; y++) {
451  const uint32_t *p = (const uint32_t *)(f->data[0] + y*f->linesize[0]);
452 
453  for (x = 0; x < f->width; x++) {
454  ret = color_inc(hist, p[x]);
455  if (ret < 0)
456  return ret;
457  nb_diff_colors += ret;
458  }
459  }
460  return nb_diff_colors;
461 }
462 
463 /**
464  * Update the histogram for each passing frame. No frame will be pushed here.
465  */
467 {
468  AVFilterContext *ctx = inlink->dst;
469  PaletteGenContext *s = ctx->priv;
470  int ret;
471 
473  av_log(ctx, AV_LOG_WARNING, "The input frame is not in sRGB, colors may be off\n");
474 
475  ret = s->prev_frame ? update_histogram_diff(s->histogram, s->prev_frame, in)
476  : update_histogram_frame(s->histogram, in);
477  if (ret > 0)
478  s->nb_refs += ret;
479 
480  if (s->stats_mode == STATS_MODE_DIFF_FRAMES) {
481  av_frame_free(&s->prev_frame);
482  s->prev_frame = in;
483  } else if (s->stats_mode == STATS_MODE_SINGLE_FRAMES && s->nb_refs > 0) {
484  AVFrame *out;
485  int i;
486 
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  av_frame_free(&in);
500  }
501 
502  return ret;
503 }
504 
505 /**
506  * Returns only one frame at the end containing the full palette.
507  */
508 static int request_frame(AVFilterLink *outlink)
509 {
510  AVFilterContext *ctx = outlink->src;
511  AVFilterLink *inlink = ctx->inputs[0];
512  PaletteGenContext *s = ctx->priv;
513  int r;
514 
516  if (r == AVERROR_EOF && !s->palette_pushed && s->nb_refs && s->stats_mode != STATS_MODE_SINGLE_FRAMES) {
517  r = ff_filter_frame(outlink, get_palette_frame(ctx));
518  s->palette_pushed = 1;
519  return r;
520  }
521  return r;
522 }
523 
524 /**
525  * The output is one simple 16x16 squared-pixels palette.
526  */
527 static int config_output(AVFilterLink *outlink)
528 {
529  outlink->w = outlink->h = 16;
530  outlink->sample_aspect_ratio = av_make_q(1, 1);
531  return 0;
532 }
533 
535 {
536  PaletteGenContext* s = ctx->priv;
537 
538  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  return 0;
544 }
545 
547 {
548  int i;
549  PaletteGenContext *s = ctx->priv;
550 
551  for (i = 0; i < HIST_SIZE; i++)
552  av_freep(&s->histogram[i].entries);
553  av_freep(&s->refs);
554  av_frame_free(&s->prev_frame);
555 }
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 
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,
583  .priv_class = &palettegen_class,
584 };
request_frame
static int request_frame(AVFilterLink *outlink)
Returns only one frame at the end containing the full palette.
Definition: vf_palettegen.c:508
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:112
AVFrame::color_trc
enum AVColorTransferCharacteristic color_trc
Definition: frame.h:657
AV_LOG_WARNING
#define AV_LOG_WARNING
Something somehow does not look correct.
Definition: log.h:186
AVPixelFormat
AVPixelFormat
Pixel format.
Definition: pixfmt.h:71
r
const char * r
Definition: vf_curves.c:127
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:436
config_output
static int config_output(AVFilterLink *outlink)
The output is one simple 16x16 squared-pixels palette.
Definition: vf_palettegen.c:527
out
FILE * out
Definition: movenc.c:55
color
Definition: vf_paletteuse.c:512
sort3id
static int sort3id(int64_t x, int64_t y, int64_t z)
Definition: vf_palettegen.c:152
ff_filter_frame
int ff_filter_frame(AVFilterLink *link, AVFrame *frame)
Send a frame of data to the next filter.
Definition: avfilter.c:1015
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:160
AVFrame
This structure describes decoded (raw) audio or video data.
Definition: frame.h:374
AVFrame::pts
int64_t pts
Presentation timestamp in time_base units (time when frame should be shown to user).
Definition: frame.h:486
AVFrame::width
int width
Definition: frame.h:446
PaletteGenContext::max_colors
int max_colors
Definition: vf_palettegen.c:74
range_box::cut_score
int64_t cut_score
Definition: vf_palettegen.c:51
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:343
AVOption
AVOption.
Definition: opt.h:357
b
#define b
Definition: input.c:41
AVCOL_TRC_UNSPECIFIED
@ AVCOL_TRC_UNSPECIFIED
Definition: pixfmt.h:583
FILTER_QUERY_FUNC
#define FILTER_QUERY_FUNC(func)
Definition: internal.h:159
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:317
cmp_color
static int cmp_color(const void *a, const void *b)
Simple color comparison for sorting the final palette.
Definition: vf_palettegen.c:167
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:422
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:463
hist_node::entries
struct color_ref * entries
Definition: vf_palettegen.c:58
AVFilter::name
const char * name
Filter name.
Definition: avfilter.h:170
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:286
video.h
hash
uint8_t hash[HASH_SIZE]
Definition: movenc.c:58
HIST_SIZE
#define HIST_SIZE
Definition: vf_palettegen.c:69
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:395
PaletteGenContext::refs
struct color_ref ** refs
Definition: vf_palettegen.c:80
formats.h
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:466
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:78
AVCOL_TRC_IEC61966_2_1
@ AVCOL_TRC_IEC61966_2_1
IEC 61966-2-1 (sRGB or sYCC)
Definition: pixfmt.h:594
Lab::b
int32_t b
Definition: palette.h:31
color_ref::count
int64_t count
Definition: vf_palettegen.c:42
AVFilterPad
A filter pad used for either input or output.
Definition: internal.h:33
FFDIFFSIGN
#define FFDIFFSIGN(x, y)
Comparator.
Definition: macros.h:45
ID_XYZ
@ ID_XYZ
Definition: vf_palettegen.c:136
ID_ZYX
@ ID_ZYX
Definition: vf_palettegen.c:136
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:534
FLAGS
#define FLAGS
Definition: vf_palettegen.c:89
NB_STATS_MODE
@ NB_STATS_MODE
Definition: vf_palettegen.c:66
intreadwrite.h
s
#define s(width, name)
Definition: cbs_vp9.c:198
ff_formats_ref
int ff_formats_ref(AVFilterFormats *f, AVFilterFormats **ref)
Add *ref as a new reference to formats.
Definition: formats.c:679
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:40
ctx
AVFormatContext * ctx
Definition: movenc.c:49
OFFSET
#define OFFSET(x)
Definition: vf_palettegen.c:88
STATS_MODE_SINGLE_FRAMES
@ STATS_MODE_SINGLE_FRAMES
Definition: vf_palettegen.c:65
ff_lowbias32
uint32_t ff_lowbias32(uint32_t x)
Definition: palette.c:211
sortstr
static const char *const sortstr[]
Definition: vf_palettegen.c:137
uninit
static av_cold void uninit(AVFilterContext *ctx)
Definition: vf_palettegen.c:546
FILTER_INPUTS
#define FILTER_INPUTS(array)
Definition: internal.h:182
compute_box_stats
static void compute_box_stats(PaletteGenContext *s, struct range_box *box)
Definition: vf_palettegen.c:174
ID_ZXY
@ ID_ZXY
Definition: vf_palettegen.c:136
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:116
query_formats
static int query_formats(AVFilterContext *ctx)
Definition: vf_palettegen.c:103
AV_OPT_TYPE_COLOR
@ AV_OPT_TYPE_COLOR
Definition: opt.h:260
hist_node
Definition: vf_palettegen.c:57
PaletteGenContext::palette_pushed
int palette_pushed
Definition: vf_palettegen.c:84
STATS_MODE_DIFF_FRAMES
@ STATS_MODE_DIFF_FRAMES
Definition: vf_palettegen.c:64
double
double
Definition: af_crystalizer.c:131
PaletteGenContext::nb_refs
int nb_refs
Definition: vf_palettegen.c:81
weight
static int weight(int i, int blen, int offset)
Definition: diracdec.c:1563
write_palette
static void write_palette(AVFilterContext *ctx, AVFrame *out)
Write the palette into the output frame.
Definition: vf_palettegen.c:253
ff_dlog
#define ff_dlog(a,...)
Definition: tableprint_vlc.h:28
PaletteGenContext::boxes
struct range_box boxes[256]
Definition: vf_palettegen.c:82
color_ref::color
uint32_t color
Definition: vf_palettegen.c:40
f
f
Definition: af_crystalizer.c:121
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:94
range_box::start
int start
Definition: vf_palettegen.c:52
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:118
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:53
PaletteGenContext::reserve_transparent
int reserve_transparent
Definition: vf_palettegen.c:75
range_box::weight
int64_t weight
Definition: vf_palettegen.c:50
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:213
AV_PIX_FMT_RGB32
#define AV_PIX_FMT_RGB32
Definition: pixfmt.h:451
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:41
palettegen_options
static const AVOption palettegen_options[]
Definition: vf_palettegen.c:90
PaletteGenContext
Definition: vf_palettegen.c:71
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:256
hist_node::nb_entries
int nb_entries
Definition: vf_palettegen.c:59
internal.h
range_box::avg
struct Lab avg
Definition: vf_palettegen.c:48
av_malloc_array
#define av_malloc_array(a, b)
Definition: tableprint_vlc.h:31
ID_XZY
@ ID_XZY
Definition: vf_palettegen.c:136
palettegen_outputs
static const AVFilterPad palettegen_outputs[]
Definition: vf_palettegen.c:565
AVFilterPad::name
const char * name
Pad name.
Definition: internal.h:39
AVFilter
Filter definition.
Definition: avfilter.h:166
update_histogram_frame
static int update_histogram_frame(struct hist_node *hist, const AVFrame *f)
Simple histogram of the frame.
Definition: vf_palettegen.c:446
ret
ret
Definition: filter_design.txt:187
range_box
Definition: vf_palettegen.c:46
color_ref
Definition: vf_palettegen.c:39
range_box::color
uint32_t color
Definition: vf_palettegen.c:47
AVFrame::height
int height
Definition: frame.h:446
cmp_funcs
static const cmp_func cmp_funcs[]
Definition: vf_palettegen.c:139
PaletteGenContext::histogram
struct hist_node histogram[HIST_SIZE]
Definition: vf_palettegen.c:79
AV_PIX_FMT_NONE
@ AV_PIX_FMT_NONE
Definition: pixfmt.h:72
AV_OPT_TYPE_INT
@ AV_OPT_TYPE_INT
Definition: opt.h:245
avfilter.h
palettegen_inputs
static const AVFilterPad palettegen_inputs[]
Definition: vf_palettegen.c:557
ref
static int ref[MAX_W *MAX_W]
Definition: jpeg2000dwt.c:112
L
#define L(x)
Definition: vpx_arith.h:36
AVFilterContext
An instance of a filter.
Definition: avfilter.h:407
AVMEDIA_TYPE_VIDEO
@ AVMEDIA_TYPE_VIDEO
Definition: avutil.h:201
mem.h
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:235
range_box::sorted_by
int sorted_by
Definition: vf_palettegen.c:54
AV_OPT_TYPE_BOOL
@ AV_OPT_TYPE_BOOL
Definition: opt.h:261
FILTER_OUTPUTS
#define FILTER_OUTPUTS(array)
Definition: internal.h:183
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:88
STATS_MODE_ALL_FRAMES
@ STATS_MODE_ALL_FRAMES
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:395
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:419
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:27
ff_vf_palettegen
const AVFilter ff_vf_palettegen
Definition: vf_palettegen.c:574
PaletteGenContext::stats_mode
int stats_mode
Definition: vf_palettegen.c:76
ID_YXZ
@ ID_YXZ
Definition: vf_palettegen.c:136
PaletteGenContext::transparency_color
uint8_t transparency_color[4]
Definition: vf_palettegen.c:85
set_colorquant_ratio_meta
static double set_colorquant_ratio_meta(AVFrame *out, int nb_out, int nb_in)
Definition: vf_palettegen.c:304
int
int
Definition: ffmpeg_filter.c:424
range_box::major_axis
int major_axis
Definition: vf_palettegen.c:49
ID_YZX
@ ID_YZX
Definition: vf_palettegen.c:136
AV_OPT_TYPE_CONST
@ AV_OPT_TYPE_CONST
Definition: opt.h:254
snprintf
#define snprintf
Definition: snprintf.h:34
PaletteGenContext::nb_boxes
int nb_boxes
Definition: vf_palettegen.c:83
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