 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 EAlerts
 Information for:
Advertisers




Electronic Imaging & Signal Processing
Exploiting optimum connectivity in image analysis
Alexandre Falcão
A graphbased approach to the design of imageprocessing 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 highresolution 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 optimumset partition problem and efficiently reduced to an optimumpath forest (OPF) in a graph derived from the image (or from a set of objects for classification). We call this method image foresting transform^{1} (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 optimumpath 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 optimumpath 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 shortestpath 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} hardwarebased 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 quality^{1} 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 userselected markers^{8}: 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 images^{9}: see Figure 1(c). Automatic segmentation can also be computed by OPF clustering^{3}: see Figure 1(d). Euclidean distance transform by IFT—see Figure 2(a)—enables fast tensorscale computation^{10} and onepixelwide and connected multiscale skeletonization^{11}—see Figure 2(b)—whose shape saliences are easily detected and related to those of the contour^{12}: see Figure 2(c, d). We have also experimented with^{10,12} shape descriptors for contentbased image retrieval and classification. We recently applied the supervised OPF classifier^{2} 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 imageanalysis operators. This is especially important for largeimage 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, contentbased image retrieval, mathematical morphology, pattern recognition, and medical imaging. His main contributions are livewire segmentation and IFT.


