Abstract:
The present invention relates to a method of generating a keypoint descriptor for identifying an object in an image or in a sequence of images, the keypoint descriptor being substantially invariant to a transformation of the object in the image. The method includes receiving object data representing an object for identification in an image; processing said object data to generate at least one basis function representing a feature having undergone at least one transformation or a transformation sequence across several consecutive frames, optionally using transformations that are out of the image plane to recognize objects from multiple views; modifying a prototype wavelet function based on said at least one basis function to generate a plurality of modified wavelet functions; comparing the plurality of modified wavelet functions with the at least one basis function; selecting a modified wavelet function of said plurality of modified wavelet functions based on the comparison of the plurality of modified wavelet functions with the at least one basis function; and processing an input image or input orientation field according to said selected modified wavelet function to generate the keypoint descriptor. The present invention further relates to a method of identifying an object in an image using a keypoint descriptor; and apparatus and computer software for implementing a method in accordance with the present invention.

Description:
FIELD OF THE INVENTION 
     The present invention relates to improvements in the field of image processing. The present invention further relates to a method of image processing, and apparatus and computer software for implementing the methods of the invention. 
     BACKGROUND OF THE INVENTION 
     In the field of computer vision one distinctive and complex task is image analysis and object recognition. A number of methods have been developed to address this task, which include: angular radial transform (ART); scale invariant feature transformation (SIFT); principal component analysis-scale invariant feature transformation (PCA-SIFT); and gradient location and orientation histogram (GLOH). 
     The method of ART disclosed in patent publication no. US 2002/0010704 describes a method of generating a descriptor for a complete image. This method has the disadvantage of not being able to account for occlusion or objects within an image. To overcome this disadvantage, a number of methods such as SIFT have been developed which include processing image data to identify a number of highly distinctive features or keypoints in an image. 
     The method of scale invariant feature transformation (SIFT) disclosed in U.S. patent Application Ser. No. 6,711,293 is a well known technique that comprises two distinctive parts: (1) keypoint detection, which identifies visually distinctive locations in a digital image; and (2) generation of a keypoint descriptor, which characterises a region or patch around the keypoint. 
     Generation of the keypoint descriptor in the SIFT method includes the step of orientation assignment using histograms to determine the dominant orientation(s). When there are two or more equally dominant orientations in an image region around the keypoint, which is the case in almost any image region containing complex imagery, additional keypoints and descriptors are required to be generated for each of the additional dominant orientations detected. 
     In addition, to generate the keypoint descriptor, it is necessary to generate a vector descriptor for each of the keypoints generated; this step also uses histograms. Therefore a problem with the SIFT method is the large amount of processing that is required to generate a keypoint descriptor that has an invariance to rotation. 
     Alternative methods that have been developed from SIFT are PCA-SIFT and GLOH. PCA-SIFT uses similar steps as in SIFT, however instead of using weighted histograms to form the descriptor, PCA-SIFT uses principal component analysis (PCA). An example of PCA-SIFT may be found in the publication entitled “PCA-SIFT: A More Distinctive Representation for Local Image Descriptors” by Yan Ke and Rahul Sukthankar. GLOH is yet another alternative method to SIFT, and is again based on the SIFT method, but utilises more spatial regions in the histograms. The resultant descriptor, which is dimensionally higher than that created using SIFT, is then reduced using PCA. 
     A problem with all of the above methods is that whilst they may be apt at object detection in still images they require a large number of keypoints and they have not been created to tackle the problems that would be encountered in object detection in a series of images such as video applications. 
     The problem with object detection in video, and for example video on the internet, is that video has a number of varying attributes that must be considered when performing computational analysis of several consecutive images to detect an object; for example: 1) bit rate and encoding method, and therefore quality and video compression artefacts; 2) resolution; and 3) colour balance. 
     Whilst much of these effects are not very noticeable to a human observer, this is because current video encoding systems rely on persistence of vision of the human visual system; they do, however, raise a significant problem for computational algorithmic analysis of the video frames. 
     An example of the problems that may occur in video, in respect of estimating keypoint motion from an image frame to a consecutive image frame, is shown in  FIGS. 1   a ,  1   b  and  1   c . Referring to  FIG. 1   a  there are shown three consecutive frames  10   a ,  10   b  and  10   c  in time having the same keypoint identified as  12   a ,  12   b  and  12   c , respectively, in the different frames. A line A-A passing through the centre of the keypoint  12   a  in the first frame  10   a  passes through the corresponding pixel in frames  10   b  and  10   c ; the keypoint in frames  10   b  and  10   c  deviates from the line A-A.  FIG. 1   a  therefore illustrates how the pixel location of a keypoint may move from one frame to next frame in video. 
     Referring to  FIG. 1   b  there are shown three consecutive frames  14   a ,  14   b  and  14   c  and two possible motion paths  18 ,  19  that an image patch  16   a  may take. In a first possible motion path  18  it can be seen that the image patches  16   b  and  16   c  in respective second and third frames  14   b  and  14   c  are located higher in each of the respective frames than image patches  16   b ′ and  16   c ′ shown in the second possible motion path  19 . 
     Referring to  FIG. 1   c  there are illustrated three consecutive frames  20   a ,  20   b  and  20   c . In the middle frame  20   b  there is an image patch  22  having a keypoint  24 . The keypoint  24 ′ and  24 ″ on respective first and third frames  20   a  and  20   c  on either side of the middle frame  20   b  show a possible motion path of the keypoint  24  along a bi-conical surface. 
     Referring to  FIG. 2  there is shown an example of three consecutive images, running from left to right of  FIG. 2 , which together form a video sequence illustrating fine variability. These images show the degree of variation in each of the frames. The feature labelled  26  has been marked in each of the consecutive frames. It can be seen that the feature  26  near the right hand side of the images appears to move to the lower right hand corner for the consecutive frames. 
     The problems in accurately identifying an object in consecutive video images that can arise from movement of a keypoint location in one frame compared with another frame is not addressed by the prior art. 
     It is an object of the present invention to provide improvements in relation to image and video processing. 
     SUMMARY OF THE INVENTION 
     In accordance with a first aspect of the present invention, there is provided a method of generating a keypoint descriptor for identifying an object in an image or in a sequence of images, the keypoint descriptor being substantially invariant to a transformation of the object in the image, wherein the method includes: 
     a) receiving object data representing an object for identification in an image; 
     b) processing said object data to generate at least one basis function representing a feature having undergone at least one transformation or a transformation sequence across several consecutive frames, optionally using transformations that are out of the image plane to recognise objects from multiple views; 
     c) modifying a prototype wavelet function being based on said at least one basis function to generate a plurality of modified wavelet functions; 
     d) comparing the plurality of modified wavelet functions with the at least one basis function; 
     e) selecting a modified wavelet function of said plurality of modified wavelet functions based on the comparison of step d); and 
     f) processing an input image or input orientation field according to said selected modified wavelet functions to generate the keypoint descriptor. 
     This method allows keypoints of an object to be identified and learned, and stored to create a reliable database of keypoint descriptors that can be used for object identification in an image. A keypoint is a distinctive location in an image that can be robustly localised from a range of viewpoints, rotation, scale, illumination, etc. The keypoint descriptor generated by the method of the invention is substantially invariant to a transformation of the object, for example a rotation and/or a translation. The rotation may be in a two-dimensional plane, or in three-dimensions. The translation may be between images in a sequence of images. Substantially invariant means that the keypoint descriptor generated by the method of the invention is suitable for identifying a keypoint in an image under analysis, to identify an object in the image for example, within acceptable tolerances for an image processing application. Therefore, the keypoint descriptor generated by the method of the invention provides accurate and high quality object identification in images, with any transformation of the object for identification having a reduced or no detrimental effect on the quality of object identification. 
     The comparing and selecting steps of the invention allow a modified wavelet function which best matches the at least one basis function to be selected. In this way, the generated keypoint descriptor may be selected to correspond as closely as possible to the generated at least one basis function whilst having the substantial invariance and ease of specification of the modified wavelet function. 
     The method of the invention facilitates generation of a keypoint descriptor quicker, compared with prior art techniques such as SIFT, due to reduced computer processing requirements. Further, the keypoint descriptor is generated by the invention by means of inner product operations, for which there are optimised software libraries and hardware implementations unlike prior art systems such as SIFT. Advantageously, the method of the present invention is applicable to generate a keypoint descriptor for identifying an object in a single, non-video, image. The object may be two-dimensional or three-dimensional, in a two- or three-dimensional image, respectively. The present invention may also be used to identify an object in a series of images spaced over time, which form a video. The present invention may therefore be implemented to improve detectability of, for example, objects, logos and/or brands in video where movement of an object for example due to panning needs to be taken into consideration, as a keypoint for an object may not be in the same pixel location in each frame. The present invention method is therefore highly versatile for image processing techniques. 
     In one embodiment of the present invention the keypoint descriptor may be arranged to identify an object in a single image. The object may be a two-dimensional or three-dimensional object in a two-dimensional image. 
     Preferably, the prototype wavelet function and the plurality of modified wavelet functions, which are used to compute the keypoint descriptor, include a radial distance component and an azimuthal angle component. 
     The prototype wavelet function and the plurality of modified wavelet functions may have the formula:
 
Ψ k ( d ,θ)= d   n     k     −1   e   −α     k     d ( n   k −α k   d ) ·(cos( m   k θ)+ q   x  sin( m   k θ)
 
     where the term d n     k     −1 e −α     k     d (n k −α k d) is the radial distance weighting component and the term (cos(m k θ)+q x  sin(m k θ)) is the azimuthal angle component, and where the term q x  denotes an imaginary unit. 
     In an alternative embodiment of the present invention the object may be a three dimensional object in a three dimensional volumetric data. The keypoint descriptor may also be arranged to identify an object in a series of images spaced over time. 
     The prototype wavelet function and the plurality of modified wavelet functions may comprise a radial distance component, an azimuthal angle component and a polar angle component, which can be an elevation or temporal angle component for three dimensional volumes or image sequences respectively. 
     The prototype wavelet function and the plurality of modified wavelet functions may have the formula:
 
Ψ k ( d,θ,φ )= d   n     k     −1   e   −α     k     d ( n   k −α k   d ) ·(cos( m   k θ)+ q   x  sin( m   k θ)) ·(cos( l   k φ)+ q   y  sin( l   k φ)
 
     where the term d n     k     −1 e −α     k     d (n k −α k d) is the radial distance component with radial element d, the term (cos(m k θ)+q x  sin(m k θ)) is the azimuthal angle component with azimuthal angle θ, and the term (cos(l k φ)+q), sin(l k φ)) is the polar angle component with polar angle φ, and where the terms q x  and q y  denote unit quaternions and obey the rules q x   2 =q y   2 =q z   2 =−1, and q x   q   y =q z . 
     Preferably, the prototype wavelet function and the modified wavelet functions comprise a non-linear weighting of the radial distance component. The non-linear weighting may represent a radial decay. 
     In a preferred embodiment the prototype wavelet function and the modified wavelet functions are quaternion wavelet functions. 
     Preferably, the keypoint is arranged to identify an object in an image patch. 
     The transformation may comprise a rotation. Alternatively, the transformation comprises a translation. The transformation could also be any other geometric transformation or any combination thereof. 
     Preferably, the wavelet functions can be optimised for specific categories of images such as natural images, video broadcasts, internet video clips. At least one basis function is an eigenfunction obtained from examples of the image category. 
     In one embodiment the modifying step may be performed in accordance with the formula: 
     
       
         
           
             
               α 
               k 
             
             , 
             
               m 
               k 
             
             , 
             
               n 
               k 
             
             , 
             
               
                 l 
                 k 
               
               = 
               
                 
                   
                     arg 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     min 
                   
                   
                     
                       
                         α 
                         k 
                       
                       , 
                       
                         m 
                         k 
                       
                       , 
                       
                         n 
                         k 
                       
                       , 
                       
                         l 
                         k 
                       
                     
                     
                       
                         v 
                         = 
                         0 
                       
                       , 
                       1 
                       , 
                       2 
                       , 
                       3 
                     
                   
                 
                 ⁢ 
                 
                   ⌊ 
                   
                     
                        
                       
                         
                           Re 
                           ⁢ 
                           
                             { 
                             
                               
                                 S 
                                 ⁡ 
                                 
                                   ( 
                                   v 
                                   ) 
                                 
                               
                               ⁢ 
                               
                                 
                                   
                                     ψ 
                                     ^ 
                                   
                                   k 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     d 
                                     , 
                                     θ 
                                     , 
                                     
                                       ϕ 
                                       ; 
                                       
                                         n 
                                         k 
                                       
                                     
                                     , 
                                     
                                       m 
                                       k 
                                     
                                     , 
                                     
                                       l 
                                       k 
                                     
                                     , 
                                     
                                       α 
                                       k 
                                     
                                   
                                   ) 
                                 
                               
                             
                             } 
                           
                         
                         - 
                         
                           ψ 
                           j 
                         
                       
                        
                     
                     2 
                   
                   ⌋ 
                 
               
             
           
         
       
     
     where S(v)=δ(v)−δ(v−1)q x −δ(v−2)q y −δ(v−3)q z , 
     Preferably, the comparing step includes matching at least one of the modified wavelet functions with the at least one basis function, and the selected modified wavelet function is selected according to matching criteria. 
     Preferably, the processing step b) includes generating a plurality of basis functions, the comparing step includes matching a number of the plurality of basis functions with at least one of the modified wavelet functions, and the selecting step includes selecting a modified wavelet function for each of the number of the plurality of basis functions according to matching criteria. 
     Preferably, the keypoint descriptor is generated on the basis of the selected wavelet functions. 
     In accordance with a second aspect of the present invention there is provided a method of identifying an object in an image, the method including processing image data representing at least part of said image with a keypoint descriptor generated using the method of the first aspect of the present invention. 
     Preferably, the method of identify an object in an image includes: 
     i) receiving said image data; 
     ii) processing said image data to generate at least one keypoint descriptor representative of at least one keypoint of said image; 
     iii) comparing the keypoint descriptor generated in the method of the first aspect of the present invention with the at least one keypoint descriptor generated in step ii); and 
     iv) determining if said at least one keypoint descriptor generated in step ii) matches the keypoint descriptor generated in the method of the first aspect of the present invention. 
     Advantageously, the method of identifying the object includes estimating transformation parameters of the object in the input image or input orientation field from the keypoint descriptor generated in the method of the present invention. 
     In yet a further aspect of the present invention there is provided apparatus arranged to perform the method of the present invention and a data carrier storing the computer software of the present invention. 
     Further features and advantages of the invention will become apparent from the following description of preferred embodiments of the invention, given by way of example only, which is made with reference to the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1   a  shows positional movement in keypoint location in consecutive frames; 
         FIG. 1   b  shows two possible motion paths of an image patch in consecutive frames; 
         FIG. 1   c  shows a possible motion path along a bi-conical surface in consecutive frames; 
         FIG. 2  shows consecutive images of a video sequence illustrating fine variability; 
         FIG. 3  shows schematically apparatus for performing the method of the present invention; 
         FIG. 4  shows a flow diagram giving an overview of the method of the present invention; 
         FIG. 5  shows a flow diagram giving an overview of generation of a basis function; 
         FIG. 6  shows a representation of an eigenvector basis function for a particular transformation; 
         FIG. 7  shows a flow diagram giving an overview of generation of wavelet prototypes; 
         FIGS. 8   a  and  8   b  show diagrammatically radial decay functions that can be applied to a radial element of the present invention; 
         FIG. 9  shows a representation of a quaternion wavelet function according to an embodiment of the present invention; 
         FIG. 10   a  shows representation of phase quadrature phase invariant receptive field models according to an embodiment of the present invention; 
         FIG. 10   b  shows representations of adapting (steering) phase response; according to an embodiment of the present invention 
         FIG. 10   c  shows representations of kernels used for response grouping according to an embodiment of the present invention; and 
         FIG. 10   d  shows representations of kernels used as bases to generate rotation invariant descriptors according to an embodiment of the present invention; 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Embodiments of the present invention provide a method of identifying a feature or an object in an image, and in particular embodiments of identifying an object in a series of images spaced over time, using a keypoint descriptor generated in accordance with the present invention. 
     Image Processing Apparatus 
     In embodiments of the method of the invention to be described the keypoint descriptor generated by the present invention is used to identify an object in an image, the method being performed by computer software which the image processing apparatus is arranged to run. The keypoint descriptor generated according to the invention may also be generated using computer software running on the image processing apparatus. The computer software may be stored on a suitable data carrier such as a compact disc (CD). 
       FIG. 3  shows schematically apparatus  30  arranged to perform the method of the invention. The apparatus  30  includes a computer terminal CT which includes a central processing unit (CPU)  32 , memory  34 , a data storage device such as a hard disc drive  36  and I/O devices  38  which facilitate interconnection of the computer CT with an optional image capture device such as a camera  40  arranged to record image data. Alternatively, the CT may be arranged to receive image data from a remote image data source such as an image database. 
     The I/O devices  38  further facilitate interconnection of a display element  42  of a screen  44  via a screen I/O device  46 . Operating system programs  48  are stored on the hard disc drive  36  and control, in a known manner, low level operation of the computer terminal CT. Program files and data  50  are also stored on the hard disc drive  36 , and control, in a known manner, outputs to an operator via associated devices and output data stored on the hard disc drive  36 . The associated devices include the display  42  as an element of the screen  44 , a pointing device (not shown) and keyboard (not shown), which receive input from, and output information to, the operator via further I/O devices (not shown). Included in the program files  50  stored on the hard drive  36  is a database  52  for storing image data and data related to the image data, including data related to the characteristics described further below, and a database  54  for storing data related to the template data, including the template data and data representative of a wavelet function for use in generating a keypoint descriptor. 
     Method of Generating a Keypoint Descriptor 
     An overview of methods according to embodiments of the present invention will first be given, with reference to  FIG. 4  which is a flow diagram indicating the steps of the invention. This will be followed by a description of the steps in greater detail. 
     With reference to  FIG. 4 , object data representative of an object for identification in an image is received, in step S 1 . 
     Next, the object data is processed to generate at least one basis function representative of a feature having undergone at least one transformation, in step S 2 . The transformation that the feature may have undergone is a geometric transformation for example: rotation, translation, skewing, scaling or any combination of these transformations. This basis function is an analytical expression that can be used to fine tune wavelet functions discussed in steps S 3 , S 4  and S 5  below. Further details of the steps involved in generating the basis function will be described later. 
     In step S 3 , a prototype wavelet function is either generated or retrieved from a data store and can be modified based on the at least one basis function generated in step S 2  resulting in a plurality of modified wavelet functions. Further details on how the prototype wavelet function is generated will be explained later. 
     In step S 4 , the plurality of modified wavelet functions, generated in step S 3 , is compared with the basis function generated in step S 2 . The basis function may be an eigenfunction. 
     In step S 5 , a modified wavelet function of the plurality of modified wavelet functions generated in step S 3  is selected based on the comparison performed in step S 4 . 
     In step S 6 , an input image or input orientation field is processed according to the selected modified wavelet function to generate a keypoint descriptor. The generated keypoint descriptor is substantially invariant to the transformation the feature has been subjected to in step S 2 , and can be used to assist in identifying an object in an image. The input image or input orientation field corresponds with image data representing at least part of an image for object identification, such as the image data referred to in the section below entitled “Identification of an Object in an Image”. 
     It will be appreciated that the keypoint descriptor generated may be stored in a database with a number of other keypoint descriptors that can then be used for identifying an object in an image. 
     In the detailed description below, reference is made to the method of generating a space-time invariant keypoint descriptor that can be used, for example, to identify features in video. However it will be appreciated that this method can be also applied used for identifying an object in a single two dimensional image. 
     Generate at Least One Basis Function 
     Referring to  FIG. 5 , generation of the basis function starts by receiving image data at step S 10 . This step involves obtaining examples of image patches or space-time image patches, for two-dimensional images or three-dimensional volumetric data respectively, that are representative of the type of visual information that is being analysed. The types of visual data often vary in resolution and statistics from one type of visual source to another. A “gross” example is the case of colour versus black and white imagery; internet streaming resolution versus High Definition broadcast; or natural images versus man-made images. 
     The next step, step S 11 , requires the generation of examples of the types of transformation for which invariance is sought. In the example shown below, there are two distinct cases of this process—one pertaining to rotation, and the other pertaining to rotation and scale. This process is performed using standard approaches which require (i) geometric transformation of coordinates of the standard space and time grid coordinates used in the representation of a discrete image sequence in accordance with the desired transform; and (ii) interpolation of the values from the transformed coordinate locations back to the standard grid used to represent discrete image sequences by trilinear, or other interpolation. 
     A set of space-time sequences, which are each a sequence of images spaced over time, may be referred to as an exemplar image or video stack. Each sequence of frames in the exemplar image stack should be at least as large as the example patch when scaled and/or rotated so that it is of maximum size. All image patches should be re-sized (zero-padded) to this size by placing the transformed sequences within an empty image sequence matrix. In this way, all exemplars will have the same pixel dimensions, denoted by N x ×N y ×N t ; in a preferred embodiment, N x , and N y  are both odd values. 
     In step S 12 , the exemplar image stack is converted into a matrix. This is achieved by re-ordering the images into vectors of dimensions N x N y N t ×1, and stacking these vectors into the rows of a matrix of dimensions N x N y N t ×M, where M represents the number of exemplar images used. Ideally a large number of exemplars of the same order of magnitude as the number of dimensions of the image patch, e.g.  225 , are used. In practice, the technique will work with as few as 1/10 th  the number of exemplars (M) as pixels (N x N y N t ). This matrix is called the observations matrix, O. 
     In step S 13 , the covariance N x N y N t ×N x N y N t  matrix, C, of the observations matrix, O, is next computed. 
     In step S 14 , the eigenvectors of C are found by singular value decomposition. The result of singular value decomposition (SVD) of a matrix C is usually denoted by equation 1:
 
[ U,S,V]=svd ( C )  (1)
 
The eigenvectors of C are stored in the columns of V. Each eigenvector is an orthogonal basis function that, when scaled to the corresponding diagonal eigenvalue entries of S, can be used to reconstruct C.
 
     In step S 15 , the eigenvectors associated with the most significant J eigenvalues, typically identified by the magnitude of positive eigenvalues, are sought by ranking the order of the values in diagonal matrix S (if not already sorted), where J is the total number of eigenvalues/vectors defined in this step. Therefore, if sorted in descending order in magnitude, starting from the largest, the top J eigenvalues associated with the top J eigenvectors are used as prototype functions from which to construct an analytic descriptor or wavelet function. 
     Construct Prototype Wavelet Function 
     In this embodiment, the next step of the process is to construct or generate the prototype wavelet function, in this example quaternion wavelet functions. In other embodiments, the prototype wavelet function may be retrieved from a data store. This step requires the specification of analytic expressions that can be used to modify and therefore fine-tune the wavelet function. In this embodiment the quaternion wavelet function is a three dimensional (3D) quaternion wavelet function. 
     For each of the J top descriptor basis functions a prototype quaternion wavelet function {circumflex over (ψ)} k (d,θ,φ) is constructed. The purpose of the approximating wavelet function is to simplify the parameterisation and specification of the descriptor, and to provide better invariance properties than can be achieved from eigendecomposition alone. 
     For example, referring to  FIG. 6  an eigenvector is shown as a space-time pattern, where x and y axes define a two-dimensional space, and a third, perpendicular, time axis is also shown; this eigenvector is insufficiently smooth for use as a basis for generating a keypoint descriptor and in itself does not yield an invariant descriptor, but it provides some information allowing the setting of wavelet function parameters appropriately. 
     Referring now to  FIG. 7 , which provides an overview of how to create the prototype wavelet functions, in step S 20 , a three-dimensional matrix, D, is constructed whose elements, d pqr , represent the Euclidean distance of each element to the central element of the matrix, the matrix elements being implicitly assigned spatial locations which are the row column and slice plane numbers of the matrix. The dimensions of matrix D should be of the order of the neighbourhood, within a single scale, over which one would wish to compute a descriptor. 
     In step S 21 , a three-dimensional matrix, Φ, is constructed, whose elements, φ pqr , represent the azimuthal angle of the position of each element in a spherical coordinate system centered on the central element of the matrix, the matrix elements being implicitly assigned spatial locations which are the row column and slice plane numbers of the matrix. The dimensions of matrix Φ should be of the same size as D. 
     In step S 22 , a three-dimensional matrix Θ, is constructed, whose elements, θ pqr , represent the polar angle of the position of each element in a spherical coordinate system centered on the central element of the matrix, the matrix elements being implicitly assigned spatial locations which are the row column and slice plane numbers of the matrix. The dimensions of matrix Θ should be the same size as D. 
     In step S 23 , a set of complex, polar separable wavelet function prototypes are constructed, each being in the form of equation 2:
 
Ψ k ( d ,θ,φ)= d   n     k     −1   e   −a     k     d ( n   k −α k   d ) ·(cos( m   k θ)+ q   x  sin( m   k θ)) ·(cos( l   k φ) +   q   y  sin( l   k φ))  (2)
 
where the term ψ k  denotes a wavelet function; d n     k     −1 e −α     k     d (n k −α k d) is the radial distance component with radial distance d, the term (cos(m k θ)+q x  sin(m k θ)) is the azimuthal angle component with azimuthal angle θ, and the term (cos(l k φ)+q y  sin(l k φ)) is the polar angle component with polar angle φ, and where the terms q x  and q y  denote the unit quaternions and obey the rules q x   2 =q y   2 =q z   2 =−1, and q x q y =q z . The parameters of the kth wavelet functions are l k , m k , n k  and α k . In equation 2 the radial distance component has a non-linear weighting so as to have good localisation performance to a specific image region/patch around a keypoint. The radial distance component d n     k     −1 e −α     k     d (n k −α k d) represents a radial decay which tapers and is graphically illustrated in  FIG. 8   a . An alternative radial distance component could be d n     k   e −α     k     d  which is graphically represented in  FIG. 8   b.  
 
     These radial distance components restricts the descriptor outputs to pertain only to the neighbourhood around the keypoint. 
     Modify Prototype Wavelet Function 
     The parameters of n k &gt;1, α k &gt;0, and m k  (integer) and l k , integer, are modified so as to select a subset of descriptor wavelet functions to minimise the difference between evaluations of ψ k (d,θ,φ) at the locations defined by matrices D, Θ and Φ at each of the basis functions, referred to by index k and each member, j, of the set of J space-time eigenvectors determined using equation 3: 
     
       
         
           
             
               
                 
                   
                     α 
                     k 
                   
                   , 
                   
                     m 
                     k 
                   
                   , 
                   
                     n 
                     k 
                   
                   , 
                   
                     
                       l 
                       k 
                     
                     = 
                     
                       
                         
                           arg 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           min 
                         
                         
                           
                             
                               α 
                               k 
                             
                             , 
                             
                               m 
                               k 
                             
                             , 
                             
                               n 
                               k 
                             
                             , 
                             
                               l 
                               k 
                             
                           
                           
                             
                               v 
                               = 
                               0 
                             
                             , 
                             1 
                             , 
                             2 
                             , 
                             3 
                           
                         
                       
                       ⁢ 
                       
                         ⌊ 
                         
                           
                              
                             
                               
                                 Re 
                                 ⁢ 
                                 
                                   { 
                                   
                                     
                                       S 
                                       ⁡ 
                                       
                                         ( 
                                         v 
                                         ) 
                                       
                                     
                                     ⁢ 
                                     
                                       
                                         
                                           ψ 
                                           ^ 
                                         
                                         k 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           d 
                                           , 
                                           θ 
                                           , 
                                           
                                             ϕ 
                                             ; 
                                             
                                               n 
                                               k 
                                             
                                           
                                           , 
                                           
                                             m 
                                             k 
                                           
                                           , 
                                           
                                             l 
                                             k 
                                           
                                           , 
                                           
                                             α 
                                             k 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                   } 
                                 
                               
                               - 
                               
                                 ψ 
                                 j 
                               
                             
                              
                           
                           2 
                         
                         ⌋ 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     where
 
 S ( v )=δ( v )−δ( z− 1) q   x −δ( v− 2) q   y −δ( v− 3) q   z  
 
     Where ∥Re{S(v){circumflex over (ψ)} k (d,θ,φ;n k ,m k ,l k ,α k )}−ψ j ∥ 2  denotes find the square root of the sum of the squares of the function ƒ(n k ,m k ,l k ,α k )=Re{S(v){circumflex over (ψ)} k (d,θ,φ;n k ,m k ,l k ,α k )}−ψ j  evaluated at predetermined discrete locations of d, θ and φ for the candidate values of (n k ,m k ,l k ,α k ). Equation 3 is an exemplary search term, and finds any value of the terms α k ,m k ,n k ,l k  of the quaternion components so that the quaternion function matches most closely the current j th  eigenfunction. In this way, the parameters of the quaternion wavelet function can be tuned to match in the best manner the learned eigenfunctions whilst still retaining the attraction of an analytic description of the quaternion i.e. ease of specification and analytic invariance to a geometric transformations, such as rotation in the spatial plane and approximate invariance to rotation in the (2D+1) space-time direction. 
     Selecting a Modified Wavelet Function 
     A matching criteria is applied to the plurality of modified wavelet functions in order to compare each of the modified wavelet functions with each of the at least one generated basis functions. Using the matching criteria, e.g. Euclidean distance, at least one closest matching modified wavelet function is selected for each of the number of the plurality of generated basis functions. This yields J sets of 4 parameters α k ,m k ,n k ,l k , one set of 4 parameters for each value of J. These  4 J parameters are used to construct J quaternion wavelet functions. An example of the four components of one such quaternion wavelet function is shown in the  FIG. 9 . Note that each wavelet function is a three dimensional quaternion function defined over an N x ×N y ×N t  grid. 
     Generate Keypoint Descriptor 
     In embodiments of the invention, the keypoint descriptor is generated or constructed by taking a set of modified quaternion wavelet functions selected from the previous step and then calculating the inner product between each of the selected modified quaternion wavelet functions and the input image, for example each of the image patch sequences, or the orientation field, to be characterised. If J quaternion wavelet functions are generated, then the keypoint descriptor consists of J quaternion wavelet function coefficients, σr j . Due to the properties of the quaternion wavelet functions, the magnitude of each coefficient will have substantial invariance to rotation in the plane and to patch velocity, that is to say an invariance to a change of position of an image patch spaced over time. These wavelet function coefficients are placed into the elements of a descriptor vector to form the keypoint descriptor. 
     Performance of a three-dimensional descriptor may be compromised if the patch velocity becomes too high. The reasons are (i) the approximation of linear motion (conical space-time geometry) by a spherical geometry breaks down, and (ii) the degree of velocity-induced pixel blurring reduces the stability of the visual structure. Nevertheless, the descriptors generated using the present invention represent a significant improvement over the stability of single-frame descriptors under conditions of moderate patch velocities. 
     Generating a Keypoint Descriptor for Two Dimensions 
     Referring to equation 2 above it will be noted that d n     k     −1 e −α     k     d (n k −α k d) is the radial distance component with radial element d, the term (cos(m k θ)+q x  sin(m k θ)) is the azimuthal angle component with azimuthal angle θ, and the term (cos(l k φ)+q y  sin(l k φ)) is the polar angle component with polar angle φ. Therefore, in further embodiments of the present invention, if a keypoint descriptor is required to be generated for identifying an object in a single frame, for example a two-dimensional object in a two-dimensional image, only the radial distance component and the azimuthal angle component are required to be used. For such embodiments, the method described previously is modified accordingly; therefore the prototype wavelet function and the plurality of modified wavelet functions generated in this instance will comprise a radial distance component d and an azimuthal angle θ having the formula:
 
ψ k ( d ,θ)= d   n     k     −1   e   −α     k     d ( n   k −α k   d ) ·(cos( m   k θ)+ q   x  sin( m   k θ))
 
For such embodiments, examples of graphical representations of the wavelet functions are illustrated in  FIGS. 10   a  to  10   d  which provide depictions of steering and some invariance properties.
 
Identifying an Object in an Image
 
     In further embodiments of the invention, the keypoint descriptor generated according to the invention is used to process image data representing at least part of an image, such as an image patch, or a whole image, having an object for identification, to identify the object. Or, the descriptor&#39;s values may be used in different ways to aid patch recognition and characterisation. 
     An exemplary method for object identification in an image includes: 
     i) receiving image data representing at least part of an image having an object for identification; 
     ii) processing the image data to generate at least one keypoint descriptor representative of at least one keypoint of the image, for example using the technique described in the reference AA Bharath, N Kingsbury, “Phase Invariant Keypoint Detection”, 15 th  International Conference on Digital Signal Processing, DSP 2007, the contents of which is incorporated herein by way of reference; 
     iii) comparing the keypoint descriptor generated in the method of the present invention with the at least one keypoint descriptor generated in step ii); and 
     iv) determining if the at least one keypoint descriptor generated in step ii) matches the keypoint descriptor generated in the method of the present invention. 
     In exemplary embodiments, the comparing of step iii) above may be performed by using a calculated match metric. For example, similar to the matching of International patent application no. PCT/EP2007058547, the contents of which is incorporated herein by reference, the match metric may be based on a Euclidean distance, as is well known in the art. In accordance with the present invention, the Euclidean distance based match metric may be calculated between the keypoint descriptor generated in the method of the present invention and each keypoint descriptor generated in step ii). Each Euclidean distance based match metric calculated in step iii) in this way is thresholded using a threshold value that can for example be set by a user of image processing software. The threshold value is set for determining whether a keypoint descriptor generated in step ii) matches the keypoint descriptor generated in the method of the invention. For example, if the Euclidean distance based match metric between one of the keypoint descriptors generated in step ii) and the keypoint descriptor generated in the method of the invention has a value greater than the threshold, then it is determined that the keypoint descriptor generated in step ii) in question matches the keypoint descriptor generated in the method of the invention. Such a match indicates, with high probability, that part of the object for identification has been successfully identified. If, however, the calculated Euclidean distance based match metric is lower than the threshold, then there is no match, indicating that the target object has not been identified. If more than one Euclidean distance match metric is greater than the threshold, then the greatest Euclidean distance match metric may be taken as the closest match, indicating that the keypoint descriptor corresponding with the greatest Euclidean distance match metric best matches the keypoint descriptor generated in the present invention. At least one verification process may be applied also, to ensure that a match makes geometric sense. 
     In such a method of object identification, in accordance with embodiments of the invention, transformation parameters of the object in the input image or orientation field may be estimated from the keypoint descriptor generated in the method of the invention. For example, if one wishes to estimate the direction of object motion in three dimensional space, this is approximated for small velocities by taking the ratio of the different components of the quaternion σj corresponding to a wavelet function {circumflex over (ψ)} 1 (d,θ,φ;n k ,1,1,α k ). For example, if the components of this coefficient are represented in equation 4
 
σ 1 =σ+σ x   q   x +σ y   q   y +σ z   q   z   (4)
 
then the ratio σ z /σ y  gives the tangent of the angle φ, which is strongly related to the direction of the motion of the patch in space. Similarly, the tangent of the dominant angle of an elongated object may be estimated by taking the ratio σ x /σ. If desired, the latter may be used to replace the angle description of the prior art SIFT approach for 2D, though the SIFT technique has no analogue for the former.
 
     Alternatively, the magnitude of each quaternion coefficient may be used for matching. If a 5×1 space-time keypoint descriptor is represented as [σ 1 , σ 2 , σ 3 , σ 4, σ   5 ], then the rotation and motion invariant keypoint descriptor may be constructed as └|σ 1 |, |σ 2 |, |σ 3 |, |σ 4 , |σ| 5 ┘. This may be used for tracking or object recognition applications as described in International patent application No. PCT/EP2007058547 the contents of which are included herein by reference. 
     In further embodiments of the invention, the transformation parameters may be used to track a keypoint in subsequent frames such that further occurrences of the keypoint will have small changes to the transformation parameters from frame to frame. Such a tracking of keypoints can provide better estimates of overall object motion and rotation and also of keypoint stability. 
     The above embodiments are to be understood as illustrative examples of the invention. Further embodiments of the invention are envisaged. For example, other quaternion wavelet functions may be added or replaced based on considerations of performance and available computing resources. For example, if for a pair of selected modified wavelet functions, {circumflex over (ψ)} j=2 (d,θ,φ) and {circumflex over (ψ)} j=5 (d,θ,φ), the shapes of these wavelet functions (determined by pair of the 4-parameter sets) are found to be very similar, one of the wavelet functions may either be removed, or replaced by a different parameter set. Instead of applying the quaternion descriptor to the pixel values themselves, in an alternative embodiment, tolerances to illumination changes may be attained by applying the descriptor to the orientation dominance field described in patent application PCT/EP2007058547 the contents of which are included herein by reference. If this type of descriptor is selected, then the learning steps described above, the pixel values of the image should be replaced by its corresponding orientation dominance field represented as x and y components (preferably not real-imaginary representation). This method may also be used to generate keypoint descriptors that may be used to identify a three dimensional object in a three dimensional image. 
     Similar as with the case of SIFT descriptors known from the prior art, descriptor matching between descriptors computed in a captured image and those descriptors held in a database, in accordance with the present invention, can be made more efficient by utilising an inverted file structure (see journal article entitled “Video Google: Efficient Visual Search of Videos” by Sivic &amp; Zisserman, 2003, Department of Engineering Science, University of Oxford, the contents of which is incorporated by reference) to rank the most relevant descriptors and/or images contained in one or more databases before those that are less relevant. A preferred embodiment of this would incorporate TF-IDF (Term Frequency, Inverse Document Frequency) weighting and hierarchical clustering to generate the “visual words” necessary for such an approach (see journal article entitled “Scalable Recognition with a Vocabulary Tree” by Nister &amp; Stewenius, 2006, Department of Computer Science, University of Kentucky, the contents of which is incorporated by reference). 
     It is to be understood that any feature described in relation to any one embodiment may be used alone, or in combination with other features described, and may also be used in combination with one or more features of any other of the embodiments, or any combination of any other of the embodiments. Furthermore, equivalents and modifications not described above may also be employed without departing from the scope of the invention, which is defined in the accompanying claims.