Nondyadic and Nonlinear Multiresolution Image Approximations

A. Muñoz Barrutia

École polytechnique fédérale de Lausanne, EPFL Thesis no. 2555 (2002), 175 p., April 12, 2002.

Download PDFDownload PS

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 l_p-norms. First, we introduce a Banach-space formulation of the problem and show that the solution is well defined. Second, we compute the l_p-approximation thanks to an iterative optimization algorithm based on digital filtering. We conclude that l₁-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 l₁-approximations is sparser. Finally, we derive an exact formula for the asymptotic L_p-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.

@PHDTHESIS(http://bigwww.epfl.ch/publications/munoz0201.html,
AUTHOR="Mu{\~{n}}oz Barrutia, A.",
TITLE="Nondyadic and Nonlinear Multiresolution Image
	Approximations",
SCHOOL="{\'{E}}cole polytechnique f{\'{e}}d{\'{e}}rale de {L}ausanne
	({EPFL})",
YEAR="2002",
type="{EPFL} Thesis no.\ 2555 (2002), 175 p.",
address="",
month="April 12,",
note="")