Epipolar geometry
The epipolar geometry (rarely also core beam geometry ) is a mathematical model of the geometry that represents the geometric relationships between different camera images of the same object. With their help, the dependence between corresponding image points describe - ie the points that generates a single object point in the two camera images. Although its foundations were examined in 1883 by Guido Hauck and 1908 by Horst von Sanden, reached the epipolar geometry only with the automatic processing of digital images, especially in the area of machine vision to greater importance.
Notably, the epipolar geometry is used in the extraction of 3D information from images. They are supported by the correspondence analysis, ie the assignment of corresponding points, and reduces the required search effort significantly.
- 4.1 Homogeneous coordinates and projection matrix
- 4.2 Relationship between corresponding points
- 4.3 Properties of the fundamental matrix
- 5.1 7 -point algorithm
- 5.2 8-point algorithm
- 9.1 distortion
- 9.2 panoramic cameras
Principle
A camera can be modeled geometrically by a pinhole camera. In this lie every point of the recorded object, the center of projection and the corresponding pixel on a line during recording. If the object point twice taken from different positions, can be at a later evaluation by the orientations of the cameras, the intersection of two straight lines, and thus the coordinates of the object point calculated. A 3D reconstruction is possible, when pixels of an object point were located in the two images. The epipolar geometry is used to support this localization: the point in the first image is given, restricts itself with known epipolar geometry of the search area in the second image on a line a.
The adjacent left graph shows the geometric relationships are clarified. Shown in addition to the image and object points, and the two projection centers the two image planes of the two cameras. These are folded in front of the projection centers. This simplifies the presentation, but does not change the geometrical relationships. The object point X is formed in the camera image 1 from the pixel xL. Based on this pixel, it is only possible to the associated beam, where X is to be determined. Possible object points X1, X2 or X3, which correspond to X as well as the pixel xL lie on this ray. This beam and therefore all possible object points are mapped in the recording of the object from a different position in the second image on a straight line. This reduces the search for the pixel to corresponding pixel xL xR in the second image.
With the help of epipolar geometry is a simple relation between corresponding points can be made without knowledge of the camera positions. From a known epipolar geometry, although information about the relative position of the cameras with each other can be derived, however, for their determination it is not necessary to know the explicit camera positions. The epipolar geometry depends only on the parameters of the cameras, and is thus independent of the structure of the recorded scene.
To describe the epipolar geometry and its elements there exists a fixed terminology. The plane, which span the two projection centers of the cameras and the recorded object point is called epipolar plane. This cuts the two images in each case a straight line, the so-called epipolar line. Only on this, a corresponding image point located at a given point in the other image. The straight line connecting the centers of the two projection cameras, pierces the two image planes in each case one point, the epipole. The two epipoles change their position in each image is not as long as the location of the cameras to each other remains stable. The epipole of an image is also the image of the projection center of the other camera. Through him run all epipolar lines of a picture, but he himself can differ depending on the location of the cameras are to each other outside of the actual image.
Were in the field of photogrammetry and are partly still the core concepts beam geometry, crux, core and core -level line instead of epipolar geometry, epipole, and epipolar epipolar line.
Applications
The epipolar geometry is mainly used in projective geometry, photogrammetry and computer vision. Their main purpose is the correspondence analysis. Searching for a salient point in an image, the corresponding point in the other image, the entire image needs to be investigated in case of unknown epipolar geometry. If the epipolar geometry is known, the search for the corresponding point can be limited to the epipolar line. This causes a significant reduction of the search space. For this reason, the epipolar geometry is used primarily where a scene or an object must be analyzed in three dimensions quickly and with little effort using cameras. Important applications include machine vision, the measurement of workpieces for quality inspection, the buildings consumption at the architectural photogrammetry or aerial photogrammetry to create maps works.
Computer Vision
The epipolar geometry limits in the correspondence search for object identification the search scope to the epipolar lines, and caused by an enormous computational time savings. At the same time it reduces the number of incorrect assignments of corresponding points by the search space limitation. Both of which are of great advantage in machine vision. In particular, in the autonomous robotics simple calculations for a high performance are required, on the one hand because of the limited hardware on mobile platforms and on the other because of the need for quick reactions to avoid a collision. Thus came to a participant in the DARPA Grand Challenge, a competition of unmanned ground vehicles, the program library OpenCV to use, fast routines for computing the epipolar geometry and its application in the correspondence analysis involves.
Self-calibration of cameras
3D reconstruction of a scene from photographs requires that the calibration of the cameras is known. Since the epipolar geometry describes the projective relationship between two images, it is used in the so-called self-calibration, ie the automatic determination of the camera parameters. The epipolar geometry is not used for correspondence search, but reversed reconstructed from known correspondences, the full camera calibration.
History
The history of the epipolar geometry is closely connected with the history of photogrammetry. The first, who analyzed the underlying geometric relationships, was the mathematician Guido Hauck. He published in 1883 in the Journal of Pure and Applied Mathematics an article in which the term core point was used for the first time:
" Let ( Figure 1a ) and two projection planes and the corresponding projection centers. The intersection of the two projection planes we call basic cut. The connecting line may intersect the two projection planes in the points, and which we call the core points of the two levels. "
A first comprehensive presentation authored in 1908, Horst von Sanden part of his dissertation The determination of the key points in photogrammetry. He described in this thesis to a simpler and more accurate determination of the key points.
In the prevailing until the introduction of digital technology known as analog photogrammetry with optical-mechanical Photography and evaluation of the correspondence analysis was performed manually. Since a human operator can easily assign corresponding points at sufficiently scene structure, the findings have rarely been applied. It was not until the advent of digital photogrammetry with digital photography and computer-based offline analysis from the 1980s and the rising demand of an automated image analysis in the field of machine vision led to a renewed intensive exploration of the epipolar geometry and its application. A first work, which is the rediscovery of the subject, was the publication of Christopher Longuet- Higgins in the journal Nature. Since then, many scientists are working with the epipolar geometry, including Huang and Faugeras, Horn and Vieville and Ling edge.
Mathematical Description
The epipolar geometry establishes a relationship between the image coordinates of corresponding points. The image coordinates are often in Cartesian coordinates, but can also be given in affine coordinates. The origin of the image coordinate system of an image is usually in the middle or a corner of the image. For digital images ( CCD images or scanned images ), for example, the row and column of pixels can be used as coordinates. If the row and column differ resolution or the axes of the coordinate system are not perpendicular to each other, these coordinates are affine.
The relationship between the image coordinates of corresponding points is described by a fundamental matrix. With it can be at any given point in the first image, the corresponding epipolar line in the second image to determine on which there is the corresponding point.
Homogeneous coordinates and projection matrix
The image of the object points on the image plane can be described by the use of projective geometry in homogeneous coordinates. Homogeneous coordinates with respect to Cartesian coordinates or affine extended to a coordinate and only up to a scale factor uniquely. The two-dimensional Cartesian or affine coordinates correspond to the homogeneous coordinates. The homogeneous coordinates may not all simultaneously be zero, and represents the same point in two-dimensional projective space, the projective plane. The same applies to the three-dimensional space.
Each point of the two-dimensional space or three-dimensional space can be described by a homogeneous coordinate. A point of the projective space corresponds, however, only a point in the affine space if it is. The points of the projective plane with are called points at infinity. As it can be interpreted as intersections of parallel lines, is omitted in projective geometry, the distinction between the parallel and non-parallel straight lines. This is advantageous in perspective, for example in the description of vanishing points. Since the equation that a straight line in the projective plane corresponds to [F 1] Just called at infinity at infinity, the set of points.
With homogeneous coordinates allows the mapping of the three-dimensional object points with the coordinates on the two-dimensional image plane described as a linear function:
The Cartesian (or affine ) image coordinates are obtained from and when. 3 x 4 projection matrix describes the perspective image of the object points on the image plane. It contains data on the orientation of the camera. As this figure shows a dimension - the distance of the object from the camera - is lost, it is not clearly reversible.
Relationship between corresponding points
Derivation of the fundamental matrix is based on the idea that in the first image to select a point, to determine any object point which is imaged on that pixel, and then to calculate the pixel in the second image. This point and the epipole located on the epipolar line to belonging in the image plane of the second image and describe it so clearly.
If a point in the first picture given, can be calculated using the corresponding projection matrix of the beam, on which the corresponding object point is located, specify. The object point itself can not be determined, since the distance from the camera is unknown. An arbitrary point on the beam can be calculated using the pseudo-inverse:
This point can be illustrated with the projection matrix of the second camera in the second image:
For a point on the epipolar line belonging to the second image is known. Another point on this epipolar line is the epipole, who is the image of the projection center of the first camera:
The epipolar line is described in homogeneous coordinates by the linear equation, [F 1] which can be calculated as the cross product of the two given straight points:
This cross product can be written with a skew-symmetric matrix as a matrix multiplication:
Where the bracketed term is combined to the fundamental matrix. Thus the equation of the epipolar line and the relationship between corresponding points:
Or:
This equation is referred to as epipolar.
A specialization of the fundamental matrix is the essential matrix. This results when normalized image coordinates are used, where the origin of the Cartesian coordinate system image is the main point of the image. Since this condition need not be met in the fundamental matrix, it is compared to the essential matrix with fewer assumptions.
Properties of the fundamental matrix
The fundamental matrix (also called bifocal tensor ) contains all the information on the epipolar geometry. It can be determined from the image coordinates of corresponding points without knowledge of the orientation of the cameras ( ie, without knowledge of the projection matrices and and the center of projection ).
The 3 × 3 fundamental matrix can be uniquely determined only up to a scale factor, as the multiplication of the fundamental matrix equal to 0 does not change with any number on the validity of the epipolar. Thus, the 9 elements are initially only 8 independent. Since the matrix - such as any skew-symmetric matrix with odd - is singular is singular, so that the determinant is 0. This additional condition reduces the degree of freedom of the fundamental matrix to 7
By means of the fundamental matrix can be calculated to a point in the first image, the corresponding epipolar line in the second image:
And vice versa, to a point in the second image the epipolar line in the first frame:
For a given epipolar line in an image are not the original point in the other image can be calculated. For this purpose, the fundamental matrix should be inverted, which is not possible due to their singularity.
Since the epipole lies on all epipolar lines must
Apply to everyone, so that the epipole and according to the epipole from the equations
Can be determined. Also from these equations, it is apparent that the determinant of the fundamental matrix must be 0, otherwise the equations have only solutions.
Calculation
The fundamental matrix and thus the epipolar geometry can be - as shown in section relationship between corresponding points - calculated directly from the two projection matrices and a projection center at a known calibration of the two cameras. Since the computation of the fundamental matrix is usually performed prior to a determination of the projection matrices, this case rarely occurs. The following explains how can only be calculated with the help of point correspondences.
To determine from a set of corresponding image points, the fundamental matrix, the epipolar is multiplied out:
Or in vector notation:
With
From point correspondences, the following homogeneous system of linear equations can be set up (the upper index indicates the point number):
Since the coordinates of corresponding points satisfy the epipolar, the columns of are linearly dependent. The matrix has therefore ideally no more than the rank 8 However, this applies to more than 8 lines only when no measurement errors in the coordinates and no mismatched pairs of points are present. Since it is not full column rank, has a solution exists from the null space of for (apart from the trivial solution).
Generally occur in the determination of the correspondences to smaller measurement inaccuracies because the pixels can only be identified with a finite accuracy. The determined from the solution vector fundamental matrix thus has not the rank 2 and thus is not singular. This leads to the fact that not all intersect with this particular fundamental matrix the epipolar lines of a picture in epipole.
In practice, two methods for calculating the fundamental matrix are used, these refer to the singularity condition: the 7- point algorithm and the 8-point algorithm. In both methods usually are not directly used the measured coordinates of the image points, but normalizes the coordinates before. The coordinate systems are shifted in both images so that the origin is the center of gravity of the pixels respectively, and then the coordinates scaled so that their values are in the order 1. This normalization may be a significant improvement in the results achieved.
7 -point algorithm
This method uses seven point correspondences to compute the fundamental matrix. Since only up to a factor is clearly rich 7 points along with the condition, in order to determine the elements 9. At 7 point correspondences, the system of equations contains only 7 equations. There are therefore two linearly independent solutions of the null space of. The fundamental matrix is determined as a linear combination of and formed matrices and:
To now be selected from the set of solutions, which has rank 2, is exploited, that due to the singularity condition of the determinant equal to 0 must be:
This general cubic equation has - if they do not degenerate to a quadratic equation - at least one and at most three real solutions. With each solution a fundamental matrix can be calculated. When multiple solutions exist, more points are required to determine a unique solution. It is the solution selected in satisfying the epipolar also for more points or is approximately satisfied in measurement inaccuracies in the coordinates.
If it is, the cubic term is zero, so that a quadratic equation is present. This equation has at most two real solutions, but can be no real solution. However, since the determinant of the matrix vanishes, is singular, and thus a solution for the desired fundamental matrix, so that overall again be one to three Fundamentalmatrizen find a solution. Alternatively, the matrix may be multiplied by -1. This then gives again a cubic equation with the solution. This procedure can also be used for numerical reasons, if the amount of is very high.
8-point algorithm
In general, more than seven point correspondences are available. The one described in the following eight -point algorithm requires a minimum of 8 corresponding point pairs, but it is also more points are used. The idea of this method comes from Longuet- Higgins.
In the first step only the equation system is considered without taking into account the condition. Ideally, the rank of the matrix 8, in practice it is, however, more than 8 points for measurement inaccuracies not the case, so that the solution can not be determined from the null space of. Instead, the solution is determined using the method of least squares or by the determination of the eigenvalues. By using more points than are required for a unique solution, may also be examined whether false correspondences or other outliers are present.
Wherein the least squares method is determined such that is minimum. Since only up to a factor is unique, a condition needs to be introduced, for example, by an element of the same one is set. The problem here is that this should not just be an element which is 0 or very small, which is a priori not known. However, you can try several options. In the second method is also minimized, but with the condition. This leads to the result that the solution of the eigenvector corresponding to the smallest eigenvalue of the matrix.
The fundamental matrix formed from the solution is not singular, in general. Therefore, this condition must be met in a second step. This is decomposed by singular value decomposition in. is a diagonal matrix containing the singular values . The smallest is set to 0, and then from the matrices, and again calculates the fundamental matrix. Because now a singular value is 0, the fundamental matrix satisfies the singularity condition.
Of the 8-point algorithm is a simple method for determining the fundamental matrix, but it is susceptible to measurement errors and incorrect correspondence. This is because the singularity condition of the fundamental matrix is only subsequently met, and that the minimal size has no physical meaning. There are other methods that do not have these disadvantages. However, these methods are expensive and are used more rarely in practice.
Automatic calculation
Especially in machine vision an automatic computation of the epipolar geometry is necessary because, for example, autonomous robots are to operate without human assistance. For the first step a lot of corresponding points is determined. This is done using an interest operator, with which distinct points can be located in an image. If these are found, it is determined at each point in the first image of the closest to him in the second image. A correspondence analysis provides a measure of the similarity. On the basis of different perspectives by which the two cameras viewing the scene of similar image sections that do not represent the same object, and image noise, the amount of corresponding points generally contains a greater number of mismatches and therefore can not be used directly to calculate the fundamental matrix be.
The following illustrations show a church that was taken from two points. The second camera position is further to the right and a little further away from the church tower than the first. Figures 1 and 2 show distinctive points and Figure 3 shows the result of the correspondence analysis, in which similar image sections - were compared with each other - without taking into account the imaging geometry. It is clearly seen that not all correspondences were determined correctly. Especially in the area of the trees this is not the case here, since the branches all have a similar shape and brightness, and therefore the correspondence analysis leads to incorrect results. For example, correspondences are found to prominent points in the second image of the right tree, though it is not visible in the other image.
- Correspondence Analysis
2 Right figure with distinct points.
3 Putative correspondences as vectors
The mismatches must be excluded before calculating means of suitable methods for the separation and elimination of outliers. To the so-called RANSAC algorithm is commonly used. This algorithm can detect mismatches in pairs of points. The calculation of applied it consists of the following steps:
The fundamental matrix is then determined by the largest amount of pairs of points from step 3 and the 8-point algorithm. Then again can be performed a correspondence analysis, in which the calculated fundamental matrix is used ( as described, the search area thereby reduced by corresponding points on the epipolar line ) and a lower value for the similarity measure is accepted. These last two steps may be repeated iteratively until the number of correspondences is stable.
The following two diagrams illustrate the result. The accepted correspondences are shown in Figure 1 as red vectors. Figure 2 shows selected points and their epipolar lines are shown in the right image. Correctly assigned distinctive points and their epipolar lines are shown in red. Points of correspondence analysis, which do not satisfy the epipolar where the point in the right image does not lie on the corresponding epipolar line are drawn in green. Incorrect correspondences are shown in blue. Although these points satisfy the epipolar and show similar image sections, but they are not pixels of the same object point. The epipole in the right image is the intersection of the epipolar lines and is left out of the picture.
- Result of the calculation
2 Some epipolar lines, calculated with.
Special cases
In certain positions of the cameras with each other may occur special circumstances. Two arrangements are particularly relevant to practice in machine vision:
In these special cases, simplifies the correspondence search, since the epipolar geometry is known. In configurations where camera views are only approximately parallel, this condition can be produced by subsequent rectification.
Extension to more than two images
The Trifokalgeometrie is the extension of epipolar geometry to three images. If the position of an object point in two images is given, is its position in the third image of the intersection of the two epipolar lines in this image. Thus, in contrast to the image pair, there is a clear result, if the point is not in the Trifokalebene ( the layer that is formed from the three centers of projection ) is or three projection centers lie on a line. The arrangement in which a 3-D point lies on the Trifokalebene is referred to as a singular event.
It is possible to extend the epipolar geometry to more than three images. This is common practice in only four views. Here exists the so-called quadrifokale tensor, which describes the relationship of image points and lines between these images. However, no mathematical relationships have been studied for more than four views, as the complexity of modeling and computation is substantially higher and in most applications, starting with the fifth camera in the additional information gain only is low.
Deviations from the model of the pinhole camera
The described relation between corresponding image points, which can be completely described by the fundamental matrix, is valid only for still images that can be modeled by a pinhole camera. If, for example, distortions in the image on the image plane, or is the image area no level, these variations are taken into account when the epipolar geometry. In particular, the epipolar lines, on which the to a pixel in the first image corresponding image point is to look in the second picture, not straight lines.
Distortion
Only with high-quality lenses hardly occurs distortion. For other lenses and corresponding accuracy requirements, the distortion is taken into account. The distortion can often be modeled as radial distortion, that is, it decreases with the distance from the Verzeichnungszentrum (usually near the center of the image ) to.
A camera is calibrated to known and the distortion, the image can be corrected. With these corrected images can then be used as with distortion-free images.
Under certain conditions, the distortion can be considered in an extended fundamental matrix. In this case, a distortion is adopted for each image, which can be described by a respective ( unknown ) parameters and corresponds to the replacement of the flat screen by a square area in the three-dimensional projective space. The relationship between two corresponding points is then described by one - fundamental matrix with 9 degrees of freedom.
Panoramic cameras
For panoramic cameras, allowing for pictures with large picture angle, the recording geometry can not be modeled by a pinhole camera with a flat image surface. The description of the epipolar geometry depends on the type of panoramic camera. If the camera example, from a pinhole camera and a hyperbolic mirror, the epipolar lines form conic sections.