Help debugging recursive runtime script

[Mini-Me]

I have some interlaced VHS captures with jittery/bouncing fields. The fields randomly move up or down a few [whole] pixels vertically, screwing up the interlacing (and potentially making deinterlacing harder). I've tried an AVT-8710 TBC, but it only makes things worse (in addition to compressing some of the upper luma range). Maybe it's broken. I've also tried solutions like Depan/DepanStabilize, Stab, and the function g-force created that preceded Stab, but they don't work nearly as well as a brute force routine.

My naive brute force version does the following:
Create 16 shifted clips by moving the odd and even fields up and down by 1, 2, 3, and 4 pixels.
Weave each clip and take a vertical edge mask of each with a "0 0 0 0 -1 0 0 1 0" kernel.
Repeatedly use GConditionalFilter and AverageLuma to compare masks, and select the less combed frame.
Perform the previous step 8 times to cut the 16 extra clips down to 8, do it 4 more times to cut 8 clips down to 4, do it 2 more times to cut 4 clips down to 2, and do it again to get the best shifted frame. Finally, compare the best shifted clip with the original to get the best frame of all.

It's giving me fantastic results, but there are three weaknesses:
It's slightly suboptimal, because it doesn't mix/match odd/even field shifts. Only one field will be shifted in the final frame. If the best solution was to move the even field up 1 and the odd field down 2, this algorithm will return a frame with only the even field shifted up 3 or the odd field shifted down 3.
It's not entirely robust, since a field might hypothetically be jittered by more than 4 rows.
It's slower than it needs to be. Running on my slow capture computer (Athlon 64 3000+), I'm getting about 3.7 FPS. Most of this computation is wasteful, because most fields are only jittered by 0, 1, or 2 rows.

In response, I'm trying to create a recursive version that starts with small shifts and moves on to progressively larger shifts when the result seems to be improving. Unfortunately, this requires runtime recursion. According to Gavino's GRunT thread, you should be able to call runtime functions within user functions called by runtime functions, but...I'm getting a crash with this version. Any pointers?

Note that this requires Masktools 2 and GRunT. The main function is Stabilize, and it requires planar input due to the mt_edge call. It also assumes TFF order for now, since that's what my captures are...but come to think of it, the AssumeTFF calls are probably unnecessary in this case, regardless of field order.

### MAIN FUNCTION ###
function Stabilize(clip orig)
{
# Get the clip's combed edges and weave them with the clip itself.
origedges = orig.GetCombedEdges()
origandedgeswoven = Interleave(orig, origedges).AssumeFieldBased.Weave()

# Stabilize in "clockwise" and "counterclockwise" directions and choose the best result.
# If orig is best, both clockwise and counterclockwise directions will return it.
# No additional test is necessary.
bestandedgeswoven = ChooseLessCombedFramesWovenEdges(StabilizeClockwise(origandedgeswoven), \
StabilizeCounterclockwise(origandedgeswoven))

# Extract and return the actual clip
best = bestandedgeswoven.SeparateFields.SelectEven.AssumeFrameBased()
return best
}


### STABILIZE SUBROUTINES ###
function GetCombedEdges(clip c)
{
# Vertical edges between adjacent lines are a decent measure of combing.
# The Greyscale call is probably useless, so consider removing it.
# The levels call could probably use more testing and better parameters,
# but it's working pretty well.
return c.mt_edge("0 0 0 0 -1 0 0 1 0", 0, 255, 0, 255).Greyscale().Levels(0, 5, 64, 0, 255)
}

function ChooseLessCombedFramesWovenEdges(clip try1andedgeswoven, clip try2andedgeswoven)
{
# Separate edges from clips, compare brightness of edges, and return the edge-woven clip
# with the dimmest edges. Chances are one or both args are redundant, but whatev.
return GConditionalFilter(try1andedgeswoven, try1andedgeswoven, try2andedgeswoven, """
AverageLuma(try1andedgeswoven.SeparateFields.SelectOdd()) < AverageLuma(try2andedgeswoven.SeparateFields.SelectOdd())
""", args = "try1andedgeswoven, try2andedgeswoven", local = true)
}


# Moving even fields up is almost equivalent to moving odd fields down.
# Do them together, and call them "clockwise."
function StabilizeClockwise(clip currentandedgeswoven)
{
# Get clips with odd fields shifted down a line and even fields shifted up a line
current = currentandedgeswoven.SeparateFields.SelectEven.AssumeFrameBased().AssumeTFF.SeparateFields()
evenup = current.ShiftEvenLumaAndChroma(0.0, 1.0).Weave()
odddown = current.ShiftOddLumaAndChroma(0.0, -1.0).Weave()

# Get combed edges of the new clips
evenupedges = evenup.GetCombedEdges()
odddownedges = odddown.GetCombedEdges()

# Weave clips with edges
evenupandedgeswoven = Interleave(evenup, evenupedges).AssumeFieldBased.Weave()
odddownandedgeswoven = Interleave(odddown, odddownedges).AssumeFieldBased.Weave()

# Which is better?
oddorevenandedgeswoven = ChooseLessCombedFramesWovenEdges(evenupandedgeswoven, odddownandedgeswoven)

# Which is best?
bestandedgeswoven = ChooseLessCombedFramesWovenEdges(currentandedgeswoven, oddorevenandedgeswoven)

# If current is not the best, recurse again using the best
return GScriptClip(currentandedgeswoven, """
return AverageLuma(currentandedgeswoven) == AverageLuma(bestandedgeswoven) ? currentandedgeswoven \
: StabilizeClockwise(bestandedgeswoven)
""", args = "currentandedgeswoven, bestandedgeswoven", local = True)
}


# Moving even fields down is almost equivalent to moving odd fields up.
# Do them together, and call them "counterclockwise."
function StabilizeCounterclockwise(clip currentandedgeswoven)
{
# Get clips with odd fields shifted down a line and even fields shifted up a line
current = currentandedgeswoven.SeparateFields.SelectEven.AssumeFrameBased().AssumeTFF.SeparateFields()
evendown = current.ShiftEvenLumaAndChroma(0.0, -1.0).Weave()
oddup = current.ShiftOddLumaAndChroma(0.0, 1.0).Weave()

# Get combed edges of the new clips
evendownedges = evendown.GetCombedEdges()
oddupedges = oddup.GetCombedEdges()

# Weave clips with edges
evendownandedgeswoven = Interleave(evendown, evendownedges).AssumeFieldBased.Weave()
oddupandedgeswoven = Interleave(oddup, oddupedges).AssumeFieldBased.Weave()

# Which is better?
oddorevenandedgeswoven = ChooseLessCombedFramesWovenEdges(evendownandedgeswoven, oddupandedgeswoven)

# Which is best?
bestandedgeswoven = ChooseLessCombedFramesWovenEdges(currentandedgeswoven, oddorevenandedgeswoven)

# If current is not the best, recurse again using the best
return GScriptClip(currentandedgeswoven, """
return AverageLuma(currentandedgeswoven) == AverageLuma(bestandedgeswoven) ? currentandedgeswoven \
: StabilizeCounterclockwise(bestandedgeswoven)
""", args = "currentandedgeswoven, bestandedgeswoven", local = True)
}


### UTILITY FUNCTIONS ###
function SubpixelShift(clip input, float deltax, float deltay, bool "sharp")
{
sharp = Default(sharp, True)
return sharp ? Spline36Resize(input, input.Width(), input.Height(), deltax, deltay, input.Width(), input.Height()) \
: BilinearResize(input, input.Width(), input.Height(), deltax, deltay, input.Width(), input.Height())
}

function ShiftOddLumaAndChroma(clip c, float deltax, float deltay, bool "sharp")
{
deltax = Default(deltax, 0.0)
deltay = Default(deltay, 0.0)
sharp = Default(sharp, True)

return Interleave(c.SelectEven(), c.SubpixelShift(deltax, deltay, sharp).SelectOdd())
}


Sorry for the long lines. :-/ Are you allowed to use '\' for line continuation inside the quotes of a runtime function (particularly with GRunT)?

[Gavino]

Are you allowed to use '\' for line continuation inside the quotes of a runtime function (particularly with GRunT)?
Yes.

Your other question may take a little longer to answer. :)

[Gavino]

I don't yet fully understand how your code is designed to work, but are you sure the recursion bottoms out?
Basically, the recursion occurs in the functions StabilizeClockwise and StabilizeCounterclockwise:
function StabilizeClockwise(clip currentandedgeswoven)
{ ...
# If current is not the best, recurse again using the best
return GScriptClip(currentandedgeswoven, """
return AverageLuma(currentandedgeswoven) == AverageLuma(bestandedgeswoven) ? currentandedgeswoven \
: StabilizeClockwise(currentandedgeswoven)
""", args = "currentandedgeswoven, bestandedgeswoven", local = True)
}
Perhaps it should be using bestandedgeswoven on the recursive call?

According to Gavino's GRunT thread, you should be able to call runtime functions within user functions called by runtime functions
What you are doing is slightly different, in that you are calling (G)ScriptClip itself recursively. I think this should work, but perhaps it's inefficient and unnecessary. Because of the ability to call runtime functions (eg AverageLuma) directly from a user function, you don't need to wrap the inner call inside ScriptClip or ConditionalFilter, as long as the function itself is called inside ScriptClip. But that would involve a redesign of your outer level function so that ScriptClip is called only once and all the recursion takes place inside it.

[Mini-Me]

I don't yet fully understand how your code is designed to work, but are you sure the recursion bottoms out?

Basically, the recursion occurs in the functions StabilizeClockwise and StabilizeCounterclockwise:

Perhaps it should be using bestandedgeswoven on the recursive call?

Good catch! I had an infinite loop, and fixing it makes the script work! The results are excellent, but I'll still tweak the combing measurement for further improvement. It also seems a lot faster than my previous version. Even though I have some other stuff running, I'm getting ~10.5 FPS on average, whereas my original implementation yielded about ~3.7 FPS. Thank you so much!

I think I need to pass the recursion level as a parameter though and put a limit on it. Ordinary frames seem to be going quite fast, but it's taking too long to find the nonexistent "sweet spot" for the garbage frames at the beginning of the capture. ;)


What you are doing is slightly different, in that you are calling (G)ScriptClip itself recursively. I think this should work, but perhaps it's inefficient and unnecessary. Because of the ability to call runtime functions (eg AverageLuma) directly from a user function, you don't need to wrap the inner call inside ScriptClip or ConditionalFilter, as long as the function itself is called inside ScriptClip. But that would involve a redesign of your outer level function so that ScriptClip is called only once and all the recursion takes place inside it.

I'll refactor it as you suggest for clarity and efficiency and see if it gets any faster. Thanks for the advice! UPDATE: The refactored version works as well, but it's a bit slower at the moment. Instead of ~10.5 FPS average, the refactored version gets ~8.6 FPS average. I'll have to keep working on this.

I know there are some other threads where posters needed something like this, so once I have the script "release ready," I'll create a new thread and officially "publish" it for use under the GPL. :) In the meantime, I'll fix the infinite loop above script in case anyone could use it ASAP.

[TheProfileth]

I look forward to your finished product

[Mini-Me]

I look forward to your finished product

I'm glad to hear it! :D

The biggest problem right now is that it's TOO good at lining up fields. In its current form, it can't differentiate between VCR jitter and a vertically panning camera, so whenever the camera pans vertically, it lines up the fields so they match. This eliminates a lot of combing in the woven image, but running it through a bob deinterlacer (or simply separating fields) shows jerkier vertical panning. Instead of smoothly panning up or down every field, it's only panning on even fields, and it's vertically aligning the odd fields with the even ones. (Doing clip.Stabilize.SeparateFields.Doubleweave() shows almost no combing on even frames and tons of combing on odd frames when the camera pans vertically.)

I'm thinking I should base the algorithm on a doubleweave and select the permutation that has the least combined combing between the two frames associated with each field. Coding it is going to get hairy, but it probably needs to be done.

UPDATE: I'm working on the doubleweave solution to eliminate the field-pairing bias, but it's pretty difficult. Since each field's shift decision affects two frames in the doubleweave, it affects the other shift decisions of those frames, which affect their neighbors, etc. Technically, I guess this is something like a sparse linear system with diagonal and near-diagonal nonzero elements in a gigantic numfields x numfields size matrix. :eek: Obviously that isn't solvable in Avisynth, but hopefully I can hack together something sane.

[Gavino]

@Mini-Me

Is this the same as (or similar to) the code that you are currently having memory problems with (reported here)?

In post #3 above, I said:
What you are doing is slightly different, in that you are calling (G)ScriptClip itself recursively. I think this should work, but perhaps it's inefficient and unnecessary. Because of the ability to call runtime functions (eg AverageLuma) directly from a user function, you don't need to wrap the inner call inside ScriptClip or ConditionalFilter, as long as the function itself is called inside ScriptClip. But that would involve a redesign of your outer level function so that ScriptClip is called only once and all the recursion takes place inside it.
The relevance of this is that, because ScriptClip compiles the run-time script on every frame, it uses up space in Avisynth's string table (for variable names, etc). Most of the time, this is not significant, but if ScriptClip is called with a very long run-time script or called recursively to a great depth, coupled with lots of source frames, it could eventually eat up a lot of memory.

[Mini-Me]

@Mini-Me

Is this the same as (or similar to) the code that you are currently having memory problems with (reported here)?

In post #3 above, I said:

The relevance of this is that, because ScriptClip compiles the run-time script on every frame, it uses up space in Avisynth's string table (for variable names, etc). Most of the time, this is not significant, but if ScriptClip is called with a very long run-time script or called recursively to a great depth, coupled with lots of source frames, it could eventually eat up a lot of memory.

Good memory, Gavino! :D Although my current working version is very different from the one posted above (complete redesign), it is in fact the same function.

The new version shares the ScriptClip recursion of the original, and it's actually a lot longer, so what you say seems very plausible. Does the string table accumulate entries every frame without ever being cleared? If so, is there a reason this is necessary, or could it be changed someday to recycle the memory?

[Gavino]

Does the string table accumulate entries every frame without ever being cleared? If so, is there a reason this is necessary, or could it be changed someday to recycle the memory?
Yes, the string table does accumulate entries for each frame rendered by a run-time filter.
I can think of a number of ways this could be improved/fixed, including changes to ScriptClip itself, but normally there is a simple workaround - use functions to cut down the size of the run-time script. Taking this approach to its limit, you can even replace the entire run-time script by a function call. Instead of writing
ScriptClip("""
... # very long script
""")
do this
function f(clip c, int current_frame) {
c
... # code from run-time script
}
...
ScriptClip("f(current_frame)")

See here for an example which fixed a previously mysterious memory leak in SRestore.
(BTW The current_frame parameter is not needed if using GRunT, since it makes current_frame global).

In your case, the recursive use of ScriptClip adds a further complication, but I think you could restructure your code to call ScriptClip once and do the recursion inside it. In fact, you said in post #4 that you were able to do this with your earlier code.

[Mini-Me]

Yes, the string table does accumulate entries for each frame rendered by a run-time filter.
I can think of a number of ways this could be improved/fixed, including changes to ScriptClip itself, but normally there is a simple workaround - use functions to cut down the size of the run-time script. Taking this approach to its limit, you can even replace the entire run-time script by a function call. Instead of writing
ScriptClip("""
... # very long script
""")
do this
function f(clip c, int current_frame) {
c
... # code from run-time script
}
...
ScriptClip("f(current_frame)")

See here for an example which fixed a previously mysterious memory leak in SRestore.
(BTW The current_frame parameter is not needed if using GRunT, since it makes current_frame global).

In your case, the recursive use of ScriptClip adds a further complication, but I think you could restructure your code to call ScriptClip once and do the recursion inside it. In fact, you said in post #4 that you were able to do this with your earlier code.

I took your advice, and the version I've been using actually does call ScriptClip only once...but since the helper functions also use ScriptClip functionality through GRunT (AverageLuma, etc.), I figured they were contributing to the size of the string table as well. Apparently they don't?

Although most of the work (and all of the recursion) is already done inside of helper functions, I'll take that approach to its limit as you suggest and call a single function from within GScriptClip, which then continues to delegate work.

Thanks for the advice, and I'll report back after some testing!

[Gavino]

I took your advice, and the version I've been using actually does call ScriptClip only once...but since the helper functions also use ScriptClip functionality through GRunT (AverageLuma, etc.), I figured they were contributing to the size of the string table as well. Apparently they don't?
Only the actual text passed to ScriptClip contributes, as that text is parsed on every frame. Called functions (assuming they are defined outside the ScriptClip string) do not - their text has already been parsed before ScriptClip is called.

[Mini-Me]

Only the actual text passed to ScriptClip contributes, as that text is parsed on every frame. Called functions (assuming they are defined outside the ScriptClip string) do not - their text has already been parsed before ScriptClip is called.

That's good to know!

Reducing the ScriptClip text to a single function call improved things considerably. I have some other [local] recursive runtime functions that still eventually run out of memory, but it takes about five times longer now. It actually takes almost a million frames now before memory usage gets high enough to crash. Practically speaking, that only happens when I run the functions on multiple source files in the same script (long story ;)). The stabilization function doesn't seem to crash at all anymore, because I can only use it once per script anyway (it uses a global variable to track changes to the previous frame, and it uses a second global to store the previous frame number and check whether the first can be used).

It seems that any ScriptClip function will eventually crash given enough frames, and mine are probably pushing that limit now. I'm looking forward to releasing them, but I'm still tweaking them for now. :) Thank you for your help!

[spoRv]

Yes, the string table does accumulate entries for each frame rendered by a run-time filter.
I can think of a number of ways this could be improved/fixed, including changes to ScriptClip itself, but normally there is a simple workaround - use functions to cut down the size of the run-time script. Taking this approach to its limit, you can even replace the entire run-time script by a function call. Instead of writing
ScriptClip("""
... # very long script
""")
do this
function f(clip c, int current_frame) {
c
... # code from run-time script
}
...
ScriptClip("f(current_frame)")


Once I had a memory leak problem usinga a function with Gscriptclip inside, and some current_frame instances, that lead always to "out of memory, folks" message... I tried your workaround but, albeit working, it didn't stop crashes...

Then, I followed another, maybe unhortodox, path, and strangely it worked - still don't know why! Can't remember what was in the functions, but it was something like the following

Before:

function x(clip clip, int parameter) {
global parameter=parameter
Gscriptclip("""
... #filter 1 using current_frame
... #filter 2 using current_frame
... #filter 3 using current_frame
""")}


After;

function x(clip clip, int parameter) {
global parameter=parameter
clip
Gscriptclip("""
... #filter 1 using current_frame
""")}

function y(clip clip, int parameter) {
global parameter=parameter
clip
Gscriptclip("""
... #filter 2 using current_frame
""")}

function z(clip clip, int parameter) {
global parameter=parameter
clip
Gscriptclip("""
... #filter 3 using current_frame
""")}

function all(clip clip, int parameter) {
global parameter=parameter
clip.x(parameter).y(parameter).z(parameter)
}

Hope this could help someone who fights with memory leaks!

[Gavino]

Once I had a memory leak problem usinga a function with Gscriptclip inside, and some current_frame instances, that lead always to "out of memory, folks" message... I tried your workaround but, albeit working, it didn't stop crashes...

Then, I followed another, maybe unhortodox, path, and strangely it worked - still don't know why!
Interesting.
Regarding string table memory use, there is no difference between your 'before' and 'after' variants - the total run-time script size is effectively the same - so I don't understand why one should work and not the other.

But I note that there is a potential problem with your use of global variables (in both versions).
If any of the functions is called more than once (with different parameter values), the run-time scripts for all except the last invocation of the function will see the wrong value for the global.
This is because all the assignments to the global occur at compile-time, before any of the run-time scripts are evaluated, and so the run-time script for each invocation of the function sees only the final value of the global.
(See The script execution model/Scope and lifetime of variables (http://avisynth.nl/index.php/The_script_execution_model/Scope_and_lifetime_of_variables))

For example, with
function x(clip clip, int parameter) {
global parameter=parameter
ScriptClip(clip, """
...
""")
}
...
x(1)
...
x(2)

when the run-time script for x(1) is evaluated, parameter has the value 2, not 1.

That's why GRunT (GScriptClip, etc) introduced the args parameter to 'freeze' compile-time values into a run-time script - the problem above is solved by writing
function x(clip clip, int parameter) {
# global parameter=parameter : removed
Gscriptclip(clip, """
...
""", args="parameter")
}

Although this problem is the same in both the 'before' and 'after' outlines you showed, I wonder if perhaps some subtle difference in the way the globals were used in the actual script was the cause of the change in behaviour. (But if no function was actually called more than once, this issue can be ruled out.)

[spoRv]

AFAIR, it was called just once. And probably there where more than one parameter, there was one for each filter... can't remember...

I'm no expert, but maybe calling all these filter within a single Gscriptclip instance made avisynth (and/or virtualdub) goes south! :D Honestly, I expected it to consume more memory splitting the tasks, but the contrary was true...

I add that I saved the clip using Lagarith, if it can be of some help to discover this strange behaviour.

Last thing: to discover if your avisynth script has some kind of memory leak, instead of waiting hours (days) before it will crash, just load it in virtualdub, and point randomly to the seeking bar - I mean, a lot of times, grab the cursor and drag it left and right... you will see memory rise; then, memory will eventually stops at a certain point, or raises until an out of memory message will appear. It can save A LOT of time, wasted otherwise...