Methods and apparatus for position estimation using reflected light sources

[0001] This application claims the benefit under 35 U.S.C. §119(e) of U.S. Provisional Application No. 60/557,252, filed Mar. 29, 2004, the entirety of which is hereby incorporated by reference.

[0002] Appendix A, which forms a part of this disclosure, is a list of commonly owned co-pending U.S. patent applications. Each one of the co-pending applications listed in Appendix A is hereby incorporated herein in its entirety by reference thereto.

[0003] 1. Field of the Invention

[0004] This invention generally relates to the estimation of position and orientation of an object with respect to a local or a global coordinate system. In particular, the invention relates to the method and apparatus that provides estimation and tracking of the position and orientation. The method and apparatus that can be used in vehicles, such as in mobile robots.

[0005] 2. Description of the Related Art

[0006] Position estimation is a topic of interest for a wide variety of application areas ranging from autonomous mobile robots, ubiquitous computing, mobile devices, tracking of assets, tracking of people, position tracking of customers in a store, tracking of pets, position of nodes in ad hoc wireless networks, position tracking of vehicles, and position tracking of mobile devices such as cell phones, personal digital assistants, and the like.

[0007] Robots are becoming more and more commonplace in society. It will be understood that these robots can be embodied in a variety of forms, such as in automated floor care products such as vacuum cleaners. A variety of applications can be found for mobile robots, such as, but not limited to, entertainment applications such as toy robots, healthcare applications such as elderly care robots, patrolling and security applications, telepresence robots, cleaning applications such as floor cleaning robots, utility applications in environments that are unfriendly to humans such as space, deep water, cold temperature, radiation, chemical exposure, biohazards, etc., dangerous tasks such as defusing of potential explosives, operation in confined spaces such as collapsed buildings, and the performance of menial tasks such as cleaning. Mobile robots, robots that can move from one location to another, often use knowledge of their position relative to their environment.

[0008] Localization techniques refer to processes by which a robot determines its position and orientation relative to a reference coordinate system. The reference coordinate system can be either local (for example, relative to an object of interest) or global. Position estimation can include estimation of any quantity that is related to at least some of an object's six degrees of freedom of in three dimensions (3-D). These six degrees of freedom can be described as the object's (x, y, z) position and its angles of rotation around each axis of a 3-D coordinate system, which angles are denoted α, β, and θ and respectively termed “pitch,” “roll,” and “yaw.” Such position estimation can be useful for various tasks and application.

[0009] For example, the bearing of a robot relative to a charging station can be useful for allowing the robot to servo to the charging station and recharge its batteries autonomously. The estimation of the distance of a pet from the front door can be used to alert the owner about a possible problem. For indoor environments, it is typically desired to track the (x, y) position of an object in a two-dimensional (2-D) floor plane and its orientation, θ, relative to an axis normal to the floor plane. That is, it can be convenient to assume that a z coordinate of the robot, as well as the robot's roll and pitch angles, are constant. The (x, y) position and the θ orientation of an object are referred to together as the pose of the object.

[0010] Numerous devices, processes, sensors, equipment, and mechanisms have been proposed for position estimation. These methods can be divided into two main categories. One category uses beacons in the environment to enable position estimation, and the second category uses natural landmarks in the environment. Because the method and apparatus described herein fall into the first category of beacon-based position estimation or localization, this section will focus on beacon-based localization methods.

[0011] Beacons are artificial devices in the environment that can be detected by an appropriate sensing apparatus. Beacons can be passive or active. Examples of passive beacons include retroreflective materials. By projecting a light source onto a retroreflective material, one can create a signature or signal that can be detected readily using one or more appropriate optical sensors. Using the signature or signal, the one or more sensors can determine their positions relative to the beacons and/or relative to the environment.

[0012] Active optical beacons emit light that can be detected by an optical sensor. The optical sensor can measure various characteristics of the emitted light, such as the distance to the emitter (using time-of-flight), the bearing to the emitter, the signal strength, and the like. Using such characteristics, one can estimate the position of the sensor using an appropriate technique, such as triangulation or trilateration. These approaches, which use active optical beacons paired with optical sensors, are disadvantageously constrained by line-of-sight between the emitters and the sensors. Without line-of-sight, a sensor will not be able to detect the emitter.

[0013] Embodiments described herein are related to methods and apparatus for the estimation of the position and orientation of a device, such as a robot, relative to a global or local reference frame. The apparatus described herein comprises an optical sensor, an optical emitter, and associated signal processing circuitry. The poses of the sensors are typically unknown, and the apparatus and methods described herein can be used to measure or estimate the pose of at least one sensor and the position of an emitter projection on a surface.

[0014] A typical application of the method and apparatus includes estimation and tracking of the position of a mobile autonomous robot. Other applications include estimation and tracking of an object for position-aware, ubiquitous devices. Additional applications include tracking of the positions of people or pets in an indoor environment. The methods and apparatus comprise one or more optical emitters, one or more optical sensors, signal processing circuitry, and signal processing methods to determine the position and orientation of at least one of the optical sensors based at least in part on the detection of the signal of one or more emitted light sources reflected from a surface.

[0019] Pose: A pose is a position and orientation in space. In three dimensions, pose can refer to a position (x, y, z) and an orientation (α, β, θ) with respect to the axes of the three-dimensional space. In two dimensions, pose can refer to a position (x, y) in a plane and an orientation θ relative to the normal to the plane.

[0020] Optical sensor: An optical sensor is a sensor that uses light to detect a condition and describe the condition quantitatively. In general, an optical sensor refers to a sensor that can measure one or more physical characteristics of a light source. Such physical characteristics can include the number of photons, the position of the light on the sensor, the color of the light, and the like.

[0021] Position-sensitive detector: A position-sensitive detector, also known as a position sensing detector or a PSD, is an optical sensor that can measure the centroid of an incident light source, typically in one or two dimensions. For example, a PSD can convert an incident light spot into relatively continuous position data.

[0022] Imager: An imager refers to an optical sensor that can measure light on an active area of the sensor and can measure optical signals along at least one axis or dimension. For example, a photo array can be defined as a one-dimensional imager, and a duo-lateral PSD can be defined as a two-dimensional imager.

[0023] Camera: A camera typically refers to a device including one or more imagers, one or more lenses, and associated support circuitry. Optionally, a camera can also include one or more optical filters and a housing or casing.

[0024] PSD camera: A PSD camera is a camera that uses a PSD.

[0025] Projector: A projector refers to an apparatus that projects light. A projector includes an emitter, a power source, and associated support circuitry. A projector can project one or more light spots on a surface.

[0026] Spot: A spot refers to a projection of light on a surface. A spot can correspond to an entire projection, or can correspond to only part of an entire projection.

[0027] Optical position sensor: An optical position sensor is a device that includes one or more cameras, a signal processing unit, a power supply, and support circuitry and can estimate its position, distance, angle, or pose relative to one or more spots.

[0028] Although these methods and apparatus will be described in terms of certain preferred embodiments, other embodiments that are apparent to those of ordinary skill in the art, including embodiments that do not provide all of the benefits and features set forth herein, are also within the scope of the invention

[0029] Embodiments advantageously use active optical beacons in position estimation. Advantageously, disclosed techniques minimize or reduce the line-of-sight limitation of conventional active optical beacon-based localization by projecting the light sources onto a surface that is observable from a relatively large portion of the environment. It will be understood that the light sources can include sources of light that are not visible to the naked eye, such as, for example, infrared (IR) sources. For example, in an indoor environment, it can be advantageous to project the emitted light from the beacon onto the ceiling. In many indoor environments, the ceiling of a room is observable from most locations with the room.

[0030] As an illustration, one can consider an application of the method and apparatus for an autonomous mobile robot such as a robotic vacuum cleaner. A common approach to self-docking and self-charging is to place active infrared (IR) beacons on the charging station, which the robot can sense with photo detectors, and use the associated sensory information to find the docking station. This approach suffers from line-of-sight limitations. If the robot and the docking station do not have line-of-sight separation, the robot cannot find its position relative to the docking station.

[0031] In one embodiment, the IR emitter can advantageously be placed in such a way that it projects onto the ceiling above the docking station, and a robot can have a photo detector that generally faces the ceiling or is capable of observing the ceiling. The robot can advantageously observe the IR projection on the ceiling even in the absence of line-of-sight separation between the robot and the docking station. In relatively many situations, the robot has a line-of-sight view of the ceiling, which enables the robot to detect the IR projection and move to the docking station for self-charging.

[0032] The method and apparatus described herein include numerous variations that differ in the type and number of active beacons used, differ in the type and number of optical sensors used for detection of reflected light, and differ in the type of signal processing used to determine the pose of an object. Embodiments of the method and apparatus include systems for estimation of the distance of an object relative to another object, estimation of the bearing of an object relative to another object, estimation of the (x, y) position of an object in a two-dimensional plane, estimation of the (x, y, z) position of an object in three-dimensional space, estimation of the position and orientation of an object in two dimensions or in three dimensions, estimation of the linear or angular velocity of an object, and estimation of the linear or angular acceleration of an object.

[0033] Embodiments of the method and apparatus are related to estimation of the position and orientation of a device, such as a mobile robot, relative to a global or a local coordinate system. The apparatus includes one or more optical sensors, one or more optical emitters, and signal processing circuitry. The initial position and orientations of the sensors can be unknown, and the apparatus and methods can be used to measure or estimate the position and orientation of one or more of the sensors and the position of the emitter projections on a surface.

[0034] In one embodiment, an optical sensor measures the optical signals generated by the optical emitters that are within the sensor's field of view by measuring the light that is projected onto a surface. By contrast, in a conventional system, such optical devices for distance or position measurement disadvantageously require line-of-sight between the emitter and the sensor. Advantageously, embodiments described herein can detect optical signals projected onto a surface, such as a ceiling of an indoor environment. The optical emitters can be configured to project one or more spots of light onto a surface that is observable by a sensor from a relatively large portion of the environment. The sensor detects the spot and estimates the sensor's position relative to the spot. The sensor can measure quantities such as the position of the spot in the sensor's reference frame and the intensity of the signal generated by the spot, and can associate a unique identifier with each spot. Each such measurement or set of measurements defines a relationship between the position of the sensor and the position of the spot. Using multiple such relationships defined between one or more sensors and one or more spots, signal processing circuitry can estimate the pose of at least one of the sensors, and, optionally, the position of one or more spots.

[0035] Embodiments of the method and apparatus described herein can vary in the number and type of optical sensors used, can vary in the number and type of optical emitters used, can vary in the projection of the light onto the sensor via, optionally, one or more spots, and can vary in the methods used for estimation of the distance, heading, position, orientation, velocity, angular velocity, acceleration, and angular acceleration of the sensor or sensors. For example, a light spot can be generated by an IR sensor that emits IR light onto a surface, and a photo detector can be used to detect the light reflected from the surface. With one emitter and one sensor, the distance and relative heading to the projected light can be measured. With two emitters and one two-dimensional sensor, the position of the sensor in a plane and the rotation of the sensor around an axis normal to that plane can be measured.

[0036] Embodiments of the method and apparatus described herein can use a wide variety of optical sensors. Some embodiments use digital or analog imaging or video cameras, such as CMOS imagers, CCD imagers, and the like. Other embodiments use PSDs, such as one-dimensional PSDs, angular one-dimensional PSDs, two-dimensional PSDs, quad PSDs, duo-lateral PSDs, tetra-lateral PSDs, and the like. Other embodiments use photo detectors.

[0037] In one embodiment, the optical sensor is combined with a lens and one or more optical filters to form a camera. For example, a PSD sensor can be enclosed in a casing with an open side that fits the lens and optical filters to filter incoming light and reduce effects of ambient light.

[0038] Embodiments of the method and apparatus described herein can also use a wide variety of optical emitters, including visible light devices, invisible light devices, laser light devices, infrared light devices, polarized light devices, light-emitting diodes (LEDs), laser diodes, light bulbs, halogen lights, projectors, and the like.

[0039] One embodiment of the method and apparatus described herein uses one two-dimensional PSD camera and a plurality of infrared (IR) emitters. Each IR emitter projects a spot onto the ceiling in a room. Each emitter is modulated with a unique pattern or frequency. The PSD camera is mounted, on a robot, for example, and faces the ceiling in such a way that its field of view intersects at least a portion of the plane that defines the ceiling onto which the spots are projected. The PSD camera provides an indication of the projected position of each observable spot in the camera sensor coordinates. In the illustrated embodiment, the position of each observed spot is defined as its centroid.

[0040] A camera position of each observed spot can correspond to the projection of a spot's position onto the image plane of the camera as defined by a corresponding perspective transformation. The PSD camera can measure the camera position of each spot. Using the measured camera positions of the spot and information related to the distance between the spots, the position (x, y) of the PSD camera in one plane and the rotation (θ) of the PSD camera around an axis normal to that plane can be determined. The position and orientation of the camera defined by (x, y, θ) is known as the pose of the camera.

[0041] For example, the PSD camera can be coupled to a mobile device such as a robot, and the device's pose can advantageously be relatively accurately determined within a room with two or more spots. Pose estimation, also known as localization, is an important component in many applications, including automated vacuuming, automated floor cleaning, telepresence, security, and entertainment. Without accurate position estimates, it is relatively difficult or impossible for a conventional robot to execute a path or trajectory because the conventional robot's internal position estimate tends to drift, and the conventional robot is generally unable to measure or account for the drift. For systematic floor coverage in a robotic vacuum cleaner, for example, a conventional robot without the ability to localize generally cannot maintain knowledge of the areas it has cleaned and the areas it has not cleaned, and the robot is therefore relatively likely to clean the same areas repeatedly and inefficiently and is relatively unlikely to clean other areas with sufficient frequency. Accordingly, many conventional robotic vacuum cleaners execute a random trajectory. By contrast, a robotic vacuum cleaner according to an embodiment with the ability to localize in a relatively accurate manner can follow a relatively efficient planned path. A robotic vacuum cleaner according to an embodiment can clean a room in a relatively efficient manner because it can track its path and can execute a planned, traversable path. Similarly, a mobile robot with the ability to localize can navigate to a desirable location and maintain a history of paths that it has taken.

[0042] Another embodiment of the method and apparatus described herein uses one two-dimensional PSD camera and one IR emitter. The IR emitter projects a spot on the ceiling, and the PSD camera faces the ceiling such that its field of view intersects at least a portion of the plane that defines the ceiling onto which the spot is projected. The PSD camera can provide indications for a measurement of the distance from the camera to the spot and the heading from the camera to the spot relative to the tangent of the circle with radius defined by the distance measurement. The distance measurement defines a circle centered at the spot projected onto the plane of the camera. In one example, the illustrated embodiment can be used for an application in which it is desired to position a device relative to the spot. Advantageously, when the camera is underneath the spot on the ceiling, then the camera position is at the center of the PSD camera. For example, if the spot is projected over a charging station, a mobile device can approach the charging station and recharge autonomously. In a related embodiment that further comprises wheel encoders, a robotic vacuum cleaner can move along concentric circles or move along a spiral to implement a floor coverage strategy that is relatively efficient, compared to a random coverage strategy.

[0043] While various embodiments have been and will be further described in the context of autonomous mobile robots, it will be understood by those of ordinary skill in the art that the principles and advantages set forth herein are applicable to other applications that benefit from position estimation, which are also within the scope of the invention.

[0044] Examples of embodiments will now be described. FIG. 1 illustrates a block diagram of components of one embodiment of an apparatus. The apparatus includes a projector 111 and an optical position sensor 112. The projector 111 emits a light pattern 113 onto a surface 116, which creates a projected light pattern 119. In one embodiment, the light pattern 113 is modulated. The reflection 114 of the projected light pattern 119 is projected onto the optical position sensor 112.

[0045] The projector 111 includes a light source 102. By way of example, the light source 102 can correspond to a device, such as a laser device, an infrared device, and the like, that can be modulated by a modulator 101. Optionally, the light from the light source 102 can pass through one or more lenses 103 to project the light onto the surface 116.

[0046] The optical position sensor 112 includes a camera 117 and a processing unit 118. The camera 117 can detect and measure the intensity and position of the light 114 reflected from the surface 116 and can generate corresponding signals that are processed by the signal processing unit 118 to estimate the position of the optical position sensor 112 relative to the projected light pattern 119. It will be understood that the optical position sensor 112 can include multiple cameras 117 and/or multiple processing units 118.

[0047] The camera 117 includes an imager 104. The imager 104 can, for example, correspond to a CMOS imager, a CCD imager, an infrared imager, and the like. The camera can optionally include an optical filter 105 and can optionally include a lens 106. The lens 106 can correspond to a normal lens or can correspond to a special lens, such as a wide-angle lens, a fish-eye lens, an omni-directional lens, and the like. Further, the lens 106 can include reflective surfaces, such as planar, parabolic, or conical mirrors, which can be used to provide a relatively large field of view or multiple viewpoints. The lens 106 collects the reflected light 114 and projects it onto the imager 104. The optical filter 105 can constrain the wavelengths of light that pass from the lens 106 to the imager 104, which can advantageously be used to reduce the effect of ambient light, to narrow the range of light to match the wavelength of the light coming from the projector 111, and/or to limit the amount of light projected onto the imager 104, which can limit the effects of over-exposure or saturation. The filter 105 can be placed in front of the lens 106 or behind the lens 106. It will be understood that the camera 117 can include multiple imagers 104, multiple optical filters 105, and/or multiple lenses 106.

[0048] The signal processing unit 118 can include analog components and can include digital components for processing the signals generated by the camera 117. The major components of the signal processing unit 118 preferably include an amplifier 107, a filter 108, an analog-to-digital converter 109, and a microprocessor 110, such as a peripheral interface controller, also known as a PIC. It will be understood that the signal processing unit 118 can include multiple filters 108 and/or multiple microprocessors 110.

[0049] Embodiments of the apparatus are not constrained to the specific implementations of the projector 111 or the optical position sensor 112 described herein. Other implementations, embodiments, and modifications of the apparatus that do not depart from the true spirit and scope of the apparatus will be readily apparent to one of ordinary skill in the art.

[0050] FIG. 2 illustrates an example of a use for the position estimation techniques. An environment includes a ceiling 206, a floor 207, and one or more walls 208. In the illustrated environment, a projector 203 is attached to a wall 208. It will be understood that the projector 203 can have an internal power source, can plug into a wall outlet or both. The projector 203 projects a first spot 204 and a second spot 205 onto the ceiling 206. An optical position sensor 202 is attached to a robot 201. The optical position sensor 202 can detect the spots 204, 205 on the ceiling 206 and measure the position (x, y) of the robot 201 on the floor plane and the orientation θ of the robot 201 with respect to the normal to the floor plane. In one embodiment, the pose of the robot 201 is measured relative to a global coordinate system.

[0051] FIG. 3 describes a geometrical model associated with one embodiment of the method and apparatus described earlier in connection with FIG. 2. The ceiling 206 lies at a height h above the floor 207. A point w₁ 301 lies at the centroid of the first spot 204, and a point w₂ 302 lies at the centroid of the second spot 205. In the illustrated embodiment, a global coordinate system with an X axis, a Y axis, and a Z axis is defined and is also referred to as the global reference frame.

[0052] In one embodiment, it is convenient to define the Y axis such that the Y axis is parallel to the vector originating at the point w₁ 301 and passing through the point w₂ 302. Additionally, it is convenient to define the X axis such that the X axis is perpendicular to the Y axis and lies in the plane defined by the floor. Further, it is convenient to define the Z axis such that the positive Z direction is specified by the cross product of the unit vector in the X direction with the unit vector in the Y direction; in standard vector calculus notation, this relationship is expressed as {circumflex over (Z)}={circumflex over (X)}×Ŷ. Thus, in the illustrated coordinate system, the Z axis is normal to the floor plane and is directed from the floor to the ceiling. In the global coordinate system, an origin O is defined as the point having coordinates (0, 0, 0). Also in the global coordinate system, the point w₁ 301 is defined as having coordinates (x₁, y₁, h), and the point w₂ 302 is defined as having coordinates (x₂, y₂, h). Further, it is convenient to assume that the origin O is located directly below the point w₁ 301, so that x_i=0 and y₁=0. Additionally, the definition of the X axis implies that x₂=0 as well. Thus, the point w₁ 301 has the coordinates (0, 0, h), and the point w₂ 302 has the coordinates (0, y₂, h). It will be understood that the aforementioned definitions can be made with no loss of generality.

[0053] A coordinate system relative to an imager is defined with a u axis, a v axis, and a z axis and can be referred to as the camera coordinate system or the camera reference frame. In the illustrated embodiment, the imager corresponds to a two-dimensional PSD sensor. In one embodiment, the height of the PSD sensor off the floor plane is relatively small compared to the ceiling height h, so the PSD sensor and the origin of the camera coordinate system use the coordinates (x, y, 0) and the orientation θ in the global coordinate system. The displacement from the origin of the global coordinate system to the origin of the camera coordinate system is denoted S; thus, ∥S∥=√{square root over (x²+y²)}, where ∥S∥ denotes the norm, or magnitude, of the vector S. The point C₁ 311 represents the projection of the point w₁ 301 onto the imager, and the point c₂ 312 represents the projection of the point w₂ 302 onto the imager. The point c₁ 311 has the coordinates (u₁, v₁, 0) in the camera reference frame, and the point c₂ 312 has the coordinates (u₂, v₂, 0) in the camera reference frame. It will be understood that the aforementioned definitions can be made with no loss of generality.

[0054] In one embodiment, the spots 204, 205 can be identified using unique signals or unique signatures. For example, the emitters that produce the spots 204, 205 can be on-off modulated with different frequencies. The emitter that produces the first spot 204 can be modulated with a first frequency f₁, and the emitter that produces the second spot 205 can be modulated with a second frequency f₂, wherein the first frequency and the second frequency are different; that is f₁≠f₂.

[0055] At this point, it should be noted that the ceiling height h and the separation y₂ between the point w₁ 301 and the point w₂ 302 can be determined in a variety of ways. For example, if the mobile robot 201 using the optical position sensor is capable of producing wheel odometry estimates, then the robot 201 can estimate h and y₂ using measurements or observations of the points w₁ 301 and w₂ 302 from multiple positions. Other appropriate techniques will be readily determined by one of ordinary skill in the art.

Exemplary Position Estimation Using the Method and Apparatus

[0056] With reference to the coordinate systems, distances, angles, and points described earlier in connection with FIG. 3, the PSD camera can measure c₁ and c₂, which correspond to the projections of w₁ and w₂ onto the PSD sensor. In one embodiment, a goal of the method is to determine S, the position of the PSD camera in the global reference frame.

[0057] In one embodiment, the PSD measures the coordinates of the centroid of the light projected onto the PSD by generating electrical current proportional to the position and intensity of the light centroid. The associated processing can be accomplished in a wide variety of ways, including analog circuitry, digital circuits, hardware, software, firmware, and combinations thereof. For example, a microcontroller, a microprocessor, a CPU, a general-purpose digital signal processor, dedicated hardware, and the like can be used.

[0058] To measure the centroids of multiple spots, a number of conditions are preferable. First, the sensor preferably does not become saturated with light, ambient or otherwise. In one embodiment, this is accomplished by using optical filters to reduce or minimize unwanted light sources that project onto the active area of the PSD sensor and by biasing the PSD to increase the light level at which it becomes saturated. Second, to measure the position of a particular light source reliably, it is preferable to isolate the light source from other light sources by reducing or eliminating the effect of other light sources, which can include ambient light and light generated by other spots. One approach is to isolate one light source is to modulate the light source with a unique pattern such that it is distinguished from other light sources. If the i-th emitter on-off modulates the projected light with a frequency f_i, the PSD sensor can extract the signal generated by filtering a signal using a band-pass filter with lower and upper frequencies of f_i−w and f_i+w, respectively, where 2w corresponds to the width of the corresponding band-pass filter. The signal processing unit of the PSD can use the filter to suppress signals with frequencies outside the frequency range defined by the band-pass filter. The filtering of the PSD signal can occur either before or after the PSD currents are converted into associated centroid positions. In one embodiment, where the first emitter is modulated at a frequency f₁ and the second emitter is modulated at a frequency f₂, and wherein f₁≠f₂, the signal processing unit filters the signal specified by f₁ to measure c₁, the centroid of the first spot, and filters the signal specified by f₂ to measure c₂, the centroid of the second spot.

Exemplary Method for Pose Estimation

[0059] In one embodiment, the apparatus includes N emitters, which project N light spots, and M cameras. The position of the i-th camera in the global reference frame is denoted herein by S_i=(x_i, y_i, z_i), and the rotational orientation of the i-th camera in the global reference frame is denoted herein by R_i=(α_i, β_i, θ_i). The position of the j-th light spot is denoted herein by w_j, and the position of the projection of the j-th spot onto the i-th camera is denoted herein by c_ij. Then, the following relationship relates S_i, w_j, and c_ij.
c_i,j=P_iR_i(w_j−S_i)  Equation 1

[0060] In Equation 1, R_i represents the three-degree-of-freedom rotation transformation, which, in one embodiment, results from the composition of three mutually orthogonal one-degree-of-freedom rotation transformations, such as R_i=R_αR_βR_θ. Also in Equation 1, P_i represents the perspective transformation associated with the i-th camera. Thus, Equation 1 defines three equations for six unknowns, in which the unknowns are x_i, y_i, z_i, α_i, β_i, and θ_i. In a system with N spots and M cameras, N×M such matrix equations can be formulated, but not all such equations are necessarily unique, independent, and non-degenerate. Thus, with two spots and one camera, values for x, y, and θ can be determined. To determine all six degrees of freedom, it is preferable to have a configuration of spots and cameras that generates at least six independent, non-degenerate equations analogous to Equation 1.

Exemplary System with Two Emitters and One Camera

[0061] In one embodiment, the system includes two spots projected onto the ceiling and one optical position sensor with one PSD camera. The relationship between a spot w₁ and its projection c_j in the PSD camera reference frame is given by the following equation.
c_j=PR_θ(w_i−S)  Equation 2

[0062] In Equation 2, S represents the position of the PSD camera in the global reference frame, and P represents the transformation from a point (X, Y, Z) in the global coordinate system to a point (u, v, z) in the PSD camera reference frame. Also, for the purposes of this example, the z axis of the camera coordinate system is aligned with the Z axis of the global coordinate system in the vertical direction. This implies that R_β and R_β correspond to identity matrices; accordingly, R_α and R_β have been omitted from Equation 2. In the case of a pinhole camera model, P corresponds to the scalar value λ/(λ−Z), where λ represents the focal length of the camera. It will be understood that multiplication by a scalar value can also be achieved by multiplication by the corresponding multiple of the appropriately-dimensioned identity matrix. Also in Equation 2, R_θ can be represented by the following unitary matrix.

[0063] $\begin{array}{cc}{R}_{\theta }=\left(\begin{array}{ccc}\cos \theta & \sin \theta & 0\\ -\sin \theta & \cos \theta & 0\\ 0& 0& 1\end{array}\right)& \mathrm{Equation}3\end{array}$

[0064] Equation 2 can be re-written as follows.
w_j−S=R_θ⁻¹P⁻¹c_j  Equation 4

[0065] In Equation 4, P⁻¹ represents the inverse perspective transformation, and R_θ⁻¹ represents the inverse rotation transformation. When the position of the i-th spot is associated with appropriate camera parameters, such as the camera focal length in a pinhole camera model, then Equation 4 defines two non-degenerate equations in three unknowns x, y, and θ for each measurement c_j. Thus, the three variables, x, y, and θ, together determine the pose of the PSD camera.

[0066] Because two equations in three unknowns do not define a unique solution for the pose of the PSD camera, it is preferable to use more independent equations than unknowns. With two spots and one PSD camera, it is possible to generate four equations in three unknowns as follows.
w₁−S=R_θ⁻¹P⁻¹c_i  Equation 5
w₂−S=R_θ⁻¹P⁻¹c₂  Equation 6

[0067] Equation 5 relates the spot w₁ with its associated PSD camera position c₁, and Equation 6 relates the spot w₂ with its associated PSD camera position c₂. Subtracting Equation 5 from Equation 6 generates the following matrix equation expressed in Equation 7.
w₂−w₁=R_θ⁻¹P⁻¹(c₂−c₁)  Equation 7

[0068] Equation 7 can be expanded as follows.

[0069] $\begin{array}{cc}\left(\begin{array}{c}0\\ \Delta y\\ 0\end{array}\right)=R_{\theta }^{-1}{P}^{-1}\left(\begin{array}{c}\Delta u\\ \Delta v\\ 0\end{array}\right)& \mathrm{Equation}8\end{array}$

[0070] The matrix equation given in Equation 8 expresses two non-degenerate linear equations. In Equation 8, Δy=d=y₂−y₁, Δu=u₂−u₁, and Δv=v₂−v₁. As discussed earlier in connection with FIG. 3, d represents the distance that separates the two spots. Accordingly, the first of the two non-degenerate linear equation defined by Equation 8 is given by the following.
0=P⁻¹(Δu cos−Δv sin θ)  Equation 9

[0071] Solving for θ in Equation 9 gives θ=tan⁻¹(Δu/Δv), and substituting this result into Equation 5 provides the following solution for S, the position of the PSD camera in the global reference frame.
S=w₁−R_θ⁻¹P⁻¹c₁|_{θ=tan−1(Δu/Δv)}  Equation 10

[0072] Accordingly, the pose (x, y, θ) of the PSD camera as a function of the measurements c₁ and c₂ can be determined using Equation 9 and Equation 10.

An Example of Using One Emitter and One Camera

[0073] In one embodiment, the system includes one spot projected onto the ceiling and one optical position sensor with one PSD camera. Similar to the relationship discussed earlier in connection with Equation 2, the relationship between the spot w and its projection c in the PSD camera reference frame is given by the following equation.
c=PR_θ(w−S)  Equation 11

[0074] Because the origin of the global coordinate system can be chosen, without loss of generality, such that the spot w is located directly above the origin, rearranging Equation 11 provides the following solution for S.
w−S=R_θ⁻¹P⁻¹c  Equation 12

[0075] Equation 12 can be rewritten in coordinate notation to give the following relationship.

[0076] $\begin{array}{cc}\left(\begin{array}{c}-x\\ -y\\ z\end{array}\right)=\left(\begin{array}{ccc}\cos \theta & -\sin \theta & 0\\ \sin \theta & \cos \theta & 0\\ 0& 0& 1\end{array}\right)P^{-1}\left(\begin{array}{c}u\\ v\\ 0\end{array}\right)& \mathrm{Equation}13\end{array}$

[0077] Thus, Equation 13 specifies two non-degenerate linear equations. In the case that P⁻¹ corresponds to a scalar or to a scalar multiple of an identity matrix, squaring and summing the two non-degenerate linear equations and simplifying the result yields the following.
x²+y²=(P⁻¹)²[(u cos θ−v sin θ)²+(u sin θ+v cos θ)²]=(P⁻¹)²(u²+v²)  Equation 14

[0078] Because x²+y² is equal to ∥S∥² and u²+v² is equal ∥c∥², Equation 14 can be simplified to ∥S∥²=(P⁻¹)²∥c∥², or ∥S∥=P⁻¹∥c∥.

[0079] Thus, the distance measurement ∥c∥, and the corresponding distance measurement ∥S∥, can define a circle in an x-y plane centered at the origin (0, 0) with radius ∥S∥. A tangent to the circle at the position of the sensor at the position of the sensor (that is, at S), is orthogonal to the vector s=(x y)^T, where the superscripted “T” denotes the vector or matrix transposition operation. The tangent ŝ can therefore be expressed as ŝ=(y−x)^T. The rotational orientation, φ, of the robot of the robot with respect to ŝ can then be estimated using a measurement of c as given in the following relationship.
φ=tan⁻¹(u/v)  Equation 15

[0080] Thus, in this embodiment, ∥S∥ and φ can be determined, which can advantageously support applications for robotics, person tracking, object tracking, and the like. In one example, the spot is projected onto the ceiling directly above a docking station, and the optical position sensor with one PSD camera is attached to a robot. Using the estimation of ∥S∥ and φ, the robot can guide itself to turn toward the spot and approach the spot. In this manner, the robot can approach the docking station and recharge itself. In an alternative example, the projector can correspond to a handheld projector and can be used to point above a user-selected object or location of interest to guide to the robot to the object or location. This alternative example provides a powerful interface for robot interaction.

[0081] One embodiment of the method and apparatus includes a camera, such as a CCD camera, a CMOS camera, and the like, and a projector that generates a pattern on a projection surface, such as a ceiling. It will be understood that this embodiment can include multiple cameras and/or multiple projectors. By way of example, the projector can correspond to a slide projector, and the pattern can be encoded in a slide. In one embodiment, at least one pattern has the shape of a circle, and in another embodiment, at least one pattern has the shape of a square. Each camera generates grayscale or color images. A signal processing unit processes the camera images, extracts the unique patterns, and estimates a position of the pattern in camera sensor coordinates. The position of the pattern can be defined as the centroid of the pattern. The position of the j-th pattern in the global reference frame can be denoted herein by w_j, and the position of the j-th pattern in the reference frame of the i-th camera can be denoted herein by c_ij. Then, the relationship between the j-th pattern and its projection onto the i-th camera is defined by Equation 1. The signal processing unit captures the camera images and processes the images using one or more image analysis techniques to detect and extract the position of known patterns. The image analysis techniques can include, by way of example, line and corner detection (to detect a square pattern, for example), Hough transform (to detect a circle, for example), and the like. After the positions of the patterns in the camera reference frames are determined, the signal processing unit can estimate the positions of the cameras with respect to the global reference frame using the methods described previously. Optionally, one or more of the projectors can modulate on-off to reduce the effects of ambient light. The modulation frequencies can advantageously be used to associate a unique identifier with each pattern. In one embodiment, the identifier of a pattern is advantageously encoded within the pattern itself. As an example, the shape of the pattern can define a unique identifier, if distinct shapes are used for each pattern. For example, the system can distinguish between a square pattern and a circular pattern and associate different identifiers with each pattern.

[0082] In one embodiment, the modulation frequency of the projector can encode information, such as bit patterns to transmit a message that can be detected and extracted by the camera and the signal processing unit. The bit patterns can be modulated in the signal using any of a variety of common modulation techniques, such as pulse width modulation, space width modulation, and phase modulation.

[0083] In another embodiment, the bit patterns are modulated on top of the original “carrier” frequency of the spot. The projectors and optical position sensors can advantageously be used for optical wireless communication. In this embodiment, the projector projects the light pattern on a reflecting surface, and the optical sensor detects the signal by viewing the reflecting surface, which eliminates the need for line-of-sight between the emitter and the sensor. The signal modulated in the projected light can carry commands, such as commands for a robot, similar to the way in which light modulated by a remote control unit can carry commands to an appliance. In one example, the projection of the spot on the ceiling directly above a docking station enables the robot to find the docking station and perform self-charging. In addition, an interface with the docking station, such as a button on the docking station, can generate a command to the robot to return to the charging station.

[0084] Yet another embodiment of the method and apparatus includes a projector for one or more distinct regions of an environment, such as a projector for each distinct region. Advantageously, this embodiment expands the coverage of localization throughout relatively large areas or throughout multiple relatively confined areas, such as multiple rooms. The covered area associated with one projector can be constrained by the field of view of the camera, the distance from the projector to the reflection surface, and the presence of objects and walls that obstruct the camera's view of the spot. Increasing the number of light patterns can increase the coverage area. In one embodiment, for coverage across multiple rooms, one or more projectors are provided for each room in which coverage is desired, so that, for example, each room can have a dedicated projector. For example, each projector can project one or more spots that have an identifier that is unique within the room. It will be understood that the identifier associated with a spot can be based on the spot's modulation frequency, the spot's shape, the spot's color, or another appropriate characteristic that can be detected by the camera sensor.

[0085] In one implementation, the combination of the individual spot identifiers with a room can define a unique identifier for the room. By way of example, a first room can have two spots having associated unique identifiers “A” and “B,” and a second room can have two spots having associated unique identifiers “A” and “C.” The unique identifiers for each room can advantageously be used by a system, such as by a robot, to build a topological map of the rooms and the connectivity of the rooms. Without a unique identifier for each room or region, the system can disadvantageously generate ambiguous position information. As an illustration, without a unique identifier for each room, the position associated with an (x, y) coordinate of a first room can generally not be distinguished from the position associated with the (x, y) coordinate of a second room.

[0086] Although this invention has been described with reference to these specific embodiments, the descriptions are intended to be illustrative of the invention and are not intended to be limiting. Various modifications and applications may occur to those skilled in the art without departing from the true spirit and scope of the invention.

[0087]

APPENDIX A
Incorporation by Reference of Commonly Owned Applications
The following patent applications, commonly owned and filed on
the same day as the present application, are hereby incorporated
herein in their entirety by reference thereto:
	Application No.	Attorney Docket
Title	and Filing Date	No.
“Methods And Apparatus For	Provisional	EVOL.0050PR
Position Estimation Using	Application
Reflected Light Sources”	60/557,252
	Filed Mar. 29, 2004
“Circuit for Estimating	Provisional	EVOL.0050-1PR
Position and Orientation	Application
of a Mobile Object”	60/602,238
	Filed Aug. 16, 2004
“Sensing device and method for	Provisional	EVOL.0050-2PR
measuring position and	Application
orientation relative to multiple	60/601,913
light sources”	Filed Aug. 16, 2004
“System and Method of	Provisional	EVOL.0050-3PR
Integrating Optics into an IC	Application
Package”	60/602,239
	Filed Aug. 16, 2004
“Circuit for Estimating Position	Utility	EVOL.0050A1
and Orientation of a Mobile	Application
Object”	Ser. No. TBD
	Filed Mar. 25, 2005
“Sensing device and method for	Utility	EVOL-0050A2
measuring position and	Application
orientation relative to multiple	Ser. No. TBD
light sources”	Filed Mar. 25, 2005
“System and Method of	Utility	EVOL.0050A3
Integrating Optics into an IC	Application
Package”	Ser. No. TBD
	Filed Mar. 25, 2005