Monday, February 25, 2013

Tutorial 26 - RLE Image Compression for Spritely

1. Introduction

Todays tutorial is brought to you courtesy of Dermot Balson from the lovely city of Perth (the most remote city on Earth according to Bill Bryson). Dermot noted that Spritely (the image editor which comes with Codea) produces some fairly large and unwieldy image files. Given Dermot's background in compression he immediately worked out a way to dramatically reduce these files in size.

Essentially, Dermot creates an array of unique colours, and builds a string for each of them which consist of two-digit cell addresses. 

Let me hand over to Dermot (@Ignatz on the Codea Forum) to explain how it all works.

2. Description of RLE compression code

Run Length Encoding (RLE) is a well known compression technique. Essentially, you run through the cells, and every time the color changes, you store the last color and the number of cells it applied to.

The RLE code can be downloaded below and has several classes.

3. Functionality

The RLE compression code can turn any image (with reason - see below) into code strings, and the Decode function can reassemble the image from these strings.

It can take images from the libraries, or Spritely code, and convert to compressed code.

The ImageCoder:code function takes the image as input and prints the code to recreate it. 

The Test tab shows how this code is used. NB this function also returns the two strings required to decode the image. This is only for testing purposes so the Main tab can show how it works - in practice, users will use the printed code.

The Decoder:Decode function takes two strings as input and returns an image

The Main function carries out several tests:

  1. It reads in an image from the standard library, codes and then decodes it back to an image
  2. It takes an image created by Spritely code (in the IconImages tab), and encodes/decodes it back to an image
  3. The code strings created for the Spritely code are used in the Test tab to demonstrate how to use them to decode an image

All three images above are drawn on screen. The first two images have their originals drawn above them for comparison purposes.

4. Using it in Practice

The ImageCoder tab is needed to encode images.

The Decoder tab needs to be included in any project where you want to decode the RLE images.

5. Compression

The level of compression depends on many factors, but as one indication, the size of the Spritely code in this example is about 28,000 chars, compared to 1,000 chars for the RLE version.

To be fair, this is largely because the Spritely image has a background color, meaning all 1,024 cells have to be coded. An image without a background would be much smaller.

6. Image Limits

The practical limits on image size and complexity are processing speed and storage, because the greater the number of colors and cells, the more space we have to allow for each item. Currently, it can allow for up to 4,096 unique r,g,b,a combinations, and up to 4,096 characters of the same color in a sequence. Increasing storage from 3 to 4 chars per item would increase capacity by a factor of 16, but would blow out the data by 1/3.

There are all sorts of ways to tweak for speed, but this may be good enough. I will tweak if there is demand for it.

7. Download the Code

Dermot has been kind enough to share his RLE coding and decoding classes. It is very well commented, so you should have no problems in following what he has done. You can download the complete project (useful for pasting directly into Codea) or the individual classes using the links below:

  1. RLE Complete v1.lua - This includes all of the individual classes and test images.
  2. RLE Readme.lua - Replicates most of the text description shown above.
  3. RLE Main.lua - The Main tab from the complete project.
  4. RLE Coder.lua - The RLE coding class.
  5. RLE Decoder.lua - The RLE decoding class.
  6. RLE Test.lua - sample string to test decoding.
  7. Spritely Flag Image.lua - The flag image from the MineSweeper program, produced using Spritely and used here to demonstrate the compression capability of the RLE algorithm.