US6009437A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Linear fitting with missing data: applications to structure-from-motion and to characterizing intensity images
Assignee: NEC Corp
•
Filing: 1998-01-06
•
Granted: 1999-12-28
•
Expires: 2018-01-06
Abstract
Abstract A method for generating a complete scene structure from a video sequence that provides incomplete data. The method has a first step of building a first matrix consisting of point locations from a motion sequence by acquiring a sequence of images of a fixed scene using a moving camera; identifying and tracking point features through the sequence; and using the coordinates of the features to build the first matrix with some missing elements where some features are not present in some images. In a second step an approximate solution is built by selecting triples of columns from the first matrix; forming their nullspaces into a second matrix; and taking the three smallest components of the second matrix. In a third step, an iterative algorithm is applied to the three smallest components to build a third matrix and to improve the estimate. Lastly, in a fourth step the third matrix is decomposed to determine the complete scene structure. Another aspect of the present invention are apparatus' for generating a complete scene structure from a video sequence that provides incomplete data utilizing the methods of the of the present invention.
Inventors
- 👤 David W. Jacobs
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:28
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/50; G06T7/55; G06T7/579; G06V; G06V10/00; G06V10/10; G06T2207/00; G06T2207/10; G06T2207/10016; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
151 words
A method for generating a complete scene structure from a video sequence that provides incomplete data, the method comprising the steps of: (a) building a first matrix consisting of point locations from the video sequence by: (i) acquiring a sequence of images of a fixed scene using a moving camera; (ii) identifying and tracking point features through the sequence; and (iii) using the coordinates of the features to build the first matrix with some missing elements where some features are not present in some images; (b) building an approximate solution by: (i) selecting triples of columns from the first matrix; (ii) forming their nullspaces into a second matrix; and (iii) taking the three smallest components of the second matrix; (c) applying an iterative algorithm to the three smallest components to build a third matrix and to improve the estimate; and (d) decomposing the third matrix to determine the complete scene structure.
Claim 2
Independent Claim
151 words
A method for generating a complete scene structure from a video sequence that provides incomplete data, the method comprising the steps of: (a) building a first matrix consisting of point locations from the video sequence by: (i) acquiring a sequence of images of a fixed scene using a moving camera; (ii) identifying and tracking point features through the sequence; and (iii) using the coordinates of the features to build the first matrix with some missing elements where some features are not present in some images; (b) building an approximate solution by: (i) selecting triples of columns from the first matrix; (ii) forming their nullspaces into a second matrix; and (iii) taking the three smallest components of the second matrix; (c) applying an iterative algorithm to the three smallest components to build a third matrix and to improve the estimate; and (d) decomposing the third matrix to determine the complete scene structure.
Claim 3
Dependent Claim
77 words
The method of claim 1, wherein the first matrix is given by the formula: ##EQU6## where Q is a single matrix containing all the tracked image points, each column of which contains all the image coordinates of a single point, and where X i ,j is the X coordinate of the j'th noisy image point in the i'th image and Y i ,j is the Y coordinate of the j'th noisy image point in the i'th image.
Claim 4
Dependent Claim
14 words
The method of claim 1, wherein the triples of columns are selected at random.
Claim 5
Dependent Claim
61 words
The method of claim 1, wherein the second matrix is given by the formula: N=[N.sub.1 N.sub.2 . . . N.sub.1 ] where S i denotes the linear space spanned by the i'th triple of columns, N i denote the nullspace of S i , such that each column of N i represents a vector orthogonal to the space S i .
Claim 6
Dependent Claim
150 words
The method of claim 1, wherein the iterative algorithm is given by the formula: T.sub.i+1 =QP.sub.i.sup.+ where T i is an estimate at iteration i of the matrix T, that represents the camera motion, P i is an estimate at iteration i, of the matrix that represents the scene structure, P i + is the pseudoinverse of P i , and Q is a single matrix containing all the tracked image points, each column of which contains all the image coordinates of a single point, and where X i ,j is the X coordinate of the j'th noisy image point in the i'th image and Y i ,j is the Y coordinate of the j'th noisy image point in the i'th image, such that a series of estimates of Q, T, and P are produced in which the magnitude of Q-Q is non-increasing, where Q represents the complete scene structure.
Claim 7
Dependent Claim
113 words
The method of claim 1, wherein the step of building an approximate solution comprises the substeps of: (a) computing the nullspace of a fully occupied subrectangle of the columns to generate the nullspace of column triples, where the nullspace is disregarded if the subrectangle is substantially degenerate; (b) choosing column triples until their nullspaces are larger than the first matrix by a predetermined constant factor, where all results are judged unreliable if the second matrix has a fourth smallest singular value that is smaller than a predetermined threshold; and (c) heuristically extending the second matrix through a repeated least squares process if an accurate estimate for a subset of the data is provided.
Claim 8
Independent Claim
147 words
A method for generating a complete scene structure from a video sequence that provides incomplete data, the method comprising the steps of: (a) building a first matrix consisting of intensity values from multiple images by: (i) acquiring a series of images of a fixed scene with separate, point light sources; (ii) identifying points in each image that provide unreliable data due to shadowing or specularities; and (iii) building the first matrix of intensity values with missing elements where data is unreliable; (b) building an approximate solution by: (i) selecting triples of columns from the first matrix; (ii) forming their nullspaces into a second matrix; and (iii) taking the three smallest components of the second matrix; (c) applying an iterative algorithm to the three smallest components to build a third matrix and to improve the estimate; and (d) decomposing the third matrix to determine the complete scene structure.
Claim 9
Independent Claim
147 words
A method for generating a complete scene structure from a video sequence that provides incomplete data, the method comprising the steps of: (a) building a first matrix consisting of intensity values from multiple images by: (i) acquiring a series of images of a fixed scene with separate, point light sources; (ii) identifying points in each image that provide unreliable data due to shadowing or specularities; and (iii) building the first matrix of intensity values with missing elements where data is unreliable; (b) building an approximate solution by: (i) selecting triples of columns from the first matrix; (ii) forming their nullspaces into a second matrix; and (iii) taking the three smallest components of the second matrix; (c) applying an iterative algorithm to the three smallest components to build a third matrix and to improve the estimate; and (d) decomposing the third matrix to determine the complete scene structure.
Claim 10
Dependent Claim
109 words
The method of claim 7, wherein the first matrix is given by the formula: Q=HN+E where, Q is a data matrix in which the j'th column gives the intensity of the j'th pixel in every image, E is a matrix of sensing errors, H is a lighting matrix in which the i'th row is the h vector for the i'th image, h is a 3-D vector for the point light source scaled by its intensity, and N is a scene matrix in which the j'th column is p j n j where p j is the surface albedo and n j the surface normal of the 3-D planar patch.
Claim 11
Dependent Claim
14 words
The method of claim 7, wherein the triples of columns are selected at random.
Claim 12
Dependent Claim
61 words
The method of claim 7, wherein the second matrix is given by the formula: N=[N.sub.1 N.sub.2 . . . N.sub.1 ] where S i denotes the linear space spanned by the i'th triple of columns, N i denote the nullspace of S i , such that each column of N i represents a vector orthogonal to the space S i .
Claim 13
Dependent Claim
151 words
The method of claim 7, wherein the iterative algorithm is given by the formula: T.sub.i+1 =QP.sub.i.sup.+ where T i is an estimate at iteration i, of the matrix that represents the lighting, P i is an estimate at iteration i, of the matrix that represents the surface normals at scene points, P i + is the pseudoinverse of P i , and Q is a single matrix containing all the tracked image points, each column of which contains all the image coordinates of a single point, and where X i ,j is the X coordinate of the j'th noisy image point in the i'th image and Y i ,j is the Y coordinate of the j'th noisy image point in the i'th image, such that a series of estimates of Q, T and P are produced in which the magnitude of Q-Q is non-increasing, where Q represents the complete scene structure.
Claim 14
Dependent Claim
113 words
The method of claim 7, wherein the step of building an approximate solution comprises the substeps of: (a) computing the nullspace of a fully occupied subrectangle of the columns to generate the nullspace of column triples, where the nullspace is disregarded if the subrectangle is substantially degenerate; (b) choosing column triples until their nullspaces are larger than the first matrix by a predetermined constant factor, where all results are judged unreliable if the second matrix has a fourth smallest singular value that is smaller than a predetermined threshold; and (c) heuristically extending the second matrix through a repeated least squares process if an accurate estimate for a subset of the data is provided.
Claim 15
Independent Claim
139 words
An apparatus for generating a complete scene structure from a video sequence that provides incomplete data, the apparatus comprising: a camera for acquiring a sequence of images of a fixed scene; means for identifying and tracking point features through the sequence; and computing means for building a first matrix consisting of point locations from a motion sequence; building the first matrix with some missing elements using the coordinates of the features where some features are not present in some images; building an approximate solution comprising: selecting triples of columns from the first matrix; forming their nullspaces into a second matrix; taking the three smallest components of the second matrix; applying an iterative algorithm to the three smallest components to build a third matrix and to improve the estimate; and decomposing the third matrix to determine the complete scene structure.
Claim 16
Independent Claim
139 words
An apparatus for generating a complete scene structure from a video sequence that provides incomplete data, the apparatus comprising: a camera for acquiring a sequence of images of a fixed scene; means for identifying and tracking point features through the sequence; and computing means for building a first matrix consisting of point locations from a motion sequence; building the first matrix with some missing elements using the coordinates of the features where some features are not present in some images; building an approximate solution comprising: selecting triples of columns from the first matrix; forming their nullspaces into a second matrix; taking the three smallest components of the second matrix; applying an iterative algorithm to the three smallest components to build a third matrix and to improve the estimate; and decomposing the third matrix to determine the complete scene structure.
Claim 17
Dependent Claim
12 words
The apparatus of claim 13, wherein computing means is a personal computer.
Claim 18
Independent Claim
138 words
An apparatus for generating a complete scene structure from a video sequence that provides incomplete data, the apparatus comprising: a plurality of discrete point light sources for acquiring a series of images of a fixed scene; and computing means for building a first matrix consisting of intensity values from multiple images; identifying points in each image that provide unreliable data due to shadowing or specularities; building the first matrix of intensity values with missing elements where data is unreliable; building an approximate solution comprising: selecting triples of columns from the first matrix; forming their nullspaces into a second matrix; taking the three smallest components of the second matrix; applying an iterative algorithm to the three smallest components to build a third matrix and to improve the estimate; and decomposing the third matrix to determine the complete scene structure.
Claim 19
Independent Claim
138 words
An apparatus for generating a complete scene structure from a video sequence that provides incomplete data, the apparatus comprising: a plurality of discrete point light sources for acquiring a series of images of a fixed scene; and computing means for building a first matrix consisting of intensity values from multiple images; identifying points in each image that provide unreliable data due to shadowing or specularities; building the first matrix of intensity values with missing elements where data is unreliable; building an approximate solution comprising: selecting triples of columns from the first matrix; forming their nullspaces into a second matrix; taking the three smallest components of the second matrix; applying an iterative algorithm to the three smallest components to build a third matrix and to improve the estimate; and decomposing the third matrix to determine the complete scene structure.
Claim 20
Dependent Claim
13 words
The apparatus of claim 15, wherein the computing means is a personal computer.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-27 | 2003-06-28 | 2003-12-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-27 | 2007-06-28 | 2007-12-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-27 | 2011-06-28 | 2011-12-28 | $7700.00 | Window Closed / Lapsed |