Method and device for searching images

Patent metadata

Field	Value
Publication number	US-10515112-B2
Application number	US-201615575234-A
Country	US
Kind code	B2
Filing date	Jun 20, 2016
Priority date	Jun 23, 2015
Publication date	Dec 24, 2019
Grant date	Dec 24, 2019

Abstract

A method and a device for searching for images in memory containing at least one or more images and, for each image, at least one sensor fingerprint associated with the image and related to the sensor that acquired the image includes a reading phase, wherein a search sensor fingerprint is read, a compression phase, wherein the search sensor fingerprint and at least one of the sensor fingerprints associated with the images are compressed by using a random projection technique, and a searching phase, wherein the images contained in the memory are either selected or discarded by comparing the sensor fingerprints of the images with the search sensor fingerprint.

First claim

The invention claimed is:

1. A method for searching for images in memory means containing at least
one or more images and/or references to said images, and,
for each image and/or reference thereof, at least one sensor fingerprint associated with said image and/or with said reference, and related to the sensor that acquired said image,
wherein said method comprises:
a reading phase, wherein, through reading means, a search sensor fingerprint is read,
a searching phase, wherein, through computing means, each one of the images and/or image references contained in the memory means is either selected or discarded on the basis of at least one comparison between at least one portion of the sensor fingerprint of one of the images and at least one portion of the search sensor fingerprint, and
a compression phase, to be carried out prior to the searching phase, wherein the search sensor fingerprint and at least one of the sensor fingerprints associated with the images and/or with the references to said images are compressed, through the computing means, by using a random projection technique.

2. The method according to claim 1 , wherein the search sensor fingerprint and each one of the sensor fingerprints associated with the images and/or with the references to said images are compressed by multiplying at least one compression matrix by each one of said fingerprints, or vice versa.

3. The method according to claim 2 , wherein said at least one compression matrix is a partial circulant matrix.

4. The method according to claim 3 , wherein the multiplication between said at least one compression matrix and at least one of the sensor fingerprints associated with the images and/or with the references to said images is carried out by using the fast Fourier transform.

5. The method according to claim 2 , wherein said at least one compression matrix is selected from a set of compression matrices on the basis of the size of the fingerprint to be compressed.

6. The method according to claim 5 , wherein two or more compression matrices are selected from the set of compression matrices on the basis of the size of the fingerprint to be compressed, and wherein the dimensions of said selected compression matrices are such that the product between said compression matrices and the fingerprint to be compressed will generate a compressed sensor fingerprint having a predefined size.

7. The method according to claim 1 , wherein each sensor fingerprint is compressed, through the computing means, by concatenating a plurality of versions of said sensor fingerprint having different resolutions, and wherein each version of said fingerprint is compressed by using a random projection technique.

8. The method according to claim 1 , wherein, during the searching phase, an index of correlation is computed, through the computing means, between the compressed search sensor fingerprint and each one of the compressed fingerprints associated with the images and/or with the references to said images, and wherein the images or the references to said images are either selected or discarded on the basis of the value of said index of correlation.

9. The method according to claim 8 , wherein the index of correlation is computed on the basis of the Hamming distance between the compressed search sensor fingerprint and each one of the compressed fingerprints associated with the images and/or with the references to said images.

10. The method according to claim 8 , wherein, during the searching phase, two or more search iterations are carried out through the computing means, wherein, during at least one of the iterations preceding the last iteration, an index of correlation is computed between at least one portion of the compressed search fingerprint and one portion of each one of the compressed fingerprints associated with the images and/or with the references to said images, and a set of images or references to said images is selected on the basis of the indices of correlation, and wherein, during the last iteration, a comparison is made between the search fingerprint and each one of the fingerprints associated with the images and/or with the references to said images included in said set of images.

11. The method according to claim 10 , wherein the portions of each one of the compressed fingerprints associated with the images and/or with the references to said images which are compared with the compressed search sensor fingerprint during at least one of the iterations preceding the last iteration are determined on the basis of the position of characteristic points of the compressed search sensor fingerprint, wherein the characteristic points are points of a compressed fingerprint having values greater than a certain threshold value or greater than the mean value of the points of said fingerprint.

12. The method according to claim 11 , also comprising a memory loading phase, which is carried out prior to the searching phase, wherein search information comprising the position of the characteristic points of the sensor fingerprints associated with the images and/or with the references to said images is loaded into volatile memory means.

13. The method according to claim 12 , wherein the positions comprised in the search information are coded with a resolution which is lower than the resolution of the compressed fingerprints associated with the images and/or with the references to said images.

14. The method according to claim 12 , wherein the positions comprised in the search information are coded in a differential manner by using an Exponential-Golomb coding of the k-th order.

15. The method according to claim 1 , wherein the searching phase comprises a plurality of searching sub-phases, wherein each one of said sub-phases can be carried out, through the computing means, independently of the other ones, and wherein each one of said sub-phases is carried out on a sub-set of the images contained in the memory means.

16. The method according to claim 15 , wherein each sub-set of the images contained in the memory means, on which a searching sub-phase is carried out, is disconnected from the other sub-sets.

17. The method according to claim 1 , wherein, during the compression phase, the value of each one of the points of the compressed fingerprints is converted, through the computing means, into a value comprised within a limited set of values.

18. A computer program product which can be loaded into the memory of an electronic computer, and which comprises portions of software code for executing the phases of the image searching method according to claim 1 .

19. A device for searching for images, comprising
input/output means adapted to gain access to mass memory means containing at least:
one or more images and/or references to said images, and,
for each image and/or reference thereof, at least one sensor fingerprint associated with said image and/or with said reference, and related to the sensor that acquired said image,

reading means configured for reading a search sensor fingerprint,
volatile memory means, into which at least a part of said sensor fingerprints can be loaded, and
computing means in signal communication with the memory means and the reading means, wherein said computing means are configured for carrying out a search among the images and/or the references to said images, wherein each one of the images and/or references to said images contained in the memory means is either selected or discarded on the basis of at least one comparison between at least one portion of the sensor fin

Assignees

• Torino Politecnico

Inventors

• Valsesia Diego
• Coluccia Giulio
• Bianchi Tiziano
• Magli Enrico

Classifications

• G06V10/7715

  Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods · CPC title

• G06F16/583

  using metadata automatically derived from the content · CPC title

• G06F18/2137

  based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps · CPC title

• G06F18/22 Primary

  Matching criteria, e.g. proximity measures · CPC title

• G06F2218/22

  Source localisation; Inverse modelling · CPC title