Discussion :

[roipoussiere]

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 :

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
#!/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 !!

[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

[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 ?

[Dan737]

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 :

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
#!/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)))

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

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