US6084592A — Interactive construction of 3D models from panora…

Claim 1

Independent Claim 187 words

A computer-implemented process to construct a model of a 3D scene from a panoramic view of the scene, comprising using a computer to perform the following steps: displaying an image of the panoramic view of the 3D scene as a screen image; recovering a camera orientation matrix of the panoramic view based on lines associated with at least one plane of the 3D scene as specified by a user of the computer-implemented process; estimating plane normals and line directions for planes in the 3D scene which are to be modeled using the camera orientation matrix; recovering a camera translation using the camera orientation matrix, wherein the camera translation is the difference between the camera projection center and the coordinate origin of the 3D scene; estimating unknown plane distances and vertex point locations for each plane in the 3D scene which is to be modeled using the estimated plane normals and line directions; constructing a model of the 3D scene consisting of at least one set of connected planes based on the plane normal and plane distance, and/or the vertex point locations, of each plane in the set.

Claim 2

Dependent Claim 187 words

A computer-implemented process to construct a model of a 3D scene from a panoramic view of the scene, comprising using a computer to perform the following steps: displaying an image of the panoramic view of the 3D scene as a screen image; recovering a camera orientation matrix of the panoramic view based on lines associated with at least one plane of the 3D scene as specified by a user of the computer-implemented process; estimating plane normals and line directions for planes in the 3D scene which are to be modeled using the camera orientation matrix; recovering a camera translation using the camera orientation matrix, wherein the camera translation is the difference between the camera projection center and the coordinate origin of the 3D scene; estimating unknown plane distances and vertex point locations for each plane in the 3D scene which is to be modeled using the estimated plane normals and line directions; constructing a model of the 3D scene consisting of at least one set of connected planes based on the plane normal and plane distance, and/or the vertex point locations, of each plane in the set.

Claim 3

Dependent Claim 74 words

The process of claim 1, wherein the camera orientation matrix recovery step comprises the steps of: the user designating lines on at least one plane in the screen image of the panoramic view of the 3D scene; the user identifying the direction of lines in the 3D scene which correspond to each of the designated lines in the screen image; and determining the camera orientation matrix using the designated lines and identified line directions.

Claim 4

Dependent Claim 70 words

The process of claim 2, wherein the camera orientation matrix recovery step further comprises the steps of: ascertaining whether the user has designated a sufficient number of lines on the at least one plane to determine the camera orientation matrix; and prompting the user to designate additional lines on the at least one plane whenever it is ascertained there are not a sufficient number to determine the camera orientation matrix.

Claim 5

Dependent Claim 89 words

The process of claim 3, wherein the ascertaining step comprises ascertaining whether the user has designated one of (i) lines on a plane corresponding to at least two vertical lines and one horizontal line of the 3D scene, (ii) lines on a plane corresponding to at least two horizontal lines and one vertical line of the 3D scene, or (iii) lines on planes corresponding to at least two sets of parallel lines of the 3D scene and the direction of each set of parallel lines in the 3D scene.

Claim 6

Dependent Claim 43 words

The process of claim 2, wherein the determining step comprises the step of deriving the camera orientation matrix from lines on a plane corresponding to at least two vertical lines and one horizontal line of the 3D scene, as designated by the user.

Claim 7

Dependent Claim 148 words

The process of claim 5, wherein the deriving step comprises the steps of: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two vertical lines and one horizontal line designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a Z-axis element of the camera orientation matrix using the computed projection plane normals associated with each of the designated vertical lines; computing an X-axis element of the camera orientation matrix using the computed Z-axis element and the projection plane normal associated with the designated horizontal line; and computing a Y-axis element of the camera orientation matrix using the computed Z-axis and X-axis elements.

Claim 8

Dependent Claim 38 words

The process of claim 6, wherein the user designated more than two vertical lines on the plane, and wherein the step of computing the Z-axis element of the camera orientation matrix comprises using a minimum eigenvalue problem approach.

Claim 9

Dependent Claim 32 words

The process of claim 6, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 10

Dependent Claim 43 words

The process of claim 2, wherein the determining step comprises the step of deriving the camera orientation matrix from lines on a plane corresponding to at least two horizontal lines and one vertical line of the 3D scene, as designated by the user.

Claim 11

Dependent Claim 148 words

The process of claim 9, wherein the deriving step comprises the steps of: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two horizontal lines and one vertical line designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing an X-axis element of the camera orientation matrix using the computed projection plane normals associated with each of the designated horizontal lines; computing a Z-axis element of the camera orientation matrix using the computed X-axis element and the projection plane normal associated with the designated vertical line; and computing a Y-axis element of the camera orientation matrix using the computed X-axis and Z-axis elements.

Claim 12

Dependent Claim 38 words

The process of claim 10, wherein the user designated more than two horizontal lines on the plane, and wherein the step of computing the X-axis element of the camera orientation matrix comprises using a minimum eigenvalue problem approach.

Claim 13

Dependent Claim 32 words

The process of claim 10, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 14

Dependent Claim 49 words

The process of claim 2, wherein the determining step comprises the step of deriving the camera orientation matrix from at least two sets of parallel lines on one or more planes and the direction of each of the parallel lines in the 3D scene, as designated by the user.

Claim 15

Dependent Claim 152 words

The process of claim 13, wherein the deriving step comprises the steps of: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two sets of parallel lines designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for each set of parallel lines in the panoramic view using the computed projection plane normals associated with that set of parallel lines; computing the camera orientation matrix from the computed panoramic view line direction for each set of parallel lines and the line direction of each corresponding set of parallel lines in the 3D scene as designated by the user using a maximum eigenvalue problem approach.

Claim 16

Dependent Claim 46 words

The process of claim 14, wherein the user designated more than two parallel lines in a set of parallel lines, and wherein the step of computing a line direction for each set of parallel lines in the panoramic view comprises using a minimum eigenvector problem approach.

Claim 17

Dependent Claim 32 words

The process of claim 14, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 18

Dependent Claim 51 words

The process of claim 2 wherein an element of the determined camera orientation matrix may be reversed in sign in comparison to the actual camera orientation matrix, and wherein the camera orientation matrix recovery step further comprises the step of resolving any sign ambiguity existing in the determined camera orientation matrix.

Claim 19

Dependent Claim 34 words

The process of claim 17 wherein the resolving step comprises the user specifying the direction of each previously designated line associated with a plane as it appears in the panoramic view of the scene.

Claim 20

Dependent Claim 122 words

The process of claim 17 wherein the resolving step comprises the steps of: the user specifying the 3D scene coordinates of at least two points identified by the user in the screen image; computing the 3D scene coordinates of the points identified by the user in the screen image by projecting the panoramic view coordinates of these points obtained from the screen image to the 3D scene using the camera orientation matrix; comparing the computed 3D scene coordinates with the coordinates specified by the user; and reversing the sign of any of the determined camera orientation matrix elements corresponding to a computed 3D scene coordinate element that has a different sign than the corresponding 3D scene coordinate element specified by the user.

Claim 21

Dependent Claim 109 words

The process of claim 1, wherein the step of estimating plane normals and line directions for planes in the 3D scene comprises the steps of: the user designating lines on each plane in the screen image of the panoramic view which is to be modeled; deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image using the camera orientation matrix; and deriving a normal for each plane in the 3D scene that corresponds to a plane of the screen image on which the user has designated lines, using the derived 3D scene line directions associated with that plane.

Claim 22

Dependent Claim 109 words

The process of claim 20, wherein the step of estimating plane normals and line directions for planes in the 3D scene further comprises the steps of: ascertaining whether the user has designated a sufficient number of lines on the at least one plane in the screen image to derive the line directions and plane normal associated with the corresponding plane in the 3D scene; and prompting the user to designate additional lines on the at least one plane in the screen image whenever it is ascertained there are not a sufficient number to derive the line directions and plane normal associated with the corresponding plane in the 3D scene.

Claim 23

Dependent Claim 41 words

The process of claim 21, wherein the ascertaining step comprises ascertaining whether the user has designated one of (i) at least two sets of parallel lines on the plane, or (ii) at least three lines of a rectangle on the plane.

Claim 24

Dependent Claim 65 words

The process of claim 20, wherein the step of deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image comprises deriving the direction of lines on planes to be modeled in the 3D scene using two pairs of parallel lines designated by the user as being on the corresponding plane in the screen image.

Claim 25

Dependent Claim 159 words

The process of claim 23, wherein the step of deriving the direction of lines on planes to be modeled in the 3D scene comprises the steps of: identifying the coordinates of two points on each line in the panoramic view that corresponds to the two pairs of parallel lines designated by the user in the screen image; computing a normal for each of the projection planes associated with the two pairs of parallel lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for each pair of parallel lines in the panoramic view using the computed projection plane normals associated with that pair of parallel lines; and computing the line direction in each plane in the 3D scene corresponding to each pair of parallel lines in the panoramic view using the computed panoramic view line directions and the camera orientation matrix.

Claim 26

Dependent Claim 32 words

The process of claim 24, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 27

Dependent Claim 65 words

The process of claim 20, wherein the step of deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image comprises deriving the direction of lines on planes to be modeled in the 3D scene using three lines of a rectangle designated by the user as being on the corresponding plane in the screen image.

Claim 28

Dependent Claim 256 words

The process of claim 26, wherein the step of deriving the direction of lines on planes to be modeled in the 3D scene comprises the steps of: identifying the coordinates of two points on each line in the panoramic view that corresponds to the three lines of the rectangle designated by the user in the screen image; computing a normal for each of the projection planes associated with the three lines of the rectangle in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for two lines of the three lines of the rectangle in the panoramic view that are parallel using the computed projection plane normals associated with the pair of parallel lines; and computing the line direction in each plane in the 3D scene corresponding to the pair of parallel lines in the panoramic view using the computed panoramic view line direction and the camera orientation matrix; computing a 3D scene projection of the projection plane normal associated with the remaining, non-parallel line of the three lines of the rectangle using the camera orientation matrix; computing a line direction for a line in the 3D scene corresponding to the remaining, non-parallel line of the three lines of the rectangle in the panoramic view using the previously computed line direction of the pair of parallel lines in the 3D scene and the previously computed 3D scene projection of the projection plane normal associated with the remaining, non-parallel line.

Claim 29

Dependent Claim 32 words

The process of claim 27, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 30

Dependent Claim 200 words

The process of claim 1, wherein the step of recovering the camera translation comprises the steps of: the user specifying the 3D scene coordinates of at least two points identified by the user in the screen image; characterizing the conversion of a point in the 3D scene to a corresponding point in the panoramic view using the relationship, (x-t)×R T x'=0, which is equivalent to, (x-t)·(R T p j ')=0, j=0,1,2 where x represents the coordinates of a point in the 3D scene, t represents the camera translation, R represents the camera orientation matrix, x' represents the coordinates of a point in the panoramic view which corresponds to a point x in the 3D scene and p 0 '=(-x 2 , x.sub. 1, 0), p 1 '=(-x 3 , 0, x 1 ) and p 2 '=(0, -x 3 , x 2 ) represent three directions perpendicular to a ray from the camera center through the point x'=(x 1 , x 2 , x 3 ); creating a system of linear equation based on the characterizing relationship using the at least two user specified points; and estimating the camera translation from the system of linear equations using a least-squares approach.

Claim 31

Dependent Claim 212 words

The process of claim 1, wherein the step of estimating plane distances and vertex point locations for each plane in the 3D scene which is to be modeled comprises the steps of: the user designating ones of, 3D scene coordinates of points corresponding to points identified by the user in the screen image, plane normals associated with planes in the 3D scene that correspond to planes identified by the user in the screen image, directions of lines in the 3D scene that correspond to lines identified by the user in the screen image, plane distances associated with planes in the 3D scene that correspond to planes identified by the user in the screen image, and planes in the screen image that correspond to parallel planes of the 3D scene; characterizing the 3D scene as at least one set of connected planes, each set being subject to a series of geometric constraints; creating a system of linear geometric constraint equations based on the characterizing constraints for each set of connected planes in the 3D scene which are to be modeled; and estimating the unknown plane distances and vertex points for each set of connected planes in the 3D scene which is to be modeled from the system of equations using a least-squares approach.

Claim 32

Dependent Claim 279 words

The process of claim 30, wherein the system of constraints employed in the characterizing step comprises: ______________________________________ Known point x.sub.i.sup.", Known plane d.sub.i.sup.", Distance Parallel planes d.sub.i - d.sub.j = Const., Point/model (x - t) · p.sub.j = 0, Point/plane x.sub.i · n.sub.k.sup." + d.sub.k = 0, Point/plane x.sub.i · n.sub.k + d.sub.k = 0, Points/line (x.sub.i - x.sub.j) × m" = 0, Points/line (x.sub.i - x.sub.j) × m = 0, Known length x.sub.i - x.sub.j = cm", Known length x.sub.i - x.sub.j = cm ______________________________________ where x" represents the coordinates of a point in the 3D scene designated by the user and x represents the unknown coordinates of a point in the 3D scene, d" represents a distance from the origin of the 3D scene to a plane in the scene as designated by the user and d represents an unknown distance from the origin of the 3D scene to a plane in the scene, t represents the camera translation, p j represents p 0 =(-x 2 , x 1 , 0), p 1 =(-x 3 , 0, x 1 ) and p 2 =(0, -x 3 , x 2 ) which correspond to three directions perpendicular to a ray from the camera center through the point x=(x 1 , x 2 , x 3 ), n" represents a normal of a plane in the 3D scene designated by the user and n represents the estimated normal of a plane in the 3D scene, m" represents a direction of a line in the 3D scene designated by the user and m represents the estimated direction of a line in the 3D scene, and c represents a scaling factor.

Claim 33

Dependent Claim 40 words

The process of claim 31, wherein the creating step comprises using the user designated points, plane normals, line directions, plane distances and parallel planes, as well as the estimated plane normals and line directions to create the system of equations.

Claim 34

Dependent Claim 30 words

The process of claim 32 wherein the camera translation has been previously estimated and the creating step further comprises using the estimated camera translation to create the system of equations.

Claim 35

Dependent Claim 32 words

The process of claim 32, wherein the camera translation is unknown and estimated along with the unknown plane distances and vertex point locations from the system of equations using the least-squares approach.

Claim 36

Independent Claim 211 words

A system for constructing a model of a 3D scene from a panoramic view of the scene, comprising: a general purpose computing device; and a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to, display an image of the panoramic view of the 3D scene on a computer monitor screen, recover a camera orientation matrix of the panoramic view based on lines associated with at least one plane of the 3D scene as specified by a user of the computing device, estimate plane normals and line directions for planes in the 3D scene which are to be modeled using the camera orientation matrix, recover a camera translation using the camera orientation matrix, wherein the camera translation is the difference between the camera projection center and the coordinate origin of the 3D scene, estimate unknown plane distances and vertex point locations for each plane in the 3D scene which is to be modeled using the estimated plane normals and line directions, construct a model of the 3D scene consisting of at least one set of connected planes based on the plane normal and plane distance, and/or the vertex point locations, of each plane in the set.

Claim 37

Independent Claim 211 words

A system for constructing a model of a 3D scene from a panoramic view of the scene, comprising: a general purpose computing device; and a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to, display an image of the panoramic view of the 3D scene on a computer monitor screen, recover a camera orientation matrix of the panoramic view based on lines associated with at least one plane of the 3D scene as specified by a user of the computing device, estimate plane normals and line directions for planes in the 3D scene which are to be modeled using the camera orientation matrix, recover a camera translation using the camera orientation matrix, wherein the camera translation is the difference between the camera projection center and the coordinate origin of the 3D scene, estimate unknown plane distances and vertex point locations for each plane in the 3D scene which is to be modeled using the estimated plane normals and line directions, construct a model of the 3D scene consisting of at least one set of connected planes based on the plane normal and plane distance, and/or the vertex point locations, of each plane in the set.

Claim 38

Dependent Claim 77 words

The system of claim 35, wherein the user designates lines on at least one plane in the screen image of the panoramic view of the 3D scene and identifies the direction of lines in the 3D scene which correspond to each of the designated lines in the screen image, and wherein the program module for recovering the camera orientation matrix comprises a sub-module for determining the camera orientation matrix using the designated lines and identified line directions.

Claim 39

Dependent Claim 72 words

The system of claim 36, wherein the program module for recovering the camera orientation matrix further comprises sub-modules for: ascertaining whether the user has designated a sufficient number of lines on the at least one plane to determine the camera orientation matrix; and prompting the user to designate additional lines on the at least one plane whenever it is ascertained there are not a sufficient number to determine the camera orientation matrix.

Claim 40

Dependent Claim 92 words

The system of claim 37, wherein the ascertaining sub-module comprises a sub-module for ascertaining whether the user has designated one of (i) lines on a plane corresponding to at least two vertical lines and one horizontal line of the 3D scene, (ii) lines on a plane corresponding to at least two horizontal lines and one vertical line of the 3D scene, or (iii) lines on planes corresponding to at least two sets of parallel lines of the 3D scene and the direction of each set of parallel lines in the 3D scene.

Claim 41

Dependent Claim 43 words

The system of claim 36, wherein the determining sub-module comprises a sub-module for deriving the camera orientation matrix from lines on a plane corresponding to at least two vertical lines and one horizontal line of the 3D scene, as designated by the user.

Claim 42

Dependent Claim 147 words

The system of claim 39, wherein the deriving sub-module comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two vertical lines and one horizontal line designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a Z-axis element of the camera orientation matrix using the computed projection plane normals associated with each of the designated vertical lines; computing an X-axis element of the camera orientation matrix using the computed Z-axis element and the projection plane normal associated with the designated horizontal line; and computing a Y-axis element of the camera orientation matrix using the computed Z-axis and X-axis elements.

Claim 43

Dependent Claim 46 words

The system of claim 40, wherein the user designated more than two vertical lines on the plane, and wherein the sub-module for computing the Z-axis element of the camera orientation matrix comprises a sub-module for using a minimum eigenvalue problem approach to compute the Z-axis element.

Claim 44

Dependent Claim 32 words

The system of claim 40, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 45

Dependent Claim 42 words

The system of claim 36, wherein the determining sub-module comprises a sub-module for deriving the camera orientation matrix from lines a plane corresponding to at least two horizontal lines and one vertical line of the 3D scene, as designated by the user.

Claim 46

Dependent Claim 147 words

The system of claim 43, wherein the deriving sub-module comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two horizontal lines and one vertical line designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing an X-axis element of the camera orientation matrix using the computed projection plane normals associated with each of the designated horizontal lines; computing a Z-axis element of the camera orientation matrix using the computed X-axis element and the projection plane normal associated with the designated vertical line; and computing a Y-axis element of the camera orientation matrix using the computed X-axis and Z-axis elements.

Claim 47

Dependent Claim 46 words

The system of claim 48, wherein the user designated more than two horizontal lines on the plane, and wherein the sub-module for computing the X-axis element of the camera orientation matrix comprises a sub-module for using a minimum eigenvalue problem approach to compute the X-axis element.

Claim 48

Dependent Claim 32 words

The system of claim 44, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 49

Dependent Claim 49 words

The system of claim 36, wherein the determining sub-module comprises a sub-module for deriving the camera orientation matrix from at least two sets of parallel lines on one or more planes and the direction of each of the parallel lines in the 3D scene, as designated by the user.

Claim 50

Dependent Claim 151 words

The system of claim 47, wherein the deriving sub-module comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two sets of parallel lines designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for each set of parallel lines in the panoramic view using the computed projection plane normals associated with that set of parallel lines; computing the camera orientation matrix from the computed panoramic view line direction for each set of parallel lines and the line direction of each corresponding set of parallel lines in the 3D scene as designated by the user using a maximum eigenvalue problem approach.

Claim 51

Dependent Claim 60 words

The system of claim 48, wherein the user designated more than two parallel lines in a set of parallel lines, and wherein the sub-module for computing a line direction for each set of parallel lines in the panoramic view comprises a sub-module for using a minimum eigenvector problem approach to compute the line direction for each set of parallel lines.

Claim 52

Dependent Claim 32 words

The system of claim 48, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 53

Dependent Claim 51 words

The system of claim 36 wherein an element of the determined camera orientation matrix may be reversed in sign in comparison to the actual camera orientation matrix, and wherein the camera orientation matrix recovery sub-module further comprises a sub-module for resolving any sign ambiguity existing in the determined camera orientation matrix.

Claim 54

Dependent Claim 34 words

The system of claim 51, wherein the user specifies the direction of each previously designated line associated with a plane of the 3D scene as it appears in the panoramic view of the scene.

Claim 55

Dependent Claim 123 words

The system of claim 51, wherein the user specifies the 3D scene coordinates of at least two points identified by the user in the screen image and the resolving sub-module comprises a sub-modules for: computing the 3D scene coordinates of the points identified by the user in the screen image by projecting the panoramic view coordinates of these points obtained from the screen image to the 3D scene using the camera orientation matrix; comparing the computed 3D scene coordinates with the coordinates specified by the user; and reversing the sign of any of the determined camera orientation matrix elements corresponding to a computed 3D scene coordinate element that has a different sign than the corresponding 3D scene coordinate element specified by the user.

Claim 56

Dependent Claim 110 words

The system of claim 35, wherein the user designates lines on each plane in the screen image of the panoramic view which is to be modeled, and the program module for estimating plane normals and line directions for planes in the 3D scene comprises sub-modules for: deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image using the camera orientation matrix; and deriving a normal for each plane in the 3D scene that corresponds to a plane of the screen image on which the user has designated lines, using the derived 3D scene line directions associated with that plane.

Claim 57

Dependent Claim 103 words

The system of claim 54, wherein the program module for estimating plane normals and line directions for planes in the 3D scene further comprises sub-modules for: ascertaining whether the user has designated a sufficient number of lines on a plane in the screen image to derive the line directions and plane normal associated with the corresponding plane in the 3D scene; and prompting the user to designate additional lines on a plane in the screen image whenever it is ascertained there are not a sufficient number to derive the line directions and plane normal associated with the corresponding plane in the 3D scene.

Claim 58

Dependent Claim 44 words

The system of claim 55, wherein the ascertaining sub-module comprises a sub-module for ascertaining whether the user has designated one of (i) at least two sets of parallel lines on the plane, or (ii) at least three lines of a rectangle on the plane.

Claim 59

Dependent Claim 68 words

The system of claim 54, wherein the sub-module for deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image comprises a sub-module for deriving the direction of lines on planes to be modeled in the 3D scene using two pairs of parallel lines designated by the user as being on the corresponding plane in the screen image.

Claim 60

Dependent Claim 158 words

The system of claim 57, wherein the sub-module for deriving the direction of lines on planes to be modeled in the 3D scene comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the two pairs of parallel lines designated by the user in the screen image; computing a normal for each of the projection planes associated with the two pairs of parallel lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for each pair of parallel lines in the panoramic view using the computed projection plane normals associated with that pair of parallel lines; and computing the line direction in each plane in the 3D scene corresponding to each pair of parallel lines in the panoramic view using the computed panoramic view line directions and the camera orientation matrix.

Claim 61

Dependent Claim 32 words

The system of claim 58, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 62

Dependent Claim 68 words

The system of claim 54, wherein the sub-module for deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image comprises a sub-module for deriving the direction of lines on planes to be modeled in the 3D scene using three lines of a rectangle designated by the user as being on the corresponding plane in the screen image.

Claim 63

Dependent Claim 255 words

The system of claim 60, wherein the sub-module for deriving the direction of lines on planes to be modeled in the 3D scene comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the three lines of the rectangle designated by the user in the screen image; computing a normal for each of the projection planes associated with the three lines of the rectangle in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for two lines of the three lines of the rectangle in the panoramic view that are parallel using the computed projection plane normals associated with the pair of parallel lines; and computing the line direction in each plane in the 3D scene corresponding to the pair of parallel lines in the panoramic view using the computed panoramic view line direction and the camera orientation matrix; computing a 3D scene projection of the projection plane normal associated with the remaining, non-parallel line of the three lines of the rectangle using the camera orientation matrix; computing a line direction for a line in the 3D scene corresponding to the remaining, non-parallel line of the three lines of the rectangle in the panoramic view using the previously computed line direction of the pair of parallel lines in the 3D scene and the previously computed 3D scene projection of the projection plane normal associated with the remaining, non-parallel line.

Claim 64

Dependent Claim 32 words

The system of claim 61, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 65

Dependent Claim 202 words

The system of claim 35, wherein the user specifies the 3D scene coordinates of at least two points identified by the user in the screen image, and the program module for recovering the camera translation comprises sub-modules for: characterizing the conversion of a point in the 3D scene to a corresponding point in the panoramic view using the relationship, (x-t)×R T x'=0, which is equivalent to, (x-t)·(R T p j ')=0, j=0,1,2 where x represents the coordinates of a point in the 3D scene, t represents the camera translation, R represents the camera orientation matrix, x' represents the coordinates of a point in the panoramic view which corresponds to a point x in the 3D scene and p 0 '=(-x 2 , x 1 , 0), p 1 '=(-x 3 , 0, x 1 ) and p 2 "=(0, -x 3 , x 2 ) represent three directions perpendicular to a ray from the camera center through the point x'=(x 1 , x 2 , x 3 ); creating a system of linear equation based on the characterizing relationship using the at least two user specified points; and estimating the camera translation from the system of linear equations using a least-squares approach.

Claim 66

Dependent Claim 214 words

The system of claim 35, wherein the user designates ones of, 3D scene coordinates of points corresponding to points identified by the user in the screen image, plane normals associated with planes in the 3D scene that correspond to planes identified by the user in the screen image, directions of lines in the 3D scene that correspond to lines identified by the user in the screen image, plane distances associated with planes in the 3D scene that correspond to planes identified by the user in the screen image, and planes in the screen image that correspond to parallel planes of the 3D scene, and wherein the program module for estimating plane distances and vertex point locations for each plane in the 3D scene which is to be modeled comprises sub-modules for: characterizing the 3D scene as at least one set of connected planes, each set being subject to a series of geometric constraints; creating a system of linear geometric constraint equations based on the characterizing constraints for each set of connected planes in the 3D scene which are to be modeled; and estimating the unknown plane distances and vertex points for each set of connected planes in the 3D scene which is to be modeled from the system of equations using a least-squares approach.

Claim 67

Dependent Claim 279 words

The system of claim 64, wherein the system of constraints employed in the characterizing step comprises: ______________________________________ Known point x.sub.i.sup.", Known plane d.sub.i.sup.", Distance Parallel planes d.sub.i - d.sub.j = Const., Point/model (x - t) · p.sub.j = 0, Point/plane x.sub.i · n.sub.k.sup." + d.sub.k = 0, Point/plane x.sub.i · n.sub.k + d.sub.k = 0, Points/line (x.sub.i - x.sub.j) × m" = 0, Points/line (x.sub.i - x.sub.j) × m = 0, Known length x.sub.i - x.sub.j = cm", Known length x.sub.i - x.sub.j = cm ______________________________________ where x" represents the coordinates of a point in the 3D scene designated by the user and x represents the unknown coordinates of a point in the 3D scene, d" represents a distance from the origin of the 3D scene to a plane in the scene as designated by the user and d represents an unknown distance from the origin of the 3D scene to a plane in the scene, t represents the camera translation, p j represents p 0 =(-x 2 , x 1 , 0), p 1 =(-x 3 , 0, x 1 ) and p 2 =(0, -x 3 , x 2 ) which correspond to three directions perpendicular to a ray from the camera center through the point x=(x 1 , x 2 , x 3 ), n" represents a normal of a plane in the 3D scene designated by the user and n represents the estimated normal of a plane in the 3D scene, m" represents a direction of a line in the 3D scene designated by the user and m represents the estimated direction of a line in the 3D scene, and c represents a scaling factor.

Claim 68

Dependent Claim 44 words

The system of claim 65, wherein the creating sub-module comprises a sub-module for using the user designated points, plane normals, line directions, plane distances and parallel plane designations, as well as the estimated plane normals and line directions to create the system of equations.

Claim 69

Dependent Claim 33 words

The system of claim 66, wherein the camera translation has been previously estimated and the creating sub-module further comprises a sub-module for using the estimated camera translation to create the system of equations.

Claim 70

Dependent Claim 32 words

The system of claim 66, wherein the camera translation is unknown and estimated along with the unknown plane distances and vertex point locations from the system of equations using the least-squares approach.

Claim 71

Dependent Claim 213 words

A computer-readable memory for constructing a model of a 3D scene from a panoramic view of the scene, comprising: a computer-readable storage medium; and a computer program comprising program modules stored in the storage medium, wherein the storage medium is so configured by the computer program that it causes the computer to, display an image of the panoramic view of the 3D scene on a computer monitor screen, recover a camera orientation matrix of the panoramic view based on lines associated with at least one plane of the 3D scene as specified by a user of the computing device, estimate plane normals and line directions for planes in the 3D scene which are to be modeled using the camera orientation matrix, recover a camera translation using the camera orientation matrix, wherein the camera translation is the difference between the camera projection center and the coordinate origin of the 3D scene, estimate unknown plane distances and vertex point locations for each plane in the 3D scene which is to be modeled using the estimated plane normals and line directions, construct a model of the 3D scene consisting of at least one set of connected planes based on the plane normal and plane distance, and/or the vertex point locations, of each plane in the set.

Claim 72

Dependent Claim 213 words

A computer-readable memory for constructing a model of a 3D scene from a panoramic view of the scene, comprising: a computer-readable storage medium; and a computer program comprising program modules stored in the storage medium, wherein the storage medium is so configured by the computer program that it causes the computer to, display an image of the panoramic view of the 3D scene on a computer monitor screen, recover a camera orientation matrix of the panoramic view based on lines associated with at least one plane of the 3D scene as specified by a user of the computing device, estimate plane normals and line directions for planes in the 3D scene which are to be modeled using the camera orientation matrix, recover a camera translation using the camera orientation matrix, wherein the camera translation is the difference between the camera projection center and the coordinate origin of the 3D scene, estimate unknown plane distances and vertex point locations for each plane in the 3D scene which is to be modeled using the estimated plane normals and line directions, construct a model of the 3D scene consisting of at least one set of connected planes based on the plane normal and plane distance, and/or the vertex point locations, of each plane in the set.

Claim 73

Dependent Claim 78 words

The computer-readable memory of claim 69, wherein the user designates lines on at least one plane in the screen image of the panoramic view of the 3D scene and identifies the direction of lines in the 3D scene which correspond to each of the designated lines in the screen image, and wherein the program module for recovering the camera orientation matrix comprises a sub-module for determining the camera orientation matrix using the designated lines and identified line directions.

Claim 74

Dependent Claim 73 words

The computer-readable memory of claim 70, wherein the program module for recovering the camera orientation matrix further comprises sub-modules for: ascertaining whether the user has designated a sufficient number of lines on the at least one plane to determine the camera orientation matrix; and prompting the user to designate additional lines on the at least one plane whenever it is ascertained there are not a sufficient number to determine the camera orientation matrix.

Claim 75

Dependent Claim 93 words

The computer-readable memory of claim 71, wherein the ascertaining sub-module comprises a sub-module for ascertaining whether the user has designated one of (i) lines on a plane corresponding to at least two vertical lines and one horizontal line of the 3D scene, (ii) lines on a plane corresponding to at least two horizontal lines and one vertical line of the 3D scene, or (iii) lines on planes corresponding to at least two sets of parallel lines of the 3D scene and the direction of each set of parallel lines in the 3D scene.

Claim 76

Dependent Claim 44 words

The computer-readable memory of claim 70, wherein the determining sub-module comprises a sub-module for deriving the camera orientation matrix from lines on a plane corresponding to at least two vertical lines and one horizontal line of the 3D scene, as designated by the user.

Claim 77

Dependent Claim 148 words

The computer-readable memory of claim 73, wherein the deriving sub-module comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two vertical lines and one horizontal line designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a Z-axis element of the camera orientation matrix using the computed projection plane normals associated with each of the designated vertical lines; computing an X-axis element of the camera orientation matrix using the computed Z-axis element and the projection plane normal associated with the designated horizontal line; and computing a Y-axis element of the camera orientation matrix using the computed Z-axis and X-axis elements.

Claim 78

Dependent Claim 47 words

The computer-readable memory of claim 74, wherein the user designated more than two vertical lines on the plane, and wherein the sub-module for computing the Z-axis element of the camera orientation matrix comprises a sub-module for using a minimum eigenvalue problem approach to compute the Z-axis element.

Claim 79

Dependent Claim 33 words

The computer-readable memory of claim 74, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 80

Dependent Claim 44 words

The computer-readable memory of claim 70, wherein the determining sub-module comprises a sub-module for deriving the camera orientation matrix from lines on a plane corresponding to at least two horizontal lines and one vertical line of the 3D scene, as designated by the user.

Claim 81

Dependent Claim 148 words

The computer-readable memory of claim 77, wherein the deriving sub-module comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two horizontal lines and one vertical line designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing an X-axis element of the camera orientation matrix using the computed projection plane normals associated with each of the designated horizontal lines; computing a Z-axis element of the camera orientation matrix using the computed X-axis element and the projection plane normal associated with the designated vertical line; and computing a Y-axis element of the camera orientation matrix using the computed X-axis and Z-axis elements.

Claim 82

Dependent Claim 47 words

The computer-readable memory of claim 78, wherein the user designated more than two horizontal lines on the plane, and wherein the sub-module for computing the X-axis element of the camera orientation matrix comprises a sub-module for using a minimum eigenvalue problem approach to compute the X-axis element.

Claim 83

Dependent Claim 33 words

The computer-readable memory of claim 78, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 84

Dependent Claim 50 words

The computer-readable memory of claim 70, wherein the determining sub-module comprises a sub-module for deriving the camera orientation matrix from at least two sets of parallel lines on one or more planes and the direction of each of the parallel lines in the 3D scene, as designated by the user.

Claim 85

Dependent Claim 152 words

The computer-readable memory of claim 81, wherein the deriving sub-module comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two sets of parallel lines designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for each set of parallel lines in the panoramic view using the computed projection plane normals associated with that set of parallel lines; computing the camera orientation matrix from the computed panoramic view line direction for each set of parallel lines and the line direction of each corresponding set of parallel lines in the 3D scene as designated by the user using a maximum eigenvalue problem approach.

Claim 86

Dependent Claim 61 words

The computer-readable memory of claim 82, wherein the user designated more than two parallel lines in a set of parallel lines, and wherein the sub-module for computing a line direction for each set of parallel lines in the panoramic view comprises a sub-module for using a minimum eigenvector problem approach to compute the line direction for each set of parallel lines.

Claim 87

Dependent Claim 33 words

The computer-readable memory of claim 82, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 88

Dependent Claim 52 words

The computer-readable memory of claim 70 wherein an element of the determined camera orientation matrix may be reversed in sign in comparison to the actual camera orientation matrix, and wherein the camera orientation matrix recovery sub-module further comprises a sub-module for resolving any sign ambiguity existing in the determined camera orientation matrix.

Claim 89

Dependent Claim 35 words

The computer-readable memory of claim 85, wherein the user specifies the direction of each previously designated line associated with the plane of the 3D scene as it appears in the panoramic view of the scene.

Claim 90

Dependent Claim 124 words

The computer-readable memory of claim 85, wherein the user specifies the 3D scene coordinates of at least two points identified by the user in the screen image and the resolving sub-module comprises a sub-modules for: computing the 3D scene coordinates of the points identified by the user in the screen image by projecting the panoramic view coordinates of these points obtained from the screen image to the 3D scene using the camera orientation matrix; comparing the computed 3D scene coordinates with the coordinates specified by the user; and reversing the sign of any of the determined camera orientation matrix elements corresponding to a computed 3D scene coordinate element that has a different sign than the corresponding 3D scene coordinate element specified by the user.

Claim 91

Dependent Claim 111 words

The computer-readable memory of claim 69, wherein the user designates lines on each plane in the screen image of the panoramic view which is to be modeled, and the program module for estimating plane normals and line directions for planes in the 3D scene comprises sub-modules for: deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image using the camera orientation matrix; and deriving a normal for each plane in the 3D scene that corresponds to a plane of the screen image on which the user has designated lines, using the derived 3D scene line directions associated with that plane.

Claim 92

Dependent Claim 104 words

The computer-readable memory of claim 88, wherein the program module for estimating plane normals and line directions for planes in the 3D scene further comprises sub-modules for: ascertaining whether the user has designated a sufficient number of lines on a plane in the screen image to derive the line directions and plane normal associated with the corresponding plane in the 3D scene; and prompting the user to designate additional lines on a plane in the screen image whenever it is ascertained there are not a sufficient number to derive the line directions and plane normal associated with the corresponding plane in the 3D scene.

Claim 93

Dependent Claim 45 words

The computer-readable memory of claim 89, wherein the ascertaining sub-module comprises a sub-module for ascertaining whether the user has designated one of (i) at least two sets of parallel lines on the plane, or (ii) at least three lines of a rectangle on the plane.

Claim 94

Dependent Claim 69 words

The computer-readable memory of claim 88, wherein the sub-module for deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image comprises a sub-module for deriving the direction of lines on planes to be modeled in the 3D scene using two pairs of parallel lines designated by the user as being on the corresponding plane in the screen image.

Claim 95

Dependent Claim 159 words

The computer-readable memory of claim 91, wherein the sub-module for deriving the direction of lines on planes to be modeled in the 3D scene comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the two pairs of parallel lines designated by the user in the screen image; computing a normal for each of the projection planes associated with the two pairs of parallel lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for each pair of parallel lines in the panoramic view using the computed projection plane normals associated with that pair of parallel lines; and computing the line direction in each plane in the 3D scene corresponding to each pair of parallel lines in the panoramic view using the computed panoramic view line directions and the camera orientation matrix.

Claim 96

Dependent Claim 33 words

The computer-readable memory of claim 92, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 97

Dependent Claim 69 words

The computer-readable memory of claim 88, wherein the sub-module for deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image comprises a sub-module for deriving the direction of lines on planes to be modeled in the 3D scene using three lines of a rectangle designated by the user as being on the corresponding plane in the screen image.

Claim 98

Dependent Claim 256 words

The computer-readable memory of claim 94, wherein the sub-module for deriving the direction of lines on planes to be modeled in the 3D scene comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the three lines of the rectangle designated by the user in the screen image; computing a normal for each of the projection planes associated with the three lines of the rectangle in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for two lines of the three lines of the rectangle in the panoramic view that are parallel using the computed projection plane normals associated with the pair of parallel lines; and computing the line direction in each plane in the 3D scene corresponding to the pair of parallel lines in the panoramic view using the computed panoramic view line direction and the camera orientation matrix; computing a 3D scene projection of the projection plane normal associated with the remaining, non-parallel line of the three lines of the rectangle using the camera orientation matrix; computing a line direction for a line in the 3D scene corresponding to the remaining, non-parallel line of the three lines of the rectangle in the panoramic view using the previously computed line direction of the pair of parallel lines in the 3D scene and the previously computed 3D scene projection of the projection plane normal associated with the remaining, non-parallel line.

Claim 99

Dependent Claim 33 words

The computer-readable memory of claim 95, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 100

Dependent Claim 204 words

The computer-readable memory of claim 69, wherein the user specifies the 3D scene coordinates of at least two points identified by the user in the screen image, and the program module for recovering the camera translation comprises sub-modules for: characterizing the conversion of a point in the 3D scene to a corresponding point in the panoramic view using the relationship, (x-t)×R T x'=0, which is equivalent to, (x-t)·(R T p j ')=0, j=0,1,2 where x represents the coordinates of a point in the 3D scene, t represents the camera translation, R represents the camera orientation matrix, x' represents the coordinates of a point in the panoramic view which corresponds to a point x in the 3D scene and p 0 '=(-x 2 , x 1 , 0), p 1 '=(-x 3 , 0, x 1 ) and p 2 " (0, -x 3 , x 2 ) represent three directions perpendicular to a ray from the camera center through the point x'=(x 1 , x 2 , x 3 ); creating a system of linear equation based on the characterizing relationship using the at least two user specified points; and estimating the camera translation from the system of linear equations using a least-squares approach.

Claim 101

Dependent Claim 215 words

The computer-readable memory of claim 69, wherein the user designates ones of, 3D scene coordinates of points corresponding to points identified by the user in the screen image, plane normals associated with planes in the 3D scene that correspond to planes identified by the user in the screen image, directions of lines in the 3D scene that correspond to lines identified by the user in the screen image, plane distances associated with planes in the 3D scene that correspond to planes identified by the user in the screen image, and planes in the screen image that correspond to parallel planes of the 3D scene, and wherein the program module for estimating plane distances and vertex point locations for each plane in the 3D scene which is to be modeled comprises sub-modules for: characterizing the 3D scene as at least one set of connected planes, each set being subject to a series of geometric constraints; creating a system of linear geometric constraint equations based on the characterizing constraints for each set of connected planes in the 3D scene which are to be modeled; and estimating the unknown plane distances and vertex points for each set of connected planes in the 3D scene which is to be modeled from the system of equations using a least-squares approach.

Claim 102

Dependent Claim 280 words

The computer-readable memory of claim 98, wherein the system of constraints employed in the characterizing step comprises: ______________________________________ Known point x.sub.i.sup.", Known plane d.sub.i.sup.", Distance Parallel planes d.sub.i - d.sub.j = Const., Point/model (x - t) · p.sub.j = 0, Point/plane x.sub.i · n.sub.k.sup." + d.sub.k = 0, Point/plane x.sub.i · n.sub.k + d.sub.k = 0, Points/line (x.sub.i - x.sub.j) × m" = 0, Points/line (x.sub.i - x.sub.j) × m = 0, Known length x.sub.i - x.sub.j = cm", Known length x.sub.i - x.sub.j = cm ______________________________________ where x" represents the coordinates of a point in the 3D scene designated by the user and x represents the unknown coordinates of a point in the 3D scene, d" represents a distance from the origin of the 3D scene to a plane in the scene as designated by the user and d represents an unknown distance from the origin of the 3D scene to a plane in the scene, t represents the camera translation, p j represents p 0 =(-x 2 , x 1 , 0), p 1 =(-x 3 , 0, x 1 ) and p 2 =(0, -x 3 , x 2 ) which correspond to three directions perpendicular to a ray from the camera center through the point x=(x 1 , x 2 , x 3 ), n" represents a normal of a plane in the 3D scene designated by the user and n represents the estimated normal of a plane in the 3D scene, m" represents a direction of a line in the 3D scene designated by the user and m represents the estimated direction of a line in the 3D scene, and c represents a scaling factor.

Claim 103

Dependent Claim 45 words

The computer-readable memory of claim 99, wherein the creating sub-module comprises a sub-module for using the user designated points, plane normals, line directions, plane distances and parallel plane designations, as well as the estimated plane normals and line directions to create the system of equations.

Claim 104

Dependent Claim 34 words

The computer-readable memory of claim 100, wherein the camera translation has been previously estimated and the creating sub-module further comprises a sub-module for using the estimated camera translation to create the system of equations.

Claim 105

Dependent Claim 33 words

The computer-readable memory of claim 100, wherein the camera translation is unknown and estimated along with the unknown plane distances and vertex point locations from the system of equations using the least-squares approach.

Claim 106

Independent Claim 225 words

A system for constructing a model of a 3D scene from a panoramic view of the scene, comprising: a general purpose computing device; an interface for dynamically interfacing a user to the computing device, wherein the user is provided with a display of an image of the panoramic view of the 3D scene on a computer monitor screen, the user then specifying features on the screen image; a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to, recover a camera orientation matrix of the panoramic view based on the features specified by the user, estimate plane normals and line directions for planes in the 3D scene which are to be modeled using the camera orientation matrix, recover a camera translation using the camera orientation matrix, wherein the camera translation is the difference between the camera projection center and the coordinate origin of the 3D scene, estimate unknown plane distances and vertex point locations for each plane in the 3D scene which is to be modeled using the estimated plane normals and line directions, and construct a model of the 3D scene consisting of at least one set of connected planes based on the plane normal and plane distance, and/or the vertex point locations, of each plane in the set.

Claim 107

Independent Claim 225 words

A system for constructing a model of a 3D scene from a panoramic view of the scene, comprising: a general purpose computing device; an interface for dynamically interfacing a user to the computing device, wherein the user is provided with a display of an image of the panoramic view of the 3D scene on a computer monitor screen, the user then specifying features on the screen image; a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to, recover a camera orientation matrix of the panoramic view based on the features specified by the user, estimate plane normals and line directions for planes in the 3D scene which are to be modeled using the camera orientation matrix, recover a camera translation using the camera orientation matrix, wherein the camera translation is the difference between the camera projection center and the coordinate origin of the 3D scene, estimate unknown plane distances and vertex point locations for each plane in the 3D scene which is to be modeled using the estimated plane normals and line directions, and construct a model of the 3D scene consisting of at least one set of connected planes based on the plane normal and plane distance, and/or the vertex point locations, of each plane in the set.

Claim 108

Dependent Claim 78 words

The system of claim 103, wherein the user specified features comprise lines on at least one plane in the screen image of the panoramic view of the 3D scene and the direction of lines in the 3D scene which correspond to each of the designated lines in the screen image, and wherein the program module for recovering the camera orientation matrix comprises a sub-module for determining the camera orientation matrix using the user specified lines and line directions.

Claim 109

Dependent Claim 113 words

The system of claim 104, wherein the interface further comprises a prompting image to provide the user with information concerning the designation of additional lines whenever the number of lines designated by the user is insufficient to determine the camera orientation matrix, and wherein the program module for recovering the camera orientation matrix further comprises sub-modules for: ascertaining whether the user has designated a sufficient number of lines on the at least one plane to determine the camera orientation matrix; and prompting the user via the interface to designate additional lines on the at least one plane whenever it is ascertained there are not a sufficient number to determine the camera orientation matrix.

Claim 110

Dependent Claim 92 words

The system of claim 105, wherein the ascertaining sub-module comprises a sub-module for ascertaining whether the user has designated one of (i) lines on a plane corresponding to at least two vertical lines and one horizontal line of the 3D scene, (ii) lines on a plane corresponding to at least two horizontal lines and one vertical line of the 3D scene, or (iii) lines on planes corresponding to at least two sets of parallel lines of the 3D scene and the direction of each set of parallel lines in the 3D scene.

Claim 111

Dependent Claim 46 words

The system of claim 104, wherein the determining sub-module comprises a sub-module for deriving the camera orientation matrix from lines on a plane corresponding to at least two vertical lines and one horizontal line of the 3D scene, as designated by the user via the interface.

Claim 112

Dependent Claim 147 words

The system of claim 107 wherein the deriving sub-module comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two vertical lines and one horizontal line designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a Z-axis element of the camera orientation matrix using the computed projection plane normals associated with each of the designated vertical lines; computing an X-axis element of the camera orientation matrix using the computed Z-axis element and the projection plane normal associated with the designated horizontal line; and computing a Y-axis element of the camera orientation matrix using the computed Z-axis and X-axis elements.

Claim 113

Dependent Claim 48 words

The system of claim 108, wherein the user specified features comprise more than two vertical lines on the plane, and wherein the sub-module for computing the Z-axis element of the camera orientation matrix comprises a sub-module for using a minimum eigenvalue problem approach to compute the Z-axis element.

Claim 114

Dependent Claim 32 words

The system of claim 108, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 115

Dependent Claim 46 words

The system of claim 104, wherein the determining sub-module comprises a sub-module for deriving the camera orientation matrix from lines on a plane corresponding to at least two horizontal lines and one vertical line of the 3D scene, as designated by the user via the interface.

Claim 116

Dependent Claim 147 words

The system of claim 111, wherein the deriving sub-module comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two horizontal lines and one vertical line designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing an X-axis element of the camera orientation matrix using the computed projection plane normals associated with each of the designated horizontal lines; computing a Z-axis element of the camera orientation matrix using the computed X-axis element and the projection plane normal associated with the designated vertical line; and computing a Y-axis element of the camera orientation matrix using the computed X-axis and Z-axis elements.

Claim 117

Dependent Claim 48 words

The system of claim 112, wherein the user specified features comprise more than two horizontal lines on the plane, and wherein the sub-module for computing the X-axis element of the camera orientation matrix comprises a sub-module for using a minimum eigenvalue problem approach to compute the X-axis element.

Claim 118

Dependent Claim 32 words

The system of claim 112, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 119

Dependent Claim 71 words

The system of claim 104, wherein the user specified features comprise the direction of each of the parallel lines in the 3D scene, and wherein the determining sub-module comprises a sub-module for deriving the camera orientation matrix from at least two sets of parallel lines on one or more planes and the direction of each of the parallel lines in the 3D scene, as designated by the user via the interface.

Claim 120

Dependent Claim 151 words

The system of claim 115, wherein the deriving sub-module comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the at least two sets of parallel lines designated by the user in the screen image; computing a normal for each of the projection planes associated with said lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for each set of parallel lines in the panoramic view using the computed projection plane normals associated with that set of parallel lines; computing the camera orientation matrix from the computed panoramic view line direction for each set of parallel lines and the line direction of each corresponding set of parallel lines in the 3D scene as designated by the user using a maximum eigenvalue problem approach.

Claim 121

Dependent Claim 62 words

The system of claim 116, wherein the user specified features comprise more than two parallel lines in a set of parallel lines, and wherein the sub-module for computing a line direction for each set of parallel lines in the panoramic view comprises a sub-module for using a minimum eigenvector problem approach to compute the line direction for each set of parallel lines.

Claim 122

Dependent Claim 32 words

The system of claim 116, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 123

Dependent Claim 51 words

The system of claim 104 wherein an element of the determined camera orientation matrix may be reversed in sign in comparison to the actual camera orientation matrix, and wherein the camera orientation matrix recovery sub-module further comprises a sub-module for resolving any sign ambiguity existing in the determined camera orientation matrix.

Claim 124

Dependent Claim 36 words

The system of claim 119, wherein the user specified features comprise the direction of each previously designated line associated with a plane of the 3D scene as it appears in the panoramic view of the scene.

Claim 125

Dependent Claim 126 words

The system of claim 119, wherein the user specified features comprise the 3D scene coordinates of at least two points identified by the user in the screen image, and wherein the resolving sub-module comprises a sub-modules for: computing the 3D scene coordinates of the points identified by the user in the screen image by projecting the panoramic view coordinates of these points obtained from the screen image to the 3D scene using the camera orientation matrix; comparing the computed 3D scene coordinates with the coordinates specified by the user; and reversing the sign of any of the determined camera orientation matrix elements corresponding to a computed 3D scene coordinate element that has a different sign than the corresponding 3D scene coordinate element specified by the user.

Claim 126

Dependent Claim 110 words

The system of claim 103, wherein the user designates lines on each plane in the screen image of the panoramic view which is to be modeled, and the program module for estimating plane normals and line directions for planes in the 3D scene comprises sub-modules for: deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image using the camera orientation matrix; and deriving a normal for each plane in the 3D scene that corresponds to a plane of the screen image on which the user has designated lines, using the derived 3D scene line directions associated with that plane.

Claim 127

Dependent Claim 155 words

The system of claim 122, wherein the interface further comprises a prompting image to provide the user with information concerning the designation of additional lines whenever the number of lines designated by the user is insufficient to derive the line directions and plane normal associated with a corresponding plane in the 3D scene, and wherein the program module for estimating plane normals and line directions for planes in the 3D scene further comprises sub-modules for: ascertaining whether the user has designated a sufficient number of lines on a plane in the screen image to derive the line directions and plane normal associated with the corresponding plane in the 3D scene; and prompting the user via the interface to designate additional lines on a plane in the screen image whenever it is ascertained there are not a sufficient number to derive the line directions and plane normal associated with the corresponding plane in the 3D scene.

Claim 128

Dependent Claim 44 words

The system of claim 123, wherein the ascertaining sub-module comprises a sub-module for ascertaining whether the user has designated one of (i) at least two sets of parallel lines on the plane, or (ii) at least three lines of a rectangle on the plane.

Claim 129

Dependent Claim 89 words

The system of claim 122, wherein the user specified features comprise designating two pairs of parallel lines on at least one plane in the screen image, and wherein the sub-module for deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image comprises a sub-module for deriving the direction of lines on planes to be modeled in the 3D scene using the two pairs of parallel lines designated by the user on the corresponding plane in the screen image.

Claim 130

Dependent Claim 157 words

The system of claim 125, wherein the sub-module for deriving the direction of lines on planes to be modeled in the 3D scene comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that.corresponds to the two pairs of parallel lines designated by the user in the screen image; computing a normal for each of the projection planes associated with the two pairs of parallel lines in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for each pair of parallel lines in the panoramic view using the computed projection plane normals associated with that pair of parallel lines; and computing the line directions in each plane in the 3D scene corresponding to each pair of parallel lines in the panoramic view using the computed panoramic view line directions and the camera orientation matrix.

Claim 131

Dependent Claim 32 words

The system of claim 126, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 132

Dependent Claim 89 words

The system of claim 122, wherein the user specified features comprise designating three lines of a rectangle on at least one plane in the screen image, and wherein the sub-module for deriving the direction of lines in the 3D scene corresponding to each of the user designated lines in the screen image comprises a sub-module for deriving the direction of lines on planes to be modeled in the 3D scene using the three lines of a rectangle designated by the user on the corresponding plane in the screen image.

Claim 133

Dependent Claim 255 words

The system of claim 128, wherein the sub-module for deriving the direction of lines on planes to be modeled in the 3D scene comprises sub-modules for: identifying the coordinates of two points on each line in the panoramic view that corresponds to the three lines of the rectangle designated by the user in the screen image; computing a normal for each of the projection planes associated with the three lines of the rectangle in the panoramic view, each projection plane being defined by the two identified points and a camera center associated with the panoramic view; computing a line direction for two lines of the three lines of the rectangle in the panoramic view that are parallel using the computed projection plane normals associated with the pair of parallel lines; and computing the line direction in each plane in the 3D scene corresponding to the pair of parallel lines in the panoramic view using the computed panoramic view line direction and the camera orientation matrix; computing a 3D scene projection of the projection plane normal associated with the remaining, non-parallel line of the three lines of the rectangle using the camera orientation matrix; computing a line direction for a line in the 3D scene corresponding to the remaining, non-parallel line of the three lines of the rectangle in the panoramic view using the previously computed line direction of the pair of parallel lines in the 3D scene and the previously computed 3D scene projection of the projection plane normal associated with the remaining, non-parallel line.

Claim 134

Dependent Claim 32 words

The system of claim 129, wherein the coordinates of the two points identified on each line in the panoramic view correspond to the coordinates of the two end points of each line.

Claim 135

Dependent Claim 205 words

The system of claim 103, wherein the user specified features comprise specifying the 3D scene coordinates of at least two points identified by the user in the screen image, and the program module for recovering the camera translation comprises sub-modules for: characterizing the conversion of a point in the 3D scene to a corresponding point in the panoramic view using the relationship, (x-t)×R T x'=0, which is equivalent to, (x-t)·(R T p j ')=0, j=0,1,2 where x represents the coordinates of a point in the 3D scene, t represents the camera translation, R represents the camera orientation matrix, x' represents the coordinates of a point in the panoramic view which corresponds to a point x in the 3D scene and p 0 '=(-x 2 , x 1 , 0), p 1 '=(-x 3 , 0, x 1 ) and p 2 "=(0, -x 3 , x 2 ) represent three directions perpendicular to a ray from the camera center through the point x'=(x 1 , x 2 , x 3 ); creating a system of linear equation based on the characterizing relationship using the at least two user specified points; and estimating the camera translation from the system of linear equations using a least-squares approach.

Claim 136

Dependent Claim 217 words

The system of claim 103, wherein the user specified features comprise designating ones of, 3D scene coordinates of points corresponding to points identified by the user in the screen image, plane normals associated with planes in the 3D scene that correspond to planes identified by the user in the screen image, directions of lines in the 3D scene that correspond to lines identified by the user in the screen image, plane distances associated with planes in the 3D scene that correspond to planes identified by the user in the screen image, and planes in the screen image that correspond to parallel planes of the 3D scene, and wherein the program module for estimating plane distances and vertex point locations for each plane in the 3D scene which is to be modeled comprises sub-modules for: characterizing the 3D scene as at least one set of connected planes, each set being subject to a series of geometric constraints; creating a system of linear geometric constraint equations based on the characterizing constraints for each set of connected planes in the 3D scene which are to be modeled; and estimating the unknown plane distances and vertex points for each set of connected planes in the 3D scene which is to be modeled from the system of equations using a least-squares approach.

Claim 137

Dependent Claim 279 words

The system of claim 132, wherein the system of constraints employed in the characterizing step comprises: ______________________________________ Known point x.sub.i.sup.", Known plane d.sub.i.sup.", Distance Parallel planes d.sub.i - d.sub.j = Const., Point/model (x - t) · p.sub.j = 0, Point/plane x.sub.i · n.sub.k.sup." + d.sub.k = 0, Point/plane x.sub.i · n.sub.k + d.sub.k = 0, Points/line (x.sub.i - x.sub.j) × m" = 0, Points/line (x.sub.i - x.sub.j) × m = 0, Known length x.sub.i - x.sub.j = cm", Known length x.sub.i - x.sub.j = cm ______________________________________ where x" represents the coordinates of a point in the 3D scene designated by the user and x represents the unknown coordinates of a point in the 3D scene, d" represents a distance from the origin of the 3D scene to a plane in the scene as designated by the user and d represents an unknown distance from the origin of the 3D scene to a plane in the scene, t represents the camera translation, p j represents p 0 =(-x 2 , x 1 , 0), p 1 =(-x 3 , 0, x 1 ) and p 2 =(0, -x 3 , x 2 ) which correspond to three directions perpendicular to a ray from the camera center through the point x=(x 1 , x 2 , x 3 ), n" represents a normal of a plane in the 3D scene designated by the user and n represents the estimated normal of a plane in the 3D scene, m" represents a direction of a line in the 3D scene designated by the user and m represents the estimated direction of a line in the 3D scene, and c represents a scaling factor.

Claim 138

Dependent Claim 44 words

The system of claim 133, wherein the creating sub-module comprises a sub-module for using the user designated points, plane normals, line directions, plane distances and parallel plane designations, as well as the estimated plane normals and line directions to create the system of equations.

Claim 139

Dependent Claim 33 words

The system of claim 134, wherein the camera translation has been previously estimated and the creating sub-module further comprises a sub-module for using the estimated camera translation to create the system of equations.

Claim 140

Dependent Claim 32 words

The system of claim 134, wherein the camera translation is unknown and estimated along with the unknown plane distances and vertex point locations from the system of equations using the least-squares approach.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2003-07-04	2004-01-03	2004-07-04	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2007-07-04	2008-01-03	2008-07-04	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2011-07-04	2012-01-03	2012-07-04	$7700.00	Window Closed / Lapsed

Interactive construction of 3D models from panoramic images

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag