NOVEL DESCRIPTOR FOR IMAGE CORRESPONDING POINT MATCHING

• US 20100080469A1
• Filed: 09/24/2009
• Published: 04/01/2010
• Est. Priority Date: 10/01/2008
• Status: Active Grant

• Current Assignee: Fujifilm Business Innovation Corp. (Fujifilm Holdings Corporation)
• Original Assignee: Fujifilm Corporation (Fujifilm Holdings Corporation), Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Yano, Hironori, Liu, Qiong
• Granted Patent: US 8,363,973 B2
• Time in Patent Office: Days
• US Class Current: 382/201
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]

Abstract

System and method of generating feature descriptors for image identification. Input image is Gaussian-blurred at different scales. A difference of Gaussian space is obtained from differences of adjacent Gaussian-blurred images. Key points are identified in the difference-of-Gaussian space. For each key point, primary sampling points are defined with three dimensional relative positions from key point and reaching into planes of different scales. Secondary sampling points are identified for each primary sampling point. Secondary image gradients are obtained between an image at a primary sampling point and images at secondary sampling points corresponding to this primary sampling point. Secondary image gradients form components of primary image gradients at primary sampling points. Primary image gradients are concatenated to obtain a descriptor vector for input image. Descriptor vector thus obtained is scale invariant and requires a number of additions equal to number of primary sampling points multiplied by a number of secondary sampling points.

Claims

1. A method for generating a feature descriptor vector for image identification, the method being implemented in a computing system having components including an input and output interface, a storage medium, one or more processors, and a link providing communication between the components, the method comprising:

receiving an input image at the input and output interface;

constructing a Gaussian pyramid space of the input image by applying Gaussian-blur filters to the input image and generating Gaussian-blurred images, the Gaussian-blur filters each having a different scale of blurring, the scales being based on input parameters;

locating key points in the Gaussian pyramid space;

identifying primary sampling points for each of the key points in the Gaussian pyramid space, the primary sampling points being defined with three dimensional relative positions from the key point;

calculating primary image gradients corresponding to the primary sampling points, the primary image gradients being vectors indicating a change in image in a vicinity of the primary sampling points; and

generating a feature descriptor vector for the input image by concatenating the primary image gradients.

2. The method of claim 1, wherein the locating key points in the Gaussian pyramid space comprises:

constructing a difference-of-Gaussian-space by obtaining differences between consecutive ones of the Gaussian-blurred images; and

locating the key points as local maxima or local minima of planes in the difference-of-Gaussian space.

3. The method of claim 1,

wherein secondary sampling points corresponding to each of the primary sampling points are used to obtain the primary image gradients, and

wherein a location of the secondary sampling points with respect to the corresponding primary sampling point is defined based on the scale of the primary sampling point.

4. The method of claim 1, wherein the Gaussian-blurred images are generated by applying a series of Gaussian-blur filters.

5. The method of claim 1, wherein the three-dimensional vectors identifying the primary sampling points for each of the key points are predetermined.

6. The method of claim 1,

wherein the input parameters include scale factor(s) and sampling parameters, wherein the sampling parameters include primary sampling parameters and a secondary sampling parameter.

7. The method of claim 6,

wherein the three-dimensional vectors of each key point are defined in a sub-coordinate system having the key point as origin.

8. The method of claim 7,

wherein the primary sampling parameters include a first parameter, dr, and a second parameter, sdr, and

wherein coordinates of the primary sampling points are determined from the primary sampling parameters and the scale of the key point, s, according to:

d=dr·

s,

sd=sdr·

s.

9. The method of claim 8, wherein the index i varies from 0 to 4 indicating five primary sampling points:

a first primary sampling point having coordinates (0, 0,

     0) corresponding the key point,

a second primary sampling point having coordinates (d, 0, sd),

a third primary sampling point having coordinates (0, d, sd),

a fourth primary sampling point having coordinates (−

d, 0, sd), and

a fifth primary sampling point having coordinates (0, −

d, sd).

10. The method of claim 8,

wherein the secondary sampling parameter is a third parameter, rr,

wherein the secondary sampling points are determined based on the third parameter, rr, the second parameter, sdr, of the primary sampling parameters, and the scale of the key point, s, of the corresponding primary sampling point, according to:

r₀=rr·

s,

r=r₀(1+sdr), and

wherein the secondary sampling points are located at equidistance intervals on a perimeter of a circle, having a radius r.

11. The method of claim 1,

wherein the primary image gradients include secondary image gradients at each of the secondary sampling points,

wherein the secondary image gradients indicate a change in image between each of the primary sampling points and the secondary sampling points corresponding to the primary sampling point according to:

I_ij=max(I(O_i)−

I(O_ij)),0)

index i indicates the primary sampling point, i=0 . . . n, n+1 being a number of the primary sampling points,

index j indicates the secondary sampling point, j=0 . . . m, m+1 being a number of the secondary sampling points,

O_i indicates the three-dimensional vector defining the primary sampling point i,

O_ij indicates the three-dimensional vector defining the secondary sampling point i,j,

I(O_i) indicates an image intensity level at the primary sampling point i,

I(O_ij) indicates an image intensity level at the secondary sampling point ij,

I_ij indicates a non-negative scalar corresponding to a change in image intensity between the primary sampling point i and the secondary sampling point ij that corresponds to the primary sampling point i,

wherein the primary image gradients at each of the primary sampling points i are obtained according to;

V_ij=I_ij/[SQRT(sum over j=0 to j=m of (I_ij)²)]

V_i=[V_i0(O_i−

O_i0)/[magnitude of (O_i−

O_i0)], . . . , V_i7(O_i−

O_im)/[magnitude of (O_i−

O_im)]]

V_ij provides a scalar indicating the secondary image gradient component magnitude at the secondary point i,j,

Vi provides the primary image gradient vector at the primary sampling point i, each V_i having a dimension equal to the total number of j, and

wherein the feature descriptor vector of each key point is obtained from the concatenation of the primary image gradients according to;

V=[V₀, . . . Vi . . . , V_n]

where n is a number of primary sampling points identified for the key point.

12. The method of claim 1, further comprising receiving the input parameters at the input and output interface.

13. A computer system for generating a feature descriptor vector for image identification comprising:

an input and output interface for receiving an input image; and

one or more processors for constructing a Gaussian pyramid space of the input image by applying Gaussian-blur filters to the input image and generating Gaussian-blurred images, the Gaussian-blur filters each having a different scale of blurring, the scales being based on input parameters,

wherein the one or more processors locate key points in the Gaussian pyramid space,

wherein the one or more processors identify primary sampling points for each of the key points in the Gaussian pyramid space, the primary sampling points being defined with three dimensional relative positions from the key point,

wherein the one or more processors calculate primary image gradients corresponding to the primary sampling points, the primary image gradients being vectors indicating a change in image in a vicinity of the primary sampling points,

wherein the one or more processors generate a feature descriptor vector for the input image by concatenating the primary image gradients, and

wherein the input and output interface provides the feature descriptor vector to a user through the input and output interface.

14. The system of claim 13, wherein the locating key points in the Gaussian pyramid space comprises:

constructing a difference-of-Gaussian-space by obtaining differences between consecutive ones of the Gaussian-blurred images; and

locating the key points as local maxima or local minima of planes in the difference-of-Gaussian space.

15. The system of claim 13,

wherein secondary sampling points corresponding to each of the primary sampling points are used to obtain the primary image gradients, and

wherein a location of the secondary sampling points with respect to the corresponding primary sampling point is based on the scale of the primary sampling point.

16. The system of claim 13, wherein the Gaussian-blurred images are generated by applying a series of Gaussian-blur filters.

17. The system of claim 13, wherein the three-dimensional vectors identifying the primary sampling points for each of the key points are predetermined.

18. The system of claim 13,

wherein the input parameters include scale factors, s, and sampling parameters, dr, sdr, rr;

wherein indices i determine each of the primary sampling points, and

wherein the sampling parameters include primary sampling parameters and a secondary sampling parameter.

19. The system of claim 18,

wherein the three-dimensional vectors of each key point are defined in a sub-coordinate system having the key point as origin (0, 0, 0).

20. The system of claim 19,

wherein the primary sampling parameters include a first parameter, dr, and a second parameter, sdr, and

wherein coordinates of the primary sampling points are determined from the primary sampling parameters and the scale factor according to:

d=dr·

s

sd=sdr·

s.

21. The system of claim 20, wherein the index i varies from 0 to 4 indicating five primary sampling points:

a first primary sampling point having coordinates (0, 0,

     0) corresponding the key point,

a second primary sampling point having coordinates (d, 0, sd),

a third primary sampling point having coordinates (0, d, sd),

a fourth primary sampling point having coordinates (−

d, 0, sd), and

a fifth primary sampling point having coordinates (0, −

d, sd).

22. The system of claim 20,

wherein the secondary sampling parameter is a third parameter, rr,

wherein the secondary sampling points are determined based on the third parameter, rr, the second parameter, sdr, of the primary sampling parameters, and the scale, s, of the corresponding primary sampling point, according to:

r₀=rr·

s,

r=r₀(1+sdr), and

wherein the secondary sampling points are located at equidistance intervals on a perimeter of a circle, having a radius r.

23. The system of claim 13,

wherein the primary image gradients include secondary image gradients at each of the secondary sampling points,

wherein the secondary image gradients indicate a change in image between each of the primary sampling points and the secondary sampling points corresponding to the primary sampling point according to:

I_ij=max(I(O_i)−

I(O_ij))),0)

index i indicates the primary sampling point, i=0 . . . n, n+1 being a number of the primary sampling points,

index j indicates the secondary sampling point, j=0 . . . m, m+1 being a number of the secondary sampling points,

O_i indicates the three-dimensional vector defining the primary sampling point i,

O_ij indicates the three-dimensional vector defining the secondary sampling point i,j,

I(O_i) indicates an image intensity level at the primary sampling point i,

I(O_ij) indicates an image intensity level at the secondary sampling point ij,

I_ij indicates a non-negative scalar corresponding to a change in image intensity between the primary sampling point i and the secondary sampling point ij that corresponds to the primary sampling point i,

wherein the primary image gradients at each of the primary sampling points i are obtained according to;

V_ij=I_ij/[SQRT(sum over j=0 to j=m of (I_ij)²)]

Vⁱ=[V_i0(O_i−

O_i0)/[magnitude of (O_i−

O_i0)], . . . , V_i7(O_i−

O_im)/[magnitude of (O_i−

O_im)]]

V_ij provides a scalar indicating the secondary image gradient component magnitude at the secondary point i,j,

Vi provides the primary image gradient vector at the primary sampling point i, each V_i having a dimension equal to the total number of j, and

wherein the feature descriptor vector of each key point is obtained from the concatenation of the primary image gradients according to;

V=[V₀, . . . Vi . . . , V_n]

where n is a number of primary sampling points identified for the key point.

24. A computer readable medium embodying a set of instructions, which, when executed by one or more processors cause the one or more processors of a computer system to perform a method for generating a feature descriptor vector for image identification, the computer system having components including an input and output interface, a storage medium, one or more processors, and a link providing communication between the components, the method comprising:

receiving an input image at the input and output interface;

constructing a Gaussian pyramid space of the input image by applying Gaussian-blur filters to the input image and generating Gaussian-blurred images, the Gaussian-blur filters each having a different scale of blurring, the scales being based on input parameters;

locating key points in the Gaussian pyramid space;

identifying primary sampling points for each of the key points in the Gaussian pyramid space, the primary sampling points being defined with three dimensional relative positions from the key point;

calculating primary image gradients corresponding to the primary sampling points, the primary image gradients being vectors indicating a change in image in a vicinity of the primary sampling points; and

generating a feature descriptor vector for the input image by concatenating the primary image gradients.