hough transform - javascript - node.js [英] hough transform - javascript - node.js
问题描述
所以，我试图实现hough变换，这个版本是一维的（它的所有昏暗减少到1 dim优化）版本基于次要的属性。
包含的是我的代码，带有一个示例图像...输入和输出。
显然的问题是我做错了。我三倍检查我的逻辑和代码，它看起来还好我的参数。但是显然我缺少某些东西。
注意，红色像素应该是椭圆中心，而蓝色像素是要删除的边到符合数学方程的椭圆）。
同样，我对openCV / matlab / ocatve / etc不感兴趣。对他们）。
非常感谢！
var fs = require（fs），
Canvas = require （canvas），
Image = Canvas.Image;
var LEAST_REQUIRED_DISTANCE = 40，// LEAST需要2点之间的距离，让我们说最小椭圆较小
LEAST_REQUIRED_ELLIPSES = 6，//找到的椭圆数目
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）; //确保一切都是黑白的！
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 。
椭圆删除受到几个错误的影响
在您的代码中，通过将坐标重置为 { - 1，-1} ，可以找到椭圆形（原始纸张算法的第12步）。
您需要添加：
`if（arr_edges [x1y1] .x === -1）break;`
在x2y2块的末尾。
更重要的是，你的算法包括擦除每个点，距离中心的距离小于 b 。 b 应该是短轴半长度（根据原始算法）。但在你的代码中，变量 b 实际上是最新的（而不是最常见的）半长度， b（而不是更大，因为它是短轴）。换句话说，您可以清除距离最新计算轴以下的圆内的所有点。
您的示例图片实际上可以通过清除所有点具有比选定主轴低的距离的圆：
max_minor = arr_accum [max_votes.index] .d;
事实上，你没有重叠的椭圆，它们足够散开。请考虑使用更好的算法来重叠或更接近的椭圆。
算法混合主轴和次轴
对于每个第三像素（x，y），如果（x，y）和（x0，y）之间的距离小于或等于（x，y）
y0）大于要考虑的一对像素
所需的最小距离，则从（7）到（9）执行以下步骤。
< blockquote>
这显然是一个近似。如果这样做，您将最终考虑比短轴半长度更远的点，并且最终在长轴上（轴被交换）。您应该确保所考虑的点和测试的椭圆中心之间的距离小于当前考虑的长轴半长（条件应当 d <= a ）。这将有助于椭圆擦除算法的一部分。
此外，如果你还与一对像素的最小距离进行比较，对于图片中较小的椭圆太大了。
LEAST_REQUIRED_ELLIPSES太小 / h3>
此参数也未命名。它是一个椭圆应该被认为有效的最少投票数。每个投票对应于一个像素。因此，值6表示只有6 + 2像素构成椭圆。由于像素坐标是整数，并且您的图片中有多于一个椭圆，所以算法可能会检测到不是的椭圆，并最终清除边缘（尤其是与有缺陷的椭圆删除算法相结合时）。基于测试，值为100将找到您的图片的五个椭圆中的四个，而80将找到它们。较小的值将不会找到椭圆的正确中心。
示例图像不是黑色&白色
尽管有注释，但示例图像并不完全是黑白的。您应该转换它或应用一些阈值（例如，大于10的RGB值，而不是简单的不同形式0）。
最小更改的差异使其工作可用：
https://gist.github.com/pguyot/26149fec29ffa47f0cfb/revisions
最后，请注意 parseInt（x.toFixed（0））可以改写 Math.floor（x），你可能不想截断这样的所有浮点数，而是舍入它们，并在需要的地方继续：从图片中删除椭圆的算法将受益于非中心坐标的截断值。这个代码肯定可以进一步改进，例如它目前计算点之间的距离 x1y1 和 x2y2 两次。 p>
So, i'm trying to implement hough transform, this version is 1-dimensional (its for all dims reduced to 1 dim optimization) version based on the minor properties.
Enclosed is my code, with a sample image... input and output.
Obvious question is what am i doing wrong. I've tripled check my logic and code and it looks good also my parameters. But obviously i'm missing on something.
Notice that the red pixels are supposed to be ellipses centers , while the blue pixels are edges to be removed (belong to the ellipse that conform to the mathematical equations).
also, i'm not interested in openCV / matlab / ocatve / etc.. usage (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]
}
}
解决方案 It seems you try to implement the algorithm of Yonghong Xie; Qiang Ji (2002). A new efficient ellipse detection method 2. p. 957.
Ellipse removal suffers from several bugs
In your code, you perform the removal of found ellipse (step 12 of the original paper's algorithm) by resetting coordinates to {-1, -1}.
You need to add:
`if (arr_edges[x1y1].x === -1) break;`
at the end of the x2y2 block. Otherwise, the loop will consider -1, -1 as a white point.
More importantly, your algorithm consists in erasing every point which distance to the center is smaller than b. b supposedly is the minor axis half-length (per the original algorithm). But in your code, variable b actually is the latest (and not most frequent) half-length, and you erase points with a distance lower than b (instead of greater, since it's the minor axis). In other words, you clear all points inside a circle with a distance lower than latest computed axis.
Your sample image can actually be processed with a clearing of all points inside a circle with a distance lower than selected major axis with:
max_minor = arr_accum[max_votes.index].d;
Indeed, you don't have overlapping ellipses and they are spread enough. Please consider a better algorithm for overlapping or closer ellipses.
The algorithm mixes major and minor axes
Step 6 of the paper reads:
For each third pixel (x, y), if the distance between (x, y) and (x0,
y0) is greater than the required least distance for a pair of pixels
to be considered then carry out the following steps from (7) to (9).
This clearly is an approximation. If you do so, you will end up considering points further than the minor axis half length, and eventually on the major axis (with axes swapped). You should make sure the distance between the considered point and the tested ellipse center is smaller than currently considered major axis half-length (condition should be d <= a). This will help with the ellipse erasing part of the algorithm.
Also, if you also compare with the least distance for a pair of pixels, as per the original paper, 40 is too large for the smaller ellipse in your picture. The comment in your code is wrong, it should be at maximum half the smallest ellipse minor axis half-length.
LEAST_REQUIRED_ELLIPSES is too small
This parameter is also misnamed. It is the minimum number of votes an ellipse should get to be considered valid. Each vote corresponds to a pixel. So a value of 6 means that only 6+2 pixels make an ellipse. Since pixels coordinates are integers and you have more than 1 ellipse in your picture, the algorithm might detect ellipses that are not, and eventually clear edges (especially when combined with the buggy ellipse erasing algorithm). Based on tests, a value of 100 will find four of the five ellipses of your picture, while 80 will find them all. Smaller values will not find the proper centers of the ellipses.
Sample image is not black & white
Despite the comment, sample image is not exactly black and white. You should convert it or apply some threshold (e.g. RGB values greater than 10 instead of simply different form 0).
Diff of minimum changes to make it work is available here:
https://gist.github.com/pguyot/26149fec29ffa47f0cfb/revisions
Finally, please note that parseInt(x.toFixed(0)) could be rewritten Math.floor(x), and you probably want to not truncate all floats like this, but rather round them, and proceed where needed: the algorithm to erase the ellipse from the picture would benefit from non truncated values for the center coordinates. This code definitely could be improved further, for example it currently computes the distance between points x1y1 and x2y2 twice.
这篇关于hough transform - javascript - node.js的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
