Method of indexing and searching digital images. RU patent 2510935.

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to systems for indexing and searching digital images contained in files of different graphics formats. The method involves finding a colour having the shortest Manhattan length from the found predominant colour in the selected colour coordinate system from a predetermined set of primary colours, classified according to brightness, saturation and hue; using the obtained colour as an identifier for organising the search procedure in an image database; determining colour association from the basic set of primary colours to form a visual colour similarity and visual colour contrast characteristic; generating an image index (metadata) according to the presented primary colour in RGB format and/or name and/or tag of the colour; searching images in the database. As a result of the search, a list of images is formed, having indices matching the presented index and/or indices for which primary colours are present in the list of associations of visual similarity or in the list of colour contrast for the primary colour in the image search index.

EFFECT: faster automatic and semi-automatic indexation of images and faster search of images with similar predominant colours in a database.

9 cl, 4 dwg

The invention relates to the systems indexing and retrieval of digital images contained in files of various graphic formats, located on the local computer of the user, including in the global network Internet.

The proposed method can be widely used in search systems, and hardware-software systems for electronic Commerce (online stores), where you often need to make a search of the products from the database store in characteristics, not only defined in text form, but the resulting digital image analysis.

In the framework of implementation of the system are divided into two main tasks: determining the dominant colour of the image to save index (metadata) of the image in the information database and search for images containing similar predominant color in the database. The main color of the image is defined as the color that has the most pixels in the image. The main color of the image can be calculated by the methods of image analysis. Also the predominant color of the image can be selected from a list of predefined colors through the interaction of a computer operator with the software of management information database.

Known from the prior art methods for content-based indexing for search files in various formats, including graphics, which is estimated coincidence content by computing the hash from content [1]. The disadvantages of these methods may include the lack of image analysis, making images with similar predominant colors can be classified as a completely different image.

Known from the prior art methods for content-based image retrieval mainly compute the characteristic vector of values for each image and save it in the information database alongside the image itself. The search images by calculating the vector characteristic values for the presented image with the subsequent comparison of the sought vector with all the vectors from the database. At the exit procedures of search by the number of images that error coincidence of vectors with the target vector is the minimum (below threshold). Such methods may include, for example, the method described in [2]. The method uses the feature vector is histograms, built on the values of channel R, G, B, expressed RGB color model. Another method [3] uses a feature vector image values of histograms, built on the values of channel N and S, expressed in the HSV color model.

Near the technical nature of a way of search of digital images from a database of images [4], at which compute a histogram of the presented images and the histogram of the image stored in the database, then expect a degree of similarity of the images using the method of assessment of similarity of the two probability distributions (Kullback-Leibler divergence) [5]. Then the search results, rank according to degree of similarity from the input image.

The disadvantages of the prototype can be attributed computational complexity of calculation of histograms of the images with the subsequent calculation of metrics similarity. Another drawback of the prototype is the need for the input image to arrange for image retrieval from the database. The prototype analyzes the content of the image and outputs of procedure of the search results with the lowest error comparison of histograms. But this formulation not really suitable for e-Commerce (online shopping). The most common problem for systems of electronic Commerce is to find the product images in the database store goods at the specified color and categories. By using the prototype can be achieved result of not quite adequate to the task of searching of goods by selected color as the image histogram is built throughout the image area, including directly the subject (an item) along with the background, which can be heterogeneous. The distortions introduced in the histogram areas background, can make a significant error in the image search results by color.

The invention allows to solve this deficiency by setting POISKOVO request not as an image of the object (goods)and in the form of a color image, painted in the colors of a color set. While the inventive method of image search produces transformation search query expressed in graphical form (colour) in the search query expressed in text form as numbers and letters that has a significant impact on the speed of the search. The number-letter string describing the color image is called a tag. The sample images goes according comparison tags small length (of the order of 10-30 characters)that requires less computational costs compared with the calculation of similarity 8-bit histograms, consisting of 256 values per channel. When using the most common color space RGB need to compare 768=256·3 values for each of the hundreds or thousands of images stored in a database of images.

The prototype cannot be used to search for images of goods, given the associations harmony of colors, in which the procedure image search get a number of images that have the color, visual harmony between them.

Thus, the primary task of building systems for image search for e-Commerce is the task of searching for images according to the given color. Image attributes that describe the color, category images and other image parameters is called the index or image metadata. The index of the image stored in the information database. The index of the image should include, along with the tag the name of the color, which should more accurately be described color of the object in the image.

The problem is solved by developing a method for indexing (formation metadata) images with the subsequent formation database metadata of images and implementation of a procedure based metadata search images in the database, the method of indexation includes the following operations:

- define a basic set of primary colors in the format of an RGB color space;

- for each primary color format RGB of the basic set are the main color in the format of HSV, keep this Association, and for each primary color introduce the title and tag color;

- the original image is in RGB format;

- determine the predominant color image in RGB format,

- lead the predominant color the image in a format HSV;

- determine the main color of the image in the format of HSV of the basic set of primary colors HSV accordance with the predominant color image HSV;

- determine the main color image in RGB format according to the Association of a basic set of colors in the format of HSV basic set of colors in RGB format;

create index (metadata) of an image according to a specified a primary color in RGB, HSV, title and tag color;

- save index (metadata) of the image in the information database.

The developed method of image search (image metadata) formed in database of images includes the following operations:

- determine the Association's primary colors from a baseline for shaping the characteristics of degree of visual similarity and harmony of colors;

create index (metadata) query image search according to the presented a primary color in RGB format, and/or name and/or tag color;

- search for images (image metadata) according to the index (metadata) query image search and the search result form the list of images index, coincident with the submitted index and/or index which will match associations visual similarities and harmony of colours.

Fig 1. Block diagram, step by step implementation of the method of indexation (formation metadata) images according to the invention.

2. Block diagram phased implementation method image search according to the invention.

3. An example of a definition of dominant and primary colour image.

Figure 4. Search example images from the database according to the main color of the image.

Hereinafter the preferred embodiment of the invention is described in detail with the involvement of graphic materials. However, the scope of protection of the invention is not limited to the preferred option of performing the invention which can be implemented in various forms. The preferred option implementation, disclosed in the description, is only an example to reveal the essence and to help experts to fully understand the claimed invention.

Table. 1

Basic set of primary colors

Color name

Bright red

(255,0,0)

red saturated bright

Bright orange

(255,128,0)

(30,1,1)

orange saturated bright

Bright yellow

(255,255,0)

(60,1,1)

yellow rich bright

Bright green

(128,255,0)

(90,1,1)

green saturated bright

Bright green

(0,255,0)

(120,1,1)

green saturated bright

Bright blue-green

(0,255,128)

(150,1,1)

blue-green saturated bright

Bright cyan

(0,255,255)

(180,1,1)

cyan saturated bright

Bright blue

(0,128,255)

(210,1,1)

blue saturated bright

Bright blue

(0,0,255)

(240,1,1)

blue saturated bright

Bright purple

(128,0,255)

(270,1,1)

purple saturated bright

Hot pink

(255,0,255)

(300,1 .1)

pink saturated bright

Bright crimson

(255,0,128)

(330,1,1)

crimson saturated bright

Dark red

(102,41,41)

(0,0.6,0 .4)

red dark gray

Dark orange

(102,71,41)

(30,0.6,0 .4)

orange gray dark

Dark yellow

(102,102,41)

(60.0.6,0.4)

yellow dark gray

Dark-green

(71,102,41)

(90, 0.6,0 .4)

light green dark gray

Dark green

(41,102,41)

(120,0.6,0 .4)

green gray dark

Dark blue-green

(41,102,71)

(150,0.6,0 .4)

blue-green dark gray

Dark cyan

(41,102,102)

(180,0.6,0 .4)

cyan gray dark

Dark-blue

(41,71,102)

(210.0.6,0.4)

blue dark gray

Dark blue

(41,41,102)

(240,0.6,0 .4)

blue dark gray

Dark purple

(71,41,102)

(270,0.6,0 .4)

purple dark gray

Dark pink

(102,41,102)

(300,0.6,0 .4)

pink gray dark

Dark crimson

(102,41,71)

(330,0.6,0 .4)

crimson dark gray

Separately notice that the color model for the base color does not change the essence of the invention and depends only on usability to create a system of indexation of digital images.

To define a basic set of primary colors, presented in the form of HSV color space, the N, S, and V may be divided into intervals for the convenience of choosing the basic colors when changing their number. The intervals for the description of the interval can be assigned names in the form of tags (Table. 2). Hereafter, the terms color channel and the coordinates of the color space have the same value. The term "color" is used mainly in the description of the reference system in the selected color space, whereas the term color coordinate" is used in the context of the coordinates in your selected report.

For channel Hue number of intervals ask how the N HUE . Under uniform breaking channel Hue each interval will have a length expressed as I HUE /N HUE , HUE where I is the maximum value for channel Hue (HUE where I =360 degrees).

For channel Saturation number of intervals ask how the N SAT . Under uniform breaking channel Saturation each interval will have a length expressed as I SAT /N SAT where I SAT maximum value for channel Saturation (where I SAT =1 when using the normalized value).

For channel Value is the number of intervals ask how the N VAL . Under uniform breaking channel Value each interval will have a length expressed as VAL I /N VAL , where VAL I - the maximum value for the channel Value (where I VAL =1 when using the normalized value).

For each the main color of the basic set of coordinate of N base color is chosen as the value of N from the intervals at which shares the Hue channel; the coordinate S primary color is chosen as the value S of the intervals at which shares the channel Saturation; coordinate V of the base color is chosen as the value of V the intervals at which shares the channel Value. In Table. 2 shows a breakdown of channels Hue, Saturation, Value at intervals. Also the table shows the values of primary colors, set within the selected range. To illustrate the performance of the method for each primary color select Hue as the middle of interval maps of the interval channel Hue. However, for channels Saturation and Value the values of the primary colors do not match the means of desired intervals.

To determine achromatic colors (colors with a small value of saturation) basic set enter the threshold T S for the values of channel Saturation and threshold T V channel values Value. They regard as the main color achromatic, if the value of the coordinates Saturation less T S and coordinate value Value is less T. V .

To simplify indexed images and groups of images in step 101 ways indexing digital imaging introduce the Association of values primary colors with the name of the color, and also with the tag. Thus the name of the color you use to interact with humans in a graphical user interface. In turn tag is used for organizing the procedure of search. Category tags may be selected as characterizing the primary colors brightness (intensity), and/or color, and/or color saturation. In Table. 1 examples of tags defined in accordance with the hue, brightness and saturation. Tags are made by a combination of tags intervals of the Table. 2.

After translating the input of the digital image in RGB format at step 103 determine the main color of the image 100 expressed in RGB color space. Being the dominant colour for automatic indexing of images in the information database of conduct by using the software, the computer operator puts the image in the database, then by clicking in the selected area of the image indicates the color of any pixel count prevailing color image. You can do without participation of the operator and as the desired area of the image to read the center of the image with coordinates (x-im /2, y im /2), where x im - image width, in pixels, y im - image height in pixels. At that, the center of Cartesian coordinates (X and Y) is placed in the upper left corner of the image. In turn, the X axis is directed horizontally from left to right, and the Y axis is directed vertically down.

The images presented in digital form, can often contain much noisy area because of signal processing in the camera and further processing and/or compression. Noisy image area is understood as areas in which the individual pixels have values very different from the mean in the given area of the image. To reduce the effect of noise on the result of determining the dominant colour perhaps the use of digital filtering image pixel area around the selected pixel. Filtering can be performed using the Gaussian. Job description digital filtering using the Gaussian it is not presented here due to the popularity of this method from the current level of technology. Any method of digital filtering can be applied to eliminate the effect of the image noise. The choice of the method of filtering does not affect the meaning of the invention. Under the area of pixels to understand a group of pixels in the immediate vicinity of a given pixel with coordinates (x, y). Area pixel is usually asked in a rectangular area of the image window with the coordinates of the upper left corner (x-x w /2,w /2) and the lower-right corner (x+x w /2,u+w /2). While x w - the width of the rectangular window in pixels, y, w - height of the rectangular window in pixels. The above method of selection window filtering is purely illustrative. The choice of the form window filter does not change the essence of the invention. I want to note that the choice of method of filtering falls on the shoulders of the developer system image indexing and does not change the essence of the invention.

After determining the dominant colour of the image portrayed in the RGB color space in step 104 method of indexation of digital images define the main color of the required image according to the basic set of primary colors. To do this, RGB is the dominant colour transform in HSV color space. For received HSV values to calculate the distance of Manhattan (1 norm) from each primary color of the base set according to a formula 1

- absolute value of the difference of coordinates of Hue for the dominant colour P {R hue , P sat , P val } and the main color Of {hue , O sat , O val };

- absolute value of the difference coordinates Saturation for the dominant colour P and the main color On;

- absolute value of the difference of coordinates of Value for the dominant colour P and the main color O.

Thus the range of values of the coordinates of Hue from 0 degrees to 360 degrees normalized in the range from 0 to 1. The function of the standard can be as in the formula 2.

So use the following formula (equation 3) to calculate the distance between colors in HSV color space

Main color presented image define a core set of basic HSV color as the color which has the least distance of Manhattan Δ hsvN (formula 3) made HSV values. Then get the value of the primary colors in RGB format of Association set the primary colors of the RGB and HSV. An example of associations primary colors listed in table 1

After defining the main color of the image portrayed in the RGB color space in step 105 method of indexation of digital images form the index (metadata) image 107. The search index is used as an identifier when searching for images in the database. Along with information about popular image color image index may contain information about the image file, such as system path to the image file. This index may also contain information about the image parameters photo (obtained for example from the EXIF metadata of the image file) and any other information characterising the image, for example to which category of products is subject, recorded on the image.

After the formation of the index (metadata) of the image in step 106 way of indexing images retain the index presented image in the information database. Along with keeping the index of images in the database, you can also save the image in the database as a byte array.

Table. 3

The Association's primary colors from the underlying collection

Color name

Association for the shade

Association contrast

Bright red

Darkred, Light red

Bright green

Bright orange

Bright yellow, Dark yellow, Light orange

Bright purple

Bright yellow

Bright orange, Dark yellow, Light yellow

Bright blue

Bright blue

Bright blue, Light blue, Dark blue

Hot pink

Bright blue

Bright blue, Lightblue

Bright yellow

Bright purple

Light violet, Dark violet

Bright orange

The example of the method of indexing images as part of the software of a control system of the database is shown in Figure 3. According to Figure 3, the operator of the database can set the categories of goods to which belong loaded into the database image. In addition to selecting categories, the software allows you to identify dominant and primary color in the image. The main color of the RGBA={252, 22, 54, 255} was automatically calculated by filtering center area of the image with a radius of a few pixels. At that, the main color of the image has been defined as "Krasny Svetlany" according to the described method of indexing the image.

The block diagram of the way search for images (image metadata) in the generated database of images presented in figure 2. According to Figure 2 in step 201 ways determine the Association's primary colors from a baseline for shaping the characteristics of degree of visual similarity and harmony of colours. An example of associations for some colors are presented in Table. 3.

After determining the associations basic colors of a basic set in step 202 ways image search form index (metadata) query image search according presented a primary color in RGB format, and/or name and/or tag color (200).

After the formation of the index in step 203 ways of finding images searches for images (image metadata) according to the index (metadata) query image search and the search result form the list of images (204) index, coincident with the submitted index and/or indexes that will match associations visual similarities and harmony of colours.

The example of the method for image search as part of the firmware web interface (a web page that is hosted on the Internet) the e-Commerce system is shown in Figure 4. According to Figure 4, the user web interface, select the desired color to search through a click on the color selection area (rectangle left top with rainbow scale). Ckicking on rainbow scale is the job of the desired shade, in turn by clicking the mouse on a rectangular area select the desired brightness and saturation. After that, the web interface displays the list of images of the goods according to your search criteria. Figure 4 shows the result of search according to the given base color without specifying categories of goods (for example, blouse, dress and so on).

The invention can be used as a software-hardware systems of electronic Commerce, in which the web user interface for selection of goods includes goods search not only for categories, but also find images goods, indicating the desired color of the goods. We can also implement image search products according to the set associations harmony of colors that can be very useful, for example, in e-Commerce systems clothes and shoes.

Literature

[1] WO 2005/033885, "oriented Content index and search method and system", 14.04.2005.

[2] "Image Retrieval using Color and Shape", Anil K. Jain and Aditya Vailaya, Pattern Recognition, 29 (8), 1996.

[3] "Supporting Similarity Queries in MARS", Michael Ortega et al., ACM Multimedia 97.

[4] US 6163622 "Image retrieval system", 19.12.2000.

[5] http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler _ divergence.

[6] http://ru.wikipedia.org/wiki/RGB.

[7] http://m.wikipedia.org/wiki/HSV_(tsvetova _ model).

1. The method of indexation of digital images, which analyze digital representation of images to create the index (metadata) graphics describing the main color of the image, and use it as an identifier for the organization of the procedures of search images, wherein define a basic set of primary colors in the format of the HSV color space; - specify the name and the color tag for each primary color is the main color of the base set is defined as achromatic, if the channel value Saturation less than a specified threshold T S and if the value of the channel Value is less certain threshold T V ; - the original image is in RGB format; - determine the predominant color image in RGB format; - make the transformation of the dominant colour image from RGB format HSV; - determine the main color image format HSV of the basic set of primary HSV color as the color which has the least distance Manhattan (1 rate) made HSV values, where are the absolute differences of the coordinates of the Hue, Saturation and Value, respectively; - make the conversion of primary colour picture format HSV to RGB format; create index (metadata) of an image according to a specified a primary color in RGB, HSV, title and tag color; - retain index (metadata) of the image in the information database;

2. The method according to claim 1, characterized in that the list of tags are classified according to categories characterizing the primary colors brightness (intensity), and/or color, and/or color saturation.

3. The method according to claim 1, characterized in that the dominant RGB color image determined by the choice of a pixel with the corresponding coordinates.

4. The method according to claim 1, characterized in that the dominant RGB color image is defined as the result of digital filtering selected area pixel with the corresponding coordinates.

5. The method according to claim 4, wherein as a function of digital filtering use the function of the Gaussian.

6. The method according to claim 1, characterized in that, for each primary color of the basic set of coordinate of N base color is chosen as the value of N from the intervals at which shares the Hue channel, while the number of intervals for channel Hue is defined as N HUE ; the coordinate S primary color is chosen as the value of S the intervals at which shares the channel Saturation, while the number of intervals for channel Saturation defined as N SAT ; coordinate V of the base color is chosen as the value V of the intervals at which shares the channel Value, while the number of intervals for the channel Value is defined as N VAL .

7. The search method of digital images using the ID of the image index (including information about the main color image in RGB format, the tag and the name of the color), wherein determine the Association of colors from the underlying set of basic colors for the formation of characteristics visual appearance of colors; - determine the Association of colors from the underlying set of basic colors for the formation of the characteristics of the visual contrast of colors; create index (metadata) of the image according presented a primary color in RGB format, and/or name and/or tag color; - search for images in the information database is formed according to the index of the image in the search result form the list of images index, coincident with the submitted index and/or the indices, which have the primary colors are present in the list of associations visual similarity or in the list of contrast colors for foreground color in the search index images.

8. The method according to claim 7, wherein the information database of digital images stored on the server in a global network the Internet.

9. The method according to claim 7, wherein the database access is performed via a web interface (a web site hosted on the global Internet), which is used by a user to form a specific search query in the information database of images.