# Audio Fingerprint Extraction Based on Locally Linear Embedding for Audio Retrieval System
## 2 Audio Fingerprint Extraction Based on LLE
### Audio Fingerprint Extraction  
(1) Maximum Spectral Points Extraction  
The discrete Fourier transform (DFT) is applied to the pre-processed audio signal and the spectrum is divided into 18 bands. In this work, we select a peak which has the maximum amplitude for each frame recording its current frame number and band number. To maintain a wide time coverage the number of selected peaks should be in the range of 70 to 100 samples. (2) MASK Region Construction  
After the peak selection step, two index sets of data is obtained, namely the frame index and frequency band index where the selected peak of each frame is located, which is equivalent to the coordinate information of each salient point. Then these data are used to construct MASK regions centered by each selected peak, so there should be one MASK region for each frame. The region covers  
Figure 2: Block diagram of audio fingerprint extraction based on LLE. five frequency bands (one located band, two bands above, and two bands below) and the time span is 19 frames (one located frame, nine frames before, and nine frames after). It is worth mentioning that overlaps are allowed between regions with different peaks during the construction process. To prevent peaks from appearing at the band boundary, the first and last two bands are not used as a selection area so there is no case where a region is built out of scope. Supposing that the peak is in \(n\)-th band of \(m\)-th frame and its MASK region is shown in Figure 3. Note that the frequency bands and time frames are distributed symmetrically. The MASK region is represented as a grid range of \(5\times 19\), and the ordinate has five frequency bands and the abscissa consists of 19 time frames. (3) Sub-region Division  
The MASK region is divided into 4 groups of sub-regions as shown in Figure 4. The four groups of sub-regions are defined as follows: the first group is horizontal sub-regions which corresponds to 1a-1h; the second group is vertical sub-regions including 2a-2d; the third group represents central sub-regions with 3a-3d; the fourth group represent marginal sub-regions in the form of 4a-4h. It can be seen that the horizontal and marginal groups have eight sub-regions, while the vertical and central groups have four sub-regions. All of them correspond to the same number of energies which represented as \(L\) (\(L=4\) or \(8\)). Then the energies of these sub-regions are calculated and the energy vector of a single group is denoted as \(\mathbf{e_{m}^{\mathrm{H}}}\), \(\mathbf{e_{m}^{\mathrm{V}}}\), \(\mathbf{e_{m}^{\mathrm{C}}}\) and \(\mathbf{e_{m}^{\mathrm{M}}}\) which means the energy vector of horizontal, vertical, central and marginal group in that order. We take \(\mathbf{e_{m}}=[e_{m1},e_{m2},\dots,e_{mL}]\) to uniformly present \(\mathbf{e_{m}^{\mathrm{H}}}\), \(\mathbf{e_{m}^{\mathrm{V}}}\), \(\mathbf{e_{m}^{\mathrm{C}}}\), and \(\mathbf{e_{m}^{\mathrm{M}}}\) for simplicity, where \(e_{mll}\) is the energy of \(l\)-th sub-region of \(m\)-th frame and the value of \(L\) depends on the group type. Figure 4: _Cont_. Figure 3: A MASK region centered by a selected peak (red block). (4) Audio Fingerprint Extraction based on LLE  
The dimension of the energy vectors obtained above is still high and the redundancy can be reduced. Thus, in consideration of the relationship of the energies, this paper use LLE to reduce the number of energies of each group respectively and finally extracts smaller fingerprints. LLE algorithm is a typical nonlinear dimensionality reduction method, which considers that the observed data is actually a result of mapping from a low-dimensional space to a high-dimensional space. Due to the internal characteristics of the data, there is redundancy in some high-dimensional data which can be uniquely represented with less data.