Research of clasterization and histogram attributes
opportunities for searching in picture databases

Abstract

Introduction

     The amount of images of the most different character constantly grows. The Internet and digital libraries give access to monstrous amount of the information. Reception of this information effectively is absolutely other question. For an example if it is necessary for user to find something, for example, a photo of a horse near water, unique hope today - that someone has already sorted such photos in advance.

     Experience of big archives of pictures shows, that it is practically impossible to predict such inquiries. Support of a new class of inquiries can demand revision of all collection of pictures, that, certainly, is extremely inefficient approach.

     Unique for today a way of the decision of this problem - algorithms of automatic recognition/analysis of pictures. In the given work the basic directions of research of a problem of the analysis of images, an estimation of efficiency of search, and a direction of the future work are resulted.

1. Existing systems of search of images in a DB

     1.1 QBIC - " query by image content ". System QBIC - the greatest system intended for search of images. Founders - IBM Almaden Research center. The system enables search under following characteristics:

• Average color
• Histogram color
• Structure
• Form
• Position
• Position of color on a picture
• Position of sides on a picture
  

     1.2 Photobook, system, constructed in Masachusetts university of technologies by Alex Pentland, basically takes all the ideas from system QBIC, but possesses an opportunity of division of a picture on segments, and works with a structure of a picture more precisely.

     1.3 Digital library Project. Development of university of Berkeley, from authors Ginger Ogle and Chad Carson, contains more than 600,000 pictures. More than 50,000 from them, including photos of surfaces and photos from air, are accessible online on official site Digital library Project. The system allows search not only on regions, color and histograms, but also by text inquiry. Unfortunately, amount of text inquiries to which the project adequately reacts, very little, but system actively develops.

2. Problem of contextual search of images

By search of images on their contents it is possible to allocate some problems: contextual search of images on their contents search on contents of areas inside of the image, spatial search-relative or absolute (the arrangement of areas inside of the image is considered), and also the search uniting all specified attributes. The interrelation of these approaches is illustrated on figure

Let's examine in more detail an essence of each of these approaches

Search on contents of the image assumes a finding in a DB of all those images which are most similar on the sample set in inquiry of the user. Difference of this technology from usual search that it assumes approximate search. It is possible to allocate two forms of such inquiry:

•      Search K of the images most similar on the sample. The images received as a result of performance of inquiry, are usually ordered on decrease of similarity on the sample of search.
•       Search of all images which differ from the sample of inquiry no more, than on the set size (threshold search). Such search is generally carried out more quickly, than previous.
  
  

     For fast comparison of images calculation of the attributes describing their contents, and indexing of a DB to these attributes is carried out. For example, in figure process of construction of the color histograms describing distribution of colors inside of the image, previous is shown to comparison of images. Except for the specified approaches based on global characteristics of images, use also the search considering attributes of separate areas of the image.

     At performance of spatial inquiry search of images on the basis of an arrangement in them of various objects is carried out. Thus images are compared to preliminary allocated areas or objects (see figure), without taking into account such characteristics of the image as color, a structure, etc. the Example of such inquiry is shown in figure. In figure (а) the sample of inquiry, in figure (б) - the image, satisfying is shown to the requirement of a relative arrangement of objects inside of the image, in figure (в) - the image, in which absolute arrangement of objects to close that is set in the sample.

Figure 1. Space request

     The spatial inquiry for search of images with a similar relative arrangement of areas consists that in a DB images in which at least R objects are characterized by the same relative arrangement are found, as well as R objects of picture-the sample. Absolute spatial search is performed by criterion function of distance D. In a DB there is K images, for which parity D (TQ, TF) where - some threshold value, and TQ, TF-sets of the allocated objects for the sample of inquiry and the image from a DB accordingly is fair.

2.1 Representation of characteristics of the image

     For representation as colors, and structures are used multivariate characteristics: color is defined as value in three-dimensional color space, a structure - as distribution of energy on nine space-to frequency channels. Values of attributes are transformed with the purpose of their representation in uniform space of vectors with 166 colors and 512 elements of a structure. For such representation of colors and structures of the image are used histograms and binary vectors. Such approach assumes a choice of the most suitable color space (by means of transformation T), the subsequent digitization of colors (by means of transformation Q) and a choice of the metrics for definition of a divergence of histograms. Now there is no common opinion about what color space is the best for representation of contents of images, and in practice various spaces of colors are used.

     For example, Swain and Ballard use for representation of colors system of coordinates with opposite directed axes, allowing to present 2048 colors. In system QBIC developed by IBM, RGB-space used is up to 4096 colors (16 levels on each component) then colors will be transformed to space Munsell by means of transformation МТМ. After that get out k the most significant colors (as a rule, k=64). Pass, Zabih and Miller simply use RGB-space, applying uniform digitization up to 64 colors. And, at last, Gray carries out transformation from RGB spaces in the beginning in CIE-LUV, and then carries out digitization up to 512 colors.

     As the requirements which are put forward to color space, it is necessary to name uniformity, completeness, compactness and naturalness. Such spaces allow representing color characteristics of the image by means of histograms and binary vectors.

     According to the requirement of uniformity the calculated similarity of colors should correspond to their perceived similarity. Thus calculation of similarity of colors should not be labour-consuming. This achieve transformation to such color space in which expression for calculation of similarity of colors is not function from coordinates in this color space. Transformation Т mainly determining uniformity of color space, together with digitization Q defines also its completeness and compactness. The space possessing property of completeness, includes all various perceived colors. Performance of this property is necessary for any color space, and visual completeness does not guarantee mathematical completeness, however the converse is true. Generally, if transformation Т is returnable the color space possesses completeness. Property of compactness of color space means, that its any color visually differs from the others.

     To limit dimension of representation of color characteristics of the image, or, that the same, the amount of colors, color space should not possess redundancy, that is to be compact. Mathematically absence of redundancy is reached, when transformation from space RGB under the scheme "one to one" or "many to one" is carried out. In the space, described absence of redundancy, should not be the colors visually perceived as identical. As a rule, at a choice of algorithm of digitization start with reasons of the compromise between completeness and absence of redundancy.

     In conformity with property of naturalness the color space assumes natural decomposition of color on three perceived components: brightness, a saturation and tone. Such representation of color is natural for the person. Ease in management of color space influences ability of the user to build the inquiries considering color of the image. Brightness is the component of visual perception - defining more light or dark shade. Change area - from shining up to matte. Tone is the component corresponding those, how much examined color is similar to one of perceived by the person: red, yellow, green and blue. The saturation defines greater or smaller concentration of tone. The saturation allows estimating a degree of difference of painted light from achromatic without taking into account its brightness.

     Transformations T and Q are under construction so that the listed properties were carried out all. These conditions, as a rule, are specific to each subject domain. For example, medical images and images of satellites demand use of the color spaces which are distinct from what are used for any images, for support of the specified properties. Originally the point is determined by coordinates of a vector in space RGB v = (r, g, b). Transformations Q and T process this vector with the purpose of construction resulting set from M colors.

Transformation of color Т is carried out above vector V RGB with the purpose of reception of the transformed vector w. The elementary is linear transformation of colors (for example, for RGB-spaces this transformation to spaces YIQ, YUV, YcrCb, OPP). To other color spaces (for example, HSV) transition is carried out by means of nonlinear transformations. As all color spaces are continuous, it is necessary to execute digitization of color space for reduction of quantity of colors.

3. Conclusions

The further investigation phases are:

•      Indexing of images, application method of histogram attributes and clasterization.
•      Possible sharing of both methods, estimation of their efficiency, and comparison.
•      Comparison of the received results with results last master works and other researches in the world

The list of the literature

1.      Integrated Spatial and Feature Image Systems: Retrieval, Analysis and Compression by John R. Smith.
2.      J. R. Smith and S.-F. Chang. Joint adaptive space and frequency graph basis selection. In Proc. Int. Conf. Image Processing. IEEE, June 1997. Submitted.
3.      Scientific American, June 1997. Searching for Digital Pictures, David A. Forsyth, Jitendra Malik, Robert Wilensky
4.      T. Caelli and D. Reye. On the classification of image regions by colour, texture and shape. Pattern Recog., 26(4), 1993.
5.      S.-K. Chang and T. L. Kunii. Pictorial data-base systems. IEEE Computer, November 1981.
6.      V. N. Gudivada and V. V. Raghavan. Design and evaluation of algorithms for image retrieval by spatial similarity. ACM Trans. on Information Systems, 13(2), April 1995.