Discrete Derivative Approximations with Scale-Space Properties: A Basis for Low-Level Feature Extraction

Tony Lindeberg

J. of Mathematical Imaging and Vision, 3(4), pp. 349--376, 1993.

Also available as technical report ISRN KTH/NA/P--92/12--SE.

Abstract

This article shows how discrete derivative approximations can be defined so that scale-space properties hold exactly also in the discrete domain. Starting from a set of natural requirements on the first processing stages of a visual system, the visual front end, an axiomatic derivation is given of how a multi-scale representation of derivative approximations can be constructed from a discrete signal, so that it possesses an algebraic structure similar to that possessed by the derivatives of the traditional scale-space representation in the continuous domain. A family of kernels is derived which constitute discrete analogues to the continuous Gaussian derivatives.

The representation has theoretical advantages to other discretizations of the scale-space theory in the sense that operators which commute before discretization commute after discretization. Some computational implications of this are that derivative approximations can be computed directly from smoothed data, and that this will give exactly the same result as convolution with the corresponding derivative approximation kernel. Moreover, a number of normalization conditions are automatically satisfied. The proposed methodology leads to a conceptually very simple scheme of computations for multi-scale low-level feature extraction, consisting of four basic steps;

large support convolution smoothing,
small support difference computations,
point operations for computing differential geometric entities, and
nearest neighbour operations for feature detection.

Applications are given demonstrating how the proposed scheme can be used for edge detection and junction detection based on derivatives up to order three.

Keywords: scale-space, visual front end, smoothing, Gaussian filtering, Gaussian derivative, discrete approximation, edge detection, junction detection, multi-scale representation, computer vision, digital signal processing

Full paper: (PostScript 1.4Mb) (PDF 0.2Mb)

Further work: (Scale selection for differential feature detectors) (Junction detection with automatic scale selection) (Shape from texture) (Shape from disparity gradients)

Tony Lindeberg <tony@bion.kth.se>