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