Yeah, you are close. Let me summarize the state of the art like this: Basically all oric conversion algorithms are brute force with a bit of optimization. Brute force is something like the following:
For each line do: for each of the 40 octet apply one of the following command:
- use 2 color dithering with current bg/fg pair or 7-bg/7-fg pair
- change bg (all pixels are bg or 7-bg)
- change fg (all pixels are bg or 7-bg)
Evaluate the error and keep the line with the least error
This enumerates and select the best option between all the possibilities of oric-lines approximating the original picture. Voilà, that's all about brute force. Simple... at least in theory.
In theory? yes because actually the number of possibilities to examine is around 15**40 (> 1E+47) which is tremendous.
Sam Hocevar's reduces this number by not evaluating the full line, but only a small look-ahead from the current position. This reduces 15**40 to something like 40*(15**DEPTH) with DEPTH the look-ahead size (2 octets in libpipi). This reduces the search space to a few thousands cases giving very interresting results but sometimes clearly not optimal because the look-ahead is too small.
In my solution, I have found that some terms in the evaluation of the error can be neglected. This allows finding an approximation of the least-error values much much quicker (say in logarithmic time). The neglected terms are small enough for the result still be pretty good. Of course this isn't strictly the least-error solution, but who cares of being 1% away from the exact optimum when other methods are much worse by several orders of magnitude ?
So to sum up, Sam Hocevar find the exact optimum error over a (very) small subset of the search-space, wereas my algorithm find an estimation of the optimum, but on the full search-space.
Another small difference comes from the function evaluating the error. Sam Hocevar uses some empirically detemined formula around euclidean distance (combined with a bit of black magic of course) whereas I use an approximation of CIE's delta-E which is the
state of the art in how color differences are perceived by the human eye. This is less fancy than empirical black magic, but the results prove this is worth it (though not as much as approximating the extremum value vs approximating the state-space).