Connectivity

A binary image is a combination of black and white pixels. Normally, it is assumed that objects are black and the background is white. How do you represent these objects? Well, each pixel is given by its location in the image, so it is just a pair of numbers (as in the Euclidean space). It seems natural to represent the object simply as a list of pairs of numbers and this is the way it is commonly done.

Pixels as dots on the grid.

4-adjacency.

8-adjacency.

Beyond that however the question is how to think of pixels. The common view is that pixels are dots; let's call them pixel-dots. They are located on a grid. Then, to study the image one has to understand how these pixel-dots form objects. This requires the notion of adjacency among pixel-dots. If two pixel-dots are "adjacent" they are connected by an edge, as shown in these pictures. The result is a graph representation of the binary image.

This seems simple enough. However, it turns out that the decision which nearby pixel-dots are adjacent isn't obvious. Should they be connected only along the grid? Or should the adjacency works diagonally as well? (These two approaches are called the 4-connectivity and the 8-connectivity respectively.)

Both are equally legitimate answers.

One may hope that choosing one of the two and sticking with it will provide a solid foundation for image analysis. The trouble starts when one considers the complement of an object represented by pixel-dots. One would expect that the complement should also be an object represented by pixel-dots based on the same adjacency relation. Consider this picture however.

If adjacency goes diagonally then A and D are connected to each other. Then B and C are not connected, so adjacency does not go diagonally. Wait a minute...

We have a problem; in fact, the Jordan theorem fails in this setting.

This paradox can be resolved by having different way to define adjacency for the set and its complement. Even if you accept this awkward "solution", it's still a can of worms... One has to create digital geometry - from scratch - to iron this out. And things will remain messy. For example, the number of different, and equally justifiable, "connectivities" in 3D is 16. Just imagine what happens in dimension n!

Instead of being worried about this, some embrace this variety and define more general "connectivities" via a 3x3 table [1]. The topic is related to lengths of curves as the 8-connectivity produces curves that go only horizontally or vertically while the 4-connectivity allows diagonal edges as well.

Your choice of connectivity affects the boundary of the object and, therefore, its perimeter. This seems important. But we are interested in the perimeter of a “real” object, which should be independent (as much as possible) from the digital representation. This perimeter is the length of a “real” curve – the boundary of the object. In Lengths of curves it is shown that the relative error of the computation of length does not diminish with the growth of the image resolution. The accuracy is improved only by choosing more and more complex ways to compute the length (roughly, increasing the degree of the approximation of the curve). The choice of connectivity is determined by a 3x3 table. With finitely many choices the error can’t be reduced to arbitrary low. You may conceivably improve the accuracy if you can choose larger and larger table...

We approach this issue differently in Cell decomposition of images.

To experiment with the concepts, download the free Pixcavator Student Edition.