# Staircase Detection, Characterization and Approach Pipeline for Search and Rescue Robots
## 2 Materials and Methods
### Staircase Plane Extraction and Characterization  
Using the bounding box obtained during the detection step, a segmentation and characterization algorithm is applied to the ROI of the organized point cloud to extract the planes corresponding to riser and calculate the distance and the orientation with respect to the camera's reference frame (shown in Figure 2). Taking into account the fact that a bounding box may contain background information and other objects (such as handrails), we implement a ROI extraction algorithm to eliminate points that do not belong to the staircase's thread and riser. A simple but efficient implementation is to shrink the width of the bounding box by a scaling factor \(BB_{f}\) that varies linearly with the distance to the staircase. The coefficients of the linear function that determines the scaling factor were obtained experimentally and must be changed for each different camera. To obtain the linear function that determines the value of the scaling factor, we first place the robot at a distance \(d_{1}\) from the staircase and vary the size of detected bounding box by a factor \(BB_{f1}\) until its size is equal to the width of the first stair riser. Afterwards, we position the robot at a distance \(d_{2}<d_{1}\) and perform the same steps to obtain a factor \(BB_{f2}\). Finally, we obtain the function of the line that passes through the points \((d_{1},BB_{f1})\) and \((d_{2},BB_{f2})\). By doing this we can determine the scaling factor \(BB_{f}\) for different distances from the staircase. This procedure is simple and more than two points can be used by fitting a line through them using linear regression. To segment the staircase's risers, we begin by applying a well known region growing segmentation algorithm [28] to the point cloud corresponding to the detected staircase. This algorithm consists of two main steps, normal estimation and region growing. The normal estimation algorithm fits a plane, using least squares, through the \(k\) nearest neighbors of each point in the point cloud and determines the plane normal parameters. By using least squares, the algorithm is able to determine areas of high curvature using the residuals of plane fitting. The region growing step uses the normals and the curvature, along with local connectivity and surface smoothness constraints, to cluster points belonging to the same region. Once the input point cloud has been segmented into smooth regions, we iterate through each region to find its centroid and a best fitting plane using the RANSAC algorithm [29]. By doing this last step, the coefficients corresponding to the Hessian Normal Form defined by \(ax+by+cz+d=0\) and the location of the centroid with respect to the cameras's reference frame are obtained. With the regions obtained and the planes fitted to each region we apply a clustering algorithm to obtain the points corresponding to the staircase's riser. The clustering takes into account three constraints:  
* The angle between planes fitted to each region. Figure 2: Reference frame used to calculate the staircase parameters. The vertical distance between the centroid of each region. * The lateral distance between the centroid of each region. The algorithm uses the region centroids (represented as a point cloud) \(\{P_{c}\}\), the coefficients of each plane normal \(\{N\}\), the clusters corresponding to each smooth region \(\{C_{p}\}\) and the total directions, from the initial seed, it will search for \(D_{total}\) as inputs and outputs new clusters corresponding to each staircase riser \(\{C_{r}\}\). To do this, we start by using the camera's reference frame origin as a seed and find the \(k\) nearest neighbors using a neighbor finding function \(\Omega\) that only considers the points available in \(\{P_{c}\}\). For each neighbor, we calculate the angle between the planes corresponding to each centroid and the vertical and horizontal distance between them.