Fonction récursive trop longue

Version imprimable

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:

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

02/05/2019, 18h41
wiztricks

Salut,

Citation:

Envoyé par Pommecannelle

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
02/05/2019, 21h15
Sve@r

Bonjour

Citation:

Envoyé par Pommecannelle

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)

Citation:

Envoyé par Pommecannelle

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

Citation:

Envoyé par Pommecannelle

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...

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:

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 !

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

Code:

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