Average all frames in a clip

[jmac698]

Hi,
I'd like a script for this, just can't think of how to do it. It's easy to use overlay or even average plugin to do a few frames, but I want to average an entire clip.
Even better if it can ignore certain pixels that changed too much.
I'm extracting a noisy background from a perfectly still camera.

[-Vit-]

Possible starting point

function AvgAll2(clip c) { c.FrameCount() <= 1 ? c : AvgAll2( Merge(c.SelectEven(),c.SelectOdd()) ) }

Some frames will count multiple times towards the average when c has an odd length (at any stage of the recursion). Imagine you could get around that with some extra code in the function. There will be accuracy loss due to the repeated rounding. It's slow though and I didn't have the patience to wait for it on a long clip.

More usable for long clips with Average (tested on 100000 frame clip, took less than a minute):

function AvgAll8(clip c) {
c.FrameCount() <= 1 ? c \
: AvgAll8( Average(c.SelectEvery(8,0),0.125,c.SelectEvery(8,1),0.125,c.SelectEvery(8,2),0.125,c.SelectEvery(8,3),0.125, \
c.SelectEvery(8,4),0.125,c.SelectEvery(8,5),0.125,c.SelectEvery(8,6),0.125,c.SelectEvery(8,7),0.125 ) )
}

Again may wish to add extra code to deal with non mod8 frame counts - not sure if it will make much difference. And give some consideration to rounding errors - but you said it is noise you are averaging so...

[Gavino]

function AvgAll2(clip c) { c.FrameCount() <= 1 ? c : AvgAll2( Merge(c.SelectEven(),c.SelectOdd()) ) }

Some frames will count multiple times towards the average when c has an odd length (at any stage of the recursion).
I think that can be fixed by writing it this way:
function AvgAll2(clip c) { c.FrameCount() <= 1 ? c : Merge(AvgAll2(c.SelectEven()), AvgAll2(c.SelectOdd())) }


Similarly, in the other function:
function AvgAll8(clip c) {
c.FrameCount() <= 1 ? c \
: Average(AvgAll8(c.SelectEvery(8,0)),0.125, AvgAll8(c.SelectEvery(8,1)),0.125, ... )
}

[-Vit-]

No, that will still have a similar problem. Consider framecount=3, it will do a 50/50 merge of a 2-frame average and a 1-frame average - uneven weights.
I think this would be correct:

function AvgAll2(clip c) {
c.FrameCount() <= 1 ? c \
: Merge( AvgAll2(c.SelectEven()), AvgAll2(c.SelectOdd()), c.SelectOdd().FrameCount()/Float(c.FrameCount) )
}


However, these versions are massively slower than the first suggestion, unusable over a few 1000 frames. The Average 8 version is actually slower with this kind of variation.

I think a different approach is needed for longer clips if precision is required. Although for extracting a static background, the original may be good enough.

[jmac698]

#avg all
#make test case
y1=blankclip(length=1,pixel_type="YV12",color_yuv=$7F8080)
y2=blankclip(length=1,pixel_type="YV12",color_yuv=$008080)
y3=blankclip(length=1,pixel_type="YV12",color_yuv=$808080)
y1+y2+y3
avgall
function AvgAll(clip c){
c.FrameCount() <= 1 ? c : Merge(AvgAll(c.SelectEven()), AvgAll(c.SelectOdd()))
}

The accuracy can be horrible. In this case, a=127, b=0, c=128. round((a+b+c)/3)=85
round((round((a+c)/2)+c)/2)=64.
With this test, I can see that merge does rounding, and that Gavino's idea works as expected, the even frames of the first clip and the odd frame(s) of the 2nd.
Even for small noise like +0 to +5, the error can be -2.
The max error is -42 in 3 frames.

Increasing the inner split like avgall8 doesn't actually help because now it just takes a specific pattern to cause the errors, I believe. For example, adding 3 at a time, but with 3 frames, you get ((a+c)/2+b)/2 There's another pattern possible with 6 frames.

There's a limit to eval strings as well.

[jmac698]

Yes, the new function gives the exact answer 85 in the test. I needed the redaverage plugin. http://forum.doom9.org/showthread.php?t=163018 click the 1.43
I actually used 1.35 but it worked.

And yes the weights were wrong, it was approx. .25*a+.5*b+.25*c,=64

[-Vit-]

This version has precision and decent performance. Uses the first version of AvgAll2 for speed. Splits the clip into blocks of power-of-2 lengths (effectively treats the frame count as binary). Each block's average is calculated correctly with the simple AvgAll2 since powers of 2 blocks will always split into equal odd/even lists. Blocks are averaged together with weighted merges. Processes 100000 480p frames in around 30s. Needs GScript:

function AvgAll(clip c) {
GScript("""
frms = c.FrameCount()
pow2 = 1
totl = 0
while (frms > 0) {
if (frms % 2 > 0) {
blkAvg = c.Trim(0,-pow2).AvgAll2()
c = c.Trim(pow2,0)
if (totl == 0) {
avg = blkAvg
} else {
avg = Merge( avg, blkAvg, Float(pow2)/(totl+pow2) )
}
totl = totl + pow2
}
frms = frms / 2
pow2 = pow2 * 2
}
""")
return avg
}

function AvgAll2(clip c) { c.FrameCount() <= 1 ? c : AvgAll2( Merge(c.SelectEven(), c.SelectOdd()) ) }


Edit: The integer rounding errors from so many small merges creep in with longer clips though - there's a gradual color shift.

Edit2: So go 16-bit. Accurate, slower, 10000 frames in a minute. Needs DitherTools:

function AvgAll_16(clip c) {
GScript("""
c = c.Dither_convert_8_to_16() # To 16 bit
c = c.Dither_lut16("x 0.5 *", U=3,V=3) # down to 15-bit to get faster average below
frms = c.FrameCount()
pow2 = 1
totl = 0
while (frms > 0) {
if (frms % 2 > 0) {
blkAvg = c.Trim(0,-pow2).AvgAll2_16()
c = c.Trim(pow2,0)
if (totl == 0) {
avg = blkAvg
} else {
avg = Merge_16( avg, blkAvg, Float(pow2)/(totl+pow2) )
}
totl = totl + pow2
}
frms = frms / 2
pow2 = pow2 * 2
}
""")
return Dither_add16(avg,avg).DitherPost(mode=-1) # Back to 16 bit then to 8 again
}

# Same as AvgAll2 for 8-bit, but uses faster average (assumes 15-bit input values)
function AvgAll2_16(clip c) {
c.FrameCount() <= 1 ? c \
: AvgAll2_16( Dither_add16(c.SelectEven(),c.SelectOdd()).Dither_lut16("x 0.5 *", U=3,V=3) )
}

# Like Avisynth native Merge but for 16-bit clips
function Merge_16(clip a, clip b, float "weight") {
weight = default(weight, 0.5)
mul1 = String(1.0-weight)
a = a.Dither_lut16("x "+mul1+" *", U=3,V=3)
mul2 = String(weight)
b = b.Dither_lut16("x "+mul2+" *", U=3,V=3)
return Dither_add16(a, b)
}

[jmac698]

Hmm if we go to gscript, what if we stack each line and resize the whole thing? Should have 32bit accuracy...


function AvgAll3(clip c){
c=c.pointresize(c.width,c.height*2)#use fat lines to workaround minheight
GScript("""
frms = c.FrameCount()
for (y=0, c.Height/2-1) {
for (t=0, frms-1) {
f=t==0?getline(c,y,t):stackvertical(f,getline(c,y,t))
}
f=f.pointresize(f.width,4)#this has to change to some command to get averageluma
#maybe f.blankclip(f.width,2,color_yuv=averageluma)
result=y==0?f:stackvertical(result,f)
}
result.pointresize(result.width, result.height/2)
""")
}

function getline(clip c, int y, int t){
y=y*2
c.trim(t,t==0?-1:t)
#return a line of height 2 from y to y+1
crop(0,y,0,-(last.height-y-2))
}

ps some bugs, still editing...

@Gavino
Which brings me to a point, it's not trivial to write practical (fast) pixel manipulation in Avisynth. People keep telling me to just write plugins, but I'd have to write a dozen plugins by now just to do simple pixel manipulation tasks (measuring pixels, draw rectangles, plot test patterns etc.) I just don't think you should need a new plugin for these tasks. So my conclusion, is something is wrong with the language. Being turing complete is not an answer, it has to be convenient and also fast, in this case expressive to pixel tasks.

Interesting, I've asked you this before http://forum.videohelp.com/threads/340426-DeJitter-help?p=2119128&viewfull=1#post2119128

[Gavino]

No, that will still have a similar problem. Consider framecount=3, it will do a 50/50 merge of a 2-frame average and a 1-frame average - uneven weights.
I think this would be correct:

function AvgAll2(clip c) {
c.FrameCount() <= 1 ? c \
: Merge( AvgAll2(c.SelectEven()), AvgAll2(c.SelectOdd()), c.SelectOdd().FrameCount()/Float(c.FrameCount) )
}

However, these versions are massively slower than the first suggestion, unusable over a few 1000 frames.
Yes, I forgot about needing different weights.
The slowdown is because Merge is optimised for a weight of 0.5 (or 0.0 or 1.0).

This version has precision and decent performance. Uses the first version of AvgAll2 for speed. Splits the clip into blocks of power-of-2 lengths (effectively treats the frame count as binary).
Really neat algorithm. :cool:

[Gavino]

Hmm if we go to gscript, what if we stack each line and resize the whole thing? Should have 32bit accuracy...
If I understand correctly, you are stacking lines from every frame together. That's going to be very slow for real clips and will likely run out of memory.
@Gavino
Which brings me to a point, it's not trivial to write practical (fast) pixel manipulation in Avisynth. People keep telling me to just write plugins, but I'd have to write a dozen plugins by now just to do simple pixel manipulation tasks (measuring pixels, draw rectangles, plot test patterns etc.) I just don't think you should need a new plugin for these tasks. So my conclusion, is something is wrong with the language. Being turing complete is not an answer, it has to be convenient and also fast, in this case expressive to pixel tasks.
Pixel manipulation in the script language would be too slow.

Once you've written one plugin, writing another one (especially if similar) is very easy. You wouldn't even need a new plugin - just keep adding new functions which could use shared code for common tasks. And once you have your development environment set up, recompilation and reloading your DLL only takes a few seconds.

Interesting, I've asked you this before http://forum.videohelp.com/threads/340426-DeJitter-help?p=2119128&viewfull=1#post2119128
I'd completely forgotten that - I see that I didn't give you a satisfactory answer then either. :)

[TheFluff]

@Gavino
Which brings me to a point, it's not trivial to write practical (fast) pixel manipulation in Avisynth. People keep telling me to just write plugins, but I'd have to write a dozen plugins by now just to do simple pixel manipulation tasks (measuring pixels, draw rectangles, plot test patterns etc.) I just don't think you should need a new plugin for these tasks. So my conclusion, is something is wrong with the language. Being turing complete is not an answer, it has to be convenient and also fast, in this case expressive to pixel tasks.

When all you have is a hammer, every problem looks like a nail. The problem is that trying to unscrew a screw with a hammer is going to fail miserably. I've said this before, but I'll say it again: AVISYNTH SCRIPT IS NOT A SUITABLE TOOL FOR EVERY SINGLE PROGRAMMING TASK ON THE PLANET.

There are things that are very easy to do in Avisynth script, and there are things that are very hard, because unlike, say, C, Avisynth script isn't intended to be a general-purpose language. If your tool isn't suited to the task at hand, use a different tool. Your obstinate insistence on using Avisynth script for absolutely everything under the sun and then complaining about how there is "something wrong with the language" is getting really annoying.

[jmac698]

I made a plugin in for this. Only problem, the script is faster! Thanks vit.
http://www.sendspace.com/filegroup/9Jp55ub7vo%2BWcMacRzuyCQ

My plan now is write a pixel manipulation plugin, so I don't have to make a dozen plugins ;)

[StainlessS]

3 new plugins in two days,
methinks we witness the birth of a monster. :)

EDIT: 4 new plugins in two days,
Will this madness never end. :devil:

EDIT: Ref to following post, Frankenstein was the scientist fellow, don't think the monster was ever named. :eek:

[jmac698]

You're only to blame man, you threw the switch with that plugin sample! Frankenstein is born!
But I have to thank you heaps for that :)

I'm telling you, I need *dozens* of plugins for the stuff I do, that's why I think it's gonna get ridiculous. I'm thinking of a meta plugin that does vector operations on all lines in parallel, as most of my stuff operates on the line level. Stuff like limit change per line, random values per line, cast to deep color stacked format, array operations, basic math, subpixel shifting, resizing, indexed replacements from video list, etc.

[Forensic]

I could use that frame averaging DLL. Please repost. Thank you.

[Reel.Deel]

I could use that frame averaging DLL. Please repost. Thank you.

I re-uploaded most of jmac's plugins here (http://forum.doom9.org/showthread.php?p=1690894#post1690894), I believe you're looking for taverage. You might also be interested in StainlessS' ClipBlend (http://forum.doom9.org/showthread.php?t=168048).

[Forensic]

Thank you