Sous-sections

Interpolation par blocs de pixels

Principe

Le déplacement à l'écran des pixels dépend de leur profondeur. Partant du constat que beaucoup de pixels suivent approximativement la même trajectoire, l'idée développée dans cette partie est de les regrouper afin de les traiter par blocs plutôt que séparément. Ceci permet de n'appliquer les calculs de déplacement qu'aux blocs et de réduire ainsi le temps de calcul, l'affichage des blocs étant confié à la carte graphique.

Maillage régulier

Tout d'abord, nous avons regroupé les points par une subdivision régulière des images de référence. Pour cela, pour une image, nous créons un maillage 3D basé sur son tampon de profondeur. Les sommets du maillage sont régulièrement positionnés en 2D par rapport à l'image puis leur troisième composante est extraite du tampon de profondeur. Nous obtenons ainsi (figure 2.22) un maillage de triangles

Figure 2.22: Maillage régulier.
0.30
\includegraphics[scale=0.2]{eps/exp-ibp-image12.bmp.eps}
basé sur un point de vue de référence et dont chaque sommet est défini dans l'espace de la caméra par ses coordonnées $ (u,v,z)$. Le principe est alors de déplacer les sommets de ce maillage vers la position qu'ils occupent à l'écran selon le second point de vue, de façon exactement similaire au déplacement de points de la partie précédente. Les triangles du maillage sont texturés avec l'image de référence ; leurs coordonnées de texture sont directement issues de leur position dans l'image, à un changement de repère près : les coordonnées de texture $ (u,v)$ sont définies entre 0 et 1, tandis que les coordonnées $ (x,y)$ des sommets sont basées sur le repère du plan de projection de la caméra dont l'origine est au milieu de l'image. La figure 2.23(a) montre le résultat de l'interpolation avec cette méthode : les sommets extérieurs à l'objet ne se déplaçant pas, les triangles du maillage formés de tels points se voient étirés (effet de skinning ou de rubber sheet). Pour les triangles disposés totalement à l'intérieur de l'objet, par contre, le résultat est satisfaisant.
Figure 2.23: Déplacement des sommets du maillage de l'image de départ vers la position qu'ils occupent à l'écran selon le second point de vue.
[Artefacts visuels (Skinning) apparaissant sur les triangles en bordure du modèle]\includegraphics[%
width=1.0\columnwidth,
height=4.5cm,
keepaspectratio]{eps/exp-ibp-image14.bmp.eps}[Correction partielle du problème en affectant une profondeur virtuelle aux sommets extérieurs]\includegraphics[%
width=1.0\columnwidth,
height=4.5cm,
keepaspectratio]{eps/exp-ibp-image15.bmp.eps}[Suppression des triangles vides]\includegraphics[%
width=1.0\columnwidth,
height=4.5cm,
keepaspectratio]{eps/exp-ibp-image13.bmp.eps}

Pour améliorer le rendu et tenter de résoudre ce problème, nous avons attribué une profondeur virtuelle à tous ces points extérieurs de façon à ce qu'ils se déplacent aussi et évitent ces étirements. La profondeur que nous attribuons aux sommets extérieurs d'un triangle est la moyenne des profondeurs des autres sommets (voir figure 2.24). Si il y a deux sommets extérieurs (cas le plus défavorable), nous leurs affectons la profondeur du seul sommet intérieur.

Figure 2.24: Attribution d'une profondeur virtuelle aux points extérieurs du maillage.
\includegraphics[%
width=0.90\columnwidth,
keepaspectratio]{eps/exp-maillage-correction.eps}

Le résultat est visible sur les sous-figures (b) et (c) : les effets d'étirement sont réduits, mais pas éliminés. En particulier, comme on peut le voir entre les pattes du tigre, les triangles de deux parties distinctes (de profondeur ''très'' différente) de l'objet partageant un ou plusieurs sommets se voient liés et étirés.

Ceci est dû à la façon dont nous avons créé le maillage : un triangle est défini par trois références aux trois sommets le constituant. Il faudrait donc, dans ce cas, séparer les sommets qui posent problème.

Maillage adaptatif

Les bordures de l'objet étant le problème central pour la création du maillage, nous avons expérimenté une autre méthode permettant d'éviter de créer des sommets extérieurs à l'objet.

Comme le montre la figure 2.25, nous segmentons tout d'abord l'image de profondeurs en un nombre fixé de couches, puis nous subdivisons les triangles du maillage régulier aux bordures de ces couches. La nombre de couches de profondeurs n'est pas choisi au hasard, il est choisi de façon à créer des zones partitionnant les niveaux de profondeurs générant les artéfacts d'étirement. Par exemple, sur la figure 2.25, si l'on créait un triangle couvrant une partie de la queue et une partie de la cuisse du tigre, ce triangle génèrerait du skinning car il y a une disparité de profondeur entre ces deux parties. Notre segmentation est donc choisie de façon à isoler ces parties de l'image. Bien sûr, cette segmentation arbitraire subdivise inutilement certaines parties de l'image, mais dans un premier temps cela permet de vérifier la validité de la méthode.

Figure 2.25: Partitionnement de l'image en un nombre fixé de niveaux de profondeurs servant à la subdivision du maillage.
\includegraphics[%
width=1.0\columnwidth,
keepaspectratio]{eps/exp-subdivision2.eps}

La subdivision des triangles se fait en parcourant pixel par pixel chacune des trois arêtes des triangles avec l'algorithme de tracé de droites de Bresenham jusqu'à passer d'un niveau de profondeur à un autre. Si nous ne trouvons aucune transition, nous ne subdivisons pas le triangle. Dans le cas contraire, nous obtenons principalement le cas exposé en figure 2.25 où deux arêtes sont coupées par une bordure de zone. Dans ce cas, nous relions les points de transition trouvés et nous subdivisons le quadrilatère $ Q$ en trois triangles $ T_{0}$, $ T_{1}$ et $ T_{2}$ sur la base d'un nouveau point $ p$ positionné au milieu de l'arête sans transition. Les critères d'arrêt de la subdivision sont un niveau de récursion maximum et une taille minimale pour les arêtes subdivisées. La figure 2.25 montre le maillage obtenu avec cette méthode sur l'image segmentée sur 6 niveaux.

Nous avons constaté que cet algorithme génère des trous, invisibles quand on subdivise l'image, mais apparents dès qu'on affiche le maillage sous un autre angle du vue. La figure 2.26 illustre cet artéfact : les trous sont dus à la différence de profondeur entre le point de subdivision ($ p_{1}$) et le point de même coordonnées de texture, mais positionné sur l'arête du triangle adjacent ($ p'_{1}$). Ce problème est courant dans les techniques utilisant la subdivision de triangles au sein de maillages : le point $ p_{1}$ est un T-vertex (litt. sommet de type T) [AMH02].

Pour corriger ce problème, nous devons subdiviser le triangle adjacent. Nous avons choisi d'effectuer cette subdivision de façon à minimiser le nombre de triangles créés.

Figure 2.26: Problème de la subdivision d'arête.
\includegraphics[%
width=1.0\columnwidth,
height=4cm,
keepaspectratio]{eps/exp-subdivision0.eps}

Comme le montre la figure 2.27, nous séparons en deux le triangle adjacent par une arête joignant le point de transition au sommet opposé. Malheureusement, cela génère des sommets hors de l'objet, et nous retrouvons les problèmes d'étirement.

Sur la figure 2.27(b), nous avons retiré du maillage ces triangles n'étant pas intégralement contenu dans l'image de l'objet. Ceci crée des trous, visibles par exemple sur les pattes arrières (voir également l'image de droite de la figure 2.28).

Les figures 2.27(c) et (d) montrent le résultat de cette méthode appliquée à l'ensemble de l'image. C'est à dire que nous ne partons pas du maillage régulier mais d'un seul carré composé de deux triangles occupant toute l'image et appliquons l'algorithme.

Figure 2.27: Application de la subdivision d'arêtes avec prise en compte des T-vertices (image (a)). Les images (c) et (d) correspondent à la subdivision appliquée à l'ensemble de l'image plutôt qu'au maillage régulier (b).
\includegraphics[%
width=1.0\columnwidth,
keepaspectratio]{eps/exp-subdivision3.eps}

Figure 2.28: Comparaison des deux algorithmes de subdivision. A gauche, la première version générant des T-vertices. A droite, la version corrigée.
\includegraphics[%
width=0.70\columnwidth,
keepaspectratio]{eps/exp-comparaison-maillages.eps}

Discussion

La construction d'un maillage basé sur une image de profondeurs s'avère être une opération compliquée. Dans les travaux de Sillion et al. [SDB97][DSSD99], un maillage de l'image de fond d'une scène urbaine est utilisé pour remplacer la géométrie distante de l'observateur. Le maillage régulier est coupé aux endroits générant de trop grand effets d'étirement. Néanmoins leur méthode est adaptée à une scène distante de l'observateur, pour laquelle les effets d'étirement subsistants ne sont pas visibles.

Dans les travaux récents de Pajarola et al. [PSM04], le problème de la création d'un maillage polygonal approximant une image de profondeur est analysé en détails et ils proposent une méthode (DMesh) permettant de détecter les disparités de profondeurs de l'image, de créer un maillage polygonal adapté et de combiner en temps réel plusieurs de ces maillages pour couvrir tous les angles de vue. Le maillage de l'image de profondeur peut également s'effectuer en temps réel et adapté au point de vue, bien qu'au prix d'une baisse de performances (150 FPS $ \Longrightarrow$ 6 FPS sur un Pentium4 1.5Ghz et une carte graphique GeForce4 Ti4600).

Porquet Damien 2005-03-02