RLE Image Compression using 3 Colours

filmote · 2018-09-13 01:10:03 UTC

I asked for this thread to be split out as I think the concept that @dreamer3 suggest to improve compression could work nicely if a few minor issues were resolved:

Dreamer3 · 2018-09-12 06:58:37 UTC

You should treat is as 3 colors, black, white, and grey… for purposes of compression. Then a simple RLE compression should tidy up things nicely.

filmote · 2018-09-12 11:32:32 UTC

I have been thinking about his and are wondering how it might work.

Some examples:

{White,3}{Black,2}

would output:

11100

Introducing grey might give:

{White,3}{Black,2}{Grey,6}

with output:

11100101010

Dithering occurs with the following example:

{White,3}{Grey,6}{Black,2}
{Black,4}{Grey,6}{Black,1}

which gives:

11110101000
00001010101

But what if the RLE looked like this:

{White,3}{Grey,6}{Black,2}
{Black,3}{Grey,6}{Black,2}

The result would be:

11110101000
00010101000

The dithering is screwed up as they are not offset.

Solutions:

You could keep track of what alternation you used previously and apply the opposite. Attempting to keep track of what you did in an adjacent row will also lead to rendering errors - how do you know what the artwork is supposed to look like? Are they vertical lines or dithering??
You could attempt to make a rule that said if the row index is even then the white pixels that make up grey appear on even columns or something like that but this is always going to result in graphics rendering slightly wrongly.

Did you have anything else in mind? Has anyone else solved this??

filmote · 2018-09-13 01:15:34 UTC

The more I think about it you probably need a black / white / grey1 (leading off with a 1) and a grey2 (leading off with a zero) to achieve it. Otherwise you might need to put a single black or white pixel into the encoding to start it on the correct pixel which is counter-productive for compression.

The code to generate the encoding would need to be smart too.

Dreamer3 · 2018-09-14 03:19:49 UTC

Or dumb and the code that renders can just track which x,y it’s on and generate the “correct” white or black pixel based on even/odd and the line number.

drummyfish · 2018-09-14 05:29:53 UTC

Suggestion: Use stateful RLE. This would fit the odd number of colors nicely. I.e. instead of coding the blocks as:

{color, count} // 1

do

{change to color, count} // 2

In 1 you have to have 2 bits for the color with one invalid (wasted) option: 00 = black, 01 = grey, 10 = white, 11 = invalid. Even if you have even number of colors, this encoding is bad because you still have invalid (wasted) strings, e.g.: {white, 3}, {white, 2}.

In 2 you have only one bit for the color change: 0 (change to grey, or white if grey is current), 1 (change to black, or white if black is current).

I imagine grey would represent dithering, so don’t interpret is as “start alternating 0s and 1s” but rather as:

color = x % 2 == y % 2 ? 1 : 0

Which would give you correct dithering every time. However there are two possible dithering patterns (the other one being the above but inverted) – so you’d have to somehow indicate which one you use. This could be done by:

Having grey1 and grey2 as you say – this is bad for stateful RLE I mentioned above as you’d have even number of colors. OR
Assuming one dithering to be default and having a “switch to the other one” symbol in the code (again stateful behavior).

filmote · 2018-09-14 05:52:29 UTC

My concern is this (and you will need to forgive me as I am not sure I will be able to explain it accurately) Assume a section of a ball that has a dithered centre as shown in the top image If we were to move the ball 1 pixel to the left it would form the bottom image.

The dark '1’s represent the border of the ball and the ‘10’ pattern the dithering. The border is still 3 pixels wide as per the original image.

If we were to try to work out a rule that calculated the dithering based on row / col, I would expect the images to do this:

Notice how the ball’s border at this now looks like it has four pixels. If the ball was to continue from right to left, it would look like the border alternates between 3 and 4 pixels in width.

Obviously, we want the first scenario but this cannot be calculated from the row / col.

Yes … good point, we do not need an ‘absolute’ colour in the encoding just a change relative to the current colour. Unfortunately, if I am right in that we need a grey1 (starting with a zero) or a grey2 (starting with a 1) then we end need two bits to detail the change which happens to be the same as an absolute colour specification.

Hope I explained that well.

drummyfish · 2018-09-14 08:22:43 UTC

We can, just take the picture coordinates, not the screen coordinates.

Yes, this is what I mentioned too. As I said, you could maybe only keep 3 colors and assume grey to be grey1 by default. Then there could be a special symbol that would say “from now on use the other grey”.

EDIT:

But thinking about this, I don’t know how to distinguish this symbol from the normal blocks without adding extra bits.

EDIT2:

Another possible solution: the whole encoded image could start with a bit that would say if we use grey1 or grey2. If there are both of these in the picture, then bad luck, one would have to be encoded as blacks and whites (the compressing program would choose the one that would save more space). I think a typical Arduboy bitmap will only contain one prevalent type of dithering at most, so this might be okay.

filmote · 2018-09-14 10:39:46 UTC

Ah … that could work. Hadn’t thought of that.

Probably a reasonable assumption.

drummyfish · 2018-09-14 11:25:46 UTC

Creating a compression algorithm is about finding out, or mostly guessing, which are the frequent, most common cases, because every compression is just mapping the most frequent cases to the shortest codes (which also implies every compression algorithms will always inevitably make the uncommon cases bigger). So we should be thinking about what the typical image will look like. RLE itself is based on the assumption there are large spaces of the same color.

Now I am remembering I was once thinking about creating a vector image format for Arduboy, which is kind of a compression too. Basically there could be a script/tool that would convert an SVG image you make with e.g. Inkscape to a format that would store points, their connections, line width, maybe even shapes like ellipses etc… and then there would be a library that would be able to display this image at arbitrary resolutions. I think it would also enable creation of some interesting looking games (you’d be able to arbitrarily scale, rotate and otherwise transform images).

filmote · 2018-09-14 11:32:48 UTC

Correct. I used an RLE approach for my levels in Lode Runner. I had a routine that calculated the length of the compression using vertical runs, horizontal runs and using a simply ‘two tiles per byte’ and chose the best for each level. Where a level had long runs or large open spaces, the RLE obviously worked best. Where the levels had diagonal patterns the third approach worked best - no surprises there!

Pharap · 2018-09-14 23:11:15 UTC

I quite like this idea.

Essentially the pixel no longer indicates the colour, it indicates which ‘branch’ to take.

I think what you’d end up with is an effect like [Stan S. Stanman]

Not what you want, but quite amusing.

Fair point.

I know someone who pulled that off but never published it.
(Minus the tool to convert an SVG).

I wanted to do it once, but as usual, it ended up near the bottom of the todo heap.

filmote · 2018-09-18 09:35:11 UTC

I had a go at creating a 3 colour encoding. The results were less than spectacular

Three images

3 colour compression : 6 pixels
ArdBitmap : 8 pixels
Arduboy Cabi: 8 pixels

3 colour compression : 283 pixels
ArdBitmap : 178 pixels
Arduboy Cabi: 192 pixels

test_03

3 colour compression : 349 pixels
ArdBitmap : 283 pixels
Arduboy Cabi: 306 pixels

Header Format:

Bytes	Description
1 - 4 (4 bits)	Image height expressed in blocks of 8 bits. Range 0 - 8 / 0 to 64 bits.
5 - 12 (8 bits)	Image width expressed in pixels. Range 0 - 255.
13 - 15 (3 bits)	Length of bits to describe a ‘small run’. Range 1 - 7.
N/A	‘Long runs’ are ‘small run’ * 3 bits in length.

Each Run Format

Bytes	Description
1 - 2 (2 bits)	Colour - 0 = black, 1 = white, 2 = grey.
1 3 (1 bit)	Is this a short run (0) or long (1).
4 - ?	Refer to the number of bits in the header setting for short run.The run is either ‘short run’ or ‘long run’ in length.

My code is here > https://github.com/filmote/Compress

Compression Code (in Java)

You will note that it tries a number of ‘short Run’ lengths to see which gives the best compression.

import java.awt.image.BufferedImage;
import java.io.ByteArrayOutputStream;
import java.io.File;
import java.io.IOException;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import javax.imageio.ImageIO;

public class Compress {
	
	public static void main(String[] args) {
		
		BufferedImage image;
		String output = new String();
				
		try {

			if (args.length == 0) { throw new Exception("An image name needs to be specified."); }
			
			File f = new File(args[0]);
			String fileName = f.getName();
			
			image = ImageIO.read(new File(args[0]));

			int originalSize = ((image.getHeight() / 8) * image.getWidth()) + 2;
			
			for (int i = 2; i < 7; i++) {
				
				String newOutput = getEncoding(i, image);
				
				if (output.length() == 0 || newOutput.length() < output.length()) {
					output = newOutput;
				}
				
			}
			
			
			Pattern pattern = Pattern.compile(",");
			Matcher matcher = pattern.matcher(output);
			
			int newSize = 0;
			while (matcher.find()) {
				newSize++;
			}
			
			
			System.out.println("const uint8_t PROGMEM " + fileName + "[] {");
			System.out.println(output);
			System.out.print("};\n\n");
			System.out.print("Original: " + originalSize + " bytes");
			System.out.print("\nCompressed: " + newSize + " bytes");
			System.out.print("\nRatio " + String.format( "%.2f", (newSize / (float)originalSize)));
			
			
		}
		catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}
	
	private static String getEncoding(int shortRun, BufferedImage image) {

		int short_run_length_in_bits = shortRun;								// Can have a value between 1 and 7. 
		int long_run_length_in_bits = short_run_length_in_bits * 3;

		int short_run_length = (1 << short_run_length_in_bits);
		int long_run_length = (1 << long_run_length_in_bits);

		ByteArrayOutputStream baos = new ByteArrayOutputStream();
		BitStream bitStream = new BitStream(baos);
		
		try {

			StringBuffer pixels = new StringBuffer();
			
			for (int x = 0; x < image.getWidth(); x++) {

				for (int y = 0; y < image.getHeight(); y++) {

					int p = image.getRGB(x, y);
					int a = (p >> 24) & 0xff;
					int r = (p >> 16) & 0xff;
					int g = (p >> 8) & 0xff;
					int b = p & 0xff;
					int avg = (r + g + b) / 3;

					pixels.append((avg > 127 ? "1" : "0"));
				}
				
			}
			
			
			// Convert runs of 1010 (dithering pixels) to 2, first pass ..

			Pattern p = Pattern.compile("1010");
			Matcher m = p.matcher(pixels.toString());
			pixels = new StringBuffer();
			 
			while (m.find()) {
			    m.appendReplacement(pixels, "22");
			}
			m.appendTail(pixels);
			
			
			// Second pass ..

			p = Pattern.compile("210");
			m = p.matcher(pixels.toString());
			pixels = new StringBuffer();
			 
			while (m.find()) {
			    m.appendReplacement(pixels, "22");
			}
			m.appendTail(pixels);
			
			
			
			// Header ..
			
			bitStream.putBits(image.getHeight() / 8, 4);
			bitStream.putBits(image.getWidth(), 8);
			bitStream.putBits(short_run_length_in_bits, 3);
	
			
			int i = 0;
			while (i < pixels.length()) {
				
				int run = 0;
				int colour = Integer.parseInt(Character.toString(pixels.charAt(i)));
				
				while (Integer.parseInt(Character.toString(pixels.charAt(i))) == colour) {
					
					run++;
					i++;
					
					if (i == pixels.length()) break;
					if ((run + 1) == long_run_length) break;
					
				}
				
				bitStream.putBits(colour, 2);
				
				if (run < short_run_length) {
					bitStream.putBit(0);
					bitStream.putBits(run, short_run_length_in_bits);
				}
				else {
					bitStream.putBit(1);
					bitStream.putBits(run, long_run_length_in_bits);				
				}
				
			}
			
			bitStream.close();
			return baos.toString();
			
		} 
		catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		return null;

	}

}

Decompression code in c++

void draw3ColourCompressed(int16_t sx, int16_t sy, const uint8_t *bitmap, uint8_t color) {

	// set up decompress state
	BitStreamReader cs = BitStreamReader(bitmap);

	// read header
	uint8_t height = (int)cs.readBits(4) * 8;
	uint8_t width = (int)cs.readBits(8);
	uint8_t shortRun = (int)cs.readBits(3);
	uint8_t longRun = 3 * shortRun;

  uint8_t x = 0;
  uint8_t y = 0;

	// no need to draw at all if we're offscreen
	if ((sx + width < 0) || (sx > WIDTH - 1) || (sy + height < 0) || (sy > HEIGHT - 1))
		return;
	
	while (1) {

		uint8_t spanColour = (uint8_t)cs.readBits(2);
		uint8_t isShortRun = ((uint8_t)cs.readBits(1) == 0);
		uint16_t run = 0;
		
		if (isShortRun) {
			run = (uint8_t)cs.readBits(shortRun);
		}
		else {
			run = (uint8_t)cs.readBits(longRun);
		}
		
		for (uint8_t i = 0; i < run; i++) {
			
			switch (spanColour) {
			
				case BLACK:
				case WHITE:
					arduboy.drawPixel(sx + x, sy + y, spanColour);
					y++;  if (y == height) { y = 0; x++; }
					break;
					
				default:
					arduboy.drawPixel(sx + x, sy + y, WHITE);
					y++;  if (y == height) { y = 0; x++; }

					arduboy.drawPixel(sx + x, sy + y, BLACK);
					y++;  if (y == height) { y = 0; x++; }
					
			}
			
		}

		if (x >= width) break;
		
	}
}

The problem with this code is that a single pixel takes 6 or so bits. It gets a lot better for runs of a single colour and better still for runs of grey.

Rather than ‘hard code’ a short or long run length, maybe I need to look at something like the Arduboy Cabi compression where the run length is a variable length encoding as well.

filmote · 2018-09-19 05:22:54 UTC

I quickly converted the code to use the same run encoding method as Arduboy’s Cabi compression.

Surely, with 3 colours it would be better than the standard cabi - especially on the 3rd image above that has ‘lots’ of grey.

Unfortunately no … it clocks in at 306 pixels which is 2 bytes more! I am not sure how that can be but I have had to add a single bit per colour change which the original did not have but I would have thought the savings on the third colour would significantly outweight this.

More likely, I have missed something in my code!

import java.awt.image.BufferedImage;
import java.io.ByteArrayOutputStream;
import java.io.File;
import java.io.IOException;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import javax.imageio.ImageIO;

public class Compress {
	
	public static void main(String[] args) {

		BufferedImage image;
		String output = new String();
				
		try {

			if (args.length == 0) { throw new Exception("An image name needs to be specified."); }
			
			File f = new File(args[0]);
			String fileName = f.getName();
			
			image = ImageIO.read(new File(args[0]));

			int originalSize = ((image.getHeight() / 8) * image.getWidth()) + 2;

			output = getEncoding(image);
				
			
			
			Pattern pattern = Pattern.compile(",");
			Matcher matcher = pattern.matcher(output);
			
			int newSize = 0;
			while (matcher.find()) {
				newSize++;
			}
			
			
			System.out.println("const uint8_t PROGMEM " + fileName + "[] {");
			System.out.println(output);
			System.out.print("};\n\n");
			System.out.print("Original: " + originalSize + " bytes");
			System.out.print("\nCompressed: " + newSize + " bytes");
			System.out.print("\nRatio " + String.format( "%.2f", (newSize / (float)originalSize)));
			
			
		}
		catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}
	
	private static String getEncoding(BufferedImage image) {

		ByteArrayOutputStream baos = new ByteArrayOutputStream();
		BitStream bitStream = new BitStream(baos);
		
		try {

			StringBuffer pixels = new StringBuffer();
			
			for (int x = 0; x < image.getWidth(); x++) {

				for (int y = 0; y < image.getHeight(); y++) {

					int p = image.getRGB(x, y);
					int a = (p >> 24) & 0xff;
					int r = (p >> 16) & 0xff;
					int g = (p >> 8) & 0xff;
					int b = p & 0xff;
					int avg = (r + g + b) / 3;

					pixels.append((avg > 127 ? "1" : "0"));
				}
				
			}
			
			
			// Convert runs of 1010 (dithering pixels) to 2, first pass ..

			Pattern p = Pattern.compile("1010");
			Matcher m = p.matcher(pixels.toString());
			pixels = new StringBuffer();
			 
			while (m.find()) {
			    m.appendReplacement(pixels, "22");
			}
			m.appendTail(pixels);
			
			
			// Second pass ..

			p = Pattern.compile("210");
			m = p.matcher(pixels.toString());
			pixels = new StringBuffer();
			 
			while (m.find()) {
			    m.appendReplacement(pixels, "22");
			}
			m.appendTail(pixels);
			
			
			// Header ..
			
			bitStream.putBits(image.getHeight() / 8, 4);
			bitStream.putBits(image.getWidth(), 8);

			int originalColour = Integer.parseInt(Character.toString(pixels.charAt(0))); 
			
			bitStream.putBits(originalColour, 2);
			boolean firstRun = true;
			
			int i = 0;
			while (i < pixels.length()) {
				
				int run = 0;
				int colour = Integer.parseInt(Character.toString(pixels.charAt(i)));
				
				while (Integer.parseInt(Character.toString(pixels.charAt(i))) == colour) {
					
					run++;
					i++;
					
					if (i == pixels.length()) break;
//					if ((run + 1) == long_run_length) break;
				}
				
				if (!firstRun) {
					
					switch (originalColour) {
					
						case 0: 
							switch (colour) {
								case 1: bitStream.putBit(0); break;	
								case 2: bitStream.putBit(1); break;
							}
							break;
							
						case 1: 
							switch (colour) {
								case 2: bitStream.putBit(0); break;	
								case 0: bitStream.putBit(1); break;
							}
							break;
							
						case 2: 
							switch (colour) {
								case 0: bitStream.putBit(0); break;	
								case 1: bitStream.putBit(1); break;
							}
							break;
						
					}
					
				}
				else {

					firstRun = false;
				
				}
				
				int numberOfBits = (Integer.toBinaryString(run).length() / 2);
			
				for (int j = 0; j < numberOfBits; j++) { 
					bitStream.putBit(0); 
				} 
				bitStream.putBit(1);
				
				numberOfBits = Integer.toBinaryString(run).length();
				if (numberOfBits % 2 == 0) numberOfBits++;
				
				bitStream.putBits(run, numberOfBits);	
				
			}
			
			bitStream.close();
			return baos.toString();
			
		} 
		catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		return null;

	}

}

filmote · 2018-09-20 00:02:31 UTC

And some minor changes and comments:

Compression:

import java.awt.image.BufferedImage;
import java.io.ByteArrayOutputStream;
import java.io.File;
import java.io.IOException;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import javax.imageio.ImageIO;

public class Compress {
	
	public static void main(String[] args) {

		BufferedImage image;
		String output = new String();
				
		try {

			if (args.length == 0) { throw new Exception("An image name needs to be specified."); }
			
			File f = new File(args[0]);
			String fileName = f.getName();
			
			image = ImageIO.read(new File(args[0]));

			int originalSize = ((image.getHeight() / 8) * image.getWidth()) + 2;

			output = getEncoding(image);
				
			
			
			Pattern pattern = Pattern.compile(",");
			Matcher matcher = pattern.matcher(output);
			
			int newSize = 0;
			while (matcher.find()) {
				newSize++;
			}
			
			
			System.out.println("const uint8_t PROGMEM " + fileName + "[] {");
			System.out.println(output);
			System.out.print("};\n\n");
			System.out.print("Original: " + originalSize + " bytes");
			System.out.print("\nCompressed: " + newSize + " bytes");
			System.out.print("\nRatio " + String.format( "%.2f", (newSize / (float)originalSize)));
			
			
		}
		catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}
	
	private static String getEncoding(BufferedImage image) {

		ByteArrayOutputStream baos = new ByteArrayOutputStream();
		BitStream bitStream = new BitStream(baos);
		
		try {

			StringBuffer pixels = new StringBuffer();
			
			
			// Read the entire image into an array.  Thank god the images are small!
			
			for (int x = 0; x < image.getWidth(); x++) {

				for (int y = 0; y < image.getHeight(); y++) {

					int p = image.getRGB(x, y);
					int a = (p >> 24) & 0xff;
					int r = (p >> 16) & 0xff;
					int g = (p >> 8) & 0xff;
					int b = p & 0xff;
					int avg = (r + g + b) / 3;

					pixels.append((avg > 127 ? "1" : "0"));
				}
				
			}
			
			
			// Convert runs of 1010 (dithering pixels) to 2, first pass ..

			Pattern p = Pattern.compile("1010");
			Matcher m = p.matcher(pixels.toString());
			pixels = new StringBuffer();
			 
			while (m.find()) {
			    m.appendReplacement(pixels, "22");
			}
			m.appendTail(pixels);
			
			
			// Second pass ..

			p = Pattern.compile("210");
			m = p.matcher(pixels.toString());
			pixels = new StringBuffer();
			 
			while (m.find()) {
			    m.appendReplacement(pixels, "22");
			}
			m.appendTail(pixels);
			
			
			// Header ..
			
			bitStream.putBits(image.getHeight() / 8, 4);
			bitStream.putBits(image.getWidth(), 8);

			int originalColour = Integer.parseInt(Character.toString(pixels.charAt(0))); 
			
			bitStream.putBits(originalColour, 2);
			boolean firstRun = true;
			
			int i = 0;
			while (i < pixels.length()) {
				
				int run = 0;
				int colour = Integer.parseInt(Character.toString(pixels.charAt(i)));
				
				while (Integer.parseInt(Character.toString(pixels.charAt(i))) == colour) {
					
					run++;
					i++;
					
					if (i == pixels.length()) break;

				}
				
				if (!firstRun) {
					
					// Colour switches are relative to the previous colour.
					// 
					// Black = 0, White = 1 and Grey = 2.  A switch value of zero increases
					// the colour by one (eg Black -> White or Grey -> Black) whereas a 
					// value of one increases the colour by two (eg Black -> Grey or White ->
					// Black).
					//
					switch (originalColour) {
					
						case 0: 
							switch (colour) {
								case 1: 
									bitStream.putBit(0); 		// Changing from Black to White
									break;	
								case 2: 
									bitStream.putBit(1); 		// Changing from Black to Grey
									break;
							}
							break;
							
						case 1: 
							switch (colour) {
								case 2: 
									bitStream.putBit(0); 		// Changing from White to Grey
									break;	
								case 0: 
									bitStream.putBit(1); 		// Changing from White to Black
									break;
							}
							break;
							
						case 2: 
							switch (colour) {
								case 0: 
									bitStream.putBit(0);		// Changing from Grey to Black 
									break;	
								case 1: 
									bitStream.putBit(1); 		// Changing from Grey to White
									break;
							}
							break;
						
					}
					
					originalColour = colour;
					
				}
				else {

					firstRun = false;
				
				}
				
				
				// The run length is encoded in two parts - the number of bits to read
				// followed by the actual value itself.  The number of bits to read is 
				// written as a number of zeroes followed by a single 1 where each zero
				// contributes two to the calculation of bits to read.
				//
				// To make the representation smaller, it is assumed that all runs will
				// have at least 1 pixel.  Each increment adds two resulting in odd number
				// bit lengths only.
				//
				// The actual code is shown below:
				//
				// uint16_t bitLength = 1;
			    // while (cs.readBits(1) == 0)
			    //    bitLength += 2;
				// 
				// Examples:
				// 1         - Run length in bits = 1
				// 01        - Run length in bits = 3
				// 001       - Run length in bits = 5
				// 0001      - Run length in bits = 7
				// 00001     - Run length in bits = 9 ..
				//
				int numberOfBits = (Integer.toBinaryString(run).length() / 2);
				
				for (int j = 0; j < numberOfBits; j++) { 
					bitStream.putBit(0); 
				} 
				bitStream.putBit(1);
				
				
				// Output the run.  If the numberof bits is even then output a leading zero ..
				
				numberOfBits = Integer.toBinaryString(run).length();
				if (numberOfBits % 2 == 0) numberOfBits++;
				bitStream.putBits(run, numberOfBits);	
				
			}
			
			bitStream.close();
			return baos.toString();
			
		} 
		catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		return null;

	}

}

And some validation:

Dreamer3 · 2018-09-21 00:21:35 UTC

Just off the top of my head:

I’d consider forgetting different run lengths and just have a single run length in the header and let the compression code try multiple run lengths to find out which provides the best compression ratio. Seems your wasting a lot of space storing run length - does it actually pay off?

If you don’t need transparency you also have “half a bit” left in the color that you could use for something… for example you could pick the most variant color (most deviation in the run length) and give it TWO color slots:

00 black (normal run)
01 grey (normal run)
02 white (normal run)
03 white (long run)

Of course now you’d need a 2 byte palette table (nibble per 2bit -> 2bit palette entry), but I think the value of still having two lengths for the most variant color would easily pay back that 2 byte cost.

Dreamer3 · 2018-09-21 00:25:21 UTC

You could also use that “third color” as an escape sequence… if you come across a string of pixels that doesn’t compress well at all then you just “escape” (2 bit escape code, 6 bit length) and then you have a run of NON-RLE encoded data that doesn’t have any RLE related overhead. So the compression would constantly be making sure that the RLE was actually BENEFITTING things and if it found a case where the actual raw data would be smaller (more than 1 byte) it just switches to raw data mode.

All of those ideas put the real effort into the ENCODER, where it belongs - the decoder is still a pretty simple fetch/process pipeline.

Dreamer3 · 2018-09-21 00:36:30 UTC

You mean bytes here, not pixels, right?

Dreamer3 · 2018-09-21 00:52:55 UTC

Ha, so it does that. Missed that. Sorry.

filmote · 2018-09-21 01:18:27 UTC

My first attempt used a fixed length run - in fact a short and a long length - and those original tests were using this. The short run length was calculated by looping through the compression algorithm with a run length (in bits) of 2, 3, 4 … up to 6 (from memory). The ‘long run length’ was 3 times this.

So in each RL set, I was using a bit to indicate whether it was short or long.

Limiting the length of a run produces a side-effect. You need to specify the colour absolutely (2 bits) whereas if your length are ‘unmlimited’ you can specify a change of colour relative to the current one (1 bit).

You are approaching my short / long run length in a different way - I like this as it does not add an extra bit. The compression code would just need to be smart enough to work out which color would give the best savings in the long runs.

Your approach saves a bit per rl combination but can only handle long runs in one colour. My (original) approach costs a bit but handles long runs in all three colours.

Interesting idea … might look into that.

Ooops … yep.