Precise image-based measurement
through irregular sampling

Here I copy a few relevant sections from the VR project proposal that was funded.
Principal Investigator: Cris Luengo.
Co-PI: Matthew Thurley.

Problem Statement

Operations within mathematical morphology depend strongly on the sampling grid (Luengo Hendriks & van Vliet, 2003), and therefore always produce a result different from what would be obtained by the corresponding continuous-domain operation. However, measurements derived from a sampled image should correspond to measurements of the object being imaged. That is, image-based measurements are ideally sampling invariant. For example, see Figure 1: a shift of the sampling grid changes the result of the dilation; a linear filter would have produced a sampled version of the same continuous-domain function in both cases. There are three reasons why the morphological operators are not sampling invariant:

• The output is given by the supremum or infimum (maximum or minimum) value in a neighbourhood. But it is very likely that a local extremum falls in between sampling grid points (as happens in the example of Figure 1), and therefore the discrete operator produces a different value than the continuous-domain operator would.
• The operators produce lines along which the derivative is not continuous (see Figure 2). These discontinuities introduce infinitely high frequencies, making the result not band limited; therefore, the result cannot be represented using the classical sampling theorem.
• The structuring element is a set, and thus in the discrete case, the image is probed with a shape limited by the sampling grid. On a rectangular sampling grid it is impossible to define a rotationally invariant set.

We propose to tackle these three issues by stepping away from the classical sampling theory. Instead, we will use irregular sampling in such a way that local maxima and minima are always sampled, and increasing the sampling density in areas with a non-continuous derivative. At the same time, it should be possible to reduce the sampling density in plateaus (flat areas), also commonly produced by these operators.

The watershed transform (Vincent and Soille, 1991) is a very commonly used algorithm to segment an image. It divides the image into regions separated by ridges of high grey values. The classical watershed algorithm selects a set of pixels as boundaries between regions. Some other implementations assign all pixels to one of the regions, making the segmentation boundary run in between pixels. In either case, the boundary between regions is given by integer grid coordinates, even though the ridges in the image can be located with much higher precision. Determining these region boundaries with a higher precision would improve many measurement tasks.

Significance

The intersection proposed here between classical mathematical morphology on a discrete grid and the continuous-domain information provided by band-limited, sampled images, is not studied at all in the literature (besides a few papers published published by the applicants). Nonetheless, this combination has the potential to yield image measurement tools with significantly increased precision over existing tools. Image-based measurement is very common, and becoming more important. Mathematical morphology with increased precision is applicable everywhere where better precision or more efficient algorithms are required. The two applications discussed in the plan are good test beds for the methods to be developed, but represent only a fraction of the possible applications. Other results of applying these algorithms could be, for example:

• a better chance at differentiating healthy from pre-cancerous cells in a Pap smear;
• reduced tolerance in nanofabrication, as certain tools might be controlled more precisely;
• increased data acquisition speed and reduced memory requirements for aerial mapping; or
• improved localization in SLAM (simultaneous localization and mapping).

Previous Work

Brockett and Maragos (1994) proposed PDEs to compute the continuous-domain dilation and erosion in the discrete domain. Many authors since have improved on these PDEs and their implementations. However, these methods still yield a worse approximation to the continuous-domain operators than the discrete operators. The main reason for this is that the result of the morphological operators is not band limited, and therefore cannot be represented on a regular grid. The more iterations are needed to solve the PDE, the more the result deviates from the expected result. Furthermore, these methods are very slow. These two flaws together make morphological PDEs not useful in practice.

Thurley (2002; Thurley and Ng, 2005) proposed morphological operators for irregularly sampled 3D surface data that used continuous-domain structuring elements. This allowed analysis without resampling to a regular grid nor interpolating to fill holes. These operators shifted sample points along the z axis only. (See the "Preliminary results" section for more details.)

Luengo (Luengo Hendriks and van Vliet, 2005; Luengo Hendriks et al., 2007) proposed operations that are, strictly speaking, not morphological operators, but their results approximate continuous-domain morphology better than the true discrete operators, and, consequently, can be used to perform more accurate measurements. These operations, besides a few other tricks, rely on interpolation to improve their result. (See the "Preliminary results" section for more details.)

We have not been able to identify other work relating the discrete and continuous-domain morphological operators.

Preliminary results

Some time ago Luengo worked on increasing the precision and accuracy of one commonly used measurement tool from mathematical morphology: the granulometry (Luengo Hendriks et al., 2007). The granulometry is a multi-scale operation that yields a size distribution of objects, or of one of the phases of a multi-phase material. By ignoring strict compliance to the properties of the granulometry in the discrete grid, he was able to create a discrete operation that better approximates the properties of its continuous-domain counterpart, in particular the scale sampling and rotation invariance. He modified the way that the structuring element is defined, and used interpolation to further improve the results at small scales.

In the same vein, Luengo has proposed to implement dilations and erosions with lines under arbitrary orientation using interpolation (Luengo Hendriks and van Vliet, 2005). This implementation again provides results much closer to its continuous-domain counterpart, at the expense of strict compliance to properties of the discrete operation.

Finally, Luengo Hendriks and van Vliet (2003) presented continuous-domain implementations of the basic morphological operators for a sampled, one-dimensional, band-limited function. Here, Luengo created a piecewise polynomial representation of the sampled function, and transformed these polynomials to obtain the result of the morphological operators. However, this seemed a dead end, as extending this to higher dimensions would be prohibitive.

Thurley (2002; Thurley and Ng, 2005) defined morphological operators (dilation and erosion, their compositions, as well as more complex tools such as reconstruction by dilation and the watershed segmentation) for irregularly sampled 3D surface points. The operators used the z coordinate (height) as the intensity value; the x and y position of the samples was not changed by these operators. This allowed analysis of scanned rock piles without resampling to a regular grid nor interpolating to fill holes. However, structuring element decomposition, an often used property of the elemental morphological operators, whilst still practically applicable, was not strictly satisfied.

In relation to this work, Thurley developed a prioritised interpolation scheme using limitations of the surface topology (Landström et al., 2011), which allows a better estimate of portions of the surface hidden from view of the camera. That is, the holes in the data could be filled in more reliably.

References

R.W. Brockett, and P. Maragos (1994), Evolution equations for continuous-scale morphological filtering, IEEE Transactions on Signal Processing 42(12):3377-3386.

A. Landström, F. Nellros, H. Jonsson, and M. Thurley (2011), Image reconstruction by prioritized incremental normalized convolution, in: Image analysis, LNCS 6688:176-185, Springer.

C.L. Luengo Hendriks, G.M.P. van Kempen, and L.J. van Vliet (2007), Improving the accuracy of isotropic granulometries, Pattern Recognition Letters 28(7):865-872.

C.L. Luengo Hendriks, and L.J. van Vliet (2003), Basic morphological operations, band-limited images and sampling, in: Scale Space Methods in Computer Vision, LNCS 2695:313-324, Springer.

C.L. Luengo Hendriks, and L.J. van Vliet (2005), Using line segments as structuring elements for sampling-invariant measurements, IEEE Transactions on Pattern Analysis and Machine Intelligence 27(11): 1826-1831.

M. Thurley (2002), Three dimensional data analysis for the separation and sizing of laboratory rock piles, PhD Thesis, Monash University.

M. Thurley, and K.C. Ng (2005), Identifying, visualizing, and comparing regions in irregularly spaced 3D surface data, Computer Vision and Image Understanding 98(2):239-270.

L. Vincent, and P. Soille, Watersheds in digital spaces: an efficient algorithm based on immersion simulations, IEEE Transactions on Pattern Analysis and Machine Intelligence 13(6):583-598.

© 2014 Cris Luengo
Last modified November 26, 2014.