This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.
Binary images
From Intelligent Perception
Contents
1 What we are trying to find in the image
We approach computer vision from the following direction.
The task is very simple. Consider the image on the right. We would like the computer to see what we see - a bunch of black "objects" on white background. We also would like these objects measured and their locations found. And we want these objects captured – pixel-wise -- so that we can deal with them as separate entities.
This problem is commonly known as "component labeling" and has many different solutions. The approach we suggest below and the algorithm we develop are different from those. However, keep in mind that the output is always the same!
There also "holes" in these objects. In fact, in the second image we have white "objects" on black background. This suggests that we should capture both.
The approach is based on cell decomposition of images, as is common in algebraic topology. This allows us to deal with objects and holes simultaneously and later to proceed to 3D with relative ease.
The algorithm is incremental, as we add pixels one by one. This allows us to proceed later to gray scale and color images with relative ease.
What about those dots on the right? They surely don't count? Maybe not. It's not for us to decide. We capture them, we measure them, we find their locations. No matter how small! After that, if the user considers them unimportant, he can ignore them. This can be as simple as moving a slider.
That's the principle we will follow here.
What if the user knows a priori that everything below a certain threshold is unimportant and doesn't want to waste time analyzing it? The answer is, shrink the image!
At this point you may want to preview the output of this analysis by running our software, Pixcavator. To see the code consider this simple demo program [1] (a few binary images are attached). Also take a look at our image analysis examples. To experiment with the concepts, download the free Pixcavator Student Edition.
For more detail see Objects in binary images.
2 The cell decomposition of the image
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. It seems natural to represent the object simply as a list of pairs of numbers and this is the way it is commonly done.
However, we will think of a pixel as a square, or a tile. This representation allows a convenient way to describe the boundary of a pixel as a combination of the four edges. Since an edge is shared by two adjacent pixels, keeping a list of these edges is a way to record how pixels are attached to each other.
Now, if the image is made of pixels, they are attached to each other along the edges they share. This it is easily applicable to all dimensions:
- a vertex is a $0$-cell,
- two adjacent edges are $1$-cells and they share a vertex, a $0$-cell,
- two adjacent pixels are $2$-cells and they share an edge, a $1$-cell,
- two adjacent voxels are $3$-cells and they share a face, a $2$-cell,
- etc.
The pattern becomes clear.
For more details see Cell decomposition of images.
3 Using cycles to partition the image
In this article our interest is 2D images only. As a result, we will have to deal with only objects and their holes. Now, we can think of white objects as holes in dark objects or vice versa. We have to choose one of these two options and we choose the former.
Binary images are analyzed as if they have black objects on white background.
Both objects and holes are captured by cycles. Until later, by cycles we will understand circular sequences of edges. There are $0$- and $1$-cycles:
- $0$-cycles represent objects or connected components of the image,
- $1$-cycles represent holes.
This results in a natural and unambiguous representation of the regions by the curves that enclose them. A $0$-cycle is traversed clockwise (on the outside of the object like a rubber band) and a $1$-cycle is traversed counterclockwise. Observe that in the either case black is on the left.
Of course, $1$-cycles of the picture are $0$-cycles of its negative (the complement) and vice versa.
Both types are captured by recording the coordinates of one of its edges. 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 left - until this edge is reached again.
The result of this topological analysis is a partition of the binary image. A 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.
4 The algorithm
The algorithm that we suggest here is incremental. The cycles are constructed through an incremental process as pixels, one by one, are added to the image. Since every pixel also contains edges and vertices, the process of adding a pixel (cell) starts with adding its vertices and then its edges, unless those are already present as parts of other pixels. These vertices, edges, and pixels are marked as "current" (see the next section).
As the new pixels are being added, components merge, holes split, etc. Thus, the topology of the image changes. This process is captured by cycles as they appear and disappear, merge and split. The information about these changes is recorded in a graph. Each node in the graph represents a cycle. The arrows that connect the nodes represent merging and splitting of the cycles.
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. Let’s consider a simple example.
During processing each cycle is assigned one of its edges. As a result, cycles as sequences of edges can be reconstructed. Starting with that edge one can simply proceed step by step in such a way that black is always on the left, image on the right.
During processing, numerical characteristics of the objects are computed. For example, as the objects are represented as cycles, the perimeter can be easily computed by traversing the cycle. It can also be computed indirectly during merging and splitting. The areas and centroids are computed either directly by means of Green's Theorem while traversing the cycle or indirectly during merging and splitting. Another characteristics is roundness computed as $\frac{4 \pi \cdot {\rm area}}{{\rm perimeter}^2}$ (in Pixcavator, it's also multiplied by $100$).
5 Example: adding a single pixel to a blank image
How the graph is created is illustrated here. It takes $9$ steps corresponding to the $9$ items added to the image. The arrows correspond to merging and splitting of cycles. The arrows are accompanied by numbers indicating which items is being added. For convenience the procedure is broken into $4$ stages. There are four pictures and a graph with $4$ “layers” corresponding to these stages.
The graph is below with the stages developing from left to right. Under the graph you can see how these stages correspond to the states of the image as parts of the pixel are being added.
At the first stage we have $4$ nodes, corresponding to the $0$-cycles. Then they merge into one. This $0$-cycle splits into two cycles, a $0$-cycle and a $1$-cycle. Finally, this $1$-cycles disappears. This is called the augmented topology graph.
For more details on this example, see Adding Pixels. For another example of how this works, see Topology graph.
Keep in mind that if you choose a different order of operations, the graph will be different. The only rule to be followed is that no edge is added until both of its end vertices are added and no pixel is added until four of its edges are added.
Exercise This order is possible: vertex, vertex, edge, vertex, edge, vertex, edge, edge, pixel. Plot the graph. Answer
Exercise Find the topology graph of the first image of the previous section?
More details are provided in Algorithm for Binary Images.
Continue to Grayscale Images or Homology in 2D.
