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
```
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?