via this paper in 2000
The use of global attributes presents limitations in modelling perceptual aspects of shapes, and poor performance in the computation of similarity with partially occluded shapes.
More effective solutions have employed local features, such as edges and corners of boundary segments.
- They are based on the partition of the shape boundary into perceptually significant tokens.
- Petrakis and Milios have approximated shapes as a sequence of convex/concave segments between two consecutive inflection points. points are indexed using an R-tree.
- Grosky and Mehrotra have approximated shapes as polygonal curves:
- for each vertex, a local feature is defined by considering the internal angle at the vertex, the distance from the adjacent vertex, and the vertex coordinates.
A fixed number
of these local features is extracted from each shape.
- A shape is thus represented by an attributed string.
- Similarity between two shapes is computed as the editing distance between the two strings of the boundary features
- Mehrotra and Gary have developed
a retrieval technique known as Feature Index-Based Similar Shape Retrieval.
a polygonal approximation of the shape boundary, which is represented by an ordered finite collection of boundary features, each collection represents one segment of the shape boundary.
- segments are defined with a fixed number of adjacent vertices
- Boundary feature vectors are organized in a kdB-tree
- The matching of one or more features doesn’t guarantee full shape matching
- once shapes with similar features are retrieved, shape similarity is checked by overlaying each retrieved shape on the query shape and evaluating the amount of overlap between them
similarity based on polygonal approximation and Euclidean distance between boundary features has little relation with perceptual similarity and cannot be employed for generic shapes.
polygonal shapes of man-made objects
sensitivity to small deviations of feature values is critical to retrieval.
If the features at the root of two subtrees placed on the same level of the index have a very small difference, and a slightly different version of one of them is compared with both, the wrong path might be chosen, thus leading to incorrect retrieval.
To cope with both these requirements two distinct distance measures have been defined: a token distance and a shape distance.
- The token distance is a metric distance and is used to provide a measure of the similarity between two tokens.
- The shape distance is a nonmetric distance, defined as a combination of token distances, and is used to derive a global measure of shape similarity which fits humans’ perception.
- Shape distance does not depend on the ordering of tokens along the curve. This can determine retrieval of false positives.
Indexing is performed at the token level, by exploiting the metric properties of token distance.
SHAPE INDEXING USING A MODIFIED M-TREE
In that a generic token is modelled as a point in the two-dimensional (2-D) feature space of curvature and orientation, the
representation of a generic shape results to be a set of points in this space.
Shape tokens are stored in an M-tree index.
M-tree organizes tokens as a hierarchical set of clusters, each of which is identified by a routing object, (i.e., the center of the cluster), and a covering radius, which determines the maximum distance between the routing object and each tokens included in the cluster