Limite de récursion

Version imprimable

Limite de récursion

Bonsoir,

Je développe un script nécessitant d'isoler chaque formes d'une image monochrome.

Pour se faire, j'utilise la fonction récursive get_shape() dont l'algo simplifié est le suivant :
Si le pixel donné est noir, je l'ajoute à la liste 'shape' et je fais get_shape() sur les pixels voisins.

Au final, j'obtiens shape, qui est une liste contenant les coordonnées des pixels noir de la forme.
J'applique cette fonction à tous les pixels noirs non traités de mon image.

Cela fonctionne très bien pour les petites images (<100px de large), par contre je ne peux pas appliquer ce code aux image plus grandes car j’atteins la limite de récursion (RuntimeError: maximum recursion depth exceeded)

Même en modifiant la limite de récursion (sys.setrecursionlimit(20000) ) (au delà de 20000 j'ai un segFault).
Ce n'est pas trop un problème de ressources car même si la récursion est très profonde, les calculs dans la fonction récursive sont très simples.

Voici mon code :
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 #!/usr/bin/python3 # -*- coding: utf-8 -*- import Image from numpy import array im = Image.open('image.png').convert('L') im_w, im_h = im.size matrix_im = array([[im.getpixel((x, y)) < 128 for y in range(im_h)] for x in range(im_w)]) tested = array([[im.getpixel((x, y)) >= 128 for y in range(im_h)] for x in range(im_w)]) class Pixel(): def __init__(self, x, y): self.x = x self.y = y def left(self): return Pixel(self.x-1, self.y) if self.x-1 >= 0 else False def right(self): return Pixel(self.x+1, self.y) if self.x+1 < im_w else False def up(self): return Pixel(self.x, self.y-1) if self.y-1 >= 0 else False def down(self): return Pixel(self.x, self.y+1) if self.y+1 < im_h else False def __cmp__(self, other): return self.x == other.x and self.y == other.y def __str__(self): return str(self.x) + ';' + str(self.y) def __repr__(self): return str(self.x) + ';' + str(self.y) def get_shape(pixel): global tested global shape tested[pixel.x][pixel.y] = True if matrix_im[pixel.x][pixel.y]: shape += [pixel] if pixel.left() and not tested[pixel.x-1][pixel.y]: get_shape(pixel.left()) if pixel.right() and not tested[pixel.x+1][pixel.y]: get_shape(pixel.right()) if pixel.up() and not tested[pixel.x][pixel.y-1]: get_shape(pixel.up()) if pixel.down() and not tested[pixel.x][pixel.y+1]: get_shape(pixel.down()) return(shape) else: return([]) shapes = [] for x in range(im_w): for y in range(im_h): if not tested[x][y]: shape = [] shapes.append(get_shape(Pixel(x, y))) for i, shape in enumerate(shapes): print('%i. Shape surface: %ipx' % (i+1, len(shape)))
Je cherche donc un moyen de repousser ou de contourner cette limite de récursion.

Merci à vous !!

09/11/2015, 20h19
wiztricks

Salut,

Si l'algo ne fonctionne pas dans des conditions normales de température et de pression, pourquoi ne pas le remettre en cause plutôt que s'acharner à essayer de le faire fonctionner en cassant les jauges de température et de pression?
La rubrique algorithmique est peut être un bon endroit où trouver des idées...

note: le segfault c'est juste que vous avez explosé la pile utilisée pour stocker le contexte des appels de fonction. Pour l'augmenter, çà dépend de l'OS mais il faut souvent recompiler Python ou patcher l'executable. Dans tous les cas, c'est un truc infâme dont vous n'avez jamais besoin: il faut regarder côté développeur d'application sur l'OS en question car çà n'a rien à voir avec Python.

- W
09/11/2015, 20h35
marco056

2 remarques :
- quand on pond un algorithme récursif, en principe, la méthode naïve existe.
- en parlant de naïveté, quelle est la condition pour laquelle l'algorithme se termine ?

Vous pourriez utiliser un générateur au lieu de faire des récursions. Depuis la version 3.3, il y a la syntaxe yield from. Voici une petite modification de votre code. Il y aurait pas mal d'autres choses à améliorer. Surtout qu'avec numpy, il y a probablement moyen de faire ça de manière bien plus efficace. En partant du principe que c'est pour apprendre:

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
# import Image
import numpy as np
 
im = np.random.randint(256, size=(12, 12))
im_w, im_h = im.shape
matrix_im  = im < 128
tested     = np.logical_not(matrix_im)
 
class Pixel():
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
    def left(self):  return Pixel(self.x-1, self.y) if self.x-1 >= 0 else False
    def right(self): return Pixel(self.x+1, self.y) if self.x+1 < im_w else False
    def up(self):    return Pixel(self.x, self.y-1) if self.y-1 >= 0 else False
    def down(self):  return Pixel(self.x, self.y+1) if self.y+1 < im_h else False
 
    def __cmp__(self, other):
        return self.x == other.x and self.y == other.y
    def __str__(self):
        return str(self.x) + ';' + str(self.y)
    def __repr__(self):
        return str(self.x) + ';' + str(self.y)
 
def get_shape(pixel):
    tested[pixel.x][pixel.y] = True
    if matrix_im[pixel.x][pixel.y]:
        yield pixel
 
        if pixel.left() and not tested[pixel.x-1][pixel.y]:
            yield from get_shape(pixel.left())
        if pixel.right() and not tested[pixel.x+1][pixel.y]:
            yield from get_shape(pixel.right())
        if pixel.up() and not tested[pixel.x][pixel.y-1]:
            yield from get_shape(pixel.up())
        if pixel.down() and not tested[pixel.x][pixel.y+1]:
            yield from get_shape(pixel.down())
 
shapes = []
for x in range(im_w):
    for y in range(im_h):
        if not tested[x][y]:
            shapes.append(list(get_shape(Pixel(x, y))))
 
for i, shape in enumerate(shapes):
    print('%i. Shape surface: %ipx' % (i+1, len(shape)))

10/11/2015, 13h16
roipoussiere

Hello, merci beaucoup pour vos réponses.

@wiztricks : Ben du coup je suis en train de recoder ça en itératif. Utiliser de la récursivité pour ce genre de process me semblait plus naturel mais bon.

@marco056 : Je ne vois pas à quoi tu fais allusion avec la méthode naïve. Sinon l'algo se termine lorsque il n'y a plus de cases à tester aux alentours.

@Dan737 : Merci pour cette modif ! En effet l'algo est plus performant, par contre je ne vois pas en quoi ça évite de faire des récursions. Il y a toujours des appels à get_shapes() dans la fonction get_shapes(). Du coup je peux traiter des images un peu plus grandes, mais il y a toujours le même problème de limite de récursion.

Je me penche sur une version itérative, j'ai vu à peu près comment m'en sortir sur papier.
10/11/2015, 14h37
Dan737

As-tu testé ce code avec une grande image ? Il n'y a pas de récursions dans mon code car ce ne sont pas des appels de fonctions avec un return, mais des generateurs qui suspendent leur exécution en attendant que le prochain generateur fournisse ses valeurs.
10/11/2015, 14h46
roipoussiere

1 pièce(s) jointe(s)
Hello, oui j'ai testé avec une grande image.

La modif appliqué à ton code pour lire les images :
Code:

1 2 3 4 # im = np.random.randint(256, size=(12, 12)) img = Image.open(str(sys.argv[1])).convert('L') img.load() im = np.asarray( img, dtype="int32" )
L'image en question à 400px de large :
Pièce jointe 192280

Stacktrace :
[...]
File "./shapes.py", line 44, in get_shape
yield from get_shape(pixel.right())
File "./shapes.py", line 41, in get_shape
if pixel.left() and not tested[pixel.x-1][pixel.y]:
File "./shapes.py", line 24, in left
def left(self): return Pixel(self.x-1, self.y) if self.x-1 >= 0 else False
RuntimeError: maximum recursion depth exceeded

Ah oui, en effet! Je me suis un peu emballé. :) En fait je me souvenais vaguement d'une présentation de D. Beazly Generators: The Final Frontier dans laquelle il montre comment utiliser des générateurs pour se passer de récursions. Mais en allant revoir un peu, il se construit sa propre pile. Voilà pour ton cas ce que ça donnerait

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
70
71
72
73
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import numpy as np
from PIL import Image

img = Image.open(str(sys.argv[1])).convert('L')
img.load()
im = np.asarray( img, dtype="int32" )


im_w, im_h = im.shape
matrix_im  = im < 200
tested     = np.logical_not(matrix_im)
 
class Pixel():
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
    def left(self):  return Pixel(self.x-1, self.y) if self.x-1 >= 0 else False
    def right(self): return Pixel(self.x+1, self.y) if self.x+1 < im_w else False
    def up(self):    return Pixel(self.x, self.y-1) if self.y-1 >= 0 else False
    def down(self):  return Pixel(self.x, self.y+1) if self.y+1 < im_h else False
 
    def __cmp__(self, other):
        return self.x == other.x and self.y == other.y
    def __str__(self):
        return str(self.x) + ';' + str(self.y)
    def __repr__(self):
        return str(self.x) + ';' + str(self.y)
 
def get_shape(pixel):
    tested[pixel.x][pixel.y] = True
    if matrix_im[pixel.x][pixel.y]:
 
        if pixel.left() and not tested[pixel.x-1][pixel.y]:
            yield get_shape(pixel.left())
        if pixel.right() and not tested[pixel.x+1][pixel.y]:
            yield get_shape(pixel.right())
        if pixel.up() and not tested[pixel.x][pixel.y-1]:
            yield get_shape(pixel.up())
        if pixel.down() and not tested[pixel.x][pixel.y+1]:
            yield get_shape(pixel.down())


        return pixel




shapes = []
for x in range(im_w):
    for y in range(im_h):
        if not tested[x][y]:
            stack = [get_shape(Pixel(x, y))]
            shape = []
            while stack:
                try:
                    node = next(stack[-1])
                    stack.append(node)
                except StopIteration as exc:
                    stack.pop()
                    shape.append(exc.value)


            shapes.append(shape)


for i, shape in enumerate(shapes):
    print('%i. Shape surface: %ipx' % (i+1, len(shape)))

J'ai testé avec ton image et le résultat donne:

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
 
1. Shape surface: 10px
2. Shape surface: 21221px
3. Shape surface: 4px
4. Shape surface: 4px
5. Shape surface: 3px
6. Shape surface: 1px
7. Shape surface: 6px
8. Shape surface: 10px
9. Shape surface: 1px
10. Shape surface: 1px
11. Shape surface: 676px
12. Shape surface: 435px
13. Shape surface: 6px
14. Shape surface: 7px
15. Shape surface: 2px
16. Shape surface: 94px
17. Shape surface: 1px
18. Shape surface: 219px
19. Shape surface: 4px
20. Shape surface: 5px
21. Shape surface: 9px
22. Shape surface: 1px
23. Shape surface: 1px
24. Shape surface: 1px
25. Shape surface: 16px

10/11/2015, 16h49
roipoussiere

Yeeess !!!
C'est excellent, merci beaucoup !!

Du coup j'ai supprimé la classe Pixel qui ne servait plus à grand chose, ce qui améliore considérablement les perfs (3.7s pour la même image en 2000px de large).

Bon ben du coup je jette mon algo itératif sur lequel je me cassait la tête depuis ce matin :-)

Encore merci, paix sur toi et toute ta famille.