Multi-representational data structure for recognition in computer systems

• US 5,749,070 A
• Filed: 04/04/1997
• Issued: 05/05/1998
• Est. Priority Date: 09/09/1993
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Gourdol, Arnaud P. J.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Dorvil, Richemond
• Application Number:
  US08/833,309
• Time in Patent Office: 396 Days
• Field of Search: 395/2.56, 395/2.51, 395/2.4, 704/231, 704/242, 704/245, 704/250, 704/200
• US Class Current: 704/242
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries

Abstract

An improved recognition data structure is described that is particularly well suited for use in a computer system having recognition abilities. The data structure includes a multi-representational data list section arranged to store a multiplicity of datum. Each datum includes a datum reference number that uniquely identifies that datum and is arranged to contain a plurality of representation zones. Each representation zone is arranged to hold data indicative of a particular representation of the data stored in the datum. The data structure also includes a trellis based recognition results section arranged to accommodate trellis based recognition results at a plurality of different trellis levels.

Claims

1. A computer-readable media having a recognition data structure suitable for use in a computer system having recognition abilities, the data structure comprising:

a multi-representational data list section arranged to store a multiplicity of datum, wherein each datum includes a datum reference number that uniquely identifies that datum, and is arranged to contain a plurality of representation zones, each representation zone being arranged to hold data indicative of a particular representation of the data stored in the datum, wherein said multiplicity of datum represents information relating to speech or stroke inputs provided to said computer system and available for recognition use by said computer system via said recognition abilities; and

a recognition results section arranged to accommodate recognition results at a plurality of different levels, wherein said recognition results are generated and provided by said recognition abilities within said computer system following recognition of said multiplicity of datum.

2. A computer-readable media having a recognition data structure as recited in claim 1 wherein the recognition results section is a trellis based recognition results structure that includes an array which identifies each link in the trellis and a label applied to that link.

3. A computer-readable media having a recognition data structure as recited in claim 2 wherein the trellis based recognition results structure further includes a second array which identifies each node in the trellis and a label applied to that node.

4. A computer-readable media having a recognition data structure as recited in claim 2 wherein the array further has storage space to identify the probability of each link being correct.

5. A computer-readable media having a recognition data structure as recited in claim 1 wherein the recognition results section is a trellis based recognition results structure that includes an array which identifies each node in the trellis and a label applied to that node.

6. A computer-readable media having a recognition data structure as recited in claim 1 wherein each datum represents a written stroke.

7. A computer-readable media having a recognition data structure as recited in claim 1 wherein each datum represents a speech utterance.

8. A computer-readable media having a recognition data structure as recited in claim 1 wherein one of the levels represents recognition on a character level.

9. A computer-readable media having a recognition data structure as recited in claim 1 wherein one of the levels represents recognition on a word level.

10. A computer-readable media having a recognition data structure as recited in claim 1 wherein one of the levels represents recognition on a sentence level.

11. A computer-readable media having a recognition data structure as recited in claim 1 wherein each zone includes an indicia identifying the format of the data stored in its associated zone and an indicia indicative of the amount of memory used to store the associated representation.

12. A computer-readable media having a recognition data structure as recited in claim 1 wherein the datum reference numbers are assigned sequentially.

13. A computer-readable media having a recognition data structure as recited in claim 1 wherein the data representations include:

a representation of a stroke in Cartesian coordinates; and

a representation of the bounding box of the stroke.

14. A computer-readable media having a recognition data structure as recited in claim 13 wherein the Cartesian coordinates representation of the stroke are represented as an array of raw digitizer coordinates.

15. (Once Amended) A computer-readable media having a recognition data structure as recited in claim 13 wherein the Cartesian coordinates representation of the stroke are represented as an array of filtered digitizer coordinates.

16. A computer-readable media having a recognition data structure as recited in claim 1 wherein the data structure is arranged to pass recognition information back and forth between an application program, an operating system and a recognition engine.

17. A computer-readable media having a recognition data structure as recited in claim 1 further comprising a seed value arranged to be uniquely altered each time that a datum is added to or removed from the data list.

18. A computer-readable media having a recognition data structure as recited in claim 17 wherein the seed number is arranged to be incremented each time that data is added to or removed from the data list.

19. A computer-readable media having a recognition data structure as recited in claim 1 wherein:

the recognition results section is a trellis based recognition results structure that includes an array which identifies each information carrying component of a trellis and a label applied to that information carrying component; and

each row in the array includes a label which takes the form of a pointer that points to a block in memory that stores a block of information that labels the information carrying component that defines the associated row.

20. A computer-readable media having a recognition data structure suitable for use in a computcr system that is arranged to pass recognition information back and forth between an application program, an operating system and a recognition engine, the data structure comprising:

a multi-representational data list section arranged within said computer-readable media to store a multiplicity of datum, wherein each datum includes a datum reference number that uniquely identifies that datum, and is arranged to contain a plurality of representation zones, each representation zone being arranged to hold data indicative of a particular representation of the data stored in the datum, an indicia identifying the format of the data stored in its associated zone and an indicia indicative of the amount of memory used to store the associated representation, wherein said multiplicity of datum represents information relating to speech or stroke inputs that are available for use by said recognition engine; and

a trellis based recognition results section arranged within said computer-readable media to contain a plurality of arrays, each array corresponding to a different trellis level and including a representation of each link or node of its associated trellis level, a label applied to the represented link or node, and an indication of the probability that the represented link or node is correct, said plurality of arrays being generated by said recognition engine following recognition of said multiplicity of datum.

21. A computer-readable media having a recognition data structure as recited in claim 20 wherein a first level of the trellis represents recognition on a character level and a second level of the trellis represents recognition on a word level.

22. A computer-readable media having a recognition data structure as recited in claim 20 further comprising a seed value arranged to be uniquely altered each time that a datum is added to or removed from the data list.