{"id":16,"date":"2008-12-27T00:20:01","date_gmt":"2008-12-26T23:20:01","guid":{"rendered":"http:\/\/drmccoy.de\/gobsmacked\/?p=16"},"modified":"2009-06-12T01:28:50","modified_gmt":"2009-06-11T23:28:50","slug":"dithering-beauty","status":"publish","type":"post","link":"https:\/\/drmccoy.de\/gobsmacked\/?p=16","title":{"rendered":"Dithering Beauty"},"content":{"rendered":"

As a start, I’d like to talk a bit about dithering.
\nWhen I found out that Urban Runner’s VMD use the Indeo 3 codec for video frame data, I was a bit crushed: The resulting frames are in true color (in the YUV colorspace) and ScummVM doesn’t (yet?) support a true color mode for game graphics — only paletted 8-bit colors.<\/p>\n

So at first, to test the Indeo 3 decoder (copied from the great FFmpeg project<\/a>), I just wrote the frame to files. The results looked, after fiddling a bit, like that:<\/p>\n\n\n\n
\n
\"Frame<\/a>
Frame 10, true color<\/figcaption><\/figure>\n

\"Frame<\/a>
Frame 50, true color<\/figcaption><\/figure><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Note that the Indeo 3 frames are originally in YUV410, i.e. only the luminance (Y) channel is in full resolution while the two chrominance (U and V) channels are halved horizontally and vertically. Also, many frames are then again down-scaled, to save space.<\/p>\n

To get it displayed in ScummVM, my first idea was (ab)using ScummVM’s overlay (which does<\/em> support 16-bit graphics) for video playing, but that got shot down rather quickly in the IRC channel and I didn’t really like it either anyway.<\/p>\n

Therefore, I looked at what the original did when Windows ran in 256 color mode and saw, that it dithered the images using an ordered dithering algorithm. I read a bit about dithering in the Wikipedia and found that an error distribution algorithm would probably look far better. An error distribution dithering algorithm distributes the errors (the difference between the color wanted and the color that’s in the palette) on to the surrounding pixels.<\/p>\n

One problem: Dithering, no matter which exact algorithm, depends on finding the closed matching color in the palette. A quickly coded linear search in the palette proved to be far too slow for video playback, though. A binary search tree, my next idea, failed because there’s no meaningful ordering on color values.<\/p>\n

After googling a bit, I stumbled upon an octree, a tree with eight children on each node. The basic concept is that you take the upper-most bit of each color component, construct an integer out of these and use that integer as an index in the list of children. Then you continue with the next bits and put the palette index in the final leaf. When looking up, you just do the same with the color you look for and find the index in the leaf. The results were this:<\/p>\n\n\n\n
\n
\"Frame<\/a>
Frame 10, nearest color, octree<\/figcaption><\/figure>\n

\"Frame<\/a>
Frame 50, nearest color, octree<\/figcaption><\/figure><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Still not all that great, but I thought it was because the palette must be still messed up (since the surrounding image was also still a bit wrong).<\/p>\n

Then I implemented the dithering, Floyd-Steinberg namely:<\/p>\n\n\n\n
\n
\"Frame<\/a>
Frame 10, Floyd-Steinberg, octree<\/figcaption><\/figure>\n

\"Frame<\/a>
Frame 50, Floyd-Steinberg, octree<\/figcaption><\/figure><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

However, a short time later, I found the distribution matrix for the Sierra-2-4A (a.k.a. “Filter Light”) algorith, which looks very similar to Floyd-Steinberg but is faster — it only distributes the error on 4 instead of 5 pixels and all fractions are achievable by shifting. The result looked liked this:<\/p>\n\n\n\n
\n
\"Frame<\/a>
Frame 10, Sierra Light, octree<\/figcaption><\/figure>\n

\"Frame<\/a>
Frame 50, Sierra Light, octree<\/figcaption><\/figure><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

The very noticeable blobs I thought, as I already said, to be the effect of a broken palette, or of my dithering. However, I couldn’t find anything wrong with the palette loading and dithering code. Thankfully, eriktorbjorn told me that after changing the octree-lookup to a linear search, the video did look correct (albeit far too slow). When finally tried that as well, I found that he was right. So I fiddled a bit with the octree, then thought about how an octree actually<\/em> works. I came to the conclusion that it wouldn’t work correctly for finding a nearest matching color, at least not how I understood and implemented it (if anybody can prove me wrong there, please do<\/strong>).<\/p>\n

Hence, I swapped the octree with the only other structure I knew would work for such a task: a lookup table. Using the full 3*8bit color component, leading to a 16MB table, was obviously too much, so I compromised on using only the 6 most significant bits of each color component, like VGA does anyway.<\/p>\n

The plain nearest matching color with the lookup table:<\/p>\n\n\n\n
\n
\"Frame<\/a>
Frame 10, Nearest color, LUT<\/figcaption><\/figure>\n

\"Frame<\/a>
Frame 50, Nearest color, LUT<\/figcaption><\/figure><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

With Floyd-Steinberg dithering:<\/p>\n\n\n\n
\n
\"Frame<\/a>
Frame 10, Floyd-Steinberg, LUT<\/figcaption><\/figure>\n

\"Frame<\/a>
Frame 50, Floyd-Steinberg, LUT<\/figcaption><\/figure><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

With Sierra-Light dithering:<\/p>\n\n\n\n
\n
\"Frame<\/a>
Frame 10, Sierra Light, LUT<\/figcaption><\/figure>\n

\"Frame<\/a>
Frame 50, Sierra Light, LUT<\/figcaption><\/figure><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

One issue remained: While the palette has a complexity of O(1) in the lookup, building lies in O(n^4) (or O(n * m^3) if you reduce the color depth), which takes even on my 3GHz desktop noticeable time. Fortunately, _sev reminded me that the completely built table could be cached onto disk. Now the table can be loaded quickly after having been built only once.<\/p>\n

In closing, it’s now quite okay. Still, if somebody knows of a better way to find the nearest matching color in a fixed palette, please let me know<\/strong>.<\/p>\n","protected":false},"excerpt":{"rendered":"

As a start, I’d like to talk a bit about dithering. When I found out that Urban Runner’s VMD use the Indeo 3 codec for video frame data, I was a bit crushed: The resulting frames are in true color (in the YUV colorspace) and ScummVM doesn’t (yet?) support a true color mode for game […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[11,61,12],"tags":[17,19,18,21,62,20,64],"_links":{"self":[{"href":"https:\/\/drmccoy.de\/gobsmacked\/index.php?rest_route=\/wp\/v2\/posts\/16"}],"collection":[{"href":"https:\/\/drmccoy.de\/gobsmacked\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/drmccoy.de\/gobsmacked\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/drmccoy.de\/gobsmacked\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/drmccoy.de\/gobsmacked\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=16"}],"version-history":[{"count":46,"href":"https:\/\/drmccoy.de\/gobsmacked\/index.php?rest_route=\/wp\/v2\/posts\/16\/revisions"}],"predecessor-version":[{"id":217,"href":"https:\/\/drmccoy.de\/gobsmacked\/index.php?rest_route=\/wp\/v2\/posts\/16\/revisions\/217"}],"wp:attachment":[{"href":"https:\/\/drmccoy.de\/gobsmacked\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=16"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/drmccoy.de\/gobsmacked\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=16"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/drmccoy.de\/gobsmacked\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=16"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}