/*
imagetracer.js
Simple raster image tracer and vectorizer written in JavaScript.
by András Jankovics 2015, 2016
andras@jankovics.net
*/
/*
The Unlicense / PUBLIC DOMAIN
This is free and unencumbered software released into the public domain.
Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.
In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
For more information, please refer to http://unlicense.org/
*/
(function(){ 'use strict';
function ImageTracer(){
var _this = this;
this.versionnumber = '1.1.0',
////////////////////////////////////////////////////////////
//
// User friendly functions
//
////////////////////////////////////////////////////////////
// Loading an image from a URL, tracing when loaded,
// then executing callback with the scaled svg string as argument
this.imageToSVG = function(url,callback,options){
options = _this.checkoptions(options);
// loading image, tracing and callback
_this.loadImage(url,
function(canvas){
callback(
_this.imagedataToSVG( _this.getImgdata(canvas),options )
);
}
);
},// End of imageToSVG()
// Tracing imagedata, then returning the scaled svg string
this.imagedataToSVG = function(imgd,options){
options = _this.checkoptions(options);
// tracing imagedata
var td = _this.imagedataToTracedata(imgd,options);
// returning SVG string
return _this.getsvgstring(td, options);
},// End of imagedataToSVG()
// Loading an image from a URL, tracing when loaded,
// then executing callback with tracedata as argument
this.imageToTracedata = function(url,callback,options){
options = _this.checkoptions(options);
// loading image, tracing and callback
_this.loadImage(url,
function(canvas){
callback(
_this.imagedataToTracedata(_this.getImgdata(canvas),options)
);
}
);
},// End of imageToTracedata()
// Tracing imagedata, then returning tracedata (layers with paths, palette, image size)
this.imagedataToTracedata = function(imgd,options){
options = _this.checkoptions(options);
// 1. Color quantization
var ii = _this.colorquantization( imgd, options );
// 2. Layer separation and edge detection
var ls = _this.layering( ii );
// Optional edge node visualization
if(options.layercontainerid){ _this.drawLayers( ls, _this.specpalette, options.scale, options.layercontainerid ); }
// 3. Batch pathscan
var bps = _this.batchpathscan( ls, options.pathomit );
// 4. Batch interpollation
var bis = _this.batchinternodes( bps );
// 5. Batch tracing
return {
'layers':_this.batchtracelayers( bis, options.ltres, options.qtres ),
'palette':ii.palette,
'width':imgd.width,
'height':imgd.height
};
},// End of imagedataToTracedata()
// creating options object, setting defaults for missing values
this.checkoptions = function(options){
options = options || {};
// Defaults for optional parameters
// Tracing
if(!options.hasOwnProperty('ltres')){ options.ltres = 1; }
if(!options.hasOwnProperty('qtres')){ options.qtres = 1; }
if(!options.hasOwnProperty('pathomit')){ options.pathomit = 8; }
// Color quantization
if(!options.hasOwnProperty('colorsampling')){ options.colorsampling = true; }
if(!options.hasOwnProperty('numberofcolors')){ options.numberofcolors = 16; }
if(!options.hasOwnProperty('mincolorratio')){ options.mincolorratio = 0.02; }
if(!options.hasOwnProperty('colorquantcycles')){ options.colorquantcycles = 3; }
// options.pal is not defined here, the custom palette should be added externally: options.pal = [ { 'r':0, 'g':0, 'b':0, 'a':255 }, {...}, ... ];
// SVG rendering
if(!options.hasOwnProperty('scale')){ options.scale = 1; }
if(!options.hasOwnProperty('simplifytolerance')){ options.simplifytolerance = 0; }
if(!options.hasOwnProperty('roundcoords')){ options.roundcoords = 1; }
if(!options.hasOwnProperty('lcpr')){ options.lcpr = 0; }
if(!options.hasOwnProperty('qcpr')){ options.qcpr = 0; }
if(!options.hasOwnProperty('desc')){ options.desc = true; }
if(!options.hasOwnProperty('viewbox')){ options.viewbox = false; }
// Blur
if(!options.hasOwnProperty('blurradius')){ options.blurradius = 0; }
if(!options.hasOwnProperty('blurdelta')){ options.blurdelta = 20; }
// options.layercontainerid is not defined here, can be added externally: options.layercontainerid = 'mydiv'; ...
return options;
},// End of checkoptions()
////////////////////////////////////////////////////////////
//
// Vectorizing functions
//
////////////////////////////////////////////////////////////
// 1. Color quantization
// Using a form of k-means clustering repeatead options.colorquantcycles times. http://en.wikipedia.org/wiki/Color_quantization
this.colorquantization = function(imgd, options ){
var arr = [], idx=0, cd,cdl,ci,c1,c2,c3,c4, paletteacc = [], pixelnum = imgd.width*imgd.height, i, j, k, cnt, palette;
// Filling arr (color index array) with -1
for( j=0; j 0 ){ imgd = _this.blur( imgd, options.blurradius, options.blurdelta ); }
// Repeat clustering step options.colorquantcycles times
for( cnt=0; cnt < options.colorquantcycles; cnt++ ){
// Average colors from the second iteration
if(cnt>0){
// averaging paletteacc for palette
for( k=0; k < palette.length; k++ ){
// averaging
if(paletteacc[k].n>0){
palette[k].r = Math.floor(paletteacc[k].r/paletteacc[k].n);
palette[k].g = Math.floor(paletteacc[k].g/paletteacc[k].n);
palette[k].b = Math.floor(paletteacc[k].b/paletteacc[k].n);
palette[k].a = Math.floor(paletteacc[k].a/paletteacc[k].n);
}
// Randomizing a color, if there are too few pixels and there will be a new cycle
if( ( paletteacc[k].n/pixelnum < options.mincolorratio ) && ( cnt < options.colorquantcycles-1 ) ){
palette[k].r = Math.floor(Math.random()*255);
palette[k].g = Math.floor(Math.random()*255);
palette[k].b = Math.floor(Math.random()*255);
palette[k].a = Math.floor(Math.random()*255);
}
}// End of palette loop
}// End of Average colors from the second iteration
// Reseting palette accumulator for averaging
for( i=0; i < palette.length; i++ ){
paletteacc[i]={};
paletteacc[i].r=0;
paletteacc[i].g=0;
paletteacc[i].b=0;
paletteacc[i].a=0;
paletteacc[i].n=0;
}
// loop through all pixels
for( j=0; j < imgd.height; j++ ){
for( i=0; i < imgd.width; i++ ){
// pixel index
idx = (j*imgd.width+i)*4;
// find closest color from palette by measuring (rectilinear) color distance between this pixel and all palette colors
cdl = 256+256+256+256; ci=0;
for(k=0;k0) && (i>0)) { n1 = ii.array[j-1][i-1]===val?1:0; }else{ n1 = 0; }
if (j>0) { n2 = ii.array[j-1][i ]===val?1:0; }else{ n2 = 0; }
if((j>0) && (i0) { n4 = ii.array[j ][i-1]===val?1:0; }else{ n4 = 0; }
if (i0) ) { n6 = ii.array[j+1][i-1]===val?1:0; }else{ n6 = 0; }
if (j ; 1 ^ ; 2 < ; 3 v
this.pathscan = function(arr, pathomit){
pathomit=pathomit||8;
var paths=[],pacnt=0,pcnt=0,px=0,py=0,w=arr[0].length,h=arr.length,
dir=0,pathfinished=true,holepath=false;
for(var j=0;j ny){ ins[pacnt][pcnt].linesegment = 7; }// NE
else { ins[pacnt][pcnt].linesegment = 0; }// E
}else if(ins[pacnt][pcnt].x > nx){
if (ins[pacnt][pcnt].y < ny){ ins[pacnt][pcnt].linesegment = 3; }// SW
else if(ins[pacnt][pcnt].y > ny){ ins[pacnt][pcnt].linesegment = 5; }// NW
else { ins[pacnt][pcnt].linesegment = 4; }// N
}else{
if (ins[pacnt][pcnt].y < ny){ ins[pacnt][pcnt].linesegment = 2; }// S
else if(ins[pacnt][pcnt].y > ny){ ins[pacnt][pcnt].linesegment = 6; }// N
else { ins[pacnt][pcnt].linesegment = 8; }// center, this should not happen
}
}// End of pathpoints loop
}// End of paths loop
return ins;
},// End of internodes()
// 4. Batch interpollation
this.batchinternodes = function(bpaths){
var binternodes = [];
for (var k in bpaths) {
if(!bpaths.hasOwnProperty(k)){ continue; }
binternodes[k] = _this.internodes(bpaths[k]);
}
return binternodes;
},
// 5. tracepath() : recursively trying to fit straight and quadratic spline segments on the 8 direction internode path
// 5.1. Find sequences of points with only 2 segment types
// 5.2. Fit a straight line on the sequence
// 5.3. If the straight line fails (an error>ltreshold), find the point with the biggest error
// 5.4. Fit a quadratic spline through errorpoint (project this to get controlpoint), then measure errors on every point in the sequence
// 5.5. If the spline fails (an error>qtreshold), find the point with the biggest error, set splitpoint = (fitting point + errorpoint)/2
// 5.6. Split sequence and recursively apply 5.2. - 5.7. to startpoint-splitpoint and splitpoint-endpoint sequences
// 5.7. TODO? If splitpoint-endpoint is a spline, try to add new points from the next sequence
this.tracepath = function(path,ltreshold,qtreshold){
var pcnt=0,segtype1,segtype2,seqend,smp=[];
while(pcnt0){ pcnt = seqend; }else{ pcnt = path.length; }
}// End of pcnt loop
return smp;
},// End of tracepath()
// 5.2. - 5.6. recursively fitting a straight or quadratic line segment on this sequence of path nodes,
// called from tracepath()
this.fitseq = function(path,ltreshold,qtreshold,seqstart,seqend){
// return if invalid seqend
if((seqend>path.length)||(seqend<0)){return [];}
// variables
var errorpoint=seqstart, errorval=0, curvepass=true, px, py, dist2;
var tl = (seqend-seqstart); if(tl<0){ tl += path.length; }
var vx = (path[seqend].x-path[seqstart].x) / tl,
vy = (path[seqend].y-path[seqstart].y) / tl;
// 5.2. Fit a straight line on the sequence
var pcnt = (seqstart+1)%path.length, pl;
while(pcnt != seqend){
pl = pcnt-seqstart; if(pl<0){ pl += path.length; }
px = path[seqstart].x + vx * pl; py = path[seqstart].y + vy * pl;
dist2 = (path[pcnt].x-px)*(path[pcnt].x-px) + (path[pcnt].y-py)*(path[pcnt].y-py);
if(dist2>ltreshold){curvepass=false;}
if(dist2>errorval){ errorpoint=pcnt; errorval=dist2; }
pcnt = (pcnt+1)%path.length;
}
// return straight line if fits
if(curvepass){ return [{'type':'L', 'x1':path[seqstart].x,'y1':path[seqstart].y, 'x2':path[seqend].x,'y2':path[seqend].y}]; }
// 5.3. If the straight line fails (an error>ltreshold), find the point with the biggest error
var fitpoint = errorpoint; curvepass = true; errorval = 0;
// 5.4. Fit a quadratic spline through this point, measure errors on every point in the sequence
// helpers and projecting to get control point
var t=(fitpoint-seqstart)/tl, t1=(1-t)*(1-t), t2=2*(1-t)*t, t3=t*t;
var cpx = (t1*path[seqstart].x + t3*path[seqend].x - path[fitpoint].x)/-t2 ,
cpy = (t1*path[seqstart].y + t3*path[seqend].y - path[fitpoint].y)/-t2 ;
// Check every point
pcnt = seqstart+1;
while(pcnt != seqend){
t=(pcnt-seqstart)/tl; t1=(1-t)*(1-t); t2=2*(1-t)*t; t3=t*t;
px = t1 * path[seqstart].x + t2 * cpx + t3 * path[seqend].x;
py = t1 * path[seqstart].y + t2 * cpy + t3 * path[seqend].y;
dist2 = (path[pcnt].x-px)*(path[pcnt].x-px) + (path[pcnt].y-py)*(path[pcnt].y-py);
if(dist2>qtreshold){curvepass=false;}
if(dist2>errorval){ errorpoint=pcnt; errorval=dist2; }
pcnt = (pcnt+1)%path.length;
}
// return spline if fits
if(curvepass){ return [{'type':'Q', 'x1':path[seqstart].x,'y1':path[seqstart].y, 'x2':cpx,'y2':cpy, 'x3':path[seqend].x,'y3':path[seqend].y}]; }
// 5.5. If the spline fails (an error>qtreshold), find the point with the biggest error
// set splitpoint = (fitting point + errorpoint)/2
var splitpoint = Math.floor((fitpoint + errorpoint)/2);
// 5.6. Split sequence and recursively apply 5.2. - 5.6. to startpoint-splitpoint and splitpoint-endpoint sequences
var sm = _this.fitseq(path,ltreshold,qtreshold,seqstart,splitpoint);
sm = sm.concat(_this.fitseq(path,ltreshold,qtreshold,splitpoint,seqend));
return sm;
},// End of fitseq()
// 5. Batch tracing paths
this.batchtracepaths = function(internodepaths,ltres,qtres){
var btracedpaths = [];
for(var k in internodepaths){
if(!internodepaths.hasOwnProperty(k)){ continue; }
btracedpaths.push( _this.tracepath(internodepaths[k],ltres,qtres) );
}
return btracedpaths;
},
// 5. Batch tracing layers
this.batchtracelayers = function(binternodes,ltres,qtres){
var btbis = [];
for(var k in binternodes){
if(!binternodes.hasOwnProperty(k)){ continue; }
btbis[k] = _this.batchtracepaths(binternodes[k],ltres,qtres);
}
return btbis;
},
////////////////////////////////////////////////////////////
//
// SVG Drawing functions
//
////////////////////////////////////////////////////////////
// Rounding to given decimals https://stackoverflow.com/questions/11832914/round-to-at-most-2-decimal-places-in-javascript
this.roundtodec = function(val,places){ return +val.toFixed(places); },
// Getting SVG path element string from a traced path
this.svgpathstring = function(desc,segments,fillcolor,options){
var str='', pcnt;
if( options.roundcoords === -1 ){
str = '';
}else{
str = '';
}
// Rendering control points
for(pcnt=0; pcnt';
str += '';
str += '';
str += '';
}
if( (!segments[pcnt].hasOwnProperty('x3')) && options.lcpr){
str += '';
}
}
return str;
},// End of svgpathstring()
// Converting tracedata to an SVG string, paths are drawn according to a Z-index
// the optional lcpr and qcpr are linear and quadratic control point radiuses
this.getsvgstring = function(tracedata,options){
options = _this.checkoptions(options);
var w = tracedata.width * options.scale, h = tracedata.height * options.scale;
var k, pcnt, thisdesc, viewboxorviewport = options.viewbox ? 'viewBox="0 0 '+w+' '+h+'" ' : 'width="'+w+'" height="'+h+'" ';
// SVG start
var svgstr = '';
return svgstr;
},// End of getsvgstring()
// Comparator for numeric Array.sort
this.compareNumbers = function(a,b){ return a - b; },
// Convert color object to rgba string
this.torgbastr = function(c){ return 'rgba('+c.r+','+c.g+','+c.b+','+c.a+')'; },
// Helper function: Appending an