Fast/realtime HD deinterlacing

[pbristow]

Hi all! Long time, no post. =:o}

Most of the work on deinterlacers (and upscalers) for AVIsynth in the last decade has concentrated on improving quality, and then optimising the performance of the technique afterwards.

In these days of HD and even 4k video, the need for a *fast* de-interlacer is rising again. YADIF is the default choice, as it gives pretty reasonable results for very little computation cost (equals processing time); but it also has some well known problems, and there are other options around...

FFMPEG for example has the Weston 3-field De-interlace Filter (w3fdif), as developed for - and widely used by - the BBC. Based on the papers describing it, this should be computationally cheaper (and thus faster) than YADIF, yet I don't notice a speed boost when using it in FFMPEG... That's probably 'cos the deinterlace step is swamped by the x264 encoding step (though it may also be that their W3fdif implementation hasn't been as carefully optimised as their YADIF).

However, it occurs to me that w3fdif would be more useful in the context of some complex Avisynth scripts, for example those involving motion estimation, where what is needed is a "quick and dirty" conversion to progressive form, but one that's less twittery than the built-in dumb Bob().

Other "low cost" options exist as well, such as the Zhao/de Haan technique described here:
http://www.ics.ele.tue.nl/~dehaan/pdf/114_ISCE_05

Basically, it's a motion-adaptive technique that uses a Weston-style static TF interpolator as a bridge to smooth the crossover between simple temporal interpolation (on static scenes) and purely spatial interpolation (on high-motion scenes). Since all three of the underlying techniques are low-cost (computation wise), the worst-case cost should be the sum of whichever two techniques are being mixed at the time, plus the cost of the motion estimator (which is itself a very simple one). - So it should end up about as fast YADIF, I think, maybe a little slower, but *possibly* with better results.

Has anyone ever tried implementing Zhao/de Haan in AVisynth? Or even just porting w3fdif over from FFMPEG, so that we could then build a script to implement Zhao/de Haan and see how it performs?

[EDIT:] On re-reading the paper more carefully, I realised what I've described above is actually Selby's method, which they describe before going on to propose their own refinement of it. Still, I'd like try out Selby's technique (which *could* be prototyped in a script), as well as Zhao/de Haan. =:o}

[wonkey_monkey]

FFMPEG for example has the Weston 3-field De-interlace Filter (w3fdif), as developed for - and widely used by - the BBC. Based on the papers describing it

Are these papers available online anywhere?

[richardpl]

FFMPEG for example has the Weston 3-field De-interlace Filter (w3fdif), as developed for - and widely used by - the BBC. Based on the papers describing it, this should be computationally cheaper (and thus faster) than YADIF, yet I don't notice a speed boost when using it in FFMPEG... That's probably 'cos the deinterlace step is swamped by the x264 encoding step (though it may also be that their W3fdif implementation hasn't been as carefully optimised as their YADIF)
Reason is simple, no SIMD have been written.

[pbristow]

Ooh, Sorry, forgot to put that link in.

Here's the European patent paper, that seems to be the clearest:
https://data.epo.org/publication-server/pdf-document?pn=0266079&ki=B1&cc=EP

When I get my next spare five-minutes-that-will-probably-stretch-to-six-hours [GRIN], I want to throw together a version in a script and play with it. It basically boils down to adding a convolved version of the previous and next fields - like a sharpener taken to infinity, so there are no DC components left - and then adding that to a dumb bob of the current frame.... But then extracting just the newly created lines and re-weaving them into the originals. So the bobbed output has the static or near-static (low temporal frequency) components drawn purely from the current frame (spatially interpreted), while the rapidly changing (high temporal frequency) components are enhanced by detail taken from the previous and following frames.

But of course, a plug-in would be much more efficient.. [NERVOUSLY EYES THE OLD MS "VIRTUAL C++" INSTALLATION ON HIS HARD DRIVE THAT NEVER SEEMS TO WANT TO PLAY NICE]...

[scharfis_brain]

that already has been implemented years ago by DOnald Graft.
It is called kerneldeint or kernelbob.

Don't expect miracles though. It reduces shimmering at the expense of high frequency ghosting and weird scene change artifacts.

[pbristow]

that already has been implemented years ago by Donald Graft.
It is called kerneldeint or kernelbob.

Ah! Is that definitely using the Weston kernels & coefficients, or just something similar? (There's a whole class of possible similar VT filters with static coefficients, of course).

[GOES TO READ UP ON KernelDeint/Bob]

Don't expect miracles though. It reduces shimmering at the expense of high frequency ghosting and weird scene change artifacts.

[NODS] The scene change issue gets mentioned in the discussions I've read, and people suggest adding a scene-change detector that either (a) drops back to a dumb bob for the two frames immediately either side of the cut, or (b) just uses detail enhancement from the preceding/following frame only (as appropriate).

[wonkey_monkey]

Well.

I won't pretend to begin to understand how the evil geniuses at the BBC (and presumably people before them) boiled a deinterlacer down to a few coefficients, but I will just say: done.

Download here: w3fdif (http://horman.net/avisynth/download/w3fdif.zip) (very beta)

Okay, not quite done, this is very much a proof-of-concept only and has the following caveats:


It's slow (it runs at 50fps on PAL SD material in full colour on my 2.2Ghz i7, but that's still a lot slower than it could be) - give me time and I'll redo it in multi-threaded x87 assembler
It only works on YV12, and only returns the Y channel (though with the helper function below it will work on anything)
It only works on TFF (if you've got BFF, flipvertical before and after)
It implements only the "complex" profile from the paper, not the "simple" one (which would be quicker)


Here's a helper function to see it working in full colour (relies on naive colourspace changes, very inefficient)

function w3fdif_colour(clip a) {
b=a.converttorgb

red=b.showred("yv12")
grn=b.showgreen("yv12")
blu=b.showblue("yv12")

red=red.w3fdif
grn=grn.w3fdif
blu=blu.w3fdif

return mergergb(red,grn,blu).converttoyv12
}


And now I'm finally going to sleep.

Edit:

that already has been implemented years ago by DOnald Graft.
It is called kerneldeint or kernelbob.

Ah. Crap. Oh well. I enjoyed coding it.

[pbristow]

Just looked at the KernelDeint source code: The coefficients there are definitely the Weston ones, so the core of KernelDeint is indeed the same as w3fdif. The surrounding motion masking isn't part of Weston, however, nor does it look to be Snell's "bridging" approach. I haven't decyphered Zhao/de Haan enough yet to compare it to KernelDeint's code, so *maybe* it's that (though at first glance the code looks too brief for that), or maybe it's DG's own additions...?

[pbristow]

Ah. Crap. Oh well. I enjoyed coding it.

[GRIN]

And I enjoyed your sig video. =;o}

[wonkey_monkey]

[GRIN]

And I enjoyed your sig video. =;o}

Ah, so some good came of this. :) Edited with Avisynth and various plugns (spot the morphs). And don't forget part two: https://www.youtube.com/watch?v=cg_-8jSw918

[richardpl]

that already has been implemented years ago by DOnald Graft.
It is called kerneldeint or kernelbob.

Don't expect miracles though. It reduces shimmering at the expense of high frequency ghosting and weird scene change artifacts.

FFmpeg have both kerndeint and w3fdif filter and they are different.

[videoh]

or maybe it's DG's own additions...? Yes, it was added simply to avoid deinterlacing progressive frames (or frame areas) just as done for the ancient VirtualDub Smart Deinterlace filter. It's a poor man's adaptive deinterlacing. :)

I have some old notes on this stuff if anyone is interested:

http://rationalqm.us/misc/journal2003.html

[wonkey_monkey]

For what's it worth, I've updated the plugin (same link (http://horman.net/avisynth/download/w3fdif.zip)) to include a slightly wider-searching version of Yadif's simple EDI spatial interpolation. It does introduce some pixel artefacts.

Am I actually achieving anything or can I go back to my previous project? ;)

[feisty2]

anyone tried RemoveGrain (mode=13-16)?
those are fast deinterlacers

[pbristow]

Am I actually achieving anything or can I go back to my previous project? ;)


Well, I haven't had a chance to play with either version yet, but... [SAVES NEW VERSION NEXT TO "VERY_BETA", as "VERY_BETA2"... =;o}

And having just got in from work, I won't be doing much testing tonight as I plan to get totally rat-arsed and swear a lot. (There may also be some heavy metal involved. Or at least some lightweight progressive alloy with heavy ambitions.)

I've got some useful "fine detail moving against static background" test clips from, would you believe it, the BBC Parliament Channel (which broadcasts in 544x576 resolution, interlaced, for a highly anamorphic 16:9 aspect ratio). Some of the MPs (especially the Lords) wear the most outrageous ties, probably for the sole purpose of distracting the home viewer from what they're saying with all their dancing moire-patterns... =;o}

In summary: Don't put yourself out just for li'l ol' me; But if you're having fun, don't let me stop you, and I'll look forward to seeing what you come up with.

[pbristow]

I have some old notes on this stuff if anyone is interested:


Thanks for that. =:o}