{'fraction_non_alphanumeric': 0.04713239780353874, 'fraction_numerical': 0.016524303437055115, 'mean_word_length': 4.462093862815885, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Musical Onset Detection via the S-Transform

Musical onset detection is a key component in any beat tracking system. Existing onset detection methods are based on temporal/spectral analysis, or methods that integrate temporal and spectral information together with statistical estimation and machine learning models. In this paper, we propose a method to localize onset components in music by using the S-transform, and thus, the method is purely based on temporal/spectral data. Unlike the other methods based on temporal/spectral data, which usually rely short time Fourier transform (STFT), our method enables effective isolation of crucial frequency subbands due to the frequency dependent resolution of S-transform. Moreover, numerical results show, even with less computationally intensive steps, the proposed method can closely resemble the performance of more resource intensive statistical estimation based approaches.


I. INTRODUCTION
When a human hears music, an action which is almost subconscious is the rhythmic tapping of the foot. These taps are consistent with the beat of the music and is measured in beats-per-minute (bpm). The process of detecting beat locations in a music is called beat tracking. Beat tracking is a vital step in many studio and live music applications: for example, when a DJ should perform beat matching to play two songs successively. Beat matching is the adjustment of the tempo of one or multiple songs so that their beat locations overlap each other when played simultaneously. The same applies for an audio engineer whenever two instrument tracks are to be played in unison. In this case the audio engineer needs to know the beat locations in both tracks to create a smooth playthrough.
Beat of a music is maintained by a rhythm instrument. A beat usually corresponds to a rapid and unpredictable change in the underlying music signal. Therefore, a primary step in any beat tracking algorithm is to represent such changes, which is referred to as the beat causing onsets (BCO). However, isolating BCOs among others can be challenging.
Existing onset isolation (detection) algorithms, based on temporal and spectral analysis, do not usually yield good results when the beat of a music is not prominent. A primary cause of this is the masking off of important BCO components. Therefore, exploring generalized mechanisms for BCO detection in music, is important in theory, as well as in practice, and therefore deserve investigation. Blending the existing temporal and spectral analysis methods with statistical estimation techniques yields more promising results, however, at the expense of significant computational complexity. Integrating temporal and spectral data of music with machine learning techniques (e.g., neural networks) is apparently the best among others. Such algorithms always rely on a substantial training phase in advance, in order to yield promising results.
In this paper, we propose a method which relies on the Stransform [1] for BCO detection. Unlike the existing methods based on statistical estimation techniques, our method does not rely on any a priori information of the underlying music. Moreover, unlike the state-of-the art machine learning algorithms, the proposed method does not require a training dataset. The proposed algorithm can be considered as a graceful trade-off between the performance and the computational complexity and resources required.
The choice of the S-transform, among other time-frequency representations (TFR), is motivated by the following: 1) The beat causing onsets are usually created by instruments with relatively lower frequencies [2], 2) S-transform provides a good concentration at lower frequencies [1]. 3) S-Transform uses a frequency-dependent window dilation, which results a frequency-dependent resolution [1]. The first two points enable one to extract the power of rhythm instruments effectively. The last point plays a key role in the sense that, unlike the STFT, S-transform is not required to know the window size a priori. This facilitates, irrespective of the underlying frequencies of the rhythm instruments, a general implementation of proposed algorithms.
The rest of the paper is organized as follows. In Section II, we give a literature overview. Section III discusses our proposed algorithms for BCO detection. In Section VII, numerical results are presented. Section VIII concludes the paper.

II. LITERATURE
Several works have been investigated on BCO detection in music [3]- [23]. These can be split into methods based on temporal/spectral analysis, and more sophisticated methods which blend temporal/spectral data together with statistical estimation techniques and machine learning techniques. Temporal and spectral analysis methods generate a time series, usually called the onset envelope function (OEF), which contains information of the locations of BCOs. The OEF is then used to compute the underlying bpm [5]. Methods based on statistical estimation and machine learning techniques rely on more resources, in addition to the pure temporal and spectral data, for locating BCOs, e.g., a priori information of the underlying music, training data sets [16, § 4].
Temporal analysis methods split the signal into frequency bands, for which amplitude envelopes are calculated and summed to obtain an OEF [3], [4]. Spectral analysis methods take into account, the change in spectral energy. These methods usually compute some form of a time-frequency representation (TFR), where the STFT is most common [3], [5], [10], [21], [22]. Different scaling methods such as the Mel [5], [6] and the square root [7] are used to avoid low amplitude components from being masked off. Either the summation [5], [7], the median [6], or the mean [8] is computed of the first order difference for each time bin to obtain an OEF.
A common limitation of the spectral analysis methods mentioned above is the poor detection of BCOs if the rhythm is less pronounced. This is due to masking off of BCO components of interest, or because spectral changes constituting to BCOs have not been identified accurately. This is the case in most classical, opera, soft pop and instrumental music [23]. In addition, the designs can be very sensitive to the algorithm parameters, e.g., window length [24].
The authors of [25] presents a comparison between several onset detection methods which were submitted to the ISMIR 2006 competition [26]. The methods discussed include the works presented by [4], [8], [20], [21] and several others. The authors show that the method proposed by [20], which maneuvers temporal/spectral data, together with statistical estimation techniques, outperforms other methods by a considerable margin.
Methods such as [16]- [19] uses a machine learning based approach where there is no computation of an OEF. Based on recent results of ISMIR [26], the research conducted in [17]- [19] appears to be the best among others. However, for machine learning algorithms, usually the existence of a reasonable training data set is necessary to achieve better accuracies.

III. PROPOSED METHOD, AN OVERVIEW
The proposed method is based on the discrete Stransform [1, § III]. Moreover, the overall method is divided into two sections; 1) Onset envelopes by band spitting.
Recall that the existing methods rely on a single STFT-TFR followed by an associated onset envelope for beat detection. Intuitively, to get the benefits of frequency dependent resolution of S-transform, it is suggestive to split the TFR into several bands and to process different subbands separately [3], [4], [20]. Such a splitting and a processing can avoid or at least minimize the masking off and suppression of desired BCO information from undesired spectral information. Thus, we first consider a band splitting followed by an onset envelope computation for each band ( Figure 1). Note that, of the several onset envelopes present, the beat information may be encoded in some, depending on the rhythm instrument used. The challenge is then to pick the 'best' one that encodes the BCOs of the underlying music. This is the second stage of our proposed method, in particular the onset envelope isolation, see Figure 1.
In the sequel, we discuss in more detail, the computation of onset envelopes by band splitting [cf. § IV] and onset envelope isolation [cf. § V].

IV. ONSET ENVELOPES BY BAND SPITTING
Let us first outline the proposed algorithm for onset envelope computation. We assume that the musical excerpt is provided in mono format.

Algorithm 1
Input: n=0 . • Downsamling factor D, a positive even integer. • Subband size, K such that (N − 1)/D = 2QK − 1 for some positive integer Q. Steps: 1) Downsamling: 3) Compute Discrete S-Transform matrix F ∈ C (M/2)×M , whose (p, n)-th element is given by: Algorithm starts with a sampled musical excerpt denoted by the sequence {x[n]} N −1 n=0 . Note that, the smaller N or the duration T of the musical excerpt is, the lesser the computational burden of the algorithm. Therefore, the duration T can be chosen intelligently for efficient implementation of the algorithm. Note that, the tempo of a music can usually range from 60 bpm to 240 bpm [27]. Therefore, T can be on the order of few seconds to extract useful beat information. For example, even in the worst-case, i.e., when the musical excerpt is of 60 bpm, a T = 4 second musical excerpt can be used to capture 4 beats for further processing.
The downsampling factor D also plays a key role for efficient implementation of the algorithm [cf. step (1)]. In other words, the larger D is, the smaller M , and therefore, the lesser computational burden of the algorithm [cf. step (2), (3)]. A better choice for D can be argued by considering the frequencies of rhythm instruments. Note that the frequencies of rhythm instruments' typically range from 32Hz to 512Hz [28]. Thus, sampling is to be done at a rate no smaller than 1024Hz to avoid aliasing. Therefore, for a musical excerpt sampled at a rate f s = 44100Hz [28], D = 40 corresponds to a sampling frequency 1102.5Hz (≥ 1024Hz) and M = 4410 samples in a T = 4 s period.
The idea of band splitting is essentially to extract the potentials of S-transform in a frequency dependent resolution. Thus, the choice of K is to be such that it is large enough to hold a sufficient spectral energy concentration to emphasize BCO s (if any). On the other hand, K should be small enough to minimize the masking off of important BCO information (if any) from spectral contents within the subband itself. Numerical experiences suggest that a K on the order of 200 for a A concise depiction of our considered TFR, in particular, the absolute discrete S-transform matrix S ∈ R (M/2)×M is shown in Figure 2, together with the considered splitting. Note that the TFR is plotted only for the range 0Hz ≤ f ≤ 551.25Hz and 0 s ≤ t ≤ T s, because the upper frequency band 551.25Hz < f ≤ 1102.5Hz is just a repetition of S.
After having determined S and its splitting [cf. step (3), (4)], step (5) computes the onset envelopes of each subband. The output of the algorithm is the onset envelopes for each subband, which is used by the onset envelope isolation stage.
V. ONSET ENVELOP ISOLATION Given onset envelopes r i ∈ R M , i = 1, . . . , Q, the task of the isolation stage is to choose one envelope that can potentially encode the BCO information. To this end, the key idea is to associate each r i , with a real number b i , so that, the bigger b i is, the higher the likeliness of r i carrying BCO information. Let us first outline the algorithm. Output: • Onset envelope isolation: Otherwise return r i , where the partition index i ∈ I .
The first step is a preconditioning step, where r i is normalized to yieldr i . For an illustration, see Figure 3-(a). It is reasonable to assume that most of the relatively lower level amplitudes ofr i do not carry BCO information. Therefore, we consider only the amplitudes ofr i above some level. More specifically, the level is chosen to be the mean [ Figure 3-(b), dotted curve] of the upper envelope u i [ Figure 3-(b), solid curve] determined at step (2). Step (3) removes the mean aforementioned fromr i to yieldr i , cf. Figure 3-(c).
Note that the upper envelope u i in step (2), computed by using cubic spline interpolation corresponds to some local maxima 2 ofr i whose separation is at least n p ∈ Z samples. For example, Figure 3-(b) shows u i ofr i in Figure 3-(a) for n p = 1.
Step (1), (2), as well as (3) of the algorithm correspond to preconditioning of the input r i . In contrast, step (4) is the key for envelope isolation, which capitalizes on a clustering of components ofr i by using a thresholding mechanism. To see this, first suppose the range of frequencies of the underlying rhythm instrument overlaps with subband i ∈ {1, . . . , Q}. Thus, there is a high potential thatr i contains nonzero components, which correspond to the BCOs. In addition, their neighboring components can also be nonzeros due to the spectral leakage caused by windowing. As a result,r i can resemble a sequence as shown in Figure 3-(c), where there are clusters of nonzero components (nonzero clusters) that are separated by clusters of zero components (zero clusters). For example,r i in Figure 3-(c) has 3 nonzero clusters. Because of the periodicity of BCOs, the 'distance' between consecutive pairs of nonzero clusters should be the same. However, for any subbandī = i, the characteristics of the nonzero clusters mentioned above, do not apply. This is indeed the key to isolate subband i from others. Steps (4)-a to (4)-e, correspond to clustering and the distance computation between consecutive pairs of nonzero clusters ofr i . First, a threshold h is given, cf. step (4)-a and Figure 3-(c). Then components ofr i which are greater than or equal to h is isolated into I, cf. step (4)-b. For example, Figure 3-(c) shows that I = {8, 9, 10, 11, 19, 20, 28, 29, 30}. Step (4)-c partitions I into subsets {I m } Mi m=1 , where each subset corresponds to a nonzero cluster. For example, from Step (4)-d computes the center of gravity of each subset, denoted {I m } Mi m=1 . Particularized to our example, we have I 1 = 9.5, I 2 = 19.5, and I 3 = 29, cf. Figure 3-(d). The distance between consecutive pairs of nonzero clusters are simply given by the (M i − 1)-vector [I 12 , I 23 , . . . , I (Mi−2)(Mi−1) , I (Mi−1)(Mi) ] T , cf. step (4)-e. This is illustrated in Figure 3-(d), where the distance between nonzero cluster 1 and 2 is I 12 and that of nonzero cluster 2 and 3 is I 23 . Finally, recall that the 'distance' between consecutive pairs of nonzero clusters should be the same if r i contains BCOs. Mathematically, this corresponds to a larger inner product of vectors c ij and 1 ∈ R Mi−1 . Therefore, step (4)-e computes such inner products denoted {v ij } D j=1 and step (5) chooses the best. At the end of step (5), associated with each subband, we have a real number b i which characterizes the likeliness of r i containing BCOs. Finally, for the specified isolation accuracy , isolated subband indexes are returned.
Finally, a potential BPM value is computed as for some i ∈ I , where x represents the rounding of x to the nearest integer and length(y) represents the length of vector y.

VI. COMPUTATIONAL COMPLEXITY
A vast majority of the existing methods use the STFT to obtain a TFR. The asymptotic complexity for the STFT is O (N log N ), where N is the samples used in the underlying FFT operations 3 [30].
The discrete S-transform, on the other hand, has an asymptotic complexity of O(N 3 ) [31]. However, by exploiting structural properties, variants of discrete S-transforms, such as fast discrete orthonormal Stockwell transform can be computed, still in O(N log N ) [31, Theorem 6.1].

VII. RESULTS
This section compares the performance of the proposed method with the algorithms documented in [5] and [20], which we consider as benchmarks A and B, respectively. Algorithm in [5] can be considered to be superior among the methods based on pure temporal/spectral analysis methods [26]. On the other hand, the work by [20] is the best among methods that rely on temporal/spectral data, together with statistical estimation.
In our simulations, we consider two publicly available datasets -the Ballroom dataset, and the Songs dataset, which comprise of 698 and 465 song excerpts, respectively [25, § III-B]. The tempo, genre, and style distribution of the datasets are given by [25,§ III].
Note that the sampling rate of each song excerpt is 44.1kHz. A downsampling factor of D = 40, a subband size K = 1103, and Q = 10 subbands are used as inputs to Algorithm 1. In the case of Algorithm 2, we use n p = 40, H = 100, and = 10 −3 . To exemplify the outputs of the proposed algorithms, we fist consider an arbitrarily chosen classical music excerpt in the Songs dataset. Figure 4 shows the output r i , i = 1, . . . , 10 for the considered music excerpt. Results show that r 9 and r 10 can apparently isolate the BCOs. Figure 5 shows v ij versus j for each subband i, i = 1, . . . , Q. Results indicate that v 10j yields values almost close to 1 for some thresholds l j [cf. step (4)-a]. More specifically, Algorithm 2 returns I = {10}, which corresponds to b 10 = 0.999895 [cf. step (5)]. The resulting BPM is 88 [cf. (1)], which is identical to the ground-truth tempo.
To see the performance of the proposed algorithms on average, we ran the algorithms separately for each data set.
As discussed in [25], we considered the same two metrics to measure the accuracy of the system. In particular, we have 3 e.g., the STFT window length. The percentage of tempo estimates within 4% of the ground-truth tempo. • Accuracy 2: The percentage of tempo estimates within 4% of either the ground-truth tempo, or half, double, three times, or one third of the ground-truth tempo. Figure 6 depicts the results of percentage accuracies of the proposed algorithm compared with the two benchmarks. Results show that the proposed method has a better performance than [5]. Note that, this gain can be accomplished with the same computational complexity, cf. § VI. Results further show that the method proposed in [20] is superior to the proposed method. This is not surprising, because, unlike the proposed method, the algorithm in [20] relies on many computationally intensive operations, e.g., filtering, comb filter operations, discrete power spectral estimations, statistical estimation of period and phase of underlying time series within a hidden Markov model, among others. Therefore, results suggest that the proposed method holds an advantage in that it is less computationally intensive than the benchmark [20], yet with a comparable performance. VIII. CONCLUSIONS In this paper, a beat causing onset (BCO) detection method based on the S-transform has been proposed. The method provided an advantage over the approaches that are purely based on classic temporal/spectral analysis. The frequency dependent window dilation used in S-transform has been the key to yield such performances by exploiting better frequency resolution at lower frequencies, where BCOs generally occur. Compared to state-of-the-art algorithms, the proposed method is less resource intensive. For example, our method does not require any a priori information of the underlying music, unlike the statistical estimation based approaches. Moreover, the method does not require training datasets like in the methods based on state-of-the-art machine learning techniques. The result is a graceful trade-off between the performance and the required computational burden and the resources.