Recent covid19 pandemia has made data visualization appearing in everyone's everyday life. Besides, ubiquitous digital technology has facilitated the collect of multi-dimensional numerical data that are analyzed by specialists. Their need to explore and to explain these data to non-specialists is important. With categorical data, a lot of diagrams are constructed on a color-coded paradigm associating colors with data classes. Depending on the number of classes or the geometry of diagrams, the class-color assignment choice can become hard a task (! permutations for classes).

The goal of this research is to develop an algorithm aiming at assigning the best color, among a user given color palette, for each class of objects in the case of categorical data while optimizing the ability, for a viewer, to distinguish classes geometrical objects one from another. Using the geometry of the displayed object and an estimation of the class' visual separation ability are means to get a better class-color assignment.

The author presents a novel framework that permits optimizing contrast color of classes objects in the case of categorical visualization.

The method relies on a fitness function separation between palette color distances and the concept of importance factors expressing the need to get for a couple of objects classes a high color contrast. We construct an importance factor using the chosen kind of visualization and especially the data geometrical properties associated. Two matrices are expressed, a first one named importance matrix (independent of the chosen color map) and a second, the color distance matrix (independent of the data). As, in this research context, the color map is given by the user, once the energy function is expressed by the inner matrix product of the two matrices, a genetic optimization algorithm searches for the best permutation.

We show applications of the concept to several kinds of categorical visualizations: streamgraphs, line charts, polygonal maps, chord diagrams. For each visualization kind, we show resulting color assignments. Streamgraph diagram and chord diagram contrast driven color-group assignment has not been explored in literature so far.

Nomenclature

Symbols

Symbol Definition the number of groups in the categorical visualization the importance matrix ( , )

the element of importance matrix coding the importance for group and group the list of group names the name of group at index the colormap ( 1 , .., )

the colors of the colormap the DE2000 color distance matrix ( , ) the DE2000 color distance between colors and a permutation ( , ..., ) the matrix coding the permutation frame change ( , ..., ) the adequacy of permutation ( , ..., )

Streamgraph

Symbol Definition , neighborhood descriptor (∈ {0, 1}) between groups and for value , elementary importance factor between and groups for value ℎ height of layer for value

Polygonal Map

Symbol Definition the edges of the categories which are frontiers with another category point at index along the edges separated by an increment value between successive points a user value coding the distance between two points along the edges the number of points along the edges of category ( ) the distance traveled within the polygon from the point perpendicularly to the current polygon edge Recent covid19 pandemia has made data visualization appearing in everyone's everyday life. The ubiquitous digital technology has facilitated the collect of multi-dimensional numerical data that are analyzed by specialists. Their need to explore and to explain these data to non-specialists is important.

With categorical data, we construct a lot of diagrams on a color-coded paradigm associating colors with data classes. Depending on the number of classes or the geometry of diagrams, the color assignment choice can become hard a task. The goal of this research is to develop an algorithm aiming at choosing the best color, among a user given color map, for each class of objects in the case of categorical data while optimizing the ability, for a viewer, to distinguish classes geometrical objects one from another. Using the geometry of the displayed object and an estimation of the class' visual separation ability are means to get a better class-color assignment.

We can evaluate the distinguishability of two colors using a color distance which quantify how much a color differs from another color. From simple euclidian RGB distance to "Lab" color space expression, various distances have been proposed in the literature aiming to express the perception of color difference or similarity. The recent developments have come with validity for the whole color cube of colors and the color distance DE2000 [START_REF] Sharma | The CIEDE2000 color-difference formula : Implementation notes, supplementary test data, and mathematical observations[END_REF] proposed by the CIE (Commission internationale de l'éclairage) possesses almost all the mathematical properties of a distance, though being not exactly symmetrical.

Let us recall that, for a diagram showing classes and colors, color-class assignment consists in choosing a bijection from the class index set {1, ..., } to the color index set {1, ..., }. A permutation of size can model this and the number of permutations for a set of size is factorial (! ) which explodes with the increasing of .

The idea behind the presented framework is to decompose an expression of a good class-color assignment in a geometrical information on one part, and a color information on the other. The author assumes that a contrast driven function can be expressed for two objects, which represents, given the object geometries and their distance, size or interface/border/common edges, the need to set colors with a large color difference in order to distinguish the two objects. We denote this "need" factor the importance factor.

A second assumption comprises stating that we can express the distinguishability between two colored objects by the product of this importance coefficient and the distance associated with the two colors.

Research Context

This section presents the context where the need for color-class assignment happen.

The Need to Separate Layers

Several years ago (2018), when the author was developing a software to help music scientists, the need to have a visual separation between groups on categorical data visualizations occurred. Before, we had 1.2. Importance, Assignment Optimization and Restrictions on Space Research Dimensions 2 developed a first attempt to visualize the personal music library as a music archipelago metaphor [START_REF] Languenou | Music archipelago, a facet-like music library comparison tool[END_REF]. A survey data collection on music listening habits which produced multi-dimensional temporal data was available and gaining comprehension of the general shape of the data was, for the music scientists, mandatory. The chosen way was to let the user interact with data properties by filtering some values, followed by an evaluation of the filtered data shown in a two-fold visualization, in a fast interactive exploration.

StreamFacet

The research led to a software called "Streamfacet", [START_REF] Languenou | StreamByFacet", un nouvel outil interactif d'exploration de données temporelles par une navigation de type facettes et un affichage en streamgraph[END_REF] displayed on figure 1.2, based on an Elastic Facet paradigm developed by M. Stefaner et al. [START_REF] Stefaner | Elastic Lists for Facet Browsers[END_REF][START_REF] Stefaner | Elastic Lists for Facet Browsing and Resource Analysis in the Enterprise[END_REF] (see figure 1.1) and Streamgraph diagrams published by Havre et al. [START_REF] Havre | Themeriver: Visualizing Thematic Changes in Large Document Collections[END_REF] in 2002 and popularized by Lee Byron and Martin Wattenberg [START_REF] Byron | Stacked Graphs -Geometry & Aesthetics[END_REF] in 2008. A video of the application in use is visible on vimeo (commentary in French).

We composed Streamfacet of two parts, the top part where the encountered values are shown as labeled buttons displayed in columns corresponding to data dimensions. Elastic Facet relates the height of each button to the label number of occurrences in the data. By clicking a button, the associated value becomes a filtering value, and it changes all columns according to the new filtered data.

The bottom part displays a streamgraph for which the grouping dimension ( ) and the time dimension ( ) are selected within the elastic list top part. While exploring by filtering and displaying streamgraphs, the number of layers varies according to filters and could be high. Even in such cases, the user wants to be able to visually separate layers one from another, even if layers' comparison and diagram understanding is almost impossible. The class-color assignment has therefore to be automatic.

For categorical visualizations where colors do not convey other database information than category, and in order to avoid favoring specific groups, the color map must be neutral in term of brightness and saturation. A widely used solution to optimize layers' visual separation is to choose a color map with a large hue interval as in a rainbow map, even if this guaranties legibility only for a rather small number of layers. A great thickness variation between displayed layers may happen, leading to difficulty in visually separate layers. Another difficulty lies because a layer may have many neighboring layers. In addition, using a rainbow color map usually leads to lesser aesthetical diagrams. Some sentences extracted from the 2008 article from Byron & Wattenberg [START_REF] Byron | Stacked Graphs -Geometry & Aesthetics[END_REF] show that the distinguishability aspect was noticed from the very beginning: "A third issue is the ability of a reader to distinguish effectively the many layers of a stacked graph (E)" "There must be enough local contrast between layers in order to differentiate each layer, a particularly important issue as raised in design issue (E)".

An automatic Color-class Assignment

The streamgraph display context is not a case where a data scientist or a graphic designer searches for a publication single streamgraph appearance in order to convey information and therefore has a lot of time to explore manually many colors assignment to streamgraph layers. While exploring data through the use of Streamfacet, the user filters data, generates streamgraphs according to dimensions. Consequently, there is a need for an automatic colors-layer assignment. In 2018, the author devised an optimization process (not published then) in order to assign layers to colors in streamgraph visualization. It appears afterward that the concept could be extended to other categorical visualizations.

Importance, Assignment Optimization and Restrictions on Space Research Dimensions

Searching all together the colors to be used in the diagram and the assignment of colors to the depicted groups leads to a complex optimization problem with constraints. For example, if is the number of groups, the number of unknown variables will be 3 × , corresponding to RGB color values. To prevent some groups from focusing viewer attention, the palette colors must be "similar" in term of brightness and saturation while being sufficiently different, adding therefore additional constraints. One way to reduce the problem complexity is to consider the color map as a user given data, limiting then the search for group-color assignment. In addition, the author believes that data scientists have preferences about color map. As DE2000 color distance is available in a lot of package, transforming diagrams geometrical data into importance factors was to be devised together with an evaluation of a good color assignment before choosing an assignment optimization process.

Problematic

This research is not about:

• an attempt to choose the color palette for a given visualization. We let this part to the user; • an attempt to help the user choose a color assignment which satisfies absolutely the whole set of data visualization constraints;

• a user test analysis to compare the presented method to other visualization color assignments.

This research is about:

• a novel automatic color-class assignment method driven by class color contrast, based on class object geometrical properties and shown data;

• a novel class-color assignment framework in which a lot of categorical visualizations could be integrated;

• the presentation of the framework diagram applications to:

-streamgraph (new); -polygonal map; -chord diagram (new); -line chart;
The goal is two-folded: first, try to adjust the color contrast in order to distinguish categorical classes with a lot of classes ( > 15) and second, give the ability to reduce the color palette hue interval for small number of classes in order to get a more aesthetic figure.

Report Organization

After a short state of the art related to class-color assignment in categorical visualizations in Chapter 2 (page 6), we expose the proposed framework and the corresponding method principles in Chapter 3 (page 10).

Then, the concept of importance matrix, core of our optimization process, is detailed in Chapter 4 (page 13).

After what, in Chapter 5 (page 15), we explain the color-class optimization process and its relation to the QAP problem.

Applications to several categorical kinds of diagram are then listed, with their dedicated importance matrix calculations and results, in Chapter 6 (page 18).

• Streamgraphs in section 6.2 page 19; • Polygonal maps in section 6.3 page 22; • Chord diagrams in section 6.4 page 28;

• Scatterplots in section 6.6 page 38;

• Simple neighbor diagrams (single bar chart and pie chart) in section 6.7 page 41; Then, we detail the extension of the method to class-color assignment with multiple visualizations sharing categories, in the section 6.8 page 42.

Finally, the Chapter 7 page 48 about method implementation follows before a conclusion in Chapter 8 page 50.

State of the Art

This chapter presents a state of the art globally limited to published researches about color-class assignment in categorical diagrams, and some related articles.

Colormaps Generation

Even if the presented method is only about class-color assignment using a user chosen color map with categorical visualization, we give a rapid review of color usage and color map related articles here-after.

In image understanding, Bertin [START_REF] Bertin | Semiology of Graphics[END_REF] wrote that color is associative, selective and ordered. Many works in psychology explore color human response [START_REF] Quinlan | Visual search for targets defined by combinations of color, shape, and size: An examination of the task constraints on feature and conjunction searches[END_REF], especially that color precedes size, shape and orientation. From empirical studies in visualization [START_REF] Ware | Color Sequences for Univariate Maps: Theory, Experiments and Principles[END_REF] to crowd sourced color aesthetics experiments [OAH11; OAH14] and distance perception between visual objects [Bor+11; DBH14], human reception to color have been explored. Some papers provide guidance on color map design [War12; Tuf90; Bre99; BT07; ZHM09; BRT95]) and some methods emphasis on optimizing for color harmony and aesthetics [START_REF] Wang | Color design for illustrative visualization[END_REF] while others propose an interactive tool [START_REF] Meier | Interactive color palette tools[END_REF] to mix, organize colors and explore color combinations. Language and semantics related to colors have also been explored using automated internet searches for term-color association [Lin+13; SS16; HS12b]. Researchers [START_REF] Schloss | Aesthetic response to color combinations: Preference, harmony, and similarity[END_REF] have published works on association of colors like color pair preference in term of aesthetic .

Many online tools like ColorBrewer [START_REF] Harrower | ColorBrewer.org: An Online Tool for Selecting Colour Schemes for Maps[END_REF] help to design palettes for specific tasks. Zhou and Hansen have published a survey on color map design in 2016 [START_REF] Zhou | A Survey of Colormaps in Visualization[END_REF].

Color in Visualization

Tasks that could be performed about visualization have been systematically studied by Adrienko and Adrienko [AA06; BM13] like localization, identification, or else comparison. These tasks have seen usage in color mapping work by Tominski et al. [START_REF] Tominski | Task-Driven Color Coding[END_REF].

Mittelstadt et al. [START_REF] Mittelstadt | ColorCAT: Guided Design of Colormaps for Combined Analysis Tasks[END_REF] describe these three tasks:

• Localization is performed when the user wants to see where specific objects are located within the data. • Identification is performed when the user browses or explores the data and reads values from color encoded objects on the screen.

• Comparison task is used to compare multiple visual encoded objects, and to perceive and understand the relative and absolute differences.

Given a dataset and a kind of visualization diagram, there are a lot of research about defining rules in order to determine which color maps should be used ([BRT95; BH11; BT07; Bre94a; Bre94b; HB03; Mit+15; Rhe00; RT99; RT96; Saj+12].

Bergman et al. [START_REF] Bergman | A rule-based tool for assisting colormap selection[END_REF] developed as well a rule-based approach that relies on the varying sensitivity of the human visual system for spatial frequencies as a basic rule for creating color palettes.

Sanyal et al. [START_REF] Sanyal | Noodles: A Tool for Visualization of Numerical Weather Model Ensemble Uncertainty[END_REF] explore the visualization of ensemble uncertainty. They apply a discrete color map by combining three sequential color maps from the "ColorBrewer" tool for rendering spaghetti plots.

Hummel et al. [START_REF] Hummel | Comparative Visual Analysis of Lagrangian Transport in CFD Ensembles[END_REF] design a 2D interactive color map to separate the joint variance parameter space into similar, dissimilar and uncertain regions to visualize and explore an ensemble of 2D convection flows. The color map enables the user to visualize specific values of interest, localization, and identification at the same time.

In practice, an appropriate color mapping scheme is often obtained by a two-step procedure:

1. selecting a good palette using a categorical color palette tool (e.g., ColorBrewer [START_REF] Harrower | ColorBrewer.org: An Online Tool for Selecting Colour Schemes for Maps[END_REF] or Colorgorical [GLS17]) 2. assigning the selected colors to the classes through a trial-and-error process.

Aupetit et al. [START_REF] Aupetit | SepMe: 2002 New visual separation measures[END_REF] published in 2016 a state of the art on visual class separation measures, applied mostly to scatterplots.

Sedlmair et al. [START_REF] Sedlmair | A Taxonomy of Visual Cluster Separation Factors[END_REF] developed a taxonomy of factors that influences the human perception of visual class separation, where most factors are derived from the positions of the data points.

Researches are also concerned with factors like class visibility [START_REF] Lee | Perceptually Driven Visibility Optimization for Categorical Data Visualization[END_REF], and perceptual distance [START_REF] Fang | Categorical Colormap Optimization with Visualization Case Studies[END_REF].

Fang et al. [START_REF] Fang | Categorical Colormap Optimization with Visualization Case Studies[END_REF] proposed to maximize the perceptual distance among a set of given colors while incorporating a set of user-defined constraints. They further compared three optimization algorithms solving this problem and found that a Genetic Algorithm (GA) can ease the effect of sticking to the local maximum.

Hurter et al. [START_REF] Hurter | An automatic generation of schematic maps to display flight routes for air traffic controllers: structure and color optimization[END_REF] proposed an optimization method for assigning colors to lines of a metro map that assigns close routes with the most distinguishable colors. Kim et al. [START_REF] Kim | Perceptually-based Color Assignment[END_REF] proposed a perception-driven color assignment method for assigning colors to un-ordered image segments, where color aesthetics and contrast are incorporated.

Wang et al. [START_REF] Wang | Optimizing Color Assignment for Perception of Class Separability in Multiclass Scatterplots[END_REF] developed an approach in class-color assignment to optimize visual class separability in scatterplot diagrams. Based on forms, distinctness and contrast with background, it considers user color map and optimizes through genetic algorithm. They provide a parameter study with numerical measure.

Analysis

Getting the perfect color samples for a diagram and a set of tasks has been widely explored. Many works in the psychology domain explore color human response [START_REF] Quinlan | Visual search for targets defined by combinations of color, shape, and size: An examination of the task constraints on feature and conjunction searches[END_REF], and state that color precedes size, shape and orientation. The color map has to be chosen in relation to the visualization tasks, which have been systematically studied [START_REF] Andrienko | Exploratory analysis of spatial and temporal data: a systematic approach[END_REF][START_REF] Brehmer | A Multi-Level Typology of Abstract Visualization Tasks[END_REF]. Some categorical visualization researches use data graphical properties to optimize color assignment in which some are pixel-based [LSS13; Zen+19] and others are segmented-based or else mark-based [START_REF] Fang | Categorical Colormap Optimization with Visualization Case Studies[END_REF][START_REF] Hurter | An automatic generation of schematic maps to display flight routes for air traffic controllers: structure and color optimization[END_REF][START_REF] Lu | Palettailor: Discriminable Colorization for Categorical Data[END_REF][START_REF] Kim | Perceptually-based Color Assignment[END_REF][START_REF] Wang | Optimizing Color Assignment for Perception of Class Separability in Multiclass Scatterplots[END_REF]. In order to optimize color assignment, researchers estimated various factors like aesthetics, harmony, class visibility, legibility, color distance, semantics, density, overlapping or fidelity to user preferences. Factors are summed using weights to get an energy formula or a fitness function. Among the encountered optimization methods, authors take advantage of simulated annealing, genetic algorithm, stochastic or gradient-based optimization.

We can find another partition among these works. Some are optimizing for both color map and color assignment [Fan+16; Hur+10; Zen+19] and others are based on a user set color map [Lu+21; Wan+18]. Wang et al. [START_REF] Wang | Optimizing Color Assignment for Perception of Class Separability in Multiclass Scatterplots[END_REF] present a general view of existing techniques and introduced their approach using point distinctness, non-separability, and genetic algorithm to optimize scatterplots diagrams. In 2021 [START_REF] Lu | Palettailor: Discriminable Colorization for Categorical Data[END_REF], the algorithm was extended to line and bar charts. Another paper [START_REF] Hurter | An automatic generation of schematic maps to display flight routes for air traffic controllers: structure and color optimization[END_REF] close to our approach is about air-traffic and metro map diagrams optimization. Their method, besides creating a color map, and changing the diagram object's location, computes distances between lines in order to optimize color differences through a result quality estimation. Lee et al [START_REF] Lee | Perceptually Driven Visibility Optimization for Categorical Data Visualization[END_REF] introduced the concept of class visibility and a color optimization algorithm based on their class visibility metric. Via color saturation, their pixel-based algorithm tries to increase the saturation difference for small regions. The class visibility factor is performed through integrating of point saliency, which measures how much a particular point color differs from its surrounding color.

Related Papers

This subsection presents some related papers and corresponding quick summaries. Papers using pixel-based optimization are not listed.

• Segmented Images Colorization Using Harmony Catherine Sauvaget, Stephane Manuel, Jean-Noel Vittaut, Jordane Suarez, and VincentBoyer [START_REF] Sauvaget | Segmented Images Colorization Using Harmony[END_REF].

Computer aided colorization process for artists. Uses a harmony factor based on region and color proportion. Based on user interactions. Dynamic programming. Uses Itten's proportion contrast.

• An automatic generation of metro-like maps to display flight routes for air traffic controllers: structure and color optimization Christophe Hurter, Mathieu Serrurier, Roland Alonso, Gilles Tabart and Jean-Luc Vinot [START_REF] Hurter | An automatic generation of schematic maps to display flight routes for air traffic controllers: structure and color optimization[END_REF] The paper presents metro lines and air route placement optimization and class-color assignment.

The algorithm tries to assign to close routes the most distinguishable colors. Uses DE2000. They discretize lines into points. They proposed a specific distance to evaluate the proximity of two lines. A quality factor measures the assignment between colors and lines:

= , , < Δ( , ) × 2 × (1 - 1 1 + -( , )
They have coded the optimization process using simulated annealing. It is to be noted that the used formula could be imported in our importance matrix. • Perceptually Driven Visibility Optimization for Categorical Data Visualization Sungkil Lee, Mike Sipsand and Hans-Peter Seidel, [START_REF] Lee | Perceptually Driven Visibility Optimization for Categorical Data Visualization[END_REF].

The paper introduces the concept of class visibility and a color optimization algorithm based on a class visibility metric. Their optimization process tries to increase the contrast for small regions and to reduce it for larger regions via the saturation component (where our optimization process uses color contrast). Point saliency measures how much a particular point has a color different from its surrounding. The applied color distance is the CIE1976. Class visibility is obtained by integrating over a region which corresponds to the eye fovea. The size of this region can be parametrised and the estimation is based on pixels (where our method is based on object geometry). Color discrimination is calculated by a repulsive force using color distance.

• Perceptually-based Color Assignment Kim Hye-Rin, Yoo Min-Joon, Henry Kang and Lee In-Kwon [START_REF] Kim | Perceptually-based Color Assignment[END_REF] The paper presents a novel method for automatic color assignment based on theories of color perception. Based on color relationships, as well as the spatial configuration of input segments, the optimization focuses on harmony.

Three factors are considered: harmony, luminance contrast and respect of additional constraints.

• Categorical Colormap Optimization with Visualization Case Studies Hui Fang, Simon Walton, E. Delahaye, J. Harris, D.A Storchak and Min Chen, [START_REF] Fang | Categorical Colormap Optimization with Visualization Case Studies[END_REF] The paper proposes an algorithmic approach for maximizing the perceptual distances among a set of given colors, avoiding local maximum in the optimization process and losing of the original semantic association. The method applies iterative transformations on a predefined colormap. In addition, they can set user constraints, like providing a constant color for a class, setting a color property fixed range or else choosing an adaptive range that could be used for each iteration. They tested three optimization algorithms, Nelder-Mead simplex, simulated annealing and genetic algorithm. Two case studies are presented, London Tube Map, and scatterplots.

• Optimizing Color Assignment for Perception of Class Separability in Multiclass Scatterplots

Yunhai Wang, Xin Chen, Tong Ge, Chen Bao, Michael Sedlmair, Chi-Wing Fu, Oliver Deussen and Baoquan Chen. [START_REF] Wang | Optimizing Color Assignment for Perception of Class Separability in Multiclass Scatterplots[END_REF] The paper presents an approach in class-color assignment to optimize visual class separability in scatterplots. Based on forms, distinctness, contrast with background, the method considers a user color map and optimization is performed through a genetic algorithm. They provide results of a parameter study with numerical measure.

• Modeling Color Difference for Visualization Design. Danielle Albers Szafir, [START_REF] Albers | Modeling Color Difference for Visualization Design[END_REF] The paper presents crowdsourced studies measuring color difference perceptions for three common mark types: points, bars, and lines, aiming at providing quantitative metrics to help people use color more effectively in visualizations. They present four mark categories: diagonally symmetric marks, elongated marks, asymmetric marks, and area marks. The method emphasis on separated visual angle and uses a CIELAB Euclidian metric. The authors found that perceptible color differences for lines vary inversely with the thickness in case of line graph visualization.

• Palettailor: Discriminable Colorization for Categorical Data Kecheng Lu, Mi Feng, Xin Chen, Michael Sedlmair, Oliver Deussen, Dani Lischinski, Zhanglin Cheng and Yunhai Wang [START_REF] Lu | Palettailor: Discriminable Colorization for Categorical Data[END_REF] An effective approach for color assignment is presented, that is based on a set of given colors. The method optimizes the perception of scatterplots while considering spatial relationships, point density, degree of overlap between point clusters, as well as background color. It is an interactive color assignment system which incorporates top K suggestions, user-defined color subsets, and classes of interest for the optimization. The system focuses on point distinctness (using DE2000) and contrast with the background.

The paper presents an integrated approach for creating and assigning color palettes to different visualizations, such as multi-class scatterplots, line, and bar charts, with an emphasis on better visual discrimination of classes. The algorithm customized optimization is based on simulated annealing to maximize the combination of three designed color scoring functions:

point distinctness: same formula as in "Optimizing color assignment for perception of class separability in multiclass scatterplots" [Wan+18]

( ) = 1 |Ω | ∈ Δ ( , ) ( ( , ))
name difference: same expression as in "Colorgical" paper [START_REF] Gramazio | Colorgorical: Creating discriminable and preferable color palettes for information visualization[END_REF], based on minimal Hellinger distance color discrimination: based on DE2000 color distance, each two colors should have a minimal DE2000 distance of 10. The method considers the background color. Formula calculates the minimum of DE2000 distance of all couples of the color map.

Point contrast with background:

( ) = 1 |Ω | ∈ Δ ( , ) ( ))
They conducted a controlled user study for scatterplots and line charts. The method unifies palette creation and color assignment into a single procedure, which may handle colors semantic.

Contribution

Besides the fact that in our application, we consider adjacencies and sizes, factors like point saliency [START_REF] Lee | Perceptually Driven Visibility Optimization for Categorical Data Visualization[END_REF] and point distinctness [START_REF] Lu | Palettailor: Discriminable Colorization for Categorical Data[END_REF], applied to scatterplots, bar charts and line charts distances, could, after re-arranging formulas, result in an importance matrix expressed to be integrated in our framework. Hurter et al. [START_REF] Hurter | An automatic generation of schematic maps to display flight routes for air traffic controllers: structure and color optimization[END_REF] proposed an algorithm which optimize objects placement and class-color assignment in which the evaluation of inter-lines distance could also, but only for color-class assignment (our framework does not handle objects location modifications), be transformed to fill an importance matrix.

The author's contribution is two-folded:

• providing a general class-color assignment framework (with a user given color map) based on a concept of importance matrix which codes the need to associate color contrast to class couples; • showing applications of the concept to several visualization types: streamgraph, polygonal map, chord diagram and line charts. Some of them (streamgraphs, chord diagrams) being never explored in existing literature.

Method Principles

This chapter explains the principles of the energy expression necessary in our optimization process to get a class-color assignment optimization. Let us remind that our importance concept relies on an energy function separated in two parts, a color part, independent of the data and a geometrical one, depending on the visualization type and the data.

Let us consider a categorical visualization displaying categories/groups/classes = { 1 , ..., }.

Visualization specialists have color map preferences which leads the author to choose an approach allowing the user to select a color map, = { 1 , ..., } leaving the optimization process trying to compute the best assignment between object classes and color samples to maximize contrast while preserving distinguishability.

The expression of a fitness function (or energy), which separates color distance values (CIE DE2000 [START_REF] Sharma | The CIEDE2000 color-difference formula : Implementation notes, supplementary test data, and mathematical observations[END_REF]) from an evaluation of the visualization type data-based need to get a color contrast, gives the flexibility to adapt this "need" factor calculation to multiple visualization diagrams. In the following, we denote this evaluation factor as "importance factor".

The optimization fitness function for a given color-class association (i.e. a permutation) is based on two symmetrical matrices:

• the color matrix, made of × elements, that contains ( , ) the color distance between colormap samples , ;

• which we call importance matrix, also made of × elements, that codes ( , ) the need to assign a high color contrast between classes and .

Once the user has chosen the colormap, the color matrix is constant, and for a given visualization of some given data, the importance matrix is constant as well. We then express the fitness function using the two matrices and and a given permutation .

Energy Evaluation

If the adequacy ( → , → ) of a single assignment of two color samples , to two classes , is given by the product of the inter-color distance ( , ) and the classes couple importance value ( , ), the overall adequacy for a permutation represented by ( 1 , .., ) can be expressed by the sum of the individual products, where the color distance is taken from ( ) to handle the color permutation:

( 1 , .., ) = =1 =1 ( ( , ). ( , )) (3.1)
Using matrix notation, we express the fitness function ( ), for a given class-color association , by a simple matrix inner product (denoted < , > ) of the two matrices where the color matrix is permuted using , the square matrix coding the permutation mapping.

( ) =< . . , > (3.2)
also called Frobenius product

Color Distance Matrix

A few decades ago, the commission internationale à l'éclairage (CIE) elaborated color distance formulas (metrics) to quantify color difference human perception. Since then, the CIE have devised various distances with constant improvements (CIE74, CIE94, etc.). The formulas give, for two "Lab" coded colors, a factor in evaluating the subjective feeling of human perceived difference among colors. We use, for the color distance matrix , the most recent color distance DE2000 (or CIEDE2000) formula provided by the CIE . Using the colormap provided by the user, we fill each element ( , ) of the color distance matrix (which is symmetrical, even if the DE2000 formula is not perfectly symmetrical) with DE2000 distance between color samples and . We show a representation of a color distance matrix on figure 3.1.

#440154FF #46337EFF #365C8DFF #277F8EFF #1FA187FF #4AC16DFF #9FDA3AFF #FDE725FF #440154FF #46337EFF #365C8DFF #277F8EFF #1FA187FF #4AC16DFF #9FDA3AFF #FDE725FF

Importance Matrix

The importance matrix , coding an evaluation of the needed color contrast between two classes, depends on the kind of visualization diagram. The calculations involve graphical object's size, neighborhood, frontier, distance between objects and therefore depend on shown data. We display a representation of an importance matrix on figure 3.2. We propose several specialized importance matrix evaluation formulas in chapter 6 on page 18 naming streamgraphs, line-charts, chord diagrams and polygonal maps.

The next chapter (chapter 4) introduces the concept and the properties which have to be integrated in the importance factor.

Energy Estimation Complexity

Thanks to the formulation in two parts (color, geometry) of equation 3.2, the complexity of the energy evaluation is rather low. As the two matrices are symmetrical and the elements for which indexes = are null, the complexity of the energy function evaluation, if is the number of classes, is then reduced to:

• accesses to the color distance matrix elements corresponding to the current permutation redirection, • ( -1)/2 multiplications while considering the product of the color distance times the importance factor (but only for nearly half of the symmetrical matrix),

• ( ( -1)/2) -1 additions in order to sum the in-between classes' energy contributions.

Importance Matrix Computation

The importance factor, as we defined it, is:

• independent of the colormap • designed for categorical diagrams • dependent on the graphical properties of the chosen diagram • dependent on the represented data In this chapter, we discuss the diagram geometrical properties which have to be handled in the importance factor and we propose diagram specialized importance factor formulas, later in in chapter 6 page 18.

Visual Properties and Color Separation

Our importance factor is designed to increase the visual discriminability of the classes composing the categorical diagram. Identification capability is let to the user colormap choice, or made possible by labeling the graphical objects. The visual solid angle should be used to express the ability of the viewer to separate one object from another, but for the moment, we calculate the importance factors through object size ratio, therefore independently of the future context of viewing (viewing distance and figure size).

Many graphical objects may compose the class, and they have to be incorporated into the calculus. The eye ability to visually "follow" a continuous graphical object (a line, a layer, a thick arrow, etc.) fosters the visual class separability. The layers of a streamgraph can be either continuous along the time interval, or appearing only on a part of diagram, or else be reduced to a null thickness at a given time and reappearing later.

The object visual separation is critical for adjacent objects to avoid spreading (the visual grouping of close objects caused by too much similar colors). In consequence, identifying frontier along adjacent objects is an important aspect.

But we have to reduce the need to assign to two classes two colors, which generate a high color contrast to a single scalar, i.e. an element of the importance matrix.

Elementary Importances: Size Matters

Visualizations diagrams are usually composed of several marks (scatterplots, bar-charts) or composed of curves or polygons (stacked-graphs, streamgraphs, polygon maps, chord diagrams). For example, in scatterplots diagram, many discs may represent a class, but in streamgraph visualization, a class' layer may be a single object. In this later case, we decompose the layer into smaller parts to evaluate local discriminability on parts of the class's object.

Let us denote these local evaluations, elementary importance factors (or in a shorter way: elementary importances).

In case of adjacent class objects visualization, besides the importance of the width and area of the colored region, and when objects discrimination is needed, Newhall (1955) [START_REF] Sidney | Width and area thresholds of discrimination of two colors[END_REF] noticed that the length of the frontier does not affect the discriminability. It seems that the perpendicular distance from the interface frontier to the other side of the region (a perpendicular thickness) represents a better criterion. The thinner the region, the higher the risk of spreading (region visual aggregation) when using similar colors. To the knowledge of the author, there are no published formula, in term of color distance and mutual thickness (or visual angle) that evaluate this risk. Concerning scatterplots, elementary importances can involve point density, discs diameter, distances separating discs from one class to discs belonging to another class.

Two kinds of simple empirical tests performed by the author, involving two rectangles filled using two close colors, where:

1. the frontier length is varying (see figure 4.1) 2. the rectangles heights are varying (see figure 4.2) confirm that the discriminality is affected by height and not affected by the frontier length. It is visible on an electronic version of this report when zooming while being probably too small on a printed version. The object's visual angle is the main property to be considered, but usually there is no information on the final display size nor knowledge on the distance between the screen (or paper) to the viewer's eye. Some published researches explore discriminability in visualization. Healey and Sawant published a paper [START_REF] Christopher | On the Limits of Resolution and Visual Angle in Visualization[END_REF] about the limits of pixel-based visualizations and visual angles. Maureen Stone explored the spreading effect and distinctness with "tableau" diagrams regarding size [START_REF] Stone | In Color Perception, Size Matters". Undetermined[END_REF]. The concept of Just Noticeable Difference (JND) [START_REF] Sharma | The CIEDE2000 color-difference formula : Implementation notes, supplementary test data, and mathematical observations[END_REF] has been expressed in order to explore colors which are subjectively considered as the same. None of their results apply to our cases.

Compiling Elementary Importances

The case of adjacent objects, as a frontier involves two regions and because the region thickness may vary along the frontier, implies a need to compile or synthesize the elementary importance factors into a single factor. But elementary importance synthesis formulas may depends on diagram type.

A Matrix to Store Importances

The importance matrix as we define it:

• is symmetrical • possesses null diagonal values • could be reduced to a triangular matrix Depending on the diagram kind, we may associate a null importance value to a classes couple that does not share a frontier. This shortcut is, for example, used in our streamgraph importance calculus.

Diagram Dependent Formulas

Let us recall that the importance matrix codes, independently of the colors, the need for visual separability of object classes using their geometrical properties, i.e. shape, neighborhood, area or else distance. In chapter 6, we list considered visual properties and dedicated importance factor formulas for steamgraphs, polygonal maps, chord diagrams and line graphs.

Color-Group Assignment Optimization

We defined, in previous chapters, the energy (or fitness) expression using an importance matrix and a color distance matrix. This chapter details the energy optimization process that permits finding (or trying to find) the best colors permutation, which gives the highest energy level.

Permutation Optimization

Various optimization algorithms for colors permutation in the case of categorical visualization have been tested in the literature. Fang et al. [START_REF] Fang | Categorical Colormap Optimization with Visualization Case Studies[END_REF] experimented Nelder-Mead simplex, simulated annealing and genetic algorithm; they found that genetic algorithm (GA) can alleviate the issue of sticking to the local maxima.

The QAP Optimization

During the author's search for published existing methods in permutation optimization, it appears to the author that the splitting in two matrices proposed in this report for class-color assignment problem has been published in economics field by Koopmans and Beckmann in 1957 [START_REF] Beckman | Assignment problems and the location of economic activities[END_REF]. Known as the Quadratic Assignment Problem (QAP), it aims at achieving an economic objective of assigning facilities to locations in order to minimize the overall cost. The problem is known as an NP-Complete problem, which can apply to many other optimization problems (backboards, inter-plant transportation, etc.). In 1998, Burkard et al. [START_REF] Burkard | The quadratic assignment problem[END_REF] published a QAP state of the art.

The neos-guide.org formulates the QAP as the following.

Consider the set of numbers = 1, 2, .., and the group of bijections between and itself, defined as = { : → }. Let be an × matrix where represents the required flow between facilities and . is an × matrix where is the distance between facilities and . We can estimate elementary costs by the product of the distance and the flow between two locations. The goal is then to minimize the overall cost.

A matrix can express a permutation as in a reference frame change [START_REF] Burkard | The quadratic assignment problem[END_REF]. Each member ∈ represents a particular arrangement of the elements so that ( ) , gives the distance between facilities and , when the facilities are permuted according to . Therefore, individual cost function for transportation between facilities and is given by , ( ) , . The sum of each and gives the overall cost for a permutation . Using previous notations, we get the total cost of assigning facilities to locations according to by the matrix inner product:

, = =1 =1 , ( ) , (5.1)
Even if the QAP energy expression relies on a minimization process, where our class-color assignment formulation expects to maximize the overall color contrast, the two problems are similar. The facilities location distance correspond to the chosen colormap DE2000 color inter-distance and the flow between https://neos-guide.org/content/quadratic-assignment-problem facilities matches the color contrast importance factor. We can express our class-color assignment problem as a QAP, by inverting the non-null elements of the color distance matrix. So far, we have not tested QAP corresponding implementation for class-color assignment.

Algorithms

The ratio between satisfying permutations or quite satisfying permutations and the total number of permutations depends strongly on the data and on the diagram type target. Sometimes the number of pleasing solutions is high, but for some data and diagram, it can appear that there is not a single satisfying permutation to the problem. For example, it could be easy to construct data for a streamgraph diagram where all layers are neighboring one another with very thin layers. Such data would have no satisfying permutation if the number of layers is high.

But usually, solving this type of problems using genetic algorithm seems to provide the best properties: fast enough, flexible, providing various solutions and being able to be executed on distributed processors.

In the presented framework, we implemented the optimization using genetic algorithm, but ideally, we should test and compare other optimization algorithms.

Genetic Optimization

In order to get an assignment in a reasonable amount of time, we may use heuristic approaches. In the literature, various methods, simulated annealing, genetic, non-linear gradient, greedy, has been experimented, but when the number of quite satisfying solutions is high enough, genetic approaches provides an advantage as various solutions can be obtained when conducting several optimization processes among which the user may choose.

Genetic optimization (GA) algorithms are inspired by biology, and are based on a representation of the problem's research space using chromosomes. At the beginning, elements (individuals) being generated by random values, compose the population. To calculate the next generation, we evaluate the quality of the individuals using a specialized fitness function. We selected only the best elements to populate the next generation through crossover reproduction between random pairs of these best elements and using random mutations on the chromosomes. The user specifies the size of the population and a number of generations to be calculated. The convergence toward a good solution depends on the energy (fitness) function expression, the chromosomes definition, the size of the population, and some other parameters like the percentage of the population used to transfer their genes, and the percentage of mutations.

With permutation search, the classic genetic optimizer has to be adapted. We code chromosomes using the bijection from initial colors to the object class which may be represented as ( 1 , 2 , ..., ) where ∈ [1, ] and ≠ ∀ ≠ .

Crossover reproduction methods must be specialized too. Taking two individuals as parameters, they have to generate valid individuals (permutations). The GA literature has produced many crossover reproduction techniques developed for permutation specialized chromosomes [DW98; US15]. We chose the "Partially Mapped Crossover" (PMX) method, among others (see [START_REF] Umbarkar | CROSSOVER OPERATORS IN GENETIC ALGORITHMS: A REVIEW[END_REF] for a state of the art), in our implementation. We display an example of the PMX method on figure 5.1. Basically, the PMX crossover copies a random chosen interval of the first parent chromosomes, and fills the rest with chromosomes from the second parent. Using genetic optimization, we must adapt the mutation process to generate chromosomes which code valid permutations. A swap between two indexes simply performed this.

The author has developed a permutation dedicated genetic package for Java language. And for language R applications, the implemented R6 class is based on the GA package.

Importance value remapping

Sometimes, the difference between, on one part, between null importance factor and low importance factors and on another part between low and high importance factors, is too small. The optimization process does not converge rapidly enough. A simple linear mapping would not enhance enough the optimization.

We experimented with the use of an importance factor remapping function based on a two-stepped linear function. In order to provide flexibility, the method takes the calculated importance factors interval (zero excepted) as parameters together with a single medium point located on a percentage of the initial importance interval on , which is remapped on a percentage of the desired importance resulting interval on . In the tests, the values 0.6 percent on and 0.1 percent on were giving improved results in order to increase high values and clearly separate lowest values from 0 importance value. We display an example of such remapping on figure 5.2. Moreover, we may set importance factors that are related to classes for which color contrast is unnecessary (0 value), to a penalty value (a negative value). This should increase the convergence but only a few tests has been performed so far. Rigorous tests with running times and results comparison should be run to decide if this option is useful.

Introduction

This chapter lists several diagrams applications of our class-color assignment method. We organized it as follows. For each categorical diagram, in subsections are explained the diagram graphical rules, the graphical aspects which are handled by the importance matrix computation. When it applies, we give elementary importance factors formulas too, before providing some explanations on the final importance factor calculation (synthesis). Finally, we provide results and show comparison figures with the color assignment corresponding color distances and calculated inter-group importance factors. The subsections are the following:

• Visualization principles and graphical Rules • Graphical criteria for color assignment • Importance factor computation • Elementary importance factor computation • Synthesizing to obtain an importance factor • Results

For each diagram type, three figures are shown:

• using our color assignment optimization;

• using directly colormap index order;

• using random color permutation.;

To visually judge the adequacy of the best color permutation with the calculated inter-class importance factors, the author devised a type of comparison figure, dedicated to the color-class assignment problem (see figure 6.7 page 24). This figure presents on the same diagram the importance matrix factors and the permuted color distance matrix. Red discs area is proportional to the importance value and normalized to the maximum importance value encountered within the matrix. Green discs depict the DE2000 color distance normalized to the encountered maximum distance. The more red visible area, the less assignment performance.

We present, for each diagram, specialized comparison figures for:

• diagram with our optimized color assignment,

• diagram using directly the colormap order,

• diagram with a color random order.

The author knows that, in the visualization research domain, it is mandatory to perform user testing, evaluation and comparison with the existing method. Author's lack of time and money explains this absence.

To the author's knowledge, there is no published method to assign color to layers in the streamgraph visualization case, nor in chord diagram visualization.

The following pages show our framework applications to streamgraphs, polygonal maps, chord diagrams, line charts and some simple neighbor diagrams.

Streamgraphs

Streamgraph diagrams published by Havre et al. [START_REF] Havre | Themeriver: Visualizing Thematic Changes in Large Document Collections[END_REF] in 2002, were popularized by Lee Byron and Martin Wattenberg in a 2008 New York Times article [START_REF] Byron | Stacked Graphs -Geometry & Aesthetics[END_REF]. They are a variation of the stacked area graphs where curves replaces polylines and where layers are organized around a varying central line where stacked-graphs are vertically stacked on the (time) axis. Since the first scientific publication many improvements have been added, by aggregation [START_REF] Greffard | Visualizing a Set of Multiple Time Series with an Aggregate Stacked Graph[END_REF], and notably on the layer order [START_REF] Di | There is More to Streamgraphs than Movies: Better Aesthetics via Ordering and Lassoing[END_REF], about correcting the layer thickness in case of significant slope [START_REF] Bu | SineStream: Improving the Readability of Streamgraphs by Minimizing Sine Illusion Effects[END_REF] and on multi-resolution streamgraphs [START_REF] Cuenca | MultiStream: A Multiresolution Streamgraph Approach to Explore Hierarchical Time Series[END_REF].

21

Visualization Principles and Graphical Rules

Usually chosen to depict time varying categories, layers height is related to a specific dimension value or a number of occurrences. The layers are stacked on in constant order along axis (various orders can be chosen, depending on preferences or data criteria) but layers can present a null thickness for some time intervals. Therefore, layers may share a frontier with many other layers. Layers can be thin on a part of the diagram and thick on another part.

The number of layers, depending on the data, can be huge. Though in this case, legibility is difficult, but in our usage where the streamgraphs are displayed depending on data exploration filters, layers colors must be handled automatically and layer discriminality must be optimized.

Graphical Criteria for Color Assignment

The main visual criterion is concerned with a visual separation between layers. An easy detection of layer borders by the viewer is an important property. As some layer parts may be very thin, it is important that layers' color choice provides enough color contrast to satisfy legibility.

Importance Computation

Consequently, given a layer ordering and depicted data, we must identify the frontier sharing between layers and calculate corresponding importance factors that rely on mutual layers thickness.

Elementary Importance Computation

As layer thickness and frontiers with other layers evolve along the time dimension, evaluating elementary importance factors which code local need to have a large color contrast for two adjacent layers is a first step before compiling, along interval, a global importance factor.

Let us denote the set of time samples used to display the streamgraph composed of layers for which ℎ is the height of layer at time .

Let us also define , , a neighborhood descriptor which codes the fact that layers and share a frontier on time sample . This descriptor is a function of data values and of layers chosen order, and return 1 if a frontier exists and 0 otherwise.

If we assume that the thinner the layer, the harder the layer frontier is visible, then a decreasing function would have the desired behavior. We considered that the need to assign high contrasted colors to the layer couple is dependent on the minimum of the two layers thickness (which can be discussed). In absence of knowledge on the human response in such geometrical cases, we can calculate the inter-layer , elementary importance factor , , for time , using the inverse of height:

, = , * (1/ℎ , 1/ℎ ) (6.1)
Then, evaluating for the whole interval of values for layers and gives an array , which has to be reduced to a single factor ( , ), the importance factor for the couple of layers , .

Two figures 6.2 and 6.3 show, for a specialized streamgraph test, a display of elementary importance factors as a red layers. So far, we do not calculate thickness as layer perpendicular size, but we take layer size, which can give strange results in some parts. This could be enhanced by generating streamgraphs with correct thickness [START_REF] Bu | SineStream: Improving the Readability of Streamgraphs by Minimizing Sine Illusion Effects[END_REF].

Synthesizing to Obtain an Importance Factor

We must, thus, compile elementary importance factor array values in order to get a global inter-layers importance factor, denoted ( , ). This synthesis process can be performed via several functions:

• maximum value ( , ) = ∈ , (6.2)
• average value

( , ) = 1/ ( ) × ∈ , (6.3)
The risk of averaging while synthesizing lies in that compensation would cancel problems. Using maximum formula could sometimes result in stating that all couples of layers share the same importance value. Data experiments seem to show that the synthesis method has to be adapted to the data. Extracting the data properties which make a specific synthesis more appropriate will need further researches.

Results

Figure 6.4 on page 23 depicts the resulting labeled streamgraph color assignment (maximum value synthesis) using a narrow part of the Viridis colormap to show the ability to reduce colormap hue interval while preserving distinguishability. The time series, displaying 21 artists of the music genre "alternative dance" presented throughout the day, comes from a sociological study about music listening usage [START_REF] Le | Où va la musique ? Presses des Mines[END_REF].

In order to show the result of our class-color assignment and to compare color assignments, we also show two different color assignments, in figure 6.5 displayed with the basic order colormap and in figure 6.6 with a random color assignment.

To compare results of color assignment, the author chose to depict comparison figures dedicated to the class-color assignment problem, with importance matrix and permuted color distance matrix on the same diagram. This allows to verify the assignment of large color distances to large importance factors.

The three figures 6.7, 6.8 and 6.9 on page 24 depict comparisons for the three streamgraphs depicted on page 23: optimized, order and random assignments.

Importance for Similar Graphs

We may perform the same importance computation, based on the same formulas, for stacked-graphs and stacked bar graphs. This is also the case for circular streamgraphs and staked radar charts.

Concerning sorted streamgraphs [START_REF] Usmani | Data-Driven Ranking and Visualization of Products by Competitiveness[END_REF] or alluvial diagrams , , , the neighborhood descriptor implementation has to be coded to handle the fact that layers may have various orderings along the time interval, but the formulas remain the same.

Polygonal Maps

Maps are a kind of visualization widely used to convey information. Categories are often displayed on maps, usually made of polygons of various sizes or based on pixel colors. In this visualization case too, we must choose category color with care. Our framework can handle polygons' discriminability by color assignment optimization, and this section presents an application for polygonal maps.

Visualization Principles and Graphical Rules

Usually, several polygons associated with categories compose the map's database. Our framework needs polygon's neighborhood information. But on good database file, polygons borders are geometrically correct in term of line sharing, helping to infer polygons neighborhood. Importance by the inverse of area A simpler, yet providing worse results, method comprises directly evaluating the importance factor (without elementary importance factors estimation) by the maximum of the inverse polygon areas:

( , ) = , × (1/ , 1/ ) (6.6)
With , equal to 1 if categories and share a frontier, and 0 otherwise. The advantage of this second formula lays because R packages already include polygon area calculation. The greatest inconvenient is that it does not consider the shape of polygons, leading to attribute a small importance value to a thin long polygons despite its low thickness value. Another inconvenient consists in that two polygons that share a small edge but are of huge area result in a small importance factor.

Results

The figure 6.12 displays a 49 categories maps (Columbus spData R package) diagram using Viridis categorical colormap. It shows smaller couples of polygons assigned with higher color contrasts. The importance computation is based on inverse polygon areas. Figure 6.13 on following page depicts the corresponding importance matrix.

Chord Diagrams

Martin Krzywinski proposed chord diagrams, in a 2007 New York Times article called "Close-ups of the Genome, Spieces by Spieces by Spieces" . Chord diagrams depict fluxes (directional type) and weighted relationships between entities (un-directional type). We depict a directional chord diagram in figure 6.18 which is visible on the data-to-viz website which shows migration between world regions.

Af ric a 0 1 2 3 4 5 6

Visualization Principles

A chord diagram displays categories around a circle. It shows fluxes as arrows, starting from a group, say , and arriving on one group, say , including itself if needed. The width of each arrow depends on the flux ( , ). On each group, arriving fluxes are sorted in decreasing order. , a square matrix containing flux between categories may represent handled data with ( , ) corresponding to the flux from group towards group .

Let be the sum of the flux arriving on the group and the sum of the flux starting from the group .

Visualization Graphical Rules

The scale factor which is used to calculate the arrow's sizes is constant. The following equation, which states that no flux is lost, gives the overall fluxes sum. Chords diagrams depict arrows with the color of the flux starting group. Therefore, all the fluxes starting from a group are filled using the same color. The angular total width of these (grouped) starting arrows is related to if is the index of the group. For each group, we place incoming arrows after outgoing arrows. For a group, incoming fluxes are displayed in decreasing order. Therefore, in each group, arriving fluxes are neighboring with various colors and various thicknesses.

We can omit the factor (2. )/(2 * ) in the following importance factor calculus, as it is present in all arrows' size expression.

Graphical Criteria for Color Assignment

To allow the user to interpret the diagram, in each group, the arrows must be visually distinct one from another. We then focus the importance factor calculation on the arrows neighborhood and their visual width. As a margin separates each category from its two neighboring categories, there is no need to insure separability from groups.

The center of the chord diagram can be visually confusing, and trying to optimize the legibility of the center part of the diagram could also be a goal. But in term of flux understanding, only the size and order of the arrows on each group are essential, arrows parts in the center being kind of "symbolic". In fact, the information lies on the side of the circle.

Importance Computation

Several important aspects have therefore to be computed for a group ,

• what are the groups of the fluxes arriving on group ?

• in which order are they depicted ? fluxes neighborhood?

• what are their visible sizes?

• what is the sum of the group outgoing fluxes?

Notation

We denote as the decreasing ordered list of the group indexes of incoming fluxes for the group and as the number of incoming flux for the group .

= { } with:

• is the -st element of • ∈ [1, ], • ∈ [1, ]
As is ordered in decreasing order, we have ( ,

) ≥ ( +1 , ) for ∈ [1, - 1].
In order to ease expression writing, let us call the index of group in .

Flux Neighborhood

Using previous notations, let us define , , a directional chord diagram neighborhood descriptor which codes the fact that the fluxes coming from the groups and share a frontier on the arrival part of group .

, is equal to 1 if the index of and are successors in .

, = 1 if ∈ and ∈ and | -| = 1 0 otherwise (6.9)

Elementary Importance Matrices

There are parts on the circle corresponding to the categories in the chord diagram. Arrows may be neighbors in each of these parts. Therefore, for each category , we construct a local importance matrix that codes the need to assign color contrast between (arriving and outgoing) arrows on the group visual part.

We denote these matrices as elementary importance matrices and their calculations involve a frontier descriptor frontier descriptor , and the flux values ( , ). If a category possesses no incoming flux from other groups, its elementary importance matrix is filled with 0 values, as there is no neighboring groups to be considered.

The final chord diagram importance matrix is obtained by setting, for each matrix element, the maximum value of corresponding elements in the elementary importance matrices.

Let be the elementary importance matrix for group , and ( , ) its elements. is a square matrix containing × elements (same as the chord diagram's final importance matrix).

The importance factor depends, as previously, on the size (i.e. thickness) of arrows, and is based on the inverse of arrow size, which is related to the corresponding flux. Considering neighboring information, the importance value for two group's incoming fluxes (including flux from the same group ) is estimated using the maximum of the inverse fluxes.

( , ) = , × max(1/ ( , ), 1/ ( , )) (6.10)

Final Frontier

A remaining neighboring possibility has to be considered, which corresponds to the frontier for a given group between the overall outgoing arrows and the first incoming arrow. The index of the first incoming flux is given by 1 which is also the greatest incoming flux for group . The size of grouped outgoing fluxes is related to ∈[1, ] ( , ). Its neighboring flux, i.e. the incoming greatest flux, is ( 1 , ) (if 1 exists and 1 ≠ ). The corresponding in/out frontier importance, if 1 exists and 1 ≠ , is given by:

( , 1 ) = ( 1 ∈ ( , ) ,
1 ( 1 , ) ) (6.11)
Finally, the element ( , 1 ) of the group elementary importance matrix is updated by getting the maximum of the importance calculated on the frontier by equation 6.11 and the previous corresponding ( , 1 ) about incoming flux (equation 6.10).

Resulting Importance Matrix

To be used by the class-color assignment optimization, we must provide a single importance matrix. Synthesizing the elementary matrices in a chord diagram's importance matrix containing × elements, is performed by getting, for each element ( , ), the maximum of the corresponding elements ( , ) of the elementary importance matrices.

( , ) = ∈[1, ] ( ( , )) (6.12)

Importance Matrix Data Application

To experiment with the application of our framework on chord diagrams, we implemented the R code given on data-to-viz website. A chord diagram is displayed on the site using emigration data coming from a publication by Guy J. Abel (2017) "Estimates of Global Bilateral Migration Flows by Gender between 1960 and 2015" [START_REF] Abel | Estimates of Global Bilateral Migration Flows by Gender between 1960 and 20151[END_REF] We display the ten elementary importance matrices in figures 6.15 and 6.16, for which it is notable that some of these matrices contain only 0 as there are no neighboring arrows for the corresponding groups. Figure 6.17 shows the resulting synthesized importance matrix.

if 1 = the formula has to be modified as the arriving flux is neighboring the outgoing flux https://www.data-to-viz.com/graph/chord.html https://raw.githubusercontent.com/holtzy/data_to_viz/master/Example_dataset/13_ AdjacencyDirectedWeighted.csv

The optimized chord diagram is displayed on figure 6.19. Small fluxes are more visible, for example, on "Oceania" incoming fluxes (at bottom left). Fluxes arriving on "Europe" category, which are greater than fluxes arriving on "Oceania", are less color contrasted. But the flux from "South east Asia" to "East Asia" is clearly visible on the color optimized diagram, whereas was not enough distinct in the original diagram.

Africa

Line Charts

Line chart is probably the most used visualization diagram in everyday media, showing time values variation, estimation and comparison. This section treats only line charts which are displayed like function = ( ) graph (one value for an value, per chart). The analysis does not allow (but could be extended to allow) free poly-lines ("metro lines" for example).

Graphical Criteria for Importance

Let us consider a line chart displaying curves as segmented lines. Usually, while reading line charts, our eyes follow the various lines, estimating values and comparing one line to the other. Among difficulties which could arise when using close colors are two special cases for which the line eye following process can become hard:

• when lines are close one to another (Proximity);

• when two lines are intersecting each other with a low angle crossing (Low Angle Crossing).

We incorporate these two cases into the inter-line importance expression.

Importance Evaluation

We should relate proximity factor to the final subtended visual angle, which we could evaluate using the final displayed diagram size and viewed distance. Usually, this information is not available. Alternatively, we evaluate the proximity between lines on axis, using a percentage of the depicted interval, depending therefore only on the data. In figure 6.21 proximity zones are depicted as triangle marks and low angle intersections zones as circles.

On the contrary, we cannot evaluate low angle lines crossings without supplementary diagram information. We can compute a crossing angle as the absolute difference of the two slopes (angles) values. But the visible angle depends on the final diagram ratio. As seen in figure 6.22, the lines slope depends on the figure ratio between figure width and figure height and on the and displayed intervals.

As a first test, the final importance factor associated with two lines is based on the sum of the number of occurrences of proximity zones and low angle intersections. Two coefficients to get asymmetrical contributions of proximity and low angle crossing zones have been introduced without seeing benefits for the tested data so far.

We provide in the following formulas which count the number of "zones" for proximity and for low crossing. As the maximum number of occurrences is, for a diagram, the same for all lines (approximately the number of samples, because crossing may appear on samples and between successive samples), there is no need to normalize it.

Proximity Importance Evaluation

Let us denotes the number of depicted lines and the number of values which are given with corresponding values. The line is traced using points of coordinates ( , ) with ∈ [1, ].

An absolute limit value for which two lines would be considered as too close would not be user friendly. We prefer setting , the percentage of interval which do not depend on data. Let us denote and the minimum and maximum values depicted on the figure and and the minimum and maximum values on axis.

Let us call

, , the number of values for which two lines and are too close. This number of occurrences is given by:

, = { , ∈ [1, ] such that | -| < * ( - )} (6.13)

Low Angle Crossing Importance Evaluation

Concerning low angles line intersections, we evaluate it through a two-step process.

1. detection of values where lines are intersecting one another; 2. lines couple crossing angle evaluation for the detected values.

The user provides , a value in degrees for which two lines, crossing with an angle less than , would be difficult to follow if their colors are too close. The final energy is obtained by summing the point distinctness of the whole points in every classes:

= =1 =1 ( ) (6.19)

Point Distinctness Energy Developed

The energy equation 6.19 can be rewritten using expression point distinctness 6.18:

= =1 =1 1 |Ω | ∈Ω Δ ( , ) ( ( , )) (6.20)
with the color of the point. Ω the set of closest point to can be broken into sets, each one containing the points of given classes.

Let us call Ω , the subset of Ω containing only the points belonging to class .

Ω = ∈[1, ] Ω ,
Therefore, the ( ) in formula 6.19 can be expressed by:

( ) = ∈[1, ] 1 |Ω , | ∈Ω , Δ ( , ) ( ( , ) (6
.21)

Importance Formula Based on Point Distinctness

Then, to fit in our importance matrix concept, we re-write the previous energy expression 6.20, while extracting the importance factor. In order to simplify the re-writing, let us consider the energy part gained by two classes 1 and 2 . Δ ( 1 , 2 ) can be factorized leading to the following expression:

( 1 , 2 ) =Δ ( 1 , 2 ) × 1 =1 2 ∈Ω 1 1 |Ω 1 | ( ( 1 , 2 )) + 2 =1 1 ∈Ω 2 1 |Ω 2 | ( ( 2 , 1 )) (6.22)
with 1 (resp. 2 ) being the number of points in the the class 1 (resp. 2 ). Symmetry shows that the two contributions from 1 to 2 on one hand and 2 to 1 on the other hand must be equal. Taking therefore only one way contribution, we simplify the energy expression 6.22:

( 1 , 2 ) = Δ ( 1 , 2 ) × 1 =1 2 ∈Ω 1 1 |Ω 1 | ( ( 1 , 2 ))
Finally, the second term of the multiplication gives the importance factor for the classes 1 and 2 :

( 1 , 2 ) = 1 =1 2 ∈Ω 1 1 |Ω 1 | ( ( 1 , 2 ))
Therefore, to evaluate ( 1 , 2 ), for all the points 1 of class 1 , we construct the influence set Ω 1 . Then we reduce each set by keeping only the points belonging to class 2 . The weight function is applied and finally the importance factor is calculated by summing the results.

We have not implemented yet the previous importance factor expression for scatterplot diagram in our framework.

Simple Neighbor Diagrams

Our color-class assignment method may handle some less complicated diagrams like single stacked bar as in figure 6.28 or pie charts (generally discarded by data scientists for the lack of value comparisons but often used in general audience) as in figure 6.29. In these two cases, while classes possess 1 or 2 neighbors, improving class separation and avoiding color spreading through an optimization of color-class assignment can be profitable.

Graphical Criteria for Color Assignment and Importance Computation

As for previous diagrams, a decreasing function can model the fact that smaller objects need more color contrast with neighbors to be legible. We also apply the size inverse function in these two cases, leading to the following expressions: ( , ) = , × (1/ , 1/ ) (6.23)

( , ) = , × (1/ℎ ℎ , 1/ℎ ℎ ) (6.24)
where , denotes the neighborhood between classes and , which is equal to 1 if class objects and share a frontier, and 0 otherwise. We can notice that the multiplicative factor ( =1 )/2 which is present in all ℎ values and the corresponding factor appearing in ( , ) expression (equation 6.23) can be omitted. It won't affect the optimization, as it would only be a final multiplicative factor in the energy. expression.

Same simplification applies for a single bar chart, where =1 )/ℎ ℎ may be omitted too (equation 6.24).

Therefore, we can simplify the importance factors expression for both diagrams into the same expression:

( , ) = , × (1/ , 1/ ) (6.25)

Results

The Importance matrix is, for these two diagrams, very simple as each class possesses only 1 or 2 neighbors. The optimization process is therefore faster than for more complicated diagrams. We showed two examples on the previous page, figures 6.28 and 6.29.

Multiple Diagrams Importance Synthesis

When several visualizations of the same type and sharing some groups of data have to be designed, we can construct a global importance matrix. This matrix codes the need for contrast between the objects appearing in the diagrams. The size of the matrix corresponds to the cardinal of the union of the categories displayed in the several diagrams. We synthesize the global importance matrix calculated for each visualization. Figures 6.31 and 6.32 display two streamgraphs which share some category names (music artists). Keeping the same color for names displayed in the two visualizations seems natural. To achieve this goal, we compute the importance matrices for the two visualizations separately (see figures 6.33a and 6.33b) and we calculate a global synthesized importance matrix using the importance values appearing in the two matrices (figure 6.34).

Results

Figures 6.31 and 6.32 on page 46 depict two streamgraph diagrams containing respectively, 30 and 24 layers (artist names) displaying music usage during the day of several users. We show the corresponding calculated importance matrices in figures 6.33a and 6.33b on page 47 and the synthetized matrix is in figure 6.34. This matrix is calculated for the union of layers' name. We display the two streamgraph diagrams with the colors permutation given by our assignment optimization using the synthesized matrix.

Optimization runtime

We perform an automatic exhaustive evaluation of the permutations fitness result for visualizations based on a few classes, ≤ 8, and for greater values of , we run the genetic optimization.

The Colombus map (see figure 6.10) which is the most complicated case test (49 classes) has been calculated using 500 generations of 400 individuals, with a running time of 2 minutes on an iMac (Retina 5K, 27 inches, end 2015, 3.3 GHz Intel Core i5 quad core, 8 Go 1867 MHz DDR3) using Rstudio and an R script based on inverse polygons area importance calculation and polygons connection (spdep R package) using package GA (without parallelism).

https://www.rstudio.com/

Conclusion

The author has presented a novel framework that permits optimizing contrast color of classes objects for categorical visualization. Our method relies on a separation between palette color distances and the concept of importance factors expressing the need to get for a couple of classes a high color contrast. We construct the importance factors depending on the chosen kind of visualization and especially on the data geometrical properties associated.

We have presented categorical diagrams applications: streamgraphs, line charts, polygonal maps, chord diagrams.

Neither controlled user tests, nor comparisons with published methods have been performed. The author is aware of this important lack in this research report.

The author hopes that data scientists will embrace this novel framework, will adapt it to other diagrams and will improve the proposed diagram's importance matrix expressions and expand the energy expression.

So far, we have coded the diagrams' importance matrix calculation outside the diagram generation code (in java, or in R), but the proposed importance formulas could be directly inserted within the diagram generation code together with an export of the importance matrix.

The developed R6 classes coded in language R will be available soon on a github repository together with use examples of each of the presented diagrams.

The author will add other categorical diagrams like alluvial or Sankey diagrams to the framework and will implement published scatterplots formulas.

In the future, the author thinks that considering the diagram (and presented objects) subtended visual angle, and therefor the future context of the real life diagram viewing (diagram size, viewing distance, electronic device or printed on paper) would be inevitable. Evaluation of the distinguishability and communication from the software to the data scientist about the various problems that could arise with the generated diagram is also perhaps the next step.

,

  a neighboring factor equal to 1 if category and share a polygon edge for index , the elementary importance for point , neighboring factor equal to 1 if category and share a polygon edge the area of polygon iii Chord Diagram Symbol Definition ( , ) flux from group to group sum of fluxes arriving to group sum of fluxes starting from group the decreasing ordered list of the group index of incoming flux for group the number of incoming flux for group , neighborhood descriptor that codes the fact that fluxes coming from group and from group share a frontier on group the elementary importance matrix for group ( , ) the elements of the elementary matrix Line-graph Symbol Definition the number of values on ( , ) the coordinate of point ∈ [1, ] the percentage of the interval for which two lines are considered as too close one from another , the number of values for which line and line are too close , the number of values for which line and line are intersecting with a too small angle Multiple Figures Importance Symbol Definition the list of group names for figure the names at index in ∪ the union set of all ∩ the intersection set of all 1 Introduction

Figure 1 . 1 :

 11 Figure 1.1: Elastic Lists by Moritz Stefaner

  It's useful to list what this presented research is about and what it is not.

Figure 1 . 2 :

 12 Figure 1.2: StreamFacet using music log

Figure 3 . 1 :

 31 Figure 3.1: Example of Color Distance Matrix

AFigure 3 . 2 :

 32 Figure 3.2: Example of Importance Matrix

Figure 4 . 1 :

 41 Figure 4.1: Varying frontier length

Figure 4 . 2 :

 42 Figure 4.2: Varying rectangles width

Figure 5 . 1 :

 51 Figure 5.1: Genetic crossover for permutation

Figure 5 . 2 :

 52 Figure 5.2: Importance value mapping

Figure 6 . 1 :

 61 Figure 6.1: Streamgraph with optimized assignment of a partial viridis colormap

Figure 6 . 2 :Figure 6 . 3 :

 6263 Figure 6.2: Streamgraph elementary importance factors for layers DDD and EEE

Figure 6 . 10 :

 610 Figure 6.10: Colombus polygonal maps (Columbus spData R package)

Figure 6 . 9 :

 69 Figure 6.9: Steamgraph matrix comparison for colormap random assignment

Figure 6 . 11 :

 611 Figure 6.11: Perpendicular distances through categories

Figure 6 . 14 :

 614 Figure 6.14: Chord diagram with color assignment

  https://archive.nytimes.com/www.nytimes.com/imagepages/2007/01/22/science/20070123_SCI_ILLO.html https://www.data-to-viz.com/graph/chord.html If we neglect the angular inter-group margin, the angular size of each group is determined by:

Figure 6 . 18 :Figure 6 . 19 :

 618619 Figure 6.18: Original Chord Diagram from data-to-viz website

Figure 6 . 20 :

 620 Figure 6.20: Line charts GDP with color assignment optimization

Figure 6 . 21 :Figure 6 . 22 :

 621622 Figure 6.21: Problematic zones detection

Firefox

  file:///Users/languenou-e/DiversLatex/internalReportImportanceDrivenC... 1 sur 1 17/05/2022 15:28

Figure 6 . 27 :

 627 Figure 6.27: Scatterplot example (wikipedia)

Figure 6 . 28 :)Figure 6 . 29 :

 628629 Figure 6.28: Bar chart example (dummy data) with reduced colormap

Figure 6 .

 6 Figure 6.31: Streamgraph 1

https://datavizproject.com/data-type/sorted-stream-graph/ https://datavizproject.com/data-type/alluvial-diagram/

Algorithm 1 Synthesis importance matrix filling //----and are names of ∪ //----initialize with 0 for ∈ ∪ do for ∈ ∪ do ∪ ( , ) ← 0 end for end for //----Fill using 1 for ∈ 1 do for ∈ 1 do ∪ ( , ) ← 1 ( , ) end for end for //----Fill using 2 for ∈ 2 do for ∈ 2 do ∪ ( , ) ← 2 ( , ) end for end for //----Fill for 1 ∩ 2 for ∈ ∩ do for ∈ ∩ do ∪ ( , ) ←

( 1 ( , ), 2 ( , )) end for end for

Adele Amy Winehouse Ariana Grande Azealia Banks Britney Spears Charli XCX Christina Aguilera Fergie Florence + the Machine Gwen Stefani Jay Sean Jennifer Lopez John Legend Justin Timberlake Katy Perry Kelly Rowland Kylie Minogue La Roux Lady Gaga Lily Allen Lorde Madonna Nicki Minaj Nicole Scherzinger Paloma Faith Rihanna Sia Sophie Ellis-Bextor Taylor Swift Amy Winehouse Ariana Grande Azealia Banks Britney Spears Charli XCX Christina Aguilera Fergie Florence + the Machine Gwen Stefani Jay Sean Jennifer Lopez John Legend Justin Timberlake Katy Perry Kelly Rowland Kylie Minogue La Roux Lady Gaga Lily Allen Lorde Madonna Nicki Minaj Nicole Scherzinger Paloma Faith Rihanna Sia Sophie Ellis-Bextor Taylor Swift The Pussycat Dolls Adele Amy Winehouse Ariana Grande Azealia Banks Britney Spears Charli XCX Christina Aguilera Fergie Florence + the Machine Gwen Stefani Jay Sean Jennifer Lopez John Legend Justin Timberlake Katy Perry Kelly Rowland Kylie Minogue La Roux Lady Gaga Lily Allen Lorde Madonna Nicki Minaj Nicole Scherzinger Paloma Faith Rihanna Sia Sophie Ellis-Bextor Taylor Swift Amy Winehouse Ariana Grande Azealia Banks Britney Spears Charli XCX Christina Aguilera Fergie Florence + the Machine Gwen Stefani Jay Sean Jennifer Lopez John Legend Justin Timberlake Katy Perry Kelly Rowland Kylie Minogue La Roux Lady Gaga Lily Allen Lorde Madonna Nicki Minaj Nicole Scherzinger Paloma Faith Rihanna Sia Sophie Ellis-Bextor Taylor Swift The Pussycat Dolls (a) First streamgraph imp. matrix Adele Alanis Morissette Amy Winehouse Anastacia Ariana Grande Avril Lavigne Charli XCX Cyndi Lauper Demi Lovato Ed Sheeran Flo Rida Florence + the Machine James Blunt Leona Lewis Lorde Madonna Nicki Minaj Pitbull Rihanna Selena Gomez Shakira Sia Taylor Swift Alanis Morissette Amy Winehouse Anastacia Ariana Grande Avril Lavigne Charli XCX Cyndi Lauper Demi Lovato Ed Sheeran Flo Rida Florence + the Machine James Blunt Leona Lewis Lorde Madonna Nicki Minaj Pitbull Rihanna Selena Gomez Shakira Sia Taylor Swift Whitney Houston Adele Alanis Morissette Amy Winehouse Anastacia Ariana Grande Avril Lavigne Charli XCX Cyndi Lauper Demi Lovato Ed Sheeran Flo Rida Florence + the Machine James Blunt Leona Lewis Lorde Madonna Nicki Minaj Pitbull Rihanna Selena Gomez Shakira Sia Taylor Swift Alanis Morissette Amy Winehouse Anastacia Ariana Grande Avril Lavigne Charli XCX Cyndi Lauper Demi Lovato Ed Sheeran Flo Rida Florence + the Machine James Blunt Leona Lewis Lorde Madonna Nicki Minaj Pitbull Rihanna Selena Gomez Shakira Sia Taylor Swift Whitney Houston (b) Second streamgraph imp. matrix Adele Amy Winehouse Ariana Grande Azealia Banks Britney Spears Charli XCX Christina Aguilera Fergie Florence + the Machine Gwen Stefani Jay Sean Jennifer Lopez John Legend Justin Timberlake Katy Perry Kelly Rowland Kylie Minogue La Roux Lady Gaga Lily Allen Lorde Madonna Nicki Minaj Nicole Scherzinger Paloma Faith Rihanna Sia Sophie Ellis-Bextor Taylor Swift The Pussycat Dolls Alanis Morissette Anastacia Avril Lavigne Cyndi Lauper Demi Lovato Ed Sheeran Flo Rida James Blunt Leona Lewis Pitbull Selena Gomez Shakira Amy Winehouse Ariana Grande Azealia Banks Britney Spears Charli XCX Christina Aguilera Fergie Florence + the Machine Gwen Stefani Jay Sean Jennifer Lopez John Legend Justin Timberlake Katy Perry Kelly Rowland Kylie Minogue La Roux Lady Gaga Lily Allen Lorde Madonna Nicki Minaj Nicole Scherzinger Paloma Faith Rihanna Sia Sophie Ellis-Bextor Taylor Swift The Pussycat Dolls Alanis Morissette Anastacia Avril Lavigne Cyndi Lauper Demi Lovato Ed Sheeran Flo Rida James Blunt Leona Lewis Pitbull Selena Gomez Shakira Whitney Houston Adele Amy Winehouse Ariana Grande Azealia Banks Britney Spears Charli XCX Christina Aguilera Fergie Florence + the Machine Gwen Stefani Jay Sean Jennifer Lopez John Legend Justin Timberlake Katy Perry Kelly Rowland Kylie Minogue La Roux Lady Gaga Lily Allen Lorde Madonna Nicki Minaj Nicole Scherzinger Paloma Faith Rihanna Sia Sophie Ellis-Bextor Taylor Swift The Pussycat Dolls Alanis Morissette Anastacia Avril Lavigne Cyndi Lauper Demi Lovato Ed Sheeran Flo Rida James Blunt Leona Lewis Pitbull Selena Gomez Shakira Amy Winehouse Ariana Grande Azealia Banks Britney Spears Charli XCX Christina Aguilera Fergie Florence + the Machine Gwen Stefani Jay Sean Jennifer Lopez John Legend Justin Timberlake Katy Perry Kelly Rowland Kylie Minogue La Roux Lady Gaga Lily Allen Lorde Madonna Nicki Minaj Nicole Scherzinger Paloma Faith Rihanna Sia Sophie Ellis-Bextor Taylor Swift The Pussycat Dolls Alanis Morissette Anastacia Avril Lavigne Cyndi Lauper Demi Lovato Ed Sheeran Flo Rida James Blunt Leona Lewis Pitbull Selena Gomez Shakira Whitney Houston Figure 6.34: Synthetized imp. matrix

Graphical Criteria for Color Assignment

In this kind of visualization too, graphical objects' thickness influences the perception. As stated by Newhall [START_REF] Sidney | Width and area thresholds of discrimination of two colors[END_REF], the length of the border between two polygons does not appear to be a good criterion. The perpendicular distance through the polygon seems to be a more accurate property.

Importance Computation

Several polygons may belong to a category and because polygons may be composed of complicated shapes, we estimate perpendicular distances along the borders which separate categories. As in streamgraph importance computation, we calculate perpendicular distances on the two sides of the border. These perpendicular thicknesses are used to estimate the elementary importance factors.

Elementary Importance Computation

We choose a step value, depending on the map scale, used as traveling increment along the frontier between two successive elementary importance factor estimations. On the lines separating category polygons, we generate points using step value, from which we compute perpendicular thicknesses on both sides. Then, we get an elementary importance value for each point, by evaluating the maximum of the inverse of the two thicknesses. Therefore, we obtain an array of elementary importance factors for each category couple, which has to be synthesized to get a single scalar value, the inter-class importance factor. Figure 6.11 shows a simple example of perpendicular distances estimation. Four categories compose the map, displayed in pink, light pink, orange and yellow. The four images display the perpendicular distances found for each category, top-left the light pink category, top-right the yellow one, bottom-left, the orange category and bottom-right the pink one.

Let us now consider a map composed of categories and, for simplification, let us assume that a category is made of a single polygon .

We consider the set of edges of the category which compose the frontiers with another category. We assume that a point generator is available, that produces 2D points , separated by a distance along the edge of . If is the number of points generated along category, we have

Let us consider now a method ( ) which calculates the distance traveled within the polygon from the point perpendicularly to the current polygon edge (i.e. a perpendicular thickness). Calling this method ( ) using the neighboring category on the current edge would give the perpendicular distance traveled within the category from the point .

As previously for streamgraph diagram, we use the same thickness inverse function to evaluate the distinctness between colors. Therefore, we calculate the elementary importance factor , as following, using , which is equal to 1 if category and share a polygon edge on point , and 0 otherwise:

Let us consider the intersections between line and line . First,we list the values for which there is a change in and value order. To perform this detection, , , an array of values coding the order, is computed as following:

[-1, 0, 1] and [1, 0, -1] in the , vector gives the set of values, denoted

, , for which the crossing angle has to be evaluated. The second step is concerned with the crossing angle evaluation. Let us define: the data ratio.

Let us now calculate the angle with axis of a single line for the value part. Using and , the slope of line in degrees for the values provided by vector , is given by:

Let us call , , the number of zones for which the crossing angle is too low, that is given for line and line by the following expression:

) where is set by the user. Finally, we express the importance factor for line and line , thanks to the two coefficients and which are defined to provide flexibility in the importance factor evaluation.

So far, the few experiments have shown that setting and to 0.5 were giving good results, but we should perform thorough testing to confirm this hypothesis.

Results

A good test base for line-charts color assignment optimization is provided by a page of the website Our World in Data . The treated data are the Percentage of Americans living alone, by age from year 1900 to year 2018. The figure 6.23 shows a image capture from the site. Figures 6.24a and 6.24b display respectively color lines without optimization and with color assignment optimization.

We show comparison figures with the color distance matrix and the importance matrix:

• without color assignment optimization in figure 6.25a

• with a random color assignment in figure 6.25b

• with color assignment optimization in figure 6.26

Scatterplots Diagrams

Scatterplots are 2D diagrams usually displaying records using two properties, sometimes more.

Visualization Principles and Visualization Graphical Rules

In process when discs overlap or when there are regions in the diagram displaying close points belonging to many classes.

Point Distinctness for Class Separation by Palettailor

Here under, we show the formulas for point distinctness which are given in the "Palettailor" paper [START_REF] Lu | Palettailor: Discriminable Colorization for Categorical Data[END_REF] in order to express the quality of the separation between classes using a palette color permutation. Let = 1 ... the color samples and = 1 ... the points where data class is composed of points. The point distinctness is given for point by

with Ω the set of the closest point to . The color distance denoted by Δ ( , ). ( ( , )) a geometric distance allowing a greater weight to close points and a lesser weight to distant points: ( ) = 1/ Ω is obtained via an -shape (based on Delaunay triangulation).

Class is composed of points 1 , 2 , ...,

.

Once the synthesised importance matrix is calculated, our color-class assignment optimization affects colors to layers in the two visualizations. The following section explains the formulas involved in the synthesized importance matrix calculation. Let 1 be the name at index in set 1 and 2 the name at index in 2 .

Global Synthesized Importance Matrix Computation

Let us call ∪ the union set of 1 and 2 and denote ∩ as the intersection set of 1 and 2 .

Let us suppose that importance matrices 1 and 2 are computed using the formulas and data corresponding to the two diagrams 1 and 2.

We can assume that an access function 1 ( 1 , 1 ) is available, that helps to get an element of the matrix 1 using two names appearing in 1 , instead of using their matrix indexes. 1 ( 1 , 1 ) returns the importance factor for the two class objects which names are 1 and 1 . In the same way, importance factor of importance matrix 2 for the two names 2 and 2 can be obtained by calling 2 ( 2 , 2 ).

To compute , the synthesis of the two importance matrices, for two names ( ∪ , ∪ ) in ∪ × ∪ , the following rules are applied (see figure 6.30):

• use the maximum of 1 and 2 if both names belong to ∩ • use 1 if one of the names belong to 1 minus 2 and the other does not appear in 2 minus 1 • use 2 if one of the names belong to 2 minus 1 and the other does not appear in 1 minus 2 • otherwise the corresponding importance value is set to 0. This gives the following formula, for ∪ , ∪ ∈ ∪ × ∪ :

The algorithm to fill the synthesized importance matrix ( ∪ ) is somehow simpler: Implementation

Java Language and R language

First devised to be used in our facetStreamgraph software, we code the importance matrix calculation for streamgraph and genetic color-layer assignment optimization, in java using processing framework.

With the potential extensions to other diagrams, we have coded R6 classes which are an implementation of class for language R, in order to provide a package to the community (available soon on github, the author expecting pros, cons, improvements and applications to other categorical diagrams).

The R6 classes are:

• an R6 class for color-class assignment optimization:

using GA package to estimate the best permutation by genetic optimization and PMX crossover reproduction, which calculate color distance matrix using Farver package to compute the DE2000 colordistance matrix • a base R6 class to handle importance matrix memory allocation, getters and setters • inherited R6 classes for:

streamgraphs (with natural layers order, but extendable to other layer order) polygonal maps. Coded into language R using the inverse of polygon area (but tested in java using perpendicular distance along the polygon frontier). chord diagrams (limited to directional, so far) line-charts (not poly-lines as in a "metro maps", so far) simple neighbor diagrams (single bar chart and pie chart)

The following list of R packages which have been helping a lot in this research:

The synthetizing of multiple diagrams is coded in java but will be coded in R too. Scatterplot diagram is the next diagram to be included in the R package.

www.processing.org