Hadamard Exhaustive Search... what is it?

[Neillithan]

I just updated to the latest version of Avidemux 2.4.1 and it seems as if there is a new option for encoding x264. It's called Hadamard Exhaustive Search. I tried searching the doom9 forum and google, but I didn't get much information about it.

In short, what is it and how is it any different or better?

I would say that my knowledge of video editing is average / intermediate so, bare in mind I'm not a guru at this stuff.

Thanks in advance!

-Neil

[microchip8]

http://en.wikipedia.org/wiki/Hadamard_transform

[Dark Shikari]

Its an even more extreme version of the exhaustive motion search.

<technical explanation>
Normal exhaustive motion search uses a highly optimized sequential elimination algorithm (SEA) to search every single candidate within <merange> pixels of the best predictor. Its about 7 times faster than a naive exhaustive search.

The Hadamard exhaustive search (TESA) attempts to approximate something that would normally be about 70 times slower than the aforementioned SEA; running a SATD (sum of absolute [Hadamard] transformed differences) on each motion vector candidate instead of a much faster SAD. This is more accurate, but much slower. Obviously, if it was actually 70 times slower, it would be totally useless. As such, TESA uses a thresholding algorithm to run SATD on the X best results from the exhaustive search, where X is <merange>/2.
</technical explanation>

Summary: Its about 0.5-1% better than exhaustive, and even slower (about 20-25% slower). :p

[Neillithan]

That's pretty wild. I read somewhere that exhaustive search isn't motion estimation, it's motion calculation... and now Hadamard attempts to improve that. lol.

[foxyshadis]

None of it is really motion estimation or calculation at all, they're just fancy tricks to minimize the residual noise. ESA and TESA can still give motion vectors that are way off the actual movement, they just do a better job of finding the cheapest motion vectors (not the most accurate). Of course, it does roughly correspond with actual motion most of the time.