Discussion :

[Pommecannelle]

Bonjours à tous !

Je viens vous exposer mon problème : je me suis lancer dans un projet qui est de récupérer le tracé des routes à partir d'image satellite. Je me retrouve aujourd'hui à devoir faire un script python qui récupère une image en noir et blanc (je l'ai binarisé) et détecte chaque composante noire afin de les compter. Ceci va me permettre de réduire les impuretés de mon image. Dans le code suivant, je charge une image de test, j'ai juste fait des formes noires sur Paint. Pour cela, j'ai fait le code suivant :

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
import numpy as np
import cv2
import sys
sys.setrecursionlimit(35000)
 
img = cv2.imread('img_test.png') #on recupere l’image couleur
(height,width,channels)=img.shape 
print('Taille de l\'image couleur: {}x{}x{}'.format(height,width,channels)) 
print('Min={} et Max={}'.format(np.min(img),np.max(img)))  
 
imgB=np.zeros((height,width),dtype=np.uint8)    #Creer une matrice de taille height*width pour le bleu, pour le moment remplie que de 0
imgG=np.zeros((height,width),dtype=np.uint8)    #Pour le vert
imgR=np.zeros((height,width),dtype=np.uint8)    #Pour le rouge
imgmax=imgR=np.zeros((height,width),dtype=np.uint8)
imgmin=imgR=np.zeros((height,width),dtype=np.uint8)
imgBcpy=np.zeros((height,width),dtype=np.uint8)
 
for h in range(height) : 
    for w in range(width) : #on parcourt la matrice (le tableau) 
        imgB[h,w]=img[h,w,0]    #Tu remplies tes matrices avec la valeur de chaque pixel, à chaque fois avec un canal différent
        imgG[h,w]=img[h,w,1]    #Le resultat est une image en nuance de gris
        imgR[h,w]=img[h,w,2]
imgBcpy=np.copy(imgB)
cpt=0
 
def parcoursimg():
    global imgBcpy
    for h in range(height):
        for w in range(width):
            if(imgBcpy[h,w]==0):
                voisins(h,w)
    return
 
def voisins(h,w):
    global imgBcpy
    global cpt
    if(imgBcpy[h,w-1]==0):
        #print(h,w,imgBcpy[h,w],cpt)
        imgBcpy[h,w-1]=127
        cpt+=1
        voisins(h,w-1)
 
    if(imgBcpy[h-1,w]==0):
        #print(h,w,imgBcpy[h,w],cpt)
        imgBcpy[h-1,w]=127
        cpt+=1
        voisins(h-1,w)
 
    if(imgBcpy[h,w+1]==0):
        #print(h,w,imgBcpy[h,w],cpt)
        imgBcpy[h,w+1]=127
        cpt+=1
        voisins(h,w+1)
 
    if(imgBcpy[h+1,w]==0):
        #print(h,w,imgBcpy[h,w],cpt)
        imgBcpy[h+1,w]=127
        cpt+=1
        voisins(h+1,w)
 
    if(imgBcpy[h-1,w]!=0 and imgBcpy[h,w+1]!=0 and imgBcpy[h+1,w]!=0 and imgBcpy[h,w-1]!=0):
        return
 
parcoursimg()
cv2.imwrite("imagetraitee.png",imgBcpy)
cv2.imshow('imgBcpy',imgBcpy)
cv2.waitKey(0)
cv2.destroyAllWindows()

J'utilise donc les libraries Opencv et Numpy. Ma première fonction parcoursimg() va parcourir mon image et appeler la fonction voisins() quand elle rencontre un pixel noir. Cette dernière va regarder chaque pixel voisin et le mettre en gris, puis appeler récursivement cette même fonction pour parcourir toute notre zone noire. Comme on peut le voir, j'utilise des variables globales, c'est moche mais ce n'est pas important du tout pour le moment. Tout marche très bien, seul problème, lorsque je rencontre une zone noire trop grande, le programme s'arette sans laisser de message d'erreur. J'ai déja fait des recherches à ce sujet, d'où le "sys.setrecursionlimit(35000)" au début du programme, qui me permet d'augmenter la limite max de récursion. Cependant, le problème viendrais du fait que, comme il y a beaucoup d'appel récursif, ça demande une trop grosse quantité de mémoire.
J'ai trouvé quelqu'un sur le net qui avait à peu près le même problème que moi, et on lui a parlé des générateurs. Ça permettrais de résoudre notre problème car ils ne blindent pas l'espace mémoire. Or, je n'arrive pas à les utiliser, j'ai essayer de remplacer mes "return" par des "yield" et de mettre "yield from" quand j'appelle une fonction, mais l'image reste inchangée quand je lance mon programme.
La solution est peut-être simple mais je n'arrive pas à la trouver.
Merci d'avance

[wiztricks]

Salut,

Cependant, le problème viendrais du fait que, comme il y a beaucoup d'appel récursif, ça demande une trop grosse quantité de mémoire.

S'il y a trop d'appels récursif, soit vous ne coupez pas l'arbre des appels soit il faut le faire en séquentiel.
Imaginez à l'étape 0, la liste des voisins à tester/flipper se réduit à ceux du point (x, y). A la sortie, vous avez une nouvelle liste de points dont les voisins sont à tester/flipper... Ce qui vous permet de ré-itérer tant que votre liste n'est pas vide.
Ce n'est pas récursif et ce n'est pas non plus très compliqué à coder.

- W

[Sve@r]

Bonjour

seul problème, lorsque je rencontre une zone noire trop grande, le programme s'arette sans laisser de message d'erreur.

Oui, il y a une limite max de récursion (je crois qu'elle vaut 1000)

Cependant, le problème viendrais du fait que, comme il y a beaucoup d'appel récursif, ça demande une trop grosse quantité de mémoire.

Il me semble que ton algorithme ressemble beaucoup au "floodfill". Si c'est ça il existe une implémentation à base de pile qui "simule" la récursivité. Sauf qu'au lieu de rappeler la fonction, c'est une boucle qui tourne tant que la pile des pixels n'est pas vide. Et la pile, elle n'est pas limitée à 1000 => https://fr.wikipedia.org/wiki/Algori..._par_diffusion

J'ai trouvé quelqu'un sur le net qui avait à peu près le même problème que moi, et on lui a parlé des générateurs. Ça permettrais de résoudre notre problème car ils ne blindent pas l'espace mémoire. Or, je n'arrive pas à les utiliser, j'ai essayer de remplacer mes "return" par des "yield" et de mettre "yield from" quand j'appelle une fonction, mais l'image reste inchangée quand je lance mon programme.

Tu peux remplacer une fonction par un générateur seulement si tu utilises ta fonction dans une itération (ex for x in fct()). Dans ce cas, tu remplaces l'itérable retourné par la fonction (ex return list(...)) par un générateur (ex for x in ...: yield x). Si toutes ces conditions sont respectées alors ton programme qui fonctionnait avant avec des trucs mémoirsés continuera à fonctionner avec des trucs générés à la demande.

Or ici les conditions ne sont pas réalisées. Tu ne cherches pas à récupérer/traiter un ensemble de trucs, mais à appliquer un algo sur un truc et le réappliquer sur ses voisins s'ils partagent la même caractéristique => c'est exactement le floodfill...

[Pommecannelle]

Merci beaucoup pour vos conseils ! Je l'ai du coup fait en utilisant des piles, comme dans l'exemple Wiki que tu as envoyé. J'ai donc mes deux fonctions, la première qui parcours l'image et la deuxième qui gère les pixels :

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
def parcoursimg():
    global imgBcpy
    for h in range(height):
        for w in range(width):
            if(imgBcpy[h,w]==0):
                remplissage(h,w)
    return
 
 
def remplissage(h,w):
    global imgBcpy
    p=[]
    p.append(h)
    p.append(w)
    while(len(p)!=0):
        wtemp=p.pop()
        htemp=p.pop()
        imgBcpy[htemp,wtemp]=127
        try:
            if(imgBcpy[htemp,wtemp-1]==0):
                    p.append(htemp)
                    p.append(wtemp-1)
            if(imgBcpy[htemp-1,wtemp]==0):
                    p.append(htemp-1)
                    p.append(wtemp)
            if(imgBcpy[htemp,wtemp+1]==0):
                    p.append(htemp)
                    p.append(wtemp+1)
            if(imgBcpy[htemp+1,wtemp]==0):
                    p.append(htemp+1)
                    p.append(wtemp)
        except IndexError:
            pass
    return

J'ai mis un "try" car quand on est au bord de l'image, le pixel voisin n'existe pas (selon sur quel bord on est).

Merci beaucoup pour votre aide !

[lg_53]

Les global .... aie aie aie, il faut arrêter de faire cela, ca va vous jouer des tours !

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
 
def parcoursimg(imgBcpy):
    for h in range(height):
        for w in range(width):
            if(imgBcpy[h,w]==0):
                remplissage(imgBcpy, h,w)
    return
 
 
def remplissage(imgBcpy, h,w):
    p=[]
    p.append(h)
    p.append(w)
    while(len(p)!=0):
        wtemp=p.pop()
        htemp=p.pop()
        imgBcpy[htemp,wtemp]=127
        try:
            if(imgBcpy[htemp,wtemp-1]==0):
                    p.append(htemp)
                    p.append(wtemp-1)
            if(imgBcpy[htemp-1,wtemp]==0):
                    p.append(htemp-1)
                    p.append(wtemp)
            if(imgBcpy[htemp,wtemp+1]==0):
                    p.append(htemp)
                    p.append(wtemp+1)
            if(imgBcpy[htemp+1,wtemp]==0):
                    p.append(htemp+1)
                    p.append(wtemp)
        except IndexError:
            pass
    return