Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
| Fahad Alraddady Computer Engineering Department College of Computers and Information Technology, Taif University, Taif, Saudi Arabia. |
| Corresponding Author: Fahad Alraddady, E-mail: alraddady@tu.edu.sa |
| Related article at Pubmed, Scholar Google |
Visit for more related articles at Journal of Global Research in Computer Sciences
Data reduction tools are developed and evaluated using a data analysis framework. Simple and intelligent thinning algorithms are applied to both synthetic and real data and the thinned datasets are ingested into an analysis system. A major problem of data reduction is that certain types of camera or scanner produce vast amounts of data, the processing of which presents serious problems. Rather than process all of this data at every stage of the representation process, an alternative is to use a strategy in which the data is initially reduced, then a preprocessing can be completed without consuming a lot of time. This paper presents an algorithm for managing the amount of point data acquired by laser scanner. The proposed algorithm includes a method based on computing the surface normal which is fundamental in the most of reverse engineering algorithms. The normal vectors are calculated by fitting the best fit plane to the neighborhood. A point is assigned to normal and the angle between an arbitrary direction and the normal is obtained. The point data is subdivided into cells based on the angles, while the non-uniform cells are obtained. Thus, the amount of points can be reduced by sampling the representative points for each cell. Experimental results show that the proposed method has good results and appears to be quite stable even for large scale data reduction.
Keywords |
| Reverse engineering, median filtering, normal vectors, data reduction. |
INTRODUCTION |
| Data reduction allows more data sets to be stored in a given amount of disk or memory space. It also reduces the time required for images to be sent over the Internet or downloaded from Web pages. Furthermore, data reduction is useful because it helps reduce the consumption of expensive resources such as hard disk space or transmission bandwidth [1]. The selection of a data reduction algorithm depends mostly on criteria of achievable compression ratio and the quality of reconstructed images. Two fundamental components of reduction are redundancy and irrelevancy reduction. Redundancy reduction aims at removing duplication from the signal source (image/video). Irrelevancy reduction omits parts of the signal that will not be noticed by the signal receiver, namely the human visual system. In general, three types of redundancy can be identified: |
| 1- Spatial redundancy or correlation between neighboring pixel values. 2- Spectral redundancy or correlation between different color planes or spectral bands [1]. 3- Temporal redundancy or correlation between adjacent frames in a sequence of images (in video applications) [2]. |
| The focused of this paper is limited in phase (1) where the establishing connectivity between adjacent points, reducing redundancy and merging point clouds taken from multiple views. A major problem in this phase is that certain types of scanner produce vast amounts of data, the processing of which presents a serious problem. Rather than process all of this data at every stage of the reconstruction process, an alternative is to use a strategy in which the data is reduced and used to construct a model. The full set of data is only used to improve this initial model if necessary. The challenge in reducing the data is to maintain sufficient information from which to calculate the object reliably without distorting the surfaces or their boundaries. Being able to reduce such large data sets whilst maintaining the information and accuracy contained in the original data will be advantageous for surface reconstruction and hence for follow on activities, especially in the manufacturing process. |
| Recently, the researchers have been shown interest by data reduction algorithms to overcome the time consuming in data preprocessing. Aljahdali et al. [3] improved a data reduction method for reducing 3D points for reverse engineering. This technique is based on a discrete Gaussian image of the scanned points which is obtained by estimating surface normals and projecting them into a Gaussian sphere. The discrete Gaussian image is then used to partition the points into cells. In each cell, a reference point and its neighbors are used to determine the cell representative point and all other points are removed. The performance of the proposed method is illustrated using a range of point clouds scanned from typical engineering surfaces. Lazarus and Splitt [4] proposed thinning algorithms for applying to both synthetic and real data. As a precursor to real-data applications, the algorithms are applied to one- and two-dimensional synthetic datasets. Piotr et al. [5] found way of data reduction can be used with synthetic transmit aperture method (STA) and it bases on an assumption that a signal obtained from any pair of transducers is the same, no matter which transducer transmits and which receives. According to this postulate, nearly a half of the data can be ignored without image quality decrease. |
| Surprisingly, little work has been done to combine real data reduction and hold only the pre-processed data for further analysis, especially in 3D data sets. Such work is crucial importance since it is extremely difficult to work with dense data in reverse engineering processes. So the present paper introduces new idea to reduce dense data and applicable for all reverse engineering processes. It has advantages of accuracy and computation, where the most computation is the surface normal, which is necessary for all most reverse engineering applications. |
| This paper presents a fast algorithm for data reduction of the given 3D points. The proposed algorithm consists of three steps. In the first step, the neighborhood of the points is estimated, whereby the surface normal is obtained using planar fitting. In the second step, point data is subdivided into cells based on surface normal. The procedure in third step is used to reduce the data in each cell. |
| This paper is organized as follows: In section 2, the proposed algorithm is described including the neighborhood is computed, fitting the plane surface to neighborhood, normal vectors are estimated, partitioning the data into cells are presented and reducing 3D data reduction. To show the efficiency of the proposed method, some examples are presented in section 3. We conclude the paper in section 4. |
| 2. The Algorithm |
| The proposed algorithm is consists of three steps. The first step is pre-processing where the data is input, organized, and partially analyzed to prepare the remaining operations. Preprocessing includes data points, sorting, determination of a neighborhood for each point, and computation of an approximate normal vector to the surface at each point. In the second step, an initial partition of point data into cells is obtained. In each cell, we use the normal vectors assigned to the points. An arbitrary direction is selected and referred as a reference direction. The angles between the reference direction and the normal vectors are estimated, where the angles with smallest value and the biggest value are selected. If the value is greater than a prescribe value the cell is partitioned again. The procedure in third step is used to reduce the redundant data in each cell. |
| The method can be divided into the following steps: |
| - Neighborhood estimation |
| - Computing the plane surface to each neighbor |
| - Estimating normal vector |
| - Reducing 3D points. |
| 2.1 Neighborhood estimation |
| A neighborhood of a point consists of data point is from the original data set, which are “near” the given point. An ideal definition of neighborhood for the purpose of points reduction would be that a neighborhood includes only those data points that describe the surface at the given point but includes all points necessary for measurement of the variation of the surface around the given point. An ideal definition of neighborhood for the purpose of feature point extraction was presented in [6,7] that a neighborhood includes only those data points that describe the surface at the given point but includes all points necessary for measurement of the variation of the surface around the given point. A neighborhood is chosen for each point that includes all point within a given distance of the point in combination with a limit on the maximum number of points in a neighborhood. Here, we use the computation of the neighborhood that presented in Vanco’s paper, where this method obtains almost good results and works very fast. We select k to be 10 which sufficient to obtain faithful results. So , for every point its k-nearest neighbors are computed, which describe this small portion of the surface-in ideal case the neighbors are distributed regularly round the point. |
| 2.2 . Computing Planer Surface to Neighbor |
| Assume a point data in which we want to manage it consists of n -points. We have the neighborhood points of a point p x y z i k i i i i ( , , ), 1,2,.., , where k is the number of neighborhood and we want to fit the best plane to those points. Then the equation of the plane is: |
 |
 |
| 2.4 Point data partitioning |
| Let the set of points which we want to handle is put in an arbitrary array with x, y and z direction. We used a binary search data structure to subdivide the point data as in Fig.(1). The point data is subdivided into two cells, which, each cell can be subdivided into two cells if it is need. We refer to the partitioning stage as levels, so the set of points is partitioned based on âÃâÃâ levels, where level ,level ,..., level 0 1 are the level’s partitioning and 2 ,2 ,...., 2 0 1 are the corresponding cells number respectively. |
| Algorithm 1: |
| 1- j=0, i=1 2- Sort the points in A1 corresponding of xdirection in an array 3- Partition the data into two cells and put them in the sub-arrays A1 and A2 4- Go to algorithm 3 to check the data(i.e if the cell needs to partition again or not) 5- Sort the points in A1 corresponding of ydirection 6- Partition the points into two cells and put it into the sub-arrays B1 and B2 7- Go to algorithm 3 to check the data(i.e if the cell needs to partition again or not) 8- Sort the points in A1 corresponding of zdirection in an array 9- Partition the points into two cells and put it into the sub-arrays Ci and Ci+1 10- Goto 6 to select B1=B2, i=i+2; 11- Goto 6 to select B1=B2, i=i+2; 12- j=j+1. 13- Repeat the statements from 2-6 for each Ci until desired j. |
 |
| 2.5 3D point’s reduction |
 |
| the normal vectors are estimated, where the angles with smallest value min and the biggest value max are selected. |
| If the value | | max min is greater than a prescribe value , the cell is partitioned again. Otherwise the median angle is selected, where it is easy to find the corresponding normal, whereby the corresponding 3D points are chosen as the representative points of the cell. |
| Algorithm 3: |
| 1- j=1 |
| 2- Select the arbitrary reference direction |
 |
Experimental results |
| The proposed technique is experimented using different types of part surfaces and the results are discussed. It was tested with real data measured using laser scanner and simulated data. Before applying the reduction algorithms, the farther noise point from the initial point cloud is removed. These tests have shown, for surface normal computation that the best neighborhood size for point set with noise sampling is in the range of 10-20. If we used a bigger neighborhood size 20, the normal vectors on smooth surfaces was not estimated better than with k = 10. If the data contains noise or they consists of scan lines with big distances between scan lines and small distance within one scan line, the neighborhood size have to be enlarged to about k = 6. |
| Table (1) shows some results that were experimented on the proposed data reduction technique. We have fitted the planes, spheres, and cylinders to the data using the Least squares method that is presented at [10] pre and post applying the proposed method. The average of the distances (the error) between the surface and the points are computed after and before fitting, where the reduction degree is the number of passing the data to the proposed algorithm without modifying the thresholds. We have selected k 10 as the best neighborhood size for a point set. The parameter has been obtained automatically based on the part of shape. It varies from cell to another depending on the size of a cell. For that non-uniform cells in which the size of cells can be varied based on the part shape are created. After testing of many examples, we noted that the selection of the parameter to be 0.1 . We note that when this parameter is decreased, the number of output data points is extremely reduced. |
| Fig.(2a) shows the point cloud of a planar surface (it is part from mechanical object) and it consists of 1654 points. The points is fed to the proposed algorithm and the result is presented in Fig.(2b). Since the examples in Fig.(3a,4a) show the 1854 and 2676 points has obtain from two different cylinder parts. The proposed algorithm has been tested by those two parts. Fig(3b, 4b) shows the result after applying the algorithm to the point cloud of a cylinder surface. The data in Fig.(4b) has been passed to the algorithm again and the result is presented in Fig.(4c). In the last example, we have tested the proposed method by simulated data to show the applicability of the method. In Fig.(3b) the sphere data is generated by sphere equation and add 50 noise points to the data. The data is passed to the algorithm and the output result has been shown in Fig.(3b). The results show in table (1) that the fitted surface is better than that one before. For example, the cylinder segment (has 2676 points) is fed to our algorithm. We note, that it has 1900 points if the reduction degree is 1. The part with 1900 points is reduced again and the result is the part with 570 points (the reduction degree in this case is 2). However, in every reduction step a surface is fitted to the data point and the error is estimated. We noted that before reduction the error is 1.0094, after applying the algorithm to the data, the error became 0.00643. The output data is fed again to the algorithm, The data is fitted to the cylinder surface. Then the error became 0.00048. This shows that the propped method is very faithful to obtain accurate results while keeping quality point data. |
Conclusion |
| fast technique for data reduction is presented, where some experimental results of that technique are given to show the ability of the developed method. We have demonstrated that when surfaces are fitted to reduced points produced by the proposed technique, the fitting results are improved from those found by using the entire data point, even with quite large factors of data reduction. The proposed method overcomes the limitation of uniform grid [12] method by using the normal vectors assign to the points, which give information about part shape. Thus, all edges are preserved, and all differential properties can be estimated without introducing errors even with the noisy cells. Also, upon calculating the normal vectors of all points, a planar grid is generated. The size of a grid is defined automatically corresponding to the user threshold and grid size depends on the intended data reduction ratio for the given part shape. |
 |
| Table (1): Some data sets have been tested by surface fitting. |
 |
 |
References |
|