Device-to-device relative localization

• US 9,674,661 B2
• Filed: 10/21/2011
• Issued: 06/06/2017
• Est. Priority Date: 10/21/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Meng, Xiangying, Moscibroda, Thomas, Chu, David Chiyuan, Qiu, Jian
• Primary Examiner(s): SCHWARTZ, JOSHUA L
• Application Number:
  US13/279,137
• Publication Number:
  US 20130102324A1
• Time in Patent Office: 2,055 Days
• Field of Search: 4554563, 455457, 4554561-4566
• CPC Class Codes: G01S 5/0284 Relative positioning
• CPC Class Codes: G01S 5/16 using electromagnetic waves other than radio waves
• CPC Class Codes: G01S 5/18 using ultrasonic, sonic, or infrasonic waves
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/80 Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication

Abstract

Techniques for generating a real-time 3D position of one device relative another device are described herein. In one embodiment, a first device may be equipped with one or more transmitters and receivers to collect location information based on direct localized signal transmission between the first device and a second device. The first device may also be equipped with an accelerometer and/or digital compasses to assist in resolving ambiguous locations when the first device and the second device are not at an alignment position. Each device may transmit part or all of its collected location information to another device to assist in obtaining the relative location. Alternatively, a separate server may receive the location information from the devices and calculate the relative location of each device based on the received location information.

Claims

1. A method comprising:

receiving, by a first handheld device, one or more localized signals from a second handheld device;

determining, based at least in part on the one or more localized signals, a location of the second handheld device relative to the first handheld device, the location comprising at least one of a distance between the second handheld device and the first handheld device or angle values of the second handheld device relative to the first handheld device;

obtaining, at the first handheld device, sensor data from one or more sensors of the first handheld device, the one or more sensors including at least one of an accelerometer, a gyroscope, or a compass;

determining, based at least in part on the location of the second handheld device relative to the first handheld device and the sensor data, that the first handheld device is at an alignment position with the second handheld device, the alignment position including a predetermined orientation and a predetermined proximity between the first handheld device and the second handheld device when a microphone of the first handheld device faces a speaker of the second handheld device, and both the first handheld device and the second handheld device are moving.

2. A method as recited in claim 1, wherein the one or more localized signals are transmitted over a distance of at most 10 meters.

3. A method as recited in claim 1, further comprising:

receiving, by the first handheld device, one or more additional localized signals from the second handheld device at different times; and

determining, based at least in part on at least one of the one or more localized signals and the one or more additional localized signals, a three-dimension (3D) location of the second handheld device relative to the first handheld device due to a movement of at least one of the first handheld device or the second handheld device.

4. A method as recited in claim 1, further comprising:

transmitting, by the first handheld device, two or more localized signals to the second handheld device through two or more transmitters on the first handheld device, the two or more localized signals configured to be received by a receiver of the second handheld device to allow the second handheld device to determine a three-dimension (3D) location of the first handheld device relative to the second handheld device.

5. A method as recited in claim 1, further comprising receiving location information collected by the second handheld device.

6. A method as recited in claim 1, wherein the determining the location of the second handheld device relative to the first handheld device comprises:

sending, by the first handheld device, one or more packets comprising data representing the one or more localized signals to a server separate from the first handheld device and from the second handheld device, the server being configured to process the data representing the one or more localized signals to generate the location of the second handheld device relative to the first handheld device; and

receiving, by the first handheld device, the location of the second handheld device relative to the first handheld device.

7. A method as recited in claim 1, wherein the one or more localized signals further include one or more of:

an audio signal;

an ultra-sonic signal;

a sub-sonic signal;

a radio frequency signal;

or

an infrared signal.

8. The method of claim 1, wherein determining the location of the second handheld device relative to the first handheld device based at least in part on the one or more localized signals is performed independent of a Global Positioning System (GPS) signal, a cellular network signal, or a WiFi signal.

9. A method as recited in claim 1, wherein the determining the location of the second handheld device relative to the first handheld device comprises determining at least one of:

a time-of-arrival (TOA) difference between the one or more localized signals being received at a first receiver of the first handheld device and a second receiver of the first handheld device;

or

an amplitude difference between the one or more localized signals being received at the first receiver of the first handheld device and the second receiver of the first handheld device.

10. A method as recited in claim 9, wherein the determining the location of the second handheld device relative to the first handheld device comprises analyzing the TOA difference to triangulate the location of the second handheld device relative to the first handheld device.

11. One or more computer storage media, embodied in hardware, having stored thereupon a plurality of computer executable instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:

determining whether a first device is at an alignment position with a second device, the alignment position including a predetermined angular orientation relative to the second device;

in response to determining that the first device is at the alignment position with the second device;

establishing a time synchronization between the first device and the second device;

receiving, by the first device, multiple localized signals from the second device, the multiple localized signals comprising at least one of multiple audio signals, multiple radio frequency signals, multiple ultra-sonic signals, multiple sub-sonic signals, or multiple infrared signals; and

determining, by the first device and based at least in part on differences in reception of the multiple localized signals, at least one of a distance between the second device and the first device or angle values of the second handheld device relative to the first handheld device; and

in response to determining that the first device is not at the alignment position with the second device;

establishing a location of the second device relative to the first device when the first device is at the alignment position with the second device immediately before when the first device is not at the alignment position with the second device;

receiving, from the second device, a signal comprising information relating to a reading of a sensor of the second device that detects an orientation of the second device to resolve ambiguous positions; and

updating the location of the second device relative to the first device at least partly based on the information relating to the reading of sensor of the second device.

12. One or more computer storage media as recited in claim 11, further comprising:

in response to determining that the first device is not at the alignment position with the second device,

providing an estimate of the location of the second device relative to the first device based on data collected from an accelerometer and a compass of the second device; and

detecting when the first device is at the alignment position with the second device.

13. The one or more computer storage media as recited in claim 11, wherein the predetermined orientation is preset such that an error of localization accuracy is within a preset threshold.

14. One or more computer storage media as recited in claim 11, further comprising in response to determining that the first device is at the alignment position with the second device,

receiving another signal including additional location information collected by the second device;

and

calculating the location of the second device relative to the first device based on the additional location information and the multiple localized signals.

15. One or more computer storage media as recited in claim 14, further comprising using a Kalman filter to smooth a result of the calculation.

16. A first handheld device comprising:

one or more receivers that receive one or more localized signals from a second handheld device;

memory storing one or more modules;

one or more processors operably coupled to the memory to execute the one or more modules to;

receive, by the first handheld device, one or more localized signals from a second handheld device;

determine, based at least in part on the one or more localized signals, a location of the second handheld device relative to the first handheld device, the location comprising at least one of a distance between the second handheld device and the first handheld device or angle values of the second handheld device relative to the first handheld device;

determine, based at least in part on the location of the second handheld device relative to the first handheld device, that a microphone of the first handheld device faces a speaker of the second handheld device, and both the first handheld device and the second handheld device are moving.

17. A first handheld device as recited in claim 16, further comprising:

one or more sensors that collect a rotation matrix of the first handheld device, the one or more sensors including at least one of an accelerometer, a compass, or a gyroscope; and

the one or more processors operably coupled to the memory to execute the one or more modules to further determine whether the first handheld device and the second handheld device are at an alignment position based on data collected by the one or more sensors, the alignment position being a predetermined orientation and a predetermined proximity relative to the second handheld device.

18. A first handheld device as recited in claim 16, wherein determining the location of the second handheld device relative to the first handheld device comprises determining at least one of:

a time-of-arrival (TOA) difference between multiple received signals at different receivers of the first handheld device, the multiple received signals corresponding to one signal received from a transmitter of the second handheld device;

or

an amplitude difference between the multiple received signals.

19. A first handheld device as recited in claim 16, wherein the one or more processors are operably coupled to the memory to further execute the one or more modules to:

send data representing the one or more localized signals to a server separate from the first handheld device; and

receive, from the server, the location of the second handheld device relative to the first handheld device, the location having been calculated by the server based on the collected location information.

20. The first handheld device of claim 16, wherein:

the one or more localized signals comprise multiple localized signals;

the one or more modules are further executable by the one or more processors to analyze the multiple localized signals to identify differences in reception strength of the multiple localized signals; and

the determining that the microphone of the first handheld device faces the speaker of the second handheld device is further based at least in part on the differences in the reception strength of the multiple localized signals.