vf_latticepal.c File Reference

Convert packed RGB/BGR to PAL8 with a per-frame palette whose colors sit on a face-centered cubic (FCC) lattice. More...

#include <math.h>
#include "libavutil/lfg.h"
#include "libavutil/mem.h"
#include "libavutil/opt.h"
#include "libavutil/pixdesc.h"
#include "avfilter.h"
#include "filters.h"
#include "formats.h"
#include "video.h"

Go to the source code of this file.

Data Structures
struct	PalEntry
struct	LatticePalContext
struct	HeapEnt

Macros
#define	MAX_DENSITY   255
#define	MAX_DENSITY_ALPHA   64
#define	VC_SHIFT   6
#define	VC_SIZE   (1 << VC_SHIFT)
#define	VC_AREA   (VC_SIZE * VC_SIZE)
#define	VC_MASK   (VC_SIZE - 1)
#define	VC_SIGMA   1.5f
#define	VC_RADIUS   7
#define	VC_KSIZE   (2 * VC_RADIUS + 1)
#define	OFFSET(x)
#define	FLAGS   AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
#define	CHECK_CELL3(a, b, c)
#define	CHECK_CELL4(a, b, c, l)

Enumerations
enum	dithering_mode {   DITHERING_NONE , DITHERING_BAYER , DITHERING_BLUE_NOISE , DITHERING_FLOYD_STEINBERG ,   NB_DITHERING }
enum	refine_mode {   REFINE_NONE , REFINE_FULL , REFINE_RESIDUAL , REFINE_BATCHED ,   NB_REFINE }

Functions
	AVFILTER_DEFINE_CLASS (latticepal)
static int	query_formats (const AVFilterContext *ctx, AVFilterFormatsConfig **cfg_in, AVFilterFormatsConfig **cfg_out)
static void	vc_splat (float *energy, const float *kern, int pos, float sign)
	Add (sign > 0) or remove (sign < 0) the Gaussian energy contribution of a minority pixel at position pos on the VC_SIZE x VC_SIZE torus.
static int	vc_extreme (const float *energy, const uint8_t *bits, int want_set, int find_max)
	Position of the extreme energy value among the cells whose bit equals want_set: the tightest cluster (find_max, among minority pixels) or the largest void (!find_max, among majority pixels).
static void	vc_generate (uint16_t *rank, uint8_t *bits, float *energy, float *e1, const float *kern, AVLFG *lfg)
	Generate a void-and-cluster blue noise rank matrix (Ulichney 1993): every cell gets a unique rank in [0, VC_AREA).
static av_always_inline void	quant_dn (const LatticePalContext *s, const int *in, int f[4])
	Quantize a color to the nearest point of the scaled D3 (FCC) or D4 lattice.
static av_always_inline int	color_inc (LatticePalContext *s, const int f[4])
	Account one pixel using the lattice color with indices f, registering the color in the cell table and the used color list on first use.
static int	nearest_alive (LatticePalContext *s, const uint8_t ci[4], int self, int *out_d2)
	Find the nearest live color of the used color list, excluding self (pass -1 to match any live color).
static void	nn_search (LatticePalContext *s, int self)
static void	heap_push (HeapEnt *heap, int *nb, int64_t imp, int idx)
static HeapEnt	heap_pop (HeapEnt *heap, int *nb)
static int	reduce_colors (LatticePalContext *s, int target)
	Reduce the live colors down to target by repeatedly dropping the color whose removal has the least impact: its pixel count times the squared distance to the nearest remaining color, which then absorbs the dropped pixels.
static av_always_inline uint32_t	entry_color (const LatticePalContext *s, const PalEntry *e)
	Palette color (AARRGGBB) of a used color list entry.
static int	refine_full (LatticePalContext *s, AVFrame *out, const AVFrame *in)
	Full refinement pass: rediffuse the whole frame against the final palette.
static int	refine_residual (LatticePalContext *s, AVFrame *out, const AVFrame *in)
	Residual refinement pass: rediffuse only the error of the dropped colors, using the first pass quantized color as the diffusion target.
static int	batch_assign (LatticePalContext *s, const AVFrame *in)
	Rediffuse the whole frame against the current live colors and reassign every pixel, recounting how often each live color is actually used.
static int	reduce_batched (LatticePalContext *s, const AVFrame *in)
	Batched reduction: instead of dropping all excess colors against the first pass statistics, drop half of the excess, rediffuse the frame against the survivors and recount from the actual assignments, then repeat.
static int	filter_frame (AVFilterLink *inlink, AVFrame *in)
static int	config_input (AVFilterLink *inlink)
static av_cold void	uninit (AVFilterContext *ctx)

Variables
static const AVOption	latticepal_options []
static const uint8_t	dither_8x8_73 [8][8]
static const AVFilterPad	latticepal_inputs []
const FFFilter	ff_vf_latticepal

Detailed Description

Convert packed RGB/BGR to PAL8 with a per-frame palette whose colors sit on a face-centered cubic (FCC) lattice.

The FCC lattice is realized as the D3 checkerboard lattice: the points (i,j,k) with an even coordinate sum, scaled so that the density option is the number of lattice steps spanning one color axis (0..255). Only the lattice points actually used by a frame enter its palette; if a frame uses more than 256 of them, the used colors are reduced by iteratively dropping the color whose removal has the least impact and mapping its pixels to the nearest remaining color.

Definition in file vf_latticepal.c.

Macro Definition Documentation

MAX_DENSITY

#define MAX_DENSITY   255

Definition at line 45 of file vf_latticepal.c.

MAX_DENSITY_ALPHA

#define MAX_DENSITY_ALPHA   64

Definition at line 46 of file vf_latticepal.c.

Referenced by config_input().

VC_SHIFT

#define VC_SHIFT   6

Definition at line 65 of file vf_latticepal.c.

Referenced by filter_frame(), and vc_splat().

VC_SIZE

#define VC_SIZE   (1 << VC_SHIFT)

Definition at line 66 of file vf_latticepal.c.

VC_AREA

#define VC_AREA   (VC_SIZE * VC_SIZE)

Definition at line 67 of file vf_latticepal.c.

Referenced by config_input(), vc_extreme(), and vc_generate().

VC_MASK

#define VC_MASK   (VC_SIZE - 1)

Definition at line 68 of file vf_latticepal.c.

Referenced by filter_frame(), and vc_splat().

VC_SIGMA

#define VC_SIGMA   1.5f

Definition at line 69 of file vf_latticepal.c.

Referenced by config_input().

VC_RADIUS

#define VC_RADIUS   7

Definition at line 70 of file vf_latticepal.c.

Referenced by config_input(), and vc_splat().

VC_KSIZE

#define VC_KSIZE   (2 * VC_RADIUS + 1)

Definition at line 71 of file vf_latticepal.c.

Referenced by config_input(), and vc_splat().

OFFSET

#define OFFSET

(

x

)

Value:

offsetof(LatticePalContext, x)

Definition at line 116 of file vf_latticepal.c.

FLAGS

#define FLAGS   AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM

Definition at line 117 of file vf_latticepal.c.

CHECK_CELL3

#define CHECK_CELL3	(		a,
			b,
			c )

Value:

    do {                                       \
    const int e = s->cell[((a) * dim + (b)) * dim + (c)];               \
    if (e > 0 && e - 1 != self && list[e - 1].alive) {                  \
        const int dr = val[a] - v0;                                     \
        const int dg = val[b] - v1;                                     \
        const int db = val[c] - v2;                                     \
        const int d2 = dr * dr + dg * dg + db * db;                     \
        if (d2 < bestd) {                                               \
            bestd = d2;                                                 \
            best  = e - 1;                                              \
        }                                                               \
    }                                                                   \
} while (0)

Referenced by nearest_alive().

CHECK_CELL4

#define CHECK_CELL4	(		a,
			b,
			c,
			l )

Value:

    do {                                    \
    const int e = s->cell[(((a) * dim + (b)) * dim + (c)) * dim + (l)]; \
    if (e > 0 && e - 1 != self && list[e - 1].alive) {                  \
        const int dr = val[a] - v0;                                     \
        const int dg = val[b] - v1;                                     \
        const int db = val[c] - v2;                                     \
        const int da_ = val[l] - v3;                                    \
        const int d2 = dr * dr + dg * dg + db * db + da_ * da_;         \
        if (d2 < bestd) {                                               \
            bestd = d2;                                                 \
            best  = e - 1;                                              \
        }                                                               \
    }                                                                   \
} while (0)

Referenced by nearest_alive().

Enumeration Type Documentation

dithering_mode

enum dithering_mode

Enumerator
DITHERING_NONE
DITHERING_BAYER
DITHERING_BLUE_NOISE
DITHERING_FLOYD_STEINBERG
NB_DITHERING

Definition at line 48 of file vf_latticepal.c.

refine_mode

enum refine_mode

Enumerator
REFINE_NONE
REFINE_FULL
REFINE_RESIDUAL
REFINE_BATCHED
NB_REFINE

Definition at line 56 of file vf_latticepal.c.

Function Documentation

AVFILTER_DEFINE_CLASS()

AVFILTER_DEFINE_CLASS

(

latticepal

)

query_formats()

static int query_formats ( const AVFilterContext * ctx, AVFilterFormatsConfig ** cfg_in, AVFilterFormatsConfig ** cfg_out )

static

Definition at line 137 of file vf_latticepal.c.

vc_splat()

static void vc_splat ( float * energy, const float * kern, int pos, float sign )

static

Add (sign > 0) or remove (sign < 0) the Gaussian energy contribution of a minority pixel at position pos on the VC_SIZE x VC_SIZE torus.

Definition at line 175 of file vf_latticepal.c.

Referenced by vc_generate().

vc_extreme()

static int vc_extreme ( const float * energy, const uint8_t * bits, int want_set, int find_max )

static

Position of the extreme energy value among the cells whose bit equals want_set: the tightest cluster (find_max, among minority pixels) or the largest void (!find_max, among majority pixels).

Definition at line 194 of file vf_latticepal.c.

Referenced by vc_generate().

vc_generate()

static void vc_generate ( uint16_t * rank, uint8_t * bits, float * energy, float * e1, const float * kern, AVLFG * lfg )

static

Generate a void-and-cluster blue noise rank matrix (Ulichney 1993): every cell gets a unique rank in [0, VC_AREA).

On a torus the filtered field of the zero pattern is the constant kernel sum minus the field of the one pattern, so the tightest cluster of zeros coincides with the largest void of ones and the ranking above 50% fill needs no separate phase.

Definition at line 219 of file vf_latticepal.c.

Referenced by config_input().

quant_dn()

static av_always_inline void quant_dn ( const LatticePalContext * s, const int * in, int f[4] )

static

Quantize a color to the nearest point of the scaled D3 (FCC) or D4 lattice.

Conway & Sloane: round every coordinate to the nearest integer; if the coordinate sum is odd, re-round the coordinate with the largest rounding error in the other direction. This works for any checkerboard lattice Dn.

Parameters

in	the nc input components
f	receives the nc lattice indices

Definition at line 281 of file vf_latticepal.c.

Referenced by batch_assign(), filter_frame(), refine_full(), and refine_residual().

color_inc()

static av_always_inline int color_inc ( LatticePalContext * s, const int f[4] )

static

Account one pixel using the lattice color with indices f, registering the color in the cell table and the used color list on first use.

Returns

the lattice cell position, or AVERROR(ENOMEM)

Definition at line 313 of file vf_latticepal.c.

Referenced by filter_frame().

nearest_alive()

static int nearest_alive ( LatticePalContext * s, const uint8_t ci[4], int self, int * out_d2 )

static

Find the nearest live color of the used color list, excluding self (pass -1 to match any live color).

While many colors are alive, search outward in Chebyshev shells of the lattice index space; the component value difference of a cell r shells away is at least r * min_gap, which bounds the search once a candidate is known. When only few colors are left the lattice around them is sparse and shells get expensive, so scan the compact live list instead. (For 3 components ci[3] is 0 everywhere, contributing nothing.)

Returns

list index of the nearest live color, its distance in *out_d2

Definition at line 360 of file vf_latticepal.c.

Referenced by batch_assign(), and nn_search().

nn_search()

static void nn_search ( LatticePalContext * s, int self )

static

Definition at line 462 of file vf_latticepal.c.

Referenced by filter_frame(), and reduce_colors().

heap_push()

static void heap_push ( HeapEnt * heap, int * nb, int64_t imp, int idx )

static

Definition at line 475 of file vf_latticepal.c.

Referenced by reduce_colors().

heap_pop()

static HeapEnt heap_pop ( HeapEnt * heap, int * nb )

static

Definition at line 487 of file vf_latticepal.c.

Referenced by reduce_colors().

reduce_colors()

static int reduce_colors ( LatticePalContext * s, int target )

static

Reduce the live colors down to target by repeatedly dropping the color whose removal has the least impact: its pixel count times the squared distance to the nearest remaining color, which then absorbs the dropped pixels.

An impact can only grow: counts grow by absorption and the nearest neighbor distance grows when the neighbor is dropped. Stale heap entries therefore underestimate their color's impact, and validating at pop time and re-pushing the corrected entry yields the exact minimum.

Definition at line 516 of file vf_latticepal.c.

Referenced by filter_frame(), and reduce_batched().

entry_color()

static av_always_inline uint32_t entry_color ( const LatticePalContext * s, const PalEntry * e )

static

Palette color (AARRGGBB) of a used color list entry.

Definition at line 590 of file vf_latticepal.c.

Referenced by filter_frame().

refine_full()

static int refine_full ( LatticePalContext * s, AVFrame * out, const AVFrame * in )

static

Full refinement pass: rediffuse the whole frame against the final palette.

The first pass diffused its error against the full lattice, so the shift from dropped colors to their nearest survivor is uncompensated and shows up as flat discolored patches exactly where the reduction hit. Re-run Floyd-Steinberg error diffusion on the original pixels, quantizing to the nearest final palette color, which redistributes that error by construction (error diffusion is average correct against any codebook).

The nearest palette color is resolved at lattice cell granularity: used cells already hold their slot from the remap, cells first touched by the diffusion get a scan over the at most 256 survivors and are cached in the cell table and recorded for the per frame reset.

Definition at line 614 of file vf_latticepal.c.

Referenced by filter_frame().

refine_residual()

static int refine_residual ( LatticePalContext * s, AVFrame * out, const AVFrame * in )

static

Residual refinement pass: rediffuse only the error of the dropped colors, using the first pass quantized color as the diffusion target.

The error stream then carries only the removal residuals: a pixel whose color survived and that receives no incoming residual picks its own color with zero error and is unchanged, keeping the character of the selected dither mode outside the reduced regions.

Runs before the cell table is rewritten: cells hold list indices, and cells resolved on demand are cached as -(slot + 1).

Definition at line 712 of file vf_latticepal.c.

Referenced by filter_frame().

batch_assign()

static int batch_assign ( LatticePalContext * s, const AVFrame * in )

static

Rediffuse the whole frame against the current live colors and reassign every pixel, recounting how often each live color is actually used.

Cells resolving to a dead or unused state are cached as -(list index+1); stale caches from earlier rounds heal themselves through the alive check.

Definition at line 816 of file vf_latticepal.c.

Referenced by reduce_batched().

reduce_batched()

static int reduce_batched ( LatticePalContext * s, const AVFrame * in )

static

Batched reduction: instead of dropping all excess colors against the first pass statistics, drop half of the excess, rediffuse the frame against the survivors and recount from the actual assignments, then repeat.

Colors whose pixels the rediffusion absorbed elsewhere become free to drop, while colors that dithering cannot reproduce (extremes of the used gamut) keep their pixels and with them a high removal impact, so they are protected in later rounds.

Definition at line 908 of file vf_latticepal.c.

Referenced by filter_frame().

filter_frame()

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

static

Definition at line 941 of file vf_latticepal.c.

config_input()

static int config_input ( AVFilterLink * inlink )

static

Definition at line 1197 of file vf_latticepal.c.

uninit()

static av_cold void uninit ( AVFilterContext * ctx )

static

Definition at line 1359 of file vf_latticepal.c.

Variable Documentation

latticepal_options

const AVOption latticepal_options[]

static

Initial value:

= {
    { "density", "set the number of lattice steps spanning one color axis", OFFSET(density), AV_OPT_TYPE_INT, {.i64=20}, 1, MAX_DENSITY, FLAGS },
    { "max_colors", "set the maximum number of palette entries to use", OFFSET(max_colors), AV_OPT_TYPE_INT, {.i64=256}, 2, 256, FLAGS },
    { "alpha", "quantize the alpha channel too, on a 4 dimensional lattice", OFFSET(alpha), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS },
    { "refine", "rediffuse the error of dropped colors against the final palette", OFFSET(refine), AV_OPT_TYPE_INT, {.i64=REFINE_NONE}, 0, NB_REFINE-1, FLAGS, .unit = "refine_mode" },
        { "none",     "no refinement",                                        0, AV_OPT_TYPE_CONST, {.i64=REFINE_NONE},     INT_MIN, INT_MAX, FLAGS, .unit = "refine_mode" },
        { "full",     "rediffuse the whole frame against the final palette",  0, AV_OPT_TYPE_CONST, {.i64=REFINE_FULL},     INT_MIN, INT_MAX, FLAGS, .unit = "refine_mode" },
        { "residual", "diffuse only the residual of the dropped colors",      0, AV_OPT_TYPE_CONST, {.i64=REFINE_RESIDUAL}, INT_MIN, INT_MAX, FLAGS, .unit = "refine_mode" },
        { "batched",  "interleave removal and rediffusion in geometric batches", 0, AV_OPT_TYPE_CONST, {.i64=REFINE_BATCHED}, INT_MIN, INT_MAX, FLAGS, .unit = "refine_mode" },
    { "dither", "select dithering mode", OFFSET(dither), AV_OPT_TYPE_INT, {.i64=DITHERING_FLOYD_STEINBERG}, 0, NB_DITHERING-1, FLAGS, .unit = "dithering_mode" },
        { "none",            "no dithering",                    0, AV_OPT_TYPE_CONST, {.i64=DITHERING_NONE},            INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
        { "bayer",           "ordered 8x8 bayer dithering",     0, AV_OPT_TYPE_CONST, {.i64=DITHERING_BAYER},           INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
        { "blue_noise",      "void-and-cluster blue noise dithering", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_BLUE_NOISE}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
        { "floyd_steinberg", "Floyd-Steinberg error diffusion", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_FLOYD_STEINBERG}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
    { NULL }
}

Definition at line 118 of file vf_latticepal.c.

dither_8x8_73

const uint8_t dither_8x8_73[8][8]

static

Initial value:

= {
    {  0, 55, 14, 68,  3, 58, 17, 72, },
    { 37, 18, 50, 32, 40, 22, 54, 35, },
    {  9, 64,  5, 59, 13, 67,  8, 63, },
    { 46, 27, 41, 23, 49, 31, 44, 26, },
    {  2, 57, 16, 71,  1, 56, 15, 70, },
    { 39, 21, 52, 34, 38, 19, 51, 33, },
    { 11, 66,  7, 62, 10, 65,  6, 60, },
    { 48, 30, 43, 25, 47, 29, 42, 24, },
}

Definition at line 160 of file vf_latticepal.c.

Referenced by config_input().

latticepal_inputs

const AVFilterPad latticepal_inputs[]

static

Initial value:

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

Definition at line 1375 of file vf_latticepal.c.

ff_vf_latticepal

const FFFilter ff_vf_latticepal

Initial value:

= {
    .p.name        = "latticepal",
    .p.description = NULL_IF_CONFIG_SMALL("Convert RGB to PAL8 using a per-frame FCC lattice palette."),
    .p.priv_class  = &latticepal_class,
    .priv_size     = sizeof(LatticePalContext),
    .uninit        = uninit,
    FILTER_INPUTS(latticepal_inputs),
    FILTER_OUTPUTS(ff_video_default_filterpad),
    FILTER_QUERY_FUNC2(query_formats),
}

Definition at line 1384 of file vf_latticepal.c.