Objective

2

Description

matching

similarity measurement

and retrieval of shapes are basic tasks in computer vision

image recognition

and machine intelligence

and they remain as open issues. Except for the methods of geometry complex transform and shape contour-based Fourier descriptor

all other methods are not information preserving

which means that the original shapes cannot be reconstructed from their descriptors. Consequently

the descriptors cannot be guaranteed to fully represent the characteristics of original shapes. Although geometry complex transform and shape contour-based Fourier descriptor are information preserving

they are only applicable to simple closed shapes or some other special types of shapes

which limits their applications. We propose a generic shape descriptor

which is named inside-circle distance transform (ICD). The ICD method can be used for matching

similarity measurement

and retrieval of any shape with obvious contours

and it is information preserving.

Method

2

In the ICD method

we initially calculate the minimum circumscribed circle of a shape. Then

we draw a set of equidistant parallel lines that are perpendicular to x-axes

calculate the intersections of each line and shape contour

and compute the distance vector for each line. We finally form a distance matrix with all distance vectors. We yield another distance matrix by rotating the shape anticlockwise around the center of its minimum circumscribed circle by $θ$ degree and repeating the aforementioned process. A set of distance matrices is generated by repeating the process for[360/$θ$] times. With all distance matrices of the shape in hand

we construct the feature matrix of the shape. The feature matrix of a shape is a representation of the original shape with rich information

which can be used to describe the original shape

to measure the similarity of two shapes and reconstruct the original shape. Therefore

ICD is an information-preserving method. This capability of ICD to reconstruct original shapes is useful. We can thoroughly understand the intrinsic of shapes using the ICD method. Feature matrix is a powerful tool for shape representation and shape matching. We prove that ICD is scaling

rotation

and translation invariant

which is an important property in shape description

matching

and retrieval.

Results

2

We construct 40 shapes to verify the capability and test the effectiveness of the ICD method. The shapes are categorized into eight classes

with five shapes in each class. In each of these eight classes

one basic shape exists

and the others are deformations of the basic shape through modifications

such as twisting the contour or adding noise. We further expand the set of shapes by performing affine transformation with random scale factor

random rotation angle

and random translation of position to generate two new shapes for each of the 40 shapes. This expansion results in a total of 120 shapes. We initially perform a similarity measurement between each of the eight basic shapes and each of 12 randomly selected shapes. Experimental result shows that in similarity measurement of shapes

the ICD method generates the same vision results as those of human vision. If two shapes are determined to be similar

then the ICD method can calculate their scaling factor and orientation differences. We also test the effectiveness of retrieval through the well-known method of "Bullseye score." Results show that 38 out of 40 subclasses achieve a score of 100

which is extremely satisfactory. We compare the ICD method with three other classic shape description and matching methods

namely

shape context method

histogram of Radon transform

and generic Fourier descriptor

on the basis of the widely used shape database of MPEG-7. This database consists of 70 classes

with 20 shapes in each class and hence a total of 1400 shapes. The Bullseye score method is adopted. Results indicate that all the methods under evaluation have their own advantages and disadvantages with respect to different shape classes. Moreover

on average

the test score of the ICD method is approximately 20 points higher than those of the other three classic methods. ICD shows significant effects outperforming those of the other methods in all experiments. In the reconstruction experiments

we randomly select four shapes from the MPEG-7 database and reconstruct them by using the ICD method with varying parameters $k$ and $θ$

where $k$=30

50

150 and $θ$=1

6. Experiment results show that the reconstructed shapes become accurate with the increase of parameter $k$ and decrease of parameter $θ$. The reconstruction experiments also imply that shape reconstruction is more sensitive to parameter $k$ than to parameter $θ$. In application scenarios in which the rotational angle is insignificant

$θ$=3 is an optimal recommendation by our experiments.

Conclusion

2

The ICD method and its corresponding feature matrix can be used to represent

match

and retrieve shapes effectively. This method has the prominent feature of being information preserving

thereby assuring that it represents a shape without losing information. When this method is used to compute similarity of shapes

it can generate the same result as that of human vision. For two similar shapes

the ICD method can compute their scale factor and rotation differences. Theoretical analysis

mathematical proofs

and experiments show that ICD is effective

useful

and information preserving

and it outperforms several important classic methods.