Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Spina, Sandro
Languages: English
Types: Doctoral thesis
Subjects: QA75, T1

Classified by OpenAIRE into

The acquisition of 3D point clouds representing the surface structure of real-world scenes has become common practice in many areas including architecture, cultural heritage and urban planning. Improvements in sample acquisition rates and precision are contributing to an increase in size and quality of point cloud data.\ud The management of these large volumes of data is quickly becoming a challenge, leading to the design of algorithms intended to analyse and decrease the complexity of this data. Point cloud segmentation algorithms partition point clouds for better management, and scene understanding algorithms identify the components of a scene in the presence of considerable clutter and noise. In many cases, segmentation algorithms operate within the remit of a specific context, wherein their effectiveness is measured. Similarly, scene understanding algorithms depend on specific scene properties and fail to identify objects in a number of situations.\ud This work addresses this lack of generality in current segmentation and scene understanding processes, and proposes methods for point clouds acquired using diverse scanning technologies in a wide spectrum of contexts. The approach to segmentation proposed by this work partitions a point cloud with minimal information, abstracting the data into a set of connected segment primitives to support efficient manipulation. A graph-based query mechanism is used to express further relations between segments and provide the building blocks for scene understanding. The presented method for scene understanding is agnostic of scene specific context and supports both supervised and unsupervised approaches. In the former, a graph-based object descriptor is derived from a training process and used in object identification. The latter approach applies pattern matching to identify regular structures. A novel external memory algorithm based on a hybrid spatial subdivision technique is introduced to handle very large point clouds and accelerate the computation of the k-nearest neighbour function. Segmentation has been successfully applied to extract segments representing geographic landmarks and architectural features from a variety of point clouds, whereas scene understanding has been successfully applied to indoor scenes on which other methods fail.\ud The overall results demonstrate that the context-agnostic methods presented in this work can be successfully employed to manage the complexity of ever growing repositories.\ud
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 231 Abuzaina, A., Nixon, M. S. & Carter, J. N. (2013). Sphere detection in kinect point clouds via the 3d hough transform, Computer Analysis of Images and Patterns, Springer, pp. 290{297.
    • Adan, A. & Huber, D. (2011). 3d reconstruction of interior wall surfaces under occlusion and clutter, 3D Imaging, Modeling, Processing, Visualization and Transmission (3DIMPVT), 2011 International Conference on, IEEE, pp. 275{ 281.
    • Anand, A., Koppula, H. S., Joachims, T. & Saxena, A. (2012). Contextually guided semantic labeling and search for three-dimensional point clouds, The International Journal of Robotics Research p. 0278364912461538.
    • Anguelov, D., Taskarf, B., Chatalbashev, V., Koller, D., Gupta, D., Heitz, G. & Ng, A. (2005). Discriminative learning of markov random elds for segmentation of 3d scan data, Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, Vol. 2, IEEE, pp. 169{176.
    • Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R. & Wu, A. Y. (1998). An optimal algorithm for approximate nearest neighbor searching xed dimensions, Journal of the ACM (JACM) 45(6): 891{923.
    • Asus, X. P. (2015). Xtion pro sensor, URL [http://http://www. asus. co. jp/Multimedia/Motion Sensor/Xtion PRO LIVE/] .
    • Bab-Hadiashar, A. & Gheissari, N. (2006). Range image segmentation using surface selection criterion, Image Processing, IEEE Transactions on 15(7).
    • Bailey, T. & Durrant-Whyte, H. (2006). Simultaneous localization and mapping (slam): Part ii, IEEE Robotics & Automation Magazine 13(3): 108{117.
    • Bayer, R. (1972). Symmetric binary b-trees: Data structure and maintenance algorithms, Acta informatica 1(4): 290{306.
    • Belongie, S., Malik, J. & Puzicha, J. (2002). Shape matching and object recognition using shape contexts, Pattern Analysis and Machine Intelligence, IEEE Transactions on 24(4): 509{522.
    • Bernardini, F. & Rushmeier, H. (2002). The 3d model acquisition pipeline, Computer graphics forum, Vol. 21, Wiley Online Library, pp. 149{172.
    • Besl, P. J. & Jain, R. C. (1985). Three-dimensional object recognition, ACM Computing Surveys (CSUR) 17(1): 75{145.
    • Biswas, J. & Veloso, M. (2012). Depth camera based indoor mobile robot localization and navigation, Robotics and Automation (ICRA), 2012 IEEE International Conference on, IEEE, pp. 1697{1702.
    • Borrmann, D., Elseberg, J., Lingemann, K. & Nuchter, A. (2011). The 3d hough transform for plane detection in point clouds: A review and a new accumulator design, 3D Research 2(2): 1{13.
    • Boykov, Y. & Funka-Lea, G. (2006). Graph cuts and e cient nd image segmentation, International journal of computer vision 70(2): 109{131.
    • Breiman, L. (2001). Random forests, Machine learning 45(1): 5{32.
    • Bro, R., Acar, E. & Kolda, T. G. (2008). Resolving the sign ambiguity in the singular value decomposition, Journal of Chemometrics 22(2): 135{140.
    • Budroni, A. & Bohm, J. (2009). Toward automatic reconstruction of interiors from laser data, Proceedings of Virtual Reconstruction and Visualization of Complex Architectures (3D-Arch) .
    • Bustos, B., Keim, D., Saupe, D. & Schreck, T. (2007). Content-based 3d object retrieval, Computer Graphics and Applications, IEEE 27(4): 22{27.
    • Camurri, M., Vezzani, R. & Cucchiara, R. (2014). 3d hough transform for sphere recognition on point clouds, Machine Vision and Applications 25(7): 1877{ 1891.
    • Chaperon, T., Goulette, F. & Laurgeau, C. (2001). Extracting cylinders in full 3d data using a random sampling method and the gaussian image., VMV, Vol. 1, Citeseer, pp. 35{42.
    • Chen, H. & Bhanu, B. (2007). 3d free-form object recognition in range images using local surface patches, Pattern Recognition Letters 28(10): 1252{1262.
    • Chen, X., Golovinskiy, A. & Funkhouser, T. (2009). A benchmark for 3d mesh segmentation, ACM Transactions on Graphics (TOG), Vol. 28, ACM, p. 73.
    • Chetverikov, D., Svirko, D., Stepanov, D. & Krsek, P. (2002). The trimmed iterative closest point algorithm, Pattern Recognition, 2002. Proceedings. 16th International Conference on, Vol. 3, IEEE, pp. 545{548.
    • Chua, C. S. & Jarvis, R. (1997). Point signatures: A new representation for 3d object recognition, International Journal of Computer Vision 25(1): 63{85.
    • Cignoni, P., Corsini, M. & Ranzuglia, G. (2008). Meshlab: an open-source 3d mesh processing system, Ercim news 73: 45{46.
    • Cignoni, P. & Scopigno, R. (2008). Sampled 3d models for ch applications: A viable and enabling new medium or just a technological exercise?, Journal on Computing and Cultural Heritage (JOCCH) 1(1): 2.
    • Clarkson, K. L. (1983). Fast algorithms for the all nearest neighbors problem, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE, pp. 226{232.
    • Cohen-Steiner, D., Alliez, P. & Desbrun, M. (2004). Variational shape approximation, ACM Transactions on Graphics (TOG), Vol. 23, ACM, pp. 905{914.
    • Daras, P. & Axenopoulos, A. (2010). A 3d shape retrieval framework supporting multimodal queries, International Journal of Computer Vision 89(2-3): 229{ 247.
    • Delingette, H. (1999). General object reconstruction based on simplex meshes, International Journal of Computer Vision 32(2): 111{146.
    • Denning, P. J. (1970). Virtual memory, ACM Computing Surveys 2: 153{189.
    • Deschaud, J.-E. & Goulette, F. (2010). A fast and accurate plane detection algorithm for large noisy point clouds using ltered normals and voxel growing, in B. Fisher & C. Theobalt (eds), 3D Data Processing, Visualization and Transmission, Eurographics Association, Paris, France.
    • Do Carmo, M. P. & Do Carmo, M. P. (1976). Di erential geometry of curves and surfaces, Vol. 2, Prentice-Hall Englewood Cli s.
    • Dorninger, P. & Nothegger, C. (2007). 3d segmentation of unstructured point clouds for building modelling, International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 35(3/W49A): 191{196.
    • Douillard, B., Underwood, J., Kuntz, N., Vlaskine, V., Quadros, A., Morton, P. & Frenkel, A. (2011). On the segmentation of 3d lidar point clouds, Robotics and Automation (ICRA), 2011 IEEE International Conference on, IEEE, pp. 2798{ 2805.
    • Elseberg, J., Borrmann, D. & Nuchter, A. (2011). E cient processing of large 3d point clouds, Information, Communication and Automation Technologies (ICAT), 2011 XXIII International Symposium on, IEEE, pp. 1{7.
    • Falcidieno, B. (2004). Aim@ shape project presentation, Shape Modeling Applications, 2004. Proceedings, IEEE, p. 329.
    • Fan, T.-J., Medioni, G. & Nevatia, R. (1989). Recognizing 3-d objects using surface descriptions, Pattern Analysis and Machine Intelligence, IEEE Transactions on 11(11): 1140{1157.
    • Faugeras, O. D. & Hebert, M. (1986). The representation, recognition, and locating of 3-d objects, Int. J. Rob. Res. 5(3): 27{52. URL: http://dx.doi.org/10.1177/027836498600500302
    • Fischler, M. A. & Bolles, R. C. (1981). Random sample consensus: a paradigm for model tting with applications to image analysis and automated cartography, Communications of the ACM 24: 381{395.
    • Fisher, M., Savva, M. & Hanrahan, P. (2011). Characterizing structural relationships in scenes using graph kernels, ACM Transactions on Graphics (TOG), Vol. 30, ACM, p. 34.
    • Friedman, J. H., Bentley, J. L. & Finkel, R. A. (1977). An algorithm for nding best matches in logarithmic expected time, ACM Transactions on Mathematical Software (TOMS) 3(3): 209{226.
    • Frome, A., Huber, D., Kolluri, R., Bulow, T. & Malik, J. (2004). Recognizing objects in range data using regional point descriptors, Computer Vision-ECCV 2004, Springer, pp. 224{237.
    • Frueh, C., Jain, S. & Zakhor, A. (2005). Data processing algorithms for generating textured 3d building facade meshes from laser scans and camera images, International Journal of Computer Vision 61(2): 159{184.
    • Gao, J. & Yang, R. (2013). Online building segmentation from ground-based lidar data in urban scenes, 3DTV-Conference, 2013 International Conference on, IEEE, pp. 49{55.
    • Golovinskiy, A. & Funkhouser, T. (2009). Min-cut based segmentation of point clouds, Computer Vision Workshops (ICCV Workshops), 2009 IEEE 12th International Conference on, IEEE, pp. 39{46.
    • Golovinskiy, A., Kim, V. G. & Funkhouser, T. (2009). Shape-based recognition of 3d point clouds in urban environments, Computer Vision, 2009 IEEE 12th International Conference on, IEEE, pp. 2154{2161.
    • Gotardo, P. F., Bellon, O. R. P. & Silva, L. (2003). Range image segmentation by surface extraction using an improved robust estimator, Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, Vol. 2, IEEE, pp. II{33.
    • Graham, R. L. & Hell, P. (1985). On the history of the minimum spanning tree problem, Annals of the History of Computing 7(1): 43{57.
    • Gross, M. & P ster, H. (2011). Point-based graphics, Morgan Kaufmann.
    • Gumhold, S., Wang, X. & MacLeod, R. (2001). Feature extraction from point clouds, Proceedings of 10th international meshing roundtable, Vol. 2001, Citeseer.
    • Hahnel, D., Burgard, W. & Thrun, S. (2003). Learning compact 3d models of indoor and outdoor environments with a mobile robot, Robotics and Autonomous Systems 44(1): 15{27.
    • Hearst, M. A., Dumais, S., Osman, E., Platt, J. & Scholkopf, B. (1998). Support vector machines, Intelligent Systems and their Applications, IEEE 13(4): 18{ 28.
    • Hetzel, G., Leibe, B., Levi, P. & Schiele, B. (2001). 3d object recognition from range images using local feature histograms, Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on, Vol. 2, IEEE, pp. II{394.
    • Hoover, A., Jean-Baptiste, G., Jiang, X., Flynn, P. J., Bunke, H., Goldgof, D. B., Bowyer, K., Eggert, D. W., Fitzgibbon, A. & Fisher, R. B. (1996). An experimental comparison of range image segmentation algorithms, Pattern Analysis and Machine Intelligence, IEEE Transactions on 18(7): 673{689.
    • Hoppe, H., DeRose, T., Duchamp, T., McDonald, J. & Stuetzle, W. (1992). Surface reconstruction from unorganized points, Vol. 26, ACM.
    • Hu, J., You, S. & Neumann, U. (2003). Approaches to large-scale urban modeling, Computer Graphics and Applications, IEEE 23(6): 62{69.
    • Jaakkola, A., Hyyppa, J., Hyyppa, H. & Kukko, A. (2008). Retrieval algorithms for road surface modelling using laser-based mobile mapping, Sensors 8(9): 5238{5249.
    • Jared, D. (2014). Structure o ers 3d scanning right on your ipad @ONLINE. URL: http://www.imore.com/ceslive-scan-your-world-structure-sensor
    • Johnson, A. E. (1997). Spin-images: a representation for 3-D surface matching, PhD thesis, Citeseer.
    • Johnson, A. E. & Hebert, M. (1999). Using spin images for e cient object recognition in cluttered 3d scenes, Pattern Analysis and Machine Intelligence, IEEE Transactions on 21(5): 433{449.
    • Juan, L. & Gwun, O. (2009). A comparison of sift, pca-sift and surf, International Journal of Image Processing (IJIP) 3(4): 143{152.
    • Karpathy, A., Miller, S. & Fei-Fei, L. (2013). Object discovery in 3d scenes via shape analysis, Robotics and Automation (ICRA), 2013 IEEE International Conference on, IEEE, pp. 2088{2095.
    • Kazhdan, M., Funkhouser, T. & Rusinkiewicz, S. (2003). Rotation invariant spherical harmonic representation of 3 d shape descriptors, Symposium on geometry processing, Vol. 6.
    • Kim, Y. M., Mitra, N. J., Yan, D.-M. & Guibas, L. (2012). Acquiring 3d indoor environments with variability and repetition, ACM Transactions on Graphics (TOG) 31(6): 138.
    • Kindermann, R., Snell, J. L. et al. (1980). Markov random elds and their applications, Vol. 1, American Mathematical Society Providence, RI.
    • Koenderink, J. J. & van Doorn, A. J. (1992). Surface shape and curvature scales, Image and vision computing 10(8): 557{564.
    • Kolb, A., Barth, E., Koch, R. & Larsen, R. (2009). Time-of- ight sensors in computer graphics, Proc. Eurographics (State-of-the-Art Report), pp. 119{134.
    • Koppula, H. S., Anand, A., Joachims, T. & Saxena, A. (2011). Semantic labeling of 3d point clouds for indoor scenes, Advances in Neural Information Processing Systems, pp. 244{252.
    • Lafarge, F. & Alliez, P. (2013). Surface reconstruction through point set structuring, Computer Graphics Forum, Vol. 32, Wiley Online Library, pp. 225{234.
    • La erty, J., McCallum, A. & Pereira, F. C. (2001). Conditional random Probabilistic models for segmenting and labeling sequence data.
    • Lai, K., Bo, L., Ren, X. & Fox, D. (2011). A large-scale hierarchical multi-view rgb-d object dataset, Robotics and Automation (ICRA), 2011 IEEE International Conference on, IEEE, pp. 1817{1824.
    • Lalonde, J.-F., Vandapel, N., Huber, D. F. & Hebert, M. (2006). Natural terrain classi cation using three-dimensional ladar data for ground robot mobility, Journal of eld robotics 23(10): 839{861.
    • Lavoue, G., Vandeborre, J.-P., Benhabiles, H., Daoudi, M., Huebner, K., Mortara, M. & Spagnuolo, M. (2012). Shrec'12 track: 3d mesh segmentation, Lee, D.-T. & Schachter, B. J. (1980). Two algorithms for constructing a delaunay triangulation, International Journal of Computer & Information Sciences 9(3): 219{242.
    • Li, B., Godil, A., Aono, M., Bai, X., Furuya, T., Li, L., Lopez-Sastre, R., Johan, H., Ohbuchi, R., Redondo-Cabrera, C. et al. (2012). Shrec'12 track: generic 3d shape retrieval, Proceedings of the 5th Eurographics conference on 3D Object Retrieval, Eurographics Association, pp. 119{126.
    • Lin, H., Gao, J., Zhou, Y., Lu, G., Ye, M., Zhang, C., Liu, L. & Yang, R. (2013). Semantic decomposition and reconstruction of residential scenes from lidar data., ACM Trans. Graph. 32(4): 66.
    • Marr, D. & Poggio, T. (1979). A computational theory of human stereo vision, Proceedings of the Royal Society of London. Series B. Biological Sciences 204(1156): 301{328.
    • Mattausch, O., Panozzo, D., Mura, C., Sorkine-Hornung, O. & Pajarola, R. (2014). Object detection and classi cation from large-scale cluttered indoor scans, Computer Graphics Forum, Vol. 33, Wiley Online Library, pp. 11{21.
    • Mikolajczyk, K. & Schmid, C. (2005). A performance evaluation of local descriptors, Pattern Analysis and Machine Intelligence, IEEE Transactions on 27(10): 1615{1630.
    • Moosmann, F., Pink, O. & Stiller, C. (2009). Segmentation of 3d lidar data in non- at urban environments using a local convexity criterion, Intelligent Vehicles Symposium, 2009 IEEE, IEEE, pp. 215{220.
    • Muja, M. & Lowe, D. (2009a). Flann-fast library for approximate nearest neighbors user manual, Computer Science Department, University of British Columbia, Vancouver, BC, Canada .
    • Ning, X., Zhang, X. & Wang, Y. (2009). Tree segmentation from scanned scene data, Plant Growth Modeling, Simulation, Visualization and Applications (PMA), 2009 Third International Symposium on, IEEE, pp. 360{367.
    • Novatnack, J. & Nishino, K. (2008). Scale-dependent/invariant local 3d shape descriptors for fully automatic registration of multiple sets of range images, Computer Vision{ECCV 2008, Springer, pp. 440{453.
    • Oehler, B., Stueckler, J., Welle, J., Schulz, D. & Behnke, S. (2011). E cient multi-resolution plane segmentation of 3d point clouds, Intelligent Robotics and Applications, Springer, pp. 145{156.
    • Oppenheim, A. V., Schafer, R. W., Buck, J. R. et al. (1989). Discrete-time signal processing, Vol. 2, Prentice-hall Englewood Cli s.
    • Pal, N. R. & Pal, S. K. (1993). A review on image segmentation techniques, Pattern recognition 26(9): 1277{1294.
    • Rusu, R. B., Blodow, N. & Beetz, M. (2009). Fast point feature histograms (fpfh) for 3d registration, Robotics and Automation, 2009. ICRA'09. IEEE International Conference on, IEEE, pp. 3212{3217.
    • Rusu, R. B., Blodow, N., Marton, Z. C. & Beetz, M. (2008). Aligning point cloud views using persistent feature histograms, Intelligent Robots and Systems, 2008. IROS 2008. IEEE/RSJ International Conference on, IEEE, pp. 3384{ 3391.
    • Rusu, R. B., Bradski, G., Thibaux, R. & Hsu, J. (2010). Fast 3d recognition and pose using the viewpoint feature histogram, Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ International Conference on, IEEE, pp. 2155{2162.
    • Rusu, R. B. & Cousins, S. (2011). 3d is here: Point cloud library (pcl), Robotics and Automation (ICRA), 2011 IEEE International Conference on, IEEE, pp. 1{4.
    • Rusu, R. B., Marton, Z. C., Blodow, N. & Beetz, M. (2008). Learning informative point classes for the acquisition of object model maps, Control, Automation, Robotics and Vision, 2008. ICARCV 2008. 10th International Conference on, IEEE, pp. 643{650.
    • Schnabel, R., Wessel, R., Wahl, R. & Klein, R. (2008). Shape recognition in 3d point-clouds, Proc. Conf. in Central Europe on Computer Graphics, Visualization and Computer Vision, Vol. 2, Citeseer.
    • Stoer, M. & Wagner, F. (1997). A simple min-cut algorithm, Journal of the ACM (JACM) 44(4): 585{591.
    • Sun, Y. & Abidi, M. A. (2001). Surface matching by 3d point's ngerprint, Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on, Vol. 2, IEEE, pp. 263{269.
    • Unnikrishnan, R. & Hebert, M. (2003). Robust extraction of multiple structures from non-uniformly sampled data, Intelligent Robots and Systems, 2003.(IROS 2003). Proceedings. 2003 IEEE/RSJ International Conference on, Vol. 2, IEEE, pp. 1322{1329.
    • Vaidya, P. M. (1989). Ano (n logn) algorithm for the all-nearest-neighbors problem, Discrete & Computational Geometry 4(1): 101{115.
    • Van De Geer, S. & Van De Geer, S. (2000). Empirical Processes in M-estimation, Vol. 105, Cambridge university press Cambridge.
    • Vosselman, G., Gorte, B. G., Sithole, G. & Rabbani, T. (2004). Recognising structure in laser scanner point clouds, International archives of photogrammetry, remote sensing and spatial information sciences 46(8): 33{38.
    • Zhang, H., Fritts, J. E. & Goldman, S. A. (2008). Image segmentation evaluation: A survey of unsupervised methods, computer vision and image understanding 110(2): 260{280.
    • Zhang, S. & Yau, S.-T. (2006). High-resolution, real-time 3d absolute coordinate measurement based on a phase-shifting method, Optics Express 14(7): 2644{ 2649.
    • Zhang, Z. (2012). Microsoft kinect sensor and its e ect, MultiMedia, IEEE 19(2): 4{10.
    • Zhao, H., Liu, Y., Zhu, X., Zhao, Y. & Zha, H. (2010). Scene understanding in a large dynamic environment through a laser-based sensing, Robotics and Automation (ICRA), 2010 IEEE International Conference on, IEEE, pp. 127{ 133.
    • Zhou, Y., Wang, D., Xie, X., Ren, Y., Li, G., Deng, Y. & Wang, Z. (2014). A fast and accurate segmentation method for ordered lidar point cloud of large-scale scenes, Geoscience and Remote Sensing Letters, IEEE 11: 1981{1985.
  • Inferred research data

    The results below are discovered through our pilot algorithms. Let us know how we are doing!

    Title Trust
  • No similar publications.

Share - Bookmark

Cite this article