A New Content Based Image Retrieval Method Based on a Sketch-Driven Interpretation of Line Segments

1 Motivations and Goals

In this paper we present a new method for Content Based image Retrieval (CBIR) based on the analysis of the ob­ ject shapes. In [Anelli et a/., 2002] we have proposed a CBIR technique based on a Deformation Tolerant version of the well-known Generalized Hough Transform (DTGHT). In this paper we start from that work and we go further with the objective to augment the system precision. We intro­ duce some segmentation rules corresponding to Gestalt prin­ ciples (see, for example, [Ullman, 1996] and [Koftka, 1935]) exploiting the continuity properties of the edge segments and a more accurate matching method which compares the searched shape with the image lines. We have obtained an acceptance/rejection rule able to classify a data base image as relevant or not relevant with respect to the user's query.

The novelties of our approach with respect to similar sys­ tems is its capability to deal with every kind of real images, without caring of light conditions, with not uniform back­ grounds and possible occluding objects.

2 Pre-Processing and Sketch Localization

Each image of the system data base is off-line pre-processed in order to extract an edge map and to reduce the noise. We perform a standard edge extraction and thinning process using the Canny edge detector with Sobel 3 x 3 masks [Shapiro and Stockman, 200 I]. After this standard pre-processing, we use two salience filters to erase those thick textured areas which deteriorate the retrieval process (for details, see [Anelli eta/. ,

2002]). From now on we call I the image's edge map after these pre-processing phases.

We are now interested in merging the pixels in I with their neighbors in order to build line segments. We de­ fine a segment s as an ordered list of points belonging to I : s =< PI ,P2, ···Pn. > suchthateachp; (i = 1, ... ,n8 ) is adja­ cent to Pi- ! and Pi+ I in a 8-connected interpretation of pixel adjacency. Moreover, p1 and Pn, (the segment end-points) can alternatively be such that: (I) they have only one adj a­ cent point; or (2) they are a junction with another segment, i. e., they have more than 2 adjacent points. All the other points Pi (i = 2, ... , n 8 -1) have exactly 2 adjacent points. This seg­ mentation process is performed because pixels that are part of the same continuous segment are more likely to belong to the same object.

On-line, the system accepts a user drawn query represent­ ing the shape she/he is interested to find in the data base. The sketch S is processed in order to extract the R-TableT [Bal­ lard, 1981]. We use the following algorithm:

Sketch Representation Construction(S)

1 Compute the centroid Pr of S.

2 For each pointpk (k = 1, ... , m) of S,set:

where m = lSI (m is the cardinality of S).

Once the R-Table is computed, we compare such sketch representation with the previously processed data base im­ ages with the aim to localize a region in each image which maximizes the likelihood of the presence of a shape similar to the sketch. This phase is important because we do not man­ ually select in the images the interesting objects from their background like the most working CBIR systems presently do. We adopt a Deformation Tolerant version of the General­ ized Hough Transform (DTGHT) [Anelli et a/. , 2002].

The main difference with the Generalized Hough Trans­ form (GHT)[Ballard, 1981] concerns the voting phase. Here we increment all those accumulator's positions belonging to a bi-dimensional squared range centered in Pr (called the vot­ ing window W (Pr) ), for each edge point p of I and each vec­ tor v = Pr - p in T . This is efficiently achieved using a dynamic programming technique and splitting the voting pro­ cess in two sequential phases: the exact voting phase and the spreading phase (for details, see [Anelli eta/. , 2002]). If M is the point with the highest score in the final Hough accu­ mulator (A) after the spreading phase, then we take it as the most likely position for the center of mass of a possible shape similar to Sin I. In other words, if such a shape exists in I, M is its most likely centroid. Experimental results presented in [Anelli eta!., 2002] confirm this assumption. Neverthe­ less, differently from the original GHT, in which the score of the accumulator in its maximum is equivalent to the number of points of S in I, with a DTGHT approach, due to the aug­ mented voting area, it is sometimes possible that a thick and random distribution of points and segments in I can produce a high value A[M] not corresponding to a shape really simi­ lar to S . In order to reject such cases, in the next section we perform some tests on the segments distribution around M .

3 Verification Phase

In the following we assume that M is the point in I found as described in Section 2, m = lSI and W is the voting window. The aim of the verification phase we are going to explain in this section is to verify if the disposition of the segments in I around M is really perceptually similar to the S' shape. In order to avoid false positives, first of all we check the por­ tion of S which can be matched with segments in I. This is intuitively done by projecting S on I (let us call S' such pro­ jection, with M its centroid), looking for segments on I in the the neighborhood of S' and marking the portion of S justified by these segments. Furthermore, we need to take into account inhibitory segments intersecting the neighborhood of S' but not really following the shapeS. In the following we give the operational definitions for justifying and inhibitory segments.

A point p belonging to I is called a valid point if:

where a is a suitable threshold and ¢I(p), ¢s(i) are, respec­ tively, the edge orientation of the point p in I and the edge orientation of the i-th point of S. We calli a valid hypothesis for p. A segments; is a justifying segment if:

where k1 is a fixed threshold (presently k1 = 0. 7) and Vi is the set of all the valid points of the segment s i. Let J be the subset of I's segments which are justyfing segments.

Finally, a segment s; is called an inhibitory segment if s; is not a justifying segment and:

where k3 and k2 are two fixed thresholds (presently k2 = 0.2, k3 = 0.4) and F; is the set of all the points p in s; which satisfy:

Let H be the subset of all the inhibitory segments of I. The verification test is given by the logical and of the justification test and the inhibitory test.

Justification Test(J)

1 Fork E [1, m], set the local boolean vector B[k] :=false.

2 For each s; E J do: 3 For each point p E V; do: 4 For each valid hypothesis k, set B[k] :=true. 5 Return:= I{B[k]: B[k] = true}l 2 k4m

In the above algorithm k4 is a threshold, currently fixed to 0. 7. We check in this way that at least a portion k4 of S is present in I in the right position with respect to M.

Finally, the following is the inhibitory test:

Inhibitory Test(H,J) := ~s;EHis;l < ~s,EJis;l.

4 Experimental Results

We have tested our method with a data base composed of283 images randomly taken from the Web. They show a great va­ riety of subjects: 26 cars, 22 horses, 20 guitars, 20 pistols, 20 tennis rackets, 20 saxophones, 20 bottles, 20 watches, 15 cru­ cifixes, lO vases. Moreover, the data base contains different other subjects such as: animals, faces, landscapes, airplanes, boats, fruits, mushrooms, cups and so on.

No simplifying assumption has been done about images: they usually have not uniform backgrounds and often the re­ trieved objects are occluded by other objects. No manual seg~ mentation has been performed on the images.

We paid attention to choose as users people not aware of the data base images' shapes. Indeed, only one of the three users in Table 1 has had the possibility to observe the reposi­ tory images before his drawings (User 3). Each user has per­ formed six queries. The drawn subjects are: a car, a pistol, a tennis racket, a watch, a bottle and a guitar. We report our re­ sults in Table 1. Average precision and recall for all the three users and all the queries are, respectively: 0.80 and 0.62.