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:
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.
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??
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.
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.
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).
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.
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.
Ah ⌠that could work. Hadnât thought of that.
Probably a reasonable assumption.
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).
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!
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.
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
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.
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;
}
}
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:
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.
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.
You mean bytes here, not pixels, right?
Ha, so it does that. Missed that. Sorry.
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.