<figure><img src="image_1.png" /></figure>

HAL
open science

# Removing Stray Noise Quickly from Point Cloud Data Based on Sheep Model

Heru Xue, Xinhua Jiang, Yanqing Zhou, Liyan Wang, Chunlan Wang

► To cite this version:

Heru Xue, Xinhua Jiang, Yanqing Zhou, Liyan Wang, Chunlan Wang. Removing Stray Noise Quickly from Point Cloud Data Based on Sheep Model. 10th International Conference on Computer and Computing Technologies in Agriculture (CCTA), Oct 2016, Dongying, China. pp.435-441, 10.1007/978-3-030-06155-5_44. http://02179987

HAL Id: hal-02179987

https://inria.hal.science/hal-02179987

Submitted on 12 Jul 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Removing Stray Noise Quickly from Point Cloud Data
Based on Sheep Model

Chunlan Wang<sup>1</sup>, Heru Xue<sup>1(✉)</sup>, Xinhua Jiang<sup>1</sup>, Yanqing Zhou<sup>1</sup>, Liyan Wang<sup>1</sup>

¹College of Computer and Information Engineering,Inner Mongolia Agricultural University
Hohht,China

wangchunlan990@163.com, {xuehr,jiangxh}@imau.edu.cn,
hellozhoyanqing@126.com, m18347541602@163.com,

**Abstract.** The noise data could be produced when we scanned the object by Handy 3D scanner due to human factors, the target surface and the instrument itself factors etc. Noised point cloud data could seriously affect the precision and efficiency of three-dimensional reconstruction in late stage. To this problem, we used the sheep body's three-dimensional point cloud data and changed the algorithm of k-nearest neighbors and presented method that combined the k-nearest neighbor denoising and median filtering. Firstly, the improved k-nearest neighbors algorithm could establish topology relationship fast, identify and delete some noise data; then, using the filter method processed the point cloud data and all noise data could be identified and deleted. The experimental results show that the method we presented can eliminate the stray noise from the point cloud data quickly and accurately and keep ideal target.

**Keywords:** scattered point cloud; k-nearest neighbor point; median filtering; outliers; noise data

# 1 Introduction

With the development of reverse engineering, the point cloud data model in 3d solid modeling is used more and more widely, and the surface data acquisition method has been diversified [1-2]. In recent years, the non-contact 3d laser scanning technology is popular in the animal husbandry and aquaculture industry, because of its sampling rate fast, high precision and high resolution [3], and easy operation, etc. By 3d laser scanner to obtain the animal shape data and realize three-dimensional reconstruction and measurement, is a hot spot in the present about the welfare animals [4]. As a result, we based on sheep body three-dimensional point cloud data to test noise point quickly remove from the group, and help to further research the three-dimensional curved surface reconstruction and features and quantity.

The point cloud data obtained by 3D scanner is disorder and scattered and the data must include some noisy data. In the process of scanning, due to the material of the object, the error of the measurement system itself, the environment factors and measurement of human factors such jitter, could produce the stray noise. The stray noise can seriously affect the feature extraction, feature matching, and the
reconstruction of the surface[5]. Therefore, the people's research focus is removing the noise from the point cloud data. For the ordered point cloud data or partially, people usually with the aid of image denoising methods to realize noise removing. The common methods include wiener filtering, least squares filtering and Gaussian filtering, tec. For disorderly scattered point cloud denoising, the scholars have put forward the Laplacian operator, mean curvature flow, moving least quadric method[6-7] to establish the space between the point cloud topology structure. The technology used common is looking for scattered data's k-nearest neighbour. In this paper presents looking for k-nearest neighbour point in two-dimensional and compared with the traditional k-nearest neighbor methods[8-10], the amount of calculation and searching efficiency, the accuracy are improvement. Meanwhile, combined with the median filtering algorithm can accurately identify and remove outliers.

# 2 K-nearest Neighbor Searching of Point Cloud Data

## 2.1 Rasterize Scattered Point Cloud Data

Hypothesis the scattered point cloud set C={p1,p2,...,pn}, and n is the total number of the point cloud scanned by the 3D scanner. Every point contains its properties for 3D coordinate. We can get the coordinates X,Y and Z by imported point cloud data files, and deposit it to the three dimensional array respectively. In the array we can find maximum: max_x, max_y, max_z and min_x, min_y, min_z in the X, Y, Z direction[11-12]. According to the extreme value of the direction can get a minimum bounding box that parallels to the axis and contains all point cloud set, then set cell_size length of the grid according to the demand. Finally, we can find out the grid number on the each direction of the bounding box:nx,ny,nz.

$$n_x = \text{fix}((\max_x - \min_x) / \text{cell_size}) + 1 \quad (1)$$

$$n_y = \text{fix}((\max_y - \min_y) / \text{cell_size}) + 1 \quad (2)$$

$$n_z = \text{fix}((\max_z - \min_z) / \text{cell_size}) + 1 \quad (3)$$

## 2.2 Searching of K-neighbor Points

Rasterized scattered point cloud data and counting the index number of each point in the sub cube and find out each small cube contains the number of points at same time. Hypothesis the point Pi's three-dimensional coordinate is: xi, yi, zi, $I \in \{1, 2,..., n\}$, then the current point in a cube for index number is:

$$\text{id}_{x_i} = \text{fix}((x_i - x_{\text{min}}) / \text{cell\_size}) + 1 \quad (4)$$

$$\text{id}_{y_i} = \text{fix}((y_i - y_{\text{min}}) / \text{cell\_size}) + 1 \quad (5)$$

$$\text{id}_{z_i} = \text{fix}((z_i - z_{\text{min}}) / \text{cell\_size}) + 1 \quad (6)$$

Firstly, we need create an array to record the total number within each grid point and each point of the serial number. Then when we want to find the points' k-neighbor of pi, we could calculate the cube the pi lives and count points total number n in the cube or adjacent sub cube. To calculate Euclidean distance between the current point with the else, and order the distance from small to large and the former k distance data is
the k-neighbor points of pi.

In the process of practical application, we may find that such problems, the establishment of the spatial topology relationship of scattered point cloud, as the change of target shape, the number of small grid will become very large. When looking for a point k-neighbor points, and if the cube the point located within containing less than set the number of neighbor points k, then it must be extended to the point where the son of the cube in the adjacent grid search, so we need look for at least 26 cubes and Which may also contain a lot of empty cubes. As a result, we think the method in computing speed and search efficiency and eliminate noise from the group can be improved.

# 3 Algorithm Design

## 3.1 Improved k-neighbor Search Algorithm

Algorithm in this paper, according to get to the point of data attributes for point 3D coordinate characteristics, we proposed to scattered point cloud in two-dimensional plane projection method to find k-neighbor points, so you can find it in the rectangular or its adjacent rectangles. And the total number of rectangles you need to look for just have 9, compared with 27 in the space grid, as shown in figure 1, figure 2, and the amount of calculation reduced significantly and the search efficiency has greatly improved. Then process the point cloud data through the image median filtering method, which can realize the scattered points in the cloud all stray noise removal.

<figure><img src="image_3.png" /><figcaption>Fig. 1. k-neighbor search area</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2. The number in the grid points</figcaption></figure>
The main implementation steps:

Step 1 According to the distribution of noise, obtained two-dimensional layout (x, y), (x, z) or (y, z);

Step2 meshing scattered point cloud data sets to the two-dimensional;

Step3 To calculate the k-neighbor of each point in the point cloud and if the current point has not enough neighbors in rectangular and its adjacent rectangular, we can determine it is isolated noise points and directly deleted;

Step4 Strives for the average distance $\bar{d}$ between the neighboring points and setting the threshold value of D, if $\bar{d} < D$, then think the pi is not the noise points and maintained, otherwise, determine the pi is noise points and delete;

$$ \bar{d} = \frac{1}{k} \sum_{j \in K(p_i)} \| p_i - p_j \| \quad (7) $$

## 3.2 Median Filtering Searching of K-neighbor Points

Using the k - nearest neighbor search can remove isolated from the group of noise point in scattered point cloud data or a small number of massive point set to remove noise from the group, and there are still some points more big block noise point set cannot be identified from the group. In plane projection point cloud image, we can observe the difference between larger stray noise point set with the principal part of the distribution of point cloud coordinates, so using median filter can be block from the larger group of noise points set quickly identify and delete.

Step5 according to block the distribution of the noise from the group point set, the plan of the point cloud can be divided into rectangles along to x or y direction, then solve p_mid that the median values of coordinates of the points; Step6 setting a reasonable threshold H and comparison points pi's abs (y (I) - p_mid) and threshold H, and if beyond the threshold, the point pi will be removed from the group point;

## 4 Experimental Results and Analysis

In this paper, the experimental cloud data comes from the sheep model and we get it in the laboratory by the Handy Scan 3D laser scanner, and the algorithm implement in the R2011b MATLAB programming environment.
<figure><img src="image_5.png" /><figcaption>Fig. 3. original point cloud data</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 4. point cloud data projected onto a plane</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 5. k - nearest neighbor search denoising</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 6. median filtering de-noising</figcaption></figure>
Putting the point cloud data into the MATLAB, we can get the result like figure 3 and it is not difficult to find out that there many stray noise data. Figure 4 is the two-dimensional through the coordinate of the x, y. Then use the method that the improved k-neighbor research we can get the figure 5, and in picture we can see the isolated noise point or part of the small block noise can be identified to delete, and a small number of relatively intensive noise point set of outliers is not identified. For this kind of relatively intensive noise point set from the group, we use median filter idea for processing, the result diagram as shown in figure 6, we may discover the stray noise in point cloud data point is to identify and eliminate completely.

<figure><img src="image_9.png" /><figcaption>Fig. 7. The figure 8 stray noise kicked out results</figcaption></figure>

The final result is shown in figure 7, as we can see the stray noise in the point cloud
data has been deleted and the picture a and b are the display from different
perspectives in three-dimensional.

5 Conclusion

This paper takes the sheep body point cloud data for experimental basis, and put
forward the method that the point cloud data in two-dimensional plane projection to
realize the measuring point k - nearest neighbor search. Compared to the old space
search, it can reduce the amount of calculation data, reduce the memory footprint and
improve the efficiency of search. Then combined with the median filtering algorithm,
can well identify distribution space discrete isolated noise in point cloud data points
and the massive noise point cloud data. Point in two-dimensional plane of k - nearest
neighbor search method of median filter can remove the noise from the group quickly ,
and it also can be used for mass point cloud data.

Acknowledgment

This work was partially supported by the National Natural Science Foundation of
China(No.61461041).

References

1. An Yanyan, Yang Qiuxiang, Feng Xinyue et al. Improved algorithm for finding k nearest neighbors of point cloud data [J]. Journal of Computer Engineering and Design, 2014,12:4228-4232(2014).

2. Wang Yong, Tang Jing, Rao Qinfei et al. A new fast denoising algorithm for scattered point cloud [J]. Journal of Computer Applications and Software, 07:74-78(2015).

3. Xu Peng, Hui Zhenyang. Based on MATLAB point cloud noise eliminating algorithm research[A]. In Guizhou province society for rock mechanics and engineering academic
4. essays in 2014[C]. The rock mechanics and engineering society: Guizhou province, 2014:4(2014).

5. Liu Tonghai, Teng Gunghui, Zhang Shengnan et al. Get surface three-dimensional reconstruction based on point cloud data and applications[J]. Transactions of The Chinese Society of Agricultural Machinery, 06:291-295(2014).

6. Zhang Qiaoying, Chen Hao, Zhu Shuang et al. Application of density-based clustering algorithms in noise removing of continuous distributed point clouds [J]. Journal of Geospatial Information, 06:101-104+2+1(2011).

7. Tang Jing. Research on point cloud data processing technology in 3D Reconstruction [D]. Chongqing University of Technology (2015).

8. Zhang Yufeng. Denoising and detection of point cloud of three-dimensional data [D]. Nanjing University of Information Science & Technology (2014).

9. Zhang Yi, Liu Xumin, Sui Ying et al. Research and improvement of denoising method based on k-neighbors[J]. Journal of Computer Applications, 2004, 27(1): 2199-2212.

10. Wu Lijuan, Zheng Mian, Zhang Caiming. Algorithm for fast searching of k-nerest neighbors in cloud points [J]. Journal of Chinese Mini-Micro Computer Systems, 2001, 7(1): 7-14.

11. Ma Changsheng, Jiang Xiaofeng, Qiang Hequn. Algorithm for searching k-nearest neighbors of scattered-point cloud data [J]. Journal of Microelectronics and computer, 2007, 12(2): 206-219.

12. Liu Xiaodong, Liu Guorong, Wang Ying et al. K-neighbor searcing of surface reconstruction from scattered points [J]. Journal of Microelectronics and computer, 2004, 23-26+30(2006).

13. Wang Lihui. Study on Data Processing Technology of 3D Cloud Point[D]. Beijing Jiaotong University(2001).