IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Créer un algorithme de "reconnaissance d'image"


Sujet :

Algorithmes et structures de données

  1. #1
    Futur Membre du Club
    Femme Profil pro
    Étudiant
    Inscrit en
    Janvier 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 27
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2019
    Messages : 8
    Points : 6
    Points
    6
    Par défaut Créer un algorithme de "reconnaissance d'image"
    Bonjour, j'ai commencé depuis peu à programmer sur python et je dois faire un programme de plusieurs centaines de lignes sur ce thème :

    J'ai trois pièces, un carré, un petit triangle et gros triangle dont on connait les dimensions. Et j'ai une image noire formée de ces éléments et à l'aide d'un programme je dois retrouver les emplacements des 3 pièces comme montré ci-dessous. Python doit montrer l'image en couleur à la fin

    Nom : Sans titre.png
Affichages : 1566
Taille : 3,7 Ko

    Je peux tourner les pièces uniquement de 90°

    Comme on connait les dimensions des pièces je les ai créées sous forme de tableau. Je pensais utiliser des tableaux, mais je ne sais pas quelle stratégie adoptée. Il faut que le programme soit efficace. Je pensais utiliser les angles ou les contours de la forme noir pour déterminer ou est chaque pièce, mais je n'y arrive pas.

    Je vous remercie par avance.

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 084
    Points
    16 084
    Par défaut
    Bonjour,

    Le problème posé s'appelle résoudre un tangram. Vous trouverez plein d'informations sur le web, y compris des algorithmes et du code (i.e. "tangram solver" en anglais).

    Généralement, il y a deux types d'approche:
    * partir des pièces et essayer tous les assemblages possibles jusqu'à trouver la silhouette.
    * partir de la silhouette et essayer tous les découpages possibles jusqu'à trouver les pièces.

    Vos contraintes étant très restrictives (3 pièces dont une grande, rotation à 90° uniquement), je suggère la première approche.

  3. #3
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 152
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 152
    Points : 9 620
    Points
    9 620
    Par défaut
    Ici on a 2 problèmes consécutifs ;
    - 1er problème : (P1) à partir d'une image en format PNG ou assimilé, et sachant que la forme noire est de type polygone, trouver rapidement les n sommets de ce polygone.
    - 2ème problème (P2) : connaissant un polygone, et connaissant les 3 formes constituantes de ce polygone, résoudre le problème du Tangram.
    Pour chacun de ces 2 problèmes, il doit y avoir des solutions connues. (je ne les connais pas).

    En temps de traitement, le 1er problème me paraît BEAUCOUP plus coûteux que le 2ème.
    Et ici le 1er problème doit certainement pouvoir être simplifié par le fait qu'on connaît les 3 formes triangle-triangle-carré. Idéalement, il faudrait donc résoudre les 2 problèmes en même temps. (problème P3)

    Quel est ton objectif : résoudre les problèmes P1 et P2 successivement, ou résoudre le problème P3 ?

  4. #4
    Futur Membre du Club
    Femme Profil pro
    Étudiant
    Inscrit en
    Janvier 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 27
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2019
    Messages : 8
    Points : 6
    Points
    6
    Par défaut
    Bonsoir, merci beaucoup pour vos réponses et votre aide.

    Mon objectif est de résoudre le problème de manière la moins coûteuse possible. Je pense que votre problème P3 serait celui qui répond le mieux à cet objectif.

    Il est précisé à la fin de mon sujet qu'il est mieux de trouver une approche qui fonctionnerait aussi pour une forme plus complexe. Je pense que cette phrase a été ajoutée pour éviter que nous fassions la première méthode proposée par pseudocode (je vous remercie au passage) qui est : "partir des pièces et essayer tous les assemblages possibles jusqu'à trouver la silhouette".

    Je trouve bien le fait de partir de la silhouette mais je ne vois pas comment faire.

  5. #5
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 084
    Points
    16 084
    Par défaut
    Citation Envoyé par Âne-ais Voir le message
    Je trouve bien le fait de partir de la silhouette mais je ne vois pas comment faire.
    Le procédé s'appelle la dissection géométrique et tu trouveras tout un tas de littérature sur le web, y compris des applications sur les tangram (i.e. "Geometric Dissection Puzzles").

    L'idée c'est de découper la forme en petits éléments: soit par "tiling" (=maillage régulier), soit par triangulation (des coups de ciseaux).
    Une fois le découpage effectué, on tente de reconstituer la forme d'une pièce en sélectionnant certains petits éléments.

  6. #6
    Futur Membre du Club
    Femme Profil pro
    Étudiant
    Inscrit en
    Janvier 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 27
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2019
    Messages : 8
    Points : 6
    Points
    6
    Par défaut
    Merci beaucoup pour cette information, j'ai trouvé de nombreuses choses mais je n'ai pas trouvé de renseignement sur la démarche/stratégie à adopter pour résoudre mon problème.

  7. #7
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 450
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 450
    Points : 5 880
    Points
    5 880
    Par défaut
    salut

    la stategie est de trouver les points remarquables

    donc les arrêtes ,changement de direction sur le contour de ta silhouette

    ensuite tu trace de droite qui passe par ces point remarquable
    un fois ces droites tracé tu efface toute celle qui se trouve a l’extérieur de la silhouette
    il te reste donc plus que des segment de droite qui définisse divers forme au sein de cette silhouette
    tu n'a plus qu'a comparer tes formes avec les les formes définis au sein de ton tracé

  8. #8
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 084
    Points
    16 084
    Par défaut
    Citation Envoyé par anapurna Voir le message
    salut

    la stategie est de trouver les points remarquables

    donc les arrêtes ,changement de direction sur le contour de ta silhouette

    ensuite tu trace de droite qui passe par ces point remarquable
    un fois ces droites tracé tu efface toute celle qui se trouve a l’extérieur de la silhouette
    il te reste donc plus que des segment de droite qui définisse divers forme au sein de cette silhouette
    tu n'a plus qu'a comparer test formes avec les les forme définis au sein de ton tracé
    C'est malheureusement pas si simple.
    Exemple avec la figure de base du Tangram: le carré.



    la silhouette est un grand carré => 4 points d'intérêts et 4 cotés.
    Pas évident de faire un découpage interne qui amène à la solution.

    (Resoudre un tangram est un problème NP-Hard).

  9. #9
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 450
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 450
    Points : 5 880
    Points
    5 880
    Par défaut
    salut

    pour ton exemple il existe plus d'une solution

    il faut donc affiner notre première solution par une triangulation
    ou la taille des triangles correspond à la taille du plus petit triangle mis à notre disposition

  10. #10
    Futur Membre du Club
    Femme Profil pro
    Étudiant
    Inscrit en
    Janvier 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 27
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2019
    Messages : 8
    Points : 6
    Points
    6
    Par défaut
    Merci pour vos réponses, je vais faire comme énoncé par anapurna.
    Mais petite question comment trouver les points colorés en rouges?

    Nom : Sans titre.png
Affichages : 1340
Taille : 3,3 Ko

  11. #11
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 152
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 152
    Points : 9 620
    Points
    9 620
    Par défaut
    Tu as les points jaunes. C'est l'étape 1.

    - Les points rouges, tu peux les déterminer en prolongeant les 2 traits verticaux. Mais ce ne serait pas une bonne méthode. Ici, on sait qu'il faut effectivement prolonger les 2 traits verticaux, parce qu'on connaît par avance la solution, mais si nos 3 formes étaient 3 trapèzes au lieu de 2 triangles et un carré, alors l'emplacement des points rouges serait différent.

    En fait, il faut probablement prendre les 3 formes connues, en commençant pas la plus grande (le grand triangle). Et il faut chercher à placer cette forme quelque part. Cette forme, elle a un côté qui est très long et qui est en diagonale ( à 45% par rapport aux 2 axes). Si on fait tourner cette pièce de 90°, la longueur en question reste en diagonale. Et dans notre forme noire, une diagonale aussi longue, elle est forcément sur la gauche du dessin. Du coup, on a placé notre grand triangle. Et on a notre 1er point rouge...
    Et on continue, en essayant de placer le carré, ou le 2ème triangle, dans l'espace restant.

    Ceci dit, parmi les points jaunes, on peut peut-être faire 2 groupes. Les angles entrants (les 4 qui forment l'enveloppe convexe), et les angles sortants (les 2 autres angles, qui délimitent la limite haute du carré). Peut-être que cette distinction peut aider dans la suite du traitement.

  12. #12
    Futur Membre du Club
    Femme Profil pro
    Étudiant
    Inscrit en
    Janvier 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 27
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2019
    Messages : 8
    Points : 6
    Points
    6
    Par défaut
    Merci beaucoup pour votre aide, j'ai une autre question portant plutôt sur un aspect pratique de la réalisation du programme me conseilleriez vous de créer mes pièces de départ avec laquelle de ses méthodes (ou aucune):

    Créer un tableau, exemple avec un carré noir

    Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    blanc,noir = 0,1
    for x in range(5,29):
        ymax = round(min(29+(x-4),29+(28-x)))
        for y in range(29,ymax):
            tab[x,y] = noir

    On l'affiche et cela donne ceci :
    Nom : Figure_2.png
Affichages : 1372
Taille : 7,5 Ko







    Ou commencer avec des formes créées comme cela :

    Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    fill([0,60,30,0],[0,0,30,0],'r')
    axis('equal')
    axis(visible='off') # a revoir
    plt.axis
    show()

    et donc obtenir un triangle plus lisse :

    Nom : Figure_3.png
Affichages : 1408
Taille : 8,0 Ko




    Merci beaucoup encore

  13. #13
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 084
    Points
    16 084
    Par défaut
    L'angle saillant (=inférieur à 180°) d'une silhouette est nécessairement décomposable en un ou plusieurs angles saillants correspondant aux pièces.

    Nom : Image6.jpg
Affichages : 1363
Taille : 9,9 Ko

    => le "sommet+bord adjacent" d'un angle saillant d'une silhouette correspond au "sommet+bord adjacent" d'une des pièces.
    C'est un très bon point de départ pour décomposer un tangram.

    Nom : Image5.jpg
Affichages : 1316
Taille : 5,4 Ko

  14. #14
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 450
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 450
    Points : 5 880
    Points
    5 880
    Par défaut
    salut

    Citation Envoyé par tbc92 Voir le message
    Tu as les points jaunes. C'est l'étape 1.

    - Les points rouges, tu peux les déterminer en prolongeant les 2 traits verticaux. Mais ce ne serait pas une bonne méthode. Ici, on sait qu'il faut effectivement prolonger les 2 traits verticaux, parce qu'on connaît par avance la solution, mais si nos 3 formes étaient 3 trapèzes au lieu de 2 triangles et un carré, alors l'emplacement des points rouges serait différent.

    En fait, il faut probablement prendre les 3 formes connues, en commençant pas la plus grande (le grand triangle). Et il faut chercher à placer cette forme quelque part. Cette forme, elle a un côté qui est très long et qui est en diagonale ( à 45% par rapport aux 2 axes). Si on fait tourner cette pièce de 90°, la longueur en question reste en diagonale. Et dans notre forme noire, une diagonale aussi longue, elle est forcément sur la gauche du dessin. Du coup, on a placé notre grand triangle. Et on a notre 1er point rouge...
    Et on continue, en essayant de placer le carré, ou le 2ème triangle, dans l'espace restant.

    Ceci dit, parmi les points jaunes, on peut peut-être faire 2 groupes. Les angles entrants (les 4 qui forment l'enveloppe convexe), et les angles sortants (les 2 autres angles, qui délimitent la limite haute du carré). Peut-être que cette distinction peut aider dans la suite du traitement.

    bin si c'est la bonne méthode du fait même qu'il doit faire une triangulation de chaque éléments
    ensuite il faut effectivement commencer par prendre les plus grandes formes afin de les placer dans l'ordre
    pour connaitre la plus grande il faut calculer l'air de chaque figure disponible.

    nous savons que pour le tangram le plus petit triangle est composant de toutes les autres pieces donc
    la triangulation nous permettra de determiner les position possible a realiser

  15. #15
    Futur Membre du Club
    Femme Profil pro
    Étudiant
    Inscrit en
    Janvier 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 27
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2019
    Messages : 8
    Points : 6
    Points
    6
    Par défaut
    Merci pour vos réponses, donc si j'ai bien compris, je cherche à prolonger les arrêtes (ou traits des bords) puis je teste la plus grande pièce? Et du coup que me conseillez-vous pour réaliser mes pièces entre les deux techniques que j'ai énoncées plus bas?

    Merci beaucoup

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algorithme de reconnaissance d'images dans une photo
    Par Armel88 dans le forum Android
    Réponses: 0
    Dernier message: 10/06/2015, 10h18
  2. Réponses: 3
    Dernier message: 17/08/2006, 12h30
  3. Algorithme de redressement d'une image "incurvée"
    Par FidoDido® dans le forum Traitement d'images
    Réponses: 1
    Dernier message: 06/06/2006, 16h17
  4. Réponses: 4
    Dernier message: 04/10/2005, 01h15
  5. Recherche d'un logiciel pour créer des algorithmes
    Par Seb003 dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 02/10/2005, 18h46

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo