How "Patch Merging" works in SWIN-Transformers?

Question

In the SOTA paper: SWIN-Transformers, the authors have tried their best to explain everything clearly. I have got an idea of how it works except the Patch Merging part. I found some blogs and other things explaining this but still I am not able to comprehend how the shape changes and how come the SHAPE of windows are changed at the time when the only thing thy are doing is Concatenating the neighbouring 2x2 patches. Could someone please explain it in Laymen terms or maybe a video link or something intuitive explanation.

• This awesome blog explains every detail clearly
• Implementation in Pytorch from scratch with explanation
• Keras / Tensorflow Implementation

Below are some intuitive images which I am trying to grasp in bits and pieces

Answer 1

What happens during the patch merging? Concatenationating is only one part of the whole operations. Below, I quote the code from the original implementation and explain step by step what happens.

x = x.view(B, H, W, C)

Firstly, x, the input image, needs to be reshaped to regain the height H and width W.

x0 = x[:, 0::2, 0::2, :]  # B H/2 W/2 C
x1 = x[:, 1::2, 0::2, :]  # B H/2 W/2 C
x2 = x[:, 0::2, 1::2, :]  # B H/2 W/2 C
x3 = x[:, 1::2, 1::2, :]  # B H/2 W/2 C

Then, the input is vectorised. Since Swin merges 4 tokens into 1 patch, one token out of a square of 4 is selected. How does the selection process work? Each vector is specialised in one corner of the square. x0 always consists of the top left corner, x1 of the bottom left corner and so on. So during this prep step, the input is divided into 4 quarters.

x = torch.cat([x0, x1, x2, x3], -1)  # B H/2 W/2 4*C

The next step is the one you already found. The 4 vectors are concatenated. Since each vector is a quarter of the input, they are half the height (H/2) and half the width (W/2) of the input. 4 quarters exists so the channel size quadruples 4*C.

By the end of this step, the desired downsampled shape in the height and width dimension are created BUT there are two many channels. Swin doubles it channels during each patch merging operation, not quadruples it. That means Swin keeps 2 tokens to represent a square of 4 tokens.

How do we get from 4 channels to 2? Via reduction through a linear layer.

x = self.reduction(x)

This operation reduces the channel size from 4 to 2.

How is the reduction defined?

self.reduction = nn.Linear(4 * dim, 2 * dim, bias=False)

As a linear projection from dim 4 to 2.