Lattice matching
First Claim
Patent Images
1. A method of searching a database comprising a plurality of information entries to identify stored image data to be retrieved therefrom, each of said plurality of information entries having an associated annotation lattice, the method comprising:
- using a user terminal to receive a query lattice representing an input query;
comparing the query lattice with each annotation lattice to provide a set of comparison results;
identifying stored image data to be retrieved from said database using the set of comparison results; and
displaying said stored image data retrieved from said database on a display of the user terminal;
wherein the query lattice and each annotation lattice define alternative label sequences that represent a sequential signal, and each lattice comprises a plurality of nodes each associated with one or more labels and representing a point in the sequential signal at which the associated label occurs,wherein the query lattice is compared with each annotation lattice by propagating a plurality of paths, each path representing a comparison between labels in the query lattice and labels in the annotation lattice, and each path having an associated accumulative value representing the closeness of the comparison,wherein during the path propagation, said comparing step defines, for each node in the query lattice, a plurality of associated storage areas in a memory, each storage area associated with a query lattice node also being associated with a respective node in the annotation lattice and being operable to store, during the path propagation, an accumulative value representing the closeness of the comparison between labels in the query lattice up to the associated query lattice node and labels in the annotation lattice up to the associated annotation lattice node,wherein said comparing step uses said storage areas during the propagation of said paths, andwherein when propagating a path from a source node in said query lattice to a destination node in said query lattice, said comparing step updates and propagates accumulative values stored in the storage areas associated with the source node to at least the storage areas associated with the destination node.
1 Assignment
0 Petitions
Accused Products
Abstract
A system is described for matching lattices such as phoneme lattices generated by an automatic speech recognition unit. The system can be used to retrieve files from a database by comparing a query lattice with annotation lattices associated with the data files that can be retrieved, and by retrieving the data files having an annotation lattice most similar to the query lattice.
17 Citations
31 Claims
-
1. A method of searching a database comprising a plurality of information entries to identify stored image data to be retrieved therefrom, each of said plurality of information entries having an associated annotation lattice, the method comprising:
-
using a user terminal to receive a query lattice representing an input query; comparing the query lattice with each annotation lattice to provide a set of comparison results; identifying stored image data to be retrieved from said database using the set of comparison results; and displaying said stored image data retrieved from said database on a display of the user terminal; wherein the query lattice and each annotation lattice define alternative label sequences that represent a sequential signal, and each lattice comprises a plurality of nodes each associated with one or more labels and representing a point in the sequential signal at which the associated label occurs, wherein the query lattice is compared with each annotation lattice by propagating a plurality of paths, each path representing a comparison between labels in the query lattice and labels in the annotation lattice, and each path having an associated accumulative value representing the closeness of the comparison, wherein during the path propagation, said comparing step defines, for each node in the query lattice, a plurality of associated storage areas in a memory, each storage area associated with a query lattice node also being associated with a respective node in the annotation lattice and being operable to store, during the path propagation, an accumulative value representing the closeness of the comparison between labels in the query lattice up to the associated query lattice node and labels in the annotation lattice up to the associated annotation lattice node, wherein said comparing step uses said storage areas during the propagation of said paths, and wherein when propagating a path from a source node in said query lattice to a destination node in said query lattice, said comparing step updates and propagates accumulative values stored in the storage areas associated with the source node to at least the storage areas associated with the destination node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 31)
-
-
11. A method of searching a database comprising a plurality of information entries to identify stored image data to be retrieved therefrom, each of said plurality of information entries having an associated annotation lattice, the method comprising:
-
using a user terminal to receive a query lattice representing an input query; comparing the query lattice with each annotation lattice to provide a set of comparison results; identifying stored image data to be retrieved from said database using the set of comparison results; and displaying said stored image data retrieved from said database on a display of the user terminal; wherein the query lattice and each annotation lattice define alternative label sequences that represent a sequential signal, and each lattice comprises a plurality of nodes each associated with one or more labels and representing a point in the sequential signal at which the associated label occurs, wherein the query lattice is compared with each annotation lattice by propagating a plurality of paths, each path representing a comparison between labels in the query lattice and labels in the annotation lattice, and each path having an associated accumulative value representing the closeness of the comparison, wherein during the path propagation, said comparing step defines, for each node in the query lattice, a plurality of associated storage areas in a memory, each storage area associated with a query lattice node also being associated with a respective node in the annotation lattice and being operable to store, during the path propagation, an accumulative value representing the closeness of the comparison between labels in the query lattice up to the associated query lattice node and labels in the annotation lattice up to the associated annotation lattice node, wherein said comparing step uses said storage areas during the propagation of said paths, wherein the method further comprises a processing step of processing accumulative values stored for a node to determine a similarity measure representing the similarity between the query and annotation lattices, and wherein the annotation lattice represents a longer sequence than the query lattice and wherein the processing step processes the accumulative values stored for the node to determine if the annotation lattice includes one or more portions similar to the query lattice. - View Dependent Claims (12, 13, 14)
-
-
15. An apparatus for searching a database comprising a plurality of information entries to identify stored image data to be retrieved therefrom, each of said plurality of information entries having an associated annotation lattice, the apparatus comprising:
-
a memory; a receiver operable to receive a query lattice representing an input query; a lattice comparison apparatus for comparing the query lattice with each annotation lattice to provide a set of comparison results; an identifier operable to identify stored image data to be retrieved from said database using the set of comparison results provided by the lattice comparison apparatus; and a display operable to display said stored image data identified by the identifier and retrieved from said database; wherein the query lattice and each annotation lattice define alternative label sequences that represent a sequential signal, and each lattice comprises a plurality of nodes each associated with one or more labels and representing a point in the sequential signal at which the associated label occurs, wherein the query lattice is compared with each annotation lattice by propagating a plurality of paths, each path representing a comparison between labels in the query lattice and labels in the annotation lattice, and each path having an associated accumulative value representing the closeness of the comparison, wherein during the path propagation, said lattice comparison apparatus is operable to define, for each node in the query lattice, a plurality of associated storage areas in said memory, each storage area associated with a query lattice node also being associated with a respective node in the annotation lattice and being operable to store, during the path propagation, an accumulative value representing the closeness of the comparison between labels in the query lattice up to the associated query lattice node and labels in the annotation lattice up to the associated annotation lattice node, wherein said lattice comparison apparatus is operable to use said storage areas during the propagation of said paths, wherein when propagating a path from a source node in said query lattice to a destination node in said query lattice, said lattice comparison apparatus is operable to update and to propagate accumulative values stored in the storage areas associated with the source node to at least the storage areas associated with the destination node. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
27. An apparatus for searching a database comprising a plurality of information entries to identify stored image data to be retrieved therefrom, each of said plurality of information entries having an associated annotation lattice, the apparatus comprising:
-
a memory; a receiver operable to receive a query lattice representing an input query; a lattice comparison apparatus for comparing the query lattice with each annotation lattice to provide a set of comparison results; an identifier operable to identify stored image data to be retrieved from said database using the set of comparison results provided by the lattice comparison apparatus; and a display operable to display said stored image data identified by the identifier and retrieved from said database; wherein the query lattice and each annotation lattice define alternative label sequences that represent a sequential signal, and each lattice comprises a plurality nodes each associated with one or more labels and representing a point in the sequential signal at which the associated label occurs, wherein the query lattice is compared with each annotation lattice by propagating a plurality of paths, each path representing a comparison between labels in the query lattice and labels in the annotation lattice, and each path having an associated accumulative value representing the closeness of the comparison, wherein during the path propagation, said lattice comparison apparatus is operable to define, for each node in the query lattice, a plurality of associated storage areas in said memory, each storage area associated with a query lattice node also being associated with a respective node in the annotation lattice and being operable to store, during the path propagation, an accumulative value representing the closeness of the comparison between labels in the query lattice up to the associated query lattice node and labels in the annotation lattice up to the associated annotation lattice node, wherein said lattice comparison apparatus is operable to use said storage areas during the propagation of said paths, wherein the apparatus further comprises a processor operable to process the accumulative values stored for a node to determine a similarity measure representing the similarity between the query and annotation lattices, and wherein the annotation lattice represents a longer sequence than the query lattice and wherein the processor is operable to process the accumulative values stored for the node to determine if the annotation lattice includes one or more portions similar to the query lattice. - View Dependent Claims (28, 29, 30)
-
Specification