From patchwork Sat Nov 5 15:26:15 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: 39176 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6a21:999a:b0:a4:2148:650a with SMTP id ve26csp1085996pzb; Sat, 5 Nov 2022 08:28:33 -0700 (PDT) X-Google-Smtp-Source: AMsMyM6EngKjriBl+Wo9wlSgxbbjj4CAmMlqsy9gfZlTYMS3KQu/T+ExQtLBn45QXE8UtFCyEjR4 X-Received: by 2002:a17:907:a067:b0:7a7:dc5e:eb2d with SMTP id ia7-20020a170907a06700b007a7dc5eeb2dmr40561074ejc.121.1667662113104; Sat, 05 Nov 2022 08:28:33 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1667662113; cv=none; d=google.com; s=arc-20160816; b=imeFZLh2iMGmHz7ryFCxOnBCJI/TdFjYOszlJmcI29BLOV5nAZbNkwy4tY7iUyI02/ ob7xizgMW3FcXtD6XIM89BMxzgrwZQZRV9YC8RbzM5MFLzm3Gu4zkQgU7vukhP6Ohso4 t5Bg7XolgFGiqddCZTnGlJ92Tbda3hcCO6592bDS9SmKQ+aoPBP31QE+EzRFFE6yOxbw Z0j4/pov4DeQDBmuehOlHNVMEgWH50g21+5Nljk7Cwa6mqQ1iueF+yWXyzEwRU0HaAgA xuQ077s2dP3chMB1O1r3u6h0R0niqGk+PqPQHOouJ07BOmBr9j36ta/RNj8HCANffXnd vnNQ== 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=1OGgb8mThABwEImI6g3/dzoChvohydhgNohxRVrvaU8=; b=dcnzsVxKdH1MUqc9j2OjzzWeuiWp0d38DPaSI8iY4N/jHZDHbxD/xu8qUFv8VYUlfP Q+DSh/6JvY6WofNBXETmg1TjdeGq+hNEv88pEOM20ZoMpTUk1BhtxH7amhUcOVb/UOkb q73GLwniAflb4M2FcDOdr63AObPmywi2yHY6Hh+x0itSKF1TZuw4lgTYZxRX2wCUCWXO XnYzacSeVzGZ8tuNSDQ4hk+o0TUypHHYPgfvU7akUh+p55K1VaI+HI58SQFsWYcmqtUE qCl/N7YhIq9mjR0+TnnmW7XpCA98zx4g2wuBRkWIcPBG2Osh3gDwoiXHogbYoNNTVODr apmw== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@pkh.me header.s=selector1 header.b=RgzT+JT2; 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 dm20-20020a170907949400b00782ff2649a7si2811554ejc.346.2022.11.05.08.28.32; Sat, 05 Nov 2022 08:28:33 -0700 (PDT) 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=RgzT+JT2; 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 77DA668B7F5; Sat, 5 Nov 2022 17:26:48 +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 79D4D68B259 for ; Sat, 5 Nov 2022 17:26:41 +0200 (EET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pkh.me; s=selector1; t=1667661983; 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=LnKLbzk+vBnDYFl2ImkRKFHFAFJ5wkfWkEZmq9hHnQk=; b=RgzT+JT2NeRtNlGOM8DBfj/cprt+MlzkRzrnVt8JP3/wsSjgiqnBmoxmtgElPL2F1uYW4j a+nbHV52wkoTxcW3N1K3Qdks5eVSH86jH2z7wk5+jJrbC6wu4WpcdeFsZYOHmraL2MeJ8M 0GRD0G/GgydVct++5h2/K9Vv6qtwe9Q= Received: from localhost (ssq0.pkh.me [local]) by ssq0.pkh.me (OpenSMTPD) with ESMTPA id 279a3559; Sat, 5 Nov 2022 15:26:23 +0000 (UTC) From: =?utf-8?b?Q2zDqW1lbnQgQsWTc2No?= To: ffmpeg-devel@ffmpeg.org Date: Sat, 5 Nov 2022 16:26:15 +0100 Message-Id: <20221105152617.1809282-14-u@pkh.me> X-Mailer: git-send-email 2.35.1 In-Reply-To: <20221105152617.1809282-1-u@pkh.me> References: <20221105152617.1809282-1-u@pkh.me> MIME-Version: 1.0 Subject: [FFmpeg-devel] [PATCH 13/15] avfilter/palettegen: use variance per-axis instead of the range 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: 8YyHYN92RRZI The split decision is now based on the per-axis variance instead of how wide they are. --- libavfilter/vf_palettegen.c | 61 ++++++++++++++++-------------- tests/ref/fate/filter-palettegen-1 | 2 +- tests/ref/fate/filter-palettegen-2 | 2 +- 3 files changed, 35 insertions(+), 30 deletions(-) diff --git a/libavfilter/vf_palettegen.c b/libavfilter/vf_palettegen.c index 4c2bcba7f7..2976012512 100644 --- a/libavfilter/vf_palettegen.c +++ b/libavfilter/vf_palettegen.c @@ -45,6 +45,7 @@ struct color_ref { struct range_box { uint32_t color; // average color double variance; // overall variance of the box (how much the colors are spread) + double axis_variance[3]; // axis specific variance 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) @@ -136,24 +137,29 @@ static int cmp_color(const void *a, const void *b) return FFDIFFSIGN(box1->color , box2->color); } -static av_always_inline float diff(const uint32_t a, const uint32_t b) -{ - const struct Lab lab0 = ff_srgb_u8_to_oklab(a); - const struct Lab lab1 = ff_srgb_u8_to_oklab(b); - const float dL = lab0.L - lab1.L; - const float da = lab0.a - lab1.a; - const float db = lab0.b - lab1.b; - return dL*dL + da*da + db*db; -} - static void compute_box_variance(PaletteGenContext *s, struct range_box *box) { double variance = 0.0; for (int i = 0; i < box->len; i++) { const struct color_ref *ref = s->refs[box->start + i]; - variance += diff(ref->color, box->color) * ref->count; + const struct Lab lab0 = ff_srgb_u8_to_oklab(ref->color); + const struct Lab lab1 = ff_srgb_u8_to_oklab(box->color); + const float dL = lab0.L - lab1.L; + const float da = lab0.a - lab1.a; + const float db = lab0.b - lab1.b; + + variance += (dL*dL + da*da + db*db) * ref->count; + + /* + * No need to normalize the per-axis variances since they are compared + * only locally within the box and thus share the same weight. + */ + box->axis_variance[0] += dL*dL * ref->count; + box->axis_variance[1] += da*da * ref->count; + box->axis_variance[2] += db*db * ref->count; } + /* * The variance is computed as a Mean Squared Error of the distance of the * current color to the box color average, with an important difference: @@ -198,6 +204,7 @@ static int get_next_box_id_to_split(PaletteGenContext *s) } } else { box->variance = -1.0; + memset(box->axis_variance, 0, sizeof(box->axis_variance)); } } return best_box_id; @@ -249,6 +256,8 @@ static void split_box(PaletteGenContext *s, struct range_box *box, int n) new_box->color = get_avg_color(s->refs, new_box); box->variance = -1.0; new_box->variance = -1.0; + memset(box->axis_variance, 0, sizeof(box->axis_variance)); + memset(new_box->axis_variance, 0, sizeof(new_box->axis_variance)); } /** @@ -346,38 +355,34 @@ static AVFrame *get_palette_frame(AVFilterContext *ctx) box->sorted_by = -1; box->color = get_avg_color(s->refs, box); box->variance = -1.0; + memset(box->axis_variance, 0, sizeof(box->axis_variance)); + compute_box_variance(s, box); s->nb_boxes = 1; while (box && box->len > 1) { int i, longest; - double Lr, ar, br; + double Lv, av, bv; uint64_t median, box_weight = 0; /* compute the box weight (sum all the weights of the colors in the - * range) and its boundings */ - float min[3] = {FLT_MAX, FLT_MAX, FLT_MAX}; - float max[3] = {-FLT_MAX, -FLT_MAX, -FLT_MAX}; + * range) */ for (i = box->start; i < box->start + box->len; i++) { const struct color_ref *ref = s->refs[i]; - const struct Lab lab = ref->lab; - min[0] = FFMIN(lab.L, min[0]), max[0] = FFMAX(lab.L, max[0]); - min[1] = FFMIN(lab.a, min[1]), max[1] = FFMAX(lab.a, max[1]); - min[2] = FFMIN(lab.b, min[2]), max[2] = FFMAX(lab.b, max[2]); box_weight += ref->count; } - /* define the axis to sort by according to the widest range of colors */ - Lr = max[0] - min[0]; - ar = max[1] - min[1]; - br = max[2] - min[2]; + /* pick the axis with the biggest variance */ + Lv = box->axis_variance[0]; + av = box->axis_variance[1]; + bv = box->axis_variance[2]; longest = 0; - if (br >= Lr && br >= ar) longest = 2; - if (ar >= Lr && ar >= br) longest = 1; - if (Lr >= ar && Lr >= br) longest = 0; + if (bv >= Lv && bv >= av) longest = 2; + if (av >= Lv && av >= bv) longest = 1; + if (Lv >= av && Lv >= bv) longest = 0; - ff_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" ranges:[%.3f %.3f %.3f] sort by %c (already sorted:%c) ", + ff_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" var:[%.3f %.3f %.3f] sort by %c (already sorted:%c) ", box_id, box->start, box->start + box->len - 1, box->len, box_weight, - Lr, ar, br, "Lab"[longest], box->sorted_by == longest ? 'y':'n'); + Lv, av, bv, "Lab"[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) { diff --git a/tests/ref/fate/filter-palettegen-1 b/tests/ref/fate/filter-palettegen-1 index 7b7ce98b76..35730a659f 100644 --- a/tests/ref/fate/filter-palettegen-1 +++ b/tests/ref/fate/filter-palettegen-1 @@ -3,4 +3,4 @@ #codec_id 0: rawvideo #dimensions 0: 16x16 #sar 0: 1/1 -0, 0, 0, 1, 1024, 0xf1fb64c1 +0, 0, 0, 1, 1024, 0xd8fd2c22 diff --git a/tests/ref/fate/filter-palettegen-2 b/tests/ref/fate/filter-palettegen-2 index b856a79273..548902fed0 100644 --- a/tests/ref/fate/filter-palettegen-2 +++ b/tests/ref/fate/filter-palettegen-2 @@ -3,4 +3,4 @@ #codec_id 0: rawvideo #dimensions 0: 16x16 #sar 0: 1/1 -0, 0, 0, 1, 1024, 0xe84a671a +0, 0, 0, 1, 1024, 0xd1f29072