[FFmpeg-devel] [PATCH 1/2 v2] delogo: Use weighted interpolation

[Stefano Sabatini]

On date Wednesday 2013-06-26 14:50:37 +0200, Jean Delvare encoded:
> The original delogo algorithm interpolates both horizontally and
> vertically and uses the average to compute the resulting sample. This
> works reasonably well when the logo area is almost square. However
> when the logo area is significantly larger than high or higher than
> large, the result is largely suboptimal.
> 
> The issue can be clearly seen by testing the delogo filter with a fake
> logo area that is 200 pixels large and 2 pixels high. Vertical
> interpolation gives a very good result in that case, horizontal
> interpolation gives a very bad result, and the overall result is poor,
> because both are given the same weight.
> 
> Even when the logo is roughly square, the current algorithm gives poor
> results on the borders of the logo area, because it always gives
> horizontal and vertical interpolations an equal weight, and this is
> suboptimal on borders. For example, in the middle of the left hand
> side border of the logo, you want to trust the left known point much
> more than the right known point (which the current algorithm already
> does) but also much more than the top and bottom known points (which
> the current algorithm doesn't do.)
> 
> By properly weighting each known point when computing the value of
> each interpolated pixel, the visual result is much better, especially
> on borders and/or for high or large logo areas.
> 
> The algorithm I implemented guarantees that the weight of each of the
> 4 known points directly depends on its distance to the interpolated
> point. It is largely inspired from the original algorithm, the key
> difference being that it computes the relative weights globally
> instead of separating the vertical and horizontal interpolations and
> combining them afterward.
> 
> Signed-off-by: Jean Delvare <khali at linux-fr.org>
> ---
> I am using unsigned long long here because the computations would
> otherwise possibly overflow when the logo area is big.
> 
> Changes since v1:
>  * Stop claiming the new algorithm is slower, it isn't.
>  * Handle clipping properly.
>  * Fix an off-by-one error on right and bottom distances.
> 
>  libavfilter/vf_delogo.c      |   25 +++-
>  tests/ref/fate/filter-delogo |  218 +++++++++++++++++++++----------------------
>  2 files changed, 126 insertions(+), 117 deletions(-)
> 
> --- ffmpeg.orig/libavfilter/vf_delogo.c	2013-06-26 10:16:22.716508202 +0200
> +++ ffmpeg/libavfilter/vf_delogo.c	2013-06-26 10:31:12.102268045 +0200
> @@ -1,6 +1,7 @@
>  /*
>   * Copyright (c) 2002 Jindrich Makovicka <makovick at gmail.com>
>   * Copyright (c) 2011 Stefano Sabatini
> + * Copyright (c) 2013 Jean Delvare <khali at linux-fr.org>
>   *
>   * This file is part of FFmpeg.
>   *
> @@ -22,7 +23,8 @@
>  /**
>   * @file
>   * A very simple tv station logo remover
> - * Ported from MPlayer libmpcodecs/vf_delogo.c.
> + * Originally imported from MPlayer libmpcodecs/vf_delogo.c,
> + * the algorithm was later improved.
>   */
>  
>  #include "libavutil/common.h"
> @@ -58,8 +60,8 @@ static void apply_delogo(uint8_t *dst, i
>                           int logo_x, int logo_y, int logo_w, int logo_h,
>                           int band, int show, int direct)
>  {
> -    int x, y;
> -    int interp, dist;
> +    int x, y, dist;
> +    uint64_t interp, weightl, weightr, weightt, weightb;
>      uint8_t *xdst, *xsrc;
>  
>      uint8_t *topleft, *botleft, *topright;
> @@ -90,23 +92,30 @@ static void apply_delogo(uint8_t *dst, i
>          for (x = logo_x1+1,
>               xdst = dst+logo_x1+1,
>               xsrc = src+logo_x1+1; x < logo_x2-1; x++, xdst++, xsrc++) {
> +
> +            /* Weighted interpolation based on relative distances */
> +            weightl = (uint64_t)              (logo_x2-1-x) * (y-logo_y1) * (logo_y2-1-y);
> +            weightr = (uint64_t)(x-logo_x1)                 * (y-logo_y1) * (logo_y2-1-y);
> +            weightt = (uint64_t)(x-logo_x1) * (logo_x2-1-x)               * (logo_y2-1-y);
> +            weightb = (uint64_t)(x-logo_x1) * (logo_x2-1-x) * (y-logo_y1);
> +
>              interp =
>                  (topleft[src_linesize*(y-logo_y  -yclipt)]   +
>                   topleft[src_linesize*(y-logo_y-1-yclipt)]   +
> -                 topleft[src_linesize*(y-logo_y+1-yclipt)])  * (logo_w-(x-logo_x))/logo_w
> +                 topleft[src_linesize*(y-logo_y+1-yclipt)])  * weightl
>                  +
>                  (topright[src_linesize*(y-logo_y-yclipt)]    +
>                   topright[src_linesize*(y-logo_y-1-yclipt)]  +
> -                 topright[src_linesize*(y-logo_y+1-yclipt)]) * (x-logo_x)/logo_w
> +                 topright[src_linesize*(y-logo_y+1-yclipt)]) * weightr
>                  +
>                  (topleft[x-logo_x-xclipl]    +
>                   topleft[x-logo_x-1-xclipl]  +
> -                 topleft[x-logo_x+1-xclipl]) * (logo_h-(y-logo_y))/logo_h
> +                 topleft[x-logo_x+1-xclipl]) * weightt
>                  +
>                  (botleft[x-logo_x-xclipl]    +
>                   botleft[x-logo_x-1-xclipl]  +
> -                 botleft[x-logo_x+1-xclipl]) * (y-logo_y)/logo_h;
> -            interp /= 6;
> +                 botleft[x-logo_x+1-xclipl]) * weightb;
> +            interp /= (weightl + weightr + weightt + weightb) * 3U;
[...]

LGTM and nice idea.

Another possibility would be to consider generalized barycentric
coordinates with respect to the logo rectangle vertexes, but this
would be a completely different algorithm.

I assume that the algorithm has been tested, and will push it in a day
(or let Michael push it) if there are no other comments.
-- 
FFmpeg = Funny & Fostering Mastering Pitiless Erotic Gnome