Acoustic ranging

• US 7,729,204 B2
• Filed: 10/07/2007
• Issued: 06/01/2010
• Est. Priority Date: 06/08/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tan, Kun, Zhang, Yongguang, Peng, Chunyi, Shen, Guobin
• Primary Examiner(s): Tarcza; Thomas H
• Assistant Examiner(s): Ratcliffe; Luke D
• Application Number:
  US11/868,515
• Publication Number:
  US 20080304361A1
• Time in Patent Office: 968 Days
• Field of Search: 367 87-191
• US Class Current: 367/127
• CPC Class Codes: G01S 15/74 Systems using reradiation of acoustic waves, e.g. IFF, i.e. identification of friend or foe
• CPC Class Codes: G06F 3/1446 display composed of modules, e.g. video walls
• CPC Class Codes: G09G 2300/026 Video wall, i.e. juxtaposition of a plurality of screens to create a display screen of bigger dimensions
• CPC Class Codes: G09G 2356/00 Detection of the display position w.r.t. other display screens

Abstract

Acoustic ranging may involve determining a distance between a first device and at least one other device using one or more acoustic signals. In an example embodiment, a first device emits a first acoustic signal and then receives the first acoustic signal at a first time. The first device also receives a second acoustic signal at a second time, with the second acoustic signal having been emitted by a second device. The first device ascertains a first value that reflects a difference between the first time and the second time. Responsive to at least the ascertained first value, the first device determines a distance between the first device and the second device.

Claims

1. A method for acoustic ranging on a first device, the method comprising:

emitting a first acoustic signal from the first device;

receiving the first acoustic signal at a first time at the first device;

receiving a second acoustic signal at a second time at the first device, the second acoustic signal emitted by a second device;

ascertaining a first value reflecting a time difference between the first time and the second time;

receiving from the second device at least a second value reflecting a time difference between when the second device received the first acoustic signal and the second acoustic signal; and

determining a distance between the first device and the second device based at least on the first value and the second value, the first device being different from the second device.

2. The method as recited in claim 1, wherein:

the act of emitting a first acoustic signal comprises an act of emitting the first acoustic signal using a speaker of the first device;

the act of receiving the first acoustic signal at a first time comprises an act of receiving the first acoustic signal at the first time using a microphone of the first device; and

the act of receiving a second acoustic signal at a second time comprises an act of receiving the second acoustic signal at the second time using the microphone of the first device.

3. The method as recited in claim 1, wherein the act of determining a distance between the first device and the second device based at least on the first value and the second value comprises an act of determining the distance between the first device and the second device based at least on the first value, the second value, a first dimension reflecting a distance between a speaker of the first device and a microphone of the first device, and a second dimension reflecting a distance between a speaker of the second device and a microphone of the second device.

4. The method as recited in claim 1, wherein the act of ascertaining a first value comprises an act of ascertaining a first sample point of the first acoustic signal, ascertaining a first sample point of the second acoustic signal, and counting samples between the first sample points of the first and second acoustic signals to derive the first value, wherein the samples are generated on a fixed frequency by an analog-to-digital (A/D) converter of the first device.

5. The method as recited in claim 4, wherein the act of ascertaining a first value further comprises an act of ascertaining the first value based at least in part on a sampling frequency for the sample points of the analog-to-digital (A/D) converter.

6. The method as recited in claim 1, further comprising:

calculating the first time at which the first acoustic signal is received using a coarse-to-fine grained approach that starts by using window energy to locate a possible time of arrival (TOA) and progresses to using at least one cross-correlation computation to obtain a finer TOA from the possible TOA.

7. The method as recited in claim 6, wherein the act of calculating comprises acts of:

locating a maximal window energy in an acoustic recording to a satisfactory precision by reducing a size of windows within which energy of the acoustic recording is being determined; and

locating a high cross-correlation result of the at least one cross-correlation computation while reducing a size of windows within which the cross-correlation computation is being performed.

8. The method as recited in claim 1, wherein:

the first value comprises a first elapsed time between two time-of-arrivals (ETOA) of the first and second acoustic signals, and the second value comprises a second ETOA of the first and second acoustic signals; and

the act of determining a distance between the first device and the second device responsive to at least the first value and the second value comprises an act of determining a difference between the first ETOA and the second ETOA;

or

the first value comprises a first difference between two index sample points at the first device, and the second value comprises a second difference between two index sample points at the second device.

9. The method as recited in claim 1, further comprising:

determining a relative left/right positioning between the first device and the second device using (i) two speakers and one microphone included in the first device or the second device and (ii) separate computations for a left distance and a right distance.

10. The method as recited in claim 1, further comprising:

determining a relative left/right positioning between the first device and the second device using (i) two speakers and one microphone included in the first device or the second device and (ii) separate computations for a left received signal energy magnitude and a right received signal energy magnitude, and a computation of a difference between the left received signal energy magnitude and the right received signal energy magnitude.

11. The method as recited in claim 1, further comprising:

receiving multiple respective acoustic signals at multiple respective times, the multiple respective acoustic signals emitted by multiple respective devices;

receiving from the multiple respective device at least multiple respective values reflecting respective time differences between when the multiple respective devices received the first acoustic signal and respective ones of the multiple respective acoustic signals; and

determining respective distances between the first device and each of the multiple respective devices responsive to at least the first value and respective ones of the multiple respective values.

12. The method as recited in claim 11, wherein the act of receiving multiple respective acoustic signals at multiple respective times comprises an act of receiving the multiple respective acoustic signals within multiple respective time windows that are sequentially assigned to the multiple respective devices.

13. The method as recited in claim 1, further comprising:

transmitting to multiple other devices an acoustic ranging procedure initiation message that includes an acoustic signal order and a time window length;

the acoustic signal order assigning respective time windows for acoustic signal emission to respective ones of the multiple other devices, and the time window length indicating a length of each of the respective time windows.

14. The method as recited in claim 1, further comprising:

transmitting to multiple other devices an acoustic ranging procedure initiation message that includes an assignment of a respective code to each respective one of the multiple other devices;

receiving multiple other acoustic signals that are coded in accordance with the assigned respective code for each respective one of the multiple other devices; and

identifying individual ones of the multiple other acoustic signals using the assigned respective code for each respective one of the multiple other devices.

15. The method as recited in claim 1, further comprising at least one of:

transmitting an acoustic ranging procedure initiation message to the second device, the acoustic ranging procedure initiation message including one or more parameters specifying how to participate in an acoustic ranging procedure;

or

receiving an acoustic ranging procedure initiation message from the second device.

16. One or more processor-accessible storage media comprising processor-executable instructions that, when executed, direct a first device to perform acts comprising:

emitting a first acoustic signal from the first device;

receiving the first acoustic signal at a first time at the first device;

receiving a second acoustic signal at a second time at the first device, the second acoustic signal emitted by a second device;

ascertaining a first value reflecting a time difference between the first time and the second time by ascertaining a first sample point of the first acoustic signal, ascertaining a first sample point of the second acoustic signal, and counting samples between the first sample points of the first and second acoustic signals to derive the first value, wherein the samples are generated on a fixed frequency by an analog-to-digital (A/D) converter of the first device;

receiving from the second device at least a second value reflecting a time difference between when the second device received the first acoustic signal and the second acoustic signal; and

determining a distance between the first device and the second device based at least on the first value and the second value, the first device being different from the second device.

17. A first device comprising:

at least one speaker;

at least one microphone;

an actuator to emit, in conjunction with the speaker, a first acoustic signal;

a sensor to receive, in conjunction with the microphone, the first acoustic signal at a first time and a second acoustic signal at a second time, the second acoustic signal emitted by a second device;

a calculator to ascertain a first value reflecting a time difference between the first time and the second time and to determine a distance between the first device and the second device based at least on the first value, the first device being different from the second device;

an application programming interface (API) to expose an acoustic ranging capability to other applications; and

an acoustic ranging controller to control performance of acoustic ranging procedures by controlling at least the calculator and to interact with the other applications via the API by receiving acoustic ranging procedure requests from the other applications and by sending calculated distances to the other applications.

18. The device as recited in claim 17, further comprising:

a communicator to receive, via a communication channel from the second device, at least a second value reflecting a difference between when the second device received the first acoustic signal and the second acoustic signal;

wherein the calculator is further to determine the distance between the first device and the second device based at least on the first value and the second value.

19. The device as recited in claim 17, further comprising:

a signal generator to generate a waveform for the first acoustic signal and to feed the generated waveform to the actuator; and

a detector to detect the first time and the second time;

wherein the sensor is to record incoming sound data into a buffer and feed the recorded sound data to the detector; and

wherein the detector is further to detect a first sample point corresponding to the first time and a second sample point corresponding to the second time by analyzing the recorded sound data and a reference version of the generated waveform, the first sample point and the second sample point relating to sample points of an analog-to-digital (A/D) converter of the first device.

20. The device as recited in claim 17, wherein the sensor is to sense the first and second acoustic signals via a coarse-to-fine grained approach that starts by using window energy to locate a possible time of arrival (TOA) and progresses to using at least one cross-correlation computation to obtain a finer TOA from the possible TOA.