trapezoid image transform with node-canvas

trapezoid.js

/**
 * Trapezoid
 *  - Image transforming class.
 * 
 * Heavily inspired from:
 * http://www.leven.ch/canvas/perspective.html
 */

/**
 * Module dependencies.
 */

var Canvas = require('canvas')
  , Image = Canvas.Image;

/**
 * Expose constructor.
 */

module.exports = Trapezoid;

/**
 * Point constructor.
 * 
 * @param {Number} x
 * @param {Number} y
 */

function Point(x, y) {
  this.x = x;
  this.y = y;
}

/**
 * Pixel constructor.
 * 
 * @param {Number} r
 * @param {Number} g
 * @param {Number} b
 * @param {Number} a
 */

function Pixel(r, g, b, a) {
  this.r = r;
  this.g = g;
  this.b = b;
  this.a = a;
}

/**
 * Trapezoid constructor.
 * 
 * @param {Buffer} source
 * @param {Number} width
 * @param {Number} height
 */

function Trapezoid(source, width, height) {
  if (!(this instanceof Trapezoid)) {
    return new Trapezoid(source, width, height);
  }
  
  var self = this;
  
  this.width = width;
  this.height = height;
  
  this.dest = new Canvas(this.width, this.height);
  this.dest.width = this.width;
  this.dest.height = this.height;
  
  this.interpolate = this.interpolateNearestNeighbor;
  this.x1 = this.y1 = this.x2 = this.y2 = this.x3 = this.y3 = this.x4 = this.y4 = 0;
  
  this.sourceImage = new Image();
  this.sourceCanvas = new Canvas(this.sourceImage.width, this.sourceImage.height);
  this.sourceContext = this.sourceCanvas.getContext('2d');
  
  this.sourceImage.onload = function() {
    self.sourceCanvas.width = self.sourceImage.width;
    self.sourceCanvas.height = self.sourceImage.height;
    self.sourceContext.drawImage(self.sourceImage, 0, 0);
  };
  this.sourceImage.src = source;
}

/**
 * Set prototype functions.
 */

!function(proto) {
    
  /**
   * Set top-left point.
   * 
   * @param {Number} x
   * @param {Number} y
   * @api public
   */
  
  proto.topLeft = function(x, y) {
    this.x1 = x;
    this.y1 = y;
    return this;
  };
  
  /**
   * Set top-right point.
   * 
   * @param {Number} x
   * @param {Number} y
   * @api public
   */
  
  proto.topRight = function(x, y) {
    this.x2 = x;
    this.y2 = y;
    return this;
  };
  
  /**
   * Set bottom-right point.
   * 
   * @param {Number} x
   * @param {Number} y
   * @api public
   */
  
  proto.bottomRight = function(x, y) {
    this.x3 = x;
    this.y3 = y;
    return this;
  };
  
  /**
   * Set bottom-left point.
   * 
   * @param {Number} x
   * @param {Number} y
   * @api public
   */
  
  proto.bottomLeft = function(x, y) {
    this.x4 = x;
    this.y4 = y;
    return this;
  };
  
  /**
   * @param {Function} callback
   * @api public
   */
  
  proto.transform = function(callback) {
    var p1 = { x: 0, y: 0 } // upper left corner
      , p2 = { x: 0, y: this.sourceImage.height } // lower left corner
      , p3 = { x: this.sourceImage.width, y: this.sourceImage.height } // lower right corner
      , p4 = { x: this.sourceImage.width, y: 0 } // upper right corner
      , q1 = { x: p1.x + this.x1, y: p1.y + this.y1 } // upper left corner
      , q2 = { x: p4.x + this.x4, y: p4.y + this.y4 } // lower left corner
      , q3 = { x: p3.x + this.x3, y: p3.y + this.y3 } // lower right corner
      , q4 = { x: p2.x + this.x2, y: p2.y + this.y2 } // upper right corner
      // get the dimensions of the transformed image
      , min = { x: Math.min(q1.x, q2.x, q3.x, q4.x), y: Math.min(q1.y, q2.y, q3.y, q4.y) }
      , max = { x: Math.max(q1.x, q2.x, q3.x, q4.x), y: Math.max(q1.y, q2.y, q3.y, q4.y) }
      , offsetX = -Math.floor(min.x)
      , offsetY = -Math.floor(min.y)
      , destWidth = this.width
      , destHeight = this.height;
    
    //////////////////////////////////////////////////////////
    // calculate the perspective transformation matrix
    
    // the order of the points does not matter as long as it is the same in both calculateMatrix() calls
    var ps = this.adjoint33(this.calculateMatrix(p1, p2, p3, p4));
    var sq = this.calculateMatrix(q1, q2, q3, q4);
  
    var mTranslation = [[1, 0, offsetX], [0, 1, offsetY], [0, 0, 1]];
    this.transpose33(mTranslation);
    
    var mPerspective = this.matrix33();
  
    this.mult33(ps, sq, mPerspective);
  
    var fw_trafo = this.matrix33();
    this.mult33(mPerspective, mTranslation, fw_trafo);
  
    var bw_trafo = this.adjoint33(fw_trafo);
      
    //////////////////////////////////////////////////////////
    // convert the imagedata arrays of src and dest into a two-dimensional matrix
    
    // create two-dimensional array for storing the destination data
    var destPixelData = new Array(destWidth);
    for (var x = 0; x < destWidth; ++x) {
      destPixelData[x] = new Array(destHeight);
    }
  
    // create two-dimensional array for storing the source data
    var srcCtx = this.sourceContext;
    srcData = srcCtx.getImageData(0, 0, this.sourceImage.width, this.sourceImage.height);
    
    var srcPixelData = new Array(srcData.width);
    for (var x = 0; x < srcData.width; ++x) {
      srcPixelData[x] = new Array(srcData.height);
    }
  
    // filling the source array
    var i = 0;
    for (var y = 0; y < srcData.height; ++y) {
      for (var x = 0; x < srcData.width; ++x) {
        srcPixelData[x][y] = {
          r: srcData.data[i++]
        , g: srcData.data[i++]
        , b: srcData.data[i++]
        , a: srcData.data[i++]
        };
      }
    }
    // append width and height for later use
    srcPixelData[srcPixelData.length] = srcData.width;
    srcPixelData[srcPixelData.length] = srcData.height;
    
    var destCanvas = new Canvas(this.wdith, this.height);
    destCanvas.width = destWidth;
    destCanvas.height = destHeight;
    var destCtx = destCanvas.getContext('2d');
    
    destCtx.beginPath();
    destCtx.moveTo(q1.x + offsetX - 1, q1.y + offsetY - 1);
    destCtx.lineTo(q2.x + offsetX - 1, q2.y + offsetY + 1);
    destCtx.lineTo(q3.x + offsetX + 1, q3.y + offsetY + 1);
    destCtx.lineTo(q4.x + offsetX + 1, q4.y + offsetY - 1);
    destCtx.closePath();
  
    // loop over to-be-warped image and apply the transformation
    for (var x = 0; x < destWidth; ++x) {
      for (var y = 0; y < destHeight; ++y) {
        // if dest pixel is not inside the to-be-warped area, skip the transformation and assign transparent black
        if (1) {
          var srcCoord = this.applyTrafo(x, y, bw_trafo);
          destPixelData[x][y] = this.interpolate(srcCoord, srcPixelData);
        } else {
          destPixelData[x][y] = { r: 0, g: 0, b: 0, a: 0 };
        }
      }
    }
    
    var destData = destCtx.createImageData(destCanvas.width, destCanvas.height);
  
    // write the data back to the imagedata array
    var i = 0;
    for (var y = 0; y < destHeight; ++y) {
      for (var x = 0; x < destWidth; ++x) {
        destData.data[i++] = destPixelData[x][y].r;
        destData.data[i++] = destPixelData[x][y].g;
        destData.data[i++] = destPixelData[x][y].b;
        destData.data[i++] = destPixelData[x][y].a;
      }
    }
  
    destCtx.putImageData(destData, 0, 0);
    
    destCanvas.toBuffer(function(err, buf) {
      callback(buf);
    });
    
    // return destCanvas;
  }
  
  /**
   * @param {Object} srcCoord
   * @param {Object} srcPixelData
   */
  
  proto.interpolateNearestNeighbor = function(srcCoord, srcPixelData) {
    var x0, y0
      , w = srcPixelData[srcPixelData.length-2]
      , h = srcPixelData[srcPixelData.length-1];
  
    // set the dest pixel to transparent black if it is outside the source area
    if (srcCoord.x < 0 || srcCoord.x > w - 1 || srcCoord.y < 0 || srcCoord.y > h - 1) {
      return { r: 0, g: 0, b: 0, a: 0 };
    }
  
    x0 = Math.round(srcCoord.x);
    y0 = Math.round(srcCoord.y);
  
    return srcPixelData[x0][y0];
  };
  
  /**
   * @param {Object} srcCoord
   * @param {Object} srcPixelData
   */
  
  proto.interpolateBilinear = function(srcCoord, srcPixelData) {
    var w = srcPixelData[srcPixelData.length - 2]
      , h = srcPixelData[srcPixelData.length - 1]
      , x0 = Math.floor(srcCoord.x)
      , x1 = x0 + 1
      , y0 = Math.floor(srcCoord.y)
      , y1 = y0 + 1;
  
    // set the dest pixel to transparent black if it is outside the source area
    if (x0 < -1 || x1 > w || y0 < -1 || y1 > h) {
      return { r: 0, g: 0, b: 0, a: 0 };
    }
  
    var f00 = (x1 - srcCoord.x) * (y1 - srcCoord.y)
      , f10 = (srcCoord.x - x0) * (y1 - srcCoord.y)
      , f01 = (x1 - srcCoord.x) * (srcCoord.y - y0)
      , f11 = (srcCoord.x - x0) * (srcCoord.y - y0)
      , alpha = [[-1, -1], [-1, -1]];
    
    if (x0 < 0) {
      x0 = 0;
      alpha[0][0] = 0;
      alpha[0][1] = 0;
    }
    
    if (y0 < 0) {
      y0 = 0;
      alpha[0][0] = 0;
      alpha[1][0] = 0;
    }
    
    if (x1 > w-1) {
      x1 = w-1;
      alpha[1][0] = 0;
      alpha[1][1] = 0;
    }
    
    if (y1 > h-1) {
      y1 = h-1;
      alpha[0][1] = 0;
      alpha[1][1] = 0;
    }
    
    // if alpha[x][x] has not been modified, then the pixel exists --> set alpha
    if (alpha[0][0] === -1) alpha[0][0] = srcPixelData[x0][y0].a;
    if (alpha[1][0] === -1) alpha[1][0] = srcPixelData[x1][y0].a;
    if (alpha[0][1] === -1) alpha[0][1] = srcPixelData[x0][y1].a;
    if (alpha[1][1] === -1) alpha[1][1] = srcPixelData[x1][y1].a;
  
    var pixel = {
      r: Math.round(srcPixelData[x0][y0].r * f00 + srcPixelData[x1][y0].r * f10 + srcPixelData[x0][y1].r * f01 + srcPixelData[x1][y1].r * f11)
    , g: Math.round(srcPixelData[x0][y0].g * f00 + srcPixelData[x1][y0].g * f10 + srcPixelData[x0][y1].g * f01 + srcPixelData[x1][y1].g * f11)
    , b: Math.round(srcPixelData[x0][y0].b * f00 + srcPixelData[x1][y0].b * f10 + srcPixelData[x0][y1].b * f01 + srcPixelData[x1][y1].b * f11)
    , a: Math.round(alpha[0][0] * f00 + alpha[1][0] * f10 + alpha[0][1] * f01 + alpha[1][1] * f11)
    };
  
    if (pixel.r < 0) pixel.r = 0;
    if (pixel.g < 0) pixel.g = 0;
    if (pixel.b < 0) pixel.b = 0;
    if (pixel.a < 0) pixel.a = 0;
  
    if (pixel.r > 255) pixel.r = 255;
    if (pixel.g > 255) pixel.g = 255;
    if (pixel.b > 255) pixel.b = 255;
    if (pixel.a > 255) pixel.a = 255;
  
    return pixel;
  };
  
  /**
   * @param {Number} x
   * @param {Number} y
   * @param {Array} trafo
   */
  
  proto.applyTrafo = function(x, y, trafo) {
    var w = trafo[0][2] * x + trafo[1][2] * y + trafo[2][2] || 1;
    
    return {
      x: (trafo[0][0] * x + trafo[1][0] * y + trafo[2][0]) / w
    , y: (trafo[0][1] * x + trafo[1][1] * y + trafo[2][1]) / w
    };
  };
  
  /**
   * @param {Array} m1
   * @param {Array} m2
   * @oaram {Array} result
   */
  
  proto.mult33 = function(m1, m2, result) {
    for (var i = 0; i < 3; ++i) {
      for (var j = 0; j < 3; ++j) {
        for (var k = 0; k < 3; ++k) {
          result[i][j] += m1[i][k] * m2[k][j];
        }
      }
    }
  };
  
  
  /**
   * @param {Number} m11
   * @param {Number} m12
   * @param {Number} m21
   * @param {Number} m22
   */
  
  proto.det22 = function(m11, m12, m21, m22) {
    return m11 * m22 - m12 * m21;
  };
  
  /**
   * @param {Array} matrix
   */
  
  proto.transpose33 = function(matrix) {
    var tmp = matrix[0][1];
    
    matrix[0][1] = matrix[1][0];
    matrix[1][0] = tmp;
  
    tmp = matrix[0][2];
    matrix[0][2] = matrix[2][0];
    matrix[2][0] = tmp;
  
    tmp = matrix[1][2];
    matrix[1][2] = matrix[2][1];
    matrix[2][1] = tmp;
  };
  
  /**
   * @param {Object} p0
   * @param {Object} p1
   * @param {Object} p2
   * @param {Object} p3
   */
  
  proto.calculateMatrix = function(p0, p1, p2, p3) {
    var a, b, c, d, e, f, g, h
      , dx1, dx2, dy1, dy2, det
      , sx = p0.x - p1.x + p2.x - p3.x
      , sy = p0.y - p1.y + p2.y - p3.y;
    
    if (sx === 0 && sy === 0) {
      a = p1.x - p0.x;
      b = p2.x - p1.x;
      c = p0.x;
      d = p1.y - p0.y;
      e = p2.y - p1.y;
      f = p0.y;
      g = 0;
      h = 0;
      
      return [[a, d, g], [b, e, h], [c, f, 1]];
    }
    
    dx1 = p1.x - p2.x;
    dx2 = p3.x - p2.x;
    dy1 = p1.y - p2.y;
    dy2 = p3.y - p2.y;
    det = this.det22(dx1, dx2, dy1, dy2);

    if (det === 0) {
      throw new Error('det=0');
      return;
    }

    g = this.det22(sx, dx2, sy, dy2)/det;
    h = this.det22(dx1, sx, dy1, sy)/det;

    a = p1.x - p0.x + g * p1.x;
    b = p3.x - p0.x + h * p3.x;
    c = p0.x;
    d = p1.y - p0.y + g * p1.y;
    e = p3.y - p0.y + h * p3.y;
    f = p0.y;
  
    return [[a, d, g], [b, e, h], [c, f, 1]];
  };
  
  /**
   * 
   */
  
  proto.matrix33 = function() {
    return [[0, 0, 0], [0, 0, 0], [0, 0, 0]];
  };
  
  /**
   * @param {Array} matrix
   */
  
  proto.adjoint33 = function(matrix) {
    var m11 = matrix[1][1] * matrix[2][2] - matrix[2][1] * matrix[1][2]
      , m12 = matrix[0][2] * matrix[2][1] - matrix[0][1] * matrix[2][2]
      , m13 = matrix[0][1] * matrix[1][2] - matrix[0][2] * matrix[1][1]
      , m21 = matrix[1][2] * matrix[2][0] - matrix[1][0] * matrix[2][2]
      , m22 = matrix[0][0] * matrix[2][2] - matrix[0][2] * matrix[2][0]
      , m23 = matrix[0][2] * matrix[1][0] - matrix[0][0] * matrix[1][2]
      , m31 = matrix[1][0] * matrix[2][1] - matrix[1][1] * matrix[2][0]
      , m32 = matrix[0][1] * matrix[2][0] - matrix[0][0] * matrix[2][1]
      , m33 = matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
  
    return [[m11, m12, m13], [m21, m22, m23], [m31, m32, m33]];
  };
  
}(Trapezoid.prototype);

usage.js

#!/usr/bin/env node

var Trapezoid = require('../lib/trapezoid')
  , fs = require('fs');

fs.readFile(__dirname + '/../assets/dialogue.png', function(err, data) {
  var tpzd = new Trapezoid(data, 640, 480);
  
  tpzd
    .topLeft(362, 125)
    .topRight(421, 131)
    .bottomRight(414, 191)
    .bottomLeft(354, 184)
    .transform(function(buf) {
      fs.writeFileSync(__dirname + '/../assets/out.png', buf);
    });
});