Correspondence Estimation and Intermediate View Reconstruction Chapters 1-4

CORRESPONDENCE ESTIMATION AND INTERMEDIATE VIEW RECONSTRUCTION Chapter 1 Introduction Visual aids are vital parts of our lives. One could not imagine a life without photographs or videos. Therefore, image processing is a huge scientific area where thousands of researchers are actively working. Although many of these researchers concentrate on two-dimensional (2D) image processing, there are many researchers in three dimensional (3D) vision research area as well. As a result of their work, in the future, we will be using more three dimensional visual aids than we use today. Nowadays, 3D devices that ordinary people are exposed to are limited to specially equipped movie theaters that require the audience to wear special kind of glasses. However, in the future, TVs that give us depth feeling without a need of any eyewear will be common in our homes. It is actually very interesting that works on three dimensional images had begun long before photography was invented. It is noted that Leonardo da Vinci (14521519) studied the perception of depth [2]. His interest and appreciation for the third dimension can be found in his notes written 500 years ago. He writes ”...the main objective of painting is to show a raised body projecting from a plane surface. Whoever achieves this surpasses all others and should be considered most skilled within his profession.” [1]. However, the breakthrough happened in 1838 when physicist Charles Wheatstone (1802-1875) invented the first stereoscopic viewer. Wheatstone, a British scientist, explained the theory of stereoscopic vision in his address entitled ”Phenomena of Binocular Vision” to the Royal Scottish Society of Arts in June 1838. The original speech can be found on the internet [6]. He constructed the stereoscopic device on the knowledge that left and right eyes view the same scene with a slightly different angle. This knowledge constructs the basics for stereoscopy. After the invention of photography, Wheatstone also introduced the first photographic stereoscope in 1841. Following Wheatstone, David Brewster (1781-1868) made significant contributions to the stereoscopic field. In 1849, he proposed his own stereoscope consisting of a pair of half lenses and an opening to a slot where the pair of images can be mounted side by side [8]. The new design was more compact than that of Wheatstone’s. One year later he succeeded in interesting the French optics company Soleil and Duboscq and the Correspondence Estimation and Intermediate View Reconstruction Figure 1.1: Wheatstone used hand drawings to demonstrate the function of his stereoscopic device company started manufacturing the device [3].The company exhibited the stereoscope in an exhibit in London. Queen Victoria was very impressed by the device. Having caught the attention of the noble, it also drew the public’s attention. As the result, within a three months period, a quarter of a million stereoscopes were sold in London and Paris. Since the first stereoscopic device, many new techniques were introduced for stereoscopic displays. In this report, we will cover these technologies and we will mainly focus on stereovision related research topics. Specifically, the report will start with the discussion of how humans perceive depth which will be followed by technologies used for stereoscopy. Also, applications of stereoscopy will be presented in this chapter. Next, we will define correspondence estimation and intermediate view reconstruction (IVR). Applications of IVR and then correspondence estimation techniques along with comparisons will be presented. Next, IVR techniques will be discussed. The report will conclude with a work plan and conclusions. 2 Correspondence Estimation and Intermediate View Reconstruction 1.1 Definition of problem The problem to be investigated is to create high-quality intermediate views using a number of cameras. For this purpose a number of techniques will be introduced to solve the following problems: • Reliable estimation of depth using multiple cameras • Transformation of the resulting depth maps to virtual viewpoints • Reconstruction of virtual view at the new viewpoint Following this phase, transmission of multiple views to users will be the main topic. The problems in this phase are: • Evaluation of (a) transmission of all multiple views (b) transmission of a minimum number of views which are going to be used at the receiver end to create the extra views. • If method (a) is preferred, compression techniques to reduce the redundancy should be investigated. • If method (b) is preferred, optimization of IVR methods should be investigated. 1.2 Goals A prototype system which renders required number of high-quality views from minimum number of cameras and then compresses them for fast transmission will be completed at the end of the project. Solutions to each problem mentioned in the previous section will act as milestones in the project. 3 Chapter 2 Perception of depth How humans perceive depth is covered in this chapter. Monocular and binocular depth cues are introduced. 2.1 How do we perceive depth? Depth is the relative distance of objects to the observer within a scene. Perception of depth is achieved by coordination of our eyes and brain. Human brain uses the depth cues, which can be defined as clues that help observer to find out the depth. There are several types of depth cues that are used by human brain. They are mainly divided into two groups as monocular and binocular depth cues. 2.1.1 Monocular depth cues Monocular depth cues don’t require the use of two eyes and as the name implies, they can be viewed with one eye. One of the basic monocular depth cues is light and shade [38]. Artists often use this cue in their works. Shadows give an idea about the shape of objects and help us to estimate the relative positions of points. Fig. 2.1 [38] shows this effect. Another monocular depth cue is interposition. If an object is blocking the view of another object, then it is obvious that it is the closer to the viewer. For example, the gray square in Fig. 2.2 is closer to the viewer than the black one. Yet another monocular depth cue is relative size. We know that objects that appear larger are closer to us. Therefore, if two objects are known to have the same size and if one of them is relatively bigger than the other, then we know that the bigger one is closer to us. The house on the left in Fig. 2.3 is closer to the viewer. Aerial perspective is defined as the blurring of distant objects in the scene because of the haze and scattering of light in the atmosphere. The objects in Fig. 2.4 are same sized but the blurry one seems to be more distant to the viewer. Textual gradient is another monocular depth cue [38] which is defined as gradual change in appearance of objects from coarse to fine. The objects that appear more Correspondence Estimation and Intermediate View Reconstruction Figure 2.1: Shadows provide depth a cue Figure 2.2: Interposition of objects provides a depth cue distinct appear closer. Fig. 2.5 shows this effect. The lines in the lower side of the figure appear closer because of the textual gradient. Motion parallax [38] depth cue can be noticed in case of continuous movement of objects. If two objects are known to have the same speed, the closer object appears to be moving faster than the distant object. This effect can be easily noticed when travelling in a car. As the car moves, hills in the landscape move very slowly, while the traffic signs on the road pass by very quickly. Objects appear to be getting smaller as they get further away from the viewer. This effect is called geometric perspective [25]. Consider the example in Fig. 2.6. Point B seems to be closer than point A. 5 Correspondence Estimation and Intermediate View Reconstruction Figure 2.3: Relative sizes of objects provides a depth cue Figure 2.4: Blurriness of objects provides a depth cue Figure 2.5: Textual gradient provides a depth cue 6 Correspondence Estimation and Intermediate View Reconstruction Figure 2.6: Geometric perspective provides a depth cue 2.1.2 Binocular depth cues Unlike monocular ones, binocular depth cues are perceived by two eyes. Human eyes are positioned at slightly different locations. The average interocular distance for humans is approximately 2.6 inches (6.5 cm) [27]. Due to this distance between eyes, the projections of the scene onto retinas of eyes are slightly different. The brain fuses these two slightly different images to give depth feeling. Fig. 2.71 shows the projection of a scene onto two cameras placed at interocular distance. If examined closely, one can notice the differences. For example, the farthest car that is in front of the bushes is more visible in the left image, while most parts of the car are occluded in the right image. Other differences can be noticed especially at object boundaries. It is also easy to notice that positions of objects are slightly different in the two images. In order to understand this effect, consider this easy experiment: While looking at a stationary scene, close and open one eye at a time. It is easy to notice the differences. Ignoring occlusions, a topic which will be covered later, all points in the left image are also present in the right image with a displacement due to the projection of scene. This displacement of a point in two images is called disparity. The disparity is larger for objects closer to the viewer2 . One can do the previous experiment to observe this fact, too. Put your thumb nearly 10 cm far away from your eyes. While looking at a distant object open and close one of your eyes. It is easy to notice that your thumb ’moves’ quite a bit, while the distant object ’moves’ little. Using this basic information and camera geometry, the depth of each pixel in the scene can be constructed using stereo images. Depth value for each pixel can be 1 Used with permission of www.stereovision.net It should be noted that we are considering parallel camera configuration here. In case of toed-in configuration, this statement may be invalid. Camera configurations are covered in Chapter 5. 2 7 Correspondence Estimation and Intermediate View Reconstruction Figure 2.7: Image on the left shows the scene through left camera and image on the right shows it through right camera regarded as a new image, which is called the depth (or range) map. 8 Chapter 3 Intermediate view reconstruction One of the main problems of stereoscopic systems is that they don’t offer the freedom of choosing the viewpoint. The observer should watch the scene at the position of cameras. When watching a stereoscopic image/video, if the viewer moves the scene stays the same, which is not realistic. In real life, if one moves his head, he can see around the objects. This is called look-around feeling which stereoscopic systems cannot deliver [25]. Figure 3.1: Intermediate view reconstruction The solution to this problem is shooting the same scene at many different viewpoints and showing two of the views at a time to the user as he moves his head. Without any novel approach, using many cameras for recording the scene seems to be the easiest way. However, this kind of setup will be not only very expensive but also very bulky. Instead, we can use special techniques to create views at virtual viewpoints using a small number of real cameras. Creating virtual views using stereoscopic images is called intermediate view reconstruction 1 . In Fig. 3.1 we show such a setup. The scene is recorded using two cameras, the question is what the scene would look like from the position of the virtual camera. We will return to intermediate view reconstruction later. 1 also called view synthesis Correspondence Estimation and Intermediate View Reconstruction 3.1 Distinction of terms Since many terms such as stereoscopic, stereographic and 3D are used in literature, it is appropriate to begin by making distinction between them. A stereographic image is a single image which contains meaningful and correct monocular depth cues. Therefore all the images that are captured using a camera are stereographic images [25]. Two stereographic images, one for left eye and one for right eye are called stereoscopic images or stereo-pair. If these images are properly delivered to viewever’s eyes, he/she will perceive the depth of the scene. The viewpoint2 in stereoscopic images is fixed. The viewer sees through the viewpoint of the cameras. There is no freedom of choosing a viewpoint. The systems that let the users to determine the viewpoint for the scenes are called 3D systems [25]. 2 Here, we use the term viewpoint to describe the position of cameras. 10 Chapter 4 Stereoscopic display technologies This chapter elaborates the benefits of stereoscopic display systems and technologies. In this chapter, we will discuss these technologies, with the emphasis on autostereoscopic displays. 4.1 Benefits and applications of stereoscopic display technologies The first application area of stereoscopic vision is entertainment. Adding the third dimension to the current technology will add realism and will be more pleasing to audiences. IMAX TM movie theaters are well-known among people for such an experience. Overcoming hardware and software problems, stereoscopic TVs can replace ordinary TVs in the future. Businesses will benefit from stereoscopic displays, too. Companies can demonstrate their products in life-size using 3D displays. A customer in another country can examine the product without visiting the company or waiting for a sample. Similarly, virtual visits of homes, vacation sites can be made possible [34]. Stereoscopic vision can also be used in remote handling applications that are potentially hazardous to humans. Examples are underground works and radioactively contaminated areas. The field of medicine can use stereoscopy for surgeries. All kind of simulators can be improved using stereoscopy. The trainee will be more aware of the situation with the enhanced display. 4.2 Current technology Color-multiplexed (Anaglyph) displays: First anaglyphs were invented by Rollman in 1853. Although this technology is very old, it is still used due to its simplicity and little cost. Anaglyph glasses have a red lens on left eye and a blue (sometimes cyan) lens on right eye. Anaglyph stereo images are produced in such a way that two images, a red Correspondence Estimation and Intermediate View Reconstruction and blue image, are superimposed, one on top of the other. Since anaglyph glasses have colored lenses, left and right eyes see the red and blue images respectively. Since two different images are perceived by each eye, viewer can perceive the depth. Crosstalk, which is defined as each eye seeing some part of the image of the other eye, is too high in this method. Also color rivalry, where homologous points are presented with non-matching colors, restricts the use of this method [55]. Many examples of anaglyph works and displays can be found on the internet. Polarization-multiplexed displays: In this method, two views are projected through light polarizers onto the screen. These superimposed images are then separated by polarized (circular or linear) glasses worn by the user. The advantages of this method are little crosstalk and inexpensive and lightweight polarizing glasses [55]. An example polarized display product NuVision 17SXTM can be found at [4]. Time-multiplexed displays: This technique exploits the fact that human visual system can retain an image for some time. The left and right views are sequentially shown on the screen and lenses of the liquid crystal shutter glasses open and close in synchronization with the displayed images. When the left view is on the display, right lens occludes the right eye and vice versa. The operation of glasses is controlled by a infrared emitter placed close on the monitor. When the observer turns away from the screen, shutter glasses stop working and both lenses switch to open, so the viewer is not affected during normal viewing. Persistence of phosphors of CRT monitors may result in some crosstalk in this method [55]. An example product, CrystalEyes 3TM can be found at [7]. Autostereoscopic displays: While the techniques above require eyewear, autostereoscopic displays don’t require eyewear. In this method, views are spatially multiplexed on a pixel-addressable screen and then separated using an optical layer that covers the display [34]. One example for the optical layer is lenticular sheet. SynthaGramTM 3D monitor, a product of StereoGraphics Corp., uses lenticular sheets for 3D viewing. This specific monitor is discussed in detail in the next section. More information on 3D display technologies can be found in [55]. 4.3 SynthaGram 3-D display The SynthaGramTM is an autostereoscopic monitor manufactured by StereoGraphics Corp. Most important features of SynthaGram are its capability to deliver 3D view without the need of eyewear and its capability to give look-around feeling. SynthaGramTM monitors use lenticular sheet (sometimes called lens sheet or micro lens) which can be regarded as many miniature lenses arrayed on a flat sheet. This sheet covers the surface of a flat panel monitor. The screen and lenticular sheet are precisely aligned using Moir Interferometry1 . The mapping of pixels on the monitor is predefined, a process called interzigging by StereoGraphics Corp. 1 Moir Interferometry is an optical technique that uses lasers to measure displacements and strains on the surface of objects. Moir gives a full-field map of the strains. It has subwavelength displacement sensitivity[5]. 12 Correspondence Estimation and Intermediate View Reconstruction Figure 4.1: Lenticular sheet The main idea of using lenticular sheet is summarized in Fig. 4.1. The basic principle of delivering different images to each eye is achieved using optical lenses of the lenticular sheet. One can think of this configuration as of eyewear, that the user should wear, is carried on the monitor itself. As already mentioned, the SynthaGramTM is capable of giving look-around feeling. This is achieved by creating a number of view zones using nine images. These nine images of the scene should be taken by evenly spaced cameras. Since there are many images shown on the monitor, the user will be able to see different perspectives as he moves his head. To sum up, in a single view zone, user can experience a lookaround feeling. If the user enters another view zone, same perspective progression is repeated. There are five view zones which are created using nine images. Using nine images wass selected after experiments of developers. Although nine images are required in order to have the best quality, fewer images can be used, but results will be degraded, since there will be distinct jumps between perspectives. It should also be noted that another advantage of having multiple view zones is that multiple users can see the same 3-D image effortlessly. Since there are nine images for the display, there are nine times more pixels than in a single image, therefore they should be processed before displayed on the monitor. This processing is called interzigging. The first step of interzigging is downsampling of images to reduce the number of pixels. Since there are nine images, downsampling by three in both x and y directions is appropriate. It should also be noted that this downsampling process obviously decreases the image quality, which is a drawback of the SynthaGramTM . Proper prefiltering stage needs to be applied to prevent aliasing. Special anti-aliasing filters for SynthaGramTM monitors are discussed in [35] . The next step is choosing the correct pixel from the source image and assigning it to its new location in the interzigged image. In an early version of such displays manufactured by Phillips, the following formula is used to choose pixels and assign them on the monitor [67]. 13 Correspondence Estimation and Intermediate View Reconstruction N= (k + kof f set − 3 l tan α) mod X Ntot X 14 (4.1) where k,l : pixel location N-tot : total number of views α: angle of slanted lenticular X: view per lens kof f set : a variable to accommodate horizontal shift of the lenticular lens array (usually zero) Figure 4.2: Nine-tile format After the interzigging operation there will be a single image to view on the SynthaGramTM with the same dimensions as the original images. However, a problem arises after interzigging. Since the new image is a ’shuffled’ image, compression significantly degrades the quality due to blocking artifacts. Blocking artifact is a problem in block based-lossy compression standards, e.g., JPEG. Due to the quantization step in compression algorithms, it is easy to see the boundary changes between blocks at high quantization levels. Although this blocking effect can be tolerated to some level in ordinary images, it results an unpleasant experience on SynthaGramTM monitors, because blocking artifact causes texture and depth distortion. In order to overcome the compression and transmission difficulty, developers introduced the nine-tile format, which is basically downsampling the images by three in each direction and concatenating them to create a single image with the same size of Correspondence Estimation and Intermediate View Reconstruction the original images. The images should be properly prefiltered before downsampling to avoid aliasing. Another reason for the nine-tile format is that for different monitor resolutions different interzigging algorithms are required. Therefore original images are required to create an interzigged image for a different monitor. Thus it is an appropriate way to store the images. 15