With a vast amount of publicly available high-quality images, actual image databases start to emerge, and image database management methods are becoming important.
Abstract
With a vast amount of publicly available high-quality images, actual image databases start to emerge, and image database management methods are becoming important. An important manner of finding your way around an image database is to look for images similar to a desired reference image. Typing in “I am looking for an image of such and such characterizations”, requires a very high level of definition on the part of the user, and understanding on the part of the algorithm. Instead, it is much easier if while examining one could label an image or even draw it, and it will index to images with similar content in the database.
There are many indicators for content similarity of images: color, texture, composition etc. In this paper we present a new shape-indexing method based on Curve-Signatures and Dynamic-Programming. We focus on shape similarity, while examining the shape of the object in the image.
Like other similarity types, shape similarity is subjective, some people may view different shapes as more similar then others. Thus our goal is to locate a set of similar images and let the user select from this given set. To help the user narrow down his selection, the system provides the Partial Compare option, to index specified parts of the shape (e.g. the tail part of a given fish contour).
DASI was tested on the Surrey database containing 1100 images of fish contours.
Implementation
1. Signature:
A curve signature is a one-dimensional description of the curve, that is invariant to a group of viewing transformations [2]. The proposed algorithm employs Curvature Signature, which is invariant to Euclidean motion (translation and rotation). The signature is thus a sequence of externalangles on the polyline obtained by sampling the contour in fixed Euclidean steps. The signature is treated as a cyclic vector, and thus it is invariant to shifts in the initial sampling point. Neighborhood signatures describing the signature’s difference from it’s surrounding are employed to enhance the similarity between fish that are related via a relatively constant curvature distortion (e.g. while swimming).
For invariance to mirror-symmetry, a pair of signatures represents each contour: The original signature, and its reverse-sample-order version.
2. Dynamic Programming:
Dynamic Programming quantifies the difference between a reference signature, and a test signature, by finding the best warp-mapping between the signatures, and returning the total error of the selected match [3]. Indexing is achieved by comparing all the images in the database to the reference image and sorting.
The boundary and the continuity conditions of the Dynamic Programming algorithm were modified in order to support invariance to the position of the
initial signature point:
1. Boundary conditions were made uniform, ensuring an equal possibility to match the first/last point of the reference signature to any point in the test signature.
2. Additional continuity penalties were modified.
The penalties preserve the desired global shape of the mapping on one hand, and enable local flexibility on the other:
- Slope Penalty: Proportional to the square of the diversion from the ideal slope
- Jump Penalty: Proportional to the square of the local matching gradient
Other important modifications were:
- Interpolation of the signature length to a fix-size
- Curve smoothing pre-processing [4]
3. Partial-Compare
The partial-compare option enables the user to specify a boundary segment, which is looked-up in the database. To implement partial-compare, the boundary conditions are modified. The specified signature segment is cyclically shifted to the beginning of the reference, and the mapping is stopped at the end of the segment.
Conclusions
As can be seen in Figure 1, DASI performs well on a large database of fish contours, and can handle the Partial-Compare task as well.
Figure 1: Examples of DASIs indexing results. The reference image is on the left and similar images are sorted from left to right. Partial compare segments are marked blue on the 3 last images.