Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-12-15
2001-08-21
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000, C382S154000
Reexamination Certificate
active
06278460
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to the field of computer modeling and, in particular, to creating a three-dimensional model from two-dimensional images.
BACKGROUND INFORMATION
Conventionally, computers display images in a standard two-dimensional format much like conventional photographic images. However, computer programmers have developed techniques over the years to create three-dimensional representations of objects for display on the computer. Unfortunately, these techniques tend to be cumbersome, complicated and difficult to implement on a routine basis.
One approach to creating a three-dimensional model is to start with two-dimensional images. The basic problem with creating a three-dimensional model in this manner is that of extracting the three-dimensional shape of the objects appearing in the sequence of two-dimensional images. The crux of the problem is that each two-dimensional image contains only a two-dimensional projection of the actual three-dimensional object, and in fact, may only contain a portion of the objects. Much work has been done on this to date.
Photogrammetry has been used to create three-dimensional models from two-dimensional images. This methodology has at least two formulations. The first formulation uses a pair of cameras locked together a fixed distance apart. The second one uses a single camera along with a position or orientation sensor. In the second case, the camera position must be known at all times, and is not derived from the images. This method requires that a human user identify a set number of points along the outline and shape of the same object appearing throughout multiple images. Once this is done, the program reconstructs a three-dimensional wire frame model of the object by calculating the three-dimensional locations of the points that the user selected and then mapping the two-dimensional image textures of the object onto that wire frame. This texture mapping introduces inherent distortions in the image.
Another methodology for creating a three-dimensional model from two-dimensional images is referred to as “optic flow.” This methodology is based on the property that due to perspective, when a viewer moves relative to stationary objects, objects closer to the viewer appear to move more in the viewers field of view than objects far away. The method estimates depth (the third dimension) from relative motion of identified objects in the two-dimensional image sequence. This method works because the distance from an object and the object's perceived shape are inherently linked due to perspective. For example, the far side of a building looks smaller than the near side. This method requires that the objects in an image be identified and tracked from frame to frame. It suffers greatly from occlusions and incomplete data because these things make tracking difficult. In addition, it is very sensitive to noise because errors in size or motion measurement are magnified greatly when estimating relative depth. In addition it requires a known camera position.
Another methodology for creating a three-dimensional model from two-dimensional images is known as “shape from motion.” This methodology formulates the problem in linear algebra. In most implementations, all of the images in the sequence are used at once in a single calculation that yields the desired output (a closed-form solution). That output is either the shape of the object given the camera motion, or the camera motion given the shape of the objects, or both shape and motion.
In order to find both shape and motion, it is necessary to make them independent of one another. This is a problem since in a perspective projection they are related as described above. Therefore, under this formulation, it becomes necessary to assume an orthographic projection. (This means that all lines of vision are parallel and thus objects do not get smaller with distance.) This has the severe disadvantage that it introduces distortion. For example, this method would assume that the far side of a building in an image is, in fact, smaller than the near side, and thus model the building in three dimensions with one side shorter than the other. There are at least two formulations of this structure from motion methodology: one that uses an iterative method, and one that uses a closed-form method.
In addition there are drawbacks to closed form solutions: They require all of the data and cannot calculate an answer as images are acquired, thus cannot be made into real time solutions. Also, they put all of the input data into a number of large matrices and operate on those to find the solution. As a result, any missing matrix values causes serious problems, including making it unsolvable without filling in those values with guesses, thus introducing large errors. In addition, this method also tracks a relatively small number of points and texture maps onto those thus introducing texture warping.
For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for an improved technique for developing a three-dimensional model from two-dimensional images.
SUMMARY
The above mentioned problems with three-dimensional computer modeling and other problems are addressed by the present invention and will be understood by reading and studying the following specification. Three-dimensional models are created from two-dimensional images, e.g., a number of two-dimensional still images or a video stream with a number of video frames, without prior knowledge of the position of the camera, its focal length, etc. by deriving a relative value related to the position or orientation of the camera for each two-dimensional image and then, based on the derived value, using “ray casting” to develop the three-dimensional model based on intersecting rays through common features of sequential images. Ray casting includes but is not limited to forming a three-dimensional vector assuming a pinhole projection. The vector originates at the focal point or camera position, passes through a selected pixel of the two-dimensional video image, and passes through at least one voxel of the three-dimensional model.
In one embodiment, the value related to the camera position or orientation is determined using ray casting based on a select number of features of each frame of a video stream. For example, a few features are selected and tracked through the sequence of images in the video stream. With the initial frame of the video stream, the value related to the camera position or orientation is locked down at an arbitrary position, e.g., the origin {0,0,0} in {x,y,z} coordinates. The camera position or orientation of the next frame is set at a selected location and the intersections of the rays through the select number of features in the two frames are analyzed. The position or orientation of the camera for the next frame is moved, iteratively, until the selected rays from the first frame intersect with the corresponding rays of the second frame within an acceptable error level, e.g., a minimum error level. This procedure is repeated for subsequent pairs of frames until the camera position or orientation is determined for each frame. It is noted that the features used to find the camera position may be different from the features used to create the points of the three-dimensional model.
In one embodiment, the three-dimensional model is developed by casting rays through each pixel of a selected feature in a pair of frames. These rays are compared to determine intersections in quality, e.g., color, and location in the three-dimensional space. Voxels of the model are derived based on these intersections.
REFERENCES:
patent: 4970666 (1990-11-01), Welsh et al.
patent: 4989152 (1991-01-01), Cheng
patent: 5365603 (1994-11-01), Karmann
patent: 5444478 (1995-08-01), Lelong et al.
patent: 5511153 (1996-04-01), Azarbayejani et al.
patent: 5566283 (1996-10-01), Modegi et al.
Bodor Robert
Myers Thomas B.
Point Cloud, Inc.
Santiago Enrique L
Schwegman Lundberg Woessner & Kluth P.A.
Zimmerman Mark
LandOfFree
Creating a three-dimensional model from two-dimensional images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Creating a three-dimensional model from two-dimensional images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Creating a three-dimensional model from two-dimensional images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2460081