le pixel noir le plus proche d'un point dans une image

Bonjour,

Il est vrai que le problème est difficile à titrer !
Pour résumer : il s'agit d'une image binaire et d'un couple entier (x,y)
Je cherche à trouver le pixel noir (i,j) tels que la distance entre (i,j) et (x,y) soit minimale
Un algorithme idiot est le suivant :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

min=infini pour chaque pixel (i,j) de l'image binaire { si ce pixel est noir et dist(i,j,x,y)<min alors { min=dist(i,j,x,y) saveI=i saveJ=j } } retourner saveI,saveJ

---

Cet algorithme est très couteux en temps de calcul
Quelqu'un connait une solution standart?
Merci d'avance

Il saut voir cela comme une recherche de plus court chemin (disjkstra, A*) voire de parcours en largeur si tu utilises la distance de Manhattan.

Intuitivement, cela revient à parcourir des cercles concentriques (centrée en x,y) de plus en plus grand jusqu'à rencontrer un pixel noir. Comme une onde qui se propage.

Bonjour,

Citation:

---

Comme une onde qui se propage.

---

cela me semble la meilleure idée. En revanche, il ne sera pas facile de progager le front étant donné que tu es dans un espace discret.

Si tu ne dois pas répéter cette opération trop souvent, la méthode basique peut etre bien.

Ce que tu fais, ressemble au calcul de la carte des distances pour une contour actif.

Bonjour,
Je vous soumets un petit algo.
Dites-moi ce que vous en pensez.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

max_l <- max(largeur, hauteur) min <- infini pr l = 0 à max_l-1 pr i = max(0, x-l) à min(largeur, x+l) pr j = max(0, y-l) à min(hauteur, y+l) si pix(i,j) noir et dist((i,j),(x,y)) < min min <- dist((i,j),(x,y)) save_i <- i save_j <- j si max_l = max(largeur, hauteur) max_l <- partie_entiere_sup(min*sqrt(2)) fsi fsi fpr fpr fpr

---

On propage la recherche depuis le point (x,y) dans des carrés (qui deviennent des rectangles quand on arrive aux bords de l'image) centrés sur (x,y).
La condition d'arrêt (non optimale) que j'ai choisie est basée sur le fait que la recherche se fait sur des carrés et non sur des cercles. Au 1er pixel noir trouvé on se trouve, au pire, sur la diagonale du carré. Il peut donc y avoir des points plus proches de (x,y) non encore explorés. Normalement en faisant max_l <- partie_entiere_sup(l*sqrt(2)) je pense qu'on est sûr d'exporer tous les pixels qui pourraient être plus proches de (x,y). Tout ça à condition que la distance soit euclidienne.

Il est clair que cette recherche n'est pas la meilleure possible mais elle est sûrement plus rapide.

Bonjour,

J'aurais utilisé la même méthode que tomtom.
On peut légérement améliorer.

1) avec : max_l <- partie_entiere_sup(min*sqrt(2))
2) en limitant l'étendue des boucles i/j en remplacant dans les bornes de la boucle l par l-min , lorsqu'on a trouvé un "point noir".

Très juste.
C'est corrigé pour min*sqrt(2)
Merki :wink:

Comme souvent quand on programme un algorithme, il faut se demander si l'on a pas une autre solution que l'assaut frontal.
Dans ton cas, deux cas se présentent. Soit il y a beaucoup de points noirs, et dans ce cas, l'algo que tu présente semble très bon. Soit il y a peu de point noirs et tu a peut-être intérèt à faire leur inventaire puis à chercher dans l'inventaire.
Le choix de la solution dépend vraiment du nombre de point et des caractéristiques de la machine.

Citation:

---

Envoyé par Selenite

il y a beaucoup de points noirs, et dans ce cas, l'algo que tu présente semble très bon.

---

Pas vraiment non... C'est indépendant de la densité de points noirs dans l'image puisqu'on cherche le point noir le plus proche d'un point. Dans tous les cas il plus judicieux de faire recherche depuis le dit point (il ne sert à rien de parcourir l'image de haut en bas si le point de référence se trouve en bas).

Merci pour l'algorithme proposé
Je vais l'utiliser pour le moment, cependant, je suis persuadé qu'il s'agit d'un problème standard pour lequel des solutions optimales existent ! Mais je pense que cet algorithme n'est pas loin de la solution optimale.

Certes, une connaissance à priori de la distibution des points noirs peut servir à améliorer l'algorithme, si par exemple on est sûr que le point noir se situe au dessus du point en question, il est inutil de parcourir les points du dessous ! Mais dans ce cas, on n'a aucune connaissance à priori !

EDIT: Je laisse le topic non résolu, je pense qu'il existe d'autres solutions !

Important : Quand on trouve une première distance qui est min l'idéal serait de limiter la recherche dans le cercle qui a pour centre (x,y) et qui a pour rayon min mais comme on travaille sur les carrés et non pas sur les cercle, on limite notre recherche sur le carré qui contient ce cercle. Ce carré a pour demi-longueur min et non pas min*sqrt(2)
En plus, puisqu'on cherche une distance qui soit strictement inférieure à min on limite la recherche dans le cercle de rayon min-1 donc dans le carré de demi-longueur min-1. Cette dernière affirmation suppose qu'il n'y a pas de pixels entre deux cercles discrets de rayons r et r+1

Salut,

je ne comprends pas très bien la question alors désolé si je suis hors-sujet :)

Tu as l'opération appelée "Distance Morphologique" (ou distance géodésique) qui se fait en 2 passages d'images sur image binaire.

Elle permet de faire une foultitude d'opérations en temps constant (a taille d'image donnée) :

- érosion multiple
- dilatation multiple
- érodé utlime
- squeletisation
- et d'autres que je dois oublier

En entrée une image binaire, en sortie une carte des distances de chaque pixel noir au pixel blanc qui lui est le plus prés (ou l'inverse).

Si ça correspond bien à ton problème, je détaillerai plus amplement l'opération. J'ai également un code c++.

A+

Flo.

PS : voici une page web qui y est consacrée :

http://www.ext.upmc.fr/urfist/image_...ropagation.htm

pour résumer :
j'ai une image binaire
j'ai calculé son squelette
j'ai décomposé le squelette en plusieurs parties et affecté à chaque partie du squelette une couleur
Ensuite, il s'agit de colorer chaque partie de l'image binaire initiale avec la couleur du squelette qui lui est la plus proche. C'est dans cette étape que j'ai eu besoin de l'algorithme en question (j'ai simplifié le problème initialement, mais en réalité je vais exécuter l'algo pour tous les points de l'image binaire et non pas pour un seul point)

Citation:

---

Envoyé par tomtom7

Citation:

---

Envoyé par Selenite

il y a beaucoup de points noirs, et dans ce cas, l'algo que tu présente semble très bon.

---

Pas vraiment non... C'est indépendant de la densité de points noirs dans l'image puisqu'on cherche le point noir le plus proche d'un point. Dans tous les cas il plus judicieux de faire recherche depuis le dit point (il ne sert à rien de parcourir l'image de haut en bas si le point de référence se trouve en bas).

---

Je parlais du dernier algo proposer, celui qui part du point de référence.
Ensuite, si la densité à quelque chose à voir. La densité moyenne nous donne le nombre de test moyen que l'on aura à effectuer. Plus la densité est basse, plus le nombre de test sera grand. Alors qu'avec un index de points noirs, plus la densité est basse plus la recherche sera rapide. Il faut savoir dans quelle zone on se trouve.

Salut,

donc tu as bien besoin d'executer une distance morphologique avec propagation d'étiquettes.

Je sais pas si tu connais le principe de la distance morphologique.

Ben c'est la même chose sauf qu'en plus de garder le min des voisins (en ajoutant 10 ou 14 selon la position du voisin), tu gardes aussi son étiquette (dans ton cas la couleur du squelette).

C'est le type même d'opération qu'on résoud par la distance morphologique avec propagation d'étiquettes.

Voilà, l'algo est pas très compliqué. Et j'ai également le code c++.

:D

A+

FLo.

ça serait sympa de ta part si tu m'envoies ce code c++!
PS: avec la méthode actuelle le résultat est obtenu instantanément

Citation:

---

PS: avec la méthode actuelle le résultat est obtenu instantanément

---

Bon ben c'est peut-être pas la peine de plus se casser la tête...
Mais comme on est un poil mazos : S'il faut faire ça pour tous les pixels alors quand on a le plus proche point noir pour un pixel donné (1), on peut le réutiliser pour le pixel (2) suivant afin de limiter l'espace à explorer.
En fait, je réalise que si la distance à (1) est assez grande, on a un no man's land autour de (2) où on ne risque pas de trouver plus proche.