# US 11,907,288 B2 · Audio identification based on data structure

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,907,288 B2
- Document ID: US11907288B2
- Status: Granted
- Kind: B2
- Application number: 16/927,577
- Filed: 2020-07-13
- Published: 2020-10-29
- Granted: 2024-02-20
- Earliest claimed: 2016-09-09
- Assignees: Gracenote, Inc.
- Applicants: Gracenote, Inc.
- Inventors: Zafar Rafii; Prem Seetharaman
- Web page: https://patentgrep.com/patent/US11907288B2

## CPC

- G06F 16/683: using metadata automatically derived from the content
- G06F 16/61: Indexing; Data structures therefor; Storage structures
- G06F 16/686: {using information manually generated, e.g. tags, keywords, comments, title or artist information, time, location or usage information, user ratings}
- G06F 17/14: Fourier, Walsh or analogous domain transformations {, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms (for correlation function computation G06F17/156; spectrum analysers G01R23/16)}
- G10L 25/27: characterised by the analysis technique
- G10L 25/51: for comparison or discrimination
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING

## Abstract

Example systems and methods are audio identification based on data structure are disclosed. An example apparatus includes memory, and one or more processors to execute instructions to execute a constant Q transform on query time slices of query audio, binarize the constant Q transformed query time slices, execute a two-dimensional Fourier transform on query time windows within the binarized and constant Q transformed query time slices to generate two-dimensional Fourier transforms of the query time windows, sequentially order the two-dimensional Fourier transforms in a query data structure, and identify the query audio as a cover rendition of reference audio based on a comparison between the query data structure and a reference data structure associated with the reference audio.

## Claims

### Claim 1

An apparatus comprising:
memory; and
one or more processors to execute instructions to:
execute a constant Q transform on query time slices of query audio;
binarize the constant Q transformed query time slices;
execute a two-dimensional Fourier transform on query time windows within the binarized constant Q transformed query time slices to generate two-dimensional Fourier transforms of the query time windows;
sequentially order the two-dimensional Fourier transforms in a query data structure; and
identify the query audio as a cover rendition of reference audio based on a comparison between the query data structure and a reference data structure associated with the reference audio.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the constant Q transformed query time slices include a first constant Q transformed query time slice, and the one or more processors are to:
calculate a median value of a range of constant Q transformed query time slices that includes the first constant Q transformed query time slice; and
binarize the first constant Q transformed query time slice based on the median value of the range.

### Claim 3 (depends on 1)

The apparatus of claim 1, wherein the one or more processors are to:
execute a constant Q transform on reference time slices of the reference audio;
binarize the constant Q transformed reference time slices;
execute a two-dimensional Fourier transform on reference time windows within the binarized constant Q transformed reference time slices to generate two-dimensional Fourier transforms of the reference time windows; and
sequentially order the two-dimensional Fourier transforms of the reference time windows in the reference data structure.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein the one or more processors are to:
store an association in a database between the reference audio and the reference data structure, the association indicates that the reference data structure is an identifier of the reference audio;
receive a request to identify the query audio, the request received from a device; and
control the device by causing the device to present a notification that the query audio is the cover rendition, the notification including the identifier.

### Claim 5 (depends on 1)

The apparatus of claim 1, wherein the one or more processors are to:
generate a similarity matrix that indicates degrees to which reference portions of the reference data structure are similar to query portions of the query data structure;
compute a distance measure between the query data structure and the reference data structure based on the similarity matrix; and
store an association in a database between the reference audio and the query audio based on a computed distance measure, the association identifying the query audio as the cover rendition.

### Claim 6 (depends on 5)

The apparatus of claim 5, wherein the one or more processors are to:
convolve the similarity matrix with a checkerboard kernel to generate a first convolved similarity matrix, the first convolved similarity matrix including positive elements and negative elements; and
replace the negative elements with zeros to generate a second convolved similarity matrix; and wherein:
the computing of the distance measure between the query data structure and the reference data structure is based on the second convolved similarity matrix.

### Claim 7 (depends on 1)

The apparatus of claim 1, wherein the one or more processors are to:
generate a similarity matrix based on reference portions of the reference data structure with respect to query portions of the query data structure;
convolve the similarity matrix with a checkerboard kernel to generate a first convolved similarity matrix including negative elements;
replace respective ones of the negative elements with zeros to generate a second convolved similarity matrix;
identify diagonals with the negative elements replaced with zeros in the second convolved similarity matrix;
compute a first set of lengths and sums of the diagonals;
compute multiplicative products of the first set;
rank the diagonals based on the multiplicative products;
identify a dominant subset of the diagonals based on the ranking;
sum multiplicative products of a second set of lengths and sums of the dominant subset; and
compute a distance measure between the query data structure and the reference data structure based on the summed multiplicative products.

### Claim 8 (depends on 1)

The apparatus of claim 1, wherein the one or more processors are to group the binarized constant Q transformed query time slices of the query audio into the query time windows prior to the executing of the two-dimensional Fourier transform on the query time windows, the query time windows including overlapping query time windows of uniform duration.

### Claim 9 (depends on 1)

The apparatus of claim 1, wherein the one or more processors are to apply a blur algorithm to the two-dimensional Fourier transforms of the query time windows prior to the sequential ordering of the two-dimensional Fourier transforms in the query data structure.

### Claim 10

A non-transitory machine-readable medium comprising instructions that, when executed, cause one or more processors to at least:
execute a constant Q transform on query time slices of query audio;
binarize the constant Q transformed query time slices;
execute a two-dimensional Fourier transform on query time windows within the binarized constant Q transformed query time slices to generate two-dimensional Fourier transforms of the query time windows;
sequentially order the two-dimensional Fourier transforms in a query data structure; and
identify the query audio as a cover rendition of reference audio based on a comparison between the query data structure and a reference data structure associated with the reference audio.

### Claim 11 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein the constant Q transformed query time slices include a first constant Q transformed query time slice, and the instructions, when executed, cause the one or more processors to:
calculate a median value of a range of constant Q transformed query time slices that includes the first constant Q transformed query time slice; and
binarize the first constant Q transformed query time slice based on the median value of the range.

### Claim 12 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein the instructions, when executed, cause the one or more processors to:
execute a constant Q transform on reference time slices of the reference audio;
binarize the constant Q transformed reference time slices;
execute a two-dimensional Fourier transform on reference time windows within the binarized constant Q transformed reference time slices to generate two-dimensional Fourier transforms of the reference time windows; and
sequentially order the two-dimensional Fourier transforms of the reference time windows in the reference data structure.

### Claim 13 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein the instructions, when executed, cause the one or more processors to:
store an association in a database between the reference audio and the reference data structure, the association indicates that the reference data structure is an identifier of the reference audio;
receive a request to identify the query audio, the request received from a device; and
control the device by causing the device to present a notification that the query audio is the cover rendition, the notification including the identifier.

### Claim 14 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein the instructions, when executed, cause the one or more processors to:
generate a similarity matrix that indicates degrees to which reference portions of the reference data structure are similar to query portions of the query data structure;
compute a distance measure between the query data structure and the reference data structure based on the similarity matrix; and
store an association in a database between the reference audio and the query audio based on a computed distance measure, the association identifying the query audio as the cover rendition.

### Claim 15 (depends on 14)

The non-transitory machine-readable medium of claim 14, wherein the instructions, when executed, cause the one or more processors to:
convolve the similarity matrix with a checkerboard kernel to generate a first convolved similarity matrix, the first convolved similarity matrix including positive elements and negative elements; and
replace the negative elements with zeros to generate a second convolved similarity matrix; and wherein:
the computing of the distance measure between the query data structure and the reference data structure is based on the second convolved similarity matrix.

### Claim 16 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein the instructions, when executed, cause the one or more processors to:
generate a similarity matrix based on reference portions of the reference data structure with respect to query portions of the query data structure;
convolve the similarity matrix with a checkerboard kernel to generate a first convolved similarity matrix including negative elements;
replace respective ones of the negative elements with zeros to generate a second convolved similarity matrix;
identify diagonals with the negative elements replaced with zeros in the second convolved similarity matrix;
compute a first set of lengths and sums of the diagonals;
compute multiplicative products of the first set;
rank the diagonals based on the multiplicative products;
identify a dominant subset of the diagonals based on the ranking;
sum multiplicative products of a second set of lengths and sums of the dominant subset; and
compute a distance measure between the query data structure and the reference data structure based on the summed multiplicative products.

### Claim 17 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein the instructions, when executed, cause the one or more processors to group the binarized constant Q transformed query time slices of the query audio into the query time windows prior to the executing of the two-dimensional Fourier transform on the query time windows, the query time windows including overlapping query time windows of uniform duration.

### Claim 18 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein the instructions, when executed, cause the one or more processors to apply a blur algorithm to the two-dimensional Fourier transforms of the query time windows prior to the sequential ordering of the two-dimensional Fourier transforms in the query data structure.

### Claim 19

A method comprising:
executing, using one or more processors, a constant Q transform on query time slices of query audio;
binarizing, using the one or more processors, the constant Q transformed query time slices;
executing, using the one or more processors, a two-dimensional Fourier transform on query time windows within the binarized constant Q transformed query time slices to generate two-dimensional Fourier transforms of the query time windows;
sequentially ordering, using the one or more processors, the two-dimensional Fourier transforms in a query data structure; and
identifying, using the one or more processors, the query audio as a cover rendition of reference audio based on a comparison between the query data structure and a reference data structure associated with the reference audio.

### Claim 20 (depends on 19)

The method of claim 19, wherein the constant Q transformed query time slices include a first constant Q transformed query time slice, and binarizing the constant Q transformed query time slices includes:
calculating a median value of a range of constant Q transformed query time slices that includes the first constant Q transformed query time slice; and
binarizing the first constant Q transformed query time slice based on the median value of the range.

### Claim 21 (depends on 19)

The method of claim 19, further including:
executing a constant Q transform on reference time slices of the reference audio;
binarizing the constant Q transformed reference time slices;
executing a two-dimensional Fourier transform on reference time windows within the binarized constant Q transformed reference time slices to generate two-dimensional Fourier transforms of the reference time windows; and
sequentially ordering the two-dimensional Fourier transforms of the reference time windows in the reference data structure.

### Claim 22 (depends on 19)

The method of claim 19, further including:
storing an association in a database between the reference audio and the reference data structure, the association indicates that the reference data structure is an identifier of the reference audio;
receiving a request to identify the query audio, the request received from a device; and
controlling the device by causing the device to present a notification that the query audio is the cover rendition, the notification including the identifier.

### Claim 23 (depends on 19)

The method of claim 19, further including:
generating a similarity matrix that indicates degrees to which reference portions of the reference data structure are similar to query portions of the query data structure;
computing a distance measure between the query data structure and the reference data structure based on the similarity matrix; and
storing an association in a database between the reference audio and the query audio based on a computed distance measure, the association identifying the query audio as the cover rendition.

### Claim 24 (depends on 23)

The method of claim 23, further including:
convolving the similarity matrix with a checkerboard kernel to generate a first convolved similarity matrix, the first convolved similarity matrix including positive elements and negative elements; and
replacing the negative elements with zeros to generate a second convolved similarity matrix; and wherein:
the computing of the distance measure between the query data structure and the reference data structure is based on the second convolved similarity matrix.

### Claim 25 (depends on 19)

The method of claim 19, further including:
generating a similarity matrix based on reference portions of the reference data structure with respect to query portions of the query data structure;
convolving the similarity matrix with a checkerboard kernel to generate a first convolved similarity matrix including negative elements;
replacing respective ones of the negative elements with zeros to generate a second convolved similarity matrix;
identifying diagonals with the negative elements replaced with zeros in the second convolved similarity matrix;
calculating a first set of lengths and sums of the diagonals;
calculating multiplicative products of the first set;
ranking the diagonals based on the multiplicative products;
identifying a dominant subset of the diagonals based on the ranking;
summing multiplicative products of a second set of lengths and sums of the dominant subset; and
calculating a distance measure between the query data structure and the reference data structure based on the summed multiplicative products.

### Claim 26 (depends on 19)

The method of claim 19, further including grouping the binarized constant Q transformed query time slices of the query audio into the query time windows prior to the executing of the two-dimensional Fourier transform on the query time windows, the query time windows including overlapping query time windows of uniform duration.

### Claim 27 (depends on 19)

The method of claim 19, further including applying a blur algorithm to the two-dimensional Fourier transforms of the query time windows prior to the sequential ordering of the two-dimensional Fourier transforms in the query data structure.