Description et reconstruction rapide de surfaces

Laurent Chevalier, Fabrice Jaillet, Atilla Baskurt

Laboratoire d’Informatique Graphique, Image et Modélisation

LIGIM, EA 1899, Université Claude Bernard Lyon 1
[Link]

Résumé

Nous présentons dans cette étude une méthode de compression géométrique d'objets
3D pour la transmission de scènes réelles et virtuelles. Nous réalisons la description de
surfaces complexes grâce à l'utilisation d'un ensemble de superquadriques dont les
relations topologiques sont décrites par un arbre d’opérations ensemblistes. A partir
d’un nuage de points non organisés de l’objet original dans R 3, cet arbre est obtenu
grâce à un algorithme de « division et fusion » adapté à notre problématique. Dans un
premier temps, le nuage est découpé jusqu’à ce que la qualité de l’approximation de
chaque ensemble de points par une superquadrique soit supérieure à un seuil donné. La
seconde étape consiste en la fusion des ensembles de points voisins obtenus, afin de
réduire le nombre de superquadriques nécessaires à l'approximation de l'objet 3D. La
méthode est appliquée sur des données synthétiques et des données 3D de profondeur
issues de la base de données MPEG7.

1. Introduction
Dans de nombreux domaines, il peut être intéressant de disposer de descripteurs
performants associés aux surfaces présentes dans une image 3D afin d’obtenir une
segmentation et une reconstruction rapide des objets tridimensionnels. Ces descripteurs
doivent pouvoir être visualisés en temps réel. Ceci implique une modélisation
simplifiée. Une certaine tolérance ou un flou dans la reconstruction de la surface d’un
objet permet d’envisager le développement d’un tel modèle (descripteur) réduit.
Nous décrivons les scènes ou objets 3D à l’aide de superquadriques [2]. Ce modèle
de surface est très utilisé dans ce domaine d’application [1], car il est à la fois compact
et généraliste. Il n’est cependant pas suffisant pour décrire des objets avec précision.
Deux solutions sont alors possibles : soit on déforme l’unique superquadrique qui
approxime les données, C’est l’approche de Bardinet en ajoutant une « Free Form

CORESA 2000 19 ET 20 OCTOBRE 2000

Deformation (FFD)» à une superquadrique pour modéliser des données médicales [3] ;
soit on décompose l’objet en éléments primitifs, chaque élément étant approximable
correctement par une seule superquadrique [4,5,6,7,8,9]. Les approches diffèrent alors
par le choix de l’algorithme de décomposition. Leonardis et Solina utilisent par exemple
une approche de type croissance de régions [6,7].
C’est résolument la solution de segmentation que nous suivons, bien que nous
utilisions comme descripteur primitif une superquadrique avec déformation. Notre
méthode de segmentation des données tridimensionnelles se base sur un algorithme de
type « division et fusion ». Le résultat final est un ensemble de superquadriques
entièrement structuré afin de rendre le descripteur plus compact et plus fonctionnel.
Dans la section 2, la définition des superquadriques est rappelée. La section 3 présente
la méthode d’approximation d’un nuage de points de R 3 avec une superquadrique. La
méthode de « division et fusion » détaillée en section 4 permet une représentation de
l’objet 3D en éléments primitifs. Cette méthode est validée sur des données synthétiques
et des données MPEG7 dans la section 5.

2. Superquadriques
Une superquadrique est un modèle de surface introduit en informatique graphique
en 1981 par A.H. Barr [2]. Extension des plus communes quadriques, le modèle peut
être partitionné en 4 sous-classes : les superellipsoïdes, les supertoroïdes, les
superhyperboloïdes et les superparaboloïdes.
Les superellipsoïdes sont les seules réellement utilisées dans le domaine qui nous
intéresse. Elles peuvent être définies par la forme implicite :

avec :
• a1, a2, a3 définissant le facteur d’échelle respectivement sur l’axe des x, y et z.
• 1 et 2 permettant de définir respectivement la courbure latitudinale et
longitudinale de la forme.
et :
• f(x,y,z)=1 si le point (x,y,z) est sur la surface.
• f(x,y,z)<1 si le point (x,y,z) est à l’intérieur.
• f(x,y,z)>1 si le point (x,y,z) est à l’extérieur.

Si une forme implicite rend relativement simple le calcul de la distance d’un point à
cette surface et ainsi l’approximation de la surface, elle est aussi synonyme d’un
affichage particulièrement lourd. Les superquadriques ont la particularité de pouvoir
aussi s’exprimer sous forme paramétrique rendant la visualisation très simple. Nous
avons par exemple la paramétrisation suivante :

Les superellipsoïdes décrivent un large éventail de formes allant de simples

ellipsoïdes (1=1 et 2=1), aux parallélépipèdes (10 et 2 0) et aux cylindres

CORESA 2000 19 ET 20 OCTOBRE 2000

(1=1 et 2 0)(Fig. 1a). Elles permettent une modélisation compacte (seulement 5
paramètres), généraliste et particulièrement adapté à notre application.

Néanmoins, nous remarquons dans les méthodes d’approximation utilisant une

décomposition en superellipsoïdes que certains objets, apparemment simples,
nécessitent l’assemblage de plusieurs primitives [7]. Cela peut conduire à un modèle
complexe. C’est pourquoi, le modèle de superellipsoïde que nous proposons possède 2
paramètres supplémentaires de déformation (Fig. 1b). Ainsi tout en gardant le caractère
compact du descripteur primitif, nous améliorons la qualité d’approximation et
diminuons le nombre de superquadriques nécessaires pour décrire certains objets.

(a) (b)

Fig. 1 : (a) Exemples de superellipsoïdes standards.

(b) Exemples de superellipsoïdes déformées.

CORESA 2000 19 ET 20 OCTOBRE 2000

3. Approximation du nuage par une superquadrique
Ayant pour données d’entrées un ensemble non organisé de N points de , sans
information de relation entre ces points, il s’agit de déterminer les valeurs des
paramètres de notre modèle pour approximer ce nuage de points.

3.1 Approximation au sens des moindres carrés

Nous utilisons la méthode la plus largement répandue pour approximer des données
tridimensionnelles avec une superquadrique. Elle a été proposée par Solina [5].
L’approximation se fait au sens des moindres carrés.
Utiliser simplement la fonction potentielle f (Eq. 1) pour approximer la distance d
d’un point à la surface n’est pas correcte lorsque est petit. Nous utilisons donc la
formule que propose Solina [5] :

L’unique considération de la distance des données au modèle n’est pas suffisante

surtout lorsque le nuage est ouvert. En effet, plusieurs superquadriques de tailles très
diverses peuvent approximer le même nuage de points. Le volume de la superquadrique
doit être pris en compte dans l’approximation. Cette prise en compte se fait en
multipliant l’erreur d’approximation par une fonction dépendante du volume. Solina a
montré, par expérimentation, que le meilleur choix était l’ajout du facteur qui
privilégie les petites superquadriques.
En tenant compte de tous les paramètres de la superquadrique, de la translation
et de la rotation éventuelles, l’approximation consiste à minimiser la fonction :

qui représente l’erreur globale d’approximation.

L’approximation par une superquadrique est donc un problème nécessitant un
algorithme de régression non-linéaire sur 11 variables. Nous utilisons l’algorithme de
Levenberg-Marquardt qui permet une convergence rapide.

3.2. Première évaluation des paramètres

L’algorithme de minimisation permet de converger vers un minimum local qui
dépend de l’initialisation des paramètres du modèle. L’estimation des valeurs initiales
se fait aisément. Les paramètres de translation ( , , ) qui indiquent la position de la
superquadrique sont donnés par le centre de gravité du nuage de points. L’orientation de
la superquadrique ( , , ) est calculée grâce à la matrice M des moments centraux
d’ordre 2. En effet, la matrice de rotation R est définie comme étant la matrice
diagonalisant celle des moments centraux, c’est à dire la matrice des vecteurs propres de
M :

CORESA 2000 19 ET 20 OCTOBRE 2000

où est diagonale. Le vecteur propre correspondant à la plus petite valeur propre de
M n’est autre que l’axe d’inertie minimum, l’axe principal de la superquadrique. La
taille de la superquadrique ( , , ) est initialisée avec la taille de la plus petite boîte
englobant tous les points du nuage et orientée comme calculé précédemment. Seuls les
paramètres et sont arbitrairement fixés à 1 pour partir d’une ellipsoïde.

4. Méthode de description
Notre objectif est d’obtenir un assemblage de primitives modélisant de manière
relativement précise un objet, un nuage de points de . Ayant fait le choix des
primitives (les superellipsoïdes avec déformation), il faut maintenant une méthode de
partitionnement des données telle que chaque sous-nuage s’approxime de manière
idéale avec ce descripteur de base. Cette méthode doit produire un nombre minimum de
primitives pour une qualité d’approximation donnée.
L’algorithme de décomposition utilisé est de type « division et fusion ».

4.1. Première étape : division du nuage

La phase de découpage est récursive. La première approximation du nuage se fait
par une seule superquadrique. Si, à la suite de cette approximation, l’erreur D (Eq. 4)
normalisée par le nombre de points N est inférieure à un seuil donné, alors le nuage
reste intact et la superquadrique résultante est considérée comme un modèle de ce
dernier. Dans le cas contraire, le nuage est scindé en deux. Ce partage se fait
arbitrairement par le plan orthogonal à un des axes passant par le centre de la région en
traitement. Suite à cette scission, on considérera par le même procédé les deux nuages
résultants de manière indépendante. Le mécanisme s’arrêtera de lui-même, lorsque pour
chaque région, le critère de division n’est plus respecté.

4.2. Deuxième étape : regroupement des régions similaires

La première étape fournit une partition des données, pour laquelle chaque région est
associée à une superquadrique. Le nombre de superquadriques constituant alors le
descripteur est souvent très important.
En effet, le plan de coupe ne tenant pas compte des relations topologiques entre les
points, la scission d’une région contenant une partie d’objet représentable par une seule
superquadrique peut conduire à la division de cette même partie d’objet.
Dans la seconde étape, nous tentons de regrouper ces régions. Pour ce faire, la
procédure d’approximation est appliquée à la fusion des nuages de chaque couple
(région , voisin1 de cette même région). Si cette approximation est satisfaisante, les
régions seront regroupées, sinon, elles resteront indépendantes. Cette étape s’arrête
lorsque la partition des données est stable.

1
Le voisinage est une notion à définir. Ce n’est pas forcément le voisinage direct. Dans les exemples
présentés dans cet article, nous considérons un voisinage par transition d’ordre 2. Deux régions sont dites
voisines si elles sont voisines directes ou voisines de voisines directes. Nous pourrons également
considérer un voisinage tenant compte de la à la distance euclidienne entre deux régions.

CORESA 2000 19 ET 20 OCTOBRE 2000

 A la fin de cette deuxième et dernière étape, l’ensemble des superquadriques a été
restreint au mieux pour la qualité d’approximation voulue, comptes tenus des divers
critères utilisés dans la procédure « division-fusion ».

4.3 Modèle final

Le résultat fourni par l’algorithme précédent est un ensemble réduit non organisé de
superquadriques. Cependant, il est possible d’aller plus loin et de structurer la
composition de cet ensemble à l’aide d’une méthode de type « Constructive Solid
Geometry (CSG) ».
Avec une telle approche, les superquadriques de l’ensemble résultant de la
décomposition des données deviennent les feuilles d’un arbre dont les nœuds sont des
opérations ensemblistes (union, intersection et différence). Un tel arbre a au moins deux
avantages en ce qui concerne la taille du descripteur. Le plus évident est qu’il est bien
plus simple de composer avec des différences pour bon nombre d’objets. En effet, pour
tous les « objets à trous » par exemple, il est plus avantageux, en terme de taille du
modèle, d’opérer une soustraction que de « tourner autour du trou ».
Le second avantage est qu’il est possible, en analysant cet arbre de trouver et
d’éliminer les redondances dans la description de la scène, sous-arbres identiques par
rotation, translation, facteur d’échelle.... La description de la scène devient ainsi plus
compacte. Nous sommes alors en présence d’un graphe orienté acyclique.
Grâce à la structuration en arbre ensembliste, il est possible de comparer différents
objets ou parties d’objets entre eux efficacement. Les applications sont multiples. Nous
pouvons envisager un moteur de recherche qui, prenant en entrée un modèle, retournera
l’ensemble des objets contenant ce descripteur.
Dans une optique de transmission, l’arbre permet également l’envoi progressif du
descripteur en fixant des priorités sur des parties de l’objet (sous-arbres). Par exemple
un modèle grossier de voiture sera envoyé, puis si nécessaire, certains détails : poignées
de portes (opérateur union), rétroviseurs (opérateur union) ou des creux dans la
carrosserie (opérateur différence). Ainsi, l’utilisateur peut obtenir le modèle, à sa
convenance, dans une qualité allant de la basse à la haute résolution.
Ainsi, la structuration de l’ensemble permet non seulement une plus grande
compacité du descripteur mais le rend également plus fonctionnel.

5. Résultats
Les objets de synthèse qui ont servis dans un premier temps pour les tests sont une
combinaison de superquadriques. Nous travaillons pour cet objet défini par un nuage de
5000 points. Le nombre de superquadriques à la fin de l’étape de division est 6 (Fig 3b).
Le descripteur final (Fig. 3c) obtenu avec l’étape de fusion est formé de deux
superquadriques comme pour l’objet initial.

CORESA 2000 19 ET 20 OCTOBRE 2000

Fig. 3 : (a) Objet initial. (b) Résultat après le division. (c) Résultat final après la fusion.

La méthode a été également testée sur des données issues de la base MPEG7. La
figure 4 illustre l’application de la méthode sur un de ces objets de la base (référence
DUCK232) (Fig. 4a). Le nuage compte environ 5000 points. A la fin de la première
étape, le modèle compte 112 superquadriques (Fig. 4b). Le modèle final n’en contient
plus que trois (Fig. 4c). Ce type de modèle final, d’assez basse résolution, est très utile
pour les comparaisons, et notamment pour la recherche d’objets similaires dans une
scène.

Fig. 4 : (a) Objet initial (base MPEG7). (b) Résultat après la division. (c) Résultat final.

6. Conclusion
Nous avons présenté une nouvelle méthode de description compacte de surfaces,
appliquée à des données tridimensionnelles non organisées. Cette description se fait,
sans connaissance a priori de l’objet, grâce à une décomposition de ce dernier en
éléments primitifs.
Le modèle surfacique de base que nous utilisons est la superquadrique à laquelle
nous avons ajouté une déformation afin d’augmenter la précision de l’approximation et
de garder un petit nombre d’éléments primitifs. La décomposition se fait d’abord dans
un sens « global à local » afin de contrôler efficacement la qualité d’approximation. La
stratégie de segmentation devient ensuite « local à global » pour réduire le nombre de
superquadriques, et ainsi, garantir la compacité du modèle final. Ce dernier est de plus
particulièrement fonctionnel et encore plus concis grâce à la structuration en arbre de
l’ensemble des primitives.
En guise d’amélioration, on peut envisager une prise en compte de la topologie des
données lors du découpage (découpage « intelligent »). Par ailleurs, le modèle ne traite
actuellement que les unions, il devra être adapté à la représentation des objets à trous ou
des objets présentant des concavités, avec l’ajout des opérateurs différences et
intersections.

Bibliographie

CORESA 2000 19 ET 20 OCTOBRE 2000

 [1] Ruud Bolle et Baba C. Vemuri. « On three-dimensional surface reconstruction
methods » IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(1), pp
1-12, Janvier 1991.
[2] Alan H. Barr. « Superquadrics et angle preserving transformations. » IEEE
Computer Graphics and Applications, vol. 1, pp 11-23, Janvier 1981.
[3] Eric Bardinet, Laurent D. Cohen, et Nicolas Ayache. « A parametric
deformable model to fit unstructured 3d data. » Rapport de recherche 2617 - INRIA,
1995.
[4] Alok Gupta et Ruzena Bajcsy. « Volumetric segmentation of range images of 3d
objects using superquadric models. » CVGIP : Image Understanding, 58(3), pp 302-
326, Novembre 1993.
[5] Franc Solina et Ruze²na Bajcsy. « Recovery of parametric models from range
images: the case for superquadrics with global deformations. » IEEE Transactions on
Pattern Analysis and Machine Intelligence, 12(2), pp 131-147, Février 1990.
[6] Ales Leonardis, Franc Solina, et Alenka Macerl. « A direct recovery of
superquadric models in range images using recover-and select paradigm. », Procedings
of 3d European Conference on Computer Vision, Stokholm, Mai 1994.
[7] Ales Leonardis, Ales Jaklic, et Franc Solina. « Superquadrics for segmenting
and modeling range data. » IEEE Transactions on Pattern Analysis and Machine
Intelligence, 19(11), pp 1289-1295, Novembre 1997.

CORESA 2000 19 ET 20 OCTOBRE 2000

 [8] Demetri Terzopoulos et Dimitri Metaxas. « Dynamic 3D models with local and
global le superquadrics. » IEEE Transactions on Pattern Analysis and Machine
Intelligence, 13(7), pp 703-714, Juillet 1991.
[9] Alex Pentland. « Reconition by parts. » IEEE 1st Int. Conf. on Computer Vision,
pp 612-620, Londres , 1987.

CORESA 2000 19 ET 20 OCTOBRE 2000