Assignment Chef icon Assignment Chef
All English tutorials

Programming lesson

Run-Length Encoding in Python: A Step-by-Step Guide for Image Compression

Learn how to implement run-length encoding (RLE) in Python for image compression. This tutorial covers encoding, decoding, hex conversion, and a full menu-driven program, with examples inspired by pixel art and retro gaming.

run-length encoding Python RLE image compression Python RLE tutorial COP3502c homework encode RLE Python decode RLE Python Python hex conversion image compression Python pixel art compression Python programming assignment lossless compression Python RLE encoding example Python list manipulation Python menu-driven program retro gaming compression data compression techniques

Introduction to Run-Length Encoding (RLE)

Run-length encoding (RLE) is a simple form of lossless data compression that replaces consecutive repeated values with a count and the value. It's widely used in image compression, especially for pixel art and simple graphics like those found in retro games or icons. In this tutorial, you'll learn how to implement RLE encoding and decoding in Python, following the structure of a typical assignment like COP3502c HW 3 and 4.

We'll build functions step by step, then combine them into a menu-driven program. By the end, you'll be able to encode and decode image data, convert between hexadecimal and decimal, and display results. This is perfect for students looking to master loops, lists, string manipulation, and type casting in Python.

Understanding the Data Format

Images are represented as flat lists of pixel values (0-15 for 16 colors). The first two numbers are width and height. For example, a simple smiley face might have data: [8, 8, 0, 11, 11, 11, 11, 11, 11, 0, ...]. RLE compresses runs: instead of storing 6 consecutive 11s, we store [6, 11].

Throughout this tutorial, we'll use the example of a pixel art gator from the assignment. This keeps the examples relevant and helps you connect theory to practice.

Step 1: Converting Data to Hexadecimal String

Function to_hex_string(data) takes a list of integers (0-15) and returns a hex string without delimiters. Each integer becomes a single hex digit. For example, [3, 15, 6, 4] becomes "3f64".

def to_hex_string(data):
    return ''.join(hex(val)[2:] for val in data)

We use hex(val)[2:] to strip the '0x' prefix. This function is useful for debugging and display.

Step 2: Counting Runs in Flat Data

Function count_runs(flat_data) returns the number of runs. For example, [15,15,15,4,4,4,4,4,4] has two runs: three 15s and six 4s.

def count_runs(flat_data):
    if not flat_data:
        return 0
    runs = 1
    for i in range(1, len(flat_data)):
        if flat_data[i] != flat_data[i-1]:
            runs += 1
    return runs

This is the counterpart to get_decoded_length for encoding.

Step 3: Encoding Flat Data to RLE

Function encode_rle(flat_data) compresses the flat list into RLE format: a list of alternating run lengths and values. For [15,15,15,4,4,4,4,4,4], we get [3,15,6,4].

def encode_rle(flat_data):
    if not flat_data:
        return []
    rle = []
    count = 1
    for i in range(1, len(flat_data)):
        if flat_data[i] == flat_data[i-1]:
            count += 1
        else:
            rle.append(count)
            rle.append(flat_data[i-1])
            count = 1
    rle.append(count)
    rle.append(flat_data[-1])
    return rle

This algorithm is essential for compressing pixel runs, like the long runs of black (0) in the gator image.

Step 4: Getting Decoded Length from RLE

Function get_decoded_length(rle_data) returns the total number of pixels when decompressed. For [3,15,6,4], it's 3+6=9.

def get_decoded_length(rle_data):
    return sum(rle_data[::2])

This helps verify that the encoded data matches the expected image size.

Step 5: Decoding RLE to Flat Data

Function decode_rle(rle_data) expands RLE back to the original flat list. It's the inverse of encode_rle.

def decode_rle(rle_data):
    flat = []
    for i in range(0, len(rle_data), 2):
        count = rle_data[i]
        value = rle_data[i+1]
        flat.extend([value] * count)
    return flat

This is used to reconstruct the image for display.

Step 6: Converting Hex String to Data

Function string_to_data(data_string) converts a hex string (like "3f64") back to a list of integers. It's the inverse of to_hex_string.

def string_to_data(data_string):
    return [int(ch, 16) for ch in data_string]

This is crucial for reading RLE hex data from user input.

Step 7: Converting RLE Data to Human-Readable String

Function to_rle_string(rle_data) formats RLE data with decimal lengths and hex values, separated by colons. For [15,15,6,4], it returns "15f:64".

def to_rle_string(rle_data):
    parts = []
    for i in range(0, len(rle_data), 2):
        length = rle_data[i]
        value = hex(rle_data[i+1])[2:]
        parts.append(f"{length}{value}")
    return ':'.join(parts)

This matches the expected output format like "28:10:6b:10:...".

Step 8: Converting RLE String to Data

Function string_to_rle(rle_string) parses a string like "15f:64" back into RLE list [15,15,6,4].

def string_to_rle(rle_string):
    rle = []
    for part in rle_string.split(':'):
        length = int(part[:-1])
        value = int(part[-1], 16)
        rle.append(length)
        rle.append(value)
    return rle

This allows the program to load RLE data entered by the user.

Building the Menu-Driven Program

Now we combine all functions into a standalone program with a menu. The program should:

  • Display a welcome message and color test.
  • Show a menu with options to load data (file, test image, RLE string, RLE hex, flat hex) and display data (image, RLE string, RLE hex, flat hex).
  • Loop until the user chooses to quit (option 0).

Here's a skeleton:

def main():
    print("Welcome to RLE Image Processor!")
    ConsoleGfx.test_rainbow()
    image_data = None
    while True:
        print_menu()
        choice = input("Select a Menu Option: ")
        if choice == '1':
            filename = input("Enter name of file to load: ")
            image_data = ConsoleGfx.load_file(filename)
        elif choice == '2':
            image_data = ConsoleGfx.test_image
            print("Test image data loaded.")
        elif choice == '3':
            rle_string = input("Enter an RLE string to be decoded: ")
            rle_data = string_to_rle(rle_string)
            image_data = decode_rle(rle_data)
        elif choice == '4':
            hex_string = input("Enter the hex string holding RLE data: ")
            rle_data = string_to_data(hex_string)
            image_data = decode_rle(rle_data)
        elif choice == '5':
            hex_string = input("Enter the hex string holding flat data: ")
            image_data = string_to_data(hex_string)
        elif choice == '6':
            if image_data:
                ConsoleGfx.display_image(image_data)
        elif choice == '7':
            if image_data:
                rle = encode_rle(image_data)
                print("RLE representation:", to_rle_string(rle))
        elif choice == '8':
            if image_data:
                rle = encode_rle(image_data)
                print("RLE hex values:", to_hex_string(rle))
        elif choice == '9':
            if image_data:
                print("Flat hex values:", to_hex_string(image_data))
        elif choice == '0':
            break

Note: ConsoleGfx is a provided module for display and file loading. You must install the CS1 theme for proper color display.

Real-World Applications and Trends

RLE is used in image formats like BMP, PCX, and even in some video codecs. It's also popular in game development for compressing tile maps and sprite data. For example, in the classic game Super Mario Bros., the background clouds and bushes are created using RLE-like patterns. In modern AI image generation, RLE can be used to compress intermediate feature maps. Understanding RLE gives you a foundation for more advanced compression algorithms like Huffman coding or LZW.

In the context of the current trend of retro gaming revival (e.g., indie pixel art games), RLE is a perfect tool to learn. It's also a stepping stone to understanding how data is stored in formats like PNG (which uses DEFLATE).

Testing and Debugging Tips

Test each function with simple examples first. Use the provided test cases from the assignment. For instance:

  • to_hex_string([3, 15, 6, 4]) should return "3f64".
  • count_runs([15,15,15,4,4,4,4,4,4]) should be 2.
  • encode_rle([15,15,15,4,4,4,4,4,4]) should yield [3,15,6,4].
  • get_decoded_length([3,15,6,4]) should be 9.
  • decode_rle([3,15,6,4]) should return the original list.
  • string_to_data("3f64") should return [3,15,6,4].
  • to_rle_string([15,15,6,4]) should give "15f:64".
  • string_to_rle("15f:64") should return [15,15,6,4].

If your output doesn't match exactly, double-check your logic for edge cases like single runs or runs of length 1.

Conclusion

You've now implemented a complete RLE image compression tool in Python. This project reinforces key programming concepts: loops, lists, string manipulation, and type casting. By building a menu-driven interface, you also gain experience with user input and control flow. These skills are directly applicable to more complex projects in data compression, image processing, and game development.

As a next step, try extending the program to support saving RLE data to a file or adding more color formats. Happy coding!