Positioning system and method

Abstract

A positioning system, in particular, six-dimensions positioning system of a shadow sensor with respect to a constellation of light sources is provided. The sensor can be a shadow sensor and has a mask and a 2D imager. By recording the shadow of the mask cast by each light source on the imager, and by properly multiplexing the light sources, the system can compute the 6D position of the shadow sensor with respect to the constellation of light sources. This computation is based, in part, on treating the shadow of the mask cast on the imager as the equivalent of the projection of light in a pinhole or projective camera. In one embodiment, the system is applied in a surgical domain. In another embodiment, the system is rapidly deployed.

Claims

1. A six dimensional (6D) positioning system, comprising: a surgical tool; a surgical lamp; a plurality of light sources positioned at fixed relative locations in or on the surgical lamp; at least one shadow sensor placed on the surgical tool and configured to sense shadows cast on the shadow sensor by light emitted from the light sources, said shadow sensor comprising an imager; and a processor; wherein: the maximum distance between any of said light sources is larger than fifty times a width or a height of said imager; and the processor is configured to: sync a shadow sensing with a pulsing of the light sources; distinguish between the sensed shadows from each of the light sources; determine two dimensional positions corresponding to each of the light sources based on the sensed shadows; and compute a six dimensional (6D) position of the at least one shadow sensor with respect to the light sources based on the determined 2D positions.

2. The positioning system according to claim 1, wherein the system comprises several shadow sensors and wherein the processor is configured to compute the 6D position of said several shadow sensors.

3. The positioning system according to claim 1, wherein the number of light sources is equal or higher than three, the system comprises an assembly comprising two shadow sensors with known relative position and wherein the processor is configured to compute the 6D position of said assembly.

4. The positioning system according to claim 1, wherein the shadow sensor comprises a mask, the mask having repetitive elements and a distinctive element, and wherein as light from the light sources passes through the mask, a shadow of the mask is cast on the imager.

5. The positioning system according to claim 1, wherein the processor is configured to distinguish between the sensed light from each of the light sources based at least in part on temporal modulation of the light sources.

6. The positioning system according to claim 1, wherein each shadow sensor further comprises a photodiode for syncing the shadow sensing with the pulsing of the light sources and/or for identifying which light source is emitting light.

7. The positioning system according to claim 1, wherein the 6D position of the shadow sensor is computed as if the shadow sensor were a pinhole camera so as to use projective geometry computations.

8. The positioning system according to claim 1, wherein the light sources are connected and wherein a radio link is used to sync the shadow sensor.

9. A six dimensional (6D) positioning system, comprising: a set of at least two light source modules, each light source module comprising: a light source; communication means for communicating with other light source modules; a clock; fixation means for fixing the module on a support at least one shadow sensor configured to sense shadows cast on the shadow sensor by light emitted from the light sources of the light source modules, said shadow sensor comprising an imager; and a processor; wherein: the maximum distance between the light sources is larger than fifty times a width or a height of said imager, and the processor is configured to: sync a shadow sensing with a pulsing of the light sources; distinguish between the sensed shadows from each of the light sources; determine two dimensional positions corresponding to each of the light sources based on the sensed shadows; and compute a six dimensional (6D) position of the at least one shadow sensor with respect to the light sources based on the determined 2D positions.

10. The positioning system according to claim 9, a light source module comprising a battery and RF communication means, the system comprising a wired network connecting said light source module with at least one other light source module.

11. The positioning system according to claim 9, each light source module comprising a battery and the communication means being RF communication means.

12. A method for estimating a six dimensional (6D) position, of a shadow sensor with respect to a plurality of light sources, the shadow sensor being configured to sense shadows cast on the shadow sensor by light emitted from the light sources, said shadow sensor comprising an imager, the maximum distance between any of said light sources being larger than fifty times a width or a height of said imager, the method comprising: sync a shadow sensing with a pulsing of the light sources; distinguish between the sensed shadows from each of the light sources; determine two dimensional (2D) positions corresponding to each of the light sources based on the sensed shadows; compute a 6D position of the at least one shadow sensor with respect to the light sources based on the determined 2D positions; sense shadows cast on the shadow sensor by light emitted from the light sources, wherein at least two light sources are at a fixed position with respect to each other; record a projection of at least six points from a fixed location, each point corresponding to the three dimensional (3D) position in space of a light source, a projection of a point being recorded as the two dimensional (2D) position of the sensed shadow cast by said light source on said shadow sensor; repeat said recording and computing steps from a different fixed location, so as to obtain N recordings comprising each the projection of a set of the same P light sources, N and P being integer numbers satisfying a predetermined constraint; compute the three dimensional (3D) relative position of every light source within a common reference frame, said position being defined up to a scale factor; and scale every computed three dimensional (3D) relative position so that the computed three dimensional (3D) relative position of said at least two light sources matches said known fixed position.

13. The method of claim 12, further comprising the following steps: sense shadows cast on an assembly comprising at least two shadow sensors with known relative positions, by light emitted from the light sources, record a projection of at least three points from a fixed location, each point corresponding to the (3D) position in space of a light source, a projection of a point being recorded as the two dimensional (2D) positions of the sensed shadows cast by said light source on each shadow sensor of said assembly; compute the three dimensional position of each point with respect to said fixed location; repeat said recording and computing steps from a different fixed location, so as to obtain M recordings comprising each the projection of a set of the same Q light sources, M and Q being integer numbers satisfying a predetermined constraint; estimate the three dimensional (3D) relative position of every light source within a common reference frame.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The invention will be better understood with the aid of the description of an embodiment given by way of example and illustrated by the figures, in which:

(2) FIG. 1A shows a section view of a pinhole camera and an object point.

(3) FIG. 1B shows a section view of a shadow sensor and of a light source of the system according to the invention.

(4) FIG. 2 shows a flow chart of some steps of the method for computing the 6D position of a shadow sensor with respect to a plurality of light sources according to one embodiment of the invention.

(5) FIG. 3 shows a section view of a light source and of a shadow sensor of the system according to one embodiment of the invention.

(6) FIG. 4 shows a section view of a light source and of a shadow sensor of the system according to another embodiment of the invention, in which the Snell's law is applied.

(7) FIG. 5A shows an example of a system according to the invention, comprising a surgical lamp comprising a plurality of light sources and a surgical tool comprising a shadow sensor.

(8) FIG. 5B shows an example of another surgical lamp comprising a plurality of light sources according to the invention.

(9) FIG. 6 shows a perspective view of a light source module according to one embodiment of the invention.

(10) FIG. 7 shows a top view of an assembly comprising two light sources with known relative position according to one embodiment of the invention.

(11) FIG. 8 shows a block diagram of a positioning system according to one embodiment of the invention.

DETAILED DESCRIPTION OF POSSIBLE EMBODIMENT(S) OF THE INVENTION

(12) FIG. 1B shows a section view of a shadow sensor 100 and of a light source 200 of the system according to the invention. Only one light source 200 is illustrated for clarity purposes. However, it must be understood that the system according to the invention comprises a plurality of light sources, which are multiplexed in time or which emit at different wavelengths, as will be discussed.

(13) In one preferred embodiment, the system according to the invention comprises more than one shadow sensor 100.

(14) Each shadow sensor 100 is configured to sense shadows cast on the shadow sensor by light emitted from the light source 200.

(15) According to one preferred embodiment, the shadow sensor 100 is the sensor as described in WO 2012/007561, the entirety of which is incorporate herein by reference. In this embodiment, it comprises a mask 102 and an imager 104, the mask 102 having repetitive elements and a distinctive element: as the light from the light source 200 passes through the mask 102, a shadow of the mask 102 is cast on the imager 104. Each repetition of the elements contributes to the precision of the measurement. Preferably, the mask 102 is parallel to the imager 104. In one preferred embodiment, the mask 102 of the shadow sensor 100 comprises at least three repetitive elements in one direction and at least three repetitive elements in another different direction.

(16) In one preferred embodiment, the 6D position of the shadow sensor(s) is computed by considering each shadow sensor as a pinhole camera, so as to use projective geometry computations. FIG. 1A shows a section view of a pinhole camera 302 and an object point 300. The light from the scene comprising the object point 300 passes through the pinhole 306.

(17) The applicant discovered that surprisingly, from a geometry computation point of view, the shadow sensor 100 can be considered as a pinhole camera, or as a projective camera.

(18) The position x is computed from the shadow of the mask 102 (FIG. 1B) and it is the same as the projection of the object point 300 of the image plane 304 of the pinhole camera of FIG. 1A. In FIGS. 1A and 1B, x is a two-dimensional variable, although shown in 1D for clarity purposes. The focal length f of the shadow sensor 100 is the distance between the mask 102 and the image plane 104. In the shadow sensor 100, the z distance from the mask 102 to the light source 200 (measured along the optical axis) could be obtained by computing the scale of the shadow of the mask 102: if the shadow is of the same scale than the mask 102, then the light source 200 is very far away, if it is larger than the light source 200, it is close to the mask 102. By computing the enlargement ratio, it is possible to determine this z distance.

(19) In practice, however, this measurement is not very well conditioned, and thus results in a measurement with poor precision. In substance, the estimation of position x is about 100 times more precise than the estimation of the z distance.

(20) Because of the poor performance in the z estimation, in one preferred embodiment the method performs an estimation of the position of the shadow sensor using only the 2D position (i.e. x) estimation for each light source 200.

(21) According to known geometric rules, the projection of four light sources 200 is used to compute the 6D position of the sensor 100 with respect to the light sources 200, provided that the relative position of the light sources are known.

(22) There are efficient linear techniques to compute the 6D position on the basis of the x position, which do not deliver the optimal result in terms of accuracy, and there are non-linear techniques that deliver better accuracy but they are iterative, and need an initial position estimate. The initial position estimate of the iterative methods can be given by a linear technique, by a tracking process over time, or set to an initial arbitrary value.

(23) For example, the computation of the 6D position of a plane in space using four or more correspondences ({x.sub.ix.sub.i}, as discussed above can be determined according to multiple view geometry principles. This computation can be applied to a scenario where the light sources 200 are all on the same plane. To do so, first the 2D homography matrix between the sensor plane and the light source plane is computed, such that
x.sub.i=Hx.sub.i(1)

(24) where H represents a 2D homography matrix.

(25) Then, the first two columns of a rotation matrix and a translation vector can be retrieved according to the relationship:
H=K[r.sub.1,r.sub.2,t](2)

(26) where K are internal parameters, r.sub.1 and r.sub.2 represent the first two columns of the rotation matrix, respectively and t represents the translation vector.

(27) From this information, the full 6D transformation from the sensor plane to the light source plane (provided that the world origin is located on the shadow sensor) can be obtained using the focal length f of the shadow sensor.

(28) The document R. Hartley and A. Zisserman, Multiple view geometry in computer vision, second edition, Cambridge University Press, the entirety of which is incorporate herein by reference, describes in the algorithm 4.2 the method for computing the 2D homography between the camera plane and the light source plane. Its equation 8.1 allows to retrieve the first two columns of the rotation matrix and the translation vector.

(29) FIG. 2 illustrates a flow chart of the 6D position computation. A computing module, for example a computing module controlled by a processor, starts in step 1 by recording the projection of four or more points. In this context, a point indicates the location of a light source in the space.

(30) The number of points, as the term is used herein can generally be understood as the sum of the number of light sources that the sensors in the system can record. When a single shadow sensor is used, any point generates a measurement consisting of two coordinates. When an assembly of two sensors is used, any point generates a measurement consisting of four coordinates. For example, a system with four light sources and one sensor has four points, which represent eight coordinates; a system with three light sources and two sensors has three points, which represent twelve coordinates. In other words, the projection of a light source on a sensor system can be understood to be a point.

(31) However it should also be noted that in some conditions, e.g. when there is a-priori knowledge on the constellation of light sources position or when the point coordinate (the two-dimensional x) is not the only information retrieved from each light source, it is possible to use fewer than four points to compute the 6D position, as will be discussed.

(32) Then, in step 2, the system computes a first estimate of the 6D position, either using past information (tracking) or using any suitable computation method, for example the linear method described above.

(33) In the step 3, from the 6D estimate, the system virtually reprojects the points on the sensor 100, using the pinhole model.

(34) In step 4, an error value is computed by comparing the reprojected 2D position of every light source 200 with the 2D position computed using the shadow. In some embodiments, the error value may be computed using an error metric such as a weighted L1 norm, but any suitable error metric could be used. Since the problem is over-constrained, the error is not null.

(35) Thus, in step 5, an iterative error minimization can be performed in order to improve the 6D position estimate. To compute the L1 weighted error norm, the weight can be set using the contrast of the shadow. In other words, the more contrasted the shadow, the more visible the light source 100, the more confidence in the measurement and the higher the weight.

(36) If the error is small enough, then the system computes the 6D position estimate of the shadow sensor 100 with respect to the plurality of light sources 100 (step 9). For example, a small enough error may correspond to an error generated when the reprojected points are less than a quarter pixel away from the measured points on average. As an alternative, the small enough error can be characterised for a given application, with a given sensor type and dimension, and a given target type and dimension, in a calibration phase by measuring the standard deviation of the measured re-projection error on a set of measurement whose 6D position estimation is known to be correct; the small enough error threshold can be set to, for example, three times said standard deviation.

(37) If the error is not small enough, then in step 6 the system check if the number of iterations exceeds a threshold: if so, then the system declares that no position is available (step 8). If number of iterations does not exceed this threshold, then the system corrects in step 7 the 6D position estimate. The value of this threshold depends principally depends on the mathematical method used in the computation. In one preferred embodiment, the value of this threshold is about 20.

(38) In the iterative process of FIG. 2, the estimate of the shadow position from the shadow signal can be updated as well so as to better correspond to the pinhole model or to the projective model. For example, by having an estimate of a light source's 3D location, the assumed shape of the shadow can be computed by accounting for scaling and/or refraction. A shifted version of this assumed shape can be used to estimate the shadow position.

(39) In a preferred embodiment, the mask 102 of the shadow sensor 100 is composed of repetitive patterns and of a distinctive element, for example, a form of a grating. In this way, as light from the light source 200 passes through the mask 102, a distinct shadow pattern is cast on the imager 104 behind the mask 102 in accordance with the position of the sensor 100 with respect to the light source 200 and the pattern of the mask 102.

(40) By using a repetitive pattern for the mask 102, the precision of the sensor 100 may be increased by improving the measurement of the sensed pattern. By recording the shadow of the mask 102 cast by each light source 200 on the imager 104, and by properly multiplexing the light sources 200, the system can compute the 6D position of the shadow sensor 100 with respect to the plurality of light sources 200.

(41) In one preferred embodiment, the repetitive pattern of the mask 102 may be a checkerboard engraved on piece of glass. In another embodiments, the repetitive pattern may be realized by using a set of micro-lenses. In one preferred embodiment, the repetitive pattern of the mask 102 is a regular pattern, wherein a shape is repeated at regular intervals on the mask 102.

(42) Ideally, a mask should cast a shadow made of regular alternations of shadow and light.

(43) In practice, if looked at in a small scale, a regular mask does not generate a strictly regular shadow. This is because the mask 102 has a certain thickness t (as illustrated in FIG. 3), because of refraction effects on the glass of the mask 102, and/or because of other optical phenomena.

(44) Nevertheless, the mask 102 should generate an approximate regular pattern, such that, in the first step of the computation of FIG. 2, it is possible to assume a regular pattern and apply an efficient and accurate algorithm to compute the position estimate.

(45) In one embodiment, the size of the imager 104 is few mm, the mask 102 to imager 104 distance is about 0.3 mm to 2 mm, e.g. 0.5 mm to 1 mm, and the distance between two repetitive patterns on the mask 102 is about 100 m. Thus, the size of a shadow sensor 100 is about 10 mm10 mm2 mm, e.g. including various processors and other components, but excluding a battery. In other embodiments, the size of the shadow sensor 100 is about 4 mm4 mm1 mm, or even 3 mm3 mm1 mm. However, it should be noted that these dimensions are not intended to be limiting and even smaller shadow sensors are envisioned to be within the scope of the present disclosure. Moreover, the shadow sensor does not necessarily have a squared section. The main advantage of the shadow sensor in terms of size, compared to a traditional camera, is its thickness: the mask-imager assembly being much thinner than a lens-imager assembly of a standard camera.

(46) The shadow computation works in principle as described in equation 2 of WO 2012/007561, reproduced herein:

(47) $\begin{array}{cc}\{\begin{array}{c}A={.Math.}_x\sin \left[\frac{2}{P}M.Math.x\right].Math.s\left(x\right)\\ B={.Math.}_x\cos \left[\frac{2}{P}M.Math.x\right].Math.s\left(x\right)\\ \mathrm{dX}=-\mathrm{atan}2\left(A,B\right).Math.P\end{array}& \left(3\right)\end{array}$

(48) where M is the pixel pitch, s(x) is the shadow pattern, x is the pixel coordinate, and a tan 2(A,B) is the arctan(A/B) function defined in [, ]. In sum, the above equation uses the shadow image to take the sum over the lines and the sum over the columns, resulting in two signals. One signal is used to estimate the x coordinate (in this case, a mono-dimensional coordinate), the other to estimate the y coordinate.

(49) To take advantage of the repetition of the pattern present in the mask 102, it is assumed that the shadow has a given shape, the measured shape is correlated with shifted versions of the assumed shape. The dot product could also be used instead of a correlation. However, it should be noted that it is preferred to use the same metric throughout the computation.

(50) In WO 2012/007561, the assumed shape is a sinusoid and two versions of the assumed shadow shape shifted by half the shape period are used. The ratio of the two dot products is taken, which follows an arctan law, to retrieve the position.

(51) More generally, when starting with a position estimate, a three shifted version of the assumed shape can be used, making sure that among the versions, the first is shifted too far in one direction and the last is shifted too far in the opposed direction. Then, a correlation (or dot product, or any similarity metric) value for each can be calculated and a parabola can be fit to the three values. The position of the parabola extremum gives the position estimate of the shadow. In other words, it can be assumed that the similarity metric can be well approximated by a quadratic rule with the shift.

(52) When using a more complex optical model, for example by taking into account the refraction phenomenon, the shifting of the shadow assumed shape is computed by virtually shifting the light sources 200 and computing the resulting shadow according to the refraction model.

(53) To measure the actual shape of the mask 102, a shadow recording can be taken by exposing the shadow sensor 100 to a collimated light source, where the rays of the collimated light source are parallel to the optical axis of the sensor 100. This shape can then be used to compute the shape of the shadow by assuming a 3D position of the light source 200 in the context of an iterative position computation process.

(54) While the above described procedure gives the position up to an undetermined multiple of the signal period, the absolute shadow location can be computed by using a distinctive element, as described in WO 2012/007561. For example, the distinctive element can be a 2D code interlaced with the repetitive patterns. It can also be a set of missing repetitive elements, for example defining a crosshair in the middle of the mask. The missing element creates a sort of hole in the repetitive pattern, the hole being not a physical hole, it represents rather the absence of a repetitive element. It must be understood that the missing repetitive elements are not necessarily repetitive. The missing elements can also be set on the border, thus having a pattern of repetitive elements that do not cover completely the imager of the sensor. The preferred solution uses a set of missing (repetitive) elements.

(55) The refraction phenomenon transforms a perfectly regular shadow of the mask 102 into an irregular shadow. This is due to a layer of glass of the mask 102 which is traversed by the light prior to reading by the imager 104, as illustrated in FIG. 4, wherein the air A is over the mask 102 and between the mask 102 and the imager 104. In the FIG. 4, the reference PS indicates the periodic signal or shadow of the ideal case (i.e. refraction), the reference NPS the non-periodic signal or shadow of the real case (i.e. with refraction) and R the region of interest for the position analysis. By assuming a light position, and applying Snell's law, the shape of the shadow may be computed, as is illustrated in FIG. 2.

(56) This shape can be used to compute the shadow position in an iterative process, by starting with an estimate of the position, computing the shadow, slightly changing the position estimate in two opposite directions, and recomputing the shadow for each position change. By correlating the real shadow with these three shadow estimates, the real shadow position can be interpolated. Once said real position is determined, one may preferably recompute the position corresponding to a sensor without refraction prior to apply projective computations to estimate a 6D position.

(57) In a practical environment, the path between a light source 200 and a sensor could be obstructed by the presence of an object or a person. Thus, by having a multitude of light sources 200, and using a temporal multiplexing scheme, in one embodiment it is possible to ensure that at least four light sources 200 are visible within a given temporal window.

(58) For example, if the system has to compute 10 positions per second, and it the acquisition time of a shadow is in the order of 5 ms, in theory one could record the position of 20 lights sources to perform the computation. Thus, if at least four of these 20 are available, then the system can compute the 6D position of the shadow sensor with respect to the light sources.

(59) To record the projection of light sources 200, a shadow sensor 100 may sense several different wavelengths, use a temporal multiplexing scheme, or a combination of sensing several wavelengths and a temporal multiplexing scheme.

(60) Temporal multiplexing allows handling more light sources 200 with simpler and less expensive hardware, particularly where the target on which they can be placed does not move fast (e.g., having a displacement larger than 10% of the desired (x, y, z) precision). However, temporal multiplexing may be less capable depending on the motion of the light sources 200 in-between the shadow acquisition. The 6D computation is based on the target, i.e. the ensemble or constellation of light sources, considered as a rigid body during the computation, which means that the relative positions of the target LEDs are fixed. Thus, a target that moves between each light source shadow acquisition is equivalent to a target where the light source can have a relative and unknown displacement, thereby resulting in a poor 6D position computation.

(61) To solve the motion issues, the shadow acquisition is performed as fast as possible. In addition, by temporally tracking the position of each light source 200 individually, and knowing when the measurement took place, the position of each light source over time can be interpolated.

(62) Thus, using these interpolated values, the 6D position of the target may be computed by taking the position of each light source at a given time.

(63) The position of the light source is interpolated in a 3D space when using a double shadow sensor (or stereo shadow sensor), or in a 2D projection space when using a single shadow sensor. The simplest interpolation model assumes that the light source travels at constant speed. More elaborate models use a constant acceleration, or a continuous acceleration assumption (without jumps), and can use a Kalmann filter to track the speed and acceleration of each light source over time.

(64) In the temporal multiplexing scheme, the projection corresponding to each light source should be known. Thus, in one embodiment, communication means as a radiofrequency link can be used to send an ID of the light sources 200 and to sync their light emission with the recording of the shadow by the shadow sensor 100.

(65) To avoid using radio frequency, other embodiments may use an additional photodiode which is sampled at higher temporal frequency than the recording of the shadow (for example at 10 times higher temporal frequency). If a filter is used in a shadow sensor 100, then the photodiode may be placed behind the filter of the shadow sensor 100, next to the imager 104.

(66) This additional photodiode serves two purposes: it is used to sync the recording of the shadow with the light emission and is used to identify which light source 200 is emitting light. This can be done, for example, by varying the emission delay in-between the light sources, such that by measuring the time interval between two or more light emissions, it is possible to determine when each light source 200 is emitting light. Therefore, it is also possible to determine the projection corresponding to each light source.

(67) One advantage to using an additional photodiode instead of a radio frequency link is that the additional photodiode is more cost effective. Moreover, it is possible to measure the visibility of each light source 200 to estimate a very approximate position in a context with a large measurement volume and a lot of light source 200, e.g. more than 10 light sources 200.

(68) Alternatively, a shadow sensor in the temporal multiplexing scheme could be used without the additional photodiode. This embodiment is cheaper as use the shadow sensor 100 itself as a photodiode. In one preferred embodiment, the clocks of the plurality of light sources 200 are sync with the clock of the shadow sensor 100, and then the shadow sensor is used as described above to compute the 6D position. Then the process is repeated whenever the clocks of the plurality of light sources 200 and the clock of the shadow sensor 100 might be out of sync.

(69) In such embodiment, the shadow sensor effectively operates as a single photodiode, i.e. it is arranged for taking images at a high framerate and summing the captured pixels to generate a single value, that can be considered as a photodiode reading. The single value is proportional to the value that would have been obtained using the additional photodiode. Since the summation process reduces the noise, the shadow sensor can be operated at a framerate higher than what would be typically reasonable for position computation. Therefore, the same method described above with respect to the photodiode may be used with the single value generated by the shadow sensor 100.

(70) Regarding the sensing of several wavelengths, as described in the WO 2012/007561, a shadow sensor 100 can simultaneously record the projection of several light sources by using light sources 200 with distinct spectra, and dividing the sensor 100 into zones with distinct frequency responses. The zones can be large zones covering several periods of the mask 102, or small zones, for example, using a filter having the size of a single pixel. In the latter case, the filters are placed on the pixels of the imager 102, whereas in the former case, the filter can be placed either near the mask 102, near the imager 104, or anywhere in-between.

(71) The filters do not need to be perfectly matched to the light source spectra; rather, it suffices that the influence of each light source 200 for each filtered response can be recovered. In other words, if a squared matrix of responses, where each line represents the response to each light source and each column represents the response for each filter, is invertible, then it is possible to distinguish the influence of each light source 200. To ensure a good resilience to noise, this matrix has, in some embodiments, a condition number below 100, and in other embodiments, below 10. The signal to noise ratio can be further enhanced by having light sources with sharp spectral emissions, and filters with sharp spectral responses at the same frequency as the light sources 200.

(72) In one preferred embodiment, the system according to the invention comprises a LEDs' assembly as the plurality of the light sources 200, a set of shadow sensors, and a processor arranged so as to compute the position of each shadow sensor 100 with respect to the LED assembly. In one preferred embodiment, the LED assembly comprises height or more LEDs, and preferably not all on the same plane.

(73) FIG. 5A shows an example of a system according to the invention, comprising a surgical lamp 20 comprising a plurality of light sources 200 and a surgical tool 10 comprising a shadow sensor 100. In a preferred embodiment, the relative position of some, preferably all the light sources 200 is known. In the illustrated embodiment, all the light sources 200 are integrated in a surgical lamp 20. In the illustrated embodiment, the light sources 200 are connected, and if a radio link is used to sync the shadow sensor 100, then only one radio emitter is needed for the light sources 200.

(74) In one preferred embodiment, the light sources are emitting light not belonging to the visible spectrum, e.g. infrared light, so as to not interfere with the light of the surgical lamp 20.

(75) In one preferred embodiment, to ease the computation, among all the light sources 200, four can be placed on the same plane: in such a case a linear method can be used to compute the first 6D position after waking up the system according to the invention.

(76) FIG. 5B shows an example of another surgical lamp 20 comprising a plurality of light sources 200 according to the invention. In this embodiment, the light sources 200 are integrated in the frame 22 of the lamp 20, e.g. a highly rigid frame holds the LEDs internally.

(77) In another preferred embodiment, the system comprises a set of at least two light source modules 30. An example of light source module 30 is visible in FIG. 6. It comprises: a light source 200, e.g. a LED; communication means 400 for communicating with other light source modules, e.g. a radio link; a clock; fixation means 600 for fixing the module 30 on a support, e.g. a wall, a ceiling, a furniture. For example, the fixation means comprise a magnet, a tape, etc.

(78) The positioning system according to this embodiment can be deployed rapidly. This embodiment allows, for example, to install a positioning system in a new room by attaching at least two modules, preferably a multitude of these modules 30, at fixed locations in a volume, e.g. a room (on walls, ceiling or fixed furniture). The volume is not necessarily closed. The fixation means 600 allow the modules 30 to be easily placed at arbitrary positions within a volume.

(79) In one embodiment, each module 30 comprises a light source 200 as a LED 200, a clock and radio frequency link (emission and reception) 400 and a battery 500. In one embodiment one module 30 of the set acts as master, the others as slave. In another embodiment, only the module 30 acting as a master comprises a radio frequency link, and a wired network connects it to any other modules, which then do not require a battery, nor a radio link.

(80) A calibration phase is needed prior to be able to track any number of shadow sensors 100 in the room. Another advantage is the ability to correct for blind spots by adding additional modules 30 and repeating the calibration phase. A blind spot in this context is a (5D) position where the shadow sensor 100 is unable to record a sufficient amount of LEDs projections, and is thus unable to compute its position.

(81) In a discovery phase, every module 30 announces itself so as to construct a list of all the modules 30 that are present in the volume.

(82) In an initialisation phase, the clocks of all the modules 30 are synced and a flash timing is assigned to each module 30 by a master, which can be one of the modules 30. Then, each light source 200 is flashing according to its scheduled timing.

(83) Then follows a calibration phase: a shadow sensor 100 is placed in the volume, e.g. in the room. It makes a reading of all the light sources 200 of the modules 300 while being in a fixed (6D) position.

(84) The shadow sensor 100 is displaced, and a new reading is performed. For each reading, the (x, y) projection of the light sources 200 on the sensor 100 is recorded. Optionally, a scale or z value can be recorded, and the reliability of the reading (for example the contrast of the shadow) may be recorded as well.

(85) If a light source 200 is not visible, the reading is marked as missing, and if reliability is recorded, it is set to 0. The process of displacing the sensor and reading the light sources 200 is repeated until the complete 3D constellation of the light sources 200 is computed. More reading can then be added to improve the results, as will be discussed.

(86) A the end of the calibration phase, the 3D location of every light sources 200 is know and recorded, the 6D pose of the shadow sensor 100 at each reading known as well, and a partial visibility map for every light source 200 at each reading location can be read as well. In this context, the visibility map is a map indicating the reliability of each light source 200 reading at every location in the room. The visibility depends on the 3D location and orientation of the shadow sensor 100, but a rotation of the sensor around its optical axis does not affect the visibility of the LED: therefore, the visibility map is a 5 dimensional map, and not a 6 dimensional map.

(87) From this visibility map, the scheduling of the light sources 200 can be reordered in such a way that light sources 200 that are close together emit within a short period of time. For example, by setting the exposure time to 4 milliseconds, and waiting 2 milliseconds in-between captures, the whole acquisition process will take 22 milliseconds for a constellation comprising four light sources (in this scenario, the image of the shadow may be stored in a temporary memory buffer, so as to start the recording of the next light source before having computed the shadow position).

(88) If a set of light sources 200 are on the right side of a room, and another set on the left side of the room, then the left light sources 200 are flashed (one after the other), followed by the right light sources 200, followed by the left light sources 200, etc. In this way, a shadow sensor 100 placed on the left side of the room is able to record a set of projection in a short amount of time; which is a condition for having a good precision if the shadow sensor 100 is in motion.

(89) If this rescheduling is not done, then in the example above, the time to get enough light sources reading would be made longer because some light sources from the right side of the room would flash inbetween the light sources of the left side of the room. By assuming that the light sources on the right are not visible, or barely visible on the left of the room, they cannot be used to compute the shadow sensor position.

(90) Once these steps are completed, the system is ready for use, i.e. any shadow sensor 100 in the volume can compute its position over time, and send the result, e.g. via an RF link to a base station.

(91) As an option, the sensor 100 comprises a processor 108 (visible on FIG. 8) so as to perform a (x, y) reading (and optionally Z and visibility reading) and send this information to an external processor 800 which will compute the (6D) position of the shadow sensor 100. In another embodiment, the processor 108 of the shadow sensor perform the (6D) position of the shadow sensor 100 as well.

(92) On very large volumes, for examples volumes covering a whole room or a whole storehouse, the exposure schedule of some the light sources 200 can be overlapped, provided these light sources 200 are not visible from the same location. In other words, there must be no location (in 5D) where any two light sources 200 with overlapping schedule have a visibility value above a very small threshold (the threshold can be even put to 0). In this context, the expression overlapping threshold indicates that when one of the light sources 200 is turned on, then the second light source 200 is turned on before the first light source 200 is turned off.

(93) In practice, it is preferable to slightly differentiate the trigger schedule of every light source 200, so that when recording the signal with a photodiode with a high sampling rate, it is possible to know which of the light sources 200 with overlapping schedule is visible.

(94) This is useful in situations where the shadow sensor 100 does not (yet) know it's location: by measuring the visibility of some the of light sources 200, and using the visibility map, it can compute a rough estimate of its position, then adjust the exposure schedule of the shadow sensor 100 to record shadows from light sources 200 in the sensor vicinity in order to precisely measure its location.

(95) The applicant discovered surprisingly that recording the position of the shadow of the light source 200 with a sensor 100 that does not move, is equivalent to detecting a set of corresponding feature points in a multiple view scenario using a pinhole camera. It is therefore possible to compute the sensor position when having recorded the light sources 200 projections from several locations.

(96) The correspondence of the feature points is given by the ID of the light source 200 which was flashing when the shadow was recorded, the coordinate of the point is given by the coordinates (x, y) of the shadow, and the set of features in the image or view of the pinhole camera is the set of coordinates recorded from a given (fixed) location of the shadow sensor 100.

(97) It is possible to use the theory of multiple view geometry. The shadow sensor can be considered as being a pinhole camera, because the geometric configuration of the imager 104 in the shadow sensor 100 is known, and the focal length f can be considered as the distance between the mask 102 and the imager 104.

(98) The following table summarizes how many views and the minimal number of points per image that must be recorded to solve the joint problem of sensor pose and LED pose estimation. The noun views indicates all the recordings taken from a shadow sensor in a given (fixed) position. In other words, the following table indicates the constraints on the minimum number of visible points P (preferably not coplanar) to retrieve the complete system geometrical configuration up to a scale factor with a single shadow sensor:

(99) TABLE-US-00001 Number of views Number of N points P 2 8 3 7 4 6

(100) There is one additional constraint linked to the fundamental scale indetermination of the method according to the invention: in a preferred embodiment using a single shadow sensor during the calibration process, the relative position of at least two light sources 200 in the set under measure is known.

(101) FIG. 7 shows a top view of an assembly 40 comprising two light sources modules 30 with known relative position according to one embodiment of the invention. The relative position d is therefore known. The assembly 40 can be used to alleviate the scale indetermination in the calibration phase.

(102) In another embodiment, the distance between two particular light sources 200 of the system can be set by software.

(103) The scale determination is done by applying the complete estimation process, measuring the distance between the two light sources with known distance d according to the coordinates in this first version of the solution, and multiplying every spatial coordinate of every location (light source and sensor) by a common factor such that the distance between the two light sources 200 with known distance d becomes the correct distance (the orientation coordinates remain unchanged).

(104) The dual solution to using the assembly 40 to solve the scale indetermination problem is by using a stereo shadow sensor whose baseline is known. By knowing the baseline distance between the two sensors 100, the stereo sensor can estimate the 3D position of each light source 200 in space without having an overall scale indetermination. When a stereo shadow sensor is available, this solution is preferred to the one using a single shadow sensor, as this solution requires a lower number of light sources simultaneously visible by the shadow sensor. Moreover, this solution is more precise in terms of S/N issues.

(105) To compute the solution, i.e. the pose of every light source 200 and set of sensor 100 fixed locations, a matrix of visibility can be built. In one preferred embodiment, this matrix comprises on the columns the light sources 200 ID, and on the rows the (fixed) location of the sensors. In a preferred embodiment, the matrix is binary, and for each location it defines whether a light source 200 is visible or not. From there, one has to find the combination of location of light sources 200 and sensor 100 that fulfils the requirement of the previous table.

(106) For example, one can find two locations where there are 8 LEDs (or more) that are visible simultaneously (in other words, two lines of the matrix which share a true on at least height columns). From there, the pose of the sensor location and LEDs can be derived.

(107) Once a first set of pose is derived then: to compute the location of an additional light source 200, it suffices that it appears in two locations with known pose, to compute a new location of the sensor 100, it suffices that it has four light source 200 projections with known location that are visible.

(108) By iterating on these criteria, it is possible to reconstruct the whole light sources' constellation along with every sensor location. If this is not possible, i.e. if the problem has no solution, then the user of the system is asked to either add some more modules 30 in the volume, or take more recordings.

(109) To effectively solve the location problem given a number of visible light sources 200 and a number of sensor location, it is possible to apply the algorithm described in chapter 18 of the document R. Hartley and A. Zisserman, Multiple view geometry in computer vision, second edition, Cambridge University Press, using projective factorization followed by bundle adjustment. In fact according to the invention the shadow sensor is a pinhole or projective camera with known calibration parameters. In one preferred embodiment, the shadow sensor is calibrated at some point in time, prior to using it in 6D computations.

(110) There are applications that require rendering the result of the traking of the sensors in a CAD design. To register the system with a cad design, one can define in the CAD design where some particular light sources 200 should appear in the CAD, and perform a bundle adjustment to align the coordinate system of the light sources 200 constellation with the coordinate system of the CAD design.

(111) For example, the exact position of some of the light sources 200 can be known in the CAD reference frame; this allows to register the CAD coordinate frame with the sensor coordinate frame.

(112) A more practical approach is to set the constraint that (at least) three light sources 200 are on a surfacefor example a wallin the CAD system, (at least) two additional light sources 200 is on a second (different) surface, and yet another light source 200 is on a third surface different from the two former surface; in this context, it is also possible to align the CAD and sensor corner frames.

(113) If a stereo shadow sensor whose baseline is known is used, the bundle adjustment that follows is then simplified because the computation can be done in 3D instead of being done in projective space. To calibrate such a system, it must record a position with at least three light sources 200 visible in the field of view. Then, to further compute the position of each light source 200, any following recordings must have at least three light sources 200 with known position and at least one light source 200 with unknown position, whose 3D position is computed using said recording. Once every LED location is computed, the system can work with a single shadow sensor, provided that at least four light sources 200 are visible in the field of view, or with a stereo shadow sensor provided that at least three light sources 200 are visible in the field of view.

(114) These possibilities are illustrated in the block diagram of FIG. 8, representing the positioning system 1000 according to one embodiment of the invention. If two shadow sensors 100 are used, then at least three light sources 200 are necessary. If one shadow sensor 100 is used, then at least four light sources 200 are necessary.

(115) In one preferred embodiment, in the calibration phase, where the location of every light source is computed, the number of light sources that must be visible simultaneously is larger than when using the system to determine the position of the shadow sensor with respect to the constellation of the light sources.

(116) This invention discloses a system that computes a six-dimensional position of a sensor with respect to a constellation of light sources. While this six dimensional computation is performed inside to the sensors, or by an external computation facility, the information that is needed, recorded or transmitted may not be six dimensional. For example, some application may only require to know the 2D (or 3D) position of a sensor inside a room. In the latter case, the six dimensional position of the sensor is computed inside to the sensors, or by an external computation facility, from which the 2D (or 3D) position is extracted and communicated to the user (or to the system that needs this information).

(117) There are however situations where the six dimensional computation of the position is not necessary. These situations occur when there are some constraints on the orientation of the sensor. It is the case when the light sources used in the computation are all on one plane, and where the shadow sensor mask is parallel to this plane. If the distance between the shadow mask and the plane is fixed, then the computation is a 2D translation+1D rotation computation, i.e. a 3D computation. If this distance is varying, then the computation can be performed in 4D, i.e. a 3D translation+1D rotation. In both situation, the computation can be performed using first a linear affine transformation, followed by a non-linear bundle adjustment. It uses conventional geometry and avoids the projective geometry considerations.

(118) For example, if the sensor is fixed on a shopping cart, and the light sources are placed on the ceiling of the store, the internal computation will be performed by estimating the 2D position+1D orientation of the shopping cart, while probably transmitting only the 2D position of the shopping cart to the positioning system. In this example, the distance between the plane containing the light sources, i.e. the ceiling, is fixed with respect to the shopping cart which rolls on the floor (it assumes the ceiling is at constant height and parallel to the floor).

(119) Another example of such a system is when the sensor is fixed on a pallet truck. If the sensor is placed on the part of the truck that goes up and down, then it will be using a 3D position estimation+1D orientation internally to perform the computation.

REFERENCE SIGNS USED IN THE FIGURES

(120) 1 Recording step 2 6D position estimate computing the step 3 Re-projecting step 4 Error computing step 5 Error checking step 6 Iteration numbers checking step 7 6D position estimate correcting step 8 No position available step 9 6D position estimate step 10 Surgical tool 20 Surgical lamp 22 Frame of the surgical lamp 40 Assembly comprising two shadow sensors 100 Shadow sensor 102 Mask 104 Imager 108 Processor of the shadow sensor 200 Light source 300 Object point 302 Pin-hole camera 304 Image plane (imager) 306 Pinhole 400 Communication means 500 Battery 600 Fixation means 800 External processor 1000 System d Distance f Focal length t Thickness x Bi-dimensional position A Air PS Periodic signal (ideal case, without refraction) NPS Non periodic signal (real case, with refraction) R Range of interest for position analysis