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:

- All pixels in the image are ordered in such a way that all darker pixels come before lighter ones.
- Following this order, each pixel is processed:
- 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 graph is given a new node and arrows that connect the nodes in order to represent the merging and the splitting of the cycles:
- adding a new vertex creates a new component;
- adding a new edge may connect two components, or create, or split a hole;
- adding the face to the hole eliminates the hole.

- Filter the noise nodes
- 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
^{2}). - 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 ^{2})**, 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.