Canvas to GIF in Javascript

I'll tell you about the features that I encountered while saving the image from the canvas in the GIF.

There will be considered ready-made solutions and my own javascript image quantization code (that is, reducing the palette to 256 colors). Also, the performance issues of some javascript constructions will be affected.

Briefly about why you need such a converter

Honestly, it’s not at all necessary to convert images using Javascript. Server languages, such as PHP, C #, JAVA, do a good job with this task. But if there is a Javascript image editor, which works with canvas, which already knows how to produce pictures in jpg and png formats, then at least it is ugly to separate the logic into the client and server parts. It is for the inner beauty of the application that I took up this issue. I want the entire application to be on javasript.

We are building bricks

Convert canvas to JPEG or PNG is not difficult. One function is enough for this:

canvas.toDataURL(mime) 

The result of this faction will be the base64 DatURL string, which you can, for example, easily substitute for the img tag src attribute.

The mime parameter can be either “image / png” or “image / jpeg”.

If you transfer “image / gif” or “image / bmp” as mime, the result will still be in PNG format.

')

Since there are a lot of programmers on our planet, I decided to find out if someone had encountered such a problem and if someone had reached out to solve it.

I was lucky, I quickly found a code on the Internet that saves the canvas in the BMP format: www.nihilogic.dk/labs/canvas2image

After tearing out the piece of code I needed, I started on the GIF.



But with GIF it was not so simple.

Almost all searches on the topic “canvas to gif” are directed to the antimatter15 library: github.com/antimatter15/jsgif

Therefore, I tried it first. Plus, she has one: she still produces a picture in GIF format, which, among other things, can be animated. Apparently, only the animation was focused, because I did not see any image quality or conversion speed.



antimatter15 (PNG to GIF, 100x16px, 56ms):





antimatter15 (JPEG to GIF, 604x377px, 4564ms):





antimatter15 (Transparent PNG to GIF, 256x256px, 1052ms):





As you can see, all the pictures have distorted colors. But the third is a special case.

Let me explain what happened to the last picture. The source file was in PNG format with transparent pixels. Canvas provides information about pixels in RGBA format, that is, three colors and a level of transparency. But the antimatter15 library simply ignores the pixel transparency level and it turns out a completely incorrect result.



In fairness, I note that the canvas2image library also does not perceive the level of transparency.

canvas2image (Transparent PNG to BMP, 256x256px):





Therefore, I urge everyone not to ignore alpha bytes, which we graciously provide the canvas.



Further searches led me to omggif (javascript implementation of GIF 89a encoder, includes animation and compression): github.com/deanm/omggif

Having seen an example that generates a transparent pixel, I immediately began to respect this library.

 // 1x1 transparent 43 bytes. function gen_empty_trans() { var gf = new omggif.GifWriter(buf, 1, 1, {palette: [0x000000, 0x000000]}); gf.addFrame(0, 0, 1, 1, [0], {transparent: 0}); return buf.slice(0, gf.end()); } 

But as you can see from the example, it does not work with canvas. When you create an object, you need to give a ready-made palette (color list), and when adding a frame, an array of indices in the palette.

Creating a palette and indexes, as it turned out, is nothing more than quantization (quantization). In the library from antimatter15, a separate NeuQuant.js file was responsible for this. In omggif there is no quantizer.

I looked at several quantizers for javascript, but no one worked with transparency.

Thanks to the omggif library, I no longer needed to understand the GIF file format, and the quantization task seemed to me not so difficult and even interesting. Therefore, it was decided to finish the converter yourself.

The algorithm for creating palettes and indexes

So, at first I divided the quantization process into 4 stages:

1. Search for pixels to include in the palette.
2. Identify colors that do not fall into the palette.
3. For each color that didn’t fall into the palette, search for the nearest color from the palette
4. Convert all pixels to color indexes in the palette.

Stage 1

The most important is the first stage. The quality of the resulting image depends on it. If the remaining steps are concrete - it is just some conversion of one data array to another, then the first item looks somewhat abstract. It is not immediately clear by what criteria to evaluate which of the colors is more important than the other.



Then I decided not to go deep into this question, but simply reduce the canvas until the number of colors in it is less than 255 (one color is always transparent). Since scaling is performed by the browser, this part of the algorithm turned out to be the fastest. Only 20ms for a jpg file with a dog (see above) from 1500ms of the execution of the entire algorithm.



Experimentally, I found out that the best way to reduce the picture exactly twice. Otherwise colors are distorted.



Also, given the transparency byte, I applied the following formulas for each pixel:

  red = 0xFF-alpha * (1-red / 0xFF)
 green = 0xFF-alpha * (1-green / 0xFF)
 blue = 0xFF-alpha * (1-blue / 0xFF) 

Thus, all the components of the color I put on a white background. At the same time, if alpha is 0, then this pixel is completely transparent and it is skipped.

Stages 2 and 3

Next you need to go through all the pixels again and put those pixels that did not fall into the main palette into a separate array (additional palette).

In parallel, when a new pixel is detected, we will determine the closest color from the palette. If we represent the red, blue and green color components as the coordinate of a point in three-dimensional space, then the difference between two colors is the distance between two points. And the distance between points is determined by the well-known formula of Pythagoras:

  d = sqrt ((x1 - x2) ^ 2 + (y1 - y2) ^ 2 + (z1 - z2) ^ 2) 

So, we have a main palette and an additional palette - colors that did not fall into the main palette. And each color of the additional palette has the closest color in the main palette.

Now is the time to pay attention to the first stage. Due to the fact that the image each time was reduced twice already, the main palette will most likely not be complete. Instead of 255, it can contain as many as 100 or less colors. Therefore, you need to supplement the main palette.

Additional stage

We will complement with colors that have the maximum difference from the colors in the main palette. At what we will add one at a time and each time recalculate an additional palette with respect to the added color. And when the main palette reaches 255 colors or the additional palette is exhausted, we move on to the final stage.

Stage 4

It's simple. We pass an array of pixels and determine the color index in the main palette by the color of the pixel. If in the main palette of this color is not, then look for it in an additional palette. And each color in the additional palette already has the closest color from the main palette.

Algorithm Optimization for Javascript

During the implementation of the algorithm on Javascrpt, I came across some features of this language that significantly influenced speed.

Optimization of the difference formula in two colors

Let's start by calculating the minimum difference between the two colors. I will cite several variants of the Pythagorean formula in Javascript. What do you think is the fastest option?

 // 1 Math.sqrt(Math.pow(red1-red2,2)+Math.pow(green1-green2,2)+Math.pow(blue1-blue2,2)) // 2 var mypow = function(a){ return a*a; }; Math.sqrt(mypow(red1-red2)+mypow(green1-green2)+mypow(blue1-blue2)) // 3 Math.sqrt((red1-red2)*(red1-red2)+(green1-green2)*(green1-green2)+(blue1-blue2)*(blue1-blue2)) // 4 var distance = function(a,b,c){ return Math.sqrt(a*a+b*b+c*c); }; distance(red1-red2, green1-green2,blue2-blue2) 

I'll start the hit parade with the slowest option - option number 2. The self-written squaring function was 2.5 times slower than the built-in Math.pow. But if we use the 3rd option, the same part of the algorithm will be executed more than 10 times faster than Math.pow. From here I conclude that in javascript very slowly the function call occurs. And the fourth option confirms this, working 10 times slower than the third.

Let's try to increase the speed. In fact, the result of the calculation of the formula will be used only to search for the minimum and maximum color difference. Therefore, you can safely remove the square root calculation.

 // 5 (red1-red2)*(red1-red2)+(green1-green2)*(green1-green2)+(blue1-blue2)*(blue1-blue2) 

Thus, we increase the speed of the third variant by another 1.5 times.

Moreover, further optimization has little effect on speed. The following option gives almost the same speed:

 // 6 (red=red1-red2)*red+(green=green1-green2)*green+(blue=blue1-blue2)*blue 

Comparative table of the second and third stages with three pictures:

	Dog	Alpha romeo	Browser Icons
Math.sqrt (Math.pow (r1-r2,2) + Math.pow (g1-g2,2) + Math.pow (b1-b2,2))	17211ms	1762ms	117ms
Math.sqrt (mypow (r1-r2) + mypow (g1-g2) + mypow (b1-b2))	40790ms	3875ms	255ms
Math.sqrt ((r1-r2) * (r1-r2) + (g1-g2) * (g1-g2) + (b1-b2) * (b1-b2))	1250ms	149ms	14ms
distance (r1-r2, g1-g2, b2-b2)	15006ms	1556ms	99ms
(r1-r2) * (r1-r2) + (g1-g2) * (g1-g2) + (b1-b2) * (b1-b2)	779ms	104ms	12ms
(r = r1-r2) * r + (g = g1-g2) * g + (b = b1-b2) * b	740ms	100ms	10ms

Palette array optimization

First, I used an array of colors to store the palette. Adding a new color happened like this:

 if(palette.indexOf(color) == -1) palette.push(color); 

But in a large array, the execution of indexOf is a very slow function, since it in turn compares all the elements with the desired one.

Therefore, I changed this option to a faster one:

 if(!palette[color)) palette[color]=true; 

This option of filling the main palette worked much faster, and when filling an additional palette, which can turn out to be much larger than the main one, the difference was 2 orders of magnitude. In order not to calculate the component colors each time, I decided to cache them in the palette:

 if(!palette[color)) palette[color]={r:red, g:green, b:blue}; 

But after filling the palette, the algorithm involves many cycles of passage:

 for(var color in palette){ var rgb=palette[color]; } 

Here, on the contrary, work with the object turned out to be much slower than if we worked with an array:

 for(var i=0, n=palette.length; i<n; i++){ var pal=palette[i]; } 

Therefore, it is better to use an array (palette) to store the palette, and to check whether there is a color in the palette, use the object (exists):

 if(!exists[color)){ exists[color]=true; palette.push({c:color, r:red, g:green, b:blue}); } for(var i=0, n=palette.length; i<n; i++){ var pal=palette[i]; } 

Cycle optimization

I will dwell a bit on testing different ways of passing cycles:

 // 1 for(var i=0, n=palette.length; i<n; i++){ var pal=palette[i]; } // 2 for(var i=0; i<palette.length; i++){ var pal=palette[i]; } // 3 for(var i=0, pal; pal=palette[i]; i++){ } 

Recently, I have been using the last option more, since for me it is the most convenient. But if you look at the performance, the situation is ambiguous. Almost no difference. Judge for yourself:

	Dog	Alpha romeo	Browser Icons
for (var i = 0, n = palette.length; i <n; i ++)	238ms	51ms	3,5ms
for (var i = 0; i <palette.length; i ++)	244ms	55ms	3,5ms
for (var i = 0, pal; pal = palette [i]; i ++)	230ms	54ms	3,5ms

Result

PNG to GIF, 100x16px, 35ms:





JPEG to GIF, 604x377px, 1338ms:





Transparent PNG to GIF, 256x256px, 268ms:





I am pleased with the result. The pictures turned out better than the library from antimatter15 gave. The speed was acceptable. Well, transparency byte is taken into account.







Now I can say with confidence:

- Convert images to Javascript!