Granted Patent B2

US 7,788,279 · App. 11/558,366 · Granted Aug 31, 2010

Abstract

Claims (84)

1. A method of aligning elements in a query sequence and to elements in a target sequence, wherein the elements represent pitches with durations of an audio sequence, the method including:

representing potential element-to-element partial alignments between query and target sequences derived from audio sequences in an m-by-n cell data structure, such that cell (i,j) represents potential alignment of query element i with target element j;

forward propagating pitches and durations from cells included in partial alignments, for scoring purposes, into cells chosen to have a deleted element;

processing the cells in the data structure in an order that processes a particular cell after antecedent cells have been processed and scored;

choosing, cell-by-cell, whether element pair (i,j) of the query and target sequences should belong to a partial alignment or whether one element in the element pair (i,j) should be deleted, including

considering at least potential transitions to (i,j)

from antecedent cell (i−1,j−1), representing potential inclusion of the element pair (i,j) in the partial alignment,

from antecedent cell (i−1,j), representing potential deletion of an element from the query sequence, and

from antecedent cell (i,j−1), representing potential deletion of an element from the target sequence;

scoring cumulative scores of the potential transitions, wherein

scoring a cumulative score of the potential inclusion of the element pair (i,j) in the partial alignment includes adding a match score to a cumulative score of the previously scored cell (i−1,j−1), wherein calculating the match score includes

using the pitches or propagated pitches of cell (i−1,j−1) and the pitches of cell (i,j) to calculate query pitch and target pitch differences, respectively, and using the durations or propagated durations of cell (i−1,j−1) the durations of cell (i,j) to calculate query duration and target duration ratios, respectively,

then comparing the query and target pitch differences and comparing the query and target duration ratios to determine the match score;

scoring cumulative scores of the potential deletions from the query or target sequence includes subtracting a deletion penalty from the previously scored antecedent cell, either cell (i−1,j) for deletion of element i from the query sequence or cell (i,j−1) for deletion of element j from the target sequence;

selecting among the cumulative scores of the potential transitions and recording at least one selected transition and the cumulative score of the selected transition; and

backtracking through the cumulative scores and the selected transitions, beginning with one or more high scores at one end of the query or target sequences to an opposite end and determining a total alignment, taking into account deletions, between the elements of the query and target sequences, and

reporting for further processing at least the total alignment between the elements of the query and target sequences.

2. The method of claim 1 , wherein the elements sometimes represent pauses, instead of pitches, further including forward propagating at least pitches, for scoring purposes, from cells included in the partial alignments into cells having pauses.

3. The method of claim 2 , wherein the scoring of a potential inclusion transition into cell (i,j) as having a pitch difference of zero if elements i and j of the query and target sequences both include pauses.

4. The method of claim 1 , wherein the elements sometimes represent pauses, instead of pitches, further including the scoring a potential inclusion transition into cell (i,j) as having a pitch difference of zero if elements i and j of the query and target sequences both include pauses.

5. The method of claim 1 , further including considering potential transitions to (i,j) that involve consolidation and combine four cells in the partial alignment, wherein the potential transitions further include

antecedent cell (i−2, j−1), representing potential consolidation of elements i−1 and i−2 from the query sequence, and

antecedent cell (i−1, j−2), representing potential consolidation of elements j−1 and j−2 from the target sequence;

wherein scoring of the potential transitions involving consolidation

selects either a dominant or weighted pitch of the consolidated elements and combines durations of consolidated elements, and

scores transitions both from an antecedent cell into the cells representing the consolidated elements and from the cells representing the consolidated elements into cell (i,j), corresponding to partial alignment of four cells, two of which represent consolidated elements.

6. The method of claim 5 , wherein consolidation of elements is limited to a predetermined number of consecutive elements in a sequence.

7. The method of claim 1 , further including representing the pitches as notes within octaves, such that a notes in different octaves can have a pitch difference of zero.

8. The method of claim 1 , repeatedly applied in a method of retrieving at least one target music item from a database of music items including music data, metadata and keys, the keys including target sequences, the method including:

capturing an audio input query from a user;

processing the audio query to generate a query sequence;

repeatedly applying the method of claim 1 , using the query sequence and multiple target sequences, and reporting scores of the total alignments of the respective query and target sequence alignments;

using the scores, selecting at least one target music item as having the target sequence similar to the query sequence; and

outputting at least an identification of the selected target music item or the selected target music data.

9. The method of claim 8 , further including:

collecting human renditions of parts of songs; and

populating the database of music items with one or more keys per song, wherein the target sequences are derived from the human renditions.

10. The method of claim 9 , further including:

collect a human rendition of a query; and

deriving the query sequence from the human rendition of the query.

11. A method of aligning elements in a query sequence and to elements in a target sequence, wherein the elements represent at least one attribute sampled from a physical source, the method including:

representing potential element-to-element partial alignments between the query and target sequences, sampled from the physical source, in an m-by-n cell data structure, such that cell (i,j) represents potential alignment of query element i with target element j;

forward propagating the attributes, for scoring purposes, from cells included in partial alignments into cells chosen to have a deleted element;

processing the cells in the data structure in an order that processes a particular cell after antecedent cells have been processed and scored;

choosing, cell-by-cell, whether element pair (i,j) of the query and target sequences should belong to a partial alignment or whether one element in the element pair (i,j) should be deleted, including

considering at least potential transitions to (i,j)

from antecedent cell (i−1,j−1), representing potential inclusion of the element pair (i,j) in the partial alignment,

from antecedent cell (i−1,j), representing potential deletion of an element from the query sequence, and

from antecedent cell (i,j−1), representing potential deletion of an element from the target sequence;

scoring cumulative scores of the potential transitions, wherein

scoring a cumulative score of the potential inclusion of the element pair (i,j) in the partial alignment includes adding a match score to a cumulative score of the previously scored cell (i−1,j−1), wherein calculating the match score includes

using the attributes or propagated attributes of cell (i−1,j−1) and the attributes of cell (i,j), applying a transition measure to calculate query and target transition values,

then comparing the query and target transition values to determine the match score;

scoring cumulative scores of the potential deletions from the query or target sequence includes subtracting a deletion penalty from the previously scored antecedent cell, either cell (i−1,j) for deletion of element i from the query sequence or cell (i,j−1) for deletion of element j from the target sequence;

selecting among the cumulative scores of the potential transitions and recording at least one selected transition and the cumulative score of the selected transition; and

backtracking through the cumulative scores and the selected transitions, beginning with one or more high scores at one end of the query or target sequences to an opposite end and determining a total alignment, taking into account deletions, between the elements of the query and target sequences, and

reporting for further processing at least the total alignment between the elements of the query and target sequences.

12. The method of claim 11 , further including considering potential transitions to (i,j) that involve consolidation and combine four cells in the partial alignment, wherein the potential transitions further include

antecedent cell (i−2, j−1), representing potential consolidation of elements i−1 and i−2 from the query sequence, and

antecedent cell (i−1, j−2), representing potential consolidation of elements j−1 and j−2 from the target sequence;

wherein scoring of the potential transitions involving consolidation

selects or combines attributes of consolidated elements, and

scores transitions both from an antecedent cell into the cells representing the consolidated elements and from the cells representing the consolidated elements into cell (i,j), corresponding to partial alignment of four cells, two of which represent consolidated elements.

13. The method of claim 12 , wherein consolidation of elements is limited to a predetermined number of consecutive elements in a sequence.

14. A method of aligning elements in a query sequence and to elements in a target sequence, wherein the elements represent at least one attribute representing a physical characteristic, the method including:

representing potential element-to-element partial alignments between the query and target sequences in an m-by-n cell data structure, such that cell (i,j) represents potential alignment of query element i with target element j;

forward propagating the attributes, for scoring purposes, from cells included in partial alignments into cells chosen to have a deleted element;

processing the cells in the data structure in an order that processes a particular cell after antecedent cells have been processed to have a recorded selected transition and cumulative score;

choosing, cell-by-cell, whether element pair (i,j) of the query and target sequences should belong to a partial alignment or whether one element in the element pair (i,j) should be deleted, including

scoring cumulative scores of potential transitions between antecedent cells and the cell (i,j), wherein

scoring a cumulative score of potential inclusion of the element pair (i,j) in the partial alignment includes adding a match score to previously scored cell (i−1,j−1), wherein calculating the match score includes

using the attributes or propagated attributes of cell (i−1,j−1) and the attributes of cell (i,j), applying a transition measure to calculate query and target transition values,

then comparing the query and target transition values to determine the match score;

scoring cumulative scores of the potential deletions from the query or target sequence includes subtracting a deletion penalty from a previously scored antecedent cell, either cell (i−1,j) for deletion of element i from the query sequence or cell (i,j−1) for deletion of element j from the target sequence;

selecting among the cumulative scores of the potential transitions and recording at least one selected transition and the cumulative score of the selected transition; and

backtracking through the cumulative scores and the selected transitions, beginning with one or more high scores at one end of the query or target sequences to an opposite end and determining a total alignment, taking into account deletions, between the elements of the query and target sequences, and

reporting for further processing at least the total alignment between the elements of the query and target sequences.

15. The method of claim 14 , further including considering potential transitions to (i,j) that involve consolidation and combine four cells in the partial alignment, wherein the potential transitions further include

antecedent cell (i−2, j−1), representing potential consolidation of elements i−1 and i−2 from the query sequence, and

antecedent cell (i−1, j−2), representing potential consolidation of elements j−1 and j−2 from the target sequence;

wherein scoring of the potential transitions involving consolidation

selects or combines attributes of consolidated elements, and

scores transitions both from an antecedent cell into the cells representing the consolidated elements and from the cells representing the consolidated elements into cell (i,j), corresponding to partial alignment of four cells, two of which represent consolidated elements.

16. The method of claim 15 , wherein consolidation of elements is limited to a predetermined number of consecutive elements in the query and/or target sequence.

Assignments (11)