59 #define HIST_SIZE (1<<(3*NBITS))
77 #define OFFSET(x) offsetof(PaletteGenContext, x)
78 #define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
80 {
"max_colors",
"set the maximum number of colors to use in the palette",
OFFSET(max_colors),
AV_OPT_TYPE_INT, {.i64=256}, 4, 256,
FLAGS },
81 {
"reserve_transparent",
"reserve a palette entry for transparency",
OFFSET(reserve_transparent),
AV_OPT_TYPE_INT, {.i64=1}, 0, 1,
FLAGS },
106 typedef int (*
cmp_func)(
const void *,
const void *);
108 #define DECLARE_CMP_FUNC(name, pos) \
109 static int cmp_##name(const void *pa, const void *pb) \
111 const struct color_ref * const *a = pa; \
112 const struct color_ref * const *b = pb; \
113 return ((*a)->color >> (8 * (2 - (pos))) & 0xff) \
114 - ((*b)->color >> (8 * (2 - (pos))) & 0xff); \
135 const uint8_t c1[] = {a >> 16 & 0xff, a >> 8 & 0xff, a & 0xff};
136 const uint8_t c2[] = {b >> 16 & 0xff, b >> 8 & 0xff, b & 0xff};
137 const int dr = c1[0] - c2[0];
138 const int dg = c1[1] - c2[1];
139 const int db = c1[2] - c2[2];
140 return dr*dr + dg*dg + db*db;
148 int box_id, i, best_box_id = -1;
149 int64_t max_variance = -1;
154 for (box_id = 0; box_id < s->
nb_boxes; box_id++) {
162 for (i = 0; i < box->
len; i++) {
169 best_box_id = box_id;
187 const int n = box->
len;
188 uint64_t
r = 0,
g = 0,
b = 0, div = 0;
190 for (i = 0; i <
n; i++) {
202 return 0xff
U<<24 | r<<16 |
g<<8 |
b;
212 new_box->
start = n + 1;
232 int x,
y, box_id = 0;
233 uint32_t *pal = (uint32_t *)out->
data[0];
234 const int pal_linesize = out->
linesize[0] >> 2;
235 uint32_t last_color = 0;
238 for (x = 0; x < out->
width; x++) {
239 if (box_id < s->nb_boxes) {
241 if ((x || y) && pal[x] == last_color)
253 pal[out->
width - pal_linesize - 1] = 0x0000ff00;
283 const double ratio = (double)nb_out / nb_in;
284 snprintf(buf,
sizeof(buf),
"%f", ratio);
316 box = &s->
boxes[box_id];
323 while (box && box->
len > 1) {
324 int i, rr, gr, br, longest;
325 uint64_t median, box_weight = 0;
330 uint8_t max[3] = {0x00, 0x00, 0x00};
333 const uint32_t rgb = ref->
color;
334 const uint8_t r = rgb >> 16 & 0xff,
g = rgb >> 8 & 0xff,
b = rgb & 0xff;
335 min[0] =
FFMIN(r, min[0]), max[0] =
FFMAX(r, max[0]);
336 min[1] =
FFMIN(g, min[1]), max[1] =
FFMAX(g, max[1]);
337 min[2] =
FFMIN(b, min[2]), max[2] =
FFMAX(b, max[2]);
338 box_weight += ref->
count;
342 rr = max[0] - min[0];
343 gr = max[1] - min[1];
344 br = max[2] - min[2];
346 if (br >= rr && br >= gr) longest = 2;
347 if (rr >= gr && rr >= br) longest = 0;
348 if (gr >= rr && gr >= br) longest = 1;
350 av_dlog(ctx,
"box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64
" ranges:[%2x %2x %2x] sort by %c (already sorted:%c) ",
352 rr, gr, br,
"rgb"[longest], box->
sorted_by == longest ?
'y':
'n');
362 median = (box_weight + 1) >> 1;
368 if (box_weight > median)
371 av_dlog(ctx,
"split @ i=%-6d with w=%-6"PRIu64
" (target=%6"PRIu64
")\n", i, box_weight, median);
375 box = box_id >= 0 ? &s->
boxes[box_id] :
NULL;
414 if (e->
color == color) {
435 int x,
y,
ret, nb_diff_colors = 0;
437 for (y = 0; y < f1->
height; y++) {
438 const uint32_t *p = (
const uint32_t *)(f1->
data[0] + y*f1->
linesize[0]);
439 const uint32_t *q = (
const uint32_t *)(f2->
data[0] + y*f2->
linesize[0]);
441 for (x = 0; x < f1->
width; x++) {
447 nb_diff_colors +=
ret;
450 return nb_diff_colors;
458 int x,
y,
ret, nb_diff_colors = 0;
460 for (y = 0; y < f->
height; y++) {
461 const uint32_t *p = (
const uint32_t *)(f->
data[0] + y*f->
linesize[0]);
463 for (x = 0; x < f->
width; x++) {
467 nb_diff_colors +=
ret;
470 return nb_diff_colors;
520 outlink->
w = outlink->
h = 16;
557 .
name =
"palettegen",
562 .
inputs = palettegen_inputs,
564 .priv_class = &palettegen_class,
static int update_histogram_frame(struct hist_node *hist, const AVFrame *f)
Simple histogram of the frame.
#define DECLARE_CMP_FUNC(name, pos)
This structure describes decoded (raw) audio or video data.
static AVFrame * get_palette_frame(AVFilterContext *ctx)
Main function implementing the Median Cut Algorithm defined by Paul Heckbert in Color Image Quantizat...
static const cmp_func cmp_funcs[]
#define AV_LOG_WARNING
Something somehow does not look correct.
static const AVFilterPad outputs[]
Main libavfilter public API header.
int h
agreed upon image height
struct color_ref * entries
static struct color_ref ** load_color_refs(const struct hist_node *hist, int nb_refs)
Crawl the histogram to get all the defined colors, and create a linear list of them (each color refer...
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.
struct range_box boxes[256]
AVFrame * ff_get_video_buffer(AVFilterLink *link, int w, int h)
Request a picture buffer with a specific set of permissions.
static uint32_t get_avg_color(struct color_ref *const *refs, const struct range_box *box)
Get the 32-bit average color for the range of RGB colors enclosed in the specified box...
static AVRational av_make_q(int num, int den)
Create a rational.
AVFILTER_DEFINE_CLASS(palettegen)
const char * name
Pad name.
AVFilterLink ** inputs
array of pointers to input links
#define av_assert0(cond)
assert() equivalent, that is always enabled.
int ff_filter_frame(AVFilterLink *link, AVFrame *frame)
Send a frame of data to the next filter.
static const uint32_t color[16+AV_CLASS_CATEGORY_NB]
int64_t pts
Presentation timestamp in time_base units (time when frame should be shown to user).
struct hist_node histogram[HIST_SIZE]
#define AVERROR_EOF
End of file.
AVDictionary * metadata
metadata.
A filter pad used for either input or output.
static unsigned color_hash(uint32_t color)
Hashing function for the color.
A link between two filters.
int width
width and height of the video frame
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
unsigned flags
Link processing flags.
static int query_formats(AVFilterContext *ctx)
static const AVOption palettegen_options[]
void av_frame_free(AVFrame **frame)
Free the frame and any dynamically allocated objects in it, e.g.
#define NULL_IF_CONFIG_SMALL(x)
Return NULL if CONFIG_SMALL is true, otherwise the argument without modification. ...
void * priv
private data for use by the filter
static int filter_frame(AVFilterLink *inlink, AVFrame *in)
Update the histogram for each passing frame.
simple assert() macros that are a bit more flexible than ISO C assert().
AVFilterFormats * in_formats
Lists of formats and channel layouts supported by the input and output filters respectively.
static const AVFilterPad palettegen_outputs[]
int w
agreed upon image width
AVFilter ff_vf_palettegen
AVFilterContext * src
source filter
static const AVFilterPad palettegen_inputs[]
static int get_next_box_id_to_split(PaletteGenContext *s)
Find the next box to split: pick the one with the highest variance.
#define av_dlog(pctx,...)
av_dlog macros
static void write_palette(AVFilterContext *ctx, AVFrame *out)
Write the palette into the output frame.
static struct AVHashContext * hash
#define AV_LOG_INFO
Standard information.
int linesize[AV_NUM_DATA_POINTERS]
For video, size in bytes of each picture line.
static av_cold void uninit(AVFilterContext *ctx)
int(* cmp_func)(const void *, const void *)
uint8_t pi<< 24) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_U8, uint8_t,(*(constuint8_t *) pi-0x80)*(1.0f/(1<< 7))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_U8, uint8_t,(*(constuint8_t *) pi-0x80)*(1.0/(1<< 7))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_S16, int16_t,(*(constint16_t *) pi >>8)+0x80) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_S16, int16_t,*(constint16_t *) pi *(1.0f/(1<< 15))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_S16, int16_t,*(constint16_t *) pi *(1.0/(1<< 15))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_S32, int32_t,(*(constint32_t *) pi >>24)+0x80) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_S32, int32_t,*(constint32_t *) pi *(1.0f/(1U<< 31))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_S32, int32_t,*(constint32_t *) pi *(1.0/(1U<< 31))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_FLT, float, av_clip_uint8(lrintf(*(constfloat *) pi *(1<< 7))+0x80)) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S16, int16_t, AV_SAMPLE_FMT_FLT, float, av_clip_int16(lrintf(*(constfloat *) pi *(1<< 15)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S32, int32_t, AV_SAMPLE_FMT_FLT, float, av_clipl_int32(llrintf(*(constfloat *) pi *(1U<< 31)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_DBL, double, av_clip_uint8(lrint(*(constdouble *) pi *(1<< 7))+0x80)) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S16, int16_t, AV_SAMPLE_FMT_DBL, double, av_clip_int16(lrint(*(constdouble *) pi *(1<< 15)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S32, int32_t, AV_SAMPLE_FMT_DBL, double, av_clipl_int32(llrint(*(constdouble *) pi *(1U<< 31))))#defineSET_CONV_FUNC_GROUP(ofmt, ifmt) staticvoidset_generic_function(AudioConvert *ac){}voidff_audio_convert_free(AudioConvert **ac){if(!*ac) return;ff_dither_free(&(*ac) ->dc);av_freep(ac);}AudioConvert *ff_audio_convert_alloc(AVAudioResampleContext *avr, enumAVSampleFormatout_fmt, enumAVSampleFormatin_fmt, intchannels, intsample_rate, intapply_map){AudioConvert *ac;intin_planar, out_planar;ac=av_mallocz(sizeof(*ac));if(!ac) returnNULL;ac->avr=avr;ac->out_fmt=out_fmt;ac->in_fmt=in_fmt;ac->channels=channels;ac->apply_map=apply_map;if(avr->dither_method!=AV_RESAMPLE_DITHER_NONE &&av_get_packed_sample_fmt(out_fmt)==AV_SAMPLE_FMT_S16 &&av_get_bytes_per_sample(in_fmt)>2){ac->dc=ff_dither_alloc(avr, out_fmt, in_fmt, channels, sample_rate, apply_map);if(!ac->dc){av_free(ac);returnNULL;}returnac;}in_planar=ff_sample_fmt_is_planar(in_fmt, channels);out_planar=ff_sample_fmt_is_planar(out_fmt, channels);if(in_planar==out_planar){ac->func_type=CONV_FUNC_TYPE_FLAT;ac->planes=in_planar?ac->channels:1;}elseif(in_planar) ac->func_type=CONV_FUNC_TYPE_INTERLEAVE;elseac->func_type=CONV_FUNC_TYPE_DEINTERLEAVE;set_generic_function(ac);if(ARCH_AARCH64) ff_audio_convert_init_aarch64(ac);if(ARCH_ARM) ff_audio_convert_init_arm(ac);if(ARCH_X86) ff_audio_convert_init_x86(ac);returnac;}intff_audio_convert(AudioConvert *ac, AudioData *out, AudioData *in){intuse_generic=1;intlen=in->nb_samples;intp;if(ac->dc){av_log(ac->avr, AV_LOG_TRACE,"%dsamples-audio_convert:%sto%s(dithered)\n", len, av_get_sample_fmt_name(ac->in_fmt), av_get_sample_fmt_name(ac->out_fmt));returnff_convert_dither(ac-> in
int av_dict_set(AVDictionary **pm, const char *key, const char *value, int flags)
Set the given entry in *pm, overwriting an existing entry.
Describe the class of an AVClass context structure.
static const AVFilterPad inputs[]
const char * name
Filter name.
AVRational sample_aspect_ratio
agreed upon sample aspect ratio
AVFilterLink ** outputs
array of pointers to output links
Frame requests may need to loop in order to be fulfilled.
uint8_t * data[AV_NUM_DATA_POINTERS]
pointer to the picture/channel planes.
static int config_output(AVFilterLink *outlink)
The output is one simple 16x16 squared-pixels palette.
static int request_frame(AVFilterLink *outlink)
Returns only one frame at the end containing the full palette.
static void split_box(PaletteGenContext *s, struct range_box *box, int n)
Split given box in two at position n.
static av_always_inline int diff(const uint32_t a, const uint32_t b)
AVFilterContext * dst
dest filter
static int color_inc(struct hist_node *hist, uint32_t color)
Locate the color in the hash table and increment its counter.
static int update_histogram_diff(struct hist_node *hist, const AVFrame *f1, const AVFrame *f2)
Update histogram when pixels differ from previous frame.
uint8_t pi<< 24) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_U8, uint8_t,(*(constuint8_t *) pi-0x80)*(1.0f/(1<< 7))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_U8, uint8_t,(*(constuint8_t *) pi-0x80)*(1.0/(1<< 7))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_S16, int16_t,(*(constint16_t *) pi >>8)+0x80) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_S16, int16_t,*(constint16_t *) pi *(1.0f/(1<< 15))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_S16, int16_t,*(constint16_t *) pi *(1.0/(1<< 15))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_S32, int32_t,(*(constint32_t *) pi >>24)+0x80) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_S32, int32_t,*(constint32_t *) pi *(1.0f/(1U<< 31))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_S32, int32_t,*(constint32_t *) pi *(1.0/(1U<< 31))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_FLT, float, av_clip_uint8(lrintf(*(constfloat *) pi *(1<< 7))+0x80)) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S16, int16_t, AV_SAMPLE_FMT_FLT, float, av_clip_int16(lrintf(*(constfloat *) pi *(1<< 15)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S32, int32_t, AV_SAMPLE_FMT_FLT, float, av_clipl_int32(llrintf(*(constfloat *) pi *(1U<< 31)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_DBL, double, av_clip_uint8(lrint(*(constdouble *) pi *(1<< 7))+0x80)) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S16, int16_t, AV_SAMPLE_FMT_DBL, double, av_clip_int16(lrint(*(constdouble *) pi *(1<< 15)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S32, int32_t, AV_SAMPLE_FMT_DBL, double, av_clipl_int32(llrint(*(constdouble *) pi *(1U<< 31))))#defineSET_CONV_FUNC_GROUP(ofmt, ifmt) staticvoidset_generic_function(AudioConvert *ac){}voidff_audio_convert_free(AudioConvert **ac){if(!*ac) return;ff_dither_free(&(*ac) ->dc);av_freep(ac);}AudioConvert *ff_audio_convert_alloc(AVAudioResampleContext *avr, enumAVSampleFormatout_fmt, enumAVSampleFormatin_fmt, intchannels, intsample_rate, intapply_map){AudioConvert *ac;intin_planar, out_planar;ac=av_mallocz(sizeof(*ac));if(!ac) returnNULL;ac->avr=avr;ac->out_fmt=out_fmt;ac->in_fmt=in_fmt;ac->channels=channels;ac->apply_map=apply_map;if(avr->dither_method!=AV_RESAMPLE_DITHER_NONE &&av_get_packed_sample_fmt(out_fmt)==AV_SAMPLE_FMT_S16 &&av_get_bytes_per_sample(in_fmt)>2){ac->dc=ff_dither_alloc(avr, out_fmt, in_fmt, channels, sample_rate, apply_map);if(!ac->dc){av_free(ac);returnNULL;}returnac;}in_planar=ff_sample_fmt_is_planar(in_fmt, channels);out_planar=ff_sample_fmt_is_planar(out_fmt, channels);if(in_planar==out_planar){ac->func_type=CONV_FUNC_TYPE_FLAT;ac->planes=in_planar?ac->channels:1;}elseif(in_planar) ac->func_type=CONV_FUNC_TYPE_INTERLEAVE;elseac->func_type=CONV_FUNC_TYPE_DEINTERLEAVE;set_generic_function(ac);if(ARCH_AARCH64) ff_audio_convert_init_aarch64(ac);if(ARCH_ARM) ff_audio_convert_init_arm(ac);if(ARCH_X86) ff_audio_convert_init_x86(ac);returnac;}intff_audio_convert(AudioConvert *ac, AudioData *out, AudioData *in){intuse_generic=1;intlen=in->nb_samples;intp;if(ac->dc){av_log(ac->avr, AV_LOG_TRACE,"%dsamples-audio_convert:%sto%s(dithered)\n", len, av_get_sample_fmt_name(ac->in_fmt), av_get_sample_fmt_name(ac->out_fmt));returnff_convert_dither(ac-> out
#define av_malloc_array(a, b)
static int cmp_color(const void *a, const void *b)
Simple color comparison for sorting the final palette.
int ff_request_frame(AVFilterLink *link)
Request an input frame from the filter at the other end of the link.
AVPixelFormat
Pixel format.
static double set_colorquant_ratio_meta(AVFrame *out, int nb_out, int nb_in)
#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...
AVFilterFormats * out_formats