Abstract
In this paper, we study qualitative topological analysis of spaces of natural images locally. We apply the techniques of computational topology to the space of 3 × 3, 4 × 4, 5 × 5, 6 × 6 and 7 × 7 high-contrast patches. We show that in each case there is a subspace of the space of all high-contrast patches that is topologically equivalent to the Klein bottle and we found that the size of the largest subspace having the Klein bottle's homology decreases with increasing of the size of patches. The data sets used in this paper are different from that discussed in the paper "on the local behavior of spaces of natural images", we conformed our findings by applying the same methods to the different sizes patches. c ⃝2016 All rights reserved.
Introduction
There have been many successful attempts in statistics of images in the recent years [7, 9, 10] . Lee, Pedersen, and Mumford [9] studied the distributions of 3 × 3 patches from optical and range images, they observed that high contrast 3 × 3 range patches are densely clustered around the binary patches and the majority of the high contrast optical patches concentrate near an annulus. In this paper we analyze the structure of high-contrast regions of natural images instead of looking at an image as a whole, we are interested in the topology of the space of n by n high-contrast patches with sufficiently small n. Carlsson, Ishkanov, de Silva, and Zomorodian [4] apply topological tools to the dataset of optical 3 × 3 patches, they find one high density subset is called the primary circle, and show that there is a large 2-dimensional subset having the topology of a Klein bottle that contains the primary circle. In [1] , Adams and Carlsson showed that 5 × 5 and 7 × 7 range patches have the primary circle behavior.
In this paper, we apply the techniques of the paper [4] to high-contrast regions of natural images, and study the topological structure of spaces of 3 × 3, 4 × 4, 5 × 5, 6 × 6 and 7 × 7 patches of natural images, these spaces have many similar properties but they are not identical. In particular, we show that there is a 2-dimensional subspace in each of the five spaces, whose homology is that of a Klein bottle. The data sets used here are collected from INRIA Holidays dataset [8] , which are different from that discussed in the paper [4] .
Persistent homology
For a given finite point set X sampled from an underlying space X ⊆ R m , together with a parameter ϵ, we construct from it a simplicial complex, called the Vietoris-Rips complex or Rips complex, denoted R ϵ . The complex will have X as its vertex set, and a collection {x 0 , x 1 , · · · , x k } will determine a k-simplex in R ϵ if and only if d(x i , x j ) ≤ ϵ for all 0 ≤ i, j ≤ k. Here d denotes the metric distance. We can compute a R ϵ complex at each scale ϵ. It is easy to see that R 0 is a 0-complex and R ∞ is an (| X | −1)-simplex. That is, the R ϵ complex may have a much higher dimension than the embedding space X. However, there is typically a proper range where R ϵ has homology groups isomorphic to those of X, and therefore has Betti numbers equal to those of X. Since we only have the finite sample and no a priori information about the underlying space X, it is impossible to make a estimate of a proper range of ϵ. To solve this problem, persistence was introduced by Edelsbrunner, Letscher, and Zomorodian [6] and refined by Carlsson and Zomorodian [11] . Edelsbrunner, Letscher, and Zomorodian have made the following observation. Whenever ϵ ≤ ϵ ′ , there exists a natural inclusion of simplicial complexes R ϵ → R ϵ ′ , and because of the functoriality property discussed above, one obtains a linear transformation
To study the homology of a space using a point cloud sampled from it, one should keep track of the entire system of vector spaces H k (R ϵ ), together with all the linear transformations described above. This system is called a persistence vector space, and it is shown in [11] that persistence vector spaces admit a classification similar to the classification result for finite dimensional vector spaces, which asserts that two vector spaces of the same dimension are isomorphic. For persistence vector spaces, it shows that attached to each persistence vector space, there is an invariant called a barcode which is just a finite collection of intervals, and that any two persistence vector spaces with the same barcodes are isomorphic. The intervals can be explained intuitively as the life-times of non-trivial cycles in a growing complex. The left endpoint of an interval signifies the birth of a new topological property, and the right endpoint signals its death. We know that the k th Betti number of a complex, β k = rankH k , roughly equal to the number of k-dimensional holes, and β k may be computed from the barcodes, it is the number of intervals in the dimension k plot that intersect the vertical line through ϵ. Thus an interval starting at time ϵ = ϵ 0 and ending at ϵ = ϵ 1 can be explained as a hole that emerges in the complex at ϵ = ϵ 0 and gets filled in at ϵ = ϵ 1 . Long intervals correspond to holes persisting through a large range of values of the persistence parameter ϵ while short intervals correspond to holes that get filled in quickly. Hence, long intervals in a barcode represent actual geometric structure of an underlying space, whereas short intervals are considered to be noise. Figure 1 gives an example of barcode for a figure "8".
In Figure 1 there are one long line in dimension 0, two in dimension 1 and no line in dimension 2 which reflects the fact that figure "8" has one connected component and two hole in dimensional one.
Since VR complexes may produce simplices in dimensions much higher than the dimension of the underlying space, in practice we use the witness complex defined in [5] .
For a point set P and a landmark subset L, let m k (p) be the distance from a point p ∈ P to its (k + 1)-th closest landmark point. The witness complex W (P, L, ϵ) is defined by follows:
(i) the vertex set is L;
(ii) for k > 0 and vertices
if all of its faces are, and if there is a witness point p ∈ P satisfying
A lazy witness complex is similar to a witness complex. However, there is an additional parameter v, typically chosen to be 0, 1, or 2, which helps decide how the lazy witness complexes are builded.
For a point cloud P , a landmark subset L, and a parameter v ∈ N, if v = 0, let m(p) = 0 for all p ∈ P . If v > 0, let m(p) be the distance p to the v-th closest landmark point. The lazy witness complex LW v (P, L, ϵ) is defined as follows:
(i) the vertex set is L;
(ii) for vertices a and b,
The lazy witness complex depends on a parameterv ∈ {0, 1, 2} which we choose to be v = 1: De Silva and Carlsson in [5] find v = 0 to be generally less effective, and v = 2 has the disadvantage of connecting every landmark point to at least one other at R = 0. For more information and examples about lazy witness complexes, please refer to the papers [2, 5] . 
The spaces of natural image patches
We collect data sets of high-contrast 3 × 3, 4 × 4, 5 × 5, 6 × 6 and 7 × 7 patches from selected natural images of INRIA Holidays dataset [8] . Each data set consists of 5 × 10 5 high-contrast log patches. INRIA Holidays dataset is available at http://lear.inrialpes.fr/ jegou/data.php. Figure 2 contains two samples.
Our main spaces X 3 , X 4 , X 5 , X 6 and X 7 are sets of 3 × 3, 4 × 4, 5 × 5, 6 × 6 and 7 × 7 patches of high contrast constructed by the following steps, each of the spaces contains 5 × 10 5 patches. The procedures used here are similar to [1, 4, 9] .
Step 1. Select 500 images from INRIA Holidays dataset.
Step 2. Compute the intensity at each pixel for every selected image by MATLAB function rgb2gray.
Step 3. Extract at random 5000 m × m patches from each image, where m = 3, 4, 5, 6, 7.
Step 4. Considering each patch as an m 2 -dimensional vector, we take the logarithm of each coordinate.
Step 5. Compute the D-norm: ∥ x ∥ D for each vector. This is a measure of the contrast of a patch. Two coordinates of x are neighbors, denoted i ∼ j, if the corresponding pixels in the m × m patch are adjacent. We compute the D-norm for a vector by the formula:
Step 6. We choose the patches that have a D-norm in the top T percent of the entire sample. We take T = 20% , as done in [1, 4, 9] .
Step 7. Subtract an average of all coordinates from each coordinate. This produces a new m 2 -vector.
Step 8. We map the spaces into a unit sphere by dividing each vector with its Euclidean norm, which is nonzero because the patches are high contrast. We do not change to the DCT basis for convenience.
Step 9. For computational convenience, we randomly choose 50,000 of the above patches in the top 20% percent, and these spaces are subspaces of X 3 , X 4 , X 5 , X 6 and X 7 , denoted byX 3 ,X 4 ,X 5 ,X 6 andX 7 respectively. 
Results forX m (k, p)
The 3 × 3 natural image patches have core subsets with topology of a circle were found by Carlsson, Ishkanov, de Silva, and Zomorodian in [4] . To detect the circle we need the concept of core subsets. We estimate the local density of the space at a point x by its the nearest neighbor. For x ∈ X and k > 0 , set ρ k (x) =| x−x k |, where x k is the k-th nearest neighbor of x. Different values of k give rise to different density estimations at x, larger k-values gives more global estimations, whereas small k-values produce local density estimates. For a fixed k, we sort the points of X by descending density, we select the points denoted by X(k, p) whose densities are in the top p percent. The core subset X(k, p) may provide important topological information, which may be lost for all the points of X.
Here we consider a core subsetX m (k, p) ofX m for m = 3, 4, 5, 6, 7. This subset represents appropriate core for proper values of two parameters k and p.
In [9] , A. Lee, K. Pedersen, and D. Mumford observe that the majority of the high contrast optical patches lie near a 2-dimensional annulus, called the primary circle. In [4] , Carlsson, Ishkanov, de Silva, and Zomorodian apply computational topological tools to identify the topologies of high density subsets of the optical patch space. they found that according to the reduction of density estimator k, firstly, the topology of the core sets changes from a circle to a 3-circle space and finally becomes that of the Klein bottle. In this paper, we use INRIA Holidays dataset, which are different from that discussed in the paper [4] , to show that various core sets of the dataset have the similar properties as above for different sizes of patches.
Considering the core subsetsX 3 (100, 20),X 4 (100, 20),X 5 (100, 20),X 6 (100, 20) andX 7 (100, 20), computing the barcodes, sample Betti barcode plots for these core subsets are given in Figures 3, 4 , 5, 6 and 7 respectively. There are a single long Betti 0 interval and a single long Betti 1 interval in the plots, which shows that they have the topology of a circle, visible in Figures 8, 9 , 10, 11 and 12. Selecting different landmark points (from 20 to 70), we do many times experiments onX 3 (100, 20),X 4 (100, 20),X 5 (100, 20), X 6 (100, 20) andX 7 (100, 20), and the results are very stable: in each trial, the circular profile β 0 = β 1 = 1 is found for nearly whole range of ϵ values, and other Betti plot intervals are very short. For different sizes of patches, there exist various core subsets ofX 3 ,X 4 ,X 5 ,X 6 andX 7 with proper values of parameters k and p, that have the topology of the primary circle. We ran about one thousand trials and found that the core subsets with following parameters have the topology of circle and the results to be robust. For the case m=3, k=60, 100, 300, 500, 700, p=20, 30, 40; For the case m=4, k=100, 300, 500, 700, p=20, 30, 40; For the case m=5, k=100, 300, 500, 700, p=10, 20, 30; For the case m=6, k=100, 300, 500, 700, p=10, 20, 30; For the case m=7, k=100, 300, 500, 700, p=10, 20, 30. If we take spaces of patches ofX 4 ,X 5 ,X 6 andX 7 and extract about 30 percent of the densest points using the density estimator k = 15 or 30, we obtain spaces whose first Betti number is equal to 5. The spaces are reasonably described as the three circle model (Figure 13 ), denoted by C 3 . Figure 14 For the case m = 3, we can not find core subsets ofX 3 that have the topology of the three circle model. The barcodes of the subsetX 3 (10, 50) sometimes show its first Betti number is five, but the result is not stable, we can not conclude thatX 3 (10, 50) has the topology of C 3 . In the section 6 we show thatX 3 has a subspace with the topology of C 3 by another way. 
Klein bottle and a space of degree 2 polynomials
We recall that the Klein bottle can be constructed by an identification space of a square in the plane as Figure 18 . The points on the boundary are identified by identifying opposite sides using the quotient topology. The three circle model can be embedded in the Klein bottle as shown in Figure 18 . The horizontal segments (black lines) actually form the primary circle (corresponding to S lin ) on the surface of the Klein bottle. The vertical segments form the secondary circles corresponding to S v and S h respectively.
To detect the topological features of subspaces of X 3 , X 4 , X 5 , X 6 and X 7 , we discuss another theoretical version of the Klein bottle. We regard the m × m patches as obtained by sampling a smooth real-valued function on the xy-plane at m × m grid points, and we study subspaces of the space of all such functions which have a rough correspondence with the subspaces of the space of patches we study. We consider the space F of all two variable polynomials of degree 2 [3] , i.e. functions
The set F is a 6-dimensional real vector space. We now consider the subspace P ⊆ F, consisting of all functions within F which have the form c(ax + by) 2 Each restriction of h m (m = 3, 4, 5, 6, 7) to the subspace P of F is one-to-one.
The proof is same as the proof in [4] . Since continuous one-to-one map on a compact space is a homeomorphism onto its image, it follows from the Proposition 5.1 that the image im(h m | P)(m = 3, 4, 5, 6, 7) is homeomorphic to the Klein bottle.
To embed the Klein bottle into a unit sphere, firstly, we uniformly select 200 points ({x 1 , · · · , x 200 }) from the unite circle, all possible tuples (x i , x j ) form a point set on the torus S 1 × S 1 . Next, we map each of the 40000 points into S 8 , S 15 , S 24 , S 35 and S 48 by maps h 3 • g, h 4 • g, h 5 • g, h 6 • g and h 7 • g respectively, the image of each map is denoted by K (3, As the first step for embedding of the space C 3 into the unit sphere S 8 , we randomly choose 500 points {(x 1 , y 1 ), · · · , (x 500 , y 500 )} from S 1 . Next, setting c = 0, d = 1; a = 1, b = 0; a = 0, b = 1 respectively, to each point of the 500 points, we evaluate its image under the map h 3 • g, denoting the collection of all images as C 3 (500).
6. Results for X 3 , X 4 , X 5 , X 6 and X 7
To find the subspace of X 3 whose homology is that of a C 3 , for each point x of C 3 (500) we calculate the Euclidean distance from x to every point of X 3 , then take the closest point to the point x. The subspace of X 3 is obtained by collecting all the closest point to any x ∈ C 3 (500), denoted by CC 3 (500). One sample PLEX Betti barcode plot for CC 3 (500) is shown in Figure 21 , which reveals that CC 3 (500) has first Betti number five. Doing many trials we find the results are robust.
Remark 6.1. If we replace X 3 byX 3 in the process of collecting points of CC 3 (500), then CC 3 (500), as a subspace ofX 3 , also has the topology of C 3 .
We know that S 8 , S 15 , S 24 , S 35 and S 48 has subspaces K (3, 200) , K (4, 200) , K (5, 200) , K (6, 200) and K (7, 200) separately, whose homology is that of a Klein bottle, by using them subspaces of X 3 , X 4 , X 5 , X 6 and X 7 can be found, and these subspaces have the topology of the Klein bottle shown by experimentation. We describe two ways to obtain the subspaces of X 3 , X 4 , X 5 , X 6 and X 7 as follows.
(i) For each point x of K(3, 200) we calculate the Euclidean distance from x to every point of X 3 , then take t closest points to the point x. The subspace of X 3 is obtained by collecting all t closest points to any x ∈ K (3, 200) , denoted by Knt (3, 200, t) . The subspaces Knt (4, 200, t) , Knt (5, 200, t) , Knt (6, 200, t) and Knt (7, 200 , t) of X 4 , X 5 , X 6 and X 7 are obtained respectively by a similar way.
(ii) For each point of X 3 , we calculate the Euclidean distance from this point to the closest point of K (3, 200) , the subspace Xp (3, 200 , r) of X 3 is obtained by taking the top r percent of the points for which this distance is smallest. The subspaces Xp (4, 200, r) , Xp (5, 200, r) , Xp (6, 200, r) and Xp (7, 200 , r) of X 4 , X 5 , X 6 and X 7 are obtained separately by a similar way.
For finding subspaces of X 3 , X 4 , X 5 , X 6 and X 7 with the topology of the Klein bottle, we use the subspaces Knt (3, 200, 1) , Knt (4, 200, 5) , Knt (5, 200, 4) , Knt (6, 200, 9) and Knt (7, 200, 11) respectively. (4, 200, 5) , Knt (5, 200, 4) , Knt (6, 200, 9) and Knt (7, 200, 11) separately. We ran more than 300 trials on Knt (3, 200, t) 2, 3, 5, 7, 9) and Knt (7, 200 , t) (for t = 2, · · · , 11) are also very stable. Remark 6.3. We note that there exist many same points in X 7 and Knt (7, 200, t) , thus, it is very difficult to find the largest subspace of X 7 by using Knt (7, 200, t) that still has the homology of the Klein bottle. Figure 27 shows the result for the space Xp (3, 200, 40) , which is the largest subspace of X 3 we found giving a true topological approximation to K (3, 200) , we ran many experiments on Xp (3, 200, 40) for different parameters and find that the result is robust. At value of r about 45 the space Xp (3, 200 , r) undergoes a topological change. Indeed, we ran 100 trials on Xp (3, 200, 45) for different parameters, where there are 56 trials whose PLEX barcodes giving the topology of the Klein bottle and some barcode intervals with the topology of the Klein bottle are very short, the other 44 trials show no the topology of the Klein bottle, Figure 28 , 29 shows two PLEX results. Similarly, we ran many trials on Xp (4, 200, 35) , Xp (5, 200, 30) , Xp (6, 200, 25) and Xp (7, 200, 20 ) respectively, we found that they are the largest subspaces of X 4 , X 5 , X 6 and X 7 giving a true topological approximation to K (4, 200) , K(5, 200), K (6, 200) and K (7, 200) separately, and at values of r about 40, 35, 30, 25 respectively the spaces Xp (4, 200, 40) , Xp (5, 200, 35) , Xp (6, 200, 30) and Xp (7, 200, 25 ) undergo a topological change. 
Conclusions
In this paper we use persistent homology to study qualitative topological analysis of spaces of different size natural image patches, the database used in this paper is different from that of paper [4] , and we get similar results to the paper [4] , which shows that the results obtained in this paper and [4] are intrinsic properties of natural image patches, they do not depend on databases. We show that the spaces of highcontrast 3 × 3, 4 × 4, 5 × 5, 6 × 6 and 7 × 7 patches have core subsets modeled as the primary circle. By the relation between the spaces of natural patches and the space of polynomials in two variables, it is shown that there exist subspaces of 3 × 3, 4 × 4, 5 × 5, 6 × 6 and 7 × 7 , whose homology is that of a Klein bottle. Applying the same methods to the different sizes patches, we found many similar properties for different sizes patches, but they also have their own characteristics. The size of the largest subspace of X 3 (X 4 , X 5 , X 6 and X 7 ) having the Klein bottle's homology depend on the size of patches. Our results show that it is essential to study different sizes patches in natural images. Figure 29 . PLEX results for Xp (3, 200, 45) 

{'paper_id': '444586', 'title': 'A topological analysis of high-contrast patches in natural images', 's2_url': 'https://api.semanticscholar.org/CorpusID:444586', 'source': 'S2ORC'}