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

[Michael Niedermayer]

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


[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

I hate to see young programmers poisoned by the kind of thinking
Ulrich Drepper puts forward since it is simply too narrow -- Roman Shaposhnik
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20110710/562535a8/attachment.asc>