Search for similar shapes in the SQUID system:

Shape Queries Using Image Databases

Imagine that you have a large number of images and wish to select some of them which are similar to a certain image. You will need a content based image database system which accepts an image as its input and retrieves all images like that by using some image properties such as color, texture, shape and keywords.

At the Centre for Vision, Speech, and Signal Processing in the 5* rated Department of Electronic and Electrical Engineering (one of only 5 UK departments to receive the highest research grading) at the University of Surrey , we have developed a system for Shape Queries Using Image Databases. SQUID is the first image database retrieval system we know of on the internet which allows users to submit shapes as query objects. The work has been carried out by Sadegh Abbasi, and has been supervised by Dr Farzin Mokhtarian, and by Professor Josef Kittler .

There are about 1100 images of marine creatures in our database. Each image shows one distinct species on a uniform background. Every image is processed to recover the boundary contour, which is then represented by three global shape parameters and the maxima of the curvature zero-crossing contours in its Curvature Scale Space image.

Curvature Scale Space Computation and Matching

The CSS image is a multi-scale organization of the inflection points (or curvature zero-crossing points) of the contour as it evolves. Intuitively, curvature is a local measure of how fast a planar contour is turning. Contour evolution is achieved by first parametrizing using arclength. This involves sampling the contour at equal intervals and recording the 2-D coordinates of each sampled point. The result is a set of 2 coordinate functions (of arclength) which are then convolved with a Gaussian filter of increasing width or standard deviation. Next step is to compute curvature on each smoothed contour. As a result, curvature zero-crossing points can be recovered and mapped to the CSS image in which the horizontal axis represents the arclength parameter on the original contour, and the vertical axis represents the standard deviation of the Gaussian filter.

The features recovered from a CSS image for matching are the maxima of its zero-crossing contours. The matching of two CSS images consists of finding the optimal horizontal shift of the maxima in one of the CSS images that would yield the best possible overlap with the maxima of the other CSS image. The matching cost is then defined as the sum of pairwise distances (in CSS) between corresponding pairs of maxima. Note that this technique was compared to moments and Fourier descriptors, and found to perform better.

The top left figure above shows a sample image from the database. The bottom left figure shows the fish boundary with white points showing the locations of its curvature zero-crossing points during evolution, and the right figure shows the construction of its CSS image. Details of this technique can be found in BMVC' 96 and IDB-MMS' 96 as well as other published papers. The CSS representation is also invariant under the affine transform and useful for robust multi-view 3-D object recognition. The parallel representation for space curves is referred to as the torsion scale space image. These ideas can also be generalised to 3-D surfaces.

Boundary data for the database objects

If you are working on shape similarity retrieval (or shape analysis in general) and wish to test your method on our data you can retrieve them. Please send us an email, and remember to acknowledge us in the relevant papers.

Retrieval using the SQUID system

You can try our system by clicking on the Demo button below. The system will show you a number of recovered object boundaries. You can then select one of them and the system will return similar contours from the database. A non-negative integer match value is shown under each retrieved shape. Zero means extremely similar. Increasing values then indicate less and less similarity to the query shape. The number of shapes retrieved can be adjusted. Naturally, if no shapes similar to the query shape exist in the database, the match values for all the retrieved shapes will tend to be high.

SQUID Demo

NOTES:

The CSS shape descriptor has been selected for MPEG-7 standardisation (thanks to Mitsubishi VIL).
SQUID database was used for MPEG-7 evaluation of shape descriptors.
SQUID has been featured on the Computer Vision Home Page (Demo section) since May 1997.
SQUID was selected a Links2Go Key Resource (ranked 28) in Computer Vision (May 1999).
Have you used SQUID for research purposes or as a teaching tool? If yes, please email us and let us know how it was used.

F.Mokhtarian@surrey.ac.uk

Last update: October 2005