A Robust Sphere Detection in a Realsense Point Cloud by USING Z-Score and RANSAC

Abstract

Three-dimensional vision cameras, such as RGB-D, use 3D point cloud to represent scenes. File formats as XYZ and PLY are commonly used to store 3D point information as raw data, this information does not contain further details, such as metadata or segmentation, for the different objects in the scene. Moreover, objects in the scene can be recognized in a posterior process and can be used for other purposes, such as camera calibration or scene segmentation. We are proposing a method to recognize a basketball in the scene using its known dimensions to fit a sphere formula. In the proposed cost function we search for three different points in the scene using RANSAC (Random Sample Consensus). Furthermore, taking into account the fixed basketball size, our method differentiates the sphere geometry from other objects in the scene, making our method robust in complex scenes. In a posterior step, the sphere center is fitted using z-score values eliminating outliers from the sphere. Results show our methodology converges in finding the basketball in the scene and the center precision improves using z-score, the proposed method obtains a significant improvement by reducing outliers in scenes with noise from 1.75 to 8.3 times when using RANSAC alone. Experiments show our method has advantages when comparing with novel deep learning method.

1. Introduction

RGB-D cameras have become a common sensor in the area of computer vision [1,2], and the popularity started with the Microsoft Kinect output on their Xbox video game console, when the camera could be used on a personal computer, scientists started taking advantage of it for research [3]. This type of camera produces, as data output, a color image and an depth image, both images describing the scene that is captured on camera. Currently, there are different brands and models of RGB-D cameras, and it is common for different cameras to offer different characteristics and limitations [4]. Recently, this type of camera has been embedded in mobile devices as in [5] popularizing the technology and use of 3D point clouds. Some formats for saving 3D point clouds are the XYZ format and the PLY format, where spatial information is included describing each point in three dimensions and sometimes metadata, such as color, can be included. These files can vary in size and density of points and these depend mostly on the camera that is being used to generate such files, thousands of points can be found in a scene captured in a single shot, and, generally, the complexity of the processing of this information is increased proportionally with the quality of the camera and of the information it produces, the greater the detail, the greater point density. Novel methods can be found that use this type of information to solve problems in different fields, for example, in 3D reconstruction [6,7], simultaneous localization and mapping (SLAM) as in [8,9], navigation [10], object detection [11], mapping urban buildings [12], recovering building geometries [13,14], indoor scene reconstruction [7,15], computer vision as face recognition [16], segmentation with background removal [17], recognition tasks in robotics using scene modeling [18], navigation in agriculture [19], pedestrian detection [11], augmented reality (AR) [20], computer-assisted surgery [21], 3D navigation for pedestrians and robots [22], ADAS (advanced driving assistance systems) [23], uncrewed aerial vehicles (UAVs) navigation [24], autonomous driving [25], body tracking [26], and RGB-D Multi-Camera Pose Estimation for 3D Reconstruction [27]. There are different sets of data or databases that are compiled and organized to facilitate the research paper using information from different scenarios represented in 3D point clouds [28]. All of the mentioned applications use precise calibration parameters. In order to match the layers of color and depth, it is necessary to obtain the orientation and relative position between both layers of information (color and depth).

Object detection in 3D point clouds is commonly used to initiate subsequent processes, such as calibration of cameras [29], point cloud registration [30], clustering of objects, and 3D point cloud compression, spheres, cones, and cylinders are used as geometric objects due to the simplicity of being represented and/or modeled mathematically [31,32]. Random Sample Consensus (RANSAC) is a stochastic method, which uses samples producing specific parameters to be adjusted in a cost function and then lists the best proposals or candidates for solution [33], RANSAC has shown promising results locating geometric primitives in point clouds in three dimensions [34], as such can be adapted in the search for specific parameters and can speed up the time due to its stochastic nature.

Sphere detection is used in camera calibration [31], many approaches convert 3D data to 2D images as in [32], then use circle and ellipse detection to find circumferences in the 2D data and later translate coordinates from 2D to 3D to locate the sphere object in the 3D data. Furthermore, there are classical options as Hough Voting still being used [35,36], and deep learning approaches as in [37,38] to locate objects with a circular shape, novel approaches using deep learning allow to locate objects in complex scenes. Some previous methods use RANSAC to find and fit the sphere, nevertheless unlike the method proposed in [32] a background subtraction is required to limit the search space. In the work of [34], to locate a sphere normal vectors are required and tolerances on the angles of the normals are used as a second acceptance criteria for the sphere to be accepted as a RANSAC candidate, in our proposal only tolerance is used on the distance as a criteria for acceptance as a RANSAC candidate.

A method to locate spheres with a known size directly in 3D point clouds is proposed, our experiments show advantages when using 3D data directly against converting the 3D point cloud to a 2D image and then use 2D methods. Some areas of application of the proposed method are RGB-D camera calibration, RGB-D Multi-Camera Pose Estimation, 3D registration, 3D navigation.

Our strategy shows the following features:

• Three-dimensional data are used directly by our method.
• Sphere size is used as a pattern to be searched.
• The proposed method allows to find the sphere in complex scenes with multiple objects and textures.
• No additional conversions are needed to detect the sphere.
• It is robust to outliers.

2. Materials and Methods

2.1. Computer Equipment, Programming Language

In this work, a personal computer with the following features, AMD Ryzen 5600x Processor with 6 cores, 12 processing threads, 3.7 GHz, 32 MB Cache L3, 3 MB Cache L2, 32 GB RAM, NVIDIA graphics card GeForce RTX 3060 TI with 8GB GDDR6 Memory, 4864 CUDA kernels, Ubuntu 20.04.2 LTS OS, Containers Docker 19.03.8, CUDA driver version 11.2. Python 3.9 as a programming language. Additionally, a MacBook air (Retina 13-inch, 2020) laptop was used with 1.1 GHz Quad-Core Intel Core i5 CPU, 8 GB RAM and integrated graphics card Intel Iris Plus Graphics 1536 MB, operating system Mac OS Big Sur 10.13 Beta and Python 2.9. All experiments will be run by exchanging the environment between the personal computer and the laptop, it was used Meshlab to visualize PLY files.

During all experiments, we use an Intel Realsense D435 with the specifications in

Table 1. Intel Realsense D435 [39].

Feature	Description
Operating range	∼0.11–10 m
Connection Interface	USB Type C
Dimensions	90 mm × 25 mm × 25 mm
Depth resolution	1280 × 720

.

2.2. RGB-D Camera

A camera was used during the capture of the scenes. RGB-D Intel RealsenseTM D435 with the following characteristics Table 1. The depth images produced by the camera in experiments contain 101,760 points in 3D for each capture of a scene. The scene in the depth image is represented in integers and has to be converted by a value of 0.001 that is configured from the factory in the RGB-D camera as depth unit. Integer values within the depth image were converted to meters using Equation (1).

$${Z\left(I_{ij}\right)}_{ij}=I_{ij}\times 0.001$$

(1)

Additionally, a projection is made from 2D coordinates to coordinates in 3D by the following Equation (2)

$$\begin{array}{c}\hfill {X\left(I_{ij}\right)}_{ij}=(i-c_x)/f_x\times 0.001\\ \hfill {Y\left(I_{ij}\right)}_{ij}=(i-c_y)/f_y\times 0.001\end{array}$$

(2)

Here, $c_x$ is the center of the sphere in the x-axes, $c_y$ is the center of the sphere in y-axes and $f_x$ is the focal length in x-axes and $f_y$ is the focal length in the y-axes, the 3D point cloud is represented with coordinates (x, y, z) and the dimensions are represented in meters with floating point numbers. The maximum and minimum value of depth depends directly of the scene captured and the characteristics of the RGB-D camera. Information contained in a ply file is shown in Figure 1 which is displayed through the Meshlab program, it is observed that all points in 3D are displayed in green and there is no clear distinction of the objects present in the scene, the structure of a bookcase is predominantly observed. In Figure 2, we can see more clearly the different layers of depth due to the representation in colors from blue to red with increasing distance from the RGB-D camera.

The shot of a scene by the camera is displayed RGB-D (Figure 1 and Figure 2). An attempt is made to capture objects at different distances in each experiment.

2.3. Model to Represent the Sphere with a Known Size

An equation is used to model a sphere where on its surface we find three different points $x_i,y_i,z_i$ with a common center or with coordinates $a,b,c$:

$$O=(a,b,c)$$

(3)

$$r^2={(x_i-a)}^2+{(y_i-b)}^2+{(z_i-c)}^2$$

(4)

here, r is the radius of the sphere. Expanding right side of Equation (4) for at least 2 different points:

$$\begin{array}{c}\hfill r^2={x_1}^2-2x_{1}a+a^2+{y_1}^2-2y_{1}b+b^2+{z_1}^2-2z_{1}c+c^2\\ \hfill r^2={x_2}^2-2x_{2}a+a^2+{y_2}^2-2y_{2}b+b^2+{z_2}^2-2z_{2}c+c^2\end{array}$$

(5)

Simplifying for two different points:

$$\begin{array}{c}{r}^2={x_1}^2-2x_{1}a+{\sout{a}}^2+{y_1}^2-2y_{1}b+{\sout{b}}^2+{z_1}^2-2z_{1}c+{\sout{c}}^2\\ r^2={x_2}^2-2x_{2}a+{\sout{a}}^2+{y_2}^2-2y_{2}b+{\sout{b}}^2+{z_2}^2-2z_{2}c+{\sout{c}}^2\end{array}$$

(6)

Then:

$$\begin{gathered} {x_1}^2-2x_{1}a+{y_1}^2-2y_{1}b+{z_1}^2-2z_{1}c={x_2}^2-2x_{2}a+{y_2}^2-2y_{2}b+{z_2}^2-2z_{2}c \\ {x_1}^2-{x_2}^2-2x_{1}a+2x_{2}a+{y_1}^2-{y_2}^2-2y_{1}b+2y_{2}b+{z_1}^2-{z_2}^2-2z_{1}c+2z_{2}c=0 \\ {x_1}^2-{x_2}^2+2a(x_2-x_1)+{y_1}^2-{y_2}^2+2b(y_2-y_1)+{z_1}^2-{z_2}^2+2c(z_2-z_1)=0 \end{gathered}$$

(7)

Expanding the Equation (4) for three different points:

$$\begin{gathered} r^2={(x_1-a)}^2+{(y_1-b)}^2+{(z_1-c)}^2 \\ {r}^2={(x_2-a)}^2+{(y_2-b)}^2+{(z_2-c)}^2 \\ {r}^2={(x_3-a)}^2+{(y_3-b)}^2+{(z_3-c)}^2 \end{gathered}$$

(8)

then in Equation (8) each equation equals r so match in the following order:

$$\begin{array}{c}\hfill {(x_1-x_c)}^2+{(y_1-y_c)}^2+{(z_1-z_c)}^2=\\ \hfill {(x_2-x_c)}^2+{(y_2-y_c)}^2+{(z_2-z_c)}^2\\ \hfill {(x_3-x_c)}^2+{(y_3-y_c)}^2+{(z_3-z_c)}^2=\\ \hfill {(x_1-x_c)}^2+{(y_1-y_c)}^2+{(z_1-z_c)}^2\\ \hfill {(x_3-x_c)}^2+{(y_3-y_c)}^2+{(z_3-z_c)}^2=\\ \hfill {(x_2-x_c)}^2+{(y_2-y_c)}^2+{(z_2-z_c)}^2\end{array}$$

(9)

The 3D Point Coordinates 1 = 3D Point Coordinates 2, 3D Point Coordinates 3 = 3D Point Coordinates 1, 3D Point coordinates 3 = 3D Point Coordinates 2, and using Equation (7) developing the system of Equation (9) we obtain:

$$\begin{array}{c}\hfill 2a(x_2-x_1)+2b(y_2-y_1)+2c(z_2-z_1)+{x_1}^2-{x_2}^2+{y_1}^2-{y_2}^2+{z_1}^2-{z_2}^2=0\\ \hfill 2a(x_3-x_1)+2b(y_3-y_1)+2c(z_3-z_1)+{x_1}^2-{x_3}^2+{y_1}^2-{y_3}^2+{z_1}^2-{z_3}^2=0\\ \hfill 2a(x_3-x_2)+2b(y_3-y_2)+2c(z_3-z_2)+{x_2}^2-{x_3}^2+{y_2}^2-{y_3}^2+{z_2}^2-{z_3}^2=0\end{array}$$

(10)

simplifying Equation (10) and rearranging in the form Ax = b we obtain:

$$\begin{array}{c}\left[\begin{array}{ccc}2\left(x_2-x_1\right)\hfill & 2\left(y_2-y_1\right)\hfill & 2\left(z_2-z_1\right)\hfill \\ 2\left(x_3-x_1\right)\hfill & 2\left(y_3-y_1\right)\hfill & 2\left(z_3-z_1\right)\hfill \\ 2\left(x_3-x_2\right)\hfill & 2\left(y_3-y_2\right)\hfill & 2\left(z_3-z_2\right)\hfill \end{array}\right]\left[\begin{array}{c}a\hfill \\ b\hfill \\ c\hfill \end{array}\right]\\ =\left[\begin{array}{c}{x}_2^2-x_1^2+y_2^2-y_1^2+z_2^2-z_1^2\hfill \\ x_3^2-x_1^2+y_3^2-y_1^2+z_3^2-z_1^2\hfill \\ x_3^2-x_2^2+y_3^2-y_2^2+z_3^2-z_2^2\hfill \end{array}\right]\end{array}$$

(11)

Then:

$$\begin{array}{c}\left[\begin{array}{ccc}\left(x_2-x_1\right)\hfill & \left(y_2-y_1\right)\hfill & \left(z_2-z_1\right)\hfill \\ \left(x_3-x_1\right)\hfill & \left(y_3-y_1\right)\hfill & \left(z_3-z_1\right)\hfill \\ \left(x_3-x_2\right)\hfill & \left(y_3-y_2\right)\hfill & \left(z_3-z_2\right)\hfill \end{array}\right]\left[\begin{array}{c}a\hfill \\ b\hfill \\ c\hfill \end{array}\right]\\ =1/2\left[\begin{array}{c}{x}_2^2-x_1^2+y_2^2-y_1^2+z_2^2-z_1^2\hfill \\ x_3^2-x_1^2+y_3^2-y_1^2+z_3^2-z_1^2\hfill \\ x_3^2-x_2^2+y_3^2-y_2^2+z_3^2-z_2^2\hfill \end{array}\right]\end{array}$$

(12)

the Equation (12) can be solved to calculate the radius by three different points on the surface of the sphere.

2.4. Z-Score

To remove outliers in the set of points that are considered as part of the sphere the punctuation is used Z [40], to remove values below a defined threshold from −1.5 and above 1.5.

$$z=\sum (X_i-\overline{X})/\sigma$$

(13)

where $X_i$ is the measured value, $\overline{X}$ is the average of the values and $\sigma$ is the standard deviation.

2.5. Basketball and RANSAC Method

In the algorithm shown in the flowchart (Figure 3), as a first step, three points are selected randomly from the 3D point cloud, we obtain the center with Equation (11) and later the radius with Equation (4), as step two, check that the radius is within a tolerance of $ϵ$ = 1 cm close to the radius of the ball of basketball with a radius of 12 cm. If it is within tolerance checks that the center exists in a list of candidate centers. If it exists, the points are added to the center of the list. If the center does not exist, a new center is added. along with its points on the surface of the sphere to the list. If a radius is not found within tolerance, check and update the stop condition which can be a limit of iterations, in the experiment a thousand iterations were used as a limit. If the stop condition is still not reached, three new candidates randomly and it starts over in the first step. If the stop condition is reached, iterates through all the points in the point cloud in 3D and check distances to registered centers, if centers are found within tolerance, each point evaluated is added to the list of whose center it corresponds.

Once the classification of the points to their centers is finished corresponding, the list is sorted and the center is selected with the greatest number of points and the least error with respect to the tolerance in the measure of the radius of the sphere. Subsequently, an adjustment of the center of the sphere is made, for this, it is used z-score or Z score, to eliminate outliers, eliminate data with Z-score less than −1.5 and greater tan 1.5, with the remaining values a barycenter is calculated and it is taken as the new center of the sphere, through which they are considered sphere points those points within the defined radius.

3. Experiments and Results

A standard size 7 basketball is used, with a circumference of approximately 35 cm and a radius of 12 cm as show in Figure 4. With a fixed radius, a tolerance of 1 cm and the RANSAC method can be integrated to adjust the system of Equations (11) by sampling three points in the 3D point cloud.

A scene with a relatively flat wall is selected to the bottom and a basketball is placed 25 cm from the realsense D435 camera, the image is captured in color or RGB (Red Green Blue, color image) as shown (Figure 4).

The depth of the same scene is captured by the realsense D435 camera, which is converted to a file PLY using Equations (1) and (2), the scene can be displayed in shades of color from blue to red as shown (Figure 5), and subsequently the PLY file is visualized with Meshlab (Figure 6).

The correct detection of the basketball is shown (Figure 7 and Figure 8) as a spherical geometry in a first experiment with good conditions in the scene where the soccer ball basketball is distinguished from the rest of the scene and is not occluded by other objects. The 3D points that belong to the surface of the ball are colored red and are distinguished from the other points in the scene.

The tolerance $ϵ$ defines the number of outliers at locations near the surface of the sphere. In this example, a thousand iterations were used to search for on the entire image per iteration, in each experiment different candidate solution proposals are generated as the center of the sphere that is sought, different solutions, because there are different points that satisfy the proposed mathematical model Equation (11) within tolerance established, however the candidate with the highest number of points and whose radius approaches with less error to the known measure of 12 cm, is the selected solution using the RANSAC method. In this first experiment, the different candidates that are generated belong to the same object, so the center is very similar in all proposals, however, the method converges to the winning center.

The adjustment of the points of the sphere is carried out by means of the Z-score Equation (13), of the points that turn out to belong to the sphere with the winning center, minor points are removed to −1.5 and greater than 1.5, which are considered as values outliers, these values were selected by means of a heuristic based on a lower RMSE type error (Root mean square error). A new center is calculated by a centroid with the remaining points. seen in color red the points discriminated as outliers (Figure 9) using the Z-score and the dots in blue as the values within the sphere of radius 12 cm from the new center.

In a second experiment, an image is generated with the Realsense D435 camera of a scene with greater complexity to the first experiment, in whose middle part, in the middle part of the scene there is a bookcase with various objects, showing a brown basketball on a tripod, which is sought by the proposed method. The scene of the second experiment is shown (Figure 10).

A depth image of the scene is generated (Figure 10), which is converted to a PLY file using Equations (1) and (2), the PLY file is visualized with Meshlab (Figure 11).

The correct detection of the basketball is shown (Figure 12) as a spherical geometry. In this image there are outliers in places close to the surface of the sphere as it can be parts of the scene that correspond to the tripod where the ball rests. In this example we used 10,000 iterations searching the entire image, in each experiment different candidate solution proposals as the center of the sphere that is sought, different solutions are found because there are points that satisfy the proposed mathematical model Equation (11) within the established tolerance, however in this experiment the candidate with the largest number of points and whose radius approaches with a smaller error the measure known 12 cm is the solution selected by the RANSAC method.

It is observed that false positives can be obtained if the tolerance is higher and if the scene is sampled without enough frequency or considering a space away from the dimensions of the actual diameter of the ball 24 cm, as in (Figure 13) where the incorrect detection of certain points that satisfy the model mathematical to represent the sphere are showed, but that nevertheless they do not belong to the geometry being sought.

A scene is captured by increasing the distance of the ball basketball towards the camera in a third experiment considering multiple levels of depth as seen in the color image (Figure 14).

A difference in depth is observed with respect to the second experiment (Figure 15).

The proposed method correctly detects the geometry searched in the scene (Figure 16) and the result (Figure 17), it is important to note that the number of solution candidates increases in scenes with greater complexity and variety of objects, however, RANSAC successfully discards false positives allowing to find the correct object.

It is observed in a close-up that the difference between the ball with the table is defined correctly (Figure 18).

Outliers are removed for center adjustment using the Z score from Equation (13) where for all points that are obtained until the selection of the best circle using RANSAC, its corresponding Z value is obtained as shown (Figure 19).

The Figure 20 shows the classification of outliers in red color after being evaluated by means of z-score.

Root Mean Square Error (RMSE) value is displayed of experiment one in meters (

Table 2. RMSE centers detected with RANSAC adjusted with Z score.

Scene and Z Threshold	RMSE RANSAC	RMSE RANSAC Center Adjusted Points	RMSE Barycenter Adjusted Points
E1 z 3	0.007343368	0.007343368	0.032156230
E1 z 2	0.007343368	0.007343368	0.020370757
E1 z 1.5	0.007343368	0.007343368	0.004612417
E2 z 1.5	0.366534813	0.357131966	0.041731429
E3 z 1.5	0.033177435	0.033539393	0.027763554

), which is used to select the threshold Z less than −1.5 and greater than 1.5, observes that by means of this threshold, an RMSE is obtained smaller in the comparison of the distances from the new center which was obtained by calculating the barycenter against the center distance obtained in a previous step only with RANSAC.

In order to compare with a state of the art method based in neural networks [38], we create a set of 200 2D images re-projecting 3D point cloud scenes to 2D images, these images containing two main types of scenes, the first one with a clean area and a flat wall in the background and the second type with a scene containing multiple objects and depths in the scene as shown in Figure 21. All images were masked manually to obtain cIOU values as in [41].

Mean Average Precision (mAP) [42] is used in

Table 3. Comparison with other methods.

Method	mAP	mAP.50cIOU	mAP.75cIOU
CircleNet-HG	0.491	0.843	0.512
SphereDetection (ours)	0.512	0.894	0.529

as a metric. To obtain cIOU values from the proposed method, the sphere center was re-projected to 2D and with the sphere radio the sphere center was reprojected to the left at same depth to compute a circle in the 2D re-projection.

4. Conclusions and Future Work

The proposed method uses the classic RANSAC algorithm and a mathematical model to obtain the radius and center of the sphere from three points that are on the surface of the sphere directly in a 3D point cloud, the defined size of the basketball is used as the objective value of our model and through a tolerance different solutions are sought randomly in. As shown in experiments, the proposed methodology converges and finds the correct object in the scene even when the complexity and variety of objects on stage are considerable. In the present work, the first sample is taken randomly from the totality of the depth images, and the remaining two samples are taken at a maximum distance of the diameter of the basketball, expediting the convergence of the method and reducing the search space.

Experiments showed advantages when using data in 3 dimensions against other methods that search for circumferences in a two-dimensional space.

The number of iterations used in the proposed method is directly related to the size and complexity of the depth image being processed. During our experiments, we observed that when processing less complex scenes, with easily distinguishable backgrounds and few objects, the number of iterations could be decreased.

In our experiments it is shown that using Z-Score the improvement is obtained by reducing outliers from 1.75 to 8.3 times when using RANSAC only in scenes with different complexity and noise characteristics.

The method provides opportunities for future work as the parallelization of the algorithm in the sampling stage, implementing heuristics to adjust tolerances versus noise and distance in the depth data, automatically adjust the number of iterations by analyzing the complexity of the scene and the number of points to process.