\section{Introduction}

The computation of feedback control for differential equations is an important topic due to applications in real life problems. Usually, one uses the dynamic programming principle and the Hamilton--Jacobi--Bellman (HJB) equations to derive the control in feedback form (see e.g. \cite{BCD97} for a complete description of the method). The major issue of this approach is that the solution of the HJB equation is not analytical and we need to build numerical approximations. Although there exists a huge literature on the approximation (see e.g. \cite{FF13}),  numerical methods suffer from the curse of dimensionality, namely the complexity of the problem increases as the dimension of the system we want to control does. In the last decades, there were a tremendous effort in mitigating the curse of dimensionality using different methods such as: model order reduction \cite{KVX04, AFV17}, spectral methods \cite{KK18}, max-plus algebra \cite{ME07, ME09}, neural networks \cite{DLM20, DM21}, tensor decomposition \cite{DKK21, OSS22, DKL22}, sparse grids method \cite{GK17} and radial basis functions \cite{AOS21}.

Recently, in \cite{AFS18} it has been introduced a tree structure algorithm to approximate the HJB equation for finite horizon problem. The value function is computed using a DP algorithm on a tree structure algorithm (TSA) constructed by the time discrete dynamics. In this way there is no need to build a fixed space triangulation and to project on it: the tree will guarantee a perfect matching with the discrete dynamics and drop off the cost of the space interpolation allowing for the solution of very high-dimensional problems. Moreover, a pruning technique has been implemented to reduce the number of branches and the exponential complexity of the tree. Error estimates have been derived in \cite{SAF19} for the TSA, including the pruning technique, to guarantee first order convergence. Later, the method has been extended to high order methods in \cite{AFS18b}, state constraint problems \cite{AFS20} and coupled with model order reduction to deal with large scale problems \cite{AS19}.

In this work, we conclude the study of the TSA explaining how to build the feedback control. Indeed, in the works presented before the control was linked to the nodes of the tree and it was not able to be obtained for different initial conditions. In fact, the methods could not reconstruct the control for points outside of the tree nodes. Here, we propose two algorithms based on scattered interpolation to overcome this limit. In particular, given the tree structure and the information of the value function on it, one may apply interpolation operators on scattered data to construct the value function, and hence the feedback map, on points not belonging to the tree.

The outline of the paper is the following. In Section 2, we recall the tree structure algorithm and the main ingredients for the resolution of the dynamic programming principle on the TSA. Section 3  is devoted to the study of our new method to reconstruct feedback control based on the use of interpolation techniques on scattered dataset. Finally, in Section 4 we present a numerical test to show the effectiveness of the proposed methodology.

\section{The tree structure algorithm}

In this section we will recall the {\em finite horizon control problem} and its approximation by the TSA (see \cite{AFS18} for a complete description of the method). Let us consider the following dynamics
\begin{equation}\label{eq}
\left\{ \begin{array}{l}
\dot{y}(s)=f(y(s),u(s),s), \;\; s\in(t,T],\\
y(t)=x\in\mathbb R^d.
\end{array} \right.
\end{equation}
where $y:[t,T]\rightarrow\mathbb R^d$ is the solution, $u:[t,T]\rightarrow\mathbb R^m$ is the control, $f:\mathbb R^d\times\mathbb R^m\times[t,T]\rightarrow\mathbb R^d$ is the dynamics and
\[\mathcal{U}=\{u:[t,T]\rightarrow U, \mbox{measurable} \}
\]
is the set of admissible controls within the compact set $U\subset \mathbb R^m$.
We assume that there exists a unique solution for \eqref{eq} for each $u\in\mathcal{U}$.
The cost functional we want to minimize read

\begin{equation}\label{cost}
 J_{x,t}(y,u):=\int_t^T L(y(s),u(s),s)e^{-\lambda (s-t)}\, ds+g(y(T))e^{-\lambda (T-t)},
\end{equation}
where $L:\mathbb R^d\times\mathbb R^m\times [t,T]\rightarrow\mathbb R$ is the running cost and $\lambda\geq0$ is the discount factor.
Finally, the optimal control problem is
\begin{equation}\label{ocp}
\min_{u\in \mathcal{U}} J_{x,t}(y,u), \mbox{ subject to } y(\cdot;u) \mbox{ solution of  \eqref{eq}}
\end{equation}
We assume that the functions $f, L$ and $g$ are bounded and Lipschitz-continuous with respect to the first variable to guarantee existence and uniqueness of the control problem \eqref{ocp}.

The value function is defined as follows
\begin{equation}
v(x,t):=\inf\limits_{u\in\mathcal{U}} J_{x,t}(u)
\label{value_fun}
\end{equation}
and satisfies the DPP, i.e. for every $\tau\in [t,T]$:
\begin{equation}\label{dpp}
v(x,t)=\inf_{u\in\mathcal{U}}\left\{\int_t^\tau L(y(s),u(s),s) e^{-\lambda (s-t)}ds+ v(y(\tau),\tau) e^{-\lambda (\tau-t)}\right\}.
\end{equation}
From \eqref{dpp}, one can derive the HJB equation for every $x\in\mathbb R^d$, $s\in [t,T)$:
\begin{equation}\label{HJB}
\left\{
\begin{array}{ll}
-\dfrac{\partial v}{\partial s}(x,s) +\lambda v(x,s)+\max\limits_{u\in U }\left\{-L(x, u,s)- \nabla v(x,s) \cdot f(x,u,s)\right\} = 0, \\
v(x,T) = g(x).
\end{array}
\right.
\end{equation}
Finally, the computation of the feedback control is straightforward, assuming the value function is known:
\begin{equation}\label{feedback}
u^*(x):=  \argmax_{u\in U }\left\{-L(x,u,t)- \nabla v(x,t) \cdot f(x,u,t)\right\}.
\end{equation}

Since equation \eqref{HJB} is a first non-linear PDE, it is hard to find an exact solution and numerical algorithms should take into account discontinuities in the gradient (see \cite{FF13} and the references therein). Introduced a time discretization of \eqref{HJB} with a time step $\Delta t: = [(T-t)/\overline N]$ and $\overline{N}$ number of steps, it is possible to consider the discrete version of the DPP \eqref{dpp}. More precisely, for $n= \overline{N}-1,\dots, 0$ and every $x\in \mathbb R^d$ we have

\begin{equation}\label{SL}
V^{n}(x)=\min\limits_{u\in U}[\Delta t\,L(x, u, t_n)+e^{-\lambda \Delta t}V^{n+1}(x+\Delta t f(x, u, t_n))],
\end{equation}
where $t_n=t+n \Delta t,\, t_{\overline N} = T$, and $V^n(x):=V(x, t_n).$ The iterative scheme \eqref{SL} is coupled with the terminal condition
\begin{equation}\label{SL_T}
V^{\overline{N}}(x)=g(x).
\end{equation}
In \eqref{SL} we use an explicit Euler scheme for a first order approximation to simplify the presentation (the high-order extension has been presented in \cite{AFS18b}). The term $V^{n+1}(x+\Delta t f(x, u, t_n))$ is usually obtained via interpolation on a fixed grid since $x+\Delta t f(x, u, t_n)$ is not a grid point (see \cite{FF13} for more details on this step). To bypass the interpolation step a tree structure is built where all the possible combinations of the term $x+\Delta t f(x, u, t_n)$ are computed  for different values of $u$. \\
First of all, let us consider a discrete version of the control domain, say $U=\{u_1,...,u_M \}$ with $M$ controls.
 We will denote the tree by $\mathcal{T}:=\cup_{j=0}^{\overline{N}} \mathcal{T}^j,$ where each $\mathcal{T}^j$ contains the nodes of the tree at time $t_j$. The first level $\mathcal{T}^0 = \{x\}$ is simply formed by the initial condition $x$. Starting from the initial condition $x$, we discretize the dynamics using  e.g. an explicit Euler scheme and we consider all the nodes obtained with different discrete controls $u_i \in U $
$$\zeta_{i}^1 = x+ \Delta t \, f(x,u_i,t_0),\qquad i=1,\ldots,M.$$
Therefore, we have $\mathcal{T}^1 =\{\zeta_1^1,\ldots, \zeta^1_M\}$.
The procedure can be easily iterated for each node of the level, obtaining at time $t_n$ the level $\mathcal{T}^n$:
$$\mathcal{T}^n = \{ \zeta^{n-1}_i + \Delta t f(\zeta^{n-1}_i, u_j,t_{n-1}) \}_{j=1}^{M}\quad i = 1,\ldots, M^{n-1}.$$
The entire tree can be represented in short as
 $$\mathcal{T}:= \{ \zeta_{i}^n  \}_{i=1}^{M^n},\quad n=0,\ldots \overline{N},$$
where the nodes $\zeta^n_i$ are the results of the dynamics at time $t_n$ with the controls $\{u_{j_k}\}_{k=0}^{n-1}$:
\begin{equation*}
\zeta_{i_n}^n = \zeta_{i_{n-1}}^{n-1} + \Delta t f(\zeta_{i_{n-1}}^{n-1}, u_{j_{n-1}},t_{n-1})
= x+ \Delta t \sum_{k=0}^{n-1} f(\zeta^k_{i_k}, u_{j_k},t_k),
\end{equation*}
with $\zeta^0 = x$, $i_k = \floor*{\dfrac{i_{k+1}}{M}}$ and $j_k\equiv i_{k+1} \mbox{mod } M$.

Although it is possible to deal with arbitrary high-dimensional problems, the construction of tree may be expensive since  $|\mathcal{T}|= O(M^{\overline{N}})$,
where $M$ is the number of discrete controls and $\overline{N}$ is the number of time steps. This leads to an exponential growth of the cardinality and it may be infeasible to apply the algorithm due to the huge amount of memory allocations, when $M$ or $\overline{N}$ are too large.
To mitigate this exponential growth a pruning criteria has been introduced.
Defining a threshold $\varepsilon_{\mathcal{T}}>0$, several branches of the tree can be cut off according to the distance between nodes. More precisely, if two nodes satisfies the following criteria
\begin{equation}\label{tol_cri}
\begin{array}{cc}
\Vert \zeta^n_i-\zeta^n_j \Vert \le \varepsilon_{\mathcal{T}},
\mbox{ for  }i\ne j \mbox{ and } n = 0,\ldots, \overline{N}.
\end{array}
\end{equation}
they can be merge, leading to a great gain in memory storage and computational time, keeping the same order of convergence (\cite{SAF19}).

The computation of the numerical value function $V(x,t)$ will be performed on the tree nodes in space as
\begin{equation}\label{num:vf}
V(x,t_n)=V^n(x), \quad \forall x \in \mathcal{T}^n,
\end{equation}

where $t_n=t+ n \Delta t$, following directly from the DPP. The tree $\mathcal{T}=\cup_{j=0}^{\overline{N}} \mathcal{T}^j$ given by the TSA defines a grid and we can write a time discretization on it for \eqref{HJB} as follows:

\begin{eqnarray}\label{HJBt2}
\begin{cases}
V^{n}(\zeta^n_i)= \min\limits_{u\in U} \{e^{-\lambda \Delta t} V^{n+1}(\zeta^n_i+\Delta t f(\zeta^n_i,u,t_n)) +\Delta t \, L(\zeta^n_i,u,t_n) \}, \hbox{ for }\zeta^n_i \in \mathcal{T}^n, n \le \overline{N}-1,\nonumber\\
V^{\overline{N}}(\zeta^{\overline{N}}_i)= g(\zeta_i^{\overline{N}}),  \qquad\quad \hbox { for }   \zeta_i^{\overline{N}} \in \mathcal{T}^{\overline{N}}.\qquad
\end{cases}
\end{eqnarray}

Since the set of controls $U$ is discrete, the minimization will be computed by comparison.
\medskip
\subsection{TSA and Model Order Reduction}
\label{POD}

The Tree Structure Algorithm has been also coupled with Proper Orthogonal Decomposition (see e.g. \cite{V13})  techniques in \cite{AS19}. The idea is to consider the projection of the dynamics onto a subspace spanned by particular orthogonal basis function in order to reduce the dimension and the complexity of the problem. Here, we sketch briefly the main concepts, the interested reader will find more details in \cite{AS19}.

Given the full dimensional dynamics \eqref{eq}, the TSA can be applied with few time steps and few controls to explore the manifold of all possible solutions. Collected all the nodes of the tree in a matrix $Y \in \mathbb{R}^{d \times N}$, called the \emph{snapshots matrix}, one can operate a Singular Value Decomposition of the matrix $Y$, obtaining $Y=\Psi \Sigma V^\top$, where $\Psi \in \mathbb{R}^{d \times d}$ and $V \in \mathbb{R}^{N \times N}$ are orthogonal matrices and $\Sigma \in \mathbb{R}^{d \times N}$ is a diagonal matrix with diagonal entries $\{\sigma_i\}_{i=1}^{\min\{d,N\}}$. The first $\ell \ll \min\{d,N\}$ columns of the matrix $\Psi$, $i.e.$ $\Psi^\ell =\{\psi_1, \ldots, \psi_\ell\}$, will represent the solution of the following minimization problem
\begin{equation*}\label{pbmin}
\min_{ {{\psi}}_1,\ldots,{{\psi}}_\ell\in\mathbb R^d} \sum_{j=1}^N \left|{ y}^j-\sum_{i=1}^\ell \langle { y}^j,{{\psi}}_i\rangle{{\psi}}_i\right|^2\quad \mbox{such that }\langle {{\psi}}_i,{{\psi}}_j\rangle=\delta_{ij}.
\end{equation*}
The number of basis $\ell$ can be fixed according to a criterium related to the projection error. More precisely, given a tolerance $\tau \in [0,1]$ the parameter $\ell$ can be chosen such that
\begin{equation}\label{POD_cri}
\mathcal{E}(\ell)=\dfrac{\sum_{i=\ell+1}^{\min\{d,N\}} \sigma_i^2}{\sum_{i=1}^{\min\{d,N\}} \sigma_i^2} \le \tau.
\end{equation}
The constructed matrix $\Psi^\ell$ will be then employed in the projection of the dynamics \eqref{eq}. Indeed, assuming the ansatz $y(t) \approx \Psi^\ell y^\ell(t)$ with $y^\ell(t) \in \mathbb{R}^\ell$, and the orthogonality of $\Psi^\ell$ the reduced dynamics reads
\begin{equation*}\label{pod_sys}
\left\{\begin{array}{l}
\dot{ y}^\ell(s)= (\Psi^\ell)^\top f( \Psi^\ell  y^\ell(s),u(s),s),\\
{ y}^\ell(t)={ \Psi^\ell}^\top x.
\end{array}\right.
\end{equation*}
In our numerical experiment we will use this method for the control of the heat equation to reduce the dimensionality of the problem.

\section{Feedback reconstruction and closed-loop control}
\label{subsec}

In this section we are going to present a technique to retrieve the feedback control based on the knowledge of the value function on the nodes of the tree. We are going to introduce two possible post-processing reconstruction which will be compared in the section of the numerical test.

The computational cost for the construction of the full tree is exponential in the number of discrete controls, for this reason it is better to consider few controls for the tree construction and for the resolution of the HJB equation. Once the value function is obtained on a tree-structure, we consider a post-processing procedure which takes into account a finer control set. This is possible thanks to the formula for the synthesis of the feedback control
\begin{equation} \label{feed:tree2}
u_{n}^{*}:=\mathop{\rm argmin}\limits_{u\in \tilde{U}} \left\{ e^{-\lambda \Delta t}V^{n+1}(x+\Delta t f(x,u,t_n)) +\Delta t \, L(x,u,t_n) \right\},
\end{equation}
where the $argmin$ will be computed on a finer set $\tilde{U}$ with respect to the initial set $U$. This minimization can be computed again by comparison, but we need to introduce an interpolation step on scattered data. In low dimension (i.e. two or three) one may consider a Delaunay triangulation of the data and then perform an interpolation on the triangulation. In high dimensions, the triangulation becomes infeasible and one has to proceed in different ways, for example via e.g. kernel methods (\cite{F15}) or via Model Order Reduction Techniques (\cite{AS19}). In the numerical test we will consider the latter case, considering a POD reduction of the dynamical system.

The method for the feedback reconstruction based on a minimization by comparison on a finer control set is presented in Algorithm \ref{alg_4}.
\begin{algorithm}[H]
\caption{Feedback reconstruction via comparison on a finer control set}
\label{alg_4}
\begin{algorithmic}[1]
 \State{Computation of the tree $\mathcal{T}$ and value function $\{V^k\}_k$ with control set $U$.}
 \State{Fix a new control set $\tilde{U}\supset U$ and $\zeta^0_*=x.$}
\For{$n=0,...,\overline{N}-1$}
 \For{$u_j \in \tilde{U}$}
    \State{$\zeta_j=\zeta^{n}_*+ \Delta t f(\zeta^{n}_*,u_j,t_{n})$}
    \State{Compute $V(\zeta_j,t_{n+1})$ via scattered interpolation with $(\mathcal{T}^{n+1},V^{n+1})$}
    \EndFor
    \State{$u_{n}^{*}:=\mathop{\rm argmin}\limits_{u_j\in \tilde{U}} \left\{ e^{-\lambda \Delta t}V(\zeta_j,t_{n+1}) +\Delta t \, L(\zeta^n_*,u_j,t_n) \right\}$}
    \State{$\zeta^{n+1}_*=\zeta^{n}_*+ \Delta t f(\zeta^{n}_*,u^*_n,t_{n})$}
    \EndFor
\end{algorithmic}
\end{algorithm}
The interpolation on scattered data can be computed via the MATLAB function

\texttt{scatteredInterpolant}. If the dynamics $f$ is autonomous, by Remark $3.3$ in \cite{AFS18} we know that we can compute at time $t_n$ the value function on the sub-tree $\cup_{k=0}^n \mathcal{T}^k$. In this case, in step $6$ we can compute the scattered interpolation with $\cup_{k=0}^n(\mathcal{T}^k,V^k)$, guaranteeing more information for a more efficient interpolation.

Now, let us consider a dynamics $f$ affine in the control $u\in \mathbb{R}$. By Remark $3.1$ in \cite{AFS18} we know that all the tree sons of a node lay on a segment. In this case we can apply one dimensional interpolation, for instance quadratic interpolation if we consider three discrete controls for each iteration. The quadratic interpolation is a reasonable choice in the Linear Quadratic Regulator case since we know that the value function is quadratic and then we do not introduce interpolation error in this case. Moreover, let us suppose that the running cost $L$ is of the form $L(x,u,t)=g(x,t)+\gamma|u|^2+\delta u$. In Algorithm \ref{alg_5} we describe this procedure based on a quadratic interpolation, fixing $\lambda=0$ for simplicity. In step $9$ the operator $\mathcal{P}_U$ stands for the projection operator onto the set $U$. We will use and compare these two techniques in the numerical experiment, where we will consider the optimal control for the heat equation.

\begin{algorithm}[H]
\caption{Feedback reconstruction via quadratic interpolation}
\label{alg_5}
\begin{algorithmic}[1]
\State{Computation of the tree $\mathcal{T}$ and value function $\{V^k\}_k$ with control set $U=\{u_1,u_2,u_3 \}$.}
 \State{$\zeta^0_*=x.$}
\For{$n=0,...,\overline{N}-1$}
 \For{$u_j \in U$}
    \State{$\zeta(u_j)=\zeta^{n}_*+ \Delta t f(\zeta^{n}_*,u_j,t_{n})$}
    \State{Compute $V(\zeta(u_j),t_{n+1})$ via scattered interpolation with $(\mathcal{T}^{n+1},V^{n+1})$}
    \EndFor
    \State{$V(\zeta(u),t_{n+1}) \approx au^2+bu+c, \quad \forall u\in [u_1,u_3]$}
    \If{$a+\Delta t\, \gamma>0$ }
    \State{$u_{n}^{*}=\mathcal{P}_{[u_1,u_3]}\left(-\frac{b+\Delta t \, \delta}{2(a+\Delta t\, \gamma)}\right) $}
    \Else

    \State{$u_{n}^{*}=\mathop{\rm argmin}\limits_{u_i \in \{u_1,u_3 \} } \left\{ V(\zeta(u_i),t_{n+1}) +\Delta t \, L(\zeta^n_*,u_i,t_n) \right\}$}

\EndIf
    \State{$\zeta^{n+1}_*=\zeta^{n}_*+ \Delta t f(\zeta^{n}_*,u^*_n,t_{n})$}
    \EndFor
\end{algorithmic}
\end{algorithm}
\section{Numerical experiment: Heat Equation}

In this example we consider the one dimensional heat equation with homogeneous Dirichlet boundary conditions
\begin{equation}
\begin{cases}
\partial_t y(x,t)= \sigma  y_{xx}(x,t) +  y_0(x)u(t) & (x,t) \in \Omega \times [0,T],
\\ y(x,t) =0 & (x,t) \in \partial \Omega \times [0,T], \\
y(x,0)=y_0(x) & x \in \Omega,
\end{cases}
\label{pde1}
\end{equation}

where the control $u(t)$ is taken in the admissible set $\mathcal{U}=\{u:[0,T]\rightarrow [-1,0] \}$, $\sigma=0.15$, $T=1$ and $\Omega=[0,1]$. The space domain is discretized with $1000$ nodes, leading to a dynamical system in dimension $\mathbb{R}^{1000}$. Since the problem is truly high dimensional, we are going to apply the POD reduction introduced in Section \ref{POD}.
We create a rough tree with two discrete controls and $\Delta t=0.1$ and we fix the tolerance $\tau=10^{-4}$ in \eqref{POD_cri}. This procedure yields a reduced dimension $\ell=2$. In this case two POD basis get enough information for a quasi-complete description of the system. Then, given the reduced dynamics, we compute the reduced tree structure and the value function with $11$ discrete controls and we compare the numerical value function computed by TSA-POD and by the Riccati equation (see e.g. \cite{AFIJ03}) according to the following errors
\begin{equation}
Err_{2}= \frac{\sum_{n=0}^N |V(y^n_*,t_n)-v(y^n_{R},t_n)|^2}{\sum_{n=0}^N |v(y^n_{R},t_n)|^2}, \quad
 Err_{\infty}=   \frac{ \max\limits_{n=0,...,N} |V(y^n_*,t_n)-v(y^n_{R},t_n)|}{  \max\limits_{n=0,...,N} |v(y^n_{R},t_n)|},
 \label{errors}
\end{equation}

where $\{y^n_*\}_n$ is the optimal trajectory computed via POD-TSA, while $\{y^n_{R}\}_n$ is the solution of the time dependent Riccati equation. The results are presented in Table \ref{test41:11contr}. The column Pruned/Full refers to the ratio between the cardinalities of the pruned tree and the full tree. Moreover, in Table \ref{test1:11contr} we recall the values obtained for the full dimensional problem. The coupling of the TSA with POD leads to more accurate results in less time. In particular, we see that for $\Delta t=0.0125$ we obtain a speed-up of a factor $7$ and a reduction of order $4$ for the cardinality of tree. In Figure \ref{fig3:cost11} we can observe the convergence of the cost functional and the approximation of the optimal control.

\begin{table}[htbp]
		\centering
		\begin{tabular}{cccccccc}
					\toprule
					 $\Delta t$ & Nodes & Pruned/Full & CPU & $Err_{2}$ &  $Err_{\infty} $ & $Order_{2}$  & $Order_{\infty}$  \\
					\midrule
					0.1 &     134 & 4.3e-10	 &  \phantom{x}0.1s&    0.244 &   0.220 &   & \\
					0.05 &   825 &  1.0e-19	 &  \phantom{x} 0.56s &   0.102 &  9.4e-2 &  1.25 &  1.22 \\
					0.025 &   11524 & 2.1e-39	 &  \phantom{x} 8.74s & 3.1e-2 & 3.0e-2  &   1.73 &    1.67 \\
					0.0125 &  194426 & 7.8e-80 &  \phantom{x}151s & 1.0e-2   &   8.2e-3 &  1.60 &   1.85  \\
			\bottomrule
		\end{tabular}
   	\caption{Test 1: Error analysis and order of convergence for TSA-POD method with $\varepsilon_{\mathcal{T}}= \Delta t^2$, $11$ discrete controls and $2$ POD basis.}
	\label{test41:11contr}
	\end{table}

\begin{table}[htbp]
		\centering
		\begin{tabular}{cccccccc}
					\toprule
					 $\Delta t$ & Nodes & Pruned/Full & CPU & $Err_{2}$ &  $Err_{\infty} $ & $Order_{2}$  & $Order_{\infty}$  \\
					\midrule
					0.1 &     134 & 4.7e-09	 &  \phantom{x}0.14s&    0.279 &   0.241 &   & \\
					0.05 &   863 & 1.2e-18	 &  \phantom{x} 0.65s &   0.144 &  0.118 &  0.95 &  1.03 \\
					0.025 &   15453 & 3.1e-38	 &  \phantom{x} 12.88s & 5.5e-2  & 5.3e-2  &  1.40 &    1.17 \\
					0.0125 &  849717 & 3.8e-78 &  \phantom{x}1.1e3s & 1.6e-2   &   1.6e-2 &  1.77 &  1.42  \\
			\bottomrule
		\end{tabular}
   	\caption{Test 1: Error analysis and order of convergence for forward Euler scheme of the TSA with $\varepsilon_{\mathcal{T}}= \Delta t^2$ and $11$ discrete controls.}
	\label{test1:11contr}
	\end{table}

\begin{figure}[htbp]
\centering
       \includegraphics[scale=0.45]{figures/POD/cost_heat.eps}
       \includegraphics[scale=0.45]{figures/POD/control_heat.eps}

       \caption{Test 1: Cost functional (left) and optimal control (right) with $11$ discrete controls. }
       \label{fig3:cost11}
	\end{figure}

\paragraph{Feedback reconstruction}

In this paragraph we are going to apply the feedback reconstruction techniques introduced in Section \ref{subsec}. We consider again $2$ POD basis and we solve the optimal control problem via POD-TSA with $3$ discrete controls. The results for this case are presented in Table \ref{test1:2contr}.

\begin{table}[htbp]
		\centering
		\begin{tabular}{cccccccc}
					\toprule
					 $\Delta t$ & Nodes & Pruned/Full & CPU & $Err_{2}$ &  $Err_{\infty} $ & $Order_{2}$  & $Order_{\infty}$  \\
					\midrule
					0.1 &     122 & 4.6e-04	 &  \phantom{x}  0.02s&    0.376 &   0.283 &   & \\
					0.05 &   689 &  4.4e-08	 &  \phantom{x} 0.19s &   0.178 &  0.136 &  1.08 &  1.06 \\
					0.025 &   9536 & 1.7e-16	 &  \phantom{x} 2.3s & 0.107 & 6.9e-2  &   0.73
 &    0.98
 \\
					0.0125 &  155293 & 2.3e-34 &  \phantom{x}37s & 0.0655   &   0.0394 &  0.71 &   0.80  \\
			\bottomrule
		\end{tabular}
   	\caption{Test 1: Error analysis and order of convergence for TSA-POD method with $\varepsilon_{\mathcal{T}}= \Delta t^2$, $3$ discrete controls and $2$ POD basis.}
	\label{test1:2contr}
	\end{table}
	Then, we pass to the post-processing procedure: we consider Algorithm \ref{alg_4}, computing the optimal trajectory/control with a finer control set. The control set $\tilde{U}$ has now $100$ discrete controls. In Table \ref{test1:2contrcomp} we present the errors and the orders according to the definition \eqref{errors}.

	\begin{table}[htbp]
		\centering
		\begin{tabular}{cccccccc}
					\toprule
					 $\Delta t$ &  CPU & $Err_{2}$ &  $Err_{\infty} $ & $Order_{2}$  & $Order_{\infty}$  \\
					\midrule
					0.1       &  \phantom{x} 0.03s&    0.315 &   0.250 &   & \\
					0.05     	 &  \phantom{x}  0.07s &   9.6e-2 &  0.100 & 1.71 &   1.32 \\
					0.025   	 &  \phantom{x}0.74s & 2.5e-2 & 3.1e-2  &  1.93 &    1.68 \\
					0.0125  &  \phantom{x} 25s & 1.4e-2   &   9.0e-3 &  0.89 &   1.81  \\
			\bottomrule
		\end{tabular}
   	\caption{Test 1: Error analysis and order of convergence for TSA-POD method with $\varepsilon_{\mathcal{T}}= \Delta t^2$, $2$ POD basis and reconstruction with $100$ controls.}
	\label{test1:2contrcomp}
	\end{table}

Since we have constructed the tree with $3$ discrete controls, we can apply also the quadratic feedback reconstruction presented in Algorithm \ref{alg_5}. The results for this case are presented in Table \ref{test1:2contrpar}. It is possible to notice that the CPU time and the errors are similar. Tables \ref{test1:2contrcomp}-\ref{test1:2contrpar}  can be now compared with Table \ref{test41:11contr} in which we were solving the optimal control problem without introducing the feedback reconstruction technique. The numerical errors in both norms are comparable in the three cases studied, while in term of computational cost we can notice a speed-up of almost 3 orders.

In Figure \ref{fig3:cost11feed} we show the cost functional and the optimal control with all these techniques. In particular, it is possible to see from the plot of the optimal control that the quadratic feedback reconstruction is more stable, while the reconstruction by comparison presents a scattering behaviour.
	\begin{table}[htbp]
		\centering
		\begin{tabular}{cccccccc}
					\toprule
					 $\Delta t$  & CPU & $Err_{2}$ &  $Err_{\infty} $ & $Order_{2}$  & $Order_{\infty}$  \\
					\midrule
					0.1 &    \phantom{x} 0.02s&   0.251 &   0.229 &   & \\
					0.05 &     \phantom{x} 0.04s &   0.109 &  9.5e-2 &  1.21 &  1.27 \\
					0.025 &    \phantom{x} 0.63s & 3.3e-2 & 3.0e-2  &   1.71 &    1.65 \\
					0.0125 &     \phantom{x}24s & 1.1e-2 &   5.9e-3 & 1.58 &   2.36  \\
			\bottomrule
		\end{tabular}
   	\caption{Test 1: Error analysis and order of convergence for TSA-POD method with $\varepsilon_{\mathcal{T}}= \Delta t^2$, $2$ POD basis and quadratic reconstruction.}
	\label{test1:2contrpar}
	\end{table}

	\begin{figure}[htbp]
\centering
       \includegraphics[scale=0.45]{figures/POD/cost_feedback.eps}
       \includegraphics[scale=0.45]{figures/POD/control_feedback.eps}

       \caption{Test 1: Cost functional (left) and optimal control (right) with different techniques for the feedback reconstruction. }
       \label{fig3:cost11feed}
	\end{figure}

\section{Conclusions}

In this work we have presented two algorithms to reconstruct the control in feedback form based on a tree structure proposed in \cite{AFS18}. Given the knowledge of the value function on the nodes of the tree, it is possible to introduce interpolation operators on scattered data to obtain the synthesis of the feedback including more discrete controls. This technique has been coupled with a Model Order Reduction method to reduce the dimensionality of the problem, allowing a fast and accurate computation of the optimal control. In the present work we have restricted ourselves to low dimensional reconstructions. In the next future our aim is to extend this idea to more high dimensional general problem using e.g. kernel methods \cite{F15}.


\section{Introduction}
Deep neural networks designed for solving the object detection task, are commonly subdivided in a \textit{backbone} and a \textit{head}. The backbone is defined as taking in an image and outputting a set of feature maps. These feature maps are typically of different resolutions, with a factor two separating consecutive maps in width and height, hence forming what is known as a \textit{feature pyramid} \cite{lin2017feature}. A common choice for the backbone is using a ResNet-50 \cite{he2016deep} network in combination with a pyramid network (PN) such as FPN \cite{lin2017feature}, PANet \cite{liu2018path}, BiFPN \cite{tan2020efficientdet} or TPN \cite{picron2021trident}.

The object detection head is defined as taking in a set of feature maps from the backbone, and outputting object detection predictions, with each prediction consisting of an axis-aligned box together with a corresponding class label and confidence score. Object detection heads are commonly subdivided in \textit{one-stage} and \textit{two-stage} heads. One-stage heads make an object detection prediction for \textit{every feature} from its input set of feature maps. Two-stage heads first evaluate for every feature whether it is related to an object, and then use these results to \textit{focus the processing} on object-related parts of the feature maps.

In what follows, we exclusively work and compare with two-stage heads. Two-stage heads can further be subdivided in \textit{region-based} and \textit{query-based} two-stage heads, based on how the second stage of the two-stage head is implemented.

Region-based two-stage heads pool a rectangular grid of features from the backbone feature maps and further process these using convolutional neural networks (CNNs) in order to obtain their final object predictions. Region-based heads are found in many well-established two-stage object detectors such as Faster R-CNN \cite{ren2015faster} and Cascade R-CNN \cite{cai2018cascade}.

Query-based two-stage heads were recently introduced in the two-stage variant of Deformable DETR \cite{zhu2020deformable}. While region-based heads extract a \textit{grid of features} from the backbone feature maps per detection, only a \textit{single feature} called the query is selected in query-based heads. These queries are then further processed using operations commonly found in a transformer decoder \cite{vaswani2017attention}, namely cross-attention, self-attention, and feedforward operations. Here the cross-attention operation is defined between the backbone feature maps and each query, the self-attention operation is applied between the queries from different predictions, and the feedforward operations are performed on each query individually.

In this paper, we propose a new query-based two-stage head, called the FQDet (Fast-converging Query-based Detector) head. FQDet was obtained by combining the query-based paradigm from two-stage Deformable DETR \cite{zhu2020deformable} with classical object detection techniques such as anchor generation and static (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot non-Hungarian) matching.

When evaluated on the 2017 COCO object detection benchmark \cite{lin2014microsoft} after training for $12$ epochs, our FQDet head with ResNet-50+TPN backbone achieves $45.4$ AP, outperforming other high-performing two-stage heads such as Faster R-CNN \cite{ren2015faster}, Cascade R-CNN \cite{cai2018cascade}, two-stage Deformable DETR \cite{zhu2020deformable} and Sparse R-CNN \cite{sun2021sparse} when using the same backbone.

\section{Related work}

\paragraph{DETR and its variants.} With its unique way of approaching the object detection task, DETR \cite{carion2020end} quickly gained a lot of popularity. Since, many variants such as SMCA \cite{gao2021fast}, Conditional DETR \cite{meng2021conditional}, Deformable DETR \cite{zhu2020deformable}, Anchor DETR \cite{wang2022anchor}, DAB-DETR \cite{liu2022dab} and DN-DETR \cite{li2022dn} have been proposed to improve the main two shortcomings of DETR, namely its slow convergence speed and its poor performance on small objects. In doing so, Deformable DETR \cite{zhu2020deformable} introduces the query-based two-stage head, a new type of two-stage head now also used in other works such as DINO \cite{zhang2022dino}.

\paragraph{Anchors.} Our FQDet head differs from other query-based two-stage heads by introducing anchors within the query-based two-stage paradigm. Faster R-CNN \cite{ren2015faster} was one of the first works to use anchors. Anchors are axis-aligned boxes of different sizes and aspect ratios that are attached to backbone feature locations and are refined to yield the final bounding box predictions. Anchors are found in both one-stage detectors (SSD \cite{liu2016ssd}, YOLO \cite{redmon2016you}, RetinaNet \cite{lin2017focal}) and two-stage detectors (Faster R-CNN \cite{ren2015faster}, Cascade R-CNN \cite{cai2018cascade}). Over the years, many anchor-free detectors have also been proposed such as CornerNet \cite{law2018cornernet}, FCOS \cite{tian2019fcos}, CenterNet \cite{zhou2019objects}, FoveaBox \cite{kong2020foveabox}, DETR \cite{carion2020end} and Deformable DETR \cite{zhu2020deformable}.

\paragraph{Matching.} Our FQDet head additionally differs from other query-based two-stage heads by using a static top-k matching scheme as opposed to the dynamic Hungarian matching scheme. Matching is the process responsible of assigning ground-truth labels to the different model outputs during training. Most detectors have a \textit{static} matching scheme, meaning that the matching scheme stays the same throughout the whole training process. Static matching schemes are common when using anchors, where label assignment is done based on the IoU overlap between anchors and ground-truth boxes (\emph{e.g}\onedot} \def\Eg{\emph{E.g}\onedot Faster R-CNN \cite{ren2015faster}, RetinaNet \cite{lin2017focal} and Cascade R-CNN \cite{cai2018cascade}). Some works make use of a \textit{dynamic} matching scheme, meaning that the matching scheme changes as training progresses. In Dynamic R-CNN \cite{zhang2020dynamic}, the minimum IoU thresholds are increased throughout the training process. In DETR \cite{carion2020end}, a dynamic Hungarian matching scheme is used, matching every ground-truth to a single prediction (one-to-one matching). In OTA \cite{ge2021ota}, the one-to-one Hungarian matching scheme from DETR is extended to one-to-many Hungarian matching, where a single ground-truth could be assigned to multiple predictions.

\section{Method}

\subsection{Overview and motivation} \label{sec:overview_motiv}
\paragraph{Overview.} Below, we give an overview of the main improvements of our FQDet head over two-stage Deformable DETR (see Appendix~\ref{sec:revisit} for more information about DETR and Deformable DETR):
\begin{enumerate}
    \item We use multiple anchors of different sizes and aspect ratios \cite{lin2017focal}, improving the cross-attention prior.
    \item We encode the bounding boxes relative to these anchors, similar to Faster R-CNN \cite{ren2015faster}.
    \item We only use an L1 loss for bounding box regression \cite{ren2015faster} without GIoU loss \cite{rezatofighi2019generalized}.
    \item We remove the auxiliary decoder losses and predictions as used in DETR \cite{carion2020end}.
    \item We do not perform iterative bounding box regression as in Deformable DETR \cite{zhu2020deformable}.
    \item We replace Hungarian matching \cite{carion2020end, zhu2020deformable} with static top-k matching (\textit{ours}).
\end{enumerate}

\paragraph{Motivation.} In what follows, we motivate each of the above FQDet design choices. The impact of these design choices on the performance will be analyzed in the ablation studies of Subsection~\ref{sec:base_abl}.

\textit{(Item 1)} We first motivate the use of anchors in our FQDet head. To understand this, we must take a look at the cross-attention operation from Deformable DETR. This operation updates a query based on features sampled from the backbone feature maps, where the sample coordinates are regressed from the query itself. These sample coordinates are defined w.r.t\onedot} \def\dof{d.o.f\onedot to a reference frame based on the query box prior, where the origin of the reference frame is placed at the center of the box prior and where the unit lengths correspond to half the width and height of the box prior. By using anchors of various sizes and aspect ratios in our FQDet head, we significantly improve these cross-attention box priors resulting in more accurate and robust sampling, and eventually in better performance.

Items 2-5 from above list now in fact all follow from the use of anchors. \textit{(Item 2)} Given that we use anchors, it is logical to also encode our bounding box predictions relative to these anchors as \emph{e.g}\onedot} \def\Eg{\emph{E.g}\onedot done in Faster R-CNN \cite{ren2015faster}. \textit{(Item 3)} Since we encode our boxes relative to the anchors, we only use an L1 loss (without GIoU loss) for the bounding box regression, as commonly used for this box encoding \cite{ren2015faster}. \textit{(Item 4)} Since we improved our box priors with the introduction of anchors, there is no need to further improve these by introducing intermediate box predictions supervised by auxiliary losses as Deformable DETR \cite{zhu2020deformable}. In our setting, updating the box priors with these intermediate box predictions even hurts the performance, as a fixed sample reference frame for the different decoder layers is to be preferred over a changing one. \textit{(Item 5)} Given that we do not make intermediate box predictions, there is also no need for iterative bounding box regression as used in Deformable DETR \cite{zhu2020deformable}.

\textit{(Item 6)} Our final design choice involves replacing the Hungarian matching with our static top-k matching. At the beginning of training, Hungarian matching might assign a ground-truth detection to a query which sampled from a very different region compared to the location of the ground-truth detection. Hungarian matching hence produces many low-quality matches at the beginning of training, significantly slowing down convergence. Instead, we propose our static (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot non-Hungarian) top-k matching scheme consisting of matching each ground-truth detection with its top-k anchors. Queries corresponding to these anchors are then also automatically matched. This matching scheme guarantees that each matched query indeed did processing in the neighborhood of the matched ground-truth detection.

\subsection{FQDet in detail}
An architectural overview of our FQDet head is displayed in Figure~\ref{fig:FQDet}. The head consists of two stages: a first stage applied to all input features and a second stage applied only to those features (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot queries) selected from Stage~1. We now discuss both stages in more depth.

\begin{figure}
    \centering
    \includegraphics[scale=0.95]{images/dts.pdf}
    \caption{Architectural overview of our two-stage FQDet head. At its input, the head receives a set of features from the backbone, for which it is currently unknown whether they belong to an object or not (orange boxes). In Stage~1, a lightweight selector network is used to determine which features belong to an object (green boxes) and which do not (red boxes). Features predicted to belong to an object are selected for Stage~2 and are now called queries. In Stage~2, queries first pass through a lightweight transition network, before being processed by $L$ consecutive transformer decoder layers. The resulting queries (flashy green boxes) are then processed by the classification and bounding box regression networks to yield the object detection predictions.}
    \label{fig:FQDet}
    \vspace{-0.4cm}
\end{figure}

\paragraph{Stage 1.} In Stage~1, the goal of our FQDet head is to determine which input features belong to an object, such that these can be selected for Stage~2. At its input, the head receives a set of backbone feature maps in the form of a feature pyramid. To each of those backbone feature locations we attach anchors of various sizes and aspect ratios. A lightweight selector network is then applied to each backbone feature outputting a score for each feature-anchor combination, with top-scoring feature-anchor combinations selected for Stage~2. In Stage~2, the selected feature becomes the query and the corresponding anchor becomes the query box prior for the cross-attention operation.

A selection loss is used to learn which features-anchor combinations should be selected. The selection targets are determined by our static top-k matching scheme, where anchors with a top-k highest IoU with one of the ground-truth boxes receive a positive label and anchors with no top-k highest IoU with any ground-truth box receive a negative label.

\paragraph{Stage 2.} In Stage~2, the goal of our FQDet head is to make an object detection prediction for each of the queries selected from Stage~1. First, the queries are passed through a lightweight transition network. This transition network is meant to change the queries from the backbone feature space to the head feature space, as
both feature spaces might have a different size.

Once processed by the transition network, the queries are passed through $L$ consecutive transformer decoder layers. Each layer consists of a sequence of cross-attention, self-attention and a feedforward network (FFN). The \textit{cross-attention} operation updates each query by sampling features from the backbone feature maps using the multi-scale deformable attention (MSDA) operation from Deformable DETR \cite{zhu2020deformable}. The \textit{self-attention} operation updates each query through interaction with other queries using a standard multi-head attention (MHA) operation \cite{vaswani2017attention}. Finally, each query is also processed individually by a \textit{feedforward network} (FFN) which is a specific type of MLP \cite{vaswani2017attention}.

After the decoder layers, the queries are processed by the classification and bounding box regression networks yielding the object detection predictions. The classification network outputs a score for each of the classes within the dataset, along with a score for the non-object class. The bounding box regression network outputs the bounding box deltas w.r.t\onedot} \def\dof{d.o.f\onedot the anchor, using the same box encoding scheme as in Faster R-CNN \cite{ren2015faster}. Both classification and bounding box regression networks are implemented using lightweight MLPs.

We use the same static top-k matching scheme in Stage~2 as in Stage~1, except that we allow for a different $k$ in both stages.

\section{Experiments} \label{sec:experiments}
\subsection{Setup} \label{sec:setup}

\paragraph{Dataset.} We perform our experiments on the COCO detection dataset \cite{lin2014microsoft}, where we train on the 2017 COCO training set and evaluate on the 2017 COCO validation or test-dev set.

\paragraph{Implementation details.} Throughout our experiments, we use a ResNet-50+TPN backbone. For the ResNet-50 network \cite{he2016deep}, we use ImageNet \cite{deng2009imagenet} pretrained weights provided by TorchVision and freeze the stem, stage~1 and BatchNorm layers (see \cite{radosavovic2020designing} for the used terminology). For the TPN network \cite{picron2021trident}, we use the TPN configuration with $3$ TPN layers and $2$ bottleneck layers per self-processing operation. The TPN network outputs a feature pyramid containing five feature maps, ranging from $P_3$ to $P_7$, each having a feature size of $256$. Here, feature map $P_i$ is downscaled $i$ times with a factor $2$ in both width and height.

For the selector network of our FQDet head, we use one hidden layer and one output layer. The hidden layer consists of a bottleneck layer \cite{he2016deep} with the same settings as used in TPN \cite{picron2021trident}. The output layer is a linear projection layer projecting each feature to a selection score for each of the anchor types. We use $9$ anchor types of different size and aspect ratio as defined in RetinaNet \cite{lin2017focal}. For the selection loss, we use a sigmoid focal loss \cite{lin2017focal} with $\alpha=0.25$ and $\gamma=2.0$ as hyperparameters. The selection targets are determined using our static top-k matching scheme with $k = 5$.

The $300$ feature-anchor combinations (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot query and query prior boxes) with the highest score are selected for the second stage. The queries pass first through one of the $9$ transition networks, depending on their corresponding anchor type. Each of these transition networks consist of a linear projection layer with output feature size $256$, preceded by a LayerNorm and a ReLU activation layer.

The transformer decoder of the FQDet head consists of $6$ consecutive decoder layers, with each layer a sequence of cross-attention, self-attention and feedforward operations. Each of the operations updates the queries by using skip connections, with each residual branch starting with a LayerNorm layer.

The cross-attention operation is implemented by the multi-scale deformable attention (MSDA) operation from Deformable DETR \cite{zhu2020deformable}. We use $8$ MSDA attention heads and $4$ MSDA sampling points per head and feature pyramid level. For the self-attention operation, we use the multi-head attention operation (MHA) from \cite{vaswani2017attention} with $8$ attention heads. The feedforward network (FFN) is implemented as in \cite{vaswani2017attention} with a hidden feature size of $1024$, except that we remove the dropout layers.

Additionally, anchor encodings are added to the queries when passed to the residual branches of the cross-attention and self-attention operations. These anchor encodings could be interpreted as enhanced positional encodings containing an additional notion of width and height. The anchor encodings are learned from the anchor boxes written in (center location, width-height) format, using an MLP with one hidden layer.

For the FQDet classification and bounding box regression networks, we use in both cases an MLP with one hidden layer. The classification and bounding box ground-truth labels are obtained using our static top-k matching scheme with $k=15$. Unmatched queries receive the \textit{non-object} label. For the classification loss, we use a sigmoid focal loss \cite{lin2017focal} with the same hyperparameters as for the selection loss. We use an L1 loss for the bounding box regression in the delta box encoding space as done in Faster R-CNN \cite{ren2015faster}. We remove duplicate detections during inference by using non-maximum suppression (NMS) with an IoU threshold of $0.5$.

We train our models with the AdamW optimizer \cite{loshchilov2017decoupled} with weight decay $10^{-4}$. We use an initial learning rate of $10^{-5}$ for the backbone parameters and for the linear projection modules computing the MSDA sampling offsets. For the remaining model parameters, we use an initial learning rate of $10^{-4}$. Our results are obtained by using the 1x training schedule, consisting of $12$ training epochs with learning rate drops after the $9$th and $11$th epoch with a factor $0.1$. Our models are trained using our internal cluster on $2$ GPUs with batch size $2$ each, while using the same data augmentation scheme as in DETR \cite{carion2020end}.

\paragraph{Evaluation.} When evaluating a model (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot backbone with head), we will report both its object detection performance as well as its computational characteristics. For the object detection performance, we report the Average Precision (AP) metrics as provided by the COCO benchmark \cite{lin2014microsoft}. For the computational characteristics, we use following five metrics:

\begin{enumerate}
    \item The number of model parameters (Params).
    \item The number of training FPS (tFPS).
    \item The peak training memory utilization (tMem).
    \item The number of inference FPS (iFPS).
    \item The peak inference memory utilization (iMem).
\end{enumerate}

The FPS and memory metrics are obtained on a GeForce GTX 1660 Ti GPU by supplying the model with a batch of two $800 \times 800$ images, each containing $10$ ground-truth objects during training. The FPS metric should be interpreted as the number of times the GPU can process above input per second. Note that both forward and backward passes (with parameter update from the optimizer) are used to obtain the training characteristics.

\subsection{Base FQDet results and ablation studies} \label{sec:base_abl}
In Table~\ref{tab:FQDet_base}, we report the results of our base FQDet head (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot our FQDet head with the settings explained above). Our base FQDet head obtains $44.3$ AP after only $12$ epochs of training, outperforming the two-stage Deformable DETR head by $5.4$ AP (see Subsection~\ref{sec:comp}).

We now perform a series of ablation studies investigating to what extent each of the design choices as listed in Subsection~\ref{sec:overview_motiv}, contribute to the increased performance of FQDet.

\begin{table*}[t!]
    \centering
    \caption{Base FQDet results on the 2017 COCO validation set.}
    \resizebox{\columnwidth}{!}{
        \begin{tabular}{c c|c c c c c c|c c c c c}
            \toprule
            Head & Epochs & AP & AP$_{50}$ & AP$_{75}$ & AP$_S$ & AP$_M$ & AP$_L$ & Params & tFPS & tMem & iFPS & iMem \\ \midrule
            FQDet & $12$ & $44.3$ & $62.5$ & $47.8$ & $25.3$ & $48.3$ & $59.0$ & $42.6$ M & $1.6$ & $2.86$ GB & $4.8$ & $0.52$ GB \\
            \bottomrule
        \end{tabular}}
    \label{tab:FQDet_base}
\end{table*}

\begin{table*}[t!]
    \centering
    \caption{FQDet anchors ablation study on the 2017 COCO validation set.}
    \resizebox{\columnwidth}{!}{
        \begin{tabular}{c c c|c c c c c c|c c c c c}
            \toprule
            Head & Sizes & Ratios & AP & AP$_{50}$ & AP$_{75}$ & AP$_S$ & AP$_M$ & AP$_L$ & Params & tFPS & tMem & iFPS & iMem \\ \midrule
            FQDet & $1$ & $1$ & $40.6$ & $60.8$ & $42.4$ & $24.1$ & $44.6$ & $53.4$ & $42.0$ M & $1.7$ & $2.84$ GB & $5.0$ & $0.51$ GB \\
            FQDet & $3$ & $1$ & $42.9$ & $61.4$ & $46.2$ & $24.4$ & $47.3$ & $57.5$ & $42.2$ M & $1.7$ & $2.84$ GB & $5.0$ & $0.51$ GB \\
            FQDet & $1$ & $3$ & $43.1$ & $62.6$ & $46.1$ & $25.8$ & $46.8$ & $57.0$ & $42.2$ M & $1.7$ & $2.84$ GB & $5.0$ & $0.51$ GB \\
            FQDet & $3$ & $3$ & $44.3$ & $62.5$ & $47.8$ & $25.3$ & $48.3$ & $59.0$ & $42.6$ M & $1.6$ & $2.86$ GB & $4.8$ & $0.52$ GB \\
            \bottomrule
        \end{tabular}}
    \label{tab:anchors}
\end{table*}

\paragraph{Anchors ablation study.} In the anchors ablation study, we vary the number of anchor types used in the FQDet selector. In our base FQDet head, we use $9$ anchor types composed of $3$ anchor sizes and $3$ anchor aspect ratios. In Table~\ref{tab:anchors}, we show the FQDet results when the number of anchor sizes and/or the number of anchor aspect ratios is reduced to $1$. We can see that the number of anchor types play an important role in the resulting performance, with a performance drop up to $3.7$ AP when only one anchor type is used. Moreover, we observe that the additional computational cost of using multiple anchor types is very limited. These results support our analysis from Subsection~\ref{sec:overview_motiv} where we highlight the importance of having good query box priors (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot anchors) for the cross-attention operation.

\begin{table*}[t!]
    \centering
    \caption{FQDet box loss ablation study on the 2017 COCO validation set.}
    \resizebox{\columnwidth}{!}{
        \begin{tabular}{c c c|c c c c c c|c c c c c}
            \toprule
            Head & L1 & GIoU & AP & AP$_{50}$ & AP$_{75}$ & AP$_S$ & AP$_M$ & AP$_L$ & Params & tFPS & tMem & iFPS & iMem \\ \midrule
            FQDet & \ding{51} & \ding{51} & $43.0$ & $60.3$ & $46.2$ & $23.5$ & $46.9$ & $58.1$ & $42.6$ M & $1.6$ & $2.86$ GB & $4.8$ & $0.52$ GB \\
            FQDet & \ding{51} & \ding{55} & $44.3$ & $62.5$ & $47.8$ & $25.3$ & $48.3$ & $59.0$ & $42.6$ M & $1.6$ & $2.86$ GB & $4.8$ & $0.52$ GB \\
            \bottomrule
        \end{tabular}}
    \label{tab:box_loss}
\end{table*}

\paragraph{Box loss ablation study.} In the box loss ablation study, we compare the L1 bounding box loss used by our base FQDet head, with a weighted combination of L1 and GIoU losses as used in DETR \cite{carion2020end} and Deformable DETR \cite{zhu2020deformable}. Note that for the weighted combination of L1 and GIoU losses, we also change the classification weight from $1.0$ to $2.0$, in order to be consistent with Deformable DETR. The results of the box loss ablation study are found in Table~\ref{tab:box_loss}. We can see that using a simple L1 box loss outperforms the weighted combination of L1 and GIoU losses by $1.3$ AP. As argued in Subsection~\ref{sec:overview_motiv}, we believe an L1 loss suffices when encoding the bounding boxes relative to anchors as done in FQDet.

\begin{table*}[t!]
    \centering
    \caption{FQDet auxiliary losses ablation study on the 2017 COCO validation set.}
    \resizebox{\columnwidth}{!}{
        \begin{tabular}{c c c|c c c c c c|c c c c c}
            \toprule
            Head & Aux. & Shared & AP & AP$_{50}$ & AP$_{75}$ & AP$_S$ & AP$_M$ & AP$_L$ & Params & tFPS & tMem & iFPS & iMem \\ \midrule
            FQDet & \ding{51} & \ding{51} & $44.1$ & $62.4$ & $47.5$ & $25.2$ & $48.0$ & $59.3$ & $42.6$ M & $1.5$ & $2.88$ GB & $4.5$ & $0.52$ GB \\
            FQDet & \ding{51} & \ding{55} & $43.7$ & $62.1$ & $46.7$ & $25.3$ & $47.6$ & $58.4$ & $43.5$ M & $1.5$ & $2.89$ GB & $4.5$ & $0.52$ GB \\
            FQDet & \ding{55} & $-$ & $44.3$ & $62.5$ & $47.8$ & $25.3$ & $48.3$ & $59.0$ & $42.6$ M & $1.6$ & $2.86$ GB & $4.8$ & $0.52$ GB \\
            \bottomrule
        \end{tabular}}
    \label{tab:aux}
\end{table*}

\paragraph{Auxiliary losses ablation study.} In the auxiliary losses ablation study, we investigate whether making intermediate predictions after each decoder layer supervised by auxiliary losses as in Deformable DETR \cite{zhu2020deformable}, improves the performance of our base FQDet head. In Table~\ref{tab:aux}, we show the performance of our FQDet head where auxiliary losses are added, both with and without shared classification and bounding box regression networks. We observe that the performance decreases between $0.2$ and $0.6$ AP, depending on whether the regression networks are shared or not. We argue that as our FQDet head already provides good box priors through its Stage~1 anchors for the Stage~2 decoder, there is no need to further improve these through intermediate box predictions supervised by auxiliary losses.

\begin{table*}[t!]
    \centering
    \caption{FQDet IBBR ablation study on the 2017 COCO validation set.}
    \resizebox{\columnwidth}{!}{
        \begin{tabular}{c c c c|c c c c c c|c c c c c}
            \toprule
            Head & Aux. & IBBR & Shared & AP & AP$_{50}$ & AP$_{75}$ & AP$_S$ & AP$_M$ & AP$_L$ & Params & tFPS & tMem & iFPS & iMem \\ \midrule
            FQDet & \ding{51} & \ding{51} & \ding{51} & $43.5$ & $62.0$ & $46.5$ & $24.7$ & $47.6$ & $58.1$ & $42.6$ M & $1.5$ & $2.89$ GB & $4.4$ & $0.52$ GB \\
            FQDet & \ding{51} & \ding{51} & \ding{55} & $43.8$ & $62.2$ & $46.7$ & $24.7$ & $47.7$ & $58.8$ & $43.5$ M & $1.5$ & $2.90$ GB & $4.4$ & $0.52$ GB \\
            FQDet & \ding{55} & \ding{55} & $-$ & $44.3$ & $62.5$ & $47.8$ & $25.3$ & $48.3$ & $59.0$ & $42.6$ M & $1.6$ & $2.86$ GB & $4.8$ & $0.52$ GB \\
            \bottomrule
        \end{tabular}}
    \label{tab:ibbr}
\end{table*}

\paragraph{IBBR ablation study.} In the iterative bounding box regression (IBBR) ablation study, we again investigate the setting with intermediate predictions supervised by auxiliary losses as in previous ablation study, except that we also do iterative bounding box regression (IBBR) as introduced in Deformable DETR \cite{zhu2020deformable}. IBBR consists in iteratively updating the bounding box predictions relative to the previous bounding box predictions (or anchors). The results of our IBBR ablation study are found in Table~\ref{tab:ibbr}, where we again consider the cases with and without shared classification and bounding box regression networks. We can see that the performance again decreases compared to our base FQDet head, this time between $0.5$ and $0.8$ AP depending on whether the regression networks were shared or not. Hence even when adding IBBR to the setting of intermediate predictions supervised by auxiliary losses, does not yield improvements for our FQDet head.

\begin{table*}[t!]
    \centering
    \caption{FQDet matching ablation study on the 2017 COCO validation set.}
    \resizebox{\columnwidth}{!}{
        \begin{tabular}{c c|c c c c c c|c c c c c}
            \toprule
            Head & Matching & AP & AP$_{50}$ & AP$_{75}$ & AP$_S$ & AP$_M$ & AP$_L$ & Params & tFPS & tMem & iFPS & iMem \\ \midrule
            FQDet & Hungarian & $35.1$ & $54.2$ & $37.5$ & $20.3$ & $38.5$ & $43.8$ & $42.6$ M & $1.5$ & $2.86$ GB & $4.8$ & $0.52$ GB \\
            FQDet & Absolute & $43.3$ & $61.0$ & $46.8$ & $25.5$ & $47.4$ & $57.6$ & $42.6$ M & $1.7$ & $2.86$ GB & $4.8$ & $0.52$ GB \\
            FQDet & Top-k (\textit{ours}) & $44.3$ & $62.5$ & $47.8$ & $25.3$ & $48.3$ & $59.0$ & $42.6$ M & $1.6$ & $2.86$ GB & $4.8$ & $0.52$ GB \\
            \bottomrule
        \end{tabular}}
    \label{tab:matching}
\end{table*}

\paragraph{Matching ablation study.} In the matching ablation study, we compare our static top-k matching scheme, with the static absolute matching scheme from Faster R-CNN \cite{ren2015faster} and the Hungarian matching scheme from Deformable DETR \cite{zhu2020deformable} (Stage~2 only). In Table~\ref{tab:matching}, we show the results when using our FQDet head with each of these three matching schemes. We can see that our top-k matching scheme works best, outperforming the absolute matching scheme with $1.0$ AP and the Hungarian scheme with $9.2$ AP. These 12-epoch results nicely support the analysis from Subsection~\ref{sec:overview_motiv}, where we argue that Hungarian matching leads to slow convergence due to the low-quality matches at the beginning of training.

\begin{table*}[t!]
    \centering
    \caption{Improving the base FQDet head by changing the number of MSDA sampling points, altering the inference strategy and training longer (evaluated on 2017 COCO validation set).}
    \vspace{0.1cm}
    \resizebox{\columnwidth}{!}{
        \begin{tabular}{c c c c|c c c c c c|c c c c c}
            \toprule
            Head & Points & Inference & Epochs & AP & AP$_{50}$ & AP$_{75}$ & AP$_S$ & AP$_M$ & AP$_L$ & Params & tFPS & tMem & iFPS & iMem \\ \midrule
            FQDet & $4$ & Old & $12$ & $44.3$ & $62.5$ & $47.8$ & $25.3$ & $48.3$ & $59.0$ & $42.6$ M & $1.6$ & $2.86$ GB & $4.8$ & $0.52$ GB \\
            FQDet & $1$ & Old & $12$ & $44.5$ & $62.9$ & $47.7$ & $26.1$ & $48.7$ & $59.3$ & $42.0$ M & $1.7$ & $2.84$ GB & $5.0$ & $0.51$ GB \\
            FQDet & $1$ & New & $12$ & $45.4$ & $64.3$ & $48.9$ & $27.4$ & $49.6$ & $60.3$ & $42.0$ M & $1.7$ & $2.84$ GB & $5.0$ & $0.51$ GB \\
            FQDet & $1$ & New & $24$ & $46.2$ & $65.3$ & $49.2$ & $29.1$ & $50.3$ & $61.0$ & $42.0$ M & $1.7$ & $2.84$ GB & $5.0$ & $0.51$ GB \\
            \bottomrule
        \end{tabular}}
    \label{tab:improvements}
\end{table*}

\subsection{Improving the base FQDet head} \label{sec:improving}
In what follows, we make following three improvements to the base FQDet head. The results after applying each of those improvements sequentially, are shown in Table~\ref{tab:improvements}.

\paragraph{MSDA sampling points improvement.} The first improvement consists in changing the number of MSDA sampling points per head and per feature pyramid level from $4$ to $1$, increasing the performance by $0.2$ AP while being computationally cheaper.

\paragraph{Inference strategy improvement.} The second improvement consists in altering the inference strategy. In the current inference strategy, we only assign a single classification label to each predicted bounding box, \emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot the label with the highest score. This is sub-optimal as the head might be hesitant about the class, with multiple classes containing similar scores. In the new inference strategy, we therefore consider all classification labels with their scores for each predicted bounding box, and feed these to the NMS algorithm to only keep the top $100$ predictions. Replacing the old inference strategy with the new one improves the performance by $0.9$ AP, while leaving the computational cost virtually unchanged.

\paragraph{Training longer.} The performance of our FQDet head can further be improved by training for $24$ epochs using the 2x schedule, increasing the performance by $0.8$ AP.

\begin{table*}[t!]
    \centering
    \caption{Comparison of our FQDet head with other prominent two-stage heads on the 2017 COCO validation set.}
    \vspace{0.1cm}
    \resizebox{\columnwidth}{!}{
        \begin{tabular}{c c|c c c c c c|c c c c c}
            \toprule
            Head & Epochs & AP & AP$_{50}$ & AP$_{75}$ & AP$_S$ & AP$_M$ & AP$_L$ & Params & tFPS & tMem & iFPS & iMem \\ \midrule
            Faster R-CNN & $12$ & $40.7$ & $60.9$ & $44.4$ & $23.9$ & $46.0$ & $54.1$ & $50.3$ M & $1.8$ & $2.62$ GB & $4.0$ & $0.55$ GB \\
            Cascade R-CNN & $12$ & $43.9$ & $61.9$ & $47.6$ & $25.8$ & $49.3$ & $58.5$ & $77.9$ M & $1.4$ & $3.15$ GB & $2.5$ & $0.65$ GB \\
            Deformable DETR & $12$ & $38.9$ & $58.1$ & $41.6$ & $23.6$ & $41.7$ & $52.3$ & $43.0$ M & $1.6$ & $3.02$ GB & $4.9$ & $0.52$ GB \\
            Sparse R-CNN & $12$ & $39.8$ & $57.4$ & $43.1$ & $23.8$ & $42.5$ & $53.4$ & $114.8$ M & $1.3$ & $4.67$ GB & $4.0$ & $0.79$ GB \\
            \midrule
            FQDet (ours) & $12$ & $\mathbf{45.4}$ & $\mathbf{64.3}$ & $\mathbf{48.9}$ & $\mathbf{27.4}$ & $\mathbf{49.6}$ & $\mathbf{60.3}$ & $42.0$ M & $1.7$ & $2.84$ GB & $5.0$ & $0.51$ GB \\
            \bottomrule
        \end{tabular}}
    \label{tab:comparison}
\end{table*}

\subsection{Comparison with other two-stage heads} \label{sec:comp}
In Table~\ref{tab:comparison}, we compare our improved FQDet head from Subsection~\ref{sec:improving} with other prominent two-stage heads from the literature. We compare with the two-stage heads from Faster R-CNN \cite{ren2015faster}, Cascade R-CNN \cite{cai2018cascade}, Deformable DETR \cite{zhu2020deformable} and Sparse R-CNN \cite{sun2021sparse}, while using the same ResNet-50+TPN backbone and training settings. We used their MMDetection implementations \cite{mmdetection} where we adapted the config files to be compatible with the $P_3$ to $P_7$ feature pyramid outputted by the backbone.

From Table~\ref{tab:comparison}, we see the clear superiority of our FQDet head. Our FQDet head outperforms all other two-stage heads with $1.5$ up to $6.5$ AP, not only outperforming the query-based two-stage Deformable DETR head, but also well-established region-based heads such as Cascade R-CNN. Additionally, our FQDet head is considerably cheaper compared to most of the heads, only being slightly more expensive during training than the Faster R-CNN head.

In Figure~\ref{fig:two-stage-comp}, we show two convergence graphs containing our FQDet two-stage head and other prominent two-stage heads using their MMDetection \cite{mmdetection} implementation. Here the left convergence graph displays the COCO validation AP after every training epoch, whereas the right convergence graph shows the COCO validation AP after each unit of normalized time, with this unit of time defined as the time it takes to train our FQDet head for one epoch.

When looking at the left convergence graph, we can see that our FQDet head performs better throughout the whole training process, highlighting its fast convergence. Only the Cascade R-CNN head trails by a small amount. It takes however substantially more time for the Cascade R-CNN head to complete one epoch compared to our FQDet head. When taking the actual training time into account in the right convergence graph, we can now see that our FQDet performs better compared to the Cascade R-CNN at any point in time during the training process. Our FQDet hence demonstrates excellent performance achieved in few training epochs, while remaining relatively cheap.

\begin{figure}
    \centering
    \begin{minipage}{0.49\textwidth}
        \centering
        \includegraphics[scale=0.42]{images/two-stage.png}
    \end{minipage} \hfill
    \begin{minipage}{0.49\textwidth}
        \centering
        \includegraphics[scale=0.42]{images/two-stage_norm.png}
    \end{minipage}
    \caption{(\textit{Left}) Convergence graph displaying the COCO validation AP after every training epoch for different two-stage heads. (\textit{Right}) Convergence graph displaying the COCO validation AP as a function of normalized training time. Here one unit of normalized training time is defined as the time it takes to train our FQDet head for one epoch.}
    \label{fig:two-stage-comp}
    \vspace{-0.4cm}
\end{figure}

\subsection{Comparison with state-of-the-art methods}
In this subsection, we compare our FQDet detector with other state-of-the-art object detection methods, when using the ResNeXt-101-64$\times$4d-DCN backbone \cite{xie2017aggregated, dai2017deformable, zhu2019deformable}. To further boost performance, we make following modifications: 1) we consider a $P_2$ to $P_7$ feature pyramid, 2) we replace convolutions with modulated deformable convolutions \cite{zhu2019deformable} in TPN, 3) we use group convolutions \cite{xie2017aggregated} with $32$ groups in TPN, and 4) we consider the $(L, B) = (3, 4)$ TPN configuration \cite{picron2021trident}. Our test-time augmentation (TTA) scheme consists of horizontal flipping and multi-scale testing with the shorter edges of images rescaled to $[500, 600, 700, 800, 900, 1000, 1100, 1200, 1300]$.

\begin{table*}[t!]
    \centering
    \caption{Comparison of FQDet with state-of-the-art object detection methods on the 2017 COCO test-dev set. All methods use the ResNeXt-101-64$\times$4d-DCN backbone. The `TTA' column indicates whether test-time augmentations such as horizontal flipping and multi-scale testing are used.}
    \vspace{0.1cm}
    \resizebox{0.85\columnwidth}{!}{
        \setlength{\tabcolsep}{7pt}
        \begin{tabular}{c c c|c c c c c c}
            \toprule
            Method & Epochs & TTA & AP & AP$_{50}$ & AP$_{75}$ & AP$_S$ & AP$_M$ & AP$_L$ \\ \midrule
            ATSS \cite{zhang2020bridging} & $24$ & \ding{55} & $47.7$ & $66.5$ & $51.9$ & $29.7$ & $50.8$ & $59.4$ \\
            Sparse R-CNN \cite{sun2021sparse} & $36$ & \ding{55} & $48.9$ & $68.3$ & $53.4$ & $29.9$ & $50.9$ & $62.4$ \\
            Deformable DETR \cite{zhu2020deformable} & $50$ & \ding{55} & $50.1$ & $69.7$ & $54.6$ & $30.6$ & $52.8$ & $64.7$ \\
            TOOD \cite{feng2021tood} & $24$ & \ding{55} & $51.1$ & $69.4$ & $55.5$ & $31.9$ & $54.1$ & $63.7$ \\
            RelationNet++ \cite{chi2020relationnet++} & $24$ & \ding{55} & $50.3$ & $69.0$ & $55.0$ & $32.8$ & $55.0$ & $65.8$ \\
            DyHead \cite{dai2021dynamic} & $24$ & \ding{55} & $52.3$ & $70.7$ & $57.2$ & $35.1$ & $56.2$ & $63.4$ \\
            \textbf{FQDet} (ours) & $12$ & \ding{55} & $51.5$ & $70.3$ & $55.7$ & $31.9$ & $54.5$ & $65.5$ \\
            \midrule
            ATSS \cite{zhang2020bridging} & $24$ & \ding{51} & $50.7$ & $68.9$ & $56.3$ & $33.2$ & $52.9$ & $62.4$ \\
            Sparse R-CNN \cite{sun2021sparse} & $36$ & \ding{51} & $51.5$ & $71.1$ & $57.1$ & $34.2$ & $53.4$ & $64.1$ \\
            Deformable DETR \cite{zhu2020deformable} & $50$ & \ding{51} & $52.3$ & $71.9$ & $58.1$ & $34.4$ & $54.4$ & $65.6$ \\
            RelationNet++ \cite{chi2020relationnet++} & $24$ & \ding{51} & $52.7$ & $70.4$ & $58.3$ & $35.8$ & $55.3$ & $64.7$ \\
            DyHead \cite{dai2021dynamic} & $24$ & \ding{51} & $\mathbf{54.0}$ & $72.1$ & $\mathbf{59.3}$ & $\mathbf{37.1}$ & $\mathbf{57.2}$ & $\mathbf{66.3}$ \\
            \textbf{FQDet} (ours) & $12$ & \ding{51} & $52.9$ & $\mathbf{72.3}$ & $57.2$ & $34.6$ & $55.8$ & $\mathbf{66.3}$ \\
            \bottomrule
        \end{tabular}}
    \label{tab:sota}
\end{table*}

In Table~\ref{tab:sota}, we compare our FQDet object detector with other state-of-the-art detectors, all using the ResNeXt-101-64$\times$4d-DCN backbone. We can see that our FQDet detector outperforms all other detectors, both with and without test-time augmentations, except for the DyHead detector \cite{dai2021dynamic}.

\subsection{Limitations} \label{sec:limitations}
Only a single dataset (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot COCO \cite{lin2014microsoft}) was used to evaluate our method. Experiments were only run a single time as running experiments multiple times would be too computationally expensive.

\subsection{Potential negative societal impacts} \label{sec:impact}
Object detection models could be used in military applications to \emph{e.g}\onedot} \def\Eg{\emph{E.g}\onedot identify human targets and could be used for mass surveillance.

\section{Conclusion}
We propose the FQDet head, a new query-based two-stage object detection head combining the best of both classical and DETR-based detectors. Our FQDet head improves the cross-attention prior with anchors and introduces the effective top-k matching scheme. We perform various ablation studies validating the FQDet design choices and show improvements w.r.t\onedot} \def\dof{d.o.f\onedot existing two-stage heads when compared on the COCO object detection benchmark after training for $12$ epochs.

\section*{Acknowledgements}
This work was supported by the Ford-KU Leuven alliance program.