Compressed fonts? Yes please!

Intro

This is a brief first look at an idea I've been ruminating on for along time. Actually, it's two ideas - tweaking CCITT Group4 (T.6) image compression and compressing font data for use on microcontrollers. Why do either of these things occupy space in my head?

CCITT Group 4

Many years ago, a standard was created for the digital FAX machine. It specified not only the audio transmission method over POTS, but also a new bitonal, lossless digital image compression scheme. The 3rd meeting of these experts (Group3) created a one-dimensional run-length encoding scheme using statistical coding (Huffman) to shrink the most common run lengths for black text on a white background. Not long afterwards, at a 4th meeting, some clever person/people added a 2D component to it to take advantage of similarities between the current line and the one above it. They called this Group 4 compression The compression ratio increased quite a bit (up to 20:1), but so did the complexity of the codec. I got interested in digital imaging in the late 80's because of my first job (Motorola in Schaumberg, Illinois). They assigned me to create a system to scan blueprints into a digital format and chose CCITT Group4 as a good fit. This started my journey with imaging and specifically 1-bit (black and white) images. The G4 compression standard fascinated me both in its elegance and simplicity. I worked on optimized code for compressing and decompressing this data for many years, but I always had a feeling in the back of my mind that Group4 wasn't fully fleshed out. It felt like the 2D part was bolted on without thinking about how that changed the statistics of the run-length encoded part. It seemed to me that the Huffman coding part for "horizontal mode" as they call it, could be simplified to not need statistical coding. This could eliminate the fixed data tables and extra logic needed to decode them. I finally got a chance to test this theory. I created a test codec I call "Group5" 😆. It eliminates the horizontal mode Huffman coding and replaces it with a 'reasonable' fixed RLE scheme. For my test images (fonts), the difference in output size vs G4 is insignificant. In other words, I can get almost identical lossless image compression in a much simpler form.

Fonts on MCUs = The 'Why'

Now we get to the 'Why' part of my idea. CCITT G4 is still ubiquitous in TIFF and PDF files. It got "one-upped" not too long ago by JBIG2. It offers higher compression ratios and, who could have guessed, much more complex code. G4 is still useful because it compresses certain types of images really well and the decoder doesn't requires 1000s of lines of C code. Bitmap fonts are a special case of image data that happens to look a lot like the images that G4 was designed to compress. I had the idea to create a compressed font standard and G4 was almost a perfect fit. For small devices with tiny memories, the fast lookup tables to decode G4 are a little heavy. I tried it anyway. Here's a demo project which decodes TIFF G4 images to an e-paper display directly from an Arduino UNO (2K of RAM, 32K of FLASH):

This is close to what I was after, but the G4 decoder used up nearly half the FLASH space of the Arduino. 

Group5

With my new idea coded and working, I wanted to test it on bitmap font data. When drawing nice looking fonts on microcontrollers, a scalable TrueType font file is large (80-300K typical) and requires lots of code to render it into a bitmap. The compromise is to pre-draw one size of font from a TTF file as a bitmap font and use that on your MCU. A single size bitmap font can get quite large too. Applying my G5 idea to bitmap fonts seems like a perfect pairing. The data is compressed between 5 and 20:1 and the code needed to decompress it is compact. Here's what that looks like in practice:

In the photo above, the font displayed is a 56 point rendering of "Roboto_Black". The uncompressed font images take about 5.5K of space, while the compressed version is about 800 bytes. The larger the font, the higher the compression ratio you will get. e.g. for a 80pt version of the same font, the compression ratio increases to 10:1.

Where do we go from here?

I guess the next move is up to the companies and people that care about this kind of tech. I'm going to be testing and perfecting the idea for a bit before I share more details. Anyone with a commercial interest should contact me directly (bitbank@pobox.com).