Valentin Lageard

Cédric Paternotte

Trolls, bans and reverts: Simulating Wikipedia

come

Introduction

When Wikipedia appeared years ago, it was met with scepticism. How could an army of contributors, many of whom appear to have no special expertise, possibly end up producing any interesting, let alone correct content about topics, including scientific ones? How could knowledge collectively arise from the aggregation of amateurs or ignoramuses? Even if so, how could it possibly rival that of traditional encyclopedias? To the surprise of most, however, Wikipedia turned out to be quite reliable as a source of information. Although it is debatable whether this epistemic feat surpasses, rivals or comes close to that of traditional encyclopedias, hardly anyone could have confidently predicted it.

Why is Wikipedia a reasonably reliable source of knowledge? Tentative explanations abound. Maybe knowledge naturally emerges from the aggregation of ignorant individuals; or maybe enough of them are close enough to expertise regarding the topics they favour. Maybe Wikipedia is run by a close-knit community of elite administrators who strive for reliability and prevent abuse. Maybe the contributors mutually check and police each other. Maybe Wikipedia's technical features, such as history checks, discussion forums and votes are crucial in maintaining the overall quality of most of its pages.

The problem of explaining the reliability of Wikipedia goes beyond mere interest for this specific epistemic entity: it concerns social epistemology as a whole. Although the study of collective epistemic enter-prises is not new, it has mainly focused on cases such as science and the social characteristics that make it epistemically successful. Such works typically assume that science stems from agents who aim for epistemic success or have motivations that happen to further epistemic success as a by-product. By contrast, the Wikipedia community contains a significant proportion of contributors with negative epistemic aims or have non-epistemic motivations that hinder epistemic ones; such contributors include disinformers and trolls.

Accordingly, our aim in this paper is to suggest explanations as to why Wikipedia is reliable despite the non-negligible proportion of contributors that oppose its epistemic aims.

We will be developing and employing computer simulations. This choice stems from the high number both of characteristics of Wikipedia that are possibly relevant to its reliability, and of hypotheses regarding the fundamental mechanisms that warrant such reliability. The simulation allows us to explore a number of possible scenarios and to isolate the specific roles of distinct factors. It also allows us to suggest a pluralist explanation -namely, the claim that it is a combination of factors that is integral to Wikipedia's epistemic reliability -which would have been more difficult to identify and defend otherwise. As we will see, this reliability does not boil down to any isolated factor, be it the wisdom of crowds, the competence of the administrators, etc. More explicitly, our formal model, developed below, suggests that two key features of Wikipedia, (i) the ability of administrators to ban contributors, and (ii) the revert function, which enables contributors to restore a previous, better version of an entry, aid in making Wikipedia entries reliable.

We proceed as follows. We start by listing the various factors that make the epistemic reliability of Wikipedia problematic and justify our focus on disinformers and trolls (Section 2). We identify several possible explanations and highlight the difficulty to adjudicate between them non-formally (Section 3). We introduce a computer simulation of a Wikipedia entry, which includes various factors, in particular contributor actions such as history checks and page reverts, as well as administrative measures such as user bans. The simulation also features contributors with a variety of epistemic and non-epistemic aims -namely regular contributors, disinformers and trolls (Section 4). We then gather the results from simulation runs in a number of contexts, gradually adding obstacles to epistemic reliability and identifying possible solutions to them. Overall, these results suggest a pluralist diagnosis -only a combination of factors of various kinds is able to guarantee its reliability (Section 5). We finally discuss this pluralist explanation as well as the robustness and limits of our results (Section 6).

Why so reliable?

How reliable is Wikipedia? What is the proportion of true to false claims it contains? Even if replies to this question exhibit some degree of disagreement, all agree that Wikipedia is more reliable than anyone would have thought initially, and in particular that it is surprisingly close to the epistemic performance of traditional encyclopedias. The classic source on Wikipedia reliability is Giles (2005), which compares its error rates with that of the Encyclopedia Britannica. On average, there is about one more error in a Wikipedia entry, and the error rate displays more variance. Moreover, "Wikipedia contained more entries than Britannica with zero errors, but two Wikipedia articles were worse than the worst of Britannica's" (Magnus 2009: 75). Even if Wikipedia may be seen as epistemically inferior to Britannica, the point is that the gap between them is surprisingly narrow.

However, the analysis of Wikipedia's reliability cannot be static, because its entries are constantly modified. As Magnus (2009) further emphasises, the speed with which new errors are corrected should also impact our assessment of Wikipedia's epistemic success. It would be damaging that errors, even if all are ultimately corrected, persist for too long. Moreover, the advantages of Wikipedia may not stem from its reliability. According to Fallis (2011), Wikipedia also fares well with respect to Goldman's (1987) criteria of power, speed and fecundity.1 Still, we will focus on the problem of explaining Wikipedia's reliability only -focusing on the proportion and persistence of errors -as it constitutes its most intriguing feature.

The reliability of Wikipedia is puzzling for a number of reasons. In what follows, we focus on what we consider to be the three major, partly interrelated problems that a satisfying explanation of Wikipedia's epistemic success must solve.

First, it somehow emerges from the individual contributions of a high number of contributors with unknown expertise -anyone can edit a Wikipedia entry, so the average reliability of most contributors may be low. As a consequence, "the true miracle of Wikipedia is that this open system of amateur user contributions and edits doesn't simply collapse into anarchy." (Anderson 2006: 71). What process could aggregate a crowd of individual ignorance into a collective body of information? Call this the amateur problem. This is not to say that no expert ever contributes to Wikipedia. However, if such experts are a minority, we should not expect their contributions to be more persistent than any other edit, as anyone may alter or delete them. Of course, the importance of the problem depends on the real proportion of non-experts among contributors, which has not been estimated.

A second, related issue stems from the fact that Wikipedia entries are fundamentally volatile bodies of text. By contrast to collective epistemic enterprises such as science, Wikipedia is constantly open to unsupervised revisions. Entries may be instantly modified by any individual contributor. Wikipedia offers no peer review process and no selection of contributors who may revise an entry. As a consequence, given the high number of contributors, most entries are modified on a daily basis and are thus unstable. Moreover, the problem is not only the sheer quantity of revisions but their scale. The content of an entry may be substantively or totally deleted without difficulty. Indeed, massive deletions have always been frequent in Wikipedia (Viegas et al. 2004). An aggravating factor is the asymmetry of effort needed to contribute positively or negatively: it is easier and faster to suppress some content than to add it (which takes time, if only to write it all). Not only are revisions frequent; we should expect them to be so, given this effort asymmetry. Overall, the quantity and scale of revisions constitutes what we call the volatility problem. It partly stems from the amateur problem: many unskilled contributors naturally allow for many errors in revisions and deletions. But regardless of its causes, the volatility problem is fundamentally epistemic: it supposes that content is only informative if it is present during a large enough proportion of time. The fact that informative content tends not to disappear (or reappears often enough) thus begs for an explanation that goes beyond the amateur problem.

A third issue stems from a characteristic of Wikipedia that make it stand out among more typically discussed cases such as epistemic enterprises such as science. As stated in the introduction, studies of science in social epistemology have traditionally considered it as based on individuals that either aim for epistemic success or whose motivations are shown to indirectly favour epistemic success. For instance, Kitcher (1990) compares collective epistemic success (the probability of obtaining a result) in the case of 'pure', truth-seeking scientists and of scientists motivated by reputation or personal gain; Strevens (2003) further stresses the beneficial epistemic consequences of egoistic motives. In Weisberg & Muldoon's (2009) 'epistemic landscape' approach, scientists are attracted by epistemically significant results. 2 Zollman (2007) considers agents who choose theories that appear to be best supported by the available evidence; and so on. All in all, agents in such formal models or simulations are epistemically beneficial. 3 Although perfectly fine on their own, the lessons drawn from such approaches cannot be adduced in order to understand Wikipedia. This is because Wikipedia contributors have a variety of motives, some of which are epistemically detrimental. Some contributors are disinformers: they intentionally insert falsities or delete true claims, for instance because of vested interests, personal opposition to a certain view, etc. Disinformers have anti-epistemic aims -they squarely oppose epistemic success. Other contributors have non-epistemic, or a-epistemic aims, that is, their contributions stem from motives whose results are not correlated with epistemic success. For instance, some contribute only to have fun or to waste other people's efforts. Following Frankfurt (2005), such contributors may be called bullshitters, or to the Internet jargon: trolls. Disinformers and trolls give rise to the vandalism problem, that is, the fact that a significant number of Wikipedia contributors are actively involved in the modification or deletion of true content and/or the insertion of false content.

Put together, these three problems make Wikipedia's reliability intriguing. How could Wikipedia's epistemic success come close to that of traditional encyclopedias, given that its content is highly unstable, most of its contributors neophytes and some of the rest disinformers and trolls? How can Wikipedia be reliable in the face of contributor amateurism, content volatility and epistemic vandalism? We now turn to possible explanations. Note already that the number and variety of problems may make it look unlikely that a unique remedy could solve them all. But this verdict would be premature: we are dealing with a complex system, about which any claim may be difficult to assess in an analytical fashion.

Hypotheses

As the use of Wikipedia is widespread, concerns regarding its reliability abound, but so do tentative explanations of this reliability. In what follows, we introduce a number of them. Our aim is twofold. First, we want to highlight the sheer number and variety of types of possibly relevant factors or processes. Second, our list of explanations should make clear that none of them is fully convincing at first glance, and that any assessment of possibly relevant factors is unlikely to be reached analytically or non-formally, which in turn motivates our appeal to a computer simulation.

The first explanation of Wikipedia's reliability is based on the socalled 'wisdom of crowds' phenomenon (Surowiecki 2004). It is usually invoked when the aggregation of individual outputs is better or more accurate than any of them considered in isolation. One explanation of this phenomenon is that individual errors may 'cancel out' one another, so that even if all individuals are mistaken, the sum or aggregation of their opinions becomes less so. However, it is far from clear that this phenomenon is responsible for the reliability of Wikipedia. The wisdom of the crowds typically happens in a context in which individual assessments are aggregated into a unique collective assessment. By contrast, Wikipedia entries consist in the juxtaposition of individual contributions that concern various aspects of a topic. Part of entries can rarely be seen as averages of multiple individual contributions, and the errors contained in one part of an entry do not compensate those found in another one -all draw reliability lower. Moreover, the wisdom of the crowd is typically thought to happen when individual opinions are independent (Surowiecki 2004). This condition may be met for some topics but not others, especially when the influential sources of information are few. Overall, it is difficult to understand to what extent the wisdom of the crowd phenomenon may justify Wikipedia's reliability.

Another explanation of Wikipedia's reliability relies on empirical properties of the population of contributors, especially on their distribution. For instance, the elite hypothesis holds that there exists a small proportion of highly reliable, highly active contributors, which would counterbalance the actions of the vast majority of more passive and less reliable contributors. In other words, the reliability of Wikipedia would be safeguarded by a benevolent, efficient elite. The actual number and distribution of reliable contributors is a purely empirical matter (and it does seem that such an elite exists; see Sanger 2009); but the question of their effect on Wikipedia's overall reliability is not. Would a reliable elite be able on its own to decrease the volatility of entries? To stave off disinformers and trolls, which are thought to be quite active as well? How reliable exactly would an elite need to be in order to effectively counterbalance a mass of neophytes?

Relevant aspects of the population of contributors also include the distribution of the anti-epistemically or non-epistemically inclined ones, that is, of disinformers and trolls. Obviously, the lower the proportion of disinformers and trolls in the population, the more reliable Wikipedia will be. So maybe disinformers and trolls are just too small a minority to substantively disrupt Wikipedia. Again, this explanations hinges on an empirical fact, but also on an assessment of the extent to which disinformers and trolls make reliability plummet.

While the previous explanations involve characteristics of the population of contributors, other ones focus on technical features of Wikipedia. A Wikipedia entry is not just characterised by its content at a given time; the history of the changes it underwent are public. Although Wikipedia entries are constantly edited and are thus fluid in a sense, the sequences of past edits are publicly available and can always be checked by anyone. Edits are transparent, and so is the list of the past contributors -even if they are anonymous, their IP addresses are available. 4 This allows one to detect whether an entry has been changed multiple times and in similar ways by a given contributor, for instance, or whether it results from the independent contributions of multiple authors. Of course, the extent and nature of the changes are also transparent. So-called 'edit wars' -sequences of opposite changes due to two or a handful of contributors -become easily detectable as well. According to this transparency hypothesis, this feature of Wikipedia goes a long way towards explaining its reliability.

Moreover, not only can past edits be known, they can also be reverted. That is, an entry can simply be returned to one of its former states, without any need to rewrite it from scratch. This facilitates the fight against disinformers and trolls, for instance, as it seems to compensate for the effort asymmetry between positive and negative contributions (see section 2). Finally, note that the transparency of entries is further compounded by the existence of public discussion pages, in which the contributors freely discuss entry-related issuesits evolution, the changes that have been or may be brought, etc. One may thus come to know whether given parts of the entry content are consensual or divisive, whether they are considered as being targeted for manipulation by disinformers or trolls, among other things. All these features participate in the transparency of the page and the associated ease with which non-epistemically inclined contributors may be staved off.

Still a different set of explanations of Wikipedia's reliability involves its structure and policy. There exist sets of recommendations regarding the acceptable form of entries. For instance, an entry should be adequately sourced -its affirmations should always be backed up by an identifiable source of information. Other recommendations include the necessity to retain a neutral point of view, the prohibition of original research.5 Such recommendations are part of Wikipedia's policy; accordingly, the policy hypothesis holds that they explain a substantial part of Wikipedia's reliability. Of course, they do not prevent contributors from making changes that do not follow them, but provide guidelines that help identify possibly problematic entries. Indeed, sections of entries that do not respect the guidelines are typically flagged for attention, that is, signalled by a tag that may indicate various issues: copy and pasted parts, non-neutral viewpoints, absence of sources, improper references, factual inaccuracy, excessive length, etc. 6 A final explanation to consider is the administration hypothesis. According to population-level hypotheses, the reliability of Wikipedia naturally emerges from the aggregate behaviour and characteristics of its contributors. The administration hypothesis adopts an opposite standpoint by claiming that the reliability of Wikipedia is chiefly explained by some of its high-level features, or by some top-down influences, namely that of its administrators. Wikipedia does not merely result from the combined actions of identical contributors. Some of them are granted an administrator status, which allows them to perform a number of specific actions, such as deleting pages, protecting them from editing, and 'rollbacking' them -reverting them to their previous states much faster than regular contributors. Most importantly, administrators can also ban or unban contributors (identified through their IP address), that is, prevent them from further modifying entries. If contributors could not be banned, disinformers and trolls may keep acting constantly, thus hampering the reliability of Wikipedia by making its volatility skyrocket. The possibility that contributors be banned limits the epistemic pollution due to disinformers or trolls: it motivates them to be subtle or to perform smaller edits than they otherwise would.

We end up with at least five hypotheses pertaining to the reliability of Wikipedia: the wisdom of the crowd hypothesis, the elite hypothesis, the transparency hypothesis, the policy hypothesis and the administration hypothesis. These are not mutually exclusive, as several factors may favour similar results. As all hypotheses share some intuitive appeal, it is difficult to find further grounds for excluding or selecting some of them, or some of their combinations. In what follows, we appeal to a computer simulation of Wikipedia, in order to tease out the respective causal effects of a number of relevant factors. Our results will indicate that the reliability of Wikipedia may stem from a combination of factors without being explainable by any isolated one.

Simulating Wikipedia

The model

Many factors may be responsible for the reliability of Wikipedia. In order to have a better grasp of their respective causal influence, we appeal to a computer simulation of Wikipedia. The aim is not to reproduce Wikipedia's functioning exactly (how could one?), but to use a simplified model that includes what we have previously identified as its main features, in order to study how their variations impact epistemic reliability. As the model is unusual and has more moving parts that the ones typically met in traditional social epistemology, it is worth spending time describing it. This also allows us to clarify our modelling assumptions.

The model aims to represent the dynamic evolution of a Wikipedia entry. An entry is represented by a finite list of information units expressing propositions, each of which may be true or false. Information units are also more or less esoteric, that is, their truth value is more or less difficult to detect (a quantitative level of esotericity is associated to each unit).

Entries get modified by a population of users. Users may do three things (at random): to contribute (add an information to the entry), to check information units in the entry or to check its previous version. To each user is attributed a level of activity (the probability that he acts in a given round), as well as a reliability, which represents both the probability that a unit added by the user is true and his ability to detect false information units. The more reliable the user, the more true (and more esoteric) units he may add, the better he is at detecting falsehoods. At each round of the simulation, depending on their activity level, users stay still or choose an action and perform a number of such actions.

Users may be of three different types: honest users, disinformers and trolls. Honest users add information units, the truth of which depends on a user's reliability; but disinformers always add false information. (So honest users may add false information units, but disinformers may not add true ones). Trolls, which are supposed to make random contributions, always add false information units. They can also act more often than other users at each round, which reflects the typically superior activity level of trolls due to the asymmetry of effort described earlier -the fact that it is easier and faster to add any content whatsoever than to contribute either honestly or deceptively.7

When checking, honest contributors check a number of (randomly determined) information units and delete them if they have detected their falsity; similarly for disinformers with units they have identified as true.8 Trolls delete every information unit they check, regardless of their truth value.

Users may also check a number of previous versions of an entry, which means they check every added or deleted information (as compared with the current version). An honest user will choose the version which is more reliable, that is, whose difference between the numbers of true and of false information units is higher, if there is one, or else keep the current version; similarly with disinformers who choose the less reliable version. Trolls revert to a random version, within a higher pool of past versions than honest users.

Finally, our model includes an administration. When honest users check previous versions, they may report disruptive edits to an administrator. Disruptive edits involve additions of falsities, deletions of truths, reversions to less reliable versions of an entry, or mass modifications (which only trolls can perform). The user responsible for the edits is then banned if these were actually disruptive (and not just considered so by the user).

This leaves us with many factors to consider. Different distributions of user reliability or activity are possible. The proportion of action types (contributions, checks, reverts) has to be chosen, as well as the number of actions for each user type (honest, disinformer, troll) and the distribution of user types.

Results

We now describe the results of a number of simulations run for diverse populations of contributors; we illustrate and interpret the main ones, while only mentioning others in passing. Fig. 1 illustrates what happens with a homogenous population of honest contributors: the quantity of true information grows steadily, while that of false information remains low; the page converges towards a high reliability. Moreover, this holds even if the users' reliability distribution has a very low average -average reliability only impacts the speed of convergence.9 Similarly, increasing the proportion of check/delete actions as compared to regular contributions, increases the speed of convergence (but reduces the total quantity of information contributed).

Note that this should not be interpreted as a solution to the amateur problem. This is because true information cannot be deleted, and so necessarily accumulates as all users are honest. Still, the result would hold even if honest users were allowed to delete true information but only rarely did so, that is, if they were themselves reliable enough. In other words, the entry's reliability stems straightforwardly from the users' characteristics.

Why not model more realistic users? This is because we aim to focus on disinformers and trolls. As we will see, they are powerful enough to counter the positive effects even of such ideal honest users, which in turn suggests that they constitute the main issue for the reliability of Wikipedia.

The introduction of disinformers shakes things up (Fig. 2 -results obtained with a 50% proportion of disinformers). The quantity of false information now steadily increases, although its variance does as well.

condition. Second, there is a constant, noisy but non negligible amount of false information. True information accumulates much more slowly, because it is more volatile. Accordingly, the simulation converge towards a low reliability.

Trolls are even more disruptive than disinformers (Fig. 3), because they prevent any convergence and create an extremely high variance of information. False information dominates true information, although without increasing, and reliability is low on average. But the variance of false information and so of the entry's reliability is high. Because trolls do not care about the truth value of the information they modify, true and false information are almost equally volatile (the difference is due to the actions of honest users).

So far, the results suggest that the model adequately represents the intuitive effects of disinformers and of trolls. The average reliability is lower with disinformers, because false information accumulates. Trolls prevent any such accumulation, but affect even very esoteric pieces of information. In addition, for a given proportion -even a low one -trolls are more harmful than disinformers overall. A 25% proportion of trolls still prevents convergence towards a high reliability; such convergence, although possible for a 5% proportion, still allows for occasional massive deletions (more on this below).

Can users fight against disinformers and trolls ? Increasing the proportion of check/delete actions for honest users is mostly ineffective: it only slows down the negative effects of the disinformers, without affecting trolls. Put differently: the wisdom of the crowd does not withstand the disruptive effect of negative epistemic motivations. What about the presence of a number of elite contributors, with significantly higher reliability than honest users? This is mostly ineffective against trolls, and against disinformers only leads to a slow increase (and high variance) of true information, which still pales when compared to that of false information (see Fig. 4).

Let us now introduce administration, which is able to ban some authors of disruptive edits if they are flagged by honest contributors. Does it suffice to stave off disinformers? It does (Fig. 5). Among other things, administration targets those who add falsities and/or delete truths. Honest users may add falsities, and are sometimes banned; but disinformers perform such actions more often and so are banned faster. This allows their proportion in the population to decrease so that convergence towards reliability is ultimately restored.

However, administration only partly harms trolls. In the long run, it successfully reduces their proportion; however, even small proportions of trolls are disruptive, as Fig. 6 makes clear. A 5% proportion of trolls is sufficient to regularly generate mass deletions of an entry, which thus has to be rebuilt from scratch. In other words, small numbers of trolls are damaging enough to guarantee a serious volatility problem. This is understandable because trolls are typically much more active than honest users -their actions are less costly and so can be performed more often for an equal level of effort.

Trolls turn out to be resistant even to large communities of honest users, even if policed by an administration. But what if the action palette of the honest users is enriched so as to reduce the asymmetry of effort between them and the trolls? This is precisely what the revert action permits -recall it allows one to instantly replace an entry by one of its older versions.

Unfortunately, the revert option alone is not up to the task of countering agents with negative or non-epistemic motivations. First, it does not prevent the convergence towards unreliability produced by disinformers; its main effect is to decrease the volatility of information. Second, it is only effective against a small enough proportion of trolls, in which case the entry becomes stable, because mass deletions are typically reverted, and converges towards a high enough reliability (see Fig. 7). However, if numerous enough, trolls will render an entry highly unstable even if the honest users have a revert option available. This is simply because the high activity of the trolls swamps the corrective effects of the honest users. Overall, the efficiency of the revert option against trolls depends on their proportion, which is an empirical factor. 10 Where are we now? An administration counters the disinformers and reduces the number of trolls; the possibility of reversion counters small proportions of trolls. One obvious solution is thus to combine them (Fig. 8), which indeed restores the convergence of the entry towards high reliability. In the beginning, true information is rare and reliability low with a high variance. Then, the administration starts banning disinformers and trolls, thus reducing their numbers; it also bans some honest users, although at a lower rate. Ultimately, only a small proportion of trolls remains, but the possibility to revert the entry ensure its resilience against their regular mass deletions.

Discussion

Empirical adequacy

Even if several explanations of the reliability of Wikipedia have been proposed, as seen in section 3, the successful epistemic consequence of aggregating diverse, possibly unreliable users, is often cited as one of its main causes. By contrast, our model emphasises the importance of structural and technical characteristics, that is, of factors both beyond and below the individual level.

Perhaps surprisingly, Wikipedia's administration plays a major role by banning troublesome contributors and maintaining their proportion under a manageable threshold. It is difficult to estimate the proportion of disinformers and trolls who contribute to Wikipedia; however, it is inferior to 20% -the estimated proportion of "vandals", that is, of contributors whose contributions are all reverted by others (which includes honest but unreliable ones -see Tsvetkova et al. 2017).

Similarly, it would be easy to underestimate the effect of a simple technical option such as reversion. Indeed, it has rarely been identified as a key factor for the success of Wikipedia, although it is commonly performed. 11 Our model suggests that it may play the key role of rendering innocuous the trolls not yet banned by the administration, by reducing the asymmetry of effort between them and the honest users.

Our simulation results thus points towards the possibility of a pluralist explanation for the reliability of Wikipedia, in which factors of different kinds play complementary roles: the behaviour of honest users matters, but so do the specific technical options available to them and the administration structure to which they can appeal.

Of course, we only claim this particular scenario to be a possible explanation for the reliability of Wikipedia, not a necessary or even a plausible one. For it is difficult to argue that simulation runs based on a particular model have any confirmatory power regarding a particular hypothesis. Still, we think that the possibility of such a multifaceted scenario, in which the respective roles of various factors are clear, is interesting in itself.

How does the model fit the real Wikipedia? The number of model parameters which one can adjust makes any reply difficult. Moreover, many of these parameters correspond to user characteristics that are hardly observable (such as reliability, but also the respective proportions of checking and of contributing, for instance). However, such an assessment is not out of reach. First, recall that the final results, represented in Fig. 8, are only obtained when the proportion of trolls is (roughly) below 10%. Our explanation of the reliability of a Wikipedia entry thus wouldn't fit cases in which a higher proportion of trolls are active. If, as suggested above, the actual proportion of disinformers and trolls and Wikipedia is below 20%, then it is plausible that there are less than 10% of trolls -because it is plausible that a majority of dishonest users are disinformers, trying to propagate false information, rather than trolls, who practice epistemic vandalism for the sake of it.

Second, even if it is difficult to extract predictions from the model, it is notable that it allows for the emergence of a commonly observed Wikipedia phenomenon: edit wars. Edit wars correspond to succession of massive changes and/or reverts in opposite directions -in other words, episodes in which a sizeable amount of information is deleted, then restored, then deleted again, and so on. 12 We take it as a virtue of our model that it shows edit wars taking place from time to time; Fig. 9 provides an illustration.

That an existing Wikipedia phenomenon can unexpectedly appear in our model is already a positive sign. In addition, the empirical adequacy of the conditions under which edit wars may emerge in our model can thus be explored. For instance, in the simulation edit wars typically happen when the proportion of disinformers is close to that of honest users, and when trolls are nearly absent. Edit wars stem from disinformers. This is because troll-based reverts are content-independent and so shouldn't be expected to repeatedly target the same information. Moreover, the frequency and length of edit wars typically increases as users activity involves a higher proportion of version checks. All these features are observable in principle and so may help provide an empirically assessment of the model.

Robustness

Our results are robust with respect to a number of factors. Changes in the reliability distribution (whether uniform or normal with various means) of users only affects the speed of convergence; so do modifications of the number of actions allowed for all users. Increasing the number of actions of trolls affects their disruptive power but not the qualitative results. 13 One change of consequence concerns the proportion of original contributions and of checks for honest agents: more contributions entail more information but a decreased reliability; more checks lead to less information but a higher reliability, which is understandable.

Of particular interest is robustness with respect to the activity profile of various users. There is evidence that user activity is very unequally distributed: a small number of editors make a disproportionate number of modifications, 14 which may be thought as a partial explanation of the reliability of Wikipedia. However, the model results turn out to be robust with respect to activity distribution. For instance, if user activity follows a Pareto distribution (that is, if it is disproportionately concentrated in a small portion of the population of users), we obtain results that are indistinguishable from that of Fig. 8.

Note however that this does not allow us to draw general conclusions, for at least two reasons. First, user activity may be correlated with high reliability: if the most reliable users happen to contribute disproportionately more than unreliable ones, then there may be consequences regarding general reliability (which could possibly support the elite hypothesis). Second, very active users typically contribute to many entries, disproportionate activity distribution may help explain the reliability of Wikipedia as a whole without playing a huge role a the level of an isolated entry, which is what our model represents. 15 That being said, at least one aspect of the simulation is not particularly robust: the volatility measure. This is because the volatility of a piece of information, that is, the total duration of its presence online, crucially depends on specific parameters. For instance, the proportion of honest users as well as the proportion of checks they perform ty-pically impact volatility measures. However, note that this does not prevent one from comparing various volatility values for different scenarios after such parameters have been fixed, which is precisely what we have done. Moreover, this does not qualitatively affect the results.

Modelling choices

There is at least one serious objection that may be levelled against our model, which concerns the idealisation of the behaviour of honest users. To recall, in our model honest users add information which may be true or false (depending on their reliability) and delete information which they have detected as false. In particular they do not delete information whose truth value is unknown. Let us label this characteristic as strong epistemic honesty. One may argue that it is excessive demand and that honest users should only display weak epistemic honesty, by being allowed to err also when they delete information. Surely, even wellmeaning individuals sometimes mistakenly delete true information.

However, modelling this would introduce more arbitrary parameters in the model. One obvious possibility would be to introduce an uncertainty threshold: when a user has not detected the truth value of an information but came close enough, then he would perceive a truth value (to be determined either randomly or on the base of the user's reliability) and delete it if perceived as false. This would necessitate a choice for the value of such a threshold, in a model that already has many moving parts. We thought such arbitrariness too costly, given the fact that there are independent reasons why strong epistemic honesty would suffice. 16 For apart from this technical point, there are at least three possible rejoinders to the objection that honest users should be modelled as displaying weak rather than strong honesty. First, if the empirical frequency of mistaken deletions is low, then our model may still approximate the dynamics of Wikipedia reasonably well. As it happens, there are reasons to consider this frequency to be low, which involve the Wikipedia's verifiability policy. While the addition of non-sourced information is a frowned upon but tolerated practice, the deletion of sourced information is detectable, revertable and typically punished. This implies that honest contributors should be more wary and so less likely to delete true information than to add false informationthey are pushed towards strong epistemic honesty. Note that this line of argument thus brings into the mix an explanatory factor of yet a different kind, that is, a policy-level one.

The second rejoinder is that a homogenous population of weakly epistemic honest users may be considered as equivalent to a heterogenous population of strongly epistemic honest users and of disinformers (which may delete true information). While the respective behaviours of such agents differ in a given run, statistically they amount to the same effects.

The third rejoinder is different. Considering only strongly epistemic honest users both highlights the problem posed by disinformers and trolls and strengthens the relevance of our pluralist explanation. It is testimony to the disruptive power of disinformers and trolls that they can have dire epistemic consequences even within communities that contain numerous strongly epistemic honest users. Moreover, if only a mix of various factors justifies the reliability of Wikipedia in an idealised community, then individual factors are even less likely to guarantee similar results in isolation. If it takes a combination of factors to push idealised users towards collective reliability, then it shouldn't take any less to push less ideal ones. Considering strongly epistemic honest users thus buttresses the need for a pluralist explanation of the reliability of Wikipedia.

Limits of the model

Our simulation model is idealised in a number of other ways as well; let us mention four of them. First, it only represents the evolution of one entry, whereas Wikipedia contains millions of them. 17 . Multiple entries allow for multiple reliability values for each user, depending on the topic considered. Multiplying entries may thus alter our core results at least if there are interaction effects between different entries. For instance, a user suspected of disinformation or trolling regarding one entry may be banned even if its contributions to other entries were legitimate; so if users can be honest regarding some topics and dishonest regarding others, then relatively to one entry, honest users would be more affected by the administration than in our model. However, it is not clear that the results would not be only quantitatively but also qualitatively different. 18 A second idealization concerns the evolving composition of the user population. In our model, the proportion of user types are fixed in each simulation. However, it is possible that these vary as time passes. 17 Currently more than 5 millions -see https : //en.wikipedia.org/wiki/W ikipedia : SizeofW ikipedia 18 One particular difficulty for modelling multiple entries is to find a common time scale. In our graphs, changes are measured as functions of the number of changes of entry version. However, such changes may occur at different paces for different entries, which complicates their combination.

For instance, trolls may drive off honest contributors, tired of endlessly restoring their contributed content. This echoes Sanger's (2009) claim that the reliability of Wikipedia should decrease in the long run because good contributors are discouraged by aggressive behaviours, themselves magnified by user anonymity. In general, it would be interesting to model and explore the negative influence of disinformers and trolls on the motivation of honest users.

Third, the technical options offered by Wikipedia have only been touched upon. As powerful as the revert option is, it is but one of the tools that users have at their disposal. Discussion forums, for instance, allow them to debate the status and evolution of a page before deciding which course of action should be taken. It is difficult to see how this should be modelled though. Another action available to the users is the flagging of various parts of an entry, in order to signal some of its issues (e.g. lack of referenced sources, excessive length, etc.).

Finally, the administration level of Wikipedia too is more complex and layered than in our model. Wikipedia does not just stem from user contributions and administrators with a banning power. Administrators may also protect, restore or delete pages and typically form judgements from the discussions that takes place in forums. They may also be sources of abuse themselves; their actions may be reverted and their status removed. 19 Still, such measures are rare and most admins do regularly ban problematic users.

We conclude this section by discussing the explanatory power of our model. Does it allow us to draw conclusions regarding collective epistemic systems other than Wikipedia? In particular, does it provide reasons to think that explanations of the reliability of such system should be pluralist as well?

Intuitively, the explanatory factors we highlight should be exportable to the extent that the model characteristics are shared by other epistemic systems. On the one hand, many online collective epistemic systems (forums, databases, etc.) are run or supervised by administrators. On the other hand, the Wikipedia revert function, which in our model is crucial for high reliability, is typically not instantiated similarly in other systems. Online databases always include backup versions to which they can be reverted in case of a problem (e.g. hacking). This, however, depends on a decision taken at the administrative level, not by the database contributors themselves. As a consequence, it is not clear whether the epistemic advantages that the revert option brings to Wikipedia, in which it is distributed, would also be present in al-ternative systems in which the revert decision is centralised. Overall, our model results may be generalised to the extent that a distributed revert option is available in the system of interest.

An additional conclusion is that reliability explanations for collective epistemic systems may crucially depend on local properties of such systems. While the distributed revert option is key to the reliability of Wikipedia, that of alternative systems may depend on different technical features, the efficiency of which itself hinges on the kind of anti-epistemic agents who tend to modify them. In other words, there may not be any general explanation of the reliability of collective epistemic systems, but only local ones.

Conclusion

The surprisingly high reliability of Wikipedia has often been seen as a beneficial effect of the aggregation of diverse contributors, or as an instance of the wisdom of crowds phenomenon. Moreover, all potential explanatory factors of this reliability have only been defended non formally. Our aim was to assess such explanations in order to further understand the reliability of a collective knowledge-forming process that is seldom studied in social epistemology: namely, one in which individual agents have non and/or anti-epistemic aims.

We have provided a first computer simulation of a Wikipedia entry, which has allowed us to assess the respective role of factors of different kinds. We identify the main threat for Wikipedia as the presence of negative or non-epistemically motivated contributors, namely disinformers and trolls, which honest contributors cannot be expected to counterbalance.

In our model, the reliability of a Wikipedia entry turns out to stem from the combination of at least two crucial factors: the administration and the revert option. By banning damaging users, the administration is able to stave off disinformers and to reduce the number of trolls; the disruptive effect of the remaining small proportion of trolls is offset by the use of the revert option by honest users. The reliability of Wikipedia is thus due to factors of at least three kinds -individual (honest users), structural (Wikipedia's administration) and technical (the revert option) -none of which would be sufficient in isolation.

Our scenario provides but a possible, and hopefully plausible explanation for the reliability of Wikipedia. However, it suggests that the correct explanation -whatever it is -may be a pluralist one, that is, it may rely on the interaction of various factors rather than amount to a single reliability-inducing process. Wikipedia is a complex system; there is no reason to expect a single factor to be responsible for its success. However, it is not so complex as to be impervious to modelling. We hope this work will pave the way for more sophisticated models that will shed further light on the recent and strange phenomena of online collaborative knowledge.

Figure 1 .

 1 Figure 1. Homogenous population of honest users: overall quantity of true and false information, average reliability of information, average volatility of true and false information.

Figure 2 .

 2 Figure 2. Heterogenous population (50% honest users, 50% disinformers).

Figure 3 .

 3 Figure 3. Heterogenous population (50% honest users, 50% trolls).

Figure 4 .

 4 Figure 4. Heteregenous population (50% disinformers, 30% normal honest users, 20% elite honest users).

Figure 5 .

 5 Figure 5. Heterogenous population (50% honest users, 50% disinformers) with administration.

Figure 6 .

 6 Figure 6. Information volatility for 5% trolls.

Figure 7 .

 7 Figure 7. Information volatility for 5% trolls and with the possibility of reversion.

Figure 8 .

 8 Figure 8. 50% trolls, administration and reversion.

Figure 9 .

 9 Figure 9. One example of an edit war, here starting shortly after version #400 (60% honest users, 40% disinformers, no administration).

SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.2

"We are also concerned with how much knowledge can be acquired from an information source, how fast that knowledge can be acquired, and how many people can acquire it" (Fallis

2011: 305).SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.3

Some of these works have been later criticised for their lack of robustness or artificial assumptions. However, here, we are merely concerned with the assumptions of epistemically beneficial agents that are shared by these works as well as their refinements.SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.4

In the non-formal literature, an earlier similar thesis is that ofHull (1989), who argues that the success of science cannot be properly explained if one neglects the scientists' desire for recognition.SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.5

SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.6

Moreover, there exist a watchlist tool, which allows users to be notified whenever a page of interest is modified.SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.7

The recommendations may be found on: https : //en.wikipedia.org/wiki/W ikipedia : V erif iability

See https : //en.wikipedia.org/wiki/W ikipedia : ContributingtoW ikipedia SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.8

In particular, one salient characteristic of troll actions is that they are particularly repetitive; seeShachaf & Hara (2010). SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.9

Note that in our model, this process involves noise. More precisely, the model compares the reliability of the checking user, modified by some noise, to the reliability of the author of the checked information, also modified by some noise. When the former is greater than the latter, a user will know whether an information is true or false.

 9 For instance, with a gaussian distribution of 0.1 average, the entry's reliability still converges to 1, although more slowly, because of two factors. First, the rate of increase of true information is about a third of what it was for the 0.5 average SimulatingWikipedia_final.

tex; 10/12/2018; 17:12; p.10

SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.11

SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.12

SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.13

SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.14

SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.15

Moreover, the threshold proportion of trolls from which reversion becomes inefficient is typically around 10%; but this value varies depending on parameters such as the size of modifications performed by trolls.SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.16

According to[START_REF] Viegas | Studying cooperation and conflict between authors with history flow visualizations[END_REF], about half of mass deletions are reverted within three minutes.SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.17

See https : //en.wikipedia.org/wiki/W ikipedia : Editwarring SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.18

Note that the results would not necessarily be robust to a decrease in troll activity, because this would both make trolls less disruptive and harder to detect (which hampers the efficiency of the administration / revert solution).

https : //en.wikipedia.org/wiki/W ikipedia : ListofW ikipedians b ynumberofedits15 We thank an anonymous referee for drawing our attention to the distribution of user activity.SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.19

We than an anonymous referee for urging us to mention such motivations.SimulatingWikipedia_final.tex; 10/12/2018;

17:12; p.20

SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.21

For a fuller description of Wikipedia's administrators, see https : //en.wikipedia.org/wiki/W ikipedia : Administrators SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.22

SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.23

SimulatingWikipedia_final.tex; 10/12/2018; 17:12; p.24

Acknowledgments

We thank Anouk Barberousse for her comments on an early version of this work.


N Papadakis

E Provenzi

Vicent Caselles

A Variational Model for Histogram Transfer of Color Images

In this paper we propose a variational formulation for intermediate color histogram equalization of two or more images. We study an energy functional composed by three terms: one tends to approach the cumulative histograms of the original images, the other two tends to maintain the initial colors and geometry. By minimizing this energy, we obtain an algorithm that balances equalization and conservative features. As a result, the original images evolve approaching the intermediate histogram between the original images. As a novel result, this midway histogram does not need to be specified in advance, but it is a natural result of the model. Finally, we provide experiments showing that the proposed method compares well with the state of the art.

I. INTRODUCTION

This paper is devoted to a variational formulation of color grading, that is the color matching of two or more images. We will show that, by minimizing a suitable energy functional, images will be matched to an intermediate common histogram.

Color grading is a main tool for color matching in the post-production industry and its need arises in many applications. For example, the same scene can be photographed with different cameras or under different illumination conditions, resulting in images that may have quite different colors. Other noticeable examples are given by flicker stabilization of video sequences and color balancing, a process that is mostly done manually.

On the other hand, color grading plays an important role also in one of the main topics in computer vision: the numerical comparison of images in order to correlate them or extract mutual information. Applications can be found in different contexts like depth or disparity computation in stereo images, or optical flow computation. Due the use of different cameras or to the variability of light conditions, a color normalization may be an important step previous to the numerical image comparison.

The main approach to color grading is based on the computation of a color transfer map.

Given two images, a source and a target, the problem is to find a mapping that transforms the source into an image with a color statistics that is as similar as possible to that of the target.

For some applications, instead of a target image, one might want to specify a reference palette to be matched. The modified image should keep the geometry of the original one, only its color aspect should be modified.

In this paper we propose a new variational model to transform two or more color images in order to approach their color histograms as much as possible. To briefly describe the process, let us consider here the case of two given color images U , V : we want to transform them into new images u and v that approximately share an intermediate color histogram which is not specified in advance and, at the same time, we want to maintain the geometry of U and V , respectively. Thus, the energy has to combine the comparison of histograms with color and shape constraints (which can be codified by the gradient direction). The shape constraints can be related to the filtering process constrained by the original gradient field used in [START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF].

Let us remark that the mapping to an intermediate histogram permits to distribute the errors in the histogram matching process without privileging one particular image with respect to the others. Up to our knowledge, there is no method in the literature that allows realizing such a process without defining the histogram beforehand.

The plan of the paper is the following. In Section II we provide a review of the state of the art in color grading and midway histogram equalization, emphasizing the role played by the Monge-Kantorovich mass transportation theory. As a technical tool, in Section III we define the L 2 distance between the cumulative histogram of an image I and a reference one and we compute its first variation with respect to I. In Section IV we describe our variational model for intermediate color histogram equalization of a given set of color images. The model penalizes the histogram separation of the set of images and constrains each of them to preserve its color and geometric information. In Section V we describe the algorithm we use to minimize the proposed energy. In Section VI we present some experiments that illustrate the model and compare it with the results obtained using the algorithm proposed in [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF]. Finally, in Section VII we summarize our main conclusions.

II. REVIEW OF THE STATE OF THE ART IN COLOR GRADING AND MIDWAY HISTOGRAM

EQUALIZATION

As previously commented, the central problem in color grading is to find a suitable transfer map. This function can be computed to match simple statistical values, like mean and variance [START_REF] Reinhard | Color transfer between images[END_REF], the covariance matrix [START_REF] Abadpour | A fast and efficient fuzzy color transfer method[END_REF], or the whole color histogram [START_REF] Morovic | Accurate 3D image colour histogram transformation[END_REF]- [START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF]. The matching of statistics can thus be done separately for each channel in the lαβ color space which has uncorrelated components as in [START_REF] Reinhard | Color transfer between images[END_REF]. Another possibility is to compute an affine map [START_REF] Wang | A novel color transfer algorithm for image sequences[END_REF]- [START_REF] Pitié | Statistical signal processing techniques for visual post-production[END_REF] to map the covariance matrices of the two color images. Concerning the map of color histograms, several works have also been proposed, for instance, in [START_REF] Grundland | Color histogram specification by histogram warping[END_REF], matching of color histograms is done on the three channels independently. The color histogram equalization can also be performed by computing a transfer map using mesh deformations to fit the existing histogram to a uniform histograms [START_REF] Pichon | Color histogram equalization through mesh deformation[END_REF].

The formulation of color histogram matching in terms of Monge-Kantorovich's mass transportation theory has been considered in [START_REF] Morovic | Accurate 3D image colour histogram transformation[END_REF], [START_REF] Delon | Fine comparison of images and other problems[END_REF], [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF]. In [START_REF] Morovic | Accurate 3D image colour histogram transformation[END_REF], [START_REF] Delon | Fine comparison of images and other problems[END_REF] the authors compute a transport plan (also called transference plan, see [START_REF] Villani | Topics in optimal transportation[END_REF]) matching two histograms which minimizes the total displacement cost measured in terms of the Earth Mover Distance (EMD) (also called Wasserstein distance [START_REF] Villani | Topics in optimal transportation[END_REF]) and solve this problem using linear programming. This technique has been applied in [START_REF] Delon | Fine comparison of images and other problems[END_REF] to midway color histogram equalization (see [START_REF] Delon | Midway image equalization[END_REF], [START_REF] Cox | Dynamic histogram warping of image pairs for constant image brightness[END_REF] for the case of gray level images), that is, to the problem of finding a midway histogram in the sense of EMD distance [START_REF] Villani | Topics in optimal transportation[END_REF] and computing mappings that transform the original images into images that share this histogram.

In [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF], assuming that the histograms of two given color images can be approximated by multivariate Gaussian distributions, Monge-Kantorovich's formulation is restricted to find a linear map that approximates the transfer of histograms. In practice, this method is applied to transfer the histogram of one image to another although it could be used to define a midway histogram as in [START_REF] Delon | Fine comparison of images and other problems[END_REF], [START_REF] Delon | Midway image equalization[END_REF].

The transfer map in the color grading method proposed in [START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF] is computed by iteratively equalizing all principal axis marginals computed for every possible rotation of the histogram, until convergence. Then the method is refined by a filtering process, constrained by the original gradient field, to reduce possible grain artifacts [START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF].

For later convenience, let us remind here a remark about midway histogram equalization pointed out by Delon [START_REF] Delon | Midway image equalization[END_REF]: if H 0 , H 1 are the cumulative histograms of two original gray-scale images I 0 and I 1 , respectively, then mapping them to have a cumulative histogram which is the direct average of the original ones, i.e. H := (H 0 + H 1 )/2, is not always a suitable choice for midway equalization. An illuminating counterexample is given by the case when I 0 and I 1 are unimodal images with spread modes centered at the levels λ 0 and λ 1 , respectively, with λ 0 = λ 1 .

Ideally, one would expect a midway image to present a single mode centered at (λ 0 + λ 1 )/2, instead it is clear that the composition of I 0 with H-1 • H 0 spreads the gray levels of the image on two modes centered at λ 0 and λ 1 in order to make its histogram correspond as much as possible to H. Thus, it generates new structures that were not present before [START_REF] Delon | Fine comparison of images and other problems[END_REF], [START_REF] Delon | Midway image equalization[END_REF]. Instead, the natural intermediate histogram H is given by

H := H -1 0 + H -1 1 2 -1 . (1)
Let ψ 0 := H-1 • H 0 and ψ 1 := H-1 • H 1 be the mappings of images I 0 and I 1 into images that share the midway histogram H. Defining T := H -1 1 • H 0 , we have

ψ 0 = I + H -1 1 • H 0 2 = I + T 2 , ψ 1 = I + H -1 0 • H 1 2 = I + T -1 2 (2)
and

H = I+T 2 -1 • H 0 = H 1 • I+T -1 2 -1
. Observe that T maps I 0 into an image whose histogram is H 1 . In [START_REF] Cox | Dynamic histogram warping of image pairs for constant image brightness[END_REF] ψ 0 , ψ 1 are computed using a dynamic programming algorithm.

Delon shows that these results can be embedded in a more abstract Monge-Kantorovich's framework which has the advantage to be easily extendible to any dimension, thus permitting to analyze color images. Let h 0 , h 1 be the histograms of two generic images I 0 , I 1 , then h 0 , h 1 can be seen as the Lebesgue densities of the probability measures dµ 0 (x) = h 0 (x)dx, dµ 1 (x) = h 1 (x)dx describing the distribution of the image values. The search of an intermediate histogram between h 0 and h 1 is then equivalent to the search of an intermediate measure between µ 0 and µ 1 . It can be proven that H can be seen as the cumulative distribution function of the middle point µ1 2 of the geodesic that connects µ 0 and µ 1 in the space of probability measures with respect to the quadratic transportation cost [START_REF] Villani | Topics in optimal transportation[END_REF], [START_REF] Delon | Midway image equalization[END_REF]. As already observed, the discrete Monge-Kantorovich problem gives a transport plan that requires the solution of a linear programming problem [START_REF] Morovic | Accurate 3D image colour histogram transformation[END_REF], [START_REF] Delon | Fine comparison of images and other problems[END_REF] to be computed. Let us mention that transport plans permit to split the mass of a bin of a given image histogram and distribute it between several bins of the other histogram. This may be considered a disadvantage. Moreover, the transport plan has the dimension of the product between the number of bins in both the original and the target image, this prevents from using fine quantization of the color space (although this may be unavoidable due to the insufficient quantization of color images). Finally, the extension to the case of more than two color images is not obvious.

As stated in the Introduction, the variational method proposed in this paper approaches the color histogram of the given images without pre-computing it and can be applied to more than two images.

III. A VARIATIONAL APPROACH TO HISTOGRAM TRANSFER

Our aim is to propose a variational formulation for midway histogram equalization. Assume that we are given two color images U : Ω U → R 3 and V : Ω V → R 3 where Ω U , Ω V denote the corresponding image domains. We want to map the images U , V onto new images u, v, respectively, so that u and v share, as much as possible, a common intermediate histogram between those of U and V . Thus, the main ingredients of the proposed energy are the distance between the two color histograms of u and v and the constraints that impose u and v to display the same geometric information as U and V , respectively.

In order to define such an energy, we need to discuss first the variational formulation of histogram transfer based on the L 2 distance between two histograms. In order to make our presentation more comprehensible, we shall discuss first the case of gray level images (which have one-dimensional histograms) and compute the first variation of the corresponding energy.

This will clarify the differences between this functional and the transport approach to midway histogram equalization and will also explain why we need to impose color and geometric constraints. We will then consider the two-dimensional case, N = 2, presenting the energy functional and its first variation. The rigorous computation details and the formulae of the color case, N = 3, are quite cumbersome, for this reason we will discuss them in the Appendix VIII.

Let us first fix the notation that will be used throughout the paper.

A. Notation

We assume that images are defined on a discrete rectangular domain, which we denote by

Ω = {1, . . . , W } × {1, . . . , H} ⊂ N 2 , W, H ≥ 1 being integers; x = (x 1 , x 2 ) denote the
coordinates of an arbitrary pixel in Ω. We assume that each image channel has a normalized dynamic range which we suppose to be [0, 1], so that images are described by vector functions

I : Ω → [0, 1] N , I(x) = (I 1 (x), . . . , I N (x)).
I : [0, 1] N → [0, 1], while H I : [0, 1] N → [0, 1]
will represent the cumulative histogram of I. Thus, if λ = (λ 1 , . . . , λ N ) ∈ [0, 1] N represents the generic N -dimensional intensity level, we have:

H I ( λ) = λ 1 0 • • • λ N 0 h I ( µ)d µ. (3)
Note that the cumulative histogram can be equivalently defined from the image I as:

H I ( λ) = 1 |Ω| |{x ∈ Ω, such that I 1 (x) ≤ λ 1 , . . . , I N (x) ≤ λ N }|, (4)
where | | denotes the area operator.

B. The L 2 distance between the cumulative histogram of a gray-scale image and a reference one and its first variation

Let I : Ω → [0, 1] be a gray level image whose cumulative histogram is H I (λ) = 1 |Ω| |{x ∈ Ω : I(x) ≤ λ}|, λ ∈ [0, 1]. Let H ref (λ)
E(I) = 1 2 1 0 (H I (λ) -H ref (λ)) 2 dλ. (5)
Obviously, the minimum would be attained when

H I (λ) = H ref (λ).
This energy term will be later used together with other (attachment to data and shape-preserving) terms in order to construct an energy for intermediate histogram equalization of a given set of images.

Let us compute the first variation of the energy [START_REF] Pitie | N-dimensional probability density function transfer and its application to colour transfer[END_REF]. For that, observe that we may write

H I (λ) = 1 |Ω| x∈Ω h λ (I(x)), (6)
where

h λ (r) = χ [0,λ] (r) λ, r ≥ 0, (7)
χ [0,λ] being the characteristic function of the set [0, λ]. Hence, if J : Ω → R + denotes a perturbation, we have d d =0 H I+ J (λ) = 1 |Ω| d d =0 x∈Ω h λ (I(x) + J(x)) = 1 |Ω| x∈Ω d d | =0 h λ (I(x) + J(x)) = - 1 |Ω| x∈Ω δ(I(x) -λ)J(x) . (8)
Then

d d =0 E(I + J) = - 1 |Ω| 1 0 (H I (λ) -H ref (λ)) x∈Ω δ(I(x) -λ)J(x) dλ = - 1 |Ω| x∈Ω 1 0 (H I (λ) -H ref (λ))δ(I(x) -λ)J(x) dλ = - 1 |Ω| x∈Ω (H I (I(x)) -H ref (I(x)))J(x) . (9)
That is

∇ I E(I) = - 1 |Ω| (H I (I(x)) -H ref (I(x))). ( 10
)
Remark 3.1: We may use a gradient descent algorithm to minimize the energy (5). Initializing with I 0 = I, for some positive evolution parameter step τ , the process is described by the equation

I k+1 = I k -τ ∇ I k E(I k ). (11)
Remark 3.2: If H 1 , H 2 are two given reference cumulative histograms, the energy

E 1,2 (I) := 1 2 1 0 (H I (λ) -H 1 (λ)) 2 dλ + 1 2 1 0 (H I (λ) -H 2 (λ)) 2 dλ. ( 12
)
expresses the distance of H I to H 1 and H 2 . Using [START_REF] Grundland | Color histogram specification by histogram warping[END_REF], the Euler-Lagrange equation ∇ I E 1,2 (I) = 0 can be written as

H I (I(x)) = H 1 (I(x)) + H 2 (I(x)) 2 . ( 13
)
As we observed in Section II, this is not a suitable choice for intermediate histogram equalization since it may generate new unwanted structures (level lines) in the image. Thus, this energy term will be constrained in order to keep the geometry of the original image. Before going into details about this constraining, let us extend the above computations to the vector case.

C. The L 2 distance between the cumulative histogram of a color image and a reference one and its first variation

Let us consider the case of vector valued images I : Ω → [0, 1] N . To simplify the presentation, let us study here the case N = 2, the case of color images with N = 3 will be considered in Appendix VIII. Thus, if

I = (I 1 , I 2 ) and λ = (λ 1 , λ 2 ) ∈ [0, 1] 2 , the cumulative histogram of I is defined by H I ( λ) = 1 |Ω| |{x : I 1 (x) ≤ λ 1 , I 2 (x) ≤ λ 2 }|. Let H ref ( λ)
be a reference cumulative histogram. We then define the transfer energy:

E( I) = 1 2 1 0 1 0 (H I ( λ) -H ref ( λ)) 2 d λ. ( 14
)
If H 1 , H 2 are defined by

H 1 (i 1 , i 2 ) ≡ i 2 0 H(i 1 , λ 2 )dλ 2 , H 2 (i 1 , i 2 ) ≡ i 1 0 H(λ 1 , i 2 )dλ 1 , (15)
then, as it will be proven in Appendix VIII, the first variations of E( I) with respect to I 1 , I 2 are

∇ I 1 E( I) = - 1 |Ω| H 1 I (I 1 (x), 1) -H 1 ref (I 1 (x), 1) + 1 |Ω| H 1 I (I 1 (x), I 2 (x)) -H 1 ref (I 1 (x), I 2 (x)) (16)
∇ I 2 E( I) = - 1 |Ω| H 2 I (1, I 2 (x)) -H 2 ref (1, I 2 (x)) + 1 |Ω| H 2 I (I 1 (x), I 2 (x)) -H 2 ref (I 1 (x), I 2 (x)) . (17)

D. Symmetrization of the cumulation of histogram

Let us mention that, by definition of cumulative histogram, the process presented above presents an important unwanted limitation that can be simply explained in the case N = 1.

Indeed, note that for any grey image

I : Ω → [0, 1], we have H I (1) = 1 |Ω| |{x : I(x) ≤ 1}| = 1.
As a consequence, when computing the gradient value of white pixels of color value 1, we will always find H I (1) -H ref (1) = 1 -1 = 0, so the white pixels can never change their intensity value. To remove this limitation, we need to consider H * , the histogram defined as

H * I (λ) = |{x : I(x) ≥ λ}|, λ ∈ [0, 1].
The energy (5) should then be completed with the term 2 dλ, so that the symmetrized energy will be

1 2 1 0 (H * I (λ) -H * ref (λ))
E(I) = 1 2 1 0 (H I (λ) -H ref (λ)) 2 + (H * I (λ) -H * ref (λ)) 2 dλ, (18)
that will allow the white pixels to move their value. Obviously, by symmetry, this new term will not affect the black pixels, as H * I (0) = 1 for any image I : Ω → [0, 1]. For the N -dimensional case, N > 1, we have

E( I) = 1 2 1 0 • • • 1 0 N times (H I ( λ) -H ref ( λ)) 2 + (H * I ( λ) -H * ref ( λ)) 2 d λ, (19)
It is clear that the gradient formulae previously written still hold for the symmetrized energy, modulo the introduction of a symmetric term, or terms (for the higher dimensional case), in H * .

IV. INTERMEDIATE HISTOGRAM EQUALIZATION OF A SET OF IMAGES

As reviewed in section II, histogram equalization is mainly addressed from the point of view of mass transfer [START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF], [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF], [START_REF] Delon | Midway image equalization[END_REF], where the unknown is the transfer function ϕ A. An energy term to approach the histogram of two images Suppose that we are given two color images U :

: [0, 1] N → [0, 1] N
Ω U → [0, 1] 3 and V : Ω V → [0, 1] 3 , U = (U 1 , U 2 , U 3 ), V = (V 1 , V 2 , V 3
), and we want to map them into two images with a common histogram as much as this is possible. We can then try to construct two color images u = (u 1 , u 2 , u 3 ) and v = (v 1 , v 2 , v 3 ) related to U , V , respectively, and defined on the spatial domains Ω U and Ω V , so that they minimize the histogram-based energy E H :

E H ( u, v) = 1 2 1 0 1 0 1 0 (H u ( λ) -H v ( λ)) 2 d λ + 1 2 1 0 1 0 1 0 (H * u ( λ) -H * v ( λ)) 2 d λ. ( 20
)
That is, u, v should have similar histograms and be relatively close to the original images U , V .

Note that, even if the final histograms of u and v are equal, we cannot guarantee that this is the true midway histogram of U and V (in the sense described in Section II). If we consider for instance two unimodal images U = λ 0 and V = λ 1 , all pixels of each image are initially equal and they will always share a common value all along the minimization process (since in this case, the gradient [START_REF] Grundland | Color histogram specification by histogram warping[END_REF] is the same for the whole image). Then, we could obtain any unimodal image u = v = s, s ∈ [0, 1], as a minimum of energy (20), while we would prefer finding the particular value s ≡ λ 0 +λ1 2 . This value can be obtained if we add a data attachment term to enforce that u, v are, respectively, close to U , V . Thus, we propose to complement the energy term (20) with data attachment terms constraining the color and the geometric information of the images u, v to be close to the one in U , V .

B. Attachment to data and to the image geometry

Contrary to the methods based on histogram transfer, as our variables are the images, we can directly add some color and geometrical restrictions on the image evolution. a) Constraining the colors: In order to enforce u and v to remain as close as possible to the original images U and V we define the following attachment to data energy term E D :

E D ( u, v) = α U 2 x∈Ω U U (x) -u(x) 2 + α V 2 x∈Ω V V (x) -v(x) 2 , (21)
where α U and α V are positive real parameters. With this new term, by setting α U = α V , we can constrain the final images u and v to have a similar distance to their original values U and V .

Let us go back to the unimodal toy example U = λ 0 and V = λ 1 and consider the energy

E HD = E H + E D , with α U = α V = > 0.
In this case both solutions u, v are unimodal, say u = λ 0 , v = λ 1 with λ 0 < λ 1 . Then we can write the energy E HD in terms of λ 0 , λ 1 and check that when > 0 is small enough (to constrain the histogram term E H to be preponderant in E HD ) the minimum of E HD is reached for the unimodal image u = v = λ 0 +λ 1 2 whose histogram corresponds to the midway one 1 .

In real applications, the energy E H is obviously never zero, so we do not reach the true midway histogram. Nevertheless, from our experiments, we can assert that the histogram and data energies (20) and ( 21) allow the histograms of images u and v to converge naturally to a histogram in a neighborhood of the midway histogram of images U and V .

b) Constraining the image geometry: We can constrain the shapes of u and v to be those of the given images U and V . To describe the shapes of U i , V i we use the normals to its level lines, that is, we use the vector fields θ( [START_REF] Ballester | A variational model for p+ xs image fusion[END_REF] (the quotient must be set to 0 when the denominator is 0) where ∇ denotes here a discrete gradient operator (see Section V-B). Then we say that the scalar image u i shares the same shapes as U i (in some sense, the same level lines) if θ(U i ) • θ(u i ) = 1, i.e. when θ(U i ) • ∇u i = |∇u i | (see [START_REF] Ballester | A variational model for p+ xs image fusion[END_REF] for more details).

U i ) = ∇U i |∇U i | , θ(V i ) = ∇V i |∇V i | [
In order to constrain the shapes of u and v to be those of U and V , respectively, we consider (together with the histogram and color terms) the following shape preserving energy

E S E S ( u, v) = β U 3 i=1 Ω U (|∇u i | -θ(U ) i • ∇u i ) + β V 3 i=1 Ω V (|∇v i | -θ(V ) i • ∇v i ) , ( 22
)
where β U and β V are positive parameters. Imposing the channels of two color images U and u to share the same shapes (or level lines) is not a strong constraint on the color distributions.

min u 3 i=1 x∈Ω U |∇U i (x) -∇u i (x)| + x∈Ω U | u(x) -ϕ( U (x))|. ( 23
)
We note that ϕ( U (x)) is known since the transfer function is previously computed. Different strategies for that can be found in [START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF], [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF]. For instance, in [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF], the following Monge's optimal transportation problem is solved:

min ϕ 1 0 1 0 1 0 ϕ( λ) -λ 2 h U ( λ)d λ, ( 24
)
where the possible transfer maps ϕ are restricted to be linear. The optimal transfer map minimizes the displacement cost of colors when mapping the histogram of U to h V .

C. A model for intermediate histogram equalization of a set of images

Combining the histogram energy (20) with the color and geometry preserving terms of Section IV-B, we finally get the following energy functional for equalizing the color of two images U and V :

E U , V ( u, v) = E H ( u, v) + E D ( u, v) + E S ( u, v). ( 25
)
The energy can be extended to deal with the equalization of more than two images. Let us consider U k , k = 1, . . . , m, a set of color images. We can then use the energy (25) and define the following problem

min u 1 ,..., um 1≤k<l≤m E U k , U l ( u k , u l ), (26)
in order to normalize the color of the set of images U k .

V. DESCRIPTION OF AN ALGORITHM TO MINIMIZE E U , V

In this Section we describe the algorithm we used to minimize (25).

A. A primal-dual algorithm

Since the shape preserving term (22) includes a total variation regularization, we minimize E through a primal-dual proximal point algorithm. Let us detail this process for the minimization of E with respect to u when v is fixed. Discarding the terms involving only v, we have

min u E H ( u, v) + α U 2 x∈Ω U U (x) -u(x) 2 + β U 3 i=1 Ω (|∇u i | -θ(U ) i • ∇u i ) = min u max σ∈S E H ( u, v) + α U 2 x∈Ω U U (x) -u(x) 2 + β U 3 i=1 Ω (σ i • ∇u i -θ(U ) i • ∇u i ) = min u max σ∈S E H ( u, v) + α U 2 x∈Ω U U (x) -u(x) 2 -β U 3 i=1 Ω div(σ i -θ(U ) i ) u i , (27)
where

S = { σ = (σ 1 , σ 2 , σ 3 ), with σ i : Ω U × Ω U → R 2 and |σ i | ≤ 1}.
Starting from initial values u 0 and σ 0 ∈ S and given two positive time steps τ and τ σ , the primal-dual proximal point algorithm consists of a gradient ascent method for the dual variable σ and a gradient descent for the variable u. The dual step is then

σ k+1 i = σ k i + τ σ β U ∇u k i . (28)
while the primal step is

u k+1 i = u k i -τ ∇ u E U , V ( u k , v k ) = u k i -τ ∇ u E H ( u k , v k ) + α U (u k i -U i ) -β U div(σ k i -θ(U ) i ) , (29)
where the gradient ∇ u k i E H ( u k , v k ) can be computed as in the Appendix. At the end of each step, the dual vector variable σ k+1 i is projected into the unitary ball S, while the variable

u k+1 i is projected into [0, 1].
Similar equations can be written for the variables v.

B. The discrete gradient and divergence

Let us first give the definition of the discrete gradient and divergence operators. Assume that the discrete spatial domain is Ω := {1, . . . , W } × {1, . . . , H}. A scalar image is thus a vector in X := R W ×H . If u ∈ X, the discrete gradient is a vector in X × X given by

∇u =   u + x u + y   , (30) where u
+ x (i, j) =    u(i + 1, j) -u(i, j) if i < W, 0 if i = W, (31) and u
+ y (i, j) =    u(i, j + 1) -u(i, j) if j < H, 0 if j = H. (32)
The discrete divergence operator is determined by the relation div σ, u

X = -σ, ∇u X×X for all u ∈ X, σ = (σ 1 , σ 2 ) ∈ X × X, where •, • X , •, • X×X denote the scalar products in X, X × X, respectively. Thus, div σ = (σ 1 ) - x + (σ 2 ) - y ,
where

(σ 1 ) - x (i, j) =          σ 1 (i, j) if i = 1, σ 1 (i, j) -σ 1 (i -1, j) if 1 < i < W, -σ 1 (i -1, j) if i = W, (33)
and

(σ 2 ) - y (i, j) =          σ 2 (i, j) if j = 1, σ 2 (i, j) -σ 2 (i, j -1) if 1 < j < H, -σ 2 (i, j -1) if j = H. (34)
Finally, let us underline that the histograms are discretized in bins. In practice, we used M bins for each channel, so that the dimension of the histograms is M 3 . The value of the histogram

H I for the color (λ 1 , λ 2 , λ 3 ) is thus H I ([λ 1 M ], [λ 2 M ], [λ 3 M ]),

A. Histogram transfer

We first apply our process with v = V being fixed, so that only the image u can change its values. In this case, we recover the same problem as the one considered in [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF]. As the code of [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF] is available on the web2 , we have compared this method with ours in terms of the distance between histograms. If h u and h v are the histograms of images u and v, respectively, both methods are compared by means of the quantity

1 0 1 0 1 0 (h u ( λ) -h v ( λ)) 2 dλ, (35)
computed for the images u obtained using both our method and the one in [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF].

In [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF], the authors show experiments on color grading between very different images. We think that this kind of experiments is not well adapted to compare different methods, as there is no ground truth available. As a consequence, we used a data set composed of pairs of images showing the same painting which are taken by unknown cameras and with different illuminations.

We considered paintings, as they involve strong color contrast, and are quite close to the examples of color grading shown in [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF]. This data set is thus favorable to the application of [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF]. The original and final images obtained by both methods, the one in [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF] and ours, on the paintings are shown in Figures 1 and2. As illustrated in table I, both approaches give similar errors in the sense of (35), the method of [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF] being slightly better in general. Both methods, nevertheless, give good results in terms of visual quality.

Reference image V Original image U Result u with [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF] Result u with our method Fig. 1. Comparison between our method and the one of [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF] for the painting of Géricault: The Raft of the Medusa.

B. Intermediate histogram equalization of a set of images

Let us consider U k , k = 1, . . . , m, a set of color images representing the same scene with different orientations or illuminations. We solve the problem (26) in order to normalize the color of the set of images U k . As already commented, we underline that, to our knowledge, there is no method in the literature that allows realizing such a process without defining a midway histogram beforehand. In [START_REF] Morovic | Accurate 3D image colour histogram transformation[END_REF], [START_REF] Delon | Fine comparison of images and other problems[END_REF], when m = 2, the problem has been considered from the point of view

Reference image V Original image U Result u with [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF] Result u with our method of Monge-Kantorovich mass transportation theory leading to a linear programming problem for the computation of the transport plan transferring both histograms. Transport plans permit to split the mass of a bin of one of the histograms and distribute it between several bins in the other one. In [START_REF] Pitié | The Linear Monge-Kantorovitch Colour Mapping for Example-Based Colour Transfer[END_REF], assuming that the histograms of two given color images can be approximated by multivariate Gaussian distributions, the Monge-Kantorovich formulation is restricted to find a linear map that approximates the transfer of histograms. The color grading method proposed in [START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF] is based on the computation of a transfer map and could be adapted to compute a midway histogram equalization (see [START_REF] Delon | Midway image equalization[END_REF]) in the case of two images. The transfer map is computed by iteratively equalizing all principal axis marginals computed for every possible rotation of the histogram, until convergence. Then the method is refined by a filtering process to reduce possible grain artifacts [START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF]. As mentioned in Section IV-B, this process is related to our geometry attachment term. Thus our method, although different in spirit, has common points with [START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF]. On the other hand, it is more adapted to the consideration of more than two images.

In Figures 3,4

VII. CONCLUSIONS AND PERSPECTIVES

We have proposed in this paper a variational model for intermediate color histogram equalization of two or more color images. Given a set of images, we transform them by minimizing an energy functional which is composed by three different terms: on one side we have a histogram transport term that tends to approach the cumulative histograms of the original images; on the other side we have two conservative terms that tend to maintain unaltered color and image geometry. The balance between these two opposite actions is vital for our purposes: the original images evolve in order to approach a common intermediate histogram that does not need to be specified in advance. Up to authors' knowledge, this is a novel property in the literature Let us compute the first variations of the energy ( 14) with respect to I 1 and I 2 . We observe that

U 1 U 2 U 3 u 1 u 2 u 3
H I ( λ) = 1 |Ω| x∈Ω h λ ( I(x)) . (36)
where

h λ (r 1 , r 2 ) = χ [0,λ 1 ] (r 1 )χ [0,λ 2 ] (r 2 ) λ 1 , λ 2 , r 1 , r 2 ≥ 0. (37)
Hence, if J = (J 1 , J 2 ) : Ω → R + × R + denotes a perturbation, we have (39)

d d =0 H I+ J (λ) = 1 |Ω| d d =0 x∈Ω h λ ( I(x) + J(x)) = 1 |Ω| x∈Ω d d =0 h λ ( I(x) + J(x)) = - 1 |Ω| x∈Ω [δ(I 1 (x) -λ 1 )h λ 2 (I 2 (x))J 1 (x) + δ(I 2 (x) -λ 2 )h λ 1 (I 1 (x))J 2 (x)] . (38) Then
That is,

∇ I 1 E( I) = - 1 |Ω| 1 I 2 (x)
[H I (I 1 (x), λ 2 ) -H ref (I 1 (x), λ 2 )] dλ 2 , (40)

∇ I 2 E( I) = - 1 |Ω| 1 I 1 (x)
[H I (λ 1 , I 2 (x)) -H ref (λ 1 , I 2 (x)] dλ 1 .

(41)

Then ( 16) and ( 17) follow.

B. The case N = 3

Let us consider the case N = 3. Let I = (I 1 , I 2 , I 3 ) be a color image defined on the domain

Let

H 1 (i 1 , i 2 , i 3 ) ≡ i 2 0 i 3 0 H(i 1 , λ 2 , λ 3 )dλ 2 dλ 3 , (43)
H 2 (i 1 , i 2 , i 3 ) ≡ (48)

  For color images, we have N = 3 and I k (x) is the intensity level of the pixel x ∈ Ω in the chromatic channel k ∈ {R, G, B}. The histogram of the image I will be denoted by the density function h

  be a given reference cumulative histogram. In order to impose the cumulative histogram of I to be close to H ref (λ) we propose to minimize the following energy:

  mapping a variable histogram to a reference one. Considering the problem of equalizing (at least) two different images with respect to their midway histogram, these methods require an a priori computation of the midway histogram. The purpose of this section is to show how can we evolve simultaneously different images so that their histograms get naturally as close as possible to an unspecified intermediate histogram.

Remark 4 . 1 :

 41 A related approach. In the case of histogram transfer by estimation of the transfer function ϕ : [0, 1] 3 → [0, 1] 3 , an analogous local shape preservation is sometimes applied as a post-processing. For instance, in[START_REF] Pitié | Automated colour grading using colour distribution transfer[END_REF], the authors tackle the problem of transferring the histogram h V of an image V to the histogram h U of image U . First, they compute the transfer function ϕ so that h ϕ• U h V and then look for an image u sharing the shapes of the original image U and whose color histogram is h ϕ• U by solving:

  where [•] denotes the integer part of its argument. VI. EXPERIMENTS In all our experiments, we used the same set of parameters. The histogram is discretized into M = 64 bins. Concerning the model parameters, we used α U = α V = 0.1 for the data term and β U = β V = 0.1 for the shape preserving term. The time steps for the primal-dual proximal point algorithm are fixed as τ = τ σ = 10 -4 .

Fig. 2 .

 2 Fig. 2. Comparison between our method and the one of [13] for our data set. First row: Dali, Tentation. Second row: Monet, Impression Rising Sun. Third row: Van Gogh: Cypress against a starry sky. Fourth row: Da Vinci, Joconde.

3 Fig. 3 .

 33 Fig. 3. Lighthouse sequence. First line: Original images. Second line: Final images.

Fig. 4 .

 4 Fig. 4. Chapel sequence. First line: Original images. Second line: Final images.

3 Fig. 5 .

 35 Fig. 5. Gros Horloge sequence. First line: Original images. Second line: Final images.

HHH I (λ 1 , λ 2 )H I (λ 1 , λ 2 )HH

 1212 I ( λ) -H ref ( λ) x∈Ω δ(I 1 (x) -λ 1 )h λ2 (I 2 (x))J 1 (x) + δ(I 2 (x) -λ 2 )h λ1 (I 1 (x))J 2 (x) d λ I ( λ) -H ref ( λ) δ(I 1 (x) -λ 1 )h λ2 (I 2 (x))J 1 (x) + δ(I 2 (x) -λ 2 )h λ1 (I 1 (x))J 2 (x) d λ -H ref (λ 1 , λ 2 ) δ(I 1 (x) -λ 1 ) dλ 1 h λ2 (I 2 (x)) dλ 2 J 1 (x) -H ref (λ 1 , λ 2 ) δ(I 2 (x) -λ 2 ) dλ 2 h λ1 (I 1 (x)) dλ 1 J 2 (x) I (I 1 (x), λ 2 ) -H ref (I 1 (x), λ 2 ) dλ 2 J 1 (x) I (λ 1 , I 2 (x)) -H ref (λ 1 , I 2 (x)) dλ 1 J 2 (x).

Ω

  and HI ( λ) = 1 |Ω| |{x ∈ Ω : I 1 (x) ≤ λ 1 , I 2 (x) ≤ λ 3 , I 3 (x) ≤ λ 3 }|, λ ∈ [0, 1] 3 .As above, let H ref ( λ) be a specified cumulative histogram. We consider the energy: ( λ) -H ref ( λ)) 2 d λ,

i 1 0 i 3 0H(λ 1 , i 2 , λ 3 )dλ 1 dλ 3 ,H 3 (i 1 , i 2 , i 3 ) ≡ i 1 0 i 2 0H(λ 1 1 I 2 (x) 1 I 3 1 I 1 I 1 I 1 I 1 (x) 1 I 3 2 I 2 I ( 1 , 2 I 1 I 1 (x) 1 I 2 3 I ( 1 , 3 I 3 I

 3123331212112131111113221211123133 , λ 2 , i 3 )dλ 1 dλ 2 . (45)With similar computations as in the case N = 2 we have:∇ I 1 E( I) = -1 |Ω| (x) [H I (I 1 (x), λ 2 , λ 3 ) -H ref (I 1 (x), λ 2 , λ 3 )] dλ 3 dλ 2 (I 1 (x), I 2 (x), 1) -H 1 ref (I 1 (x), I 2 (x)(I 1 (x), 1, I 3 (x)) -H 1 ref (I 1 (x), 1, I 3 (x)) (I 1 (x), I 2 (x), I 3 (x)) -H 1 ref (I 1 (x), I 2 (x), I 3 (x)) ,(46)∇ I 2 E( I) = -1 |Ω| (x) [H I (λ 1 , I 2 (x), λ 3 ) -H ref (λ 1 , I 2 (x), λ 3 )] dλ 3 dλ 1 (I 1 (x), I 2 (x), 1) -H 2 ref (I 1 (x), I 2 (x)I 2 (x), I 3 (x)) -H 2 ref (1, I 2 (x), I 3 (x)) (I 1 (x), I 2 (x), I 3 (x)) -H 2 ref (I 1 (x), I 2 (x), I 3 (x)) ,(47)∇ I 3 E( I) = -1 |Ω| (x) [H I (λ 1 , λ 2 , I 3 (x)) -H ref (λ 1 , λ 2 , I 3 (x))] dλ 2 dλ 1 = -1 |Ω| H 3 I (I 1 (x), 1, 1) -H 3 ref (I 1 (x), 1I 2 (x), I 3 (x)) -H 3 ref (1, I 2 (x), I 3 (x)) (I 1 (x), 1, I 3 (x)) -H 3 ref (I 1 (x),1, I 3 (x)) (I 1 (x), I 2 (x), I 3 (x)) -H 3 ref (I 1 (x), I 2 (x), I 3 (x)) .

This would not be the case by considering a L 1 attachment to data term ED( u, v) = αU ||U -u||1 + αV ||V -v||1. Indeed, the energy EH,D would have the same value for any unimodal image u = v = s, s ∈ [λ0, λ1].

http://www.mee.tcd.ie/∼sigmedia/Research/ColourGrading

ACKNOWLEDGMENTS

This work was partially funded by Mediapro through the Spanish project CENIT-2007-1012 i3media and by the Centro para el Desarrollo Tecnológico Industrial (CDTI), within the Ingenio 2010 initiative. V. Caselles and E. Provenzi acknowlege partial support by MICINN project, reference MTM2009-08171 and by GRC project, reference 2009 SGR 773, funded by the Generalitat de Catalunya. V. Caselles also acknowledges partial support by IP project "2020 3D Media: Spacial Sound and Vision", Financed by EC, and by "ICREA Acadèmia" prize for excellence in research funded by the Generalitat de Catalunya. E. Provenzi also acknowledges partial support by the Ramón y Cajal fellowship by Ministerio de Ciencia y Tecnología de