VP Image Retrieval System

Developer

National Center for Science Information Systems, University of Tokyo, Japan.

URL

http://www.rd.nacsis.ac.jp/.

References

[KSH95].

  

Figure 30: VP.

Features

The silhouettes extracted from a database image are first decomposed into convex parts. The decomposition process is recursively performed as follows: at each negative curvature point V_i, an erosional vector, directed to the interior of the shape contour and proportional to the global angle and length of the concavity at V_i, is computed. Based on this vector, the speed to erode away the current part of the contour from a negative curvature point V_i to a point V_j on the other side of the contour is defined. The shape contour will be split by a line segment V_iV_j of minimum erosion time. Next, for each part of the decomposition a number of features are extracted: attributes of the convex part (horizontal/vertical position, scale, shape, skeleton length, curvature and slope) and relations between two adjacent parts (relative horizontal/vertical position, relative scale, position of the skeletons intersection and angle between the two skeletons). In order to represent these features, their value domain is quantized into a small number of levels (e.g., 3 for the length attribute, which correspond to small, medium, large), each feature being associated a fixed number of bits in a binary sequence. Two binary vectors are constructed. The first one is the concatenation of all attribute sequences of the parts in the decomposition (such a sequence is called primitive signature). The second one, retains the relations between the parts along with their attributes.

Querying

Queries are formulated in three steps. First, a silhouette is drawn, this is next automatically decomposed into corresponding convex parts, and finally the user associates query weights to these parts. These weights specify the degree of relevance in the query process, from not important to very important, of the computed attributes and relations of the query parts. When the user chooses to relax some of the attributes of particular parts, the system represents this by adding extra 1 bit values to the primitive signatures of these parts in the sequences coresponding to the selected attributes.

Matching

The matching is done by shifting each query primitive signature over the concatenated primitive signatures of the target image and counting the matches C_a. Similar shifting and conjunction operations are applied to the second vector, storing the relations between parts, with the number of matched relations computed being C_r. The similarity score is given by $\emph{S} = (C_a+C_r)/(N_a+N_r)$, where N_a is the total number of primitive signatures of the first query vector, and N_r is the total number of relations in the other query vector.