Method for extracting representative segments from music

Abstract

A method for extracting the most representative segments of a musical composition, represented by an audio signal, according to which the audio signal is preprocessed by a set of preprocessors, each if which is adapted to identify a rhythmic pattern. The output of the preprocessors that provided the most periodic or rhythmical patterns in the musical composition selected and the musical composition is divided into bars with rhythmic patterns, while iteratively checking and scoring their quality and detecting a section that is a sequence of bars with score above a predetermined threshold. Checking and scoring is iteratively repeated until all sections are detected. Then similarity matrices between all bars that belong to the musical composition are constructed, based on MFCCs of the processed sound, chromograms and the rhythmic patterns. Then equivalent classes of similar sections are extracted along the musical composition. Substantial transitions between sections represented as blocks in the similarity matrices are collected and a representative segment is selected from each class with the highest number of sections.

Claims

1. A method comprising: processing a musical composition by a processor to identify a rhythmic pattern; dividing the musical composition into one or more bars; constructing one or more similarity matrices based at least one of the one or more bars; extracting, from the musical composition, one or more sections; and selecting a representative segment of the musical composition based on at least one of the one or more sections.

2. The method of claim 1, wherein the similarity matrices are constructed using at least one of: a) Mel-Frequency-Cepstrum-Coefficients (MFCCs); b) internal auto-correlation measure; or c) tonal-tuned metric.

3. The method of claim 1, further comprising: dividing the one or more bars into classes in relation to the similarity matrices; dividing the similarity matrices into one or more blocks; and finding a distinctive section in at least one matrix.

4. The method of claim 1, further comprising detecting bar multiplicities.

5. The method of claim 1, further comprising: adjusting boundaries of the a section of the musical composition based on one or more time points that correspond to one or more transitions.

6. The method of claim 5, further comprising adjusting the one or more transitions using a set-size convolution.

7. The method of claim 1, wherein the processor comprises at least one of: a low-pass filter, a waveform preprocessor, or tuning based signal separation.

8. The method of claim 1, further comprising defining a representative bar for a section of the musical composition for approximating a rhythmic pattern.

9. The method of claim 1, further comprising: defining a correlation scale comprising a pair of bars.

10. The method of claim 1, further comprising scoring one or more of the bars.

11. The method of claim 1, further comprising separating stable and unstable frequency components of the musical composition.

12. The method of claim 1, further comprising generating a most representative part of the musical composition.

13. The method of claim 1, wherein a class repeats throughout the musical composition.

14. The method of claim 1, wherein a representative bar is defined by constructing an average-bar.

15. The method of claim 1, further comprising comparing the representative segment to another segment within the musical composition.

16. The method of claim 15, wherein the comparing is performed until a correlation level is degraded.

17. The method of claim 1, further comprising separating one or more frequencies to filter one or more sounds from the musical composition.

18. The method of claim 1, further comprising detecting one or more segments in view of an auto-correlation above a predicted level.

19. A system comprising one or more processors to: select a section from a musical composition; process the section to choose a waveform; perform autocorrelation on the waveform over a determined range; apply a linear estimator in relation to the autocorrelation; and build a representative bar of the section.

20. A method comprising: processing a musical composition by a processor to identify a rhythmic pattern; dividing the musical composition into one or more bars; constructing one or more similarity matrices based on the one or more bars; extracting transitions between the one or more bars; and electing, based on the transitions, a representative segment of the musical composition.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) In the drawings:

(2) FIG. 1 illustrates the process for extracting the most popular and representative segments of a song, according to the present invention;

(3) FIGS. 2A and 3A illustrate the MFCCs matrix of two different pop songs;

(4) FIGS. 2B and 3B illustrate the extracted diagonals of the matrices shown in FIGS. 2A and 3A, respectively;

(5) FIG. 4 illustrates the MFCCs matrix of a Jazz composition;

(6) FIG. 5 illustrates an example of autocorrelation of a song with dominant multiplicity of 8 bars;

(7) FIGS. 6A and 6B illustrate examples of autocorrelation of autocorrelations of low-passed energy of two different songs; and

(8) FIG. 7 illustrates regions of non-typical sections in a similarity matrix.

DETAILED DESCRIPTION OF THE EMBODIMENTS OF THE INVENTION

(9) According to the present invention, a musical file is analyzed in order to generate a Thumbnail that contains examples of both the most representative and most surprising parts of a musical composition. At the first step, a similarity matrix of the given music file is generated by analyzing the file and tagging similar parts, self-similar parts (segments which are similar to themselves), tempo-changes, and surprising elements into equivalent classes. These equivalent classes repeat themselves in different time points along the audio file, for example a chorus or a verse that appears in several time points along the song. At the next step, several relevant parts to be present the user are selected as building blocks for generating a musical thumbnail, which helps the user associating the thumbnail with his preferences and deciding whether or not to listen to the whole file.

(10) Energy Division

(11) According to the method proposed by the present invention, the song is broken into parts that have the same energy level and the point of abrupt changes between adjacent levels is detected. For a given signal, the energy is averaged over short time segmentation (e.g., 2 Sec).

(12) It is desired to find the exact points of change. For each change point, the process goes back to the signal and trims a 4 Sec area from both sides of the roughly estimated change. At the next step, a moving average M(t) is applied with the same segmentation as started. At the next step, the function

(13) $P\left(t\right)=\frac{M\left(t\right)}{M\left(t-l\right)}$

(14) Where l is the number of samples of the segmentation used. The term Max(P(t)) provides the desired correction. Readjusting these change moments allows locating the Downbeat (the first beat of a measure, which generally has the highest energy density of the bass frequencies of the composition).

(15) Energy distribution over any scale may be used to define that musical scale (e.g., western or Indian musical track), as well as the genre.

(16) FIG. 5 illustrates an example of autocorrelation of the song cry me a river of the performer Justin Timberlake with detected dominant multiplicity of 8 bars. The energy levels are equally spaced peaks, which show how much the signal that is sampled in 44.1 Khz rate is similar to itself in different shifts. The x axis represents time*the sampling frequency and the y axis represents energy levels, while the highest peak (not normalized) is obtained with no shift. The peak levels drop linearly along line 50, as the similarity is degraded from bar to bar. As seen, there are 3 peaks 51, 52 and 53 that exceed the energy levels bounded by line 50. These peaks correspond to higher periodicity of the rhythmic pattern, while the 8.sup.th peak provides the highest energy. Thus, the rhythmic pattern is repeated after 8 bars.

(17) FIGS. 6A and 6B illustrate examples of autocorrelation of autocorrelations of low-passed energy from seconds 40 to 50, of two different songs. FIG. 6A shows the autocorrelations of the song A day in life with high rhythmical score. As seen from FIG. 6A, most of the peaks exceed the median energy level 61 (taken with respect to the highest peak 62. Thus, the rhythmic pattern of this song has a high score.

(18) FIG. 6B shows the autocorrelations of the album Rio of Duran Duran, with low (Drone-like) rhythmical score. As seen from FIG. 6B, most of the peaks do not exceed the median energy level 63 (taken with respect to the highest peak 64. Thus, the rhythmic pattern of this song has a low score.

(19) Bar Units Division, BPM Extraction and Rhythmical Patterns Segmentation:

(20) Three types of rhythmical divisions are extracted according to the process proposed by the present invention. Musical bars units are the short time rhythmic repetitions along the track. This process takes into consideration that bar units may change in their length, during the whole song. Musical bars units might change abruptly, or while accelerating or slowing down. Yet, the basic assumption of local periodicity of the rhythmical waveform (any waveform preprocessing which produces waveform with local periodicity) is valid for most cases. The local length of the bar unit induces the local shape of the repetitive rhythmic waveform. This feature is the local rhythmical pattern of the bar. Analyzing the rhythmical bar pattern reveals the local Beats Per Minute (BPM). Moreover, marking the moment where rhythmical bar patterns substantially change allow obtaining the rhythmical patterns segmentation, i.e., segmentation into sections of constant rhythmical patterns of the bar units.

(21) The process seeks a preprocessor which isolates the rhythmic component of the song, using the following tools:

(22) (1) a set of rhythmical waveform preprocessors.

(23) (2) a rhythmical scale function that takes any power waveform and gives a rhythmicity score that represents the local periodicity level of the waveform (in a range of about 0.6-4 sec).

(24) The processing steps are:

(25) 1. At the first step, a short section is selected from the beginning of the song.

(26) 2. At the next step, the set of preprocessors is applied on the selected section.

(27) 3. At the next step, the scale function is used to choose the best rhythmical waveform by scoring. If there isn't any positive score the section is classified as not rhythmical and the process restarts.

(28) 4. At the next step, autocorrelation is performed on the rhythmical waveform and the maximum over the range of 0.6-4 sec is selected. The distance between the inducted maximum and the zero offset will be the static bar length of the section.

(29) 5. At the next step, a linear estimator is applied on the static bar length periods point in the autocorrelation signal and multiplied points which are above the line are taken. Any multiplicity number represents a bars multiplicity of the section.

(30) 6. At the next step, the static bar length is used to build a representative bar of the section which is defined as the average sum over the n-th static bars contained in the section.

(31) 7. At the next step, the representative bar is refined by comparing it with each of the n-th static bars using the bar_compare function, defined as

(32) $\mathrm{BarCompare}\left(X,Y\right)=\max \left(\mathrm{cyclicCorrelation}\left(\frac{X}{.Math.X.Math.},\frac{Y}{.Math.Y.Math.},\right)\right),$
and the average is taken over the five best score bars as the new refined representative bar. At this stage, in order to detect the bar units performances, a bar_compare function is defined. This function traces the correlation of the given representative bar along the given rhythmical signal, using the following formula:
Bar_segmentation(s,b)=Cross-correlation(s,b)/convolution(s.sup.2,u)

(33) Where b is the normalized representative bar, s is the compared signal and l is the length of the normalized representative bar b.

(34) The division by convolution (s.sup.2,u) will normalized each offset of the cross-correlation. Therefore, energy difference has no meaning and the only property that matter is the inner energy distribution of the compared signal s on each offset.

(35) 9. At the next step, the correlation signal c is derived and a looseness parameter =0.2 Sec is defined. A local maximum is traced inductively by:

(36) i) finding max over c(1: *fs) and saving the valuev(1), and indexi(1).

(37) ii) Since at the kth step an array k*2 of values and indexes is obtained, max is found over c(*fsi(k):*fs+i(k)) while saving the value in v(k+1) and index in i(k+1).

(38) iii) terminating the process upon either extracting the whole track or getting two consecutive bad scores in the value array.

(39) At this stage, a section of the song, divided into bar units, is obtained. These bar units are locally constant in their length (up to looseness ). Each bar has its value that represents the distance from the rhythmical representative bar.

(40) 10. At the next step, the bad scores bars are saved in the section. The corresponding time points indicate bridges or transitions in the track.

(41) 11. At the next step, the process is repeated starting from the end of the last section.

(42) The above process ends with segmentation into rhythmical patterns sections, each of which contains bar division and a representative bar which represent the rhythmical pattern and shows the BPM. In addition the multiplicity of a bar is extracted (if exists) and the bars with bad score are saved.

(43) Preprocessors Set and Rhythmic Scale Function

(44) As mentioned before, the former process relies on extracting the rhythmical component from the audio track. Therefore we search from the set of preprocessors the suitable one, e.g.preprocessed power waveform that is the most periodic. Let as, then, define our

(45) Rhythmic Scale Function:

(46) Denote Cthe normalized autocorrelation of a given power signals.

(47) Denote also m=max(C(,end)), ithe index of m in C, where =0.2 sec*fs. then

(48) score(s)=1mean(C(,i))/m.

(49) Note that 0<m<1 express the measure of the periodicity (when m=1 gives a perfect period) while our score measure the level of the i period compare to the average of the level of any other periods. This way drone sound (unity distributed waveform) cannot be considered a periodic (even when m tend to 1).

(50) Preprocessor Set:

(51) Attacks Detector Preprocessor:

(52) The signal's power is divided first into energy sections (see Energy division section later). For each section, a creamy layer of the signal is selected. This layer includes samples which exceed a predetermined height (according to some percentile) and their between, for gaps that are small enough.

(53) Separating Between Melodic, Percussive and Vocal Events

(54) There are some typical attributes regarding frequency distribution in western-musical tracks. Firstly, most of the melodic instrument energy is distributed around Equal Tempered frequencies (in an Equal Tempered Scale, which is a musical scale with 12 equal divisions of the octave), such as a logarithmic 12 tone scale based around a pitch of 440 Hz (or any other arbitrary frequency). Secondly, most of the frequency components which are far away from the tuned scale are either non-harmonic resonance frequencies (including some vocal formants, which are spectral peaks of the sound spectrum the voice) or part of percussive events. Thirdly, percussive events are broad-band with different time distribution.

(55) By using spectral frequency-estimation (estimation of frequency components using the complex time derivative of the Short-Term Fourier TransformSTFT, which is a Fourier-related transform used to determine the sinusoidal frequency and phase content of local sections of a signal), it is possible to separate between stable and unstable frequency components across time frames and between tuned and un-tuned frequencies, according to a 12-tone equal temperament (a scale which divides the octave into 12 parts, all of which are equal on a logarithmic scale).

(56) The tuned data (frequency tuning is made around a small fraction neighboring the border line between adjacent parts among these 12 parts) is used for extracting musical notation. Finding the root note (the fundamental note on top of which the intervals of a chord are built) around which the energy is distributed, helps finding the recording's tuning or altering of the playing speed. The separated un-tuned data is used for beat detection, and for correlating timbre or vocal patterns.

(57) Harmonic patches and non-harmonic sounds are filtered by separating frequencies that are located at equal-tempered spots, as well as frequencies that fall within the quartic tone offset. The filters are very narrowband selective logical filters (few Hz), which are determined using Spectral-Frequency-Estimation and are capable of separating between harmonic and noisy (non-harmonic) signals.

(58) Downbeat Location:

(59) The first candidate for the Downbeat location will be the maximum energy point in the low-passed Representative-Bar. When dealing with 4/4 pop music, usually either the 1st or the 3rd beat are found. Another candidate will be the nearest change moment taken from previous measures (such as energy, notation, etc.). The point is projected through the whole section with shifts of the length of the bar.

(60) Quality Scales

(61) Correlation Scale

(62) In order to determine whether a waveform is periodic enough (the rhythmic component), the following scale is performed:

(63) If C be the normalized autocorrelation of the signal's power, i is it's index and m=max(C(, end), the score is given by:

(64) $\begin{array}{cc}=1-\frac{\mathrm{mean}\left(c\left[,i\right]\right)}{m}))& \left[\mathrm{Eq}.2\right]\end{array}$

(65) Where is selected to be samples of 0.1 Sec and m is a positive value such that m>.

(66) Similarity Matrices

(67) The similarity matrices (maps) are generated by both selecting temporal grids and different metrics, which measure musical similarity in different aspects, according to the division to bars, to tempo change detection and to various measures and internal bar tempo-maps that are defined. According to an embodiment of the invention, Time vs. Time similarity matrices are constructed based on these different metrics. The similarity matrix offers pairwise similarity between any two short intervals of fixed length in an analyzed song. Dynamic bar-length (BPM) changes and musical-meter changes are followed and the measured data reflects musical content when the time-division corresponds to the underlying musical temporal intervals.

(68) The metrics used are:

(69) 1. Mel-Frequency-Cepstrum-Coefficients (MFCC)based coefficientsto correspond to the Timbral content of a bar. Specifically, a Mel-scale filter-bank and the Discrete-Cosine-Transform (DCT) of the energy-sum logarithm are taken, together with two-time-derivatives of the above. The result is a vector of coefficients for each bar. The Cosine-Similarity between these vectors, as well as the inverse-cosine of their normalized dot-product, is calculated.
2. Internal Auto-Correlation measurewhich corresponds to the rhythmic signature of the bar. The auto-correlation of each bar's energy levels is calculated, possibly after a preprocessor that has been selected earlier, during the bar division section. The resulting autocorrelation graph corresponds to the bar's internal rhythmic structure, with phase information removed. These graphs are compared with two different metrics:
2a: Approximating the curve via a low number of coefficients: for exampletaking a DCT of the auto-correlation, and keeping the low 80 coefficients. Here also, the normalized coefficients of a bar's energy auto-correlation is taken, and its time derivative (the original autocorrelation pattern should be when sampling at standard 44.1 Khzbetween 15,000 and 70,000 samples. These vectors are mapped from a 70,000 dimensional space to about a 100 dimensional space). Then the Euclidian distance is taken in the new dimension-reduced space. Approximating these curves via Linear Predictive Coding (LPC), using Reflection-Coefficients as the vectors for comparison also yields good result.
2b: Peak-Location in the autocorrelationthe autocorrelation passes a low-pass filter, in order construct a vector of only the dominant peak locations, giving minimal peak height, and a maximal peak distance, so-that 24 evenly-spaced peaks could fit into the bar time-frame. Then, either the peak-location, in percentage of the bar, or a binary-vector of 24 locations is saved (using Hamming-distance between the binary vectors.
3. Tonal-Tuned metric: corresponds to the tonal melodic-harmonic content of the sound track. The Short-Time-Discrete-Fourier-Transform, and then Frequency-Estimation are used, in order to find stable frequencies around a narrow frequency band, when the most stable energy distribution is found, like the one described with respect to the Tuning-Preprocessor.

(70) After the Similarity Matrices are built diagonals are marked, in order to divide the tracks into equivalent classes, while seeking only sub-diagonals that are inclined in 45, in order to find parts of equal duration (e.g., a chorus of a song, a recurring verse, or recurring fill). The matrices divided into blocks using local textures and division lines. At the next step, distinctive non-typical sections in each matrix are foundas the matrices are similarity matricesdis-similar sections are simply sections with higher than median value, which are easy to locate. In a similarity matrix, non-typical sections are regions that form a white line along the array of pixels, except for a black square which represents self-similarity near the mail diagonal. These non-typical sections are illustrated in FIG. 7 by the crosses in balloons 71 and 72.

(71) Then, two representatives are selected to represent the two largest equivalent classes, and a third section containing a distinctive section (other different configuration parameters may also be presented, based on the results of this analysis). The exact boundaries of the selected parts are then adjusted via the bars multiplicity that has been calculated before.

(72) Each element (pixel) in a similarity matrix represents the comparison results between a pair of bars identified at time i and time j. Pixels with higher intensity or mutual color provide indication about bars which have high similarity. This way, it is possible to identify bars with unique similarity patterns. Usually, these bars will belong to diagonals that are parallel to the main diagonal of the matrix (inclined in 45), so as to avoid time distortions. The exact boundaries of the selected partsare then adjusted via the bars multiplicity calculated before.

(73) Energy level distributions may be also used to help deciding where each identified diagonal starts and ends.

(74) Other smaller matrices are built for this purpose: 1. Matrices comparing Representative-Bars only, as described before. These matrices are typically sized 88 for a 5 minute song (where as the full similarity matrices are typically around 300300) 2. Matrices in the Multiplicity-Scale, which is integrating the metrics for groups of bars, in the size of the multiplicity as described before.

(75) FIG. 1 illustrates the process for extracting the most popular and representative segments of a song (musical composition), according to the present invention. At the first step, the audio signal is loaded for analysis. At the next step, the audio signal is preprocessed by a set of preprocessors in the form of low-pass filters that are used to concentrate the rhythmic component in the song. At the next step, the audio signal is divided into portions, based on energy levels. At the next step, the song is divided to dynamic bars and rhythmic pattern classes are generated, while checking their quality. At the next step, similarity matrices are constructed, based on MFCCs of the processed sound and the rhythmic patterns. At the next step, classes, substantial transitions between bars and singularities are extracted. At the next step, a representative segment is selected from each class.

Example 1

The Song You Got Me Performed by the RootsFeaturing Erykah Badu (Vocals)

(76) FIG. 2A illustrates the MFCCs matrix of this song. The dark diagonals represent repetitions of the chorus. In this matrix comprises pixels in a grayscale, where darker pixels indicate a higher similarity level (it can be seen that the main diagonal is black). The grayscale levels pass a histogram, which converts the pixel values to a binary black and white scale, in which white diagonals can be identified. Only diagonals that are displaced from the main diagonal are consideredthe minimal distance should be at least the diagonal length.

(77) The extracted diagonals are illustrated in FIG. 2B. In this case, it can be seen that is possible to associate between diagonals that belong to a mutual equivalent class (a cluster). For example, diagonals 22, 23 and 24 define an equivalent class, since they contain pixels that overlap in x dimension. Similarly, diagonals 23, 25 and 26 define another equivalent class, since they contain pixels that overlap in y dimension.

Example 2

The C-Part from the Album Rio by Duran-Duran

(78) FIG. 3A illustrates the MFCCs matrix of this song. The composition starts on the white cross 31, continues through the two dark diagonal blocks 32 and 33 surrounded with brighter lines. The diagonals that were found represent the chorus. The extracted diagonals are illustrated in FIG. 3B.

(79) In this example, the timbre information shows high correlation to the C-Part, since the C-part has a saxophone entering, the last chorus has the same saxophone. The intro (represented by the white block) is a stretched chord cluster unrelated to the song and even not so self similar.

Example 3

Summertime by John Coltrain

(80) FIG. 4 illustrates the MFCCs matrix of this composition. The different dark blocks along the main diagonal correspond to the different solo segments (Saxophone, Piano, Double-Bass, Drum, and Saxophone). The Double-Bass solo (represented by the bright margins) is different, since the instruments balance changes in this part.

(81) The processing results obtained by the method proposed by the present invention can be also used to for mapping an entire song and providing a graphical interface that allows a DJ (Disc Jockeya person who plays recorded music for an audience) to view the patterns of different segments the song, as well as the time points of transitions between them. The DJ can see the map and identify the different segments of the song. The DJ can then rapidly browse between them and play the part relevant to the mix.

(82) The method described above allows finding a segment with clear start and end point music-wise, so that the chosen segment stands as a complete and independent unit. This is achieved by finding Bar-Multiplicity for local section, detecting transition points, and Downbeat detection in a bar.

(83) While some embodiments of the invention have been described by way of illustration, it will be apparent that the invention can be carried out with many modifications, variations and adaptations, and with the use of numerous equivalents or alternative solutions that are within the scope of persons skilled in the art, without exceeding the scope of the claims.