Algorithm for grayscale images
- 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(N2).
- The memory is O(N).
- The time of filtering is O(N).
See also Processing time.
See also Image Simplification.
The time complexity of the algorithm is O(n2), 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.