【paper】Perceptual Distance and Effective Indexing for shape similarity

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.


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




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s




Just another WordPress.com site

Jing's Blog

Just another WordPress.com site

Start from here......







Just another WordPress.com site

Where On Earth Is Waldo?

A Project By Melanie Coles

the Serious Computer Vision Blog

A blog about computer vision and serious stuff

Cauthy's Blog

paper review...

Cornell Computer Vision Seminar Blog

Blog for CS 7670 - Special Topics in Computer Vision


Life through nerd-colored glasses

Luciana Haill

Brainwaves Augmenting Consciousness



Dr Paul Tennent

and the university of nottingham

turn off the lights, please

A bunch of random, thinned and stateless thoughts around the Web

%d bloggers like this: