Active rough shape estimation of unknown objects

Claire Dune 1,2 , Eric Marchand1 , Christophe Collowet 1 ,Christophe Leroux2 Abstract-This paper presents a method to determine the rough shape of an object. This is a step in the development of a "One Click Grasping Tool", a grasping tool of everyday-life objects for an assistant robot dedicated to elderly or disabled. The goal is to determine the quadric that approximates at best the shape of an unknown object using multi-view measurements. Non-linear optimization techniques are considered to achieve this goal. Since multiple views are necessary, an active vision process is considered in order to minimize the uncertainty on the estimated parameters and determine the next best view. Finally, results that show the validity of the approach are presented.

I. MOTIVATIONS

Much technology remains to be developed to assist people with disabilities. Robotic assistance may help these people to recover some manipulation capabilities by achieving actions such as carrying, grabbing, picking up and moving objects [START_REF]World health organization assessment, classification and epidemiology group, international classification of functioning and disability[END_REF]. As the severity of the patient's handicap increases, the complexity of the devices to use increases. This requires significant efforts to simplify the interactions between the patient and these devices.

This paper presents our work and results produced on a "One Click Grasping Tool", a solution for grasping everyday life objects which only requires one click from the user. The aim of this work is to provide an intuitive tool able to seize objects presented in an unstructured manner and with no previously known shape [START_REF] Dune | One click focus with eye-inhand/eye-to-hand cooperation[END_REF]. The robotic system is a manipulator that can be mounted either on a wheelchair or on a mobile robot. It is equipped with a gripper and two cameras. One camera is mounted on the effector. The other one is mounted on the top of the wheelchair or on the mobile base and observes the scene. In a previous work [START_REF] Dune | One click focus with eye-inhand/eye-to-hand cooperation[END_REF] we have proposed a method that allows the user, through a single click, to select the object of interest in the remote camera view. After a search step, the effector camera is then automatically focused on the object.

However the system needs more information to achieve a relevant grasp of an unknown object in an unknown pose. This is the goalt of this paper. It is assumed that a convex rigid object can be grasped by aligning the gripper with its minimal dimension while being perpendicular to its major axis. These are the features that have to be recovered from a set of images of the object. Let us advocate that our goal is not to build an accurate 3D object reconstruction but to gather enough information to allow a manipulator to grasp it using visual servoing techniques.

Our approach is based on contour analysis and implicit 3D reconstruction methods. In this paper, the considered objects are modeled by quadratic functions. They have the property to project as conics that may be tracked over an image sequence. Then, the parameters of the quadric that fits the image data are estimated using non-linear minimization techniques. Depending of the taken views, some ambiguity may remain on the estimated parameters of the quadric. Hence, an active vision step is considered in order to minimize the uncertainty on the parameters estimation and determine the next best view.

II. RELATED WORK

In the past decades grasping of unknown objects has been investigated. This kind of application raises several issues. The first one is the selection of the information that is used to perform the grasping. The second one deals with an "exploration" task that allows sensors to get relevant information.

Regarding image based methods for grasping an unknown object, [START_REF] Hauck | Visual determination of 3d grasping points on unknown objects with a binocular camera system[END_REF] proposes to use stereo vision information to determine the grasping points. The object to grasp lies in a known scene. The object segmentation is performed by a simple image difference between the current view and the known background. Then the 3D skeleton of the object is computed and used to determine the grasping points. In [START_REF] Sanz | Grasping the notso-obvious: vision-based object handling for industrial applications[END_REF] a method to seize unknown plane dark objects on a white table is proposed. The grasping points are determined using the 2D moments. In [START_REF] Flandin | Visual data fusion for objects localization by active vision[END_REF] the ellipsoid that best fits an object set on a textured background is found. A parametric motion estimation algorithm [START_REF] Odobez | Robust multiresolution estimation of parametric motion models[END_REF] is used to detect the object that is not in the major plane of the scene. Then, using a probabilistic scheme, the ellipsoid that is inside the intersection of all cones generated by the image contours is computed.

In [START_REF] Saxena | Robotic grasping of novel objects using vision[END_REF] the grasping points of an object of unknown shape are defined by using a learned model data base. Five categories of object shapes and their grasping points are learnt. When a new object has to be grasped, it is associated to a category which determines its grasping points. Given these five models, a huge variety of objects are grasped in unstructured environments.

In [START_REF] Whaite | Autonomous exploration driven by uncertainty[END_REF] the object is represented by a set of superellipsoids. A laser sensor is servo in such a way to reduce the uncertainty on the estimated 3D functions. Even if it deals with the different field of object recognition, this approach can be related to ours. While this technique is based on the 3D points provided by a laser range finder, our technique used 2D information extracted from a set of views of the object.

Our method uses no a priori knowledge about the object except that it is roughly convex. We assume that the necessary features to perform a proper grasp are the following: the object major axis, its centroid position and its rough size. These features are contained by the quadric that best fits the object. To solve the first problem the parameters of this quadric are estimated in a determinist way using the 2D apparent contours extracted from the views of the object. The exploration problem is solved in a similar way to the solution proposed by [START_REF] Whaite | Autonomous exploration driven by uncertainty[END_REF]. The camera is controlled to reduce the uncertainty of the estimated parameters.

III. MODELING ISSUE

This section proposes a method to describe an object using a compact representation based on the computation of the quadratic function that best fits 3D shape of the object. The aim is to find the major object axis orientation, the position of its centroid and its approximate scale. Such information is critical for a grasping task.

A. The quadric representation

Let h( w X, w Q) be the quadric where w X is a 3D point expressed in the world frame R w and w Q = ( w q 0 , . . . , w q 9 ) its parameters. Let us note that in the reminder of the paper Q is expressed, if not specified, in R w . The equation of a quadric h has the following expression:

h = X Γ X, (1)
where Γ is the symmetric positive matrix associated to the quadric:

Γ =    
w q 0 w q 3 w q 4 w q 6 w q 3 w q 1 w q 5 w q 7 w q 4 w q 5 w q 2 w q 8 w q 6 w q 7 w q 8 w q 9

    (2)

B. Computation of the object features

Given the parameters Q of the quadric in R w , the features needed for the grasping can be computed (see Fig. 1). The centroid of a quadric is the point X c where all the partial derivative

∂ h ∂ X , ∂ h ∂Y , ∂ h ∂ Z are null.
The inertia axes of the object can be found by considering the eigen space associated with w Γ q . The major axis direction is the eigen vector related to the largest singular value and the small axis is related to the smallest singular value.

C. Projection in the image plane

the perspective projection equations (x X/Z, y = Y /Z) and given that the contour generator is a set of points of the quadric surface at which rays are tangent to the surface, it can be shown that the projection of a quadric in the image plane is a conic:

g(x, c) = x γ x (3)
where the parameters c = (k 0 , k 1 , k 2 , k 3 , k 4 , k 5 ) are related to the parameters of the quadric expressed in the camera frame as follows:

k 0 = c q 6 2 -c q 9 c q 0 k 1 = c q 7 2 -c q 9 c q 1 k 2 = c q 6 c q 7 -c q 9 c q 3 k 3 = c q 6 c q 8 -c q 9 c q 4 k 4 = c q 7 c q 8 -c q 9 c q 5 k 5 = c q 8 2 -c q 9 c q 2 (4)
Hence, we can compute the c parameters of the projection of a quadric in the image plane knowing the position of the camera and the Q quadric parameters. At the opposite, if we know a set of positions and the set of c parameters of some conics measured for these positions of the camera, we can infer the parameters Q of the corresponding quadric in the world frame.

IV. ROUGH SHAPE ESTIMATION FROM MULTIPLE VIEWS

Given some views of an object and the positions from which they have been taken, we aim to find which quadric best fits the shape of the object. Figure 2 presents the general fitting scheme. The yellow ellipsoid is the quadric that best fits the real object, whereas the red ellipsoid is the currently estimated quadric. In each view, an image processing algorithm gives us a set of 2D points x (in green) that are on the apparent contour of the object. Thus the fitting process consists in fitting the projection of the reel quadric with the green measured conic.

A. Conic parameters from 2D measurements

From a general point of view, given a set of points x(x, y, 1) detected on the object apparent contour (see section VI), it is possible to estimate the parameters of the conic that best fits this set of points by solving a least square problem [START_REF] Zhang | Parameter estimation techniques: A tutorial with application to conic fitting[END_REF].

In every object view, we measure the best fitting conic of parameters c and we store it along with the position from which the view has been taken as data set.

B. Cost function

Given a set of initial estimated parameters Q and a set of positions, we compute the estimated projection ĉ. We try to fit the real measurement c with the estimated projection ĉ. The cost function to minimize is thus:

f ( Q) = χ 2 ( Q, x) = ∑ i j (ĉ i j -c i j ) 2 σ i ( 5
)
where i ∈ [0, 5] is the index of the i th parameter and j ∈ [0, N] the index of the j th view. The cost function can also be written in a matrix form as the matrix F of dimension dim(F) = (6N, 1) which rows i are ĉic i and where N is the number of views we took. The corresponding Jacobian matrix is

J = ∂ c ∂ Q of dimension dim(J) = (6N, 10
). Coefficients Q are estimated solving a non-linear system. Considering non noisy data, the cost function is quadratic in the neighborhood of Q * and its minimum value can be obtained using least square estimation techniques. To ensure the uniqueness of the solution we set the x axis related coefficient to q 0 = 1, i.e., we normalize all the coefficients by q 0 = 01 .

There are several methods to update the estimated parameters during the optimization, among them, let us focus on the Gauss-Newton and the Levenberg-Marquardt approaches:

• Gauss-Newton:

Q k+1 = Q k -α k H k ( Q k ) -1 ∇ f ( Q k ) (6)
• Levenberg-Marquardt:

Q k+1 = Q k -(H k ( Q k )) + v k D k ) -1 ∇ f ( Q k ) (7)
In both cases

H k ( Q(k)) = J( Q k ) J( Q k ) is the Hessian of the cost function and ∇ f ( Q k ) is defined by ∇ f ( Q k ) = J( Q k ) F( Q k ).
On one hand, the Gauss-Newton step needs a linear estimation, in the downhill direction, of a criterion α that can be time consuming while, on the other hand, the Levenberg-Marquardt method requires the computation of the parameter v k .

When dealing with noisy data, computing the downhill direction given by H -1 J T F of the Gauss-Newton method becomes a real issue as soon as the Hessian matrix becomes ill conditioned and lead to a divergence of the minimization. For its part, Levenberg-Marquardt algorithm may require many iterations leading to a slower convergence. Thus we propose to use a mixed method between Levenberg-Marquardt and Gauss-Newton. It uses a step of Levenberg-Marquardt when the matrix is ill conditioned otherwise a Gauss-Newton step is considered.

An estimation error may also arise from the 2D conics measured in the views. To cope with the views for which the conics are ill measured, due to the noise, we propose either to use a robust estimation technique [START_REF] Malis | Experiments with robust estimation techniques in real-time robot vision[END_REF] to give a higher weight for the "good views" and a lower weight for the "outliers views" or to remove the views that are the more ambiguous at the end of the estimation process. [START_REF] Whaite | Autonomous exploration driven by uncertainty[END_REF] shows that at a given camera position, and for some estimated parameters Q, the uncertainty U( w M c , Q) on the parameters Q is:

U( w M c , Q) ∝ J T CJ ∝ J T H -1 J (8)
Hence, we can use the U value either to remove the views that are the more ambiguous or use a robust estimation over all the views.

V. CLOSING THE LOOP:

COMPUTING OPTIMAL CAMERA MOTIONS
We have shown that the Q parameters of the currently estimated quadric can be inferred from several views of an object. However it can happen that the current views do not provide enough information to accurately compute the parameters. For example, when the successive positions of the camera are too close to each other, the information on the object depth is not reliable and the parameters related to it may be ill estimated although the measured and estimated conics fit perfectly in each image plane.

Thus, in order to refine the estimation of the parameters, more views need to be taken. The issue is then to find a criterion that can help us to compute the best direction for the camera motion. We now look into active reconstruction methods.

As shown in [START_REF] Whaite | Autonomous exploration driven by uncertainty[END_REF], it is possible to use the uncertainty on the estimated parameters as a criterion to control the camera displacement. The Shannon entropy can be related to covariance matrix C of the estimated parameters. In [START_REF] Whaite | Autonomous exploration driven by uncertainty[END_REF] the authors show that the best next direction can be obtained by minimizing det(C), i.e.by finding the view where the uncertainty decrease the more or the parameters vary the more.

The determinant of the covariance matrix for the iteration k in the optimisation process can be defined as:

det(C k ) = det(H k ) -1 (9)
Besides, [START_REF] Whaite | Autonomous exploration driven by uncertainty[END_REF] shows that the Hessian matrix can be computed as the sum of the Hessian for each view:

H k+1 = H k + J T k+1 J k+1 ( 10
)
where J k+1 is the Jacobian matrix associated to the next tried view. It is directly related to the position w M ck+1 and the currently estimated parameters Q.

Then the next best location is

w M ck+1 = arg max w M c (det(H k + J k+1 J k+1 )) (11)
The relation between det(C) and the uncertainty is true in the neighborhood of the current sensor position, where the linear approximation of the function is true [START_REF] Whaite | Autonomous exploration driven by uncertainty[END_REF]. The mobile camera velocity is computed so as to move in the direction of the next best view. Yet it can be noticed that as soon as one parameter is well estimated its related eigen value is zero. Consequently the determinant det(C) is also zero even if the other parameters are badly estimated. Hence we propose to use an other criterion that is the Froebenius norm of C, that is the sum of the squared eigen values of the positive symetric C matrix. Besides, computing this criterion is less time consuming than computing the determinant. Some results are shown in the next section. The determination of the next camera location is a non linear minimization problem without analytic Jacobian computation. To tackle this issue, we have chosen to use the Simplex method of Nelder and Mead. This method only requires some evaluations of the cost function at some points that are the vertices of the current Simplex. Using this approach, only the translational velocity is computed. The rotational velocity is computed so as to keep the projection of the centroid of the estimated quadric in the center of the image plane by using a visual servoing scheme [START_REF] Espiau | A new approach to visual servoing in robotics[END_REF].

VI. DETECTION OF THE OBJECT CONTOUR IN THE IMAGE

PLANE

We proposed here to use active contours to extract the points required to compute the 2D conics as described in section IV-A. Indeed, since their first introduction [START_REF] Kass | Snakes: Active contour models[END_REF], active contours have proven to be very powerful in various contexts, including edge detection and target tracking.

They are deformable curves which are defined in an image domain and move under the influence of internal forces coming from the curve itself and external forces generated from the image (typically gradient information for edge detection). We consider here a curve parameterized by a vector a: C a (x(u)). This curve moves according to the evolution of the components of a [START_REF] Terzopoulos | Dynamic 3d models with local and global deformations: deformable superquadrics[END_REF], [START_REF] Bascle | Tracking complex primitives in an image sequence[END_REF], [START_REF] Brigger | B-spline snakes: a flexible tool for parametric contour detection[END_REF] while, with traditional methods (i.e.points-based), the curve directly moves from points, then these latter approaches are local. Conversely, using a parametric formulation C a implicitly introduces global constraints. Consequently, they are usually more robust, especially when dim(a) is low. They are also more suitable for control issue. Indeed, the computation duration is greatly reduced.

We define C a (x(u)) by a polar description:

C a (u) : x(u) = x c + ρ a (u) cos u sin u ( 12
)
with u ∈ [0, 2π], x c being a point inside the contour. Besides, we perform a Fourier expansion of the radius ρ a (u):

ρ a (u) = a 0 + k=h ∑ k=1 a k cos ku + b k sin ku ( 13
)
where h is the number of harmonics. Thus, we have here

a = (a 0 , • • • , a h , b 1 , • • • , b h ).
To derive the evolution equations of a, the problem is set as the minimization of the curve energy E(a) with respect to the parameters a, leading to the following simplified associated Euler-Lagrange equation:

γ i da i dt + ∂ E ∂ a i = 0 ( 14
)
where the curve is supposed to be massless and embedded in a viscous medium of viscosity γ i . our case, we only consider an external energy term E(a) = E ext (a), that we write:

E ext = - C a ∇ ∇ ∇I(x(u)) n(u)du. (15)
where n(u) is the outward unit normal of C a in u. Note that ∇ ∇ ∇I(x(u)) must also be computed as an outward vector. To be more robust against the initialization of C a , we also consider a similar pressure force as described in [START_REF] Cohen | Finite-element methods for active contour models and balloons for 2-d and 3-d images[END_REF]:

f p = k 1 n(u) (with k 1 a scalar).

VII. EXPERIMENTAL RESULTS

This section presents a typical execution of the application presented above. The experimental set up is shown in Figure 3. The mobile camera is mounted on the end effector of a 6-DoF robot arm. Although we do not use any a priori knowledge about the object or about the scene, the method uses some heuristics. Firstly, the object is assumed to be roughly convex. Secondly, the object can be segmented from the background using an active contour. Fig. 3. Experimental set up: a mobile manipulator equipped with an eye in hand camera. An object which shape is a priori unknown lies in a scene with a textured background.

A. Object segmentation and conic feature in 2D image.

The object is segmented from the background using the method presented in Section VI. One of the main issue when using active contours to detect an object is the initialisation step. For the purpose of our application, the aim would be to initialise the snake using only the user click on the image of the remote view. In a previous work [START_REF] Dune | One click focus with eye-inhand/eye-to-hand cooperation[END_REF], we have shown how to estimate the position of an object in the world frame from one click of the user. Using this estimation and the current position of the camera, the estimated position of the object can be projected in the mobile view and the neigborhood of this projection can be used as the initialisation for the snake.

Figure 4 shows that the segmentation is robust even in the case of a cluttered background. The two images of the top show the snake itself and the two other images show the conic fit. Even if the object is not an exact quadric, we can notice that the long axis of the conic is approximately the object long axis and that the size can be roughly estimated.

B. Quadric estimation

Assuming an initial rough estimation of the position of the object using the approach described in [START_REF] Dune | One click focus with eye-inhand/eye-to-hand cooperation[END_REF], the initial set of Q parameters are those of a sphere of radius the width of the gripper (8cm) and centered on the estimated position of the object. The projection of the estimated location can also be used to create the seed for the active contour in the effector camera view.

Considering a motion of the camera on a view sphere around the object, images are acquired, conics are extracted and finally a set of Q parameters is computed. Although correctly estimated from the available data, some ambiguities may remain on the quadric parameters especially when the views are close to each other, the object depth may be ill defined.

C. Selection of the next best direction

In order to reduce the remaining ambiguities in the quadric parameters estimation, we need to take more measurements, and to move the camera as described in section V. The next camera motion is computed in order to reduce the entropy on the parameters set. To do so, the camera is controlled toward the region where the parameters are the most likely to change i.e.region where the ambiguity is high. Fig. 6. The object has been seen from several views and a quadric that best fits its 3D shape has been estimated. However some ambiguities remain on the parameters and another view need to be taken. Those two vision spheres show the location where the ambiguities are the highest in hot colour. the left vision sphere is obtained by using the determinant criterion whereas the right one is obtained using the sum criterion.

Figure 6 highlights the regions on a view sphere where the ambiguity of the parameter set is high (hot colors) and those where the ambiguity is low (cold colors). The left sphere depicts the determinant of the estimated Hessian if the camera were moved on this position at the next step, i.e.the product of the eigen values of H. The right sphere represents the Frobenius norm of the eigen values of H if the camera were moved to these locations. We can see that many regions are in dark blue in the left sphere. This is due to the fact that a view is considered to have a low uncertainty as soon as one eigen value comes to zero whereas the other can still be high. Using the sum of the eigen values instead of the products tackles this issue.

Figure 7 illustrates the motion of the camera using both criteria. The use of the determinant results in an eratic path whereas the use of the sum results in a smooth path on the view sphere. The parameters of the quadric are found within approximately 10 views.

Figure 8 shows the evolution of the cost function and parameters over the time when adding new views. Adding Fig. 7. Camera motion along the reconstruction process. The red path is the one found using the determinant criterion and the green path is the one found while using the sum of the eigen values criterion new views leads to find a better estimation of the parameters Q. If some ambiguity remains new views may be taken until the Q parameters do not vary any more.

Along with the estimation of the quadric parameters, the object frame can be computed. Figure 9 shows some results obtained for different objects. The blue array is the major object axis, while the red array is the small object axis. The estimated quadric is projected in the view as the yellow conic. The red ellipse is the currently measured conic. Knowing the object frame we can perform a 3D servoing to align the gripper with the object frame and grasp it.

VIII. CONCLUSION

In this paper, we have proposed an efficient solution to estimate the shape of an unknown object in order to grasp it with a robotic system. The object shape is approximated by a quadric surface whose parameters are estimated using multiple views of the scene. During the acquisition phase, the robot motions are continuously optimized in order to minimize the uncertainty on the estimated parameters by selecting the next best view. Wrt many classical solutions, our reconstruction process is directly based on the contours of the object in the image. The solution is thus very fast, allowing to compute the object shape in real time and to use it in a closed-loop grasping task with the robot. The proposed solution is fully generic and works for any roughly convex object.

Fig. 1 .

 1 Fig. 1. Quadric Frame

Fig. 2 .

 2 Fig. 2. Quadric fitting scheme

Fig. 4 .

 4 Fig. 4. Some results of contour extraction and conic fitting using active contours

Fig. 5 .

 5 Fig. 5. a) Evolution of the quadric parameter estimation over the time for simulation data. b) Initial state: The camera positions are represented as small pyramids, the initial guess is represented in blue and real object in represented in red. c) Final state. The final estimation (in blue) fits the real object.

Figure 5

 5 Figure5shows the evolution of the Q parameters over the time for simulation data. It shows the initial guessed state and the final state computed using the projection of the real object in the camera views surrounding the object. The curves are smooth and the parameters of the quadric converges towards the real values. The left part of Figure8wrt the dotted line shows the estimation of the parameters of the quadric for real data. Because of the measurement noise, there is more overshoot before the optimisation process converges to the best values. TableIshows some results for different optimisation methods. The Levenberg-Marquardt method and our method give better results than the Gaussian estimation process.

Fig. 8 .

 8 Fig. 8. Evolution of the quadric parameters estimation over the time for real data. The dotted line represents the time where an additional view has been taken. Every parameter changes until a minimum is reached.

Fig. 9 .

 9 Fig.9. Results of the optimisation process. The object frames are projected in the last view along with the currently measured conic (in red) and the estimated conic in yellow. The blue array is the major axis and the red array is the minor axis of the object.

  TableIshows some results for different optimisation methods. The Levenberg-Marquardt method and our method give better results than the Gaussian estimation process.

	Method	final cost	# iteration	norm of error
	Levenberg-Marquardt	7.35e-13	7	0.089
	Gauss-Newton	2.87e-10	101	0.126
	GN robust	8.64e-06	101	0.034
	LM robust	5.20e-06	101	0.191
	Considered approach	5.60e-13	27	0.081
		TABLE I
	RESULTS OBTAINED ON QUADRIC PARAMETER ESTIMATION FROM 6

VIEWS USING VARIOUS MINIMIZATION TECHNIQUES

INRIA Rennes-Bretagne Atlantique, Lagadic, Rennes, France

CEA List, F-92265 Fontenay Aux Roses, France This work has been done at IRISA-INRIA Rennes in collaboration with CEA List. It was also supported by CEA and by Brittany County Council under contribution to student grant.

This can be done without loss of generality because the cases where q 0 = 0 are degenerate quadric that cannot represent a real 3D object.