Automatic Repeats Detection with Custom Endings

• Jun 21, 2012 - 01:09
Type
Functional
Severity
S5 - Suggestion
Status
active
Regression
No
Workaround
No
Project

I wish MuseScore had a feature for detecting automatically repeating segments, and compacting notation by using the proper vertical bars, along with the necessary 1. and 2. voltas for custom endings, when needed. I've worked to a patch (attached to this Issue) for realizing such a feature, that currently works on some simple scores I'm playing with, effectively reducing their size on screen and on paper when printed.

It had all started by checking whether this could have been written as a plugin

http://musescore-developer.685061.n2.nabble.com/Detection-of-repeating-…

but it turned out that it was not possible, so I've produced a patch to the code, realizing a new "Edit -> Repeat Detector" menu entry that activates the feature.

Pictures of the result of applying this feature on a simple test-case can be found at:

http://retis.sssup.it/~tommaso/mscore-repeat-detector-before.png
http://retis.sssup.it/~tommaso/mscore-repeat-detector-after.png

Features/limitations:
-) it detects perfectly repeating contiguous whole measures;
-) if the repetition slightly differs for a few measures at the end, then the usual 1. and 2. voltas are used to denote the needed variations on the first and second play;
-) two options are used to control the behavior:
-) min_repeat_len is the minimum length (in measures) of a repeating segment;
-) max_volta_len is the maximum length (in measures) of the different part at the repeating segment end (the different 1. and 2. variations are covered by voltas);
-) these parameters might be set in a dialog popping up when activating this feature, so that the user can fine-tune them (unimplemented yet, but planned).

Technical detail:
-) comparison of measures is based on their XML export, where the measure time (tick) has been properly shifted so that two identical measures in different parts of the score have the same identical XML; some times measures embed slight differences that are not visible on the screen (this happens even when editing very simple scores with MuseScore), and this causes the algorithm to not recognize them as identical;
-) complexity is cubic in the number of measures in the score (lots of improvement would be possible, but this already fits my trivial needs -- I hope).

Please, provide some feedback, thanks.

Tommaso

Attachment Size
mscore-repeat-detector.patch 10.72 KB

Comments

Is it something that you use often? I'm interested to hear the typical use cases you have in mind.

In my mind it seems unusual to take the trouble of writing out music twice and then understand and tweak a set of parameters so that the software can detect the repetition in a desired way and collapse the measures into repeats with alternate endings.

Sure, David, a clarification is due, the scenario you describe is absurd for me as much as it is for you :-).

So, my scenario is:
-) I find some interesting music that I like to learn/play on the Internet, normally in form of MIDI files;
-) I open it with MuseScore, then I simplify it and often adapt it to the one instrument (or a few) voice(s) I'm interested into (i.e., cut out many voices I'm not interested into), sometimes I transpose it if the original is too difficult for me;
-) then I print it down, and I can play it, and/or read it directly from the screen in MuseScore, etc......
Both when printed on paper, and when displayed on screen, if the notation gets more compact, I get happier, as I have to switch fewer times my hands between my instrument and the PC (or turn paper pages). So, automatic detection of repeating segments allows me to make the notation more compact easily and quickly (and I don't have to compare the segments note by note by myself in order to be really sure that the notes are exactly the same -- in my scenario, I don't know the piece so well to the point to realize whether there's any slight difference between the two repetitions -- so, while learning the piece, the automatic detection of repeats also makes it easier for me to realize that, hey, now I just have to repeat again this part I've already read).

Hope now it's clearer.

Anybody who ever has or will open a MIDI file with MuseScore gratefully uses such a feature, if available. With MuseScore you can expand repetitions when saving as (generating) a MIDI file, but not collapse them during open (the reverse way). Imho, this is a valuable feature I am very interested in!

Not something I would use very often myself, but I can see how that would be incredibly useful to some people.

I think this patch should be included in MuseScore at some future point :)

Any reason the patch doesn't loop through and detect all the repeats? (It only detects the first instance, requiring several menu selections).

Various enhancements would be possible, but before trying them out, I'd like to see whether the patch can actually be merged.
Among the ideas that flood my mind:
-) the current patch has 2 parameters (see description above) that might be left tunable for the user through a dialog that pops up when you invoke the feature;
-) the dialog might contain a "scope" of the repeats search, i.e., the common case is for the user to actually provide a hint for the interval (e.g., a selection of measures) in which to search for repeating patterns;
-) the dialog might contain a few options, so as to consider or ignore various notation elements while searching (e.g., ignore notes velocity or embellishments possibly present in the measures, etc.);
-) given a score, the way you can "compress" it using repeats may not be unique, i.e., various possibilities would lead to different "compression ratio" (sorry for the computer science terms applied to music notation);
-) one possibility could be to search exhaustively for the "optimum compression solution", i.e., the one leading to the maximum savings in terms of overall score length;
-) another possibility might be to identify all the possible repeating patterns at once (out of which some might partially overlap or contain/be contained within each other), and allow the user to check them all, one after the other, deciding which one he/she wants to apply; for example, a dialog or dockable window might show the search results in terms of a list of found matches, then clicking on one of them the user gets a temporary preview of their effect on the score, then a button allows to apply the detected repeat(s) to the score or cancel the whole operation;
-) perhaps the algorithm might try to identify a third repetition with the "3." custom ending as well (but I'm not sure I've ever seen that in real scores, is that actually used in music ?);
-) last, but not least, the performance of the search may be largely improved (useful for very long scores / imported MIDI files).

I've just realized a sketch of the GUI behavior described above. This version of the patch finds all the repeating segments and presents them to the user via a dockable panel. Clicking on each found solution causes a highlight of the repeating segment as a selection, then one can apply/pick it or choose a different one from the list.

You can see how it works at:
http://www.youtube.com/watch?v=84nsUdm5zzE
The patch was already introduced in
http://www.youtube.com/watch?v=JakubiKVrfg&feature=plcp
The new GUI allows users to choose which one(s), among all the repeating segments that have been found in a score, have to be highlighted with the repeating bars notation, so the user can choose the one that suits best his/her own needs/tastes.

STRENGTHS:

  • I like that the list appears in the side bar (rather than a separate dialogue window) to avoid covering the music in the middle of the screen
  • The way that it highlights the measures when you select one of the items in the list is really helpful
  • The repeat detection could save quite a bit of time for people who import MIDI files regularly

CHALLENGES and POSSIBLE SOLUTIONS

  • The chart form is not immediately understandable. Keep in mind that most users will only use this occasionally and may avoid using it altogether if they perceive that it will take more time to learn how to use it than the time it will save them for their current occasion. Consider adopting a more descriptive list even if it means that it takes more lines on the screen (see Chart Form and Descriptive Form examples below)
  • It adds an item to the Edit menu which has very situational usage. Consider the fact that the chart and side bar will be quite obtuse if a curious user applies it to their current score (and that score does not happen to have any repeated measures). My preference would be to remove it from the edit menu (based on the next point)
  • Consider running the repeat detector whenever a user opens a MIDI file. If it detects possible repeat reductions, display the Repeat Reduction sidebar automatically. This makes your new feature highly discoverable, but only in a context where it is most useful

CHART FORM [example]

Beg End Len CEL Red
11  18  8   1   7
12  19  8   2   6

DESCRIPTIVE FORM [example]

Measures 11-18:
Repeats with a 1 measure alternate ending
Reduce score by 7 measures

Measures 12-19:
Repeats with a 2 measure alternate ending
Reduce score by 6 measures

Hi, this sounds as a great news for me! After a quick walkthrough your CLA, I had (much to my regret, being this a hobby-ish thing) to burden my employer, and as the CLA here is mentioning explicitly Intellectual Properties, it seems it will have to go through our layers. I hope they'll provide the necessary clearance. A bit strange that, for this open-source project, it seems that contributing needs a step that is so formal. In many other open-source projects I've seen (including one where I've been contributing for years), it seems sufficient to drop into an e-mail a message like:

I hereby grant permission to licence my contributions to MuseScore under the Gnu General Public Licence.
Therefore, all contributions are to be considered free software; you can redistribute and/or modify them under the terms of the Gnu General Public Licence as published by the Free Software Foundation, version 2 or (at your option) any later version. These contributions are distributed in the hope that they will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

Having MuseScore itself a GPL license granting freedom of use for the software and source code, would you please detail what the CLA adds to that ?

Thanks.

Hey Tommaso,

Granting permission on contributions is only possible when you have the legal ability to do so. If the contract with your employer says that anything you make during working hours is owned by the employer, then you do not have this ability. So if applicable to your case, you'll have to ask permissions to your employer first. If not and you do own the rights, in that case you don't need to ask.

The CLA is in place as a normal legal structure to protect the MuseScore project. It is no different for any other large open source project.

I fully agree with Tommaso that the CLA of MuseScore is overkill. What I see is nothing than the possibility in future to change the license of MuseScore from GPL to something commercial. And this without having to agree with the contributors.

During my days of software devellopment I once contributed to a synchronisation mechanism for ripple control. This mechanism was patented by my company. The part of the company owning this was sold. As I wasn't with the owning company anymore, but still working on synchronisations, I wasn't allowed to use my own but patented ideas anymore.
With this experience - you understand - I decided to not transfer any rights anymore, neither copyrights nor human rights nor civil rights nor whatsoever. As a consequence, I will not contribute to MuseScore under the CLA. And perhaps you think of the fact that others might feel the same.

Thanks for sharing your opinion Manfred, I fully respect it. A CLA comes indeed with a responsibility towards the MuseScore contributors. I'll quote what Richard Stallman said to me when I explained we put a CLA in place for MuseScore: "This is a useful thing to do. Among other things, it will allow you to relicense to new GPL versions easily." Keep in mind, the MuseScore CLA only applies to the MuseScore Code, so not the complete MuseScore project.

Just so you know why this CLA was put in place, here is the history of it. So that's more than a year ago. Werner kept on releasing his code under GPLv2 like he does for more than 15y of open source coding so nothing changed. It's a fair deal between Werner and the code contributors I think, so that MuseScore can move forward. Otherwise, apps such as the Open Goldberg Variations would not have been made.

Don't hesitate to ask if you have more questions or remarks.

Sorry Thomas, I can hardly believe that Richard Stallman understood to support a CLA the sole justification of which was to follow Apple's provision. I had not the opportunity, like you evidently, to meet him personally. But he is widely known as a promotor of free (as in freedom) software and considered Apple to force computing in a cage. I cannot imagine that he converted to the other freedom: the freedom to put the hand in neighbours pocket.

Your argumentation follows a strategy many mangers use to justify their unpopular decisions:
- Don't back out of a prior agreement! A wrong decision is better than no decision. -- Imho, wrong decisions have to be revised. And the reasons given in your history link are not all valid today.
- What we do is state of the art proven by others who did it before. -- I think, multiple licensing did arise only in areas where commercial interests take priority over the free software idea.
- It's not a big deal, others did it also. Come on, join the winning team. -- Can the team also be of lemmings on their way to the coast?

The installation of MuseScore BVBA, I suspect, is an attempt to make money with originally free software. It's influence on the product shifts priorities, at least. I hope for Werner that he can sleep well and is not bothered by dreams of Goethe's Faust.

Hi David,

thanks for your feedback on this feature. A couple of further comments and thoughts:
-) the highlight of the repetition via regular selection might be improved by adding the highlighting of the 2nd repetition as well (currently it selects and highlights only the first repetition), but with some different color; for example, a color for the 1st repetition, a color for the 2nd repetition, and a color for the custom ending parts.
-) the comment on the usability is very helpful. I realize myself that, at a first glance, it might discourage the use by occasional users, as it seems to present too complex information. Though, I was happy that this way of displaying things is very compact on the screen so that the dockable panel remains small. Perhaps one might keep both a compact and extended display mode, and allow users to switch among the 2 (via a preferences option)
-) being this a dockable panel, I guess the feature might be moved to the Display-> menu, taking your advice to not have it in the Edit menu, where far more frequent actions are included
-) apart from when you open a MIDI file, that remains my personal use-case, I'd find it useful in other cases as well, for example if you open a score and try to simplify it (e.g., extracting fewer voices, or simplifying the music so as to make it accessible to a beginner player, etc.); in such cases, the simplified version might happen to have repetitions that the original fully detailed version didn't have, because originally different measures might be now equal in their simplified form.

Finally, a technical issue I have with the "dockable panel" way of implementing it, is that, once I found the repetitions, these should be invalidated as soon as the user tries to edit the score, because he/she can edit without closing the auto-repeat-detection panel. It would be painful to update the panel in real-time as the user edits, because the user might do a number of different actions (modifying, inserting and deleting measures both within detected segments and before and after them). On the other hand, recomputing the detected repetitions at each editing action when the panel is open seems an overkill as well. What would you suggest, from a usability perspective ?

Thanks again.

Reading a bit the history and motivations about this CLA business, I came across a few points:

1) the CLA existence seems motivated from the need to put mscore on the Apple Store;
2) for example, vlc had to be removed from the Apple Store due to it being GPL;
3) vlc can still be installed on Apple devices, i.e., from Cydia;
4) developers may be very happy to voluntarily contribute with GPL code, but not so happy to sign this CLA.

So, my two questions constituting at the same time concrete proposals:

a) why don't you simply make MuseScore available through Cydia, for example ?
b) why don't you handle a separate branch for distributing MuseScore through the Apple Store ? so, you would have two branches, one including all the GPL contributions; the other one, including all the features and contributions whose developers signed the CLA as well.

Any comment is welcome, thanks.

My two cents:

I'm sure Cydia is popular among a relatively small group of hackers, but not having an app in the apo store pretty much means 99% of the world will never know about it or be able to use it. No way would I favor such a path for MuseScore.

Seems this discussion should be continued somewhere else, though - the developer's mailing list, perhaps.

> This ons still seems waiting on Thommaso to sign the CLA?

Hi all,

yes, basically I asked for clearance from my employer, but I don't have it yet.

On a related note, in the mean-time I tried to think a bit more to the situation, and my personal feeling is anyway the one that I would be enthusiastic to release the patch as GPL (and, with ICTs evolving to cloud computing and the like, I think something more appropriate should be seeked, actually), but in the end this CLA is really something that hurts my view and perception of open-source and free software, as I see it should be and it could work.

Probably I should have evaluated better the situation since the beginning, and I should have developed my toy as an independent application that parses MusicXML and writes it back as such. Anyway...

@Tommaso The MuseScore Code as well as any patches applied to it are licensed under GNU GPLv2, so I don't see a conflict with your wish to publish your code under GPL. The MuseScore CLA is no different from other Contributor License Agreements, used by many major open source projects. On this matter MuseScore stands on their shoulders. A CLA is a good thing to have in place, but it comes with responsibility. Myself and many others have trusted this responsibility to Werner and in return he can keep on working on MuseScore and release his code under GPL. I find this a good deal. The choice is yours now.

Tommaso just signed the CLA yesterday, so maybe we can give the patch above another look now?
Being 5 years old I wonder whether it still applies cleanly (actually I seriously doubt it).

Better would be to submit it as PR on GitHub...