Centre d'une figure

Bonjour à tous et à toutes :)


Alors voila, je bloque dans mon code en ce moment, donc j'espère que quelqu'un pourra m'aider, ou me mettre sur la voie :/


Pour le moment, mon code se contente de tracer un cercle blanc sur fond noir, avec 5 "trous" équidistants.

Ce que j'aimerais faire, c'est savoir ou ce trouve le centre de ma figure, je m'explique :

Ma figure donne ceci (voir pièce jointe), et est placée aléatoirement sur l'écran quand on lance l'application.

J'aimerais donc par je ne sais qu'elle moyen, parcourir l'écran pour trouver le cercle blanc et déterminer son centre, puis trouver la position angulaire du petit cercle noir (entouré en rouge sur l'image en pièce jointe)


Quelqu'un peut-il m'aider ?
Merci d'avance pour vos réponses. :)


Cordialement,
Kadath.

Salut !

Ce n'est pas trivial, il s'agit d'une tâche de vision par ordinateur. A ta place, je me tournerais vers l'utilisation d'une librairie comme OpenCV. Ton problème est assez simple du point de vue de la lib et une transformée de Hough généralisée devrait faire l'affaire.

PS osef : j'ai testé OpenCV hier soir et ça roxe

La premiere partie du probleme est triviale.
J'imagine aue dans ton image il n y a que ces figures au moment ou tu va lancer l'algorithme.

Tout depend aussi de la nature de l'application ( doit elle etre rapide ou precise ?)

Ce que je te propose :

Si l'application doit etre la plus precise possible.
- un petit filtre qui construit une image tampon ou sera dessine les contours.
Des qu il y a une difference de couleur tu met le pixel correspondant a 255 dans l'image tampon.

- tu parcourt le contour du grand cercle blanc en calculant son perimetre.

- tu calcul son diametre ( plus particulierement son rayon )

- tu repart d'un point du cercle et tu parcourt son demi perimetre.

- Une fois ici tu calcul le vecteur entre ces deux positions.

- tu translate un de tes points du rayon dans la direction et le sens du vecteur ( adequoit ).

La tu as ton centre d'une facon precise.

Pour le cercle noir je suis pas sur d'avoir compris. Si tu veux recuperer le premier cercle noir sur la droite vers le haut c'est facile :

- tu parcourt ton image tampom de contour et tu selectionne le cercle qui possede tous ses points avec :
- une abscisse positive
- une ordonnee positive et minimale.

Si tes cercles sont bien equidistants sa marche.

N'hesite pas a te faire des petites structure pouvant accueillir des familles de points, sa te facilitera la tache dans la recherche de cercles.

En esperant avoir put t aider.

Ps : Vraiment desole pour les accents , le clavier que j ai est QWERTY

Ps2 : Biensur tu peux te tourner vers OpenCV si tu n a pas envie de te fatiguer. Tout depend du but pedagogique ou applicatif de ton application.

Citation:

---

Envoyé par nightwar

Ps2 : Biensur tu peux te tourner vers OpenCV si tu n a pas envie de te fatiguer. Tout depend du but pedagogique ou applicatif de ton application.

---

En effet. Ca dépend de l'image d'entrée : si c'est du beau noir et blanc nickel à pile poil 255 et 0, sans déchets, ça facilite grandement les choses. J'étais parti du principe que l'image d'entrée n'était pas aussi propre, mais ça peut être le cas, au temps pour moi.

Ca peut aussi être, sans aucune critique à l'égard des idées de Nightwar qui devraient fonctionner, l'occasion de mettre les doigts dans les outils mathématiques "génériques" utilisés pour ce genre de choses.

Peut-on en savoir un peu plus sur ce que tu fais ? La vision est un sujet qui m'intéresse particulièrement, je suis curieux :mrgreen:

Alors, oui l'image est seulement composée de couleur bien propres (un beau noir en 0,0,0 et un beau blanc en 255, 255, 255)

J'utilise la librairie SDL, et SDL_gfxprimitives pour mes cercles.



J'avais imaginé une boucle, qui parcourrai l'écran horizontalement jusqu'a trouver un pixel blanc. Puis une boucle parcourrai toujours horizontalement la zone blanche jusqu'a rencontrer un pixel qui ne serait pas blanc

A partir de ca, on pourrait prendrait la moitié de cette valeur puis une boucle parcourrai depuis ce milieu de droite la zone blanche mais verticalement cette fois, puis, en prenant le milieu de la valeur obtenue, et en l'associant a celle obtenue par le parcours de la zone en horizontal, on obtiendrais le centre du cercle.
(Cette partie serait donc intégrée après le traçage du cercle blanc mais avant les cercles noirs)



Mais c'est plus difficile a coder que ce que je ne le pensait..

Je fait (ou plutôt j'essaie de faire) une application qui génère une sorte de jante (cercle blanc composé de cinq cercles noirs équidistants positionnés aléatoirement a chaque lancement de l'application) et dont on déterminerai la position angulaire du premier cercle noir à droite, et qui afficherait donc sa position a l'écran sous forme:

x=r*cos(θ)
y=r*sin(θ)

r étant le rayon du cercle de positionnement.


Avec un schéma, ce sera peut être plus clair ^^'


Si l'un de vous peut m'aider un peu a avancer, je suis preneur..
Merci d'avance pour vos réponses
(Et merci pour vos réponses passées^^)

Tant mieux alors car je travaille dans la vision :).
En fait c'est plus un probleme de traitement d'image que de vision mais ne chipotons pas.

Citation:

---

Ca peut aussi être, sans aucune critique à l'égard des idées de Nightwar qui devraient fonctionner, l'occasion de mettre les doigts dans les outils mathématiques "génériques" utilisés pour ce genre de choses.

---

Aucune critique tu as tout a fait raison. Certaine personne ( comme moi ) aime maitriser de A a Z l'algorithme mis en jeu. Mais Utiliser des outils generiques est fortement recommande.

Citation:

---

En effet. Ca dépend de l'image d'entrée : si c'est du beau noir et blanc nickel à pile poil 255 et 0, sans déchets, ça facilite grandement les choses. J'étais parti du principe que l'image d'entrée n'était pas aussi propre, mais ça peut être le cas, au temps pour moi.

---

Oui c'est un point non negligeable dans le deroulement de l'algo. Il y a toujours une facon d'eliminer ces "dechets" mais cela peut s'averer fastidieux.


Ton algorithme presente un defaut.
Que fais tu si tu rencontre un pixel noir correspondant a un des petits cercle noir sur ta trajectoire.

Peut tu par contre explicite clairement les conditions ?:

- placement aleatoire et equidistant des cercles noirs ?
- taille du cercle blanc fixe ( important ! )

Coder ce genre d'algorithme est evident si tu possede une structure solide. Je peux te renseigner sur ce pourquoi tu bloque



EDIT

Citation:

---

(Cette partie serait donc intégrée après le traçage du cercle blanc mais avant les cercles noirs)

---

Sa m'apprendra a lire a la va vite. Tu as cependant des cas critiaue ou tes droites sont tangante au cercle .Dans ce cas la tu dois gerer pas mal de comportements.

Et puis honnetement je ne comprend pas le but de l'application si tu peut lancer l'algo avant le dessin des cercles noirs ? Peut tu approfondir le but ?

Si l'objet qui t'intéresse est en blanc, Pourquoi ne pas calculer simplement le centre de gravité de l'image entière ?

Citation:

---

Envoyé par nightwar

Et puis honnetement je ne comprend pas le but de l'application si tu peut lancer l'algo avant le dessin des cercles noirs ? Peut tu approfondir le but ?

---

C'était ce que je demandais quand je demandais d'en savoir un peu plus. Peux tu nous parler de l'application ? ça nous aidera à t'aider (si je puis m'exprimer ainsi).

Citation:

---

Si l'objet qui t'intéresse est en blanc, Pourquoi ne pas calculer simplement le centre de gravité de l'image entière ?

---

L'objet mysterieux n'est pas au centre de l'image.

Citation:

---

Envoyé par nightwar

L'objet mysterieux n'est pas au centre de l'image.

---

Justement ! Si on considière les pixels comme des points pondérés avec la valeur de leur niveau de gris (soit en l'occurence 0 ou 255, ou 0 et 1 pour simplifier) celà fonctionne effectivement...

Là on a affaire à une image segmentée, on sait qu'il s'agit d'un cercle... Trouver le contour est facile, il suffit de faire un fitting de cercle dessus et ça marche aussi. Tout dépend aussi de la taille de ce cercle en pixel par rapport au reste, des performances, requises, etc.

En fait le problème est suffisamment simple pour qu'il y ai plein de manières de le résoudre.

Kadath, ça serait vraiment bien que tu nous donnes des détails sur ce que tu fais. Je ne comprend pas pourquoi tu veux faire de la détection dans l'image alors que tu as la main sur le processus de génération de celle-ci.

Citation:

---

Envoyé par nightwar

Peut tu par contre explicite clairement les conditions ?:

- placement aleatoire et equidistant des cercles noirs ?
- taille du cercle blanc fixe ( important ! )

---

* Par placement équidistants, j'entends que les cercles seront toujours espacés de 360/5 soit 72°.
* Le rayon du cercle blanc fixe est de 250 pixels

Citation:

---

Envoyé par nightwar

Et puis honnetement je ne comprend pas le but de l'application si tu peut lancer l'algo avant le dessin des cercles noirs ? Peut tu approfondir le but ?

---

Je ne comprend pas ce que tu ne comprends pas? :?
Dans mon code, je veux juste commencer par tracer le cercle blanc, puis trouver son centre et placer les cercles noirs, afin justement de ne pas rencontrer de pixel noir correspondant a l'un des cercles noir lors de la recherche du centre.


Le but final étant de trouver la position angulaire du premier cercle noir de droite par rapport a l'axe horizontal (diamètre du cercle blanc) et de l'afficher a l'écran.

Et ce quelque soit la position du cercle blanc sur l'écran.
(cf les schémas en pièces jointes dans mon message précédent).


EDIT:

Citation:

---

Envoyé par nightwar

Tu as cependant des cas critiaue ou tes droites sont tangante au cercle .

---

Etant donné la taille du cercle par rapport a l'écran, en parcourant l'écran entre certaines valeurs, je pense qu'il n'y aura pas de soucis de cas ou les droites seront tangentes :)

Je ne comprend toujours pas le but de cette application. Est elle uniquement pour toi ? Un utilisateur va-t-il placer le cercle blanc et ton algo prend le relai en traçant les cercles noirs ? Difficile de cerner le sujet. Il te parait peut être simple étant donné que tu est le rédacteur !

Cela dit ( je retrouve un clavier AZERTY quel bonheur !) le coup du centre de gravité est une bonne approche, encore faut il savoir le coder et délaisser l'aspect performance ( un parcourt d'image s'impose pour générer la carte des poids et un autre pour positionner le centre), je peux cela dit me tromper étant donné le peu d'information donné par l'auteur de cette approche intéressante.

Ton problème peut être résolu de beaucoup de manière alors je te pose quelque question.

- qui à la main sur l'application?
- peut tu décrire un "use case" cas d'utilisation typique ?
- L'application doit être précise ou performante ?

Bien que cela ne soit pas trop nécessaire pour un problème de cette envergure....


Si le cercle possède un rayon de 250 pixels cela devient trivial.
- A la rencontre d'une discontinuité tu recherches dans un panel de 5 ou 6 voisins sur le contour du cercle.

- tu calcules un vecteur tangent
- tu te dirige de 250 pixels perpendiculairement au vecteur en partant de son origine et tu tombe pile poil sur le centre.

N'oublie pas de prendre en compte la concavité pour ne pas te retrouver n'importe ou !

En gros, on a une vue d'une "jante" percée de 5 trous représentant le passage des vis. Le diamètre de la jante et celui des trous sont connus. La position de la jante sur l'image n'est pas connue. Et l'application doit pouvoir permettre de trouver la position angulaire d'un des trous.

C'est une base pour une application qui servira a récupérer une image a partir d'une caméra pour faire le même traitement, afin de repositionné ou non la jante pour y fixer des vis de fixation.


EDIT

Je pensais utiliser quelque chose du genre:

Citation:

---

int getR(Uint32 couleur){return (couleur >> 16) & 0xff;}
int getG(Uint32 couleur){return (couleur >> 8) & 0xff;}
int getB(Uint32 couleur){return couleur & 0xff;}


bool testerCouleurNoire(int couleur)
{
if (getR(couleur)!=0) return false;
if (getG(couleur)!=0) return false;
if (getB(couleur)!=0) return false;
return true;
}

---

Puis utiliser une boucle avec un getPixel testant si la couleur est noire ou non, si oui on continue, si non on commence le traitement de la zone blanche (j'entends par là, la recherche du centre)

Mais j'ai du mal a le mettre en oeuvre...


Si vous voyez comment faire, ou si vous avez plus simple pour résoudre

Citation:

---

on a une vue d'une "jante" percée de 5 trous représentant le passage des vis. Le diamètre de la jante et celui des trous sont connus. La position de la jante sur l'image n'est pas connue. Et l'application doit pouvoir permettre de trouver la position angulaire d'un des trous.

---

Je suis preneur

Oula, je perds les fils.

Tu cherche à calculer le centre du cercle en blanc dans une image avec fond noir !

Oui kmaniche, c'est bien cela, je cherche a trouver le centre d'un cercle blanc sur fond noir

Re salut.

Déjà le problème est plus clair. Tes fonctions servent à quoi étant donné que l'image est en noir et blanc? Si ton image est couleur sa sera beaucoup plus compliquer que sa pour utiliser tes fonctions. ( conversion niveaux de gris puis binarisation qui dépend d'un seuil lui même dépendant de facteurs de luminosité d'histogramme etc... de ton image).

Ton image est noir et blanc : ces fonctions ne te servirons a rien.
Ton image est couleur : transforme la en noir et blanc.

Certain posts t'ont évoqué des solutions très acceptable pour ton problème. A ce que je vois c'est un traitement basique d'image qui est automatisé ( pourquoi vouloir placer le cercle blanc ? il est déjà présent dans l'image à un endroit inconnu ainsi que les cercles noirs)

Relis les ancien posts et choisit l'algorithme qui te fais le plus envi. Si tu bloque toujours autant donne un debut de code implémentant un algo on se fera une joie de t'aider/préciser/ avancer ton problème. :)

D'une manière plus générale ton approche semble bonne:
détecter le centre du cercle blanc ensuite avec une fenêtre de taille fixe tu te balade dans le cercle pour trouver un cercle noir ( de la même façon que pour le blanc) et tu détermine le centre de celui ci. En ayant les deux centre tu en déduit facilement l'angle.

Citation:

---

Envoyé par Kadath

Oui kmaniche, c'est bien cela, je cherche a trouver le centre d'un cercle blanc sur fond noir

---

Est-ce que tu as essayé à calculer le centre de gravité et voir le résultat. C'est solution très simple pourtant.:mouarf:

Citation:

---

Envoyé par nightwar

Tes fonctions servent à quoi étant donné que l'image est en noir et blanc?
[...]

Ton image est noir et blanc : ces fonctions ne te servirons a rien.
Ton image est couleur : transforme la en noir et blanc.

---

Tout à fait d'accord avec toi, l'image ne sera pas en noir et blanc a la base, mais comme tu l'as aussi dit, en la convertissant en noir & blanc par conversion des niveaux de gris, c'est là que mes fonctions traitants l'image en noire et blanc me seront utiles :)

Citation:

---

Envoyé par kmaniche

Est-ce que tu as essayé à calculer le centre de gravité et voir le résultat. C'est solution très simple pourtant.:mouarf:

---

Je ne vois pas trop ce que tu entends par "calculer le centre de gravité" :/

Peux-tu m'expliquer un peu plus en détails s'il te plait? :)

Même si tes fonction sont de simple opération binaires ( que je te conseille de définir en inline ) il ne faut pas les utiliser à chaque fois que tu veux connaitre la couleur ( équivalente en noir ou blanc ). Il faut absolument créer un tampon (image) contenant ta nouvelle image noir et blanc et travailler sur celle ci.

- Post processing : Conversion en niveau de gris :
Tu peux simplement faire une moyenne des composante RGB.
Tu peux utiliser une formule (cf wikipedia) qui te donne la pondération des composante RGB en pourcentage.

- Binarisation :
Tu définis un seuil et lorsque ton niveau de gris est supérieur c'est blanc inférieur c'est noir.

Une méthode encore plus simple et rapide (mais moins efficace) est de considérer une seule composante ( par exemple le rouge ) et de la confronter au seuil directement pour la binarisation. Tu économise le passage niveau de gris.

Une fois avec cette image choisis un algorithme précédemment définis.

Puisque l'image contient un fond noir avec un disque blanc, si tu cherche à calculer le centre du disque, cela revient à calculer le centre de gravité de l'image.

La formule est :

Xc = {somme(i, avec i=1 -> nbre de lignes)[si m(i,j) est blanc} / nbre de pixel blanc dans l'image

Yc = {somme(j, avec j=1 -> nbre de colonnes)[si m(i,j) est blanc} / nbre de pixel blanc dans l'image

nightwar ta solution avec l'algorithme de la transformée de Hough généralisée me semble plutot bien, pourrais-tu si tu as un moment me l'expliquer un peu mieux?
J'ai regarder un peu sur le net mais je ne comprend pas vraiment tout..

Dis merci à jbleCanard, l'idée vient de lui.

Pose toi juste une question avant de te lancer la dedans. As-tu besoin d'un algorithme de ce calibre la ? Pour en avoir codé une transformée de hough est fastidieuse en contre partie très puissante.

Pour t'éclairer le principe est très simple, tu transforme les caractéristiques de ton image dans un espace dit de hough ou il est plus facile de trouver ce que tu cherche. C'est vraiment simplifié mais c'est le principe. Avec cette transformée tu est capable de trouver tous les cercles d'une image par exemple. Wikipédia est pauvre en transformée de Hough généralisée ( car a la base elle sert pour la détection de lignes ).

Je te conseille vivement d'utiliser des implémentations déjà faite (OpenCV), mais cela te demandera de te familiariser avec cette bibliothèque.

Arf!
kmaniche, nightwar, vos deux propositions me semblent intéressantes!
Reste à voir laquelle serait la plus simple a mettre en oeuvre pour mon type d'application..:?

Salut

voilà qui me parle un peu plus ! On est donc bien en plein dans la vision :mrgreen:. En revanche, je ne vois toujours pas pourquoi tu peux dans ton application disposer de l'image avec uniquement le cercle blanc. Si c'est une image traitée depuis une caméra, retirer ces cercles est aussi difficile que ce que tu veux faire.

Comme le dit nightwar, la fameuse transformée de Hough est un outil un peu massif au vu du problème, mais pas besoin de la coder soi même. Autrement dit : ce serait dommage de faire un Hough sans comprendre au moins mathématiquement comment ça marche, mais faut pas hésiter à prendre une lib en production.

Es-tu en charge du traitement complet de l'image depuis la caméra, ou est ce que on te balance l'image binarisée et demerden zie zich avec ?

J'ai l'impression en te lisant que tu codes vraiment tout toi même, y compris la structure de données qui porte une matrice pour faire tes traitements. Est ce le cas ?

Dois tu privilégier la précision ou la rapidité ? Je dirais la précision à priori, car si tu place les vis à côté :aie:

Au niveau simplicité de mise en oeuvre et de compréhension, la solution de kmaniche est la plus simple. Et elle devrait en théorie également fonctionner même si les cercles noirs sont présents, sinon ça voudrait dire que ta jante est déséquilibrée.

L'avantage d'une transformée de Hough est par contre qu'elle va te donner directement tous les cercles et leurs coordonnées, qu'elle fonctionnera bien sur des images dégradées, etc.

Dans tous les cas, dont worry, on va y arriver :mouarf:

A part : A propos d'OpenCV, je trouve qu'on y met très vite les mains. Je suis en train de jouer avec chez moi et je m'éclate.

lol. J'aime les petits PS en taille inferieur a la fin de tes messages.

Oui OpenCV est vraiment complet et facile d'utilisation. Je l'utilise massivement.

On attend de tes nouvelles pour le calcul du centre de gravite et pour les reponses aux precedentes questions.