Discussion :

[Tloz Le Poivron]

Bonsoir à tous.

Petite introduction rapide mon problème:
Je suis étudiant en L3 d'informatique, et j'ai un devoir d'algo à faire. Ne vous étonnez pas donc si ce que je raconte fait académique ^^
Je dispose donc d'un tableau de taille n par n, et chaque case contient doit un 0, soit un 1.
Pour l'énoncé, un 1 représente du noir et le but est de trouver le plus grand carré possible dans la tache.
Heureusement pour faciliter les choses, la tache a la propriété que pour tout segment (horizontal ou vertical) dont les extrémités sont dans la tache, l'intégralité du segment est dans la tache.

On me demande dans un premier temps de donner un algorithme naïf pour résoudre le problème. Pour ca, pas de soucis, j'ai défini une fonction qui pour un point regarde si son voisin de droite, de dessous, et de dessous à droite sont noirs aussi. Autrement dit, si c'est un carré de côté 2 (par définition, tt point est un carré de côté 1). Si oui, j'appelle récursivement la fonction en testant avec 3, puis 4 et ainsi de suite, jusqu'à ce que ca renvoie faux, auquel cas, je renvoie la valeur de la taille d'avant.
Pour la façon "naïve" de faire, j'itère sur tout les points qui valent 1 et je leur applique la fonction.

Je dois trouver un algo plus efficace pour le faire, et je tourne en rond depuis deux jours. Je pense que je peux partir sans soucis avec ma fonction qui vérifie si le point est le coin supérieur gauche d'un carré que j'ai décrite au dessus, et que donc l'astuce pour gagner en efficacité, c'est la sélection des points sur lesquels je peux appliquer la fonction. Sauf que je ne trouve aucun critère permettant d'éliminer ou de privilégier des points, donc je viens misérablement quémander de l'aide ici
Sachez que si j'apprécie et je remercie d'avance toute aide, je suis quand même du genre curieux, touche à tout et que j'aime bien gratter pour trouver. Donc si plutôt que de m'apporter la solution sur un plateau d'argent vous pouviez me mettre sur la voie, je vous en serais reconnaissant.

Merci à ceux qui prendront le temps de m'aider.

[foetus]

Cela ressemble fortement à une matrice creuse très très simplifiée puisqu'il n'y a que des 1.

Une fois ta matrice (M) mise sur place, il faut faire un algo de type "glouton" [ou de type "coquille d'escargot" puisqu'on parle de vache ]
1. Je prends un élément (A) dans ma matrice (M), je le retire et je le mets dans un autre ensemble (l'algo peut-être sur place à voir)

Édit: C'est peut-être un truc plus subtil avec pour chaque point 3 états: "Non testé", "Testé", "Dans une tâche/ carré".
Et on prendrait que les points non testés.

2. À partir de cet élément, je recherche dans ma matrice creuse les 3 autres points

Code approximatif

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
void trouver_premier_carré( E(l, c) ) {
    // l: ligne, c: colonne
 
    // Test si E est le coin supérieur gauche
    Si (non sur le bord bas et droit) { tester_points((l, c+1), (l+1, c+1), (l+1, c));  }
 
    // Test si E est le coin supérieur droit
    Si (non sur le bord bas et gauche) { tester_points((l+1, c), (l+1, c-1), (l, c-1));  }
 
    // Test si E est le coin inférieur droit
    Si (non sur le bord haut et gauche) { tester_points((l, c-1), (l-1, c-1), (l-1, c));  }
 
    // Test si E est le coin inférieur gauche
    Si (non sur le bord haut et droit) { tester_points((l-1, c), (l-1, c-1), (l, c+1));  }
}

3. Je les trouve, il faut chercher les points autour des 4 premiers
4. Et ainsi de suite, tout en mémorisant le plus grand carré, et en récursif [<- ou pas : à voir].
Peut être garder une profondeur: profondeur 1 -> 3 points à chercher, 2 -> 12, 3 -> 20, ...

Peut-être un algo bête comme chou:

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 tester_contour(coin_supérieur_gauche(l1, c1), coin_supérieur_droit(l2, c2), coin_inférieur_gauche(l3, c3), coin_inférieur_droit(l4, c4)) {
    Si (possible) nouveau_coin_supérieur_gauche (l1-1, c1-1);
    Sinon retourner;
 
    Si (possible) nouveau_coin_supérieur_droit (l2-1, c2+1);
    Sinon retourner;
 
    Si (possible) nouveau_coin_inférieur_gauche (l3+1, c3-1);
    Sinon retourner;
 
    Si (possible) nouveau_coin_inférieur_droit (l4+1, c4+1);
    Sinon retourner;
 
    Tester les points sur la ligne entre nouveau_coin_supérieur_gauche et nouveau_coin_supérieur_droit, inclus;
    Tester les points sur la ligne entre nouveau_coin_inférieur_gauche et nouveau_coin_inférieur_droit, inclus;
 
    Tester les points sur la colonne entre nouveau_coin_supérieur_gauche et nouveau_coin_inférieur_gauche, exclus;
    Tester les points sur la colonne entre nouveau_coin_supérieur_droit et nouveau_coin_inférieur_droit, exclus;
}

2. Bis ou 4. Bis Il faut repartir de ta matrice creuse (M) et reprendre l'élément suivant de (A)
Fin lorsqu'il n'y a plus de points dans la matrice (M)

Édit: Ou alors on peut faire une fin d'algo plus subtile: on prend le nombre de points de la plus grande tâche trouvée à l'instant. Soit X.
On s'arrête, s'il nous reste moins de X points à tester: à voir, à tester, surtout si après on remet un coup de polish avec une méthode "try_retry"

Après il faut voir si les points trouvés pour faire un carré, il faut les extraire de (M) et/ ou alors les mettre dans une structure "Carré" et rajouter au début (étape 2) ou à la fin (étape 4) un test pour voir si l'intersection de 2 (ou X) tâches/ carrés ne contient pas une tâche/ carré plus grand(e): à moins que cela ne soit pas nécessaire.

Peut-être un algo bête comme chou, qui éviterait peut-être de ne pas lancer l'algo sur les points qui sont dans une tâche/ carré [voir l'état pour chaque point]:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
void try_retry(liste: liste des tâches/ carrés trouvé(e)s) {
    Pour chaque tâche/ carré trouvé(e) dans liste {
        Si un des 4 coins appartient à une autre tâche {
            relancer l'algo à partir de ce coin;
        }
    }
}

[Graffito]

Un début de solution consisterait à associer à chaque point la taille du carré noir dont il serait le sommet haut/gauche.

Pour calculer cette valeur, on fait une première passe sur toutes les colonnes de gauche à droite, ce qui permet en partant du bas de la colonne de trouver une taille maximale V(i,j) du carré associé à chaque point de la colonne en fonction des points situés en dessous.

On fait une deuxième passe sur toutes les lignes de bas en haut, ce qui permet en partant de la gauche de la ligne de trouver une taille maximale H(i,j) du carré associé à chaque point de la colonne en fonction des points situés à droite.

Une troisième passe pour calculer la taille réelle T(i,j) des carrés associés à chaque point se ferait ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
for (int i=n-1;i>=0;i++) // de bas en haut
   for (int j=n-1;j>=0;j++) // de droite à gauche
     if (i==n-1 || j==n-1) T(i,j)=P(i,j) ; // P(i,j) = valeurs de la matrice en entée (0 pour blanc, 1 pour noir) 
     else T(i,j)=Min(V(i,j) , H(i,j), T(i,j+1)+1 , T(i+1,j)+1, T(i+1,j+1)+1 ;

La taille T(i,j) de la tache est la plus petite de ces valeurs :
- le nombre de points noirs consécutifs au-dessous (y compris le point lui-même),
- le nombre de points noirs consécutifs à gauche (y compris le point lui-même),
- la taille de la tache associée immédiatement au dessous +1,
- la taille de la tache associée immédiatement à droite +1 ,
- la taille de la tache associée au point immédiatement en diagonale au dessous à droite +1 ;

Dans cette passe, il faudra évidement comparer T(i,j) à la plus grande taille trouvée dans l'itération pour garder la position de la + grande tache.

[Graffito]

Après reflexion les 2 premières passes ne servent à rien :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
for (int i=n-1;i>=0;i--) // de bas en haut
   for (int j=n-1;j>=0;j--) // de droite à gauche
     if (i==n-1 || j==n-1 || P(i,j)==0) T(i,j)=P(i,j) ; // P(i,j) = valeurs de la matrice en entée (0 pour blanc, 1 pour noir) 
     else T(i,j)=Min(T(i,j+1)+1 , T(i+1,j)+1, T(i+1,j+1)+1 ;

[Tloz Le Poivron]

Merci beaucoup pour votre aide à tout les deux, je teste ca dans l'après midi, et je vous dit ce que ca a donné.
Et pas de soucis si l'algo n'est pas en place, on est plus orienté complexité temporelle que spatiale.

Merci encore!

[gpcbitnik38]

ton problème me fait penser à un problème simple de traitement d'image

d'abord un petit point vocabulaire

Heureusement pour faciliter les choses, la tache a la propriété que pour tout segment (horizontal ou vertical) dont les extrémités sont dans la tache, l'intégralité du segment est dans la tache

ça c'est la définition de la convexité.
et j'aurais besoin de savoir ce que tu appel un carré ^^

.
Pour ca, pas de soucis, j'ai défini une fonction qui pour un point regarde si son voisin de droite, de dessous, et de dessous à droite sont noirs aussi

pour moi ça c'est la définition d'une boule discrète de rayon 1 avec un voisinage V4. mais bon passons ^^


tes taches sont convexes tu n'as donc pas besoin de passer par tes points a l'intérieur de ta tache il suffit de connaitre son contour pour la caractérisée. tu passera donc ton algorithme sur beaucoup moins de point.
un point de contour est définis par sa valeur (1) , le fait que au moins un de ses voisin vaut 0 et que un de ses voisins vaut 1. tu arrête ta récursivité quand tu reviens au point de départ

EDIT : j'ai dit une betise ^^ je corrige

une fois que tu as le contour de toute tes taches
pour chaque point du contour tu cherche la largeur et la longueur de ta tache ( intersection entre ton contour et les droites verticales et horizontales passant par ton point) (tu peux limiter la recherche a la parti supérieur de te tache pour éviter les doublons) et le coté du carré qui pourra rentré dans ta tache sera le minimum entre ta longueur et ta largeur du point qui aura le minimum entre ces deux le plus haut. (j'espere que je me fait comprendre ^^)


attention cette méthode n'est valable que si tes carrés on la forme que tu décrits sinon il faut changer la dernière partie

je t'invite a regarder du coter de la morpho math pour faire des choses un peu plus poussé ne serait-ce qu'avec les opérateurs d'érosion et de dilation tu peux déjà faire des chose sympa