$([x:y:z],(u,v))\mapsto ([xu:yu:z],(u,v))$ and $([x:y:z],(u,v))\mapsto ([2x:(u+1)y+(u-1)z:(u-1)y+(u+1)z],(u,v))$ provide two birational maps
$\psi\colon X_1\rat X_2$ and $\psi'\colon X_1\rat X_2'$ over $\A^2$.

Choosing $\Delta\subset \A^2$ to be the line $\{u=0\}$, the result of Lemma~\ref{lem:FlatConicFibDisc} does not hold for $\psi$ and for $\psi'$, because a general fibre of  $\eta_1^{-1}(\Delta)\to \Delta$ is a smooth conic. In both cases, exactly one hypothesis is not satisfied.
Namely, the multiplicity of the discriminant of $\eta_2$ along $\Delta$ is $2$ instead of $1$, and the surface $\eta_2'^{-1}(\Delta)$ is not irreducible.
\end{example}

The idea of the proof of the following statement was given to us by C. B\"ohnig and H.-C. Graf von Bothmer.

\begin{proposition}\label{pro:Isogenies}
Let $B$ be a smooth surface, and for $i=1,2$, let $\eta_i\colon X_i\to B$ be a standard conic bundle with discriminant a smooth irreducible curve $\Delta_i\subset B$.
Assume that there exists a commutative diagram
\[\begin{tikzcd}[link]
X_1\times Y \ar[dd,"\eta_1\times \id",swap]\ar[r,"\psi",dashed]& X_2\times Y\ar[dd,"\eta_2\times \id"]  \\ \\
B\times Y \ar[r,"\theta",dashed]& B\times Y
\end{tikzcd}\]
where $Y$ is smooth and $\psi$, $\theta$ are birational.

Then, for a general point $p\in Y$, the image of $\Delta_1\times \{p\}$ is contained in $\Delta_2\times Y$ and the morphism $\Delta_1\to \Delta_2$ obtained by composing
\[\Delta_1 \iso  \Delta_1 \times \{p\}  \stackrel{\theta}{\rat} \Delta_2 \times Y\stackrel{\pr_1}{\longto} \Delta_2\]
is surjective $($here $\pr_1\colon \Delta_2\times Y\to \Delta_2$ is the first projection$)$.
\end{proposition}

\begin{proof}
For $i=1,2$, the discriminant divisor of $\eta_i$ is reduced \cite[Corollary 1.9]{sarkisov}, so consists of $\Delta_i$. As $\Delta_i$ is smooth, $\eta_i^{-1}(p)$ is the union of two distinct lines for each $p\in \Delta_i$ (Proposition~\ref{pro:CBDivisorSingFibres}). Since $\rho(X_i/B_i)=1$, the preimage $\eta_i^{-1}(\Delta_i)$ is irreducible.
The morphism $(X_i\times Y)/(B\times Y)$ is a standard conic bundle whose discriminant divisor is reduced, consisting of the smooth hypersurface $\Delta_i\times Y\subset B\times Y$.

We choose a dense open subset $U\subseteq B\times Y$ on which $\theta$ is defined and whose complement is of codimension $2$ (since $B\times Y$ is smooth). In particular, $U\cap (\Delta_1\times Y)$ is not empty, so $U\cap (\Delta_1\times \{p\})\not=\emptyset$ for a general point $p\in Y$. After restricting the open subset, we can moreover assume that $\eta_1^{-1}(U)$ is a closed subset of $U\times\p^2$, given by the quadratic form induced by a matrix $M_1\in \GL_3(\C(U))$. The coefficients of the matrix can moreover be chosen in $\C(B)\subseteq \C(B\times Y)=\C(U)$, as the equation of $X_1\times Y$ in $\p^2\times Y$ is locally the equation of $X_1$ in $\p^2$, independent of $Y$.

We define $C\subset B\times Y$ to be image of $\Delta_1\times \{p\}$ by $\theta$, which is a point or an irreducible curve, as $\Delta_1$ is an irreducible  curve.
The aim is now to show that $C\subseteq \Delta_2\times Y$ and that $\pr_1(C)=\Delta_2$.
We choose an open subset $V\subseteq B\times Y$ intersecting $C$ such that $\eta_2^{-1}(V)$ is contained in $ \p^2\times V$ and is given by the quadratic form given by a symmetric matrix $M_2\in \Mat_{3\times 3}(\C(V))$. The morphism $\eta_2$ being flat, we can choose the coefficients of $M_2$ to be defined on $C$ and such that the residue matrix in $\widebar{M_2}\in \Mat_{3\times 3}(\C(C))$ is not zero. The birational map $\psi$ is locally given by
\[
\begin{tikzcd}[map]
U \times \p^2  & \rat & V \times \p^2\\
\left(u, \left[\begin{smallmatrix} x\\ y \\ z \end{smallmatrix}\right]\right)& \mapsrat & \left(\theta(u), A(u) \cdot \left[\begin{smallmatrix} x\\ y \\ z \end{smallmatrix}\right]\right)
\end{tikzcd}
\]
for some $A\in \GL_3(\C(U))$.  The explicit form of the map $\psi$ gives
\[\lambda\cdot M_1= \tr{A}\cdot \theta^{*}(M_2)\cdot A\]
where $\lambda\in \C(U)^*$ is a scalar and $\theta^{*}(M_2)$ is the matrix obtained from $M_2$ by applying to its coefficients the field isomorphism $\theta^{*}\colon \C(V)\to \C(U)$. As the rational map $\theta$ induces a dominant rational map $\Delta_1\times \{p\}\rat C$, we have a field homomorphism $\C(C)\to \C(\Delta_1\times \{p\})\simeq \C(\Delta_1)$, that we denote by $\bar\theta^*$. It induces a commutative diagram
\[\begin{tikzcd}[link]
\mathcal{O}_{C}(V) \ar[dd,swap]\ar[r,"\theta^*"]& \mathcal{O}_{\Delta_1\times \{p\}}(U) \ar[dd]  \\ \\
\C(C)  \ar[r,"\bar\theta^*"]& \C(\Delta_1\times \{p\})  \ar[r,phantom,"\simeq"]&[-4em] \C(\Delta_1).
\end{tikzcd}\]

We denote by $X'\subset U\times \p^2$ the subvariety given by the quadratic form associated to the matrix $\theta^{*}(M_2)$. We observe that the coefficients of $\theta^{*}(M_2)$ are defined over $\Delta_1\times \{p\}$ and that the residue gives a matrix $\widebar{\theta^{*}(M_2)}\in \Mat_{3\times 3}(\C(\Delta_1))$ which is obtained by applying the field homomorphism $\widebar{\theta^*}$ to the entries of
$\widebar{M_2}\in \Mat_{3\times 3}(C)$.
The morphism
$\pr_1\colon X'\to U$ is then an embedded conic fibration, which is flat after maybe reducing the open subset $U$ (but still having $U\cap (\Delta_1\times \{p\})\not=\emptyset$).

We can apply Lemma~\ref{lem:FlatConicFibDisc} to the birational map $X'\rat X$ given by \[
\left(u, \left[\begin{smallmatrix} x\\ y \\ z \end{smallmatrix}\right]\right) \mapsrat  \left(u, A(u)^{-1} \cdot \left[\begin{smallmatrix} x\\ y \\ z \end{smallmatrix}\right]\right)\]
and to $\Delta=\Delta_1\times \{p\}$.
Indeed, $(\eta_1 \times \id)^{-1}(\Delta_1\times \{p\})$ is irreducible as $\eta_1^{-1}(\Delta_1)$ is irreducible, and every fibre of $(\eta_1 \times \id)^{-1}(\Delta_1\times \{p\})\to \Delta_1\times \{p\}$  is the union of two distinct lines, as the same holds for $\eta_1^{-1}(\Delta_1)\to \Delta_1$ by  Proposition~\ref{pro:CBDivisorSingFibres}. Lemma~\ref{lem:FlatConicFibDisc}
gives two possibilities for the matrix $\bar\theta^*(M_2)\in \Mat_{3\times 3}(\C(\Delta_1))$: either it is of rank~$1$ (case \ref{GammaDiscNonRed}) or it is of rank~$2$, corresponding to a singular irreducible conic (case \ref{GammaDiscIrrpi}).
This gives the same two possibilities for $\widebar{M_2}\in \Mat_{3\times 3}(C)$ as $\bar{\theta}^*$ is a field homomorphism. As the rank of $M_2$ is smaller than~$3$, the variety $C$ is in the discriminant of $(X_2\times Y)/(B\times Y)$ and is thus contained in $\Delta_2\times Y$ as desired. It remains to see that $C$ is not contained in $\{q\}\times Y$ for some point $q$. Indeed, the preimage $(\eta_2\times \id)^{-1}(\{q\}\times Y)$ is isomorphic to $\eta_2^{-1}(\{q\})\times Y$, which is not irreducible, as $\eta_2^{-1}(\{q\})$ is the union of two lines (again by Proposition~\ref{pro:CBDivisorSingFibres}), but which is reduced.
\end{proof}

\subsection{Conic bundles associated to smooth cubic curves}
The principal result in this section is Proposition~\ref{pro:EnoughCB}, which provides a family of conic bundles that we shall use in the next section to prove Theorem~\ref{TheoremManyCB}.

\begin{lemma}\label{lem:ThreeConics}
For each $p=[\alpha:\beta]\in \p^1$, the set
\[\Sl_p=\{[x_0:x_1:x_2]\in \p^2 \mid \alpha x_0^2+\beta x_1x_2=\alpha x_1^2+\beta x_0x_2=\alpha x_2^2+\beta x_0x_1=0\} \]
consists of three points if $\alpha(\alpha^3+\beta^3)=0$ and is empty otherwise.
\end{lemma}
\begin{proof}
Since $\Sl_{[0:1]}=\{[1:0:0],[0:1:0],[0:0:1]\}$ and $\Sl_{[1:0]}=\emptyset$, we may assume that $\alpha\in \C^*$ and $\beta=1$.
If $[x_0:x_1:x_2]\in \Sl_p$, then $\alpha(x_0^3-x_1^3)=x_0( \alpha x_0^2+ x_1x_2)-x_1( \alpha x_1^2+ x_0x_2)=0$. The equations being symmetric, we get $x_0^3=x_1^3=x_2^3$. In particular $x_0x_1x_2\not=0$, so the three equations are equivalent to
\[\alpha=-\frac{x_1x_2}{x_0^2}=-\frac{x_0x_1}{x_2^2}=-\frac{x_0x_2}{x_1^2},\]
which implies that $\alpha^3=-1$.
For the three possible values of $\alpha$, we observe that $\Sl_{[\alpha:1]}=\{[1:x_1:-\alpha/x_1]\mid x_1^3=1\}$ consists of three points.
\end{proof}

\begin{lemma}\label{lem:Xxi}
For each $\xi\in \C$ such that $\xi^3\not=-\frac{1}{8}$, the hypersurface $X_\xi\subset \p^2\times \p^2$  of bidegree $(2,1)$ given by
\[
X_\xi=\Bigl\{([x_0:x_1:x_2],[y_0:y_1:y_2])\in \p^2 \times \p^2 \Bigm| \sum_{i=0}^2  (x_i^2+ 2\xi \frac{x_0x_1x_2}{x_i})y_i=0\Bigr\}
\]
is smooth, irreducible, rational over $\Q(\xi)$, and satisfies $\rho(X_\xi)=2$.
The second projection gives a standard conic bundle $X_\xi/\p^2$.
The discriminant curve $\Delta_\xi\subset \p^2$ is given by
\[
\]
and is the union of three lines if $\xi=0$ or if $\xi^3=1$, and is a smooth cubic otherwise.
\end{lemma}

\begin{proof}
To show that $X_\xi$ is smooth, irreducible, rational over $\Q(\xi)$ and that $\rho(X_\xi)=2$, it suffices to show that the first projection $X_\xi\to \p^2$ is a (Zariski locally trivial) $\p^1$-bundle.
This amounts to showing that the coefficients of the linear polynomial in the variables $y_i$  defining $X_\xi$ are never zero, i.e.~that for each $[x_0:x_1:x_2]\in \p^2$ we cannot have
$x_0^2+ 2\xi x_1x_2=x_1^2+ 2\xi x_0x_2=x_2^2+ 2\xi x_0x_1=0.$
This follows from Lemma~\ref{lem:ThreeConics} and from the hypothesis $\xi^3\not=-\frac{1}{8}$.

The equation of $X_\xi$ is given by
\[
( x_0 \, x_1 \, x_2 ) \cdot M \cdot \begin{pmatrix} x_0 \\ x_1 \\ x_2\end{pmatrix}=0
\text{ with }
y_0& \xi y_2& \xi y_1\\
\xi y_2& y_1& \xi y_0\\
\xi y_1& \xi y_0& y_2
\end{pmatrix} \in \Mat_{3\times 3}(\C[y_0,y_1,y_2]).
\]
The polynomial $\det(M)$ is equal to
\[\det(M)=\lambda (y_0^3+y_1^3+y_2^3)+\mu y_0y_1y_2,\text{ with }\lambda=-\xi^2\text{ and }\mu=2\xi^3+1.\]
In particular, the fibres of the second projection $X_\xi/ \p^2$ are all conics (the coefficients of $x_i^2$ is $y_i$ so not all coefficients can be zero) and a general one is irreducible.
As the threefold $X_\xi$ is smooth, irreducible and satisfies $\rho(X_\xi)=2$,  the morphism $X_\xi/ \p^2$ is a standard conic bundle. Its discriminant is given by the zero locus of $\det(M)$, which is a polynomial of degree $3$ which has the classical Hesse Form.
The discriminant corresponds to a smooth cubic if  $\lambda(27\lambda^3+\mu^3)\not=0$, and to the union of three lines in general position otherwise.
To prove this classical fact, we compute the partial derivatives of $\det(M)$, which are $(3\lambda y_0^2+\mu y_1y_2,3\lambda y_1^2+\mu y_0y_2,3\lambda y_2^2+\mu y_0y_1).$
By Lemma~\ref{lem:ThreeConics}, this has no zeroes in $\p^2$ if $\lambda(27\lambda^3+\mu^3)\not=0$ and has three zeroes otherwise. It remains to observe that $27\lambda^3+\mu^3=(8\xi^3+1)(\xi^3-1)^2$.
\end{proof}

\begin{remark}
Let $\k$ be a subfield of $\C$ and $\xi\in\k$. Then the curve $\Delta_\xi$ of Lemma~\ref{lem:Xxi} is defined over $\k$ and has a $\k$-rational point, namely the inflexion point $[0:1:-1]$.
When $\k=\C$, one can prove that all elliptic curves are obtained in this way; for smaller fields this does not seem to be true. We will however show that there are enough such curves.
\end{remark}

We thank P. Habegger for helpful discussions concerning the next lemma.

\begin{lemma}\label{lem:Isogenies}
Let $\k\subseteq \C$ be a subfield.
\begin{enumerate}
\item\label{jinvariant}
For each $\xi\in \k$,  with $\xi^3\notin \{0,-\frac{1}{8},1\}$, we denote $($as in Lemma~$\ref{lem:Xxi})$ by $\Delta_\xi$ the smooth cubic curve  defined over $\k$ given by
\[-\xi^2(y_0^3+y_1^3+y_2^3)+(2\xi^3+1)y_0y_1y_2=0.\]
The $j$-invariant of $\Delta_\xi$ is equal to
\[\left(\dfrac{16\xi^{12}+464\xi^9+240\xi^6+8\xi^3+1}{\xi^2(8\xi^9-15\xi^6+6\xi^3+1)}\right)^3.\]
\item
\label{isogenies}
There is a subset $J\subseteq \k$ having the same cardinality as $\k$ such that for all $\xi,\xi'\in J$, the following are equivalent:
\begin{enumerate}
\item
There exist surjective morphisms $\Delta_\xi\tto \Delta_{\xi'}$ and $\Delta_{\xi'}\tto \Delta_{\xi}$ defined over $\C$;
\item
\end{enumerate}
\end{enumerate}
\end{lemma}

\begin{proof}
\ref{jinvariant}.
By Lemma~\ref{lem:Xxi}, $\Delta_\xi$ is a smooth cubic curve if $\xi^3\notin \{0,-\frac{1}{8},1\}$.
We choose the inflexion point $[0:1:-1]\in \Delta_\xi$ to be the origin, make a coordinate change so that the inflexion line is the line at infinity, and thusly obtain a Weierstrass form. Then we compute the $j$-invariant as in \cite[\III.1 page 42]{silverman}; this is tedious but straightforward.
This can also be done using the formulas from \cite[page 240]{ArtebaniDolgachev}.

\ref{isogenies}.
Let $\xi,\xi'\in \k$ be such that $\xi^3,(\xi')^3\notin \{0,-\frac{1}{8},1\}$. We see the curves $\Delta_\xi$ and $\Delta_{\xi'}$ as elliptic curves defined over $\k$ with origin $O=[0:1:-1]$. Suppose that there is a surjective morphism $\phi\colon \Delta_\xi\tto \Delta_{\xi'}$ defined over $\C$. It sends the origin of $\Delta_\xi$ onto a $\C$-rational point of $\Delta_{\xi'}$. Applying a translation at the target, we can assume that $\phi(O)=O$, which means that $\phi$ is an isogeny, and that $\Delta_{\xi}$ and $\Delta_{\xi'}$ are isogenous over $\C$ (see \cite[Definition, \S III.4 page 66]{silverman}).

We now choose a sequence $p_1,p_2,\ldots$ of increasing prime numbers such that for each $i\ge 2$, the prime number $p_i$ does not appear in the denominator of the $j$-invariant of $\Delta_{p_{i'}}$ for each $i'<i$. For each $i\ge 1$, the  $j$-invariant of $\Delta_{p_i}$ is an element of $\Q$ having a denominator divisible by $p_i$ (follows from~\ref{jinvariant}), so $\Delta_{p_i}$ does not have potential good reduction modulo $p_i$ but this does not hold for $\Delta_{p_{i'}}$ for $i'>i$, which then has potential good reduction modulo $p_{i}$ \cite[Proposition 5.5, \S VII.5, page 197]{silverman}. This implies that there is no isogeny $\Delta_{p_i}\to \Delta_{p_{i'}}$ defined over any number field $K$ and where one curve has good reduction and the other has bad reduction \cite[Corollary 7.2, \S VII.7, page 202]{silverman}, and thus no isogeny defined over $\C$ \cite[Lemma 6.1]{MasserWustholz}.
If $\k$ is countable, this achieves the proof of \ref{isogenies}.

It remains to consider the case where $\k$ is an uncountable subfield of $\C$.
The set of $j$-invariants of curves $\Delta_\xi$, where $\xi\in \k$ is such that $\xi^3\notin \{0,-\frac{1}{8},1\}$, is then uncountable too.

We denote by $\Omega\subseteq \C^2$ the set consisting of pairs $(j_1,j_2)\in \widebar{\Q}^2$ such that the curves of $j$-invariants $j_1$ and $j_2$ are isogenous. The set $\Omega$ is a countable union of algebraic curves defined over $\Q$, given by the zero set of  the so-called modular transformation polynomials (see \cite[5\S3]{lang} and in particular \cite[Theorem 5, Chapter~5\S3, page 59]{lang}). Moreover, these curves are irreducible and invariant under the exchanges of variables $(x,y)\mapsto (y,x)$ \cite[Theorem 3, Chapter~5\S3, page 55]{lang}, so are not vertical or horizontal lines in $\C^2$.

We write  $S=\{\xi\in \k\mid \xi^3\notin \{0,-\frac{1}{8},1\}\}$.
Then, by the previous paragraph, for each element $\xi\in S$ the curve $\Delta_\xi$ is isogeneous (over $\C$) to only countably many isomorphism classes of $\Delta_{\xi'}$ with $\xi'\in\k$.
Putting an equivalence relation on $S$ saying that two elements are equivalent if the curves are isogeneous over $\C$ (see \cite[III.6, Theorem 6.1(a)]{silverman}), we obtain that each equivalence class is countable, so the set of equivalence classes has the cardinality of $S$, or equivalently of $\k$. This achieves the proof.
\end{proof}

\begin{proposition}\label{pro:EnoughCB}
Let $\k$ be a subfield of $\C$. For each $n\ge 3$, there is a set $J$ having the cardinality of $\k$ indexing decomposable conic bundles $X_i/B_i$ defined over $\k$, where $X_i,B_i$ are smooth varieties rational over $\k$, and such that two conic bundles $X_i/B_i$ and $X_j/B_j$ are equivalent $($over $\C)$ if and only if $i=j$.
\end{proposition}

\begin{proof}
We choose the set $J\subseteq \k$ of Lemma~\ref{lem:Isogenies}\ref{isogenies}, and consider, for each $\xi\in J$, the hypersurface $X_\xi\subset \p^2\times \p^2$ of Lemma~\ref{lem:Xxi}, which is given by
\[
X_\xi=\Bigl\{([x_0:x_1:x_2],[y_0:y_1:y_2])\in \p^2 \times \p^2 \Bigm| \sum_{i=0}^2  (x_i^2+ 2\xi \frac{x_0x_1x_2}{x_i})y_i=0\Bigr\}
\]
By Lemma~\ref{lem:Xxi}, the second projection gives a standard conic bundle $X_\xi\to \p^2$ whose discriminant curve $\Delta_\xi\subset \p^2$ is given by $-\xi^2(y_0^3+y_1^3+y_2^3)+(2\xi^3+1)y_0y_1y_2$.
Note that $(X_\xi \times \p^{n-3})/(\p^2\times \p^{n-3})$ (or simply $X_\xi/\p^2$ if $n=3$) is a decomposable conic bundle defined over $\k$, as it is embedded in the trivial $\p^2$-bundle $(\p^2\times \p^2\times \p^{n-3})/(\p^2\times \p^{n-3})$ by construction. Moreover, $X_\xi \times \p^{n-3}$ is birational to $\p^n$ over $\k$ (Lemma~\ref{lem:Xxi}).
By Proposition~\ref{pro:Isogenies}, two conic bundles $(X_\xi \times \p^{n-3})/(\p^2\times \p^{n-3})$ and $(X_{\xi'} \times \p^{n-3})/(\p^2\times \p^{n-3})$ are equivalent only if there exist surjective morphisms $\Delta_\xi\tto \Delta_{\xi'}$ and $\Delta_{\xi'}\tto \Delta_{\xi}$. This is only possible if $\xi=\xi'$, by Lemma~\ref{lem:Isogenies}\ref{isogenies}.
\end{proof}

\subsection{Proofs of Theorems~\ref{TheoremManyCB} and \ref{TheoremTame}}

\begin{proof}[Proof of Theorem~\ref{TheoremManyCB}]
By Theorem~\ref{TheoremBirMori}, we have respectively a group homomorphism and a groupoid homomorphism:
\[\begin{tikzcd}[link]
\Bir(\p^n) \ar[rr]&&\bigast_{C\in \CB(\p^n)} \left(\bigoplus_{\MC(C)}\Z/2\right)  \\ \\
\BirMori(\p^n)  \ar[uu,phantom,"\vertsubseteq"]\ar[uurr]&
\end{tikzcd}\]
For each subfield $\k\subseteq \C$, we can embed $\Bir_\k(\p^n)$ into $\Bir_\C(\p^n)$ and look at the image in $\bigast_{C\in \CB(\p^n)} \left(\bigoplus_{\MC(C)}\Z/2\right)$.
We  consider the set of decomposable conic bundles $X_i/B_i$ defined over $\k$ indexed by $J$  of Proposition~\ref{pro:EnoughCB}, which give pairwise distinct elements of $C_i\in \CB(\p^n)$, and associate to these birational maps $\psi_i\colon X_i\rat \p^n$ defined over $\k$.
For each $i\in J$, there is an involution $\iota_i\in\psi_i\Bir_\k(X_i/B_i)\psi_i^{-1}\subseteq \Bir_\k(\p^n)$ whose image in $\bigoplus_{\MC(C_i)}\Z/2$ is not trivial by Proposition~\ref{pro:largeimageAnyCB}. One can thus take a projection $\bigoplus_{\MC(C_i)}\Z/2\to \Z/2$ such that the image of $\iota_i$ is  non-trivial.
We obtain a surjective group homomorphism from $\Bir_\k(\p^n)$ to $\smash{\bigast_{i\in J} \Z/2}$ where $J$ has the cardinality of $\k$ and such that each involution $\iota_i\in \Bir_\k(\p^n)$ is sent onto the generator indexed by $i$. There is thus a section of this surjective group homomorphism.
\end{proof}

\begin{remark}\label{rem:product_and_sum}
As Proposition~\ref{pro:EnoughCB} gives an infinite image, the above proof naturally gives a surjective homomorphism to the group $\bigast_{J} (\bigoplus_\Z \Z/2)$, but since there is an abstract surjective homomorphism from $\bigast_{J}  \Z/2$ to this group, we chose not to mention the direct sum in the statement of the theorem.

Moreover, with the alternative form the existence of a section would be far less clear.
Indeed, $(\Z/2)^3$ does not embed in $\Bir(X/B)$ and $(\Z/2)^7$ does not embed in $\Bir(X)$, for $X$ rationally connected of dimension $3$ [71, 73], so it seems probable that $\bigoplus_\Z \Z/2$ does not embed in $\Bir(X)$ for any variety $X$.
\end{remark}

\begin{proof}[Proof of Theorem~\ref{TheoremTame}]
We consider a subfield $\k$ of $\C$, an integer $n\ge 3$, and a subset $S\subset  \Bir_\k(\p^n)$
of cardinality smaller than the one of $\k$.
We want to construct a surjective homomorphism $\Bir_\k(\p^n) \tto \Z/2$ such that the group $G$  generated by $\Aut_\k(\p^n)$, by all Jonqui\`eres elements and by $S$ is contained in the kernel.
We use the group homomorphism
\[\tau\colon \Bir_\k(\p^n) \to \bigast_J \Z/2 \]
given by  Theorem~\ref{TheoremManyCB}.
Each $j \in J$ corresponds to a conic bundle $X_j/B_j$.
The group $\Aut_\k(\p^n)$ is in the kernel of $\tau$.
The group of Jonqui\`eres elements is conjugated to the subgroup $J\subset \Bir(\p^1 \times \p^{n-1})$ consisting of elements sending a general fibre of $\p^1\times \p^{n-1}/\p^{n-1}$ onto another one.
The action on the base yields an exact sequence
\[ 1\to \Bir(\p^1 \times \p^{n-1}/\p^{n-1})\to J\to \Bir(\p^{n-1})\to 1.\]
This gives $J=\Bir(\p^1 \times \p^{n-1}/\p^{n-1}) \rtimes J'$, where $J'\subset J$ is the group isomorphic to $\Bir(\p^{n-1})$ that acts on $\p^1\times \p^{n-1}$ with trivial action on the first factor.
We can assume that $\p^1 \times \p^{n-1}/\p^{n-1} = X_{j_0}/B_{j_0}$ for some $j_0 \in J$. The image of $\Bir(\p^1 \times \p^{n-1}/\p^{n-1})$ by $\tau$  is contained in the group $\Z/2$ indexed by $j_0$.
Now observe that $J'\subset \Ker\tau$.
Indeed, we first decompose an element of $J'\simeq \Bir(\p^{n-1})$ as a product of Sarkisov links between terminal Mori fibre spaces $Y_i\to S_i$, where $Y_i$ has dimension $n-1$, and observe that taking the product with $\p^1$ gives Sarkisov links between the Mori fibre spaces $Y_i\times \p^1 \to S_i\times \p^1$ of dimension $n$.
Each of the Sarkisov links of type $\II$ arising in such decomposition has covering gonality $1$, as $\covgon(\Gamma\times \p^1)=1$ for each variety $\Gamma$.

We consider the group homomorphism
$\hat\tau\colon \Bir_\k(\p^n)\to \bigast_{J \setminus \{j_0\}}\Z/2$ obtained by composing $\tau$ with the projection $\bigast_{J}\Z/2\to \bigast_{J \setminus \{j_0\}}\Z/2$ obtained by forgetting the factor indexed by $j_0$.

The image by $\hat\tau$ of all Jonqui\`eres elements is trivial, hence the group $\hat\tau(G)$ has at most the cardinality of $S$, which by assumption is strictly smaller than the cardinality of $J$.
We construct the expected morphism by projecting from $\hat\tau(\Bir_\k(\p^n))$ onto a factor $\Z/2$ which is not in the image of $G$.
\end{proof}

\section{Complements}\label{sec:Complements}

\subsection{Quotients and SQ-universality}
\label{sec:SQ}

A direct consequence of Theorem~\ref{TheoremManyCB} is that we have a lot of quotients of $\Bir_\k(\p^n)$ for $n\ge 3$.

Firstly, we can have quite small quotients (which is not the case for $\Bir_\C(\p^2)$ which has no non-trivial countable quotient, as mentioned before):

\begin{corollary}
For each $n\ge 3$, each subfield $\k\subseteq \C$, and each integer $m\ge 1$, there are $($abstract$)$ surjective group homomorphisms from $\Bir_\k(\p^n)$ to the dihedral group $D_{2m}$ of order $2m$ and the symmetric group $\Sym_m$.
In particular, there is a normal subgroup of $\Bir_\k(\p^n)$ of index $r$ for each even integer $r> 1$.
\end{corollary}
\begin{proof}
Follows from Theorem~\ref{TheoremManyCB} and the fact that $D_{2m}$ and $\Sym_m$ are generated by involutions.
\end{proof}

Secondly, we get much larger quotients:

\begin{corollary}
For any $n\ge 3$, any subfield $\k\subseteq \C$ and any integer $m\ge 1$, there are $($abstract$)$ surjective group homomorphisms
\begin{align*}
\Bir_\k(\p^n)\tto \SL_m(\k),&&\Bir_\k(\p^n)\tto \Bir_{\overline{\Q}}(\p^2).
\end{align*}
\end{corollary}

\begin{proof}
We observe that $\SL_m(\k)$ has the cardinality of $\k$ and that $\Bir_{\overline{\Q}}(\p^2)$ is countable. Hence, both groups have at most the cardinality of $\k$.
Both groups are generated by involutions: for $\Bir_{\overline{\Q}}(\p^2)$ this is by the Noether-Castelnuovo Theorem which says that $\Bir_{\overline{\Q}}(\p^2)$ is generated by the standard quadric involution and by $\Aut_{\overline{\Q}}(\p^3)\simeq \PGL_3(\overline{\Q})=\PSL_3(\overline{\Q})$, and thus is generated by involutions.
Hence, the two groups are quotients of $\bigast_{J} \Z/2$.
The result then follows from Theorem~\ref{TheoremManyCB}.
\end{proof}

Similarly, over $\C$ we get:

\begin{corollary}
For any $n \ge 3$, there exists a surjective group homomorphism
\[
\Bir_\C(\p^n)\tto  \Bir_\C(\p^2).
\]
\end{corollary}

Recall that a group $G$ is \emph{SQ-universal} if any countable group embeds in a quotient of $G$.
The free group $\Z * \Z$ was an early example of SQ-universal group.
More generally any nontrivial free product $G_1 * G_2$ distinct from $\Z/2 * \Z/2$ is SQ-universal, see \cite[Theorem 3]{Schupp}.
From a modern point of view, this also follows from [66], by looking at the action of any loxodromic isometry on the associated Bass-Serre tree.
In particular, taking $G_1 = \Z/2 * \Z/2$ and $G_2 = \Z/2$, we get that $\Z/2 * \Z/2 * \Z/2$ is SQ-universal.

\begin{corollary}
For any field $\k\subseteq \C$ and any $n \ge 3$, the Cremona group $\Bir_\k(\p^n)$ admits a surjective morphism to the SQ-universal group $\Z/2 * \Z/2 * \Z/2$.
In particular, $\Bir_\k(\p^n)$ also is SQ-universal.
\end{corollary}

\begin{proof}
Follows from Theorem~\ref{TheoremManyCB} and from the fact that $\Z/2 * \Z/2 * \Z/2$ is SQ-universal.
\end{proof}

\subsection{Hopfian property}\label{sec:Hopfian}
Recall that a group $G$ is \emph{hopfian} is every surjective group homomorphism $G\tto G$ is an isomorphism.
It was proven in [32] that the group $\Bir_\C(\p^2)$ is hopfian. An open question, asked by I. Dolgachev (see [33]), is whether the Cremona group $\Bir_\C(\p^n)$ is generated by involutions for each $n$, the answer being yes in dimension $2$ and open in dimension $\ge 3$. Theorem~\ref{TheoremManyCB} relates these two notions and shows that we cannot generalise both results at the same time (being hopfian and generated by involutions) to higher dimension.

\begin{corollary}\label{Cor:Hopfian}
For each $n\ge 3$ and each subfield $\k\subseteq \C$, the group $\Bir_\k(\p^n)$ is not hopfian if it is generated by involutions.
\end{corollary}

\begin{proof}
Follows from Theorem~\ref{TheoremManyCB}, as the group homomorphisms provided by  Theorem~\ref{TheoremManyCB} is not injective, and because $\Bir_\k(\p^n)$ has the same cardinality as $\k$ (the set of all polynomials of degree $n$ with coefficients in $\k$ has the same cardinality as $\k$).
\end{proof}

\subsection{More general fields}
\label{sec:field}

Every field isomorphism $\k\iso\k'$ naturally induces an isomorphism $\Bir_\k(\p^n)\iso \Bir_{\k'}(\p^n)$. More generally, it associates to each variety and each rational map defined over $\k$, a variety and a rational map defined over $\k'$. It then induces an isomorphism between the group of birational maps defined over $\k$ and $\k'$ of the varieties obtained. This implies that the five
Theorems~\ref{TheoremBirPnnotsimple}-\ref{TheoremManyCB} also hold for each ground field which is abstractly isomorphic to a subfield of $\C$.
This includes any field of rational functions of any algebraic variety defined over a subfield of $\C$ as these fields have characteristic zero and cardinality smaller or equal than the one of $ \C$.

\subsection{Amalgamated product structure}

We work over the field $\C$.
In the next result, an element of $\CB(X)$ is said to be decomposable if it is the class of a decomposable conic bundle (in the sense of Definition~\ref{def:DecomposableCB}).

\begin{theorem}\label{thm:AmalgamatedProduct}
For each integer $n\ge 3$, and let $X/B$ be a conic bundle, where $X$ is a terminal variety of dimension $n$. We denote by $\rho$ the group homomorphism
\[\rho\colon \Bir(X) \to \bigast_{C\in \CB(X)} \left(\bigoplus_{\MC(C)}\Z/2\right)\]
given by Theorem~\ref{TheoremBirMori}. For each $C\in \CB(X)$ we fix a choice of representative $X_C/B_C$, and we denote $G_C = \rho^{-1} (\rho (\Bir(X_C/B_C)))\subseteq \Bir(X)$.
Then, the following hold:
\begin{enumerate}
\item\label{IntersectA} For all $C \neq C'$ in $\CB(X)$, the group $A = G_C \cap G_{C'}$ contains $\ker \rho$ and does not depend on the choice of $C,C'$;
\item \label{BirXFreeproduct}
The group $\Bir(X)$ is the free product of the groups $G_C$, $C\in \CB(X)$,  amalgamated over their common intersection $A$:
\[
\Bir(X) = \bigast_{A} G_C.
\]
\item\label{NonTrivial}
For each decomposable $C\in \CB(X)$ we have $A\subsetneq G_C$.
Moreover, the free product of \ref{BirXFreeproduct} is non-trivial $($i.e.~$A\subsetneq G_C\subsetneq \Bir(X)$ for each $C)$ as soon as $\CB(X)$ contains two distinct decomposable elements.
This is for instance the case when $X$ is rational, as $\CB(X)$ then contains uncountably many decomposable elements.
\end{enumerate}
\end{theorem}

\begin{proof}
\ref{IntersectA}.
For each $C\in \CB(X)$, we denote by $H_C=\left(\bigoplus_{\MC(C)}\Z/2\right)$ the factor indexed by $C$ in the free product $\bigast_{C\in \CB(X)} \left(\bigoplus_{\MC(C)}\Z/2\right)=\bigast_{C\in \CB(X)} H_C$.
By definition of the group homomorphism, for each $C\in \CB(X)$ we have $\rho(\Bir(X_C/B_C)) \subseteq H_C$. As $H_C$ is a $\F_2$-vector space with basis $\MC(C)$ and $\rho(\Bir(X_C/B_C))$ is a linear subspace, there exists a projection $H_C\to \rho(\Bir(X_C/B_C))$. We then denote by
\[
\rho'\colon \Bir(X) \to \bigast_{C\in \CB(X)} \rho(\Bir(X_C/B_C))
\]
the group homomorphism induced for each $C$ by the projection
\[H_C\to\rho(\Bir(X_C/B_C)).\]
By definition of the free product, we obtain $H_C\cap H_{C'}=\id$ for all $C\not=C'$.
This implies that $G_C \cap G_{C'} = \ker \rho' \supseteq \ker \rho$.

\ref{BirXFreeproduct}.
We first observe that by construction the groups $G_C$ generate the group $\Bir(X)$.
The fact that $\Bir(X) = \bigast_{A} G_C$ corresponds to saying that all relations in $\Bir(X)$ lie in the groups $G_C$. This follows from the group homomorphism $\rho$ to a free product, where no relation between the groups $H_C$ exists.

\ref{NonTrivial}.
The fact that $A\subsetneq G_C$ for each decomposable $C$ follows from Proposition~\ref{pro:largeimageAnyCB}.
Hence, the free product of \ref{BirXFreeproduct} is non-trivial if there are least two $C$ corresponding to decomposable conic bundles.
If $X$ is rational, then we moreover have uncountably many such elements by Proposition~\ref{pro:EnoughCB}.
\end{proof}

In Theorem~\ref{thm:AmalgamatedProduct}, one could be tempted to say that $A=\ker\rho$, but this is not clear.
Indeed, it could be that some elements of $\bigoplus_{\MC(C)}\Z/2$ are in the image of $\Bir(X)$ but not in the image of $\Bir(X/B)$.

\subsection{Cubic varieties}\label{Sec:CubicVar}

Here again we work over $\C$.
We recall the following result, which allows to apply Theorem~\ref{TheoremBirXBnotsimple} to any smooth cubic hypersurface of dimension $\ge 3$:

\begin{lemma}\label{Lem:SmoothCubicHypersurfaceLine}
Let $n\ge 4$ and let $\ell\subset X\subset \p^n$ be a line on a smooth cubic hypersurface.
We denote by $\hat{X}$ and $P$ the respective blow-ups of $X$ and $\p^n$ along $\ell$.
Then, the projection $pr_{\ell}$ away from $\ell$ gives rise to a decomposable conic bundle and a decomposable $\p^2$-bundle
\[\hat{X}\subset P=\p(\mathcal{O}_{\p^{n-2}}\oplus \mathcal{O}_{\p^{n-2}}\oplus \mathcal{O}_{\p^2}(1))\stackrel{pr_{\ell}}\to \p^{n-2}.\]
Moreover, the discriminant of the conic bundle is a hypersurface of degree $5$.
\end{lemma}
\begin{proof}
We take coordinates $[y_0:y_1:\cdots:y_{n-2}:u:v]$ on $\p^n$ and assume that $\ell\subset \p^n$ is the line given by $y_0=y_1=\cdots=y_{n-2}=0$.
The equation of $X$ is then given by
\[Au^2+2Buv+Cv^2+2Du+2Ev+F=0\]
where $A,B,C,D,E,F\in \C[y_0,\ldots,y_{n-2}]$ are homogeneous polynomials of degree $1,1,1,2,2,3$ respectively.

As in the proof of Proposition~\ref{pro:largeimageAnyCB}, we view $P=\p(\mathcal{O}_{\p^{n-2}}\oplus \mathcal{O}_{\p^{n-2}}\oplus \mathcal{O}_{\p^{n-2}}(1))$ as the quotient of $(\A^{2}\setminus \{0\})\times (\A^{n-1}\setminus \{0\})$ by $(\mathbb{G}_m)^2$ via
\[\left((\lambda,\mu),(x_0,x_1,x_2,y_0,y_1,\cdots,y_{n-2})\right)\mapsto (\lambda x_0,\lambda x_1,\lambda\mu^{-1} x_2,\mu y_0,\cdots,\mu y_{n-2})\]
and denote by $[x_0\colon x_1 \colon x_2 \semicolon y_0 \colon \cdots \colon y_{n-2}]\in P$ the class of $(x_0,x_1,x_2,y_0,\cdots,y_{n-2})$. The birational morphism
\[
\begin{tikzcd}[map]
P & \to & \p^n\\
{[x_0\colon x_1 \colon x_2 \semicolon y_0 \colon y_1 \colon y_2\colon \cdots \colon y_{n-2}]} & \mapsto & {[x_2y_0 \colon \cdots \colon x_2y_{n-2}:x_0:x_1]}
\end{tikzcd}\]
is the blow-up of $\ell$, so $\hat{X}$ is given by
\[Ax_0^2+2Bx_0x_1+Cx_1^2+2Dx_2x_0+2Ex_2x_1+Fx_2^2=0,\]
which is then a conic bundle over $\p^2$. The discriminant of the curve gives a hypersurface $\Delta\subset \p^2$ of degree $5$, given by the determinant of
$\left(\begin{smallmatrix} A & B & D \\
B & C & E \\ D & E & F\end{smallmatrix}\right)$.
\end{proof}

\begin{corollary}\label{cor:SmoothCubicBirXZ2}
For each $n\ge 4$ and each smooth cubic hypersurface $X\subset \p^n$, there exists a surjective group homomorphism $\Bir(X)\tto \bigoplus_\Z \Z/2$
\end{corollary}

\begin{proof}
Follows from the application of Theorem~\ref{TheoremBirXBnotsimple} to the conic bundle associated to blow-up of a line of $X$ (Lemma~\ref{Lem:SmoothCubicHypersurfaceLine}).
\end{proof}

Every smooth cubic threefold $X\subset \p^4$ is not rational, and moreover two such cubics are birational if and only if they are projectively equivalent, i.e.~equal up to an element of $\Aut(\p^4)=\PGL_5(\C)$ [25].
We moreover get the following:

\begin{proposition}\label{Prop:Cubicfreeproduct}
Let $X\subset \p^4$ be a general smooth cubic hypersurface. We have a surjective group homomorphism
$\Bir(X)\tto \bigast_J \Z/2$, where $J$ has the cardinality of~$\C$.
\end{proposition}

\begin{proof}
The map of Lemma~\ref{Lem:SmoothCubicHypersurfaceLine} associates to each smooth cubic threefold $X$ and each line $\ell\subset X$ a quintic curve $\Delta\subset \p^2$ and also a theta-characteristic; this induces a birational map between the pairs $(\ell,X)$ of lines on smooth cubic threefolds, up to $\PGL_5(\C)$, and the pairs $(\theta,\Delta)$, where $\Delta\subset \p^2$ is a smooth quintic and $\theta$ is a theta-characteristic, again up to $\PGL_3(\C)$ \cite[Theorem 4.1 and Proposition 4.2]{CasRob}.

In particular, taking a general smooth cubic hypersurface $X\subset \p^4$ and varying the lines $\ell\subset X$ (which form a $2$-dimensional family), we obtain a family $J$ of dimension $2$ of smooth quintics $\Delta\subset \p^2$, not pairwise equivalent modulo $\PGL_3(\C)$. This yields conic bundles that are not pairwise equivalent, parametrised by a complex algebraic variety of dimension $2$.
Applying the group homomorphism of Theorem~\ref{TheoremBirMori} and projecting on the corresponding factors provides a surjective group homomorphism
$\Bir(X)\tto \bigast_J \Z/2$, similarly as in the proof of Theorem~\ref{TheoremManyCB}.
\end{proof}

\subsection{Fibrations graph} \label{sec:graph}

We explain how to get a natural graph structure from the set of rank~$r$ fibrations, similarly as in [61].

Let $Z$ be a variety birational to a Mori fibre space.
We construct a sequence of nested graphs $\Gl_n$, $n \ge 1$, as follows.
The set of vertices of $\Gl_n$ are rank~$r$ fibrations $X/B$, for any $r \le n$, with a choice of a birational map $\phi\colon Z \rat X$, and modulo $Z$-equivalence (Definition \ref{def:Tequivalent}).
We denote $(X/B, \phi)$ such an equivalence class.
We put an oriented edge from $(X/B, \phi)$ to $(X'/B', \phi')$ if $\rho(X'/B') = \rho(X/B) - 1$ and the birational maps from $Z$ induce a factorisation of $X/B$ through $X'/B'$, that is, if there is a morphism $B' \to B$ and a birational contraction $X \rat X'$ such that the following diagram commutes
\[
\begin{tikzcd}[link]
& Z  \ar[dr, dashed,"\phi'"] \ar[dl, dashed, "\phi",swap] \\
X \ar[rr,dashed] \ar[dd] && X'  \ar[dd] \\ \\
B  && B' \ar[ll]
\end{tikzcd}
\]
We call the graph $\Gl := \bigcup_n \Gl_n$ the \emph{fibrations graph} associated with $Z$.
The group $\Bir(Z)$ naturally acts on each graph $\Gl_n$, and so also on $\Gl$, by precomposition :
\[
g \cdot (X/B, \phi) := (X/B, \phi \circ g^{-1}).
\]

The fact that Sarkisov links generate $\BirMori(Z)$ is equivalent to the fact that $\Gl_2$ is a connected graph.
Lemma \ref{lem:2 rank 2} implies that $\Gl_3$ is the $1$-skeleton of a square complex, where each square has one vertex of rank 3, one vertex of rank 1 and two vertices of rank 2.
The fact that elementary relations generate all relations in $\BirMori(Z)$ is equivalent to the fact that this square complex is simply connected.

It is not clear to us if for $n \ge 4$ the graph $\Gl_n$ is still the $1$-skeleton of a cube complex.

\begingroup \vbadness 10000\relax % pour eviter les underfull vbox badboxes
\bibliographystyle{myalpha}
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{BCTSSD85}

[1]
H.~Ahmadinezhad \& T.~Okada.
\newblock Stable rationality of higher dimensional conic bundles.
\newblock {\em \'{E}pijournal Geom. Alg\'{e}brique}, 2:Art. 5, 13, 2018.

[2]
H.~{Ahmadinezhad} \& F.~{Zucconi}.
\newblock {Mori dream spaces and birational rigidity of Fano 3-folds.}
\newblock {\em {Adv. Math.}}, 292:410--445, 2016.

[3]
H.~Ahmadinezhad \& F.~Zucconi.
\newblock Circle of {S}arkisov links on a {F}ano 3-fold.
\newblock {\em Proc. Edinb. Math. Soc. (2)}, 60(1):1--16, 2017.

[4]
\newblock {\em Geometry of the plane {C}remona maps}, volume 1769 of {\em
Lecture Notes in Mathematics}.
\newblock Springer-Verlag, Berlin, 2002.

[5]
A.~Alzati \& F.~Russo.
\newblock Some extremal contractions between smooth varieties arising from
projective geometry.
\newblock {\em Proc. London Math. Soc. (3)}, 89(1):25--53, 2004.

[6]
M.~Artebani \& I.~Dolgachev.
\newblock The {H}esse pencil of plane cubic curves.
\newblock {\em Enseign. Math. (2)}, 55(3-4):235--273, 2009.

[7]
I.~Arzhantsev, U.~Derenthal, J.~Hausen \& A.~Laface.
\newblock {\em Cox rings}, volume 144 of {\em Cambridge Studies in Advanced
\newblock Cambridge University Press, Cambridge, 2015.

[8]
F.~Bastianelli, P.~{De Poi}, L.~Ein, R.~Lazarsfeld \& B.~Ullery.
\newblock Measures of irrationality for hypersurfaces of large degree.
\newblock {\em Compos. Math.}, 153(11):2368--2393, 2017.

[9]
A.~Beauville, J.-L. Colliot-Th\'{e}l\`ene, J.-J. Sansuc \& P.~Swinnerton-Dyer.
\newblock Vari\'{e}t\'{e}s stablement rationnelles non rationnelles.
\newblock {\em Ann. of Math. (2)}, 121(2):283--318, 1985.

[10]
\newblock Singularities of linear systems and boundedness of {F}ano varieties.
\newblock {\em \href{https://arxiv.org/pdf/1609.05543}{Preprint
arXiv:1609.05543}}, 2016.

[11]
\newblock Anti-pluricanonical systems on {F}ano varieties.
\newblock {\em Ann. of Math. (2)}, 190(2):345--463, 2019.

[12]
C.~{Birkar}, P.~{Cascini}, C.~D. {Hacon} \& J.~{McKernan}.
\newblock {Existence of minimal models for varieties of log general type.}
\newblock {\em {J. Am. Math. Soc.}}, 23(2):405--468, 2010.

[13]
\newblock Groupes de {C}remona, connexit\'e et simplicit\'e.
\newblock {\em Ann. Sci. \'Ec. Norm. Sup\'er. (4)}, 43(2):357--364, 2010.

[14]
J.~Blanc, A.~Fanelli \& R.~Terpereau.
\newblock Automorphisms of $\mathbb{P}^1$-bundles over rational surfaces.
\newblock {\em \href{https://arxiv.org/pdf/1707.01462}{Preprint
arXiv:1707.01462}}, 2017.

[15]
J.~Blanc, A.~Fanelli \& R.~Terpereau.
\newblock Connected algebraic groups acting on 3-dimensional {M}ori fibrations.
\newblock {\em manuscript in preparation}, 2019.

[16]
J.~Blanc \& J.-P. Furter.
\newblock Topologies and structures of the {C}remona groups.
\newblock {\em Ann. of Math. (2)}, 178(3):1173--1198, 2013.

[17]
J.~Blanc \& I.~Hed\'en.
\newblock The group of {C}remona transformations generated by linear maps and
the standard involution.
\newblock {\em Ann. Inst. Fourier (Grenoble)}, 65(6):2641--2680, 2015.

[18]
J.~Blanc \& S.~Zimmermann.
\newblock Topological simplicity of the {C}remona groups.
\newblock {\em Amer. J. Math.}, 140(5):1297--1309, 2018.

[19]
\newblock {\em Topology and groupoids}.
\newblock BookSurge, LLC, Charleston, SC, 2006.
\newblock Third edition of \textit{Elements of modern topology} [McGraw-Hill,
New York, 1968],.

[20]
\newblock Morphisms between {C}remona groups, and characterization of rational
\newblock {\em Compos. Math.}, 150(7):1107--1124, 2014.

[21]
S.~Cantat \& S.~Lamy.
\newblock Normal subgroups in the {C}remona group.
\newblock {\em Acta Math.}, 210(1):31--94, 2013.
\newblock With an appendix by Yves de Cornulier.

[22]
S.~Cantat \& J.~Xie.
\newblock Algebraic actions of discrete groups: The $p$-adic method.
\newblock {\em Acta Math.}, 220(2):239--295, 2018.

[23]
S.~Casalaina-Martin \& R.~Friedman.
\newblock Cubic threefolds and abelian varieties of dimension five.
\newblock {\em J. Algebraic Geom.}, 14(2):295--326, 2005.

[24]
\newblock Le trasformazioni generatrici del gruppo cremoniano nel piano.
\newblock {\em Atti della R. Accad. delle Scienze di Torino}, (36):861--874,

[25]
C.~H. Clemens \& P.~A. Griffiths.
\newblock The intermediate {J}acobian of the cubic threefold.
\newblock {\em Ann. of Math. (2)}, 95:281--356, 1972.

[26]
\newblock Factoring birational maps of threefolds after {S}arkisov.
\newblock {\em J. Algebraic Geom.}, 4(2):223--254, 1995.

[27]
\newblock Singularities of linear systems and {$3$}-fold birational geometry.
\newblock In {\em Explicit birational geometry of 3-folds}, volume 281 of {\em
London Math. Soc. Lecture Note Ser.}, pages 259--312. Cambridge Univ. Press,
Cambridge, 2000.

[28]
A.~{Corti}, A.~{Pukhlikov} \& M.~{Reid}.
\newblock {Fano 3-fold hypersurfaces.}
\newblock In {\em {Explicit birational geometry of 3-folds}}, pages 175--258.
Cambridge: Cambridge University Press, 2000.

[29]
F.~Dahmani, V.~Guirardel \& D.~Osin.
\newblock Hyperbolically embedded subgroups and rotating families in groups
acting on hyperbolic spaces.
\newblock {\em Mem. Amer. Math. Soc.}, 245(1156), 2017.

[30]
V.~I. Danilov.
\newblock Non-simplicity of the group of unimodular automorphisms of an affine
\newblock {\em Mat. Zametki}, 15:289--293, 1974.

[31]
\newblock Sous-groupes alg\'ebriques de rang maximum du groupe de {C}remona.
\newblock {\em Ann. Sci. \'Ecole Norm. Sup. (4)}, 3:507--588, 1970.

[32]
\newblock Le groupe de {C}remona est hopfien.
\newblock {\em C. R. Math. Acad. Sci. Paris}, 344(3):153--156, 2007.

[33]
\newblock Cremona maps and involutions.
\newblock {\em \href{https://arxiv.org/pdf/1708.01569}{Preprint
arXiv:1708.01569}}, 2017.

[34]
L.~Ein, R.~Lazarsfeld, M.~Musta{\c t}{\u a}, M.~Nakamaye \& M.~Popa.
\newblock Asymptotic invariants of base loci.
\newblock {\em Ann. Inst. Fourier (Grenoble)}, 56(6):1701--1734, 2006.

[35]
\newblock {\em Conferenze di Geometria: fundamenti di una geometria
\newblock Bologna, 1895.

[36]
\newblock Applications of {K}awamata's positivity theorem.
\newblock {\em Proc. Japan Acad. Ser. A Math. Sci.}, 75(6):75--79, 1999.

[37]
\newblock Some remarks on the minimal model program for log canonical pairs.
\newblock {\em J. Math. Sci. Univ. Tokyo}, 22(1):149--192, 2015.

[38]
J.-P. Furter \& S.~Lamy.
\newblock Normal subgroup generated by a plane polynomial automorphism.
\newblock {\em Transform. Groups}, 15(3):577--610, 2010.

[39]
F.~Gounelas \& A.~Kouvidakis.
\newblock Measures of irrationality of the {F}ano surface of a cubic threefold.
\newblock {\em Trans. Amer. Math. Soc.}, 371(10):7111--7133, 2019.

[40]
C.~D. Hacon \& J.~Mckernan.
\newblock On {S}hokurov's rational connectedness conjecture.
\newblock {\em Duke Math. J.}, 138(1):119--136, 2007.

[41]
C.~D. Hacon \& J.~McKernan.
\newblock The {S}arkisov program.
\newblock {\em J. Algebraic Geom.}, 22(2):389--405, 2013.

[42]
\newblock {\em Algebraic geometry}.
\newblock Springer-Verlag, New York-Heidelberg, 1977.
\newblock Graduate Texts in Mathematics, No. 52.

[43]
\newblock {\em Algebraic topology}.
\newblock Cambridge University Press, Cambridge, 2002.

[44]
Y.~Hu \& S.~Keel.
\newblock Mori dream spaces and {GIT}.
\newblock {\em Michigan Math. J.}, 48:331--348, 2000.

[45]
H.~P. Hudson.
\newblock {\em Cremona transformations in plane and space}.
\newblock Cambridge, University Press, 1927.

[46]
V.~A. Iskovskikh.
\newblock Generators of the two-dimensional {C}remona group over a nonclosed
\newblock {\em Trudy Mat. Inst. Steklov.}, 200:157--170, 1991.

[47]
V.~A. Iskovskikh.
\newblock Factorization of birational mappings of rational surfaces from the
point of view of {M}ori theory.
\newblock {\em Uspekhi Mat. Nauk}, 51(4(310)):3--72, 1996.

[48]
V.~A. Iskovskikh, F.~K. Kabdykairov \& S.~L. Tregub.
\newblock Relations in a two-dimensional {C}remona group over a perfect field.
\newblock {\em Izv. Ross. Akad. Nauk Ser. Mat.}, 57(3):3--69, 1993.
\newblock Translation in Russian Acad. Sci. Izv. Math. 42 (1994), no. 3,

[49]
V.~A. Iskovskikh.
\newblock Cremona group.
\newblock In {\em
of Mathematics}}}. 1987.

[50]
A.-S. Kaloghiros.
\newblock Relations in the {S}arkisov program.
\newblock {\em Compos. Math.}, 149(10):1685--1709, 2013.

[51]
A.-S. Kaloghiros, A.~K\"uronya \& V.~Lazi\'c.
\newblock Finite generation and geography of models.
\newblock In {\em Minimal models and extremal rays ({K}yoto, 2011)}, volume~70
of {\em Adv. Stud. Pure Math.}, pages 215--245. 2016.

[52]
\newblock The cubo-cubic transformation of {${\bf P}^3$} is very special.
\newblock {\em Math. Z.}, 195(2):255--257, 1987.

[53]
\newblock Higher direct images of dualizing sheaves. {I}.
\newblock {\em Ann. of Math. (2)}, 123(1):11--42, 1986.

[54]
\newblock Effective base point freeness.
\newblock {\em Math. Ann.}, 296(4):595--605, 1993.

[55]
\newblock {\em Rational curves on algebraic varieties}, volume~32.
\newblock Springer-Verlag, Berlin, 1996.

[56]
\newblock Singularities of pairs.
\newblock In {\em Algebraic geometry---{S}anta {C}ruz 1995}, volume~62 of {\em
Proc. Sympos. Pure Math.}, pages 221--287. Amer. Math. Soc., Providence, RI,

[57]
\newblock Conic bundles that are not birational to numerical {C}alabi-{Y}au
\newblock {\em \'{E}pijournal Geom. Alg\'{e}brique}, 1:Art. 1, 14, 2017.

[58]
J.~Koll\'ar \& S.~Mori.
\newblock Classification of three-dimensional flips.
\newblock {\em J. Amer. Math. Soc.}, 5(3):533--703, 1992.

[59]
J.~Koll\'ar \& S.~Mori.
\newblock {\em Birational geometry of algebraic varieties}, volume 134 of {\em
Cambridge Tracts in Mathematics}.
\newblock Cambridge University Press, Cambridge, 1998.
\newblock With the collaboration of C. H. Clemens and A. Corti, Translated from
the 1998 Japanese original.

[60]
\newblock Challenging problems on affine {$n$}-space.
\newblock {\em Ast\'erisque}, (237):Exp.\ No.\ 802, 5, 295--317, 1996.
\newblock S\'eminaire Bourbaki, Vol. 1994/95.

[61]
S.~Lamy \& S.~Zimmermann.
\newblock Signature morphisms from the {C}remona group over a non-closed field.
\newblock {\em \href{https://arxiv.org/pdf/1707.07955}{Preprint
arXiv:1707.07955}, to appear in JEMS}, 2020.

[62]
\newblock {\em Elliptic functions}, volume 112 of {\em Graduate Texts in
\newblock Springer-Verlag, New York, second edition, 1987.
\newblock With an appendix by J. Tate.

[63]
\newblock {\em Positivity in algebraic geometry. {I}}.
\newblock Springer-Verlag, Berlin, 2004.
\newblock Classical setting: line bundles and linear series.

[64]
\newblock Non simplicit\'e du groupe de {C}remona sur tout corps.
\newblock {\em Ann. Inst. Fourier (Grenoble)}, 66(5):2021--2046, 2016.

[65]
D.~W. Masser \& G.~W\"{u}stholz.
\newblock Estimating isogenies on elliptic curves.
\newblock {\em Invent. Math.}, 100(1):1--24, 1990.

[66]
A.~Minasyan \& D.~Osin.
\newblock Acylindrical hyperbolicity of groups acting on trees.
\newblock {\em Math. Ann.}, 362(3-4):1055--1105, 2015.

[67]
S.~Mori \& S.~Mukai.
\newblock Classification of {F}ano {$3$}-folds with {$B_2\geq 2$}. {I}.
\newblock In {\em Algebraic and topological theories ({K}inosaki, 1984)}, pages
496--545. Kinokuniya, Tokyo, 1985.

[68]
\newblock Une remarque sur la g\'en\'eration du groupe de {C}remona.
\newblock {\em Bol. Soc. Brasil. Mat. (N.S.)}, 30(1):95--98, 1999.

[69]
I.~Pan \& A.~Simis.
\newblock Cremona maps of de {J}onqui\`eres type.
\newblock {\em Canad. J. Math.}, 67(4):923--941, 2015.

[70]
\newblock Gonality of modular curves in characteristic {$p$}.
\newblock {\em Math. Res. Lett.}, 14(4):691--701, 2007.

[71]
\newblock {$p$}-elementary subgroups of the {C}remona group of rank 3.
\newblock In {\em Classification of algebraic varieties}, EMS Ser. Congr. Rep.,
pages 327--338. Eur. Math. Soc., Z\"urich, 2011.

[72]
\newblock Simple finite subgroups of the {C}remona group of rank 3.
\newblock {\em J. Algebraic Geom.}, 21(3):563--600, 2012.

[73]
\newblock 2-elementary subgroups of the space {C}remona group.
\newblock In {\em Automorphisms in birational and affine geometry}, volume~79
of {\em Springer Proc. Math. Stat.}, pages 215--229. 2014.

[74]
Y.~Prokhorov \& C.~Shramov.
\newblock Jordan property for {C}remona groups.
\newblock {\em Amer. J. Math.}, 138(2):403--418, 2016.

[75]
V.~G. Sarkisov.
\newblock On conic bundle structures.
\newblock {\em Izv. Akad. Nauk SSSR Ser. Mat.}, 46(2):371--408, 432, 1982.

[76]
\newblock Relations in the {C}remona group over perfect fields.
\newblock {\em \href{https://arxiv.org/pdf/1906.05265}{Preprint
arXiv:1906.05265}}, 2019.

[77]
P.~E. Schupp.
\newblock A survey of {SQ}-universality.
\newblock pages 183--188. Lecture Notes in Math., Vol. 319, 1973.

[78]
I.~P. Shestakov \& U.~U. Umirbaev.
\newblock The tame and the wild automorphisms of polynomial rings in three
\newblock {\em J. Amer. Math. Soc.}, 17(1):197--227, 2004.

[79]
J.~H. Silverman.
\newblock {\em The arithmetic of elliptic curves}, volume 106 of {\em Graduate
Texts in Mathematics}.
\newblock Springer, Dordrecht, second edition, 2009.

[80]
\newblock On the maximal connected algebraic subgroups of the {C}remona group.
\newblock In {\em Algebraic groups and related topics ({K}yoto/{N}agoya,
1983)}, volume~6 of {\em Adv. Stud. Pure Math.}, pages 349--436.
North-Holland, Amsterdam, 1985.

[81]
\newblock The {A}belianization of the real {C}remona group.
\newblock {\em Duke Math. J.}, 167(2):211--267, 2018.

\end{thebibliography}

\endgroup

\end{document}


# Tomographic Reconstruction and Regularisation
with Search Space Expansion and Total Variation

Mohammad Majid al-Rifaie Tim Blackwell
School of Computing & Mathematical Sciences, University of Greenwich, London,
UK
<EMAIL_ADDRESS>
Department of Computing, Goldsmiths College, University of London, London UK
<EMAIL_ADDRESS>Corresponding author.

###### Abstract

The use of ray projections to reconstruct images is a common technique in
medical imaging. Dealing with incomplete data is particularly important when a
patient is vulnerable to potentially damaging radiation or is unable to cope
with the long scanning time. This paper utilises the reformulation of the
problem into an optimisation tasks, followed by using a swarm-based
reconstruction from highly undersampled data where particles move in image
space in an attempt to minimise the reconstruction error. The process is prone
to noise and, in addition to the recently introduced search space expansion
technique, a further smoothing process, total variation regularisation, is
adapted and investigated. The proposed method is shown to produce lower
reproduction errors compared to standard tomographic reconstruction toolbox
algorithms as well as one of the leading high-dimensional optimisers on the
clinically important Shepp-Logan phantom.

##  1 Introduction

Tomographic reconstruction (TR), which is the determination of the internal
structure of an opaque object from projected images cast by penetrating
radiation, is at the heart of all medical imaging procedures (X-Ray CT, PET,
MRI, Nuclear Medicine and ultrasound [24]) and has widespread application in
various scientific fields, mathematics and industry [27, 36, 18, 13, 19, 25,
32, 16, 22].

As part of the imaging process, a number of projections is acquired which are
often insufficient for a unique reconstruction. Given the under-determined
nature of the problem, and the random nature of the radiation, the operating
characteristics of the detectors and, in medical applications, patient
movement, projection data is incomplete and noisy. The use of an accurate and
fast image reconstruction algorithms with the ability to identify structures
from reduced patient radiation dose (by weakening the incident radiation
and/or reducing acquisition time) is a significant challenge. Success in this
‘few-view‘ scenario would enable procedures that were once prohibited.

There are several reconstruction methods which address various challenges
posed in the imaging procedure. Filtered backprojection (FBP), is a standard
reconstruction technique, which operates with only a single iteration but is
not suitable for few-view imaging [24]. With increased computational power,
Algebraic Reconstruction Techniques (ART) have recently been in more common
use. This class of methods are iterative algorithms based on Kacmarz’s method
[36] and, while capable of dealing with few-view scenarios, the added
artefacts caused by overfitting is a known weakness. Furthermore, evidence of
their worth in large patient populations is lacking [23].

If the data is transformed to a sparse and therefore compressible
representation, exact image reconstruction is feasible. Compressed Sensing
(CS), which exploits this principle, shows promise for few-view
reconstruction, but is heavily dependant on knowledge of the sparse
representation, and on replacing the non-convex optimisation problem typically
unsolvable by traditional methods, by a solvable convex minimisation [17].

Maximum-likelihood expectation maximisation (MLEM) and the more
computationally efficient ordered subset expectation maximisation (OSEM) are
iterative statistical methods which have been trialled and found to be
superior to FBP in some cases e.g. [44, 39].

Reconstruction problems can be cast as optimisation tasks which opens up the
possibility of using population based methods and other metaheuristics (e.g.
[34, 28, 21, 12, 29, 40, 45, 26]). An ant algorithm has been developed for
binary reconstruction [5]. TR problems and particularly, few-view tomography,
is underdetermined: there are many solutions with zero reconstruction error
but only some of these are medically feasible and representative of the
original object. Artefacts and noise typically reduce reconstruction quality.
The challenge is therefore to find biologically plausible solutions of low
reconstruction error.

The research in this paper builds on the findings of reference [7] which
introduced swarm optimisation with search space expansion (SSE). The idea
behind SSE is a successive widening of the effective search space; clamping at
each search space boundary favours homogeneity and significantly reduces
noise. This work introduces a regularisation procedure in order to further
smooth swarm reconstructions. A penalty term, proportional to image gradient,
is added to the reconstruction error with the effect that the optimiser must
minimise both reconstruction quality and pixel heterogeneity. This approach,
known as Total Variation regularisation (TV), has previously been shown to aid
CT reconstructions with traditional algorithms [38].

This paper compares the performance of FBP and ART toolbox reconstruction
algorithms, and a gradient descent reconstruction procedure, CGLS, to a number
of population based methods (local and global particle swarm optimisation
(PSO), dispersive flies optimisation (DFO) and differential evolution (DE)).
The best performing method is then subject to TR-optimised manifestations of
SSE and TV. The results are further compared to a state-of-the art high-
dimensional optimiser. The statistical analysis and the demonstrable visual
reconstruction demonstrates the ability of the proposed method to reconstruct
medically pertinent images from limited views.

##  2 Tomography and reconstruction

The problem in discrete reconstruction is:

$\displaystyle\text{find }x$ $\displaystyle\in$
$\displaystyle\\{0,1,\ldots,k-1\\}^{n},k>1$ $\displaystyle\text{ such that
}Ax$ $\displaystyle=$ $\displaystyle b$ (1)

where $b\in\mathbbm{R}^{m}$ is the vector of detector values. A projection
matrix, $A\in\mathbbm{R}_{\geq 0}^{m\times n}$, where $m$ is the total number
of projections, and $n$ is the number of pixels in the reconstructed image. We
consider the problem as greyscale, where $x$ is a vector of reconstructed
pixel values and $k=256$ i.e. $x\in\\{0,1\ldots,255\\}^{n}$.

The original object or the ground truth, denoted $x^{*}$, also satisfying
$Ax^{*}=b$, is either a phantom (artificial test case) or an imaged subject.
Given the under-deterministic nature of the problem, the equation $Ax=b$
cannot be inverted (few view, $m<<n$) and there are multiple solutions.
Suppose $y$ is a trial solution; $y$ is forward projected, and a
reconstruction error, $e_{1}$, evaluated,

$\displaystyle e_{1}(y)$ $\displaystyle=||b-Ay||_{2}^{2}.$ (2)

Low reconstruction error does not imply faithfulness to the original object
$x^{*}$. The distance between $y$ to $x^{*}$ can be measured by a reproduction
error, $e_{2}$, in instances where $x^{*}$ is known:

$\displaystyle e_{2}$ $\displaystyle=||y-x^{*}||_{1}$ (3)

The reproduction error provides a test of the algorithmic ability to find a
feasible reconstruction.

Libraries such as the Astra toolbox [43] provide the forward projection
operator $A$ in addition to the standard reconstruction algorithms such as
ART, FPB and SIRT. In the absence of real-world data, and for algorithm
development and comparison, a virtual phantom $x^{*}$ is designed and
$b=Ax^{*}$ is computed by forward projection. The fitness function for
optimisation is therefore defined as $e_{1}(y)=||b-Ay||_{2}^{2}$ where $Ay$ is
computed, for trials $y$, by the toolbox.

Discrete TR problems are translatable into real valued problems suitable for
optimisers such as PSO and DE by enabling $y$ to take continuous rather than
discrete values, $y\in[0,255]^{n}$, therefore, allowing $e_{1}$ and $e_{2}$ to
accept real inputs. The original object, $x^{*}$, remains discrete. Final
solutions $y$ can be discretised for visualisation purposes if necessary.

##  3 Regularisation

One of the issues associated with image reconstruction is the presence of salt
and pepper noise which impacts the fidelity of the reconstructed image to the
ground truth. This work uses two approaches to reduce the noise during the
reconstruction process: search space expansion (SSE) and total variation
regularisation (TV).

###  3.1 Search space expansion

In SSE, the search space allocated to the optimiser is initially confined to
only a portion of the feasible space [7]. Assuming the complete search space
to be $\Xi=[0,255]^{n}$, the initial space would be defined as
$\Xi_{1}=[0,\frac{255}{d}]^{n}$, where $d>1$. Any particle leaving this
initially allocated space is clamped to the edges. The initial search space is
then progressively expanded to explore previous unseen territories. Expansions
from the initial space to the subsequent expanded ones kick-in at preset
intervals during the optimisation. By the end of the optimisation process, the
optimiser can access the entire search space.

For empirical trials a series of boxes $\Xi_{p}=[0,\frac{p}{P}\times 255]^{n}$
are defined with expansions at equal divisions of the total budget of function
evaluations. For example, with five subspaces and a budget of 100,000 function
evaluations (FEs), search is conducted in the following boxes:

$\displaystyle\Xi_{1}$ $\displaystyle=[0,\frac{255}{5}]^{n},$ $\displaystyle
0<FE\leq 20000$ $\displaystyle\Xi_{2}$ $\displaystyle=[0,\frac{2\times
255}{5}]^{n},$ $\displaystyle 20000<FE\leq 40000$ $\displaystyle\Xi_{3}$
$\displaystyle=[0,\frac{3\times 255}{5}]^{n},$ $\displaystyle 40000<FE\leq
60000$ $\displaystyle\Xi_{4}$ $\displaystyle=[0,\frac{4\times 255}{5}]^{n},$
$\displaystyle 60000<FE\leq 80000$ $\displaystyle\Xi_{5}$
$\displaystyle=[0,255]^{n},$ $\displaystyle 80000<FE\leq 100000.$

###  3.2 Total Variation

To perform the reconstruction task, the problem is formulated in order to
retrieve the unknown vector $y$ based on the projection matrix $A$ and the
observation vector $b$. In inverse problems such as TR, regularisation
attempts to circumvent overfitting [20]. Total Variation (TV) regularisation
is a deterministic technique that penalises discontinuities in image
processing tasks.

Eq. 2 is augmented with a total variation regularisation term:

$\displaystyle e_{1}^{TV}(y)=||b-Ay||^{2}_{2}+\mu\ TV(y)$ (4)

where the first term serves as a data fidelity term, ensuring the consistency
between the reconstructed image $y$ and the measurement $b$, and the second
term is the TV semi-norm. $\mu>0$ controls the influence of the TV term.

The TV norm is

$\displaystyle
TV(y)={\sum}_{ij}\sqrt{|y_{i+1,j}-y_{i,j}|^{2}+|y_{i,j+1}-y_{i,j}|^{2}}$ (5)

where the sum is over 2D pixel locations $(i,j)$. Regions of small pixel value
gradient $|y_{i+1,j}-y_{i,j}|$ and $|y_{i,j+1}-y_{i,j}|$ will minimise $TV(y)$
and provide homogeneous regions of biologically feasible structure. It has
been shown that the TV enhancement is robust, and able to remove noise and
artefacts in the reconstructed image [37].

##  4 Minimalist swarm optimiser and TR

Dispersive flies optimisation (DFO) is a slimmed-down particle swarm
optimisation (PSO) variant, which is distinguished by the abolition of
particle memory. Updates are computed from current, rather than historical,
position [2]. The exploration and exploitation behaviour of the algorithm is
investigated in [3]. DFO also implements component-wise particle jumps which
have been shown to be beneficial in bare bones PSO [15].

The optimisation starts by determining the best overall position $g^{t+1}$, if
unique, and positions of all best ring neighbours in the neighbourhood,
$n_{i}^{t+1}$ of each particle (barring the current swarm best particle, which
is not updated). Position component $d$ of all particles $i$, (other than the
swarm best) updates according to

$\displaystyle\text{if }u\sim U(0,1)<\Delta$ $\displaystyle\quad
x_{id}^{t+1}\sim U(X_{d})$ else $\displaystyle\quad
x_{id}^{t+1}=n_{id}^{t+1}+\phi u_{1}(g_{d}^{t+1}-x_{id}^{t})$ (6)

where $\Delta$ is a predetermined jump probability and $U(X_{d})$ is the
uniform distribution along axis $d$ of the search space $X$, $u_{1}\sim
U(0,1)$ and $\phi\in[0,\sqrt{3}]$. The constraint on $\phi$ is derived from a
convergence analysis for stochastic difference equations [15]. The algorithm
employs global and local strategies and has two arbitrary parameters $N$ and
$\Delta$; and $\phi$ is invariably set to 1 in published studies. The
algorithm has been applied to a wide range of problems in computer vision,
aesthetics measurement and art, optimising food processes, electronics, data
science and neuroevolution [8, 1, 11, 33, 9, 10, 4, 14].

##  5 Experiments and results

The experiments use five phantoms as shown in Fig. 1. Phantoms 1 - 4 are
binary images and phantom 5, the Shepp-Logan phantom, is a discrete problem
with six pixel value levels [35]. The phantom sizes are $32\times 32$ and
$64\times 64$. To test few-view, undersampled conditions, the number of
projections, $\alpha$, was set to 6, 8, 16 and 32. ASTRA toolbox [43] is used
to conduct phantom imaging using parallel geometry with the number of rays set
to 32 and 64 for the the $32\times 32$ and $64\times 64$ phantoms
respectively.

Figure 1: Phantoms

From the ASTRA toolbox, five reference algorithms were selected: filtered
backprojection (FBP), the algebraic algorithms ART, SIRT and SART, and a
gradient descent reconstruction procedure, CGLS. The potential of swarm
reconstruction was tested with three swarm algorithms, PSO (in two varieties,
global PSO or GPSO, and local PSO, LPSO), DE and DFO.

The swarm algorithms were run for $100,000$ function evaluations. ART, CGLS,
FBP, SART and SIRT perform the reconstruction in $\mathbbm{R}^{D}$, where
$D=32\times 32\text{ or }64\times 64$. Reconstructions were scaled to
$X=[0,255]^{D}$ for the purpose of computing the reproduction error, $e_{2}$.

A swarm size of $N=100$ was chosen for G/LPSO, DE and DFO. Particles were
initialised in $X$ with the uniform distribution and G/LPSO velocities were
set to zero. Particles in all three swarms were clamped to the search box: any
particle attempting to leave $X$ was placed on the boundary, and in the case
of G/LPSO, velocity is set to zero.

Table 1: Rounded median reconstruction error, $e_{1}$, for each problem and algorithm. | TR toolbox algorithms | Population-based optimisers
---|---|---
| ART | CGLS | FBP | SART | SIRT | DE | DFO | GPSO | LPSO
Ph 1, size = $32^{2}$, $\alpha=6$ | 218 | 16 | 57353136 | 1 | 0 | 6213594 | 6509 | 36756397 | 302287
$\alpha=8$ | 434 | 13 | 55960670 | 9 | 0 | 8972489 | 0 | 51413743 | 33858
$\alpha=16$ | 1192 | 1 | 12080882 | 1421 | 12 | 15729665 | 0 | 104974480 | 4189
$\alpha=32$ | 4767 | 12 | 12993996 | 765224 | 79 | 30193881 | 0 | 202177910 | 2387
Size = $64^{2}$, $\alpha=6$ | 511 | 22 | 881101300 | 2 | 0 | 449457240 | 290703650 | 962231630 | 128747038
$\alpha=8$ | 1993 | 4 | 684892900 | 54 | 1 | 612323100 | 403979650 | 1338255850 | 178845160
$\alpha=16$ | 5347 | 8 | 154832160 | 977 | 12 | 1263333600 | 777572730 | 2558892500 | 343625315
$\alpha=32$ | 32556 | 6 | 95809730 | 52562 | 73 | 2450199350 | 1524608650 | 5098064750 | 666271775
Ph 2, size = $32^{2}$, $\alpha=6$ | 682 | 27 | 219649500 | 0 | 0 | 4881877 | 489974 | 26541697 | 2598464
$\alpha=8$ | 1027 | 0 | 125614740 | 12 | 0 | 7757407 | 290828 | 36228715 | 2010975
$\alpha=16$ | 1014 | 4 | 30864254 | 1144 | 12 | 13824955 | 0 | 75870290 | 163955
$\alpha=32$ | 6805 | 20 | 34511600 | 3798144 | 136 | 27962292 | 0 | 157194035 | 69490
Size = $64^{2}$, $\alpha=6$ | 21532 | 25 | 2552608300 | 7 | 0 | 296865630 | 205105125 | 650832450 | 113333140
$\alpha=8$ | 13219 | 29 | 1476768100 | 121 | 0 | 385430975 | 271130845 | 797472900 | 157673265
$\alpha=16$ | 8634 | 1 | 421734660 | 1859 | 20 | 811162880 | 559093000 | 1715699050 | 324069900
$\alpha=32$ | 50550 | 11 | 278557820 | 42777 | 289 | 1649504250 | 1108368850 | 3431840500 | 634350900
Ph 3, size = $32^{2}$, $\alpha=6$ | 88 | 0 | 118908584 | 0 | 0 | 7825271 | 134 | 67812627 | 736763
$\alpha=8$ | 124 | 0 | 74234100 | 1 | 0 | 10517076 | 56 | 80654290 | 1326800
$\alpha=16$ | 1543 | 0 | 9678624 | 3988 | 13 | 24247643 | 0 | 168775595 | 2079945
$\alpha=32$ | 5894 | 2 | 4692086 | 4138801 | 97 | 42903300 | 0 | 330850820 | 2896024
Size = $64^{2}$, $\alpha=6$ | 3449 | 0 | 1572601300 | 0 | 0 | 835896350 | 503486890 | 2165751550 | 195114935
$\alpha=8$ | 491 | 1 | 1007831400 | 13 | 0 | 1019598350 | 581618945 | 2758263850 | 241910610
$\alpha=16$ | 6827 | 4 | 188459900 | 1472 | 28 | 2082434150 | 1198967450 | 5413350650 | 515041345
$\alpha=32$ | 17844 | 2 | 36140108 | 15064 | 149 | 3993287550 | 2389057650 | 10727333500 | 990994525
Ph 4, size = $32^{2}$, $\alpha=6$ | 217 | 2 | 808024770 | 2 | 0 | 4994230 | 609809 | 25554527 | 3385390
$\alpha=8$ | 555 | 1 | 370298020 | 30 | 1 | 5256030 | 721491 | 24894351 | 4710365
$\alpha=16$ | 8929 | 0 | 69808620 | 10431 | 57 | 23979954 | 2613173 | 72151635 | 14181106
$\alpha=32$ | 47093 | 2 | 26453604 | 4325603 | 590 | 60286648 | 826782 | 157362800 | 27365272
Size = $64^{2}$, $\alpha=6$ | 8068 | 7 | 13681514000 | 10 | 0 | 261069665 | 111867240 | 769442225 | 85870980
$\alpha=8$ | 1008 | 3 | 4972211700 | 1 | 0 | 243611335 | 95635225 | 714078650 | 91989665
$\alpha=16$ | 12288 | 0 | 1202136800 | 1727 | 62 | 582503870 | 259003385 | 1622731400 | 279910750
$\alpha=32$ | 78954 | 1 | 269898500 | 240709 | 702 | 1278379300 | 602676550 | 2860742250 | 706395100
Ph 5, size = $32^{2}$, $\alpha=6$ | 322 | 2 | 64488092 | 5 | 0 | 3358653 | 356519 | 19843914 | 2682284
$\alpha=8$ | 429 | 0 | 37028332 | 102 | 6 | 5220447 | 508443 | 28824148 | 4289071
$\alpha=16$ | 6785 | 2 | 7614852 | 2373 | 29 | 16464641 | 1470355 | 66384160 | 10751817
$\alpha=32$ | 5198 | 2 | 9878102 | 90968 | 74 | 44725869 | 4028948 | 153507290 | 24552911
Size = $64^{2}$, $\alpha=6$ | 2881 | 4 | 1179886800 | 0 | 0 | 240579325 | 98721218 | 821075400 | 69743575
$\alpha=8$ | 1581 | 0 | 663436700 | 218 | 1 | 328983280 | 136800775 | 1059109055 | 107567910
$\alpha=16$ | 5234 | 0 | 159528460 | 890 | 19 | 721549070 | 291544490 | 2089936600 | 248175780
$\alpha=32$ | 37583 | 0 | 62805610 | 58163 | 145 | 1414172750 | 600360370 | 4179300750 | 532845370
Table 2: Algorithms comparison based on $e_{1}$. Numbers indicate statistically significant wins for the algorithm in the left hand column versus the algorithm in the top row. | ART | CGLS | FBP | SART | SIRT | DE | DFO | GPSO | LPSO | $\Sigma$
---|---|---|---|---|---|---|---|---|---|---
ART | NA | 0 | 40 | 12 | 0 | 40 | 31 | 40 | 39 | 202
CGLS | 40 | NA | 40 | 32 | 22 | 40 | 33 | 40 | 40 | 287
FBP | 0 | 0 | NA | 0 | 0 | 16 | 9 | 25 | 10 | 60
SART | 28 | 8 | 40 | NA | 0 | 40 | 32 | 40 | 37 | 225
SIRT | 40 | 18 | 40 | 40 | NA | 40 | 33 | 40 | 40 | 291
DE | 0 | 0 | 23 | 0 | 0 | NA | 0 | 40 | 0 | 63
DFO | 7 | 7 | 31 | 8 | 6 | 40 | NA | 40 | 22 | 161
GPSO | 0 | 0 | 13 | 0 | 0 | 0 | 0 | NA | 0 | 13
LPSO | 1 | 0 | 29 | 3 | 0 | 40 | 18 | 40 | NA | 131

The DFO jump probability was set to $0.001$; G/LPSO was run with $w=0.729844$
and $c=1.49618$ and the DE/best/1 parameters $F$ and $C_{R}$ were both set to
$0.5$. All algorithms with randomisation were run 30 times on each of the 40
problems: 5 phantoms $\times$ 4 projection types (6, 8, 16, 32) $\times$ 2
sizes ($32\times 32$ and $64\times 64$).

Table 3: Rounded median reproduction error, $e_{2}$, for each problem and each algorithm. Lighter shading indicates the proximity of the reconstructions to the phantoms. The largest error in phantoms of sizes $32^{2}$ and $64^{2}$ are $255\times 32^{2}$ and $255\times 64^{2}$ respectively. | TR toolbox algorithms | Population-based optimisers
---|---|---
| ART | CGLS | FBP | SART | SIRT | DE | DFO | GPSO | LPSO
Ph 1, size = $32^{2}$, $\alpha=6$ | 51826 | 99356 | 82043 | 52562 | 52254 | 13242 | 420 | 29844 | 2773
$\alpha=8$ | 51750 | 66418 | 86995 | 52311 | 53461 | 11821 | 1 | 27672 | 680
$\alpha=16$ | 38745 | 115808 | 55146 | 58775 | 42220 | 8124 | 0 | 25746 | 150
$\alpha=32$ | 37587 | 6821 | 35016 | 112567 | 27634 | 6962 | 0 | 24352 | 80
Size = $64^{2}$, $\alpha=6$ | 216081 | 217040 | 425778 | 214884 | 246053 | 159530 | 142480 | 220776 | 97210
$\alpha=8$ | 227658 | 286941 | 385363 | 225173 | 241075 | 152623 | 135958 | 217264 | 91322
$\alpha=16$ | 162459 | 210787 | 262494 | 195464 | 179756 | 152407 | 129482 | 211900 | 84812
$\alpha=32$ | 132566 | 130101 | 181438 | 464631 | 150986 | 149321 | 128086 | 210921 | 80886
Ph 2, size = $32^{2}$, $\alpha=6$ | 75478 | 117958 | 96146 | 74991 | 75948 | 20278 | 9493 | 35795 | 16268
$\alpha=8$ | 66315 | 110549 | 91503 | 70612 | 71292 | 18407 | 5107 | 33860 | 9631
$\alpha=16$ | 53931 | 104435 | 67266 | 62931 | 52404 | 11191 | 0 | 27210 | 1327
$\alpha=32$ | 35972 | 16688 | 45266 | 119778 | 29999 | 8957 | 0 | 26880 | 536
Size = $64^{2}$, $\alpha=6$ | 306143 | 489520 | 396555 | 300664 | 308809 | 178848 | 170864 | 230096 | 135870
$\alpha=8$ | 271574 | 457891 | 408102 | 275737 | 280536 | 173193 | 164081 | 227429 | 129423
$\alpha=16$ | 230965 | 231018 | 319252 | 248662 | 241230 | 158693 | 146497 | 217395 | 109135
$\alpha=32$ | 178735 | 179516 | 217124 | 389843 | 181413 | 154848 | 139559 | 216685 | 101305
Ph 3, size = $32^{2}$, $\alpha=6$ | 54111 | 110037 | 75229 | 53060 | 61049 | 11359 | 34 | 30476 | 3542
$\alpha=8$ | 69160 | 77480 | 87131 | 70097 | 65759 | 12164 | 19 | 31467 | 4563
$\alpha=16$ | 43337 | 77609 | 57842 | 87346 | 40388 | 10360 | 0 | 32132 | 2537
$\alpha=32$ | 33606 | 9854 | 36061 | 110320 | 31623 | 8781 | 0 | 31635 | 1756
Size = $64^{2}$, $\alpha=6$ | 239804 | 376982 | 396969 | 236242 | 243335 | 164059 | 138704 | 238811 | 90967
$\alpha=8$ | 275303 | 470541 | 408217 | 271385 | 297473 | 171601 | 144178 | 245820 | 98706
$\alpha=16$ | 207820 | 475237 | 315308 | 200323 | 219470 | 170917 | 138741 | 242887 | 92402
$\alpha=32$ | 141076 | 142095 | 192508 | 482340 | 141896 | 169328 | 138694 | 246142 | 89084
Ph 4, size = $32^{2}$, $\alpha=6$ | 106233 | 106734 | 106053 | 107896 | 106042 | 42639 | 36845 | 52692 | 41449
$\alpha=8$ | 99030 | 126284 | 112713 | 98011 | 101802 | 50782 | 45347 | 57539 | 48984
$\alpha=16$ | 78535 | 109904 | 93446 | 118392 | 90560 | 38058 | 22937 | 50469 | 32753
$\alpha=32$ | 61504 | 18723 | 76074 | 148488 | 59498 | 30381 | 3817 | 45841 | 22629
Size = $64^{2}$, $\alpha=6$ | 359476 | 457919 | 341521 | 351830 | 369252 | 227959 | 198832 | 286299 | 194556
$\alpha=8$ | 370377 | 508417 | 397320 | 379010 | 402508 | 242933 | 216563 | 288858 | 216007
$\alpha=16$ | 327332 | 311610 | 353516 | 334652 | 378013 | 232429 | 199097 | 293588 | 200125
$\alpha=32$ | 260130 | 241566 | 315026 | 470472 | 250627 | 228127 | 182692 | 291675 | 191472
Ph 5, size = $32^{2}$, $\alpha=6$ | 81618 | 125584 | 85029 | 82844 | 80749 | 42046 | 37052 | 53284 | 41565
$\alpha=8$ | 69074 | 69497 | 93444 | 69635 | 71007 | 40768 | 34377 | 52579 | 40438
$\alpha=16$ | 45410 | 97915 | 65674 | 82172 | 46194 | 37515 | 27831 | 50481 | 33405
$\alpha=32$ | 25400 | 1332 | 45441 | 91940 | 15897 | 34474 | 21385 | 47786 | 29791
Size = $64^{2}$, $\alpha=6$ | 289093 | 419775 | 326454 | 287494 | 292781 | 216387 | 180379 | 278224 | 184707
$\alpha=8$ | 283383 | 433439 | 379237 | 286974 | 288103 | 214797 | 178452 | 276883 | 178909
$\alpha=16$ | 225719 | 230242 | 291806 | 253042 | 224918 | 214866 | 171819 | 279062 | 170918
$\alpha=32$ | 145426 | 159103 | 180867 | 461802 | 184953 | 211410 | 167643 | 278226 | 168244
Table 4: Algorithms comparison based on $e_{2}$. Numbers indicate statistically significant wins for the algorithm in the left hand column versus the algorithm in the top row. | ART | CGLS | FBP | SART | SIRT | DE | DFO | GPSO | LPSO | $\Sigma$
---|---|---|---|---|---|---|---|---|---|---
ART | NA | 32 | 37 | 29 | 28 | 4 | 1 | 11 | 2 | 144
CGLS | 8 | NA | 20 | 17 | 13 | 5 | 2 | 12 | 3 | 80
FBP | 3 | 20 | NA | 16 | 4 | 1 | 0 | 4 | 0 | 48
SART | 11 | 23 | 24 | NA | 18 | 0 | 0 | 4 | 0 | 80
SIRT | 12 | 27 | 36 | 22 | NA | 3 | 1 | 10 | 1 | 112
DE | 36 | 34 | 39 | 40 | 37 | NA | 0 | 40 | 0 | 226
DFO | 39 | 38 | 40 | 40 | 39 | 40 | NA | 40 | 22 | 298
GPSO | 28 | 27 | 35 | 35 | 28 | 0 | 0 | NA | 0 | 153
LPSO | 38 | 37 | 40 | 40 | 39 | 39 | 13 | 40 | NA | 286

###  5.1 Vanilla swarm and toolbox algorithms results

Aggregating the results of Table 1 which summarises the performance of the
swarm and toolbox algorithms, Table 2 reports on Wilcoxon statistical
significance tests on the reconstruction error for algorithm pairs for the 40
problem instances at a significance level of $0.05$. The rows show the number
of instances in which the row algorithm performed better than the column
algorithm. For example, reading along the first row, ART gave a significantly
smaller reconstruction error, $e_{1}$, than SART on 12 of the 40 trials.

Algebraic reconstruction algorithms ART, SART and SIRT and gradient descent,
CGLS, uniformly outperform DE, GPSO and LPSO and are better than DFO in at
least 31 trials. SIRT presents the best performance as shown in shaded colour
in the last column which sums the total number of significant wins. These
results are expected given the toolbox algorithms have been specifically
designed for reconstruction while the swarm algorithms are off-the-shelf
multi-purpose low-dimensional optimisers that have not been tuned to the
reconstruction task.

In Table 4, comparing algorithm pairs based on the reproduction error,
$e_{2}$, illustrates that DE, LPSO (and to a lesser extent GPSO) consistently
find better reproductions than any of the toolbox algorithms; and DFO produces
better results than the rest of the swarm and toolbox algorithms.

Table 3 presents the median reproduction error of each algorithm over each set
of problem. Lighter shading indicates lower $e_{2}$ error. DFO generates good
reproduction, followed by LPSO. DFO produces exact reconstruction of the
original phantoms ($e_{2}=0$) in 6 out of 40 experiments, where no other swarm
or toolbox algorithm is capable of producing an exact reconstruction.

###  5.2 Parameter tuning

To better optimise the leading swarm method in the context of the problem, DFO
parameters were fine-tuned. Phantom $1$, with size $32\times 32$ and
$\alpha=6$, was used as a benchmark to sweep through the parameter space. The
parameters tuned are $N,\phi$ and $\Delta$, and DFO was used as a hyper-
parameter optimiser. The optimiser was run 30 times with the population size
of $10$ and the termination criterion set to $100$ iterations ($1000$ function
evaluations). During the fine-tuning exercise, the elitism mechanism was
revised, catering for the presence of stochasticity in the optimisation
process, and to enable re-evaluation of the current best particle parameters
found in the trials. The optimum and most frequent successful parameter values
found were $\Delta=0.001$, $N=2$ and $\phi=1.7320508\approx\sqrt{3}$. The
small value of optimal $N$ confirms the finding that the function profile has
a single broad funnel leading the global optima, in effect rendering the task
into a largely unimodal problem [6]. It also indicates that DFO is acting as a
‘swarm-inspired local search’ and the collective presence of a large
communication network is unnecessary in this context. Three local search
algorithms (Nelder-Mead [31], L-BFGS-B [46], MTS-LS1 [41]), had been
investigated, demonstrating that a ‘simple’ local search may fall short of
competing with ‘a swarm-based local search’.

###  5.3 Search space expansion

The positive impact of SSE has been studied by researchers. In this work,
first SSE is fine-tuned on Shepp-Logan phantom, which was introduced in 1974,
and is a schematic representation of a cranial slice [35] (a standard phantom
for TR algorithm testing); then, the fitness function is adapted to integrate
the TV regularisation term (Eq. 4). Fine-tuning SSE identifies the optimal
number of expanding boxes required to reduce the noise in the reconstructed
images.

As a result, Table 5 presents the median errors for the reconstruction and
reproduction errors, $e_{1}$ and $e_{2}$ respectively, for 30 runs.

While a single box produces the smallest median reconstruction error (see the
first row in Table 5, and Table 6-left), the result is distant from the
original phantom (see the corresponding $e_{2}$ error and Fig. 2); 50 boxes,
however, produces a better reproduction error, with the reconstructed image
closer to the original. Increasing the number of boxes beyond 50 does not
statistically significantly alter the $e_{2}$ outcome (see last row in Table
6-right).

No. of boxes FEs | 10k | 20k | 30k | 40k | 50k | 60k | 70k | 80k | 90k | 100k
---|---|---|---|---|---|---|---|---|---|---
1 |  |  |  |  |  |  |  |  |  |
2 |  |  |  |  |  |  |  |  |  |
3 |  |  |  |  |  |  |  |  |  |
10 |  |  |  |  |  |  |  |  |  |
50 |  |  |  |  |  |  |  |  |  |
100 |  |  |  |  |  |  |  |  |  |
Figure 2: Visualsing the reconstruction process of Shepp-Logan phantom at different points in the optimisation process (every 10,000 FEs) and for varying number of expanding boxes, with phantom size of $32\times 32$ and $6$ projections.  Table 5: Median error values for 30 runs on each of five boxing scenarios for $32\times 32$ Shepp-Logan, imaged with 6 projections. The smallest $e_{1}$ and $e_{2}$ errors are highlighted.  Boxes | $e_{1}$ | $e_{2}$
---|---|---
1 | 47222 | 32642
2 | 113234 | 24731
3 | 102552 | 20463
10 | 110200 | 20085
50 | 114391 | 19662
100 | 120111 | 19957
Table 6: Statistical analysis of $e_{1}$ (left) and $e_{2}$ (right) for
varying boxing scenarios for $32\times 32$ Shepp Logan with 6 projections. A
‘1’ indicates a Wilcoxon win for the algorithm over 30 runs in the left hand
column versus the algorithm in the top row. ‘0’ indicates no significant
difference in the algorithms. For the reproduction error, there are no
significant differences from boxing scenario 50.

$e_{1}$ $e_{2}$

Boxes | 1 | 2 | 3 | 10 | 50 | 100
---|---|---|---|---|---|---
1 | NA | 1 | 1 | 1 | 1 | 1
2 | 0 | NA | 0 | 0 | 0 | 1
3 | 0 | 1 | NA | 1 | 1 | 1
10 | 0 | 0 | 0 | NA | 1 | 1
50 | 0 | 0 | 0 | 0 | NA | 1
100 | 0 | 0 | 0 | 0 | 0 | NA

Boxes | 1 | 2 | 3 | 10 | 50 | 100
---|---|---|---|---|---|---
1 | NA | 0 | 0 | 0 | 0 | 0
2 | 1 | NA | 0 | 0 | 0 | 0
3 | 1 | 1 | NA | 0 | 0 | 0
10 | 1 | 1 | 1 | NA | 0 | 0
50 | 1 | 1 | 1 | 1 | NA | 0
100 | 1 | 1 | 1 | 1 | 0 | NA

###  5.4 Total variation regularisation

Total variation regularisation is another tool in ‘denoising’ images during
the reconstruction process. The successful use of this method depends highly
on adjusting the $\mu$ parameter (Eq. 4). To conduct the fine-tuning, a range
of values from $\mu=[0,1000]$ are selected and 30 independent trials are run
for each $\mu$ value. Table 7 presents (a) the median error values for both
$e_{1}$ and $e_{2}$, along with (b) the statistical analysis of the results.
Based on the statistical analysis of the reproduction error, the ‘sweet spot’
for the regularisation parameter is between $\mu=[40,65]$, with the best value
$\mu=55$ with 19 significant wins out of 25. The regularisation, which is
studied here, follows the search space expansion, and serves the similar
purpose of smoothing the reconstructed images by balancing the trade off
between a smaller $e_{1}$ error with a more clinically plausible
reconstruction. We notice that, as in the boxing scenarios, regularisation
degrades the $e_{1}$ error as shown in Table 7 (the best $e_{1}$ is obtained
when $\mu=0$), but improves the overall reconstruction, as seen from its
impact on $e_{2}$ error.

Table 7: Total variation regularisation. (a) $e_{1}$ and $e_{2}$ median error values for varying $\mu$, along with (b) the count of statistically significant wins for each $\mu$. | (a) Error values |  (b) Statistically significant cases
---|---|---
$\mu$ | $e_{1}$ | $e_{2}$ | $e_{1}$ | $e_{2}$
0 | 118549 | 19833 |  24 | 1
1 | 176868 | 19457 | 23 | 2
5 | 401477 | 18274 | 22 | 3
10 | 642329 | 17213 | 21 | 4
15 | 846614 | 16379 | 20 | 6
20 | 1033289 | 15807 | 19 | 8
25 | 1216424 | 15353 | 18 | 9
30 | 1386386 | 14972 | 17 | 12
35 | 1556795 | 14734 | 16 | 16
40 | 1719532 | 14580 | 15 | 18
45 | 1889283 | 14630 | 14 | 17
50 | 2052300 | 14625 | 13 | 18
55 | 2187202 | 14650 | 12 | 19
60 | 2352773 | 14672 | 11 | 16
65 | 2507530 | 14577 | 10 | 18
70 | 2665960 | 14762 | 9 | 15
75 | 2813415 | 14682 | 8 | 14
80 | 2957201 | 14861 | 7 | 13
85 | 3098517 | 14906 | 6 | 13
90 | 3249197 | 15097 | 5 | 12
95 | 3410860 | 15243 | 4 | 9
100 | 3539566 | 15306 | 3 | 9
150 | 4899699 | 16182 | 2 | 6
200 | 6174531 | 17193 | 1 | 4
1000 | 24795852 | 25632 | 0 | 0

###  5.5 Comparison with SHADE-ILS algorithm

The standard version of the optimisers used in this work are designed for
lower dimensional problems. Large-scale global optimisation (LSGO), which
deals with a great number of variables, has been gaining increasing popularity
in recent years. One such method, SHADE with iterative local search or SHADE-
ILS [30], which has won the CEC’2018 LSGO competition, hybridises SHADE and
two local search methods: MTS-L1 [42] and L-BFGS-B [47]. The performance of
this algorithm along with its use of local search methods, provides a good
basis for comparison with the proposed swarm technique. In this comparison,
the optimised DFO for TR, with neither the search space expansion nor total
variation regularisation (DFO-TR), is compared against DFO-TR with search
space expansion and total variation regularisation (DFO-TR-$\mu$), the best
performing TR toolbox algorithm (SIRT), and SHADE-ILS.

Wilcoxon significance results for 30 runs on Shepp-Logan phantom are given in
Table 8. Table 8-left compares algorithm pairs when rated according to the
reconstruction error, $e_{1}$. Unsurprisingly, SIRT produces the best
reconstruction, $e_{1}$ (followed by SHADE-ILS); while DFO-TR does not offer a
statistically significantly difference with SHADE-ILS in image reproduction,
$e_{2}$, DFO-TR-$\mu$ which benefits from the dual regularisation methods,
produces statistically significant smaller reproduction errors (Table
8-right).

Fig. 3 shows the visual reconstruction of the Shepp-Logan phantom using the
four aforementioned techniques. The figure shows the presence of artefacts in
SIRT, and salt-and-pepper noise in both DFO-TR and SHADE-ILS. Under this
highly undersampled scenario, DFO-TR-$\mu$ presents a respectable
reconstruction of the phantom, albeit with yet some distance from a zero
reproduction error.

Table 8: Comparison with SHADE-ILS. A ‘1’ indicates a Wilcoxon win for the
algorithm over 30 runs in the left hand column versus the algorithm in the top
row. ‘0’ indicates no significant difference in the algorithms.

$e_{1}$ | DFO-TR | DFO-TR-$\mu$ | SIRT | SHADE-ILS
---|---|---|---|---
DFO-TR | NA | 1 | 0 | 0
DFO-TR-$\mu$ | 0 | NA | 0 | 0
SIRT | 1 | 1 | NA | 1
SHADE-ILS | 1 | 1 | 0 | NA

$e_{2}$ | DFO-TR | DFO-TR-$\mu$ | SIRT | SHADE-ILS
---|---|---|---|---
DFO-TR | NA | 0 | 1 | 0
DFO-TR-$\mu$ | 1 | NA | 1 | 1
SIRT | 0 | 0 | NA | 0
SHADE-ILS | 0 | 0 | 1 | NA

Phantom | DFO-TR | DFO-TR-$\mu$ | SIRT | SHADE-ILS
---|---|---|---|---
|  |  |  |
Figure 3: Reconstructing Shepp-Logan by the swarm optimiser without the
smoothing methods (DFO-TR), the presented method with dual regularisation of
search space expansion and the total variation (DFO-TR-$\mu$), the best
standard TR toolbox algorithm (SIRT), and SHADE-ILS.

##  6 Conclusion

This work investigates two regularisation methods in the context of
tomographic reconstruction when dealing with highly undersampled data in few-
view scenarios. These methods – search space expansion and total variation –
are sequentially fine-tuned and adapted to the reconstructing algorithm.
Integrating these methods results in the worsening of the reconstruction
errors, which was expected; however, the presented pipeline, and the use of
the updated objective function, result in lower reproduction errors, which
demonstrates a more faithful reconstruction to the ground truth than the
standard toolbox algorithms and a high-dimensional optimiser. Among the
subjects of future research is reformulating the problem into a multiobjective
problem as well as hybridising classical toolbox techniques (with their
signature feature of low reconstruction error) and the presented swarm
optimisation method, benefiting from dual regularisation (with low
reproduction errors) which could produce a powerful algorithm capable of fast
noise- and artefacts-free reconstructions in the few-view regime.

## References

  * [1] Bishwa Babu Acharya, Sandeep Dhakal, Aayush Bhattarai, and Nawraj Bhattarai.  Pid speed control of dc motor using meta-heuristic algorithms.  International Journal of Power Electronics and Drive Systems, 12(2):822, 2021.
  * [2] Mohammad Majid al-Rifaie.  Dispersive flies optimisation.  In 2014 Federated Conference on Computer Science and Information Systems, pages 529–538. IEEE, 2014.
  * [3] Mohammad Majid al-Rifaie.  Exploration and exploitation zones in a minimalist swarm optimiser.  Entropy, 23(8):977, 2021.
  * [4] Mohammad Majid al-Rifaie and Ahmed Aber.  Dispersive flies optimisation and medical imaging.  In Recent Advances in Computational Optimization, pages 183–203. Springer, 2016.
  * [5] Mohammad Majid al-Rifaie and Tim Blackwell.  Applications of Evolutionary Computation: 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 – April 1, 2016, Proceedings, Part I, chapter Binary Tomography Reconstruction by Particle Aggregation, pages 754–769.  Springer International Publishing, Cham, 2016.
  * [6] Mohammad Majid al-Rifaie and Tim Blackwell.  Swarm led tomographic reconstruction.  In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’22, page 1121–1129, New York, NY, USA, 2022. Association for Computing Machinery.
  * [7] Mohammad Majid al-Rifaie and Tim Blackwell.  Tomographic reconstruction with search space expansion.  In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1286–1293, 2023.
  * [8] Mohammad Majid al-Rifaie and Marc Cavazza.  Evolutionary optimisation of beer organoleptic properties: A simulation framework.  Foods, 11(3):351, Jan 2022.
  * [9] Mohammad Majid al-Rifaie, Anna Ursyn, Robert Zimmer, and Mohammad Ali Javaheri Javid.  On symmetry, aesthetics and quantifying symmetrical complexity.  In João Correia, Vic Ciesielski, and Antonios Liapis, editors, Computational Intelligence in Music, Sound, Art and Design: EvoMUSART 2017, pages 17–32. Springer International Publishing, 2017.
  * [10] Haya Abdullah Alhakbani and Mohammad Majid al-Rifaie.  Optimising svm to classify imbalanced data using dispersive flies optimisation.  In 2017 Federated Conference on Computer Science and Information Systems (FedCSIS), pages 399–402. IEEE, 2017.
  * [11] Prashant Aparajeya, Frederic Fol Leymarie, and Mohammad Majid al-Rifaie.  Swarm-based identification of animation key points from 2d-medialness maps.  In Anikó Ekárt, Antonios Liapis, and María Luz Castro Pena, editors, Computational Intelligence in Music, Sound, Art and Design, pages 69–83, Cham, 2019. Springer International Publishing.
  * [12] Kees Joost Batenburg and Walter A Kosters.  Solving Nonograms by combining relaxations.  Pattern Recognition, 42(8):1672–1683, 2009.
  * [13] Kees Joost Batenburg and Willem Jan Palenstijn.  On the reconstruction of crystals through discrete tomography.  In International Workshop on Combinatorial Image Analysis, pages 23–37. Springer, 2004.
  * [14] J. Mark Bishop and Mohammad Majid al-Rifaie.  Autopoiesis in creativity and art.  In Proceedings of the 3rd International Symposium on Movement and Computing, MOCO ’16, pages 27:1–27:6, New York, NY, USA, 2016. ACM.
  * [15] Tim Blackwell.  A study of collapse in bare bones particle swarm optimization.  IEEE Transactions on Evolutionary Computation, 16(3):354–372, 2011\.
  * [16] MD Butala, RJ Hewett, RA Frazin, and F Kamalabadi.  Dynamic three-dimensional tomography of the solar corona.  Solar Physics, 262(2):495–509, 2010.
  * [17] Emmanuel J Candes, Justin K Romberg, and Terence Tao.  Stable signal recovery from incomplete and inaccurate measurements.  Communications on pure and applied mathematics, 59(8):1207–1223, 2006.
  * [18] José-Maria Carazo, CO Sorzano, Eicke Rietzel, R Schröder, and Roberto Marabini.  Discrete tomography in electron microscopy.  In Discrete Tomography, pages 405–416. Springer, 1999.
  * [19] Bruno Carvalho, Gabor Herman, Samuel Matej, Claudia Salzberg, and Eilat Vardi.  Binary tomography for triplane cardiography.  In Information Processing in Medical Imaging, pages 29–41. Springer, 1999.
  * [20] Antonin Chambolle.  An algorithm for total variation minimization and applications.  Journal of Mathematical imaging and vision, 20:89–97, 2004.
  * [21] Marco Cipolla, Giosuè Lo Bosco, Filippo Millonzi, and Cesare Valenti.  An island strategy for memetic discrete tomography reconstruction.  Information Sciences, 257:357–368, 2014.
  * [22] Richard J Gardner.  Geometric tomography, volume 1.  Cambridge University Press Cambridge, 1995.
  * [23] Lucas L Geyer, U Joseph Schoepf, Felix G Meinel, John W Nance Jr, Gorka Bastarrika, Jonathon A Leipsic, Narinder S Paul, Marco Rengo, Andrea Laghi, and Carlo N De Cecco.  State of the art: iterative ct reconstruction techniques.  Radiology, 276(2):339–357, 2015.
  * [24] A. Giussani and C. Hoeschen.  Imaging in nuclear medicine.  Springer, 2013.
  * [25] U Hampel, A Bieberle, D Hoppe, J Kronenberg, E Schleicher, T Sühnel, F Zimmermann, and C Zippe.  High resolution gamma ray tomography scanner for flow measurement and non-destructive testing applications.  Review of scientific instruments, 78(10):103704, 2007.
  * [26] Gang Hu, Min-you Chen, Wei He, and Jin-qian Zhai.  Clustering-based particle swarm optimization for electrical impedance imaging.  Advances in Swarm Intelligence, pages 165–171, 2011.
  * [27] R.W. Irving and M.R. Jerrum.  Three-dimensional data security problems.  SIAM J. Comput., 23:170–184, 1994.
  * [28] Fethi Jarray and Ghassen Tlig.  A simulated annealing for reconstructing hv-convex binary matrices.  Electronic Notes in Discrete Mathematics, 36:447–454, 2010.
  * [29] Póth Miklós.  Particle swarm optimization approach to discrete tomography reconstruction problems of binary matrices.  In Intelligent Systems and Informatics (SISY), 2014 IEEE 12th International Symposium on, pages 321–324. IEEE, 2014.
  * [30] Daniel Molina, Antonio LaTorre, and Francisco Herrera.  Shade with iterative local search for large-scale global optimization.  In 2018 IEEE congress on evolutionary computation (CEC), pages 1–8. IEEE, 2018.
  * [31] John A Nelder and Roger Mead.  A simplex method for function minimization.  The computer journal, 7(4):308–313, 1965.
  * [32] Guust Nolet et al.  A breviary of seismic tomography.  Imaging the Interior, 2008.
  * [33] Hooman Oroojeni, Mohammad Majid al-Rifaie, and Mihalis A. Nicolaou.  Deep neuroevolution: Training deep neural networks for false alarm detection in intensive care units.  In European Association for Signal Processing (EUSIPCO) 2018, pages 1157–1161. IEEE, 2018.
  * [34] Ahlem Ouaddah and Dalila Boughaci.  Improving reconstructed images using hybridization between local search and harmony search meta-heuristics.  In Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation, pages 1475–1476. ACM, 2014\.
  * [35] Lawrence A Shepp and Benjamin F Logan.  The fourier reconstruction of a head section.  IEEE Transactions on nuclear science, 21(3):21–43, 1974.
  * [36] Abe R. Shliferstein and YT Chien.  Some properties of image-processing operations on projection sets obtained from digital pictures.  IEEE Transactions on Computers, 26(10):958–970, 1977.
  * [37] Emil Y Sidky and Xiaochuan Pan.  Image reconstruction in circular cone-beam computed tomography by constrained, total-variation minimization.  Physics in Medicine & Biology, 53(17):4777, 2008.
  * [38] Zhen Tian, Xun Jia, Kehong Yuan, Tinsu Pan, and Steve B Jiang.  Low-dose ct reconstruction via edge-preserving total variation regularization.  Physics in Medicine & Biology, 56(18):5949, 2011.
  * [39] Ana Carolina Trevisan, Michel David Raed, Vitor Tumas, Leonardo Alexandre-Santos, Felipe Arriva Pitella, Emerson Nobuyuki Itikawa, Jose Henrique Silvah, Mery Kato, Edson Zangiacomi Martinez, Jorge Alberto Achcar, et al.  Comparison between osem and fbp reconstruction algorithms for the qualitative and quantitative interpretation of brain dat-spect using an anthropomorphic striatal phantom: implications for the practice.  Research on Biomedical Engineering, 36(1):77–88, 2020.
  * [40] Jens Tronicke, Hendrik Paasche, and Urs Böniger.  Crosshole traveltime tomography using particle swarm optimization: A near-surface field example.  Geophysics, 77(1):R19–R32, 2012.
  * [41] Lin-Yu Tseng and Chun Chen.  Multiple trajectory search for large scale global optimization.  In 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), pages 3052–3059. IEEE, 2008.
  * [42] Lin-Yu Tseng and Chun Chen.  Multiple trajectory search for large scale global optimization.  In 2008 IEEE congress on evolutionary computation (IEEE world congress on computational intelligence), pages 3052–3059. IEEE, 2008.
  * [43] Wim Van Aarle, Willem Jan Palenstijn, Jeroen Cant, Eline Janssens, Folkert Bleichrodt, Andrei Dabravolski, Jan De Beenhouwer, K Joost Batenburg, and Jan Sijbers.  Fast and flexible x-ray tomography using the astra toolbox.  Optics express, 24(22):25129–25147, 2016.
  * [44] Floris HP van Velden, Reina W Kloet, Bart NM van Berckel, Saskia PA Wolfensberger, Adriaan A Lammertsma, and Ronald Boellaard.  Comparison of 3d-op-osem and 3d-fbp reconstruction algorithms for high-resolution research tomograph studies: effects of randoms estimation methods.  Physics in Medicine & Biology, 53(12):3217, 2008.
  * [45] P Wang, JS Lin, and M Wang.  An image reconstruction algorithm for electrical capacitance tomography based on simulated annealing particle swarm optimization.  Journal of applied research and technology, 13(2):197–204, 2015\.
  * [46] Ciyou Zhu, Richard H Byrd, Peihuang Lu, and Jorge Nocedal.  Algorithm 778: L-bfgs-b: Fortran subroutines for large-scale bound-constrained optimization.  ACM Transactions on mathematical software (TOMS), 23(4):550–560, 1997.
  * [47] Ciyou Zhu, Richard H Byrd, Peihuang Lu, and Jorge Nocedal.  Algorithm 778: L-bfgs-b: Fortran subroutines for large-scale bound-constrained optimization.  ACM Transactions on mathematical software (TOMS), 23(4):550–560, 1997.