Méthode "libre", lignes de contrôle

Cette technique ne segmente pas l'image en morceaux (triangles), mais introduit un certain nombre d'éléments graphiques - contours, comme c-dessous. (C'est la technique de base exploitée par des logiciels comme WinMorph, par ElasticReality, et quelques autres applications commerciales et shareware (de qualité souvent médiocre...).) Les contours peuvent être simples, des segments de droites, ou des splines. Ou même des points.

licontr (211K)

Il faut délimiter sur l'image-source un certain nombre de zones (ouvertes ou fermées) par des lignes droites ou courbes, où les courbes sont typiquement des splines relativement simples mathématiquement.

Ainsi la souplesse de transformation peut être assez grande. C'est une technique assez sophistiquée. Envisageons un segment du contour - repère.

xp_fig1 (1K)
Pour un point $X$ quelconque, on peut trouver la distance entre ce point et le segment, et aussi la distance de ses ses bouts.

Pour donner une certaine idée nous pouvons commencer par les déformations basées sur les points de contrôle. Mais, cette fois il n'y aura pas de triangulation. Les points ne sont pas connectés. L'image ci-dessous vient d'un logiciel Japonais de morphing, Morpher, de Masakazu Fujimiya. [Programme mort, inaccessible.]

fuji (19K)
Pour déplacer les points entre les points de contrôle – ... pas de grille, ni d'axes naturels, pas de coordonnées spéciales, comme dans les cas bi-linéaire et symplectique.

Il faut trouver une fonction qui ramène les points de contrôle (un ensemble bien défini) source vers les positions finales, et pour les points intermédiaires on interpole ; le déplacement est atténué en fonction de distance entre ce point et les points de contrôle - en principe - tous. Les plus proches influencent le plus le déplacement. Ceci sera le point de départ pour des méthodes plus élaborées, où on remplacera les points de contrôle par des lignes droites ou courbes. La construction de telles fonctions n'est pas unique, et la liberté de paramétrisation joue son role artistique...

Exemple. peut être basé sur le suivant. Si $\vec{q}_i$ est le déplacement (relatif) du point de contrôle $\vec{p}_i$, (donc $\vec{q}_i = \vec{p}'_i - \vec{p}_i$), pour un point arbitraire $\vec{X}$ le déplacement sera égal à

$\displaystyle{\mathbb{N} \cdot \sum_{i=1}^N F_i\cdot c_i \cdot \vec{q}_i}$
où $\mathbb{N}$ est la normalisation, et $F_i$ est la "force" d'influence du point de contrôle $i$ sur $\vec{X}$, par ex. $F_i = 1/||\vec{X} - \vec{p}_i||$. Le facteur $c$, correspond à l'atténuation de la force avec distance, à cause de la "rigidité de l'espace", par ex. $c_i = \exp(-\beta ||\vec{X} - \vec{p}_i||^2)$. La constante de normalisation doit inclure $1/(\sum_i 1/||\vec{X} - \vec{p}_i||)$.

Si $\vec{p}$ est très proche d'un point de contrôle, il sera déplacé comme lui, l'inverse de la distance affaiblit d'autres contributions. Mais, même s'il y a un seul point de contrôle (en fait : deux, la source et la cible), $\vec{X}$ n'est pas obligé de le suivre, car le facteur de rigidité $c$ ajoute une atténuation supplémentaire.

Beier et Neely préféraient des lignes aux points. Voici comment déplacer un point, en présence d'une paire de lignes de controle.

On définit

$u = ((\vec{X} - \vec{P})\cdot(\vec{Q} - \vec{P}))/(||\vec{Q} - \vec{P}||^2)$
($u$ correspond à la position le long de la ligne $PQ$, la fraction de la distance entre $P$ et $Q$; négative ou supérieure à 1 si la projection du point $\vec{X}$ dépasse le segment). Introduisons l'opérateur $\epsilon$ tel que $\epsilon \vec{v}$ soit un vecteur perpendiculaire à $\vec{v}$.

Si $\vec{v} = (v_x,v_y)$, alors $\epsilon \vec{v} = (-v_y,v_x)$.

La distance perpendiculaire entre le point et la ligne de contrôle, est

$v = ((\vec{X} - \vec{P})\cdot\epsilon(\vec{Q} - \vec{P}))/(||\vec{Q} - \vec{P}||)$
La formule du déplacement est
$\vec{X}' = \vec{P}' + u\cdot(\vec{Q}' - \vec{P}') + (v\cdot\epsilon (\vec{Q}' - \vec{P}'))/(||\vec{Q}' - \vec{P}'||)$.

L'algorithme utilise la transformation inverse.

Pour tout pixel cible $\vec{X}$, trouver les paramètres $(u,v)$ correspondants.
Passer à l'image source, et avec les mêmes $(u,v)$, récupérér $\vec{X}'$. Transférer la couleur de $\vec{X}'$ vers $\vec{X}$.

Pour plusieurs familles de lignes de contrôle, on construit une moyenne pondérée. Si $l_i$ est la longueur de la ligne $i$, et $d_i$ est la distance entre le pixel et la ligne (abs $v$, si $v$ est entre 0 et 1, sinon c'est soit la distance de $\vec{P}$, soit de $\vec{Q}$). Le poids vaut

$w_i = \left(\frac{l_i^p}{a+d_i}\right)^b$,
où $a$, $p$ et $b$ sont des paramètres qui influencent la rigidité de l'espace et l'importance relative de segments longs par rapport aux courts. Ceci n'est pas unique ! Les valeurs de $b$ entre 0.5 et 2 sont les plus utiles ; $p$ est typiquement entre 0 et 1. $a$ détermine la précision, si $a> 0$, la transition est adoucie ; on a pu introduire ce paramètre aussi dans le modèle basé sur les points de contrôle. Si $a=0$, et les lignes ont des intersections, on risque des singularités.

Attention, même si l'utilisateur ne le fait pas, une configuration arbitraire sur la source et sur la cible, peuvent provoquer l'intersection sur une ou plusieurs instances intermédiaires. Le morphing demande encore le transfert des couleurs par le fondu.

Mais même la simple interpolation des lignes n'est pas triviale.

Si un segment subit une rotation, et si on l'interpole par le déplacement des points terminaux, il changera de longueur lors de ce procès (imaginez la rotation de 180°...).

stupid (3K)

On peut faire mieux. Beier et Neely proposent une autre interpolation : on déplace le centre, et on effectue la rotation de l'orientation du segment. Ensuite on interpole la longueur du segment. Ceci peut être plus "correct", mais pas forcément intuitif. Le codage est plus long.

Il est très facile de produire des "fantômes" dans des endroits complètement bizarres, et parfois l'augmentation du nombre des lignes de contrôle n'est pas une bonne idée. Donc, les logiciels de morphing prolifèrent. Voulez-vous un projet de morphing?

On peut effectuer le warping avant de commencer à interpoler les couleurs, ou vice-versa. Cette possibilité est offerte par le logiciel XMRM.

 

Le warping/morphing ne s'applique pas qu'aux images. Les déformations sont devenues des techniques standard de modifications des sons, de la musique, où on peut transmuter un instrument musical en un autre durant l'exécution d'un morceau. Ou, obtenir une transition douce et naturelle (loin du cross-fading) entre deux sons.

Notez que la méthode des entités de contrôle combine les deux stratégies du traitement, directe et inverse. Les lignes de contrôle - pour les images intermédiaires - subissent la transformation directe, de la source vers la cible. Quand le nouveau squelette est complet, la transformée inverse est appliquée lors du balayage de la cible.

On peut se poser une question importante : et si la source et la cible, vues du point de vue du "squelette", de la transformation des contours, maillages, etc., ne sot pas conformes, si leur topologie est différente, s'ils ne sont pas homéomorphes? Ceci est particulièrement important pour la déformation et l'animation des objets 3D : les sommets des maillages bougent.

 

Dans le premier cas (réalisé avec Blender), le problème ne se pose tellement pas, car tout maillage non-pathologique peut être converti automatiquement en sphère. Mais nous avons déjà vu des pathologies dans des cas 2D plus simples, la conversion d'un triangle en rectangle. La théorie est compliquée, même si manuellement nous pouvons faire tout, en ajoutant des nouvelles arêts par le dédoublement des sommets et leur séparation.

On peut également fusionner les sommets. Cependant, faire cela par un processus automatique est très compliqué, et jusqu'aujourd'hui, les solutions ne sont pas idéales.

Voici à gauche un applet de Mark Newbold, qui illustre cette technique. Vous pouvez le réaliser vous-mêmes avec VRML.

Dans le cadre plus général, il existe une technique d'interpolation entre des formes quelconques (surtout polygonales, bien sûr), basée sur le concept de la somme de Minkowski.

Si vous avez deux ensembles de points (sommets de polygones par exemple), $X=\{x\}$, $Y=\{y\}$, alors la somme de Minkowski est tout simplement l'ensemble - somme, ${x+y$, tels que $x \in X, y \in Y}$.

Les détails sont compliqués, l'usage de cette technique semble assez spécialisée, mais faire une petite application qui effectue cette transformation n'est pas difficile. Nous allons vous montrer un applet Java (de Alexander Bogomolny), très ancien...

 

Il est loin de la perfection, il n'est pas adapté aux figures concaves etc., mais vous devez saisir l'idée générale. Voici encore deux exemples de morphing 3D.

   

hermite (4K) Nous avons mentionné que les interpolations linéaires des position et des couleurs ne sont pas forcément appréciées par nos mécanismes visuels, et que nous pouvons aussi utiliser des fonctions nonlinéaires, comme celle de Hermite : $f(x) = 3\cdot x^2 - 2\cdot x^3$, qui démarre et s'arrête doucement (avec la dérivée égale à zéro aux bouts).