Faculté des sciences et techniques de l'ingénieur STI, Section d'électricité, Institut de traitement des signaux ITS (Laboratoire de traitement des signaux 1 LTS1)

Compression of 3D models with NURBS

Santa Cruz Ducci, Diego ; Ebrahimi, Touradj (Dir.)

Thèse sciences techniques Ecole polytechnique fédérale de Lausanne EPFL : 2003 ; no 2770.

Add to personal list
    Summary
    With recent progress in computing, algorithmics and telecommunications, 3D models are increasingly used in various multimedia applications. Examples include visualization, gaming, entertainment and virtual reality. In the multimedia domain 3D models have been traditionally represented as polygonal meshes. This piecewise planar representation can be thought of as the analogy of bitmap images for 3D surfaces. As bitmap images, they enjoy great flexibility and are particularly well suited to describing information captured from the real world, through, for instance, scanning processes. They suffer, however, from the same shortcomings, namely limited resolution and large storage size. The compression of polygonal meshes has been a very active field of research in the last decade and rather efficient compression algorithms have been proposed in the literature that greatly mitigate the high storage costs. However, such a low level description of a 3D shape has a bounded performance. More efficient compression should be reachable through the use of higher level primitives. This idea has been explored to a great extent in the context of model based coding of visual information. In such an approach, when compressing the visual information a higher level representation (e.g., 3D model of a talking head) is obtained through analysis methods. This can be seen as an inverse projection problem. Once this task is fullled, the resulting parameters of the model are coded instead of the original information. It is believed that if the analysis module is efficient enough, the total cost of coding (in a rate distortion sense) will be greatly reduced. The relatively poor performance and high complexity of currently available analysis methods (except for specific cases where a priori knowledge about the nature of the objects is available), has refrained a large deployment of coding techniques based on such an approach. Progress in computer graphics has however changed this situation. In fact, nowadays, an increasing number of pictures, video and 3D content are generated by synthesis processing rather than coming from a capture device such as a camera or a scanner. This means that the underlying model in the synthesis stage can be used for their efficient coding without the need for a complex analysis module. In other words it would be a mistake to attempt to compress a low level description (e.g., a polygonal mesh) when a higher level one is available from the synthesis process (e.g., a parametric surface). This is, however, what is usually done in the multimedia domain, where higher level 3D model descriptions are converted to polygonal meshes, if anything by the lack of standard coded formats for the former. On a parallel but related path, the way we consume audio-visual information is changing. As opposed to recent past and a large part of today's applications, interactivity is becoming a key element in the way we consume information. In the context of interest in this dissertation, this means that when coding visual information (an image or a video for instance), previously obvious considerations such as decision on sampling parameters are not so obvious anymore. In fact, as in an interactive environment the effective display resolution can be controlled by the user through zooming, there is no clear optimal setting for the sampling period. This means that because of interactivity, the representation used to code the scene should allow the display of objects in a variety of resolutions, and ideally up to infinity. One way to resolve this problem would be by extensive over-sampling. But this approach is unrealistic and too expensive to implement in many situations. The alternative would be to use a resolution independent representation. In the realm of 3D modeling, such representations are usually available when the models are created by an artist on a computer. The scope of this dissertation is precisely the compression of 3D models in higher level forms. The direct coding in such a form should yield improved rate-distortion performance while providing a large degree of resolution independence. There has not been, so far, any major attempt to efficiently compress these representations, such as parametric surfaces. This thesis proposes a solution to overcome this gap. A variety of higher level 3D representations exist, of which parametric surfaces are a popular choice among designers. Within parametric surfaces, Non-Uniform Rational B-Splines (NURBS) enjoy great popularity as a wide range of NURBS based modeling tools are readily available. Recently, NURBS has been included in the Virtual Reality Modeling Language (VRML) and its next generation descendant eXtensible 3D (X3D). The nice properties of NURBS and their widespread use has lead us to choose them as the form we use for the coded representation. The primary goal of this dissertation is the definition of a system for coding 3D NURBS models with guaranteed distortion. The basis of the system is entropy coded differential pulse coded modulation (DPCM). In the case of NURBS, guaranteeing the distortion is not trivial, as some of its parameters (e.g., knots) have a complicated influence on the overall surface distortion. To this end, a detailed distortion analysis is performed. In particular, previously unknown relations between the distortion of knots and the resulting surface distortion are demonstrated. Compression efficiency is pursued at every stage and simple yet efficient entropy coder realizations are defined. The special case of degenerate and closed surfaces with duplicate control points is addressed and an efficient yet simple coding is proposed to compress the duplicate relationships. Encoder aspects are also analyzed. Optimal predictors are found that perform well across a wide class of models. Simplification techniques are also considered for improved compression efficiency at negligible distortion cost. Transmission over error prone channels is also considered and an error resilient extension defined. The data stream is partitioned by independently coding small groups of surfaces and inserting the necessary resynchronization markers. Simple strategies for achieving the desired level of protection are proposed. The same extension also serves the purpose of random access and on-the-fly reordering of the data stream.
    Résumé
    Avec les récents progrès de l'informatique et des télécommunications, les modèles 3D sont de plus en plus utilisés dans les applications multimédia. La visualisation, les jeux, le divertissement et la réalité virtuelle comptent parmi les exemples les plus répandus. Dans le domaine du multimédia les modèles 3D ont été traditionnellement représentés comme des maillages polygonaux. Cette représentation plane par morceaux, peut être vue comme l'analogue des images bitmap pour les surfaces 3D. Comme les images bitmap, ils jouissent d'une grande flexibilité et sont particulièrement bien adaptés pour décrire des informations acquises depuis le monde réel, comme par exemple, lors d'un processus de balayage. Ils souffrent, cependant, des mêmes limitations, notamment une résolution limitée et un grand espace de stockage. La compression de maillages polygonaux est un domaine de recherche très actif depuis une décennie et des algorithmes de compression efficaces permettant de réduire fortement les besoins en place de stockage, ont été proposés dans la littérature. Cependant, cette description bas-niveau de formes 3D a une performance limitée. Une compression plus efficace devrait être possible avec l'usage de primitives de plus haut niveau. Cette idée a été extensivement explorée dans le contexte du codage à base de modèles de l'information visuelle. Dans une telle approche, lors de la compression de l'information visuelle une représentation de plus haut niveau (par ex. un modèle 3D d'une tête parlante) est obtenue par analyse. Ceci peut être vu comme un problème de projection inverse. Une fois cette tâche accomplie, les paramètres du modèle résultants sont codés à la place de l'information originale. Il est communément admis que si le module d'analyse est suffisamment efficace le coût total de codage (dans le sens débit distorsion) en sera largement réduit. La performance relativement basse et la haute complexité des méthodes d'analyse existantes (mis à part des cas spécifiques où une connaissance a priori de la nature des objets est disponible), a empêché un large déploiement des techniques de codage basées sur une telle approche. Le progrès dans le domaine de l'infographie (computer graphics) a néanmoins changé cette situation. En effet, de nos jours, un nombre croissant d'images, vidéos et contenu 3D sont générés par procédés de synthèse au lieu de provenir d'un appareil de capture, tels une caméra ou un scanner. Cela signifie que le modèle sous-jacent dans le stade de synthèse peut être utilisé pour améliorer les performances de codage sans avoir besoin de recourir à un module d'analyse hautement complexe. En d'autres mots, ce serait une erreur que de vouloir essayer de compresser une description bas-niveau (par ex. un maillage polygonal) alors qu'une description de plus haut niveau est disponible dans le processus de synthèse (par ex. une surface paramétrique). Cela est, cependant, ce qui est couramment fait dans le domaine du multimédia, où des descriptions de modèles 3D de haut niveau sont convertis en maillage polygonaux, ne serait-ce que par manque d'un format standard pour le codage de ceux-ci. Par ailleurs, la façon dont nous consommons l'information audiovisuelle est en train de changer. A l'opposé des anciennes applications et une grande partie des actuelles, l'interactivité est en train de devenir un élément clé de la manière dont nous consommons l'information. Dans le cadre de la présente dissertation, cela signifie que, lorsque nous codons une information visuelle (par ex. une image ou une vidéo), des considérations évidentes par le passé telles que la sélection des paramètres d'échantillonnage n'est plus aussi évidente qu'avant. En effet, à l'instar d'un environnement interactif où la résolution d'affichage effective peut être contrôlée par l'utilisateur à travers un zoom, il n'y a pas de choix optimal clairement défini pour les paramètres d'échantillonnage. Cela signifie qu'à cause de l'interactivité, la représentation utilisée pour coder la scène devrait permettre l'affichage des objets dans une large gamme de résolutions et, idéalement, jusqu'à l'infini. Une façon de résoudre ce problème serait l'utilisation d'un suréchantillonnage extensif. Néanmoins, cette approche est irréaliste et trop coûteuse à implanter dans beaucoup de situations. L'alternative serait d'utiliser une représentation indépendante de la résolution. Dans le domaine du modelage 3D, lesdites représentations sont couramment disponibles lorsque les modèles sont crées par un artiste sur un ordinateur. Le sujet de cette dissertation est précisément la compression de modèles 3D dans une forme de plus haut niveau. Le codage direct sous une telle forme devrait délivrer une performance débit distorsion améliorée tout en procurant un large degré d'indépendance de résolution. Il n'y a pas eu, jusqu'à ce jour, de travaux majeurs sur la compression efficace de telles représentations, telles que les surfaces paramétriques. Cette thèse propose une solution pour combler ce vide. Une variété de représentations 3D de haut niveau existe, parmi lesquelles les surfaces paramétriques sont un choix répandu parmi les designers. Dans la famille des surfaces paramétriques, les B-Splines rationnelles non-uniformes (NURBS) jouissent d'une grande popularité étant donné qu'une large gamme d'outils basés sur les NURBS sont couramment disponibles. Récemment, les NURBS ont été ajoutées dans le Virtual Reality Modeling Language (VRML) ainsi que son descendant de nouvelle génération le eXtensible 3D (X3D). Les bonnes propriétés des NURBS et leur utilisation largement répandue nous ont conduit à les choisir comme forme sous laquelle les modèles seront codés. Le but principal de cette dissertation est la définition d'un système de codage des modèles 3D NURBS avec une distorsion garantie. La base du système est la modulation par impulsion et codage différentiel (DPCM) codée entropiquement. Dans le cas de NURBS, garantir la distorsion n'est pas évident, dès lors que certains de ses paramètres (par ex. noeuds) ont une influence compliquée sur la distorsion totale de la surface. A cette fin, une analyse détaillé de la distorsion est effectuée. En particulier, des relations jusqu'alors inconnues entre la distorsion des noeuds et la distorsion de la surface résultante est démontrée. L'efficacité de la compression est recherchée à chaque stade et des codeurs entropiques simples mais néanmoins efficaces sont définis. Le cas particulier de surfaces fermées et dégénérées avec des point de contrôle dupliqués est adressé et un codage simple et efficace est proposé pour compresser les relations de duplication. Les aspects de l'encodeur sont aussi analysés. Des prédicteurs optimaux ayant une bonne performance sur une large classe de modèles sont trouvés. Des techniques de simplification, ayant un coût négligeable sur la distorsion, sont aussi considérées pour une meilleure efficacité de compression. La transmission sur des canaux présentant un taux d'erreur non négligeable est aussi considérée est une extension de résilience aux erreurs est définie. Le train de données est morcelé en codant indépendamment des petits groupes de surfaces et en insérant les marqueurs de resynchronisation nécessaires. Des stratégies simples pour atteindre le niveau désiré de protection sont proposées. La même extension sert aussi pour l'accès aléatoire et le réordonnancement à la demande du train de données.