A short outline of the procedure (cf. text below):

The goal is to extract:

Points:
- Junctions (intersections of lines)
- Dots (isolated, circular symmetric, small point-type regions)
Lines:
- Step Edges (contour lines, i. e. common boundary of two regions)
- Bar Edges like drawings (elongated, line-type regions, maybe isolated or open, i.e. not connected to other lines)
Blobs:
- homogeneous image regions
Topological neighborhood relations between the features

(In case some of the features or the relations are not necessary for the application any selection or combination can be defined by the users in the control file of FEX. It is also possible to use the edge pixel chains instead of the chain approximation, i.e. the polygons).

The FEX procedure consists of three main parts:

Extraction of point areas and line areas of interest. These areas indicate the approximate location of the different feature types
Location of points and lines with high accuracy within the point and line areas of interest. And, the approximation of line pixel sequences (chains) and blob boundaries by analytic functions (here straight lines)
Extraction of neighborhood relations between the features.

1. Step: Classification

Homogeneity:

The definition of homogeneity is based on the gradients of the image function. In the TESTPTATTERN image and also in the other examples of this demo the image function is simply the intensity function, but the concept of FEX allows also to define the image function by colour or texture. E.g.. the homogeneity criteria is defined for an arbitrary number of input channels, thus works also for the RGB-space. We model the observed greylevel g(r,c) of the pixel at position (r,c) to be the real (noise-free) greylevel f(r,c) overlayed with image noise n(r,c), thus

g(r,c) = f (r,c) + n(r,c).

n(r,c) is assumed to be signal dependent and POISSON distributed. We estimate the image noise within FEX automatically. This allows later to define, also automatically, the signal dependent thresholds of the homogeneity criteria, which are e.g. required for the extraction of the regions.

Shape:

Non-homogeneous image areas are analyzed further for the shape of inhomogeneity: Similar gradient directions within a local neighborhood indicate that we have a linear feature (step edge or line edge), changing gradient directions within a local neighborhood, e.g. a high curvature, indicate a point type feature (corner, junction, dot).

Output of 1. Step: Ternary Image

Given the input image we first calculate the homogeneity measure and shape measure for each pixel. This leads to two (iconic) feature images. We are then able to classify at each image position, whether the pixel lies in a homogeneous blob, or whether the pixel belongs to, or is influenced by a line type feature or by a point type feature, thus belongs to a point region or a line region. This classification leads to the ''3-feature-class-image'', the Ternary Image.

2. Step: Feature Location:

Within the point-type and the line-type-areas, indicated in the Ternary Image, the estimation procedures of the accurate position of the points and the lines takes place. A set of iconic feature images is necessary to find the best positions of points and line points. (cf. Claudia Fuchs: Image Segmentation in: Second Course for Digital Photogrammetry,ipb, Bonn, 1994). Sequences of line points are finally approximated by straight lines (i.e. line segments, polygons). Applying a connected components algorithm for all homogeneous areas of the Ternary Image directly leads to the blobs. Similarly to the lines, the blob boundaries (including the blob holes) can be approximated by line segments (here always closed polygons).

Output of 2. Step: Symbolic Feature Description

All features are described by their geometric and/or radiometric properties, also including quality aspects, e.g the covariance matrix of the point coordinates as a measure of the geometric accuracy of the points, or the variance of the greylevels within the blobs as a quality measure of the blob homogeneity.

The features are stored in lists, thus we now have a vector type or symbolic description of the image structure.

3. Step: Neighborhood Relations

To estimated the neighborhood relations between the features, we build up a label image of all features and calculate the exoskeleton (the Voronoi Diagram) in the label image. The surrounding areas of the features bounded by the exoskeleton lines are called feature regions.

Each exoskeleton line indicates a neighborhood relation between two features, the nodes of the exoskeleton indicate the neighborhood of at least three features. The neighborhood relations are characterized by some attributes: e.g. to describe the connectivity or the strength of a neighborhood relation we calculate and store the length of the exoskeleton line between the two features.

Output of 3. Step: Feature Adjacency Graph FAG

We collect all relations derivable by the exoskeleton. Then, features and neighborhood relations define an attributed planar graph, the FEATURE ADJACENCY GRAPH, where the features correspond to the graph nodes and the neighborhood relations correspond to the graph edges. The FAG is saved in a ASCII FILE in the ''Global Exchange Format'' (cf. FEX home page), including the image characteristics (e.g. the image noise), and also the defined control parameters.