Apparatus and method for recreating and manipulating a 3D object based on a 2D projection thereof

• US 5,821,943 A
• Filed: 06/30/1995
• Issued: 10/13/1998
• Est. Priority Date: 04/25/1995
• Status: Expired due to Fees

• Current Assignee: CogniTens Ltd. (Hexagon AB)
• Original Assignee: CogniTens Ltd. (Hexagon AB)
• Inventors: Shashua, Amnon
• Primary Examiner(s): BUCHEL JR, RUDOLPH JOHN
• Application Number:
  US08/497,224
• Time in Patent Office: 1,201 Days
• Field of Search: 382/190, 382/201-202, 395/119, 395/127, 395/140-143, 345/419-420, 345/427, 345/433-439, 345/440-443
• US Class Current: 345/427
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2207/20088 Trinocular vision calculations; trifocal tensor
• CPC Class Codes: G06T 2207/20228 Disparity calculation for image-based rendering
• CPC Class Codes: G06T 7/55 from multiple images
• CPC Class Codes: G06T 7/97 Determining parameters from multiple pictures depth or shape recovery from multiple images G06T7/55; stereo camera calibration G06T7/85

Abstract

A method for generating information regarding a 3D object from at least one 2D projection thereof, the method comprising providing at least one 2D projection of a 3D object, generating an array of numbers described by:

α.sub.ijk =v.sub.i '"'"'b.sub.jk -v.sub.j "a.sub.ik (i,j,k=1,2,3),

where a_ij and b_jk are elements of matrices A and B respectively and v_i '"'"' and v_i " are elements of vectors v'"'"' and v" respectively, wherein the matrices and vectors together describe camera parameters of three views of the 3D object and employing the array to generate information regarding the 3D object.

Claims

1. An image processing system for generating an image of a scene from three views of the scene, the image processing system comprising:

A. a planar view processor for identifying from the three planar views a set P_s of at least one point P in the scene which has a respective projection in all three views;

B. a trilinear tensor generator for generating from the set P_s a trilinear tensor T having components α

_ijk conforming to

space="preserve" listing-type="equation">α

.sub.ijk =v'"'"'.sub.i b.sub.jk -v.sub.j".sub.j a.sub.ik (i, j, k=1, 2,

     3),

where v_i '"'"' and v_j " are components of vectors v'"'"' and v", and a_jk and b_jk are components of matrices A and B defined such that, for each point P .OR right. P_s in the set, projection points p, p'"'"' and p" onto the respective first, second and third views have coordinates in the respective view given by

p= I,0!P (where "I" represents an identity matrix),

p'"'"'≅

A,v'"'"'!P (where "≅

" represents equality up to a scale factor), and

p"≅

B,v"!P,

A, B, v'"'"' and v" being the same for projection points p, p'"'"' and p" for point P .OR right. P_s ; and

C. an image generator for utilizing the trilinear tensor T to generate the image of said scene.

2. An image processing system as defined in claim 1 in which said set P_s comprises a plurality of points P, each point P having a projection in all three views.

3. An image processing system as defined in claim 1 further comprising a planar view generator for generating said three planar views.

4. The image processing system as defined in claim 3 in which said trilinear tensor generator generates the components α

_ijk of the trilinear tensor T in accordance with

space="preserve" listing-type="equation">x"α

.sub.13..sup.T p-x"x'"'"'α

.sub.33..sup.T p+x'"'"'α

.sub.31..sup.T p-α

.sub.11..sup.T p=0,

space="preserve" listing-type="equation">y"α

.sub.13..sup.T p-y"x'"'"'α

.sub.33..sup.T p+x'"'"'α

.sub.32..sup.T p-α

.sub.12..sup.T p=0,

space="preserve" listing-type="equation">x"α

.sub.23..sup.T p-x"y'"'"'α

.sub.33..sup.T p+y'"'"'α

.sub.31..sup.T p-α

.sub.21..sup.T p=0,

and

space="preserve" listing-type="equation">y"α

.sub.23..sup.T p-y"y'"'"'α

.sub.33..sup.T p+y'"'"'α

.sub.32..sup.T p-α

.sub.22..sup.T p=0

for said points P_s, where each point p'"'"' has coordinates (x'"'"', y'"'"',

     1)^T and each point p" has coordinates (x", y",

     1)^T, a_ij. for each "i" and "j" (i, j=1, 2,

     3) represents a vector of said trilinear tensor, and "T" represents a transpose operation.

5. An image processing system as defined in claim 2 in which said set P_s comprises seven points P, each point P having a projection in all three views.

6. An image processing system as defined in claim 1 in which said image generator generates said image as a two-dimensional image.

7. An image processing system as defined in claim 6 in which said image generator displays the image generated thereby.

8. An image processing system as defined in claim 6 in which said image generator utilizes the trilinear tensor T to generate, from coordinates for projection points in two of said views for a point P_x in the scene, coordinates for a corresponding projection point in the third of said views, the corresponding projection point comprising a point in said image.

9. An image processing system as defined in claim 8 in which said image generator generates the coordinates for the corresponding projection point by plugging into the trilinear tensor T the coordinates for the projection points in said two of said views.

10. An image processing system as defined in claim 6 in which said image is of said scene at a particular point in time, the image processing system further including a comparator for comparing said image to another image of said scene at a different point in time thereby to facilitate the identification of differences in the scene at the respective points in time.

11. An image processing system as defined in claim 1 in which said image generator generates said image as a three-dimensional image.

12. An image processing system as defined in claim 11 further comprising a novel view generator for generating, from said three-dimensional image, a two-dimensional image comprising a novel view of said scene from a predetermined direction.

13. An image processing system as defined in claim 12 in which said image generator further displays the image generated thereby.

14. An image processing system as defined in claim 13, the system generating said image from more than three views,

A. said planar view processor identifying, for each of a plurality of subsets "m" of three of said planar views, two of said views being the same for all of said subsets "m," a set P_s of at least one point P in the scene which has a projection in all three views of the respective subset;

B. said trilinear tensor generator for generating, for each subset "m," a trilinear tensor T_m having components α

_ijk,m ;

C. said image processing system further comprising a correspondence matrix generating element comprising;

i. a correspondence matrix generator for generating, for each trilinear tensor T_m associated with a subset of views "m," a two-dimensional correspondence matrix G_m having a plurality of rows and columns, each column "j" of the correspondence matrix G_m containing the elements α

_1j1,m, α

_1j2,m, . . . , α

_3j3,m of the respective trilinear tensor T_m ; and

ii. a concatenation element for concatenating the correspondence matrices G_m for the respective subsets together, thereby to generate a concatenated correspondence matrix CG_m ; and

D. said epipolar line generator generates each said epipolar line as the cross product of corresponding columns of four largest principal components of the concatenated correspondence matrix CG_m.

15. An image processing system as defined in claim 14 in which said each set P_s comprises a plurality of points P, each point P having a projection in all three views of the respective set "m."

16. An image processing system as defined in claim 15 in which each said set P_s comprises seven points P, each point P having a projection in all three views of the respective set "m."

17. An image processing system as defined in claim 11 in which said scene includes at least one object, the image processing system further comprising an image comparator for performing a comparison operation in connection with a portion of the image corresponding to the object and a predetermined model for said object.

18. An image processing system as defined in claim 17 in which the image comparator, if it determines that a difference exists between the portion of the image corresponding to the object and the predetermined model, further compares said difference with a predetermined tolerance.

19. An image processing system as defined in claim 1 in which said image generator comprises:

A. a fundamental matrix generator for generating a fundamental matrix F from the trilinear tensor T;

B. an epipole generator for generating coordinates for an epipole v'"'"' in said second view;

C. an affine depth generator for using the fundamental matrix F, said coordinates for said epipole v'"'"', and coordinates (x_r, y_r) and (x'"'"'_r, y'"'"'_r) of corresponding points p_r and p'"'"'_r in said respective first and second views to generate an affine depth value κ

_r, thereby to provide coordinates for (x, y, 1, κ

_r) for a point P_r in the scene.

20. An image processing system as defined in claim 19 in which said fundamental matrix generator generates the fundamental matrix F as E_j^T F+F^T E_j =0 (j=1, 2, 3), where E_j are three matrices E_j =α

_1j1, α

_1j2, . . . , α

_3j3 and "T" represents a transpose operation.

21. An image processing system as defined in claim 20, the system generating said image from more than three views,

A. said planar view processor identifying, for each of a plurality of subsets "m" of three of said planar views, two of said views being the same for all of said subsets "m," a set P_s having at least one point P in the scene which has a projection in all three views of the respective subset;

B. said trilinear tensor generator generates, for each subset "m," a trilinear tensor T_m having components α

_ijk,m ;

C. said image processing system further comprising a correspondence matrix generating element comprising;

i. a correspondence matrix generator for generating, for each trilinear tensor T_m associated with a subset of views "m," a two-dimensional correspondence matrix G_m having a plurality of rows and columns, each column "j" of the correspondence matrix G_m containing the elements α

_1j1,m, α

_1j2,m, . . . , α

_3j3,m of the respective trilinear tensor T_m ;

ii. a concatenation element for concatenating the correspondence matrices G_m for the respective subsets together, thereby to generate a concatenated correspondence matrix CG_m ; and

D. said fundamental matrix generator generates the fundamental matrix F as C_k^T F+F^T C_k =0 (k=1, 2, 3,

     4) where each C_k represents one of four largest principal components of the concatenated correspondence matrix CG_m and "T" represents a transpose operation.

22. An image processing system as defined in claim 21 in which said each said set P_s comprises a plurality of points P, each point P having a projection in all three views.

23. An image processing system as defined in claim 22 in which each said set P_s comprises seven points P, each point P having a projection in all three views.

24. An image processing system as defined in claim 19 in which said affine depth generator generates said affine depth κ

in conformance with p'"'"'_r ≅

v'"'"'!F p_r +κ

v'"'"'.

25. An image processing system as defined in claim 19 in which said image generator comprises:

A. a homography generator for generating a homography matrix E_i from the trilinear tensor T;

B. an epipole generator for generating coordinates for an epipole v'"'"' in said second view;

C. an affine depth generator for using the homography matrix E_i, said coordinates for said epipole v'"'"', and coordinates (x_r, y_r) and (x'"'"'_r, y'"'"'_r) of corresponding points p_r and p'"'"'_r in said respective first and second views to generate an affine depth value κ

_r, thereby to provide coordinates for (x, y, 1, κ

_r) for a point P_r in the scene.

26. An image processing system as defined in claim 25 in which said affine depth generator generates the affine depth value κ

_r in accordance with p'"'"'_r ≅

E_i p_r +κ

v'"'"'.

27. An image processing system as defined in claim 21 further comprising a planar view generator for generating said more than three views.

28. An image processing system as defined in claim 27 in which said epipole coordinate determination element uses a least-squares methodology to determine the coordinate of said epipole.

29. An image processing system as defined in claim 21 in which said epipole generator generates said coordinates for said epipole v'"'"' as F^T v'"'"'=0, where "F" is said fundamental matrix and "T" represents a transpose operation.

30. An image processing system as defined in claim 21 in which said epipole generator comprises:

A. an epipolar line generator for generating, from the tensor T, a plurality of epipolar lines; and

B. an epipole coordinate determination element for determining the coordinate of said epipole as the point of intersection of said epipolar lines.

31. An image processing system as defined in claim 22 in which said epipolar line generator generates each said epipolar line as the cross product of corresponding columns of two of the three matrices E_j =α

_1j1, α

_1j2, . . . , α

_3j3 (j=1, 2,

     3).

32. An image processing system as defined in claim 14 further comprising a planar view generator for generating said more than three views.

33. An image processing system as defined in claim 1, the system generating said image from more than three views,

A. said planar view processor identifying, for each of a plurality of subsets "m" of three of said planar views, two of said views being the same for all of said subsets "m," a set P_s of at least one point P in the scene which has a projection in all three views of the respective subset;

B. said trilinear tensor generator generates, for each subset "m," a trilinear tensor T_m having components α

_ijk,m ;

C. said image processing system further comprising a correspondence element for processing said trilinear tensors T_m in accordance with a rank-4 constraint, thereby to generate a set of processed trilinear tensors T_m '"'"' which are linear related to each other, the image generator utilizing at least one processed trilinear tensor for at least one subset to generate said image instead of the associated trilinear tensor for the same subset.

34. An image processing system as defined in claim 33 in which said each set P_s comprises a plurality of points P, each point P having a projection in all three views of the respective set "m."

35. An image processing system as defined in claim 33 in which each said set P_s comprises seven points P, each point P having a projection in all three views of the respective set "m."

36. An image processing system as defined in claim 33 in which said correspondence element comprises:

A. a correspondence matrix generator for generating, for each trilinear tensor T_m associated with a subset of views "m," a two-dimensional correspondence matrix G_m having a plurality of rows and columns, each column "j" of the correspondence matrix G_m containing the elements α

_1j1,m, α

_1j2,m, . . . , α

_3j3,m of the respective trilinear tensor T_m ;

B. a concatenation element for concatenating the correspondence matrices G_m for the respective subsets together, thereby to generate a concatenated correspondence matrix CG_m ;

C. a rank-4 processing element for processing said concatenated correspondence matrix CG_m in accordance with the rank-4 constraint, thereby to generate a processed concatenated correspondence matrix CG_m ; and

D. a processed trilinear tensor generator for generating from the processed concatenated correspondence matrix CG_m the set of processed trilinear tensors T_m '"'"'.

37. An image processing system as defined in claim 36 in which:

A. said concatenation element concatenates the correspondence matrices G_m such that columns of successive ones of the correspondence matrices G_m form successive sets of columns of the concatenated correspondence matrix CG_m ; and

B. said processed trilinear tensor generator generates each processed trilinear tensor T_m '"'"' associated with a subset "m" from the ones of the set of columns of the concatenated correspondence matrix associated with the correspondence matrix G_m for the same subset "m."

38. A computer-implemented image processing method for generating an image of a scene from three views of the scene, the image processing method comprising the steps of:

A. identifying from said three planar views a set P_s of at least one point P in the scene which has a projection in all three views;

B. generating from the set P_s a trilinear tensor T having components α

_ijk conforming to;

space="preserve" listing-type="equation">α

.sub.ijk =v.sub.i '"'"'b.sub.jk -v.sub.j "a.sub.ik (i, j, k=1, 2,

     3),

where v_i '"'"' and v_j '"'"' are components of vectors v'"'"' and v", and a_jk and b_jk are components of matrices A and B defined such that, for said point P .OR right. P_s in the set, projection points p, p'"'"' and p" onto the respective first, second and third views have coordinates in the respective view given by

p= I,0!P (where "I" represents an identity matrix),

p'"'"'≅

A,v'"'"'!P (where "≅

" represents equality up to a scale factor), and

p"≅

B,v"!P,

A, B, v'"'"' and v" being the same for projection points p, p'"'"' and p" for all points P .OR right. P_s ; and

C. utilizing the trilinear tensor T to generate said image.

39. A computer-implemented image processing method as defined in claim 38 in which said set P_s comprises a plurality of points P, each point P having a projection in all three views.

40. A computer-implemented image processing method as defined in claim 39 in which said set P_s comprises seven points P, each point P having a projection in all three views.

41. A computer-implemented image processing method as defined in claim 40 in which said trilinear tensor generating step includes the step of generating the components α

_ijk of the trilinear tensor T in accordance with;

space="preserve" listing-type="equation">x"α

.sub.13..sup.T p-x"x'"'"'α

.sub.33..sup.T p+x'"'"'α

.sub.31..sup.T p-α

.sub.11..sup.T p=0,

space="preserve" listing-type="equation">y"α

.sub.13..sup.T p-y"x'"'"'α

.sub.33..sup.T p+x'"'"'α

.sub.32..sup.T p-α

.sub.12..sup.T p=0,

space="preserve" listing-type="equation">x"α

.sub.23..sup.T p-x"y'"'"'α

.sub.33..sup.T p+y'"'"'α

.sub.31..sup.T p-α

.sub.21..sup.T p=0,

and

space="preserve" listing-type="equation">y"α

.sub.23..sup.T p-y"y'"'"'α

.sub.33..sup.T p+y'"'"'α

.sub.32..sup.T p-α

.sub.22..sup.T p=0,

for said points P_s, where each point p'"'"' has coordinates (x'"'"', y'"'"',

     1)^T and each point p" has coordinates (x", y",

     1)^T, α

_ij. for each "i" and "j" (i, j=1, 2,

     3) represents a vector of said trilinear tensor, and "T" represents a transpose operation.

42. A computer-implemented image processing method as defined in claim 38 further comprising the step of generating said three planar views.

43. A computer-implemented image processing method as defined in claim 38 in which said image generation step includes the step of generating said image as a two-dimensional image.

44. A computer-implemented image processing method as defined in claim 43 in which said image generation step further includes the step of displaying the generated image.

45. A computer-implemented image processing method as defined in claim 43 in which said image is of said scene at a particular point in time, the image processing method further comprising the step of comparing said image to another image of said scene at a different point in time thereby to facilitate identification of differences in the scene at the respective points in time.

46. A computer-implemented image processing method as defined in claim 38 in which said image generation step includes the step of utilizing the trilinear tensor T to generate, from coordinates for projection points in two of said views for a point P_x in the scene, coordinates for a corresponding projection point in the third of said views, the corresponding projection point comprising a point in said image.

47. A computer-implemented image processing method as defined in claim 46 in which said image generation step includes the step of generating the coordinates for the corresponding projection point by plugging into the trilinear tensor T the coordinates for the projection points in said two of said views.

48. A computer-implemented image processing method as defined in claim 38 in which said image generation step includes the step of utilizing the trilinear tensor T to generate a three-dimensional image of the scene.

49. A computer-implemented image processing method as defined in claim 48 further comprising the step of generating, from the three-dimensional image, a two-dimensional image comprising a novel view of said scene from a predetermined direction.

50. A computer-implemented image processing method as defined in claim 49 further comprising the step of displaying the image comprising the novel view.

51. A computer-implemented image processing method as defined in claim 48 in which said scene includes at least one object, the image processing method further comprising the step of comparing at least a portion of the image corresponding to the object and a predetermined model for said object.

52. A computer-implemented image processing method as defined in claim 51 further comprising the step of, if a difference is determined between the at least a portion of the image corresponding to the object and the predetermined model for said object, comparing said difference to a predetermined tolerance and generating an indication in response to the comparison.

53. A computer-implemented image processing method as defined in claim 51 in which said utilization step comprises the steps of:

A. generating a homography matrix E_i from the trilinear tensor T;

B. generating coordinates for an epipole v'"'"' in said second view;

C. using the homography matrix E_i, said coordinates for said epipole v'"'"', and coordinates (x_r, y_r) and (x'"'"'_r,y'"'"'_r) of corresponding points p_r and p'"'"'_r in said respective first and second views to generate an affine depth value κ

_r, thereby to provide coordinates for (x, y, 1, κ

_r) for a point P_r in the scene.

54. A computer-implemented image processing method as defined in claim 53 in which said affine depth generation step includes the step of generating the affine depth value κ

_r in accordance with p'"'"'_r ≅

E_i p_r +κ

v'"'"'.

55. A computer-implemented image processing method as defined in claim 48 in which said utilization step includes the steps of:

A. generating a fundamental matrix F from the trilinear tensor T;

B. generating coordinates for an epipole v'"'"' in said second view;

C. using the fundamental matrix F, said coordinates for said epipole v'"'"', and coordinates (x_r, y_r) and (x'"'"'_r, y'"'"'_r) of corresponding points p_r and p'"'"'_r in said respective first and second views to generate an affine depth value κ

_r, thereby to provide coordinates for (x, y, 1, κ

_r) for a point P_r in the scene.

56. A computer-implemented image processing method as defined in claim 55 in which said fundamental matrix generating step includes the step of generating the fundamental matrix F as E_j^T F+F^T E_j =0 (j=1, 2, 3), where E_j are three matrices E_j =α

_1j1, α

_1j2, . . . , α

_3j3 and "T" represents a transpose operation.

57. A computer-implemented image processing method as defined in claim 55, the method generating said image from more than three planar views of a scene, in which

A. said point set identifying step includes the step of identifying, for each of a plurality of subsets "m" of three of said planar views, two of said views being the same for all of said subsets "m," a set P_s at least one point P in the scene which has a projection in all three views of the respective subset;

B. said trilinear tensor generating step includes the step of generating, for each subset "m," a trilinear tensor T_m having components α

_ijk,m ;

C. said method further includes a correspondence matrix generating step comprising the steps of;

i. generating, for each trilinear tensor T_m associated with a subset of views "m," a two-dimensional correspondence matrix G_m having a plurality of rows and columns, each column "j" of the correspondence matrix G_m containing the elements α

_1j1,m, α

_1j2,m, . . . , α

_3j3,m of the respective trilinear tensor T_m ; and

ii. concatenating the correspondence matrices G_m for the respective subsets together, thereby to generate a concatenated correspondence matrix CG_m ; and

D. said fundamental matrix generating step includes the step of generating the fundamental matrix F as C_k^T F+F^T C_k =0 (k=1, 2, 3,

     4) where each C_k represents one of four largest principal components of the concatenated correspondence matrix CG_m and "T" represents a transpose operation.

58. A computer-implemented image processing method as defined in claim 57 in which said each said set P_s comprises a plurality of points P, each point P having a projection in all three views.

59. A computer-implemented image processing method as defined in claim 58 in which each said set P_s comprises seven points P, each point P having a projection in all three views.

60. A computer-implemented image processing method as defined in claim 57 further comprising the step of generating said three planar views.

61. A computer-implemented image processing method as defined in claim 57 in which said epipole generating step includes the step of generating said coordinates for said epipole v'"'"' as F^T v'"'"'=0, where "F" is said fundamental matrix and "T" represents a transpose operation.

62. A computer-implemented image processing method as defined in claim 55 in which said epipole generating step includes the steps of

A. generating, from the tensor T, a plurality of epipolar lines;

and

B. determining the coordinate of said epipole as the point of intersection of said epipolar lines.

63. A computer-implemented image processing method as defined in claim 62 in which said epipolar line generating step includes the step of generating each said epipolar line as the cross product of corresponding columns of two of the three matrices E_j =α

_1j1, α

_1j2, . . . , α

_3j3 (j=1, 2,

     3).

64. A computer-implemented image processing method as defined in claim 63, the method generating said image from more than three planar views of a scene, in which

A. said point set identifying step includes the step of identifying, for each of a plurality of subsets "m" of three of said planar views, two of said views being the same for all of said subsets "m," a set P_s at least one point P in the scene which has a projection in all three views of the respective subset;

B. said trilinear tensor generating step includes the step of generating, for each subset "m," a trilinear tensor T_m having components α

_ijk,m ;

C. said method further comprises a correspondence matrix generating step comprising the steps of;

i. generating, for each trilinear tensor T_m associated with a subset of views "m," a two-dimensional correspondence matrix G_m having a plurality of rows and columns, each column "j" of the correspondence matrix G_m containing the elements α

_1j1,m, α

_1j2,m, . . . α

_3j3,m of the respective trilinear tensor T_m ; and

ii. concatenating the correspondence matrices G_m for the respective subsets together, thereby to generate a concatenated correspondence matrix CG_m ; and

D. said epipolar line generating step includes the step of generating each said epipolar line as the cross product of corresponding columns of four largest principal components of the concatenated correspondence matrix CG_m.

65. A computer-implemented image processing method as defined in claim 64 in which said each said set P_s comprises a plurality of points P, each point P having a projection in all three views.

66. A computer-implemented image processing method as defined in claim 65 in which each said set P_s comprises seven points P, each point P having a projection in all three views.

67. A computer-implemented image processing method as defined in claim 63 in which said epipole coordinate determination step includes the step of using a least-squares methodology to determine the coordinate of said epipole.

68. A computer-implemented image processing method as defined in claim 64 further comprising the step of generating said three planar views.

69. A computer-implemented image processing method as defined in claim 55 in which said affine depth generating step includes the step of generating said affine depth κ

in conformance with p'"'"'_r ≅

v'"'"'!F p_r +κ

v'"'"'.

70. A computer-implemented image processing method as defined in claim 38, the method generating said image from more than three planar views of a scene, in which

A. said point set identifying step includes the step of identifying, for each of a plurality of subsets "m" of three of said planar views, a set P_s at least one point in the scene which has a projection in all three views of the respective subset;

B. said trilinear tensor generating step includes the step of generating, for each subset "m," a trilinear tensor T_m having components α

_ijk,m ;

C. said method further comprising a correspondence step for processing said trilinear tensors T_m in accordance with a rank-4 constraint, thereby to generate a set of processed trilinear tensors T_m '"'"' which are linear related to each other, the utilization element utilizing at least one processed trilinear tensor for at least one subset to generate said image instead of the associated trilinear tensor for the same subset.

71. A computer-implemented image processing method as defined in claim 70 in which said each said set P_s comprises a plurality of points P, each point P having a projection in all three views.

72. A computer-implemented image processing method as defined in claim 71 in which each said set P_s comprises seven points P, each point P having a projection in all three views.

73. A computer-implemented image processing method as defined in claim 72 further comprising the step of generating said three planar views.

74. A computer-implemented image processing method as defined in claim 70 in which said correspondence step comprises the steps of:

A. generating, for each trilinear tensor T_m associated with a subset of views "m," two of said views being the same for all of said subsets "m," a two-dimensional correspondence matrix G_m having a plurality of rows and columns, each column "j" of the correspondence matrix G_m containing the elements α

_1j1,m, α

_1j2,m, . . . , α

_3j3,m of the respective trilinear tensor T_m ;

B. concatenating the correspondence matrices G_m for the respective subsets together, thereby to generate a concatenated correspondence matrix CG_m ;

C. processing said concatenated correspondence matrix CG_m in accordance with the rank-4 constraint, thereby to generate a processed concatenated correspondence matrix CG_m ; and

D. generating from the processed concatenated correspondence matrix CG_m the set of processed trilinear tensors T_m '"'"'.

75. A computer-implemented image processing method as defined in claim 74 in which:

A. said concatenation step includes the step of concatenating the correspondence matrices G_m such that columns of successive ones of the correspondence matrices G_m form successive sets of columns of the concatenated correspondence matrix CG_m ; and

B. said processed trilinear tensor generating step includes the step of generating each processed trilinear tensor T_m '"'"' associated with a subset "m" from the ones of the set of columns of the concatenated correspondence matrix associated with the correspondence matrix G_m for the same subset "m."

76. A computer program product for enabling a computer to generate an image of a scene from three views of the scene, the three views having a set P_s of at least one point P in the scene which has a respective projection in all three views, the computer program product comprising a computer-readable medium having encoded thereon:

A. a trilinear tensor generation module for enabling said computer to generate from the set P_s a trilinear tensor T having components α

_ijk conforming to

space="preserve" listing-type="equation">α

.sub.ijk =v.sub.i '"'"'b.sub.jk -v.sub.j "a.sub.ik (i, j, k=1, 2,

     3),

where v_i '"'"' and v_j " are components of vectors v'"'"' and v", and a_jk and b_jk are components of matrices A and B defined such that, for each point P .OR right. P_s in the set, projection points p, p'"'"' and p" onto the respective first, second and third views have coordinates in the respective view given by

p= I,0!P (where "I" represents an identity matrix),

p'"'"'≅

A,v'"'"'!P (where "≅

" represents equality up to a scale factor), and

p"≅

B,v"!P,

A, B, v'"'"' and v" being the same for projection points p, p'"'"' and p" for point P .OR right. P_s ; and

B. an image generation module for enabling said computer to utilize the trilinear tensor T to generate the image of said scene.

77. A computer program product as defined in claim 76 further comprising a planar view processing module for enabling said computer to identify from the three planar views the set P_s of at least one point P in the scene which has a respective projection in all three views.

78. A computer program product as defined in claim 77 in which said image generation module enables said computer to generate said image as a two-dimensional image.

79. A computer program product as defined in claim 78 in which said image generator module further enables said computer to display the image generated thereby.

80. A computer program product as defined in claim 78 in which said image generation module enables said computer to utilize the trilinear tensor T to generate, from coordinates for projection points in two of said views for a point P_x in the scene, coordinates for a corresponding projection point in the third of said views, the corresponding projection point comprising a point in said image.

81. A computer program product as defined in claim 80 in which said image generation module enables said computer to generate the coordinates for the corresponding projection point by plugging into the trilinear tensor T the coordinates for the projection points in said two of said views.

82. A computer program product as defined in claim 78 in which said image is of said scene at a particular point in time, the computer program product further including a comparator module for enabling said computer to compare said image to another image of said scene at a different point in time thereby to facilitate the identification of differences in the scene at the respective points in time.

83. A computer program product as defined in claim 76 in which said set P_s comprises a plurality of points P, each point P having a projection in all three views.

84. A computer program as defined in claim 83 in which said set P_s comprises seven points P, each point P having a projection in all three views.

85. A computer program product as defined in claim 76 further comprising a planar view generator module for enabling said computer to generate said three planar views.

86. A computer program product as defined in claim 85 in which said trilinear tensor generation module enables said computer to generate the components α

_ijk of the trilinear tensor T in accordance with

space="preserve" listing-type="equation">x"α

.sub.13..sup.T p-x"x'"'"'α

.sub.33..sup.T p+x'"'"'α

.sub.31..sup.T p-α

.sub.11..sup.T p=0,

space="preserve" listing-type="equation">y"α

.sub.13..sup.T p-y"x'"'"'α

.sub.33..sup.T p+x'"'"'α

.sub.32..sup.T p-α

.sub.12..sup.T p=0,

space="preserve" listing-type="equation">x"α

.sub.23..sup.T p-x"y'"'"'α

.sub.33..sup.T p+y'"'"'α

.sub.31..sup.T p-α

.sub.21..sup.T p=0,

and

space="preserve" listing-type="equation">y"α

.sub.23..sup.T p-y"y'"'"'α

.sub.33..sup.T p+y'"'"'α

.sub.32..sup.T p-α

.sub.22..sup.T p=0,

for said points P_s, where each point p'"'"' has coordinates (x'"'"', y'"'"',

     1)^T and each point p" has coordinates (x", y",

     1)^T, α

_ij. for each "i" and "j" (i, j=1, 2,

     3) represents a vector of said trilinear tensor, and "T" represents a transpose operation.

87. A computer program product as defined in claim 76 in which said image generator module enables said computer to generate said image as a three-dimensional image.

88. A computer program product as defined in claim 87 further comprising a novel view generator module for enabling said computer to generate, from said three-dimensional image, a two-dimensional image comprising a novel view of said scene from a predetermined direction.

89. A computer program product as defined in claim 88 in which said image generator module further enables said computer to display the image generated thereby.

90. A computer program product as defined in claim 89, the computer program product enabling said computer to generate said image from more than three views,

A. said computer program product comprising a planar view processor module for enabling said computer to identify, for each of a plurality of subsets "m" of three of said planar views, two of said views being the same for all of said subsets "m," a set P_s of at least one point P in the scene which has a projection in all three views of the respective subset;

B. said trilinear tensor generator module enabling said computer to generate, for each subset "m," a trilinear tensor T_m having components α

_ijk,m ;

C. said computer program product further comprising a correspondence matrix generating module comprising;

i. a correspondence matrix generator module for enabling said computer to generate, for each trilinear tensor T_m associated with a subset of views "m," a two-dimensional correspondence matrix G_m having a plurality of rows and columns, each column "j" of the correspondence matrix G_m containing the elements α

_1j1,m, α

_1j2,m, . . . , α

_3j3,m of the respective trilinear tensor T_m ; and

ii. a concatenation module for enabling said computer to concatenate the correspondence matrices G_m for the respective subsets together, thereby to generate a concatenated correspondence matrix CG_m ; and

D. said epipolar line generator module enabling said computer to generate each said epipolar line as the cross product of corresponding columns of four largest principal components of the concatenated correspondence matrix CG_m.

91. A computer program product as defined in claim 90 in which said each set P_s comprises a plurality of points P, each point P having a projection in all three views of the respective set "m."

92. A computer program product as defined in claim 91 in which each said set P_s comprises seven points P, each point P having a projection in all three views of the respective set "m."

93. A computer program product as defined in claim 90 further comprising a planar view generator module for enabling said computer to generate said more than three views.

94. A computer program product as defined in claim 87 in which said scene includes at least one object, the computer program product further comprising an image comparator module for enabling said computer to perform a comparison operation in connection with a portion of the image corresponding to the object and a predetermined model for said object.

95. A computer program product as defined in claim 94 in which the image comparator module further enables said computer to, if it determines that a difference exists between the portion of the image corresponding to the object and the predetermined model, further compare said difference with a predetermined tolerance.

96. A computer program product as defined in claim 87 in which said image generator module comprises:

A. a fundamental matrix generator module for enabling said computer to generate a fundamental matrix F from the trilinear tensor T;

B. an epipole generator module for enabling said computer to generate coordinates for an epipole v'"'"' in said second view;

C. an affine depth generator module for enabling said computer to use the fundamental matrix F, said coordinates for said epipole v'"'"', and coordinates (x_r, y_r) and (x'"'"'_r, y'"'"'_r) of corresponding points p_r and p'"'"'_r in said respective first and second views to generate an affine depth value κ

_r, thereby to provide coordinates for (x, y, 1, κ

_r) for a point P_r in the scene.

97. A computer program product as defined in claim 96 in which said fundamental matrix generator module for enabling said computer to generate the fundamental matrix F as E_j^T F+F^T E_j =0 (j=1, 2, 3), where E_j are three matrices E_j =α

_1j1, α

_1j2, . . . , α

_3j3 and "T" represents a transpose operation.

98. A computer program product as defined in claim 97, the computer program product enabling said computer to generate said image from more than three views,

A. the computer program product including a planar view processor module for enabling said computer to identify, for each of a plurality of subsets "m" of three of said planar views, two of said views being the same for all of said subsets "m," a set P_s having at least one point P in the scene which has a projection in all three views of the respective subset;

B. said trilinear tensor generator module for enabling said computer to generate, for each subset "m," a trilinear tensor T_m having components α

_ijk,m ;

C. said computer program product further comprising a correspondence matrix generating module comprising;

i. a correspondence matrix generator module for enabling said computer to generate, for each trilinear tensor T_m associated with a subset of views "m," a two-dimensional correspondence matrix G_m having a plurality of rows and columns, each column "j" of the correspondence matrix G_m containing the elements α

_1j1,m, α

_1j2,m, . . . , α

_3j3,m of the respective trilinear tensor T_m ;

ii. a concatenation module for enabling said computer to concatenate the correspondence matrices G_m for the respective subsets together, thereby to generate a concatenated correspondence matrix CG_m ; and

D. said fundamental matrix generator module enabling said computer to generate the fundamental matrix F as C_k^T F+F^T C_k =0 (k=1, 2, 3,

     4) where each C_k represents one of four largest principal components of the concatenated correspondence matrix CG_m and "T" represents a transpose operation.

99. A computer program product as defined in claim 98 in which said each said set P_s comprises a plurality of points P, each point P having a projection in all three views.

100. A computer program product as defined in claim 91 in which each said set P_s comprises seven points P, each point P having a projection in all three views.

101. A computer program product as defined in claim 96 in which said affine depth generator module for enabling said computer to generate said affine depth κ

in conformance with p'"'"'_r ≅

v'"'"'!F p_r +κ

v'"'"'.

102. A computer program product as defined in claim 96 in which said image generator module comprises:

A. a homography generator module for enabling said computer to generate a homography matrix E_i from the trilinear tensor T;

B. an epipole generator module for enabling said computer to generate coordinates for an epipole v'"'"' in said second view;

C. an affine depth generator module for enabling said computer to use the homography matrix E_i, said coordinates for said epipole v'"'"', and coordinates (x_r, y_r) and (x'"'"'_r, y'"'"'_r) of corresponding points p_r and p'"'"'_r in said respective first and second views to generate an affine depth value ε

_r, thereby to provide coordinates for (x, y, 1, κ

_r) for a point P_r in the scene.

103. A computer program product as defined in claim 102 in which said affine depth generator module for enabling said computer to generate the affine depth value κ

_r in accordance with p'"'"'_r ≅

E_i p_r +κ

v'"'"'.

104. A computer program product as defined in claim 98 further comprising a planar view generator module for enabling said computer to generate said more than three views.

105. A computer program product as defined in claim 104 in which said epipole coordinate determination module for enabling said computer to use a least-squares methodology to determine the coordinate of said epipole.

106. A computer program product as defined in claim 98 in which said epipole generator module enables said computer to generate said coordinates for said epipole v'"'"' as F^T v'"'"'=0, where "F" is said fundamental matrix and "T" represents a transpose operation.

107. A computer program product as defined in claim 98 in which said epipole generator module comprises:

A. an epipolar line generator module for enabling said computer to generate, from the tensor T, a plurality of epipolar lines; and

B. an epipole coordinate determination module for enabling said computer to determine the coordinate of said epipole as the point of intersection of said epipolar lines.

108. A computer program product as defined in claim 91 in which said epipolar line generator module enables said computer to generate each said epipolar line as the cross product of corresponding columns of two of the three matrices E_j =α

_1j1, α

_1j2, . . . , α

_3j3 (j=1, 2,

     3).

109. A computer program product as defined in claim 96, the computer program product enabling said computer to generate said image from more than three views,

A. said computer program product including a planar view processor module for enabling said computer to identify, for each of a plurality of subsets "m" of three of said planar views, two of said views being the same for all of said subsets "m," a set P_s of at least one point P in the scene which has a projection in all three views of the respective subset;

B. said trilinear tensor generator module enabling said computer to generate, for each subset "m," a trilinear tensor T_m having components α

_ijk,m ;

C. said computer program product further comprising a correspondence module for enabling said computer to process said trilinear tensors T_m in accordance with a rank-4 constraint, thereby to generate a set of processed trilinear tensors T_m '"'"' which are linear related to each other, the image generator utilizing at least one processed trilinear tensor for at least one subset to generate said image instead of the associated trilinear tensor for the same subset.

110. A computer program product as defined in claim 109 in which said each set P_s comprises a plurality of points P, each point P having a projection in all three views of the respective set "m."

111. A computer program product as defined in claim 109 in which each said set P_s comprises seven points P, each point P having a projection in all three views of the respective set "m."

112. A computer program product as defined in claim 109 in which said correspondence module comprises:

A. a correspondence matrix generator module for enabling said computer to generate, for each trilinear tensor T_m associated with a subset of views "m," a two-dimensional correspondence matrix G_m having a plurality of rows and columns, each column "j" of the correspondence matrix G_m containing the elements α

_1j1,m, α

_1j2,m, . . . , α

_3j3,m of the respective trilinear tensor T_m ;

B. a concatenation module for enabling said computer to concatenate the correspondence matrices G_m for the respective subsets together, thereby to generate a concatenated correspondence matrix CG_m ;

C. a rank-4 processing module for enabling said computer to process said concatenated correspondence matrix CG_m in accordance with the rank-4 constraint, thereby to generate a processed concatenated correspondence matrix CG_m ; and

D. a processed trilinear tensor generator module for enabling said computer to generate from the processed concatenated correspondence matrix CG_m the set of processed trilinear tensors T_m '"'"'.

113. A computer program product as defined in claim 112 in which:

A. said concatenation module enables said computer to concatenate the correspondence matrices G_m such that columns of successive ones of the correspondence matrices G_m form successive sets of columns of the concatenated correspondence matrix CG_m ; and

B. said processed trilinear tensor generator module enables said computer to generate each processed trilinear tensor T_m '"'"' associated with a subset "m" from the ones of the set of columns of the concatenated correspondence matrix associated with the correspondence matrix G_m for the same subset "m."