Quantized feature index trajectory

• US 7,945,441 B2
• Filed: 08/07/2007
• Issued: 05/17/2011
• Est. Priority Date: 08/07/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mukerjee, Kunal, Thompson, R. Donald
• Primary Examiner(s): AZAD, ABUL K
• Application Number:
  US11/835,389
• Publication Number:
  US 20090043575A1
• Time in Patent Office: 1,379 Days
• Field of Search: 704/222, 704/230
• US Class Current: 704/222
• CPC Class Codes: G10L 15/02 Feature extraction for speech recognition; Selection of recognition unit
• CPC Class Codes: G10L 19/0018 Speech coding using phonetic or linguistical decoding of the source; Reconstruction using text-to-speech synthesis
• CPC Class Codes: G10L 2015/025 Phonemes, fenemes or fenones being the recognition units

Abstract

Indexing methods are described that may be used by databases, search engines, query and retrieval systems, context sensitive data mining, context mapping, language identification, image recognition, and robotic systems. Raw baseline features from an input signal are aggregated, abstracted and indexed for later retrieval or manipulation. The feature index is the quantization number for the underlying features that are represented by an abstraction. Trajectories are used to signify how the features evolve over time. Features indexes are linked in an ordered sequence indicative of time quanta, where the sequence represents the underlying input signal. An example indexing system based on the described processes is an inverted index that creates a mapping from features or atoms to the underlying documents, files, or data. A highly optimized set of operations can be used to manipulate the quantized feature indexes, where the operations can be fine tuned independent from the base feature set.

Claims

1. A portable electronic device that device that is arranged to manage time domain data with a quantized feature index trajectory methodology, the portable electronic device comprising:

a feature quantizer block that is arranged to convert the time domain data into a stream of feature indexes;

a buffer block that is arranged to store the time domain data and also store at least a portion of the stream of feature indexes as buffered feature indexes, wherein the buffered feature indexes are associated with the time domain data;

a QFIT processing block that is arranged to process the buffered feature indexes and the time domain data by;

associating each buffered feature index with a respective time index relative to the corresponding time domain data;

linking each buffered feature index together in a feature trail such that each buffered feature index in the feature trail is linked to a preceding buffered feature index that has an earlier time index; and

generating a feature vector that is associated with the time domain data and the feature trail; and

updating indexes for searching and retrieval operations such that the feature vector operates as an index for the time domain data.

2. The portable electronic device of claim 1, wherein each feature index is either a numerical index or a symbolic name that is mapped to a characteristic feature of the time domain data.

3. The portable electronic device of claim 1, wherein each feature index is a numerical index that is mapped to one member of a group of acoustic phonemes that represent human speech.

4. The portable electronic device of claim 1, further comprising a front end processor that is arranged to capture one or more time domain signals and generate a frame of time domain data for the feature quantizer.

5. The portable electronic device of claim 1, the feature quantizer block comprising a feature extractor block and a feature indexer block, wherein the feature extractor block is arranged to generate frequency domain data in response to the time domain data, and wherein the feature indexer block is arranged to generate the stream of feature indexes in response to the frequency domain data.

6. The portable electronic device of claim 4, the feature indexer comprising a classifier block and a feature normalization model, wherein the classifier block is arranged to compare the frequency domain data to the feature normalization model to identify an appropriate feature index for each portion of the frequency domain data.

7. The portable electronic device of claim 1, wherein the QFIT processing block is further arranged for generating a multi-resolution mapping between feature vectors and feature vectors such that different feature indexes are mapped to the feature vectors based on a specified resolution level for the QFIT processing block.

8. The portable electronic device of claim 1, wherein the QFIT processing block is further arranged to retrieve previously indexed time domain data from a feature trail for a query by:

comparing the feature trail for the query to known feature trails, identifying a best match for the comparison, and retrieving the previously indexed time domain data that corresponds to the identified best match.

9. The portable electronic device of claim 1, wherein the QFIT processing block is further arranged to retrieve previously indexed time domain data from a feature trail for a query by:

comparing the feature trail for the query to known feature trails at each specified resolution, identifying a best match for the comparison at each of the specified resolutions, adding matches to histogram bins for each match, and retrieving the previously indexed time domain data that corresponds to the identified best match as determined from the histogram bins.

10. The portable electronic device of claim 1, wherein the QFIT processing block is further arranged to remove a previously stored feature from an identified feature trail by:

selecting the previously stored feature from the identified feature trail, evaluating a frequency of use for the selected feature, and removing the selected feature and updating the links to other features from the identified feature trail when the frequency of use for the selected feature exceeds a threshold.

11. A computer implemented method for managing time domain data with a quantized feature index trajectory methodology, the method comprising:

segmenting a frame of time domain data into time windows;

quantizing features for each time window segment such that each time window has a corresponding feature index;

storing the time domain data and the quantized features;

time stamping each quantized feature with a respective time index relative to the corresponding time domain data;

linking each quantized feature together in a feature trail such that each quantized feature in the feature trail is linked to a preceding quantized feature that has an earlier time index;

generating a feature vector that is associated with the time domain data and the feature trail; and

updating indexes to the time domain data for searching and retrieval operations such that the feature vector operates as an index for the time domain data.

12. The computer implemented method of claim 11, further comprising mapping the feature vector to another feature trail that is specified at a different resolution from the feature trail such that the feature vector is mapped to different specified resolutions.

13. The computer implemented method of claim 11, further comprising retrieving previously stored time domain data using another feature trail in a retrieval query as a search index by comparing the feature trail for the retrieval query to prior known feature trails, identifying a best match for the comparison, and retrieving the previously indexed time domain data that corresponds to the identified best match.

14. The computer implemented method of claim 11, further comprising retrieving previously stored time domain data using another feature trail in a retrieval query as a search index by:

comparing the feature trail for the retrieval query to prior known feature trails at each specified resolution, identifying a match for each feature in the feature trail that matches the comparison at each of the specified resolutions, adding matches to histogram bins for each matched feature in the feature trail, and retrieving the previously stored time domain data that corresponds to the identified best match as determined from the histogram bins.

15. The computer implemented method of claim 11, further comprising removing a previously stored feature from an identified feature trail by:

selecting the previously stored feature from the identified feature trail, evaluating a frequency of use for the selected feature, and removing the selected feature and updating the links to other features in the identified feature trail when the frequency of use for the selected feature exceeds a threshold.

16. A computer-readable storage device for storing a set of computer-executable instructions to implement a method for managing time domain data with a quantized feature index trajectory methodology, the method comprising:

identifying a first set of quantized features that are linked together in a first feature trail such that each quantized feature in the first feature trail is linked to a preceding one of the quantized features in the first feature trail that has an earlier time index;

mapping the first set of quantized features in the first feature trail to a feature vector that is associated with stored time domain data;

identifying a second set of quantized features that are linked together in the second feature trail such that each quantized feature in the second feature trail is linked to a preceding one of the quantized features in the second feature trail that has an earlier time index;

comparing the first set of quantized features from the first feature trail to the second set of quantized features from the second feature trail;

identifying the stored time domain data when a match is identified from the comparison of the first set of quantized features from the first feature trail to the second set of quantized features from the second feature trail; and

performing an operation on the stored time domain data when the match is identified.

17. The computer-readable storage device for storing the set of computer-executable instructions to implement the method of claim 16, wherein performing the operation on the stored time domain data comprises one of:

a retrieval operation, a storage operation, and a delete operation.

18. The computer-readable storage device for storing the set of computer-executable instructions to implement the method of claim 16, wherein performing the operation on the stored time domain data when the match is identified comprises performing a storage operation for the second set of quantized features that are linked together in the second feature trail by mapping the feature vector to the second set of quantized features with a specified resolution that is different from the first set of quantized features such that the feature vector has a multi-resolution mapping.

19. The computer-readable storage device for storing the set of computer-executable instructions to implement the method of claim 16, wherein performing the operation comprises performing a compaction operation on an identified feature trail by:

selecting each previously stored feature from the identified feature trail, evaluating a frequency of use for the selected feature, removing the selected feature when the frequency of use for the selected feature exceeds a threshold, and updating the links to other features in the identified feature trail.

20. The computer-readable storage device for storing the set of computer-executable instructions to implement the method of claim 16, wherein identifying the stored time domain data when the match is identified from the comparison comprises:

comparing the each quantized features for the second feature trail to each quantized feature for the first feature trail at each specified resolution, identifying a match for each quantized feature in the first feature trail that matches the comparison at each of the specified resolutions, adding matches to histogram bins for each matched feature in the first feature trail, and identifying a match from the histogram bins.