Generating correlation scores

• US 9,569,405 B2
• Filed: 04/30/2014
• Issued: 02/14/2017
• Est. Priority Date: 04/30/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sharifi, Matthew, Roblek, Dominik
• Primary Examiner(s): Malzahn, David H
• Application Number:
  US14/265,868
• Publication Number:
  US 20150317281A1
• Time in Patent Office: 1,021 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78

Abstract

A computer-implemented method includes obtaining first and second binary vectors. For each of a plurality of vector locations in a first of j words in the first binary vector, the method includes shifting the binary values for the second binary vector so that a particular one of the binary values in the second binary vector is located at a vector location in a first of the k words in the second binary vector that matches the vector location in the first of j words in the first binary vector. For each of the j words in the first binary vector, the method includes aligning the second binary vector with the word in the first binary vector and determining a binary correlation score. A similarity of the first binary vector and the second binary vector can be determined based at least on one or more of the determined binary correlation scores.

Claims

1. A computer-implemented method for determining an echo of an audio signal, comprising:

receiving, by a computing system, a first audio signal and a second audio signal;

determining, by the computing system, a first binary vector that represents the first audio signal and a second binary vector that represents the second audio signal, the first binary vector being of length X and the second binary vector being of length Y, the first and second binary vectors each being segmented into words of length n, the first binary vector of length X being longer than the second binary vector of length Y, the first binary vector comprising respective binary values for a plurality of vector locations 0 through X−

1, the second binary vector comprising respective binary values for a plurality of vector locations 0 through Y−

1;

aligning, by the computing system, the second binary vector in a first position with respect to the first binary vector so that each of the binary values in the second binary vector aligns with a respective binary value in the first binary vector;

generating, by the computing system, a first binary correlation score for the first position of the second binary vector with respect to the first binary vector by (i) performing respective first binary operations between each binary value in the second binary vector in the first position and the aligned binary value in the first binary vector and (ii) combining results of the respective first binary operations according to a pre-defined correlation function;

aligning, by the computing system, the second binary vector in a second position with respect to the first binary vector, without shifting binary values of the second binary vector to different vector locations in the second binary vector, so that each of the binary values in the second binary vector aligns with a respective binary value in the first binary vector, the second position being offset by a multiple of n vector locations from the first position with respect to the first binary vector;

generating, by the computing system, a second binary correlation score for the second position of the second binary vector with respect to the first binary vector by (i) performing respective second binary operations between each binary value in the second binary vector in the second position and the aligned binary value in the first binary vector and (ii) combining results of the respective second binary operations according to the pre-defined correlation function; and

determining, by the computing system and based on at least one of the first binary correlation score or the second binary correlation score, whether the first audio signal represented by the first binary vector includes an echo of the second audio signal represented by the second binary vector.

2. The computer-implemented method of claim 1, wherein the second binary vector of length Y is a multiple of the word length n and each word in the second binary vector is filled with n binary values.

3. The computer-implemented method of claim 1, wherein:

aligning the second binary vector in the first position with respect to the first binary vector and generating the first binary correlation score for the first position of the second binary vector comprises aligning the second binary vector and generating the first binary correlation score without shifting binary values of the second binary vector to different vector locations in the second binary vector; and

aligning the second binary vector in the second position with respect to the first binary vector and generating the second binary correlation score for the second position of the second binary vector comprises aligning the second binary vector and generating the second binary correlation score without shifting binary values of the second binary vector to different vector locations in the second binary vector.

4. The computer-implemented method of claim 1, wherein:

the first binary vector is segmented into j words of length n;

the second binary vector is segmented into k words of length n;

aligning the second binary vector in the first position with respect to the first binary vector comprises aligning a first of the k words in the second binary vector with a first of the j words in the first binary vector; and

aligning the second binary vector in the second position with respect to the first binary vector comprises aligning the first of the k words in the second binary vector with a second of the j words in the first binary vector that is different than the first of the j words in the first binary vector.

5. The computer-implemented method of claim 4, further comprising, for each of a plurality of words selected from a group consisting of the j words in the first binary vector other than the first and second of the j words:

aligning the second binary vector in a particular position with respect to the first binary vector by aligning the first of the k words in the second binary vector with the respective word among the plurality of words in the first binary vector; and

generating a third binary correlation score for the particular position of the second binary vector with respect to the first binary vector, including performing respective third binary operations between each binary value in the second binary vector in the particular position and the aligned binary value in the first binary vector.

6. The computer-implemented method of claim 5, wherein the plurality of words selected from the group consisting of the j words in the first binary vector other than the first and second of the j words comprises all j−

2 words in the first binary vector other than the first and second of the j words.

7. The computer-implemented method of claim 1, further comprising:

shifting the binary values of the second binary vector by one vector location to generate a first shifted second binary vector in which binary values in the first shifted second binary vector are offset from corresponding binary values in the second binary vector by one vector location; and

for each of at least some of the words in the first binary vector, aligning a first word of the first shifted second binary vector with the word in the first binary vector and generating a third binary correlation score by (i) performing respective third binary operations between each binary value in the first shifted second binary vector and a respective aligned binary value in the first binary vector and (ii) combining results of the respective third binary operations according to the pre-defined correlation function.

8. The computer-implemented method of claim 7, further comprising:

generating n−

2 additional shifted second binary vectors in which, for each m from 2 through n−

1, an mth one of the additional shifted second binary vectors has respective binary values that are offset from corresponding binary values in the second binary vector by m vector locations; and

generating binary correlation scores using the additional shifted second binary vectors by aligning each of the additional shifted second binary vectors in one or more positions with respect to the first binary vector and generating a respective binary correlation score.

9. The computer-implemented method of claim 1, further comprising:

shifting the binary values of the first binary vector by a first number of vector locations to generate a first shifted first binary vector in which binary values in the first shifted first binary vector are offset from corresponding binary values in the first binary vector by the first number of vector locations; and

for each of at least some of the words in the first shifted first binary vector, aligning a first word of the second binary vector with the word in the first shifted first binary vector and generating a third binary correlation score by (i) performing respective third binary operations between each binary value in the second binary vector and an aligned binary value in the first shifted first binary vector and (ii) combining results of the respective third binary operations according to the pre-defined correlation function.

10. The computer-implemented method of claim 1, further comprising shifting the binary values of the first binary vector by one vector location at a time for a total of n−

1 times, and generating, after each shift of the first binary vector, one or more binary correlation scores based on the shifted first binary vector and the second binary vector.

11. The computer-implemented method of claim 1, further comprising determining a cross-correlation of the first binary vector and the second binary vector based on one or more of the binary correlation scores.

12. The computer-implemented method of claim 11, wherein determining whether the first binary vector is similar to the second binary vector comprises determining whether a value of the cross-correlation of the first binary vector and the second binary vector satisfies a threshold cross-correlation value.

13. The computer-implemented method of claim 1, wherein the binary values in the first binary vector and the second binary vector each represent changes among consecutive digitized samples in one or more sets of data, wherein the first binary vector and the second binary vector each comprises binary values consisting of 0 and 1, wherein a binary value of 1 indicates an increase from a first sample value to a next sample value in the one or more sets of data, wherein a binary value of 0 indicates a decrease from a first sample value to a next sample value in the one or more sets of data.

14. The computer-implemented method of claim 1, wherein:

the first binary vector and the second binary vector each comprises binary values consisting of 0 and 1; and

performing respective first or second binary operations to generate a third binary correlation score for the first position or the second position of the second binary vector with respect to the first binary vector comprises performing an XOR operation between each binary value in the second binary vector in the first or second position, respectively, and the aligned binary value in the first binary vector.

15. The computer implemented method of claim 1, wherein generating the first binary correlation score for the first position of the second binary vector with respect to the first binary vector comprises (i) performing respective XOR operations between each binary value in the second binary vector in the first position and the aligned binary value in the first binary vector and (ii) determining a sum of values resulting from the respective XOR operations as the first binary correlation score.

16. The computer-implemented method of claim 1, wherein generating the first binary correlation score for the first position of the second binary vector with respect to the first binary vector comprises (i) performing respective XOR operations between each binary value in the second binary vector in the first position and the aligned binary value in the first binary vector, (ii) determining a sum of values resulting from the respective XOR operations, and (iii) computing the first binary correlation score based on a lag value of the second binary vector with respect to the first binary vector and the sum of values resulting from the respective XOR operations.

17. The computer-implemented method of claim 1, further comprising:

in response to determining that the audio signal represented by the first binary vector includes the echo of the audio signal represented by the second binary vector, filtering the audio signal represented by the first binary vector to at least partially remove the echo of the audio signal represented by the second binary vector from the audio signal represented by the first binary vector.

18. One or more computer-readable storage devices having instructions stored thereon that, when executed by one or more processors, cause the one or more processors to perform operations for determining an echo of an audio signal, the operations comprising:

receiving a first audio signal and a second audio signal;

determining a first binary vector that represents the first audio signal and a second binary vector that represents the second audio signal, the first binary vector being of length X and the second binary vector being of length Y, the first and second binary vectors each being segmented into words of length n, the first binary vector of length X being longer than the second binary vector of length Y, the first binary vector comprising respective binary values for a plurality of vector locations 0 through X−

1, the second binary vector comprising respective binary values for a plurality of vector locations 0 through Y−

1;

aligning the second binary vector in a first position with respect to the first binary vector so that each of the binary values in the second binary vector aligns with a respective binary value in the first binary vector;

generating a first binary correlation score for the first position of the second binary vector with respect to the first binary vector by (i) performing respective first binary operations between each binary value in the second binary vector in the first position and the aligned binary value in the first binary vector and (ii) combining results of the respective first binary operations according to a pre-defined correlation function;

aligning the second binary vector in a second position with respect to the first binary vector, without shifting binary values of the second binary vector to different vector locations in the second binary vector, so that each of the binary values in the second binary vector aligns with a respective binary value in the first binary vector, the second position being offset by a multiple of n vector locations from the first position with respect to the first binary vector;

generating a second binary correlation score for the second position of the second binary vector with respect to the first binary vector by (i) performing respective second binary operations between each binary value in the second binary vector in the second position and the aligned binary value in the first binary vector and (ii) combining results of the respective second binary operations according to the pre-defined correlation function; and

determining based on at least one of the first binary correlation score or the second binary correlation score, whether the first audio signal represented by the first binary vector includes an echo of the second audio signal represented by the second binary vector.

19. A system comprising:

one or more computer processors; and

one or more computer-readable storage devices having instructions stored thereon that, when executed by the one or more computer processors, cause the one or more computer processors to perform operations for determining an echo of an audio signal, the operations comprising;

receiving a first audio signal and a second audio signal;

determining a first binary vector that represents the first audio signal and a second binary vector that represents the second audio signal, the first binary vector being of length X and the second binary vector being of length Y, the first and second binary vectors each being segmented into words of length n, the first binary vector of length X being longer than the second binary vector of length Y, the first binary vector comprising respective binary values for a plurality of vector locations 0 through X−

1, the second binary vector comprising respective binary values for a plurality of vector locations 0 through Y−

1;

aligning the second binary vector in a first position with respect to the first binary vector so that each of the binary values in the second binary vector aligns with a respective binary value in the first binary vector;

generating a first binary correlation score for the first position of the second binary vector with respect to the first binary vector by (i) performing respective first binary operations between each binary value in the second binary vector in the first position and the aligned binary value in the first binary vector and (ii) combining results of the respective first binary operations according to a pre-defined correlation function;

aligning the second binary vector in a second position with respect to the first binary vector, without shifting binary values of the second binary vector to different vector locations in the second binary vector, so that each of the binary values in the second binary vector aligns with a respective binary value in the first binary vector, the second position being offset by a multiple of n vector locations from the first position with respect to the first binary vector;

generating a second binary correlation score for the second position of the second binary vector with respect to the first binary vector by (i) performing respective second binary operations between each binary value in the second binary vector in the second position and the aligned binary value in the first binary vector and (ii) combining results of the respective second binary operations according to the pre-defined correlation function; and

determining based on at least one of the first binary correlation score or the second binary correlation score, whether the first audio signal represented by the first binary vector includes an echo of the second audio signal represented by the second binary vector.