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

# Algorithm for grayscale images

In order to perform topological analysis of a gray scale image we construct its topology graph.

Outline:

1. All pixels in the image are ordered in such a way that all darker pixels come before lighter ones.
2. Following this order, each pixel is processed:
1. add its vertices, unless those are already present as parts of other pixels;
2. add its edges, unless those are already present as parts of other pixels;
3. add the face of the pixel.
3. At every step, the graph is given a new node and arrows that connect the nodes in order to represent the merging and the splitting of the cycles:
1. adding a new vertex creates a new component;
2. adding a new edge may connect two components, or create, or split a hole;
3. adding the face to the hole eliminates the hole.
4. Filter the noise nodes
1. Select the tips of branches (leaves)

The algorithm is virtually identical to the one for binary images.

N is the number of pixels in the image.

• The time of the construction is O(N2).
• The memory is O(N).
• The time of filtering is O(N).

Only step 3.2 has any difficulty. However, thanks to cell decomposition of images, there are only 4 cases to consider. See Pseudocode for gray scale images