[débutant] Actions dans une boucle non effectuées

**Diegoooowwww** · 27/12/2008, 22h07

Bonsoir,

je travaille actuellement (dans le cadre des TIPE, je suis étudiant en spé) sur un programme de compression fractale d'images en ocaml. Je programme actuellement l'algorithme le plus "naïf" qui puisse exister avant de passer à des choses plus poussées (arbres, réseaux de neurones...), et j'arrive à la fin.
Pour rappeler brièvement le principe, il s'agit de trouver des parties qui se ressemblent dans les images, pour cela on constitue 2ensembles, un ensemble de départ (les "Di", i etant un indice) et un ensemble d'arriver (les "Ri", idem). Le but est de trouver pour chaque élément de l'ensemble d'arrivé (Ri) l'élément de l'ensemble de départ (Di) qui lui soit le plus proche (au sens d'une distance préalablement définie).
Pour ce faire, dans l'algorithme programmé, on compare chaque élément de l'ensemble de départ aux 8 isométries (nos éléments sont des carrés) de chaque élément de l'ensemble d'arrivée, apres avoir préalablement effectué une opération de contrastage adéquate, et l'on répertorie ces distances dans un tableau final.
Le problème ce situe là exctement : la fonction qui crée cette matrice (car c'en est une) laisse des "cases vides". Si quelqu'un a une idée... je m'arrache les cheveux depuis quelques temps déjà dessus.

Voilà la fonction en question :

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
let compare n ensemble_ri ensemble_di =
						let nvx_di = resize_di ensemble_di in
						let result = make_array2D 8 nbri (0.,0,(0.,0.)) in
						let d = ref (foi max_int) in
						for i = 0 to (nbri-1) do
							for j = 0 to 7 do
								for k = (((n-1)*nbdiv)/10) to ((n*nbdiv)/10 - 1) do
									let (s,o) = minimise j nvx_di.(k) ensemble_ri.(i) in
									let distance = dist.(j) (s,o) nvx_di.(k) ensemble_ri.(i) in
									if !d > distance then	begin
															d:=distance; (result,i,j) <== (!d,k,(s,o));
															end
								done;
							done;
						done;
						result;;

Quelques explications :

les éléments des ensembles sont des images considérées comme des tableaux de points.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
```
type point = {x:float; y:float; z:int};; (*z est le niveau de gris*)
```
l'indice n dans la boucle vient du fait de l'extrême lenteur du programme (plusieurs heures...) et permet de le faire tourner par "petits bouts".
la fonction resize permet simplement de mettre les Di à la taille des Ri, ceux ci étant plus grands
la fonctin make_array2D crée un élément de type :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
```
type 'a array2D = {mutable l:int; mutable h:int; mutable m: 'a array};; (* l=largeur, h=hauteur, m=matrice *)
```
une matrice qui contient ses dimensions.
les fonctions (<==) et (==>) correspondent à . et (<-) pour le type array2D
minimise renvoi un couple d'arguments relatifs à la modification de contraste.
dist est un tableau de fonctions de distances pour comparer deux images ; elles représentent la même distance mais parcourent les tableaux différement pour ne pas avoir à créer les 8 isométries pour élément de l'ensemble d'arrivée.
dans minimise et dist, l'argument j est relatif a l'isométrie utilisée.

Enfin voilà le résultat que me donne ocaml :

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
val distances_1 : (float * int * (float * float)) array2D =
  {l = 8; h = 256;
   m =
    [|(1837.7342502382164, 1068, (-0.391495902739304, 244.02251712247994));
      (291.4579768289891, 954, (-0.25382715282694412, 217.67660388802841));
      (158.45695204940708, 1260, (-0.10027961452777623, 184.22643549835834));
      (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (119.88876626215378, 761, (-0.074536402037438776, 179.37773960370492));
      (0., 0, (0., 0.));
      (33.358573672923484, 954, (-0.069710805193329631, 214.877416080155));
      (1772.6080616405955, 1020, (0.36380218370732209, 155.20730250285166));
      (0., 0, (0., 0.));
      (137.51816702819963, 142, (0.15595973079704098, 148.8907614439068));
      (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (118.88483261873802, 771, (-0.064263054363027233, 177.34547825572159));
      (0., 0, (0., 0.));
      (30.08391824429351, 800, (0.0708221806709118, 198.76268753249187));
      (0., 0, (0., 0.)); (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (112.37994194191872, 112, (-0.19982617090941432, 200.47882574488057));
      (0., 0, (0., 0.)); (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (0., 0, (0., 0.)); (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (0., 0, (0., 0.)); (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (21.418990720563656, 373, (-0.08941144795550951, 216.88315759437529));
      (0., 0, (0., 0.)); (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (0., 0, (0., 0.)); (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (0., 0, (0., 0.)); (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (0., 0, (0., 0.)); (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (0., 0, (0., 0.)); (0., 0, (0., 0.)); (0., 0, (0., 0.));
      (0., 0, (0., 0.)); (0., 0, (0., 0.)); (0., ...); ...|]}

PS : si besoin je peux fournir d'autres parties du code, celui ci étant relativement important j'ai préféré vous éviter des fonctions inutiles. Si vous voulez l'intégralité du code, je préfère l'envoyer par mp, pour de simples raisons de confidentialité dans le cadre des TIPE...

Merci d'avance et bonne soirée

**InOCamlWeTrust** · 28/12/2008, 00h01

Montre make_array2D... si ça se trouve, c'est l'erreur classique en un peu plus sioux.

D'un autre côté, tu n'as pas vraiment besoin des largeurs et hauteurs des matrices, puisqu'elles sont fournies par l'implantation... mais j'avoue ne pas avoir lu l'intégralité de ton code.

**Diegoooowwww** · 28/12/2008, 00h25

Code :

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

1
2
3
let make_array2D larg haut a = let tab = Array.make (larg*haut) a in {l=larg; h=haut; m=tab};;
let (==>) mat (i,j) = let n = j*(mat.l)+i in mat.m.(n);;
let (<==) (mat,i,j) k = let n = j*(mat.l)+i in mat.m.(n)<-k;;

Disons que les dimensions des matrices sont pratiques pour les fonctions de changement de taille des images... Mais il est vrai que je me suis rendu compte plus tard qu'une simple matrice aurait suffit, mais il aurait fallut remodifier tout le code.
J'y penserai peut être lors d'une optimisation future, cependant c'est assez pratique pour éviter les Array.length

De plus toutes les autres fonctions utilisant cette structure de données fonctionnent correctement.

alex_pi · 28/12/2008, 00h56

Envoyé par Diegoooowwww

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
let compare n ensemble_ri ensemble_di =
						let nvx_di = resize_di ensemble_di in
						let result = make_array2D 8 nbri (0.,0,(0.,0.)) in
						let d = ref (foi max_int) in
						for i = 0 to (nbri-1) do
							for j = 0 to 7 do
								for k = (((n-1)*nbdiv)/10) to ((n*nbdiv)/10 - 1) do
									let (s,o) = minimise j nvx_di.(k) ensemble_ri.(i) in
									let distance = dist.(j) (s,o) nvx_di.(k) ensemble_ri.(i) in
									if !d > distance then	begin
															d:=distance; (result,i,j) <== (!d,k,(s,o));
															end
								done;
							done;
						done;
						result;;

Salut

Si je comprends vaguement ton code, tu ne modifies le contenu d'une case que si !d est supérieur à distance. Il ne me semble donc pas illogique que parfois, tu ne modifies pas le contenue d'une case ! Je ne comprends pas vraiment ce que tu fais, mais il me parait étrange que d'un tour de boucle sur l'autre, tu conserves la valeur précédente de !d. Tu es sûr de cette partie là ?

Et pourquoi pour tes matrices bidimensionnelle, tu n'utilises pas... des matrices bidimensionnelle ? Genre un tableau de tableau quoi

Ca permet bêtement d'accéder à la case i, j par m.(i).(j). Ca me semble moins lourd, et probablement moins sujet à erreur que ta méthode. Fais juste attention de bien utiliser make_matrix pour la créer.

**Diegoooowwww** · 28/12/2008, 01h33

Alors j'ai déjà répondu à pourquoi pas une simple matrice, car premierement j'ai accès à ses dimensions, mais surtout parce que j'ai un moment besoin de rétrécir l'image et donc sans recréer de matrice je peux simplement modifier la hauteur et la largeur de l'array2D. Mais je conviens que cela est source éventuelle d'erreurs.

Cette fonction doit renvoyer un array2D tel que si on le nomme result :
let (d,k,(s,o)) = result.(i).(j);;
on sort bien du type float*int*(float*float) où
d est la distance de l'élément de départ indicé k à l'élément de l'ensemble d'arrivée indicé i ayant subit l'isométrie indicée j, (s,o) étant des paramètres de contraste associés à Di.(k) et Ri.(i) affecté de l'isométrie j.

(j'utilise la notation .(i).(j) afin de simplifier l'écriture, bien qu'elle differe de mon code)

Le but est de parcourir l'ensemble de départ (les Di) et de trouver pour chaque élément de l'ensemble d'arrivé celui qui est le plus proche (distance la plus petite). Cette fonction renvoi finalement la distance minimale de l'ensemble de départ à un élément de l'ensemble d'arrivé ayant subit une isométrie (renvoyer k et (s,o) permet de retrouver l'élément pour lequel le min est atteint).
Voilà pourquoi je ne modifie pas toujours la référence d : c'est le minimum relatif.

Aaaaaaah mais en écrivant je vient de me rendre compte qu'il fallait que je réinitialise la référence d à max_int a chaque nouveau passage dans la boucle... sinon il est effectivement plausible qu'il ne trouve plus de distance inférieure à d.
Je pense tenir ma réponse. Je testerai ca demain (question de temps) et vous tiens au courant, mais je pense que ce code devrait fonctionner :

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
let compare n ensemble_ri ensemble_di =
						let nvx_di = resize_di ensemble_di in
						let result = make_array2D 8 nbri (0.,0,(0.,0.)) in
						let d = ref (foi max_int) in
						for i = 0 to (nbri-1) do
							for j = 0 to 7 do
                                                        d := (foi max_int);
								for k = (((n-1)*nbdiv)/10) to ((n*nbdiv)/10 - 1) do
									let (s,o) = minimise j nvx_di.(k) ensemble_ri.(i) in
									let distance = dist.(j) (s,o) nvx_di.(k) ensemble_ri.(i) in
									if !d > distance then	begin
															d:=distance; (result,i,j) <== (!d,k,(s,o));
															end
								done;
							done;
						done;
						result;;

alex_pi · 28/12/2008, 10h45

Envoyé par Diegoooowwww

Alors j'ai déjà répondu à pourquoi pas une simple matrice, car premierement j'ai accès à ses dimensions, mais surtout parce que j'ai un moment besoin de rétrécir l'image et donc sans recréer de matrice je peux simplement modifier la hauteur et la largeur de l'array2D. Mais je conviens que cela est source éventuelle d'erreurs.

Euh.. Tu mets

Code :

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

1
2
3
4
let dim m = 
  let l = Array.length m in
  let c = if l = 0 then 0 else Array.length m.(0) in 
  (l,c);;

dans ton module de matrices bidimensionnelle, ça va, ça coute pas trop cher ! Et pour le changement de dimension en place, ça pue quand même l'optimisation inutile et génératrice d'erreurs.

Envoyé par Diegoooowwww

Aaaaaaah mais en écrivant je vient de me rendre compte qu'il fallait que je réinitialise la référence d à max_int a chaque nouveau passage dans la boucle... sinon il est effectivement plausible qu'il ne trouve plus de distance inférieure à d.

C'est ce que je disais...

**gasche** · 28/12/2008, 15h20

Code :

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

1
2
3
4
5
6
7
let d = ref (foi max_int) in
for i = 0 to (nbri-1) do
    for j = 0 to 7 do
        d := (foi max_int);
        (* ... *)
    done
done;

Caca.

Code :

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

1
2
3
4
5
6
for i = 0 to (nbri-1) do
    for j = 0 to 7 do
        let d = ref (foi max_int) in
        (* ... *)
    done
done;

Par ailleurs, ton excuse pour les matrices est bidon. Quand on a fait quelque chose de manière moche, et qu'on voit comment corriger, on corrige, point. Si ça t'oblige à modifier "tout ton code", c'est sans doute qu'il y a un défaut de conception, mais on ne laisse pas du code pas beau sous prétexte que hell, corriger c'est fatiguant.

**Diegoooowwww** · 28/12/2008, 16h38

Mon problème est résolu, merci.

Envoyé par bluestorm

Par ailleurs, ton excuse pour les matrices est bidon. Quand on a fait quelque chose de manière moche, et qu'on voit comment corriger, on corrige, point. Si ça t'oblige à modifier "tout ton code", c'est sans doute qu'il y a un défaut de conception, mais on ne laisse pas du code pas beau sous prétexte que hell, corriger c'est fatiguant.

Je suis parfaitement conscient de cela mais vois-tu pour l'instant il me reste beaucoup à faire et n'étant pas sûr de finir à temps je préfère dégrossir le travail et le fignoler après, ce qui bien sûr ne veut pas dire coder n'importe comment. Mais jusqu'à maintenant j'avais trop à faire pour m'occuper de changer ceci. Mais si cela peut en rassurer certains je ne comptais pas laisser cela tel quel indéfiniment.

**Garulfo** · 29/12/2008, 05h18

Envoyé par Diegoooowwww

[...]
Je suis parfaitement conscient de cela mais vois-tu pour l'instant il me reste beaucoup à faire et n'étant pas sûr de finir à temps je préfère dégrossir le travail et le fignoler après, ce qui bien sûr ne veut pas dire coder n'importe comment. Mais jusqu'à maintenant j'avais trop à faire pour m'occuper de changer ceci. Mais si cela peut en rassurer certains je ne comptais pas laisser cela tel quel indéfiniment.

Ça c'est aussi une mauvaise excuse

C'est en général un signe que le travail a été mal fait dès le début. C'est-à-dire que tu as sauté sur du code sans faire l'analyse et la conception proprement.

Bon maintenant que tu es rendu là, c'est vrai qu'il faut que tu te demandes ce qui vaut le mieux, continuer car le retour serait trop pénible ou faire le retour car continuer serait trop laborieux… Espérons que la prochaine fois tu t'y prendras mieux.

**Diegoooowwww** · 31/12/2008, 11h57

Je ne vais pas me répéter, mais c'est la seule fonction "non réfléchie" si j'ose dire. Tout le reste du code a été retravaillé pour être efficace (dans la limite du possible ^^), et je sais qu'il faut modifier ces array2D, ce que je ferai à la rentrée puisque j'ai maintenant fini mon objectif pour cette période.
Mais Garulfo a tout à fait raison le retour est relativement pénible et je prefèrait m'y consacrer quand il n'y aurait plus que ce problème là.

Envoyé par Garulfo

Espérons que la prochaine fois tu t'y prendras mieux.

Oui, c'était une de mes premières fonctions, que j'avoue avoir bâclée et m'en être aperçu bien tard.