霍夫变换 - javascript - node.js [英] hough transform - javascript - node.js

问题描述

所以，我正在尝试实现霍夫变换，这个版本是基于次要属性的一维版本(它的所有暗淡减少到 1 暗淡优化)版本.随附的是我的代码，带有示例图像...输入和输出.

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.

注意，红色像素应该是椭圆中心，而蓝色像素是要去除的边缘(属于符合数学方程的椭圆).

另外，我对 openCV/matlab/ocatve/etc.. 的使用不感兴趣(没有反对他们).非常感谢！

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. p.957.

在您的代码中，您通过将坐标重置为 {-1, -1} 来删除找到的椭圆(原始论文算法的第 12 步).

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 应该是短轴半长(根据原始算法).但是在您的代码中，变量 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;

确实，您没有重叠的椭圆，而且它们已经足够分散了.请考虑使用更好的算法来处理重叠或更接近的椭圆.

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

论文的第 6 步内容如下:

Step 6 of the paper reads:

对于每第三个像素(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 <= a).这将有助于算法的椭圆擦除部分.

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 太大了.您的代码中的注释是错误的，它最多应该是最小椭圆短轴的一半半长.

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.

尽管有评论，但示例图像并不完全是黑白的.您应该对其进行转换或应用一些阈值(例如大于 10 的 RGB 值，而不是简单地与 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).

可在此处获得使其工作的最小更改差异: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)，你可能不想截断所有浮点数像这样，而是将它们四舍五入，并在需要的地方继续:从图片中删除椭圆的算法将受益于中心坐标的非截断值.这段代码肯定可以进一步改进，例如它当前计算点 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.

这篇关于霍夫变换 - javascript - node.js的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！