[JAVA] Détection de formes ou de caractères dans une image

Version imprimable

07/12/2010, 21h55
smh_master

1 pièce(s) jointe(s)

[JAVA] Détection de formes ou de caractères dans une image

Bonjour,
j'ai une image qui contient une grille complète (3x3) du jeu morpion. je veux développer un code qui me permet de savoir qui est le joueur vainqueur ( le X ou le O ).
donc pour le faire il faut avoir un moyen qui me permet de détecter la forme X et/ou O ou bien en tant que caractères X et/ou O.
Mon problème est que je ne trouve pas de pistes pour commencer mon développement.
s'il y en a d'autres méthodes autres que j'ai proposé, je serais à votre écoute.
merci.
08/12/2010, 11h34
ToTo13

Bonjour,

je dirai que Hough sera ton ami :
- Hough pour détecter les lignes et donc avoir une idée de ta grille.
- Hough pour détecter les cercles pour trouver le nombre de ronds et leurs position, donc par déduction tu auras aussi la position des croix.

j'ai trouvé le code de "Hough Circle" qui est le 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
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
 
import java.awt.*;
import java.awt.image.*;
import java.applet.*;
import java.net.*;
import java.io.*;
import java.lang.Math;
import java.util.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.JApplet;
import javax.imageio.*;
import javax.swing.event.*;
 
public class circleHough {
 
		int[] input;
		int[] output;
		float[] template={-1,0,1,-2,0,2,-1,0,1};;
		double progress;
		int width;
		int height;
		int[] acc;
		int accSize=30;
		int[] results;
		int r;
 
		public void circleHough() {
			progress=0;
		}
 
		public void init(int[] inputIn, int widthIn, int heightIn, int radius) {
			r = radius;
			width=widthIn;
			height=heightIn;
			input = new int[width*height];
			output = new int[width*height];
			input=inputIn;
			for(int x=0;x<width;x++) {
				for(int y=0;y<height;y++) {
					output[x + (width*y)] = 0xff000000;
				}
			}
		}
		public void setLines(int lines) {
			accSize=lines;		
		}
		// hough transform for lines (polar), returns the accumulator array
		public int[] process() {
 
			// for polar we need accumulator of 180degress * the longest length in the image
			int rmax = (int)Math.sqrt(width*width + height*height);
			acc = new int[width * height];
			for(int x=0;x<width;x++) {
				for(int y=0;y<height;y++) {
					acc[x*width+y] =0 ;
				}
			}			
			int x0, y0;
			double t;
			progress=0;
 
			for(int x=0;x<width;x++) {
				progress+=0.5;			
				for(int y=0;y<height;y++) {
 
					if ((input[y*width+x] & 0xff)== 255) {
 
						for (int theta=0; theta<360; theta++) {
							t = (theta * 3.14159265) / 180;
							x0 = (int)Math.round(x - r * Math.cos(t));
							y0 = (int)Math.round(y - r * Math.sin(t));
							if(x0 < width && x0 > 0 && y0 < height && y0 > 0) {
								acc[x0 + (y0 * width)] += 1;
							}
						}
					}
				}
			}
 
			// now normalise to 255 and put in format for a pixel array
			int max=0;
 
			// Find max acc value
			for(int x=0;x<width;x++) {
				for(int y=0;y<height;y++) {
 
					if (acc[x + (y * width)] > max) {
						max = acc[x + (y * width)];
					}
				}
			}
 
			//System.out.println("Max :" + max);
 
			// Normalise all the values
			int value;
			for(int x=0;x<width;x++) {
				for(int y=0;y<height;y++) {
					value = (int)(((double)acc[x + (y * width)]/(double)max)*255.0);
					acc[x + (y * width)] = 0xff000000 | (value << 16 | value << 8 | value);
				}
			}
			findMaxima();
 
			System.out.println("done");
			return output;
		}
		private int[] findMaxima() {
			results = new int[accSize*3];
			int[] output = new int[width*height];
 
 
			for(int x=0;x<width;x++) {
				for(int y=0;y<height;y++) {
					int value = (acc[x + (y * width)] & 0xff);
 
					// if its higher than lowest value add it and then sort
					if (value > results[(accSize-1)*3]) {
 
						// add to bottom of array
						results[(accSize-1)*3] = value;
						results[(accSize-1)*3+1] = x;
						results[(accSize-1)*3+2] = y;
 
						// shift up until its in right place
						int i = (accSize-2)*3;
						while ((i >= 0) && (results[i+3] > results[i])) {
							for(int j=0; j<3; j++) {
								int temp = results[i+j];
								results[i+j] = results[i+3+j];
								results[i+3+j] = temp;
							}
							i = i - 3;
							if (i < 0) break;
						}
					}
				}
			}
 
			double ratio=(double)(width/2)/accSize;
			System.out.println("top "+accSize+" matches:");
			for(int i=accSize-1; i>=0; i--){
				progress+=ratio;			
				//System.out.println("value: " + results[i*3] + ", r: " + results[i*3+1] + ", theta: " + results[i*3+2]);
				drawCircle(results[i*3], results[i*3+1], results[i*3+2]);
			}
			return output;
		}
 
		private void setPixel(int value, int xPos, int yPos) {
			output[(yPos * width)+xPos] = 0xff000000 | (value << 16 | value << 8 | value);
		}
 
		// draw circle at x y
		private void drawCircle(int pix, int xCenter, int yCenter) {
			pix = 250;
 
			int x, y, r2;
			int radius = r;
			r2 = r * r;
			setPixel(pix, xCenter, yCenter + radius);
			setPixel(pix, xCenter, yCenter - radius);
			setPixel(pix, xCenter + radius, yCenter);
			setPixel(pix, xCenter - radius, yCenter);
 
			y = radius;
			x = 1;
			y = (int) (Math.sqrt(r2 - 1) + 0.5);
			while (x < y) {
				    setPixel(pix, xCenter + x, yCenter + y);
				    setPixel(pix, xCenter + x, yCenter - y);
				    setPixel(pix, xCenter - x, yCenter + y);
				    setPixel(pix, xCenter - x, yCenter - y);
				    setPixel(pix, xCenter + y, yCenter + x);
				    setPixel(pix, xCenter + y, yCenter - x);
				    setPixel(pix, xCenter - y, yCenter + x);
				    setPixel(pix, xCenter - y, yCenter - x);
				    x += 1;
				    y = (int) (Math.sqrt(r2 - x*x) + 0.5);
			}
			if (x == y) {
				    setPixel(pix, xCenter + x, yCenter + y);
				    setPixel(pix, xCenter + x, yCenter - y);
				    setPixel(pix, xCenter - x, yCenter + y);
				    setPixel(pix, xCenter - x, yCenter - y);
			}
		}
 
		public int[] getAcc() {
			return acc;
		}
 
		public int getProgress() {
			return (int)progress;
		}
 
	}

sauf que j'ai pas su comment l'utiliser pour la détection des "O".
par contre, j'ai réalisé un code qui permet de découper ma grille en 9 images de chaque case de cette grille. Ceci me permettrais de traiter chaque image à part pour la determiner si elle est un "X" ou "O".
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
 
import java.awt.image.BufferedImage;
import java.io.File;
import javax.imageio.ImageIO;
 
public class AllMethodes {
 
    public void decouperIm() {
        int k = 0;
        try {
            System.out.println("1");
            BufferedImage bi = ImageIO.read(new File("C:/morpion1.jpg"));
            System.out.println("2");
            int wid = bi.getWidth() / 3;
            int hei = bi.getHeight() / 3;
            System.out.println("width " + wid + " height " + hei);
            BufferedImage a1 = new BufferedImage(wid, hei, BufferedImage.TYPE_INT_RGB);
 
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    a1.getGraphics().drawImage(bi, 0, 0, a1.getWidth(), a1.getHeight(), j * wid, i * hei, (j + 1) * wid, (i + 1) * hei, null);
                    ImageIO.write(a1, "jpg", new File("/a" + (k++) + ".jpg"));
                    System.out.println("image " + k + " traité");
                }
            }
        } catch (Exception e) {
            System.out.print("erreur " + e);
        }
    }

Si quelqu'un a une idée comment pourrais-je utiliser la détection de cercle de hough dans mon cas, je serais très reconnaissant.

09/12/2010, 10h36
ToTo13

Bonjour,

effectivement ce code à l'air très bizarre :-(
Le principe de Hough pour les cercles est de tirer des triplets de points, de calculer le cercle passant par ces trois points (simple opération mathématique) et de sauver le résultat.
En réitérant l'opération un grand nombre de fois, on voit des candidats apparaître.
09/12/2010, 11h43
Nebulix

Si tu fais un histogramme des distances des points au centre de gravité d'une croix, tu as qqch de plat entre 0 et max, et pour un cercle qqch de piqué à max.
Tu peux jouer avec les moments pour trouver un critère robuste.
09/12/2010, 11h53
pseudocode

Une extraction des composantes connexes et un calcul de corrélation avec une base de référence (ou un réseau de neurone), ca devrait suffire.
09/12/2010, 23h16
smh_master

Citation:

Envoyé par ToTo13

Bonjour,

effectivement ce code à l'air très bizarre :-(
Le principe de Hough pour les cercles est de tirer des triplets de points, de calculer le cercle passant par ces trois points (simple opération mathématique) et de sauver le résultat.
En réitérant l'opération un grand nombre de fois, on voit des candidats apparaître.

puisque tu vois que le code a l'air bizarre pourrais tu me fournir la classe de Hough qui est généralement utilisé pour traiter les cercles (si vous ne voyez pas d'inconvénient et la manière de l'utiliser car là je me sens hors normes)
si je poste ici c'est que j'ai plus de choix et je manque d'idées et d'espoir :(
pour les autres merci de m'avoir répondu.
09/12/2010, 23h52
ToTo13

Faisons plus simple :
- Récupère celle pour les lignes de PseudoCode dans la rubrique contribuez.
- Tu détectes les six lignes principales.
- Tu isoles ensuite les composantes de chaque case.

Une fois que tu en seras là, tu ré-appliqueras Hough sur les composantes afin de différencier celles qui sont des croix de celles qui sont des ronds.

Sinon pour détecter les lignes principales, je pense que l'idée de PseudoCode de compter les composantes connexes est bonne : la plus grande est ton maillage.
Par contre je pense que le réseau de neurones est un peu trop hard pour ce qu'il apporterait.
14/12/2010, 23h19
smh_master

Puisque j'ai réussis à couper mon image de grille complète en 9 cases (9 images), voilà la squelette de ce que j'ai voulu faire:

public boolean IsCercle(Image im){

//ici un traitement pour déterminer si im est un cercle
...

if(im est un cercle) return true;

else return false;

}
Mais vu que je ne connais pas grand chose sur les traitements d'images j'ai pas su implémenter ce que je viens d'écrire.
Par contre, on m'a dit que chaque image peut avoir un vecteur qui pourrais l'identifier. Donc si je connais comment calculer le vecteur de chaque images des 9 que j'ai eu, il se trouve qu'il y a ce qu'on appelle "distance noté d" qui est enfaite une valeur qui exprime la différence entre 2 images.
d = V1-V2 (avec V1 est le vecteur de l'image1 et V2 est le vecteur de l'image2) donc les 2 images sont presque identiques lorsque la valeur de d tend vers 0.
quelqu'un a une idée sur ça aussi ?
15/12/2010, 11h23
ToTo13

Puisque tu fais du Java, récupère donc l'implémentation de Hough faite par PseudoCode dans la rubrique Contribuez.

Je pense qu'avec deux pauvres masques de valeurs on doit pouvoir différencier une croix d'un cercle.

Code:

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

Code:

1
2
3
4
5
6
7
8
9
 
1 . . 0 0 . . 1
. 1 . 0 0 . 1 .
. . 1 . . 1 . .
0 0 . 1 1 . 0 0
0 0 . 1 1 . 0 0
. . 1 . . 1 . .
. 1 . 0 0 . 1 .
1 . . 0 0 . . 1

Citation:
Envoyé par pseudocode
Je pense qu'avec deux pauvres masques de valeurs on doit pouvoir différencier une croix d'un cercle.
Code:

1 2 3 4 5 6 7 8 0 . . 1 1 . . 0 . 1 . . . . 1 . . . . 0 0 . . . 1 . 0 0 0 0 . 1 1 . 0 0 0 0 . 1 . . . 0 0 . . . . 1 . . . . 1 . 0 . . 1 1 . . 0
Code:

1 2 3 4 5 6 7 8 9 1 . . 0 0 . . 1 . 1 . 0 0 . 1 . . . 1 . . 1 . . 0 0 . 1 1 . 0 0 0 0 . 1 1 . 0 0 . . 1 . . 1 . . . 1 . 0 0 . 1 . 1 . . 0 0 . . 1
Tu ne crains pas un problème d'invariance par homothétie ?

16/12/2010, 11h45
math_lab

Une autre technique de bourrin: tu regardes s'il y a beaucoup de pixels proches du centre de la case. Si c'est le cas, c'est probablement un X, sinon, c'est un O. Bien évidemment c'est absolument pas robuste, mais pour une application pareille, ça devrait suffire.
Tu peux l’améliorer en regardant la distance par rapport au centroide de ta forme, plutôt que le centre de la case, mais ça t'oblige a faire une première passe. Ensuite, si la distance minimum de tes pixels par rapport au centre est supérieur a un seuil, c'est un cercle.
16/12/2010, 12h24
pseudocode

Citation:

Envoyé par ToTo13

Tu ne crains pas un problème d'invariance par homothétie ?

Il faut tester... Mais une fois les composantes connexes extraites et retaillées en 8x8, ca devrait limiter le problème. Au peut également créer plusieurs masques pour chaque signe, afin de gérer des écritures différentes.

http://xphilipp.developpez.com/tmp/tictactoe.png