Minimizing canvas "bitmap" data size

Question

Context: multi-user app (node.js) - 1 painter, n clients

Canvas size: 650x400 px (= 260,000 px)

For the canvas to be updated frequently (I'm thinking about 10 times a second), I need to keep the data size as small as possible, especially when thinking about upload rates.

The toDataURL() method returning a base64 string is fine but it contains masses of data I don't even need (23 bit per pixel). Its length is 8,088 (without the preceding MIME information), and assuming the JavaScript strings have 8-bit encoding that would be 8.1 kilobytes of data, 10 times per second.

My next try was using JS objects for the different context actions like moveTo(x, y) or lineTo(x, y), sending them to the server and have the clients receive the data in delta updates (via timestamps). However, this turned out to be even less efficient than the base64 string.

{ 
    "timestamp": 0, 
    "what": { 
       "name": LINE_TO, 
       "args": {"x": x, "y": y}  
    } 
}

It doesn't work fluently nor precisely because there are nearly 300 lineTo commands already when you swipe your brush shortly. Sometimes there's a part of the movement missing (making a line straight instead of rounded), sometimes the events aren't even recognized by the script client-side because it seems to be "overwhelmed" by the mass of events triggered already.

So I have to end up using the base64 string with its 8.1 KB. I don't want to worry about this much - but even if done asynchronously with delta updates, there will be major lags on a real server, let alone the occasional bandwidth overrun.

The only colors I am using are #000 and #FFF, so I was thinking about a 1-bit data structure with delta updates only. This would basically suffice and I wouldn't mind any "color" precision losses (it is black after all).

With most of the canvas being white, you could think of additional Huffman run-length encoding to reduce size even further, too. Like a canvas with a size of 50x2 px and a single black pixel at (26, 2) would return the following string: 75W1B74W (50 + 25 white pixels, then 1 black pixel, then 24 more white pixels)

It would even help if the canvas consisted of a 1-bit string like this:

00000000000000000000000000000000000000000000000000 
00000000000000000000000001000000000000000000000000

That would help a lot already.

My first question is: How to write an algorithm to get this data efficiently?

The second is: How could I pass the pure binary canvas data to the clients (via node server)? How do I even send a 1-bit data structure to the server? Would I have to convert my bits to a hexadecimal (or more) number and re-parse?

Would it be possible to use this as a data structure?

Thanks in advance,

Harti

Answer 1

I need to keep the data size as small as possible

Then don't send the entire data. Send only the changes, close to what you propose yourself.

Make the framework such that every user can only do "actions" such as "draw black strokeWidth 2 from X1,Y1 to X2,Y2".

I wouldn't bother with some pure binary thing. If there's only two colors then that's easy to send as the string "1,2,x,y,x2,y2", which the other people will parse precisely the same way the local client will, and it will get drawn the same way.

I wouldn't overthink this. Get it working with simple strings before you worry about any clever encoding. It's worth trying the simple thing first. Maybe the performance will be quite good without going through a lot of trouble!

Answer 2

I sorted it out, finally. I used an algorithm to get the image data within a specified area (i.e. the area currently drawn on), and then paste the image data to the same coordinates.

1. While drawing, I keep my application informed about how big the modified area is and where it starts (stored in currentDrawingCoords).

2. pixels is an ImageData Array obtained by calling context.getImageData(left, top, width, height) with the stored drawing coordinates.

3. getDeltaUpdate is called upon onmouseup (yeah, that's the drawback of the area idea):

   getDeltaUpdate = function(pixels, currentDrawingCoords) {   
       var image = "" + 
           currentDrawingCoords.left + "," + // x
           currentDrawingCoords.top + "," + // y
           (currentDrawingCoords.right - currentDrawingCoords.left) + "," + // width
           (currentDrawingCoords.bottom - currentDrawingCoords.top) + "";  // height
       var blk = 0, wht = 0, d = "|";
   
       // http://stackoverflow.com/questions/667045/getpixel-from-html-canvas
       for (var i=0, n=pixels.length; i < n; i += 4) {
               if(
                   pixels[i]   > 0 ||
                   pixels[i+1] > 0 ||
                   pixels[i+2] > 0 ||
                   pixels[i+3] > 0
               ) {
                   // pixel is black
                   if(wht > 0 || (i == 0 && wht == 0)) {
                       image = image + d + wht;        
                       wht = 0;
                       d = ",";
                   }
                   blk++;
   
                   //console.log("Pixel " + i + " is BLACK (" + blk + "-th in a row)");
               } else {
                   // pixel is white 
                   if(blk > 0) {
                       image = image + d + blk;        
                       blk = 0;
                       d = ",";
                   }
                   wht++;
   
                   //console.log("Pixel " + i + " is WHITE (" + blk + "-th in a row)");
               }
       }
   
       return image;   
   }
   

4. image is a string with a header part (x,y,width,height|...) and a data body part (...|w,b,w,b,w,[...])

5. The result is a string with less characters than the base64 string has (as opposed to the 8k characters string, the delta updates have 1k-6k characters, depending on how many things have been drawn into the modification area)

6. That string is sent to the server, pushed to all the other clients and reverted to ImageData by using getImageData:

   getImageData = function(imagestring) {
       var data = imagestring.split("|");
       var header = data[0].split(",");
       var body = data[1].split(",");
   
       var where = {"x": header[0], "y": header[1]};
       var image = context.createImageData(header[2], header[3]); // create ImageData object (width, height)
   
       var currentpixel = 0,
       pos = 0,
       until = 0,
       alpha = 0,
       white = true;
   
       for(var i=0, n=body.length; i < n; i++) {
           var pixelamount = parseInt(body[i]); // amount of pixels with the same color in a row
   
           if(pixelamount > 0) {
               pos = (currentpixel * 4);
               until = pos + (pixelamount * 4); // exclude
   
               if(white) alpha = 0;
               else alpha = 255;
   
               while(pos < until) {
                   image.data[pos] = 0;
                   image.data[pos+1] = 0;
                   image.data[pos+2] = 0;
                   image.data[pos+3] = alpha;                  
                   pos += 4;
               }
               currentpixel += pixelamount;
               white = (white ? false : true);
           } else {
               white = false;  
           }
       }
   
       return {"image": image, "where": where};
   }
   

7. Call context.putImageData(data.image, data.where.x, data.where.y); to put the area on top of everything there is!

As previously mentioned, this may not be the perfect suit for every kind of monochrome canvas drawing application since the modification area is only submit onmouseup. However, I can live with this trade-off because it's far less stressful for the server than all the other methods presented in the question.

I hope I was able to help the people to follow this question.