Distance interior ratio: A new shape signature for 2D shape retrieval☆
Introduction
Shape is an important feature used for describing image content. It can be used in image retrieval, which is the process of identifying images (objects) in a large database that are similar to a given image [25] as well as a 3-dimensional shape retrieval [3], [16]. Assuming image segmentation has been done and each object in the database is a simple polygon with n vertices, the similarity of the two polygons can be measured using the closest distance between the boundary points on one polygon to the others. Modified Hausdorff distance [7] and Frenchet distance [1] are examples of shape similarity measurement. The restriction of such methods is a linear scan of the database when applied in the retrieval system [20].
A shape signature that is able to characterize the properties of a shape in a compact representation is applied with an efficient search structure, such as Locality Sensitive Hashing [9]. A good shape signature should be invariant under rigid motion, and robust to noise and occlusion. There are two main groups of shape signature: region-based methods and contour-based methods [17], [25]. The region-based method considers the information of the pixels within the shape. The shape matrix [8], [24] is an example of this group. In contrast, the contour-based method considers the information obtained from the shape contour. Many contour-based methods have been proposed, although the location of the line segment on the shape contour has never been included. Pairwise distance among points on a shape contour [12], [18] or between points and the shape’s centroid [21], [26] are natural information. A normalized histogram is applied in order to achieve a compact size while being invariant to noise and rigid motion. To capture salient features of shape, local quantities such as Shape Context [2], Inner Distance Shape Context [15], and Distance Sets [10] can be computed. The signature at each point can be used to efficiently find the correspondence points on the two shapes. Methods such as thin-plate spline (TPS) [2] and dynamic programming (DP) [15] are applied in order to obtain the optimum assignment of correspondence points of the two objects.
Recent local descriptors considered both shape contour and region that are insensitive to articulated shape [11] and occluded shape [13]. Both methods apply the geodesic distance in order to find the shortest path inside the shape region to represent a shape’s geometric structure. In [6], complex network and spectral graph theories are used to define the shape signature.
In our preliminary experiment of two-dimensional shape retrieval, we found two problems. The first problem is a homometric pair [23] that is a pair of objects with different shapes but similar distance distribution. See Fig. 1 for illustration. The second problem arises when defining the interval of each bin in a histogram using the maximum distance.
According to our observation of the pairwise distance of the homometric pair objects, the distance from a point p to points on the two shapes’ contours as in Fig. 2 are the same. This is because the pairwise distance distribution does not take into account whether or not the line segment crosses the shape contour. To cope with the homometric pair problem, we proposed a distance called Distance Interior Ratio (DIR) that is able to capture the information of the location of the line segments between the two points on the shape contour. Given a segment ab between two points a and b on the boundary of a region P, the DIR (Distance Interior Ratio) of ab is the ratio of the total length of its fragments P ∩ ab to the length |ab|. Using the DIR distance distribution, the two shapes in Fig. 2 are different. The DIR distance of all line segments of a triangle shape in Fig. 2 equals 1, while it is strictly less than 1 for some line segments of a T shape. A preliminary result is reported in [5].
The proposed DIR distance is different from the inner distance [15] and the geodesic distance [11]. The inner distance and the geodesic distance consider only the line segments of the shortest path within the shape contour. The inner distance requires a construction of a visibility graph in order to find the shortest path among points on the shape contour. The geodesic distance requires high computation cost when finding the minimum path that joins the two points on a shape contour. Our proposed method considers all line segments that joins two points on a shape contour in order to find the intersection pattern of the distribution of line segments with the shape itself.
To the best of our knowledge, this is the first descriptor that includes the location information of each line segment.
A histogram is a common method that has been used to compress the distribution of brightness of pixels in an image [22] or the distance distributions into a predefined number of bins [12], [18]. Usually, the interval is the same for every bin. It is selected as the absolute difference of the minimum and the maximum distance divided by the total number of bins (maximum-alignment). Line segments in such a way that the distances are in the interval of each bin is counted.
For such an assignment of line segments to bins, even small changes of either the minimum or the maximum distance may result in shifted bins. Consider the point configurations and their distance sets in Fig. 3(a) and (b). Their maximum-alignment histograms are shown in Fig. 4(a) and (b). The interval of the former is 1.8 and the one of the latter is 2.8. This results in shifted bins. For instance, the line segments of the length 3 switches its bin as depicted in Fig. 4(b). We proposed a new method called mean-alignment. The interval of the bins in the first half of the histogram is defined using the absolute difference between the minimum distance and the mean distance, whereas the interval of the bins in the second half is defined using the absolute difference between the mean distance and the maximum distance. Using the proposed method, the interval of the bins in each half is independently defined using the mean distance. Therefore, small changes of a shape contour result in different histogram in either the first or second half, which represents the bins for short and long line segments, respectively. Fig. 4(c) and (d) illustrate that none of the short line segments in Fig. 3(a) and (b) switches its bin.
Our contributions are a shape signature named “Distance Interior Ratio” (DIR) and a histogram alignment method for adjusting the interval of the histogram according to the distance distribution called “mean-alignment”.
Note that, in this research, we are only interested in the efficiency of the shape signature. In other words, no shape matching procedure such as thin-plate spline (TPS) as in [2] and dynamic programming (DP) as in [15] are applied.
Section snippets
Distance features
In this work, we consider that the object in the image is segmented and the shape contour is known. We define the shape contour as a set where n is the total number of uniformly selected pixels on the contour and is a vector of the coordinate of the pixel i. Let (pi, pj) be a line segment connecting points pi ∈ P and pj ∈ P where i ≠ j.
Two distance features among points in P are used to represent the shape characteristic: the Euclidean distance and the proposed DIR
Mean-alignment histogram
The shape signature of P is a two dimensional histogram of the DIR and the Euclidean distances that is denoted by H(P). It is computed by counting a number of points plotted on the feature space F that fall into an interval of each bin of a histogram. The interval of each bin is defined according to the mean value of the distance set. Details are presented in this section.
Characteristic of the distance interior ratio (DIR)
The mean-alignment histogram is able to represent distance distribution that are partially similar. However, it cannot always give a good representation. The comparison of the mean-alignment histograms of the pairwise Euclidean distance of the homometric pairs objects is depicted in Fig. 9. The height of the bars at positions 6, 7, and 8 are almost the same. Fortunately, the proposed DIR distance is able to represent the characteristic of each shape differently using the intersection patterns
Experimental result
The performance of shape signature using DIR distance is evaluated using the MPEG7 CE-Shape-1 [14] and Kimia’s 99 [19] datasets. For the DIR histogram matrix, we choose and . The boundary pixels of each object are extracted and then 500 points uniformly selected. The experiments are conducted on a desktop machine with the Intel Core i5 2.4GHz CPU and 4 GB of memory. In this research, we are only interested in the efficiency of the descriptor. In other words, no shape
Conclusion
We propose a shape signature that is a two-dimensional histogram of the Distance Interior Ratio (DIR) distance and the Euclidean distance. The DIR distance is computed from the fraction of the portion of a line segment lying inside the shape contour and the length of the line segment. Using the DIR distance, the shape is characterized according to the intersection patterns of the distribution of line segments. If a line segment crosses the shape’s concavity part, the DIR distance is strictly
Acknowledgment
The authors would like to thanks the reviewers for their valuable comments. The first author is supported by Faculty of Science and Technology, Thammasat University research fund. The second and the third authors are supported by JST entrusted project “research and development of data integration and analysis for utilization of real-world big data”. The second author is also supported by JSPS Grant Scientific Research (C) 25330002. The third author is also supported by JSPS Grant Scientific
References (26)
- et al.
Using shape distributions to compare solid models
Symposium on Solid Modeling and Applications
(2002) - et al.
Reconstructing sets from interpoint distances (extended abstract)
Proceedings of the 6th Annual Symposium on Computational Geometry
(1990) - et al.
Computing the frechet distance between two polygonal curves
Int. J. Comput. Geom. Appl.
(1995) - et al.
Shape matching and object recognition using shape contexts
IEEE Trans. Pattern Anal. Mach. Intell.
(2002) - et al.
Content-based retrieval of 3d models
ACM Trans. Multim. Comput., Commun. Appl.
(2006) Algorithm for computer control of a digital plotter
IBM Syst. J.
(1965)- et al.
Classified-distance based shape descriptor for application to image retrieval
Comput. Anal. Images Patterns
(2013) - et al.
A novel 2d shape signature method based on complex network spectrum
Pattern Recogn. Lett.
(2015) - et al.
A modified hausdorff distance for object matching
Proceedings of the International Conference on Pattern Recognition
(1994) Invariant shape description and measure of object similarity
Proceedings of the 4th International Conference on Image Processing and its Applications
(1992)
Similarity search in high dimensions via hashing
Proceedings of the 25th International Conference on Very Large Data Basess
Distance sets for shape filters and shape recognition
IEEE Trans. Image Process.
Matching 2d and 3d articulated shapes using the eccentricity transform
Comput. Vis. Image Underst.
Cited by (37)
L-shaped geometry-based pattern descriptor serving shape retrieval
2023, Expert Systems with ApplicationsCitation Excerpt :The region-based representation Tensor-based Scale Sector (TSS) (Freitas, Torres, & Miranda, 2016) constructed relatively oriented local distributed features within circular sectors. Similarly, Distance Interior Ratio (DIR) histograms (Kaothanthong, Chun, & Tokuyama, 2016) fabricated the intersection of line segment patterns present in shape. Also, retrieval rate improvement was achieved by histogram alignment based on the distance distribution.
Low-complexity arrays of contour signatures for exact shape retrieval
2021, Pattern RecognitionFast global SA(2,R) shape registration based on invertible invariant descriptor
2021, Signal Processing: Image CommunicationCitation Excerpt :The proposed method using the invariant at multi-scale for presenting global and local information for the shape. Also, Kaothanthong et al. [20] present a shape signature named DIR (distance interior ratio) based on the intersection of line segments with the curve, and a histogram alignment method. In [21], it is about a multi scale Fourier descriptor based on triangular features.
Multiscale Fourier descriptor based on triangular features for shape retrieval
2019, Signal Processing: Image CommunicationCitation Excerpt :Moreover, the complexity of these distance learning methods is generally higher. It is worth noting that our method achieves comparative or better retrieval rates in comparison with the multi-scale convexity concavity (MCC) [37] and DIR [6] methods using dynamic programming. In comparison with the other Fourier-based methods, the complexity of our method in the stage of shape matching is at an order of magnitude with the other Fourier-based methods.
Hexagonal Grid based triangulated feature descriptor for shape retrieval
2018, Pattern Recognition LettersCitation Excerpt :These are further classified into 70 shape classes with 20 shape images in each class. This dataset is used in most of the shape retrieval framework listed in the literature [1–12,15–19]. Fig. 7 shows some sample images from each class of the mentioned dataset.
Fast shape recognition via a bi-level restraint reduction of contour coding
2024, Visual Computer
- ☆
This paper has been recommended for acceptance by Dr. N. Sladoje.