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

Pseudocode for gray scale images

From Mathematics Is A Science

Jump to: navigation, search

Start at Gray scale images.

The algorithm from Pseudocode for binary images is executed to partition each frame of the sequence into black and white regions. These regions are bounded by 0- and 1-cycles respectively and this information is recorded in a graph, as before. The crucial difference is that we have now a sequence of binary images. Therefore the following is needed:

The cycles in every frame are related to the cycles in the previous and next frames to form the full topology graph of the image.

Specifically, suppose the first frame is analyzed with the binary algorithm and the graph is constructed. Now, the nodes in the graph with no ancestors represent the cycles in the this frame. They are called principal cycles. Those are the truly important nodes in the graph because they represent features of the frame that are independent from its specific order in the representation of the image as a collection of pixels. Next, we move to the second frame, how? We simply continue to add pixels, see Adding Pixels. As a result the graph continues to grow. In the end of the second frame we again identify nodes without ancestors and make them framed. And so on.

The algorithm of image analysis is the process of adding pixels one by one while keeping track of changes in the topology.

The analysis of the topology of a gray scale image consists of two stages:

  1. The creation of the augmented graph, and
  2. The filtering of the principal cycles based on user's settings and creation of the list of active cycles.

The operation of adding a pixel and all functions it calls are exactly the same as in the case of a binary image. The only difference is a list of all principal cycles is maintained.

ImageAnalysis with gray scale image I  

FOR all thresholds T = 0, …, 255
  FOR all pixels P in I
	IF the value of P <= T THEN 
 		 CALL AddPixel with P
	ENDIF
  ENDFOR
Add all cycles with no descendants to the list of principal cycles
ENDFOR

FOR all principal cycles C
  IF C is a 0-cycle, Evaluate(C) == 1, and C does not have an ancestor D with Evaluate(D) == 1 THEN
     Add C to the list of active cycles
  ENDIF
  IF C is a 1-cycle, Evaluate(C) == 1, and C does not have a descendant D with Evaluate(D) == 1 THEN
     Add C to the list of active cycles
  ENDIF
ENDFOR

Cycles can be evaluated based on their measurements and other characteristics: area, integrated optical density, contrast, etc. The most typical is the area, as below.

Evaluate with cycle C 

IF the area enclosed by C < MinArea THEN
  RETURN 0
ENDIF
RETURN 1

Keep in mind that AddCell automatically computes all numerical characteristics - Area, Perimeter, etc - of all cycles it processes. Therefore each principal node comes out with all of its data already available. What is missing from this short piece of code is how the collected data about the cycles and their positions in the graph is later used to evaluate them.

For more details and some C++ source code see Algorithm for Grayscale Images.