From patchwork Tue Dec 27 23:18:11 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?b?Q2zDqW1lbnQgQsWTc2No?= X-Patchwork-Id: 39792 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6a20:bc95:b0:ad:ade2:bfd2 with SMTP id fx21csp3762607pzb; Tue, 27 Dec 2022 15:22:13 -0800 (PST) X-Google-Smtp-Source: AMrXdXtPs95ZMo6BIG/ioaim7FmL7INj4VndRrdWQGlhUdbwsW2GkUGJSwV3aAIm11iCArP8Q3U3 X-Received: by 2002:a17:906:bc47:b0:78d:f455:3110 with SMTP id s7-20020a170906bc4700b0078df4553110mr17472597ejv.56.1672183333641; Tue, 27 Dec 2022 15:22:13 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1672183333; cv=none; d=google.com; s=arc-20160816; b=b9QrXearOt1Fc8VUW+r+3s1lURoSYugeKq3H59lVp2KVRlhjJGaODs8treKxdY7VOY e8vIsZcizQEr+/tu0TnD9k4Pu+suP9qFK41LdXL65wjma0lju1WvvMWLl1QitrEUg6Gy IAYMheQWhPbL3sCC7/+qzUnQh6O+/sznsJCYpCGW6qH8MoCdWXBggJujA7o4WNkZaz1g 1f2h+4jEzL8zHv4le6JRwQ7a9VczTWHhaQJ4irE6kkDtjH/yu7d6vPhRvU6aWuwPpIuE 2PYxgZEQwrRNZJfqCIkZWCK1237uyWPGilMZSe06gPHduFdz5fZbgav83nWgXO96u0Ca 9SGQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:content-transfer-encoding:cc:reply-to :list-subscribe:list-help:list-post:list-archive:list-unsubscribe :list-id:precedence:subject:mime-version:references:in-reply-to :message-id:date:to:from:dkim-signature:delivered-to; bh=W/ptnjwGNqIk/cX4RNZ5e4nxSHALPVlFlGUqgLGzOj4=; b=R7I+e2R0/QPFbauch1JvLsiQmwTmE+txR6Ey1coLwVurPf2RMAzrul505b9doPW2rQ F36XCA+6hvAAny8eOakvbtVhL8lFnWHgLFlSrLcoxyheiYroRbAB8lztK3crFEKv6vQV crNTmfbEkblp95OVz0MxB1WjtLOJ8BgyFB8Pt75wG2gHUdzcJYeD5JBR3A2NutitMabn zy+pzkr6Jk+EfLDAItIB9lRoyYAmVvKjJFbJYb4H3Lm7YU5KoNE8NXi1xX7UXP7V+tTU 33+Xb1DvpLyKyXLKolRUoRzPy8TMBam8fzJjydtl8qYgxti9vn29d7zd8e2FenXM1GZr Q18g== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@pkh.me header.s=selector1 header.b=KGuW+AVV; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=pkh.me Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id o22-20020a170906975600b007c4f75345e1si13042415ejy.443.2022.12.27.15.22.13; Tue, 27 Dec 2022 15:22:13 -0800 (PST) Received-SPF: pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) client-ip=79.124.17.100; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@pkh.me header.s=selector1 header.b=KGuW+AVV; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=pkh.me Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id CD9EC68BCFA; Wed, 28 Dec 2022 01:18:54 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from ssq0.pkh.me (laubervilliers-656-1-228-164.w92-154.abo.wanadoo.fr [92.154.28.164]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 7818168BCAA for ; Wed, 28 Dec 2022 01:18:36 +0200 (EET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pkh.me; s=selector1; t=1672183100; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=XPkYZ/bpHbaZoEDxUkZIaXL9j6n7q+v/ZMxVF4OvPZM=; b=KGuW+AVVO+RxuCp7ZaCsCadi5ovahc9LLQaKf2tmpDYbXHG7xTXvaynJ5NITcEqh0Bpzox 7+QPJJp7EbpLYDnA0ZXRSvvWL6Mrzz6A06CltaZyEmodqwr5XjEUeMjj6jVxBCOYT7s+3U sbJUwaIR/+D81pKDuVbCbFrqxxE1wO0= Received: from localhost (ssq0.pkh.me [local]) by ssq0.pkh.me (OpenSMTPD) with ESMTPA id e62d72ec; Tue, 27 Dec 2022 23:18:20 +0000 (UTC) From: =?utf-8?b?Q2zDqW1lbnQgQsWTc2No?= To: ffmpeg-devel@ffmpeg.org Date: Wed, 28 Dec 2022 00:18:11 +0100 Message-Id: <20221227231814.2520181-30-u@pkh.me> X-Mailer: git-send-email 2.38.1 In-Reply-To: <20221227231814.2520181-1-u@pkh.me> References: <20221105152617.1809282-1-u@pkh.me> <20221227231814.2520181-1-u@pkh.me> MIME-Version: 1.0 Subject: [FFmpeg-devel] [PATCH v2 29/32] avfilter/paletteuse: remove alternative search methods X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Cc: =?utf-8?b?Q2zDqW1lbnQgQsWTc2No?= Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" X-TUID: zVTu87uycaoD This is a maintenance pain more than anything. It appears to make the code slightly faster as a side effect. --- libavfilter/vf_paletteuse.c | 220 +++++------------------------------- 1 file changed, 31 insertions(+), 189 deletions(-) diff --git a/libavfilter/vf_paletteuse.c b/libavfilter/vf_paletteuse.c index 0342002b15..690422a842 100644 --- a/libavfilter/vf_paletteuse.c +++ b/libavfilter/vf_paletteuse.c @@ -45,13 +45,6 @@ enum dithering_mode { NB_DITHERING }; -enum color_search_method { - COLOR_SEARCH_NNS_ITERATIVE, - COLOR_SEARCH_NNS_RECURSIVE, - COLOR_SEARCH_BRUTEFORCE, - NB_COLOR_SEARCHES -}; - enum diff_mode { DIFF_MODE_NONE, DIFF_MODE_RECTANGLE, @@ -107,10 +100,8 @@ typedef struct PaletteUseContext { /* debug options */ char *dot_filename; - int color_search_method; int calc_mean_err; uint64_t total_mean_err; - int debug_accuracy; } PaletteUseContext; #define OFFSET(x) offsetof(PaletteUseContext, x) @@ -130,12 +121,7 @@ static const AVOption paletteuse_options[] = { /* following are the debug options, not part of the official API */ { "debug_kdtree", "save Graphviz graph of the kdtree in specified file", OFFSET(dot_filename), AV_OPT_TYPE_STRING, {.str=NULL}, 0, 0, FLAGS }, - { "color_search", "set reverse colormap color search method", OFFSET(color_search_method), AV_OPT_TYPE_INT, {.i64=COLOR_SEARCH_NNS_RECURSIVE}, 0, NB_COLOR_SEARCHES-1, FLAGS, "search" }, - { "nns_iterative", "iterative search", 0, AV_OPT_TYPE_CONST, {.i64=COLOR_SEARCH_NNS_ITERATIVE}, INT_MIN, INT_MAX, FLAGS, "search" }, - { "nns_recursive", "recursive search", 0, AV_OPT_TYPE_CONST, {.i64=COLOR_SEARCH_NNS_RECURSIVE}, INT_MIN, INT_MAX, FLAGS, "search" }, - { "bruteforce", "brute-force into the palette", 0, AV_OPT_TYPE_CONST, {.i64=COLOR_SEARCH_BRUTEFORCE}, INT_MIN, INT_MAX, FLAGS, "search" }, { "mean_err", "compute and print mean error", OFFSET(calc_mean_err), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS }, - { "debug_accuracy", "test color search accuracy", OFFSET(debug_accuracy), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS }, { NULL } }; @@ -193,26 +179,6 @@ static struct color_info get_color_from_srgb(uint32_t srgb) return ret; } -static av_always_inline uint8_t colormap_nearest_bruteforce(const uint32_t *palette, const struct color_info *target, const int trans_thresh) -{ - int i, pal_id = -1, min_dist = INT_MAX; - - for (i = 0; i < AVPALETTE_COUNT; i++) { - const uint32_t c = palette[i]; - - if (c >> 24 >= trans_thresh) { // ignore transparent entry - const struct color_info pal_color = get_color_from_srgb(palette[i]); - const int d = diff(&pal_color, target, trans_thresh); - if (d < min_dist) { - pal_id = i; - min_dist = d; - } - } - } - return pal_id; -} - -/* Recursive form, simpler but a bit slower. Kept for reference. */ struct nearest_color { int node_pos; int dist_sqd; @@ -248,7 +214,7 @@ static void colormap_nearest_node(const struct color_node *map, } } -static av_always_inline uint8_t colormap_nearest_recursive(const struct color_node *node, const struct color_info *target, const int trans_thresh) +static av_always_inline uint8_t colormap_nearest(const struct color_node *node, const struct color_info *target, const int trans_thresh) { struct nearest_color res = {.dist_sqd = INT32_MAX, .node_pos = -1}; colormap_nearest_node(node, 0, target, trans_thresh, &res); @@ -260,88 +226,11 @@ struct stack_node { int dx2; }; -static av_always_inline uint8_t colormap_nearest_iterative(const struct color_node *root, const struct color_info *target, const int trans_thresh) -{ - int pos = 0, best_node_id = -1, best_dist = INT_MAX, cur_color_id = 0; - struct stack_node nodes[16]; - struct stack_node *node = &nodes[0]; - - for (;;) { - - const struct color_node *kd = &root[cur_color_id]; - const struct color_info *current = &kd->c; - const int current_to_target = diff(target, current, trans_thresh); - - /* Compare current color node to the target and update our best node if - * it's actually better. */ - if (current_to_target < best_dist) { - best_node_id = cur_color_id; - if (!current_to_target) - goto end; // exact match, we can return immediately - best_dist = current_to_target; - } - - /* Check if it's not a leaf */ - if (kd->left_id != -1 || kd->right_id != -1) { - const int dx = target->lab[kd->split] - current->lab[kd->split]; - int nearer_kd_id, further_kd_id; - - /* Define which side is the most interesting. */ - if (dx <= 0) nearer_kd_id = kd->left_id, further_kd_id = kd->right_id; - else nearer_kd_id = kd->right_id, further_kd_id = kd->left_id; - - if (nearer_kd_id != -1) { - if (further_kd_id != -1) { - /* Here, both paths are defined, so we push a state for - * when we are going back. */ - node->color_id = further_kd_id; - node->dx2 = dx*dx; - pos++; - node++; - } - /* We can now update current color with the most probable path - * (no need to create a state since there is nothing to save - * anymore). */ - cur_color_id = nearer_kd_id; - continue; - } else if (dx*dx < best_dist) { - /* The nearest path isn't available, so there is only one path - * possible and it's the least probable. We enter it only if the - * distance from the current point to the hyper rectangle is - * less than our best distance. */ - cur_color_id = further_kd_id; - continue; - } - } - - /* Unstack as much as we can, typically as long as the least probable - * branch aren't actually probable. */ - do { - if (--pos < 0) - goto end; - node--; - } while (node->dx2 >= best_dist); - - /* We got a node where the least probable branch might actually contain - * a relevant color. */ - cur_color_id = node->color_id; - } - -end: - return root[best_node_id].palette_id; -} - -#define COLORMAP_NEAREST(search, palette, root, target, trans_thresh) \ - search == COLOR_SEARCH_NNS_ITERATIVE ? colormap_nearest_iterative(root, target, trans_thresh) : \ - search == COLOR_SEARCH_NNS_RECURSIVE ? colormap_nearest_recursive(root, target, trans_thresh) : \ - colormap_nearest_bruteforce(palette, target, trans_thresh) - /** * Check if the requested color is in the cache already. If not, find it in the * color tree and cache it. */ -static av_always_inline int color_get(PaletteUseContext *s, uint32_t color, - const enum color_search_method search_method) +static av_always_inline int color_get(PaletteUseContext *s, uint32_t color) { int i; struct color_info clrinfo; @@ -366,20 +255,19 @@ static av_always_inline int color_get(PaletteUseContext *s, uint32_t color, return AVERROR(ENOMEM); e->color = color; clrinfo = get_color_from_srgb(color); - e->pal_entry = COLORMAP_NEAREST(search_method, s->palette, s->map, &clrinfo, s->trans_thresh); + e->pal_entry = colormap_nearest(s->map, &clrinfo, s->trans_thresh); return e->pal_entry; } static av_always_inline int get_dst_color_err(PaletteUseContext *s, - uint32_t c, int *er, int *eg, int *eb, - const enum color_search_method search_method) + uint32_t c, int *er, int *eg, int *eb) { const uint8_t r = c >> 16 & 0xff; const uint8_t g = c >> 8 & 0xff; const uint8_t b = c & 0xff; uint32_t dstc; - const int dstx = color_get(s, c, search_method); + const int dstx = color_get(s, c); if (dstx < 0) return dstx; dstc = s->palette[dstx]; @@ -395,8 +283,7 @@ static av_always_inline int get_dst_color_err(PaletteUseContext *s, 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, - const enum color_search_method search_method) + enum dithering_mode dither) { int x, y; const int src_linesize = in ->linesize[0] >> 2; @@ -421,7 +308,7 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram const uint8_t g = av_clip_uint8(g8 + d); const uint8_t b = av_clip_uint8(b8 + d); const uint32_t color_new = (unsigned)(a8) << 24 | r << 16 | g << 8 | b; - const int color = color_get(s, color_new, search_method); + const int color = color_get(s, color_new); if (color < 0) return color; @@ -429,7 +316,7 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram } else if (dither == DITHERING_HECKBERT) { const int right = x < w - 1, down = y < h - 1; - const int color = get_dst_color_err(s, src[x], &er, &eg, &eb, search_method); + const int color = get_dst_color_err(s, src[x], &er, &eg, &eb); if (color < 0) return color; @@ -441,7 +328,7 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram } else if (dither == DITHERING_FLOYD_STEINBERG) { const int right = x < w - 1, down = y < h - 1, left = x > x_start; - const int color = get_dst_color_err(s, src[x], &er, &eg, &eb, search_method); + const int color = get_dst_color_err(s, src[x], &er, &eg, &eb); if (color < 0) return color; @@ -455,7 +342,7 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram } else if (dither == DITHERING_SIERRA2) { const int right = x < w - 1, down = y < h - 1, left = x > x_start; const int right2 = x < w - 2, left2 = x > x_start + 1; - const int color = get_dst_color_err(s, src[x], &er, &eg, &eb, search_method); + const int color = get_dst_color_err(s, src[x], &er, &eg, &eb); if (color < 0) return color; @@ -474,7 +361,7 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram } else if (dither == DITHERING_SIERRA2_4A) { const int right = x < w - 1, down = y < h - 1, left = x > x_start; - const int color = get_dst_color_err(s, src[x], &er, &eg, &eb, search_method); + const int color = get_dst_color_err(s, src[x], &er, &eg, &eb); if (color < 0) return color; @@ -485,7 +372,7 @@ static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFram if ( down) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 1, 2); } else { - const int color = color_get(s, src[x], search_method); + const int color = color_get(s, src[x]); if (color < 0) return color; @@ -551,35 +438,6 @@ static int disp_tree(const struct color_node *node, const char *fname) return 0; } -static int debug_accuracy(const struct color_node *node, const uint32_t *palette, const int trans_thresh, - const enum color_search_method search_method) -{ - int r, g, b, ret = 0; - - for (r = 0; r < 256; r++) { - for (g = 0; g < 256; g++) { - for (b = 0; b < 256; b++) { - const struct color_info target = get_color_from_srgb(0xff000000 | r<<16 | g<<8 | b); - const int r1 = COLORMAP_NEAREST(search_method, palette, node, &target, trans_thresh); - const int r2 = colormap_nearest_bruteforce(palette, &target, trans_thresh); - if (r1 != r2) { - const struct color_info pal_c1 = get_color_from_srgb(0xff000000 | palette[r1]); - const struct color_info pal_c2 = get_color_from_srgb(0xff000000 | palette[r2]); - const int d1 = diff(&pal_c1, &target, trans_thresh); - const int d2 = diff(&pal_c2, &target, trans_thresh); - if (d1 != d2) { - av_log(NULL, AV_LOG_ERROR, - "/!\\ %02X%02X%02X: %d ! %d (%06"PRIX32" ! %06"PRIX32") / dist: %d ! %d\n", - r, g, b, r1, r2, pal_c1.srgb & 0xffffff, pal_c2.srgb & 0xffffff, d1, d2); - ret = 1; - } - } - } - } - } - return ret; -} - struct color { struct Lab value; uint8_t pal_id; @@ -746,11 +604,6 @@ static void load_colormap(PaletteUseContext *s) if (s->dot_filename) disp_tree(s->map, s->dot_filename); - - if (s->debug_accuracy) { - if (!debug_accuracy(s->map, s->palette, s->trans_thresh, s->color_search_method)) - av_log(NULL, AV_LOG_INFO, "Accuracy check passed\n"); - } } static void debug_mean_error(PaletteUseContext *s, const AVFrame *in1, @@ -1009,38 +862,27 @@ static int load_apply_palette(FFFrameSync *fs) return ff_filter_frame(ctx->outputs[0], out); } -#define DEFINE_SET_FRAME(color_search, name, value) \ +#define DEFINE_SET_FRAME(name, value) \ static int set_frame_##name(PaletteUseContext *s, AVFrame *out, AVFrame *in, \ int x_start, int y_start, int w, int h) \ { \ - return set_frame(s, out, in, x_start, y_start, w, h, value, color_search); \ -} - -#define DEFINE_SET_FRAME_COLOR_SEARCH(color_search, color_search_macro) \ - DEFINE_SET_FRAME(color_search_macro, color_search##_##none, DITHERING_NONE) \ - DEFINE_SET_FRAME(color_search_macro, color_search##_##bayer, DITHERING_BAYER) \ - DEFINE_SET_FRAME(color_search_macro, color_search##_##heckbert, DITHERING_HECKBERT) \ - DEFINE_SET_FRAME(color_search_macro, color_search##_##floyd_steinberg, DITHERING_FLOYD_STEINBERG) \ - DEFINE_SET_FRAME(color_search_macro, color_search##_##sierra2, DITHERING_SIERRA2) \ - DEFINE_SET_FRAME(color_search_macro, color_search##_##sierra2_4a, DITHERING_SIERRA2_4A) \ - -DEFINE_SET_FRAME_COLOR_SEARCH(nns_iterative, COLOR_SEARCH_NNS_ITERATIVE) -DEFINE_SET_FRAME_COLOR_SEARCH(nns_recursive, COLOR_SEARCH_NNS_RECURSIVE) -DEFINE_SET_FRAME_COLOR_SEARCH(bruteforce, COLOR_SEARCH_BRUTEFORCE) - -#define DITHERING_ENTRIES(color_search) { \ - set_frame_##color_search##_none, \ - set_frame_##color_search##_bayer, \ - set_frame_##color_search##_heckbert, \ - set_frame_##color_search##_floyd_steinberg, \ - set_frame_##color_search##_sierra2, \ - set_frame_##color_search##_sierra2_4a, \ -} - -static const set_frame_func set_frame_lut[NB_COLOR_SEARCHES][NB_DITHERING] = { - DITHERING_ENTRIES(nns_iterative), - DITHERING_ENTRIES(nns_recursive), - DITHERING_ENTRIES(bruteforce), + return set_frame(s, out, in, x_start, y_start, w, h, value); \ +} + +DEFINE_SET_FRAME(none, DITHERING_NONE) +DEFINE_SET_FRAME(bayer, DITHERING_BAYER) +DEFINE_SET_FRAME(heckbert, DITHERING_HECKBERT) +DEFINE_SET_FRAME(floyd_steinberg, DITHERING_FLOYD_STEINBERG) +DEFINE_SET_FRAME(sierra2, DITHERING_SIERRA2) +DEFINE_SET_FRAME(sierra2_4a, DITHERING_SIERRA2_4A) + +static const set_frame_func set_frame_lut[NB_DITHERING] = { + set_frame_none, + set_frame_bayer, + set_frame_heckbert, + set_frame_floyd_steinberg, + set_frame_sierra2, + set_frame_sierra2_4a, }; static int dither_value(int p) @@ -1060,7 +902,7 @@ static av_cold int init(AVFilterContext *ctx) if (!s->last_in || !s->last_out) return AVERROR(ENOMEM); - s->set_frame = set_frame_lut[s->color_search_method][s->dither]; + s->set_frame = set_frame_lut[s->dither]; if (s->dither == DITHERING_BAYER) { int i;