NP-Hard problems in x264

[daanking]

I was wondering what NP-hard (or NP-complete of course) problems are being solved or approximated by x264 during encoding. I am asking this because i have a general interest in these kind of problems, and i need some experience in these problems as well (doing a Master in this field at the moment). Also, the fact that one of the motion estimation algorithms is called exhaustive search does hint at the fact that something NP-hard is being solved exact. Finally, i use x264 on a regular basis, so if I can help, i would be very happy!

[Dark Shikari]

Practically all NP-Hard problems in x264 would fit into the category of "optimizing for a metric in the case that the optimization cannot be dynamically programmed." In particular, this covers basically everything that cannot be practically trellised.

One example of this is Quantization Noise Shaping, a method of optimizing quantization for an arbitrary quality metric. Uses a greedy algorithm: tests every possible +/-1 change in DCT coefficients from the current best and picks the best change, accepts it, and repeats the process until no better change is left. Suffers from many problems: the process is quite slow and not useful for improving mean squared error (trellis can do that much faster, since MSE can be measured in the frequency domain). Additionally, it tends to expose flaws in quality metrics; psy-RD, for example, does not work well with QNS. Finally, it's not optimal either; the greedy algorithm is an approximation for the actual solution, which is NP. QNS is not currently implemented in x264, but I have some very hacky patches I use for testing.

Practically all cases of optimizing multiple syntax elements at the same time (multiple macroblocks, motion vectors, etc) fall into a similar category due to the effects of CABAC. These can theoretically be trellised but the computational complexity of trellis becomes gargantuan when one attempts to deal with reasonably large datasets of that sort (say, an entire frame). In practice, iterative analysis would be useful in these cases (encode frame once, then encode it again with the knowledge from the first encode, see what changes, repeat until nothing changes). Snow uses this for motion search.

[daanking]

Sounds pretty tough! As i understand, QNS tries to find the optimal rounding of all pixel values (DCT coefficients), where the cost is an arbitray function. This means that there are 2^pixels different solutions (round up or down)... If the cost function is local (ie only depends on the pixel value itself, or maybe on its neighbours), there could be a few symmetries that can be exploited. Should be studied more though! My gut feeling is that the greedy approach is going to be pretty suboptimal, and tabu search or simulated annealing will be a bit better... These are harder put in a time frame, so maybe they are not good approaches.

What about motion estimation? Is there anything that can be improved there? I would love to help, but I come from a Physics background, so i am not really familiar with the ins and outs of video compression :o

[Dark Shikari]

Sounds pretty tough! As i understand, QNS tries to find the optimal rounding of all pixel values (DCT coefficients), where the cost is an arbitray function. This means that there are 2^pixels different solutions (round up or down)... If the cost function is local (ie only depends on the pixel value itself, or maybe on its neighbours), there could be a few symmetries that can be exploited. Should be studied more though! My gut feeling is that the greedy approach is going to be pretty suboptimal, and tabu search or simulated annealing will be a bit better... These are harder put in a time frame, so maybe they are not good approaches.Well the real challenge isn't optimizing rounding--it's optimizing for a quality metric that isn't mean squared error. Rounding itself is optimized pretty well with QNS but it only helps at quantizers roughly 15 and lower. It can help a whole lot at extremely low quantizers, but generally if you're at the point that it helps, the difference is going to be completely imperceptible.

It would be a good question though as to how well a greedy approach actually works. Simulated annealing might be a decent idea given the enormous size of the search space.

Speaking of enormous search spaces, a recent attempt of mine was to write a program to attempt to generate SIMD assembly code to perform an arbitrary shuffle operation on input values (i.e. the case where the values don't fit in one register and the shuffle involves moving values between registers). The resulting search space turned out to be so phenomenally large even for very small shuffles that it rendered all my approaches, regardless of heuristic, completely moot.What about motion estimation? Is there anything that can be improved there? I would love to help, but I come from a Physics background, so i am not really familiar with the ins and outs of video compression :oDrop by IRC, #x264dev on Freenode.

[akupenguin]

the fact that one of the motion estimation algorithms is called exhaustive search does hint at the fact that something NP-hard is being solved exact.
Exhaustive motion search is O(n^2) in the search range. UMH is O(n). And the fast searches are O(n) worst case, but sublinear on average.

Generally I consider anything worse than n*log(n) to be too slow. QNS, even after greedy approximation, is only remotely viable because n is limited to 16 or 64.

[Dark Shikari]

Generally I consider anything worse than n*log(n) to be too slow. QNS, even after greedy approximation, is only remotely viable because n is limited to 16 or 64.And QNS is still quite bad, potentially average-case N^3:

(Number of coefficients to search over) * (Cost of checking a single coefficient) * (Number of iterations that have to be made).

(Number of coefficients to search over) is probably roughly linear by transform size, and I would suspect (Number of iterations that have to be made) is also. Maybe slightly sublinear. (Cost of checking a single coefficient) is at best N and potentially worse, e.g. NlogN (in the case that you're using a frequency-transform-based quality metric).Exhaustive motion search is O(n^2) in the search range.Isn't it somewhat below n^2 across the "normal" range of ~8-64 because of SEA?

[akupenguin]

Isn't it somewhat below n^2 across the "normal" range of ~8-64 because of SEA?
Yes. One video closely fits cycles(merange) = 636*n+11.5*n^2. i.e. at merange=64, half of the cputime is in the n^2 term.