P5-T5 — Bounding Boxes and Geometric Object Properties

Learning objectives

After this lesson, you should be able to:

• Define axis-aligned and oriented bounding boxes and compute the area penalty of the axis-aligned box.
• Fit a minimum-area oriented rectangle to points and derive centre, size, heading and distance from it.
• Write the seven parameters of a 3D box and the intersection-over-union of two boxes.
• Explain what a partial view of an object permits, and how priors on size and shape help.

The idea: a few numbers for an object

A planner does not want 150 points; it wants a footprint to keep clear of, a position to follow and perhaps a heading. A bounding box offers that in seven numbers.

A box is a statement about space. Make it as tight as the data allow, and be honest about the parts that were not seen.

The mathematics: minimum-area box, parameters and IoU

Minimum-area oriented rectangle

For a heading θ, rotate the points into axes aligned with θ and take the extents:

(x_i, y_i)

the point coordinates in the ground plane (the z coordinate is used only for the height).

θ

the heading of the first box axis, counter-clockwise from +x. Rotating the frame by 90° only swaps length and width, so [0°, 90°) is enough.

A(θ)

the area of the bounding rectangle for that heading.

The optimum is attained at a heading where one side of the rectangle lies along an edge of the convex hull of the points (the rotating-calipers result), so an exact algorithm needs to check only the hull edges. Scanning every degree is simple and accurate to about a degree. The other properties follow from the best angle: the centre is the middle of the u and v extents rotated back, the length and width are the extents, the height is max z − min z and the distance is the smallest range among the points.

3D box parameters and IoU

A 3D box has seven parameters, (x, y, z, l, w, h, ψ): centre, size and yaw. Two boxes are compared by intersection over union:

For boxes in the plane the intersection is a polygon found by clipping; 3D IoU multiplies by the overlap in height. IoU is 1 for identical boxes and 0 for disjoint ones, and is the standard score in detection benchmarks (Lesson P6-T5).

What a partial view allows

A LiDAR sees the surfaces facing it. For a box, that is one face (seen head-on) or two (seen from a corner), so the points form a line or an L-shape. The fitted rectangle then covers only the visible faces: its size is a lower bound on the object’s size along the line of sight and the heading is determined only if an L is visible. With a single face the heading is perpendicular to the line (or parallel), but the depth of the object is unknown.

Standard remedies add prior knowledge: typical sizes for the class (a car is about 4.5 × 1.8 m), the assumption that the object rests on the ground and is rectangular, and consistency over time as the viewpoint changes (a tracker accumulates the shape).

A worked example: what the wrong box costs, and an L-shape

Cost of the axis-aligned box

The object in the figure is 2 m × 1 m, turned by 45°. Its own area is 2.0 m². The axis-aligned box has side 2·(1·cos 45° + 0.5·sin 45°) = 2.12 m in each direction.

A planner that treats the axis-aligned box as occupied gives up 2.5 m² of free space around this single object: in a narrow aisle that can be the difference between passing and not. For a long, thin object (a 4 m by 0.5 m pipe at 45°) the ratio is even larger: the AABB has side 3.18 m and an area of 10.1 m² against 2.0 m².

An L-shape seen from a corner

A LiDAR sees a box from its nearest corner at (5, 0) and gets points on two perpendicular faces, one going up and to the right for 1.0 m, the other going down and to the right for 0.8 m, with a point every 0.2 m: (5.00, 0.00), (5.14, 0.14), (5.28, 0.28), (5.42, 0.42), (5.57, 0.57), (5.71, 0.71), (5.14, -0.14), (5.28, -0.28), (5.42, -0.42), (5.57, -0.57). Trying all headings, the smallest rectangle has area 0.80 m² at 45° with sides 1.00 × 0.80 m, while the axis-aligned box has area 0.90 m². The oriented box follows the two faces (sides of about 1.0 and 0.8 m, the lengths of the visible faces) and its heading is the direction of the longer face; the axis-aligned box is 1.1 times larger.

What is unknown here is the far side of the box. The rectangle spans only the visible faces: the real box may be deeper by up to its depth. If it is a car (about 1.8 m wide, 4.5 m long) and the visible faces are 1.5 m and 1.2 m, the box is incomplete: the planner should treat the unseen part as possibly occupied, or use a size prior to extend the box away from the sensor.

IoU of two boxes

Two 4 m × 2 m boxes (area 8 m² each) overlap by a 3 m × 2 m region (area 6 m²) because one is shifted by 1 m along its length. Union = 8 + 8 − 6 = 10 m², so IoU = 6/10 = 0.60. A shift of 0.5 m gives intersection 7 and IoU = 7/9 = 0.78. Detectors are often scored by whether IoU exceeds 0.5 or 0.7; a one-metre localisation error on a 4 m object is enough to fall below 0.7.

Engineering implications and limitations

Fit to the visible points, report the visible extent. Say in the data which faces were seen (a flag for “L-shape”, “single face”), so that the planner can treat the unseen side as unknown.

Use priors with a flag. Extending a box to a typical object size is useful and risky: a small vehicle with the prior of a large one, or a person treated as a car, gives wrong space. Keep the measured box and the completed box separately, with the source of each dimension.

Smooth over time. Heading flips between frames when only one face is visible, and a box can jump by half a length as faces appear. Track the box with a filter (Module 7) and use the motion direction to fix the heading of moving objects.

Use the right distance. For collision avoidance the relevant distance is from the robot’s footprint to the box polygon (or the nearest point), not to the box centre. A long object’s centre may be 8 m away while its end is 2 m away.

Remember the vertical. Height is measured relative to the fitted ground plane (Lesson P5-T3), not the sensor. A cluster whose lowest point is well above the ground is an overhanging object (a branch, a sign) which a ground robot may be able to pass beneath.

Test with known shapes. Generate boxes at known sizes and headings, scan them with the sensor model, and measure the box error as a function of range and yaw. The error at long range and grazing angles tells you the useful limit of the detector.

Common misconceptions

Engineering takeaways

1. AABB overestimates a turned object (2.25 times the area for a 2 × 1 m box at 45°); the minimum-area oriented box follows the object.
2. Fit by trying headings 0–90°: rotate, take extents, keep the smallest area; centre, length, width, height and nearest distance follow.
3. A 3D box has seven parameters (x, y, z, l, w, h, yaw); IoU = |A ∩ B| / |A ∪ B| compares boxes.
4. A sensor sees one or two faces, so the box covers the visible part; priors on size and consistency over time extend it, and should be flagged.
5. Smooth heading over time, use distance to the footprint, measure height above the ground plane, and test with known shapes.

References and further reading

Standard references; the areas, the L-shape fit and the IoU numbers were computed for this lesson.

• Freeman, H. and Shapira, R. (1975). Determining the minimum-area encasing rectangle for an arbitrary closed curve. Communications of the ACM 18(7): the minimum-area rectangle has a side along a hull edge.
• Zhang, X., Xu, W., Dong, C. and Dolan, J. M. (2017). Efficient L-shape fitting for vehicle detection using laser scanners. IEEE Intelligent Vehicles Symposium: fitting a rectangle to the visible L-shape of a vehicle.
• Geiger, A., Lenz, P. and Urtasun, R. (2012). Are we ready for autonomous driving? The KITTI vision benchmark suite. CVPR: 3D box parameterisation and IoU-based evaluation.
• Everingham, M. et al. (2010). The Pascal Visual Object Classes (VOC) Challenge. International Journal of Computer Vision 88: intersection over union.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: what a sensor cannot see: occlusion, sparse returns at range and how they limit detection.

Related content

Nothing below is required to finish this lesson.

• Before
  P5-T4: Clustering and Object Separation

  Cluster points into objects and choose distance thresholds.

• Lab
  P5-L3: Debug a Failed 3D Detection Pipeline

  Repair range-dependent clustering and oriented boxes so distant and partially seen objects are found.