This page is a part of the Computer Vision Wiki. The wiki is devoted to computer vision, especially low level computer vision, digital image analysis, and applications. The exposition is geared towards software developers, especially beginners. The wiki contains discussions, mathematics, algorithms, code snippets, source code, and compiled software. Everybody is welcome to contribute with this in mind - all links are no-follow.

From Computer Vision Wiki

In this article the algorithm for analysis for gray scale images is explained in detail and illustrated with C++ source code.

The data structure of the algorithm

The input image of the algorithm is a gray scale 2D image, i.e., an array of of integers from 0 to 255 with dimensions dim1 and dim2.

int image[ dim1*dim2 ];

The algorithm first creates binary frames for each value of the threshold and then partitions the image by providing boundaries of the objects. Geometrically, these boundaries are circular sequences of directed edges of pixels in the image. In other words, these are 0- and 1-cycles. The first task is to count them.

long betti[2] = {0,0}; // Betti numbers = number of current cycles of each dimension

For each value of the parameter, the gray level, the image is binary. Two Boolean arrays of the same size are used: the previous frame (PrevFrame) and the current frame (CurrFrame).

bool *CurrFrame = new bool [ dim1*dim2 ];
bool *PrevFrame = new bool [ dim1*dim2 ];

The binary frame is created by thresholding the image.

for(int k=0;k < dim1;k++) // start the (k,l) pixel
for(int l=0;l < dim2;l++)
           if( image[l+dim2*k] < frame )
                 CurrFrame[l+dim2*k] = 0;
           else
                 CurrFrame[l+dim2*k] = 1;

As pixels are added, this array is incrementally changed - pixels are added - and analyzed by the algorithm. Recall that at every step the cycles that have no descendants are called current cycles. Similarly, the edges that represent current cycles are called current edges. Cycles in the image are represented by nodes in the graph. The structure of the graph is the same as before - an acyclic binary directed graph. Except this time this graph spans through the frames. For each frame, the regions and holes are represented as nodes of this graph. Each node representing a region or hole is connected to the nodes representing regions and holes that existed previously (its parents) or appear later (its children) by directed edges, or arrows, of the graph. The arrows (one or two from each node) indicate merging and splitting of the regions as we add vertices, edges, and pixels, Adding Pixels. There are no circular sequences of arrows. Each node of the graph contains a pair of links (pointers) to next nodes. If the cycle is merged with another, one link used, if it splits, two. This information is used even after the cycle ceases to be current, i.e., after a merge or a split.

int frame = 0; // current frame number, 0-255

In the end of processing a frame, CurrFrame, it is copied to PrevFrame.

for(int k=0; k < dim1; k++) // start the (k,l) pixel
for(int l=0; l < dim2; l++)
 PrevFrame[l+dim2*k] = CurrFrame[l+dim2*k];

The run through pixels of the image

At every step of the run through the image, the value of the pixel in the image is considered. If the color is white, skip to the next step. If the color is black, execute AddCell. Every time a cell is added, the topology of the image changes, the graph, the list of current cycles, and the Betti numbers are updated.

for( k=0; k < dim1; k++ )// start the (k,l) pixel
for( l=0; l < dim2; l++ )
{
if( CurrFrame[ l+dim2*k ] == 0 )// if the new pixel is black.. 
   AddCell( k, l ); 
}

Cycles in the image are represented by nodes in a directed graph as before. In this graph, the cycles are related to each other to record the changes in the topology of the image in terms of merging and splitting of components and holes as pixels are added. In particular, the 0- and 1-Betti numbers are updated at every step. In addition to the structure defined in Chapter 2, we need to record the frame when the cycle was created.

struct Cycle { 
           ...
       int Birth; // the frame of birth
       };     

Each node of the graph contains only a pair of links (pointers) to next nodes. If the cycle is merged with another, one link used, if it splits, two. The node may contain additional information: the dimension of the node, the frame of birth (gray level), a pointer to the edge that created the cycle, the area, the perimeter, etc.

CreateCycle is almost the same as before. The only new command is

   Cycle0->Birth = frame;      

At every step of the run through the image, a pixel in PrevFrame is compared to the corresponding one in CurrFrame. If the colors are the same, skip to the next step. If the color changes from white to black, execute AddCell. Observe that in the case of gray scale images, the color can never change from black to white (RemoveCell will used in the future).

// processing the frame
for( int k=0; k < dim1; k++ ) // start the (k,l) pixel
for( int l=0; l < dim2; l++ )
{
// if the new pixel is black and the color of its position is white
if( CurrFrame[l+dim2*k] == 0 && PrevFrame[l+dim2*k] == 1 )      
   AddCell( k, l ); 
}

     The AddCell command is exactly the same. 

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

Continue to Homology in 2D.