Discussion :

[Faengsel]

Bonjour !

Actuellement, je travaille sur la reconnaissance de formes avec mon partenaire de binôme. Lui s'occupe de l'extraction des caractéristiques, et moi du prétraitement d'image.

Je bloque à la squelettisation où on avons choisi d'utiliser l'algorithme de Hilditch. Rien à faire, mon programme est syntaxiquement correct, mais il me retourne l'image de départ sans la modifier...
J'ai repris l'algorithme exact décrit par Hilditch (que vous pouvez trouver ici si vous le souhaitez. Un peu compliqué, ma foi) et non un algorithme reformulé (et quelque peu incompréhensible) sur Internet.

Je travaille avec Python 3.3.1 en utilisant la bibliothèque PIL.

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
from PIL import Image
 
# CONVERTIR LISTE EN INTEGER
def t2i(tup):
	liste = list(tup) # Eventuelle conversion en liste si l'entree est un tuple
	n0 = int(liste[0]/255)
	n1 = int(liste[1]/255)
	n2 = int(liste[2]/255)
	return n0+n1+n2
 
n = (0,0,0)
b = (255,255,255)
 
# SQUELETTISATION
def squelettiser(img):	
	imgskel=Image.new(img.mode, img.size)
 
	largeur=img.size[0]-2
	hauteur=img.size[1]-2
 
	for y in range(2,hauteur):
		for x in range(2,largeur): 
			# VOISINAGE DE P0
			P0 = img.getpixel((x,y))
			P1 = img.getpixel((x,y+1))
			P2 = img.getpixel((x-1,y+1))
			P3 = img.getpixel((x-1,y))
			P4 = img.getpixel((x+1,y-1))
			P5 = img.getpixel((x,y-1))
			P6 = img.getpixel((x+1,y-1))
			P7 = img.getpixel((x+1,y))
			P8 = img.getpixel((x+1,y+1))
 
			# NOMBRE DE VOISINS BLANCS DE P0
			N_P0 = t2i(P1) + t2i(P2) + t2i(P3) + t2i(P4) + t2i(P5) + t2i(P6) + t2i(P7) + t2i(P8)
 
 
			H_P0 = 0 # Nombre de transitions du blanc vers le noir du pixel P0
			H1_P0 = 0 # Voir les dernières conditions
			H3_P0 = 0
			N_P0 = 0 
 
			condition1 = 0
			condition2 = 0
			condition3 = 0
			condition4 = 0
			condition5 = 0
 
 
			# NOMBRE DE TRANSITIONS BLANC => NOIR
			if  P0 == n:
				if  P8 == b and P1 == n:
					H_P0 = H_P0 + 1
				if  P1 == b and P2 == n:
					H_P0 = H_P0 + 1
				if  P2 == b and P3 == n:
					H_P0 = H_P0 + 1
				if  P3 == b and P4 == n:
					H_P0 = H_P0 + 1
				if  P4 == b and P5 == n:
					H_P0 = H_P0 + 1
				if  P5 == b and P6 == n:
					H_P0 = H_P0 + 1
				if  P6 == b and P7 == n:
					H_P0 = H_P0 + 1
				if  P7 == b and P8 == n:
					H_P0 = H_P0 + 1
 
 
 
				# CONDITION 1
				if 1 <= N_P0 <= 6:
					condition1 = 1
 
				# CONDITION 2
				if condition1 and H_P0 == 1:
					condition2 = 1
 
				# CONDITION 3
				if condition2 and t2i(P1) + t2i(P3) + t2i(P5) + t2i(P7) >= 1:
					condition3 = 1
 
				# CONDITION 4
				if P1 == b:
					H1_P0 = 1				
				if condition3 and (H1_P0 == 1 or P3 == n):
					condition4 = 1
 
				# CONDITION 5
				if P3 == b:
					H3_P0 = 1
				if condition4 and (H3_P1 == 1 or P1 == n):
					condition5 = 1
 
				# EFFACER PIXEL P0
				if condition5:
					img.putpixel((x,y),b)
				else:
					img.putpixel((x,y),n)
 
			else:
				img.putpixel((x,y),b)
	data=list(img.getdata())
	imgskel.putdata(data)
	imgskel.save("Image_Squelette.png")

Je pense que le problème vient de la façon dont j'efface le pixel P0 car quoi que je mette après le if, j'obtiens toujours l'image de départ. Et je ne comprends pas ce qui cloche... Quelqu'un pourrait-il m'aider ?

Merci d'avance .

PS : J'ignore si j'ai posté dans la bonne rubrique et je vous prie de m'excuser si ce n'était pas le cas.

[VinsS]

Salut,

Je comprend juste que tu fais un voisinage de pixel mais pas plus. Par contre en parcourant le code on voit ceci:

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
 
			# NOMBRE DE VOISINS BLANCS DE P0
			N_P0 = t2i(P1) + t2i(P2) + t2i(P3) + t2i(P4) + t2i(P5) + t2i(P6) + t2i(P7) + t2i(P8)
 
# 5 lignes plus loin:
			N_P0 = 0 
 
# 30 lignes plus loin:
				if 1 <= N_P0 <= 6:
					condition1 = 1
# Si N_PO == 0 donc condition1 vaut toujours 0
# 4 lignes plus loin:
				if condition1 and H_P0 == 1:
					condition2 = 1
# idem condition2 vaut toujours 0
# 4 lignes plus loin:
				if condition2 and t2i(P1) + t2i(P3) + t2i(P5) + t2i(P7) >= 1:
					condition3 = 1
# idem ...

Je me suis arrêté là.

[Faengsel]

Ah oui, effectivement. Merci ! Alors maintenant j'obtiens une image différente de celle de départ, bien que ce ne soit pas le résultat que je souhaite (mais le problème vient peut-être des conditions imposées en elles-même).

Et en effet, je définis le voisinage du pixel que l'on traite à chaque fois (P0). Ensuite, pour que P0 puisse être effacé, il doit remplir certaines conditions :
1. Avoir au moins deux pixels voisins noirs et au plus sept noirs.
2. Le squelette doit rester continu donc le nombre de transitions du blanc vers le noir dans le voisinage de P0 doit être égal à 1.
3. P1 + P3 + P5 + P7 >= 1 pour que P0 soit sur le bord du contour de l'image (on traite des contours de triangles, carrés...), sachant qu'un pixel vaut 1 s'il est blanc et 0 s'il est noir.
4. Deux autres conditions pour qu'on n'efface pas totalement les lignes de deux pixels d'épaisseur.

Est-il normal à présent que les conditions 2 à 5 n'ont aucune influence sur la condition 1 ? De même, la condition 2 prise seule et indépendamment de la 1 fonctionne, mais si la condition 3 est vérifiée tout en dépendant de la condition 2, le programme n'exécutera quand même que la condition 2 sans tenir compte de la troisième. C'est problématique...

[VinsS]

Je pense qu'il y a d'abord un problème avec ta fonction t2i()

Code :

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

1
2
3
4
5
6
7
 
def t2i(tup):
    liste = list(tup) # Eventuelle conversion en liste si l'entree est un tuple
    n0 = int(liste[0]/255)
    n1 = int(liste[1]/255)
    n2 = int(liste[2]/255)
    return n0+n1+n2

Ici tout octet inférieur à 255 retourne 0 et 255 retourne 1 or tu les additionnes et, ce me semble, tu cherches à identifier les pixels blancs.

Je m'explique:
p = (15, 42, 154) retourne 0+0+0 >> 0
p = (0, 0, 255) retourne 0+0+1 >> 1 ce pixel n'est pas blanc il est bleu
p = (0, 255, 255) retourne 0+1+1 >> 2 pas blanc mais retourne 2
p = (255, 255, 255) retourne 1+1+1 >> 3 pas blanc mais retourne 3

donc ici:

Code :

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

1
2
 
N_P0 = t2i(P1) + t2i(P2) + t2i(P3) + t2i(P4) + t2i(P5) + t2i(P6) + t2i(P7) + t2i(P8)

si il y a trois pixels blanc, chacun retournant 3, N_PO = 9 soit plus qu'il n'y a de voisins !

Si mon raisonnement est bon, (quelque chose peut m'échapper dans ton script) alors remplace cette ligne par:

Code :

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

1
2
 
N_PO = (P1 == b) + (P2 == b) + (P3 == b) + (P4 == b) + (P5 == b) + (P6 == b) + (P7 == b) + (P8 == b)

Je suppose que tu vas me dire que tes images sont strictement noir et blanc, dans ce cas peut-être qu'une conversion du format au départ simplifierait les choses.

Aurais-tu un modèle d'image à nous montrer ?

[Faengsel]

Effectivement, je ne travaille que sur des images en noir et blanc dans la mesure où j'ai déjà créé une procédure pour passer les images en noir et blanc au préalable, donc les pixels peuvent soit prendre la valeur (0,0,0), soit (255,255,255). Et dans ce cas, j'ai oublié de faire la moyenne arithmétique des trois n dans ma fonction t2i si je veux que N_P0 soit compris entre 0 et 8.

Je ne comprends pas bien ce que tu entends par « conversion de format ».

On peut travailler par exemple sur un simple carré de 3 pixels d'épaisseur : http://oi43.tinypic.com/2z4wxhx.jpg
Le but est d'obtenir un squelette - qui ressemblerait ici grossièrement à un carré et - avec un pixel d'épaisseur.

Ce que j'obtiens à présent :
http://i79.servimg.com/u/f79/13/51/98/55/image_10.png

Je suppose qu'il doit y avoir un petit problème théorique (gros doute sur les deux ou trois dernières conditions) parce qu'avec les progammes et algorithmes reformulés qu'on trouve sur internet (où mes trois dernières conditions ont été changées), ça marche assez bien :
http://i79.servimg.com/u/f79/13/51/98/55/squele10.png

Donc je pense que je dois me repencher sur l'algorithme original. Un très grand merci pour m'avoir corrigée !

[VinsS]

J'ai encore trouvé quelques trucs qui ne vont pas.

dans la recherche de voisinage, il y deux fois le même pixel:

Code :

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

1
2
3
4
 
			P4 = img.getpixel((x+1,y-1))
 
			P6 = img.getpixel((x+1,y-1))

J'ai suivi le document que tu donnes en lien pour l'ordre des voisins, soit:

4 | 3 | 2
5 | 0 | 1
6 | 7 | 8

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
            vsn = []
            vsn.append(img.getpixel((x, y)))
            vsn.append(img.getpixel((x+1, y)))
            vsn.append(img.getpixel((x+1, y-1)))
            vsn.append(img.getpixel((x, y-1)))
            vsn.append(img.getpixel((x-1, y-1)))
            vsn.append(img.getpixel((x-1, y)))
            vsn.append(img.getpixel((x-1, y+1)))
            vsn.append(img.getpixel((x, y+1)))
            vsn.append(img.getpixel((x+1, y+1)))

Je les ai mis dans une liste par facilité.

À la condition 5 tu as mis H3_P1, je suppose qu'il s'agit de H3_P0.
Toutes les conditions sont en cascade, sauf les deux dernières, on peut donc simplifier.
Et en simplifiant aussi le calcul des voisins et des transitions, ça donne ceci:

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
 
n = (0,0,0)
b = (255,255,255)
 
# SQUELETTISATION
def squelettiser(img):	
    imgskel=Image.new(img.mode, img.size)
 
    largeur=img.size[0]-2
    hauteur=img.size[1]-2
 
    for y in range(2,hauteur):
        for x in range(2,largeur): 
            # VOISINAGE DE P0
            vsn = []
            vsn.append(img.getpixel((x, y)))
            vsn.append(img.getpixel((x+1, y)))
            vsn.append(img.getpixel((x+1, y-1)))
            vsn.append(img.getpixel((x, y-1)))
            vsn.append(img.getpixel((x-1, y-1)))
            vsn.append(img.getpixel((x-1, y)))
            vsn.append(img.getpixel((x-1, y+1)))
            vsn.append(img.getpixel((x, y+1)))
            vsn.append(img.getpixel((x+1, y+1)))
 
            # LISTE DES VOISINS BLANCS DE P0
            whites = [i == b for i in vsn]
            # NOMBRE DE VOISINS BLANCS DE P0
            nwhites = sum(whites)
 
            if vsn[0] == n:
                whites.append(whites[1])
                # NOMBRE DE TRANSITIONS BLANC => NOIR
                trans = sum([v and not whites[i+2] for i, v in enumerate(whites[1:-1])])
                px = n
                # CONDITION 1 ET CONDITION 2
                if 1 <= nwhites <= 6 and trans == 1:
                    # CONDITION 3
                    if whites[1] + whites[3] + whites[5] + whites[7] >= 1:
                        # CONDITION 4
                        if vsn[1] == b or vsn[3] == n):
                            img.putpixel((x, y), b)
                        # CONDITION 5
                        elif vsn[3] == b or vsn[1] == n):
                            img.putpixel((x, y), b)
 
    data=list(img.getdata())
    imgskel.putdata(data)
    imgskel.save("Image_Squelette.png")

Il faudra voir pour les conditions 4 et 5 pourquoi tu ne vérifies que les voisins 1 et 3.

J'ai pas testé mon code ...

[Faengsel]

C'est vraiment gentil de t'y pencher davantage. Oui, Hilditch note les voisins différemment, mais on était partis sur
2 | 1 | 8
3 | 0 | 7
4 | 5 | 6
pour la suite de l'algorithme sur laquelle on a travaillé avant de faire la squelettisation donc on a gardé par commodité.

Effectivement, H3_P0 et non H3_P1... Je l'avais corrigé par la suite mais je n'ai pas reposté le programme suite aux modifications.

On regarde seulement pour 1 et 3 parce qu'étant donné qu'on balaie de haut en bas et de gauche à droite, il faut juste vérifier les conditions 4 et 5 pour les pixels (dans ma notation) P8, P1, P2, P3. Or les Pi où i est pair vérifient automatiquement toutes les conditions, y compris les deux dernières, donc il faut juste vérifier les conditions pour P1 et P3 (pour Hilditch, il s'agira de P3 et P5).

Maintenant, tout marche parfaitement bien ! J'ai testé ton code et il n'y a aucun souci apparent. Merci beaucoup, énormément même !

Problème résolu donc .

[VinsS]

J'ajouterai juste une chose, je pense que la deuxième condition n'est pas nécessaire ici:

Code :

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

1
2
 
                if 1 <= nwhites <= 6 and trans == 1:

En effet, si le nombre de blancs est au minimum de un et que le nombre de noir est au minimum de deux il y a forcément au minimum une transition.
Donc ceci suffit:

Code :

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

1
2
 
                if 1 <= nwhites <= 6:

...

[Faengsel]

Souvent, le squelette est discontinu donc en ce sens la deuxième condition n'est pas nécessaire mais Hilditch souhaitait un squelette continu et cette condition s'assure qu'il demeure une connectivité dans le contour. Je pense que c'est un problème surtout si tu obtiens ton squelette de 1 pixel d'épaisseur et si, par exemple, tu as ce motif répété sur une partie de la figure : http://oi43.tinypic.com/316rwn9.jpg Le pixel central respecte toutes les conditions à part la deuxième et si on efface l'efface, on risque d'effacer également une bonne partie de la figure dans la mesure où le motif serait récurrent. Or, nous avons besoin d'un squelette continu pour le reste de notre programme de reconnaissance de formes, c'est pourquoi on exige que le nombre de transition soit obligatoirement unitaire.