System and method for computing a location of an acoustic source

• US 6,912,178 B2
• Filed: 04/15/2003
• Issued: 06/28/2005
• Est. Priority Date: 04/15/2002
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Polycom Incorporated (HP Inc.)
• Inventors: Chu, Peter L., Washington, Richard, Kenoyer, Michael
• Primary Examiner(s): PIHULIC, DANIEL T
• Application Number:
  US10/414,421
• Publication Number:
  US 20040032796A1
• Time in Patent Office: 805 Days
• Field of Search: 367/125, 367/129, 367/118, 367/123
• US Class Current: 367/123
• CPC Class Codes: G01S 5/18 using ultrasonic, sonic, or infrasonic waves
• CPC Class Codes: H04N 7/142 Constructional details of the terminal equipment, e.g. arrangements of the camera and the display
• CPC Class Codes: H04R 2201/401 2D or 3D arrays of transducers
• CPC Class Codes: H04R 2430/23 Direction finding using a sum-delay beam-former
• CPC Class Codes: H04R 3/005 for combining the signals of two or more microphones specially adapted for hearing aids H04R25/407

Abstract

In accordance with the present invention, a system and method for computing a location of an acoustic source is disclosed. The method includes steps of processing a plurality of microphone signals in frequency space to search a plurality of candidate acoustic source locations for a maximum normalized signal energy. The method uses phase-delay look-up tables to efficiently determine phase delays for a given frequency bin number k based upon a candidate source location and a microphone location, thereby reducing system memory requirements. Furthermore, the method compares a maximum signal energy for each frequency bin number k with a threshold energy E_t(k) to improve accuracy in locating the acoustic source.

Claims

1. A method for computing a location of an acoustic source, comprising the steps of:

receiving acoustic signals from the acoustic source by an array of M-1 microphones and a reference microphone, each microphone identified by an integer microphone index m, 0≦

m≦

M-1;

storing phase-delay look-up tables, the phase-delay look-up tables based upon a plurality of candidate source locations and a spatial configuration of the array of microphones; and

processing the received acoustic signals using the phase-delay look-up tables to compute the location of the acoustic source.

2. The method of claim 1, wherein an entry in a first phase-delay look-up table is defined by an algebraic expression D(r,m)=512·

b·

Δ

m·

v, where r is a vector to a candidate source location of the plurality of candidate source locations, b is a frequency width, v is inversely proportional to a speed of sound, and Δ

m is a distance between a location of a microphone m and the candidate source location minus a distance between a location of the reference microphone and the candidate source location.

3. The method of claim 1, wherein an entry in a second phase-delay look-up table is defined by an algebraic expression cos_table(j)=cos(π

·

j/256), where j is an integer index and 0≦

j511.

4. The method of claim 1, wherein an entry in a third phase-delay look-up table is defined by an algebraic expression sin_table(j)=sin(π

·

j/256), where j is an integer index and 0≦

j≦

511.

5. The method of claim 1, wherein the processing further comprises the steps of:

processing each received acoustic signal to generate blocks of complex coefficients sampled in frequency, each complex coefficient of a block associated with a frequency bin number k, where 0≦

k≦

N-1;

computing signal energies, a signal energy received by the array of microphones from a candidate source location of the plurality of candidate source locations for the frequency bin number k determined by multiplying a complex coefficient of a selected block from each received acoustic signal associated with a microphone m by an appropriate phase delay, summing the phase-delayed complex coefficients, and squaring the summation; and

computing the location of the acoustic source by normalizing and summing the signal energies over the N frequency bin numbers for each candidate source location of the plurality of candidate source locations to give a total signal energy for each candidate source location.

6. The method of claim 5, wherein the processing further comprises the steps of:

digitizing each received acoustic signal;

segmenting each digitized signal into a plurality of blocks, each block of the plurality of blocks including N digital samples Xpm(n), each digital sample Xpm(n) identified by the integer microphone index m, an integer block index p, and an integer sample index n, where 0≦

n≦

N-1 and

performing a discrete Fast Fourier Transform (FFT) on each block to transform the N digital samples per block to N complex coefficients Fpm(k) per block, where 0≦

k≦

N-1.

7. The method of claim 5, wherein the appropriate phase delay for the frequency bin number k, the candidate source location, and the microphone m is determined from a first phase-delay look-up table D(r,m), a second phase-delay look-up table cos_table(j), and a third phase-delay look-up table sin_table(j), where r is a vector to the candidate source location of the plurality of candidate source locations and j is an integer computed from an algebraic expression based upon the first look-up table and the frequency bin number k.

8. The method of claim 5, wherein the computing the location of the acoustic source further comprises the step of determining a maximum total signal energy.

9. A method for computing a location of an acoustic source, comprising the steps of:

receiving analog signals from M-1 microphones and a reference microphone, each received analog signal and each microphone identified by an integer microphone index m, 0≦

m≦

M-1;

digitizing each received analog signal to generate a plurality of digital samples;

segmenting each digitized signal into a plurality of blocks, each block of the plurality of blocks including N digital samples of the plurality of digital samples and each digital sample of the N digital samples identified by the integer microphone index m, an integer block index p, and an integer sample index n, 0≦

n≦

N-1;

performing a discrete Fast Fourier Transform (FFT) on each block to transform the N digital samples to N complex coefficients, a complex coefficient Fpm(k) of the N complex coefficients identified by the integer microphone index in, the integer block index p, and an integer frequency bin number k, 0≦

k≦

N-1;

searching P blocks of each digitized signal for a maximum signal energy associated with the integer frequency bin number k, identifying a block p′

containing the maximum signal energy, 0≦

p′

≦

P-1;

comparing the maximum signal energy with a threshold energy Et(k), and if the maximum signal energy is less than the threshold energy, setting each complex coefficient of the P blocks of each digitized signal associated with the integer frequency bin number k equal to zero;

determining a plurality of phase delays using look-up tables;

multiplying each complex coefficient by a phase delay eiθ

m from the plurality of phase delays to generate phase-delayed complex coefficients and summing the phase-delayed complex coefficients over the integer microphone index m for a candidate source location (x,y,z) of a plurality of candidate source locations and for the integer frequency bin number k according to a first algebraic expression $\mathrm{Gx},y,z<br><br>\left(k\right)=\underset{m=0}{\overset{M-1}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>e<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{i\theta <br><br>mF}}_m^{p^{\mathrm{\prime <br><br>}}}<br><br>\left(k\right);<br><br>$

computing a normalized total signal energy for the candidate source location (x,y,z) according to a second algebraic expression;

$W<br><br>\left(x,y,z\right)=\underset{k=\mathrm{kl}}{\overset{k=k<br><br>\text{\hspace{1em}<br><br>}<br><br>h}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left[<br><br>\mathrm{Gx},y,z<br><br>\left(k\right)<br><br><br><br>2/<br><br>S<br><br>\left(k\right)<br><br><br><br>2\right],$

where 0≦

k1≦

kh≦

N-1 and S(k) is an approximate measure of signal strength for the integer frequency bin number k; and

determining the location of the acoustic source based upon the normalized total signal energies computed for the plurality of candidate source locations.

10. The method of claim 9, wherein M=16.

11. The method of claim 9, wherein N=640.

12. The method of claim 9, wherein P=5.

13. The method of claim 9, wherein an entry in a first look-up table is defined by an algebraic expression D(r,m)=512·

b·

Δ

m·

v, where r is a vector to the candidate source location (x,y,z) of the plurality of candidate source locations, b is a frequency width of the integer frequency bin number k, v is inversely proportional to a speed of sound, and Δ

m is a distance between a location of a microphone m and the candidate source location (x,y,z) minus a distance between a location of the reference microphone and the candidate source location (x,y,z).

14. The method of claim 13, wherein an integer index j is defined by a third algebraic expression j=0x1FF &

int(k·

D(r,m)), where int(k·

D(r,m)) is a product k·

D(r,m) rounded to a nearest integer, 0 x1FF is a hexadecimal representation of a decimal number 511, and &

is a binary “

and”

function.

15. The method of claim 14, wherein the phase delay eiθ

m is defined by a fourth algebraic expression eiθ

m=cos_table(j)+i·

sin_table(j), where i is (−

1)1/2, cos_table(j)=cos(π

·

j/256), and sin_table(j)=sin(π

·

j/256).

16. The method of claim 9, wherein |S(k)|2 is defined by a fifth algebraic expression $$

S⁡

(k)

⁢

2=∑

m=0M-1⁢

 

⁢



Fp′

⁢

m⁡

(k)

⁢

2.

17. The method of claim 9, wherein determining the location of the acoustic source further comprises the step of determining a maximum normalized total signal energy from the normalized total signal energies.

18. An electronic-readable medium having embodied thereon a program, the program being executable by a machine to perform method steps for computing a location of an acoustic source, the method steps comprising:

receiving acoustic signals from the acoustic source by an array of M-1 microphones and a reference microphone, each microphone identified by an integer microphone index m, 0≦

m≦

M-1;

storing phase-delay look-up tables, the phase-delay look-up tables based upon a plurality of candidate source locations and a spatial configuration of the array of microphones; and

processing the received acoustic signals using the phase-delay look-up tables to compute the location of the acoustic source.

19. The electronic-readable medium of claim 18, further comprising the steps of:

processing each received acoustic signal to generate blocks of complex coefficients sampled in frequency, each complex coefficient of a block associated with a frequency bin number k, where 0≦

k≦

N-1;

computing signal energies, a signal energy received by the array of microphones from a candidate source location of the plurality of candidate source locations for the frequency bin number k determined by multiplying a complex coefficient of a selected block from each received acoustic signal associated with a microphone m by an appropriate phase delay, summing the phase-delayed complex coefficients, and squaring the summation; and

computing the location of the acoustic source by normalizing and summing the signal energies over the N frequency bin numbers for each candidate source location of the plurality of candidate source locations to give a total signal energy for each candidate source location.

20. The electronic-readable medium of claim 19, wherein the appropriate phase delay for the frequency bin number k, the candidate source location, and the microphone m is determined from a first phase-delay look-up table D(r,m), a second phase-delay look-up Table cos_table(j), and a third phase-delay look-up table sin_table(j), where r is a vector to the candidate source location of the plurality of candidate source locations and j is an integer computed from an algebraic expression based upon the first look-up table and the frequency bin number k.

21. The electronic-readable medium of claim 19, wherein the computing the location of the acoustic source further comprises the step of determining a maximum total signal energy.

22. A system for computing a location of an acoustic source, comprising:

means for receiving acoustic signals from the acoustic source by an array of M-1 microphones and a reference microphone, each microphone identified by an integer microphone index m, 0≦

m≦

M-1;

means for storing phase-delay look-up tables, the phase-delay look-up tables based upon a plurality of candidate source locations and a spatial configuration of the array of microphones; and

means for processing the received acoustic signals using the phase-delay look-up tables to compute the location of the acoustic source.