Antoine ROJAT - Schéma de Subdivision Box Spline

De Ensiwiki
Aller à : navigation, rechercher


Schémas de subdivision BOX SPLINE

Labo LJK
Equipe MGMI
Encadrants Sylvain.Meignen@imag.fr

Etudiant

ROJAT, Antoine

Introduction

Même si aujourd'hui la puissance des ordinateurs est immense, nous ne sommes toujours pas en mesure de représenter des objets continus. Nous ne pouvons que les approcher en considérant un nombre très important de points. La représentation d'objets continus par ordinateur est au coeur de nombreux domaines et notament celui du calcul scientifique. Les résultats démontrés dans le cadre du calcul scientifique trouvent leurs applications dans d'autres domaines comme l'imagerie ou la conception assistée par ordinateur.

Sufbdiv1.jpg

L'idée générale, en ce qui concerne l'imagerie, est que plus une courbe ou une surface est régulière, plus elle nous apparaîtra comme étant "naturelle".

Il faut noter que dans la plupart des logiciels de calcul, on représente les fonctions par un ensemble fini de points. A l'aide de cet ensemble on reconstitue les courbes ou les surfaces en "reliant" les points. Il est clair qu'il faut disposer d'un grand nombre de points afin que le résultat soit satisfaisant.

Dans ce domaine, de nombreuses recherches ont été menées et elles ont mis en évidence l'utilité d'un outil mathématique très performant : les schémas de subdivision, qui sont des procédés rapides permettant de reconstituer efficacement et fidèlement des courbes régulières.

Sufbdiv2.jpg

Les schémas de subdivision sont un domaine d'étude extrêmement vaste et mon travail devait porter sur les schémas de subdivision basés sur les box-splines. Dans un premier temps je me suis tourné vers la théorie générale des schémas de subdivision afin de pouvoir ensuite mieux appréhender les schémas de subvision box-splines.


La théorie générale des schémas de subdivision se scinde en deux parties distinctes :

  • l'étude de la convergence des schémas
  • l'étude des propriétés de régularité de la courbe obtenue par application des schémas


Dans le cadre de mon travail, je me suis concentré sur le cas des courbes (cas de la dimension 2) et j'ai d'autre part restreint mon étude aux schémas de subdivision linéaires. Bien que les résultats sur la régularité de la courbe générée par application d'un schéma de subdivision ne se généralisent pas, la plupart des résultats sur la convergence des schémas peuvent facilement s'étendre au cas où l'on considère des surfaces.

Prérequis

Avant d'exposer les résultats de mon travail, je présente ici quelques définitions liées aux schémas de subdivison qui permettront d'appréhender le reste de cet article.

L'idée des schémas de subdivision est la suivante : on combine un polygone de contrôle choisi au départ avec un ensemble de coefficients appelé masque du schéma de subdivision, ce qui détermine un nouveau polygone de contrôle, et on itère jusqu'à ce que le résultat soit satisfaisant.

Dans le cadre de cet article, les points du nouveau polygone de contrôle sont obtenus par combinaison linéaire des points du polygone de contrôle de l'itération courante, c'est ce qui justifie l'appellation de "schémas de subdivision linéaires".

Par ailleurs mon travail porte essentiellement sur le cas des schémas diadiques, c'est-à-dire ceux où l'on double le nombre de points du polygone de contrôle à chaque itération.

Un schéma de subdivision est entièrement caractérisé par son masque. D'autre part, on considère que le masque est une suite à support compact.

De manière plus formelle, considérons un schéma de subdivision S et son masque A = (a_{k} )_{k}  et un polygone de contrôle  F = (f_{j})_{j}  .

Le polygone de contrôle résultant de l'application du schéma de subdivision est déterminé par  F^{1}  f^{1}_{l}=\sum_{n \in\mathbb{Z}} a_{l-2n}f_{n}

Enfin on définit la notion de polynôme caractéristique d'un schéma de subdivision de la manière suivante :

Soit S un schéma de subdivision et A son masque. Le polynôme caractéristique de S est \sum_{n\in \mathbb{Z}} a_{n} z^{-n}

Travail réalisé

Dans le cadre de mon TER, je me suis basé sur un article de Nira Dyn qui est une chercheuse de référence dans le domaine des schémas de subdivision. J'ai commencé par lire son article de manière transversale afin d'avoir une compréhension globale de la philosophie des schémas de subdivision. Plus particulièrement, mon travail a été le suivant :

  • Compréhension des résultats énoncés dans l'article de Nira Dyn
  • Redémonstration de l'ensemble de ces résultats dans le cadre de la dimension 2
  • Implémentation de deux schémas de subdivision classiques : Chaikin et Four Points Scheme

L'étude de ces deux schémas m'a notament permis de conclure que leur utilisation devait se restreindre au cas de la reconstitution d'images et qu'ils ne pouvaient pas être utilisés dans le cadre du calcul scientifique. En effet, ces schémas ne permettent pas de représenter des fonctions très régulières puisqu'ils convergent vers des courbes de classe  C^{1} ce qui n'est pas un niveau de régulartité suffisant pour le calcul scientifique.

Les résultats de convergence

Je me suis dans un premier temps attaché à comprendre et à redémontrer l'ensemble des résultats permettant de prouver la convergence d'un schéma de subdivision. Le premier résultat sur lequel j'ai travaillé est une condition nécessaire de convergence pour un schéma. Dans la pratique, ce résultat permet d'écarter des schémas trivialement non-convergents.

D'autre part, dans la plupart des résultats qui portent sur la convergence, on fait intervenir un schéma aux différences défini de la façon suivante :

Soit S un schéma de subdivision. Il existe S_{1} un schéma de subdivision tel que  df^{k} = S_{1}df^{k-1}

(df^{k})_{m}=2^{k} ( f^{k}_{m+1} - f^{k}_{m}), k \in \mathbb{Z}.

De plus le schéma de subdivision S est uniformément convergent si et seulement si

\frac{1}{2}S_{1} converge uniformément vers la fonction nulle quel que soit l'ensemble de points de contrôle initiaux f^{0}.

L'utilisation de ce théorème est la suivante : pour examiner la convergence d'un schéma de subdivision donné, on s'intéresse au schéma aux différences associé et de cette façon on reporte l'étude sur un schéma qui se révèle, dans la pratique, plus simple.

Le théorème précédent donne un moyen d'examiner la convergence d'un schéma de subdivision : pour ce faire on calcule la norme uniforme des itérations successives d'un schéma aux différences donné. Dès lors que l'on obtient une valeur inférieure à 1, on est assuré de l'uniforme convergence vers 0 de ce schéma (ce résultat est explicité dans mon compte-rendu).

Après avoir étudié les résultats liés à la convergence des schémas, je me suis intéressé à la régularité des courbes produites par application d'un schéma de subdivision.

Les résultats de régularité

Dans le domaine du calcul scientifique, on cherche à approcher de la manière la plus précise possible des objets mathématiques tels que des fonctions de classe  C^{\infty} .

Dans le cadre des schémas de subdivision linéaires, le théorème qui est au coeur de cette problématique est le suivant :

Soit un schéma de subdivision dont le polynôme caractéristique est de la forme : a(z)=(\frac{1+z}{2z})^{k} q(z)

Soit le schéma de subdivision Q dont le polynôme caractéristique est q(z).

Si Q est un schéma de subdivision convergent alors les courbes générées par S sont de classe C^{k}(\mathbb{R}).

Ce résultat est particulièrement intéressant en calcul scientifique puisqu'à partir d'un schéma de subdivision que l'on sait convergent, on peut construire un schéma qui converge vers des fonctions dont la régularité est aussi élevée que souhaitée.

Cependant, d'après les différents articles que j'ai pu lire dans le cadre de mon travail, il s'avère que lorsque l'on souhaite obtenir des schémas qui convergent vers des courbes dont la régularité est importante, on utilise préférentiellement des schémas de subdivision non-linéaires.

Le théorème précédent est basé sur l'étude du masque d'un schéma de subdivision pour déterminer la régularité des courbes engendrées par celui-ci. Dans son article, Nyra Din propose aussi une autre approche : la fonction associée à un schéma de subdivision. Pour ce faire, elle introduit la notion d'opérateur associé à un schéma : Soit S un schéma de subdivision que l'on supposera dans la suite uniformément convergent. Soit A son masque. On peut alors définir l'opérateur suivant :

T\Psi = \displaystyle{ \sum_{n \in \mathbb{Z}} a_{n} \Psi(2.-n) }

La fonction associée au schéma de subdivision est l'unique fonction à support compact qui vérifie :

T\Phi=\Phi

Cette définition fournit un moyen pratique de calculer \Phi : on cherche le point fixe de l'opérateur associé à un schéma donné.

Durant mon travail, j'ai également examiné le résultat suivant : 
\forall f^{0},\ S^{\infty}f^{0}=\displaystyle{\sum_{n \in \mathbb{Z}} f_{n}^{0}\phi(.-n)  }

Ce résultat permet de relier les courbes engendrées par un schéma à la fonction associée à ce schéma. C'est là que réside le lien avec les schémas de subdivision basés sur les box-splines : les box-splines vérifient une relation de la forme : B = \displaystyle{ \sum_{n \in \mathbb{Z}} a_{n} B(2.-n) }

Box Splines

Lors de la dernière partie de mon TER, j'ai voulu examiner les schémas de subdivision basés sur les box-splines. Pour cela j'ai étudié un article de Pierre Pansu. Dans la mesure où ce travail n'est pas abouti, je ne l'ai pas incorporé dans mon compte-rendu.

Conclusion

Dans le cadre de mon TER, j'ai pu me familliariser avec le travail de recherche et cela a été une expérience très enrichissante. J'ai implémenté deux schémas classiques (qui figurent dans la section documents additionnels). Mon travail m'a permis de reformuler plusieurs résultats énoncés par Nira Dyn afin de les mettre en perspective pour en apprécier l'intérêt pratique. J'espère que les résultats que j'ai obtenus s'avèreront utiles de ce point de vue.

Durant les six mois pendant lesquels j'ai travaillé sur mon TER, j'ai eu le temps de bien comprendre la notion de schéma de subdivision, mais je commence seulement à en saisir les mutliples applications possibles. C'est pourquoi j'aurais souhaité pouvoir poursuivre mes recherches dans ce domaine. En effet, le cadre de mon TER était très vaste et je n'ai naturellement pas eu le temps d'examiner l'ensemble du sujet.

Dans les documents additionnels ci-après, vous trouverez mon compte-rendu de TER, les slides de ma présentation ainsi que deux scripts scilab permettant de réaliser deux schémas de subdivision classiques :

  • l'algorithme de Chaikin
  • l'algorithme four-points scheme

Je tiens à adresser mes remerciements à Monsieur Sylvain MEIGNEN pour avoir accepté d'encadrer mon travail.

Documents additionnels

Bibliographie

=== Documents additionnels ===