Vineet Gandhi
email: vineet.gandhi@inria.fr

Jan Čech
email: jan.cech@inria.fr

Radu Horaud
email: radu.horaud@inria.fr

High-Resolution Depth Maps Based on TOF-Stereo Fusion

The combination of range sensors with color cameras can be very useful for robot navigation, semantic perception, manipulation, and telepresence. Several methods of combining range-and color-data have been investigated and successfully used in various robotic applications. Most of these systems suffer from the problems of noise in the range-data and resolution mismatch between the range sensor and the color cameras, since the resolution of current range sensors is much less than the resolution of color cameras. High-resolution depth maps can be obtained using stereo matching, but this often fails to construct accurate depth maps of weakly/repetitively textured scenes, or if the scene exhibits complex self-occlusions. Range sensors provide coarse depth information regardless of presence/absence of texture. The use of a calibrated system, composed of a time-of-flight (TOF) camera and of a stereoscopic camera pair, allows data fusion thus overcoming the weaknesses of both individual sensors. We propose a novel TOF-stereo fusion method based on an efficient seed-growing algorithm which uses the TOF data projected onto the stereo image pair as an initial set of correspondences. These initial "seeds" are then propagated based on a Bayesian model which combines an image similarity score with rough depth priors computed from the low-resolution range data. The overall result is a dense and accurate depth map at the resolution of the color cameras at hand. We show that the proposed algorithm outperforms 2D image-based stereo algorithms and that the results are of higher resolution than off-the-shelf color-range sensors, e.g., Kinect. Moreover, the algorithm potentially exhibits real-time performance on a single CPU.

I. INTRODUCTION

An advanced computer vision system should be able to provide both accurate color and depth information for each pixel at high resolution. Such a system can be very useful for automated vision problems especially in the context of robotics, e.g., for building dense 3D maps of indoor environments.

The 3D structure of a scene can be reconstructed from two or more 2D views via a parallax between corresponding image points. However, it is difficult to obtain accurate pixel-topixel matches for scenes of objects without textured surfaces, with repetitive pattern, or in the presence of occlusions. The main drawback is that stereo matching algorithms frequently fail to reconstruct indoor scenes composed of untextured surfaces, e.g., walls, repetitive patterns and surface discontinuities, which are typical in man-made environments.

Alternatively, active-light range sensors, such as timeof-flight (TOF) or structured-light cameras, can be used to directly measure the 3D structure of a scene at video † V. Gandhi acknowledges support from the Erasmus Mundus CIMET master program. The technology used by both these camera types allows simultaneous range and photometric data acquisition with an extremely accurate temporal synchronization, which may not be the case with other types of range cameras such as the current version of Kinect. ' frame-rates. However, the spatial resolution of currently available range sensors is lower than high-definition (HD) color cameras, the luminance sensitivity is poorer and the depth range is limited. The range-sensor data are often noisy and incomplete over extremely scattering parts of the scene, e.g., non-Lambertian surfaces. Therefore it is not judicious to rely solely on range-sensor estimates for obtaining 3D maps of complete scenes. Nevertheless, range cameras provide good initial estimates independently of whether the scene is textured or not, which is not the case with stereo matching algorithms. These considerations show that it is useful to combine the active-range and the passiveparallax approaches, in a mixed system. Such a system can overcome the limitations of both the active-and passiverange (stereo) approaches, when considered separately, and provides accurate and fast 3D reconstruction of a scene at high resolution, e.g. 1200 × 1600 pixels at 30 frames/second, as in Fig. 1.

A. Related Work

The combination of a depth sensor with a color camera has been exploited in several robotic applications such as object recognition [START_REF] Gould | Integrating visual and range data for robotic object detection[END_REF], [START_REF] Stückler | Combining depth and color cues for scaleand viewpoint-invariant object segmentation and recognition using random forests[END_REF], [START_REF] Attamimi | Real-time 3D visual sensor for robust object recognition[END_REF], person awareness, gesture recognition [START_REF] Droeschel | Towards joint attention for a domestic service robot -person awareness and gesture recognition using time-of-flight cameras[END_REF], simultaneous localization and mapping (SLAM) [START_REF] Castaneda | SLAM combining tof and high-resolution cameras[END_REF], [START_REF] Jebari | Multi-sensor semantic mapping and exploration of indoor environments[END_REF], robotized plant-growth measurement [START_REF] Alenyà | 3d modelling of leaves from color and tof data for robotized plant measuring[END_REF], etc. These methods have to deal with the difficulty of noise in depth measurement and the inferior resolution of range data as compared to the color data. Also, most of these systems are limited to RGB-D, i.e., a single color image combined with the range data. Interestingly enough, the recently commercialized Kinect1 camera falls in the RGB-D family of sensors. We believe that extending this model to an RGB-D-RGB sensor is extremely advantageous because it can incorporate stereoscopic matching and hence better deal with the problems mentioned above.

Stereo matching has been one of the most studied paradigms in computer vision. Several papers, e.g., [START_REF] Scharstein | A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[END_REF], [START_REF] Seitz | A comparison and evaluation of multi-view stereo reconstruction algorithms[END_REF] present an overview of existing techniques and highlight recent progress in stereo matching and stereo reconstruction. Algorithms based on a greedy local search are typically fast but frequently fail to reconstruct the poorly textured regions or ambiguous surfaces. Global methods formulate the matching task as a single optimization problem which leads to minimization of an Markov random field (MRF) energy function of the image similarity likelihood and a prior on the surface smoothness. These algorithms solve some of the aforementioned problems of local methods but are very complex and computationally expensive since optimizing an MRF-based energy function is an NP-hard problem in the general case.

A practical tradeoff between the local and the global methods in stereo is the seed growing class of algorithms [START_REF] Čech | Efficient sampling of disparity space for fast and accurate matching[END_REF], [START_REF] Cech | Efficient sequential correspondence selection by cosegmentation[END_REF], [START_REF] Cech | Scene flow estimation by growing correspondence seeds[END_REF]. The correspondences are grown from a small set of initial correspondence seeds. Interestingly, they are not particularly sensitive to wrong input seeds. They are significantly faster than the global approaches, but they have difficulties in presence of non textured surfaces; Moreover, in these cases they yield depth maps which are relatively sparse. Denser maps can be obtained by relaxing the matching threshold but this leads to erroneous growth, which is a natural tradeoff between the accuracy and density of the solution. Some form of regularization is necessary in order to take full advantage of these methods.

Recently an external prior-based generative probabilistic model for stereo matching was proposed in [START_REF] Geiger | Efficient large-scale stereo matching[END_REF], [START_REF] Newcombe | Live dense reconstruction with a single moving camera[END_REF] for reducing the matching ambiguities. The prior used was based on surface-triangulation on initially-matched distinctive interest points in the images. Again, in the absence of textured regions, such support points are either not available or are not reliable enough and the priors are erroneous. Consequently, the methods produce artifacts in cases the priors win over the data and the solution is biased towards the incorrect priors. This clearly shows the need for more accurate prior models. [START_REF] Wang | Global stereo matching leveraged by sparse ground control points[END_REF] integrates a regularization term based on the depth values of initially matched ground control points in a global energy minimization framework. The ground control points are gathered using an accurate laser scanner. A laser scanner is difficult to operate and cannot provide range information fast enough such that it can be used in a practical robotic application.

A TOF camera is based on an active sensor principle2 that allows 3D data acquisition at video frame rates, e.g., 30FPS as well as accurate synchronization with any number of color cameras 3 . A modulated near infrared light from the camera's internal lighting source is reflected by objects in the scene and travels back to the sensor, where its precise time of flight is measured independently at each of the sensor's pixel by calculating the phase delay between the emitted and the detected wave. A complete depth map of the scene can be obtained using this sensor at the cost of very low spatial resolution and coarse depth accuracy.

The fusion of TOF data with stereo data has been recently studied. For example, [START_REF] Mutto | A probabilistic approach to tof and stereo data fusion[END_REF] obtained a higher quality depth map, by a probabilistic ad-hoc fusion of TOF and stereo data. Work in [START_REF] Zhu | Fusion of time-of-flight depth and stereo for high accuracy depth maps[END_REF] merges the depth probability distribution function obtained from TOF and stereo. However both these methods are meant for improvement over the initial data gathered with the TOF camera and the final depth-map result is still limited to the resolution of the TOF sensor. The method proposed in this paper increases the resolution from 0.03MP to the full resolution of the color cameras being used, e.g., 2MP.

The problem of depth map upsampling has been previously addressed. In [START_REF] Chan | A noise-aware filter for real-time depth upsampling[END_REF] a noise-aware filter for adaptive multi-lateral upsampling of TOF depth maps is presented. The work described in [START_REF] Gould | Integrating visual and range data for robotic object detection[END_REF] extends the model of [START_REF] Diebel | An application of Markov random fields to range sensing[END_REF] and demonstrates that the object detection accuracy can be significantly improved by combining a state-of-art 2D object detector with 3D depth cues. The approach deals with the problem of resolution mismatch between range-and color-data using an MRF-based super-resolution technique in order to infer the depth at every pixel. The proposed method is slow: It takes around 10 seconds to produce a 320 × 240 depth image. All of these methods are limited to depth-map upsampling using only a single color image and do not exploit the added advantage offered by stereo matching, which can highly enhance the depth map both qualitatively and quantitatively. Recently, [START_REF] Fischer | Combination of time-of-flight depth and stereo using semiglobal optimization[END_REF] proposed a method which combines TOF estimates with stereo in a semiglobal matching framework. However, at pixels where TOF disparity estimates are available, the image similarity term is ignored. This make the method quite susceptible to errors in regions where TOF estimates are not precise, especially in textured regions where stereo itself is reliable.

B. Contributions

In this paper we propose a novel Bayesian method for incorporating range data within a robust seed-growing algorithm for stereoscopic matching [START_REF] Čech | Efficient sampling of disparity space for fast and accurate matching[END_REF]. A calibrated system composed of an active range sensor and a stereoscopic colorcamera pair [START_REF] Hansard | Projective alignment of range and parallax data[END_REF], e.g., Fig. 1, allows the range data to be projected onto each one of the two images, thus providing an initial sparse set of point-to-point correspondences (seeds) between the two images. This initial seed set is used in conjunction with the seed-growing algorithm proposed in [START_REF] Čech | Efficient sampling of disparity space for fast and accurate matching[END_REF]. The novelty is that the range data are used as the vertices of a mesh-based surface representation which, in turn, is used as a prior to regularize the image-based matching procedure. The Bayesian fusion, between the mesh-based surface (initialized from the sparse range data) and the seed-growing stereo matching algorithm itself, combines the merits of the two 3D sensing methods and overcomes the limitations outlined above. The proposed fusion model can be incorporated within virtually any stereo algorithm that is based on energy minimization and which requires proper initialization. It is, however, particularly efficient and accurate when used in combination with match-propagation methods.

The remainder of this paper is structured as follows: Section II describes the proposed range-stereo fusion algorithm. Experimental results on a real dataset and evaluation of the method, are presented in section III. Finally, section IV draws some conclusions.

II. THE PROPOSED ALGORITHM

As outlined above, the TOF camera provides a lowresolution depth map of a scene. This map can be projected onto the left and right images associated with the stereoscopic pair, using the projection matrices estimated by the calibration method described in [START_REF] Hansard | Projective alignment of range and parallax data[END_REF]. Projecting a single 3D point (x, y, z) gathered by the TOF camera onto the rectified images provides us with a pair of corresponding points (u, v) and (u ′ , v) in the respective images. Each element (u, u ′ , v) denotes a point in the disparity space 4 . Hence, projecting all the points obtained with the TOF camera gives us a sparse set of 2D point correspondences. This set is termed as the set of initial support points or TOF seeds.

These initial support points are used in a variant of the seed-growing stereo algorithm [START_REF] Čech | Efficient sampling of disparity space for fast and accurate matching[END_REF], [START_REF] Cech | Scene flow estimation by growing correspondence seeds[END_REF] which further grows them into a denser and higher resolution disparity map. The seed-growing stereo algorithms propagate the correspondences by searching in the small neighborhood of given seed correspondences. Hereby, only a small fraction of disparity space is visited, which makes the algorithm extremely efficient from a computational point of view. The limited neighborhood also gives a kind of implicit regularization, nevertheless the solution can be arbitrarily complex, since multiple seeds are provided.

The integration of range data within the seed-growing algorithm required two major modifications: (1) The algorithm is using TOF seeds instead of the seeds obtained by matching distinctive image features, such as interest points, between the two images, and (2) the growing procedure is regularized using a similarity statistic which takes into account the photometric consistency as well as the depth 4 The disparity space is a space of all potential correspondences [START_REF] Scharstein | A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[END_REF]. Draw seed s ∈ S of the best simil(s|IL, IR, Dp) value.

6:

for each of the four best neighbors i ∈ {1, 2, 3, 4}

q * i = (u, u ′ , v) = argmax q∈N i (s) simil(q|IL, IR, Dp) do 7: c := simil(q * i |IL, IR, Dp) 8:
if c ≥ τ and pixels not matched yet then 9:

Update the seed queue S := S ∪ {q * i }.

10:

Update the output map D(u, v) = uu ′ .

11:

end if 12:
end for 13: until S is empty 14: return disparity map D. likelihood based on disparity estimate by interpolating the rough triangulated TOF surface. This can be viewed as a prior cast over the disparity space.

The growing algorithm is summarized in Sec. II-A. The processing of the TOF correspondence seeds is explained in Sec. II-B, and the sensor fusion based similarity statistic is described in Sec. II-C.

A. The Growing Procedure

The growing algorithm is sketched in pseudo-code as Alg. 1. The input is a pair of rectified images (IL, IR), a set of (refined) TOF seeds S, and a parameter τ which directly controls a trade-off between accuracy and density of the matching. The output is a disparity map D which relates pixel correspondences between the input images.

First, the algorithm computes the prior disparity map Dp by interpolating TOF seeds. Map Dp is of the same size as the input images and the output disparity map, Step 1. Then, a similarity statistic simil(s|IL, IR, Dp) of the correspondence, which measures both the photometric consistency of the possible correspondence and consistency with the prior, is computed for all seeds s = (u, u ′ , v) ∈ S, Step 2. Recall that the seed s stands for a correspondence (u, v) ↔ (u ′ , v) between pixels in the left and the right images. For each seed, the algorithm searches other correspondences in the surroundings of the seeds by maximizing the similarity statistic. This is done in a 4-neighborhood {N1, N2, N3.N4} of the pixel correspondence, such that in each respective direction (left, right, up, down) the algorithm searches the disparity in a range ±1 pixel from the disparity of the seed, Step 6. If the similarity statistic of a candidate exceeds threshold τ , then a new correspondence is found, Step 8. It becomes a new seed, and output disparity map D is updated. The process repeats until there are no more seeds to be grown.

The algorithm is fairly insensitive to wrong initial seeds. Since the seeds compete to be matched in the best first strategy, the wrong seeds typically have low score simil(s) and therefore when they are drawn in Step 5, the involved pixels are likely to have been matched already. For more details on the growing algorithm, we refer to [START_REF] Cech | Scene flow estimation by growing correspondence seeds[END_REF], [START_REF] Čech | Efficient sampling of disparity space for fast and accurate matching[END_REF].

B. TOF Seeds and Their Refinement

The original version of the seed-growing stereo algorithm [START_REF] Cech | Scene flow estimation by growing correspondence seeds[END_REF] uses an initial set of seeds S obtained by detecting interest points in both images and matching them. Here, we propose to use TOF seeds. As already outlined, these seeds are obtained by projecting the low-resolution depth map associated with the TOF camera onto the high-resolution images. Likewise in the case of interest points, yields a sparse set of seeds, e.g., approximately 25,000 seeds in the case of the TOF camera used in our experiments. Nevertheless, one of the main advantages of the TOF seeds over the interest points is that they are regularly distributed across the images regardless of the presence/absence of texture. This is not the case with interest points whose distribution strongly depends on texture as well as lighting conditions, etc. Obviously, regularly distributed seeds will provide a better coverage of the observed scene.

However, TOF seeds are not always accurate. Indeed, when a 3D point is projected onto the left-and the rightimage, it does not always yield a valid stereo match. There may be several sources of error which make the TOF seeds less reliable than one would have expected, e.g., Fig. 2 and Fig. 3. In detail:

1) Imprecision due to the calibration data. The transformations allowing to project the 3D TOF points onto the 2D images are obtained via a complex sensor calibration process [START_REF] Hansard | Projective alignment of range and parallax data[END_REF]. This introduces a localization error up to 2-3 pixels. 2) Outliers due to the physical/geometric properties of the scene. Range sensors are based on active light and on the assumption that the active beam of light travels from the sensor and back to it. There are a number of situations where the beam is lost, such as specular surfaces, absorbing surfaces (such as fabric), scattering surfaces (such as hair), slanted surfaces, bright surfaces (computer monitors), faraway surfaces (limited range), or when the beam travels in an unpredictable way, such a multiple reflections.

3) The TOF-and 2D cameras observe the scene from slightly different points of view. Therefore, it may occur that a 3D point that is present in the TOF image is only seen into the left or right image, e.g., Fig. 3.

Therefore, a fair percentage of the TOF seeds are outliers. Although the seed-growing stereo matching algorithm is robust to the presence of outliers in the initial set of seeds, as already explained in section II-A, we implemented a straightforward refinement step in order to detect and eliminate these kind of bad seed data, prior to applying Alg. 1. Firstly, the seeds that lie in low-intensity (very dark) regions are discarded since TOF-based range data are not reliable in these cases. Secondly, in order to handle the background-to-foreground occlusion effect just outlined, we detect seeds which are not uniformly distributed across image regions. Indeed, projected 3D points lying on smooth frontoparallel surfaces form a regular image pattern of seeds, while projected 3D points that belong to a background surface and which project onto a foreground image region do not form a regular pattern. See occlusion boundary in Fig. 4(a).

Such seeds are detected by counting the occupancy of small 5 × 5 pixel windows around every seed point in both images. If there is more than one seed point, the seeds belonging to the background are discarded. Refined set of seeds is shown in Fig. 4(b). The refinement procedure typically filters 10-15% of all seed points.

C. Similarity Statistic Based on Sensor Fusion

The original seed-growing matching algorithm [START_REF] Cech | Scene flow estimation by growing correspondence seeds[END_REF]

as the similarity statistic to measure the photometric consistency of a correspondence s : (u, v) ↔ (u ′ , v). We denote by wL and wR the feature vectors which collect image intensities in small windows of size n × n pixels centered at (u, v) and (u ′ v) in the left and right image respectively. The parameter ǫ prevents instability of the statistic in cases of low intensity variance. This is set as the machine floating point epsilon. The statistic has low response in textureless regions and therefore the growing algorithm does not propagate the correspondences across these regions. Since the TOF sensor can provide seeds without the presence of any texture, we propose a novel similarity statistic, simil(s|IL, IR, Dp). This similarity measure uses a different score for photometric consistency as well as an initial high-resolution disparity map Dp, both incorporated into the Bayesian model explained in detail below. The initial disparity map Dp is computed as follows. A 3D meshed surface is built from a 2D triangulation applied to the TOF image. The disparity map Dp is obtained via interpolation from this surface such that it has the same (high) resolution as of the left and right images. Fig. 5(a) and 5(b) show the meshed surface projected onto the left high-resolution image and built from the TOF data, before and after the seed refinement step, which makes the Dp map more precise.

Let us now consider the task of finding an optimal highresolution disparity map. For each correspondence (u, v) ↔ (u ′ , v) and associated disparity d = u-u ′ we seek an optimal disparity d * such that: (2) By applying the Bayes' rule, neglecting constant terms, assuming that the distribution P (d) is uniform in a local neighborhood where it is sought (Step. 6), and considering conditional independence P (I l , Ir, D|d) = P (IL, IR|d)P (Dp|d), we obtain:

d * = argmax d P (IL, IR|d) P (Dp|d), (3)
where the first term is the image likelihood and the second term is the range-sensor likelihood. We define the image and range-sensor likelihoods as:

P (IL, IR|d) ∝ EXPSSD(wL, wR) = = exp - P n×n i=1 (wL(i) -wR(i)) 2 σ 2 s P n×n i=1 (wL(i) 2 + wR(i) 2 ) ! , (4)
and as

P (Dp|d) ∝ exp " - (d -dp) 2 2σ 2 p « (5)
respectively, where σs are σp two normalization parameters. Therefore, the new similarity statistic becomes simil(s|IL, IR, Dp) = EPC(wL, wR, Dp) = = exp -

P n×n i=1 (wL(i) -wR(i)) 2 σ 2 s P n×n i=1 (wL(i) 2 + wR(i) 2 ) - (d -dp) 2 2σ 2 p ! . (6)
Notice that the proposed image likelihood has a high response for correspondences associated with textureless regions. However, in such regions, all possible matches have similar image likelihoods. The proposed range-sensor likelihood regularizes the solution and forces it towards the one closest to the prior disparity map Dp. A tradeoff between these two terms can be obtained by tuning the parameters σs and σp.

III. EXPERIMENTS

Our experimental setup comprises one Mesa Imaging Swissranger TM SR4000 TOF camera and a pair of highresolution Point Grey5 color cameras, e.g., Fig. 1. The two color cameras are mounted on a rail with a baseline of about 49 cm and the TOF camera is approximately midway between them. All three optical axes are approximately parallel. The resolution of the TOF image is of 144×177 and the color cameras have a resolution of 1224 × 1624. Recall that Fig. 1(b) highlights the resolution differences between the TOF and color images.This camera system was calibrated using the method described in [START_REF] Hansard | Projective alignment of range and parallax data[END_REF].

In all our experiments, we set the parameters of the method as follows: Windows of 5 × 5 pixels were used for matching (n = 5), matching threshold in Alg. 1 to τ = 0.5, the balance between the photometric and range sensor likelihoods was set to σ 2 s = 0.1 and to σ 2 p = 0.001 in (6). We show both qualitatively and quantitatively (using datasets with ground-truth) benefits of the range sensor and an impact of particular variants of the proposed fusion model integrated in the growing algorithm. Namely, we compare results of (i) the original stereo algorithm [START_REF] Cech | Scene flow estimation by growing correspondence seeds[END_REF] with MNCC correlation and Harris seeds (MNCC-Harris), (ii) the same algorithm with TOF seeds (MNCC-TOF), (iii) the algorithm which uses EXPSSD similarity statistic instead with both Harris (EXPSSD-Harris) and TOF seeds (EXPSSD-TOF), and (iv) the full sensor fusion model of the regularized growth (EPC). Finally small gaps of unassigned disparity in the disparity maps were filled by a primitive procedure which assigns median disparity in the 5 × 5 window around the gap (EPC -gaps filled). These small gaps usually occur in slanted surfaces, since Alg. 1 in Step. 8 enforces one-toone pixel matching. Nevertheless this way, they can be filled easily if needed.

A. Real-Data Experiments

We captured two real-world datasets using the camera setup described above, SET-1 in Fig. 6 and SET-2 in 7. Notice that in both of these examples the scene surfaces are weakly textured.

1) Comparisons between disparity maps:

Results as disparity maps are shown color-coded, such that warmer colors are further away from the cameras and unmatched pixels are dark blue.

In Fig. 6(b), we can see that the original algorithm [START_REF] Cech | Scene flow estimation by growing correspondence seeds[END_REF] has difficulties in low textured regions which results in large unmatched regions due to MNCC statistic [START_REF] Alenyà | 3d modelling of leaves from color and tof data for robotized plant measuring[END_REF], and it produces several mismatches over repetitive structures on the background curtain, due to erroneous (mismatched) Harris seeds. In Fig. 6(c), we can see that after replacing the sparse erratic Harris seeds with uniformly distributed mostly correct TOF seeds, results improve significantly. There are no more mismatches on the background, but unmatched regions are still large. In Fig. 6(d), the EXPSSD statistic (4) was used instead of MNCC which causes similar mismatches as in Fig. 6(b), but unlike MNCC there are matches in textureless regions, nevertheless mostly erratic. The reason is that unlike MNCC statistic the EXPSSD statistic has high response in low textured regions. However, since all disparity candidates have equal (high) response inside such regions, the unregularized growth is random, and produces mismatches. The situation does not improve much using the TOF seeds, as shown in Fig. 6(e). Significantly better results are finally shown in Fig. 6(f) which is using the full proposed fusion model EPC [START_REF] Cech | Scene flow estimation by growing correspondence seeds[END_REF]. The EPC statistic compared to EXPSSD has the additional regularizing range sensor likelihood term which guides the growth in ambiguous regions and attracts the solution towards the rough estimate of the TOF camera.

Results are further refined by filling small gaps in Fig. 6(g). Similar observations can be made in Fig. 7. The proposed model clearly outperforms the other discussed approaches.

2) Comparisons between reconstructed surfaces: For the proper analysis of a stereo matching algorithm it is important to inspect the reconstructed 3D surfaces. Indeed the visualization of the disparity/depth maps can sometimes be misleading. Surface reconstruction reveals fine details in the quality of the results. This is in order to qualitatively show the gain of the high-resolution depth map produced by the proposed algorithm with respect to low-resolution depth map of the TOF sensor.

In order to provide a fair comparison, we show the reconstructed surfaces associated with the dense disparity maps Dp obtained after 2D triangulation of the TOF data points, Fig. 8(a), as well as the reconstructed surfaces associated with the disparity map obtained with the proposed method, Fig. 8(b). Clearly, much more of the surface details are recovered by the proposed method. Notice precise object boundaries and fine details, like a pillow on the sofa chair and a collar of the T-shirt, which appear in Fig. 8(b). This qualitatively corroborates the precision of the proposed method compared to the TOF data.

B. Ground-Truth Evaluation

To quantitatively demonstrate the validity of the proposed algorithm, we carried out an experiment on datasets with associated ground-truth results. Similarly to [START_REF] Mutto | A probabilistic approach to tof and stereo data fusion[END_REF] we use Middlebury dataset [START_REF] Scharstein | A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[END_REF] and simulated the TOF camera by sampling the ground-truth disparity map.

We used the Middlebury-2006 dataset 6 . On purpose, we selected three challenging scenes with weakly textured surfaces: Lampshade-1, Monopoly, Plastic. The input images are of size 1330 × 1110 pixels. We took every 10th pixel in a regular grid to simulate the TOF camera. This gives us about 14k of TOF points, which is roughly the same ratio to color images as for the real sensors. We are aware that simulation TOF sensor this way is naive, since we do not simulate any noise or artifacts, but we believe that for validating the proposed method this is satisfactory. 6 http://vision.middlebury.edu/stereo/data/scenes2006/ Results are shown in Fig. 9. We show left input image, results of the same algorithms as in the previous section with the real sensor, and the ground-truth disparity map. For each disparity, we compute the percentage of correctly matched pixels in non-occluded regions. This error statistic is computed as number of pixels for which the estimated disparity differs from the ground-truth disparity by less than one pixel divided by number of all pixels in non-occluded regions. Notice that unmatched pixels are considered as errors of the same kind as mismatches. This is in order to allow a strict but fair comparison between algorithms which deliver solution of different density. The quantitative evaluation confirms the observation from the real-world setup. The proposed algorithm which uses the full sensor fusion model significantly outperforms all other tested variants.

For the sake of completeness we also report error statistics for the prior disparity map Dp which is computed by interpolating TOF seeds, see Step 1 of Alg.1. This is 92.9%, 92.1%, 96.0% for Lampshade-1, Monopoly, Plastic scene respectively. These results are already quite good, which means the interpolation we use to construct the prior disparity map is appropriate. These scenes are mostly piecewise planar, which the interpolation captures well. On the other hand, recall that in the real case, not all the seeds are correct due to various artifacts of a range sensor. Nevertheless in all three scenes, the proposed algorithm (EPC with gaps filled) was able to further improve the precision up to 96.4%, 95.3%, 98.2% for respective scenes. This is again consistent with the experiments with the real TOF sensor, where higher surface details were recovered, see Fig. 8.

C. Computational Costs

The original growing algorithm [START_REF] Cech | Scene flow estimation by growing correspondence seeds[END_REF] has low computational complexity due to intrinsic search space reduction. Assuming the input stereo images of size n × n pixels, the algorithm has the complexity of O(n 2 ), while any exhaustive algorithm has the complexity at least O(n 3 ), [START_REF] Cech | Efficient sequential correspondence selection by cosegmentation[END_REF]. Factor n 3 is the size of the search space where the correspondences are sought, i.e. the disparity space. The growing algorithm does not compute similarity statistics of all possible correspondences, but efficiently traces out components of high similarity score around the seeds. This low complexity is beneficial especially for high resolution imagery, which allows precise surface reconstruction.

The proposed algorithm with all presented modifications does not represent any significant extra cost. Triangulation of TOF seeds and the prior disparity map computation is not really expensive as well as the computing the new EPC statistic instead of MNCC.

For our experiments, we use an academic (combined Matlab and C) implementation which takes about 5 seconds with 2 MP images. Nevertheless, recently [START_REF] Dobias | Real-time global prediction for temporally stable stereo[END_REF] presented an implementation of the growing algorithm [START_REF] Cech | Scene flow estimation by growing correspondence seeds[END_REF] which runs in real-time in normal CPU, without parallel hardware. This indicates that a real-time implementation of the proposed algorithm would be feasible. IV. CONCLUSIONS We have proposed a novel correspondence growing algorithm with fusion of a range sensor and a pair of passive color cameras to obtain accurate and dense 3D reconstruction of a given scene. The proposed algorithm is robust and performs well on both textured and texture less surfaces and ambiguous repetitive patterns. The algorithm exploits the strengths of TOF sensor and stereo matching between color cameras in a combined way to compensate for their individual weaknesses. The algorithm has shown promising results on difficult real world data as well as on challenging standard datasets which quantitatively corroborates its favourable properties. Together with the strong potential for real-time performance that we discussed, the algorithm would be practically very useful in many computer vision and robotic applications.

  (a) A TOF-stereo setup (b) The TOF image is shown in the upper-left corner of a color image.(c) The proposed method delivers a high-resolution depth map.

Fig. 1 .

 1 Fig. 1. (a) Two high-resolution color cameras (2.0MP at 30FPS) are combined with a single low-resolution time-of-flight camera (0.03MP at 30FPS). (b) A 144 × 177 TOF image and a 1224 × 1624 color image are shown at the true scale. (c) The depth map obtained with our method. The technology used by both these camera types allows simultaneous range and photometric data acquisition with an extremely accurate temporal synchronization, which may not be the case with other types of range cameras such as the current version of Kinect.

Fig. 2 .

 2 Fig. 2. Projection of TOF sensor data on left and right images. The points are color coded and the color represents disparity such that colder colors are closer to the cameras. The images are not in the true scale. Notice wrong correspondences on the computer screen due to low reflectance and artifacts along occlusion boundaries.

Fig. 3 .

 3 Fig. 3. The effect of occlusions. A background (BG) point P is seen in the left image (IL) and in the TOF image, while it is occluded by a foreground object (FG) and hence not seen in the right image (IR). In the process of reprojection of 3D TOF points, a wrong correspondence (P IL ↔ P ′ IR ) is produced.

Fig. 4 .

 4 Fig. 4. An example of the effect of correcting the set of seeds on the basis that they should be regularly distributed.

  Fig. 5. Triangulation and prior disparity map Dp. These are shown using both raw seeds (a), (c) and refined seeds (b), (d). A positive impact of the refinement procedure is clearly visible.

  uses Moravec's normalized cross correalation [17] (MNCC), simil(s) = MNCC(wL, wR) = 2cov(wL, wR) var(wL) + var(wR) + ǫ

d

  * = argmax d P (d|IL, IR, Dp).

  Fig.6. SET-1. (a) A triplet composed of a pair of color images (left and right) and a TOF image (middle), results obtained (b) using the seed growing stereo algorithm[START_REF] Cech | Scene flow estimation by growing correspondence seeds[END_REF] combined Harris seeds and MNCC statistic, (c) using TOF seeds and MNCC statistic , (d) using Harris seeds and EXPSSD statistic, (e) using TOF seeds with EXPSSD statistics. Results obtained with proposed full stereo-TOF fusion model using EPC similarity statistic (f) and full model EPC after filling small gaps (g).

  Fig. 7. SET-2. Please refer to the caption of Fig. 6 for explanation.

  (a) Dense surface reconstruction using the disparity map Dp corresponding to a 2D triangulation of the TOF data points. Zoomed sofa chair and zoomed T-shirt from SET-2 in Fig. 7(a). (b) Surface reconstruction using the proposed algorithm (EPC) shown on the same zoomed areas as above, i.e., Fig. 7(g).

Fig. 8 .

 8 Fig. 8. The reconstructed surfaces are shown as relighted 3D meshed for (a) the prior disparity map Dp (2D triangulation on projected and refined TOF seeds), and (b) for the disparity map obtained using the proposed algorithm. Notice the fine surface details which were recovered by the proposed method.

Fig. 9 .

 9 Fig.9. Middlebury dataset. We show left images, results of the same algorithms as in Fig.6 and 7, and the ground-truth disparity maps. There are error statistics (percentage of correctly matched pixels) below the disparity maps. Observations from the real-world cases are confirmed quantitatively. The algorithm using the full model (EPC) gives clearly the best results.

  Algorithm 1 Growing algorithm with sensor fusion Require: Rectified images (IL, IR), initial correspondence seeds S, image similarity threshold τ . 1: Compute the prior disparity map Dp by interpolating seeds S. 2: Compute simil(s|IL, IR, Dp) for each every seed s ∈ S. 3: Initialize empty disparity map D of size IL (and Dp).

	4: repeat
	5:

http://www.xbox.com/en-US/kinect

http://www.mesa-imaging.ch

http://www.4dviews.com

http://www.ptgrey.com/


Lucie Bailly
email: lucie.bailly@irphe.univ-mrs.fr

Audrey Lemercier

Christian Geindreau

Laurent Orgéas

Valérie Deplano

Towards New Aortic Tissues Analogue Materials: Micro-mechanical Modelling and Experiments

come   L'archive ouverte pluridisciplinaire

ABSTRACT

Human abdominal aortic tissue is a complex cylindrical soft sandwich structure, arranged in three different concentric layers. Within these layers, distribution and arrangement of all components display a double-helix architecture of wavy fibres, characterised by distinctive preferred orientations [START_REF] Holzapfel | Determination of material models for arterial walls from uniaxial extension tests and histological structure[END_REF]. The macroscopic mechanical behaviour of human healthy abdominal aorta (AA) and aneurysmal (AAA) tissues is highly non-linear, anisotropic and essentially hyperelastic [START_REF] Vande Geest | The effects of aneurysm on the biaxial mechanical behavior of human abdominal aorta[END_REF]. The global objective of this work is to design and process new artificial hyperelastic and anisotropic membranes mimicking the macroscopic histological and mechanical features of AA and AAA tissues. These materials will be then used to build more realistic phantoms of AAA for in vitro experiments [START_REF] Deplano | Flow behaviour in an asymmetric compliant experimental model for abdominal aortic aneurysm[END_REF]. The aim of the present study is (i) to develop a theoretical framework able to predict the optimal microstructure and mechanical behaviour of such AA/AAA analogues, and (ii) to provide experimental validation of micro-mechanical modelling.

Proposed target AA/AAA analogues are composite membranes composed of a thin and soft hyperelastic silicone layer reinforced by simplified periodic fibrous microstructures displaying preferred orientations. In an attempt to mimic main histological features of the biological tissues, three kinds of fibrous architecture were investigated: a one-layer lattice of straight fibres, a one-layer lattice of wavy fibres, and a bi-layer lattice of straight fibres. Each fibrous lattice can be seen as a repetition of a Representative Elementary Cell (REC) as sketched in Fig. 1(a) in case of the one-layer lattice. Fibres are supposed to be linked at the REC extremities A 1 , A 2 , A 3 and A 4 . In between these points, the mechanical behaviour of the fibres are supposed to be of hyperelastic types. To fit bi-axial experimental data obtained from the literature [START_REF] Vande Geest | The effects of aneurysm on the biaxial mechanical behavior of human abdominal aorta[END_REF], with normal or pathologic aortic tissues, the microstructure of the periodic lattices (fibre chord l 0 , angle between fibres θ 0 ) together with the mechanical behaviour of the fibres (fibre tension-elongation curve) were optimised by using theoretical results arising from an upscaling process based on the homogenisation of periodic and discrete structures [START_REF] Caillerie | Discrete homogenization in graphene sheet modeling[END_REF][START_REF] Bailly | Towards a biomimetism of abdominal healthy and aneurysmal arterial tissues[END_REF]. From this theoretical work, it is shown that a material constituted by only one periodic lattice of fibres is clearly not sufficient to describe all the experimental data set. Instead, a quantitative agreement between measurements and the model predictions is obtained by using a material with two fibre lattices (see Fig. 1(b)). Besides, the microstructures and mechanical properties of the optimised fibrous lattices are strongly different for the abdominal healthy and aneurysmal arterial tissues. In particular, the optimal angles between fibres in the case of the healthy aorta are consistent with histological data. Lastly, it must be pointed out that the anisotropic mechanical behaviour of the optimised material is described by only five parameters.

Based on these theoretical results, several types of commercial fibres were selected and their tensile mechanical behaviours were characterised. A specific device dedicated to the manufacturing of periodic fibrous lattices and square composite membranes was designed to control the architecture of the REC of the processed anisotropic hyperelastic membranes, i.e. the angle between fibres, and the fibre chord. The three kinds of fibrous microstructure were characterised by means of X-rays micro-tomograph, as illustrated on Fig. 1(a). The in-plane mechanical behaviour of the composite membranes was characterised under various loadings using a uniaxial tensile-testing device, and discussed with respect to above theoretical predictions.

Figure 1 :

 1 Figure 1: (a) Typical rhombic lattice under consideration and corresponding periodic REC of the onelayer fibrous structure solution in cases of straight fibres (left) and wavy fibres (right); (b) Comparison between the optimized theoretical predictions of the bi-layer model (solid lines) and Vande Geest experimental data from [2] (symbols) at the macroscopic scale for AA samples: Cauchy tension τ versus elongation. Legend refers to the controlled axial Piola-Kirchhoff tensions ratio.


Michael Sapienza

Miles Hansard
email: miles.hansard@eecs.qmul.ac.uk

Radu Horaud

Real-time visuomotor update of an active binocular head

Keywords: Perception, cognition, interaction Équipe-Projet PERCEPTION Real-time vision, Active binocular vision, Visual tracking, 3D reconstruction

In order for a binocular head to perform optimal 3D tracking, it should be able to verge its cameras actively, while maintaining geometric calibration. In this work we introduce a calibration update procedure, which allows a robotic head to simultaneously fixate, track, and reconstruct a moving object in real-time. The update method is based on a mapping from motor-based to image-based estimates of the camera orientations, estimated in an offline stage. Following this, a fast online procedure is presented to update the calibration of an active binocular camera pair. The proposed approach is ideal for active vision applications because no image-processing is needed at runtime for the scope of calibrating the system or for maintaining the calibration parameters during camera vergence. We show that this homography-based technique allows an active binocular robot to fixate and track an object, whilst performing 3D reconstruction concurrently in real-time.

Fixation visuo-motrice temps-réel avec un système binoculaire actif

Résumé : Afin qu'une tête binoculaire puisse effectuer le suivi optimal en 3D, elle devrait être en mesure de pointer ses caméras activement, tout en conservant l'étalonnage géométrique. Dans ce travail nous présentons une procédure de mise à jour de calibration qui permet à une tête robotique de fixer et de reconstruire simultanément, un objet en mouvement en temps réel. La méthode de mise à jour est basée sur une cartographie du moteur basé à base d'images.

Les estimations des orientations appareil, estimée à un stade déconnecté. Suite à cela, une procédure rapide en ligne est présentée à mettre à jour l'étalonnage d'une paire de jumelles appareil actif. L'approche proposée est idéal pour les applications de vision active, car aucun traitement d'image est nécessaire à l'exécution de la portée de l'étalonnage du système ou pour maintenir les paramètres d'étalonnage lors de convergence caméra. Nous montrons que cette technique basée sur homographie permet un robot binoculaire active fixer et à suivre un objet, tout en effectuant simultanément la reconstruction 3D en temps réel.

Mots-clés : Vision temps-réel, vision binoculaire active, suivi visuel, reconstruction 3D

Introduction

The estimation of scene-structure from a binocular image pair is an important task in robot vision. Once the epipolar geometry between the two cameras is known, image-features can be matched more easily, and depth information can be recovered [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. For an active binocular robot head, which continuously fixates a moving target, a real-time method for updating the relationship between the cameras is required. Such an online method would allow independent or coupled camera vergence rotations while maintaining geometric calibration. This will enable the robot to perform 3D reconstruction while actively examining different parts of the scene, or while tracking a moving object [START_REF] Grosso | Active/dynamic stereo vision[END_REF][START_REF] Barreto | Active stereo tracking of N ≤ 3 targets using line scan cameras[END_REF][START_REF] Hansard | Cyclopean geometry of binocular vision[END_REF]. Furthermore, this online calibration update must be computationally efficient if it is to be used alongside other complex algorithms such as object tracking and 3D reconstruction.

Popeye is an active binocular robot (POP Consortium, 2008), which reproduces the sensory configuration of the human head (Fig. 1). The orientation of the robot head (pan/tilt) is controlled by motors, as is the direction of the eyes (version/vergence). The robot can therefore direct its attention towards a visual stimulus in its surroundings using combined stereo and tracking techniques [START_REF] Bellotto | Computationally efficient solutions for tracking people with a mobile robot: an experimental evaluation of Bayesian filters[END_REF]. The advantage of an active vision system is INRIA that information about the environment can be gathered more efficiently, by appropriately re-orienting the cameras. Hence visual information is combined with motor control, in a feedback loop, which enables the robot to react to a dynamic environment [START_REF] Bajcsy | Active perception[END_REF].

Previous Work

In order to preserve the calibration of the stereo system after camera vergence, one could continually recalibrate the system. This would, however, be very difficult to perform in real-time. A more efficient method would be to calibrate the system once, and then to update this calibration as the cameras move. This technique was used in [START_REF] Björkman | Real-time epipolar geometry estimation of binocular stereo heads[END_REF], where the epipolar geometry was updated by extracting information from feature correspondences in the current images. This required an iterative approach to estimate the stereohead geometric parameters, which is computationally expensive. Furthermore, such an approach ignores kinematic information that can be used to improve the real-time performance of the system. The problem was also tackled in [START_REF] Hart | Epipolar geometry for humanoid robotic heads[END_REF] who developed an epipolar-kinematic model in which motor data is used to compute an updated representation of the epipolar geometry. The kinematics of the system are obtained by rotating the cameras and observing the relationship between the images of two views before and after the rotation. After this calibration procedure, the essential matrix [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]) can be updated, provided that the current settings of the camera motors are known. This approach allows computation of the essential matrix in realtime. Related methods can be used to coordinate an active camera with a static camera [START_REF] Horaud | Camera cooperation for achieving visual attention[END_REF].

The Popeye robot belongs to a class of active binocular robot heads with very accurate motors [START_REF] Shih | Calibration of an active binocular head[END_REF][START_REF] Aryananda | MERTZ: A quest for a robust and scalable active vision humanoid head robot[END_REF][START_REF] Beira | Design of the robot-cub (icub) head[END_REF][START_REF] Miwa | Development of a new human-like head robot we-4[END_REF]. Moreover, the design of the eye pan mechanical structures allows each camera position to be precisely adjusted to achieve close agreement between the optical and rotational centres of the cameras. This permits a direct approach to epipolar-update, as described in section 2. The accuracy and negligible backlash of the DC brushed motors ensures the repeatability of the new method, as demonstrated in section 3.

The present work is closely related to certain autocalibration procedures [START_REF] Hartley | Self-calibration of stationary cameras[END_REF][START_REF] Ruf | Visual servoing of robot manipulators Part I: Projective kinematics[END_REF][START_REF] Knight | Automated alignment of robotic pan-tilt camera units using vision[END_REF], in which constrained movements are used to estimate the camera parameters. The aim of the present work is somewhat different; we estimate a direct mapping from motorsettings to image-transformations, without explicitly estimating the calibration parameters.

The paper is organized as follows. The problem definition and main contributions of this work are stated in sections 1.2 and 1.3. Sections 2.1, 2.2 and 2.4 describe the estimation, analysis and synthesis of homographies, respectively. The new method is based on the statistical model (3), which allows for uncertainty in the homography estimates, as defined in section 2.3. Section 3 describes the results of experiments using Popeye. The conclusions of the work are stated in section 4.

Problem Definition

The problem to be solved is that of compensating for the effects of known camera-rotations on the images. This is important for both monocular and binocular tasks, as described below. The monocular geometry (which applies equally to the left and right cameras) will be described first.

The standard pinhole-camera model will be used to represent the imaging process. The scene and image points will be identified by homogeneous coordinates X ≃ (X, Y, Z, 1) ⊤ and x ≃ (x, y, 1) ⊤ respectively, where '≃' indicates equality up to a non-zero scale factor. If the pose of the camera, with respect to the scene coordinate-system, is represented by the 3 × 3 rotation matrix R and 3 × 1 translation-vector t, then x ≃ A(R |t)X , where A is the (invertible) upper-triangular matrix that contains the intrinsic parameters [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. Now consider two views, V and V j , that differ by a rotation of the single camera described above. Specifically, suppose that the camera is aligned with the scene-coordinate system, and that image-points x ∈ V and x j ∈ V j are observed before and after a vergence rotation (monocular pan) of angle θ j . It follows that x ≃ A(I |0 )X and x j ≃ A(R j |0 )X and therefore

x j ≃ H j x where H j ≃ AR j A -1 .

(1)

The full-rank 3 × 3 matrix H j represents the homography [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]) that maps view V to view V j , as shown in Fig. 2. The matrix H j will be analysed in section 2.2. Now, in the binocular case, let x ℓ and x r be corresponding points in the left and right images. The epipolar geometry of the binocular system is expressed by the constraint x ⊤ r F x ℓ = 0 where F is the fundamental matrix [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. If the cameras are rotated, by angles θ ℓj , θ rj , then the new coordinates x ℓj , x rj will not be compatible with F . However, if homographies H ℓj and H rj are available, then the points can be transformed back to the coordinate system of F , so that (H -1 rj x rj ) ⊤ F (H -1 ℓj x ℓj ) = 0. Alternatively, F itself can be transformed, so that the general epipolar constraint is

x ⊤ rj F j x ℓj = 0 where F j = H -⊤ rj F H -1 ℓj . (2)
The cases H ℓ0 = I and H r0 = I are defined so that F 0 = F is the original fundamental matrix. The original problem, of compensating for binocular vergence, has now been reduced to that of estimating the homographies H ℓj and H rj .

There are two possible ways to estimate these matrices. This is an essentially monocular task, and so the left/right subscripts will now be suppressed. In the image-based method, H j is estimated from 1 ≤ k ≤ N point-correspondences x k ↔ x jk . This method is accurate, but it is also slow, as an additional correspondence problem must be solved after every camera movement. Alternatively,

INRIA

Figure 2: A camera samples the bundle of rays that pass through the optical centre C . Two different views, separated by a rotation of θ j , are indicated by the planes V and V j . Corresponding points x and x j , which are images of X , are related by a projective transformation H of the projective space P 2 . in the motor-based method, the current motor-angle θ j is substituted into the underlying rotation matrix R j which appears in (1). This method is fast, but the results are inaccurate, owing to residual misalignment of the optical and rotational centres (see sec. 2.3).

Main Contributions

This paper shows that the image-based and motor-based approaches, as described above, can be combined. The resulting method has the accuracy of the former approach, as well as the speed of the latter. An outline of the new method is given below.

Firstly, in an offline calibration procedure, the image-based method is used to estimate the homographies H j that are induced by a set of motor-angles θ j , where 1 ≤ j ≤ M , as described in section 2.1. Each estimated homography determines another angle φ j , which is extracted from the matrix H j , as described in section 2.2. The image-based and motor-based angles are theoretically equal, φ j = θ j . In practice, however, there is a systematic difference between these parameters, owing to the optical and mechanical effects described in section 2.3. These systematic effects can be represented by a statistical model f , and a vector of parameters η, such that φ ≈ f (θ, η).

(3)

If the parameters can be learned, then a homography-angle φ can be predicted from any current motor-angle θ, as described in section 2.3. The corresponding homography H θ can then be quickly constructed following a real-time online procedure described in section 2.4. This method is accurate, because the predicted homography H θ must be compatible with the original H j at all fitted values θ = θ j , where j indexes the M views that are used to estimate the model (3). This method is also fast, because no feature point extraction and matching is required after each camera rotation. This computational efficiency allows the system to fixate a moving target with calibrated cameras. Finally our proposed method is robust because at runtime, it does not depend on the scene texture, establishing feature point correspondences, or a generic scene assumption, unlike purely image-based methods (section 3.5). In summary, the main contribution of this paper is a novel method for realtime epipolar geometry update, which is applied to an active binocular robotic head. We demonstrate the validity of this homography-based method on the Popeye robot, which can simultaneously fixate an object, track it over time, and perform 3D reconstruction in real-time.

Methods

The update-procedure will now be presented, in order of execution. Most importantly, section 2.3 introduces a model and solution for the angle mapping (3).

INRIA

Homography Estimation

The initial homographies H j are estimated by the standard direct linear transformation algorithm [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. Each homography has eight degrees of freedom (3 × 3 minus scale). This means that k = 1, . . . , N correspondences x k ↔ x jk are required, where N ≥ 4. It can be shown [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]) that each correspondence defines a pair of homogeneous constraints

0 ⊤ 3 -w k x ⊤ jk y k x ⊤ jk w k x ⊤ jk 0 ⊤ 3 -x k x ⊤ jk h j = 0 2 (4)
where

x k = (x k , y k , w k ) ⊤ , h j = H 11 j , H 12 j , . . . , H 33 j ⊤
, and 0 L is the columnvector of L zeros. The N instances of the 2 × 9 matrix on the left of ( 4) are stacked to form a single 2N × 9 matrix G j . A solution for H j can then be obtained from the right singular-vector of G j that corresponds to the smallest singular value.

Homography Analysis

Recall from ( 1) that H j ≃ AR j A -1 , where R j is a rotation matrix. This means that the homography H j is a conjugate rotation, having the same eigenvalues as R j [START_REF] Hartley | Self-calibration of stationary cameras[END_REF]. Furthermore, H j can be decomposed as

H j ≃ U D j U -1 (5)
where D j is a diagonal matrix of eigenvalues, and U j is a matrix of eigenvectors.

The decomposition has the following structure [START_REF] Hartley | Self-calibration of stationary cameras[END_REF][START_REF] Ruf | Visual servoing of robot manipulators Part I: Projective kinematics[END_REF], which involves a complex-conjugate pair of eigenvalues:

D j ≃ diag λ j , λ * j , 1 where λ j = exp(iφ j ) (6)
and U = (u, v , w ). ( 7)

The angle φ j and axis w correspond to the rotation R j . The complex vectors u and v represent the circular points in the plane orthogonal to the rotation axis [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. Under pure rotations, the axis of rotation is fixed, and therefore the matrix U remains unchanged. In practice, there are M eigenvector matrices U j , which are only approximately equal, owing to misalignment of the optical and rotational centres. Thus, a synthesis matrix Ū may be chosen as that associated with the largest motor-angle θ j , or estimated with a suitable averaging procedure in an offline learning stage. 1 Following this, the pre-computed eigenvector matrix Ū will be used in section 2.4 for homography synthesis in a real-time online procedure, since only λ j needs to be computed at runtime. The angle φ can be computed from the motor-rotation θ as described in the following section.

Motor-Based Parametrization

This section addresses the chief issue, which is the relationship (3) between the motor parameter θ, and the homography parameter φ. The model f in (3) must account for two systematic effects. Firstly, the existence of a 'pinhole' optical centre is only an approximation for real cameras. Secondly, the approximate optical centre may not coincide with the rotational centre of the system. This means that camera rotations will be accompanied by small translations [START_REF] Hayman | The effects of translational misalignment when self-calibrating rotating and zooming cameras[END_REF]. It is important to note that these effects need only be modelled over a limited range of angles, as determined by the mechanics of the system. Furthermore, this range has a natural origin, which corresponds to the straight-ahead camera position. All motor-counts θ are specified in relation to this origin.

The preceding considerations suggest the zero-offset linear model φ ≈ η θ, which will be experimentally validated in section 3. This model states that the M available angle-pairs {θ j , φ j } are related by

φ j = η θ j + ǫ j where 1 ≤ j ≤ M. (8)
The random errors ǫ j are due to the optical and mechanical effects described above, as well as to lens distortion and feature mis-localisation. The unknown parameter η can be estimated, given one or more angle-pairs. The estimation procedure requires the definition of a distance metric in which the observed discrepancies δ = φ -η θ can be minimized. Two possible metrics are |δ| R ∈ [0, ∞], the standard Euclidean metric on R 1 , and |δ| S ∈ [0, 1], an angular metric on the circle S 1 . These are respectively defined as

|δ| R = √ δ 2 and |δ| S = 1 2 (1 -cos δ). (9)
The Euclidean metric is not suitable for general angular problems because, for example, |δ| R = |δ + 2π| R . However, using the Taylor approximation cos

(δ) = 1 -1 2 δ 2 + O(δ 4 ), it is clear that |δ| S = 1 4 |δ| 2 R + O(δ 4 ). (10)
Hence, for small values of δ, it is possible to use |δ| 2 R rather than |δ| S . This is important, because the Euclidean metric is much easier to work with. The approximation can be quantified by the relative error

E RS (δ) = abs |δ| S -1 4 |δ| 2 R |δ| S . (11)
The maximum relative error E RS (φ j -θ j ) is 0.12% for the data-set used here, and so the Euclidean metric will be used. It will be demonstrated in section 3.3 that the results of using |δ| S are, for practical purposes, identical.

The minimum of the Euclidean error can be found by setting the derivative d/dη of 1 4 N j |φ j -η θ j | 2 R to zero. This leads to the well-known estimate for

INRIA

Algorithm 1 Offline parameter estimation 1. Estimate homographies H j induced by a set of motor-angles θ j (section 2.1).

2. Eigendecompose H j to obtain (i) eigenvalues λ j , from which the imagebased rotation φ j is found, and (ii) a matrix of eigenvectors Ū (section 2.2).

3. Estimate parameters η relating image and motor-based rotation angles using (12).

the slope of a regression-line through the origin:

η = M j θ j φ j M j θ 2 j . ( 12
)
If the errors ǫ j in (8) are normally distributed, pr(ǫ j ) ∝ exp -1 2 ǫ 2 j , then η in ( 12) is also the Maximum Likelihood estimate of the underlying parameter η.

It is now straightforward, given any motor angle θ, to compute a predicted homography angle φ = η θ (13) by analogy with the original model ( 8). This prediction, given the estimate η, does not involve any other computations.

Homography Synthesis

Suppose that a homography angle φ has been predicted from a motor-angle θ, using the fitted model (13). It is then possible, by inverting the procedure of section 2.2, to create a new homography H , as noted in [START_REF] Hartley | Multiple view geometry in computer vision[END_REF][START_REF] Knight | Automated alignment of robotic pan-tilt camera units using vision[END_REF]. First, by analogy with (6), the eigenvalue matrix is synthesized:

D = diag λ, λ * , 1 where λ = exp(iφ), (14)
and λ, λ * are complex conjugates. The coordinates u and v of the circular points (7) are independent of the rotation angle. It follows that, by analogy with (5), the synthesis matrix of eigenvectors Ū can be combined with D as follows,

H = Ū D Ū -1 (15)
which gives the estimated homography. The above procedure is performed separately for the left and right cameras, so that H ℓj and H rj are obtained from θ ℓj and θ rj , respectively. It is emphasized that only (13,14 & 15) need to be computed at run-time, with Ū fixed in advance. The current fundamental matrix F j is then obtained from H -⊤ rj F H -1 ℓj , as in (2). Both the offline and online parameter estimation procedures are detailed in algorithms 1 and 2 respectively.

Algorithm 2 Online epipolar geometry update 1. Calculate predicted homography angle φ using (13).

2. Create new homography H from synthesized eigenvector matrix Ū and eigenvalue matrix D as in ( 14).

3. Update fundamental matrix F j using the homographies H ℓj and H rj representing the rotation of both cameras using (2).

Experiments and Results

In order to evaluate the new approach, a sequence of tests were carried out using the Popeye robot, as described in sections 3.1 and 3.2. The experiments were set in a laboratory environment in which the Popeye head was placed in a position to best view any surrounding activity. The resulting data is explored in section 3.3, and the assumptions of section 2 are validated. The performance of the new method is evaluated in section 3.4 using an image-based error measure, and compared to a purely image-based method (section 3.5).

Robot Hardware

The robot's vision system consists of two PointGrey colour cameras, which provide images of size 1024 × 768. The Popeye head has four rotational degrees of freedom, but only the left/right vergence motors are used for the experimental analysis. The rotations are performed by DC brushed motors, which are controlled by discrete (and repeatable) angle-steps. The mechanical system also provides a reference position (straight ahead).

Calibration Procedure

A practical angular range of operation was chosen to be ±20 • around the reference position, as shown in Fig. 3. This range was split into a discrete set of nine views V j , each separated by ∆θ = 5 • . The resulting images are representative of the viewable area of the scene. Textured cards were fixed to the facing furniture, containing stable calibration features. Each camera was rotated in turn by ∆θ over the whole angular range of operation, at each step taking a snapshot of the viewable area. For each view, ten evenly distributed feature-points were matched and verified by standard methods [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. Three calibration runs were performed for each of the two cameras, giving a total of six data-sets. The homography matrices mapping each view V j to the fronto-parallel position V were then estimated, using the method of section 2.1. The eigendecomposition of 2.2 was then used to extract the homography angle φ j corresponding to each motor angle θ j . The linear model f , that characterizes the relationship between the motor-angle θ and the homography-angle φ, was then estimated by the method of section 2.3.

INRIA

Figure 3: An illustration of the motor-camera calibration procedure. For each camera, a set of images are extracted which are representative of the viewable area. The relationship between the motor-angle θ and the homography-angle φ is modelled by the method described in section 2.3.

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
Figure 4: Visualization of the relationship between φ j (inner points) and θ j (outer points) for the left and right cameras. The connecting lines would be purely radial if all {θ j , φ j } pairs were equal. The area of each translucent sector is proportional to the corresponding angular discrepancy |φ j -θ j |.

Exploratory Analysis

The first task is to examine the relationship between the measured motor angles θ j and the estimated homography angles φ j . The mean absolute discrepancy |θ j -φ j | is 2.92 • , with a standard deviation of 1.85 • . The maximum absolute discrepancy is 6.87 • . The data from the first trial are plotted in Fig. 4. It can be seen that the discrepancy tends to increase for more extreme views, in agreement with the model φ ≈ ηθ in ( 8).

The data can now be used to validate the quadratic approximation |δ| R of the angular error |δ| S in (9). Note that the latter is a data-dependent sum of j = 1, . . . , M cosinusoids, 1 2 1 -cos(φ j -ηθ j ) . The small range of the angular errors means that there is no significant difference between the minima of the two metrics, as shown in Fig. 5. The optimum η for the angular error (found by numerical minimization) differs from the regression estimate η in (12) by 1.9 × 10 -8 .

Having validated the error-metric, the adequacy of the simple model φ = ηθ + ǫ in (8) must also be confirmed. This can be done by plotting the predicted values φ θ = ηθ in the same form as the observed values in Fig. 4. It can be seen from Fig. 6 that, with respect to the predicted values, there is no systematic pattern in the residuals. This indicates that the linear model is adequate.

Lastly, the validity of the synthetic homographies can be checked visually, in the actual images. This is done by synthetically un-rotating the robot's current view, based on the known motor angles and fitted models, as illustrated in Fig. 7(a)-(c).

Quantitative Evaluation

Consider the views V and V j , separated by an angle θ j and related by homography H j . Recall that point x k in V is mapped to point x jk in V j as x jk ≃ H j x k (1). The error of each mapping H j will now be evaluated over the N point-pairs in each data-set. The points are subject to errors in both images, and so the symmetric transfer error [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]) is used: 9), on the actual data-set. The upper plot shows periodic form of the angular error. The global minimum is well-approximated by a parabola, as in (10). The least-squares estimate ( 12) is the minimum of the parabola, indicated by the vertical line. For the present data, the difference between the two metrics is insignificant. The lower plot shows a magnified view.

E 2 H j = 1 2N N k=1 d 2 x k , H -1 j x jk + d 2 x jk , H j x k . ( 16
• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
Figure 6: Visualization of the relationship between φ j (inner points) and φ = ηθ j (outer points) for the left and right cameras. The angular errors (represented by the translucent sectors) are greatly reduced with respect to those in Fig. 4 (note that the inner points, representing φ j , are unchanged).

INRIA

Here, for example, d2 x jk , H j x k is the squared Euclidean image-distance between the measured point x jk in V j and the point H j x k that is mapped from the reference view V. This criterion will be used to quantitatively evaluate the accuracy of the synthesized homographies that were obtained from the motor-camera model. Matched points were extracted from the three data-sets, with left and right views spanning ±20 • of pan. For each set of images, the motor-camera calibration procedure was carried out as described in section 3.2. The estimated linear relationship between the homography-angles φ j and the motor angles θ j can be seen in Fig. 8.

The model parameters were then used to synthesize the homographies needed to map the scene points from the fronto-parallel images V to the rotated views V j at angles θ j . For a comparison between our motor-image based and a purely image-based method, we additionally estimated the homographies with the standard direct linear transformation (DLT) algorithm [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. The actual and predicted scene points obtained with both methods were then compared in terms of symmetric transfer error, as defined in ( 16). A discussion of the results obtained with both methods is presented in the following section.

Discussion

The results obtained after computing the RMS transfer error for our motorimage method, over all six data sets, 2 was 2.09 pixels (in the 1024×768 images). The maximum and standard deviation of the transfer errors were 6.68 and 1.16 pixels, respectively. The purely image-based method achieved an RMS transfer error of 1.03, and a maximum and standard deviation of 3.28 and 0.58 pixels respectively. The plots in Fig. 9 show a breakdown of the errors across the two cameras, nine angles and three experimental trials.

Note that image-based results are representative of an ideal case, in which sufficient stable points and perfect correspondences are available to the algorithm. In practice, an automatic interest point detector and correspondence algorithm will have to cope with low textured scenes, and imperfect matches.

The results from Fig. 9 show that in an ideal case, the purely image-based method will produce lower pixel errors. However, a collection of independently fitted homographies has many more parameters than our synthesis model, so indeed they should produce a better fit. Let N c and N r denote the number of monocular cameras and monocular camera rotations respectively. Then, the number of estimated parameters for the image-based method is 8 × N r × N c , estimated online (H has 8 degrees of freedom). For the motor-image method, the number of parameters is (1 + 8) × N c , estimated offline (1 dof from φ, and 8 from the U matrix). U has at most eight degrees of freedom, as it is obtained from the 3 × 3 matrix H , which is defined up to an overall scale. More importantly, it is clearly seen that the number of parameters estimated by our Note that H 0 = I , by definition, and so there is no error at θ = 0. The image-based method (green) represents the best case scenario where there are sufficient stable points, prefect correspondences, and necessary scene structure to avoid degenerate cases. Our motor-image approach (black) shows performance in practice and does not require point correspondences, scene texture or a particular structure.

Left Camera

method does not depend on the number of camera rotations, N r . For example in our experiments, the number of estimated parameters totalled 8 × 8 × 2 = 128 for the image based method, and (1 + 8) × 2 = 18 for the motor-camera method.

It is additionally important to point out that for our motor-image based technique, the scene-structure or texture is of no particular importance; each image-point could represent any scene-point on the corresponding ray (as indicated in Fig. 2). Hence the motor-image based results generalize immediately to any scene.

In contrast, purely image-based methods do depend on the scene texture and structure to compute feature correspondences and to avoid degenerate cases. In the case where F is re-estimated online, at least n ≥ 7 point correspondences are needed after each camera rotation, subject to the points being in general 3D position. This means that the points must not lie on (or near) a plane or other 'degenerate' surface, [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. The image based method to which we compare involves the re-estimation of homographies to update F . In order to compute each H , at least four (no three collinear) point correspondences per camera rotation are required. Since the motor-image method does not depend on computing H from feature point correspondences, it is not susceptible to the degeneracies described above, making it invariant to scene texture and structure. A complete theoretical error analysis of the epipolar geometry [START_REF] Csurka | Characterizing the uncertainty of the fundamental matrix[END_REF][START_REF] Brandt | On the probabilistic epipolar geometry[END_REF] is beyond the scope of this work.

In these experiments we have shown that our method accounts for small misalignments in the optical and rotational camera centres. The development of a similar approach which accounts for the purposeful misalignment of camera rotation and optical centres [START_REF] Hayman | The effects of translational misalignment when self-calibrating rotating and zooming cameras[END_REF] is left for future work.

Target tracking and 3D reconstruction

In order to validate the homography-based method in a real-world setting, the algorithm was used to extend the capabilities of the Popeye robot by allowing sparse 3D reconstruction during camera vergence movements. Whereas previously the cameras of the robot were static and the viewable area constrained to the initial calibration position of the cameras, it is now possible to allow the cameras to move and verge on a target of interest whilst maintaining its calibrated state. A simple gaze control feedback algorithm was implemented to keep each camera centred on a target of interest as it moved. In this scenario, the robot was placed in a room and its task was to keep track of a human face whilst performing sparse 3D reconstruction of this area of interest.

The possible movements allowed by the binocular robot are horizontal head pan rotation, a vertical tilt movement, and independent pan movements for the stereo cameras. The camera pan movements are considered to be independent and we consider the task of bringing the target position to the centre of the cameras as a monocular tracking task, unlike the tracking in [START_REF] Pagel | Self calibration of the fixation movement of a stereo camera head[END_REF], in which the camera movements were coupled. This leads to a simple update procedure to bring the object of interest to the centre of each camera:

δθ ∝ arctan δ x f x δψ ∝ arctan δ y f y (17)
where δθ and δψ are the damped pan and tilt eye motor rotations necessary to keep track of a moving target under stability. The damping factor for each motor ξ was found by giving a step-input in the form of a fixed face target to the active head. The motor response was plotted for varying ξ in Fig. 10, and the parameters close to critical damping were chosen.

The commonly used Viola-Jones face detection algorithm [START_REF] Viola | Robust real-time face detection[END_REF] was used to return the position of a single face in each of the camera images. Feature points within this face area were found using an interest point detector [START_REF] Harris | A Combined Corner and Edge Detector[END_REF]. A more recent method inspired by human visual attention [START_REF] Frintrop | Active gaze control for attentional visual SLAM[END_REF] can easily be incorporated to determine a region of interest in the image. The detected feature points were matched after limiting the search-space, for each point, to a region around the conjugate epipolar line. The matched points were then triangulated and plotted in euclidean space as shown in Fig. 11(a)-(c). The complete system runs in real-time (approx. 6fps), with all image-processing implemented on standard

Conclusion

The results described in section 3.4 show that the new method of homographygeneration is sufficiently accurate for practical use. For example, the method can be used to predict the coordinates of image-features, after controlled rotations of the cameras. The method is also useful for binocular vision, in which the fundamental matrix is updated as described in section 1.2. Furthermore, the new method is also fast, because the mapping from motor settings to image transformations is only estimated once. No additional point-correspondences are needed at run-time, and so computationally expensive feature-extraction and matching is avoided. The methods described here have enabled active tracking and image-stabilization to be performed in real-time by the Popeye robot.

Future work will consider more complicated models for the mapping φ ≈ f (θ, η) which relates the motor and homography angles (3). It is expected that the method can be extended, in this way, to systems that have poor alignment between the optical and rotational centres. Finally, the idea of estimating the relationship between control-based and image-based parameters could be applied to other visual processes, such as active zoom.

Figure 1 :

 1 Figure 1: The Popeye active binocular robotic head (designed and built in the Institute for Systems & Robotics, University of Coimbra, Portugal). The binocular vergence is controlled by a pair of motors, one below each camera. The pan and tilt angles of the head are controlled by another pair of motors.

Figure 5 :

 5 Figure5: Comparison of the angular (dashed) and Euclidean (solid) metrics (9), on the actual data-set. The upper plot shows periodic form of the angular error. The global minimum is well-approximated by a parabola, as in (10). The least-squares estimate (12) is the minimum of the parabola, indicated by the vertical line. For the present data, the difference between the two metrics is insignificant. The lower plot shows a magnified view.

  (a) A binocular image pair taken from the fronto-parallel configuration (left camera -right camera). (b) The left and right cameras are rotated by -10 and +12 degrees respectively, and the homographies representative of these rotations are calculated.(c) The estimated homographies are then used to un-rotate the current images to the original fronto-parallel views (note: the field of view is truncated).

Figure 7 :

 7 Figure 7: Visual validation of the synthesized homographies.

Figure 8 :Figure 9 :

 89 Figure8: Homography-angles φ j plotted as a function of the motor-angles θ j . Three trials are shown (rows) for each camera (columns). The least-squares regression model is drawn through the data points. It can be seen that the homography/motor relationship is approximately linear, with a slope η < 1. The dashed line, for comparison, has unit slope.

Figure 10 :

 10 Figure10: Response of the active binocular head motors to a step input. A static face was detected and the cameras rotated to fixate on the face. The damping factor was tuned so as to give a fast rise-time with minimal overshoot.

  (a) A snapshot of the sparse reconstruction (left) of the plane formed by a textured poster (right) fixed to the wall of the lab. (b) The active head has detected a face and begins to track its movement whilst reconstructing matched points in this region of interest.(c) As the target moves closer to the camera, the vergence angle between the cameras is updated to continually maintain fixation.

Figure 11 :

 11 Figure 11: A 3D viewer (left) and the image captured from the left camera of the binocular stereo pair (right). In all three camera images, the matched points (red dots) are plotted in euclidean space and seen with the 3D viewer, which is updated in real-time. The motion of the head, for example between 11(b) and 11(c) is well reconstructed despite the camera movement and varying vergence angle.

  Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Main Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . Homography Estimation . . . . . . . . . . . . . . . . . . . . . . . 2.2 Homography Analysis . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Motor-Based Parametrization . . . . . . . . . . . . . . . . . . . . 2.4 Homography Synthesis . . . . . . . . . . . . . . . . . . . . . . . .

	1 Introduction
	1.1 2 Methods
	2.1

3 Experiments and Results 3.1 Robot Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Calibration Procedure . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Exploratory Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Quantitative Evaluation . . . . . . . . . . . . . . . . . . . . . . . 3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Target tracking and 3D reconstruction . . . . . . . . . . . . . . .

RR n°7682

The Ū matrix was obtained by computing columns ū and w as the leading eigenvectors of j u j u ⊤ j and j w j w ⊤ j respectively, with v = ū * .RR n°7682

The statistics were computed after excluding the 'perfect' values at θ = 0.RR n°7682

Visit: http://www.youtube.com/watch?v=jcIK8AMoejo RR n°7682