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.

# Frame Graphs

The algorithm from Binary Images#The pseudocode of the algorithm is executed to partition each frame of the sequence into black and white regions. These regions are bounded by 0- and 1-cycles respectively and this information is recorded in a graph, see Adding Pixels. The crucial difference is this:

The cycles in every frame are related to the cycles in the previous and next frames.

Thus, graphs of the frames are connected to each other to form a bigger graph. We call this graph the full graph. For each frame, the objects and holes in them are represented as nodes of this graph. In fact, these nodes are of a special kind - they have no ancestors within this frame. We will call these nodes and cycles framed and they appear in the frame graph.

Now, each framed node represents a region or hole in the frame. Through the graph, it is connected to framed nodes that represent regions and holes that existed previously (ancestors) or appear later (descendants). This is the most important part of the full graph. It consists of the connections of the cycles in the current frame to the ones in the next, skipping all the intermediate states of the graph as we add pixels one by one. We will call it the frame graph. Its links reflect merging of 0-cycles and splitting of 1-cycles as we move from frame to frame.

The frame graph can however be constructed based entirely on the image and its frames, without using the full graph as in the following example.

Below we have a gray scale image, its frames, followed by frames with cycles.

The original image: 3 dark objects, one with a hole.
Frame 1.
Frame 2.
Frame 3.
Frame 4.

Frame 1.
Frame 2.
Frame 3.
Frame 4.

Note: Keep in mind that the frame graph provides only a partial picture of the topology of the image. For example, from this graph is impossible to see that C is a hole in A, not B. This information is revealed by the full graph, down to vertices and edges, created while we are Adding Pixels.

Exercise. Draw the frame graph for this image.