Tutoriels
 
Tutoriels
TL Majeure SIR
Séminaire Technique Smartroom
Installation
 
 
Items
Filtrage adaptatif
Compléments sur les descripteurs de Fourier
 
  
> SIRIEN Home > Obsolètes > Tutoriels > Compléments sur les descripteurs de Fourier

Systèmes Interactifs et Robotiques

Compléments sur les descripteurs de Fourier
 
  by Collette Jean-Luc
 
 

Rappels

Avec une liste ordonnée de N points (x_m,y_m) représentant un contour fermé, on peut construire une suite de nombres complexes :


z_m=x_m+iy_m

En considérant que cette suite est la représentation sur une période d’un signal périodique de période N, on peut lui associer une décomposition en série de Fourier :


a_k=\frac{1}{N}\sum_{m=0}^{N-1}(z_m-\overline{z})exp\left(-\frac{2 \pi jkm}{N}\right)

La valeur \overline{z} est la moyenne du signal complexe.

Pour approximer le contour, on peut ne conserver dans cette décomposition que les coefficients les plus significatifs, pour k_{min}\leq k \leq k_{max}. L’approximation du contour est alors donnée par le signal complexe :


\hat{z}_m=\overline{z}+\sum_{k=k_{min}}^{k_{max}}a_k exp\left(\frac{2 \pi jkm}{N}\right)

Les attributs caractérisant la forme, invariants par translation et par rotation peuvent être alors les d_k=|a_k| avec d_0=0 (si le contour fermé est parcouru dans le sens trigonométrique).

Normalisations possibles

- Invariance vis-à-vis du sens de parcours du contour

En fonction du sens de parcours du contour, on obtient des coefficients a_k pour le signal z_m ou les coefficients a_{-k} pour le signal z_{(-m)[N]}. Pour assurer l’unicité de la représentation, il convient de réaliser la permutation ci-dessous dans le cas où d_1<d_{-1}.

\begin{array}{lcl}
a_{temp} & = &  a_k \\
a_k & = & a_{-k}\\
a_{-k} & = & a_{temp}}
\end{array}

Il faut dans ces conditions que k_{min}=-k_{max} afin d’obtenir des vecteurs qui puissent être comparés entre eux, avec ou sans permutation.

- Invariance vis-à-vis de l’échelle

Avec la permutation précédente, d_1 a la valeur la plus grande. En divisant tous les coefficients a_k par d_1, on obtient des coefficients indépendants du facteur d’échelle.

- Coefficients complexes normalisés

L’inconvénient de l’utilisation des paramètres d_k est qu’une infinité de formes différentes peuvent être associées au même vecteur de paramètres d_k (en ne modifiant que la phase des coefficients a_k).

Pour caractériser la forme de façon plus pertinente, il convient donc de revenir aux coefficients complexes a_k initialement obtenus par décomposition en série de Fourier. Pour qu’ils soient indépendants aussi de la rotation, comme les d_k, il convient de procéder à des modifications sur les a_k en appliquant les quatre équations ci-dessous.

\begin{array}{lcl}
\phi & = &  Arg\{a_{-1}\times a_1\}/2 \\
a_k & = & a_k\times exp(-i \phi)\\
\theta & = & Arg\{a_1\}\\
a_k & = & a_k\times exp(-i \theta k)
\end{array}

En effet, si on obtient pour une forme donnée des coefficients a_k, la même forme orientée autrement avec une origine différente pour le signal complexe représentant le contour, sera associée à des coefficients de la forme a_k^\prime =a_k exp(j\alpha+j\beta k). L’angle \alpha varie selon l’orientation de la forme et l’angle \beta varie selon l’origine du signal complexe (le décalage d’origine correspond à un retard pur, induisant une variation linéaire de la phase).

Ainsi, Arg\{a_{-1}^\prime \times a_1^\prime\}=Arg\{a_{-1}\times a_1\}+2\alpha pour toute valeurs de \beta. Avec les deux premières équations faisant intervenir le paramètre \phi, on obtient donc des coefficients qui ne dépendent plus de l’angle d’orientation de la forme (à une valeur \pi près).

Cette première correction étant faite, il reste à obtenir des coefficients associés à la même origine du signal complexe. On fait appel alors aux deux dernières équations faisant intervenir le paramètre \theta qui rajoutent alors à l’argument des coefficients un terme linéaire qui fait que le coefficient complexe a_1 devienne réel. En conséquence, le coefficient a_{-1} devient lui aussi réel.

Essai sur une base de données synthétique

On calcule les coefficients complexes normalisés à partir d’une base de données synthétique. Ci-dessous, vous trouverez le fichier archive correspondant qui contient les programme Matlab lançant les traitements (lancer testdesfournorm après avoir extrait les fichiers).

  • fichier archive (version Linux avec Octave, lancer make avant de lancer octave)

Ci-dessous vous trouverez une version avec toutes les normalisations effectuées (coefficients complexes normalisés et invariants vis-à-vis du sens de parcours du contour et de sa taille).

  • fichier archive (version Linux avec Octave, lancer make avant de lancer octave)

Les trois formes à partir desquelles sont générées les images de la base synthétique sont représentées ci-dessous.

A partir de ces images initiales, on génère une base de données de 500 images comprenant ces formes avec des angles d’orientation choisis de façon aléatoire. On calcule les coefficients normalisés et on reconstruit le contour approximé pour chaque image de la base (avec k_{max}=-k_{min}=10). L’ensemble des contours approximés est tracé ci-dessous. On peut constater que les contours se retourvent tous orientés de la même façon quelle que soit l’orientation initiale. Les points origine du suivi des contours (points verts) se retrouvent aussi approximativement au même endroit.

Le module des coefficients est tracé ci-dessous.

Les parties réelles et imaginaires des coefficients sont tracées ci-dessous. On peut vérifier sur ce tracé que les coefficients a_1 et a_{-1} ont des parties imaginaires nulles, suite à la normalisation proposée.

Les vecteurs constitués des parties réelles et imaginaires des coefficients sont présentés à l’entrée d’un algorithme de K-moyennes. Comme l’orientation n’est connue qu’à \pi près, il faut 6 classes pour identifier 3 formes. On trace ci-dessous les contours associés à chacun des vecteurs prototypes. On peut ainsi vérifier la pertinence des classes obtenues (ce qui n’aurait pas pu être fait avec simplement les modules des coefficients). A posteriori, on peut associer les prototypes 4 et 5 à l’objet numéro 1, les prototypes 2 et 3 à l’objet numéro 2 et les prototypes 1 et 6 à l’objet numéro 3.

Essai sur une base de données de gestes

L’ensemble des normalisations proposées est appliqué sur les contours extraits d’une base de données de gestes dont voici des extraits ci-dessous.

Les contours approximés et réorientés sont représentés ci-desous avec k_{max}=-k_{min}=10. Pour construire la base de données des descripteurs, on rajoute à chaque contour représenté par la suite z_m, le contour représenté par la suite -z_m afin que dans une phase de reconnaissance, toutes les orientations possibles soient prises en compte même si elles ne sont pas présentes au moment de l’apprentissage.

Avec la normalisation, on a bien d_1=1 pour tous les descripteurs calculés.

On obtient a_1=1 pour tous les descripteurs calculés.

Après quantification vectorielle (par la méthode des K-moyennes), les vecteurs prototypes (en rouge dans la figure ci-dessous, avec en bleu l’ensemble des vecteurs dans la classe) sont associés aux différents gestes à identifier. Comme avec la base de données synthétique testée plus haut, il faut au moins deux prototypes pour une classe de geste.