Abstract:
There is provided a method and apparatus for processing images to create a novel view of a scene. The method comprises the steps of: (a) providing first and second images of a scene; (b) applying a stereo matching algorithm to the first and second images to generate a first disparity map which maps between corresponding points from the first image to the second image; (c) forward mapping the first disparity map into the coordinates of a third image to generate a second disparity map; (d) using the second disparity map, reverse mapping for at least some of the pixel positions in the third image to corresponding points in the first and second images to obtain possible colour values for each of the at least some of the pixels in the third image; and (e) assigning a final colour value to each of the at least some of the pixels in the third image on the basis of the possible colour values, thereby providing a novel view of the scene.

Description:
[0001]     The present invention relates to a method of processing images and in particular to processing first and second images of a scene to provide a third image of that scene from a different viewpoint.  
       BACKGROUND  
       [0002]     In the field of computer imaging, it is often desirable to be able to produce a view of a scene from a viewpoint other than those already available. An application of such a technique is in content generation for stereoscopic displays. In a stereoscopic display, two slightly different images of the same scene are supplied to a user, one image being supplied to each eye, the perception of the user being that of a three-dimensional scene. It may be the case that the depth range provided by the two images is too great for comfortable viewing on a given three-dimensional display, in which case it is desirable to vary the depth range in the stereogram. No explicit three-dimensional information about the scene may be available, and a method of providing a new image of the scene on the basis of existing images only would allow the creation of a new stereogram which would be more comfortable for the user to view.  
         [0003]     Several existing view synthesis techniques are known. Chen and Williams, View Interpolation for Image Synthesis, Proc, ACM SIGGRAPH 1993, pages 279-288 and Chen and Williams, Three-Dimensional Image Synthesis using View Interpolation, U.S. Pat. No. 5,613,048 describe how a three-dimensional scene can be represented by a collection of two dimensional images. It is assumed that a number of “correspondence maps” are available. These maps define the position in each two-dimensional image of a given feature as the viewpoint changes. It is suggested that the maps could be obtained by manually labelling features in the source images or by reference to a geometric model of the scene. The changes in position of a given feature define the binocular disparities of the points in the scene.  
         [0004]     To produce a novel view of the scene, pixels from the source images are “forward mapped” into a new image in accordance with the correspondence maps. If multiple features are mapped to the same target position in the novel view, the feature that is “in front” is chosen. This technique can reduce the amount of storage space and rendering time required without necessarily compromising the quality of the novel view. There is, however, no guarantee that the novel view will be complete: there may be regions in the novel view which were not populated with colour values in the forward mapping process. It is suggested that the novel view should initially be filled with a distinctive colour which is subsequently overwritten by the forward-mapped pixel values. Any gaps in the novel view can therefore be easily identified. The gaps are then filled by interpolation from the surrounding pixel colours or interpolation of the surrounding correspondence map information with reference back to the source images. Neither of these techniques produces an accurate representation. Interpolation of the surrounding pixel colours can only produce a smooth transition between the nearby pixels, resulting in a poor approximation to any image structure that ought to appear in the missing region. The novel view will therefore appear blurred, and this problem will increase with the size of the region from which information is missing. Simple interpolation of the correspondence map data in the neighbourhood of the gap is not usually appropriate, as it does not account for depth-discontinuities.  
         [0005]     A theoretical analysis of view interpolation is given in Seitz and Dyer, View Morphing, Proc, ACM SIGGRAPH 1996, pages 21-30, which improves upon the method of Chen and Williams as applied to real images. Again, correspondence maps are obtained defining the image position of a given feature. A stereo matching algorithm can be applied to pairs of images to generate the correspondence map. To render a novel view, Seitz and Dyer use the same forward mapping procedure as Chen and Williams. Colour information from both source images is blended to produce pixel values in the novel view. Gaps in the novel view are filled by interpolating between the nearby pixels.  
         [0006]     The method of Seitz and Dyer is illustrated in the flow diagrams of  FIG. 1   a  and  FIG. 1   b .  FIG. 1   a  illustrates the geometric processing which is undertaken. Positions (i, j L ) and (i, j R ) of points in the original images I L  and I R  are matched by matching algorithm M to produce disparity maps D L  and D R . The matches are obtained by searching for similar image features so that I L  (i, j L ) and I R  (i, j R ) are approximately equal since they represent the same feature of the scene. Alternatively, this may be considered as a position (i, j L ) in I L  having a corresponding point in I R  at (i, j R )=(i, i L −D L  (i, j L )). Likewise, the point (i, j R ) in I R  has a corresponding point in I L  at (i, j L )=(i, j R +D R  (i, j R )). The row index i is the same in the two images since the images are assumed to be rectified, that is, common features are expected to be related by horizontal translations only.  
         [0007]      FIG. 1   b  illustrates the colour processing of the image. Colours from the original images I L  and I R  are forward mapped into the coordinates j L ′ and j R ′ of two novel images I L ′ and I R ′. In each case, the final colour is obtained by a blending operation B. The blending operation produces a colour value in the novel images I L ′ and I R ′ for each of the corresponding image features.  
         [0008]      FIG. 2  illustrates the positions of the cameras associated with the original images I L  and I R . The positions of the novel views I L ′ and I R ′between the positions of the two original images may be defined using a parameter t whose value varies between 0 and 1 between the positions of the original images. For the synthesis of stereoscopic image pairs, two such parameters are required: t L  and t R  for novel views I L ′ and I R ′, respectively.  
         [0009]     The process illustrated in  FIG. 1   b  can be understood by following the route of a particular pixel. For example, starting from the top left box of  FIG. 1   b , a colour from image I L  at position j L  is selected. The disparity map D L  is used to map this colour to two new positions. The first new position lies in image I L ′ at position j L ′=μL−t L  D L  (j L ). The second new position is in image I R ′ at position j R ′=j L −t R  D L  (j L ). Similarly, a colour from image I R  at position j R  is mapped to positions j L ′=j R +(1−t L ) D R  (j R ) in I L ′ and to j R ′=j R +(1−t R ) D R  (j R ) in image I R ′ using disparity map DR. This gives a pair of colours at each position in I L ′ and I R ′ which are blended as indicated.  
         [0010]     U.S. Pat. No. 6,215,496 describes a modified “sprite” representation in which ordinary sprites can be used to render relatively flat or distant parts of a scene. Only one input image is used, taken in conjunction with an associated depth map. The depth information is forward mapped to the output position and the colour is reverse mapped to the single input image. This representation can be improved by allowing each pixel to be independently offset from the sprite mapping. The offsets are determined by the scene depth of the points in relation to the surface that is being warped. It is assumed that the offsets can be obtained from an existing model of the surface, or computed by a correspondence algorithm. The method of U.S. Pat. No. 6,215,496 is illustrated in  FIGS. 3   a  and  3   b  which show the geometric and colour processing, respectively. The original images, I L  and I R  are matched as above. The disparities are then forward mapped giving new disparity maps D L ′ and D R ′ in the coordinates of the new images. Specifically, a disparity D L  (j L ) is mapped to position j L ′=j L −t L  D L  (j L ) in new disparity map D L ′ and similarly a disparity D R  (j R ) is mapped to position j R ′=j R +(1−t R ) D R  (j R ) in new disparity map D R ′.  
         [0011]     The colour processing shown in  FIG. 3   b  starts from a position in one of the novel views, using the corresponding disparity map to look up a colour in one of the source images. This colour is then rendered in the novel view. For example, position j L ′ in image I L ′ corresponds to disparity D L ′(j L ′). This means that j L ′ can be mapped to position j L =j L ′+t L  D L ′(j L ′) in image I L . The colour I L  (j L ) can then be rendered to position j L ′ in image I L ′.  
         [0012]     The method of Chen and Williams is designed to work with computer-generated images. The method of Seitz and Dyer uses forward mapping. The method of the above-mentioned US patent is designed to produce novel views of flat or distant parts of a scene based on a single source image. It is desired to be able to provide a method of generating novel views of a scene. Particularly, it is desired to provide a method which can be used to vary the depth range in a stereogram when no explicit three-dimensional information about the scene is available.  
         [0013]     U.S. Pat. No. 5,917,937 discloses a stereo matching algorithm for determining disparities, colours and opacities from multiple input images. This algorithm generates a general disparity space and makes estimates of colours and opacities in the disparity space by forward mapping the source images into the disparity space. Statistical methods are used to refine the estimates.  
       SUMMARY  
       [0014]     According to a first aspect of the invention, there is provided a method of processing images comprising the steps of: 
    (a) providing first and second images of a scene;     (b) applying a stereo matching algorithm to the first and second images to generate a first disparity map which maps between corresponding points from the first image to the second image;     (c) forward mapping the first disparity map into the coordinates of a third image to generate a second disparity map;     (d) using the second disparity map, reverse mapping for each pixel position in the third image to corresponding points in the first and second images to obtain possible colour values for each pixel in the third image; and     (e) assigning a final colour value to each of the at least some of the pixels in the third image on the basis of the possible colour values, thereby providing a novel view of the scene.    
 
         [0020]     The first and second images may have been rectified so that they are related by horizontal offsets only.  
         [0021]     The position of the third image may be chosen by a user. The position of the third image may lie between the positions of the first and second images.  
         [0022]     Step (c) may comprise forward mapping the first disparity map such that each entry in the second disparity map identifies a unique position in each of the first and second images. Step (c) may comprise adjusting the forward mapping such that gaps in the second disparity map are filled. The gaps in the pixel positions of the third image may be filled on the basis of the values of the second disparity map at each end of each gap.  
         [0023]     The colour values obtained from the first and second images corresponding to each pixel position in the third image in step (d) may be obtained by interpolation between neighbouring pixels in each of the first and second images. Interpolation may be one of linear and cubic approximation.  
         [0024]     Step (e) may comprise blending the possible colour values to provide the colour value. The blending may be performed in accordance with the proximity of the location of the third image with respect to the locations of the first and second images. The colour blending may be weighted such that the closer of the first and second images to the third image has a greater influence on the colour of the pixel in the third image.  
         [0025]     The final colour value may be one of the possible colour values.  
         [0026]     The stereo matching algorithm of step (b) may comprise enforcing a monotonicity constraint to produce a single disparity map.  
         [0027]     The method may comprise the further steps of repeating step (b) with the first and second images exchanged, thereby generating a different first disparity map which maps between corresponding points from the second image to the first image; and repeating step (c) for the different first disparity map to generate a different second disparity map; wherein step (d) is performed for each of the two second disparity maps to obtain the possible colour values.  
         [0028]     The two second disparity maps may be merged in the coordinates of the third image prior to steps (d) and (e). The method may comprise the further step of comparing the two first disparity maps and deleting any inconsistent entries, thereby providing a single first disparity map.  
         [0029]     The method may comprise the further step of repeating steps (c) to (e) for a different third image position, thereby producing two third images together forming a novel stereo pair view of the scene.  
         [0030]     In accordance with a second aspect of the invention, there is provided an apparatus for processing images comprising: image acquisition means for providing first and second images of a scene; means for applying a stereo matching algorithm to the first and second images to generate a first disparity map which maps between corresponding points from the first image to the second image; means for forward mapping the first disparity map into the coordinates of a third image to generate a second disparity map; means for using the second disparity map to perform a reverse mapping for at least some of the pixel positions in the third image to corresponding points in the first and second images to obtain possible colour values for each of the at least some of the pixels in the third image; and means for assigning a final colour value to each of the at least some of the pixels in the third image on the basis of the possible colour values, thereby providing a novel view of the scene.  
         [0031]     In accordance with a further aspect of the invention, there is provided a program for controlling a computer to perform the method and the first aspect of the invention.  
         [0032]     The program may be stored in a storage medium. The program may be transmitted across a communications network.  
         [0033]     In accordance with a still further aspect of the invention, there is provided a computer programmed to perform the method of the first aspect of the invention. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0034]      FIGS. 1   a  and  1   b  are flow diagrams illustrating a prior art method of synthesising a novel view of a scene;  FIG. 2  illustrates two cameras obtaining two different views of a scene;  FIGS. 3   a  and  3   b  are flow diagrams illustrating a further prior art method of synthesising a novel view of a scene;  
         [0035]      FIG. 4  illustrates an embodiment of the present invention;  
         [0036]      FIG. 5  illustrates the creation of a disparity map in accordance with an embodiment of the present invention;  
         [0037]      FIGS. 6   a  and  6   b  are flow diagrams illustrating a method of synthesising a novel view of a scene in accordance with an embodiment of the present invention;  
         [0038]      FIGS. 7 and 8  are plan views of the scene of  FIG. 2 ;  
         [0039]      FIGS. 9-11  illustrate the steps of forward and reverse mapping in accordance with an embodiment of the present invention; and  
         [0040]      FIG. 12  is a schematic diagram of a computer in accordance with an embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0041]     The embodiments described hereinbelow define a method for synthesising new images from two given views of a scene. Partially occluded and ambiguous regions of each novel view are rendered appropriately. Additionally, colour information from both input images is used to determine the pixel values in each novel view. An embodiment of the present invention is illustrated in  FIG. 4 . Cameras  1  and  2  are used to obtain input images I L  and I R , respectively. These images are transferred to a computer  4 . The user may specify an intermediate viewpoint at a position t, via the input device  6 . The input device may be, for example, a keyboard or a mouse. The computer processes the inputs as described below and produces an intermediate view I′. The output image appears on a display  5  attached to the computer. The intermediate position at which the novel view is generated is equivalent to capturing an image of the scene with a notional camera  3 , positioned a distance b from camera  1 . The location of the novel view I′ is defined in terms of the ratio of distance b to distance a, the total distance between cameras  1  and  2 .  
         [0042]     The method of the first embodiment of the present invention comprises obtaining disparity maps between more than one input image, using, for example, a matching algorithm, forward mapping disparities from more than one image to each desired output image position, and obtaining the colour information for the novel view by reverse mapping back to more than one input image. The embodiments of the invention may be used to generate a pair of novel views comprising a novel synthetic stereo pair. The embodiments of the invention are more accurate than the forward mapping algorithm described by Seitz and Dyer. The reverse mapping procedure introduces fewer anomalous pixels, and no spurious blank regions. As is well known, a reverse mapping procedure also allows source images to be sampled in a more controlled manner.  
         [0043]     An advantage of the reverse mapping process described below is that newly hidden or revealed parts of the scene can be resolved among pixel offsets rather than among pixel colours, as is required in certain of the above prior art. This allows the novel views to be rendered more completely and more accurately.  
         [0044]     According to certain of the embodiments, it can be ensured that the two source images are consistent with each other. This constraint reduces the number of depth artefacts that are apparent when the new images are viewed as a stereo pair. The importance of combining colour information from different source images is preserved.  
         [0045]     The method as described hereinbelow requires two or more input views of the same scene or object. The minimal case is illustrated in  FIG. 2  in which cameras  1  and  2  capture a stereo pair of images I L  and I R  of a scene comprising surfaces  7  and  8  separated in depth. If the cameras are not side-by-side with parallel optic axes, the images must first be rectified. The process of rectification ensures that corresponding features in the two images are related by horizontal offsets only.  
         [0046]     The two images produced by the cameras of  FIG. 2  are illustrated in  FIG. 5 . The two surfaces  7  and  8  are denoted with labels F and G. Since the two cameras capturing the two images are parallel, only horizontal disparities are present. The two images have been cropped, so that surface G has no disparity. A row of pixels through the centre of each image is denoted by the dotted line. The row of pixels and the corresponding disparities are shown at  10 . For example, point f 1  is at pixel position  5  in image I L  and at position  5 +(−2)=3 in image I R . That is, the pixel indicated at  11  contains image feature f 1  and has a corresponding entry at  12  in the disparity map of −2. This indicates that, to obtain the corresponding position of feature f 1  in image I R , two pixel positions must be subtracted from the pixel position of f 1  in image I L , leaving the pixel at position  3  in image I R  as indicated at  13 . Points labelled X were visible in one image only, and can therefore not be matched.  
         [0047]      FIGS. 6   a  and  6   b  are flow diagrams illustrating the geometric processing and colour processing aspect of the embodiment of the present invention, respectively. Starting from source images I L  and I R  ( 30   a ,  30   b ), a stereo matching algorithm M ( 31 ) is used to compute the correspondence maps (or disparity maps) producing disparity maps D L  ( 32   a ) (which maps image I L  to image I R ) and D R  ( 32   b ) (which maps image I R  to image I L ). In general, the two maps are independent because there will be features in image I L  that are hidden from view in image I R , and vice versa. The disparity maps are computed and forward mapped to provide new disparity maps D L ′ and D R ′ ( 33   a ,  33   b ). Starting from a position in one of the two novel views, the corresponding disparity map is used to look up a colour in each source view. For example, disparity map D L   40  is used to look up colours at j L  and j R  in images I L  and I R , respectively. The colour from image I L  is associated with position j L ′ and blended with the colour from image I R  which is also associated with position j L ′. The result is assigned to position j L ′ in image I L ′. A corresponding set of steps applies to the computation of the colour at position j R ′ in image I R ′. The result is two output images I L ′ and I R ′ ( 34   a ,  34   b ) forming novel views of the scene of the original images.  
         [0048]     The individual stages of the algorithm are described below. It is convenient to consider the synthesis of a single image, I′, rather than the stereo pair of images I L ′ and I R ′. With reference to the following section, the left-hand novel image can be obtained by substituting the corresponding features with the L subscript, and correspondingly for the right-hand novel image with the R subscript.  
         [0049]      FIG. 7  shows points f 1  to f 4  on surface  7  and points g 1  to g 10  on surface  8 . The configuration of the two surfaces is viewed by cameras  1  and  2 , producing images I L  and I R , respectively.  
         [0050]     Note that g 3  and g 4  are hidden from camera  2 , and that g 7  and g 8  are hidden from camera  1 . Rows of pixels from images I L  and I R  are shown in  FIG. 9 , which indicates matches between image points in I L  and I R . Point matches are indicated by arrows, which are slanted according to the disparity. With reference to  FIG. 7 , it is assumed for the purposes of illustration that the images are horizontally aligned such that surface G is at zero disparity. No disparity is available at g 3  or g 4  in I L , or at g 7  and g 8  in I R , as these points were not visible at both cameras.  
         [0051]     Image I′ is the “target image”, corresponding to a viewpoint between the original cameras. In particular, if t is a parameter in the range 0-1, and C L , C R  are the camera positions, then the new viewpoint is effectively located at a position (1−t)C L +tC R . For example, with t=½, image I′ will correspond to a viewpoint halfway between C L  and C R , taken by notional camera  3 , as shown in  FIG. 8 .  
         [0052]     To perform reverse mapping, a new disparity map D′, expressed in the coordinates of I′ is required, as indicated in  FIGS. 6   a  and  6   b . Both D L  and D R  can be forward mapped into D′. If the disparities are represented by non-negative numbers, then for each position (i,j), the equations are 
 
D′(i, j′)←D L  (i, j L ), where  j=j   L   −tD   L  ( i, j   L ) and 
 
D′(i, j′)←D R  (i, j R ), where  j′=j   R +(1 −t )D R  (i, j R ).  (1) 
 
         [0053]     The notation ‘a←b’ means ‘the value b is assigned to a’. These equations can be interpreted as mapping towards j R  and j L  respectively, given that 0≦t≦1.  
         [0054]     The forward mapping process is indicated in the lower part of  FIG. 6   a . In general, the horizontal target coordinate in Equations (1) will not be a whole number, and so the source disparities will not map to an exact pixel position. Furthermore, it is possible for more than one source value to map to the same (approximate) position. The following procedure can be used to produce a single estimate at each pixel.  
         [0055]     Each forward-mapped sample can be associated with a “coverage” value 0≦α≦1. For example, suppose that the horizontal target position is between two pixels p and q, so that j p ≦j′≦j q . The source value is mapped to both positions, with α p =j q −j′ and α q =j′−j p . This results in a list of source values and corresponding “coverages” at each target position. The outermost values, which represent surfaces closest to the target viewpoint, should tend to occlude the other values at each position. This principle can be used to obtain a single target value at each position. The value is computed by sorting the list of candidate values from low to high disparity. The list is then composited from back to front, using the a values as weights.  
         [0056]     The procedure described above is used to resolve multiple values into a single estimate at each position in D′. Each entry in D′ identifies a unique position in each of the source images. However, in general there will also be regions of D′ to which no values have been mapped. This is due to the effect of occluding surfaces in the scene. The resulting gaps can be filled independently along each row of the disparity array, as described below.  
         [0057]     In general, the disparity surface of the occluded surface should be extended until it meets the occluding edge, and this can be achieved in the following way. The disparities at either end of each gap are examined, and the lesser of the two identifies the side that is to be extrapolated. A one-dimensional model can then be fitted to the adjacent disparities on that side of the gap. This model is constrained, such that the extrapolated edge cannot be in front of the occluding edge at the point of contact. As a convenient approximation to this procedure, the smaller of the two end-point disparities can simply be assigned to all positions in the gap. This is effectively a zero-order extrapolation model.  
         [0058]     The forward mapping stage is illustrated in  FIG. 10 . Disparities are forward mapped according to the correspondences shown in  FIG. 9 . This process leaves gaps between g 2  and f 1  and between f 4  and g 9  in the coordinates of I′. The missing values are estimated by comparing the end points of the gap; in this example, the disparity of g 2  is less than that of f 1 , and so its value will be copied into the gap. Similarly, the disparity of g 9  will be copied into the gap between f 4  and g 9  in I′. With reference to  FIGS. 2 and 7 , it can be seen in  FIG. 11  that surface G has effectively been extended to meet the occluding surface F.  
         [0059]     In order to render the novel view, each pixel position must now be reverse mapped into the source views as follows:  
                 I   ′     ⁡     (     i   ,     j   ′       )       ←     {                 I   L     ⁡     (     i   ,     j   L       )                   I   R     ⁡     (     i   ,     j   R       )             ⁢           ⁢   where   ⁢           ⁢     j   L       =         j   ′     +         tD   ′     ⁡     (     i   ,     j   ′       )       ⁢           ⁢   and   ⁢           ⁢     
     ⁢     j   R         =       j   ′     -       (     1   -   t     )     ⁢         D   ′     ⁡     (     i   ,     j   ′       )       .                       (   2   )             
 
         [0060]     Note that if t=0, then j L =j′, so that points can be drawn directly from I L . Likewise, if t=1, then j R =j′, so that points can be drawn directly from I R . In general, the source coordinates in I L  and I R  will not be integer positions. However, it is straightforward to obtain a colour in each case, by interpolation between the neighbouring pixels. Linear interpolation between the horizontally adjacent values is a suitable procedure, although more accurate models, such as cubic interpolation, could be used.  
         [0061]     According to Equation (2), the backward mapping and interpolation procedures will usually give two possible values for each pixel in the novel view. It is natural to blend these colours, according to the proximity of the novel viewpoint to the source camera positions. In particular, if I′ coincides with I L , then colours from I R  should make no contribution. Likewise, I L  should not contribute if I′ coincides with I R . If the new view coincides with one of the original views, then the new colour will be set equal to the corresponding original colour. These considerations lead to the colour-blending scheme 
 
I′(i, j′) (1−t)I L  (i, j L )+tI R (i, j R )  (3) 
 
 with j L  and j R  defined as in Equation (2). Points that were visible in one view only (such as g 3  in  FIG. 11 ) must be rendered directly, as there is no companion colour to blend with. For this reason, it may be desirable to apply a global colour normalisation to the two original images before the pixels are mapped. 
 
         [0062]     The process described above will produce a geometrically correct interpolated view, subject to the accuracy of the disparity information and the extrapolation model. For example, the scene shown in  FIG. 7  will be rendered correctly by the method described here. This is not true of the ordinary forward mapping method, for example, assuming that the pixel colours were forward mapped. With reference to  FIG. 10 , consider the pixel between g 2  and f 1  which, as before, is left undefined in the coordinates of I′. The gap could be filled by interpolating between the known colours g 2  and f 1 , as shown by Chen and Williams and by Seitz and Dyer. This approach would not, in general, give an accurate estimate of the missing value; in particular, surfaces F and G are separate, as in  FIG. 7 , and so they are likely to be distinct colours. If the gap around g 3  is large, then a spurious colour gradient will appear in the synthetic range. Note that extrapolation of the colour from either end of the gap will, in general, also produce an artefact. This is because the missing image region may contain complex image features. It is not usually possible to extrapolate (or interpolate) image features from the surrounding pixels. In principle, the gaps in the original disparity arrays could be filled before the forward mapping process. However, this would still not guarantee that all pixels in I′ would be defined, and so the gap-filling problem would remain.  
         [0063]     In some cases, previously unseen image texture must be synthesised in the novel view. When combined with a texture-synthesis algorithm, the procedure described above ensures that new images from different viewpoints will be mutually consistent.  
         [0064]     As described above, the method described herein is particularly well suited to the synthesis of stereoscopic image pairs. This is because two interpolated images of the same scene will be mutually consistent. In a further embodiment, the method can also be used to synthesise individual images, for non-stereoscopic applications.  
         [0065]     The disparity maps D L  and D R  may have been obtained independently, by matching the left image to the right, and the right image to the left, respectively. In general, the two disparity maps will not be mutually consistent, due to errors in the matching process. However, it is possible to enforce consistency in the following way: D L  is used to map a point (i, j L ) in I L  to (i, j R ) in I R . The other disparity map, DR, is then used to map (i, j R ) back to I L . If the disparity maps are consistent, then the above process will return the original point, (i, j L ). If the test fails, then the disparity DL (i, j L ) can be discarded. The same result would be obtained with the L and R indices exchanged.  
         [0066]     If the disparity maps are consistent, then it is unnecessary to store both of them, because D L  can be computed from D R , and vice versa. Monotonicity is a special case of consistency, meaning that corresponding features appear in the same horizontal order in I L  and I R . It is often useful to enforce monotonicity, as part of the image-matching algorithm. This results in a single disparity map. Furthermore, the process of forward mapping the disparities (as in Equation (1)) is simplified in this case. The ordering constraint means that no more than one disparity can map to a given position in D′, and so there are no conflicts to be resolved.  
         [0067]     Depending on the choice of matching algorithm, the disparity map can be incomplete. For example, the matching algorithm may fail over blank regions of the source images, in which there are no features to be matched. Equally, it may be desirable to delete any disparities in D L  that are inconsistent with DR, and vice versa, as described above. The resulting gaps can be filled as described above.  
         [0068]     If there are more than two source views, it may be possible to compute several independent disparity maps. This is because the visible regions of the scene are likely to vary according to the choice of camera pair. There are two ways to combine the multiple estimates. As described earlier in the case of two disparity maps, the largest available value (meaning the closest feature) can always be chosen. Alternatively, a consistent relationship can be imposed among all of the disparity maps, as described above.  
         [0069]     In order to increase the depth range, new views must be obtained from more widely separated positions. This makes it much more likely that part of a novel view will have been hidden from both source cameras. Although it will not usually be possible to render the hidden area correctly, it may be possible to make a good prediction. Furthermore, the prediction can be made consistently across a number of synthetic views.  
         [0070]     The appearance of an unseen area can often be well predicted from the appearance of the surrounding region. For example, Effros and Leung, Texture Synthesis by Non-Parametric Sampling, Proc, IEEE International Conference on Computer Vision, 1999, pages 1033-1038, describes a simple algorithm which is capable of synthesising a variety of image textures. New pixel colours are predicted by a procedure which involves sampling the horizontal and vertical image neighbourhood. If a completely new image region must be generated in each of two novel views, a texture synthesis algorithm could be applied to the missing region in each case. However, this would not result in a consistent stereo image pair.  
         [0071]     The reverse mapping representation, described above, allows for consistent texture synthesis. This is because it is possible to sample the source images via the backward mapping procedure. The resulting texture model then supplies the missing pixel values. Since the same texture model is used for each new image, the resulting novel views will be mutually consistent.  
         [0072]     The schematic diagram of  FIG. 12  illustrates a computer  4  for performing the above-described image processing. A central processing unit (CPU)  23  is connected to a read-only memory (ROM)  20  and a random access memory (RAM)  22 . The CPU is provided with image data  24  from the image sources via an input/output mechanism  25 . The CPU then performs the geometric and colour processing to provide the novel image  26 , in accordance with instructions provided by the program storage  21  (which may be part of the ROM  20 ). The program itself, or any of the inputs and/or outputs to the system may be provided or transmitted to/from a communication network  27 , which may be, for example, the internet.  
         [0073]     It will be appreciated by the skilled person that various modifications may be made to the above embodiments without departing from the scope of the present invention as set out in the accompanying claims.