Discussion :

[black_hole]

Bonjour,

J'ai des données d'un capteur que je recois en coordonnées polaires. Les données recues sont des tableaux MxN, les données en X sont des coordonnées polaires de {-theta , theta} avec une résolution de (theta*2/M) .
Les coordonnées en Y sont les distance de [dmin, dmax] avec une résolution de (dmax-dmin) / N.

Quelqu'un pourrait me conseiller un algorithme permettant de creer une grille d'occupation à partir de mon jeu de donnée polaire?

Je ne sais pas comment pondérer la valeur en coordonnée polaire vers la grille en cordoonée XY. Par exemple si pour la coordonnée polaire p = (r,theta) j'obtiens un point pg = (10.66,1.88) quel est la pondération que je dois appliquer au 4 pixels au alentour?

[wiwaxia]

Bonjour,

... Je ne sais pas comment pondérer la valeur en coordonnée polaire vers la grille en cordoonée XY. Par exemple si pour la coordonnée polaire p = (r,theta) j'obtiens un point pg = (10.66,1.88) quel est la pondération que je dois appliquer au 4 pixels au alentour?

En notant P00, P10, P01 et P11 les pixels de
coordonnées respectives (10, 1), (11, 1), (10, 2) et (11, 2),
le pixel "moyen" résultera de la combinaison linéaire:

Pm = (1-0.66)*(1-0.88).P00 + 0.66*(1-0.88).P10 + (1-0.66)*0.88.P10 + 0.66*0.88.P11 .

Si l'on veut rationaliser cela,il faut décomposer toute coordonnée réelle en deux parties entière et décimale:

x = Ex + Dx , avec Ex = Trunc(x) , Dc = Frac(x);
y = Ey + Dy, avec Ey = Trunc(y) , Dc = Frac(y);

chaque composante couleur (j = 1, 2 ou 3) du pixel moyen pourra ainsi s'exprimer en fonction des 4 pixels concernés:

P00 = P(Ex, Ey) , P10 = P(Ex+1, Ey) , P01 = P(Ex, Ey+1) et P11 = P(Ex+1, Ey+1)

(et en tenant compte de la nécessité de revenir à un résultat entier) par la combinaison linéaire:

P(x, y)[j] = Round((1-Dx)(1-Dy)*P00[i] + Dx(1-Dy)*P10[j] + (1-Dx)Dy*P01[j] + Dx*Dy*P11[j]) .

La formule d'interpolation peut se réduire à des sommes de deux termes, mais elle comporte alors deux stades impliquant des vecteurs de R³; il suffit d'écrire dans ce cas:

Wx0[j] = (1-Dx)*P00[i] + Dx*P10[j] ,
Wx1[j] = (1-Dx)*P01[j] + Dx*P11[j] ,
P(x, y)[j] = Round((1-Dy)*Wx0[j] + Dy*Wx1[j]) .

Formules à vérifier.

[Guesset]

Bonjour,

La réponse de wiwaxia est complète et il n'y a donc rien à ajouter à l'algorithme éprouvé d'interpolation bilinéaire (même si j'ai toujours été gêné qu'un point qui, en général, sera dans un seul triangle des 4 points voisins altère aussi le quatrième point ).

Cependant sur cette base, l'implémentation peut être plus ou moins efficace. Des mises en facteurs peuvent diminuer sensiblement le nombre d'opérations (notamment les multiplications en flottants) et il existe une instruction sincos qui divise par deux les temps de projection cartésienne.

Salutations

[wiwaxia]

Bonjour,

... j'ai toujours été gêné qu'un point qui, en général, sera dans un seul triangle des 4 points voisins altère aussi le quatrième point ) ...

La valeur locale d'une fonction de deux variables W(x, y) sur le domaine de double interpolation

[Ex, Ex + 1]×[Ey, Ey + 1]

est donnée par le polynôme symétrique:

W(Ex + Dx, Ey + Dy) = (1-Dx)(1-Dy)*P00[i] + Dx(1-Dy)*P10[j] + (1-Dx)Dy*P01[j] + Dx*Dy*P11[j] ,

auxquelles sont équivalentes les deux étapes précédemment données.

Le polynôme en question équivaut à la donnée implicite de deux fonctions affines:

a) à (Dy) constant: W(Ex + Dx, Ey + Dy) = A(Dy) + B(Dy)*Dx ,
b) à (Dx) constant: W(Ex + Dx, Ey + Dy) = C(Dx) + D(Dx)*Dy .

La surface d'équation z = F(x, y) = (1-x)(1-y)*K00 + x(1-y)*K10 + (1-x)y*K01 + xy*K11
contient un double faisceau de droites situées dans des plans parallèles à (xOz) et (yOz).

[Guesset]

Bonjour Wiwaxia,

Je te remercie mais j'exprimais seulement une limitation des traitements bilinéaires qui, en appliquant une opération linéaire en x puis en y (ou dans l'ordre inverse, cela n'a pas d'importance si la transformation a, comme ici, seulement une pente et pas de constante), inscrit ses effets dans un carré ce qui ne saurait être optimal.

Par exemple, pour un point P dans une maille carrée, le point le plus loin dans cette maille peut être plus loin qu'un point d'une autre maille. Pourtant seul le premier sera altéré. Cela traduit une métrique implicite non isotrope (un compas qui trace des carrés ).

L'avantage essentiel est la simplicité et donc l'efficacité en temps de traitement. Comme tu l'écris, c'est une double interpolation et non une interpolation de surface.

C'est un joli sujet en soi loin d'être épuisé par quelques algorithmes éprouvés.

Salutations

Philippe

[wiwaxia]

Tes remarques suscitent quelques observations.

... pour un point P dans une maille carrée, le point le plus loin dans cette maille peut être plus loin qu'un point d'une autre maille. Pourtant seul le premier sera altéré. Cela traduit une métrique implicite non isotrope (un compas qui trace des carrés ) ...

Il importe de distinguer tout point quelconque du plan, pour lequel on cherche une estimation de la couleur locale, des noeuds de la grille où la fonction est parfaitement connue, puisqu'il s'agit des pixels de l'image initiale.
L'arrangement régulier de ces derniers détermine une partition du plan de l'image, et les sommets (A, B, C, D) d'un carré sont bien les noeuds les plus proches de tout point (M) situé à l'intérieur.
Les indices (r, v, b) de la couleur locale sont naturellement bornés par les valeurs extrêmes rencontrées aux sommets, et l'on a (sauf configuration très particulière et discutable):

Min(I_A, I_B, I_C, I_D) <~ I_M <~ Max(I_A, I_B, I_C, I_D) ;

d'où l'idée d'une combinaison linéaire impliquant des distances, et conduisant à une valeur locale (I_M) d'autant plus proche de celle de l'un des sommets que la distance correspondante est plus faible.

a) Dans le cas d'un assemblage hexagonal de pixels, la maille est un triangle équilatéral (AB = BC = CA = a) et les indices des 3 sommets sont pondérés par les distances séparant le point considéré (M) de chacun des trois côtés:

a(3^1/2/2).I_M = MI*I_A + MJ*I_B + MK*I_C ;

la somme des longueurs des 3 hauteurs abaissées depuis le point (M) est en effet constante , et l'on établit facilement l'égalité:

MI + MJ + MK = AB.(3^1/2/2)

à partir de l'expression de l'aire du triangle.

b) Cependant les pixels constituent le plus souvent un réseau à maille carrée (AB = BC = CD = DA = a), et les distances séparant le point (M) des 4 côtés vérifient les relations:

MI + MK = MJ + ML = a ;

on envisage alors la combinaison linéaire:

a².I_M = MJ.(MK.I_A + MI.I_C) + ML.(MK.I_B + MI.I_D)

d'où découle naturellement la relation donnée au message #02.

Il s'agit bien, dans les deux cas, de distances euclidiennes.