Apparatus and method for determining the position of an object in 3-dimensional space

[0001] This application claims priority to a U.S. provisional application Ser. No. 60/942,316 entitled ULTRASONIC 3D WIRELESS COMPUTER MOUSE, filed on Jun. 6, 2007, which is incorporated by reference in its entirety herein

[0002] This invention relates generally to interfacing a user mouse interface to a computer and without limitation thereto determining the position of the computer mouse interface in 3-dimensions and providing the 3-dimensional position in real time to the computer.

[0003] Computer interfaces are one of the three major divisions within computer theory and design: input, processing and output. The goal of a computer interface is to balance the relationship between instinctive interaction and device functionality.

[0004] A computer mouse as a user interface to a computer was developed in the 1960s at the Stanford Research Institute as a token that could be moved about a surface and that was able to translate movement data to the computer. Although significant development has occurred, the mouse is still used primarily as a 2-dimensional interface. The standard mouse is ill suited for 3D software and even the development of a scroll wheel to traverse a third-dimension does not allow for simultaneous movement in three dimensions nor does it provide high resolution along the z-axis.

[0005] Accordingly, it would be advantageous to provide a new computer mouse interface that allowed for movement in three dimensions and also provides for high resolution along the z-axis.

[0006] An apparatus and method is disclosed for determining the position of a user interface mouse using time of arrival measurements. As an exemplary embodiment but not limited thereto, a transmitter transmits a signal to an array of receivers that are spatially separated from one another. The time of arrival at each receiver is determined and the difference in time of arrival for each receiver relative to a predetermined reference receiver is then determined. Using the time difference of arrival (TDOA) of each receiver, the location in 3-dimensional space of each receiver, the speed of sound, and the position of the transmitter in 3-dimensional space relative to the reference receiver may be found.

[0007] Other features, aspects, and advantages of the above-described method and system will be apparent from the detailed description of the invention that follows.

[0020] The following detailed description sets forth numerous specific details to provide a thorough understanding of the invention. However, those skilled in the art will appreciate that the invention may be practiced without these specific details. In other instances, well-known methods, procedures, components, protocols, algorithms, and circuits have not been described in detail so as not to obscure the invention.

[0021] The apparatus and method described herein are for transmitting a signal, which may be from a user interface, to a plurality of receivers each of which receives and conditions the signal and the provides the plurality of signals to a digital signal processor (DSP) that processes the signals received by the plurality of receivers to determine the time of arrival (TOA) of the signal at each receiver. The time difference of arrival for each receiver relative to a reference receiver is determined and the position in 3-dimensional space of the transmitter is determined in real time and this position data is provided to a computer or other electronic device.

[0022] FIG. 1 depicts a block diagram of the apparatus described herein that is used to provide a 3-dimensional user interface to a computer. In particular, the system 100 includes a transmitter 102 and a receiver 104, a computer interface 106, and a computer 108. The transmitter 102 is designed to provide a wireless signal 103 to the receiver 104 that can be processed and analyzed to determine the spatial position of the transmitter in 3-dimension space relative to a predetermined origin. The receiver 104 includes a transducer array that includes a plurality of transducers, 110a-110d spatially separated from one another in 3-dimensions and each having a specific 3-dimensional set of coordinates relative to a predetermined origin, wherein one of the plurality of transducers 110a-d is determined to be a reference transducer, which may be collocated with the predetermined origin. The receiver 104 also includes, a plurality of signal receivers 112a-112d, one for each transducer in the transducer array. As will be explained in more detail below, the signal receiver that corresponds to the reference transducer is selected as a reference receiver.

[0023] The receiver 104 further includes a digital signal processor (DSP) 114 that converts signals into a digital format and provides for the calculations for the time of arrival (TOA) of the wireless signal 103 at each of the plurality of transducers 110a-110b, for the time difference of arrival (TDOA), which is the difference in arrival time of the signal 103 for each of the plurality of transducers 110a-110d relative to the reference transducer, and for the determination of the set of 3-dimensional coordinates of position of the transmitter relative to the predetermined origin location. The DSP 114 receives the plurality of output signals 109 from the plurality of signal receivers 112a-112d and uses the plurality of received signals 109 to determine the 3-dimensional position 111 of the transmitter as a function of the 3-dimensional locations of each of the transducers 110a-110d relative to the predetermined origin, and the time difference of arrival data of the signal 103 for each of the plurality of transducers 110a-110d relative to the reference transducer. The three-dimensional position 111 is then provided to the computer interface 106 and then to a computer 108. In one embodiment the system 100, may make use of the transmitter 102 as a user interface for a computer and the system in sensing the position of the transmitter 102 may provide the 3-dimensional location of the transmitter 102 to the computer 108. In this embodiment the transmitter 102 is equivalent to a 3-dimensional computer mouse. In another embodiment, the 3-Dimensional position data may be used to track the motion of desired objects

[0024] The transmitter may transmit any suitable signal 103, e.g., radio frequency, microwave, sonic or ultrasonic energy may be used. As will be discussed in more detail below, time difference of arrival data is calculated and analyzed to find the transmitter position in 3-dimensional space. Different types of signals, e.g., electromagnetic or sound waves may be used depending upon the scale of the system involved. For example, to achieve a given spatial accuracy, the following equation is used:

[0025] $\Delta t=\frac{2\Delta d}{c}$

[0026] Where c is the propagation speed of the signal and d is the desired resolution. For a 1 mm spatial accuracy in a single dimension an electromagnetic signal would have a Δt of 6.67 ps, while a sonic signal would have a Δt of 5.58 μs. This represents a six order of magnitude difference between using an electromagnetic such as an optical or radio signal versus an acoustic signal such as a sonic or ultrasonic signal. Due to processing requirements and the distances involved being fairly small, on the order of 1 or 2 meters, in the preferred embodiment, ultrasonic signals will be used. However, in other systems, and depending upon the system requirements, it may be advantageous to use electromagnetic signals instead.

[0027] FIG. 2 depicts an embodiment of the transmitter 102 provided for in FIG. 1. In particular, the transmitter 102 includes a signal generator 202 that provides a signal 203 having predetermined waveform, at a predetermined frequency, and using a predetermined pulse repetition rate to a transducer drive circuitry 204. The transducer drive circuitry 204 amplifies the signal 203 and provides this amplified signal 205 to the ultrasonic transducer 206 that generates ultrasonic signal 103 as shown in FIG. 1. A power supply 201, described in more detail below provides power to the transmitter components. The actual circuit design of the transducer drive circuitry would be well known in the electrical art. The actual circuit would be dependent upon the type of transducer used, the power required, the type of waveform being generated, environmental conditions, and other system requirements.

[0028] The transmitter is preferably a small lightweight and unobtrusive device. To this end, the ultrasonic transducer 206 should be small and not cumbersome. Ultrasonic transducers can transmit nearly any frequency over 20 KHz, but the ultrasonic transducer used herein is preferably a 40 KHz transducer. In addition, ultrasonic transducers may be open or closed, i.e., open transducers have the piezo-electric device and cone exposed to air, while a closed transducer has the piezo-electric device mounted on the outer case. In the apparatus described herein, an open transducer is preferred; however, an enclosed transducer may also be used in harsh environments, or if other system requirements militate for an enclosed transducer.

[0029] The transducer 206 may be omni-directional in transmitting a signal or may be directional. The disclosed apparatus preferably uses an ultrasonic transducer 206 that is directional and does not attenuate the transmitted signal significantly in the 30° to 45° range. The ultrasonic transducer may also have varying bandwidth; however, because the apparatus described herein uses an ultrasonic transducer using a center frequency of substantially 40 KHz the bandwidth is not a large concern, except in how the transducer may act as a bandpass filter on a transmitted or received signal. In addition, the ultrasonic transducer 206 may be of varying sizes; however, a smaller transducer is preferred, provided that it meets other system requirements as well. In one embodiment of the apparatus described herein, a Kobtrone transducer having a transmitter and receiver part numbers, respectively, of 255-400ST12 and 255-400SR12 were used and are available from a distributor such as Mouser Electronics, a TTI company at Mouser Electronics, Inc. 1000 North Main Street Mansfield, Tex. 76063 at (800) 346-6873.

[0030] The signal generator 202 may be either an analog or digital signal generator depending upon the system requirements For example, crystal oscillators, phase locked loops, integrated timing circuits, or digital oscillators may be used. However, in the apparatus described herein a digital signal processing system or programmable controller is preferred. This allows for a low power, flexible design that uses fewer components than the analog methods described above.

[0031] FIG. 3 depicts a block diagram of a firmware implementation suitable for use on a programmable controller or digital signal processor. The s/w initialization block 302 sets the outputs and other functions as required. The main transmit loop 304 forms the signal 203 that is provided to the transducer amplifier 204 shown in FIG. 2 and that is eventually provided to the transducer 206 to transmit signal 103. An interrupt service routine 306 is used to bring the microcontroller or digital signal processor out of a low power that may be entered between pulses. The selection of a particular programmable controller/digital signal processor is based on several parameters. The device should be low power, come in a physically small package, have a low pin count, an external crystal connection for a 40 KHz crystal, and have at least one available digital Input/Output line. In one embodiment, the programmable controller/digital signal processor may be a Texas Instrument MSP430F20xx available from Texas Instruments.

[0032] The flexibility afforded by using a programmable controller allows for data to be encoded and transmitted within the signal used to provide the Time Delay of Arrival (TDOA) measurements. Using sonic signals, such as ultrasonic, phase of the transmitted signals would be changing with the position of the transmitter so that on-off-keying (OOK) is a preferred choice for data transmission using an ultrasonic transducer. For example, clicking of right or left buttons or using a track wheel could be encoded and transmitted using OOK signals. In the event that optical or radio signals could make use of frequency-shift keying (FSK) or phase shift keying (PSK) such as QPSK or BPSK could also be used.

[0033] In another embodiment, more than one transmitter may be used at a time and the signals differentiated using encoded data that corresponds to a particular transmitter. In the event that more than one transmitter is used, transmitters could also be differentiated by differences in frequencies that are transmitted or other forms of multiplexing may be used as well.

[0034] In one embodiment of the present apparatus, the signal is comprised of a series of square wave pulses wherein each square wave pulse is 20 cycles of the 40 KHz signal and each series of pulses would have a pulse rate of 100 Hz. This translates to a pause of 380 cycles of 40 KHz signal between each pulse. Other pulse widths and pulse rates may be used depending upon the system requirements.

[0035] In the event that a Texas Instrument MSP430F20xx is used, the devices auxiliary clock (ACLK) is set to run off an external 40 KHz crystal, the capture/compare register (CCR) is used to count up to a specified value at the rate of one per ACLK cycle and then trigger an interrupt. The firmware depicted in FIG. 3 sends a signal by the following steps: (1) Set port 1.0 to output ACLK (auxiliary clock); enter low power mode (LPM3); Set CCR to count 20 ACLK cycles then interrupt to come out of low power mode; Turn off ACLK output on Port 1.0 then enter low power mode; set CCR to count 380 ACLK cycles then interrupt; repeat from (1).

[0036] FIG. 4 depicts an embodiment of a transducer array for use in the apparatus described herein for receiving the signal 103 provided by the transmitter 102 and converting the signal 103 into an electrical signal that is suitable for further processing. In particular, the receiver array includes a plurality of ultrasonic transducers 110a-d that are spatially separated from one another and attached to a frame 400. The ultrasonic transducers, discussed above, act as bandpass filters having a center frequency of 40 KHz. The actual spatial distribution of the transducer array is in 3-dimensions and is a function of the system requirements. Each transducer 110a-d is spaced apart, in all 3-dimensions, both from the designated reference transducer as well as from other transducers in the transducer array. In addition, although five transducers 110a-d are depicted in the figure, any number greater than or equal to four may be used, with a correlation between accuracy and the number of receivers used in the array.

[0037] FIG. 5 depicts a block diagram of a representative signal receiver 112a of the plurality of receivers 112a-d, shown in FIG. 1, suitable for use in receiver 104 in the apparatus described herein. Each of the signal receivers 112a-d is configured to amplify and convert the electrical signal received from a corresponding transducer 110a-d into a format that preserves the pulse peak time of the electrical signal and in which the received electrical signal is in a condition to be digitized. Thus, the signal receivers 112a-d should introduce minimal distortion and signal delay of the received electrical signals. In particular, each of the signal receivers 112a-d includes an AC amplifier 502 that receives the one of the plurality of signals 109 from a corresponding transducer of the transducer array 110a-d. The AC amplifier 502 is configured to substantially block the DC component of the signal 109 and amplifies the signal 109 with a bandpass substantially centered at 40 KHz. The amplified signal is provided to an envelope detector 504 that detects the signal envelope and rectifies the signal forming a baseband signal. The detected baseband signal is then provided to a low pass filter 506 that converts the baseband signal into a single sine wave shaped pulse. As will be explained in more detail below, the peak of the single sine wave shaped pulse corresponds to the time of arrival at the associated transducer 110a-d relative to the other receivers. In one embodiment, the low pass filter 506 is a Chebyshev filter having a cutoff frequency of between 1000 to 2000 Hz. The design of a single pole or multi-pole Chebyshev filter, whether passive or active, is well known within the art and the actual design of the low pass filter 506 is dependent upon the system requirements including system and environmental noise levels, proximity of adjacent signals, power requirements, and other design criteria.

[0038] The envelope detector 504 may be of a coherent or incoherent design. Direct-detection receivers employ a square-law device that produces an electrical signal proportional to the intensity of the incident signal (e.g., an ultrasonic transducer)—the signal's power is measured directly. Since any phase information is lost in the process, direct detection cannot be used to measure the Doppler frequency shift of the signal, and direct detection is subject to other noise sources in the receiver and to background signals incident on the ultrasonic transducer receiver. Under certain conditions of limited signal strength, direct detection therefore offers sensitivity inferior to that of coherent detection. However, direct detection has advantages over coherent detection when either source temporal coherence or the spatial phase characteristics of the received signal cannot be strictly controlled, or when complexity or cost are important design issues.

[0039] Coherent detection first multiplies the incoming signal with a model of the expected signal and then integrates the product forming a correlation output function that provides accurate timing information using the peak of the integrated (correlation) signal. Since the pulse length is the same in all receivers, the peak should correspond to the time at which the pulse was received at the corresponding receiver. Coherent phase detection using a DSP chip has advantages over analog coherent detection in that the amplitude of the received signal can be normalized such that the peak of each signal can be more accurately determined using software.

[0040] In the apparatus described herein a direct detection, i.e., incoherent, system is used in the form of a precision rectifier depicted in FIG. 6. The diodes leave only the positive portion of the sinusoidal signal and the op-amp provides a gain of R3/R4 to reduce the forward voltage drop to nearly zero.

[0041] The power supply 501 may be provided by an external power supply, a battery power supply, or in the case of a computer interface 106 that is a USB interface, the necessary power may be supplied by the computer 108 via the computer interface 106 such as the well known USB interface.

[0042] FIG. 7 depicts an embodiment of the DSP 114 of FIG. 1 that is responsible for the A-D conversion and calculations to determine the location of the transmitter in space. In particular, FIG. 7 depicts the DSP system 114 that is used to provide the main functionality of the system described herein. In one embodiment, the DSP system 114 should be able to provide an updated 3-dimensional location to the computer at least every 16 ms so that cursor movement appears smooth on a 60 Hz monitor. Obviously if the monitor was other than 60 Hz then the update time would be adjusted accordingly. In other embodiments, the updated 3-dimensional position may be updated sufficiently fast so that a user does not notice any appreciable delay by the computer. The DSP system uses the time that each of the receivers in the receiver array received the signal 103 from transmitter 102. The difference between these times, set relative to a reference receiver, typically set as the origin (0,0,0), must have a high resolution. The faster the various receivers are updated, the higher the time resolution will be with the concomitant improvement in spatial resolution as well.

[0043] The DSP 114 includes a multiplexer block 702, sampling block 704, peak detection/TDOA block 706, and position calculation block 708. As the various transducers 110a-d receive the signal 103 from transmitter 102, each of the plurality of transducer-signal receiver combinations provides a signal 109 to the DSP 114 that is an amplified and detected form of the signal 103 that was received at the particular transducer 110a-d. Thus the DSP 114 receives a signal 109 from every transducer-signal receiver combination, i.e., DSP 114 receives a plurality of signals 109 from the receiver 104. Because there is a single DSP and it can only convert one signal of the plurality of signals 109 at a time, each of the plurality of signals 109 must be individually selected and passed in a predetermined order, converted into a digital format, and used to calculate the position of the transmitter 102. Thus, the selected signal of the plurality of signals 109 is provided to the A/D converter 704 and converted into a digital representation of the selected signal of the plurality of signals 109. Thus, the multiplexer 702 is used to select an individual signal, pass the selected signal of the plurality of signals 109 to the sampling A/D converter 704. The A-D converter 704 converts the selected analog signal into a digital representation of the selected analog signal and provides the digitized version to the peak detection/TDOA block 706. As will be explained in more detail below, the peak detection/TDOA block 706 detects the time of the peak of the digitized representation of the selected signal and uses this time to form time of arrival (TOA) data for the corresponding one of the transducers 110a-d and ultimately to form the time difference of arrival (TDOA) data for the corresponding one of the transducers 110a-d relative to the reference transducer. When TDOA data for each of the transducers 110a-d has been determined, this set of TDOA data is then provided to position calculation block 708 that calculates the transmitter position and provides the set of 3-dimensional coordinates 111 to the computer interface 106.

[0044] Although the amplitude of the signal 103 received by each of the plurality of transducers 110a-d in the transducer array 110 will vary due to the physical parameters of the system itself; the signal 103 received by each of the transducers 110a-d will have a substantially similar waveform shape when compared to the signal 103 received at other transducers in the transducer array 110a-d. In general, due to the bandwidth limited nature of the transmitter and receiver ultrasonic transducers 206 (FIG. 2) and 112a-d (FIG. 1), respectively, the signal 103 when it is received by one of the transducers 110a-b will not have a sharp edge, but rather, will resemble a smooth curve. The time at which any signal 103 is received by a transducer 110a-d only varies with the time at which the peak of the particular signal is received. Thus, the time of the peak of the received signal can be used to determine the time of arrival of the signal at a particular transducer 110a-d. Once the time of arrival has been calculated for each the transducers 110a-d, the time of arrival at the reference transducer is subtracted from the time of arrival for every other receiver and the time difference of arrival (TDOA) can be ascertained.

[0045] To determine the peak of the digitized representation of the received signal, the digitized representation of the received signal is compared to a stored high resolution representation of the received signal. Initially, the received signal is compared to a threshold value and the number of clock signals is counted and the variable Offset is then set to the number of clock values needed to exceed the threshold value and a flag is set, the value of the threshold is selected based on the system parameters and the signal to noise ratio desired. The flag controls whether the channel will be storing data. After the flag is set, the channel will store received signal data. The Offset value will be the initial sampling time. Once the flag has been set, the next 90 values of the received signal will be stored. Once 90 values have been stored, a flag will be set indicating that sampling for that channel has been completed. FIG. 8 depicts a received signal that has been sampled and stored.

[0046] After all the channels have stored 90 samples each curve is normalized to the amplitude of the stored curve that each of the sampled signals will be compared to, see FIG. 9A. After normalizing each sampled signal, the signal is then shifted in time, see FIG. 9B and subtracted from the stored curve forming an error value. The sampled signal is shifted in time until the error is minimized and the amount of shift required is stored as a variable Shift, see FIG. 9C.

[0047] After shifting a sampled signal to minimize the error, the time value for the start of the sampled signal and the difference from that time to the peak is known. To determine the absolute peak time, i.e., the time difference from the start of the sampling to the time when the peak is reached, the Shift value is subtracted from the Offset value. This is value is the time of arrival for a single channel. As discussed above, one transducer is designated the reference transducer and the time of arrival of the reference transducer is subtracted from time of arrival for each of the other transducers 110a-d in order to determine the TDOA for each transducer.

[0048] Once all of the receiver TDOA have been determined, calculations using the TDOA data are performed to develop an estimate of the spatial location of the transmitter. In the following equations, c represents the speed of sound in air, the L, R, Q, W, and C are the initial coordinates of the transducers 110a-d in the transducers array, and x, y, and z are the coordinates of the transmitter. The following four equations relate the propagation time to the distance between each receiver and the transmitter:

[0049] $T_L=\frac{1}{c}\sqrt{{\left(x_L-x\right)}^2+{\left(y_L-y\right)}^2+{\left(z_L-z\right)}^2}$ $T_R=\frac{1}{c}\sqrt{{\left(x_R-x\right)}^2+{\left(y_R-y\right)}^2+{\left(z_R-z\right)}^2}$ $T_Q=\frac{1}{c}\sqrt{{\left(x_Q-x\right)}^2+{\left(y_Q-y\right)}^2+{\left(z_Q-z\right)}^2}$ $T_C=\frac{1}{c}\sqrt{{\left(x\right)}^2+{\left(y\right)}^2+{\left(z\right)}^2}.$

[0050] The following equations are used to calculate the TDOA between the receiver and each of the other receivers. By simultaneously solving these equations for x, y, and z the position of the transmitter may be determined:

[0051] ${\tau }_L=T_L-T_C=\frac{1}{c}\sqrt{{\left(x_L-x\right)}^2+{\left(y_L-y\right)}^2+{\left(z_L-z\right)}^2}-\sqrt{x^2+y^2+z^2}$ ${\tau }_R=T_R-T_C=\frac{1}{c}\sqrt{{\left(x_R-x\right)}^2+{\left(y_R-y\right)}^2+{\left(z_R-z\right)}^2}-\sqrt{x^2+y^2+z^2}$ ${\tau }_Q=T_Q-T_C=\frac{1}{c}\sqrt{{\left(x_Q-x\right)}^2+{\left(y_Q-y\right)}^2+{\left(z_Q-z\right)}^2}-\sqrt{x^2+y^2+z^2}.$

[0052] These equations may be solved using known numerical methods that may be programmed using a standard computer language such as C or C++ or may be solved using numerical analysis software such as MATLAB®.

[0053] The computer interface 106 is a programmable controller that communicates through the computer interface, typically a USB interface, to the computer. The microcontroller must also be able to communicate with the DSP chip as well. In one embodiment of the apparatus described herein, a PIC16C745 Microcontroller available from Microchip is a suitable 8-bit CMOS controller with USB support. Programming the microcontroller to communicate with the DSP chip and pass location and other mouse data to the computer would be known in the art and is dependent upon the system configuration. Other mouse data may include gestures that indicate right or left button clicks or movement of a track wheel.

[0054] The power supply for the transmitter should be small, lightweight, and unobtrusive. In one embodiment, the transmitter is disposed upon a user's finger with the transducer resting on top of the user's finger. In this configuration, the movement of the user's hand is sensed and transferred to the computer. Other embodiments are also considered. For example, the transmitter may be placed on a glove that is to be worn by the user or the transmitter may be placed on a moving object whose position needs to be monitored by a system. In the embodiment in which the transmitter is placed on the user's finger or on a glove worn by the user, the transmitter power supply must adaptable to such a configuration.

[0055] Lithium polymer batteries can be configured or molded to take nearly any shape. In one embodiment, the battery may be an ultra-thin lithium polymer power cell from PowerStream Electronics, 140 South Mountainway Dr., Orem, Utah 84058 that is 500 microns thick and has a capacity of 45 mAh. This battery may be shaped into a ring configuration that is sized and configured to slide onto and off of a user's finger. In this embodiment, the transmitter is disposed upon the battery on top of the user's finger.

[0056] It should be appreciated that other variations to and modifications of the above-described apparatus and method for finding the location of a transmitter in 3-dimensional space relative to a predetermined origin may be made without departing from the inventive concepts described herein. Accordingly, the invention should not be viewed as limited except by the scope and spirit of the appended claims.