Abstract:
Method and apparatus for generating compact signatures of acoustic signal are disclosed. A method of generating acoustic signal signatures comprises the steps of dividing input signal into multiple frames, computing Fourier transform of each frame, computing difference between non-negative Fourier transform output values for the current frame and non-negative Fourier transform output values for one of previous frames, combining difference values into subgroups, accumulating difference values within a subgroup, combining accumulated subgroup values into groups, and finding an extreme value within each group.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of U.S. Provisional Application No. 61/699,394, filed Sep. 11, 2012. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    The problem of comparing and matching acoustic signals arises in several applications, such as monitoring and identification of music aired on TV or radio broadcasting channels. measuring TV/radio audience, linking online content to a particular audio signals and in some other applications. 
         [0003]    Matching of acoustic signals can be performed via methods of correlation analysis. For example, such approach has been proposed in U.S. Pat. No. 3,919,479 and No. 4,450,531. However, these methods have several drawbacks: 
         [0004]    Firstly, computing correlation of two or more digitized acoustic signals computationally is very CPU intensive. 
         [0005]    Secondly, two acoustic signals, which sound almost identically for human ear, may differ significantly by sound waveforms, because of psychoacoustic properties of human hearing system (insensitivity of human hearing to phase distortions and time-frequency masking effect, etc.) 
         [0006]    Thirdly, in most applications, where the comparison of multiple acoustic signals is needed, the amount of memory required to store the original audio samples can be excessively large. 
         [0007]    To overcome abovementioned drawbacks, one can utilize a method of acoustic signatures (aka, audio fingerprinting). An acoustic signature of audio fragment is a compact set of numerical values, which represents the major psychoacoustic properties of considered fragment. After computation of acoustic signatures the audio fragments can be compared by comparing their corresponding signatures. 
         [0008]    A good audio signature generation method has the following desirable properties:
       It should be insensitive to small audio distortions and transformations (e.g. lossy compression, filtering and so on), that may occur during audio signal distribution via analog or digital media channels   It should be compact to allow storing large arrays of signatures and simplify signature comparisons   It should allow simple generation and cross comparison of signatures with minimal microprocessor usage, which is especially important in mobile applications where the microprocessor capabilities are usually limited       
 
         [0012]    For example, U.S. Pat. No. 7,549,052 discloses a prior art method of deriving a signature from audio signals, which includes the following steps (see also  FIG. 1 ):
       Dividing audio signal fragment into multiple overlapped frames   Calculating Fourier Transform of the frame   Calculating signal energy values for multiple frequency bands E(n,m), where n is the frame index, and m is the frequency band index, m=1, . . . M.   Calculating binary signature value in accordance with simple equation:       
 
         [0000]    
       
         
           
             
               H 
                
               
                 ( 
                 
                   n 
                   , 
                   m 
                 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       1 
                       , 
                       
                         
                           
                             if 
                              
                             
                                 
                             
                              
                             
                               ( 
                               
                                 
                                   E 
                                    
                                   
                                     ( 
                                     
                                       n 
                                       , 
                                       m 
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   E 
                                    
                                   
                                     ( 
                                     
                                       n 
                                       , 
                                       
                                         m 
                                         + 
                                         1 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                           - 
                           
                             ( 
                             
                               
                                 E 
                                  
                                 
                                   ( 
                                   
                                     
                                       n 
                                       - 
                                       1 
                                     
                                     , 
                                     m 
                                   
                                   ) 
                                 
                               
                               - 
                               
                                 E 
                                  
                                 
                                   ( 
                                   
                                     
                                       n 
                                       - 
                                       1 
                                     
                                     , 
                                     
                                       m 
                                       + 
                                       1 
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                         &gt; 
                         0 
                       
                     
                   
                 
                 
                   
                     
                       0 
                       , 
                       
                         
                           
                             if 
                              
                             
                                 
                             
                              
                             
                               ( 
                               
                                 
                                   E 
                                    
                                   
                                     ( 
                                     
                                       n 
                                       , 
                                       m 
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   E 
                                    
                                   
                                     ( 
                                     
                                       n 
                                       , 
                                       
                                         m 
                                         + 
                                         1 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                           - 
                           
                             ( 
                             
                               
                                 E 
                                  
                                 
                                   ( 
                                   
                                     
                                       n 
                                       - 
                                       1 
                                     
                                     , 
                                     m 
                                   
                                   ) 
                                 
                               
                               - 
                               
                                 E 
                                  
                                 
                                   ( 
                                   
                                     
                                       n 
                                       - 
                                       1 
                                     
                                     , 
                                     
                                       m 
                                       + 
                                       1 
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                         ≤ 
                         0 
                       
                     
                   
                 
               
             
           
         
       
     
         [0017]    Generally, this method demonstrates good performance in real-life applications. Nonetheless. it has several drawbacks and limitations:
       Signature size: as suggested in U.S. Pat. No. 7,549,052 and in accordance with our own experiments to achieve robust performance using this prior art method it is necessary to use, at least, 32-bit signature per frame. If the frame interval is equal to 12 ms then the resulting acoustic signature stream is 344 Bytes per second,   Microprocessor intensive direct signature comparison: In particular, the prior art method requires bit-by bit comparison of 32-bit signature words. However, in many mobile CPUs (such as ARM) there is no dedicated hardware instruction to perform such comparison, therefore, counting bit matching should be performed via software procedure, which requires multiple CPU cycles (for example, in ARM microprocessor this requires at least 10 CPU cycles per word).       
 
         [0020]    In the present invention, we propose a new method of generating acoustic signatures, which allows minimizing audio-signature size and reduces CPU resources required for direct signature comparison. Meanwhile, in comparison with known prior art methods, the proposed method demonstrates the same or higher probability of correct detection of noisy and distorted acoustic fragments. 
       BRIEF SUMMARY OF THE INVENTION 
       [0021]    In the proposed method, to generate a compact signature of acoustic signal one should perform the following consecutive steps:
       (1) Firstly, the digitized sound signal shall be divided into (overlapped) frames.   (2) Then (optionally) for each frame the smoothing window function (e.g. Hann window) shall be applied   (3) After that, the Fourier transform (FT) for the current frame shall be computed and the output samples shall be squared.   (4) Then, from each squared FT output value for the current frame the corresponding value for the previous frame shall be subtracted as D(n,k)=X(n,k)=X(n−l,k) where X(n,k) is a squared output of k-th Fourier transform bin for n-th frame.   (5) After that, the differences D(n,k) shall be divided into M groups (m=1,2, . . . ,M) with l subgroups in each group; where each subgroup consists of fixed number (P m ) of difference samples D(n,k).   (6) Values of D(n,k), corresponding to each subgroup shall be accumulated, such that for each group one obtains a set of accumulated values S(n,m,i)   (7) Finally, inside each group m=1,2, . . . , M a subgroup with maximum value of S(n,m,i) shall be found such that       
 
         [0000]    
       
         
           
             
               i 
               m 
               
                 ( 
                 max 
                 ) 
               
             
             = 
             
               
                 max 
                 i 
               
                
               
                 S 
                  
                 
                   ( 
                   
                     n 
                     , 
                     m 
                     , 
                     i 
                   
                   ) 
                 
               
             
           
         
       
     
         [0029]    Here, the set of indexes i m   (max) , m=1, 2, . . . , M is referred to as an acoustic signature of current sound frame. 
         [0030]    The acoustic signature of sound fragment corresponds to the sequence of frame signatures, i.e.: {i 1   (max) (n), . . . , i M   (max) }, {i 1   (max) (n+1), . . . , i M   (max) (n+1)}, {i 1   (max) (n+2), . . . , i M   (max) (n+2)}, . . . 
         [0031]    The comparison and search of audio signatures can be implemented by comparing max. indexes {i 1   (max) (n), . . . , i M   (max) }, {i 1   (max) (n+1), . . . , i M   (max) (n+1)}, {i 1   (max) (n+2), . . . , i M   (max) (n+2)}, . . . of two or more acoustic fragments. During comparison process only a simple fact of matching/not-matching of corresponding indexes i m   (max) (n) shall be detected, and the total number of matching indexes shall be counted. In case of perfect matching of audio fragments composed of N frames, the number of matching acoustic signature indexes shall be N×M. In case of comparing random (uncorrelated) acoustic fragments, an average number of matching indexes shall be approximately: (N×M)/I. Thus, the optimal decision threshold shall be in the range of (N×M)/I . . . N×M, and shall depend upon application requirements for the trade-off between probability of false identification and probability of misdetection of correct signal. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0032]      FIG. 1  shows schematically a prior art circuit arrangement for extracting a signature from acoustic signal 
           [0033]      FIG. 2  shows an arrangement for generating a signature from the acoustic signal in accordance with the present invention. 
           [0034]      FIG. 3  illustrates the principle of grouping Fourier transform bins into subgroups and groups in accordance with the present invention. 
           [0035]      FIG. 4  shows an exemplary embodiment of acoustic signal identification apparatus in accordance with the present invention 
           [0036]      FIG. 5  illustrates identification of reference signature sample in noisy acoustic signal by prior art method and the method in accordance with the present invention 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0037]    The first three steps in the proposed acoustic signature generation scheme that is dividing into overlapped frames, windowing, and Fourier transformation are fairly common for many types of acoustic signal processing tasks. These pre-processing steps are often used in audio classification, speaker identification, voice recognition and so on. The reason behind this is that the frequency domain representation is very convenient for extracting perceptually important signal features. Some of the perceptually motivated features commonly used to characterize acoustic signals are: spectral flux and spectral centroid and spectral peaks. The spectral flux is calculated as: 
         [0000]    
       
         
           
             
               SF 
                
               
                 ( 
                 n 
                 ) 
               
             
             = 
             
               
                 ∑ 
                 
                   k 
                   = 
                   0 
                 
                 K 
               
                
               
                   
               
                
               
                  
                 
                   
                     
                       F 
                        
                       
                         ( 
                         
                           n 
                           , 
                           k 
                         
                         ) 
                       
                     
                     2 
                   
                   - 
                   
                     
                       F 
                        
                       
                         ( 
                         
                           
                             n 
                             - 
                             1 
                           
                           , 
                           k 
                         
                         ) 
                       
                     
                     2 
                   
                 
                  
               
             
           
         
       
     
         [0000]    where F(n,k) is the Fourier transform output for frame n, and frequency bin k. Spectral flux measures how quickly the power spectrum changes. The spectral flux can be used to determine the timbre of an audio signal. Therefore, the spectral flux is the perceptually motivated feature often used in audio classification algorithms. Another perceptually motivated feature, which can be extracted from FT output is the time-frequency distribution of local spectral peaks, where peak is defined as a local maximum of the magnitude spectrum. Finally, the spectral centroid is a measure of spectral shape: 
         [0000]    
       
         
           
             
               SC 
                
               
                 ( 
                 n 
                 ) 
               
             
             = 
             
               
                 
                   ∑ 
                   
                     k 
                     = 
                     0 
                   
                   K 
                 
                  
                 
                     
                 
                  
                 
                   kF 
                    
                   
                     ( 
                     
                       n 
                       , 
                       k 
                     
                     ) 
                   
                 
               
               
                 
                   ∑ 
                   
                     k 
                     = 
                     0 
                   
                   K 
                 
                  
                 
                     
                 
                  
                 
                   F 
                    
                   
                     ( 
                     
                       n 
                       , 
                       k 
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0038]    Although these features are perceptually motivated and often used in audio classification algorithms they cannot be used directly as audio signatures because (a) they characterize signal in general, and (b) they do not allow compact representation using small number of bits. 
         [0039]    In the proposed invention, to achieve the desirable signature properties, the spectral flux is calculated not for entire FT frame, but for local subgroups of frequency bins (steps 4 and 5). The local spectral flux values accurately capture local signal dynamics, but nonetheless they need a lot of bits for storage. 
         [0040]    To reduce the amount of bits needed for signature storage. we propose dividing local spectral flux values into several groups and finding the largest local spectral flux value within each group. The positions of local spectral flux peaks in each frame constitute acoustic signature for this frame. It should be noted that such signature derivation is perceptually motivated since the relative positions of the largest local spectral flux values is one of the most psychoacoustically significant sound characteristics. 
         [0041]    In the preferred embodiment of the invention, it is desirable that the number of subgroups (that is local spectral flux values) in each group be the integer power of two, that is I=2 p . where p is a positive integer. In such a case, to represent a single signature index i m   (max) (n) one would need an optimal (integer) number of bits. The number of samples D(n,k) in each subgroup does not have to be the same, but it is preferred that the number of subgroups per group be the same for all groups. One exemplary group/subgroup arrangement is illustrated in  FIG. 3 . 
         [0042]    We have experimentally discovered that the proposed method with parameters M=8 (number of groups) and I=8 (number of subgroups in each group), in most test cases performs better than known prior art methods, such as one disclosed in U.S. Pat. No. 7,549,052. On the other hand, in the proposed the signature storage requires only N*8*log 2(8)=N*24 bit, versus N*32 bit in [U.S. Pat. No. 7,549,052], that is 25% signature size reduction. 
         [0043]    In addition, the proposed method has one more distinct advantage which is especially important for mobile applications. In mobile platforms, the CPU usually lacks a dedicated hardware instruction to count the number of non-zero bits in a word, such as POPCOUNT (consider, for example, a popular ARM architecture). In this case, a POPCOUNT function is usually implemented in software and requires multiple CPU cycles (e.g., at least, ten cycles in ARM architecture). Therefore, this function becomes a major CPU hog for a signature comparison/search on mobile devices. In a prior art methods, which perform bit-by-bit signature comparison, as for example in abovementioned reference, one such function is required for every frame. On the other hand, in the proposed method, only one POPCOUNT function is required per four (4) frames, if the signature sequence is properly pre-formatted. Therefore, the proposed method allows up to 4 times faster direct signature comparison. 
         [0044]    An exemplary embodiment of acoustic signal identification apparatus in accordance with the present invention is illustrated in  FIG. 4 . In the proposed apparatus, acoustic signatures calculated in signature generation unit  1  are compared with the set of reference signatures #1, . . . , #L, which are pre-computed and stored in device memory. The reference signatures can be fixed or can be updated regularly. The comparison of signatures is performed in L sliding correlators  3 . Finally, the sliding correlator outputs are compared with pre-defined threshold in threshold comparison unit  4  and the signal identification decision is made as a result of such comparison. 
         [0045]    Performance of the proposed method in comparison with the prior art method is illustrated in  FIG. 5 . The lower graph in  FIG. 5(   b ), shows the output of one of sliding correlators in the proposed acoustic signal identification scheme. The input acoustic signal contains highly distorted and noisy sample of reference signal at time t=96 sec. The sliding correlator output produces apparent peak above detection threshold (solid line), corresponding to the false identification probability &lt;10 −7  (d). Conversely, the same noisy signal when passed through prior-art signature correlator with the equivalent parameters does not exhibit any evident drop in bit error rate (BER), as seen in  FIG. 5(   c ). Nevertheless, the proposed scheme requires 25% less storage for signatures and allows faster direct signature comparison. 
         [0046]    It should be pointed out that the acoustic signature generator and the acoustic signal identification apparatus described hereinbefore constitute just preferred embodiments. As an alternative to the embodiment described hereinbefore, values X(n,k) can be obtained by finding absolute value of k-th Fourier transform bin for n-th frame, instead of finding square value. In another embodiment of the present invention the acoustic signatures can be calculated by finding the minimum value of S(n,m,i) inside each group m=1,2, . . . ,M, such that i m   (min) =min S (n,m,i).