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)

For the last stages see also Stages of analysis.

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(N²).
• The memory is O(N).
• The time of filtering is O(N).

See also Processing time.

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

See also Image Simplification.

The time complexity of the algorithm is O(n²), where n is the number of pixels in the image. See also Processing time.

Further see Grayscale images - implementation.

Exercise. Create a simple interface for the program without simplification and run it. The output should be a sequence of the Betti numbers of the frames. Find or create a simple gray scale image and verify the correctness of the Betti numbers.

Exercise. Design a character recognition system. Answer

See also Homology in 2D.