# Object shape recognition using rectangle fitting — PythonRobotics documentation

# Object shape recognition using rectangle fitting

This is an object shape recognition using rectangle fitting.

This example code is based on this paper algorithm:

- Efficient L-Shape Fitting for Vehicle Detection Using Laser Scanners - The Robotics Institute Carnegie Mellon University

The algorithm consists of 2 steps as below.

## Step1: Adaptive range segmentation

In the first step, all range data points are segmented into some clusters.

We calculate the distance between each range data and the nearest range data, and if this distance is below a certain threshold, it is judged to be in the same cluster. This distance threshold is determined in proportion to the distance from the sensor. This is taking advantage of the general model of distance sensors, which tends to have sparser data distribution as the distance from the sensor increases.

The threshold range is calculated by:

\[r_{th} = R_0 + R_d * r_{origin}\]

where

- \(r_{th}\): Threashold range

- \(R_0, R_d\): Constant parameters

- \(r_{origin}\): Distance from the sensor for a range data.

## Step2: Rectangle search

In the second step, for each cluster calculated in the previous step, rectangular fittings will be applied. In this rectangular fitting, each cluster’s distance data is rotated at certain angle intervals. It is evaluated by one of the three evaluation functions below, then best angle parameter one is selected as the rectangle shape.

### 1. Rectangle Area Minimization criteria

This evaluation function calculates the area of the smallest rectangle that includes all the points, derived from the difference between the maximum and minimum values on the x-y axis for all distance data points. This allows for fitting a rectangle in a direction that encompasses as much of the smallest rectangular shape as possible.

### 2. Closeness criteria

This evaluation function uses the distances between the top and bottom vertices on the right side of the rectangle and each point in the distance data as evaluation values. If there are points on the rectangle edges, this evaluation value decreases.

### 3. Variance criteria

This evaluation function uses the squreed distances between the edges of the rectangle (horizontal and vertical) and each point. Calculating the squared error is the same as calculating the variance. The smaller this variance, the more it signifies that the points fit within the rectangle.

## API

class Mapping.rectangle_fitting.rectangle_fitting.LShapeFitting

  LShapeFitting class. You can use this class by initializing the class and changing the parameters, and then calling the fitting method.

  class Criteria(value)

    An enumeration.

  R0

    Range segmentation parameter [m]

  Rd

    Range segmentation parameter [m]

  criteria

    Fitting criteria parameter

  d_theta_deg_for_search

    Angle difference parameter [deg]

  fitting(ox, oy)

    Fitting L-shape model to object points

    Parameters

      - ox (x positions of range points from an object) –

      - oy (y positions of range points from an object) –

    Returns

      - rects (Fitting rectangles)

      - id_sets (id sets of each cluster)

  min_dist_of_closeness_criteria

    Minimum distance for closeness criteria parameter [m]

## References

- Efficient L-Shape Fitting for Vehicle Detection Using Laser Scanners - The Robotics Institute Carnegie Mellon University