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

[Michael Niedermayer]

On Sun, Jul 10, 2011 at 08:36:21PM +0200, Stefano Sabatini wrote:
> 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)

a parametric radius is certainly a good idea
and radius > max(w,h) makes little sense as theres nothing left of the
picture at that point.
about min(w,h)/2, i think that may be annoying in corner cases
like when a image is 16x1024 sized for example, so it probably makes
sense to extend the code to handle values above that limit at some
point in the future.

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Frequently ignored awnser#1 FFmpeg bugs should be sent to our bugtracker. User
questions about the command line tools should be sent to the ffmpeg-user ML.
And questions about how to use libav* should be sent to the libav-user ML.
-------------- 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/e8aabd3c/attachment.asc>