This paper proposes a fast algorithm for ground segmentation of point clouds. It differentiates ground points from obstacle points from unstructured point clouds. This segmentation consists of performing an orthogonal projection into the horizontal xy plane followed by a top-down area subdivision. This process self-adapts to the point cloud, focusing processing effort on detailed areas. Real-time performance for execution in low cost embedded devices is demonstrated through quantitative and qualitative test results.
MasudaH., NiwaT., TanakaI. and MatsuokaR., Reconstruction of polygonal faces from large-scale point-clouds of engineering plants, Computer-Aided Design and Applications12(5) (2015), 555-563, [Online]. Available: http://dx.doi. org/10.1080/16864360.2015.1014733.
2.
GuoH., ZhuD. and MordohaiP., Correspondence estimation for non-rigid point clouds with automatic part discovery, The Visual Computer (2015), 1-14. [Online]. Available: http://dx.doi.org/10.1007/s00371-015-1136-5.
3.
AbayowaB.O., YilmazA. and HardieR.C., Automatic registration of optical aerial imagery to a lidar point cloud for generation of city models, ISPRS Journal of Photogrammetry and Remote Sensing106 (2015), 68-81. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S092427161 5001434.
4.
OchmannS., VockR., WesselR. and KleinR., Automatic reconstruction of parametric building models from indoor point clouds, Computers and Graphics54 (2016), 94-103, special Issue on CAD/Graphics 2015. [Online]. Available: http:// www.sciencedirect.com/science/article/pii/S0097849315001119.
5.
WeberT., HnschR. and HellwichO., Automatic registration of unordered point clouds acquired by kinect sensors using an overlap heuristicISPRS Journal of Photogrammetry and Remote Sensing102 (2015), 96-109. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S092427161 4002895.
6.
ZhangJ. and SinghS., Visual-lidar odometry and mapping: low-drift, robust, and fast, in IEEE International Conference on Robotics and Automation, ICRA 2015, Seattle, WA, USA, 26-30 May, 2015, 2015, pp. 2174-2181. [Online]. Available: http://dx.doi.org/10.1109/ICRA.2015.7139486.
7.
BehleyJ., SteinhageV. and CremersA., Efficient radius neighbor search in three-dimensional point clouds, in Robotics and Automation (ICRA), 2015 IEEE International Conference on, May 2015, pp. 3625-3630.
8.
SchnabelR., WahlR. and KleinR., Efficient ransac for point-cloud shape detection, Computer Graphics Forum26(2) (2007), 214-226. [Online]. Available: http://dx.doi.org/ 10.1111/j.1467-8659.2007.01016.x.
9.
HulikR., SpanelM., SmrzP. and MaternaZ., Continuous plane detection in point-cloud data based on 3d hough transform, Journal of Visual Communication and Image Representation25(1) (2014), 86-97, visual Understanding and Applications with RGB-D Cameras. [Online]. Available: http:// www.sciencedirect.com/science/article/pii/S104732031300062X.
10.
LimbergerF.A. and OliveiraM.M., Real-time detection of planar regions in unorganized point clouds, Pattern Recognition48(6) (2015), 2043-2053. [Online]. Available: http:// www.sciencedirect.com/science/article/pii/S0031320315000072.
11.
MoosmannF., PinkO. and StillerC., Segmentation of 3d lidar data in non-flat urban environments using a local convexity criterion, in Intelligent Vehicles Symposium, 2009 IEEE, Jun. 2009, pp. 215-220.
12.
StromJ., RichardsonA. and OlsonE., Graph-based segmentation for colored 3d laser point clouds, in Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ International Conference on, Oct. 2010, pp. 2131-2136.
13.
SchoenbergJ., NathanA. and CampbellM., Segmentation of dense range information in complex urban scenes, in Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ International Conference on, Oct. 2010, pp. 2033-2038.
14.
JordanK. and MordohaiP., A quantitative evaluation of surface normal estimation in point clouds, in Intelligent Robots and Systems (IROS 2014), 2014 IEEE/RSJ International Conference on, Sep. 2014, pp. 4220-4226.
15.
HernandezJ. and MarcoteguiB., Point cloud segmentation towards urban ground modeling, in Urban Remote Sensing Event, 2009 Joint, May 2009, pp. 1-5.
16.
HimmelsbachM., LuettelT. and WuenscheH., Real-time object classification in 3d point clouds using point feature histograms, in Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on, Oct. 2009, pp. 994-1000.
17.
HamppJ. and BormannR., Quadtree-based polynomial polygon fitting, in Intelligent Robots and Systems (IROS), 2013 IEEE/RSJ International Conference on, Nov. 2013, pp. 4207-4213.
18.
BewleyA. and UpcroftB., Advantages of exploiting projection structure for segmenting dense 3d point clouds, in Australasian Conference on Robotics and Automation (ACRA2013), J. Katupitiya, J. Guivant and R. Eaton, eds, University of New South Wales, Sydney, NSW: Australian Robotics & Automation Association, 2013, pp. 1-8. [Online]. Available: http://eprints.qut.edu.au/66623/.
19.
ParkJ., ChoiS. and YuW., Quadtree sampling-based superpixels for 3d range data, in Robotics and Automation (ICRA), 2014 IEEE International Conference on, May 2014, pp. 5495-5501.
20.
KlasingK., WollherrD. and BussM., A clustering method for efficient segmentation of 3d laser data, in Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on, May 2008, pp. 4043-4048.
21.
DouillardB., UnderwoodJ., KuntzN., VlaskineV., QuadrosA., MortonP. and FrenkelA., On the segmentation of 3d lidar point clouds, in Robotics and Automation (ICRA), 2011 IEEE International Conference on, May 2011, pp. 2798-2805.
22.
Marcon dos SantosG.A., FerraoV.T., VinhalC.D.N. and Cruz JuniorG., An adaptive algorithm for embedded real-time point cloud ground segmentation, in Soft Computing and Pattern Recognition (SoCPaR), 2015 7th International Conference on, Nov. 2015, pp. 76-83.
23.
FischlerM.A. and BollesR.C., Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography, Commun. ACM24(6) (1981), 381-395. [Online]. Available: http://dx.doi.org/ 10.1145/358669.358692.
24.
BackT., FogelD.B. and MichalewiczZ., eds, Handbook of Evolutionary Computation, 1st ed., Bristol, UK, UK: IOP Publishing Ltd., 1997.
25.
EibenA. and SmithJ., Introduction to evolutionary computing, Assembly Automation24(3) (2004), 324-324. [Online]. Available: http://dx.doi.org/10.1108/aa.2004.24.3.324.1.
26.
WahlR., GutheM. and KleinR., Identifying planes in point-clouds for efficient hybrid rendering, in The 13th Pacific Conference on Computer Graphics and Applications, Oct. 2005.
27.
YangM.Y. and FörstnerW., Plane detection in point cloud data, in Proceedings of the 2nd int conf on machine control guidance, Bonn1 (2010), 95-104.
28.
GotardoP., BellonO., BoyerK. and SilvaL., Range image segmentation into planar and quadric surfaces using an improved robust estimator and genetic algorithm, Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on34(6) (2004), 2303-2316.
29.
BazarganiM., MateusL. and LojaM., Planar surfaces recognition in 3d point cloud using a real-coded multistage genetic algorithm, in Applications of Evolutionary Computation, ser. Lecture Notes in Computer Science, A.M. Mora and G. Squillero, eds, Springer International Publishing, 2015, vol. 9028, pp. 529-540. [Online]. Available: http://dx.doi.org/ 10.1007/978-3-319-16549-3_43.
30.
TodaY. and KubotaN., Behavior analysis of evolution strategy sample consensus, in Mecatronics (MECATRONICS), 2014 10th France-Japan/ 8th Europe-Asia Congress on, Nov. 2014, pp. 250-255.
31.
MurrayR.M., SastryS.S. and ZexiangL., A Mathematical Introduction to Robotic Manipulation, 1st ed., Boca Raton, FL, USA: CRC Press, Inc., 1994.
32.
MunozD., VandapelN. and HebertM., Onboard contextual classification of 3-d point clouds with learned high-order markov random fields, in Robotics and Automation, 2009. ICRA '09. IEEE International Conference on, May 2009, pp. 2009-2016.
