The specific example I've been working on today is YCbCr/YUV optimization. Say you know the reconstruction matrix (YUV->RGB) and you want to find the optimal YUV coefficients for some given RGB ?
Well the standard answer is you invert the reconstruction matrix and then multiply that by your RGB. That is wrong!.
In general what we are trying to solve here is a problem something like this :
13 * x + 17 * y = 200; 11 * x + 7 * y = 100; find x & y to minimize the error x & y are integers and bounded in [-100,100]I guess these types of problems are "integer programming" (this particular case is integer linear programming since my example is linear, but sometimes we have to do it on nonlinear problems), and integer programming is NP-hard , so there is no exact solution but brute force.
(more generally, minimize error E(x,y,..) subject to various linear constraints)
The usual approach is just to wave your hands around and pretend that your variables are actually continuous, work out the math for the solution as if they were, and then round to ints at the end.
The problem is that that can be arbitrarily far from the optimal solution. Obviously in some simple problems you can bound the error of using this approach, or you may even know that this is the minimum error, but in nasty problems it might be way off.
We saw this same issue before in DXT1
I've never really seen many pages or much reference on this kind of problem. I did at one point decide that I was sick of the approximate hacky solutions and tried to find some software package to do this for real and came up empty on real usable ones.
There are a few hacky tricks you can use :
1. Find the continuous solution, then for each float value try clamping it to various integers nearby. See which of these rounds is best. The problem is for an N variable problem this takes 2^N tries if all you try is floor and ceil, and really you'd like to try going +1 and -1 beyond that a few times.
2. You can always remove one linear variable. That is, if you can reduce the problem to just something like a x = b, then the optimal integer solution is just round(b/a). What that means is if you use some other approach for all but one variable (such as brute force search), then you can solve the last variable trivially.
3. Often the importance of the various variables is not the same, their coefficients in the error term may vary quite a bit. So you may be able to brute force search on just the term with the largest contribution to the error, and use a simpler/approximate method on the other terms.