Image Curvature Microscope

This workshop may eventually be submitted and published.

Overview
References
Level Lines Affine Shortening
Image Curvature Microscope
On Line Demo
Examples

Adina Ciomaga ciomaga[AT]cmla.ens-cachan.fr
Lionel Moisan moisan[AT]parisdescartes.fr
Pascal Monasse monasse[AT]imagine.enpc.fr
Jean-Michel Morel morel[AT]cmla.ens-cachan.fr

Overview

A new image processing algorithm simulating a subpixel evolution of an image by affine curvature motion.
A subpixelian algorithm computing the image curvature and yielding an accurate numerical image microscope. Illustrations on many image details of all kinds.
Equivalence between Affine Curve Shortening and Affine Curvature Motion: explicit method to construct a viscosity solution for the scalar affine curvature motion, provided we are given the affine shortening evolutions of the level lines of the initial data.

References

Attneave F. Some informational aspect of visual perception
Psychological Review. Vol 61(3), May 1954, 183-193.
Koepfler G., Moisan L. Geometric Multiscale Representation of Numerical Images
Springer Lecture Notes in Computer Science, vol. 1682, pp. 339-350, 1999
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
Pascal Monasse and Frederic Guichard, Fast computation of a contrast invariant image representation
IEEE Trans. on Image Proc, 1998, vol. 9, 860-872.
G. Sapiro and A. Tannenbaum Affine invariant scale-space
International Journal of Computer Vision, 11:25-44, 1993.

Article ref
?preprint on line article

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)$

where k(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:

extraction of the level lines of the bilinear interpolation of the initial image;
independent evolution of each level line by affine curve shortening;
reconstruction of a new image from the evolved level lines.

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:

build the tree of connected components of lower level sets level and the tree of connected components of upper level sets, taking into account the holes in each connected component.
find for each hole in a connected component the connected omponent in the other tree corresponding t it.
merge both trees, putting connected components corresponding to holes as descendants of the ones containing them.

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:

break the curve into convex or concave parts
sample with high precision
apply discrete affine erosion
concatenate the pieces of curves previously obtained.

image reconstruction

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

we enumerate the tree in preorder and
fill the interior of the current level line with its level.

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:

extract and evolve for short time the original level lines, while keeping their global topological structure;
compute discrete curvatures for each evolved polygonal level line;
create a new image that registers at each pixel the average of all discrete curvatures computed for every curve passing by.

On Line Demo

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

Level Lines Shortening - Adina Ciomaga, Pascal Monasse
level lines extraction - FLST - Pascal Monasse
geometric affine scale space of curves - GASS - Lionel Moisan
image reconstruction - Adina Ciomaga, Pascal Monasse
curvature map - Adina Ciomaga

demo

Examples

Curvature display

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

The main outline of the following gallery is to visualise the level lines and the microscopic curvature map of an image. This must be considered as a preprocessing procedure (i.e. the first step in optimizing the data) and not as a self-contained shape recovery method. Various postprocessing methods may be further applied.
Only closed curves are subjected to Affine Shortening. Nevertheless, images may have open level lines, particullarly the ones touching the frame. One may agree to close these lines by measuring the line integral or the surface area. But these will create strong curvatures at the meeting points of the level lines with the image frame. To avoid this phenomena, we suggest and extrapolation method, i.e. to flip the image left and right, up and down for 20 pixels and to add a constant strip of constant width.
The curvature map is printed over the smoothed image and the latter is attenuated (i.e. gray values are concentrated around 128). Curvature values shade from red to green as follows: pozitive curvatures are displayed in red, negative ones in green and zero ones in yellow.

original	curvatures

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

original	curvatures

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 image	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 image	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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).

image	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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.

image	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

Vanishing points of straight lines are line terminators.

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

... up to 3rd order

Dual micropatterns

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

Micropatterns and mirros preattentively undistinguishable

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

and few others

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

buildings, round the corner(s)

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

and how about groups of individuals?

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

Microscopic organic tissus

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

Digital canvas without JPEG artefact?

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

more of fauna and flora

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

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

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering

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

original image

image extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures 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 extraction	original level lines	curvatures before filtering

smoothed image	shortened level lines	curvatures after filtering