clamp_bounding_boxes collapses slightly tilted rotated boxes to a point because _order_bounding_boxes_points does not pick the leftmost corner #9676

🐛 Describe the bug

clamp_bounding_boxes deletes a rotated box that is tilted by a fraction of a degree and sticks out of the canvas. Both clamping_mode="soft" and "hard" return a zero-size box at (0, H) although most of the box is inside the image. The same box with tilt 0, or with the mirrored tilt, is clamped correctly.

import torch
from torchvision import tv_tensors
from torchvision.transforms.v2 import functional as F

def clamp(angle, mode):
    box = tv_tensors.BoundingBoxes([[13.355, 19.723, 75.347, 48.114, angle]], format="CXCYWHR",
                                   canvas_size=(200, 300), clamping_mode=mode, dtype=torch.float64)
    return F.clamp_bounding_boxes(box)[0].tolist()

print(clamp(0.0, "soft"))    # [25.514, 21.89, 51.029, 43.78, 0.0]      correct
print(clamp(0.2, "soft"))    # [25.480, 21.824, 51.113, 43.826, 0.2]    correct
print(clamp(-0.2, "soft"))   # [0.0, 200.0, 0.0, 0.0, 0.0]              the box is gone
print(clamp(-0.2, "hard"))   # [0.0, 200.0, 0.0, 0.0, 0.0]
print(clamp(179.9, "soft"))  # [0.0, 200.0, 0.0, 0.0, 0.0]

The box covers x from -24.6 to 51.3 on a 300 px wide canvas, so 2240 of its 3625 px² are inside the image.

How often. 2000 random boxes crossing only the left edge (w in [40, 120], h in [30, 90], float64), fraction clamped to zero area, identical for soft and hard:

The same happens around 90° and -90° (r = 89.9 and r = -90.1 collapse in the example above, 89.4 and -90.6 do not). On 4000 random boxes partially outside a 200x300 canvas, three fail in each mode: two collapse to a point, and the third (r = -90.07°) collapses in soft mode and is placed 5.6e4 px outside the canvas in hard mode (output cx = -28054, h = 56456).

Root cause. _order_bounding_boxes_points in torchvision/transforms/v2/functional/_meta.py documents "the point with the lowest x value, ties broken by the lowest y", but implements it as

_, x1 = (y / y_max + (x / x_max) * 100).min(dim=1)

The y term ranges over about one unit, so it outweighs any x difference smaller than x_max / 100. For a box tilted by less than about a degree the two left-hand corners are closer than that in x, the top one has the lower y, and it wins even when the bottom one is further left. _clamp_along_y_axis relies on the first point being the leftmost one: with the wrong point first, _clamp_y_intercept clamps the intercept of the top edge into the interval spanned by the two horizontal edges, which puts the top edge onto the bottom edge, and the box degenerates to a point. For the example box at -0.6° the two left corners are 0.50 px apart in x and the threshold is x_max / 100 = 0.51 px; at -1° they are 0.84 px apart and the box clamps fine, which is exactly the boundary of the table above. main (7b0e250) has the same code.

Fix. Order the points lexicographically, lowest x then lowest y, and treat x values within a few ulps of the largest coordinate as equal so that boxes at exactly 0, 90, 180 and 270 degrees still tie after the cos/sin round-off of the format conversion. torch.finfo is not scriptable, so the tolerance is a small per-dtype table. With the patch:

• the table above is 0 % everywhere and the 0°/180° results are unchanged,
• the 4000 random partially-outside boxes pass all four checks I could write down for both modes in float64: the result is a rectangle with the input orientation, hard results lie inside the canvas and inside the input box, soft results lie inside the input box and contain the polygon input ∩ canvas (on main these checks fail on the three collapsed boxes and the blown-up one),
• soft results for -0.05°, -0.2° and 179.9° are within 0.03, 0.13 and 0.07 px of the 0° result,
• test/test_transforms_v2.py from v0.29.0 against the installed 0.29.0 wheel, -k "Clamp or Rotate or Affine or Flip or Resize or Crop or Pad or Perspective or ConvertBoundingBoxFormat or Elastic or RandomIoUCrop or RandomZoomOut or SanitizeBoundingBoxes": 4943 passed, 2334 skipped, 348 xfailed, 2 errors that are fixture 'mocker' not found in TestRandomIoUCrop and unrelated,
• the new TestClampBoundingBoxes::test_small_tilt_is_not_collapsed (soft/hard x -0.05/-0.2/179.9 x float32/float64) fails 12/12 on the current code and passes 12/12 with the patch.

Possibly related, not addressed by the patch. For any nonzero tilt, clamping_mode="hard" returns half the box: with the example above, r = -0.05 gives w = 25.5 instead of 51.0 and r = +0.05 gives h = 21.9 instead of 43.8, while r = 0 keeps both. Over the 2000 left-edge boxes the hard area is 50.0 % (median) of the axis-aligned clamp for every tilt from 0.05° to 5° in either direction (measured with the patch applied, since on the current code the small negative tilts collapse), and 100 % at exactly 0°. A same-orientation rectangle with about twice the area fits inside input ∩ canvas, so this does not look like the "largest angle-preserving box enclosed within the original box and the image canvas" that _clamp_y_intercept describes. I can open a separate issue with the numbers if you want.

Is the ordering fix the direction you want, or would you rather make _clamp_along_y_axis independent of which corner comes first? I am happy to open the PR either way.

Patch

The complete change is below so that nobody has to redo it; I will open it as the PR as soon as a maintainer confirms the direction.

diff --git a/test/test_transforms_v2.py b/test/test_transforms_v2.py
index 6d9f973..faaab3d 100644
--- a/test/test_transforms_v2.py
+++ b/test/test_transforms_v2.py
@@ -5737,6 +5737,30 @@ class TestClampBoundingBoxes:
     def test_transform(self):
         check_transform(transforms.ClampBoundingBoxes(), make_bounding_boxes())
 
+    @pytest.mark.parametrize("clamping_mode", ("soft", "hard"))
+    @pytest.mark.parametrize("angle", (-0.05, -0.2, 179.9))
+    @pytest.mark.parametrize("dtype", (torch.float32, torch.float64))
+    def test_small_tilt_is_not_collapsed(self, clamping_mode, angle, dtype):
+        # A box that sticks out of the left edge of the canvas, tilted by a fraction of a degree in the direction that
+        # puts its bottom-left corner slightly left of its top-left corner. The point ordering used to pick the
+        # top-left corner as the first point anyway and the box was clamped down to a single point.
+        canvas_size = (200, 300)
+
+        def make(r):
+            return tv_tensors.BoundingBoxes(
+                [[13.355, 19.723, 75.347, 48.114, r]],
+                format="CXCYWHR",
+                canvas_size=canvas_size,
+                clamping_mode=clamping_mode,
+                dtype=dtype,
+            )
+
+        out = F.clamp_bounding_boxes(make(angle))
+        assert out[0, 2] > 1 and out[0, 3] > 1  # width and height in pixels, both were 0 before the fix
+        if clamping_mode == "soft":
+            # A tilt this small has to give almost the same box as no tilt at all
+            torch.testing.assert_close(out[0, :4], F.clamp_bounding_boxes(make(0.0))[0, :4], atol=0.3, rtol=0)
+
     @pytest.mark.parametrize("rotated", (True, False))
     @pytest.mark.parametrize("constructor_clamping_mode", ("soft", "hard", None))
     @pytest.mark.parametrize("clamping_mode", ("soft", "hard", None, "auto"))
diff --git a/torchvision/transforms/v2/functional/_meta.py b/torchvision/transforms/v2/functional/_meta.py
index 80bd23a..2d26897 100644
--- a/torchvision/transforms/v2/functional/_meta.py
+++ b/torchvision/transforms/v2/functional/_meta.py
@@ -446,9 +446,22 @@ def _order_bounding_boxes_points(
     if indices is None:
         output_xyxyxyxy = bounding_boxes.reshape(-1, 8)
         x, y = output_xyxyxyxy[..., 0::2], output_xyxyxyxy[..., 1::2]
-        y_max = torch.max(y.abs(), dim=1, keepdim=True)[0]
-        x_max = torch.max(x.abs(), dim=1, keepdim=True)[0]
-        _, x1 = (y / y_max + (x / x_max) * 100).min(dim=1)
+        # Lowest x first, lowest y among the points that share the lowest x. Two x values count as equal when they
+        # are within a few ulps of the largest coordinate, so that boxes rotated by exactly 0, 90, 180 or 270 degrees
+        # still tie after the cos/sin round-off of the format conversion, while a real tilt picks the leftmost point.
+        if x.dtype == torch.float64:
+            rel_tol = 8 * 2.220446049250313e-16
+        elif x.dtype == torch.float32:
+            rel_tol = 8 * 1.1920928955078125e-07
+        elif x.dtype == torch.bfloat16:
+            rel_tol = 8 * 0.0078125
+        elif x.dtype == torch.float16:
+            rel_tol = 8 * 0.0009765625
+        else:
+            rel_tol = 0.0
+        x_min = x.amin(dim=1, keepdim=True)
+        tol = x.abs().amax(dim=1, keepdim=True) * rel_tol
+        x1 = torch.where(x <= x_min + tol, y, y.amax(dim=1, keepdim=True) + 1).argmin(dim=1)
         indices = torch.ones_like(output_xyxyxyxy)
         indices[..., 0] = x1.mul(2)
         indices.cumsum_(1).remainder_(8)

AI disclosure: I used an AI coding agent to help write this patch, the tests and this description. I have read the change and the tests myself and I will answer review comments personally.

Versions

torchvision 0.29.0+cpu (main 7b0e250 has the same _order_bounding_boxes_points)
torch 2.14.0+cpu
Python 3.13.14, Linux x86_64 (glibc 2.34), CPU only, no CUDA