\section{Introduction}
The problem of allocating a heterogeneous, divisible resource among a set of $n$ agents with varying preferences is essentially described as the problem of cutting a cake in intuitive concepts. The cake cutting problem is a fundamental topic in the theory of fair division  \cite{cakecuttingdispute,Cake,Fairdivisionandcollectivewelfare,HandbookCSC} and it has received a significant amount of attention in the domains of mathematics, economics, political science, and computer science \cite{TheEfficiencyoffairdivision,cakecuttingreallyisnotapieceofcake,feeiciencyoffairdivisionwithconnectedpiece,ChildrenCryingatbirthdayparties,cakecuttingnotjustchildplay,TheQuerycomplexityofcakecutting}. Dividing a cake fairly among agents is a challenging task.
\textit{Envy-freeness} and \textit{proportionality} are the most `important criteria of a fair allocation in the cake-cutting literature. In an envy-free allocation, every agent is pleased with the pieces they are allocated as opposed to any other agent's allocation. In a proportional allocation, each agent receives at least $\frac{1}{n}$ of the value he estimates to the cake. When all of the cake has been divided, envy-freeness entails proportionality. It is generally known that envy-free allocations always exists \cite{ANENVY-FREECAKEDIVISIONPROTOCOL} and even if we specify that each agent must receive a connected piece \cite{rental,Stromquist1980HowTC}. In addition to the existence, the algorithmic design aspect of the process has also been thought about for a long time \cite{ADiscreteandBoundedEnvy-FreeCakeCuttingProtocolforAnyNumberofAgents,Aboundedandenvy-freecakecuttingalgorithm,Adiscreteandboundedenvyfreecakecuttingprotocolforfouragents,Howtocutacakefairly,ANoteOnCakeCutting,Stromquist2008EnvyFreeCD}. For any number of agents, we are able to calculate a proportional allocation \cite{Howtocutacakefairly,ANoteOnCakeCutting} as well as an envy-free allocation \cite{ADiscreteandBoundedEnvy-FreeCakeCuttingProtocolforAnyNumberofAgents}.\newline
\\
In contrast, the dual problem of cake-cutting, also known as chore-cutting, seeks to allocate an undesirable resource to a set of $n$ agents, with each agent wishing to receive as little of the resource as possible. Chore division might model the allocation of chores within a household, liabilities in a bankrupt company, etc. Similar to the cake-cutting problem, dividing a chore fairly is also a challenging problem. The most important criteria of a fair allocation, similar to cake cutting, are \textit{envy-freeness} and \textit{proportionality}. For most questions in cake cutting there exist parallel questions in chore division; for instance, an $n$-person envy-free cake cutting algorithm, in which each agent is satisfied that no other agent has received a bigger piece in the their estimation, was found by Brams and Taylor \cite{ANENVY-FREECAKEDIVISIONPROTOCOL}, while the equivalent chore-cutting result found by Peterson and Su \cite{Npersonchoredivision}. We know how to compute a proportional allocation ( similar to the cake cutting) and an envy-free allocation \cite{envy-freechoredivisionforanyagents} for any number of agents. Though several algorithms for cake cutting also apply to chore-cutting, the theoretical properties of the two problems differ in many cases, and much less work has been done for chore-cutting than for cake cutting \cite{AlgorithmicSolutionsforEnvy-FreeCakeCutting,AlgorithmsforCdivisionofchores,complexitychoredivisio,DividingConnectedChoresfairly,ExactProceduresforenvyfreechoredivision,Chaudhury2020DividingBI}.\newline
\\
However, a fundamental issue when deploying a certain cake cutting (or, chore-cutting) algorithm  is that agents are self-interested and may manipulate and misreport their valuations  to the algorithm to get better allocations. This motivates the study of the cake-cutting problem ( or,chore-cutting) from a game-theoretic aspect, in particular
a mechanism design aspect. Is there a \textit{truthful} and fair cake cutting mechanism such that truth-telling is each agent's dominant strategy? This question was first proposed by Chen, Lai, Parkes and Procaccia \cite{TruthJusticecakecutting}.\newline
Now one question arises: how can we represent a value density function succinctly? There are two different approaches that have been considered in the literature.
The first, in fact the most ubiquitously used model in the literature, is the Robertson-Webb model where the mechanism proceeds through a sequence of queries on the valuation functions of the agents that are of the following two types:
\begin{itemize}
    \item $\textbf{Eval}_i(x,y)$: ask agent $i$ his value on the interval $[x,y]$.

    \item $\textbf{Cut}_i(x,p)$: ask agent $i$ for a point $y$ where $[x,y]$ is worth exactly $p$.
\end{itemize}
Under this model, it has been shown that no truthful envy-free mechanism exists with bounded number of queries \cite{howtocutacakebeforepartyends} and that any truthful mechanism is dictatorial \cite{dictatorship} (i.e., there is a fixed agent who gets the entire cake among two agents).\\
In the second approach, the value density function is assumed to be \textit{piecewise-constant}. Piecewise constant functions are concise and may approximate general valuation functions to any accuracy \cite{howtocutacakebeforepartyends} , and they can be succinctly encoded. The mechanism then takes the $n$ encoded value density functions as inputs and outputs an allocation. These mechanisms are called \textit{direct-revelation mechanisms}.
 \\
For direct-revelation mechanisms, Chen et al. \cite{TruthJusticecakecutting} first give a deterministic truthful Pareto optimal envy-free cake cutting mechanism for any number of agents with piecewise uniform valuation functions. Chen et al.'s result show that fairness and truthfulness are compatible in the allocation of heterogeneous resources (cake). Chen et al. \cite{TruthJusticecakecutting} then proposed the following natural open problem.
\newline
\\
\textit{Does there exist a truthful envy-free cake-cutting mechanism for piecewise-constant value density functions?}
\\
\newline
Tao \cite{OnExistenceoftruthfulfaircakecuttingmechanisms} shows the negative result of the above question raised by Chen et al.\cite{TruthJusticecakecutting}. Basically, for most questions in cake cutting there exist parallel questions in chore-cutting. Now you may think the following question :
\newline
\\
\textit{Does there exist a truthful envy-free chore-cutting mechanism for piecewise-constant value density functions?}
\newline
\\
Bei et al. \cite{Truthfulfairdivisionwithoutfreedisposal} first show the existence of a truthful envy-free chore-cutting mechanism for two agents. They also show that when each agent values a single interval of the form $[0,x_i]$,  no truthful envy-free chore-cutting mechanism exists with one of the following properties:
\begin{itemize}
    \item anonymity;

    \item connected piece assumption;

    \item position-oblivious.

\end{itemize}
Francis \cite{Strategyproofchoredivision} show a truthful proportional Pareto optimal algorithm for chore-cutting with piecewise uniform valuation functions.

The purpose of this paper is to demonstrate some impossibility results regarding the existence of a truthful envy-free chore-cutting mechanism under some known constraints.
\subsection{Our Results}
    Throughout the paper, we focus on deterministic truthful envy-free mechanisms when agents have \textit{piecewise constant valuations}. Among the several valuation function classes, this one stands out as one of the most expressive functions in the study of cake cutting \cite{cakecuttingenvyandtruth,OptimalProportionalCakeCuttingwithConnectedPieces,Optimalenvyfreecakecutting,cakecuttingalgorithmsforpiecewiseconstant,TruthJusticecakecutting,Truthfulfairdivisionwithoutfreedisposal,DeterministicStrategyproof,towardsmore}. Moreover, piecewise-constant functions become more desirable because they are concise and may approximate general valuation functions to any accuracy \cite{howtocutacakebeforepartyends}.\newline
    In the first part, a family of impossibility results related chore-cutting mechanisms is shown. Firstly, we show that no deterministic truthful envy-free mechanism exists with connected piece assumption. Even if each agent has a non-zero chore value for the whole chore i.e., $f_i(x)>0$ for all $x\in [0,1]$, the same impossible result still occurs. Secondly, we prove that no deterministic truthful dictatorship mechanism exists that is envy-free i.e., no deterministic truthful envy-free chore mechanism exists where an agent would not accept any chore valuation. After removing the dictatorial constraint, the same impossibility result also applies to non-wasteful constraints.
\subsection{Related Work}
For many years, the ``cake cutting problem" has been a significant topic in the fields of fair division and social choice. Research on fair division originated in the 1940s by the Polish mathematician Hugo Dyonizy Steinhaus to focus on protocols for achieving fairness objectives in cake-cutting. \cite{Theproblemoffairdivision}. Even though the existence and computation of fair allocations have been thoroughly researched \cite{ANENVY-FREECAKEDIVISIONPROTOCOL,Howtocutacakefairly,rental,ANoteOnCakeCutting,Stromquist1980HowTC}, Chen et al's \cite{TruthJusticecakecutting} research work that we mentioned earlier was the first to consider incentive issues. Chen et al. \cite{TruthJusticecakecutting} give the first truthful envy-free Pareto optimal cake cutting mechanism that works when each agent's valuation is piecewise uniform, a special case of piecewise constant valuation. Specifically, the mechanism proposed by chen et al.\cite{TruthJusticecakecutting} for piecewise uniform value density functions is further studied by
many researchers \cite{cakecuttingalgorithmsforpiecewiseconstant,IncentiveCompatible,TruthfulCakeCuttingForExternalities,cakecuttingenvyandtruth,Truthfulfairdivisionwithoutfreedisposal,OnExistenceoftruthfulfaircakecuttingmechanisms,DeterministicStrategyproof,truthfulcakesharing,Envyfreemechanismwithminimumnumberofcut,anenvyfreeandteruthfulmechanismswithasmallnumberofcuts,TruthfulnessPF,TruthfulFairdivision}. Aziz and Ye \cite{cakecuttingalgorithmsforpiecewiseconstant}
show that no truthful cake cutting mechanism exists if it satisfies one of the following properties:
\begin{itemize}
    \item proportional and Pareto-optimal;

    \item Robust-proportional and non-wasteful.
\end{itemize}
 Bei et al. \cite{cakecuttingenvyandtruth} show that there does not exist a truthful envy-free cake cutting mechanism under one of the four constraints:
 \begin{itemize}
     \item non-wasteful;

     \item position-oblivious;

     \item connected piece assumption;

     \item agents report their value density function functions sequentially.

 \end{itemize}
 Bei et al. \cite{Truthfulfairdivisionwithoutfreedisposal} show that no truthful envy-free cake cutting ( or, chore cutting) mechanism with uniform density functions of the form $[0,x_i]$ exists if it satisfies one of the four constraints:
 \begin{itemize}
     \item anonymity;

     \item connected piece assumption;

     \item position-oblivious.
 \end{itemize}
Tao \cite{OnExistenceoftruthfulfaircakecuttingmechanisms} shows that there does not a exist truthful proportional cake cutting mechanism, even when all of the following hold:
\begin{itemize}
    \item there are two agents;

    \item valuation density functions are piecewise constant;

    \item each agent is hungry: for $i=1,2$, $f_i(x)>0$ $\forall x \in [0,1]$;

    \item the mechanism needs not be entire: the mechanism may throw away parts of the cake.
\end{itemize}
 Maya and Nisan \cite{IncentiveCompatible} give a characterization of truthful and Pareto optimal mechanisms for two agents. Recently, Francis \cite{Strategyproofchoredivision}
present a truthful proportional Pareto optimal algorithm for chore-cutting with piecewise uniform valuation functions.
\section{Preliminaries}
In a chore-cutting instance, a divisible and heterogeneous bad resource (or a ``chore''), represented by the interval\footnotemark{} $[0,1]$ to be divided among a set of agents $N=\{1,2,....,n\}$ \footnotetext{We often denote the chore by an interval $[a,b]$ for convenience. It can be normalised to $[0, 1]$.} \cite{complexitychoredivisio,DividingConnectedChoresfairly,AlgorithmsforCdivisionofchores}. Each agent $i$ is endowed with an integrable, non-negative chore density function $f_i:[0,1]\rightarrow \mathbb{R}^+\cup {0}$, which captures how the agent $i$ values different parts of the chore. By $f_i(x)$ we denote the value of density function of the agent $i$ at the point $x$.
A \textit{piece of chore} $X$ is a finite union of disjoint subintervals of $[0,1]$. Basically, the agent $i$'s chore value on the piece $X$, denoted by $v_i(X)$, is given by
\begin{center}
    \[v_i(X) = \sum_{I\in X}\int_{I} f_i(x) \,dx \]
\end{center}
An allocation is a partition of $[0,1]$ into a set $\{A_1,A_2,...,A_n\}$ where each $A_i$ allocated to agent $i$, and $A_i\cap A_j=\emptyset$ for any $i\neq j$. The allocation is said to be entire if  $\bigcup_{i=1}^n A_i=[0,1]$. Note that in the chore-cutting agents want to minimize their value.
Two notions of fairness have been studied in the chore-cutting literature.\newline
An allocation $(A_1,A_2,....,A_n)$ is said to be proportional if each agent receives at most his average share of the entire chore:
\begin{center}
    $\forall i : v_i(A_i)\leq \frac{1}{n} v_i([0,1])$.
\end{center}
An allocation $(A_1,A_2,....,A_n)$ is said to be envy-free if no agent can obtain a lower share by exchanging with any other agent:
\begin{center}
    $\forall i,j: v_i(A_i)\leq v_i(A_j)$.
\end{center}
An entire envy-free allocation is always proportional. In the case of two agents, an allocation is envy-free if and only if is proportional.
\newline
A direct-revelation chore-cutting mechanism $\mathcal{M}$ is a function that takes the valuation functions $(f_1,f_2,....,f_n)$ of the agents as an input and returns an allocation $(A_1,A_2,....,A_n)$ as an output. We only consider deterministic mechanisms in this paper, meaning that the allocation is completely determined by the input density functions. Moreover, we assume that the mechanism has to allocate the entire chore to the agents.\newline
We end this section by defining a number of properties that we consider in this paper.
\newline
\textbf{Definition 1.} Let $F=(f_1,f_2,...,f_n)$ be a given vector of  input chore density functions. The indicator function  $L_{F}:{\mathbb{R}^n} \rightarrow [0,1]$ is defined as
\begin{center}
$L_F(r_1,r_2,....,r_n)=|\{x|\forall $i$, f_i(x)=r_i \}|.$ \\
where $(r_1,r_2,....,r_n)\in \mathbb{R}^n$ and $|S|$ indicates the sum total of the lengths of the intervals in $S$.

\end{center}
\textbf{Definition 2.} A direct-revelation chore-cutting mechanism $\mathcal{M}:(f_1,f_2,....,f_n)\rightarrow (A_1,A_2,....,A_n)$ is said to satisfy
\begin{itemize}
    \item proportionality, If it consistently provides a proportional allocation ;

    \item envy-freeness, If it consistently provides an envy-free allocation ;

    \item truthfulness, if each agent's dominant strategy is to report his true chore density function i.e., for each agent $i$, any $(f_1,....,f_n)$ and any $f_i^\prime$,
    \begin{center}
        $v_i(\mathcal{M}_i(f_1,....,f_n))\leq v_i(\mathcal{M}_i(f_1,...,f_{i-1},f_i^\prime,f_{i+1},...,f_n))$.

    \end{center}
    Note that this means misreporting a density function never benefits the agent.
    \item connected piece assumption, if each $A_i$ is always a contiguous piece.

    \item non-wastefulness, if for each agent $i$, $f_i(x)>0$ for any $x\in A_i$ i.e., no agent can receive any portion with chore value 0.

   \item Pareto optimality, if for any allocation returned by the mechanism, there does not exist any alternate allocation that makes no agent worse off and at least one agent better off with regard to the particular valuation density functions. For example suppose
    $(A_1^\prime,A_2^\prime,....,A_n^\prime)$ is another allocation returned by $\mathcal{M}$ rather than $(A_1,A_2,....,A_n)$ with respect to the chore density functions $f_1,f_2,....,f_n$. Then $(A_1,A_2,....,A_n)$ is Pareto optimal if for all $i$, $v_1(A_i^\prime)\geq v_(A_i)$ and there exists at least one $i$ such that $v_1(A_i^\prime)> v_(A_i)$.

    \item dictatorial, if there is a fixed agent who does not accept a share with non-zero chore valuation.
    \item position oblivious, if for any two cake cutting instances with chore density functions $F=(f_1,f_2,....,f_n)$
    and $ F^\prime=(f_1^\prime,f_2^\prime,....,f_n^\prime) $ such that $L_{F}=L_{F^\prime}$, the mechanism $\mathcal{M}$ returns the allocations $\mathcal{M}(F)=(A_1,A_2,....,A_n)$ and $\mathcal{M}(F^\prime)=(A_1^\prime,A_2^\prime,....,A_n^\prime)$ such that $v_i(A_i)=v_i(A_i^\prime)$ for every $i$.

    \item  anonymity, if for any vectors of chore density function $(f_1,....,f_n)$ and any permutation $\sigma$ of $(1,2,...,n)$, then $v_i(A_i)=v_i(A_{\sigma^{-1}(i)}^\prime)$ for every $i$ where $\mathcal{M}(f_1,f_2,....,f_n)=(A_1,A_2,....,A_n)$ and
    $\mathcal{M}(f_{\sigma (1)},f_{\sigma (2)},...,f_{\sigma (n)})=(A_1^\prime,A_2^\prime,....,A_n^\prime)$
\end{itemize}
The chore mechanism is said to be dictatorial if there is an agent which never receives a piece of chore with a value above zero, no matter what the chore density functions are.\\
Naturally, a mechanism is obviously position-oblivious if the chore values the agents get depend only on the lengths of the pieces that different groups of agents have chore valuations on and not on where these pieces are, and is anonymous if the value that the agents get doesn't depend on their identities.\\
Note that throughout this paper we assume that the agents have piecewise-constant valuation functions. A function $f_i$ is said to be piecewise-constant if the cake can be partitioned into a finite number of intervals such that $f_i$ is constant over each interval.
\section{Impossibility Results}
\textbf{Theorem 1.} There exists no deterministic truthful envy-free mechanism that satisfies the connected piece assumption, even for two agents.\\
\newline
\textbf{Proof.} Suppose the chore is presented by $[0,9]$. Let $\epsilon>0$ be a sufficiently small constant. Consider the chore-cutting instance $F=(f_1,f_2)$ where
\begin{equation*}
    f_1(x)=
    \begin{cases}
    1 & \text{if } x \in [3,4+\epsilon] \cup [5,6]\\
    0 & \text{otherwise}
    \end{cases}
\end{equation*}
\begin{equation*}
    \text{and}
\end{equation*}
\begin{equation*}
     f_2(x)=
    \begin{cases}
     1 & \text{if } x\in [1,2]\cup [7- \epsilon,8]  \\
     0 & \text{otherwise}
    \end{cases}.
\end{equation*}
\newline
Under the connected piece constraint, it is easy to see that both of them will get a value at least 1 and agent $2$ will get a connected piece from the left side of the chore.
\newline
Due to envy-freeness and connected piece condition, we must get
$v_2(\mathcal{M}_2(F))=1$ and $V_1(\mathcal{M}_1(F))\leq 1+\frac{\epsilon}{2}$ which implies that $[0,4-\frac{\epsilon}{4}]\subseteq \mathcal{M}_2(F)$ and $\mathcal{M}_1(F)\subseteq [4-\frac{\epsilon}{2},9]$.
Considering the scenario where agent $1$ misreports his density function to be
\begin{equation*}
    f_1^\prime(x)=
    \begin{cases}
        1 & \text{if } x \in [3,4+\epsilon]\cup [5,6] \\
        2 & \text{if } x \in [8,9] \\
        0 & \text{otherwise}
    \end{cases}
\end{equation*}
\newline
Due to envy-freeness and connected piece condition, it is also clear that agent $2$ must receive a contiguous piece from the left side of the chore $[0,9]$ and agent $1$ will receive a valuation at most $2+\frac{\epsilon}{2}$ which implies that
$\mathcal{M}_1(f_1^\prime,f_2)\subseteq [6-\frac{\epsilon}{2},9]$. Since $v_1([6-\frac{\epsilon}{2},9])=\frac{\epsilon}{2}$. This contradicts that $\mathcal{M}$ is truthful.
\\
\newline
\textbf{Theorem 2.} If every agent is required to receive a connected piece, no deterministic truthful envy-free mechanism exists, even for two hungry agents.
\\
\newline
\textit{Proof.} We will prove this theorem by contradiction. Suppose such mechanism $\mathcal{M}$ exists for two agents. We construct three chore-cutting instances and analyze the outputs of $\mathcal{M}$ on these instances. For the first two instances we show that the outputs are unique. Based on the first two instances, we show that the allocation of the last chore-cutting instance output by $\mathcal{M}$ will violate the contiguity constraint.\\
\newline
\textbf{Instance 1.} $F^{(1)}=(f_1^{(1)},f_2^{(1)})$, where $f_1^{(1)}(x)=1$ and $f_2^{(1)}(x)=1$ for $x\in [0,1]$.
\newline
Due to envy-freeness, we must have $|\mathcal{M}_1(F^{(1)})|=|\mathcal{M}_2(F^{(1)})|=\frac{1}{2}$. We will denote the allocation of $\mathcal{M}(F^{1})$ by $(A_1,A_2)$. We will use $A_1$ and $A_2$ in the the definitions of the remaining two instances.\
\newline
\textbf{Definition.} $A_1=\mathcal{M}_1(F^{(1)})$ and $A_2=\mathcal{M}_2(F^{(1)})$.
\\
\newline
Without loss of generality, we assume that $A_1=[0,.5]$ and $A_2=(.5,1]$. Since $A_1$ and $A_2$ are contiguous piece.\newline
Let $\epsilon$ be a sufficiently small positive real number.\\
\newline
\textbf{Instance 2.} $F^{(2)}=(f_1^{(2)},f_2^{(2)})$, where $f_1^{(2)}(x)=1$  for $x\in [0,1]$ and
\begin{equation*}
    f_2^{(2)}(x)=
    \begin{cases}
        1 & \text{if } x\in A_1\\
        \epsilon & \text{if } x \in A_2
    \end{cases}.
\end{equation*}
\newline
In the following proposition we will see that the only possible output by $\mathcal{M}$ is $(A_1,A_2)$.\\
\newline
\textbf{Proposition.1.} $\mathcal{M}(F^{(2)})=(A_1,A_2)$.
\\
\newline
\textit{Proof.} Firstly, we must have $|\mathcal{M}_2(F^{(2)})|\geq \frac{1}{2}$. Otherwise, agent $1$ will receive a piece of chore of length strictly greater than $\frac{1}{2}$. Since agent $1$'s valuation function is uniform on [0,1], $\mathcal{M}$ is not envy-free.\newline
Secondly, we must have $ \mathcal{M}_2(F^{(2)}) \subseteq A_2$. Suppose that $A_2$ does not contain all of  $\mathcal{M}_2(F^{(2)})$, i.e., $|A_2\cap \mathcal{M}_2(F^{(2)})|<\frac{1}{2}$. Given that $|\mathcal{M}_2(F^{(2)})|\geq \frac{1}{2}$.
\begin{center}
  $v_2(\mathcal{M}_2(F^{(2)}))$
  $=v_2(A_1 \cap \mathcal{M}_2(F^{(2)}))+v_2(A_2\cap \mathcal{M}_2(F^{(2)})) $ \\
  $=1.|A_1\cap \mathcal{M}_2(F^{(2)})|+\epsilon.|A_2 \cap \mathcal{M}_2(F^{(2)})| $ \\
  $\geq (\frac{1}{2}-|A_2\cap \mathcal{M}_2(F^{(2)})|) + \epsilon.|A_2 \cap \mathcal{M}_2(F^{(2)})|$  \\
  $=\frac{1}{2} -(1-\epsilon)|A_2 \cap \mathcal{M}_2(F_{(2)})| $\\
$> \frac{1}{2}-(1-\epsilon).\frac{1}{2}>\frac{\epsilon}{2}$.
\end{center}
On the other hand, if agent 2 misreports his value density function to $f_2^{(1)}$ (instead of his true value density function $f_2^{(2)}$), the mechanism receives input $(f_1^{(2)},f_2^{(1)})$, which becomes instance 1 since $f_1^{(1)}=f_1^{(2)}$. In this case the allocation output is $(A_1,A_2)$, and agent 2's total value, in terms of his/her true valuation $f_2^{(2)}$, is $\frac{\epsilon}{2}$. Therefore, agent 2 can receive less value by misreporting his value density function, and $\mathcal{M}$ cannot be truthful.\newline
Putting together, we have $ \mathcal{M}_2(F^{(2)})\subseteq A_2$ and $|\mathcal{M}_2(F^{(2)})|\geq \frac{\epsilon}{2}$, which implies $M_2(F^{(2)})=A_2$. So,we must have $M_1(F^{(2)})=A_1$\\
\newline
\textbf{Instance 3.} $F^{(3)}=(f_1^{(3)},f_2^{(3)})$, where
\begin{equation*}
    f_1^{(3)}(x)=
    \begin{cases}
        1 & \text{if } x\in A_1\\
        0.5 & \text{if } x \in A_2
    \end{cases}
\end{equation*}
\begin{equation*}
    \text{and}
\end{equation*}
\begin{equation*}
    f_2^{(3)}(x)=
    \begin{cases}
        1 & \text{if } x\in A_1\\
        \epsilon & \text{if } x \in A_2
    \end{cases}.
\end{equation*}
\\
\newline
Now we will show in the following proposition that each agent gets exactly half from both of $A_1$ and $A_2$. Which contradicts that $\mathcal{M}$ allocates connected piece for each agents.\\
\newline
\textbf{Proposition.2.} $|\mathcal{M}_1(F^{(3)})\cap A_1|=|\mathcal{M}_1(F^{(3)})\cap A_2|=|\mathcal{M}_2(F^{(3)})\cap A_1|=|\mathcal{M}_2(F^{(3)})\cap A_2|=\frac{1}{4}$.\\
\newline
We provide a brief intuition behind the proof first. Firstly, agent $1$ cannot receive a subset of length less than $\frac{1}{2}$. Otherwise, in Instance $2$, agent $1$ will misreport his value density function from $f_1^{(2)}$ to $f_1^{(3)}$, which is more beneficial to agent $1$ ( as $f_1^{(2)}$ is uniform and agent $1$) receives a lower length by misreporting).\newline
Secondly, agent $1$ cannot receive larger than half of $A_1$. If agent $1$ receives larger than $x$, agent $1$ needs to receive less than half of $A_2$ by a length of at least $2x$ to guarantee envy-freeness. This will make the total length received by agent $1$ less than $\frac{1}{2}$.
\newline
Thirdly, agent $1$ cannot receive less than half of $A_1$. If agent receives less than half of $A_1$, agent $2$, having significantly less value on $A_2$ and high value on $A_1$. Since agent $2$ will get a piece from $A_1$ of length larger than half. This will destroy the envy-freeness of agent $1$, for that agent $2$ has take too much.\\
\newline
Finally, having shown that agent $1$ must receive exactly half of $A_1$, the envy-freeness of agent $1$ and proven fact that agent $1$'s received total length is at least 0.5 imply that agent $1$ has to receive exactly half of $A_2$.\\
\newline
\textit{Proof of Proposition.} First we must have $|\mathcal{M}_1(F^{(3)})|\geq \frac{1}{2}$. Suppose this is not the case: $|\mathcal{M}_1(F^{(3)})|<\frac{1}{3}$. We show that $\mathcal{M}$ cannot be truthful. Consider Instance $2$ where agent $1$'s density function is uniform. In Instance $2$, if agent $1$ misreports his/her density function to $f_1^{(3)}$, the mechanism $\mathcal{M}$ will see an input that is exactly the same as $F^{(3)}$ (notice $f_2^{(2)}=f_2^{(3)}$), and agent $1$ will receive a subset with length strictly less than $\frac{1}{2}$. However we have seen that in Proposition $1$ that agent $1$ will receive a subset with length exactly $\frac{1}{2}$ if (s)he reports truthfully. Since agent $1$'s true valuation is uniform, agent $1$ will benefit from this misreporting.
\newline
Let $|\mathcal{M}_1(F^{(3)})\cap A_1|=\frac{1}{4}+x$ where $x\in [-\frac{1}{4},\frac{1}{4}]$. Our aim is to prove that $x=0$. Agent $1$'s total utility in [0,1] is $\int_{0}^{1} f_1^{(3)}(x) dx=\frac{3}{4}$. To guarantee envy-freeness, we must have
\begin{center}
    $v_1(\mathcal{M}_1(F^{(3)}))$=$v_1(\mathcal{M}_1(F^{(3)})\cap A_1)+v_1(\mathcal{M}_1(F^{(3)})\cap A_2)$\\
    = $1.|\mathcal{M}_1(F^{(3)})\cap A_1|+\frac{1}{2}|\mathcal{M}_1(F^{(3)})\cap A_2|$\\
    =$1.(\frac{1}{4}+x)+\frac{1}{2}.|\mathcal{M}_1(F^{(3)})\cap A_2|\leq \frac{3}{8}$      .....(1)

\end{center}
From (1) we get $|\mathcal{M}_1(F^{(3)})\cap A_2|\leq \frac{1}{4}-2x$.
The total length agent $1$ receives is then $|\mathcal{M}_1(F^{(3)})|\leq \frac{1}{2}-x$. Since we have seen $|\mathcal{M}_1(F^{(3)})|\geq \frac{1}{2}$ at the beginning, we have $x\leq 0$.\newline
On the other hand, since $|\mathcal{M}_1(F^{(3)})\cap A_1|= \frac{1}{4}+x$, we have $|\mathcal{M}_2(F^{(3)})\cap A_1|\geq \frac{1}{4}-x$.
Since $v_2([0,1])=\frac{\epsilon}{2}+\frac{1}{2}$ and $v_2(\mathcal{M}_2(F^{(3)})\cap A_1)=1.|\mathcal{M}_2(F^{(3)})\cap A_1|\geq \frac{1}{4}-x$, to guarantee envy-freeness for agent $2$, we must have $v_2(\mathcal{M}_2(F^{(3)})\cap A_2)\leq \frac{\epsilon}{4}+x$. Therefore $|\mathcal{M}_2(F^{(3)})\cap A_2|\leq \frac{1}{4}+\frac{x}{\epsilon}$ which implies $|\mathcal{M}_1(F^{(3)})\cap A_2|\geq \frac{1}{4}-\frac{x}{\epsilon}$.  Putting this into (1), we get
\begin{center}
   $1.(\frac{1}{4}+x)+\frac{1}{2}.(\frac{1}{4}-\frac{x}{\epsilon})\leq \frac{3}{8}$
\end{center}
which implies $x\geq 0$ if $\epsilon$ is sufficiently small. Therefore $x=0$, we have $|\mathcal{M}_1(F^{(3)})\cap A_1|=\frac{1}{4}$. Since agent $1$ receives exactly length $\frac{1}{4}$ on $A_1$. Due to envy-freeness, agent $1$ can get at most $\frac{1}{4}$ on $A_2$  and $|\mathcal{M}_1(F^{(3)})|\geq\frac{1}{2}$. Therefore $|\mathcal{M}_1(F^{(3)})\cap A_2|=\frac{1}{4}$.\\
\newline
\textbf{Theorem 3.} There does not exist deterministic non-wasteful truthful envy-free mechanism even with two players.\\
\newline
\textit{Proof.} Assume by contradiction that such mechanism $\mathcal{M}$ exists. Consider the chore-cutting instance with two agents whose density functions are $f_1(x)=1$ and $f_2(x)=1$ on the entire chore. The allocation $A=(A_1,A_2)$ given by $\mathcal{M}$
must satisfy $|A_1|=|A_2|=\frac{1}{2}$. Now consider another chore-cutting instance with two agents whose value density functions are
$h_2(x)=1$ and
\begin{equation*}
    h_1(x)=
    \begin{cases}
        0 & \text{if } x\in A_1\\
        1 & \text{if } x\in A_2
    \end{cases}
\end{equation*}
\newline
Due to truthfulness, agent $1$ will get the piece of chore $A_1$. Otherwise he can misreport his value density function $h_1^\prime= f_1$. Since the mechanism $\mathcal{M}$ is non-wasteful. So the agent $2$ will get the entire piece of chore $A_2$.
Due to the envy-freeness, agent $1$ will get at most $\frac{1}{2}$ of $A_1$. This contradicts the envy-freeness of agent $2$. So such mechanism $\mathcal{M}$ does not exist.
\\
\newline
\textbf{Theorem 4.} There does not exist a deterministic truthful envy-free mechanism that is a dictatorship, even with two agents.\\
\newline
\textit{Proof.} Suppose otherwise that there is a dictatorship truthful envy-free mechanism. Consider the chore-cutting instance with two agents whose density functions are $f_1(x)=1$ and $f_2(x)=1$
on the entire chore. The allocation $A=(A_1,A_2)$ given by $\mathcal{M}$ must satisfy $|A_1|=|A_2|=\frac{1}{2}$. Consider another chore-cutting instance with two agents whose value density functions are $g_2(x)=1$ where $x\in [0,1]$ and
\begin{equation*}
    g_1(x)=
    \begin{cases}
        0 & \text{if } x\in A_1 \\
        1 & \text{otherwise}
    \end{cases}
\end{equation*}
\newline
For instance $(g_1,g_2)$, agent $1$ will get the $A_1$ if $\mathcal{M}$ is truthful, as otherwise she can bid $g_1^\prime(x)=1$ and get $A_1$. Moreover agent $1$ cannot get less than $A_1$ because of envy-freeness. Thus $A=(A_1,A_2)$ is the only possible allocation generated by $\mathcal{M}$  for the instance $(g_1,g_2)$.
\newline
However, by taking advantage of dictatorship condition, agent $2$ can misreport his density function and get a better allocation than $A_2$. For example agent $2$ can bid the following function $g_2^\prime$:
\begin{equation*}
 g_2^\prime =
 \begin{cases}
     \frac{1}{2} & \text{if } x\in A_1\\
     1 & \text{if } x\in A_2
 \end{cases}
\end{equation*}
\newline
Due to dictatorship, agent $1$ only gets the share from $A_1$. Without loss of generality, agent $1$ gets all of $A_1$. Due to envy-freeness, agent $2$ gets at most $\frac{3}{4}$ of $A_2$. Thus, agent $2$ will receive a strictly smaller value from manipulation , which implies that $\mathcal{M}$ cannot be truthful.
\section{Acknowledgements}
The author would like to thank Bodhayan Roy for his suggestions which have improved the presentation of this paper significantly.

\bibliographystyle{unsrtnat}


\section{Introduction}
\label{sec:introduction}
\begin{figure*}[!htb]
\centering
\includegraphics[width=.75\textwidth]{intro_principle.pdf}
\caption{
Left: Stain normalization based on conventional GAN approaches. For each staining a separate model has to be trained to normalize many stainings to the target domain. Right: Stain normalization with MultiStain-CycleGAN, which is trained on one staining and can normalize any H\&E staining of the same tissue type. Dotted arrows indicate the data needed for training the respective model, normal arrows show the inference path.
}
\label{fig:gan_normalization}
\end{figure*}
The gold standard of cancer diagnosis is histopathologic investigation of tissue. This involves microscopic examination of dissected and stained tissue to examine signs and characteristics of specific diseases. During dissection, the tissue is fixed in formaldehyde and embedded in paraffin \citep{Chatterjee2014-sy}. The following staining of the tissue sections serves to highlight the various structures and cells in the tissue \citep{Ghaznavi2013-zs}. For light microscopy, the tissue sections are routinely stained with hematoxylin and eosin (H\&E) \citep{Alturkistani2015-wz}. The staining of the tissue helps the pathologist to make diagnoses based on certain features such as cell morphology or the arrangement of cells \citep{Gurcan2009-pd}. Staining mainly depends on the formulation of the stain and the application time among other pipeline-dependent aspects \citep{Kothari2014-fu}.
After the tissue is stained, the slides are reviewed by pathologists. Both diagnosis and tumor grading are performed with the goal of providing prognosis and treatment recommendations \citep{Farahani2015-sk}.
With the advancement of technology and the rise of whole-slide imaging, i.e., the digitization of high-resolution microscopic images, digital pathology has rapidly gained importance \citep{Alturkistani2015-wz}. Digitizing the slides allows the use of automated systems for detection, classification or segmentation of a desired entity. Deep Learning (DL) and Convolutional Neural Networks (CNN) emerged as an effective tool in automatic image analysis, using big data to parameterize models that no longer rely on hand-crafted features \citep{LeCun2015-yu}. By using DL-based algorithms, pathologists can be relieved of monotonous and repetitive tasks by supporting them \citep{Echle2021-ek}. DL has already been successfully tested in various clinical tasks, such as tumor detection \citep{Cruz-Roa2017-ky}, mitosis detection \citep{Saha2018-cb,Albarqouni2016-ta}, grading of cancer \citep{Bulten2020-bz}, predicting the lymph sentinel status \citep{Kiehl2021-um}, patient survival estimation \citep{Wessels2022-ly} or tumor subtyping \citep{Wang2020-ai}. \\
The appearance of slides is highly variable as a result of different scanners, staining techniques, and laboratories \citep{Ciompi2017-qd}. This variability is not a problem for pathologists \citep{Bancroft2008-gk}, but current deep learning algorithms have significant issues with this \citep{Ciompi2017-qd}. Even very small changes in the image can lead to large deviations in performance for DL-based algorithms \citep{Kurakin2016-ti}. This is especially true for domain shifts, where a different input data distribution can lead to reduced performance and in turn potentially harm the patient \citep{Stacke2021-nu}. As early as 1994, Lyon et al. postulated that the standardization of dyes and stains will play an increasingly important role in the future \citep{Lyon1994-dy}. However, not all differences are due to non-standardized processes and thus not all variations are avoidable \citep{Niethammer2010-tt}. In conclusion, every tissue source site e.g. medical center or clinic, has a distinct signature due to biological variations in patients treated at various centers, specimen acquisition, staining, and digitization. On the one hand, this center-specific signature leads to biases in the data, which many algorithms suffer from; on the other hand, it can be used to determine the source of a whole slide image (WSI). The origin of the WSI can then be used to draw conclusions about the patient demographics, such as age, nationality and ethnicity. DL is able to determine the origin of a WSI with high accuracy \citep{Howard2021-lw}. This means that patient data privacy is no longer guaranteed and also enables the misuse of this information. To integrate DL into the work of pathologists and clinicians, methods that make these algorithms robust and stain-invariant must be developed, as well as new approaches that can remove the center-specific signature. Stain normalization is one possible method for achieving this objective.

\subsection{Stain normalization}
\label{stain_normalization}

Methods for normalization of histological slides have already been shown to be effective for some applications \citep{Ciompi2017-qd}. These normalization methods transform images $x$ of a domain $\mathcal{X}$ to look like they originated from a target domain $\mathcal{Y}$ or to match the appearance of a template image $y$. Because of this, the field of stain normalization is a very active field, which tries to map images from a source domain to a target domain. In this regard, Salvi et al. divides the field into the three areas: Global color normalization, color normalization after stain separation, and Deep Learning based normalization \citep{Salvi2021-nh}.
Methods based on global color normalization apply procedures that use the statistics of a template image and obtain a transformation from it, such as the global color transformation using Principal Component Analysis (PCA) by \citep{Reinhard2001-qk} or histogram specification proposed by \citep{Gurcan2009-pd}. In methods based on stain normalization after stain separation, the individual staining components, usually hematoxylin and eosin, are separated. This technique makes use of the property that the two stains can be linearly separated by a transformation into optical density space \citep{Roy2018-ed}. Each pixel can then be calculated by the product of a stain color appearance matrix, which is acquired by a template image,  and the stain density map \citep{Salvi2021-nh}. The estimation of the appearance matrix can be based on singular value decomposition as described by \citep{Macenko2009-yu}, prior information \citep{Ruifrok2001-ll}, non-negative matrix factorization \citep{Vahadane2016-kj} or spectral matching \citep{Tosta2019-af}.
More recent approaches rely increasingly on neural networks. Generative Adversarial Networks (GAN) are used to normalize stains and show promising results \citep{Zanjani2018-xi, Bentaieb2018-ro}. Following the work of \citep{Gatys2016-ss}, stain normalization is treated as neural style transfer, where the goal is to give an input image the appearance of a learned distribution of images. GANs are deep generative models which consist of two networks: A generator which generates images and a discriminator which tries to separate the generated images from the actual images corresponding to the distribution of the training data. The training is a minimax game in which the two models compete with each other. The goal of the generator is to generate images from a noise vector \(z\) such that the distribution of the generated images \(P_{G}(z)\) corresponds as closely as possible to the distribution of the training data \(P_{data}(x)\). The loss function can be described as:
\begin{equation}
\begin{split}
\min_{G}\max_{D} V\left(G,D\right) = {} &\mathbb{E}_{x\sim p_{data}\left(x\right)} \left[\log{\left(D_{x}\right)}\right] + \\
                             & \mathbb{E}_{z\sim p_{z}\left(z\right)} \left[\log{\left(1-D\left(G\left(z\right)\right)\right)}\right].
\end{split}
\end{equation}
The generator tries to minimize the loss function, while the discriminator tries to maximize it. The models are trained until they reach an optimum \citep{Goodfellow2014-rt}.
\citep{Isola2017-nl} extends this approach by passing an image instead of a noise vector z as input to the generator. This allows images to be transferred to another domain, which is essential for the normalization of histological stains. However, the disadvantage of this approach is that image pairs are required. In histopathology, it is rare for the same slide to be re-stained multiple times, so this approach is of limited use. Salehi et al. circumvent this drawback by converting images to gray-scale images, thus generating image pairs synthetically \citep{Salehi2020-sg}. Due to the missing image pair problem, more work has been directed towards cycle-consistent adversarial networks (CycleGANs), proposed by \citep{Zhu2017-pb}, which no longer require image pairs by using cycle-consistency. Approaches based on CycleGAN are particularly suitable for the field of image-to-image translation in histopathology. CycleGAN and its variants have already demonstrated in several studies that they are suitable for stain-to-stain translation or normalization tasks \citep{Shaban2019-ce,De_Bel2021-io,Runz2021-bg,Zhou2019-is}.
\subsection{Multi-domain stain normalization}
\label{multi_domain}
The majority of previous literature focuses on transfer between two stains, but not on a many-to-one approach, which offers more flexibility in real-world settings. One-to-one approaches require to train a new model whenever stains from a new domain have to be normalized, see Fig. \ref{fig:gan_normalization}. Furthermore, they depend on the local availability of the data to perform the normalisation. In privacy-preserving settings such as federated or swarm learning, this is not the case. For this reason, we introduce MultiStain-CycleGAN, an unsupervised multi-domain capable stain normalization method based on CycleGAN. The method presented here follows a comparable approach as described \citep{Tellez2019-fo} but with the additional reconstruction of the input image to ensure the integrity of the image structure through the cycle consistency condition. In doing so, we reformulate the stain normalization task into an image-to-image translation task, in which heavily augmented input images are subjected to gray-scale conversion and transformed into the desired stain. The network learns to reconstruct images from gray images with different contrasts, which have the appearance of the learned staining and thus perform stain normalization. Our method is tested for several properties including tumor classification, domain classification, image quality of generated images and distribution shift after normalization.
Our contributions can be summarized to:
\begin{itemize}
  \item Developing MultiStain-CycleGAN, a robust deep learning  based multi-domain approach for stain normalization without the need for retraining to normalize untrained stainings.
  \item Achieving low accuracy on tissue source site classification to remove spurious domain factors and thus improving data privacy  while generating images with the highest SSIM index and retaining tumor prediction accuracy
  \item Detailed analysis of the studied normalization methods in terms of their ability to improve a downstream task, their image quality and their ability to disguise the origin of the images, as well as the influence of different data augmentation intensities.
\end{itemize}

The following parts of this work are structured as follows: Chapter \ref{sec:materials} introduces the datasets and their attributes. In addition, it gives a description of how the data is acquired, preprocessed and stratified. Chapter \ref{sec:methods} explains stain normalization with CycleGAN and how we derived a multi-domain approach from it. Furthermore, the metrics used to measure the distribution shift and the image quality of the normalized images as well as the used neural networks are explained. Chapter \ref{sec:experimental_setup} describes the experimental setup and chapter \ref{sec:results} lists the results in detail. Afterwards the results are discussed and placed into context in chapter \ref{sec:discussion}. Chapter \ref{sec:conclusion} provides a concluding summary and identifies research gaps for future work.

\section{Materials}
\label{sec:materials}
\begin{figure*}[!htb]
\centering
\includegraphics[width=.75\textwidth]{slide_overview.pdf}
\caption{
Example slides for the different domains from the CAMELYON17 dataset. The images a)-e) show examples of tissue sections of the different centers with their different stainings: a) CWZ; b) RST; c) UMCU; d) RUMC; e) LPON.
}
\label{fig:slides}
\end{figure*}
The CAMELYON 17 Challenge dataset \citep{Bandi2019-rv} consists of whole slide images originating from five different medical centers, digitized with three different scanners. The five centers are: Radboud  University  Medical  Center (RUMC), Canisius-Wilhelmina  Hospital (CWZ), University  Medical  Center  Utrecht (UMCU), Rijnstate  Hospital  in  Arnhem  (RST) and Laboratory  of  Pathology  East-Netherlands (LPON). The dataset provides the domain shift we require for our investigation of stain normalization. The dataset encompasses a total of 500 breast tissue WSIs, 50 of them with annotations at lesion level. Examples for the appearance of the different stainings of the different domains are visualized in Fig. \ref{fig:slides}. All in all, this dataset allows us to make valid statements about the proposed normalization method and the quality of the normalized images. The 50 lesion-level annotated slides were primarily used to evaluate tumor classification, and the remaining slides were then used to classify the tissue submitting site, image quality, and determine the distance between the target and source domains. For the preprocessing of the tile-based approach, we utilized our self-developed publicly available pipeline\footnote{https://github.com/DBO-DKFZ/wsi\_preprocessing} for the extraction of tiles from WSIs and a subsequent filtering by tissue presence according to \citep{Khened2021-ti}.  We employed a configuration such that each tile had a spatial extent of \(64\times64\ \mu m\) and a resolution of \(256\times256\) pixels. Furthermore, we sampled the tiles with an overlap of 25\% for non-annotated and 50\% for annotated tissue. For the evaluation of our multi-domain stain normalization, we chose CWZ as the target domain.
\subsection{Normalization Network}
Our MultiStain-CycleGAN required tiles from two of the five domains for training. In our experiments, we arbitrarily chose the two centers CWZ and LPON. For the training we used about 240 000 tiles from center CWZ and about 270 000 tiles from the center LPON. The tiles were extracted only from the slides containing lesion level annotations, i.e. 10 slides per center.
\subsection{Tumor classifier}
For the tumor classifier, we used a 5-fold cross-validation. The folds were stratified according to the class 'tumor' or 'non-tumor'. In training, we only used data from the target domain with lesion-level annotations, with each fold containing 39 000 tiles, resulting in 195 000 for the total number of train images. Of these, a total of 24 000 tiles belong to the 'tumor' class. For the test set, the target domain CWZ was omitted because in this work we only focused on images with domain shift for tumor classifier performance. For the remaining centers, we decided to use 5000 stratified randomly drawn tiles of both classes, resulting in a total test set of 40 000 tiles for the tumor classifier.
\subsection{Domain classifier}
Also for the training of the domain classifier we decided to use a 5-fold cross-validation, stratified by centers. Each training fold contains 290 000 tiles, in total about 1430 000 tiles, which were extracted from the 50 slides with lesion-level annotations. The test set consists of a total of 25 000 tiles, composed of 5 000 tiles per center. The test set is based on tiles from the 90 slides without lesion-level annotations, which have not been used in the evaluation before.

\section{Methods}
\label{sec:methods}
This section introduces the general methods needed for this work such as CycleGAN and stain normalization. Then, we present how we derived MultiStain-CycleGAN and how we perform stain normalization. Furthermore, we explain how we conduct the study. Last but not least, we describe the used performance metrics.
\subsection{Cycle-consistent adversarial networks}
\begin{figure}[!t]
\centering
\includegraphics[scale=.135]{cycleGAN.pdf}
\caption{The principle of image-to-image translation with CycleGAN proposed by Zhu et al. An image from a domain $\mathcal{X}$ is mapped to a domain $\mathcal{Y}$ by a generative model. After the mapping the image will be reconstructed into its original domain and the cycle-consistency loss is computed, enabling unpaired image-to-image translation.
}
\label{fig:cycleGAN}
\end{figure}
Cycle-consistent adversarial networks proposed by Zhu et al. learn a mapping from a domain $\mathcal{X}$ to a domain $\mathcal{Y}$ using training data \(x_i \in X\) and \(y_i \in Y\). Where $X$ and $Y$ denotes the respective datasets of the domains. In Fig. \ref{fig:cycleGAN}, the two mappings are illustrated with \(G : \mathcal{X} \to \mathcal{Y}\) and \(F : \mathcal{Y} \to \mathcal{X}\). The domain-dependent adversarial discriminators \(D_x\) and \(D_y\) learn whether the input image is a generated image \(G(x)\) or \(F(y)\) or a sample \(x\) or \(y\) from the distribution of the training data \citep{Zhu2017-pb}. Here, the objective function contains several loss terms. Among them are adversarial losses \(L_{D_x}\) and  \(L_{D_y}\), to learn matching the distribution of generated and train data \citep{Goodfellow2014-rt} and a cycle-consistency loss \(L_{rec}\), which helps to preserve the structure of input images, as well as identity losses \(L_{idt_x}\) and \(L_{idt_y}\), which help to keep the color palette close to the input image \citep{Zhu2017-pb}.
The two adversarial losses are applied to the two mapping functions $G$ and $F$. For example, the adversarial loss for the function \(G : \mathcal{X} \to \mathcal{Y}\) with its discriminator \(D_y\) can be expressed as follows:
\begin{align}
\begin{split}\label{eq:gan}
L_{GAN}\left(G,D_y,X,Y\right) ={}& \mathbb{E}_{y\sim p_{data}(y)} \left[\log\left(D_{y}(y)\right)\right] + \\ &\mathbb{E}_{x\sim p_{data}(x)} \left[\log\left(1-D_y\left(G\left(x\right)\right)\right)\right].
\end{split}
\end{align}
Here, the generator $G$ tries to generate images $G(x)$ that appear as if they originate from the distribution $Y$, while the discriminator $D_y$ tries to distinguish the generated samples $G(x)$ from the real samples $y$. This process is repeated for the function \(F: \mathcal{Y} \to \mathcal{X}\) with \(L_{GAN}(F,D_x,Y,X)\)\citep{Zhu2017-pb}.
Adversarial training can theoretically learn mappings $G$ and $F$ such that the generated images correspond to the distribution of the respective target domains $\mathcal{X}$ and $\mathcal{Y}$. Furthermore, with a sufficiently large capacity of the model, it is possible to map the same input to several different outputs in the target domain. To reduce the solution space, Zhu et al. suggest that the mapping functions should be cycle-consistent. This behavior is enforced by the cycle consistency loss with:
\begin{align}
\begin{split}\label{eq:cycle_consistency}
    L_{cyc} \left( G,F,X,Y \right) ={} & \mathbb{E}_{x\sim p_{data} \left( x \right)} \left[ \| F \left( G \left( x \right) \right) - x \|_1 \right] +\\
   & \mathbb{E}_{y\sim p_{data}\left(y\right)} \left[ \|G \left(F\left(y\right)\right) - y \|_1 \right].
\end{split}
\end{align}
For certain tasks, including stain normalization, it is useful to add an identity loss which ensures that the mapping is consistent with the color of the input image. The two mapping functions $G$ and $F$ learn the identity function in case a sample from the real distribution represents the input image. This loss is described by:
\begin{align}
\begin{split}\label{eq:idt}
    L_{identity}\left(G,F,X,Y\right) ={}& \mathbb{E}_{y\sim p_{data}(y)}\left[||G(y)-y||_1\right]+\\
         & \mathbb{E}_{x\sim p_{data}(x)} \left[||F(x) - x||_1\right].
\end{split}
\end{align}
The complete objective function is therefore obtained as:
\begin{align}
\begin{split}
    L \left( G,F,D_x,D_y,X,Y \right) ={} & L_{GAN} \left( G,D_y,X,Y \right) + \\
                      & L_{GAN} \left( F,D_x,Y,X \right) + \\
                      & \lambda L_{cyc} \left( G,F,X,Y \right) + \\
                      & L_{identity} \left( G,F,X,Y \right)
\end{split}
\end{align}
\citep{Zhu2017-pb}.
\subsection{Multi-domain stain normalization with MultiStain-CycleGAN}
\begin{figure*}[!t]
\centering
\includegraphics[scale=.15]{multi_stain_principle.pdf}
\caption{
Overview of the MultiStain-CycleGAN. Images $x$ from a source domain  will be mapped to an intermediate domain by a function $H$. $H$ consists of a color augmentation function and a grayscale conversion.
The generator $G$ then transforms the gray image $w$ into the target domain. This process, including projecting $y'$ into the intermediate domain, is repeated for the normalized image $y'$ again, to reconstruct the original image. The second path has been omitted for clarity. Further, instead of feeding the network a real image from the respective domain for calculating the identity loss used by Zhu et al., a reconstruction task of unaugmented gray images $H'(x)$ is done. The intermediate domain allows to normalize any H\&E stains without having to re-train the model.
}
\label{fig:principle}
\end{figure*}
To convert CycleGAN into a many-to-one approach, we performed several modifications. To reduce the space of possible inputs and thus simplify the problem, the images are converted to 3-channel grayscale images. Thus, the new task for the two mapping functions $G$ and $F$ is the reconstruction of the RGB images of the respective domain from the gray-converted images. We hypothesize that if the reconstruction $F(G(x))$ and $G(F(y))$ is sufficiently good, the loss of information due to gray scale conversion will be compensated by the model and thus be valid.
In order to increase the variance of the input data and thus improve the generalization ability of the generators, an augmentation function is applied. The augmentation function $H$ then is obtained from the color augmentation and the gray value conversion. This function is essential to later normalize data outside the distribution of the raw training data. Depending on the intensity of the augmentation, more or less information can be lost in the image due to lack of contrast. The task of the generators changes to denoising and recoloring into the target domain. By applying the function $H$, the images are transformed into the intermediate domain $\mathcal{W}$, which represents the input space (see Fig. \ref{fig:principle}). The use of the intermediate domain $\mathcal{W}$ allows us to normalize a large variation of input images at inference time. Since the original identity loss task is no longer relevant in this setup, the additional task of reconstructing unaugmented grayscale images was added instead. This additional task allows to compensate for the noisy images that may result from strong contrast augmentations, thus focusing $G$ and $F$ on the normalization of color instead of the denoising task. This domain faithful reconstruction loss of the gray converted input image $x’$, $y’$ and the original image $x$, $y$ is:
\begin{align}
\begin{split}\label{eq:idt_rec}
    L_{idt_{rec}}(G,F,X,Y) ={}& \mathbb{E}_{y\sim p_{data}(y)} \left[\|G(y') - y\|_1\right]+\\
         & \mathbb{E}_{x\sim p_{data}(x)} \left[\|F(x') - x\|_1\right] .
\end{split}
\end{align}
Thus, the complete objective function for our model results in:
\begin{align}
    \begin{split}
        L\left(G,F,D_x,D_y,X,Y\right) ={}  &  L_{GAN}\left(G,D_y,X,Y\right)+\\
                                & L_{GAN}\left(F,D_x,Y,X\right)+\\
                                & \lambda_{cyc} L_{cyc}\left(G,F\right)+\\
                                & \lambda_{idt} L_{idt_{rec}}\left(G,F\right) .
    \end{split}
\end{align}
For our experiments, we choose $\lambda_{cyc}=10$ and $\lambda_{idt}=0.5$ as in the original implementation \citep{Zhu2017-pb}. The two generators $G$ and $F$ are each an adapted U-Net, which has proven to be a very effective architecture in various medical tasks \citep{Ronneberger2015-gz}. The network contains several downsampling, and respective upsampling blocks, which double the number of filters and halve the image dimensions respectively and vice versa. For our evaluation, we implemented a tile size of $256 \times 256$ and a filter count for the innermost block of $32$ proved effective. In the case of a downsampling block, the blocks consist of convolution layers and a leaky ReLu activation function with a slope $a = 0.2$ and an instance normalization layer described by \citep{Ulyanov2016-on}. In the case of an upsampling block, it consists of a transpose convolution layer, a ReLu activation function and an instance normalization layer.
The two discriminators are PatchGANs proposed by \citep{Isola2017-nl}, their loss can be interpreted as a kind of style loss. In addition, spectral normalization introduced by \citep{Miyato2018-cx} was used as a normalization layer to stabilize the training. The respective discriminator consists of three blocks, each consisting of a convolution layer, a leaky ReLu activation function and a normalization layer. The filter numbers increase quadratically with the depth of the discriminator. The least squares GAN (LSGAN) loss is used as loss, which allows a better image quality for generated images \citep{Mao2017-jg}. To further stabilize the training, and reduce oscillations \citep{Goodfellow2016-fn}, we implemented an image buffer as proposed by \citep{Shrivastava_undated-te}, which includes a history of generated images, of size 50. Since in our experiments we noticed a tendency of the discriminator loss to converge to zero, we introduced an update threshold to avoid this, which prevents a gradient update as soon as one of the discriminator losses falls below a threshold value. The threshold was set to 0.1.\\
For our training, we used the ADAM optimizer \citep{Kingma2014-kl} with a learning rate of $10^{-5}$ with a linear decay over 50 Epochs. We trained the MultiStain-CycleGAN for 100 epochs in total on a Nvidia V100. For the color augmentation we used the following factors: Saturation 0.75, brightness 0.75, contrast 0.5. Since we subject our images to gray conversion, changing the hue value has no effect on the output image. These parameters were determined empirically by visual inspection of test images. They were chosen in such a way that the morphology of the structures is largely preserved.
\subsection{Image quality and domain shift metrics}
For the evaluation of the image quality and the measurement of the domain shift of our normalization method, we chose the Structural Similarity (SSIM) Index \citep{Wang2004-ic} and the Fréchet Inception Distance (FID) \citep{Heusel2017-bc}, respectively. These metrics are intended to help evaluate the quality of the generated images and quantify the change in domain shift.
\subsubsection{Fréchet inception distance}
\label{subsub:fid}
In order to be able to make a statement about the domain shift before and after normalization and to evaluate different stain normalization methods with respect to their ability to reduce the domain gap, we decided to use the FID described by Heuse et al. The FID is an improvement over the Inception Score proposed by \citep{Salimans2016-qe} in terms of consistency with human perception as the disturbance of the image increases. We chose this metric because of its frequent application in generative tasks and the extensive evaluation of the method \citep{Xu2018-hx,Lucic2017-qn}. The FID represents the difference between two Gaussians consisting of the features of an inception model. The FID is given by:
\begin{equation}
    \text{FID}\left(\mu_X,\mu_Y,C_X,C_Y\right) = \|\mu_X-\mu_Y\|+ Tr\left(C_X+C_Y-2\sqrt{C_XC_Y}\right).
\end{equation}
Where the mean and covariance $\mu_X, C_X$ corresponds to the Gaussian of the generated data and $\mu_Y, C_Y$ corresponds to the Gaussian of the real world data. The FID is zero in case of matching images. \\
Due to the issue described by \citep{Liu2018-kq} that using an ImageNet model to project generated images of domains unrelated to ImageNet into feature space can be ineffective. Following the suggestion of Liu et al., we used the model of \citep{Ciga2022-fd} as a domain-specific encoder, which was trained on several histopathology datasets. The FID correlates with human visual perception and measures of how large the perceived difference is between images from two different distributions. In the stain normalization use case, a high FID means that there is a large domain shift. This domain shift, and thus the FID, should be reduced by stain normalization methods.
\subsubsection{Structural Similarity Index}
To compare the perceived structure before and after normalization, we utilize the Structural Similarity Index proposed by Wang et al. for our evaluation. The SSIM index compares two images in terms of their similarity and image quality. The SSIM index is 1 in case of two identical images. In contrast to the use of the Mean Squared Error (MSE) for the comparison of images, the SSIM index calculates contrast, structure and luminance separately and then combines them.  We chose this metric because it has already been used in stain normalization scenarios \citep{Hoque2021-bx, Shaban2019-ce} and due to the high importance of keeping structural features unaffected by normalization. Preserving the structure after normalization is essential, otherwise the morphology of the cells is altered. This can lead to errors in classification, as will be shown in chapter \ref{sec:results}. The SSIM is given by:
\begin{equation}
    \text{SSIM}\left(x,y\right) = \frac{\left(2\mu_x\mu_y+C_1\right)\left(2\sigma_{xy}+C_2\right)}{\left(\mu_x^2+\mu_y^2+C_1\right)\left(\sigma_x^2+\sigma_y^2+C_2\right)}.
\end{equation}
Where $\mu_x$ and $\sigma_x^2$ correspond to the mean and variance of the image $x$, respectively. $\sigma_{xy}$ corresponds to the covariance of the images $x$ and $y$, and $C_1$ and $C_2$ are constants to stabilize the denominator.
\subsection{Network-based metrics}
Image-based similarity metrics such as FID and SSIM can give clues about the visual similarity of the normalized pictures. However, they do not evaluate how well downstream classifiers perform on the normalized images. As the goal of stain normalization is to at least maintain task performance while ideally obscuring the origin of the slide, we additionally evaluate our approach with network-based metrics.
\subsubsection{Domain classifier}
\label{susubsec:tissue_classifier}
To verify that the respective normalization methods are able to disguise the tissue source site, we use an Xception classifier proposed by \citep{Chollet2017-gi} pre-trained on ImageNet to follow \citep{Howard2021-lw}. We measure accuracy because this is a balanced test dataset and we are interested in the clinic an image originates from. As described in chapter \ref{sec:materials}, we applied a 5-fold cross-validation to obtain an approximate distribution of accuracy and exclude outliers. Each model was trained with a learning rate of $10^{-4}$ and a batch size of 32 for 50 epochs. Due to very large performance differences of the discriminator with different levels of color augmentations in training, we decided to use a high intensity of color augmentation. We used color jitter with the parameters brightness: 0.7, contrast: 0.7, saturation: 0.7, hue: 0.5.
\subsubsection{Tumor classifier}
For tumor classification, we utilized a ResNet18 pre-trained on ImageNet. Analogous to the domain classifier, we trained the classifier with a learning rate of $10^{-4}$ and a batch size of 32 for 50 epochs. Again, we chose accuracy as the target metric  due to the testset having balanced classes, as described in chapter \ref{sec:materials}. Also with this classifier we could see very large performance differences depending on the intensity of the color augmentation that was used. Thus, we employed  the same parameters as described for the domain classifier in \ref{susubsec:tissue_classifier}.

\section{Experimental setup}
\label{sec:experimental_setup}
\subsection{Normalization}
\label{subsec:normalization}
\begin{figure}[!t]
\centering
\includegraphics[width=.45\textwidth]{templates.pdf}
\caption{The target domain representative template images from three different slides used for the template-based methods.}
\label{fig:templates}
\end{figure}
\begin{table*}[!ht]
\centering
\caption{Estimated mean and standard deviation of domain and tumor classifier accuracy for the different normalization methods analyzed. Furthermore, the mean SSIM index and its standard deviation as well as the FID for the tumor classifier dataset are shown.}
\vspace{5mm}
\label{tab:results_short}
\begin{tabular}{@{}llllll@{}}
                    & \parbox{3cm}{Domain Classifier\\ Accuracy} $\downarrow$ & \parbox{2.5cm}{Tumor Classifier\\ Accuracy} $\uparrow$& \parbox{2cm}{Sustained \\ performance}  & SSIM Index $\uparrow$ & FID $\downarrow$ \\ \toprule
Unnormalized        &$0.952_{\pm0.002}$& $0.901_{\pm0.002}$& - &$1$&$41.389$\\ \midrule
Macenko Template 1  &$0.818_{\pm0,016}$&$0.892_{\pm0.003}$& - &$0.907_{\pm0.089}$&$59.247$\\
Macenko Template 2  &$0.634_{\pm0.029}$&$0.832_{\pm0.008}$& - &$0.753_{\pm0.13}$&$50.550$\\
Macenko Template 3  &$0.829_{\pm0.012}$&$0.887_{\pm0.003}$& - &$0.897_{\pm0.099}$&$62.010$\\ \midrule
Reinhard Template 1 &$0.905_{\pm0.009}$&$0.900_{\pm0.005}$& \checkmark &$0.861_{\pm0.108}$&$35.310$\\
Reinhard Template 2 &$0.910_{\pm0.007}$&$0.904_{\pm0.006}$& \checkmark &$0.818_{\pm0.121}$&$41.720$\\
Reinhard Template 3 &$0.911_{\pm0.006}$&$0.899_{\pm0.005}$& \checkmark &$0.889_{\pm0.099}$&$33.910$\\ \midrule
Vahadane Template 1 &$0.852_{\pm0.019}$&$0.892_{\pm0.003}$& - &$0.898_{\pm0.096}$&$51.150$\\
Vahadane Template 2 &$0.605_{\pm0.040}$&$0.650_{\pm0.018}$& - &$0.674_{\pm0.149}$&$63.590$\\
Vahadane Template 3 &$0.855_{\pm0.012}$&$0.890_{\pm0.003}$& - &$0.900_{\pm0.094}$&$50.060$\\ \midrule
\textbf{MultiStain-CycleGAN}   &$0.701_{\pm0.016}$&$0.900_{\pm0.004}$& \checkmark &$0.957_{\pm0.034}$&$40.874$     \\ \bottomrule
\end{tabular}
\end{table*}
For all experiments, we trained our MultiStain-CycleGAN to learn the transformation $G: \text{CWZ} \to \text{LPON}$ and $F: \text{LPON} \to\text{CWZ}$. For simplicity, we examine only the normalization $F$. Due to the huge memory requirements of WSIs, we were forced to perform the evaluation in a tile-by-tile manner. Thus, in order to analyze all the criteria under consideration, both the domain dataset and the tumor classifier dataset have to be normalized using the normalization methods under investigation. To place our method in the context of existing literature, we compare it with other common normalization methods, which can be used in a multi-domain manner. We chose the methods of \citep{Macenko2009-yu}, \citep{Reinhard2001-qk} and \citep{Vahadane2016-kj} because of their frequent use in stain normalization in histopathology. Due to the template-based nature of these methods, we selected three representative templates shown in Fig. \ref{fig:templates} for these. This leads to three normalized datasets for each of the template-based approaches for the respective task. For the Machenko normalization and the Reinhard and Vahadane method, we utilized the implementations from torchstain\footnote{https://github.com/EIDOSLAB/torchstain} and staintools\footnote{https://github.com/Peter554/StainTools} respectively.
\subsection{Deep learning classifier}
\label{subsec:classifier_eval}
We trained each of the classifiers five times using different seeds. We trained our models with four different augmentation intensities to analyze the behavior of the studied methods considering color augmentation.  Since we use tiles of size $256 \times 256$ as input for the normalization methods as described in chapter \ref{sec:materials}, they were brought to the size $224 \times 224$ using a center crop in order to use the pretrained ResNet18 and the Xception model. For each task, the accuracy for each of the normalized and unnormalized datasets is determined for each of the five models.
\subsection{FID and SSIM index}
\label{subsec:fid_ssim}
We likewise use an open-source implementation\footnote{https://github.com/mseitzer/pytorch-fid} to calculate the FID and have modified it as described in section \ref{subsub:fid} to use a model trained on histopathological data. We calculated the FID for both the normalized domain and tumor classifier datasets by computing the distance between 40 000 random tiles from the 10 WSIs with lesion-level annotations of the target domain and the respective normalized dataset.\\
The SSIM index is calculated using image pairs compared to the FID. Here, for each of the normalized datasets, the SSIM index is calculated using the normalized image and the non-normalized image. Thus, for each of the datasets, we estimate a mean value and the associated standard deviation. For the calculation we use the implementation of scikit-image \citep{Van_der_Walt2014-br}.
\section{Results}
\label{sec:results}
\begin{figure*}[!ht]
 \centering
     \includegraphics[width=\textwidth]{normed_images.pdf}
     \caption{Examples of normalization of the different methods studied. Tiles are taken from slides of all centers. Our method achieves very good stain adaptation. Furthermore, the problems of the template-based normalization are shown by very different results depending on the template. }
     \label{fig:normed_images}
\end{figure*}
\begin{figure*}[!ht]
 \centering
     \includegraphics[width=0.9\textwidth]{domain_acc.pdf}
     \caption{The behavior of the domain classifier under different normalization methods over the two metrics SSIM index and FID. For each method, the five trained models are visualized. MultiStain-CycleGAN achieves the highest SSIM index while performing well in fooling the domain classifier. Macenko 2 and Vahadane 2 acquire the low accuracy of the domain classifier with a strong perturbation of the image content.}
     \label{fig:tissue_site_acc}
\end{figure*}
\begin{figure*}[!ht]
 \centering
     \includegraphics[width=\textwidth]{tumor_acc.pdf}
     \caption{The dependence of tumor classifier accuracy on SSIM index on the left and FID on the right. Each method is represented by the five models trained. It is shown that with decreasing SSIM index, tumor classifier performance decreases significantly. This is possibly due to loss of contrast and the associated structural changes and loss of information in the images. The result is similar for the FID, where accuracy decreases with increasing FID.}
     \label{fig:tumor_acc}
\end{figure*}
A summary of the results is given in table \ref{tab:results_short}. This includes the classifier results averaged over each of the five models for the heavy augmentation level, the mean SSIM index, and the FID. In addition, we introduce a check that indicates whether the ranges $\mu \pm \sigma$ of tumor classifier accuracy of the respective methods overlap with or exceed the range of the unnormalized case. Where $\mu$ denotes the estimated mean and $\sigma$ denotes the estimated standard deviation of the tumor classifier accuracy. This is then referred to as sustained performance. An overview of the normalization results of the different methods studied is provided by Fig. \ref{fig:normed_images}. This shows the original images and the normalized variant in each case. The images are from all of the centers available in the Camelyon17 dataset. For comparison, images of the target domain CWZ are given in \ref{fig:examples_images}. More tiles normalized with our method can be seen in \ref{fig:normalization_examples}. Here, the tiles are from the untrained centers RST, UMCU and RUMC. In the following, the results of domain classification will be discussed in more detail.
\subsection{Domain classification}
\label{subsec:tissue_site_results}
We examined the results of the tissue site classifier, or domain classifier, for the different normalization methods, as well as for the unnormalized case. A detailed overview of the different classification results of the domain classifier are given in table \ref{tab:detailed_domain_results}. \\
The domain could be estimated with very high accuracy of 0.952 in the unnormalized case. The Reinhard normalization still has a high accuracy of over 0.9 in all cases. The lowest accuracy was achieved by the Vahadane and Macenko normalization for template 2 with 0.605 and 0.634, respectively, followed by MultiStain-CycleGAN with an accuracy of 0.701. Fig. \ref{fig:tissue_site_acc} shows the accuracy of the domain classifier over the two metrics SSIM index and the FID. In the left plot, as well as in table \ref{tab:results_short}, it can be seen that the two methods that result in the lowest accuracy of the domain classifier also have a very low SSIM index. Further, our presented method achieves the highest SSIM index, with a value of 0.957. \\
In the right plot in Fig. \ref{fig:tissue_site_acc}, the accuracy of the domain classifier over the FID is shown. Again, the outlier character of the two methods Macenko Template 2 and Vahadane Template 2 can be seen. The two methods have by far the highest FID. Our method is placed in the middle and only slightly below the unnormalized data. In general, a trend emerges here, which shows that with increasing FID, the accuracy of the domain classifier also decreases, although our approach is somewhat out of line here.
\subsection{Tumor classification}
\label{subsec:tumor_acc_results}
The evaluation of the tumor classifier was performed analogously to the domain classifier. Again, a detailed listing of the results is given in the appendix in table \ref{tab:detailed_tumor}. The accuracy of tumor classification is relatively high at about 0.9 in all studied normalization methods as well as in the unnormalized case, with the exception of the methods Macenko Template 2 and Vahadane Template 2. These two methods have a significant loss in accuracy. Thus, for this task, no improvement in classifier performance is shown by applying the studied stain normalizations. \\
Fig. \ref{fig:tumor_acc} on the left shows tumor classifier accuracy as a function of the SSIM index. It can be seen that most methods have a very similar performance compared to the unnormalized case. Furthermore, several methods decrease the accuracy moderately to strongly compared to the unnormalized case.  This case can be observed especially when the SSIM index decreases strongly. On the right side of Fig. \ref{fig:tumor_acc}, tumor classifier accuracy over FID is visualized. The tumor classifier accuracy decreases with increasing FID. However, the trend here is less clear than in the case of the left plot.

\section{Discussion}
\label{sec:discussion}
As shown in Fig. \ref{fig:tumor_acc}, saturation effects occur for both metrics. It can be seen that the performance of the tumor classification is only significantly reduced when the SSIM index falls below a threshold. Similar results can be observed for FID, but the trend is somewhat more continuous. \\
As expected, a high FID and low SSIM index results in a significant performance loss of the tumor classifier. This possibly results from the fact that the two methods reduce the contrast too much, altering the morphology of the tissue. It follows that this is a severe loss of information. Due to the loss of essential information, the domain can no longer be estimated by the domain classifier. Interestingly, despite a mid-range FID, our method is significantly more capable than other methods in fooling the domain classifier, except for the two methods Macenko Template 2 and Vahadane Template 2. Thus, our method can beat the other methods by the highest SSIM index and comparatively very good ability to fool the domain classifier. This behavior is again supported by Fig. \ref{fig:domain_over_tumor_acc}, which shows a clear gap in domain classifier accuracy between our method and the other normalization methods, and at the same time a clear gap in tumor classifier accuracy to the two outlier methods. \\
Despite only slightly lower FID compared to the unnormalized case, our approach significantly lowered the accuracy of the domain classifier. Here, the visual perception and the FID drift apart, as one can see clear differences before and after normalization in Fig. \ref{fig:normed_images}. Thus, in our case, we see the FID only conditionally suitable to quantify domain shifts for histopathological data.
Furthermore, the metrics show that our method is able to normalize stainings that are not contained within the training set and thus can normalize different domains with one model without the need for retraining. This is supported by the high tumor classifier accuracy despite distribution shifts through the different centers showing how good the ability of our method is to normalize unseen domains in training.
\begin{figure}[ht]
 \centering
     \includegraphics[width=0.45\textwidth]{domain_acc_over_tumor_acc.pdf}
     \caption{The accuracy of the domain classifier over the tumor classifier accuracy of the different methods. MultiStain-CycleGAN is the only method that is able to both fool the domain classifier and maintain tumor classifier accuracy. Despite its frequent use, Macenko normalization in our case decreases tumor classifier accuracy in all cases. The Reinhard normalization provides a normalization that is very consistent, but does not offer the capability to fool the domain classifier. }
     \label{fig:domain_over_tumor_acc}
\end{figure}
We could not observe any significant improvement of the downstream task, in our case tumor classification, in the case of heavy data augmentation. This is partly consistent with the findings of \citep{Tellez2019-fo}. Here, however, it could be due to the task being too trivial to solve. Based on the tables \ref{tab:detailed_domain_results} and \ref{tab:detailed_tumor}, it can be seen that it is essential to investigate stain normalization methods considering color augmentation. The results show that when using no to moderate color augmentation, our normalization method can achieve high improvements, which however become smaller when using strong color augmentation. Thus, the domain classifier can be fooled much less with heavy color augmentation applied in training and the accuracy increases by more than 30\% compared to the use of no color augmentation.
A similar picture emerges for tumor classification, where our normalization provides an accuracy gain of over 10\% in the case of no color augmentation. In the case of medium color augmentation, we still achieve a slightly increased performance, which then disappears in the case of heavy color augmentation.\\
Another point that the results show is that template-based approaches, depending on the template chosen, can deliver very different solutions and associated performances with very high variances. Thus, the choice of an inappropriate template can lead to performance losses. GAN-based approaches have an advantage here, since they take the entire training dataset into account and can thus lead to more consistent solutions.\\
In the end, we can say that we can partially reproduce the results of \citep{Howard2021-lw} and extend them with a GAN-based approach. Also, our results show that despite the use of commonly used stain normalization methods, the domain can be predicted with high accuracy.  Our method is the exception here, as it results in a significant loss of domain classifier accuracy while maintaining high image quality.

\section{Conclusion}
\label{sec:conclusion}
We have presented MultiStain-CycleGAN, a new approach to stain normalization based on a modified CycleGAN, using an intermediate domain which works for multiple unseen stainings without the need to retrain and is thus multi-domain capable. We have extensively compared our approach with several commonly used normalization methods. We have intensively analyzed the different methods using different metrics and augmentation levels to understand the behavior of the methods under investigation. It has been shown that our method does not suffer from the problems of template-based approaches, and at the same time, in contrast to conventional GAN-based approaches, training a single model is sufficient. Furthermore, our method is best able to fool the domain classifier while providing the best image quality and high performance in the downstream task. In doing so, this work is a step towards disguising the origin of the tissue sections and reducing bias through the different domains. Continuing this work, other stainings such as IHC can be investigated. Furthermore, more complex downstream tasks should be analyzed, since in the case of our task none of the normalization methods led to an improvement in performance.

\section*{Acknowledgments}
The research is funded by the \textit{Ministerium für Soziales und Integration}, Baden Württemberg, Germany.

\bibliographystyle{unsrtnat}


\section{Motivation}

Climate change results in an increased probability of extreme weather events causing, among others, severe floods \cite{hallegatte2013future}, landslides \cite{kainthura2022hybrid}, and glacier collapses \cite{rounce2023global}. Such natural hazards can cause significant casualties, put critical infrastructures at risk of failure, and decrease the quality of human lives.
Near real-time mapping of natural hazards is emerging priority for the support of natural disaster relief, risk management, and informing governmental policy decisions.

Advances in deep learning (DL) have resulted in a set of tools for earth monitoring \cite{zhu2017deep,wang2022self}. For instance, DL models have shown their advantages for land cover classification tasks \cite{wang2020weakly} and segmentation of floods \cite{fraccaro2022deploying}.
However, these approaches are designed for one specific task in one geographic region based on specific frequency bands of satellite data.
Therefore, DL models used to map specific natural hazards struggle with their generalization to other types of natural hazards in unseen regions (see \cite{lunga2021resflow}).
Therefore, adapting DL models to, for example, unseen natural hazards requires additional data labeled. Data annotation takes a significant amount of time, prolongs model fine-tuning, and generates additional costs.

In this work, we propose a methodology to significantly improve generalizability of DL natural hazards mappers based on pre-training on a suitable pre-task. Our approach supports the development of foundation models for earth monitoring, such as \cite{sun2022ringmo}, with the objective of directly segmenting unseen natural hazards across unseen geographic regions.
Our contributions are as follows: First, we demonstrate across four U-Net architectures that our approach significantly improves the generalizability of DL models for the segmentation of unseen natural hazards. Second, we show that our approach generalizes over novel geographic regions and different frequency bands of satellite data without access to data from the target domain.
Third, by leveraging characteristics of unlabeled images from the target domain that are publicly available, our approach is able to further improve the generalization behavior without fine-tuning.

\section{Methodology}

In contrast to previous generations of geospatial DL models that are, if at all, pre-trained on the natural image domain (e.g., MS-COCO), we propose to pre-train models on a more suitable pre-task.
In particular, we select the localization of buildings in the xBD dataset \cite{gupta2019xbd} as a suitable pre-task due to the dataset size and geographic diversity allowing us for an extensive pre-training on a simple localization task.

For training, we follow the settings proposed in the xView2 challenge \cite{durnov2020xview}: We utilize the well-established U-Net architecture with ResNet-34 \cite{he2016deep}, SeNet-154 \cite{hu2018squeeze}, SeResNeXt-50 \cite{hu2018squeeze,xie2017aggregated}, DPN-92 \cite{chen2017dual} as backbones and a weighted combination of focal and dice loss. All models are pre-trained over 50 epochs with early stopping by means of AdamW optimizer with learning rate of 0.00015. We apply a threshold to each mask produced by our models to classify pixels as \textit{background} or \textit{natural hazard}. This threshold is determined by the 95\% percentile of the pixel distribution per image.

After pre-training, we evaluate the generalization properties of the models on three downstream tasks. In particular, we evaluate the performance of our models on the segmentation of flood events from the Sen1Floods11 dataset \cite{bonafilia2020sen1floods11} (composed of 430 satellite images by Sentinel-1 capturing eleven globally-distributed flood events), the segmentation of fractures in glaciers from the Antarctic fracture detection dataset \cite{lai2020vulnerability} (consisting of 38 satellite images of six antarctic glaciers with fractures), and the segmentation of landslides from the HR-GLDD dataset \cite{meena2022hr} (containing 1,758 landslide instances from ten globally-distributed regions). These datasets consist of satellite images of unseen natural hazards in novel geographic regions and comprise different frequency bands. This setting allows us to holistically evaluate the generalization of the models.

For benchmarking, we compare the performance of our models with two different random baselines (i.e., uniform noise and masks generated by randomly initialized U-Net models) and the well-established segmentation model DeepLabV3 \cite{chen2017rethinking}.
We evaluate the generalizability in two settings: without any domain adaptation and when unsupervised domain adaptation was applied.
Therefore, for unsupervised domain adaptation, we make use of the available unlabeled data to update the statistics of the batch normalization layers of our models and thereby adapt our models to the domain of the downstream tasks. We evaluate different scenarios as part of $k$-shot adaptation (i.e., including $k \in \{1, 5, 10, 50\}$ unlabeled images from the target domain).
For evaluation, we calculate balanced accuracy, IoU, and F1 Score. Since the two classes of natural hazard and background are highly imbalanced but equally important for achieving the task, we only report balanced accuracy.

\section{Evaluation of Results}
In Figure \ref{fig:eval-results}, we present our results. First, we find that the performance of DeepLabV3 pre-trained on the MS-COCO dataset does not significantly vary from random performance for the segmentation of natural hazards. Unsurprisingly, the model predicts each pixel to belong to the background class as none of the classes encountered in pre-training are part of the target domain. Thus, DeeplabV3 does not generalize to the segmentation of natural hazards and requires fine-tuning.
Second, without access to any data from the target domain and across different unseen geographic regions, we confirm that performance of all four models is significantly better than the baselines for the segmentation of landslide and fractures in glaciers performing one-tailed Wilcoxon Rank tests with 0.01 significance level. For the segmentation of floods, two out of four models are significantly better than the baselines.
Third, by utilizing unlabeled images as part of the unsupervised domain adaptation, we observe a general trend. For the majority of the models, an increase in the number of unlabeled images for unsupervised domain adaptation leads to improvement of the model performance.
We only observe individual performance drops (e.g., zero-shot adaptation vs. 5-shot adaptation of SeNet-154 in Figure \ref{fig:antarctic}). This can be explained by non-optimal thresholding based on changing mask distributions.

\begin{figure}[ht]
     \centering
        \begin{subfigure}[b]{0.33\textwidth}
        \tiny
        \begin{tabular}{l S[table-format=1.2]S[table-format=1.2]S[table-format=1.2]S[table-format=1.2]}
        \toprule
              {\# images} & {ResNet-34} & {SeNet-154} & {SeResNeXt-50} & {DPN-92} \\
              \midrule
              0 & 0.5278 & 0.5120 & 0.5468*** & 0.6147*** \\
              \midrule
              1 & 0.5359 & 0.5089 &	0.5483 & 0.6197 \\
              5 & 0.5677 & 0.5147 &	0.5529 & 0.6345 \\
              \bottomrule
             \end{tabular}
         \centering
         \includegraphics[width=1\textwidth]{figures/sen1flood11_bal_acc_perc_thr.pdf}
         \caption{Sen1Floods11}
         \label{fig:sen1floods11}
     \end{subfigure}
     \vspace{0.5cm}
     \begin{subfigure}[b]{0.33\textwidth}
        \tiny
        \begin{tabular}{l S[table-format=1.2]S[table-format=1.2]S[table-format=1.2]S[table-format=1.2]}
        \toprule
              {\# images} & {ResNet-34} & {SeNet-154} & {SeResNeXt-50} & {DPN-92} \\
              \midrule
              0 & 0.6443*** &	0.7366*** & 0.6641*** & 0.6244*** \\
              \midrule
              1 & 0.6573 &	0.7119 & 0.6603 & 0.6220 \\
              5 & 0.6605 &	0.6162 & 0.6748 & 0.6183 \\
              \bottomrule
             \end{tabular}
           \centering
         \includegraphics[width=1\textwidth]{figures/glaciers_bal_acc_perc_thr.pdf}
         \caption{Antarctic Glaciers}
         \label{fig:antarctic}
     \end{subfigure}
     \vspace{0.5cm}
     \begin{subfigure}[b]{0.33\textwidth}
         \tiny
        \begin{tabular}{l S[table-format=1.2]S[table-format=1.2]S[table-format=1.2]S[table-format=1.2]}
        \toprule
              {\# images} & {ResNet-34} & {SeNet-154} & {SeResNeXt-50} & {DPN-92} \\
              \midrule
              0 & 0.6110*** & 0.6024*** & 0.5633*** & 0.5523*** \\
              \midrule
              1 & 0.6147 & 0.6021 &	0.5736 & 0.5508 \\
              5 & 0.6177 & 0.5896 & 0.5554 & 0.5396 \\
              \bottomrule
             \end{tabular}
         \centering
         \includegraphics[width=1\textwidth]{figures/landslide_bal_acc_perc_thr.pdf}
         \caption{Landslide}
         \label{fig:landslide}
     \end{subfigure}
     \caption{Generalizability of four U-Net models pre-trained on building localization in satellite images on three segmentation downstream tasks: (a) flood mapping, (b) fractures in glaciers, and (c) landslide mapping. Graphs depict mean $\pm$ std over 5 seeds, *** stands for statistically significant performance.}
     \label{fig:eval-results}
\end{figure}

For the Sen1Floods11 dataset, we observe that without access to any information from the target domain (i.e., zero-shot adaptation), the DPN-92 model achieves a balanced accuracy score of 61.47\%, as shown in Figure \ref{fig:sen1floods11}. When adapting the model to the target domain, the performance increases up to 65.72\% given 50 unlabeled images from the target domain.
For the segmentation of fractures in glaciers shown in Figure \ref{fig:antarctic}, the ResNet-34 model achieves a score of 64.43\% in the zero-shot adaptation, This score is increased up to 71.42\% with 50-shot adaptation.
Finally, for the segmentation of landslide, the ResNet-34 model achieves an initial performance of 61.10\% that is improved up to 62.63\% with 50 unlabeled images from the target domain as depicted in Figure \ref{fig:landslide}.

\section{Conclusion}

In this work, we demonstrate that a suitable pre-training improves the generalization of DL models for segmentation of unseen natural hazards.
Importantly, our approach is not limited to a specific frequency band or geographical region. Our results show that unsupervised domain adaptation can improve the performance of all considered models based on very few unlabeled samples.

\bibliographystyle{IEEEbib}