Metrical Properties of Nested Partitions for Image Retrieval

Metrical Properties of Nested Partitions for Image Retrieval

Dmitry Kinoshenko (Kharkiv National University of Radio Electronics, Ukraine), Vladimir Mashtalir (Kharkiv National University of Radio Electronics, Ukraine), Vladislav Shlyakhov (Kharkiv National University of Radio Electronics, Ukraine) and Elena Yegorova (Kharkiv National University of Radio Electronics, Ukraine)
DOI: 10.4018/978-1-61692-859-9.ch002


This chapter proposes a metric on partitions of arbitrary measurable sets and its special properties for metrical content-based image retrieval based on the ‘spatial’ semantic of images. The approach considers images represented in the form of nested partitions produced by any segmentations. Nested partitions representation expresses a degree of information refinement or roughening and so not only corresponds to rational content control but also ensures creation of specific search algorithms (e.g. invariant to image background) and synthesize hierarchical models of image search reducing the number of query and database elements match operations.
Chapter Preview


As a promising and active research problem, the study of content-based information retrieval has been focused on such approaches as search by association, aimed search and category search. Somehow or other, any retrieval scheme is based on a query matching. There exist various querying modalities on qualitative level: given keywords, free-text (metadata) inducing by summarizing, datum exemplum, computer-generated or man made rough sketches, composite models. Different query forms require different processing methods but in any case measures of similarity (dissimilarity) are the kernel issues to assess on the base of data abstracted descriptions the certain semantic indistinguishability between a pair of media occurrences generally from large databases. It is clear that different distance measures have their own advantages and disadvantages but prospective key problem is to understand the semantics of a query, not simply the low-level underlying computational features. Synergy between machine learning and multimedia retrieval expresses in different ways. It should be emphasized automatic learning of a similarity metric or distance from ground-truth data, machine learning using both quantitative and qualitative responses for generation of relevance feedback-based search and learning algorithms ability to adapt and compensate for the noise and clutter in real contexts (Ma, 2009). Similarity measures have to be possessed of following main properties: agreement with semantics must be satisfactory for task-level system, robustness to noise and media transforms has to satisfy user requirements, computational complexity must provide approximate real time in large scale database, invariance to different backgrounds must allow to retrieve objects of interest. Further we shall focus an attention on content based image retrieval or more precisely on its core substantially defining effectiveness CBIR viz aspects of possible metrical interpretations of image content from segmentation point of view.

The elucidation of image content is complex and delicate even for human understanding (see e.g. Figure 1) so questions how to extract useful image features and how to use them for valid retrieval are of great importance. Thus, visual similarity may be problematic due to the semantic gap between low-level content and high-level concepts.

Figure 1.

Assessments of visual content: edge image (on the left), binary image (on the right)

Comprehensive studies have been carried out with similarity between images given by image features such as color, texture, or shape and on the composition of these features. A number of region based retrieval systems are well investigated also (Lew at al 2006; Datta et al. 2008).

All similarity measures may be classified from the position of fulfillment axioms identity, symmetry and triangle inequality. If all axioms hold we have a metric, if an identity transforms to reflexivity, i.e. similarity equals to zero when comparing elements are the same, we get pseudometric. If symmetry is not valid we are dealing with a quasimetric. If triangle inequality does not hold we can operate a semimetric. If only reflexivity and triangle inequality are true we get a hemimetric. If triangle inequality is strengthened (instead of distances sum their maximum is used) we have an ultrametric. At last, if only reflexivity occurs we obtain a prametric. Certainly, all foregoing measures may be used in CBIR but we strongly need all axioms satisfying. Uppermost metric is most intuitive to compare arbitrary data comprehensively. Further, that is self-evident that to locate user-relevant information in large collections of objects, fast algorithms of exact match or adequate proximity concepts can be grounded on a metric solely. A metric provides specialized search mechanisms which allow to eliminate iteratively inconsistent data subsets (Zezula et al. 2006). The obvious additional advantage of metric search is that the results can be ranked according to their estimated relevance.

Complete Chapter List

Search this Book: