nnedi2/nnedi3/eedi3

[DeathWolf]

For all those getting an error, the version of vcomp needed is not one commonly found, it's a dev version with a security fix.
Here's the good redist to get:
http://www.microsoft.com/downloads/details.aspx?FamilyID=766A6AF7-EC73-40FF-B072-9112BAB119C2&displaylang=en

@tritical: you might want to put that in the readme:)

[tritical]

Thanks for posting that link DeathWolf.

Part of the problem was the first mt version of eedi3 I posted needed the first vs2005 redist, but between that release and this last one I finally got my desktop computer, which has all my avisynth projects, online - about a year after moving. I had just been moving things between it and my laptop with a usb stick as needed. In the process of running windows update it installed sp1 for vs2005 and some other security updates resulting in needing this newer vcomp.dll. Sorry about that.

[Taurus]

@DeathWolf:
Thank you for pointing it out.

@tritical:
Yeah, its working now without errors.

But I think there will be others who will come to complain.
So the readme should be updated as soon as possible.

[kai0n7]

For all those getting an error, the version of vcomp needed is not one commonly found, it's a dev version with a security fix.
Here's the good redist to get:
http://www.microsoft.com/downloads/details.aspx?FamilyID=766A6AF7-EC73-40FF-B072-9112BAB119C2&displaylang=en

@tritical: you might want to put that in the readme:)

That got it working for me, thanks!

[tritical]

@Archimedes

What do you think of this enlargement?

nnedi3_rpow2 (rfactor=4, nsize=0, nns=4, qual=2, cshift="Spline36Resize"), 1600x1200 (http://bengal.missouri.edu/~kes25c/castle_4x_new.png)

[akupenguin]

http://akuvian.org/src/x264/nnedi.tar.bz2
Same algorithm as nnedi3-0.9.1, and about 4x faster (per cputime. I haven't implemented threads).
This is just a C function, not an avisynth filter.
I included only the 8x6 mode because I'm only interested in scaling, not deinterlacing. But I assume the wider modes would benefit from the same optimizations.

Changed:
* Convert much of the float math to fixed-point.
* The max part of softmax was useless. Adding a constant before exp is equivalent to multiplying after, and the weighted average removes any such multiplicative constant.
* Edge mirroring was weird: nnedi3 kept 1 copy of the edge row on 2 sides of the frame, and 2 copies on the other 2 sides. imho 2 looks better.
* And a bunch of assembly optimizations.

@tritical
I have some further optimization ideas, but they would require retraining. Could you post sourcecode for that?
I tried to apply CMAES, and it sorta worked, but wasn't really satisfactory; I don't know if I'm doing something wrong or if I just haven't thrown enough cputime at it.

[tritical]

4x is impressive! Not to mention I guess you figured out the structure from just the dll? I'll admit it isn't the most complicated thing in the world though. I had actually spent some time rolling together separate functions in the prescreener network into one big asm function (to eliminate unneeded function call overhead and memory stores) and a few other minor things and only got maybe 20%. Doing an int16 implementation never crossed my mind. I would think that would only get you 2x faster at best? Then you got another 2x on top of that? And here I thought I knew how to program :p

Anyways, I haven't had time to look at your code in depth or compile it. Hopefully tomorrow or the day after. On the training, I no longer use CMA-ES just basic online gradient descent with a cooling schedule.

Oh, and the mirroring thing is a bug... it should only be keeping 1 copy of the edge row on all sides. On the softmax bit, softmax is invariant to a global offset as you point out. The subtracting out the max of all the net values before computing the exp() of them is simply to make exp() well behaved in training (avoid overflow and maintain accuracy of the softmax output). Definitely could be avoided after training, though I doubt it's taking up much cpu time.

[akupenguin]

I would think that would only get you 2x faster at best? Then you got another 2x on top of that? And here I thought I knew how to program :p
Other improvements:
* I can eliminate the horizontal sum from the end of each dotproduct by shuffling the inputs appropriately. If there were only 1 dotp that would be counterproductive, but with lots of them I can reuse the shuffled inputs and it's a net win.
* The prescreener (once you get past the first round of dotps) was latency bound, and out of order execution can't look far enough ahead to interleave multiple copies of the whole function. Manual interleave helped a bunch. (Just moving the first dotps into a separate loop from the tail of the prescreener also helped somewhat, because then out of order execution could do something. Still far from my end result though.)
* Some more scheduling improvements smaller than the above.
* There's a lot of spatial locality in the prescreener results. I subsampled it and then evaluated the in between samples only when the neighbors disagree. (This might be counterproductive on the really slow modes.)
* Your exp approximation was excessively precise. A 6th order polynomial iirc, whose error was less than floating-point precision. I got away with 2nd order (0.1% rmse).
* Mean removal can be factored into weights for free. (Noticed just now and updated the code.)

Oh, and the mirroring thing is a bug... it should only be keeping 1 copy of the edge row on all sides.
When I tried that, it tended to reverse the direction of diagonal lines that hit the edge of the frame. I'm assuming that's because a diagonal becomes a sharp angle in the mirrored image.

The subtracting out the max of all the net values before computing the exp() of them is simply to make exp() well behaved in training (avoid overflow and maintain accuracy of the softmax output).
Yep, I had to deal with that. (But the risk is only overflow/underflow, not loss of precision. Incrementing a floating point exponent doesn't lose any LSBs.) Still possible to munge the constants instead of the variables if you run the net several times between updates. And I wouldn't expect it to drift out of the allowed range very fast.

[aegisofrime]

@akupenguin and tritical: I assume that what akupenguin posted was the source code? Any chance of a compiled version for consumer usage?

[tritical]

He posted source code for a program that enlarges by 2, not an avisynth plugin. Not sure if he plans to make it one or not. I'm working on implementing some of his optimizations in nnedi3. Specifically, int16 dot products, mean removal factored into the weights, and faster exp function for the prediction neural network. Mean removal factored into the weights for the first stage of the prescreener. I probably wont get to anything else anytime soon, but for larger nsize areas (those besides nsize=0/4) and nns values (> 1) the computation is dominated by the predictor so this should give most of the speed up. Once I finish that I'll release a new version and my source code. I have plans to revamp the prescreener, but may or may not get to it anytime soon. Or someone else might do it first :).

I had also been experimenting with minimizing abs error instead of squared error, the last image I posted of the castle was using weights optimized for abs error. Since all that takes is me waiting for models to train I might add abs error optimized weights at some point.

[aegisofrime]

Thanks for the update tritical! I use NNEDI2 on a daily basis (mainly with TGMC), so having an NNEDI3 competitive speed wise would be great! :)

[Terka]

Tritical,
thank you for all your work!
Will theese speed improvements added to nnedi2 also?

[LoRd_MuldeR]

I had also been experimenting with minimizing abs error instead of squared error, the last image I posted of the castle was using weights optimized for abs error. Since all that takes is me waiting for models to train I might add abs error optimized weights at some point.

I wonder: Did you ever try other metrics than squared/absolute error, like SSIM for example? Or is the "sliding window" approach not suitable for your algorithm?

(BTW: Looking forward for any speed-optimization in NNEDI3)

[tritical]

I did try SSIM, but it's hard to effectively use it within the online gradient descent training scheme because the derivative for a single pixel depends on all of the other pixels within the gaussian weighted window around it. That means I can't calculate a single pixel result and then do gradient descent on the model weights unless I assume a value for all of the missing pixels (those which need to be interpolated by the network) and pre-compute the necessary statistics beforehand (so that during training I only have to modify a few values based on the current result to compute the gradient). What I tried was assuming all of the missing values were perfect... that gave results very close to mse training. The one idea I didn't try was starting by assuming all of the missing values were interpolated using cubic interpolation, and after each iteration (after presenting all of the training cases to the network) recalculating all of the ssim statistics that depend on the missing pixels based on the current state of the network. Like a lot of things I plan to try that in the future.

Now if you're not using online gradient descent (say CMA-ES or a fitness function based optimization) you could just run through the training set, interpolate all the necessary pixels, compute ssim for everything at the end. I actually tried that as well, but it takes A LOT more cpu time. Using online gradient descent I can train the 6x48x256 network on 60 million pixels in only a few days on my quadcore desktop. For nnedi2 I was using separable CMA-ES for training (using the scheme I just described) and to train on 1/5 the pixels was taking about 3x longer while using about 4x the cpu power. And nnedi2 is basically equivalent to 4x12x32 in nnedi3 terms. Those are rough numbers of course.

[LoRd_MuldeR]

Time to start a nnedi@home project :D

[akupenguin]

The one idea I didn't try was starting by assuming all of the missing values were interpolated using cubic interpolation, and after each iteration (after presenting all of the training cases to the network) recalculating all of the ssim statistics that depend on the missing pixels based on the current state of the network. Like a lot of things I plan to try that in the future.
Surely the correct algorithm involves computing the partial derivatives of ssim wrt all of its inputs, not treating the neighboring pixels as constants?

For nnedi2 I was using separable CMA-ES for training (using the scheme I just described) and to train on 1/5 the pixels was taking about 3x longer while using about 4x the cpu power.
Is that measuring just speed of convergence, or weighting by quality of solutions found?

[tritical]

Surely the correct algorithm involves computing the partial derivatives of ssim wrt all of its inputs, not treating the neighboring pixels as constants?

I compute the partial of ssim with respect to the network output, which does depend on neighboring pixel values... some of which are fixed, but some of which depend on the network. I assumed fixed values (from the very beginning of the optimization) for those pixels as well, as a rough, fast approximation. Recalculating the statistics depending on those pixels after each (or every few) complete pass through the training patterns using the current state of the network is more desirable, but I haven't done it yet.

EDIT: The partial of ssim with respect to the network output is only for ssim of the 11x11 gaussian weighted window centered on the current pixel. I'm not explicitly taking into account other ssim windows that depend on the network output at this point.

Is that measuring just speed of convergence, or weighting by quality of solutions found?
Time to equal quality of solution, approximately. In all of my tests gradient descent achieved equal or lower training error in significantly less time. Of course given more time cmaes might do better, but for my time/cpu point gradient descent was much better.

[akupenguin]

BTW, modes with more weights than fit in L1d cache are bottlenecked by cache misses, not arithmetic throughput. I didn't rectify this (except insofar as int16 reduces cache footprint too), but you probably want to if you're tuning for nsize>8x6.

[Forteen88]

@tritical: Could you please make a comparison of NNEDI3, with the same source as these:
http://forum.doom9.org/showthread.php?p=1343668#post1343668
Thanks

[Archimedes]

@Archimedes

What do you think of this enlargement?

nnedi3_rpow2 (rfactor=4, nsize=0, nns=4, qual=2, cshift="Spline36Resize"), 1600x1200 (http://bengal.missouri.edu/~kes25c/castle_4x_new.png)
Looks much better, than with the current version of NNEDI3 with the same parameter.

[yup]

Hi all!
Please explain how work sclip parameter? It is first iteration for finding solution?
yup.

[Skauneboy]

I can't get EEDI3 to work with this AA-function:

o=last
AssumeBFF().SeparateFields()
dbl = mt_Average(SelectEven().EEDI3(field=0),SelectOdd().EEDI3(field=1),U=3,V=3)
dblD = mt_MakeDiff(o,dbl,U=3,V=3)
shrpD = mt_MakeDiff(dbl,dbl.RemoveGrain(11),U=3,V=3)
DD = shrpD.Repair(dblD,13)
dbl.mt_AddDiff(DD,U=3,V=3)

Repair gives the error "clips must be of equal type". It works fine with your other interpolation filters though.

[Didée]

Oops, I don't have eedi3.dll at hand ... give a try if it works with the following change?

dbl = mt_Average(SelectEven().EEDI3(field=0),SelectOdd().EEDI3(field=1),U=3,V=3).AssumeFrameBased()

[Skauneboy]

Thanks for the suggestion Didée but it didn't work. Something awry with the field-parameter of EEDI3? Or perhaps Repair.dll is at fault.

[Didée]

Ah, reading documentation helps. EEDI3 works framebased like NNEDIx, not fieldbased like EEDI2. Try like so:


o=last
AssumeBFF() # should not be needed ...
EEDI3(field=-2)
dbl = merge( selecteven(), selectodd() )
dblD = mt_MakeDiff(o,dbl,U=3,V=3)
shrpD = mt_MakeDiff(dbl,dbl.RemoveGrain(11),U=3,V=3)
DD = shrpD.Repair(dblD,13)
dbl.mt_AddDiff(DD,U=3,V=3)

[Skauneboy]

Ah, that did the trick. :thanks:

[Chainmax]

I did some more comparisons using Gabriel Knight's "Making Of" video:


eedi3_rpow2(rfactor=2,cshift="spline36resize",hp=false)
http://img827.imageshack.us/img827/5200/fr12307eedi3v091.png

nnedi3_rpow2(rfactor=2,nsize=3,nns=4,qual=2,cshift="spline36resize")
http://img137.imageshack.us/img137/8916/fr12307nnedi3v091.png

eedi3_rpow2(alpha=0.3,beta=0,rfactor=2,cshift="spline36resize",hp=true,vcheck=3)
http://img825.imageshack.us/img825/3504/fr12307nnedi3v091try2.png


Original screen batch here (http://forum.doom9.org/showpost.php?p=1356658&postcount=122). In my opinion, on the particular filterchain used for this particular source, the first version of EEDI3 gives the more pleasing results.

[markanini]

Thanks for the comparison chainmax. I'd go with nnedi3 myself in this case but I wouldn't argue with your preference for eedi3 as it's a matter of taste.

I'm eagerly awaiting for Triricals next nnedi3 release.

[Usedocne]

Thanks also Chainmax. I couldn't choose between them though. Each is good on different areas (parts of mic, side of face), but struggle on others. They are pretty much equal imho, in as far as weighing up the positives and negatives effects.

[tritical]

So I finally got back to working on this, and almost have the next nnedi3 release ready... but one question first. Does anyone using this not have an SSE2 capable processor? I'm considering dropping support for SSE/MMX since it's a pain to keep around and test.

[aegisofrime]

So I finally got back to working on this, and almost have the next nnedi3 release ready... but one question first. Does anyone using this not have an SSE2 capable processor? I'm considering dropping support for SSE/MMX since it's a pain to keep around and test.

Those are pretty old CPUs. We are talking about Pentium 3s and Athlon XPs and below... Judging by the processing power of those CPUs, I doubt anyone will use them for NNEDI3...

Of course, this is just my opinion.

[SubJunk]

Welcome back, Tritical. Looking forward to the release. I think you can safely drop SSE/MMX support

[Blue_MiSfit]

I'd say so as well. Anyone doing encoding on a P3 / Athlon XP probably won't mind having to use the previous release - especially if they're willing to tolerate everything else that comes with life on such old CPUs ;)

[mandarinka]

I have one Athlon XP at hand, but I'm okay with requiring SSE2. It is better when you have less obstacles to improve the filter (which I like a lot - I use daa() and the difference nnedi3 made was quite something, thanks!).

[tritical]

I put up the new version. I decided to drop sse/mmx, but v0.9.1 is still available from the old_stuff directory of my website. Changes:

+ clean up and release source code
+ speed improvements - (thanks Loren Merritt - akupenguin - for many ideas and code)
int16 dot products in prescreener/predictor neural networks
faster exp function approximation
mean removal factored into weights
lots of smaller changes
+ new prediction nn weights for certain nsize/nns combinations
+ added fapprox parameter
- fixed bug with border mirroring
- dropped support for sse/mmx - all asm code requires sse2. changed opt parameter accordingly.

The fapprox parameter is a bitmask that lets you switch between int16 and float dot products in the predictor or prescreener (&1 and &2). That part was mainly for testing. It also allows switching between 3 exp function approximations based on bits 2/3 (&12 = 0,4, or 8/12). 0 gets you what I was originally using - exp from intel approximate math library (6th order - slowest, most accurate). 4 gets you the exp from Loren's code (2nd order - faster, slightly less accurate). 8/12 get you an even faster, more inaccurate version. By default the fastest version is used - I couldn't tell any noticeable difference when flipping back and forth between frames when using it (and pixel changes are pretty much +-2 at max). Perhaps someone might want to change that setting.

Hope to have predictor weights trained to minimize abs(error) or sqrt(abs(error)) eventually.

[LoRd_MuldeR]

Thanks for the update!

One thing I noticed: Using NNEDI3_rpow2() with only 'refactor' set will complain that 'fapprox' must be in the [0,7] range.

What 'fapprox' value would you recommend as default for NNEDI3_rpow2() ???

[tritical]

Give me a sec and I'll fix that. Hopefully that's the only bug :).
The default of 15 is what I'd recommend or switching to the slightly slower exp() function - fapprox = 7. I personally can't tell a difference in the final result though. fapprox=0 would technically be the most accurate, but basically disables all of the major optimizations between this version and the last version.

Finished uploading the fix.

[Usedocne]

HUGE thanks tritical and akupenguin. *goes off to speed test TGMC*

[Usedocne]

Here's my TGMC results, if anyone cares:

1000 frames (720x480i)

1m.35s nnedi3 v0.9.2

1m.50s nnedi2 v1.6

2m.28s nnedi3 v0.9.1

[IanB]

@Tritical,

Just for interest it would have been nice to see the MMX/SSE source code before you junked it.

Also do you have any plans to release the source code for nnedi2?

[ajp_anton]

Now that you're back, could you please make a 64-bit version?

[aegisofrime]

Now that you're back, could you please make a 64-bit version?

With the source code released, it should be a lot easier. Somebody with the right skills can just compile a 64-bit version.

[tritical]

@Usedocne
Thanks for testing. What are the times if you use nsize=5 in nnedi3? That is more comparable to nnedi2.

@IanB
I think I still have the v0.9.1 source code around. I can post that, but really it is just the sse2 floating point code in nnedi3 minus any sse2 instructions + the necessary workarounds. nnedi2 is the same as nnedi3 except for some changes to the predictor nn. Specifically:

1.) nnedi2 always used 4x12 neighborhood
2.) nnedi2 didn't scale by the standard deviation of the neighborhood
3.) the second set of neurons (perceptrons) which use the elliott activation function and whose output is multiplied by 5.0 in nnedi3 used the linear activation function (essentially no activation function) in nnedi2.
4.) the first set of neurons which use a softmax activation in nnedi3 were actually the final layer of a three layer feed forward nn in nnedi2 (first two layers used elliott, connection architecture was the same as the prescreener - final layer connected to both previous layers, etc...)

I personally see nnedi2 as completely superseded by nnedi3. I know some people use nnedi2 because it is faster by default, but if you use equivalent settings in nnedi3 (nsize=5 instead of the default nsize=6) they are basically the same speed - and that was with v0.9.1 of nnedi3.

@ajp_anton
I might actually since I now have a computer (a new laptop) which has a 64-bit version of windows. Or if someone else does it first even better.

[Usedocne]

Updated TGMC speed test results:

1000 frames (720x480i)

1m.24s nnedi3-nsize=5 v0.9.2

1m.46s nnedi3-nsize=5 v0.9.1

1m.50s nnedi2 v1.6

[jpsdr]

Out of curiosity, i've tried to compile the source (with Visual Studio 2008), i've got the 6MB binary file. So, when i build the project, it said everything went fine, but... i've not the .dll result file. Has anyone tried to compile ???

[XhmikosR]

Everything works fine here. I built nnedi3 with MSVC2010 and ICL 11. Can someone compare them to the original build speed-wise?
nnedi3_MSVC2010_SSE2 (http://xhmikosr.1f0.de/avisynth/nnedi3_MSVC2010_SSE2.7z)
nnedi3_VS2008_ICL11 (http://xhmikosr.1f0.de/avisynth/nnedi3_VS2008_ICL11.7z)

[jpsdr]

Ok... My mistake, didn't take look on right place...

[aegisofrime]

Is that ICL version still biased against AMD CPUs?

[XhmikosR]

No idea, I don't have an AMD cpu and I don't care about AMD at all :p But it should work on AMD cpus.

[aegisofrime]

No idea, I don't have an AMD cpu and I don't care about AMD at all :p But it should work on AMD cpus.

Oh, I was referring to the whole fiasco of Intel's compiler taking the slower route, so to speak, when it detects a CPUID that is not Intel. It works, but slower than it should be.

Anyway, here's my test. Test content is 1000 frames of 720x480i DVD content, using QTGMC. avs2avi was used in null mode to eliminate encoder as a variable.

The PC's specs are

AMD Phenom II X4 955 @Stock speed, Undervolted @ 1.28V
4GB Corsair DDR2-800 RAM
Windows 7 Ultimate 64


SetMTMode(5,4)
DGDecode_mpeg2source("C:\Work\Test.d2v")
SetMTMode(2,4)
QTGMC(Preset="Slow",EDIMode="NNEDI3")

Distributor()

Trim(0,1000)

tritical's NNEDI3
* Pass 1/1: Finished in 00:00:50.171 (19.95 FPS)
* Frames: 1001 (1001 keyframes)
* Size: 494.88 MB

NNEDI3 ICL11
* Pass 1/1: Finished in 00:00:50.798 (19.71 FPS)
* Frames: 1001 (1001 keyframes)
* Size: 494.88 MB

NNEDI3 MSVC2010
* Pass 1/1: Finished in 00:00:50.607 (19.78 FPS)
* Frames: 1001 (1001 keyframes)
* Size: 494.88 MB

NNEDI2
* Pass 1/1: Finished in 00:00:51.873 (19.30 FPS)
* Frames: 1001 (1001 keyframes)
* Size: 494.88 MB