This page is a part of CVprimer.com, a wiki devoted to computer vision. It focuses on low level computer vision, digital image analysis, and applications. It is designed as an online textbook but the exposition is informal. It geared towards software developers, especially beginners, and CS students. The wiki contains mathematics, algorithms, code examples, source code, compiled software, and some discussion. If you have any questions or suggestions, please contact me directly.

From Computer Vision Primer

We address the issue of image segmentation of binary and gray scale images. The scientific foundation of the proposed method is topology, the science of continuity and connectedness.

The topological analysis is intended to reveal the most basic things about the image: how many connected components are present, which ones have holes and how many. It is also a part of the analysis to capture these topological features. The next stage is geometric: measuring them and finding their locations. With this data, it may be possible to understand the content of the image.

We will use the tools that are standard in the discipline. The first tool is cell decomposition: the image is represented as a combination of pixels as well as edges and vertices. The second tool is cycles: both the connected components and the holes are captured by circular sequences of edges.

The challenge is that these topological tools have not been commonly applied in the analysis of gray scale images. For example, while in binary images the meaning of connected components is clear, for gray scale images, a “connected component” should be a dark region surrounded by a lighter area. In other words, it is a sublevel set of the gray level function. To deal with the multitude of sublevel sets we record them in a graph. This graph captures the inclusion hierarchy among the sublevel sets. It may be called the inclusion tree. A similar data structure is created for the holes (with the supralevel sets). Combined these two graphs represent the topology of the image, the topology graph. It is the foundation of the image analysis algorithm of Pixcavator. Download the free Pixcavator Student Edition here.

There are a few papers on this subject. One of them has an especially simple example:

J. Andrew Bangham, J. R. Hidalgo, Richard Harvey, Gavin C. Cawley, The Segmentation of Images via Scale-Space Trees, British Machine Vision Conference, 1998.

Their algorithm (called "sieve") produces a tree decomposition of gray scale images as follows. It cuts (simultaneously!) minima and maxima of the gray scale function - slice by slice. The result is a hierarchy of objects (called "granulas") that is recorded as a tree. Their example is below.

An image and its scale tree.

This tree may resemble the topology graph – until you build one. This is what it looks like. Here the gray scale levels run from 0 (E) to 255 (A).

The topology graph for the image. The objects are: mouth E (black), head B (gray), eyes C and D, entire image A (white).

Generally the topology graph isn't a tree (try the negative of this image). This comes as a consequence of treating light and dark objects (maxima and minima) separately and independently. Indeed, dark objects may merge or light objects may split etc as you go up the gray levels.

There are other issues. First, the central (in my view) question of what is object in a gray scale image and how to count them isn’t addressed in this and related papers. Second, the approach is only partially applicable to 3D images as there is no way of capturing tunnels without Homology. Third, it is unclear how this approach can be applied to Color Images. As for Image Simplification, since it is carried out via the sieve, the granule removal is based on size only.

In spite of the differences the testing presented in this paper validates our approach.