Slavkov Dragan

Hajdukovic
email: dragan.hajdukovic@physac.me

Hawking radiation cannot exist if quantum vacuum fluctuations are gravitational dipoles

It was recently suggested that what we call dark matter and dark energy, can be explained as the local and global effects of the gravitational polarization of the quantum vacuum by the immersed Standard Model matter. This result appears as the consequence of the working hypothesis that by their nature quantum vacuum fluctuations are virtual gravitational dipoles. Here, as a consequence of the same hypothesis we point out that instead of the non-existent thermal Hawking radiation there is a much stronger and potentially detectable, non-thermal radiation which is caused by the conversion of virtual particle-antiparticle pairs into real ones; this conversion happens deep inside the horizon of a black hole. Contrary to Hawking radiation which leads to the black hole information paradox, there is no information loss paradox within the framework of the quantum vacuum "enriched" with virtual gravitational dipoles.

Let us start with one of the most beautiful and the most famous relations of theoretical physics:

GM c T k H B  8 3   (1)
The physical meaning of the above relation [1] is that a Schwarzschild black hole of mass M radiates as a black body of temperature T H ;  , c, G and k B are respectively the reduced Planck constant, the speed of light, the Gravitational constant and the Boltzmann constant.

The Hawking temperature is an extremely low temperature. If we limit ourselves to astronomical black holes which have masses in the range from a few solar masses to ten billion solar masses, the corresponding Hawking temperature varies from . The hottest black holes have a temperature 100 million times smaller than the tiny temperature of the cosmic microwave background. Even if the Hawking radiation exists, there is no way that we can detect such a miniscule radiation by observing the astronomical black holes.

It is amusing that such a tiny effect, if it exists, can cause one of the major problems in theoretical physics: the information loss paradox [2]. If the Hawking radiation doesn't exist, the information loss paradox doesn't exist as a well.

While it is always neglected, as a phenomenon depending on the existence of the quantum vacuum, Hawking radiation is model-dependent; it depends on the used model of the gravitational properties of the quantum vacuum. Hawking calculations correspond to the case when quantum vacuum fluctuations strictly behave as a positive gravitational charge; hence, Hawking calculations are invalid if, for instance, quantum vacuum fluctuations are virtual gravitational dipoles.

It was recently suggested [3][4][5][START_REF] Hajdukovic | What if quantum vacuum fluctuations are virtual gravitational dipoles[END_REF] that what we call dark matter and dark energy can be explained as the local and global effects of the gravitational polarization of the quantum vacuum by the immersed Standard Model matter. This result appears as the consequence of the working hypothesis, that by their nature quantum vacuum fluctuations are virtual gravitational dipoles; in particular this hypothesis is true

______________________________________________________________________________

28th Texas Symposium on Relativistic Astrophysics Geneva, Switzerland --December 13-18, 2015

if particles and antiparticles have the gravitational charge of the opposite sign, what is on the way to be tested by three competing experiments at CERN (ALPHA, AEGIS and GBAR). Here, as a consequence of the same hypothesis we suggest that instead of the nonexistent thermal Hawking radiation there is a much stronger and potentially detectable, non-thermal radiation which is caused by the conversion of virtual particle-antiparticle pairs into real ones; this conversion happens deep inside the horizon by the virtue of extremely strong gravitational field (the particle-antiparticle creation rate increases with the strength of the field). Contrary to Hawking radiation which leads to the black hole information paradox, there is no information loss paradox within the framework of the quantum vacuum "enriched" with virtual gravitational dipoles. Before any mathematical considerations let us note an obvious fact, if particles and antiparticles have the gravitational charge of the opposite sign a black hole is also a white hole. A black hole made from matter is a black hole for matter but a white hole for antimatter, while a black hole made from antimatter is a black hole for antimatter but white whole for matter. It would be better to call these objects black-white holes instead of black holes. And, this is compatible with General Relativity; to see it let us consider the simplest case of a Schwarzschild black hole made from matter. While it is often neglected, from a mathematical point of view there are two solutions: the positive mass Schwarzschild solution

     d d r dr r c GM dt r c GM c ds 2 2 2 2 1 2 2 2 2 2 sin 2 1 2 1                    (2)
considered as the physical space-time metric; and the negative mass Schwarzschild solution

     d d r dr r c GM dt r c GM c ds 2 2 2 2 1 2 2 2 2 2 sin 2 1 2 1                    (3)
considered as a nonphysical solution. It serves as the simplest example of a naked singularity [START_REF] Preti | [END_REF] and a repulsive space-time allowed by mathematical structure of general relativity but rejected as nonphysical (but, imagine Dirac neglecting his negative energy solution and missing the prediction of antimatter). However, in the framework of the gravitational repulsion between matter and antimatter, both solutions may be given a physical meaning: the metric (2) is the metric "seen" by a test particle, while the metric (3) is the metric "seen" by a test antiparticle . The major difference is that there is a horizon in the case of metric (2), while there is no horizon in the case of metric (3). In simple words, a black hole made from matter acts as a black hole with respect to matter and as a white hole with respect to antimatter.

Deep inside its matter horizon, antimatter particles can be created in two different ways. First, a black hole can absorb material from its neighborhood. It is obvious that, as the result of the collisions of the infalling material (analogous to collisions in our accelerators), different kinds of antiparticles can be created inside the horizon and (assuming the gravitational repulsion between matter and antimatter) long-living antiparticles would be violently ejected outside the horizon; hence black holes contribute to the high energy component of antimatter in cosmic rays. Of course, the ejection rate should be greater if the quantity of the infalling material is greater; a black-white hole behaves as an irregular source of antimatter.

As we will argue later the energy m  with which an infalling particle of mass m hits the target (and consequently the upper limit for energy of products of collision) is ! Of course this kind of radiation is independent from the existence of the quantum vacuum.

In addition to the above irregular creation and emission of antiparticles there is a second mechanism of creation of particle-antiparticle pairs, mainly limited to neutrino-antineutrino pairs. Namely, virtual particle-antiparticle pairs from the quantum vacuum might be converted into real ones by a sufficiently strong gravitational field deep inside the horizon of a black hole (this is the gravitational analog of the Schwinger mechanism in quantum electrodynamics).

According to the Schwinger mechanism in quantum electrodynamics [8], a virtual electron-positron pair can be converted to a real one by an external field which, during their short lifetime, can separate particle and antiparticle to a distance of about one reduced Compton wavelength.

For a constant acceleration a (which corresponds to a constant electric field) the particle creation rate per unit volume and time (for particles with mass m ), can be written as [5, 9]]

m cr m cr n cr m m m c a mc a a n n a a c dtdV dN     2 1 2 4 , , exp 1                       (5)
If there are virtual gravitational dipoles, equation ( 5) is valid for gravity; consequently instead of Hawking radiation there is a radically different, non-thermal radiation, based on the gravitational version of the Schwinger mechanism.

Equation ( 5) contains a sum of exponential functions with negative exponents; hence, the particle creation rate is significant only for a gravitational field a greater than the critical value

H m H m S m m r c c GM r c R dt dN                   2 2 2   (7)

______________________________________________________________________________

28th Texas Symposium on Relativistic Astrophysics Geneva, Switzerland --December 13-18, 2015

According to [START_REF] Preti | [END_REF], the particle-antiparticle creation rate per unit time depends on both mass M and radius H r . If H r (i.e. the size of a black hole) is very small, the conversion of matter into antimatter is very fast! At first sight, this looks to be the demise of the existence of black holes as objects with extremely long lifetimes. However, it is obvious that the first production of the lightest charged particles (electron-positron pairs) is accompanied with a phase transition from the Schwarzschild metric to the Reissner-Nordstrom metric (i.e. metric of a negatively charged black hole). The negative electric charge of the black hole opposes both [9] the further collapse and the further creation of electron-positron pairs by the gravitational field (it is because the electric and gravitational force on a positron, have opposite directions; hence, after some time the ejection of positrons should be stopped, and, as a final result, a black hole made from matter should emit mainly antineutrinos.). Consequently, the size of a black hole and the critical radius for production of the electron-positron pairs should be of the same order of magnitude; we may use the approximation ; the size of a tennis ball but not a singularity! The number of the ejected antineutrinos (equation ( 7)) is of the order of 41 10 antineutrinos per second with maximal energy (equation ( 4)) of a few GeV. These numbers suggest that antineutrinos created by black hole from the quantum vacuum, might be detectable with a future generation of the neutrino telescopes.

The fact that radiation caused by the Schwinger mechanism is not a thermal one makes our theory of black hole radiation free of the information loss paradox which is inherent shortcomings of Hawking's theory because of its thermal nature [2].



  are respectively the Schwarzschild radius of the black hole and the reduced Compton wavelength of electron. Consequently, a supermassive black hole with mass of about 10 10 solar masses may emit antiprotons and antineutrons with energies up to a few GeV 12 10

  of a black hole with mass M; the comparison leads to the conclusion S cr g a  , i.e. a virtual pair can be converted to a real one only deep inside the horizon of a black hole. Instead of considering the mass collapsed to singularity, let us consider a black hole as a "ball" of a small size S H R r  , and let us define a critical radius S Cm R r  , as the distance at which the gravitational acceleration 2 r GM g  , produced by a Schwarzschild black hole (according to equation (3)), has the critical value shell with the inner radius H r and the outer radius Cm r acts as a "factory" for creation of particle-antiparticle pairs with mass m . It is evident that there is a series of decreasing critical radiuses Cm r . For instance, according to (6), the critical radius  C r corresponding to neutrinos is nearly four orders of magnitude greater than the critical radius Ce r for electrons. Integration of Eq. (5) over the shell determined by

  equation (4) as the upper bound for the energy of ejected antiparticles with mass m .According to the approximationCe H r r  and equation (6), the size of the supermassive black hole in the center of the Milky Way (with

Acknowledgments: We thank the "Hipotekarna Banka" in Montenegro for the sponsorship of our participation on the 28th Texas Symposium on Relativistic Astrophysics.


Fei Liu
email: fei.liu@insa-lyon.fr

Arnaud Lelevé
email: arnaud.leleve@insa-lyon.fr

Damien Eberard
email: damien.eberard@insa-lyon.fr

Tanneguy Redarce
email: tanneguy.redarce@insa-lyon.fr

A Dual-user Teleoperation System with Adaptive Authority Adjustment for Haptic Training

Keywords: Dual-user Teleoperation, Port-Hamiltonian, Adaptive Authority Adjustment (AAA), Shared Control

This paper presents a shared control based dual-user teleoperation haptic training system. The main contribution is an Adaptive Authority Adjustment (AAA). The authority is detemined online according to the trainee's behavior performance. An evaluation method is introduced based on an adaptive virtual boundary, which results into a time-varing dominance factor. An overruling function is set upstream to solve some specific cases. The system is modeled and controled in port-Hamiltonian form for passivity preserving. Experiments are conducted for validation.

Introduction

Medical robotics have received a great deal of attention for the past decades [START_REF] Taylor | Medical robotics in computer-integrated surgery[END_REF]. As an important part of this field, bilateral teleoperation systems which enable the execution of a remote task by providing haptic feedback, find useful applications such as Minimally Invasive Surgery (MIS) [START_REF] Tavakoli | Haptics For Teleoperated Surgical Robotic Systems[END_REF] and medical training systems [START_REF] Panait | The role of haptic feedback in laparoscopic simulation training[END_REF]. Indeed, MIS requires skilled and trained staffs as it requires precision, dexterity and reliability for the surgeon who is penalized by a limited observation and operation field (shaking cameras, reduced field of view, visual interruptions, ...). Simulation based training is progressively extending the classical medical hands-on training [START_REF] Fairhurst | Simulation speak[END_REF] but for complex training cases, it is useful to work on a simulated with a mentor who can make demonstrations and to bring real-time corrections to the trainee's motions.

Dual-user teleoperation systems have been proposed to fulfill the purpose of supervised haptic training. This kind of system is an extension of the traditional bilateral teleoperation system, which features two users working collaboratively and simultaneously on a shared remote environment. A typical dual-user training system is shown in Fig. 1.

Several architectures have been proposed for the dual-user teleoperation system. The Shared Control based structure has been mostly developed in [START_REF] Ghorbanian | A novel control framework for nonlinear time-delayed dual-master/single-slave teleoperation[END_REF][START_REF] Khademian | Shared control architectures for haptic training: performance and coupled stability analysis[END_REF][START_REF] Nudehi | A shared-control approach to haptic interface design for minimally invasive telesurgical training[END_REF][START_REF] Razi | Analysis of coupled stability in multilateral dual-user teleoperation systems[END_REF]. The main idea of this architecture is to share the control authority of each user over the slave robot according to a dominance factor (α ∈ [0, 1]). When α = 1 (resp. 0), the trainer (resp. trainee) has full authority on the trainee's (resp. trainer's) device and the slave. When 0 < α < 1, both users share the slave control with a dominance (over the other user) which is function of α. The control authority shared between the users is chosen according to their relative level of skills and experiences.

For the haptic training application, it is important to design a system enabling adaptive authority adjustment. During a given training task, the authority of the trainee over the slave should be adjusted adaptively according to his performances. This allows the trainer to focus on the task without having to manually manage the authority factor when the trainee deviates from the right motion. In any case, the trainer still holds the rights to reset the trainee's authority during the training progress, even when the trainee shows skillfulness. This kind of system requires for Online Authority Adjustment (OAA) behaviors without disturbing the stability and performance. At the same time, an online motion measure of the trainee's skill level which adapts the control authority should be provided. We found that only a few papers are concerned with this issue. In [START_REF] Shahbazi | A dual-user teleoperated system with virtual fixtures for robotic surgical training[END_REF], the control authority is adaptively adjusted according to the trainee's expertise. But it requires to specify a maximum desired level of authority of the trainee over the task at first. As a matter of fact, the trainer cannot alter this desired level during training progress. In [START_REF] Shahbazi | Networked dual-user teleoperation with time-varying authority adjustment: A wave variable approach[END_REF], the shared control authority is managed using a time-varying dominance factor. However, the proposed method necessitates a bounded first-derivative for the dominance factor α(t). This involves that it should be pre-designed as a derivable function. Both of the two aforementioned methods constrains the cases of emergency when the authority needs to be changed suddenly.

In this paper, our main contribution is to incorporate the Adaptive Authority Adjustment (AAA) into a Shared Control Based Dual-User Teleoperation system. The passivity of the system is ensured by port-Hamiltonian approach. The outline of this paper is as follows: next section introduces the dual-user architecture we based our work on. Part 3 defines the AAA while part 4 shows experimentation results before our conclusions.

2 Shared Control Based Dual-user Teleoperation Fig. 2 The global scheme of shared control based dual-user teleoperation system. The structure inside the blue solid line is the shared control based architecture.

In this section, we introduce a shared control based teleoperation, as shown in Fig. 2. The system is modeled within port-Hamiltonian framework.

Port-Hamiltonian Approach

The port-Hamiltonian framework is an energetic based generalization of the standard Hamiltonian mechanics. The port-Hamiltonian approach allows to keep track of the energy flows in the dynamic behaviors with its energetic structure, which is favorable in the modeling process. From the view of control, one of the advantages of such approach is that the Hamiltonian function, which is usually formed as Lyapunov function explicitly appears in the dynamics of the system [START_REF] Maschke | Port controlled hamiltonian systems: modeling origins and system theoretic properties[END_REF]. The most common representation of a port-Hamiltonian system is the following:

     ẋ = [J(x) -R(x)] ∂H ∂x + g(x)u y = g T (x) ∂H ∂x (1)
where x ∈ R n is the state and H(x) : R n → R represents the Hamiltonian function;

J(x) = -J T (x) is a skew-symmetric matrix representing Dirac structure, R(x) = R T (x) ≥ 0 specifies the energy dissipation, g(x)
is a matrix representing the way that the power is exchanged through the power ports formed by input-output pair (u, y) between the system and its environment.

Port-Hamiltonian approach has been applied for bilateral system modeling and controlling in [START_REF] Secchi | Control of Interactive Robotic Interfaces: A Port-Hamiltonian Approach[END_REF][START_REF] Stramigioli | Geometric scattering in robotic telemanipulation[END_REF]. The intrinsically passive controller (IPC) is proposed, which is passive regardless the characteristics and parameters. This provides a natural robustness and leaves freedom to tune its parameters for performance. In our architecture, we reuse the IPC controllers as our local compliance controller.

Shared Control Based Architecture

In this study, a one degree of freedom (rotation) system is modeled. The main concept of shared control is to introduce a dominance factor. We use Dirac structure, which keeps the power balance (see [START_REF] Schaft | L2-Gain and Passivity Techniques in Nonlinear Control[END_REF]), for authority management. Three Dirac structures are inserted between the IPC controllers, named D m1 , D m2 and D s . In order to achieve our control goal, three dominance factors α, β 1 , β 2 ∈ [0, 1] are adopted. As the efforts (forces) and flows (velocities) follow power-conserving interconnection (skew-symmetric representation, see [START_REF] Schaft | L2-Gain and Passivity Techniques in Nonlinear Control[END_REF]), the behavior of these Dirac structures is passive and lossless. The D m1 , D m2 and D s in input-output matrix are given by,

D m1 :   θr1 T s1 y 1   =   0 α 1 -α -α 0 0 α -1 0 0     T r1 θs1 u 1   D m2 :   θr2 T s2 y 2   =   0 1 -α α α -1 0 0 -α 0 0     T r2 θs2 u 2   D s :   θs1 θs2 T rs   =   0 0 β 1 0 0 1 -β 2 -β 1 β 2 -1 0     T s1 T s2 θrs   (2)
The relationship between α and β 1 , β 2 are defined as,

β 1 = α, α = 1, 0 1, 0 < α < 1 β 2 = α, α = 1, 0 0, 0 < α < 1 (3)
Thus, we obtain three modes by changing the dominance factor α: training mode (α = 1), guidance mode (0 < α < 1) and evaluation mode (α = 0). Notice that the modulated flow source MSf is associated with a velocity signal which is equal to θrs .

Passivity

As shown in Fig. 2, in oder to analyze the close-loop passivity, the dual-user system can be divided into several parts. Both users and the environment could be considered with passive behaviors, which is a common assumption in the literature. The master and the slave robot are physically passive. The IPC controllers are intrinsically passive. The shared control based architecture is passive due to the powerconserving composition of three Dirac structures. As long as the modulated flow sources MSf keep passive behaviors, the passivity of close-loop dual-user teleoperation system is preserved.

Proposition 1 The modulated flow sources MSf hold passive behaviors: i.e., ∃ finite constant d ∈ R s.t.

t 0 u T 1 y 1 + u T 2 y 2 dt ≤ d 2 ∀t ≥ 0 (4)
i.e., maximum generated energy from the MSf is bounded.

Proof. Let us first denote the generated energy at time t from MSf by integrating Eq. 2 as,

t 0 u T 1 y 1 + u T 2 y 2 dt = t 0 (1 -α)T T r1 θrs + αT T r2 θrs dt = t 0 -T T r1 θr1 -T T r2 θr2 + T T rs θrs dt (5)
Considering the subsystem of masters (or slave) with the corresponding IPC controller, which is passive, there exists a finite constant c i , ∈ R, s.t.

t 0 T T h1 θm1 + T T r1 θr1 dt ≥ -c 2 1 ∀t ≥ 0 t 0 T T h2 θm2 + T T r2 θr2 dt ≥ -c 2 2 ∀t ≥ 0 t 0 T T e θs -T T rs θrs dt ≥ -c 2 3 ∀t ≥ 0 (6)
Suppose that the operators and the environment define passive mappings, i.e., ∃ finite constant

k i ∈ R s.t. t 0 -T T h1 θm1 dt ≥ -k 2 1 ∀t ≥ 0 t 0 -T T h2 θm2 dt ≥ -k 2 2 ∀t ≥ 0 t 0 -T T e θs dt ≥ -k 2 3 ∀t ≥ 0 (7)
By combining Eq. 5, 6 and 7, we can straightforward prove the passive behavior of MSf in Eq. 4, that is:

t 0 u T 1 y 1 + u T 2 y 2 dt ≤ c 2 1 + c 2 2 + c 2 3 + k 2 1 + k 2 2 + k 2 3 = d 2 ∀t ≥ 0 (8
d dt V (t) = dH m1 dt + dH m2 dt + dH s dt + u T 1 y 1 + u T 2 y 2 + 0 = -T T h1 θm1 -T T h2 θm2 -T T e θs -P m1 -P m2 -P s (9)
where P m1 , P m2 , P s are the dissipated power at each subsystem. Since the close-loop energy function has no relationship with the dominance factors α, β 1 , β 2 , and according to the condition for passivity of a switched system given by [START_REF] Mahapatra | Stable haptic interaction with switched virtual environments[END_REF], we confirm the conclusion of Proposition 2.

Adaptive Authority Adjustment

In this section, we introduce the Adaptive Authority Adjustment (AAA), which adapts in real-time the authority according to the behavior performances of the trainer.

Adaptive Virtual Boundary

The virtual boundary based is the maximum allowed distance between both master positions. It is used to guide the trainee through the right trajectory. The trainee can move his device freely inside the boundary. The virtual boundary is defined as:

d θm = (θ m1 -θ m2 ) 2 ≤ B ( 10
)
where B defines the maximum allowed distance between the trainer and the trainee. We take the form of B specified in [START_REF] Shahbazi | A dual-user teleoperated system with virtual fixtures for robotic surgical training[END_REF], as a function of the adaptive dominance factor (see the following section). That is,

B = B 0 -k b ln(α a + ) (11)
where B 0 is the maximum allowed distance when the trainer gets full control, i.e. α a = 1. The ln(•) function enables a non-linear behavior which results in the decreasing of the boundary as the trainee gets qualified (i.e. α = 0). k b is a tuning gain and is a very small value to avoid the zero argument case for ln(•), i.e. when α a = 0.

As soon as the condition given in Eq. 10 is violated, a virtual torque will be generated, defined as follows:

T v = -k v (θ m1 -θ m2 ) ( 12
)
where k v acts as a virtual stifness. Notice that in our architecture, this torque won't be transmitted back to the trainee (which is different from [START_REF] Shahbazi | A dual-user teleoperated system with virtual fixtures for robotic surgical training[END_REF]), but used as a criterion for evaluation of the expertise of the trainee.

Adaptive Dominance Factor

The adaptive dominance factor refers to α a , which determines the shared control authority based on the expertise of the trainee. The worse the trainee performs, the higher virtual torque T v is generated. Therefore, we make use of T v as an evaluation index. α a is defined as follows:

α a = 1 -e - T 2 v 2•(T 0 ) 2 (13)
where T 0 is a task based parameter. It is straightforward to conclude that α ranges from 0 to 1, which represents expertise of the trainee ranges from inexperienced to professional.

It is worth to note that the control authority can be switched to any expected value online by the trainer, denoted by α o . We call this is the overrule function. The final decision of α is:

α = α a , overrule = False α o , overrule = True (14)

Experiment

In order to validate our proposed architecture with Adaptive Authority Adjustment method, we conducted the following experiments. The dual-user teleoperation platform is shown in Fig. 3. Two Sensable PHANTOM Omni devices (only their first joints) were employed as the two masters operated by the trainer and the trainee. The devices' kinematic SIMULINK HAPTIC DEVICE Fig. 3 The experiment setup and dynamic parameters are available in [START_REF] Sansanayuth | Teleoperation with inverse dynamics control for phantom omni haptic device[END_REF]. The slave system and control software were implemented using Matlab Simulink. A simulated one d.o.f. joint robot (with mass M s and f s friction coefficient) was set up for the virtual slave.The master IPC controllers adopt the form proposed in [START_REF] Stramigioli | Modeling and IPC Control of Interactive Mechanical Systems: A Coordinate-Free Approach[END_REF]. Note that we applied a different form of IPC controller for the slave, for the purpose of fitting reverse causality interaction with two masters. The explicit equations of the master controllers can be found in [START_REF] Stramigioli | Modeling and IPC Control of Interactive Mechanical Systems: A Coordinate-Free Approach[END_REF]. The one of the slave IPC controller can be obtained in the same way. The AAA parameters are selected as:

B 0 = 0.05 rad, k b = 0.01, k v = 10 N/m, T 0 = 0.707 Nm (15)

AAA Behavior

In the first experiment, we conducted an Adaptive Authority Adjustment. The training goal of this experiment was to move the slave device at target position located at angle 0.3 rad. A virtual obstacle (which may represent a human bone) was set at angle 0.5 rad. The obstacle model was:

T w = 0, θ s < 0.5 rad -k w (θ s -0.5), θ s ≥ 0.5 rad (16)
where k w = 10 N • m/rad is the obstacle stiffness and θ s is the slave robot's joint angle. The hand torques are estimated with a Nicosia observer described in [START_REF] Nicosia | Robot control by using only joint position measurements[END_REF].

The tracking of positions and hand/environment torques are shown in Fig. 4. The experiment time is separated into nine phases, i.e. A-I, given as Table 1.

In figure 4, we can check that the phase A corresponds to the training mode. The authority is overruled by the trainer with α o = 1. The trainer guides the trainee and the slave to the target position. The authority is set to the trainee during phase B. But due to unskilled behavior of the trainee, the slave does not reach the target position. Then, the trainer tries to lead the slave to the right position in phase C. The virtual boundary narrows down. There is a variation of authority during this period. The authority of the trainee over the slave reduced to around 0.4 based on the adaptive distance evaluation method, i.e. Eq. 13. Both the trainer and the trainee feel a torque on their hands during this period. In phase D, the full authority is given back to the trainee again. But he leads the slave beyond the target position. The trainer tries to revise the position by moving his device back a little. But it takes no effect since the trainee is still inside the virtual boundary. Under such cases, the overrule behavior could be adopted to set an expected authority. In this experiment, the overrule authority is set to 1 in phase E. The trainer guides the slave to the right position. In phase F, the trainee gets another chance to perform the task, but this time he leads his device to the virtual obstacle. The slave contacts the obstacle at time 50.9s. Afterwards, the trainer pulls the slave to the opposite direction, to get a certain level of authority. He almost gets full control at time 54.8s. The slave mainly follows the trainer. The trainee feels a bigger resistance torque, that informs him the wrong behavior. After releasing his device, he gets full authority again. At last, he leads the slave to the target position and finishes the task in phase I.

A B C D E F G H I α 1 0 [0,1] 0 1 0 [0,1] ≈1 0 β 1 1 0 1 0 1 0 1 1 0 β 2 1 0 0 0 1 0 0 0 0 α a 0 0 [0,1] 0 1 0 [0,1] ≈1 0 α o 1 0 0 0 1 0 0 0 0 Mode T E G E T E G G E Wall Contact N N N N N N Y N N Overrule Y N N N Y N N N

Transparency

It is worth to explore the force details during the wall contact cases. The transparency is an important issue in teleoperation problems, which indicates whether the user feels the environment properly. In our last experiment, both of the trainer and the trainee experienced a weighted torque (due to shared value of α) compared with the one generated by the obstacle (i.e., T w ) in phase G.

In this experiment, all the configurations keep the same as previously. The result is shown in Fig. 5 The experiment is divided into two phases A and B. During the first phase A, the trainee guides the slave to the obstacle, and gets into contact with it at time 3.3s. Then, the trainee continues his motion in depth until 0.6 rad. From the torque tracking, we could conclude the trainee experiences full obstacle feedback torque. But the trainer doesn't feel it. Afterwards, the trainer tries to move his device towards the same position as the trainee. Then, both the trainer and the trainee feel a full reaction torque generated by the environment, which indicates good transparency.

Conclusions

In this paper, we designed a shared control based dual-user teleoperation system with Adaptive Authority Adjustment (AAA). The adaptive virtual boundary and adaptive dominance factor are introduced for evaluation of the trainee's behavior performance. The authority is adaptively determined base on this evaluation. An overrule function is brought forward to respond some specific cases. The stability of the system is ensured by an energetic modeling which guarantees the passivity of the system while the authority parameters evolve in time. The experiments revealed a good performance and transparency. Future work will extend the number of degrees of freedom and involve time delays.

Fig. 1 A

 1 Fig. 1 A Dual-User Training System

) Proposition 2

 2 The closed-loop system is passive regardless variation dominance factors α ∈ [0, 1].Proof. Firstly, we consider the shared control based architecture. The three Dirac structures form a lossless architecture which can be easily concluded. The energy stored inside them is always zero. Then, by denoting the Hamiltonian function of each subsystem at masters and slave sides (in Port-Hamiltonian framework) with H m1 , H m2 , H s . Considering energy generated by MSf as internal stored part, we set the close-loop energy function as,

Fig. 4

 4 Fig. 4 Positions and torques tracking with variations of authority and virtual boundary

Fig. 5

 5 Fig. 5 Positions and torques tracking

Table 1

 1 The experiment phases Phase

Acknowledgements

The authors acknowledge the financial support of the China Scholarship Council (CSC) Scholarship.


E Humbert

L Molinet

OPTIMAL TRANSPORTATION BETWEEN HYPERSURFACES BOUNDING SOME STRICTLY CONVEX DOMAINS

Let M, N be two smooth compact hypersurfaces of R n which bound strictly convex domains equipped with two absolutely continuous measures µ and ν (with respect to the volume measures of M and N ). We consider the optimal transportation from µ to ν for the quadratic cost. Let (φ : m → R, ψ : N → R) be some functions which achieve the supremum in the Kantorovich formulation of the problem and which satisfy

Define for y ∈ N ,

In this short paper, we exhibit a relationship between the regularity of ϕ 2 and the existence of a solution to the Monge problem.

Let M and N be two smooth compact hypersurfaces of R n , n ≥ 2, which are the boundary of some strictly convex domains. In the present paper, we study the existence of a solution of Monge Problem when considering the optimal transport with quadratic cost between two measures µ and ν respectively supported in M and N . This situations has been already studied: see [START_REF] Gangbo | Shape recognition via Wasserstein distance[END_REF]. In the whole paper, we assume that µ and ν have the form µ = f (x)dv(x) and ν = g(y)dv(y) where f, g are some non-zero nonnegative continuous functions on M and N and where dv stands for the volume measures on M and N . The quadratic cost is defined for all x, y ∈ R n by c 2 (x, y) := 1 2 |x -y| 2 . Here, | • | denotes the standard norm associated to the canonical scalar product of R n . For all x, y ∈ R n , the scalar product of x and y will be denoted by x • y. The standard formulation of the optimal transport from µ to ν for the quadratic cost is T 0 := inf π∈Π ′ (µ,ν)

I ′ 0 (π)
where Π ′ (µ ′ , ν ′ ) is the set of probabilily measures π(•,

•) on R n × R n such that π(R n , •) = ν and π(•, R n ) = µ
and for all π ∈ Π ′ (µ ′ , ν ′ ),

I ′ 0 (π) := R n ×R n c 2 (x, y)dπ(x, y).
As easily checked, this is an equivalent formulation to write By the Monge-Kantorovich duality (see for instance, [START_REF] Kantorovich | On the translocations of masses, C.R[END_REF], [START_REF] Villani | Topics on transportations[END_REF]), one has

T 0 = sup (ϕ,ψ)∈Ω J 0 (ϕ, ψ) (0.2)
where Ω is the set of couples of functions (ϕ, ψ)

∈ C 0 (M ) × C 0 (N ) such that ϕ(x) + ψ(y) ≤ c 2 (x, y)
for all (x, y) ∈ M × N and where

J 0 (g, h) = M g(x)dµ(x) + N h(y)dν(y). for all (g, h) ∈ C 0 (M ) × C 0 (N ).
Actually, in many situations, one can also show the uniqueness of π (see [START_REF] Ahmad | Optimal transportation, topology and uniqueness[END_REF]). It is standard to prove that (see for instance [START_REF] Ahmad | Optimal transportation, topology and uniqueness[END_REF] for references):

(1) the infimum in (0.1) is attained by some probability measure π, which is called a transference plan; (2) the supremum in (0.2) is attained by some couple of functions (ϕ, ψ) which satisfy for all x ∈ M , y ∈ N :

(0.3) ψ(y) = inf z∈M c 2 (z, y) -ϕ(z) ; ϕ(x) = inf z∈N c 2 (x, z) -ψ(z)
In the whole paper, if η : M → R, we will note for all y ∈ N η * (y) = inf x∈M c 2 (x, y) -η(x) . (0.4)

In the same way, if η : N → R, we will note for all x ∈ M η * (x) = inf y∈N c 2 (x, y) -η(y) , (0.5) so that ϕ * = ψ and ψ * = ϕ.

An important question about (0.1) is the following : are the transference plans associated with (0.1) supported in a graph ? Indeed, a positive answer to this question would ensure the existence of a solution to the famous Monge problem (see, for instance, [START_REF] Villani | Topics on transportations[END_REF] for some explanations). Unfortunately, the answer is no in its full generality. Gangbo and McCann [3] could construct some counter examples. Even worse: numerical computations indicate that this is not true either in the simplest situation when M = N = S 1 (for n ≥ 1, S n denotes the unit sphere of R n+1 ) and when µ and ν have smooth positive densities (see [START_REF] Chiappori | Hedonic price equilibria, stable matching, and opitmal transport: equivalence, topology and uniqueness[END_REF]).

In this paper we try to give some simple criteria that would imply a positive answer. Before, stating our result, we need to introduce some definitions.

For any fonction Θ : M → R, we set for all y ∈ N

Θ 2 (y) = sup x∈M c 2 (x, y) -Θ(x) . (0.6)
and in the same way, if Θ : N → R, we set for all x ∈ M Θ 2 (x) = sup y∈N c 2 (x, y) -Θ(x) . (0.7) While, as proven is [START_REF] Gangbo | Shape recognition via Wasserstein distance[END_REF], the function ϕ is always C 1 , the function ϕ 2 has no reason to be C 1 in general but surprisingly, its regularity is directly related to the question above. More precisely, our main result is Theorem 0.1. For all y ∈ N , define Θ y : M → R by

Θ y (x) = c 2 (x, y) -ϕ(x)
so that, for y ∈ N , ϕ * (y) = inf M Θ y and ϕ 2 (y) = sup M Θ y . Then, the following assertions are equivalent:

(1) ϕ 2 is C 1 ;

(2) for all y ∈ N , the function Θ y has exactly two critical points: its minimum and it maximum. If one of the assertions above is true then ϕ 22 = ϕ * * = ϕ. Moreover, the support of π is contained in a graph.

The idea of the proof is as follows. Let Γ be the set of points x ∈ M which are the maximum of a function Θ y for some y ∈ N . There is then two crucial observations:

(1) If (x, y) belongs to the support of π and if x ∈ Γ, then y is unique. This implies that if Γ = M then the support of π is contained in a graph. (2) Let x ∈ Γ, y ∈ N such that x is the maximum of Θ y . Then, y is unique.

This allows to define a map T : Γ → N such that T (x) = y. The main argument of the proof is to show that under the assumptions of Theorem 0.1, T is actually a homeomorphism, which implies that Γ = M and allows to conclude. Even if assumptions 1) or 2) are not easy to check, we think that this theorem gives a new point of view, that we hope useful, to this Monge problem. For convenience of the reader, we stated all the results which seem of particular interest to us in Propositions 1.3, 1.4, 1.6. Theorem 0.1 is a direct consequence of these propositions.

1. Proof of Theorem 0.1 1.1. Notations and Preliminaries. We keep the notations of the introduction: (ϕ, ψ) is a couple of functions maximizing the problem (0.2). By Gangbo and McCann [3], these functions are C 1 . Indeed, in their paper Section 3, they show that the convex functions they study are tangentially differentiable and that these tangent differentials are continuous on M and N . Here, the function we consider are the same functions restricted to M and N and are hence C 1 . Notice that the proof of this fact is far to be obvious. In addition, the functions ϕ, ψ satisfy ϕ * = ψ and ψ * = ϕ. We recall that for all y ∈ N , we defined Θ y :

M → R by Θ y (x) = c 2 (x, y) -ϕ(x).
In the same way, if x ∈ M , we define Θ

x : N → R by Θ x (x) = c 2 (x, y) -ψ(x).
For x ∈ M , y ∈ N , we introduce the sets:

Ω x := {z ∈ N /θ x (z) = inf z ′ ∈N θ x (z ′ ) = ϕ * (z) = ψ(z)} and Ω y := {z ∈ M /θ y (z) = inf z ′ ∈M θ y (z ′ ) = ψ * (z) = ϕ(z)}.
Note that, by compacity of M and N , these sets are non empty. Note also that

Ω x := {z ∈ N /ϕ(x)+ψ(z) = c 2 (x, z)} and Ω y := {z ∈ M /ϕ(z)+ψ(y) = c 2 (z, y)} which has the immediate consequence that y ∈ Ω x ⇔ x ∈ Ω y ⇔ ϕ(x) + ψ(y) = c 2 (x, y). (1.1)
Now, proving that the support of π is contained in a graph of a continuous preserving map α : M → N (resp. α : N → M ) is reduced to proving that for all x ∈ M (resp. y ∈ N ), the set Ω x (resp. Ω y ) contains exactly one point. Indeed, by (0.1) and (0.2), one has

M×N c 2 (x, y)dπ(x, y) = M ϕ(x)dµ(x) + N ψ(y)dν(y)
which can be rewritten, since the marginals of π are µ and ν, by

M×N (c 2 (x, y) -ϕ(x) -ψ(y)) dπ(x, y) = 0.
Since c 2 (x, y) -ϕ(x) -ψ(y) ≥ 0, one has identically on the support of π:

c 2 (x, y) = ϕ(x) + ψ(y)
and hence x ∈ Ω y or y ∈ Ω x .

For any y ∈ N we denote by n N (y) the unitary normal outside vector to N at y and we define the line D y by D y = y -∇ψ(y) + span(n N (y)) .

Similarly, for x ∈ M we define the line D x by

D x = x -∇ϕ(x) + span(n M (x)) .
An easy computation of the derivative of Θ y and Θ x shows that if x ∈ M, y ∈ N , then

y ∈ D x ⇔ ∇Θ y (x) = 0 and x ∈ D y ⇔ ∇Θ x (y) = 0. (1.2)
Finally, we will use several times the following Lemma: Lemma 1.1. For all x ∈ M , y ∈ N , the functions Θ x and Θ y are never constant.

Proof. Assume for instance that Θ y is constant. Then for any x ∈ M , x ∈ Ω y and hence, by (1.1), y ∈ Ω x . By (1.2), x ∈ D y which implies that M is contained in the right line D x . This is impossible and Lemma 1.1 follows.

1.2. Properties of ϕ 2 . In the proof on Theorem 0.1, we will use some basic properties of ϕ 2 . Many of them are very standard. We first recall its definition:

ϕ 2 (y) = sup x∈M c 2 (x, y) -ϕ(x) .
For convenience, for any y ∈ N , we will denote by Ω 2 y the set of points of M achieving the maximum in the definition of ϕ 2 . We collect the properties we will need in the following Proposition: Proposition 1.2.

(1) For all x ∈ M , ty ∈ N , one has ϕ(x)

+ ϕ 2 (y) ≥ c 2 (x, y) with equality if and only if x Ω 2 y ; (2) ϕ 22 ≤ ϕ; (3) ϕ 2 is Lipschitz; (4) ϕ 222 = ϕ 2 ;
(5) Let y ∈ M . Assume that there is only one point such x y such that

ϕ 2 (x) = c 2 (x y , y) -ϕ(x y )
i.e. the supremum in the definition of ϕ 2 is attained at only one point, then ϕ 2 is differentiable at y.

Proof. We start by proving 1). Let x ∈ M and y ∈ N . It holds that

ϕ(x) + ϕ 2 (y) = ϕ(x) + sup z∈M c 2 (z, y) -ϕ(z) ≥ ϕ(x) + (c 2 (x, y) -ϕ(x)) = c 2 (x, y).
The inequality above becomes an equality if and only if x ∈ Ω 2 y . This proves 1).

Let us now deal with 2). Let x ∈ M . By definition:

ϕ 22 (x) = sup y∈N (c 2 (x, y) -ϕ 2 (y)).
By compacity of N , there exists y x ∈ M such that

ϕ 22 (x) = c 2 (x, y x ) -ϕ 2 (y x ). (1.3)
By definition, one also have

ϕ 2 (y x ) = sup z∈M (c 2 (z, y x ) -ϕ(z)).
and, setting z = x, one has

ϕ 2 (y x ) ≥ c 2 (x, y x ) -ϕ(x).
Together with (1.3), this gives 2).

Let us prove 3). Let y, z ∈ M , x y ∈ Ω 2 y and x z ∈ Ω 2 z . We prove that 1 2 (z + y -2x y ) • (z -y) ≥ ϕ 2 (z) -ϕ 2 (y) ≥ 1 2 (z + y -2x z ) • (z -y).
(1.4)

The definition of Ω 2 z implies that

ϕ 2 (z) = c 2 (x z , z) -ϕ(x z ).
The construction of ϕ 2 implies that

ϕ 2 (y) ≥ c 2 (x z , y) -ϕ(x z ).
Observing that

1 2 (z + y -2x z ) • (z -y) = c 2 (x z , z) -c 2 (x z , y),
this provides the right inequality of (1.4). The left inequality is proven in the same way. Now, observe that since M, N are compact, there exists a constant C > 0 independant of y, z such that

1 2 |z + y -2x z | ≤ C and 1 2 |z + y -2x y | ≤ C.
Using that |z-y| is less than the geodesic distance on N , we immediatly deduce that ϕ 2 is lipschitz. Note that this implies that ϕ 2 is continuous and by Rademacher's Theorem, is differentiable almost everywhere.

We now prove 4). By Point 2) ϕ 22 ≤ ϕ. In particular, for all y ∈ N ,

ϕ 222 (y) = sup x∈M (c 2 (x, y) -ϕ 22 (x)) ≥ sup x∈M (c 2 (x, y) -ϕ(x)) = ϕ 2 (y).
For all x ∈ M , y ∈ N , we also have as in Point 1)

ϕ 22 (x) + ϕ 2 (y) ≥ c 2 (x, y).
Then as in Point 2), ϕ 222 = (ϕ 2 ) 22 ≤ ϕ 2 . This shows 4).

Let us finish by proving 5). Let y ∈ M and assume that Ω 2 y is reduced to one point x. Let (z k ) be a sequence of points of N tending to y. For all k, choose x k ∈ Ω 2 z k . By compacity of M , one can assume that x k converges to some x ′ ∈ M . The definition of Ω 2

z k and Point 1) implies that

ϕ(x k ) + ϕ 2 (z k ) = c 2 (x k , z k ).
By continuity of ϕ and ϕ 2 , we obtain as z k tends to y,

ϕ(x ′ ) + ϕ 2 (y) = c 2 (x ′ , y)
which proves that x ′ ∈ Ω 2 y and hence x ′ = x Using (1.4), we have

1 2 (z k -y) • (z k + y -2x k ) ≥ ϕ 2 (z k ) -ϕ 2 (y) ≥ 1 2 (z k -y) • (z k + y -2x). (1.5)
Until the end of the proof, the notation o k will stand for a term which is o(|z k -y|). Since x k tends to x, we have

x k • (z k -y) = x • (z k -y) + o k .
When z k is close to y, z k -y = P y (z k -y) + o k , where P y denotes the orthogonal projection onto the tangent space T y N . Coming back to (1.5), we obtain that

1 2 P y (z k -y) • (z k + y -2x) + o k ≥ ϕ 2 (z k ) -ϕ 2 (y) ≥ 1 2 P y (z k -y) • (z k + y -2x) + o k .
Since P y is self-adjoint, this yields

1 2 (z k -y) • P y (z k + y -2x) + o k ≥ ϕ 2 (z k ) -ϕ 2 (y) ≥ 1 2 (z k -y) • P y (z k + y -2x) + o k .
Noticing that

lim k P y (z k + y -2x) = 2P y (y -x)
and setting v := P y (y -x), it follows that

(z k -y) • v + o k ≥ ϕ 2 (z k ) -ϕ 2 (y) ≥ (z k -y) • v + o k .
This ensures that for any sequence z k tending to y, one can extract a subsequence such that

ϕ 2 (z k ) -ϕ 2 (y) -v • (z k -y) = o k .
Since when z k tends to y, (z k -y) is equivalent to the geodesic distance from y to z k in N , this proves that ϕ 2 is differentiable and that ∇ϕ 2 (y) = v which completes the proof of Proposition 1.2.

1.3. Proof of Theorem 0.1. We define

Γ := {x ∈ M / ∃y ∈ N , θ y (x) = sup x∈M θ y (x) = ϕ 2 (y)}
The first observation is the following:

Proposition 1.3. (Properties of the set Γ) (1) The set Γ is closed; (2) If x ∈ Γ then #Ω x = 1.
In particular, if Γ = M , the support of π is contained in a graph. (3) For all x ∈ Γ, one has ϕ 22 (x) = ϕ(x) = ϕ * * (x).

Proof. Let us first show that Γ is closed: let (x n ) ⊂ Γ be such that x n → x in M . There exists (y n ) ⊂ N such that for all n ∈ N, Θ yn (x n ) = max M Θ yn . Now, let (y n k ) be a subsequence of (y n ) that converges to some y ∈ N . Such subsequence exists by compactness of N . On the one hand, by the continuity of the map z → max M Θ z , we obtain that Θ yn k (x n k ) = max M θ yn → max M Θ y . On the other hand, we have Θ yn k (x n k ) → Θ y (x). Therefore Θ y (x) = max M Θ y and thus x ∈ Γ. This proves that Γ is closed.

Les us come to the proof of the second part of the statement. Let x ∈ Γ. By definition of Γ, there exists y 1 ∈ N such that x is a maximum for Θ y1 . Assume that #Ω x ≥ 2 and let also y 2 , y 3 ∈ Ω x , y 2 = y 3 . Then, x ∈ Ω yi for i = 2, 3 and then x is a minimum of Θ yi i = 2, 3. By Equation (1.2), y 1 , y 2 , y 3 ∈ D x . Since N is the boundary of a strictly convex domain, D x intersects N at at most two points. Since y 2 = y 3 , we must have y 1 = y 2 or y 1 = y 3 . Let us assume for instance that y 1 = y 2 . This means that x is a minimum as well as a maximum of Θ y1 which forces Θ y1 to be constant on M . By Lemma 1.1, this cannot occur.

Let us prove now the third part of the statement. For all x ∈ M , it holds that ϕ * * (x) = ψ * (x) = ϕ(x). By Proposition 1.2, ϕ 22 ≤ ϕ. It thus remains to prove that if x ∈ Γ then ϕ 22 (x) ≥ ϕ(x). For such x, there exists y ∈ N such that

|x -y| 2 2 -ϕ(x) = ϕ 2 (y) = ϕ 222 (y) = sup z∈M |z -y| 2 2 -ϕ 22 (z) ≥ |x -y| 2 2 -ϕ 22 (x) ≥ |x -y| 2 2 -ϕ(x)
Here, we used the fact that ϕ 222 = ϕ 2 , which is proven in Proposition 1.2. We then must have equality in all the inequalities above which implies ϕ 22 (x) ≥ ϕ(x).

We are now in position to define

T : Γ → N x → T (x)
such that Θ T (x) (x) = sup M Θ T (x) . Then, Proposition 1.4. (Properties of the mapping T ) T is a well defined continuous map which is surjective. Moreover, for all x ∈ Γ, the outer unit normal vector to M at x and to N at T (x) satisfy:

n M (x) • n N (T (x)) < 0.
Proof. To show that T is well defined, we have to show that for all x ∈ Γ, there exists one and only one y ∈ N such that Θ y (x) = sup M Θ y . The existence of such y is ensured by the fact that x ∈ Γ. Now, assume that y 1 and y 2 satisfy this relation. Then, y 1 and y 2 must belong to the right line D x (see Relation (1.2)). Moreover, since Ω x is never empty, let y 3 ∈ Ω x then again y 3 ∈ D x . Notice that y 3 is distinct from y 1 and y 2 otherwise Θ y1 is constant which is prohibited by Lemma 1.1. Since D x intersects N at at most two points, y 2 and y 3 must be equal. This prove that T is well defined.

The fact that T is surjective is obvious: if y ∈ N , we choose x ∈ M , which is compact, such that x is a maximum of Θ y . The definition of T implies that T (x) = y.

Let us show the continuity of T . Let (x n ) ⊂ Γ such that x n → x in Γ. By construction we have θ T (xn) (x n ) = max M θ T (xn) . Now, let (x n k ) be a subsequence of (x n ) such that T (x n k ) converges to some y ∈ N . Obviously, proceeding as in the proof of Proposition 1.3, Θ y (x) = max M Θ y and thus y = T (x). Therefore T (x) is the unique adherence point of the sequence (T (x n )) which ensures that T (x n ) → T (x) and proves the continuity of T .

Let us prove the last part of the statement of Proposition 1.4. Let x ∈ Γ and set y = T (x). Since x a maximum for Θ y , by (1.2), y ∈ D x . Let also y ′ be a minimum for Θ x i.e. y ′ ∈ Ω x . By (1.1), x is also a minimum for Θ y ′ which implies, by (1.2), that y ′ ∈ D x . Moreover, y = y ′ since otherwise this would imply that Θ y is constant which would contradict Lemma 1.1. Since N bounds a strictly convex domain, D x intersects N at at most two points which forces to have

D x ∩ N = {y, y ′ }.
Note that n M (x) • n N (y) = 0 since otherwise this would imply that D x is tangent to N and thus intersects N at only one point. Note also that among n M (x) • n N (y), n M (x) • n N (y ′ ), one is positive and the other one is negative. It then suffices to prove that n M (x) • n N (y ′ ) > 0. This fact is proven in [START_REF] Gangbo | Shape recognition via Wasserstein distance[END_REF]: with their notations, t + (x) = y ′ satisfies the desired relation. Since the proof is easy we repeat it here for sake of completeness. Let x ′ ∈ Ω y . Then, x ′ = x otherwise we would get that Θ x is constant. The monotonicity property asserts that

(x -x ′ ) • (y -y ′ ) ≤ 0. (1.6) Indeed, since x ∈ Ω y ′ and x ′ ∈ Ω y , we have ϕ(x) + ψ(y ′ ) = c 2 (x, y ′ ) and ϕ(x ′ ) + ψ(y) = c 2 (x ′ , y).
Moreover, by definition of (ϕ, ψ),

ϕ(x) + ψ(y) ≤ c 2 (x, y) and ϕ(x ′ ) + ψ(y ′ ) ≤ c 2 (x ′ , y ′ ).
These relations imply that

c 2 (x ′ , y) + c 2 (x, y ′ ) ≤ c 2 (x, y) + c 2 (x ′ , y ′ ).
Coming back to the definition of c 2 , we obtain Relation (1.6). Note that since y, y ′ ∈ D x , the definition of D x tells us that -→ yy ′ = λn M (x) for some λ = 0. If we assume that n M (x) • n N (y ′ ) < 0 and n M (x) • n N (y) > 0 then the fact that N bounds a strictly convex domain forces λ < 0. Therefore, Relation (1.6) becomes (x -x ′ ) • n M (x) ≤ 0 which is impossible since x = x ′ and since M bounds a strictly convex domain. This ends the proof of Proposition 1.4.

Note that the preceding proof shows that Lemma 1.5. For all x ∈ Γ, D x ∩ N has exactly two distinct points y, y ′ such that x is a maximum for Θ y and a minimum for Θ y ′ . Moreover n M (x) • n N (y) < 0 and n M (x) • n N (y ′ ) > 0.

Proposition 1.6. The following assertions are equivalent:

(1) ϕ 2 is C 1 ;

(2) T is injective;

(3) for all y ∈ M , Θ y has exactly two critical points. If one of these assertions is true, then Γ = M .

Proof. Let us show that 1) implies 2). Assume ϕ 2 is C 1 . For all y ∈ N , define the right line D 2 y = y -∇ϕ 2 (y) + span(n N (y)) . An straightforward computation shows that for x ∈ M ,

  µ, ν) is the set of probabilily measures π(•, •) on M × N such that π(M, •) = ν and π(•, N ) = µ and for all π ∈ Π(µ, ν), I 0 (π) := M×N c 2 (x, y) dπ(x, y).

x ∈ D 2 y

 2 ⇐⇒ y is a critical point of Θ 2 (•) := c 2 (x, •) -ϕ 2 (•). (1.7) Let x ∈ Γ.Then x is a maximum of the function Θ y i.e. ϕ 2 (y) = Θ y (x) for some y ∈ N . Now, using the fact that ϕ 222 = ϕ 2 (see Proposition 1.2), one also hassup z∈M (c 2 (z, y) -ϕ 22 (z)) = ϕ 222 (y) = ϕ 2 (y) = Θ y (x). (1.8)On the other hand, by Proposition 1.3, ϕ(x) = ϕ 22 (x) and hence Θ y (x) = c 2 (x, y) -ϕ 22 (x).

Together with (1.8), we get that x is a maximum for z → c 2 (z, y) -ϕ 22 (z). Obviously, mimicking what was done to get (1.1), we also have that y is a maximum for the function of N z → c 2 (x, z) -ϕ 2 (z). Relation (1.7) then leads to x ∈ D 2 y . Assume now that T (x) = T (x ′ ). We then obtain that x, x ′ ∈ D 2 T (x) . Moreover, Lemma 1.5 also establishes that n M (x) • n N (T (x)) < 0 and n M (x ′ ) • n N (T (x)) < 0 which forces x and x ′ to be equal since M bounds a strictly convex domain. This proves that T is injective.

Let us prove that 2) implies 3). At first, we show that under assumption 2), Γ = M . From Propositions 1.3 and 1.4, T : Γ → M is now bijective, continuous. Since Γ is compact, it sends closed sets on closed sets and thus T is actually a homeomorphism. This ensures that Γ = M . Indeed, M and N bound some convex domains in R n and are then diffeomorphic to S n . We just proved that Γ is a closed set of M homeomorphic to N and hence to S n . To prove that Γ = M , it suffices to notice that it is open in M and to conclude by the fact that M is connected. This follows from the Jordan-Brouwer separation theorem (see for instance [START_REF] Greenberg | Algebraic Topology, a first course[END_REF], Corollay (18.9) Page 110).

We are now in position to prove 3). A consequence of Lemma 1.5 and the fact that

We already noticed that each Ω x (x ∈ M ) is reduced to a point (this comes from Proposition 1.3 and the fact that Γ = M ) but this is also true for Ω y for any y ∈ N . Indeed, if x, z are some minima for Θ y , they must belong to the right line D y and they must satisfy (1.9) which is only possible if x = z. So, let y ∈ N and let x be a minimum of Θ y and x ′ be a maximum of Θ y . Assume that Θ y has some other critical point x ′′ . Then, y ∈ D x ′′ . By Lemma 1.5, x ′′ must be a maximum or a minimum of Θ y . The argument above tells us that x ′′ cannot be a minimum. But x ′′ cannot be either a maximum: it would imply T (x) = T (x ′′ ) which is impossible since we assumed T to be injective. This proves that the only critical points of Θ y are x, x ′ . Finally, we prove that 3) implies 1). Assume that Θ y has only two critical points for any y ∈ N . Then, for all y, Ω 2 y is reduced to one point (otherwise, Θ y has at least two maxima and one minimum). From Point 5) of Proposition 1.2, we obtain that ϕ 2 is differentiable on N . It remains to prove that its differential is continuous. Let (y k ) be a sequence of points in N tending to some y. Let x k ∈ Ω 2 y k and x ∈ Ω 2 y . Let x ′ be an adherence point of (x k ). Since x k is a maximum of z → c 2 (z, y k ) -ϕ(z), passing to the limit, x ′ is a maximum of z → c 2 (z, y) -ϕ(z). This implies that x ′ ∈ Ω 2 y , which is reduced to one point. Hence x ′ = x which shows that x k tends to x. In particular, the sequence of right lines (D 2 y k ) (which are orthogonal to the tangent spaces T y k N and which are such that x k ∈ D 2 y k ) has a limit position which is D 2 y . The definition of these right lines gives the continuity at y of the differential of ϕ 2 . This ends the proof of Proposition 1.6. Theorem 0.1 is a direct consequence of Propositions 1.3, 1.4 and 1.6.


Kessi Louisa
email: louisa.kessi@liris.cnrs.fr

Frank Lebourgeois
email: franck.lebourgeois@liris.cnrs.fr

Christophe Garcia
email: christophe.garcia@liris.cnrs.fr

Louisa Kessi

Jean Duong
email: jean.duong@liris.cnrs.fr

AColDPS :Robust and Unsupervised Automatic Color Document Processing System

Keywords: Document image analysis, color processing, business document, mathematical morphology, color morphology

This paper presents the first fully automatic color analysis system suited for business documents. Our pixelbased approach uses mainly color morphology and does not require any training, manual assistance, prior knowledge or model. We developed a robust color segmentation system adapted for invoices and forms with significant color complexity and dithered background. The system achieves several operations to segment automatically color images, separate text from noise and graphics and provides color information about text color. The contribution of our work is Tree-fold. Firstly, it is the usage of color morphology to simultaneously segment both text and inverted text. Our system processes inverted and non-inverted text automatically using conditional color dilation and erosion, even in cases where there are overlaps between the two. Secondly, it is the extraction of geodesic measures using morphological convolution in order to separate text, noise and graphical elements. Thirdly, we develop a method to disconnect characters touching or overlapping graphical elements. Our system can separate characters that touch straight lines, split overlapped characters with different colors and separate characters from graphics if they have different colors. A color analysis stage automatically calculates the number of character colors. The proposed system is generic enough to process a wide range of images of digitized business documents from different origins. It outperforms the classical approach that uses binarization of greyscale images.

INTRODUCTION

Color document processing is an active research area with significant applications. In recent years, there has been an increasing need for systems which are able to convert pre-printed color documents into digital format automatically. Most of the time, the color image is converted into a greyscale image. However, the performance decreases when the segmentation fails. Nowadays, companies have to deal with huge volumes of administrative color documents such as invoices, forms, and letters and so on. Indeed, some companies can have to cope with dithering documents, complex color background and linear color variations, which amounts to not knowing if text is darker or lighter compared to the background, highlighting regions, corrective red overload on black text and not uniform color text/graphics overlapping. Indeed, some dithered documents may not lead to a correct automatic analysis. Smoothing most often permits to reduce dithering significantly but can also seriously damage the text. Therefore, the color information is significant. Then, a color-based segmentation could improve the process.

Related Work

As far as the authors know, there are only few works about the use of the color for document analysis. The only referenced work for color documents come from [START_REF] Bottou | Djvu: analyzing and compressing scanned documents for internet distribution[END_REF] for the DjVu compression. In the work of [START_REF] Karatzas | Color text segmentation in web images based onhuman perception Image and Vision Computing[END_REF], (Y. [START_REF] Peng | Color-based clustering for text detection and extraction in image[END_REF] and [START_REF] Jung | Hybrid approach to efficient text extraction in complex color images[END_REF]) localization of colored text is described. OCR of colored characters is presented in [START_REF] Badekas | Text segmentation in color documents[END_REF]. Most of the research on color documents considers the classification as an essential pre-processing step to any analysis. This facilitates the extraction of the connected components by a simple growing region. The work focuses mostly on-pixel classification approaches to reduce the number of colors found. The pixel classification consists of assigning each pixel of the image to the color class layer according to its colorimetric appearance. In this context, [START_REF] Ouji | Chromatic /achromatic separation in noisy document images[END_REF] introduce a new pseudo-saturation measure to separate color layers and monochrome layer. The author segments text colors and background by selecting maxima in the hue histogram. However, this global analysis of the image cannot make the difference between text colors and background color. Moreover it works only for cleaned images. This method is not operating for business document images. (Ait [START_REF] Younes | Color Image Profiling Using Fuzzy Sets[END_REF] describe the color thanks to fuzzy sets in order to classify images based on dominant colors. However, they dealing with a fixed number of colors which is not optimized for documents containing just a few colors. [START_REF] Carel | Dominant Color Segmentation of Administrative Document Images by Hierarchical Clustering[END_REF] propose a hierarchical clustering based approach to extract dominant color masks of administrative documents. Moreover, this approach was evaluated on a relatively small base. Therefore, they need to provide more extensive quantitative analysis of the process both in terms of its effectiveness and computational requirements. On the other hand, this method requires user interaction for setting threshold parameters order to decide what a dominant color is or not. This approach works only for a specific category of images and is very sensitive for noises. This paper addresses the most challenging problem of color morphology. We use this theory to develop the first robust unsupervised Automatic Color Document Processing System pixel-based approach.

Motivation

In this paper, we present an automatic system which segments color characters from business documents and especially from forms and invoices. Our objective is achieved if all color characters are correctly segmented from the background, using an automatic procedure without any information provided by the user. Contrary to previous works, we develop the first full data-driven pixel-based approach which doesn't need any priori information such as the number of text colors or any training or manual assistance. The paper is organized as follows. Section 2 presents the color morphology fundamentals and in Section 3 there is a detailed description of our approach. Results are discussed in Section 4. In Section 5 conclusions are drawn.

COLOR MATHEMATICAL MORPHOLOGY

The theory of Mathematical Morphology [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF] consists of quantitatively describing the geometric structures present in the image, and offers a wide range of tools [START_REF] Soille | Morphological image analysis: Principles and applications[END_REF]. Motivated by the recent researches on extension of morphological operations to color images [START_REF] Chanussot | Total ordering based on space filling curves for multivalued morphology[END_REF], we have decided to employ color mathematical morphology tools to achieve color document images segmentation in a flexible and fast manner.

Our system uses the morphological convolution (1) and the lexicographic order to encode color vectors into a scalar.The morphological convolution transforms a binary image I into an image I G by taking the largest or smallest value of I + V on the domain of definition Dv of a neighborhood V.

I G (x) =Min or Max { I(x+k)+V(k) } ∀ k∈D V ∀ x∈X (1)
By using the interleaved bits, color morphology in 3 dimensional spaces can be substituted efficiently by a scalar classical morphology (Chanussot et al.1998) popularized by (Aptoula et al., 2009) show that the scalar morphology by using the encoding scheme illustrated in Figure 2 avoids pseudo colors apparition. We reduce the dissymmetry between color components by rotating the sequence of RGB.

Figure 2: Color coding in scalar by using interleaved bit and rotation of the sequence of RGB.

OUR PROPOSITION

Figure 3 illustrates the main steps of the proposed system. Each step will be detailed in the next sections following the organisation of the paper.

Figure 3: illustrates the overall scheme of AColDPS.

Color Clustering

The spatial MeanShift originally introduced by [START_REF] Comaniciu | MeanShift: A Robust Approach toward Feature Space Analysis[END_REF] demonstrates that a densitybased clustering is efficient for color clustering and reduces the complexity of the original MeanShift algorithm by introducing the spatial coordinates into the color vector. Applied to color documents, the spatial Mean Shift requires a complex fusion step to restore the continuity of the characters. The Fast Integral MeanShift proposed by (Lebourgeois et al., 2013)

Segmentation of Thin Colored Objects by Using Color Morphology

This step consists to generate a binary image of thin colored objects. It differs from the classical binarization of the luminance by an adaptive thresholding approach. For images which use colors having almost the same luminance, the thresholding of the luminance fails. We use the mathematical morphology because it can extract objects according to geometrical measures. Thin objects can be segmented by a classical Top-Hat transform. The closing of an image I is the dilation followed by an erosion of the image with the same structural element (2). It enlarges the lighter foreground and removes the thin objects which are darker than the background (figure 5c). The radius of the structural element B measures the thickness of the object to remove. The Black-Top-Hat (3) of an image I consists of make the difference between the closing image and the original image I, in order to highlight all thin colored objects which are darker than the background in luminance (figure 5d).

If we assume that all characters use colors which are darker than the background, in luminance, a Black-Top-Hat is efficient to extract all colored characters from any colored background. By using the interleaved bits order explained in [START_REF] Chanussot | Total ordering based on space filling curves for multivalued morphology[END_REF] To extract all colored characters even with fading ink, we apply an adaptive thresholding like Sauvola thresholding. In our case, we use the variable adaptive thresholding windows (Gaceb et al., 2013) which compute the best window size of the Sauvola The difference between our thresholding and the classical Sauvola with fixed window size is noticeable on dithered images or images having noise and large objects. However, Sauvola thresholding can be used without significant loss of performance in the case of the segmentation of the Black-Top-Hat images because the size of objects cannot exceed twice the size of the structural elements. In this case the variable window size of the Sauvola thresholding (Gaceb et al., 2013) manages to reduce noise from the images.

In the domain of business documents, we cannot assume that text is darker than the background in luminance. Invoices and forms present inverted text which is brighter than the background. This inverted text is important for the recognition of business There is no simple binary operation which separate inverted and not inverted text. The local dominant colors bring a solution to segment simultaneously inverted and non-inverted text by morphology. This operation allows to measure the color of the background whether the text is inverted or not. The precision of the dominant color image is not important. In order to make a precise adjustment to the original image we dilate or erode the dominant color image with the original image. Among all possible existing methods, to compute the dominant color we have chosen the median filtering with a large radius since its complexity has been seriously reduced and can be calculated in constant time (Perreault, 2007) whatever the size of the window.

Figure 6b shows the result of the median with radius 15 or a window size of 30 on image in figure 6a. The dominant color image is a coarse representation which we refine by applying a conditional erosion and dilation with the original image.

In classical morphology theory for binary image, the conditional dilation CD B M (X) of a subset X by a structural element B conditioned to a mask M is equal to the intersection between the Dilated of X with the binary mask M (6). Accordingly, the conditional erosion CE B M (X) of a subset X by a structural element B conditioned to a mask M is equal to the intersection between the complementary of the erosion of X with the binary mask M [START_REF] Gaceb | Adaptative Smart-Segmentation Method for Images of Business Documents[END_REF].

CD B M (X) = Dilate (X) ∩M (6) CE B M (X) = (Erode (X)) c ∩M (7)
Applied to greyscale images or to scalar color images by using interleaved bits of the three color channels, the conditional dilation CD B M (X) of a scalar image X under condition of a scalar image M is equal to the minimum of the dilation of X and the image M (8). By symmetry, the conditional erosion CE B M (X) is obtained by the maximum between M and the erosion of X (9). Figure 6e and figure 6f show the positive and the negative parts of thin colored objects, respectively. Both positive and negative images contain a strong dithering of the background in the blue column (Figure 6h). The final result is obtained by taking the min of the adaptive thresholding of the positive and the negative image (figure 6g). The radius of the median in order to find the local dominant colors depends on the size of the text to segment.

The window size of the median operator must be larger than the maximum text height. For color images with resolution of 300 dpi of resolution, the maximal height of text does not exceed 25 pixels.

The size of the window for the median filtering must be larger than this value. In order to have more margin, we chose a window size larger than 30 or a radius larger than 15.

Separation of Text from Graphics, Image Noise and Dithered Background

This step does not use any connected components extraction or analysis. It is only based on morphological convolution for geodesic measures described in section 2 applied on the binary image obtained by the previous step.

a) Despeckle

To save computational time, we apply a despeckle to quickly remove noise and dithered background. We apply a two pas distance transform in the 8connectivity neighbourhood of the binary image.

The maximal value of the distance transform is reached along the medial axis (Chassery,1991) and measure the minimum geodesic distance from each pixel to the contours of the object. The maximal value inside each object measures the maximal thickness of that object. To propagate the maximal thickness value inside each object, we repeat until the morphological convolution of dilation with a null mask M0 is stable. All pixels inside each object will take the same value equal to the maximal thickness of that object. The despeckle consists to erase in one pass, all objects having a maximal thickness of ThicknessMin threshold. It is similar to threshold the resulting image with a ThicknessMin threshold. Figure 7 shows a despeckle of document figure 6 with ThicknessMin=2. We choose to set HeightMin and WidthMin to the value 3 in order to keep and thin characters like 'I' or '1'. For printing documents, we set WidthMax and HeightMax to value 64 for 300dpi images, because characters cannot exceed this size. For ligatured manuscripts we set WidthMax and HeightMax to value 512 and 128 respectively, in order to shift correctly handwritten words in the image TextsImage.

We keep the graphical information into a binary image for further analysis to localise frames and detect tables in future work. Tables or frames bordered by dot lines or dashed lines cannot be separated from the text image because the geodesic width or height are similar to the size of characters.

Figure 9 illustrates the separation between speckles, text and graphics. Figure 9a shows the difficulties of color printed invoices with complex color background. Figure 9b shows the large amount of speckles (noise and dots from dithering part) deleted from the binary image. Figure 9c displays the graphics elements and large objects. We notice that small vertical lines from tables in columns are not classified into graphics because their heights do not exceed HeightMax.

The horizontal dot line and other small components from the graphical background are classified to the image TextsImage instead of GraphicsImage because their geodesic widths are under the limit WidthMax. These errors have no consequences, because during the layout analysis, these random elements from the image TextsImage will be rejected because they are not aligned enough to build a text line. We design the system to be sure that all the characters are correctly classified into the image TextsImage. But for characters connected to the graphical elements, these characters are found in the GraphicsImage. The next step aims to separate characters connected to graphics.

Separation of Characters Connected to Graphics

Figure 10 illustrates frequent cases for invoices with printing text which overlap lines surrounding frames or tables. When colors cannot separate characters and graphics, the image GraphicsImage contains textual element which touch graphics (Figure 10b). We can achieve a coarse separation between characters and graphics by using elementary morphological operation with the existing information provided by the system. The binary morphological closing of GraphicsImage, with an horizontal / vertical element Bh / Bv respectively, removes all characters that touch graphics both vertically / horizontally (figure 10c The size of the horizontal and vertical structural elements Bh and Bv must be fixed to the minimal width and height of characters to separate from the graphics, respectively. Typically we use WidthMax and HeightMax for the size of the horizontal and vertical structural elements respectively.

The reconstruction of characters after splitting them from a graphic line is possible but we do not achieve this restoration. This character reconstruction will be detailed in future work. Our proposed morphological operation works perfectly well for text touching straight lines only, and is also tolerant to image skew (figure 10h).

Color Fusion and Selection

This step consists of combining the color information from the MeanShift clustering and the color segmentation by morphology to merge outlier colors classes to the main color classes. This step also ranks the text color layer by frequency and selects the main text colors. We have already illustrated (figure 4) that the MeanShift produces classes of outliers colors due to the existing color transitions along characters contour. As the Meanshift is applied only in the colorimetric space, for each pixel independently to the other neighbouring pixels, these color outliers cannot be avoided. We have tested several pre-processing algorithms such as the edge preserving smoothing (Nikolaou,2009) or other choc filters to suppress the color transitions along contours. However, this kind of pre-processing is time consuming and cannot be used for real time applications.

We have developed a straightforward merging process which takes into account the spatial cooccurrence of colors classes in the segmented image by the MeanShift. We use TextsImage to compute statistics about the connectivity of colors classes found by the MeanShift. We only focus on text color because the color of the background is useless for our application. In the image TextsImage, we compute the 2D spatial co-occurrence H2D (i,j) equal to the number of class color i connected spatially to class colorj in all the inside characters of the imageTextsImage. We use a 8-connectivity to count correctly in one pass H2D(i,j).We compute H1D(i) the number of occurrence of the class color from H2D(i,j). C(i,j)=H2D(i,j)/H1D(j) measures the degree of connectivity between the class colori with the class colorj. Color Outliers share a high connectivity with main colors of characters.

Algorithmic Optimization

Several hundreds of thousands of documents are automatically processed daily by the company. We must reduce the algorithmic complexity of each step of the AColDPS system. The overall processing for each image must not exceed few seconds without parallelization. The objective consists of computing an image in less than a second with parallelisation.

The color clustering is already optimized with a complexity of a O(N) by using the Fast Integral MeanShift based on integral cubes (Lebourgeois et al., 2013). The adpative thresholding of the color morphology results is also already optimized with integral images (Gaceb et al., 2013). Median filter is also computed in constant time by using partial histograms correspondence of sliding windows between two successive windows (Perreault, 2007).

We have speeded-up the median filtering by applying it on a low resolution image for a degraded result. However, the median result is just a coarse representation of the local dominant color we use as seeds for a conditional dilation or erosion. The quality of the median result is not taken into account during the process. For the morphological color operation of dilation and erosion, integral images cannot be used with min and max operators, only summation of functions can be computed. To optimize the color morphological operations of dilation and erosion, we use the same idea from (Perreault, 2007). Instead of computing the statistical histogram to calculate the median values, we compute the local maxima and minima of a sliding window by using an horizontal raw vector which stores the maximal/minimal values of each column of the windows. When the window slides from a pixel to another, we just shift the values in the row vector and compute the maxima/minima of the new column that we compare to the maxima/minima of the row horizontal vector only once.

Color segmentation and the clustering process run in much reduced time and depend only on the number of pixels to process. The color fusion and selection step depends on the number of colors found by the fast integral MeanShift. As the number of clusters is reduced, the number of operations are not time consuming. The computational time for the separation between text from graphics and noise is not predictable. The morphological convolution like all geodesic transformation is repeated until there is not change. The number of iterations depends on the complexity of shapes and the alignment of dots for the dithered image. The more the image contains complex graphics and noise or dithered background, the more time this step will take. The time of the processing is maximal for complex shapes like Peano curves or other space-filling curve. For a 300dpi image 1640 x 2332, it takes less than 3 sec. for color clustering, 6 sec. for color image segmentation by morphology and colors fusion and selection on one core without parallelization. The separation of text from graphics, image noise and dithered background can take less than a second for simple and clean image to several seconds for complex images with dithered background. All the algorithms are sequential and can be easily parallelized.

RESULTS

Global Performances

We first illustrate the performances of the color automatic segmentation on a test image provided by the private company Janich&KlassComputertechnik GmbH which has developed the software DpuScan and its Advanced Color Document Processing (ACDP) tool, which is widely used in the industry and distributed worldwide. DpuScan is well-known to be the best tool to separate text colors in business documents. But it is achieved manually by selecting each color background and text color.

Figure 11 shows that AColDPS find text color automatically and achieve a good segmentation of this image. We display all color layers of text in the same image with an artificial white background to save place. Figure 12 and 13 show the pertinence to use color information to segment text from complex pre-printed backgrounds. The thresholding of the luminance image (figure 12b) make difficult the separation between handwritten text and the preprinted forms. After a color analysis, the added handwritten text can be easily segmented.

Evaluation on the Database

We have tested the proposed system on 529 color images of various invoices and forms in real situation. Among 529 images we manually found 4 images with some problems of segmentation. Among these errors, we found 2 images that present a change of text color, detected by the system, because of the ink bleed trough of the color background to the characters of the foreground (Figure15). 1 images show handwritten texts totally illegible because of the ink fading. 1 error is due to the printing of black characters crossing a large black frame. Most of errors can be explained by the quality of the document itself. We have achieved 99.25 % of correctly segmented document.

CONCLUSIONS

In this paper, we have presented an unsupervised fully automatic system for color business document segmentation. We have developed the first fully data-driven pixel-based approach that does not need a priori information, training or manual assistance.

The proposed method has the following advantages:

1) It does not require any connected component analysis and simplifies the extraction of the layout and the recognition step undertaken by the OCR; 2) it processes inverted and non-inverted text automatically, using color morphology, even in cases where there are overlaps between the two; 3) it efficiently removes noise and speckles from dithered background and automatically suppresses graphical elements using geodesic measurements; 4) it splits overlapped characters and separates characters from graphics if they have different colors. The proposed Automatic Color Document Processing System has the potential to be adapted into different business document images. The system outperformed the classical approach that uses binarization of the greyscale image and simplifies both the extraction of the layout and the recognition performed by the OCR. In future works, we plan to find a solution to reconstruct characters crossing graphical elements.

ACKNOWLEDGMENT

This work is granted by ITESOFT for the project DOD.

Figure 1 :

 1 Figure 1: Issues some examples of several difficulties presented in color business document.

Figure 4 :

 4 Figure 4: Fast Integral Mean Shift application.

  the multidimensional morphology in (RGB) color space can be substituted efficiently by a scalar classical morphology. Closing(I) = Erode B (Dilate B (I

Figure 5 :

 5 Figure 5: Black-Top-Hat Color Morphology operation

  documents because it generally represents the labelling of a column or a row in a table. To extract inverted text, we must apply a White-Top-Hat which is the dual operation of the Black-Top-Hat transform. The opening of the image (4) deletes thin bright objects from darker background. The difference between the original image and the opening image (5) highlights the thin objects brighter than the background. Opening(I) = Dilate B (Erode B (cannot combine the Black-Top-Hat and the White-Top-Hat results at pixel-level. The duality of these two morphological operations makes impossible the separation between inverted and noninverted text. In the Black-Top-Hat, inverted text becomes white over black background and in White-Top-Hat it appears black over white background.

  segment separately both inverted and non-inverted text by using the conditional dilation (11) and the conditional erosion of the dominant color image (12) restricted by the original image I, respectively. DominantLocalColor(I) ≈ Median(I) (10) CD B I (Median(I))=min(Dilate(Median(I)) , I) (11) CE B I (Median(I))=max(Erode(Median(I)) ,I) (12) CE B I (Median(I)) erases all not inverted texts which are darker in luminance than the background (Figure 6c). Accordingly, CD B I (Median(I)) deletes all inverted texts which are brighter than the background (figure 6d). To extract the not inverted text, we define Positive(I) by taking the difference between CE B I (Median (I)) and the original image I (10).Accordingly, to segment inverted texts, we define Negative(I) by taking the difference between the original image I and CD B

Figure

  Figure8aand 8b show that AColDPS can process successive inclusion of color frames without heuristics. The dithering part of the blue column is also segmented like all thin objects such as characters and thin graphical objects. Invoices and forms frequently use dithered background colors that need cleaning. In the next step, we propose a straightforward process to remove both large graphic objects and noise without connected components extraction by using morphological geodesic operations.

Figure 7 :

 7 Figure 7: Results of the Despeckle by morphology b) Separation between Graphics/Text/Dithered PartsThe geodesic measure of width and height is not the measure of the bounding box surrounding the object, but the measure of the width and height inside the object. The geodesic measures bring more pertinent information than classical spatial measures. Moreover, the noise removal based on geodesic width and height has nothing to do with the morphological despeckle described previously based on the objects thickness. The Objects' thickness and geodesic width and height are complementary

  after propagation of maximal values by morphological convolution of dilation with NULL M0 mask.

Figure 8 :

 8 Figure 8: Results of the geodesic transform by morphological convolution

  Figure10illustrates frequent cases for invoices with printing text which overlap lines surrounding frames or tables. When colors cannot separate characters and graphics, the image GraphicsImage contains textual element which touch graphics (Figure10b). We can achieve a coarse separation between characters and graphics by using elementary morphological operation with the existing information provided by the system. The binary morphological closing of GraphicsImage, with an horizontal / vertical element Bh / Bv respectively, removes all characters that touch graphics both vertically / horizontally (figure10c,10d). We define H_Text (15) and V_Text(16) by the difference between the horizontal / vertical closing of GraphicsImage with the image GraphicsImage itself, respectively. Images H_Text/V_Text show characters disconnected with horizontal / vertical lines (Figure10e, 10f), respectively.X= GraphicsImageH_Text=HorizontalClosing Bh ( X ) c ∩X X= GraphicsImage V_Text=VerticalClosing Bv ( X ) c ∩X

  Figure11shows that AColDPS find text color automatically and achieve a good segmentation of this image. We display all color layers of text in the same image with an artificial white background to save place. Figure12and 13 show the pertinence to use color information to segment text from complex pre-printed backgrounds. The thresholding of the luminance image (figure12b) make difficult the separation between handwritten text and the preprinted forms. After a color analysis, the added handwritten text can be easily segmented. Figure14zoom on the table headings of the figure 4. It illustrates the color separation between overlapped texts in the worst case when inverted text crosses non inverted text. AColDPS separates correctly the two layers of text (figure14).

Figure 11 :

 11 Figure 11: AColDPS result on DPUscan test image.

Figure 13 :

 13 Figure 13: AColDPS separates correctly color handwritten text and the background even with highlighting regions.

Figure 14 :

 14 Figure 14: Correct color separations with overlapped inverted and not inverted texts.

  Figure 12: Color segmentation outperforms the adaptive thresholding of the luminance for character segmentation.Figure15Failure of AColDPS because of color transfer from the background to the foreground.

Figure 15

 15 Figure 12: Color segmentation outperforms the adaptive thresholding of the luminance for character segmentation.Figure15Failure of AColDPS because of color transfer from the background to the foreground.

Algorithm 2 merges color class i to color class j if the connectivity C(i,j) exceeds Cmin=0.25 and if

and H1D(j)are maximal and the colorimetric distance is minimal. To keep the color coherency, we merge small class to large class and not the inverse.

Algorithm 2: Color Fusion

{ j=ColorClass(x-1,y) H2D(i,j)++ } if (TextsImage(x,y-1)==0)

{ j=ColorClass(x,y-1) H2D(i,j)++ } if (TextsImage(x-1,y-1)==0) {j=ColorClass(x-1,y-1) H2D(i,j)++} } forcolor class i forcolor class j >i if C(i,j)>cmin mergei to j if { * H1D(i)<H1D(j) * C(i,j) is maximal * H1D(j) is maximal * ColorDistance(i,j) minimal }

After merging the color classes in ColorClass, we repeat algorithm 2 until there is no more changes. The iterations are necessary to merge successively layers of colors around characters contours. To select the right number of different text color, we rank the text color classes in descending order of frequency. There is a gap between two consecutive ranked color classes of the decreasing curve of frequencies. We set the number of text colors in the middle of the larger gap between successive color classes.