Spatially indexed grammar and methods of use

• US 8,060,367 B2
• Filed: 06/26/2007
• Issued: 11/15/2011
• Est. Priority Date: 06/26/2007
• Status: Active Grant

• Current Assignee: NeuStar Information Services, Inc. (Neustar Incorporated)
• Original Assignee: Targus Information Corporation (Neustar Incorporated)
• Inventors: Keaveney, John F.
• Primary Examiner(s): JACKSON, JAKIEDA R
• Application Number:
  US11/768,433
• Publication Number:
  US 20090006077A1
• Time in Patent Office: 1,603 Days
• Field of Search: 704/247, 704/9
• US Class Current: 704/247
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G10L 15/19 Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules
• CPC Class Codes: G10L 2015/228 of application context

Abstract

Improved systems and methods are described which simplify the individual'"'"'s interaction with speech recognition software, expand the database of spoken point names that can be recognized, and increase the quality and therefore likelihood of success of speech recognition applications. The present systems and methods apply to various uses, such as providing driving directions, finding the nearest location based service, and finding the nearest “Where Am I?” type of location based services.

Claims

1. A non-transitory computer readable medium having stored thereon one or more sequences of instructions for causing one or more processors to perform the steps for speech recognition using tiles, each tile defines an area on the surface of the earth and the defined area is a more or less symmetrical shape defined by a coordinate system and can have a spatially proximate relationship to other tiles, a grammar is associated with each tile and is derived from feature names of first level identifiers in the area defined by the tile and, each first level identifier corresponds to a point on the surface of the earth, the steps comprising:

identifying a candidate area location;

choosing an initial tile based on the candidate area location;

comparing an utterance of a first level identifier against a first grammar associated with the initial tile to determine if the utterance corresponds to a feature from which the first grammar was derived, wherein the grammar comprises an audio file associated with each of the feature names of the first level identifiers associated with the tile, and wherein the utterance corresponds to a feature from which the first grammar was derived if the utterance matches an audio file associated with the first grammar;

if the utterance does not correspond to a feature in the first grammar,

determining a plurality of second tiles; and

comparing the utterance of the first level identifier against the plurality of grammars associated with the plurality of second tiles to determine if the utterance corresponds to a feature from which the plurality of grammars was derived; and

determining a point coordinate associated with the feature which matches the utterance.

2. The computer readable medium of claim 1, wherein the step of identifying a candidate area location further comprises:

prompting an individual for the candidate area location; and

receiving an utterance from the individual of the candidate area location.

3. The computer readable medium of claim 1 wherein the step of identifying a candidate area location further comprises determining a latitude and a longitude from a device associated with an individual.

4. The computer readable medium of claim 1 wherein the step of identifying a candidate area location further comprises determining a location of a communication infrastructure associated with an individual.

5. The computer readable medium of claim 1, wherein the first level identifier includes one or more of a street address, an intersection, or a landmark.

6. The computer readable medium of claim 1 wherein the initial tile and the plurality of second tiles are substantially rectangular geographic regions.

7. The computer readable medium of claim 1 further comprising providing the point coordinate to a location based service.

8. The computer readable medium of claim 1 wherein the step of choosing an initial tile further comprises selecting the initial tile to be substantially centered within the candidate area location.

9. The computer readable medium of claim 1 wherein the step of choosing an initial tile further comprises:

determining a latitude and a longitude associated with the candidate area location;

converting the latitude and the longitude to a tile code by interleaving a first digit of the latitude with a first digit of the longitude, interleaving a second digit of the latitude with a second digit of the longitude, interleaving a third digit of the latitude with a third digit of the longitude, and adding a fourth digit of the latitude;

using the tile code as an index to select the initial tile.

10. The computer readable medium of claim 1 wherein the step of identifying a candidate area location further comprises:

prompting an individual for an utterance of a general location;

receiving the utterance of the general location;

identifying the general location by comparing the utterance of the general location to a first grammar;

selecting a second grammar such that the second grammar contains features that are located geographically within the general location;

prompting an individual for an utterance of a specific location;

receiving the utterance of the specific location; and

identifying the specific location by comparing the utterance of the specific location to the second grammar.

11. The computer readable medium of claim 1 wherein the plurality of second tiles are substantially surrounding the initial tile.

12. The computer readable medium of claim 1 wherein the step of determining a plurality of second tiles further comprises removing a duplicate feature from the plurality of second grammars.

13. A computerized system for generating a spatially indexed grammar associated with place names, the computerized system comprising:

a processor;

a memory coupled to the processor;

a tile-code generation module which partitions a geographical area into a plurality of finite non-overlapping regions and assigns an index to each of the finite regions, the index configured to be determined using a coordinate system by interleaving a first digit of a horizontal coordinate associated with one of the finite regions with a first digit of a vertical coordinate associated with one of the finite regions, interleaving a second digit of the horizontal coordinate with a second digit of the vertical coordinate, interleaving a third digit of the horizontal coordinate with a third digit of the vertical coordinate, and adding a fourth digit of the horizontal coordinate;

a feature generation module which classifies a number of points on each of the place names within each of the finite regions, each of the points comprising names of first level identifiers in an area defined by the finite regions;

a sorting and de-duping module which sorts the place names associated with the place names in each of the finite regions and removes one or more duplicate points within each of the finite regions; and

a tile file generation module which generates a list of features and associated speech recognition grammars for at least a first and a second of the finite regions, after the features are sorted and the duplicate features are removed from the first and the second of the finite regions.

14. The system of claim 13 wherein the coordinate system is a latitude and a longitude coordinate system.

15. The system of claim 13 wherein the coordinate system is V and H coordinate system.

16. The system of claim 13 wherein the index is determined by interleaving a first and second characteristic of the coordinate system.

17. The system of claim 13 wherein the index is a 7-byte tile code.

18. A method for matching a spoken location description with data associated with a feature that exists geographically within the coordinate location on the surface of the earth, the method comprising:

determining a coordinate associated with a specific location;

using one or more processors to choose an initial tile and a first grammar associated with the initial tile, the initial tile being substantially centered around the coordinate and defining an area on the surface of the earth and the defined area is a more or less symmetrical shape defined by a coordinate system and can have a spatially proximate relationship to other tiles, the grammar being associated with the initial tile and being derived from feature names of first level identifiers in the area defined by the initial tile and each first level identifier corresponding to a point on the surface of the earth;

obtaining a spoken language description of a point within the specific location;

using one or more processors to compare the point with the data associated with the feature, wherein the first grammar comprises an audio file associated with each of the feature names of the first level identifiers associated with the tile, and wherein the utterance corresponds to a feature from which the first grammar was derived if the spoken language description matches an audio file associated with the first grammar;

querying a geocoding module with text associated with the feature, the text associated with the feature comprises a text representation of the audio file that matched the spoken language description; and

providing information associated with the feature.

19. The method of claim 18, wherein the point includes one or more of a street address, an intersection, or a landmark.

20. The method of claim 18 wherein the initial tile is a substantially symmetrical region.

21. The method of claim 18 further comprising providing the information to a location based service.

22. The method of claim 18 wherein the step of choosing an initial tile further comprises:

determining a latitude and a longitude associated with the coordinate; and

selecting the initial tile such that a tile code associated with the initial tile corresponds to the latitude and the longitude.

23. The method of claim 18 further comprising:

identifying a general location; and

obtaining a spoken language description of the specific location within the general location.

24. The method of claim 23, wherein the step of identifying a general location further comprises:

prompting an individual for the general location; and

receiving an utterance from the individual of the general location.

25. The method of claim 23 wherein the step of identifying a general location further comprises determining a latitude and a longitude from a device associated with an individual.

26. The method of claim 23 wherein the step of identifying a general ideation further comprises determining a location of a communication infrastructure associated with an individual.

27. The method of claim 23 wherein the step of identifying a general location further comprises obtaining a city, a state, or a county associated with a user.

28. The method of claim 23 wherein the step of obtaining a spoken language description of a specific location further comprises obtaining a spoken language description of a city.

29. A spatially indexed grammar apparatus comprising:

a place grammar to output a candidate area location associated with a wireless device;

a point coordinate database to output a point coordinate associated with the candidate area location;

an initial tile from a set of tiles, each tile representing a finite non-overlapping region, the initial tile having an associated speech recognition grammar, the initial tile having a relationship to the point coordinate;

a plurality of additional tiles associated with the grammar, the plurality of additional tiles having a spatially proximate relationship to the initial tile;

a voice response system configured to match an utterance to a feature in the speech recognition grammar; and

a geocoding module to receive a text-based representation of a feature from the grammar, the feature matching a spoken location description of a first level identifier from a user.

30. The apparatus of claim 29 wherein the place grammar is derived from a U.S. Geographic Information Service State &

Topical Gazetteer file.

31. The apparatus of claim 29 wherein the place grammar contains place names, including a state, a city and a neighborhood.

32. The apparatus of claim 29 wherein the point coordinate comprises a latitude and a longitude.

33. The apparatus of claim 29 wherein the point coordinate comprises a V and H coordinate.

34. The apparatus of claim 29 wherein the grammar comprises a first grammar associated with the initial tile and a second grammar associated with the plurality of additional tiles.

35. The apparatus of claim 29 wherein the first level identifier comprises a street address, an intersection, or a landmark.

36. A method for speech recognition using tiles, each tile defines an area on the surface of the earth and the defined area is a more or less symmetrical shape defined by a coordinate system and can have a spatially proximate relationship to other tiles, the method comprising:

one or more processors using a place grammar to output a candidate area location associated with a wireless device;

one or more processors using a point coordinate database to output a point coordinate associated with the candidate area location;

choosing an initial tile from a set of tiles, the initial tile having an associated first speech recognition grammar, the initial tile having a relationship to the point coordinate;

choosing a plurality of additional tiles, the plurality of additional tiles having a spatially proximate relationship to the initial tile, and an associated second speech recognition grammar; and

providing a text-based representation of a feature from the first or the second grammar to a geocoding module, the feature matching a spoken location description of a first level identifier from a user, wherein the spoken location description matches an audio file associated with a feature name from the first or the second grammar.

37. The method of claim 36 wherein the step of using a place grammar to output a candidate area location further comprises:

prompting an individual for the candidate area location;

receiving an utterance from the individual of the general location; and

comparing the utterance against the place grammar.

38. A method for speech recognition using tiles, each tile defines an area on the surface of the earth and the defined area is a more or less symmetrical shape defined by a coordinate system and can have a spatially proximate relationship to other tiles, a grammar is associated with each tile and is derived from feature names of first level identifiers in the area defined by the tile and, each first level identifier corresponds to a point on the surface of the earth, the method comprising:

prompting a user for a general location;

capturing a first utterance from the user;

matching the first utterance against a place grammar to determine if the first utterance corresponds to a first feature from which the place grammar was derived, wherein the place grammar comprises an audio file associated with features that fall within the area defined by the tile;

prompting a user for a specific location;

capturing a second utterance from the user;

selecting a portion of the place grammar such that the portion of the place grammar contains feature names of first level identifiers that exist geographically within the geographic area associated with the first feature;

matching the second utterance against the portion of the place grammar to determine if the second utterance corresponds to a second feature from which the portion of the place grammar was derived;

determining a coordinate location associated with the second feature;

using the coordinate location as a basis for an index into a spatially indexed grammar;

selecting an initial tile using the index;

prompting the user for a point;

capturing a third utterance from the user;

matching the third utterance against a grammar associated with the initial tile to determine if the third utterance corresponds to a third feature from which the grammar associated with the initial tile was derived;

if the third utterance does not correspond to the third feature determining a plurality of second tiles and comparing the third utterance against a plurality of grammars associated with the plurality of second tiles to determine if the third utterance corresponds to a fourth feature from which the plurality of grammars was derived;

sending a text-based representation of the point to a geocoding module; and

playing back information from the geocoding module associated with the text-based representation of the point.

39. A method for speech recognition using tiles, each tile defines an area on the surface of the earth and the defined area is a more or less symmetrical shape defined by a coordinate system and can have a spatially proximate relationship to other tiles, a grammar is associated with each tile and is derived from feature names of first level identifiers in the area defined by the tile and, each first level identifier corresponds to a point on the surface of the earth, the method comprising:

using a general and a specific location to obtain an initial tile;

sending a grammar associated with the initial tile to speech recognition software of an interactive voice response system, wherein the place grammar comprises an audio file associated with features that fall within the area defined by the tile;

matching a spoken utterance of a first level identifier with a feature in the grammar;

determining if the spoken utterance matches the feature;

if the spoken utterance does not correspond to the feature determining a plurality of second tiles and comparing the spoken utterance against a plurality of grammars associated with the plurality of second tiles to determine if the spoken utterance corresponds to a feature from which the plurality of grammars was derived;

sending a text representation of the feature to a geocoding module to determine coordinates for a point matching the spoken utterance; and

providing the coordinates for the point to a location based service.