[java] Etiquettage de composantes connexes (union-find)

[pseudocode]

Envoyé par Anis99

Bonsoir,
je ne sais pas si j'ai fais tout le necessaire pour implementer un code java pour l'extraction des composantes connexes! mais j'ai pas pu
alors la je vous demande de m'aider d'avantage car je n'arrive pas a implementé le code pour extraire les composantes connexes.

C'est quoi que tu veux dire par "extraire les composantes connexes" ? Qu'est-ce que tu voudrais que ta fonction te renvoie comme type de données ?

[Anis99]

Bonsoir,
Ben je voudrais avoir comme resultat une image segmenté ainsi que mes composantes connexes(je travaille sur des images manuscrites arbes numérisé donc mes composantes c'est les mots) dans une structure de donnée!

Cordialement

[pseudocode]

Envoyé par Anis99

Bonsoir,
Ben je voudrais avoir comme resultat une image segmenté ainsi que mes composantes connexes(je travaille sur des images manuscrites arbes numérisé donc mes composantes c'est les mots) dans une structure de donnée!

Cordialement

le tableau int[][] retourné par la fonction compute() est la carte des régions de l'image. Tu as donc directement la segmentation et une structure de données contenant les composantes.

[Anis99]

Envoyé par pseudocode

le tableau int[][] retourné par la fonction compute() est la carte des régions de l'image. Tu as donc directement la segmentation et une structure de données contenant les composantes.

Bonsoir;
donnez moi un exemple pour que je puisse affiché une composante connexe;

Cordialment

[pseudocode]

Envoyé par Anis99

Bonsoir;
donnez moi un exemple pour que je puisse affiché une composante connexe;

Cordialment

Code java :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
// calcule des composantes connexes
int[][] rmap = new CCLabeling(image,W,H).compute();
 
// extraction d'une composante dans un BufferedImage
BufferedImage output = new BufferedImage(W, H, BufferedImage.TYPE_INT_RGB);
for(int y=0;y<H;y++)
	for(int x=0;x<W;x++) {
		int num = rmap[x][y];
 
		if (num==2) // numero de la composante a extraire
			output.setRGB(x, y, Color.WHITE.getRGB() );
		else
			output.setRGB(x, y, Color.BLACK.getRGB() );
	}

[Anis99]

Envoyé par pseudocode

Code java :

Bonjour;
je pense qu'on s'est pas bien compris ,quand je vous disais extraire une composante connexe je voulais dire encadrer les composantes connexes dans l'image résultat(image segmenté).

Cordialement.

[pseudocode]

Envoyé par Anis99

Bonjour;
je pense qu'on s'est pas bien compris ,quand je vous disais extraire une composante connexe je voulais dire encadrer les composantes connexes dans l'image résultat(image segmenté).

Cordialement.

Code java :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// calcul des composantes connexes
int[][] rmap = new CCLabeling(image,W,H).compute();
 
// mise en relief des composantes
BufferedImage output = new BufferedImage(W, H, BufferedImage.TYPE_INT_RGB);
for(int y=1;y<H-1;y++)
	for(int x=1;x<W-1;x++) {
		// composante du pixel x,y
		int num = rmap[x][y];
 
		// composantes des 4 voisins
		int north = rmap[x][y-1];
		int south = rmap[x][y+1];
		int west = rmap[x-1][y];
		int east = rmap[x+1][y];
 
		// si les composantes ne sont pas identiques afficher une frontière
		if (num!=north || num!=south || num!=west || num!=east)
			output.setRGB(x, y, Color.WHITE.getRGB() );
	}

[Anis99]

Bonsoir;

la je viens d'exécuté le code et ça na pas donner les resultats souhaité, car moi je veux que chaque composante connexes soit encadré(mettre dans une rectangle) dans l'imgae segmenté.

Cordialement.

[pseudocode]

Envoyé par Anis99

Bonsoir;

la je viens d'exécuté le code et ça na pas donner les resultats souhaité, car moi je veux que chaque composante connexes soit encadré(mettre dans une rectangle) dans l'imgae segmenté.

Cordialement.

C'est pas dit que toutes les composantes rentrent dans des rectangles disjoints. Il y a de grande chance que les rectangles se superposent ou s'incluent mutuellement. Par exemple sur un symbole ying-yang.

[Anis99]

Envoyé par pseudocode

C'est pas dit que toutes les composantes rentrent dans des rectangles disjoints. Il y a de grande chance que les rectangles se superposent ou s'incluent mutuellement. Par exemple sur un symbole ying-yang.

je sais mais c'est pas grave , car moi je le veux juste question de faire apparaitre les composantes connexes (faire convaincre que l'image a subi une operation de segmentation )et de plus si vous avez une meilleur idée je suis a votre disposition.

Cordialement.

[pseudocode]

Envoyé par Anis99

je sais mais c'est pas grave , car moi je le veux juste question de faire apparaitre les composantes connexes (faire convaincre que l'image a subi une operation de segmentation )et de plus si vous avez une meilleur idée je suis a votre disposition.

Code java :

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
 
// calcul des composantes connexes
int[][] rmap = new CCLabeling(image,W,H).compute();
 
// compte le nombre de labels
int labels = 0;
for(int y=0;y<H;y++) 
	for(int x=0;x<W;x++) 
		if (rmap[x][y]>labels) labels=rmap[x][y];
 
// recherche des coordonnées min/max de chaque composante
int[][] bounds = new int[labels+1][];
for(int y=0;y<H;y++)
	for(int x=0;x<W;x++) {
		// composante du pixel x,y
		int num = rmap[x][y];
 
		// mise a jour du rectangle englobant
		int[] rect = bounds[num];
		if (rect==null)
			bounds[num] = new int[] {x,y,x,y};
		else {
			if (x<rect[0]) rect[0]=x;
			if (y<rect[1]) rect[1]=y;
			if (x>rect[2]) rect[2]=x;
			if (y>rect[3]) rect[3]=y;
		}
	}
 
// affichage des rectangles englobants dans une image
BufferedImage output = new BufferedImage(W, H, BufferedImage.TYPE_INT_RGB);
Graphics2D g2d = output.createGraphics();
for(int i=1;i<=labels;i++) {
	int[] rect = bounds[i];
	g2d.drawRect(rect[0], rect[1], rect[2]-rect[0], rect[3]-rect[1]);
}

[Anis99]

Envoyé par pseudocode

Code java :

Bonsoir ;
je tien a vous remercié pour toutes l'aides que vous m'avez apporter!
ce code permet d'afficher seulement les rectangles, tandis que moi je veux que les rectangles ainsi que les ecritures

Cordialement

[pseudocode]

Envoyé par Anis99

Bonsoir ;
je tien a vous remercié pour toutes l'aides que vous m'avez apporter!
ce code permet d'afficher seulement les rectangles, tandis que moi je veux que les rectangles ainsi que les ecritures

Cordialement

Et bien dessine les rectangles sur l'image d'origine plutot que sur une image vierge.

[Anis99]

Bonjour;
je vais demander de bien vouloir m'accorder ce service qui de m'expilquer le code CClabeling car j'ai des truc qui m'echape afin que je puisse rediger un article

Cordialement.

[allissaid]

Salut ! Merci beaucaup pour la contribution, c'est superbe.

Es qu'il y à quelque façon de modifier l'algorithme parce que les pixels de background (pixels egale a 0) dans image[x][y] ne soient pas etiquetes et
ills resten en 0?

Arrevoir !

(excuses moi pour mon français.. je l'ai oublié)

[zuulcoder]

J'ai tenté de porter l'algorithme "Union / Find" en Delphi 7 à partir de celui proposé par Pseudocode en C.
Je me heurte à un soucis manifeste.
Le résultat ne me donne pas 19 étiquettes mais 174 et la visu de la matrice CCRoot confirme bien que ça merdoie quelquepart. La question à deux franc c'est : Où ?

Les deux algos C et Delphi me semblent identiques en tous points.
Quelqu'un à une idée ?
A noter que dans l'algo en C la fonction "CCadd" renvoi une valeur qui est stockée dans la variable "Root", mais cette valeur est écrasée par la réaffectation de Root := CC_NOROOT; en début de boucle. L'ago en Java ne renvoi rien pour cette même fonction. Normal ?

J'ai joint le programme exe et le source en PJ pour que chacun puisse se faire une idée.

http://imageshack.us/photo/my-images...ltaterron.png/

Code Delphi :

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
 
Var
  Image   :Array of Integer;
  CCroots :Array of Integer;
 
//==============================================================================
Procedure TForm1.CCinit(W,H:Integer);
Begin
  // Array to store the input bitmap as [X,Y] integer values...
  SetLength(Image,   W*H);
 
  // Array to store the output result as [X,Y] integer labels numbers...
  SetLength(CCRoots, W*H);
End;
 
//==============================================================================
Procedure TForm1.CCclear;
Begin
  // In Delphi the array are destroyed automatically when the form is destroyed.
  // So, it's not usefull to free the array manualy.
End;
 
//==============================================================================
// Find the root of the node at position "PosI"
//==============================================================================
Function TForm1.CCfind(PosI:Integer):Integer;
Begin
  While (CCroots[PosI] <> PosI) do Begin
    PosI := CCroots[PosI];
  End;
 
  Result := PosI;
End;
 
//==============================================================================
// Union of the 2 path formed by the 2 roots
//==============================================================================
Function TForm1.CCunion(Root0,Root1:Integer):Integer;
Begin
  If      (Root0 = Root1)     Then Result := Root0
  Else If (Root0 = CC_NOROOT) Then Result := Root1
  Else If (Root1 = CC_NOROOT) Then Result := Root0
  Else If (Root0 < Root1)     Then Begin
    CCroots[Root1] := Root0;
    Result := Root0;
  End Else Begin
    CCroots[Root0] := Root1;
    Result := Root1;
  End;
End;
 
//==============================================================================
// Set the root of the node at position pos
//==============================================================================
Function TForm1.CCadd(PosI,Root:Integer):Integer;
Begin
  If (Root = CC_NOROOT) Then CCroots[PosI] := PosI
                        Else CCroots[PosI] := Root;
  Result := CCroots[PosI];
End;
 
//==============================================================================
// Return and build the connected component labels array
//==============================================================================
Procedure TForm1.CClabel(W,H:Integer);
Var x,y,root,PosI            :Integer;
    TheLabel                 :Integer;
 
Begin
  PosI := 0;
 
  For Y := 0 to H - 1 do Begin
    For X := 0 to W - 1 do Begin
      Root := CC_NOROOT;
 
      If ( (X>0)   And (Image[PosI - 1] = Image[PosI]))               Then Root := CCunion(CCfind(PosI - 1),     Root);
      If ( (X>0)   And (Y>0) And (Image[PosI - 1 - W] = Image[PosI])) Then Root := CCunion(CCfind(PosI - 1 - W), Root);
      If ( (Y>0)   And (Image[PosI - W] = Image[PosI]))               Then Root := CCunion(CCfind(PosI - W),     Root);
      If ( (X<W-1) And (Y>0) And (Image[PosI + 1 - W] = Image[PosI])) Then Root := CCunion(CCfind(PosI + 1 - W), Root);
 
      CCadd(PosI, Root);
 
      Inc(PosI);
    End;
  End;
 
  // Remove indirection...
  For PosI := 0 to (W * H) - 1 do Begin
    CCroots[PosI] := CCfind(PosI);
  End;
 
  // Relabel...
  TheLabel := 1;
  For PosI := 0 to (W * H) - 1 do Begin
    If (CCroots[PosI] = PosI) Then Begin
      Memo.Lines.Add(IntToStr(TheLabel));
      CCroots[PosI] := TheLabel;
      Inc(TheLabel);
    End Else Begin
      CCroots[PosI] := CCroots[CCroots[PosI]];
    End;
  End;
End;

[pseudocode]

Envoyé par zuulcoder

A noter que dans l'algo en C la fonction "CCadd" renvoi une valeur qui est stockée dans la variable "Root", mais cette valeur est écrasée par la réaffectation de Root := CC_NOROOT; en début de boucle. L'ago en Java ne renvoi rien pour cette même fonction. Normal ?

Effectivement, ca ne sert pas grand chose. Sans doute une information de débug que j'ai laissé trainer.

Les deux algos C et Delphi me semblent identiques en tous points.
Quelqu'un à une idée ?

Si ce n'est pas le code, c'est les données. Est-ce que tu es sur de ce qui est stocké dans ton tableau 'Image' ?

[zuulcoder]

Envoyé par pseudocode

Si ce n'est pas le code, c'est les données. Est-ce que tu es sur de ce qui est stocké dans ton tableau 'Image' ?

J'ai un début d'explication.
Les données sont bonnes. Ca déconne car le tableau utilisé n'est pas carré (448 * 146). Dès que je passe sur une matrice carrée cela fonctionne normalement. Je pense que cela vient de l'utilisation d'un tableau linéaire avec Delphi. Du coup j'ai tenté de passé par un tableau 2D standard pour le tableau "Image". Le résultat final est bon sauf que l'image a subie une rotation droite de 90° plus une symétrie axiale verticale

J'ai utilisé l'ago Java qui passe par un tableau 2D pour "Image"
La seule chose que j'ai modifié c'est la procédure "CClabel" :

Ancien code :

Code Delphi :

1
2
3
4
5
 
        If ( (X>0)   And (Image[PosI - 1] = Image[PosI]))               Then Root := CCunion(CCfind(PosI - 1),     Root);
        If ( (X>0)   And (Y>0) And (Image[PosI - 1 - W] = Image[PosI])) Then Root := CCunion(CCfind(PosI - 1 - W), Root);
        If ( (Y>0)   And (Image[PosI - W] = Image[PosI]))               Then Root := CCunion(CCfind(PosI - W),     Root);
        If ( (X<W-1) And (Y>0) And (Image[PosI + 1 - W] = Image[PosI])) Then Root := CCunion(CCfind(PosI + 1 - W), Root);

Nouveau code avec tableau 2D :

Code Delphi :

1
2
3
4
5
 
        If ( (X>0)   And (Image1[X-1,Y] = Image1[X,Y]))             Then Root := CCunion(CCfind(PosI - 1),     Root);
        If ( (X>0)   And (Y>0) And (Image1[X-1,Y-1] = Image1[X,Y])) Then Root := CCunion(CCfind(PosI - 1 - W), Root);
        If ( (Y>0)   And (Image1[X,Y-1] = Image1[X,Y]))             Then Root := CCunion(CCfind(PosI - W),     Root);
        If ( (X<W-1) And (Y>0) And (Image1[X+1,Y-1] = Image1[X,Y])) Then Root := CCunion(CCfind(PosI + 1 - W), Root);

Et le résultat :
http://imageshack.us/photo/my-images/706/rotationb.png/

[pseudocode]

Envoyé par zuulcoder

Du coup j'ai tenté de passé par un tableau 2D standard pour le tableau "Image". Le résultat final est bon sauf que l'image a subie une rotation droite de 90° plus une symétrie axiale verticale

C'est surement les coordonnées Y et X qui sont inversées dans ton tableau image. Je suppose qu'en Delphi il faut mettre le Y avant le X (Image1[Y,X])

[zuulcoder]

Envoyé par pseudocode

C'est surement les coordonnées Y et X qui sont inversées dans ton tableau image. Je suppose qu'en Delphi il faut mettre le Y avant le X (Image1[Y,X])

En effet, le transfert dans le canva de l'image finale était inversé en X/Y

Voilà, donc l'ago finalisé porté en Delphi 7 :
Merci pour l'aide apportée

Code Delphi :

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
 
Var
  SizeX   :Integer;
  SizeY   :Integer;
 
  CCroots :Array of Integer;
  Image1  :Array of Array of Integer;
 
//==============================================================================
Procedure CCinit(W,H:Integer);
Var I                        :Integer;
Begin
  // Définition de la taille du tableau image initial 2D en dynamique...
  SetLength(Image1,   SizeY);
  For I := 0 to SizeY - 1 do Begin
    SetLength(Image1[I],   SizeX);
  End;
 
  // Array to store the output result as [X,Y] integer labels numbers...
  SetLength(CCRoots, W*H);
 
End;
 
//==============================================================================
Procedure CCclear;
Begin
  // In Delphi the array are destroyed automatically when the parent form is destroyed.
  // So, it's not usefull to free the array manualy.
End;
 
//==============================================================================
// Find the root of the node at position "PosI"
//==============================================================================
Function CCfind(PosI:Integer):Integer;
Begin
  While (CCroots[PosI] <> PosI) do Begin
    PosI := CCroots[PosI];
  End;
 
  Result := PosI;
End;
 
//==============================================================================
// Union of the 2 path formed by the 2 roots
//==============================================================================
Function CCunion(Root0,Root1:Integer):Integer;
Begin
  If      (Root0 = Root1)     Then Result := Root0
  Else If (Root0 = CC_NOROOT) Then Result := Root1
  Else If (Root1 = CC_NOROOT) Then Result := Root0
  Else If (Root0 < Root1)     Then Begin
    CCroots[Root1] := Root0;
    Result := Root0;
  End Else Begin
    CCroots[Root0] := Root1;
    Result := Root1;
  End;
End;
 
//==============================================================================
// Set the root of the node at position pos
//==============================================================================
Function CCadd(PosI,Root:Integer):Integer;
Begin
  If (Root = CC_NOROOT) Then CCroots[PosI] := PosI
                        Else CCroots[PosI] := Root;
  Result := CCroots[PosI];
End;
 
//==============================================================================
// Return and build the connected component labels array
//==============================================================================
Procedure CClabel(W,H:Integer);
Var x,y,root,PosI            :Integer;
    TheLabel                 :Integer;
 
Begin
  PosI := 0;
 
  For Y := 0 to H - 1 do Begin
    For X := 0 to W - 1 do Begin
      Root := CC_NOROOT;
 
      If ( (X>0)   And (Image1[X-1,Y] = Image1[X,Y]))             Then Root := CCunion(CCfind(PosI - 1),     Root);
      If ( (X>0)   And (Y>0) And (Image1[X-1,Y-1] = Image1[X,Y])) Then Root := CCunion(CCfind(PosI - 1 - W), Root);
      If ( (Y>0)   And (Image1[X,Y-1] = Image1[X,Y]))             Then Root := CCunion(CCfind(PosI - W),     Root);
      If ( (X<W-1) And (Y>0) And (Image1[X+1,Y-1] = Image1[X,Y])) Then Root := CCunion(CCfind(PosI + 1 - W), Root);
 
      CCadd(PosI, Root);
 
      Inc(PosI);
    End;
  End;
 
  // Merge left and right borders...
  PosI := 0;
  For Y := 0 to H - 1 do Begin
    If (Image1[0,Y] = Image1[W-1,Y]) Then CCunion(CCfind(PosI), CCfind(PosI+W-1));
    PosI := PosI + W;
  End;
 
  // Merge top and bottom border...
  PosI := 0;
  For X := 0 to W - 1 do Begin
    If (Image1[X,0] = Image1[X,H-1]) Then CCunion(CCfind(PosI), CCfind(PosI+(H-1)*W));
    PosI := PosI + 1;
  End;
 
  // Remove indirection...
  For PosI := 0 to (W * H) - 1 do Begin
    CCroots[PosI] := CCfind(PosI);
  End;
 
  // Relabel...
  TheLabel := 1;
  For PosI := 0 to (W * H) - 1 do Begin
    If (CCroots[PosI] = PosI) Then Begin
      CCroots[PosI] := TheLabel;
      Inc(TheLabel);
    End Else Begin
      CCroots[PosI] := CCroots[CCroots[PosI]];
    End;
  End;
End;