# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  Parcours de pixels en spirale

## 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 coordonnes 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:


```

```

Si vous avez des ides pour calculer P(N+1) connaissant N, P(N), x, y, ...   ::mrgreen::

----------


## Nemerle

Deux possibilits 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 mme direction. A chaque tape tu avances d'un (soit +/-1 sur x ou y) en dcrmentant un index i gal  N au dbut; 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 possibilits ci-dessous. Dans tous les cas tu tournes tj  droite.


 ::yaisse::  C'est cool ca... Ca me parrait une super mthode.

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 rpetitives: 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 mathmatiques, 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 forme de carrs concentriques.
Le premier carr est constitu du seul pixel initial
Le second est constitu de 8 pixels (coordonnes entre -1 et +1 sauf (0,0))
Le troisime est constitu de 16 pixels (coordonnes entre -2 et 2 sauf les prcdents)

Pour n>=1,le n-ime comporte 8*(n-1) pixels (coordonnes entre -(n-1) et +(n-1) sauf...)

Le point d'entre dans le second carr est (-1,0)
Le point d'entre dans le troisime carr est (-2,-1)

Le point d'entre dans le n-ime carr est (-(n-1),-(n-2))

On dsigne par n l'ordre d'un point dans la spirale, x(n), y(n) ses coordonnes.
Tout revient  trouver x(n) et y(n) en fonction de n

Les points d'entre 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'entre 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 primtre du carr de rang k+2 
le ct de ce carr tant 2k+1
On sait alors que -(k-1)   <x(n) < +(k+1), idem pour y(n)
Pour finir on dtermine x(n) et y(n) avec prcision suivant les valeurs de h par rapport  2k+1 en tournant.

----------


## Zavonen

On peut aussi concevoir une mthode rcurrente comme suit:
On considre une matrice carre binaire d'ordre, disons 11 pour fixer les ides.
On met tous les coeff  zro sauf le 'centre' C(5,5), point de dpart 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 dcrivant successivement les 'cercles' de rayon 0, 1, 2, etc... (qui sont en fait des carrs)
La faon dont passe d'un 'cercle' au suivant dpend de la construction du second point  partir du premier. on peut par exemple prendre une translation de vecteur V par exemple (-1,0).
Une mthode pour dterminer un point P(n+1)  partir du prcdent P(n), peut donc se dcrire comme suit:
1) On dtermine d'abord tous les voisins immdiats de P(n), obtenus en faisant un pas dans une direction quelconque . Parmi ces voisins on dtermine ceux qui ne sont pas encore 'marqus' (coef = 0) (2 ou 3 poss) et qui sont  mme distance de C que P(n) (0 ou 1 poss). On peut dmontrer que seulement deux cas sont possibles:
1) Il n'existe aucune solution
2) Il existe une solution unique.
Dans le cas 1) On a dja complt 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 mme 'cercle'.
Dans les deux cas on marque et on continue.

----------


## souviron34

j'ai dj 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 dtermines 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)] (ct gauche)
4)    tu fais une boucle de [(x-ir),(y+ir)]  [(x+ir), (y+ir)] (ct suprieur)
5)    tu fais une boucle de [(x+ir),(y+ir)]  [(x+ir),(y-ir)] (ct droit)
6)    tu fais une boucle de [(x+ir),(y-ir)]  [(x-ir),(y-ir)] (ct bas)Bon, sur les images en gnral bas et haut sont inverss, mais avec a tu fais le tour, par cercles croissants.

----------


## pseudocode

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

Le code en Java, pour la postrit:


```

```

Merci a tout le mode...  ::king::

----------


## Nemerle

merci du code  :;):  

C'est dingue comme certaines rposnes cherchent justes  complexifier le problme..........

----------


## Zavonen

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


C'est mme mieux, on vous dit exactement o aller...
Pour la postrit aussi :
Le code C qui donne DIRECTEMENT les coordonnes du point d'indice n de la spirale.
Mthode dveloppe dans les deux posts prcdents



```

```

----------


## Nemerle

Etant matheux, j'aime la postrit... quand elle est utile.....

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

----------


## Zavonen

J'essaie de rpondre, dans la mesure du possible aux questions qui sont poses, dans la mesure o je les comprends et mme si elles n'ont pour moi aucun intrt immdiat. 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 exgses et de vos jugements de valeur  l'emporte pice 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 itrative est la meilleur pour moi.

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

----------


## Zavonen

> Je posais juste la question du "calcul direct" a titre de curiosit mathmatique. 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 prs 1000 itrations, ce qui n'est pas norme car la boucle est presque vide, elle se rsume  l'incrmentation et au test.
Toutefois, s'il fallait passer au turbo, il faudrait mettre  les 1000 carrs 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 itrations.
Il n'en reste pas moins que pour votre problme la solution Nemerle est plus adapte  vos besoins et tout le monde (mme moi) peut le comprendre. Elle vous satisfait, vous l'avez dit, problme rsolu, point barre. Ce qui n'empche pas d'essayer de rpondre  vos questions et de proposer d'autres possibilits, mme si elles sont trop complexes pour le 'mathmaticien autoproclam' dont nous parlons.
Tout mathmaticien 'vritable' aurait pu, au contraire, tre positif et faire profiter le groupe de la remarque suivante:
La fonction que je dcris ralise une bijection de  N sur Z^2. cet enroulement de (tous) les points  coordonnes entires positives ou ngatives en spirale, ralise une bijection de N sur (2N)*(2N). Elle tablit donc d'un seul coup, les deux ingalits:
card(N+N) <card(N)
card(NxN) <card(N)
Ceci est, historiquement, la base de la 'thorie des nombres transfinis' de G. Cantor, fondement de la thorie moderne des ensembles. 
La plupart des bouquins de maths, proposent au lieu de cela la fameuse 'numration diagonale' ralisant la bijection N sur NxN, moins forte et moins esthtique, 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 inadaptes. 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'apprcie  sa juste valeur.
J'ai ragi ici , non pas pour gcher cette discussion, mais parce que j'en assez de voir Nemerle dfouler son agressivit sur n'importe qui en fonction de ses humeurs. Il m'arrive d'avoir cet honneur (je veux dire de dclencher les foudres de notre matheux de service), mais parfois ce sont d'autres qui se voient traiter de dbile, CPPN, etc...

----------


## pseudocode

Aprs 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 dpart.

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

Donc pour appliquer sur mon image 2D, j'ai eu l'ide 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.  ::yaisse2::  

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 rsultats.

----------


## 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 rsultats.


Dsol de ne pouvoir vous aider, je ne connais pas grand chose ( mon grand regret) en imagerie numrique. 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 rsultats.


Il est plutt 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 prcdents 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 qualite" qu'aprs 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 rsultats.


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

Tu veux faire une image "prvue", c'est a ?  partir de l'image originale et de la prvision 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 accs 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 rsultats 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 dfinitivement 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'ide 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 repre cartsien aprs rotation de 45. Autrement dit tu parcours ton image selon chaque diagonale.
C'est galre pour le calcul des extrmites en x' et y', mais a reste faisable.

A la fin tu moyenne sur tes 4 images rsultantes, ou mme mieux tu pondres 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 reprsenter, 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...

----------


## Nemerle

> Bie
> J'ai ragi ici , non pas pour gcher cette discussion, mais parce que j'en assez de voir Nemerle dfouler son agressivit sur n'importe qui en fonction de ses humeurs. Il m'arrive d'avoir cet honneur (je veux dire de dclencher les foudres de notre matheux de service), mais parfois ce sont d'autres qui se voient traiter de dbile, CPPN, etc...


et bien, et bien...

Pour conclure, et sans aggressivit, j'indique juste que je n'ai jamais SUPPORTE l'talage de ses connaissances de faon insistante, et de mme avec son vocabulaire (exgses, tiens-tiens...). 

On part ici d'un problme simple, et on se retrouve avec Cantor (j'aurais beaucoup  prciser sur ton post, mais je n'ose plus, de peur d'tre encore pris pour un aggressif...) ou avec un algorithme inutilement compliqu, bien qu'explicite. Introduire une digression ne me pose pas de problme , quand elle est annonce humblement...

Quand  mon post ' ici, une programmation standard est bien plus "rapide"! ', si elle est aggressive, j'en suis dsol... quoiqu'en ne comprenant pas trs bien.

Je vais rflchir  ma communication, mais je pense que tu devrais aussi envisager la possibilit de vhiculer un certain pdantisme dans tes posts ...

----------


## pseudocode

> mais physiquement qu'est-ce qu'il est cens reprsenter, ton filtre ?


C'est un filtre prdictif. Je pense que c'est une variation du filtre de kalman etendue, mais sans le code impossible d'en etre sr ::roll::  

Le but ultime est de debruiter une image (avec bcp de bruit, genre 50%). 

Pour cela, je dois dtecter les pixels "bruits". L'ide etait donc de faire une prdiction de la valeur d'un pixel puis de la comparer a la valeur relle. Si l'ecart est suprieur a un certain seuil on considere que le pixel original etait du "bruit" et on le remplace par la prdiction.




> 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...


Effectivement un filtre 1D n'a pas d'influence sur une image 2D. L'ide etait donc de transformer le voisinage 2D d'un pixel en signal 1D. Mais bon, ca marche pas terrible.

@mchk0123: j'ai essay ce genre de bidouille, mais plus j'ajoute de valeurs a moyenner, plus je perd d'informations... a la fin tout est flou.

@tous: Je vais rutiliser mes methodes de dtection de bruit habituelles, et je vais etre confront a un autre probleme... que je vais expliquer dans un autre post

----------


## physicist

Salut Pseudocode





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


Quel type de filtre tu veux appliquer et dans quel contexte veux tu prdire la valeur du prochain pixel?




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


C'est effectivement original, ta faon de parcourir l'image en spirale,enfin presque...


Va voir du cot des transformes en ondelette, ou tu peux regarder aussi les transformes ridgelet ou curvelet.

voici la rfrence d'un article:

Fast Discrete Curvelet Transforms
Emmanuel Cands, Laurent Demanet, David Donoho and Lexing Ying
parue dans : Applied and Computational Mathematics, Caltech, Pasadena, CA 
July 2005, revised March 2006

Article un peu technique mais qui ouvre la porte a de grandes possibilits de traitement de signal en 2D.


Aplus... :;): 


ps: en fichier joint une petit illustration tir de l'article, que tu trouveras aisement sur scholar google.

----------


## physicist

Encore une petite chose... pour montrer l'efficacit de ces mthodes pour le "denoising", puisque apparemment le problme ici est un bruit trs fort sur l'image

http://www-stat.stanford.edu/~jstarck/comp.html#data

A plus. ::P:

----------

