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)

Non-linear subdivision of univariate signals and discrete surfaces

Aspert, Nicolas ; Ebrahimi, Touradj (Dir.)

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

Ajouter à la liste personnelle
    Summary
    During the last 20 years, the joint expansion of computing power, computer graphics, networking capabilities and multiresolution analysis have stimulated several research domains, and developed the need for new types of data such as 3D models, i.e. discrete surfaces. In the intersection between multiresolution analysis and computer graphics, subdivision methods, i.e. iterative refinement procedures of curves or surfaces, have a non-negligible place, since they are a basic component needed to adapt existing multiresolution techniques dedicated to signals and images to more complicated data such as discrete surfaces represented by polygonal meshes. Such representations are of great interest since they make polygonal meshes nearly as exible as higher level 3D model representations, such as piecewise polynomial based surfaces (e.g. NURBS, B-splines...). The generalization of subdivision methods from univariate data to polygonal meshes is relatively simple in case of a regular mesh but becomes less straightforward when handling irregularities. Moreover, in the linear univariate case, obtaining a smoother limit curve is achieved by increasing the size of the support of the subdivision scheme, which is not a trivial operation in the case of a surface subdivision scheme without a priori assumptions on the mesh. While many linear subdivision methods are available, the studies concerning more general non-linear methods are relatively sparse, whereas such techniques could be used to achieve better results without increasing the size support. The goal of this study is to propose and to analyze a binary non-linear interpolatory subdivision method. The proposed technique uses local polar coordinates to compute the positions of the newly inserted points. It is shown that the method converges toward continuous limit functions. The proposed univariate scheme is extended to triangular meshes, possibly with boundaries. In order to evaluate characteristics of the proposed scheme which are not proved analytically, numerical estimates to study convergence, regularity of the limit function and approximation order are studied and validated using known linear schemes of identical support. The convergence criterion is adapted to surface subdivision via a Hausdorff distance-based metric. The evolution of Gaussian and mean curvature of limit surfaces is also studied and compared against theoretical values when available. An application of surface subdivision to build a multiresolution representation of 3D models is also studied. In particular, the efficiency of such a representation for compression and in terms of rate-distortion of such a representation is shown. An alternate to the initial SPIHT-based encoding, based on the JPEG 2000 image compression standard method. This method makes possible partial decoding of the compressed model in both SNR-progressive and level-progressive ways, while adding only a minimal overhead when compared to SPIHT.
    Résumé
    Durant les 20 dernières années, l'expansion simultanée de la puissance de calcul des ordinateurs, de leurs capacités graphiques et d'interconnection par réseau, ainsi que des techniques liées à l'analyse multirésolution a stimulé de nombreux domaines de recherche et a fait croître les besoins en nouveaux types de données comme par exemple les modèles 3D, i.e. les surface discrètes. Dans la partie commune à l'analyse multirésolution et à la modélisation informatique de courbes et de surfaces, les techniques de subdivision, i.e. les méthodes itératives de raffinement des courbes ou des surfaces, tiennent une place non-négligeable car elles constituent un bloc essentiel à l'adaptation des techniques multirésolution dédiées aux signaux et aux images à des donées plus compliquées, comme par exemple les surfaces discrètes représentées par des maillages polygonaux. Ces représentations multirésolutions sont d'un grand intérêt, car elles permettent aux maillages polygonaux d'être presque aussi flexibles que des représentations de plus haut niveau des modèles 3D, comme par exemple les surfaces générées grâces à des polynômes par morceaux (NURBS, B-splines...). La généralisation des méthodes de subdivision dédiées aux signaux unidimensionnels aux maillages polygonaux est relativement simple dans le cas de maillages réguliers, mais devient plus difficile quand doivent être prises en compte les possibles irrégularités. De plus, alors qu'il est possible d'obtenir des courbes limites plus régulières en augmentant le support d'un schéma de subdivision unidimensionnel linéaire, ceci ne peut que très difficilement être généralisé au cas des méthodes de subdivision pour les surfaces discrètes sans faire de suppositions a priori sur le maillage. Alors que beaucoup d'études ont été menées sur les schémas de subdivision linéaires, celles concernant les méthodes non-linéaires sont nettement moins nombreuses, alors que de telles méthodes pourraient être utilisées pour obtenir de meilleurs résultats que les méthodes linéaires de même support. Le but de cette étude est de proposer et d'analyser une méthode de subdivision non-linéaire, binaire et interpolante pour des signaux unidimensionnels. La méthode proposée utilise les coordonnées polaires locales pour calculer les positions des nouveaux points. Il est démontré que cette méthode génère des fonctions limites continues. Le schéma proposé est également étendu aux maillages triangulaires, ainsi qu'aux maillages triangulaires ayant des bords. Pour évaluer les autres caractéristiques de la méthode de subdivision proposée qui ne sont pas prouvées analytiquement, des estimateurs numériques pour étudier la convergence, la régularité de la fonction limite et l'ordre d'approximation, sont définis et validés grâce à des schémas linéaires connus ayant le même support que la méthode non-linéaire étudiée. Le critère de convergence est étendu aux méthodes de subdivision pour les surfaces grâce à une métrique basée sur la distance de Hausdorff. L'évolution des courbures Gaussiennes et moyennes des surfaces limites obtenues est également étudiée et comparée aux valeurs théoriques lorsque celles-ci sont disponibles. Une application de la subdivision des surfaces pour générer des représentations multirésolution de modèles 3D est également étudiée. En particulier, l'intérêt de cette méthode pour compresser les modèles 3D ainsi que son efficacité en termes de débit-distortion est montrée. Une méthode alternative d'encodage, basée sur la méthode utilisée dans le standard de compression d'images JPEG 2000, est proposée pour remplacer la méthode initiale basée sur SPIHT. Cette nouvelle méthode rend possible le décodage partiel, soit progressif par niveau de résolution, soit progressif par qualité, des modèles 3D compressés tout en ne nécessitant que peu d'informations supplémentaires par rapport à SPIHT.