This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.
Pseudocode for binary images
From Intelligent Perception
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
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?
