Subdivision schemes for curve design and image analysis

Staff - Faculty of Informatics

Date: / -

Università degli Studi Milano Bicocca, Italy


You are cordially invited to attend the PhD Dissertation Defense of Elena VOLONTÉ on Thursday, January 18th 2018 at 10h30 in room 3014 – building U5, Università degli Studi di Milano-Bicocca, Italy

Joint research doctoral thesis

Subdivision schemes are able to produce functions, which are smooth up to pixel accuracy, in few steps of an iterative process. Therefore, they are a powerful tool for displaying functions in computer graphics and signal analysis. My thesis focuses on two of these applications: one by studying the regularity of the limit curve, and one by analysing anisotropic phenomena in image processing.

Being an iterative process, the first inquiry about a subdivision scheme is if it converges. For this reason a lot of research on subdivision schemes concerns the smoothness of the limit curve. Linear schemes are well investigated in this sense, because the new points are a linear combination of points from the previous iteration. Instead in non-linear schemes, the new points depend in a non-linear way on the points from the previous step. This type of schemes are not generally exploited but they are an interesting tool to guarantee some geometric properties of the limit curve. For non-linear schemes, in many cases, there are only ad hoc proofs or numerical evidence about the regularity of these schemes. The first paper that covers this lack of studies is by Dyn and Hormann, where they give sufficient conditions on the convergence and tangent continuity of an interpolatory scheme. The peculiarity of their approach is to consider entities like tangents and curvatures. The summability of the sequences of maxima edge lengths and angles ensure that the limit curve is tangent continuous. The aim of my work is to find a geometric condition for the curvature continuity of the limit curve. The curvature is the reciprocal of the radius of the osculating circle which is the limit of the circles passing through three point q, p, r when q and r converge to p. To require the continuity of the curvature it seems natural to come up with a condition that depends on the difference of curvatures of neighbouring circles. The proof of the proposed condition is not completed, but we give a numerical evidence of it.

Subdivision schemes can also be used in image analysis. Due to their relation with a multiresolution analysis, interpolatory subdivision schemes allow to analyse a signal. One crucial issue is the analysis of anisotropic signals with the aim to catch directional edges. When dealing with anisotropic phenomena, wavelets do not provide optimally representations. For this reason directional transforms were introduced. Among them, the shearlet transform is interesting because it provides the general approach of multiple subdivision scheme where in each iteration an expanding matrix and a subdivision scheme are chosen in a finite set. The expanding matrices are responsible for the refinement: in this sense we require that they are jointly expanding. In order to define a directional transform it is crucial that the expanding matrices satisfy the slope resolution property. In the shearlets case the expanding matrices considered are the product of a diagonal matrix and a pseudo rotation matrix called shear. The drawback is that the diagonal matrix considered has large determinant that leads to a quite substantial complexity in implementations. In my work we overcome this problem by proposing, for any dimension, a family of matrices, product of an anisotropic diagonal matrix and a shear matrix, whose determinant is considerable lower than the shearlet case. We prove that the elements of this family satisfy all the prescribed properties. In this sense we are able to define a directional transform and we test the performance with some images. For dimension d=3, we also study the possibility to reduce even more the determinant by relaxing the structure of the matrix.


Dissertation Committee:

  • Dr. Milvia Rossini, Università degli Studi di Milano-Bicocca, Italy (Research advisor)
  • Prof. Kai Hormann, Università della Svizzera italiana, Switzerland (Research advisor)
  • Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Internal Member)
  • Prof. Lourenco Beirao Da Veiga, Università degli Studi di Milano-Bicocca, Italy (Internal Member)
  • Prof. Costanza Conti, Università di Firenze, Italy (External Member)
  • Prof. Ulrich Reif, Technische Universität Darmstadt, Germany (External Member)