ultraleap Patent | Determining positional information for an object in space
Patent: Determining positional information for an object in space
Drawings: Click to check drawins
Publication Number: 20150253428
Publication Date: 20150910
Applicants: Leap Motion
Assignee: Leap Motion
Abstract
System and methods for locating objects within a region of interest involve, in various embodiments, scanning the region with light of temporally variable direction and detecting reflections of objects therein; positional information about the objects can then be inferred from the resulting reflections.
Claims
1. A method for obtaining positional information about an object within a region of interest, the method comprising: (a) activating sources directed to portions of the region of interest according to an ordering of points, such that each point in the ordering directs electromagnetic radiation of at least one source to one of the portions of the region of interest; (b) capturing a portion of the electromagnetic radiation reflected by an object; (c) forming a signal over time of at least one property of the captured electromagnetic radiation; (d) determining from the signal, at least one point in the ordering in which a dominant contributor to the captured electromagnetic radiation was activated; (e) determining an identity for the dominant contributor from the point in the ordering; (f) determining from the identity of the dominant contributor, a portion of the region of interest to which the electromagnetic radiation from the dominant contributor was directed; and (g) determining positional information for the object based at least in part upon the portion of the region of interest.
2. The method of claim 1, wherein capturing electromagnetic radiation reflected by the object comprises capturing data frames of the region with a pixelated sensor.
3. The method of claim 2, further comprising determining a direction of the reflected electromagnetic radiation relative to the sensor, the positional information further being based in part on the direction of the reflected electromagnetic radiation.
4. The method of claim 2, wherein the data frames are captured at a rate exceeding a scan rate associated with the illuminating electromagnetic radiation.
5. The method of claim 2, wherein determining a direction of the illuminating electromagnetic radiation associated with the electromagnetic radiation reflected by the object comprises determining an intensity peak across a temporal sequence of data frames for at least one pixel corresponding to the object within the data frame.
6. The method of claim 5, wherein determining the intensity peak comprises performing a Fourier transform on the temporal sequence of data frames for the at least one pixel.
7. The method of claim 1, wherein the electromagnetic radiation is retro-reflected by the object.
8. The method of claim 7, further comprising physically associating the object with a retro-reflector.
9. The method of claim 1, wherein the region is scanned periodically.
10. The method of claim 1, wherein the point in the ordering corresponding to capture of the reflected electromagnetic radiation corresponds to a phase within an emission cycle.
11. The method of claim 10, wherein determining the direction of the illuminating electromagnetic radiation associated with the electromagnetic radiation reflected by the object comprises determining the point in the cycle where the captured radiation is greatest.
12. The method of claim 11, wherein the point in the cycle is detected using a phase-detector circuit.
13. The method of claim 1, wherein scanning the region comprises sequentially operating a plurality of light-emitting devices emitting light to respective different portions of the region of interest.
14. The method of claim 13, further comprising operating only a subset of the plurality of light-emitting devices so as to reduce a resolution of the scan.
15. The method of claim 13, wherein sequentially operating the plurality of devices comprises sequentially causing the devices to emit pulses of light.
16. The method of claim 15, wherein successive pulses overlap temporally.
17. The method of claim 13, wherein sequentially operating the plurality of devices comprises driving each device according to a time-variable intensity having an intensity peak, the peaks occurring sequentially for the plurality of light-emitting devices.
18. The method of claim 18, wherein light emitted by the plurality of light-emitting devices overlap spatially and temporally, determining a direction of the illuminating light associated with the light reflected by the object comprising determining an effective primary direction of the overlapping illuminating light.
19. The method of claim 1, wherein scanning the region comprises moving a light-emitting device.
20. The method of claim 1, wherein scanning the region comprises moving at least one of a deflecting optic or a screen used in conjunction with a light-emitting device.
21. The method of claim 1, wherein the positional information comprises at least one of a distance, a depth, or a position of at least one of the object or a surface feature thereof.
22. The method of claim 1, wherein the positional information comprises a depth profile of the object.
23. The method of claim 1, wherein the positional information is determined further based at least in part on a geometric relationship between the source and the detector.
24. The method of claim 1, further comprising periodically repeating steps (a) through (c) so as to update the positional information to track movement of the object.
25. A system for obtaining positional information about an object within a region of interest, the system comprising: a directed light source with variable direction for scanning the region with an illuminating light; a detector for capturing light reflected by the object, and circuitry for (i) determining a time of capture of the reflected light and, based thereon, an associated direction of the illuminating light, and (ii) deriving the positional information about the object at least in part from the direction of the illuminating light.
26. The system of claim 25, wherein the directed light source comprises a plurality of light-emitting devices emitting light in a respective plurality of different primary directions.
27. The system of claim 26, wherein the directed light source further comprises a controller for sequentially operating the plurality of light-emitting devices.
28. The system of claim 26, wherein the light-emitting devices comprise light-emitting diodes.
29. The system of claim 26, wherein the light-emitting devices are arranged such that their respective primary directions intersect at a common center.
30. The system of claim 29, wherein the light-emitting devices are affixed to at least one of an arcuate surface, facets of a polygonal surface, or facets of a polyhedral surface.
31. The system of claim 28, wherein the plurality of light-emitting devices comprises a plurality of light emitters and a plurality of associated deflecting optics for deflecting light emitted by the emitters into the different primary directions.
32. The system of claim 27, wherein the directed light source comprises at least one moving light-emitting devices.
33. The system of claim 27, wherein the directed light source comprises at least one light-emitting device and at least one of a moving deflecting optic or a moving screen having a perforation therein.
34. The system of claim 27, wherein the detector comprises a camera for imaging the region.
35. The system of claim 34, wherein the camera comprises a lens and a sensor.
36. The system of claim 35, wherein the sensor comprises at least one of a CCD sensor or a MEMS sensor.
37. The system of claim 34, wherein the camera comprising a light-sensing device and a scanning mirror.
38. The system of claim 25, wherein the detector is co-located with the light source, the system further comprising a retro-reflector affixed to the object.
39. The system of claim 25, wherein the directed light source comprises a controller for varying the emission direction so as to periodically scan the region.
40. The system of claim 39, wherein the controller is synchronized with the circuitry.
41. The system of claim 39, wherein the circuitry causes the detector to be read out at a rate exceeding the scan rate of the directed light source.
42. The system of claim 39, wherein the circuitry comprises a phase-detector circuit for determining a phase within an emission cycle corresponding to a maximum intensity of the captured light.
43. The system of claim 39, wherein the circuitry comprises a digital processor configured for performing a Fourier transform on the captured light to thereby determine a phase within an emission cycle corresponding to a maximum intensity of the captured light.
44. The system of claim 25, further comprising a retro-reflector affixed to the object.
45. A method for determining depth associated with at least one object within a region of interest, the method comprising: scanning the region with an illuminating light beam having a temporally variable beam direction so as to illuminate the at least one object; acquiring a temporal sequence of images of the region while the region is being scanned, each image corresponding to an instantaneous direction of the illuminating light beam, at least one of the images capturing light reflected by the at least one illuminated object; and based at least in part on the instantaneous direction of the light beam in the at least one image capturing light reflected by the at least one object, determining a depth associated with the at least one object.
46. The method of claim 46, wherein multiple of the images acquired during a single scan of the region capture light reflected by the at least one object, the method comprising determining a depth profile of the at least one object based thereon.
47. A method for locating an object within a region, the method comprising: using a light source affixed to the object, scanning the region with an illuminating light beam having a temporally variable beam direction; using a sensor co-located with the light source, capturing reflections of the illuminating beam from a plurality of retro-reflectors fixedly positioned at known locations; based on times of capture of the reflections, determining associated directions of the illuminating light beam; and locating the object relative to the known locations of the retro-reflectors based at least in part on the directions of the illuminating light beam.
48. The method of claim 48, wherein the object is located in a two-dimensional region based on reflections from at least three retro-reflectors.
49. A device, affixed to an object of interest, for locating the object within a region relative to a plurality of retro-reflectors fixedly positioned at known locations, the device comprising: a light source for scanning the region with an illuminating light beam having a temporally variable beam direction; a sensor co-located with the light source for capturing reflections of the illuminating beam from the plurality of retro-reflectors; circuitry for determining, from times of capture of the reflections, directions of the illuminating light beam associated therewith, and for locating the object relative to the retro-reflectors based at least in part on the directions.
50. The device of claim 50, wherein the object is a mobile device.
51. A computer-implemented method for conducting machine control, the method comprising: scanning a region of space, the scanning including (i) directing at least one light emission from a vantage point of a vantage region to a region of space, (ii) detecting a reflectance of the at least one light emission, and (iii) determining that the detected reflectance indicates a presence of an object in the region of space; determining one or more object attributes of the object; analyzing the one or more object attributes to determine a potential control surface of the object; determining that control-surface attribute changes in the potential control surface indicate control information; and responding to the indicated control information according to response criteria.
52. A computer-implemented method according to claim 52, wherein the first light emission is directed to the region of space according to a first scan pattern, and wherein determining that the detected reflectance indicates a presence of an object comprises directing a second light emission to the region of space according to a second scan pattern.
53. A computer-implemented method according to claim 53, wherein directing the second emission comprises: scanning to a refined scan pattern.
54. A computer-implemented method according to claim 54, wherein scanning to the refined scan pattern includes capturing surface detail about the object.
55. A computer-implemented method according to claim 52, wherein determining object attributes of the object comprises: determining positional information of at least a portion of the object.
56. A computer-implemented method according to claim 56, wherein analyzing the object attributes to determine a potential control surface of the object comprises: determining based at least in part upon the positional information whether a portion of the object provides control information.
57. A computer-implemented method according to claim 57, wherein determining whether one or more control-surface attribute changes in the potential control surface indicate control information comprises: determining whether control-surface attribute changes in the potential control surface indicate an engagement gesture.
58. A computer-implemented method according to claim 58, wherein responding to the indicated control information according to response criteria comprises: determining a command to a user interface based at least in part upon the engagement gesture.
59. A computer-implemented method according to claim 52, wherein determining object attributes of the object comprises: determining dynamic information of at least a portion of the object.
60. A computer-implemented method according to claim 52, wherein determining object attributes of the object comprises: determining physical information of at least a portion of the object.
61. A computer-implemented method according to claim 52, wherein determining object attributes of the object comprises: determining at least one of optical or radio properties of at least a portion of the object.
62. A computer-implemented method according to claim 52, wherein determining object attributes of the object comprises: determining chemical properties of at least a portion of the object.
63. A computer-implemented method according to claim 1, wherein: directing the emission includes scanning across an entryway; determining that the detected reflectance indicates a presence includes detecting an object comprising a person seeking entrance, and conducting a second scanning to a refined scan pattern of the person; determining whether control-surface attribute changes in the potential control surface indicate control information includes determining whether the control-surface attribute changes indicate a vein pattern of a hand of the person; and responding to the indicated control information according to response criteria comprises permitting the person to enter when the vein pattern matches a stored vein pattern of an individual authorized to enter.
Description
CROSS-REFERENCE TO RELATED APPLICATIONS
[0001] This application claims priority to and the benefit of, and incorporates herein by reference in their entireties, U.S. Provisional Application Nos. 61/792,025, 61/800,327 and 61/801,479, each filed on Mar. 15, 2013.
TECHNICAL FIELD
[0002] Embodiments of the disclosed technology generally relate to distance measurement and, more particularly, to determining a position and/or depth of an object or features of an object surface in space.
BACKGROUND
[0003] Determining the distance of objects from an observation point, or tracking objects in three dimensions, is important for many applications, including, e.g., surveying, navigation, surveillance, focus finding in photography, and motion capture for gesture- and movement-controlled video gaming, to name just a few. A variety of approaches to distance determination exist. For example, ultrasonic and laser rangefinders are based on time-of-flight measurements, i.e., they emit a sound or light pulse toward the object, capture a reflected signal pulse (or echo), and measure the roundtrip time for the pulse, from which the distance of the object can be calculated. This method generally works well over large distances where precision beyond a few meters is not required. However, since the accuracy of the measurement depends heavily on recording the precise times of broadcast and capture, which is challenging, in particular, for very fast-moving waves (e.g., light waves), this approach is--absent expensive high-speed equipment--generally unsuitable for more precise determinations and/or determinations made over shorter distances. A need therefore exists for alternative methods for determining the distance, depth, and/or three-dimensional position of an object or surface feature thereof.
SUMMARY
[0004] Embodiments hereof provide an approach to distance or depth measurements that utilizes a directed light source with time-variable direction to sweep or scan a spatial region of interest, and a light detector to measure light reflected by object(s) that might exist within the region of interest in a way that temporally resolves the different directions. In one embodiment, the light source scans the spatial region periodically (e.g., like a flash light waving back and forth over the region of interest), such that each direction of the illuminating emission provides information about object(s) that might exist in the region being scanned. For example, light direction can correspond to, and/or can include information about, a particular phase or point within the emission cycle. The direction of the illuminating emission thus provides information about one or more of a presence, location, or other perceivable property of the object(s). For example, in some embodiments, a camera--or other light sensor--can be synchronized with the light source to capture light diffusely reflected (e.g., scattered) off objects in the spatial region. Positional information can be extracted from analyzing the captured light. In an embodiment, positional information can be extracted from the time (or phase within the cycle) at which the light is received. The direction of the illuminating emission, and thus the direction of the object's location viewed from the source/sensor arrangement, can be calculated. For example, positional information can comprise relative distances between the camera, the object, and the receiver.
[0005] An embodiment uses two such source/sensor arrangements disposed in different locations, each scan the same plane, thereby enabling the location of an object within that plane to be determined from the intersection of the two scanning directions that result in respective reflection signals. In a yet further embodiment, a third source/sensor arrangement is disposed in a different plane such that the emission of the third source/sensor arrangement scans along an axis orthogonal to the two co-planar source/sensor arrangements, thereby enabling a three-dimensional spatial region to be scanned for the location of the object. The distances to the object within the spatial region can be determined by triangulation based upon the relative distances between the object and the various source/sensor arrangements.
[0006] In further embodiments, an object of interest is equipped with a retro-reflector, and the specular reflection of the illuminating emission is detected with a photo-sensor co-located with the light source.
[0007] In yet further embodiments, an object may be equipped, for tracking purposes, with a light source and sensor, and its location may be computed from reflection signals that it receives from retro-reflectors at fixed spatial locations.
[0008] Among other aspects, in an embodiment, directed light source refers to a light source that emits light in accordance with a directional nature (primary direction). The light emission may have any divergence, ranging from highly collimated to wide-angle, and can often be characterized with a Gaussian profile. In an embodiment, the primary direction of the emission comprises the central or average direction, or the direction of brightest emission, which coincide for a Gaussian profile. Some implementations include a directed light source with time-variable direction, comprising an arrangement of one or more light-emitting devices, optionally in conjunction with any associated optics or other components, that emits light, at any moment in time, in a primary direction that changes as a function of time.
[0009] In some embodiments, variable emission direction is achieved by an arrangement of two or more light-emitting devices, at least two of which emit in a different direction, that are electronically controlled to change activation levels among two or more activation states (e.g., turn on and turn off) sequentially, periodically, or according to pattern (or combinations thereof)), such that a combination of the contributions from the two or more light sources emit radiation during a complete control cycle, or emission cycle, in accordance with a scan pattern.
[0010] Individual light-emitting devices define an emission point, and collectively, the light-emitting devices of the light source define an emission region. The light-emitting devices can be arranged and/or spaced according to implementation (e.g., based upon individual emission divergences, area coverage, interference avoidance, other application specific needs, and so forth) such that the emissions collectively cover at least some desired subset of the entire spatial region of interest. In alternative embodiments, a single light-emitting device can be used; the emission direction can be varied directly by moving (mechanically, optically, electrically, or combinations thereof) the light-emitting device, and/or indirectly by moving a light-deflecting optic, such as a prism or mirror to scan the region of interest.
[0011] In embodiments, scanning encompasses directing light, e.g., as achieved by moving one or more individual light-emitting devices and/or associated optics, as well as making discrete changes in emission direction, e.g., by activating light-emitting devices pointing in different directions. In embodiments, two or more activation states of two or more light sources can be at least partially concurrent, or completely discrete. In some embodiments, the scan pattern enables light to sweep a region of interest, by changing the emission direction continuously or discretely as a function of time. For example, in some embodiments, the emission can change between discontiguous directions (e.g., in accordance with a random, pseudo-random, or programmed scan pattern). In embodiments, a scan pattern provides a continuous or discontiguous spatial, temporal, or spatio-temporal change in light at the region of interest. Implementation-specific needs can be met using any or combinations of individual light-emitting devices, such as light-emitting diodes (LEDs), lasers, incandescent or fluorescent light bulbs, or any other devices emitting light in one or more suitable frequency ranges, such as the optical, infrared (IR), or ultraviolet (UV) regime.
[0012] In an embodiment, light scattered or reflected by objects illuminated by the light source is captured using a light detector (or multiple detectors), suited to the application, that measures a property, comprising any of an intensity, color, polarization, other property or combinations thereof, of the incoming light as a function of time; each detector defines a detection point, and when alone or combined with multiple light-sensing elements, defines a detection region. In embodiments, the light detector can be synchronized with the light source so that the timing of the various control states of the light source (corresponding, for example, to different emission compositions, directions, other controllable aspects) is known relative to the timing of the measurements at the detector, enabling associating the direction of the illuminating emission with each point in time of the measured signal. Various embodiments utilize a digital camera with a one- or two-dimensional electronic pixelated sensor, which can be non-coplanar or coplanar, such as a CCD (charge-coupled device) or CMOS (complementary metal-oxide semiconductor) sensor used as a photo-sensor array. The camera may acquire a temporal sequence of captured frames, at a frame rate faster than the scan rate of the light source, such that multiple frames are acquired during an emission cycle of the source and each frame corresponds to a different control state of the illuminating emission. The frames can be processed by a computer, or other suitable processing device(s), which can analyze the frames to determine a phase of a signal formed by the pixel output in response to the changing light conditions experienced by the sensor within each cycle for each pixel, e.g., by means of a discrete Fourier transform. In alternative embodiments, the signal comprises a photocurrent generated in each light-sensor pixel that is processed continuously by an associated phase-detecting circuit. Accordingly, embodiments can enable determining the direction of the illuminating emission from information extracted from the signal. In an embodiment, a camera can include a lens and/or other optics that focus light received from a particular direction onto a particular region of the sensor (corresponding to a pixel or group of pixels); thus, the position within the sensor at which the reflected light is received is related to the direction from which the light comes.
[0013] In one aspect, embodiments provide a method for obtaining positional information about an object within a region of interest. The method may include (a) activating sources directed to portions of the region of interest according to an ordering of points, such that each point in the ordering directs electromagnetic radiation of at least one source to one of the portions of the region of interest (e.g., the NE quadrant, SE quadrant, etc.); (b) capturing a portion of the electromagnetic radiation reflected by an object; (c) forming a signal over time of at least one property (e.g., intensity, color, polarization, other property or combinations thereof) of the captured electromagnetic radiation; (d) determining from the signal at least one point in the ordering in which a dominant contributor to the captured electromagnetic radiation was activated; (e) determining an identity for the dominant contributor from the point in the ordering; (f) determining from the identity of the dominant contributor, a portion of the region of interest to which the electromagnetic radiation from the dominant contributor was directed; and (g) determining positional information for the object based at least in part upon the portion of the region of interest. In one embodiment, activating sources includes activating illumination sources (e.g., LEDs) directed in different directions according to a known order, such that each point in the order is associated with a particular direction. The ordering can be fixed or can vary from scan instance to scan instance. Further, more than one source can be activated at a time to form a cross-fade or other illumination profile. From the signal, it may then be determined where in the order the greatest contributor--or contributors--of the captured light was activated, and, based thereon, the identity of the greatest contributor(s) and the direction in which the light was emitted may be determined. Based on the direction in which the illumination is emitted, the positional information of the object may be determined.
[0014] Capturing the reflected light may include capturing data frames (e.g., sensor states resulting from capturing illumination of a scan, or image resulting from a capture with a sensor array of a camera) of the region. The direction of the reflected light relative to the camera may be determined, and the positional information may be further based in part thereon. The data frames may be captured at a rate exceeding a scan rate associated with the illuminating emission. The direction of the illuminating emission associated with the spectral region reflected by the object may be ascertained by determining an intensity peak across a temporal sequence of data frames for at least one pixel corresponding to the object within the data frame. The intensity peak, in turn, may be determined, e.g., from a Fourier transform on the temporal sequence of data frames. In some embodiments, the electromagnetic radiation is retro-reflected by the object. A retro-reflector may be physically associated with the object.
[0015] The region may be scanned periodically, according to a same or a different order of activation. The point in the ordering corresponding to capture of the reflected electromagnetic radiation corresponds to a phase within an emission cycle. Determining the direction of the illuminating electromagnetic radiation associated with the electromagnetic radiation reflected by the object may include determining the point in the cycle where the captured radiation is greatest. This point in the cycle may be detected using a phase-detector circuit or equivalent. Scanning the region may involve sequentially operating a plurality of light-emitting devices each directing light to a different portion of the region of interest. In some embodiments, only a subset of the plurality of light-emitting devices are operated so as to reduce a resolution of the scan. Sequentially operating the plurality of devices may comprise sequentially causing the devices to emit pulses of light; successive pulses may overlap temporally. Sequentially operating the plurality of devices may, alternatively or additionally, involve driving each device according to a time-variable intensity having an intensity peak, the peaks occurring sequentially for the plurality of light-emitting devices. In some embodiments, light emitted by the plurality of light-emitting devices overlap spatially and temporally; in this case, determining a direction of the illuminating emission associated with the light reflected by the object may include determining an effective primary direction of the overlapping illumination. The "effective primary direction" is the direction along which the intensity maximum resulting from the spatiotemporal overlap between illuminations from two or more sources with different individual primary directions lies. In various embodiments, scanning the region includes moving (e.g., rotating or translating) a light-emitting device, or moving a deflecting optic and/or a screen used in conjunction with a light-emitting device.
[0016] In another aspect, embodiments pertain to a system for obtaining positional information about an object within a region of interest. The system may include a directed light source with variable direction for scanning the region with an illuminating light, a detector for capturing light reflected by the object, and circuitry for (i) determining a time of capture of the reflected light and, based thereon, an associated direction of the illuminating light, and (ii) deriving the positional information about the object at least in part from the direction of the illuminating light. In some embodiments, the system also includes a retro-reflector affixed to the object.
[0017] In some embodiments, the directed light source includes a plurality of light-emitting devices (e.g., LEDs) emitting light in a respective plurality of different primary directions. Further, the directed light source may include a controller for sequentially operating the plurality of light-emitting devices. The light-emitting devices may be arranged such that their respective primary directions intersect at a common center. For example, the light-emitting devices may be affixed to an arcuate surface, facets of a polygonal surface, or facets of a polyhedral surface. (An "arcuate surface" is herein understood to mean a segment of a spherical surface (e.g., a semispherical surface) or a surface having at least one cross-section shaped like a segment of a circle (e.g., a semicircle).) The plurality of light-emitting devices may include a plurality of light emitters and a plurality of associated deflecting optics for deflecting light emitted by the emitters into the different primary directions. In some embodiments, the directed light source comprises one or more moving light-emitting devices. In other embodiments, the directed light source includes one or more light-emitting devices and a moving deflecting optic and/or a moving screen having a perforation therein.
[0018] In various embodiments, the detector includes a camera for imaging the region; the camera may include a lens and a sensor (e.g., a CCD or MEMS sensor), or a light-sensing device and a scanning mirror. In certain embodiments, the detector is co-located with the light source, and the system further includes a retro-reflector affixed to the object. The directed light source may include a controller for varying the emission direction so as to periodically scan the region; this controller may be synchronized with the circuitry determining the time of capture of the reflected light. The circuitry causes the detector to be read out at a rate exceeding the scan rate of the directed light source. In some embodiments, the circuitry includes a phase-detector circuit for determining a phase within an emission cycle corresponding to a maximum intensity of the captured light, and/or a digital processor configured for performing a Fourier transform on the captured light to thereby determine a phase within an emission cycle corresponding to a maximum intensity of the captured light.
[0019] In another aspect, embodiments provide a method for determining depth associated with one or more objects within a region of interest. The method includes (a) scanning the region with an illuminating light beam having a temporally variable beam direction so as to illuminate the object(s), (b) acquiring a temporal sequence of images of the region while the region is being scanned, each image corresponding to an instantaneous direction of the illuminating light beam and at least one of the images capturing light reflected by the illuminated object(s); and (c) based at least in part on the instantaneous direction of the light beam in the image(s) capturing light reflected by the object(s), determining a depth associated with the object(s). Multiple of the images acquired during a single scan of the region may capture light reflected by the object(s); the method may include determining a depth profile of the object(s) based thereon.
[0020] A further aspect relates to a method for locating an object within a region. In various embodiments, the method involves, (a) using a light source affixed to the object, scanning the region with an illuminating light beam having a temporally variable beam direction; (b) using a sensor co-located with the light source, capturing reflections of the illuminating beam from a plurality of retro-reflectors fixedly positioned at known locations; (c) based on times of capture of the reflections, determining associated directions of the illuminating light beam; and (d) locating the object relative to the known locations of the retro-reflectors based at least in part on the directions of the illuminating light beam. In some embodiments, the object is located in a two-dimensional region based on reflections from at least three retro-reflectors.
[0021] Yet another aspect pertains to a device, affixed to an object of interest, for locating the object within a region relative to a plurality of retro-reflectors fixedly positioned at known locations. The device may include a light source for scanning the region with an illuminating light beam having a temporally variable beam direction; a sensor co-located with the light source for capturing reflections of the illuminating beam from the plurality of retro-reflectors; and circuitry for determining, from times of capture of the reflections, directions of the illuminating light beam associated therewith, and for locating the object relative to the retro-reflectors based at least in part on the directions. The object may, for example, be a mobile device.
[0022] In a further aspect, embodiments provide a computer-implemented method for conducting machine control. The method involves scanning a region of space, the scanning including (i) directing at least one light emission from a vantage point of a vantage region to a region of space, (ii) detecting a reflectance of the at least one light emission, and (iii) determining that the detected reflectance indicates a presence of an object in the region of space. Further, the method includes determining one or more object attributes of the object; analyzing the one or more object attributes to determine a potential control surface of the object; determining whether one or more control-surface attribute changes in the potential control surface indicate control information; and, if so, responding to the indicated control information according to response criteria. In some embodiments, the first light emission is directed to the region of space according to a first scan pattern, and determining that the detected reflectance indicates a presence of an object comprises directing a second light emission to the region of space according to a second scan pattern. Directing the second emission may involve scanning to a refined scan pattern, e.g., so as to capture surface detail about the object.
[0023] In some embodiments, determining object attributes of the object comprises determining positional information of at least a portion of the object. Analyzing the object attributes to determine a potential control surface of the object may include determining based at least in part upon the positional information whether a portion of the object provides control information. Determining whether one or more control-surface attribute changes in the potential control surface indicate control information may include determining whether control-surface attribute changes in the potential control surface indicate an engagement gesture. Responding to the indicated control information according to response criteria may include determining a command to a user interface based at least in part upon the engagement gesture. In various embodiments, determining object attributes of the object comprises determining dynamic information of at least a portion of the object, physical information of at least a portion of the object, optical and/or radio properties of at least a portion of the object, and/or chemical properties of at least a portion of the object.
[0024] In certain embodiments, directing the emission includes scanning across an entryway; determining that the detected reflectance indicates a presence includes detecting an object comprising a person seeking entrance, and conducting a second scanning to a refined scan pattern of the person; determining whether control-surface attribute changes in the potential control surface indicate control information includes determining whether the control-surface attribute changes indicate a vein pattern of a hand of the person; and responding to the indicated control information according to response criteria comprises permitting the person to enter when the vein pattern matches a stored vein pattern of an individual authorized to enter.
[0025] In a further aspect, a method for obtaining positional information includes (a) scanning the region with an illuminating emission having a temporally variable emission direction; (b) capturing light reflected by the object and, based on a time of capture of the reflected light, determining an associated direction of the illuminating emission; and (c) deriving the positional information about the object at least in part from the direction of the illuminating emission. The positional information may be determined further based at least in part on a geometric relationship between the light source and the detector. The positional information may include a distance, a depth, or a position of the object or a surface feature thereof. In some embodiments, the positional information comprises a depth profile of the object. The method may involve periodically repeating steps (a) through (c) so as to update the positional information to track movement of the object.
[0026] Advantageously, these and other aspects of the disclosed technology may enable machines, computers, automata, and/or other types of intelligent devices to obtain information about objects present and events and/or actions (such as user gestures, signals, or other motions conveying commands and information to the device) occurring in a monitored region of interest. These and other advantages and features of various embodiments of the disclosed technology will become more apparent through reference to the following description, the accompanying drawings, and the claims. It is to be understood that the features of the various embodiments described herein are not mutually exclusive and can exist in various combinations and permutations.
BRIEF DESCRIPTION OF THE DRAWINGS
[0027] In the following description, various embodiments disclosed technology are described with reference to the following drawings, in which:
[0028] FIG. 1 illustrates an exemplary machine sensory and control system in embodiments;
[0029] FIGS. 2A-2E illustrate exemplary emission components of the machine sensory and control system of FIG. 1, in accordance with various embodiments;
[0030] FIGS. 3A-3E illustrate exemplary detector components of the machine sensory and control system of FIG. 1, in accordance with various embodiments;
[0031] FIGS. 4A-1 and 4A-2 schematically illustrate an exemplary system for conducting variation determination with emitters operated in discrete modes;
[0032] FIGS. 4B-1, 4B-2, and 4B-3 schematically illustrate an exemplary system for conducting variation determination with emitters operated in continuously variable modes;
[0033] FIG. 5A is a schematic diagram of an exemplary system for conducting variation determination with a pixelated sensor in accordance with various embodiments;
[0034] FIG. 5B illustrates an exemplary control scheme for the light source depicted in FIG. 1A in accordance with one embodiment;
[0035] FIG. 5C illustrates a reflection signal detected with the camera depicted in FIG. 5A, resulting from the light-source control scheme of FIG. 5B, in accordance with one embodiment;
[0036] FIG. 5D illustrates the computation of depth for the geometric configuration of the system depicted in FIG. 5A, in accordance with one embodiment;
[0037] FIG. 5E illustrates an exemplary control scheme for the light source depicted in FIG. 5A that exploits different scan frequencies in accordance with an alternative embodiment;
[0038] FIG. 5F illustrates a spectral reflection signal detected with the camera depicted in FIG. 5A resulting from the light-source control scheme of FIG. 5E;
[0039] FIGS. 6A-6C illustrate different exemplary light-source configurations in accordance with various embodiments;
[0040] FIGS. 7A and 7B illustrate embodiments in which light source and camera are, respectively, integrated into the same unit or provided as separate devices;
[0041] FIG. 8A illustrates an object location mid-way between the primary directions of two discrete light emitters with overlapping illumination regions, and FIG. 8B shows the resulting reflection intensity in accordance with one embodiment;
[0042] FIG. 8C illustrates an object located closer to one of two primary directions of two discrete light emitters with overlapping illumination regions, and FIG. 8D shows the resulting reflection intensity in accordance with one embodiment;
[0043] FIG. 8E illustrates a control scheme with temporal overlap between the pulses emitted by different discrete light emitters having overlapping illumination regions, and FIGS. 8F and 8G show the resulting reflection intensities in accordance with various embodiments;
[0044] FIG. 8H illustrates the intensity variation of a pulsed light source in accordance with various embodiments;
[0045] FIG. 9A illustrates a light source with only two light emitter producing overlapping illumination regions, and FIG. 9B illustrates a control scheme for the light source with temporal overlap in accordance with one embodiment;
[0046] FIGS. 10A-10G illustrate moving light sources in accordance with various embodiments;
[0047] FIGS. 11A-11N illustrate different exemplary light sources for scanning a three-dimensional region in accordance with various embodiments;
[0048] FIGS. 12A and 12B are flow charts illustrating methods for depth determination in accordance with various embodiments;
[0049] FIG. 13A is a schematic diagram of an exemplary system for depth determination that uses light sources producing different light characteristics in accordance with various embodiments;
[0050] FIG. 13B is a schematic diagram of an exemplary system for depth determination based on retro-reflection off an object in accordance with various embodiments;
[0051] FIG. 13C is a schematic diagram of an exemplary system for determining the two-dimensional position of an object using retro-reflection in accordance with various embodiments;
[0052] FIG. 13D is a schematic diagram illustrating how an object equipped with a light source can be localized based on retro-reflections off multiple stationary reflectors in accordance with various embodiments;
[0053] FIG. 14 is a block diagram of an exemplary computational facility for determining positional information in accordance with various embodiments;
[0054] FIG. 15 illustrates an exemplary task environment in which various embodiments of the disclosed technology may be utilized;
[0055] FIG. 16 illustrates a variation determination system in accordance with various embodiments;
[0056] FIGS. 17A-17D illustrate predictive information including a model in accordance with various embodiments; and
[0057] FIGS. 18A and 18B illustrate virtual constructs implementing an engagement target with which a control object interacts in accordance with various embodiments.
DETAILED DESCRIPTION
[0058] Described herein are various embodiments of methods and systems for determining the distance, depth, and/or position of objects (and surface features of objects) in space relative to a physical reference (such as a light source and detector, as described in detail below). Sensing distance, depth, and/or position of objects automatically (e.g., programmatically) can enable machines to be controlled by salient properties of the objects or object motion. The object(s) may generally be any inanimate or animate objects, and may have complex surfaces and/or change in position or shape over time. Certain embodiments provide improved accuracy in positional and/or depth determination, thereby supporting object and/or object-surface recognition, as well as object-change, event, and/or action recognition, and/or combinations thereof.
[0059] FIG. 1 illustrates an exemplary machine sensory and control system in embodiments. In one embodiment, a motion-sensing and controller system provides for detecting that some variation(s) in one or more portions of interest of a user (or other object) has occurred, for determining that an interaction with one or more machines corresponds to the variation(s), for determining whether the interaction should occur, and, if so, for affecting the interaction. The machine sensory and control system (MSCS) typically includes a portion-detection system, a variation-determination system, an interaction system, and an application-control system.
[0060] As FIG. 1 shows, one embodiment of detection system 100 embodiment includes an emission module 102, a detection module 104, a controller 106, a signal-processing module 108, and a machine-control module interface 110. The emission module 102 illuminates one or more objects of interest 112 (e.g., the user's finger or some other control object) within an area of interest 114. In one embodiment, the emission module 102 includes one or more emitter(s) 120A, 120B (e.g., LEDs or other devices emitting light in the IR, visible, or other spectrum regions, or combinations thereof; radio and/or other electromagnetic signal emitting devices) that are controllable via emitter parameters (e.g., frequency, activation state, firing sequences and/or patterns, and so forth) by the controller 106. However, other existing/emerging emission mechanisms and/or some combination thereof can also be utilized in accordance with the requirements of a particular implementation. The emitters 120A, 120B can be individual elements coupled with materials and/or devices 122. For instance, a light-emitting element 120A, 120B may be combined with a lens 122A (see FIG. 2A), multi-lens 122B (see FIG. 2B), image-directing film (IDF) 122C (see FIG. 2C), liquid lens, multiple such elements or combinations thereof, and/or others, with varying or variable optical properties to direct the emission. Further, as shown in FIG. 2D, one or more arrays 120D of emissive elements (combined on a die or otherwise) may be used with or without the addition of devices 122 for directing the emission, and positioned within an emission region 200 (see FIG. 2A) according to one or more emitter parameters (e.g., statically mounted (e.g., fixed, parallel, orthogonal or forming other angles with a work surface, one another or a display or other presentation mechanism), dynamically mounted (e.g., pivotable, rotatable and/or translatable), embedded (e.g., within a machine or machinery under control) or otherwise coupleable using an interface (e.g., wired or wireless). In some embodiments, illustrated in FIG. 2E, structured lighting techniques can provide improved surface-feature-capture capability by casting illumination according to a reference pattern onto the object. Image-capture techniques described in further detail herein can be applied to capture and analyze differences in the reference pattern and the pattern as reflected by the object. In yet further embodiments, the detection system 100 may omit the emission module 102 altogether (e.g., in favor of ambient lighting).
[0061] With renewed reference to FIG. 1 and further reference to FIGS. 3A-3E, in one embodiment, the detection module 104 includes one or more capture device(s) 130A, 130B (e.g., e.g., devices sensitive to visible light or other electromagnetic radiation) that are controllable via the controller 106. The capture device(s) 130A, 130B can comprise one or more individual image-capture elements 130A or arrays of image-capture elements 130A (e.g., pixel arrays, CMOS or CCD photo sensor arrays, or other imaging arrays) or individual photosensitive elements 130B or arrays of photosensitive elements 130B (e.g., photodiodes, photo sensors, single detector arrays, multi-detector arrays, or other configurations of photo sensitive elements), or combinations thereof. However, other existing/emerging detection mechanisms and/or some combination thereof can also be utilized in accordance with the requirements of a particular implementation.
[0062] Capture device(s) 130A, 130B can each define a particular vantage point 300 from which objects 112 within the area of interest 114 are sensed, and can be positioned within a detection region 302 (see FIG. 3A) according to one or more detector parameters (either statically (e.g., fixed, parallel, orthogonal or forming other angles with a work surface, one another, or a display or other presentation mechanism) or dynamically (e.g., pivotably, rotatably, and/or translatably); and mounted, embedded (e.g., within a machine or machinery under control), or otherwise coupleable using a wired or wireless interface). Capture devices 130A, 130B can be coupled with devices and/or materials (such as, e.g., lenses 310A (see FIG. 3A), multi-lenses 310B (see FIG. 3B), image-directing film (IDF) 310C (see FIG. 3C), liquid lenses, combinations thereof, and/or others) with varying or variable optical properties for directing the reflectance to the capture device 130A, 130B for controlling or adjusting resolution, sensitivity, and/or contrast. Capture devices 130A, 130B can be designed or adapted to operate in the IR, visible, or other spectrum regions, or combinations thereof; or alternatively operable in conjunction with radio- and/or other electromagnetic-signal-emitting devices in various applications. Multiple capture devices 130A, 130B can be organized in arrays 320, in which the image capture device(s) can be interleaved by row (see, e.g., FIG. 3D), column, or according to a pattern, or can be otherwise addressable individually or in groups. In an embodiment, capture devices 130A, 130B can capture one or more images for sensing objects 112 and capturing information about the object (e.g., position, motion, and so forth). In embodiments comprising more than one capture device, particular vantage points of capture devices 130A, 130B can be directed to area of interest 114 so that fields of view 330 of the capture devices at least partially overlap. Overlap in the fields of view 330 (see, e.g., FIG. 3E) provides capability to employ stereoscopic vision techniques, including those known in the art, to obtain information from a plurality of images captured substantially contemporaneously.
[0063] While illustrated with reference to a particular embodiment in which control of emission module 102 and detection module 104 are co-located within a common controller 106, it should be understood that these control functions may, in alternative embodiments, be implemented in separate hardware components, or may each be distributed over a plurality of components. Controller 106 comprises control logic (implemented in hardware, software, or combinations thereof) to conduct selective activation/de-activation of emitter(s) 120A, 120B in on-off or other activation states or combinations thereof (and/or to control active directing devices) to produce emissions of (e.g., spatiotemporally) varying intensities in accordance with a scan pattern which can be directed to scan the area of interest 114. Controller 106 can further comprise control logic (implemented in hardware, software, or combinations thereof) to conduct selection, activation, and control of capture device(s) 130A, 130B (and/or to control associated active directing devices) to capture images or otherwise sense differences in reflectance or other illumination. Signal-processing module 108 determines whether captured images and/or sensed differences in reflectance and/or other sensor-perceptible phenomena indicate a possible presence of one or more objects of interest 112, such as control objects 113; the presence of such objects, and/or variations thereof (e.g., in position, shape, etc.), can be used as input to a machine controller via the machine- and application-control module interface 110.
[0064] In various embodiments, the variation of one or more portions of interest of a user or control object can correspond to a variation of one or more attributes (e.g., position, motion, appearance, surface patterns) of a user's hand or finger(s) 113, points of interest on the hand, a facial portion, etc., or other control objects (e.g., styli, tools), and so on (or some combination thereof) that is detectable by, or directed at, but otherwise occurs independently of the operation of the machine sensory and control system. Thus, for example, the system may be configurable to "observe" ordinary user locomotion (e.g., motion, translation, expression, flexing, deformation, and so on), locomotion directed at controlling one or more machines (e.g., gesturing, intentionally system-directed facial contortion, and so forth), and/or attributes thereof (e.g., rigidity, deformation, fingerprints, veins, pulse rates, and/or other biometric parameters); see, e.g., U.S. Provisional Patent Application Ser. No. 61/952,843 (filed on Mar. 13, 2014), the entire disclosure of which is hereby incorporated by reference. In one embodiment, the system provides for detecting that some variation(s) in one or more portions of interest (e.g., fingers, fingertips, or other control surface portions) of a user has occurred, for determining that an interaction with one or more machines corresponds to the variation(s), for determining whether the interaction should occur, and, if so, for at least one of initiating, conducting, continuing, discontinuing, and/or modifying the interaction (and/or a corresponding or related interaction).
[0065] FIGS. 4A-1 and 4A-2 illustrate an exemplary system for conducting distance/depth determination with emitters operated in discrete modes. As shown in FIG. 4A-1, the system includes an emitting source 402 comprising a number of (in the depicted exemplary embodiment, four) emitting elements (e.g., emitters A, B, C, D) to provide a directed source having a variable direction that illuminates a region of interest 414 including an object of interest 412. The source 402 can scan a spatial region according to a suitable scan pattern by activating and de-activating select ones of the emitting elements according to a known ordering. For instance, the region may be divided into a number of sub-regions (e.g., four quadrants), which are then illuminated by select activation of emitting elements. Emissions that intercept the object 412 are reflected, and a portion of the reflection is captured by a receiver 404 (e.g., a single detector element, any arrangement--e.g., an array, line, etc.--of individual detector elements, a camera or camera-like device comprising a pixelated sensor, or other arrangements of detector elements or combinations thereof). When the illumination strikes an object 414, a reflection is detected by the receiver 404 which forms a signal of a property (e.g., intensity, polarization, frequency, or the like) of the reflection received over time. A point in the ordering in which a dominant contributor to the captured electromagnetic radiation was activated can be determined from the signal. The point in the ordering corresponding to the time of receipt of the reflection allows an inference of the direction of the illuminating emission and, thus, of the sub-region in which the reflecting object is located. An identity for the dominant contributor can be determined from the point in the ordering. A portion of the region of interest (e.g., sub-region) to which the electromagnetic radiation from the dominant contributor was directed can be determined from the identity of the dominant contributor. Positional information for the object (e.g., sub-region in which at least a portion of the object is located) can be determined based upon the portion of the region of interest. In some implementations, multiple illuminating emissions having different properties, e.g., different frequencies (e.g., color), may be used contemporaneously or sequentially and distinguished using suitable filters with the detector(s).) Multiple sources and detectors may be used to scan the region of interest along different planes so as to provide three-dimensional information as illustrated by FIG. 13A and described in further detail below. For example, a cubic volume may be scanned along two perpendicular planes, each divided into four quadrants. Localizing an object in one of the four quadrants for both scans allows identifying in which one of eight sub-cubes the objects is located. As will be apparent to one of skill in the art, the spatial resolution of object localization achieved in this example embodiment corresponds directly to the spatial resolution of the scan pattern; the more sub-regions there are, the more precise is the determined object location. As illustrated in FIG. 4A-2, the sources A, B, C, D may be operated in a discrete, binary mode, i.e., turned on and off one at a time. This results in a binary signal at the receiver 404, with intensity or amplitude levels of varying degree; reflected illumination from the emitter that provides the most direct illumination of the object 414, in this case emitter B, results in the point of greatest magnitude in an intensity vs. time signal. A point of greatest magnitude that changes position within the ordering--e.g., occurs relative to activation of emitter D in the illustrated example--in successive captures (e.g., frames) of receiver 404 indicates a variation in the position or shape of the object being tracked. Patterns of variations can be detected and cross-correlated to recognize gestures made by a tracked hand for example.
[0066] FIGS. 4B-1 through 4B-3 illustrate an exemplary system for conducting distance/depth determination with emitters operated in continuously variable modes. The system hardware may have the same or similar emitter and receiver hardware as the discrete-mode embodiment described above with reference to FIGS. 4A-1 through 4A-2, but the emitters A, B, C, D are turned on and off gradually, reaching their respective intensity maxima according to a continuum. Since the emitters are energized and de-energized continuously, their active, energized states may temporally overlap using techniques such as described in further detail with reference to FIGS. 8E-8G and 9A-9B below. In some embodiments, one emitter remains energized while the next emitter is energized to create a "cross-fade." The reflected emissions detected at the receiver may result in a continuously varying signal with a (global) maximum corresponding to the most direct illumination (which may be either a single maximum, as shown in FIG. 4B-2, or the largest one of a number of local maxima, as shown in FIG. 4B-3).
[0067] FIG. 5A conceptually illustrates, in more detail, an exemplary system 500 for distance or depth sensing in accordance with various embodiments. The system 500 includes a plurality of integral, non-integral, and/or communicatively coupled elements: a light source 502 that emits light toward a region of interest 504, a controller 506 for operating the light source 502 so as to scan the region 504, a pixelated sensor array 508 (e.g., a camera or other sensor array, typically including associated control hardware) for capturing a portion of the emitted light as reflected from an object 510, and a sensor-data processing facility 512 for processing the sensor data acquired by the sensor array 508. The various system components may be provided in a more distributed or more integrated manner. The controller 506 and sensor-data processing facility 512 may each be implemented in hardware, software, or a combination of both. Further, they may be implemented as separate components (as depicted), or integrated into a single device. In some embodiments, a suitably programmed general-purpose computer interfacing with the sensor array 508 serves to process the sensor data and determine positional information associated therewith. The computer may also store a program module that provides the functionality of the light-source controller 506. Alternatively, the controller 506 and/or the sensor-data processing facility 512 may be implemented with dedicated electronic circuitry, such as, e.g., digital signal processors (DSPs), field programmable gate arrays (FPGAs), or application-specific integrated circuits (ASICs), etc. In some embodiments, the sensor-data processing facility 512 is provided in the form of custom hardware that is integrated with the sensor array 508 into a single device.
[0068] As depicted, the light source 502 may include a plurality of individually controllable light-emitting devices 520, 522, 524, 526, 528 (such as, e.g., LEDs), disposed, e.g., on a semispherical surface 530. Each individual light-emitting device defines an emission point, and collectively, the light-emitting devices of the light source define an emission region. The light-emitting devices 520, 522, 524, 526, 528 may be powered by a dedicated driver circuit 514, or, alternatively or in addition, via a network link directly by the controller 506. The controller 106 may set the drive currents to alter the activation states of these devices 520, 522, 524, 526, 528 (e.g., turn on and off, vary intensity, etc.) at periodic (or other) intervals, e.g., cycling through them in various orderings according to a scan pattern to emit light in different primary directions (indicated in FIG. 5A by dashed lines) into the region 504. While light source 502 is depicted with five devices, embodiments can be created using virtually any number of light sources (not shown in FIG. 5A for clarity sake) to satisfy implementation-specific criteria or needs.
[0069] FIG. 5B illustrates an exemplary control scheme for the light-emitting devices 520, 522, 524, 526, 528, involving periodic pulsed operation of each device and uniform spacing of the pulses from all devices throughout the emission cycle. The scan rate (i.e., the number of emission cycles per second) may be selected based on the anticipated range of velocities of the object 510 and/or the reference frame in movable/moving sensor/detector configurations, depth of view of the region of interest, expected distance(s) to object(s) anticipated to appear within the region of interest, power consumption, desired resolution of tracking of object(s), application receiving the result, other configuration-dependent criteria, or combinations thereof. For example, scan rate can be selected such that multiple cycles can occur before the object 510 (or reference frame) moves appreciably. While FIG. 5B illustrates one embodiment of an emission cycle, it will be appreciated that other emission-cycle embodiments, using different numbers of light sources, cycle parameters, and activation states (not shown by FIG. 5B for clarity sake) are readily apparent to one of skill in the art based on the principles and practices revealed herein. As shown by FIG. 5B, an emission cycle can be advantageously apportioned into phases, such that a phase (.PHI.) corresponds to an activation state of one or more light-emitting devices comprising emitter 502. Changing the activation state of the light-emitting devices (e.g., turn on and off, vary intensity, and so forth), can advantageously sweep the region of interest. In embodiments, the light emitters can be operated individually or in groups, in any order, and according to any scan pattern. In some embodiments, light sources can be illuminated to different levels of brightness based upon an activation state. For example, a light emitter can be switched to a first activation state (e.g., partially illuminated), and subsequently switched to a second setting (e.g., more or brightly illuminated). Third, fourth, and additional illumination levels can be provided for in some embodiments. Some embodiments provide for pulsing of illumination source(s) at different intervals, brightness levels, polarizations, coherence properties and so forth based upon activation states. In yet further embodiments, the brightness of each device can be varied continuously, e.g., in a linear, quadratic, exponential, or logarithmic fashion.
[0070] With reference again to FIG. 5A, the sensor array 508 can comprise a pixelated sensor 540, such as an array constructed of photodiodes, phototransistors, photovoltaic cells, photoresistors and/or other types of photo-sensing devices capable of converting light into an intensity-dependent current and/or voltage. In some embodiments, a conventional CCD or CMOS camera is used, and the image sensor of the camera is periodically first exposed to light and then read, resulting in a series of data frames. (Alternatively, in "rolling-shutter" cameras, the sensor is exposed and read sequentially in multiple segments (or even individual pixels), such that the exposure of one segment (or pixel) can temporally overlap with the reading of a previously exposed segment (or pixel). In an embodiment, the sensor array facilitates random access to segments or pixels. The rate at which frames are read determines the temporal resolution of image acquisition. In another embodiments, the image sensor 540 is read using custom electronic circuitry. For example, in one embodiment, each individual sensor can be associated with a dedicated analog circuit that continuously measures the photo-induced current or voltage.
[0071] The sensor array 508 and sensor-data processing facility 512 can be operated to capture and analyze data frames at a rate that temporally resolves the discrete phases of the light source 502. For example, using a frame-based read-out architecture, the sensor array 508 can acquire data, for the depicted embodiment, at five frames per emission cycle, such that each data frame corresponds to one of the states within the emission cycle. The sensor array 508 can be synchronized (broadly understood) with the light source 502, e.g., based on a synchronization signal received from the controller 506 or a signal from a separate timer fed to both the controller 506 and the sensor array 508, such that each data frame can be associated with a direction cc of the illuminating emission. Synchronization can comprise acquisition of a data frame occurring substantially contemporaneously with the activation of one or more light sources in a particular state forming an emission of light, or at a known period of time thereafter. In embodiments, the sensor array can be read at a rate above or below the rate of change in the state of the light source. In one embodiment, the frame rate is read at a rate above the rate at which the light source state changes, which prevents a decrease in the angular resolution of the sweep because a single frame does not, in this case, integrate multiple states of the light source.
[0072] In one embodiment, sensor array 508 further comprises an imaging optic 542, (e.g., a lens, image-directing film, liquid or variable lenses, other optically active material, or combinations thereof) to focus light onto the sensor 540. Again with reference to FIG. 5A, in the illustrated embodiment, calibration techniques can be employed to correct for variations in components (e.g., deviations in lens optical characteristics, smudges, dust, manufacturing tolerances, burned out emitters and so forth), environment (e.g., temperature, ambient light, vibration, and so forth), usage (e.g., in home, underwater, outdoors, factory environment, highway, and so forth), and/or configurations (flat, 3D, coplanar, non-coplanar, circular, and so forth) of sensor array 508. For example, incoming light approaching sensor array 508 at the angle .beta. relative to the optical axis 544 of the lens 542 (i.e., a normal through the center of the lens), can be mapped sub-optimally to the pixels of the sensor 540 due in part to such variations. Accordingly, in an embodiment, nominal parameters of the lens shape and position and orientation relative to the sensor can be used to compute a coarse mapping function, and subsequent calibration techniques can refine that function to account for deviations from the nominal parameters. Various calibration methods are well-known to persons of skill in the art. In one embodiment, for example, a well-defined test-pattern (e.g., a checkerboard pattern) of known dimensions is imaged, and a function that maps the known original pattern onto the measured pattern in the image is determined. In an embodiment, calibration information can be stored in a library, look-up table or other suitable storage mechanism for data for use by the sensor-data processing facility 512.
[0073] In some embodiments, sensor array 508 comprises a micro-electro-mechanical system (MEMS) camera. The MEMS camera can scan (e.g., by raster-scan, or other scan pattern) the region of interest using a scanning mirror in conjunction with a single photodiode (or other light-sensing device). Light striking the scanning mirror of the MEMS camera from different directions is captured at different times during a scan. The scanning mirror directs the captured light to the photodiode which converts the light into a signal representing the region scanned. In an embodiment, analysis of the signal can provide blobs corresponding to objects in the region of interest captured by the system. In some embodiments, the scanning mirror is controlled based at least in part upon control information provided by a secondary imaging or sensory system. For example, a first imaging can provide one or more portions of the region of interest to which the scanning mirror is directed to conduct a more refined scanning. Of course, other image recognition techniques in addition to, or instead of, blob tracking are readily provided for by embodiments. In some embodiments, the MEMS camera scans the region of interest at a rate much faster than the light source changes state, e.g., once, twice and so forth for each discrete direction of the illuminating emission, thereby enabling the scan to provide substantially the same information as a complete image frame acquired by a conventional camera.
[0074] In embodiments, location information for an object (or a particular surface region thereof) can be determined in part based on the state (e.g., temporally changing direction, composition, and so forth) of the light that strikes the object (or the particular surface region) and produces a reflection that can be detected by the sensor array 508. As illustrated in FIG. 5A, an object 510 is illuminated most directly by light from light emitter 526 at phase .phi..sub.4 (see FIG. 5B) within the cycle, but--due to its location within the region 504--does not receive as large a quantity of illumination from the other light emitters 520, 522, 524, and 526. In an embodiment of the illustrated configuration, the measured time-dependent intensity at pixels that receive light reflected and/or scattered by the object 510 can exhibit a relative peak (corresponding to the reflection) as received at the sensor array 508 as illustrated by the received signal's .phi..sub.4 in FIG. 5C.
[0075] Although depicted schematically in FIG. 5A as a single ray for clarity sake, in embodiments the emissions of the light emitter(s) can possess any of a variety of profiles, characteristics, and properties. In one embodiment, intensity distribution of the emission peaks along the primary direction and falls off to all sides, asymptotically reaching zero at large distances from the optical axis. Light travelling in different primary directions can overlap spatially, including on the surface of the object that scatters light towards the sensor. In embodiments, some or all of the sensor 540 can detect light originating from multiple emitters throughout an emission cycle. A reflecting object can appear brightest to the sensor 108 when the object receives maximal illumination. Location information about the object 510 as viewed from the sensor 508 corresponds to, and can be determined from, the maximum intensity of the reflected light at the sensor and the phase within the emission cycle that emitted the light. FIG. 8B illustrates an embodiment in which the intensity of a reflection signal from the object 510 can vary as a function of time if a plurality of emissions spatially overlap such that the object 510 is not only illuminated by emitter 526, but also by the neighboring emitters 524, 528.
[0076] When the illumination of the region of interest by the light source 502 significantly exceeds any illumination by ambient light, a reflection peak may be determined, e.g., directly within the time-domain intensity signal captured by the sensor for each pixel. Further, to increase the signal-to-noise ratio (i.e., the intensity ratio between light originating from the light source 502 and ambient light), the frequencies to which the sensor array 508 is sensitive can be tailored to the emission frequencies of the light source 502, e.g., by selecting a sensor material that absorbs primarily in that range, or by equipping the sensor with a suitable color filter that strongly absorbs frequencies other than those emitted by the light source 502. Typically, however, the signal is filtered to extract signal components that occur with the scan frequency. This can be accomplished in several ways, depending on the type of sensor array 508 and image-processing facility 512 that is employed. For example, if sensor array 508 comprises a conventional camera read out frame by frame to a general-purpose computer for image-processing, the computer can apply a discrete Fourier transform to corresponding pixels of a time series of image frames that spans multiple emission cycles (e.g., using any of the well-known fast Fourier transform (FFT) algorithms), resulting in a complex-valued frequency-domain intensity signal for each pixel. The peak of this signal will occur at the scan frequency for all pixels, but the associated phase will vary between pixels, depending on the phase within the emission cycle at which the pixel receives illumination.
[0077] In an embodiment, custom read-out circuitry can be employed, enabling the output signal of each pixel to be analyzed with an analog or digital phase detector, for example, that is driven by a reference signal whose frequency equals the scan frequency of the light source 502; the reference signal may be provided to the circuit, e.g., by the controller 506 of the light source. Suitable phase detectors are well-known to those of skill in the art, and can be implemented without undue experimentation. If a type-II phase detector is used, the output is a constant voltage proportional to the phase difference between the reference signal and the measured signal (of the same frequency). More detail on phase-detector circuits is available in the literature, e.g., in Wolaver, Dan H. (1991), Phase-Locked Loop Circuit Design, Prentice Hall, ISBN 0-13-662743-9. In some embodiments, discriminating between reflection signals and background light and/or identifying reflection peaks comprises some form of thresholding, (e.g., based on signal amplitude or intensity). Thresholding can be implemented in software, hardware, or a combination of both. In some embodiments, the detector is dormant until a reflection signal is detected; i.e., signal processing is triggered only upon detection of a threshold amount or intensity of light.
[0078] In the embodiments described above, the illumination is emitted in different directions at different times (or phases) within an emission cycle. Accordingly, for a detected reflection signal, the corresponding direction of the illumination can be determined from the point in the scan pattern ordering that light is emitted at the time of detection. In alternative embodiments, illumination can be emitted simultaneously in multiple directions from multiple sources, and the various emissions can be pulsed at different frequencies to facilitate discrimination between the different directions. For example, with reference to FIG. 5A, the light-emitting devices 520, 522, 524, 526, 528 can be operated continuously in a pulsed fashion, each at a different frequency; this is illustrated in FIG. 5E. In the image acquired by the sensor array 508, the reflection signal received at each pixel may be Fourier-transformed to determine, based on the frequency of the signal, from which of the light-emitting devices 520, 522, 524, 526, 528 the detected light originates. This way, each pixel can be associated with a direction of the illumination and, based on the position of the pixel within the sensor array, the direction of the reflected light. For example, if the object 510 lies in the path of light from light-emitting device 526, the Fourier-transformed signal, shown in FIG. 5F, would peak at the scan frequency of that device. Alternatively or additionally, discrimination between multiple illuminating emissions simultaneously emitted in different directions can be accomplished based on different light characteristics, such as color or wavelength, intensity, polarization, etc. For instance, different color filters may be applied to the light captured by a camera to identify, based on the color(s) detected, from which emitters the light originates.
[0079] The depth of an object 510 (or a surface point thereof) within the monitored region 504 may be determined by triangulation from the direction of the illumination that strikes the object 510 and the direction of the reflected light that is captured by the sensor array 508, the former being inferable from the time at which the light is received (e.g., the acquisition time, within the emission cycle, of the particular frame that captures the reflection) or, alternatively, the frequency of the detected signal, and the latter being inferable from the position of the object within the image (or the orientation of the scanning mirror in an embodiment with a MEMS camera). This is conceptually illustrated in FIG. 5A. In the depicted embodiment, the light source 502 and sensor array 508 are arranged such that the diameter of the light source 502 and the camera lens 542 lie in the same plane. Light emitter 526 emits an illuminating emission 550 at an angle .alpha., and the sensor array 508 receives a reflected emission 552 at an angle 13, both relative to a normal to that plane. The illuminating and reflected emissions 550, 552 together with a line connecting the center C.sub.1 of the light source 502 to the center C.sub.2 of the lens 542 form a triangle, isolated for greater clarity in FIG. 5D. The depth of the object 510 within the imaged region, i.e., the perpendicular distance y of the intersection point P of the light emissions 550, 552 (which is the point on the surface of the object 510 that intercepts the illuminating emission 550 and is detected in the image as the origin of the reflected emission 552) from the baseline connecting C.sub.1 and C.sub.2, can be computed from the angles .alpha., .beta. and the known length d of the baseline as:
y=d/(tan(.alpha.)+tan(.beta.))
For an extended object or multiple objects, the above analysis can be repeated for each such reflection to determine associated depths of the object(s). In some embodiments, a depth value is determined for each pixel in the image.
[0080] In the embodiment depicted in FIG. 5A, the light-emitting devices 520, 522, 524, 526, 528 are advantageously arranged such that the primary directions of their respective emissions all intersect at the center C.sub.1 of the light source 502, allowing the above formula to be applied straightforwardly to light emitted from any of the devices 520, 522, 524, 526, 528. As will be readily apparent to one of skill in the art, the same advantage can be achieved if the light-emitting devices 520, 522, 524, 526, 528 are arranged on the facets of a regular polygon 600 (or a portion thereof), as shown in FIG. 6A, or in any other manner that preserves a common intersection between the emissions from different directions, with the intersection point located in the plane of the lens. For example, as shown in FIG. 6B, a planar arrangement of light emitters 610 in combination with individual light-deflecting optics 612 (e.g., lenses) for each emitter 610 can be configured, by choosing suitable deflection angles via the orientations of the optics, to effect a common intersection point. Further, the light emissions in different directions need not be uniformly distributed over a complete half-circle, but may have varying angular spacing and/or cover an arc (i.e., a portion of a circle) that extends over more or less than 180.degree., depending on the desired angular extent of the scan field. FIG. 6C shows, for example, an arrangement of light emitters 620 on an arc segment 622 spanning about 120.degree.; the base of the arc is advantageously displaced from the plane of the camera lens 642 such that the center C.sub.1 of the circle falls in that plane.
[0081] Of course, the common intersection point of the emissions travelling in different directions serves merely computational convenience. Depth information can, in principle, be derived for any arrangement of light-emitting devices as long as their positions and orientations relative to each other and relative to the camera are known; the particular arrangement may, however, affect the computational complexity (e.g., in terms of the number of equations to be solved) of the depth determination. For example, a defined, fixed geometric relationship between the light-emitting devices of the light source can be achieved by integrating them with, mounting them on, or otherwise attaching them to a common rigid structure, e.g., made of plastic, metal, or any other suitable rigid material.
[0082] In some embodiments, a fixed geometric relationship also exists between the light source and the camera (or other light detector). For instance, as shown in FIG. 7A, the light source 700 and detector 702 may be mounted together in a single unit 704, and may receive power, and/or communicate with other devices (such as the image-processing facility 512), via cables 706 or wirelessly. The unit 704 may be of any size, shape, or material; in various embodiments, it is integrated with another device, such as a television, automobile, or computer. FIG. 7B shows another implementation, in which the light source 700 and detector 702 are maintained as separate units (one or both of which may be integrated into another device); the two units may be located at fixed, known spatial positions so that they, nonetheless, bear a fixed geometric relationship.
[0083] Alternatively, in some embodiments, the light source and light detector are movable relative to each other, either arbitrarily or consistently with one or more well-defined degrees of freedom. For example, the light source and detector may be integrated into a flexible or bendable pad or other structure, which fixes their distance along the surface of that structure, but allows their relative orientation and free-space distance to change. The information deficit arising from such unknown parameters of the geometric arrangement may be cured by using multiple sweeping light sources (i.e., multiple directed light sources with variable emission directions) and/or multiple detectors that, collectively, enable solving for the unknown parameters along with the desired depth information associated with the monitored region and/or objects. Embodiments include: (1) a photo-detector embedded in a device with emitters; (2) a photo-detector embedded in a second device with emitters directed to a photo-detector embedded in a first device; (3) a photo-detector separate unit from all emitters; (4) a photo-detector fixed to an object being tracked; (5) photo-detector(s) and emitter(s) can be implemented together as vcsels, such as for example the SPIE Vol 4652 Chip Scale Integration by Vixar, a company located at 2950 Xenium Lane, Suite 104, Plymouth, Minn.; and (6) other configurations including combinations of the described embodiments. Example layouts of emitters are illustrated by FIGS. 11E-11N and the accompanying description herein below. In further embodiments, described in more detail below, one of the light source or the detector is affixed to the object to be tracked.
[0084] The depth resolution that can be achieved with systems in accordance herewith can vary with the angular resolution of the scan. With light sources that emit light in a finite number of discrete principle directions (such as the light source 502 depicted in FIG. 5A), and assuming that the light detector temporally resolves all of these directions, the angular resolution relates directly to the angular spacing between the illuminating emissions generated by adjacent light-emitting devices. Thus, the larger the number of light-emitting devices is for a given angular coverage of the scan, the better is, in general, the angular resolution. In some embodiments, however, the angular resolution of the scan is effectively increased by exploiting spatial overlap between adjacent emissions to interpolate between their two primary directions. With reference to FIGS. 5B and 8A, consider, for example, an object 800 located at an angle mid-way between the primary emission directions of two adjacent light emitters 524, 526 whose diverging light emissions overlap. In this case, the time-varying intensity of the reflection from the object 800 (resulting from the control scheme of FIG. 5B) does not have a single maximum per cycle, but is equally bright when the object 800 is illuminated by light emitter 524 as when it is illuminated by light emitter 526, as is illustrated in FIG. 8B. By contrast, if the object 800 is located closer to the primary direction of light emitter 524, as shown in FIG. 8C, the intensity reaches its maximum when emitter 524 is turned on; the object 800 may, in this configuration, still receive and reflect light from emitter 526, but at a much lower intensity; this is shown in FIG. 8D. The closer the object 800 is to the primary direction of light emitted from either light emitter, the more pronounced is generally the reflection of light from that emitter, and the dimmer is any reflection of light from neighboring light emitter. Thus, the relative intensities of reflection signals resulting from the operation of the different light emitters can be used to determine the angular position of the object 800 relative to the light source with a precision that exceeds the angular resolution of the primary emission directions.
[0085] In some embodiments, the individual light-emitting devices are operated such that their respective emissions overlap not only spatially, but also temporally. For example, the light emitters may be turned on and off gradually (e.g., by varying their respective drive currents along a continuum), with each emitter being activated before its predecessor in the cycle is completely extinguished to provide a "cross-fade"; an exemplary control scheme is illustrated in FIG. 8E. At an individual pixel, the spatiotemporal overlap in activation of light emitters results in a continuous intensity distribution. Depending on the degree of temporal overlap, this intensity distribution can have a single maximum 810, as shown in FIG. 8F (for an object location along the primary direction of light emitter 526), or multiple local maxima 812 corresponding to the different pulses, with a global maximum 814 corresponding to the pulse that is emitted directly towards the reflecting object, as shown in FIG. 8G. In this case, the time-varying intensity can be analyzed to ascertain not only the global maximum 814, but also (or alternatively) the two local maxima 812 or minima 816 flanking it, which can increase the accuracy of the maximum determination. Techniques for determining maxima and minima vary widely, but in one embodiment, a derivative of the intensity vs. time (or distance) can be computed at points in time. When the derivative is zero, a maximum or minimum is indicated. (In some embodiments, the temporal resolution of read-out exceeds the temporal resolution corresponding to the different emission directions, e.g., multiple frames are acquired for each discrete light pulse.) In both cases, any asymmetry in the signal may be exploited to increase the angular resolution of the scan in a similar fashion as explained above with respect to FIGS. 8A-8D.
[0086] The temporal overlap between two adjacent light emitters may result, depending on the extent of spatial overlap between their emissions, in a bimodal angular distribution of the emitted light with varying relative magnitudes of the two peaks (which lie along the primary directions), or in a single peak that shifts from the primary direction of the first emission to the primary direction of the second emission. If the light emitters are turned on in the order in which they are arranged (e.g., from left to right or from right to left) they effectively create a continuous sweep, as the angle at which the intensity peaks varies continuously with time from the first emitter to the last emitter. By exploiting varying and overlapping intensity levels in this manner, the angular resolution of the scan can be increased in embodiments beyond that provided inherently by the different primary directions associated with the individual light emitters. In an embodiment, filters can be employed in conjunction with emitters of different characteristics (e.g., frequency, wavelength, polarization, phase, angular frequency, etc.) to provide improved discrimination between overlapping firing emitters.
[0087] FIG. 9A illustrates an embodiment in which a continuously sweeping light emission is created by a light source 900 that has two light emitters 902, 904. In one embodiment, the two emitters 902, 904 are controlled such that the sum of their central emission intensities is constant, but the intensity of each individual emitter's output varies between that constant value and zero; the intensities as functions of time may, e.g., be the squares of a cosine and a sine, respectively, as shown in FIG. 9B. With sufficient spatial overlap between the two emissions (e.g., chosen such that the intensity decreases by less than 50% from the source center to the midpoint between the two primary directions), this control scheme can produce an angular intensity distribution with a single maximum that oscillates back and forth between the two primary directions. For any point in time, the direction where the maximum lies can be determined straightforwardly by setting the derivative of the angular intensity distribution with respect to the angle to zero and solving for the angle. In the same manner, the relationship between the effective aggregate primary direction and the time or phase within the emission cycle can be theoretically determined for any number of spatio-temporally overlapping light emissions with discrete individual primary directions. Alternatively, the system may be calibrated to empirically determine the functional relationship between effective primary direction and time/phase; the calibration may involve placing an object sequentially at multiple known angles relative to the light source, acquiring frames during one or more emission cycles for each of these locations, and identifying the phase within each cycle that causes a detectable reflection signal.
[0088] Of course, the intensity of the light emitters need not necessarily vary along a continuum. Instead, each light emitter may step through a series of discrete illumination settings. The illumination of objects within the region of interest by different emitters can overlap in time ("cross-fade") such that, while one light emitter is still illuminated, the next one may begin illumination (e.g., at a low dimming setting). In some embodiments, three or more light emitters are illuminated concurrently at different settings, but, in other embodiments, only one light emitter is configured at the maximum setting at any given time. Some embodiments can vary overall angular resolution and/or accuracy achieved by the system 100, at least in part, by varying the number of discrete dimming levels.
[0089] In some embodiments, a continuous sweep is achieved with a light source that includes a rotating or otherwise moving light-emitting device. As shown in FIGS. 10A and 10B, the device 1000 may, for example, be mounted on a support structure 1002 (e.g., a bar or wheel) that rotates continuously in the same direction (FIG. 10A), or back and forth between two angular boundaries (FIG. 10B). In the former case, the rotating light source 1004 may be combined with two or more cameras 1006, 1008 facing in opposite directions to facilitate a full 360.degree. scan of the space surrounding the light source 1004 and cameras 1006, 1008. Alternatively, as illustrated in FIG. 10C, two light-emitting devices 1010, 1012 may be mounted on opposite ends of the support structure 1002 to continuously scan the half space imaged by a camera 1014 while the light source undergoes a full 360.degree. rotation. As will be readily apparent to one of skill in the art, moving light sources can generally be implemented with one, two, or more light-emitting devices in a variety of suitable configurations.
[0090] Further, instead of moving (e.g., rotating) the light-emitting device itself, a moving light source may utilize a moving deflecting optic in conjunction with a stationary light emitter. In various embodiments, illustrated in FIGS. 10D-10F, the deflecting optic is a lens 1020, a prism 1022, or a semicircular slab 1024 with a high index of refraction. In the embodiment of FIG. 10F, the slab 1024 may be arranged relative to the light-emitting device 1026 such that the light enters the slab 1024 through its curved boundary and exits it always at the center point 1028. This configuration results in a scanning that originates from the same point, simplifying the computation of depth values. Computational simplicity is also aided, in various embodiments, by utilizing a narrow, highly collimated light source, e.g., a laser diode.
[0091] Yet another approach to generating a continuously moving illumination involves the use of a moving screen in front of a light-emitting device that emits over a substantial spatial angle (or, in some embodiments, isotropically in many directions); FIG. 10G shows an exemplary embodiment. The screen 1030 transmits light through a hole, slot, or other perforation 1032 while blocking light transmission in other directions, thereby "cutting" a narrower window out of the light from the emitter. This light emission moves (e.g., rotates) as the perforation moves along with the screen; thus, the light emitter and moving screen together form a moving light source. Additional embodiments of moving light sources may occur to people of skill in the art, and are to be considered within the scope of the disclosed technology.
[0092] In some embodiments providing a spatially continuous sweep across the region of interest (whether implemented by a moving light source or by a number of discrete stationary emitters with gradually varying and temporally overlapping intensity), the angular resolution of the scan, and thus the depth resolution, depends on the temporal resolution of image acquisition, i.e., the rate at which information is read from the camera. For conventional cameras, the frame rate can often be increased at the cost of decreasing the spatial resolution; for example, by reading out only every other pixel, the frame rate can be doubled. In some embodiments, the pixel-read-out density and frame rate are set such that the lateral and depth resolution achieved by the system are approximately the same.
[0093] In some embodiments in which relatively low or moderate scan rates, low or moderate angular resolutions of the scan (as determined by the density of different directions that light can be emitted or the read-out rate of the camera, or both or other limiting factors) are employed, and having short or medium distances between the object of interest, the light source and detector, the emission of light in a certain primary direction and the detection of its reflection by the detector can be considered to occur practically simultaneously, i.e., before the direction changes and/or within the same frame. Consequently, the travel time, or time of flight, of light from the source to the object and then to the detector can be neglected in these cases. For example, if the object is no more than one hundred meters away from the light source and detector, the time of flight is less than a microsecond. Accordingly, as long as emissions of light having different directions are separated in time by more than, say, a microsecond, the reflection can, for practical purposes, be considered as received instantaneously. In some embodiments contemplating higher scan rates and angular resolution and/or larger distances, however, the time of flight can be taken into consideration to accurately determine the emission direction that corresponds to a particular reflection signal from the time of receipt of that signal. For instance, if the emission direction changes, and a new image frame is acquired, every nanosecond, a total travel distance of only ten meters results in a shift of 33 frames between emission of the light and capture of the reflection. Thus, in order to accurately determine the position of the object, a reflection received by the detector should be associated with the emission direction 33 frames (or 33 ns) prior. A synching event, (e.g., pause in scan, burst of energy in scan by activating all, most, many emitters contemporaneously, etc.) can be used to synch up emitter scan cycle and detector scan cycle. In one embodiment, illustrated by FIG. 8H, a synching event includes a time delay between cycles having a time period of sufficient duration that any emitted energy will have returned.
[0094] Of course, the time period needed for energy emitted to return is typically not known a priori in embodiments in which the distance of the object from the light source and detector is the very parameter to be measured. In some embodiments, this problem is addressed by determining the distance iteratively: in a first iteration, the position of the object, and thus its distance from the source and detector, may be determined based on the assumption that the time of flight is zero. The distance thus determined is then used to compute a round-trip travel time adjustment, determine a corrected emission direction, and re-compute the object position. This process may be repeated for a fixed number of iterations, or until a positional accuracy is achieved or some other convergence criterion is satisfied; in some embodiments, one or two iterations suffice for the desired accuracy of the positional measurement.
[0095] In the above discussion, the operation of the described embodiments is, for ease of explanation, illustrated for two-dimensional space; the disclosed technology is, however, not limited to two dimensions. Other embodiments incorporating the principles discussed herein to three dimensions will be readily apparent to those of skill in the art. For example, while FIG. 5A implies that the light source 502, sensor array 508, and object 510 all lie in the same plane, e.g., the horizontal plane, this need not necessarily be the case as shown by FIG. 15 herein below. The object 510, for example, may lie above or below the horizontal plane, and may nonetheless be illuminated by the light emissions during a horizontal sweep of that plane due to the inherent vertical extent of the light emitted. The sensor array 508 may capture a two-dimensional image of the region 504, mapping all light incident upon the detector under a particular angle relative to the horizontal scan plane to the same row of the image sensor. For example, a reflection signal received from an object location within the scan plane may strike a sensor row within that same plane, whereas a reflection received from an object location below the scan plane may strike the sensor pixels in a row above the plane, and vice versa. From the horizontal position of the reflection in the data frames (i.e., the column of the image sensor) and the direction of the illumination corresponding to this reflection, the depth of the object can be calculated, e.g., as explained with respect to FIG. 5A. The depth value in conjunction with the two-dimensional location of the reflection in the image, in turn, allows computing the location of the reflection point on the surface of the object in a plane parallel to the image plane at the determined depth. Thus, the three-dimensional position of the object is computed.
[0096] In an embodiment, an intensity threshold may be used to define the emission diameter as the full width of the emission portion that covers intensities down to the threshold value (e.g., down to half the maximum intensity). Thereby, embodiments can provide the ability to accommodate situations wherein the emission intensity falls off on one or more sides of a "peak" defining a horizontal scan plane (e.g., according to a Gaussian or similar vertical intensity distribution). The light practically sweeps a three-dimensional slice of a thickness corresponding to that diameter. To expand the spatial volume covered by the scan, the light source 502 may be equipped with means for deliberately increasing the vertical emission diameter and/or divergence, such as a cylindrical lens or other diverging optic, and/or with means for narrowing the horizontal divergence without affecting the vertical divergence, such as a vertical slot.
[0097] In alternative embodiments, the monitored region is expanded, or the accuracy of positional determinations therein is increased, by utilizing multiple intersecting or parallel scan planes, or by scanning a three-dimensional spatial volume with a beam whose primary direction can be varied both azimuthally and attitudinally. FIG. 11A, for instance, shows a light source that includes two mutually perpendicular linear arrangements 1100, 1102 of discrete light-emitting devices 1104, which may be positioned on a planar or curved surface. In some embodiments, the rows correspond to the equator and meridian, respectively, of a semispherical surface 1106, as shown in FIG. 11B. FIG. 11C illustrates another embodiment, in which discrete light-emitting devices 1104 are distributed uniformly over a semispherical surface 1106 (or as smaller or larger surface portion of a sphere). In FIG. 11D, the light-emitting devices 1120 are mounted on the faces of a regular polyhedron 1110. (Dashed lines indicate edges or light emitters that are hiding from view.) The light sources shown in FIGS. 11C and 11D are three-dimensional generalizations of the light sources depicted in FIGS. 4A, 5A and 6A. FIGS. 11E and 11F illustrate sources 1104 comprising two or more lighting elements 1104a disposed on surface 1112 along with photo-detectors 1103. Surface 1112 can be flat, curved, or a combination of multiple surface portions. In one embodiment photo-detectors 1103 receive reflectance of emissions of energy emitted by sources 1104 co-located on surface 1112 as described in further detail with reference to FIGS. 4A-1, 4A-2, and 13A. In an alternative embodiment, more than one "scanner" unit comprising surface 1112, sources 1104, and photo-detectors 1103 can be implemented together such that photo-detectors 1103 of a first surface 1112 receive reflectance of emissions from sources 1104 of a second surface 1112 and vice versa. In FIG. 11E, source 1104 includes a plurality of photo-emitting elements which can be individually activated to emit electromagnetic energy in various directions sequentially, randomly or according to a pattern. Thus, the "firing order" indicated by numerals assigned to photo-emitting elements 1104a are illustrative of one exemplary firing order used in some embodiments. FIGS. 11G-11H illustrate different arrangements of sensors and emitters configured on a single surface 1112. FIGS. 11I-11J illustrate sensor-and-emitter pair configurations on a single surface 1112. FIGS. 11K-11N illustrate a variety of other configurations of sensors and emitters on a single surface 1112. Of course, moving lights sources as described, e.g., with respect to FIGS. 10A-10G can similarly be generalized to three-dimensional structures. For instance, a light-emitting device may be mounted on a sphere with two rotational degrees of freedom, or combined with a lens that can rotate about two mutually perpendicular axes lying in the plane of the lens (i.e., perpendicular to its optical axis) and intersecting at its center.
[0098] Various embodiments of systems for determining distance, depth, or other positional information associated with objects have heretofore been described. As will be readily appreciated by those of skill in the art, the performance of the various systems--in terms of accuracy and precision or resolution of the positional determinations--varies greatly, depending on a number of system parameters including, but not limited to, the type (e.g., discrete vs. continuous) and scan rate of the light source, the number of discrete light-emitting devices (if applicable), the beam divergence, the existence and/or extent of spatial and/or temporal overlap of emissions of different sources, the read-out scheme and rate of the camera, the spatial resolution of the camera, and/or the type of data analysis. Some embodiments can determine depth within approximately millimeters or micrometers of accuracy; other embodiments may determine positional information within approximately centimeters of accuracy. The disclosed technology is, however, not limited to any particular accuracy (or other performance parameter), and certain attributes of the disclosed technology may be adjusted to increase or decrease accuracy and/or performance, e.g., as applications of the disclosed technology require. For example, in embodiments that utilize light sources with multiple light-emitting devices generating emissions in a finite number of discrete directions, a coarse scan can be achieved by skipping some light sources when situations call for less accuracy, and a more accurate, fine-grained scan can be achieved by operating the light source with a larger number of light-emitting devices. In some embodiments, a coarse scan of an entire field of view is conducted to locate one or more objects, and then followed by a comparatively fine-grained scan limited to a portion of the field of view in which the object has been located. The fine-grained scan may serve to identify detailed features of the object(s), thereby enabling different objects (e.g., hands of different human users, different pets walking across the field of view, etc.) to be distinguished.
[0099] FIGS. 12A and 12B summarize two methods in accordance herewith, which correspond to two respective classes of applications. FIG. 12A shows a method 1200 that can be used to determine depth values for all pixels of an image capturing a region of interest. The method 1200 involves repeatedly sweeping the region of interest with an emission (action 1202), and capturing one-dimensional or, more typically, two-dimensional images of the region at a rate that resolves the different directions of the emission at the desired accuracy (action 1204). (Capturing images herein means that light from different locations within the region corresponding to different directions of incidence on the image sensor is resolved in some manner (e.g., spatially with a pixelated sensor, or temporally via a raster scan), regardless whether the image data is read out, stored, analyzed, and/or computationally represented frame by frame or, e.g., pixel by pixel.) Further, the method includes determining, for each pixel, the maximum intensity of the detected reflection during an emission cycle and the corresponding phase within the cycle (1206) (which may, in some cases, be the only phase for which a reflection signal is detected at all). In some embodiments, this is done separately for every emission cycle so that any movements of objects within the region are detected at the scan rate; in other embodiments, the signals for multiple successive emission cycles are averaged to improve accuracy at the cost of responsiveness. From the phase of peak-intensity, the direction of the emission to which this peak is attributable is determined for each pixel (action 1208), and based on the angles of the illuminating and reflecting emissions, the depth is computed (e.g., as explained with respect to FIG. 5C) and associated with the respective pixel (action 1210). This way, a complete depth profile of the image is obtained. This may serve to measure not only the (e.g., three-dimensional) position of an object as a whole, or the positions of multiple objects (including objects bounding the monitored space, such as walls), but also to determine, e.g., the shape an object's surface and/or any changes thereto over time. The process may be repeated to track changes of the object location, shape, etc. For example, in some embodiments, the object is a person's hand, whose position, orientation, and articulation are tracked, e.g., for purposes of gesture recognition.
[0100] FIG. 12B illustrates a method that may be more appropriate for tracking the position(s) of one or more objects within a spatial region that is large compared to the dimensions of the object(s). This method 1220 likewise includes scanning the entire region repeatedly with a light beam (action 1222) and acquiring images of the region (action 1224). However, the method 1220 deviates in the analysis of the image data. Rather than determining depths for all pixels, it involves identifying object(s) of interest in the (one- or two-dimensional) camera images (1226), and computing depth values only for one or more pixels of the identified object(s) (actions 1228, 1230, 1232). The object(s) may be identified in the images in any of a number of ways, e.g., using conventional edge-detection or patch-detection techniques, template matching against a database of object images, and/or foreground/background discrimination based on the intensity of the measured reflection integrated over an entire emission cycle (which will generally be greater for objects in the foreground, due to the decrease in intensity with the square of the distance). For pixels of interest, depth may then be determined using the same procedure as described above for method 1200, i.e., by determining of the phase within the emission cycle for which the reflection intensity is maximized (action 1228), inferring the corresponding illuminating-beam direction therefrom (action 1230), and computing the depth from the angles of the illuminating and reflected light (action 1232). Advantageously, this method 1220 reduces the computational resources required to process the images.
[0101] Further, while certain embodiments described heretofore utilize a camera that provides one- or two-dimensional frames imaging light reflected from objects of a region of interest, which can be supplemented with depth information employing the methods described above, certain alternative embodiments do not require the use of a multi-element camera, but can localize objects using only a single photo-sensitive element (or multiple individual elements in different locations) in conjunction with a directed light source with variable beam direction. The light source may scan a spatial region according to a suitable scan pattern. For instance, the region may be divided into a number of subregions (e.g., four quadrants), which are then sequentially illuminated. When the illuminating light strikes an object, a reflection signal is detected by the light-sensitive element. The time of receipt of the reflection signal allows an inference of the direction of the illuminating emission and, thus, of the subregion in which the reflecting object is located. (Alternatively, multiple illuminating emissions having different properties, e.g., different color, may be used simultaneously and distinguished using suitable filters with the detector(s).) Multiple light sources and detectors may be used to scan the region of interest along different planes so as to provide three-dimensional information. For example, a cubic volume may be scanned along two perpendicular planes, each divided into four quadrants. Localizing an object in one of the four quadrants for both scans allows identifying in which one of eight sub-cubes the objects is located. As will be apparent to one of skill in the art, the spatial resolution of object localization achieved in this manner corresponds directly to the spatial resolution of the scan pattern; the more subregions there are, the more precise is the determined object location.
[0102] In embodiments that utilize multiple light sources, the light emanating therefrom may be distinguished based on its spectral properties (color, frequency, wavelength), intensity, polarization, the (angular) frequency or repetition rate of the scan pattern, the frequency of a binary flash pattern, a temporal intensity modulation pattern, or some other optical property or pattern. For example, if two light sources scan the region of interest periodically, but each at its own repetition rate, a detector may Fourier transform the overall signal it receives to identify peaks at two frequencies corresponding to the two repetition rates. Similarly, if two light sources flash at different frequencies, a Fourier transform and/or suitable frequency filters facilitate discriminating between them and/or extracting a signal corresponding to one or the other light source. Staged filtering allows first extracting the signal from a particular light source and then (following demodulation) extracting a signal at the scan frequency (i.e., repetition rate). Alternatively or additionally, if the different light sources emit different colors or polarizations, the detectors may be equipped with suitable spectral or polarization filters to differentiate between signals from the different sources. An exemplary embodiment is illustrated in FIG. 13A, where an object 1300 may intersect light emitted from two light sources 1302, 1304 that produce light having different characteristics (say, emit light of different colors). A number of light detectors (which may be individual photosensitive elements, or combinations thereof such as cameras) are placed in various locations to capture reflections off the object, each detector being adapted, e.g., via a suitable filter, to receive light only from one of the light sources 1302, 1304. Thus, as illustrated, detector/filter combination 1306 captures light originating from light source 1302, whereas detector/filter combinations 1308, 1309 capture light originating from light source 1304. Of course, many more light sources and/or detectors may be used. A particular light source may have one or more associated detectors for receiving light from that source. Further, multiple light sources that emit light with the same properties (e.g., color) may share one or more associated detectors. The embodiments described above all take advantage of diffuse reflections of the emission, i.e., of light scattered in all directions. This allows the camera or other sensor to capture reflections off any object within its field of view, regardless of the angle of incidence on the object surface and the angle relative to the surface normal under which the detector appears from the point of incidence (which is the angle of reflection for the portion of the reflected light that is captured). In certain alternative embodiments, specular reflection is used instead. For that purpose, an object of interest may be specially equipped with a reflector (i.e., mirror), or the surface properties of the object may inherently cause specular reflection (e.g., for smooth, metallic surfaces). Since, for specular reflection, the angle of reflection equals the angle of incidence, illuminating light that "sweeps" across the reflector generally results in a sweeping reflection. In order to increase the likelihood of capturing a signal from this moving reflection, a plurality of detectors may be employed, e.g., distributed over a bounding surface (e.g., defined by one or more walls) of the region of interest. Further, as with diffuse-reflector embodiments, multiple light sources may be used, e.g., to scan the region of interest along different planes or in different directions. The light sources may differ in the light and scanning properties (e.g., color, polarization, angular frequency of the scan, etc. as described above) to enable the detectors to distinguish between signals originating from different light source.
[0103] Alternatively, to ensure the continuous detection of the reflected light, the object of interest may be equipped with a reflector that reflects light back into the direction it came from, with minimal scattering. Various types of retro-reflectors are well-known to those of skill in the art; one example is a corner reflector, which includes three mutually perpendicular mirror surfaces arranged like three interior walls of a cube that have a common corner point. In retro-reflector embodiments, the reflected light can be captured by a light detector that is co-located with the light source. For purposes hereof, the detector is co-located with the light source if it is sufficiently close to the light source to intercept the reflected light, i.e., if its distance from the optical axis is smaller than the beam-profile radius of the reflected beam at the light source. (The beam radius may be defined, e.g., based on the maximum allowable intensity fall-off from the central peak intensity, and this maximum allowable fall-off may, in turn, depend on the sensitivity of the detector). In general, the allowable distance of the detector from the light source is the greater, the more divergent the beam is and the more distant the object of interest is. The light detector may be a single photodiode, phototransistor, photovoltaic cells, photoresistor or other kind of photo-sensing device, or an array or irregular arrangement of multiple such devices. In some embodiments, multiple light-sensing cells are arranged in a ring around the light source to capture a large portion of the reflected light. Importantly, since the reflection of interest comes, at any point in time, only from one direction (which is the direction of the illuminating beam), the sensor need not resolve different directions of incoming light; consequently, there is no need for a focusing optic or for a pixel-wise read-out of the sensor. Instead, to the extent the detector comprises more than one light sensors, the detected light is integrated over all of the sensors to yield an aggregate signal. (Of course, this does not exclude the use of a regular camera with a pixelated sensor and lens.)
[0104] FIG. 13B illustrates how a light source 1310 and co-located detector 1312 may be used to track a retro-reflecting object 1314. As with the diffuse-reflection embodiments described above, the light source 1310 generates a beam 1316 of variable direction to sweep a region of interest 1318, which is, in this case, a region where the object of interest 1314 is generally expected. The variable beam direction may be achieved with multiple cyclically operated light-emitting devices with fixed beam directions, with one or more moving light emitters, with a fixed light emitter and moving deflector, or generally with any of the light sources described above. The light source 1310 may be operated to repeatedly scan the entire region 1308, preferably at a rate that is fast compared to the rate of motion of the object 1314. Alternatively, the light source may scan only a subregion around the previously measured location, or a projected expected location, of the object 1314. The object 1314 has a retro-reflector 1320 (or multiple retro-reflectors 1320, in which case an orientation information can be discerned as well) integrated therewith or attached thereto such that, whenever the beam 1316 strikes the retro-reflector 920, a reflection signal is sent back to and measured by the detector 1312. Control and detector circuitry 1322 (implemented in a single device or multiple intercommunicating devices) associated with the light source 1310 and the detector 1312 correlates the measured signal with the direction of the illuminating beam 1316 from which it originates. The circuitry 1322 may, for example, include a controller for operating the light source 1310 and an analog phase-detecting circuit that receives a clock signal of the scan frequency as a reference, and measures the timing of the detected reflection relative thereto. Thus, the direction, measured from the light source 1310 and detector 1312, at which the object 1314 occurs can be determined as a function of time.
[0105] If the movement of the object 1304 is confined to a known trajectory (e.g., by means of rails), the intersection of the measured direction with that trajectory uniquely determines the position of the object. Otherwise, additional information may be obtained from a second light-source/detector pair, hereinafter referred to as a "scanner." For instance, as shown in FIG. 13C, the position of an object 1330 that moves in two dimension may be determined from two two-dimensional scans simultaneously performed by two scanners 1332, 1334. Each of the scanners 1332, 1334 determines a line along which the object is located during a given emission cycle. The intersection 1336 of the two lines specifies the position of the object 1330. Note that, although each line corresponds to the primary direction of the beam that strikes the object 1330, the two beams need not strike the object 1330 at the same time, and consequently need not, and typically do not, intersect each other at the current object location. In fact, the two scanners 1332, 1334 may operate independently from each other, and even at different scan frequencies, as long as they track the object relative to a common spatio-temporal reference frame. Of course, the embodiment illustrated in FIGS. 13B and 13C can straightforwardly be extended to more than two scanners and/or three-dimensional scan patterns, e.g., to take redundant measurements for improved accuracy and/or to allow tracking an object in three dimensions. Object-tracking methods that utilize specular reflection in accordance herewith may be used, e.g., in various industrial contexts. For instance, they may serve to track the positions of robots moving across a manufacturing floor or a distribution and mailing center. One or more scanners may be mounted, e.g., onto the walls or ceiling, to sweep a light beam thereacross and capture reflections from retro-reflectors affixed to the robots.
[0106] In some embodiments employing specular-reflection techniques, the roles of the scanner and the retro-reflector are reversed, and one or more retro-reflectors are fixed in space to serve as reference locations for a moving object equipped with a scanner. In two dimensions, three retro-reflectors 1340 at known locations suffice to uniquely determine the location and/or orientation of the object 1342 from measurements of the three angles .gamma..sub.1, .gamma..sub.2, .gamma..sub.3 enclosed between the lines of sight connecting the object 1342 to respective pairs of retro-reflectors 1340, as illustrated in FIG. 13D. This configuration may find its application, for example, in the triangulation of mobile device positions. An inexpensive scanner may be integrated into a cell phone or other mobile device, and three or more retro-reflectors may be mounted, e.g., on buildings, cell towers, or other permanent structures. The scanner may continuously sweep its surroundings, preferably with light outside the visible range (e.g., IR light). Based on the reflection signals received from three (or more) retro-reflectors at known locations, the position of the mobile device can be computed. To facilitate distinguishing the reflection signals received from different retro-reflectors, the reflectors may alter some property of the light, such as a polarization, spectral property (e.g., wavelength/frequency, or color), amplitude modulation, etc.). The different reflectors may have different physical properties (e.g., shape, size, color), reflective properties, surface characteristics (e.g., patterns), etc. to effect the different light properties. In some embodiments, the retro-reflectors are positioned at known, elevated heights. Assuming that the scanner is on or near the ground, this allows a determination of the distance between the scanner and retro-reflector based on the azimuthal angle of the reflector as measured from the scanner. With directional and distance information available, the position of the mobile device can be inferred from only two reflection signals. Alternatively, the distances may be used to verify and/or increase the accuracy of the computed device location.
[0107] In some embodiments, time of flight techniques or Doppler techniques can be used in conjunction with the techniques described herein. For example, during an initial phase, the light source may be controlled to emit, for a number of emission cycles, only one pulse in one direction per emission cycle, allowing a determination of the delay between the time of emission and the time of receipt of any corresponding reflection. This procedure may be repeated for multiple beam directions until a reflection signal is detected.
[0108] In embodiments where the light source sends out discrete pulses, and the pulse rate and dimensions of the monitored space are such that the reflection of each pulse is detected before the next pulse is emitted, allowing each image frame to be associated straightforwardly with the direction of the illuminating beam, time-of-flight measurements may be used to supplement the triangulation-based depth/distance determination. For example, if the camera is read out much faster than the illuminating beam changes direction, i.e., a sequence of multiple images is acquired for each pulse, the time delay between the emission of the pulse and the receipt of the reflection can be inferred readily from the number of the image within the sequence that captures the reflection.
[0109] Furthermore, at significantly higher camera read-out rates, slight time-of-flight differences between pulses from different light emitters reflected by the same object may be resolved; such time-of-flight differences may result from slightly different distances between the various emitters and the object. For instance, two light-emitting devices may emit pulses of light at t=10 ns and t=11 ns, respectively. The first pulse may arrive at the camera sensor at t=10.5 ns while the second pulse may arrive at t=11.6 ns, revealing that the travel time of light from the second emitter is 0.1 ns longer (corresponding to an additional distance of 3 cm). For certain advantageous geometric arrangements of the light emitters, such as the one depicted in FIG. 5A, the light source that emits directly towards an object is also the one closest to the object. Thus, if the pulse emitted directly toward the object results in the brightest reflection signal--as it ordinarily does--the minimum travel time (or phase difference between pulse emission and detection), among the pulses emitted during an emission cycle, generally coincides with the maximum intensity. However, the relationship between the direction of illumination and brightness of the reflection may, in some cases, not hold, e.g., due to surface irregularities of the object that cause different reflectivity for light incident from different directions. A travel-time-based determination of the direction of the illuminating beam along which the object is located may, in these scenarios, be more accurate or reliable than an intensity-based determination. Measurements of the Doppler shift of light (or other radiation) reflected by a moving object can provide additional information about the motion of the object, which may supplement information obtained with methods described herein.
[0110] The various embodiments described herein generally utilize some type of control and/or computational facility (hereinafter "computer") for operating the light source and detector and analyzing the captured signals or images. This computer may be provided in various form factors, and may be implemented in one or more dedicated, application-specific devices (e.g., a DSP or ASIC) designed or selected for use with the light source and/or detector, or integrated into another, stand-alone computing device (such as a personal computer, tablet computer, or a smart phone), depending on the application context. In one embodiment, some or all of the functionality of the computer is integrated into the light source (e.g., into the support structure onto which the light-emitting devices are mounted) and/or incorporated into or affixed to the detector. The computer may include digital circuitry (e.g., a computer processor and memory) and/or analog circuitry (e.g., an analog phase detector).
[0111] FIG. 14 shows, in a simplified block diagram, an exemplary embodiment of a computer 1400 for determining a distance to an object in accordance with an embodiment of the disclosed technology. The computer 1400 may include a processor 1402, memory 1404 (e.g., RAM, ROM, and/or flash memory), one or more interfaces 1406 for the light source and detector, and/or one or more user input/output devices 1408 (e.g., a display (optionally touch-enabled), speakers, a keyboard, and/or a mouse), as well as one or more buses 1409 over which these components communicate. The computer 1400 may also include other removable/non-removable, volatile/nonvolatile computer storage media, such as a solid-state or magnetic hard disk, an optical drive, flash memory, random-access memory, read-only memory, or any other similar type of storage medium. The processor 1402 may be a general-purpose microprocessor, microcontroller, digital-signal processor, or any other type of computational engine. The interface 1406 may include hardware and/or software that enables communication between the computer 1400 and the light source and/or detector. For example, the interface 1406 may include one or more data ports (such as USB ports) to which devices may be connected, as well as hardware and/or software signal processors to modify sent or received data signals (e.g., to reduce noise or reformat data). In some embodiments, the interface 1406 also transmits control signals to, e.g., activate or deactivate attached devices, to control camera settings (frame rate, image quality, sensitivity, zoom level, etc.), or the like. Such signals may be transmitted, e.g., in response to control signals from the processor 1402, which may in turn be generated in response to user input or other detected events.
[0112] The memory 1404 may be used to store instructions to be executed by processor 1402 as well as input and/or output data associated with execution of the instructions. These instructions, illustrated as a group of modules, control the operation of the processor 1402 and its interaction with the other hardware components. Typically, an operating system 1410 directs the execution of low-level, basic system functions such as memory allocation, file management, and operation of mass storage devices. The operating system may be or include a variety of operating systems, such as WINDOWS, LINUX, OS/X, iOS, Android or any other type of operating system. At a higher level, the memory 1004 may store control modules 1412, 1414 for operating the light source and the camera (or other detector), an image-analysis module 1416 for analyzing the image data received from the detector (e.g., to determine the intensity maximum of the time-varying signal for each pixel, to identify objects of interest and determine the associated direction of the incident beam, etc.), and a triangulation module 1418 that computes depth and/or distance values based on the measured image data and the corresponding control state of the light source. In general, the instructions may be implemented in any programming language, including, for example, C, C++, JAVA, Fortran, Basic, Pascal, or low-level assembler languages.
[0113] Embodiments of the disclosed technology may be used to map out a room or similarly sized area in order to determine its dimensions and/or precisely locate room walls as well as objects, people, or other things in the room. This information may be used by a computer, television, or other device or machine in the room to improve the experience of a user of the device by, for example, allowing the user to interact with the device based on the room dimensions. The device may adjust a property of its output (e.g., a sound level, sound distribution, brightness, or user-interface perspective) based on objects in the room or the position of the user. Further embodiments can be used to track the motion of objects in a field of view, optionally in conjunction with other mobile-tracking systems. Object tracking may be employed, for example, to recognize gestures or to allow the user to interact with a computationally rendered environment; see, e.g., U.S. Patent Application Ser. No. 61/752,725 (filed on Jan. 15, 2013) and Ser. No. 13/742,953 (filed on Jan. 16, 2013), the entire disclosures of which are hereby incorporated by reference.
[0114] FIG. 15 illustrates an exemplary task environment in which a human operator 1500 of a machine 1502 interacts with the machine 1502 via motions and gestures. The machine may be communicatively coupled to and receive information about the motions and gestures from one or more light-source/detector pairs 1504. For example, as shown, three light-source/detector pairs 1504 are used to scan the region of interest horizontally and vertically. Of course, different numbers and arrangements of light sources and detectors (whether provided in source/detector pairs 1504 or in configurations where the light sources and detectors are located independently) may be employed in other embodiments. To conduct machine control, a region of space in front of or near the machine 1502 (or, alternatively, in other designated portions of the room) may be scanned by directing one or more light emissions from the vantage point(s) or region(s) of the light source(s) to the region of space, detecting any reflectance of the light emission from an object or objects within the region, and, if a reflectance is detected, inferring therefrom the presence of an object (or objects) in the region of space.
[0115] For example and with reference to FIG. 16, an exemplary embodiment of a variation-determination system 1600 comprises a model-management module 1602 that provides functionality to build, modify, and/or customize one or more models to recognize variations in objects, positions, motions, and/or attribute states or changes therein based on sensory information obtained from a suitable detection system, such as system 100 shown in FIG. 1. A motion capture and sensory analyzer 1604 finds motions (e.g., translational, rotational), conformations, and presence of objects within sensory information provided by detection system 100. The findings of motion capture and sensory analyzer 1604 serve as input of sensed (e.g., observed) information from the environment with which model refiner 1606 can update predictive information (e.g., models, model portions, model attributes, and so forth).
[0116] The model refiner 1606 may update one or more models 1608 (or portions thereof) from sensory information (e.g., images, scans, other sensory-perceptible phenomena) and environmental information (i.e., context, noise, and so forth); enabling a model analyzer 1610 to recognize object, position, motion, and/or attribute information that might be useful in controlling a machine. Model refiner 1606 employs an object library 1612 to manage objects including one or more models 1608 (e.g., of user portions (e.g., hand, face), other control objects (e.g., styli, tools) or the like) (see, e.g., the models depicted in FIGS. 17A and 17B), and/or model components (e.g., shapes, 2D model portions that sum to 3D, outlines and/or outline portions (e.g., closed curves), attributes (e.g., attach points, neighbors, sizes (e.g., length, width, depth), rigidity/flexibility, torsional rotation, degrees of freedom of motion, and others), and so forth) useful to define and update models 1608 and model attributes. While illustrated with reference to a particular embodiment in which models, model components, and attributes are co-located within a common object library 1612, it should be understood that these objects will be maintained separately in some embodiments.
[0117] With the model-management module 1602, one or more object attributes may be determined based on the detected light. Object attributes may include (but are not limited to) the presence or absence of the object; positional attributes such as the (e.g., one-, two-, or three-dimensional) location and/or orientation of the object (or locations and/or orientations of various parts thereof); dynamic attributes characterizing translational, rotational, or other forms of motion of the object (e.g., one-, two-, or three-dimensional momentum or angular momentum); physical attributes (e.g., structural or mechanical attributes such as appearance, shape, structure, conformation, articulation, deformation, flow/dispersion (for liquids), elasticity); optical properties or, more generally, properties affecting or indicative of interaction with electromagnetic radiation of any wavelength (e.g., color, translucence, opaqueness, reflectivity, absorptivity); and/or even chemical properties (as inferred, e.g., from optical properties) (such as material properties and composition).
[0118] In some embodiments, scanning the region involves multiple emission cycles. During different emission cycles, the region may (but need not) be scanned in accordance with different scan patterns. For example, an initial emission cycle may serve to detect an object, and during a subsequent cycle, a more refined scan pattern may serve to capture surface detail about the object, determining positional information for at least a portion of the object, or determining other kinds of object attributes. Multiple sequential emission cycles may also serve to detect changes in any of the object attributes, e.g., due to motion or deformation; for such differential object-attribute determinations, the same or similar scan patterns are typically used throughout the cycles. The object attributes may be analyzed to identify a potential control surface of the object.
[0119] FIG. 17A illustrates predictive information including a model 1700 of a control object constructed from one or more model subcomponents 1702, 1703 selected and/or configured to represent at least a portion of a surface of control object 112, a virtual surface portion 1706 and one or more attributes 1708. Other components can be included in predictive information 1710 not shown in FIG. 17A for clarity sake; such as models (user portions (hand, face), objects (styli, tools), model components (shapes, e.g., 2D model portions that sum to 3D), and model-component attributes (e.g., degrees of freedom of motion, torsional rotation, attach points, neighbors, size (length, width, depth), rigidity/flexibility), and others). In an embodiment, the model subcomponents 1702, 1703 can be selected from a set of radial solids, which can reflect at least a portion of a control object 112 in terms of one or more of structure, motion characteristics, conformational characteristics, other types of characteristics, and/or combinations thereof. In one embodiment, radial solids include a contour and a surface defined by a set of points having a fixed distance from the closest corresponding point on the contour. Another radial solid embodiment includes a set of points a fixed distance from corresponding points on a contour along a line normal thereto. In an embodiment, computational technique(s) for defining the radial solid include finding a closest point on the contour and the arbitrary point, then projecting outward the length of the radius of the solid. In an embodiment, such projection can be a vector normal to the contour at the closest point. An example radial solid (e.g., 1702) includes a "capsuloid", i.e., a capsule-shaped solid including a cylindrical body and semi-spherical ends. Another type of radial solid (e.g., 1703) includes a sphere. Other types of radial solids can be identified based on the foregoing teachings.
[0120] In an embodiment and with reference to FIG. 17B, updating predictive information to observed information comprises selecting one or more sets of points 1750 in space surrounding or bounding the control object within a field of view of one or more image-capture device(s). As shown, points 1750 can be determined using one or more sets of lines 1752A, 1752B, 1752C, and 1752D originating at vantage point(s) associated with the image-capture device(s) (e.g., FIG. 1: 130A, 130B) and determining therefrom one or more intersection point(s) defining a bounding region (i.e., region formed by lines 1752A, 1752B, 1752C, and 1752D) surrounding a cross-section of the control object. The bounding region can be used to define a virtual surface (FIG. 17A: 1706) to which model subcomponents 1702, 1703, and 1754 can be compared. The virtual surface 1706 can include a visible portion 1760A and a non-visible "inferred" portion 1760BB. Virtual surfaces 1706 can include straight portions and/or curved surface portions of one or more virtual solids (i.e., model portions) determined by model refiner 1606.
[0121] For example and according to one embodiment illustrated by FIG. 17B, model refiner 1606 determines to model subcomponent 1754 of an object portion (happens to be a finger) using a virtual solid, an ellipse in this illustration, or any of a variety of 3D shapes (e.g., ellipsoid, sphere, or custom shape) and/or 2D slice(s) that are added together to form a 3D volume. Accordingly, beginning with generalized equations for an ellipse (1) with (x, y) being the coordinates of a point on the ellipse, (x.sub.C, y.sub.C) the center, a and b the axes, and .theta. the rotation angle, the coefficients C.sub.1, C.sub.2 and C.sub.3 are defined in terms of these parameters, as shown:
C 1 x 2 + C 2 xy + C 3 y 2 - ( 2 C 1 x c + C 2 y c ) x - ( 2 C 3 y c + C 2 x c ) y + ( C 1 x c 2 + C 2 x c y c + C 3 y c 2 - 1 ) = 0 C 1 = cos 2 .theta. a 2 + sin 2 .theta. b 2 C 2 = - 2 cos .theta. sin .theta. ( 1 a 2 - 1 b 2 ) C 3 = sin 2 .theta. a 2 + cos 2 .theta. b 2 ( 1 ) ##EQU00001##
[0122] The ellipse equation (1) is solved for .theta., subject to the constraints that: (1) (x.sub.C, y.sub.C) must lie on the centerline determined from the four tangents 1752A, 1752B, 1752C, 1752D (i.e., centerline 1756 of FIG. 17B); and (2) a is fixed at the assumed value a.sub.0. The ellipse equation can either be solved for .theta. analytically or solved using an iterative numerical solver (e.g., a Newtonian solver as is known in the art). An analytic solution can be obtained by writing an equation for the distances to the four tangent lines given a y.sub.C position, then solving for the value of y.sub.C that corresponds to the desired radius parameter a=a.sub.0. Accordingly, equations (2) for four tangent lines in the x-y plane (of the slice), in which coefficients A.sub.i, B.sub.i and D.sub.i (for i=1 to 4) are determined from the tangent lines 1752A, 1752B, 1752C, 1752D identified in an image slice as described above.
A.sub.1x+B.sub.1y+D.sub.1=0
A.sub.2x+B.sub.2y+D.sub.2=0
A.sub.3x+B.sub.3y+D.sub.3=0
A.sub.4x+B.sub.4y+D.sub.4=0 (2)
[0123] Four column vectors r.sub.12, r.sub.23, r.sub.14 and r.sub.24 are obtained from the coefficients A.sub.i, B.sub.i and D.sub.i of equations (2) according to equations (3), in which the "\" operator denotes matrix left division, which is defined for a square matrix M and a column vector v such that M\v=r, where r is the column vector that satisfies Mr=v:
r 13 = [ A 1 B 1 A 3 B 3 ] \ [ - D 1 D 3 ] r 23 = [ A 2 B 2 A 3 B 2 ] \ [ - D 21 - D 3 ] r 14 = [ A 1 B 1 A 4 B 4 ] \ [ - D 1 - D 4 ] r 24 = [ A 2 B 2 A 4 B 4 ] \ [ - D 2 - D 4 ] ( 3 ) ##EQU00002##
[0124] Four component vectors G and H are defined in equations (4) from the vectors of tangent coefficients A, B, and D and scalar quantities p and q, which are defined using the column vectors r.sub.12, r.sub.23, r.sub.14 and r.sub.24 from equations (3).
c1=(r.sub.13+r.sub.24)/2
c2=(r.sub.14+r.sub.23)/2
.delta.1=c2.sub.1-c1.sub.1
.delta.2=c2.sub.2-c1.sub.2
p=.delta.1/.delta.2
q=c1.sub.1-c1.sub.2*p
G=Ap+B (4)
H=Aq+D
[0125] Six scalar quantities v.sub.A2, v.sub.AB, v.sub.B2, w.sub.A2, w.sub.AB, and w.sub.B2 are defined by equation (5) in terms of the components of vectors G and H of equation (4).
v = [ G 2 2 G 3 2 G 4 2 ( G 2 H 2 ) 2 ( G 3 H 3 ) 2 ( G 4 H 4 ) 2 H 2 2 H 3 2 H 4 2 ] \ [ 0 0 1 ] w = [ G 2 2 G 3 2 G 4 2 ( G 2 H 2 ) 2 ( G 3 H 3 ) 2 ( G 4 H 4 ) 2 H 2 2 H 3 2 H 4 2 ] \ [ 0 1 0 ] v A 2 = ( v 1 A 1 ) 2 + ( v 2 A 2 ) 2 + ( v 3 A 3 ) 2 v AB = ( v 1 A 1 B 1 ) 2 + ( v 2 A 2 B 2 ) 2 + ( v 3 A 3 B 3 ) 2 v B 2 = ( v 1 B 1 ) 2 + ( v 2 B 2 ) 2 + ( v 3 B 3 ) 2 w A 2 = ( w 1 A 1 ) 2 + ( w 2 A 2 ) 2 + ( w 3 A 3 ) 2 w AB = ( w 1 A 1 B 1 ) 2 + ( w 2 A 2 B 2 ) 2 + ( w 3 A 3 B 3 ) 2 w B 2 = ( w 1 B 1 ) 2 + ( w 2 B 2 ) 2 + ( w 3 B 3 ) 2 ( 5 ) ##EQU00003##
[0126] Using the parameters defined in equations (1)-(5), solving for .theta. is accomplished by solving the eighth-degree polynomial equation (6) for t, where the coefficients Q.sub.i (for i=0 to 8) are defined as shown in equations (7)-(15).
0=Q.sub.8t.sup.8+Q.sub.7t.sup.7+Q.sub.6t.sup.6+Q.sub.5t.sup.5+Q.sub.4t.s- up.4+Q.sub.3t.sup.3+Q.sub.2t.sup.2+Q.sub.1t+Q.sub.0 (6)
[0127] The parameters A.sub.1, B.sub.1, G.sub.1, H.sub.1, v.sub.A2, v.sub.AB, v.sub.B2, w.sub.A2, w.sub.AB, and w.sub.B2 used in equations (7)-(15) are defined as shown in equations (1)-(4). The parameter n is the assumed semi-major axis (in other words, a.sub.0). Once the real roots t are known, the possible values of .theta. are defined as .theta.=a tan(t).
Q 8 = 4 A 1 2 n 2 v B 2 2 + 4 v B 2 B 1 2 ( 1 - n 2 v A 2 ) - ( G 1 ( 1 - n 2 v A 2 ) w B 2 + n 2 v B 2 w A 2 + 2 H 1 v B 2 ) 2 ( 7 ) Q 7 = - ( 2 ( 2 n 2 v AB w A 2 + 4 H 1 v AB + 2 G 1 n 2 v AB w B 2 + 2 G 1 ( 1 - n 2 v A 2 ) w AB ) ) ( G 1 ( 1 - n 2 v A 2 ) w B 2 + n 2 v B 2 w A 2 + 2 H 1 v B 2 ) - 8 A 1 B 1 n 2 v B 2 2 + 16 A 1 2 n 2 v AB v B 2 + ( 4 ( 2 A 1 B 1 ( 1 - n 2 v A 2 ) + 2 B 1 2 n 2 v AB ) ) v B 2 + 8 B 1 2 ( 1 - n 2 v A 2 ) v AB ( 8 ) Q 6 = - ( 2 ( 2 H 1 v B 2 + 2 H 1 v A 2 + n 2 v A 2 w A 2 + n 2 v B 2 ( - 2 w AB + w B 2 ) + G 1 ( n 2 v B 2 + 1 ) w B 2 + 4 G 1 n 2 v AB w AB + G 1 ( 1 - n 2 v A 2 ) v A 2 ) ) x ( G 1 ( 1 - n 2 v A 2 ) w B 2 + n 2 v B 2 w A 2 + 2 H 1 v B 2 ) - ( 2 n 2 v AB w A 2 + 4 H 1 v AB + 2 G 1 n 2 v AB w B 2 + 2 G 1 ( 1 - n 2 v A 2 ) w AB ) 2 + 4 B 1 2 n 2 v B 2 2 - 32 A 1 B 1 n 2 v AB + v B 2 + 4 A 1 2 n 2 ( 2 v A 2 v B 2 + 4 v AB 2 ) + 4 A 1 2 n 2 v B 2 2 + ( 4 ( A 1 2 ( 1 - n 2 v A 2 ) + 4 A 1 B 1 n 2 v AB + B 1 2 ( - n 2 v B 2 + 1 ) + B 1 2 ( 1 - n 2 v A 2 ) ) ) v B 2 + ( 8 ( 2 A 1 B 1 ( 1 - n 2 v A 2 ) + 2 B 1 2 n 2 v AB ) ) v AB + 4 B 1 2 ( 1 - n 2 v A 2 ) v A 2 ( 9 ) Q 5 = - ( 2 ( 4 H 1 v AB + 2 G 1 ( - n 2 v B 2 + 1 ) w AB + 2 G 1 n 2 v AB v A 2 + 2 n 2 v A ( - 2 w AB + w B 2 ) ) ) ( G 1 ( 1 - n 2 v A 2 ) w B 2 + n 2 v B 2 w A 2 + 2 H 1 v B 2 ) - ( 2 ( 2 H 1 v B 2 + 2 H 1 v A 2 + n 2 v A 2 w A 2 + n 2 v B 2 ( - 2 w AB + w B 2 ) + G 1 ( - n 2 v B 2 + 1 ) w B 2 + 4 G 1 n 2 v AB w AB + G 1 ( 1 - n 2 v A 2 ) v A 2 ) ) x ( 2 n 2 v AB w A 2 + 4 H 1 v AB + 2 G 1 n 2 v AB w B 2 + 2 G 1 ( 1 - n 2 v A 2 ) w AB ) + 16 B 1 2 n 2 v AB v B 2 - 8 A 1 B 1 n 2 ( 2 v A 2 v B 2 + 4 v AB 2 ) + 16 A 1 2 v A 2 v AB - 8 A 1 B 1 n 2 v B 2 2 + 16 A 1 2 n 2 v AB v B 2 + ( 4 ( 2 A 1 2 n 2 v AB + 2 A 1 B 1 ( - n 2 v B 2 + 1 ) + 2 A 1 B 1 ( 1 - n 2 v A 2 ) + 2 B 1 2 n 2 v AB ) ) v B 2 + ( 8 ( A 1 2 ( 1 - n 2 v A 2 ) + 4 A 1 B 1 n 2 v AB + B 1 2 ( - n 2 v B 2 + 1 ) + B 1 2 ( 1 - n 2 v A 2 ) ) ) v AB + ( 4 ( 2 A 1 B 1 ( 1 - n 2 v A 2 ) + 2 B 1 2 n 2 v AB ) ) v A 2 ( 10 ) Q 4 = ( 4 ( A 1 2 ( - n 2 v B 2 ) + A 1 2 ( 1 - n 2 v A 2 ) + 4 A 1 B 1 n 2 v AB + B 1 2 ( - n 2 v B 2 + 1 ) ) ) v B 2 + ( 8 ( 2 A 1 2 n 2 v AB + 2 A 1 B 1 ( - n 2 v B 2 + 1 ) + 2 A 1 B 1 ( 1 - n 2 v A 2 ) + 2 B 1 2 n 2 v AB ) ) v AB + ( 4 ( A 1 2 ( 1 - n 2 v A 2 ) + 4 A 1 B 1 n 2 v AB + B 1 2 ( - n 2 v B 2 + 1 ) + B 1 2 ( 1 - n 2 v A 2 ) ) ) v A 2 + 4 B 1 2 n 2 ( 2 v A 2 v B 2 + 4 v AB 2 ) - 32 A 1 B 1 n 2 v A 2 v AB + 4 A 1 2 n 2 v A 2 2 + 4 B 1 2 n 2 v AB v B 2 + 4 A 1 2 n 2 ( 2 v A 2 v B 2 + 4 v AB 2 ) - ( 2 ( G 1 ( - n 2 v B + 1 ) v A 2 + n 2 v A 2 ( - 2 w AB + w B 2 ) + 2 H 1 v A 2 ) ) ( G 1 ( 1 - n 2 v A 2 ) w B 2 + n 2 v B 2 w A 2 + 2 H 1 v B 2 ) - ( 2 ( 4 H 1 v AB + 2 G 1 ( - n 2 v B 2 + 1 ) w AB + 2 G 1 n 2 v AB v A 2 + 2 n 2 v AB ( - 2 w AB + w B 2 ) ) ) x ( 2 n 2 v AB w A 2 + 4 H 1 v AB + 2 G 1 n 2 v AB w B 2 + 2 G 1 ( 1 - n 2 v A 2 ) w AB ) - ( 2 H 1 v B 2 + 2 H 1 v A 2 + n 2 v A 2 w A 2 + n 2 v B 2 ( - 2 w AB + w B 2 ) + G 1 ( - n 2 v B 2 + 1 ) w B 2 + 4 G 1 n 2 v AB w AB + G 1 ( 1 - n 2 v A 2 ) v A 2 ) 2 ( 11 ) Q 3 = - ( 2 ( G 1 ( - n 2 v B 2 + 1 ) v A 2 + n 2 v A 2 ( - 2 w AB + w B 2 ) + 2 H 1 v A 2 ) ) ( 2 n 2 v AB w A 2 + 4 H 1 v AB + 2 G 1 n 2 v AB w B 2 + 2 G 1 ( 1 - n 2 v A 2 ) w AB ) - ( 2 ( 4 H 1 v AB + 2 G 1 ( - n 2 v B 2 + 1 ) w AB + 2 G 1 n 2 v AB v A 2 + 2 n 2 v AB ( - 2 w AB + w B 2 ) ) ) x ( 2 H 1 v B 2 + 2 H 1 v A 2 + n 2 v A 2 w A 2 + n 2 v B 2 ( - 2 w AB + w B 2 ) + G 1 ( - n 2 v B 2 + 1 ) w B 2 + 4 G 1 n 2 v AB w AB + G 1 ( 1 - n 2 v A 2 ) v A 2 ) + 16 B 1 2 n 2 v A 2 v AB - 8 A 1 B 1 n 2 v A 2 2 + 16 B 1 2 n 2 v AB v B 2 - 8 A 1 B 1 n 2 ( 2 v A 2 v B 2 + 4 v AB 2 ) + 16 A 1 2 n 2 v A 2 v AB + ( 4 ( 2 A 1 2 n 2 v AB + 2 A 1 B 1 ( - n 2 v B 2 + 1 ) ) ) v B 2 + ( 8 ( A 1 2 ( - n 2 v B 2 + 1 ) + A 1 2 ( 1 - n 2 v A 2 ) + 4 A 1 B 1 n 2 v AB + B 1 2 ( - n 2 v B 2 + 1 ) ) ) v AB + ( 4 ( 2 A 1 2 n 2 v AB + 2 A 1 B 1 ( - n 2 v B 2 + 1 ) + 2 A 1 B 1 ( 1 - n 2 v A 2 ) + 2 B 1 2 n 2 v AB ) ) v A 2 ( 12 ) Q 2 = 4 A 1 2 ( - n 2 v B 2 + 1 ) v B 2 + ( 8 ( 2 A 1 2 n 2 v AB + 2 A 1 B 1 ( - n 2 v B 2 + 1 ) ) ) v AB + ( 4 ( A 1 2 ( - n 2 v B 2 + 1 ) + A 1 2 ( 1 - n 2 v A 2 ) + 4 A 1 B 1 n 2 v AB + B 1 2 ( - n 2 v B 2 + 1 ) ) ) v A 2 + 4 B 1 2 n 2 v A 2 2 + 4 B 1 2 n 2 ( 2 v A 2 v B 2 + 4 v AB 2 ) - 32 A 1 B 1 n 2 v A 2 v AB + 4 A 1 2 n 2 v A 2 2 - ( 2 ( G 1 ( - n 2 v B 2 + 1 ) v A 2 + n 2 v A 2 ( - 2 w AB + w B 2 ) + 2 H 1 v A 2 ) ) x ( 2 H 1 v B 2 + 2 H 1 v A 2 + n 2 v A 2 w A 2 + n 2 v B 2 ( - 2 w AB + w B 2 ) + G 1 ( - n 2 v B 2 + 1 ) w B 2 + 4 G 1 n 2 v AB w AB + G 1 ( 1 - n 2 v A 2 ) v A 2 ) - ( 4 H 1 v AB + 2 G 1 ( - n 2 v B 2 + 1 ) w AB + 2 G 1 n 2 v AB v A 2 + 2 n 2 v AB ( - 2 w AB + w B 2 ) ) 2 ( 13 ) Q 1 = 8 A 1 2 ( - n 2 v B 2 + 1 ) v AB + ( 4 ( 2 A 1 2 n 2 v AB + 2 A 1 B 1 ( - n 2 v B 2 + 1 ) ) ) v A 2 + 16 B 1 2 n 2 v A 2 v AB - 8 A 1 B 1 n 2 v A 2 2 - ( 2 ( G 1 ( - n 2 v B 2 + 1 ) v A 2 + n 2 v A 2 ( - 2 w AB + w B 2 ) + 2 H 1 v A 2 ) ) ( 4 H 1 v AB + 2 G 1 ( - n 2 v B 2 + 1 ) w AB + 2 G 1 n 2 v AB v A 2 + 2 n 2 v AB ( - 2 w AB + w B 2 ) ) ( 14 ) Q 0 = 4 A 1 2 ( - n 2 v B 2 + 1 ) v A 2 - ( G 1 ( - n 2 v B 2 + 1 ) v A 2 + n 2 v A 2 ( - 2 w AB + w B 2 ) + 2 H 1 v A 2 ) 2 + 4 B 1 2 n 2 v A 2 2 ( 15 ) ##EQU00004##
[0128] In this exemplary embodiment, equations (6)-(15) have at most three real roots; thus, for any four tangent lines, there are at most three possible ellipses that are tangent to all four lines and that satisfy the a=a.sub.0 constraint. (In some instances, there may be fewer than three real roots.) For each real root .theta., the corresponding values of (x.sub.C, y.sub.C) and b can be readily determined. Depending on the particular inputs, zero or more solutions will be obtained; for example, in some instances, three solutions can be obtained for a typical configuration of tangents. Each solution is completely characterized by the parameters {.theta., a=a.sub.0, b, (x.sub.C, y.sub.C)}. Alternatively, or additionally, referring to FIG. 16, a model builder 1614 and model updater 1616 provide functionality to define, build, and/or customize model(s) 1608 using one or more components in object library 1612. Once built, model refiner 1606 updates and refines the model, bringing the predictive information of the model in line with observed information from the detection system 102.
[0129] The model subcomponents 1702, 1703, 1754 can be scaled, sized, selected, rotated, translated, moved, or otherwise re-ordered to enable portions of the model corresponding to the virtual surface(s) to conform within the points 1750 in space. Model refiner 1606 employs a variation detector 1608 to substantially continuously determine differences between sensed information and predictive information and provide to model refiner 1606 a variance useful to adjust the model 1608 accordingly. Variation detector 1608 and model refiner 1606 are further enabled to correlate among model portions to preserve continuity with characteristic information of a corresponding object being modeled, continuity in motion, and/or continuity in deformation, conformation and/or torsional rotations.
[0130] In an embodiment, when the control object morphs, conforms, and/or translates, motion information reflecting such motion(s) is included in the observed information. Points in space can be recomputed based on the new observation information. The model subcomponents can be scaled, sized, selected, rotated, translated, moved, or otherwise re-ordered to enable portions of the model corresponding to the virtual surface(s) to conform to the set of points in space.
[0131] In an embodiment, motion(s) of the control object can be rigid transformations, in which case points on the virtual surface(s) remain at the same distance(s) from one another through the motion. Motion(s) can be non-rigid transformations, in which points on the virtual surface(s) can vary in distance(s) from one another during the motion. In an embodiment, observation information can be used to adjust (and/or recompute) predictive information, thereby enabling "tracking" the control object. In embodiments, the control object can be tracked by determining whether a rigid transformation or a non-rigid transformation occurs. In an embodiment, when a rigid transformation occurs, a transformation matrix is applied to each point of the model uniformly. Otherwise, when a non-rigid transformation occurs, an error indication can be determined, and an error-minimization technique such as described herein above can be applied. In an embodiment, rigid transformations and/or non-rigid transformations can be composed. One example composition embodiment includes applying a rigid transformation to predictive information. Then an error indication can be determined, and an error minimization technique such as described herein above can be applied. In an embodiment, determining a transformation can include calculating a rotation matrix that provides a reduced RMSD (root mean squared deviation) between two paired sets of points. One embodiment can include using Kabsch Algorithm to produce a rotation matrix. In an embodiment and by way of example, one or more force lines can be determined from one or more portions of a virtual surface.
Collisions
[0132] In an embodiment, predictive information can include collision information concerning two or more capsuloids. By means of illustration, several possible fits of predicted information to observed information can be removed from consideration based upon a determination that these potential solutions would result in collisions of cap suloids. In an embodiment, a relationship between neighboring capsuloids, each having one or more attributes (e.g., determined minima and/or maxima of intersection angles between capsuloids) can be determined. In an embodiment, determining a relationship between a first capsuloid having a first set of attributes and a second capsuloid having a second set of attributes includes detecting and resolving conflicts between first attributes and second attributes. For example, a conflict can include a capsuloid having one type of angle value with a neighbor having a second type of angle value incompatible with the first type of angle value. Attempts to attach a capsuloid with a neighboring capsuloid having attributes such that the combination will exceed what is allowed in the observed--or to pair incompatible angles, lengths, shapes, or other such attributes--can be removed from the predicted information without further consideration.
Lean Model
[0133] In an embodiment, predictive information can be artificially constrained to capsuloids positioned in a subset of the observed information--thereby enabling creation of a "lean model." For example, as illustrated in 17A, capsuloid 1702 could be used to denote the portion of the observed without addition of capsuloids 1703. In a yet further embodiment, connections can be made using artificial constructs to link together capsuloids of a lean model. In another embodiment, the predictive information can be constrained to a subset of topological information about the observed information representing the control object to form a lean model. In an embodiment, a lean model can be associated with a full predictive model. The lean model (or topological information, or properties described above) can be extracted from the predictive model to form a constraint. Then, the constraint can be imposed on the predictive information, thereby enabling the predictive information to be constrained in one or more of behavior, shape, total (system) energy, structure, orientation, compression, shear, torsion, other properties, and/or combinations thereof.
Occlusions
[0134] In an embodiment, the observed can include components reflecting portions of the control object which are occluded from view of the device ("occlusions" or "occluded components"). In one embodiment, the predictive information can be "fit" to the observed as described herein above with the additional constraint(s) that some total property of the predictive information (e.g., potential energy) be minimized or maximized (or driven to lower or higher value(s) through iteration or solution). Properties can be derived from nature, properties of the control object being viewed, others, and/or combinations thereof. In another embodiment, as shown by 17C and 17D, a deformation of the predictive information subcomponent 1760 can be allowed subject to an overall permitted value of compression, deformation, flexibility, others, and/or combinations thereof.
Friction
[0135] In an embodiment, a "friction constraint" is applied on the model 1700. For example, if fingers of a hand being modeled are close together (in position or orientation), corresponding portions of the model will have more "friction". The more friction a model subcomponent has in the model, the less the subcomponent moves in response to new observed information. Accordingly, the model is enabled to mimic the way portions of the hand that are physically close together move together, and move less overall.
[0136] With renewed reference to FIG. 16A, an environmental filter 1620 reduces extraneous noise in sensed information received from the detection system 100 using environmental information to eliminate extraneous elements from the sensory information. Environmental filter 1620 employs contrast enhancement, subtraction of a difference image from an image, software filtering, and background subtraction (using background information provided by objects-of-interest determiner 1622 (see below) to enable model refiner 1606 to build, refine, manage, and maintain model(s) 1608 of objects of interest from which control inputs can be determined.
[0137] A model analyzer 1610 determines that a reconstructed shape of a sensed object portion matches an object model in an object library, and interprets the reconstructed shape (and/or variations thereon) as user input. Model analyzer 1610 provides output in the form of object, position, motion, and attribute information to an interaction system 1630.
[0138] The interaction system 1630 includes an interaction-interpretation module 1632 that provides functionality to recognize command and other information from object, position, motion and attribute information obtained from variation system 1600. An interaction-interpretation module 1632 embodiment comprises a recognition engine 1634 to recognize command information such as command inputs (i.e., gestures and/or other command inputs (e.g., speech, and so forth)), related information (i.e., biometrics), environmental information (i.e., context, noise, and so forth) and other information discernable from the object, position, motion, and attribute information that might be useful in controlling a machine. Recognition engine 1634 employs gesture properties 1636 (e.g., path, velocity, acceleration, and so forth), control objects determined from the object, position, motion, and attribute information by an objects-of-interest determiner 1622 and optionally one or more virtual constructs 1638 (see e.g., FIGS. 18A and 18B: 1800 and 1820) to recognize variations in control-object presence or motion indicating command information, related information, environmental information, and other information discernable from the object, position, motion, and attribute information that might be useful in controlling a machine. With reference to 18A and 18B, virtual construct 1800, 1820 implement an engagement target with which a control object 112 interacts--enabling the machine sensory and control system to discern variations in control object (i.e., motions into, out of or relative to virtual construct 1800, 1820) as indicating control or other useful information. Returning to FIG. 16, a gesture trainer 1640 and gesture-properties extractor 1642 provide functionality to define, build, and/or customize gesture properties 1636.
[0139] A context determiner 1634 and object-of-interest determiner 1622 provide functionality to determine from the object, position, motion, and attribute information objects of interest (e.g., control objects, or other objects to be modeled and analyzed) and/or objects not of interest (e.g., background), based upon a detected context. For example, when the context is determined to be an identification context, a human face will be determined to be an object of interest to the system and will be determined to be a control object. On the other hand, when the context is determined to be a fingertip control context, the finger tips will be determined to be object(s) of interest and will be determined to be control objects whereas the user's face will be determined not to be an object of interest (i.e., background). Further, when the context is determined to be a stylus (or other tool) held in the fingers of the user, the tool tip will be determined to be object of interest and a control object whereas the user's fingertips might be determined not to be objects of interest (i.e., background). Background objects can be included in the environmental information provided to environmental filter 1620 of model-management module 1602.
[0140] A virtual environment manager 1646 provides creation, selection, modification, and de-selection of one or more virtual constructs 1800, 1820 (see FIGS. 18A and 18B). In some embodiments, virtual constructs (e.g., a virtual object defined in space such that variations in real objects relative to the virtual construct, when detected, can be interpreted for control or other purposes) are used to determine variations (i.e., virtual "contact" with the virtual construct, breaking of virtual contact, motion relative to a construct portion, and so forth) to be interpreted as engagements, dis-engagements, motions relative to the construct(s), and so forth, enabling the system to interpret pinches, pokes and grabs, and so forth. Interaction-interpretation module 1632 provides as output the command information, related information, and other information discernable from the object, position, motion, and attribute information that might be useful in controlling a machine from recognition engine 1634 to an application control system 1650.
[0141] Further with reference to FIG. 16, an application control system 1650 includes a control module 1652 that provides functionality to determine and authorize commands based upon the command and other information obtained from interaction system 1630.
[0142] A control module 1652 embodiment comprises a command engine 1654 to determine whether to issue command(s) and what command(s) to issue based upon the command information, related information, and other information discernable from the object, position, motion, and attribute information, as received from the interaction-interpretation module 1632. Command engine 1654 employs command/control repository 1656 (e.g., application commands, OS commands, commands to the machine sensory and control system, miscellaneous commands) and related information indicating context received from the interaction-interpretation module 1632 to determine one or more commands corresponding to the gestures, context, and so forth indicated by the command information. For example, engagement gestures can be mapped to one or more controls, or a control-less screen location, of a presentation device associated with a machine under control. Controls can include imbedded controls (e.g., sliders, buttons, and other control objects in an application), or environmental level controls (e.g., windowing controls, scrolls within a window, and other controls affecting the control environment). In embodiments, controls may be displayed using 2D presentations (e.g., a cursor, cross-hairs, icon, graphical representation of the control object, or other displayable object) on display screens and/or presented in 3D forms using holography, projectors, or other mechanisms for creating 3D presentations, or may be audible (e.g., mapped to sounds, or other mechanisms for conveying audible information) and/or touchable via haptic techniques.
[0143] Further, an authorization engine 1658 employs biometric profiles 1660 (e.g., users, identification information, privileges, and so forth) and biometric information received from the interaction-interpretation module 1632 to determine whether commands and/or controls determined by the command engine 1654 are authorized. A command builder 1662 and biometric profile builder 1660 provide functionality to define, build, and/or customize command/control repository 1652 and biometric profiles 1660.
[0144] Selected authorized commands are provided to machine(s) under control (i.e., "client") via interface layer 1664. Commands/controls to the virtual environment (i.e., interaction control) are provided to virtual environment manager 1646. Commands/controls to the emission/detection systems (i.e., sensory control) are provided to emission module 102 and/or detection module 104 as appropriate.
[0145] For example, if the control object is a hand, analysis of the hand's shape and configuration (which may be the object attributes of interest) may determine the positions of the finger tips, which may constitute the relevant control surfaces. Furthermore, changes in control attributes of the identified control surface(s), such as positional changes of the fingertips, may be analyzed to determine whether they are indicative of control information. In hand-gesture-based machine control, for instance, this may serve to discriminate between deliberate motions intended to provide control input and hand jitter or other inevitable motions. Such discrimination may be based, e.g., on the scale and speed of motion, similarity of the motions to pre-defined motion patterns stored in a library, and/or consistency with deliberate motions as characterized using machine learning algorithms or other approaches.
[0146] Further, in some embodiments, as illustrated with reference to FIGS. 18A and 18B, a hand gesture or other motion is analyzed relative to a programmatically defined engagement target (e.g., a plane, curved surface (whether open or closed), point, line, or volume whose position and location in space is well-defined and which need generally not coincide with a physical surface) to determine whether the change in the control surface is indicative of an engagement gesture. For example, if the fingertip pierces an engagement surface, this may be interpreted as a click event, or if one or more fingertips or the entire hand moves substantially parallel to an engagement surface defined relative to a display screen, this may be interpreted as a scrolling gesture. If a particular detected motion (or, more generally, change in object attributes) corresponds to control information, an appropriate response action is taken, generally in accordance with and/or based on response criteria, such as the context in which the control information was received (e.g., the particular software application active at the time, the user accessing the system, an active security level, etc.). The response may involve issuing a command (e.g., open a new document upon a "click," or shift the displayed content in response to a scrolling motion) to a user interface based on the detected gesture or motion. As illustrated in, FIGS. 18A and 18B, a machine sensory and controller system 1810 can be embodied as a standalone unit(s) 1810 coupleable via an interface (e.g., wired or wireless), embedded (e.g., within a machine 1812, 1814 or machinery under control), or combinations thereof.
[0147] To provide yet another concrete example of machine control in accordance herewith, in one embodiment, the system is used for security purposes and directs light emission at an entryway to a secure room or space. If, during the scan across the entryway, a reflection is detected, this may indicate the presence of a person seeking entrance. A second scan may then be conducted, according to a more refined scan pattern, to obtain more detailed information about the person. For example, a vein pattern of the person's hand may be identified. Vein patterns of authorized users may be stored in a database, allowing the system to check whether the detected person is authorized to enter the secure space. In other words, the control information in this case is authentication information. If a match of the detected vein pattern with a stored pattern is found, the system may respond by permitting the person to enter (e.g., by automatically opening a mechanical barrier, temporarily interrupting laser beams crossing the entryway, or by some other means). Certain embodiments of depth-sensing positioning and tracking systems in accordance herewith may also be mounted on automobiles or other mobile platforms to provide information as to the outside environment (e.g., the positions of other automobiles) to other systems within the platform. In general, embodiments of the disclosed technology may be employed in a variety of application areas, including, without limitation, consumer applications including interfaces for computer systems, laptops, tablets, television, game consoles, set top boxes, telephone devices and/or interfaces to other devices; medical applications including controlling devices for performing robotic surgery, medical imaging systems and applications such as CT, ultrasound, x-ray, MRI or the like, laboratory test and diagnostics systems and/or nuclear medicine devices and systems; prosthetics applications including interfaces to devices providing assistance to persons under handicap, disability, recovering from surgery, and/or other infirmity; defense applications including interfaces to aircraft operational controls, navigations systems control, on-board entertainment systems control and/or environmental systems control; automotive applications including interfaces to automobile operational systems control, navigation systems control, on-board entertainment systems control and/or environmental systems control; security applications including, monitoring secure areas for suspicious activity or unauthorized personnel; manufacturing and/or process applications including interfaces to assembly robots, automated test apparatus, work conveyance devices such as conveyors, and/or other factory floor systems and devices, genetic sequencing machines, semiconductor fabrication related machinery, chemical process machinery and/or the like; and/or combinations thereof.
[0148] Certain embodiments of the disclosed technology are described above. It is, however, expressly noted that the disclosed technology is not limited to those embodiments. Rather, variations, additions, modifications, and other implementations of what is described herein, as will occur to those of ordinary skill in the art, are deemed within the spirit and scope of the disclosed technology. For example, it may be appreciated that the techniques, devices, and systems described herein with reference to embodiments employing light waves may be equally applicable to methods and systems employing other types of radiant energy waves, such as acoustical energy or the like. Moreover, it is to be understood that the features of the various embodiments described herein are not mutually exclusive and can exist in various combinations and permutations, even if such combinations or permutations are not made express herein, without departing from the spirit and scope of the disclosed technology. Accordingly, the scope of the disclosed technology is not intended to be limited by the preceding illustrative description.
