[FFmpeg-devel] [PATCH 4/6] avfilter: add palettegen filter
Clément Bœsch
u at pkh.me
Sun Jan 25 19:55:21 CET 2015
---
doc/filters.texi | 24 +++
libavfilter/Makefile | 1 +
libavfilter/allfilters.c | 1 +
libavfilter/vf_palettegen.c | 382 ++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 408 insertions(+)
create mode 100644 libavfilter/vf_palettegen.c
diff --git a/doc/filters.texi b/doc/filters.texi
index 64384d0..5e27ae5 100644
--- a/doc/filters.texi
+++ b/doc/filters.texi
@@ -6884,6 +6884,30 @@ pad="2*iw:2*ih:ow-iw:oh-ih"
@end example
@end itemize
+ at section palettegen
+
+Generate one palette for a whole video stream.
+
+It accepts the following option:
+
+ at table @option
+ at item reserve_transparent
+Create a palette of 255 colors maximum and reserve the last one for
+transparency. Reserving the transparency color is useful for GIF optimization.
+If not set, the maximum of colors in the palette will be 256.
+Set by default.
+ at end table
+
+ at subsection Examples
+
+ at itemize
+ at item
+Generate a representative palette of a given video using @command{ffmpeg}:
+ at example
+ffmpeg -i input.mkv -vf palettegen palette.png
+ at end example
+ at end itemize
+
@section perspective
Correct perspective of video not recorded perpendicular to the screen.
diff --git a/libavfilter/Makefile b/libavfilter/Makefile
index f7285b3..6ea7e9c 100644
--- a/libavfilter/Makefile
+++ b/libavfilter/Makefile
@@ -159,6 +159,7 @@ OBJS-$(CONFIG_OPENCL) += deshake_opencl.o unsharp_opencl.
OBJS-$(CONFIG_OVERLAY_FILTER) += vf_overlay.o dualinput.o framesync.o
OBJS-$(CONFIG_OWDENOISE_FILTER) += vf_owdenoise.o
OBJS-$(CONFIG_PAD_FILTER) += vf_pad.o
+OBJS-$(CONFIG_PALETTEGEN_FILTER) += vf_palettegen.o
OBJS-$(CONFIG_PERMS_FILTER) += f_perms.o
OBJS-$(CONFIG_PERSPECTIVE_FILTER) += vf_perspective.o
OBJS-$(CONFIG_PHASE_FILTER) += vf_phase.o
diff --git a/libavfilter/allfilters.c b/libavfilter/allfilters.c
index 028e3ea..a3443a0 100644
--- a/libavfilter/allfilters.c
+++ b/libavfilter/allfilters.c
@@ -174,6 +174,7 @@ void avfilter_register_all(void)
REGISTER_FILTER(OVERLAY, overlay, vf);
REGISTER_FILTER(OWDENOISE, owdenoise, vf);
REGISTER_FILTER(PAD, pad, vf);
+ REGISTER_FILTER(PALETTEGEN, palettegen, vf);
REGISTER_FILTER(PERMS, perms, vf);
REGISTER_FILTER(PERSPECTIVE, perspective, vf);
REGISTER_FILTER(PHASE, phase, vf);
diff --git a/libavfilter/vf_palettegen.c b/libavfilter/vf_palettegen.c
new file mode 100644
index 0000000..eaa4938
--- /dev/null
+++ b/libavfilter/vf_palettegen.c
@@ -0,0 +1,382 @@
+/*
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/**
+ * @file
+ * Generate one palette for a whole video stream.
+ */
+
+#include "libavutil/avassert.h"
+#include "libavutil/opt.h"
+#include "avfilter.h"
+#include "internal.h"
+
+/* Reference a color and how much it's used */
+struct color_ref {
+ uint16_t rgb555;
+ int count; // copied from the histogram value
+};
+
+/* Store a range of colors */
+struct range_box {
+ int start; // index in PaletteGenContext->refs
+ int len; // number of referenced colors
+ int sorted_by; // whether range of colors is sorted by red (0), green (1) or blue (2)
+};
+
+typedef struct {
+ const AVClass *class;
+ int reserve_transparent;
+ uint32_t cdist[1<<15]; // color distribution
+ struct color_ref refs[1<<15]; // references of all the colors used in the stream
+ int nb_refs;
+ struct range_box boxes[256]; // define the segmentation of the colorspace
+ int nb_boxes;
+} PaletteGenContext;
+
+#define OFFSET(x) offsetof(PaletteGenContext, x)
+#define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
+static const AVOption palettegen_options[] = {
+ { "reserve_transparent", "reserve a palette entry for transparency", OFFSET(reserve_transparent), AV_OPT_TYPE_INT, {.i64=1}, 0, 1, FLAGS },
+ { NULL }
+};
+
+AVFILTER_DEFINE_CLASS(palettegen);
+
+static int query_formats(AVFilterContext *ctx)
+{
+ static const enum AVPixelFormat in_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
+ static const enum AVPixelFormat out_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
+ AVFilterFormats *in = ff_make_format_list(in_fmts);
+ AVFilterFormats *out = ff_make_format_list(out_fmts);
+ if (!in || !out)
+ return AVERROR(ENOMEM);
+ ff_formats_ref(in, &ctx->inputs[0]->out_formats);
+ ff_formats_ref(out, &ctx->outputs[0]->in_formats);
+ return 0;
+}
+
+typedef int (*cmp_func)(const void *, const void *);
+
+#define DECLARE_CMP_FUNC(name, pos) \
+static int cmp_##name(const void *pa, const void *pb) \
+{ \
+ const struct color_ref *a = pa; \
+ const struct color_ref *b = pb; \
+ return (a->rgb555 >> (5 * (2 - (pos))) & 0x1f) \
+ - (b->rgb555 >> (5 * (2 - (pos))) & 0x1f); \
+}
+
+DECLARE_CMP_FUNC(r, 0)
+DECLARE_CMP_FUNC(g, 1)
+DECLARE_CMP_FUNC(b, 2)
+
+static const cmp_func cmp_funcs[] = {cmp_r, cmp_g, cmp_b};
+
+/**
+ * Simple color comparison for sorting the final palette
+ */
+static int cmp_color(const void *a, const void *b)
+{
+ const uint32_t c1 = *(const uint32_t *)a;
+ const uint32_t c2 = *(const uint32_t *)b;
+ return c2 - c1;
+}
+
+/**
+ * Find the next box to split. Current heuristic is to try to split the box
+ * with the most different indexed colors.
+ * TODO: we might want to involve the weight of the color to find a better box
+ * to split.
+ */
+static int get_next_box_id_to_split(PaletteGenContext *s)
+{
+ int i, max_len = -1, box_id;
+
+ if (s->nb_boxes == FF_ARRAY_ELEMS(s->boxes) - s->reserve_transparent)
+ return -1;
+
+ for (i = 0; i < s->nb_boxes; i++) {
+ if (s->boxes[i].len > max_len) {
+ max_len = s->boxes[i].len;
+ box_id = i;
+ }
+ }
+ return max_len > 1 ? box_id : -1;
+}
+
+/**
+ * Get the 32-bit average color for the range of RGB555 colors enclosed in the
+ * specified box.
+ */
+static uint32_t get_avg_color(const struct color_ref *refs,
+ const struct range_box *box)
+{
+ const int n = box->len;
+ int i, r = 0, g = 0, b = 0;
+ const struct color_ref *ref = &refs[box->start];
+
+ for (i = 0; i < n; i++) {
+ r += ref[i].rgb555 >> 10;
+ g += ref[i].rgb555 >> 5 & 0x1f;
+ b += ref[i].rgb555 & 0x1f;
+ }
+
+ /* Upsampling from 5 to 8 bits: x*(255/31) is simplified to x*8423/1024, or
+ * with rounded bitshift: (x*8423 + (1<<9))>>10. The averaging by n is then
+ * integrated in that expression. */
+ r = (r * 8423 / n + (1<<9)) >> 10;
+ g = (g * 8423 / n + (1<<9)) >> 10;
+ b = (b * 8423 / n + (1<<9)) >> 10;
+
+ return 0xffU<<24 | r<<16 | g<<8 | b;
+}
+
+/**
+ * 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.
+ */
+static void split_box(PaletteGenContext *s, struct range_box *box, int n)
+{
+ struct range_box *new_box = &s->boxes[s->nb_boxes++];
+ new_box->start = n + 1;
+ new_box->len = box->start + box->len - new_box->start;
+ new_box->sorted_by = box->sorted_by;
+ box->len -= new_box->len;
+
+ av_assert0(box->len >= 1);
+ av_assert0(new_box->len >= 1);
+}
+
+/**
+ * Write the palette into out frame.
+ */
+static void write_palette(const PaletteGenContext *s, AVFrame *out)
+{
+ int x, y, box_id = 0;
+ uint32_t *pal = (uint32_t *)out->data[0];
+ const int pal_linesize = out->linesize[0] >> 2;
+
+ for (y = 0; y < out->height; y++) {
+ for (x = 0; x < out->width; x++)
+ pal[x] = box_id < s->nb_boxes ? s->cdist[box_id++] : 0xff000000; // pad with black
+ pal += pal_linesize;
+ }
+
+ if (s->reserve_transparent) {
+ av_assert0(s->nb_boxes < 256);
+ pal[out->width - pal_linesize - 1] = 0x0000ff00; // add a green transparent color
+ }
+}
+
+/**
+ * Main function implementing the Median Cut Algorithm defined by Paul Heckbert
+ * in Color Image Quantization for Frame Buffer Display (1982)
+ */
+static AVFrame *get_palette_frame(AVFilterContext *ctx)
+{
+ PaletteGenContext *s = ctx->priv;
+ AVFilterLink *outlink = ctx->outputs[0];
+ int i, color, box_id = 0;
+ int longest = 0;
+ uint32_t *cdist = s->cdist;
+ struct range_box *box;
+
+ /* create the palette frame */
+ AVFrame *out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
+ if (!out)
+ return NULL;
+ out->pts = 0;
+
+ /* reference only the used colors */
+ for (color = 0; color < FF_ARRAY_ELEMS(s->cdist); color++) {
+ if (cdist[color]) {
+ struct color_ref *ref = &s->refs[s->nb_refs];
+ ref->rgb555 = color;
+ ref->count = cdist[color];
+ s->nb_refs++;
+ }
+ }
+
+ /* set first box for 0..nb_refs */
+ box = &s->boxes[box_id];
+ box->len = s->nb_refs;
+ box->sorted_by = 0; // 0 .. 0x7fff makes red most significant color
+ s->nb_boxes = 1;
+
+ while (box && box->len > 1) {
+ int box_weight = 0, median, rr, gr, br;
+
+ /* compute the box weight (sum all the weights of the colors in the
+ * range) and its boundings */
+ uint8_t min[3] = {0xff, 0xff, 0xff};
+ uint8_t max[3] = {0x00, 0x00, 0x00};
+ for (i = box->start; i < box->start + box->len; i++) {
+ const uint16_t rgb = s->refs[i].rgb555;
+ const uint8_t r = rgb >> 10, g = rgb >> 5 & 0x1f, b = rgb & 0x1f;
+ min[0] = FFMIN(r, min[0]), max[0] = FFMAX(r, max[0]);
+ min[1] = FFMIN(g, min[1]), max[1] = FFMAX(g, max[1]);
+ min[2] = FFMIN(b, min[2]), max[2] = FFMAX(b, max[2]);
+ box_weight += s->refs[i].count;
+ }
+
+ /* define the axis to sort by according to the widest range of color */
+ rr = max[0] - min[0];
+ gr = max[1] - min[1];
+ br = max[2] - min[2];
+ longest = 1; // pick green by default (color the eye is the most sensitive to)
+ if (rr >= gr && rr >= br) longest = 0;
+ if (br >= rr && br >= gr) longest = 2;
+ if (gr >= rr && gr >= br) longest = 1; // prefer green again
+
+ av_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6d ranges:[%2d %2d %2d] sort by %c (already sorted:%c) ",
+ box_id, box->start, box->start + box->len - 1, box->len, box_weight,
+ rr, gr, br, "rgb"[longest], box->sorted_by == longest ? 'y':'n');
+
+ /* sort the range by its longest axis if it's not already sorted */
+ if (box->sorted_by != longest) {
+ qsort(&s->refs[box->start], box->len, sizeof(*s->refs), cmp_funcs[longest]);
+ box->sorted_by = longest;
+ }
+
+ /* locate the median where to split. XXX: paper mention a split
+ * according to the variance which might be more efficient */
+ median = box_weight >> 1;
+ box_weight = 0;
+ /* if you have 2 boxes, the maximum is actually #0: you must have at
+ * least 1 color on each side of the split, hence the -2 */
+ for (i = box->start; i < box->start + box->len - 2; i++) {
+ box_weight += s->refs[i].count;
+ if (box_weight > median)
+ break;
+ }
+
+ av_dlog(ctx, "split @ i=%-6d with w=%-6d (target=%6d)\n", i, box_weight, median);
+ split_box(s, box, i);
+
+ box_id = get_next_box_id_to_split(s);
+ box = box_id >= 0 ? &s->boxes[box_id] : NULL;
+ }
+
+ av_log(ctx, AV_LOG_DEBUG, "%d%s boxes generated out of %d/%d colors\n",
+ s->nb_boxes, s->reserve_transparent ? "(+1)" : "",
+ s->nb_refs, (int)FF_ARRAY_ELEMS(s->cdist));
+
+ for (box_id = 0; box_id < s->nb_boxes; box_id++)
+ s->cdist[box_id] = get_avg_color(s->refs, &s->boxes[box_id]);
+ qsort(s->cdist, s->nb_boxes, sizeof(*s->cdist), cmp_color);
+
+ write_palette(s, out);
+
+ return out;
+}
+
+/**
+ * For each frame, make an histogram of all the colors, with a 5-bit per
+ * component resolution.
+ *
+ * XXX: request RGB555 in query_formats() instead of downsampling here?
+ * XXX: maybe use a hash table for the histogram to store them with full
+ * resolution?
+ */
+static void update_histograms(uint32_t *hist, const AVFrame *in)
+{
+ int x, y;
+
+ for (y = 0; y < in->height; y++) {
+ const uint32_t *p = (const uint32_t *)(in->data[0] + y*in->linesize[0]);
+
+ for (x = 0; x < in->width; x++) {
+ const uint8_t r = p[x] >> (16+3) & 0x1f;
+ const uint8_t g = p[x] >> ( 8+3) & 0x1f;
+ const uint8_t b = p[x] >> ( 3) & 0x1f;
+ hist[r<<10 | g<<5 | b]++;
+ }
+ }
+}
+
+/**
+ * Update the histogram for each passing frame. No frame will be pushed here.
+ */
+static int filter_frame(AVFilterLink *inlink, AVFrame *in)
+{
+ AVFilterContext *ctx = inlink->dst;
+ PaletteGenContext *s = ctx->priv;
+ update_histograms(s->cdist, in);
+ av_frame_free(&in);
+ return 0;
+}
+
+/**
+ * Returns only one frame at the end containing the full palette.
+ */
+static int request_frame(AVFilterLink *outlink)
+{
+ AVFilterContext *ctx = outlink->src;
+ AVFilterLink *inlink = ctx->inputs[0];
+ int r;
+
+ r = ff_request_frame(inlink);
+ if (r == AVERROR_EOF) {
+ r = ff_filter_frame(outlink, get_palette_frame(ctx));
+ if (r < 0)
+ return r;
+ return AVERROR_EOF;
+ }
+ return r;
+}
+
+/**
+ * The output is one simple 16x16 squared-pixels palette.
+ */
+static int config_output(AVFilterLink *outlink)
+{
+ outlink->w = outlink->h = 16;
+ outlink->sample_aspect_ratio = av_make_q(1, 1);
+ outlink->flags |= FF_LINK_FLAG_REQUEST_LOOP;
+ return 0;
+}
+
+static const AVFilterPad palettegen_inputs[] = {
+ {
+ .name = "default",
+ .type = AVMEDIA_TYPE_VIDEO,
+ .filter_frame = filter_frame,
+ },
+ { NULL }
+};
+
+static const AVFilterPad palettegen_outputs[] = {
+ {
+ .name = "default",
+ .type = AVMEDIA_TYPE_VIDEO,
+ .config_props = config_output,
+ .request_frame = request_frame,
+ },
+ { NULL }
+};
+
+AVFilter ff_vf_palettegen = {
+ .name = "palettegen",
+ .description = NULL_IF_CONFIG_SMALL("Find the optimal palette for a given stream."),
+ .priv_size = sizeof(PaletteGenContext),
+ .query_formats = query_formats,
+ .inputs = palettegen_inputs,
+ .outputs = palettegen_outputs,
+ .priv_class = &palettegen_class,
+};
--
2.2.2
More information about the ffmpeg-devel
mailing list