This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.

A graph representation of the topology of color images by Saveliev

From Intelligent Perception

Jump to: navigation, search

A graph representation of the topology of color images by Peter Saveliev

In a binary image, we think of black objects as connected components and white objects as holes in the black objects. Next, in gray scale images we capture the connected components of upper and lower level sets of the gray level function of the image. The rationale for this approach is that these sets are arguably building blocks of real items depicted in the image. Now we would like to extend this idea to color images.

We concentrate on darker areas surrounded by lighter background and lighter areas surrounded by darker background, i.e., the lower and the upper level sets of the “gray level function” that defines the image. Given a gray scale image $X$ with gray level function $g: X → \{0,..,255\}$, the connected components of the upper level sets $\{x: g(x) ≥ L\}, L=0,..,255$, of $g$ have a clear hierarchy represented by the inclusion tree. There is also the inclusion tree of the lower level sets, $\{x: g(x) ≤ L\}$. The connected components of the upper level sets may be objects and the connected components of the lower level sets may be holes in these objects. In addition to these, in order to capture the topology of the image, we need to know which hole corresponds to which object [1], [2].

In [3] we presented an extension of this lower/upper level set approach by introducing the topology graph.

In a gray scale image $S$, the connected components of the lower and upper level sets are organized in the topology graph $G$ of a gray scale image the arrows of which indicate inclusions. The inclusion trees of the lower and the upper level sets remain intact inside this graph (red and green nodes respectively): the latter is turned upside down and attached “horizontally” to the former.

Each gray level $L=0,..,255$ can be used to threshold S which results in a binary image $B$. Then the topology graph of $B$ appears as a “horizontal” layer in G corresponding to $L$ (blue rectangle).

Once noise (crossed circles) is removed, the leaves of the remaining graph (blue circles) are the objects and holes of the image.

Now, it is possible to threshold an RGB color image so that a binary image is created for each combination of red, green, and blue. Then a modification of the algorithm builds the topology graph of the color image from the topology graphs in these binary images.

In the case of color images it is not possible anymore to appeal to the dark versus light argument or to the mathematics of upper and lower level sets.

The RGB color space is $C = \{(r, g, b): 0 ≤ r, g, b ≤ 255\}$. There is a natural partial order on $C$:

  • $(r, g, b) ≤ (r’, g’, b’)$ if $r ≤ r’, g ≤ g’, b ≤ b’$.

We concentrate on darker areas surrounded by lighter background and lighter areas surrounded by darker background, i.e., the lower and the upper level sets of the “color function” that defines the image.

Suppose we are given a color image with color function $c: X → \{0,..,255\}^3$. We concentrate on the connected components of the lower level sets ${x: c(x) ≤ (r, g, b)}$ and the upper level sets $\{x: c(x) ≥ (r, g, b)\}, r, g, b = 0, .., 255$, of $c$ with respect to this partial order. These sets will be considered as the objects and holes in the image respectively. These sets are organized in the topology graph of the color image, which is a directed graph based on inclusion.

The topology graph is illustrated below. Suppose the image has only blue and green: $(0,g,b)$. For each $g$ fixed the image has only one parameter and, just like a gray scale image, is represented by a topology graph. These graphs are the “vertical” slices of the full graph stacked behind each other.

With all three colors involved the topology graph is like a 3d grid with each cell containing the topology graph of the corresponding binary image.

Then, in order to capture objects and holes in the image one needs to capture objects and holes in all of its possible binarizations (via thresholding), without double counting. This idea is used in the construction below.

The (augmented) topology graph of the color image is constructed as follows:

  • All pixels in the image are ordered according to the partial order of the color space.
  • Following this order, each pixel is processed as follows:
    • add its vertices, unless those are already present as parts of other pixels;
    • add its edges, unless those are already present as parts of other pixels;
    • add the face of the pixel.
  • At every step, the augmented graph is given a new node and arrows, as follows:
    • adding a new vertex creates a new component in the complex;
    • adding a new edge may connect two components, or create, or split a hole;
    • adding the face to the hole eliminates the hole.
  • Remove the nodes that represent noise.
  • Choose the leaves of what’s left from the inclusion trees.

If one applies this approach to a gray scale image the results will be identical to the ones that come from the gray scale analysis presented earlier. A similar conclusion is reached when an image has one single color varied in terms of its intensity.

The complexity of the algorithm is at most $O(N^2)$, where $N$ is the number of pixels in the image. Testing of the algorithm has produced expected results.

REFERENCES

  • [1] Bangham, J. A., Hidalgo, J. R., Harvey, R., and Cawley, G. C., “The segmentation of images via scale-space trees”, British Machine Vision Conference, 33-43 (1998).
  • [2] Monasse, P. and Guichard, F., “Fast computation of a contrast invariant image representation”, IEEE Transactions on Image Processing 9 (5), 860–872 (2000).
  • [3] Saveliev, P., “A graph, non-tree representation of the topology of a gray scale image by Saveliev”, Proceedings of SPIE, Image Processing, Algorithms and Systems IX, 2011, Volume 7870, O1-O19.