Discrete Scale-Space Theory and the Scale-Space Primal Sketch

Tony Lindeberg

PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44 Stockholm, Sweden, May 1991. (ISRN KTH NA/P--91/8--SE)

---

To request a printed copy of this PhD thesis, including all the figures, please contact your library or ask a secretary at our department providing the numbers CVAP84 and ISRN KTH NA/P--91/8--SE.

Extended book version

Note! The PhD thesis contains some details that are not included in the book.

---

Scanned version - with all the figures: (PDF 57.3Mb)

Text version - unfortunately with missing figures: (PDF 2,3Mb)

---

Abstract

This thesis, within the subfield of computer science known as computer vision, deals with the use of scale-space analysis in early low-level processing of visual information. The main contributions comprise the following five subjects:

• The formulation of a scale-space theory for discrete signals. Previously, the scale-space concept has been expressed for continuous signals only. We propose that the canonical way to construct a scale-space for discrete signals is by convolution with a kernel called the discrete analogue of the Gaussian kernel, or equivalently by solving a semi-discretized version of the diffusion equation. Both the one-dimensional and two-dimensional cases are covered. An extensive analysis of discrete smoothing kernels is carried out for one-dimensional signals and the discrete scale-space properties of the most common discretizations to the continuous theory are analysed.

• A representation, called the scale-space primal sketch, which gives a formal description of the hierarchical relations between structures at different levels of scale. It is aimed at making information in the scale-space representation explicit. We give a theory for its construction and an algorithm for computing it.

• A theory for extracting significant image structures and determining the scales of these structures from this representation in a solely bottom-up data-driven way.

• Examples demonstrating how such qualitative information extracted from the scale-space primal sketch can be used for guiding and simplifying other early visual processes. Applications are given to edge detection, histogram analysis and classification based on local features. Among other possible applications one can mention perceptual grouping, texture analysis, stereo matching, model matching and motion.

• A detailed theoretical analysis of the evolution properties of critical points and blobs in scale-space, comprising drift velocity estimates under scale-space smoothing, a classification of the possible types of generic events at bifurcation situations and estimates of how the number of local extrema in a signal can be expected to decrease as function of the scale parameter. For two-dimensional signals the generic bifurcation events are annihilations and creations of extremum-saddle point pairs. Interpreted in terms of blobs, these transitions correspond to annihilations, merges, splits and creations.

Experiments on different types of real imagery demonstrate that the proposed theory gives perceptually intuitive results.

Keywords: computer vision, low-level processing, scale-space, diffusion, Gaussian filtering, discrete smoothing, primal sketch, segmentation, descriptive elements, scale detection, image structure, focus-of-attention, tuning low-level processing, blob detection, edge detection, edge focusing, histogram analysis, junction classification, perceptual grouping, texture analysis, critical points, classification of blob events, bifurcations, drift velocity, density of local extrema, multi-scale representation, digital signal processing

Further reading: (Monograph on scale-space theory) (Other publications on scale-space theory) (Encyclopedia entry on scale-space theory)