# Audio Fingerprint Extraction Based on Locally Linear Embedding for Audio Retrieval System
## 2 Audio Fingerprint Extraction Based on LLE
### Audio Fingerprint Extraction
The algorithm needs to first obtain the reconstruction weights of the sample frame in the neighborhood, and then solve the mapping of the sample in the low-dimensional space according to the principle that the reconstruction weights remains unchanged equally to minimize the loss. The method in this paper fully considers the linear relationship between sample frames which corresponds to the time sequence structure of audio signals, and describes the essential characteristics of the data in the low dimension with the minimal feature loss. We reduce the dimension of the energy vector of audio signals belonging to the same group of sub-regions which also reduce the amount of energy involved in fingerprint calculation. The new energy vector is used to extract low dimensional fingerprints by comparing the adjacent energies. (i) Selection of \(K\) nearest frames  
The calculation is closely related to the group of its sub-regions. Therefore, the processed data is the energy vector composed of all the sub-regions' energies of an audio frame in a same group which is denoted as \(\mathbf{e_{m}}\) mentioned above. Assuming that there are \(M\) frames in the given audio data, the MASK region of each frame has four groups of sub-regions and \(L\) energies are calculated in a single group (\(L=4\) or \(8\)) which forms an energy matrix with \(M\)\(L\)-dimensional data \(\mathbf{E}=[\mathbf{e_{1}},\mathbf{e_{2}},\ldots,\mathbf{e_{M}}]\). The algorithm selects \(K\) nearest frames by finding the results with minimum Euclidean distance between the \(m\)-th energy vector \(\mathbf{e_{m}}\) and other data in matrix \(\mathbf{E}\). The results are arranged in ascending order of Euclidean distance and represented as \(\mathbf{\Theta}=\{\eta_{1},\eta_{2},\ldots,\eta_{K}\}\) where \(\eta_{K}\) is the \(k\)-th nearest energy vector of \(\mathbf{e_{m}}\) and the value range of \(K\) is from \(3\) to \(8\) which can ensure the efficiency and prevent the complexity from becoming too high. However, if we only use Euclidean distance to select the proximities, it inevitably occurs that two frames are too far apart in time. In practical conditions, it is obviously unreasonable for two frames that are not related in information to be determined as proximity. In order to ensure that the times span of the nearest selection results is not too long and in view of the upper end of the \(K\)'s value range is \(8\), this paper limits the range of selection within \(10\) frames (five before and five after) which  
Figure 4: 4 layers of sub-region division. Equation (9) formally conforms to the definition of matrix eigenvalues and eigenvectors. Thus, the optimization result of this paper is a matrix composed of the eigenvectors corresponding to the smallest \(d\) non-0 eigenvalues of matrix \(\mathbf{D}\) (\(d<L\)). Until now, the algorithm has obtained a new energy vector \(e^{\prime}_{m}=[e^{\prime}_{m1},e^{\prime}_{m2},\ldots,e^{\prime}_{md}]\) and the number of vector is still \(M\) corresponding the \(M\) frames audio signal. But the dimension of the elements reduces from \(L\) to \(d\) reflecting the reduction of sub-regions' energy. Finally, the audio fingerprints are extracted by comparing the energies in adjacent sub-regions as follow. \[F(m,i)=\left\{ \begin{array}{ll}1,\ if\ e^{\prime}_{m,i+1}-e^{\prime}_{m,i}>0 \\ 0,\ if\ e^{\prime}_{m,i+1}-e^{\prime}_{m,i}<0\end{array} \right.,\ i=1,2,\ldots,d-1 \tag{10}\]  
where \(e^{\prime}_{m,i}\) is the energy of \(i\)-th sub-region in the \(m\)-th frame, \(F(m,i)\) is the \(i\)-th bit of the fingerprint in one of the sub-region group and the fingerprints in other groups can also be computed in the same way. By changing the \(d\) and observing the retrieval results, the limitation of dimensionality reduction in a single group can be determined.