Background to the Invention Scanners, that is devices that can capture an image and convert it into a unique set of electrical signals are well known. Similarly 3-dimensional (3D) scanning systems are known that can image an object to obtain 3D surface representations of the object. Fields of application of 3D scanning systems are varied and, for example, include medical imaging, reverse engineering, computer vision, and video and film production.

A known 3D scanning apparatus 101 is schematically illustrated in Fig. 1.

The known apparatus comprises a CCD video camera 102 and a laser light source 103 in a fixed geometric relationship. The target object 104 (in the example, a model human head) rotates on a calibrated turntable 105, a light stripe 106 is cast onto the object 104 that is to be imaged, and a single video frame is recorded for each incremental rotation. Assuming that a point on the surface of the target object can be determined with at least one pixel accuracy, the depth d or distance from the origin (at the centre of the lens) for each point on the surface is derived from trigonometric relationships. In other words a fixed relationship between the light source 103 and the CCD camera 102 allows depth estimation by triangulation for each point on the object's surface. Fig. 2 illustrates the apparatus of Fig. 1 in plan view and from this Figure the following relationship is derived:

where: f (bj) represents the distance from the centre of the lens in the X direction and is a function of the brightness b ; of pixel i (0 : 5 i < NR) and its immediate neighbours to the right and left (see equations 2 and 3 below) ; is a system constant representing the angle in the XZ plane between the laser beam and the Z-axis; NR is a system constant representing the number of pixels in a row; D is a system constant representing the distance in mm from the origin to the centre of the turntable; and S is a system constant estimated by an initial calibration using an object of known distance from the origin, and is an invariant for that particular sensor.

The definitions above for the system constants (, NR, S, D) are one of a number of ways in which the system invariants can be set, all of which require measurement of the relative positions of some apparatus components. During the scanning process, the only physical measurement required is that for the rotation angle of the turntable. This enables a set of vertical profiles of each scan, spaced out by an angle equal to the angular increments of the turntable to be visualised. The estimation of the rotation angle of the turntable is described below.

To permit apparatus 101 to provide accurate 3D images a sub-pixel estimator is required to detect the pixel having the highest brightness in a row of pixels and for outputting brightnesses to the left and right of that pixel. In this way it is possible to estimate the brightest spot position (and therefore the position of the stripe) with sub-pixel accuracy.

As is known to those skilled in the art a cross-section of a stripe's light intensity shows a Gaussian profile where the centre of the line is brighter than the edges. The accuracy of the depth estimation depends on how accurately the centre of the stripe can be estimated. Fig. 3 schematically illustrates part of a typical row of pixels 301 in the CCD, which sample brightness as a 256-level grey scale. If a single vertical stripe is projected, there will be a peak 302 with an approximately Gaussian profile 303 somewhere along that row.

The sub-pixel estimator for a CCD row gives the distance x (in pixels and fractions thereof) of a point from the start of a row. We have NR sample points (0, bo), (1, bi), (2, b2),, (NR-1, bNR-1) equally spaced one pixel apart along the row, each sample point with a brightness value between 0 and 255. The brightest sample is at point (n, bn), but that may not coincide with the exact centre of the stripe's Gaussian profile. The x-value of the centre of the stripe can be estimated to sub-pixel accuracy by the formula: Finally, 0, is the angle in the XZ plane measured at the centre of the CCD from the Z axis to the peak of the point with the highest brightness: 0 = arcsin x/d (4) In order for 3D images of objects or, in general physical entities, to be produced the apparatus of Fig. 1 forms part of an image acquisition system. The main processing functions and data flow of a typical image acquisition system are

schematically illustrated in Fig. 4. At 401 an object is scanned using a CCD camera to obtain a 2D image followed by filtering and thresholding. Following step 401, at step 402 the 2D point data is processed to detect the brightest pixels in each scan line of the CCD. Next, at step 403 (Sub-Pixel Estimator) the exact position of the pixel with highest brightness is determined with sub-pixel accuracy using Equation 2. Following step 403, at step 404 a 2D line profile is created comprising the set of 2D points forming a line (or lines) for each scanned frame.

Each point on this line corresponds to the same rotation angle of the turntable.

Following step 404, at step 405 the depth of each point on the line is estimated using Equation 1 and substantially at the same time the rotation angle of the turntable is also estimated as indicated at 406. At 407 the 2D lines are then put together, taking into consideration the rotation angle of the turntable to form a 3D surface. Finally at step 608 a 3D surface registration method is employed to fuse the 3D surfaces so obtained into a 3D model of the object being imaged.

Published references concerning geometric methods for the estimation of the rotation angle, rotation matrix and translation vector in rigid body transformations as developed by an inventor of the present invention are as follows : M. A. Rodrigues and Y. Liu, "On the Representation of Rigid Body Transformations for Accurate Reg-istration of Free Form Surfaces", Robotics and Autonomous Systems, an International Journal, Vol 968 (2002) 1-16.

This paper describes geometric properties of reflected correspondence vectors, RCV, for estimation of rotation angle, rotation matrix and translation vector; and Y. Liu and M. A. Rodrigues, "Geometric Understanding of Rigid Body Transformations", 1999 IEEE In-ternational Conference on Robotics and Automation, ICRA'99, Detroit, Michigan, May 10-15,1999, pp 1275-11280.

This paper describes geometric properties of correspondence vectors, CV, for estimation of rotation angle, rotation matrix and translation vector.

The known apparatus of Fig. 1 suffers from many drawbacks in that although it is accurate and reliable its operation and calibration is time consuming. As well as being relatively expensive to purchase such apparatus of the type described is thus also expensive to operate. A further problem with the apparatus of Fig. 1 is that it is restrictive in that an object being imaged has to be positioned on the turntable. Many objects required to be scanned are not suitable for or are difficult to correctly mount on a turntable of the type described and larger objects may simply be too large to be accommodated by such systems.

An improvement upon the apparatus of Fig. 1 comprises a system that does not require a rotating turntable. Instead a scanning camera comprising the laser source and detector is used such that the geometric relationship between the two is known. By taking single stripe images in an indexed fashion (one after the other) as regards rotation of the camera relative to the object being imaged the relationship between the stripe image data obtained from one stripe to the next is known. In this way a 3D image can be built up of a surface. This kind of apparatus is expensive, and suffers from similar constraints to turntable type systems described above. In particular strict indexing is required to permit the resultant stripes to be correctly identified as regards their true relationship with each other.

In view of the problems associated with the aforementioned 3D scanning systems there is a need to provide improved methods, apparatus and systems for 3D imaging. In particular there is a need to build an imaging system that permits a free-form of imaging that is not restricted to use of an accurately rotating turntable or a rotatable indexed single stripe scanner camera. By free- form it is meant imaging a physical entity from a first angle or at a first orientation (i. e. with respect to a first coordinate frame) followed by imaging at a different angle or orientation (i. e. with respect to a second coordinate reference frame) wherein the relationship between the reference frames is unknown. The idea is to take multiple stripe images simultaneously in"one shot". Typically the orientation

of the physical entity with respect to the physical entity being imaged is changed (for example by moving the physical entity by hand) for obtaining two surface images, but alternatively the camera scanner may be moved relative to the physical entity. Such free-form imaging systems may utilise a substantially hand- held scanner camera or one that is mounted an a support that enables the field of view to be rotated in both a vertical and horizontal direction.

Free-form 3D imaging systems are known, but an important problem associated with such systems is the need to provide an accurate estimate of the rotation angle between a first 3D data set representing a surface region and an adjacent 3D data set of an overlapping surface region. An accurate estimate of the rotation angle is required so that the two imaged surfaces may be accurately registered. By surface registration it is meant fitting the surfaces together so as to provide a larger total surface. In this way an improved (more complete) model of the imaged physical entity is obtained.

. The general problem of registering 3D surfaces is summarised with reference to Figs. 5a and 5b.

Figure 5a schematically illustrates a register surface SR as a triangulated mesh of points a1, a2... a14... an which is to be rotated in three dimensions by a rotation matrix R and translated in three dimensions by translation vector t. The aim of the rotation and translation is to optimally align the mesh of points with a reference surface SF. Surface SF comprises a similar mesh of points b1, b2, b3... b14 (generally labelled bi) and surface SF comprises a region which overlaps with and corresponds to a region of surface SR. The basic problem is to find the rotation matrix R and the translation vector t which minimise the aggregate distances between a set of points of surface SR and their corresponding closest points on surface SF.

A conventional algorithm used for registration of 3D surfaces is the so- called Iterative Closest Point (ICP) algorithm, originated by Besl McKay (P. J. Besl

N. D. McKay. A Method for Registration of 3D Shapes. IEEE Transactions Pattern Analysis and Machine Intelligence, pages 239-256, volume 14, no. 2 February 1992). Besides the original ICP algorithm there have been many attempts at improving the basic ICP algorithm so as to provide faster and more reliable registration of 3D data sets.

In implementing the known ICP algorithm the following expression is to be minimised: where: N= number of points in the region of overlap and ai is the closest point on SR to bi.

Minimisation is achieved by assuming that the closest points correspond and then iteratively solving the above equation. In the above equation it is assumed that the sum of the squares of the distances is minimised to find Rt.

The effect of the operation of matrix R and vector t on surface SR is schematically illustrated in Fig. 6. The resultant aggregate distances dil d22, d33... di having been minimised.

Due to measurement inaccuracies the sum of the squares of the distances in the region of overlap is never optimised to zero and therefore in practice optimal surface registration is not achieved. The surfaces shown in Figs. 5 and 6 additionally illustrate that the 3D data sets to be registered are in fact more accurately described as point clouds as it will be appreciated by those skilled in the art.

Although ICP methods work in many applications they are known to fail in many situations. Thus, for example, if two surfaces to be registered are more

than about 35° of rotational distance apart (in terms of the angle from which each image is taken) then the ICP, is likely to give poor results as regards the quality of the match-up of the two surfaces. In addition the known ICP methods are generally computationally intensive since the closest point approach starts at an arbitrarily chosen guess at the closest point and then proceeds by searching for a closer value. In general the ICP approach is limited by one or more of the following factors: The algorithm is prone to local minima. Thus it requires initial alignment to be quite close and it is difficult to consistently reproduce similar results; The registration is susceptible to dis-alignment through erroneous data; and An optimal selection of points is very difficult to determine and to repeat.

This is so even though the performance of ICP algorithms can be optimised by sampling a specific subset of points from the su rface SR.

As already stated above various improved versions of the ICP algorithm are known to those skilled in the art. Thus, for example, registration may be based on applying a weighting factor that is proportional to the size of the triangle of the triangulated reference surface. Similarly registration may be based on matching of surfaces as well as points. Another modification involves introducing a weighting factor which takes into account the uncertainty in the positions of the points. However many of the improved ICP methods are known to suffer from one or more of: lack of convergence, inaccuracy or unstable behaviour.

In view of the above there is thus a need to improve 3D image processing methods, apparatus and systems. In particular there is a need to more accurately and reliably estimate the angle of rotation from one image data set to another so that image registration and 3D model building is made more reliable and accurate without having to rely on expensive and time intensive none free-form apparatus.

More generally there is a need to provide improved pattern recognition data processing methods and apparatus.

Summary of the Invention An object of the present invention is to provide an improved method and apparatus for processing 3D surface representations of physical entities.

Another object of the present invention is to provide a method and apparatus fro recognising a portion of a 3D image of a surface.

A further object of the present invention is to provide an alternative surface registration method to the known ICP based methods.

A further object of the present invention is to provide an improved method and apparatus for estimating the rotational position of a first 3D image data set of a physical entity with respect to a second 3D image data set of the physical entity.

Yet a further object of the present invention is to provide an improved method and apparatus for building a 3D model of an imaged physical entity through registering a plurality of 3D surface representations of the physical entity.

More generally, a further object of the present invention is to provide improved pattern recognition data processing methods and apparatus and in particular there is a need to provide improved methods and apparatus for processing image data wherein the image data comprises a first image data set representing a first surface and a second image data set representing a second surface, the surfaces having corresponding surface regions, the methods and apparatus directed to identifying a set of substantially corresponding surface features of the surfaces. This objective relates to recognizing same or substantially similar (overlapping) portions of imaged surfaces of a physical entity.

This objective also relates to selecting a surface feature configuration (pattern in

3D space) of an imaged surface of a first imaged physical entity and recognizing a substantially similar feature configuration in an imaged surface of a second physical entity.

Yet a further object of the present invention is to provide improved image processing methods and apparatus for use in fields of technology such as astronomy, medical imaging, reverse engineering imaging, and other fields where processing of multi-dimensional datasets is required including processing of 3D surface representations and processing o-f data sets of a higher number of dimensions.

Yet a further object of the present invention is to provide an improved method and apparatus for sub-pixel estimation including the providing of a data- provider for a sub-pixel estimator.

According to a first aspect of the present invention there is provided a method of processing image data, said image data comprising a first image data set representing a first surface and a second image data set representing a second surface, said surfaces having substantially corresponding surface regions, said method directed to identifying a set of substantially corresponding surface features of said surfaces, said method characterized by comprising the steps of: obtaining a feature vector processing template that is configured to structurally embody a plurality of surface feature vectors; embodying said processing template with a plurality of feature vectors selected from said first surface to thereby establish a configuration of feature vectors representing a portion of said first surface ; and searching for said representative configuration of feature vectors on said second surface;

wherein: said template is configured to embody said selected feature vectors in a structural configuration comprising a hinge part from which extend a plurality of said selected feature vectors.

Preferably said template is, prior to being embodied, substantially independent of the surface characteristics of said surface.

Preferably said hinge of said embodied template structural configuration comprises a feature vector in the form of a point selected from said first surface.

Preferably said template hinge is configured to enable a said feature vector to be oriented in substantially any direction from said hinge.

Preferably said feature vector processing template for structurally configuring a plurality of surface feature vectors is configured to arrange said feature vectors in the form of a polypod.

Preferably said polypod is in the form of a tripod.

Preferably a said selected feature vector comprises a direction of and a distance of a point on said first surface from said hinge.

Preferably all of said feature vectors of said embodied structural configuration define points on said first surface.

Preferably a said feature vector extending from said hinge comprises a primary feature vector configuration and a secondary feature vector configuration.

Preferably said secondary feature vector configuration comprises a polypod represented by a circle in 2D projective view.

Preferably said secondary feature vector configuration comprises a line in 2D projective view that is perpendicular to said primary feature vector.

Preferably said step of searching for said representative configuration of feature vectors on said second surface comprises the steps of: first, undertaking a search for a configuration of primary feature vectors to obtain a set of possible correspondences; and second, using a set of secondary said feature vectors to eliminate false matches.

Preferably said method is used to calculate a rotation matrix R relating said surfaces.

Preferably said method is used to calculate a translation vector t relating said surfaces.

Preferably said method is used to register said surfaces.

According to a second aspect of the present invention there is provided an image processing apparatus for processing a first image data set representing a first surface and a second image data set representing a second surface, said surfaces having substantially corresponding surface regions, said apparatus configured to identify a set of substantially corresponding surface features of said surfaces, said apparatus characterized by comprising: means for obtaining a feature vector processing template that is configured to structurally embody a plurality of surface feature vectors;

embodying means for embodying said processing template with a plurality of feature vectors selected from said first surface to thereby establish a configuration of feature vectors representing a portion of said first surface; and searching means for searching for said representative configuration of feature vectors on said second surface; wherein: said embodying means is configured to embody said selected feature vectors in a structural configuration comprising a hinge part from which extend a plurality of said selected feature vectors.

Preferably said processing template is, prior to being embodied by said embodying means, substantially independent of the surface characteristics of said surface.

Preferably said embodying means is configured to embody said hinge part in the form of a point selected from said first surface.

Preferably said embodying means is configured to enable a said feature vector to be oriented in substantially any direction from said hinge.

Preferably said means for obtaining said template is configured to obtain a template for structurally arranging a plurality of surface feature vectors in the form of a polypod.

Preferably said polypod is a tripod.

Preferably said embodying means is configured to enable selection of a feature vector comprising a direction of and a distance of a point on said first surface from said hinge.

Preferably said embodying means is configured to enable selection of said feature vectors of said embodied structural configuration such that they all define points on said first surface.

Preferably said embodying means is configured to embody said template with a primary feature vector configuration and a secondary feature vector configuration.

Preferably said embodying means is configured to embody a said secondary feature vector configuration in the form of a polypod.

Preferably said embodying means is configured to embody a primary feature vector of said primary feature vector configuration with a secondary feature vector configuration that, as viewed in 2D projective view, comprises a line that is perpendicular to said primary feature vector.

Preferably said searching means for searching for said representative configuration of said feature vectors on said second surface comprises means for performing the steps of: first, undertaking a search for a configuration of primary feature vectors to obtain a set of possible correspondences; and second, using a set of secondary said feature vectors to eliminate false matches.

Preferably said apparatus further comprises a rotation matrix calculation means to calculate a rotation matrix R relating said surfaces.

Preferably said apparatus further comprises a translation vector calculation means to calculate a translation vector t relating said surfaces.

Preferably said apparatus further comprises a surface registration means configured to register said surfaces.

According to a third aspect of the present invention there is provided a computer program configured to be run on a data processing apparatus to perform a method as claimed in any of claims 1 to 15 appended hereto.

According to a fourth aspect of the present invention there is provided a 3D imaging system configured to perform any of the methods as claimed in any of claims 1 to 15 appended hereto.

According to a fifth aspect of the present invention there is provided a 3D imaging system comprising any of the apparatus as claimed in any of claims 16 to 30 appended hereto.

According to a sixth aspect of the present invention there is provided, for a first data set representing a first N-dimensional surface and a second data set representing a second N-dimensional surface, said data sets having substantially corresponding N-dimensional surface regions, a method of processing said data to identify a set of substantially corresponding surface features of said N- dimensional surfaces, said method characterized by comprising the steps of: obtaining a feature vector processing template that is configured to structurally embody a plurality of feature vectors; embodying said processing template with a plurality of feature vectors selected from said first surface to thereby establish a configuration of feature vectors representing a a portion of said first surface; and

searching for said representative configuration of feature vectors on said second surface; wherein: said template is configured to embody said selected feature vectors in a structural configuration comprising a hinge part from which extend a plurality of said selected feature vectors.

According to a seventh aspect of the present invention there is provided an image processing apparatus for processing a first image data set representing a first N-dimensional surface and a second image data set representing a second N-dimensional surface, said surfaces having substantially corresponding surface regions, said apparatus configured to identify a set of substantially corresponding surface features of said surfaces, said apparatus characterized by comprising: means for obtaining a feature vector processing template that is configured to structurally embody a plurality of surface feature vectors; embodying means for embodying said processing template with a plurality of feature vectors selected from said first surface to thereby establish a configuration of feature vectors representing a portion of said first surface; and searching means for searching for said representative configuration of feature vectors on said second surface; wherein: said embodying means is configured to embody said selected feature vectors in a structural configuration comprising a hinge part from which extend a plurality of said selected feature vectors.

According to an eighth aspect of the present invention there is provided a method of processing image data, said image data comprising a first image data set representing a first surface and a second image data set representing a second surface, said surfaces having corresponding surface regions, said method directed to identifying a set of corresponding surface features of said surfaces and comprising the steps of: selecting a feature vector processing template having a predefined shape; embodying said processing template with a plurality of feature vectors selected from said first surface; in accordance with said embodied processing template defining a configuration of feature vectors on said first surface; and searching for and identifying said configuration of defined feature vectors on said second surface; wherein: said template shape is configured to embody said feature vectors in a structural configuration comprising a hinge part from which extend a plurality of said feature vectors.

According to a ninth aspect of the present invention there is provided an image processing apparatus for processing a first image data set representing a first surface and a second image data set representing a second surface, said surfaces having corresponding surface regions, said apparatus configured to

identify a set of corresponding surface features of said surfaces, said apparatus comprising : selection means for selecting a feature vector processing template having a predefined shape; embodying means for embodying said processing template with a plurality of feature vectors selected from said first surface; means for defining a configuration of feature vectors on said first surface in accordance with said embodied processing template; and searching means for searching for and identifying said configuration of defined feature vectors on said second surface; wherein: said embodying means is configured to embody said feature vectors, in accordance with said template shape, in a structural configuration comprising a hinge part from which extend a plurality of said feature vectors.

Brief Description of the Drawings For a better understanding of the invention and to show how the same may be carried into effect, there will now be described by way of example only, specific embodiments, methods and processes according to the present invention with reference to the accompanying drawings in which: Figs. 7 (a)- (c) schematically illustrate a preferred embodiment of a configuration of feature vectors r and w and their corresponding projections s and v in the plane V. A set of three such vectors (r, w) form a tripod as configured in accordance with the present invention;

Figs. 8 (a) and 8 (b) schematically illustrate usage of the tripods (a set of three vectors (s, v) in the projective plane V) of Figs. 7 (a)- (c) for feature extraction; Fig 8 (b) illustrates a tripod fitted to a model of a human face; Fig. 9 further details the components of a configuration of feature vectors as configured in accordance with a preferred embodiment of the present invention; Fig. 10 illustrates schematically a tripod of the type illustrated in Fig. 7 (a) to Fig. 9 as fitted to an arbitrary surface; Fig. 11 schematically illustrates a further preferred embodiment for the feet portions of a configuration of principal feature vectors in the form of a tripod; Fig. 12 schematically illustrates a further preferred embodiment for configuring the feet portions of feature vectors; Fig. 13 further details the embodiment of feet of the type shown in Fig. 12; Fig. 14 schematically illustrates, in 2D projective view, a further example of a polypod configuration in the form of a quadpod; and Fig. 15 schematically illustrates an improved data provider configured to more efficiently providing data to a sub-pixel estimator of the type described in relation to Figs. 3 and 4.

Detailed Description There will now be described by way of example a specific mode contemplated by the inventors. In the following description numerous specific details are set forth in order to provide a thorough understanding. It will be apparent however, to one skilled in the art, that the present invention may be practiced without limitation to these specific details. In other instances, well

known methods and structures have not been described in detail so as not to unnecessarily obscure the description.

The methods of the present invention and apparatus or systems embodying the methods allow reliable and accurate 3D model building through an image registration method that is not based on the aforementioned ICP algorithm. It is assumed that 3D surfaces, such as in the form of surface data files comprising the relevant depth information for each point, are provided. The surfaces that are the subject of matching-up substantially similar or identical patterns of surface feature vectors and/or surface registration and/or rotation estimation may be obtained from a variety of methods such as free form-imaging or the more restrictive turntable or indexed single stripe imaging camera devices previously discussed.

Preferred embodiments of the present invention are described below in relation to two imaged surfaces obtained using a turntable type 3D imaging system which is useful for explanatory purposes in terms of the orientations of images being processed. However the invention pertains to matching two 3D surfaces however obtained or provided. The surfaces may thus be of a real imaged physical entity or they may be computer generated in some way.

Although in one aspect the present invention relates to various methods for processing images, it also concerns image processing apparatus and systems embodying the methods. Thus, for example, in a preferred embodiment the invention comprises an image processing apparatus for processing a first image data set representing a first surface and a second image data set representing a second surface, the surfaces having substantially corresponding surface regions, the apparatus configured to identify a set of substantially corresponding surface features of the surfaces and the apparatus characterized by comprising: means for obtaining a feature vector processing template that is configured to structurally embody a plurality of surface feature vectors;

embodying means for embodying the processing template with a plurality of feature vectors selected from the first surface to thereby establish a configuration of feature vectors representing a portion of the first surface; and searching means for searching for the representative configuration of feature vectors on the second surface; wherein: the embodying means is configured to embody the selected feature vectors in a structural configuration comprising a hinge part from which extend a plurality of the selected feature vectors.

3D Model Building Through Surface Registration In order to build a more complete 3D model of an object, first a set of depth profiles are determined as described above by rotating the object by at least 360° about a line parallel to the Y axis (for normal rotation of the turntable, the direction of rotation is not important). Each value d in the depth profile has corresponding (x, y, z) coordinates so that a full 3D representation is obtained for each profile : x is estimated by Equation 2; y is the number of pixels in the Y direction of the point on the surface corresponding to the depth d. Unlike the sub-pixel accuracy that is obtained in the X direction, here the accuracy is limited to one pixel. z is estimated as follows. First, project d onto the XZ plane using angle y (defined below) and then project it again onto the Z axis using angle 0 (defined by Equation 4):

=arcsiny/d, z=dcosvcosO (5) All profiles put together yield a point cloud representing the surface of the object. Thus, each point is a vector pi and we call this the set of image data P = { p1, p2, ###, pn1}. The object is then rotated by about 90° either around the X or Z axis (that is, the object is placed on its side on the turntable) and the above procedure for depth profile estimation is repeated. This will result in another set of image data P'= {P'1, p'2,"-, P'n2}.

Both sets of image data (P, P') represent imaged surfaces of the same physical entity. The data sets may be real image data sets of a physical entity in the real world or they may be computer generated. The matching of and subsequent registration of these two surfaces will yield a fuller, that is a more complete, 3D model. The procedure is summarised as follows : 1. determine a set of feature vectors on the first image P using the projective tripod method described below ; 2. apply the image matching method described below by searching for the same set of feature vectors on the second image P'. When a match is encountered within a specified error threshold, then the images can be registered; and 3. If the images are to be registered then utilise the determined match information to estimate the transformation parameters rotation matrix R and translation vector t and then fuse the two surfaces into a single 3D model.

The Projective Tripod Method for Feature Vector Extraction In accordance with a preferred embodiment of the present invention, definitions for the Projective Tripod Method are illustrated in Figs. 7 (a) -7 (c).

Consider Fig. 7 (a). Assume V c 91 3 is a subspace, r C 913 (r is a member of the set R3) and s # V has the property that u = r-s C V. In this definition, V# is the orthogonal complement of V : V# = {u # R3: u#s=) for every s # V}.

The set of feature vectors s # V is defined by the projections of feature vectors r e B3 onto subspace V. Now consider Fig. 7 (b). In this case, s # V and v C V and s v = 0 for every s 6 V. Finally, consider Fig. 7 (c). In this case, r # R3, w # R3, s # V, v # V, and s and v are the projections of r and w onto V.

Figs. 8 (a) and 8 (b) schematically illustrate the projective tripod method for surface feature extraction.

In Fig. 8 (a) the projective tripod is defined in the plane V by si (i = 1,2, 3) equal length, equally spaced out principal vectors (si are the projections of vectors ri onto V) and a number of secondary vectors v (j = 1,2,..., n) perpendicular to si where v are the projections of wj onto V. Fig. 8 (a) depicts a subspace V # 913 where the set of principal feature vectors si form a tripod hinged at their origin, each with internal angle 0 = 120°. The secondary feature vectors vj are also defined in the planar subspace V. The principal feature vectors are the projections of vectors ri # R3 onto V and the secondary feature vectors are the projections of vectors wi # R3 onto V.

The set of vectors ri and wj are depicted in Fig. 8 (b) on the surface of the image object, a model of a human head 801. Note that all vectors, including the

tripod origin 0 are defined on the surface of the object. Normally, if the object's structure is complex enough, the length of the vectors w, in general, will not be equal (i. e. fi 0 r2 0 r3) and the length of all sets of vectors w are also not necessarily equal. Defining a set of feature vectors F as the set of vectors ri and corresponding vectors wij : F = {ri, wij # i = 1, 2, 3 and j = 1, 2, ###, n}, the registration task is then to map the vector set {rj, wj} from one image onto another: from P onto P'.

Unlike the ICP based methods the method of the present invention, in the best mode contemplated, makes use of the actual file structure of a scanned surface as follows. When an object is scanned, all pixels as seen by the CCD are processed and the depth of each pixel is estimated. Some of these pixels will fall outside the object or are unresolved in terms of depth estimation and the resultant vertices (x, y, z) of all such pixels are marked as invalid. An array is defined which contains all vertices, valid and invalid, placed in a rectangular grid corresponding to the original CCD image. This array of vertices corresponds to a projective image and the configuration of vectors will be placed over this array such that the vectors are defined over valid vertices. This immediately guarantees that the configuration fits or is"adjusted"to the surface within threshold distances to the nearest points and, from this viewpoint, all vectors are defined as same length straight line segments (although they bend around the surface). Also, it allows one to exploit properties of neighbouring points for fine registration such as the shape of each configuration vector as it adjusts itself to the surface.

Implementations of ICP that are known to the inventors of the present invention do not use such constraints and resultant processing is more open ended in terms of the accuracy and efficiency of the pattern recognition being undertaken.

I n contrast to the known ICP methods the present invention therefore enables the required pattern recognition to be realised more accurately and efficiently.

Fig. 9 schematically illustrates a two dimensional projective view (projected onto a plane) of a preferred embodiment of a tripod as configured in accordance with the present invention. Tripod 901 comprises a hinge point 902 about which extend three primary feature vectors 903 to 905 respectively. Feature vectors 903,904 and 905 may be configured as elongate legs extending from central hinge point 902. In the preferred embodiment the legs 903,904 and 905 are all identical in length. However the invention is not to be considered as limited to equal length legs and it is possible to utilize a configuration of primary feature vectors such that they are not all of the same length. As can be seen from Fig. 9, in the preferred embodiment the angle from one leg to the next is, in 2D, 120° and thus the legs are equally spaced. In use the tripod is placed upon a point cloud representing a three dimensional surface and the end points of legs 903, 904, and 905, respectively labelled 907,908 and 906 are placed upon the surface together with the central origin point 902 also being placed upon the surface. The contact points on the surface where the tripod touches may be considered to all constitute the feature vectors to be used as a search configuration or signature to be searched for on the second surface. It is the relationship of the points to one another in terms of orientation, direction and distance of the end of the extending feature vectors relative to the origin point that embodies the required signature information to be searched in the surface matching process. Thus upon the tripod being placed on, that is fitted to, a three- dimensional first or reference surface it acquires a three dimensional shape.

Following projection of the two dimensional tripod onto a three dimensional surface the length of the legs are configured to contract or lengthen depending on the fit of the tripod to a particular portion of the surface selected. In the embodiment of Fig. 9 the end points of the primary feature vectors, that is points 906,907 and 908 at the opposite end to the hinge point, are configured as single points. Points 906,907 and 908 may conveniently be termed the"feet"of the respective principal feature vectors and represent points on the reference surface. By points it is meant actual image data points (or interpolations thereof) that represent particular positions on a given surface.

Fig. 10 schematically illustrates tripod 901 having been obtained and fitted to a 3D surface as indicated at 1001. The surface is generally indicated at 1002, by a series of broken contour lines. The tripod 901 is shown as touching the surface at its central point and also at the positions of its feet 906,907 and 908.

In this example it can readily be seen that principal feature vector 908 has been lengthened, but in general the principal feature vectors may lengthen, contract or remain the same length as regards projection from the 2D representation to a 3D fitted representation. It is the nature of the fit under consideration, that is the configuration of the particular surface portion to be searched for, that determines the dimensions and/or orientations of the principal feature vectors in the 3D representation.

Fig. 11 schematically illustrates a further preferred embodiment, as a 2D projection, for the feet portions (secondary feature vectors) of a tripod type configuration of primary feature vectors. The tripod illustrated in Fig. 11 comprises a central hinge point 1101 about which extends a series of legs. At the ends of the legs there are feet configured in the form of a line. Each foot 1102-1104 comprises a line that is perpendicular to the leg to which it is attached.

By a line it is meant a secondary feature vector configuration that extends from the hinge point represented by the end point of the principal feature vector. The embodiment illustrated actually comprises two secondary extending feature vectors each extending away from the hinge point located at the attaching end of the principal vector (the hinge point itself being a feature vector of the secondary configuration). The term"configuration of secondary feature vectors"is however to be construed as including one or a plurality of secondary feature vectors. In the present disclosure the term secondary feature vector is used interchangeably herein to mean either a whole configuration of a foot or a part thereof, the precise meaning in each case being evident from the particular context.

Feet configured in the form of a line are considered to provide a better basis for matching a tripod that is being fitted to a second surface. This is because feet configured in the form of a line offer a higher degree of accuracy as

regards the search than do straightforward point-type feet of the type illustrated in Fig. 9 and 10. However, the inventors have found that the optimum configuration for the feet is, in a 2D projective view, a plurality of secondary feature vectors that extend from the point of attachment to the primary feature vector to the circumference of a circle. A tripod configured with such feet is schematically illustrated in Fig. 12 with origin 1201 and feet 1202-1204 respectively. In this way the hinge point of the secondary feature configuration is located within the circle, at its centre, as is schematically illustrated in Fig. 13. In this arrangement the secondary feature vectors (in common with the primary feature vectors that depend from the principal hinge feature vector) therefore take on the appearance of the spokes of a bicycle wheel extending circumferentially from an axle.

In the preferred embodiment the primary feature vectors are configured via a feature vector processing template in the form of a tripod arrangement, but those skilled in the art will realise that various other configurations may provide the desired degree of accuracy required in the surface matching process. Thus, for example, a more complex geometrical structure than a tripod of the type described above could be used. For example a substantially similar structure to the aforementioned tripod could be constructed that has a greater number of legs than three. Thus if four such legs are utilized then a"quad-type"geometrical structure would be realised (called herein a"quadpod") which may offer a higher degree of accuracy as regards initial registration than the use of a structure comprising only three feature vectors. A quadpod is schematically illustrated in 2D projective view in Fig. 14. Quadpod 1401 comprises a central hinge point feature vector 1402 from which extend four principal feature vector legs 1403- 1406 respectively. Unlike the triangles forming the mesh in ICP methods (see Fig.

5 and 6) which are essentially 2 dimensional entities the polypods of the present invention rnay form shapes having 3 dimensions in 3D virtual space. As regards the ICP triangles all vertices of a triangle are connected and thus the shape is a closed shape. The connection of one triangle to the next about two adjacent edges may be considered to constitute a hinge in that it is the relative orientation angle of each triangle from the hinge that essentially constitutes a surface

feature. In contrast the polypods configured in accordance with the present invention may be considered to comprise an open shape that is much more versatile. By defining or obtaining a particular polypod template, such as for a tripod shape, then the template can readily be embodied with feature vector data derived from actual surface data and the template may be used in respect of any surface of interest.

Those skilled in the art will appreciate that the invention is not to be considered as limited to any particular number of principal feature vectors and in principle any number of principal feature vectors may be used. In general a configuration of principal feature vectors comprising a plurality of feature vectors arranged about a hinge-like origin may thus be termed a"polypod".

Notwithstanding the fact that a principal feature vector configuration may comprise 2,3, 4,5 or more such feature vectors arranged about a hinge the inventors have found that usage of a feature vector configuration comprising three principal feature vectors extending from a hinge which itself constitutes a surface feature vector provides adequate results in most circumstances. A tripod configured in this way is considered to represent the best mode contemplated and comprises four points that locate with a given reference surface to be matched to a second surface. Using at least four principal feature vectors in this way is found to provide good results with most types of complex surfaces that are the subject of processing in real applications of the technology. However for certain more simple surfaces an embodiment comprising only the hinge point principal feature vector plus two feature vectors arranged therefrom may yield desirable results.

The tripod type configuration of principal feature vectors described is, as mentioned above, to be construed as an example of a more general set of shapes termed"polypods". Since a feature vector configuration is strictly an operator for application with respect to a series of points in space the"shape"is that which subsists in the virtual world although appropriate processing and display means may be configured to represent actual configurations in use in

relation to the particular surfaces under consideration. The general form of such a shape comprises a hinge-like attachment point (or more generally a hinge region) from which extend a plurality of principal feature vectors. The set of principal feature vectors represented by the configuration comprises the vectors arranged about the hinge and the hinge itself. Thus in the tripod example four such principal feature vectors are provided for fitting to or on a given surface. A particularly desirable quality exhibited by a polypod type of configuration is that a hinge is present. In the preferred embodiment the hinge constitutes a feature vector, but other configurations of polypods may be contemplated such as a quadpod wherein the hinge is not configured as a feature vector in that it is not required to be applied to a surface.

Desirable characteristics of a general feature vector configuration that may be used in relation to a wide variety of complex surface types is that it should: be configured in the form of a general template that may then be specifically configured for use in respect of particular surfaces to be processed; and 'comprise a structure that enables the specific feature vectors selected from a particular surface to be readily embodied upon the template.

The polypod configuration comprises a hinge point which by mechanical analogy may be considered to represent a ball-joint. In the best mode the hinge comprises a point in space that allows full 360° rotation in all planes passing through the point. In this way the principal feature vectors may be oriented in any specified spatial direction from the hinge. The full rotational freedom embodiment may be considered to represent total spherical rotational freedom about the hinge. A fully rotational hinge like structure enables the principal feature vectors to be specified in respect of all sorts of complex surface shapes. In other words the feature vectors can be made to fit to, for example, convex surfaces, concave surfaces and more complex surface shapes comprising a mixture of the two.

Although a rotational characteristic of permitting 360° rotation in all planes is considered to represent the best mode it will be appreciated that lower degrees of rotational freedom may find useful application in many situations. In particular a degree of rotational freedom restricted to just one hemisphere of the space about a hinge may be used successfully in relation to many surfaces that are processed in practice. The important point is that the general template used by a particular surface-image processor must be provided with enough rotational freedom to accommodate (i. e. correctly specify) the principal feature vector values that are obtained from a given reference image to be registered. Also each principal feature vector leg (sub-template) of the template should, in the preferred embodiments of the invention, be rotatable freely of the other sub-template legs.

In other words rotation of a leg sub-template should not be constrained, that is tied to in some way, the rotation of another leg. Finally it will be appreciated that these considerations are all generally applicable to the configuration of the secondary feature vector configurations. In particular those skilled in the art will appreciate that the circle type embodiment of a foot described above is basically configured in the form of a polypod. Thus, for example, a tripod type template structure may be employed to embody a principal feature vector configuration and similarly a tripod type template structure may be employed to embody a secondary feature vector configuration.

The Projective Tripod Registration Method The method is based on a coarse to fine strategy. The method now described is by way of example and represents a preferred embodiment. Various modifications may be made as regards the configuration of the feature vector configurations defined so as to arrive at different, but equally viable processing routines.

First, from the projective plane principal vectors si define the set of vectors ri on the first image. Then on the second image, find the corresponding vectors ei

followed by a refinement of the match by using the set of secondary feature vectors wij and finding their corresponding w'ij.

The algorithm described below uses geometric properties of correspondence and reflected correspondence vectors (as described in the two papers by Rodrigues referenced earlier in the section entitled"Background to the Invention"and incorporated herein by reference) to estimate the rotation axis h, the rotation angle 0, the rotation matrix R and the translation vector t of the transformation. The transformation (R, t) is used to register image data sets (P, P') when a match is found for the projective tripod in image P'.

Coarse Registration of Surfaces (using tripod feature vectors ri) A coarse registration of surfaces may be achieved using only the principal feature vectors defined above as follows : 1. Set a threshold p specifying the desired accuracy of the registration. On the image plane V (the image plane of the CCD), choose a constant length L for principal feature vectors si, where i = 1,2, 3. Choose the origin 0 on the first image (the centre of the image plane is a good choice) and determine vector po (the origin of the tripod on the object's surface), and vectors pij = {rj, wij}, where j = 1, 2,---ni. In the best mode contemplated the selected length L is the same for all the principal featu re vectors se. However the invention is not to be construed by those skilled in the art as limited in this respect since the invention may be configured to operate by using principal feature vectors si that are of different lengths.

2. Determine a starting point on the second image (or origin) defined as vector p'o. Calculate the distance to p'o for all other points in the image and sort vector points in ascending order of distances P$soned = {P'k | k = 1, 2, , n2}.

Setk=0.

3. Set k # k + 1. If k # n2 then set origin p'0 = P'k. From the origin and for each point p'j (j =1, 2,---, ni) in P'determine a set of vectors with the same length as vectors (ri, r2, r3). As a result, a set of possible correspondences (po, p'o) and (ri, r'i) (i = 1,2, 3) for such point vectors is obtained.

4. Eliminate false matches by comparing, from the origin p'o, the direction and orientation of vectors r'j with ri This leads to a set of refined set of possible correspondences ("po,"p'o) and (#ri, #r'i) (i = 1,2, 3).

Fine Registration of Surfaces (using tripod feature vectors w ; j) The accuracy of the registration may be improved by also utilising a set of secondary feature vectors in a matching process: 5. For each point-p'j (j = 1, 2, ###, m1) in P'determine a set of vectors with the same length as vectors (wiz, W2j, w3j), j = 1, 2, ###, m2 so that possible correspondences (w1j, w'ij), (w2j, w'2j) and (wsj, w'3j) for such point vectors is obtained.

6. Eliminate false matches by comparing the direction and orientation of vectors w'ij with wij. This leads to a refined set of possible correspondences (#wij, #w'ij) where (i = 1,2, 3) and (j = 1, 2,---, m3).

7. Update the motion parameters rotation matrix R and translation vector t based on the refined correspondences (#p0, #p'0), (#ri, #r'i), (#wij, #w'ij).

8. Register the two images by applying the transformation parameters to each point pi : p'i = Rpi + t (6) where (pi # P).

9. Compute the relative error e of the registration of set of points P'with the set of points p'i evaluated by Equation 6 and compare the error with the parameter p.

If c : 5 p then the algorithm terminates and the two images are fused together.

Otherwise, use the next set of refined correspondences and resume from step 7 or re-start from step 3.

Data Provider for Sub-Pixel Estimator As will be understood by those skilled in the art the sub-pixel estimator described in relation to Fig. 4 is known to be implemented as part of a software package. However in the best mode contemplated the data provider for the sub- pixel estimator may, in accordance with an aspect of the present invention, be implemented in hardware for applications where high processing speeds are required to produce results in real-time.

In accordance with an aspect of the present invention a preferred circuit 1501 is schematically illustrated in Fig. 15. Circuit 1501 detects the pixel of highest brightness in a row of pixels and outputs a composite signal comprising a number of data bits representing the peak sample value on that horizontal line and the four adjacent sample values, a number of data bits representing the number of samples counted between the start of the line and the peak sample, and a single bit representing the low period of the horizontal synchronising pulse of the video signal, which gives the period when the above data is true. The device allows fast data acquisition by directly providing formatted data for estimation of the centre of the brightest spot with sub-pixel accuracy.

Device 1501 provides a set of data bits related to the pixel with highest brightness in a row of pixels. This device inputs a Composite Video Signal of 1 volt p-p, and outputs the following logical data for each horizontal video line : 1.5 x 8-bit data bytes representing the peak sample value on that horizontal line and the four adjacent sample values ; 2.1 x 16-bit data word representing the number of samples counted between the start of the line and the peak sample ; and 3.1 single bit representing the low period of the horizontal synchronising pulse of the video signal, which gives the period when the above data is true.

This data will be used to estimate the centre of a Gaussian peak within each horizontal line. Circuit 1501 provides an improvement over prior art methods which either use video capture devices that present a large, unwanted amount of data per line, or employ analogue threshold detectors which cannot be resolved to a high resolution.

The methods of the present invention may also find useful application in processing higher dimension data sets than three dimensional image type data.

Data sets comprising greater than three dimensions (N>3) may therefore be processed using suitably configured polypod operators to determine particular features of the data. In this way an N-dimensional data set may be processed.

To maintain terminology in relation to the three-dirnensional example given above, processing may thus be considered to apply to"N-dimensional"surfaces although it will be understood by those skilled in the art that the term"surface" used in this respect is merely by analogy and such N-dimensional data sets could be described using other more appropriate terminology.

Although the methods and apparatus of the present invention have been described in relation to imaging systems employing visible light, such as structured light systems, the methods and apparatus are also to be considered as useable in a wide variety of other imaging methodologies. Thus those skilled in

the art will realise that the present invention is applicable to imaging using a wide variety of radiations including electromagnetic radiations such as x-rays and other forms of radiation such as ultrasound. The image processing methods and apparatus are potentially useful in many forms of imaging that use a detector to detect an emitted radiation source. The example of using a CCD camera and a light source is merely one example of many to which the methods of the present invention are considered to find commercial use. Similarly as regards visible light systems a laser source and a CCD video camera are merely examples of suitable radiation sources and detector arrangements that may be used in an image processing method and apparatus for imaging using visible light. The methods and apparatus described herein are considered to find a wide variety of application in industry, medical imaging and various other imaging fields such as in computer vision.