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