This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.

Cycles in images

From Intelligent Perception

Jump to: navigation, search

Our interest is 2D images only. As a result, we will have to deal with only objects and their holes. Recall,

Binary images are analyzed as if they have black objects on white background.

Both objects (components) and holes are captured by cycles. By a cycle, we will understand a circular sequence of edges. There are $0$- and $1$-cycles:

  • A $0$-cycle follows the outer boundary of an object (like a rubber band),
  • A $1$-cycle follows the outer boundary of a hole.

The image:

The image.

Its topological features are represented as cycles. Here $A$ and $B$ are $0$-cycles, $C$ and $C’$ are $1$-cycles:

Its topological features are represented as cycles. Here A and B are 0-cycles, C and C’ are 1-cycles.

This results in a natural and unambiguous representation of the regions by the curves that enclose them.

  • A $0$-cycle is traversed clockwise.
  • A $1$-cycle is traversed counterclockwise.

Observe that in the either case black is on the right.

Thanks to cell decomposition, this approach is easy to use for image analysis.

Note: The name “$1$-cycle” is justified by the fact that this is a sequence of edges or $1$-cells. But so is a $0$-cycle. How come? The representation is only a matter of convenience. A $0$-cycle can just as easily be represented as a sequence of 0-cells (in fact a single vertex will suffice).

Of course, $1$-cycles of the picture are $0$-cycles of its negative and vice versa, except for ones that touch the border of the image.

Given an image, any cycle can be traversed by taking left turns from the initial edge in such a way that black pixels are always on the right - until this edge is reached again. (This does not work in 3D, at all. Dealing with tunnels would require homology theory anyway.)

Cycles partition the image.jpg

Exercise. Follow the above idea to come up with an economical way of capturing cycles.

The result of this topological analysis is a partition of the binary image. The partition is a collection of non-overlapping regions, connected sets of black pixels and connected sets of white pixels, that covers the whole image. The partition is achieved by finding boundaries of these regions as $0$- and $1$-cycles. These cycles are closed curves made of vertical and horizontal edges of pixels. On the right is an example of how cycles partition an image.

Note: To connect this treatment of cycles to that of homology theory observe that the contour that represents a $0$-cycle in an image $M$ is, in fact, a $1$-cycle of the closure of the complement of $M$. This is an instance of the Alexander duality.

Pixcavator's image analysis is based on the cycles representation. Take a look at our numerous examples of image analysis. To experiment with the concepts, download the free Pixcavator Student Edition.