So, the trick is to try and minimize the amount of data you send, which can be done in various ways including things like base64 encoding, or using LZW compression. I did try those methods, and while they do work, they were taking far too long (at least in VM1) to do their thing. Uploading the big-ass string was faster than compressing and uploading the small version. I was resigned to just sending the big string, but kept thinking there must be a way to somewhat minimize the impact. That's when I hit on this simple array compression technique that is reminiscent of RLE.
Here's the function:
function compressArray(orig:Array):Array{
var l = orig.length;
var comp:Array = new Array(); //new compressed array
for(var i = 0; i < l; i++){
comp[i] = "";
}
comp[0] = orig[0];
var lastEqualIndex = 0;
for(var i = 1; i < l; i++){
if(orig[i] != comp[lastEqualIndex]){
//new color
comp[i] = orig[i];
lastEqualIndex = i;
}
}
return comp;
}
It works like so - a new array, comp, is created, the same length as the original, and filled with "" - empty strings.
The first item in the new array is set to the first item in the original, and the initial 0 index is stored in lastEqualIndex - since the two arrays are now identical at index 0.
The original array is then iterated starting at the second item in the array - index 1, and going to the end. If the current item in the original array is different from the item in the comp array at the lastEqualIndex, then a new value has been encountered. It is stored in the new, comp, array and the lastEqualIndex is updated to reflect the current index in the loop.
What this accomplishes is creating a new array where runs of duplicate data are eliminated and only the initial value in the run is kept. The other items in the run are kept at their initial empty string values.
Example:
original: [FFFFFF, FFFFFF, AAAAAA, BBBBBB, AAAAAA, AAAAAA, AAAAAA, AAAAAA]
new version: [FFFFFF, , AAAAAA, BBBBBB, AAAAAA, , , ]
original: 55 bytes
new version: 31 bytes
A full 44% reduction
Here's some actual examples when the array is filled with color values:

As you can see, some images are more compressible than others, as is normal. I couldn't believe the last image saw an 86% reduction, I expected much worse from it.
The nice thing about this method, aside from the fact that it's extremely fast, is that the array indexes are preserved and so it's very easy to reconstruct the original array: If a value in the array is "", just use the last item (color) that wasn't empty. Simple as that.

3 comments:
You mention null a few times, which isn't correct.
You're using empty string values. There's a difference.
Dave, that looks great. Simple and fast is a great combination! I've used LZW in as2 before and its been very sluggish at best. I think this your approach is superb to combine speed and reasonable compression (in AS2!) for image data in particular.
So for the encoding on the upload are you just using amf to do the remaining encoding work for you...? Or are the colour values stored in hex string format for example - as per the example in your post? (to avoid the the character code zero which is not possible in a string)
Muzak, yes you're right of course, I just said null for ease. Thanks.
GWD - I am using LoadVars and POST. I actually did try with AMFPHP and was having some problems that I couldn't figure out. It was throwing errors about not being able to find the gateway URL when the string was too large, so I switched to LV. And yes, I'm just sending Hex strings - using toString(16) on the getPixel() values.
Post a Comment