[FFmpeg-devel] [PATCH] lavfi: port boxblur filter from libmpcodecs
Michael Niedermayer
michaelni at gmx.at
Sun Jul 10 11:48:59 CEST 2011
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>
More information about the ffmpeg-devel
mailing list