Hough transformer – javascript – node.js

Donc, j'essaie de mettre en œuvre hough transform, cette version est 1-dimensionnelle (c'est pour toute dims réduite à 1 dim optimisation) version basée sur les propriétés mineures. Le code ci-joint contient un exemple d'image … entrée et sortie.

Une question évidente est ce que je fais mal. J'ai triplé, vérifie ma logique et mon code et cela semble aussi bien mes paramètres. Mais évidemment, je manque à quelque chose.

Notez que les pixels rouges sont censés être des centres d'ellipses, tandis que les pixels bleus sont des arêtes à supprimer (appartiennent à l'ellipse conforme aux équations mathématiques).

De plus, je ne suis pas intéressé par l'utilisation d'openCV / matlab / ocatve / etc. (rien contre eux). Merci beaucoup!

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

Image originaleHough transformer la sortie

Il semble que vous essayez de mettre en œuvre l'algorithme de Yonghong Xie; Qiang Ji (2002). Une nouvelle méthode efficace de détection d'ellipse 2. p. 957 .

L'élimination de Ellipse souffre de plusieurs bugs

Dans votre code, vous effectuez la suppression de l'ellipse trouvée (étape 12 de l'algorithme du papier d'origine) en réinitialisant les coordonnées sur {-1, -1} .

Vous devez ajouter:

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

À la fin du bloc x2y2. Sinon, la boucle considérera -1, -1 comme un point blanc.

Plus important encore, votre algorithme consiste à effacer tous les points dont la distance au centre est inférieure à b . b est censé être la demi-longueur d'axe mineur (selon l'algorithme d'origine). Mais dans votre code, la variable b est en fait la dernière demi-longueur (et pas la plus fréquente), et vous effacez les points avec une distance inférieure à b (au lieu de plus grande, car c'est l'axe mineur). En d'autres termes, vous effacez tous les points dans un cercle avec une distance inférieure au dernier axe calculé.

Votre image d'échantillon peut effectivement être traitée avec un dégagement de tous les points dans un cercle avec une distance inférieure à l'axe majeur sélectionné avec:

 max_minor = arr_accum[max_votes.index].d; 

En effet, vous n'avez pas de ellipses superposées et elles sont assez répandues. Veuillez considérer un meilleur algorithme pour les superpositions superposées ou plus étroites.

L'algorithme mélange des axes majeurs et mineurs

L'étape 6 du document se lit comme suit:

Pour chaque troisième pixel (x, y), si la distance entre (x, y) et (x0, y0) est supérieure à la distance minimale requise pour une paire de pixels à considérer, effectuez les étapes suivantes à partir de (7) À (9).

Ceci est clairement une approximation. Si vous le faites, vous finirez par considérer des points plus loin que la demi-longueur de l'axe mineur, et éventuellement sur l'axe principal (avec les axes échangés). Vous devez vous assurer que la distance entre le point considéré et le centre d'ellipse testé est plus petite que l'on considère actuellement la demi-longueur de l'axe principal (la condition doit être d <= a ). Cela aidera l'élimination de l'élimination d'une partie de l'algorithme.

En outre, si vous comparez aussi avec la moindre distance pour une paire de pixels, selon le papier d'origine, 40 est trop large pour l'ellipse plus petite dans votre image. Le commentaire dans votre code est erroné, il devrait être à la moitié maximum de la plus petite longueur demi-longueur de l' axe secondaire de l'ellipse.

LEAST_REQUIRED_ELLIPSES est trop petit

Ce paramètre est également méconnu. C'est le nombre minimum de votes qu'une ellipse devrait considérer comme valide. Chaque vote correspond à un pixel. Donc, une valeur de 6 signifie que seulement 6 + 2 pixels font une ellipse. Puisque les coordonnées des pixels sont des nombres entiers et que vous avez plus d'une ellipse dans votre image, l'algorithme pourrait détecter des ellipses qui ne sont pas, et éventuellement des bords clairs (en particulier lorsqu'ils sont combinés avec l'algorithme d'effacement de l'élimination buggy). Sur la base des tests, une valeur de 100 trouvera quatre des cinq ellipses de votre image, tandis que 80 les trouvera tous. Les valeurs plus petites ne trouvent pas les centres appropriés des ellipses.

L'image d'échantillon n'est pas en noir et blanc

Malgré le commentaire, l'image échantillon n'est pas exactement en noir et blanc. Vous devez le convertir ou appliquer un seuil (par exemple, des valeurs RGB supérieures à 10 au lieu de la forme simplement différente 0).

La diffusion des modifications minimales pour le faire fonctionner est disponible ici: https://gist.github.com/pguyot/26149fec29ffa47f0cfb/revisions

Enfin, notez que parseInt(x.toFixed(0)) pourrait être réécrit Math.floor(x) , et vous ne voulez probablement pas tronquer tous les flotteurs comme celui-ci, mais plutôt les Math.floor(x) , et procéder là où nécessaire: l'algorithme à effacer L'ellipse de l'image bénéficiera des valeurs non tronquées pour les coordonnées du centre. Ce code pourrait certainement encore être amélioré, par exemple, il calcule actuellement la distance entre les points x1y1 et x2y2 deux fois.