Graph representation of gray scale images
More precisely, this article is about graph representation of the topology of gray scale images (an image becomes a graph when one uses adjacency). The connected components of upper and lower level sets of the gray scale function are building blocks of segmentation.
The idea is that it is unlikely that a boundary of a real object depicted in the image cutting through upper or lower level sets. However, one can imagine a picture with bald spot merging with the sky behind.
The connected components of the lower level sets have a clear hierarchy based on inclusion. This hierarchy provides a graph representation of the topology of the image.
Such an arrangement of sets is represented by an inclusion tree. In general the inclusion tree of an image may be complex.
Similar analysis applies to upper level sets – light holes in dark components. See also Tree representation of images.
The problem with inclusion trees: The inclusion trees for upper and lower level sets, if considered separately, do not help in finding out which object has which hole. Therefore, in order to capture the topology of the image (with holes), the two trees have to be combined in some way.
Combined inclusion tree
Level set are the boundaries of the upper and lower level sets. The Jordan Theorem implies that a component of a level set encircles or is encircled by components of other level sets. Then the outer borders of the lower and upper level sets are still ordered and the result is a tree.
For example: P. Monasse and F. Guichard, Fast computation of a contrast invariant image representation. IEEE Transactions on Image Processing, 9(5), pp. 860–872, 2000.
This is how the lower and upper level trees are normally merged. There are drawbacks for this approach.
- The lower level sets are mixed with the upper level sets.
- The gray levels are also mixed.
The topology graph of the image
There is an alternative way to combine the inclusion trees.
The upper level tree is turned upside down and attached to the lower level tree – along the aligned layers corresponding to the gray levels. (Reminds slightly of the structure of the DNA.)
- The lower and upper inclusion trees remain intact within the graph.
- The graph breaks into layers that coincide with the topology graphs of the binary images obtained via thresholding.
- The topology graph is not a tree in general.
For more details see Topology graph.
See also Graph representation of color images.