"Algorithms Returning Perspective"
BobMaX - July 2004
KEYWORDS: CAD-based Photogrammetry, Camera Matching
ABSTRACT This paper describes the evolution of photogrammetric and mapping of simple vector-producing three-dimensional models and the evolution of algorithms for the prospective return metrics from individual photo.
1 INTRODUCTION The idea of \u200b\u200busing photography for the purpose of historical significance is attributed to the French Laussedat in 1850. Only in early 1900, however, there were the first practical applications in cartography, with the advent of aerial photogrammetry. Since 1946, after the end of the second war and military intelligence, began the first university courses to 'Institute of Photogrammetry and Remote Sensing in Finland. The change from the optical-mechanical methods of returning to digital occurred after 1980. From this date, photogrammetry has followed the evolution of computer graphics systems.
In recent years, programs have evolved from a simple CAD tool for 2D drawing to complex systems for the management of project quality. The functions necessary to the design of architectural organisms can be used within hours of photogrammetric restitution programs, closing a circle around the needs of the existing modeling.
Fig. 1 Classical photogrammetric aerial
Fig. 2 Modern Urban Three-dimensional Restitution
Fig. 3 Dimensional Laser Detection
Today, the modern laser measurement techniques, from ground or airborne, are integrated with the more traditional monoscopic photogrammetry, achieving a "solid stock" of complex urban bodies.
Fig. 4 Urban Return via "Canoma"
2 photogrammetry "CAD-based
Before describing the trends in Photogrammetry" CAD-based, it is useful to define these terms.
2.1 Definitions
The acronym CAD stands for Computer Aided Design or Computer-Aided Design. The CAD has become synonymous with program management, manipulation and visualization of three-dimensional data.
other hand, traditionally, photogrammetry focuses on the accurate measurement of 3D coordinates, from pairs of photos, land or air, bodies of architectural or territorial.
Generally, photogrammetry has been limited to a refund from the ground up, the edges of the eaves of buildings, or in general is the projection of architectural plant, at a level of detail maps.
A feature of the programs photogrammetry has almost always been the traditional starting from nothing, that the redesign of the geometry without the use of existing maps, as if to emphasize a strong scientific method.
functions present in a graphic design software photogrammetry, generally are limited until recently to the design of two-dimensional graphics primitives on planes parallel to the horizontal.
Fig. 5 Mapping vector
3 Development of Photogrammetry
With the advent of photogrammetry of nearby or "close-range" have applied the techniques of stereoscopic facades of buildings or internal, obtaining, however, more and vector representations of the significant edges of the bodies recovered.
From mathematical point of view, stereoscopic photogrammetry uses systems of linear equations to solve the mutual orientation of the frame, note the coordinates of pairs of points on photographs taken. Once oriented frames and built the so-called "stereoscopic model," the program simply returns three-dimensional coordinates of points on the two collimated image through the intersection of visual rays from the starters two centers of power [1].
This detection system, although characterized by high stringency, however, is characterized by high operating costs, associated with the need to shoot double, and considerable difficulties of recovery.
Moreover, the obligation of stereoscopic filming limits its use to the present, and not usability of Heritage archive images, or drawings and paintings, models for the reconstruction of architectural heritage lost, or lost in part.
3.1 The Software "Facade"
Since 1996 there has been an evolution of the photogrammetry, starting from the experiences of Paul Debevec, University of California, Berkeley. His doctoral thesis on "Modeling and Rendering Architecture from Photographs" [2], has become the reference text in the new trend of photogrammetry. Its software "Facade" allows you to calculate the parameters from perspective geometry notes and return the three-dimensional model with a yield of the existing photo.
Fig. 6 From the video "Campanile Movie" by Paul Debevec
The result of the procedure Debevec is a 3D model "dressed" with the materials derived from photos.
While remaining an experimental software, created within a research university, "Facade" was able to impose a methodology and an innovative type of data in the field of photogrammetry.
3.2 Construction of the topology of the model
The strength of "Facade" is that the model is being built is not only linear, ie made up of lines representing the edges of the building, but is determined by basic objects, such as cuboid, pyramid, truncated pyramid and more that can be linked by topological constraints, such as adjacency, overlap, centering.
This philosophy makes it much more intuitive to base model construction, from an image perspective.
Fig. 7 Collimation of the 3D model on the photos
Fig. 8 Projecting textures on the model
In "Facade" the individual components that make up the building move together, in solidarity with one another, when you must accomplish the task of associating the points covered with graphics.
parameters as the actual height of a component of the object are then calculated by the program, solving the set of constraints.
Fig. 9 main software screen "Facade" of Debevec
3.3 The Software "Canoma"
methodology drawn from the same line "Facade", a series of programs have been developed.
The first low-cost commercial software based on CAD-based photogrammetry is "Canoma, 1998, created by Robert Seidl and Tilman Reinhardt [3].
"Canoma" is characterized by a remarkable intuition, for the graphical interface, and great interactivity.
The user has a palette of three-dimensional graphics primitives that can be placed on the picture, and then rotated and deformed as the basis of size, until visually match the image. Once "fixed" the object, the program calculates the parameters of perspective, through an innovative algorithm that is described later.
Fig. 10 Software "Canoma" Robert Seidl and Tilman Reinhardt
Enter more primitive graphics, the user can define the type of link with the previous object, or another of his choice. Can then be stacked, side by side and glued the visible components of a building.
The catalog includes graphics, parallel to the horizontal, vertical, solid extrusion vertical or horizontal, the subject staircase, the archway, the cylinder and even the table.
Once composed the set of objects, inserting the stink of collimation can be called the procedure performed final processing of the model.
addition to the calculation of the point of view and the size of the objects, "Canoma" extracts from photographs, each face of the object, the corresponding portion, and conducts orthogonal straightening, creating materials that will be displayed on the model 3D final.
Once the model can be inserted a second image, taken from another point of view, to repeat the process of collimation, and get cover the object with other materials, invisible from the first picture. To achieve this, the operator simply has to rotate the object until it is roughly equivalent to how it looks from the new point of view. After that, you need to enter new points-of-sight. For a more accurate recording, you can zoom in, until you see the individual pixels.
When the second photo is collimated, you can repeat the calculation, rendering of the new model.
The procedure can be repeated with other pictures, even in more detail, until the total coverage of the model.
Fig 11 Image of the front of San Pietro in Montorio in Rome
Where an interposed body, such as a tree, it appears to create cones of shadow on the texture, these can be corrected individually, with a function Correction painting, called automatically by "Canoma", using the preferred program operator.
incorrect if all the textures, the three-dimensional model can be saved in standard formats provided, to CAD programs.
Among the various graphics formats is provided for the VRML97, today considered the three-dimensional data interchange files among the most popular.
Another possibility, meno scientifica, prevista da "Canoma", è quella di permettere il salvataggio di una sequenza di punti di vista a scelta dell'operatore, per realizzare una animazione di percorso intorno o attraverso gli oggetti realizzati.
"Canoma" rappresenta oggi un esempio di un ottimo ed innovativo software fotogrammetrico, il cui sviluppo è terminato, e non è più distribuito.
Un limite di "Canoma" è stato, finora, la mancata possibilità di caricare la geometria di modelli tridimensionali provenienti da altri programmi.
Il presente articolo nasce dallo scambio di eMail tra lo scrivente e Robert Seidl, uno degli autori di "Canoma", riguardante la realizzazione di un modulo conversion of three-dimensional objects from a CAD program to the native format Canoma. This collaboration has produced the software ExportToCanoma [14], currently being distributed for free through the site exporttcanoma.blogspot.com.
Fig. 12 Software ExportToCanoma
3.4 Other programs CAD-based Photogrammetry
To date, the number of low-cost programs to return to three-dimensional picture is increasing.
Fig. 13 Software "PhotoModeler" of Eos Systems
PhotoModeler Pro from Eos Systems, allows the use of CAD-type graphics primitives to draw the outlines architectural directly above the photo, used as wallpaper.
Another program used in the field of CAD-based photogrammetry is ImageModeler, Realviz's, which also produces MatchMover, a program that applies the algorithm on video sequences.
Fig. 14 Software "ImageModeler" of Realviz
Software "Marina" uses parametric modeling polyhedra lala for restitution from old prints, uncalibrated old photos or even of sketches.
Fig. 15 Software "Marina" of the 'Ecole des Mines de Nantes
Recently, it was made a free program of the University of Hannover, Germany, called VoodooCameraTracker , which automatically fits sequences of photos, and exports three-dimensional points and the parameters found in the room.
Fig. 16 Software Voodoo Camera Tracker University of Hannover
You can easily infer a trend that is a further evolution of the photogrammetry: the calculation of parameters of perspective from not only from sequences of still images, but video clips. In this way we obtain the parameters of the movement for the purpose, among others, to facilitate assembly of the computer synthesized objects in the actual filming.
An interesting observation to make about the control points, known as "Tie Points", that this generation of automatic collimation to obtain, through pattern matching or statistical recognition of the conformation of the masks of pixels per image. A first advantage of using video sequences is that the high number of frames brings positive results in a smaller difference between the images, and therefore more easily recognized points, which are just "slipped" in small quantities.
But the second advantage is that the high number of Tie Points form a cloud of points in space that in itself is a sort of "relief" of the object, making it similar to a laser survey, although less detailed.
4 mathematical description of Restitution Perspective
The process of image formation must be modeled in a strictly mathematical. The most general camera model is known as the central projection. A 3D point is projected onto the image plane by the lines of visual rays. The corresponding image point is the intersection of the image plane with the visual rays departing from the optical center and the 3D point.
4.1 The Helmert transformation
Starting from the classical method of transformation, we will try to follow the development of algorithms for calculation of parameters for Return Perspective.
claimed that Beinat [8]: "In the major disciplines, the model par excellence, is the transformation of similarity represented by the formulation of Helmert." In it, the calculation of the deformation of two forms be similar to, from, is obtained by minimizing the sum of squared distances between points counterparts of the two figures, the initial and the final one. In essence, a method of least squares iteration, you get the roto-translation matrix that takes a picture A to picture B.
Basically you get: Scale Factor S, T translation, rotation matrix R , and values the difference between the homologous points. This technique is commonly used in the transformation of geographical coordinates between different systems.
The first step in the implementation of the algorithm and Helmert 'to overlap the two plane figures formed by the points of origin and the destination based on their centers of gravity. So, we calculated the coefficients of the roto-translation matrix.
The Helmert transformation, however, can lead to a deformation orthogonality of axes and can not be used in case of return perspective.
4.2 The definition of the angles of rotation
Particular attention should be paid in the expression of the rotation matrix, since there is no single method for defining the corners, but these depend on the priorities that you choose in the axes that serve as "pivotal." We can in fact be defined before a rotation around X, then a round and then a Y around Z; but we can also define, however, before a rotation around Z, then around an X and then another around Z. In total, may be defined 24 different types of rotation around all three, or only around two axes, one of which is repeated in the permutation; in "GraphicsGems" [9] have defined all types of possible rotation. One of these representations is of particular importance and took the name of "Euler angles. Depending on the discipline in which it is applied, the rotation around an axis can certainly take a different name, in general, Roll call rotation about the Y axis, we will call the rotation around the X Pitch, Yaw or lists is the rotation about Z axis
However, the representation by the Euler angles, although intuitive, is reported to be difficult to use. And 'in fact more useful representation through a matrix containing the values \u200b\u200bof sine and cosine of the angles.
According Beinat, "Today's more the trend has arisen to consider the rotation matrices directly in their natural form, represented by the explicit components, just as it is managed in the computer's memory. Rarely is the need to 'extract 'the value of the Euler angles in the hidden value of the components of a matrix. "
4.3 The solution to the vanishing point
A first implementation of the program of photogrammetric restitution is based on the laws of perspective of descriptive geometry. This approach links the algorithm to the return of boxed items, and figures at right angles.
In essence, are calculated vanishing points of lines which belong to the edges of a rectangle in the image represented, and through the first two points of the third flight is calculated, determined through the center of the image, which is geometrically orthocentre the triangle of the joints. Once you have determined the triangle of the joints, the focal length is calculated, ie the scale of the image.
It then goes back to the points of the rectangle with a simple ratio of similar triangles.
This procedure returns the rectangle on a scale determined by a fixed distance from the point of view to 1. Now you can scale the rectangle, by imposing a real measure of his side. We calculate the scale ratio and the factor 1 is replaced by this new value. continuing to enter the coordinates of image points and indicating the level to which it belongs, namely the vanishing points, the program calculates the coordinates of the point in space, tying the previous paragraph.
If the polygon that is being rebuilt is a rectangle, parallel to the axes can be returned automatically also all the image points contained in it, using an algorithm based on homology and on a dichotomous division.
fact, is necessary on the actual rectangle, a grid determined by a value of acceptable coverage, and dividing the rectangle in half. We continue the splitting, always in the middle of its upper left. When this process reaches a resolution imposed, it is estimated the same grid on the image corresponding to the bounding polygon, the polygon dividing itself in half, but projecting the secant lines to the vanishing points. You can get the perspective grid, in which points correspond to the actual grid of the rectangle. At this point read by the image points, in terms of color values \u200b\u200band transfer these values \u200b\u200bto the corresponding real points of the rectangle, storing them in an image file, related to the rectangle.
As noted earlier, this algorithm will only return items or related to a rectangular box section. The main part of this algorithm is shown in Appendix B.
4.4 L 'Restorative algorithm of "Facade"
Under "Facade," by Paul Debevec in the Computer Science Division at the University of California at Berkeley [2], an algorithm is used to optimize the model parameters and the positions of the chamber to make the model consistent with the observed edges in the images.
The algorithm also uses a procedure to two times the initial estimate, which automatically calculates an estimate of the camera positions and parameters of the model, estimated to be close to correct solution, and this makes the non-linear optimization out of local minimum and facilitates convergence.
4.4.1 the objective function
The reconstruction algorithm of "Facade" works by minimizing an objective function O that sums the disparity between the projected model edges and corners marked in the images, O = ΣErr , Err where the difference is calculated for each edge.
Thus, the unknown parameters of the model and the positions of the room are calculated by minimizing O respect to these variables.
5 Towards the SVD solution
Estimate homography Picture -> Object [13].
In the case of a camera is not calibrated, an accurate estimate of the homography between image and object planes can be achieved through a number of known points corresponding image-object.
From each pair of points corresponding image-object we can extract two equations that are linear in the elements of matrix H . They are:
h11x h12y + + + h13 = h31xX h32yX h33X
h21x + + + H23 = h22y h31xY + + h32yY h33Y
For n correspondences we obtain a system of 2n equations in eight unknowns. If n = 4 we obtain an exact solution. Otherwise, if n> 4, the matrix is \u200b\u200boverdetermined, and H is estimated by a minimization scheme.
The solution is obtained using the method of Singular Value Decomposition (SVD).
This method minimizes an algebraic error which has no geometric meaning. And 'good practice to use this method to get a good initial solution and then execute a non-linear minimization to refine the solution by a more significant reduction of geometric errors.
Description of the SVD method:
Any mxn matrix to (m> = n) can be written as the product of an mxn matrix u " column-orthogonal, a diagonal nxn matrix with a positive or zero, and the transpose of a orthogonal matrix v nx n.
That is: A =
t u v W
where:
:
The elements of the diagonal matrix W are the Singular Values \u200b\u200bof the matrix A and non-negative numbers.
REFERENCES:
[1] V. Franco - M. Lo Brutto "Elements of Digital Photogrammetry" University of Palermo - Dispenza Course Topography-May 2003
[2] PE Debevec. "Modeling and Rendering Architecture from Photographs". PhD thesis, University of California at Berkeley, Computer Science Division, Berkeley CA, 1996. http://www.debevec.org/Thesis .
[3 ] R. Seidl, T. Reinhardt, "Canoma User Guide" - MetaCreations 1998
[4] C. Bräuer-Burchardt , K. Voss - Digital Image Processing Group, Friedrich-Schiller-University - “Facade Reconstruction of Destroyed Buildings Using Historical Photographs”, 2000
[5] R.Cantoni, G.Vassena, C.Lanzi “FROM THE SURVEY TO THE 3D ANIMATION: THE SANTA MARIA IN SOLARIO CHAPEL IN BRESCIA” - University of Brescia, Civil Engineering Dep. – 2000
[6] Frank A. van den Heuvel -“RECONSTRUCTION FROM A SINGLE ARCHITECTURAL IMAGE FROM THE MEYDENBAUER ARCHIVES” - Delft University of Technology, Department of Geodesy Delft – 2001
[7] V. Gergely - “CAMERA MATCHING IN COMPUTER GRAPHICS "- Master's Thesis Budapest University of Technology and Economics - 2003
[8] A. Beinat - "Technical Analysis of Procrustes and Datum Transformations in Surveying and Photogrammetry" - PhD Thesis Politecnico di Milano, 2000
[9] K. Shoemake, "Graphics Gems IV", Academic Press, 1994
[10] U. Neumann et al .- "Approaches to Large-Scale Urban Modeling" - University of Southern California, 2003
[11] JE Eaton, "GNU Octave Reference Manual" - Network Theory Ltd. , 1997
[12] S. Huot , Ch Colin - "MARINA: 3D Reconstruction from Images using Formal Projective Geometry" - Department of Computer Science. École des Mines de Nantes, France
[13] A. Criminisi - "Accurate Visual Metrology from Single and Multiple Images uncalibrated SPIN Springer's Computer Science - April 30, 2001
[14] R. Angeletti - "ExportToCanoma - http://exporttocanoma.blogspot.com -
March 2004 [15] R. de Rubertis - "electronic design" - Edizioni Kappa - 1979
[16] R. de Rubertis - "Computer Graphics - Applications and Research Laboratory of Automatic Drawing - Faculty of Architecture 1985
0 comments:
Post a Comment