3R encoding and hierarchical census data mapping

A project log for Recursive Range Reduction (3R) HW&SW CODEC

A high speed circuit design in JS and VHDL for decoding 3R bitstreams, a "quasi-entropy" code that compacts series of correlated numbers.

Yann Guidon / YGDES 08/26/2015 at 05:190 Comments

It just occured to me... in my sleep :-D

The 3R code is also useful for geographic (or geometric) data coding.

Imagine you're creating a zoomable map of, for example, human population on Earth based on a system lile or google maps.

You might have a database of every inhabitant, that's about 7 billion entries, but you can't store or send that much data to the browser. What you can do however is send hierarchical data, with local sums over a sub-range of the location of interest.

Let's say you divide the globe into a 16x16 grid. If this is mapped over the Earth, 1/2 will be 0s because of the water that covers the globe (it's more like 2/3 but think of the people living on the islands).

You just have to store and transmit a 16*16=256 numbers block to the viewer. Many of these numbers are 0s and they are close to each other, 3R loves to remove consecutive 0s. 3R also adjusts the coding size for all the other numbers.

Now zoom in on one of the sub-zones : your viewer will fetch the corresponding 16*16 sub-block for the local data but with only 255 numbers inside (since you already know the total sum from the "top block".

If you want to have more accuracy, since your viewer might have a 1024² graphic resolution, you'll download more consecutive sub-blocks, but depending on the zooming factor, your sub-blocks might have too much resolution : no problem ! 3R blocks can be "partially decoded" and you can modify the decoder so it only outputs partial sums at a given level, and not the actual values.

But for now, I'll stay focused on high speed lossless image (de)compression.