University of Waterloo Links
Some External Links

Recent Progress (2001-present)

Fractal image coding revisited, IFS on multifunction spaces, inverse problems using the "collage coding" method for contraction maps

  • Fractal image coding revisited

    After a kind of hiatus, we have returned to fractal image coding (FIC) to determine whether it can

    • perform standard image processing tasks in a novel fashion and
    • yield unique information about images.

    Recall that FIC is a "local IFS" procedure involving the approximation of image range subblocks by greyscale-modified subimages that are supported on larger domain subblocks.

    • Fractal image denoising

      We have been able to show that fractal coding can work remarkably well to denoise images. We have also shown that such denoising can also be accomplished in the wavelet domain [6,20] using the fractal-wavelet transform. Much of this work is to be found in the Ph.D. thesis of M. Ghazel:

    • Statistics of domain-range pairings and the self-similarity of images

      The success of fractal denoising - and indeed fractal image compression methods in general - is based upon the important fact that, in general, even in the presence of noise, a significant number of domain subblocks will approximate a given range subblock almost as well as the optimal domain subblock selected by collage coding. It appears that this property, perhaps implicitly assumed, has never been investigated in detail until now. This work formed a part of the Ph.D. thesis of S.K. Alexander.

    • Fractal coding over complex tilings

      In his Ph.D. thesis work, D. Piche investigated the fractal-wavelet coding of images using nonseparable Haar wavelet basis functions that were constructed over complex tilings, following the procedure of Grochenig and Madych.

      Some of this work may also be found in the following paper:
      • F. Mendivil and D. Piche, xxxxx

    • Continuous evolution of fractal transforms

      Consider the evolution equation u_t = u - Tu, where T is a contraction mapping. Then u -> u' as t -> infinity, where u'=Tu' is the unique fixed point of T. (To the best of our knowledge, no study or use of such a seemingly inocuous evolution equation has appeared in the literature.) If T is a (nonlocal) fractal transform operator, then the above represents a continuous evolution toward the attractor/fixed point of T. If we use the Euler forward method to discretize/differentiate in time, then when the timestep h=1, we have the usual iteration method of fractal coding.

      Someone working in the area of evolutionary PDEs may well consider the above evolution equation to be a kind of "cheat job" since the asymptotic behaviour of u(t) is prescribed by T. However, one can begin to do many interesting things with this equation, e.g., introducing dissipative terms to modify the asymptotic limit. Our evolution equation with a fractal transform operator T represents the introduction of nonlocal PDE methods in imaging.

      Nonlocal ODEs/PDEs have been studied in a number of theoretical contexts, but not in imaging.

    • Fractal image coding as projection onto convex subsets (POCS)

      We show how fractal image coding can be viewed and generalized in terms of the method of projections onto convex sets (POCS). In this approach, the fractal code defines a set of spatial domain similarity constraints. We also show how such a reformulation in terms of POCS allows additional contraints to be imposed during fractal image decoding. Two applications are presented: image construction with an incomplete fractal code and image denoising.

    • Fractal image superresolution using a "method of examples"

      We present a novel single-frame image zooming technique based on so-called "self-examples". Our method combines the ideas of fractal-based image zooming, example-based zooming, and nonlocal-means image denoising in a consistent and improved framework. In Bayesian terms, this example-based zooming technique targets the MMSE estimate by learning the posterior directly from examples taken from the image itself at a different scale, similar to fractal-based techniques. The examples are weighted according to a scheme introduced by Buades et al. to perform nonlocal-means image denoising. Finally, various computational issues are addressed and some results of this image zooming method applied to natural images are presented.

    • Image superresolution using "iterated fourier transform systems"

      In the following paper we introduce a fractal-based method over (complex-valued) Fourier transforms of functions with compact support X subset R. This method of ``iterated Fourier transform systems'' (IFTS) has a natural mathematical connection with the fractal-based method of IFSM in the spatial domain. A major motivation for our formulation is the problem of resolution enhancement of band-limited magnetic resonance images. In an attempt to minimize sampling/transform artifacts, it is our desire to work directly with the raw frequency data provided by an MR imager as much as possible before returning to the spatial domain. In this paper, we show that our fractal-based IFTS method can be tailored to perform frequency extrapolation.

    • Self-similarity of images in the Fourier domain, with applications

      This paper explores the use of self-similarity methods on frequency domain data. A major motivation for our work is provided by recent work showing that images are, in general, affinely self-similar locally: Given a “range block” of an image, there are generally a number of “domain blocks” that can approximate it well under the action of affine greyscale transforms. This spatial domain self-similarity is dramatically demonstrated when errors of approximation are plotted for all domain-range pairings.

      Here we demonstrate that such self-similarity is also exhibited by subblocks of Fourier data. The underlying explanation for this block-based self-similarity is that a connection can be made between the well-known result of autoregressive (AR) correlation coefficients and block-based fractal coding. This justifies block-based fractal coding in the complex Fourier domain, which we then employ for the purpose of frequency extrapolation or magnetic resonance imaging (MRI) data.

  • IFS on vector-valued measures

    We define an abstract framework for self-similar vector-valued Borel measures on a compact space (X,d) based upon a formulation of IFS on such measures. This IFS method permits the construction of tangent and normal vector measures to planar fractal curves. Line integrals of smooth vector fields over planar fractal curves may then be defined. These line integrals then lead to a formulation of Green's Theorem and the Divergence Theorem for planar regions bounded by fractal curves.

  • Iterated Function Systems on Multifunctions

    The following projects represent the vision of Davide La Torre, who joined our group in 2006 (see "A brief history of our group"). We seek to formulate IFS-type operators over spaces of multifunctions, that is, set-valued functions.

    • In the following paper, we introduce a method of IFS over the space of set-valued mappings (multifunctions). This is done by first considering a couple of useful metrics over the space of multifunctions F(X,Y). Some appropriate IFS-type fractal transform operators T : F(X,Y) -> F(X,Y) are then defined which combine spatially-contracted and range-modified copies of a multifunction u to produce a new multifunction v = Tu. Under suitable conditions, the fractal transform T is contractive, implying the existence of a fixed-point set-valued mapping u. Some simple examples are then presented. In particular, we consider the case where u(x) is a closed interval and its application to image coding. We then consider the inverse problem of approximation of set-valued mappings by fixed points of fractal transform operators $T$ and present some preliminary results.

      D. La Torre, F. Mendivil and E.R. Vrscay, Iterated function systems on multifunctions, in Math Everywhere (Springer-Verlag, Heidelberg, 2006).

    • In the following paper, we study the properties of multifunction operators that are contractive in the Covitz-Nadler sense. Such operators T possess fixed points satisying the relation x in Tx. We introduce an iterative method involving projections that guarantees convergence from any starting point x_0 in X to a point x in X_T, the set of all fixed points of the multifunction operator T. We also prove a continuity result for fixed point sets X_T as well as a generalized collage theorem for contractive multifunctions. These results can then be used to solve inverse problems involving contractive multifunctions. Two applications of contractive multifunctions are introduced: (i) integral inclusions and (ii) iterated multifunction systems.

      H.E. Kunze, D. La Torre and E.R. Vrscay, Contractive multifunctions, fixed-pont inclusions and iterated multifunction systems, J. Math. Anal. Appl.330, 159-173 (2007).

  • Fixed point theory for random contraction mappings

    Most natural phenomena or the experiments that explore them are subject to small variations in the environment within which they take place. As a result, data gathered from many runs of the same experiment may well show differences that are most suitably accounted for by a model that incorporates some randomness. Differential equations with random coefficients are one such class of useful models. In this paper we consider such equations as random fixed point equations T(omega,x(omega))=x(omega), where T : omega x X -> X is a given integral operator, omega is a probability space and X is a complete metric space. We consider the following inverse problem for such equations: given a set of realizations of the fixed point of T (possibly the interpolations of different observational data sets), determine the operator T or the mean value of its random components, as appropriate. We solve the inverse problem for this class of equations by using the collage theorem.