(function() {
/**
* ViolaJones utility.
* @static
* @constructor
*/
tracking.ViolaJones = {};
/**
* Holds the minimum area of intersection that defines when a rectangle is
* from the same group. Often when a face is matched multiple rectangles are
* classified as possible rectangles to represent the face, when they
* intersects they are grouped as one face.
* @type {number}
* @default 0.5
* @static
*/
tracking.ViolaJones.REGIONS_OVERLAP = 0.5;
/**
* Holds the HAAR cascade classifiers converted from OpenCV training.
* @type {array}
* @static
*/
tracking.ViolaJones.classifiers = {};
/**
* Detects through the HAAR cascade data rectangles matches.
* @param {pixels} pixels The pixels in a linear [r,g,b,a,...] array.
* @param {number} width The image width.
* @param {number} height The image height.
* @param {number} initialScale The initial scale to start the block
* scaling.
* @param {number} scaleFactor The scale factor to scale the feature block.
* @param {number} stepSize The block step size.
* @param {number} edgesDensity Percentage density edges inside the
* classifier block. Value from [0.0, 1.0], defaults to 0.2. If specified
* edge detection will be applied to the image to prune dead areas of the
* image, this can improve significantly performance.
* @param {number} data The HAAR cascade data.
* @return {array} Found rectangles.
* @static
*/
tracking.ViolaJones.detect = function(pixels, width, height, initialScale, scaleFactor, stepSize, edgesDensity, data) {
var total = 0;
var rects = [];
var integralImage = new Int32Array(width * height);
var integralImageSquare = new Int32Array(width * height);
var tiltedIntegralImage = new Int32Array(width * height);
var integralImageSobel;
if (edgesDensity > 0) {
integralImageSobel = new Int32Array(width * height);
}
tracking.Image.computeIntegralImage(pixels, width, height, integralImage, integralImageSquare, tiltedIntegralImage, integralImageSobel);
var minWidth = data[0];
var minHeight = data[1];
var scale = initialScale * scaleFactor;
var blockWidth = (scale * minWidth) | 0;
var blockHeight = (scale * minHeight) | 0;
while (blockWidth < width && blockHeight < height) {
var step = (scale * stepSize + 0.5) | 0;
for (var i = 0; i < (height - blockHeight); i += step) {
for (var j = 0; j < (width - blockWidth); j += step) {
if (edgesDensity > 0) {
if (this.isTriviallyExcluded(edgesDensity, integralImageSobel, i, j, width, blockWidth, blockHeight)) {
continue;
}
}
if (this.evalStages_(data, integralImage, integralImageSquare, tiltedIntegralImage, i, j, width, blockWidth, blockHeight, scale)) {
rects[total++] = {
width: blockWidth,
height: blockHeight,
x: j,
y: i
};
}
}
}
scale *= scaleFactor;
blockWidth = (scale * minWidth) | 0;
blockHeight = (scale * minHeight) | 0;
}
return this.mergeRectangles_(rects);
};
/**
* Fast check to test whether the edges density inside the block is greater
* than a threshold, if true it tests the stages. This can improve
* significantly performance.
* @param {number} edgesDensity Percentage density edges inside the
* classifier block.
* @param {array} integralImageSobel The integral image of a sobel image.
* @param {number} i Vertical position of the pixel to be evaluated.
* @param {number} j Horizontal position of the pixel to be evaluated.
* @param {number} width The image width.
* @return {boolean} True whether the block at position i,j can be skipped,
* false otherwise.
* @static
* @protected
*/
tracking.ViolaJones.isTriviallyExcluded = function(edgesDensity, integralImageSobel, i, j, width, blockWidth, blockHeight) {
var wbA = i * width + j;
var wbB = wbA + blockWidth;
var wbD = wbA + blockHeight * width;
var wbC = wbD + blockWidth;
var blockEdgesDensity = (integralImageSobel[wbA] - integralImageSobel[wbB] - integralImageSobel[wbD] + integralImageSobel[wbC]) / (blockWidth * blockHeight * 255);
if (blockEdgesDensity < edgesDensity) {
return true;
}
return false;
};
/**
* Evaluates if the block size on i,j position is a valid HAAR cascade
* stage.
* @param {number} data The HAAR cascade data.
* @param {number} i Vertical position of the pixel to be evaluated.
* @param {number} j Horizontal position of the pixel to be evaluated.
* @param {number} width The image width.
* @param {number} blockSize The block size.
* @param {number} scale The scale factor of the block size and its original
* size.
* @param {number} inverseArea The inverse area of the block size.
* @return {boolean} Whether the region passes all the stage tests.
* @private
* @static
*/
tracking.ViolaJones.evalStages_ = function(data, integralImage, integralImageSquare, tiltedIntegralImage, i, j, width, blockWidth, blockHeight, scale) {
var inverseArea = 1.0 / (blockWidth * blockHeight);
var wbA = i * width + j;
var wbB = wbA + blockWidth;
var wbD = wbA + blockHeight * width;
var wbC = wbD + blockWidth;
var mean = (integralImage[wbA] - integralImage[wbB] - integralImage[wbD] + integralImage[wbC]) * inverseArea;
var variance = (integralImageSquare[wbA] - integralImageSquare[wbB] - integralImageSquare[wbD] + integralImageSquare[wbC]) * inverseArea - mean * mean;
var standardDeviation = 1;
if (variance > 0) {
standardDeviation = Math.sqrt(variance);
}
var length = data.length;
for (var w = 2; w < length; ) {
var stageSum = 0;
var stageThreshold = data[w++];
var nodeLength = data[w++];
while (nodeLength--) {
var rectsSum = 0;
var tilted = data[w++];
var rectsLength = data[w++];
for (var r = 0; r < rectsLength; r++) {
var rectLeft = (j + data[w++] * scale + 0.5) | 0;
var rectTop = (i + data[w++] * scale + 0.5) | 0;
var rectWidth = (data[w++] * scale + 0.5) | 0;
var rectHeight = (data[w++] * scale + 0.5) | 0;
var rectWeight = data[w++];
var w1;
var w2;
var w3;
var w4;
if (tilted) {
// RectSum(r) = RSAT(x-h+w, y+w+h-1) + RSAT(x, y-1) - RSAT(x-h, y+h-1) - RSAT(x+w, y+w-1)
w1 = (rectLeft - rectHeight + rectWidth) + (rectTop + rectWidth + rectHeight - 1) * width;
w2 = rectLeft + (rectTop - 1) * width;
w3 = (rectLeft - rectHeight) + (rectTop + rectHeight - 1) * width;
w4 = (rectLeft + rectWidth) + (rectTop + rectWidth - 1) * width;
rectsSum += (tiltedIntegralImage[w1] + tiltedIntegralImage[w2] - tiltedIntegralImage[w3] - tiltedIntegralImage[w4]) * rectWeight;
} else {
// RectSum(r) = SAT(x-1, y-1) + SAT(x+w-1, y+h-1) - SAT(x-1, y+h-1) - SAT(x+w-1, y-1)
w1 = rectTop * width + rectLeft;
w2 = w1 + rectWidth;
w3 = w1 + rectHeight * width;
w4 = w3 + rectWidth;
rectsSum += (integralImage[w1] - integralImage[w2] - integralImage[w3] + integralImage[w4]) * rectWeight;
// TODO: Review the code below to analyze performance when using it instead.
// w1 = (rectLeft - 1) + (rectTop - 1) * width;
// w2 = (rectLeft + rectWidth - 1) + (rectTop + rectHeight - 1) * width;
// w3 = (rectLeft - 1) + (rectTop + rectHeight - 1) * width;
// w4 = (rectLeft + rectWidth - 1) + (rectTop - 1) * width;
// rectsSum += (integralImage[w1] + integralImage[w2] - integralImage[w3] - integralImage[w4]) * rectWeight;
}
}
var nodeThreshold = data[w++];
var nodeLeft = data[w++];
var nodeRight = data[w++];
if (rectsSum * inverseArea < nodeThreshold * standardDeviation) {
stageSum += nodeLeft;
} else {
stageSum += nodeRight;
}
}
if (stageSum < stageThreshold) {
return false;
}
}
return true;
};
/**
* Postprocess the detected sub-windows in order to combine overlapping
* detections into a single detection.
* @param {array} rects
* @return {array}
* @private
* @static
*/
tracking.ViolaJones.mergeRectangles_ = function(rects) {
var disjointSet = new tracking.DisjointSet(rects.length);
for (var i = 0; i < rects.length; i++) {
var r1 = rects[i];
for (var j = 0; j < rects.length; j++) {
var r2 = rects[j];
if (tracking.Math.intersectRect(r1.x, r1.y, r1.x + r1.width, r1.y + r1.height, r2.x, r2.y, r2.x + r2.width, r2.y + r2.height)) {
var x1 = Math.max(r1.x, r2.x);
var y1 = Math.max(r1.y, r2.y);
var x2 = Math.min(r1.x + r1.width, r2.x + r2.width);
var y2 = Math.min(r1.y + r1.height, r2.y + r2.height);
var overlap = (x1 - x2) * (y1 - y2);
var area1 = (r1.width * r1.height);
var area2 = (r2.width * r2.height);
if ((overlap / (area1 * (area1 / area2)) >= this.REGIONS_OVERLAP) &&
(overlap / (area2 * (area1 / area2)) >= this.REGIONS_OVERLAP)) {
disjointSet.union(i, j);
}
}
}
}
var map = {};
for (var k = 0; k < disjointSet.length; k++) {
var rep = disjointSet.find(k);
if (!map[rep]) {
map[rep] = {
total: 1,
width: rects[k].width,
height: rects[k].height,
x: rects[k].x,
y: rects[k].y
};
continue;
}
map[rep].total++;
map[rep].width += rects[k].width;
map[rep].height += rects[k].height;
map[rep].x += rects[k].x;
map[rep].y += rects[k].y;
}
var result = [];
Object.keys(map).forEach(function(key) {
var rect = map[key];
result.push({
total: rect.total,
width: (rect.width / rect.total + 0.5) | 0,
height: (rect.height / rect.total + 0.5) | 0,
x: (rect.x / rect.total + 0.5) | 0,
y: (rect.y / rect.total + 0.5) | 0
});
});
return result;
};
}());