Abstract:
A method of 3D reconstruction of a scene, including the implementation of at least two sensors each having a series of elementary receivers arranged so as to view the scene according to distinct respective solid angles and which are each sensitive to a physical characteristic of a signal received by the receiver originating from the scene. The sensors are adapted for emitting an asynchronous stream of events indicative of a modification of the signal received by one of the elementary receivers at a given instant, as well as the implementation of a 3D reconstruction algorithm having a step of pairing elementary receivers of each of the sensors utilizing signals generated by the sensors, the pairing including pairing between them events generated by each of the sensors and temporarily close together.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This is a National Stage of International Application No. PCT/EP2012/074989 filed Dec. 10, 2012, claiming priority based on French Patent Application No. 1161320, filed Dec. 8, 2011, the contents of all of which are incorporated herein by reference in their entirety. 
     The invention relates to a method of 3D reconstruction of a scene calling upon asynchronous sensors. 
     BACKGROUND OF THE INVENTION 
     It is known practice to carry out three-dimensional reconstructions on the basis of images taken by at least two synchronized cameras taking images of the same scene. The first stereovision algorithms appeared in the 1970s. Significant progress has been made in recent years. This progress concerns increasingly effective matching algorithms. 
     The optical sensors used include elementary receivers (for example pixels of a camera) arranged in a matrix to see the scene from separate respective solid angles, and capture images of the scene at regular intervals (generally several images per second). Each image is then represented by a table of values (one per elementary receiver) each representing a physical characteristic of a signal received from the scene by the corresponding elementary sensor, for example a luminous intensity. 
     More precisely, such optical sensors generate, at each time increment t k , and for each elementary receiver placed at x,y, items of information f  k (x,y)=δ(t,t k )·f (x,y,t). where f is the luminous intensity perceived by the receiver placed at x, y, and δ is Kronecker&#39;s symbol. The item of information sent back by such a sensor is then the matrix or frame I k ={f  k (x,y)}, xεN, yεM, where N,M are the dimensions of the matrix, this information being sent at each time increment. 
     Then the matching algorithm searches these items of information for patterns that can be due to one and the same element of the scene and matches the corresponding elementary sensors together. Knowing the position of these elementary receivers thus matched, it is easy to retrieve by triangulation the point of the scene that has been seen by these two elementary receivers, and therefore to incorporate it into the 3D reconstruction of the scene. 
     Each image can represent a size of several megaoctets, and this at the rate of several images per second (typically 24 images per second), which represents a considerable bandwidth. The 3D reconstruction algorithms then carry out a search for patterns in the images taken by the various sensors at the same instant with the aim of matching together patterns corresponding to one and the same element of the scene. These algorithms require software packages that consume a good deal of power and computing time, which are not envisionable for real-time applications. 
     SUBJECT OF THE INVENTION 
     The subject of the invention is a method of 3D reconstruction of a scene allowing implementation in real time with reasonable computing means. 
     DISCLOSURE OF THE INVENTION 
     With the aim of achieving this goal, a method of 3D reconstruction of a scene is proposed, including:
         the implementation of at least two sensors each including a series of elementary receivers arranged to observe the scene from separate respective solid angles and which are each sensitive to a physical characteristic of a signal received by said receiver originating from the scene;   the implementation of a 3D reconstruction algorithm including a step of matching receivers of each of the sensors employing signals generated by the sensors;       

     According to the invention, the method includes the use of sensors that are each adapted to emit an asynchronous stream of events that are each indicative of a modification of the signal received by one of the elementary receivers at a given instant, the matching consisting in matching together events generated by each of the sensors by selecting temporally close events. 
     The use of such sensors makes it possible to spectacularly decrease the output of information from the sensors and considerably simplifies the matching. The matching of temporally close events in fact comes down to matching the receivers on each of the sensors that have generated the events thus matched. The matching is very simple to implement, with modest processing means. 
     The 3D reconstruction method of the invention can be implemented with reasonable means, for example a simple personal computer equipped with suitable data acquisition cards. 
    
    
     
       DESCRIPTION OF THE FIGURES 
       The invention will be better understood in the light of the figures of the appended drawings, among which: 
         FIG. 1  is a diagram illustrating the focal planes of two asynchronous sensors observing one and the same scene according to the invention; 
         FIG. 2  is a timing diagram of events detected by the sensors in  FIG. 1 ; 
         FIG. 3  is a diagram illustrating the focal planes of three asynchronous sensors observing one and the same scene according to the invention; 
         FIG. 4  is a timing diagram of events detected by the sensors in  FIG. 3 . 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In the mode of implementation detailed below, with reference to  FIG. 1 , a scene is filmed using two sensors C 1  and C 2  each including a CCD or CMOS camera (called right and left respectively). Each camera includes MxN pixels, each comparable to an elementary sensor. Each pixel sees the scene from a given solid angle and is sensitive to the luminous intensity received in this solid angle.  FIG. 1  illustrates the focal planes of the two sensors C 1  and C 2 . 
     However, in the context of the invention, the cameras are not used in a conventional manner. Rather than using the camera to make it generate frames I k ={f  k (x, y)},xεN, yεM at regular intervals, each elementary information item of which represents the luminous intensity received by each pixel at the instant t k , it is a derivative item of information that is of interest here, in this case the direction of variation of the luminous intensity received by each of the pixels. The quantity of interest is thus 
               e   ⁡     (     x   ,   y   ,   t     )       =     sign   ⁢       ∂   f       ∂   t       ⁢     (     x   ,   y   ,   t     )             
which can take two values: −1 if the luminous intensity of the signal received by the pixel is decreasing, and 1 if the luminous intensity of the signal received by the pixel is increasing. This quantity is sampled for instants of sampling t k :
 
                 e   k     ⁡     (     x   ,   y     )       =         δ   ⁡     (     t   ,     t   k       )       ·   sign     ⁢       ∂   f       ∂   t       ⁢     (     x   ,   y   ,   t     )             
where δ is Kronecker&#39;s symbol.
 
     Thus, this event is indicative of an increase (+1) or of a decrease (−1) in the luminous intensity perceived by the pixel P x,y  situated at x,y at time t k . 
     Such an item of information can for example be generated by post-processing of the information about the received luminous intensity from each of the pixels of the camera, which is embedded on a digital processing card connected to the camera and which is embedded either in the camera itself, or in the computer to which the camera is linked. 
     The item of matrix information I k ={f  k (x,y)}, xεN, yεM usually generated by such cameras and employed for 3D reconstruction in known methods is then replaced according to the invention by an item of matrix information E k ={e k (x,y)},xεN,yεM. 
     Such an item of matrix information clearly consumes less memory space than a conventional image, since each data item of the matrix information item is easily contained in a single octet. 
     However, rather than transmitting the information items in matrix form, it is possible, according to a particularly advantageous aspect of the invention, to transmit an asynchronous stream of events E i , each event being identified by:
         data enabling the identification of the pixel whose quantity e has changed value, in this case the coordinates x,y of the corresponding pixel P xy ;   the instant of the change of value;   an indicator of the modification of the signal perceived by the pixel, in this case taking the value (−1;1) reached by the quantity e upon this change (hereinafter called value of the event).       

     This asynchronous stream can be represented by the following notation: 
     {x 1 ,y 1 ,t 1 ,e 1 ; x 2 ,y 2 ,t 2 ,e 2 ; x 3 ,y 3 ,t 3 ,e 3 ; . . . x n ,y n ,t n ,e n } 
     where E 1 =[x 1 ,y 1 ,t 1 ,e 1 ] is the first event, and E n [x n ,y n ,t n ,e n ] is the n th  event. 
     This asynchronous stream is generated here by the electronics card providing the post-processing of the camera data. The items of identification information of each event are of modest memory size and can be sent sequentially. These information items are of course only sent if an event E has actually been generated, which considerably decreases the necessary output. In the absence of an event (for example a fixed scene and a fixed camera), nothing is sent. An asynchronous signal has therefore been created, which can be transmitted by means of a simple series link, but containing enough information to allow a 3D reconstruction of the scene, as will now be detailed. 
     With this aim, a very simple matching method is implemented according to the invention on the basis of the events generated by the two sensors C 1 , C 2 , the cameras of which are filming the same scene. The principle of this matching consists in positing the hypothesis that it is very likely that temporally close events generated by the two cameras relate to one and the same pattern or point of the scene. An attempt will then be made to match two temporally close events generated by the left-hand sensor and the right-hand sensor. In this way a matching will be performed that is spatial as well as temporal. 
     However, if at a given instant a change of luminous intensity, due for example to a movement in the scene, affects such and such a pixel on both cameras and where applicable generates events for each of the sensors, it is not very likely that the instants of occurrence of these events will coincide exactly with each other. First of all, the cameras show a latency time for reacting and generating the events, which also often varies for each of the pixels. Next, delays can arise in the generation of the information and its transmission. It can thus turn out to be hazardous to match events on the sole basis of an exact temporal coincidence of events generated by both cameras. 
     It is however possible to select, for each event E 1  generated by the left-hand camera (named left-hand event, or source event, and whose corresponding pixel P 1  is seen in  FIG. 1 ) , a set of events (here the events E 2 ,E′ 2 , E″ 2 ) generated by the right-hand camera (named right-hand events and whose corresponding pixels P 2 ,P′ 2 , P″2 can be seen) which have occurred in a given time window ΔT around the instant of occurrence of the left-hand event as is illustrated in  FIG. 2 . Thus, the right-hand event or events are selected to be temporally close to the source event. Obviously, the smaller the time window, the fewer the right-hand events that the set thus determined will contain. 
     This preliminary selection makes it possible to retain only a small number of right-hand events, one of which will be matched with the left-hand event. Where applicable, a single right-hand event is selected. The desired matching is then performed. If such is not the case, it is then a question of filtering the right-hand events to retain only the one that corresponds to the left-hand event under consideration. To do this, at least one of the following sifting procedures is applied:
         for each of the selected right-hand events the distance is computed between the corresponding pixel and the epipolar line L 1  in the focal plane of the right-hand camera that corresponds to the pixel P 1  linked to the left-hand event. Thus, all the right-hand events for which the distance thus determined is above a given limit D are eliminated. Preferably, the distance under consideration is a Euclidian distance;   all the selected right-hand events not having the same value as that of the left-hand are eliminated. Thus, if the left-hand event corresponds to an increase in luminous intensity, only the right-hand events also corresponding to an increase in luminous intensity will be retained;   all the selected right-hand events having already been the subject of a matching are eliminated, according to the application of the uniqueness principle.       

     Preferably, the sifting procedures are applied in the order indicated, until only one right-hand event is retained. These selection and sorting procedures consume very little memory size and computing time, and can therefore be easily implemented in real time with reasonable means, for example a simple personal computer. 
     The matching of two events therefore makes it possible to determine the matching of the two corresponding pixels as well as the instant when these two pixels must be matched. A conventional triangulation then makes it possible to determine the position of the point of the scene that has been seen by the two pixels thus matched. 
     According to a particularly advantageous embodiment, at least three sensors are used to observe the same scene, as illustrated in  FIG. 3 . The following explanation relates to the use of three sensors C 1 , C 2 , C 3  but is easily generalized to more than three sensors. 
     The use of at least three sensors allows a fine discrimination of events. To do this it is necessary to know the fundamental matrices F AB , F AC , F BC  linking each pair of sensors. 
     The implementation of the temporal selection, as mentioned beforehand, makes it possible to retain a certain number of events generated by each of the sensors and likely to correspond to the same point of the scene. 
     For example here, for the event E 1  of pixel P 1  in the plane of C 1 , the events E 2 ,E′ 2 ,E″ 2  of the respective pixels P 2 , P′ 2 , P″ 2  have been selected in the plane of C 2 , and the events E 3 ,E′ 3 , E″ 3  of the respective pixels P 3 , P′ 3 , P″ 3  have been selected in the plane C 3 . 
     To determine which of the events E 2 , E′ 2 , E″ 2  and E 3 , E′ 3 , E″ 3  correspond to the event E 1 , it suffices to determine in the plane of C 1  the epipolar lines corresponding to each of these events in the plane of C 1 , using the fundamental matrices. The pixel P 1  corresponding to the event is then at the intersection of two epipolar lines (here lines L 12  and L 13 ) generated by two events (here events E 2  and E 3  of pixels P 2  and P 3 ). 
     Reciprocally, it is observed that the pixel P 2  is at the intersection of the epipolar lines L 23  and L 21  generated by the events E 1  and E 3  in the plane of C 2 , and that the pixel P 3  is at the intersection of the epipolar lines L 31  and L 32  generated by the events E 1  and E 2  in the plane of C 3 . This property makes it possible to determine very quickly which of the temporally selected events must be matched. 
     The invention is of course not limited to that which has been described, but on the contrary encompasses any variant falling within the context defined by the claims. 
     To implement the matching procedure, these described sifting procedures may be applied in the order indicated, or in another order. Other sifting can of course be carried out, as long as temporally close events are matched together. 
     It is of course possible to use other sensors than conventional cameras, the signal of which is processed to deliver events relating to modifications in luminous intensity received by the pixels. It is for example possible to use sensors such as those described in the article “A 128×128 120 dB 15 μs latency asynchronous temporal contrast vision sensor”, P. Lichtsteiner, C. Posch, T. Delbruck, IEEE Journal of Solid State Circuits, Vol. 43, No 2, Feb. 2008. This type of sensor includes receivers which, in an independent and continuous manner, quantify relative changes in luminous intensity to generate events. The sensor delivers by design an asynchronous stream of events and is perfectly adapted to the method of the invention. 
     Although in the example described the signal perceived by the receivers of the sensors is a luminous intensity, it is of course possible to use sensors sensitive to other signals originating from the scene, such as for example infrared radiation, sonic intensity, a radar echo, etc. 
     Although the modification of the signal perceived by the elementary receivers is here quantified in a basic way (a first value for an increase in the signal, and a second value for a decrease in the signal), it is of course possible to quantify these modifications in a more elaborate way, for example by gray or color levels or by levels of luminous intensity, at the cost of a modest increase in the memory size of the event indicator. 
     Of course, the elementary receivers can be true receivers, arranged to form together a sensor, the visual field of which includes as many pixels as there are elementary receivers. However, the elementary receivers can be virtually created by computationally isolating elementary regions of the surface of the sensor sensitive to said signal, for each of which a modification of a physical characteristic of the signal received in said region is detected, and by generating as many signals as there are individual regions. In particular, if the set of receivers form one and the same sensor, they can assume any geometry, not necessarily planar. For example, the set of receivers can be arranged in a sphere. In such geometries, the epipolar line linked to an event detected by another sensor will more generally take the shape of a geodesic. 
     Of course, the method of the invention applies to a mobile scene with fixed sensors just as well as to a fixed scene with mobile sensors, vibrating sensors for example. 
     Finally, the method of the invention can immediately be generalized to the use of more than two asynchronous sensors.