Hi Sandura,

if your workflow is based on a Structure from Motion pipeline (many are these days), there is indeed first a feature detection step. In past decades, a wide variety of feature detectors have been developed. Aside from their effectiveness, they vary widely in computational complexity and the type of features they detect.

Afterwards, these features (which can be corners, blobs or lines) have to be described by so-called feature descriptors or feature vectors. Such a descriptor computes a feature vector with local characteristics to describe a local patch (whose size can vary) of pixels around each feature. Just as the detected feature itself, this vector should be invariant (i.e. robust to image noise and photometric plus geometric deformations).

Then, all descriptor vectors are matched between different images. To compute a match, a distance between the descriptors is generally used (e.g. the Euclidean distance). The dimension of the descriptor has a direct impact on the time this takes, and fewer dimensions are desirable for fast matching. However, lower-dimensional descriptor vectors are generally less distinctive than their high-dimensional counterparts.

A robust outlier detection algorithm such as RANSAC (RANdom SAmple Consensus) will ensure the rejection of probable false matches by testing them for consistency. This is done for all possible image pairs by checking if their putative matches fulfil the so-called epipolar geometry constraint : i.e. that the displacements of image features are a possible result solely of the motion of the camera between both images. At the end of this process, the fundamental matrices F of the image pairs are obtained: each of them is a 3 × 3 matrix depending on seven parameters that describes the motion (i.e. relative orientation) from the first to the second image.

Finally, the complete set of image correspondences (called tie points) for the whole image sequence is obtained after considering all meaningful image pairs. The set of corresponding image features thus obtained functions, together with the fundamental matrices, as input for the last steps of the structure form Motion (SfM) computation.

Relying on the algorithms that detect, describe and match local feature points throughout the multiple images, SfM computes the locations of those feature points in a local coordinate frame, creating a sparse 3D point cloud that represents the geometry/structure of the scene. This determination of a point’s 3D position when observed from two or more cameras is called image triangulation. However, image triangulation requires the knowledge of the images’ interior and exterior orientation (called camera intrinsics and extrinsics in computer vision).

These are obtained after combining all the relative orientations of the image pairs in form of their fundamental matrices. SfM can accomplish this as it is based on the projective reconstruction theorem, which states: "given a set of point correspondences in two views defined by the fundamental matrix, the 3D scene geometry and images’ projection matrices (which comprise all the orientation parameters) may be reconstructed from these correspondences alone, and any two such reconstructions from these correspondences are projectively equivalent".

However, rather than a projective reconstruction, a metric reconstruction is wanted: i.e. one in which orthogonal planes are at right angles, parallel lines stay parallel and the reconstructed 3D model is a scaled version of reality. This can be accomplished by running a simultaneous self-calibration / auto-calibration to define the camera’s interior orientation. The latter is stored for each image in the intrinsic parameter matrix (in photogrammetry, these are called the interior camera orientations).

Up to now all images were dealt with in pairs, for each of which a fundamental matrix was computed. Afterwards the oriented image pairs were combined to form the complete block of images and to yield the structure of the scene. The results obtained this way are, however, suboptimal because not all overlapping images are used at the same time and the discrepancies in the structure (caused by small errors during the feature measurement phase) are not optimally minimised. To overcome these problems, the final stage of most SfM algorithms is bundle adjustment. Bundle adjustment iteratively optimises the 3D structure and the projection matrices of all images simultaneously by performing a robust non-linear minimisation of the actual measurement errors, also known as re-projection errors. The technique was developed half a century ago in the field of photogrammetry but is now also largely applied in the computer vision community. The term bundle adjustment comes from the fact that the bundles of rays connecting camera/projection centres to 3D scene points are adjusted to minimise the sum of squared differences between the observed and re-projected image points.

This means that an SfM approach can recover the scene structure and camera projection matrices from image correspondences alone without prior knowledge about camera poses or interior orientation. There is thus no real need to use calibrated cameras and optics during the image acquisition stage, which makes the procedure very flexible and well suited for almost any kind of imagery. It needs to be noted, though, that a proper image network geometry is essential for reliably obtaining the exterior and interior orientation parameters.

Finally, it is It is essential to understand that the SfM output is characterised by a scale ambiguity. This means that if the entire scene is scaled by some factor and the distance between the camera positions is simultaneously scaled by the same scale factor, the projections of the scene points in the image will remain exactly the same. The reconstructed 3D scene obtained after a standard SfM approach is thus expressed in a local coordinate framework and equivalent to the real-world scene up to a global scaling, rotation and translation. These parameters can only be recovered via the use of additional data, which in turn define a coordinate reference system. Ideally, one should this import highly accurate camera positions or a minimum of three ground control points or known distances and use them as constraints in the bundle adjustment. This approach can correct for errors such as drift in the recovered camera and point locations, avoids instability of the bundle solution while the SfM output is directly georeferenced.

At this stage a georeferenced sparse 3D reconstruction of the scene is available. ‘Sparse’ because it is only based on the reconstructed set of image features. However, with the now known orientation of the images, it becomes possible to create a dense 3D model and compute orthophotographs. The essential step in this process is the computation of this denser 3D model. Alternatively, one could interpolate the sparse set of 3D points, but this would yield a far from optimal result. Therefore, it is better to run a multi-view stereo algorithm to compute a dense estimate of the surface geometry of the observed scene. Because these solutions operate on pixel values instead of on feature points, this additional step enables the generation of detailed 3D point clouds (which can be meshed) from the initially calculated sparse point clouds, hence reproducing fine details present in the scene.

I hope this helps!

Cheers,

Geert

Hi Sandura,

if your workflow is based on a Structure from Motion pipeline (many are these days), there is indeed first a feature detection step. In past decades, a wide variety of feature detectors have been developed. Aside from their effectiveness, they vary widely in computational complexity and the type of features they detect.

Afterwards, these features (which can be corners, blobs or lines) have to be described by so-called feature descriptors or feature vectors. Such a descriptor computes a feature vector with local characteristics to describe a local patch (whose size can vary) of pixels around each feature. Just as the detected feature itself, this vector should be invariant (i.e. robust to image noise and photometric plus geometric deformations).

Then, all descriptor vectors are matched between different images. To compute a match, a distance between the descriptors is generally used (e.g. the Euclidean distance). The dimension of the descriptor has a direct impact on the time this takes, and fewer dimensions are desirable for fast matching. However, lower-dimensional descriptor vectors are generally less distinctive than their high-dimensional counterparts.

A robust outlier detection algorithm such as RANSAC (RANdom SAmple Consensus) will ensure the rejection of probable false matches by testing them for consistency. This is done for all possible image pairs by checking if their putative matches fulfil the so-called epipolar geometry constraint : i.e. that the displacements of image features are a possible result solely of the motion of the camera between both images. At the end of this process, the fundamental matrices F of the image pairs are obtained: each of them is a 3 × 3 matrix depending on seven parameters that describes the motion (i.e. relative orientation) from the first to the second image.

Finally, the complete set of image correspondences (called tie points) for the whole image sequence is obtained after considering all meaningful image pairs. The set of corresponding image features thus obtained functions, together with the fundamental matrices, as input for the last steps of the structure form Motion (SfM) computation.

Relying on the algorithms that detect, describe and match local feature points throughout the multiple images, SfM computes the locations of those feature points in a local coordinate frame, creating a sparse 3D point cloud that represents the geometry/structure of the scene. This determination of a point’s 3D position when observed from two or more cameras is called image triangulation. However, image triangulation requires the knowledge of the images’ interior and exterior orientation (called camera intrinsics and extrinsics in computer vision).

These are obtained after combining all the relative orientations of the image pairs in form of their fundamental matrices. SfM can accomplish this as it is based on the projective reconstruction theorem, which states: "given a set of point correspondences in two views defined by the fundamental matrix, the 3D scene geometry and images’ projection matrices (which comprise all the orientation parameters) may be reconstructed from these correspondences alone, and any two such reconstructions from these correspondences are projectively equivalent".

However, rather than a projective reconstruction, a metric reconstruction is wanted: i.e. one in which orthogonal planes are at right angles, parallel lines stay parallel and the reconstructed 3D model is a scaled version of reality. This can be accomplished by running a simultaneous self-calibration / auto-calibration to define the camera’s interior orientation. The latter is stored for each image in the intrinsic parameter matrix (in photogrammetry, these are called the interior camera orientations).

Up to now all images were dealt with in pairs, for each of which a fundamental matrix was computed. Afterwards the oriented image pairs were combined to form the complete block of images and to yield the structure of the scene. The results obtained this way are, however, suboptimal because not all overlapping images are used at the same time and the discrepancies in the structure (caused by small errors during the feature measurement phase) are not optimally minimised. To overcome these problems, the final stage of most SfM algorithms is bundle adjustment. Bundle adjustment iteratively optimises the 3D structure and the projection matrices of all images simultaneously by performing a robust non-linear minimisation of the actual measurement errors, also known as re-projection errors. The technique was developed half a century ago in the field of photogrammetry but is now also largely applied in the computer vision community. The term bundle adjustment comes from the fact that the bundles of rays connecting camera/projection centres to 3D scene points are adjusted to minimise the sum of squared differences between the observed and re-projected image points.

This means that an SfM approach can recover the scene structure and camera projection matrices from image correspondences alone without prior knowledge about camera poses or interior orientation. There is thus no real need to use calibrated cameras and optics during the image acquisition stage, which makes the procedure very flexible and well suited for almost any kind of imagery. It needs to be noted, though, that a proper image network geometry is essential for reliably obtaining the exterior and interior orientation parameters.

Finally, it is It is essential to understand that the SfM output is characterised by a scale ambiguity. This means that if the entire scene is scaled by some factor and the distance between the camera positions is simultaneously scaled by the same scale factor, the projections of the scene points in the image will remain exactly the same. The reconstructed 3D scene obtained after a standard SfM approach is thus expressed in a local coordinate framework and equivalent to the real-world scene up to a global scaling, rotation and translation. These parameters can only be recovered via the use of additional data, which in turn define a coordinate reference system. Ideally, one should this import highly accurate camera positions or a minimum of three ground control points or known distances and use them as constraints in the bundle adjustment. This approach can correct for errors such as drift in the recovered camera and point locations, avoids instability of the bundle solution while the SfM output is directly georeferenced.

At this stage a georeferenced sparse 3D reconstruction of the scene is available. ‘Sparse’ because it is only based on the reconstructed set of image features. However, with the now known orientation of the images, it becomes possible to create a dense 3D model and compute orthophotographs. The essential step in this process is the computation of this denser 3D model. Alternatively, one could interpolate the sparse set of 3D points, but this would yield a far from optimal result. Therefore, it is better to run a multi-view stereo algorithm to compute a dense estimate of the surface geometry of the observed scene. Because these solutions operate on pixel values instead of on feature points, this additional step enables the generation of detailed 3D point clouds (which can be meshed) from the initially calculated sparse point clouds, hence reproducing fine details present in the scene.

I hope this helps!

Cheers,

Geert

Hi Sandura,

In general, DSM is interpolated from dense 3D point cloud. So the basic task of DSM generation is to generate dense 3D point cloud. There are two major means to get dense 3D point cloud, namely, photogrammetry and LiDAR. Photogrammetry is to extract dense 3D point cloud from photos (your question is about this mean) while LiDAR is to get 3D point cloud by light detection and ranging.

So how to get dense 3D point cloud from photos? There are two key words here, “dense” and “3D point”.

Let’s answer a simplified question: how to get a 3D point from photos? Suppose there are three points on a plane, and the coordinates of two points are known, now how can we get the coordinate of the third point? There are two ways, 1) observe the two known points from the third point, or 2) observe the third point from the two known points. No matter which way is chosen, the coordinate of the third point can be calculated by trigonometric function. In fact, this method is called triangulation. Triangulation can be not only used on a 2D plane, but also used in 3D space. If a 3D point in the object space is viewed in two photos, then the 3D point and the two projected points (one projected point for each photo) form a triangle in 3D object space. Now if we know the coordinates of projected points, we can get the coordinate of the 3D point in the object using triangulation. Moreover, the projected point is 2D point on the photo and its coordinate depends on the coordinate of camera center. Therefore, we can get coordinate of each projected point if we get the coordinate of camera center.

And bundle block adjustment is to get the coordinates of camera centers. In the first answer, Geert has given a very detailed explanation of bundle block adjustment.

However, bundle block adjustment can only get coordinates of camera centers, but neither a 3D point nor dense 3D point cloud. To get a 3D point or dense 3D point cloud, we have to figure out which two projected points on the photos are corresponding in order to construct a triangle with the potential 3D point in the object space. And then the coordinate of the potential 3D point can be calculated via triangulation. In other word, if we know a pair of correspondence of projected points on two photos, we can a 3D point coordinate. If we know dense (pixel-wise for nowadays) correspondence of photos, we can get 3D point cloud. And the process of finding dense correspondence of photos is also called dense image matching in photogrammetry.

Therefore, DSM generation has one basic principle: Triangulation and two key technologies: Bundle Block Adjustment and Dense Image Matching.

P.S. DSM can also directly generated without generating 3D point could. (refer to our paper: Direct Digital Surface Model Generation by Semi-Global Vertical Line Locus Matching ). And also in my opinion, you question might be equal to "what is photogrammetry?" because the basic task of photogrammetry is to extract DSM from photos. So you can refer the book Digital Photogrammetry (A Practical Course) written by Wilfried Linder.

Yanfeng,

Sorry, the sentence "However, bundle block adjustment can only get coordinates of camera centers, but neither a 3D point nor dense 3D point cloud. " is not correct. Actually, bundle block adjustment can not only get coodinates of camera centers but also sparse 3D point cloud. However, DSM generation need dense 3D point cloud, so dense image matching is an indispensable process.

Thanks a lot Geert for such a detailed explanation. It is indeed very helpful. I am grateful to you. @Zhang, Thank you also for further explanation. Yes the question might have seemed like asking "What is photogrammetry". But my focus was to know the step by step process from raw photos till DSM,orthophoto which is not the exactly same as in photogrammetry books.

@Zhang thanks a lot for the book. Though late reply wanted to thank you for suggesting this book. It was very helpful. Contemporary compared to old photogrammetry text books we followed in our institute.