Discussion :

[pseudocode]

Bonjour,

je souhaite vous soumettre une petite recherche d'algo.

Le probleme consiste a trouver le point suivant d'une spirale discrete, je m'explique:

- Au depart, on a un point P(0) de coordonnées discretes (x,y) (= un pixel)
- Le point suivant, P(1), est le point gauche voisin de P(0)
- ... et ainsi de suite: P(N+1) etant toujours un voisin de P(N) tel qu'on obtienne une spirale:

Code :

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

1
2
3
4
5
   ______
  |  __  |
  | |_ | |
  |____| |
    ...__|

Si vous avez des idées pour calculer P(N+1) connaissant N, P(N), x, y, ...

[Nemerle]

Deux possibilités ci-dessous. Dans tous les cas tu tournes tj à droite.

1. Tu stockes la position (x,y), la direction et le "nombre de pas" N que tu dois faire dans la même direction. A chaque étape tu avances d'un (soit +/-1 sur x ou y) en décrémentant un index i égal à N au début; quand N=0, tu "tournes" et tu fais i=N+1, et tu recommences

2. Si tu as une table T[x,y] ou tu indiques si tu es passé par (x,y), alors tu ne stockes que la position et la direction, et en (x,y) tu regardes si tu es passé par le point à droite de (x,y): si oui tu continues dans ta direction, sinon tu passes à ce point en changeant ta direction.


--> la direction, c'est un vecteur (a,b) ou a,b=-1,0 ou 1. Exemple vers le haut: (0,-1), tu passes de (x,y) à (x,y)+(0,-1)=(x,y-1). Quand tu tournes, tu passes ta direction de (0,-1) à (1,0) (direction vers la droite)...

[pseudocode]

Deux possibilités ci-dessous. Dans tous les cas tu tournes tj à droite.

C'est cool ca... Ca me parrait une super méthode.

De plus, je viens de remarquer que le nombre de "step" a faire suit une logique simple:

avance de 1 pixel + tourne a droite
avance de 1 pixel + tourne a droite
2x avance de 1 pixel + tourne a droite
2x avance de 1 pixel + tourne a droite
3x avance de 1 pixel + tourne a droite
3x avance de 1 pixel + tourne a droite
...

Ce qui conduit a:
N=0: position initiale
N=1: direction=gauche
N=2: direction=haut
N=3,4: direction=droite
N=5,6: direction=bas
N=7,8,9: direction=gauche
N=10,11,12: direction=haut
...

Les directions sont répetitives: une liste circulaire contenant [G,H,D,B]. Il reste a savoir quand "incrementer" l'index de la liste (et faire un modulo 4)

Sur mon exemple, on incremente l'index de la liste pour N=1,2,4,6,9,12,...
Je peux toujours pré-calculer cette liste, ou meme calculer la prochaine valeur "dynamiquement".

Mais pour la beauté des mathématiques, je me demande si on peut trouver une fonction F(N) qui indique la direction a suivre, uniquement en fonction de N... ?

[Zavonen]

La spirale est formée de carrés concentriques.
Le premier carré est constitué du seul pixel initial
Le second est constitué de 8 pixels (coordonnées entre -1 et +1 sauf (0,0))
Le troisième est constitué de 16 pixels (coordonnées entre -2 et 2 sauf les précédents)

Pour n>=1,le n-ième comporte 8*(n-1) pixels (coordonnées entre -(n-1) et +(n-1) sauf...)

Le point d'entrée dans le second carré est (-1,0)
Le point d'entrée dans le troisième carré est (-2,-1)

Le point d'entrée dans le n-ième carré est (-(n-1),-(n-2))

On désigne par n l'ordre d'un point dans la spirale, x(n), y(n) ses coordonnées.
Tout revient à trouver x(n) et y(n) en fonction de n

Les points d'entrée ont pour ordre: 2,10, 26,..., 2+4*k*(k+1)=f(k)

Tout revient donc dans un premier temps à situer n relativement à la suite des points d'entrée f(k). On sait alors sur quel carré on se trouve.

Supposons n= f(k) + h et n<f(k+1)
donc h <8*(k+1)
8*(k+1) étant le périmétre du carré de rang k+2
le côté de ce carré étant 2k+1
On sait alors que -(k-1) <x(n) < +(k+1), idem pour y(n)
Pour finir on détermine x(n) et y(n) avec précision suivant les valeurs de h par rapport à 2k+1 en tournant.

[Zavonen]

On peut aussi concevoir une méthode récurrente comme suit:
On considère une matrice carrée binaire d'ordre, disons 11 pour fixer les idées.
On met tous les coeff à zéro sauf le 'centre' C(5,5), point de départ de la spirale, qui vaut 1.
On remarque que si M1(x1,y1) et M2(x2,y2) sont deux points, le nombre
Sup(|x1-y1|,|x2-y2|) est une distance.
Pour cette distance la spirale s'obtient en décrivant successivement les 'cercles' de rayon 0, 1, 2, etc... (qui sont en fait des carrés)
La façon dont passe d'un 'cercle' au suivant dépend de la construction du second point à partir du premier. on peut par exemple prendre une translation de vecteur V par exemple (-1,0).
Une méthode pour déterminer un point P(n+1) à partir du précédent P(n), peut donc se décrire comme suit:
1) On détermine d'abord tous les voisins immédiats de P(n), obtenus en faisant un pas dans une direction quelconque . Parmi ces voisins on détermine ceux qui ne sont pas encore 'marqués' (coef = 0) (2 ou 3 poss) et qui sont à même distance de C que P(n) (0 ou 1 poss). On peut démontrer que seulement deux cas sont possibles:
1) Il n'existe aucune solution
2) Il existe une solution unique.
Dans le cas 1) On a déja complété le 'cercle'. P(n+1) s'obtient donc à partir de P(n) par une translation de vecteur V, on passe au 'cercle' suivant.
Dans le cas 2) l'unique solution est P(n+1), on reste sur le même 'cercle'.
Dans les deux cas on marque et on continue.

[souviron34]

j'ai déjà implanté un truc comme ça (d'ailleurs, c'est pour les contours dans le post que j'ai mis :-) ) ..


Moi ce que j'ai fais c'est :

1) tu détermines ton rayon r
2) tu fais une boucle ir de 1 à r

3) tu fais une boucle de [(x-ir),(y-ir)] à [(x-ir),(y+ir)] (côté gauche)
4) tu fais une boucle de [(x-ir),(y+ir)] à [(x+ir), (y+ir)] (côté supérieur)
5) tu fais une boucle de [(x+ir),(y+ir)] à [(x+ir),(y-ir)] (côté droit)
6) tu fais une boucle de [(x+ir),(y-ir)] à [(x-ir),(y-ir)] (côté bas)

Bon, sur les images en général bas et haut sont inversés, mais avec ça tu fais le tour, par cercles croissants.

[pseudocode]

J'ai implémenté l'algo avec la liste circulaire des directions (2 listes en fait: dx[] et dy[]). Ca marche bien.

Le code en Java, pour la postérité:

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
/**
 * Parcours en spirale
 * 
 * @param x0 position X initiale
 * @param y0 position Y initiale
 * @param distanceMax distance a parcourir
 */
void move(int x0, int y0, int distanceMax) {
	// directions possibles: G=(-1,0) H=(0,-1) D=(1,0) B=(0,1)
	int[] dx = new int[] {-1,0,1,0};
	int[] dy = new int[] {0,-1,0,1};
	int dirIndex=0;
 
	// distance parcourue
	int distance=0;
 
	// nombre de pas a faire
	int stepToDo=1;
 
	// position courante
	int x=x0, y=y0;
	System.out.println("Initial position: " +x+","+y);
 
	while (true) {
 
		// a faire 2 fois avec le meme nombre de pas (gauche+haut) ou (droite+bas) 
		for (int i = 0; i < 2; i++) {
 
			// déplacement du nombre de pas
			for (int j = 0; j < stepToDo; j++) {
 
				// condition de sortie
				distance++;
				if(distance>distanceMax) return;
 
				// déplacement
				x+=dx[dirIndex];
				y+=dy[dirIndex];
 
				System.out.println("Current position: " +x+","+y+" distance="+distance);
			}
 
			// tourne a droite
			dirIndex = (dirIndex + 1) % 4;
		}
 
		// incrementer le nombre de pas a faire
		stepToDo++;
	}
 
}

Merci a tout le mode...

[Nemerle]

merci du code

C'est dingue comme certaines réposnes cherchent justes à complexifier le problème..........

[Zavonen]

Mais pour la beauté des mathématiques, je me demande si on peut trouver une fonction F(N) qui indique la direction a suivre, uniquement en fonction de N... ?

C'est même mieux, on vous dit exactement où aller...
Pour la postérité aussi :
Le code C qui donne DIRECTEMENT les coordonnées du point d'indice n de la spirale.
Méthode développée dans les deux posts précédents

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
#include <stdio.h>
#include <stdlib.h>
 
// retourne les carrés des nombres impairs
int f( int k)
{ return (2*k+1)*(2*k+1);}
 
// détermine sur quel cercle on se trouve
int Trouve_k(int n)
{ int i;
   for( i=0; f(i)<=n;i++);
   return i;
}
 
// détermine la position sur le cercle
// à partir du coin inférieur gauche
int Trouve_h(int n)
{  int k= Trouve_k(n);
    return ((8*k+(n-f(k))+1))%(8*k);}
 
 
// calcule le décalage par rapport à ce même coin
void Offset (int k, int h, int O[2])
{ int q=h/(2*k);
  int r=h-q*2*k;
  switch (q)
  { case 0: O[0]+=0;O[1]+=r; break;
    case 1: O[1]+=2*k;O[0]+=r; break;
    case 2: O[0]+=2*k;O[1]+=2*k-r;break;
    default: O[1]+=0;O[0]+=2*k-r;break;
  }
}
 
// met dans P les coordonnées du point d'indice n de la spirale (n>1)
void Pos (int n, int P[2])
{ int k=Trouve_k(n);
  int h=Trouve_h(n);
  P[0]=-k;
  P[1]=-k;
  Offset(k,h,P);
}
 
 
// essai
void test()
{ int A[2];
  int n;
  for (n=1;n<30;n++)
   {Pos(n,A);
   printf("(%d,%d)\n",A[0],A[1]);
   }
}
 
 
int main()
{
    test();
	return 0;
}

[Nemerle]

Etant matheux, j'aime la postérité... quand elle est utile.....

ici, une programmation standard est bien plus "rapide"!

[Zavonen]

J'essaie de répondre, dans la mesure du possible aux questions qui sont posées, dans la mesure où je les comprends et même si elles n'ont pour moi aucun intérêt immédiat. C'est le premier point!
Pour le reste les gens sur ce forum savent lire et penser. Nemerle, ils n'ont pas besoin de vos exégèses et de vos jugements de valeur à l'emporte pièce pour se faire une opinion.

[pseudocode]

Restons calme et courtois...

C'est vrai qu'en terme de programmation, etant donné que je dois tracer toute la spirale, la methode itérative est la meilleur pour moi.

Je posais juste la question du "calcul direct" a titre de curiosité mathématique. Et je suis epaté que Zavonen ait trouvé (meme s'il reste encore une bouche for dans Trouve_k() )

[Zavonen]

Je posais juste la question du "calcul direct" a titre de curiosité mathématique. Et je suis epaté que Zavonen ait trouvé (meme s'il reste encore une bouche for dans Trouve_k() )

Bien vu !
Prenons le cas où on veut remplir un écran 1000*1000 avec un million de pixels. Pour le pixel d'ordre 1000000 il faudra faire une boucle qui sera parcourue un certain nombre de fois, ce nombre est facile à trouver il correspond au plus grand carré impair situé avant 1000000 disons encore à une unité près 1000 itérations, ce qui n'est pas énorme car la boucle est presque vide, elle se résume à l'incrémentation et au test.
Toutefois, s'il fallait passer au turbo, il faudrait mettre les 1000 carrés impairs dans un tableau et faire une recherche dichotomique sur ce tableau, au lieu de cette boucle for. On passe alors en log2(1000) soit environ 10 itérations.
Il n'en reste pas moins que pour votre problème la solution Nemerle est plus adaptée à vos besoins et tout le monde (même moi) peut le comprendre. Elle vous satisfait, vous l'avez dit, problème résolu, point barre. Ce qui n'empêche pas d'essayer de répondre à vos questions et de proposer d'autres possibilités, même si elles sont trop complexes pour le 'mathématicien autoproclamé' dont nous parlons.
Tout mathématicien 'véritable' aurait pu, au contraire, être positif et faire profiter le groupe de la remarque suivante:
La fonction que je décris réalise une bijection de N sur Z^2. cet enroulement de (tous) les points à coordonnées entières positives ou négatives en spirale, réalise une bijection de N sur (2N)*(2N). Elle établit donc d'un seul coup, les deux inégalités:
card(N+N) <card(N)
card(NxN) <card(N)
Ceci est, historiquement, la base de la 'théorie des nombres transfinis' de G. Cantor, fondement de la théorie moderne des ensembles.
La plupart des bouquins de maths, proposent au lieu de cela la fameuse 'énumération diagonale' réalisant la bijection N sur NxN, moins forte et moins esthétique, en tout cas moins originale.
Il m'arrive, dans d'autres discussions où vous participez aussi (on vous voit partout Pseudocode, et le plus souvent pour le meilleur...) de faire des suggestions inadaptées. Il se trouve que vous prenez le temps, ainsi que d'autres de me dire poliment et gentiment pourquoi cela ne convient pas, ce que j'apprécie à sa juste valeur.
J'ai réagi ici , non pas pour gâcher cette discussion, mais parce que j'en assez de voir Nemerle défouler son agressivité sur n'importe qui en fonction de ses humeurs. Il m'arrive d'avoir cet honneur (je veux dire de déclencher les foudres de notre matheux de service), mais parfois ce sont d'autres qui se voient traiter de débile, CPPN, etc...

[pseudocode]

Après toutes ces explications, je commence a comprendre un peu plus clairement votre raisonement. L'approche par bijection de Z sur Z^2 me plait beaucoup, d'autant plus que c'est ce que je cherchais a faire au départ.

Pour la petite histoire, je fais un traitement d'image et je dois appliquer un filtre. Le calcul effectué par le filtre est une prédiction de la prochaine valeur d'un signal discret a une dimension.

Donc pour appliquer sur mon image 2D, j'ai eu l'idée de transformer la zone autour d'un pixel en signal 1D. D'ou la spirale.

La conclusion de tout cela etant que ca ne marche pas.

Je ne sais pas si ca vient du filtre ou de mon approche pour le moins "originale". Je vais essayer avec l'approche plus classique: filtrage sur la verticale, puis, filtrage sur l'horizontale et enfin "melange" des deux résultats.

[Zavonen]

Je ne sais pas si ca vient du filtre ou de mon approche pour le moins "originale". Je vais essayer avec l'approche plus classique: filtrage sur la verticale, puis, filtrage sur l'horizontale et enfin "melange" des deux résultats.

Désolé de ne pouvoir vous aider, je ne connais pas grand chose (à mon grand regret) en imagerie numérique. Je m'y entends (un peu) en dessin vectoriel.

[mchk0123]

Avec mes maigres connaissances en traitement d'image :

Je ne sais pas si ca vient du filtre ou de mon approche pour le moins "originale". Je vais essayer avec l'approche plus classique: filtrage sur la verticale, puis, filtrage sur l'horizontale et enfin "melange" des deux résultats.

Il est plutôt recommendé d'utiliser des filtres 2D sur une image, que de passer en 1D filtrer, et repasser en 2D. Les filtres 2D tirant partie de plus d'informations, nottament de tous les voisins (3x3 ou 5x5, ...) et non uniquement des points précédents et suivants.

Pour l'exemple, si tu applique un filtre 1D moyenneur sur ta spirale et que tu reconstruit l'image en 2D, elle sera de "moins bonne qualitée" qu'aprés un passage à un filtre moyenneur 2D.

[souviron34]

Je ne sais pas si ca vient du filtre ou de mon approche pour le moins "originale". Je vais essayer avec l'approche plus classique: filtrage sur la verticale, puis, filtrage sur l'horizontale et enfin "melange" des deux résultats.

Comme l'a dit mchk0123, classiquement c'est des filtres 2D (gaussien, sobel, etc..).

Tu veux faire une image "prévue", c'est ça ? à partir de l'image originale et de la prévision d'un signal ?

Mais je me pose la question d'un signal 1D affectant une image 2D .... A moins que ce soit style FFT...

[pseudocode]

C'est clair que ca serait mieux avec un filtre 2D.

Le probleme c'est que je n'ai pas accès au code du filtre. Il est livré sous forme d'une dll. Donc je dois me conformer a l'interface du filtre qui veut un signal 1D...

Apres tests, les résultats sont un poil meilleurs en moyennant le filtrage horizontal + vertical. Mais ca reste vraiment pas terrible.

Je vais donc mettre ce filtre a la poubelle et devoir en construire un, en 2D.
Je vais surement solliciter votre aide d'ailleur...

A bientot dans un autre post

[mchk0123]

Bon petite bidouille possible avant de jeter définitivement l'éponge.

Tu as pensé à faire tourner ton filtre 4 fois ?

Je m'explique, lancer le filtre une fois en vertical, une autre fois en horizontal, ça ne suffit pas. En effet tu perd l'effet combiné x & y.

Donc l'idée est de lancer le filtre 2x de plus en utilisant toujours le principe de 1x vertical et 1x horizontal mais cette fois çi, sur un repère cartésien aprés rotation de 45°. Autrement dit tu parcours ton image selon chaque diagonale.
C'est galère pour le calcul des extrémitées en x' et y', mais ça reste faisable.

A la fin tu moyenne sur tes 4 images résultantes, ou même mieux tu pondères les images sur x & y avec un coef 2, et les images sur x' et y' avec un coef 1.

[souviron34]

mais physiquement qu'est-ce qu'il est censé représenter, ton filtre ?

J'avoue que j'ai du mal à comprendre comment un filtre 1D peut avoir une influence sur une image 2D.... Comme je disais plus haut, si c'est une FFT, OK. Mais en dehors de ça, je ne vois pas trop...