We present a novel technique for 3D point cloud simplification — the so-called fractal bubble algorithm — to minimize the computational time and overall storage space. The proposed fractal bubble algorithm generates 2D elastic bubbles and copies of themselves through 2D data sets representing planar geometric contours. Each of the bubbles, as it grows, is made to select a single point of its first contact, and all the selected points become the simplified set of points. The fractal bubble algorithm is repeatedly applied to the simplification of planar slices of general 3D point clouds corresponding to 3D geometric objects, leading to the global simplification of 3D point clouds. The benefits of the algorithm are: first the algorithm is computationally light and memory efficient, second it is simple to implement and inherently allows the organized selection of the points of contact and finally it enables us to simplify the point cloud data through a multi-scale fashion by varying a set of user-controlled algorithm parameters. Numerical results verify the effectiveness of the proposed algorithm.
WöhlerC., 3D Computer Vision: Efficient Methods and Applications, 2nd Ed, Springer, Springer: London, UK, 2013.
2.
BoschéF., ForsterA. and ValeroE., 3DSurveyingTechnologies and Applications: Point Clouds and Beyond, Technical report, Heriot-Watt University, UK, 2015.
3.
Lyons-BaralJ. and KemenyJ., Applications of point cloud technology in geomechanical characterization, analysis and predictive modeling, Mining Engineering68(5) (2016), 18–29.
4.
KumarA., JainP.K. and PathakP.M., Industrial application of point cloud/STL data for reverse engineering, DAAAM International Scientific Book, 2012; Chapter 38.
5.
AlexaM., BehrJ., Cohen-OrD., FleishmanS., LevinD. and SilvaC.T., Point set surfaces, In Proceedings of the IEEE Visualization, California, USA, 21 - 26 October 2001; pp. 21–28.
6.
DuX., YinB. and KongD., Adaptive Out-of-Core Simplification of Large Point Clouds, In Proceedings of the IEEE International Conference on Multimedia and Expo, Beijing, China, 2-5 July 2007; pp. 1439–1442.
7.
PaulyM. and GrossM., Spectral processing of point-sampled geometry, In Proceedings of the annual conference on Computer graphics and interactive techniques, New York, USA, 01 August 2001; pp. 379–386.
8.
MoenningC. and DodgsonN.A., Intrinsic point cloud simplification, In Proceedings of the International Conference on Computer Graphics and Vision, Moscow, Russia, 6-10 September 2004.
9.
SongH. and FengH.Y., A global clustering approach to point cloud simplification with a specified data reduction ratio, Computer-Aided Design40(3) (2008), 281–292.
10.
KolliosG., GunopulosD., KoudasN. and BerchtoldS., Efficient biased sampling for approximate clustering and outlier detection in large data sets, IEEE Transactions on Knowledge and Data Engineering15(5) (2003), 1170–1187.
11.
BoissonnatJ.D. and CazalsF., Coarse-to-ne surface simplification with geometric guarantees, Computer Graphics Forum20(3) (2001), 490–499.
12.
SongH. and FengH.Y., A progressive point cloud simplification algorithm with preserved sharp edge data, The International Journal of Advanced Manufacturing Technology45(5-6) (2009), 583–592.
13.
KalaiahA. and VarshneyA., Modeling and rendering of points with local geometry, IEEE Transactions on Visualization and Computer Graphics9(1) (2003), 30–42.
14.
LeeK.H., WooH. and SukT., Point data reduction using 3D grids, The International Journal of Advanced Manufacturing Technology18(3) (2001), 201–210.
15.
LiH., XuP. and ShenY., A self-adaption fast point cloud simplification algorithm based on normal eigenvalues, In Proceedings of the International Congress on Image and Signal Processing, Dalian, China, 14–16 October 2014; pp. 852–856.
16.
MoenningC. and DodgsonN.A., A new point cloud simplification algorithm, In Proceedings of the International Conference on Visualization, Imaging and Image Processing, Benalmadena, Spain, 8-10 September, 2003.
17.
QingS., TaoX., TatsuoY., YujieZ., WentingY. and HangZ., Point cloud simplification algorithm based on particle swarm optimization for online measurement of stored bulk grain, International Journal of Agricultural and Biological Engineering9(1) (2016), 71–78.
18.
LealN., LealE. and GermanS.T., A linear programming approach for 3d point cloud simplification, IAENG International Journal of Computer Science44(1) (2017), 60–67.
19.
LiT., PanQ., GaoL. and LiP., A novel simplification method of point cloud with directed Hausdorff distance, In Proceedings of the International Conference on Computer Supported Cooperative Work in Design, Wellington, New Zealand, 26-28 April 2017; pp. 469–474.
20.
MandelbrotB.B., The fractal geometry of nature; Times Books: New York City, USA, 1982.
21.
PriebeC.E., SolkaJ.L., LoreyR.A., RogersG.W., PostonW.L., KallergiM., OianW., ClarkeL.P. and ClarkR.A., The application of fractal analysis to mammographic tissue classification, Cancer letters77(2) (1994), 183–189.
22.
BarrettA.H. and PelegM., Applications of fractal analysis to food structure, LWT-Food Science and Technology28(6) (1995), 553–563.
23.
ZhouG.Y., LeuM.C. and BlackmoreD., Fractal geometry model for wear prediction, Wear170(1) (1993), pp. 1–14.
24.
LopesR. and BetrouniN., Fractal and multifrl analysis: A review, Medical Image Analysis13(4) (2009), 634–649.
25.
UmyaiP., KumhomP. and ChamnongthaiK., Air bubbles detecting on ribbed smoked sheets based on fractal dimension, In Proceedings of the International Symposium on Intelligent Signal Processing and Communications Systems, Chiang Mai, Thailand, 7-9 Dec. 2011, pp. 1–4.
YangM., 134. Research on Denoising Algorithms Based on Point Cloud Data of Terrestrial 3D Laser Scanner, Revista de la Facultad de Ingeniería 32(11), 2017.
28.
WangY., Outlier formation and removal in 3Dlaser scanned point clouds, 2014, Doctoral dissertation, University of British Columbia.
SongH. and FengH.Y., Point-cloud simplification with bounded geometric deviations, International Journal of Computer Applications in Technology30(4) (2007), pp. 236–244.
33.
NingX., WangY., MengW. and ZhangX., Optimized shape semantic graph representation for object understanding and recognition in point clouds, Optical Engineering55(10) (2016), 103–111.
34.
SongH. and FengH.Y., A point cloud simplification algorithm for mechanical part inspection, In Proceedings of the International Conference on Information Technology for Balanced Automation Systems, Boston, USA, September 2006, pp. 461–468.
35.
ShiB.Q., LiangJ. and LiuQ., Adaptive simplification of point cloud using k-means clustering, Computer-Aided Design43(8) (2011), 910–922.
36.
PaulyM., GrossM. and KobbeltL.P., Efficient simplification of pointsampled surfaces, In Proceedings of the conference of IEEE visualization, Boston, USA, 27 Oct. -1 Nov. 2002, pp. 163–170.
37.
CignoniP., RocchiniC. and ScopignoR., Metro: Measuring error on simplified surfaces, Comput Graph Forum17(2) (1998), 167–174.
38.
MiaoY., PajarolaR. and FengJ., Curvature-aware adaptive re-sampling for point-sampled geometry, Comput-Aided Design41(6) (2009), 395–403.
