Correspondence Estimation and Intermediate View Reconstruction Chapters 5-8

Chapter 5 3-D geometry In this chapter, we will define basic concepts that we frequently use in 3-D processing such as camera model, projective and epipolar geometry. 5.1 Pinhole camera model Since we work on images taken by cameras, it is essential that we have a camera model to extract quantitative measures. Therefore, we will first define the basic model used in the literature which is the pinhole camera model. Although being very simple, this model accurately models the geometry and optics of most modern cameras [24]. Figure 5.1: Pinhole camera model The image formation process in a pinhole camera model is illustrated in Fig. 5.1. All of the light rays departing from the object pass through a small hole, called center of projection or optical center, and forms the inverted image on the screen. Now we Correspondence Estimation and Intermediate View Reconstruction 17 will elaborate on the geometry, and derive the equations that describe projective geometry. Figure 5.2: Projection of a point in 3D world onto image plane Consider Fig. 5.2 which shows two planes: Plane F, the focal plane, is where the center of projection resides, and plane R, the retinal plane, is where points in three-dimensional space are projected onto. The distance between plane F and R is called focal length. Now let us define two coordinate systems, one for the three dimensional space (world coordinates) (C, x, y, z) which is centered at C, and one for the retinal plane (c, u, v) which is centered at c. Now let’s study the point M with coordinates (x,y,z ) in three-dimensional space. M is going to be projected onto m on the retinal plane R through the point C on the focal plane, thus resulting in point m. Using basic geometric relation of similar triangles, the following relation can be written − Rewriting the equations we get u v f = = z x y (5.1) Correspondence Estimation and Intermediate View Reconstruction      u     =    v     z    x   −f /z 0 0 0   y     0 −f /z 0 0      z    0 0 1/z 0 1  18 (5.2) where z 6= 0 Next, we define an additional component S in order to convert the above relationship to linear, so that we can define an image point with a triplet (U,V,S) where u = U/S v = V /S and S 6= 0 This additional component comes from the idea that (U, V, S), (u, v, 1) and (u, v) should represent the same point. Finally combining previous equations, we derive the following equation.       or    x   U   −f 0 0 0      y    =  V   0 −f 0 0     z     0 0 1 0   S 1    ~M ~ ~ =P m where (5.3) (5.4) ~ = [x y z t]T . ~ = [U V S]T and M m To sum up, in (5.4) we project a point in world coordinates to the camera plane with the help of a linear equation. 5.2 Stereo camera setups There are two primary camera configurations in the literature. The parallel camera configuration uses two cameras with parallel optical axes. This configuration is frequently used due to its simplicity in both setup and mathematical derivations. Since the optical axes are parallel, they will converge at infinity and infinity will projected on the screen. This may result in excessive screen parallax on the screen and can cause viewing difficulties for the observer. Another problem is Correspondence Estimation and Intermediate View Reconstruction that depending on the distance between the cameras the common field of view may be small. This creates a problem at the correspondence matching stage. The second configuration is toed-in camera or converging camera configuration where cameras are a little rotated towards each other, so that the optical axes of cameras converge at some point other than infinity. The advantage is that the common field of view is increased. However, this configuration introduces opposing keystone distortions in the stereo pair. Keystone distortion can be described as distortion that projects a rectangular figure as a trapezoid in the picture. A comparison of these two configurations along with resulting distortions is discussed in [68]. 5.3 Camera geometry We will now define geometric relations for the camera setups mentioned in the previous section using the pinhole camera model. 5.3.1 Parallel cameras Figure 5.3: Projection of a point onto parallel cameras The parallel camera configuration is illustrated in Fig. 5.3. Consider a point P in 3D world with coordinates (X, Y, Z) and its projection onto two points pl and pr on image sensors of the left and right cameras. Let the coordinates of points pl and 19 Correspondence Estimation and Intermediate View Reconstruction 20 pr be (xl , yl ) and (xr , yr ), respectively. The horizontal distance b between the two cameras’ optical centers is called the baseline distance. Finally, assuming that two identical cameras are used, let the focal length of the cameras be f . Using the perspective transformation the following relations [25] can be written xl = f X + b/2 f −Z (5.5) Y f −Z (5.6) X − b/2 f −Z (5.7) yl = f xr = f Y (5.8) f −Z It is obvious that yl and yr are identical. This is the advantage of the parallel camera setup. Disparity d is mathematically defined as yr = f d = xr − xl (5.9) The Z component of point P can be also computed using similarity of triangles (P, pl , pr ) and (P, C, C). Z b = Z +f b+d Z= 5.3.2 (5.10) bf d (5.11) Converging cameras In converging camera setup, cameras are a little rotated towards each other at angle β so that their optical axes intersect at a convergence point. For the setup given in Fig. 5.4 the convergence point is at Zconvergence = b 2 tan β (5.12) The projection of a 3D point on convergenging cameras is more complicated than the parallel cameras case. In addition to steps in the parallel cameras case, there is also a rotation in projection. Using derivations given in [25] we can show the projection step by step i) Translation      X + b/2  X     →  Y   Y     Z Z      (5.13) Correspondence Estimation and Intermediate View Reconstruction 21 Figure 5.4: Projection of a point onto converging cameras ii) Rotation around the y axis by angle of β   X + b/2   Y   Z     cos(β)(X + b/2) − sin(β)Z   → Y     sin(β)(X + b/2) + cos(β)Z       (5.14) iii) Perspective projection xl = f cos(β)(X + b/2) − sin(β)Z f − sin(β)(X + b/2) − cos(β)Z (5.15) yl = f Y f − sin(β)(X + b/2) − cos(β)Z (5.16) xr = f cos(β)(X − b/2) + sin(β)Z f + sin(β)(X + b/2) − cos(β)Z (5.17) yr = f Y f + sin(β)(X − b/2) − cos(β)Z (5.18) Using these equations we can determine the horizontal disparity as d = xr − xl = −2f N D (5.19) Correspondence Estimation and Intermediate View Reconstruction 22 where h i N = 4 sin(β) cos(β)Z 2 + 2b − 4f sin(β) − 4b cos2 (β) Z b cos(β) [2f − b sin(β)] + 4 sin(β) cos(β)X 2 (5.20) and D = 4 cos2 (β)Z 2 + 4 cos(β) − [b ∗ sin(β) − 2f ] Z h i 4f 2 − 4f b sin(β) + b2 sin2 (β) − 4 sin2 (β)X 2 (5.21) For β = 0 the converging camera setup becomes equivalent to parallel camera setup. 5.3.3 Epipolar geometry Figure 5.5: Epipolar geometry Epipolar geometry introduces a very powerful restriction in correspondence estimation. Epipolar constraint was first introduced in [40]. In order to understand the epipolar constraint better, consider Fig. 5.5. It can be noticed that all possible physical points M that may have produced ml are the infinite half line hC, M i. As a direct consequence, all possible matches mr of ml on the right retinal plane are formed by this half-line through the second camera. This Correspondence Estimation and Intermediate View Reconstruction image is a half-line epipolar line 2 going through mr which is the intersection of the line that connects the center of projections with the right retinal plane. Using the latter observation, the epipolar constraint states that for a given ml on left retinal plane, all its possible matches on the right plane lie on a line. After introducing this constraint, the matching process reduces to one dimension from two. 23 Chapter 6 Correspondence estimation techniques In previous chapter, we have given the basics for stereo geometry which are used to solve stereo vision problems. The biggest obstacle for this problem is the correspondence estimation. Correspondence estimation can be described as finding the corresponding token (line, pixel, object etc.) in second image using a given token in the first image. By nature, correspondence estimation is ill-posed which means that the problem has no exact or unique solution or is overly sensitive to the date. There are mainly two constraints introduced to make the problem simpler. The first constraint, constant image brightness constraint (CIB) [28], is introduced in order to be able to relate luminance values and correspondence. The constant image brightness constraint states that corresponding pixels in images should have equal luminance values. However, even this strong constraint is not enough for solving the problem. Consider an image which contains a contour whose points have the same luminance, then pick a point on the contour. Since all points have the same luminance values, what is the corresponding point in the other image? Thus, CIB is not enough to convert the problem to a well-posed one [58]. The second constraint is epipolar constraint which restricts the search range for a corresponding point in one image to the epipolar line in the other image. Another problem in correspondence estimation is occlusion. As illustrated in Fig. 6.1, occlusion problem arises when a point is visible through one camera but not the other one. In such cases, correspondence estimation becomes impossible. Yet another problem can be noticed from programming perspective. As opposed to motion estimation in video, the possible range of vectors in disparity estimation is larger, therefore there are more candidates to investigate which obviously requires very high computational effort [72]. Of course, in case of the epipolar constraint, number of calculations significantly decreases, however in real-world images there is almost always a vertical component of disparity vectors. A technique called rectification [51] is used to ’adjust’ images so that images are re-projected onto planes corresponding to parallel camera setup. In other words, Correspondence Estimation and Intermediate View Reconstruction Figure 6.1: Point A is visible on right camera but not visible on the left camera images are aligned in such a way that disparities in vertical direction are cancelled after rectification step. A free rectification toolbox for MATLAB can be found in [16]. Although rectification methods help reduce the computational load, they manipulate the original images, therefore may yield problems during intermediate view reconstruction. Specifically, during the process of rectification, images are resampled. Some of the data can be lost during rectification, especially details in small areas. The loss of data may degrade the quality of resulting intermediate views. Now we will discuss methods used in correspondence estimation. Numerous methods have been proposed in literature: Block matching algorithms: These techniques match rectangular blocks of pixels in images [39, 63, 69, 10, 23]. For a block Blef t in the left image, a block Bright is searched in the right image in a predefined search window. The resemblance is evaluated using some cost function, for example Sum of Absolute Differences. Once the best match is found, same correspondence vector is assigned to all points in the block. Therefore this method a piecewise constant disparity map. The advantage of this method is its simplicity. Many efficient block matching techniques are available in video compression. Hardware implementations are also available. This method yields very good results in large textured areas that are displaced uniformly [58]. Results can be enhanced using different block sizes, however large blocks tend to work better due to carrying more features to match. Although being very simple, this method cannot fully describe disparities that yield constant depths. Another problem is the assumption that states that all points in the block should have experienced the same displacement, therefore they should 25 Correspondence Estimation and Intermediate View Reconstruction 26 have equal depth values. However, this assumption fails at object boundaries. The depth suddenly changes at object boundary, however since it is assumed that all points in a block should have the same depth, the resulting depth map will contain incorrect values if there is an object boundary in the block. One solution for this problem is changing block size in problematic areas [44]. In potential boundary areas, the block size can be reduced to accommodate the sudden change in the depth. Although this works up to some level, detection of problematic areas and implementation are difficult. Block matching is computationally expensive especially for large disparity values since a cost function is evaluated at every candidate point. Feature matching: This method tries to match a specific feature between the images. The feature may be determined automatically or by the user. This can be a line, an edge or any other specific feature in the scene [15, 17, 64, 37]. The advantage of feature matching is that features used are usually more reliable than intensities when CIB constraint does not hold. However, feature matching may face problems if the feature extraction process yields missing or false features [49]. Although feature matching techniques can compute reliable and accurate correspondences, they compute sparse maps. No disparity information is computed for non-feature points. Optical Flow: All previous methods work locally on the images, therefore resulting disparity map is sometimes not reliable. Moreover, in case of feature matching a sparse disparity map is computer. However a dense depth map which requires disparity vectors calculated for each pixel independently is required for applications such as intermediate view synthesis. Optical flow, proposed by Horn and Schunck in [29], is a seminal method that started the work towards calculating the motion globally. Optical flow is the apparent motion of a brightness pattern. In theory, the optical flow is equal to motion field1 . Let E(x, y, t) be the brightness at time t at the image point (x, y), and u(x, y) and v(x, y) be the horizontal and vertical components of the optical flow at that image point. Using the constant image brightness constraint, we can write the following equality at t + 4t where 4t is a small time interval E(x, y, t) = E(x + u4t, y + v4t, t + 4t) (6.1) Expanding the equation using Taylor series and making some approximations, we end up with the following equation which is called the optical flow constraint equation. Ex u + Ey v + Et = 0. (6.2) where Ex = ∂E , ∂x Ey = ∂E , ∂y Et = ∂E ∂t and 1 Practically, this condition is not always satisfied in some cases such as rotation of an object. Correspondence Estimation and Intermediate View Reconstruction u= dx , dt v= 27 dy dt Working solely with 6.2 will yield an irregular optical flow map. However, since the optical flow will be very similar on the average, it can be smoothed by introducing additional constraints. Assuming the rigid body motion, we can smooth most parts of the image by minimizing the departure of velocities u and v from the smoothness. Specifically, we can minimize es = Z Z ((u2x + u2y ) + (vx2 + vy2 )) dx dy. (6.3) After combining (6.2) and (6.3) and introducing a smoothness parameter λ, we minimize the following integral Z Z ((u2x + u2y ) + (vx2 + vy2 ) + λ (Ex u + Ey v + Et )2 dx dy (6.4) The corresponding Euler equations are ∇2 u = λ(Ex u + Ey v + Et )Ex (6.5) ∇2 v = λ(Ex u + Ey v + Et )Ey (6.6) where ∇2 = ∂2 ∂2 + ∂x2 ∂y 2 . Although smoothing the optical flow using additional constraints yields better estimates, it also creates a major problem at object boundaries. There will be discontinuities at the object boundaries where the motion field (or the depth) suddenly changes. Therefore, regularization algorithms that are used to smooth the optical flow should force smoothness inside a rigid body but should refrain from smoothing across the object boundaries. March discusses this problem in [47]. He proposes to use a mask for the optical flow equation, which prevents smoothing across the boundaries. Recognizing an object boundary is an easy task for a human but it is very difficult to detect in computational implementations. An edge in the image may be a boundary between objects or a textural edge as well. Explicitly marking the boundaries and preventing the algorithms work at these points may solve the problem. After Horn and Schunck, many optical flow methods have been proposed in literature: Lucas and Kanade [41], Nagel-Enkelmann [50] are two of the popular ones. For a detailed comparison of optical flow methods, refer to Barron et al.’s paper [14] which quantitively evaluates several methods. McCane et al. also compares optical flow methods in [48]. The main drawback of optical flow methods is that they cannot capture displacements more than one or two pixels due to the approximation in derivation. Therefore, hierarchical scheme implementations are required to compute large displacements. Initializating the method using coarse displacements may be another solution. Correspondence Estimation and Intermediate View Reconstruction Another drawback of this method is that the derivatives given above are numerically approximated. This requires a local spatiotemporal linearity of luminance which is not always the case for image sequences with large motion [58]. Phase-based methods: Another approach for correspondence estimation is based on phase of the Fourier transform of two images [31, 43, 42]. The idea behind phase-based methods is to compute the disparity as the spatial shift from the local phase differences in Fourier domain [42]. Usually both images are convolved with a filter and local phase is extracted from the result. Since the local shift is approximately proportional to the local phase difference, a disparity value can be estimated at each point. The filter usually exploited is Gabor filter. An FFTbased disparity estimation is also proposed in [11]. For a comparison of some of the phase-based disparity estimation techniques refer to [22]. Other methods: Since the problem is ill-posed, many other approaches for disparity estimation can be found in the literature. Although we will not give details of these methods, we will give some references to these work. One approach is simultaneous estimation of correspondence fields combined with object segmentation using Bayesian methods [20, 36]. Other approaches that use partial differential equation (PDE) based methods can be found in [56, 12, 13, 66]. The basic idea of PDE based methods is to represent the image as the level set of a higher dimensional hypersurface. Using PDEs in image analysis helps to model the images in a continuous domain, which leads to gridindependence and isotropy [59]. Another advantage of variational and PDE methods is that they allow to directly handle and process visually important geometric features such as gradients, curvatures. They can also easily simulate dynamic processes such as nonlinear diffusion [19]. Moreover, the PDE approach can achieve accurate and stable solutions with the help of available research on numerical analysis [18]. Moreover, A Maximum A Posteriori (MAP) estimation technique can be found in [9]. 28 Chapter 7 Intermediate view reconstruction techniques In previous chapter, we presented some techniques to compute the correspondences between images. Now we are going to present techniques that utilize these computed correspondences to construct intermediate views. For simplicity let’s assume the number of cameras is two and the cameras are perfectly parallel. Similar approaches can be used to extend the method for more cameras. Figure 7.1: Intermediate view reconstruction pivoting on the intermediate view We have two images Ilef t (x, y), Iright (x, y) and the correspondence (disparity) map d(x, y) and we would like to reconstruct the intermediate view Iα (x, y) at relative position α, where 0 ≤ α ≤ 1. In order to compute the intensity value of a point (x, y) on Iα , we pivot on intermediate view plane at (x, y) such that the disparity vector d(x, y) passes through (x, y). Then, we have three points of interest1 : Ilef t (x − α d(x, y), y) 1 assuming vertical disparities are zero Correspondence Estimation and Intermediate View Reconstruction 30 Iright (x + (1 − α )d(x, y), y) Iα (x, y) The basic approach to calculate the intensity of Iα (x, y) is weighted averaging. Therefore we can write the following equation Iα (x, y) = (1 − α) Ilef t (x − α d(x, y), y) + α Iright (x + (1 − α )d(x, y), y) (7.1) Since we pivoted on the intermediate view, intersections of a disparity vector with left and right images do not, in general, belong to their sampling lattices. These intensities should be computed using interpolation techniques such as bilinear interpolation or bicubic spline. Instead of pivoting on an intermediate view, we can also pivot on left and right views, however in this case, most of the points reconstructed on intermediate view will not belong to the sampling lattice. The resulting irregularly-spaced points can be projected onto orthogonal lattice using such techniques as Projection onto Convex Sets (POCS) [65]. There are a few methods that utilize the approach described by (7.1). The basic method is block-based reconstruction [33]. One disparity vector is assigned per block and all points in the block are reconstructed using (7.1). As already mentioned, the assumption that all points in a block should have the same disparity does not always hold. Therefore, it is appropriate to change the block size when required. Quadtree block matching [45] technique first calculates the disparity values for larger blocks and then reduces the block size at possible boundary locations. After estimation of disparity field, intermediate views are reconstructed using (7.1) again. Linear interpolation methods that use equation (7.1) tend to result in blurry intermediate views. Mansouri and Konrad proposed a winner-take-all approach to overcome this problem [46]. In their approach, the intermediate view is reconstructed by tilings from either left or right images. In other words, every block in the intermediate view is equal to the corresponding disparity-compensated block in either the left or right image. Although this method decreases the blurr in reconstructed image, it also introduces a patchiness effect when left and right views have significant differences in intensities. Another method by Scharstein computes two intermediate views at the same point by forward mapping (disparity compensating the images using disparity vectors) both left and right views [61]. The algorithm computes the disparity field using an intensity gradient method described in [60]. Then, both left and right images are forward mapped to intermediate location. Obviously there will be holes in forward mapped images since a point may be overdefined (i.e., more than two points in original image can fall on the same location in intermediate view) or the new point is not visible in both of the views. The next step is combining these two intermediate views. Weighted averaging is one of the methods to blend the images. Also, holes can be filled using information from one of the images. However, holes may still exist in the Correspondence Estimation and Intermediate View Reconstruction intermediate view. At this point, Scharstein uses texture synthesis methods. This method being simple, suffers from the forward mapping part. Filling the holes using texture synthesis methods may be a problem for reconstructed views. Especially areas with details may not be reconstructed properly. Redert et al. introduce a method which can reconstruct views at non intermediate positions [57]. Their motivation is to overcome the restriction that fixes the new viewpoint between the cameras. They compute correspondences using dynamic programming and working on blocks of 4x4 points. Then they compute the intermediate view at center point between the two cameras. For the rest of the algorithm, they use this center view and a single disparity map D (either right-to-center or center-to-left). They relate the center view to any view at position (Sx , Sy , Sz ) with the following formula     Szoom  X − Sx D   Xv  (7.2)    = Hc 1 − Sz f D Y − S D R Y v y where Hc and Vc are sizes of the image in x and y direction respectively, R = Hc /Vc the pixel ratio of the camera and f focal length of the camera. Image rendering using equation (7.2) also suffers from problems like in Scharstein’s case. Pixels in virtual image may be overdefined or remain undefined. In case of overdefinition authors select the point that is closest to virtual camera. For undefined case they use linear interpolation using the neighboring points to fill the holes. It should be noted that the method is successful in the sense of simplicity since it uses a single image and a single disparity map for any intermediate view. Havaldar et al. proposed a view synthesis technique in [26] which uses projective invariants. They do not require knowledge of the camera positions. An invariant, defined with respect to a transformation T , is a property which remains unchanged under transformation T . For example, parallel lines always map to parallel line under orthographic projection. Also, the ratio of line segments with respect to each other named cross ratio remains unchanged. Their method starts by extracting feature points which are usually corners and faces. Next, these features are matched using correspondence estimation methods. Given any corresponding points on two images, the prediction of the point in new image is accomplished using cross ratio of four points in two images. Since for every point whose cross ratio is computed, the location of the point in new image can be calculated, these points are linked to form wireframes in the virtual view. After this step, the boundaries of objects in the scene are reconstructed. The final step is texture mapping which uses back projection using the computed projective transform. Utilizing more than two cameras for view synthesis is also discussed in the literature. The advantage is that occluded parts may be better defined using additional views. Park and Inoue proposed an arbitrary view generation algorithm using five cameras [53]. Their camera system consists of a center camera and a total of four cameras to each direction of above, lower, left and right, separated by the same distance. The center camera is of special importance since all of the correspondence 31 Correspondence Estimation and Intermediate View Reconstruction 32 estimations will include this camera. In their algorithm, they exploit a hierarchical correspondence estimation algorithm given in [54]. This estimation method assumes that at least one of the two cameras located symmetrically (i.e., either left or right or upper or lower) is not influenced by occlusion, therefore gives correct matching data. At each step, they compare cost values of symmetric cameras and discard the larger one. This is equivalent to choosing the most proper configuration consisting of three cameras. Following this correspondence estimation step, they construct a depth map for the central camera using the disparity values. In the next step, they relate the points (x, y) in central camera with the points 0 0 (x , y ) of a virtual camera at position (Sx , Sy , Sz ) with the following equations: 1 f Sx x = x− 1 − Sz /D(x, y) D(x, y) ! (7.3) 1 f Sy y = x− 1 − Sz /D(x, y) D(x, y) ! (7.4) 0 0 where D(x, y) is the depth map and f is the focal length. By using (7.3) and (7.4), they forward map the depth map of central camera to that of the virtual camera. However, the problem of having overdefined or undefined points again arises due to the forward mapping. For overdefined points, they choose the smallest value among the multiple depth values. In order to fill the holes (i.e. undefined points) in transformed depth map, they use the concept of observable viewpoint (OVP). OVP can be defined as the direction of mapping. For example, if the camera is moved to the right, the new image on the new viewpoint will contain some information that cannot be observed from the original viewpoint and all of the new points will be on the right of objects, because the camera is moved to the right. In summary, the OVP is the direction in which an uncovered area appears. Thus, they fill the empty points with the maximum depth value of two endpoints along the direction of OVP. After these steps they have a fully defined depth map at new viewpoint. The reasons for choosing smallest depth value for overdefined points but choosing the maximum depth value for undefined points are not explicitly mentioned and seem to contradict each other. The final step in the algorithm is texture mapping. This is easily done at points that can be observed from both primary and virtual cameras. For uncovered areas, they map a color value from one or two of the secondary images using the depth value guessed in the previous step. If none of the projection methods succeeds to fill the empty region, they interpolate the holes by weighted spreading of colors from neighboring pixels. Finally, after reconstructing the virtual view, they change the orientation and scale of the image if desired. They employ 2D geometric transformations given in [52]. Correspondence Estimation and Intermediate View Reconstruction Figure 7.2: (a) The scene is shot using n cameras. The point of interest is V . (b) Projection of 3D LOS onto input cameras. (c) The projected lines are aligned and stacked. The color consistent points are flower, tail and grass. Since flower is closest to V , color of flower is selected as the color visible from point V . An interesting work by Irani et al. proposes to reconstruct views at any point in the scene without computing any correspondence estimation [30]. In their algorithm, they first align and compare all the projections of each line of sight emerging from the virtual camera center in the input views and then the they create the virtual view. They describe the line-of-sight as the sight of the viewpoint along the line that stretches from the point to the direction desired. To better understand this method, consider the scene given in Fig. 7.2 [30] where n uncalibrated cameras are utilized. The question is how scene looks like from the eye of the person, point V . In order to extract the color information which is visible from V , the line of sight (LOS) stretching from V should be analyzed. In this example, the first physical point that LOS intersects is the flower, therefore visible from V . This 3D LOS currently analyzed creates a 2D projection on each image as shown in Fig. 7.2.b. Therefore, the idea is to find the 2D projections of a 3D LOS and to 33 Correspondence Estimation and Intermediate View Reconstruction stack them as shown in Fig. 7.2.c to create color-consistent columns. Next step is to choose the closest column to viewpoint and assign as the color visible from point V in the direction of the LOS. Although it is a bit different than view synthesis, we would like to mention the work of Seitz and Dyer [62]. Motivation of view morphing is in creating natural additional views between two images which are going to be used in transition from one image to the other when played as a video sequence. Therefore, images do not necessarily have to be the same. Due to its ability to change the viewpoint, view morphing is somehow related to view synthesis and can be used for this purpose. Another approach in intermediate view reconstruction used especially in computer vision area is to reconstruct a 3D volumetric model of the scene and then to use this model to map new virtual views. All methods we have already mentioned were 2D methods. They first relate the images with correspondence estimation and then work towards view reconstruction. Volumetric methods first create a 3D model of the scene and then manipulate and transform the object and easily create new views. However, these methods’ execution speed is dependent on scene complexity. Moreover, they require sophisticated software and hardware for a realistic result. There are also other works that use image sequences instead of calibrated multiple cameras [21]. Although they are a bit different from intermediate view reconstruction, it is going to be appropriate to mention other image-based rendering techniques. A survey by Kang [32] gives details about image-based rendering techniques. The term imagebased is used here to describe that the methods use explicit images rather than volumetric 3D models. The first category is non-physically based image mapping. One of the ideas in this method is to create an arbitrary view as a linear combination of a set of images which are considered to be basis images. This method is also utilized in entertainment industry for view morphing. Another category is mosaicing. The aim in mosaicing is to create a higher resolution or a larger image using the combination of at least two different images. An example of this work is to create panoramic image using a few images. Since intermediate views are also contained in mosaics, arbitrary view generation is also possible. In order to create the image mosaics from images, the constituent images are registered first. Many image registration techniques are used for registering. One of the main obstacle in this method is to remove the discontinuities and distortions at boundaries where images are connected [32]. The third category of methods is interpolation from dense samples. The aim here is to first build up a lookup table by many samples from a scene from many cameras and then arbitrary view is generated by interpolating the stored lookup table. The advantage of this method is that correspondence estimation step is usually not necessary. Rapid image synthesis is possible using the lookup table without the estimation step. However, the number of samples required is very large (in hundreds 34 Correspondence Estimation and Intermediate View Reconstruction and thousands). In addition, camera viewpoints should also be available. These are the main drawbacks of this method [32]. 35 Chapter 8 Conclusion and future work In this report, we first presented how humans perceive the depth and described the basic monocular and binocular depth cues used by the brain. We then described the technologies used for stereoscopic viewing and mentioned the SynthaGramTM monitor which utilizes lenticular sheets. SynthaGram monitors do not require the viewer to use special glasses and, therefore are more attractive to the audience. They can also deliver look-around feeling which is not possible in ordinary stereoscopic technologies. The geometry of 3D was described next. We related the points in real world with points in an image. Following this projection we introduced stereo cameras and elaborated on the projection of the same 3D point onto image planes. The displacement of the point between its projections, which is called disparity, was defined mathematically. Following this, we discussed the basic methods used for correspondence estimation. Block matching, although being very simple to implement, suffer from the unrealistic assumption that all the points in the same block should have the same disparity (or depth) value. Feature matching methods which can yield good results, suffer from the feature extraction part. In case of unreliable features, results will be degraded. Another problem is that these methods create sparse correspondence maps. Optical flow methods are the first methods that consider the image as a whole and try to estimate correspondence map as a function that can describe the motion. They give very promising results, however they can only describe displacements of a few pixels and therefore not suitable for most cases. Moreover, the discretization step of the continuous functions can significantly affect the results. One of the most promising emerging methods is the use of partial differential equations to estimate the correspondences. They yield very good results when compared to other methods. Next, we described the methods that create new virtual views. We mainly concentrated on 2D methods, which explicitly work on images. They first relate the images using correspondence estimation methods and then use this result for view synthesis. There are also 3D methods which first reconstruct a 3D model of the scene and then map back to 2D to create a virtual view. Correspondence Estimation and Intermediate View Reconstruction 8.1 Future work We plan to use more than two cameras to shoot the scene and then try to compute additional intermediate views. As we presented before, one of the main obstacles in correspondence estimation are occlusions. In case of occlusions, two cameras will not be enough to extract depth information. Introducing extra cameras into acquisition process may solve this problem. Following the detection of occlusions, we can ignore the information from problematic camera and use other cameras for reliable information. Another advantage of having multiple cameras is that we will have additional constraints during the computation of depth and creating intermediate views. Consider the case when there is no occlusion. Giving the emphasis to the central camera, we can compute many different depth values for the same point using the central camera and one of the additional cameras. The very important result here is that all depth values should be exactly equal since the cameras are coplanar. We may use this constraint for better estimation and reconstruction. Following the reconstruction of the depth map, we would like to fit a continuous function onto this discrete map. We can utilize one of the works [71, 70] on this topic. The advantage of fitting a continuous function is that in case of mapping to a new viewpoint, since we have a depth everywhere, no holes will exist in the new depth map. 8.2 Conclusion In this report, we have described some of the methods found in the literature for correspondence estimation and intermediate view reconstruction. We mentioned pros and cons of each method. Finally, we set our future plan. 37