SIGIR 2007 Proceedings

Poster

A Flexible Retrieval System of Shapes in Binary Images
Gloria Bordogna Luca Ghilardi Simone Milesi Marco Pagani
CNR IDPA Facoltą di Ingegneria Facoltą di Ingegneria CNR IDPA via Pasubio 5, Dalmine (BG) Universitą di Bergamo Universitą di Bergamo via Pasubio 5, Dalmine (BG) +390356224262 via Marconi 5, Dalmine (BG) via Marconi 5, Dalmine (BG) +390356224261 I24044 Italy I24044 Italy I24044 Italy I24044 Italy gloria.bordogna@idpa.cnr.it ghilardi.luca@tele2.it milesi.simone@gmail.com marco.pagani@idpa.cnr.it

ABSTRACT
This poster overviews the main characteristics of a flexible retrieval systems of shapes present in binary images and discusses some evaluation results. The system applies multiple indexing criteria of the shapes synthesizing distinct characteristics such as global features of the objects contour (Fourier Coefficients), boundary irregularities (Multifractal Spectrum), presence of concavities and convexities on the boundary (Contour Scale Space). The system is flexible since it allows customizing the retrieval function to fit an application need. The query consists in submitting to the system a binary image containing a desired shape and in specifying the distinct importance of the shape characteristics that must be taken into account to evaluate the relevance of the retrieved shapes. The retrieval function is then defined as a Flexible Multicriteria fusion Function producing ranked results. The evaluation experiments showed that this system can be suited to different retrieval purposes, and that generally the combination of the distinct shape indexing criteria increases both Recall and Precision with respect to the application of any single indexing criterion alone.

Categories and Subject Descriptors:

H.3.3 [Image indexing and Retrieval]: Information Search and Retrieval.

General Terms: Algorithms, Design, Experimentation. Keywords: shapes indexing and retrieval. 1. INTRODUCTION
Generally, in the literature, shape retrieval systems are designed for specific applications, and thus they adopt a single indexing method and a rigid retrieval scheme implementing a single retrieval function that demonstrated its effectiveness in a given context . In designing the shape retrieval system we did not target a specific application, so we defined the model and designed the system by considering as main requirements its flexibility, meant as the possibility to suit the retrieval results yielded by the system to fit distinct user needs. To this end we conceived the shape retrieval system as performing a Flexible Multi Criteria Decision making activity in which:

- the alternatives are the shapes of objects present in binary images that have to be identified in the binary images, and represented in a database. This phase has to take into account that shapes characteristics can be multiple, and that can be synthesized only approximately by a set of attributes (descriptors), - the query specifies soft constraints (admitting satisfaction degrees) on the shapes descriptors. These constraints should be customizable by the user to a specific purpose. This requirement lead us to define a query as consisting of a binary image containing the desired (ideal) shape together with tolerance values for the partial matching functions, thus requiring a more or less strict interpretation of the soft constraints, and finally importance weights associated with the distinct shape characteristics to express their desired influence on the retrieval and ranking results. - the retrieval function is the flexible multi criteria decision function performing the evaluation of the query in two steps: first each set of descriptors associated with a shape characteristic are matched against those of the ideal shape in the query, independently one another. This phase produces several ranked lists in which each stored shape can appear in a different position within each list according to the similarity of its shape characteristic with respect to those of the query shape. Secondly, these ranked lists are fused into an overall ranked list by taking into account the positions of the shapes within each list and the importance weights of the lists, i.e., of the shape characteristics, specified by the user. In figure 1 a high level sketch of the functional components of the flexible shape retrieval system is shown.

Fig. 1: Sketch of the Flexible Shape Retrieval System In the implemented system three kinds of shape characteristics (represented by three vectors of real values) have been considered to index the shapes [1]: - the number and extent of concavities and convexities on the boundary of shapes; the concavities and convexities are represented by the Contour Scale Space distribution (CSS) [4];

Copyright is held by the author/owner(s). SIGIR'07, July 23­27, 2007, Amsterdam, The Netherlands. ACM 978-1-59593-597-7/07/0007.

745


SIGIR 2007 Proceedings

Poster

from the CSS distribution a n-dimension vector of real values is computed in which the i-th element is the number of concavities/convexities with a wideness greater than i ; - ·the irregularity/linearity of the boundary that can be approximately related to the Multi-Fractal Spectrum (MFS) of the shape contour [2]; - the presence on the boundary of global shape features that can be approximately described by the Fast Fourier Coefficients (FFC) [3]; All the three vectors of descriptors are invariant with respect to rotation and scaling of the shapes. Besides these shapes descriptors also some metric descriptors are computed, such as the area, the circularity and fractal dimension. These indexes can be used in the retrieval phase to pre-filter the shapes in the archive to minimize the set of items on which to evaluate the soft constraints on the shapes characteristics. This allows to reduce the cost of the retrieval function.

more extensive experiments are needed to conclude to which extent the approach is effective.

Fig. 3 Ranked shapes from top left to bottom right given the query at the top left (in red the shapes of a wrong category)

2. EXPERIMENTS
We conducted the evaluations on two collections: a collection of 1100 shapes of marine creatures, gently provided by the University of Surrey (UK) [5] and a collection of leaves with distinct shapes and irregularity of the contour, some of them artificially generated so as to emphasise the irregularity of the contour to test the effect of the different sets of descriptors. Fig. 4 Average R-P graphs by applying distinct retrieval functions and by considering six queries

3. CONCLUSION
The system is conceived for variety of applications in which it is necessary to store in the database shapes present in binary images and to retrieve shapes similar to those appearing in a visual query image. The novelty of our approach is the use of multiple indexing criteria of the shapes and its flexibility, i.e., the possibility to tune the retrieval criteria to a specific purpose, emphasizing the role of specific characteristics of the shapes in determining the retrieval results.

Fig 2: ranked leaves with FFC (above) and MFS (below): the colour distinguishes the contour regularity degree (red smoothest) Figure 2 reports the first eight ranked leaves (from left to right) by using only the FFC and the MFS respectively given the query at the left: it can be observed that with MFS we retrieve the leaves with decreasing irregularity of the contour, while with the FFC the ranking reflects a similarity of global shape features. We visually classified the marine creature into six classes according to the similarity of their silouette. We then submitted six queries by taking a fish from each category and performing the retrieval first on the basis of each single set of descriptors (FFC, CSS, MFS) and then by considering all the descriptors with the same weight, and with distinct weights emphasising some evident characteristics of the ideal shapes (in figure 3 we show the ranked list of shapes given the first top left shape as query and a retrieval function that takes into account all the indexing criteria with equal importance) . It can be seen how only 6 out of 50 shown shapes belong to a different category than the query category, and the first wrong element is 23rd position. In Figure 4 we report the average R-P graph for each applied retrieval function obtained by considering the six queries: it can be noticed how the single indexing criteria produce worse results than by considering all the criteria with either same weight or best weights. Further it can be noticed that the CSS criterion alone is very influent on the overall effectiveness. These preliminary results are encouraging, even if

AKNOWLEDGEMENTS
We want to thank the "Centre for Vision, Speech, and Signal Processing" of the Electronic and Electrical Engineering Dep. at Surrey University for providing the marine creatures collection.
4.

REFERENCES.

[1] Ghilardi L., Milesi S., Un sistema flessibile di retrieval di forme in immagini digitali binarie, tesi di laurea Bergamo University Informatics Engineering Dep., 2007. [2] A. Chhabra and R.V. Jensen. Direct Determination of the f(alpha) Singularity Spectrum. Physical Review Letters, 62, March 1989. [3] Dengsheng Zhang, Guojun Lu. A Comparative Study on Shape Retrieval Using Fourier Descriptors with Different Shape Signatures. Proceedings of the International Conference on Multimedia, 2001 [4] F. Mokhtarian, A.K. Mackworth. Theory of multi-scale, curvature based shape representation for planar curves. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-14 (1992) 789­805. [5] www.ee.surrey.ac.uk/Research/VSSP/imagedb/demo.html.

746