# Segmenting Urban Scene Imagery in Real Time Using an Efficient UNet-like Transformer
## 2 Methods
### Decoder
#### 2.2.1 Focused Linear Attention  
First, we analyzed the self-attention in the standard Transformer. Considering \(N\) tokens \(z\in\mathbb{R}^{N\times C}\), the details of the self-attention calculation in each head are shown in Equation (2):  
\[ \begin{array}{l}\mathcal{O}=zW_{\mathcal{O}},K=zW_{\mathcal{K}},V=zW_{ \mathcal{V}}\\ O_{i}=\sum\limits_{j=1}^{N}\sum\limits_{\sum_{l=1}^{N}\frac{L(O_{i},K_{j})}{ \sum_{l=1}^{N}L(O_{i},K_{j})}}V_{j}\end{array} , \tag{2}\]  
where \(W_{\mathcal{O}}\), \(W_{\mathcal{K}}\), and \(W_{\mathcal{V}}\in\mathbb{R}^{C\times C}\) are the transformation matrices, and \(L(0)\) denotes the similarity function. In many Transformer architectures, the Softmax attention mechanism is often used to represent this similar relationship. As a result, the algorithm computes the attention between all the query-key pairs, resulting in O (N\({}^{2}\)) computation complexity. Due to the computational complexity quadratic to the input, it limits the potential to apply Transformer-based models to real-time scenes. Some studies used sparse global attention or partitioned smaller windows to solve this problem, but these methods sacrificed the model's ability to model global context to some extent. Meanwhile, the linear attention reduces the computational complexity from O (N\({}^{2}\)) to O (N) and has the potential to replace the traditional Softmax attention mechanism in Transformer-based models. Specifically, LNA uses a carefully designed kernel function to approximate the similarity function:  
\[L(Q,K)=\delta(Q)\delta(K)^{T}, \tag{3}\]  
where we can rewrite the previous formula as:  
\[O_{i}=\sum\limits_{j=1}^{N}\frac{\delta(Q_{i})\delta\left(K_{j}\right)^{T}}{ \sum\limits_{j=1}^{N}\delta(Q_{i})\delta\left(K_{j}\right)^{T}}V_{j}. \tag{4}\]  
As a result, we can change the order of self-attention computation based on the matrix multiplication properties, i.e.,  
\[O_{i}=\frac{\delta(Q_{i})\left(\sum\limits_{j=1}^{N}\delta\left(K_{j}\right)^{ T}V_{j}\right)}{\delta(Q_{i})\left(\sum\limits_{j=1}^{N}\delta\left(K_{j} \right)^{T}\right)}, \tag{5}\]  
where the computational complexity is reduced to O (N). However, existing LNA modules are either unable to fully achieve the same performance capability as the Softmax attention mechanism, or they incur additional computational costs from designing complex kernel functions, so directly applying LNA to the Transformer model is not a simple problem. Fortunately, the novel focused linear attention mechanism [25] offers a new approach to solving the problem, which can reduce the self-attention computation complexity while maintaining the performance. On the one hand,the Softmax attention mechanism has the property of nonlinear weighting, which makes it more likely to focus on the more important image features. However, the traditional LNA has a smoother and more homogeneous attention distribution, which makes it difficult to focus on the information-rich regions of the image. As a remedy, based on the LNA, FLA makes the same query-key pairs closer and different query-key pairs farther away by changing the orientation of each query and key vector. Specifically, a simple function, \(f_{c}\), is proposed to perform this mapping:  
\[ \begin{split}& L\big{(}Q_{i},K_{j}\big{)}=\delta_{c}(Q_{i})\delta_{c} (K_{j})^{\top}\\ &\delta_{c}(z)=\ f_{c}(\text{Re}LU(z)),\ f_{c}(z)=\frac{\|z\|}{\| z^{\ast k}\|}\ Z^{\ast\ast k},\end{split}  \tag{6}\]  
where \(z^{\ast\ast k}\) denotes \(z\) to the power of \(k\), and we found that the norm of the feature remains after mapping (\(\|z\|=\|f_{c}\left(2\right)\|\)), indicating that only the vector direction is changed. As a result, the mapping function \(f_{c}\) can actually affect the attention distribution. As is shown in Figure 2, we can see that \(f_{c}\) makes each vector closer to the axis closest to the vector, and the proximity can be controlled by the parameter \(k\).