Faculté des sciences et techniques de l'ingénieur STI, Section de microtechnique, Institut d'imagerie et optique appliquée IOA (Laboratoire d'imagerie biomédicale LIB)

Nondyadic and nonlinear multiresolution image approximations

Muñoz Barrutia, Maria Arrate ; Unser, Michael (Dir.)

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

Ajouter à la liste personnelle
    Summary
    This thesis focuses on the development of novel multiresolution image approximations. Specifically, we present two kinds of generalization of multiresolution techniques: image reduction for arbitrary scales, and nonlinear approximations using other metrics than the standard Euclidean one. Traditional multiresolution decompositions are restricted to dyadic scales. As first contribution of this thesis, we develop a method that goes beyond this restriction and that is well suited to arbitrary scale-change computations. The key component is a new and numerically exact algorithm for computing inner products between a continuously defined signal and B-splines of any order and of arbitrary sizes. The technique can also be applied for non-uniform to uniform grid conversion, which is another approximation problem where our method excels. Main applications are resampling and signal reconstruction. Although simple to implement, least-squares approximations lead to artifacts that could be reduced if nonlinear methods would be used instead. The second contribution of the thesis is the development of nonlinear spline pyramids that are optimal for lp-norms. First, we introduce a Banach-space formulation of the problem and show that the solution is well defined. Second, we compute the lp-approximation thanks to an iterative optimization algorithm based on digital filtering. We conclude that l1-approximations reduce the artifacts that are inherent to least-squares methods; in particular, edge blurring and ringing. In addition, we observe that the error of l1-approximations is sparser. Finally, we derive an exact formula for the asymptotic Lp-error; this result justifies using the least-squares approximation as initial solution for the iterative optimization algorithm when the degree of the spline is even; otherwise, one has to include an appropriate correction term. The theoretical background of the thesis includes the modelisation of images in a continuous/discrete formalism and takes advantage of the approximation theory of linear shift-invariant operators. We have chosen B-splines as basis functions because of their nice properties. We also propose a new graphical formalism that links B-splines, finite differences, differential operators, and arbitrary scale changes.
    Résumé
    Le sujet de cette thèse est le développement de nouvelles approximations multiéchelle d'image. Plus précisément, nous présentons deux types de généralisation de techniques multiéchelles: réduction d'image par un facteur arbitraire, et approximations non-linéaires basées sur des métriques qui diffèrent de la métrique euclidienne habituelle. Les décompositions multiéchelle traditionnelles se limitent aux échelles dyadiques. Comme première contribution de cette thèse, nous développons une méthode qui surmonte cette restriction et qui s'adapte bien aux calculs de changement arbitraire d'échelle. L'élément clef en est un nouvel algorithme, numériquement exact, pour le calcul du produit vectoriel entre un signal défini continûment et des B-splines de tout ordre et de taille arbitraire. Cette technique peut aussi s'appliquer à la conversion d'une grille non-uniforme en une grille uniforme, qui est un autre exemple d'approximation où notre méthode est particulièrement performante. Les applications principales sont le ré-échantillonnage et la reconstruction de signal. Bien qu'elles soient simples à implémenter, les approximations au sens des moindres carrés conduisent à des défauts qui pourraient être réduits si elles étaient remplacées par des méthodes non-linéaires. La seconde contribution de cette thèse est le développement de pyramides non-linéaires, basées sur des splines, et optimales en normes lp. Tout d'abord, nous formulons le problème dans un espace de Banach et nous montrons que la solution est bien définie. Ensuite, nous calculons l'approximation au sens lp grâce à un algorithme itératif d'optimisation construit à l'aide de filtres numériques. Nous concluons que les approximations au sens l1 réduisent les défauts liés aux méthodes des moindres carrés; en particulier, perte de netteté des contours et tintements. De plus, nous observons que l'erreur des approximations au sens l1 est moins dense. Enfin, nous déduisons une formule exacte pour l'erreur asymptotique au sens Lp; ce résultat justifie de l'usage d'une approximation au sens des moindres carrés comme solution initiale de l'algorithme itératif d'optimisation. Le contenu théorique de cette thèse inclut la modélisation d'images dans un formalisme continu/discret et tire parti de la théorie d'approximation d'opérateurs linéaires à invariance de phase. Nous avons choisi des B-splines comme fonctions de base en raison de leur propriétés élégantes. Nous proposons en outre un nouveau formalisme graphique qui relie B-splines, différences finies, opérateurs différentiels, et changements arbitraires d'échelle.