From patchwork Mon Sep 20 22:26:51 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paul B Mahol X-Patchwork-Id: 30388 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a6b:6506:0:0:0:0:0 with SMTP id z6csp1865047iob; Mon, 20 Sep 2021 15:27:21 -0700 (PDT) X-Google-Smtp-Source: ABdhPJxT+OqTJmE9n/bPdcYa9PSex560tRRipdB527KIf0UWIpwsnrdBeRvVYN624wxKxGZ03fpk X-Received: by 2002:a17:906:1901:: with SMTP id a1mr31450312eje.129.1632176840859; Mon, 20 Sep 2021 15:27:20 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1632176840; cv=none; d=google.com; s=arc-20160816; b=vuDELnJRR4SAlXZ3dT8T721sC/PlqaFjo/J3iU12pHpSM1a3+AZfvol2EfHnr7PV4O fAmwW29swadxvK956j9sE1Fgi/WoBlYPbzqf56Pd107Kf52+ATUou5h3MBw8bOSLwt1G MFd+Xk1vB+RkBLURPgd0JKZ9la+mjn5k3pAqIGelxw8+Sg971I6ySVJk7+HTropflYF3 RrRSGql74HKf6qkWPHsECv5JbfdeSuOUv10+ISly51QLnuoJYELhOFW/gIajEpqGWwPu w3goxE4X6jMk8gWPyNUmODyp7rZPN5lVvNzy/Hfj9sNwPhmiEzNR5cwHEpMbeLzD49Im 2q1w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:content-transfer-encoding:mime-version:reply-to :list-subscribe:list-help:list-post:list-archive:list-unsubscribe :list-id:precedence:subject:message-id:date:to:from:dkim-signature :delivered-to; bh=tldpyv6VRxvRkPeuU+7RXFd+WQeLENHn9cxYkBXURv8=; b=i62TUJcvdzfOVZMOHO3kRauStTWUna56/39d/cORsoZclIGvKy1+5BPcSuWJ54H106 YoyvTrUyzcPmW0PgLkwAaouqiFnMqYoFapeiS7den4er3W5zpZg90aRoWznF23WFMOJF urEzOWEYSLkGYkuB9Wk7+1AZlkvwIB7tJMJjJIgz5KIYWhk5ha2N4msH9ehb0UhrC37C Nj/PB/bNqOPe8Uj5Ed85B7/KMd1ThgMR7xrd0b0zhFrI3F7QW+Myo4eF3SqLE6Ww/mo8 TKpsHMfXjZatkpLYdmWqQSalf939xSp2CjA6HeNApDqj/niqhV1329Px3Y7amEYB8IsT T2ow== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@gmail.com header.s=20210112 header.b="Q8IL/sgY"; 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=QUARANTINE dis=NONE) header.from=gmail.com Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id p6si18177379edy.476.2021.09.20.15.27.20; Mon, 20 Sep 2021 15:27:20 -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=@gmail.com header.s=20210112 header.b="Q8IL/sgY"; 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=QUARANTINE dis=NONE) header.from=gmail.com Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id EC6E868AFBB; Tue, 21 Sep 2021 01:27:15 +0300 (EEST) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-ed1-f43.google.com (mail-ed1-f43.google.com [209.85.208.43]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id DACB768AE78 for ; Tue, 21 Sep 2021 01:27:08 +0300 (EEST) Received: by mail-ed1-f43.google.com with SMTP id eg28so44327088edb.1 for ; Mon, 20 Sep 2021 15:27:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:subject:date:message-id; bh=q/9iitTm0JJsEgPqP5fL2zLKFm6UfuweKpMJeratCZc=; b=Q8IL/sgYL8BCUutL2KaMDBDcI7rlHMYQvvj+cM9fraiGNosqYg0HgFGvZBXYVDP+Aw XweSQye92jHjs8V1NOx2EXTu1/5T9C0cxoxAju1yoomhke99UEEITbw4Kz16wJ63jZBT 0Lk2rVlwnepVzApb+Oj5xs2V59VsL32NwiwN0NTAJU2eaS+eNuXf4PEpbSs5OeeupNld glUCkWiljyi5mjt1O0wohYJ2xcHDoGEjeKZ/0c5Q9VykIHUmlIdJ+kwbpGikKtyOYW2C yspQa+L6RvU5Vl1b6LZO8Nz0WwxpUgyQyHVm8SdUS1JQF02ZyJJM5hiBZmSkNAUOobJE BfgQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id; bh=q/9iitTm0JJsEgPqP5fL2zLKFm6UfuweKpMJeratCZc=; b=GPNuGZxvD/CVlQzVRC/eMS/EFrkCgWls+B/Gy6r/DfFk+M2ZlSonIPhZ2a+hzcmJoh Hhc/epRNv7SKXTCqRcIpcO5dSrIvx6N/w1YI3C3owsn6Q3YfwvY1ziEm5X2cS6ImZSNc cAvu1pexq1tTqwS4AQ7p2vtp/yt6ekteVqkYMvGzwGtn4R8a4MvhO1od4/acCnFvw4Rx GOn61Xh8gr1XWAM1RgNxewbLsU6ju+awQTletg4a8RZl4GS62yh+VDcQ0xOt25uQQNCc l4/VKsBvAJx8easK0WmWmNcHaa967k9daTkd3mNWqCxomA0JaSqwyTWFiCvsegAOeigD LmoA== X-Gm-Message-State: AOAM531SxKyVdgaqBdUnWp4qhrNwHCgd3Xx6jQrw7VzjsQgGKnzQNA3T oUIcoei3fqoj2uCPkqQEXUbgxRO38S8= X-Received: by 2002:a50:cc48:: with SMTP id n8mr31354270edi.304.1632176828154; Mon, 20 Sep 2021 15:27:08 -0700 (PDT) Received: from localhost.localdomain ([95.168.120.5]) by smtp.gmail.com with ESMTPSA id k3sm6586028eje.117.2021.09.20.15.27.05 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 20 Sep 2021 15:27:07 -0700 (PDT) From: Paul B Mahol To: ffmpeg-devel@ffmpeg.org Date: Tue, 21 Sep 2021 00:26:51 +0200 Message-Id: <20210920222651.32168-1-onemda@gmail.com> X-Mailer: git-send-email 2.17.1 Subject: [FFmpeg-devel] [PATCH] avfilter: add morpho filter 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 MIME-Version: 1.0 Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" X-TUID: H67UQleJBH/D Signed-off-by: Paul B Mahol --- doc/filters.texi | 39 ++ libavfilter/Makefile | 1 + libavfilter/allfilters.c | 1 + libavfilter/vf_morpho.c | 909 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 950 insertions(+) create mode 100644 libavfilter/vf_morpho.c diff --git a/doc/filters.texi b/doc/filters.texi index 0c45fb710d..7c8861d2b3 100644 --- a/doc/filters.texi +++ b/doc/filters.texi @@ -10225,6 +10225,7 @@ A number representing position of the first frame with respect to the telecine pattern. This is to be used if the stream is cut. The default value is @code{0}. @end table +@anchor{dilation} @section dilation Apply dilation effect to the video. @@ -11541,6 +11542,7 @@ value. @end table +@anchor{erosion} @section erosion Apply erosion effect to the video. @@ -15316,6 +15318,43 @@ Default value is 0. This filter supports the all above options as @ref{commands}. +@section morpho + +This filter allows to apply main morphological grayscale transforms, +erode and dilate with arbitrary structures set in second input stream. + +Unlike naive implementation and much slower performance in @ref{erosion} +and @ref{dilation} filters, when speed is critical @code{morpho} filter +should be used instead. + +A description of accepted options follows, + +@table @option +@item mode +Set morphological transform to apply, can be: + +@table @samp +@item erode +@item dilate +@item open +@item close +@end table +Default is @code{erode}. + +@item planes +Set planes to filter, by default all planes except alpha are filtered. + +@item structure +Set which structure video frames will be processed from second input stream, +can be @var{first} or @var{all}. Default is @var{all}. +@end table + +The @code{morpho} filter also supports the @ref{framesync} options. + +@subsection Commands + +This filter supports same @ref{commands} as options. + @section mpdecimate Drop frames that do not differ greatly from the previous frame in diff --git a/libavfilter/Makefile b/libavfilter/Makefile index 272f876c07..06e01da38e 100644 --- a/libavfilter/Makefile +++ b/libavfilter/Makefile @@ -350,6 +350,7 @@ OBJS-$(CONFIG_MIDEQUALIZER_FILTER) += vf_midequalizer.o framesync.o OBJS-$(CONFIG_MINTERPOLATE_FILTER) += vf_minterpolate.o motion_estimation.o OBJS-$(CONFIG_MIX_FILTER) += vf_mix.o framesync.o OBJS-$(CONFIG_MONOCHROME_FILTER) += vf_monochrome.o +OBJS-$(CONFIG_MORPHO_FILTER) += vf_morpho.o OBJS-$(CONFIG_MPDECIMATE_FILTER) += vf_mpdecimate.o OBJS-$(CONFIG_NEGATE_FILTER) += vf_lut.o OBJS-$(CONFIG_NLMEANS_FILTER) += vf_nlmeans.o diff --git a/libavfilter/allfilters.c b/libavfilter/allfilters.c index 1283d124b8..10dfe72131 100644 --- a/libavfilter/allfilters.c +++ b/libavfilter/allfilters.c @@ -335,6 +335,7 @@ extern const AVFilter ff_vf_midequalizer; extern const AVFilter ff_vf_minterpolate; extern const AVFilter ff_vf_mix; extern const AVFilter ff_vf_monochrome; +extern const AVFilter ff_vf_morpho; extern const AVFilter ff_vf_mpdecimate; extern const AVFilter ff_vf_msad; extern const AVFilter ff_vf_negate; diff --git a/libavfilter/vf_morpho.c b/libavfilter/vf_morpho.c new file mode 100644 index 0000000000..d55ddbce48 --- /dev/null +++ b/libavfilter/vf_morpho.c @@ -0,0 +1,909 @@ +/* + * Copyright (c) 2016 ReneBrals + * Copyright (c) 2021 Paul B Mahol + * + * This file is part of FFmpeg. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include "libavutil/avassert.h" +#include "libavutil/imgutils.h" +#include "libavutil/intreadwrite.h" +#include "libavutil/opt.h" +#include "libavutil/pixdesc.h" +#include "avfilter.h" +#include "formats.h" +#include "framesync.h" +#include "internal.h" +#include "video.h" + +enum MorphModes { + ERODE, + DILATE, + OPEN, + CLOSE, + NB_MODES +}; + +typedef struct IPlane { + uint8_t **img; + size_t w; + size_t h; + size_t range; + int type_size; + + void (*max)(uint8_t *c, uint8_t *a, uint8_t *b, size_t x); + void (*min)(uint8_t *c, uint8_t *a, uint8_t *b, size_t x); + void (*max_in_place)(uint8_t *a, uint8_t *b, size_t x); + void (*min_in_place)(uint8_t *a, uint8_t *b, size_t x); +} IPlane; + +typedef struct LUT { + uint8_t ***arr; + int minR; + int maxR; + size_t I; + size_t X; + int padX; +} LUT; + +typedef struct chord { + int x; + int y; + int l; + int i; +} chord; + +typedef struct chord_set { + chord *C; + size_t size; + size_t cap; + + int *R; + size_t Lnum; + + int minX; + int maxX; + int minY; + int maxY; +} chord_set; + +typedef struct MorphoContext { + const AVClass *class; + FFFrameSync fs; + + chord_set SE[4]; + IPlane SEimg[4]; + IPlane g[4], f[4], h[4]; + LUT Ty[4]; + + int mode; + int planes; + int structures; + + int planewidth[4]; + int planeheight[4]; + int splanewidth[4]; + int splaneheight[4]; + int depth; + int type_size; + int nb_planes; + + int got_structure[4]; + + AVFrame *temp; +} MorphoContext; + +#define OFFSET(x) offsetof(MorphoContext, x) +#define FLAGS AV_OPT_FLAG_VIDEO_PARAM | AV_OPT_FLAG_FILTERING_PARAM | AV_OPT_FLAG_RUNTIME_PARAM + +static const AVOption morpho_options[] = { + { "mode", "set morphological transform", OFFSET(mode), AV_OPT_TYPE_INT, {.i64=0}, 0, NB_MODES-1, FLAGS, "mode" }, + { "erode", NULL, 0, AV_OPT_TYPE_CONST, {.i64=ERODE}, 0, 0, FLAGS, "mode" }, + { "dilate", NULL, 0, AV_OPT_TYPE_CONST, {.i64=DILATE}, 0, 0, FLAGS, "mode" }, + { "open", NULL, 0, AV_OPT_TYPE_CONST, {.i64=OPEN}, 0, 0, FLAGS, "mode" }, + { "close", NULL, 0, AV_OPT_TYPE_CONST, {.i64=CLOSE}, 0, 0, FLAGS, "mode" }, + { "planes", "set planes to filter", OFFSET(planes), AV_OPT_TYPE_INT, {.i64=7}, 0, 15, FLAGS }, + { "structure", "when to process structures", OFFSET(structures), AV_OPT_TYPE_INT, {.i64=1}, 0, 1, FLAGS, "str" }, + { "first", "process only first structure, ignore rest", 0, AV_OPT_TYPE_CONST, {.i64=0}, 0, 0, FLAGS, "str" }, + { "all", "process all structure", 0, AV_OPT_TYPE_CONST, {.i64=1}, 0, 0, FLAGS, "str" }, + { NULL } +}; + +FRAMESYNC_DEFINE_CLASS(morpho, MorphoContext, fs); + +static int query_formats(AVFilterContext *ctx) +{ + static const enum AVPixelFormat pix_fmts[] = { + AV_PIX_FMT_YUVA444P, AV_PIX_FMT_YUV444P, AV_PIX_FMT_YUV440P, + AV_PIX_FMT_YUVJ444P, AV_PIX_FMT_YUVJ440P, + AV_PIX_FMT_YUVA422P, AV_PIX_FMT_YUV422P, AV_PIX_FMT_YUVA420P, AV_PIX_FMT_YUV420P, + AV_PIX_FMT_YUVJ422P, AV_PIX_FMT_YUVJ420P, + AV_PIX_FMT_YUVJ411P, AV_PIX_FMT_YUV411P, AV_PIX_FMT_YUV410P, + AV_PIX_FMT_GBRP, AV_PIX_FMT_GBRAP, AV_PIX_FMT_GRAY8, AV_PIX_FMT_GRAY9, + AV_PIX_FMT_YUV420P9, AV_PIX_FMT_YUV422P9, AV_PIX_FMT_YUV444P9, AV_PIX_FMT_GBRP9, + AV_PIX_FMT_YUVA420P9, AV_PIX_FMT_YUVA422P9, AV_PIX_FMT_YUVA444P9, + AV_PIX_FMT_YUV420P10, AV_PIX_FMT_YUV422P10, AV_PIX_FMT_YUV444P10, + AV_PIX_FMT_YUV420P12, AV_PIX_FMT_YUV422P12, AV_PIX_FMT_YUV444P12, AV_PIX_FMT_YUV440P12, + AV_PIX_FMT_YUV420P14, AV_PIX_FMT_YUV422P14, AV_PIX_FMT_YUV444P14, + AV_PIX_FMT_YUV420P16, AV_PIX_FMT_YUV422P16, AV_PIX_FMT_YUV444P16, + AV_PIX_FMT_YUVA420P10, AV_PIX_FMT_YUVA422P10, AV_PIX_FMT_YUVA444P10, + AV_PIX_FMT_YUVA422P12, AV_PIX_FMT_YUVA444P12, + AV_PIX_FMT_YUVA420P16, AV_PIX_FMT_YUVA422P16, AV_PIX_FMT_YUVA444P16, + AV_PIX_FMT_GBRP10, AV_PIX_FMT_GBRP12, AV_PIX_FMT_GBRP14, AV_PIX_FMT_GBRP16, + AV_PIX_FMT_GBRAP10, AV_PIX_FMT_GBRAP12, AV_PIX_FMT_GBRAP16, + AV_PIX_FMT_GRAY10, AV_PIX_FMT_GRAY12, AV_PIX_FMT_GRAY14, AV_PIX_FMT_GRAY16, + AV_PIX_FMT_NONE + }; + + return ff_set_common_formats_from_list(ctx, pix_fmts); +} + +static void min_fun(uint8_t *c, uint8_t *a, uint8_t *b, size_t x) +{ + for (size_t i = 0; i < x; i++) + c[i] = FFMIN(b[i], a[i]); +} + +static void mininplace_fun(uint8_t *a, uint8_t *b, size_t x) +{ + for (size_t i = 0; i < x; i++) + a[i] = FFMIN(a[i], b[i]); +} + +static void max_fun(uint8_t *c, uint8_t *a, uint8_t *b, size_t x) +{ + for (size_t i = 0; i < x; i++) + c[i] = FFMAX(a[i], b[i]); +} + +static void maxinplace_fun(uint8_t *a, uint8_t *b, size_t x) +{ + for (size_t i = 0; i < x; i++) + a[i] = FFMAX(a[i], b[i]); +} + +static void min16_fun(uint8_t *cc, uint8_t *aa, uint8_t *bb, size_t x) +{ + uint16_t *a = (uint16_t *)aa; + uint16_t *b = (uint16_t *)bb; + uint16_t *c = (uint16_t *)cc; + + for (size_t i = 0; i < x; i++) + c[i] = FFMIN(b[i], a[i]); +} + +static void mininplace16_fun(uint8_t *aa, uint8_t *bb, size_t x) +{ + uint16_t *a = (uint16_t *)aa; + uint16_t *b = (uint16_t *)bb; + + for (size_t i = 0; i < x; i++) + a[i] = FFMIN(a[i], b[i]); +} + +static void max16_fun(uint8_t *cc, uint8_t *aa, uint8_t *bb, size_t x) +{ + uint16_t *a = (uint16_t *)aa; + uint16_t *b = (uint16_t *)bb; + uint16_t *c = (uint16_t *)cc; + + for (size_t i = 0; i < x; i++) + c[i] = FFMAX(a[i], b[i]); +} + +static void maxinplace16_fun(uint8_t *aa, uint8_t *bb, size_t x) +{ + uint16_t *a = (uint16_t *)aa; + uint16_t *b = (uint16_t *)bb; + + for (size_t i = 0; i < x; i++) + a[i] = FFMAX(a[i], b[i]); +} + +static int alloc_lut(LUT *Ty, chord_set SE, int type_size) +{ + size_t prePadX = 0; + + /* + * The LUT is pre-padded on X. This is needed for dilation, where the + * padding might contain valid information. + */ + if (SE.minX < 0) + prePadX = 0 - SE.minX; + Ty->padX = prePadX; + + Ty->arr = av_calloc((Ty->maxR - Ty->minR + 1), sizeof(uint8_t **)); + if (!Ty->arr) + return AVERROR(ENOMEM); + for (int r = 0; r < (Ty->maxR - Ty->minR + 1); r++) { + Ty->arr[r] = av_calloc(Ty->I, sizeof(uint8_t *)); + if (!Ty->arr[r]) + return AVERROR(ENOMEM); + for (int i = 0; i < Ty->I; i++) { + Ty->arr[r][i] = av_calloc(Ty->X + prePadX, type_size); + if (!Ty->arr[r][i]) + return AVERROR(ENOMEM); + /* Shifting the X index such that negative indices correspond to + * the pre-padding. + */ + Ty->arr[r][i] = &(Ty->arr[r][i][prePadX * type_size]); + } + } + + Ty->arr = &(Ty->arr[0 - Ty->minR]); + + return 0; +} + +static void free_lut(LUT *table, int type_size) +{ + uint8_t ***rp; + + if (!table->arr) + return; + + // The R index was shifted, create a pointer to the original array + rp = &(table->arr[table->minR]); + + for (int r = table->minR; r <= table->maxR; r++) { + for (int i = 0; i < table->I; i++) { + // The X index was also shifted, for padding purposes. + av_free(table->arr[r][i] - table->padX * type_size); + } + av_freep(&table->arr[r]); + } + av_freep(&rp); +} + +static void circular_swap(LUT Ty) +{ + uint8_t **Ty0; + int r; + + /* + * Swap the pointers to r-indices in a circle. This is useful because + * Ty(r,i,x) = Ty-1(r+1,i,x) for r < ymax. + */ + if (Ty.maxR - Ty.minR > 0) { + Ty0 = Ty.arr[Ty.minR]; + + for (r = Ty.minR; r < Ty.maxR; r++) { + Ty.arr[r] = Ty.arr[r + 1]; + } + + r = Ty.maxR; + Ty.arr[r] = Ty0; + } +} + +static void compute_min_row(IPlane f, LUT *Ty, chord_set SE, int r, size_t y) +{ + if (y + r > 0 && y + r < f.h) { + memcpy(Ty->arr[r][0], f.img[y + r], Ty->X * f.type_size); + } else { + memset(Ty->arr[r][0], UINT8_MAX, Ty->X * f.type_size); + } + + for (int i = 1; i < SE.Lnum; i++) { + int d = SE.R[i] - SE.R[i - 1]; + f.min(Ty->arr[r][i], + Ty->arr[r][i - 1], + Ty->arr[r][i - 1] + d * f.type_size, + FFMAX((int)Ty->X - (int)d, 0)); + } +} + +static void update_min_lut(IPlane f, LUT *Ty, chord_set SE, size_t y, size_t tid, size_t num) +{ + for (size_t i = 0; i < num; i++) + circular_swap(*Ty); + + compute_min_row(f, Ty, SE, Ty->maxR - tid, y); +} + +static int compute_min_lut(LUT *Ty, IPlane f, chord_set SE, size_t y, size_t num) +{ + if (Ty->I != SE.Lnum || + Ty->X != f.w || + Ty->minR != SE.minY || + Ty->maxR != SE.maxY + num - 1) { + int ret; + + free_lut(Ty, f.type_size); + + Ty->I = SE.Lnum; + Ty->X = f.w; + Ty->minR = SE.minY; + Ty->maxR = SE.maxY + num - 1; + ret = alloc_lut(Ty, SE, f.type_size); + if (ret < 0) + return ret; + } + + for (int r = Ty->minR; r <= Ty->maxR; r++) + compute_min_row(f, Ty, SE, r, y); + + return 0; +} + +static void compute_max_row(IPlane f, LUT *Ty, chord_set SE, int r, size_t y) +{ + if (y + r > 0 && y + r < f.h) { + memcpy(Ty->arr[r][0], f.img[y + r], Ty->X * f.type_size); + } else { + memset(Ty->arr[r][0], 0, Ty->X * f.type_size); + } + + for (int i = 1; i < SE.Lnum; i++) { + int d = SE.R[i] - SE.R[i - 1]; + + f.max(Ty->arr[r][i] - Ty->padX * f.type_size, + Ty->arr[r][i - 1] - Ty->padX * f.type_size, + Ty->arr[r][i - 1] + (d - Ty->padX) * f.type_size, + Ty->X + Ty->padX - d); + memcpy(Ty->arr[r][i] + (Ty->X - d) * f.type_size, + Ty->arr[r][i - 1] + (Ty->X - d) * f.type_size, + d * f.type_size); + } +} + +static void update_max_lut(IPlane f, LUT *Ty, chord_set SE, size_t y, size_t tid, size_t num) +{ + for (size_t i = 0; i < num; i++) + circular_swap(*Ty); + + compute_max_row(f, Ty, SE, Ty->maxR - tid, y); +} + +static int compute_max_lut(LUT *Ty, IPlane f, chord_set SE, size_t y, size_t num) +{ + if (Ty->I != SE.Lnum || + Ty->X != f.w || + Ty->minR != SE.minY || + Ty->maxR != SE.maxY + num - 1) { + int ret; + + free_lut(Ty, f.type_size); + + Ty->I = SE.Lnum; + Ty->X = f.w; + Ty->minR = SE.minY; + Ty->maxR = SE.maxY + num - 1; + ret = alloc_lut(Ty, SE, f.type_size); + if (ret < 0) + return ret; + } + + for (int r = Ty->minR; r <= Ty->maxR; r++) + compute_max_row(f, Ty, SE, r, y); + + return 0; +} + +static void line_dilate(IPlane *g, LUT *Ty, chord_set SE, int y, size_t tid) +{ + memset(g->img[y], 0, g->w * g->type_size); + + for (size_t c = 0; c < SE.size; c++) { + g->max_in_place(g->img[y], + Ty->arr[SE.C[c].y + tid][SE.C[c].i] + SE.C[c].x * g->type_size, + FFMIN(FFMAX((int)g->w - SE.C[c].x, 0), g->w)); + } +} + +static void line_erode(IPlane *g, LUT *Ty, chord_set SE, int y, size_t tid) +{ + memset(g->img[y], UINT8_MAX, g->w * g->type_size); + + for (size_t c = 0; c < SE.size; c++) { + g->min_in_place(g->img[y], + Ty->arr[SE.C[c].y + tid][SE.C[c].i] + SE.C[c].x * g->type_size, + FFMIN(FFMAX((int)g->w - SE.C[c].x, 0), g->w)); + } +} + +static int dilate(IPlane *g, IPlane f, chord_set SE, LUT *Ty) +{ + int ret = compute_max_lut(Ty, f, SE, 0, 1); + if (ret < 0) + return ret; + + line_dilate(g, Ty, SE, 0, 0); + for (size_t y = 1; y < f.h; y++) { + update_max_lut(f, Ty, SE, y, 0, 1); + line_dilate(g, Ty, SE, y, 0); + } + + return 0; +} + +static int erode(IPlane *g, IPlane f, chord_set SE, LUT *Ty) +{ + int ret = compute_min_lut(Ty, f, SE, 0, 1); + if (ret < 0) + return ret; + + line_erode(g, Ty, SE, 0, 0); + for (size_t y = 1; y < f.h; y++) { + update_min_lut(f, Ty, SE, y, 0, 1); + line_erode(g, Ty, SE, y, 0); + } + + return 0; +} + +static int insert_chord_set(chord_set *chords, chord c) +{ + // Checking if chord fits in dynamic array, resize if not. + if (chords->size == chords->cap) { + chords->C = av_realloc_f(chords->C, chords->cap * 2, sizeof(chord)); + if (!chords->C) + return AVERROR(ENOMEM); + chords->cap *= 2; + } + + // Add the chord to the dynamic array. + chords->C[chords->size].x = c.x; + chords->C[chords->size].y = c.y; + chords->C[chords->size++].l = c.l; + + // Update minimum/maximum x/y offsets of the chord set. + if (c.x < chords->minX) + chords->minX = c.x; + if (c.x > chords->maxX) + chords->maxX = c.x; + + if (c.y < chords->minY) + chords->minY = c.y; + if (c.y > chords->maxY) + chords->maxY = c.y; + + return 0; +} + +static void free_chord_set(chord_set *SE) +{ + av_freep(&SE->C); + SE->size = 0; + SE->cap = 0; + + av_freep(&SE->R); + SE->Lnum = 0; +} + +static int init_chordset(chord_set *chords) +{ + chords->size = 0; + chords->C = av_calloc(1, sizeof(chord)); + if (!chords->C) + return AVERROR(ENOMEM); + + chords->cap = 1; + chords->minX = INT_MAX; + chords->maxX = INT_MIN; + chords->minY = INT_MAX; + chords->maxY = INT_MIN; + + return 0; +} + +static int comp_chord_length(const void *p, const void *q) +{ + chord a, b; + a = *((chord *)p); + b = *((chord *)q); + + return (a.l > b.l) - (a.l < b.l); +} + +static int comp_chord(const void *p, const void *q) +{ + chord a, b; + a = *((chord *)p); + b = *((chord *)q); + + return (a.y > b.y) - (a.y < b.y); +} + +static int build_chord_set(IPlane SE, chord_set *chords) +{ + size_t chordLengthIndex, x, y; + int chordStart, val, ret; + int centerX, centerY; + size_t rCap = 1; + chord c; + + ret = init_chordset(chords); + if (ret < 0) + return ret; + /* + * In erosion/dilation, the center of the IPlane has S.E. offset (0,0). + * Otherwise, the resulting IPlane would be shifted to the top-left. + */ + centerX = (SE.w - 1) / 2; + centerY = (SE.h - 1) / 2; + + /* + * Computing the set of chords C. + */ + for (y = 0; y < SE.h; y++) { + chordStart = -1; + for (x = 0; x < SE.w; x++) { + if (SE.type_size == 1) { + //A chord is a run of non-zero pixels. + if (SE.img[y][x] != 0 && chordStart == -1) { + // Chord starts. + chordStart = x; + } else if (SE.img[y][x] == 0 && chordStart != -1) { + // Chord ends before end of line. + c.x = chordStart - centerX; + c.y = y - centerY; + c.l = x - chordStart; + insert_chord_set(chords, c); + chordStart = -1; + } + } else { + //A chord is a run of non-zero pixels. + if (AV_RN16(&SE.img[y][x * 2]) != 0 && chordStart == -1) { + // Chord starts. + chordStart = x; + } else if (AV_RN16(&SE.img[y][x + 2]) == 0 && chordStart != -1) { + // Chord ends before end of line. + c.x = chordStart - centerX; + c.y = y - centerY; + c.l = x - chordStart; + insert_chord_set(chords, c); + chordStart = -1; + } + } + } + if (chordStart != -1) { + // Chord ends at end of line. + c.x = chordStart - centerX; + c.y = y - centerY; + c.l = x - chordStart; + insert_chord_set(chords, c); + } + } + + /* + * Computing the array of chord lengths R(i). + * This is needed because the lookup table will contain a row for each + * length index i. + */ + qsort(chords->C, chords->size, sizeof(chord), comp_chord_length); + chords->R = av_calloc(1, sizeof(int)); + chords->Lnum = 0; + val = 0; + rCap = 1; + + if (chords->size > 0) { + val = 1; + if (chords->Lnum >= rCap) { + chords->R = av_realloc_f(chords->R, rCap * 2, sizeof(int)); + if (!chords->R) + return AVERROR(ENOMEM); + rCap *= 2; + } + chords->R[chords->Lnum++] = 1; + val = 1; + } + + for (int i = 0; i < chords->size; i++) { + if (val != chords->C[i].l) { + while (2 * val < chords->C[i].l && val != 0) { + + if (chords->Lnum >= rCap) { + chords->R = av_realloc_f(chords->R, rCap * 2, sizeof(int)); + if (!chords->R) + return AVERROR(ENOMEM); + rCap *= 2; + } + chords->R[chords->Lnum++] = 2 * val; + val *= 2; + } + val = chords->C[i].l; + + if (chords->Lnum >= rCap) { + chords->R = av_realloc_f(chords->R, rCap * 2, sizeof(int)); + if (!chords->R) + return AVERROR(ENOMEM); + rCap *= 2; + } + chords->R[chords->Lnum++] = val; + } + } + + /* + * Setting the length indices of chords. + * These are needed so that the algorithm can, for each chord, + * access the lookup table at the correct length in constant time. + */ + chordLengthIndex = 0; + for (int i = 0; i < chords->size; i++) { + while (chords->R[chordLengthIndex] < chords->C[i].l) + chordLengthIndex++; + chords->C[i].i = chordLengthIndex; + } + + /* + * Chords are sorted on Y. This way, when a row of the lookup table or IPlane + * is cached, the next chord offset has a better chance of being on the + * same cache line. + */ + qsort(chords->C, chords->size, sizeof(chord), comp_chord); + + return 0; +} + +static void free_iplane(IPlane *imp) +{ + av_freep(&imp->img); +} + +static int read_iplane(IPlane *imp, const uint8_t *dst, int dst_linesize, + int w, int h, int R, size_t type_size) +{ + if (!imp->img) + imp->img = av_calloc(h, sizeof(*imp->img)); + if (!imp->img) + return AVERROR(ENOMEM); + + imp->w = w; + imp->h = h; + imp->range = R; + imp->type_size = type_size; + imp->max = type_size == 1 ? max_fun : max16_fun; + imp->min = type_size == 1 ? min_fun : min16_fun; + imp->max_in_place = type_size == 1 ? maxinplace_fun : maxinplace16_fun; + imp->min_in_place = type_size == 1 ? mininplace_fun : mininplace16_fun; + + for (int y = 0; y < h; y++) + imp->img[y] = (uint8_t *)dst + y * dst_linesize; + + return 0; +} + +static int config_input(AVFilterLink *inlink) +{ + const AVPixFmtDescriptor *desc = av_pix_fmt_desc_get(inlink->format); + MorphoContext *s = inlink->dst->priv; + + s->depth = desc->comp[0].depth; + s->type_size = (s->depth + 7) / 8; + s->nb_planes = desc->nb_components; + s->planewidth[1] = s->planewidth[2] = AV_CEIL_RSHIFT(inlink->w, desc->log2_chroma_w); + s->planewidth[0] = s->planewidth[3] = inlink->w; + s->planeheight[1] = s->planeheight[2] = AV_CEIL_RSHIFT(inlink->h, desc->log2_chroma_h); + s->planeheight[0] = s->planeheight[3] = inlink->h; + + return 0; +} + +static int config_input_structure(AVFilterLink *inlink) +{ + const AVPixFmtDescriptor *desc = av_pix_fmt_desc_get(inlink->format); + AVFilterContext *ctx = inlink->dst; + MorphoContext *s = inlink->dst->priv; + + av_assert0(ctx->inputs[0]->format == ctx->inputs[1]->format); + + s->splanewidth[1] = s->splanewidth[2] = AV_CEIL_RSHIFT(inlink->w, desc->log2_chroma_w); + s->splanewidth[0] = s->splanewidth[3] = inlink->w; + s->splaneheight[1] = s->splaneheight[2] = AV_CEIL_RSHIFT(inlink->h, desc->log2_chroma_h); + s->splaneheight[0] = s->splaneheight[3] = inlink->h; + + return 0; +} + +static int activate(AVFilterContext *ctx) +{ + MorphoContext *s = ctx->priv; + return ff_framesync_activate(&s->fs); +} + +static int do_morpho(FFFrameSync *fs) +{ + AVFilterContext *ctx = fs->parent; + AVFilterLink *outlink = ctx->outputs[0]; + MorphoContext *s = ctx->priv; + AVFrame *in = NULL, *structurepic = NULL; + AVFrame *out; + int ret; + + ret = ff_framesync_dualinput_get(fs, &in, &structurepic); + if (ret < 0) + return ret; + if (!structurepic) + return ff_filter_frame(outlink, in); + + out = ff_get_video_buffer(outlink, outlink->w, outlink->h); + if (!out) { + av_frame_free(&in); + return AVERROR(ENOMEM); + } + av_frame_copy_props(out, in); + + for (int p = 0; p < s->nb_planes; p++) { + const uint8_t *src = in->data[p]; + const int src_linesize = in->linesize[p]; + const uint8_t *ssrc = structurepic->data[p]; + const int ssrc_linesize = structurepic->linesize[p]; + uint8_t *ddst = out->data[p]; + const int dst_linesize = out->linesize[p]; + const int swidth = s->splanewidth[p]; + const int sheight = s->splaneheight[p]; + const int width = s->planewidth[p]; + const int height = s->planeheight[p]; + const int type_size = s->type_size; + + if (!(s->planes & (1 << p))) { + av_image_copy_plane(out->data[p] + 0 * out->linesize[p], + out->linesize[p], + in->data[p] + 0 * in->linesize[p], + in->linesize[p], + width * ((s->depth + 7) / 8), + height); + continue; + } + + if (!s->got_structure[p] || s->structures) { + ret = read_iplane(&s->SEimg[p], ssrc, ssrc_linesize, swidth, sheight, 1, type_size); + if (ret < 0) + goto fail; + ret = build_chord_set(s->SEimg[p], &s->SE[p]); + if (ret < 0) + goto fail; + s->got_structure[p] = 1; + } + + ret = read_iplane(&s->f[p], src, src_linesize, width, height, 1, type_size); + if (ret < 0) + goto fail; + + ret = read_iplane(&s->g[p], ddst, dst_linesize, s->f[p].w, s->f[p].h, s->f[p].range, type_size); + if (ret < 0) + goto fail; + + switch (s->mode) { + case ERODE: + ret = erode(&s->g[p], s->f[p], s->SE[p], &s->Ty[p]); + break; + case DILATE: + ret = dilate(&s->g[p], s->f[p], s->SE[p], &s->Ty[p]); + break; + case OPEN: + ret = read_iplane(&s->h[p], s->temp->data[p], s->temp->linesize[p], width, height, 1, type_size); + if (ret < 0) + break; + ret = erode(&s->h[p], s->f[p], s->SE[p], &s->Ty[p]); + if (ret < 0) + break; + ret = dilate(&s->g[p], s->h[p], s->SE[p], &s->Ty[p]); + break; + case CLOSE: + ret = read_iplane(&s->h[p], s->temp->data[p], s->temp->linesize[p], width, height, 1, type_size); + if (ret < 0) + break; + ret = dilate(&s->h[p], s->f[p], s->SE[p], &s->Ty[p]); + if (ret < 0) + break; + ret = erode(&s->g[p], s->h[p], s->SE[p], &s->Ty[p]); + break; + default: + av_assert0(0); + } + + if (ret < 0) + goto fail; + + if (s->structures) + free_chord_set(&s->SE[p]); + } + + av_frame_free(&in); + out->pts = av_rescale_q(s->fs.pts, s->fs.time_base, outlink->time_base); + return ff_filter_frame(outlink, out); +fail: + av_frame_free(&in); + return ret; +} + +static int config_output(AVFilterLink *outlink) +{ + AVFilterContext *ctx = outlink->src; + MorphoContext *s = ctx->priv; + AVFilterLink *mainlink = ctx->inputs[0]; + int ret; + + s->fs.on_event = do_morpho; + ret = ff_framesync_init_dualinput(&s->fs, ctx); + if (ret < 0) + return ret; + outlink->w = mainlink->w; + outlink->h = mainlink->h; + outlink->time_base = mainlink->time_base; + outlink->sample_aspect_ratio = mainlink->sample_aspect_ratio; + outlink->frame_rate = mainlink->frame_rate; + + if ((ret = ff_framesync_configure(&s->fs)) < 0) + return ret; + outlink->time_base = s->fs.time_base; + + s->temp = ff_get_video_buffer(outlink, outlink->w, outlink->h); + if (!s->temp) + return AVERROR(ENOMEM); + + return 0; +} + +static av_cold void uninit(AVFilterContext *ctx) +{ + MorphoContext *s = ctx->priv; + + for (int p = 0; p < 4; p++) { + free_iplane(&s->SEimg[p]); + free_iplane(&s->g[p]); + free_iplane(&s->f[p]); + free_chord_set(&s->SE[p]); + free_lut(&s->Ty[p], s->type_size); + } + + ff_framesync_uninit(&s->fs); + + av_frame_free(&s->temp); +} + +static const AVFilterPad morpho_inputs[] = { + { + .name = "default", + .type = AVMEDIA_TYPE_VIDEO, + .config_props = config_input, + }, + { + .name = "structure", + .type = AVMEDIA_TYPE_VIDEO, + .config_props = config_input_structure, + }, +}; + +static const AVFilterPad morpho_outputs[] = { + { + .name = "default", + .type = AVMEDIA_TYPE_VIDEO, + .config_props = config_output, + }, +}; + +const AVFilter ff_vf_morpho = { + .name = "morpho", + .description = NULL_IF_CONFIG_SMALL("Apply Morphological filter."), + .preinit = morpho_framesync_preinit, + .priv_size = sizeof(MorphoContext), + .priv_class = &morpho_class, + .activate = activate, + .uninit = uninit, + .query_formats = query_formats, + FILTER_INPUTS(morpho_inputs), + FILTER_OUTPUTS(morpho_outputs), + .flags = AVFILTER_FLAG_SUPPORT_TIMELINE_GENERIC, + .process_command = ff_filter_process_command, +};