`Marash et al.
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006363345Bl
`US 6,363,345 Bl
`Mar.26,2002
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) SYSTEM, METHOD AND APPARATUS FOR
`CANCELLING NOISE
`
`(75)
`
`Inventors: Joseph Marash, Haifa; Baruch
`Berdugo, Kiriat-Ata, both of (IL)
`
`(73) Assignee: Andrea Electronics Corporation,
`Melville, NY (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/252,874
`
`(22) Filed:
`
`Feb. 18, 1999
`
`(51)
`
`Int. Cl? ................................................ GlOL 21/02
`
`(52)
`(58)
`
`U.S. Cl. ........................ 704/226; 704/233; 704/205
`Field of Search ................................. 704/270, 500,
`704/233, 200, 201, 205, 226, 227, 228,
`211, 216; 379/22.08, 392.Dl, 3, 406.01,
`406.12, 406.13, 406.14, 406.05
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`2,379,514 A
`2,972,018 A
`3,098,121 A
`3,101,744 A
`
`7/1945 Fisher
`2/1961 Hawley et a!.
`7/1963 Wadsworth
`8/1963 Warnaka
`
`(List continued on next page.)
`
`FOREIGN PATENT DOCUMENTS
`
`DE
`DE
`DE
`EP
`EP
`EP
`EP
`EP
`EP
`
`2640324
`3719963
`4008595
`0 059 745 B1
`0 380 290 A2
`0 390 386
`0 411 360 B1
`0 509 742 A2
`0 483 845
`
`3/1978
`3/1988
`9/1991
`9/1982
`8/1990
`10/1990
`2/1991
`10/1992
`1!1993
`
`OTHER PUBLICATIONS
`B.D. VanVeen and K.M. Buckley, "Beamforming: AVer(cid:173)
`satile Approach to Spatial Filtering," IEEE ASSN Magazine,
`vol. 5, No. 2, Apr. 1988, pp. 4-24.
`Beranek, Acoustics (American Institute of Physics, 1986)
`pp. 116-135.
`Boll, IEEE Trans. on Aeons., vol. ASSP-27, No. 2, Apr.
`1979, pp. 113-120.
`Daniel Sweeney, "Sound Conditioning Through DSP", The
`Equipment Authority, 1994.
`(List continued on next page.)
`Primary Examiner---Richemond Dorvil
`(74) Attorney, Agent, or Firm---Frommer Lawrence &
`Haug; Thomas J. Kowalski
`ABSTRACT
`(57)
`
`A threshold detector precisely detects the positions of the
`noise elements, even within continuous speech segments, by
`determining whether frequency spectrum elements, or bins,
`of the input signal are within a threshold set according to
`current and future minimum values of the frequency spec(cid:173)
`trum elements. In addition, the threshold is continuously set
`and initiated within a predetermined period of time. The
`estimate magnitude of the input audio signal is obtained
`using a multiplying combination of the real and imaginary
`part of the input in accordance with the higher and lower
`values between the real and imaginary part of the signal. In
`order to further reduce instability of the spectral estimation,
`a two-dimensional smoothing is applied to the signal esti(cid:173)
`mate using neighboring frequency bins and an exponential
`average over time. A filter multiplication effects the subtrac(cid:173)
`tion thereby avoiding phase calculation difficulties and
`effecting full-wave rectification which further reduces arti(cid:173)
`facts. Since the noise elements are determined within con(cid:173)
`tinuous speech segments, the noise is canceled from the
`audio signal nearly continuously thereby providing excellent
`noise cancellation characteristics. Residual noise reduction
`reduces the residual noise remaining after noise can cella(cid:173)
`tion. Implementation may be effected in various noise can(cid:173)
`celing schemes including adaptive beamforming and noise
`cancellation using computer program applications installed
`as software or hardware.
`
`(List continued on next page.)
`
`47 Claims, 10 Drawing Sheets
`
`202
`
`R(O) 1(0)
`
`204
`
`206
`
`208
`
`Y(n)=
`1/3[Y(n-1 )+ Y(n)+Y(n+1 )]
`
`Time Domain
`214"' Input Signal
`
`216
`
`Noise Processing
`
`Petitioner Apple Inc.
`Ex. 1001, p. 1
`
`
`
`US 6,363,345 Bl
`Page 2
`
`4,752,961 A
`4,769,847 A
`4,771,472 A
`4,783,798 A
`4,783,817 A
`4,783,818 A
`4,791,672 A
`4,802,227 A
`4,811,404 A
`4,833,719 A
`4,837,832 A
`4,847,897 A
`4,862,506 A
`4,878,188 A
`4,908,855 A
`4,910,718 A
`4,910,719 A
`4,928,307 A
`4,930,156 A
`4,932,063 A
`4,937,871 A
`4,947,356 A
`4,951,954 A
`4,955,055 A
`4,956,867 A
`4,959,865 A
`4,963,071 A
`4,965,834 A
`4,977,600 A
`4,985,925 A
`4,991,433 A
`5,001,763 A
`5,010,576 A
`5,018,202 A
`5,023,002 A
`5,029,218 A
`5,046,103 A
`5,052,510 A
`5,070,527 A
`5,075,694 A
`5,086,385 A
`5,086,415 A
`5,091,954 A
`5,097,923 A
`5,105,377 A
`5,117,461 A
`5,121,426 A
`5,125,032 A
`5,126,681 A
`5,133,017 A
`5,134,659 A
`5,138,663 A
`5,138,664 A
`5,142,585 A
`5,192,918 A
`5,208,864 A
`5,209,326 A
`5,212,764 A
`5,219,037 A
`5,226,077 A
`5,226,087 A
`5,241,692 A
`5,251,263 A
`5,251,863 A
`5,260,997 A
`5,272,286 A
`5,276,740 A
`5,311,446 A
`5,311,453 A
`5,313,555 A
`5,313,945 A
`
`6/1988 Kahn
`9/1988 Taguchi
`9/1988 Williams, III et a!.
`11/1988 Leibholz et a!.
`11/1988 Hamada eta!.
`11/1988 Graupe eta!.
`12/1988 Nunley eta!.
`1!1989 Elko eta!.
`3/1989 Vilmur eta!.
`5/1989 Carme eta!.
`6/1989 Fanshel
`7/1989 Means
`8/1989 Landgarten et a!.
`10/1989 Ziegler et a!.
`3/1990 Ohga eta!.
`3/1990 Horn
`3/1990 Thubert
`5/1990 Lynn
`5/1990 Norris
`6/1990 Nakamura
`6/1990 Hattori
`8/1990 Elliott et a!.
`8/1990 MacNeill
`9/1990 Fujisaki et a!.
`9/1990 Zarek eta!.
`9/1990 Stettiner et a!.
`10/1990 Larwin eta!.
`10/1990 Miller
`12/1990 Ziegler
`1!1991 Langberg et a!.
`2/1991 Warnaka et a!.
`3/1991 Moseley
`4/1991 Hill
`5/1991 Takahashi et a!.
`6/1991 Schweizer et a!.
`7/1991 Nagayasu
`9/1991 Warnaka et a!.
`10/1991 Gossman
`12/1991 Lynn
`12/1991 Donnangelo et a!.
`2/1992 Launey eta!.
`2/1992 Takahashi et a!.
`2/1992 Sasaki eta!.
`3/1992 Ziegler et a!.
`4/1992 Ziegler, Jr.
`5/1992 Moseley
`6/1992 Bavmhauer
`6/1992 Meister et a!.
`6/1992 Ziegler, Jr. et a!.
`7/1992 Cain eta!.
`7/1992 Moseley
`8/1992 Moseley
`8/1992 Kimura eta!.
`8/1992 Taylor
`3/1993 Sugiyama
`5/1993 Kaneda
`5/1993 Harper
`5/1993 Ariyoshi
`6/1993 Smith eta!.
`7/1993 Lynn eta!.
`7/1993 Ono
`8/1993 Harrison et a!.
`10/1993 Andrea eta!.
`10/1993 Gossman et a!.
`11/1993 Gatley eta!.
`12/1993 Cain eta!.
`1!1994 Inanaga et a!.
`5/1994 Ross eta!.
`5/1994 Denenberg et a!.
`5/1994 Kamiya
`5/1994 Friedlander
`
`U.S. PATENT DOCUMENTS
`
`3,170,046 A
`3,247,925 A
`3,262,521 A
`3,298,457 A
`3,330,376 A
`3,394,226 A
`3,416,782 A
`3,422,921 A
`3,562,089 A
`3,702,644 A
`3,830,988 A
`3,889,059 A
`3,890,474 A
`4,068,092 A
`4,122,303 A
`4,153,815 A
`4,169,257 A
`4,239,936 A
`4,241,805 A
`4,243,117 A
`4,261,708 A
`4,321,970 A
`4,334,740 A
`4,339,018 A
`4,363,007 A
`4,409,435 A
`4,417,098 A
`4,433,435 A
`4,442,546 A
`4,453,600 A
`4,455,675 A
`4,459,851 A
`4,461,025 A
`4,463,222 A
`4,473,906 A
`4,477,505 A
`4,489,441 A
`4,490,841 A
`4,494,074 A
`4,495,643 A
`4,517,415 A
`4,527,282 A
`4,530,304 A
`4,539,708 A
`4,559,642 A
`4,562,589 A
`4,566,118 A
`4,570,155 A
`4,581,758 A
`4,589,136 A
`4,589,137 A
`4,600,863 A
`4,622,692 A
`4,628,529 A
`4,630,302 A
`4,630,304 A
`4,636,586 A
`4,649,505 A
`4,653,102 A
`4,653,606 A
`4,654,871 A
`4,658,426 A
`4,672,674 A
`4,683,010 A
`4,696,043 A
`4,718,096 A
`4,731,850 A
`4,736,432 A
`4,741,038 A
`4,750,207 A
`
`2/1965 Leale
`4/1966 Warnaka
`7/1966 Warnaka
`1!1967 Warnaka
`7/1967 Warnaka
`7/1968 Andrews, Jr.
`12/1968 Warnaka
`1!1969 Warnaka
`2/1971 Warnaka et a!.
`11/1972 Fowler eta!.
`8/1974 Mol eta!.
`6/1975 Thompson et a!.
`6/1975 Glicksberg
`1!1978 Ikoma eta!.
`10/1978 Chaplin et a!.
`5/1979 Chaplin et a!.
`9/1979 Smith
`12/1980 Sakoe
`12/1980 Chance, Jr.
`1!1981 Warnaka
`4/1981 Gallagher
`3/1982 Thigpen
`6/1982 Wray
`7/1982 Warnaka
`12/1982 Haramoto et a!.
`10/1983 Ono
`11/1983 Chaplin et a!.
`2/1984 David
`4/1984 Ishigaki
`6/1984 Thigpen
`6/1984 Bose eta!.
`7/1984 Crostack
`7/1984 Franklin
`7/1984 Poradowski
`9/1984 Warnaka et a!.
`10/1984 Warnaka
`12/1984 Chaplin et a!.
`12/1984 Chaplin et a!.
`1!1985 Bose
`1!1985 Orban
`5/1985 Laurence
`7/1985 Chaplin et a!.
`7/1985 Gardos
`9/1985 Norris
`12/1985 Miyaji eta!.
`12/1985 Warnaka et a!.
`1!1986 Chaplin et a!.
`2/1986 Skarman et a!.
`4/1986 Coker eta!.
`5/1986 Poldy eta!.
`5/1986 Miller
`7/1986 Chaplin et a!.
`11/1986 Cole
`12/1986 Borth eta!.
`12/1986 Kryter
`12/1986 Borth eta!.
`1!1987 Schiff
`3/1987 Zinser, Jr. et a!.
`3/1987 Hansen
`3/1987 Flanagan
`3/1987 Chaplin et a!.
`4/1987 Chabries et a!.
`6/1987 Clough eta!.
`7/1987 Hartmann
`9/1987 Iwahara et a!.
`1!1988 Meisel
`3/1988 Levitt eta!.
`4/1988 Cantrell
`4/1988 Elko eta!.
`6/1988 Gebert eta!.
`
`Petitioner Apple Inc.
`Ex. 1001, p. 2
`
`
`
`US 6,363,345 Bl
`Page 3
`
`5/1994 Gossman et a!.
`5,315,661 A
`6/1994 Hunt
`5,319,736 A
`7/1994 Stites, III
`5,327,506 A
`7/1994 Gossman et a!.
`5,332,203 A
`8/1994 Addeo eta!.
`5,335,011 A
`9/1994 Harper
`5,348,124 A
`10/1994 Irissou et a!.
`5,353,347 A
`10/1994 Oh eta!.
`5,353,376 A
`5,361,303 A
`11/1994 Eatwell
`11/1994 Ross eta!.
`5,365,594 A
`12/1994 Denenberg
`5,375,174 A
`1!1995 Andrea eta!.
`5,381,473 A
`1!1995 Gammie eta!.
`5,381,481 A
`1!1995 Masuda eta!.
`5,384,843 A
`3/1995 Nishimoto et a!.
`5,402,497 A
`5/1995 Engebretson et a!.
`5,412,735 A
`5/1995 Gatley eta!.
`5,414,769 A
`5/1995 Scribner et a!.
`5,414,775 A
`5/1995 Shen
`5,416,845 A
`5/1995 Boze
`5,416,847 A
`5/1995 Shimada
`5,416,887 A
`5/1995 Eatwell
`5,418,857 A
`6/1995 Gossman et a!.
`5,423,523 A
`7/1995 Ross eta!.
`5,431,008 A
`7/1995 Yang eta!.
`5,432,859 A
`7/1995 Nadim
`5,434,925 A
`8/1995 Denenberg et a!.
`5,440,642 A
`9/1995 Yamaguchi et a!.
`5,448,637 A
`9/1995 Jones
`5,452,361 A
`10/1995 Cain eta!.
`5,457,749 A
`11/1995 Eatwell
`5,469,087 A
`11/1995 Curtis eta!.
`5,471,106 A
`11/1995 Sasaki eta!.
`5,471,538 A
`12/1995 Hildebrand
`5,473,214 A
`12/1995 Cezanee et a!.
`5,473,701 A
`12/1995 Yoshida eta!.
`5,473,702 A
`12/1995 Eatwell
`5,475,761 A
`5,479,562 A * 12/1995 Fielder et a!.
`5,481,615 A
`1!1996 Eatwell eta!.
`5,485,515 A
`1!1996 Allen eta!.
`5,493,615 A
`2/1996 Burke eta!.
`5,502,869 A
`4/1996 Smith eta!.
`5,511,127 A
`4/1996 Warnaka
`5,511,128 A
`4/1996 Lindeman
`5,515,378 A
`5/1996 Roy, III et a!.
`5,524,056 A
`6/1996 Killion et a!.
`5,524,057 A
`6/1996 Akiho eta!.
`5,526,432 A
`6/1996 Denenberg
`5,546,090 A
`8/1996 Roy, III et a!.
`5,546,467 A
`8/1996 Denenberg
`5,550,334 A
`8/1996 Langley
`5,553,153 A
`9/1996 Eatwell
`10/1996 Ziegler et a!.
`5,563,817 A
`10/1996 Ross eta!.
`5,568,557 A
`12/1996 Brandstein et a!.
`5,581,620 A
`1!1997 Cai eta!.
`5,592,181 A
`5,592,490 A
`1!1997 Barratt et a!.
`5,600,106 A
`2/1997 Langley
`5,604,813 A
`2/1997 Evans eta!.
`5,615,175 A
`3/1997 Cater eta!.
`5,617,479 A
`4/1997 Hildebrand et a!.
`5,619,020 A
`4/1997 Jones eta!.
`5,621,656 A
`4/1997 Langley
`5,625,697 A
`4/1997 Bowen eta!.
`4/1997 Goldburg et a!.
`5,625,880 A
`5/1997 Ziegler, Jr. et a!.
`5,627,746 A
`5,627,799 A
`5/1997 Hoshuyama
`5,638,022 A
`6/1997 Eatwell
`5,638,454 A
`6/1997 Jones eta!.
`5,638,456 A
`6/1997 Conley eta!.
`5,642,353 A
`6/1997 Roy, III et a!.
`
`.............. 704/229
`
`7/1997 Ikeda
`5,644,641 A
`7/1997 Gifford et a!.
`5,649,018 A
`7/1997 Eatwell
`5,652,770 A
`7/1997 Ross eta!.
`5,652,799 A
`8/1997 Crow
`5,657,393 A
`9/1997 Chu eta!.
`5,664,021 A
`9/1997 Ohashi
`5,668,747 A
`5,668,927 A * 9/1997 Chan eta!. ................. 704/240
`5,673,325 A
`9/1997 Andrea eta!.
`5,676,353 A
`10/1997 Jones eta!.
`5,689,572 A
`11/1997 Ohki eta!.
`5,692,053 A
`11/1997 Fuller eta!.
`5,692,054 A
`11/1997 Parrella et a!.
`5,699,436 A
`12/1997 Claybaugh et a!.
`5,701,344 A
`12/1997 Wakui
`5,706,394 A * 1!1998 Wynn ......................... 704/219
`5,715,319 A
`2/1998 Chu
`5,715,321 A
`2/1998 Andrea eta!.
`5,719,945 A
`2/1998 Fuller eta!.
`5,724,270 A
`3/1998 Posch
`5,727,073 A
`3/1998 Ikeda
`5,732,143 A
`3/1998 Andrea eta!.
`5,745,581 A
`4/1998 Eatwell eta!.
`5,748,749 A
`5/1998 Miller eta!.
`5,768,473 A
`6/1998 Eatwell eta!.
`6/1998 Houser eta!.
`5,774,859 A
`5,787,259 A * 7/1998 Haroun eta!. .............. 709/253
`5,798,983 A
`8/1998 Kuhn eta!.
`9/1998 Ross eta!.
`5,812,682 A
`5,815,582 A
`9/1998 Claybaugh et a!.
`5,818,948 A * 10/1998 Gulick ........................ 381/77
`5,825,897 A
`10/1998 Andrea eta!.
`5,825,898 A
`10/1998 Marash
`5,828,768 A
`10/1998 Eatwell eta!.
`5,835,608 A
`11/1998 Warnaka et a!.
`5,838,805 A
`11/1998 Warnaka et a!.
`3/1999 Czarnecki et a!.
`5,874,918 A
`5,909,495 A
`6/1999 Andrea
`5,914,877 A * 6/1999 Gulick .................. 364/400.01
`5,914,912 A
`6/1999 Yang
`5,995,150 A * 11/1999 Hsieh et a!.
`
`................ 348/409
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`EP
`FR
`GB
`GB
`GB
`GB
`GB
`GB
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`wo
`wo
`wo
`wo
`wo
`wo
`wo
`
`0 583 900 A1
`0 595 457 A1
`0 721 251
`0 724 415
`2305909
`1 160 431
`1 289 993
`1 378 294
`2 172 769 A
`2 239 971 B
`2 289 593 A
`56-89194
`59-64994
`62-189898
`1-149695
`1-314098
`2-070152
`3-169199
`3-231599
`4-16900
`wo 88/09512
`wo 92/05538
`wo 92/17019
`wo 94/16517
`wo 95/08906
`wo 96/15541
`wo 97/23068
`
`2/1994
`5/1994
`7/1996
`11/1996
`10/1976
`8/1969
`9/1972
`12/1974
`9/1986
`7/1991
`11/1995
`7/1981
`4/1984
`8/1987
`6/1989
`12/1989
`3/1990
`7/1991
`10/1991
`1!1992
`12/1988
`4/1992
`10/1992
`7/1994
`3/1995
`5/1996
`6/1997
`
`Petitioner Apple Inc.
`Ex. 1001, p. 3
`
`
`
`US 6,363,345 Bl
`Page 4
`
`01HER PUBLICATIONS
`
`Edward J. Foster, "Switched on Silence", Popular Science,
`1994, p. 33.
`Kuo, Automatic Control of Systems, pp. 504--585.
`Luenberger, Optimization by Vector Space Method, pp.
`134--138.
`Ogata, Modern Control Engineering, pp. 474-508.
`Oppenheim Schafer, Digital Signal Processing (Prentice
`Hall) pp. 542-545.
`P.P. Vaidyanathan, "Multirate Digital Filters, Filter Banks,
`Polyphase Networks, and Applications; A Tutorial," IEEE
`Proc., vol. 78, No. 1, Jan. 1990.
`P.P. Vaidyanathan, "Quadrature Mirror Filter Banks,
`M-band Extensions and Perfect-Reconstruction Tech(cid:173)
`niques," IEEE ASSP Magazine, Jul. 1987, pp. 4-20.
`Rabiner et al., IEEE Trans. on Aeons., vol. ASSP-24, No. 5,
`Oct. 1976, pp. 399-418.
`
`Rubiner et al., Digital Processing of Speech Signals (Pren(cid:173)
`tice Hall, 1978) pp. 130-135.
`Sapontis, Probability, Lambda Variables and Structural
`Processes, pp. 467-474.
`Scott C. Douglas, "A Family of Normalized LMS Algo(cid:173)
`rithms," IEEE Signal Proc. Letters, vol. 1, No.3, Mar. 1994.
`Sewald et al., "Application of ... Beamforming to Reject
`Turbulence Noise in Airducts," IEEE ICASSP vol. 5, No.
`CONF-21, May 7, 1996, pp. 2734-2737.
`White, Moving-Coil Earphone Design, 1963, pp. 188-194.
`Widrow et al., "Adaptive Noise Canceling: Principles and
`Applications," Proc. IEEE, vol. 63, No. 12, Dec. 1975, pp.
`1692-1716.
`Youla et al., IEEE Trans. on Aeons., vol. MI-l, No.2, Oct.
`1982, pp. 81-101.
`
`* cited by examiner
`
`Petitioner Apple Inc.
`Ex. 1001, p. 4
`
`
`
`1--"
`~
`(It
`~
`~
`~
`~
`0'1
`rJ'l
`
`e
`
`'"""' c
`'"""' 0 ......,
`~ .....
`'JJ. =(cid:173)~
`
`N c c
`
`N
`
`~~
`N
`~ :-:
`~
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`118
`~
`
`Samples
`Output
`
`1-1--~
`
`FIG. 1
`
`Spectral Subtraction System
`
`< 116
`
`100
`
`< 114
`
`112 (200)
`
`(
`
`110
`?
`
`Petitioner Apple Inc.
`Ex. 1001, p. 5
`
`Sum
`512PointHNoise HIFFTHAnd
`Overlap
`
`Processing
`
`'-' --l•~l FFT
`
`I -
`
`Window
`Hanning
`By
`Multiply
`
`256 History
`Point with
`256 New
`Combine
`
`Data
`Input
`Collect
`
`108
`Coefficients
`Shading
`
`106
`
`104
`
`Samples-
`Input
`~
`102
`
`
`
`1--"
`~
`(It
`~
`~
`~
`~
`0'1
`rJ'l
`
`e
`
`"""' c
`0 .....,
`N
`~ ......
`'JJ. =(cid:173)~
`
`N c c
`
`N
`
`~~
`N
`~ :-:
`~
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`218
`
`216
`
`--
`
`Estimation
`Noise
`
`-
`
`(300)
`
`• 21~
`
`,,
`
`Y(n)t0.3+Y(n)t_1 *0. 7
`Y(n)=
`
`2~8
`
`FIG. 2
`
`Noise Processing
`
`Petitioner Apple Inc.
`Ex. 1001, p. 6
`
`Process
`Subtraction
`
`2>0 t
`
`-Process
`-Residual
`t
`
`1/3[Y(n-1 )+Y(n)+Y(n+1 )]
`
`+0.4*Min[R(n),l(n)]
`Y(n)=Max[R(n),l(n)] __. Y(n)=
`~
`204
`
`>
`206
`
`2(1)(114)
`
`R(n) I(
`
`R(O) I(
`
`202
`
`
`
`1--"
`~
`(It
`~
`~
`~
`~
`0'1
`rJ'l
`
`e
`
`'"""' c
`0 ......,
`~
`
`~ .....
`'JJ. =-~
`
`N c c
`
`N
`
`~~
`N
`~ :-:
`~
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`Bin(n)
`For
`Level
`Noise
`<
`312
`
`FIG. 3
`
`Noise Estimation Process
`
`310
`
`308
`
`Petitioner Apple Inc.
`Ex. 1001, p. 7
`
`Every 5 Seconds
`I nit With Future Min
`
`Every 5 Seconds
`I nit With Y(n)
`
`f--
`
`5 Sec
`Min Over
`Search For
`Future Minimum
`
`.
`
`304
`
`300 (212)
`
`Y(n)
`
`Y(O)
`
`302
`
`f--. 0.05*New Data+
`
`0.95*N(n)
`
`N(n)=
`
`~306
`
`' lf[Y(n)>
`
`Discard
`4*Min]
`
`5 Sec
`Min Over
`Search For
`Current Minimum 1---
`
`
`
`1--"
`~
`(It
`~
`~
`~
`~
`0'1
`rJ'l
`
`e
`
`'"""' c
`0 ......,
`~
`
`~ .....
`'JJ. =(cid:173)~
`
`N c c
`
`N
`
`~~
`N
`~ :-:
`~
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`FIG. 4
`
`Subtraction Process
`
`Process
`Residual Noise
`-Out To
`
`Out[ I (n )]=In [I (n )]*H (n)
`
`Out[R(n )]=In [R(n )]*H (n) tv404
`
`ln[l(n)]
`
`ln[R(n)]
`
`tv402
`
`IY(n)l
`
`IIY(n)l -N(n)l
`
`• H(n) =
`
`Y(n)
`
`N(n)
`
`400 (21 0)
`
`Petitioner Apple Inc.
`Ex. 1001, p. 8
`
`
`
`U.S. Patent
`U.S. Patent
`
`Mar.26,2002
`Mar. 26, 2002
`
`Sheet 5 of 10
`S
`m
`
`US 6,363,345 Bl
`US 6,363,345 B1
`
`Mm:_m.>
`
`5A5._.:3E_:__>_E:MEE£_>>Eva
`
`""'" 0
`LO
`>
`
`momamm
`
`--c
`
`c
`._ ._
`0:::
`
`1-..C
`0
`(..)
`LL
`())
`c
`())
`oc%
`C
`I
`I - c
`:::::l 0
`1--Z
`
`gommqwéoz
`
`.ou_:0E3.
`
`N
`mom
`0
`LO
`>
`
`..c
`())
`(..)
`(..):!::
`·- :s:
`~(f)
`
`GEcom
`
`0
`0
`LO
`
`c ·rn rn
`E c
`.2>
`0
`0U)
`(J)-
`E ~
`·- c 1---
`
`_m:m_mS9:
`
`:_mEOfl_GEE.
`
`
`
`
`
`(])
`()
`0
`L...
`a_
`(])In
`•
`en
`OC)
`Z -
`LL
`m
`::J
`"U
`en
`(])
`0::
`
`rJ) en
`
`mmmooiwm_oz_m:_o_mmm_
`
`m.o_"_
`
`Petitioner Apple Inc.
`Ex. 1001, p. 9
`
`
`
`
`
`U.S. Patent
`
`Mar.26,2002
`
`Sheet 6 of 10
`
`US 6,363,345 Bl
`
`-c -'-"' c
`
`0:::
`
`'-"'
`
`ex:>
`0
`L()
`
`>
`--
`
`v
`c c
`'-"' '-"'
`>-Z
`""
`~v
`
`§I
`
`..................
`c
`
`c -->- z
`
`I.....,C
`0
`(.)
`LL Q)
`c Q)
`oc%
`C
`I.... c
`I
`::I 0
`1-Z
`
`0
`"!""""
`L()
`
`>
`
`E
`Q)
`..
`::I
`. 0. ..c ·- ::I
`(.)
`E a.>
`ro
`a.>--c-
`0:::~~~
`
`(])
`>
`......
`ctS
`c
`!....
`......
`(])
`<(
`en
`en
`(]) <(
`(.)
`0 Lt)
`•
`a... (!)
`(]) -en LL
`0 z
`
`!.....
`
`ctS
`::J
`""0
`en
`(])
`0:::
`
`.........
`
`c - --
`
`.........
`c
`0:::
`
`Petitioner Apple Inc.
`Ex. 1001, p. 10
`
`
`
`U.S. Patent
`
`Mar.26,2002
`
`Sheet 7 of 10
`
`US 6,363,345 Bl
`
`Read Input
`Samples
`
`600
`
`602
`
`Store Data in
`Buffer
`
`604
`
`'
`
`\
`
`608
`
`I
`(
`\
`
`Stored Inputs
`
`Stored Data ,
`
`[R(0-255);1(0-255)]
`
`\
`
`614
`
`I
`\
`
`No-_.,.
`
`Yes
`+
`Move 512 Last
`Points to Processing
`Buffer
`
`Perform 512
`Points FFT
`
`IV 606
`
`IV 610
`
`Store 256
`Significant Complex
`Points in Buffer
`
`tv 612
`
`0
`
`FIG. 6
`
`Petitioner Apple Inc.
`Ex. 1001, p. 11
`
`
`
`U.S. Patent
`
`Mar.26,2002
`
`Sheet 8 of 10
`
`US 6,363,345 Bl
`
`0
`
`702
`
`704
`
`Y(n)=Max[R(n),l(n)]+.,..---i
`0.4*Min[R(n),l(n)]
`
`Stored Data
`[R(0-255); 1(0-255)]
`
`Stored Y(0-255)
`
`Y(n)=
`1/3[Y(n-1)+Y(n)+Y(n+1)]
`
`706
`
`Y(n)1=
`0.3*Y(n)t+0.7*Y(n)t_1
`
`708
`
`714
`
`716
`
`Yes
`
`Yes
`
`718
`
`720
`
`Replace Future
`Minimum With Y(n)
`
`No
`
`Replace Current
`Minimum With Y(n)
`
`lnit Future Minimum
`With Current Y(n)
`
`722
`
`lnit Current Minimum
`ith Future Minimum
`
`726
`
`No
`
`®
`
`FIG. 7
`
`Petitioner Apple Inc.
`Ex. 1001, p. 12
`
`
`
`U.S. Patent
`
`Mar.26,2002
`
`Sheet 9 of 10
`
`US 6,363,345 Bl
`
`802
`
`804
`
`Yes
`
`N(0-255)
`
`N(n)t=
`N(n)t_1 *0.095+
`Y(n)*0.05
`
`806
`
`808
`
`Stored Y(0-255)
`
`H(n)=
`{IIY(n)I-N(n)I}/IY(n)l
`
`N(0-255)
`Buffer
`
`812
`
`814
`
`810
`
`816
`
`Stored Out
`[R(0-255 ), 1(0-255)]
`
`Out[R(n),l(n)]=
`H(n)*ln[R(n), l(n)]
`
`Stored Data
`[R(0-255); 1(0-255)]
`
`818
`
`820
`
`Yes
`
`Decay [R(n),l(n)]
`
`FIG. 8
`
`Petitioner Apple Inc.
`Ex. 1001, p. 13
`
`
`
`U.S. Patent
`
`Mar.26,2002
`
`Sheet 10 of 10
`
`US 6,363,345 Bl
`
`900
`<
`
`(
`
`\
`
`Stored IFFT
`Results
`
`902
`2
`
`+
`Perform IFFT
`
`I
`
`\
`
`904
`2
`
`(
`
`\
`
`Stored Out
`[R(0-255), 1(0-255)]
`
`I
`
`\
`
`Sum First 256 Points 'V906
`With
`Previous Last 256
`Points
`
`Out
`
`FIG. 9
`
`Petitioner Apple Inc.
`Ex. 1001, p. 14
`
`
`
`US 6,363,345 Bl
`
`1
`SYSTEM, METHOD AND APPARATUS FOR
`CANCELLING NOISE
`
`RELATED APPLICATIONS INCORPORATED
`BY REFERENCE
`
`The following applications and patent(s) are cited and
`hereby herein incorporated by reference: U.S. patent Ser.
`No. 09/130,923 filed Aug. 6, 1998, U.S. patent Ser. No.
`09/055,709 filed Apr. 7, 1998, U.S. patent Ser. No. 09!059,
`503 filed Apr. 13, 1998, U.S. patent Ser. No. 08/840,159 filed
`Apr. 14,1997, U.S. patent Ser. No. 09/130,923 filed Aug. 6,
`1998, U.S. patent Ser. No. 08/672,899 now issued U.S. Pat.
`No. 5,825,898 issued Oct. 20, 1998. And, all documents
`cited herein are incorporated herein by reference, as are
`documents cited or referenced in documents cited herein.
`
`FIELD OF THE INVENTION
`
`The present invention relates to noise cancellation and
`reduction and, more specifically, to noise cancellation and
`reduction using spectral subtraction.
`
`BACKGROUND OF THE INVENTION
`
`5
`
`15
`
`2
`correlated with the speech signal. The spectral subtraction
`method, however, creates artifacts, sometimes described as
`musical noise, that may reduce the performance of the
`speech algorithm (such as vocoders or voice activation) if
`the spectral subtraction is uncontrolled. In addition, the
`spectral subtraction method assumes erroneously that the
`voice switch accurately detects the presence of speech and
`locates the non-speech time intervals. This assumption is
`reasonable for off-line systems but difficult to achieve or
`10 obtain in real time systems.
`More particularly, the noise magnitude spectrum is esti(cid:173)
`mated by performing an FFT of 256 points of the non-speech
`time intervals and computing the energy of each frequency
`bin. The FFT is performed after the time domain signal is
`multiplied by a shading window (Hanning or other) with an
`overlap of 50%. The energy of each frequency bin is
`averaged with neighboring FFT time frames. The number of
`frames is not determined but depends on the stability of the
`noise. For a stationary noise, it is preferred that many frames
`20 are averaged to obtain better noise estimation. For a non(cid:173)
`stationary noise, a long averaging may be harmful.
`Problematically, there is no means to know a-priori whether
`the noise is stationary or non-stationary.
`Assuming the noise magnitude spectrum estimation is
`calculated, the input signal is multiplied by a shading
`window (Hanning or other), an FFT is performed (256
`points or other) with an overlap of 50% and the magnitude
`of each bin is averaged over 2-3 FFT frames. The noise
`magnitude spectrum is then subtracted from the signal
`30 magnitude. If the result is negative, the value is replaced by
`a zero (Half Wave Rectification). It is recommended,
`however, to further reduce the residual noise present during
`non-speech intervals by replacing low values with a mini(cid:173)
`mum value (or zero) or by attenuating the residual noise by
`35 30 dB. The resulting output is the noise free magnitude
`spectrum.
`The spectral complex data is reconstructed by applying
`the phase information of the relevant bin of the signal's FFT
`with the noise free magnitude. An IFFT process is then
`performed on the complex data to obtain the noise free time
`domain data. The time domain results are overlapped and
`summed with the previous frame's results to compensate for
`the overlap process of the FFT.
`There are several problems associated with the system
`described. First, the system assumes that there is a prior
`knowledge of the speech and non-speech time intervals. A
`voice switch is not practical to detect those periods.
`Theoretically, a voice switch detects the presence of the
`50 speech by measuring the energy level and comparing it to a
`threshold. If the threshold is too high, there is a risk that
`some voice time intervals might be regarded as a non-speech
`time interval and the system will regard voice information as
`noise. The result is voice distortion, especially in poor signal
`55 to noise ratio cases. If, on the other hand, the threshold is too
`low, there is a risk that the non-speech intervals will be too
`short especially in poor signal to noise ratio cases and in
`cases where the voice is continuous with little intermission.
`Another problem is that the magnitude calculation of the
`FFT result is quite complex. This involves square and square
`root calculations which are very expensive in terms of
`computation load. Yet another problem is the association of
`the phase information to the noise free magnitude spectrum
`in order to obtain the information for the IFFT. This process
`requires the calculation of the phase, the storage of the
`information, and applying the information to the magnitude
`data-all are expensive in terms of computation and
`
`Ambient noise added to speech degrades the performance
`of speech processing algorithms. Such processing alga- 25
`rithms may include dictation, voice activation, voice com(cid:173)
`pression and other systems. In such systems, it is desired to
`reduce the noise and improve the signal to noise ratio (SIN
`ratio) without effecting the speech and its characteristics.
`Near field noise canceling microphones provide a satis(cid:173)
`factory solution but require that the microphone in the
`proximity of the voice source (e.g., mouth). In many cases,
`this is achieved by mounting the microphone on a boom of
`a headset which situates the microphone at the end of a
`boom proximate the mouth of the wearer. However, the
`headset has proven to be either uncomfortable to wear or too
`restricting for operation in, for example, an automobile.
`Microphone array technology in general, and adaptive
`beamforming arrays in particular, handle severe directional 40
`noises in the most efficient way. These systems map the
`noise field and create nulls towards the noise sources. The
`number of nulls is limited by the number of microphone
`elements and processing power. Such arrays have the benefit
`of hands-free operation without the necessity of a headset. 45
`However, when the noise sources are diffused, the per(cid:173)
`formance of the adaptive system will be reduced to the
`performance of a regular delay and sum microphone array,
`which is not always satisfactory. This is the case where the
`environment is quite reverberant, such as when the noises
`are strongly reflected from the walls of a room and reach the
`array from an infinite number of directions. Such is also the
`case in a car environment for some of the noises radiated
`from the car chassis.
`
`OBJECTS AND SUMMARY OF THE
`INVENTION
`
`The spectral subtraction technique provides a solution to
`further reduce the noise by estimating the noise magnitude
`spectrum of the polluted signal. The technique estimates the 60
`magnitude spectral level of the noise by measuring it during
`non-speech time intervals detected by a voice switch, and
`then subtracting the noise magnitude spectrum from the
`signal. This method, described in detail in Suppression of
`Acoustic Noise in Speech Using Spectral Subtraction, 65
`(Steven F Boll, IEEE ASSP-27 N0.2 April, 1979), achieves
`good results for stationary diffused noises that are not
`
`Petitioner Apple Inc.
`Ex. 1001, p. 15
`
`
`
`US 6,363,345 Bl
`
`4
`ciated that, since the noise elements are determined within
`continuous speech segments, the noise estimation is accurate
`and it may be canceled from the audio signal continuously
`providing excellent noise cancellation characteristics.
`The present invention also provides a residual noise
`reduction process for reducing the residual noise remaining
`after noise cancellation. The residual noise is reduced by
`zeroing the non-speech segments, e.g., within the continuous
`speech, or decaying the non-speech segments. A voice
`10 switch may be used or another threshold detector which
`detects the non-speech segments in the time-domain.
`The present invention is applicable with various noise
`canceling systems including, but not limited to, those sys(cid:173)
`tems described in the U.S. patent applications incorporated
`15 herein by reference. The present invention, for example, is
`applicable with the adaptive beamforming array. In addition,
`the present invention may be embodied as a computer
`program for driving a computer processor either installed as
`application software or as hardware.
`
`20
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`3
`memory requirements. Another problem is the estimation of
`the noise spectral magnitude. The FFT process is a poor and
`unstable estimator of energy. The averaging-over-time of
`frames contributes insufficiently to the stability. Shortening
`the length of the FFT results in a wider bandwidth of each 5
`bin and better stability but reduces the performance of the
`system. Averaging-over-time, moreover, smears the data
`and, for this reason, cannot be extended to more than a few
`frames. This means that the noise estimation process pro(cid:173)
`posed is not sufficiently stable.
`It is therefore an object of this invention to provide a
`spectral subtraction system that has a simple, yet efficient
`mechanism, to estimate the noise magnitude spectrum even
`in poor signal-to-noise ratio situations and in continuous fast
`speech cases.
`It is another object of this invention to provide an efficient
`mechanism that can perform the magnitude estimation with
`little cost, and will overcome the problem of phase associa(cid:173)
`tion.
`It is yet another object of this invention to provide a stable
`mechanism to estimate the noise spectral magnitude without
`the smearing of the data.
`In accordance with the foregoing objectives, the present
`invention provides a system that correctly determines the
`non-speech segments of the audio signal thereby preventing
`erroneous processing of the noise canceling signal during
`the speech segments. In the preferred embodiment, the
`present invention obviates the need for a voice switch by
`precisely determining the non-speech segments using a 30
`separate threshold detector for each frequency bin. The
`threshold detector precisely detects the positions of the noise
`elements, even within continuous speech segments, by
`determining whether frequency spectrum elements, or bins,
`of the input signal are within a threshold set according to a
`minimum value of the frequency spectrum elements over a
`preset period of time. More precisely, current and future
`minimum values of the frequency spectrum elements. Thus,
`for each syllable, the energy of the noise elements is
`determined by a separate threshold determination without 40
`examination of the overall signal energy thereby providing
`good and stable estimation of the noise. In addition, the
`system preferably sets the threshold continuously and resets
`the threshold within a predetermined period of time of, for
`example, five seconds.
`In order to reduce complex calculations, it is preferred in
`the present invention to obtain an estimate of the magnitude
`of the input audio signal using a multiplying combination of
`the real and imaginary parts of the input in accordance with,
`for example, the higher and the lower values of the real and 50
`imaginary parts of the signal. In order to further reduce
`instability of the spectral estimation, a two-dimensional
`(2D) smoothing process is applied to the signal estimation.
`A two-step smoothing function using first neighboring fre(cid:173)
`quency bins in each time frame then applying an exponential 55
`time average effecting an average over time for each fre(cid:173)
`quency bin produces excellent results.
`In order to reduce the complexity of determining the
`phase of the frequency bins during subtraction to thereby
`align the phases of the subtracting elements, the present
`invention applies a filter multiplication to effect the subtrac(cid:173)
`tion. The filter function, a Weiner filter function for example,
`or an approximation of the Weiner filter is multiplied by the
`complex data of the frequency domain audio signal. The
`filter function may effect a full-wave rectification, or a 65
`half-wave rectification for otherwise negative results of the
`subtraction process or simple subtraction. It will be appre-
`
`35
`
`Other objects, features and advantages according to the
`present invention will become apparent from the following
`25 detailed description of the illustrated embodiments when
`read in conjunction with the accompanying drawings in
`which corresponding components are identified by the same
`reference numerals.
`FIG. 1 illustrates the present invention;
`FIG. 2 illustrates the noise processing of the present
`invention;
`FIG. 3 illustrates the noise estimation processing of the
`present invention;
`FIG. 4 illustrates the subtraction processing of the present
`invention;
`FIG. 5 illustrates the residual noise processing of the
`present invention;
`FIG. SA illustrates a variant of the residual noise process-
`ing of the present invention;
`FIG. 6 illustrates a flow diagram of the present invention;
`FIG. 7 illustrates a flow diagram of the present invention;
`FIG. 8 illustrates a flow diagram of the present invention;
`and
`FIG. 9 illustrates a flow diagram o