Next: Mathematical Preliminaries
Up: Lectures
Previous: Image Examples and Basics

More Image Basics

Last updated on September 11, 1995 at 6:30 AM

More Image Examples

Continue remainder of information from the previous lecture (if any).

Playing on the Pixel Grid: Connectivity

Many of the simplest computer vision algorithms involve what I call "playing on the pixel grid". These are algorithms that essentially involve operations between neighboring pixels on a rectangular lattice. While these algorithms are usually simple, they are often very useful and can sometimes become more complex.

Neighborhoods and Connectivity

One simple relationship between pixels is connectivity---which pixels are "next to" which others?

Suppose that we consider as neighbors only the four pixels that share an edge (not a corner) with the pixel in question: (x+1,y), (x-1,y), (x,y+1), and (x,y-1). These are called "4-connected" neighbors for obvious reasons. Now consider the following:

Figure 3.1: Paradox of 4-connected neighbors.

The black pixels on the diagonal in Fig. 3.1 are not 4-connected. However, they serve as an effective insulator between the two sets of white pixels, which are also not 4-connected across the black pixels. This creates undesirable topological anomalies.

An alternative is to consider a pixel as connected not just pixels on the same row or column, but also the diagonal pixels. The four 4-connected pixels plus the diagonal pixels are called "8-connected" neighbors, again for obvious reasons.

But again, a topological anomaly occurs:

Figure 3.2: Paradox of 8-connected neighbors.

The black pixels on the diagonal are connected, but then again so are the white background pixels. Some pixels are connected across the links between other connected pixels!

The usual solution is to use 4-connectivity for the foreground with 8-connectivity for the background or to use 8-connectivity for the foreground with 4-connectivity for the background, as illustrated in Fig 3.3.

Figure 3.3: Solution to paradoxes of 4-connected and 8-connected neighbors: use different connectivity for the foreground and background.

Another form of connectivity is "mixed-connectivity", a form of 8-connectivity that considers diagonally-adjacent pixels to be connected if no shared 4-connected neighbor exists. (In other words, use 4-connectivity where possible and 8-connectivity where not.)

Properties of Connectivity

For simplicity, we will consider a pixel to be connected to itself (trivial connectivity). In this way, connectivity is reflexive.

It is pretty easy to see that connectivity is also symmetric: a pixel and its neighbor are mutually connected.

4-connectivity and 8-connectivity are also transitive: if pixel A is connected to pixel B, and pixel B is connected to pixel C, then there exists a connected path between pixels A and C. (Mixed-connectivity is not transitive--can you explain why?)

A relation (such as connectivity) is called an equivalence relation if it is reflexive, symmetric, and transitive.

Connected Component Labeling

If one finds all equivalence classes of connected pixels in a binary image, this is called connected component labeling. The result of connected component labeling is another image in which everything in one connected region is labeled "1" (for example), everything in another connected region is labeled "2", etc.

Can you think of ways to do connected component labeling?

Here is one algorithm:

Scan through the image pixel by pixel across each row in order:
- If the pixel has no connected neighbors with the same value that have already been labeled, create a new unique label and assign it to that pixel.
- If the pixel has exactly one label among its connected neighbor with the same value that has already been labeled, give it that label.
- If the pixel has two or more connected neighbors with the same value but different labels, choose one of the labels and remember that these labels are equivalent.
Resolve the equivalencies by making another pass through the image and labeling each pixel with a unique label for its equivalence class.

You will implement this algorithm as part of your first programming assignment.

Distance Measures

It is often useful to describe the distance between two pixels

and

One obvious measure is the Euclidean (as the crow flies) distance .

Another measure is the 4-connected distance (sometimes called city-block distance .

A third measure is the 8-connected distance (sometimes called chessboard distance .

For those familiar with vector norms, these correspond to the , , and norms.

Weighted Averages of Neighborhoods

There are many, many useful operations that can be performed by computing some weighted average of the pixels in a neighborhood. Your text gives a brief introduction to this--read it now and we'll come back to this in much more detail later in the course.

Next: Mathematical Preliminaries
Up: Lectures
Previous: Image Examples and Basics