Distance interior ratio: A new shape signature for 2D shape retrieval

Highlights

• A novel 2D shape signature named Distance Interior Ratio (DIR) is proposed.

• DIR represents an intersection pattern of line segments on a shape contour.

• Interval of each bin is defined using to the mean of the distribution method.

• Our method achieves higher retrieval rate than other distance distribution methods.

• DIR distance can differentiate the distance distributions of homometric pair objects.

Abstract

In this work, we propose a shape signature named Distance Interior Ratio (DIR) that utilizes intersection pattern of the distribution of line segments with the shape. To improve the efficiency of the histogram-based shape signature, we present a histogram alignment method for adjusting the interval of the histogram according to the distance distribution. The experimental result shows a 3.25% improvement using the proposed histogram alignment. When compared to other shape signatures, our experimental result gives a 77.69% retrieval rate using MPEG7 Part B dataset [Latecki, et al. (2000)[14]].

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.