[FFmpeg-devel] [PATCH] lavfi: port boxblur filter from libmpcodecs

[Stefano Sabatini]

On date Sunday 2011-07-10 11:48:59 +0200, Michael Niedermayer encoded:
> On Sun, Jul 10, 2011 at 01:24:48AM +0200, Stefano Sabatini wrote:
> > On date Saturday 2011-07-09 23:33:22 +0200, Michael Niedermayer encoded:
> > > On Sat, Jul 09, 2011 at 06:41:44PM +0200, Stefano Sabatini wrote:
> > > [...]
> > > > +static inline void blur(uint8_t *dst, int dst_linesize, uint8_t *src, int src_linesize,
> > > > +                        int w, int radius)
> > > > +{
> > > 
> > > linesizes represent the size in bytes of a horizintal line everywhere
> > > in ffmpeg.
> > > here they dont, thus IMHO the original that used step is less confusing.
> > 
> > Changed back.
> > 
> > > > +    int x, sum = 0;
> > > > +    const int length = radius*2 + 1;
> > > > +    const int inv = ((1<<16) + length/2)/length;
> > > > +
> > > > +    for (x = 0; x < radius; x++)
> > > > +        sum += src[x]<<1;
> > > > +    sum += src[radius];
> > > > +
> > > > +    for (x = 0; x <= radius; x++) {
> > > > +        sum += src[radius+x] - src[radius-x];
> > > > +        dst[x] = (sum*inv + (1<<15))>>16;
> > > > +    }
> > > > +
> > > > +    for (; x < w-radius; x++) {
> > > > +        sum += src[radius+x] - src[x-radius-1];
> > > > +        dst[x] = (sum*inv + (1<<15))>>16;
> > > > +    }
> > > > +
> > > > +    for (; x < w; x++) {
> > > > +        sum += src[2*w-radius-x-1] - src[x-radius-1];
> > > > +        dst[x] = (sum*inv + (1<<15))>>16;
> > > > +    }
> > > > +}
> > 
> > BTW would you mind to explain the algorithm in this function? I can't
> > grasp it, but surely this will crash if radius is big enough.
> 
> it needs radius < w
> 
> the way it works is very simple
> naive boxblur would sum source pixels from x-radius .. x+radius for
> destination pixel x. That would be O(radius*width)
> If you now look at what source pixels represent 2 consecutive output
> pixels then you see they are almost identical and only differ by 2
> pixels, like:
> 
> src0       111111111
> dst0           1
> 
> src1        111111111
> dst1            1
> 
> src0-src1  1       -1
> 
> so when you know one output pixel you can find the next by just adding
> 1 and subtracting 1 input pixel.
> Which is faster, namely O(width) and thus also asymptotically optimal

Yes makes sense now.

As for the radius limit (radius < min(w/2,h/2)), what do you think is
the best option?

1. fail if the condition is not satisfied
2. clip radius in the valid range, and warn the user
3. make radius parametric, so you can tell radius=min(w/4,h/4)
-- 
FFmpeg = Fanciful and Freak Minimalistic Problematic Extroverse Guru