AP CSP - U1-L9 Black and White Images with HEX

RLE (Run Length Encoding)

Images are all around us, from application icons to animated GIFs to photos. Image files can take up a lot of space, so computers employ a range of algorithms to compress image files. For the simplest of images, computers can use a compression algorithm called run-length encoding (RLE).

Bitmaps

Before we explore image compression, let's see how we can represent an image in binary without any compression. Here's a simple image, a 16x16 heart icon:

The heart icon is made up of only two colors, red and white, so a computer could represent it in binary by mapping red pixels to 1 and white pixels to 0. This is called a bitmap, since it's mapping pixels to bits. (technically red is more than 1 bit, but that will be discussed later on)

What did you notice as you scrolled through the image of the binary RUN LENGTH ENCODING?

Imagine that you had to read the bits above out to someone who was copying them down.

After a while, you might say things like "five zeroes" instead of "zero zero zero zero zero". Well, the computer can do that too...

RLE compression algorithm

In run-length encoding, the computer replaces each row with numbers that say how many consecutive pixels are the same color, always starting with the number of white pixels.

Going Left to Right, For example, the first row contains 3 white pixels, 2 red pixels, 5 white pixels, 2 red pixels, then 4 white pixels:

0001100000110000

This would be represented as follows:

3,2,5,2,4

The fourth row is interesting because it starts with a red pixel. Run-length encodings start with the number of white pixels, so this is how it'd be represented:

0,15,1

Here's the second row of the bitmap for the heart icon:

0011110001111000

How would that row be represented in RLE?

On your assignment,

Using the Image Below: What is its RLE? Going from L-R?

RLE decompression

When a computer uses run-length encoding, it should be able to perfectly recreate the image from the compressed representation—and so should we, if we follow the computer's strategy.

Using the Pixel Widget Tool. Decompress this and produce a Black and White Image, and then paste a photo of it in your assignment.

Page updated

Report abuse