{"id":3041,"date":"2010-11-24T19:24:12","date_gmt":"2010-11-25T03:24:12","guid":{"rendered":"http:\/\/multimedia.cx\/eggs\/?p=3041"},"modified":"2010-11-24T19:24:12","modified_gmt":"2010-11-25T03:24:12","slug":"greed-is-good-greed-works","status":"publish","type":"post","link":"https:\/\/multimedia.cx\/eggs\/greed-is-good-greed-works\/","title":{"rendered":"Greed is Good; Greed Works"},"content":{"rendered":"

Greed, for lack of a better word, is good; Greed works.<\/em><\/a> Well, most of the time. Maybe.<\/p>\n

Picking Prediction Modes<\/strong>
\nVP8 uses one of 4 prediction modes to predict a 16×16 luma block or 8×8 chroma block before processing it (for luma, a block can also be broken into 16 4×4 blocks for individual prediction using even more modes).<\/p>\n

So, how to pick the best predictor mode? I had no idea when I started writing my VP8 encoder. I did not read any literature on the matter; I just sat down and thought of a brute-force approach. According to the comments in my code:<\/p>\n

\r\n\/\/ naive, greedy algorithm:\r\n\/\/   residual = source - predictor\r\n\/\/   mean = mean(residual)\r\n\/\/   residual -= mean\r\n\/\/   find the max diff between the mean and the residual\r\n\/\/ the thinking is that, post-prediction, the best block will\r\n\/\/ be comprised of similar samples\r\n<\/pre>\n
After removing the predictor from the macroblock, individual 4×4 subblocks are put through a forward DCT and quantized. Optimal compression in this scenario results when all samples are the same since only the DC coefficient will be non-zero. Failing that, when the input samples are at least similar to each other, few of the AC coefficients will be non-zero, which helps compression. When the samples are all over the scale, there aren’t a whole lot of non-zero coefficients unless you crank up the quantizer, which results in poor quality in the reconstructed subblocks.<\/p>\n
Thus, my goal was to pick a prediction mode that, when applied to the input block, resulted in a residual in which each element would feature the least deviation from the mean of the residual (relative to other prediction choices).<\/p>\n
Greedy Approach<\/strong>
\nI realized that this algorithm falls into the broad general category of “greedy” algorithms<\/a>— one that makes locally optimal decisions at each stage. There are most likely smarter algorithms. But this one was good enough for making an encoder that just barely works.<\/p>\n
Compression Results<\/strong>
\nI checked the total file compression size on my usual 640×360 Big Buck Bunny logo image while forcing prediction modes vs. using my greedy prediction picking algorithm. In this very simple test, DC-only actually resulted in slightly better compression than the greedy algorithm (which says nothing about overall quality).<\/p>\n\n\n\n\n\n\n\n
prediction mode<\/th>\nquantizer index = 0 (minimum)<\/th>\nquantizer index = 10<\/th>\n<\/tr>\n
greedy<\/td>\n286260<\/td>\n98028<\/td>\n<\/tr>\n
DC<\/td>\n280593<\/td>\n95378<\/td>\n<\/tr>\n
vertical<\/td>\n297206<\/td>\n105316<\/td>\n<\/tr>\n
horizontal<\/td>\n295357<\/td>\n104185<\/td>\n<\/tr>\n
TrueMotion<\/td>\n311660<\/td>\n113480<\/td>\n<\/tr>\n<\/table>\n
As another data point, in both quantizer cases, my greedy algorithm selected a healthy mix of prediction modes:<\/p>\n
    \n
  • quantizer index 0: DC = 521, VERT = 151, HORIZ = 183, TM = 65<\/li>\n
  • quantizer index 10: DC = 486, VERT = 167, HORIZ = 190, TM = 77<\/li>\n<\/ul>\n
    Size vs. Quality<\/strong>
    \nAgain, note that this ad-hoc test only measures one property (a highly objective one)– compression size. It did not account for quality which is a far more controversial topic that I have yet to wade into.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Producing a greedy, naive algorithm for choosing intra prediction modes in a VP8 video encoder<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[219],"tags":[],"class_list":["post-3041","post","type-post","status-publish","format-standard","hentry","category-vp8"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts\/3041","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/comments?post=3041"}],"version-history":[{"count":7,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts\/3041\/revisions"}],"predecessor-version":[{"id":3048,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts\/3041\/revisions\/3048"}],"wp:attachment":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/media?parent=3041"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/categories?post=3041"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/tags?post=3041"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}