Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-05-11
2002-07-16
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S619000
Reexamination Certificate
active
06421049
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods for determining approximate solutions to large, sparse linear systems and, in particular, to the applications of such methods in the fields of photogrammetry and computer-assisted three-dimensional modeling.
BACKGROUND
Three-dimensional modeling, which is now a subset of the larger field of computer graphics, has become popular in a number of areas, for example, as applied in computer-aided design of architecture industrial design and construction. As has been recognized in these and other fields, it is often desirable to have a three-dimensional model, complete with a description of shape, location, orientation and material surface properties (i.e., texture), in order to produce realistic renderings on a computer which can be used to document a new design of a city, a building or an object. The model can also be used for computer animations, virtual reality immersion of users in a scene or for manufacturing tasks.
Image assisted modeling may be regarded as a subset of three-dimensional modeling in that the model is produced from an image, rather than from scratch. In the field of image assisted modeling, a user manipulates a three-dimensional model of a scene (perhaps represented as a computer-generated graphical representation of the scene) interactively, to fit the scene to a given image. From the point of view of the software algorithm which allows such manipulation, this requires solving the basic photogrammetric equation
p=f
(
q
), with constraints
p=p
0
(1)
where p is the vector of coordinates of vertices of points of the model and q is the vector of parameters of the model. The vector p
0
denotes the user specified locations of these points on the image. Function f maps the parameters q first into three-dimensional vertex coordinates in a world space, then second through a camera projection into camera space, and third, into a screen space for presentation to the user. In the general case where non-orthographic cameras are used to take the source image, f is non-linear with respect to q.
Because in general, (1) defines a non-linear system, solving (1) is commonly done by first converting it to a linear system, for example, using a first order Taylor series expansion, where J is the Jacobian of f (i.e., the derivatives of all elements of p with respect to all elements of q):
p
0
=
f
(
q
)+
J.dq/dt
(2)
where is used to represent the product of a matrix with a vector. Equation (2) is then integrated over time to yield a solution.
For photogrammetric problems. J is large and sparse (i.e., mostly zero). While integrating (2) over time, one must recompute J for each new time step and solve the corresponding linear system. This solution process is roughly O(n*m), where n is the number of elements of p and m is the number of elements of q. Because of the complex computations involved, previous approaches to such modeling problems often involve algorithms that run in “batch” mode. That is, a user must create all of the input data (e.g., vertices edges, associations, etc.) and then invoke the modeling method. The modeling algorithms then complete all of the required calculations before providing any feedback to the user. Sometimes, because of inconsistent or undetermined input information or due to singularities in the modeling algorithms themselves, these batch processes cannot return correct or even useful models. Even worse, such algorithms often provide little or no indication of what the cause of the problem was or where the user might correct the input information to resubmit to the batch process.
A recently published method (Paul Debevec et al., “Modeling and Rendering Architecture from Photographs: A Hybrid Geometry- and Image-Based Approach”,
University of California Berkeley Technical Report UCB
-
CSD
-96-893, January 1996) somewhat simplifies this situation by not having to deal with geometry at a vertex, then edge, then face level, but rather with primitives such as boxes or cylinders. The method requires a user to first create a parameterized (or rough) model of the objects in the scene using a separate editor. Second, the user draws edges on top of one or more photographs. Third, the user marks each edge in each photograph as corresponding to a particular edge in the parameterized model. The method then calculates values for the parameters in the model. This work is based on concepts and mathematics from Camillo Taylor and David Kriegman of Yale University, as reported in “Structure and Motion from Line Segments in Multiple Images”, Yale University, Technical Report #94026, January 1994. Although somewhat less labor intensive than previous techniques, the Debevec method (known as Facade) still requires three, individually intensive, steps and the user must be skilled enough to build a parameterized model independent of the photographs.
Other reported methods, e.g., Michael Kass “CONDOR: Constraint-Based Dataflow”,
SIGGRAPH '
92, pp. 321-330 (Jul. 26-31, 1992) and Michael Gleicher and Andrew Witkin, “Through-the-Lens Camera Control”,
SIGGRAPH
'92, pp. 331-340 (Jul. 26-31, 1992), use data structures known as a dataflow network to create the required Jacobian matrix for providing iterative solutions to the modeling problem. For example, Gleicher and Witkin show how to apply traditional keyframing techniques to existing three-dimensional models and how to then solve for camera positions. However, in this technique, no modeling is done on top of an image nor is any texture extraction provided.
In general then, existing modeling techniques have not provided solutions to the photogrammetric equation (1) which allow for interactive use. Of course, in other fields much attention has been paid to the solution of sparse matrices. For example, parameter separation is a known technique for solving non-linear least squares problems. See, e.g., Ake Bjorck “Numerical Methods for Least Squares Problems”, SIAM (1996). Unfortunately though, these techniques cannot be used for all functions f. Other methods exploit specific sparsity structures of a matrix or specific small changes to the linear system represented thereby. See, e.g., William H. Press et al.,
Numerical Recipes in C
(1988). These techniques, however, do not adapt well to interactive situations.
In light of the need for computer-generated three-dimensional models, but given the shortcoming of prior schemes for solving the photogrammetric equation, it would be desirable to have an improved computer-assisted technique for solving such problems in an interactive environment.
SUMMARY AND OBJECTIVES OF THE INVENTION
Thus, one object of the present invention is to provide an improved computer-assisted technique for solving photogrammetric problems in an interactive environment.
In one embodiment, the present invention provides a computer-assisted technique for providing approximate solutions to photogrammetric problems in interactive applications, for example, image assisted modeling applications wherein a three-dimensional model is constructed on top of one or more images. Rather than directly solve the system described by equation (2) above, the present invention computes an approximate solution which can be used to quickly redraw and update the model for presentation to the user. In other words, the techniques of the present invention allow for an efficient conversion of the full problem described by (2) into a smaller problem where only a subset of the model's parameters are used. The size of the smaller problem can be adjusted to different system capabilities and/or model complexities to ensure computation of an approximate solution in a given time. For use in an interactive environment, this time may be adjusted so that redraw rates are within acceptable tolerances, say from 5 to 30 frames per second.
By way of example, the computer-assisted method may allow for drawing a three-dimensional representation of a scene using parameterized primitives having constraints which are updated
Reinhardt Tilman
Seidl Robert
Adobe Systems Inc.
Brier Jeffery
Yang Ryan
LandOfFree
Parameter selection for approximate solutions to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parameter selection for approximate solutions to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameter selection for approximate solutions to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2895997