##### Tools

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

# Pseudocode 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
ENDFOR
Add all nodes with no descendants to the list of principal cycles
FOR all white pixels P in I
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


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?