Distance measurements between computing devices

Some implementations provide techniques and arrangements for distance measurements between computing devices. Some examples determine a distance between devices based at least in part on a propagation time of audio tones between the devices. Further, some examples determine the arrival time of the audio tones by performing autocorrelation on streaming data corresponding to recorded sound to determine a timing of an autocorrelation peak indicative of a detection of an audio tone in the streaming data. In some cases, cross correlation may be performed on the streaming data in a search window to determine a timing of a cross correlation peak indicative of the detection of the audio tone in the streaming data. The location of the search window in time may be determined based at least in part on the timing of the detected autocorrelation peak.

BACKGROUND

The continued proliferation of computing devices, including mobile computing devices, has led to an increase in the availability of applications and other content used on these devices. For instance, users employ a variety of applications, such as games, digital media players, browsers, and the like, on an assortment of computing devices. As the number of computing devices and applications used on these devices continues to increase, users are ever more interested in enhancing their experiences while using these computing devices and applications.

SUMMARY

Some implementations provide techniques and arrangements for distance measurements between computing devices, such as mobile computing devices. For example, some determine a distance between devices based at least in part on a propagation time of audio tones between the devices. Some determine the arrival time of the audio tones by performing autocorrelation on streaming data corresponding to recorded sound to determine a timing of an autocorrelation peak indicative of a detection of an audio tone in the streaming data and performing cross correlation on the streaming data in a search window to determine a timing of a cross correlation peak indicative of the detection of the audio tone in the streaming data, the location of the search window in time being determined based at least in part on the timing of the detected autocorrelation peak.

DETAILED DESCRIPTION

Overview

Some implementations herein enable a plurality of computing devices to continuously maintain an accurate measurement of distance between the devices. Such computing devices may include digital media devices and eBook readers; tablet computing devices; desktop, terminal and workstation computing devices; smart phones and mobile devices; laptop and netbook computing devices; televisions, gaming systems and home electronic devices; or the like. In some examples herein, sound can be used for such distance measurements. Many conventional distance ranging protocols are based on the assumption that device positions remain static during the process of taking a measurement. For many applications, such as motion based games, this is not a valid assumption. Furthermore, if the devices are moving towards or apart from each other, other issues, such as Doppler effects, may affect measurement accuracy.

This disclosure includes techniques and arrangements for fast and accurate real-time distance measurements between computing devices. In some implementations, a system implements an algorithm which uses a combination of autocorrelation and cross-correlation to compute the distance between two devices. In addition or alternatively, some implementations use a pipelined streaming execution framework which performs multiple operations in parallel, such as recording of audio into an audio stream in parallel with the performance of correlation and distance computations on the recorded audio stream. Further, some implementations may implement techniques to mitigate Doppler effects and/or techniques to handle multi-path, ambient noise, and packet loss.

One example implementation may include, for example, a phone-to-phone mobile motion game (MMG), in which two players wield their phones, and try to “attack” each other. The rules can be varied, but in one instance, a player wins if the player makes an “attack gesture” while the player's phone is within a set distance of the opponent's phone, e.g., 20 cm. A game of this type relies on the ability to conduct fast, accurate, and robust distance measurements between the phones, so that, at any moment during play, both phones have precise distance information, i.e., both phones know how far they are apart from each other. Furthermore, the measurements may also be highly accurate, such as within less than a few centimeters, and may be robust in the face of movement and ambient or external noise.

Of course, it should be understood that, though this disclosure may describe the system and method in the context of such a game for ease of understanding, the system and method described herein are not limited to such uses and may be used in many other situations.

The distance measurement functionality described herein may be implemented at various levels in the software and hardware of computing systems. Such levels include the Operating System (OS) level, such as in the OS with or without application support, the application level, either separate from OS (i.e. stand-alone) or as a plug-in to the OS or a plug-in to another application and so forth.

It should also be noted that, for readability, interactions between modules may be described herein as signals, commands or the passage of data items, but it would be understood by one of ordinary skill in the art that such interactions may be implemented in various ways, such as by function calls between various program modules.

Example Implementations

FIG. 1illustrates an example framework of a system100according to some implementations. System100includes a first device102and a second device104. An exploded view of the first device102is shown below the devices and illustrates the first device102as a logical system made up of a speaker106, a microphone108, a transceiver110, and a ranging module112. Although not shown, in some implementations, the second device104includes the same or similar components as the first device102.

Viewing the operation of the system100at this depth, the first device102and second device104output tone A114and tone B116respectively from their speakers106and record sound at microphones108. The recorded sound is input to the ranging module112. The ranging module112of each device processes the recorded sound to detect the tone A114or B116output by the speaker of the other device to determine the time that the tone A114or tone B116that was received. The devices102and104then exchange the determined times via the transceiver110of devices102and104. The ranging module112of each device then uses the exchanged times to determine the distance between the first device102and the second device104. The determination of distance may also be based on the time at which the first device102and the second device104output tone A114and tone B116, respectively. In some implementations, the first device102and second device104each store the time at which a command was issued to output tone A114or tone B116. In other implementations, the first device102and the second device104may each detect the reception of both tone A114and tone B116at its respective microphone108. Such implementations are useful in many situations, for example, where the devices have unpredictable delays or lag times from the issuance of a command to output a tone until the actual output of the tone from the speaker.

Thus, while the users of the first device102and the second device104are operating their devices in a distance based application, such as the phone-to-phone mobile motion game discussed above, the devices102and104repeatedly determine distance between the devices based on the exchanged tones to allow the distance based application to operate.

The ranging module112includes a playback module118, a recording module120, an autocorrelation module122, a cross-correlation module124, a measurement exchange module126, and a distance calculation module128. While the ranging module112is illustrated as including these separate modules, implementations are not so limited and may be implemented as any number of modules and hardware components. As such, the logical arrangements illustrated herein may be implemented as several components of hardware each configured to perform one or more functions, may be implemented in software or firmware where one or more programs are used to perform the different functions, or may be a combination of hardware, firmware, and/or software. For purposes of discussion, the modules described herein will be discussed as a set of software routines stored in a computer readable storage medium.

In operation, the playback module118and recording module120control the operations of the speaker106and microphone108to output the tone A114and tone B116and record sound including the tones. The sound that is recorded by the microphone108is received by the recording module120and passed to the autocorrelation module122as recorded sound stream130.

In some implementations, tones A114and B116each include two copies of a respective pseudorandom sequence. In other words, tone A114is composed of a first pseudorandom sequence followed immediately by an exact copy of the first pseudorandom sequence. Tone B116is similarly composed of a second pseudorandom sequence followed immediately by an exact copy of the second pseudorandom sequence. Where the length of a tone is L seconds, the autocorrelation module122operates by correlating a sliding window of the recorded audio stream130L/2 seconds wide such that autocorrelation is performed on the most recent L/2 seconds of the recorded audio stream130with a L/2 seconds length portion of a delayed sound stream that a copy of the recorded audio stream130that is delayed by L/2 seconds. The autocorrelation module122determines the time that the correlation peaks and outputs the time to the cross correlation module124as autocorrelation peak132. It should also be noted that the use of different pseudorandom sequences for tone A114and tone B116provides an additional benefit in that it allows for tone loss detection. Specifically, in systems in which the first device102and the second device104each detect the reception of both tone A114and tone B116at its respective microphone108, if a device detects the same tone consecutively, it will be able to determine that it has lost at least one tone that may have occurred there between. Further tone loss detection capabilities may be provided by implementing the system to use four (or more) tones instead of two. In other words, systems may alternate such that a first distance measurement may be made based on an exchange of tone A114and tone B116and a second distance measurement may be made based on an exchange of a tone A′ and a tone B′ and then repeating the exchange of tone A114and tone116and so on.

FIG. 2illustrates a graph200of the timing of the operation of autocorrelation module122according to some implementations and, in particular, charts the autocorrelation202calculated by the autocorrelation module122. The autocorrelation202indicates the correlation between the recorded sound stream130and a delayed sound stream204. In particular, as the recorded sound stream130is received, the stream is copied and stored as the delayed sound stream204, which as stated above is delayed by L/2 seconds relative to the recorded sound stream130. Thus, as the recorded sound stream130is recorded, the first and second halves of tone B in the recorded sound stream130, i.e. tone B1206and tone B2208, are duplicated and stored as tone B1210and tone B2212of the delayed sound stream204.

During operation, the autocorrelation module122correlates respective L/2 length portions of the recorded sound stream130and delayed sound stream204that are within the autocorrelation window214at each unit of time, i.e. the autocorrelation is determined for each of a plurality of iterations. InFIG. 2, tone B2208of the recorded sound stream130and tone B1210of the delayed sound stream204are in the autocorrelation window214. As can be seen inFIG. 2, in the iterations corresponding to the moments leading up to the autocorrelation window214being positioned as shown inFIG. 2, i.e. as the autocorrelation window214slid to the right with each passing unit of time, the autocorrelation202has risen. When the autocorrelation window214is at the point shown inFIG. 2, the autocorrelation202peaks, identified as autocorrelation peak132. This is because the portions of the recorded sound stream130and delayed sound stream204, i.e. tone B2208tone B1210, are matching copies of the same pseudorandom sequence and thus have a high correlation. In fact, ignoring distortions that occur in realistic situations, the correlation at this time may be seen as the maximum possible correlation. Following the occurrence of the autocorrelation peak132inFIG. 2, i.e. as the autocorrelation window214continues to slide to the right as with each passing unit of time, the autocorrelation202falls. The autocorrelation module122determines the time at which the autocorrelation202peaks, shown as autocorrelation peak132, and passes this data to the cross correlation module124.

The autocorrelation module122may calculate the autocorrelation value using the following equation:

R⁡(L/2,t0)=∑t∈W⁢⁢[X⁡(t)-X⁡(t)_]*[Y⁡(t)-Y⁡(t)_]∑t∈W⁢⁢[X⁡(t)-X⁡(t)_]2*∑t∈W⁢[Y⁡(t)-Y⁡(t)_]2⁢⁢where⁢⁢X⁡(t)_=∑t∈W⁢⁢X⁡(t)L/2,Y⁡(t)_=∑t∈W⁢⁢Y⁡(t)L/2,and⁢⁢W=[t0-L2+1,t0],X⁡(t)(1)
being the recorded sound stream130and Y(t) being the delayed sound stream204. As is apparent from previous discussions, the higher the autocorrelation value, i.e. R(L/2, t0), the more closely the X(t) correlates to Y(t).

The above equation for R(L/2, t0) can be expressed in a form that can be computed in linear time for the sliding autocorrelation window technique discussed above. In particular, the equation can be expressed as:

The linear complexity computation works as follows. Take XΣas an example, assuming its value at time t0is known, i.e. XΣ(t0), then

X⁡(t0-L2+1),
and XΣ(t0) are known, XΣ(t0+1) is computed in O(1) time. The other variables can be updated in the same way. Thus, for any t0, R(L/2, t0) can be computed in O(1) time by sliding the autocorrelation window214along t using equation 3.

Furthermore, while the recorded sound stream130and the delayed sound stream204are shown as two separate streams in this example, other implementations are not so limited. For example, in some implementations, one copy of the recorded sound stream130may be kept and one or more memory pointers may be used to indicate the beginning and end of a virtual delayed sound stream without duplicating the recorded audio stream130. This and other variations on the implementation of the particulars of the data storage would be apparent to one of ordinary skill in the art in view of the disclosure herein.

As stated above, once determined, the timing of the autocorrelation peak132is passed to the cross correlation module124by the autocorrelation module122. The cross-correlation module124determines the precise timing of tone B by searching in a relatively small cross correlation search window around the autocorrelation peak132using cross-correlation. There are several reasons for using the cross correlation module124in addition to the autocorrelation module122. First, auto-correlation fundamentally has a much flatter peak area. In other words, if a time slot's autocorrelation is high, its neighboring time slot's value is also high. Thus, a precise timing of the tone is difficult to determine. For this reason, the autocorrelation peak may be described as giving a “rough” timing estimate of the arrival time of the tone. Second, an offset can result due to signal distortion of the tone after propagation. Even in quiet environments, this can result in errors on the order of centimeters in the final result. Cross-correlation, on the other hand, is able to determine the time-of-arrival peak much more accurately in some implementations. For these reasons, in some implementations, cross correlation is performed on a search windows which is determined based on the result of the autocorrelation. This window is relatively small. This way, some implementations combine the benefits of cross correlation and autocorrelation.

In some implementations, the cross correlation module124operates by performing cross correlation on a predetermined number of L second long windows of the recorded sound stream130ending at evenly spaced points throughout the cross correlation search window. In some implementations, the correlation determined by the cross correlation module124is between the content of each of the L length windows and a reference copy of tone B116. In such implementations, the reference copy of tone B116may be received from the second device104at the initialization of communication between the first device102and second device104by the distance based application. Alternatively, the reference copy of tone B116may be predetermined and “hard-coded” into the distance based application. Of course, other variations on the implementation of the particulars of how the reference copy of tone B116becomes known to the first device102would be apparent to one of ordinary skill in the art in view of the disclosure herein.

FIG. 3illustrates a graph300showing the timing of the operation of cross correlation module124and, in particular, charts the cross correlation302calculated by the cross correlation module124. In particular, for each of a number of L second length windows of the recorded sound stream130ending at points spaced throughout the cross correlation search window304, the cross correlation module124calculates the cross correlation302between the content of the L second window of the recorded sound stream130and a reference copy of tone B116. Thus, as shown inFIG. 3, at the point in the cross correlation search window304corresponding to the end of the recorded tone B116, a sharp cross correlation peak306occurs in the cross correlation302that indicates the “precise” timing of tone B116. The cross correlation module124passes the precise timing that has been determined by the cross correlation module124to the measurement exchange module126. Further, in cases where the autocorrelation module122finds a “false peak,” i.e. an autocorrelation peak which does not actually correspond to the arrival of tone A114or tone B116, the cross correlation module124may find no cross correlation peak306and can thereby prevent a false positive that would otherwise result from the use of the autocorrelation module122alone.

The cross correlation module124may calculate the cross correlation value using the following equation:

CC⁡(t0)=∑t∈W⁢⁢[X⁡(t)-X⁡(t)_]*[T⁡(t-t0)-T⁡(t-t0)_]∑t∈W⁢⁢[X⁡(t)-X⁡(t)_]2*∑0t=1-L⁢[T⁡(t)-T⁡(t)_]2(4)
where X(t) is the recorded sound stream130, T(t), tε[−L+1, 0] is the reference copy of the tone to be detected,

As indicated above, the cross correlation module124passes the precise timing that has been determined by the cross correlation module124to the measurement exchange module126. The measurement exchange module126controls the transceiver110to exchange the precise timing determined by the cross correlation module124with the other device and receives the precise time determined by the correlation module124of the ranging module112of the other device. Other information may be exchanged before, during, or after this time. The exchanged and determined information is then passed to the distance calculation module128.

The distance calculation module128uses the exchanged and determined information to determine the distance between the first device102and second device104.

The distance calculation module128may calculate the distance between the first device102and the second device104using the following equation:

d=12·c·((tA⁢⁢2-tB⁢⁢1)-(tA⁢⁢1-tB⁢⁢2))(5)
where c is the speed of sound, tA1is the time tone A is output by the speakers of the first device102, tA2is the time tone A is determined to have been received by the microphone108of the second device104, tB1is the time tone B is output by the speakers of the second device104, and tB2is the time tone B is determined to have been received by the microphone108of the first device102. In implementations in which each of the first device102and the second device104use autocorrelation and cross correlation to determine the precise arrival timing of both tone A114and tone B116at its own respective microphones, tA1and tB1can be the times at which tone A114and tone B116are determined to have been received at the microphone of the first device102and the microphone of the second device104, respectively. In such implementations, some portion of the calculation may be performed before the devices exchange timing data. For example, each device may determine the difference between the time that tone A114and tone B116were received at its respective microphone and then exchange the calculated differences rather than the specific times of arrival that are determined using correlation. This and other variations on the implementation of the particulars of the calculation of the distance based on the times of arrival would be apparent to one of ordinary skill in the art in view of the disclosure herein.

FIG. 4illustrates an example process flow400according to some implementations. In this particular case, the process flow illustrates the process of the first device102outputting tone A114, detecting the timing of tone A at its own microphone108, exchanging the timing with the second device104which provides the timing of tone A at the microphone108of the second device104, and calculating the distance based thereon. In the flow diagrams ofFIG. 4, each block represents one or more operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the blocks represent computer-executable instructions that, when executed by one or more processors, cause the processors to perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, modules, components, data structures, and the like that perform particular functions or implement particular abstract data types. The order in which the blocks are described is not intended to be construed as a limitation, and any number of the described operations can be combined in any order and/or in parallel to implement the processes. For discussion purposes, the process flow400is described with reference to the system100, described above, although other models, frameworks, systems and environments may implement the illustrated process.

At block402, the playback module118of the first device102controls the speakers106to play tone A114which includes two copies of a pseudorandom sequence.

At block404, the recording module120of the first device102controls the microphone108to record audio and passes the recorded sound stream130to the autocorrelation module122.

At block406, the autocorrelation module122performs autocorrelation on the recorded sound stream130to detect a “rough” arrival time of tone A114. The determination may be performed in the manner discussed above with respect toFIG. 2. The rough arrival time of tone A114is passed to the cross-correlation module124.

At block408, the cross cross-correlation module124performs cross-correlation to search a relatively small window of the recorded sound stream130located around the rough arrival time determined by the autocorrelation module122to detect a precise arrival time of tone A114. The cross correlation determination may be performed in the manner discussed above with respect toFIG. 3. The precise arrival time of tone A114is passed to the measurement exchange module126.

At block410, the measurement exchange module126controls the transceiver110to send the precise arrival time of tone A114determined by the cross correlation module124to the second device104and receives a precise time determined by the correlation module124of the ranging module112of the second device104for the arrival time of tone A114at the second device104. As stated above, other information may be exchanged before, during, or after this time. In some embodiments, blocks404,406,408and410may be repeated to ascertain the precise arrival time of tone B116at the first device102and the second device104. Having the precise arrival time of both tone A114and tone B116at the microphones of both the first device102and the second device104provides the additional benefit that fixed clock synchronization errors between the first device102and the second device104will be eliminated, as is apparent from equation 5 discussed above. The exchanged and determined information is then passed to the distance calculation module128as timing information136.

At block412, the distance calculation module128receives the timing information136. The distance calculation module128uses the timing information136to determine the distance between the first device102and second device104. The calculation of the distance using the timing information136may be performed in the manner discussed above with respect toFIG. 1and using equation 5 discussed above.

The process flow400shown inFIG. 4can be implemented with many variations that would be apparent to one of ordinary skill in the art in view of the disclosure provided herein. One aspect of process flow400that can be varied is whether the steps are performed sequentially or in parallel.

FIG. 5illustrates an execution time diagram500of the first device102in a sequential implementation. To implement process flow400in a sequential manner, the system implements the process using a play and/or record then compute and exchange sequence. The particular implementation shown inFIG. 5is of a type which alternates between tone B116being output by the second device104and tone A114being output by the first device102, with each of the first device102and the second device104using autocorrelation and cross correlation to determine the precise arrival timing of both tone A114and tone B116at its respective microphone. This is differentiated from other implementations in which a device outputting a particular tone does not determine the precise arrival timing of that tone at its own respective microphone. As mentioned previously, such implementations may rely on other information, such as the time at which the command to output the particular tone was issued.

At502, the first device102records audio for a predetermined amount of time during which the second device104outputs tone B116. At the end of the predetermined amount of time, i.e. at504, the first device102and second device104use autocorrelation to detect the rough arrival timing of tone B116at their respective microphones. Then, at506, the first device102and second device104use cross correlation to detect the precise arrival timing of tone B116at their respective microphones. At508, the first device102and second device104exchange the precise arrival timings of tone B at their respective microphones. At510, the first device102outputs tone A114while recording audio during a predetermined amount of time represented by the width of510. Next, during512and514, the first device102and second device104each use autocorrelation and then cross correlation to detect the precise arrival timing of tone A114at their respective microphones. Finally, at516, the first device102and second device104exchange the precise arrival timings of tone A114at their respective microphones and use the precise arrival timings of tone A114and tone B116at the microphones of the first device102and second device104to calculate the distance between the devices. Thus, at the end this sequence, indicated by518, the distance between the devices has been determined. This process would then repeat. The measurement delay520for the sequential implementation is shown inFIG. 5and encompasses the entire width of the execution time diagram shown inFIG. 5. While the sequential implementation described above with respect toFIG. 5is faster than conventional systems, further improvement is achieved by performing at least some of the operations in parallel. Such a parallel implementation is described with reference toFIG. 6.

FIG. 6illustrates an example execution time diagram600according to some implementations of the first device102that include parallel execution of some operations. In particular, in a system operating in the manner shown inFIG. 6, the operations of the ranging module112are performed by at least five concurrently executing threads: a playback thread602, a recording thread604, an autocorrelation thread606, a cross correlation thread608, and a measurement exchange and distance calculation thread610.

The playback thread602is responsible for controlling the speaker106to output tone A114as described above. Similarly, the recording thread604is responsible for controlling the microphone108to record audio and for providing the recorded sound stream130to the autocorrelation thread606. One example of concurrency of the playback thread602and the recording thread604occurs when playback thread602controls the speaker106of the first device102to output tone A114while the recording thread604controls the microphone to record audio. The concurrency of the playback and recording may also occur in the sequential implementation discussed with respect toFIG. 5because in the sequential implementation the first device102and the second device104may each determine the precise arrival timing of both tone A114and tone B116at their respective microphones. However, the implementations operating in the manner shown inFIG. 6include further concurrency of operation than those operating as shown inFIG. 5, as will be described below.

The autocorrelation thread606operates concurrently with the recording thread604such that the recording operation does not stop during the autocorrelation operation. In some implementations, at least the recording thread604and the autocorrelation thread606operate nearly continuously, if not actually continuously, during the operation of the ranging module112. The autocorrelation thread606detects autocorrelation peaks, e.g. autocorrelation peak132, and outputs the timing of the detected autocorrelation peaks to the cross correlation thread608. The autocorrelation thread606may operate in the manner discussed above regarding the autocorrelation module122ofFIG. 1. InFIG. 6, example detections and outputting of the timings of autocorrelation peaks is indicated inFIG. 6as black vertical lines in the autocorrelation thread606. The first such detection and output of an autocorrelation peak is indicated as item612.

Prior to being provided with the timing of an autocorrelation peak by the autocorrelation thread606, the cross correlation thread608may be idle. When the timing of an autocorrelation peak is provided by the autocorrelation thread606, the cross correlation thread608performs cross correlation in a search window surrounding the location in time of the autocorrelation peak132to determine a precise arrival time of the tone corresponding to the autocorrelation peak132at the microphone in the manner discussed above regardingFIG. 1. Once the precise arrival timing of the tone is determined by the cross correlation thread608, the timing is provided to the measurement exchange and distance calculation thread610which controls the transceiver110to exchange the determined precise arrival timing with the second device.

In contrast toFIG. 5, before the cross correlation thread608and measurement exchange and distance calculation thread610complete the operations for the first tone at the point indicated by item614, in this case tone B116, the playback thread602begins outputting tone A114, as indicated by item616. Though not shown inFIG. 6, the playback thread602may even begin outputting tone A114prior to the detection of the first autocorrelation peak at612. Soon after the outputting of tone A114begins, the recording thread604begins to record tone A114and the autocorrelation thread606detects the arrival of tone A as a second autocorrelation peak, indicated by item618. Cross correlation is performed for the second autocorrelation peak by the cross correlation thread608and the resulting precise timing is exchanged with the second device104by the measurement exchange and distance calculation thread610. Finally, at the point indicated by item620, the measurement exchange and distance calculation thread610uses the precise arrival times of tone A114and tone B116at the microphones of the first device102and second device104to calculate the distance between the devices. As shown inFIG. 6, the process would then repeat. The overall time for measuring the distance between the devices is indicated by item622.

As stated above, implementations including parallel execution of operations provide benefits over sequential implementations. Specifically, in some implementations, by overlapping of the recording operations with the correlation, exchange and compute operations, the number of distance measurements performed in a set amount of time can be more than double that of sequential implementations using the same calculation techniques. However, as stated previously, while benefits are seen in the parallel implementations, implementations of the described system and method should not be construed as limited to parallel implementations.

As previously mentioned, in motion based applications, the Doppler effect can have an impact on the correlation processes. Doppler effects happen when there is a relative movement between the sound player and recorder. In short, when two devices are moving towards each other, the sound wave will arrive at the recorder earlier than expected so that the recorded tone appears “compressed.” Thus, since the recorder is still recording the sound at a constant rate, the recorded sound samples will be shorter than expected. This means, in the recorded version of the tone, the repeating pseudorandom sequences will have a shorter length than the autocorrelation window, i.e. L/2. Thus, the window used in the autocorrelation calculation may be adapted to the length of the compressed sound wave. Similarly, when the phones are moving apart, the tone is “diluted,” and thus a longer window may be employed.

To recover the autocorrelation peaks, a method is used to determine the autocorrelation using the appropriate offset between the recorded sound and the delayed sound. In some examples, this is accomplished by determining the autocorrelation using a window size that provides such an offset between the recorded sound and the delayed sound. As an example, in a “compressed” case, the peak can be “recovered” by calculating the autocorrelation on a window of size L/2−1, L/2−2, and so on rather than L/2. In the case of human movement not exceeding 2 m/s, a range of window sizes from L/2−3 to L/2+3, i.e. seven window sizes, recovers most errors due to the Doppler effect. Thus, to provide the maximum likelihood of detecting every tone, a parallel autocorrelator may calculate the autocorrelation for each of the seven window sizes at each time slot. However, while calculating seven autocorrelations for each time slot does provide a greater detection ratio, it also creates a large increase in the computation complexity of the autocorrelator.

FIG. 7illustrates a particular implementation of a more efficient parallel autocorrelator700which compensates for Doppler effects, specifically a prediction based parallel autocorrelator. The parallel autocorrelator700reduces the computational complexity and delay by predicting which of the autocorrelators will be used based on recent changes in the distance between the two devices over time, or based on the current relative speed of the devices. In the implementation shown inFIG. 7, the parallel autocorrelator700includes a Doppler prediction module702, an L/2 autocorrelator704, an L/2+1 autocorrelator706, an L/2+2 autocorrelator708, an L/2−1 autocorrelator710, an L/2−2 autocorrelator712, and a peak collector714. In some examples, the parallel autocorrelator700may include additional autocorrelators, such as autocorrelators with L/2+3 and L/2−3 window sizes and so on.

In operation, the Doppler prediction module702receives the recorded sound stream130and distance history716. From the distance history716, the Doppler prediction module702predicts the linear speed of the devices relative to one another and therefrom determines whether the sound waves of recorded tones will be compressed or diluted. For example, the Doppler prediction module702could estimate the linear speed of the second device104relative to the first device102based on recent changes in the distance between the devices. If the Doppler prediction module702determines that the devices are likely moving away from one another, the Doppler prediction module702outputs a diluted activator718which activates the L/2+1 autocorrelator706and L/2+2 autocorrelator708. On the other hand, if the Doppler prediction module702determines that the devices are likely moving towards one another, the Doppler prediction module702outputs a compressed activator720which activates the L/2−1 autocorrelator710and L/2−2 autocorrelator712. Depending on whether the diluted activator718or the compressed activator720is output, Doppler prediction module702proceeds to provide the recorded sound stream130to the activated autocorrelators. Alternatively, the recorded sound stream130could be provided to all the autocorrelators with only the activated autocorrelators using the provided recorded sound stream130.

During operation, the L/2 autocorrelator704and the two activated autocorrelators perform autocorrelation on the recorded sound stream130and if a peak is detected, outputs a parallel autocorrelator peak722to the peak collector714. Upon receiving the parallel autocorrelator peak722, the peak collector714outputs the autocorrelation peak132as described above with reference toFIG. 1. In some implementations, the information about which autocorrelator found the parallel autocorrelator peak722could be included in the information provided to the cross correlation module124and the cross correlation module124may adapt its operation to take the Doppler effect into account in a manner similar to that described above, such as by using a compressed version of the reference copy of the tone for cross correlation when the autocorrelation peak was detected by the L/2−1 autocorrelator710or the L/2−2 autocorrelator712.

In addition, although the Doppler prediction module described herein may decide only between “diluted” autocorrelators and “compressed” autocorrelators, implementations are not limited to this particular configuration and other configurations would be apparent to one of ordinary skill in the art in view of the disclosure provided herein.

While several examples have been illustrated herein for discussion purposes, numerous other configurations may be used and thus implementations herein are not limited to any particular configuration or arrangement. Some implementations may include an ambient noise and/or multipath filter to mitigate environmental noise such as from shouting, talking and crowd noise as well as to reduce false correlations or interference from multipath effects. In short, low and high pass filters could be used to reduce environmental effects. Each of these environmental factors is common during operation. Additionally, smoothing operations could be performed on the autocorrelation202in order to limit issues such as multiple peaks surrounding the locations of the actual peak. Another variation could involve the partial or complete overlap of tone A114and tone B116in time. Such an implementation may use a variety of adaptations based on the physical properties of sound to minimize the interference of the tones and adaptations of the ranging module112to allow correlation operations to still be performed. Adaptations based on the physical properties of sound could include but are not limited to using separate frequencies and selecting the pseudorandom sequences of the tones specifically to minimize interference in the correlation operations that could be caused by overlapping of the tones. Depending on the adaptations of the physical properties of the tones, various adaptations of the ranging module112could be implicated. For example, it might be helpful to use dedicated autocorrelation modules or dedicated cross correlation modules for each of tone A114and tone B116in situations in which the frequencies are different. Even in cases where the autocorrelation module122can detect each tone despite a partial overlap with the other tone, for faster detection of the cross correlation peaks, a dedicated cross correlation module could be included for each of the tones.

As previously stated, while several examples have been illustrated herein for discussion purposes, numerous other configurations may be used and thus implementations herein are not limited to any particular configuration or arrangement. For example, the discussion herein refers to signals being output and received by particular components or modules system. This should not be taken as a limitation as such communication need not be direct and the particular components or module need not necessarily be a single functional unit. For example, the measurement exchange module126and the distance calculation module128are discussed as separate logical components of the system which carry out separate step functions and communicate with each other. This is not to be taken as limiting implementations to only those in which the modules directly send and receive signals to and from one another. The signals could instead be relayed by a separate module upon receipt of the signal. Further, the modules may be combined or the functionality may be separated amongst modules in various manners not limited to those discussed above. Moreover, while specific equations have been provided as examples, implementations are not limited to these specific equations but may instead use other similar calculations. Other variations in the logical and practical structure and framework of various implementations would be apparent to one of ordinary skill in the art in view of the disclosure provided herein.

The processes described herein are only examples provided for discussion purposes. Numerous other variations will be apparent to those of skill in the art in light of the disclosure herein. Further, while the disclosure herein sets forth several examples of suitable frameworks, architectures and environments for executing the techniques and processes herein, implementations herein are not limited to the particular examples shown and discussed. The processes illustrated herein are shown as a collection of operations in a logical flow graph, which represents a sequence of operations, some or all of which can be implemented in hardware, software or a combination thereof. In the context of software, the blocks represent computer-executable instructions stored on one or more computer-readable media that, when executed by one or more processors, perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures and the like that perform particular functions or implement particular abstract data types. The order in which the operations are described is not intended to be construed as a limitation. Any number of the described blocks can be combined in any order and/or in parallel to implement the process, and not all of the blocks need be executed.

Example Computing Device and Environment

FIG. 8illustrates an example configuration of a computing device800and an environment that can be used to implement the modules and functions described herein. The computing device800may include at least one processor802, a memory804, communication interfaces806, a display device808(e.g. a touchscreen display or other display), other input/output (I/O) devices810(e.g. a touchscreen display or a mouse and keyboard), and one or more mass storage devices812, able to communicate with each other, such as via a system bus814or other suitable connection.

The processor802may be a single processing unit or a number of processing units, all of which may include single or multiple computing units or multiple cores. The processor802can be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor802can be configured to fetch and execute computer-readable instructions stored in the memory804, mass storage devices812, or other computer-readable media.

Memory804and mass storage devices812are examples of computer storage media for storing instructions which are executed by the processor802to perform the various functions described above. For example, memory804may generally include both volatile memory and non-volatile memory (e.g., RAM, ROM, or the like). Further, mass storage devices812may generally include hard disk drives, solid-state drives, removable media, including external and removable drives, memory cards, flash memory, floppy disks, optical disks (e.g., CD, DVD), a storage array, a network attached storage, a storage area network, or the like. Both memory804and mass storage devices812may be collectively referred to as memory or computer storage media herein, and may be capable of storing computer-readable, processor-executable program instructions as computer program code that can be executed by the processor802as a particular machine configured for carrying out the operations and functions described in the implementations herein.

The computing device800may also include one or more communication interfaces806for exchanging data with other devices, such as via a network, direct connection, or the like, as discussed above. The communication interfaces806can facilitate communications within a wide variety of networks and protocol types, including wired networks (e.g., LAN, cable, etc.) and wireless networks (e.g., WLAN, cellular, satellite, etc.), the Internet and the like. Communication interfaces806can also provide communication with external storage (not shown), such as in a storage array, network attached storage, storage area network, or the like.

A display device808, such as a touchscreen display or other display device, may be included in some implementations. Other I/O devices810may be devices that receive various inputs from a user and provide various outputs to the user, and may include a touchscreen, a keyboard, a remote controller, a mouse, a printer, audio and/or voice input/output devices, and so forth.

Memory804may include modules and components for the computing device800according to the implementations discussed herein. In the illustrated example, memory804includes the ranging module112of the first device102which includes the playback module118, the recording module120, the autocorrelation module122, the cross correlation module124, the measurement exchange module126, and the distance calculation module128as described above that afford the functionality described herein that can provide fast and accurate distance measurements between computing devices. Memory804may further include one or more other modules816, such as an operating system, drivers, application software, communication software, or the like. Memory804may also include other data818, such as data stored while performing the functions described above and data used by the other modules816. Memory804may also include other data and data structures described or alluded to herein. For example, memory804may store the reference copies of tone A114and tone B116in cases where these tones are predetermined.

Although illustrated inFIG. 8as being stored in memory804of computing device800, the ranging module112, or portions thereof, may be implemented using any form of computer-readable media that is accessible by computing device800. As used herein, “computer-readable media” includes, at least, two types of computer-readable media, namely computer storage media and communications media.

In contrast, communication media may embody computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave, or other transmission mechanism. As defined herein, computer storage media does not include communication media.

Further, although the ranging module112is illustrated inFIG. 8as being stored in memory804of computing device800, in other implementations, the ranging module112, or portions thereof, may be implemented as an application specific integrated circuit (ASIC) or other form of special purpose computing device and integrated with the other hardware and software components of computing device800.

CONCLUSION

Although the subject matter has been described in language specific to structural features and/or methodological acts, the subject matter defined in the appended claims is not limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims. This disclosure is intended to cover any and all adaptations or variations of the disclosed implementations, and the following claims should not be construed to be limited to the specific implementations disclosed in the specification. Instead, the scope of this document is to be determined entirely by the following claims, along with the full range of equivalents to which such claims are entitled.