WO2014045075A1

WO2014045075A1 - Method and a device for visualizing information related to similarity distance computed between two images

Info

Publication number: WO2014045075A1
Application number: PCT/IB2012/002176
Authority: WO
Inventors: Régis BEHMO; Fabien FRELING; Yannick ALLUSSE; Simon Dolle
Original assignee: LTU Technologies SAS
Current assignee: LTU Technologies SAS
Priority date: 2012-09-21
Filing date: 2012-09-21
Publication date: 2014-03-27
Anticipated expiration: 2015-03-21

Description

Method and a device for visualizing information related to similarity distance computed between two images

The present invention relates generally to a method and a device for visualizing information related to similarity distance computed between two images.

With the advent of Internet and digital cameras, the amount of pictures available to professionals as well as the amateurs has exploded. The movement even accelerated with the Web 2.0 wave that has allowed every internet user to share its photographs online. In parallel with this explosion the need to organize these new databases has raised.

Different kinds of algorithms have been developed to address this problem. Some of them are able to detect image copies and are used to avoid duplication in databases or to detect copyright infringement. Some algorithms are less strict than copy detection algorithms and are able to quantify the amount of similarity between two images.

Algorithm which quantify similarity between two images sometimes deliver surprising results. For instance two visually close images may be considered as very different by the algorithm or on the contrary, two distinct images may be considered as similar. In this case, it is interesting to understand why the algorithm has returned these surprising results. This may allow the developers to detect bug in the algorithm, improve the algorithm implementation, or to give advice to a user on the optimal way to index its specific image database, or to give the user a better understanding of the algorithm internals.

The present invention aims at providing a method and a device which enable to understand why an algorithm which quantifies similarity between two images returns such results.

To that end, the present invention concerns a method for visualizing information related to similarity distance computed between two images, characterized in that the method comprising the steps of :

- displaying the images,

- displaying a decomposition of the similarity distance into plural classes,

- receiving a command for selecting one of the classes,

- retrieving pixels of the images which correspond to the selected class,

- modifying the display of the retrieved pixels on each of the displayed images. The present invention concerns also a device for visualizing information related to similarity distance computed between two images, characterized in that the device comprises :

- means for displaying the images,

- means for displaying a decomposition of the similarity distance into plural classes,

- means for receiving a command for selecting one of the classes,

- means for retrieving pixels of the images which correspond to the selected class,

- means for modifying the display of the retrieved pixels on each of the displayed images.

Thus, it is possible to understand why an algorithm which quantifies similarity between two images returns such results.

The present invention enables the developers to detect bug in the algorithm, its implementation, to improve the efficiency of algorithms which quantify similarity or to enable a user on the optimal way to index its specific image database.

According to a particular feature, the similarity distance is determined from a colour distance. Thus, the present invention is adapted to cases wherein colour similarity is the major criterion for similarity analysis. This is for example the case when, the algorithm is used for searching items like a clothe or a car of a given colour in a merchandising website.

According to a particular feature, the similarity distance is further determined from a shape and texture distance.

Thus, the similarity distance is more accurate.

According to a particular feature, the method comprises further step of :

- displaying at least one pattern enabling a selection of the colour distance or the shape and texture distance,

- receiving a command for selecting the colour distance or the shape and texture distance,

- displaying the decomposition of the colour distance into different classes or displaying the decomposition of the shape and texture distance into different classes according to the received command for selecting one of the distances.

Thus, it is more easy for the user or the developer to understand which part of the similarity distance calculation has default or which indexing of images could be improved or which similarity distance is the best suited to his need.

As result, similarity distance calculation may be improved.

According to a particular feature, if the received command is a command for selecting the colour distance, the method comprises further step of displaying the colour corresponding to the selected contribution.

Thus, the user can easily understand what in the colour similarity calculation or what in the indexing process needs to be improved or is providing good results.

According to a particular feature, the received command is a command for selecting the shape and texture distance, the display on each of the displayed images of the retrieved pixels is performed according to the sign of the selected class.

Thus, it is possible to identify which regions have been detected as similar between the two images, and to quantify their similarity.

The present invention also concerns, in at least one embodiment, a computer program that can be downloaded from a communication network and/or stored on a medium that can be read by a computer or processing device. This computer program comprises instructions for causing implementation of the aforementioned method, or any of its embodiments, when said program is run by a processor. The present invention also concerns an information storage means, storing a computer program comprising a set of instructions causing implementation of the aforementioned method, or any of its embodiments, when the stored information is read from said information storage means and run by a processor.

The characteristics of the invention will emerge more clearly from a reading of the following description of an example embodiment, the said description being produced with reference to the accompanying drawings, among which :

Fig. 1 is an example of a device for visualizing information related to similarity distance computed between two images;

Fig. 2 is an example of an algorithm for determining similarity distance computed between two images;

Fig. 3 is first example of a first screen displayed by the present invention;

Fig. 4a is an example of an algorithm for visualizing information related to similarity distance computed between two images when the similarity distance is determined only from colour distance or when a user selects colour distance mode.

Fig. 4b is an example of an algorithm for visualizing information related to similarity distance computed between two images when the similarity distance is determined from shape and texture distance;

Fig. 5 is a second example of a screen displayed by the present invention.

Fig. 1 is an example of a device for visualizing information related to similarity distance computed between two images.

According to the shown architecture, the device 10 comprises the following components interconnected by a communications bus 101 : a processor, microprocessor, microcontroller or CPU {Central Processing Unit) 100; a RAM {Random-Access Memory) 103; a ROM {Read-Only Memory) 102; a hard disk 104 or any other device adapted to store images, a display 106 and an input interface 105.

CPU 100 is capable of executing instructions loaded into RAM 103 from ROM 102 or from an external memory, such as an SD card. After the device 10 has been powered on, CPU 100 is capable of reading instructions from RAM 103 and executing these instructions. The instructions form one computer program that causes CPU 100 to perform some or all of the steps of the algorithms described hereafter with regard to Figs. 2 and 4. Any and all steps of the algorithms described hereafter with regard to Figs. 2 and 4 may be implemented in software by execution of a set of instructions or program by a programmable computing machine, such as a PC {Personal Computer), a DSP {Digital Signal Processor) or a microcontroller; or else implemented in hardware by a machine or a dedicated component, such as an FPGA {Field- Programmable Gate Array) or an ASIC {Application-Specific Integrated Circuit).

In other words, the device 10 includes circuitry, or a device including circuitry, causing the device 10 to perform the steps of the algorithms described hereafter with regard to Figs. 2 and 4.

From the input interface 105, the CPU 100 receives commands from a user for selecting data displayed on the display 106.

It has to noted here that the display 106 may not be included in the device 10 and may be link to the device 10 through a communication link.

According to the invention, the device 10 comprises:

- means for displaying two images,

- means for displaying a decomposition of the similarity distance into different classes,

- means for receiving a command for selecting one of the classes,

Fig. 2 is an example of an algorithm for determining similarity distance computed between two images.

At step S200, the CPU obtains a first image Ii from the hard disk 104. The first image is for example a reference image to be compared to other images.

At next step S201 , the CPU obtains a second image I₂ from the hard disk 104. The second image I₂ is for example one of the other images.

At next step S202, the CPU 100 computes a Bag-of-Co lours. The Bag-of- Colours feature is computed as described in the paper of Wengert & Douze, entitled "Bag-of-Colors for improved image search." and published in Proceedings of the 19th ACM, 201 1 or in a particular case wherein the blocks used in above mentioned paper are resumed to one pixel. A palette P is a finite set of distinct colours of size N. Each element c; of P, with i=l to N, is called a palette colour and is identified by an index. In a preferred implementation, the palette is learnt from a large set of images thanks to a K-Means algorithm and N is set to 64.

In this algorithm, colours are represented, for example in a CIE-Lab colour space and the distance between two colours is computed thanks to a L₂ distance also known as Euclidean distance.

A Lab color space is a colour-opponent space with a first dimension for lightness and second and third dimensions for the color-opponent.

In the paper entitled "Photoelectric Color-Difference Meter" of Hunter published in the Proceedings of the Winter Meeting of the Optical Society of America, Hunter introduced Color space coordinates.

CIE Lab introduced on nonlinearly compressed CIE color space coordinates in

1976.

The difference between Hunter and CIE colour coordinates is that the CIE coordinates are based on a cube root transformation of the colour data.

For each pixel of the image, the algorithm looks for the closest palette colour. The pixel is assigned to this palette colour. Then for each colour c; the algorithm counts how many pixels boc(i) have been assigned to each palette colour and builds the histogram boc of the boc(i).

The algorithm weights each of the histogram classes to give more weight to the least frequent palette colours to get the histogram boc_v

Boc_v(i) = Vi * boc(i)

where each Vi, with i= l to N is predetermined or is computed offline. In a preferred implementation, each v; is the inverse document frequency (i.e idf) of the palette colour and is computed in a large set of images.

The inverse document frequency is a numerical statistic which reflects how important a colour is to a document in a collection or corpus.

Finally the histogram boc is normalized to a norm of 1 according to norm Li. Li distance is the taxicab metric also known as rectilinear distance.

The Bag-of-Colours features computed on image is named boci, the Bag-of- Colours features computed on image I₂ is named boc₂.

At next step S203, the CPU 100 stores for each pixel of image L and of image I₂, the index of the colour in the palette to which it has been assigned. At next step S204, the CPU 100 computes a VLAD vector. The VLAD vector is computed as described in the paper of Jegou; Douze & Schmid, entitled "Aggregating local descriptors into a compact image representation" and published in Proceedings of the 23rd IEEE Conference on Computer Vision & Pattern Recognition(CVPR) , 2010.

The CPU 100 detects a set of regions R in the image. In a preferred implementation the algorithm uses a dense interest point detector.

For each region r E R, CPU 100 computes a d-dimensional descriptor desc(r). In a preferred implementation, the CPU 100 uses a descriptor of dimension d = 128 as disclosed in the paper of Heikkila, Pietikainen and Schmid, entitled "Description of Interest Regions with Center-Symmetric Local Binary Patterns" and published in Springer Berling, 2006.

The CPU 100 uses a codebook C. The codebook is a finite set of distinct descriptors of size N. Each element w; of C is called a visual word and is identified by an index. In a preferred implementation, the codebook is learnt from a large set of images thanks to a K-Means algorithm and N=128.

The CPU 100 computes the distance L₂ between desc(r) and each visual word w of the codebook. The index i of the closest visual word is called NN(desc(r)) and determines a raw VLAD matrix V which is a matrix V_f of dimension d x N such that:

By extension Vi is the line of index i. The vector obtained by reshaping the VLAD matrix into a vector is called the VLAD vector.

Then CPU 100 normalizes the resulting vector to norm 1 according to L₂ norm.

The resulting vector is named V. We call normalization vector

( 0 otherwise J

At next step S205, the CPU 100 stores in addition to each normalized VLAD vectors Vi and V₂, and for each region, the region position and the region dimensions, as well as NN(desc(r)) and p(r) = desc(r)— w_NN(^_desc^ Finally the CPU 100 stores the normalization vectors -L = n(V^) and ₂ = w(V₂).

At next step S206, the CPU 100 performs a colour distance computation. The colour distance computation consists in computing the Li distance between boci and boc₂. The resulting distance is named d_coi_OUr. According to a particular feature, the CPU 100 performs at step S207 a shape and texture computation.

The shape and texture distance computation is the L₂ distance between Vi and V₂. The resulting distance is named d_sh_ape.

At next step S208, the CPU 100 performs a similarity distance computation. The similarity distance is computed as a linear combination of d_coi_OUr and d_sh_ape. d similarity ^ colour- ^-colour shape - d shape^■

In a preferred implementation c_coi_OUr = c_sh_ape = 0.5.

If only colour distance computation is performed, c_coi_OUr =1 and c_sh_ape = 0.

At next step S209, the CPU 100 commands the displaying of the image Ii and the image I₂ as shown in Fig. 3.

Fig. 3 is first example of a first screen displayed by the present invention.

Fig. 3 shows a first screen 300 which comprises in an image display area 301 the first image Ii noted 302 and the second image I₂ noted 303.

At next step S210, the CPU 100 commands the displaying of the similarity distances in the similarity area 304 of the screen 300. The similarity area 304 comprises the similarity distance value d_simii_arity as well as the colour distance value dcoiour and the shape and texture distance value d_sh_ape. For example, the similarity distance value dsimiiarity is equal to 2.0, the colour distance value d_coi_OUr is equal to 1.5 and the shape and texture distance value d_sh_ape is equal to 2.5.

At next step S211, the CPU 100 commands the displaying of analysis mode switches 305 if both colour distances values and shape and texture values are used for determining the similarity distance.

In Fig. 3, two switches are displayed. It has to be noted here only one toggle switch may be displayed.

At next step S212, the CPU 100 command the displaying of the colour frame which comprises the palette of 64 colours.

At next step S213, the CPU 100 commands the displaying of a display navigation frame 307.

At next step S214. The CPU 100 commands the displaying of a decomposition of the similarity distance into plural contributions.

For example, the decomposition of the similarity distance is an histogram composed of bars. Fig. 4a is an example of an algorithm for visualizing information related to similarity distance computed between two images when the similarity distance is determined only from colour distance or when a user selects colour distance mode.

The present algorithm is executed automatically by the CPU 100 when the similarity distance is determined only from colour distance or when a user, using analysis mode switches 305, selects colour distance mode,

At step S400, the CPU 100 retrieves a colour distance histogram from boci and boc₂.

For that, the CPU 100 retrieves data stored at step S203.

At next step S401 , the CPU 100 commands the display of the histogram of colour. The way the histogram is displayed lets the user easily identify for which indexes boci and boc₂ have similar or dissimilar values, for example using superimposed bars of different colours for boci and boc₂ as shown in Fig. 3.

For the sake of simplicity only a part of the bars of the histogram of colour are displayed in Fig. 3. In practice, there is one bar for each colour of the palette of colours.

For example, bars related to boci are in black and bars related to boc₂ are hashed.

At next step S402, the CPU 100 checks if a bar of the displayed histogram is selected by the user.

The user selects a bar of histogram by selecting using the button "previous bar" or the button "next bar" displayed in Fig. 3 or by pointing, for example with a mouse, one of the bars.

If a bar of the displayed histogram is selected by the user, the CPU 100 moves to step S403. Otherwise the CPU 100 returns to S402.

Fig. 5 is a second example of a screen displayed by the present invention.

In the example of Fig. 5, the bar noted 510 is selected by the user.

At step S403, the CPU 100 retrieves the pixels which have the index of the selected bar 410 in the histogram.

At step S404, the CPU 100 highlights the selected bar as shown in Fig. 5.

At next step S405, the CPU highlights the pixels 512 in image Iml noted 502 in Fig. 5 and the pixels 513 in image Im2 noted 503 which correspond to the retrieved pixels. At the same step the CPU 100 commands the displaying of the similarity distances in the similarity area 504 of the screen 500. The similarity area 404 comprises the colour distance value d_coi_OUr.

At the same step the CPU 100 highlights the color palette that corresponds to the selected color in the color frame 306.

After that, the CPU returns to step S402.

Fig. 4b is an example of an algorithm for visualizing information related to similarity distance computed between two images when the similarity distance is determined from shape and texture distance.

The present algorithm is executed automatically by the CPU 100 when a user, using analysis mode switches 305, selects shape and texture distance mode,

At step S410, the CPU 100 retrieves a shape and texture distance histogram. The histogram frame displays a bar histogram that represents the contribution of each visual word of the codebook to d_sh_ape. The computation of the values of the histo gram is as fo Hows :

dshape = \\V-L ^~ V₂ \\

As Vi and V₂ have a L₂ norm of 1,

d_s ² _hape = 2 - 2{V , V₂ )

As

{v , v₂) = ^ ( ¾,w)

wee

(Vi,w_> ^2,w) ^1S representative of the contribution of the visual word w to d_sh_ape and is called the contribution of w to d_shape .

For that, the CPU 100 retrieves data stored at step S205.

At next step S411, the CPU 100 commands the display of the histogram of shape and texture.

At next step S412, the CPU 100 checks if a bar of the displayed histogram is selected by the user.

The user selects a bar of the displayed histogram by selecting using the button "previous bar" or the button "next bar" displayed in Fig. 3 or by pointing, for example with a mouse, one of the bars.

If a bar of the displayed histogram is selected by the user, the CPU 100 moves to step S413. Otherwise the CPU 100 returns to S412. At step S413 , the CPU 100 retrieves in images Imi and Im₂, the pixels corresponding to the selected bar.

(Vi_,i, V_2ii ) = n_u. V_2ii. ^ p(r) = n_2ii. V_u. ^ p(r)

r e R₁,WW(desc(r))=i r e R₂,NN(desc(r))=i dshape can be decomposed as a sum over individual region contributions.

For r E l , the contribution of r to the similarity score with respect to visual word Wi is defined as follow:

c (_r) _ f ⁰ NN(desc r))≠ i

1 \n_{2 i}. V_{l i}. p(r) otherwise

If r £ I₂, the definition of C_j(r) can be easily deduced from the previous case.

Thanks to the information stored at step S205, the CPU 100 knows the p(r). For each pixel, the CPU 100 computes the contribution of the pixel to the similarity distance with respect to the visual word w;. The contribution of the pixel is the sum of all the contributions of the regions the pixel belongs to with respect to Wi.

At next step S414, the CPU 100 highlights the selected bar.

At next step S415, the CPU commands the highlight of the pixels in image Imi and the pixels in image Im₂ and the display on each of the displayed images of the retrieved pixels is performed according to the sign of the contribution of the pixel with respect to the selected class.

For example, for each highlighted pixel, its colour depends of the sign of the pixel contribution to the similarity distance with respect to the selected class. If the pixel contribution is positive, pixel has a green colour, if the pixel contribution is negative, pixel has a red colour, if the pixel contribution is null, the pixel has no colour. The intensity of the pixel overlay is then proportional to the absolute value of the contribution. It is possible to identify which regions have been detected as similar between the two images, and to quantify their similarity.

At the same step the CPU 100 commands the displaying of the similarity area

404 which comprises the colour distance value d_coi_OUr. After that, the CPU returns to step S412.

Naturally, many modifications can be made to the embodiments of the invention described above without departing from the scope of the present invention.

Claims

1. Method for visualizing information related to similarity distance computed between two images, characterized in that the method comprising the steps of :

- displaying the images,

- displaying a decomposition of the similarity distance into plural classes,

- receiving a command for selecting one of the classes,

- retrieving pixels of the images which correspond to the selected class,

- modifying the display of the retrieved pixels on each of the displayed images.

2. Method according to claim 1, characterized in that the similarity distance is determined from a colour distance.

3. Method according to claim 2, characterized in that the similarity distance is further determined from a shape and texture distance.

4. Method according to any of the claims 1 to 3, characterized in that the method comprises further step of :

5. Method according to claim 4, characterized in that if the received command is a command for selecting the colour distance, the method comprises further step of displaying the colour corresponding to the selected contribution.

6. Method according to claim 4, characterized in that if the received command is a command for selecting the shape and texture distance, the display on each of the displayed images of the retrieved pixels is performed according to the sign of the selected class.

7. Method according to any of the claims 1 to 6, characterized in that the decomposition of the similarity distance is an histogram and in that the classes are bars of the histogram.

8. Device for visualizing information related to similarity distance computed between two images, characterized in that the device comprises :

- means for displaying the images,

- means for receiving a command for selecting one of the classes,

9. A computer program characterized in that it comprises program code instructions which can be loaded in a programmable device for implementing the method according to any one of claims 1 to 7, when the program code instructions are run by the programmable device.

10. Information storage means, characterized in that they store a computer program comprising program code instructions which can be loaded in a programmable device for implementing the method according to any one of claims 1 to 7, when the program code instructions are run by the programmable device.