Eric Marchand
email: marchand@irisa.fr

Franois Chaumette
email: chaumett@irisa.fr

Active sensor placement for complete scene reconstruction and exploration

This paper deals with the 3D structure estimation and exploration of a scene using active vision. We have used the structure from controlled motion approach to obtain a precise and robust estimation of the 3D structure of geometrical primitives. Since it involves to gaze successively on the considered primitives, we have developed perceptual strategies able to perform a succession of robust estimations without any assumption on the number and on the localization of the different objects. An exploration process centered on current visual features and on the structure of the previously studied primitives is presented. This leads to a gaze planning strategy that mainly uses a representation of known and unknown areas as a basis for selecting viewpoints. The proposed strategy ensures the completeness of the reconstruction.

Overview

Many applications in robotics involve a good knowledge of the robot environment. For such applications, the aim of this paper is to obtain a complete and precise descripcvption of a static scene using the visual data provided by a camera mounted on the end effector of a robot arm. The idea of using active schemes to address vision issues has been recently introduced [START_REF] Aloimonos | Active vision[END_REF] [START_REF] Bajcsy | Active perception[END_REF]. Active vision is defined in [START_REF] Bajcsy | Active perception[END_REF] as an intelligent data acquisition process. Since the major shortcomings which limit the performance of vision systems are their sensitivity to noise and their low accuracy, the aim of active vision is generally to elaborate control strategies for adaptively setting camera parameters (position, velocity,. . . ) in order to improve the knowledge of the environment [START_REF] Aloimonos | Active vision[END_REF]. Here, the purpose of active vision is handled at two levels: a local aspect where active vision is used to constrain the camera motion in order to improve the quality of the reconstruction results, and a global aspect which is used to explore the unknown areas [START_REF] Marchand | Stratégies de perception par vision active pour la reconstruction et l'exploration de scènes statiques[END_REF].

The method we have used to estimate the 3D structure of the objects assumed to be present in the scene is fully described in [START_REF] Chaumette | Structure from controlled motion[END_REF]. It is based on the measure of the camera velocity and the corresponding motion of the object in the image. More precisely, we use a "structure from controlled motion" method which consists in constraining the camera motion in order to obtain a precise and robust estimation of 3D geometrical primitives such as points, straight lines and cylinders [START_REF] Chaumette | Structure from controlled motion[END_REF]. If p is the set of parameters describing the 3D structure of a primitive, we have:

p = p(P , Ṗ , Tc) (1)
where:

• p is the estimated value of p;

• P is the set of parameters describing the 2D position of the perspective projection of the primitive in the image; • and Ṗ is the measured time variation of P due to the applied camera velocity Tc. This approach has been applied to the most representative primitives (i.e., points, straight lines, circles, spheres and cylinders) [START_REF] Chaumette | Structure from controlled motion[END_REF]. As far as cylinders are concerned, this method provides the 3D orientation and position of their axis, as well as their radius. For a segment, it provides the 3D orientation and position of the straight line to which the segment belongs. When no particular strategy concerning camera motion is defined, important errors on the 3D structure estimation can be observed. This is due to the fact that the quality of the estimation is very sensitive to the nature of the successive camera motions. An active vision paradigm is thus necessary to improve the accuracy of the estimation results by generating adequate camera motions. It has been shown in [START_REF] Chaumette | Structure from controlled motion[END_REF] that two vision-based tasks (called fixation and gazing tasks) have to be realized in order to obtain a robust and non biased estimation. The visual servoing approach [START_REF] Espiau | A new approach to visual servoing in robotics[END_REF] is perfectly suitable to perform such tasks. Dealing with cylinders or segments, they must appear centered and vertical (or horizontal) in the image [START_REF] Chaumette | Structure from controlled motion[END_REF].

As far as the global aspect of our reconstruction scheme is concerned, active vision is used to determine the location of the next camera position in order to obtain a complete model of the scene. Previous works have been done in order to answer the "where to look next" question. Differences can be done if the complete geometrical description about the scene is known [START_REF] Cowan | Automatic sensor placement from vision task requirements[END_REF][13] and if the sensor is in an unknown environment. In that case, it raises the problem of autonomous exploration [START_REF] Connoly | The determination of next best views[END_REF][7] [11][15][17] [START_REF] Whaite | Autonomous exploration: Driven by uncertainty[END_REF]. In [START_REF] Connoly | The determination of next best views[END_REF], the sensor placement is computed from a local map of the scene which is described by an octree. The proposed solution, called the "planetarium algorithm", gives for all camera positions on a sphere located around the scene, the viewpoint from which the maximal amount of unexamined area will be visible. In [START_REF] Maver | Occlusions as a guide for planning the next view[END_REF], Maver and Bajcsy use information given by occlusions to plan the next viewing direction. In [START_REF] Wixson | Viewpoint selection for visual search[END_REF], Wixson describes strategies to search for a known object in a cluttered area. Three strategies for sensor placement are studied and compared: the "model-based strategy" based on the Connoly's algorithm, the "occlusion-based strategy" which uses occluding edges to restrict attention to areas that have not been checked yet, and a strategy which simply rotates the camera around the scene with a fixed rotation increment. In [START_REF] Kutulakos | Provable strategies for vision-guided exploration in three dimensions[END_REF], Kutulakos presents an approach for exploring a 3D surface, using a mobile monocular camera, which is based on the use of the occlusion boundary. In [START_REF] Whaite | Autonomous exploration: Driven by uncertainty[END_REF], Whaite and Ferrie present a system which creates a 3D model of the environment using the data gathered by a laser range-finder system through a sequence of exploratory probes. Our concern is to deal with the problem of recovering the 3D spatial structure of a whole scene without any knowledge on the localization, the number, and the dimensions of the different geometrical primitives of the scene (assumed to be composed of polygons, cylinders and segments). Since the proposed structure estimation method involves fixating at and gazing on the different primitives in the scene, this can be done on only one primitive at a time, hence reconstructions have to be performed in sequence for each primitive of the scene. Our incremental strategy leads to an exploration process which is handled at two levels:

• When a new primitive appears in the field of view of the camera, or has been previously observed, it is estimated. In that case, we do not need to compute explicitly new viewpoints. This level is called local exploration. It allows to split the observed areas into free-space and reconstructed objects. • When a local exploration ends, a more complex strategy has to be implemented in order to focus on parts of the 3D space which are occluded or have not been already observed. This level is called global exploration.

Incremental scene exploration

As already stated, the scene is assumed to be only composed of polyhedral objects and cylinders, so that the contours of all the objects projected in the image plane form a set of segments. The first step in the scene reconstruction process is to obtain the list of these segments. We denote these lists ω φt = {Si, i = 1 . . . M }, where φt is the corresponding camera location from which the M segments Si are observed. For real time issue, we cannot create a list at each iteration of the estimation process. So, they are created after each reconstruction, and are used for the selection of the next considered segment.

An other list, denoted Ω T t 2

t 1
, is used. It contains all the untreated segments previously observed, and the camera positions φ k from which they have been observed. More precisely, we have:

Ω T t 2 t 1 = {(Si, φ k ), i = 1 . . . N, k ∈ [t1, t2]} where • T t 2 t 1 = {φt 1 , φt 1 +1, .
. . , φt 2 } is the set of all viewpoints between t1 and t2. Initially, T 0 0 = {φ0} is the first camera location.

• Si is a 2D segment associated with an unestimated primitive and φ k is the camera location from which it has been observed. φ k belongs to T t 2 t 1 . N is the number of untreated segments. Using these two sets of segments it is possible to define an incremental reconstruction strategy:

Step 0 Initialization.

We consider that the camera is located in φ0 and ω φ 0 is acquired. We do not have any information about the parameters of the corresponding 3D primitives. Therefore the 3D map of the scene is initially empty: Ω T 0 0 = ω φ 0 = {(Si, φ0), i = 1 . . . n} and T 0 0 = {φ0}. We extract from ω φ 0 a segment Si to be estimated.

Step 1 Active 3D estimation and 3D map creation. Let us consider now that the camera is located in φt, (φt = φ0 if this is the beginning of the exploration process). An estimation based on Si is performed, including a recognition process [START_REF] Marchand | Controlled camera motions for scene reconstruction and exploration[END_REF] (does this segment correspond to a 3D segment or to a cylinder ?), the structure estimation process (see previous section and [START_REF] Chaumette | Structure from controlled motion[END_REF]) and the estimation of the primitive length [START_REF] Marchand | Stratégies de perception par vision active pour la reconstruction et l'exploration de scènes statiques[END_REF]. The obtained parameters p of the primitive are introduced into the 3D global map of the scene. We then remove from Ω T t 0 all the 2D segments, corresponding to this estimated primitive.

Step 2 Local and global 2D lists generation. After the active estimation, because of the camera motion implied by this process (see [START_REF] Chaumette | Structure from controlled motion[END_REF]), the camera is located in φt+1. A new local set of segments ω φ t+1 corresponding to this position is constructed and merged with Ω T t 0 :

Ω T t+1 0 = Ω T t 0 ∪ ω φ t+1
Step 3 Segment selection. Three different cases may occur:

1. In the case where several unestimated segments are in the current list ω φ t+1 , a choice is performed in order to select the next chosen segment Si (see [START_REF] Marchand | Controlled camera motions for scene reconstruction and exploration[END_REF] for more details). An active estimation (step 1) based on this segment is then performed. We iterate the steps estimation, 2D lists creation and selection until one of the segments present in the current list ω φ t+1 has not been estimated. 2. If all the segments of ω φ t+1 have been considered and if at least one of the 2D segments previously observed have not been estimated (i.e., ω φ t+1 empty and Ω T t+1 0 not empty), we look in Ω T t+1 0 for the couple (Si, φ k ), for which the distance between the current camera location φt+1 and the location φ k (from which the segment Si has been observed) is minimal. Then, the camera moves to the position φ k (thus, φt+1 := φ k ). An active estimation (step 1) is then performed. 3. Finally, if Ω T t+1 0 is empty (i.e., all the 2D segments observed from any previous camera positions have been treated), a new viewpoint must be found. A global exploration, which is described in the next section, is thus necessary.

Experimental results

The example reported here (see Figure 1.a) deals with a scene composed of a cylinder (whose radius is 40 mm) and five polygons which lie in different planes. In Figure 2.a is displayed the initial image acquired by the camera. Figure 2 shows the images acquired before each optimal estimation and the corresponding list of segments. On Figure 2.a, the segment at the middle of the image is chosen and an estimation of the cylinder parameters is performed, first using one limb and then using both limbs (see [START_REF] Marchand | Controlled camera motions for scene reconstruction and exploration[END_REF] for details). After this reconstruction, all the segments observed from the current camera viewpoint belong to estimated primitives (see Figure 2.b). Thus, we look in Ω T t+1 0 for an untreated segment. Here, the camera moves to the previous position (Figure 2.a) and the camera gazes on the segment on the right of the image. The process is iterated Since this exploration strategy is local, it avoids computing explicitly new viewpoints. Furthermore, the composition of simple primitives, such as polygons, can be treated by this algorithm. However, more complex combinations raise new problems: an object can be occluded by another one (or by itself). Finally, as shown on the previous results, several objects may not have been observed from the different viewpoints. Exploration probes are thus necessary to make sure that the whole scene has been reconstructed.

Global exploration

Exploration Strategy

We consider a scene composed of a set O of initially unknown primitives. At the end of the local exploration, a subset O(T t 0 ) ⊆ O has been observed and reconstructed. Thus, we have to determine viewpoints able to bring more information about the scene. By information, we mean either a new primitive, either the certainty that a given area is object-free. Such viewpoints will be computed using the previously estimated 3D map and the part of the 3D scene which has not been already observed. If a new primitive is observed from the computed viewpoint, the local exploration process is used to estimate its parameters.

Knowing the set T t 0 of viewpoints since the beginning of the reconstruction process, it is possible to maintain a map of the observed and unexplored areas. The knowledge is thus composed by:

• the primitive already estimated: O(T t 0 ); • the known free space, denoted V(T t 0 ). Knowing the position of the primitives, and the position φ of the camera, it is possible to compute the area V(φ) observed from this position (using a ray tracing scheme). Thus, knowing the trajectory T t 0 , we can determined V(T t 0 ) the area observed from the beginning of the reconstruction process. We have V(T t 0 ) = t i=0 V(φi). This area can also be determined incrementally if we consider only the additional information given by the last viewpoint. Thus we have:

V(T t 0 ) = V(T t-1 0 ) ∪ V(φt) V(T 0 0 ) = V(φ0) (2)
• the unknown area U(T t 0 ): knowing the location of the reconstructed objects and the known free space, U(T t 0 ) is computed as:

U(T t 0 ) = V(T t 0 ) ∪ O(T t 0 ) (3)
We want to ensure the completeness of the reconstruction. In theory, the reconstruction must end when all the space has been observed, i.e., if at instant t:

U(T t 0 ) = ∅ (4)
However, this condition is usually unreachable. Ensuring the completeness of the reconstruction is not always possible. Some areas may be observed only from a set of viewpoints unreachable by the camera. Furthermore, due to the objects topology, some areas may be unobserved whatever the position of the camera. Thus we use the following termination condition:

∀φt+1, V(T t 0 ) ∪ V(φt+1) = V(T t 0 ) O(T t 0 ) ∪ O(φt+1) = O(T t 0 ) (5)
This means that the exploration process is as complete as possible if for all reachable viewpoints, the camera looks at a known part of the scene. We thus can be sure that, at the end of the exploration process, all the areas of the scene are either free-space, either an object which has been reconstructed, either an unobservable area.

Viewpoint Selection.

A simple strategy able to compute the "next best view" φt+1 is to consider the viewpoint which maximizes the volume of the new observed areas [START_REF] Connoly | The determination of next best views[END_REF] [START_REF] Wixson | Viewpoint selection for visual search[END_REF]. However the final trajectory may be ineffective dealing with the final distance covered by the camera. Furthermore, such a strategy do not take into account some problems such as the manipulator kinematics constraints or geometric constraints. We have thus to introduce some constraints in the strategy in order to reflect these different aspects of the exploration problem. We have chosen to formulate the probing strategy as a function minimization problem. Like in [START_REF] Tarabanis | The MVP sensor planning system for robotic vision tasks[END_REF][15] [START_REF] Pito | A sensor based solution to the next best view problem[END_REF], we define a function to be minimized which integrates the constraints imposed by the robotic system and evaluates the quality of the viewpoint. Thus, we use a set of independent measures which determine the quality or the badness of a viewpoint. Each result of a given measure belongs to [0, 1] (or has an infinitive value for unreachable positions). A value near 0 results from an ideal situation. The function F to be optimized is taken as a weighted sum of this set of measures.

Quality of a new position

The quality of a new position φt+1 is defined by the volume of the unknown area which appears in the field of view of the camera. The new observed area is given by G(φt+1) where:

G(φt+1) = V(φt+1) -V(φt+1) ∩ V(T t 0 ) (6)
where V(φt+1) defines the part of the scene observed from the position φt+1 and V(φt+1)∩V(T t 0 ) defines the sub-part of V(φt+1) which has been already observed (see Figure 3). If the position φt+1 does not give any wage of information (i.e. G ′ (φt) = ∅), we must reject this position. Thus, the value of the measure g is fixed to infinity in that case. The measure of the quality of the position φt+1 is then given by:

g(φt+1) = ∞ if G(φt+1) = ∅ 1 - volume(G(φ t+1 )) volume(V(φ t+1 )) else (7) V( t) G( t+1) V( t+1)
area previously observed area observed from the new viewpoint from the new position gain : area discovered Displacement Cost. A term reflecting the cost of the camera displacement between two viewpoints φt and φt+1 is introduced in the cost function F, in order to reduce the total camera displacement. It is defined using the following relation:

C(φt, φt+1) = 1 N dof N ddl i=1 βi | qi t -qi t+1 | | Qi M ax -Qi M in | (8)
where:

-N dof is the number of robot degrees of freedom ; qi is the position of the robot joint i and | Qi M ax -Qi M in | gives the distance between the joint limits on axis i ; βi are weights setting the relative importance of an axis with respect to the others (βi ∈ [0, 1]). For instance, rotational motions may be preferred to translational ones.

Additional Constraints. Additional constraints are associated to camera locations. The goal of these constraints is:

-to avoid unreachable viewpoints. This is a binary test which returns an infinite value when the position is unreachable:

A(φ) = 0 if φ is reachable ∞ else ( 9
)
A position is unreachable if it is not in the operational space of the manipulator, or if this position is located in an unknown area (leading to a collision risk). -to avoid positions near the robot joint limits. When a new primitive is observed from the computed viewpoint φt+1, an optimal estimation of its parameters must be performed. This estimation requires camera motions performed by visual servoing which can not be realized if the robot encounters a joint limit. The measure associated to this constraint is optimal (equal to 0) if the camera is located at the middle of the extension of each axis of the robot:

B(φ) = 1 N ddl N dof i=1 4(qi - Q i M ax +Q i M in 2 ) 2 (Qi M ax -Qi M in ) 2 (10)
Note that unlike in mobile robotics we do not have odometry problems and due to the quality of the reconstruction, it is not necessary to perform other estimations of the primitives and develop merging processes which would have implied the introduction of other constraints (such as overlap constraint) in our objective function. However, this algorithm can also be used with reconstruction scheme such as stereovision or laser range finder. Constraints introduced in the optimization function can be changed function of the sensor or robot caracteristics (e.g., scannings, tolerance or overlap constraints in the case of a laser range finder [START_REF] Pito | A sensor based solution to the next best view problem[END_REF] or of a mobile robot).

The function F(φt+1) to be minimized is thus defined as a weighted sum of the different measures:

F(φt+1) = A(φ) + α1g(φt+1) + α2C(φt, φt+1) + α3B(φ) (11
) Here, the weights are predetermined in order to reflect the relative importance of the different measures. For example, the wage of information given by a new position is more important than the cost of the camera displacement. We have defined a priority order of the coefficients αi such that α1 > α2 > α3. More precisely we have fixed α1 = 0.6, α2 = 0.3 and α3 = 0.1.

We have decided to constrain the camera viewpoints inside an hemisphere located around the scene (assumed to be inside the hemisphere), but only in the region already observed and object-free (in order to avoid collision). At the beginning of the exploration process, as the observed area is null, the camera motion is limited to the surface of the sphere. To minimize F(φ), we have used a fast deterministic relaxation scheme corresponding to a modified version of the ICM algorithm. Unlike stochastic relaxation methods such as simulated annealing, we cannot ensure that the global minimum of the function is reached. However, our method is not time-consuming and experimental results show that we always get a correct minimum in a low number of iterations.

Focusing on the regions of interest

At the end of the reconstruction process, some residual areas remain unexplored. This is mainly due to the termination criterion we have proposed (see equation ( 5)). First of all, it is not possible to ensure that 100% of the scene can be observed: the topology of the objects, the kinematic constraints of the manipulator prevent from observing the whole space. Thus, small parts of the scene usually remain unobserved. Second, the marginal gain of information decreases rapidly while the number of viewpoints increases. Thus, even if the whole scene is observable, the observation of the last residual areas requires a large number of viewpoints. For these different reasons, we decide to stop the exploration when a subset of the observable space has been really observed (typically, we define a threshold located between 95% and 97% of the observable space). However, it is necessary to verify that the remaining unobserved areas do not contain any objects (and if any to perform a reconstruction).

In a first time, we compute a segmentation of the residual areas considering the polyhedron incorporating a set of connex unobserved areas (defined here by small voxels). As the goal is to define small regions, if the volume of the computed polyhedrons is to important, they are subdivided. In a second time, considering sequentially each sub-scene, a focused global exploration algorithm is then performed. Like in the case of the global exploration algorithm we consider that the camera motion is limited inside an hemisphere located around this polyhedron. The knowledge previously acquired is used in order to consider a collision avoidance process. This strategy allows to decrease significantly the number of viewpoints while increasing the part of observed areas (leading to 99%).

Reducing the number of viewpoints

The technique proposed in the previous paragraphs to solve the "next best view" problem is a depth-first search algorithm. We do no try to consider the whole trajectory in order to reduce either the number of viewpoints, either the distance performed by the camera. The following algorithm aims at reducing the number of viewpoints needed to explore the scene. The problem can be stated as follow: at instant t the camera has already performed the trajectory T t 0 ; knowing the set of reconstructed objects O(T t 0 ) and the observed area V(T t 0 ), find the trajectory T

t f in t+1
which ensures a complete reconstruction of the scene in a minimal number of viewpoints.

Even knowing a complete model of the scene, the problem is, in the general case, NP-complete [START_REF] Tarbox | Planning for complete sensor coverage in inspection[END_REF]. Furthermore, to determine such a trajectory, we need to know the shape and the location of the objects. In our case, we do not have this information. Thus this scheme is efficient if all the objects present in the scene have been already reconstructed at time t. Then, the trajectory T t f in t+1 can be computed. However if a new primitive is observed from viewpoint φ t ′ , t ′ ∈ [t + 1, t f in [, it must be reconstructed and a new trajectory T t f in t ′ must be determined. It is possible, using the method proposed in Section 3.2 to obtain a set of viewpoints T n 0 0 such that the whole scene is observed from the n0 = t f in viewpoints. As previously stated, at the end of the exploration process, the marginal gain of each viewpoint is weak. A local adjustment of the position of a viewpoint along the computed trajectory may be preferable to the addition of a new viewpoint. Furthermore, it is possible that the information given by a viewpoint at time t is also given by other viewpoints at time t ′ > t. This viewpoint φt is thus useless and can be deleted. If n0 is the initial number of viewpoints, the iterative algorithm allowing to define a trajectory which ensures a reconstruction as complete as possible of the scene in n viewpoints (n ≤ n0) can be decomposed in two steps: In a first time, we want to know if some local adjustments of the trajectory could increase the quantity of available information. Thus we consider each viewpoint φi ∈ T t f in t+1 and look for a viewpoint φ i ′ such that:

volume(U(T t f in 0 )) ≤ volume(U(T ′ t f in 0 ))
where T ′ t f in 0 = {φ0, . . . , φi-1, φ ′ i , φi+1, . . . , φt f in } and where U represents the unknown area (see equation ( 3)). To compute φ i ′ , we use the proposed computing viewpoints algorithm considering in (6) G(φ i ′ ) as:

G(φ i ′ ) = V(φ i ′ ) -V(φ i ′ ) ∩ V(T t f in 0 -φi).
If such a viewpoint exists, φi is replaced with φ i ′ in the trajectory. This process is done for each viewpoint of the trajectory T t f in t+1 and iterated while the location of a viewpoint is modified. Figure 4 describes the result of this local adjustment algorithm.

In a second time, if the whole scene is observed, the viewpoint φmin, bringing the lowest quantity of information is suppressed from the trajectory. The local adjustment process is then used again in order to compensate for this deletion. This algorithm is iterated while the observed areas remains greater than a predefined threshold (99% in our case).

Experimental results

First, we consider the case of a simple scene composed by a cylinder and a polygon in order to illustrate the influence of the different proposed strategies. All the objects have been reconstructed during a first local exploration/reconstruction process (see Figure 5). The observed/unobserved/occluded areas are computed using a ray tracing algorithm. In this first experiment, we want to analyze the influence of the weights αi involved in [START_REF] Maver | Occlusions as a guide for planning the next view[END_REF]. In the first strategy (Figure 6.a), the distance between two viewpoints is not taken into account, thus this strategy is mainly based on the maximization of the new observed area (the weight α2 in ( 11) is null). The second strategy (Figure 6.b) uses the distance between two successive viewpoints in order to reduce the total distance covered by the camera We note that if the distance between two viewpoints is not taken into account, the camera motion behaves like a "bee flight". Such motion does not occur if the distance cost is introduced into the energy function. The camera motion is more continuous and shorter (1.13 m versus 3.37 m with α2 = 0). This underlines the interest in introducing the distance parameter into the energy function. Focusing on the regions of interest Using the same scene, we decide to stop the exploration when 95% of the scene has been observed. Then, we compute a segmentation of the residual areas (see Figure 7.a and 7.b). Four regions of interest are created. The camera focuses on each of these regions in order to ensure that no other objects can be observed in the scene. The remaining area unobserved (Figure 7.c) is less that 1% and mostly corresponds to occluded regions which cannot be observed due to robot kinematic constraints. Figure 8 depicts the results obtained for the reconstruction of another scene, a polyhedron, using this algorithm. Cylinder and polygons scene In this experiment, we consider the scene proposed in Section 2. Figure 11 presents the different steps of the global exploration of the scene. Each figure shows the obtained 3D scene, the camera trajectory and the projection on a virtual plane of the unknown areas. After a last exploration process, the last polygon is reconstructed and the camera is located in φ30 (Figure 11.d). At this step, 99% of the space has been observed, which ensures that the reconstruction of the scene is complete. Figure 12 shows the final 3D model of the scene (to be compared to Figure 1) and the camera trajectory.

Reducing the number of viewpoints

Conclusion

In this paper, we have proposed a method for 3D environment perception using a sequence of images acquired by a mobile camera. Since the method used for reconstruction is based on peculiar camera motions, perceptual strategies able to appropriately perform a succession of individual primitive reconstruction have been proposed. An important feature of our approach is its ability to easily determine the next primitive to be estimated without any knowledge or assumption on the number, the localization and the spatial relation between objects. Our approach is entirely bottom-up and does not use any a priori on the environment except the nature of the considered primitives and a bounding volume located around the scene. Experiments carried out on a robotic cell have proved the validity of our approach (accurate, stable and robust results, efficient exploration algorithms), but have also shown its limitations: the constraints on the camera motion, which are necessary to obtain precise results, imply the sequencing of visual estimations.

Figure 1 :

 1 Figure 1: External view of the scene and results of the first local exploration process.

Figure 2 :

 2 Figure 2: Different steps of the local exploration process:image and list of segments from position φ0,φ1, φ2 and φ6 (dashed lines correspond to segments which are the projection of estimated primitives).

Figure 3 :

 3 Figure 3: Quality of a new position (2D projection).

Figure 4 :

 4 Figure 4: Projection on a virtual plane of the view cone associated to each camera viewpoints φ ∈ T n t+1 . (a) The volume of observed area has been deliberately limited to 75%. (b) After a set of local adjustments (the number of viewpoint remains constant), more than 95% of the scene is observed.

Figure 5 :

 5 Figure 5: Results of the first local exploration process: (a) Reconstructed scene and projection on a virtual plane of the unknown area (b) Reconstructed scene and volumetric representation of the occluded area.

Figure 6 :

 6 Figure 6: Global exploration of the scene. Camera motion with (a) α2 = 0 (b) α2 = 0.3.

Figure 9 :

 9 Figure 9: Projection on a virtual plane of the view cone associated to each camera viewpoints φ ∈ T n 0 (a) Initial trajectory (n = 29) (b) final computing trajectory (n = 15).

Figure 10 :

 10 Figure 10: Percentage of observed areas versus the number of viewpoints.

Figure 11 .

 11 a corresponds to the camera position φ6 obtained just after the local exploration process described in Section 2. The first camera displacements allows to reduce significantly the unknown areas. At position φ13 (see Figure11.b), a new primitive is detected. A new local exploration process is performed. It ends at position φ24 (Figure11.c). At this step, the two polygons on the "top" of the scene have been reconstructed. A new global exploration is then performed.

Figure 12 :

 12 Figure 12: 3D model of the reconstructed scene and polar view of the camera trajectory

Figure 7 :Figure 8 :Figure 11 :

 7811 Figure 7: Focusing on the regions of interest : (a) observed/unobserved areas and camera trajectory before focusing, (b) detected regions of interest, (c) observed/unobserved areas and camera trajectory after focusing.

  Using the algorithm proposed in Section 3.4, we can reduce the number of viewpoints from 29 (see Figure9.a) to 15 (see Figure9.b) without any waste of information. Figure10shows the percentage of observed area (after local adjustement) versus the number of viewpoint. Above 20 viewpoints, the percentage of observed area is greater than 99%, and below 15 viewpoints the percentage of observed area is smaller than the initial one. However, reducing to 15 the number of viewpoints requires approximatively 15 minutes on a SUN SS20 while only 10 seconds are necessary to compute a new viewpoint. Thus, we think that this optimization algorithm is interesting only if time is not critical. It is also more adapted to the inspection of a known scene than to the exploration of an unknown environment.

Éric Marchand is currently at Yale University, Dpt of Computer Science, PO Box

208-285, New Haven, CT 06520-8285, E-mail: marchand@cs.yale.edu