Range Image Interpretation of Mail Pieces with Superquadrics

Franc Solina, Ruzena BajcsyAAAI 1987

Abstract

Automating the sorting of non-flat mail pieces, such as parcels and tubes, presents a significant challenge due to the inherent variability and physical imperfections of real-world objects. This paper proposes a robust interpretation method using superquadrics—a flexible family of parametric shapes. By fitting these models to 3D range data through numerical optimization, the system can simultaneously determine an object's position, orientation, size, and shape category. The approach is resilient to noise and surface irregularities, providing a unified framework for the classification of diverse mail items.

Introduction

In the late 1980s, postal automation was highly effective for standard flat letters but struggled with the "messy" reality of parcels and packages. Unlike letters, packages vary wildly in geometry and often feature crumpled edges, wrinkled wrapping, or bulging sides. Traditional computer vision techniques, which relied on rigid geometric primitives like perfect boxes or cylinders, were often insufficient for these irregular forms.

The authors address this by bridging the gap between low-level scene description and high-level object recognition. Instead of maintaining a massive library of every possible box size, they utilize a mathematical primitive flexible enough to represent a broad class of shapes with a minimal set of parameters.

Methodology: The Power of Superquadrics

The core of this approach is the superquadric, a parametric surface that generalizes the ellipsoid. By adjusting "squareness" parameters ($\epsilon_1, \epsilon_2$), a single mathematical model can smoothly transition between a sphere, a cylinder, and a rectangular box.

Model Fitting and Optimization

To fit a superquadric to a cloud of 3D range points, the authors employ an Inside-Outside function $F(x, y, z)$. This function determines whether a point lies on, inside, or outside the model's surface. The fitting process involves minimizing the error between the observed data points and the model surface using the Levenberg-Marquardt method.

The iterative convergence of a superquadric model to a set of range data points, showing stages from initial estimate (E) through 20 iterations.

To ensure the model accurately captures the object's boundaries rather than expanding to fit occluded space, a smallest volume constraint is added to the cost function. Furthermore, to prevent the optimization from getting stuck in local minima, "jitter" is introduced via Poisson-distributed noise, helping the algorithm find the global best fit.

Key Insights and Results

The research highlights several critical advantages of using superquadrics for range image interpretation:

  1. Shape as a Continuum: Rather than forcing an object into a binary "box" or "cylinder" category, superquadrics treat shape as a continuous spectrum. A parcel with rounded corners is simply represented by specific squareness values.
  2. Robustness to Noise: By using only 11 to 13 parameters to describe hundreds of data points, the system is inherently overconstrained. This makes it highly resistant to surface noise, such as wrinkles in brown paper packaging.
  3. Segmentation by Recovery: A significant innovation is the idea that segmentation—separating an object from its background—can occur during the modeling process. The model "carves out" the object by iteratively fitting itself to the densest cluster of points.
Superquadric models fitted to multiple objects within a range image, demonstrating the system's ability to interpret complex scenes.

The system successfully recovered position, orientation, size, and deformation parameters (like tapering) simultaneously. On the hardware of the time (a VAX 785), convergence typically occurred within 12 to 20 iterations, with each iteration taking approximately 15 seconds for 500 points.

Conclusion

This work demonstrates that superquadrics provide a powerful and flexible tool for interpreting complex 3D scenes. By representing shapes parametrically, the system can classify mail pieces—identifying "flats," "tubes," or "parcels"—based on recovered dimensions and squareness. While computationally intensive for its era, the method laid the groundwork for more advanced automated handling systems by accounting for the geometric imperfections of real-world objects.

Summary updated

BibTeX
@inproceedings{solina1987range,
  author = {Franc Solina and Ruzena Bajcsy},
  title = {{Range Image Interpretation of Mail Pieces with Superquadrics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure