# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  Identifier le centre d'une ellipse

## shindara

Bonjour,
Je suis actuellement en train de developper une application Java qui doit a un moment donne identifier le centre d'ellipses presentes sur une image, dans laquelle il n'y a aucun bruit (je joins un exemple d'image au post).
J'aurai donc plusieurs questions : 
- tout d'abord quelle est selon vous la meilleure methode pour identifier les centres des ellipses ?
- je pensais utiliser la transformee de Hough, qui parait theoriquement pas mal, mais j'ai beaucoup de mal a voir comment l'appliquer surtout dans le cas d'une ellipse. Encore une fois je ne cherche qu'a identifier les centres, et non a obtenir les contours par exemple, Hough devrait donc etre simplifie je pense. Donc si vous pouviez me mettre sur la voie ca serait parfait...
- enfin, si qqun a envie de faire partager un peu de code java ou tout ca est implemente, je suis preneur ;-).
Voila, j'espere avoir ete clair.
Merci pour votre future aide.
Thomas

----------


## souviron34

ben dans ce cas je dirais ma mthode  :;):  (moindres carrs gnraliss).

je posterais le code (je l'ai en Fortran, mais j'essaierais de le traduire en C) dans la nuit, puisque cela fait plusieurs fois que la question est pose, je le mettrais dans contribuez...

----------


## shindara

les moindres carres ?? J'y avais pense mais je trouvais ca tres complique pour les ellipses et je ne pensais pas que ca pouvait detecter plusieurs ellipses sur une meme image. Mais bon meme si ca m'en detecte une seule, je prends, ca me va parfaitement ;-)... C'est pour ca que je pensais que Hough etait plus efficace...
En tout ca, merci bien
Thomas

----------


## souviron34

ok j'ai mis le code dans contribuez (http://www.developpez.net/forums/sho...d.php?t=363333)..

Dsol c'est du Fortran.. Pour la conversion en C, on verra plus tard.

Les 2 paramtres principaux sont les tableaux XX et YY, les tableaux des coordonnes X et Y des pixels pris en compte dans l'image...

Comme c'tait pour de l'astrophysique, le principe tait le suivant :

Dans une image, isoler tous les pixels d'une certaine intensit (+ ou - delta).Stocker leurs coordonnesAppeler la routine, et donc dterminer les paramtres de l'ellipseChanger l'intensit

C'tait pour un cas o je n'tais cens avoir qu'une srie d'ellipses dans l'image, prises une  une, chacune spare par une intensit (en fait une image de galaxie o la luminosit va dcroissante du centre vers le bord : une sorte de ballon de rugby 3D)). Je dfilais donc dans le delta total d'intensit..

Il est quasi sr que avec plusieurs ellipses simultanes, effectivement Hough est mieux... 

Mais avec une image comme tu montres, ceci marche trs bien...

Et quoiqu'il en soit,je voulais mettre cet algo sur le site, donc merci  :;):

----------


## ToTo13

Bonjour,

alors :
 - Hough est trs bien pour les ellipse.
 - Sinon il y a la mthode de Arnaud Le Trotter et Remy Bulot (laboratoire LSIS, quipe I&M) qui fait du suivit d'ellispe temps rel car l'application est sur des flux vidos. Cette mthode est expliqu dans la thse de Arnaud.

----------


## shindara

Bonjour,
Premierement, merci beaucoup pour le code Fortran, je m'empresse de le traduire en java, de le tester et de le poster si qqun est interesse.
Deuxiemement, la question sur Hough n'etait pas  "est-ce applicable aux ellipses", mais "comment l'appliquer aux ellipses". Parce que je pense qu'il y beaucoup de methodes possibles en fait, et Hough parait etre une des meilleures. Mais d'apres ce que j'ai vu, notamment sur ce forum, on parle d'espace a cinq dimensions,etc... sans trop detaille la methode, qui a l'air tres compliquee. Et j'ai aussi cherche la methode de Arnaud Le Trotter et Remy Bulot, mais je n'ai pas reussi a la trouver.
Dans mon cas je pense que je peux me limiter a un espace a deux dimensions, etant donne que je ne cherche que les coordonnees du centre, et j'avais trouve une methode calculant ces coordonnees avec au minimum trois points appartenant a l'ellipse et en utilisant les tangentes a l'ellipse. Peut etre est ce cette methode la qui est decrite dans la fameuse these, mais le fait est que je ne vois pas comment obtenir les equations des tangentes seulement a partir des coordonnees de trois points. Voila j'espere avoir ete a peu pres clair.
Merci encore en tous les cas pour votre aide.
Thomas

----------


## pseudocode

Heu... rassure moi: l'image que tu as post n'est pas la veritable image que tu dois traiter ?  :8O:

----------


## souviron34

lol pourquoi pas ?

[EDIT]
Tiens je posterais un scan d'une image astro pour vous montrer.. quand je serais rentr...
[/EDIT]

----------


## pseudocode

> lol pourquoi pas ?


ben dans ce cas, une simple segmentation (blanc/noir) + labelisation (scanline) + bounding box (min/max)... et hop... le centre des ellipses = le centre des bounding box.  ::mrgreen::

----------


## souviron34

::mouarf::   faux...

regarde la figure ci-jointe...

Le point rouge le centre de l'ellipse, le point khaki le centre de la BoundingBox...

 ::aie::

----------


## pseudocode

Ah ok... J'avais pas compris l'image du P.O. En fait, il cherche le centre d'une ellipse connaissant seulement 5 points du contour.

Je croyais qu'il cherchait le centre de CHACUNE des 5 petites ellipses blanches.  ::mrgreen::

----------


## shindara

En fait ce que je cherche c'est bien le centre de toutes mes ellipses>
Ce que je pensais faire c'etait filtrer prealablement avec un filtre de Sobel pour extraire les contours des ellipses (mais peut etre que je n'en ia pas besoin...) et ensuite je prends entre 10 et 20 % de mes points de contour  et je calcule mon centre avec les moindres carres.
Voila mon idee de depart, mais je suis peut etre completement a cote de la plaque en fait, faut pas hesiter a me le dire...
Thomas

----------


## parp1

Tu travailles sur une image d'un Fantme?

J'imagine que tu vas traiter un probleme plus complexe par la suite non ?

Je pense que si c'est le cas il serait interessant de nous mettre une image relle.
Parce qu'un algorithme fonctionnant pour quelque chose de simple, ne resoudera pas forcement un probleme compliqu. Et l'inverse c'est pareil.
Merci!

----------


## shindara

Je travaille en fait sur des images de scanner. J'ai donc toute une serie d'images qui sont les plans de coupe de machoire de patient et ces ellipses ne sont en fait que des implants. Le but est ensuite de construire ces implants en trois dimensions en construisant des cylindres qui doivent etre construits exactement a l'endroit des implants sur le scanner.
Donc mon idee est la suivante : 
-identifier le centre d'un implant sur chaque image du scanner -> identifier le centre d'une ellipse.
-tracer en trois dimensions la droite qui passent par tous les centres ou du  moins celle qui minimise la distance entre la droite et tous les points
-construire mon cylindre autour de cette droite.

Voila pourquoi j'ai besoin du centre des ellipses. Je ne sais pas si ces precisions font avancer le debat, mais ca situe le contexte quoi... Donc l'image que j'ai montree est une image reelle, une de celle que j'utilise.

----------


## pseudocode

> Voila pourquoi j'ai besoin du centre des ellipses. Je ne sais pas si ces precisions font avancer le debat, mais ca situe le contexte quoi... Donc l'image que j'ai montree est une image reelle, une de celle que j'utilise.


Vous faites comme vous voulez, mais je pense que Hough c'est un peu dmesur face au probleme.

La solution: Segmentation + Labelisation + BoundingBox me parrait beaucoup plus simple...

----------


## shindara

je suis d'accord que Hough peut paraitre demesure c'est pour ca que je cherchais une autre solution. 
J'avais d'ailleurs pense a une Bounding Box, mais sur certaines images on ne voit que la moitie de l'ellipse si l'implant est penche. Et dans ce cas la il faut que je calcule le centre juste a partir des points que j'ai, et la une bounding box ne marche pas... Comme ce sont des plans de coupes, pour un implant penche, la premiere image et le derniere image ne representeront pas l'implant en entier mais seulement une partie (comme sur l'image jointe). J'ai donc besoin d'une methode qui calcule le centre d'une ellipse, meme quand celle ci est a moitie presente...

----------


## pseudocode

> Comme ce sont des plans de coupes, pour un implant penche, la premiere image et le derniere image ne representeront pas l'implant en entier mais seulement une partie (comme sur l'image jointe). J'ai donc besoin d'une methode qui calcule le centre d'une ellipse, meme quand celle ci est a moitie presente...


A la vue de l'image jointe, je ne pense pas qu'il y ait assez de points pour obtenir un centre d'ellipse fiable. Autant approximer et rechercher le centre d'un cercle. C'est plus simple et sans doute suffisant...

----------


## souviron34

je suis au regret de te dire que ma mthode marche avec moins de 1/50 ime des points...  ::P:  

En fait, si mes souvenirs sont bons, sur une image 512*512, avec une ellipse le long de la diagonale, il me semble qu'avec seulement une 50 aine de pixels dans un des coins je trouvais l'ellipse...

Comme je disais, je vous posterais une image originale vers la mi-juillet  :;):

----------


## pseudocode

Je ne dis pas que Hough ne marchera pas... Je dis juste que, a la vue de l'image:

1. les ellipses sont tres proche d'etre des cercles
2. visiblement tous les cercles ont +/- le meme diametre

Et je pense qu'il y a plus simple que Hough pour trouver le centre d'un cercle quand on a N points consecutifs de son contour et qu'on connait son diametre approximatif. Mais bon, ce n'est que mon avis.

----------


## parp1

Re bonjour, ton probleme a l'aire interressant. Pourquoi ne pas faire une Hypermatrice, c'est a dire, tu crer un matrice 3D constitu de tes coupes.

Un simple seuillage 3d permet d'extraire tes implants.

Pour ma part j'utilise VTK.

Tu programmes dans quel language?
Je te mets un exemple d'un seuillage de crane que j'ai fait avec des donnes fournis par VTK. J'ai seuill les dents. 

Les resultats sont assez laids car les images font 64*64*93. Et nous avons des variations dans les gris, bien plus que sur tes images.

Mais l'extraction est rapide.

Si tu veux tu pourrais m'envoyer des images afin que je puisse faire la manip sur mon poste si tu veux. J'espere que c'est du Dicom Anonymis.

----------


## shindara

Alors j'ai pas bien compris l'hyper matrice et le seuillage 3d mais je veux bien essayer oui.

----------


## shindara

> Je ne dis pas que Hough ne marchera pas... Je dis juste que, a la vue de l'image:
> 
> 1. les ellipses sont tres proche d'etre des cercles
> 2. visiblement tous les cercles ont +/- le meme diametre
> 
> Et je pense qu'il y a plus simple que Hough pour trouver le centre d'un cercle quand on a N points consecutifs de son contour et qu'on connait son diametre approximatif. Mais bon, ce n'est que mon avis.


Sur cet exemple oui toutes les ellipses ont le meme diametre et sont proches d'etre des cercles mais ce n'est pas toujours le cas en fait

----------


## Zavonen

Pour dterminer une ellipse passant par 5 points (5 exactement) pas besoin d'algo compliqu.
Pour dfinir une ellipse unique, il faut 5 points.
On peut alors rsoudre le systme :
a x + b xy + c y + d x + e y + f = 0
qui ne contient en fait que 5 inconnues, l'un des facteurs pouvant tre pris arbitrairement. 
C'est un systme linaire, les mthodes de rsolution ne manquent pas (Pivot de Gauss par exemple) et sont implmentes dans tous les langages.
Cela fait il faut faire disparatre le terme en xy par une transformation linaire

(x,y) -->(X,Y)=A(x,y) o A est une matrice carre orthogonale d'ordre 2 (en pratique une rotation)
Ce problme s'appelle la rduction des formes quadratiques. C'est un autre classique et dans le cas de deux variables on peut le faire  la main sans grosse thorie (en rsolvant  nouveau un systme linaire)
Aprs, dans un repre donn (calcul en transformant le repre canonique par l'inverse de A) l'quation est
aX+dX+cY+dY+f= 0
Attention, c'est pas forcment les mmes coeffs qu'avant !!!!
Il n'y a plus qu' faire une translation pour liminer les termes en X et en Y, cette translation donne le centre de l'ellipse (dans le repre o l'quation est rduite). Il suffit donc de revenir dans le repre initial.
Voil, il s'agit simplement de mettre bout  bout des trucs connus. Il n'y a rien de plus compliqu que la rsolution d'un systme linaire.

----------


## pseudocode

> Sur cet exemple oui toutes les ellipses ont le meme diametre et sont proches d'etre des cercles mais ce n'est pas toujours le cas en fait


Dans ce cas, ok. 

Je conserve quand meme l'ide de Segmentation+boundingBox pour rduire les calculs de Hough

Edit: Je me demande comment faire pour rcuperer les points du contour dans le cas des ellipses partielles... en particulier comment differencier la partie "arrondie" du contour de l'ellipse et la partie "droite" due a la coupe. Peut-etre en calculant le rayon de courbure ?

----------


## souviron34

> Edit: Je me demande comment faire pour rcuperer les points du contour dans le cas des ellipses partielles... en particulier comment differencier la partie "arrondie" du contour de l'ellipse et la partie "droite" due a la coupe. Peut-etre en calculant le rayon de courbure ?


  ::D:  ce que donne ma mthode (a et b)...

----------


## parp1

> Alors j'ai pas bien compris l'hyper matrice et le seuillage 3d mais je veux bien essayer oui.


En fait tu compte faire comment une fois que tu auras tes centres pour reconstruire tes prothese en 3D? openGL?

En fait ton volume est constitu de plusieur couche. Tes images 2D superpos.

Si tu fais une matrice a 3 dimension ayant pour valeur dans chaque case la valeur du Voxel a coordonne suivante.

Pixel (1,1) de l'image1 emplira le voxel de coordonnes (1,1,1)
pixel(2,6) de l'image5 emplira le voxel de coordonnes (2,6,5)

Tu va te retrouver avec un cube de donnes. Le seuillage c'est simple, tu parcours tout tes pixels de ta matrice, et tu mets a 255 ou 1 (selon si tu veux un booleen ou une image) le pixel tant suprieurs a un seuil que tu designes. Et a zro les pixels ne respectant pas la condition.

J'espere t'avoir un peu aid.

----------


## mchk0123

Je vais faire mon pinailleur, mais je vous rappelles  tous qu'une ellipse n'a pas un seul centre mais deux centres (appells foyers) !

Sinon plus pratiquement, pour un cercle il suffirait de prendre l'intersection de 2 droites perpendiculaires aux tangentes en 2 points.
Pour les ellipse il y surement un proprite gomtrique analogue.
Je vais regarder de ce ct, et je reviens ds que j'ai du nouveau.

----------


## Zavonen

> Je vais faire mon pinailleur, mais je vous rappelles  tous qu'une ellipse n'a pas un seul centre mais deux centres (appells foyers) !


Niet, niet !
Il y a les coniques  centre (ellipses et hyperboles) et les autres (paraboles).
Le centre est bien le centre de symtrie. Les autres points, comme vous le dites sont les foyers.

----------


## mchk0123

C'est juste que le problme "trouver le centre d'une ellipse" me parait plus compliqu que le problme "trouver les foyers d'une ellipse".
Et qui peut le plus, peut le moins.

Le problme n'est pas trs simple (surtout s'il s'agit d'une recherche d'ellipse passant au plus prs de points, plutt que exactement sur les points).
Voil ce que j'ai trouv comme aide :

http://www.bmva.ac.uk/bmvc/1997/pape.../ellipse3.html

Et surtout la mthode de calcul suivante :

http://www.bmva.ac.uk/bmvc/2004/papers/paper_083.pdf

Bon courage pour la suite.

----------


## pseudocode

Le probleme c'est que ces methodes font un fitting de courbe. Cela  obliger a calculer les contours de l'image (sobel, ...). Mais cela pose probleme pour les ellipses partielles car le contour fait apparaitre la ligne de coupe, qui n'est pas un element du perimetre de l'ellipse complete.

Sans compter qu'il est dommage de supprimer l'information apporte par le contenu de l'ellipse.

Je pense plutot a faire un fitting de surface. Mais je ne sais pas si on peut adapter les methodes "polynomiales" pour les surfaces...

----------


## mchk0123

Bien vu pour le fitting de surface.

Sinon, bah, je serais tent de dire que les lignes de coupes ne sont pas vraiment un problme insurmontable tant donn que pour une ellipse partielle ce seront des segments de droites si l'image est assez propre.

Du coup, plusieurs solutions pour les liminer :
- labelisation
- puis au choix : dtection par direction de gradient constante
- ou bien : seuillage sur les pics de la drive de la direction du gradient (dtection des sommets saillants)
- ou bien : une simple transforme de Hough

----------


## parp1

> ces ellipses ne sont en fait que des implants. Le but est ensuite de construire ces implants en *trois dimensions* en construisant des cylindres qui doivent etre construits exactement a l'endroit des implants sur le scanner.
> Donc mon idee est la suivante : 
> -identifier le centre d'un implant sur chaque image du scanner -> identifier le centre d'une ellipse.
> -tracer en trois dimensions la droite qui passent par tous les centres ou du  moins celle qui minimise la distance entre la droite et tous les points
> -construire mon cylindre autour de cette droite.


Vous allez dire que je suis born, mais pourquoi s'embetter a chercher le centre de ses ellipses.

Si il veut sortir la droite passant au mieux par le centre de ses ellipses je ne ferai pas comme cela...

Son image n'a pas besoin de traitement, un seuillage avec un seuil de 128 suffit a departager les groupes d'objets. (Fond et Prothese dentaire)

Si il veut la droite passant au mieu, un simple Squelette avec une ebarbage (le tout en 3D) suffira. 

Deuxio un seuillage sur le volume directement donnera la forme relle des prothese dentaires. Ne serait ce t il pas mieux que cette grossiere approximation avec un cylindre?

Pouquoi faire compliquer quand on peut faire simple?

----------


## pseudocode

> Deuxio un seuillage sur le volume directement donnera la forme relle des prothese dentaires. Ne serait ce t il pas mieux que cette grossiere approximation avec un cylindre?
> 
> Pouquoi faire compliquer quand on peut faire simple?


Oui, je suis assez d'accord. Plus on a d'informations, plus la modlisation est prcise. Si le but est de modeliser un volume 3D, auntant travailler sur des donnes 3D. 

L'ide de passer par la modelisation de surfaces 2D puis de les assembler peut sembler plus simple, mais je pense que, au final, ca va etre plus compliqu et moins fiable que l'approche globale 3D.

----------


## shindara

> Deuxio un seuillage sur le volume directement donnera la forme relle des prothese dentaires. Ne serait ce t il pas mieux que cette grossiere approximation avec un cylindre?


Non ce ne serait pas mieux, car je veux que mes protheses dentaires soient des cylindres, je ne veux pas qu'elles aient la forme qu'elles ont sur les scanners.

En tout cas je vois que le sujet dechaine les passions, tant mieux...

----------


## parp1

Dans ce cas tu recherches l'axe de ton cylindre c'est bien ca que tu veux faire.

Construire l'axe de ton cylindre point par point... via image par image?

Dans ce cas construit le volume et fait le squelette par amincissement. Avec Ebarbage si il le faut. tu devrais avoir l'axe de ton cylindre.

----------


## shindara

C'est exactement ca : 
- trouver le centre de chaque ellipse sur chaque image
- trouver la droite qui fit le mieux avec tous les centres en trois dimensions, qui sera donc l'axe de mon cylindre
- construire le cylindre autour de cet axe.

Donc je suis ouvert a n'importe quelle methode, mais je ne sais ce qu'est l'ebarbage... desole ::oops::

----------


## parp1

Est ce que tu sais ce qu'est un squelette?

En thorie le squelette est souvent tres propre, mais lorsqu'arrive la pratique, il peut y a voir des effets indsirable du a l'echantillonage, etc etc.

Et des petites branches parasites (par rapport a l'effet attendu) apparaissent.

L'ebarbage, ou ebarbulage (selon la litterature) consiste a supprimer toutes ces petites branches. Afin de retrouver un squelette proche de la thorie.

(J'espere que mes collegues vont approuver)

Ce que je ferais a ta place. Je sais je suis tres ttu.

Je crer le volume de prothses relles. 

J'extrait le squelette. que je nettoie. (selon l'axe Z tes prothese ressemble a un rectangle on est bien d'accord) Il est donc facile (je pense) d'extraire le squelette afin qu'il te serve de nuage de point. Un petit fitting et hop tu as la droite passant au mieux par ton squelette. 


La thorie en image...

----------


## pseudocode

> L'ebarbage, ou ebarbulage (selon la litterature) consiste a supprimer toutes ces petites branches. Afin de retrouver un squelette proche de la thorie.
> 
> (J'espere que mes collegues vont approuver)


Les "petites branches", comme tu dis, font partie du squelette thorique.

C'est juste que ces "petites branches" ne font pas partie du squelette "intuitif" form a partir des axes porteurs (plus grandes composantes principales)

----------


## mchk0123

Pour complter l'explication, le dbarbulage se fait typiquement sur image binaire  base de sries de filtres morphologiques obtenus par rotations et symtries.

Maintenant si tu est sous matlab, il y a peut-tre une fonction toute faite.

----------


## ToTo13

Bonjour,

pour Arnaud Le Troter, voil la page de ses publications :
http://www.lsis.org/~arnaud_le_trote...04701e0792c1b4
Contactes le directement pour avoir l'article.

Sinon je viens de trouver cela :
ftp://ftp.cordis.europa.eu/pub/ist/d...biber_etal.pdf

----------

