[New motion search algorithm] Simulated annealing

[Raere]

Once you tidy up everything, will the patches be merged onto the main x264 tree? I can't wait to use the new stuff all compiled and stuff for us newbs.

[Terranigma]

What's the command for simulated annealing?

[Dark Shikari]

What's the command for simulated annealing?
It'll be --me sau when its done (standing for Simulated Annealing w/ UMH).

[Terranigma]

It'll be --me sau when its done (standing for Simulated Annealing w/ UMH).

OK, thanks. So will it work with this (http://forum.doom9.org/showpost.php?p=1042408&postcount=98) build? He said it's patched with SAU, but i'm unsure it'd even work now because you just said "It'll be --me sau when its done" :p

[Dark Shikari]

OK, thanks. So will it work with this (http://forum.doom9.org/showpost.php?p=1042408&postcount=98) build? He said it's patched with SAU, but i'm unsure it'd even work now because you just said "It'll be --me sau when its done" :pNote what I said about that build:

a) He said there were errors when patching even though it compiled successfully. This probably means its broken.

b) The algorithm, though working, was quite bugged at that point.

I've changed the algorithm so that instead of a single, long SA function, 6 different annealing functions are called in a hexagon formation between 8 and 12 spaces away from the center. The best result from these is then taken, and a 5x5 ESA is run on that location.

Its slow, but to speed it up I've done some very heavy optimization (elimination of branches, etc) along with some early termination code.

[Bulletproof]

Can this be combined with the hadamard transformations?

[Sharktooth]

yes, it can but there's no hurry.

[Dark Shikari]

Can this be combined with the hadamard transformations?
Yes, easily.

[DeathTheSheep]

"6 different annealing functions are called in a hexagon formation between 8 and 12 spaces away from the center."

What if the actual motion is closer to the center than those 8-12 spaces? Will it be ignored?! Or do you mean "in addition to searching near the center" these hexagons will poke around their 12 spaces away and illuminate the big picture?

"I've done some very heavy optimization (elimination of branches, etc) along with some early termination code."
Done? As in past tense? That's pretty interesting...

[Dark Shikari]

"6 different annealing functions are called in a hexagon formation between 8 and 12 spaces away from the center."

What if the actual motion is closer to the center than those 8-12 spaces? Will it be ignored?! Or do you mean "in addition to searching near the center" these hexagons will poke around their 12 spaces away and illuminate the big picture?
First of all, one can expect that at least one of these branches will head towards the center, in all probability. Depending on whether it improves the results, I may run a 7th in the center. I could also run a couple iterations of HEX in the middle.

"I've done some very heavy optimization (elimination of branches, etc) along with some early termination code."
Done? As in past tense? That's pretty interesting...
These are just on my code, nothing else.

[Dark Shikari]

Slight difficulty so far. The problem is that SAU simply isn't good enough with its current algorithm to be useful. Its definitely better and slightly slower than UMH, but look at these graphs and you'll understand the problem:

http://i15.tinypic.com/4uah8hj.png

SAU-SAD is worse and slower than UMH-SATD!

And SAU-SATD is worse than ESA-SAD. :mad:

(I'll find a way to fix this ;) )

[akupenguin]

better graph
http://akuvian.org/images/x264_sau_speed_v_quality_0.png

[Sharktooth]

SATD UMH seems the best compromise between speed and quality. it also scales well.
SAD ESA is also interesting but still slower and "fluctuating".

[*.mp4 guy]

Satd ESA is the most interesting to me, it has a rather impresive total quality increase, it outperforms Sad ESA by an impressive margin aswell. It's too bad that its unusable slow. Satd UMH is probably the most usable option.

[Dark Shikari]

Satd ESA is the most interesting to me, it has a rather impresive total quality increase, it outperforms Sad ESA by an impressive margin aswell. It's too bad that its unusable slow. Satd UMH is probably the most usable option.
The graph uses the old SATD ESA algorithm; the new one is about 2-2.5x faster, so slightly usable.

By the way, I totally trashed the Simulated Annealing algorithm in favor of another one (since I couldn't get SA to work well enough). The new algorithm basically takes advantage of the fact that the HEX ME algorithm is so well optimized, and, well... has fun with that :p

Its relatively near ESA in terms of quality, at least for SAD. Hopefully it'll turn out well for SATD too. Graphs will be up later.

Not sure what to call it: maybe HHH for Hexagon Hexagon Hexagon (Hungry Hungry Hexagons?) Or TMH for Too Many Hexagons? Or MHS for Multi Hexagon Search?

Also note the new algorithm scales somewhat differently; the new portion of the algorithm only scales every 8 --merange, so the only difference between --merange 16 and --merange 23 is the increased size of the UMH search. Technically it does have slight improvements there, as UMH has an adaptive search range that will increase the merange when it thinks its necessary, so a few times it'll go over --merange 24 and activate the next level of the algorithm.

[Dark Shikari]

Updated graph with the new algorithm:

http://i15.tinypic.com/4tjd8i9.png

I need to find a way to make that thing faster :mad:. It isn't bad for SAD, but SATD UMH barely eclipses it. And with SATD, its just too slow, though still vastly faster than ESA.

[check]

is there any reason why some of these functions seem to produce such variable output? It seems to be all the ones based on SAD, but is it some problem that persists across test samples, or just random luck?

[Dark Shikari]

is there any reason why some of these functions seem to produce such variable output? It seems to be all the ones based on SAD, but is it some problem that persists across test samples, or just random luck?Its both. A test sample may have situations in which SAD finds a pretty good match very close-by, and if the motion search is extended far enough, finds another good match that is slightly better quality-wise but much farther away, resulting in the block requiring more bits to encode.

It all boils down to SAD being a mediocre metric.

The source footage I'm using is the scene with all the wires (the running scene) in Elephant's Dream, which might be particularly susceptible to this problem, given the very complex background.

[Sagekilla]

Wow, that kind of explains why SATD ESA has such a higher quality over everything else.. Literally a perfect example of where using a brute force method -can- be worth it.

[Dark Shikari]

Apparently the numbers for SATD UMH were totally wrong; I have no idea why. Here's the graph with corrected numbers, along with my new and improved algorithm.

http://i10.tinypic.com/66bsdox.png

[Sagittaire]

Mind posting to the x264 list for the benefit of those who don't regularly check the forum? (As an aside, Gabriel Bouvigne has recently posted some very interesting b-frame patches there that might interest you.)

Where I can find these patch ?

[foxyshadis]

Original message (http://mailman.videolan.org/pipermail/x264-devel/2007-August/003559.html)
bchanges.diff (http://mailman.videolan.org/pipermail/x264-devel/attachments/20070828/5d798238/attachment.txt)

[Dark Shikari]

Updated graph with some slight improvements to MHS.

http://i6.tinypic.com/5z5107o.png

Note that SAD ESA cannot be multithreaded at the moment; all the others can. The graph is singlethreaded performance.

[foxyshadis]

Odd, the last two graphs appear to have exactly the same datapoints.

[Dark Shikari]

Odd, the last two graphs appear to have exactly the same datapoints.
The change was small, but yeah, I think I forgot to copy/paste the datapoints into the new graph. Fixed.

I have some other possible improvements to MHS upcoming as I change some of the hexagonal searches a slight bit.

If I can do enough elimination I may be able to raise the entire curve up a bit and possibly regain the --merange 32 spike in the older MHS.

[Dark Shikari]

I'm going to shut down this thread for now (maybe it can be locked?) and make a new thread, since I totally redid the algorithm described in the original post and it doesn't even have the same name.

[DeathTheSheep]

I don't think locking is such a good idea (the algorithm still exists and is still linked to!) but splitting into a new thread is the way to go. :cool: