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

Introduction to Run-Length Encoding (RLE)

Run-length encoding (RLE) is a simple form of lossless data compression that is widely used in imaging, especially for pixel art and simple graphics. In an era where AI-generated images and retro-style games are trending, understanding RLE helps you appreciate how data can be stored efficiently. For example, the viral pixel art from games like Minecraft or Stardew Valley often uses RLE to keep file sizes small. In this tutorial, we'll build Python functions to encode and decode image data using RLE, just like in your COP3502C homework.

Understanding the Basics

What is RLE?

RLE replaces sequences of repeated values (runs) with a count and the value. For instance, the flat data [0, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0, 2, 2] becomes [2, 0, 3, 2, 6, 0, 2, 2] in RLE: two zeros, three twos, six zeros, two twos. This is exactly how many retro games compress sprite data.

In your assignment, images are stored as lists of integers (0-15 for colors), with the first two numbers being width and height. Your job is to implement methods that convert between flat data (raw pixels) and RLE data, and also handle string representations (hex and delimited formats).

Implementing the Core Functions

Let's write each required method step by step. We'll use Python 3 and focus on clarity.

1. to_hex_string(data)

This function converts a list of integers (0-15) into a hexadecimal string without delimiters. Each integer maps to a hex digit (0-9, a-f). 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 get the hex representation without the '0x' prefix. This is essential for converting both raw and RLE data to a displayable string.

2. count_runs(flat_data)

Counts the number of runs (sequences of identical values) in flat data. For [15,15,15,4,4,4,4,4,4], there are 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 function helps determine the length of the encoded list (double the runs).

3. encode_rle(flat_data)

Encodes flat data into RLE format. We iterate through the list, counting consecutive identical values.

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 is the inverse of decoding. For the example, it returns [3,15,6,4].

4. get_decoded_length(rle_data)

Given RLE data (a list where even indices are counts, odd indices are values), compute the total number of pixels after decoding.

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

This is the counterpart to count_runs.

5. decode_rle(rle_data)

Decodes RLE data back to flat data.

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

For [3,15,6,4], it returns [15,15,15,4,4,4,4,4,4].

6. string_to_data(data_string)

Converts a hex string (like "3f64") into a list of integers. Each two-character hex pair? Actually, each character is one hex digit representing a value 0-15.

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

This is the inverse of to_hex_string.

7. to_rle_string(rle_data)

Converts RLE data to a human-readable string: for each run, the length in decimal (1-2 digits) followed by the value in hex (1 digit), separated by colons. Example: [15,15,6,4] becomes "15f:64".

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

8. string_to_rle(rle_string)

Parses a string like "15f:64" back into RLE data list.

def string_to_rle(rle_string):
    rle = []
    for part in rle_string.split(':'):
        # part is like "15f" where last character is hex value, rest is decimal count
        count = int(part[:-1])
        value = int(part[-1], 16)
        rle.append(count)
        rle.append(value)
    return rle

This is the inverse of to_rle_string.

Putting It All Together: The Menu-Driven Program

Your assignment requires a standalone program with a menu. We'll create a main() function that displays a welcome message, a color test, and 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).

Here's a skeleton:

def main():
    print("Welcome to RLE Image Processor!")
    ConsoleGfx.test_rainbow()
    image_data = None
    while True:
        print("\nRLE Menu")
        print("0. Exit")
        print("1. Load file")
        print("2. Load test image")
        print("3. Read RLE string")
        print("4. Read RLE hex string")
        print("5. Read flat hex string")
        print("6. Display image")
        print("7. Display RLE string")
        print("8. Display RLE hex")
        print("9. Display flat hex")
        choice = input("Select a Menu Option: ")
        if choice == '0':
            break
        elif 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_str = input("Enter an RLE string to be decoded: ")
            rle_data = string_to_rle(rle_str)
            image_data = decode_rle(rle_data)
        elif choice == '4':
            hex_str = input("Enter the hex string holding RLE data: ")
            rle_data = string_to_data(hex_str)
            image_data = decode_rle(rle_data)
        elif choice == '5':
            hex_str = input("Enter the hex string holding flat data: ")
            image_data = string_to_data(hex_str)
        elif choice == '6':
            ConsoleGfx.display_image(image_data)
        elif choice == '7':
            rle_data = encode_rle(image_data)
            print("RLE representation:", to_rle_string(rle_data))
        elif choice == '8':
            rle_data = encode_rle(image_data)
            print("RLE hex values:", to_hex_string(rle_data))
        elif choice == '9':
            print("Flat hex values:", to_hex_string(image_data))
        else:
            print("Invalid option.")

if __name__ == "__main__":
    main()

Note: ConsoleGfx is a provided class; you only need to implement the methods above.

Testing Your Implementation

Test with the smiley example from the assignment. For instance, loading the RLE string 28:10:6B:10:10B:10:2B:10:12B:10:2B:10:5B:20:11B:10:6B:10 should produce the correct image. Verify that encoding and decoding are inverses: decode_rle(encode_rle(flat)) should return the original flat data.

Also test edge cases: empty data, single run, maximum run length (127? Actually, runs can be any length, but in RLE for images, runs are often limited to 127 to fit in a byte; however, your assignment uses decimal counts, so no limit is specified).

Connecting to Real-World Trends

RLE is not just for homework; it's used in modern applications like streaming pixel art in the NFT space, where each unique image is stored efficiently. Also, many AI image generators use similar compression to reduce storage. Understanding RLE gives you a foundation for more advanced compression like Huffman coding or LZW, which are used in PNG and GIF formats.

In the world of competitive programming, RLE is a common technique for string compression problems. And if you're into retro game development, you'll use RLE to store tile maps and sprites.

Conclusion

By implementing these eight functions and a menu-driven program, you've mastered the core of run-length encoding in Python. This skill is directly applicable to your COP3502C homework and beyond. Remember to test thoroughly and match the expected output exactly. Good luck!