SPIE Membership Get updates from SPIE Newsroom
  • Newsroom Home
  • Astronomy
  • Biomedical Optics & Medical Imaging
  • Defense & Security
  • Electronic Imaging & Signal Processing
  • Illumination & Displays
  • Lasers & Sources
  • Micro/Nano Lithography
  • Nanotechnology
  • Optical Design & Engineering
  • Optoelectronics & Communications
  • Remote Sensing
  • Sensing & Measurement
  • Solar & Alternative Energy
  • Sign up for Newsroom E-Alerts
  • Information for:


Print PageEmail PageView PDF

Electronic Imaging & Signal Processing

Exploiting optimum connectivity in image analysis

A graph-based approach to the design of image-processing operators takes into account adjacency relations and connectivity functions for enhanced speed and effectiveness.
23 October 2009, SPIE Newsroom. DOI: 10.1117/2.1200910.1830

The goal of image analysis is to take action based on interpretation of a picture's content. The process may require filtering, segmentation, representation, and classification. Segmentation extracts objects of interest from the image. Filtering aids segmentation and corrects its result. A compact representation of an object's features is used in classification, which assigns the image to a category depending on a corresponding action. Current imaging technologies create extra challenges for analysis by offering high-resolution and vast databases, and encouraging a growing demand for efficient and effective processing methods.

Optimum connectivity between image elements can be exploited to filter images without creating false edges, as well as to group pixels into objects (segmentation), create multiscale representations for extracting shape descriptors, and cluster objects into categories (classification). These problems can be elegantly unified in an optimum-set partition problem and efficiently reduced to an optimum-path forest (OPF) in a graph derived from the image (or from a set of objects for classification). We call this method image foresting transform1 (IFT). Generalizing it to arbitrary data sets enables the design of OPF classifiers.2,3

Figure 1. (a, b) Interactive image foresting transform (IFT) segmentation by marker competition. (c) Automatic brain segmentation based on an object model and IFT. (d) Automatic segmentation of a wrist by optimum-path forest (OPF) clustering.

The IFT takes image elements (pixels or objects) as nodes of a graph whose arcs are defined by some adjacency relation. A connectivity function assigns a value to any path, including trivial ones formed by a single node. Considering the maximum (minimum) value among all possible paths with a terminus at each node, the optimum path is trivial for some nodes, called roots. The remaining nodes will have an optimum path coming from their most strongly connected root, partitioning the graph into a disjoint set of optimum-path trees. The operators are simply reduced to a local processing operation on attributes of this forest (e.g., paths, connectivity values, and root labels).

Figure 2. (a) Euclidean distance transform of a leaf and (b) its multiscale skeletons. (c) Saliences (i.e., points of interest) of an internal skeleton obtained from (b). (d) Contour saliences computed on the basis of the internal and external skeletons.

The IFT extends Dijkstra's shortest-path algorithm to multiple sources (which may be embedded in the connectivity function) and more general connectivity functions. For sparse graphs, several image operators can be implemented in linear time. Further optimizations are possible with differential IFTs,4 hardware-based implementations,5 and variants for specific applications.6 The IFT's unified framework helps to provide a better understanding of the theoretical relation among certain image operators.7

Connected filters improve image quality1 and extract image features for segmentation.8 The connectivity function computes arc weights based on these features and object information. This provides a reliable approach for several interactive segmentation paradigms according to user-selected markers8: see Figure 1(a, b). Object models have also been proposed and combined with the IFT in a synergistic way for fast and accurate automatic 3D segmentation of medical images9: see Figure 1(c). Automatic segmentation can also be computed by OPF clustering3: see Figure 1(d).

Euclidean distance transform by IFT—see Figure 2(a)—enables fast tensor-scale computation10 and one-pixel-wide and connected multiscale skeletonization11—see Figure 2(b)—whose shape saliences are easily detected and related to those of the contour12: see Figure 2(c, d). We have also experimented with10,12 shape descriptors for content-based image retrieval and classification. We recently applied the supervised OPF classifier2 to several applications. Its accuracy is comparable to that obtained by support vector machines, but its computational performance is far superior.

The idea of exploiting connectivity by optimum paths in a graph derived from a data set opens avenues to the design of fast and effective image-analysis operators. This is especially important for large-image data sets, which nowadays are very common. Our future efforts will include a parallel IFT to exploit the recent and upcoming technologies of multicore machines, its combination with other image analysis techniques, and new learning algorithms for the OPF classifiers.

Alexandre Falcão
Laboratory of Visual Informatics
Institute of Computing
University of Campinas
Campinas, Brazil

Alexandre Xavier Falcão has been a professor since 1998. His research focuses on image processing and analysis, volume visualization, content-based image retrieval, mathematical morphology, pattern recognition, and medical imaging. His main contributions are live-wire segmentation and IFT.