#include "libavutil/avassert.h"
#include "libavutil/internal.h"
#include "libavutil/opt.h"
#include "libavutil/qsort.h"
#include "libavutil/intreadwrite.h"
#include "avfilter.h"
#include "internal.h"

Data Structures
struct	color_ref

struct	range_box

struct	hist_node

struct	PaletteGenContext

Macros
#define	NBITS 5

#define	HIST_SIZE (1<<(4*NBITS))

#define	OFFSET(x) offsetof(PaletteGenContext, x)

#define	FLAGS AV_OPT_FLAG_FILTERING_PARAM\|AV_OPT_FLAG_VIDEO_PARAM

#define	DECLARE_CMP_FUNC(name, pos)

Typedefs
typedef int(*	cmp_func) (const void , const void )

Enumerations
enum	{ STATS_MODE_ALL_FRAMES, STATS_MODE_DIFF_FRAMES, STATS_MODE_SINGLE_FRAMES, NB_STATS_MODE }

Functions
	AVFILTER_DEFINE_CLASS (palettegen)

static int	query_formats (AVFilterContext *ctx)

static int	cmp_color (const void a, const void b)
	Simple color comparison for sorting the final palette. More...

static av_always_inline int	diff (const uint32_t a, const uint32_t b)

static av_always_inline int	diff_alpha (const uint32_t a, const uint32_t b)

static int	get_next_box_id_to_split (PaletteGenContext *s)
	Find the next box to split: pick the one with the highest variance. More...

static uint32_t	get_avg_color (struct color_ref const refs, const struct range_box *box, int use_alpha)
	Get the 32-bit average color for the range of RGB colors enclosed in the specified box. More...

static void	split_box (PaletteGenContext s, struct range_box box, int n)
	Split given box in two at position n. More...

static void	write_palette (AVFilterContext ctx, AVFrame out)
	Write the palette into the output frame. More...

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 reference entry is a pointer to the value in the histogram/hash table). More...

static double	set_colorquant_ratio_meta (AVFrame *out, int nb_out, int nb_in)

static AVFrame *	get_palette_frame (AVFilterContext *ctx)
	Main function implementing the Median Cut Algorithm defined by Paul Heckbert in Color Image Quantization for Frame Buffer Display (1982) More...

static unsigned	color_hash (uint32_t color, int use_alpha)
	Hashing function for the color. More...

static int	color_inc (struct hist_node *hist, uint32_t color, int use_alpha)
	Locate the color in the hash table and increment its counter. More...

static int	update_histogram_diff (struct hist_node hist, const AVFrame f1, const AVFrame *f2, int use_alpha)
	Update histogram when pixels differ from previous frame. More...

static int	update_histogram_frame (struct hist_node hist, const AVFrame f, int use_alpha)
	Simple histogram of the frame. More...

static int	filter_frame (AVFilterLink inlink, AVFrame in)
	Update the histogram for each passing frame. More...

static int	request_frame (AVFilterLink *outlink)
	Returns only one frame at the end containing the full palette. More...

static int	config_output (AVFilterLink *outlink)
	The output is one simple 16x16 squared-pixels palette. More...

static int	init (AVFilterContext *ctx)

static av_cold void	uninit (AVFilterContext *ctx)

Variables
static const AVOption	palettegen_options []

static const cmp_func	cmp_funcs [] = {cmp_a, cmp_r, cmp_g, cmp_b}

static const AVFilterPad	palettegen_inputs []

static const AVFilterPad	palettegen_outputs []

const AVFilter	ff_vf_palettegen

Detailed Description

Generate one palette for a whole video stream.

Definition in file vf_palettegen.c.

Macro Definition Documentation

◆ NBITS

#define NBITS 5

Definition at line 61 of file vf_palettegen.c.

◆ HIST_SIZE

#define HIST_SIZE (1<<(4*NBITS))

Definition at line 62 of file vf_palettegen.c.

◆ OFFSET

#define OFFSET ( x ) offsetof(PaletteGenContext, x)

Definition at line 82 of file vf_palettegen.c.

◆ FLAGS

#define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM

Definition at line 83 of file vf_palettegen.c.

◆ DECLARE_CMP_FUNC

#define DECLARE_CMP_FUNC	(	name,
		pos
	)

Value:

static int cmp_##name(const void *pa, const void *pb)   \
{                                                       \
    const struct color_ref * const *a = pa;             \
    const struct color_ref * const *b = pb;             \
    return   (int)((*a)->color >> (8 * (3 - (pos))) & 0xff)  \
           - (int)((*b)->color >> (8 * (3 - (pos))) & 0xff); \
}

Definition at line 113 of file vf_palettegen.c.

Typedef Documentation

◆ cmp_func

typedef int(* cmp_func) (const void *, const void *)

Definition at line 111 of file vf_palettegen.c.

Enumeration Type Documentation

◆ anonymous enum

anonymous enum

Enumerator
STATS_MODE_ALL_FRAMES
STATS_MODE_DIFF_FRAMES
STATS_MODE_SINGLE_FRAMES
NB_STATS_MODE

Definition at line 54 of file vf_palettegen.c.

Function Documentation

◆ AVFILTER_DEFINE_CLASS()

AVFILTER_DEFINE_CLASS ( palettegen )

◆ query_formats()

static int query_formats ( AVFilterContext * ctx )

static

Definition at line 98 of file vf_palettegen.c.

◆ cmp_color()

static int cmp_color	(	const void *	a,
		const void *	b
	)

static

Simple color comparison for sorting the final palette.

Definition at line 132 of file vf_palettegen.c.

Referenced by get_palette_frame().

◆ diff()

static av_always_inline int diff	(	const uint32_t	a,
		const uint32_t	b
	)

static

Definition at line 139 of file vf_palettegen.c.

Referenced by activate(), add_hfyu_median_pred_int16_c(), add_lag_median_prediction(), add_median_pred_c(), add_median_prediction(), adpcm_ct_expand_nibble(), adpcm_decode_frame(), adpcm_ima_alp_compress_sample(), adpcm_ima_alp_expand_nibble(), adpcm_ima_expand_nibble(), adpcm_ima_oki_expand_nibble(), adpcm_ima_qt_compress_sample(), adpcm_ima_qt_expand_nibble(), adpcm_ima_wav_expand_nibble(), adpcm_sbpro_expand_nibble(), amplify_frame(), aptx_encode_channel(), arith2_get_consumed_bytes(), asf_read_frame_header(), block_angle(), blur(), build_diff_map(), calc_slice_sizes(), cbs_av1_get_relative_dist(), celt_decode_tf_changes(), celt_enc_tf(), celt_quant_fine(), check_add_median_pred(), codebook_sanity_check_for_rate_quarter(), comp_harmonic_coeff(), compare_blocks(), compute_target_delay(), config_filter(), copy_region_enc(), deband_16_c(), deband_8_c(), decode_channel_sf_idx(), decode_channel_wordlen(), decode_dc(), decode_frame(), decode_line_TMPL(), decode_residual(), decode_tones_amplitude(), dering_TMPL(), detect_scene_change(), diff_c(), dnxhd_calc_bits_thread(), dnxhd_encode_dc(), do_chromahold16_slice(), do_chromahold_slice(), do_chromakey_pixel(), do_chromakey_pixel16(), do_colorkey_pixel(), do_hsvkey_pixel(), dpcm_decode_frame(), dpcm_predict(), draw_spatial(), dts_probe(), encode_block(), encode_dc(), encode_high(), encode_line_TMPL(), encode_low(), encode_residual_ch(), encode_scale_factors(), enqueue_packet(), est_alpha_diff(), estimate_pitch(), eval_sse(), exp_quant_coarse(), fbdev_write_packet(), ff_dcaadpcm_subband_analysis(), ff_libwebp_get_frame(), ff_mpeg1_decode_block_intra(), ff_mpeg4_encode_mb(), ff_rate_estimate_qscale(), filter_frame(), find_block_motion(), find_missing_packets(), find_timestamp_in_playlist(), fixed_gain_smooth(), fold(), get_closest_codebook(), get_next_box_id_to_split(), get_pts(), get_relative_dist(), get_scene_score(), get_video_frame(), glyph_cmp(), h263_decode_block(), index_mb(), init_quantized_coeffs_elem0(), inv_predict_11(), IsAlmostEqual(), limitdiff16(), limitdiff8(), ljpeg_encode_bgr(), lsf2lsp(), lsf_decode(), magicyuv_median_pred16(), main(), make_noises(), max_component_diff(), mdec_decode_block_intra(), mf_enca_output_score(), motion_search(), movie_push_frame(), mpeg2_decode_block_intra(), mpeg2_fast_decode_block_intra(), mvi_predict(), no_codebook_bits(), parse_playlist(), parse_tonal(), perform_dc_correction(), pixel_color7_slow(), process_subpacket_9(), put_alpha_diff(), pxr24_uncompress(), rgb2yuv_fsb(), rtp_parse_one_packet(), rv30_weak_loop_filter(), rv40_weak_loop_filter(), sad_hv_bilinear_filter_16width_msa(), sad_hv_bilinear_filter_8width_msa(), select_from_pts_buffer(), silk_stabilize_lsf(), speedhq_init_static_data(), svq1_decode_motion_vector(), swap_samplerates_on_filter(), synchronize_audio(), tm2_null_res_block(), truemotion2rt_decode_frame(), update_qscale(), validate_options(), vp8_handle_packet(), wavpack_encode_block(), and wmv2_pred_motion().

◆ diff_alpha()

static av_always_inline int diff_alpha	(	const uint32_t	a,
		const uint32_t	b
	)

static

Definition at line 149 of file vf_palettegen.c.

Referenced by get_next_box_id_to_split().

◆ get_next_box_id_to_split()

static int get_next_box_id_to_split ( PaletteGenContext * s )

static

Find the next box to split: pick the one with the highest variance.

Definition at line 163 of file vf_palettegen.c.

Referenced by get_palette_frame().

◆ get_avg_color()

static uint32_t get_avg_color	(	struct color_ref const	refs,
		const struct range_box *	box,
		int	use_alpha
	)

static

Get the 32-bit average color for the range of RGB colors enclosed in the specified box.

Takes into account the weight of each color.

Definition at line 203 of file vf_palettegen.c.

Referenced by get_palette_frame(), and split_box().

◆ split_box()

static void split_box	(	PaletteGenContext *	s,
		struct range_box *	box,
		int	n
	)

static

Split given box in two at position n.

The original box becomes the left part of the split, and the new index box is the right part.

Definition at line 236 of file vf_palettegen.c.

Referenced by get_palette_frame().

◆ write_palette()

static void write_palette	(	AVFilterContext *	ctx,
		AVFrame *	out
	)

static

Write the palette into the output frame.

Definition at line 256 of file vf_palettegen.c.

Referenced by get_palette_frame().

◆ load_color_refs()

static struct color_ref** load_color_refs	(	const struct hist_node *	hist,
		int	nb_refs
	)

static

Crawl the histogram to get all the defined colors, and create a linear list of them (each color reference entry is a pointer to the value in the histogram/hash table).

Definition at line 289 of file vf_palettegen.c.

Referenced by get_palette_frame().

◆ set_colorquant_ratio_meta()

static double set_colorquant_ratio_meta	(	AVFrame *	out,
		int	nb_out,
		int	nb_in
	)

static

Definition at line 307 of file vf_palettegen.c.

Referenced by get_palette_frame().

◆ get_palette_frame()

static AVFrame* get_palette_frame ( AVFilterContext * ctx )

static

Main function implementing the Median Cut Algorithm defined by Paul Heckbert in Color Image Quantization for Frame Buffer Display (1982)

Definition at line 320 of file vf_palettegen.c.

Referenced by filter_frame(), and request_frame().

◆ color_hash()

static unsigned color_hash	(	uint32_t	color,
		int	use_alpha
	)

inlinestatic

Hashing function for the color.

It keeps the NBITS least significant bit of each component to make it "random" even if the scene doesn't have much different colors.

Definition at line 430 of file vf_palettegen.c.

Referenced by color_inc().

◆ color_inc()

static int color_inc	(	struct hist_node *	hist,
		uint32_t	color,
		int	use_alpha
	)

static

Locate the color in the hash table and increment its counter.

Definition at line 447 of file vf_palettegen.c.

Referenced by update_histogram_diff(), and update_histogram_frame().

◆ update_histogram_diff()

static int update_histogram_diff	(	struct hist_node *	hist,
		const AVFrame *	f1,
		const AVFrame *	f2,
		int	use_alpha
	)

static

Update histogram when pixels differ from previous frame.

Definition at line 474 of file vf_palettegen.c.

Referenced by filter_frame().

◆ update_histogram_frame()

static int update_histogram_frame	(	struct hist_node *	hist,
		const AVFrame *	f,
		int	use_alpha
	)

static

Simple histogram of the frame.

Definition at line 498 of file vf_palettegen.c.

Referenced by filter_frame().

◆ filter_frame()

static int filter_frame	(	AVFilterLink *	inlink,
		AVFrame *	in
	)

static

Update the histogram for each passing frame.

No frame will be pushed here.

Definition at line 518 of file vf_palettegen.c.

◆ request_frame()

static int request_frame ( AVFilterLink * outlink )

static

Returns only one frame at the end containing the full palette.

Definition at line 556 of file vf_palettegen.c.

◆ config_output()

static int config_output ( AVFilterLink * outlink )

static

The output is one simple 16x16 squared-pixels palette.

Definition at line 575 of file vf_palettegen.c.

◆ init()

static int init ( AVFilterContext * ctx )

static

Definition at line 582 of file vf_palettegen.c.

◆ uninit()

static av_cold void uninit ( AVFilterContext * ctx )

static

Definition at line 592 of file vf_palettegen.c.

Variable Documentation

◆ palettegen_options

const AVOption palettegen_options[]

static

Initial value:

= {
    { "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 },
    { "reserve_transparent", "reserve a palette entry for transparency", OFFSET(reserve_transparent), AV_OPT_TYPE_BOOL, {.i64=1}, 0, 1, FLAGS },
    { "transparency_color", "set a background color for transparency", OFFSET(transparency_color), AV_OPT_TYPE_COLOR, {.str="lime"}, 0, 0, FLAGS },
    { "stats_mode", "set statistics mode", OFFSET(stats_mode), AV_OPT_TYPE_INT, {.i64=STATS_MODE_ALL_FRAMES}, 0, NB_STATS_MODE-1, FLAGS, "mode" },
        { "full", "compute full frame histograms", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_ALL_FRAMES}, INT_MIN, INT_MAX, FLAGS, "mode" },
        { "diff", "compute histograms only for the part that differs from previous frame", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_DIFF_FRAMES}, INT_MIN, INT_MAX, FLAGS, "mode" },
        { "single", "compute new histogram for each frame", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_SINGLE_FRAMES}, INT_MIN, INT_MAX, FLAGS, "mode" },
    { "use_alpha", "create a palette including alpha values", OFFSET(use_alpha), AV_OPT_TYPE_BOOL, {.i64 = 0}, 0, 1, FLAGS },
    { NULL }
}

Definition at line 84 of file vf_palettegen.c.

◆ cmp_funcs

const cmp_func cmp_funcs[] = {cmp_a, cmp_r, cmp_g, cmp_b}

static

Definition at line 127 of file vf_palettegen.c.

Referenced by get_palette_frame().

◆ palettegen_inputs

const AVFilterPad palettegen_inputs[]

static

Initial value:

= {
    {
        .name         = "default",
        .type         = AVMEDIA_TYPE_VIDEO,
        .filter_frame = filter_frame,
    },
}

Definition at line 603 of file vf_palettegen.c.

◆ palettegen_outputs

const AVFilterPad palettegen_outputs[]

static

Initial value:

= {
    {
        .name          = "default",
        .type          = AVMEDIA_TYPE_VIDEO,
        .config_props  = config_output,
        .request_frame = request_frame,
    },
}

Definition at line 611 of file vf_palettegen.c.

◆ ff_vf_palettegen

const AVFilter ff_vf_palettegen

Initial value:

= {
    .name          = "palettegen",
    .description   = NULL_IF_CONFIG_SMALL("Find the optimal palette for a given stream."),
    .priv_size     = sizeof(PaletteGenContext),
    .init          = init,
    .uninit        = uninit,
    FILTER_INPUTS(palettegen_inputs),
    FILTER_OUTPUTS(palettegen_outputs),
    FILTER_QUERY_FUNC(query_formats),
    .priv_class    = &palettegen_class,
}

Definition at line 620 of file vf_palettegen.c.

Data Structures

Macros

Typedefs

Enumerations

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ NBITS

◆ HIST_SIZE

◆ OFFSET

◆ FLAGS

◆ DECLARE_CMP_FUNC

Typedef Documentation

◆ cmp_func

Enumeration Type Documentation

◆ anonymous enum

Function Documentation

◆ AVFILTER_DEFINE_CLASS()

◆ query_formats()

◆ cmp_color()

◆ diff()

◆ diff_alpha()

◆ get_next_box_id_to_split()

◆ get_avg_color()

◆ split_box()

◆ write_palette()

◆ load_color_refs()

◆ set_colorquant_ratio_meta()

◆ get_palette_frame()

◆ color_hash()

◆ color_inc()

◆ update_histogram_diff()

◆ update_histogram_frame()

◆ filter_frame()

◆ request_frame()

◆ config_output()

◆ init()

◆ uninit()

Variable Documentation

◆ palettegen_options

◆ cmp_funcs

◆ palettegen_inputs

◆ palettegen_outputs

◆ ff_vf_palettegen