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

Pseudocode for binary images

From Mathematics Is A Science

Jump to: navigation, search

Start with Binary Images and Algorithm for Binary Images.

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

A crucial part of the algorithm is maintaining the correspondence between edges and cycles. Each directed edge is given by the coordinates of its initial point and the direction: left, right, up, down. For convenience, vertices are recorded as edges with 0 direction. Then this correspondence takes the form of a table, T, so that for every directed edge E, T(E) is the cycle that passes through E. This table is updated at every step of the algorithm.

 ImageAnalysis with binary image I 
 
 FOR all black pixels P in I
   CALL AddPixel with P
 ENDFOR
 Add all nodes with no descendants to the list of principal cycles
 
 FOR all white pixels P in I
   CALL AddPixel with P
 ENDFOR
 Add the carrier to the list of principal cycles
 
 FOR all principal cycles C
  IF Evaluate(C) == 1 and 
     Add C to the list of active cycles
  ENDIF
 ENDFOR

Cycles can be evaluated based on their measurements: area, perimeter, roundness, etc. The most typical is the area, as below. Here MinArea is the lowest area set by the user.

 Evaluate with cycle C 
 
 IF the area enclosed by C < MinArea THEN
  RETURN 0
 ENDIF
 RETURN 1
Case (a) - the new edge connects two different 0-cycles.
Case (b) - the new edge connects a 0-cycle to itself.
Case (c) - the new edge connects a 1-cycle to itself.
Case (d) - the new edge connects a 1-cycle to a 0-cycle (inside).

Next is the operation of adding a pixel. It includes adding its vertices, its edges, and then the face of the pixel. Adding an edge means assigning cycles to both of the directed edges: forward E and backward -E. After all the edges have been added, there is always a 1-cycle inside the pixel. It is “removed” as the face closes the hole.

 AddPixel with pixel P 

 CALL AddVertex with upper right vertex of P
 CALL AddVertex with upper left vertex of P
 CALL AddVertex with lower right vertex of P
 CALL AddVertex with lower left vertex of P
 
 CALL AddEdge with lower edge of P
 CALL AddEdge with right edge of P
 CALL AddEdge with upper edge of P
 CALL AddEdge with left edge of P
 
 E = lower edge of P directed counterclockwise
 CALL RemoveCycle with 1-cycle A = T(E) 
 

Adding a vertex is trivial. It creates one new 0-cycle represented by a node that isn’t connected to anything yet. But first you verify that the vertex isn’t already present.

 AddVertex with vertex V 
 
 IF V is present THEN
    RETURN
 ENDIF
 Mark V as present
 Call CreateCycle with V RETURNING 0-cycle A

Adding an edge is the most complex step. There are four cases illustrated in Figures 12-15. Which case occurs is determined by examining the correspondence table T.

 AddEdge with edge E 
 
 IF T(E) != NULL or T(-E) != NULL THEN
   RETURN
 ENDIF
 
 CALL NextEdge with E RETURNING edge E1
 A = T(E1)
 CALL NextEdge with –E RETURNING edge E2
 B = T(E2)
 
 IF A == B THEN
   CALL SplitCycle with E1, E2, and A
 ELSE
   CALL MergeCycles with E1 and A, B
 ENDIF
 

A 0-cycle can merge with either 0- or 1-cycle: case (a) or (b).

 MergeCycles with cycles A, B and edge E 
   
 CALL CreateCycle with E RETURNING cycle C
 
 CALL MarkEdges with E and C

Add arrows from A, B to C to the graph

Either a 0- or 1-cycle can split: case (c) or (d).

 SplitCycle with edges E1, E2 and cycle A 
 
 CALL CreateCycle with E1 RETURNING cycle C
 CALL CreateCycle with E2 RETURNING cycle D
 
 CALL MarkEdges with E1 and C
 CALL MarkEdges with E2 and D

Add arrows from A to C, D to the graph

Creating a cycle means adding a new node to the graph.

 CreateCycle with edge E 
 
 Create node A in the graph
 T(E) = A
 RETURN A
 	

Removing a cycle means assigning NULL to all of its edges.

 RemoveCycle with cycle A 
 
 FOR all edges E in I
   IF T(E) == A THEN 
     T(E) = NULL
   ENDIF
 ENDFOR

Given an edge of a cycle, one can find the next edge of the cycle.

 NextEdge with edge E 
 Start points of edges E1, E2, E3, E4 = end point of E
 Direction of E1 = direction of E + 90 degrees
 Direction of E2 = direction of E
 Direction of E3 = direction of E - 90 degrees
 Direction of E4 = - direction of E
 
 FOR edge G = E1, E2, E3, E4 
  IF T(G) != NULL 
     RETURN G
  ENDIF
 ENDFOR

Next one goes around a given cycle and assigns its value to the edges.

 MarkEdges with edge E and cycle A 
 
 CALL NextEdge with edge E RETURNING edge G
 WHILE G != E
   T(G) = A
  CALL NextEdge with edge G RETURNING edge G
 ENDWHILE
 
 IF the full turn is clockwise THEN
   A is a 0-cycle
 ELSE
   A is a 1-cycle
 ENDIF

More details are provided in Binary images - implementation illustrated with C++ source code.

Exercise. Provide pseudocode for the (a) triangular and (b) hexagonal grid. (c) Suggest another grid. (d) Is it possible to have a similar algorithm if the cells are irregular?