Patch Grid for a Resized Image
Problem Statement
A ViT-style encoder first resizes an image to a fixed square side, then cuts it into non-overlapping patch x patch tiles. Report the patch grid.
Background
If an image is resized to side x side and split into patch x patch tiles, the grid is (side // patch) rows by (side // patch) columns and the number of visual tokens is their product. When side is not divisible by patch, the leftover strip on the right/bottom is dropped (floor division) — the usual reason a "224" model uses 16-pixel patches (14x14 = 196 tokens).
Your Task
Implement:
def patch_grid(side, patch):
Return a dict with keys "rows", "cols", "num_tokens" (all ints).
Input Format
- side (int): the square side the image is resized to.
- patch (int): the patch edge length.
Output Format
A dict of three ints.
Sample
print(patch_grid(224, 16))
Output:
{'rows': 14, 'cols': 14, 'num_tokens': 196}
Example:
print(patch_grid(224, 16))
{'rows': 14, 'cols': 14, 'num_tokens': 196}- Determine the number of patches that fit along one dimension by performing floor division of the image side by the patch size, which discards any remainder: n=224//16=14.
- Assign this value to both grid dimensions since the image is square and patches are square, resulting in 14 rows and 14 columns.
- Calculate the total number of visual tokens by multiplying the number of rows by the number of columns: 14×14=196.
- The final output is
{'rows': 14, 'cols': 14, 'num_tokens': 196}
Constraints:
1 <= patch <= side <= 4096- Use floor division; a non-divisible remainder strip is dropped.
- All three returned values are ints.
1. Background Knowledge
In Vision Transformers (ViT), an input image is not processed as a whole but is split into a grid of small, non-overlapping square regions called patches. Each patch is then linearly projected into a vector, and these vectors serve as the visual tokens fed into the Transformer encoder. This design mirrors how text is tokenized in language models: just as a sentence becomes a sequence of word tokens, an image becomes a sequence of patch tokens.
The geometry is straightforward. If an image is resized to a square of side length S and each patch has edge length P, the number of patches that fit along one dimension is given by integer (floor) division:
N=⌊PS​⌋Because the image is square, the grid is N×N, and the total number of visual tokens is N2. When S is not evenly divisible by P, the leftover strip along the right and bottom edges is simply discarded. This is why a standard ViT model that resizes to 224×224 with 16×16 patches produces 14×14=196 tokens.
Understanding this mapping is essential for working with patch embedding layers, computing attention masks, or designing custom vision backbones. The patch grid dimensions directly determine the sequence length of the token array, which affects memory usage and computational cost in subsequent Transformer layers.
2. Algorithm Approach
This is a direct computation problem. There is no search, iteration, or complex data structure involved. The approach is:
- Compute the number of patches per row (and per column, since the image is square) using floor division.
- Square that value to get the total token count.
- Package the three integers into a dictionary.
The entire logic fits in a few arithmetic operations. The key insight is recognizing that "non-overlapping tiles dropped at the edges" maps exactly to the floor-division operator // in Python.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.