Adding pixels

Adding a stand-alone pixel requires 9 steps: adding 4 vertices, 4 edges, and the cell itself.

The image is built pixel by pixel. As it happens, the changes in topology are being tracked. The steps and the changing topology are recorded in a graph, the topology graph.

Based on the cell decomposition of images vertices and edges are also added. Generally, adding a new vertex creates a new component and a new node in the graph. Adding a new edge either connects two components or creates a hole in an existing component. Adding the cell itself eliminates a 1-cycle.

Now, let's consider the step of adding a single pixel to a black image. The pixel consists of 9 parts numbered as follows:

• vertices 1-4,
• edges 5-8,
• pixel itself 9.

They are added in this order illustrated below.

Stage 1

Stage 2

Stage 3

Stage 4

• Stage 1: 4 vertices (1-4) are added and exist as separate 0-cycles, A, B, C, D.
• Stage 2: as we add the first edge (5) two of these cycles (1 and 2) merge into one, E. As we add the next edge (6), the third 0-cycle (3) joins them, F. Adding the third edge (7) merges vertex (4) with the rest. At this point all we have is a single 0-cycle, G.
• Stage 3: adding the fourth edge (8) changes the 0-cycle, H, and creates a 1-cycle, I.
• Stage 4: adding the cell itself (9) eliminates cycle I.

Steps 1-4

Step 5

Step 6

Step 7

Step 8

Step 9

A graph representation of the 4 stages (9 steps) of adding a stand-alone pixel.

Since two vertices and one edge are already present, adding a second pixel requires only 6 steps: adding 2 vertices, 3 edges, and the cell itself.

A graph representation of the 6 steps of adding a second pixel.

In the image below, adding 1st pixel takes 9 steps, 2-6th 6 steps each, 7th 5 steps, and 8th 4 steps. More details on this example here [1].

If we omit the intermediate steps of adding edges and vertices, the graph looks much simpler. Here is an example: 8 pixels arranged in a square. The pixels, 1-8, are added one by one. After the first one there are no new cycles until pixel 7 which creates a new 1-cycle.

Exercise. Plot the graph for this image (Gridface). Answer