Abstract
3D image retrieval approach is a challenging problem in the research of content-based image retrieval. In this paper, a novel retrieval approach combined differential geometry and co-occurrence matrix is presented. Firstly, Gaussian curvature and mean curvature are utilized to represent the inherent characteristic of spatial surface, and then we use co-occurrence matrix to store the shape information of 3D images. Secondly, normalization process is applied to the co-occurrence matrix and the invariants independence of the translation, scaling, and rotation transforms are proved. In comparison with the recent methods, experiments indicate a lower computation complexity and a better retrieval rate to 3D images with slight different shape characteristic.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
3D image retrieval is an important problem in pattern recognition with many applications, such as 3D image search engine [1], automatic assembly for 3D components [2], and other applications. In the recent decades, there has been lots of research on 3D image retrieval; the approach can be divided into content-based image retrieval (CBIR) [3] and semantic-based image retrieval (SBIR) [4]. SBIR approach can fully use the advantages of visual cognition mechanism to improve the retrieval effect, but in some traditional system, such as architecture and mechanical component retrieval, CBIR approach can be more simple and effective.
In this paper, based on CBIR system, we are focused on the precision improvement to 3D similar image retrieval. In some cases, the images may be similar with slight different shape characteristic, so it is a challenging problem to search the correct image from the database with similar shape.
In recent decades, there has been lots of research on 3D image retrieval. In this problem, a key question is the shape characteristic representation. We can use different approaches which include Fourier descriptor representations [5], moment invariants representations [6], shape distributions [7], curvature-based representations [8], and neural network approaches [9]. In these approaches, global approaches can supply a more precise representation for surface, and they are robust to noise and have a lower computation complexity, but they cannot achieve a perfect classification rate in recognition to surfaces with slight different shape characteristics. Figure 1 shows some images that traditional global approaches cannot distinguish.
To a spatial surface, shape detail can be represented by inherent characteristic. According to differential geometry principle, inherent characteristic can be described by some local geometry parameters, such as spatial curvature of each point [10]. If the retrieval process can fully use these parameters, a good retrieval result will be achieved even to the images with slight different shape characteristic. However, spatial curvature can only describe the local characteristic of the surface and cannot perform well in the global shape representation, presence of noise, occlusion, and clutter.
In this paper, we propose a new solution combined the two kinds of characteristic. After using spatial curvature to describe the local characteristic, we choose co-occurrence matrix to represent the global shape characteristic. It is well known that co-occurrence matrix is widely used to texture analysis and can estimate image properties related to second-order statistics [11, 12]; traditional co-occurrence matrix has been proved to be very powerful for texture analysis and dealt mainly with gray level to describe the characteristic of texture.
A co-occurrence matrix can describe the gray statistical characteristic on a texture image if the matrix stores the gray-level information; we can deduce that a co-occurrence matrix can represent the spatial curvature statistical characteristic on a 3D surface if the matrix stores the curvature information. Therefore, we extend the ideas of traditional co-occurrence matrix and introduce a different solution to match the 3D surfaces with slight different shape characteristic; a new “spatial curvature co-occurrence matrix” can be defined to represent the local and global shape information, and the matching problem of 3D images can be simplified to the comparison of the new defined co-occurrence matrix.
Our method is based on three procedures. The first is the numerical approach that efficiently calculates the spatial curvature of each pixel on spatial curved surface. The second is to construct the curvature co-occurrence matrix based on selected neighborhood factor, normalization process to curvature co-occurrence matrix, and some characteristic invariants independent of the translation, scaling, and rotation transforms are illustrated. Then, we compute the characteristic invariants of the matrix. The third is the classification process using similarity distance measure based on the invariants. Finally, the surfaces can be matched based on these characteristic invariants. In fact, co-occurrence matrix has been combined with the Gaussian curvature for shape representation [13], so the idea proposed in this paper is an improvement to the Gaussian curvature co-occurrence matrix. Experiments indicate a better classification rate and running complexity than traditional approaches to 3D surfaces with slight different shape characteristic.
2 The spatial curvature and co-occurrence matrix
2.1 Compute the spatial curvature
According to differential geometry principle, curvature is the inherent characteristic of a spatial surface. When a rigid transformation is applied to the spatial surface, curvature is an invariant and it is independent of the parametric approach of the surface. Therefore, Gaussian curvature and mean curvature are employed for the representation of spatial surface in this paper.
In 3D Euclidean space, given a parametric surface defined as:
where X–Y is the reference plane in 3D space, D is the projection region of the surface to X–Y plane, f(x, y) represents the distance from the surface to point (x, y) in reference plane.
S(x, y) can be represented by two fundamental forms. The first fundamental form can be posed as follows [10]:
where E, F, G, are the parameters of the first fundamental form:
The second fundamental form can be represented as follows:
where L, M, N represent the parameters of the second fundamental form, n is unit normal vector in point [x, y S(x, y)]:
The two fundamental forms of a surface can be uniquely determined by six parameters: E, F, G, L, M, N.
Gaussian curvature K and mean curvature H can be formulated as follows:
For a discretized parametric surface, \( \frac{\partial S}{\partial x},\frac{\partial S}{\partial y},\frac{{\partial^{2} S}}{{\partial x^{2} }},\frac{{\partial^{2} S}}{\partial x\partial y},\frac{{\partial^{2} S}}{{\partial y^{2} }} \) can be computed as follows:
where \( f_{x} = \frac{\partial f}{\partial x},f_{y} = \frac{\partial f}{\partial y},f_{xx} = \frac{{\partial^{2} f}}{{\partial x^{2} }},f_{xy} = f_{yx} = \frac{{\partial^{2} f}}{\partial x\partial y},f_{yy} = \frac{{\partial^{2} f}}{{\partial y^{2} }}. \)
So that Gaussian curvature K and mean curvature H can be computed according to the following formulas:
For digital range image surface, approximations can be computing by local polynomial fitting approach, n × n operator is usually utilized to the convolution operation with original range image:
where D is n × n operator. For n = 7, the parameters can be computed as follows:
where d 0, d 1, d 2 are column vectors for window operator computing.
2.2 The gray-level co-occurrence matrix
Traditional co-occurrence matrix can well describe the texture characteristic, and it is computed based on gray level. Gray-level co-occurrence matrix is one of the most known texture analysis methods, and its main idea is to characterize the relationship between the values of neighboring pixels [14].
Let f(x, y) be an image of size M × N. Suppose that the gray value of each pixel is normalized into n levels. A d-dependent co-occurrence matrix may be defined as a two-dimensional array whose generic element p d (i, j) represents the joint probability, approximated by the relative frequency, of the occurrence of a pair of points, spatially separated by d pixels, one having gray level i and the other with gray level j.
In recent decades, gray-level co-occurrence matrix has been extended to some area, such as texton co-occurrence matrix [12] and color co-occurrence matrix [15].
3 Spatial curvature co-occurrence matrix
3.1 Construct spatial curvature co-occurrence matrix
In this paper, the surface of 3D objects can be considered to be composed of spatial pixel points characterized by spatial curvature, spatial distribution of the curvatures discriminates different shape classes. Therefore, spatial curvature co-occurrence matrix can be used to represent the traversal of adjacent pixel shape difference in a 3D image.
In our approach, the co-occurrence matrix will be computed based on the curvature value of each pixel, and then we will construct some invariants, which are independent of the translation, scaling, and rotation transforms.
Before the construction of curvature co-occurrence matrix, we must normalize all the Gaussian and mean curvature values into n levels. To a point in 3D image, the Gaussian and mean curvature must be both considered to represent the shape characteristic. In a 3D surface \( S,\forall p \in S \), the complex curvature C(p) is defined as follows:
where K(p) is the Gaussian curvature of point p, and H(p) is the mean curvature of point p.
After the computation of complex curvature, we can define a d-dependent co-occurrence matrix whose element p d (i, j) represents the occurrence of a pair of points, spatially separated by d pixels, one having complex curvature level i and the other with level j.
However, in many cases, a lot of plane points, whose complex curvature are closely to zero can exist in the surface. They cannot contribute to the matching but will occupy large computing and reduce the matching efficiency. So that these plane points will be discarded before matching. Therefore, the definition of curvature co-occurrence matrix is proposed as follows:
Definition 1
Let S be a spatial curved surface,a curvature co-occurrence matrix named p d (i, j) is defined as:
where D(p 1, p 2) is the Euclidean distance between point p 1 and p 2, \( |\# | \) represents the cardinality of a set, σ is to discard plane points, N is the number of the points.
3.2 Normalization and invariants
In Definition 1, p d (i, j) represents the occurrence of a pair of points, spatially separated by d, one having complex curvature level i and the other with level j. After a rotation transform, the spatial relationship and complex curvature level of each pair will not be changed. Therefore, complex curvature co-occurrence matrix will be independent to rotation transform.
We consider a scaling transform with a scaling factor. After this transform, complex curvature of every pixel point will be changed according to the scaling factor. So the normalized complex curvature level value n is invariant. In addition, the size of neighborhood d must change with the scaling factor. In our approach, we define the value of d as follows:
where k > 0 is a neighborhood factor.
In formula 12, \( |S| \) represents the number of pixel in the surface. The reason for computing the square root of \( |S| \) is to make the scaling transform to be linear. By choosing k, we can get a suitable pixel distance, thereby obtaining suitable co-occurrence matrix.
Hence, the independence of the curvature co-occurrence matrix to scaling transforms can be guaranteed by neighborhood factor k.
Measure of co-occurrence matrix uniformity may be used for discrimination. Several parameters have been proposed to analyze texture in [14]. To curvature co-occurrence matrix, we define four invariants to describe the shape characteristic of 3D images:
where μ x and σ x are the mean and standard deviation of the row sums of the curvature co-occurrence matrix, and μ y and σ y are analogous statistics of the column sums.
3.3 Similarity measurement
In the image retrieval system, we will firstly compute the Gaussian and mean curvature of each pixel on each 3D surface, after normalize all the Gaussian and mean curvature values into n levels, then compute the complex curvature of each point. Secondly, a neighborhood factor k will be selected to construct the curvature co-occurrence matrix according to Definition 1. Again, the shape characteristic invariants will be computed.
Finally, similarity measurement process will be performed through measuring the similarity distance to every pair of surfaces in the gallery. In our algorithm, one-order Minkowski distance is employed to measure the difference of each two surfaces in the gallery. Let S and S″ be two spatial curved surfaces, the one-order Minkowski distance between S and S″ is defined as follows:
In our algorithm, a neighborhood factor can be chosen for the similarity measurement, and we can choose a threshold value to measure whether S and S″ are the same object.
4 Experimentation results
4.1 Common 3D image retrieval
The goal of the first experimentation is to verify the retrieval performance of curvature co-occurrence matrix. In this experimentation, image database is established referred to the literature [16]. In this database, we have selected 15 image categories, every category containing 100 images of size. The 15 3D images are shown in Fig. 2.
In this experiment, some traditional approaches for image retrieval and our algorithm will be applied in retrieval process for performance comparison. To each surface, we firstly compute the complex curvature of each pixel. Secondly, a neighborhood factor k will be selected to construct the curvature co-occurrence matrix according to Definition 1; in our algorithm, a neighborhood factor is chosen as 0.4 for the performance comparison and the threshold value is 20 %. In addition, we apply some traditional approach such as Fourier descriptor representations [5], moment invariants representations [6], shape distributions [7], curvature-based representations [8], and neural network approaches [9] for comparison. We design retrieval precision to represent the percentage of correct retrieval quantity in the gallery. The average retrieval precision [17] of applying these approaches is shown in the Table 1. In this table, the third column illustrates the running time of every algorithm (CPU: PIV2.0GHZ, RAM: 1 GB, Software: MATLAB7.0).
The result shows that the algorithm in this paper has a good retrieval precision and takes low running time. However, this approach has no obvious advantage in comparison with some other algorithms.
4.2 3D similar image retrieval
In the second experimentation, we will construct a database containing some 3D images with slight different shape characteristic. In this database, we select 10 image categories but some categories are similar, every category containing 100 images of size. The 10 3D images are shown in Fig. 2.
We apply the same image retrieval approach in this database. The average retrieval precision of applying these approaches is shown in the Table 2.
As we can see from Table 2, our algorithm can get a correct result. Although the moment invariants representation takes the least running time, the average retrieval precision is not good. Our algorithm cost only 17,540 ms in the experiment because the plane points are discarded before matching. Therefore, the idea based on curvature co-occurrence matrix can get better classification result to surfaces with slight different shape characteristic.
4.3 The selection of neighborhood factor
In our algorithm, the selection of neighborhood factor k is very important. The neighborhood factor can guarantee the independence of the curvature co-occurrence matrix to scaling transforms. In the first and second experiment, the neighborhood factor is chosen as 0.4 and this value is selected based on the third experiment Fig. 3.
In fact, when k is bigger, the average retrieval precision will be higher. However, a bigger neighborhood factor will cost more running time. We choose 20 different neighborhood factors and apply the first experiment; the relationship between neighborhood factor and retrieval precision is shown in Fig. 4, and the relationship between neighborhood factor and running time is shown in Fig. 5.
It can be seen from the two figures, we can get a better result if the size of neighborhood factor is suitably selected. Generally, when neighborhood factor is selected close to 0.5, our algorithm will get a good effect.
4.4 Noise robustness
It is well known that the computation of Gaussian curvature and means curvature is notoriously sensitive to noise and local perturbation. In the fourth experiment, firstly, we add Gaussian noise [N(0, σ)] on each surface in the database mentioned in the first experiment. In this experiment, σ increases from 0 to 1.0 mm. We classify the various noisy surfaces using curvature co-occurrence matrix and some traditional approaches. The retrieval precision is shown in Fig. 6 for various σ values.
From the figure, we can see that our algorithm does not have good noisy robustness. At present, our approach can get encouraging matching efficiency and running time complexity in case of high signal-to-noise ratio. However, our algorithm can keep a good classification rate when σ < 0.1 mm, the future work will concentrate to the problem of noise robustness.
5 Conclusion
This paper proposes a novel approach for 3D image retrieval. Gaussian curvature and mean curvature are employed to represent the inherent characteristic of spatial curved surfaces; the conception of traditional co-occurrence matrix in texture analysis is extended to the idea of basing on the spatial points, and then the curvature co-occurrence matrix is constructed to describe the shape characteristic of 3D images. Normalization process is applied to the co-occurrence matrix, and the invariants independence of the translation, scaling, and rotation transforms is proved. For 3D images with slight different shape characteristic, experiments indicate a lower computation complexity and a better retrieval rate in comparison with the recent methods.
However, the efficiency of this approach would be reduced when the noise increase. In future work, we will focus on the research of the recognition problems for noise robustness and the improvement of the algorithm.
References
Funkhouser T, Min P, Kazhdan M, Chen J et al (2003) ACM Transactions on Graphics 22(1):83–105
Reinhart, G., Tekouo W. 2009. Automatic programming of robot-mounted 3D optical scanning devices to easily measure parts in high-variant assembly. 58(1):25–28
Liu Y, Zhang D, Lu G, Ma W (2007) A survey of content-based image retrieval with high-levelsemantics. Pattern Recognition 40(1):262–282
Wong RCF, Leung CHC (2008) Automatic semantic annotation of Real-World Web images. IEEE Transactions on Pattern Analysis Machine Intelligence 30(11):1933–1944
Zhang Z, Troje NF (2005) View-independent person identification from human gait. Neurocomputing 69(1–3):250–256
Xu D, Lia H (2008) Geometric moment invariants. Pattern Recognition 41(1):240–249
Osada R, Funkhouser T, Chazelle B, Dobkin D (2002) Shape distributions. ACM Transactions on Graphics 21(4):807–832
Ludersa E, Thompsona PM, Narra KL, Togaa AW et al (2006) A curvature-based approach to estimate local gyrification on the cortical surface. NeuroImage 29(4):1224–1230
Zhang J, Ge Y, Ong SH, Chui CK et al (2008) Rapid surface registration of 3D volumes using a neural network approach. Image Vis Computing 26(2):201–210
Dubrovin B, Fomenko A, Novikov S (1999) Modern geometry-methods and applications (I), 2nd edn. Springer-Verlag, GTM
Haralick R, Shanmugam K (1973) I Dinstein. Textural features for image classification. IEEE Transactions on Systems Man and Cybernetics 3(9):610–621
Liu GH, Yang JY (2008) Image retrieval based on the texton co-occurrence matrix. Pattern Recognition 41(12):3521–3527
GUO K. 2010. 3D shape representation using Gaussian curvature Co-occurrence Matrix.Lecture Notes in Computer Science, 6319: 373–380
Haralick RM, Shangmugam K, Dinstein I (1973) Textural feature for image classification. IEEE Transactions on System Man Cybemetics 3(6):610–621
Yu FX, Luo H, Lu ZM (2011) Colour image retrieval using pattern co-occurrence matrices based on BTC and VQ. Electron Lett 47(2):100–101
Mian AS, Bennamoun M, Owens R (2006) Three-dimensional model-based object recognition and segmentation in cluttered scenes. IEEE Transactin Pattern Analysis Machine Intelligence 28(10):1584–1601
Liu GH, Li ZY, Zhang L, Xu Y (2011) Image retrieval based on micro-structure descriptor 44(9):2123–2133
Acknowledgments
This work is supported by Research Fund for the Doctoral Program of Higher Education of China (20090162120069), Science and Technology Plan of Hunan (2009FJ3016), NSFC(61202341), postdoctoral fund of Central South University.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Guo, K., Duan, G. 3D image retrieval based on differential geometry and co-occurrence matrix. Neural Comput & Applic 24, 715–721 (2014). https://doi.org/10.1007/s00521-012-1288-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00521-012-1288-4