[New patch] Hadamard motion estimation

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