Method for searching for a similar image in an image database based on a reference image

• US 9,418,313 B2
• Filed: 08/06/2014
• Issued: 08/16/2016
• Est. Priority Date: 08/08/2013
• Status: Active Grant

• Current Assignee: STMicroelectronics International N.V. (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SA (STMicroelectronics NV)
• Inventors: Valente, Stphane
• Primary Examiner(s): Dunphy, David F
• Application Number:
  US14/452,761
• Publication Number:
  US 20150043828A1
• Time in Patent Office: 741 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]

Abstract

A method for extracting characteristic points from an image, includes extracting characteristic points from a first image, generating for each characteristic point a descriptor with several components describing an image region around the characteristic point, and comparing two by two the descriptors of the first image, the characteristic points whose descriptors have a proximity between them greater than an ambiguity threshold, being considered ambiguous.

Claims

1. A method, comprising:

extracting characteristic points from a first image;

generating for each characteristic point of the first image a plurality of components of a descriptor describing an image region around the characteristic point;

comparing the descriptors of the characteristic points of the first image;

classifying characteristic points of the first image based on the comparing and an ambiguity threshold;

comparing descriptors of characteristic points of the first image with descriptors of characteristic points of a second image, to obtain a set of pairs of characteristic points belonging respectively to the first and second images, the descriptors of which have a proximity lower than a first threshold;

defining a set of spatial transformation models linking the respective positions of the characteristic points of at least two pairs;

testing the spatial transformation models by determining whether a model links respective positions of the characteristic points of other pairs of characteristic points, within an error margin lower than a position error threshold; and

identifying the second image as a relevant visual search image based on whether at least one of the transformation models links characteristic points of a number of pairs greater than a threshold of number of pairs, wherein the comparing descriptors of characteristic points of the first image to descriptors of characteristic points of the second image is limited to characteristic points classified as non-ambiguous with respect to at least one of the first and second images and the testing considers ambiguous characteristic points.

2. The method according to claim 1, comprising:

removing characteristic points classified as ambiguous from a set of characteristic points associated with the first image.

3. The method according to claim 1, comprising:

associating a first characteristic point of the first image with an ambiguity rating based on a proximity of the descriptor of the first characteristic point to a descriptor of another characteristic point of the first image considered to be a closest characteristic point to the first characteristic point.

4. The method according to claim 1, comprising, for each characteristic point:

determining a direction of the characteristic point;

determining points of a region around the characteristic point, oriented according to the direction of the characteristic point, from pixels of the region around the characteristic point;

dividing the region into sub-regions; and

determining for each sub-region a characteristic point descriptor component from the points of the sub-region.

5. A method, comprising:

extracting characteristic points from a first image;

generating for each characteristic point of the first image a plurality of components of a descriptor describing an image region around the characteristic point;

comparing the descriptors of the characteristic points of the first image;

classifying characteristic points of the first image based on the comparing and an ambiguity threshold;

comparing descriptors of characteristic points of the first image with descriptors of characteristic points of a second image, to obtain a set of pairs of characteristic points belonging respectively to the first and second images, the descriptors of which have a proximity lower than a first threshold;

defining a set of spatial transformation models linking the respective positions of the characteristic points of at least two pairs;

testing the spatial transformation models by determining whether a model links respective positions of the characteristic points of other pairs of characteristic points, within an error margin lower than a position error threshold; and

identifying the second image as a relevant visual search image based on whether at least one of the transformation models links characteristic points of a number of pairs greater than a threshold number of pairs, wherein the second image is one of a plurality of images of an image database and the method comprises;

comparing the first image with the plurality of images of the image database; and

associating a visual search relevance rating with an image of the image database identified as relevant based on a surface area of a region of the image of the database delimited by the characteristic points belonging to the pairs linked by the at least one transformation model.

6. The method of claim 5 wherein the comparing descriptors of characteristic points of the first image to descriptors of characteristic points of the second image is limited to characteristic points classified as non-ambiguous with respect to at least one of the first and second images.

7. The method according to claim 6 wherein the testing considers ambiguous characteristic points.

8. The method according to claim 5, comprising:

removing characteristic points classified as ambiguous from a set of characteristic points associated with the first image.

9. The method according to claim 5, comprising:

associating a first characteristic point of the first image with an ambiguity rating based on a proximity of the descriptor of the first characteristic point to a descriptor of another characteristic point of the first image considered to be a closest characteristic point to the first characteristic point.

10. The method according to claim 5, comprising, for each characteristic point:

determining a direction of the characteristic point;

determining points of a region around the characteristic point, oriented according to the direction of the characteristic point, from pixels of the region around the characteristic point;

dividing the region into sub-regions; and

determining for each sub-region a characteristic point descriptor component from the points of the sub-region.

11. A method, comprising:

extracting characteristic points from a first image;

generating for each characteristic point of the first image a plurality of components of a descriptor describing an image region around the characteristic point;

comparing the descriptors of the characteristic points of the first image;

classifying characteristic points of the first image based on the comparing and an ambiguity threshold;

comparing descriptors of characteristic points of the first image with descriptors of characteristic points of a second image, to obtain a set of pairs of characteristic points belonging respectively to the first and second images, the descriptors of which have a proximity lower than a first threshold;

defining a set of spatial transformation models linking the respective positions of the characteristic points of at least two pairs;

testing the spatial transformation models by determining whether a model links respective positions of the characteristic points of other pairs of characteristic points, within an error margin lower than a position error threshold; and

identifying the second image as a relevant visual search image based on whether at least one of the transformation models links characteristic points of a number of pairs greater than a threshold of number of pairs, wherein the second image is one of a plurality of images of an image database;

comparing the first image with the plurality of images of the image database; and

associating a visual search relevance rating with an image of the image database identified as relevant based on a number of pairs linked by the at least one transformation model, wherein the relevance rating is completed for each image of the image database identified as relevant, ambiguous characteristic points in the first and second images are searched for pairs of characteristic points having a proximity of descriptors lower than the first threshold, and the relevance rating is incremented when the at least one transformation model links respective positions of the characteristic points of a pair of ambiguous characteristic points.

12. The method according to claim 11, comprising:

associating a visual search relevance rating with an image of the image database identified as relevant based on a surface area of a region of the image of the image database delimited by the characteristic points belonging to the pairs linked by the at least one transformation model.

13. The method according to claim 11, comprising:

removing characteristic points classified as ambiguous from a set of characteristic points associated with the first image.

14. The method according to claim 11, comprising:

associating a first characteristic point of the first image with an ambiguity rating based on a proximity of the descriptor of the first characteristic point to a descriptor of another characteristic point of the first image considered to be a closest characteristic point to the first characteristic point.

15. The method according to claim 11, comprising, for each characteristic point:

determining a direction of the characteristic point;

determining points of a region around the characteristic point, oriented according to the direction of the characteristic point, from pixels of the region around the characteristic point;

dividing the region into sub-regions; and

determining for each sub-region a characteristic point descriptor component from the points of the sub-region.

16. The method of claim 11 wherein the comparing descriptors of characteristic points of the first image to descriptors of characteristic points of the second image is limited to characteristic points classified as non-ambiguous with respect to at least one of the first and second images.

17. The method according to claim 16 wherein the testing considers ambiguous characteristic points.

18. A system, comprising:

a memory; and

processing circuitry, which, in operation;

compares descriptors of characteristic points of a first image with descriptors of characteristic points of a second image, the characteristic points of at least one of the first and second images being limited to characteristic points classified as non-ambiguous based on an ambiguity threshold;

identifies, based on the comparisons of the descriptors, a set of pairs of characteristic points belonging respectively to the first and second images, the descriptors of which have a proximity lower than a first threshold;

defines a set of spatial transformation models linking the respective positions of the characteristic points of at least two pairs of the set of pairs;

tests the spatial transformation models by determining whether a model links respective positions of the characteristic points of other pairs of characteristic points, within an error margin lower than a position error threshold, wherein the testing considers ambiguous characteristic points; and

identifies the second image as a relevant search image based on whether at least one of the transformation models links characteristic points of a number of pairs greater than a threshold of number of pairs.

19. The system of claim 18 wherein the second image is one of a plurality of images of an image database and the processing circuitry, in operation:

compares the first image with a plurality of images of the image database; and

associates a visual search relevance rating with images of the image database identified as relevant.

20. The system of claim 19 wherein the visual search relevance rating of an image of the image database identified as relevant is based on the number of pairs of links established by the at least one transformation model.

21. A method, comprising:

comparing, using digital image processing circuitry, descriptors of characteristic points of a first image with descriptors of characteristic points of a second image, the characteristic points of at least one of the first and second images being limited to characteristic points classified as non-ambiguous based on an ambiguity threshold;

identifying, using the digital image processing circuitry and based on the comparisons of the descriptors, a set of pairs of characteristic points belonging respectively to the first and second images, the descriptors of which have a proximity lower than a first threshold;

defining, using the digital image processing circuitry, a set of spatial transformation models linking the respective positions of the characteristic points of at least two pairs of the set of pairs;

testing, using the digital image processing circuitry, the spatial transformation models by determining whether a model links respective positions of the characteristic points of other pairs of characteristic points, within an error margin lower than a position error threshold, wherein the testing considers ambiguous characteristic points; and

identifying, using the digital image processing circuitry, the second image as a relevant search image based on whether at least one of the transformation models links characteristic points of a number of pairs greater than a threshold of number of pairs.

22. The method of claim 21 wherein the second image is one of a plurality of images of an image database and the method comprises:

comparing the first image with a plurality of images of the image database; and

associating a visual search relevance rating with images of the image database identified as relevant.

23. The method of claim 22 wherein the visual search relevance rating of an image of the image database identified as relevant is based on the number of pairs of links established by the at least one transformation model.