Abstract:
A method of selecting first and second basis views from a group of at least three provided views where the first and second basis views are used in synthesizing a third virtual view. The group of provided views are spatially offset from one another in at least one dimension.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of provisional application 60/881,917, filed 22 Jan. 2007 and entitled Method for Supporting Intuitive View Specification In The Free Viewpoint Television Application, the entire disclosure of which is hereby incorporated by reference. 
    
    
     This application is related to copending U.S. patent application Ser. No. 11/462,327, filed 3 Aug. 2006 and entitled Virtual View Specification and Synthesis in Free Viewpoint (the &#39;327 application), the entire disclosure of which is hereby incorporated by reference. 
     BACKGROUND OF THE INVENTION 
     The present system relates to implementing Free-viewpoint Television (FTV) with minor revision to typical television (TV) infrastructure and related viewer experiences. In addition to home entertainment, FTV can be used in other environments, such as gaming and education. 
     When viewing typical TV, the viewpoint is predetermined during the production of the particular program being watched by the placement of an acquisition camera. Unlike typical TV, FTV provides the viewer the freedom of choosing his own viewpoint by supplying the viewer&#39;s television set, or other display device, with multiple video streams captured by a set of cameras, each depicting a different view of a single scene, and by using the provided ‘real’ views to create a continuum of ‘virtual’ views, as described in detail in the &#39;327 application. 
     However, the multiple video streams of a single scene may not contain explicit information about their spatial positioning relative to one another, so it is desirable for FTV to determine the relative spatial positioning of the video streams in order to select which video streams to use as the basis in creating the virtual view. Thus, the spatial positioning relationships are extrapolated from the data that is contained in the video streams. A variety of virtual view specification techniques utilize existing, image-based rendering techniques. For example, in a fully calibrated system where the relative spatial relationships between all the video streams are known the virtual view determination may be done through geometry. An alternative technique uses a viewer&#39;s manual selection of a variety of points, including the projection of the virtual camera center. Another technique determines the virtual viewpoint using a rotation matrix and a translation vector with respect to a known camera. However, these approaches require a fully calibrated system with known camera positioning or calibration input from a viewer. 
     The &#39;327 application describes a technique for specifying a virtual view between any two viewer-chosen real basis views in an uncalibrated system. This allows virtual viewpoint specification using only a single user specified parameter, thereby permitting a virtual view to be defined by indicating a one dimensional directional shift, e.g. to the left, to the right, up, or down, from a current view. One limitation of the above two view based specification is the requirement for the viewer to choose the two basis views. This selection requirement may be non-intuitive for the viewer and tends to disrupt the TV viewing experience. For example, every time the viewer begins viewing a new scene it may be necessary to first display the available basis views for that scene and prompt the viewer to select the initial basis views. Thus a more ‘user friendly’ technique for selecting the basis views is desirable. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL DRAWINGS 
         FIG. 1  illustrates an exemplary camera layout, demonstrating the difference in viewpoint between cameras. 
         FIG. 2  illustrates the geometrical relationship of two cameras arranged in a standard stereo setup. 
     
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     In a FTV application at a given point in time the viewer sees the current view, just as in a typical TV system. Unlike typical TV, the viewer may selectively “shift away” from the current view. The viewer should experience the viewpoint shift in a relatively seamless manner. From the viewer&#39;s perspective, the viewpoint shift may appear as though the acquisition camera recording the current view physically shifted in the desired direction. Although multiple real views may be provided, the number of real views may be lower than the number of potential virtual views. Thus, whenever the user pushes an arrow button on a remote control (or otherwise indicates by some manner) to shift the viewpoint, the new view may be a virtual one and this requires a virtual view synthesis. Without sufficient calibration, it is not feasible to use a distance or an angle relative to the current view to specify the new view. However, determining or using a relative spatial relationship among the basis views permits using the single-parameter-based technique described in the &#39;327 application to specify the virtual view. 
     Referring to  FIG. 1 , if the current viewpoint is real view b, and it is known that the nearest real view to the relative right of view b is view c, then when the viewer pushes a right-arrow button, the technique described in the &#39;327 application may be used to parameterize a virtual view b′ based on view b (left) and view c (right). For purposes of illustration in the foregoing description only the horizontal relationship between the views is described. The vertical relationship is done in a similar fashion. Once the two appropriate basis views are determined, then the technique described in the &#39;327 application is applicable. However, the appropriate basis views are first selected without the assistance of the viewer. 
     In a preferred embodiment of the technique one of the basis views is defined by the current view (view cur ) on display at the time the viewer indicates a desire to shift away from that view. If view cur  is a real view, then view cur  will itself be used as a basis view. If view cur  is a synthesized virtual view then one of the basis views used to synthesize view cur  is known and this view may be used as one of the basis views for the new virtual view. Since there may be multiple views to either side of view cur , the preferred technique identifies the one that is closest. For example, again referring to  FIG. 1 , if view cur  is real view b and the viewer indicates a desire to shift the viewpoint to the right, then view b should be one of the two basis views. What should be determined is whether view a or view c is preferably the second of the two basis views. 
     A preferred embodiment of the present technique utilizes two techniques for making a determination of which view should be used, each using a different assumption. The first technique estimates the pair-wise left-right relations of two images. The second technique estimates a closeness measure among multiple views. Although the two techniques share some common elements, including the use of conventional feature point detection and correspondence techniques, the estimation of a fundamental matrix, and comparable computational costs, they are fundamentally different as they rely on different assumptions. 
     The main assumption of the first technique of pair-wise left-right relations is that a camera&#39;s intrinsic matrix can be estimated by a relatively simple and conventional technique, described below. This, in turn requires that the acquisition process be typical, e.g., without asymmetric cropping of the images, uses a known or reasonable range of zoom factors, etc. If the assumption is satisfied, this technique is relatively straightforward to use because it directly provides the necessary translation vector between two views. The main assumption of the second technique of the closeness factor is that a feature correspondence algorithm will be able to detect more background feature points than foreground ones. Scenes with relatively small foreground objects on a relatively far background, for example two people standing on a street, naturally satisfy this assumption. On the other hand, scenes with a close shot of an object, for example a close shot of a bouquet, violate this assumption. 
     In the first preferred technique, the fundamental matrix F of the known basis view and one of the potential basis views is estimated. This may preferably be done using known feature correspondence techniques. For example, the random sample consensus (RANSAC) algorithm could be used in conjunction with a Harris Corner Detector to estimate the fundamental matrix. A single intrinsic matrix K for the cameras may also be estimated. This may preferably be done by assuming the principal points are located at the center of the image and setting the focal length f as equal to the image width w multiplied by the zoom factor x (which is set to 1 if unknown). This initial estimate of K may be further refined by a conventional approach based on the reprojection errors in the feature points. Thus: 
     
       
         
           
             
               K 
               = 
               
                 [ 
                 
                   
                     
                       f 
                     
                     
                       0 
                     
                     
                       
                         p 
                         x 
                       
                     
                   
                   
                     
                       0 
                     
                     
                       f 
                     
                     
                       
                         p 
                         y 
                       
                     
                   
                   
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                   
                 
                 ] 
               
             
             , 
             
               
                 
                   
                     
                       p 
                       x 
                     
                     = 
                     
                       w 
                       / 
                       2 
                     
                   
                 
               
               
                 
                   
                     
                       p 
                       y 
                     
                     = 
                     
                       h 
                       / 
                       2 
                     
                   
                 
               
             
           
         
       
     
     The essential matrix E of the cameras may now be computed using the estimated fundamental matrix F and intrinsic matrix K:
 
E=K −1 FK
 
     Applying single value decomposition techniques to the essential matrix E yields the rotation and translation matrices for the two views. There are 6 parameters recovered from this process, 3 for the rotation matrix and 3 for the translation matrix, represented by R x , R, y  R z , t x , t y  and t z . The relative left-right relationship of the two views can be determined by examining t x , if t x &gt;0 then view  1  is on the right; otherwise, it is on the left. This technique is advantageous because the value of t x  can be used to further sort multiple views. For example, if view a and view b are both on the left of view c, the magnitude of t x  will determine which one is closer to view c. 
     However, this technique works well only as long as the estimates for the fundamental and intrinsic matrices are accurate. The accuracy of the estimation is dependent on the strength of the feature correspondence algorithm. Practically speaking, using the image center to approximate the principal point of a camera is a good estimate, unless, for instance, the image is cropped significantly and largely asymmetrical. Also, because the distance between the two cameras under consideration may be reasonably large, small errors in the principal points will not significantly affect the estimated translation matrix. 
     The second preferred technique relies on computing the average and median disparity values (defined as the average of the maximum and the minimum disparities). Although a fully calibrated system cannot be assumed, it is helpful to describe how the view disparities can be used to determine pair-wise left-right relationship of two views in such a system, such as a standard stereo setup. By definition, in a standard stereo setup all disparities between the views are horizontal and the magnitude of the disparity for a given point is a function of the point&#39;s depth in the field of view, with the magnitude approaching zero as the depth approaches infinity. 
       FIG. 2  illustrates two views, d and e, positioned in a standard stereo setup. For a given point m in the scene each camera views a respective matching point m d , m e  at respective coordinates x d,m , y d,m  and x e,m , y e,m . Because of the standard stereo setup, y d,m  will equal y e,m  but there will be a horizontal disparity: d m =x e,m −x d,m . Because view d is on the left of view e, the disparity for all points in these two views will be greater than zero. This is true regardless of the location of the point m in the field of view. Conversely, if view d were on the right of view e, the disparity would be less than zero. 
     Yet a practical embodiment should account for all the available views being in general positions, not a standard stereo setup. It is feasible, given some assumptions, to use known techniques to rectify two uncalibrated views to create an approximation of a fully calibrated standard stereo setup. 
     A preferred technique for selecting an appropriate basis view using image rectification begins, as did the technique described above, with estimating the fundamental matrix F of the two images. Using the fundamental matrix F, the two images may be rectified such that all epipolar lines become horizontal and aligned. For a description of such a rectification technique, see J. Zhou and B. Li, “Image Rectification for Stereoscopic Visualization Without 3D Glasses,” International Conference on Content-Based Image and Video Retrieval, 2006. 
     The feature points may then be transformed to the rectified image coordinate system and disparities for the feature points may be calculated. In the rectified image coordinate system, all disparities will be one dimensional (e.g. horizontal, with zero vertical disparity). After rectification however, the horizontal distance between the two image planes is still unknown. This is equivalent to adding an unknown constant to all the image disparities. This consequently introduces some ambiguity in determining relative camera position because, for example, the addition of the constant may cause there to be both positive and negative disparities. 
     To resolve the ambiguity, the technique assumes more feature points were detected in the background than the foreground. Given a disparity set D={d i }, i=1, . . . , n, the average disparity is defined as 
     
       
         
           
             
               Avg 
               ⁢ 
               
                   
               
               ⁢ 
               
                 ( 
                 D 
                 ) 
               
             
             = 
             
               
                 1 
                 n 
               
               ⁢ 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                 ⁢ 
                 
                   d 
                   i 
                 
               
             
           
         
       
     
     and the median disparity as 
     
       
         
           
             
               Median 
               ⁢ 
               
                   
               
               ⁢ 
               
                 ( 
                 D 
                 ) 
               
             
             = 
             
               
                 
                   Max 
                   ⁡ 
                   
                     ( 
                     
                       d 
                       i 
                     
                     ) 
                   
                 
                 + 
                 
                   Min 
                   ⁡ 
                   
                     ( 
                     
                       d 
                       i 
                     
                     ) 
                   
                 
               
               2 
             
           
         
       
     
     If there are more background points than foreground points, it follows the average depth of those points is closer to the background and the average disparity will be closer to the minimum disparity than the maximum and, consequently, the average disparity will be less than the median disparity. This relationship is not influenced by the shifting of disparities due to the rectification ambiguity. Therefore, if the average disparity is less than the median disparity, then first image is on the left, otherwise it is on the right. 
     The terms and expressions which have been employed in the foregoing specification are used therein as terms of description and not of limitation, and there is no intention in the use of such terms and expressions of excluding equivalents of the features shown and described or portions thereof, it being recognized that the scope of the invention is defined and limited only by the claims which follow.