A field matcher especially for cartoons

[mwhitlock]

I've recently been working on converting the Futurama DVDs into MPEG-4 AVC+AAC (x264 + Nero Digital AAC). The MPEGs on the DVDs are encoded with 3:2 pulldown flags, so I simply used "Forced Film" mode in DGIndex, giving me 24000/1001-fps clips with mostly progressive frames. In a perfect world, they'd all be progressive frames, but due to the lipsyncing process used by the animators, there are many frames that are still combed. Too bad the DVD authors encoded those frames as progressive, thus screwing up the chroma subsampling, but that's another story for another day.

Careful study using AviSynth's SeparateFields and StackHorizontal functions led me to realize that most of the combed frames were in fact weaves of one field from the previous frame and the opposite field from the next frame. I knew that any kind of motion-based smart deinterlacing would be stupid because I wasn't dealing with an actual interlaced source, but I also couldn't run IVTC because I was already at 24fps. The solution of course was to field match to restore the progressive frames.

However, in many cases, particularly due to the bad chroma subsampling, pairing the even field from one frame with the odd field from another frame produced rainbowy artifacts. Tritical's TFM field matcher likes pairing fields from different frames, so I couldn't use it. I needed a field matcher that would prefer taking both fields from the same source frame and only resort to mixing fields from two source frames if absolutely necessary. To solve my problem, I scripted my own field matcher using purely built-in AviSynth functions.

http://img53.imageshack.us/img53/8051/compare6xc.png (http://imageshack.us)

My first task was finding a way to tell if any two fields were meant to go together in the same progressive frame. The fields of almost any progressive frame are extremely similar to each other, and when bobbed to correct for the vertical displacement, they're almost identical. Therefore, to tell if two fields belonged to the same progressive frame, I only needed to determine "how identical" they were. The easiest way I found was to difference the two bobbed fields using the Overlay function and examine the value of YPlaneMax() on the result. The magic number for my content was around 235-240: maximum lumas higher than that meant the two fields were definitely not from the same progressive frame.

Now I will turn to the task of picking out the fields to compare from the source clip. My current frame is cc, which is my source clip, and my next frame is nn = cc.DeleteFrame(0). I bob cc and nn so I have offset-corrected fields that should overlap perfectly if they belong together. I then do the four differences: the current even field with the current odd field, the next even field with the next odd field, the current even field with the next odd field, and the next even field with the current odd field.

You might wonder why I test both diagonal directions. If the field order of the clip is constant, I should never get matches in both diagonals in the same clip. But guess what, the field order of my source material isn't constant! Incredible what the lipsyncing process does to video.

At this point, it's simply a matter of choosing the highest preference pairing that satisfies my match condition. The AviSynth script for my field matcher follows:

function FieldMatch(clip c) {
global cc = c
global nn = cc.DeleteFrame(0)
global bc = cc.Bob()
global bn = nn.Bob()
return ScriptClip( \
cc, \
"bc.SelectEven().Overlay(bc.SelectOdd(), mode="+Chr(34)+"Difference"+Chr(34)+").YPlaneMax() < 240 ? cc : " + \
"bn.SelectEven().Overlay(bn.SelectOdd(), mode="+Chr(34)+"Difference"+Chr(34)+").YPlaneMax() < 240 ? nn : " + \
"bc.SelectEven().Overlay(bn.SelectOdd(), mode="+Chr(34)+"Difference"+Chr(34)+").YPlaneMax() < 240 ? " + \
"Interleave(cc.SeparateFields().SelectEven(), nn.SeparateFields().SelectOdd()).Weave() : " + \
"bn.SelectEven().Overlay(bc.SelectOdd(), mode="+Chr(34)+"Difference"+Chr(34)+").YPlaneMax() < 240 ? " + \
"Interleave(nn.SeparateFields().SelectEven(), cc.SeparateFields().SelectOdd()).Weave() : " + \
"cc" \
)
}

To do a real nice comparison, I set up the following script:

cc = MPEG2source("F:\1ACV01.d2v", cpu=6).BicubicResize(640, 480)
nn = cc.DeleteFrame(0)

bc = cc.Bob()
bn = nn.Bob()

dceco = bc.SelectEven().Overlay(bc.SelectOdd(), mode="Difference")
dneno = bn.SelectEven().Overlay(bn.SelectOdd(), mode="Difference")
dceno = bc.SelectEven().Overlay(bn.SelectOdd(), mode="Difference")
dneco = bn.SelectEven().Overlay(bc.SelectOdd(), mode="Difference")

c = cc.SeparateFields()
n = nn.SeparateFields()

out = ScriptClip( \
cc, \
"dceco.YPlaneMax() < 240 ? cc.Subtitle("+Chr(34)+"Curr/Curr"+Chr(34)+") : " + \
"dneno.YPlaneMax() < 240 ? nn.Subtitle("+Chr(34)+"Next/Next"+Chr(34)+") : " + \
"dceno.YPlaneMax() < 240 ? Interleave(c.SelectEven(), " + \
"n.SelectOdd()).Weave().Subtitle("+Chr(34)+"Curr/Next"+Chr(34)+") : " + \
"dneco.YPlaneMax() < 240 ? Interleave(n.SelectEven(), " + \
"c.SelectOdd()).Weave().Subtitle("+Chr(34)+"Next/Curr"+Chr(34)+") : " + \
"cc.Subtitle("+Chr(34)+"Curr/Curr - Match Failure"+Chr(34)+")" \
)

StackVertical( \
StackHorizontal( \
cc.Subtitle("Original"), \
StackVertical( \
StackHorizontal( \
ScriptClip(c.SelectEven().HorizontalReduceBy2().Subtitle("Curr Even"), \
"Subtitle(String(dceco.YPlaneMax()), align=2).\
Subtitle(String(dceno.YPlaneMax()), align=3)"), \
ScriptClip(n.SelectEven().HorizontalReduceBy2().Subtitle("Next Even"), \
"Subtitle(String(dneco.YPlaneMax()), align=1).\
Subtitle(String(dneno.YPlaneMax()), align=2)") \
), \
StackHorizontal( \
c.SelectOdd().HorizontalReduceBy2().Subtitle("Curr Odd"), \
n.SelectOdd().HorizontalReduceBy2().Subtitle("Next Odd") \
) \
) \
), \
StackHorizontal( \
cc.TFM(PP=0, display=true, micout=2).Subtitle("TFM(PP=0)", align=1), \
out.Subtitle("Mine", align=3) \
) \
)

Download a sample output from this comparison script (http://www.filewire.com/download.php?id=84ef0ef71c699e333905722) (66.2 MB)
This video file is ripe with good points for comparison of the two field matchers. Be sure to look at frame 692.

[mwhitlock]

I've been messing with this a bit more. The original script was having false positives on the combing detection, so it was avoiding frames that it should have accepted. The result was some jerkiness. I decided to rework the script using tritical's IsCombedTIVTC function instead of my difference max luma trick. The new version is faster, and seems to do fairly well.

function FieldMatch(clip c) {
global cc = c
global nn = c.DeleteFrame(0)
c2 = cc.SeparateFields()
n2 = nn.SeparateFields()
global cn = Interleave(c2.SelectEven(), n2.SelectOdd()).Weave()
global nc = Interleave(n2.SelectEven(), c2.SelectOdd()).Weave()
return ScriptClip(cc, \
"!cc.IsCombedTIVTC(cthresh=12, MI=40) ? cc : " + \
"!nn.IsCombedTIVTC(cthresh=12, MI=40) ? nn : " + \
"!cn.IsCombedTIVTC(cthresh=12, MI=40) ? cn : " + \
"!nc.IsCombedTIVTC(cthresh=12, MI=40) ? nc : cc" \
)
}

I had to tweak the cthresh and MI parameters to make them work better on the cartoon material. These values seem to do a good job.

I also discovered a nice option of MPEG2source to help with the chroma problems. It's still not perfect because the DVD authoring has done some damage to the chroma on certain frames, but that's exactly why I wrote this field matcher, to try to avoid those bad frames by using both fields from the next full frame instead of mixing fields from the current, broken-chroma frame and the next, good frame.

cc = MPEG2source("F:\1ACV01.d2v", cpu=6, upConv=1).BicubicResize(640, 480)
nn = cc.DeleteFrame(0)
c2 = cc.SeparateFields()
n2 = nn.SeparateFields()
cn = Interleave(c2.SelectEven(), n2.SelectOdd()).Weave()
nc = Interleave(n2.SelectEven(), c2.SelectOdd()).Weave()

out = ScriptClip( \
cc, \
"!cc.IsCombedTIVTC(cthresh=12, MI=40) ? cc.Subtitle("+Chr(34)+"Curr/Curr"+Chr(34)+") : " + \
"!nn.IsCombedTIVTC(cthresh=12, MI=40) ? nn.Subtitle("+Chr(34)+"Next/Next"+Chr(34)+") : " + \
"!cn.IsCombedTIVTC(cthresh=12, MI=40) ? cn.Subtitle("+Chr(34)+"Curr/Next"+Chr(34)+") : " + \
"!nc.IsCombedTIVTC(cthresh=12, MI=40) ? nc.Subtitle("+Chr(34)+"Next/Curr"+Chr(34)+") : " + \
"cc.ShowCombedTIVTC(cthresh=12, MI=40).Subtitle("+Chr(34)+"Curr/Curr - Match Failure"+Chr(34)+")" \
)

StackHorizontal( \
StackVertical( \
cc.ShowCombedTIVTC(cthresh=12, MI=40, display=2), \
cc.TFM(PP=0, cthresh=12, MI=40, display=true, micout=2) \
), \
StackVertical( \
StackVertical( \
StackHorizontal( \
ScriptClip( \
c2.SelectEven().HorizontalReduceBy2().Subtitle("Curr Even"), \
"Subtitle(String(!cc.IsCombedTIVTC(cthresh=12, MI=40)), align=2)." + \
"Subtitle(String(!cn.IsCombedTIVTC(cthresh=12, MI=40)), align=3)" \
), \
ScriptClip( \
n2.SelectEven().HorizontalReduceBy2().Subtitle("Next Even"), \
"Subtitle(String(!nc.IsCombedTIVTC(cthresh=12, MI=40)), align=1)." + \
"Subtitle(String(!nn.IsCombedTIVTC(cthresh=12, MI=40)), align=2)" \
) \
), \
StackHorizontal( \
c2.SelectOdd().HorizontalReduceBy2().Subtitle("Curr Odd"), \
n2.SelectOdd().HorizontalReduceBy2().Subtitle("Next Odd") \
) \
), \
out.Subtitle("Mine", align=1) \
) \
)

There's the new test script.

Here are some interesting frames from the comparison:
http://img457.imageshack.us/img457/9637/1229ss.th.png (http://img457.imageshack.us/my.php?image=1229ss.png) http://img164.imageshack.us/img164/3561/5206ub.th.png (http://img164.imageshack.us/my.php?image=5206ub.png) http://img457.imageshack.us/img457/673/6924xo.th.png (http://img457.imageshack.us/my.php?image=6924xo.png)
http://img457.imageshack.us/img457/7955/8827mu.th.png (http://img457.imageshack.us/my.php?image=8827mu.png) http://img457.imageshack.us/img457/5412/10069hi.th.png (http://img457.imageshack.us/my.php?image=10069hi.png) http://img457.imageshack.us/img457/4118/15206ay.th.png (http://img457.imageshack.us/my.php?image=15206ay.png)

Download this new comparison script's output of the same clip (http://www.filewire.com/download.php?id=b704d2de1c69a6cee697c16) (68.7 MB)

[mwhitlock]

Here's a tiny clip (7 frames) from my source that demonstrates the issue with the alternating field orders. TFM can only be set to use TFF or BFF order, so it can't properly handle this clip with either setting. My field matcher looks at both Curr-Even/Next-Odd and Next-Even/Curr-Odd to select the best match, so it can handle problematic areas like that in this clip.

problematic.avi (http://www.filewire.com/download.php?id=531a0b241c69a75e39defac) (1731 KB)

[tritical]

Would you be able to post the original source vobs? Also, tfm(mode=4) is able to match clips with alternating field order.

[mwhitlock]

Would you be able to post the original source vobs?
I'd be hesitant to do this for a couple of reasons: 1) they're huge, of course (1GB each), and I have no good way of cutting out just a few frames from them; and 2) I've probably already stepped over the copyright line with the test clips I've posted, but posting original VOBs from the DVD is pretty blatant.

The problematic clip I posted is encoded with Huffyuv by VirtualDub reading the following AviSynth script:
MPEG2source("F:\1ACV01.d2v", cpu=6, upConv=1)
where MPEG2source is from Donald Graft's DGDecode plugin. I produced the d2v file with DGIndex operating in "Forced Film" mode. I used "Fast Recompress" mode in VirtualDub since that preserves the YUY2 colorspace from the AviSynth script. (Right?)

Would something like ProjectX be able to losslessly extract those few frames from the VOBs and save them to an MPEG-2 elementary video stream? I suppose it would actually need to copy the full GOPs, not just the frames I put in problematic.avi.

I can post another Huffyuv AVI from a d2v created with the "Honor Pulldown Flags" mode of DGIndex if that would be helpful to you.

I'm going to try the mode=4 now. I thought I tried all the modes of TFM but maybe not.

Thanks for taking an interest!

[mwhitlock]

Interestingly, this crashes:
TFM(mode=4, PP=0, display=true, micout=2)
And while this doesn't crash, it still can't handle the clip:
TFM(mode=4, PP=0, display=true)
I also tried explicitly setting order=0 and order=1, and they produced different results (different frames came through as combed).

[mwhitlock]

Take a look at this hellish nightmare. I extracted this MPEG-2 elementary video stream from the VOB using ProjectX in demux mode.

Download (http://www.filewire.com/download.php?id=508e2af11c69af5e17ba166) (1497 KB)

[mwhitlock]

And here's the MPEG-2 of the "problematic" clip:

Download (http://www.filewire.com/download.php?id=638233091c69af83b1fd7fc) (2133 KB)

[tritical]

Thanks for the clip. You can also use dgindex for cutting... set cut points on the timeline and then go to file->save project and demux video which will give you a .m2v file.

In the clip you posted (before ivtc) there are many frames where both the top/bottom field have no matching field in either the previous, current, or next frame. This is partly due to the fact that some fields have chroma that actually belongs to another field. In some places this problem occurs two frames in row. Your field matcher effectively allows discarding the entire current frame and replacing it with the next frame in cases where the current frame is combed... this is able to deal with the case where there is no good match at all for one frame but if it happens twice in a row even it fails (though it would probably work if you allowed replacing with either the next or the prev). For example:

function FieldMatch(clip c) {
global cc = c
global nn = c.DeleteFrame(0)
global pp = c.DuplicateFrame(0)
return ScriptClip(cc, \
"!cc.IsCombedTIVTC(cthresh=12, MI=40) ? cc : " + \
"!nn.IsCombedTIVTC(cthresh=12, MI=40) ? nn : " + \
"!pp.IsCombedTIVTC(cthresh=12, MI=40) ? pp : cc" \
)
}

Using the following script with that version and force film in dgindex gives all clean frames:

mpeg2source()
fieldmatch()

Completely replacing the current frame with either the prev or the next if the current frame is combed and the prev or next is not (as opposed to deinterlacing the current frame) is very risky in terms of creating extra duplicates and jerky motion. Just try the following avs scripts and single step through the stream counting the number of duplicates:

mpeg2source() <= w/ force film
fieldmatch() <= yours from the second post

mpeg2source() <= w/ force film
fieldmatch() <= the one I just posted

mpeg2source() <= w/o force film
tfm(chroma=true)
tdecimate()

The last one has no duplicates and has the least jerky motion (in fact if you remove tdecimate() there are some sets of 5 at 29.97 fps that don't even have one duplicate). However, it also has deinterlaced frames present. In anime/cartoons the jerkiness isn't that noticeable in non-panning scenes, but if you try replacement on panning scenes the jerkiness will be very evident. In the end it is a trade off between jerkiness and clean matches. It would actually be incredibly easy to add a pp option to tfm that would (if the current frame is combed) check to see if either the prev or next came out clean and copy it over instead of deinterlacing. I might add it in the first version along with fixing that bug with micout/pp=0.

edit: this is using the first m2v you posted.

[mwhitlock]

Thanks for the reply. In fact, I had already added the previous-match check before having read your post. I find that the majority of mismatched frames occur on scene changes, so it's okay to replace with the entire previous or next frame because a duplicated frame isn't noticeable at a scene change.

function FieldMatch(clip c) {
global pp = c.DuplicateFrame(0)
global cc = c
global nn = c.DeleteFrame(0)
p2 = pp.SeparateFields()
c2 = cc.SeparateFields()
n2 = nn.SeparateFields()
global pc = Interleave(p2.SelectEven(), c2.SelectOdd()).Weave()
global cp = Interleave(c2.SelectEven(), p2.SelectOdd()).Weave()
global cn = Interleave(c2.SelectEven(), n2.SelectOdd()).Weave()
global nc = Interleave(n2.SelectEven(), c2.SelectOdd()).Weave()
return ScriptClip(cc, \
"!cc.IsCombedTIVTC(cthresh=12, MI=80, blockx=16, blocky=32) ? cc : " + \
"!nn.IsCombedTIVTC(cthresh=12, MI=80, blockx=16, blocky=32) ? nn : " + \
"!cn.IsCombedTIVTC(cthresh=12, MI=80, blockx=16, blocky=32) ? cn : " + \
"!nc.IsCombedTIVTC(cthresh=12, MI=80, blockx=16, blocky=32) ? nc : " + \
"!pp.IsCombedTIVTC(cthresh=12, MI=80, blockx=16, blocky=32) ? pp : " + \
"!cp.IsCombedTIVTC(cthresh=12, MI=80, blockx=16, blocky=32) ? cp : " + \
"!pc.IsCombedTIVTC(cthresh=12, MI=80, blockx=16, blocky=32) ? pc : cc")
}

While I have your attention, you know what would be REALLY useful for your IsCombedTIVTC function? A parameter that controls how many blocks have to exceed MI for the function to return true. Right now, all that can be controlled is the size of the block and the minimum number of combed pixels in the most combed block that is needed to consider the frame combed. But I have a lot of frames where one or two blocks have very many "combed" pixels when the frame itself is not combed. These pixels are simply false positives due to striated textures at just the right distance and orientation from camera. What would be most excellent would be if I could tell IsCombedTIVTC, "only return true if at least 5 16x32 blocks contain at least 80 combed pixels." Could you please add that? Of course the default value for the new parameter would be 1, resulting in exactly the same behavior as current. It's a different logic predicate, though, ("at least x blocks contain at least y combed pixels" instead of "the most combed block contains at least y pixels"), so I think you might have to modify your assembly code to accommodate this request. If you would do that, I, of course, would think you're awesome!

As an afterthought, the reason I hate deinterlacing cartoons is that it causes all the close-to-horizontal lines in the picture to go fat or blurry for a frame, which wastes a lot bits in the video codec and looks pretty shitty.

[tritical]

I'll add the parameter for requiring a number of blocks above MI in the next version. It should only take a few lines of code and won't require changing or adding any assembly code.

[mwhitlock]

I think you're awesome!

[Leak]

My first task was finding a way to tell if any two fields were meant to go together in the same progressive frame. The fields of almost any progressive frame are extremely similar to each other, and when bobbed to correct for the vertical displacement, they're almost identical. Therefore, to tell if two fields belonged to the same progressive frame, I only needed to determine "how identical" they were. The easiest way I found was to difference the two bobbed fields using the Overlay function and examine the value of YPlaneMax() on the result. The magic number for my content was around 235-240: maximum lumas higher than that meant the two fields were definitely not from the same progressive frame.
Maybe it's just me, but this sounds awfully similar to my BlendBob filter (http://forum.doom9.org/showthread.php?t=80289), just using the original fields instead of blending the bobs... :D

Well, the more the merrier as they say... ;)

[Pookie]

Then thanks to all three of you guys :)