Last active
April 18, 2016 15:32
-
-
Save pguyot/26149fec29ffa47f0cfb to your computer and use it in GitHub Desktop.
Hough transform
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var fs = require("fs"), | |
Canvas = require("canvas"), | |
Image = Canvas.Image; | |
var LEAST_REQUIRED_DISTANCE = 20, // LEAST required distance between 2 points , lets say smallest ellipse minor | |
LEAST_REQUIRED_ELLIPSES = 80, // number of found ellipse | |
arr_accum = [], | |
arr_edges = [], | |
edges_canvas, | |
xy, | |
x1y1, | |
x2y2, | |
x0, | |
y0, | |
a, | |
alpha, | |
d, | |
b, | |
max_votes, | |
cos_tau, | |
sin_tau_sqr, | |
f, | |
new_x0, | |
new_y0, | |
any_minor_dist, | |
max_minor, | |
i, | |
found_minor_in_accum, | |
arr_edges_len, | |
hough_file = 'sample_me2.jpg', | |
edges_canvas = drawImgToCanvasSync(hough_file); // make sure everything is black and white! | |
arr_edges = getEdgesArr(edges_canvas); | |
arr_edges_len = arr_edges.length; | |
var hough_canvas_img_data = edges_canvas.getContext('2d').getImageData(0, 0, edges_canvas.width,edges_canvas.height); | |
for(x1y1 = 0; x1y1 < arr_edges_len ; x1y1++){ | |
if (arr_edges[x1y1].x === -1) { continue; } | |
for(x2y2 = 0 ; x2y2 < arr_edges_len; x2y2++){ | |
if ((arr_edges[x2y2].x === -1) || | |
(arr_edges[x2y2].x === arr_edges[x1y1].x && arr_edges[x2y2].y === arr_edges[x1y1].y)) { continue; } | |
if (distance(arr_edges[x1y1],arr_edges[x2y2]) > LEAST_REQUIRED_DISTANCE){ | |
x0 = (arr_edges[x1y1].x + arr_edges[x2y2].x) / 2; | |
y0 = (arr_edges[x1y1].y + arr_edges[x2y2].y) / 2; | |
a = Math.sqrt((arr_edges[x1y1].x - arr_edges[x2y2].x) * (arr_edges[x1y1].x - arr_edges[x2y2].x) + (arr_edges[x1y1].y - arr_edges[x2y2].y) * (arr_edges[x1y1].y - arr_edges[x2y2].y)) / 2; | |
alpha = Math.atan((arr_edges[x2y2].y - arr_edges[x1y1].y) / (arr_edges[x2y2].x - arr_edges[x1y1].x)); | |
for(xy = 0 ; xy < arr_edges_len; xy++){ | |
if ((arr_edges[xy].x === -1) || | |
(arr_edges[xy].x === arr_edges[x2y2].x && arr_edges[xy].y === arr_edges[x2y2].y) || | |
(arr_edges[xy].x === arr_edges[x1y1].x && arr_edges[xy].y === arr_edges[x1y1].y)) { continue; } | |
d = distance({x: x0, y: y0},arr_edges[xy]); | |
if (d > LEAST_REQUIRED_DISTANCE && d <= a){ | |
f = distance(arr_edges[xy],arr_edges[x2y2]); // focus | |
cos_tau = (a * a + d * d - f * f) / (2 * a * d); | |
sin_tau_sqr = (1 - cos_tau * cos_tau);//Math.sqrt(1 - cos_tau * cos_tau); // getting sin out of cos | |
b = (a * a * d * d * sin_tau_sqr ) / (a * a - d * d * cos_tau * cos_tau); | |
b = Math.sqrt(b); | |
b = parseInt(b.toFixed(0)); | |
d = parseInt(d.toFixed(0)); | |
if (b > 0){ | |
found_minor_in_accum = arr_accum.hasOwnProperty(b); | |
if (!found_minor_in_accum){ | |
arr_accum[b] = {f: f, cos_tau: cos_tau, sin_tau_sqr: sin_tau_sqr, b: b, d: d, xy: xy, xy_point: JSON.stringify(arr_edges[xy]), x0: x0, y0: y0, accum: 0}; | |
} | |
else{ | |
arr_accum[b].accum++; | |
} | |
}// b | |
}// if2 - LEAST_REQUIRED_DISTANCE | |
}// for xy | |
max_votes = getMaxMinor(arr_accum); | |
// ONE ellipse has been detected | |
if (max_votes != null && | |
(max_votes.max_votes > LEAST_REQUIRED_ELLIPSES)){ | |
// output ellipse details | |
new_x0 = parseInt(arr_accum[max_votes.index].x0.toFixed(0)), | |
new_y0 = parseInt(arr_accum[max_votes.index].y0.toFixed(0)); | |
setPixel(hough_canvas_img_data,new_x0,new_y0,255,0,0,255); // Red centers | |
// remove the pixels on the detected ellipse from edge pixel array | |
for (i=0; i < arr_edges.length; i++){ | |
any_minor_dist = distance({x:new_x0, y: new_y0}, arr_edges[i]); | |
any_minor_dist = parseInt(any_minor_dist.toFixed(0)); | |
major_half_len = arr_accum[max_votes.index].d; // major distance | |
// coloring in blue the edges we don't need | |
if (any_minor_dist <= major_half_len){ | |
setPixel(hough_canvas_img_data,arr_edges[i].x,arr_edges[i].y,0,0,255,255); | |
arr_edges[i] = {x: -1, y: -1}; | |
}// if | |
}// for | |
}// if - LEAST_REQUIRED_ELLIPSES | |
// clear accumulated array | |
arr_accum = []; | |
}// if1 - LEAST_REQUIRED_DISTANCE | |
if (arr_edges[x1y1].x === -1) break; | |
}// for x2y2 | |
}// for xy | |
edges_canvas.getContext('2d').putImageData(hough_canvas_img_data, 0, 0); | |
writeCanvasToFile(edges_canvas, __dirname + '/hough.jpg', function() { | |
}); | |
function getMaxMinor(accum_in){ | |
var max_votes = -1, | |
max_votes_idx, | |
i, | |
accum_len = accum_in.length; | |
for(i in accum_in){ | |
if (accum_in[i].accum > max_votes){ | |
max_votes = accum_in[i].accum; | |
max_votes_idx = i; | |
} // if | |
} | |
if (max_votes > 0){ | |
return {max_votes: max_votes, index: max_votes_idx}; | |
} | |
return null; | |
} | |
function distance(point_a,point_b){ | |
return Math.sqrt((point_a.x - point_b.x) * (point_a.x - point_b.x) + (point_a.y - point_b.y) * (point_a.y - point_b.y)); | |
} | |
function getEdgesArr(canvas_in){ | |
var x, | |
y, | |
width = canvas_in.width, | |
height = canvas_in.height, | |
pixel, | |
edges = [], | |
ctx = canvas_in.getContext('2d'), | |
img_data = ctx.getImageData(0, 0, width, height); | |
for(x = 0; x < width; x++){ | |
for(y = 0; y < height; y++){ | |
pixel = getPixel(img_data, x,y); | |
if (pixel.r > 10 && | |
pixel.g > 10 && | |
pixel.b > 10 ){ | |
edges.push({x: x, y: y}); | |
} | |
} // for | |
}// for | |
return edges | |
} // getEdgesArr | |
function drawImgToCanvasSync(file) { | |
var data = fs.readFileSync(file) | |
var canvas = dataToCanvas(data); | |
return canvas; | |
} | |
function dataToCanvas(imagedata) { | |
img = new Canvas.Image(); | |
img.src = new Buffer(imagedata, 'binary'); | |
var canvas = new Canvas(img.width, img.height); | |
var ctx = canvas.getContext('2d'); | |
ctx.patternQuality = "best"; | |
ctx.drawImage(img, 0, 0, img.width, img.height, | |
0, 0, img.width, img.height); | |
return canvas; | |
} | |
function writeCanvasToFile(canvas, file, callback) { | |
var out = fs.createWriteStream(file) | |
var stream = canvas.createPNGStream(); | |
stream.on('data', function(chunk) { | |
out.write(chunk); | |
}); | |
stream.on('end', function() { | |
callback(); | |
}); | |
} | |
function setPixel(imageData, x, y, r, g, b, a) { | |
index = (x + y * imageData.width) * 4; | |
imageData.data[index+0] = r; | |
imageData.data[index+1] = g; | |
imageData.data[index+2] = b; | |
imageData.data[index+3] = a; | |
} | |
function getPixel(imageData, x, y) { | |
index = (x + y * imageData.width) * 4; | |
return { | |
r: imageData.data[index+0], | |
g: imageData.data[index+1], | |
b: imageData.data[index+2], | |
a: imageData.data[index+3] | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment