# Audio Fingerprint Extraction Based on Locally Linear Embedding for Audio Retrieval System
## 1 Introduction  
With the development of internet technology, people are in an age of information explosion. The amount of audio information increased sharply in 30 years, which means people are exposed to various information every day [1]. For individuals, only a small fraction of it needs to be used, thus, how to obtain the content we want from the numerous audio information sources we are exposed to, namely audio retrieval, is an important problem worth studying [2, 3]. In the field of audio retrieval, high-dimensional audio features reduce the searching efficiency because of their redundancy of information and large storage. These features are computed in the time or frequency domain [4]. For instance, short time energy, linear prediction coefficients (LPC), perceptual linear predictive (PLP), and Mel frequency cepstral coefficient (MFCC) are commonly adopted as audio features [5, 6]. Additionally, the human auditory system (HAS) reflects similarities in auditory perception, so pitch is also used in related research. With the development of audio compression and storage technology, quantities of digital audio information have appeared on the internet which puts forward a higher requirement for the efficiency of audio features and gives rise to audio fingerprinting [7]. Audio fingerprinting can be seen as a short summary of audio signals that is a compact representation of acoustic characteristics [8]. Therefore an audio fingerprint with a limited number ofbits can represent an audio signal consisting of a large amount of data. It is extracted from the most important part of HAS, which has similarities of perception. Meanwhile audio fingerprinting shows higher search efficiency in audio retrieval works. It is widely used in music identification, copyright protection, integrity verification, and other aspects [9]. In a variety of algorithms, the most classic one is Philips' audio fingerprinting algorithm proposed by [PERSON] and [PERSON] [10]. It computes fingerprints by comparing the energies in adjacent bands. The algorithm has high robustness to different kinds of signal degradations and the retrieval performance can be maintained when the audio signal is interfered. Moreover, it has a short granularity of about 3 s, which is the minimum length of an audio segment required for retrieval. The algorithm has low resistance to linear speed changes of the audio signal [11; 12]. Another representative algorithm, named Shazam fingerprinting, proposed by [PERSON] encodes the relationship between every two spectral maxima by using their time and frequency information [13]. It gains better robustness especially under noisy condition, but it uses a large number of bits in its encoding, which reduces the retrieval speed. In addition to the above two common methods, other researchers also introduced wavelet transform into fingerprint extraction [14; 15]. This kind of method can provide time-frequency analysis of the signal which has a good resolution both in time and frequency [16]. It has a high recall rate in audio retrieval, but its accuracy drops when the audio signal is disturbed. In recent years, [PERSON] combined the two methods mentioned above and proposed a novel fingerprint called Masked Audio Spectral Keypoints (MASK) [17]. The algorithm builds regions around selected salient spectral points and generates binary fingerprints by comparing the band energy. Although it has excellent performance of audio retrieval, its fingerprint dimension has room for further reduction. Thus, this paper optimizes the method by extracting a smaller fingerprint. In this paper, an audio fingerprint extraction based on locally linear embedding (LLE) is proposed for audio retrieval system. The method uses LLE to reduce the number of sub-region energies and the reduction reflects in the dimension of fingerprints on account of comparing the energies [18]. In addition, a matching strategy based on dynamic time warping (DTW) is introduced into the system to gain a high resistance against linear speed changes of audio signals [19].