FFmpeg
vf_paletteuse.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  * Use a palette to downsample an input video stream.
25  */
26 
27 #include "libavutil/bprint.h"
28 #include "libavutil/file_open.h"
29 #include "libavutil/internal.h"
30 #include "libavutil/opt.h"
31 #include "libavutil/qsort.h"
32 #include "avfilter.h"
33 #include "filters.h"
34 #include "formats.h"
35 #include "framesync.h"
36 #include "internal.h"
37 #include "palette.h"
38 #include "video.h"
39 
51 };
52 
53 enum diff_mode {
57 };
58 
59 struct color_info {
60  uint32_t srgb;
62 };
63 
64 struct color_node {
65  struct color_info c;
66  uint8_t palette_id;
67  int split;
69 };
70 
71 #define CACHE_SIZE (1<<15)
72 
73 struct cached_color {
74  uint32_t color;
75  uint8_t pal_entry;
76 };
77 
78 struct cache_node {
81 };
82 
83 struct PaletteUseContext;
84 
86  int x_start, int y_start, int width, int height);
87 
88 typedef struct PaletteUseContext {
89  const AVClass *class;
91  struct cache_node cache[CACHE_SIZE]; /* lookup cache */
92  struct color_node map[AVPALETTE_COUNT]; /* 3D-Tree (KD-Tree with K=3) for reverse colormap */
94  int transparency_index; /* index in the palette of transparency. -1 if there is no transparency in the palette. */
97  int dither;
98  int new;
101  int ordered_dither[8*8];
105 
106  /* debug options */
109  uint64_t total_mean_err;
111 
112 #define OFFSET(x) offsetof(PaletteUseContext, x)
113 #define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
114 static const AVOption paletteuse_options[] = {
115  { "dither", "select dithering mode", OFFSET(dither), AV_OPT_TYPE_INT, {.i64=DITHERING_SIERRA2_4A}, 0, NB_DITHERING-1, FLAGS, "dithering_mode" },
116  { "bayer", "ordered 8x8 bayer dithering (deterministic)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_BAYER}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
117  { "heckbert", "dithering as defined by Paul Heckbert in 1982 (simple error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_HECKBERT}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
118  { "floyd_steinberg", "Floyd and Steingberg dithering (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_FLOYD_STEINBERG}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
119  { "sierra2", "Frankie Sierra dithering v2 (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_SIERRA2}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
120  { "sierra2_4a", "Frankie Sierra dithering v2 \"Lite\" (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_SIERRA2_4A}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
121  { "sierra3", "Frankie Sierra dithering v3 (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_SIERRA3}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
122  { "burkes", "Burkes dithering (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_BURKES}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
123  { "atkinson", "Atkinson dithering by Bill Atkinson at Apple Computer (error diffusion)",0, AV_OPT_TYPE_CONST, {.i64=DITHERING_ATKINSON}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
124  { "bayer_scale", "set scale for bayer dithering", OFFSET(bayer_scale), AV_OPT_TYPE_INT, {.i64=2}, 0, 5, FLAGS },
125  { "diff_mode", "set frame difference mode", OFFSET(diff_mode), AV_OPT_TYPE_INT, {.i64=DIFF_MODE_NONE}, 0, NB_DIFF_MODE-1, FLAGS, "diff_mode" },
126  { "rectangle", "process smallest different rectangle", 0, AV_OPT_TYPE_CONST, {.i64=DIFF_MODE_RECTANGLE}, INT_MIN, INT_MAX, FLAGS, "diff_mode" },
127  { "new", "take new palette for each output frame", OFFSET(new), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS },
128  { "alpha_threshold", "set the alpha threshold for transparency", OFFSET(trans_thresh), AV_OPT_TYPE_INT, {.i64=128}, 0, 255, FLAGS },
129 
130  /* following are the debug options, not part of the official API */
131  { "debug_kdtree", "save Graphviz graph of the kdtree in specified file", OFFSET(dot_filename), AV_OPT_TYPE_STRING, {.str=NULL}, 0, 0, FLAGS },
132  { NULL }
133 };
134 
135 AVFILTER_DEFINE_CLASS(paletteuse);
136 
137 static int load_apply_palette(FFFrameSync *fs);
138 
140 {
141  static const enum AVPixelFormat in_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
142  static const enum AVPixelFormat inpal_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
143  static const enum AVPixelFormat out_fmts[] = {AV_PIX_FMT_PAL8, AV_PIX_FMT_NONE};
144  int ret;
145  if ((ret = ff_formats_ref(ff_make_format_list(in_fmts),
146  &ctx->inputs[0]->outcfg.formats)) < 0 ||
147  (ret = ff_formats_ref(ff_make_format_list(inpal_fmts),
148  &ctx->inputs[1]->outcfg.formats)) < 0 ||
150  &ctx->outputs[0]->incfg.formats)) < 0)
151  return ret;
152  return 0;
153 }
154 
155 static av_always_inline uint32_t dither_color(uint32_t px, int er, int eg,
156  int eb, int scale, int shift)
157 {
158  return (px & 0xff000000)
159  | av_clip_uint8((px >> 16 & 0xff) + ((er * scale) / (1<<shift))) << 16
160  | av_clip_uint8((px >> 8 & 0xff) + ((eg * scale) / (1<<shift))) << 8
161  | av_clip_uint8((px & 0xff) + ((eb * scale) / (1<<shift)));
162 }
163 
164 static av_always_inline int diff(const struct color_info *a, const struct color_info *b, const int trans_thresh)
165 {
166  const uint8_t alpha_a = a->srgb >> 24;
167  const uint8_t alpha_b = b->srgb >> 24;
168 
169  if (alpha_a < trans_thresh && alpha_b < trans_thresh) {
170  return 0;
171  } else if (alpha_a >= trans_thresh && alpha_b >= trans_thresh) {
172  const int64_t dL = a->lab[0] - b->lab[0];
173  const int64_t da = a->lab[1] - b->lab[1];
174  const int64_t db = a->lab[2] - b->lab[2];
175  const int64_t ret = dL*dL + da*da + db*db;
176  return FFMIN(ret, INT32_MAX - 1);
177  } else {
178  return INT32_MAX - 1;
179  }
180 }
181 
182 static struct color_info get_color_from_srgb(uint32_t srgb)
183 {
184  const struct Lab lab = ff_srgb_u8_to_oklab_int(srgb);
185  struct color_info ret = {.srgb=srgb, .lab={lab.L, lab.a, lab.b}};
186  return ret;
187 }
188 
190  int node_pos;
191  int64_t dist_sqd;
192 };
193 
194 static void colormap_nearest_node(const struct color_node *map,
195  const int node_pos,
196  const struct color_info *target,
197  const int trans_thresh,
198  struct nearest_color *nearest)
199 {
200  const struct color_node *kd = map + node_pos;
201  int nearer_kd_id, further_kd_id;
202  const struct color_info *current = &kd->c;
203  const int64_t current_to_target = diff(target, current, trans_thresh);
204 
205  if (current_to_target < nearest->dist_sqd) {
206  nearest->node_pos = node_pos;
207  nearest->dist_sqd = current_to_target;
208  }
209 
210  if (kd->left_id != -1 || kd->right_id != -1) {
211  const int64_t dx = target->lab[kd->split] - current->lab[kd->split];
212 
213  if (dx <= 0) nearer_kd_id = kd->left_id, further_kd_id = kd->right_id;
214  else nearer_kd_id = kd->right_id, further_kd_id = kd->left_id;
215 
216  if (nearer_kd_id != -1)
217  colormap_nearest_node(map, nearer_kd_id, target, trans_thresh, nearest);
218 
219  if (further_kd_id != -1 && dx*dx < nearest->dist_sqd)
220  colormap_nearest_node(map, further_kd_id, target, trans_thresh, nearest);
221  }
222 }
223 
224 static av_always_inline uint8_t colormap_nearest(const struct color_node *node, const struct color_info *target, const int trans_thresh)
225 {
226  struct nearest_color res = {.dist_sqd = INT_MAX, .node_pos = -1};
227  colormap_nearest_node(node, 0, target, trans_thresh, &res);
228  return node[res.node_pos].palette_id;
229 }
230 
231 struct stack_node {
232  int color_id;
233  int dx2;
234 };
235 
236 /**
237  * Check if the requested color is in the cache already. If not, find it in the
238  * color tree and cache it.
239  */
241 {
242  struct color_info clrinfo;
243  const uint32_t hash = ff_lowbias32(color) & (CACHE_SIZE - 1);
244  struct cache_node *node = &s->cache[hash];
245  struct cached_color *e;
246 
247  // first, check for transparency
248  if (color>>24 < s->trans_thresh && s->transparency_index >= 0) {
249  return s->transparency_index;
250  }
251 
252  for (int i = 0; i < node->nb_entries; i++) {
253  e = &node->entries[i];
254  if (e->color == color)
255  return e->pal_entry;
256  }
257 
258  e = av_dynarray2_add((void**)&node->entries, &node->nb_entries,
259  sizeof(*node->entries), NULL);
260  if (!e)
261  return AVERROR(ENOMEM);
262  e->color = color;
263  clrinfo = get_color_from_srgb(color);
264  e->pal_entry = colormap_nearest(s->map, &clrinfo, s->trans_thresh);
265 
266  return e->pal_entry;
267 }
268 
270  uint32_t c, int *er, int *eg, int *eb)
271 {
272  uint32_t dstc;
273  const int dstx = color_get(s, c);
274  if (dstx < 0)
275  return dstx;
276  dstc = s->palette[dstx];
277  if (dstx == s->transparency_index) {
278  *er = *eg = *eb = 0;
279  } else {
280  const uint8_t r = c >> 16 & 0xff;
281  const uint8_t g = c >> 8 & 0xff;
282  const uint8_t b = c & 0xff;
283  *er = (int)r - (int)(dstc >> 16 & 0xff);
284  *eg = (int)g - (int)(dstc >> 8 & 0xff);
285  *eb = (int)b - (int)(dstc & 0xff);
286  }
287  return dstx;
288 }
289 
291  int x_start, int y_start, int w, int h,
292  enum dithering_mode dither)
293 {
294  const int src_linesize = in ->linesize[0] >> 2;
295  const int dst_linesize = out->linesize[0];
296  uint32_t *src = ((uint32_t *)in ->data[0]) + y_start*src_linesize;
297  uint8_t *dst = out->data[0] + y_start*dst_linesize;
298 
299  w += x_start;
300  h += y_start;
301 
302  for (int y = y_start; y < h; y++) {
303  for (int x = x_start; x < w; x++) {
304  int er, eg, eb;
305 
306  if (dither == DITHERING_BAYER) {
307  const int d = s->ordered_dither[(y & 7)<<3 | (x & 7)];
308  const uint8_t a8 = src[x] >> 24;
309  const uint8_t r8 = src[x] >> 16 & 0xff;
310  const uint8_t g8 = src[x] >> 8 & 0xff;
311  const uint8_t b8 = src[x] & 0xff;
312  const uint8_t r = av_clip_uint8(r8 + d);
313  const uint8_t g = av_clip_uint8(g8 + d);
314  const uint8_t b = av_clip_uint8(b8 + d);
315  const uint32_t color_new = (unsigned)(a8) << 24 | r << 16 | g << 8 | b;
316  const int color = color_get(s, color_new);
317 
318  if (color < 0)
319  return color;
320  dst[x] = color;
321 
322  } else if (dither == DITHERING_HECKBERT) {
323  const int right = x < w - 1, down = y < h - 1;
324  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
325 
326  if (color < 0)
327  return color;
328  dst[x] = color;
329 
330  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 3, 3);
331  if ( down) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 3, 3);
332  if (right && down) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 2, 3);
333 
334  } else if (dither == DITHERING_FLOYD_STEINBERG) {
335  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
336  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
337 
338  if (color < 0)
339  return color;
340  dst[x] = color;
341 
342  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 7, 4);
343  if (left && down) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 3, 4);
344  if ( down) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 5, 4);
345  if (right && down) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 1, 4);
346 
347  } else if (dither == DITHERING_SIERRA2) {
348  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
349  const int right2 = x < w - 2, left2 = x > x_start + 1;
350  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
351 
352  if (color < 0)
353  return color;
354  dst[x] = color;
355 
356  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 4, 4);
357  if (right2) src[ x + 2] = dither_color(src[ x + 2], er, eg, eb, 3, 4);
358 
359  if (down) {
360  if (left2) src[ src_linesize + x - 2] = dither_color(src[ src_linesize + x - 2], er, eg, eb, 1, 4);
361  if (left) src[ src_linesize + x - 1] = dither_color(src[ src_linesize + x - 1], er, eg, eb, 2, 4);
362  if (1) src[ src_linesize + x ] = dither_color(src[ src_linesize + x ], er, eg, eb, 3, 4);
363  if (right) src[ src_linesize + x + 1] = dither_color(src[ src_linesize + x + 1], er, eg, eb, 2, 4);
364  if (right2) src[ src_linesize + x + 2] = dither_color(src[ src_linesize + x + 2], er, eg, eb, 1, 4);
365  }
366 
367  } else if (dither == DITHERING_SIERRA2_4A) {
368  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
369  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
370 
371  if (color < 0)
372  return color;
373  dst[x] = color;
374 
375  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 2, 2);
376  if (left && down) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 1, 2);
377  if ( down) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 1, 2);
378 
379  } else if (dither == DITHERING_SIERRA3) {
380  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
381  const int right2 = x < w - 2, down2 = y < h - 2, left2 = x > x_start + 1;
382  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
383 
384  if (color < 0)
385  return color;
386  dst[x] = color;
387 
388  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 5, 5);
389  if (right2) src[ x + 2] = dither_color(src[ x + 2], er, eg, eb, 3, 5);
390 
391  if (down) {
392  if (left2) src[src_linesize + x - 2] = dither_color(src[src_linesize + x - 2], er, eg, eb, 2, 5);
393  if (left) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 4, 5);
394  if (1) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 5, 5);
395  if (right) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 4, 5);
396  if (right2) src[src_linesize + x + 2] = dither_color(src[src_linesize + x + 2], er, eg, eb, 2, 5);
397 
398  if (down2) {
399  if (left) src[src_linesize*2 + x - 1] = dither_color(src[src_linesize*2 + x - 1], er, eg, eb, 2, 5);
400  if (1) src[src_linesize*2 + x ] = dither_color(src[src_linesize*2 + x ], er, eg, eb, 3, 5);
401  if (right) src[src_linesize*2 + x + 1] = dither_color(src[src_linesize*2 + x + 1], er, eg, eb, 2, 5);
402  }
403  }
404 
405  } else if (dither == DITHERING_BURKES) {
406  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
407  const int right2 = x < w - 2, left2 = x > x_start + 1;
408  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
409 
410  if (color < 0)
411  return color;
412  dst[x] = color;
413 
414  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 8, 5);
415  if (right2) src[ x + 2] = dither_color(src[ x + 2], er, eg, eb, 4, 5);
416 
417  if (down) {
418  if (left2) src[src_linesize + x - 2] = dither_color(src[src_linesize + x - 2], er, eg, eb, 2, 5);
419  if (left) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 4, 5);
420  if (1) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 8, 5);
421  if (right) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 4, 5);
422  if (right2) src[src_linesize + x + 2] = dither_color(src[src_linesize + x + 2], er, eg, eb, 2, 5);
423  }
424 
425  } else if (dither == DITHERING_ATKINSON) {
426  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
427  const int right2 = x < w - 2, down2 = y < h - 2;
428  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
429 
430  if (color < 0)
431  return color;
432  dst[x] = color;
433 
434  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 1, 3);
435  if (right2) src[ x + 2] = dither_color(src[ x + 2], er, eg, eb, 1, 3);
436 
437  if (down) {
438  if (left) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 1, 3);
439  if (1) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 1, 3);
440  if (right) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 1, 3);
441  if (down2) src[src_linesize*2 + x ] = dither_color(src[src_linesize*2 + x ], er, eg, eb, 1, 3);
442  }
443 
444  } else {
445  const int color = color_get(s, src[x]);
446 
447  if (color < 0)
448  return color;
449  dst[x] = color;
450  }
451  }
452  src += src_linesize;
453  dst += dst_linesize;
454  }
455  return 0;
456 }
457 
458 #define INDENT 4
459 static void disp_node(AVBPrint *buf,
460  const struct color_node *map,
461  int parent_id, int node_id,
462  int depth)
463 {
464  const struct color_node *node = &map[node_id];
465  const uint32_t fontcolor = node->c.lab[0] > 0x7fff ? 0 : 0xffffff;
466  const int lab_comp = node->split;
467  av_bprintf(buf, "%*cnode%d ["
468  "label=\"%c%d%c%d%c%d%c\" "
469  "fillcolor=\"#%06"PRIX32"\" "
470  "fontcolor=\"#%06"PRIX32"\"]\n",
471  depth*INDENT, ' ', node->palette_id,
472  "[ "[lab_comp], node->c.lab[0],
473  "][ "[lab_comp], node->c.lab[1],
474  " ]["[lab_comp], node->c.lab[2],
475  " ]"[lab_comp],
476  node->c.srgb & 0xffffff,
477  fontcolor);
478  if (parent_id != -1)
479  av_bprintf(buf, "%*cnode%d -> node%d\n", depth*INDENT, ' ',
480  map[parent_id].palette_id, node->palette_id);
481  if (node->left_id != -1) disp_node(buf, map, node_id, node->left_id, depth + 1);
482  if (node->right_id != -1) disp_node(buf, map, node_id, node->right_id, depth + 1);
483 }
484 
485 // debug_kdtree=kdtree.dot -> dot -Tpng kdtree.dot > kdtree.png
486 static int disp_tree(const struct color_node *node, const char *fname)
487 {
488  AVBPrint buf;
489  FILE *f = avpriv_fopen_utf8(fname, "w");
490 
491  if (!f) {
492  int ret = AVERROR(errno);
493  av_log(NULL, AV_LOG_ERROR, "Cannot open file '%s' for writing: %s\n",
494  fname, av_err2str(ret));
495  return ret;
496  }
497 
499 
500  av_bprintf(&buf, "digraph {\n");
501  av_bprintf(&buf, " node [style=filled fontsize=10 shape=box]\n");
502  disp_node(&buf, node, -1, 0, 0);
503  av_bprintf(&buf, "}\n");
504 
505  fwrite(buf.str, 1, buf.len, f);
506  fclose(f);
507  av_bprint_finalize(&buf, NULL);
508  return 0;
509 }
510 
511 struct color {
512  struct Lab value;
513  uint8_t pal_id;
514 };
515 
516 struct color_rect {
519 };
520 
521 typedef int (*cmp_func)(const void *, const void *);
522 
523 #define DECLARE_CMP_FUNC(name) \
524 static int cmp_##name(const void *pa, const void *pb) \
525 { \
526  const struct color *a = pa; \
527  const struct color *b = pb; \
528  return FFDIFFSIGN(a->value.name, b->value.name); \
529 }
530 
534 
535 static const cmp_func cmp_funcs[] = {cmp_L, cmp_a, cmp_b};
536 
537 static int get_next_color(const uint8_t *color_used, const uint32_t *palette,
538  int *component, const struct color_rect *box)
539 {
540  int wL, wa, wb;
541  int longest = 0;
542  unsigned nb_color = 0;
543  struct color_rect ranges;
544  struct color tmp_pal[256];
545  cmp_func cmpf;
546 
547  ranges.min[0] = ranges.min[1] = ranges.min[2] = 0xffff;
548  ranges.max[0] = ranges.max[1] = ranges.max[2] = -0xffff;
549 
550  for (int i = 0; i < AVPALETTE_COUNT; i++) {
551  const uint32_t c = palette[i];
552  const uint8_t a = c >> 24;
553  const struct Lab lab = ff_srgb_u8_to_oklab_int(c);
554 
555  if (color_used[i] || (a != 0xff) ||
556  lab.L < box->min[0] || lab.a < box->min[1] || lab.b < box->min[2] ||
557  lab.L > box->max[0] || lab.a > box->max[1] || lab.b > box->max[2])
558  continue;
559 
560  if (lab.L < ranges.min[0]) ranges.min[0] = lab.L;
561  if (lab.a < ranges.min[1]) ranges.min[1] = lab.a;
562  if (lab.b < ranges.min[2]) ranges.min[2] = lab.b;
563 
564  if (lab.L > ranges.max[0]) ranges.max[0] = lab.L;
565  if (lab.a > ranges.max[1]) ranges.max[1] = lab.a;
566  if (lab.b > ranges.max[2]) ranges.max[2] = lab.b;
567 
568  tmp_pal[nb_color].value = lab;
569  tmp_pal[nb_color].pal_id = i;
570 
571  nb_color++;
572  }
573 
574  if (!nb_color)
575  return -1;
576 
577  /* define longest axis that will be the split component */
578  wL = ranges.max[0] - ranges.min[0];
579  wa = ranges.max[1] - ranges.min[1];
580  wb = ranges.max[2] - ranges.min[2];
581  if (wb >= wL && wb >= wa) longest = 2;
582  if (wa >= wL && wa >= wb) longest = 1;
583  if (wL >= wa && wL >= wb) longest = 0;
584  cmpf = cmp_funcs[longest];
585  *component = longest;
586 
587  /* sort along this axis to get median */
588  AV_QSORT(tmp_pal, nb_color, struct color, cmpf);
589 
590  return tmp_pal[nb_color >> 1].pal_id;
591 }
592 
593 static int colormap_insert(struct color_node *map,
594  uint8_t *color_used,
595  int *nb_used,
596  const uint32_t *palette,
597  const int trans_thresh,
598  const struct color_rect *box)
599 {
600  int component, cur_id;
601  int comp_value;
602  int node_left_id = -1, node_right_id = -1;
603  struct color_node *node;
604  struct color_rect box1, box2;
605  const int pal_id = get_next_color(color_used, palette, &component, box);
606 
607  if (pal_id < 0)
608  return -1;
609 
610  /* create new node with that color */
611  cur_id = (*nb_used)++;
612  node = &map[cur_id];
613  node->split = component;
614  node->palette_id = pal_id;
615  node->c = get_color_from_srgb(palette[pal_id]);
616 
617  color_used[pal_id] = 1;
618 
619  /* get the two boxes this node creates */
620  box1 = box2 = *box;
621  comp_value = node->c.lab[component];
622  box1.max[component] = comp_value;
623  box2.min[component] = FFMIN(comp_value + 1, 0xffff);
624 
625  node_left_id = colormap_insert(map, color_used, nb_used, palette, trans_thresh, &box1);
626 
627  if (box2.min[component] <= box2.max[component])
628  node_right_id = colormap_insert(map, color_used, nb_used, palette, trans_thresh, &box2);
629 
630  node->left_id = node_left_id;
631  node->right_id = node_right_id;
632 
633  return cur_id;
634 }
635 
636 static int cmp_pal_entry(const void *a, const void *b)
637 {
638  const int c1 = *(const uint32_t *)a & 0xffffff;
639  const int c2 = *(const uint32_t *)b & 0xffffff;
640  return c1 - c2;
641 }
642 
644 {
645  int nb_used = 0;
646  uint8_t color_used[AVPALETTE_COUNT] = {0};
647  uint32_t last_color = 0;
648  struct color_rect box;
649 
650  if (s->transparency_index >= 0) {
651  FFSWAP(uint32_t, s->palette[s->transparency_index], s->palette[255]);
652  }
653 
654  /* disable transparent colors and dups */
655  qsort(s->palette, AVPALETTE_COUNT-(s->transparency_index >= 0), sizeof(*s->palette), cmp_pal_entry);
656 
657  for (int i = 0; i < AVPALETTE_COUNT; i++) {
658  const uint32_t c = s->palette[i];
659  if (i != 0 && c == last_color) {
660  color_used[i] = 1;
661  continue;
662  }
663  last_color = c;
664  if (c >> 24 < s->trans_thresh) {
665  color_used[i] = 1; // ignore transparent color(s)
666  continue;
667  }
668  }
669 
670  box.min[0] = box.min[1] = box.min[2] = -0xffff;
671  box.max[0] = box.max[1] = box.max[2] = 0xffff;
672 
673  colormap_insert(s->map, color_used, &nb_used, s->palette, s->trans_thresh, &box);
674 
675  if (s->dot_filename)
676  disp_tree(s->map, s->dot_filename);
677 }
678 
680  const AVFrame *prv_src, const AVFrame *cur_src,
681  const AVFrame *prv_dst, AVFrame *cur_dst,
682  int *xp, int *yp, int *wp, int *hp)
683 {
684  int x_start = 0, y_start = 0;
685  int width = cur_src->width;
686  int height = cur_src->height;
687 
688  if (prv_src->data[0] && diff_mode == DIFF_MODE_RECTANGLE) {
689  int y;
690  int x_end = cur_src->width - 1,
691  y_end = cur_src->height - 1;
692  const uint32_t *prv_srcp = (const uint32_t *)prv_src->data[0];
693  const uint32_t *cur_srcp = (const uint32_t *)cur_src->data[0];
694  const uint8_t *prv_dstp = prv_dst->data[0];
695  uint8_t *cur_dstp = cur_dst->data[0];
696 
697  const int prv_src_linesize = prv_src->linesize[0] >> 2;
698  const int cur_src_linesize = cur_src->linesize[0] >> 2;
699  const int prv_dst_linesize = prv_dst->linesize[0];
700  const int cur_dst_linesize = cur_dst->linesize[0];
701 
702  /* skip common lines */
703  while (y_start < y_end && !memcmp(prv_srcp + y_start*prv_src_linesize,
704  cur_srcp + y_start*cur_src_linesize,
705  cur_src->width * 4)) {
706  memcpy(cur_dstp + y_start*cur_dst_linesize,
707  prv_dstp + y_start*prv_dst_linesize,
708  cur_dst->width);
709  y_start++;
710  }
711  while (y_end > y_start && !memcmp(prv_srcp + y_end*prv_src_linesize,
712  cur_srcp + y_end*cur_src_linesize,
713  cur_src->width * 4)) {
714  memcpy(cur_dstp + y_end*cur_dst_linesize,
715  prv_dstp + y_end*prv_dst_linesize,
716  cur_dst->width);
717  y_end--;
718  }
719 
720  height = y_end + 1 - y_start;
721 
722  /* skip common columns */
723  while (x_start < x_end) {
724  int same_column = 1;
725  for (y = y_start; y <= y_end; y++) {
726  if (prv_srcp[y*prv_src_linesize + x_start] != cur_srcp[y*cur_src_linesize + x_start]) {
727  same_column = 0;
728  break;
729  }
730  }
731  if (!same_column)
732  break;
733  x_start++;
734  }
735  while (x_end > x_start) {
736  int same_column = 1;
737  for (y = y_start; y <= y_end; y++) {
738  if (prv_srcp[y*prv_src_linesize + x_end] != cur_srcp[y*cur_src_linesize + x_end]) {
739  same_column = 0;
740  break;
741  }
742  }
743  if (!same_column)
744  break;
745  x_end--;
746  }
747  width = x_end + 1 - x_start;
748 
749  if (x_start) {
750  for (y = y_start; y <= y_end; y++)
751  memcpy(cur_dstp + y*cur_dst_linesize,
752  prv_dstp + y*prv_dst_linesize, x_start);
753  }
754  if (x_end != cur_src->width - 1) {
755  const int copy_len = cur_src->width - 1 - x_end;
756  for (y = y_start; y <= y_end; y++)
757  memcpy(cur_dstp + y*cur_dst_linesize + x_end + 1,
758  prv_dstp + y*prv_dst_linesize + x_end + 1,
759  copy_len);
760  }
761  }
762  *xp = x_start;
763  *yp = y_start;
764  *wp = width;
765  *hp = height;
766 }
767 
769 {
770  int x, y, w, h, ret;
771  AVFilterContext *ctx = inlink->dst;
772  PaletteUseContext *s = ctx->priv;
773  AVFilterLink *outlink = inlink->dst->outputs[0];
774 
775  AVFrame *out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
776  if (!out) {
777  *outf = NULL;
778  return AVERROR(ENOMEM);
779  }
781 
782  set_processing_window(s->diff_mode, s->last_in, in,
783  s->last_out, out, &x, &y, &w, &h);
784  av_frame_unref(s->last_out);
785  if ((ret = av_frame_replace(s->last_in, in)) < 0 ||
786  (ret = av_frame_ref(s->last_out, out)) < 0 ||
787  (ret = ff_inlink_make_frame_writable(inlink, &s->last_in)) < 0) {
788  av_frame_free(&out);
789  *outf = NULL;
790  return ret;
791  }
792 
793  ff_dlog(ctx, "%dx%d rect: (%d;%d) -> (%d,%d) [area:%dx%d]\n",
794  w, h, x, y, x+w, y+h, in->width, in->height);
795 
796  ret = s->set_frame(s, out, in, x, y, w, h);
797  if (ret < 0) {
798  av_frame_free(&out);
799  *outf = NULL;
800  return ret;
801  }
802  memcpy(out->data[1], s->palette, AVPALETTE_SIZE);
803  *outf = out;
804  return 0;
805 }
806 
807 static int config_output(AVFilterLink *outlink)
808 {
809  int ret;
810  AVFilterContext *ctx = outlink->src;
811  PaletteUseContext *s = ctx->priv;
812 
814  if (ret < 0)
815  return ret;
816  s->fs.opt_repeatlast = 1; // only 1 frame in the palette
817  s->fs.in[1].before = s->fs.in[1].after = EXT_INFINITY;
818  s->fs.on_event = load_apply_palette;
819 
820  outlink->w = ctx->inputs[0]->w;
821  outlink->h = ctx->inputs[0]->h;
822 
823  outlink->time_base = ctx->inputs[0]->time_base;
824  if ((ret = ff_framesync_configure(&s->fs)) < 0)
825  return ret;
826  return 0;
827 }
828 
830 {
831  AVFilterContext *ctx = inlink->dst;
832 
833  if (inlink->w * inlink->h != AVPALETTE_COUNT) {
835  "Palette input must contain exactly %d pixels. "
836  "Specified input has %dx%d=%d pixels\n",
837  AVPALETTE_COUNT, inlink->w, inlink->h,
838  inlink->w * inlink->h);
839  return AVERROR(EINVAL);
840  }
841  return 0;
842 }
843 
844 static void load_palette(PaletteUseContext *s, const AVFrame *palette_frame)
845 {
846  int i, x, y;
847  const uint32_t *p = (const uint32_t *)palette_frame->data[0];
848  const ptrdiff_t p_linesize = palette_frame->linesize[0] >> 2;
849 
850  s->transparency_index = -1;
851 
852  if (s->new) {
853  memset(s->palette, 0, sizeof(s->palette));
854  memset(s->map, 0, sizeof(s->map));
855  for (i = 0; i < CACHE_SIZE; i++)
856  av_freep(&s->cache[i].entries);
857  memset(s->cache, 0, sizeof(s->cache));
858  }
859 
860  i = 0;
861  for (y = 0; y < palette_frame->height; y++) {
862  for (x = 0; x < palette_frame->width; x++) {
863  s->palette[i] = p[x];
864  if (p[x]>>24 < s->trans_thresh) {
865  s->transparency_index = i; // we are assuming at most one transparent color in palette
866  }
867  i++;
868  }
869  p += p_linesize;
870  }
871 
872  load_colormap(s);
873 
874  if (!s->new)
875  s->palette_loaded = 1;
876 }
877 
879 {
880  AVFilterContext *ctx = fs->parent;
881  AVFilterLink *inlink = ctx->inputs[0];
882  PaletteUseContext *s = ctx->priv;
883  AVFrame *master, *second, *out = NULL;
884  int ret;
885 
886  // writable for error diffusal dithering
888  if (ret < 0)
889  return ret;
890  if (!master || !second) {
892  return AVERROR_BUG;
893  }
894  if (!s->palette_loaded) {
895  load_palette(s, second);
896  }
899  if (ret < 0)
900  return ret;
901  return ff_filter_frame(ctx->outputs[0], out);
902 }
903 
904 #define DEFINE_SET_FRAME(name, value) \
905 static int set_frame_##name(PaletteUseContext *s, AVFrame *out, AVFrame *in, \
906  int x_start, int y_start, int w, int h) \
907 { \
908  return set_frame(s, out, in, x_start, y_start, w, h, value); \
909 }
910 
920 
922  [DITHERING_NONE] = set_frame_none,
923  [DITHERING_BAYER] = set_frame_bayer,
924  [DITHERING_HECKBERT] = set_frame_heckbert,
925  [DITHERING_FLOYD_STEINBERG] = set_frame_floyd_steinberg,
926  [DITHERING_SIERRA2] = set_frame_sierra2,
927  [DITHERING_SIERRA2_4A] = set_frame_sierra2_4a,
928  [DITHERING_SIERRA3] = set_frame_sierra3,
929  [DITHERING_BURKES] = set_frame_burkes,
930  [DITHERING_ATKINSON] = set_frame_atkinson,
931 };
932 
933 static int dither_value(int p)
934 {
935  const int q = p ^ (p >> 3);
936  return (p & 4) >> 2 | (q & 4) >> 1 \
937  | (p & 2) << 1 | (q & 2) << 2 \
938  | (p & 1) << 4 | (q & 1) << 5;
939 }
940 
942 {
943  PaletteUseContext *s = ctx->priv;
944 
945  s->last_in = av_frame_alloc();
946  s->last_out = av_frame_alloc();
947  if (!s->last_in || !s->last_out)
948  return AVERROR(ENOMEM);
949 
950  s->set_frame = set_frame_lut[s->dither];
951 
952  if (s->dither == DITHERING_BAYER) {
953  const int delta = 1 << (5 - s->bayer_scale); // to avoid too much luma
954 
955  for (int i = 0; i < FF_ARRAY_ELEMS(s->ordered_dither); i++)
956  s->ordered_dither[i] = (dither_value(i) >> s->bayer_scale) - delta;
957  }
958 
959  return 0;
960 }
961 
963 {
964  PaletteUseContext *s = ctx->priv;
965  return ff_framesync_activate(&s->fs);
966 }
967 
969 {
970  PaletteUseContext *s = ctx->priv;
971 
972  ff_framesync_uninit(&s->fs);
973  for (int i = 0; i < CACHE_SIZE; i++)
974  av_freep(&s->cache[i].entries);
975  av_frame_free(&s->last_in);
976  av_frame_free(&s->last_out);
977 }
978 
979 static const AVFilterPad paletteuse_inputs[] = {
980  {
981  .name = "default",
982  .type = AVMEDIA_TYPE_VIDEO,
983  },{
984  .name = "palette",
985  .type = AVMEDIA_TYPE_VIDEO,
986  .config_props = config_input_palette,
987  },
988 };
989 
990 static const AVFilterPad paletteuse_outputs[] = {
991  {
992  .name = "default",
993  .type = AVMEDIA_TYPE_VIDEO,
994  .config_props = config_output,
995  },
996 };
997 
999  .name = "paletteuse",
1000  .description = NULL_IF_CONFIG_SMALL("Use a palette to downsample an input video stream."),
1001  .priv_size = sizeof(PaletteUseContext),
1002  .init = init,
1003  .uninit = uninit,
1004  .activate = activate,
1008  .priv_class = &paletteuse_class,
1009 };
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:108
cached_color::color
uint32_t color
Definition: vf_paletteuse.c:74
ff_framesync_configure
int ff_framesync_configure(FFFrameSync *fs)
Configure a frame sync structure.
Definition: framesync.c:134
AV_BPRINT_SIZE_UNLIMITED
#define AV_BPRINT_SIZE_UNLIMITED
config_input_palette
static int config_input_palette(AVFilterLink *inlink)
Definition: vf_paletteuse.c:829
AVPixelFormat
AVPixelFormat
Pixel format.
Definition: pixfmt.h:64
query_formats
static int query_formats(AVFilterContext *ctx)
Definition: vf_paletteuse.c:139
set_frame
static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFrame *in, int x_start, int y_start, int w, int h, enum dithering_mode dither)
Definition: vf_paletteuse.c:290
PaletteUseContext::dot_filename
char * dot_filename
Definition: vf_paletteuse.c:107
r
const char * r
Definition: vf_curves.c:126
AVERROR
Filter the word “frame” indicates either a video frame or a group of audio as stored in an AVFrame structure Format for each input and each output the list of supported formats For video that means pixel format For audio that means channel sample they are references to shared objects When the negotiation mechanism computes the intersection of the formats supported at each end of a all references to both lists are replaced with a reference to the intersection And when a single format is eventually chosen for a link amongst the remaining all references to the list are updated That means that if a filter requires that its input and output have the same format amongst a supported all it has to do is use a reference to the same list of formats query_formats can leave some formats unset and return AVERROR(EAGAIN) to cause the negotiation mechanism toagain later. That can be used by filters with complex requirements to use the format negotiated on one link to set the formats supported on another. Frame references ownership and permissions
opt.h
ff_make_format_list
AVFilterFormats * ff_make_format_list(const int *fmts)
Create a list of supported formats.
Definition: formats.c:401
color_node::c
struct color_info c
Definition: vf_paletteuse.c:65
ff_framesync_uninit
void ff_framesync_uninit(FFFrameSync *fs)
Free all memory currently allocated.
Definition: framesync.c:304
out
FILE * out
Definition: movenc.c:54
color
Definition: vf_paletteuse.c:511
av_bprint_init
void av_bprint_init(AVBPrint *buf, unsigned size_init, unsigned size_max)
Definition: bprint.c:69
color_get
static av_always_inline int color_get(PaletteUseContext *s, uint32_t color)
Check if the requested color is in the cache already.
Definition: vf_paletteuse.c:240
ff_filter_frame
int ff_filter_frame(AVFilterLink *link, AVFrame *frame)
Send a frame of data to the next filter.
Definition: avfilter.c:978
palette.h
PaletteUseContext::last_out
AVFrame * last_out
Definition: vf_paletteuse.c:104
dither_color
static av_always_inline uint32_t dither_color(uint32_t px, int er, int eg, int eb, int scale, int shift)
Definition: vf_paletteuse.c:155
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:100
colormap_nearest_node
static void colormap_nearest_node(const struct color_node *map, const int node_pos, const struct color_info *target, const int trans_thresh, struct nearest_color *nearest)
Definition: vf_paletteuse.c:194
init
static av_cold int init(AVFilterContext *ctx)
Definition: vf_paletteuse.c:941
set_frame_func
int(* set_frame_func)(struct PaletteUseContext *s, AVFrame *out, AVFrame *in, int x_start, int y_start, int width, int height)
Definition: vf_paletteuse.c:85
AVFrame
This structure describes decoded (raw) audio or video data.
Definition: frame.h:340
uninit
static av_cold void uninit(AVFilterContext *ctx)
Definition: vf_paletteuse.c:968
AVFrame::width
int width
Definition: frame.h:412
w
uint8_t w
Definition: llviddspenc.c:38
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:341
AVOption
AVOption.
Definition: opt.h:251
b
#define b
Definition: input.c:41
FILTER_QUERY_FUNC
#define FILTER_QUERY_FUNC(func)
Definition: internal.h:169
stack_node::dx2
int dx2
Definition: vf_paletteuse.c:233
data
const char data[16]
Definition: mxf.c:148
PaletteUseContext::set_frame
set_frame_func set_frame
Definition: vf_paletteuse.c:99
disp_tree
static int disp_tree(const struct color_node *node, const char *fname)
Definition: vf_paletteuse.c:486
get_dst_color_err
static av_always_inline int get_dst_color_err(PaletteUseContext *s, uint32_t c, int *er, int *eg, int *eb)
Definition: vf_paletteuse.c:269
AVFilter::name
const char * name
Filter name.
Definition: avfilter.h:170
c1
static const uint64_t c1
Definition: murmur3.c:52
FFFrameSync
Frame sync structure.
Definition: framesync.h:168
EXT_INFINITY
@ EXT_INFINITY
Extend the frame to infinity.
Definition: framesync.h:75
video.h
hash
uint8_t hash[HASH_SIZE]
Definition: movenc.c:57
Lab::a
int32_t a
Definition: palette.h:31
PaletteUseContext::palette_loaded
int palette_loaded
Definition: vf_paletteuse.c:96
AVFrame::data
uint8_t * data[AV_NUM_DATA_POINTERS]
pointer to the picture/channel planes.
Definition: frame.h:361
formats.h
stack_node::color_id
int color_id
Definition: vf_paletteuse.c:232
DIFF_MODE_NONE
@ DIFF_MODE_NONE
Definition: vf_paletteuse.c:54
NB_DITHERING
@ NB_DITHERING
Definition: vf_paletteuse.c:50
Lab::b
int32_t b
Definition: palette.h:31
dither_value
static int dither_value(int p)
Definition: vf_paletteuse.c:933
scale
static av_always_inline float scale(float x, float s)
Definition: vf_v360.c:1389
apply_palette
static int apply_palette(AVFilterLink *inlink, AVFrame *in, AVFrame **outf)
Definition: vf_paletteuse.c:768
PaletteUseContext::cache
struct cache_node cache[CACHE_SIZE]
Definition: vf_paletteuse.c:91
AVFilterPad
A filter pad used for either input or output.
Definition: internal.h:47
colormap_insert
static int colormap_insert(struct color_node *map, uint8_t *color_used, int *nb_used, const uint32_t *palette, const int trans_thresh, const struct color_rect *box)
Definition: vf_paletteuse.c:593
av_frame_alloc
AVFrame * av_frame_alloc(void)
Allocate an AVFrame and set its fields to default values.
Definition: frame.c:88
color_info
Definition: vf_paletteuse.c:59
PaletteUseContext::ordered_dither
int ordered_dither[8 *8]
Definition: vf_paletteuse.c:101
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:180
set_processing_window
static void set_processing_window(enum diff_mode diff_mode, const AVFrame *prv_src, const AVFrame *cur_src, const AVFrame *prv_dst, AVFrame *cur_dst, int *xp, int *yp, int *wp, int *hp)
Definition: vf_paletteuse.c:679
FF_ARRAY_ELEMS
#define FF_ARRAY_ELEMS(a)
Definition: sinewin_tablegen.c:29
av_cold
#define av_cold
Definition: attributes.h:90
INDENT
#define INDENT
Definition: vf_paletteuse.c:458
color_rect
Definition: vf_paletteuse.c:516
color_info::srgb
uint32_t srgb
Definition: vf_paletteuse.c:60
PaletteUseContext::bayer_scale
int bayer_scale
Definition: vf_paletteuse.c:100
width
#define width
s
#define s(width, name)
Definition: cbs_vp9.c:198
dithering_mode
dithering_mode
Definition: vf_paletteuse.c:40
config_output
static int config_output(AVFilterLink *outlink)
Definition: vf_paletteuse.c:807
g
const char * g
Definition: vf_curves.c:127
ff_formats_ref
int ff_formats_ref(AVFilterFormats *f, AVFilterFormats **ref)
Add *ref as a new reference to formats.
Definition: formats.c:617
color_node::right_id
int right_id
Definition: vf_paletteuse.c:68
DITHERING_HECKBERT
@ DITHERING_HECKBERT
Definition: vf_paletteuse.c:43
stack_node
Definition: vf_paletteuse.c:231
filters.h
ctx
AVFormatContext * ctx
Definition: movenc.c:48
ff_lowbias32
uint32_t ff_lowbias32(uint32_t x)
Definition: palette.c:211
FILTER_INPUTS
#define FILTER_INPUTS(array)
Definition: internal.h:192
file_open.h
ff_inlink_make_frame_writable
int ff_inlink_make_frame_writable(AVFilterLink *link, AVFrame **rframe)
Make sure a frame is writable.
Definition: avfilter.c:1427
colormap_nearest
static av_always_inline uint8_t colormap_nearest(const struct color_node *node, const struct color_info *target, const int trans_thresh)
Definition: vf_paletteuse.c:224
if
if(ret)
Definition: filter_design.txt:179
color_node::palette_id
uint8_t palette_id
Definition: vf_paletteuse.c:66
load_apply_palette
static int load_apply_palette(FFFrameSync *fs)
Definition: vf_paletteuse.c:878
AVClass
Describe the class of an AVClass context structure.
Definition: log.h:66
NULL
#define NULL
Definition: coverity.c:32
ff_vf_paletteuse
const AVFilter ff_vf_paletteuse
Definition: vf_paletteuse.c:998
av_frame_copy_props
int av_frame_copy_props(AVFrame *dst, const AVFrame *src)
Copy only "metadata" fields from src to dst.
Definition: frame.c:736
PaletteUseContext::dither
int dither
Definition: vf_paletteuse.c:97
fs
#define fs(width, name, subs,...)
Definition: cbs_vp9.c:200
color_info::lab
int32_t lab[3]
Definition: vf_paletteuse.c:61
get_next_color
static int get_next_color(const uint8_t *color_used, const uint32_t *palette, int *component, const struct color_rect *box)
Definition: vf_paletteuse.c:537
AVPALETTE_SIZE
#define AVPALETTE_SIZE
Definition: pixfmt.h:32
set_frame_lut
static const set_frame_func set_frame_lut[NB_DITHERING]
Definition: vf_paletteuse.c:921
PaletteUseContext
Definition: vf_paletteuse.c:88
c
Undefined Behavior In the C some operations are like signed integer dereferencing freed accessing outside allocated Undefined Behavior must not occur in a C it is not safe even if the output of undefined operations is unused The unsafety may seem nit picking but Optimizing compilers have in fact optimized code on the assumption that no undefined Behavior occurs Optimizing code based on wrong assumptions can and has in some cases lead to effects beyond the output of computations The signed integer overflow problem in speed critical code Code which is highly optimized and works with signed integers sometimes has the problem that often the output of the computation does not c
Definition: undefined.txt:32
cmp_funcs
static const cmp_func cmp_funcs[]
Definition: vf_paletteuse.c:535
AVPALETTE_COUNT
#define AVPALETTE_COUNT
Definition: pixfmt.h:33
disp_node
static void disp_node(AVBPrint *buf, const struct color_node *map, int parent_id, int node_id, int depth)
Definition: vf_paletteuse.c:459
DITHERING_NONE
@ DITHERING_NONE
Definition: vf_paletteuse.c:41
paletteuse_options
static const AVOption paletteuse_options[]
Definition: vf_paletteuse.c:114
ff_dlog
#define ff_dlog(a,...)
Definition: tableprint_vlc.h:28
PaletteUseContext::trans_thresh
int trans_thresh
Definition: vf_paletteuse.c:95
qsort.h
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:106
ff_framesync_init_dualinput
int ff_framesync_init_dualinput(FFFrameSync *fs, AVFilterContext *parent)
Initialize a frame sync structure for dualinput.
Definition: framesync.c:372
master
const char * master
Definition: vf_curves.c:129
av_frame_ref
int av_frame_ref(AVFrame *dst, const AVFrame *src)
Set up a new reference to the data described by the source frame.
Definition: frame.c:361
av_bprint_finalize
int av_bprint_finalize(AVBPrint *buf, char **ret_str)
Finalize a print buffer.
Definition: bprint.c:240
nearest_color
Definition: vf_paletteuse.c:189
shift
static int shift(int a, int b)
Definition: bonk.c:262
DITHERING_BAYER
@ DITHERING_BAYER
Definition: vf_paletteuse.c:42
av_err2str
#define av_err2str(errnum)
Convenience macro, the return value should be used only directly in function arguments but never stan...
Definition: error.h:121
DITHERING_FLOYD_STEINBERG
@ DITHERING_FLOYD_STEINBERG
Definition: vf_paletteuse.c:44
Lab
Definition: palette.h:30
PaletteUseContext::palette
uint32_t palette[AVPALETTE_COUNT]
Definition: vf_paletteuse.c:93
color
static const uint32_t color[16+AV_CLASS_CATEGORY_NB]
Definition: log.c:94
DITHERING_SIERRA2
@ DITHERING_SIERRA2
Definition: vf_paletteuse.c:45
color::value
struct Lab value
Definition: vf_paletteuse.c:512
PaletteUseContext::fs
FFFrameSync fs
Definition: vf_paletteuse.c:90
diff
static av_always_inline int diff(const struct color_info *a, const struct color_info *b, const int trans_thresh)
Definition: vf_paletteuse.c:164
height
#define height
AV_PIX_FMT_RGB32
#define AV_PIX_FMT_RGB32
Definition: pixfmt.h:441
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
DITHERING_SIERRA2_4A
@ DITHERING_SIERRA2_4A
Definition: vf_paletteuse.c:46
PaletteUseContext::transparency_index
int transparency_index
Definition: vf_paletteuse.c:94
internal.h
DITHERING_SIERRA3
@ DITHERING_SIERRA3
Definition: vf_paletteuse.c:47
activate
static int activate(AVFilterContext *ctx)
Definition: vf_paletteuse.c:962
OFFSET
#define OFFSET(x)
Definition: vf_paletteuse.c:112
color_rect::min
int32_t min[3]
Definition: vf_paletteuse.c:517
bprint.h
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:255
cache_node
Definition: vf_paletteuse.c:78
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
internal.h
color_rect::max
int32_t max[3]
Definition: vf_paletteuse.c:518
cmp_pal_entry
static int cmp_pal_entry(const void *a, const void *b)
Definition: vf_paletteuse.c:636
delta
float delta
Definition: vorbis_enc_data.h:430
av_always_inline
#define av_always_inline
Definition: attributes.h:49
FFMIN
#define FFMIN(a, b)
Definition: macros.h:49
cache_node::entries
struct cached_color * entries
Definition: vf_paletteuse.c:79
av_frame_unref
void av_frame_unref(AVFrame *frame)
Unreference all the buffers referenced by frame and reset the frame fields.
Definition: frame.c:622
AVFilterPad::name
const char * name
Pad name.
Definition: internal.h:53
avpriv_fopen_utf8
FILE * avpriv_fopen_utf8(const char *path, const char *mode)
Open a file using a UTF-8 filename.
Definition: file_open.c:159
PaletteUseContext::diff_mode
int diff_mode
Definition: vf_paletteuse.c:102
color_node::split
int split
Definition: vf_paletteuse.c:67
cached_color::pal_entry
uint8_t pal_entry
Definition: vf_paletteuse.c:75
load_colormap
static void load_colormap(PaletteUseContext *s)
Definition: vf_paletteuse.c:643
PaletteUseContext::total_mean_err
uint64_t total_mean_err
Definition: vf_paletteuse.c:109
diff_mode
diff_mode
Definition: vf_paletteuse.c:53
FLAGS
#define FLAGS
Definition: vf_paletteuse.c:113
AVFilter
Filter definition.
Definition: avfilter.h:166
cache_node::nb_entries
int nb_entries
Definition: vf_paletteuse.c:80
AV_PIX_FMT_PAL8
@ AV_PIX_FMT_PAL8
8 bits with AV_PIX_FMT_RGB32 palette
Definition: pixfmt.h:77
ret
ret
Definition: filter_design.txt:187
FFSWAP
#define FFSWAP(type, a, b)
Definition: macros.h:52
av_bprintf
void av_bprintf(AVBPrint *buf, const char *fmt,...)
Definition: bprint.c:99
DECLARE_CMP_FUNC
#define DECLARE_CMP_FUNC(name)
Definition: vf_paletteuse.c:523
left
Tag MUST be and< 10hcoeff half pel interpolation filter coefficients, hcoeff[0] are the 2 middle coefficients[1] are the next outer ones and so on, resulting in a filter like:...eff[2], hcoeff[1], hcoeff[0], hcoeff[0], hcoeff[1], hcoeff[2] ... the sign of the coefficients is not explicitly stored but alternates after each coeff and coeff[0] is positive, so ...,+,-,+,-,+,+,-,+,-,+,... hcoeff[0] is not explicitly stored but found by subtracting the sum of all stored coefficients with signs from 32 hcoeff[0]=32 - hcoeff[1] - hcoeff[2] - ... a good choice for hcoeff and htaps is htaps=6 hcoeff={40,-10, 2} an alternative which requires more computations at both encoder and decoder side and may or may not be better is htaps=8 hcoeff={42,-14, 6,-2}ref_frames minimum of the number of available reference frames and max_ref_frames for example the first frame after a key frame always has ref_frames=1spatial_decomposition_type wavelet type 0 is a 9/7 symmetric compact integer wavelet 1 is a 5/3 symmetric compact integer wavelet others are reserved stored as delta from last, last is reset to 0 if always_reset||keyframeqlog quality(logarithmic quantizer scale) stored as delta from last, last is reset to 0 if always_reset||keyframemv_scale stored as delta from last, last is reset to 0 if always_reset||keyframe FIXME check that everything works fine if this changes between framesqbias dequantization bias stored as delta from last, last is reset to 0 if always_reset||keyframeblock_max_depth maximum depth of the block tree stored as delta from last, last is reset to 0 if always_reset||keyframequant_table quantization tableHighlevel bitstream structure:==============================--------------------------------------------|Header|--------------------------------------------|------------------------------------|||Block0||||split?||||yes no||||......... intra?||||:Block01 :yes no||||:Block02 :....... ..........||||:Block03 ::y DC ::ref index:||||:Block04 ::cb DC ::motion x :||||......... :cr DC ::motion y :||||....... ..........|||------------------------------------||------------------------------------|||Block1|||...|--------------------------------------------|------------ ------------ ------------|||Y subbands||Cb subbands||Cr subbands||||--- ---||--- ---||--- ---|||||LL0||HL0||||LL0||HL0||||LL0||HL0|||||--- ---||--- ---||--- ---||||--- ---||--- ---||--- ---|||||LH0||HH0||||LH0||HH0||||LH0||HH0|||||--- ---||--- ---||--- ---||||--- ---||--- ---||--- ---|||||HL1||LH1||||HL1||LH1||||HL1||LH1|||||--- ---||--- ---||--- ---||||--- ---||--- ---||--- ---|||||HH1||HL2||||HH1||HL2||||HH1||HL2|||||...||...||...|||------------ ------------ ------------|--------------------------------------------Decoding process:=================------------|||Subbands|------------||||------------|Intra DC||||LL0 subband prediction ------------|\ Dequantization ------------------- \||Reference frames|\ IDWT|------- -------|Motion \|||Frame 0||Frame 1||Compensation . OBMC v -------|------- -------|--------------. \------> Frame n output Frame Frame<----------------------------------/|...|------------------- Range Coder:============Binary Range Coder:------------------- The implemented range coder is an adapted version based upon "Range encoding: an algorithm for removing redundancy from a digitised message." by G. N. N. Martin. The symbols encoded by the Snow range coder are bits(0|1). The associated probabilities are not fix but change depending on the symbol mix seen so far. bit seen|new state ---------+----------------------------------------------- 0|256 - state_transition_table[256 - old_state];1|state_transition_table[old_state];state_transition_table={ 0, 0, 0, 0, 0, 0, 0, 0, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 190, 191, 192, 194, 194, 195, 196, 197, 198, 199, 200, 201, 202, 202, 204, 205, 206, 207, 208, 209, 209, 210, 211, 212, 213, 215, 215, 216, 217, 218, 219, 220, 220, 222, 223, 224, 225, 226, 227, 227, 229, 229, 230, 231, 232, 234, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 248, 0, 0, 0, 0, 0, 0, 0};FIXME Range Coding of integers:------------------------- FIXME Neighboring Blocks:===================left and top are set to the respective blocks unless they are outside of the image in which case they are set to the Null block top-left is set to the top left block unless it is outside of the image in which case it is set to the left block if this block has no larger parent block or it is at the left side of its parent block and the top right block is not outside of the image then the top right block is used for top-right else the top-left block is used Null block y, cb, cr are 128 level, ref, mx and my are 0 Motion Vector Prediction:=========================1. the motion vectors of all the neighboring blocks are scaled to compensate for the difference of reference frames scaled_mv=(mv *(256 *(current_reference+1)/(mv.reference+1))+128)> the median of the scaled left
Definition: snow.txt:386
av_frame_replace
int av_frame_replace(AVFrame *dst, const AVFrame *src)
Ensure the destination frame refers to the same data described by the source frame,...
Definition: frame.c:482
AVFrame::height
int height
Definition: frame.h:412
c2
static const uint64_t c2
Definition: murmur3.c:53
framesync.h
DIFF_MODE_RECTANGLE
@ DIFF_MODE_RECTANGLE
Definition: vf_paletteuse.c:55
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
cmp_func
int(* cmp_func)(const void *, const void *)
Definition: vf_paletteuse.c:521
PaletteUseContext::map
struct color_node map[AVPALETTE_COUNT]
Definition: vf_paletteuse.c:92
L
#define L(x)
Definition: vpx_arith.h:36
av_clip_uint8
#define av_clip_uint8
Definition: common.h:102
AVFilterContext
An instance of a filter.
Definition: avfilter.h:397
AVMEDIA_TYPE_VIDEO
@ AVMEDIA_TYPE_VIDEO
Definition: avutil.h:201
CACHE_SIZE
#define CACHE_SIZE
Definition: vf_paletteuse.c:71
map
const VDPAUPixFmtMap * map
Definition: hwcontext_vdpau.c:71
color::pal_id
uint8_t pal_id
Definition: vf_paletteuse.c:513
DITHERING_BURKES
@ DITHERING_BURKES
Definition: vf_paletteuse.c:48
AV_OPT_TYPE_BOOL
@ AV_OPT_TYPE_BOOL
Definition: opt.h:244
FILTER_OUTPUTS
#define FILTER_OUTPUTS(array)
Definition: internal.h:193
DEFINE_SET_FRAME
#define DEFINE_SET_FRAME(name, value)
Definition: vf_paletteuse.c:904
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:34
src
INIT_CLIP pixel * src
Definition: h264pred_template.c:418
DITHERING_ATKINSON
@ DITHERING_ATKINSON
Definition: vf_paletteuse.c:49
get_color_from_srgb
static struct color_info get_color_from_srgb(uint32_t srgb)
Definition: vf_paletteuse.c:182
d
d
Definition: ffmpeg_filter.c:368
paletteuse_outputs
static const AVFilterPad paletteuse_outputs[]
Definition: vf_paletteuse.c:990
int32_t
int32_t
Definition: audioconvert.c:56
PaletteUseContext::calc_mean_err
int calc_mean_err
Definition: vf_paletteuse.c:108
AVERROR_BUG
#define AVERROR_BUG
Internal bug, also see AVERROR_BUG2.
Definition: error.h:52
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:385
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:27
h
h
Definition: vp9dsp_template.c:2038
ff_framesync_activate
int ff_framesync_activate(FFFrameSync *fs)
Examine the frames in the filter's input and try to produce output.
Definition: framesync.c:355
color_node::left_id
int left_id
Definition: vf_paletteuse.c:68
color_node
Definition: vf_paletteuse.c:64
AVFILTER_DEFINE_CLASS
AVFILTER_DEFINE_CLASS(paletteuse)
AV_OPT_TYPE_STRING
@ AV_OPT_TYPE_STRING
Definition: opt.h:229
ff_framesync_dualinput_get_writable
int ff_framesync_dualinput_get_writable(FFFrameSync *fs, AVFrame **f0, AVFrame **f1)
Same as ff_framesync_dualinput_get(), but make sure that f0 is writable.
Definition: framesync.c:410
int
int
Definition: ffmpeg_filter.c:368
PaletteUseContext::last_in
AVFrame * last_in
Definition: vf_paletteuse.c:103
nearest_color::node_pos
int node_pos
Definition: vf_paletteuse.c:190
AV_OPT_TYPE_CONST
@ AV_OPT_TYPE_CONST
Definition: opt.h:234
paletteuse_inputs
static const AVFilterPad paletteuse_inputs[]
Definition: vf_paletteuse.c:979
load_palette
static void load_palette(PaletteUseContext *s, const AVFrame *palette_frame)
Definition: vf_paletteuse.c:844
cached_color
Definition: vf_paletteuse.c:73
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
nearest_color::dist_sqd
int64_t dist_sqd
Definition: vf_paletteuse.c:191
NB_DIFF_MODE
@ NB_DIFF_MODE
Definition: vf_paletteuse.c:56
Lab::L
int32_t L
Definition: palette.h:31
dither
static const uint8_t dither[8][8]
Definition: vf_fspp.c:60