/**
* Real-time object detector based on the Viola Jones Framework.
* Compatible to OpenCV Haar Cascade Classifiers (stump based only).
*
* Copyright (c) 2012, Martin Tschirsich
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
*/
var objectdetect = (function() {
"use strict";
/**
* Define system-specific optimal array types (Float32Array if available).
*/
var ImageArray, ZeroFilledImageArray;
if (typeof Float32Array !== "undefined") {
ImageArray = ZeroFilledImageArray = Float32Array;
} else {
ZeroFilledImageArray = function(length) {
Array(length);
for (var i = 0; i < length; ++i) this[i] = 0;
};
ZeroFilledImageArray.prototype = ImageArray = Array;
}
var /**
* Converts from a 4-channel RGBA source image to a 1-channel grayscale
* image. Corresponds to the CV_RGB2GRAY OpenCV color space conversion.
*
* @param {Array} src 4-channel 8-bit RGBA source image
* @param {Array} [dst] 1-channel 32-bit destination image. If omitted,
* a new image will be created
* @return {Array} 1-channel 32-bit destination image
*/
convertRgbaToGrayscale = function(src, dst) {
var srcLength = src.length;
if (!dst) { dst = new ImageArray(srcLength >> 2); }
for (var i = 0; i < srcLength; i += 4) {
dst[i >> 2] = (src[i] * 4899 + src[i + 1] * 9617 + src[i + 2] * 1868 + 8192) >> 14;
}
return dst;
},
/**
* Computes the gradient magnitude using a sobel filter after
* applying gaussian smoothing (5x5 filter size). Useful for canny
* pruning.
*
* @param {Array} src 1-channel source image
* @param {Number} srcWidth Width of the source image
* @param {Array} [dst] 1-channel destination image. If omitted,
* a new image will be created
* @return {Array} Destination image
*/
buffer = null,
computeCanny = function(src, srcWidth, srcHeight, dst) {
var srcLength = src.length;
if (!dst) { dst = new ImageArray(srcLength); }
else if (dst === src) { src = new ImageArray(dst); }
// Gaussian filter (size 5, sigma sqrt(2)) horizontal pass:
if (!buffer) buffer = new ImageArray(srcLength);
for (var x = 2; x < srcWidth-2; ++x) {
for (var y = 0; y < srcHeight; ++y) {
var index = x + y * srcWidth;
dst[index] =
0.1117 * src[index - 2] +
0.2365 * src[index - 1] +
0.3036 * src[index ] +
0.2365 * src[index + 1] +
0.1117 * src[index + 2];
}
}
// Gaussian filter (size 5, sigma sqrt(2)) vertical pass:
for (var x = 0; x < srcWidth; ++x) {
for (var y = 2; y < srcHeight-2; ++y) {
var index = x + y*srcWidth;
buffer[index] =
0.1117 * dst[index - (srcWidth << 1)] +
0.2365 * dst[index - srcWidth ] +
0.3036 * dst[index ] +
0.2365 * dst[index + srcWidth ] +
0.1117 * dst[index + (srcWidth << 1)];
}
}
// Compute gradient:
for(x = 2; x < srcWidth - 2; ++x) {
for(y = 2; y < srcHeight - 2; ++y) {
var grad_x =
- buffer[x-1 + (y-1) * srcWidth]
+ buffer[x+1 + (y-1) * srcWidth]
- 2 * buffer[x-1 + y * srcWidth]
+ 2 * buffer[x+1 + y * srcWidth]
- buffer[x-1 + (y+1) * srcWidth]
+ buffer[x+1 + (y+1) * srcWidth];
var grad_y =
buffer[x-1 + (y-1) * srcWidth]
+ 2 * buffer[x + (y-1) * srcWidth]
+ buffer[x+1 + (y-1) * srcWidth]
- buffer[x-1 + (y+1) * srcWidth]
- 2 * buffer[x + (y+1) * srcWidth]
- buffer[x+1 + (y+1) * srcWidth];
dst[x + y * srcWidth] =
(grad_x < 0 ? -grad_x : grad_x) +
(grad_y < 0 ? -grad_y : grad_y);
}
}
return dst;
},
/**
* Computes the integral image of a 1-channel image. Arithmetic
* overflow may occur if the integral exceeds the limits for the
* destination image values ([0, 2^32-1] for am unsigned 32-bit image).
* The integral image is 1 pixel wider both in vertical and horizontal
* direction compared to the source image.
*
* SAT = Summed Area Table
*
* @param {Array} src 1-channel source image
* @param {Number} srcWidth Width of the source image
* @param {Number} srcHeight Height of the source image
* @param {Array} [dst] 1-channel destination image (optional)
* @return {Array} Destination image
*/
computeSat = function(src, srcWidth, srcHeight, dst) {
var srcLength = src.length,
dstWidth = srcWidth + 1;
if (!dst) { dst = new ZeroFilledImageArray(srcLength + dstWidth + srcHeight); }
for (var x = 1; x <= srcWidth; ++x) {
var column_sum = 0;
for (var y = 1; y <= srcHeight; ++y) {
var index = x + y * dstWidth;
column_sum += src[index - y - dstWidth];
dst[index] = dst[index - 1] + column_sum;
}
}
return dst;
},
/**
* Computes the squared integral image of a 1-channel image.
* @see computeSat()
*
* @param {Array} src 1-channel source image
* @param {Number} srcWidth Width of the source image
* @param {Number} srcHeight Height of the source image
* @param {Array} [dst] 1-channel destination image. If omitted, the
* result is written to src (faster)
* @return {Array} Destination image
*/
computeSquaredSat = function(src, srcWidth, srcHeight, dst) {
var srcLength = src.length,
dstWidth = srcWidth + 1;
if (!dst) { dst = new ZeroFilledImageArray(srcLength + dstWidth + srcHeight); }
for (var x = 1; x <= srcWidth; ++x) {
var column_sum = 0;
for (var y = 1; y <= srcHeight; ++y) {
var index = x + y * dstWidth;
var val = src[index - y - dstWidth];
column_sum += val * val;
dst[index] = dst[index - 1] + column_sum;
}
}
return dst;
},
/**
* Computes the rotated / tilted integral image of a 1-channel image.
* @see computeSat()
*
* @param {Array} src 1-channel source image
* @param {Number} srcWidth Width of the source image
* @param {Number} srcHeight Height of the source image
* @param {Array} [dst] 1-channel destination image. If omitted, the
* result is written to src (faster)
* @return {Array} Destination image
*/
computeRsat = function(src, srcWidth, srcHeight, dst) {
var srcLength = src.length,
dstWidth = srcWidth + 1,
dstLength = srcLength + dstWidth + srcHeight;
if (!dst) { dst = new ZeroFilledImageArray(dstLength); }
// Compute first diagonal integral:
for (var y = 1; y <= srcHeight; ++y) {
for (var x = 1; x <= srcWidth; ++x) {
dst[x + y * dstWidth] = src[x - 1 + y * srcWidth - srcWidth] + dst[x + y * dstWidth - dstWidth - 1];
}
}
// Compute second diagonal integral:
for (var y = 1; y <= srcHeight; ++y) {
dst[srcWidth + y * dstWidth] += dst[srcWidth + y * dstWidth - dstWidth];
}
for (var x = srcWidth - 1; x > 0; --x) {
for (var y = srcHeight; y > 0; --y) {
dst[x + y * dstWidth] += dst[x + y * dstWidth - dstWidth] + dst[x + 1 + y * dstWidth - dstWidth];
}
}
return dst;
},
/**
* Compute area on a SAT.
*
* @param {Array} sat 1-channel integral source image
* @param {Number} satWidth Width of the integral source image
* @param {Number} x Area to evaluate
* @param {Number} y Area to evaluate
* @param {Number} width Area to evaluate
* @param {Number} height Area to evaluate
* @return {Number} Area
*/
computeSatSum = function(sat, satWidth, x, y, width, height) {
y *= satWidth;
height *= satWidth;
return sat[x + y ] -
sat[x + width + y ] -
sat[x + y + height] +
sat[x + width + y + height];
},
/**
* Compute area on a RSAT.
* @see computeSatSum()
*
* @param {Array} rsat 1-channel integral source image
* @param {Number} rsatWidth Width of the integral source image
* @param {Number} x Area to evaluate
* @param {Number} y Area to evaluate
* @param {Number} width Area to evaluate
* @param {Number} height Area to evaluate
* @return {Number} Area
*/
computeRSatSum = function(rsat, rsatWidth, x, y, width, height) {
return rsat[x + (y ) * rsatWidth] -
rsat[x + width + (y + width ) * rsatWidth] -
rsat[x - height + (y + height ) * rsatWidth] +
rsat[x + width - height + (y + width + height) * rsatWidth];
},
/**
* Equalizes the histogram of an unsigned 1-channel image with values
* in range [0, 255]. Corresponds to the equalizeHist OpenCV function.
*
* @param {Array} src 1-channel integer source image
* @param {Array} [dst] 1-channel destination image. If omitted, the
* result is written to src
* @return {Array} Destination image
*/
equalizeHistogram = function(src, dst) {
var srcLength = src.length;
if (!dst) { dst = src; }
// Compute histogram and histogram sum:
var hist = new ZeroFilledImageArray(256);
for (var i = 0; i < srcLength; ++i) {
++hist[src[i]];
}
// Compute integral histogram:
var prev = hist[0];
for (var i = 1; i < 256; ++i) {
prev = hist[i] += prev;
}
// Equalize image:
var norm = 255 / srcLength;
for (var i = 0; i < srcLength; ++i) {
dst[i] = ~~(hist[src[i]] * norm + 0.5);
}
return dst;
},
/**
* Evaluates a Haar cascade classifier at a specified scale.
*
* @param {Array} sat SAT of the source image
* @param {Array} rsat RSAT of the source image
* @param {Array} ssat Squared SAT of the source image
* @param {Array} cannySat SAT of canny source image or undefined
* @param {Number} width Width of the source image
* @param {Number} height Height of the source image
* @param {Number} scale Scale
* @param {Object} cascadeClassifier Haar cascade classifier
* @return {Array} Rectangles representing detected object
*/
detectSingleScale = function(sat, rsat, ssat, cannySat, width, height, scale, cascadeClassifier) {
var windowWidth = ~~(cascadeClassifier.size[0] * scale);
var windowHeight = ~~(cascadeClassifier.size[1] * scale);
var stepX = ~~(0.5 * scale + 1.5); // = 2;
var stepY = ~~(0.5 * scale + 1.5); // = 2;
var rects = [];
for (var x = 0; x + windowWidth <= width; x += stepX) {
for (var y = 0; y + windowHeight <= height; y += stepY) {
var invArea = 1 / (windowWidth * windowHeight);
// Canny test:
if (cannySat) {
var edgesDensity = computeSatSum(cannySat, width + 1, x, y, windowWidth, windowHeight) * invArea;
if (edgesDensity < 20 || edgesDensity > 100) {
continue;
}
}
// Correct?
var satOffset = x + y * (width + 1);
var satHeight = windowHeight * (width + 1);
var mean = (sat[satOffset] -
sat[satOffset + windowWidth] -
sat[satOffset + satHeight] +
sat[satOffset + windowWidth + satHeight]) * invArea;
var variance = (ssat[satOffset] -
ssat[satOffset + windowWidth] -
ssat[satOffset + satHeight] +
ssat[satOffset + windowWidth + satHeight]) * invArea - mean * mean;
var std = variance > 1 ? Math.sqrt(variance) : 1;
// Evaluate cascade classifier: stages
var complexClassifiers = cascadeClassifier.complexClassifiers;
var found = true;
for (var i = 0, iEnd = complexClassifiers.length; i < iEnd; ++i) {
var complexClassifier = complexClassifiers[i];
// Evaluate complex classifier: trees
var simpleClassifiers = complexClassifier.simpleClassifiers;
var complexClassifierThreshold = complexClassifier.threshold;
var complexClassifierSum = 0;
for (var j = 0, jEnd = simpleClassifiers.length; j < jEnd; ++j) {
var simpleClassifier = simpleClassifiers[j];
// Evaluate simple classifier: nodes
var features = simpleClassifier.features;
var simpleClassifierSum = 0;
if (simpleClassifier.tilted === 1) {
for (var k = 0, kEnd = features.length; k < kEnd; ++k) {
var feature = features[k];
// Evaluate feature: rects
var featureOffset = ~~(x + feature[0] * scale) + ~~(y + feature[1] * scale) * (width + 1);
var featureWidth = ~~(feature[2] * scale);
var featureWidthTimesWidth = ~~(feature[2] * scale) * (width + 1);
var featureHeight = ~~(feature[3] * scale);
var featureHeightTimesWidth = ~~(feature[3] * scale) * (width + 1);
simpleClassifierSum +=
(rsat[featureOffset] -
rsat[featureOffset + featureWidth + featureWidthTimesWidth] -
rsat[featureOffset - featureHeight + featureHeightTimesWidth] +
rsat[featureOffset + featureWidth - featureHeight + featureWidthTimesWidth + featureHeightTimesWidth]) * feature[4];
}
} else {
for (var k = 0, kEnd = features.length; k < kEnd; ++k) {
var feature = features[k];
// Evaluate feature: rects
var featureOffset = ~~(x + feature[0] * scale) + ~~(y + feature[1] * scale) * (width + 1);
var featureWidth = ~~(feature[2] * scale);
var featureHeight = ~~(feature[3] * scale) * (width + 1);
simpleClassifierSum +=
(sat[featureOffset] -
sat[featureOffset + featureWidth] -
sat[featureOffset + featureHeight] +
sat[featureOffset + featureWidth + featureHeight]) * feature[4];
}
}
complexClassifierSum += (simpleClassifierSum * invArea < simpleClassifier.threshold * std) ? simpleClassifier.left_val : simpleClassifier.right_val;
// Possible optimization if all values are positive:
// if (complexClassifierSum >= complexClassifierThreshold) break;
}
if (complexClassifierSum < complexClassifierThreshold) {
found = false;
break;
}
}
if (found) rects.push([x, y, windowWidth, windowHeight]);
}
}
return rects;
},
/**
* Evaluates a Haar cascade classifier at all scales.
*
* @param {Array} sat SAT of the source image
* @param {Array} rsat RSAT of the source image
* @param {Array} ssat Squared SAT of the source image
* @param {Array} cannySat SAT of canny source image or undefined
* @param {Number} width Width of the source image
* @param {Number} height Height of the source image
* @param {Object} cascadeClassifier Haar cascade classifier
* @return {Array} Rectangles representing detected object
*/
detectMultiScale = function(sat, rsat, ssat, cannySat, width, height, cascadeClassifier, scaleFactor, scaleMin) {
var initialWidth = cascadeClassifier.size[0];
var initialHeight = cascadeClassifier.size[1];
if (!scaleMin) scaleMin = 1;
if (!scaleFactor) scaleFactor = 1.2;
var scale = scaleMin;
var rects = [];
while (scale * initialWidth < width && scale * initialHeight < height) {
rects = rects.concat(detectSingleScale(sat, rsat, ssat, cannySat, width, height, scale, cascadeClassifier));
scale *= scaleFactor;
}
return rects;
},
/**
* Evaluates a Haar cascade classifier at increasingly coarser scale.
* Stops the evaluation as soon as the first object has been detected.
*
* @param {Array} sat SAT of the source image
* @param {Array} rsat RSAT of the source image
* @param {Array} ssat Squared SAT of the source image
* @param {Array} cannySat SAT of canny source image or undefined
* @param {Number} width Width of the source image
* @param {Number} height Height of the source image
* @param {Object} cascadeClassifier Haar cascade classifier
* @return {Array} Rectangles representing detected object
*/
detectFinestScale = function(sat, rsat, ssat, cannySat, width, height, cascadeClassifier) {
var initialWidth = cascadeClassifier.size[0];
var initialHeight = cascadeClassifier.size[1];
var scale = 1;
var scaleFactor = 1.2;
var rects = [];
while (scale * initialWidth < width && scale * initialHeight < height) {
rects = detectSingleScale(sat, rsat, ssat, cannySat, width, height, scale, cascadeClassifier);
if (rects[0]) break;
scale *= scaleFactor;
}
return rects;
},
/**
* Groups rectangles together using a rectilinear distance metric. For
* each group of related rectangles, a representative mean rectangle
* is returned.
*
* @param {Array} rects Rectangles (Arrays of 4 floats)
* @param {Number} minNeighbors
* @return {Array} Mean rectangles (Arrays of 4 floats)
*/
groupRectangles = function(rects, minNeighbors) {
var rectsLength = rects.length;
// Partition rects into similarity classes:
var numClasses = 0;
var labels = new Array(rectsLength);
for (var i = 0; i < labels.length; ++i) {
labels[i] = 0;
}
for (var i = 0; i < rectsLength; ++i) {
var found = false;
for (var j = 0; j < i; ++j) {
// Determine similarity:
var rect1 = rects[i];
var rect2 = rects[j];
var delta = 0.1 * (Math.min(rect1[2], rect2[2]) + Math.min(rect1[3], rect2[3]));
if (Math.abs(rect1[0] - rect2[0]) <= delta &&
Math.abs(rect1[1] - rect2[1]) <= delta &&
Math.abs(rect1[0] + rect1[2] - rect2[0] - rect2[2]) <= delta &&
Math.abs(rect1[1] + rect1[3] - rect2[1] - rect2[3]) <= delta) {
labels[i] = labels[j];
found = true;
break;
}
}
if (!found) {
labels[i] = numClasses++;
}
}
// Compute average rectangle (group) for each cluster:
var groups = new Array(numClasses);
for (var i = 0; i < numClasses; ++i) {
groups[i] = [0, 0, 0, 0, 0];
}
for (var i = 0; i < rectsLength; ++i) {
var label = labels[i];
groups[label][0] += rects[i][0];
groups[label][1] += rects[i][1];
groups[label][2] += rects[i][2];
groups[label][3] += rects[i][3];
groups[label][4]++;
}
for (var i = 0; i < numClasses; ++i) {
var numNeighbors = groups[i][4];
if (numNeighbors >= minNeighbors) {
groups[i][0] /= numNeighbors;
groups[i][1] /= numNeighbors;
groups[i][2] /= numNeighbors;
groups[i][3] /= numNeighbors;
}
}
// Filter out small rectangles inside larger rectangles:
var filteredGroups = [];
for (var i = 0; i < numClasses; ++i) {
var r1 = groups[i];
for (var j = 0; j < numClasses; ++j) {
if (i === j) continue;
var r2 = groups[j];
var dx = r2[2] * 0.2;
var dy = r2[3] * 0.2;
if (r1[0] >= r2[0] - dx &&
r1[1] >= r2[1] - dy &&
r1[0] + r1[2] <= r2[0] + r2[2] + dx &&
r1[1] + r1[3] <= r2[1] + r2[3] + dy) {
break;
}
}
if (j === numClasses) {
filteredGroups.push(r1);
}
}
return filteredGroups;
};
return {
equalizeHistogram: equalizeHistogram,
convertRgbaToGrayscale: convertRgbaToGrayscale,
computeCanny: computeCanny,
computeSat: computeSat,
computeRsat: computeRsat,
computeSatSum: computeSatSum,
computeSquaredSat: computeSquaredSat,
computeRSatSum: computeRSatSum,
groupRectangles: groupRectangles,
detectMultiScale: detectMultiScale,
detectSingleScale: detectSingleScale,
detectFinestScale: detectFinestScale
};
})();