FFmpeg
vf_palettegen.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 Stupeflix
3  *
4  * This file is part of FFmpeg.
5  *
6  * FFmpeg is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * FFmpeg is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with FFmpeg; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20 
21 /**
22  * @file
23  * Generate one palette for a whole video stream.
24  */
25 
26 #include "libavutil/avassert.h"
27 #include "libavutil/internal.h"
28 #include "libavutil/opt.h"
29 #include "libavutil/qsort.h"
30 #include "libavutil/intreadwrite.h"
31 #include "avfilter.h"
32 #include "internal.h"
33 
34 /* Reference a color and how much it's used */
35 struct color_ref {
36  uint32_t color;
37  uint64_t count;
38 };
39 
40 /* Store a range of colors */
41 struct range_box {
42  uint32_t color; // average color
43  int64_t variance; // overall variance of the box (how much the colors are spread)
44  int start; // index in PaletteGenContext->refs
45  int len; // number of referenced colors
46  int sorted_by; // whether range of colors is sorted by red (0), green (1) or blue (2)
47 };
48 
49 struct hist_node {
50  struct color_ref *entries;
52 };
53 
54 enum {
59 };
60 
61 #define NBITS 5
62 #define HIST_SIZE (1<<(4*NBITS))
63 
64 typedef struct PaletteGenContext {
65  const AVClass *class;
66 
70  int use_alpha;
71 
72  AVFrame *prev_frame; // previous frame used for the diff stats_mode
73  struct hist_node histogram[HIST_SIZE]; // histogram/hashtable of the colors
74  struct color_ref **refs; // references of all the colors used in the stream
75  int nb_refs; // number of color references (or number of different colors)
76  struct range_box boxes[256]; // define the segmentation of the colorspace (the final palette)
77  int nb_boxes; // number of boxes (increase will segmenting them)
78  int palette_pushed; // if the palette frame is pushed into the outlink or not
79  uint8_t transparency_color[4]; // background color for transparency
81 
82 #define OFFSET(x) offsetof(PaletteGenContext, x)
83 #define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
84 static const AVOption palettegen_options[] = {
85  { "max_colors", "set the maximum number of colors to use in the palette", OFFSET(max_colors), AV_OPT_TYPE_INT, {.i64=256}, 4, 256, FLAGS },
86  { "reserve_transparent", "reserve a palette entry for transparency", OFFSET(reserve_transparent), AV_OPT_TYPE_BOOL, {.i64=1}, 0, 1, FLAGS },
87  { "transparency_color", "set a background color for transparency", OFFSET(transparency_color), AV_OPT_TYPE_COLOR, {.str="lime"}, 0, 0, FLAGS },
88  { "stats_mode", "set statistics mode", OFFSET(stats_mode), AV_OPT_TYPE_INT, {.i64=STATS_MODE_ALL_FRAMES}, 0, NB_STATS_MODE-1, FLAGS, "mode" },
89  { "full", "compute full frame histograms", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_ALL_FRAMES}, INT_MIN, INT_MAX, FLAGS, "mode" },
90  { "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" },
91  { "single", "compute new histogram for each frame", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_SINGLE_FRAMES}, INT_MIN, INT_MAX, FLAGS, "mode" },
92  { "use_alpha", "create a palette including alpha values", OFFSET(use_alpha), AV_OPT_TYPE_BOOL, {.i64 = 0}, 0, 1, FLAGS },
93  { NULL }
94 };
95 
96 AVFILTER_DEFINE_CLASS(palettegen);
97 
99 {
100  static const enum AVPixelFormat in_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
101  static const enum AVPixelFormat out_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
102  int ret;
103 
104  if ((ret = ff_formats_ref(ff_make_format_list(in_fmts) , &ctx->inputs[0]->outcfg.formats)) < 0)
105  return ret;
106  if ((ret = ff_formats_ref(ff_make_format_list(out_fmts), &ctx->outputs[0]->incfg.formats)) < 0)
107  return ret;
108  return 0;
109 }
110 
111 typedef int (*cmp_func)(const void *, const void *);
112 
113 #define DECLARE_CMP_FUNC(name, pos) \
114 static int cmp_##name(const void *pa, const void *pb) \
115 { \
116  const struct color_ref * const *a = pa; \
117  const struct color_ref * const *b = pb; \
118  return (int)((*a)->color >> (8 * (3 - (pos))) & 0xff) \
119  - (int)((*b)->color >> (8 * (3 - (pos))) & 0xff); \
120 }
121 
126 
127 static const cmp_func cmp_funcs[] = {cmp_a, cmp_r, cmp_g, cmp_b};
128 
129 /**
130  * Simple color comparison for sorting the final palette
131  */
132 static int cmp_color(const void *a, const void *b)
133 {
134  const struct range_box *box1 = a;
135  const struct range_box *box2 = b;
136  return FFDIFFSIGN(box1->color , box2->color);
137 }
138 
139 static av_always_inline int diff(const uint32_t a, const uint32_t b)
140 {
141  const uint8_t c1[] = {a >> 16 & 0xff, a >> 8 & 0xff, a & 0xff};
142  const uint8_t c2[] = {b >> 16 & 0xff, b >> 8 & 0xff, b & 0xff};
143  const int dr = c1[0] - c2[0];
144  const int dg = c1[1] - c2[1];
145  const int db = c1[2] - c2[2];
146  return dr*dr + dg*dg + db*db;
147 }
148 
149 static av_always_inline int diff_alpha(const uint32_t a, const uint32_t b)
150 {
151  const uint8_t c1[] = {a >> 24 & 0xff, a >> 16 & 0xff, a >> 8 & 0xff, a & 0xff};
152  const uint8_t c2[] = {b >> 24 & 0xff, b >> 16 & 0xff, b >> 8 & 0xff, b & 0xff};
153  const int da = c1[0] - c2[0];
154  const int dr = c1[1] - c2[1];
155  const int dg = c1[2] - c2[2];
156  const int db = c1[3] - c2[3];
157  return da*da + dr*dr + dg*dg + db*db;
158 }
159 
160 /**
161  * Find the next box to split: pick the one with the highest variance
162  */
164 {
165  int box_id, i, best_box_id = -1;
166  int64_t max_variance = -1;
167 
168  if (s->nb_boxes == s->max_colors - s->reserve_transparent)
169  return -1;
170 
171  for (box_id = 0; box_id < s->nb_boxes; box_id++) {
172  struct range_box *box = &s->boxes[box_id];
173 
174  if (s->boxes[box_id].len >= 2) {
175 
176  if (box->variance == -1) {
177  int64_t variance = 0;
178 
179  for (i = 0; i < box->len; i++) {
180  const struct color_ref *ref = s->refs[box->start + i];
181  if (s->use_alpha)
182  variance += (int64_t)diff_alpha(ref->color, box->color) * ref->count;
183  else
184  variance += (int64_t)diff(ref->color, box->color) * ref->count;
185  }
186  box->variance = variance;
187  }
188  if (box->variance > max_variance) {
189  best_box_id = box_id;
190  max_variance = box->variance;
191  }
192  } else {
193  box->variance = -1;
194  }
195  }
196  return best_box_id;
197 }
198 
199 /**
200  * Get the 32-bit average color for the range of RGB colors enclosed in the
201  * specified box. Takes into account the weight of each color.
202  */
203 static uint32_t get_avg_color(struct color_ref * const *refs,
204  const struct range_box *box, int use_alpha)
205 {
206  int i;
207  const int n = box->len;
208  uint64_t a = 0, r = 0, g = 0, b = 0, div = 0;
209 
210  for (i = 0; i < n; i++) {
211  const struct color_ref *ref = refs[box->start + i];
212  if (use_alpha)
213  a += (ref->color >> 24 & 0xff) * ref->count;
214  r += (ref->color >> 16 & 0xff) * ref->count;
215  g += (ref->color >> 8 & 0xff) * ref->count;
216  b += (ref->color & 0xff) * ref->count;
217  div += ref->count;
218  }
219 
220  if (use_alpha)
221  a = a / div;
222  r = r / div;
223  g = g / div;
224  b = b / div;
225 
226  if (use_alpha)
227  return a<<24 | r<<16 | g<<8 | b;
228 
229  return 0xffU<<24 | r<<16 | g<<8 | b;
230 }
231 
232 /**
233  * Split given box in two at position n. The original box becomes the left part
234  * of the split, and the new index box is the right part.
235  */
236 static void split_box(PaletteGenContext *s, struct range_box *box, int n)
237 {
238  struct range_box *new_box = &s->boxes[s->nb_boxes++];
239  new_box->start = n + 1;
240  new_box->len = box->start + box->len - new_box->start;
241  new_box->sorted_by = box->sorted_by;
242  box->len -= new_box->len;
243 
244  av_assert0(box->len >= 1);
245  av_assert0(new_box->len >= 1);
246 
247  box->color = get_avg_color(s->refs, box, s->use_alpha);
248  new_box->color = get_avg_color(s->refs, new_box, s->use_alpha);
249  box->variance = -1;
250  new_box->variance = -1;
251 }
252 
253 /**
254  * Write the palette into the output frame.
255  */
257 {
258  const PaletteGenContext *s = ctx->priv;
259  int x, y, box_id = 0;
260  uint32_t *pal = (uint32_t *)out->data[0];
261  const int pal_linesize = out->linesize[0] >> 2;
262  uint32_t last_color = 0;
263 
264  for (y = 0; y < out->height; y++) {
265  for (x = 0; x < out->width; x++) {
266  if (box_id < s->nb_boxes) {
267  pal[x] = s->boxes[box_id++].color;
268  if ((x || y) && pal[x] == last_color)
269  av_log(ctx, AV_LOG_WARNING, "Duped color: %08"PRIX32"\n", pal[x]);
270  last_color = pal[x];
271  } else {
272  pal[x] = last_color; // pad with last color
273  }
274  }
275  pal += pal_linesize;
276  }
277 
278  if (s->reserve_transparent && !s->use_alpha) {
279  av_assert0(s->nb_boxes < 256);
280  pal[out->width - pal_linesize - 1] = AV_RB32(&s->transparency_color) >> 8;
281  }
282 }
283 
284 /**
285  * Crawl the histogram to get all the defined colors, and create a linear list
286  * of them (each color reference entry is a pointer to the value in the
287  * histogram/hash table).
288  */
289 static struct color_ref **load_color_refs(const struct hist_node *hist, int nb_refs)
290 {
291  int i, j, k = 0;
292  struct color_ref **refs = av_malloc_array(nb_refs, sizeof(*refs));
293 
294  if (!refs)
295  return NULL;
296 
297  for (j = 0; j < HIST_SIZE; j++) {
298  const struct hist_node *node = &hist[j];
299 
300  for (i = 0; i < node->nb_entries; i++)
301  refs[k++] = &node->entries[i];
302  }
303 
304  return refs;
305 }
306 
307 static double set_colorquant_ratio_meta(AVFrame *out, int nb_out, int nb_in)
308 {
309  char buf[32];
310  const double ratio = (double)nb_out / nb_in;
311  snprintf(buf, sizeof(buf), "%f", ratio);
312  av_dict_set(&out->metadata, "lavfi.color_quant_ratio", buf, 0);
313  return ratio;
314 }
315 
316 /**
317  * Main function implementing the Median Cut Algorithm defined by Paul Heckbert
318  * in Color Image Quantization for Frame Buffer Display (1982)
319  */
321 {
322  AVFrame *out;
323  PaletteGenContext *s = ctx->priv;
324  AVFilterLink *outlink = ctx->outputs[0];
325  double ratio;
326  int box_id = 0;
327  struct range_box *box;
328 
329  /* reference only the used colors from histogram */
330  s->refs = load_color_refs(s->histogram, s->nb_refs);
331  if (!s->refs) {
332  av_log(ctx, AV_LOG_ERROR, "Unable to allocate references for %d different colors\n", s->nb_refs);
333  return NULL;
334  }
335 
336  /* create the palette frame */
337  out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
338  if (!out)
339  return NULL;
340  out->pts = 0;
341 
342  /* set first box for 0..nb_refs */
343  box = &s->boxes[box_id];
344  box->len = s->nb_refs;
345  box->sorted_by = -1;
346  box->color = get_avg_color(s->refs, box, s->use_alpha);
347  box->variance = -1;
348  s->nb_boxes = 1;
349 
350  while (box && box->len > 1) {
351  int i, ar, rr, gr, br, longest;
352  uint64_t median, box_weight = 0;
353 
354  /* compute the box weight (sum all the weights of the colors in the
355  * range) and its boundings */
356  uint8_t min[4] = {0xff, 0xff, 0xff, 0xff};
357  uint8_t max[4] = {0x00, 0x00, 0x00, 0x00};
358  for (i = box->start; i < box->start + box->len; i++) {
359  const struct color_ref *ref = s->refs[i];
360  const uint32_t rgb = ref->color;
361  const uint8_t a = rgb >> 24 & 0xff, r = rgb >> 16 & 0xff, g = rgb >> 8 & 0xff, b = rgb & 0xff;
362  min[0] = FFMIN(a, min[0]); max[0] = FFMAX(a, max[0]);
363  min[1] = FFMIN(r, min[1]); max[1] = FFMAX(r, max[1]);
364  min[2] = FFMIN(g, min[2]); max[2] = FFMAX(g, max[2]);
365  min[3] = FFMIN(b, min[3]); max[3] = FFMAX(b, max[3]);
366  box_weight += ref->count;
367  }
368 
369  /* define the axis to sort by according to the widest range of colors */
370  ar = max[0] - min[0];
371  rr = max[1] - min[1];
372  gr = max[2] - min[2];
373  br = max[3] - min[3];
374  longest = 2; // pick green by default (the color the eye is the most sensitive to)
375  if (s->use_alpha) {
376  if (ar >= rr && ar >= br && ar >= gr) longest = 0;
377  if (br >= rr && br >= gr && br >= ar) longest = 3;
378  if (rr >= gr && rr >= br && rr >= ar) longest = 1;
379  if (gr >= rr && gr >= br && gr >= ar) longest = 2; // prefer green again
380  } else {
381  if (br >= rr && br >= gr) longest = 3;
382  if (rr >= gr && rr >= br) longest = 1;
383  if (gr >= rr && gr >= br) longest = 2; // prefer green again
384  }
385 
386  ff_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" ranges:[%2x %2x %2x %2x] sort by %c (already sorted:%c) ",
387  box_id, box->start, box->start + box->len - 1, box->len, box_weight,
388  ar, rr, gr, br, "argb"[longest], box->sorted_by == longest ? 'y' : 'n');
389 
390  /* sort the range by its longest axis if it's not already sorted */
391  if (box->sorted_by != longest) {
392  cmp_func cmpf = cmp_funcs[longest];
393  AV_QSORT(&s->refs[box->start], box->len, const struct color_ref *, cmpf);
394  box->sorted_by = longest;
395  }
396 
397  /* locate the median where to split */
398  median = (box_weight + 1) >> 1;
399  box_weight = 0;
400  /* if you have 2 boxes, the maximum is actually #0: you must have at
401  * least 1 color on each side of the split, hence the -2 */
402  for (i = box->start; i < box->start + box->len - 2; i++) {
403  box_weight += s->refs[i]->count;
404  if (box_weight > median)
405  break;
406  }
407  ff_dlog(ctx, "split @ i=%-6d with w=%-6"PRIu64" (target=%6"PRIu64")\n", i, box_weight, median);
408  split_box(s, box, i);
409 
410  box_id = get_next_box_id_to_split(s);
411  box = box_id >= 0 ? &s->boxes[box_id] : NULL;
412  }
413 
414  ratio = set_colorquant_ratio_meta(out, s->nb_boxes, s->nb_refs);
415  av_log(ctx, AV_LOG_INFO, "%d%s colors generated out of %d colors; ratio=%f\n",
416  s->nb_boxes, s->reserve_transparent ? "(+1)" : "", s->nb_refs, ratio);
417 
418  qsort(s->boxes, s->nb_boxes, sizeof(*s->boxes), cmp_color);
419 
421 
422  return out;
423 }
424 
425 /**
426  * Hashing function for the color.
427  * It keeps the NBITS least significant bit of each component to make it
428  * "random" even if the scene doesn't have much different colors.
429  */
430 static inline unsigned color_hash(uint32_t color, int use_alpha)
431 {
432  const uint8_t r = color >> 16 & ((1<<NBITS)-1);
433  const uint8_t g = color >> 8 & ((1<<NBITS)-1);
434  const uint8_t b = color & ((1<<NBITS)-1);
435 
436  if (use_alpha) {
437  const uint8_t a = color >> 24 & ((1 << NBITS) - 1);
438  return a << (NBITS * 3) | r << (NBITS * 2) | g << NBITS | b;
439  }
440 
441  return r << (NBITS * 2) | g << NBITS | b;
442 }
443 
444 /**
445  * Locate the color in the hash table and increment its counter.
446  */
447 static int color_inc(struct hist_node *hist, uint32_t color, int use_alpha)
448 {
449  int i;
450  const unsigned hash = color_hash(color, use_alpha);
451  struct hist_node *node = &hist[hash];
452  struct color_ref *e;
453 
454  for (i = 0; i < node->nb_entries; i++) {
455  e = &node->entries[i];
456  if (e->color == color) {
457  e->count++;
458  return 0;
459  }
460  }
461 
462  e = av_dynarray2_add((void**)&node->entries, &node->nb_entries,
463  sizeof(*node->entries), NULL);
464  if (!e)
465  return AVERROR(ENOMEM);
466  e->color = color;
467  e->count = 1;
468  return 1;
469 }
470 
471 /**
472  * Update histogram when pixels differ from previous frame.
473  */
474 static int update_histogram_diff(struct hist_node *hist,
475  const AVFrame *f1, const AVFrame *f2, int use_alpha)
476 {
477  int x, y, ret, nb_diff_colors = 0;
478 
479  for (y = 0; y < f1->height; y++) {
480  const uint32_t *p = (const uint32_t *)(f1->data[0] + y*f1->linesize[0]);
481  const uint32_t *q = (const uint32_t *)(f2->data[0] + y*f2->linesize[0]);
482 
483  for (x = 0; x < f1->width; x++) {
484  if (p[x] == q[x])
485  continue;
486  ret = color_inc(hist, p[x], use_alpha);
487  if (ret < 0)
488  return ret;
489  nb_diff_colors += ret;
490  }
491  }
492  return nb_diff_colors;
493 }
494 
495 /**
496  * Simple histogram of the frame.
497  */
498 static int update_histogram_frame(struct hist_node *hist, const AVFrame *f, int use_alpha)
499 {
500  int x, y, ret, nb_diff_colors = 0;
501 
502  for (y = 0; y < f->height; y++) {
503  const uint32_t *p = (const uint32_t *)(f->data[0] + y*f->linesize[0]);
504 
505  for (x = 0; x < f->width; x++) {
506  ret = color_inc(hist, p[x], use_alpha);
507  if (ret < 0)
508  return ret;
509  nb_diff_colors += ret;
510  }
511  }
512  return nb_diff_colors;
513 }
514 
515 /**
516  * Update the histogram for each passing frame. No frame will be pushed here.
517  */
519 {
520  AVFilterContext *ctx = inlink->dst;
521  PaletteGenContext *s = ctx->priv;
522  int ret = s->prev_frame ? update_histogram_diff(s->histogram, s->prev_frame, in, s->use_alpha)
523  : update_histogram_frame(s->histogram, in, s->use_alpha);
524 
525  if (ret > 0)
526  s->nb_refs += ret;
527 
528  if (s->stats_mode == STATS_MODE_DIFF_FRAMES) {
529  av_frame_free(&s->prev_frame);
530  s->prev_frame = in;
531  } else if (s->stats_mode == STATS_MODE_SINGLE_FRAMES && s->nb_refs > 0) {
532  AVFrame *out;
533  int i;
534 
536  out->pts = in->pts;
537  av_frame_free(&in);
538  ret = ff_filter_frame(ctx->outputs[0], out);
539  for (i = 0; i < HIST_SIZE; i++)
540  av_freep(&s->histogram[i].entries);
541  av_freep(&s->refs);
542  s->nb_refs = 0;
543  s->nb_boxes = 0;
544  memset(s->boxes, 0, sizeof(s->boxes));
545  memset(s->histogram, 0, sizeof(s->histogram));
546  } else {
547  av_frame_free(&in);
548  }
549 
550  return ret;
551 }
552 
553 /**
554  * Returns only one frame at the end containing the full palette.
555  */
556 static int request_frame(AVFilterLink *outlink)
557 {
558  AVFilterContext *ctx = outlink->src;
559  AVFilterLink *inlink = ctx->inputs[0];
560  PaletteGenContext *s = ctx->priv;
561  int r;
562 
564  if (r == AVERROR_EOF && !s->palette_pushed && s->nb_refs && s->stats_mode != STATS_MODE_SINGLE_FRAMES) {
565  r = ff_filter_frame(outlink, get_palette_frame(ctx));
566  s->palette_pushed = 1;
567  return r;
568  }
569  return r;
570 }
571 
572 /**
573  * The output is one simple 16x16 squared-pixels palette.
574  */
575 static int config_output(AVFilterLink *outlink)
576 {
577  outlink->w = outlink->h = 16;
578  outlink->sample_aspect_ratio = av_make_q(1, 1);
579  return 0;
580 }
581 
583 {
584  PaletteGenContext* s = ctx->priv;
585 
586  if (s->use_alpha && s->reserve_transparent)
587  s->reserve_transparent = 0;
588 
589  return 0;
590 }
591 
593 {
594  int i;
595  PaletteGenContext *s = ctx->priv;
596 
597  for (i = 0; i < HIST_SIZE; i++)
598  av_freep(&s->histogram[i].entries);
599  av_freep(&s->refs);
600  av_frame_free(&s->prev_frame);
601 }
602 
603 static const AVFilterPad palettegen_inputs[] = {
604  {
605  .name = "default",
606  .type = AVMEDIA_TYPE_VIDEO,
607  .filter_frame = filter_frame,
608  },
609 };
610 
611 static const AVFilterPad palettegen_outputs[] = {
612  {
613  .name = "default",
614  .type = AVMEDIA_TYPE_VIDEO,
615  .config_props = config_output,
616  .request_frame = request_frame,
617  },
618 };
619 
621  .name = "palettegen",
622  .description = NULL_IF_CONFIG_SMALL("Find the optimal palette for a given stream."),
623  .priv_size = sizeof(PaletteGenContext),
624  .init = init,
625  .uninit = uninit,
629  .priv_class = &palettegen_class,
630 };
request_frame
static int request_frame(AVFilterLink *outlink)
Returns only one frame at the end containing the full palette.
Definition: vf_palettegen.c:556
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
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:116
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:575
out
FILE * out
Definition: movenc.c:54
color
Definition: vf_paletteuse.c:600
ff_filter_frame
int ff_filter_frame(AVFilterLink *link, AVFrame *frame)
Send a frame of data to the next filter.
Definition: avfilter.c:999
AVERROR_EOF
#define AVERROR_EOF
End of file.
Definition: error.h:57
NBITS
#define NBITS
Definition: vf_palettegen.c:61
DECLARE_CMP_FUNC
#define DECLARE_CMP_FUNC(name, pos)
Definition: vf_palettegen.c:113
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
STATS_MODE_SINGLE_FRAMES
@ STATS_MODE_SINGLE_FRAMES
Definition: vf_palettegen.c:57
av_frame_free
void av_frame_free(AVFrame **frame)
Free the frame and any dynamically allocated objects in it, e.g.
Definition: frame.c:111
AVFrame
This structure describes decoded (raw) audio or video data.
Definition: frame.h:325
AVFrame::pts
int64_t pts
Presentation timestamp in time_base units (time when frame should be shown to user).
Definition: frame.h:432
AVFrame::width
int width
Definition: frame.h:397
PaletteGenContext::max_colors
int max_colors
Definition: vf_palettegen.c:67
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:34
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:320
cmp_color
static int cmp_color(const void *a, const void *b)
Simple color comparison for sorting the final palette.
Definition: vf_palettegen.c:132
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:400
range_box::variance
int64_t variance
Definition: vf_palettegen.c:43
hist_node::entries
struct color_ref * entries
Definition: vf_palettegen.c:50
color_ref::count
uint64_t count
Definition: vf_palettegen.c:37
max
#define max(a, b)
Definition: cuda_runtime.h:33
FFMAX
#define FFMAX(a, b)
Definition: macros.h:47
AVFilter::name
const char * name
Filter name.
Definition: avfilter.h:175
c1
static const uint64_t c1
Definition: murmur3.c:51
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:289
hash
uint8_t hash[HASH_SIZE]
Definition: movenc.c:57
color_inc
static int color_inc(struct hist_node *hist, uint32_t color, int use_alpha)
Locate the color in the hash table and increment its counter.
Definition: vf_palettegen.c:447
HIST_SIZE
#define HIST_SIZE
Definition: vf_palettegen.c:62
AVFrame::data
uint8_t * data[AV_NUM_DATA_POINTERS]
pointer to the picture/channel planes.
Definition: frame.h:346
PaletteGenContext::refs
struct color_ref ** refs
Definition: vf_palettegen.c:74
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:518
rgb
Definition: rpzaenc.c:59
PaletteGenContext::prev_frame
AVFrame * prev_frame
Definition: vf_palettegen.c:72
U
#define U(x)
Definition: vp56_arith.h:37
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:582
FLAGS
#define FLAGS
Definition: vf_palettegen.c:83
intreadwrite.h
s
#define s(width, name)
Definition: cbs_vp9.c:256
g
const char * g
Definition: vf_curves.c:117
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:82
NB_STATS_MODE
@ NB_STATS_MODE
Definition: vf_palettegen.c:58
uninit
static av_cold void uninit(AVFilterContext *ctx)
Definition: vf_palettegen.c:592
FILTER_INPUTS
#define FILTER_INPUTS(array)
Definition: internal.h:190
AVClass
Describe the class of an AVClass context structure.
Definition: log.h:66
get_avg_color
static uint32_t get_avg_color(struct color_ref *const *refs, const struct range_box *box, int use_alpha)
Get the 32-bit average color for the range of RGB colors enclosed in the specified box.
Definition: vf_palettegen.c:203
NULL
#define NULL
Definition: coverity.c:32
cmp_func
int(* cmp_func)(const void *, const void *)
Definition: vf_palettegen.c:111
query_formats
static int query_formats(AVFilterContext *ctx)
Definition: vf_palettegen.c:98
AV_OPT_TYPE_COLOR
@ AV_OPT_TYPE_COLOR
Definition: opt.h:240
hist_node
Definition: vf_palettegen.c:49
PaletteGenContext::palette_pushed
int palette_pushed
Definition: vf_palettegen.c:78
double
double
Definition: af_crystalizer.c:132
PaletteGenContext::nb_refs
int nb_refs
Definition: vf_palettegen.c:75
write_palette
static void write_palette(AVFilterContext *ctx, AVFrame *out)
Write the palette into the output frame.
Definition: vf_palettegen.c:256
ff_dlog
#define ff_dlog(a,...)
Definition: tableprint_vlc.h:28
STATS_MODE_ALL_FRAMES
@ STATS_MODE_ALL_FRAMES
Definition: vf_palettegen.c:55
PaletteGenContext::boxes
struct range_box boxes[256]
Definition: vf_palettegen.c:76
color_ref::color
uint32_t color
Definition: vf_palettegen.c:36
qsort.h
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:117
range_box::start
int start
Definition: vf_palettegen.c:44
diff_alpha
static av_always_inline int diff_alpha(const uint32_t a, const uint32_t b)
Definition: vf_palettegen.c:149
for
for(k=2;k<=8;++k)
Definition: h264pred_template.c:425
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:45
PaletteGenContext::reserve_transparent
int reserve_transparent
Definition: vf_palettegen.c:68
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 variance.
Definition: vf_palettegen.c:163
AV_PIX_FMT_RGB32
#define AV_PIX_FMT_RGB32
Definition: pixfmt.h:379
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
palettegen_options
static const AVOption palettegen_options[]
Definition: vf_palettegen.c:84
PaletteGenContext
Definition: vf_palettegen.c:64
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
AV_QSORT
#define AV_QSORT(p, num, type, cmp)
Quicksort This sort is fast, and fully inplace but not stable and it is possible to construct input t...
Definition: qsort.h:33
hist_node::nb_entries
int nb_entries
Definition: vf_palettegen.c:51
internal.h
av_malloc_array
#define av_malloc_array(a, b)
Definition: tableprint_vlc.h:31
av_always_inline
#define av_always_inline
Definition: attributes.h:49
palettegen_outputs
static const AVFilterPad palettegen_outputs[]
Definition: vf_palettegen.c:611
FFMIN
#define FFMIN(a, b)
Definition: macros.h:49
AVFilterPad::name
const char * name
Pad name.
Definition: internal.h:55
update_histogram_frame
static int update_histogram_frame(struct hist_node *hist, const AVFrame *f, int use_alpha)
Simple histogram of the frame.
Definition: vf_palettegen.c:498
AVFilter
Filter definition.
Definition: avfilter.h:171
ret
ret
Definition: filter_design.txt:187
range_box
Definition: vf_palettegen.c:41
color_ref
Definition: vf_palettegen.c:35
range_box::color
uint32_t color
Definition: vf_palettegen.c:42
AVFrame::height
int height
Definition: frame.h:397
c2
static const uint64_t c2
Definition: murmur3.c:52
cmp_funcs
static const cmp_func cmp_funcs[]
Definition: vf_palettegen.c:127
PaletteGenContext::histogram
struct hist_node histogram[HIST_SIZE]
Definition: vf_palettegen.c:73
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:603
ref
static int ref[MAX_W *MAX_W]
Definition: jpeg2000dwt.c:112
AVFilterContext
An instance of a filter.
Definition: avfilter.h:408
color_hash
static unsigned color_hash(uint32_t color, int use_alpha)
Hashing function for the color.
Definition: vf_palettegen.c:430
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:236
diff
static av_always_inline int diff(const uint32_t a, const uint32_t b)
Definition: vf_palettegen.c:139
range_box::sorted_by
int sorted_by
Definition: vf_palettegen.c:46
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:70
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:370
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:27
ff_vf_palettegen
const AVFilter ff_vf_palettegen
Definition: vf_palettegen.c:620
PaletteGenContext::stats_mode
int stats_mode
Definition: vf_palettegen.c:69
STATS_MODE_DIFF_FRAMES
@ STATS_MODE_DIFF_FRAMES
Definition: vf_palettegen.c:56
update_histogram_diff
static int update_histogram_diff(struct hist_node *hist, const AVFrame *f1, const AVFrame *f2, int use_alpha)
Update histogram when pixels differ from previous frame.
Definition: vf_palettegen.c:474
PaletteGenContext::use_alpha
int use_alpha
Definition: vf_palettegen.c:70
PaletteGenContext::transparency_color
uint8_t transparency_color[4]
Definition: vf_palettegen.c:79
set_colorquant_ratio_meta
static double set_colorquant_ratio_meta(AVFrame *out, int nb_out, int nb_in)
Definition: vf_palettegen.c:307
int
int
Definition: ffmpeg_filter.c:153
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:77
min
float min
Definition: vorbis_enc_data.h:429