Discussion: Algorithme de forme

  1. #1
    Candidat au Club
    Homme Profil pro
    Responsable sécurité
    Inscrit en
    février 2014
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Responsable sécurité

    Informations forums :
    Inscription : février 2014
    Messages : 7
    Points : 3
    Points
    3

    Par défaut Algorithme de forme

    Bonjour,

    J'ai un petit problème, j'ai un tableau de string contenant n*m cases (donc un tableau en 2D). De plus, une case peut avoir deux états :
    Les cases vides qui sont représentés par un espace.
    Les cases qui représente un "pixel noir" et qui sont représentés par un "X"

    L'idée est que j'ai implémenté l'algorithme de flood_fill qui consite a remplir une forme dans le tableau en lui donnant les coordonées d'une case vide (représenté par un espace) :
    Pour mieux comprendre, voilà un exemple avec "flood_fill(array, 1, 2);"
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    Avant : 
    ----------
    |  XXXXXXX|
    | X      X|
    |X       X|
    |XXXXX   X|
    |    X   X|
    |    XXX X|
    |       XX|
    |         |
    |         |
    ----------
    
    Apres : 
    
    ----------
    |  XXXXXXX|
    | XZZZZZZX|
    |XZZZZZZZX|
    |XXXXXZZZX|
    |    XZZZX|
    |    XXXZX|
    |       XX|
    |         |
    |         |
    ----------
    Maintenant moi, mon problème c'est de trouver automatiquement ce "1,2". Du coup je suis partie du principe que j'allais re-utiliser flood_fill et que si je tombais sur les bors de mon tableau, donc i = 0 ou j = 0 et que la case n'était pas un X, ça veut dire que je suis en dehors d'une forme non? Et si c'est le cas, je mets une variable z (par référence) à 0 et je "return;" cela donne :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void check(std::string array[9][9], int i, int j, int &z)
    {
      if ((i == 0 || j == 0 || i == 8 || j == 8 ) && array[i][j] != "X")
      {
       std::cout << "Here" << std::endl; // Ca c'est mon print de debug pour le bug que j'explique après
       z = 0;
       return;
      }
      if (array[i][j] == " ")
      {
        array[i][j] = "Z";
        z++;
        check(array, i+1, j, z);
        check(array, i-1, j, z);
        check(array, i, j+1, z);
        check(array, i, j-1, z);
      }
    }
    L'idée est donc que je parcours mon tableau en lancant check(array, i, j, z) et si j'ai (z != 0) alors je lance flood_fill sur i et j et tout devrait marcher correctement!
    Sauf que dans certain cas ça marche pas du tout.. Par exemple sur "check(array, 1, 3, 0);" et en modifiant mon tableau d'origine j'ai :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    ----------
    |  XXXXXXX|
    | X      X|
    |X       X|
    |        X|
    |    X   X|
    |    XXX X|
    |       XX|
    |         |
    |         |
    ----------
    
    Here
    Here
    Here
    Here
    Here
    Here
    Here
    Here
    Here
    Here
    Here
    Here
    Here
    
    ----------
    |  XXXXXXX|
    | XZZZZZZX|
    |XZZZZZZZX|
    | ZZZZZZZX|
    | ZZZXZZZX|
    | ZZZXXXZX|
    | ZZZZZZXX|
    | ZZZZZZZ |
    |         |
    ----------
    Du coup, le problème c'est que pour debugger un algo reccursif comme ça c'est ultra chaud... du coup je sèche un peu.
    Si quelqu'un a une idée ou des questions n'hésitez pas :-). Ou si quelqu'un a un meilleur algorithme pour trouver une forme je suis preneur!

    Merci d'avance

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 030
    Points : 15 585
    Points
    15 585

    Par défaut

    Je n'ai pas compris le rapport entre le besoin (trouver automatiquement un point de départ ?) et le problème (remplissage incorrect).

    Tout ce que je peux dire, c'est que le seul moyen de sortir d'un appel de check(), c'est de passer par ce block:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    std::cout << "Here" << std::endl; // Ca c'est mon print de debug pour le bug que j'explique après
    z = 0;
    return;
    C'est à dire qu'à la sortie de l'appel de check(), on a forcément z=0

    Du coup, le bloc de code:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    array[i][j] = "Z";
    z++;
    check(array, i+1, j, z);
    check(array, i-1, j, z);
    check(array, i, j+1, z);
    check(array, i, j-1, z);
    est équivalent à:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    array[i][j] = "Z";
    z++;
    check(array, i+1, j, z); // --->  quand on sort de cet appel, forcément z=0
    check(array, i-1, j, 0);
    check(array, i, j+1, 0);
    check(array, i, j-1, 0);
    Du coup, qu'est ce que cette variable "z" est censée représenter pour toi ?

    si quelqu'un a un meilleur algorithme pour trouver une forme je suis preneur!
    Les algos de type "scanline" sont beaucoup moins complexes (en terme de mémoire et de temps), et plus facile a débugguer car il n'y a pas d'appels récursifs.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Candidat au Club
    Homme Profil pro
    Responsable sécurité
    Inscrit en
    février 2014
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Responsable sécurité

    Informations forums :
    Inscription : février 2014
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    Merci de ta réponse pseudocode. Effectivement j'ai oublié de préciser quelque chose, ici check remplit mon tableau avec des Z ok ? Et l'idée c'est que si z est différent de 0 alors il est censé avoir trouvé une forme (dans l'idée). Du coup ce que je faisais c'est une double boucle pour parcourir mon tableau (qui est elle meme a l'intérieur de ma double boucle) et qui ensuite va dire si c'est Z ok alors tu le remplaces par un " ".
    Parce que l'algo de check ecris dans mon tableau pour faire les tests et j'ai pas pu annuler les modifications que la fonction check faisaient.
    En code ça donne :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
      for (int i = 0; i < 9; i++)
      {
        for (int j = 0; j < 9; j++)
        {
          check(array, i, j, z);  // du coup je le lance sur la case, et vu que z est une référence (déclaré plus haut) alors la valeur de z va se modifier
          for (int c = 0; c < 9; c++)
          {
            for (int y = 0; y < 9; y++)
            {
              if (array[c][y] == "Z")
              {
                array[c][y] = " "; // l'algo de check écrit des Z un peu partout pour faire ses tests alors je remet mon tableau comme avant check
              }
            }
          }
          if (z != 0)
          {
            floodfill(array, i, j); // si (z != 0) alors en théorie on a trouvé une forme, du coup on lance flood_fill dessus
          }
        }
      }
    Sauf que comme je l'ai dit, le problème c'est que pour certain cas comme (1,3) check me retourne une valeur supérieur a 0 alors qu'il ne devrait pas vu qu'il finit sur des bords.
    Dailleurs je peux pas changer le 0 par z puisque z est une référence et donc dans l'appel de check je dois mettre une référence.

    Du coup si tu as des idées de comment fixer l'algorithme ou des meilleurs je suis preneur. Pendant ce temps je vais me renseigner sur les algos de scanlines.


    Merci d'avance

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 030
    Points : 15 585
    Points
    15 585

    Par défaut

    Citation Envoyé par Casshern123 Voir le message
    Effectivement j'ai oublié de préciser quelque chose, ici check remplit mon tableau avec des Z ok ? Et l'idée c'est que si z est différent de 0 alors il est censé avoir trouvé une forme (dans l'idée). Du coup ce que je faisais c'est une double boucle pour parcourir mon tableau (qui est elle meme a l'intérieur de ma double boucle) et qui ensuite va dire si c'est Z ok alors tu le remplaces par un " ".
    Ah... je comprends mieux.
    En gros tu vas faire deux fois le travail: ton premier parcours pour trouver les formes, et le second parcours pour les remplir.

    Bon, hum... comment dire. C'est pas vraiment optimal en plus d'être assez compliqué.

    J'avais posté il y a loooongtemps une contribution qui s'appelle "Etiquettage de composantes connexes".
    Ca utilise l'algo union-find et ca permet de remplir toutes les formes de ton tableau avec une valeur différente pour chaque forme.

    Est-ce que c'est ca que tu veux ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Candidat au Club
    Homme Profil pro
    Responsable sécurité
    Inscrit en
    février 2014
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Responsable sécurité

    Informations forums :
    Inscription : février 2014
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    Ouais, tu as parfaitement compris ce que je souhaitais faire !
    Du coup, oui l'idee c'est de "colorier" chaque forme de mon tableau. Quand je dis colorier je parle bien entendu de mettre un "O" a dans les cases vides entourés d'un "X" par exemple.
    Du coup j'ai regardé ton algo mais la pour l'instant je vois pas trop comment l'adapter dans mon cas

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 030
    Points : 15 585
    Points
    15 585

    Par défaut

    L'algo en question te crée un deuxième tableau qui est la carte des composantes connexes.
    Pour chaque case du tableau d'origine, la case correspondante dans la carte te donne le numero de la composante (=l'identifiant de la forme).

    Dans ton cas, l'idée serait de

    1. étendre ton tableau d'origine avec une ligne/colonne supplémentaire en haut/bas/gauche/droite.
    Cela permet d'être certain que la forme ne touche pas le bord du tableau. La composante associée a la case (0,0) sera donc le "fond" de l'image.

    2. Créer la carte des composantes connexes

    3. Conserver les composantes qui ne sont ni le "fond" ni un "contour" (les cases "x" dans ton tableau de départ)

                 +-----------+      +-----------+  +-----------+
    +---------+  |           |      |00000000000|  |           |
    |  XXXXXXX|  |   XXXXXXX |      |00011111110|  |           |
    | X      X|  |  X      X |      |00122222210|  |   222222  |
    |X       X|  | X       X |      |01222222210|  |  2222222  |
    |XXXXX   X|  | XXXXX   X | ---> |01111122210|  |      222  |
    |    X   X|  |     X   X |      |00000122210|  |      222  |
    |    XXX X|  |     XXX X |      |00000111210|  |        2  |
    |       XX|  |        XX |      |00000000110|  |           |
    |         |  |           |      |00000000000|  |           |
    |         |  |           |      |00000000000|  |           |
    +---------+  +-----------+      +-----------+  +-----------+
       source     src extended        carte des     sans fond et
                                      c.connexes    sans contour
    
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Candidat au Club
    Homme Profil pro
    Responsable sécurité
    Inscrit en
    février 2014
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Responsable sécurité

    Informations forums :
    Inscription : février 2014
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    Heu.. Ouais c'est pas encore trop clair dans ma tête mais disons...

    Parce que là, l'algo fait quoi? Il trouve une forme et la remplit tout seul? Transformer la carte en 1,2 et 0 ok, mais pour dire que y a une forme avec des 1 c'est la tout le probleme. De trouver une forme

    Je vois quand même pas comment l'algorithme se comporte quand il n y a pas de forme, c'est a dire des X un peu random mais qui se referme pas.

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 030
    Points : 15 585
    Points
    15 585

    Par défaut

    Parce que là, l'algo fait quoi? Il trouve une forme et la remplit tout seul?
    L'algo te crée le tableau "carte des c.connexes" à partir du tableau "src extended"

    mais pour dire que y a une forme avec des 1 c'est la tout le probleme. De trouver une forme
    la composante 0 n'est pas une forme, car c'est la composante associée à un bord de ton image (et on a étendu le tableau pour être certain que les bords ne contiennent pas de forme).

    Les autres composantes (1,2,..) sont donc associées soit à une case "x", soit a l'intérieur d'une forme.
    => il suffit de regarder dans le tableau de départ pour savoir dans quel cas on est.

    Je vois quand même pas comment l'algorithme se comporte quand il n y a pas de forme, c'est a dire des X un peu random mais qui se referme pas.
    Tu auras des 0 partout, sauf pour les cases "x" ou tu auras le numéro de la composante (=point X isolé, ou ligne de X, ou bloc de X).

    +-----------+      +-----------+
    |           |      |00000000000|
    |    X    X |      |00001000020|
    |  X      X |      |00300000020|
    |         X |      |00000000020|
    | XXXXX   X | ---> |04444400020|
    | XXXXX   X |      |04444400020|
    |         X |      |00000000020|
    |         X |      |00000000020|
    |           |      |00000000000|
    |           |      |00000000000|
    +-----------+      +-----------+
     src extended        c.connexes 
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Candidat au Club
    Homme Profil pro
    Responsable sécurité
    Inscrit en
    février 2014
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Responsable sécurité

    Informations forums :
    Inscription : février 2014
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    Merci de ta réponse c'est un peu plus clair. Mais ce que je pige toujours pas, c'est comment avec ça je trouve une forme. Parce qu'ok passait de src a la carte des c. connexes, je vois bien mais ensuite ?
    Si tu mets ça a mon problème initial je pige pas. Ca va transformer ma map ok, mais en quoi ça aide a trouver et colorier une forme? Désolé je suis un peu lent a saisir là .. :p

    Edit : ok après avoir bien relu et tout ça, j'ai compris en effet! Mais maintenant comment je fais pour adapter ton algortihme sur un tableau et non une image?

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 030
    Points : 15 585
    Points
    15 585

    Par défaut

    Citation Envoyé par Casshern123 Voir le message
    Mais maintenant comment je fais pour adapter ton algortihme sur un tableau et non une image?
    La contribution parle d'image, mais l'algorithme traite en réalité des tableaux.

    Dans l'implémentation en C:

    * Le tableau en entrée (image) est un tableau 2D : int image[456][123] = /* ... */;

    * La tableau en sortie (CCroots) est un tableau 1D: long *CCroots;
    => pour y accéder avec des coordonées 2D: long numero_composante = CCroots[x+y*W];

    ou alors un recast du genre:
    long (*composantes)[123] = (long (*)[123]) CCroots;
    long numero_composante = composantes[x][y];
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  11. #11
    Candidat au Club
    Homme Profil pro
    Responsable sécurité
    Inscrit en
    février 2014
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Responsable sécurité

    Informations forums :
    Inscription : février 2014
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    Ah oui effectivement, mon erreur c'était que je pensais que ça modifiait mon tableau directement !
    Ca a l'air de marcher pas trop mal !
    Merci ! Juste tu sais ou je pourrai trouver une explication de l'algo ? Parce que là je l'ai lancé en regardant vite fait. Plus t'as de lien, plus ça me va !

    Parce que j'aimerai bien le faire marcher aussi en "diagonale" si c'est possible, du style
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    0 0 0 0 0 0 0 0 0 
    0 1 1 1 1 0 0 0 0 
    0 1 0 0 1 0 0 0 0 
    0 1 0 0 0 1 1 0 0 
    0 1 0 0 0 0 1 0 0 
    0 1 0 0 0 0 1 0 0 
    0 0 1 1 1 1 1 0 0 
    0 0 0 0 0 0 0 0 0 
    0 0 0 0 0 0 0 0 0
    Dailleurs, dans CCinit, t'as un "long i" qui est pas utilisé.
    Et dailleurs, y a un moyende pouvoir le faire sans extend le tableau en hauteur et largeur ? (juste voir si une opti est possible)

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 030
    Points : 15 585
    Points
    15 585

    Par défaut

    Citation Envoyé par Casshern123 Voir le message
    Ah oui effectivement, mon erreur c'était que je pensais que ça modifiait mon tableau directement !
    Ca a l'air de marcher pas trop mal !
    Merci ! Juste tu sais ou je pourrai trouver une explication de l'algo ? Parce que là je l'ai lancé en regardant vite fait. Plus t'as de lien, plus ça me va !
    Regarde le message #6 dans la contribution.

    Parce que j'aimerai bien le faire marcher aussi en "diagonale" si c'est possible, du style
    L'algo proposé fusionne les composantes reliées "en diagonale".
    Pour annuler ce comportement, il faut supprimer les tests avec les pixels en diagonale (NORD_OUEST, et NORD_EST)

    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
     
    ...
     
    // test la liaison avec le pixel OUEST
    if ( (x>0) && (image[pos-1]==image[pos]) )
    	root = CCunion( CCfind(pos-1) , root);
     
    // test la liaison avec le pixel NORD_OUEST
    if ( (x>0 && y>0) && (image[pos-1-W]==image[pos]) )
    	root = CCunion( CCfind(pos-1-W) , root);
     
    // test la liaison avec le pixel NORD
    if ( (y>0) && (image[pos-W]==image[pos]) )
    	root = CCunion( CCfind(pos-W) , root);
     
    // test la liaison avec le pixel NORD_EST
    if ( (x<(W-1) && y>0) && (image[pos+1-W]==image[pos]) )
    	root = CCunion( CCfind(pos+1-W) , root);
     
    ...

    Dailleurs, dans CCinit, t'as un "long i" qui est pas utilisé.
    Exact, c'est une erreur. Ca fait 8 ans que c'est comme ca


    Et dailleurs, y a un moyende pouvoir le faire sans extend le tableau en hauteur et largeur ? (juste voir si une opti est possible)
    Tu peux, mais sans étendre le tableau tu peux avoir plusieurs composantes de "fond" si ta forme touche 2 bords.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  13. #13
    Candidat au Club
    Homme Profil pro
    Responsable sécurité
    Inscrit en
    février 2014
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Responsable sécurité

    Informations forums :
    Inscription : février 2014
    Messages : 7
    Points : 3
    Points
    3

    Par défaut

    Merci de ta réponse, j'ai pu l'implémenter et je dois admettre que ça marche plutot bien :-)!

    Je passe ça en résolu !

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

Discussions similaires

  1. Algorithme reconstruction de forme 3D
    Par firespirit dans le forum Traitement d'images
    Réponses: 9
    Dernier message: 03/12/2009, 09h42
  2. Algorithme pour redimensionnement de me form vs composantes
    Par burnx22 dans le forum Mathématiques
    Réponses: 3
    Dernier message: 26/02/2009, 01h27
  3. Réponses: 1
    Dernier message: 14/05/2008, 17h31
  4. [Image] Algorithme pour déterminer une forme continue
    Par wizzmasta dans le forum Général Algorithmique
    Réponses: 1
    Dernier message: 25/04/2006, 15h56
  5. algorithme : en forme sql
    Par lou87 dans le forum Général Algorithmique
    Réponses: 8
    Dernier message: 05/04/2006, 09h24

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