\nIdeally, FFmpeg<\/a> \/ Libav<\/a> should be able to handle this automatically. Indeed, FFmpeg used to be able to, at least at the time I wrote this post about ZMBV<\/a> and was unhappy with FFmpeg’s default results. Somewhere along the line, FFmpeg and Libav lost the ability to do this. I suspect it got removed during some swscale refactoring.<\/p>\n
Still, there’s no telling if the old system would have computed palettes correctly for QuickTime files.<\/p>\n
Distance Approach<\/strong> How to perform the matching? Find the palette entry that is closest to a given input pixel, where “closest” is the minimum distance as computed by the usual distance formula (square root of the sum of the squares of the diffs of all the components).<\/p>\n That means for each pixel in an image, check the pixel against 256 palette entries (early termination is possible if an acceptable threshold is met). As you might imagine, this can be a bit time-consuming. I wondered about a faster approach…<\/p>\n Lookup Table<\/strong> The first (0th) entry in the table is (FF, FF, FF), followed by (FF, FF, CC), (FF, FF, 99), and on down to (FF, FF, 00) when the green component gets knocked down and step and the next color is (FF, CC, FF). The first 36 palette entries in the table all have a red component of 0xFF. Thus, if an input RGB pixel has a red color closest to 0xFF, it must map to one of those first 36 entries.<\/p>\n I created a table which maps indices 0..215 to values from 5..0. Each of the R, G, and B components of an input pixel are used to index into this table and derive 3 indices ri, gi, and bi. Finally, the index into the palette table is given by:<\/p>\n For example, the pixel (0xFE, 0xFE, 0x01) would yield ri, gi, and bi values of 0, 0, and 5. Therefore:<\/p>\n The palette index is 5, which maps to color (0xFF, 0xFF, 0x00).<\/p>\n Validation<\/strong> One problem is that the regulation QuickTime palette actually has 40 more entries above and beyond the typical 216-entry color cube (rounding out the grand total of 256 colors). Thus, using the distance approach with the full default table provides for a little more accuracy.<\/p>\n However, there still seems to be a problem. Let’s check our old standby, the Big Buck Bunny logo image:<\/p>\n I can’t quite account for that big red splotch there. That’s the most notable difference between images 1 and 2 and the only visible difference between images 2 and 3.<\/p>\n To prove to myself that the distance approach is equivalent to the table approach, I wrote a Python script to iterate through all possible RGB combinations and verify the equivalence. If you’re not up on your base 2 math, that’s 224<\/sup> or 16,777,216 colors to run through. I used Python’s multiprocessing<\/a> module to great effect and really maximized a Core i7 CPU with 8 hardware threads.<\/p>\n So I’m confident that the palette conversion techniques are sound. The red spot is probably attributable to a bug in my WIP SMC encoder.<\/p>\n Source Code<\/strong>
\nWhen I started writing my SMC video encoder<\/a>, I needed to convert RGB (from PNG files) to PAL8 colorspace. The path of least resistance was to match the pixels in the input image to the default 256-color palette that QuickTime assumes (and is hardcoded into FFmpeg\/Libav).<\/p>\n
\n![\"\"](\"http:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2011\/08\/palette-distance-formula.png\" "\\"Palette")
\n<\/center><\/p>\n
\nI think this is the approach that FFmpeg used to use, but I went and derived it for myself after studying the default QuickTime palette table. There’s a pattern there– all of the RGB entries are comprised of combinations of 6 values — 0x00, 0x33, 0x66, 0x99, 0xCC, and 0xFF. If you mix and match these for red, green, and blue values, you come up with 6 * 6 * 6 = 216<\/code> different colors. This happens to be identical to the web-safe color palette<\/a>.<\/p>\n\r\n index = ri * 36 + gi * 6 + bi\r\n<\/pre>\n
\r\n index = 0 * 36 + 0 * 6 + 5\r\n<\/pre>\n
\nSo I was pretty pleased with myself for coming up with that. Now, ideally, swapping out one algorithm for another in my SMC encoder should yield identical results. That wasn’t the case, initially.<\/p>\n
\n![\"\"](\"http:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2011\/08\/bbb-title-distance-full-palette.png\" "\\"Logo,")
\nDistance approach using the full 256-color QuickTime default palette<\/em>
\n<\/center><\/p>\n
\n![\"\"](\"http:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2011\/08\/bbb-title-distance.png\" "\\"Logo,")
\nDistance approach using the 216-color palette<\/em>
\n<\/center><\/p>\n
\n![\"\"](\"http:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2011\/08\/bbb-title-table.png\" "\\"Logo,")
\nTable lookup approach using the 216-color palette<\/em>
\n<\/center><\/p>\n
\nUpdate August 23, 2011:<\/em> Here’s the Python code I used for proving equivalence between the 2 approaches. In terms of leveraging multiple CPUs, it’s possibly the best program I have written to date.<\/p>\n