Positioning using audio recognition

• US 9,435,878 B1
• Filed: 09/17/2014
• Issued: 09/06/2016
• Est. Priority Date: 07/19/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sharifi, Matthew
• Primary Examiner(s): Smith, Creighton
• Application Number:
  US14/488,858
• Time in Patent Office: 720 Days
• Field of Search: 700/94, 704/251
• US Class Current: 1/1
• CPC Class Codes: G01S 5/24 Position of single direction-finder fixed by determining direction of a plurality of spaced sources of known location
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G10L 25/48 specially adapted for particular use

Abstract

Systems and methods for determining location based on audio fingerprinting are disclosed. An extraction component extracts a set of interest points from an audio signal associated with an audio announcement. Then a matching component determines if the extracted set of interest points matches a set of interest points representative of an audio fingerprint in a data store comprising audio fingerprints. In an aspect, the audio fingerprints in the audio fingerprint data store represent announcements for underground transportation systems. A location component further determines location information associated with the audio fingerprint based in part on the set of extracted interest points matching the set of audio interest points representative of the audio fingerprint in the data store.

Claims

1. A device, comprising:

a memory having stored thereon computer executable components; and

a processor configured to execute the following computer executable components stored in the memory;

an indexing component configured to receive reference audio fingerprints and metadata respectively associated with the reference audio fingerprints, wherein the reference audio fingerprints respectively correspond audio announcements and the metadata is respectively related to the audio announcements;

an extraction component configured to extract interest points from an audio signal in response to detection of the audio signal by the device and compute audio fingerprints based on the interest points; and

a matching component configured to render metadata associated with one of the reference audio fingerprints in response to a determination that one of the audio fingerprint matches the one of the reference audio fingerprints.

2. The device of claim 1, wherein the metadata respectively associated with the reference audio fingerprints comprises location information corresponding to respective locations at which the audio announcements are played.

3. The device of claim 2, further comprising a location component configured to determine a location of the device based on the metadata associated with the one of the reference audio fingerprints.

4. The device of claim 1, wherein the extraction component is configured to group the interest points into subsets of the interest points based on association with respective fixed, consecutive and overlapping windows of time over the duration of the audio signal, and compute the audio fingerprints for respective subsets of the interest points.

5. The device of claim 1, wherein the reference audio fingerprints respectively correspond to sets of reference interest points taken from respective audio samples of the audio announcements, wherein the reference interests points respectively comprise a frequency component and a time component, and wherein the indexing component is configured to generate an inverted index for the reference audio fingerprints that maps a frequency component for a reference interest point to an identifier for a reference audio fingerprint and a time component for the reference interest point.

6. The device of claim 5, wherein the matching component is configured to employ the inverted index to match the audio fingerprints to the reference audio fingerprints.

7. The device of claim 1, further comprising:

a navigation component configured to select the reference audio fingerprints for downloading to the device based on a location of the device.

8. The device of claim 7, wherein the navigation component is further configured to select the reference audio fingerprints for downloading to the device based on historical travel patterns of the device.

9. The device of claim 1, further comprising:

an analysis component configured to determine a transportation system expected to be accessed by a user of the device in the future based on at least one of;

a location of the device, historical travel patterns of the user, or a schedule of the user; and

a navigation component configured to select the reference audio fingerprints for downloading to the device based on the transportation system, wherein the audio announcements correspond to a set of audio announcements for the transportation system.

10. The device of claim 1, wherein the metadata respectively associated with the reference audio fingerprints comprises feature data corresponding to information about respective locations at which the audio announcements are played, including at least one of:

physical structures at or near the respective locations, mechanisms for navigating about the respective locations, or characteristics of a transportation system providing transit to and from the respective locations.

11. The device of claim 10, further comprising an analysis component configured to infer at least one of:

a direction a user of the device is traveling, a mechanism or characteristic of the mechanism via which the user is traveling, or a travel plan of the user, based on metadata associated with two or more two or more reference audio fingerprints corresponding to two or more audio fingerprints consecutively detected in audio signals by detection component.

12. A method comprising:

receiving, by a mobile device comprising a processor, reference audio fingerprints and metadata respectively associated with the reference audio fingerprints, wherein the reference audio fingerprints respectively correspond audio announcements and the metadata is respectively related to the audio announcements;

storing, by the mobile device, the reference audio fingerprints and the metadata in memory of the mobile device;

extracting, by the mobile device, interest points from an audio signal in response to detection of the audio signal by the mobile device;

determining audio fingerprints based on the interest points; and

rendering metadata associated with one of the reference audio fingerprints in response to a determination that one of the audio fingerprints matches the one of the reference audio fingerprints.

13. The method of claim 12, further comprising:

determining, by the mobile device, that a network connection is unavailable, wherein the extracting is responsive to the determining the that the network connection is unavailable.

14. The method of claim 12, wherein the metadata respectively associated with the reference audio fingerprints comprises location information corresponding to respective locations at which the audio announcements are played, the method further comprising:

determining, by the mobile device, a location of the mobile device based on the metadata associated with the one of the reference audio fingerprints.

15. The method of claim 12, wherein the determining the audio fingerprints comprises:

grouping the interest points into subsets of the interest points based on association with respective fixed, consecutive and overlapping windows of time over the duration of the audio signal; and

determining the audio fingerprints for respective subsets of the interest points.

16. The method of claim 12, wherein the reference audio fingerprints respectively correspond to sets of reference interest points taken from respective audio samples of the audio announcements, wherein the reference interests points respectively comprise a frequency component and a time component, the method further comprising:

generating, by the mobile device, an inverted index for the reference audio fingerprints that maps a frequency component for a reference interest point to an identifier for a reference audio fingerprint and a time component for the reference interest point; and

employing the inverted index to match the audio fingerprints to the reference audio fingerprints.

17. The method of claim 12, further comprising:

selecting, by the mobile device, the reference audio fingerprints for downloading to the mobile device based on a location of the mobile device.

18. A tangible computer-readable storage medium comprising computer-readable instructions that, in response to execution, cause a computing system to perform operations, comprising:

extracting interest points from an audio signal in response to detection of the audio signal by a device;

determining audio fingerprints based on the interest points;

comparing the audio fingerprints to reference audio fingerprints stored in memory of the device, wherein the reference audio fingerprints respectively correspond audio announcements and the reference audio fingerprints are respectively associated with metadata related to the audio announcements; and

rendering metadata associated with one of the reference audio fingerprints in response to a determination, based on the comparing, that one of the audio fingerprints matches the one of the reference audio fingerprints.

19. The tangible computer-readable storage medium of claim 18, wherein the metadata respectively associated with the reference audio fingerprints comprises location information corresponding to respective locations at which the audio announcements are played, the method further comprising:

determining, by the mobile device, a location of the mobile device based on the metadata associated with the one of the reference audio fingerprints.

20. The tangible computer-readable storage medium of claim 18, wherein the metadata respectively associated with the reference audio fingerprints comprises feature data corresponding to information about respective locations at which the audio announcements are played, including at least one of:

physical structures at or near the respective locations, mechanisms for navigating about the respective locations, or characteristics of a transportation system providing transit to and from the respective locations, wherein the operations further comprise;

identifying two or more audio fingerprints in consecutively detected in audio signals;

analyzing metadata associated with two or more two or more reference audio fingerprints corresponding to two or more audio fingerprints; and

inferring, based on the analyzing, at least one of;

a direction a user of the device is traveling, a mechanism or characteristic of the mechanism via which the user is traveling, or a travel plan of the user.