Skip to content

Commit bbe8fd1

Browse files
eduardolundgreneduardolundgren
committed
Source formatting fast algorithm
1 parent c4de87e commit bbe8fd1

7 files changed

Lines changed: 143 additions & 74 deletions

File tree

‎examples/assets/book.JPG‎

-53.4 KB
Binary file not shown.

‎examples/assets/keypoints_book_1.png‎

-159 KB
Binary file not shown.

‎examples/assets/keypoints_book_2.png‎

-76.3 KB
Binary file not shown.

‎examples/fast.html‎

Lines changed: 10 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -11,44 +11,20 @@
1111
<body>
1212
<canvas id="canvas"></canvas>
1313
<script>
14-
var CornerTracker = function() {
15-
CornerTracker.base(this, 'constructor');
16-
};
17-
18-
tracking.inherits(CornerTracker, tracking.Tracker);
19-
20-
CornerTracker.prototype.track = function(pixels, width, height) {
21-
var grayScale = new Uint8ClampedArray(width * height),
22-
position = 0,
23-
w = 0;
24-
25-
for (var i = 0; i < height; i++) {
26-
for (var j = 0; j < width; j++) {
27-
grayScale[position++] = pixels[w]*0.299 + pixels[w + 1]*0.587 + pixels[w + 2]*0.114;
28-
w += 4;
29-
}
30-
}
31-
32-
var timeNow = new Date().getTime();
33-
var corners = tracking.Fast.findCorners(grayScale, width, height);
34-
console.log('time:', new Date().getTime() - timeNow);
35-
36-
this.onFound(corners);
37-
};
38-
14+
var width = 320;
15+
var height = 240;
3916
var canvas = tracking.one('#canvas');
4017
var context = canvas.getContext('2d');
4118

42-
tracking.Canvas.loadImage(canvas, 'assets/book1.png', 0, 0, 320, 240, function() {
43-
var tracker = new CornerTracker();
44-
tracker.onFound = function(corners) {
45-
for (var i = 0; i < corners.length; i += 2) {
46-
context.fillStyle = "rgb(255,0,0)";
47-
context.fillRect(corners[i], corners[i+1], 1, 1);
48-
}
49-
};
19+
tracking.Canvas.loadImage(canvas, 'assets/book1.png', 0, 0, width, height, function() {
20+
var imageData = context.getImageData(0, 0, width, height);
21+
var gray = tracking.Image.calculateLumaGrayscale(imageData.data, width, height);
22+
var corners = tracking.Fast.findCorners(gray, width, height);
5023

51-
tracking.track('#canvas', tracker);
24+
for (var i = 0; i < corners.length; i += 2) {
25+
context.fillStyle = '#f00';
26+
context.fillRect(corners[i], corners[i + 1], 1, 1);
27+
}
5228
});
5329
</script>
5430
</body>

‎gulpfile.js‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@ gulp.task('build', function() {
2626
'src/Canvas.js',
2727
'src/EPnP.js',
2828
'src/Fast.js',
29+
'src/Image.js',
2930
'src/Math.js',
3031
'src/Matrix.js',
3132
'src/Tracker.js',

‎src/Fast.js‎

Lines changed: 97 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -23,45 +23,82 @@
2323
*/
2424
tracking.Fast = {};
2525

26+
/**
27+
* Holds the threshold to determine whether the tested pixel is brighter or
28+
* darker than the corner candidate p.
29+
* @type {number}
30+
* @default 20
31+
* @static
32+
*/
2633
tracking.Fast.FAST_THRESHOLD = 20;
2734

35+
/**
36+
* Caches coordinates values of the circle surounding the pixel candidate p.
37+
* @type {Object.<number, Int32Array>}
38+
* @private
39+
* @static
40+
*/
2841
tracking.Fast.circles_ = {};
2942

30-
tracking.Fast.findCorners = function(grayScale, width, height) {
31-
var baseCircle = this.getCircle_(width),
32-
circle = new Int32Array(16),
33-
corners = [],
34-
i,
35-
j,
36-
k,
37-
p,
38-
w = 0;
39-
40-
for (i = 3; i < height - 3; i++) {
41-
for (j = 3; j < width - 3; j++) {
42-
w = i*width + j;
43-
p = grayScale[w];
44-
45-
for (k = 0; k < 16; k++) {
46-
circle[k] = grayScale[baseCircle[k] + w];
43+
/**
44+
* Finds corners coordinates on the graysacaled image.
45+
* @param {array} The grayscale pixels in a linear [p1,p2,...] array.
46+
* @param {number} width The image width.
47+
* @param {number} height The image height.
48+
* @return {array} Array containing the coordinates of all found corners,
49+
* e.g. [x0,y0,x1,y1,...], where P(x0,y0) represents a corner coordinate.
50+
*/
51+
tracking.Fast.findCorners = function(pixels, width, height) {
52+
var circleOffsets = this.getCircleOffsets_(width),
53+
circlePixels = new Int32Array(16),
54+
corners = [];
55+
56+
// When looping through the image pixels, skips the first three lines from
57+
// the image boundaries to constrain the surrounding circle inside the image
58+
// area.
59+
for (var i = 3; i < height - 3; i++) {
60+
for (var j = 3; j < width - 3; j++) {
61+
var w = i * width + j;
62+
var p = pixels[w];
63+
64+
// Loops the circle offsets to read the pixel value for the sixteen
65+
// surrounding pixels.
66+
for (var k = 0; k < 16; k++) {
67+
circlePixels[k] = pixels[w + circleOffsets[k]];
4768
}
4869

49-
if (this.isCorner(circle, p, this.FAST_THRESHOLD)) {
70+
if (this.isCorner(p, circlePixels, this.FAST_THRESHOLD)) {
71+
// The pixel p is classified as a corner, as optimization increment j
72+
// by the circle radius 3 to skip the neighbor pixels inside the
73+
// surrounding circle. This can be removed without compromising the
74+
// result.
5075
corners.push(j, i);
51-
j+=3;
76+
j += 3;
5277
}
5378
}
5479
}
5580

5681
return corners;
5782
};
5883

59-
tracking.Fast.isCorner = function(circle, p, threshold) {
84+
/**
85+
* Checks if the circle pixel is brigther than the candidate pixel p by
86+
* a threshold.
87+
* @param {number} circlePixel The circle pixel value.
88+
* @param {number} p The value of the candidate pixel p.
89+
* @param {number} threshold
90+
* @return {Boolean}
91+
*/
92+
tracking.Fast.isBrighter = function(circlePixel, p, threshold) {
93+
return circlePixel - p > threshold;
94+
};
95+
96+
tracking.Fast.isCorner = function(p, circlePixels, threshold) {
6097
var brighter,
61-
circlePoint,
98+
circlePixel,
6299
darker;
63100

64-
if (this.isTriviallyExcluded(circle, p, threshold)) {
101+
if (this.isTriviallyExcluded(circlePixels, p, threshold)) {
65102
return false;
66103
}
67104

@@ -70,13 +107,13 @@
70107
brighter = true;
71108

72109
for (var y = 0; y < 9; y++) {
73-
circlePoint = circle[(x + y) & 15];
110+
circlePixel = circlePixels[(x + y) & 15];
74111

75-
if (!this.isBrighter(circlePoint, p, threshold)) {
112+
if (!this.isBrighter(p, circlePixel, threshold)) {
76113
brighter = false;
77114
}
78115

79-
if (!this.isDarker(circlePoint, p, threshold)) {
116+
if (!this.isDarker(p, circlePixel, threshold)) {
80117
darker = false;
81118
}
82119
}
@@ -85,12 +122,35 @@
85122
return brighter || darker;
86123
};
87124

88-
tracking.Fast.isTriviallyExcluded = function(circle, p, threshold) {
125+
/**
126+
* Checks if the circle pixel is darker than the candidate pixel p by
127+
* a threshold.
128+
* @param {number} circlePixel The circle pixel value.
129+
* @param {number} p The value of the candidate pixel p.
130+
* @param {number} threshold
131+
* @return {Boolean}
132+
*/
133+
tracking.Fast.isDarker = function(circlePixel, p, threshold) {
134+
return p - circlePixel > threshold;
135+
};
136+
137+
/**
138+
* Fast check to test if the candidate pixel is a trivially excluded value.
139+
* In order to be a corner, the candidate pixel value should be darker or
140+
* brigther than 9-12 surrouding pixels, when at least three of the top,
141+
* bottom, left and right pixels are brither or darker it can be
142+
* automatically excluded improving the performance.
143+
* @param {number} circlePixel The circle pixel value.
144+
* @param {number} p The value of the candidate pixel p.
145+
* @param {number} threshold
146+
* @return {Boolean}
147+
*/
148+
tracking.Fast.isTriviallyExcluded = function(circlePixels, p, threshold) {
89149
var count = 0;
90-
var circleTop = circle[0];
91-
var circleRight = circle[4];
92-
var circleBottom = circle[8];
93-
var circleLeft = circle[12];
150+
var circleBottom = circlePixels[8];
151+
var circleLeft = circlePixels[12];
152+
var circleRight = circlePixels[4];
153+
var circleTop = circlePixels[0];
94154

95155
if (this.isBrighter(circleTop, p, threshold)) {
96156
count++;
@@ -119,7 +179,6 @@
119179
if (this.isDarker(circleLeft, p, threshold)) {
120180
count++;
121181
}
122-
123182
if (count < 3) {
124183
return true;
125184
}
@@ -128,15 +187,13 @@
128187
return false;
129188
};
130189

131-
tracking.Fast.isBrighter = function(circlePoint, p, threshold) {
132-
return circlePoint > p + threshold;
133-
};
134-
135-
tracking.Fast.isDarker = function(circlePoint, p, threshold) {
136-
return circlePoint < p - threshold;
137-
};
138-
139-
tracking.Fast.getCircle_ = function(width) {
190+
/**
191+
* Gets the sixteen offset values of the circle surrounding pixel.
192+
* @param {number} width The image width.
193+
* @return {array} Array with the sixteen offset values of the circle
194+
* surrounding pixel.
195+
*/
196+
tracking.Fast.getCircleOffsets_ = function(width) {
140197
if (this.circles_[width]) {
141198
return this.circles_[width];
142199
}

‎src/Image.js‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
(function() {
2+
/**
3+
* Image utility.
4+
* @static
5+
* @constructor
6+
*/
7+
tracking.Image = {};
8+
9+
/**
10+
* Converts a color from a colorspace based on an RGB color model to a
11+
* grayscale representation of its luminance. The coefficients represent the
12+
* measured intensity perception of typical trichromat humans, in
13+
* particular, human vision is most sensitive to green and least sensitive
14+
* to blue.
15+
* @param {Uint8ClampedArray} pixels The pixels in a linear [r,g,b,a,...]
16+
* array.
17+
* @param {number} width The image width.
18+
* @param {number} height The image height.
19+
* @return {Uint8ClampedArray} The grayscale pixels in a linear [p1,p2,...]
20+
* array, where `pn = rn*0.299 + gn*0.587 + bn*0.114`.
21+
* @static
22+
*/
23+
tracking.Image.calculateLumaGrayscale = function(pixels, width, height) {
24+
var gray = new Uint8ClampedArray(width * height);
25+
var p = 0;
26+
var w = 0;
27+
for (var i = 0; i < height; i++) {
28+
for (var j = 0; j < width; j++) {
29+
gray[p++] = pixels[w]*0.299 + pixels[w + 1]*0.587 + pixels[w + 2]*0.114;
30+
w += 4;
31+
}
32+
}
33+
return gray;
34+
};
35+
}());

0 commit comments

Comments
 (0)