Automatic object shape recognition through point clouds analysis

POLITECNICO DI MILANO

School of Industrial and Information Engineering

Master of Science in Space Engineering

Automatic object shape recognition

through point clouds analysis

Author:

Marco Bianchi Matr. 804743

Advisor:

Prof. Mauro Massari

Abstract

This paper wants to propose an preliminary algorithm for recovery the shape of 3D objects directly from a surface point cloud. No surface recon-struction or surface normal computation are needed in advance.

The recognition is performed in three stages. The rst stage consists on localizing the areas in which key-points can be present and identifying them. The second stage extracts a neighbourhood cloud for each key-point and analyses it in order to bring out the peculiarity of the region and classify it. Lastly the recognition process is performed together with the calculus of the main characteristic dimensions.

The method is simple, fast and could be applied to space activities where an automatic robotic vision is required.

Sommario

Questo documento vuole proporre un algoritmo preliminare atto a in-tepretare la forma di oggetti tridimensionali. Non sono necessarie alcuna previa ricostruzione o calcolo di normali superciali.

Il riconoscimento consta di tre stadi. Il primo stadio consiste nel local-izzare le aree che potebbero ospitare particolari punti di interesse e nella identicazione di questi. Il secondo, per ogni punto di interesse estrae una nuvola di punti nella sua prossimità e la analizza, in modo da evidenziare le caratteristiche della regione e per classicarla. In ultimo si attuano riconoscimento della forma e il calcolo delle dimensioni caratteristiche.

Il metodo è semplice, veloce e può essere applicato a quelle attività spaziali nelle quali è richiesta la visione robotica automatica.

Contents

List of Figures vii

List of Tables ix

1 Introduction 1

2 Preliminary and applications 3

2.1 Overview on 3D data acquisition . . . 3

2.2 Point clouds . . . 5

2.2.1 Point Cloud Library . . . 8

2.3 State of the art . . . 11

2.3.1 Descriptors . . . 11

2.3.2 Key-points . . . 12

2.3.3 Current approaches . . . 13

3 Proposed method 19 3.1 Strategy for vertices identication . . . 19

3.2 Characterisation of the key-points . . . 23

3.2.1 Covariance matrix . . . 24

3.2.2 Curvature . . . 26

3.2.3 Sub-clouds characterisation . . . 26

3.3 Shape recognition from the key-points . . . 28

3.3.1 Prism . . . 28

3.3.2 Cone . . . 30

3.3.3 Cylinder . . . 31

3.3.4 Sphere . . . 31

3.4 Filtering . . . 32

4 Tests and Results 35 4.1 Laboratory activities and instruments . . . 35

4.1.1 Acquisition issues . . . 36 v

4.2 Recognition phase . . . 37 4.2.1 Performances . . . 43 5 Conclusions and future work 45

List of Figures

2.1 3D scanning taxonomy (1). [By Brian Curless, Sig2000

CoursesNotes] . . . 4

2.2 3D scanning taxonomy (2). [By Brian Curless, Sig2000 CoursesNotes] . . . 4

2.3 FPFH descriptor . . . 12

2.4 Example of a recognition process with local descriptors. . . 14

2.5 Example of global descriptor applied in the centroid: VFH 15 2.6 Superquadratics family. . . 16

3.1 Example of RANSAC . . . 20

3.2 Plane segmentation. . . 21

3.3 Lines and extremities. . . 22

3.4 Typologies of neighbours point clouds. . . 23

3.5 The covariance matrix . . . 25

3.6 Eigenvalues versus variance . . . 25

3.7 Border clouds at the base of a cone point cloud . . . 27

3.8 Edge identication. . . 29

3.9 Corner points projected on the plane. . . 30

3.10 Reconstruct prism from vertices. . . 30

3.11 Reconstruct cylinder from edge. . . 32

4.1 Konica Minolta VIVID 9i 3D Laser Scanner and turntable. 36 4.2 The cone (a) and the box (b) used for the tests. . . 37

4.3 Planes recognised in a solid of revolution. . . 38

4.4 The plane recognition phase in a mug before (a) and after (b) the cleaning. . . 39

4.5 Local maxima and key-point. . . 39

4.6 Markers in synthetic point clouds. . . 40

4.7 Markers in acquired point clouds. . . 41

4.8 Example of dicult recognition. . . 42

List of Tables

2.1 Optical acquisition methods characteristics. . . 6

2.2 Global vs local descriptors. . . 16

4.2 Dimensions of the synthetic point clouds. . . 42

4.3 Dimensions of the acquired point clouds. . . 42

Chapter 1

Introduction

Several eorts always have been made to simplify and make safer those actions where men are implied and moreover where they can not partici-pate, automating the processes and placing robots side by side the man. This happened in elds related to industries, medicine, agriculture and many others. Of course the space environment is one of those that most requires very high levels of security, reliability and simplicity, moreover when the man itself is implied. Automatic robotic systems are strongly required for any activity both on-orbit and on ground.

In the last years a very important problem rose, concerning the satel-lite overcrowding of the areas just outside the atmosphere and the one at the altitude of approximately 36 km, corresponding to the Low Earth Orbits (LEO) and the Geosynchronous Earth Orbits (GEO). These or-bits, due to their proximity and properties, are those most exploited by Earth observations, telecommunications and localization services. The hight manufacturing cost of a satellite and the recent space debris alarm have solicited the companies to refuel the functioning satellites for eco-nomic motivations, and to reach and rid the orbits of the inoperative satellites for security reasons. Furthermore a lot of eorts and resources are implied in the maintenance and provisions of the International Space Station (ISS), as long as many studies are conducted in the attempt to carry again the man on the Moon and even to Mars. Thus dierent au-tonomous and robotic concepts are developing in order to help the astro-nauts for these purposes. Recent works report studies and demonstrations of modular satellite built on-orbit [7] and of an automatic robotic vision for a autonomous tracking during satellite rendez-vous [14] or on-orbit service [11]. In [3][6][21] is observed how robots could assist a space crew independently and in cooperation.

In the light of these current necessities, the present paper oers a 1

preliminary pipeline algorithm for automatic objects recognition tasks, for those elds where robots have to grasp and handle objects as well as identify the shape during tracking or in the approaching phases. It is a simple procedure that exploits the point clouds versatility and precision to represent and analyse target objects characterised and composed by simple geometrical shapes, without the need of a prior surface reconstruction and without the calculus of the surface normals for each points, which makes faster the procedure. With this regard the automatic robotic vision takes a relevant rule in all the above mentioned space activities. The method makes use of particular points selected on the surface through the analysis of their neighbourhood clouds and that corresponds to the vertices or the edges of the objects. Finding geometric relations among them will be show how the shape can be reconstructed.

Many are the possibilities existing for shapes acquisition, subdivided in dierent technologies and methods. Contact probes (destructive or not) are characterised by very high delity and precision but need to much time and a short range of operability; reective and transmissive techniques are more versatile, faster and still very accurate. It has been chosen to use, as support for the analysis, a laser scanner, i.e. an active optical device, that returns range images in the form of point cloud data, due to the em-ployment simplicity, the reliability and the availability of the resources. Moreover point clouds are very convenient when we have to analyse au-tomatically the data and apply on them recognition algorithms and not simply generate rendered images that could be well interpreted only by humans. The aim is to make the data readable and understandable by a robot, thus it is needed to work on each single regions of the object and to nd relations among the surrounding areas. The operations took place inside the Space Mechatronic Systems Technology (SMeSTech) Labora-tory at the University of Strathclyde. The method has been developed in C++ exploiting the Point Cloud Library (PCL) for the analysis of the

data acquired.

To this aim, after a brief introduction to what is a point cloud and its applications, the successive chapters will provide an explanation of the proposed functional and algorithmic architecture. Then some experimen-tal results will be presented, nally some conclusions and considerations will be drawn in the nal chapter, together with some indications regard-ing possible future improvements in the pipeline.

Chapter 2

Preliminary and applications

2.1 Overview on 3D data acquisition

The main methods to acquire 3D data are four, but only one is useful for our purpose. Using CAD tools is complex and requires skilled users; they are not adequate for accurate reproduction of highly complex, free form surfaces and, most important, they need a user that manually represents the object under observation. Image-based Rendering and Modeling use 2D images and models to reproduce the 3D shape but still the construc-tion must be user-assisted. Only 3D scanning techniques can manage the construction of an accurate 3D model of a really complex artefact. In Figures 2.1 and 2.2 is shown the 3D scanning taxonomy.

The characteristic for an optimal scanner are: • truly 3D

• accurate • fast

• easy to use and to move in the acquisition space • safe, both for the user and the reconstructed object

• capable of capturing object appearance (color or radiance) • low price

A rst division has to be made among the techniques, distinguishing them from contact and noncontact devices. The rst is relative to contact probes handled manually or through robots that register the surface evo-lution under inspection. They have to be discarded because too slow and

Shape aquisition Non-contact Transmissive Industrial CT Reective Optical Non-optical Sonar Microwave radar Contact Destructive Slicing Non-destructive Jointed arms CMM

Figure 2.1: 3D scanning taxonomy (1). [By Brian Curless, Sig2000 Courses-Notes] Optical Active Triangulation Structured light Laser-based Imaging radar Passive Depth from fosus/defocus Stereo Shape from silhouettes

Figure 2.2: 3D scanning taxonomy (2). [By Brian Curless, Sig2000 Courses-Notes]

2.2. POINT CLOUDS 5 equivocally accurate (depending on the point to be sampled) and even de-structive in some cases. Among the noncontact possibilities the optical and transmissive ones are worth to note. The possible data produced in output by a scanner are of four types and depend on the technology and methods used. The optical beam can be concentrated in one point and in this case the approach is similar to the contact probe above cited. It can be produced as a prole, a range image or as volumetric section. The last one derives from the use of transmissive activeCT scanners that do not produce point clouds but a set of 2D slices which are then `stacked together' to produce a 3D representation. A 3D model can also be recon-structed by tting an isosurface. The others two possibilities regard the laser devices and will be discussed later. Considering optical subsection, a common method is to exploit a series of images acquired from dierent views in order to extract the object silhouette in each image [5]. Each silhouette plus the camera center denes a conic region of space which encloses the object; the intersection of the cones gives a bounding vol-ume from which is possible to reconstruct the 3D shape. Must be noted that the bounding volume is the visual hull of the real 3D object without the concavities. The reconstruction is carried out by compositing conic regions in a discrete voxel space, and then tting an isosurface. Another diuse approach uses a structured light, made by regular or more complex stripe pattern, projected on the object. Just with one or two photos is possible to acquire the 3D shape and reconstruct the geometry by trian-gulation. The laser scan is the method used in this paper and it projects on the object a line-shaped beam that sweeps it in its entirety. Its output is a range image that can be managed like a point cloud. In Table 2.1

are summarised the advantages and the disadvantages of the described techniques.

2.2 Point clouds

The starting point for all the types of virtual recognitions are standard digital images and videos or range images and point clouds which include also space information. The methods that analyse 2D images exploit the dierence in colour and brightness, that each pixel has, to detect some relevant information. For example the `Edge detection' is a mathematical method that identies the points in a digital image at which the image brightness changes sharply. These points are typically organized into a set of curved line segments termed edges. Conversely `Blob detection' methods research regions in a digital image that have properties, such as

Methods ADVANTAGIES DISADVANTAGIES Silhouette  Very fast and easy touse.  Low accuracy.

 Low price.  Concave regions not seen.

 No registration re-quired.

Laser based  Compact Low power required.  Large variation in Expensive. resolution and eld of view

 Tight focus over long distances.

Structured light  Simpler design, nosweeping/translating devices needed

 Trade o depth-of-eld for speed

 Fast and cheap (a single image for each multi-stripe pattern).

 Ambiguity in single multi-stripe pattern  From low to high

ac-curacy

Active CT  A complete modelis returned in a single shot, registration and merging not required

 Limitation in the size of the scanned ob-ject

 Output: volume data, much more than exterior surface

 Cost of the device  Output: no data on surface attributes (e.g. color)

2.2. POINT CLOUDS 7 brightness and colour, that are constant or approximately constant, com-pared to surrounding regions. The recognition of these primitives entities leads to the recognition of features, more sophisticated and remarkable characteristics that will be discussed later.

A great improvement came from the employment of 3D sensors to capture information. Devices like the `Microsoft Kinect', endowed with a RGB camera and double infrared depth sensor composed by a laser scanner, allow to obtain 3D point cloud data with embedded colour in-formation. Having a 3D representation allows to estimate with decent accuracy the exact position and orientation of the object, relative to the sensor. Also, 3D object recognition tends to be more robust to clutter (crowded scenes where objects in the front occlude objects in the back-ground). And nally, having information about the object's shape will help with collision avoidance or grasping operations.

As the result of a 3D scanning process point clouds are used for many purposes, including to create 3D CAD models for manufactured parts, 3D reverse engineering, 3D geometry reconstruction, metrology/quality inspection, and a multitude of visualization, animation, rendering and medical applications. Instead devices like range cameras provide intensity images where each pixel expresses the distance between a known reference frame and a visible point in the scene. Therefore, a range image repro-duces the 3D structure of a scene. Range images are also referred to as depth images, depth maps, xyz maps, surface proles and 2.5D images. Range images can be represented in two basic forms. One is a list of 3D co-ordinates in a given reference frame (cloud of points), for which no specic order is required. The other is a matrix of depth values of points along the directions of the x,y image axes, which makes spatial organisation explicit. A point cloud is a way to visualize and describe objects. It is a data structure used to represent a collection of multi-dimensional points and is commonly used to represent three-dimensional data of a whatever sur-face. Generally the points collected, representing an underlying sampled surface, are dened in Cartesian coordinates and often others information are placed beside the spatial components in the output le data, such as the surface normal and the surface colour, which are useful to improve the object characterisation. The point clouds come from sensing devices such as RGB-D and Stereo cameras, 3D laser scanners and time-of-ight cameras or synthetically from software (e.g. Blender).

2.2.1 Point Cloud Library

In this work the point clouds will be used for the shape recognition am-bit and Point Cloud Library (PCL) will be exploited for this purpose. PCL is a standalone, large scale, open project for 2D/3D image and point cloud processing (in C++, w/ new python bindings). The PCL framework

contains numerous state-of-the art algorithms developed in C++including

ltering, feature estimation, surface reconstruction, registration, model tting and segmentation. The le format used by PCL to store the point dataset is the PCD (Point Cloud Data). Each PCD le contains a header that identies and declares certain properties of the point cloud data stored in the le, after which the points are listed in ASCII or binary format. Algorithms in PCL are subdivided in thematic modules, some of them are now summarized and integrated with the functions used in the pipeline.

Filtering

Here are contained outliers and noise removal mechanisms for 3D point cloud data ltering applications. For outliers is meant those points that are present in the cloud but come from measurement error. In the pre-sented code the following ltering function will be used:

• VoxelGrid lter

The VoxelGrid class creates a 3D voxel grid (a voxel grid is like a set of tiny 3D boxes in space) over the input point cloud data. Then, in each voxel (i.e., 3D box), all the present points will be approxi-mated (i.e., downsampled) with their centroid. This approach is a bit slower than approximating them with the center of the voxel, but it represents the underlying surface more accurately.

Surface

The aim is reconstruct the original surfaces from 3D scansions. Meshing algorithms, based on triangulation, smoothing and hole tting, are pro-vided together with algorithms for creating convex or concave hull aimed to represent a simplied surface or extract boundaries. In the presented code the following smoothing function will be used:

• Moving Least Squares surface reconstruction method

Some of the data irregularities (caused by small distance measure-ment errors) are very hard to remove using statistical analysis. To create complete models and glossy surfaces , occlusions in the data

2.2. POINT CLOUDS 9 must be accounted for. In situations where additional scans are im-possible to acquire, a solution is to use a resampling algorithm, which attempts to recreate the missing parts of the surface by higher or-der polynomial interpolations between the surrounding data points. By performing resampling, these small errors can be corrected and the double walls artefacts resulted from registering multiple scans together can be smoothed.

Registration

Combining several datasets into a global consistent model is usually per-formed using a technique called registration. The key idea is to identify corresponding points between the data sets and nd a transformation that minimizes the distance (alignment error) between corresponding points. This process is repeated, since correspondence search is aected by the relative position and orientation of the data sets. Once the alignment errors fall below a given threshold, the registration is said to be complete. Segmentation

For segmentation is meant to subdivide a point cloud in distinct clusters. In such cases, clustering is often used to break the cloud down into its constituent parts, which can then be processed independently. For exam-ple it is possible to subdivide a scene of a table with objects on it into the several objects leaned.

Other employed classes

The main classes and functions used for the construction of the pipeline are here listed:

• pcl::ModelCoefficients

It is a sample model consensus method in which the search method and the mathematical model must be chosen. In the proposed code it was used with the RANSAC (RANdom SAmple Consensus) method and with a plane model in order to nd the surfaces of the point cloud. It receives as input also a set of data and a threshold. Ran-domly it selects a subset from the input dataset. A tting model and the corresponding model parameters are computed using only the el-ements of this sample subset. The algorithm checks which elel-ements of the entire dataset are consistent with the model instantiated by the estimated model parameters obtained. A data element will be

considered as an outlier if it does not t the tting model instan-tiated by the set of estimated model parameters within some error threshold that denes the maximum deviation attributable to the ef-fect of noise. The process is repeated randomly and iteratively until suciently many points have been classied as part of the consensus set.

• pcl::KdTreeFLANN

k-d tree (k-dimensional tree) is a data structure that organises a set of points in a k-dimensional space, in a way that makes range search operations very ecient (for example, nding the nearest neighbour of a point, which is the point that is closest to it in space; or nding all neighbours within a radius).

• pcl::BoundaryEstimation

It estimates whether a set of points is lying on surface boundaries using an angle criterion. The code makes use of the estimated surface normals at each point in the input dataset.

• pcl::ExtractIndices

It extracts a set of indices from a point cloud. For indices is meant the list indices of the points inside the data le or inside the point cloud class.

• pcl::EuclideanClusterExtraction

It is meant to divide an unorganised point cloud model into smaller parts. Selecting the min and max dimension of the clusters and a tolerance value (e.g. the resolution of the cloud), through the nearest neighbours research, it nds all the parts of the cloud that are enough isolated from the others, such that they can be considered independent.

• pcl::computeCovarianceMatrixNormalized

It receives the cloud dataset together with the centroid and returns the covariance matrix normalised. Normalized means that every entry has been divided by the number of points in the point cloud. • pcl::computePointNormal

It estimates local surface properties at each 3D point, such as surface normals and curvatures. Through the nearest neighbour research the class selects a small number of neighbours for each points and com-putes the tting plane, from which the properties are then derived.

2.3. STATE OF THE ART 11 • pcl::ProjectInliers

It uses a model and a set of inlier indices from a PointCloud to project them into a separate PointCloud.

• pcl::pointToPlaneDistance

It gets the distance from a point to a plane, receiving as input the point and the plane coecients.

2.3 State of the art

The object recognition task has been largely developed during the last few decades, thanks the advent of sensors always more sophisticated but still at a relative low cost, and the growth of application elds, such as the agriculture, industrial, urban and space environments [10, 12, 13, 14], in which autonomous systems entailed several advantages. Thanks to new-generation depth sensors, a popular approach to tackle object recognition is to deploy 3D data, motivated by its inherently higher eectiveness com-pared to 2D images in dealing with occlusions and clutter, as well as by the possibility of achieving 6-degree-of-freedom.

2.3.1 Descriptors

For object recognition is meant the ability to identify and recognise an object inside an image, a point cloud or a video and estimate its pose. Each object is recognised through some features that are meaningful for the unique characterisation of it. A feature of a point is some character-istic that can help us to tell it apart from a dierent point and it is a compact  but rich  representation of our (3D) data. It is designed to be invariant (or robust) to a specic class of transformations and/or set of disturbances. Usually scale-invariance is not an issue but better if each feature is extracted together with its characteristic scale. For a feature to be optimal, it must meet the following criteria:

• It must be robust to transformations: rigid transformations (the ones that do not change the distance between points) like trans-lations and rotations must not aect the feature.

• It must be robust to noise: measurement errors that cause noise should not change the feature estimation much.

p

p

p

p

p

p

p

p

p

_p

p

p

p

p

p

p

p

p

Figure 2.3: Point pairs established when computing the FPFH descriptor for a point.

• It must be resolution invariant: if sampled with dierent density (like after performing downsampling), the result must be identical or similar.

This is where descriptors come in. They are more complex (and precise) signatures of a point, that encode a lot of information about the surround-ing geometry. In Figure 2.3an the FPFH (Fast Point Feature Histogram) descriptor is depicted. The FPFH tries to capture information of the geometry surrounding the point by analyzing the dierence between the directions of the normals in the vicinity The purpose is to unequivocally identify a point across multiple point clouds, no matter the noise, reso-lution or transformations. Also, some of them capture additional data about the object they belong to, like the viewpoint (that lets us retrieve the pose).

2.3.2 Key-points

Usually descriptors are applied on specic points, called key-points. Key-points (also referred to as interest Key-points) are Key-points in an image or point cloud that are stable, distinctive, and can be identied using a well-dened

2.3. STATE OF THE ART 13 detection criterion. Typically, the number of interest points in a point cloud will be much smaller than the total number of points in the cloud, and when used in combination with local feature descriptors at each key-point, the key-points and descriptors can be used to form a compact  yet descriptive  representation of the original data. The key-points have the following requirements for being meaningful enough:

• Distinctive, i.e. suitable for eective description and matching (globally denable)

• Repeatable with respect to point-of-view variations, noise, etc... (locally denable)

For example, as stressed in [17]:

• It must take information about borders and the surface structure into account.

• It must select positions that can be reliably detected even if the object is observed from another perspective.

• The points must be on positions that provide stable areas for normal estimation or the descriptor calculation in general.

2.3.3 Current approaches

Algorithms for 3D object recognition can be divided between local and global. Local approaches extract repeatable and distinctive key-points from the 3D surface of the models in the library and the scene, each be-ing then associated with a 3D descriptor of the local neighbourhood [18]. Scene and model key-points are successively matched together via their associated descriptors to attain point-to-point correspondences. Once cor-respondences are established, they are usually clustered together by taking into account geometrical constraints derived from the underlying assump-tion that model-to-scene transformaassump-tions are rigid. Clustered correspon-dences dene model hypotheses, i.e. subsets of corresponcorrespon-dences holding consensus for a specic 6DOF pose instance of a given model in the cur-rent scene. In Figure2.4 is shown an example of recognition process using key-points and descriptors.

Conversely, global methods, e.g., [16], compute a single descriptor which encompasses the whole object shape: this requires, in presence of clutter and/or occlusions, the scene to be pre-processed by a suitable 3D segmentation algorithm capable of extracting the individual object

(a) Carton of milk. (b) Identication of key-points.

(c) Association of descriptors to

the keypoints. (d) Correspondence between two similar ob-jects. Figure 2.4: Example of a recognition process with local descriptors.

2.3. STATE OF THE ART 15

Figure 2.5: Example of global descriptor applied in the centroid: VFH

instances. In Figure2.5 is shown an example of a global descriptor com-puted from the centroid and setting all the cluster's points as neighbours. Each methods distinguishes from the others according to the typology of the descriptor employed. Some use the dierence between the angles of the normals of the point and its neighbours, for example. Others use the distances between the points. Because of this, some are inherently better or worse for certain purposes. A given descriptor may be scale invari-ant, and another one may be better with occlusions and partial views of objects. In Table 2.2 pro and contra are summarised.

Others global techniques exploits the generality properties of the su-perquadratics [4]. A superquadric (see Figure 2.6) is an equation of a particular form whose solutions dene a closed surface. As the equation's two parameters are varied, the surface deforms through a range of shapes that includes cubes, diamonds, pyramids, and smooth, intermediate forms. Six more parameters are added to specify size along each axis, bending along two axes, and tapering along one axis, producing a family of parts extremely expressive.

There are also examples of pipeline algorithms that have the capacity of learn from the environment without any need of an a-priori knowledge or a mathematical model. For example in [19] is introduced a methodology for learning 3D descriptors from synthetic CAD-models and classication of never-before-seen objects at the rst glance. Being able to learn on CAD models has several advantages. Besides simplifying the training stage as there is no need for calibrated systems, there is the possibility to train a grasping robot to manage objects. Once a grasping robot recognises any of these objects on a real scene and their pose is fully estimated, the grasps learned o-line can be used to grasp the real object.

Descriptors PRO CONTRA

Local  Well suited to handle clut-ter and occlusions.  No notion of what an ob-ject is. They just describe how the local geometry is around that point.

 Can be vector quantized in codebooks.

 Segmentation, registra-tion, recognition in clutter, 3D SLAM.

Global  More descriptive on ob-jects with poor geomet-ric structure (household ob-jects...)

 Complete information concerning the surface is needed (no occlusions and clutter, unless pre-processing)

 Higher invariance, well suited for retrieval and cat-egorization.

Table 2.2: Global vs local descriptors.

2.3. STATE OF THE ART 17 * * *

Our work inserts itself in this contest but without using an actual descrip-tor as those described previously. It could be consider a local approach because it searches for some specic key-points and then analyses the sur-rounding clouds in order to classify them. The match is not made between descriptors and other models, but the key-points themselves establish the correspondences with a model embedded.

Chapter 3

Proposed method

The basic idea underneath the algorithm is based on the thesis that nding all the vertices of an object it is possible to derive which object we deal with. Indeed, since we focus on engineering objects, our hypothesis is that the samples are almost regular and convex solids. Thus for almost all the cases, we have a unilateral association between the number of the vertices and the type of the solid. The case of zero vertices excludes a large part of solids but can not identify a single one, so it will be necessary to take into account also the points onto the edges. This method has been chosen since it answers positively to the simplicity constrain that was established, from the mathematical point of view. Indeed no function is used neither to enclose the entire volume nor to follow the surfaces or the edges.

As of now the procedure will follow three macro steps:

1. Identication of the key-points (vertices plus other notable points) 2. Characterisation of the key-points, which allows to distinguish in

which way they are useful 3. Shape recognition

3.1 Strategy for vertices identication

In a generic solid a vertex is the result of the intersection of two or more edges; an edge, in turn, is identied by the intersection of two planes. From this depends, rst of all, the research of all the planes present in the cloud. The most used methods in literature, through which is possible to nd a plane in a point cloud, are based on least squares approaches. The one here applied parses the entire point cloud searching a subset

(a) (b)

Figure 3.1: Example how RANSAC technique recognises a mathematical model.

containing the maximum number of points belonging to a plane within a certain threshold, called inliers, and rejecting the points that don't match with the plane model (the outliers). The Figure 3.1 shows with a linear example how the algorithm works. It is able to nd the combination of points that most of all represents the given mathematical model, also in the presence of noise. The approach, through which the points are considered part of the plane, is based on the Random Sample Consensus (RANSAC) technique. It is an iterative and non deterministic algorithm that produces a reasonable result only with a certain probability, with this probability increasing as more iterations are allowed. The RANSAC algorithm was introduced by Fischler and Bolles in 1981. The cycling execution of this function allows to nd all the planes. Since the plane is identied for less than the threshold, this implies a certain uncertainty; indeed considering two adjacent planes and trying to identify the rst one, part of the second is considered as part of the rst, because now the plane has a thickness (see Figure 3.2).

This introduces an error in the identication of the corner when the planes will be intersected, that depends on the value of the threshold. It must be considered that this variable inuences the segmentation, since with a high value nding inliers for the plane model is simpler and the algorithm works better. This is the reason why in the presented code the plane-segmentation function is called twice sequentially but with two dierent threshold, the rst bigger than in the second call.

3.1. STRATEGY FOR VERTICES IDENTIFICATION 21

Threshold

Points wrongly considered belonging to the plane

Figure 3.2: Plane segmentation.

With regard to regular polyhedrons, this method can identify easily all the faces. Some issues arise when we deal with solids of revolution. Actu-ally in this case not all the surfaces are planar, but, since the segmented plane is dened through a threshold, is still possible to nd some plane. This is explained by the fact that the function considers as inliers all the points that have a distant from the ideal mathematical model of the plane within the specied tolerance, so these points can constitute a rounded surface but unless they are inside the thickness of the plane they belong to it. Generally these local-planes can also not be extended throughout the edges; the only constrain needed is that some of they must be tangent one to each other.

Now the next step is to use the found planes to identify all the points that lie on adjacent boundaries. In order to reduce the number of points to take into account, for each plane only the boundaries are selected and compared one to each other. If two boundaries have some points in com-mon, these latter become part of a line. In the case of polyhedrons the lines correspond to the corners while in general they can also not have any geometrical meaning. As a matter of fact in a cylinder there are no corners so the selected lines, deriving from the union of two planes, can be either the edges on the bases or random lines on the lateral rounded sur-face. In the rst case the extremities of the lines are really the searched key-points of the solid, since they lie on the circular edge, while in the

Lines on the surface Extremities on the surface Extremities already on the edge New key-points to be found from the surface extremity (a)

1

2

3

4

(b) Key-point pursuing process. Figure 3.3: Lines and extremities.

second case they can have no meaning if the line doesn't go through the whole height of the cylinder (see Figure 3.3a). The presence of points on the lateral surface is dictated by the eciency of the plane recognition process, and depends on the quality of the starting point cloud. Hence it is important to apply a methodology that allows to reach the edges starting from points on the surface. Moreover, due to the thickness of the planes and the possible noise of the cloud, generally the extremities of the lines not always constitute the points placed at the vertices. This issue is solved by adopting an algorithm (in the code it is implemented in the function vertexPursuit) that searches the vertices/key-points in the surrounding of the lines extremities. Following Figure 3.3b, the method starts from a neighbourhood of the rst point, looking for the point that has the maximum distance from the centre of the whole point cloud. In order to compute this centre it has been used a function that creates the minimal-radius-sphere enclosing all the points of the cloud. The centre of this bounding sphere is considered as the centre of the entire point cloud. Once the farthest point is found the research starts again, each time having as centre the last identied point, and goes on until the new point that is found coincides with the centre of the neighbourhood: this means that, locally, the farthest point is found. In this way it is possible to nd either the vertices on the corners and interesting points on the edges, which from now they all will be called key-points. The explained

3.2. CHARACTERISATION OF THE KEY-POINTS 23

Figure 3.4: Typologies of neighbours point clouds. In green the points distri-bution, in violet covariance ellipsoid and in yellow the key-point: a) surface, b) edge, c) border and d) corner.

vertices research exploits the k-nearest algorithm built in PCL. It uses a KdTree data structure, thought for organizing some number of points in a space with k dimensions.

∗ ∗ ∗

All the points identied belong to particular areas of the entire point cloud. As it is explained in [8] and showed in Figure 3.4, in specic they can be part of an edge, a border or a corner, depending on how the main point cloud is built and on the shape of the objects taken into account. The corner and the edges are 3D features while the border is considered at.

3.2 Characterisation of the key-points

Understanding to which category the portions of the cloud, hosting the key-points, are part of is fundamental for the object recognition, because they discriminate if a cloud has planar or rounded surfaces. The method here used exploits the properties of the covariance matrix together with the cloud curvature.

3.2.1 Covariance matrix

The variance on a set of data D = [x, y, z] provides a measure of how much the data are spread across the space:

V ar(x) = E(x − E[x])2 = σ(x, x), (3.1) where E[·] is the expected value. This variable can only be used to explain the spread of the data in the directions parallel to the axes of the space, but not for others orientations. Instead other correlations can be captured by extending the notion of variance to what is called the covariance of the data, dened as:

Cov(x, y) = E [(x − E[x]) · (y − E[y])] = σ(x, y). (3.2) The Equation 3.2 expresses a measure of the strength of the correlation between two or more sets of random variates. For uncorrelated variates the covariance is zero. All the covariances can be summarized in a matrix, called the covariance matrix:

Σ =  

σ(x, x) σ(x, y) σ(x, z) σ(y, x) σ(y, y) σ(y, z) σ(z, x) σ(z, y) σ(z, z) 

 (3.3)

If x is positively correlated with y, y is also positively correlated with x, hence:

σ(x, y) = σ(y, x) σ(y, z) = σ(z, y) σ(z, x) = σ(x, z) (3.4) Therefore, the covariance matrix is always a symmetric matrix with the variances on its diagonal and the covariances o-diagonal. Figure 3.5 il-lustrates how the overall shape of the data denes the covariance matrix. Eigenvectors {e0; e1; e2} and eigenvalues λ0 ≤ λ1 ≤ λ2 uniquely dene

the covariance matrix, and therefore the shape of the data. The largest eigenvector of the covariance matrix always points into the direction of the largest variance of the data, and the magnitude of this vector equals the corresponding eigenvalue. The second largest eigenvector is always orthogonal to the largest eigenvector, and points into the direction of the second largest spread of the data. So on for the third couple. The eigen-values represent the variance of the data along the eigenvector directions, whereas the variance components of the covariance matrix represent the spread along the axes. The eigenvectors {e0; e1; e2} of the correlation

matrix together with the corresponding eigenvalues {λ0; λ1; λ2}, where

λ0 ≤ λ1 ≤ λ2, dene the correlation ellipsoid that adopts the general form

3.2. CHARACTERISATION OF THE KEY-POINTS 25

Figure 3.5: The covariance matrix denes the shape of the data. Diagonal spread is captured by the covariance, while axis-aligned spread is captured by the variance.

3.2.2 Curvature

Taking into account solids of revolution, such as cones or cylinders, some identied key-point lies on the boundary of the basis. If the scan is com-puted without moving the object from the lean base, the resulting point cloud will be lacking of this part. Thus the key-points, instead of being in a edge (3D), will be on a border (2D) and the surrounding point cloud will be almost at instead of being three-dimensional. In Figure3.7clouds of 16 neighbours in border regions are showed, enlightening their planar nature. The red markers identify the key-points. Certainly this depends also on the main curvature of the entire object but with a neighbour cloud of only 16 elements it is not perceived. The dimension of the neighbour cloud has been chosen of 16 points as result of a sensitivity analysis aimed to well represent small features. It is possible to understand if a cloud is a border through its curvature. We dene it as

σn =

λ0

λ0+ λ1+ λ2 (3.5)

where n is the number of neighbours and λ0 quantitatively describes the

variation along the surface normal, i.e. estimates how much the points deviate from the tangent plane. For σn = 0 the cloud is a plane. The

maximum value σn = 1/3 is reached with completely isotropically

dis-tributed points. This type of curvature, named also surface variation, is not the best way for curvature estimation, as it is pointed out in [15], but for our purpose it is licit since we only need to know if a cloud can be approximated into a plane or not. In our code clouds having a curvature less than 0.02 are considered borders, all the others are managed as edges or corners.

3.2.3 Sub-clouds characterisation

The three eigenvectors of the covariance matrix dene the spread direc-tions of the cloud. Considering them as normals we can derive the cor-respondent planes, two of which have a useful geometrical meaning. The smallest eigenvector e0 denes a plane that, if centred in the centroid of

a cloud, ts in the best way all its points. Taking into account again Figure 3.4, the depicted vector in the quadrant a) is the the smaller eigen-vector and the green plane ts well the points described by their covari-ance ellipsoid (whose axes are the covaricovari-ance eigenvectors). Instead in the quadrants b−c) the depicted eigenvectors are the bigger ones, i.e. e2, and

3.2. CHARACTERISATION OF THE KEY-POINTS 27

(a)

(b)

direction. Applied to an edge-shaped cloud, the plane built by the small-est eigenvalue points to the edge rim. Hence using the second eigenvector e1 we obtain a plane that passes through the key-point and the ridge of

the edge and contains e0 and e2, which is parallel to the ridge since this

is the longest dimension. In this way this plane cuts the edge in two parts along the edge. The projection of the whole neighbours cloud on this plane returns a at cloud whose boundary has a linear section, corresponding to the ridge in the 3D cloud, and with in the middle the key-point (Fig-ure3.8). Instead, projecting on the same plane a corner neighbours cloud, the resultant cloud will have still a corner shape, with at the vertex the key-point (gure 3.9). It is sucient computing the angles between each sequential neighbours, in the projected cloud, and verifying that these are smaller, within a certain threshold, than 180 deg, in order to identify the cloud as a corner. At the end we obtain the exact number of the points at the vertices of the corners and a random number of points lying on the borders and/or on the edges.

3.3 Shape recognition from the key-points

Only with the number of the vertices we can deduce only polyhedral ob-jects, for others types we have to resort also to the others points belonging to edges and borders. Here below the recognition methods for each shape will be discuss. The only information exploited are the number, the po-sition and the typology of the key-points previously found. From now on every points talked about have to be considered as key-points. Table 3.1

shows the relationship between the number and the type of the points and the geometries.

Geometries sphere cylinder cone tetrahedron parallelepiped pentagon

Edges/border points x x x - -

-Corner points 0 0 1 4 8 10

Table 3.1: Shape recognition scheme.

3.3.1 Prism

In order to identify a straight prism, a random point (among the key-points) is selected together with two neighbours and the plane passing through them is computed. The cloud with the key-points is parsed and only the points with distance from the plane smaller than the threshold

3.3. SHAPE RECOGNITION FROM THE KEY-POINTS 29

e

e

e

(a) Plane generated by the second eigen-vector applied on an edge.

(b) Points belonging to an edged, projected on the intersecting plane.

Figure 3.9: Corner points projected on the plane.

(2 mm) are kept. If the number of inliers is equal or less than 4 the plane represents the lateral face. Thus the distances computed between the three points closer to the key-point and the key-point itself are the three main dimensions. Instead if the inliers are more than 4, the plane, tting them, represents or the bottom face or the top one. Thus the two main dimensions are computed through the two closer neighbours, while the third is the distance of one of the outliers respect to the tting plane considered. Refer to Figure 3.10 for exemplication.

Fitting plane Inliers Outliers Key-point Neighbours Main dimensions

Figure 3.10: Method for reconstruct a regular straight prism from its vertices

3.3.2 Cone

For what regard the cone recognition, at the beginning all the points are considered except the only point at the vertex. All the combinations made

3.3. SHAPE RECOGNITION FROM THE KEY-POINTS 31 by three points are selected and for each one we nd the radius associated to the circumference passing through them. Calling t, u, v the sides, in vectorial form, of a triangle with vertices p1, p2, p3, such that the origin is

shifted in p1

t = p2− p1 u = p3− p1 v = p3− p2, (3.6)

the circumradius r is found as

r = ktk kuk kvk 4kt × uk

2

(3.7) i.e. the fraction between the product of the triangle side lengths and the area of the triangle multiplied by 4. The circumcentre p0 is dened as

p0 = p1+ u ktk (u · v) − t kuk (t · v) 4kt × uk 2 2 (3.8) Computing the distance from the base-plane to the point at the vertex we can nd the height of the cone.

3.3.3 Cylinder

In the case of the cylinder, a random point is chosen among the amount of the key-points. Starting from it, all the combinations with others two points are considered and for each set we nd the plane passing through the points. For each plane, the distances of all the others points from the plane itself are computed and only those that are below a given threshold are kept. These points will be associated to the respective plane. The points lying on the plane having the maximum number of points associated with, will be considered as constituents of one of the cylinder bases. All the remaining points will belong to the other base. Through the same procedure used for the cone, we nd the radius of the circular bases. The height is computed as the mean distance of the points of one base from the plane including the other base.

3.3.4 Sphere

For regard to spherical objects, the method before-mentioned is not ex-ploited, instead it is used a simpler one made ad hoc. Since a sphere, or a

Fitting planes

Inliers Outliers Key-point Combinations

Figure 3.11: Method for reconstruct a regular straight cylinder from points on the edges

portion of it, is dened as `the set of all the points lying at the same dis-tance from the centre', the algorithm, before starting the above explained procedure, checks if the points belonging to the point cloud respect the sphere-criterion, under a certain threshold. Each point's distance from the centroid is compared with the radius of the bounding sphere. If the mean value approximately equals the bounding sphere radius within two times the cloud resolution and the standard deviation is less than 0.1, then the cloud is a sphere or a portion of it. If the check is negative the algorithm proceeds ahead, on the contrary it returns the the value of the mean radius of the sphere.

3.4 Filtering

The point clouds used for the recognition are the outcome of a previous cloud assembly, which makes the nal point cloud be non-uniform and not perfectly smooth. The rst anomaly is caused by the scanning device that has an orientation during the object acquisition, hence each point cloud has its own points orientation with a certain points density. When the clouds are merged, there will be regions in which the points became very close to each other and almost overlap, changing the density and moreover the cloud resolution. Indeed most of the functions, especially those that have to manage the neighbours points, receive the resolution as input, since this parameter governs the level of identiable details within the scanned point clouds. The resolution is computed by a function just after the ltering process as the mean distance of each point from its closer

3.4. FILTERING 33 neighbour. The second irregularity comes from the level of accuracy of the registration process and the clouds matching grade. Thus, before the en-tire recognition process begins, the cloud is ltered through two dierent algorithms with two dierent purposes. The rst ltering phase is accom-plished by a smoothing lter developed by the PCL community. It has the goal of make the surface glossy and smooth. Secondly the point cloud dataset is downsampled through a VoxelGrid lter that reduces the num-ber of points using a voxelized grid approach. 3D voxel grids are built over the input point cloud data. This allows to get rid of the points superposi-tion and clustering, restoring a more homogeneous dataset. Furthermore, downsampling the cloud means to speed up the calculation rates during the execution of the algorithms.

Chapter 4

Tests and Results

In this chapter, the verication of the proposed algorithm pipeline is pre-sented. Its aim is to identify primitives geometries that characterise ob-jects, consequently the code was implemented with the purpose of dealing with simple object typologies.

4.1 Laboratory activities and instruments

The work has been performed in the Space Mechatronic Systems Tech-nology (SMeSTech) Lab at the University of Strathclyde. It is aimed to advance research and development of mechatronic solutions for space ap-plications. Mechatronics has been established as key technology in devel-oping many intelligent systems and in particular for consumable products believing that there are much scope and opportunities for its applications in particular in space explorations to improve human being's current qual-ity of life and future survivals and possible expansion of living space, in facing limited and reducing resources on the Earth. The SMeSTech Lab, initially funded by the University of Strathclyde and International fund-ing, provides research expertise and undertakes projects in:

• Space robotics for in-orbit satellite services and refuelling

• Space mechatronic system development methodologies and tronic system modelling and simulation platforms to support mecha-tronic systems development

• Space systemhuman interaction and integration technology

• Novel and smart space mechanisms and mechatronic devices devel-opment and prototyping

Figure 4.1: Konica Minolta VIVID 9i 3D Laser Scanner and turntable.

• Mechatronic solutions for advancing manufacturing techniques for large, one-o and complex space systems

In the lab some experimental tests were carried out in order to prove the quality of the developed algorithm, Real objects were scanned and rep-resented as point clouds. The acquisition device used was a laser scanner and the objects were placed over an automated turntable (see Figure 4.1

and Table 4.1 for specications). The shapes under test were a paral-lelepiped, a box, a pentagon and a cone (two of them in Figure 4.2).

Other shapes (the cube, the cylinder, the sphere and another cone) have been tested only numerically without rely on real objects. Their point clouds were manually generated through parametric functions.

Measuring Method Triangulation light block method Scan Range 0.6 to 1.0 or 0.5 to 2.5

Laser Scan Method Galvanometer-driven rotating mirror Laser Class Class 2

Accuracy (X,Y,Z) ±0.05 mm Precision (Z, σ ) 0.008 mm Input Time (per scan) 2.5 sec Ambient Lighting Condition 500 lx

Table 4.1: Konica Minolta VIVID 9i 3D Laser Scanner specications.

4.1.1 Acquisition issues

Each object is scanned from four points of view and the respective point clouds were assembled together and then manually cleared from the macro

4.2. RECOGNITION PHASE 37

(a) (b)

Figure 4.2: The cone (a) and the box (b) used for the tests.

scale noise. This choice was made in order to focus only on the recognition process, leaving the ltering action to future implementations. Also the registration phase is not embedded in the present pipeline. It has been computed automatically by the Polygon Editing Tool of Konica Minolta. Thus the following numerical results strongly depends on the acquisition and registration phases. It results that the point clouds do not match perfectly the real objects, i.e. that implies that some zones of the cloud overlap generating a gap. This issue has been solved by using the smooth-ing lter algorithm described in Section 3.4, but an error respect to the real object was not totally eluded. Under these premises, good results have been obtained for almost all the objects tested, for what concern the key-points recognition task.

4.2 Recognition phase

In all the accounted objects, the plane segmentation nds enough tangent planes, both in the prisms and in the solids of revolution, such that it was possible to select the boundaries that they had in common, as it is proven in Figure4.3. The identied planes are marked in blu, the boundary lines in red and the tangent boundaries in green.

Figure 4.3: Planes recognised in a solid of revolution.

were set as 1.1 and 1.2 and selected through a trial and error method. In the case in which objects were not cleared from the noise, such as that coming from the ground reection or from inside walls, the algorithm can still nd planes but they could be not tangent to each others. The mug in Figures 4.4 was successfully analysed, once cleared from the handle (be-cause the algorithm is not suppose to work with such a feature) and from the noise. Therefore this methodology can be a starting base for a space object recognition task, such as tracking objects during a rendez-vous, since the satellites simple geometries and the deep space lacking of noise, well suit with the underlying code hypothesis. Also the cases in which robots or however robotic arms are employed to grasp and handle simple objects, such as the astronauts tools [21], could be included in the employ-ment eld. For those applications which do not allow or is diculty to obtain an all-rounded cloud, this code is to be improved with a single view recognition capability. For such types of geometries also the key-points research works successfully, identifying points on corners and edges at the maximum local distance from the centre of the entire cloud. The number of such points ideally should be two times the number of the lines iden-tied from the boundaries, but it could vary instead because the vertex pursuing function, cited in Section3.1and built to nd a global maximum in local neighbours clouds, depending on the dimension of the neighbour-hood cloud itself, could merge several points in a single one. These points are located initially at distinct extremities of the lines (see Figure 4.5) and the nal point, in which them all are merged, represents the one at maximum distance among all the points of the cloud composed by all the neighbourhood-clouds, in turn generated starting from the intermediate maxima points, merged together.

4.2. RECOGNITION PHASE 39

(a) (b)

Figure 4.4: The plane recognition phase in a mug before (a) and after (b) the cleaning. 1. Lines identified 2. Extremities with neighbourhood 4. Key-point 3. Local maxima Ref

(a) (b) Figure 4.6: Markers in synthetic point clouds.

synthetically built and acquired point clouds respectively. The common boundaries are highlighted in green while the planes are identied in blue. The red markers identify the position of the points at the end of the vertices identication process described in Section 3.1. It is worth noting that all the markers coincide with the vertices, in those objects in which they are present; instead they are located also on the edges in the objects characterised by rounded surfaces.

Achieving the well identication of all the key-points does not guar-antee the nal shape recognition. As a matter of fact, in Figure 4.8 the markers well identify the corners but the shape is impossible to recognise, because the cloud is aected by too much noise and the corners are not enough sharp and clear. The method regarding the sub-clouds character-isation is strongly based on the points distribution nearby the remarkable regions. Which means that it works if the cloud is spread in such a way that the plane, having as normal the mid-length eigenvector, intersects the ridge of the edge. This occurs selecting a proper number of points and when the points distribution has a signicant curvature, otherwise in the characterisation phase a corner cloud projection could resemble a edge projection or the eigenvectors will not be sorted properly, generat-ing a plane not well align and thus the recognition failure. Also this is consistent with the cited space applications.

Good results come instead from the other objects taken into account, characterised by sharper edges. The main dimensions calculated through the algorithm are very close to those of the point cloud acquired and

man-4.2. RECOGNITION PHASE 41

(a) (b)

(c)

Figure 4.8: Example of dicult recognition.

Cube Cylinder Sphere Point cloud 20 20 20 40 20 39.37

Measure 20 20 20 40 20 39.37 Err. % 0 0 0 0 0 0

Table 4.2: Dimensions of the synthetic point clouds.

ually measured. Tables 4.2 and 4.3 shows the average of these measures and the percent errors.

The dimensions of the synthesized cloud are calculated without errors. Also in the acquired clouds, in most of the measures, the error is not sig-nicant considering that each characteristic dimension, both in the cloud and in the calculus, is averaged with the others of the same type in the object.

Cone Pentagon Parallelepiped Point cloud 200 30 30 58 58 80 103 170

Measure 200.16 29.51 31.23 57.8 58.09 79.29 102.36 167.72 Err. % 0.08 1.62 4.1 0.34 0.16 0.89 0.62 1.34

4.2. RECOGNITION PHASE 43

4.2.1 Performances

The algorithm has been tested on a Linux machine (Kubuntu 15.04) with the characteristics summarised in the Table 4.4. It was tested also with a growing number of points having as cloud the cylinder and the cone, both manually generated. In the following graph, which shows the time-vs-points trend, it is possible to note that the algorithm also with some tens of thousands of points is reasonably fast.

Processor Intel Core 2 Duo P8600 Frequency 2.40 GHz

RAM 4 GB Operative system 64 bit

Table 4.4: PC specications. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 ·105 10 20 30 40 Number of points Time [s] Time performance Cylinder Cone

Chapter 5

Conclusions and future work

The method makes use of particular points selected on the surface through the analysis of their neighbourhood clouds and that corresponds to the vertices or the edges of the objects.

This paper has shown a preliminary methodology for the automatic recognition of object shape represented by unstructured point clouds. The data have been acquired from real objects through a laser scanner and then cleaned and registered before being analysed. The method researches and manages to nd key-points on the surface, characterised by well dened neighbourhood clouds. The investigation on the surrounding of these par-ticular points is carried out through a covariance analysis. At this regard we have also introduced an innovative method to distinguish edge-shaped from corner-shaped point clouds, based on an intersecting plane derived from the covariance eigenvectors. We believe that the algorithm presented in this paper can be the basis of many point-based space applications, such as grasping and handle tools, helping astronauts, identifying the motion of tracked satellite or debris, i.e. both on-orbit and on planets services. Our method is simple, fast and well succeeds to identify primitives geomet-ric shapes without requiring any previous reconstruction of the underlying surface. It is able to recognise parallelograms, pentagons, cones, cylinders, spheres and easily new shapes can be added to the repository.

Directions for future work include a better noise management and a more ecient plane segmentation method, beside to enlarge the number of geometries embedded. Moreover the method still lacks of a pose estimation algorithm.

Bibliography

[1] url: http : / / pointclouds . org / documentation / tutorials / resampling.php#moving-least-squares.

[2] Radu Bogdan Rusu and Steve Cousins. 3D is here: Point Cloud Library (PCL). In: IEEE International Conference on Robotics and Automation (ICRA). Shanghai, China, May 2011.

[3] Myron A Diftler et al. Robonaut mobile autonomy: Initial exper-iments. In: Robotics and Automation, 2005. ICRA 2005. Proceed-ings of the 2005 IEEE International Conference on. IEEE. 2005, pp. 14251430.

[4] Kate Duncan et al. Multi-scale superquadric tting for ecient shape and pose recovery of unknown objects. In: Robotics and Au-tomation (ICRA), 2013 IEEE International Conference on. IEEE. 2013, pp. 42384243.

[5] Peter Eisert. Reconstruction of Volumetric 3D Models. In: 3D Videocommunication: Algorithms, Concepts and Real-Time Systems in Human Centred Communication (2005), pp. 133150.

[6] Jon D Erickson et al. An intelligent space robot for crew help and crew and equipment retrieval. In: Applied Intelligence 5.1 (1995), pp. 739.

[7] Michael Goeller et al. Modular robots for on-orbit satellite servic-ing. In: Robotics and Biomimetics (ROBIO), 2012 IEEE Interna-tional Conference on. IEEE. 2012, pp. 20182023.

[8] Stefan Gumhold, Wang Xinlong, and Rob Macleod. Feature Extrac-tion from Point Clouds. In: In Proceedings of the 10 th InternaExtrac-tional Meshing Roundtable. 2001, pp. 293305.

[9] Ulrich Hillenbrand and Roberto Lampariello. Motion and param-eter estimation of a free-oating space object from range data for motion prediction. In: 8th International Symposium on Articial Intelligence, Robotics, and Automation in Space. 2005.

[10] AR Jimenez, R Ceres, JL Pons, et al. A survey of computer vision methods for locating fruit on trees. In: Transactions of the ASAE-American Society of Agricultural Engineers 43.6 (2000), pp. 1911 1920.

[11] Benoit P Larouche and Zheng H Zhu. Vision-Based On-orbit Ser-vice Robot. In: A A 21.22 (2012), p. 23.

[12] Elias N Malamas et al. A survey on industrial vision systems, ap-plications and tools. In: Image and vision computing 21.2 (2003), pp. 171188.

[13] Przemyslaw Musialski et al. A survey of urban reconstruction. In: Computer graphics forum. Vol. 32. 6. Wiley Online Library. 2013, pp. 146177.

[14] Nassir W Oumer and Giorgio Panin. 3D point tracking and pose estimation of a space object using stereo images. In: Pattern Recog-nition (ICPR), 2012 21st International Conference on. IEEE. 2012, pp. 796800.

[15] Mark Pauly, Markus Gross, and Leif P. Kobbelt. Ecient Simpli-cation of Point-sampled Surfaces. In: Proceedings of the Conference on Visualization '02. VIS '02. Boston, Massachusetts: IEEE Com-puter Society, 2002, pp. 163170. isbn: 0-7803-7498-3. url: http: //dl.acm.org/citation.cfm?id=602099.602123.

[16] Radu Bogdan Rusu et al. Fast 3d recognition and pose using the viewpoint feature histogram. In: Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ International Conference on. IEEE. 2010, pp. 21552162.

[17] Bastian Steder et al. Point feature extraction on 3D range scans taking into account object boundaries. In: Robotics and automation (icra), 2011 ieee international conference on. IEEE. 2011, pp. 2601 2608.

[18] Federico Tombari, Samuele Salti, and Luigi Di Stefano. Unique sig-natures of histograms for local surface description. In: Computer VisionECCV 2010. Springer, 2010, pp. 356369.

[19] Walter Wohlkinger et al. 3dnet: Large-scale object class recognition from cad models. In: Robotics and Automation (ICRA), 2012 IEEE International Conference on. IEEE. 2012, pp. 53845391.

[20] Wenfu Xu et al. Unied multi-domain modelling and simulation of space robot for capturing a moving target. In: Multibody System Dynamics 23.3 (2010), pp. 293331.

BIBLIOGRAPHY 49 [21] Enrica Zereik et al. Space robotics supporting exploration missions: vision, force control and coordination strategy for crew assistants. In: Intelligent Service Robotics 4.1 (2011), pp. 3960.