[go: up one dir, main page]

WO2009150361A2 - Procede et dispositif de reconnaissance invariante-affine de formes - Google Patents

Procede et dispositif de reconnaissance invariante-affine de formes Download PDF

Info

Publication number
WO2009150361A2
WO2009150361A2 PCT/FR2009/050923 FR2009050923W WO2009150361A2 WO 2009150361 A2 WO2009150361 A2 WO 2009150361A2 FR 2009050923 W FR2009050923 W FR 2009050923W WO 2009150361 A2 WO2009150361 A2 WO 2009150361A2
Authority
WO
WIPO (PCT)
Prior art keywords
tilt
image
digital image
sifs
images
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/FR2009/050923
Other languages
English (en)
Other versions
WO2009150361A3 (fr
Inventor
Jean-Michel Morel
Guoshen Yu
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Ecole Polytechnique
Ecole Normale Superieure de Paris
Original Assignee
Ecole Polytechnique
Ecole Normale Superieure de Paris
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Ecole Polytechnique, Ecole Normale Superieure de Paris filed Critical Ecole Polytechnique
Priority to JP2011510028A priority Critical patent/JP5442721B2/ja
Priority to EP09761912A priority patent/EP2289026A2/fr
Priority to US12/993,499 priority patent/US8687920B2/en
Priority to CN200980127996.XA priority patent/CN102099815B/zh
Publication of WO2009150361A2 publication Critical patent/WO2009150361A2/fr
Publication of WO2009150361A3 publication Critical patent/WO2009150361A3/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
    • G06V10/74—Image or video pattern matching; Proximity measures in feature spaces
    • G06V10/75—Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
    • G06V10/754—Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries involving a deformation of the sample pattern or of the reference pattern; Elastic matching
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V2201/00—Indexing scheme relating to image or video recognition or understanding
    • G06V2201/11—Technique with transformation invariance effect

Definitions

  • the present invention relates to a method and a device for recognizing objects in at least one digital image.
  • a pattern recognition method is intended to recognize an object or type of object that has been photographed when the relative position of the object and the actual or simulated camera is unknown, or when the object eventually distorted.
  • the object itself can be a graphic and non-physical object (such as a digital logo or the result of a simulation).
  • the shooting device or simulation of shooting
  • the invention relates to any acquisition of images, and any distortion or geometric deformation of the view of an object driven by the change of position relative to the object of the camera, or by the peculiarities of the device for acquiring or simulating images.
  • the objects photographed or simulated do not need to be identical, it is enough that they are similar, a current situation for objects resulting from an industrial or graphic production.
  • One or more images of the object to be recognized are available: these are the "request” images.
  • the image or images where the object is searched do not necessarily contain it. The goal is to find reliable clues as to whether the object is present in these analyzed images, and to give its position in the image.
  • the first simplification proposed by all the methods dealing with the problem of recognition is to suppose that the object has a fairly regular relief so that one can interpret the local deformations in the target images like plane affine deformations of the image request.
  • Most of the physical objects of interest are indeed volumes whose surface has flat or slightly curved faces. Exceptions are rare.
  • An example of an exception is a leafless tree, whose appearance can change drastically by a change of viewing angle, or the eddy of a liquid.
  • any regular deformation in the mathematical sense of the term (differentiable) is, locally in the image, close to an affine deformation.
  • the distortion of its image caused by a change of position of the camera observing it is a flat homography, which is in every point tangent to an affine application. If further the camera is far enough from the observed object, this distortion of the image looks more and more like a global affine transformation.
  • any affine transform of the plane of the positive determinant image can be interpreted as a distortion of the image due to the movement in the space of a camera observing the image and located far from the image (virtually 'infinite).
  • the problem of pattern recognition can be reduced to the search for local features of images which are invariant modulo an affine transformation. These characteristics are then robust to the apparent local deformations caused by the relative movements of the object and the camera, as well as to the distortions caused by the acquisition device, such as for example the optical distortion of a lens, and finally distortions due to deformations of the object itself.
  • tilt and “digital” which are terms commonly used by those skilled in the art and which mean respectively tilt and digital.
  • SIF and SIFT which are abbreviations known by those skilled in the art and which respectively mean “scale invariant feature” and “scale invariant feature transform”, that is, “invariant characteristic in scale” and “invariant scale feature transform” .
  • the invention also aims to allow object recognition in an image for which the shooting is oblique, in comparison with a frontal shot facing the object, or also oblique.
  • the invention therefore aims to improve the recognition rate regardless of the shots.
  • At least one of the above-mentioned objects is reached with a method for the recognition of objects in at least one digital image in which: a) from said digital image, a plurality of digital rotations and at least two digital tilts are simulated different from 1, so as to develop for each rotation-tilt pair, a simulated image, and b) we apply an algorithm producing invariant values by translation, rotation and zoom on the simulated images so as to determine local characteristics called SIFs ( "Scale invariant features”) that we use for object recognition.
  • SIFs Scale invariant features
  • each position of the camera is defined by a rotation-tilt pair
  • those skilled in the art will readily understand that other more or less complex transformations can be used to define a position of the camera.
  • the invention is remarkable in that - A - that any change of orientation of the axis of the camera can be summarized to a rotation followed by a tilt.
  • the method according to the present invention is based on the observation that any affine transformation of the plane can be interpreted as a transformation of the image due to a change of position of a camera to infinity. Thanks to this interpretation one can decompose an affine transformation into the product:
  • Prior art algorithms make it possible to recognize an image for which the first three transformations are arbitrary. They correspond to the four parameters of axial rotation of the camera, zoom, and translation parallel to the focal plane (and therefore perpendicular to the optical axis).
  • the SIFT method makes it possible to determine SIFs ("scale invariant features"), that is to say more precisely invariant characteristics by zoom, translation and rotation of the image, but does not take into account the last two parameters relating to the optical axis direction change of the camera.
  • SIFs scale invariant features
  • Lowe provides additional views to improve the sensitivity of the SIFT method, but these are real views, which involves additional manipulations as well as a considerable increase in the data to be processed.
  • Pritchard only provides for four simulated images because it was considered that going beyond would be counterproductive and prohibitive in terms of computing time. The present invention goes beyond a generally accepted prejudice, according to which the calculation time would be prohibitive if the number of simulated images was increased.
  • the method according to the present invention it is possible to simulate with sufficient accuracy all the distortions of the image due to the variations of the two parameters not processed in the SIFT method, which are the change of direction parameters of the optical axis of the camera.
  • several simulated images are first produced according to said last two parameters which are described by a rotation and a tilt.
  • rotation-tilt pairs can fit in a half-sphere above the digital image.
  • Rotation and tilt are considered to correspond to longitude and latitude in space, respectively.
  • Pritchard actually describes four rotations and a single tilt value from a frontal image.
  • the initial images can be obtained by non-frontal, i.e. oblique to about 80 degrees.
  • the systems of the prior art make it possible to recognize objects with a tolerance for changes in camera axis orientation resulting in real tilts up to 3 or 4.
  • a tilt much greater than 2, up to 30 for example or more is possible, and the method according to the invention makes it possible to recognize such oblique views one from the other.
  • This process is therefore capable of recognizing all the possible views of the image at infinity, since the simulated views need only an invariant recognition algorithm by translation, rotation and zoom, a well-controlled problem in the state of the art that knows how to calculate SIFs.
  • the method is applied to a so-called request image and a so-called target image, the SIFs of the simulated images of the request being compared to the SIFs of the simulated images of the target so as to recognize similar or identical objects between the query and the target.
  • the SIFs relating to the request can be determined during a preliminary step of calibration to form a dictionary of SIFs. And the SIFs relating to the targets can be respectively determined during an operating step during which the SIFs obtained from each target are compared with the SIFs of said dictionary.
  • the method according to the invention is carried out in which the request contains any shot of an object of similar or identical shape. to the shape of another object contained in the target under any shot, and rotational-tilt pairs are determined, ie this optimum number and these optimal positions as those for which the SIFs of the two objects are similar, for a large number of objects tested.
  • the method according to the invention provides for producing the same number of simulated images for the request and for the target, and for the same rotation-tilt pairs. But it also provides the case where we develop a different number of simulated images for the query and for the target, especially with different or identical tilts.
  • the number of rotations per tilt increases as the tilt value increases.
  • the tilt is defined as a function of the latitude in a half-sphere above the digital image, and the difference in latitude between two consecutive tilts decreases as the tilt increases.
  • the tilts considered form approximately that is to say with a tolerance, a finite geometric sequence 1, a, a 2 , a 3 , ..., a ", a being a number greater than 1.
  • a is in the root order of 2 (V2) and n can range from 2 to 6 if the rotation-tilt pairs are applied as well. on the target only on the query, and from 2 to 12 if the rotation-tilt pairs are applied to only one of the two images.
  • b is of the order of 72 degrees
  • k is the last integer value such that kb / t is less than 180 degrees.
  • t images 2.5.f images.
  • applying a tilt t consists in subsampling the digital image in a direction of a value equal to t, which divides its area by t.
  • a tilt can also be applied by combining subsampling of the digital image in one direction with oversampling in a direction orthogonal to the previous one.
  • the method according to the invention takes a time comparable to the SIFT method, for example, while allowing the recognition of oblique views up to a transition tilt of 16.
  • a tilt can be simulated by combining an oversampling in a direction and a subsampling in the orthogonal direction, so that the surface of the image remains constant and does not decrease (see definition of the tilt further).
  • simulating all the views depending on two parameters while maintaining a computation time and a reasonable memory is made possible thanks to the fact that the space of the two parameters rotation and tilt is sampled with relatively few values for each parameter, and that simulating skew distortions can decrease the size of the images by downsampling. This makes it possible to virtually generate all the possible views at a given accuracy, while not extending the required memory capacity too much.
  • the method according to the invention can be applied to said digital image in comparison with the same digital image or a transformation thereof, for example an axial symmetry, so as to determine in this digital image symmetries, repeated forms or forms with periodicities.
  • a device for implementing a method for recognizing objects in at least one digital image comprises a processing circuit configured to: a) apply, from said digital image, a plurality of digital rotations and at least two digital tilts t different from 1 so as to develop for each rotation-tilt pair, a simulated image , and b) apply an invariant algorithm by translating, rotating and zooming the simulated images to determine local characteristics called SIFs ("scale invariant features") that are used for object recognition.
  • SIFs scale invariant features
  • This device advantageously comprises a memory space in which is stored a dictionary of SIFs; and the processing circuit is configured to compare the SIFs of said digital image (initial image) with the SIFs of said dictionary.
  • the processing circuit can be configured to process an arbitrary number of images in parallel.
  • Figure 1 is a general view of a device implementing the method according to the invention
  • FIG. 2 is a flowchart illustrating in a simplified manner steps of the method according to the invention.
  • Figure 3 is a general view illustrating the four main parameters describing the positions of a camera;
  • Figure 4 is a general view illustrating multiple comparisons between simulated images;
  • FIG. 5 is a general view illustrating a sphere in which rotation-tilt pairs are inscribed
  • FIG. 6 is a general view illustrating a distribution of the positions of the simulated tilts and rotations on the sphere of FIG. 5;
  • Figures 7 and 8 are views illustrating the difference between absolute tilts and relative tilts, or transition tilts.
  • a processing unit 1 such as a computer with software and hardware means necessary for its proper operation. It comprises in particular a processing circuit 2 such as a microprocessor or a dedicated microcontroller which is configured to process images according to the method according to the present invention. There is also a conventional memory space 3 capable of storing in particular SIFs in the form of a dictionary. This computer is equipped with a visualization monitor 4 on which the processed images can be displayed.
  • a processing circuit 2 such as a microprocessor or a dedicated microcontroller which is configured to process images according to the method according to the present invention.
  • a conventional memory space 3 capable of storing in particular SIFs in the form of a dictionary.
  • This computer is equipped with a visualization monitor 4 on which the processed images can be displayed.
  • a camera 5 is connected to the computer 1 via a connection cable. But other means of connection including wireless can be used. It is also possible to recover images previously acquired and stored in stationary storage means of the computer or laptop.
  • the flowchart illustrates the parallel processing of the two images request 6 and target 10.
  • a first simulated image is produced for a rotation torque 7.11 and tilt 8.12, and steps 7, 11 and 8 are performed several times, for example p times, 12, so as to generate p simulated images at 9 and 13.
  • each of the images undergoes the same treatment consisting in simulating all the possible distortions due to the changes of orientation of the axis of the camera, which is a two-parameter space, called longitude and latitude.
  • theta angle ⁇ is the latitude and the angle phi ⁇ the longitude.
  • the output 15 may be a list (possibly empty) of sub-image pairs of the request and of the target where there is an object recognized on the two images, as well as the affine transformation identified as making it possible to transform one of the sub-images into the other.
  • FIG. 3 illustrates the four main parameters inducing a deformation of the image taken by a camera: the camera can turn on itself by an angle ⁇ , its optical axis can adopt a theta angle ⁇ (latitude) with respect to the frontal axis, and this inclination of a theta angle is made in a vertical plane making an angle phi ⁇ (longitude) with a fixed direction.
  • the method according to the invention makes it possible to generate all the affine deformations that would be due to the changes of direction of the axis of the camera at infinity frontally observing the plane image, these deformations therefore depending on the two parameters, the longitude and the latitude, which are sampled so that the number of views generated is a few tens.
  • the simulated longitudes are more and more numerous when the latitude increases. But when the latitude increases, the images are also possibly more and more subsampled in one direction and therefore smaller and smaller, the subsampling rates then being a geometric sequence.
  • Longitude is described by a parameter ⁇ (see Figure 3).
  • the values of tilt t are logarithmically scaled and those of ⁇ arithmetically.
  • Transform A is a linear transform of the plane associated with a 2x2 matrix with four elements (a, b, c, d).
  • the application u (x, y) -> u (A (x, y)) is then interpreted as the deformation of the image that will be observed when the camera rotates on its optical axis by an angle psi ⁇ , that it slides on its optical axis while moving away (or getting closer if lambda ⁇ ⁇ l) on this axis of a factor lambda, and that its optical axis moves away from its frontal position by a combination of a change of latitude theta ⁇ and a change of longitude phi ⁇ .
  • the camera can also begin to move by a translational movement perpendicular to its optical axis, resulting in a prior translation of the image (e, f) not taken into account in the previous formula.
  • This translation (e, f), the lambda zoom ⁇ and the rotation psi ⁇ are the four parameters mastered by the state of the art.
  • the present invention relates to the manner of recognizing an image when it has also undergone the deformations caused by the changes of latitude and longitude.
  • Figure 5 illustrates a sphere on which tilts and rotations are positioned. In this figure in perspective we see the positions of the cameras that would be simulated for tilts 2, 2V2 and 4, respectively for angles 60 °, 69.30 ° and 75.52 °. There are more and more angles of rotation as the tilts increase.
  • Figure 6 illustrates a distribution of the positions of the tilts and rotations.
  • Each circle corresponds to a tilt.
  • the points indicated therefore have for coordinates sin ( ⁇ ) cos ( ⁇ ) and sin ( ⁇ ) sin ( ⁇ ).
  • the rectangles indicate the distortion of a square image caused by each tilt.
  • the visual effect is that the image rotates on the computer screen at an angle ⁇ . This operation simulates the effect that would have had a rotation around its optical axis of a camera taking the image in front view.
  • This operation simulates the result on an image u (x, y), assumed to be frontally observed by a camera at infinity, of the inclination in the x direction of the optical axis of the camera.
  • the image u (x, y) is the front view and the image v (x, y) is the oblique view after tilt t of an angle ⁇ in the direction of x.
  • This operation simulates the distance of the camera from the image, the distance to the object before the distance being in the ratio h to the distance after the distance.
  • the function G (x, y) often a Gaussian, simulates the optical convolution core of a camera.
  • a digital zoom is obtained by simple interpolation. Zooming out or zooming out is a short zoom.
  • t l /
  • SIF scale invariant feature

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Theoretical Computer Science (AREA)
  • Medical Informatics (AREA)
  • Health & Medical Sciences (AREA)
  • Databases & Information Systems (AREA)
  • Evolutionary Computation (AREA)
  • General Health & Medical Sciences (AREA)
  • Artificial Intelligence (AREA)
  • Software Systems (AREA)
  • Computing Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Multimedia (AREA)
  • Image Analysis (AREA)
  • Image Processing (AREA)
  • Studio Devices (AREA)

Abstract

L'invention concerne un procédé pour la reconnaissance d'objets dans au moins une image digitale dans lequel : a) à partir de ladite image digitale, on simule une pluralité de rotations digitales et au moins deux tilts digitaux différents de 1, de façon à élaborer pour chaque couple rotation-tilt, une image simulée; et b) on applique un algorithme produisant des valeurs invariantes par translation, rotation et zoom sur les images simulées de façon à déterminer des caractéristiques locales dites SIFs (« scale invariant features ») que l'on utilise pour la reconnaissance d'objets. A l'étape b, on peut utiliser la méthode SIFT.

Description

" Procédé et dispositif de reconnaissance invariante-affine de formes."
La présente invention concerne un procédé et un dispositif pour la reconnaissance d'objets dans au moins une image digitale.
D'une façon générale, un procédé de reconnaissance de formes a pour objet de reconnaître un objet ou un type d'objet qui a été pris en photo quand la position relative de l'objet et du dispositif de prise de vue réel ou simulé sont inconnus, ou quand l'objet s'est éventuellement déformé. L'objet lui- même peut être un objet graphique et non physique (comme par exemple un logo digital ou le résultat d'une simulation). Pour simplifier nous appellerons dans la suite « caméra » le dispositif de prise de vue (ou de simulation de prise de vue), mais l'invention concerne toute acquisition d'images, et toutes distorsions ou déformations géométriques de la vue d'un objet entraînées par le changement de position relativement à l'objet de la caméra, ou par les particularités du dispositif d'acquisition ou de simulation d'images. De plus les objets photographiés ou simulés n'ont pas besoin d'être identiques, il suffit qu'ils soient semblables, une situation courante pour des objets issus d'une production industrielle ou graphique. Une ou plusieurs images de l'objet à reconnaître sont à disposition : ce sont les images « requêtes ». L'image ou les images où l'objet est recherché ne le contiennent pas forcément. Le but est de trouver des indices fiables pour savoir si l'objet est présent dans ces images analysées, et de donner sa position dans l'image.
La première simplification proposée par toutes les méthodes traitant le problème de reconnaissance est de supposer que l'objet a un relief assez régulier pour que l'on puisse interpréter les déformations locales dans les images cibles comme des déformations affines planaires de l'image requête. La plupart des objets physiques d'intérêt sont en effet des volumes dont la surface présente des faces planes ou légèrement courbées. Les exceptions sont rares. Comme exemple d'exception, citons un arbre sans feuilles, dont l'aspect peut changer drastiquement par un changement d'angle de vue, ou les remous d'un liquide. Or, toute déformation régulière au sens mathématique du terme (différentiable) est, localement dans l'image, proche d'une déformation affine. C'est en particulier le cas pour la déformation apparente de l'image optique d'un objet assez régulier, quand cette déformation apparente dans l'image est causée par le mouvement de la caméra, ou par les distorsions optiques de la caméra, ou par le mouvement de l'objet, voire par une déformation progressive de l'objet lui-même. Par exemple dans le cas d'un objet plat, la déformation de son image causée par un changement de position de la caméra l'observant est une homographie plane, qui est en tout point tangente à une application affine. Si de plus la caméra est assez loin de l'objet observé, cette déformation de l'image ressemble de plus en plus à une transformation affine globale. Réciproquement, toute transformée affine du plan de l'image de déterminant positif peut être interprétée comme une déformation de l'image due au mouvement dans l'espace d'une caméra observant l'image et située loin de l'image (virtuellement à l'infini). Rappelons qu'une déformation affine du plan de coordonnées (x,y) s'écrit sous la forme x'=ax+by+e, y'=cx+dy+f, et les paramètres a, b, c, d forment une matrice à deux lignes et deux colonnes que nous noterons A. La déformation affine d'une image u(x,y) s'écrit donc u (x',y')= u(A(x,y) +(e,f))
Pour les raisons données ci-dessus, le problème de la reconnaissance des formes peut être réduit à la recherche de caractéristiques locales d'images qui soient invariantes modulo une transformation affine. Ces caractéristiques sont alors robustes aux déformations locales apparentes entraînées par les mouvements relatifs de l'objet et de la caméra, ainsi qu'aux distorsions entraînées par le dispositif d'acquisition, telles que par exemple la distorsion optique d'une lentille, et finalement aux distorsions dues aux déformations de l'objet lui-même.
Dans la suite, on utilise « tilt » et « digital » qui sont des termes couramment utilisés par l'homme du métier et qui signifient respectivement inclinaison et numérique. On utilise également SIF et SIFT qui sont des abréviations connues par l'homme du métier et qui signifient respectivement « scale invariant feature » et « scale invariant feature transform», soit « caractéristique invariante en échelle » et « transformée de caractéristique invariante en échelle ».
On connaît le document US 671 1293 (Lowe) qui décrit une méthode dite méthode SIFT pour « scale invariant feature transform » permettant de reconnaître des objets sur une image prise de manière frontale par une caméra. Dans ce document US 671 1293, on considère qu'explorer tout l'espace affine serait prohibitif et non efficace. Lowe remarque enfin que le défaut d'invariance de sa méthode SIFT pourrait être compensé en prenant des vues réelles des objets 3D éloignées les unes des autres de 30 degrés.
Le document « Cloth Motion Capture », de D. Pritchard et W. Heidrich, Eurographics 2003/ volume 22, Number 3, décrit une méthode pour déterminer des caractéristiques SIFT, dans laquelle, à partir d'une image initiale prise de manière frontale, on élabore quatre images simulées avec un tilt égal à deux. La première image simulée est obtenue pour un tilt réalisé selon l'horizontal, la seconde selon la verticale, les troisième et quatrième selon deux axes de 45 degrés. Cette méthode prévoit donc quatre images simulées de façon à améliorer la reconnaissance.
La présente invention a pour but un nouveau procédé de reconnaissance d'une portion d'une image planaire qui a subi une transformation affine arbitraire. L'invention a aussi pour but de permettre la reconnaissance d'objet dans une image pour laquelle la prise de vue est oblique, en comparaison à une prise de vue frontale face à l'objet, ou également oblique. L'invention a donc pour but d'améliorer le taux de reconnaissance quelles que soient les prises de vues..
On atteint au moins l'un des objectifs précités avec un procédé pour la reconnaissance d'objets dans au moins une image digitale dans lequel : a) à partir de ladite image digitale, on simule une pluralité de rotations digitales et au moins deux tilts digitaux différents de 1, de façon à élaborer pour chaque couple rotation-tilt, une image simulée, et b) on applique un algorithme produisant des valeurs invariantes par translation, rotation et zoom sur les images simulées de façon à déterminer des caractéristiques locales dites SIFs (« scale invariant features ») que l'on utilise pour la reconnaissance d'objets. En d'autres termes, à partir de l'image digitale, on simule plusieurs changements de directions d'axe optique d'une caméra observant l'image digitale à l'infini. Bien que chaque position de la caméra soit définie par un couple rotation-tilt, l'homme du métier comprendra aisément que d'autres transformations plus ou moins complexes peuvent être utilisées pour définir une position de la caméra. Néanmoins, l'invention est remarquable par le fait - A - que tout changement d'orientation de l'axe de la caméra peut se résumer à une rotation suivie d'un tilt.
Le procédé selon la présente invention est basé sur l'observation que toute transformation affine du plan peut être interprétée comme une transformation de l'image due à un changement de position d'une caméra à l'infini. Grâce à cette interprétation on peut décomposer une transformation affine en le produit:
-d'un mouvement de la caméra le long de l'axe optique, ou zoom (1 paramètre), -d'une translation parallèlement au plan focal (2 paramètres),
-d'une rotation axiale de la caméra (1 paramètre),
-et d'un changement de direction d'axe optique de la caméra (2 paramètres).
Des algorithmes de l'art antérieur, tels que la méthode SIFT, permettent de reconnaître une image pour laquelle les trois premières transformations sont arbitraires. Elles correspondent aux quatre paramètres de rotation axiale de la caméra, de zoom, et de translation parallèlement au plan focal (et donc perpendiculairement à l'axe optique). La méthode SIFT permet de déterminer des SIFs (« scale invariant features »), c'est-à-dire plus précisément des caractéristiques invariantes par zoom, translation et rotation de l'image, mais ne tient pas compte des deux derniers paramètres relatifs au changement de direction d'axe optique de la caméra. Lowe prévoit des vues supplémentaires pour améliorer la sensibilité de la méthode SIFT, mais il s'agit de vues réelles, ce qui implique des manipulations supplémentaires ainsi qu'une augmentation considérable des données à traiter. Pritchard prévoit uniquement quatre images simulées car on considérait qu'aller au- delà serait contreproductif et prohibitif en termes de temps de calcul. La présente invention va au-delà d'un préjugé généralement admis, selon lequel le temps de calcul serait prohibitif si l'on augmentait le nombre d'images simulées.
Avec le procédé selon la présente invention, on peut simuler avec une précision suffisante toutes les distorsions de l'image dues aux variations des deux paramètres non traités dans la méthode SIFT, qui sont les paramètres de changement de direction de l'axe optique de la caméra. Avec l'invention, on élabore d'abord plusieurs images simulées en fonction desdits deux derniers paramètres que l'on décrit par une rotation et un tilt. En particulier, les couples rotation-tilt peuvent s'inscrire dans une demi-sphère au-dessus de l'image digitale. On considère que la rotation et le tilt correspondent respectivement à la longitude et la latitude dans l'espace. Pritchard décrit en fait quatre rotations et une seule valeur de tilt à partir d'une image frontale. Avec l'invention, les images initiales peuvent être obtenues par des prises de vues non frontales, c'est-à-dire obliques jusqu'à environ 80 degrés. Les systèmes de l'art antérieur permettent de reconnaître des objets avec une tolérance pour des changements d'orientation d'axe de la caméra entraînant des tilts réels allant jusqu'à 3 ou 4. Le procédé selon l'invention peut traiter les tilts jusqu'à une valeur dépassant 40. En effet, dans la situation où une caméra a pris deux vues d'un objet plat avec des tilts t et t', la simulation de l'une de ces vues obliques à partir de l'autre peut demander de simuler un tilt allant jusqu'à la valeur tt'. Par exemple pour des latitudes de 80°, le tilt est de 5.76 et le tilt combiné quand les vues obliques ont une différence de longitude égale à 90° est égal à 5.762=33.2. Un tilt très supérieur à 2, allant jusqu'à 30 par exemple ou plus est donc possible, et le procédé selon l'invention permet de reconnaître de telles vues obliques l'une à partir de l'autre.
Ce procédé est donc capable de reconnaître toutes les vues possibles de l'image à l'infini, puisque les vues simulées n'ont plus besoin que d'un algorithme de reconnaissance invariant par translation, rotation et zoom, problème bien maîtrisé dans l'état de l'art qui sait calculer des SIFs.
Le principe sur lequel se base le procédé selon l'invention n'est pas de supposer que toute l'image a subi une seule transformation affine, ce qui n'est vrai que pour un objet complètement plan et une caméra à l'infini. Par contre, en appliquant un algorithme de reconnaissance prenant en compte toutes les transformations affines de l'image on obtient bien une reconnaissance complète, car chaque déformation est localement tangente à une application affine. On peut résumer la situation en disant que la simulation de toutes les transformations affines suffit pour simuler effectivement toutes les déformations locales de l'image. Selon un mode de mise en œuvre de l'invention, le procédé est appliqué à une image dite requête et une image dite cible, les SIFs des images simulées de la requête étant comparés aux SIFs des images simulées de la cible de façon à reconnaître des objets semblables ou identiques entre la requête et la cible.
A titre d'exemple non limitatif, lorsqu'on applique le procédé selon l'invention à une ou plusieurs images dites requêtes et une ou plusieurs images dites cibles, les SIFs relatifs à la requête peuvent être déterminés au cours d'une étape préalable d'étalonnage de façon à constituer un dictionnaire de SIFs. Et les SIFs relatifs aux cibles peuvent être respectivement déterminés au cours d'une étape de fonctionnement pendant laquelle on compare les SIFs obtenus à partir de chaque cible aux SIFs dudit dictionnaire.
Pour déterminer empiriquement un nombre et des positions optimaux des couples rotation-tilt à réaliser afin de garantir des résultats acceptables, on réalise le procédé selon l'invention dans lequel la requête contient une prise de vue quelconque d'un objet de forme semblable ou identique à la forme d'un autre objet contenu dans la cible sous une prise de vue quelconque, et on détermine des couples rotation-tilt, c'est à dire ce nombre optimum et ces positions optimales comme étant ceux pour lesquels les SIFs des deux objets sont semblables, pour un grand nombre d'objets testés.
Le procédé selon l'invention prévoit d'élaborer un même nombre d'images simulées pour la requête et pour la cible, et pour les mêmes couples rotation-tilt. Mais il prévoit également le cas où on élabore un nombre différent d'images simulées pour la requête et pour la cible, notamment avec des tilts différents ou identiques.
Avantageusement, le nombre de rotations par tilt augmente en même temps que la valeur du tilt augmente. De préférence, on définit le tilt comme une fonction de la latitude dans une demi-sphère au-dessus de l'image digitale, et l'écart de latitude entre deux tilts consécutifs diminue en même temps que le tilt augmente. En particulier, la latitude peut être mesurée par un paramètre θ allant de 0 à 90 degrés, ou alternativement par un paramètre de tilt défini par t= l/| cos(θ) | . Ces caractéristiques permettent d'avoir des positions simulées de plus en plus rapprochées de la caméra lorsque la latitude tend vers les 90°. Selon une caractéristique avantageuse de l'invention, pour une rotation donnée, les tilts considérés forment approximativement, c'est-à-dire avec une tolérance, une suite géométrique finie 1, a, a2, a3, ... , a", a étant un nombre plus grand que 1. A titre d'exemple non limitatif, a est de l'ordre de racine de 2 (V2) et n peut aller de 2 à 6 si les couples rotation-tilt sont appliqués aussi bien sur la cible que sur la requête, et de 2 à 12 si les couples rotation-tilt sont appliqués sur une seule des deux images.
Selon une autre caractéristique avantageuse de l'invention, pour un tilt t donné, les rotations digitales, par exemple à partir du tilt t =a, forment approximativement, c'est-à-dire avec une tolérance, une suite arithmétique 0, b/t, 2b/t, ..., kb/t degrés, avec b en degrés et k un nombre entier.
De préférence, b est de l'ordre de 72 degrés, et k est la dernière valeur entière telle que kb/t soit inférieur àl80 degrés. Avec ces valeurs typiques, pour chaque tilt testé t on simule (180/72). t images= 2,5.f images.
Avantageusement, appliquer un tilt t consiste à sous-échantillonner l'image digitale dans une direction d'une valeur égale à t, ce qui divise sa surface par t. On peut également appliquer un tilt en combinant un sous- échantillonnage de l'image digitale selon une direction avec un sur- échantillonnage selon une direction orthogonale à la précédente.
Pour éviter que la surface totale simulée n'excède trop celle de l'image initiale, on peut prendre par exemple a= racine de 2 et /7=4. Si chaque tilt t est obtenu par sous-échantillonnage, cela divise la surface de l'image après tilt par t. Donc on simule pour chaque t des images dont la surface totale est 18O.t/(72.t) = 2,5 fois la surface de l'image initiale. La surface traitée est donc égale à 2.5 fois la surface de l'image initiale multipliée par le nombre de tilts. La surface simulée est donc 2, 5. /7=10 fois celle de l'image initiale. Si toutefois on applique le procédé selon l'invention à des zooms arrière d'un facteur 3 des images requête et cible, la surface simulée est d'à peine 10/9 = 1.11 fois la surface initiale. Donc le procédé selon l'invention prend un temps comparable à la méthode SIFT, par exemple, tout en permettant la reconnaissance de vues obliques jusqu'à un tilt de transition de 16. Toutefois, un tilt peut être simulé en combinant un sur-échantillonnage dans une direction et un sous-échantillonnage dans la direction orthogonale, de sorte que la surface de l'image reste constante et ne diminue pas (voir définition du tilt plus loin).
Ainsi, avec le procédé selon l'invention, simuler toutes les vues dépendant de deux paramètres en conservant un temps de calcul et une mémoire raisonnable est rendu possible grâce au fait que l'espace des deux paramètres rotation et tilt est échantillonné avec assez peu de valeurs pour chaque paramètre, et que la simulation des distorsions dues aux vues obliques peut faire diminuer la taille des images par sous-échantillonnage. Cela permet de générer virtuellement toutes les vues possibles à une précision donnée, tout en n'étendant pas trop la capacité mémoire requise.
Selon un mode de réalisation avantageux de l'invention, le procédé selon l'invention peut s'appliquer à ladite image digitale en comparaison avec la même image digitale ou une transformée de celle-ci, par exemple une symétrie axiale, de façon à déterminer dans cette image digitale des symétries, des formes répétées ou des formes présentant des périodicités.
Suivant un autre aspect de l'invention, il est prévu un dispositif pour la mise en œuvre d'un procédé pour la reconnaissance d'objets dans au moins une image digitale selon l'invention. Ce dispositif comprend un circuit de traitement configuré pour : a) appliquer, à partir de ladite image digitale, une pluralité de rotations digitales et au moins deux tilts digitaux t différents de 1 de façon à élaborer pour chaque couple rotation-tilt, une image simulée, et b) appliquer un algorithme invariant par translation, rotation et zoom sur les images simulées de façon à déterminer des caractéristiques locales dites SIFs (« scale invariant features ») que l'on utilise pour la reconnaissance d'objets.
Ce dispositif comprend avantageusement un espace mémoire dans lequel est stocké un dictionnaire de SIFs ; et le circuit de traitement est configuré de façon à comparer les SIFs de ladite image digitale (image initiale) aux SIFs dudit dictionnaire.
Selon l'invention, le circuit de traitement peut être configuré de façon à traiter un nombre arbitraire d'images en parallèle. D'autres avantages et caractéristiques de l'invention apparaîtront à l'examen de la description détaillée d'un mode de mise en œuvre nullement limitatif, et des dessins annexés, sur lesquels :
La figure 1 est une vue générale d'un dispositif mettant en œuvre le procédé selon l'invention ;
La figure 2 est un organigramme illustrant de façon simplifiée des étapes du procédé selon l'invention ;
La figure 3 est une vue générale illustrant les quatre paramètres principaux décrivant les positions d'une caméra ; La figure 4 est une vue générale illustrant des comparaisons multiples entre images simulées ;
La figure 5 est une vue générale illustrant une sphère dans laquelle s'inscrivent des couples rotation-tilt ;
La figure 6 est une vue générale illustrant une répartition des positions des tilts et rotations simulés sur la sphère de la figure 5 ;
Les figures 7 et 8 sont des vues illustrant la différence entre tilts absolus et tilts relatifs, ou tilts de transition.
Sur la figure 1, on voit une unité de traitement 1 telle qu'un ordinateur doté de moyens logiciels et matériels nécessaires pour son bon fonctionnement. Il comprend notamment un circuit de traitement 2 tel qu'un microprocesseur ou un microcontrôleur dédié qui est configuré de façon à traiter des images selon le procédé selon la présente invention. On distingue également un espace mémoire 3 conventionnel apte à stocker notamment des SIFs sous la forme d'un dictionnaire. Cet ordinateur est équipé d'un moniteur 4 de visualisation sur lequel peuvent s'afficher les images traitées.
Une caméra 5 est reliée à l'ordinateur 1 via un câble de connexion. Mais d'autres moyens de connexion notamment sans fil peuvent être utilisés. On peut aussi récupérer des images préalablement acquises et stockées dans des moyens de stockages fixes de l'ordinateur ou portable.
Bien que l'invention n'y soit pas limitée, on va maintenant décrire le procédé de reconnaissance selon l'invention appliqué pour la reconnaissance d'objets entre une image cible et une image requête.
Sur la figure 2, l'organigramme illustre le traitement en parallèle des deux images requête 6 et cible 10. A partir des deux images requête 6 et cible 10, on élabore une première image simulée pour un couple de rotation 7,11 et tilt 8,12, et on réalise plusieurs fois, par exemple p fois, les étapes 7,11 et 8,12, de façon à générer p images simulées en 9 et 13. En d'autres termes, chacune des images subit le même traitement consistant à simuler toutes les distorsions possibles dues aux changements d'orientation de l'axe de la caméra, ce qui est un espace à deux paramètres, qu'on appelle longitude et latitude. Sur la figure 3 par exemple, l'angle thêta θ est la latitude et l'angle phi φ la longitude. Ces images simulées sont faites pour un nombre fini p de paires de longitudes et de latitudes, avec un échantillonnage qui rend le nombre de vues effectivement simulées petit (quelques dizaines), tout en garantissant que les quelques dizaines d'images simulées restent proches de toute autre vue possible. A l'étape 14 sur la figure 2, les images ainsi simulées sont ensuite comparées entre elles par l'un quelconque des algorithmes déjà existants qui réalisent une reconnaissance efficace modulo une rotation de l'image ( = rotation de la caméra autour de son axe optique), une translation ( = mouvement de la caméra perpendiculaire à son axe) et un zoom ( = mouvement de la caméra sur son axe optique). Un tel algorithme est notamment l'algorithme SIFT tel que décrit dans le document US 671 1293. Sur la figure 4, on voit une illustration des comparaisons multiples effectuées sur les images simulées. Les deux images requête A et cible B symbolisées par deux carrés, entourées par leurs vues simulées (des parallélogrammes) obtenues par deux tilts et les rotations associées. Les flèches joignant des parallélogrammes d'une des images à quelques parallélogrammes de l'autre indiquent que l'on fait des comparaisons des vues simulées d'une image avec des vues simulées de l'autre.
La sortie 15 peut être une liste (éventuellement vide) de paires de sous-images de la requête et de la cible où figure un objet reconnu sur les deux images, ainsi que la transformation affine identifiée comme permettant de transformer une des sous-images en l'autre.
La figure 3 illustre les quatre paramètres principaux induisant une déformation de l'image prise par une caméra : la caméra peut tourner sur elle-même d'un angle psi ψ, son axe optique peut adopter un angle thêta θ (latitude) par rapport à l'axe frontal, et cette inclinaison d'un angle thêta est faite dans un plan vertical faisant un angle phi φ (longitude) avec une direction fixée.
Le procédé selon l'invention permet de générer toutes les déformations affines qui seraient dues aux changements de direction de l'axe de la caméra à l'infini observant frontalement l'image plane, ces déformations dépendant donc des deux paramètres, la longitude et la latitude, qui sont échantillonnés de sorte que le nombre de vues généré soit de quelques dizaines. Les longitudes simulées sont de plus en plus nombreuses quand la latitude croît. Mais quand la latitude croît, les images sont aussi éventuellement de plus en plus sous-échantillonnées dans une direction et donc de plus en plus petites, les taux de sous-échantillonnage étant alors une suite géométrique.
De manière encore plus précise, la latitude est mesurée par un paramètre θ allant de 0 à 90 degrés, ou alternativement par un paramètre de tilt défini par t= l/| cos(θ) | . La longitude est décrite par un paramètre φ (voir figure 3). Les valeurs du tilt t sont échelonnées logarithmiquement et celles de φ arithmétiquement.
On peut définir le déplacement de la caméra d'une position à une autre par une transformée A définie par :
fcosψ - sinψlft OTcosφ - sinφ A = HxR1 (V)T1R2 (^) = I Ύ
|_sinψ cosψ J[O l_||_sinφ cosφ
La transformée A est une transformée linéaire du plan associée à une matrice 2x2 à quatre éléments (a, b, c, d). Etant donnée une image u(x,y), interprétée comme une image vue frontalement par une caméra optique, l'application u(x,y) -> u(A(x,y)) s'interprète alors comme la déformation de l'image qui sera observée quand la caméra tourne sur son axe optique d'un angle psi ψ, qu'elle glisse sur son axe optique en s'éloignant (ou se rapprochant si lambda λ< l) sur cet axe d'un facteur lambda, et que son axe optique s'éloigne de sa position frontale par une combinaison d'un changement de latitude thêta θ et d'un changement de longitude phi φ. La caméra peut aussi commencer par se déplacer par un mouvement de translation perpendiculaire à son axe optique, ce qui entraîne une translation préalable de l'image (e,f) non prise en compte dans la formule précédente. Cette translation (e, f), le zoom lambda λ et la rotation psi ψ sont les quatre paramètres maîtrisés par l'état de l'art. La présente invention porte sur la manière de reconnaître une image quand elle a subi en plus les déformations provoquées par les changements de latitude et de longitude. La figure 5 illustre une sphère sur laquelle sont positionnés des tilts et des rotations. Sur cette figure en perspective on voit les positions des caméras qui seraient simulées pour les tilts 2, 2V2 et 4, soit respectivement pour les angles 60°, 69.30° et 75.52°. Il y a de plus en plus d'angles de rotation quand les tilts augmentent. La figure 6 illustre une répartition des positions des tilts et rotations.
Chaque cercle correspond à un tilt. Le cercle le plus intérieur est pour le tilt associé à thêta θ= 45°, et les cercles successifs correspondent à thêta θ=60, 70, 75 et 80°. Plus le tilt augmente, et plus il est nécessaire d'augmenter le nombre de positions sur le cercle, c'est-à-dire le nombre de longitudes phi φ. Les points indiqués ont donc pour coordonnées sin(θ)cos(φ) et sin(θ) sin(φ). Les rectangles indiquent la déformation d'une image carrée provoquée par chaque tilt.
Le procédé selon l'invention fait intervenir un certain nombre de termes connus par l'homme du métier et qui sont rappelés ci- dessous :
Rotation de l'image digitale u(x,y) : calcul, par interpolation à partir des valeurs u(x,y) aux pixels (x,y) de l'image, des valeurs v(x,y) = u(R(x,y)) où R est une rotation planaire d'angle phi, décrite par une matrice à deux lignes et deux colonnes de paramètres (cos (φ), -sin(φ), sin(φ), cos(φ)). L'effet visuel est que l'image tourne sur l'écran de l'ordinateur d'un angle φ. Cette opération simule notamment l'effet qu'aurait eu une rotation autour de son axe optique d'une caméra prenant l'image en vue frontale.
Tilt de l'image digitale dans la direction de x : on pose v(x,y) = u(xa,y/b), et ab= t est le « facteur de tilt », en abrégé le « tilt ». Cette opération simule le résultat sur une image u(x,y), supposée observée frontalement par une caméra à l'infini, de l'inclinaison dans la direction de x de l'axe optique de la caméra. L'angle de l'axe optique avec la direction normale est l'une des deux valeurs thêta θ comprises entre -90° et +90° telles que t= l/| cos(θ) | . L'image u(x,y) est la vue frontale et l'image v(x,y) est donc la vue oblique après tilt t d'un angle θ dans la direction de x. Sur l'image digitale, le tilt peut être obtenu en suréchantillonnant l'image d'un facteur b dans la direction de y, et en sous-échantillonnant l'image d'un facteur a dans la direction de x, où b est un facteur arbitraire entre 1 et t. Si a = t, b= l, on a juste un sous-échantillonnage dans la direction de x, et si a = l, b=t, on a juste un sur-échantillonnage dans la direction de y. En cas de sous- échantillonnage, l'image doit être préalablement lissée dans la direction de x par convolution de l'image avec un filtre passe-bas unidimensionnel. Si a=t, et b= l, l'image digitale après tilt a une surface divisée par t (et la surface ne change pas si a=Vt, b=Vt).
Zoom arrière de l'image digitale : application à l'image u(x,y) d'une convolution v(x,y) = (G*u) par un filtre passe-bas Gh(x,y) = (l/h2)G(x/h,y/h), suivie d'un sous-échantillonnage v(x,y) = (Gh*u)(xh,yh), où h est le facteur de zoom arrière. Cette opération simule l'éloignement de la caméra par rapport à l'image, la distance à l'objet avant l'éloignement étant dans le rapport h à la distance après l'éloignement. La fonction G(x,y), souvent une gaussienne, simule le noyau de convolution optique d'une caméra. Un zoom avant numérique est obtenu par simple interpolation. Un zoom arrière ou avant est un zoom tout court.
Tilt absolu et tilt relatif: On appelle tilt absolu le facteur t= l/|cos(θ) | de compression de l'image dans une direction entraîné par le passage de la caméra d'une position frontale face à un objet plan, à une vue oblique. Supposons maintenant qu'un même objet plan ait été pris en photo par une caméra dans deux positions dont l'axe optique passe par le même point de l'image. La position de l'axe de la première caméra est décrite par deux angles θ et φ et celle de la seconde par deux angles θ' et φ'. Quand φ=φ', le tilt qu'il faut appliquer à l'une des deux images pour passer directement à l'autre (à un zoom près) est égal au rapport t'/t, où t' désigne le plus grand des deux tilts, et t le plus petit. Quand φ=φ'+90°, ce même tilt devant être appliqué à l'une des deux images u(tx,y) pour passer à l'autre u(x,t'y) est maximal et égal au produit tt'. Ce fait explique pourquoi, pour comparer des vues obliques, on simule avantageusement des tilts importants pouvant dépasser 40. Sur les figures 7 et 8 notamment, on voit de manière illustrée la différence entre tilts absolus et tilts relatifs, ou de transition. A gauche, sur la figure 7, on voit la caméra dans deux positions correspondant aux valeurs de θ =30° et 60°, avec et φ=φ'. L'un des tilts est égal à 2, l'autre à 2/V3, et le tilt relatif, de transition pour passer de v à v', est donc V3, qui est plus petit que le tilt qui passait de u à v'. Donc, quand les tilts se font dans le même plan (φ=φ'), on voit que les tilts à simuler sont plus petits que les tilts originaux. A droite, le plan de tilt a changé : on a φ-φ'=90°, et les tilts sont t=2 de u à v , et t'=4 de u à v'. Dans ce cas, les tilts se multiplient, et le tilt relatif, de transition de v à v', est 2 x4 =8.
SIF (« scale invariant feature ») : nombres ou ensembles de nombres attachés à une image digitale et qui changent peu quand on fait tourner l'image, ou quand on la translate, et qui peuvent aussi se maintenir avec peu de changement quand un zoom est appliqué à l'image. Les SIFs permettent donc de reconnaître des pixels dans l'image indépendamment de leur position, recadrage, orientation, et zoom. Un exemple classique de tels indicateurs sont obtenus par la méthode SIFT (« scale invariant feature transform »).
La présente invention peut efficacement s'appliquer à l'un des domaines suivants :
- comparaison de différentes images d'un film ou des images de plusieurs films ;
- comparaison de différentes images prises par une caméra ou plusieurs caméras placées dans des positions successives ou simultanées ;
- utilisation à bord d'un véhicule équipé de caméras, par exemple pour sa navigation ;
- détection des symétries obliques dans une image par l'application du procédé à l'image et à l'image symétrisée par rapport à une droite arbitraire ;
- reconnaissance des êtres animés (humains, animaux, machines) ; comparaison ou classement des photographies, peintures, et généralement œuvres d'art plastiques ;
- organisation et gestion de grandes bases de données d'images individuelles ou collectives ; - reconstruction de relief d'une scène ou d'un objet à partir de plusieurs vues ;
- calibration ou étalonnage d'images prises par une ou plusieurs caméras ; -cartographie, plane, ou en relief par comparaison de vues aériennes, spatiales, ou terrestres ; - reconnaissance de symboles, mots, caractères d'imprimerie ou logos ; et
- application à un film pour suivre à la trace un objet présent dans toute une séquence.
Bien sûr, l'invention n'est pas limitée aux exemples qui viennent d'être décrits et de nombreux aménagements peuvent être apportés à ces exemples sans sortir du cadre de l'invention.

Claims

REVENDICATIONS
1. Procédé pour la reconnaissance d'objets appliqué à une image digitale dite requête et à une image digitale dite cible dans lequel : a) à partir de chaque image digitale, on simule une pluralité de rotations digitales et au moins deux tilts digitaux différents de 1, de façon à élaborer pour chaque couple rotation-tilt, une image simulée, et b) on applique un algorithme produisant des valeurs invariantes par translation, rotation et zoom sur les images simulées de façon à déterminer des caractéristiques locales dites SIFs (« scale invariant features ») que l'on utilise pour reconnaître des objets semblables ou identiques entre la requête et la cible.
2. Procédé selon la revendication 1, caractérisé en ce que la requête contient une prise de vue quelconque d'un objet de forme semblable ou identique à la forme d'un autre objet contenu dans la cible sous une prise de vue quelconque ; et en ce qu'on détermine des couples rotation-tilt pour lesquels les SIFs des deux objets sont semblables.
3. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'on élabore un même nombre d'images simulées pour la requête et pour la cible, et pour les mêmes couples rotation-tilt.
4. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'on élabore un nombre différent d'images simulées pour la requête et pour la cible.
5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le nombre de rotations par tilt augmente en même temps que la valeur du tilt augmente.
6. Procédé selon l'une quelconque des revendications précédentes, dans lequel procédé le tilt est fonction de la latitude dans une demi-sphère au- dessus de l'image digitale ; caractérisé en ce que l'écart de latitude entre deux tilts consécutifs diminue en même temps que le tilt augmente.
7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que les tilts considérés forment approximativement une suite géométrique finie 1, a, a2, a3, ... , a", a étant un nombre plus grand que 1.
8. Procédé selon la revendication 7, caractérisé en ce que a est de l'ordre de racine de 2 et n allant de 2 à 6 si les couples rotation-tilt sont appliqués aussi bien sur la cible que sur la requête, et de 2 à 12 si les couples rotation-tilt sont appliqués sur une seule des deux images.
9. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que, pour un tilt t donné, les rotations digitales forment une suite approximativement arithmétique 0, b/t, 2b/t, ..., kb/t degrés, avec b en degrés et k un nombre entier.
10. Procédé selon la revendication 9, caractérisé en ce que b est de l'ordre de 72 degrés, et k la dernière valeur entière telle que kb/t soit inférieur à 180 degrés.
11. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'appliquer un tilt t consiste à sous-échantillonner l'image digitale dans une direction fixée d'une valeur égale à t.
12. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'appliquer un tilt t consiste à sous-échantillonner l'image digitale dans une direction fixée et à sur-échantillonner dans une direction orthogonale à la précédente.
13. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il est appliqué à une ou plusieurs images dites requêtes et une ou plusieurs images dites cibles ; et en ce que les SIFs relatifs à la requête sont déterminés au cours d'une étape préalable d'étalonnage de façon à constituer un dictionnaire de SIFs ; et en ce que les SIFs relatifs aux cibles sont respectivement déterminés au cours d'une étape de fonctionnement pendant laquelle on compare les SIFs obtenus à partir de chaque cible aux SIFs dudit dictionnaire.
14. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il est appliqué à une image digitale en comparaison avec la même image digitale ou une transformée de celle-ci, de façon à déterminer dans cette image digitale des symétries obliques, des formes répétées ou des formes présentant des périodicités.
15. Dispositif pour la mise en œuvre d'un procédé pour la reconnaissance d'objets appliqué à une image digitale dite requête et à une image digitale dite cible selon l'une quelconque des revendications précédentes, ce dispositif comprenant un circuit de traitement configuré pour : a) appliquer, à partir de chaque image digitale, une pluralité de rotations digitales et au moins deux tilts digitaux t différents de 1 de façon à élaborer pour chaque couple rotation-tilt, une image simulée, et b) appliquer un algorithme produisant des valeurs invariantes par translation, rotation et zoom sur les images simulées de façon à déterminer des caractéristiques locales dites SIFs (« scale invariant features ») que l'on utilise pour reconnaître des objets semblables ou identiques entre la requête et la cible.
16. Dispositif selon la revendication 15, caractérisé en ce qu'il comprend un espace mémoire dans lequel est stocké un dictionnaire de SIFs ; et en ce que le circuit de traitement est configuré de façon à comparer les SIFs de ladite image digitale aux SIFs dudit dictionnaire.
PCT/FR2009/050923 2008-05-19 2009-05-18 Procede et dispositif de reconnaissance invariante-affine de formes Ceased WO2009150361A2 (fr)

Priority Applications (4)

Application Number Priority Date Filing Date Title
JP2011510028A JP5442721B2 (ja) 2008-05-19 2009-05-18 形状の不変量アフィン認識方法及びデバイス
EP09761912A EP2289026A2 (fr) 2008-05-19 2009-05-18 Procédé et dispositif de reconnaissance invariante-affine de formes
US12/993,499 US8687920B2 (en) 2008-05-19 2009-05-18 Method and device for the invariant-affine recognition of shapes
CN200980127996.XA CN102099815B (zh) 2008-05-19 2009-05-18 用于形状的仿射不变识别的方法和装置

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0853244 2008-05-19
FR0853244A FR2931277B1 (fr) 2008-05-19 2008-05-19 Procede et dispositif de reconnaissance invariante-affine de formes

Publications (2)

Publication Number Publication Date
WO2009150361A2 true WO2009150361A2 (fr) 2009-12-17
WO2009150361A3 WO2009150361A3 (fr) 2010-02-25

Family

ID=40352778

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2009/050923 Ceased WO2009150361A2 (fr) 2008-05-19 2009-05-18 Procede et dispositif de reconnaissance invariante-affine de formes

Country Status (7)

Country Link
US (1) US8687920B2 (fr)
EP (1) EP2289026A2 (fr)
JP (1) JP5442721B2 (fr)
KR (1) KR20110073386A (fr)
CN (1) CN102099815B (fr)
FR (1) FR2931277B1 (fr)
WO (1) WO2009150361A2 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12462422B2 (en) 2019-01-24 2025-11-04 Panasonic Intellectual Property Management Co., Ltd. Calibration method and calibration apparatus

Families Citing this family (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20110054872A1 (en) * 2009-08-31 2011-03-03 Aptina Imaging Corporation Optical simulator using parallel computations
KR101165357B1 (ko) * 2011-02-14 2012-07-18 (주)엔써즈 이미지 특징 데이터 생성 장치 및 방법
CN102231191B (zh) * 2011-07-17 2012-12-26 西安电子科技大学 基于asift的多模态图像特征提取与匹配方法
US9020982B2 (en) * 2012-10-15 2015-04-28 Qualcomm Incorporated Detection of planar targets under steep angles
CN103076943B (zh) * 2012-12-27 2016-02-24 小米科技有限责任公司 一种图标的转换方法和图标的转换装置
JP6014008B2 (ja) * 2013-11-13 2016-10-25 日本電信電話株式会社 幾何検証装置、幾何検証方法及びプログラム
CN104156413A (zh) * 2014-07-30 2014-11-19 中国科学院自动化研究所 一种基于商标密度的个性化商标匹配识别方法
US9026407B1 (en) * 2014-10-16 2015-05-05 Christine Marie Kennefick Method of making and using a material model of elements with planar faces
CN109801234B (zh) * 2018-12-28 2023-09-22 南京美乐威电子科技有限公司 图像几何校正方法及装置

Family Cites Families (33)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5161204A (en) * 1990-06-04 1992-11-03 Neuristics, Inc. Apparatus for generating a feature matrix based on normalized out-class and in-class variation matrices
US5903454A (en) * 1991-12-23 1999-05-11 Hoffberg; Linda Irene Human-factored interface corporating adaptive pattern recognition based controller apparatus
JP3244798B2 (ja) * 1992-09-08 2002-01-07 株式会社東芝 動画像処理装置
US5911035A (en) * 1995-04-12 1999-06-08 Tsao; Thomas Method and apparatus for determining binocular affine disparity and affine invariant distance between two image patterns
US5802525A (en) * 1996-11-26 1998-09-01 International Business Machines Corporation Two-dimensional affine-invariant hashing defined over any two-dimensional convex domain and producing uniformly-distributed hash keys
US6005986A (en) * 1997-12-03 1999-12-21 The United States Of America As Represented By The National Security Agency Method of identifying the script of a document irrespective of orientation
US6181832B1 (en) * 1998-04-17 2001-01-30 Mclean Hospital Corporation Methods and systems for removing artifacts introduced by image registration
US6912293B1 (en) * 1998-06-26 2005-06-28 Carl P. Korobkin Photogrammetry engine for model construction
US7016539B1 (en) * 1998-07-13 2006-03-21 Cognex Corporation Method for fast, robust, multi-dimensional pattern recognition
US6711293B1 (en) 1999-03-08 2004-03-23 The University Of British Columbia Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image
US6507661B1 (en) * 1999-04-20 2003-01-14 Nec Research Institute, Inc. Method for estimating optical flow
US6975755B1 (en) * 1999-11-25 2005-12-13 Canon Kabushiki Kaisha Image processing method and apparatus
US6771808B1 (en) * 2000-12-15 2004-08-03 Cognex Corporation System and method for registering patterns transformed in six degrees of freedom using machine vision
US7142718B2 (en) * 2002-10-28 2006-11-28 Lee Shih-Jong J Fast pattern searching
US7289662B2 (en) * 2002-12-07 2007-10-30 Hrl Laboratories, Llc Method and apparatus for apparatus for generating three-dimensional models from uncalibrated views
JP4865557B2 (ja) * 2003-08-15 2012-02-01 スカーペ テクノロジーズ アクティーゼルスカブ 有界三次元対象物の分類と空間ローカライゼーションのためのコンピュータ視覚システム
WO2005055138A2 (fr) * 2003-11-26 2005-06-16 Yesvideo, Inc. Modelisation statistique en reponse-processus d'une image visuelle permettant de determiner la similarite entre des images visuelles et utilisation de cette similarite d'images pour generer une interaction avec une collection d'images visuelles
US7697792B2 (en) * 2003-11-26 2010-04-13 Yesvideo, Inc. Process-response statistical modeling of a visual image for use in determining similarity between visual images
US7382897B2 (en) * 2004-04-27 2008-06-03 Microsoft Corporation Multi-image feature matching using multi-scale oriented patches
US7493243B2 (en) * 2004-12-27 2009-02-17 Seoul National University Industry Foundation Method and system of real-time graphical simulation of large rotational deformation and manipulation using modal warping
US7653264B2 (en) * 2005-03-04 2010-01-26 The Regents Of The University Of Michigan Method of determining alignment of images in high dimensional feature space
US7929775B2 (en) * 2005-06-16 2011-04-19 Strider Labs, Inc. System and method for recognition in 2D images using 3D class models
EP1736928A1 (fr) * 2005-06-20 2006-12-27 Mitsubishi Electric Information Technology Centre Europe B.V. Recalage robuste d'images
US7454037B2 (en) * 2005-10-21 2008-11-18 The Boeing Company System, method and computer program product for adaptive video processing
US7912321B1 (en) * 2005-12-19 2011-03-22 Sandia Corporation Image registration with uncertainty analysis
EP1850270B1 (fr) * 2006-04-28 2010-06-09 Toyota Motor Europe NV Détecteur robuste et descripteur de point d'intérêt
CN100587518C (zh) * 2006-07-20 2010-02-03 中国科学院自动化研究所 遥感影像高精度控制点自动选择方法
KR100796849B1 (ko) * 2006-09-04 2008-01-22 삼성전자주식회사 휴대 단말기용 파노라마 모자이크 사진 촬영 방법
CN100530239C (zh) * 2007-01-25 2009-08-19 复旦大学 基于特征匹配与跟踪的视频稳定方法
JP4668220B2 (ja) * 2007-02-20 2011-04-13 ソニー株式会社 画像処理装置および画像処理方法、並びにプログラム
KR100884904B1 (ko) * 2007-09-12 2009-02-19 아주대학교산학협력단 평행 투영 모델을 이용한 자기위치 인식 방법
US8090160B2 (en) * 2007-10-12 2012-01-03 The University Of Houston System Automated method for human face modeling and relighting with application to face recognition
US8004576B2 (en) * 2008-10-31 2011-08-23 Digimarc Corporation Histogram methods and systems for object recognition

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12462422B2 (en) 2019-01-24 2025-11-04 Panasonic Intellectual Property Management Co., Ltd. Calibration method and calibration apparatus

Also Published As

Publication number Publication date
US20110069889A1 (en) 2011-03-24
US8687920B2 (en) 2014-04-01
FR2931277A1 (fr) 2009-11-20
KR20110073386A (ko) 2011-06-29
CN102099815B (zh) 2014-09-17
WO2009150361A3 (fr) 2010-02-25
JP2011521372A (ja) 2011-07-21
FR2931277B1 (fr) 2010-12-31
CN102099815A (zh) 2011-06-15
JP5442721B2 (ja) 2014-03-12
EP2289026A2 (fr) 2011-03-02

Similar Documents

Publication Publication Date Title
WO2009150361A2 (fr) Procede et dispositif de reconnaissance invariante-affine de formes
EP1421442B1 (fr) Procede de capture d&#39;une image panoramique au moyen d&#39;un capteur d&#39;image de forme rectangulaire
Lumsdaine et al. Full resolution lightfield rendering
EP1386480B1 (fr) Procede de capture et d&#39;affichage d&#39;une image panoramique numerique a resolution variable
EP2923330B1 (fr) Procede de reconstruction 3d et de mosaïquage 3d panoramique d&#39;une scene
EP0977148B1 (fr) Dispositif électronique de recalage automatique d&#39;images
US20100033551A1 (en) Content-Aware Wide-Angle Images
EP2828834A2 (fr) Modèle et procédé de production de modèle 3d photo-réalistes
Jung et al. Deep360Up: A deep learning-based approach for automatic VR image upright adjustment
FR2955409A1 (fr) Procede d&#39;integration d&#39;un objet virtuel dans des photographies ou video en temps reel
CN101356546A (zh) 图像高分辨率化装置、图像高分辨率化方法、图像高分辨率化程序以及图像高分辨率化系统
WO2005010820A2 (fr) Procede et dispositif automatise de perception avec determination et caracterisation de bords et de frontieres d&#39;objets d&#39;un espace, construction de contours et applications
Chandramouli et al. Convnet-based depth estimation, reflection separation and deblurring of plenoptic images
FR3047103A1 (fr) Procede de detection de cibles au sol et en mouvement dans un flux video acquis par une camera aeroportee
EP2432660A1 (fr) Procede et dispositif pour etendre une zone de visibilite
FR2729236A1 (fr) Guidage de robot par eclairage actif
EP2994813B1 (fr) Procede de commande d&#39;une interface graphique pour afficher des images d&#39;un objet tridimensionnel
EP3018625B1 (fr) Procédé de calibration d&#39;un système de visée
WO2011033186A1 (fr) Procédé de numérisation tridimensionnelle d&#39;une surface comprenant la projection d&#39;un motif combiné
CA3230088A1 (fr) Procede de mise en relation d&#39;une image candidate avec une image de reference
WO2011033187A1 (fr) Procédé de numérisation tridimensionnelle comprenant une double mise en correspondance
WO2020094441A1 (fr) Capteur d&#39;image pour la reconnaissance optique de code(s)
EP4567755A1 (fr) Procédé et système de capture sans contact d&#39;empreinte biométrique
Kopanas Point based representations for novel view synthesis
EP3454118B1 (fr) Dispositif et procédé pour reconstruire la surface 3d du tour complet d&#39;un sujet

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 200980127996.X

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 09761912

Country of ref document: EP

Kind code of ref document: A2

WWE Wipo information: entry into national phase

Ref document number: 2011510028

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 12993499

Country of ref document: US

Ref document number: 12010502606

Country of ref document: PH

NENP Non-entry into the national phase

Ref country code: DE

ENP Entry into the national phase

Ref document number: 20107028499

Country of ref document: KR

Kind code of ref document: A

WWE Wipo information: entry into national phase

Ref document number: 2009761912

Country of ref document: EP