{"id":243365,"date":"2016-06-26T20:32:08","date_gmt":"2016-06-27T03:32:08","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-project&#038;p=243365"},"modified":"2016-06-26T20:51:24","modified_gmt":"2016-06-27T03:51:24","slug":"rlgr","status":"publish","type":"msr-project","link":"https:\/\/www.microsoft.com\/en-us\/research\/project\/rlgr\/","title":{"rendered":"RLGR Entropy Coder"},"content":{"rendered":"<p>We have developed an efficient entropy coder for integer value data. We refer to this compression algorithm as a <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/adaptive-run-length-golomb-rice-encoding-of-quantized-generalized-gaussian-sources-with-unknown-statistics\/\">Run-Length Golomb-Rice<\/a> (RLGR) coder. The RLGR coder is very simple to implement, and uses backward adaptation of just a few parameters, based on previously-encoded symbols. That way, the <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" rel=\"noopener noreferrer\" target=\"_blank\" href=\"http:\/\/patft.uspto.gov\/netacgi\/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=7,580,585.PN.&OS=PN\/7,580,585&RS=PN\/7,580,585\">RLGR <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>encoder can quickly adapt to the statistics of the symbol source without any overhead of transmitting parameters associated with an estimated probability distribution function for the source symbols.<\/p>\n<p>Our <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/adaptive-run-length-golomb-rice-encoding-of-quantized-generalized-gaussian-sources-with-unknown-statistics\/\">DCC 2006 paper<\/a> shows that, in the limit of a near-stationary source, the RLGR encoder is nearly optimal (typically within 10%), for a wide range of sources in the class of <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" rel=\"noopener noreferrer\" target=\"_blank\" href=\"https:\/\/en.wikipedia.org\/wiki\/Generalized_normal_distribution\">generalized Gaussians<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, which can model source from broadly wide PDFs, such as near uniform, to highly concentrated PDFs, such as Laplacians.<\/p>\n<p>In many practical applications the symbol source is neither stationary nor ergodic, in some cases with rapid changes in local statistics, so the RLGR encoder can outperform other entropy encoders, such as modern adaptive arithmetic encoders.<\/p>\n<p>The RLGR coder is used as the entropy encoder for our <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/project\/jpeg-xr\/\">PTC<\/a> image encoder. It is also used by the Windows Remote Desktop Protocol since Windows 7 SP1, as part of the <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" rel=\"noopener noreferrer\" target=\"_blank\" href=\"https:\/\/msdn.microsoft.com\/en-us\/library\/ff635268.aspx\">RemoteFX<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> protocol.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We have developed an efficient entropy coder for integer value data. We refer to this compression algorithm as a Run-Length Golomb-Rice (RLGR) coder. The RLGR coder is very simple to implement, and uses backward adaptation of just a few parameters, based on previously-encoded symbols. That way, the RLGR encoder can quickly adapt to the statistics [&hellip;]<\/p>\n","protected":false},"featured_media":243431,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"research-area":[13551,13547],"msr-locale":[268875],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-243365","msr-project","type-msr-project","status-publish","has-post-thumbnail","hentry","msr-research-area-graphics-and-multimedia","msr-research-area-systems-and-networking","msr-locale-en_us","msr-archive-status-active"],"msr_project_start":"2000-10-31","related-publications":[],"related-downloads":[],"related-videos":[],"related-groups":[],"related-events":[],"related-opportunities":[],"related-posts":[],"related-articles":[],"tab-content":[],"slides":[],"related-researchers":[{"type":"user_nicename","value":"malvar","display_name":"Rico Malvar","author_link":"<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/malvar\/\" aria-label=\"Visit the profile page for Rico Malvar\">Rico Malvar<\/a>","is_active":false,"user_id":32786,"last_first":"Malvar, Rico","people_section":0,"alias":"malvar"}],"msr_research_lab":[],"msr_impact_theme":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/243365","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-project"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/243365\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/243431"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=243365"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=243365"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=243365"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=243365"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=243365"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}