Geoinformatics FCE CTU 12, 2014 41 Denoising of Laser Scanning Data Using Wavelet Petr Jašek, Martin Štroner Czech Technical University in Prague, Faculty of Civil Engineering, Department of Special Geodesy, Thákurova 7, 16629 Praha 6, Czech Republic, E-mail: petr.jasek@fsv.cvut.cz, martin.stroner@fsv.cvut.cz Abstract Regarding the terrestrial laser scanning accuracy, one of the main problems is the noise in measured distance which is necessary for the spatial coordinates´ determination. In this paper the technique of using the wavelet transformation for the reduction of the noise in the laser scanning data is described. This method of filtration is made in “post processing” and due to this fact any changes in the measuring procedure in the field shouldn´t be done. The creation of the regular matrix is needed to apply image processing. This matrix then makes the range image. In the paper real and simulated efficiency tests of wavelet transformation, the final summary and advantages or disadvantages of this method are introduced. Key words: Laser scanning, noise reduction, wavelet transform, points 1. Introduction 3D terrestrial scanning based on the spatial polar method (frequently also called laser scanning) is a surveying method of the determination of spatial coordinates of points, usually within one scan in a regular angular raster. The horizontal direction, the zenith angle and the slope length are always measured. The coordinates are identified in a local system defined by the start, i.e. the reference point of the scanner and the basic (zero) horizontal direction identifying the direction of the positive X axis. Numerous scanning systems work at any arbitrary screen angle, therefore, the actual XY axis plane is not necessarily horizontal. A significant characteristic of the scanning process is a high measurement velocity and also non-selectivity of point sampling. The measurement accuracy may be characterised by standard deviations of the measurement of the above-mentioned quantities (for more facts about 3D terrestrial scanning see [1]).In commonly performed surveying measurements requiring higher accuracy than the accuracy corresponding to one single measurement, the number of repeated measurements may commonly be increased to obtain more accurate results by their arithmetic mean, or the same may also be achieved by the measurement of redundant quantities, and the accuracy is then improved by adjustment. In 3D scanning, on the contrary, this is normally not possible (with the exception of some instruments by the Trimble Company, e.g. the GS 200 type [2]; or by using the ScanAverager programme [3] for repeatedly scanned data from special selected instruments). The accuracy of measured lengths is usually one of the factors limiting the achievable accuracy of measurement results in multi- purpose 3D scanners, in continuous surfaces, however, this accuracy may be improved by eliminating the noise (random errors) based on the properties of neighbouring points. 2. Description of Wavelet Transform Processing Algorithm Wavelet transform is an integral transformation that allows obtaining time-frequency description of the signal. It is possible to use it for data decorrelation, decomposition of the signal into independent building blocks. JAŠEK, P. – ŠTRONER, M.: DENOISING OF LASER SCANNING DATA USING WAVELET Geoinformatics FCE CTU 12, 2014 42 0,, 1 )(, ≠∈� � � � � � − = sRs s t s t s τ τ ψψ τ , (1) where ψ is the mother wavelet, s is scale changing the width of the mother wavelet (dilatation), τ is location parameter, changing the location of the wavelet in the timeline (translation). The whole mathematical principle and precise description can be found in [4]. For denoising is used discrete wavelet transform (DWT). For the discrete wavelet transformation is most appropriate to use the dyadic sampling, where an orthonormal basis is created with use of suitable wavelet Ψ. Zkpks pp ∈== ,2,2 τ (2) and therefore �� � � �� � � − = p p p pk kt t 2 2 2 1 )(, ψψ , (3) where p is scale, k is location. Chosen wavelet allows nonredundant signal decomposition, so- called multiresolution analysis, due to the orthogonality. 3. Preparation of data before denoising For our application discrete wavelet transform was used. The main idea of application of wavelet transform used for elimination of distance noise in scan is to transfer obtained coordinates X, Y, Z to original polar coordinates �, �, d. For application of image processing it is necessary to create a regular matrix from the data that will show range image. Every measured distance have precisely determined position in the matrix and describes value of pixel in image. )],();,();,([)],();,();,([),( mndmnmnmnZmnYmnXmnP ξϕ�= (4) Figure 1: Create of range image Application of the wavelet transform was done after creating the range image in software Matlab R2011b. Parent family of orthonormal wavelets daubechies [5] were used. Use of daubechies wave was based on previous testing. JAŠEK, P. – ŠTRONER, M.: DENOISING OF LASER SCANNING DATA USING WAVELET Geoinformatics FCE CTU 12, 2014 43 4. The Reference Method - Denoising by Near Points Surface Fitting The method is based on surface fitting by plane and polynomial surfaces of 2nd, 3rd and 4th degree. The processing involves a gradual choice of a selected number of the nearest points for each point of a scan, a selected surface is interleaved with them and by the elongation or shortening of a beam with a given horizontal direction and the zenith angle onto the intersection with the surface a new (smoothed) position of the points is obtained. In spite of being always obtained in a certain order during the measurement, scanning data do not preserve this arrangement after their export, therefore, the procedure chosen for the searching of the neighborhood of a point in a large point cloud (hundreds of thousands to millions of points) was the conversion of the problem of searching the neighborhood in space (3D) into searching on a plane (2D); to this end, an algorithm was designed which is based on the application of coordinates recalculated into slope lengths, horizontal directions and zenith angles in the local coordinate system of the scanner. To make this procedure usable, untransformed data must be smoothed, to acquire a regular spaced matrix of points. A full description was given in [6]. 5. Testing the Application of Smoothing (Denoising) Methods In addition to real scan a virtual flawless scans of spherical and plane surfaces were created for testing of new methods of denoising. These scans were decomposed into components �, �, d. The distance component was modified by artificial noise. The noise had a normal distribution with standard deviation 2 mm. Re-scanned coordinates were calculated from lengths including the noise and then were denoised using above described methods. Two criteria were selected for evaluating the success of these methods: - Using a standard deviation of the differential model against flawless source - Using a standard deviation of fit by sphere/plane - Number of the triangles of the TIN model 5.1 Virtual scan - sphere Figure 2: Differentials models a) Scan with noise, b) Denoised wavelet db6, c) Second order Chebyshev - LSM, d) Third order Chebyshev - LSM, e) Fourth order Chebyshev - LSM, f) Plane – LSM JAŠEK, P. – ŠTRONER, M.: DENOISING OF LASER SCANNING DATA USING WAVELET Geoinformatics FCE CTU 12, 2014 44 Table 1: Achieved accuracy - virtual scan of sphere �� Standard deviation of the fit [mm] Number of triangles Std. deviation of the model [mm] Virtual scan 0,0 7 003 Scan with noise 1,4 5 061 1,2 Wavelet db6 0,4 7 283 0,4 Second order Chebyshev 0,6 7 247 0,5 Third order Chebyshev 0,6 7 204 0,5 Fourth order Chebyshev 0,9 6 624 0,7 Plane 0,3 7 321 0,3 5.2 Virtual scan – plane Figure 3: Differentials models a) Scan with noise, b) Denoised wavelet db6, c) Second order Chebyshev - LSM, d) Third order Chebyshev - LSM, e) Fourth order Chebyshev - LSM, f) Plane – LSM Table 2: Achieved accuracy - virtual scan of plane Standard deviation of the fit [mm] Number of triangles Std. deviation of the model [mm] Virtual scan 0,0 18 049 Scan with noise 1,9 14 050 1,6 Wavelet db6 0,5 17 906 0,5 Second order Chebyshev 0,8 17 817 0,7 Third order Chebyshev 0,8 17 725 0,7 Fourth order Chebyshev 1,3 17 274 1,0 Plane 0,4 17 927 0,4 5.3 Real scan Quality of denoising of an object, which was cut out from sculpture of David, was assessed according to the number of created triangles and the visual quality of the resulting triangular JAŠEK, P. – ŠTRONER, M.: DENOISING OF LASER SCANNING DATA USING WAVELET Geoinformatics FCE CTU 12, 2014 45 model. Improvement in the quality of triangular network is visible after the methods of denoising are applied. Real scan was obtained by measuring the 3D scanner Leica HDS 3000. The best results were obtained by using wavelet transform and second order of Chebyshev´s polynomial. When higher orders or number of iterations of wavelet transform were applied, the shape of real object was repressed. When the method of denoising by fitting the plane was used, the original object got degraded. Figure 4: Triangular networks a) Scanned object b) Real scan, c) Averaged scan from 5 scans, d) Denoised wavelet db6, e) Second order Chebyshev - LSM, f) Third order Chebyshev - LSM, g) Fourth order Chebyshev - LSM, h) Plane – LSM Table 3: Achieved accuracy - real scan of sculpture (number of triangles of network) Real scan Wavelet db6 Second order Chebyshev Third order Chebyshev Fourth order Chebyshev Plane 15609 18958 19009 18922 18525 19066 JAŠEK, P. – ŠTRONER, M.: DENOISING OF LASER SCANNING DATA USING WAVELET Geoinformatics FCE CTU 12, 2014 46 6. Influence of the Scanning Resolution and Size of the Standard Deviation of the Distance on the Success Rate of the Denoising To test of the influence of the scanning resolution and of the standard deviation of the distance there was created four virtual point clouds of the sphere (diameter 0.6 m) with resolution of the 2 mm x 2 mm, 4 mm x 4 mm, 6 mm x 6 mm and 10 mm x 10 mm. XYZ coordinates were decomposed to �, �, d the same way as in previous case. Distance d was then contaminated by the normal distribution noise with standard deviation 2 mm and 4 mm. As can be seen in Figure 5, resolution of the scan do not influences the success rate of the denoising too much. Quite more important parameter is the standard deviation of the distance. There can be also seen, that the best results are being achieved by using of the wavelet transform denoising method and by the plane fitting denoising method. Figure 5: Graph of standard deviation of the fit sphere – noise 2 mm / 4 mm 7. Conclusion Testing of proposed noise filtering methods, in the measured distance, were performed on three surfaces (sphere, plane and continuous part from sculpture of David). The first two testing surfaces were created virtually as flawless surfaces. Then the artificial noise was added. Improvement in all of the proposed solutions of denoising is visible from obtained results. It can be concluded that the best results mathematic surfaces were achieved by denoising using wavelet transform and a fitting plane. For continuous structures very similar results are achieved by using wavelet transform and fitting by the second order of Chebyshev´s polynomials. It is clearly evident that the benefits of new filtration process led to the suppression of the noise of measured distance. Therefore the resulting models of scanned objects can be more accurate and credible. Acknowledgements The article was written with support of the internal grant of Czech Technical University in Prague SGS14 “Optimization of acquisition and processing of 3D data for purpose of engineering surveying“. References [1] ŠTRONER, Martin and POSPÍŠIL, Ji�í. Terestrické skenovací systémy: Vyd. 1. Praha: eské vysoké u�ení technické v Praze, 2008, 353 s., ISBN 978-80-01-04141-3. [2] TRIMBLE,“Trimble GS Series 3D Scanner,” Trimble, 2005, (5 March 2013). JAŠEK, P. – ŠTRONER, M.: DENOISING OF LASER SCANNING DATA USING WAVELET Geoinformatics FCE CTU 12, 2014 47 [3] ŠTRONER, Martin., “Projekt ScanAverager v2.4.1,” Dpt. of Special Geodesy, 2012, http://k154.fsv.cvut.cz/~stroner/ScanAverager_v2/index.html (5 March 2013). [4] ADDISON, Paul S. The illustrated wavelet transform handbook: introductory theory and applications in science, engineering, medicine and finance. New York: Taylor, c2002. ISBN 07-503-0692-0. [5] DAUBECHIES, Ingrid. Ten Lectures on Wavelets. Philadelphia, Pennsylvania : Society for Industrial and Applied Mathematics, 1992. xix, 357 s. (CBMS-NSF regional conference series in applied mathematics; sv. 61) ISBN 0898712742 [6] SMÍTKA, Václav and ŠTRONER, Martin. 3d Scanner Point Cloud Denoising By Near Points Surface Fitting. In: Videometrics, Range Imaging and Applications XII; and Automated Visual Inspection. Bellingham (state Washington): SPIE, 2013, vol. 1. ISBN 978-0-8194-9607-2.