In that, the digital image segmentation algorithm is pre-processing for many systems of a machine vision, object detection, etc. and there is no universal of one for any type of digital image, it is necessary to obtain a new approach to it. Topological data analysis is issued not so long ago but its instruments have a universal character. We obtained the algorithm which is based on the persistent homologies as the effective mode of topological data analysis and its implementation in C# (.NET 4.5). A pixel of a digital image is considered as a point of fifth-dimensional space (two coordinates of the location and three color components). Then, we construct the filtration of some complexes and calculate topological invariant at obtained filtration. For this algorithm, there is one parameter which is appeared at a step of filtration. Its testing on different types of images (data of aerial photography, compositions, etc.) was held and the results were compared with the K-means algorithm.
The image segmentation is a useful part of a machine vision [
A finite set of segments is the result of image segmentation. Each of the segments covers the entire image or a set of contours extracted from the image. Each of the pixels in a region is similar according to some characteristic or computed property, such as color, intensity, or texture. Neighboring regions are significantly different concerning to the same characteristic or characteristics.
The most of image segmentation methods are based on statistical methods [
The author proposes the image segmentation algorithm based on the persistent
homologies as the effective mode of topological data analysis [
In this paper, the segmentation means to unite the pixels according to their characteristic to have a similar intensity.
In contradistinction to the algorithm described above, our algorithm considers an image as a set of points in 5 and calculates persistent homology for all points. Also, it does not need any type of image preprocessing such as, for example, edge detection, and works with the color image while many segmentation algorithms deal with the grey-scaled images. 2
Let formulate the terms of computational topology, see [
Let K be simplicial complex. A p-chain is a formal sum of p-simplices in K and its standard notation is c=∑ , where is p-simplex in K and is either 1 or 0. The p-chains together with the additional operation form the group of p-chains denoted as . The neutral element is 0=∑ 0 and the inverse of c is -c since c+(-c)=0. For p<0 and p>dim K this group is trivial. To relate these groups, we define the boundary of a p-simplex as a sum of its (p-1)-dimensional faces.
For p-chain c=∑ the boundary is the sum of boundaries of its and : → −1 is a homomorphism. The p-cycle is a p-chain with an empty boundary. The group of p-cycles is the kernel of the p-th boundary homomorphism, p=ker . The p-boundary is a p-chain that is the boundary of a (p+1)-chain. The group of pboundaries is the image of the (p+1)-st boundary homomorphism, p=Im +1. Since the boundaries form subgroups of the cycle groups, we can take quotients, which are the homology groups = p / p.
The Vietoris-Rips complex is the clique complex of -neighborhood graph. A filtration of a space X is a nested sequence of subspaces: ∅ ⊆ 1 ⊆…⊆ = .
The set { } =1 of Vietoris-Rips complexes is the filtration for any finite set { 1, 2, …, }, where < , i<j.
The p-th persistent homology pi,j is Im Let pi= ( ), where be p-th homology, and , for 0≤ i<j ≤ k+1.
, : pi → p, i<j, be a map.
On other words, pi,j= pi/( pj ∩ pi), where pi is p-cycles of and pj is
pboundaries of . There is a method of their calculation based on the matrices
algebra, the persistence barcode and the persistence diagrams (see [
It's known that 0=rank 0i,j is the number of connected components of the space. For the digital image segmentation, it is the same as the number of segments. 3
Let consider a digital image D as a set of points M in 5. Denote by L the length of D and W the width of D. Every pixel P has two parameters of the plane location (x and y) and three components of color (for example, RGB). Let P (x, y, r, g, b) be a pixel of D. The digital image segmentation algorithm based on a persistent homology is the following: f(y)= ⁄max{ , }
, f(r)= ⁄255, f( )= ⁄255 and f(b)= ⁄255; Step 1. Construct a map f: M ⊂ 5 →I, where I is a unit cube in 5. For example, for every P it can be realized by the following formulas f(x)= ⁄max{ , } Step 2. Fix a finite set { 1, 2, …, } such that < for i<j. Construct the filtration of Vietoris-Rips complexes { } =1 on the even grid of the set f(M) ⊂I; Step 3. Construct the matrices of persistent homology 0i,j of { } =1 ; Step 4. For every , i=1,…,k, the rank of Smith normal form of the persistent homology matrix is calculated. These numbers are the quantities of segmentation clusters; Step 5. For obtaining the quantity N of segments we use the following formula: N= ∑ =1 ∑ =1 where is the rank of Smith normal form of the persistent homology matrix that corresponds to (number from step 2).
We have to remark that (1) is the discrete analog of the center of mass. If there is a possibility to change from 1 to 2 in such a way that is approximate to a continuous one, we have to replace (1) the sign of the sum with the integral sign.
In Step 2 there are several possibilities to construct simplicial complexes, for
example, Cech complexes [
The image segmentation algorithm based on the persistent homologies is implemented in C# (.NET 4.5). This software consists of five parts: the graphical user interface, the auxiliary functions module, the Vietoris-Rips complexes constructions module, the homology calculation module, and the segments visualization module. Its action guide is given below: Step 1. Downloading of digital image with such extensions: .bmp, .gif,.jpeg, .png, .tiff; Step 2. Transformation of the image into a set of points at space 5 using Step 1 of the algorithm and even grid; Step 3. Construction of Vietoris-Rips complexes and calculation of 0i,j using Step 2−5 of the algorithm; Step 4. Visualization of the segmentation in an original digital image with the possibility to show it for either a range 1 <…< 2 with some accuracy or a fix .
It was tested on different types of images. In Fig. 1 there is a colorful digital image and the result of segmentation where each segment is colored by a certain color. In Fig. 2, there is a real digital image on the left which is data of aerial photography. To segment such photo is a complicated task for a person. On the right of Fig. 2 the result of segmentation is presented which corresponds =0.101. Remind that is a parameter from step 2 of the algorithm.
In Fig. 3, there is the segmentation of data of aerial photography which corresponds =0.127. This result of segmentation is interesting by the fact that such objects as forest and ground (green grass) belong to the same segment but buildings belong to others. It can help to solve the problem of automation of recognition of the target objects.
During testing, we noticed an effect of the appearance of the small omissible segments. In Fig. 4 such effect is present in the lower image which is the result of segmentation. Such small omissible segments are the highlights on the coins. It is conditioned by non-availability of any type of image preprocessing. We can prevent this effect by choosing the specific value of or making some type of postprocessing, for example, combining areas that are smaller than a fixed number with one of the neighbors.
As a generalization, the persistent homology segmentation algorithm (PHSA) has one parameter such that the more it is, the smaller number of segments is. It is obvious, if =0, then every pixel of a digital image is a separate segment. Whereas, if = √ 2 + 2⁄max{ , } , where L be the length and W be the width of an image, then a number of segments equals to 1. It means that all pixels belong to the same one.
PHSA is not sensitive to emissions, as there is no one center of a segment. A result of its segmentation is close to human perception. 5
After testing on real images it becomes obvious that the digital image segmentation algorithm based on the persistent homologies is more effective than the K-means algorithm and not sensitive even to high noise levels. Its work time is not sufficient for real-time processing.
In further research, the digital image segmentation algorithm based on the persistent homologies will be adapted for video files with real-time processing and its parameter value dependence on some characteristics of a digital image (textures, brightness, etc.) will be obtained.