System and method for “Stitching” a plurality of reconstructions of three-dimensional surface features of object(s) in a scene defined relative to respective coordinate systems to relate them to a common coordinate system

[0002] This application is a continuation in part of U.S. patent application Ser. No. 08/989,047, filed Dec. 11, 1997, in the names of Dan Albeck, et al., and entitled “Apparatus And Method For 3-Dimensional Surface Geometry Reconstruction,” assigned to the assignee of this application

[0003] U.S. patent application Ser. No. 08/497,224, filed Jun. 30, 1995, in the name of Amnon Shashua, and entitled “Apparatus And Method For Recreating And Manipulating A 3D Object Based On A 2D Projection Thereof,” assigned to the assignee of this application, incorporated by reference.

[0004] U.S. patent application Ser. No. 08/989,047, filed Dec. 11, 1997, in the names of Dan Albeck, et al., and entitled “Apparatus And Method For 3-Dimensional Surface Geometry Reconstruction,” assigned to the assignee of this application, incorporated by reference.

[0005] This application relates generally to the field of reconstructing and/or manipulating surface geometries of one or more three dimensional objects in a scene, from a plurality of two dimensional images of the scene. The application more particularly relates to reconstruction and manipulation of such surface geometries of the object(s) as determined from a plurality of sets of two-dimensional images, each image set facilitating the reconstruction and/or manipulation of a predetermined portion of the surface geometries of the object(s) in the scene, with the plurality of image sets facilitating the reconstruction and/or manipulation of respective portions of the surface geometries of the object(s) in the scene.

[0006] Reconstruction and/or manipulation (generally, “reconstruction”) of surface features of three-dimensional object(s) in a scene, from a plurality of two-dimensional images of the object(s), is useful in a number of applications. U.S. patent application Ser. No. 08/989,047, filed Dec. 11, 1997, in the names of Dan Albeck, et al., and entitled “Apparatus And Method For 3-Dimensional Surface Geometry Reconstruction” (hereinafter referred to as the “Albeck application”) describes an apparatus for performing such reconstruction using a rig of three cameras, using a tensor arrangement described in U.S. patent application Ser. No. 08/497,224, filed Jun. 30, 1995, in the name of Amnon Shashua, and entitled “Apparatus And Method For Recreating And Manipulating A 3D Object Based On A 2D Projection Thereof” (hereinafter referred to as the “Shashua application”) to generate information regarding reconstruction for the features of the object(s) from three images generated by the cameras. In the arrangement described in the Shashua application, the surface features that are reconstructed are defined by points that have coordinates in a coordinate system relative to one of the cameras in the rig. A problem arises in reconstruction if the surface features that are to be reconstructed cannot all be recorded by all of the cameras with the rig in one position. The apparatus described in the Albeck application provides a mechanism for moving the rig so as to allow the cameras to record sets of images of various portions of the surface(s) of the object(s). However, when the rig moves from one location, in which the cameras record a set of images of one portion of the object(s), to another location, in which the cameras record another set of images of another portion of the object(s), the coordinate system for the points defining the surface features of the various portions of the object(s) also changes.

[0007] In order to utilize the reconstruction information generated in the two coordinate systems in a unitary manner in connection with the object(s) in the scene, it is necessary to relate the coordinate systems to a common coordinate system, which will allow all of the points of the various portions of the reconstructed object(s) to be related to the common coordinate system, effectively “stitching” the reconstructions together. The common coordinate system can conveniently be one of the two coordinate systems used in reconstruction, or it can be a third coordinate system, but in any case all of the points for the various portions of the reconstructed object need to be related to a common coordinate system. When a rig, such as the rig described in the Albeck application is moved from one position to another, to facilitate recording of sets of images of different portions of the object(s), the movement comprises one or both of a translation and a rotation of the rig, both in three dimensions. If the translational and rotational movement of the rig can be controlled sufficiently precise, the relation of the coordinate system after movement to the coordinate system before movement can easily be determined. However, if, for example, the mass of the rig is sufficiently large, in a number of applications the movement of the rig cannot readily be controlled sufficiently precisely to allow sufficiently precise reconstruction.

[0008] The invention provides new and improved systems and methods for “stitching” a plurality of reconstructions of three-dimensional surface features of object(s) in a scene, the reconstructions being defined relative to respective coordinate systems, thereby to relate them to a common coordinate system.

[0009] In brief summary, the invention provides a system disclosed for stitching a plurality of reconstructions of three-dimensional surface features of at least one object in a scene to relate the reconstructions to a common coordinate system. Each reconstruction is generated from a plurality of two-dimensional images of the scene, and each reconstruction is defined relative to a respective one of a plurality of reconstruction coordinate systems defined relative to one of the images in the scene. The system generates, from at least some of the images, values for translational and rotational components relating a respective reconstruction coordinate system to the common coordinate system. Thereafter, the system uses the values of the translational and rotational components to convert coordinates of the surface features in the respective reconstruction coordinate systems to the common coordinate system.

[0010] In embodiments of the system, the common coordinate system for simplicity is selected to be one of the reconstruction coordinate systems, and the values for translational and rotational components relating the other reconstruction coordinate system(s) to the common coordinate system uses overlapping regions of the images which define the respective reconstruction coordinate systems. In those embodiments, the system first determines the dominate translation that best aligns the largest portions of the image which defines the common coordinate system and the other images, shifts the other images by the amount of the dominate translation and then generates a pixel-to-pixel correspondence to generate a displacement field. From the dominate translation and the displacement field, the system generates the values for the translational and rotational components.

[0011] In embodiments of the system, for multiple reconstructions, instead of processing successive pairs of sets of images to determine translational and rotational components associated with respective reconstruction coordinate systems, the system makes use of a statistical methodology, identified as the “E-M” (estimation and maximization) methodology, to generate maximum likelihood estimates of the translational and rotational components associated with the relations between the reconstructin coordinate systems and the common coordinate system.

[0012] This invention is pointed out with particularity in the appended claims. The above and further advantages of this invention may be better understood by referring to the following description taken in conjunction with the accompanying drawings, in which:

[0013] FIG. 1 is a diagram of a system for “stitching” a plurality of reconstructions of three-dimensional surface features of object(s) in a scene defined relative to respective coordinate systems to relate them to a common coordinate system, constructed in accordance with the invention;

[0014] FIGS. 2 through 5 are flowcharts depicting operations performed by the system depicted in FIG. 1 in connection with the invention.

[0015] FIG. 1 is a diagram of a system 10 for “stitching” a plurality of reconstructions of three-dimensional surface features of object(s) in a scene defined relative to respective coordinate systems to relate them to a common coordinate system, constructed in accordance with the invention. With reference to FIG. 1, system 10 includes a rig 11 including a plurality of cameras 12(0) through 12(C) (generally referred to by reference numeral 12(c)) mounted on a common support 13. The cameras 12(c) are preferably focused on generally the same portion of a scene, including the same portion(s) of the surface(s) of one or more objects generally identified by reference numeral 14 in the scene, thereby to facilitate recording of a set of two-dimensional images of the respective portion(s) by the respective cameras 12(c). The cameras 12(c) provide the set of recorded images to an image processor 15 which generates, from the images provided thereto by the cameras 12(c), information relating to a three-dimensional reconstruction of surface features of the respective object(s) 14 in the scene, for the respective portion(s) to which the cameras 12(c) are focused. In one embodiment, the rig 11 and cameras 12(c) are similar to the respective elements of the apparatus described in the aforementioned Albeck application. In that embodiment, the cameras 12(c) preferably include CCD (“charge-coupled device”) image recording devices, which provide image information in digital form to the image processor 15 for processing. In addition, in that embodiment, the image processor 15 includes suitably-programmed computing devices (such as a suitably-programmed general purpose computer) which generates the three-dimensional surface information from the set of two-dimensional images in a manner similar to that described in the aforementioned Shashua application.

[0016] The system 10 is further provided with a motor 16 which, under control of a control processor 17, can move the rig 11 to facilitate direction of the cameras 12(c) to another portion of the scene 14, including respective other portion(s) of the surface(s) of respective object(s) in the scene 14 from which position the cameras 12(c) can record a second set of images. The rig 11 before one such illustrative movement, indicated in FIG. 1 by the arrow associated with reference numeral 18, is depicted in solid lines in FIG. 1, and rig 11 after the illustrative movement 18 depicted in dashed lines in FIG. 1. In addition, the set of images recorded by the respective cameras 12(c) prior to the illustrative movement 18 of rig 11 is represented by images 20(A)(0) through 20(A)(C) (generally identified by reference numeral 20(A)(c)), and the set of images recorded by the respective cameras 12(c) after the illustrative movement 18 of rig 11 is represented by images 20(B)(0) through 20(B)(c) (generally identified by reference numeral 20(B)(c)). The respective sets of images 20(A)(c) and 20(B)(c) are preferably not of coincident portions of the surface(s) of the object(s) 14 in the scene. Instead, the sets of images 20(A)(c) and 20(B)(c) will preferably be of different portions of the respective surface(s), but, as will be described below, the portions of the respective surface(s) represented by the sets of images 20(A)(c) and 20(B)(c) preferably overlap to some extent.

[0017] The image processor 15 processes the images 20(A)(c) provided by the cameras 12(c) prior to the illustrative movement 18 to generate the three-dimensional surface information relating to the portion(s) of the object(s) depicted by the images 20(A)(c). In addition, the image processor 15 processes the images 20(B)(c) provided by the cameras 12(c) after the illustrative movement 18 to generate the three-dimensional surface information relating to the portion(s) of the object(s) depicted by images 20(B)(c). In one embodiment, operations performed by the image processor 15 in generating the three-dimensional surface information, in connection with the images recorded both before and after the illustrative movement 18, correspond to those operations described in the aforementioned Shashua application, and the information so generated may represent a three-dimensional reconstruction of the portion(s) of the object(s) depicted in the respective set of images. In that embodiment, the image processor 15 generates, from a plurality of sets of points p_j, p_j′ and p_j″ (“j” being an index) in images 20(A)(0) through 20(A)(2), respectively, with points p_j, p_j′ and p_j″ in each set corresponding to projections of a point P_jon a surface of an object in the scene 14 onto the respective images 20(A)(0) through 20(A)(2), a tensor T_A. In generating the tensor T_A, the image processor 15 uses two-dimensional coordinates, in the respective images 20(A)(c), of a selected number of sets of respective points p_j, p_j′ and p_j″. As described in the Shashua application, seven sets of points p_j, p_j′ and p_j″ will suffice to enable the image processor 15 to generate the tensor T_A. As also described in the Shashua application, using the tensor T_Aand two-dimensional coordinates of any set of points p_j, p_j′ and p_j″ in the images 20(A)(c) which are projections of a point P_j(including, but not limited to, the seven sets of points used to generate the tensor T_A), the image processor 15 can determine the three-dimensional coordinates of the corresponding point P_jin the scene 14. The three dimensional coordinates of point P_jwill be in a coordinate system relative to one of the images 20(A)(c), illustratively the image 20(A)(0) recorded by camera 12(0) before the illustrative movement 18.

[0018] Similarly, the image processor generates, from coordinates a plurality of points q_j, q_j′ and q_j″ to in images 20(B)(0) through 20(B)(2), respectively, all corresponding to projections of respective points Q_jonto the respective images 20(B)(0) through 20(B)(2), a tensor T_Band coordinates for the respective points Q_jin a coordinate three-dimensional coordinate system relative to one of the images, illustratively image 20(B)(0), recorded by camera 12(0) after the illustrative movement 18. If the rig 11 is rigid under the movement, so that the cameras 12(c) will be in the same positions relative to each other before and after the illustrative movement 18, and if the three-dimensional coordinate systems are relative to images recorded by the same camera 12(0), then the tensor T_Bwill correspond to the tensor T_A. In the following, it will be assumed that the rig 11 is rigid under movement, so that the same tensor can be used both before and after the illustrative movement 18.

[0019] As noted above, the coordinates generated by the image processor 15 for points P_jgenerated using images 20(A)(c) are defined relative to a three-dimensional coordinate system associated with one of the cameras 12(c), for example, camera 12(0), in its position, prior to the illustrative movement 18, at which image 20(A)(0) was recorded, and coordinates generated by the image processor 15 for points Q_jfrom images 20(B)(c) are defined relative to a coordinate system that is preferably associated with the same camera 12(0), but which will be relative to the camera's position after the illustrative movement 18 at which image 20(B)(0) was recorded. In each case, the coordinates will be defined relative to two coordinate axes (illustratively referred to herein as “x” and “y” axes”) which correspond to the plane of the respective image 20(A)(0) and 20(B)(0), and a third axis (illustratively referred to herein as a “z” axis) that is transverse thereto. It will be appreciated that the coordinate systems for the two sets of points P_jand Q_jin the scene 14 will differ. To be able to utilize both sets of points in a unitary fashion, it is desirable to associate them both with a common coordinate system. The particular common coordinate system which is selected is not important, and, for simplicity and without loss of generality, it (that is, the common coordinate system) can be selected to be the coordinate system before the illustrative movement 18 or after the illustrative movement 18. In one embodiment, the common coordinate system is selected to correspond to the coordinate system associated with camera 12(0) prior to the illustrative movement 18. Thus, in processing the images 20(B)(c) which are recorded after the illustrative movement 18, the image processor 15 will relate the coordinates of the points in three dimensional space that are recorded by the cameras 12(c) after the illustrative movement 18, to the coordinate system associated with camera 12(0) prior to the illustrative movement 18.

[0020] Generally, the change in coordinate system resulting from the illustrative movement 18 consists of one or both of a translational component and/or a rotational component, both in three dimensional space. Thus, if the coordinate system associated with camera 12(0), both before and after the illustrative movement 18, has an origin at the center of the image plane of the camera 12(0), the translational component comprises the position of the center of the image plane after the illustrative movement 18, in the coordinate system associated with the camera 12(0) before the illustrative movement 18. In addition, the rotational component corresponds to the angle of the image plane after the illustrative movement 18, relative to the image plane before the illustrative movement 18. It will be appreciated that, if the position of the origin after the illustrative movement 18 corresponds to the position of the origin before the illustrative movement 18, there is no translational component for the illustrative movement 18. Similarly, if the angular position of the coordinate axes after the illustrative movement 18 corresponds to the angular position of the coordinate axes before the illustrative movement 18, there is no rotational component for the illustrative movement 18.

[0021] It will be appreciated that, if the position and angular orientation of the rig 11 before and after the illustrative movement 18 can be controlled or determined (by, for example, mechanical or electronic sensors) to a sufficient degree of accuracy they (that is, the position and angular orientation) can be used to define the translational and rotational components to relate the coordinate system after the illustrative movement 18 to the coordinate system before the illustrative movement 18. However, in one embodiment, to provide a higher degree of accuracy, the image processor 15 uses the overlapping portions of the respective sets of images 20(A)(c) and 20(B)(c) to determine the translational and rotational components comprising the illustrative movement 18, thereby to relate the coordinate system associated with points Q_jto the common coordinate system, so that all points P_jand Q_jwill be in the same coordinate system, namely, the common coordinate system defined relative to image 20(A)(0).

[0022] Operations performed by the image processor 15 in determining the translational and rotational components comprising the illustrative movement 18 will be described in connection with flowcharts depicted in FIGS. 2 through 4. Generally, using operations described below in connection with FIGS. 2 through 4, the image processor 15 identifies the coordinates, in the coordinate system after the illustrative movement 18, of a number of points Q_jin the scene 14 as recorded in images 20(B)(c) after the illustrative movement 18, which correspond to points P_jin the coordinate system before the illustrative movement 18 as recorded in images 20(A)(c). Since the points Q_jand P_jare, in fact, the same points in the scene 14, although defined in relation to different coordinate systems, the image processor 15 can determine the relationships between the two coordinate systems to, in turn, determine the values for the translational and rotational components comprising the illustrative movement 18.

[0023] As an extension, using operations described below in connection with FIG. 5, after the image processor 15 has determined the values for the translational and rotational components comprising one or more illustrative movements, the image processor 15 generates a maximum likelihood estimate to refine the values using an “E-M” (estimation and maximization) technique. By refining the values for the translational and rotational components in this manner, the image processor 15 can reduce or eliminate errors which may develop particularly in connection with determining values for such components for a plurality of successive illustrative movements to facilitate relating coordinate systems associated with each illustrative movement to a common coordinate system.

[0024] More specifically, and with reference to FIG. 2, the image processor 15 initially determines, for a set of points on the surface(s) of the respective object(s) in the scene 14, coordinates of each of the points in both the coordinate system before the illustrative movement 18 and the coordinate system after the illustrative movement 18 (step 100). After the image processor 15 has determined coordinates of the points in both coordinate systems, it will use the coordinates in the two coordinate systems to relate the coordinate system after the illustrative movement 18 to the coordinate system before the illustrative movement 18, to determine the values of the translational and rotational components comprising the illustrative movement 18 (step 101). After the image processor 15 has determined the values for the translational and rotational components for the illustrative movement 18, it can use them to convert the coordinates of the points which are defined in coordinate system after the illustrative movement 18 to the coordinate system before the illustrative movement 18 (step 102). The details of the operations performed by the image processor 15 in connection with steps 100 and 101 will be described in connection with the flowcharts depicted in FIGS. 3 and 4, respectively.

[0025] FIG. 3 depicts operations performed by the image processor 15 in connection with determining, for a set of points on the surface(s) of the respective object(s) in the scene 14, coordinates of each of the points in both the coordinate system before the illustrative movement 18 and the coordinate system after the illustrative movement 18 (reference step 100). In performing step 100, the image processor 15 several general operations. First, the image processor identifies coordinates, in the respective images 20(B)(c), of sets of points, with the points each set corresponding to a point in the image 20(A)(0). Points in each set so identified will be a projection of the same point in the scene 14 as the point in the image 20(A)(0). Since the points in a set are projections of the same point in the scene 14, the image processor 15 can determine the coordinates of the point in the scene 14 in the coordinate system after the illustrative movement 18, that is, the coordinate system relative to image 20(B)(0), using the tensor and the coordinates of the points in the set in the respective images 20(B)(c).

[0026] As noted above, the illustrative movement 18 is such to ensure that the sets of images 20(A)(c) and 20(B)(c) overlap to some extent, and the image processor 15 makes use of the information contained in the overlapping portions in determining the translational and/or rotational components of the illustrative movement 18. However, the image processor 15 does not know which portions of the respective sets of images 20(A)(c) and 20(B)(c) overlap, and so it will initially determine the portions of the images in each set which overlap with the images in the other set. More specifically, in connection with step 100, the image processor 15 initially determines for each of the images 20(B)(c), the portion of the respective image 20(B)(c) which overlaps with the image 20(A)(0), which image, as noted above, is recorded by the camera 12(0) before the illustrative movement 18 and which serves to define the common coordinate system. In that connection, for each image 20(B)(c), the image processor 15 determines the dominant translation (u_D,v_D) that best aligns the largest portions of image 20(A)(0) and the respective image 20(B)(c) (step 120), and then shifts the respective image 20(B)(c) by shifting the coordinates of the points of the respective image 20(B)(c) by the dominant translation (u_D,v_D) to create a respective shifted image 20(B′)(c) (step 121). The image processor 15 generates values for the dominant translation (u_D,v_D) for each image 20(B)(c), and different values may be generated for “u_D” and “v_D” for each of the images 20(B)(c). Details of operations performed by the image processor 15 in connection with steps 120 and 121 will be described below in connection with equations (1) through (3). In any case, the effect of steps 120 and 121, as applied to each image 20(B)(c) is to effectively shift the portion of the respective image 20(B)(c) which overlaps with the image 20(A)(0) to approximately the same coordinate positions in the respective image.

[0027] Following step 121, the image processor 15 generates a pixel-to-pixel correspondence between image 20(A)(0) and each of the respective shifted images 20(B′)(c), the pixel-to-pixel correspondence defining a displacement field (u_P(x,y),v_P(x,y)) that identifies the displacement, from location (x,y) of the point in the image 20(A)(0), to the location (x+u_p(x,y),y+v_p(x,y)) of the corresponding point in the respective shifted image 20(B′)(c). Details of operations performed by the image processor in connection with step 122 will be described below in connection with equations (4) through (6). After the image processor 15 has determined, for a particular image 20(B)(c), the dominant translation (u_D,v_D) and the displacement field (u_P(x,y),v_P(x,y)), for each point in image 20(A)(0) which is also depicted in image 20(B)(c), the coordinates of the point in image 20(B)(c) can be determined from the coordinates (x,y) of the corresponding point in image 20(A)(c), the dominant translation (u_D,v_D) and the appropriate value from the displacement field (u_P(x,y),v_P(x,y)). After the image processor 15 has performed steps 120 through 122 for each of the images 20(B)(0), 20(B)(1) and 20(B)(2) (step 123), it will have determined, for each point p_jin image 20(A)(0) in the regions which overlap with respective images 20(B)(0), 20(B)(1) and 20(B)(2), coordinates of corresponding points in those images 20(B)(0), 20(B3)(1) and 20(B)(2), that is, coordinates of a respective set of point q_j, q_j′ and q_j″ which are projections of the same respective point Q_jin the scene 14. It will be appreciated that, since the points q_j, q_j′ and q_j″ in each set all correspond to the point p_jin image 20(A)(0), and since that point p_jis also a projection of a point P_jin the scene 14, the points P_jand Q_jcorrespond to the same point in the scene 14. In any case, after the image processor 15 has determined the coordinates of sets of points q_j, q_j′ and q_j″ in images 20(B)(0), 20(B)(1) and 20(B)(2), respectively, it can generate the coordinates of the corresponding points Q_jin the scene 14 using the tensor as described in the aforementioned Shashua application (step 124). It will be appreciated that the coordinates of the point Q_jwill be in the coordinate system after the illustrative movement 18, as defined by image 20(B)(0).

[0028] As noted above, in performing steps 120 and 121 in connection with one of the images 20(B)(c), the image processor 15 initially determines the dominant translation (u_D,v_D) that best aligns the largest portions of image 20(A)(0) and the respective image 20(B)(c), and then shifts the respective image 20(B)(c) by the dominant translation (u_D,v_D) so generated to generate a respective shifted image 20(B′)(c). In one embodiment, the image processor 15 determines the dominant translation (u_D,v_D) (reference step 120) by means of a first-order Taylor expansion of the sum of squares difference (“SSD”) between the two images. In that embodiment, the dominant translation (u_D,v_D) corresponds to the translation that minimizes $\begin{array}{cc}\sum _R{\left(A_0\left(x,y\right)-B_c\left(x+u_D,y+v_D\right)\right)}^2,& \left(1\right)\end{array}$

[0029] where A₀(x,y) represents the intensity map of image 20(A)(0), B_c(x+u_D,y+v_D) represents the intensity map of the respective image 20(B)(c), “x” and “y” represent the coordinates of the respective picture elements, or “pixels” in the respective images 20(A)(0) and 20(B)(c), and “R” represents the respective overlapping portions. In that case, then

[0030] (A₀(x,y)−B_c(x+u_D,y+v_D))−u_DB_c(x+u_D,y+v_D)−v_DB_c(x+u_D,y+v_D)=0,  (2)

[0031] where B_c(x+u_D,y+v_D) and B_c(x+u_D, y+v_D) represent the “x” and “y” components,

[0032] respectively, of the gradient of the intensity values for the respective images 20(B)(c), should hold for each point in the respective pair of images 20(A)(0) and 20(B)(c). The image processor 15 minimizes equation (2) with respect to “u_D” and “v_D” by, in turn, solving $\begin{array}{cc}\left[\begin{array}{cc}\sum {\left(B_{c_x}\right)}^2& \sum B_{c_x}{B}_{c_y}\\ \sum B_{c_x}{B}_{c_y}& \sum {\left(B_{c_y}\right)}^2\end{array}\right]\left[\begin{array}{c}{u}_D\\ v_D\end{array}\right]=\left[\begin{array}{c}-\sum \left(A_0-B_c\right)B_{c_x}\\ -\sum \left(A_0-B_c\right)B_{c_y}\end{array}\right],& \left(3\right)\end{array}$

[0033] where the sum is over respective regions of images 20(A)(0) and 20(B)(c), for “u_D” and “v_D” for each image 20(13)(c). In one embodiment, the image processor 15 solves equation (3) for “u_D” and “v_D” using the well-known Newton-Raphson iterative optimization technique.

[0034] As noted above, after the dominant translation (u_D,v_D) has been generated using equations (1) through (3) (reference step 120), the image processor 15 shifts the respective image 20(B)(c) to by (u_D,v_D) to generate a shifted image 20(B′)(c) (reference step 121). Following step 121, the image processor 15 generates a pixel-to-pixel correspondence between image 20(A)(0) and each of the respective shifted images 20(B′)(c) to generate a displacement field (u_P(x,y),v_P(x,y)) (step 122). In performing step 122, in one embodiment the image processor 15 determines the displacement field (u_P(x,y),v_P(x,y) using a differential method based on the first order Taylor expansion of the sum of squares difference of a local region, or window. In that embodiment, the pixel-to-pixel correspondence corresponds to the translation that minimizes $\begin{array}{cc}\sum _k{\left(A_0\left(x,y\right)-B_c^{\prime }\left(x+u_p,y+v_p\right)\right)}^2,& \left(4\right)\end{array}$

[0035] where A₀(x,y) represents the intensity map of image 20(A)(0), B′_c(x+u_P,y+v_P) represents the intensity map of the respective shifted image 20(B′)(c), “x” and “y” represent the coordinates of the respective picture elements, or “pixels” in the image 20(A)(0) and shifted image 20(B′)(c), respectively, “k” is an index, and the sum is over a small window around the respective pixel at location (x,y). In one embodiment, the window is a five pixel-by-five pixel window around the respective pixel (x,y), although it will be appreciated that other size windows can be used. In that case, then

[0036] (A₀(x,y)−B′_c(x+u_P,y+v_P))−u_PB′_c(x+u_P,y+v_P)−v_PB′_c(x+u_P,y+v_P)=0,  (2)

[0037] where B′_c(x+u_P,y+v_P) and B′_c(x+u_P,y+v_P) represent the “x” and “y” components,

[0038] respectively, of the gradient of the intensity values for the respective shifted image 20(B′)(c), should hold for each point in the respective image 20(A)(0) and shifted image 20(B′)(c) in the window. The image processor 15 minimizes equation (5) with respect to “u_P” and “v_P” by, in turn, solving $\begin{array}{cc}\left[\begin{array}{cc}\sum {\left(B_{c_x}^{\prime }\right)}^2& \sum B_{c_x}^{\prime }{B}_{c_y}^{\prime }\\ \sum B_{c_x}^{\prime }{B}_{c_y}^{\prime }& \sum {\left(B_{c_y}^{\prime }\right)}^2\end{array}\right]\left[\begin{array}{c}{u}_P\\ v_P\end{array}\right]=\left[\begin{array}{c}-\sum \left(A_0-B_c^{\prime }\right)B_{c_x}^{\prime }\\ -\sum \left(A_0-B_c^{\prime }\right)B_{c_y}^{\prime }\end{array}\right],& \left(6\right)\end{array}$

[0039] for each pixel location (x,y), where each sum is over the pixels in the window, to generate “u_P” and “v_P” for each location (x,y) in image 20(B)(c). In one embodiment, the image processor 15 solves equation (6) for “u_P” (that is, “u_P(x,y)”) and “v_P” (that is, “v_P(x,y)”) for each pixel location (x,y) using the well-known Newton-Raphson optimization technique, which is performed in a series of iterations. In each iteration, the image processor 15 generates a displacement field (u_P(x,y),v_P(x,y)) which it uses to generate an updated shifted image 20(B′_UPDATED)(c), which is used as the shifted image 20(B′)(c) in connection with equation (6) in the next iteration.

[0040] In one embodiment, particularly in connection with processing of image 20(A)(0) and a respective shifted image 20(B′)(c) for which there are relatively large displacements between corresponding pixels, image processor 15 performs the Newton-Raphson iterations hierarchically in a coarse-to-fine manner. In these operation, the image processor 15 initially divides the image 20(A)(0) and the respective shifted image 20(B′)(c) into a hierarchy of images in a predetermined frequency range from a low frequency to a high frequency, with the series of images in the hierarchy associated with image 20(A)(0) and the series in the hierarchy associated with the respective shifted image 20(B′)(c) being associated with the same set of frequencies. It will be appreciated that the detail of low frequency images will be relatively coarse and the detail of high frequency images will be relatively fine, and thus the series of images in each hierarchy will extend monotonically from relatively coarse to relatively fine detail. In successive iterations, the image processor 15 processes images from coarse (low frequency) to fine (high frequency) and, in each iteration, the image processor 15 processes a pair of images from the respective hierarchies (that is, the hierarchy associated with image 20(A)(0) and the hierarchy associated with the respective shifted image 20(B′)(c)) that are associated with the same frequency. The image processor 15 adjusts the size of the window used in the respective iterations according to the frequency of the images that are being processed during the iteration; in particular, the window will be larger when lower frequency (that is, coarser) images are processed, and smaller when high frequency (that is, finer) images are processed. In each iteration, the image processor 15 generates a displacement field (u_P(x,y),v_P(x,y)), as described above in connection with equation (6), for each pixel in the images from the hierarchy which is amplified and used to generate a respective updated shifted image 20 (B′_UPDATED)(c) for use as the shifted image 20(B′)(c) in connection with equation (6) in the next iteration as described above. The image processor 15 performs successive iterations throughout the respective hierarchies it of images, until it has processed the finest (highest-frequency) image, at which point it will have generated the displacement field (u_P(x,y),v_P(x,y))

[0041] It will be appreciated that, after the image processor has performed step 124, the image processor 15 will have generated coordinates of at least one point Q_j, and possibly a number of points Q_j, in scene 14, which are projected onto images 20(B)(c), and which are also projected at least onto image 20(A)(0). As noted above, the coordinates of points Q_jwill be in the coordinate system associated with image 20(B)(0), whereas the coordinates of the same points, identified as points P_j, projected onto images 20(A)(c) are in the coordinate system associated with image 20(A)(0). Thus, following step 124, it will use the coordinates in the two coordinate systems to relate the coordinate system after the illustrative movement 18 to the coordinate system before the illustrative movement 18, to determine the translational and rotational components comprising the illustrative movement 18 (reference step 101, FIG. 2). In that connection, the translational and rotational components comprising the illustrative movement 18 will be such as to minimize $\begin{array}{cc}\sum _j{\Vert {\mathrm{RP}}_j+t-Q_j\Vert }^2& \left(7\right)\end{array}$

[0042] where “R” represents the rotational component of the illustrative movement 18, “t” represents the translational component of the illustrative movement 18, and “P_j” and “Q_j” represent corresponding points, in their respective coordinate systems. In (7), the translation “t” can be determined since, after finding the rotation “R,” it is evident that the appropriate translation is simply Q′-RP′, where P′ is the average over the points P_jand Q′ is the average over the points Q_j. It will be appreciated that, after the averages P′ and Q′ are generated, and if new sets of points {P_j-P′}_jand {Q_j-Q′}_jare introduced, the center of each of these sets is the origin of the respective coordinate system, and thus the best transformation for mapping one of the new sets of points onto the other of the new sets of points involves merely a rotation, which, in turn, corresponds to the rotational component R of the illustrative movement 18. Known algorithms may be used to generate the rotational component R between the sets {P_j-P′}_jand {Q_j-Q′}_j, as described in, for example, Gene H. Golub and Charles F. Van Loan, “Matrix Computations” (2d ed) (Johns Hopkins University Press, 1989), page 582 (hereinafter “the Golub, et al., book”).

[0043] With this background, operations performed by the image processor 15 in connection with generating values for “R” and “t” so as to minimize (7) will be described in connection with FIG. 4. With reference to FIG. 4, the image processor 15 initially determines an average for each of the sets of points P_jand Q_j(step 130), referred to as P′ and Q′, respectively. After the image processor has generated the averages P′ and Q′, it generates the sets of points {P_j-P′}_jand {Q_j-Q′}_j(step 131) and, using the sets of points {P_j-P′}_jand {Q_j-Q′}_jgenerated in step 131, generate the value for the rotational component R using, for example, the algorithm described in the Golub, et al., book (step 132). After generating the value for the rotational component R, the image processor 15 generates the value for the translational component “t” as Q′-RP′ (step 133).

[0044] After the image processor 15 has determined the values for the translational and rotational components t and R for the illustrative movement 18, it can use them to convert the coordinates of the points which are defined in coordinate system associated with image 20(B)(0) to the coordinate system associated with image 20(A)(0) (reference step 102).

[0045] Operations described above in connection with FIGS. 2 through 4 and equations (1) through (7) are an efficient mechanism by which a common coordinate system for points P_jin the scene 14 which are projected onto the images 20(A)(c) recorded by the cameras 12(c) before the illustrative movement 18 and the points Q_jin the scene 14 which are projected onto the images 20(B)(c) recorded by the cameras 12(c) after the illustrative movement 18. In performing the operations as described above, the image processor 15 can process all of the pixels of the images 20(A)(0) and 20(B)(c). However, if it does so, the amount of computation which may be required to be performed by the image processor may be quite substantial, depending on the number of pixels comprising the respective images. In addition, if a number of the pixels in one or more of the images 20(A)(0) are in regions of relatively low-contrast, the values of the results of the computation may be relatively noisy. To reduce both the amount of computation which the may be required and the amount of noise which may be present in the values for the translational and rotational components, the image processor 15 can perform the operations in connection with points p_j, p_j′, and p_j″ on images 20(A)(c), and points q_j, q_j′ and q_j″ on images 20(B)(c), which are deemed to be “good” points. Preferably, a point in one image will be a “good” point if it is likely to have a good match in at least one of the other images, which will generally be the case if the local intensity around the respective point has a relatively high variance, which will be the case if the point is in an region of relatively high contrast in the image, and if the variance of the local intensity is not shaped as a straight line through the point. If A_c(x,y) represents the intensity map of the respective image 20(A)(c), where “x” and “y” represent the coordinates of the respective point in the respective image, a point is considered a “good” point if the matrix $\begin{array}{cc}\left[\begin{array}{cc}\sum {\left(A_{c_x}\right)}^2& \sum A_{c_x}{A}_{c_y}\\ \sum A_{c_x}{A}_{c_y}& \sum {\left(A_{c_y}\right)}^2\end{array}\right]& \left(8\right)\end{array}$

[0046] is of rank “two.” In the matrix in (8), A_cand A_crepresent the components of the gradient of the intensity map at the respective point along the respective “x” and “y” axes, and the summation is over a local region around the respective point. In one embodiment, the image processor 15 determines for each point in an image 20(A)(c) whether the matrix in (8) is of rank “two” by determining whether the ratio of the eigenvalues of the matrix is close to one and the value of the smaller eigenvalue is above a selected threshold value. The image processor 15 can identify “good” points in images 20(B)(c), as represented by local intensity maps B(x,y), in a similar manner.

[0047] It will be appreciated that the image processor 15 can perform the operations described above in connection with FIGS. 2 through 4 for each of a series of illustrative movements M₁, M₂, . . . , M_I(generally, “M_i”) of the rig 11 to determine the values for the translational and rotational components of each illustrative movement. Thus, for a first illustrative movement M₁(which may correspond to illustrative movement 18 as described above) the image processor 15 uses the sets of images 20(A)(c) and 20(B)(c) to determine the values for the translational and rotational components of the first illustrative movement M₁, thereby to relate the coordinate system associated with image 20(B)(0) to the common coordinate system associated with image 20(A)(0). Similarly, for a second illustrative movement M₂, the image processor uses sets of images 20(B)(c) and, for example, 20(C)(c) (not shown) to determine the values for the translational and rotational components of the second illustrative movement M₂, thereby to relate the coordinate system associated with image 20(C)(0) to the coordinate system associated with image 20(B)(0). In addition, using the previously-determined values for the translational and rotational components of the first illustrative movement M₁, the image processor 15 can readily relate the coordinate system associated with image 20(C)(0) to the common coordinate system associated with image 20(A)(0) in a manner that will be apparent to those skilled in the art. Thus, it will be apparent that the image processor 15 can use successive pairs of sets of images 20(A)(c) and 20(B)(c), 20(B)(c) and 20(C)(c), 20(C)(c) and 20(D)(c), . . . , to determine the values for the translational and rotational components associated with each successive illustrative movement M₁, M₂, M₃, . . . , to successively relate the respective coordinate system associated with image 20(B)(0), 20(C)(0), . . . , to the common coordinate system associated with image 20(A)(0). However, it will also be apparent that errors which can develop in the values for the translational and rotational components associated with each movement can propagate to movements thereafter.

[0048] To accommodate that, instead of processing successive pairs of sets of images to determine translational and rotational components associated with each successive movement Mi, in one embodiment, the image processor 15 makes use of a statistical methodology, identified as the “E-M” (estimation and maximization) methodology, to generate maximum likelihood estimates of the translational and rotational components associated with the respective movements. In that operation, the image processor 15 determines, from overlapping regions of sets of points in the images 20(A)(0), 20(B)(0), . . . , and in one or more iterations, both coordinates of a set of points of the object(s) in the scene 14 in the common coordinate system and values of the translational and rotational components relative to the common coordinate system of the other coordinate systems.

[0049] More specifically, (reference the change in notation from that used in connection with equations (1) through (8) above) given surface features of the object(s) in the scene 14 defined by a set of “n” points Q={q₁, . . . ,q_j, . . . ,q_n}, and given a set “P” of “m” images P={P₁, . . . ,P_i, . . . ,P_m} of the scene 14, each image P_icomprising points p_ijwhich are projections of the respective points q_jin the scene, then

[0050] p_ij=S_i(q_j)+ε_ij=A_iq_j+b_i+ε_iji=l, . . . , m j=l, . . . , n,  (9)

[0051] where each “S_i” is one of a plurality of transformations S={S_l, . . . , S_i, . . . S_m}, each transformation S_ibeing associated with a correspondingly-indexed image P_iconsisting of a rotation matrix A_iand an affine displacement vector b_i

[0052] S_i(q_j)=A_iq_q+b_i  (10)

[0053] The coordinates of each point p_ijin the respective image P_iare noisy, and the value “ε_ij” in equation (9) comprises a vector representing the noise component of the respective point. In the following, it will be assumed that ε_ijis a Gaussian random vector with a zero mean (average) and a scalar covariance matrix σ ²I, where “I” represents a three-by-three (or “d-by-d,” where “d” represents the number of dimensions in the scene 14) identity matrix. It will further be assumed that the vectors ε_ijassociated with the points p_ijin the various images P_iare mutually independent. With these assumptions, in each iteration, the image processor 15 can generate, in an estimation phase of the iteration, a new maximum likelihood estimate of the coordinates of each of the points in the scene 14, identified as {circumflex over (q)}_j(S₀), as $\begin{array}{cc}{\hat{q}}_j\left(S_0\right)=\frac{1}{m}\sum _{i=1}^m{S}_{0i}^{-1}\left(p_{\mathrm{ij}}\right)j=1,\dots ,n& \left(11\right)\end{array}$

[0054] where “S₀” represents, for the first iteration, an initial set of transformations S₀={S₀₁, . . . ,S_0m}, and, for each subsequent iteration, a corresponding set of transformations as determined during the previous iteration, and S_0i⁻¹(p_ij) represents the inverse transformation for point p_ijunder the respective transformation S_0i.

[0055] After the estimation phase of each iteration, the image processor 15 can generate re-estimations for the transformations S_iduring a maximum phase. If a subsequent iteration is to be performed, the set of re-estimated transformations generated during the iteration can be used as the transformation set S₀during the subsequent iteration. On the other hand, if no subsequent iteration is to be performed, the set of re-estimated transformations can be used as the transformations to relate the various coordinate systems to the common coordinate system. In re-estimating each transformation S_i=(A_i,b_i), the image processor 15 generates a covariance matrix H_ias $\begin{array}{cc}{H}_i=\frac{1}{n}\sum _{j=1}^n\left(\hat{q}\left(S_0\right)-\stackrel{\_}{q}\left(S_0\right)\right){\left(p_{\mathrm{ij}}-{\stackrel{\_}{p}}_i\right)}^{T}i=1,\dots ,m& \left(12\right)\end{array}$

[0056] where $\begin{array}{cc}\stackrel{\_}{q}\left(S_0\right)=\frac{1}{n}\sum _{j=1}^n{\hat{q}}_j\left(S_0\right)& \left(13\right)\end{array}$

[0057] and $\begin{array}{cc}{\stackrel{\_}{p}}_i=\frac{1}{n}\sum _{j=1}^n{p}_{\mathrm{ij}}i=1,\dots ,m.& \left(14\right)\end{array}$

[0058] If U_iD_iV_i^Trepresents the singular value decomposition (“SVD”) of the covariance matrix H_i(see, for example, W. Press, Numerical Recipes In Fortran2d Edition (Cambridge Univ. Press, 1986, 1992), pp. 51 et seq., for a description of singular value decomposition), the image processor 15 generates the re-estimation of the rotation matrix A_ias

[0059] A_i=V_iU_i^−T  (15)

[0060] and, using the value for A_igenerated using equation 13, generates the re-estimation of the affine displacement vector b_ias

[0061] b_i={overscore (p)}_i−A_i{overscore (q)}(S₀)  (16)

[0062] for i=1, . . . , m.

[0063] The image processor 15, in connection with the E-M methodology, can perform a number of iterations until selected termination criteria have been satisfied. In accordance with one termination criterion, the image processor 15 can perform a number of iterations until the transformations S_i=(A_i, b_i) which are generated during an iteration correspond to the transformations which were generated during the previous iteration, or differ by a predetermined maximum tolerance value. Alternatively, or in addition, the image processor 15 can perform a number of iterations until it has performed a predetermined maximum number of iterations.

[0064] In the processing operations in connection with equations (9) through ( 16) above, the images P_icorrespond to the images 20(A)(0), 20(B)(0), . . . , which define the coordinate systems for the various sets of images 20(A)(c), 20(B)(c), . . . . During the first iteration, the image processor 15 can select the transformation S₁, which is associated with image P₁(which corresponds to image 20(A)(0), whose coordinate system defines the common coordinate system as described above in connection with equations (1) through (8) and FIGS. 2 through 4) to be the identity transformation, and the other transformations will correspond to the translational and rotational components determined as described above in connection with equations (1) through (8) and FIGS. 2 through 4. In successive iterations, the rotation matrix A₁generated for the transformation S₁may be perturbed slightly, but from equation (16) it is clear that the affine displacement vector b₁generated for the transformation S₁will be zero for each iteration. After the image processor 15 has performed the number of iterations, if the rotation matrix A₁for transformation S₁is such that the transformation S₁is not the identity transformation, it can adjust the transformation S₁and other transformations S₂, . . . so as to force the transformation S₁to the identity transformation. In that operation, since the affine displacement vector b₁of transformation S₁is identically zero, the adjustments to the transformations involve only adjustments to the rotation matrices.

[0065] With this background, the operations performed by the image processor 15 in connection with the E-M methodology (equations (9) through (16)) will be described in connection with FIG. 5. With reference to FIG. 5, the image processor 15 first determines the initial set of transformations using points which are projected into all of the images 20(A)(0), 20(B)(0), . . . which define the respective coordinate systems associated with the respective sets of images 20(A)(c), 20(B)(c), . . . , with the transformation set S₁associated with image 20(A)(0) being forced to the identity transformation (step 150). Thereafter, the image processor 15 performs, for each image 20(A)(0), 20(B)(0), . . . , the estimation phase to generate a new maximum likelihood estimate of the coordinates of respective points in the scene 14 (step 151) in connection with equation (11). Following step 151, the image processor 15 generates, for each image 20(A)(0), 20(B)(0), . . . , a covariance matrix H_i(equations (12) through (14)) (step 152), determines the singular value decomposition U_iD_iV_i^Tthereof (step 153) and generates therefrom an updated rotation matrix A_ifor the respective transformation S_iusing matrices U_iand V_i^T(step 154) in accordance with equation (15). After the updated rotation matrix A_ihas been determined for a respective transformation, the image processor 15 generates an updated affine displacement vector b_ifor the transformation (step 155) in accordance with equation (16).

[0066] After updated rotation matrices A_iand affine displacement vectors b_ihave been generated for all of the transformations S_i, the image processor 15 determines whether an iteration termination criterion has been satisfied, such that it should terminate iterations (step 156). If the image processor 15 makes a negative determination in step 156, it will return to step 151 to repeat the operations described above in connection with steps 151 through 156. On the other hand, if the image processor 15 makes a positive determination in step 156, it will sequence to step 157 to determine whether the with the final transformation S₁is the identity transformation. If the image processor 15 makes a positive determination in step 157, it will exit (step 158), with the transformations S₂. . . defining the translational and rotational components which relate the respective coordinate systems associated with images 20(B)(0), . . . to the common coordinate system associated with image 20(A)(0). On the other hand, if the image processor 15 makes a negative determination in step 157, it will adjust the rotation matrices A_iassociated with the transformations so that transformation S_iis the identity transformation (step 159) and sequence to step 158 to exit.

[0067] The invention provides a number of advantages. In particular, the invention provides a mechanism whereby reconstructions of objects in a scene, with each reconstruction comprising points in respective three-dimensional coordinate systems, can be related to a common coordinate system.

[0068] It will be appreciated that numerous modifications may be made to the system as described above. For example, although the system has been described as using reconstructions generated using the tensor as described in the Shashua application, it will be appreciated that reconstructions using other methodologies including, for example, the Fundamental Matrix, can also be used. Indeed, the system can use reconstructions generated by any combination of methodologies, that is, one reconstruction may be generated using the tensor described in the Shashua tensor and another reconstruction may be generated using the Fundamental Matrix. It will be appreciated that, if the reconstruction generated using images 20(B)(c) is generated using the Fundamental Matrix, then only two images will be needed, in which portions of two images will need to overlap with the image 20(A)(0).

[0069] It will be appreciated that a system in accordance with the invention can be constructed in whole or in part from special purpose hardware or a general purpose computer system, or any combination thereof, any portion of which may be controlled by a suitable program. Any program may in whole or in part comprise part of or be stored on the system in a conventional manner, or it may in whole or in part be provided in to the system over a network or other mechanism for transferring information in a conventional manner. In addition, it will be appreciated that the system may be operated and/or otherwise controlled by means of information provided by an operator using operator input elements (not shown) which may be connected directly to the system or which may transfer the information to the system over a network or other mechanism for transferring information in a conventional manner.

[0070] The foregoing description has been limited to a specific embodiment of this invention. It will be apparent, however, that various variations and modifications may be made to the invention, with the attainment of some or all of the advantages of the invention. It is the object of the appended claims to cover these and such other variations and modifications as come within the true spirit and scope of the invention.