Scale robust feature-based identifiers for image identification

• US 8,831,355 B2
• Filed: 04/21/2009
• Issued: 09/09/2014
• Est. Priority Date: 04/23/2008
• Status: Active Grant

• Current Assignee: Rakuten Group, Inc.
• Original Assignee: Mitsubishi Electric Corporation
• Inventors: Bober, Miroslaw, Brasnett, Paul
• Primary Examiner(s): Park, Edward
• Application Number:
  US12/989,362
• Publication Number:
  US 20110038545A1
• Time in Patent Office: 1,967 Days
• Field of Search: 382/190, 382/192, 382/231
• US Class Current: 382/192
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

A method for deriving an image identifier comprises deriving a scale-space representation of an image, and processing the scale-space representation to detect a plurality of feature points having values that are maxima or minima. A representation is derived for a scale-dependent image region associated with one or more of the detected plurality of feature points. In an embodiment, the size of the image region is dependent on the scale associated with the corresponding feature point. An image identifier is derived using the representations derived for the scale-dependent image regions. The image identifiers may be used in a method for comparing images.

Claims

1. A method for deriving a representation of an image by processing signals corresponding to the image, the method comprising:

deriving a scale-space representation of the image;

processing the scale-space representation to detect a plurality of feature points having amplitude extrema;

for one or more of the detected plurality of feature points, determining a scale-dependent image region associated with the corresponding feature point, and deriving a representation for each determined, scale-dependent image region, the method comprising selecting a predetermined number of feature points from the detected plurality of feature points, and determining a scale-dependent image region associated with each of the selected feature points, wherein the spatial positions of the selected feature points are distributed across the image, and the spatial position of each selected feature point is separated from the other selected feature points by at least a predetermined distance in the image, by selecting feature points by order of strength with the restriction that a feature point is not selected if it is within an exclusion zone around any of the previously selected features.

2. A method as claimed in claim 1, wherein the plurality of feature points are detected by applying an operator based on second order image gradients, to the scale-space representation of the image, and identifying those feature points in the scale-space representation with the highest resulting values.

3. A method as claimed in claim 1, where the step of selecting comprises removing from the detected plurality of feature points those feature points having the lowest amplitude values in the scale-space representation, or amplitude values in the scale-space representation below a threshold.

4. A method as claimed in claim 1, wherein the step of selecting comprises removing, from the detected plurality of feature points, feature points according to their spatial position in the image.

5. A method as claimed in claim 1, wherein the step of selecting comprises applying an operator to the detected plurality of feature points, the operator based on first order image gradients, and removing the features points with resulting values below a threshold.

6. A method as claimed in claim 5, wherein the operator is a scale adapted Harris operator.

7. A method as claimed in claim 1, wherein the step of determining a scale-dependent image region for a feature point in the scale-space representation comprises determining a spatial region of the image associated with the spatial position of the feature point, wherein the size of the spatial region is based on the scale of the feature point.

8. A method as claimed in claim 1, further comprising:

before determining a scale-dependent image region, refining the spatial positions of the one or more feature points to sub-pixel resolution, preferably using cubic interpolation.

9. A method as claimed in claim 1, wherein the step of deriving a representation for each determined, scale-dependent image region, comprises deriving a representation based on line projections across the image region, preferably using the Trace transform, or equivalent.

10. A method as claimed in claim 1, wherein the step of deriving a representation for each determined, scale-dependent image region, comprises:

deriving a function of at least part of the image region; and

using the function to obtain an intermediate representation of the at least part of the image region.

11. A method as claimed in claim 10, comprising:

for each of the one or more determined scale-dependent image regions;

deriving a function of at least part of the image region, where the function of a translated, scaled or rotated version of an image region is a translated or scaled version of the function of the image region.

12. A method as claimed in claim 10, wherein:

the step of deriving a function of at least part of the image region comprises applying a first functional along lines over the image region, the method preferably further comprising;

applying a second functional to the derived function to obtain an intermediate representation of the at least part of the image region.

13. A method as claimed in claim 1, further comprising:

deriving the representation of the image from two or more of the derived representations of the scale-dependent image regions.

14. A method as claimed in claim 1, further comprising:

for the one or more of the plurality of feature points, determining a feature direction for the feature point, preferably by integrating over a neighbourhood of the feature point.

15. A method as claimed in claim 14, wherein the feature direction is determined using the equation:

16. A method as claimed in claim 1, wherein the step of deriving a representation for each determined, scale-dependent image region comprises deriving a binary image descriptor for the scale-dependent image region.

17. A method for comparing images using descriptors of images derived using a method as claimed in claim 1, the method comprising:

comparing representations of one or more scale-dependent image regions associated with the descriptor of a first image, with representations of one or more scale-dependent image regions associated with the descriptor of a second image.

18. A method as claimed in claim 17, comprising:

comparing a subset of the representations of image regions of the descriptor of a first image with a corresponding subset of the representations of image regions of the descriptor of a second image, to identify candidate pairs of matching image regions.

19. A method as claimed in claim 17, comprising:

determining a first plurality of sets of a predetermined number of features points associated with image regions represented in the descriptor of the first image;

determining a second plurality of sets of the predetermined number of features points associated with image regions represented in the descriptor of the second image;

comparing a set of the determined first plurality of sets with a set of the determined second plurality of sets using a matching algorithm.

20. A method as claimed in claim 19, wherein the predetermined number is three, and the matching algorithm is based on the Hamming distance between a pair of representations of image regions associated with features points in the first and second images, and the cumulative Hamming distance between the three pairs of representations of image regions associated with features points in the first and second images.

21. A method as claimed in claim 20, further comprising:

determining candidate matching sets of features points, in the first and second images, when;

said Hamming distance is below a first threshold, and

said cumulative Hamming distance is below a second threshold.

22. A method as claimed in claim 21, further comprising:

applying a geometric constraint to geometric information for each said candidate matching set, to eliminate false matches from the candidate sets.

23. A method as claimed in claim 22, wherein the step of applying a geometric constraint comprises:

determining the length of spatial lines between each of the feature points in the candidate sets;

determining a ratio between pairs of the lines in the candidate sets of the first image and the second image, and

deriving at least one measure of similarity between the determined line length ratios associated with the first image and the determined line length ratios associated with the second image.

24. A method as claimed in claim 22, wherein the representations of the image regions associated with the feature points include feature direction information, and the geometric constraint takes into account feature direction.

25. A method as claimed in claim 22, further comprising:

eliminating a candidate matching set of feature point from the candidate sets if a measure of similarity is below a threshold.

26. A method as claimed in claim 22, further comprising:

if there are no candidate matching sets, determining that the first and second images do not match.

27. A method as claimed in claim 26, further comprising:

if candidate matching sets remain;

comparing the representations of all of the image regions of the descriptor of a first image with the representations of all of the image regions of the descriptor of a second image, to determine a further matching set of feature points, not present in the candidate set.

28. A method as claimed in claim 27, wherein a further matching set of feature points is determined based on a lowest Hamming distance between feature points of the first and second images, not present in the candidate sets.

29. A method as claimed in claim 27, further comprising:

adding the determined further matching set of feature points to the candidate sets, to produce updated candidate sets, and

applying a geometric constraint to geometric information for each updated candidate matching set of four feature points, to further eliminate false matches from the candidate sets.

30. An apparatus comprising:

an image database for storing images or representations of images;

an identifier database; and

a processor configured to execute for executing the method of claim 1 or claim 17.

31. A non-transitory computer storage medium having stored thereon instructions that, when executed by a computer, perform the method as claimed in claim 1 or claim 17.