AI Engineer Exhaustive
HardComputer Vision

ROI Pooling

Computer Vision

Hard

Problem

Convert each rectangular region of a feature map into a fixed square grid with max pooling. Each region is [x_1,y_1,x_2,y_2] with half-open bounds, so it contains rows y_1 through y_2-1 and columns x_1 through x_2-1.

For output row i, use:

h_{\mathrm{start}}=y_1+\left\lfloor\frac{iH_R}{S}\right\rfloor

h_{\mathrm{end}}=y_1+\left\lfloor\frac{(i+1)H_R}{S}\right\rfloor

For output column j, use:

w_{\mathrm{start}}=x_1+\left\lfloor\frac{jW_R}{S}\right\rfloor

w_{\mathrm{end}}=x_1+\left\lfloor\frac{(j+1)W_R}{S}\right\rfloor

Here, H_R=y_2-y_1, W_R=x_2-x_1, and S is output size. Expand an empty bin to one pixel, then take its maximum. Return one square two-dimensional list per region, preserving region order.

Theory

In object detection, a region proposal network suggests many regions of interest (ROIs) of different sizes. But the classifier that follows needs fixed-size inputs.

The challenge:

ROI pooling converts arbitrary-sized regions into fixed-size feature maps.

How ROI Pooling Works

Given:

For each ROI:

  1. Divide the ROI into a grid of output_size x output_size bins
  2. Apply max pooling within each bin
  3. Result: one output_size x output_size feature map per ROI

Bin Calculation

For an ROI with coordinates (x_1, y_1, x_2, y_2):

ROI dimensions:

For bin (i, j) in the output grid:

h_{start} = y_1 + \left\lfloor \frac{i \cdot \text{roi}_h}{\text{output size}} \right\rfloor

h_{end} = y_1 + \left\lfloor \frac{(i+1) \cdot \text{roi}_h}{\text{output size}} \right\rfloor

Similarly for width. Then take the max value in that bin region.

Numerical Example

Feature map (6x8):

 1  2  3  4  5  6  7  8
 2  3  4  5  6  7  8  9
 3  4  5  6  7  8  9 10
 4  5  6  7  8  9 10 11
 5  6  7  8  9 10 11 12
 6  7  8  9 10 11 12 13

ROI: [1, 1, 5, 5] (x1=1, y1=1, x2=5, y2=5) Output size: 2x2

ROI dimensions: roi_h = 4, roi_w = 4

Bin (0, 0):

Bin (0, 1):

Bin (1, 0):

Bin (1, 1):

Output:

5  7
7  9

Quantization Issues

ROI pooling has quantization errors:

Problem 1: ROI coordinates are quantized

Problem 2: Bin boundaries are quantized

These errors hurt accuracy, especially for small objects.

Handling Edge Cases

Empty bins:

ROI outside feature map:

Very small ROIs:

ROI Align: The Improvement

ROI Align (from Mask R-CNN) fixes quantization issues:

Key differences:

Result:

Multi-Channel ROI Pooling

For a feature map with C channels:

The pooling operation is the same; just repeated for each channel.

Where ROI Pooling Is Used

Faster R-CNN:

Fast R-CNN:

Feature Pyramid Networks:

ROI Pooling vs. Spatial Pyramid Pooling

ROI Pooling:

Spatial Pyramid Pooling (SPP):

Both solve the "variable size to fixed size" problem but in different ways.

Implementation Strategy

For each ROI:

  1. Extract ROI bounds
  2. Compute bin boundaries (with floor division)
  3. For each bin: a. Handle empty bin case b. Extract the region from feature map c. Compute max value d. Store in output
  4. Return output tensor

When multiple ROIs are processed, the result is a list (or batch) of fixed-size feature maps.

Examples

Example 1

Input
feature_map = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]], rois = [[0, 0, 4, 4]], output_size = 2
Output
[[[6, 8], [14, 16]]]
Explanation
The full map splits into four two-by-two bins, and each output contains one bin maximum.

Example 2

Input
feature_map = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]], rois = [[0, 0, 2, 2], [2, 2, 4, 4]], output_size = 2
Output
[[[1, 2], [5, 6]], [[11, 12], [15, 16]]]

Hints

  1. Use math.floor on each scaled bin boundary.
  2. Collect values between each pair of half-open row and column boundaries, then take max.

Requirements

Constraints

Starter Code

import math

def roi_pool(feature_map: list, rois: list, output_size: int) -> list:
    """
    Returns a list of pooled grids.
    """
    # Write code here
    pass

Test Cases

CaseMatches
Full map 2x2 pool—public
Two separate ROIs—public