[New patch] Hadamard motion estimation

[DeathTheSheep]

Hmm, for some reason now there is a disproportionately (?) huge SSIM increase (and filesize decrease) with ESA...

Is there any hope in doubling (just doubling) ESA's effective speed, such as using a refined and more ingeniously optimized SSE2 method? Such as a way of losslessly ruling out mvs similar to, but different from, SEA's incompatible method?

[Dark Shikari]

Hmm, for some reason now there is a disproportionately (?) huge SSIM increase (and filesize decrease) with ESA...

Is there any hope in doubling (just doubling) ESA's effective speed, such as using a refined and more ingeniously optimized SSE2 method? Such as a way of losslessly ruling out mvs similar to, but different from, SEA's incompatible method?
There are a few things that can be done.

1. Optimize the ESA algorithm in a very very mildly lossy manner. For example, do an ESA of 1/4 of the fullpel spaces and save the SATD score for each one, and then rule out all neighbors of the lowest 50% SATD-scoring spaces. Or do an interpolation (like a resizing algorithm) to estimate the SATD scores of the 3/4 of the spaces that were not calculated, and then pick the best 25% and run SATD on them to get the actual result.

2. Do a full Qpel-RD search of the entire ME space, and use the results from that to help programmers optimize UMH into giving more accurate results, as suggested by Aku.

[DeathTheSheep]

I like them both :).

The question is, which is easier to implement? Or which should be done first?

#1 Much faster than ESA now, but very near ESA lossless results. Great in short-term and long term, even if not "optimal" for speed. I like it! :D
#2 Looks better for long-term development and refinement, leading to long-term encoding speed. But I'm not quite sure how to "use" the results to better UMH.

[Dark Shikari]

I like them both :).

The question is, which is easier to implement? Or which should be done first?

#1 Looks like a stopgap measure, but very near ESA lossless results. I like it! :D
#2 Looks better for long-term development and refinement, leading to long-term encoding speed. But I'm not quite sure how to "use" the results to better UMH.
1) could probably be implemented in about 10 minutes :p

I'll open up Notepad++ and see what I can figure out :cool:

Update 1: \o/ Worked on the first compile without compile errors.
Update 2: Simple code explanation so far: it does bilinear interpolation between nearby calculated SATD scores. Note that because I'm lazy, it simply ignores edges at the moment.
Update 3: 90 minutes of debugging and it works. It seems to be pretty good at the moment, but I'm improving it. I've changed the algorithm from the original somewhat.
Update 4: Some speed improvement with some quality loss. I've improved the algorithm (previously it lost easily to UMH) and now its much better than UMH and is slightly worse than ESA. More to come.

[Dark Shikari]

I guess my goal has changed; my new goal is to create an algorithm that is either:

a) Much faster than ESA, slower than UMH, and beats out UMH by a lot.
or
b) Similar speed to UMH, and beats UMH.

:cool:

One idea of mine is to use SAD to decide when to do SATD.

[buzzqw]

hope the best for your quest!

BHH

[DeathTheSheep]

Looks like you're doing both!
I've improved the algorithm (previously it lost easily to UMH) and now its much better than UMH and is slightly worse than ESA.
So right now it's about ESA-level but faster, so level "a)" above.
If you increase the speed to UMH's level, at the expense of quality, you will achieve "b)" above. Maybe split it into 2 versions: Shikari HQ and Shikari Fast. :p

[Dark Shikari]

Looks like you're doing both!

So right now it's about ESA-level but faster.
If you increase the speed to UMH's level, at the expense of quality, you will achieve "b)" above. Maybe split it into 2 versions: Shikari HQ and Shikari Fast. :p
Well the problem is that its not as good as ESA.

Basically the issue with ESA is that I've gotten a bunch of "motion search grids" with SATD scores at each location. You find quickly that the SATD scores don't work by interpolation. For example, you'll have a line that looks like this:

650 350 550 320 540 310 610

You have no way of finding those 3xxs without searching each one.

However, the main possible optimization is in excluding areas of the search; using a very fast, wide search to dump certain areas, and then progressively refining everything else, and at each step of the process dumping the worst area.

[DeathTheSheep]

Yep, that's what I figured. It all comes down to figuring out what not to search (perhaps in multiple iterations), then searching the rest.

Maybe it's too early to ask, but have you made any progress these past 3 hours? :p

[Dark Shikari]

Improved ME algorithm:

1. Do a full SAD ESA.
2. Pick all SADs below a threshold.
3. Run SATD on these locations.

Test material: 1000 frames of ED (running/wires scene) at 640x360 (for faster processing).

All measurements are as compared to --me umh --hadamard.

Threshold:
(Average SAD) - 3 * (Average SAD - Lowest SAD) / 4: 2.05 times faster, exactly the same quality/bitrate as a full ESA.

(And I haven't been working on it for hours straight :p)

Numbers fixed (I made a dumb commandline error before this).

[akupenguin]

(Average SAD) - 3 * (Average SAD - Lowest SAD) / 4: 6% slower, 0.19% better quality/bitrate
14% of the benefit for 7% of the cost compared to ESA.
(Average SAD) - 1 * (Average SAD - Lowest SAD) / 2: 16% slower, 0.3% better quality/bitrate
22% of the benefit for 20% of the cost. not worth much.

[Dark Shikari]

14% of the benefit for 7% of the cost compared to ESA.

22% of the benefit for 20% of the cost. not worth much.
As I just noted in an edit, I made a stupid commandline error so the numbers are being fixed.

[Terranigma]

aku, after Shikari finish working out all the kinks, would there be a chance this'll make it to the svn? :)

[Dark Shikari]

Holy shit :eek::eek::eek::eek:

When correctly testing my modified ESA algorithm for SATD, I got over a 100% speed boost at zero quality cost. :p

[akupenguin]

aku, after Shikari finish working out all the kinks, would there be a chance this'll make it to the svn?
of course.

[Terranigma]

Ok, thanks for the prompt reply. :cool:

[Dark Shikari]

Here's my ESA code if anyone's interested. I'll add it to the patch later.

if(h->param.analyse.i_hadamard)
{
//ESA with SATD can be very very closely approximated by running a full ESA using the SAD metric
//and then picking the best results and running SATD on them. Testing shows that this differs from
//actual ESA by a very, very small amount, while the speed is approximately doubled.
int sadarray[(max_x - min_x) + 1][(max_y - min_y) + 1];
int min=10000000; //Arbitrary large number
int total=0;
//Run an ESA SAD and store the values in an array. Calculate the minimum and average SAD values.
for( my = min_y; my <= max_y; my++ )
{
for( mx = min_x; mx <= max_x; mx++ )
{
sadarray[mx-min_x][my-min_y]=h->pixf.sad[i_pixel]( m->p_fenc[0],\
FENC_STRIDE,&p_fref[(my)*m->i_stride[0]+(mx)], m->i_stride[0] )+BITS_MVD(mx,my);
if(sadarray[mx-min_x][my-min_y] < min){
min = sadarray[mx-min_x][my-min_y];}
total += sadarray[mx-min_x][my-min_y];
}
}
int average = total/((max_y-min_y+1)*(max_x-min_x+1));
int threshold = average-3*(average-min)/4; //This threshold seems to provide reasonable accuracy and speed
//Run ESA search, limited by SAD thresholds
for( my = min_y; my <= max_y; my++ )
for( mx = min_x; mx <= max_x; mx++ )
if(sadarray[mx-min_x][my-min_y] < threshold) COST_MV(mx,my);
}

I ran it again with all debugging variables removed (the code shown here, that is) and the speed was boosted from 2.05x normal ESA speed to 2.27x normal ESA speed with the exact same output.

[DeathTheSheep]

You know what? It's like a miracle or something. I asked earlier:
Is there any hope in doubling (just doubling) ESA's effective speed

And I'll be darned. ;) "2.27 times faster, exactly the same quality/bitrate as a full ESA." Same day, too.

Are you still tweaking it, or is it building time? :D

[Dark Shikari]

You know what? It's like a miracle or something. I asked earlier:


And I'll be darned. ;) "2.27 times faster, exactly the same quality/bitrate as a full ESA." Same day, too.

Are you still tweaking it, or is it building time? :DUpdated patch is uploaded, along with updated code, see the original post.

It wasn't unexpected though; its almost exactly the same concept as the SAD ESA algorithm--use a faster comparison method to eliminate as many possibilities as possible. In this case SAD itself is the faster comparison method, since SATD is so much slower by comparison. The main difference between this algorithm and the SAD algorithm is that the SAD ESA, if I remember correctly, is 100% equivalent to a true ESA, while the SATD ESA I've come up with is very close but not exactly.

[Raere]

So, being just a lowly user of x264, let me get this straight.

The best thing, quality-wise is

--me esa --hadamard --ref 16 ?

With Shikari's ESA patch, it'll be 2.27 times faster than regular ESA? Would it be close to UMH speed at all?

Looking forward to a build with the latest ESA patch, I have no idea how to patch myself.

[Dark Shikari]

So, being just a lowly user of x264, let me get this straight.

The best thing, quality-wise is

--me esa --hadamard --ref 16 ?

With Shikari's ESA patch, it'll be 2.27 times faster than regular ESA? Would it be close to UMH speed at all?

Looking forward to a build with the latest ESA patch, I have no idea how to patch myself.
First of all, it'll be 2.27 times faster than bruteforce ESA using --hadamard. It will still be much slower than not using --hadamard and using --me esa, because the regular ESA algorithm is heavily optimized in a manner that doesn't work for --hadamard.

Its nowhere near the speed of UMH--its still over 50% slower than --me umh --hadamard.

Also, --hadamard --me esa --ref 16 will get you the best results, though you need all the other important commandlines (--subme, --trellis, --bframes, etc).

I would recommend against doing something like --hadamard --me esa --ref 16 unless you are completely batshit insane.

[Sharktooth]

"batshit insane"... thanks! now i have a name for the new insane profile for megui! :D

[Dark Shikari]

"batshit insane"... thanks! now i have a name for the new insane profile for megui! :D
Want to be really insane?

Add --merange 512 to any commandline containing --me esa. Your computer will kill you in aggravation some time between now and the end of the universe.

[DeathTheSheep]

Yeah, I remember doing something like that. I thought something was wrong until my computer...attempted to murder me. Then I knew something was wrong.

But with the patch, instead of getting 0.01fps, I might get just over 0.02. Joy! I can feel the bat shit.

Seriously, I wonder if the patch speeds up ESA proportionally to the merange. I'd assume bruteforce ESA range 128 to be well over 2 times slower than the PSEA ("pseudo-SEA") range 128.

For instance, SAD SEA encodes at 30fps at range 16 and 12fps at range 64. That's well within the same order of magnitude. Bruteforce SATD ESA encodes at 5fps range 16 and 0.44fps at range 64. That's well over an order of magnitude in slowdown.

[Raere]

Thanks Shikari, that makes sense. Will using --umh and --hadamard with, say 10 reference frames yield any quality difference?

i.e. what settings I usually use, but just with hadamard added.

[akupenguin]

@DeathTheSheep
SAD SEA uses a threshold that only eliminates candidates it can guarantee are worse than the best candidate so far. Increasing merange adds a bunch of candidates most of which have bad scores, so most are eliminated.
SATD SEA as presented uses a threshold dependent on the average, not just the best score. So adding lots of bad candidates raises the threshold.
That isn't an answer to your question, but it's the cause behind whatever the answer turns out to be.

[Dark Shikari]

Thanks Shikari, that makes sense. Will using --umh and --hadamard with, say 10 reference frames yield any quality difference?

i.e. what settings I usually use, but just with hadamard added.
Yes, you'll probably get about 1-2% better quality-per-bitrate than normal.

Odds are unless you're encoding anime or the like, that number of reference frames won't be that useful, so if you don't like the speed you can use --ref 6 or --ref 5 or whatever to make up for it.

[Razorholt]

Dark Shikari,

Is --merange a important quality factor with --hadamard? I usually set it to 24.

Thanks,
- Dan

[Sagittaire]

News from rdo for bframe placement ... ?

[Terranigma]

After this is all done with, i'll update and submit my own personal profile for megui. With the custom parameters and tweaks, it might even yield a higher quality than hq-insane; and i'm not even using 16 reference frames. :D

[addit]

Dark Shikari,

Seeing as your tweaking with ESA hows about making it multi-threaded already? :devil:

[Revgen]

Dark Shikari,

Seeing as your tweaking with ESA hows about making it multi-threaded already? :devil:

Multi-threading makes sense after a feature has stabilized. It's better to confirm that it's working before doing anything else.

That being said, did Dark Shikari mention multi-threading wasn't supported?

[akupenguin]

Multithreading isn't supported with the current SAD SEA. It is supported with Shikari's SATD ESA, because it's not SEA.

[Dark Shikari]

Dark Shikari,

Is --merange a important quality factor with --hadamard? I usually set it to 24.

Thanks,
- DanIt does seem to help, but I haven't done enough tests to see if it helps any more than without --hadamard.
News from rdo for bframe placement ... ?
I've been a bit busy, if I manage to get a fade fix done, it won't be RDO, more like a dirty-hack fade detect :p

[Dark Shikari]

Multithreading isn't supported with the current SAD SEA. It is supported with Shikari's SATD ESA, because it's not SEA.
That figures.

Anyways, here's the TODO list given that update:

Short-term TODO (next few days):
* Fix the parameter parser to allow threads with SATD ESA and slightly improve the error message to inform the user that --threads and --me esa without --hadamard causes --me esa to fall back to --me umh. (I'd personally prefer it to keep --me esa and cause --threads to fall back, but that would change the behavior of the program and I'm not sure aku would want it).
* See if I can possibly improve --me umh or --me hex with --hadamard in the same manner that I improved --me esa.

Medium-term TODO (next few weeks):
*Add an ugly fade-detection hack to improve B-frame placement.

Long-term TODO (next few months/if ever):
*B-frame decision RDO?

[Sharktooth]

i guess threads have priority over ESA since ESA is a sort of insane option. no one with a bit of brain would use ESA in place of UMH unless he has a lot of free time...

[DeathTheSheep]

It gives up to 5% extra quality with less bitrate, but takes forever. With DS's patch, it's almost 2.5x faster, though. (Still an insane option? Yep!)

Anyway, I did a bit of testing on the new algorithm at qp 30. With roughly the same filesize:

Non-SEA-thres-tweaked: 0.9613759
New-SEA-thres-tweaked: 0.9611238

Looks like perhaps the threshold should be dynamically adjusted relative to QP used, because the higher ones tend to show more pronounced differences in the two transformations.

[danielkun]

wizboy11's build was prior to the esa me optimization, so I don't think that build was updated, is there any build with the optimizations? 2.27 speed increase is really tempting (even if that is still really slow)

[Dark Shikari]

It gives up to 5% extra quality with less bitrate, but takes forever. With DS's patch, it's almost 2.5x faster, though. (Still an insane option? Yep!)

Anyway, I did a bit of testing on the new algorithm at qp 30. With roughly the same filesize:

Non-SEA-thres-tweaked: 0.9613759
New-SEA-thres-tweaked: 0.9611238

Looks like perhaps the threshold should be dynamically adjusted relative to QP used, because the higher ones tend to show more pronounced differences in the two transformations.
Also note the bitrate when you do the comparison.

Sometimes a change increases bitrate but increases quality, or decreases quality but decreases the bitrate. You can't look at quality alone in testing.

I can definitely make the threshold dynamic--pretty graphs and such testing will probably give me some hints as to what to set the threshold to.

Also, it appears that --me hex/umh/dia will be able to be optimized in the same manner that I optimized ESA, so stay tuned :)

[DeathTheSheep]

Of course. But like I said above: With roughly the same filesize:...

Literally, the files differ by 29 bytes, and x264 reports the same bitrate.

The differences between the two files are very easily spotted, too (put in avi so they can be easily compared with virtualdub):

Test.zip (242KB) (http://gabe.ej.am/test.zip)

Pay close attention to the roofs of the buildings on the left-hand-side as the camera zooms in, especially close to the scene change.

[Dark Shikari]

Of course. But like I said above:

Literally, the files differ by 29 bytes, and x264 reports the same bitrate.

The differences between the two files are very easily spotted, too (put in avi so they can be easily compared with virtualdub):

Test.zip (242KB) (http://gabe.ej.am/test.zip)

Pay close attention to the roofs of the buildings on the left-hand-side as the camera zooms in, especially close to the scene change.
Are you sure you're using the correct build?

None of the builds listed on the front page contain my ESA patch. There are only two options--the faster one, being SATD SEA, which [b]doesn't work[b] and gives bad results.

[DeathTheSheep]

Yes, I'm 100% sure. Finally compiled them myself with MingW GCC4.3 (Aug 24), SSSE3 compatible YASM, pthreads + gpac support, fprofiled, the works...

Yes, the options are identical, but I noticed a speedup with the new repatched ESA, along with the aforementioned quality drop. I'm 100% sure it wasn't a straight SAD SEA search.

Just to make sure, I tried the broken SAD SEA with hadamard: the filesize went up quite a bit and was twice again as fast as your patched ESA (which was over twice as fast as plain exhaustive), but much worse quality than either.

[Dark Shikari]

Yes, I'm 100% sure. Finally compiled them myself with MingW GCC4.3 (Aug 24), SSSE3 compatible YASM, pthreads + gpac support, fprofiled, the works...

Yes, the options are identical, but I noticed a speedup with the new repatched ESA, along with the aforementioned quality drop. I'm 100% sure it wasn't a straight SAD SEA search.

Just to make sure, I tried the broken SAD SEA with hadamard: the filesize went up quite a bit and was twice again as fast as your patched ESA (which was over twice as fast as plain exhaustive), but much worse quality than either.That is quite interesting. Can you upload the source you're using somewhere and post it? I'll test on that and see the results, and try to use that to optimize for a better result.

Also post the encoding settings you're using.

[DeathTheSheep]

Oh, sorry. Baseline defaults but with -m 7 [can't do insane option without an insane setting!] -q 30 [so no bitrate control to skew results] --no-fast pskip [this is just to force analysis of the blocks for pskip, again insane setting] --keyint LARGE# [because keyframes aren't interesting for ME] (--hadamard --me-esa) of course.

The source was downloaded right here (first post, I believe) and relayed to me by gtalk, so I'm pretty sure it has the new esa, especially considering the results. Though I later found it wasn't core2 optimized but a "k8." Oh the irony.

But I'm told different compiler/processor optimizations don't matter for the output.

[Sharktooth]

but it matters for the speed...

[DeathTheSheep]

Yeah, as I thought, else why would they be used, right? (The question is, is a specifically AMD build good for an Intel?)

[Sharktooth]

it will run (if no 3dnow instruction will be in the binaries) but optimizations could hurt the speed since the compiler optimizes the execution for a different CPU.

[akupenguin]

gcc 4.2+ has a -march=core2. But in previous gccs without that, -march=k8 is the best for running on a core2. (And in those versions, -march=k8 is essentially equivalent to not specifying march. Because gcc doesn't actually know how to use 3dnow instructions, and the k8 timings are its default for the x86_64 instruction set.)

However, I'm pretty sure Shikari meant "source" as in video clip.

[Sharktooth]

sorry for the OT, but aku did you happen to have a look at this (http://developer.amd.com/sse5.jsp)?

[burfadel]

sorry for the OT, but aku did you happen to have a look at this (http://developer.amd.com/sse5.jsp)?

That won't be any good to 2009 though, when the CPU support in (AMD Bulldozer) is released. Looks interesting though, a 30 percent speed increase for DCT, and 500 percent increase in certain encryption speeds.