Partial Shape Matching using Smith Waterman Algorithm

Partial Shape Matching using Smith Waterman Algorithm

1. Introduction

Shapes are mathematically defined as an equivalence class under a group of transform. However, in computer vision communities, a shape is more often referred to the geometric relations of object parts or feature points. Usually we care more about shape similarities and shape distances (dissimilarity). Surveys about shape matching can be found from [34]. Shape is one important aspect of objects’ features and, therefore, shapes are frequently used as an important and distrimitive feature for object recognition.

   Some of previous shape representation methods do not divide the whole shapes into parts and compute a multi-dimensional feature value for the whole shape. Perimeter, compactness, eccentricity, Fourier, and wavelet descriptor are among the most frequently used features. Other methods represent the shapes by parts, but they do not compute features for each individual part. A feature vector is computed for the whole shape, for example, shape area, Euler number, and Hu moments [48]. These shapes are more like shape-features for shape classification or object detection.

   Here, we focus more on the methods that represent the shapes using parts or points where shape features are computed for each part or point. The advantage of part-based method is that this representation provides more information about the shapes and makes correspondence based matching possible.

2. Partial Shape Matching Using Smith Waterman Algorithm

If the points in a shape are connected sequentially, it is a sequential shape. Contours of objects, both outer and inner contour, are suitable for this kind of presentation.

The following figure illustrates the main idea of partial shape matching. Similar shape parts (point 1 through point 15) are efficiently found by using a local alignment algorithm, the Smith Waterman Algorithm [1], and local shape descriptors; green points are matched point pairs (labeled by number) while red points are unmatched points; other black points are not in similar segments.

Figure 1. The main idea of partial shape matching

3. Source Code

Play with some examples:
1. Download the Kimia Shape database
2. Install OpenCV/python in your machine
3. Download the codes from
http://code.google.com/p/shapematching/
4. play with them

a. Extract sequential shapes
>exMSS.py -d -n 100 -o animal-01.mss animal-01.jpg

b. extract shape features, for example, shape context feature
>exFeature.py -s animal-01.mss animal-01.sc
>exFeature.py -s animal-02.mss animal-02.sc

c. Partial Shape matching
>csw.py -i animal-01.jpg,animal-02.jpg animal-01.sc animal-02.sc

Reference:

[1] T.F.Smith and M.S.Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147:195–197, 1981.
[2] L.Chen, R. S. Feris, and M. Turk. Efficient Partial Shape Matching Using SmithWaterman Algorithm, Workshop on Non-Rigid Shape Analysis and Deformable Image Alignment (NORDIA'08) 27-28 June 2008, Anchorage, Alaska, in conjunction with CVPR'08 (pdf)

Longbin Chen's Home Page