$-\kappa(\rho,c)\lvert\mathbf{v}\rvert^{2}-F_{\rho}\left[c_{\rho}+\lvert\mathbf{v}\rvert^{2}-\left(\frac{1}{2}\lvert\mathbf{v}\rvert^{2}+u-\rho\frac{\partial\mathcal{F}}{\partial\rho}\right)+\mu
c\right]-F_{\mathbf{v}}\left[c_{\mathbf{v}}-\mathbf{v}\right]-F_{c}\left[c_{c}+\mu\right]\leq
0.$

The obvious choices are of course

$\begin{cases}c_{\rho}=-\lvert\mathbf{v}\rvert^{2}+\left(\frac{1}{2}\lvert\mathbf{v}\rvert^{2}+u-\rho\frac{\partial\mathcal{F}}{\partial\rho}\right)-\mu
c,\\\ c_{\mathbf{v}}=\mathbf{v},\\\ c_{c}=-\mu.\end{cases}$

From the previous constitutive relations and choices of Lagrange multipliers,
we have that the dissipation inequality (A.19) is satisfied.

###  A.7 Summary of the model’s equations

Using the previous constitutive relations our general model is the following
compressible Navier-Stokes-Cahn-Hilliard system

$\displaystyle\frac{\partial\rho}{\partial t}$ $\displaystyle=-{\rm
div}\left(\rho\mathbf{v}\right)+F_{\rho},$ (A.27)
$\displaystyle\rho\frac{\mathop{\kern 0.0pt\mathrm{D}}\\!{}c}{\mathop{\kern
0.0pt\mathrm{D}}\\!{}t}$ $\displaystyle={\rm
div}\left(b(c)\nabla\mu\right)+F_{c}-cF_{\rho},$ $\displaystyle\rho\mu$
$\displaystyle=-\gamma{\rm div}\left(\rho\nabla
c\right)+\rho\frac{\partial\psi_{0}}{\partial c},$
$\displaystyle\rho\frac{\mathop{\kern
0.0pt\mathrm{D}}\\!{}\mathbf{v}}{\mathop{\kern 0.0pt\mathrm{D}}\\!{}t}$
$\displaystyle=\begin{multlined}-\left[\nabla p+\gamma{\rm
div}\left(\rho\nabla c\otimes\nabla c\right)\right]+{\rm
div}\left(\nu(c)\left(\nabla\mathbf{v}+\nabla\mathbf{v}^{T}\right)\right)\\\
-\frac{2}{3}\nabla\left(\nu(c)\left({\rm
div}\left(\mathbf{v}\right)\right)\right)-\left(\kappa(\rho,c)+F_{\rho}\right)\mathbf{v}+F_{\mathbf{v}},\end{multlined}-\left[\nabla
p+\gamma{\rm div}\left(\rho\nabla c\otimes\nabla c\right)\right]+{\rm
div}\left(\nu(c)\left(\nabla\mathbf{v}+\nabla\mathbf{v}^{T}\right)\right)\\\
-\frac{2}{3}\nabla\left(\nu(c)\left({\rm
div}\left(\mathbf{v}\right)\right)\right)-\left(\kappa(\rho,c)+F_{\rho}\right)\mathbf{v}+F_{\mathbf{v}},$

with $p$ defined in (A.24).

##  Appendix B Model reduction, general assumptions and biologically relevant
choices of the model’s functions

###  B.1 Specific choices of functionals and model reductions

##### Problem 1: General compressible NSCH with friction term and mass
transfer.

Assuming no creation of mass nor transfer of mass from the exterior of the
system we have

$F_{c}=-F_{1-c},$ (B.1)

leading to mass conservation

$F_{\rho}=0.$ (B.2)

Furthermore, we assume no external source of velocity and energy, leading to

$F_{\mathbf{v}}=0,\text{ and }F_{u}=0.$ (B.3)

Furthermore, using the same simplifying assumption as in Abels and Feireisl
[4] to avoid vacuum zones, our final reduced system of equations is

$\displaystyle\frac{\partial\rho}{\partial t}+{\rm
div}\left(\rho\mathbf{v}\right),$ (B.4) $\displaystyle\frac{\partial\rho
c}{\partial t}+{\rm div}\left(\rho c\mathbf{v}\right)={\rm
div}\left(b(c)\nabla\mu\right)+F_{c},$ (B.5)
$\displaystyle\rho\mu=-\gamma\Delta c+\rho\frac{\partial\psi_{0}}{\partial
c},$ (B.6) $\displaystyle\frac{\partial\rho\mathbf{v}}{\partial t}+{\rm
div}\left(\rho\mathbf{v}\otimes\mathbf{v}\right)=\begin{multlined}-\left[\nabla
p+\gamma{\rm div}\left(\nabla c\otimes\nabla c-\frac{1}{2}\lvert\nabla
c\rvert^{2}\mathbf{1}\right)\right]+{\rm
div}\left(\nu(c)\left(\nabla\mathbf{v}+\nabla\mathbf{v}^{T}\right)\right)\\\
-\frac{2}{3}\nabla\left(\nu(c)\left({\rm
div}\left(\mathbf{v}\right)\right)\right)-\kappa(\rho,c)\mathbf{v},\end{multlined}-\left[\nabla
p+\gamma{\rm div}\left(\nabla c\otimes\nabla c-\frac{1}{2}\lvert\nabla
c\rvert^{2}\mathbf{1}\right)\right]+{\rm
div}\left(\nu(c)\left(\nabla\mathbf{v}+\nabla\mathbf{v}^{T}\right)\right)\\\
-\frac{2}{3}\nabla\left(\nu(c)\left({\rm
div}\left(\mathbf{v}\right)\right)\right)-\kappa(\rho,c)\mathbf{v},$ (B.9)

######  Remark B.1.

In this article, we prove the existence of a weak solutions for Problem 1 and
propose an efficient structure and bounds-preserving scheme.

##### Problem 2: Biologically relevant variant of the system.

For this variant of the system, we assume the production of mass and neglect
certain effects. Namely, we neglect inertia effects, and the viscosity of the
fluid, and assume no external source of velocity. This leads to the momentum
equation

$\nabla p+\kappa(\rho,c)\mathbf{v}=-\gamma{\rm div}\left(\nabla c\otimes\nabla
c-\frac{1}{2}\lvert\nabla c\rvert^{2}\mathbf{1}\right)-F_{\rho}\mathbf{v}.$

Then, we assume one cell population proliferates while the other does not,
leading to

$F_{c}=F_{\rho}=\rho cP_{c}(p),\quad\text{and}\quad F_{1-c}=0,$

with a pressure-dependent proliferation rate $P_{c}(p)\geq 0$. The growth
function $P_{c}(p)$ is used to represent the capacity of cells to divide
accordingly to the pressure exerted on them. It is well known that cells are
able to divide as long as the pressure is not too large. Once a certain
pressure $p_{\text{max}}$ is reached cells enter a quiescent state. Therefore,
we assume that

$P_{c}^{\prime}(p)\leq 0,\quad\text{and}\quad P_{c}(p)=0\quad\text{for}\quad
p>p_{\text{max}}.$ (B.10)

Combining these changes, the model becomes

$\begin{cases}\frac{\partial\rho}{\partial t}+{\rm
div}\left(\rho\mathbf{v}\right)=\rho cP_{c}(p),\\\ \frac{\partial\rho
c}{\partial t}+{\rm div}\left(\rho c\mathbf{v}\right)={\rm
div}\left(b(c)\nabla\mu\right)+\rho cP_{c}(p),\\\ \rho\mu=-\gamma\Delta
c+\rho\frac{\partial\psi_{0}}{\partial c},\\\ \nabla
p+\kappa(\rho,c)\mathbf{v}=-\gamma{\rm div}\left(\nabla c\otimes\nabla
c-\frac{1}{2}\lvert\nabla c\rvert^{2}\mathbf{1}\right)-\rho
cP_{c}(p)\mathbf{v}.\end{cases}$ (B.11)

###  B.2 Biologically consistent choices of functions

As said in the derivation of the model, the free energy density $\mathcal{F}$
is the sum of two terms: $\frac{\gamma}{2}\lvert\nabla c\rvert^{2}$ taking
into account the surface tension effects existing between the phases of the
mixture and the potential $\psi_{0}(\rho,c)$ representing the cell-cell
interactions and pressure. Thus, we choose

$\psi_{0}(\rho,c)=\psi_{e}(\rho)+\psi_{\text{mix}}(\rho,c),$ (B.12)

with $\psi_{\text{mix}}(\rho,c)=H(c)\log\rho+Q(c)$. Then, using the
constitutive relation for the pressure we have

$p(\rho,c)=\rho^{2}\frac{\partial\psi_{0}}{\partial\rho}=p_{e}(\rho)+\rho
H(c).$ (B.13)

The function $b(\rho)$ is the active mobility of the cells of the growing
population.

Let us explain how the choices of functions for the free energy density and
mobility are motivated by biological observations.

To satisfy the conditions (2.7), we propose to choose

$b(c)=C_{b}c(1-c)^{\alpha},\quad\alpha\geq 1,$ (B.14)

where $C_{b}$ is a positive constant.

######  Remark B.2.

Note that we cannot prove the existence of solutions for this mobility because
it is degenerate. Instead, in the analysis part of this paper, we use an
approximate mobility bounded away from zero. The difficulty of the degenerate
mobility comes when one tries to identify the chemical potential $\mu$ when
the parameters in the approximating schemes are removed. Indeed the estimate
of the dissipation of the energy
$\int_{\Omega}b(c)|\nabla\mu|^{2}\mathop{}\\!\mathrm{d}x$ does not provide
estimates on $\nabla\mu$ anymore.

We use for the pressure a power law such that

$p_{e}(\rho)=\frac{1}{a-1}\rho^{a-1}.$ (B.15)

For $H(c)$ and $G(c)$, two choices can be considered depending on the behavior
of the cells we want to represent. If the two cell populations exert
attractive forces when they recognize cells of the same type and repulsion
with the other type, the potential has to take a form of a double-well for
which the two stable phases are located at the bottom of the two wells (see
e.g. Figure 7(a)). This is a situation close to the phase separation in binary
fluids. Thermodynamically consistent potentials are of Ginzburg-Landau type
with the presence of logarithmic terms. Even though the double-well form of
the potential is originally used for applications dealing with materials, it
can also be motivated for biological purposes. Indeed, considering an
application where the mixture is saturated with two cell types, a double-well
potential is biologically relevant and reflects correctly the expected
behavior of cells: they are attracted to each other respectively to their cell
type at low densities and after a certain density they start to repel each
other to avoid the creation of overcrowded zones. A typical example of
biologically relevant double-well potential is given by

$\psi_{\text{mix}}=\frac{1}{2}\left(\alpha_{1}(1-c)\log(\rho(1-c))+\alpha_{2}c\log(\rho
c)\right)-\frac{\theta}{2}(c-\frac{1}{2})^{2}+k,$ (B.16)

thus giving

$H(c)=\frac{1}{2}\left(\alpha_{1}(1-c)+\alpha_{2}c\right),\quad
Q(c)=\frac{1}{2}\left(\alpha_{1}(1-c)\log(1-c)+\alpha_{2}c\log(c)\right)-\frac{\theta}{2}(c-\frac{1}{2})^{2}+k,$

where $\theta>1$ and $k$ is an arbitrary constant.

(a) Double-well potential

(b) Single-well potential

Figure 7: For both figures $\rho=1$. Double-well logarithmic potential (left)
with $\alpha_{1}=1.2$ and $\alpha_{2}=0.8$ and single-well logarithmic
potential (right)

To meet the phenomenological observations of the interaction between cells
when the mixture is composed of only one cell population (and the other
component of the mixture is supposed to be much more compressible), a single-
well potential seems more appropriate [15, 19].

Indeed, when the distance between cells falls below a certain value (i.e. if
the cell density is large enough), cells are attracted to each other. Then, it
exists a threshold value called the mechanical equilibrium for which $\rho
H(c_{e})+Q(c_{e})=0$ i.e. there is an equilibrium between attractive and
repulsive forces. For larger cell densities, cells are packed too close to
each other, they thus experience a repulsive force. When cells are so packed
that they fill the whole control volume, then the repulsive force becomes
infinite due to the pressure. The representation of such functional is
depicted in Figure 7(b). A typical example of single-well potential which has
been used for the modeling of living tissue and cancer [19, 7] is

$\psi_{\text{mix}}(\rho,c)=-(1-c_{e})\log(\rho(1-c))-\frac{c^{3}}{3}-(1-c_{e})\frac{c^{2}}{2}-(1-c_{e})c+k,$
(B.17)

thus giving

$H(c)=-(1-c_{e}),\quad
Q(c)=-(1-c_{e})\log(1-c)-\frac{c^{3}}{3}-(1-c_{e})\frac{c^{2}}{2}-(1-c_{e})c+k,$
(B.18)

where $k$ is an arbitrary constant.

## References

  * [1] H. Abels, On a diffuse interface model for two-phase flows of viscous, incompressible fluids with matched densities, Arch. Ration. Mech. Anal., 194 (2009), pp. 463–506.
  * [2] , Strong well-posedness of a diffuse interface model for a viscous, quasi-incompressible two-phase flow, SIAM J. Math. Anal., 44 (2012), pp. 316–340.
  * [3] H. Abels, D. Depner, and H. Garcke, On an incompressible Navier-Stokes/Cahn-Hilliard system with degenerate mobility, Ann. Inst. H. Poincaré C Anal. Non Linéaire, 30 (2013), pp. 1175–1190.
  * [4] H. Abels and E. Feireisl, On a diffuse interface model for a two-phase flow of compressible viscous fluids, Indiana Univ. Math. J., 57 (2008), pp. 659–698.
  * [5] H. Abels, H. Garcke, and G. Grün, Thermodynamically consistent, frame indifferent diffuse interface models for incompressible two-phase flows with different densities, Math. Models Methods Appl. Sci., 22 (2012), pp. 1150013, 40.
  * [6] A. Agosti, Discontinuous Galerkin finite element discretization of a degenerate Cahn-Hilliard equation with a single-well potential, Calcolo, 56 (2019), pp. Paper No. 14, 47.
  * [7] A. Agosti, P. F. Antonietti, P. Ciarletta, M. Grasselli, and M. Verani, A Cahn-Hilliard-type equation with application to tumor growth dynamics, Math. Methods Appl. Sci., 40 (2017), pp. 7598–7626.
  * [8] G. L. Aki, W. Dreyer, J. Giesselmann, and C. Kraus, A quasi-incompressible diffuse interface model with phase transition, Math. Models Methods Appl. Sci., 24 (2014), pp. 827–861.
  * [9] D. Ambrosi and L. Preziosi, On the closure of mass balance models for tumor growth, Mathematical Models and Methods in Applied Sciences, 12 (2002), pp. 737–754.
  * [10] D. M. Anderson, G. B. McFadden, and A. A. Wheeler, Diffuse-interface methods in fluid mechanics, in Annual review of fluid mechanics, Vol. 30, vol. 30 of Annu. Rev. Fluid Mech., Annual Reviews, Palo Alto, CA, 1998, pp. 139–165.
  * [11] J. W. Barrett, J. F. Blowey, and H. Garcke, Finite element approximation of the Cahn-Hilliard equation with degenerate mobility, SIAM J. Numer. Anal., 37 (1999), pp. 286–318.
  * [12] D. Bresch and B. Desjardins, Existence of global weak solutions for a 2D viscous shallow water equations and convergence to the quasi-geostrophic model, Comm. Math. Phys., 238 (2003), pp. 211–223.
  * [13] , On the construction of approximate solutions for the 2D viscous shallow water model and for compressible Navier-Stokes models, J. Math. Pures Appl. (9), 86 (2006), pp. 362–368.
  * [14] D. Bresch, A. F. Vasseur, and C. Yu, Global existence of entropy-weak solutions to the compressible Navier-Stokes equations with non-linear density dependent viscosities, J. Eur. Math. Soc. (JEMS), 24 (2022), pp. 1791–1837.
  * [15] H. Byrne and L. Preziosi, Modelling solid tumour growth using the theory of mixtures, Math. Med. Biol., 20 (2003), pp. 341–366.
  * [16] J. W. Cahn, On spinodal decomposition, Acta metall., 9 (1961), pp. 795–801.
  * [17] J. W. Cahn and J. E. Hilliard, Free Energy of a Nonuniform System. I. Interfacial Free Energy, J. Chem. Phys., 28 (1958), pp. 258–267.
  * [18] C. Chatelain, T. Balois, P. Ciarletta, and M. B. Amar, Emergence of microstructural patterns in skin cancer: a phase separation analysis in a binary mixture, New Journal of Physics, 13 (2011), p. 115013.
  * [19] C. Chatelain, P. Ciarletta, and M. Ben Amar, Morphological changes in early melanoma development: influence of nutrients, growth inhibitors and cell-adhesion mechanisms, J. Theoret. Biol., 290 (2011), pp. 46–59.
  * [20] L. Cherfils, E. Feireisl, M. Michálek, A. Miranville, M. Petcu, and D. Pražák, The compressible Navier-Stokes-Cahn-Hilliard equations with dynamic boundary conditions, Math. Models Methods Appl. Sci., 29 (2019), pp. 2557–2584.
  * [21] M. Ebenbeck, H. Garcke, and R. Nürnberg, Cahn–hilliard–brinkman systems for tumour growth, Discrete and Continuous Dynamical Systems - S, 14 (2021), pp. 3989–4033.
  * [22] C. Eck, H. Garcke, and P. Knabner, Mathematical modeling, Springer Undergraduate Mathematics Series, Springer, Cham, 2017.
  * [23] C. M. Elliott and H. Garcke, On the Cahn-Hilliard equation with degenerate mobility, SIAM J. Math. Anal., 27 (1996), pp. 404–423.
  * [24] J. L. Ericksen, Liquid crystals with variable degree of orientation, Arch. Rational Mech. Anal., 113 (1990), pp. 97–120.
  * [25] E. Feireisl, Dynamics of viscous compressible fluids, vol. 26 of Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2004.
  * [26] E. Feireisl and A. Novotný, Singular limits in thermodynamics of viscous fluids, Advances in Mathematical Fluid Mechanics, Birkhäuser Verlag, Basel, 2009.
  * [27] H. Garcke, K. F. Lam, E. Sitka, and V. Styles, A cahn–hilliard–darcy model for tumour growth with chemotaxis and active transport, Mathematical Models and Methods in Applied Sciences, 26 (2016), pp. 1095–1148.
  * [28] J. Giesselmann and T. Pryer, Energy consistent discontinuous Galerkin methods for a quasi-incompressible diffuse two phase flow model, ESAIM Math. Model. Numer. Anal., 49 (2015), pp. 275–301.
  * [29] Z. Guo, P. Lin, and J. S. Lowengrub, A numerical method for the quasi-incompressible Cahn-Hilliard-Navier-Stokes equations for variable density flows with a discrete energy law, J. Comput. Phys., 276 (2014), pp. 486–507.
  * [30] M. E. Gurtin, On a nonequilibrium thermodynamics of capillarity and phase, Quart. Appl. Math., 47 (1989), pp. 129–145.
  * [31] M. E. Gurtin, E. Fried, and L. Anand, The mechanics and thermodynamics of continua, Cambridge University Press, Cambridge, 2010.
  * [32] M. E. Gurtin, D. Polignone, and J. Viñals, Two-phase binary fluids and immiscible fluids described by an order parameter, Mathematical Models and Methods in Applied Sciences, 06 (1996), pp. 815–831.
  * [33] Q. He and X. Shi, Numerical study of compressible Navier-Stokes-Cahn-Hilliard system, Commun. Math. Sci., 18 (2020), pp. 571–591.
  * [34] P. C. Hohenberg and B. I. Halperin, Theory of dynamic critical phenomena, Rev. Mod. Phys., 49 (1977), pp. 435–479.
  * [35] B. S. Hosseini, S. Turek, M. Möller, and C. Palmes, Isogeometric analysis of the Navier-Stokes-Cahn-Hilliard equations with application to incompressible two-phase flows, J. Comput. Phys., 348 (2017), pp. 171–194.
  * [36] F. Huang and J. Shen, Bound/positivity preserving and energy stable scalar auxiliary variable schemes for dissipative systems: applications to Keller-Segel and Poisson-Nernst-Planck equations, SIAM J. Sci. Comput., 43 (2021), pp. A1832–A1857.
  * [37] F. Huang, J. Shen, and K. Wu, Bound/positivity preserving and unconditionally stable schemes for a class of fourth order nonlinear equations, J. Comput. Phys., 460 (2022), pp. Paper No. 111177, 16.
  * [38] S. Jin and Z. P. Xin, The relaxation schemes for systems of conservation laws in arbitrary space dimensions, Comm. Pure Appl. Math., 48 (1995), pp. 235–276.
  * [39] , The relaxation schemes for systems of conservation laws in arbitrary space dimensions, Comm. Pure Appl. Math., 48 (1995), pp. 235–276.
  * [40] K. F. Lam and H. Wu, Thermodynamically consistent Navier-Stokes-Cahn-Hilliard models with mass transfer and chemotaxis, European J. Appl. Math., 29 (2018), pp. 595–644.
  * [41] R. J. LeVeque et al., Finite volume methods for hyperbolic problems, vol. 31, Cambridge university press, 2002.
  * [42] P.-L. Lions, Mathematical topics in fluid mechanics. Vol. 2, vol. 10 of Oxford Lecture Series in Mathematics and its Applications, The Clarendon Press, Oxford University Press, New York, 1998.  Compressible models, Oxford Science Publications.
  * [43] , Mathematical topics in fluid mechanics. Vol. 2, vol. 10 of Oxford Lecture Series in Mathematics and its Applications, The Clarendon Press, Oxford University Press, New York, 1998.  Compressible models, Oxford Science Publications.
  * [44] S. Lisini, D. Matthes, and G. Savaré, Cahn-Hilliard and thin film equations with nonlinear mobility as gradient flows in weighted-Wasserstein metrics, J. Differential Equations, 253 (2012), pp. 814–850.
  * [45] I. S. Liu, Method of Lagrange multipliers for exploitation of the entropy principle, Arch. Rational Mech. Anal., 46 (1972), pp. 131–148.
  * [46] X. Liu, J. Fang, S. Huang, X. Wu, X. Xie, J. Wang, F. Liu, M. Zhang, Z. Peng, and N. Hu, Tumor-on-a-chip: from bioinspired design to biomedical application, Microsystems & Nanoengineering, 7 (2021), p. 50.
  * [47] T. Lorenzi, A. Lorz, and B. Perthame, On interfaces between cell populations with different mobilities, Kinetic and Related Models, 10 (2016), pp. 299–311.
  * [48] J. Lowengrub, E. Titi, and K. Zhao, Analysis of a mixture model of tumor growth, European J. Appl. Math., 24 (2013), pp. 691–734.
  * [49] , Analysis of a mixture model of tumor growth, European J. Appl. Math., 24 (2013), pp. 691–734.
  * [50] J. Lowengrub and L. Truskinovsky, Quasi-incompressible Cahn-Hilliard fluids and topological transitions, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci., 454 (1998), pp. 2617–2654.
  * [51] A. Miranville, The Cahn-Hilliard equation, vol. 95 of CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2019.  Recent advances and applications.
  * [52] A. Moussa, Some variants of the classical Aubin-Lions lemma, J. Evol. Equ., 16 (2016), pp. 65–93.
  * [53] I. Müller, Thermodynamics, Pitman, 1985.
  * [54] G. A. Narsilio, O. Buzzi, S. Fityus, T. S. Yun, and D. W. Smith, Upscaling of navier–stokes equations in porous media: Theoretical, numerical and experimental approach, Computers and Geotechnics, 36 (2009), pp. 1200 – 1206.
  * [55] B. Perthame and A. Poulain, Relaxation of the Cahn-Hilliard equation with singular single-well potential and degenerate mobility, European J. Appl. Math., 32 (2021), pp. 89–112.
  * [56] E. Rocca, G. Schimperna, and A. Signori, On a cahn–hilliard–keller–segel model with generalized logistic source describing tumor growth, Journal of Differential Equations, 343 (2023), pp. 530–578.
  * [57] J. Shen, J. Xu, and J. Yang, The scalar auxiliary variable (SAV) approach for gradient flows, J. Comput. Phys., 353 (2018), pp. 407–416.
  * [58] , The scalar auxiliary variable (SAV) approach for gradient flows, J. Comput. Phys., 353 (2018), pp. 407–416.
  * [59] M. F. P. ten Eikelder, K. G. van der Zee, I. Akkerman, and D. Schillinger, A unified framework for Navier-Stokes Cahn-Hilliard models with non-matching densities, Math. Models Methods Appl. Sci., 33 (2023), pp. 175–221.
  * [60] A. F. Vasseur and C. Yu, Existence of global weak solutions for 3D degenerate compressible Navier-Stokes equations, Invent. Math., 206 (2016), pp. 935–974.
  * [61] S. M. Wise, J. S. Lowengrub, H. B. Frieboes, and V. Cristini, Three-dimensional multispecies nonlinear tumor growth—I: Model and numerical method, J. Theor. Biol., 253 (2008), pp. 524–543.


# TIB’s Visual Analytics Group at MediaEval ’20: Detecting Fake News on Corona
Virus and 5G Conspiracy

Gullal S. Cheema1, Sherzod Hakimov1, Ralph Ewerth1,2 1TIB – Leibniz
Information Centre for Science and Technology, Hannover, Germany
2L3S Research Center, Leibniz University Hannover, Germany  gullal.cheema,
sherzod.hakimov<EMAIL_ADDRESS>
###### Abstract.

Fake news on social media has become a hot topic of research as it negatively
impacts the discourse of real news in the public. Specifically, the ongoing
_COVID-19_ pandemic has seen a rise of inaccurate and misleading information
due to the surrounding controversies and unknown details at the beginning of
the pandemic. The _FakeNews_ task at MediaEval 2020 tackles this problem by
creating a challenge to automatically detect tweets containing misinformation
based on text and structure from Twitter follower network. In this paper, we
present a simple approach that uses BERT embeddings and a shallow neural
network for classifying tweets using only text, and discuss our findings and
limitations of the approach in text-based misinformation detection.

††copyright: rightsretained††doi: ††isbn: ††conference: Multimedia Evaluation
Workshop; December 14-15 2020; Online††journalyear: 2020

##  1\. Introduction and Related Work

The _FakeNews_ task (Pogorelov et al.,
2020)111https://multimediaeval.github.io/editions/2020/tasks/fakenews/ focuses
on automatically predicting whether a tweet consists of misinformation
(conspiracy) over the use of two concepts _COVID-19_ and _5G_ network. The
dataset also consists of other conspiracy tweets that are either over some
other concepts or accidentally contain the two buzzwords. The challenge
requires the participants to mainly develop text or structure based detection
models to automatically detect conspiracy tweets.

In the last five years, social media fake news detection has attracted a lot
of research interest in academia and industry. Consequently, the problem has
been approached from different perspectives including stance detection (Riedel
et al., 2017; Hanselowski et al., 2018), claim detection and verification
(Elsayed et al., 2019; Barrón-Cedeno et al., 2020), sentiment analysis (Cui et
al., 2019; Ajao et al., 2019), etc. To learn a model from text, recently
different variants of neural networks have been used for fake news detection.
Convolutional Neural Networks (CNN) in general have been extensively used with
word embeddings in several works (Yang et al., 2018; Fang et al., 2019;
Kaliyar et al., 2020) for social media fake news detection. Recently, Ajao et.
al. (Ajao et al., 2018) proposed a hybrid model with a Convolutional Neural
Network (CNN) and a Recurrent Neural Network (RNN) to identify fake news on
Twitter. In similar CLEF challenges (Elsayed et al., 2019; Barrón-Cedeno et
al., 2020) over the years, the problem of claim detection in tweets has been
tackled with a combination of rich set of features and different kinds of
classifiers like SVM (Zuo et al., 2018), gradient boosting (Yasser et al.,
2018) and sequential neural networks (Hansen et al., 2018). However, several
works (Williams et al., 2020; Cheema et al., 2020) recently have moved from
using word2vec (Mikolov et al., 2013) type embeddings to rich contextual deep
transformer _BERT_ (Bidirectional Encoder Representations from Transformers)
(Devlin et al., 2019) like embeddings.

##  2\. Approach

We approach the problem from only the textual perspective and rely on training
a shallow neural network over contextual word embeddings. Our submitted models
use the recently proposed _BERT-large_ based model pre-trained (Müller et al.,
2020) on a large corpus of _COVID_ Twitter data. This essentially improves the
performance by 3-4% in comparison to vanilla _BERT_ (V-BERT) since the
embeddings are better aligned (with regard to _COVID_) for the task at hand.
We also experiment with additional features like sentiment, subjectivity and
lexical features that have been shown to improve performance in similar tasks
(Elsayed et al., 2019; Barrón-Cedeno et al., 2020). We observed no
improvements using combination of these features and excluded them in this
paper.222Source code: https://github.com/cleopatra-itn/TIBVAMediaEvalFakeNews

Text Pre-processing For vanilla _BERT-large_ , we use Baziotis et. al.’s
(Baziotis et al., 2017) tool to apply the following normalization steps:
tokenization, lower-casing, removal of punctuation, spell correction,
normalize hashtags, all-caps, censored, elongated and repeated words, and
remove terms like URL, email, phone, user mentions. For _COVID_ Twitter BERT
(Müller et al., 2020), we follow their pre-processing which normalizes text,
and additionally replaces user mentions, emails, URLs with special keywords.

Contextual Feature Extraction To get one embedding per tweet, we follow the
observations made by Devlin et al. (2019) that different layers of _BERT_
capture different kinds of information, so an appropriate pooling strategy
should be applied depending on the task. The paper also suggests that the last
four hidden layers of the network are good for transfer learning tasks and
thus we experiment with 4 different combinations, i.e., concatenate last 4
hidden layers (4-CAT), the average of last 4 hidden layers (4-SUM), last
hidden layer (LAST), and $2^{nd}$ last hidden layer (2-LAST). We normalize the
final embedding so that $l2$ norm of the vector is 1.

Shallow Neural Network We use the extracted and pooled _BERT_ embeddings and
train a two-layer neural network. Before passing the features through the
first layer, we apply a squeeze and excitation (SE) operation (Hu et al.,
2018) that enhances the representation to learn a better model. The SE
operation has been shown to improve feature representations and performance in
CNNs. Then, the embedding is projected down to 128 dimensions, which is
followed by batch normalization and ReLU operation to introduce non-linearity.
The $2^{nd}$ layer is a linear classification layer that produces a softmax
probability for each class. Dropout with rate of 0.2 and 0.5 is applied after
SE operation and first layer to avoid over-fitting.

Final Prediction on Test Set We train five models on 5-fold splits and take
the majority label as the predicted label for the tweet. As described in the
challenge, the 3-class submissions can have an additional cannot-determine
class. We assign a tweet with this label if the softmax probability is less
than 0.4, which signifies that the model is not confident enough.

##  3\. Experimental Results

The _FakeNews_ development set consists of 5,999 extracted tweets over three
classes: _5G_ and _COVID-19_ conspiracy (1,128 samples), Non-conspiracy (4,173
samples) and other conspiracy (698 samples). We generate five-fold stratified
training and validation splits in the ratio of 80:20, so that the distribution
of classes remains the same in the training and validation sets. The official
test data originally consisted of 3,230 tweets, out of which 308 are not valid
or non-existent at the time of evaluation since participants were required to
crawl tweets on their own. Table 1 shows the performance of different models
on validation sets, while Table 2 shows the evaluation of our submitted models
on the official test data. All the runs for the test data use _COVID_ Twitter
BERT (C-BERT) extracted features. Official metric is Matthews correlation
coefficient (MCC). For validation sets, we provide both average accuracy (ACC)
and MCC scores. In Table 1, we also show the result of fine-tuning (FT) the
last two and four layers of 2 BERT variants with a linear classification layer
on top of BERT’s _CLS_ embedding. Although the average performance of
finetuning 4 layers is marginally better than the fixed average word
embeddings, the highest in two of the splits is better in the fixed embedding
plus neural network.

Table 1. Model Evaluation of Validation Set. Model | Pooling | Classes | ACC | MCC
---|---|---|---|---
V-BERT (FT)2 | _CLS_ | 3 | 0.7616 $\pm$ 0.0125 | 0.4521 $\pm$ 0.0347
V-BERT (FT)4 | _CLS_ | 3 | 0.7656 $\pm$ 0.0094 | 0.4611 $\pm$ 0.0266
C-BERT (FT)2 | _CLS_ | 3 | 0.8131 $\pm$ 0.0063 | 0.5837 $\pm$ 0.0107
C-BERT (FT)4 | _CLS_ | 3 | 0.8171 $\pm$ 0.0091 | 0.5952 $\pm$ 0.0192
C-BERT + NN | 4-SUM | 3 | 0.8138 $\pm$ 0.0112 | 0.5793 $\pm$ 0.0272
4-CAT | 3 | 0.8163 $\pm$ 0.0112 | 0.5841 $\pm$ 0.0264
2-LAST | 3 | 0.813 $\pm$ 0.0073 | 0.5761 $\pm$ 0.0181
LAST | 3 | 0.8083 $\pm$ 0.0085 | 0.5662 $\pm$ 0.0211
C-BERT + NN | 4-SUM | 2 | 0.8881 $\pm$ 0.0122 | 0.6173 $\pm$ 0.0401
4-CAT | 2 | 0.8901 $\pm$ 0.0087 | 0.6236 $\pm$ 0.0330
2-LAST | 2 | 0.8886 $\pm$ 0.0103 | 0.6184 $\pm$ 0.0357
LAST | 2 | 0.8838 $\pm$ 0.0058 | 0.5976 $\pm$ 0.0218
Table 2. Official Test Data Results. 3-class submissions include an additional cannot-determine (CD) class when the model confidence is lower than 0.4. Submission | Classes | MCC
---|---|---
Run 1 (4-SUM) | 3+CD | 0.5717
Run 2 (4-CAT) | 3+CD | 0.5773
Run 3 (4-SUM) | 2 | 0.5986
Run 4 (4-CAT) | 2 | 0.6083

##  4\. Discussion

Our findings and observations from the FakeNews task can be summarized as
follows:

  * •

Vanilla _BERT_ clearly has a wider domain gap to perform well on this task, as
the concepts and keywords related to _COVID_ are fairly recent. The _COVID_
Twitter _BERT_ outperforms in our finetuning experiment as well as with a
shallow neural network on the extracted embeddings.

  * •

The pooling operation and the number of last layers to obtain a sentence
embedding does make a difference, as only using the last layer (or $2^{nd}$
last) performs marginally lower across the metrics. An even better embedding
could be a sentence embedding extracted from a sentence-transformer (Reimers
and Gurevych, 2019), but only if it is pretrained on a _COVID_ Twitter corpus
to narrow down the domain and knowledge gap.

  * •

Although two-class prediction performance has higher metric scores, merging
the other-conspiracy and
non-conspiracy tweets decreases the true positives (see Figure 1) for the
conspiracy class. This could be because the model is able to learn and detect
the conspiracy aspect in tweets, and merging the other two categories
negatively impacts the learning.

  * •

In similar social media challenges, pre-processing text also plays a
significant role. Therefore, we experimented with replacing different keywords
like corona, sars cov2, wuhan virus, ncov, korona, koronavirus with
coronavirus or covid, and similarly five g, fiveg, 5 g with 5g. Unfortunately,
doing so degraded the performance in some splits and was not a part of our
submission model.

(a) 3-class

(b) 2-class

Figure 1. Confusion matrices for the different settings

##  5\. Conclusion

In this paper, we have presented our solution for the FakeNews detection task
of MediaEval 2020. The described solution is based on extracting embeddings
from transformer models and training shallow neural networks. We compared the
two transformer models and observed that _BERT_ transformer pre-trained on
_COVID_ tweets performs better than vanilla version. Pooling operations such
as concatenation or averaging of embeddings of the last hidden layers also
play an important role as shown by experimental evaluation. In future work, we
will focus on the integration of additional contextual information that is
presented via external links along with data from other modalities such as
images.

## Acknowledgements

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie grant
agreement no 812997 (CLEOPATRA ITN).

## References

  * (1)
  * Ajao et al. (2018) Oluwaseun Ajao, Deepayan Bhowmik, and Shahrzad Zargari. 2018\.  Fake news identification on twitter with hybrid cnn and rnn models. In Proceedings of the 9th international conference on social media and society. 226–230.
  * Ajao et al. (2019) Oluwaseun Ajao, Deepayan Bhowmik, and Shahrzad Zargari. 2019\.  Sentiment aware fake news detection on online social networks. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2507–2511.
  * Barrón-Cedeno et al. (2020) Alberto Barrón-Cedeno, Tamer Elsayed, Preslav Nakov, Giovanni Da San Martino, Maram Hasanain, Reem Suwaileh, Fatima Haouari, Nikolay Babulkov, Bayan Hamdan, Alex Nikolov, and others. 2020\.  Overview of CheckThat! 2020: Automatic identification and verification of claims in social media. In International Conference of the Cross-Language Evaluation Forum for European Languages. Springer, 215–236.
  * Baziotis et al. (2017) Christos Baziotis, Nikos Pelekis, and Christos Doulkeridis. 2017\.  DataStories at SemEval-2017 Task 4: Deep LSTM with Attention for Message-level and Topic-based Sentiment Analysis. In Proceedings of the 11th International Workshop on Semantic Evaluation (SemEval-2017). Association for Computational Linguistics, Vancouver, Canada, 747–754.
  * Cheema et al. (2020) Gullal S. Cheema, Sherzod Hakimov, and Ralph Ewerth. 2020\.  Check_square at CheckThat! 2020 Claim Detection in Social Media via Fusion of Transformer and Syntactic Features. In Working Notes of CLEF 2020 - Conference and Labs of the Evaluation Forum, Thessaloniki, Greece, September 22-25, 2020 (CEUR Workshop Proceedings), Linda Cappellato, Carsten Eickhoff, Nicola Ferro, and Aurélie Névéol (Eds.), Vol. 2696. CEUR-WS.org.  http://ceur-ws.org/Vol-2696/paper_216.pdf
  * Cui et al. (2019) Limeng Cui, Suhang Wang, and Dongwon Lee. 2019.  SAME: sentiment-aware multi-modal embedding for detecting fake news. In Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 41–48.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics. Association for Computational Linguistics, 4171–4186.  https://doi.org/10.18653/v1/n19-1423
  * Elsayed et al. (2019) Tamer Elsayed, Preslav Nakov, Alberto Barrón-Cedeno, Maram Hasanain, Reem Suwaileh, Giovanni Da San Martino, and Pepa Atanasova. 2019\.  Overview of the CLEF-2019 CheckThat! Lab: automatic identification and verification of claims. In International Conference of the Cross-Language Evaluation Forum for European Languages. Springer, 301–321.
  * Fang et al. (2019) Yong Fang, Jian Gao, Cheng Huang, Hua Peng, and Runpu Wu. 2019.  Self multi-head attention-based convolutional neural networks for fake news detection.  PloS one 14, 9 (2019), e0222713.
  * Hanselowski et al. (2018) Andreas Hanselowski, Avinesh PVS, Benjamin Schiller, Felix Caspelherr, Debanjan Chaudhuri, Christian M Meyer, and Iryna Gurevych. 2018\.  A retrospective analysis of the fake news challenge stance detection task.  arXiv preprint arXiv:1806.05180 (2018).
  * Hansen et al. (2018) Casper Hansen, Christian Hansen, Jakob Grue Simonsen, and Christina Lioma. 2018.  The Copenhagen Team Participation in the Check-Worthiness Task of the Competition of Automatic Identification and Verification of Claims in Political Debates of the CLEF-2018 CheckThat! Lab.. In CLEF (Working Notes).
  * Hu et al. (2018) Jie Hu, Li Shen, and Gang Sun. 2018.  Squeeze-and-excitation networks. In Proceedings of the IEEE conference on computer vision and pattern recognition. 7132–7141.
  * Kaliyar et al. (2020) Rohit Kumar Kaliyar, Anurag Goswami, Pratik Narang, and Soumendu Sinha. 2020.  FNDNet–A deep convolutional neural network for fake news detection.  Cognitive Systems Research 61 (2020), 32–44.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013.  Distributed representations of words and phrases and their compositionality.  Advances in neural information processing systems 26 (2013), 3111–3119.
  * Müller et al. (2020) Martin Müller, Marcel Salathé, and Per E Kummervold. 2020\.  COVID-Twitter-BERT: A Natural Language Processing Model to Analyse COVID-19 Content on Twitter.  arXiv preprint arXiv:2005.07503 (2020).
  * Pogorelov et al. (2020) Konstantin Pogorelov, Daniel Thilo Schroeder, Luk Burchard, Johannes Moe, Stefan Brenner, Petra Filkukova, and Johannes Langguth. 2020.  FakeNews: Corona Virus and 5G Conspiracy Task at MediaEval 2020. In MediaEval 2020 Workshop.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 3973–3983.
  * Riedel et al. (2017) Benjamin Riedel, Isabelle Augenstein, Georgios P Spithourakis, and Sebastian Riedel. 2017.  A simple but tough-to-beat baseline for the Fake News Challenge stance detection task.  arXiv preprint arXiv:1707.03264 (2017).
  * Williams et al. (2020) Evan Williams, Paul Rodrigues, and Valerie Novak. 2020\.  Accenture at CheckThat! 2020: If you say so: Post-hoc fact-checking of Claims using Transformer-based Models. In Working Notes of CLEF 2020 - Conference and Labs of the Evaluation Forum, Thessaloniki, Greece, September 22-25, 2020 (CEUR Workshop Proceedings), Linda Cappellato, Carsten Eickhoff, Nicola Ferro, and Aurélie Névéol (Eds.), Vol. 2696. CEUR-WS.org.  http://ceur-ws.org/Vol-2696/paper_226.pdf
  * Yang et al. (2018) Yang Yang, Lei Zheng, Jiawei Zhang, Qingcai Cui, Zhoujun Li, and Philip S Yu. 2018\.  TI-CNN: Convolutional neural networks for fake news detection.  arXiv preprint arXiv:1806.00749 (2018).
  * Yasser et al. (2018) Khaled Yasser, Mucahid Kutlu, and Tamer Elsayed. 2018\.  bigIR at CLEF 2018: Detection and Verification of Check-Worthy Political Claims.. In CLEF (Working Notes).
  * Zuo et al. (2018) Chaoyuan Zuo, Ayla Karakas, and Ritwik Banerjee. 2018\.  A Hybrid Recognition System for Check-worthy Claims Using Heuristics and Supervised Learning.. In CLEF (Working Notes).


# VALUE: Large Scale Voting-based Automatic Labelling
for Urban Environments

Giacomo Dabisias1,2, Emanuele Ruffaldi1, Hugo Grimmett2, and Peter Ondruska2
1PERCRO Laboratory, TeCIP Institute, Scuola Superiore Sant’Anna, Pisa, Italy.
{g.dabisias<EMAIL_ADDRESS>Vision Labs, London, United
Kingdom.
{giacomo, hugo<EMAIL_ADDRESS>
###### Abstract

This paper presents a simple and robust method for the automatic localisation
of static 3D objects in large-scale urban environments. By exploiting the
potential to merge a large volume of noisy but accurately localised 2D image
data, we achieve superior performance in terms of both robustness and accuracy
of the recovered 3D information. The method is based on a simple distributed
voting schema which can be fully distributed and parallelised to scale to
large-scale scenarios. To evaluate the method we collected city-scale data
sets from New York City and San Francisco consisting of almost 400k images
spanning the area of 40 km2 and used it to accurately recover the 3D positions
of traffic lights. We demonstrate a robust performance and also show that the
solution improves in quality over time as the amount of data increases.

##  I Introduction

The next generation of self-driving cars will likely operate more robustly by
using maps of their environment [1]. These maps allow the robots to have
strong priors on their environments to improve perception [2], and have metric
and semantic components for localisation and planning (top-left and top-right
in Fig. 1) [3]. For self-driving cars in urban environments, these semantic
maps typically contain static objects such as road signs, traffic lights, road
markings, etc. It is common to manually label these [4], but on the city-scale
this becomes prohibitively expensive, and furthermore it needs to be
laboriously relabelled as the urban landscape inevitably changes. A system
that can automatically generate such labels for entire cities without the need
for hand-labeling would be very valuable to overcome this issue. In this paper
we present such a system.

Figure 1: We use VALUE to automatically find the 3D locations of all traffic
lights in Manhattan, such that they can be used for autonomous driving. Zero
images were manually labeled to make this semantic map.

While the idea of using machine learning for automatic content detection has
been explored before, the use of large-scale accurate maps together with
machine learning opens new possibilities. Our work is inspired by the
possibility to merge large amounts of noisily labelled but accurately
localised data from a particular location. With this, we compute accurate,
denoised estimations of the semantic information of a superior quality.

Our contribution is a novel and simple system that (1) takes images, their
accurate 3D position in a large-scale environment and returns the 3D positions
of static object in the environment; (2) improves both object detection rate
and 3D object position accuracy as areas are revisited, making it scale and
work better with very large data sets; (3) deliberately avoids the need for
visually matching objects in-between the images, a problem that prevents most
similar systems from working on objects that (a) inherently look similar to
each other (like traffic lights) and (b) can appear very differently based on
time of day, lighting, weather conditions, season, etc.

We evaluate our system on two new large datasets taken from San Francisco and
New York City, in total comprising almost 0.4M images over 40 $km^{2}$ from
different times and weather conditions over a period of several weeks to
robustly recover position of the traffic lights in the environment. We
demonstrate that significantly superior results can be obtained using even
only mediocre and noisy 2D detection algorithms, if enough data are provided.

##  II Background

A number of works explore robust detection of static 3D objects in the
environment.

The basic component in a vision-based systems is an accurate 2D detection of
the object in a single image or video. Recently, this approach has been
dominated by deep learning techniques [5, 6, 7]. In this work we decided to
adopt a fully Convolutional Neural Network (CNN) as described by Huang et al.
[8] to detect traffic lights in a large collection of pictures.

Given two detections of the same object coming from a stereo camera, it is
possible to determine the 3D position of the object by triangulation [9, 10].
These approaches are viable, for example, for the online detection of relative
positions of objects around the vehicle

Similarly, if the position of multiple cameras observing the same object are
known, a multi-view triangulation approach can be used [11]. This has an
advantage over live detection since a significantly higher number of potential
views from different cameras can be collected over extended periods of time,
resulting into potentially significantly higher performance. We take this
approach in our work when we use large collection of 2D observations to
produce accurate, denoised 3D locations.

A common problem in applying such approaches relies in the need to accurately
localise a set of sensors in the area. This problem can be addressed by using
a highly-precise GPS system. Unfortunately, accuracy of GPS in dense urban
environments is limited due to low sky visibility. An alternative approach in
these environments consists in using a map-based localisation. Here state-of-
the-art structure-from-motion systems have demonstrated ability to construct
large-scale map of the environments [12]. We follow this approach and
construct a large-scale map of the city to localise accurately the positions
of all the traffic lights.

The most closely related work to ours is [13] where they use, similarly to us,
high-accuracy localisation of camera-equipped vehicles to map positions of
traffic lights in the environment. The main difference relies in the fact that
they use lidars for localisation, high resolution cameras for image
acquisition and a traffic light position prior database. Our work is novel for
the use of a robust triangulation method operating jointly on the set of all
the data from a particular location, resulting in improved performance as the
amount of data increases.

##  III Method

Our system takes a large set of 2D images $I_{i}$, with associated camera-
intrinsics parameters $q_{i}$ and 6 degrees-of-freedom poses
$P_{i}\in\mathbb{SE}(3)$, and produces a set of 3D positions of objects
$L_{i}\in\mathbb{R}^{3}$. In our work the images are captured from our mapping
fleet traversing various cities, and the poses are calculated using a large-
scale structure-from-motion (SFM) pipeline [14], but in general there is no
restriction on the source of the poses as long as they are accurate and
globally consistent.

The process then consists of two steps: (1) applying a noisy 2D detector to
each image $I_{i}$ resulting in a set of object detections
$Z_{i}\subset\mathbb{R}^{2}$ followed by (2) estimating their final 3D
positions $L$ by a simple voting-based triangulation algorithm.

###  III-A 2D Object Detection

We generate 2D object detections in the images using an off-the-shelf CNN
trained to predict bounding boxes for traffic lights [8]. These detections are
usually noisy and suffer from many false positives and false negatives. In
Sec. IV we show that our system compensates for these noisy detections if
shown a large amount of data. One alternative to using a detector is to use
hand-annotated labels from, for example, Amazon Mechanical Turk [15] which
have also been shown to suffer from label noise [16].

Algorithm 1 Robust Voting-Based Triangulation

Input: | $\mathbf{I}$ | set of images
---|---|---
| $\mathbf{Q}$ | camera intrinsics
| $\mathbf{P}$ |  $\mathbb{SE}(3)$ camera poses
| $d_{max}$ | maximum reprojection error
| $\alpha$ | minimum ratio of inliers
Output: | $\mathbf{L}$ | 3D positions of objects

| Detect objects in 2D images:
---|---
1. |  for $I_{i}\in\mathbf{I}$
2. |  $Z_{i}\leftarrow\textit{detect}(I_{i})$
3. | $\mathbf{Z}\leftarrow\cup_{i}\hskip 2.84526ptZ_{i}$
4. | $\mathbf{L}\leftarrow\emptyset$
5. |  for $(i_{a},i_{b})\in\mathbf{I}$
6. |  for $(z_{a},z_{b})\in{(\mathbf{Z}_{i_{a}},\mathbf{Z}_{i_{b})}}^{2}$
|  Compute 3D position of the object:
7. |  $l_{ab}\leftarrow\textit{triangulate}(\\{z_{a},z_{b}\\})$
|  Compute inliers for computed 3D position:
8. |  $S_{ab}\leftarrow\\{z_{k}|\forall z_{k}\in\mathbf{Z}:\pi(l_{ij},p_{k},q_{k})-z_{k}<d_{max}\\}$
| Find the hypothesis with most votes:
9. |  $a,b\leftarrow\operatorname*{arg\,max}_{a,b}|S_{ab}|$
10. |  if $|S_{ab}|\geq\alpha\cdot mean(|S|)$
11. |  $L\leftarrow L\cup\textit{triangulate}(S_{ab})$
12. |  $Z\leftarrow Z-S_{ab}$
13. |  goto $5$
14. |  return $\mathbf{L}$

###  III-B Robust Voting-based Triangulation

The output of the previous step is a large set of 2D detections. Importantly,
the 2D detection step cannot tell you which detections can be associated with
which physical 3D traffic light $D_{i}$, and any feature descriptors that it
might produce to associate them would be useless under the appearance changes
that we see in outdoor environments. This is true for any set of objects that
look similar (traffic lights are a good example). The only difference between
them is their position in 3D space. Without this association, classical
algorithms for multi-view triangulation can therefore not be directly used.
Instead, we use a robust voting-based triangulation algorithm to jointly
determine these 2D associations and the position of the traffic lights in 3D
space.

Figure 2: An example of a cluster in the map consisting of several traversals
in differing conditions. Top: Close-up of the dataset clustering. Bottom row:
example frames that are from different traversals belonging to the highlighted
cluster and associated traffic lights.

.

For each pair of detections $(z_{a},z_{b})$ (where $a$ and $b$ are indices
into 2D detections) from two different images $I_{i}$, $I_{j}$ we create a 3D
hypothesis $h_{ab}$ under the assumption that these two detections correspond
to the same physical 3D traffic light generating in total $\mathcal{O}(N^{2})$
hypotheses where $N$ is the total number of detected traffic lights. The 3D
position $l^{*}$ of each hypothesis can be determined by $K$-view
triangulation (in this case $K=2$), where we minimise the sum of the
reprojection errors:

$l^{*}=\operatorname*{arg\,min}_{l}\sum_{k\in
W}\big{(}\pi(l,p_{k},q_{k})-z_{k}\big{)}^{2},$ (1)

where $W$ is {a,b} in this case, $\pi$ is the projection of the 3D point $l$
into the camera at position $p_{k}$ with intrinsics $q_{k}$ and $z_{k}$ is the
center of the closes traffic light in the image. We consider a hypothesis
viable if it satisfies the following:

  1. 1.

_triangulation constraint_ : the point is triangulated in front of each camera
in a valid distance range,

  2. 2.

_rays intersect in 3D space_ : the reprojection error is smaller than
$d_{\text{max}}$,

  3. 3.

_the projection is stable_ : the angle between the optical axes is larger than
$\theta_{min}$,

  4. 4.

_distance to camera_ : the distance from the traffic light to either camera is
less than $r_{max}$.

Optionally, additional constraints reflecting prior information about the
location of a traffic lights can be used to further restrict the hypothesis
space.

For each hypothesis $h_{ab}$ we compute the set of consistent inliers
$S_{ab}$. This set consists of all the 2D detections that observe a traffic
light at the same location, which is computed by projecting the 3D position
$l^{*}$ into each image and verifying whether the projected position is less
than $d_{\text{max}}$ to any 2D detection. This parameter can be tuned to
obtain a lower reprojection error at the cost of the number of correctly
triangulated traffic lights. Next, we remove the hypothesis with the maximum
number of votes and also remove the detections that voted for it (inlier
detections). This process is repeated until no hypothesis with at least
$\alpha\cdot M$ inliers is found, where $M$ is the average number of inliers
per hypothesis and $\alpha$ is a tunable parameter over the confidence. This
creates a set of confirmed hypotheses. An important theoretical property of
this schema is that in the case of noisy but unbiased 2D detector and a
uniform distribution of the data, it converges to the correct solution as the
amount of data increases. This is due to noisy detections forming hypotheses
with small numbers of votes, and correct detections gathering consistent votes
over time. As the amount of data increases, these two metrics begin to
separate, and $\alpha$ is the threshold on their ratio.

Finally, for every hypothesis we refine its 3D position by optimising the
reprojection error from (1) over all the hypothesis detections. This entire
algorithm is presented in Alg. 1.

###  III-C Large-Scale System

The above method works well for small-scale scenario but does not scale well
to large, city-scale settings we are interested in due to its potential
$\mathcal{O}(N^{3}*M^{2})$ complexity where $M$ is the number of images $N$ is
the average number of detected traffic lights in each image. Instead, we
resort to a distribution schema based on splitting the data set to clusters,
running Alg. 1 for each cluster independently, and then merging the results.

We employ a simple clustering schema where, for each traffic light, we add to
its cluster all images closer than $N_{\text{max}}$ meters (50m default). An
illustration of these clusters is shown in Fig. 2.

After each cluster is triangulated using Alg. 1, it might be the case that the
same traffic light is triangulated in two different clusters. To resolve this
issue we merge all pairs of traffic lights closer than $1m$, producing the
final set of labels $L$. It would be possible to further optimize the final
results by globally optimizing the positions of the traffic lights in the map,
but this has not been done given the high computational cost.

##  IV Experiments

We evaluate the presented system on two large-scale data sets from San
Francisco and New York City that we collected using a dedicated fleet of
mapping vehicles. We demonstrate that the presented system scales to the size
of cities, and that as the amount of data increases it generates increasingly
accurate results both in terms of successfully recovered traffic lights and
their 3D positions, despite using a very inaccurate off-the-shelf 2D detector.

| _San Francisco_ | _New York City_
---|---|---
# images | 12048 | 360207
# detections | 17198 | 547689
# clusters | 172 | 3941
# traffic lights | 183 | 1732
# detectable traffic lights | 167 | 1906
mean # views / cluster | 70.05 | 91.4
mean # detections / frame | 1.65 | 2.84
# images with 0 detection | 1587 | 44483
# images with 1 detections | 6231 | 145608
# images with 2 detections | 2389 | 125924
# images with 3 detections | 1346 | 32487
# images with 4 detections | 369 | 7754
# images with 5 detections | 98 | 2700
# images with 6 detections | 17 | 802
# images with 7 detections | 9 | 283
# images with 8 detections | 0 | 80
# images with 9 detections | 1 | 51
# images with 10+ detections | 1 | 35
Table I: Per-dataset statistics of 2D detection and clustering. | _San Francisco_ | _New York City_
---|---|---
true positives | 156 | 1560
false positives | 4 | 84
false negatives | 11 | 172
duplicates | 14 | 56
mean reprojection error | 2.94 | 3.24
Table II: The results of the method on two datasets.

###  IV-A Data Sets

The San Francisco and New York City data sets have been created by capturing
images using a fleet of vehicles. The vehicles traversed most of the roads
multiple times, in both directions, at varying times of day and weather
conditions. During this time they captured images at regular intervals.
Example images are shown in Figs. 1 and 2. Each of these images has associated
ground-truth 2D labels of traffic lights.

We resize each image to $640\times 480$ pixels and use a large-scale,
distributed, structure-from-motion pipeline [12, 17] running on multiple
computers to calculate the 3D positions $P$ of the images.

Each data set covers an area with a certain number of physical traffic lights.
Not all of them are recoverable, i.e. their 3D positions cannot be accurately
determined. We consider a traffic light recoverable if it has been observed
from at least two different viewpoints under angle difference at least
$\theta_{min}$. In reality, as the amount of data increases, almost all the
traffic lights eventually become recoverable. The sizes of these data sets
together with their RMSE results are shown in Tab. I. We also present the
amount of traffic lights present in our dataset along with the number of
detectable traffic lights.

###  IV-B 2D Detection

We use a simple, convolutional neural network architecture to detect traffic
lights in 2D images. Firstly, we use a binary segmentation network [8] to
compute the probability that each pixel is part of a traffic light. We then
use a simple thresholding schema to compute connected components of pixels
representing traffic lights, and fit bounding boxes.

We train this network using the Bosch Data Set [18]. We split the data set
into a training set of size 5,093 and a testing set of size 8,334, covering in
total 24,242 traffic lights detections. For training we use two Nvidia P5000
cards until convergence. The network has been used to classify all the images
in our datasets.

In this work we purposely did not fine-tune the detector for either the San
Francisco or New York City data sets. There are significant differences
between the training and testing data: the Bosch data are from a suburban
area, while our data are urban; the cameras are different; and the training
data contain mostly small traffic lights while our evaluation data contain
traffic lights of all sizes. While the learned classifier achieves 90% recall
on the Bosch test data, it becomes a relatively noisy detector on our datasets
with a recall of 85% and an average Intersection-Over-Union (IOU) of 0.45.
Fine tuning the detector could possibly improve further the results, but this
has not been investigated.

###  IV-C Results

(a) New York City

(b) San Francisco

(c) New York City

(d) San Francisco

Figure 3: Performance of the system as a function of number of passes through
a location. As the amount of data increases both recall and 3D localisation
accuracy (as measured by negative reprojection error) increase.

We run the described clustering method from Section III on all the data. Fig.
2 shows the results of clustering in the San Francisco data set. Any clusters
can contains images from multiple passes of the mapping vehicles through the
area, as shown in Tab. III.

| _# clusters_
---|---
_# passes_ | _San Francisco_ | _New York City_
1 | 47 | 476
2 | 43 | 304
3 | 9 | 229
4 | 6 | 121
5 | 1 | 49
6 | 4 | 27
7 | 6 | 0
8 | 6 | 0
9 | 1 | 0
Table III: Statistics of a number of passes per cluster. As the mapping fleet
traverses the environment each place is visited several times. As discussed in
the text more passes through the environment result into higher performance of
the system.

Tab. II shows the statistics for the triangulation step. The presented method
is able to recover at least 90% of all the recoverable traffic lights in both
data sets, while suffering from only about 10% of false positive detections.
The average reprojection error of the triangulated objects for two datasets is
2.94 and 3.24 pixels for San Francisco and New York respectively. Note that
reprojection error incorporates both the error in the triangulated 3D object
and the underlying map accuracy. As discussed in Sec. III-C, during the
triangulation some of the traffic lights might be detected in two or more
different clusters and must be unified in the merge step. These form only a
small fraction of all the traffic lights. All results have been inspected
manually given the absence of ground truth for the 3D positions of traffic
lights.

(a)

(b)

(c)

Figure 4: Failure modes of the presented method. When not enough data from a
particular location are provided both (a) false negative detections due to the
undetected objects or (b) temporarily consistent wrong detections can
manifest. The largest challenge is (c) consistent and repeated detections of a
objects that look similar to a traffic light over a period of time.

Running the 2D detector over all 372k images took 30 hours. Clustering was
performed in 1.1 minutes for San Francisco and 19 minutes for New York City,
while the final triangulation took 1.1 and 3.1 minutes respectively.

Of primary importance is the performance of the system as the number of data
increases. We characterise this by an increasing number of passes through an
area. For this experiment we took a random subset of 25 clusters with at least
5 passes and computed the statistics of the number of recovered traffic lights
and their reprojection error. The results are shown in Fig. 3(a-b). Note that
the recall starts off poorly because not all traffic lights in a cluster are
detectable in a single pass, if for instance, they are angled orthogonally to
the direction of travel and increases with the number of passes through an
area. With increasing passes we are more likely to detect the traffic light
and have enough views to accurately localise it in 3D. We can see that the
likelihood of detecting a traffic light does increase with number of passes.
Note that the number of false positives for this random subset of 25 clusters
is zero.

Figs. 3(c-d) show that the 3D localisation accuracy also increases with number
of passes. We measure this by taking the 3D object position estimated using up
to $N$ passes and project it into the images from a _leave-one-out_ pass,
measuring the reprojection error between where that 3D object is projected
into the image and where it truly appears in the image. The statistics in Fig.
3 show that the system converges in both recoverability of the traffic lights
and their 3D position with more data.

Finally, we show some failure cases. The method converges under the assumption
that the underlying detector is unbiased, but might produce incorrect results
when this assumption is broken or when only a small amount of data are
provided. Figure 4 shows some of these cases. While the method is prone to
generate a number of false negative detections, the largest problem are the
false positive detections created by consistent, incorrect detections. While
some of them tend to appear only in a single pass (such as series of
reflections on a deck of the car) and thus can be resolved with more data, the
incorrect detections of traffic-light-like objects which are repeatedly and
consistently observed over periods of time poses a serious challenge to be
addressed in the future.

##  V Conclusions

We have demonstrated a simple and robust system for finding the 3D positions
of static objects in complex city environments. We leverage a reliable image
pose source and a large quantity of image data to overcome the common
challenges of noisy 2D labels. The resulting accurate 3D object positions are
borne out of a voting-based triangulation system that solves the data
association problem that poses a particularly difficult challenge when the
desired objects are similar in physical construction and yet appear vastly
different in images as a result of strong variations in lighting and weather.

The system is specifically designed in such a way to be parallelisable, and
therefore efficiently process very large image sets. We have evaluated our
system on city-scale data sets comprising almost 0.4M images, and have shown
that despite the very noisy input detections, the system output increases in
3D positional accuracy and recall with more data.

## References

  * [1] J. Janai, F. Güney, A. Behl, and A. Geiger, “Computer vision for autonomous vehicles: Problems, datasets and state-of-the-art,” _arXiv preprint 1704.05519_ , 2017.
  * [2] D. Barnes, W. Maddern, and I. Posner, “Exploiting 3d semantic scene priors for online traffic light interpretation,” in _Intelligent Vehicles Symposium (IV), 2015 IEEE_. IEEE, 2015, pp. 573–578.
  * [3] A. Nüchter and J. Hertzberg, “Towards semantic maps for mobile robots,” _Robotics and Autonomous Systems_ , vol. 56, no. 11, pp. 915–926, 2008.
  * [4] J. Stallkamp, M. Schlipsing, J. Salmen, and C. Igel, “The german traffic sign recognition benchmark: a multi-class classification competition,” in _Neural Networks (IJCNN), The 2011 International Joint Conference on_. IEEE, 2011, pp. 1453–1460.
  * [5] V. John, K. Yoneda, B. Qi, Z. Liu, and S. Mita, “Traffic light recognition in varying illumination using deep learning and saliency map,” in _Intelligent Transportation Systems (ITSC)_. IEEE, 2014, pp. 2286–2291.
  * [6] G. Csurka and F. Perronnin, “A simple high performance approach to semantic segmentation.” in _BMVC_ , 2008, pp. 1–10.
  * [7] D. Pathak, E. Shelhamer, J. Long, and T. Darrell, “Fully convolutional multi-class multiple instance learning,” _arXiv preprint arXiv:1412.7144_ , 2014.
  * [8] G. Huang, Z. Liu, and K. Q. Weinberger, “Densely connected convolutional networks,” _CoRR_ , vol. abs/1608.06993, 2016.
  * [9] R. I. Hartley and P. Sturm, “Triangulation,” _Computer vision and image understanding_ , vol. 68, no. 2, pp. 146–157, 1997.
  * [10] H.-L. Lee, “Critical points for two-view triangulation,” _arXiv preprint 1608.05512_ , 2016.
  * [11] R. Hartley and A. Zisserman, _”Multiple view geometry in computer vision”_. Cambridge university press, 2003\.
  * [12] B. Klingner, D. Martin, and J. Roseborough, “Street view motion-from-structure-from-motion,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2013, pp. 953–960.
  * [13] N. Fairfield and C. Urmson, “Traffic light mapping and detection,” in _ICRA_. IEEE, 2011, pp. 5421–5426.
  * [14] J. J. Koenderink and A. J. Van Doorn, “Affine structure from motion,” _JOSA A_ , vol. 8, no. 2, pp. 377–385, 1991.
  * [15] M. Buhrmester, T. Kwang, and S. D. Gosling, “Amazon’s mechanical turk: A new source of inexpensive, yet high-quality, data?” _Perspectives on psychological science_ , vol. 6, no. 1, pp. 3–5, 2011.
  * [16] B. Frénay and M. Verleysen, “Classification in the presence of label noise: a survey,” _IEEE transactions on neural networks and learning systems_ , vol. 25, no. 5, pp. 845–869, 2014.
  * [17] S. Zhu, T. Shen, L. Zhou, R. Zhang, J. Wang, T. Fang, and L. Quan, “Parallel structure from motion from local increment to global averaging,” _ArXiv e-prints_ , 2017.
  * [18] K. Behrendt and L. Novak, “A deep learning approach to traffic lights: Detection, tracking, and classification,” in _ICRA_. IEEE, 2017, pp. 1370–1377.