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

[Michael Niedermayer]

On Sun, Jul 10, 2011 at 11:30:54PM +0200, Stefano Sabatini wrote:
> On date Sunday 2011-07-10 22:03:56 +0200, Michael Niedermayer encoded:
> > 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.
> 
> also we may make horizontal/vertical radius configurable.
> 
> Anyway I don't see the need for adding even more features right now,
> new version attached.

yes, LGTM
and thx

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

It is dangerous to be right in matters on which the established authorities
are wrong. -- Voltaire
-------------- 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/20110711/e47d854a/attachment.asc>