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 "filters.h"
34 #include "formats.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;
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  AVFilterFormatsConfig **cfg_in,
105  AVFilterFormatsConfig **cfg_out)
106 {
107  static const enum AVPixelFormat in_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
108  static const enum AVPixelFormat out_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
109  int ret;
110 
111  if ((ret = ff_formats_ref(ff_make_format_list(in_fmts) , &cfg_in[0]->formats)) < 0)
112  return ret;
113  if ((ret = ff_formats_ref(ff_make_format_list(out_fmts), &cfg_out[0]->formats)) < 0)
114  return ret;
115  return 0;
116 }
117 
118 typedef int (*cmp_func)(const void *, const void *);
119 
120 #define DECLARE_CMP_FUNC(k0, k1, k2) \
121 static int cmp_##k0##k1##k2(const void *pa, const void *pb) \
122 { \
123  const struct color_ref * const *a = pa; \
124  const struct color_ref * const *b = pb; \
125  const int c0 = FFDIFFSIGN((*a)->lab.k0, (*b)->lab.k0); \
126  const int c1 = FFDIFFSIGN((*a)->lab.k1, (*b)->lab.k1); \
127  const int c2 = FFDIFFSIGN((*a)->lab.k2, (*b)->lab.k2); \
128  return c0 ? c0 : c1 ? c1 : c2; \
129 }
130 
137 
139 static const char * const sortstr[] = { "Lab", "Lba", "bLa", "aLb", "baL", "abL" };
140 
141 static const cmp_func cmp_funcs[] = {
142  [ID_XYZ] = cmp_Lab,
143  [ID_XZY] = cmp_Lba,
144  [ID_ZXY] = cmp_bLa,
145  [ID_YXZ] = cmp_aLb,
146  [ID_ZYX] = cmp_baL,
147  [ID_YZX] = cmp_abL,
148 };
149 
150 /*
151  * Return an identifier for the order of x, y, z (from higher to lower),
152  * preferring x over y and y over z in case of equality.
153  */
154 static int sort3id(int64_t x, int64_t y, int64_t z)
155 {
156  if (x >= y) {
157  if (y >= z) return ID_XYZ;
158  if (x >= z) return ID_XZY;
159  return ID_ZXY;
160  }
161  if (x >= z) return ID_YXZ;
162  if (y >= z) return ID_YZX;
163  return ID_ZYX;
164 }
165 
166 /**
167  * Simple color comparison for sorting the final palette
168  */
169 static int cmp_color(const void *a, const void *b)
170 {
171  const struct range_box *box1 = a;
172  const struct range_box *box2 = b;
173  return FFDIFFSIGN(box1->color, box2->color);
174 }
175 
176 static void compute_box_stats(PaletteGenContext *s, struct range_box *box)
177 {
178  int64_t er2[3] = {0};
179 
180  /* Compute average color */
181  int64_t sL = 0, sa = 0, sb = 0;
182  box->weight = 0;
183  for (int i = box->start; i < box->start + box->len; i++) {
184  const struct color_ref *ref = s->refs[i];
185  sL += ref->lab.L * ref->count;
186  sa += ref->lab.a * ref->count;
187  sb += ref->lab.b * ref->count;
188  box->weight += ref->count;
189  }
190  box->avg.L = sL / box->weight;
191  box->avg.a = sa / box->weight;
192  box->avg.b = sb / box->weight;
193 
194  /* Compute squared error of each color channel */
195  for (int i = box->start; i < box->start + box->len; i++) {
196  const struct color_ref *ref = s->refs[i];
197  const int64_t dL = ref->lab.L - box->avg.L;
198  const int64_t da = ref->lab.a - box->avg.a;
199  const int64_t db = ref->lab.b - box->avg.b;
200  er2[0] += dL * dL * ref->count;
201  er2[1] += da * da * ref->count;
202  er2[2] += db * db * ref->count;
203  }
204 
205  /* Define the best axis candidate for cutting the box */
206  box->major_axis = sort3id(er2[0], er2[1], er2[2]);
207 
208  /* The box that has the axis with the biggest error amongst all boxes will but cut down */
209  box->cut_score = FFMAX3(er2[0], er2[1], er2[2]);
210 }
211 
212 /**
213  * Find the next box to split: pick the one with the highest cut score
214  */
216 {
217  int best_box_id = -1;
218  int64_t max_score = -1;
219 
220  if (s->nb_boxes == s->max_colors - s->reserve_transparent)
221  return -1;
222 
223  for (int box_id = 0; box_id < s->nb_boxes; box_id++) {
224  const struct range_box *box = &s->boxes[box_id];
225  if (s->boxes[box_id].len >= 2 && box->cut_score > max_score) {
226  best_box_id = box_id;
227  max_score = box->cut_score;
228  }
229  }
230  return best_box_id;
231 }
232 
233 /**
234  * Split given box in two at position n. The original box becomes the left part
235  * of the split, and the new index box is the right part.
236  */
237 static void split_box(PaletteGenContext *s, struct range_box *box, int n)
238 {
239  struct range_box *new_box = &s->boxes[s->nb_boxes++];
240  new_box->start = n + 1;
241  new_box->len = box->start + box->len - new_box->start;
242  new_box->sorted_by = box->sorted_by;
243  box->len -= new_box->len;
244 
245  av_assert0(box->len >= 1);
246  av_assert0(new_box->len >= 1);
247 
248  compute_box_stats(s, box);
249  compute_box_stats(s, new_box);
250 }
251 
252 /**
253  * Write the palette into the output frame.
254  */
256 {
257  const PaletteGenContext *s = ctx->priv;
258  int box_id = 0;
259  uint32_t *pal = (uint32_t *)out->data[0];
260  const int pal_linesize = out->linesize[0] >> 2;
261  uint32_t last_color = 0;
262 
263  for (int y = 0; y < out->height; y++) {
264  for (int x = 0; x < out->width; x++) {
265  if (box_id < s->nb_boxes) {
266  pal[x] = s->boxes[box_id++].color;
267  if ((x || y) && pal[x] == last_color)
268  av_log(ctx, AV_LOG_WARNING, "Duped color: %08"PRIX32"\n", pal[x]);
269  last_color = pal[x];
270  } else {
271  pal[x] = last_color; // pad with last color
272  }
273  }
274  pal += pal_linesize;
275  }
276 
277  if (s->reserve_transparent) {
278  av_assert0(s->nb_boxes < 256);
279  pal[out->width - pal_linesize - 1] = AV_RB32(&s->transparency_color) >> 8;
280  }
281 }
282 
283 /**
284  * Crawl the histogram to get all the defined colors, and create a linear list
285  * of them (each color reference entry is a pointer to the value in the
286  * histogram/hash table).
287  */
288 static struct color_ref **load_color_refs(const struct hist_node *hist, int nb_refs)
289 {
290  int k = 0;
291  struct color_ref **refs = av_malloc_array(nb_refs, sizeof(*refs));
292 
293  if (!refs)
294  return NULL;
295 
296  for (int j = 0; j < HIST_SIZE; j++) {
297  const struct hist_node *node = &hist[j];
298 
299  for (int i = 0; i < node->nb_entries; i++)
300  refs[k++] = &node->entries[i];
301  }
302 
303  return refs;
304 }
305 
306 static double set_colorquant_ratio_meta(AVFrame *out, int nb_out, int nb_in)
307 {
308  char buf[32];
309  const double ratio = (double)nb_out / nb_in;
310  snprintf(buf, sizeof(buf), "%f", ratio);
311  av_dict_set(&out->metadata, "lavfi.color_quant_ratio", buf, 0);
312  return ratio;
313 }
314 
315 /**
316  * Main function implementing the Median Cut Algorithm defined by Paul Heckbert
317  * in Color Image Quantization for Frame Buffer Display (1982)
318  */
320 {
321  AVFrame *out;
322  PaletteGenContext *s = ctx->priv;
323  AVFilterLink *outlink = ctx->outputs[0];
324  double ratio;
325  int box_id = 0;
326  struct range_box *box;
327 
328  /* reference only the used colors from histogram */
329  s->refs = load_color_refs(s->histogram, s->nb_refs);
330  if (!s->refs) {
331  av_log(ctx, AV_LOG_ERROR, "Unable to allocate references for %d different colors\n", s->nb_refs);
332  return NULL;
333  }
334 
335  /* create the palette frame */
336  out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
337  if (!out)
338  return NULL;
339  out->pts = 0;
340 
341  /* set first box for 0..nb_refs */
342  box = &s->boxes[box_id];
343  box->len = s->nb_refs;
344  box->sorted_by = -1;
345  compute_box_stats(s, box);
346  s->nb_boxes = 1;
347 
348  while (box && box->len > 1) {
349  int i;
350  int64_t median, weight;
351 
352  ff_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" sort by %s (already sorted:%c) ",
353  box_id, box->start, box->start + box->len - 1, box->len, box->weight,
354  sortstr[box->major_axis], box->sorted_by == box->major_axis ? 'y':'n');
355 
356  /* sort the range by its major axis if it's not already sorted */
357  if (box->sorted_by != box->major_axis) {
358  cmp_func cmpf = cmp_funcs[box->major_axis];
359  qsort(&s->refs[box->start], box->len, sizeof(struct color_ref *), cmpf);
360  box->sorted_by = box->major_axis;
361  }
362 
363  /* locate the median where to split */
364  median = (box->weight + 1) >> 1;
365  weight = 0;
366  /* if you have 2 boxes, the maximum is actually #0: you must have at
367  * least 1 color on each side of the split, hence the -2 */
368  for (i = box->start; i < box->start + box->len - 2; i++) {
369  weight += s->refs[i]->count;
370  if (weight > median)
371  break;
372  }
373  ff_dlog(ctx, "split @ i=%-6d with w=%-6"PRIu64" (target=%6"PRIu64")\n", i, weight, median);
374  split_box(s, box, i);
375 
376  box_id = get_next_box_id_to_split(s);
377  box = box_id >= 0 ? &s->boxes[box_id] : NULL;
378  }
379 
380  ratio = set_colorquant_ratio_meta(out, s->nb_boxes, s->nb_refs);
381  av_log(ctx, AV_LOG_INFO, "%d%s colors generated out of %d colors; ratio=%f\n",
382  s->nb_boxes, s->reserve_transparent ? "(+1)" : "", s->nb_refs, ratio);
383 
384  for (int i = 0; i < s->nb_boxes; i++)
385  s->boxes[i].color = 0xffU<<24 | ff_oklab_int_to_srgb_u8(s->boxes[i].avg);
386 
387  qsort(s->boxes, s->nb_boxes, sizeof(*s->boxes), cmp_color);
388 
390 
391  return out;
392 }
393 
394 /**
395  * Locate the color in the hash table and increment its counter.
396  */
397 static int color_inc(struct hist_node *hist, uint32_t color)
398 {
399  const uint32_t hash = ff_lowbias32(color) & (HIST_SIZE - 1);
400  struct hist_node *node = &hist[hash];
401  struct color_ref *e;
402 
403  for (int i = 0; i < node->nb_entries; i++) {
404  e = &node->entries[i];
405  if (e->color == color) {
406  e->count++;
407  return 0;
408  }
409  }
410 
411  e = av_dynarray2_add((void**)&node->entries, &node->nb_entries,
412  sizeof(*node->entries), NULL);
413  if (!e)
414  return AVERROR(ENOMEM);
415  e->color = color;
417  e->count = 1;
418  return 1;
419 }
420 
421 /**
422  * Update histogram when pixels differ from previous frame.
423  */
424 static int update_histogram_diff(struct hist_node *hist,
425  const AVFrame *f1, const AVFrame *f2)
426 {
427  int x, y, ret, nb_diff_colors = 0;
428 
429  for (y = 0; y < f1->height; y++) {
430  const uint32_t *p = (const uint32_t *)(f1->data[0] + y*f1->linesize[0]);
431  const uint32_t *q = (const uint32_t *)(f2->data[0] + y*f2->linesize[0]);
432 
433  for (x = 0; x < f1->width; x++) {
434  if (p[x] == q[x])
435  continue;
436  ret = color_inc(hist, p[x]);
437  if (ret < 0)
438  return ret;
439  nb_diff_colors += ret;
440  }
441  }
442  return nb_diff_colors;
443 }
444 
445 /**
446  * Simple histogram of the frame.
447  */
448 static int update_histogram_frame(struct hist_node *hist, const AVFrame *f)
449 {
450  int x, y, ret, nb_diff_colors = 0;
451 
452  for (y = 0; y < f->height; y++) {
453  const uint32_t *p = (const uint32_t *)(f->data[0] + y*f->linesize[0]);
454 
455  for (x = 0; x < f->width; x++) {
456  ret = color_inc(hist, p[x]);
457  if (ret < 0)
458  return ret;
459  nb_diff_colors += ret;
460  }
461  }
462  return nb_diff_colors;
463 }
464 
465 /**
466  * Update the histogram for each passing frame. No frame will be pushed here.
467  */
469 {
470  AVFilterContext *ctx = inlink->dst;
471  PaletteGenContext *s = ctx->priv;
472  int ret;
473 
475  av_log(ctx, AV_LOG_WARNING, "The input frame is not in sRGB, colors may be off\n");
476 
477  ret = s->prev_frame ? update_histogram_diff(s->histogram, s->prev_frame, in)
478  : update_histogram_frame(s->histogram, in);
479  if (ret > 0)
480  s->nb_refs += ret;
481 
482  if (s->stats_mode == STATS_MODE_DIFF_FRAMES) {
483  av_frame_free(&s->prev_frame);
484  s->prev_frame = in;
485  } else if (s->stats_mode == STATS_MODE_SINGLE_FRAMES && s->nb_refs > 0) {
486  AVFrame *out;
487  int i;
488 
490  out->pts = in->pts;
491  av_frame_free(&in);
492  ret = ff_filter_frame(ctx->outputs[0], out);
493  for (i = 0; i < HIST_SIZE; i++)
494  av_freep(&s->histogram[i].entries);
495  av_freep(&s->refs);
496  s->nb_refs = 0;
497  s->nb_boxes = 0;
498  memset(s->boxes, 0, sizeof(s->boxes));
499  memset(s->histogram, 0, sizeof(s->histogram));
500  } else {
501  av_frame_free(&in);
502  }
503 
504  return ret;
505 }
506 
507 /**
508  * Returns only one frame at the end containing the full palette.
509  */
510 static int request_frame(AVFilterLink *outlink)
511 {
512  AVFilterContext *ctx = outlink->src;
513  AVFilterLink *inlink = ctx->inputs[0];
514  PaletteGenContext *s = ctx->priv;
515  int r;
516 
518  if (r == AVERROR_EOF && !s->palette_pushed && s->nb_refs && s->stats_mode != STATS_MODE_SINGLE_FRAMES) {
519  r = ff_filter_frame(outlink, get_palette_frame(ctx));
520  s->palette_pushed = 1;
521  return r;
522  }
523  return r;
524 }
525 
526 /**
527  * The output is one simple 16x16 squared-pixels palette.
528  */
529 static int config_output(AVFilterLink *outlink)
530 {
531  outlink->w = outlink->h = 16;
532  outlink->sample_aspect_ratio = av_make_q(1, 1);
533  return 0;
534 }
535 
537 {
538  PaletteGenContext* s = ctx->priv;
539 
540  if (s->max_colors - s->reserve_transparent < 2) {
541  av_log(ctx, AV_LOG_ERROR, "max_colors=2 is only allowed without reserving a transparent color slot\n");
542  return AVERROR(EINVAL);
543  }
544 
545  return 0;
546 }
547 
549 {
550  int i;
551  PaletteGenContext *s = ctx->priv;
552 
553  for (i = 0; i < HIST_SIZE; i++)
554  av_freep(&s->histogram[i].entries);
555  av_freep(&s->refs);
556  av_frame_free(&s->prev_frame);
557 }
558 
559 static const AVFilterPad palettegen_inputs[] = {
560  {
561  .name = "default",
562  .type = AVMEDIA_TYPE_VIDEO,
563  .filter_frame = filter_frame,
564  },
565 };
566 
567 static const AVFilterPad palettegen_outputs[] = {
568  {
569  .name = "default",
570  .type = AVMEDIA_TYPE_VIDEO,
571  .config_props = config_output,
572  .request_frame = request_frame,
573  },
574 };
575 
577  .name = "palettegen",
578  .description = NULL_IF_CONFIG_SMALL("Find the optimal palette for a given stream."),
579  .priv_size = sizeof(PaletteGenContext),
580  .init = init,
581  .uninit = uninit,
585  .priv_class = &palettegen_class,
586 };
request_frame
static int request_frame(AVFilterLink *outlink)
Returns only one frame at the end containing the full palette.
Definition: vf_palettegen.c:510
formats
formats
Definition: signature.h:47
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:116
AVFrame::color_trc
enum AVColorTransferCharacteristic color_trc
Definition: frame.h:672
AV_LOG_WARNING
#define AV_LOG_WARNING
Something somehow does not look correct.
Definition: log.h:215
AVPixelFormat
AVPixelFormat
Pixel format.
Definition: pixfmt.h:71
ID_YXZ
@ ID_YXZ
Definition: vf_palettegen.c:138
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:435
config_output
static int config_output(AVFilterLink *outlink)
The output is one simple 16x16 squared-pixels palette.
Definition: vf_palettegen.c:529
out
FILE * out
Definition: movenc.c:55
color
Definition: vf_paletteuse.c:513
sort3id
static int sort3id(int64_t x, int64_t y, int64_t z)
Definition: vf_palettegen.c:154
ff_filter_frame
int ff_filter_frame(AVFilterLink *link, AVFrame *frame)
Send a frame of data to the next filter.
Definition: avfilter.c:1062
AVERROR_EOF
#define AVERROR_EOF
End of file.
Definition: error.h:57
palette.h
int64_t
long long int64_t
Definition: coverity.c:34
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:162
FILTER_INPUTS
#define FILTER_INPUTS(array)
Definition: filters.h:262
AVFrame
This structure describes decoded (raw) audio or video data.
Definition: frame.h:389
AVFrame::pts
int64_t pts
Presentation timestamp in time_base units (time when frame should be shown to user).
Definition: frame.h:501
AVFrame::width
int width
Definition: frame.h:461
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:429
b
#define b
Definition: input.c:41
AVCOL_TRC_UNSPECIFIED
@ AVCOL_TRC_UNSPECIFIED
Definition: pixfmt.h:614
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:319
cmp_color
static int cmp_color(const void *a, const void *b)
Simple color comparison for sorting the final palette.
Definition: vf_palettegen.c:169
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:424
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:475
hist_node::entries
struct color_ref * entries
Definition: vf_palettegen.c:58
NB_STATS_MODE
@ NB_STATS_MODE
Definition: vf_palettegen.c:66
ID_XZY
@ ID_XZY
Definition: vf_palettegen.c:138
AVFilter::name
const char * name
Filter name.
Definition: avfilter.h:205
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:288
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:410
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:468
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:625
ID_YZX
@ ID_YZX
Definition: vf_palettegen.c:138
Lab::b
int32_t b
Definition: palette.h:31
color_ref::count
int64_t count
Definition: vf_palettegen.c:42
weight
const h264_weight_func weight
Definition: h264dsp_init.c:33
AVFilterPad
A filter pad used for either input or output.
Definition: filters.h:38
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:209
ID_ZYX
@ ID_ZYX
Definition: vf_palettegen.c:138
av_cold
#define av_cold
Definition: attributes.h:90
init
static int init(AVFilterContext *ctx)
Definition: vf_palettegen.c:536
FLAGS
#define FLAGS
Definition: vf_palettegen.c:89
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:678
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:40
filters.h
ctx
AVFormatContext * ctx
Definition: movenc.c:49
OFFSET
#define OFFSET(x)
Definition: vf_palettegen.c:88
ff_lowbias32
uint32_t ff_lowbias32(uint32_t x)
Definition: palette.c:211
sortstr
static const char *const sortstr[]
Definition: vf_palettegen.c:139
uninit
static av_cold void uninit(AVFilterContext *ctx)
Definition: vf_palettegen.c:548
FILTER_OUTPUTS
#define FILTER_OUTPUTS(array)
Definition: filters.h:263
compute_box_stats
static void compute_box_stats(PaletteGenContext *s, struct range_box *box)
Definition: vf_palettegen.c:176
AVClass
Describe the class of an AVClass context structure.
Definition: log.h:75
NULL
#define NULL
Definition: coverity.c:32
cmp_func
int(* cmp_func)(const void *, const void *)
Definition: vf_palettegen.c:118
ID_XYZ
@ ID_XYZ
Definition: vf_palettegen.c:138
AV_OPT_TYPE_COLOR
@ AV_OPT_TYPE_COLOR
Underlying C type is uint8_t[4].
Definition: opt.h:323
hist_node
Definition: vf_palettegen.c:57
PaletteGenContext::palette_pushed
int palette_pushed
Definition: vf_palettegen.c:84
double
double
Definition: af_crystalizer.c:132
PaletteGenContext::nb_refs
int nb_refs
Definition: vf_palettegen.c:81
STATS_MODE_SINGLE_FRAMES
@ STATS_MODE_SINGLE_FRAMES
Definition: vf_palettegen.c:65
AVFilterFormatsConfig
Lists of formats / etc.
Definition: avfilter.h:111
STATS_MODE_ALL_FRAMES
@ STATS_MODE_ALL_FRAMES
Definition: vf_palettegen.c:63
write_palette
static void write_palette(AVFilterContext *ctx, AVFrame *out)
Write the palette into the output frame.
Definition: vf_palettegen.c:255
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: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: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:120
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
query_formats
static int query_formats(const AVFilterContext *ctx, AVFilterFormatsConfig **cfg_in, AVFilterFormatsConfig **cfg_out)
Definition: vf_palettegen.c:103
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:215
AV_PIX_FMT_RGB32
#define AV_PIX_FMT_RGB32
Definition: pixfmt.h:475
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:220
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
FILTER_QUERY_FUNC2
#define FILTER_QUERY_FUNC2(func)
Definition: filters.h:239
palettegen_outputs
static const AVFilterPad palettegen_outputs[]
Definition: vf_palettegen.c:567
AVFilterPad::name
const char * name
Pad name.
Definition: filters.h:44
AVFilter
Filter definition.
Definition: avfilter.h:201
update_histogram_frame
static int update_histogram_frame(struct hist_node *hist, const AVFrame *f)
Simple histogram of the frame.
Definition: vf_palettegen.c:448
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:461
STATS_MODE_DIFF_FRAMES
@ STATS_MODE_DIFF_FRAMES
Definition: vf_palettegen.c:64
cmp_funcs
static const cmp_func cmp_funcs[]
Definition: vf_palettegen.c:141
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
Underlying C type is int.
Definition: opt.h:259
avfilter.h
palettegen_inputs
static const AVFilterPad palettegen_inputs[]
Definition: vf_palettegen.c:559
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:457
ID_ZXY
@ ID_ZXY
Definition: vf_palettegen.c:138
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:237
range_box::sorted_by
int sorted_by
Definition: vf_palettegen.c:54
AV_OPT_TYPE_BOOL
@ AV_OPT_TYPE_BOOL
Underlying C type is int.
Definition: opt.h:327
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
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:397
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:434
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:27
ff_vf_palettegen
const AVFilter ff_vf_palettegen
Definition: vf_palettegen.c:576
PaletteGenContext::stats_mode
int stats_mode
Definition: vf_palettegen.c:76
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:306
range_box::major_axis
int major_axis
Definition: vf_palettegen.c:49
AV_OPT_TYPE_CONST
@ AV_OPT_TYPE_CONST
Special option type for declaring named constants.
Definition: opt.h:299
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