Pseudocode for binary images
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?