Matthew Cassidy
email: matthew.cassidy@etu.enseeiht.fr

Jean Mélou
email: jean.melou@toulouse-inp.fr

Yvain Quéau
email: yvain.queau@ensicaen.fr

François Lauze
email: francois@di.ku.dk.

Jean-Denis Durou
email: durou@irit.fr

Refractive Multi-view Stereo

Keywords: 3Dreconstruction, Multi-view Stereo, Refraction

In this article we show how to extend the multi-view stereo technique when the object to be reconstructed is inside a transparent -but refractive -material, which causes distortions in the images. We provide a theoretical formulation of the problem accounting for a general, non-planar shape of the refractive interface, then a discrete solving method, which are validated by tests on synthetic and real data.

Introduction

Many Natural History Museums have collections of fragile specimens embedded in a transparent medium, for instance a prehistoric insect trapped in a block of amber, or a small animal conserved in a solution of formaldehyde or alcohol in a glass jar (see Fig. 1). They constitute an invaluable source of information for evolutionary scientists. Exploitation of these resources necessitates "see through" 3D-estimation techniques. Computerised tomography (CT) provides a 3D-reconstruction, however it requires special CT scanners that can handle objects of various sizes. It is expensive and time consuming. This may be feasible for a limited amount of samples but out of reach for large collections (thousands of amber pieces, or linear kilometers of specimens in jars). Photogrammetric 3D-scanning is a reasonable alternative, which however requires overcoming several difficulties.

First of all, if the refractive medium deflects the trajectory of light rays that pass through it, the shape of the interface, i.e. the separation surface between air and this medium, has a strong influence on the appearance of the object to be reconstructed. In the example on the left in Fig. 1, it is not forbidden to cut the amber block to give it a particular shape, as long as this does not alter the insect. The shape of the refractive interface will thus be assumed to be known. However, unlike most existing techniques, we do not restrict our attention to the planar case.

Refraction can cause other difficulties. Because it is wavelength dependent, it causes light dispersion. In addition, an inhomogeneous transparent medium may have spatially varying refractive index, resulting in light rays that are not straight. Taking a varying refractive index into account does not present an intractable difficulty, but estimating this index at each point in the medium is in itself a difficult problem. We will therefore assume that the refractive medium is homogeneous and that the refractive index varies little with wavelength.

Contributions -We introduce a general 3Dreconstruction method for objects trapped inside a homogeneous refractive medium with arbitrary, known interface, from a set of calibrated multi-view stereo images. The paper is organized as follows. In Section 2, we review the main studies taking into account refraction. We show in Section 3 how to extend the multiview stereo technique in the presence of an interface. The main difficulty of this extension, which is detailed in Section 4, consists in predicting the projection in an image of a 3D point located in the refractive medium. A first set of tests is conducted in Section 5 to validate this method. In Section 6, we show how to extend it to any shape of the interface. Section 7 allows us to validate it on real data. Finally, we conclude in Section 8 by mentioning some possible extensions.

State of the Art

Light rays from a point source naturally tend to diverge. By refraction, a lens allows to deviate their trajectories to make them converge in an image point. Refraction is therefore the key to optical instruments, with the caveat that manufacturing a photographic lens assembly requires very precise alignment of the lenses that make it up, in order to limit undesired effects, called aberrations. However, if the scene itself contains transparent, i.e. refractive, objects, this modifies the appearance of opaque objects, which appear distorted.

Correcting refraction in the images -A number of papers have addressed the correction of these distortions when the transparent object, such as a window pane, is attached to the front of the camera, in which case the distortions can be calibrated, and standard 3D-reconstruction pipelines can then be employed. For example, while it is relevant to use photogrammetry to study convection in a water-filled tank, Maas shows in [START_REF] Castillón | State of the Art of Underwater Active Optical 3D Scanners[END_REF] how to take into account refraction through both sides of the glass to improve measurement accuracy. In [START_REF] Cao | Universal algorithm for water depth refraction correction in through-water stereo remote sensing[END_REF], Luczynski et al. show how to correct the images acquired by a pair of calibrated underwater cameras, protected by a glass plate, to restore epipolar geometry. The same idea of pre-correcting the images has also been explored in [START_REF] Agrafiotis | Correcting image refraction: Towards accurate aerial image-based bathymetry mapping in shallow waters[END_REF]34], as well as in [2] where correction is carried out by neural networks. It has also been shown in [20,37] that light field cameras can provide useful clues for correcting refraction in the images. Another example where the consideration of refraction is required is the 3D-reconstruction of the seabed from aerial images [7,30].

Active refraction techniques -On the other hand, several studies, which can be grouped under the term active refraction, take advantage of refraction to allow 3D-reconstruction from a single view, thanks to image duplication, using either a bi-prism [25,35], or a glass plate rotating around the optical axis [START_REF] Chen | Depth from refraction using a transparent medium with unknown pose and refractive index[END_REF][START_REF] Gao | A Refractive Camera for Acquiring Stereo and Super-resolution Images[END_REF]. A problem involving refraction, but with a different goal than ours, is that of estimating the surface of a transparent object. The solution proposed by Morris and Kutulakos consists in mapping points of interest seen through transparency [29]. Another approach is that of Ben-Ezra and Nayar [START_REF] Ben-Ezra | What does motion reveal about transparency[END_REF], who fit the parameters of a surface model in order to reproduce the distorted image of an object of known geometry. The 3D-reconstruction of transparent objects has also been revisited recently under the neural network perspective [START_REF] Li | Through the Looking Glass: Neural 3D Reconstruction of Transparent Shapes[END_REF].

Refractive structure-from-motion -Chari and Sturm showed in [11] how to extend epipolar geometry in the case where the camera is separated from the 3Dscene by a planar interface, using a 12×12 fundamental matrix. The explicit consideration of refraction in the estimation of pose by structure-from-motion was also studied by Jordt et al. [21,22], Kang et al. [23], Qiao et al. [START_REF] Qiao | Structure from Motion of Underwater Scenes Considering Image Degradation and Refraction[END_REF], Suresh et al. [32], and most recently by Chadebecq et al. [9]. In most of these papers, validation is carried out on underwater images -a recent survey of underwater 3D-imaging techniques can be found in [8].

Refractive multi-view stereo -In this paper, we rather assume that the camera poses have been pre-calibrated, e.g. by structure-from-motion, and we focus on 3D-reconstruction by multi-view stereo (MVS). Extensions of the PMVS algorithm (patch-based multi-view stereo) by Furukawa and Ponce [16] have been proposed by Kang et al. [START_REF] Kang | Two-View Underwater Structure and Motion for Cameras under Flat Refractive Interfaces[END_REF] and by Chang and Chen [START_REF] Chang | Multi-View 3D Reconstruction for Scenes under the Refractive Plane with Known Vertical Direction[END_REF], but the extension process is not really detailed. Agrawal et al. have also studied MVS in a refractive medium in [3], but their work remains limited to a (multi-layer) planar interface. To the best of our knowledge, the only work considering a non-planar interface is the recent work of Yoon et al. [START_REF] Yoon | Depth estimation from stereo cameras through a curved transparent medium[END_REF]. However, their objective is different, because the curved refractive medium is placed between the observer and the object, while in our case the object lies inside the refractive medium.

Overall, there is a lack of multi-view stereo method adapted to the case of an object placed in a refractive medium with non-planar shape. The goal of our work is to fill this gap.

From Multi-view Stereo to Refractive Multi-view Stereo

Multi-view stereo (MVS) provides a dense 3Dreconstruction by maximizing the photometric consistency across a set of images. An overview of MVSrelated approaches is provided in [15]. Knowing t + 1 images of the same 3D-scene and the corresponding t + 1 camera poses, we choose the first pose as reference. For a 3D-point P visible in all the images, we note p = π(P) the projection of P into the reference image and p j = π j (P), j ∈ {1, . . . , t}, its projections into the t other images, called control images. The Lambertian hypothesis is written:

I j • π j • π -1 (p) pj = I(p), j ∈ {1, . . . , t} (1)
with I j and I denoting the grayscale functions of the j-th control image and of the reference image.

The MVS method consists in searching the 3D-point P = π -1 (p) conjugate to pixel p that "best" satisfies the system of Eqs. ( 1). This can be done by solving this system in the least-squares sense:

min P=π -1 (p) t j=1 [I j • π j (P) -I(p)] 2 (2)
In practice, this comparison is performed between the neighborhoods of two pixels, using a robust estimator (see the overview presented in [15, chapter 2]).

MVS in a homogeneous medium -When the medium is homogeneous, it is easy to parameterize the back-projection π -1 from the reference camera to the surface by using perspective projection. Denoting by P = [x, y, z] the 3D-point conjugate to pixel p, and by K the intrinsics camera matrix:

π -1 (p) = z K -1 p 1 (3)
The projection from the surface into the j-th control image is also given by central projection, along with a rigid change of coordinates system. Denoting by (R j , t j ) the known pose of the j-th camera (rotation and translation, respectively), and defining

ρ([a, b, c] ) = [a/c, b/c] : π j (P) = ρ(K [R j P + t j ]) (4)
Inserting (3) and ( 4) into (2), the 3D-reconstruction problem is easily reparameterized in terms of the sole depth value z. The function to be minimized may however be nonlinear, non-differentiable and/or nonconvex, which makes optimization potentially difficult. For this reason, minimization is usually performed by an exhaustive search (brute-force) in a list of predefined depth values. This apparently simplistic strategy proves to be very efficient for 3D-reconstruction of scenes with sufficiently textured surfaces [18]. As depicted in Fig. 2, the scenario is similar, but clearly more complex, in the presence of a refractive medium. In this case, the projection of a 3D-point P into the images is clearly more complex, due to refraction.

MVS in the presence of a refractive medium -

The presence of a medium whose refraction index is strictly more than 1, i.e. of an interface between the object to be reconstructed and the camera, has the effect of distorted images. Among other consequences, the epipolar geometry of a pair of images is lost. Instead of corresponding to an epipolar straight line in the second image, a point in the first image now corresponds to a curve, the shape of which obviously depends on the position of the interface, its geometry, and the refractive index involved.

Chari and Sturm showed in [11] how to generalize the matrix formalism of the epipolar geometry with a 12 × 12 fundamental matrix, but epipolar geometry is primarily used for the estimation of the pose by structure-from-motion. Since this problem has already been studied in several articles [9, 21], we focus on the extension of MVS, which amounts to solving Problem (2) in each point p of the reference image. Some adaptations are necessary, in comparison with the case of a homogeneous medium:

• To calculate P = π -1 (p) in the presence of an interface, we need to draw the ray from C through p. While this ray is straight in the absence of an interface, it now follows a broken line (see on the right in Fig. 2). The back-projection π -1 is thus not as simple as in (3):

π -1 (p) = P + z v (5)
where we denote by P the point of refraction, by v the direction of refraction, and by z ≥ 0 the distance travelled along that direction. Finding the point of refraction P amounts to finding the intersection between the viewing direction and the interface, while the direction of refraction v is given by the Descartes-Snell's laws (see Section 4). The first of these tasks can be tedious, depending on the parameterization of the shape of the interface.

• The calculation of p j = π j (P) is much more difficult if there is an interface, in comparison with (4). Indeed, function π j is no longer a central projection into the j-th control image. We will see in Section 4 that this calculation requires solving a shortest optical path problem.

• As shown in Fig. 3, in the case of a non-planar interface, a 3D-point P can project in several points of the j-th control image, which correspond to as many local minima of the optical path between P and C j , according to Fermat's principle. However, this does not complicate the problem, since each of these projections can equivalently be used in Problem (2).

Figure 3: Due to the non-planarity of the interface, a 3D-point P may project in several points of the j-th control image.

In comparison with the classical MVS problem, the main difficulty of refractive MVS is therefore to compute p j = π j (P), which amounts to finding the point of refraction P defined on the right in Fig. 2.

Projections into the Control Images

Descartes-Snell's first law of refraction tells us that the refracted ray lies in the plane of incidence, defined by the incident ray and the normal to the point of refraction P. For this reason, one can represent the refraction phenomenon within a plane (see Fig. 4).

Denoting by i 1 the angle between the incident light ray and the normal to the interface, in a medium of refractive index n 1 , and by i 2 the angle between the refracted ray and the same normal, in a medium of refractive index n 2 , Descartes-Snell's second law of refraction tells us that:

O u v P C j v 1 v 2 u 1 u 2 u P i 1 i 2 Interface n 1 n 2
n 1 sin i 1 = n 2 sin i 2 (6)
In the case of a planar interface, let us square both members of Eq.( 6), using the notations of Fig. 4:

n 2 1 (u 1 -u) 2 (u 1 -u) 2 + v 2 1 = n 2 2 (u 2 -u) 2 (u 2 -u) 2 + v 2 2 (7)
To determine the point of refraction P, we thus are led to solve a polynomial equation of degree 4 in ū:

a 4 u 4 + a 3 u 3 + a 2 u 2 + a 1 u + a 0 = 0 (8)
whose coefficients are expressed in function of u 1 , v 1 , u 2 , v 2 , and α = n 2 /n 1 (see [3] for more details).

Since the optical path has a unique minimum in this case, Eq.(8) has a unique real solution. Therefore, the calculation of p j = π j (P) can be done in two steps. First, to find the shortest optical path between P and C j , an equation such as (8) must be solved to determine the point of refraction P. Then, P must be projected into the j-th control image, according to (4).

One may wonder whether the transformation π j keeps the alignment of points i.e., if the image by π j of a light ray after refraction, which is a straight line, is still a straight line in the j-th control image, in which case we could simply look along this straight line to find the point conjugate to a point p of the reference image. This does not hold true in the general case, and even in the simplest case of a planar interface, it has been shown in [11] that at a point p of the reference image corresponds, in the second image, a curve whose equation is deduced from a 12 × 12 matrix.

However, this equation is not very useful to solve Problem (2). Indeed, we already mentioned in Section 3 that it is recommended to carry out the resolution of this problem by an exhaustive search in a list of 3D-points P 1 , P 2 , P 3 , etc., located for instance on parallel slices of the refractive medium (see Fig. 5).

Validation on Synthetic Images

A plausible strategy for solving the refractive MVS (RMVS) problem is therefore to proceed exactly as for the classical MVS problem, except that, for each pixel p of the reference image, and for each of the 3Dpoints P 1 , P 2 , P 3 , etc., Problem (2) now requires solving t polynomial equations of degree 4 such as (8), in addition to computing t projections such as [START_REF] Alicevision | [END_REF].

Images of the 3D-model Stanford Bunny cast in a box-shaped block of glass are simulated using the ray tracing features of the free software Blender (see Fig. 6): a wooden texture is applied on the surface of the bunny to facilitate the matching; a realistic refractive index of 1.5 is chosen for the glass; the scene is placed in front of a green background, to facilitate the background/foreground segmentation. Let us evaluate the method described in Sections 3 and 4. Fig. 7 shows two views of the colored 3D-point cloud obtained from 24 images such as that in Fig. 6, by merging four clouds. Each cloud is estimated from six images: five images taken through the same vertical face of the box are complemented by one image taken from the side. The RMSE values corresponding to the four 3Dpoint clouds which are merged to form the cloud in Fig. 7, are reported in Table 1. These very low RMSE values, compared to the scale of the reference 3D-model (in the order of 20 mm), and to the distance of the 3Dmodel from the camera (between 90 mm and 110 mm), validate the relevance of the RMVS method. Let us remark that, in the same series of simulated images as that of Fig. 6, under certain angles, the image of the bunny is duplicated (see Fig. 8). This makes it possible to implement single-view stereoscopy, in a similar way as in [25,35]. In addition to being very resource-intensive, our solving strategy presents another serious limitation: it is difficult to generalize to an interface with a more complex shape. These two problems can be overcome by opting for a fully-discrete solving strategy, which consists of discretizing the interface as well.

Discretizing the Interface

Huygens-Fresnel's principle allows us to predict the wave surfaces of a luminous flux, which are orthogonal to the light rays. A discrete version of the wave surfaces calculation is provided by Dijkstra's algorithm [13], that finds the shortest path between two vertices in a graph. To calculate the path of the light rays, we could therefore cut out the full scene into voxels, and consider them as the vertices of an indirected graph. However, the problem is greatly simplified under the assumption that the refractive medium is homogeneous. Indeed, if the refractive index is the same at any point in the block, the light propagates inside the medium along straight lines (as in the air). The path of a light ray between a point P k in the block and the optical center C j is thus a broken line, with just one break at the interface (see the red lines in Fig. 5). As already stated at the end of Section 3, finding the shortest path between P k and C j thus reduces to the search for the point of refraction P (see Fig. 4). For a planar interface, we know from Section 4 that this amounts to solving a degree 4 equation, but for more complex shapes, the analytical solving may be intractable.

To find P, a simpler solution consists in discretizing the interface, and calculating the optical path through each point of the discretized interface. Problem (2) can then be solved as follows: for each pixel p of the reference image, and for each tested point P k , one just has to find the shortest path between P k and the optical center C j (see Fig. 9). To define the discretization scale, a compromise has to be found between accuracy and a reasonable computing time. In this respect, we only test the points on the interface that simultaneously face the camera, and project inside the silhouette of the object in each of the control images.

Figure 9: For each pixel p of the reference image, and each tested point P k , the optical path between P k and C j is calculated through each point on the discretized interface. The one which corresponds to the minimum optical path is chosen as the point of refraction P.

To validate this fully-discrete solving strategy, we use the 3D-model of an insect called graphosoma. Fig. 10 shows two simulated images of this insect trapped in a spherical block of glass, seen from two viewpoints, as well as the same views of this insect outside the glass. In addition to the obvious magnification effect due to the 3D-shape of the block of glass, which is equivalent to a convex lens, strong deformations appear, particularly near the limbs. Fig. 11 shows the result by our fully-discrete RMVS solving method, obtained by merging four colored 3Dpoint clouds: each cloud is obtained from six images (one reference image plus five control images). Not only the insect's legs and antennas from these four clouds do coincide, but fine details are reconstructed. At this point, let us insist that we merge the 3D-point clouds without any post-processing.

Figure 11: Fully-discrete RMVS: Two views of the 3Dreconstruction provided by our method, using 24 images such as those of the top row in Fig. 10.

The result in Fig. 11 validates our fully-discrete RMVS solving strategy, at least qualitatively. To confirm this assertion, Table 2 lists the RMSE values of the four 3D-point clouds, to be compared to the scale of the reference 3D-model (around 20 mm), and to the distance of the 3D-model from the camera (between 90 mm and 110 mm). Without taking refraction into account, the legs and antennas are duplicated (the absence of post-processing accentuates the duplication effect), as shows the result on the left in Fig. 12 11 (RMVS) and that on the left in Fig. 12 (simple MVS).

As the result on the left in Fig. 12 is obtained by (wrongly) setting the index of the refractive medium to 1, this shows how crucial a precise knowledge of the refractive index is. An additional result provided by AliceVision, which is a classical SfM/MVS free software [START_REF] Alicevision | [END_REF], however not intended to consider refraction, is shown on the right in Fig. 12. Unsurprisingly, this result is far from being satisfactory, even qualitatively.

Figure 12: Left: Ghost legs and antennas appear when an erroneous value of the refractive index (here equal to 1) is used. Right: Misunderstanding of the graphosoma 3D-shape by the AliceVision free software [START_REF] Alicevision | [END_REF].

The image of a straight rod passing through a refractive ellipsoid (see Fig. 13) shows to which extent such an interface can distort the image. Since the projections of the 3D-points inside the ellipsoid are very difficult to predict, our fully-discrete RMVS solving method could be less accurate in such a case. Indeed, Fig. 14 shows how distorted the bunny's images are, when the glass block is ellipsoidal. Even if the 3D-reconstruction provided by our fully-discrete RMVS solving method, using six images, is faithful to the original, it is much less accurate than that of Fig. 7, because for some rays, the angle i 2 of the Descartes-Snell's law ( 6) is very close to π/2 (grazing angle). Since the derivative of the arcsin function tends towards infinity in 1, this causes strong inaccuracies in the calculation of the angle i 1 in Eq.( 6). Due to the huge distortions of the images, the 3Dreconstruction by RMVS, using six images, is far less accurate than that of Fig. 7. However, the general shape of the reconstructed 3D-point cloud is still much more significant of a bunny than the image on the left.

Validation on Real Images

Now, let us test this solving method on real images. As sets of images from Natural History Museums have not yet been produced, we use a present time insect from a private collection. It is a grasshopper cast in a box-shaped block of resin. The photographs were taken under poorly controlled operating conditions, placing the scene in front of a blue background to facilitate segmentation (see Fig. 15).

The main difficulty in implementing our 3Dreconstruction method is to estimate the camera poses. We could have used a method of estimation of the pose by refractive structure-from-motion [9], but we also need to know the position of the faces of the resin block. So we simply glued a small grid on each face, which allowed us to obtain estimates that were consistent with each other. Fig. 16 shows two views of the 3D-reconstruction of the grasshopper obtained from five images taken through the same face, plus one image taken from the side (we set the resin refraction index to the plausible value n 1 = 1.6). Although imperfect, this result is encouraging. In particular, the reconstructed legs and antennas seem realistic, which is probably an important criterion in determining whether or not we meet the needs of entomologists.

Conclusion and Perspectives

In this paper, we have shown how to adapt the multiview stereo technique to the case where the object of interest is trapped in a refractive medium. Knowing that refraction distorts the images, it is necessary to take it into account to model the path of the light rays. More specifically, we have proposed a fully-discrete solving method. Our first results on real data are encouraging, although there are still many obstacles to overcome before this preliminary study leads to an operational method that can be used by entomologists.

Among the tasks to be carried out as a priority, it is necessary to improve the estimation of the camera poses, using refractive structure-from-motion methods, which are based on the matching between points of interest seen by transparency, provided that the epipolar geometry is adapted [11].

Another improvement of our method will consist in estimating the block 3D-shape, resorting for instance to shape-from-silhouettes [19]. By taking care to place the block in front of a colored background, as we already did (see Fig. 15), this technique allows one to estimate the volume of any convex object, provided a sufficient number of images are used.

As already noticed, another essential characteristic of the refractive medium, whose precise estimation would improve the results on real data, is its index, which was arbitrarily set at 1.6 for the test in Fig. 16. Recall that the problem would be much more complex if the refractive index of the material were not homogeneous.

The efficiency of our RMVS solving method could also be improved. To give an order of magnitude of the complexity of this resolution strategy, each 3Dpoint cloud giving, by merging, the result on the left of Fig. 7, is obtained with t = 5 control images. The reference image has about 1.5×10 5 pixels. Since the block of glass is discretized into 200 slices, the complete resolution of Problem (2) requires solving about 10 8 equations of degree 4, which takes about one hour of computing time on a standard PC, using either an analytical or a bisection method of solving.

Finally, in the longer term, we plan to adapt to refraction the photometric 3D-reconstruction methods that are shape-from-shading [START_REF] Durou | Numerical Methods for Shape-from-shading: A New Survey with Benchmarks[END_REF] and photometric stereo [33]. To our knowledge, these problems have been very rarely addressed in the refractive case. In addition to the need to model the phenomenon of light attenuation inside the refractive medium, according to Beer-Lambert's law, it will also be necessary to take color into account, i.e. to consider that this attenuation depends on the wavelength. And while we have deliberately ignored light scattering, this phenomenon will also have to be taken into account in the context of photometric 3D-reconstruction.

Figure 1 :

 1 Figure 1: Prehistoric beetle trapped in amber (seen under a microscope), and reptiles specimens in jars, from the Natural History Museum in Copenhagen.

Figure 2 :

 2 Figure 2: Left: MVS in a homogeneous medium. Right: MVS in the presence of a refractive medium.In this case, the projection of a 3D-point P into the images is clearly more complex, due to refraction.

Figure 4 :

 4 Figure 4: Descartes-Snell's second law of refraction.

Figure 5 :

 5 Figure 5: We must find the projection p k j into the j-th control image of each of the points P k , k ∈ {1, 2, 3, . . . }, located on parallel slices of the refractive medium. The point P k selected is the one whose image p k j is most similar to p.

Figure 6 :

 6 Figure 6: Simulated image of the Stanford Bunny embedded in a box-shaped block of glass.

Figure 7 :

 7 Figure7: RMVS: Two views of the 3D-point cloud obtained from 24 images such as that in Fig.6. The space between the two ears of the rabbit is dusty, because this part is only visible in a few images.

Figure 8 :

 8 Figure 8: Under certain angles, the image of the bunny in a box-shaped block of glass is duplicated.

Figure 10 :

 10 Figure 10: Top row: Simulated images of a graphosoma trapped in a spherical block of glass, seen from two viewpoints. Bottom row: Images from the same viewpoints, and at the same scale, but outside the block of glass. Besides the magnification effect due to the block convexity, deformations clearly appear. Source of the 3D-model: Digital Archive of Natural History [5].

Figure 13 :

 13 Figure 13: Simulated image of a straight rod passing through a refractive ellipsoid. The projections of the points inside the medium are highlighted in red.

Figure 14 :

 14 Figure 14: Left: Simulated image of the Stanford Bunny inside an ellipsoidal block of glass. Right:Due to the huge distortions of the images, the 3Dreconstruction by RMVS, using six images, is far less accurate than that of Fig.7. However, the general shape of the reconstructed 3D-point cloud is still much more significant of a bunny than the image on the left.

Figure 15 :

 15 Figure 15: Two real images of a grasshopper cast in a box-shaped block of resin. The small grid glued on each side allows us to estimate the camera pose and the position of the planar interface.

Figure 16 :

 16 Figure 16: 3D-reconstruction of the grasshoper by RMVS: Two views of the 3D-point cloud obtained from five images through the same face, plus one side shot.

Table 1 :

 1

	Face	Front	Back	Left	Right
	RMSE (mm)	0.28	0.29	0.34	0.38

RMSE of each 3D-point cloud obtained from six images: five images taken through the same face, complemented by one image taken from the side.

Table 2 :

 2 , which is confirmed by the RMSE values listed in Table2. RMSE of each of the 3D-point clouds which, by merging, provide the 3D-reconstruction in Fig.

	RMVS (mm)	0.22	0.23	0.18	0.16
	MVS (mm)	0.51	0.83	0.72	0.31


Jonnatan Arroyo

Ramiro Velazquez
email: rvelazquez@up.edu.mx

Mehdi Boukallel

Nicola Ivan

Ramiro Velázquez

Nicola Ivan Giannoccaro

Paolo Visconti

Design and Implementation of a Low-Cost Printer Head for Embossing Braille Dots on Paper

Keywords: Assistive technology, Braille embosser, cam-follower mechanism, mechatronic device, tactile printing

est destinée au dépôt

INTRODUCTION

Visually impaired people face countless difficulties in their daily lives. This is especially true for activities such as environment understanding, urban mobility, reading, computer access, object finding, among others [START_REF] Pissaloux | Mobility of Visually Impaired People: Fundamentals and ICT Assistive Technologies[END_REF].

In particular, to address the reading and computer access challenges, three solutions have been explored so far with the aim of improving digital text accessibility: screen magnifiers, voice synthesizers, and Braille terminals. Screen magnifiers perform screen magnification for those who still have some degree of remnant vision [START_REF] Evans | Screen Readers and Screen Magnifiers[END_REF]. Voice synthesizers literally read the text displayed on the computer screen [START_REF] Gahlawat | Natural speech synthesizer for blind persons using hybrid approach[END_REF], and Braille terminals display the text on the screen in Braille code [START_REF] Velazquez | A portable piezoelectric tactile terminal for Braille readers[END_REF].

Audio books are perhaps the simplest and fastest way to convey text to visual impaired people. Entire print books are recorded while being read out loud. They can be reproduced by standard music players such as desktop component systems or wearable headsets.

Audio books are considered a simple, inexpensive, and non-Braille reading alternative for visually impaired people. Since they first became available in 1950, they have been considered a valuable tool for this population. Nowadays, a significant number of titles are available and are accessible via Internet for example, from the NLS [START_REF]National Library Service for the Blind and Physically Handicapped[END_REF]. Even though the attractive advantages they offer, two issues have still to be considered [START_REF] Velazquez | Wearable Assistive Devices for the Blind, in Wearable and Autonomous Biomedical Devices and Systems for Smart Environment: Issues and Characterization[END_REF]:

1) Availability. Not all print books are systematically produced in audible version. Moreover, there is a significant delay for new books that editorials do plan to release in audio version. Having new books in audio form could take a significant amount of time.

2) Audiobooks cannot be considered substitutional to print books. It is true that they fit perfectly the needs of the elderly and non-Braille visually impaired readers. However, as normally sighted prefer to read a printed book instead of listening to it, there is no reason to directly assume otherwise for the visually impaired. Reading heightens the self-esteem, the intellectual activity, and the independence of visually impaired people. Moreover, it increases their literacy and trains their orthography, which is generally quite bad.

Tactile printing is another method for conveying text to the visually impaired. Impact printers can stamp text and graphics (i.e. charts, graphs, mathematical functions, and diagrams) on paper by hitting it with the sufficient force to create a deformation (dot) that can be clearly felt with the fingertips. Their main inconvenient is the cost: Braille embossers or Braille printers roughly go from 2,000 to 80,000 USD [7]. In consequence, they are rarely privately owned. Normally, they can be found and used in some public libraries and special education institutions. The printing cost issue is still to be considered: printing a single page in Braille is five times more expensive than with traditional ink printers. Concerning the industrial fabrication and commercialization of tactile/Braille books, it is even more limited than that of audio books.

The printer head that strikes the paper to stamp the tactile graphics or Braille characters is the main component of the tactile embossers. Commercial embossers usually exploit the hammer solenoid technology for implementing their printer heads. Unfortunately, this technology has increased its cost over the years.

With the aim of contributing to the design of small desktop Braille embosser concepts that visually impaired people can own and use at home (Figure 1) and make Braille printing efficient and cost-effective, we introduce in this work a simple low-cost printer head device capable of embossing Braille dots and tactile graphics on paper. This device is based on traditional mechanisms such as the cam-follower and low-cost off-the-shelf actuators such as the servomotor.

The remainder of this paper is structured as follows: Section II introduces the main concepts related to Braille standards and overviews the relevant work performed on Braille character display. Section III details the printer head design and operation principle. Section IV discusses its implementation and use in Braille printers. Finally Section V closes the paper summarizing the main concepts and future work perspectives.

BRAILLE AND BRAILLE DISPLAY

Thousands of visually impaired people worldwide use Braille in their native languages as an effective way of reading, writing, and learning [START_REF] Khidri | Blind aid: A self-learning Braille system for visually impaired[END_REF][START_REF] Jimenez | Biography of Louis Braille and invention of the Braille alphabet[END_REF]. The Braille system, which was created by Louis Braille in 1852, is a system of raised dots, which form letters that can be read with the fingertips. Braille is not a language, rather it is a coding system, which can be used to read and write in many languages such as English, Spanish, French, etc.

In Braille, single text characters are normally represented by six-pin cells. Sixty-four combinations are formed from raising the pins at any of the six positions. In practice, some pin combinations are omitted as they feel the same and are complex to discriminate tactually. Letters, symbols, and words are conveyed to readers from pin combinations. Eight-dot Braille cells can also be found. They are often used to shorten symbols represented by two cells (for example, upper case characters). Figure 2 shows the main specifications of six-dot Braille cells defining the height of dots and the important distances between dots, cells, and lines.

Research concerning Braille character display has mainly focused on implementing refreshable electronic interfaces that are capable of raising and retrieving pins. Piezoelectric [START_REF] Summers | A broadband tactile array on the fingertip[END_REF][START_REF] Hernandez | Characterization of a piezoelectric ultrasonic linear motor for Braille displays[END_REF], electromagnetic [START_REF] Zarate | Using pot-magnets to enable stable and scalable electromagnetic tactile displays[END_REF][START_REF] Benali-Khoudja | VITAL: An electromagnetic integrated tactile display[END_REF], pneumatic [START_REF] Premarathna | Fabrication of a soft tactile display based on pneumatic balloon actuators and voice coils: Evaluation of force and vibration sensations[END_REF][START_REF] Yoo | Position controlled pneumatic tactile display for tangential stimulation of a finger pad[END_REF], shape memory alloy (SMA) [START_REF] Velazquez | Toward low-cost highly portable tactile displays with shape memory alloys[END_REF][START_REF] Chaves | Microactuators of SMA for Braille display system[END_REF], electro active polymers (EAPs) [START_REF] Citerin | Electro-Active Polymer Actuators for Tactile Displays, in The Sense of Touch and its Rendering[END_REF][START_REF] Matysek | Dielectric elastomer actuators for tactile displays[END_REF], and electro rheological (ER) fluids [START_REF] Liu | Touch sensitive electrorheological fluid based tactile display[END_REF][START_REF] Goto | Tactile bump display using electro-rheological fluid[END_REF] technologies have been explored for such purpose. Each technology offers its own advantages and limitations and tradeoffs between the main actuating characteristics (bandwidth, delivered force, cost, integration capacity, and scalability) have to be established for pin implementation.

Braille printing is another way for displaying Braille characters. Unlike tactile electronic interfaces, this method consists on embossing dots permanently on paper. Commercial electronic Braille embossers are based on high performance solenoids called hammer solenoids. Prototypes like the EVEREST-D V5 can output up to 140 Braille characters per second using 13 actuators, which amounts to 500 A4 pages per hour [START_REF]EVEREST-D V5[END_REF]. However, this kind of technology is far from being affordable for end users.

Research on Braille printing is sparse: Apurva et al. proposed in [START_REF]EVEREST-D V5[END_REF] a printer head involving three servomotors coupled with gears each actuating two needles. The six dots in a cell can be embossed upon the rotation of the three servomotors. Li and coworkers introduced in [START_REF] Li | Graphic printing method for new Braille printer[END_REF] an UV-curing adhesive technique to generate durable Braille dots. By opening a jet valve, glue dots are deposited on the paper surface. Kociolek et al. presented in [START_REF] Kociolek | A Braille printer on reusable thermoplastic sheets[END_REF] a thermal Braille printing device based on reusable memory shape plastic films. This technique thermally erases dots from sheets already filled with dots.

Duran and colleagues implemented a single hammer mounted in a two-axis platform [START_REF] Duran Encinas | Low-cost Braille printer prototype design with OCR technology[END_REF]. When actuated, the hammer stamps a mark on the paper. This proposal aims to contribute to the Braille printing research area by providing a new and efficient actuation idea for making Braille embossers simpler and thus, truly affordable.

SYSTEM OVERVIEW

Figure 3 shows the conceptual representation of a Braille embosser. Just as traditional ink printers, paper displacement is to be carried out by one step motor and guide rollers. A second step motor moves horizontally the printer head.

The printer head is detailed in Figure 3 inset. The design targets a device of compact dimensions (73 x 39.5 x 39 mm) fully complying with Braille standards. Three hammers strike sequentially the paper to stamp Braille dots of 0.8 mm height.

Braille embossing is done column by column, so a Braille character requires three sequences: one hammer strike, then printer head displacement, and finally another hammer strike.

Figure 4 shows the structure and main components of the printer head. Note that rotational motion is transferred from a servomotor to a shaft via a gear train. The shaft encompasses three cam-followers circumferentially arranged at 120º. The rotation of the servomotor determines which cam-follower is actuated. Feedback on the shaft's angular position is ensured by two optical encoders.

Figure 5 describes the printer head's operation while Figure 6 details the actuation sequence of the hammers. To actuate the hammers, the servomotor turns in steps of 120º. For example, to print all three dots on paper, the step motor will turn the full 360º clockwise (CW). To actuate hammers P1 and P3 being in P1, the motor would only have to turn 120º counter clockwise (CCW). Note that it is possible to actuate any hammer from any position. To move the printer head horizontally (i.e. to emboss the next column or cell), no hammer must be actuated (i.e. set down) otherwise there is the risk of breaking the paper or jamming the embosser. For this purpose, the shaft turns 60º towards the hammer that is next to be actuated to place it in a neutral position. Figure 7 shows the displacement function for the cam-follower mechanisms of the printer head. The first region (0º -80º) corresponds to hammer setting (hammer going down to emboss the paper). The hammer marks the paper when the cam is at 80º. The second region (80º -160º) corresponds to hammer resetting (hammer rising), and the third one (160º -360º) corresponds to hammer in neutral position.

This actuation approach offers interesting features such as simplicity, compactness, noiseless operation, a single actuator to control, low-cost, and ease of implementation.

IMPLEMENTATION

For the implementation of the concept, we selected a commercially available low-cost miniature servomotor from Power HD [START_REF]HD-1711MG motor, Power HD[END_REF], which provides a 3.5 kg-cm torque that ensures that hammers will develop the necessary impact force to emboss the Braille dots on paper. This servomotor offers a speed of 1.5 rad/s, which is appropriate for the application. Its dimensions and mass meet the requirements for the development of a compact printer head.

The gear train and the three cam-follower mechanisms were fast prototyped using thermoplastic material. A second stage envisages its manufacturing using metal. All parts were integrated in an ABS enclosure of compact dimensions just as envisaged conceptually in Figure 3 inset. Figure 8(a) shows the elements mounted on the shaft: a gear train and the three cams. As followers (the hammers), wood metal nails were selected together with springs to reset them and ensure their continuous contact with the cams. The wood nails were modified in their tips to obtain a conic shape instead of a cylindrical one and prevent from perforating the paper during impact. In addition, a soft damping material is needed below the printing area (see support surface in Figure 3). Several materials were tested being foamy the one that showed the best results. Figure 10 shows the general schematic diagram of the Braille embosser. Note that the data flow towards the printer head involves two stages: Braille translator and Hardware. The following subsections detail both stages.

Braille Translator

Text to Braille translation can be performed in two grades. Grade 1 Braille is the basic translation in which each printed character is substituted by its Braille equivalent. Grade 2 Braille or contracted Braille is the advanced mode in which words are shortened to fit a single cell. There are 189 contractions of the most commonly used words. Grade 2 Braille follows a complex system of rules and translation can be done properly only by a human [28].

We have developed a computer-based Braille translator tool capable of converting text files into Braille using Grade 1 Braille. Such tool basically consists of a lookup table in which letters are simply associated to their equivalent in Braille (see Figure 11). Figure 12 shows a snapshot of the graphical user interface (GUI). Developed under a Visual.Net environment, the Braille translator tool was designed to offer users a simple and intuitive translation process:

1) File-upload function: It allows the upload of supported files to be translated into Braille. Currently, the tool supports the most popular file formats such as doc, txt, and pdf.

2) Textbox function: It allows the user to freely type or paste any desired text to be translated.

Experimental measurements of the translator's computing time show that -using a modest resource standard desktop computer (simulating the equipment a visual impaired person would probably have at home) with only 256 MB of RAM memory-a page of 2,000 characters can be translated in 0.8 s. Roughly, a standard 300 page textbook can be fully translated into Braille in 240 s.

This software tool has been used in previous Assistive Technology (AT) projects [START_REF] Velazquez | A portable piezoelectric tactile terminal for Braille readers[END_REF][START_REF] Velazquez | A portable eBook reader for the blind[END_REF].

Once the Braille transcription has been completed, all characters are encoded as vectors and sent to the hardware module via serial communication. Figure 11 shows how vectors are constructed from the Braille characters. 'One' values indicate dots to be stamped while 'zeros', dots to be skipped. In addition, 'b' values are used for spaces between words while 'c' values for line change (see correspondence in Figure 2).

Hardware

Figure 13 details the components of the hardware module. Inside the printer, an electronic module encompasses a microcontroller, which processes the Braille vectors generating a buffer to control the printer head's hammers.

Communication between the printer head and the microcontroller is bidirectional because it is necessary to know with accuracy the shaft's position to actuate the cam-follower mechanisms.

In addition to receiving the Braille vectors from the software, the microcontroller manages the position data coming from the printer head's encoders and the embosser's sensors. The microcontroller controls the servomotor and the two step- motors that actuate the guide rollers and the printer head moving structure (see Figure 3). Figure 14 shows an example of printing outcome achieved with the prototype presented herein. Braille standard complying dots can be effectively embossed on paper. Our current work seeks to have visually impaired readers assess the printed pages to confirm that Braille characters are tactually discernable and comfortable to the fingertips.

As aforementioned, Braille characters are embossed at speeds of 0.2 s/120°. Letters like 'y' and 'q' requiring the highest number of dots (five) can be embossed in 1 s. Most letters of the alphabet are represented by two or three dots requiring an embossing time between 0.5 and 0.7 s, respectively.

Normally, one A4 page can contain around 1,000 characters (25 lines of 40 cells). With our system, printing a regular text page containing most of the letters in the alphabet and spaces between words roughly takes 10 min, which amounts to six A4 pages per hour. Note that this printing speed is suitable for home purposes only.

We are currently working on debugging the microcontroller's code to handle efficiently all input and output data and the daily situations traditional printers face such as paper run out, jams, diverse alerts, etc.

CONCLUSION

Developing new Assistive Technologies is important for improving the quality of life of visually impaired people. In this paper, we focused our efforts in actuators that can be used for improving digital text document accessibility. In particular, we overviewed the design and implementation of a novel printer head device capable of embossing Braille dots on paper.

Based on the traditional cam-follower mechanism concept and off-the-shelf servomotors, such device consists of three hammers that sequentially strike the paper to stamp Braille characters. The concept is simple, compact, noiseless, low-cost, easy to maintain/repair and is the base for the development of an inexpensive Braille embosser prototype intended for home use.

A Braille embosser prototype was then deployed with the printer head device and a Braille software translator as main components. Experimental results show that texts can be quickly converted into Braille using Grade 1 Braille translation and that Braille characters can be embossed in the range of 0.5 to 1 s.

Future work will focus on expanding the software translating capabilities. In particular, Internet file-formats, such as HTML would allow visually impaired users to directly print web pages in Braille. Other translation approaches such as those based in Neural Networks [START_REF] Bailon | Filipino to Chinese Speech-to-speech Translator Using Neural Network with Database System[END_REF] will be explored to offer more versatility to the prototype. It is also expected to have the translator as a free web service taking into account the quality and appearance concepts for websites described in [START_REF] Priya | Assessment of Website Quality based on Appearance[END_REF].

Figure 1 :

 1 Figure 1: Pictorial representation of a small desktop Braille printer concept.

Figure 2 :

 2 Figure 2: Standard for Braille printed pages.

Figure 3 :

 3 Figure 3: Conceptual design of a simple low-cost Braille embosser. Inset: the three-dot printer head proposal.

Figure 4 :

 4 Figure 4: The printer head's main components.

Figure 5 :

 5 Figure 5: Detail of the printer head operation. Three cam-follower mechanisms arranged at 120° intervals around the shaft strike the paper. Their actuation is determined by the rotation of the servomotor.

Figure 6 :

 6 Figure 6: Actuation logic for the hammers: the servomotor turns CW and CCW in steps of 120° to actuate the hammers.

Figure 7 :

 7 Figure 7: The cam-follower displacement function.

Figure 8 (Figure 9 :

 89 Figure 8(b) shows the first prototype of printer head developed. Its final laboratory cost is only 40 USD. The first tests conducted with the prototype have been satisfactory: the hammers emboss correctly Braille dots on bond-type paper commonly used in ink printers.

Figure 8 :

 8 Figure 8: Printer head: (a) Detail of the elements encompassed on the shaft and (b) prototype.

Figure 11 :

 11 Figure 11: Grade 1 Braille transcription and resulting vectors sent to the hardware module.

Figure 10 :

 10 Figure 10: Functional control scheme and data flow.

Figure 12 :

 12 Figure 12: Snapshot of the Braille translator GUI showing its two main functions: 1) file upload and 2) textbox.

Figure 13 :

 13 Figure 13: Block diagram of the Braille embosser hardware.

Figure 14 :

 14 Figure 14: An example of the Braille dots embossed on paper by the printer head prototype.