Skip to content

Commit b9caf4d

Browse files
mairatmaeduardolundgren
mairatma
authored and
eduardolundgren
committed
ColorTracker - Multiple results and better performance
1 parent 4f91f6b commit b9caf4d

8 files changed

Lines changed: 500 additions & 214 deletions

File tree

‎bower.json‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,6 @@
1818
"bower_components"
1919
],
2020
"dependencies": {
21-
"threejs": "~0.0.67"
21+
"threejs": "r67"
2222
}
2323
}

‎build/tracking-min.js‎

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎build/tracking.js‎

Lines changed: 211 additions & 95 deletions
Original file line numberDiff line numberDiff line change
@@ -1681,6 +1681,14 @@
16811681
*/
16821682
tracking.ColorTracker.knownColors_ = {};
16831683

1684+
/**
1685+
* Caches coordinates values of the neighbours surrounding a pixel.
1686+
* @type {Object.<number, Int32Array>}
1687+
* @private
1688+
* @static
1689+
*/
1690+
tracking.ColorTracker.neighbours_ = {};
1691+
16841692
/**
16851693
* Registers a color as known color.
16861694
* @param {string} name The color name.
@@ -1720,78 +1728,115 @@
17201728
* the blog extracted from the cloud points.
17211729
* @private
17221730
*/
1723-
tracking.ColorTracker.prototype.calculateCentralCoordinate_ = function(cloud, total) {
1724-
var dx = 0;
1725-
var dy = 0;
1731+
tracking.ColorTracker.prototype.calculateDimensions_ = function(cloud, total) {
17261732
var maxx = -1;
17271733
var maxy = -1;
17281734
var minx = Infinity;
17291735
var miny = Infinity;
1730-
var totalInliers = 0;
17311736

17321737
for (var c = 0; c < total; c += 2) {
17331738
var x = cloud[c];
17341739
var y = cloud[c + 1];
17351740

1736-
if (x > -1 && y > -1) {
1737-
dx += x;
1738-
dy += y;
1739-
totalInliers++;
1740-
1741-
if (x < minx) {
1742-
minx = x;
1743-
}
1744-
if (x > maxx) {
1745-
maxx = x;
1746-
}
1747-
if (y < miny) {
1748-
miny = y;
1749-
}
1750-
if (y > maxy) {
1751-
maxy = y;
1752-
}
1741+
if (x < minx) {
1742+
minx = x;
1743+
}
1744+
if (x > maxx) {
1745+
maxx = x;
1746+
}
1747+
if (y < miny) {
1748+
miny = y;
1749+
}
1750+
if (y > maxy) {
1751+
maxy = y;
17531752
}
17541753
}
1755-
if (totalInliers === 0) {
1756-
return null;
1757-
}
1754+
17581755
return {
1759-
x: dx / totalInliers,
1760-
y: dy / totalInliers,
1761-
z: 60 - ((maxx - minx) + (maxy - miny)) / 2
1756+
maxx: maxx,
1757+
maxy: maxy,
1758+
minx: minx,
1759+
miny: miny
17621760
};
17631761
};
17641762

17651763
/**
1766-
* Flags the cloud points with -1 when the pixel of the desired color is far
1767-
* by `tracking.ColorTracker.MIN_PIXELS` of the area with a bigger density
1768-
* of pixels of the desired color. This helps to reduce outliers from the
1769-
* tracking.
1770-
* @param {Array.<number>} cloud Major row order array containing all the
1771-
* points from the desired color, e.g. [x1, y1, c2, y2, ...].
1772-
* @param {number} total Total numbers of pixels of the desired color.
1773-
* @private
1764+
* Gets the colors being tracked by the `ColorTracker` instance.
1765+
* @return {Array.<string>}
17741766
*/
1775-
tracking.ColorTracker.prototype.flagOutliers_ = function(cloud, total) {
1776-
for (var m = 0; m < total; m += 2) {
1777-
var dist = 0;
1778-
for (var n = 2; n < total; n += 2) {
1779-
dist += tracking.Math.distance(cloud[m], cloud[m + 1], cloud[n], cloud[n + 1]);
1780-
}
1781-
if (dist/total >= tracking.ColorTracker.MIN_PIXELS) {
1782-
cloud[m] = -1;
1783-
cloud[m + 1] = -1;
1784-
total[m]--;
1785-
}
1767+
tracking.ColorTracker.prototype.getColors = function() {
1768+
return this.colors;
1769+
};
1770+
1771+
/**
1772+
* Gets the eight offset values of the neighbours surrounding a pixel.
1773+
* @param {number} width The image width
1774+
* @return {array} Array with the eight offset values of the neighbours
1775+
* surrounding a pixel.
1776+
*/
1777+
tracking.ColorTracker.prototype.getNeighboursForWidth_ = function(width) {
1778+
if (tracking.ColorTracker.neighbours_[width]) {
1779+
return tracking.ColorTracker.neighbours_[width];
17861780
}
1781+
1782+
var neighbours = new Int32Array(8);
1783+
1784+
neighbours[0] = -width * 4;
1785+
neighbours[1] = -width * 4 + 4;
1786+
neighbours[2] = 4;
1787+
neighbours[3] = width * 4 + 4;
1788+
neighbours[4] = width * 4;
1789+
neighbours[5] = width * 4 - 4;
1790+
neighbours[6] = -4;
1791+
neighbours[7] = -width * 4 - 4;
1792+
1793+
tracking.ColorTracker.neighbours_ = neighbours;
1794+
1795+
return neighbours;
17871796
};
17881797

17891798
/**
1790-
* Gets the colors being tracked by the `ColorTracker` instance.
1791-
* @return {Array.<string>}
1799+
* Unites groups whose bounding box intersect with each other.
1800+
* @param {Array.<Object>} results
17921801
*/
1793-
tracking.ColorTracker.prototype.getColors = function() {
1794-
return this.colors;
1802+
tracking.ColorTracker.prototype.regroupResults_ = function(results) {
1803+
var newResults = [];
1804+
var going;
1805+
1806+
for (var r = 0; r < results.length; r++) {
1807+
going = true;
1808+
1809+
for (var s = r + 1; s < results.length; s++) {
1810+
if ((results[r].minx >= results[s].minx && results[r].minx <= results[s].maxx) ||
1811+
(results[r].maxx >= results[s].minx && results[r].maxx <= results[s].maxx)) {
1812+
if ((results[r].miny >= results[s].miny && results[r].miny <= results[s].maxy) ||
1813+
(results[r].maxy >= results[s].miny && results[r].maxy <= results[s].maxy)) {
1814+
1815+
going = false;
1816+
1817+
results[s].minx = Math.min(results[r].minx, results[s].minx);
1818+
results[s].maxx = Math.max(results[r].maxx, results[s].maxx);
1819+
results[s].miny = Math.min(results[r].miny, results[s].miny);
1820+
results[s].maxy = Math.max(results[r].maxy, results[s].maxy);
1821+
results[s].z = 60 - ((results[s].maxx - results[s].minx) + (results[s].maxy - results[s].miny)) / 2;
1822+
1823+
break;
1824+
}
1825+
}
1826+
}
1827+
1828+
if (going) {
1829+
newResults.push({
1830+
color: results[r].color,
1831+
height: results[r].maxy - results[r].miny,
1832+
width: results[r].maxx - results[r].minx,
1833+
x: results[r].minx,
1834+
y: results[r].miny
1835+
});
1836+
}
1837+
}
1838+
1839+
return newResults;
17951840
};
17961841

17971842
/**
@@ -1810,58 +1855,105 @@
18101855
* @param {number} height The pixels canvas height.
18111856
*/
18121857
tracking.ColorTracker.prototype.track = function(pixels, width, height) {
1813-
var instance = this,
1814-
color,
1815-
colorFn,
1816-
colorIndex,
1817-
colors = this.getColors(),
1818-
cloud = [],
1819-
payload = [],
1820-
total = [];
1821-
1822-
tracking.Matrix.forEach(pixels, width, height, function(r, g, b, a, w, i, j) {
1823-
for (colorIndex = -1; color = colors[++colorIndex];) {
1824-
if (!cloud[colorIndex]) {
1825-
total[colorIndex] = 0;
1826-
cloud[colorIndex] = [];
1827-
}
1828-
1829-
colorFn = tracking.ColorTracker.knownColors_[color];
1830-
1831-
if (colorFn && colorFn.call(instance, r, g, b, a, w, i, j)) {
1832-
total[colorIndex] += 2;
1833-
cloud[colorIndex].push(j, i);
1834-
}
1835-
}
1836-
});
1858+
var colors = this.getColors();
1859+
var payload = [];
18371860

1838-
for (colorIndex = -1; color = colors[++colorIndex];) {
1839-
if (total[colorIndex] < tracking.ColorTracker.MIN_PIXELS) {
1840-
continue;
1841-
}
1842-
1843-
instance.flagOutliers_(cloud[colorIndex], total[colorIndex]);
1844-
1845-
var data = instance.calculateCentralCoordinate_(cloud[colorIndex], total[colorIndex]);
1846-
if (data) {
1847-
data.color = colors[colorIndex];
1848-
data.pixels = cloud[colorIndex];
1849-
payload.push(data);
1850-
}
1861+
for (var colorIndex = 0; colorIndex < colors.length; colorIndex++) {
1862+
payload.push(this.trackColor_(pixels, width, height, colors[colorIndex]));
18511863
}
18521864

18531865
if (payload.length) {
1854-
if (instance.onFound) {
1855-
instance.onFound.call(instance, payload);
1866+
if (this.onFound) {
1867+
this.onFound.call(this, payload);
18561868
}
18571869
}
18581870
else {
1859-
if (instance.onNotFound) {
1860-
instance.onNotFound.call(instance, payload);
1871+
if (this.onNotFound) {
1872+
this.onNotFound.call(this, payload);
18611873
}
18621874
}
18631875
};
18641876

1877+
/**
1878+
* Find the given color in the given matrix of pixels.
1879+
* @param {Uint8ClampedArray} pixels The pixels data to track.
1880+
* @param {number} width The pixels canvas width.
1881+
* @param {number} height The pixels canvas height.
1882+
* @param {string} color The color to be found
1883+
*/
1884+
tracking.ColorTracker.prototype.trackColor_ = function(pixels, width, height, color) {
1885+
var colorFn = tracking.ColorTracker.knownColors_[color];
1886+
var currGroup = new Int32Array(pixels.length >> 2);
1887+
var currGroupSize;
1888+
var currI;
1889+
var currJ;
1890+
var currW;
1891+
var marked = new Int8Array(pixels.length);
1892+
var minPixels = tracking.ColorTracker.MIN_PIXELS;
1893+
var neighboursW = this.getNeighboursForWidth_(width);
1894+
var queue = new Int32Array(pixels.length);
1895+
var queuePosition;
1896+
var results = [];
1897+
var w = -4;
1898+
1899+
if (!colorFn) {
1900+
return results;
1901+
}
1902+
1903+
for (var i = 0; i < height; i++) {
1904+
for (var j = 0; j < width; j++) {
1905+
w += 4;
1906+
1907+
if (marked[w]) {
1908+
continue;
1909+
}
1910+
1911+
currGroupSize = 0;
1912+
1913+
queuePosition = -1;
1914+
queue[++queuePosition] = w;
1915+
queue[++queuePosition] = i;
1916+
queue[++queuePosition] = j;
1917+
1918+
marked[w] = 1;
1919+
1920+
while (queuePosition >= 0) {
1921+
currJ = queue[queuePosition--];
1922+
currI = queue[queuePosition--];
1923+
currW = queue[queuePosition--];
1924+
1925+
if (colorFn.call(this, pixels[currW], pixels[currW + 1], pixels[currW + 2], pixels[currW + 3], currW, currI, currJ)) {
1926+
currGroup[currGroupSize++] = currJ;
1927+
currGroup[currGroupSize++] = currI;
1928+
1929+
for (var k = 0; k < neighboursW.length; k++) {
1930+
var otherW = currW + neighboursW[k];
1931+
var otherI = currI + neighboursI[k];
1932+
var otherJ = currJ + neighboursJ[k];
1933+
if (!marked[otherW] && otherI >= 0 && otherI < height && otherJ >= 0 && otherJ < width) {
1934+
queue[++queuePosition] = otherW;
1935+
queue[++queuePosition] = otherI;
1936+
queue[++queuePosition] = otherJ;
1937+
1938+
marked[otherW] = 1;
1939+
}
1940+
}
1941+
}
1942+
}
1943+
1944+
if (currGroupSize >= minPixels) {
1945+
var data = this.calculateDimensions_(currGroup, currGroupSize);
1946+
if (data) {
1947+
data.color = color;
1948+
results.push(data);
1949+
}
1950+
}
1951+
}
1952+
}
1953+
1954+
return this.regroupResults_(results);
1955+
}
1956+
18651957
// Default colors
18661958
//===================
18671959

@@ -1875,7 +1967,7 @@
18751967
if ((g - r) >= thresholdGreen && (b - r) >= thresholdBlue) {
18761968
return true;
18771969
}
1878-
return Math.sqrt(dx * dx + dy * dy + dz * dz) < 80;
1970+
return dx * dx + dy * dy + dz * dz < 6400;
18791971
});
18801972

18811973
tracking.ColorTracker.registerColor('magenta', function(r, g, b) {
@@ -1887,7 +1979,7 @@
18871979
if ((r - g) >= threshold && (b - g) >= threshold) {
18881980
return true;
18891981
}
1890-
return Math.sqrt(dx * dx + dy * dy + dz * dz) < 140;
1982+
return dx * dx + dy * dy + dz * dz < 19600;
18911983
});
18921984

18931985
tracking.ColorTracker.registerColor('yellow', function(r, g, b) {
@@ -1896,12 +1988,36 @@
18961988
dy = g - 255,
18971989
dz = b - 0;
18981990

1899-
if ((r - g) >= threshold && (b - g) >= threshold) {
1991+
if ((r - b) >= threshold && (g - b) >= threshold) {
19001992
return true;
19011993
}
1902-
return Math.sqrt(dx * dx + dy * dy + dz * dz) < 100;
1994+
return dx * dx + dy * dy + dz * dz < 10000;
19031995
});
19041996

1997+
1998+
// Caching neighbour i/j offset values.
1999+
//===================
2000+
2001+
var neighboursI = new Int32Array(8);
2002+
var neighboursJ = new Int32Array(8);
2003+
2004+
neighboursI[0] = -1;
2005+
neighboursI[1] = -1;
2006+
neighboursI[2] = 0;
2007+
neighboursI[3] = 1;
2008+
neighboursI[4] = 1;
2009+
neighboursI[5] = 1;
2010+
neighboursI[6] = 0;
2011+
neighboursI[7] = -1;
2012+
2013+
neighboursJ[0] = 0;
2014+
neighboursJ[1] = 1;
2015+
neighboursJ[2] = 1;
2016+
neighboursJ[3] = 1;
2017+
neighboursJ[4] = 0;
2018+
neighboursJ[5] = -1;
2019+
neighboursJ[6] = -1;
2020+
neighboursJ[7] = -1;
19052021
}());
19062022

19072023
(function() {

0 commit comments

Comments
 (0)