[New patch] Hadamard motion estimation

[Dark Shikari]

This patch adds the --hadamard option, which uses a a Hadamard-transform-based motion search instead of SAD (Sum of Absolute Differences). Basically what this option does is use SATD everywhere that SAD is currently used. Depending on the motion search and reference frame settings, this has a varying effect on quality and speed. Its probably equivalent to the Microsoft VC-1 codec "Hadamard" option.

On --me hex with few reference frames, the slowdown could be very small, while on --me umh with a whole bunch of reference frames the slowdown can be well over 50%. I would recommend using this option particularly when you find yourself using very large numbers of reference frames; it is probably a lot better to use --hadamard and --ref 6 than --ref 16.

In terms of code, since I couldn't quickly think up a simple way of dynamically swapping the metric functions in the motion estimation functions themselves without using tons of if statements (which would cause a speed decrease even with --hadamard off!), I took the hackish approach of directly messing with pixel.c. This technically means that any function calling SAD is actually calling SATD. Fortunately, this doesn't seem to cause a problem, and works as far as I can tell.

It raises quality a small amount. Bitrate is sometimes raised, sometimes lowered; it depends on the sound. If --hadamard is compared with a normal encode at the same bitrate, by using ABR instead of CRF mode, the quality (SSIM) boost ranges from very little to as high as 2.5% depending on the source and the settings. PSNR usually, though not always, increases.

Get the patch here (http://tjhsst.edu/~jgarrett/hadamard.diff). Its for version 667b but should work for anything after (hopefully).

Update: Diff has been fixed so it can be run from the x264 source directory like it should be able to. Use patch -u -p1 <hadamard.diff

For those who can't get the patch to work, I patched the code myself and uploaded it here (http://tjhsst.edu/~jgarrett/x264_667b_AQ_Hadamard.7z). This is Cef's code so it includes all the other patches.

Update: we now have builds with the patch thanks to Wiz!

Uploaded the builds for everyone.
All builds are based off of Cef's 667b so they have all patches he uses (including AQ)
And since I aim to please, I've uploaded a few different versions although the speed difference should be minimal but you should download the appropriate build for your processor.
x264 generic (http://www.sendspace.com/file/2jl2w0) (generic build with mmx)
x264 P3 (http://www.sendspace.com/file/suxa6e) (generic build with mmx+sse)
x264 Pentium4 (http://www.sendspace.com/file/oq5jdy) (mmx, sse, sse2, tuned for pentium4)
x264 K8 (http://www.sendspace.com/file/v8idrx) (mmx, sse, sse2, tuned for k8)
Last but not least, experimental Core2 build (with -mssse3), built with GCC 4.3
x264 Core2 (experimental) (http://www.sendspace.com/file/pyi74g) (mmx, sse, sse2, sse3, ssse3, tuned for core2)

Built with GCC 4.2.1 (latest stable version) with avis input, mp4 output and pthreads (i.e. the only options that really matter to most end users... :))

Only had to add one more CFLAG to it. I built it with the -march=pentium2 to enable MMX support (since I think all the CPUs everyone uses here have MMX and the difference between MMX and the additional SSE+ ones are like 1% since most of it (the important stuff) is written in ASM anyway.

From Sharktooth:

I built it with most of those, march=pentium2 with -mmmx is redundent.
finline functions I believe is activated with -O3 so also redundent.
-funroll-loops I didn't add since I really don't know if it makes it faster or not. Most of the time this can bloat code. However in certain circumstances it can make code faster. I wanted to keep it simple so I didn't add it and it can vary from computer to computer.
ffast-math and -fomit-frame-pointer were also added (already there).

Also, all builds have two additional LDFLAGS to the default x264 ones. -Wl,-O1 and -Wl,--sort-common.

Enjoy.
Another update: a build with a fixed ESA algorithm, which works with --hadamard (--hadamard off it is unchanged) has been compiled by wiz. --me esa --hadamard is very very slow but will blow away any other motion estimation.
Do I need to recompile it again?

Edit:
Here:
x264 Hadamard fixed ESA build 667b x86 (32 bit) Generic (http://www.sendspace.com/file/h36ua8) (mmx support needed)

Too lazy right now to do like 5 builds. And I can't get the stupid 64bit compiler to work.
Another update: ESA with --hadamard is now about 2.27 times faster. It isn't 100% equivalent to the actual ESA algorithm, but all differences in terms of quality/bitrate are within an absolutely miniscule margin of error.

[akupenguin]

Its probably equivalent to the Microsoft VC-1 codec "Hadamard" option.
I care about matching ffmpeg much more than matching VC-1, so call it "--cmp satd" (the default of course being "--cmp sad").

In terms of code, since I couldn't quickly think up a simple way of dynamically swapping the metric functions in the motion estimation functions themselves without using tons of if statements (which would cause a speed decrease even with --hadamard off!)

You had almost the right idea, see pixf.mbcmp[]. Just give it a new set of variables and don't overwrite sad.


cosmetics:
The accepted diff format everywhere I code is -u, not -c.
No hard tabs.

[Dark Shikari]

You had almost the right idea, see pixf.mbcmp[]. Just give it a new set of variables and don't overwrite sad.

Explain--how do I, in me.c, dynamically tell the program to use satd instead of sad? Wouldn't I still need if statements? I.e.:


int cost;
if(p->analyse.hadamard) cost = h->pixf.satd[i_pixel]( m->p_fenc[0], FENC_STRIDE, &p_fref[(my)*m->i_stride[0]+(mx)], m->i_stride[0] ) + BITS_MVD(mx,my);
else
cost = 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);
instead of
int cost = 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);
?

cosmetics:
The accepted diff format everywhere I code is -u, not -c.
No hard tabs.Well the hard tabbing is easy to fix, as is the diff. A search and replace should resolve that.

[akupenguin]

int cost = h->pixf.fpelcmp[i_pixel]( m->p_fenc[0], FENC_STRIDE, &p_fref[(my)*m->i_stride[0]+(mx)], m->i_stride[0] ) + BITS_MVD(mx,my);

where pixf.fpelcmp is initialized either to pixf.sad or pixf.satd, in mbcmp_init().

[Dark Shikari]

int cost = h->pixf.fpelcmp[i_pixel]( m->p_fenc[0], FENC_STRIDE, &p_fref[(my)*m->i_stride[0]+(mx)], m->i_stride[0] ) + BITS_MVD(mx,my);

where pixf.fpelcmp is initialized either to pixf.sad or pixf.satd, in mbcmp_init().
Fixed, fixed, and fixed. Try it now, I totally rewrote the patch using your better method.

[Terranigma]

This is interesting. Last night while playing with the mainconcept h.264 avc encoder, I noticed this option; so I read the .pdf document to get a better understanding and it said:
This is an optimized cosine transformation. Activating the option, the clip will be encoded in better quality, and it will have a smaller file size So today, I was going to ask that this be implemented, but there's no need for me to do that now. Hopefully this'll make it in the next revision. :D

[Dark Shikari]

This is interesting. Last night while playing with the mainconcept h.264 avc encoder, I noticed this option; so I read the .pdf document to get a better understanding and it said:
So today, I was going to ask that this be implemented, but there's no need for me to do that now. Hopefully this'll make it in the next revision. :D
x264 already uses the Hadamard transformation as part of the subpixel refinement process. The reason it doesn't normally use it for the fullpel search is because its quite a bit slower, and if you're trying to optimize speed with quality (--subme 6, --me hex, etc) rather than trying to squeeze out every last bit of quality (--subme 7, --me umh, etc), using the Hadamard transform on the fullpel search would be a comparative waste of time.

One possibility would be to come up with some adaptive method of switching between them, as exists in VC-1. This would require a bit more code but could offer a nice compromise between --hadamard and the normal mode.

My tests do suggest that --hadamard with --ref 3 or 4, --subme 7, --no-fast-pskip, and --me umh might stay above 1 FPS on the MSU test system, so this patch could be used on the upcoming codec competition.

It would be nice to get a good make fprofiled, AQ-patched build with --hadamard if anyone here is up to the task.

[Sharktooth]

A fast generic build can be obtained using:

- GCC ver. 3.4.x

- pthreadw32

- cflags: -march=pentium2 -mmmx -O3 -finline-functions -funroll-loops -ffast-math -fomit-frame-pointer (some of them may be redundant)

- make fprofiled

Note: i also used to compile pthread AND gpac libs with -O3 -march=pentium2 -fomit-frame-pointer etc...

[TheRyuu]

common/pixel.c: In function 'x264_pixel_init':
common/pixel.c:643: error: expected ';' before 'pixf'
make: *** [common/pixel.o] Error 1

Compile error.

[Dark Shikari]

Oops, I accidentally deleted a single semicolon while editing the diff. C'mon you can fix that :p

pixf->satd_x3[PIXEL_8x8] = x264_pixel_satd_x3_8x8_ssse3;

is the correct line instead of

pixf->satd_x3[PIXEL_8x8] = x264_pixel_satd_x3_8x8_ssse3


The one-byte-differing diff has been re-uploaded ;)

[ChronoCross]

it's been awhile since I did patching so forgive me if this is stupid.

Here's the errors I got



$ patch -u -p1 <hadamard.diff
patching file `common/common.c'
Hunk #2 succeeded at 432 with fuzz 1 (offset -10 lines).
Hunk #3 succeeded at 889 (offset -13 lines).
patching file `common/pixel.c'
Hunk #1 succeeded at 322 (offset -8 lines).
Hunk #3 succeeded at 546 (offset -10 lines).
Hunk #4 FAILED at 579.
1 out of 5 hunks FAILED -- saving rejects to common/pixel.c.rej
patching file `common/pixel.h'
patching file `encoder/encoder.c'
Hunk #1 succeeded at 552 (offset -8 lines).
patching file `encoder/me.c'
patching file `x264.c'
Hunk #2 succeeded at 393 (offset -7 lines).
patching file `x264.h'
Hunk #1 succeeded at 214 (offset -1 lines).



***************
*** 511,520 ****
pixf->satd[PIXEL_16x16]= x264_pixel_satd_16x16_sse2;
pixf->satd[PIXEL_16x8] = x264_pixel_satd_16x8_sse2;
pixf->satd[PIXEL_8x16] = x264_pixel_satd_8x16_sse2;
pixf->satd[PIXEL_8x8] = x264_pixel_satd_8x8_sse2;
pixf->satd[PIXEL_8x4] = x264_pixel_satd_8x4_sse2;

//#ifdef ARCH_X86
pixf->sad_x3[PIXEL_16x16] = x264_pixel_sad_x3_16x16_sse2;
pixf->sad_x3[PIXEL_16x8 ] = x264_pixel_sad_x3_16x8_sse2;

--- 579,600 ----
pixf->satd[PIXEL_16x16]= x264_pixel_satd_16x16_sse2;
pixf->satd[PIXEL_16x8] = x264_pixel_satd_16x8_sse2;
pixf->satd[PIXEL_8x16] = x264_pixel_satd_8x16_sse2;
pixf->satd[PIXEL_8x8] = x264_pixel_satd_8x8_sse2;
pixf->satd[PIXEL_8x4] = x264_pixel_satd_8x4_sse2;
+
+ pixf->satd_x3[PIXEL_16x16]= x264_pixel_satd_x3_16x16_sse2;
+ pixf->satd_x3[PIXEL_16x8] = x264_pixel_satd_x3_16x8_sse2;
+ pixf->satd_x3[PIXEL_8x16] = x264_pixel_satd_x3_8x16_sse2;
+ pixf->satd_x3[PIXEL_8x8] = x264_pixel_satd_x3_8x8_sse2;
+ pixf->satd_x3[PIXEL_8x4] = x264_pixel_satd_x3_8x4_sse2;
+
+ pixf->satd_x4[PIXEL_16x16]= x264_pixel_satd_x4_16x16_sse2;
+ pixf->satd_x4[PIXEL_16x8] = x264_pixel_satd_x4_16x8_sse2;
+ pixf->satd_x4[PIXEL_8x16] = x264_pixel_satd_x4_8x16_sse2;
+ pixf->satd_x4[PIXEL_8x8] = x264_pixel_satd_x4_8x8_sse2;
+ pixf->satd_x4[PIXEL_8x4] = x264_pixel_satd_x4_8x4_sse2;

//#ifdef ARCH_X86
pixf->sad_x3[PIXEL_16x16] = x264_pixel_sad_x3_16x16_sse2;
pixf->sad_x3[PIXEL_16x8 ] = x264_pixel_sad_x3_16x8_sse2;

[Dark Shikari]

Can't think of anything that would cause that--it could be that your source isn't the same as my source, since the source I used is patched, for Cef's build.

It should be obvious what the patch is changing though in that case, hopefully. You can always download my 7z'd source.

[ChronoCross]

Can't think of anything that would cause that--it could be that your source isn't the same as my source, since the source I used is patched, for Cef's build.

It should be obvious what the patch is changing though in that case, hopefully. You can always download my 7z'd source.

ah......then it's not svn compatible. I must have misread. Thanks

[Dark Shikari]

ah......then it's not svn compatible. I must have misread. ThanksCef's source does include the SVN metadata, but you'll probably have to slightly modify the patch to fit a totally unpatched source set.

It shouldn't be hard to get it to work on SVN though.

[TheRyuu]

Alright, finally got the dam thing built.
Luckily the missing ";" was the only problem.

Uploaded the builds for everyone.
All builds are based off of Cef's 667b so they have all patches he uses (including AQ)
And since I aim to please, I've uploaded a few different versions although the speed difference should be minimal but you should download the appropriate build for your processor.
x264 generic (http://www.sendspace.com/file/2jl2w0) (generic build with mmx)
x264 P3 (http://www.sendspace.com/file/suxa6e) (generic build with mmx+sse)
x264 Pentium4 (http://www.sendspace.com/file/oq5jdy) (mmx, sse, sse2, tuned for pentium4)
x264 K8 (http://www.sendspace.com/file/v8idrx) (mmx, sse, sse2, tuned for k8)
Last but not least, experimental Core2 build (with -mssse3), built with GCC 4.3
x264 Core2 (experimental) (http://www.sendspace.com/file/pyi74g) (mmx, sse, sse2, sse3, ssse3, tuned for core2)

Built with GCC 4.2.1 (latest stable version) with avis input, mp4 output and pthreads (i.e. the only options that really matter to most end users... :))

Only had to add one more CFLAG to it. I built it with the -march=pentium2 to enable MMX support (since I think all the CPUs everyone uses here have MMX and the difference between MMX and the additional SSE+ ones are like 1% since most of it (the important stuff) is written in ASM anyway.

From Sharktooth:
- cflags: -march=pentium2 -mmmx -O3 -finline-functions -funroll-loops -ffast-math -fomit-frame-pointer (some of them may be redundant)

I built it with most of those, march=pentium2 with -mmmx is redundent.
finline functions I believe is activated with -O3 so also redundent.
-funroll-loops I didn't add since I really don't know if it makes it faster or not. Most of the time this can bloat code. However in certain circumstances it can make code faster. I wanted to keep it simple so I didn't add it and it can vary from computer to computer.
ffast-math and -fomit-frame-pointer were also added (already there).

Also, all builds have two additional LDFLAGS to the default x264 ones. -Wl,-O1 and -Wl,--sort-common.

Enjoy.

[Dark Shikari]

Sweet, thanks a lot :cool:

I have to try these builds now :)

[LoRd_MuldeR]

The "x264 Core2 (experimental)" build seems to work fine on my Core 2 Quad (WindowsXP x64)

[TheRyuu]

The "x264 Core2 (experimental)" build seems to work fine on my Core 2 Quad (WindowsXP x64)

Well, it should for the most part work. Only reason I marked it as experimental is it was built using a "Stage 1" GCC 4.3 which may not be the most stable compiler in the world.
I only put the different CPU builds out to help "please" everyone but the only real difference should be like 1-2% between the different builds.

[Cef]

I made a 64 bit (http://mirror05.x264.nl/Cef/force.php?file=./x264_x64_hadamard.7z) one, in case anyone needs.

[Kurth]

Well I have an AMD Athlon X2 4000+ Brisbane and I tried two builds with the same config the only diference is the --hadamard command.

The video is Japanese Anime.

x264 build 671 from http://x264.nl/

encoder commandline:
--crf 18 --keyint 300 --min-keyint 30 --ref 4 --mixed-refs --no-fast-pskip --bframes 3 --b-pyramid --b-rdo --bime --weightb --subme 6 --trellis 1 --analyse all --8x8dct --me umh --threads auto --thread-input --progress --no-dct-decimate --output "E:\Video.mkv" "E:\Video.avs"

avis [info]: 704x400 @ 30.00 fps (3038 frames)
x264 [info]: using cpu capabilities: MMX MMXEXT SSE SSE2 3DNow!
x264 [info]: slice I:77 Avg QP:15.79 size: 17806 PSNR Mean Y:70.93 U:77.83 V:76.52 Avg:71.33 Global:53.77
x264 [info]: slice P:2307 Avg QP:15.96 size: 10602 PSNR Mean Y:51.21 U:54.28 V:53.11 Avg:51.71 Global:49.54
x264 [info]: slice B:654 Avg QP:19.61 size: 4581 PSNR Mean Y:49.92 U:53.83 V:52.39 Avg:50.55 Global:46.65
x264 [info]: mb I I16..4: 57.0% 40.7% 2.3%
x264 [info]: mb P I16..4: 8.6% 17.0% 0.7% P16..4: 41.3% 11.1% 5.2% 0.2% 0.1% skip:15.8%
x264 [info]: mb B I16..4: 0.1% 0.5% 0.1% B16..8: 30.6% 1.8% 6.3% direct: 6.2% skip:54.4%
x264 [info]: 8x8 transform intra:62.0% inter:72.2%
x264 [info]: ref P 89.5% 7.1% 2.3% 1.1%
x264 [info]: ref B 83.4% 12.1% 2.8% 1.8%
x264 [info]: SSIM Mean Y:0.9938007
x264 [info]: PSNR Mean Y:51.435 U:54.782 V:53.548 Avg:51.955 Global:48.794 kb/s:2277.12
encoded 3038 frames, 12.84 fps, 2277.28 kb/s
desired video bitrate of this job: 18 kbit/s - obtained video bitrate (approximate): 2280 kbit/s

AVInaptic DRF analysis Average DRF 16.742922

x264 hadamard K8 build

encoder commandline:
--crf 18 --keyint 300 --min-keyint 30 --ref 4 --mixed-refs --no-fast-pskip --bframes 3 --b-pyramid --b-rdo --bime --weightb --subme 6 --trellis 1 --analyse all --8x8dct --me umh --threads auto --thread-input --progress --no-dct-decimate --output "E:\Video1.mkv" "E:\Video.avs" --hadamard

avis [info]: 704x400 @ 30.00 fps (3038 frames)
x264 [info]: using cpu capabilities: MMX MMXEXT SSE SSE2 3DNow!
x264 [info]: slice I:83 Avg QP:15.58 size: 16745 PSNR Mean Y:70.38 U:78.42 V:77.06 Avg:70.92 Global:54.16
x264 [info]: slice P:2310 Avg QP:15.84 size: 10417 PSNR Mean Y:51.33 U:54.36 V:53.12 Avg:51.80 Global:49.63
x264 [info]: slice B:645 Avg QP:19.79 size: 4741 PSNR Mean Y:49.73 U:53.50 V:52.12 Avg:50.27 Global:46.60
x264 [info]: mb I I16..4: 57.9% 39.9% 2.1%
x264 [info]: mb P I16..4: 8.4% 15.9% 0.6% P16..4: 41.2% 12.2% 5.0% 0.2% 0.1% skip:16.4%
x264 [info]: mb B I16..4: 0.1% 0.6% 0.1% B16..8: 30.9% 1.9% 6.3% direct: 6.4% skip:53.6%
x264 [info]: 8x8 transform intra:61.0% inter:73.0%
x264 [info]: ref P 90.2% 6.7% 2.1% 1.0%
x264 [info]: ref B 83.6% 12.0% 2.7% 1.7%
x264 [info]: SSIM Mean Y:0.9938760
x264 [info]: PSNR Mean Y:51.509 U:54.834 V:53.562 Avg:52.000 Global:48.848 kb/s:2252.37
encoded 3038 frames, 6.22 fps, 2252.53 kb/s
desired video bitrate of this job: 18 kbit/s - obtained video bitrate (approximate): 2255 kbit/s

AVInaptic DRF analysis Average DRF 16.675444

File encoded with build 671 from http://x264.nl/
Size: 28.193 KB

File encoded with hadamard K8 build
Size: 27.888 KB

The hadamard option is really slow but it got better quality and used less bitrate.

[gigah72]

i have a core duo t2300 and use the core2 build, but sse3 is not listed in the cpu capabilities info.
is this normal?

[slavickas]

i have a core duo t2300 and use the core2 build, but sse3 is not listed in the cpu capabilities info.
is this normal?

coz its core duo, not core 2 duo

[DeathTheSheep]

Size and quality increases are reversed when using an exhaustive search. This was the case with x264-satd-opt in the past, as well.

The real question is, why is this the case? You mentioned SATD being non-optimal for centering an exhaustive search around.
I'll venture to guess the reason: SAD-Opt is not always the best way of picking what block to center a short-range, high-precision search around. I'm guessing that an exhaustive search has a tendency to find blocks that otherwise wouldn't be looked at but just happen to have a decent SSIM, resulting in a bad high-precision search.

Oh the irony!

To check my theory, try comparing a SAD-Opt ESA and SAD-Opt UMH encode... see which is better! If the UMH is actually better, that would be quite interesting.
Here SSIM isn't factored into the equation, but the results still exhibit that strange pattern. (Recall ESA is intended to be the best method, and that akupenguin uses it to measure how much worse the other algorithms are from it.) Are there any other theories?

[Dark Shikari]

Size and quality increases are reversed when using an exhaustive search. This was the case with x264-satd-opt in the past, as well.

The real question is, why is this the case? You mentioned SATD being non-optimal for centering an exhaustive search around.Yeah, that has always been strange, especially as SATD itself is a very tried-and-true method, unlike my whole SSIM bit.

Here's my explanation. The encoder, when doing a hex search, for example, looks around in a hexagon pattern for the best block, then diamond-refines it, and then does subpixel refinement. This means that a metric that accurately says "this block is within a few pixels of what RD thinks is the best block" is the best metric, because the hex search is looking for the best point at which to further refine the search, not the best point period.

However, for ESA, you want a metric that says "this block is within 1/2 pixel of the best block, RD-wise," because it literally checks every block on a fullpel basis.

I would make a guess that SATD is better at finding blocks near the best, while SAD is better for finding blocks that are basically right on top of the best. It isn't that SAD is good at finding such blocks; its just that SATD is probably bad at it.

One thought--which gives better results, --me umh --hadamard or --me esa?

[gigah72]

coz its core duo, not core 2 duo

i agree, but does it check for core 2 duo or sse3 capablity?

http://img174.imageshack.us/img174/538/sse3pa2.png (http://imageshack.us)

[DeathTheSheep]

Ah, that does make some sense!
But why would a metric that finds the best block (or "right on top of the best")--SAD--produce worse results with the exhaustive search than a metric that finds blocks near the best--SATD--with a patterned search?

Unless that is to say SATD's 'near'-prediction beats SAD's 'best'-prediction.

If this is the case, is there such an optimal metric as you defined that can be implemented into x264 for exhaustive search?

[Dark Shikari]

Ah, that does make some sense!
But why would a metric that finds the best block (or "right on top of the best")--SAD--produce worse results with the exhaustive search than a metric that finds blocks near the best--SATD--with a patterned search?

Unless that is to say SATD's 'near'-prediction beats SAD's 'best'-prediction.

If this is the case, is there such an optimal metric as you defined that can be implemented into x264 for exhaustive search?
I'm going to try varying the metrics used for different parts of the search and seeing if I can figure out what exactly is going on.
i agree, but does it check for core 2 duo or sse3 capablity?

http://img174.imageshack.us/img174/538/sse3pa2.png (http://imageshack.us)
SSSE3, not SSE3. Big difference. x264 doesn't use SSE3.

[foxyshadis]

x264 doesn't have or need sse3. It's ssse3 that's useful, and even if gcc uses it, it won't show up (because that list only shows what x264 optimizations are used, not what compiler optimizations, and x264 only uses ssse3 in 64-bit mode).

So far it looks pretty unequivocally better for cartoons & cg, but by a pretty small amount. Live action is less conclusive and I'm getting sick of this graphing. :p

[Terranigma]

x264 doesn't have or need sse3. It's ssse3 that's useful, and even if gcc uses it, it won't show up (because that list only shows what x264 optimizations are used, not what compiler optimizations, and x264 only uses ssse3 in 64-bit mode).

How much of a speed difference, in terms of percentage, would you say there is between sse2 & ssse3? Also, does x264 reap any benefit from the new sse4 instruction? Could you also give a value, in terms of prcoessing speed between ssse3 and sse4 as well? Thanks in advance. :)

[Dark Shikari]

How much of a speed difference, in terms of percentage, would you say there is between sse2 & ssse3? Also, does x264 reap any benefit from the new sse4 instruction? Could you also give a value, in terms of prcoessing speed between ssse3 and sse4 as well? Thanks in advance. :)
The new SSEs and such are only useful in terms of the instructions they add; and if they don't add any instructions that are useful and faster than older instructions, they're not going to be used.

SSE4 isn't even out yet on any consumer chips, but I believe it includes a Sum of Absolute Difference operation, which should speed up encoding a lot. Unfortunately it won't help at all with the --hadamard option :p

[Terranigma]

Unfortunately it won't help at all with the --hadamard option :p

Ok, thanks for the info; this was the main reason of my asking. Would it be okay to only use hadamard for the final pass? :devil:

[akupenguin]

Size and quality increases are reversed when using an exhaustive search. This was the case with x264-satd-opt in the past, as well.

SATD should work in ESA. It should not work in SEA. This means you need to uncomment

#if 0
/* plain old exhaustive search */
for( my = min_y; my <= max_y; my++ )
for( mx = min_x; mx <= max_x; mx++ )
COST_MV( mx, my );
#else

SEA (the complicated alternative to that code) losslessly rules out most of the mvs, and thus produces results identical to ESA much faster. But it can only work for SAD and (with some changes) SSD.

SSE4 isn't even out yet on any consumer chips, but I believe it includes a Sum of Absolute Difference operation, which should speed up encoding a lot. Unfortunately it won't help at all with the --hadamard option :p
A SAD instruction has existed since MMX2. SSE4 adds an ESA instruction. But I'm unsure of whether it will be faster than SSE2 SEA, since the benchmarks I've seen claim only about a factor of 2 speedup over SSE2 ESA.

It's ssse3 that's useful, and even if gcc uses it, it won't show up (because that list only shows what x264 optimizations are used, not what compiler optimizations, and x264 only uses ssse3 in 64-bit mode).
x264 uses SSSE3 in 32-bit mode too.
btw, the instructions provided in SSSE3 should be very useful for SATD, but Core2's implementation of PHADD* is so much slower than PADD* that I can't actually use PHADD*. Penryns's improved permutation engine might increase the speed of this instruction until it's useful.

[Dark Shikari]

satd should work in ESA. It should not work in SEA. This means you need to uncomment

#if 0
/* plain old exhaustive search */
for( my = min_y; my <= max_y; my++ )
for( mx = min_x; mx <= max_x; mx++ )
COST_MV( mx, my );
#else

SEA (the complicated alternative to that code) losslessly rules out most of the mvs, and thus produces results identical to ESA much faster. But it can only work for SAD and (with some changes) SSD.Should I modify the patch to use the old ESA algorithm when --hadamard is used?
Ok, thanks for the info; this was the main reason of my asking. Would it be okay to only use hadamard for the final pass? :devil:Of course, I don't think it changes the bitstream decisions enough to effect a first pass at all.

[CruNcher]

does it only work @ high submes ? above 1 or 2 i see no effect their it even makes the filesize bigger ?
the improvement i see is in the last 3 digits of SSIM and for the speed loss not really good, especialy as i can't see any visual difference :P
@ aku
someone has to make deadzones adaptive (modes based on MV,QP and Bitrate) i see a real quality gain their correctly used in terms of bitrate and scenes for example credits are fine with 32-32 the current 11-21 just wastes to much bits :) the overblurring has also a nice effect on scenes where banding is visible for example Dark Shikaris night scenes would look less visible with 32-32 trough the overbluring sure it takes also details but in some situations as camera pans or non conversation scenes i think it's a nice thing to make use off (especialy for ultra low bitrate encodes) and you can still use lower settings saving fewer bits :)

[akupenguin]

Deadzones only go up to 32.
Credits are fine with higher QP too, if you used deadzones just to save bits.
I don't see how deadzones could have any effect on banding, but please prove me wrong.

[CruNcher]

it doesn't but the overblurring makes it less noticeable in the background then a very clear deadzone setting especialy from some metters away of the display device

[DeathTheSheep]

Should I modify the patch to use the old ESA algorithm when --hadamard is used?


There's no harm in trying; it looks like it might work fine. :)

[Sagittaire]

- For the first time I have 44.00 dB for my HPII trailer at 900 Kbps.
- For the first time I have 41.42 dB for my HPII trailer at 450 Kbps.

[Dark Shikari]

There's no harm in trying; it looks like it might work fine. :)
Done, and here's the results.

Not surprisingly the old ESA method is incredibly slow, so in a sense it is telling us "please don't use --hadamard and --me esa for any normal usage!" However I would think that using the SEA method with --hadamard would be somewhat disingenuous considering that it simply makes no sense to do so mathematically.

Settings used: --bframe 16 --b-pyramid --subme 7 --b-pyramid --ref 3 --progress --mixed-refs --bime --weightb --partitions all --direct auto --deblock 0:0 --no-fast-pskip --crf 25

Source: 1000 frames of Elephant's Dream: the running scene in the room full of wires. Singlethreaded.

SATD = --hadamard used, SAD = --hadamard not used.

SEA ME algorithm means the current x264 ESA algorithm, and ESA means the pure bruteforce algorithm, which is the only real option for use with --hadamard.

http://i10.tinypic.com/5yiklqe.png

Notice a few things:

1. --me umh --hadamard is about the same same speed as --me esa and basically equals its quality per bitrate. I haven't tried other --meranges but I assume UMH-Hadamard would be superior at higher meranges due to the faster speed.

2. --me esa --hadamard with the ESA modification is very slow but blows away everything else with the lowest bitrate and best quality without a doubt.

3. --me esa --hadamard without the ESA modification is useless.

4. --hadamard is basically pointless below --me umh.

[akupenguin]

Next experiment: full RDO of all 16641 qpel positions in the search range (assuming merange=16) ;) Just to give an upper bound on the improvements possible.
Note that the optimal subpel position is not necessarily next to the optimal fullpel position, since the subpel filter alters the pixels.

[Dark Shikari]

Next experiment: full RDO of all 16641 qpel positions in the search range (assuming merange=16) ;) Just to give an upper bound on the improvements possible.That would be absolutely insane.

But possible :devil:

Heck, you could actually use that as a way to tune our current motion search methods; do a massive RD-Qpel ESA search and then see how the current methods could be changed to better fit that search.
Note that the optimal subpel position is not necessarily next to the optimal fullpel position, since the subpel filter alters the pixels.Of course.

[ChronoCross]

I did the patching for svn but IDK how to create the patch in the correct format.

Anyway what I wanted to say was thank you for this thread as I've picked up a few things about the inner working behind everything. Threads like this are always thought provoking.

[Sagittaire]

Next experiment: full RDO of all 16641 qpel positions in the search range (assuming merange=16) ;) Just to give an upper bound on the improvements possible.
Note that the optimal subpel position is not necessarily next to the optimal fullpel position, since the subpel filter alters the pixels.


Well for ED (and I know very well Elephant Dream movie), IMO the best possible improvement way is RDO for bframes placement. Here a little example with the first 50 frame of ED (fade scene):

- 3 adaptative bframe with pure q25 encoding:
2048 Kbps and 48.73 dB

- 0 no adaptative bframe with pure q25 encoding:
2048 Kbps and 48.73 dB

- 1 no adaptative bframe with pure q25 encoding:
1482 Kbps and 48.83 dB

- 2 no adaptative bframe with pure q25 encoding:
1282 Kbps and 48.93 dB

- 3 no adaptative bframe with pure q25 encoding:
1249 Kbps and 48.61 dB

- 3 no adaptative pyramidal bframe with pure q25 encoding:
1180 Kbps and 48.43 dB


For fade scene the most important function is wpred. Anyway x264 use only wpred for bframe and x264 RC don't use bframe in fade scene (???).


D:\Mes dossiers\Codec\x264>x264.exe --qp 25 --threads 1 --thread-input --keyint 250 --min-keyint 1 -
-mvrange 511 --level 4.1 --bframe 3 --b-pyramid --b-rdo --bime --weightb --ref 5 --mixed-refs --dire
ct auto --deblock -1:-1 --ipratio 1.00 --pbratio 1.00 --partitions "all" --8x8dct --me "umh" --subm
e 7 --no-fast-pskip --no-dct-decimate --trellis 2 --progress -o NUL test.avs
avis [info]: 1920x1080 @ 23.98 fps (50 frames)
x264 [warning]: DPB size (25067520) > level limit (12582912)
x264 [info]: using cpu capabilities: MMX MMXEXT SSE SSE2
x264 [info]: slice I:1 Avg QP:25.00 size: 306 PSNR Mean Y:100.00 U:100.00 V:100.00 Avg:100.0
0 Global:100.00
x264 [info]: slice P:43 Avg QP:25.00 size: 12406 PSNR Mean Y:50.93 U:53.53 V:55.68 Avg:51.79 Gl
obal:48.10
x264 [info]: slice B:6 Avg QP:25.00 size: 51 PSNR Mean Y:100.00 U:100.00 V:100.00 Avg:100.0
0 Global:100.00
x264 [info]: mb I I16..4: 100.0% 0.0% 0.0%
x264 [info]: mb P I16..4: 36.1% 7.9% 0.1% P16..4: 28.9% 2.3% 0.3% 0.0% 0.0% skip:24.5%
x264 [info]: mb B I16..4: 0.0% 0.0% 0.0% B16..8: 0.0% 0.0% 0.0% direct: 0.0% skip:100.0%
x264 [info]: 8x8 transform intra:17.0% inter:97.5%
x264 [info]: direct mvs spatial:0.0% temporal:100.0%
x264 [info]: ref P 96.7% 2.4% 0.7% 0.1% 0.1%
x264 [info]: SSIM Mean Y:0.9892583
x264 [info]: PSNR Mean Y:57.796 U:60.033 V:61.884 Avg:58.536 Global:48.753 kb/s:2048.72

encoded 50 frames, 1.09 fps, 2051.81 kb/s

D:\Mes dossiers\Codec\x264>x264.exe --qp 25 --threads 1 --thread-input --keyint 250 --min-keyint 1 -
-mvrange 511 --level 4.1 --bframe 0 --no-b-adapt --b-rdo --bime --weightb --ref 5 --mixed-refs --dir
ect auto --deblock -1:-1 --ipratio 1.00 --pbratio 1.00 --partitions "all" --8x8dct --me "umh" --sub
me 7 --no-fast-pskip --no-dct-decimate --trellis 2 --progress -o NUL test.avs
avis [info]: 1920x1080 @ 23.98 fps (50 frames)
x264 [warning]: DPB size (15667200) > level limit (12582912)
x264 [info]: using cpu capabilities: MMX MMXEXT SSE SSE2
x264 [info]: slice I:1 Avg QP:25.00 size: 306 PSNR Mean Y:100.00 U:100.00 V:100.00 Avg:100.0
0 Global:100.00
x264 [info]: slice P:49 Avg QP:25.00 size: 10893 PSNR Mean Y:56.93 U:59.22 V:61.11 Avg:57.69 Gl
obal:48.67
x264 [info]: mb I I16..4: 100.0% 0.0% 0.0%
x264 [info]: mb P I16..4: 31.6% 6.9% 0.1% P16..4: 25.3% 2.0% 0.2% 0.0% 0.0% skip:33.7%
x264 [info]: 8x8 transform intra:17.0% inter:97.5%
x264 [info]: ref P 96.7% 2.4% 0.7% 0.1% 0.1%
x264 [info]: SSIM Mean Y:0.9892583
x264 [info]: PSNR Mean Y:57.796 U:60.033 V:61.884 Avg:58.536 Global:48.753 kb/s:2048.67

encoded 50 frames, 1.11 fps, 2051.52 kb/s

D:\Mes dossiers\Codec\x264>x264.exe --qp 25 --threads 1 --thread-input --keyint 250 --min-keyint 1 -
-mvrange 511 --level 4.1 --bframe 1 --no-b-adapt --b-rdo --bime --weightb --ref 5 --mixed-refs --dir
ect auto --deblock -1:-1 --ipratio 1.00 --pbratio 1.00 --partitions "all" --8x8dct --me "umh" --sub
me 7 --no-fast-pskip --no-dct-decimate --trellis 2 --progress -o NUL test.avs
avis [info]: 1920x1080 @ 23.98 fps (50 frames)
x264 [warning]: DPB size (18800640) > level limit (12582912)
x264 [info]: using cpu capabilities: MMX MMXEXT SSE SSE2
x264 [info]: slice I:1 Avg QP:25.00 size: 306 PSNR Mean Y:100.00 U:100.00 V:100.00 Avg:100.0
0 Global:100.00
x264 [info]: slice P:25 Avg QP:25.00 size: 14375 PSNR Mean Y:55.84 U:58.18 V:60.21 Avg:56.62 Gl
obal:48.66
x264 [info]: slice B:24 Avg QP:25.00 size: 1121 PSNR Mean Y:56.85 U:59.84 V:61.85 Avg:57.51 Gl
obal:48.83
x264 [info]: mb I I16..4: 100.0% 0.0% 0.0%
x264 [info]: mb P I16..4: 40.3% 13.8% 0.4% P16..4: 16.0% 2.5% 0.1% 0.0% 0.0% skip:26.9%
x264 [info]: mb B I16..4: 0.1% 0.0% 0.0% B16..8: 3.4% 0.0% 0.0% direct: 0.2% skip:96.3%
x264 [info]: 8x8 transform intra:23.5% inter:92.3%
x264 [info]: direct mvs spatial:70.8% temporal:29.2%
x264 [info]: ref P 96.6% 2.5% 0.7% 0.2% 0.1%
x264 [info]: ref B 99.5% 0.4% 0.0% 0.1%
x264 [info]: SSIM Mean Y:0.9895206
x264 [info]: PSNR Mean Y:57.211 U:59.811 V:61.790 Avg:57.914 Global:48.833 kb/s:1482.98

encoded 50 frames, 1.65 fps, 1486.20 kb/s

D:\Mes dossiers\Codec\x264>x264.exe --qp 25 --threads 1 --thread-input --keyint 250 --min-keyint 1 -
-mvrange 511 --level 4.1 --bframe 2 --no-b-adapt --b-rdo --bime --weightb --ref 5 --mixed-refs --dir
ect auto --deblock -1:-1 --ipratio 1.00 --pbratio 1.00 --partitions "all" --8x8dct --me "umh" --sub
me 7 --no-fast-pskip --no-dct-decimate --trellis 2 --progress -o NUL test.avs
avis [info]: 1920x1080 @ 23.98 fps (50 frames)
x264 [warning]: DPB size (18800640) > level limit (12582912)
x264 [info]: using cpu capabilities: MMX MMXEXT SSE SSE2
x264 [info]: slice I:1 Avg QP:25.00 size: 306 PSNR Mean Y:100.00 U:100.00 V:100.00 Avg:100.0
0 Global:100.00
x264 [info]: slice P:17 Avg QP:25.00 size: 16724 PSNR Mean Y:56.67 U:58.92 V:60.65 Avg:57.41 Gl
obal:48.70
x264 [info]: slice B:32 Avg QP:25.00 size: 1557 PSNR Mean Y:57.50 U:59.68 V:61.26 Avg:58.19 Gl
obal:48.93
x264 [info]: mb I I16..4: 100.0% 0.0% 0.0%
x264 [info]: mb P I16..4: 43.9% 17.8% 0.9% P16..4: 11.2% 2.2% 0.2% 0.0% 0.0% skip:23.7%
x264 [info]: mb B I16..4: 0.1% 0.1% 0.0% B16..8: 4.4% 0.1% 0.1% direct: 0.3% skip:95.0%
x264 [info]: 8x8 transform intra:26.1% inter:87.6%
x264 [info]: direct mvs spatial:71.9% temporal:28.1%
x264 [info]: ref P 96.8% 2.4% 0.6% 0.1% 0.0%
x264 [info]: ref B 99.7% 0.2% 0.1% 0.0% 0.0%
x264 [info]: SSIM Mean Y:0.9894938
x264 [info]: PSNR Mean Y:58.068 U:60.229 V:61.825 Avg:58.765 Global:48.936 kb/s:1282.96

encoded 50 frames, 2.05 fps, 1286.22 kb/s

D:\Mes dossiers\Codec\x264>x264.exe --qp 25 --threads 1 --thread-input --keyint 250 --min-keyint 1 -
-mvrange 511 --level 4.1 --bframe 3 --no-b-adapt --b-rdo --bime --weightb --ref 5 --mixed-refs --dir
ect auto --deblock -1:-1 --ipratio 1.00 --pbratio 1.00 --partitions "all" --8x8dct --me "umh" --sub
me 7 --no-fast-pskip --no-dct-decimate --trellis 2 --progress -o NUL test.avs
avis [info]: 1920x1080 @ 23.98 fps (50 frames)
x264 [warning]: DPB size (18800640) > level limit (12582912)
x264 [info]: using cpu capabilities: MMX MMXEXT SSE SSE2
x264 [info]: slice I:1 Avg QP:25.00 size: 306 PSNR Mean Y:100.00 U:100.00 V:100.00 Avg:100.0
0 Global:100.00
x264 [info]: slice P:13 Avg QP:25.00 size: 18693 PSNR Mean Y:55.53 U:57.84 V:59.61 Avg:56.29 Gl
obal:48.67
x264 [info]: slice B:36 Avg QP:25.00 size: 2287 PSNR Mean Y:55.90 U:58.72 V:61.06 Avg:56.67 Gl
obal:48.47
x264 [info]: mb I I16..4: 100.0% 0.0% 0.0%
x264 [info]: mb P I16..4: 47.2% 21.3% 1.6% P16..4: 6.9% 1.8% 0.1% 0.0% 0.0% skip:21.0%
x264 [info]: mb B I16..4: 0.3% 0.3% 0.0% B16..8: 5.6% 0.1% 0.2% direct: 0.5% skip:93.0%
x264 [info]: 8x8 transform intra:27.8% inter:86.7%
x264 [info]: direct mvs spatial:69.4% temporal:30.6%
x264 [info]: ref P 96.7% 2.7% 0.5% 0.1% 0.1%
x264 [info]: ref B 99.8% 0.2% 0.0% 0.0% 0.0%
x264 [info]: SSIM Mean Y:0.9892318
x264 [info]: PSNR Mean Y:56.689 U:59.318 V:61.461 Avg:57.436 Global:48.611 kb/s:1249.17

encoded 50 frames, 2.10 fps, 1252.35 kb/s

D:\Mes dossiers\Codec\x264>x264.exe --qp 25 --threads 1 --thread-input --keyint 250 --min-keyint 1 -
-mvrange 511 --level 4.1 --bframe 3 --b-pyramid --no-b-adapt --b-rdo --bime --weightb --ref 5 --mixe
d-refs --direct auto --deblock -1:-1 --ipratio 1.00 --pbratio 1.00 --partitions "all" --8x8dct --me
"umh" --subme 7 --no-fast-pskip --no-dct-decimate --trellis 2 --progress -o NUL test.avs
avis [info]: 1920x1080 @ 23.98 fps (50 frames)
x264 [warning]: DPB size (25067520) > level limit (12582912)
x264 [info]: using cpu capabilities: MMX MMXEXT SSE SSE2
x264 [info]: slice I:1 Avg QP:25.00 size: 306 PSNR Mean Y:100.00 U:100.00 V:100.00 Avg:100.0
0 Global:100.00
x264 [info]: slice P:13 Avg QP:25.00 size: 18696 PSNR Mean Y:55.53 U:57.85 V:59.62 Avg:56.30 Gl
obal:48.68
x264 [info]: slice B:36 Avg QP:25.00 size: 1787 PSNR Mean Y:55.75 U:59.01 V:59.27 Avg:56.42 Gl
obal:48.24
x264 [info]: mb I I16..4: 100.0% 0.0% 0.0%
x264 [info]: mb P I16..4: 47.0% 21.1% 1.5% P16..4: 7.2% 1.8% 0.1% 0.0% 0.0% skip:21.2%
x264 [info]: mb B I16..4: 0.2% 0.2% 0.0% B16..8: 4.9% 0.1% 0.1% direct: 0.4% skip:94.2%
x264 [info]: 8x8 transform intra:27.6% inter:85.9%
x264 [info]: direct mvs spatial:75.0% temporal:25.0%
x264 [info]: ref P 91.8% 5.6% 1.8% 0.5% 0.2%
x264 [info]: ref B 98.8% 0.9% 0.2% 0.0% 0.1%
x264 [info]: SSIM Mean Y:0.9893261
x264 [info]: PSNR Mean Y:56.577 U:59.531 V:60.178 Avg:57.260 Global:48.438 kb/s:1180.27

encoded 50 frames, 1.55 fps, 1183.41 kb/s

[DeathTheSheep]

Assuming I can't compile it myself, where could I get ahold of that "fixed" ESA build? :)

[Terranigma]

Hmm, I thought p4x4 was only useable on an unrestricted level, yet you have partitions all with a level of 4.1

[Dark Shikari]

Assuming I can't compile it myself, where could I get ahold of that "fixed" ESA build? :)The patch linked in my original post has now been updated with the ESA change. The linked .7z with the source code has also been updated.

[Dark Shikari]

Well for ED (and I know very well Elephant Dream movie), IMO the best possible improvement way is RDO for bframes placement. Here a little example with the first 50 frame of ED (fade scene):

- 3 adaptative bframe with pure q25 encoding:
2048 Kbps and 48.73 dB

- 0 no adaptative bframe with pure q25 encoding:
2048 Kbps and 48.73 dB

- 1 no adaptative bframe with pure q25 encoding:
1482 Kbps and 48.83 dB

- 2 no adaptative bframe with pure q25 encoding:
1282 Kbps and 48.93 dB

- 3 no adaptative bframe with pure q25 encoding:
1249 Kbps and 48.61 dB

- 3 no adaptative pyramidal bframe with pure q25 encoding:
1180 Kbps and 48.43 dB


For fade scene the most important function is wpred. Anyway x264 use only wpred for bframe and x264 RC don't use bframe in fade scene (???).
I actually have an idea for a stopgap measure before B-frame decision RDO is implemented. Here's the pseudocode.
float averageLuma(frame,width,height)
{
int linetotal = 0
double total = 0
for line in frame
{
for pixel in line
{
linetotal += pixel.luma
}
total += linetotal
linetotal = 0
}
return (float)total/(width*height)
}

FrameDecision(args)
{
//normal stuff goes here
float avgLuma[MaxBFrames];
avgLuma[0]=averageLuma(getFrame(currentFrame))
int totalBias = 0
for(n = 1, n < MaxBframes, n++)
{
avgLuma[n]=averageLuma(getFrame(currentFrame+n))
if(avgLuma[n] < avgLuma[n-1]) totalBias++
else break
}
int C = 3 //Arbitrary constant, would have to be tuned through experimentation
for(n = 1, n < totalBias, n++)
{
getFrame(n).b_bias += C * n * n
}
//Final frame decision goes here
}

Basically what I'm doing is, when the luma is decreasing consistently from each frame to the next and to the next, I am biasing these frames in favor of being B-frames. If the luma decreases just a couple times in a row, it biases it very little (notice the n^2). If it decreases 16 times in a row, you get a C*256 b-bias for each of those frames.

To a developer: what would be the best way to:

a) Make a function that counts up the luma and averages it
b) set the b-bias for multiple frames in the future

Not algorithmically how would I do it, but technically (dealing with the x264 codebase).

[TheRyuu]

The patch linked in my original post has now been updated with the ESA change. The linked .7z with the source code has also been updated.

Do I need to recompile it again?

Edit:
Here:
x264 Hadamard fixed ESA build 667b x86 (32 bit) Generic (http://www.sendspace.com/file/h36ua8) (mmx support needed)

Too lazy right now to do like 5 builds. And I can't get the stupid 64bit compiler to work.

[jethro]

- For the first time I have 44.00 dB for my HPII trailer at 900 Kbps.
- For the first time I have 41.42 dB for my HPII trailer at 450 Kbps.

I just got Global PSNR 42.933 @ 450kbps with your HPII trailer. It was only 2nd try so this can't be best result.

x264h.exe --pass 2 --
bitrate 450 --stats ".stats" -b 8 -m 7 -f -1:-1 --b-rdo -t2 --hadamard --me umh
--bime -8 -w -r 5 --mixed-refs --pbratio 1.2 --b-pyramid --threads auto --thread-input --progress --direct auto --output output.mp4 "input.avs"
avis [info]: 720x576 @ 25.00 fps (3212 frames)
x264 [info]: using cpu capabilities: MMX MMXEXT SSE SSE2 SSSE3
mp4 [info]: initial delay 2 (scale 25)
x264 [info]: slice I:54 Avg QP:26.15 size: 9026 PSNR Mean Y:46.56 U:49.07
V:49.77 Avg:47.27 Global:45.29
x264 [info]: slice P:1329 Avg QP:28.83 size: 3593 PSNR Mean Y:43.52 U:46.74
V:47.46 Avg:44.33 Global:42.72
x264 [info]: slice B:1829 Avg QP:28.28 size: 1068 PSNR Mean Y:46.02 U:49.17
V:49.92 Avg:46.77 Global:43.04
x264 [info]: mb I I16..4: 46.9% 48.4% 4.7%
x264 [info]: mb P I16..4: 12.7% 11.1% 0.7% P16..4: 21.9% 4.6% 0.6% 0.0% 0
.0% skip:48.4%
x264 [info]: mb B I16..4: 0.5% 0.7% 0.1% B16..8: 24.8% 0.4% 0.6% direct:
0.4% skip:72.5%
x264 [info]: 8x8 transform intra:46.4% inter:89.9%
x264 [info]: direct mvs spatial:0.0% temporal:100.0%
x264 [info]: ref P 76.5% 11.5% 6.9% 2.7% 2.5%
x264 [info]: ref B 83.2% 9.0% 4.3% 2.1% 1.4%
x264 [info]: SSIM Mean Y:0.9746582
x264 [info]: PSNR Mean Y:44.993 U:48.164 V:48.904 Avg:45.768 Global:42.933 kb/s:
449.33

encoded 3212 frames, 8.62 fps, 449.53 kb/s
Press any key to continue . . .

[Sagittaire]

I just got Global PSNR 42.933 @ 450kbps with your HPII trailer. It was only 2nd try so this can't be best result.

I crop/trim all the black part. I use this script:

source=Mpeg2Source("D:\Mes dossiers\B.A\Harry Potter\azerty.d2v",idct=2)
source=Trim(source,70,3145)
source=Crop(source,0,76,-0,-76)
source=LanczosResize(source,720,304)
Return(source)

[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.

[Dark Shikari]

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.
Correct, I meant the video clip.

Anyways I've been a bit busy lately, but I'm currently working on an algorithm to adaptively choose SAD or Hadamard, like the "Adaptive" option in VC-1. I've found some strange results, for example where using SATD in just 10% of cases (carefully chosen cases) can increase quality by about 0.7%, almost half of the total 1.8% or so from SATD.

What's really strange is the following:

Running SATD in case A creates a 0.7% quality increase
Running SATD in case B creates a 0.6% quality increase
Case A implies a lack of case B--they don't overlap
Running SATD in case A and case B creates a 0.3% quality increase (?!)

[akupenguin]

Running SATD in case A creates a 0.7% quality increase
Running SATD in case B creates a 0.6% quality increase
Running SATD in case A and case B creates a 0.3% quality increase (?!)
Is that property and the approximate numbers involved independent of video content?
Can you quantify which macroblocks get the improvement in one case and not in the other, and see whether the regression is mostly due to increased distortion, increased residual cost, or increased mv cost?

[Dark Shikari]

Is that property and the approximate numbers involved independent of video content?
Can you quantify which macroblocks get the improvement in one case and not in the other, and see whether the regression is mostly due to increased distortion, increased residual cost, or increased mv cost?
I haven't tried it on different videos, so it could be content-dependent. What is a good way to measure distortion on a per-macroblock basis?

[akupenguin]

Disable deblocking (and use a high enough bitrate that this doesn't impose a huge penalty), look at PSNR and not SSIM, and set trellis to either 0 or 2. Then it's simply the SSD and bits from an RD call for the final chosen mode.
Those assumptions may not match the real world, but they ensure that the block-wise metrics are identical to the frame-wise metrics.

[Dark Shikari]

Disable deblocking (and use a high enough bitrate that this doesn't impose a huge penalty), look at PSNR and not SSIM, and set trellis to either 0 or 2. Then it's simply the SSD and bits from an RD call for the final chosen mode.
Those assumptions may not match the real world, but they ensure that the block-wise metrics are identical to the frame-wise metrics.
Somewhat on this topic, one thing I've been wanting to do. SAD and SATD are nice because I can easily make COST_MV calls anywhere with a single line of code. RDO isn't nearly as pretty and requires extra variables and such.

How would you suggest I go about making it so that I can call RDO as easily as COST_MV?

[DeathTheSheep]

Its probably equivalent to the Microsoft VC-1 codec "Hadamard"
I'm currently working on an algorithm...like the "Adaptive" option in VC-1.
Dark Shikari you VC-1 junkie, you. ;)

Anyways here's the source vid. (http://gabe.ej.am/SourceVid.zip)

edit: Yeah, I found that 1/3 is a perfect multiplier for the threshold. It gives me identical or near-identical results with straight ESA at my settings. Yeah, it's slower than your 3/4s, going from 13.2fps down to 8.5fps. But still, compared to 5.6fps with straight ESA, I'll deal with it. :)

[Dark Shikari]

Dark Shikari you VC-1 junkie, you. ;)

Anyways here's the source vid. (http://gabe.ej.am/SourceVid.zip)

edit: Yeah, I found that 1/3 is a perfect multiplier for the threshold. It gives me identical or near-identical results with straight ESA at my settings. Yeah, it's slower than your 3/4s, going from 13.2fps down to 8.5fps. But still, compared to 5.6fps with straight ESA, I'll deal with it. :)
That video seems to be a very bad example overall, for two reasons:

1. Tons of fades, which x264's frame decision algorithm is horrible with.

2. Basically no motion other than camera panning.

Its definitely nice to find something that breaks my ESA algorithm, but as a general test clip that seems like a bad one to use.

[DeathTheSheep]

Those clips that seem "bad" tend, more often than not, to be the most useful for me, because they bring out problems the "standard" tests don't reveal. That's precisely why most of the problems occur in scenes people don't use as test clips--because the codec hasn't been tuned for them.

Dark, slow moving block messes. Bluesky issue. Adaptive quantization woes. Mild fade-out problems. The biggest problems, in my opinion, these are all visible from the non-standard test clips, ones without blinding flashes and high-paced motion to distract you from what you would otherwise take the time to notice. And that's precisely where I intend to focus most: the places I usually focus most in real life. :)

...I also have a nice high motion test clip I'm now using, though, just in case. :)

[Dark Shikari]

Those clips that seem "bad" tend, more often than not, to be the most useful for me, because they bring out problems the "standard" tests don't reveal. That's precisely why most of the problems occur in scenes people don't use as test clips--because the codec hasn't been tuned for them.

Dark, slow moving block messes. Bluesky issue. Adaptive quantization woes. Mild fade-out problems. The biggest problems, in my opinion, these are all visible from the non-standard test clips, ones without blinding flashes and high-paced motion to distract you from what you would otherwise take the time to notice. And that's precisely where I intend to focus most: the places I usually focus most in real life. :)

...I also have a nice high motion test clip I'm now using, though, just in case. :)Fades are bad though, IMO, because they're testing something that really should be fixed separately--for example, something that improves fades with the current algorithm may hurt fades much more once B-frames with fades are properly fixed.

[DeathTheSheep]

I don't use B-frames. :)

Pretty much everyone who encodes for the lowest-common-denominator/portable/all-standards-compliant/low-decode-complexity stuff won't either.

Of course I'm not saying it's bad to optimize B-frames (on the contrary), just that optimizing for use without them doesn't hurt, either. Especially since x264 is smart enough to know whether the user has them turned on or not and can choose which algorithm to use, respectively. :)

[DeathTheSheep]

Sorry for the ominous double post, but I have a suggestion/question to pose.

What is the best way one could go about defining an adaptive motion search range...like Microsoft's VC-1, lavc, etc?

16 at times seems a huge overkill for slow pans (especially at low resolutions!) but far too narrow in high-paced animated motion (especially at high resolutions). Granted, the resolution is something of a moot point, given that one can set a different range from the start if his resolution warrants it. But for different types and extremities of motion, an adaptive merange might positively effect both quality and speed. This may be especially true of exhaustive searches, since a higher merange just when needed poses a substantial gain, and a smaller exhaustive window during slow motion would prevent false far-predictions while dramatically boosting speed...

[Dark Shikari]

Sorry for the ominous double post, but I have a suggestion/question to pose.

What is the best way one could go about defining an adaptive motion search range...like Microsoft's VC-1, lavc, etc?

16 at times seems a huge overkill for slow pans (especially at low resolutions!) but far too narrow in high-paced animated motion (especially at high resolutions). Granted, the resolution is something of a moot point, given that one can set a different range from the start if his resolution warrants it. But for different types and extremities of motion, an adaptive merange might positively effect both quality and speed. This may be especially true of exhaustive searches, since a higher merange just when needed poses a substantial gain, and a smaller exhaustive window during slow motion would prevent false far-predictions while dramatically boosting speed...
Remember that --merange is not the maximum ME range; its the ME refinement range. Before the refinement even begins, x264 uses predictors from previous blocks to find a good place to start the ME search.

So the 16 merange is a range around the predicted point, not the range around the starting point.

An adaptive MErange could be useful, but on the other hand note that most of the ME algorithms already have early termination code.

[DeathTheSheep]

So it is not actually is the maximum range a block can travel in order to get into a me vector? Wasn't that its definition?
Assuming it is a "refinement" range (which doubtlessly it is anyway, in the common definition of the word), why not refine a larger range if motion occurs across the span of that range?

If something moves over a set 'x' pixels of distance, it won't make it into the vector, and thus some efficiency might well be lost.

Yes, I am aware of early termination. But this isn't necessarily to say a range of 8 is worse on something that clearly moved 5 pixels, than a range of 64 on something that moved those 5 pixels. In fact, there's more room for false prediction and more innacurate "early termination." In regards to ESA, of course, "early termination" is more of a farce than anything, since everything not losslessly ruled out by the new lowpass is bound to be analyzed anyway, since the entire span has a uniform search priority of 1!

[Dark Shikari]

So it is not actually is the maximum range a block can travel in order to get into a me vector? Wasn't that its definition?
That's mv-range, not me-range, I believe.

[TheRyuu]

Has the diff patch been updated with the faster stuff (honestly, I haven't been following the development of this, so I don't know the terms here).

I'll build it again if your ready.

[Dark Shikari]

Has the diff patch been updated with the faster stuff (honestly, I haven't been following the development of this, so I don't know the terms here).

I'll build it again if your ready.
Still working on things at the moment--until I'm satisfied that there's no good way to make things better I'll keep improving things. There's been no recent changes to the diff though since the ESA speed improvement.

[DeathTheSheep]

Well, mvrange is just the length/size of the vector itself, which is automatically adjusted (by default) based on how much info is in merange! Obviously if there isn't much motion to map in the merange, there usually isn't going to be much to cram in a vector.

With a big merange, you can fit a much larger uniform area of displacement into the vector oftentimes (up to +/- 512 vertically, I believe), leading to more accuracy in most cases.

Argh, the vector size vs. estimation range!1/1@0N3

[akupenguin]

I can't even say for sure that you're wrong, you're just not making sense.

[Dark Shikari]

Aku, can you give me advice on my question earlier (how to make RDO into something that can be called as easily as COST_MV in the motion search function), how to deal with the extra variables the RDO function requires as arguments, etc?

Also, does anyone have a good program that can take a few million lines of data and create a chart or a series of data showing its distribution?

I.e. if I have 10 million numbers, and I want to see how they are distributed, what is a good program to do this? Openoffice and Excel both stop at low row amounts (2^16-1 and 2^20-1 respectively) and don't seem to have any good tools for this.

If I can get a good program for this I will be able to do my algorithm improvement work much faster.

Edit: Bleh, I decided to do the distribution-sorting (counting how many of each number there is) in x264 itself... I can code C better than I can use most spreadsheets ;)

Basically what I'm doing is running every motion search using SAD and SATD, separately. Then I choose a possible metric one could use to make an adaptive SAD-SATD decision. Then I'm getting the distributions for two sets of data:
a) The set metrics for all motion searches
b) The set of metrics for all motion searches in which SATD finds a different result than SAD
The latter, of course, is what we care about--the other motion searches we want to avoid bothering using SATD on them. If I can find a metric whose distribution significantly differs between those two groups, that's one possible way to improve the speed.

[akupenguin]

Aku, can you give me advice on my question earlier (how to make RDO into something that can be called as easily as COST_MV in the motion search function), how to deal with the extra variables the RDO function requires as arguments, etc?
Store lambda2 in x264_t. Write a wrapper around rd_cost_part() that takes mv as a parameter and sets h->mb.cache.mv appropriately. I'm not sure what to do about i8: it could be derived by comparing fenc to h->mb.pic.p_fenc[0], but that's kinda ugly.

Also, does anyone have a good program that can take a few million lines of data and create a chart or a series of data showing its distribution?
I use gnuplot for stuff like http://akuvian.org/src/x264/cmp.html
It takes a certain amount of RAM to do anything to 10 million points, but there's no inherent limit.

[DeathTheSheep]

You're just not making sense.

I was starting to confuse myself. Could you perhaps clear up the distinction between merange and mvrange?
...the maximum range/distance a macroblock can travel in order to get encoded as a me vector?
Is this merange, mvrange, or neither (i.e. there is no such thing)?

And do you have any remarks about implementing adaptive motion search range?

[akupenguin]

Macroblocks don't "travel", and there's no such thing as a "me vector". Objects travel, blocks are predicted. ME = motion estimation, MC = motion compensation, MV = motion vector.

Motion estimation consists of: Evaluate about 10 different predictions for the current motion vector, then search the neighborhood of the best prediction. Where "best" means "lowest SAD + bits", though Shikari's patch modifies that.

mvrange limits the length of any mv. i.e. the maximum distance between a macroblock and the pixels that it's predicted from. There is no reason to even reduce mvrange, unless you're targetting a low Level which requires it. If the motion of a given object in the video from one frame to the next (well, from one frame to some other frame that references it, might not be strictly the next frame) exceeds mvrange, then even if the motion estimation algorithm finds the mv, it will be prohibited from using it, and forced to pick a different reference frame or use intra instead.

merange determines the size of the neighborhood to be searched around the best predictor. It affects only UMH and ESA (because HEX and DIA are purely iterative and thus don't have an explicit pattern size).
If the distance between the best predictor and the real mv exceeds merange, then x264 probably won't find the real mv. (For DIA and Hex there's no strict threshold, just the greater the distance, the lower the likelyhood of finding it.) If merange is significantly larger than the distance between predictor and real mv, then you've wasted some cpu time. So you want to increase merange in chaotic regions where motion can't be predicted well, and you can get away with reducing merange in scenes with smooth motion fields. Even a very fast pan counts as smooth, because each motion vector is the same as its neighbors.

UMH already adapts range somewhat. It looks at the variance between the 10 predictors, and uses a smaller merange if all the predictions are about the same, or a larger merange if they differ a lot. But of course it could be improved.

[DeathTheSheep]

So, one could simplify the terms as such:
merange Size of neighborhood searched around a best predictor (when using esa or umh). Not adaptive with ESA, minimally so with UMH.
mvrange Maximum allowed distance between macroblocks and best predictor (between next/reference frames).

If merange is significantly larger than the distance between predictor and real mv, then you've wasted some cpu time. So you want to increase merange in chaotic regions where motion can't be predicted well, and you can get away with reducing merange in scenes with smooth motion fields.

This is exactly what I was getting at before; is there a way to autodetect motion field smoothness before applying a potentially wasteful merange size? Or dynamically increasing merange in chaotic regions?

[Razorholt]

@Dark Shikari : First, thank you very much for working on this patch! Also, should I wait until you release your next version before I embark to an everlasting encoding process? How close are you from that next release?


Best,
- Dan

[Dark Shikari]

@Dark Shikari : First, thank you very much for working on this patch! Also, should I wait until you release your next version before I embark to an everlasting encoding process? How close are you from that next release?


Best,
- DanUnfortunately I haven't really made any progress. It seems that switching between SATD and SAD, even intelligently, can have bad results because it causes motion vectors to lose coherence.

So not much has changed since my current patch.

In terms of using SATD as a refinement instead of as the sole metric, this works well in ESA (with my optimized algorithm), mediocre in UMH (still better than SAD but not worth the quality loss) and doesn't work at all in hex due to its algorithm.

[Razorholt]

No problem at all. :) I can use AQ with your patch, right?

Here is my cmd line:
--pass 2 --bitrate 1450 --stats ".stats" --ref 6 --
mixed-refs --no-fast-pskip --bframes 3 --b-pyramid --b-rdo --
bime --weightb --direct auto --subme 7 --analyse all --8x8
dct --pbratio 1.1 --vbv-maxrate 25000 --me esa --merange
24 --threads auto --thread-input --
cqmfile "C:\Videos\prestige.cqm" --progress --no-dct-
decimate --no-psnr --no-ssim --output "" "" --hadamard --aq-
strength 0.7 --aq-sensitivity 15

[Sagekilla]

Razor, any reason for using esa and a merange of 24? From what I know, the quality difference between using that and regular --me umh and standard --merange 16 is too little to warrant using esa at all.

Also, yes that would be correct for using AQ.

[Dark Shikari]

Razor, any reason for using esa and a merange of 24? From what I know, the quality difference between using that and regular --me umh and standard --merange 16 is too little to warrant using esa at all.

Also, yes that would be correct for using AQ.
Hadamard ESA gives a boost of about 0.8-1.8% SSIM over Hadamard UMH based on the source.

--merange 24 is a nice way to slow it down even further though :p as if Hadamard ESA wasn't slow enough.

[Razorholt]

Razor, any reason for using esa and a merange of 24? From what I know, the quality difference between using that and regular --me umh and standard --merange 16 is too little to warrant using esa at all.

I find the video less blocky, especially encoding from DVD source at a low bitrate (500kbps).

[Dark Shikari]

Also, today's random x264 project: create a completely new algorithm (based somewhat off of HEX) using simulated annealing (http://en.wikipedia.org/wiki/Simulated_annealing).

[Sagittaire]

Also, today's random x264 project: create a completely new algorithm (based somewhat off of HEX) using simulated annealing (http://en.wikipedia.org/wiki/Simulated_annealing).

News from rdo for bframe placement?

[Dark Shikari]

News from rdo for bframe placement?I don't know nearly enough about the x264 codebase to even begin that... I could try a dirty hack like I described earlier but even that will be hard unless I can have a good 15-30 minute chat with Akupenguin to understand the code better. It isn't very well-commented :p

Update 1 on simulated annealing: Its promising! 0.24% quality per bitrate improvement with about 11% speed loss over hex. Note however that this is literally the first time I ran the algorithm with no tuning at all to any of the parameters--this has a lot of potential, IMO.
Update 2: +0.85% quality, -20% speed. Still tons more tuning to do, along with implementation of a "memory" aka Tabu search and other common advanced features of simulated annealing.

[Sagekilla]

I find the video less blocky, especially encoding from DVD source at a low bitrate (500kbps).

Mmm, yes I could imagine that being a bit problematic. Why don't you try adding in --b-rdo too? That's the only setting you seem to be not using.

[Razorholt]

Why don't you try adding in --b-rdo too?
Look closely :)

[Sagekilla]

Haha I see it, sorry about that.

Just curious but what resolution do you use for such a low (500 kbps you said) bitrate?

[Razorholt]

480x or 512x depending on the source.

[foxyshadis]

Update 2: +0.85% quality, -20% speed. Still tons more tuning to do, along with implementation of a "memory" aka Tabu search and other common advanced features of simulated annealing.

That's pretty cool. By your metrics on this source, though, what is the difference between hex and umh, as the other anchor for comparison to the gains here?

Count me in for those who are looking forward to even a rough improvement in fade quality.

[Dark Shikari]

That's pretty cool. By your metrics on this source, though, what is the difference between hex and umh, as the other anchor for comparison to the gains here?

Count me in for those who are looking forward to even a rough improvement in fade quality.
This is unrelated to fade quality--thats a frame placement issue. This is just a brand new motion estimation function.

[Razorholt]

ooh, how about another random x264 project that will make that codec retain more grains? :D

[Dark Shikari]

ooh, how about another random x264 project that will make that codec retain more grains? :DThat's hard... and I won't do it, because I hate grain with a passion. :p

[akupenguin]

That's hard... and I won't do it, because I hate grain with a passion. :p
All the more reason to implement FGM, if you ever watch encodes by people who like grain. It would make grain toggleable at playback time.

[Razorholt]

How about... x264 retaining more details then? :D:D yes?

[DeathTheSheep]

Also, today's random x264 project: create a completely new algorithm (based somewhat off of HEX) using simulated annealing (http://en.wikipedia.org/wiki/Simulated_annealing).

Woah, very nice. Would this take merange as a parameter?

And to the best of your reasoning (even if it's speculative), do you predict results of higher quality than UMH to be attained for a majority of sources?

[Dark Shikari]

Woah, very nice. Would this take merange as a parameter?

And to the best of your reasoning (even if it's speculative), do you predict results of higher quality than UMH to be attained for a majority of sources?
See the new thread :p

Right now it is completely independent of merange altogether, but it should not be too hard to make a parameter that basically affects the "distance" which the algorithm "prefers" to travel without affecting its other properties.

[Mug Funky]

All the more reason to implement FGM, if you ever watch encodes by people who like grain. It would make grain toggleable at playback time.

yeah, considering the HD era means grains are bigger and more prominent, and it's currently fashionable to shoot on very fast film (look at spider man 3). denoising HD is also quite tricky, so more often than not it simply isn't done.

still, when digital movie cameras get good we'll be seeing a whole lot less grain i suppose.

[R3Z]

How about... x264 retaining more details then? :D:D yes?

How about you use a bitrate more apropriate to movies rather than postage stamps :p

[Razorholt]

How about you use a bitrate more apropriate to movies rather than postage stamps :p

Even at 2500kbps x264 doesn't retain as much details as H.264 or even XviD - And I'm being very objective in my comment.

[akupenguin]

x264 doesn't retain as much details as H.264
That statement is meaningless. Maybe you meant a specific H.264 implementation other than x264?

[Sagekilla]

Even at 2500kbps x264 doesn't retain as much details as H.264 or even XviD - And I'm being very objective in my comment.

If you use deadzone settings plus a good matrix (Prestige) it can retain plenty of detail. Using Prestige matrix plus my (for all intents and purposes, insane, since it takes 15+ hours per encode) settings I can usually retain almost all of the detail from the source DVDs I rip @ crf 19.5. Then again, my movie rips typically tend to be 1/2 to 1/3 size of the original or somewhere thereabout, still good though. I use crf 19.5 and I typically get a bitrate of about 1600 - 1800 kbps, here's a sample clip using my insane settings: 60 second sample encode (http://skdotnet.sytes.net:45312/60_sample.mkv)

x264.exe --crf 20 --pass 1 --stats "H:\Movies\300\Stats.log" --ref 4 --mixed-refs --no-fast-pskip --bframes 16 --b-pyramid --weightb --b-rdo --bime --direct auto --filter -3:0 --partitions all --8x8dct --subme 7 --me umh --hadamard --trellis 0 --aq-strength 0.5 --aq-sensitivity 15 --progress --threads auto --thread-input --cqm "H:\Matrices\prestige.cfg" --output "H:\Movies\300\cropVideo.264" "H:\Movies\300\crop.avs"

[Razorholt]

What's your --deadzone settings?

[Sagekilla]

What's your --deadzone settings?

Standard, I didn't modify them at all.

Edit: To be more precise, --deadzone-inter 21 --deadzone-intra 11

[Razorholt]

So, your settings can help me compete with H.264 and get that sort of results? -> http://images.apple.com/movies/wb/300/300-tlr1b_h480p.mov (I know the sources aren't probably the same but I'm focusing on gains retention here, especially on skins)

Objectively, and post-processing aside, you're saying that x264 and H.264 can produce the same exact results at same bitrates, correct?

I remember Sharktooth making a comment on x264 and grains retention but I can't find the post... :(

[Terranigma]

What aku was saying, was that x264 is h.264, and that you weren't clear on what h.264 coder or codec you were talking about. Mainconcept? Elecard? Nero Recode? Ateme? Perhaps something else?

[Dark Shikari]

So, your settings can help me compete with H.264 and get that sort of results? -> http://images.apple.com/movies/wb/300/300-tlr1b_h480p.mov (I know the sources aren't probably the same but I'm focusing on gains retention here, especially on skins)

Objectively, and post-processing aside, you're saying that x264 and H.264 can produce the same exact results at same bitrates, correct?

I remember Sharktooth making a comment on x264 and grains retention but I can't find the post... :(
Here's what you're saying, paraphrased.

So, your engine mods can help me compete with cars and get that sort of results?

Objectively, you're saying that your Honda Civic and cars can reach the same exact speed in the same time, correct?

x264 is an implementation of H.264. :p

[Razorholt]

What aku was saying, was that x264 is h.264, and that you weren't clear on what h.264 coder or codec you were talking about. Mainconcept? Elecard? Nero Recode? Ateme? Perhaps something else?

Thanks Terranigma for the clarification. I use both Mainconcept and Nero.

[Dark Shikari]

Thanks Terranigma for the clarification. I use both Mainconcept and Nero.Mainconcept in most tests shows as being roughly tied with x264, though I hope to change that over the next few months with my x264 modifications.

Nero is much more limited and is considerably inferior I believe due to its encoder limitations.

[Sharktooth]

h.264 is a standard. x264 is an implementation of the h.264 standard.
now, about encoding fine details like grain, try lowering the deadzones (between 3 and 6 for intra and between 10 and 18 for inter).
keep in mind lowering the deadzones settings will require a higher bitrate.
also avoid to overcompress (using insane settings) coz some options may sacrifice fine details for a higher compression (coz metrics and human visual system are 2 completely different things).

[Terranigma]

Mainconcept in most tests shows as being roughly tied with x264, though I hope to change that over the next few months with my x264 modifications.


I always wondered what settings were used with these tests, because I can't get a quality encoding with mainconcept if I tried. Even using the suggested settings from the adobe doc. :p

I prefer x264 over these other encoders mainly because it's open source and gives you the freedom to control every aspect of the encoder. Take Mainconcept and Elecard for example; it won't let me use more than 3 b-frames. :mad:

[Razorholt]

Here's what you're saying, paraphrased.

So, your engine mods can help me compete with cars and get that sort of results?

Objectively, you're saying that your Honda Civic and cars can reach the same exact speed in the same time, correct?

x264 is an implementation of H.264. :p

Oookay... Let me correct what I wrote. I was asking whether MeGUI - that I love and cherish - and any other x264-based encoder can match Nero, MainConcept, etc... Is that better, Mister? :p

[Dark Shikari]

Oookay... Let me correct what I wrote. I was asking whether MeGUI - that I love and cherish - and any other x264-based encoder can match Nero, MainConcept, etc... Is that better, Mister? :p
Yes, I would personally state that in my opinion x264, with the proper settings, is vastly superior to all other H.264 encoders due to either better quality/bitrate, better customizability, or both, except in the following cases:

1. Interlaced encoding. x264 doesn't have full MBAFF/PAFF support.

2. Film Grain Modelling. Some of the fanciest/most expensive encoders, most not available to consumers, have FGM support. This gives a considerable advantage in compressing movies at high bitrates.

Some professional compressionists are on record as stating similar; that x264 outperforms most other commercial encoders.

MeGUI can use any settings you want with x264, so if it doesn't look as good as video compressed by a different H.264 implementation, check your settings first.

[Sharktooth]

Ehrr... MeGUI is just a GUI... it uses x264 for encoding. So does every GUI and every software that uses x264 for encoding. There are no x264-based encoders except x264 :D
And however, yes, IMHO x264 is as good if not better than other encoders. It's just a matter of how you configure it for encoding.

[akupenguin]

also avoid to overcompress (using insane settings) coz some options may sacrifice fine details for a higher compression (coz metrics and human visual system are 2 completely different things).
Your intent is correct, but your statement is misleading, so I'll rephrase it:
There is no such thing as "overcompress", except maybe "pick too low of a bitrate", which is unrelated to the current discussion.
You meant "overfit". Any lossy compression has to sacrifice some types of information in favor of other types of information. Optimizing for some metric is better than not optimizing for anything, even if that metric is very approximate. But overfitting to a model of distortion that isn't identical to HVS can cause the encoder to make such tradeoffs in cases that are detrimental to perceived quality.

[Terranigma]

Razorholt, compare HQ-Schizo (http://forum.doom9.org/showthread.php?p=1040887#post1040887) to whatever encoder you're using and post screenshots. :p

[Manao]

2. Film Grain Modelling. Some of the fanciest/most expensive encoders, most not available to consumers, have FGM support. This gives a considerable advantage in compressing movies at high bitrates.No. FGM helps at all bitrates, and I'd say it helps more at low bitrates than at high bitrates.

[Dark Shikari]

No. FGM helps at low bitrates, not at high bitrates.Yes, you're correct. My thought process was:

a) I remove grain when I encode at low bitrates.
b) Therefore, grain is only important at high bitrates.
c) Therefore, FGM is only useful at high bitrates.

But obviously FGM is useful at low bitrates in order to avoid a).

[Sharktooth]

Your intent is correct, but your statement is misleading, so I'll rephrase it:
There is no such thing as "overcompress", except maybe "pick too low of a bitrate", which is unrelated to the current discussion.
You meant "overfit". Any lossy compression has to sacrifice some types of information in favor of other types of information. Optimizing for some metric is better than not optimizing for anything, even if that metric is very approximate. But overfitting to a model of distortion that isn't identical to HVS can cause the encoder to make such tradeoffs in cases that are detrimental to perceived quality.
it's exactly what i meant but i was never able to explain things in the correct way, even in my native language... so thanks.

[Sagekilla]

Yes, I would personally state that in my opinion x264, with the proper settings, is vastly superior to all other H.264 encoders due to either better quality/bitrate, better customizability, or both, except in the following cases:

1. Interlaced encoding. x264 doesn't have full MBAFF/PAFF support.

2. Film Grain Modelling. Some of the fanciest/most expensive encoders, most not available to consumers, have FGM support. This gives a considerable advantage in compressing movies at high bitrates.

Some professional compressionists are on record as stating similar; that x264 outperforms most other commercial encoders.

MeGUI can use any settings you want with x264, so if it doesn't look as good as video compressed by a different H.264 implementation, check your settings first.

Yup, agreed on that point that x264 is superior to other encoders. Like Akupenguin said, he's giving us enough rope to hang ourselves with x264. With that said, with proper settings x264 blows away other consumer available codecs. You don't necessarily have to use insane settings like mine, I just do that so I can get the lowest possible file size short of enabling ESA. I've personally used only one other H.264 based encoder, namely Nero Digital, and I didn't quite like it's results.. The videos looked mushy considering the bitrate I was using and the settings I used (both pretty high)


Edit: Speaking of your first point, who even uses interlacing anymore? Unless you've somehow found interlaced content that will not deinterlace properly I see no point in even using the setting. It's an old technology from the early days of analog broadcasting that shouldn't have a place in today's progressive based LCD/Plasma/DLP/whatever displays.

[fields_g]

This might show how little I know about FGM, but if you encode at 320x240, then play it scaled larger (for example 960x720) would the grain pixels be at the scaled playback resolution?

If it is the playback resolution, wouldn't it be an argument for FGM potentially being benificial for lower resolution encodes also?

[foxyshadis]

FGM is normally implemented in the decoder, so unless the decoder scales on output, it'd be same as the source. (I don't know of any that do, although it's a good reason to make one.) If FGM was implemented in mplayer/ffdshow or even a renderer, then it's possible.

[akupenguin]

This might show how little I know about FGM, but if you encode at 320x240, then play it scaled larger (for example 960x720) would the grain pixels be at the scaled playback resolution?
The standard only specifies a syntax and semantics for describing the grain. So the player is allowed to upscale before reconstructing it. That said, the grain syntax doesn't allow for features smaller than 1 pixel, so your upscaling player would have to either extrapolate the high frequencies or somehow know that the grain description is supposed to apply to a higher resolution than was actually encoded. Maybe SVC can signal that.

[akupenguin]

Optimization idea for SATD ESA (possibly also UMH, but I'm not sure):
SATD(enc,ref) = sum(abs(hadamard(diff(enc,ref)))) = sub(abs(diff(hadamard(enc),hadamard(ref))).
Despite the two hadamards, that actually decreases the amount of computation. One of the hadamards is of the input block and so can be done only once per search. The other can be reused, since each 4x4 hadamard block is shared among (16 mvs offset by multiples of 4 pixels) * (several block sizes). This sharing is possible only after the above factoring, because that's what causes the different hadamards to have the same inputs.
There's also some sharing within the computation of hadamard(ref), e.g. run 1 row transform and then 4 column transforms at 1 pixel offsets.
And after reducing SATD to prefilter+SAD, lossless SEA should work. Though I'm not sure whether SEA will be able to eliminate many mvs, since it depends on certain statistics of the image, and the hadamard filtered image will be different from a natural image.
The disadvantage is that it takes lots of memory: 32 bytes per pixel per reference frame, as compared to 4 for SAD SEA, and 0 for DIA/HEX/UMH.

[Dark Shikari]

Optimization idea for SATD ESA (possibly also UMH, but I'm not sure):
SATD(enc,ref) = sum(abs(hadamard(diff(enc,ref)))) = sub(abs(diff(hadamard(enc),hadamard(ref))).
Despite the two hadamards, that actually decreases the amount of computation. One of the hadamards is of the input block and so can be done only once per search. The other can be reused, since each 4x4 hadamard block is shared among (16 mvs offset by multiples of 4 pixels) * (several block sizes). This sharing is possible only after the above factoring, because that's what causes the different hadamards to have the same inputs.
There's also some sharing within the computation of hadamard(ref), e.g. run 1 row transform and then 4 column transforms at 1 pixel offsets.
And after reducing SATD to prefilter+SAD, lossless SEA should work. Though I'm not sure whether SEA will be able to eliminate many mvs, since it depends on certain statistics of the image, and the hadamard filtered image will be different from a natural image.
The disadvantage is that it takes lots of memory: 32 bytes per pixel per reference frame, as compared to 4 for SAD SEA, and 0 for DIA/HEX/UMH.32 bytes per pixel per reference frame?

That's an entire gigabyte of memory for a 1080p clip encoded with 16 reference frames... :eek:

Your method would be lossless, but are you sure it outperforms my current method, which albeit not lossless appears "mostly lossless" in most cases (its not in the patch in the original post though)?

I would think any method that requires so much memory is infeasible and impractical.

[akupenguin]

You don't strictly need that much memory, but without it you can only reuse results within one search (or with more complexity, across block sizes within one ref). In that restricted case, it only reduces hadamards by a factor of ~25 compared to brute force. Does your lossy method eliminate 96% of the mvs?
Plus, who'd run 1080p 16ref SATD ESA on a wimpy computer?

[Dark Shikari]

You don't strictly need that much memory, but without it you can only reuse results within one search (or with more complexity, across block sizes within one ref). In that restricted case, it only reduces hadamards by a factor of ~25 compared to brute force. Does your lossy method eliminate 96% of the mvs?
Plus, who'd run 1080p 16ref SATD ESA on a wimpy computer?
A factor of 25?

Isn't that a bit of an overestimation, one would think? SAD ESA doesn't do nearly that much, does it?

My method does a full SAD ESA (not SEA) and then does SATD on, I'm guessing, about 1/10 - 1/5 of those.

[akupenguin]

SAD SEA runs the actual SAD on between 1/4 and 1/8 of the mvs (assuming merange=16).
But SAD SEA's efficiency has a different basis: how well you can estimate SAD scores with a faster metric. My proposed SATD ESA is based on redundant computations, not estimation.

Ok, so the 25 is for 16x16 partitions (whether or not you use the lots of memory). If you do use memory then it completely eliminates hadamards from smaller partitions. If you don't use any memory then it reduces hadamards by a factor of 13 in 16x8 partitions and 6 in 8x8 partitions. Either way, there's still a SAD ESA (to add up the results of the hadamards, not like your threshold).

[Dark Shikari]

SAD SEA runs the actual SAD on between 1/4 and 1/8 of the mvs (assuming merange=16).
But SAD SEA's efficiency has a different basis: how well you can estimate SAD scores with a faster metric. My proposed SATD ESA is based on redundant computations, not estimation.

Ok, so the 25 is for 16x16 partitions (whether or not you use the lots of memory). If you do use memory then it completely eliminates hadamards from smaller partitions. If you don't use any memory then it reduces hadamards by a factor of 13 in 16x8 partitions and 6 in 8x8 partitions. Either way, there's still a SAD ESA (to add up the results of the hadamards, not like your threshold).It sounds like it would be a bit more efficient, and truly lossless as compared to a normal SATD ESA, but on the other hand it would require a lot more coding to implement, especially given the different behavior required for each type of partition.

[akupenguin]

especially given the different behavior required for each type of partition.
No difference in behavior. With memory, the hadamard computations aren't actually done during ME, they're a prefilter like SEA's integral image, and my numbers are the amortized cost. Without memory, the difference in speedup factors is because the different partitions sizes have to filter the same area. i.e. The behavior differs now, and it won't after the proposed change.

[DeathTheSheep]

Plus, who'd run 1080p 16ref SATD ESA on a wimpy computer?
Very true, I was thinking the same thing. :p 16 refs is as slow as molasses as is (say that 6 times fast).

[Sagekilla]

Very true, I was thinking the same thing. :p 16 refs is as slow as molasses as is (say that 6 times fast).

That that that that that that! (Sorry, couldn't help it :p) Anyway, who'd run a 16 ref 1080p encode to begin with? Unless you have some dual socket kentsfield with at least 4 GB of RAM I doubt you'd be doing that. Besides, 4-6 refs sounds more realistic for that kind of encode.

[Dark Shikari]

Apparently the UMH mode might need some slight tweaking; its still using the same early termination, which is designed around SAD. Turning it off results in a catastrophic FPS drop, which suggests that its early terminating, well, a whole lot of the time more than with SAD.

I'm going to do some testing to see if it should be modified or not.

[akupenguin]

x264_satd_fpel.05.diff (http://akuvian.org/src/x264/x264_satd_fpel.05.diff) Your algorithm. Mostly cosmetic changes, but I did get a 8% speedup just by changing sadarray[] from column major to row major order.

x264_satd_fpel.06.diff (http://akuvian.org/src/x264/x264_satd_fpel.05.diff) Reusing hadamards. Faster than brute-force, but slower that your threshold.
It successfully eliminates almost all of the hadamards: from 20% (yours) to 4% of the cpu time. And the 20% is with SSSE3 while the 4% is plain C. However, 16bit SAD is slower than than 8bit SAD, so just "reducing motion search to SAD ESA" isn't enough.

[Dark Shikari]

x264_satd_fpel.05.diff (http://akuvian.org/src/x264/x264_satd_fpel.05.diff) Your algorithm. Mostly cosmetic changes, but I did get a 8% speedup just by changing sadarray[] from column major to row major order.

x264_satd_fpel.06.diff (http://akuvian.org/src/x264/x264_satd_fpel.05.diff) Reusing hadamards. Faster than brute-force, but slower that your threshold.
It successfully eliminates almost all of the hadamards: from 20% (yours) to 4% of the cpu time. And the 20% is with SSSE3 while the 4% is plain C. However, 16bit SAD is slower than than 8bit SAD, so just "reducing motion search to SAD ESA" isn't enough.Ah, so the SAD needs to be 16-bit because the SATD scores are higher than 255.

That's quite a patch; how much slower is it than my threshold? If its not much slower it would be preferable as it is indeed lossless, while my threshold (according to some reports) can fail to provide good results in some cases.

[akupenguin]

brute force: 1.03 fps
reuse: 1.76 fps
threshold: 2.60 fps

[Dark Shikari]

brute force: 1.03 fps
reuse: 1.76 fps
threshold: 2.60 fpsWhat happens if you take the SATD scores and scale them to fit in 0-255 (and, say, cut off the top 1% to avoid dealing with extremely high maximums)?

Would the precision loss be bad enough to decrease quality? And how much of a speed boost would it give?

Additionally, is there any way to combine my thresholding with your optimization?

[akupenguin]

Hadamard DC coefs are in the range 0-4080. And they really use that whole range, it's not just outliers. So you could downscale everything by a factor of 16, and it would become just an 8bit SAD. But I'm sure that will lose lots of precision. Or you could keep DC coefs at full precision in a separate array, and scale/clip AC which uses a much smaller typical range. Might be ok quality, but more complicated.

[Dark Shikari]

Hadamard DC coefs are in the range 0-4080. And they really use that whole range, it's not just outliers. So you could downscale everything by a factor of 16, and it would become just an 8bit SAD. But I'm sure that will lose lots of precision. Or you could keep DC coefs at full precision in a separate array, and scale/clip AC which uses a much smaller typical range. Might be ok quality, but more complicated.What exactly is a DC or AC coefficient? I have never found an explanation for these terms.

[akupenguin]

By analogy to Direct Current / Alternating Current. In any frequency-based transform, such as FFT, DCT, or Hadamard, the DC coefficient represents the average of the input window, and all the other coefficients are AC and represent differences between samples.

[akupenguin]

x264_satd_fpel.07.diff (http://akuvian.org/src/x264/x264_satd_fpel.07.diff) Threshold. Another 13% speedup because you weren't using sad_x3.

[Dark Shikari]

x264_satd_fpel.07.diff (http://akuvian.org/src/x264/x264_satd_fpel.07.diff) Threshold. Another 13% speedup because you weren't using sad_x3.SAD_X3 has that much of a speed increase? What about SAD_X4?

[akupenguin]

x4 is slower that x3 here, because typical meranges result in 4n+1 columns, so 3 sads are wasted if you do multiples of 4.
There shouldn't be any significant difference in speed per sad between x3 and x4, the two versions are just to allow for whatever number is convenient.

[DeathTheSheep]

How would you convert from the old threshold format to the new one?
"average-3*(average-min)/4" -> "(average+3*min)>>2"

Let's say I wanted the old one to be average-1*(average-min)/3; how would I translate this for the new one?
What does ">>" do anyway?

[akupenguin]

average-3*(average-min)/4 = average-average*3/4+min*3/4 = average*1/4+min*3/4 = (average+3*min)/4 = (average+3*min)>>2

[Dark Shikari]

How would you convert from the old threshold format to the new one?
"average-3*(average-min)/4" -> "(average+3*min)>>2"

Let's say I wanted the old one to be average-1*(average-min)/3; how would I translate this for the new one?
What does ">>" do anyway?
>> is just a bitshift; personally I think its pointless to say ">>2" instead of "/4" because its less clear to the reader yet both result in the exact same code due to compiler optimization.

[akupenguin]

The compiler can only optimize /4 into >>2 for unsigned values, because division of negative numbers has different rounding.

[DeathTheSheep]

I see. What is the bitshift to result in an equivalent of /10, or /5, for instance?

[Dark Shikari]

I see. What is the bitshift to result in an equivalent of /10, or /5, for instance?
That is vastly more complicated; powers of 2 are easy because its binary.

If I recall correctly, to divide by 5, you do something like (x * 0x66666667) >> 1.

[DeathTheSheep]

Gotcha. Yeah, I'll stick with division. :)

[edit] Never mind, definitely a compiler thing...

[Dark Shikari]

Gotcha. Yeah, I'll stick with division. :)The problem with division being that it can take upwards of 40-80 processor cycles depending on the CPU :p

[DeathTheSheep]

Ouch!!

Heck, according to my compiler, "(average+3*min)/10" != "average-3*(average-min)/10"!!

Apparently, I fail at algebra. :p

[akupenguin]

Heck, according to my compiler, "(average+3*min)/10" != "average-3*(average-min)/10"!!
You fail at algebra.

[Dark Shikari]

You fail at algebra.This. ;)

[DeathTheSheep]

Oh snap

[Inventive Software]

"(average+3*min)/10" != "average-3*(average-min)/10"

Apparently, I fail at algebra. :p

If all of that's your code, essentially it's wrong. If you're trying to replace the first with the second, it's still wrong.

If you want to get rid of divisors, here's a really piss-easy way to do it: 1/the number you want to not divide. In your case 1/10, which is 0.1, which is rational and easy to compute.

So your line (and feel free to correct me on this if I'm completely skywards) should be:

"(average+3*min)*0.1"

[Dark Shikari]

If all of that's your code, essentially it's wrong. If you're trying to replace the first with the second, it's still wrong.

If you want to get rid of divisors, here's a really piss-easy way to do it: 1/the number you want to not divide. In your case 1/10, which is 0.1, which is rational and easy to compute.

So your line (and feel free to correct me on this if I'm completely skywards) should be:

"(average+3*min)*0.1"
Of course what you're actually doing on an assembly level (pseudocode) is, assuming you add the required x264_emms() to stop the program from giving you infinities:

CLEAR MMX REGISTERS FOR FLOATS (EMMS, 6 clocks)
MOVE INTEGER min TO register (1 clock)
MOVE INTEGER average TO register (1 clock)
MULTIPLY INTEGER min BY 3 AND STORE IN min (3-7 clocks) Note GCC will convert this from min*3 to (min + min << 1)
ADD min AND average AND STORE IN min (1 clock)
CONVERT min FROM INTEGER TO FLOAT (Lots of clocks)
FLOATING POINT MULTIPLY min AND 0.1 AND STORE IN min (4-7 clocks)

Considering you're doing this to avoid an integer division, you're probably worse off than before.

Rule 1 of optimizing math: Don't convert between integers and floats unless you really really have to.
Rule 2: Floats are usually slower than ints.
Rule 3: In a program covered with MMX code, floats are an even worse idea.

This is why if you need to do integer division, you should either use fixed point division or use magic numbers.

[Inventive Software]

I thought he was trying to avoid division full stop! :confused:

I've also, most of the time, gone by the rule that multiplication is better than division. This isn't the case I assume?

So what if you were just working with floats... would it make sense then?

[Dark Shikari]

So what if you were just working with floats... would it make sense then?Yes.

The issue is that the cost of converting to float and EMMS, both of which are probably going to hold up the execution of the program, are likely nearly as bad as that of integer division itself.

[akupenguin]

In the case of integer division by a constant, gcc will convert division to multiplication.
It can't make the same optimization for floating-point division, because x/10.0 is not bitwise identical to x*0.1, unless you use -ffast-math to make it ignore the difference.
(uint32_t)x/10 => ((uint64_t)x*0xcccccccd)>>35
But as long as you're picking arbitrary fractions, it's better to make the denominator a small power of 2. Then gcc might be able to avoid the multiplication too, and just use shift or lea.

[akupenguin]

Did you compare various functions of (min,average) against constant ratios of min? The latter would allow some amount of SEA during the sadarray generation.

[Dark Shikari]

Did you compare various functions of (min,average) against constant ratios of min? The latter would allow some amount of SEA during the sadarray generation.I didn't try constant ratios of min, but that might not be a bad idea at all. I'll try it in a bit and post the results here.

I was just working on trying to optimize ME DIA but unfortunately the logic required to save 1 COST_MV call per DIA cycle takes more clock cycles than the saved COST_MV call anyways. I did manage to get a 3.6% speed boost with a 0.1% quality boost (negligable) by doing a full me-range radius-2 DIA and then 2 cycles of radius-1 DIA, so that could give a bit of a first-pass speed boost for encoding.

[Dark Shikari]

OK, here's your results:

Threshold: current with 3/4: 0.4 FPS and 0.10% quality loss over ideal

Threshold: current with 1/2: 0.32 FPS and 0.03% quality loss over ideal

Threshold: min*2: 0.26 FPS and 0.05% quality loss over ideal

Threshold: 3*min/2: 0.35 FPS and 0.07% quality loss over ideal

Threshold: 4*min/3: 0.39 FPS and 0.05% quality loss over ideal

Threshold: 5*min/4: 0.4 FPS and 0.01% quality loss over ideal

In other words the quality loss is negligible and meaningless as its basically random, and a min-only based threshold works quite well; this means you could implement a SAD SEA algorithm and then my current hadamard thresholding together, right?

[DeathTheSheep]

I like the last one quite a bit. :p 0.01%? I never thought I'd see that number in a threshold-based algo...

[Dark Shikari]

I like the last one quite a bit. :p 0.01%? I never thought I'd see that number in a threshold-based algo...Seen --subme 7's algorithm?

void x264_me_refine_qpel_rd( x264_t *h, x264_me_t *m, int i_lambda2, int i8 )

That uses a SATD threshold to decide when to do RD, quite a low one too; 17/16!

[akupenguin]

SATD SEA
x264_satd_fpel.10.diff (http://akuvian.org/src/x264/x264_satd_fpel.10.diff) : simple version
x264_satd_fpel.11.diff (http://akuvian.org/src/x264/x264_satd_fpel.11.diff) : sad_x3 version, might or might not be slightly faster. (The difference is much less than before, since there's fewer SADs and x3 adds some complexity to SEA.)
I used threshold=5/4, but the speed/quality tradeoff might be different now.