Canvas to GIF on Javascript
I’ll tell you about the features that I encountered when saving images from canvas to GIF.
Here, ready-made solutions and my own javascript image quantization code (that is, reducing the palette to 256 colors) will be considered. The performance issues of some javascript constructs will also be raised.
Briefly about why such a converter is needed
Honestly, it is not necessary to convert images using Javascript. Server languages, such as PHP, C #, JAVA, can do this well. But if there is a Javascript image editor that works with canvas, which already knows how to display pictures in jpg and png formats, then at least it is ugly to separate the logic into the client and server parts. It was for the internal beauty of the application that I addressed this issue. I want the whole application to be in javasript.
Collect bricks
Converting canvas to JPEG or PNG is not at all difficult. One function is enough for this:
canvas.toDataURL(mime)
The result of this function will be a base64 DatURL string, which, for example, can be easily substituted into the src attribute of the img tag.
The mime parameter can be either “image / png” or “image / jpeg”.
If you pass “image / gif” or “image / bmp” as the mime, the result will still be in PNG format.
Since there are more than a few programmers on our planet, I decided to find out if anyone had such a problem and if anyone got their hands on it.
I was lucky, I quickly found on the Internet a code that saves canvas in BMP format: www.nihilogic.dk/labs/canvas2image
Having picked out the piece of code I needed, I set to GIF.
But with GIF it was not so simple.
Almost all searches on the theme "canvas to gif" lead to the antimatter15 library:github.com/antimatter15/jsgif
Therefore, I first tried it. She has one plus: she still gives out a picture in GIF format, which, among other things, can be made animated. Apparently, the emphasis was only on animation, because I did not see either the image quality or the 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 images have distorted colors. But the third has a special case.
I will explain what happened to the last picture. The source file was in PNG format with transparent pixels. Canvas provides pixel information in RGBA format, that is, three colors and a level of transparency. But the library from antimatter15 simply ignores the transparency level of the pixels and the result is completely incorrect.
In fairness, I note that the canvas2image library also does not perceive the level of transparency.
canvas2image (Transparent PNG in BMP, 256x256px):
Therefore, I urge everyone not to ignore the alpha byte that canvas kindly provides us.
Further searches led me to omggif (javascript implementation of GIF 89a encoder, includes animation and compression): github.com/deanm/omggif
Seeing an example that generates a transparent pixel, I immediately started 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 creating an object, you need to give an already prepared palette (a list of colors), and when adding a frame, an array of indices in the palette.
Creating palettes and indexes, as it turned out, is nothing more than quantization. In the library from antimatter15, a separate file NeuQuant.js was responsible for this. There is no quantizer in omggif.
I looked at a few quantizers for javascript, but none 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 itself.
Algorithm for creating a palette and indexes
So, first I divided the quantization process into 4 stages:
- Search for pixels to include in the palette.
- Identify colors that are not in the palette.
- For each color that does not fit into the palette, search for the closest color from the palette
- Convert all pixels to color indices in the palette.
Stage 1
The most important is the first stage. The quality of the received image depends on it. If the remaining steps are concrete - it’s just some transformation of one data array into another, then the first item looks somewhat abstract. It is not immediately clear by what criteria to evaluate which of the flowers is more important than the other.
Then I decided not to go deep into this issue, but simply reduce the canvas until the number of colors in it is less than 255 (one color is always transparent). Since scaling is done 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) out of 1500ms of the entire algorithm.
Empirically, I found out that it is best to reduce the picture exactly twice. Otherwise, the 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, I impose all the color components on a white background. Moreover, 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 move out to a separate array (additional palette) those pixels that did not fall into the main 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 constituent colors as the coordinate of a point in three-dimensional space, then the difference between the two colors is like the distance between two points. And the distance between the points is determined by the well-known Pythagorean formula:
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.
Here is the time to pay attention to the first stage. Due to the fact that the image was already halved each time, the main palette is likely to be incomplete. Instead of 255, it may contain only 100 or fewer flowers. Therefore, you need to supplement the main palette.
Additional stage
We will supplement with colors that have the maximum difference from the colors in the main palette. Moreover, we will add one at a time and each time recount an additional palette relative to the added color. And when the main palette reaches 255 colors or an additional palette is exhausted, we will move on to the last stage.
Stage 4
Everything is simple here. We pass an array of pixels and determine the color index in the main palette by the color of the pixel. If this color is not in the main palette, then we are looking for it in the 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 affected the speed.
Two-color formula optimization
We start by calculating the minimum difference between the two colors. I will give several options for the Pythagorean formula in the Javascript language. 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 version - option number 2. The self-written squaring function turned out to be 2.5 times slower than the built-in Math.pow. But if you use the 3rd option, then the same part of the algorithm will execute more than 10 times faster than Math.pow. From this I conclude that in javascript it is very slowly the function call that 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 calculating the formula will be used only to find the minimum and maximum color difference. Therefore, you can safely remove the calculation of the square root.
//Вариант 5
(red1-red2)*(red1-red2)+(green1-green2)*(green1-green2)+(blue1-blue2)*(blue1-blue2)
Thus, we increase the speed of the third option 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
Comparison 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, executing indexOf is a very slow function, since it takes turns comparing all the elements with the searched 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 the additional palette, which can be much larger than the main one, the difference was 2 orders of magnitude. In order not to calculate the constituent 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 assumes many cycles of passage:
for(var color in palette){
var rgb=palette[color];
}
On the contrary, working with an object turned out to be much slower than if we were working with an array:
for(var i=0, n=palette.length; i
Поэтому лучше для хранения палитры использовать массив (palette), а для проверки, есть ли цвет в палитре, использовать объект (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
Оптимизация циклов
Немного остановлюсь на тестиовании разных способов прохода циклов:
//Вариант 1
for(var i=0, n=palette.length; i
В последнее время я больше применяю последний вариант, так как для меня он самый удобный. Но если смотреть на производительность, то ситуация неоднозначная. Разницы почти нет. Судите сами:
Собака Alpha Romeo Иконки браузеров for(var i=0, n=palette.length; i 238ms 51ms 3,5ms for(var i=0; i 244ms 55ms 3,5ms for(var i=0, pal; pal=palette[i]; i++) 230ms 54ms 3,5ms
Результат
PNG в GIF, 100x16px, 35ms:
JPEG в GIF, 604x377px, 1338ms:
Прозрачный PNG в GIF, 256x256px, 268ms:
Результатом я доволен. Картинки получились более качественные чем давала библиотека от antimatter15. Скорость оказалась приемлемой. Ну и байт прозрачности учтен.
Вот мой код(Основные функции canvasToGIFDataURL и canvasPalette)
// base64 encodes either a string or an array of charcodes
var encodeData = function(data) {
var strData = "";
if (typeof data == "string") {
strData = data;
} else {
var aData = data;
for (var i=0;i=255){
var subcanvas=document.createElement('canvas'),
width=oData.width>>1,
height=oData.height>>1;
subcanvas.width=width;
subcanvas.height=height;
subcanvas.getContext('2d').drawImage(canvas, 0, 0,width,height);
return canvasPalette(subcanvas);
}
else{
exists[col]=true;
palette.push({c:col,r:r,g:g,b:b});
}
}
}
return {exists:exists, palette:palette};
}
var canvasToGIFDataURL = function(canvas){
var dr,dg,db;
var oData = readCanvasData(canvas);
var data=oData.data;
var palette=canvasPalette(canvas);
var exists=palette.exists;
palette=palette.palette;
var outpalette=[];
var pixels=[];
var maxdDifI=null;
var maxdDif=0;
for(var i = 0,pi=0,l=data.length; i < l; i+=4, pi++){
var a=data[i+3];
if(a==0){
pixels[pi]=-1;
continue;
}
var r=(cW-a*(1-data[i]/cW))|0,
g=(cW-a*(1-data[i+1]/cW))|0,
b=(cW-a*(1-data[i+2]/cW))|0,
col=b+(g<<8)+(r<<16);
pixels[pi]=col;
if(!exists[col]){
exists[col]=true;
var minDif=0xffffff,
minDifColIndex=null;
for(var j=0, nj=palette.length; j maxdDif) {
maxdDif=minDif;
maxDifI=outpalette.length;
}
outpalette.push({c:col, d:minDif, r:r, g:g, b:b, index:minDifColIndex});
}
}
while(maxdDif!=null && palette.length<255){
var dif=outpalette.splice(maxdDifI,1)[0];
maxdDif=null;
maxdDifI=0;
var r=dif.r, g=dif.g, b=dif.b, col=dif.c;
var index=palette.length;
palette.push({c:col,r:r,g:g,b:b});
for(var j=0, nj=outpalette.length; j maxdDif) {
maxdDif=dif.d;
maxDifI=j;
}
}
}
var map={};
palette.unshift({c:-1});
for(var j=0,pal; pal=palette[j]; j++){
var col=pal.c;
map[col]=j;
palette[j]=col;
}
for(var j=0,dif; dif=outpalette[j]; j++){
map[dif.c]=dif.index+1;
}
var indexes=[];
for(var i = 0, pixel; pixel=pixels[i]; i++){
indexes.push(map[pixel]);
}
for(var l=2;l<=256;l=l<<1){
if(palette.length==l) break;
if(palette.length
Исходные картинкиИконки браузеров
Собака
Alpha Romeo
Теперь я с уверенностью могу сказать:
— Конвертировать изображения можно на Javascript!