title: hough transform - javascript - node.js
body: <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. </p>
  
  <p>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.</p>
  
  <p><strong>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).</strong></p>
  
  <p>also, i'm not interested in openCV / matlab / ocatve / etc.. usage (nothing against them). 
  Thank you very much!</p>
  
  <pre><code>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 &lt; arr_edges_len ; x1y1++){
  
    if (arr_edges[x1y1].x === -1) { continue; }
  
    for(x2y2 = 0 ; x2y2 &lt; arr_edges_len; x2y2++){
  
      if ((arr_edges[x2y2].x === -1) ||
          (arr_edges[x2y2].x === arr_edges[x1y1].x &amp;&amp; arr_edges[x2y2].y === arr_edges[x1y1].y)) { continue; }
  
      if (distance(arr_edges[x1y1],arr_edges[x2y2]) &gt; 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 &lt; arr_edges_len; xy++){
  
          if ((arr_edges[xy].x === -1) || 
              (arr_edges[xy].x === arr_edges[x2y2].x &amp;&amp; arr_edges[xy].y === arr_edges[x2y2].y) ||
              (arr_edges[xy].x === arr_edges[x1y1].x &amp;&amp; arr_edges[xy].y === arr_edges[x1y1].y)) { continue; }
  
          d = distance({x: x0, y: y0},arr_edges[xy]);
  
          if (d &gt; 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 &gt; 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 &amp;&amp;
            (max_votes.max_votes &gt; 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 &lt; 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 &lt;= 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 &gt; max_votes){
        max_votes     = accum_in[i].accum;
        max_votes_idx = i;
      } // if
    }
  
  
    if (max_votes &gt; 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 &lt; width; x++){
      for(y = 0; y &lt; height; y++){
  
        pixel = getPixel(img_data, x,y);
  
  
        if (pixel.r !== 0 &amp;&amp; 
            pixel.g !== 0 &amp;&amp;
            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]
      }
  }
  </code></pre>
  
  <p><img src="https://i.stack.imgur.com/tK2br.jpg" alt="Original image">
  <img src="https://i.stack.imgur.com/e3K0i.png" alt="Hough transform output"></p>