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

[Stefano Sabatini]

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.
-- 
FFmpeg = Furious and Foolish Meaningless Power Ecumenical Gadget
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-lavfi-port-boxblur-filter-from-libmpcodecs.patch
Type: text/x-diff
Size: 16335 bytes
Desc: not available
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20110710/d8ebc36c/attachment.bin>