This page is a part of the Computer Vision Wiki. The wiki is devoted to computer vision, especially low level computer vision, digital image analysis, and applications. The exposition is geared towards software developers, especially beginners. The wiki contains discussions, mathematics, algorithms, code snippets, source code, and compiled software. Everybody is welcome to contribute with this in mind - all links are no-follow.

From Computer Vision Wiki

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

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.

The image and its cycles

Exercise. Plot the graph for this image. Answer