EP1794745B1 - Device and method for changing the segmentation of an audio piece - Google Patents

Abstract

For grouping temporal segments of an audio piece, which is structured into main parts repeatedly occurring in the audio piece, into various segment classes, at first a similarity representation for the segments is provided, wherein the similarity representation for each segment comprises an associated plurality of similarity values, wherein the similarity values indicate how similar the segment is to every other segment of the audio piece. Hereupon, using the similarity values associated with the segment, a similarity threshold value for a segment is calculated in order to then associate a segment with a segment class when the similarity value of the segment meets a predetermined relation with reference to the similarity threshold value. With this, clustering is achieved, which also works efficiently and correctly where there are segments with strongly different or almost equal combined similarity values.

Description

The present invention relates to audio segmentation, and more particularly to the analysis of pieces of music on the individual major parts contained in the pieces of music which may occur repeatedly in the piece of music.

Rock and pop music mostly consists of more or less distinct segments, such as intro, verse, chorus, bridge, outro, etc. Detecting the start and end times of such segments and the segments according to their affiliation to the most important classes ( Stanza and chorus) is the target of audio segmentation. Correct segmentation and labeling of the calculated segments can be usefully used in different areas. For example, pieces of music from online providers, such as Amazon, Musicline, etc., can be intelligently "played".

Most providers on the Internet are limited to a short excerpt from the offered pieces of music in their audio samples. In this case, it would of course also make sense to offer the interested parties not only the first 30 seconds or any 30 seconds, but a most representative excerpt from the song. This could be z. B. the refrain, or else a summary of the song, consisting of segments that belong to the various main classes (stanza, chorus, ...).

Another application example of the technique of audio segmentation is the integration of the segmentation / grouping / marking algorithm into a music player. The information about segment beginnings and segment ends enables the targeted navigation through a piece of music. Due to the class affiliation of the segments, ie whether a segment is a verse, a chorus, etc., z. B. also jump directly to the next chorus or the next stanza. Such an application is of interest to large music markets, offering their customers the opportunity to listen to complete albums. This saves the customer the annoying, searching fast-forward to characteristic parts in the song, which might perhaps cause him to actually buy a piece of music in the end.

There are several approaches in the field of audio segmentation. In the following, the approach of Jonathan Foote and Matthew Cooper is exemplified. This procedure is in FOOTE, JT / Cooper, ML: Summarizing Popular Music via Structural Similarity Analysis. Proceedings of the IEEE Workshop on Signal Processing to Audio and Acoustics 2003 , FOOTE, JT / COOPER, ML: Media Segmentation using Self-Similar Decomposition. Proceedings of SPIE Storage and Retrieval for Multimedia Databases, Vol. 5021, pp. 167-75, January 2003 represented.

The known method of Foote is based on the block diagram of Fig. 5 exemplified. First, a WAV file 500 is provided. In a subsequent extraction block 502, a feature extraction then takes place, as a feature, extracting the spectral coefficients per se or, alternatively, the mel frequency cepstral coefficients (MFCCs). Prior to this extraction, a short-term Fourier transform (STFT) is performed with 0.05 second wide non-overlapping windows with the WAV file. The MFCC features are then extracted in the spectral range. It should be noted that the parameterization is not optimized for compression, transmission or reconstruction, but for a Audio analysis. The requirement is that similar audio pieces produce similar features.

The extracted features are then stored in a memory 504.

The feature extraction algorithm now has a segmentation algorithm that ends in a similarity matrix, as shown in block 506. First, however, the feature matrix is read in (508), to then group feature vectors (510), and then build a similarity matrix based on the grouped feature vectors, which consists of a distance measurement between each of all features. In particular, all pairs of audio window pairs are compared using a quantitative similarity measure, distance.

The structure of the similarity matrix is in Fig. 8 shown. So is in Fig. 8 the music piece is represented as stream or stream 800 of audio samples. The audio piece is windowed as it has been executed, with a first window labeled i and a second window labeled j. Overall, the audio piece has z. B. K windows. This means that the similarity matrix has K rows and K columns. Then, for each window i and for each window j, a similarity measure to each other is calculated, and the calculated similarity measure or distance measure D (i, j) is input to the row or column designated by i and j in the similarity matrix. One column therefore shows the similarity of the window designated by j to all other audio windows in the piece of music. The similarity of the window j to the very first window of the piece of music would then be in the column j and in the line 1. The similarity of the window j to the second window of the piece of music would then be in the column j, but now in the line 2. By contrast, the similarity of the second window to the first window in the second column of the matrix and in the first row of the matrix.

It can be seen that the matrix is redundant in that it is symmetric to the diagonal, and that on the diagonal the similarity of a window is to itself, which is the trivial case of 100% similarity.

An example of a similarity matrix of a piece is in Fig. 6 to see. Here again the completely symmetrical structure of the matrix with respect to the main diagonal is recognizable, whereby the main diagonal is visible as a light stripe. It should also be noted that due to the small window length compared to the relatively coarse time resolution in Fig. 6 the main diagonal is not to be seen as a lighter solid line, but off Fig. 6 only approximately recognizable.

This is done using the similarity matrix as described, for. In Fig. 6 A kernel correlation 512 is performed on a kernel matrix 514 to obtain a novelty measure, also known as a novelty score, that could be averaged and smoothed into Fig. 9 is shown. The smoothing of this Novelty Score is in Fig. 5 schematically represented by a block 516.

Thereafter, in a block 518, the segment boundaries are read using the smoothed novelty value trace, whereupon the local maxima in the smoothed novelty profile must be determined and possibly even shifted by a constant number of samples caused by the smoothing to actually represent the correct segment boundaries of the audio piece as absolute or relative time.

This is done, as it already is in a block called clustering Fig. 5 can be seen, creates a so-called segment similarity representation or segment similarity matrix. An example of a segment similarity matrix is in Fig. 7 shown. The similarity matrix in Fig. 7 is basically similar to the feature similarity matrix of Fig. 6 , but now not more, as in Fig. 6 Features are used in windows, but features from a whole segment. The segment similarity matrix has a similar meaning to the feature similarity matrix, but with a much coarser resolution, which of course is desired when considering that window lengths are in the order of 0.05 seconds while reasonably long segments are in the order of perhaps 10 seconds of a piece ,

Then, in a block 522, a clustering is carried out, ie an arrangement of the segments into segment classes (an arrangement of similar segments in the same segment class), in order then to mark the found segment classes in a block 524, which is also referred to as "labeling". Thus, in labeling, it is determined which segment class contains segments that are stanzas that are choruses that are intros, outros, bridges, and so on.

Finally, in one with 526 in Fig. 5 designated block creates a music grammar, the z. B. can be provided to a user, without redundancy of a piece only z. B. a verse, a chorus and the intro to hear.

Below, the individual blocks are discussed in more detail.

As already stated, the actual segmentation of the piece of music does not take place until the feature matrices have been generated and stored (block 504).

Depending on which feature the piece of music is to be examined for its structure, the corresponding feature matrix is read out and loaded into a main memory for further processing. The feature matrix has the dimension number of analysis windows times the number of feature coefficients.

The similarity matrix brings the feature course of a piece into a two-dimensional representation. For each pairwise combination of feature vectors, the distance measure is computed, which is recorded in the similarity matrix. There are various possibilities for calculating the distance measure between two vectors, namely, for example, the Euclidean distance measurement and the cosine distance measurement. A result D (i, j) between the two feature vectors is stored in the i, jth element of the window similarity matrix (block 506). The main diagonal of the similarity matrix represents the course over the entire piece. Accordingly, the elements of the main diagonal result from the respective comparison of a window with itself and always have the value of the greatest similarity. For the cosine distance measurement this is the value 1, for the simple scalar difference and the Euclidean distance this value is 0.

To visualize a similarity matrix, as in Fig. 6 is shown, each element i, j is assigned a gray value. The gray values are graded in proportion to the similarity values, so that the maximum similarity (the main diagonal) corresponds to the maximum similarity. Through this representation, one can already recognize the structure of a song visually on the basis of the matrix. Areas of similar feature expression correspond to quadrants of similar brightness along the main diagonal. Finding the boundaries between the areas is the task of the actual segmentation.

The structure of the similarity matrix is important to the novelty measure calculated in kernel correlation 512. The novelty measure arises from the correlation of a particular kernel along the main diagonal of the similarity matrix. An exemplary kernel K is in Fig. 5 shown. If one correlates this kernel matrix along the main diagonal of the similarity matrix S, and thereby sums all the products of the superimposed matrix elements for each time point i of the piece, one obtains the measure of novelty, which in a smoothed form exemplifies Fig. 9 is shown. Preferably, the kernel K is not in Fig. 5 but an enlarged kernel, which is also superimposed with a Gaussian distribution, so that the edges of the matrix go to zero.

The selection of the striking maxima in the novelty course is important for the segmentation. The selection of all maxima of the unsmoothed novelty course would lead to a strong over-segmentation of the audio signal.

Therefore, the novelty measure should be smoothed with different filters, such as IIR filters or FIR filters.

If the segment boundaries of a piece of music are extracted, then similar segments must be identified as such and grouped into classes.

Foote and Cooper describe the calculation of a segment-based similarity matrix using a Cullback-Leibler distance. For this purpose, individual segment feature matrices are extracted from the entire feature matrix on the basis of the segment boundaries obtained from the novelty process, ie each of these matrices is a submatrix of the entire feature matrix. The resulting segment similarity matrix 520 is now subjected to Singular Value Decomposition (SVD).

Then one obtains singular values in descending order.

At block 526, an automatic digest of a piece is then performed based on the segments and clusters of a piece of music. For this purpose, first the two clusters with the largest singular values are selected. Then, the segment with the maximum value of the corresponding cluster indicator is added to this summary. This means that the summary includes a stanza and a chorus. Alternatively, all repeated segments can also be removed to ensure that all piece information is provided, but always exactly once.

Regarding further techniques for segmentation / music analysis will be on CHU, s. / LOGAN B .: Music Summary using Key Phrases. Technical Report, Cambridge Research Laboratory 2000 . BARTSCH, MA / WAKEFIELD, g. H .: To Catch a Chorus: Using Chroma-Based Representation for Audio Thumbnailing. Proceedings of the IEEE Workshop on Signal Processing to Audio and Acoustics 2001. http://musen.engin.umich.edu/papers/bartsch wakefield waspaa01 final.pdf , referenced

A disadvantage of the known method is the fact that the singular value decomposition (SVD) for segment class formation, that is to say for the assignment of segments to clusters, is very computationally intensive and is problematic in the evaluation of the results. Thus, if the singular values are nearly equal, then a possibly wrong decision is made that the two similar singular values actually represent the same segment class and not two different segment classes.

Further, it has been found that the results obtained by the singular value decomposition become more and more problematic when it differentiates strong similarity values So if a piece contains very similar components, such as stanza and chorus, but also relatively dissimilar parts, such as Intro, Outro or Bridge.

Further problematic in the known method is that it is always assumed that the cluster among the two clusters with the highest singular values having the first segment in the song is the cluster "stanza", and that the other cluster is the cluster "chorus "is. This procedure is based on the assumption in the known method that a song always begins with a stanza. Experience has shown that this will result in significant labeling errors. This is problematic insofar as the labeling is effectively the "harvest" of the entire process, that is, what the user experiences directly. Even if the previous steps were so precise and time-consuming, everything becomes relative if the label is incorrectly labeled at the end, because then the user's overall confidence in the entire concept could be damaged.

It should also be noted at this point that there is a particular need for automatic music analysis methods, without the result always being able to be checked and, if necessary, corrected. Instead, a method can only be used on the market if it can run automatically without human correction.

Another disadvantage of the known concept is the fact that in the segmentation is built on the segmentation calculated by the Singularwertzerlegung. In other words, this means that both clustering and final labeling are based on the segmentation determined by singular value decomposition. However, clustering and labeling, and thus the music summary, which is the actual product of the entire process for the listener, can never be better than the underlying segmentation.

If an over-segmentation takes place, as occurs frequently in particular for kernel-correlation-based concepts, one will end up with far too many segment classes which have to be reworked in order to completely remove disturbing segment classes which are actually not appropriate for a major part. This "post-repair" is unfavorable in that it eliminates audio information. A listener, when navigating through the audio track due to the already designated segment classes, will not be able to hear all the audio information, as insignificant segments, which are not actually a major part, have been completely eliminated in this procedure.

Even more important, however, is the fact that over-segmentation, which may also occur through other segmentation techniques, indicates the fact that the original primary segmentation was incorrect. The segments of, for example, the segment class denoted "refrain" are of different quality. Thus, a segment where the segmentation was correct has a longer refrain, while another segment where the segmentation was not correct has a shorter refrain. Subsequently, working with the segmented representation of the audio piece, this leads to synchronization problems and also to irritation in the user, who may even go so far that he loses all confidence in the segmentation concept.

The specialist publication: " A Fuzzy Approach Towards Perceptual Classification And Segmentation of MP3 / AAC Audio, S. Kiranyaz, US, Control, Communications and Signal Processing, 2004, pages 727-730 discloses an approach to classify and segment MP3 and AAC audio pieces in the compression domain. The audio signal is divided into segments classified as speech, music, fuzzy or silence. In particular, small silence segments are eliminated and adjacent non-silence segments are merged.

The object of the present invention is to achieve a more precise segmentation concept, which should also be compatible with an already existing first segmentation of the audio piece.

This object is achieved by a device for changing a segmentation of an audio piece according to claim 1 or 19, a method for changing a segmentation of an audio piece according to claim 18 or 20 or a computer program according to claim 21.

The present invention is based on the finding that the over-segmentation is effectively counteracted if, after an original segmentation and subsequent segmentation class assignment, the originally already completed original segmentation is post-corrected. For this purpose, the device according to the invention comprises a segmentation correction device for correcting the segmentation, which is designed to merge a segment having a length which is shorter than a predetermined minimum length with a time predecessor segment or a successor segment, by a changed segmentation of the audio piece to obtain. According to the invention, this post-correction takes place after the first segmentation and the allocation to the segment classes subsequent to the first segmentation, that is also after the clustering. This makes it possible for the segmentation correction to merge not only short segments according to certain criteria with a preceding segment and a subsequent segment but also information about the segment class affiliation of the predecessor segment, about the segment class affiliation of the predecessor segment or about the segment class affiliation for this merger of the short segment itself.

However, even without regard to the segment class affiliations of the short segment, the predecessor segment or the successor segment, simple algorithms can achieve a segment merge already having an acceptable hit probability based on a review of the novelty values at the segment boundaries.

However, due to the novelty values at the segment boundaries, the segment merge is preferably carried out only to a certain extent as a last resort, if a corresponding short segment could not be merged by previous reviews in which the segment class affiliation of the affected forerunner / successor segments was taken into account.

In a preferred embodiment of the present invention, an adaptive segment assignment is performed based on the primary segmentation, however, upon the occurrence of segmentation assignment conflicts, segments that are actually associated with a first segment class are provided with a bias to another class of segment that caused the conflict become. If it then turns out that a segment with such a tendency is at the same time a short segment, and it also turns out that the trend is indicative of a segment class to which the temporally preceding segment or the temporally succeeding segment belongs at the same time, one of the original segmentation of similarity on the basis of this trend or trend.

The inventive concept is particularly advantageous in that no portion of the audio piece is completely eliminated. The user, who then navigates through the audio piece when all processing is complete, will find segments constituting the changed segmentation whose total length is still equal to the original length of the audio piece.

In addition, a number of segment classes equal to the number of main parts occurring in an audio track are obtained.

Furthermore, the minimum length of a segment can be adjusted variably, solely on the basis of a temporal threshold value specification, which opens up possibilities in this regard, in particular in connection with a music genre identification, of minimum permissible minimum segment lengths Music genre adapt, especially since different genre of music can bring different lengths segments with it.

Furthermore, the concept according to the invention also makes it possible to reduce the number of segment classes by assigning short segments on the basis of a minimum length threshold specification until an expected number is met, without the segment representation of the audio piece comprising holes.

In a preferred embodiment, a segment is assigned to a segment class based on an adaptive similarity mean for a segment such that the similarity mean takes into account which overall similarity score a segment has in the entire piece. After such a similarity mean has been calculated for a segment, for the calculation of which the number of segments and the similarity values of the plurality of similarity values assigned to the segment are required, the actual assignment of a segment to a segment class, ie to a cluster, then becomes apparent based on this similarity mean. For example, if a similarity value of a segment to the segment under consideration is above the similarity mean, then the segment is assigned as belonging to the currently considered segment class. Conversely, if the similarity value of a segment to the segment under consideration is below that similarity mean, it will not be assigned to the segment class.

In other words, this means that the assignment is no longer made dependent on the absolute size of the similarity values, but relative to the similarity mean. This means that for a segment that has a relatively low similarity score, so z. For example, for a segment that has an intro or outro, the similarity mean will be lower than for a segment that is a stanza or chorus. Thus, the strong deviations of the similarities of segments in pieces or the frequency of occurrence of certain segments are considered in pieces, with z. B. numerical problems and thus ambiguities and associated misallocations can be avoided.

The inventive concept is particularly suitable for pieces of music that consist not only of stanzas and choruses, so have the segments that belong to segment class that have the same similarity values, but also for pieces that in addition to stanza and chorus also have other parts, namely an introduction (Intro), an interlude (Bridge) or a finale (Outro).

In a preferred embodiment of the present invention, the calculation of the adaptive similarity mean and the assignment of a segment are performed iteratively, ignoring similarity values of assigned segments at the next iteration run. This results in a new maximum similarity absolute value for the next iteration run, ie the sum of the similarity values in a column of the similarity matrix, since the similarity absolute values corresponding to the previously assigned segments have been set to zero.

According to the invention, a segmentation post-correction is carried out in such a way that after the segmentation z. B. based on the novelty value (the local maxima of the novelty value) and after a subsequent assignment to segment classes relatively short segments are examined to see if they can be assigned to the predecessor segment or the successor segment, since segments below a minimum Segment length is likely to indicate over-segmentation.

In an alternative preferred embodiment of the present invention, after the final segmentation and assignment into the segment classes, a labeling is performed using a special selection algorithm to obtain the most correct labeling of the segment classes as a stanza or chorus.

Fig. 1

ein Blockschaltbild der erfindungsgemäßen Vorrichtung zum Gruppieren gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung;

Fig. 2

ein Flussdiagramm zur Darstellung einer bevorzugten Ausführungsform der Erfindung zum iterativen Zuweisen;

Fig. 3

ein Blockdiagramm der Funktionsweise der Segmentierungskorrektureinrichtung;

Fig. 4a

und Fig. 4b eine bevorzugte Ausführungsform der Segmentklassenbezeichnungseinrichtung;

Fig. 5

ein Gesamtblockschaltbild eines Audioanalysewerkzeugs;

Fig. 6

eine Darstellung einer beispielhaften Merkmalsähnlichkeitsmatrix;

Fig. 7

eine beispielhafte Darstellung einer Segmentähnlichkeitsmatrix;

Fig. 8

eine schematische Darstellung zur Veranschaulichung der Elemente in einer Ähnlichkeitsmatrix S; und

Fig. 9

eine schematische Darstellung eines geglätteten Neuheitswerts.

Preferred embodiments of the present invention will be explained below in detail with reference to the accompanying drawings. Show it:

Fig. 1

a block diagram of the device according to the invention for grouping according to a preferred embodiment of the present invention;

Fig. 2

a flow chart for illustrating a preferred embodiment of the invention for iterative assignment;

Fig. 3

a block diagram of the operation of the Segmentierungskorrektureinrichtung;

Fig. 4a

and Fig. 4b a preferred embodiment of the segment class designator;

Fig. 5

an overall block diagram of an audio analysis tool;

Fig. 6

a representation of an exemplary feature similarity matrix;

Fig. 7

an exemplary representation of a segment similarity matrix;

Fig. 8

a schematic representation for illustrating the elements in a similarity matrix S; and

Fig. 9

a schematic representation of a smoothed novelty value.

Fig. 1 shows a device for grouping temporal segments of a piece of music, which is divided into main parts repeatedly occurring in the piece of music, into different segment classes, one segment class being assigned to a main part. The present invention thus relates particularly to pieces of music which are subject to a certain structure in which similar sections appear several times and alternate with other sections. Most rock and pop songs have a clear structure in terms of their main parts.

The literature deals with the theme of music analysis mainly on the basis of classical music, but it also applies much to rock and pop music. The main parts of a piece of music are also called "large moldings". A large shaped part of a piece is understood to mean a section which, with respect to various features, e.g. B. melody, rhythm, texture, etc., has a relatively uniform nature. This definition applies generally in music theory.

Large moldings in rock and pop music are z. Eg verse, chorus, bridge and solo. In classical music, an interplay of chorus and other parts (couplets) of a composition is also called rondo. In general, the couplets contrast with the chorus, for example in terms of melody, rhythm, harmony, key or instrumentation. This can also be transferred to modern light music. Just as there are different forms in the rondo (chain rondo, bowed rondo, sonata rondo), there are also proven patterns in rock and pop music for setting up a song. Of course these are just a few options out of many. Ultimately, of course, the composer decides how his piece is constructed. An example of a typical structure of a rock song is the pattern.
ABABCDAB,
where A equals strophe, B equals refrain, C equals bridge, and D equals solo. Often a piece of music is introduced with a prelude. Intros often consist of the same chord progression as the stanza, but with different instrumentation, eg. B. without drums, without bass or distortion of the guitar in rock songs etc.

The apparatus of the invention comprises first means 10 for providing a similarity representation to the segments, the similarity representation having for each segment an associated plurality of similarity values, the similarity values indicating how similar the segment is to each other segment. The similarity representation is preferably that in Fig. 7 shown segment similarity matrix. It has for each segment (in Fig. 7 Segments 1-10) has its own column, which has the index "j". Further, the similarity representation has a separate row for each segment, with one row labeled with a row index i. This will be referred to below with reference to the exemplary segment 5. The element (5,5) in the main diagonal of the matrix of Fig. 7 is the similarity value of the segment 5 with itself, ie the maximum similarity value. Furthermore, the segment 5 is still medium-like to the segment No. 6, as it is by the element (6,5) or by the element (5,6) of the matrix in Fig. 7 is designated. Moreover, the segment 5 is still similar to the segments 2 and 3, as represented by elements (2,5) or (3,5) or (5,2) or (5,3) in FIG Fig. 7 is shown. As for the other segments 1, 4, 7, 8, 9, 10, the segment No. 5 has a similarity as described in FIG Fig. 7 is no longer visible.

A plurality of similarity values associated with the segment is, for example, a column or a row of the segment similarity matrix in FIG Fig. 7 , which indicates this column or row based on their column / row index which segment it refers to, namely, for example, to the fifth segment, and where this row / column comprises the similarities of the fifth segment to each other segment in the piece. Thus, the plurality of similarity values is, for example, a row of the similarity matrix or, alternatively, a column of the similarity matrix of Fig. 7 ,

The device for grouping temporal segments of the piece of music further comprises means 12 for calculating a similarity mean for a segment, using the segments and the similarity values of the plurality of similarity values associated with the segment. The device 12 is designed to z. For column 5 in Fig. 7 to calculate a similarity mean. In a preferred embodiment, when the arithmetic mean is used, means 12 will add the similarity values in the column and divide by the number of segments in total. In order to eliminate self-similarity, the similarity of the segment to itself could also be deducted from the result of the addition, whereby, of course, a division should no longer be performed by all elements, but by all elements less 1.

Alternatively, the means 12 for computing could also calculate the geometric mean, that is, squiggle each similarity value of a column separately to sum the squared results, and then calculate a root from the summation result represented by the number of elements in the column the number of elements in the column is less 1) to divide. Any other mean values, such as the median value, etc., are usable as long as the mean value for each column of the similarity matrix is adaptively calculated, that is, a value calculated using the similarity values of the plurality of similarity values associated with the segment.

The adaptively calculated similarity threshold is then provided to a segment 14 for assigning a segment to a segment class. The means 14 for assigning is arranged to associate a segment with a segment class if the similarity value of the segment satisfies a predetermined condition with respect to the mean of similarity. For example, if the similarity mean is such that a larger value indicates greater similarity and a smaller value indicates lesser similarity, then the predetermined relationship will be that the similarity value of a segment must be equal to or above the similarity mean, thus the segment is assigned to a segment class.

In a preferred embodiment of the present invention, there are still other devices to realize specific embodiments, which will be discussed later. These devices are a segment selection device 16, a segment assignment conflict device 18, a segmentation correction device 20 and a segment class designation device 22.

P ist die Anzahl der Segmente. SÄ ist der Wert der Selbstähnlichkeit eines Segments mit sich selbst. Je nach verwendeter Technik kann der Wert z. B. Null oder Eins sein. Die Segmentauswahleinrichtung 16 wird zunächst den Wert V(j) für jedes Segment berechnen, um dann das Vektorelement i des Vektors V mit maximalem Wert herauszufinden. Anders ausgedrückt bedeutet dies, dass die Spalte in Fig. 7 gewählt wird, die bei der Aufaddition der einzelnen Ähnlichkeitswerte in der Spalte den größten Wert oder Score erreicht. Dieses Segment könnte beispielsweise das Segment Nr. 5 bzw. die Spalte 5 der Matrix in Fig. 7 sein, da dieses Segment mit drei anderen Segmenten zumindest eine gewisse Ähnlichkeit hat. Ein anderer Kandidat bei dem Beispiel von Fig. 7 könnte auch das Segment mit der Nr. 7 sein, da dieses Segment ebenfalls zu drei anderen Segmenten eine gewisse Ähnlichkeit hat, die zudem noch größer ist als die Ähnlichkeit des Segments 5 zu den Segmenten 2 und 3 (höhere Grauschattierung in Fig. 7).The segment selector 16 in FIG Fig. 1 is trained to look for each column in the matrix first Fig. 7 to calculate an overall similarity value V (j), which is determined as follows: $$\begin{array}{cc}V\left(j\right)={\displaystyle \underset{i=1}{\overset{P}{\Sigma }}}{S}_s\left(i,,j\right)-S\ddot{A}& j=1.....P\end{array}$$

P is the number of segments. SÄ is the value of self-similarity of a segment to itself. Depending on the technique used, the value z. B. zero or one. The segment selector 16 will first calculate the value V (j) for each segment to then find the vector element i of the maximum value vector V. In other words, this means that the column in Fig. 7 chosen becomes the largest value or score when the individual similarity values in the column are added. For example, this segment could be segment no. 5 or column 5 of the matrix in Fig. 7 be, since this segment has at least a certain similarity with three other segments. Another candidate in the example of Fig. 7 could also be the segment with the number 7, since this segment also has a certain similarity to three other segments, which is even greater than the similarity of the segment 5 to the segments 2 and 3 (higher shade of gray in FIG Fig. 7 ).

For the following example, it is now assumed that the segment selector 16 selects the segment # 7 because it has the highest similarity score due to the matrix elements (1,7), (4,7), and (10,7). In other words, this means that V (7) is the component of the vector V which has the maximum value among all the components of V.

Now, the similarity score of column 7, that is, for segment no. 7, is still divided by the number "9" in order to obtain from the means 12 the similarity threshold value for the segment.

Then, in the segment similarity matrix for the seventh row or column, it is checked which segment similarities are above the calculated threshold, i. H. with which segments the ith segment has an above-average similarity. All these segments are now also assigned to a first segment class like the seventh segment.

For the present example, it is assumed that the similarity of the segment 10 to the segment 7 is below average, but that the similarities of the segment 4 and the segment 1 to the segment 7 are above average. Therefore, in the first segment class next to the segment no. 7 also segment no. 4 and segment no. 1 are classified. By contrast, segment no. 10 is not classified in the first segment class due to the below-average similarity to segment no.

After the assignment, the corresponding vector elements V (j) of all segments which have been assigned to a cluster in this threshold value analysis are set to 0. In the example these are beside V (7) also the components V (4) and V (1). This immediately implies that the 7th, 4th, and 1st columns of the matrix will no longer be available for a later maximum search, that they are zero, so they can not be a maximum.

This is roughly equivalent to setting the entries (1,7), (4,7), (7,7) and (10,7) of the segment similarity matrix to 0. The same procedure is used for column 1 (elements (1,1), (4,1) and (7,1)) and column 4 (elements (1,4), (4,4), (7,4) and (10, 4)). Due to the ease of handling, however, the matrix is not changed, but the components of V that belong to an assigned segment are ignored on the next maximum search in a later iteration step.

In a next iteration step, a new maximum is now selected from the remaining elements of V, that is to say V (2), V (3), V (5), V (6), V (8), V (9) and V (10) searched. The segment no. 5, ie V (5), is expected to yield the largest similarity score. The second segment class then obtains segments 5 and 6. Due to the fact that the similarities to segments 2 and 3 are below average, segments 2 and 3 are not placed in the second order clusters. Thus, the elements V (6) and V (5) are set to 0 by the vector V due to the assignment made, while still the components V (2), V (3), V (8), V (9) and V (10) of the vector for the selection of the third-order cluster remain.

Then again a new maximum among the mentioned remaining elements of V is searched for. The new maximum could be V (10), ie the component of V for segment 10. Segment 10 thus comes in the segment class of third order. Thus, it could also be found that the segment 7 also has an above-average similarity to the segment 10, although the segment 7 is already identified as belonging to the first segment class. This results in an assignment conflict that is caused by the segment assignment conflicting device 18 of FIG Fig. 1 is resolved.

A simple kind of resolution could be to simply not assign the segment 7 into the third segment class and e.g. For example, instead of assigning the segment 4, if for the segment 4 would not also conflict exist.

Preferably, however, in order not to disregard the similarity between the segment 7 and the segment 10, the similarity between 7 and 10 is considered in the following algorithm.

Generally, the invention is designed not to discount the similarity between i and k. Therefore, the similarity values S _s (i, k) of segment i and k are compared with the similarity value S _s (i *, k), where i * is the first segment assigned to the cluster C *. The cluster or the segment class C * is the cluster to which segment k is already assigned on the basis of a previous examination. The similarity value S _s (i *, k) is decisive for the fact that the segment k belongs to the cluster C *. If S _s (i *, k) is greater than S _s (i, k), segment k in cluster C * is left. If S _s (i *, k) is smaller than S _s (i, k), the segment k is taken out of the cluster C * and assigned to the cluster C. For the first case, ie if the segment k does not change the cluster membership, a tendency towards the cluster i is noted for the cluster C *. Preferably, however, this tendency is also noted when segment k changes cluster membership. In this case, a tendency of this segment to the cluster in which it was originally recorded is noted. These tendencies may be advantageously used in a segmentation correction performed by the segmentation correction means 20.

The similarity value check will be in favor of the first segment class due to the fact that the segment 7 is the "source segment" in the first segment class. The segment 7 will therefore not change its cluster membership (segment affiliation), but it will remain in the first segment class. However, this fact is taken into account by the fact that segment no. 10 in the third segment class is attested a trend towards the first segment class.

According to the invention, it is thus taken into account that, in particular for the segments whose segment similarities to two different segment classes exist, these similarities are nevertheless not ignored, but may eventually be taken into account later by the trend or the tendency.

The procedure continues until all segments in the segment similarity matrix are assigned, which is the case when all elements of vector V are set to zero.

This would be for the in Fig. 7 shown example mean that next, in the fourth segment class, the maximum of V (2), V (3), V (8), V (9), so the segment 2 and 3 are classified, then, in a fifth segment class, segments 8 and 9, respectively, until all segments have been assigned. This is the in Fig. 2 shown iterative algorithm finished.

In the following, the preferred implementation of the segmentation correction device 20 will be described in detail with reference to FIG Fig. 3 received.

Thus, when calculating the segment boundaries by means of the kernel correlation, but also when calculating segment boundaries by means of other measures, an over-segmentation of a piece often occurs, ie too many segment boundaries or generally too short segments are calculated. An over-segmentation, z. B. caused by an incorrect subdivision of the stanza, is inventively corrected by the fact that due to the segment length and the information in which segment class a predecessor or successor segment has been sorted, is corrected. In other words, the correction serves to completely eliminate segments that are too short, ie to merge with adjacent segments, and segments that are short but are not too short, ie that are short in length but longer than the minimum length to undergo a special investigation into whether they may not yet be merged with a predecessor segment or a successor segment. In principle, successive segments belonging to the same segment class are always fused together. Results in Fig. 7 shown scenario z. B. that the segments 2 and 3 come in the same segment class, they are automatically merged together, while the segments in the first segment class, ie the segments 7, 4, 1 are spaced apart and therefore (at least initially) are not merged. This will be in Fig. 3 indicated by a block 30. It is now examined in a block 31 whether segments have a segment length which is smaller than a minimum length. Thus, there are preferably different minimum lengths.

Relatively short segments shorter than 11 seconds (a first threshold) are only examined at all, while later still shorter segments (a second threshold, smaller than the first one) shorter than 9 seconds, and later remaining segments shorter than 6 seconds (a third threshold shorter than the second threshold) are again treated alternatively.

In the preferred embodiment of the present invention in which this staggered length check occurs, the segment length check in block 31 is initially directed to finding the segments shorter than 11 seconds. For the segments that are longer than 11 seconds, no post processing is done, as indicated by a "No" at block 31. For segments shorter than 11 seconds, a trend check (block 32) is first performed. Thus, it is first examined whether a segment due to the functionality of the segment allocation conflicting device 18 of Fig. 1 has an associated trend or an associated trend. In the example of Fig. 7 this would be the segment 10 that has a trend towards the segment 7 or a trend towards the first segment class. If the tenth segment is shorter than 11 seconds, the in Fig. 7 Nevertheless, due to the trend check, nothing is done, since a fusion of the considered segment takes place only if it has a tendency not to any cluster, ie to any segment class, but a tendency to a cluster of an adjacent (before or after) segment , However, this is for the segment 10 in the in Fig. 7 example not shown.

In order to avoid too short segments, which have no tendency to cluster an adjacent segment, the procedure is as shown in the blocks 33a, 33b, 33c and 33d in Fig. 3 is shown. Thus, nothing is done on segments longer than 9 seconds, but shorter than 11 seconds. They are left. In a block 33a, however, is now for segments of the cluster X, which are shorter than 9 seconds, and where both the predecessor segment As well as the successor segment to cluster Y, an assignment to cluster Y is made, which automatically means that such a segment is merged with both the predecessor and successor segments, resulting in an overall longer segment from the considered segment as well as the predecessor and the successor segments. Thus, a subsequent merger may result in a combination of initially separate segments over an intervening segment to be merged.

In a block 33b it is further explained what happens to a segment that is shorter than 9 seconds and that is the only segment in a segment group. For example, segment no. 10 is the only segment in the third segment class. If it was shorter than 9 seconds, it will automatically be assigned to the segment class to which segment no. 9 belongs. This automatically leads to a fusion of the segment 10 with the segment 9. If the segment 10 is longer than 9 seconds, then this merger is not performed.

In a block 33c an examination is then made for segments shorter than 9 seconds which are not the only segment in a corresponding cluster X than in a corresponding segment group. They undergo closer scrutiny to establish regularity in clustering. First, all segments from segment group X shorter than the minimum length are searched for. Subsequently, it is checked for each of these segments whether the predecessor and successor segments each belong to one uniform cluster. If all predecessor segments are from a uniform cluster, all segments that are too short from cluster X are assigned to the predecessor cluster. If, on the other hand, all successor segments are from a uniform cluster, the segments too short from cluster X are each assigned to the successor cluster.

In a block 33d is executed what happens, even if this condition is not fulfilled for segments that are shorter than 9 seconds. In this case, a novelty value check is performed by resorting to the novelty value curve, which in Fig. 9 is shown. In particular, the novelty curve, which resulted from the kernel correlation, is read out at the locations of the affected segment boundaries, and the maximum of these values is determined. If the maximum occurs at the beginning of a segment, the segments that are too short are assigned to the cluster of the successor segment. If the maximum occurs at a segment end, the segments that are too short are assigned to the cluster of the predecessor segment. Would that be in Fig. 9 If the segment labeled 90 has a segment that is shorter than 9 seconds, the novelty check at the beginning of segment 90 would give a higher novelty value 91 than at the end of the segment, with the novelty value at the end of the segment labeled 92. This would mean that the segment 90 would be assigned to the successor segment since the novelty value to the successor segment is less than the novelty value to the predecessor segment.

If segments still remain that are shorter than 9 seconds and could not yet be merged, a staggered selection will be carried out among them. In particular, now all segments among the remaining segments shorter than 6 seconds are selected. The segments whose length is between 6 and 9 seconds from this group are allowed "untouched".

However, the segments shorter than 6 seconds are now all subjected to the novelty check explained by elements 90, 91, 92 and assigned to either the predecessor or the successor segment, so that at the end of the in Fig. 3 Correction algorithm shown all too short segments, namely all segments below a length of 6 Seconds, have been merged intelligently with predecessor and successor segments.

This procedure according to the invention has the advantage that no elimination of parts of the piece has been carried out, that is to say that no simple elimination of the segments which are too short has been carried out by setting them to zero, but that the entire complete piece of music remains as a whole The segmentation is therefore no information loss occurred, which would be, however, if one z. B. in response to the over-segmentation would simply eliminate all too short segments "regardless of losses" easily.

Subsequently, reference will be made to Fig. 4a and Fig. 4b a preferred implementation of the segment class designator 22 of Fig. 1 shown. According to the invention, two clusters are assigned the labels "stanza" and "refrain" during labeling.

According to the present invention, not a largest singular value of a singular value decomposition and the associated cluster are used as a refrain and the cluster for the second largest singular value as a stanza. Furthermore, it is not generally assumed that each song starts with a stanza, so that the cluster with the first segment is the stanza cluster and the other cluster is the refrain cluster. Instead, according to the invention, the cluster in the candidate selection having the last segment is called a refrain, and the other cluster is called a stanza.

Thus, for the two clusters finally available for stanza / refraction selection, it is checked (40) which cluster has the segment which occurs as the last segment of the segments of the two segment groups in the song progression, in order to designate it as refrain.

The last segment may actually be the last segment in the song, or a segment later in the song than any segment of the other segment class. If this segment is not the actual last segment in the song, this means that there is still an outro.

This decision is based on the realization that the chorus comes in the vast majority of cases in a song behind the last stanza, so directly as the last segment of the song, if a piece z. B. is hidden with the chorus, or as a segment in front of an outro, which follows a chorus and with which the piece is terminated.

If the last segment is from the first segment group, then all segments of that first (most significant) segment class are referred to as a refrain, as indicated by a BLock 41 in FIG Fig. 4b is shown. In addition, in this case all segments of the other segment class to be selected are marked as "stanza", since typically of the two candidate segment classes, one class will have the chorus, and thus immediately the other class will have the stanzas.

If, on the other hand, the investigation in block 40 reveals that which segment class in the selection has the last segment in the music track progression, that this is the second, ie rather non-hierarchical segment class, then it is examined in block 42 whether the second segment class has the first segment in the music piece , This investigation is based on the knowledge that the likelihood is very high that a song starts with a verse, not a chorus.

If the question is answered with "No" in block 42, that is, if the second segment class does not have the first segment in the piece of music, then the second segment class is referred to as a refrain, and the first segment class is referred to as a stanza, as indicated in a block 43 , Will against it the query in the block 42 with "Yes" answered, then, contrary to the rule, the second segment group is called a stanza and the first segment group as a refrain, as indicated in a block 44. The designation in block 44 occurs because the probability that the second segment class corresponds to the refrain is already quite low. If the improbability that a piece of music is introduced with a refrain comes to the fore, there are some signs of an error in clustering. B. that the last considered segment was erroneously assigned to the second segment class.

In Fig. 4b It was shown how the stanza / chorus determination was performed on the basis of two available segment classes. After this stanza / refrain determination, the remaining segment classes may then be designated in a block 45, where an outro will possibly be the segment class having the last segment of the piece, while an intro will be the segment class comprising the first Segment of a piece in itself.

The following is based on Fig. 4a It shows how to determine the two segment classes that represent the candidates for the in Fig. 4b given algorithm.

In general, an assignment of the label "stanza" and "refrain" is performed in the labeling, whereby one segment group is marked as a stanza segment group, while the other segment group is marked as a refrain segment group. Basically, this concept is based on the assumption (A1) that the two clusters (segment groups) with the highest similarity values, ie cluster 1 and cluster 2, correspond to the chorus and stanza clusters. The last of these two clusters is the refrain cluster, assuming that a verse follows a chorus.

The experience from numerous tests has shown that cluster 1 in most cases corresponds to the refrain. For cluster 2, however, the assumption (A1) is often not fulfilled. This situation usually occurs when there is either a third, frequently repeating part in the play, eg. As a bridge, with a high similarity of intro and outro, or for the not uncommon case that a segment in the piece has a high similarity to the chorus, thus also has a high overall similarity, the similarity to the chorus but just not great is enough to still belong to cluster 1.

Research has shown that this situation often occurs for variations of the refrain at the end of the piece. In order to mark (label) chorus and stanza correctly with as high a certainty as possible, the in Fig. 4b described segment selection in that, as shown in Fig. 4a is shown, the two candidates for the verse-chorus selection is determined depending on the existing in the same segments.

First, in a step 46, the cluster or segment group with the highest similarity value (value of the component of V which is once a maximum for the segment class determined first, ie segment 7 in the example of FIG Fig. 7 , was), that is, the segment group that at the first pass of Fig. 1 has been identified as the first candidate included in the stanza refrain selection.

It is now questionable which other segment group will be the second participant in the verse-chorus selection. The most likely candidate is the second highest segment class, that is, the segment class that passes through the in Fig. 1 described concept is found. However, this does not always have to be this way. Therefore, for the second highest segment class (segment 5 in Fig. 7 ), that is, cluster 2 checks whether this class has only a single segment or exactly two segments, one of them the two segments is the first segment and the other segment of the two is the last segment in the song (block 47).

If, on the other hand, the question is answered with "No", the second highest segment class has, for example, B. at least three segments, or two segments, one of which is within the piece and not at the "edge" of the piece, the second segment class initially remains in the selection and is henceforth referred to as "Second Cluster".

On the other hand, if the question is answered "yes" in block 47, then the second highest class is eliminated (block 48a), then it is replaced by the segment class most commonly found in the entire song (in other words, containing the most segments) and does not correspond to the highest segment class (cluster 1). This segment class will henceforth be referred to as "Second Cluster".

Second clusters, as explained below, still have to measure themselves with a third segment class (48b), which is referred to as a "third cluster" in order to ultimately survive the selection process as a candidate.

The segment class "Third Cluster" corresponds to the cluster, which occurs most frequently in the entire song, but neither the highest segment class (cluster 1) nor the segment class "Second Cluster" corresponds, so to speak, the next most common (often equally common) occurring clusters by cluster 1 and "Second Cluster".

With regard to the so-called bridge problem, it is now checked for "third cluster" whether it belongs more in the stanza-refrain selection than "second cluster" or not. This happens because "Second Cluster" and "Third Cluster" often occur the same number of times, so one of them may represent a bridge or another recurring intermediate part. To ensure that the segment class is selected from the two that most closely corresponds to the stanza or chorus, so not a bridge or other intermediate piece, the investigations shown in blocks 49a, 49b, 49c are performed.

The first examination in block 49a is to examine whether each segment of third cluster has a certain minimum length, using as threshold z. B. 4% of the total song length is preferred. Other values between 2% and 10% can also lead to meaningful results.

In a block 49b, it is then examined whether ThirdCluster has a greater total portion of the song than SecondCluster. To do this, the total time of all segments in ThirdCluster is added up and compared to the corresponding total of all Segments in SecondCluster, where ThirdCluster has a larger overall song share than SecondCluster, if the accumulated segments in ThirdCluster are greater than the accumulated SecondCluster segments.

In block 49c, it is finally checked whether the distance of the segments from third cluster to the segments from cluster 1, ie the most frequent cluster, is constant, ie. H. whether a regularity is evident in the sequence.

If all these three conditions are answered with "yes", ThirdCluster enters the verse-chorus selection. If, on the other hand, at least one of these conditions is not met, ThirdCluster does not get into the stanza-refrain selection. Instead, SecondCluster enters the stanza-refrain selection as it passes through a block 50 in Fig. 4a is shown. This completes the "Candidate search" for the verse-chorus selection, and the in Fig. 4b shown algorithm, which is finally determined which Segment class that includes stanzas, and which class of segments includes the chorus.

It should be noted at this point that the three conditions in the blocks 49a, 49b, 49c could alternatively also be weighted, so that z. For example, a no answer in block 49a will be "overruled" if both the query in block 49b and the query in block 49c are answered "yes." Alternatively, a condition of the three conditions could be emphasized, so that z. For example, it only examines whether there is regularity of the sequence between the third segment class and the first segment class, while the queries in blocks 49a and 49b are not performed or performed only if the query in block 49c is "no". answered, but z. B. a relatively large total amount in block 49b and relatively large minimum quantities in block 49a are determined.

Alternative combinations are also possible, and for a low-level investigation, only polling one of the blocks 49a, 49b, 49c will be sufficient for certain implementations.

Hereinafter, exemplary implementations of the block 526 for performing a music summary are set forth. So there are different possibilities, which can be stored as music summary. Two of them are described below, namely the option entitled "Refrain" and the option entitled "Medley".

The refrain option is to choose a version of the chorus as a summary. This will attempt to choose a chorus version that lasts between 20 and 30 seconds if possible. If a segment with such a length is not contained in the refrain cluster, a version is chosen which has the smallest possible deviation to a length of 25 seconds. Is the chosen chorus longer than 30 seconds, it is hidden in this embodiment for 30 seconds and if it is shorter than 20 seconds, it will be extended to 30 seconds with the following segment.

Storing a medley for the second option is more like an actual summary of a piece of music. Here, a section of the stanza, a section of the chorus and a section of a third segment are constructed in their actual chronological order as a medley. The third segment is selected from a cluster that has the largest total portion of the song and is not a verse or chorus.

• "drittes Segment"-Strophe-Refrain;
• Strophe-Refrain-"drittes Segment"; oder
• Strophe-"drittes Segment"-Refrain.

The following priority is used to search for the most appropriate sequence of segments:

• "third segment" stanza refrain;
• Stanza refrain "third segment"; or
• Stanza "third segment" refrain.

The selected segments are not installed in their full length in the medley. The length is preferably set to a fixed 10 seconds per segment, so that a total of 30 seconds is created again. However, alternative values are also readily feasible.

Preferably, in order to save computation time after the feature extraction in block 502 and after block 508, respectively, a grouping of a plurality of feature vectors is performed in block 510 by forming an average over the grouped feature vectors. The grouping can save computing time in the next processing step, the calculation of the similarity matrix. To calculate the similarity matrix, a distance is determined between all possible combinations of two feature vectors. Dara-us surrendered with n vectors over the whole piece of nxn calculations. A grouping factor g indicates how many consecutive feature vectors are grouped into a vector by averaging. This can reduce the number of calculations.

The grouping is also a kind of noise suppression in which small changes in the feature expression of successive vectors are compensated on average. This property has a positive effect on finding large song structures.

The concept according to the invention makes it possible to navigate through the calculated segments by means of a special music player and to selectively select individual segments, so that a consumer in a music shop can immediately immediately refrain, for example by pressing a certain key or by activating a certain software command jump to see if the chorus pleases him, and then maybe listen to a stanza so that the consumer can finally make a purchase decision. This makes it easy for a prospective buyer to hear from a piece exactly what he is particularly interested in, while he z. B. the solo or the bridge then actually save for the listening pleasure at home.

Alternatively, the concept according to the invention is also of great advantage for a music store, since the customer can listen in and therefore also quickly and ultimately buy, so that the customers do not have to wait long to listen in, but also quickly get their turn. This is because a user does not have to constantly go back and forth, but gets targeted and quickly all the information of the piece he would like to have.

Furthermore, reference is made to a significant advantage of the inventive concept, namely that in particular Reason for the post-correction of the segmentation no information of the piece will be lost. Thus, although all segments, which are preferably shorter than 6 seconds, merged with the predecessor or successor segment. However, no segments as short as they are will be eliminated. This has the advantage that the user can basically listen to everything in the play, so that a striking but clear piece that would very well have fallen off a segmentation post-correction that would have actually completely eliminated a portion of the play, nevertheless is available to the user so that he may perhaps make a well considered purchase decision just because of the short distinctive piece.

However, the present invention is also applicable in other application scenarios, for example in advertising monitoring, ie where an advertiser wants to check whether the audio piece for which he has bought advertising time, has actually been played over the entire length. An audio piece may include, for example, music segments, speaker segments, and noise segments. The Segmentierungsalgori thmus, so the segmentation and subsequent classification in segment groups then allows a quick and much less expensive review than a complete sample-wise comparison. The efficient checking would simply consist of segment class statistics, that is, a comparison of how many segment classes have been found and how many segments are in each segment class, with a default given the ideal ad item. Thus, it is readily possible for an advertiser to recognize whether or not a broadcaster or television station has actually broadcast all the main parts (sections) of the commercial signal.

The present invention is further advantageous in that it can be used for searching in large music databases, for example, to listen only to the choruses of many pieces of music, and then to a music program selection perform. In this case, only individual segments would be selected from the "class" segmented class of many different pieces and provided by a program provider. Alternatively, there could also be an interest, from an interpreter all z. B. to compare guitar solo with each other. According to the invention, these can also readily be provided by always selecting one or more segments (if present) in the segment class designated "Solo" from a large number of pieces of music, e.g. B. assembled and provided as a file.

Still other applications are to mix stanzas and choruses from different audio pieces, which will be particularly interesting for DJs and opens up completely new possibilities of creative music synthesis, which can be carried out easily and above all automatically accurately. Thus, the inventive concept can be easily automated, since it requires at no point a user intervention. This means that users of the inventive concept by no means require special training, except for. For example, a common skill in dealing with normal software user interfaces.

Depending on the practical circumstances, the inventive concept can be implemented in hardware or in software. The implementation may be on a digital storage medium, in particular a floppy disk or CD with electronically readable control signals, which may interact with a programmable computer system such that the corresponding method is executed. In general, the invention thus also consists in a computer program product with a program code stored on a machine-readable carrier for carrying out the method according to the invention, when the computer program product runs on a computer. In other words puts the invention thus is a computer program with a program code for carrying out the method when the computer program runs on a computer.

Claims (21)

1. Apparatus for changing a segmentation of an audio piece into temporal segments, wherein the audio piece is structured into main parts repeatedly occurring in the audio piece, comprising:

   means (10, 12, 14) for providing a representation of the audio piece, in which the segments of the audio piece are assigned into various segment classes, wherein one segment class each is associated with a main part, wherein the means (10, 12, 14) for providing is formed to provide a novelty value for segment boundaries of the short segment, the novelty value indicating how much novelty content the short segment has with reference to a segment adjoining the segment boundary; and

   segment correction means (20) for correcting the segmentation, wherein the segment correction means (20) is formed to merge a short segment with a length shorter than a predetermined minimum length with a temporal predecessor segment or a temporal successor segment to obtain a changed segmentation of the audio signal, and wherein the segment correction means (20) is formed to merge the short segment with the segment adjoining the segment boundary of the short segment, which has a novelty value indicating a lower novelty content compared with a novelty content at another segment boundary of the short segment.
2. Apparatus of claim 1, wherein the segment correction means (20) is formed to further use a segment class membership of the short segment for merging the short segment.
3. Apparatus of claim 1 or 2, wherein the segment correction means (20) is formed to determine such segments as short segments, the temporal length of which is smaller than 18 seconds and in particular smaller than 12 seconds.
4. Apparatus of one of the preceding claims, wherein the segment correction means (20) is formed to merge the short segment with the temporal predecessor segment or the temporal successor segment using information on a segment class membership of a temporal predecessor segment or a temporal successor segment or the short segment itself.
5. Apparatus of claim 1, wherein the segment correction means (20) is formed to perform the merging due to the novelty value only for short segments having a predetermined minimum length smaller than 8 seconds and in particular smaller than 6 seconds.
6. Apparatus of claim 1 or 5, wherein the segment correction means (20) is formed to merge only such short segments due to an examination of a novelty value that could not be merged in a previous examination using information on a segment class membership of the short segment, the temporal predecessor segment, or the temporal successor segment.
7. Apparatus of one of the preceding claims, further comprising:

   segment assignment conflict means (18) formed to calculate a first similarity value of the conflict segment to a segment in a first segment class and to calculate a second similarity value of the conflict segment to a segment in a second segment class in the case in which a conflict segment should be associated with two different segment classes by the means (14) for assigning, and

   wherein means (14) for assigning is formed to remove the conflict segment from the first segment class and assign it to the second segment class in the case in which the second similarity value indicates stronger similarity of the conflict segment to the segment of the second segment class.
8. Apparatus of claim 7, wherein the segment assignment conflict means (18) is formed to assign a tendency to the first segment class to the segment in the case of a removal of the segment from the first segment class or to assign a tendency to the second segment class to the segment in the case of a removal of the segment not having taken place.
9. Apparatus of one of the preceding claims, wherein the segmentation correction means (20) is formed to ascertain, for a segment shorter than a predetermined minimum length, whether a tendency of the segment matches a segment class to which a temporally preceding segment belongs, and to merge the segment with the temporally preceding segment in this case, or which is formed to ascertain, for a segment shorter than a predetermined minimum length, whether a tendency of the segment indicates a segment class to which a temporally following segment belongs, and to merge the segment with the temporally following segment in this case.
10. Apparatus of one of the preceding claims, wherein the segmentation correction means (20) is formed to merge temporally successive segments belonging to the same segment class.
11. Apparatus of one of the preceding claims, wherein the segmentation correction means (20) is formed to select only segments for correcting the segments that have a temporal segment length shorter than a predetermined minimum length.
12. Apparatus of claim 11, wherein the segmentation correction means (20) is formed to merge a selected segment from a second segment class, the temporal predecessor segment of which and the temporal successor segment of which belong to a first segment class, with the predecessor segment and the successor segment.
13. Apparatus of claim 11 or 12, wherein the segmentation correction means (20) is formed to merge a segment that is in a segment class only including a single segment with the preceding segment or the following segment.
14. Apparatus of claim 11, 12, or 13, wherein the segmentation correction means (20) is formed to merge several selected segments that are in the same segment class with a temporally preceding segment each or a temporally following segment each, when all selected segments of the segment class include predecessor segments from one and the same segment class or successor segments from one and the same segment class.
15. Apparatus of one of the preceding claims, wherein the segmentation correction means (20) is formed to determine, for a segment having a smaller temporal length than a predetermined minimum length, a first novelty value at a beginning of the segment and to determine a second novelty value at an end of the segment, and to merge the segment with a temporally following segment, when the first novelty value is greater than the second novelty value, or to merge the segment with a temporally preceding segment, when the first novelty value is smaller than the second novelty value.
16. Apparatus of one of the preceding claims, wherein the segmentation correction means (20) is formed to perform various correction measures depending on various predetermined segment lengths.
17. Apparatus of one of the preceding claims, wherein the means (10, 12, 14) for providing the representation of the audio piece comprises:

    means (10) for providing a similarity representation for the segments, wherein the similarity representation for each segment comprises an associated plurality of similarity values, wherein the similarity values indicate how similar the segment is to each other segment of the audio piece;

    means (12) for calculating a similarity threshold for a segment using the plurality of the similarity values associated with the segment; and

    means (14) for assigning a segment to a segment class, when the similarity value of the segment meets a predetermined condition referring to the similarity threshold value.
18. Method for changing a segmentation of an audio piece into temporal segments, wherein the audio piece is structured into main parts repeatedly occurring in the audio piece, comprising:

    providing (10, 12, 14) a representation of the audio piece, in which the segments of the audio piece are assigned into various segment classes, wherein one segment class each is associated with a main part, wherein in the step of providing a novelty value is provided for segment boundaries of the short segment, the novelty value indicating how much novelty content the short segment has with reference to a segment adjoining the segment boundary; and

    correcting (20) the segmentation by merging a short segment with a length shorter than a predetermined minimum length with a temporal predecessor segment or a temporal successor segment, in order to obtain a changed segmentation of the audio signal, wherein in the step of correcting the short segment is merged with the segment adjoining the segment boundary of the short segment, which has a novelty value indicating a lower novelty content compared with a novelty content at another segment boundary of the short segment.
19. Apparatus for changing a segmentation of an audio piece into temporal segments, wherein the audio piece is structured into main parts repeatedly occurring in the audio piece, comprising:

    means (10, 12, 14) for providing a representation of the audio piece, in which the segments of the audio piece are assigned into various segment classes, wherein one segment class each is associated with a main part;

    segment correction means (20) for correcting the segmentation, wherein the segment correction means (20) is formed to merge a short segment with a length shorter than a predetermined minimum length with a temporal predecessor segment or a temporal successor segment to obtain a changed segmentation of the audio signal; and

    segment assignment conflict means (18) formed to calculate a first similarity value of the conflict segment to a segment of a first segment class and to calculate a second similarity value of the conflict segment to a segment of a second segment class in the case in which a conflict segment should be associated with two different segment classes by the means (14) for assigning, wherein the segment assignment conflict means (18) is formed to assign a tendency to the first segment class to the segment in the case of a removal of the segment from the first segment class or to assign a tendency to the second segment class to the segment in the case of a removal of the segment not having taken place,

    wherein means (14) for assigning is formed to remove the conflict segment from the first segment class and assign it to the second segment class in the case in which the second similarity value indicates stronger similarity of the conflict segment to the segment of the second segment class, and
    wherein segmentation correction means (20) is formed to ascertain, for a segment shorter than a predetermined minimum length, whether a tendency of the segment matches a segment class to which a temporally preceding segment belongs, and to merge the segment with the temporally preceding segment in this case, or wherein the segment correction means (20) is formed to ascertain, for a segment shorter than a predetermined minimum length, whether a tendency of the segment indicates a segment class to which a temporally following segment belongs, and to merge the segment with the temporally following segment in this case.
20. Method for changing a segmentation of an audio piece into temporal segments, wherein the audio piece is structured into main parts repeatedly occurring in the audio piece, comprising:

    providing (10, 12, 14) a representation of the audio piece, in which the segments of the audio piece are assigned into various segment classes, wherein one segment class each is associated with a main part; and

    correcting (20) the segmentation by merging a short segment with a length shorter than a predetermined minimum length with a temporal predecessor segment or a temporal successor segment, in order to obtain a changed segmentation of the audio signal,

    in a case in which a conflict segment should be associated with two different segment classes, calculating a first similarity value of the conflict segment to a segment of a first segment class and calculating a second similarity value of the conflict segment to a segment of a second segment class,

    in case of a removal of the segment from the first segment class, assigning a tendency to the first segment class to the segment, or

    in case of a removal of the segment not having taken place, assigning a tendency to the second segment class, and

    in a case in which the second similarity value indicates stronger similarity of the conflict segment to the segment of the second segment class, removing the conflict segment from the first segment class and assigning it to the second segment class,
    wherein in the step of correcting the following steps are performed:

    for a segment shorter than a predetermined minimum length, ascertaining, whether a tendency of the segment matches a segment class to which a temporally preceding segment belongs, and, in this case, merging the segment with the temporally preceding segment, or

    for a segment shorter than a predetermined minimum length, ascertaining, whether a tendency of the segment indicates a segment class to which a temporally following segment belongs, and, in this case, merging the segment with the temporally following segment.
21. Computer program with a program code adapted for performing the method of changing a segmentation according to claim 18 or 20, when the computer program is executed on a computer.

Images