Hough变换 - JavaScript的 - 的node.js [英] hough transform - javascript - node.js

问题描述

所以，我想实现Hough变换，这个版本是一维（其减少到1昏暗优化所有变暗）版本的基础上轻微的性能。 附上我的code，具有样本图像...输入和输出。

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.

很明显的问题是我做错了。我已经翻了三倍检查我的逻辑和code，它看起来也不错我的参数。但很明显我缺少的东西。

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.

请注意，红色的像素应该是椭圆的中心，而蓝色像素的边缘被删除（属于符合数学方程式的​​椭圆）。

另外，我也没兴趣的OpenCV / MATLAB / ocatve /等的使用（没有对他们）。 非常感谢你！

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]
    }
}

推荐答案

看来你尝试实施的永红谢;季强（2002）。一种新的高效的椭圆检测方法2页。 957 。

在你的code，你通过重置坐标来执行删除操作发现椭圆（原皮的算法的步骤12） { - 1，-1}

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

您需要添加：

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

在X2Y2块的末尾。否则，循环将考虑-1，-1作为一个白点。

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

更重要的是，你的算法是由在擦除每一点它距离市中心比小b 。 B 据说是短轴半长（占原算法）。但是，在你的code，变量 B 其实就是最新的（而不是最常见），半长的，你删除一个点距离低于B（而不是更大，因为它是短轴）。换句话说，你有清晰的距离比最新的计算轴低。一个圆圈中所有点

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;

事实上，你没有重叠的椭圆，他们有s $ P $垫不够。请考虑重叠或接近椭圆一个更好的算法。

Indeed, you don't have overlapping ellipses and they are spread enough. Please consider a better algorithm for overlapping or closer ellipses.

纸张的第6步读取：

有关每个第三像素（x，y）时，如果（X，Y）和（X0之间的距离，   Y0）大于对于一对像素的至少要求的距离   要考虑然后执行从下述工序（7）〜（9）。

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).

这显然是一个近似值。如果你这样做，你最终会考虑百分点，比短轴半长进一步，并最终在长轴（与轴交换）。你应该确保的考虑点与被测椭圆中心之间的距离比当前考虑的长轴的半长度小（条件应 D＆所述; =一）。这将有助于与算法的椭圆擦除部分

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.

另外，如果你也与最小距离的像素对，按原来的文件相比，40是太大，在照片中更小的椭圆。在code的评论是错误的，应该是在最大半最小的​​椭圆短轴的半长的。

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.

此参数也名不副实。它是票椭圆应该被认为是有效的最小数目。每票对应于一个像素。所以值6意味着只有6 + 2个像素作一个椭圆。由于像素坐标是整数，你有超过1椭圆您的图片，该算法可以检测出椭圆都没有，并最终明确的边缘（尤其是在与车椭圆擦除算法相结合）。根据测试，值100会发现四个照片中的五个椭圆的，而80将它们全部找到。较小的值将找不到椭圆的正确中心。

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.

尽管注释，样本图像不完全是黑色和白色。你应该将它转换或申请某个阈值（如RGB值大于10，而不是简单地不同的形式0）。

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，使其工作可以在这里找到： https://gist.github.com/pguyot/26149fec29ffa47f0cfb/revisions

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

最后，请注意， parseInt函数（x.toFixed（0））可以改写 Math.floor（x），你可能想不会截断这样所有的花车，而是他们周围，并继续在需要的地方：算法删除从图片中椭圆将受益于非截断值的中心坐标。这code绝对可以进一步改进，例如它目前计算点之间的距离 X1Y1 和 X2Y2 两次

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变换 - JavaScript的 - 的node.js的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！