Image Curvature Microscope
Adina Ciomaga, Lionel Moisan, Pascal Monasse, Jean-Michel Morel
⚠ This is a preprint. It may change before it is accepted for publication.

Overview

References

  1. Attneave F. Some informational aspect of visual perception
    Psychological Review. Vol 61(3), May 1954, 183-193.
  2. Koepfler G., Moisan L. Geometric Multiscale Representation of Numerical Images
    Springer Lecture Notes in Computer Science, vol. 1682, pp. 339-350, 1999
  3. Moisan L. Affine plane curve evolution: a fully consistent scheme
    Image Processing, IEEE Transactions on Volume 7, Issue 3, Mar 1998 Page(s):411 - 420
  4. Pascal Monasse and Frederic Guichard, Fast computation of a contrast invariant image representation
    IEEE Trans. on Image Proc, 1998, vol. 9, 860-872.
    1. Sapiro and A. Tannenbaum Affine invariant scale-space
      International Journal of Computer Vision, 11:25-44, 1993.

Article ref
Ciomaga A., Monasse P., Morel J.-M. An Image Curvature Microscope, preprint

Level Lines Affine Shortening

Background

The geometric information of an image relies on the topological boundaries of the connected components of the level sets, i.e. the level lines. This topographic map gives a complete representation of an image and has two advantages: it is independent of the gray scale and it is embedded in a tree structure. Monasse and Guichard developed in [4] a Fast Level Set Transform which associates with an image the inclusion tree of connected components of level sets.

This site demonstrates a fully contrast invariant and affine invariant numerical method computing a multiscale image curvature by evolving simultaneously all of the image level lines by affine shortening. The method involves a decomposition of the image into its level lines followed by a reconstruction from the level lines after evolution.

Continuous evolution

Digital images are given in discrete sampled form but the underlying continuous substratum is a assumed to be piecewise \mathcal C^1 and interpolated as such. Within this framework, isolevel sets are finite unions of disjoint Jordan curves, for almost every level. We can therefore apply, separately to each level line, the geometric curve shortening:

\frac{\partial x}{\partial t}=k^{1/3}(x(t),t)\nu(x(t),t)

wherek(x) is the curvature of the level line at x and \nu(x) is the inward, unit vector field to the level line at x.

Solutions exist, they are smooth and the curves disappear in finite time. Due to the inclusion principle, we can reconstruct, at each scale t, a function u(·, t) for which the level lines are the evolutions of the original level lines. We call this function the level lines affine shortening (LLAS) evolution of the initial data u0 , at scale t. We prove in a companion paper that the level lines affine shortening evolution of a function is a viscosity solution of the affine morphological scale space (AMSS) equation.

u_t=|Du|curv(u)^{1/3},

where

Du=(u_x,u_y)=(\frac{\partial u}{\partial x},\frac{\partial u}{\partial y})

and

|Du|(curv(u))^\frac 13=(u_{xx}u_y^2-2u_{xy}u_xu_y+u_{yy}u_x^2)^\frac 13.

Similar results hold for curve shortening.

Discrete evolution

Level Lines Affine Shortening stands for simultaneous affine smoothing of level lines.

The algorithm has three steps:

A detailed description and relevant information is be provided in the following.

level lines extraction

One can decompose an image into its level lines at quantized levels. A fast algorithm, the Fast Level Set Transform (FLST) performing the decomposition into a tree of shapes, is described in [4]. The image is parsed into a set of parametric Jordan curves. This set is ordered in a tree structure, induced by the geometrical inclusion of the level sets, since two Jordan level curves do not meet.

The steps of the algorithm are the following:

level lines evolution

Affine shortening is numerically defined as an alternate filter, which alternates affine erosion and affine dilation. A fast algorithm was proposed by Moisan [2,3] and consists of the iteration of a four-steps process:

image reconstruction

To construct an image from its topo map, given by a family of discrete level lines organized in inclusion tree structure,

With that order, any level line is painted before its descendants, ensuring that its private pixels are at the correct level, while non-private pixels get painted over by the children.

Image Curvature Microscope

The main outcome is thus an accurate curvature estimate on all level lines. As a visualization tool, the fact that all level lines are polygons with real coordinates permits to zoom in the image at an arbitrary resolution. This is necessary to explore visually the intricacy of the local image structure. Hence the name of curvature microscope given to the final visualization.

Whenever we talk about curvatures in a digital image, we actually refear to the curvatures of the level lines associated to the image. In practice, each level line is aproximated by a polygonal line. The discrete formula for the curvature at each vertex is given by the inverse of the circumscribed radius associated to three consecutive points on the curve.

k_i=2\frac{ u_i^1 u_{i+1}^2 - u_i^2 u_{i+1}^1}{u_i u_{i+1} v_{i}}

The algorithm is given as follows:

On Line Demo

The code is written in Megawave2. Implementations are provided by:

Examples

Curvature display

Before going through the examples, several remarks must be pointed out with respect to the curvature display.

originalcurvatures

Gallery

According to the founding Attneave paper [1] visual nformation is redundant. Attneave cheked that the main redundancy results either from areas with homogeneous color or texture, or from contours with homogeneous direction.

Indeed, common objects may be represented with great economy and striking fidelity by marking the points at which their contours change direction maximally and then connecting these points appropriately with a straightedge. The best example is probably the one given by Attneave in 1954, on which the theory was later founded:

Attneave's cat

originalcurvatures

Zoom in here for details

Level lines are concatenations of pieces of hyperbolae and straight segments. Short time smoothing reveal useful invariant features (curvature extremas, inflection points, angles and junctions).

extracted imageoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

LLAS evolution is usefull aswell for JPEG artefact reduction. High oscillations due to JPEG compression are displayed on the level lines map and are strongly reduced by performing affine smoothing. The image can be restored via LLAS image motion, whereas the curvature computing scheme via shortened level lines is blind to the oscillation artefact.

extracted imageoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Geometric shapes

A straight oblique line would present a staircase effect because of its pixel representation, but it is actually perceived serrated. The right angles that it forms contain considerably less information than when a contour contains isolated angle (i.e., a corner). This is because they fall into a pattern that is repetitive (thus easily extrapolated by any subject).

imageoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

junctions, terminators and fattening

When a curve stops onto another curve, T-junctions or Y-junctions are created. In such cases, our perception tends to interpret the interrupted curve as the boundary of some object undergoing oclussion. Junctions are detected via adjiacent positive and negative curvatures. Note that short time smoothing is necessary to distinguish them from the staircase effect.

imageoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

For an image as the checkerboard below, no smoothing is necessary when level lines are vertical and horizontal. But when JPEG artefact is strong, LLAS might help the retrieve shapes and their boundaries. Note also the fattening phenomena that appears at saddle points.

image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

If some segment of an area boundary maintains a constant direction (e.g. arc of a circle) or varies according to some regular function, then the relevant information relies on the locations of its limiting points and the function profile. In the presence of X-junctions, the transparence phenomena occurs. It can be lit up by detecting adjiacent negatiwe, pozitive and zero curvatures.

image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Vanishing points of straight lines are line terminators.

image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Graphics

Aliasing due to pixelization manifests itself along edges due to coarse quantization. The LLS filter might be used for quality improvement of graphics. The perceived contour is the resultant of an averaging process.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

and shape recovering up to what point?

Shape recovery is possible even with badly pixelized shapes. The only drawback is a slight rounding of the corners.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

On the contrary, if the texture is random (downhere except for borders), then fattening happens and shape retrieval becomes almost impossible.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Preattentively undiscriminable textons ...

Julesz conjectured in his second texture perception theory that two different textures cannot be preattentively discriminated if they have the same texton density. The image consists of rotated 10's and S's. These patterns are different but have the same "texton densities", namely the same density of space orientations, corners, terminators, and bar lengths. The microscopic curvature map conforms to our visual perception of these textons, whereas curvatures before filtering are oscillatory.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

... up to 3rd order

Dual micropatterns

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Micropatterns and mirros preattentively undistinguishable

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Textures

Identical or similar stimulus patterns appearing at different places in the same field may be described by describing one and specifying the positions of the others and the type of similarity or how each pattern differs from some skeleton pattern. This is particullary interesting, as common features and invariant factors contribute to homogenity.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

and few others

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering
original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

buildings, round the corner(s)

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering
original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering
original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

biology

Basic morphological differences between bacteria rely on forms and their associations. The shapes are determined by the bacterial cell wall and cytoskeleton. This provides information about the ability of bacteria to acquire nutrients, attach to surfaces or swim through liquids. The curvature is an intrinsic geometrical descriptor, useful for shape discrimination. Ee display bacterial morphologies and the corresponding curvature map. Bacteria porosities are characterised by strong curvature oscillations, whereas the borders of bacterial shapes present smooth curvature variations.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

and how about groups of individuals?

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Microscopic organic tissus

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Paintings

Leonardo's portrait of Mona Lisa is remarkable for its sfumato technique of soft shaded modeling. The stylistic motifs are reflected in the fact that level lines fall widely apart like in a very blurry image.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Digital canvas without JPEG artefact?

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering
original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Nature

The popular JPEG image coding format aims to compress images while maintaining acceptable image quality. This is achieved by dividing the image in blocks of 8x8 pixels and applying a discrete cosine transform (DCT) on the partitioned image. The resulting coefficients are quantised, less significant coeficients are set to zero. Consequently, several types of artifacts can appear such as Gibbs's oscillations, staircase noise along curving edges or checkerboarding. The phenomena is illustrated below. As can be seen, Level Lines Shortening might be used as a post processing technique for JPEG artefact reduction. However, one shouldn't expect to improve the overall image quality as it remains a diffusion process.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

more of fauna and flora

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering
original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering
original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Topography

Digital elevation models represent ground surface topography. Gray levels indicate ground elevation (lightest shades for highest elevations) and therefore the image level lines are true level lines. As can be seen in the image below, the set of level lines of a digital image is a natural representation of the shape contents, as it provides topological information invariant to contrast changes. Bilinear interpolation is the most local of continuous interpolations and preserves order between the gray levels of the image. Thus level lines with different gray level never touch. However, they are concatenations of pieces of hyperbolae and straight segments and hence present oscillations along transversal contours. Useful invariant features such as curvature extremas and inflection points are not relevant for shape recognition. Short time smoothing reduces oscillations and straightens up edges. Curvature extremas after filtering become relevant as geometric shape descriptors.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

or maybe google and satellites

Ringing, aliasing, JPEG artefacts can be removed with short time affine smoothing. The topology of the terrain is easily restablished.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Low resolution satellite image may suffer the same defects. Although details are lost, some background can still be recovered.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Text processing

Pixelized written text can be efficiently restored. The image below was run with the above algorithm. The resulting image is a bit blurred, but one can reconstruct a binary image by applying an adequate grey level threshold. Level lines follow well the letter contours and the affine curvature shortening permits to compute the real curvatures.

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering
original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

And don't forget to look (out) for the cars!

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering

Cores, bifurcations and ridge endings characterize uniquelly fingerprints. Level Lines Affine Shortening removes oscillations due to the grid or JEPG compression and provides a smooth version of the fingerprint, whereas the curvature map locates its characteristic points. It is readble the advantage of a subpixel smoothing, which tears appart ridges and emphasizes crossovers; pores dissapear and islands shrink, so that the resulting image is very much alike the original print.

Fingerprints

original image
image extractionoriginal level linescurvatures before filtering
smoothed imageshortened level linescurvatures after filtering