From patchwork Tue Dec 27 23:17:53 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?b?Q2zDqW1lbnQgQsWTc2No?= X-Patchwork-Id: 39768 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6a20:bc95:b0:ad:ade2:bfd2 with SMTP id fx21csp3761414pzb; Tue, 27 Dec 2022 15:19:44 -0800 (PST) X-Google-Smtp-Source: AMrXdXsyvFf9faoG2PSkWxY7tCSjn6V85zAkxnal4ua/elKL2K6b2F8zmRiUZJuCfFUivMJIK6GV X-Received: by 2002:a05:6402:3784:b0:46d:cead:4eab with SMTP id et4-20020a056402378400b0046dcead4eabmr20843482edb.6.1672183184054; Tue, 27 Dec 2022 15:19:44 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1672183184; cv=none; d=google.com; s=arc-20160816; b=rJa28a56IqJWMm7SplP6uad4XVvkckEdCl0ANtE8qBvRyZcGYM0T8oxxFHC6xY7rFI BkJOsLGHqPZOmZA3bmj0guRhgfrMWbsbCo59M40vCzblrLm5SUGdUP//ew6CPU0OLbIJ Nuv4me+e/FaWqXTj8n1I7zVoNv6FkVOdTG6TuxCnHh/M1khyxAsQXrm55SCWcuSZqiw6 BfOU0cO8pvqN905gDZyJ27FOs8CmAnjgGWANBP890BKJedBjVPgh6D6TrFvkxbyCHdxZ pB+GXJLkbojDlQ2aybxju2liC50RwZEFCiK6fkRwaryDFE4vX6jJ/1G4MvRYMWGdagQR EXeg== 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=APkXuceIschghsprzNmLI7y5/OhoQLYMcr6soI45q2g=; b=eYMnjJXuOZN+f6JergEDWrvQJZqYL2TANAYtp7vYtIxEjOj4gQQc6CSGHk4Vyl9QF7 0ilLCrfBMjx8AVGpivmHq01cHo5UB1hcxuTp8ym5Tr9tS25ZCpb3Wp9FGScFzR+SNljI eQEYyZ0ZCPXOVBuG7CTRGg5MWHb/c074LKmxvgqDPwIYAGLTLDd65RoOgG3rLGNT+yZb DaB1RnS4aipxGGwTMaXZ7GnFuyMGhuKhQxvI8gQksUT/umeyOtshGPkEx50BHx2npcqK K0W6V8Z9RQ9edmCS2AnpepeagkU5TWMmL2Ta0T1xnEIIafZXlqD1GqvGUAW+HGFTYql3 KVRQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@pkh.me header.s=selector1 header.b=gOkAtnwn; 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 r20-20020aa7c154000000b0048254d95382si9664870edp.342.2022.12.27.15.19.43; Tue, 27 Dec 2022 15:19:44 -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=gOkAtnwn; 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 A360668BC75; Wed, 28 Dec 2022 01:18:37 +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 E17CF68BCAB for ; Wed, 28 Dec 2022 01:18:32 +0200 (EET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pkh.me; s=selector1; t=1672183098; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=cR82zIx+RektCK5Q2UTsk6Dg2g2Cnqw8Siad9rvETFY=; b=gOkAtnwnw1VO0UmTSkA070HgkfWJvxi+yY2wJ5WsLT3pjEvAMkb8tlIBBcpLMltYmm7yq4 lejerUCFmKy8rDy81BujGl/Y00pNLGpkpEyr616rLSkYqzmktZkFVHaGEUr0sLDIU1ymC/ 3ttPPVPJD60lkfZTccuvcGaaWCE4D/c= Received: from localhost (ssq0.pkh.me [local]) by ssq0.pkh.me (OpenSMTPD) with ESMTPA id 9a45f9ba; Tue, 27 Dec 2022 23:18:18 +0000 (UTC) From: =?utf-8?b?Q2zDqW1lbnQgQsWTc2No?= To: ffmpeg-devel@ffmpeg.org Date: Wed, 28 Dec 2022 00:17:53 +0100 Message-Id: <20221227231814.2520181-12-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 11/32] avfilter/palettegen: define the best axis to cut using the squared error 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: X0Mf219C1oM/ This is following the results from personal research¹. ¹: https://github.com/ubitux/research/tree/main/color-quantization#results --- libavfilter/vf_palettegen.c | 42 ++++++++++++++++++------------ tests/ref/fate/filter-palettegen-1 | 2 +- tests/ref/fate/filter-palettegen-2 | 2 +- 3 files changed, 27 insertions(+), 19 deletions(-) diff --git a/libavfilter/vf_palettegen.c b/libavfilter/vf_palettegen.c index a047c75599..ed1448755c 100644 --- a/libavfilter/vf_palettegen.c +++ b/libavfilter/vf_palettegen.c @@ -147,31 +147,39 @@ static av_always_inline int diff(const uint32_t a, const uint32_t b) static void compute_box_stats(PaletteGenContext *s, struct range_box *box) { - int rr, gr, br; + int avg[3]; + int64_t er2[3] = {0}; - /* 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}; + /* Compute average color */ + uint64_t sr = 0, sg = 0, sb = 0; box->weight = 0; for (int i = box->start; i < box->start + box->len; i++) { const struct color_ref *ref = s->refs[i]; - const uint32_t rgb = ref->color; - const uint8_t r = rgb >> 16 & 0xff, g = rgb >> 8 & 0xff, b = rgb & 0xff; - 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]); + sr += (ref->color >> 16 & 0xff) * ref->count; + sg += (ref->color >> 8 & 0xff) * ref->count; + sb += (ref->color & 0xff) * ref->count; box->weight += ref->count; } + avg[0] = sr / box->weight; + avg[1] = sg / box->weight; + avg[2] = sb / box->weight; - /* define the axis to sort by according to the widest range of colors */ - rr = max[0] - min[0]; - gr = max[1] - min[1]; - br = max[2] - min[2]; + /* Compute squared error of each color channel */ + for (int i = box->start; i < box->start + box->len; i++) { + const struct color_ref *ref = s->refs[i]; + const int64_t dr = (int)(ref->color >> 16 & 0xff) - avg[0]; + const int64_t dg = (int)(ref->color >> 8 & 0xff) - avg[1]; + const int64_t db = (int)(ref->color & 0xff) - avg[2]; + er2[0] += dr * dr * ref->count; + er2[1] += dg * dg * ref->count; + er2[2] += db * db * ref->count; + } + + /* Define the best axis candidate for cutting the box */ box->major_axis = 1; // pick green by default (the color the eye is the most sensitive to) - if (br >= rr && br >= gr) box->major_axis = 2; - if (rr >= gr && rr >= br) box->major_axis = 0; - if (gr >= rr && gr >= br) box->major_axis = 1; // prefer green again + if (er2[2] >= er2[0] && er2[2] >= er2[1]) box->major_axis = 2; + if (er2[0] >= er2[1] && er2[0] >= er2[2]) box->major_axis = 0; + if (er2[1] >= er2[0] && er2[1] >= er2[2]) box->major_axis = 1; // prefer green again } /** diff --git a/tests/ref/fate/filter-palettegen-1 b/tests/ref/fate/filter-palettegen-1 index bebfd24e19..278d831846 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, 0x3395ef5a +0, 0, 0, 1, 1024, 0x394ee723 diff --git a/tests/ref/fate/filter-palettegen-2 b/tests/ref/fate/filter-palettegen-2 index 9abec0fe8e..e9bc635c81 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, 0x23e072c8 +0, 0, 0, 1, 1024, 0xc54d773d