canvas в gif

Коротко о том, зачем нужен такой конвертер

Честно говоря, совсем не обязательно конвертировать изображения с помощью Javascript. С этой задачей хорошо справляются серверные языки, например PHP, C#, JAVA. Но если есть Javascript приложение, которое работает с canvas, который уже умеет выдавать картинки в jpg и png форатах, то как минимум некрасиво разделять логику на клиентскую и серверную часть. Именно для внутренней красоты приложения я и занялся этим вопросом. Я хочу, чтобы все приложение было на javasript.

Собираем кирпичики

Конвертировать canvas в JPEG или в PNG совсем не сложно. Для этого достаточно одной функции:

canvas.toDataURL(mime) 

Результат этой фанкции будет строка base64 DatURL, которую можно, например, спокойно подставлять в атрибут src тега img.
Параметр mime может быть либо «image/png» либо «image/jpeg».
Если в качестве mime передавать «image/gif» или «image/bmp», то результат все равно будет в формате PNG.

Так как программистов на нашей планете не мало, я решил узнать сталкивался ли кто-то с такой проблемой и дошли ли у кого-нибудь руки до ее решения.
Мне повезло, я быстро нашел в интернете код, который сохраняет canvas в формат BMP: www.nihilogic.dk/labs/canvas2image
Выдрав нужный мне кусок кода, я принялся за GIF.

Но с gif оказалось не все так просто.
Почти все поиски на тему «canvas to gif» ведут на библиотеку antimatter15: github.com/antimatter15/jsgif
Поэтому ее то я первую и попробовал. Плюс у нее один: она все таки выдает картинку в формате GIF, которую, кроме всего прочего, можно сделать анимационной. Видимо только на анимацию и делался упор, потому как я не увидел ни качества изображения, ни скорости конвертирования.

antimatter15 (GIF в GIF, 100x16px, 56ms):

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

antimatter15 (Прозрачный PNG в GIF, 256x256px, 1052ms):

Объясню что случилось с последней картинкой. Исходный файл был в формате PNG с прозрачными пикселями. Канвас выдает информацию о пикселях в формате RGBA, то есть три цвета и уровень прозрачности. Но библиотека от antimatter15 просто игнорирует уровень прозрачности пикселей и получается совсем некорректный результат.

Справедливости ради замечу, что библиотека canvas2image тоже не воспринимает уровень прозрачности.
canvas2image (Прозрачный PNG в BMP, 256x256px):

Поэтому призываю всех не игнорировать alpha байт который нам любезно предоставляет сanvas.

Дальнейшие поиски привели меня к omggif (javascript реализация GIF 89a кодера, включает анимацию и компрессию): github.com/deanm/omggif
Увидев пример, который генерирует прозрачный пиксель, я сразу зауважал эту библиотеку.

// 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()); } 

Но как видно из примера он не работает с canvas. При создании объекта нужно отдавать уже готовую палитру (список цветов), а при добавлении кадра — массив индексов в палитре.
Создание палитры и индексов, как оказалось, есть ни что иное как квантизация (quantization). В библиотеке от antimatter15 за это отвечал отдельный файл NeuQuant.js. В omggif квантизатора нет.
Я посмотрел несколько квантизаторов для javascript, но никакой не работал с прозрачностью.
Благодаря библиотеке omggif мне уже не надо было разбираться в формате GIF файла, а задача квантизации показалась мне не такой уж сложной и даже интересной. Поэтому решено было допилить конвертер самому.

Алгоритм создания палитры и индексов

Итак, сначала процесс квантизации я разделил на 4 этапа:

1. Поиск пикселей, которые нужно включить в палитру.
2. Определение цветов, которые не попали в палитру.
3. Для каждого цвета, который не попал в палитру, поиск ближайшего цвета из палитры
4. Преобразование всех пикселей в индексы цвета в палитре.

Этап 1

Самым важный — это первый этап. От него зависит качество полученного изображения. Если остальные этапы конкретны — это просто некоторое преобразование одного массива данных в другой, то первый пункт выглядит несколько абстрактно. Не сразу понятно по каким критериям оценивать, какой из цветов важнее другого.

Тут я решил сильно не углубляться в этот вопрос, а просто уменьшать canvas пока количество цветов в нем не будет меньше 255 (один цвет всегда прозрачный). Поскольку масштабирование выполняется браузером, то эта часть алгоритма оказалась самая быстрая. Всего 20ms для jpg файла с собачкой (смотреть выше) из 1500ms выполнения всего алгоритма.

Опытным путем я выяснил, что лучше всего картинку уменьшать ровно в два раза. Иначе искажаются цвета.

Также, учитывая байт прозрачности, я применил такие формулы для каждого пикселя:

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

Таким образом все составляющие цвета я накладываю на белый фон. При этом, если alpha равен 0, значит этот пиксель полностью прозрачный и он пропускается.

Этапы 2 и 3

Дальше нужно пройти заново все пиксели и вынести в отдельный массив (дополнительная палитра) те пиксели, которые не попали в основную палитру.
Параллельно, при обнаружении нового пикселя, определим ближайший цвет из палитры. Если представить красный, синий и зеленый составляющие цвета в качестве координаты точки в трехмерном пространстве, то разница двух цветов — это как минимальное раcстояние между двумя точками. А минимальное расстояние между точками определяется по известной формуле Пифагора:

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

Итак, у нас есть основная палитра и дополнительная палитра — цвета, которые не попали в основную палитру. И у каждого цвета дополнительной палитры есть ближайший цвет в основной палитре.
Тут самое время обратить внимание на первый этап. Из-за того, что изображение каждый раз уменьшалось аж в два раза, то основная палитра скорее всего будет получаться не полной. Вместо 255 она может содержать всего 100 или меньше цветов. Поэтому нужно дополнить основную палитру.

Дополнительный этап

Дополнять будем цветами, которые имеют максимальное отличие от цветов в основной палитре. При чем будем добавлять по одному и каждый раз пересчитывать дополнительную палитры относительно добавленного цвета. И когда основная палитра достигнет 255 цветов либо исчерпается дополнительная палитра, перейдем к последнему этапу.

Этап 4

Тут все просто. Проходим массив пикселей и по цвету пикселя определяем индекс цвета в палитре.

Оптимизация алгоритма для языка Javascript

В ходе реализации алгоритма на Javascrpt я столкнулся с некоторыми особенностями этого языка, которые значительно повлияли скорость.

Оптимизация формулы отличия двух цветов

Начнем с вычисления минимального отличия между двумя цветами. Приведу несколько вариантов формулы Пифагора на языке Javascript. Как вы думаете какой вариант самый быстрый?

//Вариант 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) 

Начну хит парад с самого медленного варианта — вариант под номером 2. Самописная функция возведения в квадрат оказалась в 2,5 раза медленнее, чем встроенная Math.pow. Но если воспользоваться 3-м вариантом, то та же самая часть алгоритма выполнится в более 10 раз быстрее чем второй. Отсюда я делаю вывод, что в javascript очень медленно происходит именно вызов функций. И четвертый вариант подтверждает это, работая в 10 раз медленнее третьего.
Попробуем еще увеличить скорость. По сути результат вычисления формулы будет использоваться только для поиска минимальной и максимальной разницы цветов. Поэтому можно спокойно убрать вычисление квадратного корня.

//Вариант 5 (red1-red2)*(red1-red2)+(green1-green2)*(green1-green2)+(blue1-blue2)*(blue1-blue2) 

Таким образом мы увеличиваем скорость третьего варианта еще в 1.5 раза.
При чем, дальнейшая оптимизация мало влияет на скорость. Следующий вариант дает почти такую же скорость:

//Вариант 6 (red=red1-red2)*red+(green=green1-green2)*green+(blue=blue1-blue2)*blue 

Сравнительная таблица выполнения второго и третьего этапов с тремя картинками:

Оптимизация массива палитры

Сначала для хранения палитры я использовал массив цветов. Добавление нового цвета происходило приблизительно так:

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

Но в большом массиве выполнение indexOf — очень медленная функция, так как она по очереди сравнивает все элементы с искомым.
Поэтому я поменял этот вариант на более быстрый:

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

Этот вариант наполнения основной палитры работал на много быстрее, а при наполнении дополнительной палитры, которая может получаться намного больше основной, разница была в 2 порядка. Чтобы каждый раз не вычислять составляющие цвета я решил кешировать их в палитре:

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

Но после наполнения палитры алгоритм предполагает много циклов прохода:

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

Тут наоборот работа с объектом оказалась намного медленнее, чем если бы мы работали с массивом:

for(var i=0, n=palette.length; i<n; i++){     var pal=palette[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<n; i++){     var pal=palette[i]; } 

Оптимизация циклов

Немного остановлюсь на тестиовании разных способов прохода циклов:

//Вариант 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++){ } 

В последнее время я больше применяю последний вариант, так как для меня он самый удобный. Но если смотреть на производительность, то ситуация неоднозначная. Разницы почти нет. Судите сами:

Результат

GIF в GIF, 100x16px, 35ms:

JPEG в GIF, 604x377px, 1338ms:

Прозрачный PNG в GIF, 256x256px, 268ms:

Результатом я доволен. Картинки получились более качественные чем давала библиотека от antimatter15. Скорость оказалась приемлемой. Ну и байт прозрачности учтен.

 		// 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<aData.length;i++) { 					strData += String.fromCharCode(aData[i]); 				} 			} 			return btoa(strData); 		}; 		var readCanvasData = function(oCanvas) { 			var iWidth = parseInt(oCanvas.width); 			var iHeight = parseInt(oCanvas.height); 			return oCanvas.getContext("2d").getImageData(0,0,iWidth,iHeight); 		}; 		var makeDataURI = function(strData, strMime) { 			return "data:" + strMime + ";base64," + strData; 		};  		var cW=0xff;	  		var canvasPalette=function(canvas){ 			var oData = readCanvasData(canvas), 				data=oData.data, 				exists={}, 				palette=[]; 			 			for(var i = 0, n=data.length; i < n; i+=4){ 				var a=data[i+3]; 				if(a==0) 					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); 					 				if(!exists[col]){ 					if(palette.length>=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,mime){ 						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<nj; j++){ 									var pal=palette[j], 										d=(dr=pal.r-r)*dr+(dg=pal.g-g)*dg+(db=pal.b-b)*db; 									if(d<minDif){ 										minDif=d; 										minDifColIndex=j; 									} 								} 								 								if(minDif > 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<nj; j++){ 								var dif=outpalette[j], 									d=(dr=dif.r-r)*dr+(dg=dif.g-g)*dg+(db=dif.b-b)*db; 								if(d<dif.d){ 									dif.d=d; 									dif.index=index; 								} 								if(dif.d > 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<l) { 								while(palette.length<l) 									palette.push(0); 								break; 							} 						} 						var buf = []; 						var gf = new GifWriter(buf, oData.width, oData.height, {palette: palette}); 						gf.addFrame(0, 0, oData.width, oData.height, indexes,{transparent: 0}); 						var binary_gif =  buf.slice(0, gf.end()); 						return makeDataURI(encodeData(binary_gif), 'image/gif');			 		}; 

Теперь я с уверенностью могу сказать:
— Конвертировать изображения можно на Javascript!