Method and device for the invariant-affine recognition of shapes

• US 8,687,920 B2
• Filed: 05/18/2009
• Issued: 04/01/2014
• Est. Priority Date: 05/19/2008
• Status: Active Grant

• Current Assignee: Ecole Normale Superieure, Ecole polytechnique
• Original Assignee: Ecole Normale Superieure, Ecole polytechnique
• Inventors: Morel, Jean-Michel, Yu, Guoshen
• Primary Examiner(s): Seth, Manav
• Application Number:
  US12/993,499
• Publication Number:
  US 20110069889A1
• Time in Patent Office: 1,779 Days
• US Class Current: 382/296
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching
• CPC Class Codes: G06V 2201/11 Technique with transformation invariance effect

Abstract

A method for the recognition of objects in at least one digital image includes: a) simulating from the digital image a plurality of digital rotations and at least two digital tilts different from 1 in order to develop a simulated image for each rotation-tilt pair; and b) applying an algorithm generating values that are invariant in translation, rotation and zoom onto the simulated images in order to determine so-called SIF (scale invariant features) local characteristics used for recognizing objects. The SIFT method can be used in step b.

Claims

1. A method for object recognition applied to a digital image called a query and to a digital image called a target, the method comprising:

simulating, by one or more processors, from each of the digital images a plurality of digital rotations and at least two digital tilts different from 1 in order to develop a simulated image for each rotation-tilt pair; and

applying an algorithm, by the one or more processors, generating values that are invariant in translation, rotation and zoom onto the simulated images in order to determine local characteristics, called scale invariant features (SIF), used for recognizing similar or identical objects between the query and the target.

2. The method according to claim 1, wherein the query contains any view taken of an object with a shape similar or identical to the shape of another object contained in the target from any view, and

rotation-tilt pairs are determined for which the SIFs of two objects are similar.

3. The method according to claim 1, wherein one and the same number of simulated images are produced for the query and for the target, and for the same rotation-tilt pairs.

4. The method according to claim 1, wherein a different number of simulated images is produced for the query and for the target.

5. The method according to claim 1, wherein the number of rotations per tilt increases at the same time as the value of the tilt increases.

6. The method according to claim 1, wherein the tilt is a function of the latitude in a hemisphere above the digital image, and

the difference in latitude between two consecutive tilts decreases at the same time as the latitude increases.

7. The method according to claim 1, wherein the tilts considered form approximately a finite geometric progression 1, a, a², a³, . . . , aⁿ, a being a number greater than 1.

8. The method according to claim 7, wherein a is of the order of root 2 and n is in the range from 2 to 6 when the rotation-tilt pairs are applied both on the target and on the query, and from 2 to 12 when the rotation-tilt pairs are applied on just one of the two images.

9. The method according to claim 1, wherein, for a given tilt t, the digital rotations form an approximately arithmetic progression 0, b/t, 2b/t, . . . , kb/t degrees, with b in degrees and k an integer.

10. The method according to claim 9, wherein b is of the order of 72 degrees, and k is the last whole value such that kb/t is less than 180 degrees.

11. The method according to claim 1, wherein applying a tilt t consists of under-sampling the digital image in a fixed direction from a value equal to t.

12. The method according to claim 1, wherein applying a tilt t consists of under-sampling the digital image in a fixed direction and over-sampling in a direction orthogonal to the preceding.

13. The method according to claim 1, wherein the method is applied to one or more images called queries and one or more images called targets,

the SIFs relating to the query are determined in the course of a previous stage of calibration so as to constitute a dictionary of SIFs;

and

the SIFs relating to the targets are respectively determined in the course of a stage of operation during which the SIFs obtained from each target are compared with the SIFs in said dictionary.

14. The method according to claim 1, wherein the method is applied to a digital image by comparison with the same digital image or a transform of the same digital image, and oblique symmetries, repeated shapes or shapes having periodicities in the same digital image are determined.

17. The method according to claim 2, wherein one and the same number of simulated images are produced for the query and for the target, and for the same rotation-tilt pairs.

18. The method according to claim 2, wherein a different number of simulated images is produced for the query and for the target.

15. A Device for object recognition between a digital image which is a query and to a digital image which is a target, the device comprising:

a processing circuit configured to;

apply from each of the digital images a plurality of digital rotations and the at least two digital tilts different from 1 in order to develop a simulated image for each rotation-tilt pair, and

apply an algorithm generating values that are invariant in translation, rotation and zoom onto the simulated images in order to determine local characteristics, called scale invariant features (SIF), used to recognize similar or identical objects between the query and the target.

16. The device according to claim 15, further comprising a memory space in which a dictionary of SIFs is stored,

wherein the processing circuit is configured so as to compare SIFs of said digital image with the SIFs in said dictionary.