text:
\section*{Appendix}

\input{files/6-appendix}

\end{document}

\section{Conclusion}
In this work, we have presented an alternative
perspective for semantic segmentation by introducing a {\em sequence-to-sequence} prediction framework.
In contrast to existing FCN based methods that enlarge the receptive field typically with dilated convolutions and attention modules at the {\em component} level,
we made a step change at the {\em architectural} level to completely eliminate the reliance on FCN and elegantly solve the limited receptive field challenge.
We implemented the proposed idea with Transformers
that can model global context at every stage of feature learning.
Along with a set of decoder designs in different complexity, strong segmentation models are established
with none of the bells and whistles deployed by recent methods.
Extensive experiments demonstrate that our models set new state of the art on ADE20, Pascal Context and competitive results on Cityscapes.
Encouragingly, our method is ranked the $1^{st}$ place in the highly competitive ADE20K test server leaderboard on the day of submission.

\section*{Acknowledgments}
This work was supported by Shanghai Municipal Science and Technology Major Project (No.2018SHZDZX01),
ZJLab,
and Shanghai Center for Brain Science and Brain-Inspired Technology.

\section{Introduction}

Since the seminal work of \cite{fcn}, existing semantic segmentation models have been dominated by those based on fully convolutional network (FCN).
A standard FCN segmentation model has an encoder-decoder architecture:
the {\em encoder} is for feature representation learning, while
the {\em decoder} for pixel-level classification of the feature representations
yielded by the encoder.
Among the two,  feature representation learning (\textit{i.e.}, the encoder)
is arguably the most important model component \cite{chen2018deeplab,pspnet,zhang2020dynamic,li2020improving}.
The encoder, like most other CNNs designed for image understanding, consists of stacked convolution layers. Due to concerns on computational cost, the resolution of feature maps is reduced progressively, and the encoder is hence able to learn more abstract/semantic visual concepts with a gradually increased receptive field. Such a design is popular due to
two favorable merits,
namely translation equivariance and locality.
The former respects well the nature of imaging process
\cite{zhang2019making} which underpins the model generalization
ability to unseen image data.
Whereas the latter controls the model complexity
by sharing parameters across space. However,
it also raises a fundamental limitation
that learning {long-range dependency information}, critical for semantic segmentation in unconstrained scene images \cite{segnet,denseaspp},
becomes challenging due to still limited receptive fields.

To overcome this aforementioned limitation,  a number of approaches have been introduced recently.
One approach is to directly manipulate the convolution operation. This includes
large kernel sizes \cite{largekernel},
atrous convolutions \cite{holschneider1990real,chen2018deeplab},
and image/feature pyramids \cite{pspnet}.
The other approach is to integrate attention modules into the FCN architecture. Such a module aims to model {\em global} interactions of all pixels in the feature map \cite{wang2018nonlocal}.
When applied to
semantic segmentation \cite{huang2018ccnet,li2019global}, a common design is to combine the attention module to the FCN architecture with attention layers sitting on the top.
Taking either approach, the standard encoder-decoder FCN model architecture remains unchanged. More recently, attempts have been made to get rid of convolutions altogether and deploy attention-alone models \cite{wang2020axial} instead. However, even without convolution, they do not change the nature of the FCN model structure: an encoder downsamples the spatial resolution of the input, developing lower-resolution feature mappings useful for discriminating semantic classes, and the decoder upsamples the feature representations into a full-resolution segmentation map.

In this paper, we aim to provide a rethinking to the semantic segmentation model design and contribute an alternative. In particular, we propose to replace the stacked convolution layers based encoder with gradually reduced spatial resolution with a pure transformer \cite{vaswani2017attention}, resulting in a new segmentation model termed {\em SEgmentation TRansformer} (SETR). This transformer-alone encoder treats an input image as a sequence of {\em image patches} represented by learned patch embedding, and transforms the sequence with global self-attention modeling for discriminative feature representation learning. Concretely, we first decompose an image into a grid
of fixed-sized patches, forming a sequence of patches.
With a linear embedding layer applied to the
flattened pixel vectors of every patch, we then obtain a
sequence of feature embedding vectors
as the input to a transformer. Given the learned features from the encoder transformer,
a decoder is then used
to recover the original image resolution.
Crucially there is {\em no} downsampling in spatial resolution but global context modeling at every layer of the encoder transformer, thus offering a completely new perspective to the semantic segmentation problem.

This pure transformer design is inspired by its tremendous success in natural language processing (NLP)~\cite{vaswani2017attention,Devlin2018}.
More recently, a pure vision transformer or ViT \cite{dosovitskiy2020image} has shown to be effective for image classification tasks.  It thus provides direct evidence that the traditional stacked convolution layer (\textit{i.e.}, CNN) design can be challenged and image features do not necessarily need to be learned progressively from local to global context by reducing spatial resolution. However, extending a pure transformer
from image classification to a spatial location sensitive task of semantic segmentation is non-trivial. We show empirically that SETR not only offers a new perspective in model design, but also achieves new state of the art on a number of benchmarks.

The following {\bf contributions} are made in this paper:
(1) We reformulate the image semantic segmentation problem
from a {\em sequence-to-sequence} learning perspective, offering an alternative to the dominating encoder-decoder FCN model design.
(2) As an instantiation, we exploit the transformer framework
to implement our fully attentive feature representation encoder
by sequentializing images.
(3) To extensively examine the self-attentive feature presentations,
we further introduce three different decoder designs
with varying complexities.
Extensive experiments show that our SETR models can
learn superior feature representations as compared to
different FCNs with and without attention modules, yielding
new state of the art on ADE20K (50.28\%), Pascal Context (55.83\%) and competitive results on Cityscapes.
Particularly, our entry is ranked the $1^{st}$ place in the highly competitive ADE20K test server leaderboard.
\section{Experiments}
\label{sec:exp}
\input{table/model_variant}
\input{table/setting}
\input{table/ablation_camera}

\subsection{Experimental setup}
We conduct experiments on three widely-used semantic segmentation benchmark datasets.

\paragraph{Cityscapes}\cite{Cityscapes}
densely annotates 19 object categories in images with urban scenes.
It contains 5000 finely annotated images, split into 2975, ~500 and 1525 for training, validation and testing respectively.
The images are all captured at a high resolution of $2048 \times 1024$.
In addition, it provides 19,998 coarse annotated images for model training.

\paragraph{ADE20K}\cite{ADE20K}
is a challenging scene parsing benchmark with 150 fine-grained semantic concepts.
It contains 20210, ~2000 and 3352 images for training, validation and testing.

\paragraph{PASCAL Context}\cite{mottaghi_cvpr14}
provides pixel-wise semantic labels for the whole scene
(both "thing" and "stuff" classes), and contains 4998 and 5105 images for training and validation respectively.
Following previous works, we evaluate on the most frequent 59 classes and the background class (60 classes in total).

\input{table/pretrain}

\paragraph{Implementation details}
Following the default setting (\textit{e.g.},~data augmentation and training schedule) of public codebase {\em mmsegmentation} \cite{mmsegmentation},
(i) we apply random resize with ratio between 0.5 and 2, random cropping (768,~512 and 480 for Cityscapes, ADE20K and Pascal Context respectively) and random horizontal flipping during training for all the experiments;
(ii) We set batch size 16 and the total iteration to 160,000 and 80,000 for the experiments on ADE20K and Pascal Context.
For Cityscapes, we set batch size to 8 with a number of training schedules reported in Table~\ref{tab:ablation},~\ref{tab:city_val} and~\ref{tab:citytest} for fair comparison.
We adopt a polynomial learning rate decay schedule~\cite{pspnet} and employ SGD as the optimizer.
Momentum and weight decay are set to 0.9 and 0 respectively for all the experiments on the three datasets.
We set initial learning rate 0.001 on ADE20K and Pascal Context, and 0.01 on Cityscapes.

\paragraph{Auxiliary loss}
As~\cite{pspnet} we also find the auxiliary segmentation loss helps the model training.
Each auxiliary loss head follows a 2-layer network.
We add auxiliary losses at different Transformer layers:
SETR-\textit{Na\"ive}~($Z^{10}, Z^{15}, Z^{20}$),
SETR-\textit{PUP}~($Z^{10}, Z^{15}, Z^{20}, Z^{24}$),
SETR-\textit{MLA}~($Z^6, Z^{12}, Z^{18}, Z^{24}$).
Both auxiliary loss and main loss heads are applied
concurrently.

\input{figure/visual_ade20k}
\input{table/ade20k}
\paragraph{Multi-scale test}
We use the default settings of {\em mmsegmentation} \cite{mmsegmentation}.
Specifically, the input image is first scaled to a uniform size.
Multi-scale scaling and random horizontal flip are then performed on the image with a scaling factor (0.5, 0.75, 1.0, 1.25, 1.5, 1.75).
Sliding window is adopted for test (\textit{e.g.}, $480 \times 480$ for Pascal Context).
If the shorter side is smaller than the size of the sliding window, the image is scaled with its shorter side to the size of the sliding window (\textit{e.g.}, 480) while keeping the aspect ratio.
Synchronized BN is used in decoder and auxiliary loss heads.
For training simplicity, we do not adopt the widely-used tricks such as OHEM~\cite{ocnet} loss in model training.

\paragraph{Baselines}
We adopt dilated FCN~\cite{fcn} and Semantic FPN~\cite{kirillov2019panoptic} as baselines with their results taken from \cite{mmsegmentation}.
Our models and the baselines are trained and tested in the same settings for fair comparison.
In addition, state-of-the-art models are also compared.
Note that the dilated FCN is with output stride 8 and we use output stride 16 in all our models due to GPU memory constrain.

\paragraph{SETR variants}

Three variants of our model with different decoder designs (see Sec.~\ref{sec:decoder}), namely SETR-\textit{Na\"ive}, SETR-\textit{PUP}~  and SETR-\textit{MLA}.
Besides,
we use two variants of the encoder ``T-Base'' and ``T-Large'' with 12 and 24 layers respectively (Table~\ref{tab:config}).
Unless otherwise specified, we use ``T-Large'' as the encoder for SETR-\textit{Na\"ive}, SETR-\textit{PUP}~and SETR-\textit{MLA}.
We denote SETR-\textit{Na\"ive-Base}~as the model utilizing ``T-Base'' in SETR-\textit{Na\"ive}.

Though designed as a model with a pure transformer encoder, we also set a hybrid baseline \textit{Hybrid} ~by using a ResNet-50 based FCN encoder and feeding its output feature into SETR.
To cope with the GPU memory constraint and for fair comparison, we only consider `T-Base'' in \textit{Hybrid}~and set the output stride of FCN to $1/16$.
That is, \textit{Hybrid}~ is a combination of ResNet-50 and SETR-\textit{Na\"ive-Base}.

\input{figure/visual_pascal_context}
\input{table/pascal-context}

\paragraph{Pre-training}
We use the pre-trained weights provided by ViT~\cite{dosovitskiy2020image} or DeiT~\cite{touvron2020training}
to initialize all the transformer layers and the input linear projection layer in our model.
We denote~SETR-\textit{Na\"ive-DeiT}~as the model utilizing DeiT~\cite{touvron2020training} pre-training in SETR-\textit{Na\"ive-Base}.
All the layers without pre-training are randomly initialized.
For the FCN encoder of \textit{Hybrid}, we use the initial weights pre-trained on ImageNet-1k.
For the transformer part, we use the weights pre-trained by ViT~\cite{dosovitskiy2020image}, DeiT~\cite{touvron2020training} or randomly initialized.

\input{figure/visual_cityscapes}
\input{table/cityscape_val}

We use patch size $16\times16$ for all the experiments. We perform 2D interpolation on the pre-trained position embeddings, according to their location in the original image for different input size fine-tuning.

\paragraph{Evaluation metric}
Following the standard evaluation protocol~\cite{Cityscapes}, the metric of mean Intersection over Union (mIoU) averaged over all classes is reported.
For ADE20K, additionally pixel-wise accuracy is reported following the existing practice.

\subsection{Ablation studies}

Table~\ref{tab:ablation} and~\ref{tab:pretrain} show ablation studies on
{\bf(a)} different variants of SETR~on various training schedules,
{\bf(b)} comparison to FCN~\cite{mmsegmentation} and Semantic FPN~\cite{mmsegmentation},
{\bf(c)} pre-training on different data,
{\bf(d)} comparison with \textit{Hybrid},
{\bf(e)} compare to FCN with different pre-training.
Unless otherwise specified, all experiments on Table~\ref{tab:ablation} and~\ref{tab:pretrain} are trained on Cityscapes train fine set with batch size 8, and evaluated using the single scale test protocol on the Cityscapes validation set in mean IoU (\%) rate.
Experiments on ADE20K also follow the single scale test protocol.
\input{table/cityscape_test}

From Table~\ref{tab:ablation}, we can make the following observations:
{\bf(i)} Progressively upsampling the feature maps, SETR-\textit{PUP}~achieves the best performance among all the variants on Cityscapes.
One possible reason for inferior performance of SETR-\textit{MLA}~is that the feature outputs of different transformer layers do not have the benefits of resolution pyramid as in feature pyramid network (FPN) (see Figure~\ref{fig:layer}).
However, SETR-\textit{MLA}~performs slightly better than SETR-\textit{PUP}, and much superior to the variant SETR-\textit{Na\"ive}~that upsamples the transformers output feature by 16$\times$ in one-shot, on ADE20K val set (Table~\ref{tab:pretrain} and~\ref{tab:ade}).
{\bf(ii)} The variants using ``T-Large'' (\textit{e.g.},~SETR-\textit{MLA}~and SETR-\textit{Na\"ive}) are superior to their ``T-Base'' counterparts, \textit{i.e.}, SETR-\textit{MLA-Base}~and SETR-\textit{Na\"ive-Base}, as expected.
{\bf(iii)}
While our SETR-\textit{PUP-Base}~(76.71) performs worse than \textit{Hybrid-Base}~(76.76), it shines (78.02) when training with more iterations (80k).
It suggests that FCN encoder design can be replaced in semantic segmentation, and further confirms the effectiveness of our model.
{\bf(iv)} Pre-training is critical for our model.
Randomly initialized~SETR-\textit{PUP}~only gives 42.27\% mIoU on Cityscapes.
Model pre-trained with DeiT~\cite{touvron2020training} on ImageNet-1K gives the best performance on Cityscapes, slightly better than the counterpart pre-trained with ViT~\cite{dosovitskiy2020image} on ImageNet-21K.
{\bf(v)}
To study the power of pre-training and further verify the effectiveness of our proposed approach, we conduct the ablation study on the pre-training strategy in Table~\ref{tab:pretrain}.
For fair comparison with the FCN baseline,
we first pre-train a ResNet-101 on the Imagenet-21k dataset with a classification task and then adopt the pre-trained weights for a dilated FCN training for the semantic segmentation task on ADE20K or Cityscapes.
Table~\ref{tab:pretrain} shows that with ImageNet-21k pre-training FCN baseline experienced a clear improvement over the variant pre-trained on ImageNet-1k.
However, our method outperforms the FCN counterparts by a large margin, verifying that the advantage of our approach largely comes from the proposed \textit{sequence-to-sequence} modeling strategy rather than bigger pre-training data.

\input{figure/visual_layer}

\subsection{Comparison to state-of-the-art }

\paragraph{Results on ADE20K}
Table~\ref{tab:ade} presents our results on the more challenging ADE20K dataset.
Our SETR-\textit{MLA}~achieves superior mIoU of 48.64\% with single-scale (SS) inference.
When multi-scale inference is adopted, our method achieves a new state of the art with mIoU hitting 50.28\%.
Figure~\ref{fig:ade} shows the qualitative results of our model and dilated FCN on ADE20K.
When training a single model on the train+validation set with the default 160,000 iterations, our method ranks $1^{st}$
place in the highly competitive ADE20K test server leaderboard.

\input{figure/visual_attention}

\paragraph{Results on Pascal Context}
Table~\ref{tab:pascal} compares the segmentation results on Pascal Context.
Dilated FCN with the ResNet-101 backbone achieves a mIoU of 45.74\%.
Using the same training schedule, our proposed SETR significantly outperforms this baseline, achieving mIoU of 54.40\% (SETR-\textit{PUP}) and 54.87\% (SETR-\textit{MLA}).
SETR-\textit{MLA}~further improves the performance to 55.83\% when multi-scale (MS) inference is adopted, outperforming the nearest rival APCNet with a clear margin.
Figure~\ref{fig:pascal} gives some qualitative results
of SETR and dilated FCN.
Further visualization of the learned attention maps in Figure~\ref{fig:attention} shows that SETR~can attend to semantically meaningful foreground regions, demonstrating its ability to learn discriminative feature representations useful for segmentation.

\paragraph{Results on Cityscapes}
Tables~\ref{tab:city_val} and~\ref{tab:citytest} show the comparative results on the validation and test set of  Cityscapes respectively.
We can see that our model SETR-\textit{PUP}~is superior to FCN baselines, and FCN plus attention based approaches, such as Non-local~\cite{wang2018nonlocal} and CCNet~\cite{huang2018ccnet}; and its performance is on par with the best results reported so far.
On this dataset we can now compare with the closely related Axial-DeepLab~\cite{cheng2020panoptic,wang2020axial} which aims to use an attention-alone model but still follows the basic structure of FCN.
Note that Axial-DeepLab sets the same output stride 16 as ours.
However, its full input  resolution ($1024 \times 2048$) is much larger than our crop size $768 \times 768$, and it runs more epochs (60k iteration with batch size 32) than our setting (80k iterations with batch size 8).
Nevertheless, our model is still superior to Axial-DeepLab
when multi-scale inference is adopted on Cityscapes validation set.
Using the fine set only, our model (trained with 100k iterations) outperforms Axial-DeepLab-XL with a clear margin on the test set.
Figure~\ref{fig:city} shows the qualitative results of our model and dilated FCN on Cityscapes.
\section{Method}

\subsection{FCN-based semantic segmentation}
In order to contrast with our new model design, let us first revisit the conventional FCN \cite{fcn} for image semantic segmentation. An FCN encoder consists of a stack of sequentially connected convolutional layers. The first layer takes as input the image, denoted as $H \times W \times 3$ with
 $H \times W $ specifying the image size in pixels.
The input of subsequent layer $i$ is a three-dimensional tensor sized $h \times w \times d$, where $h$ and $w$ are spatial dimensions of feature maps, and $d$ is the feature/channel dimension.
Locations of the tensor in a higher layer are computed based on the locations of tensors of all lower layers they are connected to via layer-by-layer convolutions, which are defined as their {\em receptive fields}.
Due to the locality nature of convolution operation, the receptive field increases linearly along the depth of layers, conditional on the kernel sizes (typically $3 \times 3$).
As a result, only higher layers with big receptive fields can model long-range dependencies
in this FCN architecture.
However, it is shown that the benefits of adding more layers
would diminish rapidly once reaching certain depths \cite{resnet}. Having limited receptive fields for context modeling is thus an intrinsic limitation of the vanilla FCN architecture.

Recently, a number of state-of-the-art methods \cite{zhang2019dual,huang2018ccnet,zhang2020dynamic}
suggest that combing FCN with attention mechanism is a more effective strategy for learning long-range
contextual information.
These methods limit the attention learning
to higher layers with smaller input sizes alone due to its quadratic complexity
\wrt the pixel number of feature tensors.
This means that dependency learning on lower-level feature tensors is lacking, leading to sub-optimal representation learning.
To overcome this limitation, we propose a pure self-attention based encoder, named {\em SEgmentation TRansformers} (SETR).

\subsection{Segmentation transformers (SETR)}
\paragraph{Image to sequence}
SETR~follows the same input-output structure as in NLP for transformation between 1D sequences. There thus exists a mismatch between 2D image and 1D sequence.
Concretely, the Transformer, as depicted in  Figure~\ref{fig:SETR_transformer}(a), accepts a 1D sequence of feature embeddings $Z \in \mathbb{R}^{L\times C}$ as input, $L$ is the length of sequence, $C$ is the hidden channel size. Image sequentialization is thus needed to convert an input image $x\in \mathbb{R}^{H\times W\times 3}$ into $Z$.

A straightforward way for image sequentialization is
to flatten the image pixel values into a 1D vector with size of $3HW$.
For a typical image sized at $480 (H)\times480(W)\times3$,
the resulting vector will have a length of 691,200.
Given the quadratic model complexity of Transformer,
it is not possible that such high-dimensional vectors
can be handled in
both space and time.
Therefore tokenizing every single pixel as input to our transformer is out of the question.

In view of the fact that a typical encoder designed for semantic segmentation would downsample a 2D image $x\in \mathbb{R}^{H\times W\times 3}$ into a feature map $x_f\in \mathbb{R}^{\frac{H}{16}\times \frac{W}{16}\times C}$, we  thus decide to set the transformer input sequence length $L$ as $\frac{H}{16} \times \frac{W}{16} = \frac{HW}{256}$.
This way, the output sequence of the transformer can be simply reshaped to the target feature map $x_f$.

To obtain the $\frac{HW}{256}$-long input sequence, we divide an image $x\in \mathbb{R}^{H\times W\times 3}$ into a grid of $\frac{H}{16}\times\frac{W}{16}$ patches uniformly,
and then flatten this grid into a sequence.
By further mapping each vectorized patch $p$ into a latent $C$-dimensional embedding space
using a linear projection function $f$:
$p \longrightarrow e \in \mathbb{R}^C$,
we obtain a 1D sequence of patch embeddings
for an image $x$.
To encode the patch spacial information,
we learn a specific embedding $p_i$ for every location $i$
which is added to $e_i$ to form the final sequence input $E = \{e_1+p_1,~e_2+p_2,~\cdots,~e_L+p_L\}$. This way, spatial information is kept despite the orderless self-attention nature of transformers.

\paragraph{Transformer}
Given the 1D embedding sequence $E$ as input,
a pure transformer based encoder is employed to learn feature representations. This means each transformer layer has a global
 receptive field, solving the limited receptive field problem of existing FCN encoder once and for all.
The transformer encoder consists of $L_e$ layers of multi-head
self-attention (MSA) and Multilayer Perceptron (MLP) blocks \cite{velivckovic2017graph}
(Figure \ref{fig:SETR_transformer}(a)).
At each layer $l$, the input to self-attention is in a triplet of
(\texttt{query}, \texttt{key}, \texttt{value})
computed from the input $Z^{l-1} \in \mathbb{R}^{L\times C}$ as:
\begin{align}\footnotesize
    \text{query} = {Z^{l-1}} \textbf{W}_Q, \;
    \text{key} = {Z^{l-1}} \textbf{W}_K, \;
    \text{value} = {Z^{l-1}} \textbf{W}_V,
\end{align}
where $\textbf{W}_Q$/$\textbf{W}_K$/$\textbf{W}_V  \in \mathbb{R}^{C\times d}$
are the learnable parameters of three linear projection layers
and $d$ is the dimension of (\texttt{query}, \texttt{key}, \texttt{value}).
Self-attention (SA) is then formulated as:
\begin{equation}\footnotesize
    SA(Z^{l-1}) = Z^{l-1} +
    \operatorname{softmax}(\frac{Z^{l-1} \textbf{W}_Q (Z \textbf{W}_K)^\top}{\sqrt{d}}) (Z^{l-1} \textbf{W}_V).
    \label{eq:attn}
\end{equation}
MSA is an extension with $m$ independent SA operations
and project their concatenated outputs:
$MSA(Z^{l-1}) = [SA_1(Z^{l-1});~SA_2(Z^{l-1}); ~\cdots;~SA_m(Z^{l-1})]\textbf{W}_O$, where $\textbf{W}_O \in \mathbb{R}^{md \times C} $. $d$ is typically set to $C/m$.
The output of MSA is then transformed
by an MLP block with residual skip as the layer output as:
\begin{equation}\footnotesize
    Z^l = MSA(Z^{l-1}) + MLP(MSA(Z^{l-1})) \in \mathbb{R}^{L \times C}.
\end{equation}
Note, layer norm is applied before MSA and MLP blocks
which is omitted for simplicity.
We denote $\{Z^1,~Z^2,~\cdots,~Z^{L_e}\}$ as the features of transformer layers.

\subsection{Decoder designs}
\label{sec:decoder}
To evaluate the effectiveness of SETR's encoder feature representations $Z$, we introduce three different decoder designs to perform pixel-level segmentation.
As the goal of the decoder is to generate the segmentation results in the original 2D image space $(H \times W)$, we need to reshape the encoder's features (that are used in the decoder),
$Z$, from a 2D shape of $\frac{HW}{256} \times C$
to a standard 3D feature map $\frac{H}{16} \times \frac{W}{16} \times C$. Next, we briefly describe the three decoders.

\paragraph{(1) Naive upsampling (Naive)}
This naive decoder
first projects the transformer feature $Z^{L_e}$ to the dimension of category number (\textit{e.g.}, 19 for experiments on Cityscapes).
For this we adopt a simple 2-layer network with architecture:
$1 \times 1$ conv + sync batch norm (w/ ReLU) + $1 \times 1$ conv.
After that, we
simply bilinearly upsample the output to the full image resolution,
followed by a classification layer with pixel-wise cross-entropy loss.
When this decoder is used,
we denote our model as SETR-\textit{Na\"ive}.

\paragraph{(2) Progressive UPsampling (PUP)}
Instead of one-step upscaling which may introduce  noisy
predictions, we consider a {\em progressive upsampling} strategy
that alternates conv layers and upsampling operations.
To maximally mitigate the adversarial effect,
we restrict upsampling to 2$\times$.
Hence, a total of 4 operations are needed for reaching
the full resolution from $Z^{L_e}$ with size $\frac{H}{16} \times \frac{W}{16}$.
More details of this process are given in Figure \ref{fig:SETR_transformer}(b).
When using this decoder,
we denote our model as SETR-\textit{PUP}.

\paragraph{(3) Multi-Level feature Aggregation (MLA)}

The third design is characterized by multi-level feature aggregation (Figure \ref{fig:SETR_transformer}(c))
in similar spirit of feature pyramid network \cite{fpn,kirillov2019panoptic}.
However, our decoder is  fundamentally different
because the feature representations $Z^l$ of every SETR's layer share the same resolution without a pyramid shape.

Specifically, we take as input the feature representations
$\{ Z^m\}$ ($m \in \{{\frac{L_e}{M}}, {2\frac{L_e}{M}}, \cdots, {M\frac{L_e}{M}} \}$)
from $M$ layers uniformly distributed across the layers with step $\frac{L_e}{M}$ to the decoder.
$M$ streams are then deployed, with each focusing on one specific
selected layer.
In each stream,
we first reshape the encoder's feature
$Z^{l}$ from a 2D shape of $\frac{HW}{256} \times C$
to a 3D feature map $\frac{H}{16} \times \frac{W}{16} \times C$.
A 3-layer (kernel size $1\times 1$, $3\times 3$, and $3 \times 3$) network is applied with the feature channels
halved at the first and third layers respectively,
and the spatial resolution upscaled $4\times$ by bilinear operation
after the third layer.
To enhance the interactions across different streams, we introduce a top-down aggregation design via element-wise addition after the first layer.
An additional $3 \times 3$ conv is applied after the element-wise additioned feature.
After the third layer, we obtain the fused feature from all the streams via channel-wise concatenation which is then bilinearly upsampled $4\times$ to the full resolution.
When using this decoder, we denote our model as SETR-\textit{MLA}.

\section{Related work}

\input{figure/sketch_transformer}

\paragraph{Semantic segmentation}
Semantic image segmentation has been significantly boosted with the development of deep neural networks. By removing  fully connected layers, the fully convolutional network (FCN)~\cite{fcn} is able to achieve pixel-wise predictions. While the predictions of FCN are relatively coarse, several CRF/MRF~\cite{chen2015semantic,liu2015semantic,zheng2015conditional} based approaches are developed to help refine the coarse predictions. To address the inherent tension between semantics and location~\cite{fcn}, coarse and fine layers need to be aggregated for both the encoder and decoder. This leads to different variants of the encoder-decoder structures~\cite{unet,deconvnet,segnet} for multi-level feature fusion.

Many recent  efforts have been focused on addressing the limited receptive field/context modeling problem in FCN.  To enlarge the receptive field, DeepLab~\cite{deeplabv1} and Dilation~\cite{dilation} introduce the dilated convolution. Alternatively, context modeling is the focus of PSPNet~\cite{pspnet} and DeepLabV2~\cite{deeplabv2}. The former proposes the PPM module to obtain different region's contextual information while the latter develops ASPP module that adopts pyramid dilated convolutions with different dilation rates. Decomposed large kernels~\cite{largekernel} are also utilized for context capturing.
Recently, attention based models are popular for capturing long range context information. PSANet~\cite{psanet} develops the pointwise spatial attention module for dynamically capturing the long range context. DANet~\cite{DAnet} embeds both spatial attention and channel attention. CCNet~\cite{huang2019ccnet} alternatively focuses on economizing the heavy computation budget introduced by full spatial attention. DGMN~\cite{zhang2020dynamic} builds a dynamic graph message passing network for scene modeling and it can significantly reduce the computational complexity. Note that all these approaches are still based on FCNs where the feature encoding and extraction part are based on classical ConvNets like VGG~\cite{vgg} and ResNet~\cite{resnet}. In this work, we alternatively rethink the semantic segmentation task from a different perspective.

\paragraph{Transformer}
Transformer and self-attention models have revolutionized  machine translation and NLP~\cite{vaswani2017attention,Devlin2018,dai2019transformer,Yang2019xlnet}. Recently, there are also some explorations for the usage of transformer structures in image recognition. Non-local network~\cite{wang2018nonlocal} appends transformer style attention onto the convolutional backbone. AANet~\cite{bello2019attention} mixes convolution and self-attention for backbone training. LRNet~\cite{hu2019local} and stand-alone networks~\cite{ramachandran2019stand} explore local self-attention to avoid the heavy computation brought by global self-attention. SAN~\cite{zhao2020san} explores two types of self-attention modules. Axial-Attention~\cite{wang2020axial} decomposes the global spatial attention into two separate axial attentions such that the computation is largely reduced. Apart from these pure transformer based models, there are also CNN-transformer hybrid ones. DETR~\cite{carion2020end} and the following deformable version utilize transformer for object detection where transformer is appended inside the detection head. STTR~\cite{li2020revisiting} and LSTR~\cite{liu2020lane} adopt transformer for disparity estimation and lane shape prediction respectively.  Most recently, ViT~\cite{dosovitskiy2020image} is the first work to show that a pure transformer based image classification model can achieve the state-of-the-art. It provides direct inspiration to exploit a pure transformer based encoder design in a semantic segmentation model.

The most related work is \cite{wang2020axial} which  also leverages attention for image segmentation. However, there are several key differences. First, though convolution is completely removed in \cite{wang2020axial} as in our SETR, their model still follows the conventional FCN design in that spatial resolution of feature maps is reduced progressively. In contrast, our sequence-to-sequence prediction model keeps the same spatial resolution throughout and thus represents a step-change in model design.
Second, to maximize the scalability on modern hardware accelerators and facilitate easy-to-use, we stick to the standard self-attention design. Instead, \cite{wang2020axial} adopts a specially designed axial-attention  \cite{ho2019axial} which is less scalable to standard computing facilities. Our model is also superior in segmentation accuracy (see Section~\ref{sec:exp}).
\section{Visualizations}

\paragraph{Position embedding}
Visualization of the learned position embedding in Figure~\ref{fig:pos} shows that the model learns to encode distance within the image in the similarity of position embeddings.

\paragraph{Features}

Figure~\ref{fig:layer-pup} shows the feature visualization of our SETR-\textit{PUP}.
For the encoder, 24 output features from the 24 transformer layers namely $Z^1-Z^{24}$ are collected. Meanwhile, 5 features ($U^1-U^5$) right after each bilinear interpolation in the decoder head are visited.

\paragraph{Attention maps}

Attention maps (Figure~\ref{fig:attention-50}) in each transformer layer catch our interest.
There are 16 heads and 24 layers in T-large.
Similar to \cite{abnar2020quantifying}, a recursion perspective into this problem is applied.
Figure~\ref{fig:ori-gt-att} shows the attention maps of different selected spatial points (red).

\input{figure/visual_position_embed_80}
\input{figure/ori-gt-att}

\input{figure/visual_layer-pup}
\input{figure/visual_attention_50}


text:
\section{How to Use this Template}

\section{Introduction}

The recently proposed classification of Shapovalov wave spacetimes \cite{Osetrin2020Symmetry} provides additional mathematical tools for constructing exact integrable models of gravitational waves, including primordial gravitational waves in Bianchi universes \cite{Lukash1976268,Osetrin202289
}
and other exact models of plane gravitational waves
\cite
Osetrin2020410,Osetrin2020403}.
Current advances in gravitational wave astronomy in detecting gravitational waves and the resulting astrophysical information
\cite{PhysRevLett.116.061102,PhysRevX.9.031040,PhysRevX.11.021053} increased interest in the mathematical aspects of gravitational wave research as well.

The relevance of these lines of research is also related to the importance of the discovery of primordial gravitational waves for constructing a theory of the early universe and possible confirmation of the stage of inflation predicted by some theories.
Interest in the study of gravitational waves is also due to possible secondary physical effects in a gravitational wave, such as the formation of black holes \cite{Saito200916,Saito2010867}, the capture of astrophysical objects by a gravitational wave
\cite{Bialynicki-Birula2018}, gravitational wave lensing and other effects.

The Shapovalov wave spacetimes allow the presence of special symmetries of the Hamilton-Jacobi equation, leading to the existence of privileged coordinate systems, where the equations of motion of test particles and the eikonal equation for radiation in the Hamilton-Jacobi formalism allow exact integration by the method of separation of variables. Moreover, among the separable variables on which the space-time metric depends (non-ignored variables),
there are wave variables along which the space-time interval vanishes. Gravitational wave velocity according to gravitational wave detection data from neutron star mergers \cite{Abbott2017PRL161101}
equal to the velocity of light. Therefore, the existence of the possibility of separating null variables indicates the wave nature of such spacetime models, and the use of wave variables in describing gravitational waves is experimentally justified.

Shapovalov wave spaces in the four-dimensional case include three main types according to the number of commuting Killing vectors they allow and, accordingly, in privileged coordinate systems, the number of Killing vectors determines the number of non-ignorable variables on which the space-time metric depends. For privileged coordinate systems, Vladimir Shapovalov obtained the structure of the space metric \cite{Shapovalov1978I,Shapovalov1978II,Shapovalov1979}, which leads to the separation of variables in the Hamilton-Jacobi equation, which allows one to construct exact integrable models of gravitational waves in various theories of gravity, where test particles move along geodesic curves of spacetime.

There is currently interest in studying the properties of modified theories of gravity, which could give corrections to Einstein's theory of gravity in the early stages of the universe (quantum corrections, quadratic theories and
$f(R)$-theories of gravity, theories with a scalar field, etc.) and could offer theoretical description of the phenomena of ''inflation'', ''dark matter'' and ''dark energy''
\cite{Odintsov2007115,Odintsov201159,Odintsov2017104,Osetrin2021092501}.
Therefore, the use of additional mathematical tools for the comparative analysis of exact models of gravitational waves in various theories of gravity also makes it possible to select the most realistic theories and models.

In this direction, one of the first models of modified theories of this kind was the Brans-Dicke scalar-tensor theory of gravity \cite{Brans1961925}. Scalar-tensor theories have firmly taken their place in theoretical research on gravity and cosmology \cite{Novikov2014352}, which is determined by attempts to use an additional scalar field to describe various possible scenarios for the dynamics of the universe and other theoretical constructions
\cite{Odintsov2022729,Odintsov2022100950,Odintsov2022136817,Capozziello2021100867}.

In this paper, Shapovalov wave spaces of type I are considered in the scalar-tensor theory of gravity of Brans-Dicke. An additional scalar field in theory complicates the field equations, but also provides additional possibilities. The resulting equation for a scalar field of the type of the Klein-Gordon equation also requires additional study. As Shapovalov \cite{Shapovalov1978I,Shapovalov1978II} showed, the scalar equation can be integrated by separation of variables in the same privileged coordinate systems as the Hamilton-Jacobi equation. Therefore, the use of Shapovalov wave spaces also provides additional possibilities for the exact solution of the scalar equation \cite{Osetrin20181383,Osetrin20202050275,Osetrin20202050184, Osetrin20211173}. Recently, in the study of the symmetries of the {Klein}-{Gordon}-{Fock} equations, new results have also been obtained
\cite{Obukhov2021727,Obukhov202113201320,Obukhov2022346,Obukhov2022023505}.

Type I Shapovalov metrics are the most general gravitational-wave models of Shapovalov spacetimes, since they depend on three variables in the privileged coordinate system, including the wave variable. Note that metrics of this type when using Einstein's vacuum equations lead to degeneration, since the number of non-ignorable variables in the metric decreases when solving vacuum field equations and the space becomes either a type II wave Shapovalov space with two non-ignorable variables in the metric, or a type III space with one wave variable in metric. Preservation of type I metrics is possible if there are additional fields and matter in the models under consideration. Therefore, the existence of non-degenerate Shapovalov models of type I in the Brans-Dicke theory of gravity and the possibility of detecting such gravitational waves in observations would be additional evidence in favor of scalar-tensor theories of gravity.

The authors investigate exact wave models of spacetime to find out the differences that may arise in these gravitational wave models for Einstein's theory and for modified theories of gravity. Type I Shapovalov wave spaces have internal symmetries that relate them to mathematical models of gravitational waves, but, nevertheless, these models of gravitational waves do not lead to the appearance of exact solutions for Einstein's vacuum equations, in contrast to type II and III models. And in the modified Brans-Dicke theory of gravity, exact wave solutions for given spaces, as we show below, arise. This makes it possible to obtain observational differences in the detection of gravitational waves by existing and future detectors. This is also significant in the analysis of stochastic gravitational wave noise detected by existing gravitational wave detectors. In addition, primordial gravitational waves of this type could leave an imprint on the cosmic microwave background. Finding "traces" of such gravitational waves would argue for greater realism in scalar-tensor gravity theories than Einstein's theory. The possibility of exact integration of the equations of motion of test particles and the geodesic deviation equations in these models of gravitational waves allows gravitational wave detectors to more efficiently analyze and select such disturbances in signals with high noise.

 \section{
 Gravitational-wave spacetimes of Shapovalov
 }

Shapovalov wave spaces allow exact integration of the equations of motion of test particles in the Hamilton-Jacobi formalism
\begin{equation}
g^{\alpha\beta}\frac{\partial S}{\partial x^\alpha}\frac{\partial S}{\partial x^\beta}=m^2c^2
,\qquad
\alpha,\beta,\gamma=0,1,2,3.
\label{HJE}
\end{equation}
with the separation of non-ignorable wave variables (the space metric depends on these variables), along which the space-time interval vanishes \cite{Osetrin2020Symmetry}.
Here $S$ is the action function of the test particle, $m$ is the mass of the particle, $c$ is the speed of light. Let us choose a system of units in the future, where the speed of light is equal to unity.

Type I Shapovalov spacetimes admit one Killing vector, which is included in the so-called ''complete set'' of vectors and Killing tensors of the second rank, which determine integrals of motion linear and quadratic in momenta. In a privileged coordinate system, where the equation (\ref{HJE}) allows complete separation of variables, the type I Shapovalov space-time metric depends on three variables, including the null wave variable, which will be denoted by $x^0$. Another null variable $x^1$ is ignored (cyclic) and is not included in the metric.

Let us consider a model with a type I Shapovalov wave space metric, which in a privileged coordinate system can be written in the following form:
\begin{equation}
g^{\alpha\beta}=\frac{1}{f_0}
\left(
\begin{array}{cccc}
0&1&0&0\\
1&0&0&0\\
0&0&\frac{1}{W}&0\\
0&0&0&\frac{1}{W}
\end{array}
\right)
\label{metric1}
,\end{equation}
where
\begin{equation}
f_0=f_0(x^0),\ \ \ \  W(x^2,x^3)=t_3(x^3)-t_2(x^2)
.\end{equation}

The scalar curvature ${R}$  takes the following form
\begin{equation}
{R}(x^0,x^2,x^3) =
\frac{{f_0}
}{({t_2} - {t_3})^3}
\Bigl(
({t_2} - {t_3}) \left({t_2}'' - {t_3}''\right)-{{t_2}'}^2-{{t_3}'}^2
\Bigr)
,
\end{equation}
where the top prime means the ordinary derivative with respect to the variable on which the function depends.

The nonzero components of the Riemann curvature tensor have the following form:
\begin{equation}
{R}_{0202} = {R}_{0303} =\frac{\left({f_0}'{}^2-2 {f_0}{} {f_0}''\right) ({t_2} - {t_3})}{4 {f_0}{}^3}
,\end{equation}
\begin{equation}
{R}_{2323} = \frac{({t_2} - {t_3}) \left({t_2}'' - {t_3}''\right)-{t_2}'{}^2-{t_3}'{}^2}{2 {f_0}{} ({t_2} - {t_3})}
\label{riman}
.\end{equation}
In addition, all nonzero components of the Weyl conformal curvature tensor $C_{\alpha\beta\gamma\delta}$ are proportional to the scalar curvature $R$
and when the scalar curvature vanishes, they also vanish, which leads to a conformally flat spacetime.

Note that the ability to exactly integrate the Hamilton-Jacobi equations for Shapovalov wave spaces allows one to obtain the trajectories of test particles, as well as to find exact solutions to the geodesic deviation equation and the exact form of tidal accelerations in these spaces. These possibilities make it possible to determine all physical effects in gravitational waves.

\section{
Brans-Dicke scalar-tensor theory of gravity
}

The Lagrange function for the Brans-Dicke theory of gravity (BDT) can be written in the following form \cite{Novikov2014352}:
 \begin{equation}
L=\phi\, (R+2\Lambda)-\frac{\omega}{\phi}\, g^{\alpha\beta}\partial_{\alpha}\phi\partial_{\beta}\phi+16\pi\kappa L_{matter}
,
\end{equation}
where $\phi$ is a scalar field, $\omega$ is a constant parameter of the theory, $\Lambda$ is a cosmological constant.

Field equations of the Brans-Dicke scalar-tensor gravity theory with cosmological constant
$\Lambda$ can be written as follows:
\begin{equation}
G_{\alpha\beta}=
\frac{8\pi}\Phi T_{\alpha\beta}+\Lambda g_{\alpha\beta}+\frac{\omega}{\Phi^2}(\Phi_{,\alpha}\Phi_{,\beta}-\frac 12 g_{\alpha\beta}g^{\gamma\delta}\Phi_{,\gamma}\Phi_{,\delta})+
	\frac 1\Phi(\Phi_{;{\alpha\beta}}-g_{\alpha\beta} \Phi^{;\gamma}{}_{;\gamma})
\label{EqBD}
,\end{equation}
\begin{equation}
\frac{3+2\omega}\Phi \,\Phi^{;\gamma}{}_{;\gamma}
=
\frac{8\pi}\Phi T^\gamma{}_\gamma+2\Lambda
\label{EqScalar}
.\end{equation}
Here, the comma denotes the ordinary partial derivative, and the semicolon denotes the covariant derivative.

To obtain exact gravitational wave solutions, consider the vacuum model
$T_{\alpha\beta}=0$. It is convenient to pass to the form of the scalar field $\Phi=e^\phi$, then the BDT equations will take the following more compact form:
\begin{equation}
G_{\alpha\beta}+g_{\alpha\beta}(\phi^{;\gamma}{}_{;\gamma}+(1+\omega/2)\phi^{,\gamma}\phi_{,\gamma}-\Lambda)-\phi_{;{\alpha\beta}}-(\omega+1)\phi_{,\alpha}\phi_{,\beta}=0
,\label{tbd}
\end{equation}
\begin{equation}
(\omega+3/2)(\phi^{;\gamma}{}_{;\gamma}+\phi^{,\gamma}\phi_{,\gamma})-\Lambda=0
.\label{trac}
\end{equation}
Note that the higher derivatives of the scalar field $\phi$ can be found from the equations (\ref{tbd}) and substituted into the scalar equation (\ref{trac}) to reduce the order of this equation.

The equations of the scalar-tensor theory of gravity of Brans-Dicke for the considered metric lead to the following form of field equations:
\begin{equation} \phi_{,00}=\frac{f_0{}'}{f_0}\phi_{,0}+\frac 32\frac{{f_0{}'}^2}{f_0{}^2}-(\omega+1)\phi_{,0}{}^2+\frac{f_0{}''}{f_0},\end{equation}
\begin{equation} \phi_{,01}=(\omega+1)\left(\frac{2\Lambda f_0}{3+2\omega}-\phi_{,0}\phi_{,1}\right),\end{equation}
\begin{equation} \phi_{,11}=-(\omega+1)\phi_{,1}{}^2,\end{equation}
\begin{equation} \phi_{,1\mu}=-(\omega+1)\phi_{,1}\phi_{,\mu},
\qquad \mu,\nu=2,3,\end{equation}
\begin{equation} \phi_{,0\mu}=\phi_{,\mu}\left(\frac 12\frac{f_0{}'}{f_0}-(\omega+1)\phi_{,0}\right),\end{equation}
$$
\phi_{,\mu\mu}=W\left(\frac 13(R+\Lambda)f_0-\frac 12\frac{f_0{}'}{f_0}\phi_{,1}+\frac 13\omega\phi_{,0}\phi_{,1}\right)-\frac{5\omega+6}6{\phi_{,2}}^2
$$
\begin{equation}
\mbox{}
+\omega
  {\phi_{,3}}^2-(-1)^{\mu}\frac{\phi_{,2}t_2{}'+\phi_{,3}t_3{}'}{2W},\end{equation}
\begin{equation} \phi_{,23}=\frac{\phi_{,2}t_3{}'+\phi_{,3}t_2{}'}{2W}-(\omega+1)\phi_{,2}\phi_{,3},\end{equation}
\begin{equation}
W((2\omega+3)R+2(4\omega+3)\Lambda)f_0=\omega(2\omega+3)(2W\phi_{,0}\phi_{,1}+{\phi_{,2}}^2+{\phi_{,3}}^2)
.
\label{EqSovm0}
\end{equation}
The equation (\ref{EqSovm0}) arises as a consequence of the scalar equation (\ref{EqScalar}) when the higher derivatives of the scalar field $\phi$ from the other field equations of the theory are substituted into it.

\subsection{Scalar field of the form
$\phi=\phi(x^0,x^1,x^2,x^3)$ and $\phi_{,1}\neq 0$.}

Assume that the scalar field $\phi$ depends on all variables, including the null variable $x^1$, on which the spacetime metric does not depend.

In this case, the system of BDT equations is quite cumbersome, but it allows one to find the conditions for the compatibility of field equations, which leads to relations of the following form:
\begin{equation} \phi_{,2}(2f_0f_0{}''-3{f_0{}'}^2)=\phi_{,3}(2f_0f_0{}''-3{f_0{}'}^2)=0
\label{sovm2}
.\end{equation}

The requirement $\phi_{,1}\neq 0$ imposes strict conditions on the dependence of the scalar field on the variables $x^2$ and $x^3$, so the case of ${\phi_{,2}}^2+{ \phi_{,3}}^2\neq 0$ in (\ref{sovm2})
leads to the degeneration of the space into a flat one for any $\omega$.

Thus, the scalar field for $\phi_{,1}\ne 0$ can only have the following form:
\[ \phi=\phi(x^0,x^1).\]
In this case, the system of BDT equations takes the following form:
\begin{equation} \phi_{,00}=\frac{f_0{}'}{f_0}\phi_{,0}+\frac 32\frac{{f_0{}'}^2}{f_0{}^2}-(\omega+1)\phi_{,0}{}^2+\frac{f_0{}''}{f_0}\end{equation}
\begin{equation} \phi_{,01}=\frac{\Lambda}2f_0-\frac{\omega+2}2\phi_{,0}\phi_{,1}-\frac 14\frac{f_0{}'}{f_0}\phi_{,1}\end{equation}
\begin{equation} \phi_{,11}=-(\omega+1)\phi_{,1}{}^2\label{eqq11}\end{equation}
\begin{equation} (2\omega f_0\phi_{,0}-f_0{}')(2\omega+3)\phi_{,1}-2(2\omega+1)\Lambda f_0{}^2=0\end{equation}
\begin{equation} (R+\Lambda)f_0+\omega\phi_{,0}\phi_{,1}-\frac 32\frac{f_0{}'}{f_0}\phi_{,0}=0\end{equation}
Consider the equation(\ref{eqq11}). For $\omega\neq -1$ the scalar field is in the form
\begin{equation}
\phi(x^0,x^1)=\frac 1{\omega+1}\ln{\Bigl(a(x^0)x^1+b(x^0)\Bigr)}
,
\end{equation}
however, as a result of substitution into other equations of the system and separation of the coefficients of $x^1$, it turns out that $a(x^0)=0$, and the scalar field does not depend on $x^1$. Consequently,
a solution that satisfies the stated requirements is possible only for $\omega=-1$.

Integration of the equation (\ref{eqq11}) and separation of the coefficients for $x^1$ for $\omega=-1$  leads to the scalar field $\phi=\alpha x^1+b(x^0)$, $ \alpha - const$.
Substitution
into other equations of the system allows to find all unknown functions.

The final solution for the case $\phi=\phi(x^0,x^1)$  is as follows:
\begin{equation}
f_0=e^{\beta x^0}
,\end{equation}
\begin{equation}
\left({t_{2}}' \right)^2=2\alpha\beta\, t_{2}{}^3+\lambda\, t_{2}{}^2
+\gamma\, t_{2}+\delta
,
\end{equation}
\begin{equation}
\left({t_{3}}' \right)^2=-\Bigl(2\alpha\beta\, t_{3}{}^3+\lambda\, t_{3}{}^2
+\gamma\, t_{3}+\delta \Bigr)
\end{equation}
\begin{equation}
\omega=-1,
\qquad
\phi(x^0,x^1)=\frac{\Lambda}{\alpha\beta}e^{\beta x^0}-\frac{\beta}2 x^0+\alpha x^1
\label{sol2full}
,
 \end{equation}
where $\alpha$, $\beta$, $\gamma$, $\delta$ and $\lambda$ are constants.

In the resulting solution, we can set $\alpha=\beta=1$ by scaling transformations, then
\begin{equation}
f_0=\exp{x^0}
,\qquad
\left({t_\mu{}' }\right)^2=(-1)^\mu \Bigl(2 t_\mu{}^3+\lambda t_\mu{}^2+\gamma t_\mu+\delta\Bigr)
,
\end{equation}
\begin{equation}
\omega=-1
,\qquad
\phi(x^0,x^1)=\Lambda e^{x^0}-x^0/2+ x^1
.
\end{equation}
The cosmological constant $\Lambda$ remains arbitrary, the Riemann curvature tensor $R_{ijkl}$ and the Weyl conformal curvature tensor $C_{ijkl}$ do not vanish, and for the scalar curvature $R$ we obtain:
\begin{equation}
R=e^{-x^0},
\qquad
C_{ijkl}\neq 0.
\end{equation}

Thus, a nontrivial solution is obtained for Shapovalov wave spaces of type I in the Brans-Dicke theory with a scalar field depending on null variables, with a cosmological constant and an exponential conformal factor depending on the wave variable. Note that a vacuum solution of this type does not arise in general relativity \cite{Osetrin2020Symmetry} .

\subsection{Scalar field of the form
$\phi=\phi(x^0,x^2,x^3)$.}

Let's consider the case when the scalar field $\phi$ does not depend on the ''ignored'' null variable $x^1$, on which the metric does not depend either.
The system of BDT equations (\ref{tbd}-\ref{trac}), resolved with respect to higher derivatives, takes the following form:
\begin{equation} \phi_{,00}=\frac{f_0{}'}{f_0}\phi_{,0}+\frac 32\frac{{f_0{}'}^2}{{f_0}^2}-\frac{f_0{}''}{f_0}-(\omega+1)\phi_{,0}{}^2,\label{eq00}\end{equation}
\begin{equation} \phi_{,02}=\phi_{,2}\left(\frac 12\frac{f_0{}'}{f_0}-(\omega+1)\phi_0\right),\end{equation}
\begin{equation} \phi_{,03}=\phi_{,3}\left(\frac 12\frac{f_0{}'}{f_0}-(\omega+1)\phi_0\right),\label{eq03}\end{equation}
\begin{equation} \phi_{,22}=\Lambda Wf_0+\frac{\omega\phi_{,3}{}^2-(\omega+2)\phi_{,2}{}^2}2-\frac{\phi_{,2}t_2{}'+\phi_{,3}t_3{}'}{2W},\label{eq22}\end{equation}
\begin{equation} \phi_{,22}+\phi_{,33}=2\Lambda Wf_0-(\phi_{,2}{}^2+\phi_{,3}{}^2)\end{equation}
\begin{equation} \phi_{,23}=-(\omega+1)\phi_{,2}\phi_{,3}+\frac{\phi_{,2}t_3{}'-\phi_{,3}t_2{}'}{2W},\label{eq23}\end{equation}
\begin{equation}
(2\Lambda-R)Wf_0+\omega(\phi_{,2}{}^2+\phi_{,3}{}^2)=0,
\end{equation}
\begin{equation}
 R=\frac{{t_2{}'}^2+{t_3{}'}^2+W(t_2{}''-t_3{}'')}{W^3f_0},
\label{eq01}
 \end{equation}
\begin{equation} \Lambda(\omega+1)=0.\end{equation}

The study of the compatibility of the subsystem of equations (\ref{eq00}-\ref{eq03}) leads to relations that are further used to classify possible solutions:
\begin{equation} \phi_{,2}(2f_0f_0{}''-3{f_0{}'}^2)=\phi_{,3}(2f_0f_0{}''-3{f_0{}'}^2)=0\label{sovm}.\end{equation}
The compatibility equations (\ref{sovm}) lead to the following two possible cases:
\begin{enumerate}
\item[1)] ${\phi_{,2}}\,{\phi_{,3}}\neq 0,\quad 2f_0f_0{}''-3{f_0{}'}^2=0$;
\item[2)] $\phi_{,2}=\phi_{,3}=0$, \quad $\phi=\phi(x^0)$.
\end{enumerate}
In the following, we will consider these cases separately.

\subsubsection{Scalar field of the form  $\phi=\phi(x^0,x^2,x^3)$ and ${\phi_{,2}}\,{\phi_{,3}}\neq 0$.}

From the compatibility conditions we get $f_0=1/{\left({x^0}\right)^2}$ and now we can integrate the equations (\ref{eq00}-\ref{eq03}). In this case, two cases are possible depending on the values of the constant $\omega$:
\begin{enumerate}
\item[A)] $\omega=-1$, $\phi={ \xi(x^2,x^3)}/{x^0}$.
Substitution into the equation (\ref{eq01}) allows us to separate the coefficients at $x^0$. As a result, we get $R=0$, which, in view of (\ref{riman}) and (\ref{sovm}), means the degenerate case, since in this case the spacetime becomes flat.
\item[B)] $\omega\neq -1$, $\Lambda=0$, $\phi=\frac1{\omega+1}\ln\frac{ \xi(x^2,x^3)}{x^0}$,
where the function $\xi(x^2,x^3)$ must satisfy the following equations:
\begin{equation}
\xi_{,22}=\frac{\omega}{2(\omega+1)}\frac{\xi_{,2}{}^2+\xi_{,3}{}^2}{\xi}-\frac{\xi_{,2}t_2{}'+\xi_{,3}t_3{}'}{2W}
\label{Eq22}
,\end{equation}
\begin{equation}
  \xi_{,33}=\frac{\omega}{2(\omega+1)}\frac{\xi_{,2}{}^2+\xi_{,3}{}^2}{\xi}+\frac{\xi_{,2}t_2{}'+\xi_{,3}t_3{}'}{2W}
\label{Eq33}
,
\end{equation}
\begin{equation}
\xi_{,23}=\frac{\xi_{,2}t_3{}'-\xi_{,3}t_2{}'}{2W},
\label{eq23}
\end{equation}
\begin{equation}
\frac{\omega}{(\omega+1)^2}\frac{\xi_{,2}{}^2+\xi_{,3}{}^2}{\xi^2}=
\frac{{t_2{}'}^2+{t_3{}'}^2+W(t_2{}''-t_3{}'')}{W^2}
.
\label{EqSovm}
\end{equation}
\end{enumerate}

Let's consider the solution when the scalar field $\phi$ admits separation of variables:
\begin{equation}
\xi(x^2,x^3)=\xi_2(x^2)\,\xi_3(x^3)
,\qquad
{{\xi_2}'}\,{{\xi_3}'}\ne 0
.
\label{xi23}
\end{equation}
From here we get the relations:
\begin{equation}
\xi_{,2}=\xi\,
\frac{d}{dx^2}
\log{\xi_2}
,\qquad
\xi_{,3}=\xi\,
\frac{d}{dx^3}
\log{\xi_3}
.
\label{xi2andxi3}
\end{equation}
Substituting the relations (\ref{xi2andxi3}) into the equation (\ref{eq23}) and separating the variables, we get
\begin{equation}
{\xi_2}t_2{}'/{\xi_2}'-2t_2=
{\xi_3}t_3{}'/{\xi_3}'-2t_3
=\mbox{const}=2c
,
\end{equation}
In this way
\begin{equation}
2\,\frac{d\log{{\xi_2}}}{dx^2}=\frac{d\log{(t_2+c)}}{dx^2}
,\qquad
2\,\frac{d\log{{\xi_3}}}{dx^3}=\frac{d\log{(t_3+c)}}{dx^3}
.
\end{equation}
From this we obtain relations relating the functions $t_\mu$ and $\xi_\mu$ of the following form:
\begin{equation}
{\left(\xi_2\right)}^2=a(t_2+c),
\qquad
{\left(\xi_3\right)}^2=b(t_3+c)
\label{Solutions_xi2_and_xi3}
,
\end{equation}
where $a$, $b$ and $c$ are constants.

Since the functions $t_2, t_3$ enter the metric only as a difference, and the constants $a, b$ add only a constant term to the scalar field $\phi$, then the constants $a,b,c$ can be chosen in the simplest way. As a result, we have an intermediate result for the scalar field $\phi$:
\begin{equation} \xi = \sqrt{t_2 t_3},\ \ \ \ \phi=\frac 1{2(\omega+1)}\ln \frac{t_2t_3}{{x^0}^2}.\label {xi_t2t3}\end{equation}
Having this, excluding the second derivatives from the equations (\ref{Eq22}), (\ref{Eq33}), (\ref{EqSovm}), we obtain the following relation
\begin{equation} \omega(\omega+2)=0.\end{equation}
The case $\omega=0$ leads to a flat solution, it is easy to see this, taking into account the relations (\ref{riman}), (\ref{eq01}), thus,
\begin{equation} \omega =-2.\label{omega-2}\end{equation}

The sum of equations (\ref{Eq22}) and (\ref{Eq33}) after substituting (\ref{xi_t2t3}) and (\ref{omega-2}) allows us to separate variables, and we get
\begin{equation} \frac{t_2{}''}{t_2}-\frac 32\frac{{t_2{}'}^2}{{t_2}^2}=-\left(\frac{t_3{}'' }{t_3}-\frac 32\frac{{t_3{}'}^2}{{t_3}^2}\right)=\mbox{const}=\lambda,\end{equation}
 the solution is the following
\begin{equation}
t_2=\alpha / \cos^2 \sqrt{\lambda} x^2,\ \ \ \ \ t_3=\beta/\cosh^2\sqrt{\lambda} x^3.
\end{equation}
Substituting this solution into the equations (\ref{Eq22}) and (\ref{Eq33}) leads to a simple condition $\alpha=\beta $, further,
scaling constants $\alpha, \lambda$ can be converted to the simplest form, as a result, the final solution has the following form
\begin{equation}
f_0=1/{\left({x^0}\right)^2}
,\qquad
t_2=\epsilon/\cos^2 x^2
,\qquad
t_3=\epsilon/\cosh^2 x^3
,\qquad
\epsilon=\pm 1,
\end{equation}
\begin{equation}
\phi=\ln(x^0\cos x^2\cosh x^3)
,\qquad
\Lambda=0
\label{BDTsolutionII}
.\end{equation}
For the resulting exact solution (\ref{BDTsolutionII}) of the equations of the Brans-Dicke theory, the Riemann curvature tensor, the scalar curvature, and the Weyl conformal curvature tensor do not vanish:
\begin{equation} R=2\epsilon {x^0}^2,\ \ \ \ \ R_{2323}\neq 0,\ \ \ \ \ C_{ijkl}\neq 0.\end{equation}

\subsubsection{Scalar field of the form $\phi=\phi(x^0)$.}

Let's consider the case where the scalar field $\phi$ depends only on the non-ignorable wave variable $x^0$
($\phi_{,2}=\phi_{,3}=0$), on which the wave metric itself depends.
Equations (\ref{eq22}) and (\ref{eq01}) imply that
the cosmological constant $\Lambda$ and the scalar curvature $R$ vanish in this case:
\begin{equation} \Lambda=R=0.\end{equation}
Then you can immediately separate the variables in the equation (\ref{eq01}), which allows you to find
differential equations for the functions $t_\mu(x^\mu)$:
\begin{equation} {\left(t_{2}{}'\right)}^2=a {t_{2}}^2+2b t_{2}+c,
\label{t23Casex0}
\end{equation}
\begin{equation} {\left(t_{3}{}'\right)}^2=-\Bigl(a {t_{3}}^2+2b t_{3}+c\Bigr),
\end{equation}
where $a$, $b$ and $c$ are constants.

The system of field equations is left with the only equation (\ref{eq00}) connecting the function $f_0$ (scale factor of the metric) and the scalar field $\phi(x^0)$:
\begin{equation} \phi''=\phi'\left(\frac {f_0{}'}{f_0}-(\omega+1)\phi'\right)-\frac{2f_0f_0{}''-3{f_0 {}'}^2}{2{f_0}^2}\label{eqfi}
.\end{equation}
The equation (\ref{eqfi}) obviously admits solutions for the scalar field $\phi=\phi_0(x^0)$ for a given conformal factor $f_0(x^0)$ of the metric.

In the case under consideration, the Weil tensor $C_{ijkl}$ vanishes and only two nonzero components of the Riemann curvature tensor remain
$R_{ijkl}$:
\begin{equation} R_{0202}=R_{0303}=\frac{W}{4f_0}(3{f_0{}'}^2-2f_0f_0{}'')
,\end{equation}
\begin{equation}
C_{ijkl}
=R_{2323}
=0.
\end{equation}
Thus, this solution is the case of a conformally flat space, and the metric and components of the Riemann curvature tensor depend on the wave variable $x^0$.
The scalar field $\phi$ and the conformal factor of the metric $f_0$ remain arbitrary functions of the wave variable $x^0$, but are related by the equation (\ref{eqfi}).

Note that the equation (\ref{eqfi}) admits a de Sitter-type solution.
Consider the scale factor of the metric in the following form:
\begin{equation}
f_0(x^0)=k e^{\beta x^0}
,\qquad
k,\beta - \mbox{const}
\label{f0DeSitter}
.\end{equation}

Then the equation (\ref{eqfi}) takes the following form:
\begin{equation} \phi''=\phi'\left(\beta-(\omega+1)\phi'\right)+\beta^2/2
\label{eqfifi}
.\end{equation}
Equation (\ref{eqfifi}) for scalar field $\phi$ for metric (\ref{metric1}) with scale factor (\ref{f0DeSitter})
has three solutions depending on the values of the constant
$\omega$:
\begin{enumerate}
\item[1)]
$\omega=-1$. Then
\begin{equation} \phi=\beta e^{\beta x^0}-\frac{\beta}2 x^0,\end{equation}
\item[2)]
$\omega<-3/2$. Then
\begin{equation} \phi=\frac{\beta}{2(\omega+1)}x^0+\frac 1{\omega+1}\ln\cos(\beta\sqrt{-(2\omega+3)}\,x^0/2),\end{equation}
\item[3)]
$\omega>-3/2, \ \ \omega\neq-1$. Then
\begin{equation} \phi=\frac{\beta}{2(\omega+1)}x^0-\frac 1{\omega+1}\ln\cosh(\beta\sqrt{2\omega+3}\,x^0/2)
,
\end{equation}
\end{enumerate}
where $\beta$ is a constant parameter.

Thus, we have obtained a number of exact solutions to the equations of the scalar-tensor Brans-Dicke theory in vacuum for the type I Shapovalov wave space. Recall that there are no exact solutions of this type for the case of vacuum Einstein equations \cite{Osetrin2020Symmetry}, since Shapovalov spaces of type I degenerate in the case of vacuum Einstein equations.

Thus, scalar-tensor theories of gravity can give such types of exact models of gravitational waves that do not arise in general relativity.

\section{
Equations of motion and trajectories of test particles
}

Let's consider the equation of motion of test particles in a gravitational field in the Hamilton-Jacobi formalism (the speed of light is chosen to be unity):
$$
g^{\alpha\beta}\frac{\partial S}{\partial x^\alpha}\frac{\partial S}{\partial x^\beta}=m^2
.
$$

The complete integral of the Hamilton-Jacobi equation (\ref{HJE}) for the Shapovalov spacetimes in the privileged coordinate system can be represented in a separated form:
\begin{equation}
S={\theta}_0(x^0)+{\theta}_1(x^1)+{\theta}_2(x^2)+{\theta}_3(x^3),
\end{equation}
moreover, for the ignored variable $x^1$, on which the metric in the privileged coordinate system does not depend, the function ${\theta}_1(x^1)$ can be reduced by admissible coordinate transformations to the form $kx^1$, where $k$ is a constant.

From the equation (\ref{HJE}), separating the variable $x^0$, we get:
\begin{equation}
\frac{m^2}{f_0(x^0)}-2k{{\theta}_0}'(x^0)=\frac{1}{t_3(x^3)-t_2(x^2)}
\Bigl(
\left( {{\theta}_2}'(x^2) \right)^2
+
\left( {{\theta}_3}'(x^3) \right)^2
\Bigr)
=\mbox{const}=p
.
\end{equation}
Finally, separating the variables $x^2$ and $x^3$ we get:
\begin{equation}
\left( {{\theta}_2}'(x^2) \right)^2
+p t_2(x^2)
=
-\left( {{\theta}_3}'(x^3) \right)^2
+p t_3(x^3)
=\mbox{const}=q
.
\end{equation}

Thus, for the complete integral of the particle action function $S(x^\alpha,k,p,q)$ we obtain the following expression:
$$
S=kx^1-\frac{p}{2k}x^0+\frac{m^2}{2k}\int{\frac{dx^0}{f_0(x^0)}}
+\varepsilon_2\int{\sqrt{q-pt_2(x^2)}\,dx^2}
$$
\begin{equation}
\mbox{}
+\varepsilon_3\int{\sqrt{pt_3(x^3)-q}\,dx^2}
,\qquad
\varepsilon_2,\varepsilon_3=\pm 1
,
\end{equation}
where $k$, $p$ and $q$ are constant parameters.

The equations of trajectories of test particles for the considered Shapovalov spaces of type I in the Hamilton-Jacobi formalism take the form:
\begin{equation}
\frac{\partial S}{\partial k}
=\mbox{const}=\sigma_1
\quad\to\quad
x^1+\frac{p}{2k^2}x^0+\frac{m^2}{2k^2}\int{\frac{dx^0}{f_0(x^0)}}=\sigma_1
,\qquad
k\ne 0
\label{Trajectory1}
,
\end{equation}
\begin{equation}
\frac{\partial S}{\partial p}
=\mbox{const}=\sigma_2
\quad\to\quad
-\frac{x^0}{2k}
-\frac{\varepsilon_2}{2}\int{\frac{t_2(x^2)\,dx^2}{\sqrt{q-pt_2(x^2)}}}
+\frac{\varepsilon_3}{2}\int{\frac{t_3(x^3)\,dx^3}{\sqrt{pt_3(x^3)-q}}}
=\sigma_2
,
\label{Trajectory2}
\end{equation}
\begin{equation}
\frac{\partial S}{\partial q}
=\mbox{const}=\sigma_3
\quad\to\quad
\frac{\varepsilon_2}{2}\int{\frac{dx^2}{\sqrt{q-pt_2(x^2)}} }
-
\frac{\varepsilon_3}{2}\int{\frac{dx^3}{\sqrt{pt_3(x^3)-q}}}
=\sigma_3
,
\label{Trajectory3}
\end{equation}
where $\sigma_1$, $\sigma_2$ and $\sigma_3$ are new independent constant parameters of the test particle motion determined by the initial conditions. Thus, the motion of test particles in the considered space-time models is determined by a set of constant parameters $k$, $p$, $q$, $\sigma_1$, $\sigma_2$ and $\sigma_3$, given by the initial conditions.

Note that the proper time of the test particle $\tau$ using the obtained trajectory equations can be written in the following form in terms of the coordinate variables on the trajectory:
\begin{equation}
\tau=S\,\bigr |_{m=1}=2k x^1+\frac{p}{k}\,x^0
.
\label{taux0x1}
\end{equation}
Here we set the additive constant equal to zero by choosing the origin. Thus proper time, as expected, is a linear combination of the null variables $x^0$ and $x^1$.

If we substitute (\ref{taux0x1}) into the equation (\ref{Trajectory1}), then on the trajectories of test particles we get:
\begin{equation}
\tau=
-
\frac{1}{k}\int{\frac{dx^0}{f_0(x^0)}}+2k\sigma_1
\label{taux0}
,
\end{equation}

Thus, the equations (\ref{taux0x1}), (\ref{taux0}) together with the equations (\ref{Trajectory2}) and (\ref{Trajectory3}) define the coordinates of the test particle $x^\alpha$ on the trajectory as a function of of the proper time of the particle $\tau$.

\section{Conclusion}
The exact solutions of the vacuum equations of the Brans-Dicke theory of gravity for Shapovalov type I wave spaces are found. Gravitational-wave solutions are obtained, depending on the maximum possible number of variables for wave metrics of 4-dimensional space-time
(three variables, including the wave variable) in privileged coordinate systems, where it is possible to separate the wave variablesin the Hamilton-Jacobi equation for test particles and in the eikonal equation for radiation. The situation is shown to differ from the general theory of relativity, where these gravitational-wave models based on Einstein's vacuum equations degenerate \cite{Osetrin2020Symmetry}. Thus, Shapovalov's wave spaces provide an additional mathematical tool for obtaining exact models of gravitational waves, which makes it possible to study differences in modified gravity theories and form tests for observational verification of these differences.

\authorcontributions{Conceptualization, K.O.; methodology, K.O. and I.K.; validation, A.F., I.K., E.O. and K.O.;  investigation, K.O., I.K., A.F. and E.O; writing---original draft preparation, K.O.; supervision, K.O.; project administration, K.O.; funding acquisition, K.O. All authors have read and agreed to the published version of the manuscript.}

\funding{The reported study was funded by RFBR, project number N~20-01-00389~A.}

\conflictsofinterest{The authors declare no conflict of interest. }

\institutionalreview{Not applicable.}

\informedconsent{Not applicable.}

\dataavailability{Not applicable.}

\reftitle{References}

redpajama_set_name: RedPajamaArXiv