Hough transform - javascript - node.js

Question

So, I'm trying to implement the hough transformation, this version is a one-dimensional (its for all reduced to 1-dimensional optimization) version based on minor properties. Enclosed is my code, with a sample image ... input and output.

The obvious question is what am I doing wrong. I tripled checking my logic and code, and it looks good and my parameters. But obviously, I missed something.

Note that the red pixels must be the centers of the ellipses, and the blue pixels are the edges that need to be removed (refer to the ellipse that corresponds to the mathematical equations).

also, I'm not interested in using openCV / matlab / ocatve / etc .. (nothing against them). Thank you very much!

var fs = require("fs"), Canvas = require("canvas"), Image = Canvas.Image; var LEAST_REQUIRED_DISTANCE = 40, // LEAST required distance between 2 points , lets say smallest ellipse minor LEAST_REQUIRED_ELLIPSES = 6, // 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){ 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)); max_minor = b;//Math.max(b,arr_accum[max_votes.index].d); // between the max and the min // coloring in blue the edges we don't need if (any_minor_dist <= max_minor){ 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 }// 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 !== 0 && pixel.g !== 0 && pixel.b !== 0 ){ 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] } } 

Answer 1

It seems you are trying to implement the Yonghong Xie algorithm ; Qiang Ji (2002). A new effective method for detecting an ellipse 2. sec. 957 .

Deleting an ellipse has several errors

In the code, you delete the found ellipse (step 12 of the original paper algorithm) by resetting the coordinates to {-1, -1} .

You need to add:

 `if (arr_edges[x1y1].x === -1) break;` 

at the end of the x2y2 block. Otherwise, the cycle will consider -1, -1 as a white point.

More importantly, your algorithm is to erase each point whose center distance is less than b . b , presumably, is a small axis of length (according to the original algorithm). But in your code, the variable b is actually the last (and not the most frequent) half of the length, and you delete points with a distance below b (instead of the larger one, since this is a minor axis). In other words, you clear all points inside the circle with a distance below the last calculated axis.

Your sample image can actually be processed by clearing all points inside the circle with a distance below the selected main axis using:

 max_minor = arr_accum[max_votes.index].d; 

Indeed, you do not have overlapping ellipses, and they are common enough. Please consider a better algorithm for overlapping or closer ellipses.

The algorithm mixes major and minor axes

Step 6 of the article reads:

For every third pixel (x, y), if the distance between (x, y) and (x0, y0) is greater than the required smallest distance for a pair of pixels to consider, then perform the following steps from (7) to (9).

This is obviously an approximation. If you do this, you will eventually consider points that are more than half the length of the minor axis, and, ultimately, on the main axis (with axes replaced). You must make sure that the distance between the point in question and the tested center of the ellipse is less than what is currently considered a large half axis (condition should be d <= a ). This will help with the ellipse erasing part of the algorithm.

Also, if you also compare with the smallest distance for a pair of pixels, according to the original paper, 40 is too large for a smaller ellipse in your picture. The comment in the code is incorrect, it should be no more than half the smallest half axis of the minor axis of the ellipse.

LEAST_REQUIRED_ELLIPSES is too small

This parameter is also incorrectly specified. This is the minimum number of votes that an ellipse must be considered valid. Each vote corresponds to a pixel. Thus, a value of 6 means that only 6 + 2 pixels form an ellipse. Since the coordinates of the pixels are integers, and you have more than 1 ellipse in your image, the algorithm can detect ellipses that are not, but ultimately, sharp edges (especially in combination with the elliptical error erasure algorithm). Based on the tests, a value of 100 will find four out of five ellipses of your image, and 80 will find them all. Smaller values ​​will not find the correct centers of the ellipses.

Sample image is not black and white

Despite the comment, the image of the sample is not quite black and white. You must convert it or apply some threshold (for example, RGB values ​​are greater than 10 instead of a simple 0 form).

Changing the minimum changes to make it work is available here: https://gist.github.com/pguyot/26149fec29ffa47f0cfb/revisions

Finally, note that parseInt(x.toFixed(0)) can be rewritten with Math.floor(x) , and you probably don't want to trim all such floats like this, but rather round them and continue where necessary : Algorithm for removing an ellipse from an image to capitalize on not truncated values ​​for central coordinates. This code can definitely be further improved, for example, it currently calculates the distance between points x1y1 and x2y2 twice.