Abstract:
A method of processing data is provided. The method comprises the steps of: comparing first and second samples of a space, the first and second samples being related by a set of transformations, to provide a set of pairs of signals, each of the pairs of signals corresponding to substantially the same feature in the space in the first and second samples; for each of the pairs of signals, evaluating residuals corresponding to the differences between the values of the space in each sample; evaluating a first estimate of the set of transformations from the residuals; estimating a tensor field representing orientation of flow in the space, the tensor field covering at least one point in the space; and recalculating, from the first estimate and the tensor field, the residuals for each of the pairs of signals to improve the estimate of the set of transformations.

Description:
TECHNICAL FIELD  
       [0001]     The present invention relates to processing data to improve the estimate of a transformation between two signals. It is assumed that each signal is sampled, and that each sample comprises two or more measured variables. For example, each pixel in a typical colour image consists of red, green and blue values.  
       BACKGROUND  
       [0002]     The transformation between two signals can be estimated by matching samples from one input to corresponding samples in the other. For example, the motion of an object can be estimated by tracking image-features between successive video frames, as described by Horn and Schunck, Determining Optic Flow, Artificial Intelligence, 17, 185-204, 1981.  
         [0003]     Under the assumption that the corresponding points within the image have the same brightness or colour in adjacent frames, the motion field can be estimated by matching corresponding points from one image to another. The accuracy of such estimates is limited by the content of the images. For example, regions of the image having a uniform brightness or colour will not yield accurate information as to potential motion, because for each point in such a region, there will be many possible matches in the adjacent video frames.  
         [0004]     It is shown, however, in Horn and Schunck, that the motion field can be estimated in featureless regions. If the scene consists of locally smooth surfaces, then the resulting motion field will also be locally smooth. Adopting this smoothness as a constraint ensures that the motion estimates in featureless regions are consistent with the estimates obtained in nearby, but more feature-rich regions of the images. The effect of the smoothness constraint is to impose a condition that the directions of neighbouring motion estimates are approximately parallel to one another. In essence, this method imposes a smoothness constraint onto a geometric mapping between matching features.  
         [0005]     In Jähne et al, Study of Dynamical Processes with Tensor-Based Spatial Temporal Image Processing Techniques, Proceedings of European Conference on Computer Vision, pp 323-336, 1998, an alternative approach to optical flow estimation is given. In order to detect motion between adjacent frames of video data, the video sequence is represented as a volume in (x, y, t), where x and y are the two spatial dimensions of the video data and t represents time. Adopting this approach, any moving feature will appear as an oriented structure in the volume. For example, a moving point would trace out a line in the three-dimensional space whereas a moving edge would sweep out an oriented plane. Such lines and planes can be detected by evaluation of the structure tensor at each point in the space. The structure tensor is defined in Knutsson, Representing Local Structure using Tensors, Proceedings of the Sixth Scandinavian Conference of Image Analysis, pp 244-251, 1989, in which the structure tensor is represented by a matrix, the eigenvalues of which are functions of the local dimensionality of the signal.  
         [0006]     A method of recovering the internal structure of a high-dimensional data-set is given in Roweis and Saul, Nonlinear Dimensionality Reduction by Locally Linear Embedding, Science 290, pp 2323-2326, 2000. The method is based on the concept that a given data point may be represented as a linear combination of its nearest neighbours in the high-dimensional space. For data which lies on a lower-dimensional surface, the neighbouring points can be used to construct a local coordinate system that dispenses with at least some of the original axes. The result of this process is a “local linear embedding”, which facilitates interpretation of the original data.  
         [0007]     Miller and Tieu, Colour Eigenflows: Statistical Modelling of Joint Colour Changes, Proceedings of the International Conference on Computer Vision, pp 607-614, 2001 disclose image analysis which considers the changes in ambient lighting. A statistical model of how a given colour in a particular image changes with respect to the illuminant is constructed. This enables prediction, given an input image, of the appearance of the scene under different illumination. Changes in the appearance of the image, for example the parallax introduced by moving the view point, are not considered. This statistical model is akin to imposing the smoothness constraint onto a photometric mapping.  
       SUMMARY  
       [0008]     According to a first aspect of the invention, there is provided a method of processing data comprising: (a) comparing first and second samples of a space, the first and second samples being related by a set of transformations, to provide a set of pairs of signals, each of the pairs of signals corresponding to substantially the same features in the space in the first and second samples; (b) for each of the pairs of signals, evaluating residuals corresponding to the differences between the values of the space at the location of the feature in each sample; (c) evaluating a first estimate of the set of transformations from the residuals; (d) estimating a tensor field representing orientation of flow in the space, the tensor field covering at least one point in the space; and (e) recalculating, from the first estimate and the tensor field, the residuals for each of the pairs of signals to improve the estimate of the set of transformations.  
         [0009]     Steps (d) and (e) may be repeated at least once.  
         [0010]     The step (a) may be effected using a signal-matching algorithm.  
         [0011]     The residuals may be equal to d k =f′(p k )−f″(p k +t k ), where f′(p k ) and f″(p k +t k ) are a pair of signals corresponding to substantially the same feature in the space, measured at points p k  and p k +t k , respectively, t k  represents the set of transformations and k is the index of each pair of signals. Step (c) may comprise defining a symmetric and positive-definite matrix M, such that |d k | M =(d k   T Md k ) 1/2 , and minimising |d k | with respect to t k .  
         [0012]     The step of estimating a tensor field may be carried out for every point in the space and may comprise determining tensors for regions in which no tensor has yet been determined by interpolating between existing tensors obtained from prior estimates of the set of transformations. The interpolation may be based upon a neighbourhood weighting function whose value decreases monotonically away from the location of the pair of signals. The neighbourhood weighting function may be a Gaussian function. The tensor field may be used to calculate a matrix M f  representing the set of transformations at each point in the space. The eigenvalues of the matrix M f  may be chosen to fit the dimensionality of the set of transformations.  
         [0013]     The method may be iterated until a convergence condition is met. The dimensionality of the estimate of the set of transformations may be subject to at least one constraint. This constraint may be a spatial smoothness or a diochromatic model constraint.  
         [0014]     The method may be applied to data wherein the first and second samples of a space are first and second images, the space is a red-green-blue colour space, and the set of transformations represent a spatial disparity at each point in the images. The method may be applied to the image data to provide image recognition or image prediction. The estimated tensor field may be used to create a model of a transformation between first and second images.  
         [0015]     According to a second aspect of the invention, there is provided a method of estimating disparity between first and second images, comprising: computing first and second disparity maps for matching features in the first and second images, corresponding to first image to second image disparity and second image to first image disparity, respectively; deleting inconsistent entries from the first and second disparity maps to obtain a cross-checked third disparity map; and improving the third disparity map in accordance with the first aspect of the invention, using the third disparity map as the first estimate of the set of transformations.  
         [0016]     According to a third aspect of the invention, there is provided a method of estimating motion in a video stream, comprising applying the method of the first aspect of the invention to substantially adjacent pairs of images from the video stream, the pairs of images corresponding to the first and second samples in a red-green-blue colour space. In such a method, the step of estimating a tensor field covering each point in the space for a given substantially adjacent pair of images may comprise estimating a current tensor field using a prior tensor field evaluated when matching a prior pair of images from the video stream. The current tensor field may be recursively estimated from the prior tensor field.  
         [0017]     The method may be applied to audio data as part of a speech recognition algorithm.  
         [0018]     Further aspects of the present invention include a program for controlling a computer to perform the above-described methods, such a program when stored on a storage medium, transmission of such a program across a communications network, and a computer programmed to perform such a method.  
         [0019]     In accordance with a further aspect of the present invention, there is provided an apparatus for matching signals, comprising: means for comparing first and second samples of a space, the first and second samples being related by a set of (unknown) transformations, to provide a set of pairs of signals, each of the pairs of signals corresponding to substantially the same feature in the space in the first and second samples; means for evaluating residuals for each of the pairs of signals, the residuals corresponding to the differences between the characteristics of the space at the location of the feature in each sample; means for evaluating a first estimate of the set of transformations from the residuals; and means for estimating a tensor field representing orientation of flow in the space, the tensor field covering each point in the space; and means for recalculating, from the first estimate and the tensor field, the residuals for each of the pairs of signals to improve the estimate of the set of transformations. 
     
    
     BRIEF DESCRIPTION OF DRAWINGS  
       [0020]      FIG. 1  is a flow diagram illustrating the implementation of the method of an embodiment of the present invention;  
         [0021]      FIGS. 2   a  to  2   f  illustrate the steps of image matching;  
         [0022]      FIG. 3   a  to  3   c  are a comparison between a one-dimensional and a two-dimensional flow field;  
         [0023]      FIG. 4   a  to  4   c  illustrate vector and tensor representations of a one-dimensional flow;  
         [0024]      FIG. 5  illustrates an image matching algorithm in accordance with an embodiment of the present invention;  
         [0025]      FIG. 6  illustrates a motion estimation algorithm in accordance with an embodiment of the present invention;  
         [0026]      FIG. 7  illustrates a recursive motion estimation algorithm in accordance with an embodiment of the present invention;  
         [0027]      FIG. 8  is a flow chart illustrating a method constituting an embodiment of the present invention; and  
         [0028]      FIG. 9  is a block schematic diagram of an apparatus for performing the method of  FIG. 8 . 
     
    
     DETAILED DESCRIPTION  
       [0029]     The method as described hereinbelow will be described primarily with reference to matching graphical images, although this is merely an example and the method may be used in other applications, such as speech recognition. The method is generally applicable to the matching of so-called vector-valued signals. Such signals can be thought of as inputs with a number of measurable variables at each point. For example, a typical colour image has three variables: red, green and blue, at each spatial position. The method of an embodiment of the present invention starts from two sets of samples of a space, for example two images taken of a scene, and provides an effective way of matching features which correspond in the two images. The appearance of a single feature may change between two different views due to a variety of reasons, including change in perspective from the viewpoint and differences in illumination. Matching the common features enables a transformation model of the scene to be established from which images can be created from a novel viewpoint, other images from the scene may be recognised, and motion estimation of common features may be estimated, in addition to other applications.  
         [0030]     The transformation model is estimated by comparing the positions of corresponding features in the two views. In order to make this comparison, image points must be “matched” between the two views. The change in appearance of the common features is a multi-dimensional function, mapping each point to a new position and colour. Position is a two-dimensional parameter, whilst colour is a three-dimensional parameter (red, green, blue).  
         [0031]     It is generally difficult to make accurate estimates of such mappings because the signals may be locally ambiguous. There may be no way to distinguish between many possible mappings, even if there is only one correct solution. To reduce the number of possible mappings it is necessary to constrain the choice of mappings in some way. The method provided by the embodiments of the present invention consists of a signal-matching procedure that imposes a novel form of constraint.  
         [0032]     When imposing a dimensionality constraint, it is generally expected that the dimensionality of mapping between two signals is lower than that of the signals themselves. Consider the example of two colour images, related by a spatial mapping and a brightness offset. The brightness offset can be interpreted as a one-dimensional transformation of the three-dimensional colour space. A model of this transformation can be constructed, and used to help estimate the spatial mapping. Although the transformation between the colours (or other dependent variables) may be much more complex, a useful model can typically be constructed by the method described here.  
         [0033]     The term “space”, as used herein, refers to a set of points, each point being determined by a unique combination of values from each of a set of variables. For example, each point in a space of colours can be determined by its red, green and blue values.  
         [0034]     It is useful to compare the methods of the embodiments of the present invention to the algorithm of Horn and Schunck. Both methods apply constraints in order to improve the estimate of a signal transformation. The Horn and Schunck method constrains the transformation to be spatially smooth. This approach results in a biased solution, because the underlying transformation may not always be smooth; for example, the motion field produced by an object moving across a static backdrop is discontinuous at the boundary of the object. The methods of the embodiments of the present invention impose constraints on the dependent variables of the transformation. In particular, the dependent variables are required to change consistently with respect to the transformation.  
         [0035]     For example, the dependent variables of a typical image are the red, green and blue values at each spatial position. Suppose that the two input signals are views of the same object, taken from slightly different positions. The apparent colour of a scene point can be modelled as a mixture of the ‘surface’ and ‘illuminant’ colours. Although a given scene-point may have a different colour in each view (e.g. due to lighting effects) both colours should be mixtures of the same surface and illuminant components. This constraint can be enforced by the present method. The advantage of this approach is that it applies to both the continuous and discontinuous parts of the signal transformation.  
         [0036]     The block diagram of  FIG. 1  illustrates the applications of the method described below. Data samples  1  and  2  are taken from a data source  10 . The data source  10  may be, for example, a visible scene, in which case the samples  1  and  2  are images of that scene. The data sample domain  11  is a subset of the data source  10 . The samples  1  and  2  are subject to data processing  12  which yields a transformation model  13 . The transformation model  13  can be used to provide an image recognition system  14  for detecting previously unanalysed data sample  3 . Alternatively the transformation model  13  may be used in a prediction system  15  to create a novel data sample corresponding to an artificially generated view of the data source  10 .  
         [0037]      FIGS. 2   a  to  2   f  illustrate the general approach to image-matching.  FIGS. 2   a  and  2   b  show images f′ and f″ representing different views of the same scene. The images are matched by identifying points with similar colours, and the resulting spatial flow is shown in  FIG. 2   c . Note that the flow is smooth. Two further views are shown in  FIGS. 2   d  and  2   e , which can be matched as before. However, in this example the resulting spatial flow is not smooth.  
         [0038]     Although signal matching algorithms are known for matching common features between two images, the method described herein increases the accuracy and the completeness of the computed mappings. The accuracy can be improved because the dimensionality constraint described below can be used to make mapping consistent with a physical model of the transformation. The completeness can be improved because, for ambiguous regions, the dimensionality constraint eliminates a large number of spurious solutions.  
         [0039]     The method can be combined with further constraints, for example the smoothness constraint described in Horn and Schunck. Further details of the latter are given below. Alternatively, the method may be applied in the absence of any further constraints. The main problem with smoothness constraints is that they must be used selectively. In particular, to avoid biasing the estimate, smoothing should not be applied across depth or motion boundaries. This greatly complicates the signal-matching problem, because the locations of the discontinuities must be estimated in conjunction with the point-matches. By contrast, the dimensionality constraint described here can be applied to both the continuous and discontinuous parts of the signal transformation.  
         [0040]     The method may be easily combined with existing matching algorithms and can be turned on or off as required. The computational overhead introduced by the method is easily managed; for a given pair of samples, the new metric adds a constant amount to the cost of computing the original Euclidean distance. The representation constructed during the matching procedure may have additional uses. For example, when considering the matching of two images of a particular scene, the representation constitutes a photometric model of the scene which may be used in rendering any novel views, leading to a more accurate result.  
         [0041]     A more detailed description of a particular embodiment of the present invention will now be described.  
         [0042]     Two signals, taking values from a space          , are defined as f′ and f″. These two signals are measured at points p k , where k is a convenient index for the samples. The method of this embodiment may be considered as solving a matching problem of the form 
 
f′(p k )         f″(p k +t k ), k=1 . . . K,  [1]
 
 the vectors t k  defining the underlying transformation. The symbol indicates that the two signals match at points p k  and p k +t k , respectively. 
 
         [0043]     The method described herein may be applied to match any pair of vector-valued signals and may be extended to any number of dimensions and any range of functions. However, this embodiment will be described in connection with colour images in which the domain of each signal consists of points p=(x, y) and the range of each signal is the RGB colour-space           such that f′=(r′,g′,b′) and f″=(r″,g″,b″). For example, Equation 1 can be interpreted as a mapping between two views f′ and f″ at the scene, with t k  being the parallax of each point p k .  
         [0044]     The object of the matching algorithm is to recover the underlying transformation vectors t k . This is achieved by minimising the error d with respect to the possible values of t k , where 
 
 d   k   =f ′( p   k )− f″ ( p   k   +t   k ).  [ 2 ]
 
         [0045]     Equation 2 provides a definition of a “residual” vector d k . The norm d is usually equal to the Euclidean distance, so that if d is a column vector and d T  is its transpose, then |d|=(d T d) 1/2 . The method of the embodiment provides a generalisation of this definition, in particular by considering metrics of the type 
 
| d|   M =( d   T   Md ) 1/2 ,  [ 3 ]
 
 where M is a symmetric and positive-definite matrix. In particular, if M is the identity matrix, then |d| M  reduces to the Euclidean distance |d|. In general, however, the matrix M is allowed to vary over the space          . This means that a given discrepancy d, as defined in Equation 2, may seem to be smaller or larger, depending on the individual locations of f′ and f″ in          . The motivation for this is shown in  FIGS. 3   a - 3   c .  FIG. 3   a  illustrates a two-dimensional flow d k  in a two-dimensional space          . The axes of the two dimensional space represent the dependent variables of the mapping. For example, the square could represent a slice through the cube containing the RGB colour space,          , in which case the arrows would indicate matches between similar colours. The arrows indicate the direction of the flow of the four flow vectors illustrated.  FIG. 3   b  illustrates a one-dimensional flow (all the vectors being aligned) in a two-dimensional space. The local dimensionality of the flow may vary within the space. Two possible matches are illustrated in  FIG. 3   c  and indicated by the residual vectors shown as dashed arrows. The residual vectors are the same length and therefore the two matches are equally plausible according to the ordinary measure, |d|. However, only one of the two residuals is consistent with the existing one-dimensional local flow shown in  FIG. 3   b . It would be preferable for the metric of Equation 3 to yield a “shorter” length to this residual so that the consistent match is preferred. 
 
         [0046]     Known matches f′(p k )         f″(p k +t k ) from a previous iteration of the algorithm or, in the first instance, the first set of residuals d k , are used to define M at each point in the space          . The definition is based on the associated ‘residual’ vectors d k , each of which connects two points f k ′ and f k ″ in          . It is natural to attach each residual to the midpoint, which is defined as  
                 f   k     =       1   2     ⁢     (       f   k   ′     +     f   k   ″       )         ,           [   4   ]             
 
 such that  
         f   k   ′     =         f   k     -       1   2     ⁢     d   k     ⁢           ⁢   and   ⁢           ⁢     f   k   ″         =       f   k     +       1   2     ⁢       d   k     .               
 
 Next, each known residual is represented as a symmetric matrix, formed by the normalized outer-product  
               Δ   k     =           d   k     ⁢     d   k   T                d   k          2       .             [   5   ]             
 
         [0047]     This structure tensor representation was proposed in a different context by Knutsson. In effect, d k  represents a direction, whereas Δ k  represents an orientation.  
         [0048]      FIGS. 4   a  to  4   c  illustrate the differences between local direction and local orientation as represented by d k  and Δ k , respectively.  FIG. 4   a  is a vector representation of a sampled one-dimensional flow, d k . The average of the vectors is zero.  FIG. 4   b  is a tensor representation Δ k  of the same sampled flow, the tensors being attached to the midpoint of the original vectors. The average of the tensors is representative of the flow.  
         [0049]     The next step is to define M at each point in          , based on the value of Δ at that point. This is not immediately possible because, in general, only a subset of points in           will have associated tensors. Nonetheless, it is straightforward to ‘fill in’ the missing tensors, using a scheme which is similar to that described by Miller and Tieu. A tensor at any point f can be obtained from the local average  
                 Δ   f   *     =         ∑     k   =   1     K     ⁢         N   k     ⁡     (     f   ,     f   k       )       ⁢     Δ   k             ∑     k   =   1     K     ⁢       N   k     ⁡     (     f   ,     f   k       )             ,           [   6   ]             
 
 where N k (f, f k ) is a ‘neighbourhood’ function which takes a high value when f k  is close to f and falls monotonically to zero as the points become distant. A Gaussian curve of a given variance is a natural choice. The averaged and interpolated tensor representation Δ f * is illustrated in  FIG. 4   c . There is now only the tensor at each point f, and some additional tensors have been interpolated. The result is a complete estimate of the flow that generated the vectors of  FIG. 4   a . It is also possible to incorporate geometric information into the neighbouring function. For example, suppose that p k  is defined by analogy with f k  in Equation 4. The weighting N k (.,.) can then be a function of the separation between p and p k , as well as the corresponding values f and f k . This modification makes the scheme more conservative, as flow-information is only integrated over points p k  that are close to p. The precise definition of N k (.,.) will depend on the application. 
 
         [0050]     The discrepancies d and −d are consistent with the same oriented flow-structure, although their directions are opposed. If the interpolation procedure in Equation 6 were applied directly to the residual vectors, they would cancel each other out. This is the reason for the tensor representation; according to Equation 5, d and −d map to the same tensor and so the opposite directions support the same flow estimate in Equation 6.  
         [0051]     Using Equation  6 , a matrix M f  can be estimated at each point in          , based on the corresponding matrix Δ f *. The underlying idea is that if the local flow lies in a subspace of          , then M f  should ‘underestimate’ distances measured in this subspace. It follows that any matches in the flow subspace will tend to be favoured. This achieves the principle objective of the embodiment, which is to make use of inherent structure in the signal-to-signal mapping, as shown in  FIGS. 3   a - 3   c.    
         [0052]     The matrix M f  is set to have the same normalized eigenvectors as Δ f *, because these are aligned with the local structure of the flow field. The dimensionality of the local flow is estimated from the eigenvalues of Δ f *. If the local flow does not have the required dimensionality, then the eigenvalues of M f  are set to unity, so that |d| M  corresponds to the Euclidean distance. If the local flow does have the required dimensionality, then the eigenvectors spanning the flow are given suitably reduced eigenvalues. The matrix M f  will usually be a continuous function of Δ f , although the precise definition will depend on the particular matching problem.  
         [0053]     In a particular application, the definition of M f  may be physically motivated. For example, in the matching of two colour images, Shafer&#39;s dichromatic model (S. A. Shafer, “Using Color to Separate Reflection Components”, Color Research and Application 10(4), 210-218, 1985) can be used. The model represents the appearance of a surface as a mixture of two components; a ‘body’ contribution, which is characteristic of the material, and a ‘surface’ contribution, which is characteristic of the illuminant. The relative proportions of the components depend on the surface orientation, and on the viewing direction. It follows that two views of the same surface should produce RGB values in the same 2-D subspace. This constraint can easily be imposed within the scheme outlined above.  
         [0054]     For example, consider a function pr(f k |{f n ,n≠k}), which can be used to express the probability of match k given the other existing matches, and the dichromatic model. The probability should be low if the first and third eigenvalues of Δ k * are approximately equal, as this would indicate a lack of local structure (including the special case of perfect matching, |d k |=0). The probability should be high if there is a significant difference between the first and third eigenvalues, as this would indicate a locally one-or two-dimensional structure, either of which would be consistent with the dichromatic model.  
         [0055]     Given a definition of the probability, the matrix M is made to have the same eigenvectors as Δ k *, but with the first two eigenvalues made inversely proportional to pr (f k |{f n ,n≠k}). The photometric parameters are not actually estimated; the example is based simply on the dimensionality of the dichromatic model.  
         [0056]     An embodiment of the flow-representation in a matching scheme will now be described. It is assumed that an existing signal-matching algorithm is provided. The flow field is initialized by the residuals d k  of the first attempt at matching, which uses the ordinary metric, |d k |. The complete tensor field Δ f * is then estimated, as described above. On the second iteration, the new metric |d k | M  can be used to improve the matching. The improved match residuals contribute back to the flow field, and the tensors Δ f * are re-estimated. This process continues until a given criterion is met. For example, if the eigenvalues of M are suitably defined, then the iterations can continue until the average error  
         1   K     ⁢         ∑   K     K     ⁢            d   k          M           
 
 is reduced to a given level. Alternatively, the total number of iterations can be limited. 
 
         [0057]      FIG. 5  illustrates schematically the first two passes of an iterative stereo matching algorithm constituting a further embodiment of the present invention. Signals f′ and f″ are the left and right hand images from a stereo pair. For clarity, matches between different image points are shown on different rows of the diagram, indicated at  20  and  21 , respectively. Image point  31  forms a closed loop with f′ and f″, indicating a consistent match. This value is therefore used to contribute to the initial estimate of          . Image point  30  does not have a closed loop and therefore is not used in providing the initial estimate.  
         [0058]     The flow representation is used in the second iteration (k=2), after which the number of consistently matched points has increased: image point  31  is unchanged as image point  31 ′ whereas image point  30  now forms image point  30 ′, a closed loop indicating a match. The flow field is then recomputed from these new matches in further iterations. Arrows leading into           indicate residual colour-vectors being passed from a matching stage. Arrows leading out of           indicate matrices M f  being used to compare pixels in a new matching problem.  
         [0059]     The binocular disparity of an image-point between two images in a stereo pair can be estimated by defining a region of pixels containing the point in the first image and locating the most similar region in the other image. There are two problems with this approach. Firstly it is confused by image ambiguities (e.g. featureless regions). Secondly, it is asymmetric with respect to the two input images, as a given scene point may appear in one view only. These problems can be addressed by computing both of the possible disparity maps (i.e. left-to-right and right-to-left), and deleting any inconsistent entries. The result of this procedure is a sparse but relatively accurate disparity map.  
         [0060]     The matches retained by the above cross-checking procedure can be used to estimate the RGB flow in          . This is attractive because the consistent matches are likely to be correct and because the cross-checking procedure is effectively parameter-free. Once the colour flow has been estimated, the disparity maps can be re-computed using the metric |d| M  as described above. This process may continue for a fixed number of iterations, or until a convergence condition is met.  
         [0061]     In accordance with a further embodiment, the binocular procedure described above can be adapted for motion-estimation, using a video stream as input. This is illustrated in  FIGS. 6 and 7 . The video can be treated as a series of frames, f 1  . . . f n . Each adjacent pair of frames can be treated by analogy with the left and right images of a stereo pair. However, the colour flow field need not be independently estimated for each pair of frames. It is expected that each colour flow tensor, Δ f *, will show a strong temporal correlation over the course of the video stream. There are two ways to make use of these correlations.  
         [0062]     In one embodiment, the process of matching frames f n  and f n−1  can make use of the flow-field           computed from the f n−1           f n−2  correspondences. This is illustrated in  FIG. 6  where a flow field  41  is computed between frames f 1  and f 2 , then used for the matching between frames f 2  and f 3 . Similarly, flow fields  42  and  43  are used for subsequent matches. Alternatively, the flow field can be recursively estimated, as shown in  FIG. 7 . This means that the tensors computed from the f n           f n−1  correspondences are merged with the tensors from the f n−1           f n−2 , and so on to provide a continuously updated flow field  44 - 46 . The advantage with this approach is that, in principle, it would lead to a more accurate and more complete flow-field. The drawback is that the flow-field may contain a proportion of irrelevant information at any given stage.  
         [0063]      FIG. 8  is a flow chart illustrating the method of an embodiment of the invention. At step  50 , data samples are taken of the space and at step  51  the residuals are evaluated. A first estimate of transformations between the common features of the data samples is obtained at step  52 . A tensor field is estimated at step  53  and is used at  54  to recalculate the residuals to provide an improved estimate of the matching between the two signals. At step  55 , a decision is made whether the matching is complete. This may be based upon whether a sufficient level of matching has been achieved, or whether a certain number of iterations have been performed. The output of the method is a set of matched signals  56 .  
         [0064]     The methods described above may be embodied in a program for controlling a computer to perform the method. The program may be stored on a storage medium, for example hard or floppy disks, CD or DVD-recordable media or flash memory storage products. The program may also be transmitted across a communication network, for example the Internet or a group of computers connected together in a LAN.  
         [0065]     The schematic diagram of  FIG. 9  illustrates a central processing unit (CPU)  60  connected to a read-only memory (ROM)  61  and a random access memory (RAM)  62 . The CPU is provided with data samples  63  via an input/output mechanism  64 . The CPU then performs the matching procedure on the provided data in accordance with the instructions provided by the program storage  65  (which may be a part of the ROM  61 ) and provides the output, i.e. the matched data samples  66  via the input/output mechanism  64 . The program itself, or any of the inputs and/or outputs to the system may be provided or transmitted to/from a communications network  67 , which may be, for example the Internet.