1 // Copyright (c) 2018, ETH Zurich and UNC Chapel Hill.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are met:
6 //
7 // * Redistributions of source code must retain the above copyright
8 // notice, this list of conditions and the following disclaimer.
9 //
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
12 // documentation and/or other materials provided with the distribution.
13 //
14 // * Neither the name of ETH Zurich and UNC Chapel Hill nor the names of
15 // its contributors may be used to endorse or promote products derived
16 // from this software without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE
22 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 // POSSIBILITY OF SUCH DAMAGE.
29 //
30 // Author: Johannes L. Schoenberger (jsch-at-demuc-dot-de)
31
32 #ifndef COLMAP_SRC_BASE_RECONSTRUCTION_H_
33 #define COLMAP_SRC_BASE_RECONSTRUCTION_H_
34
35 #include <unordered_map>
36 #include <unordered_set>
37 #include <vector>
38
39 #include <Eigen/Core>
40
41 #include "base/camera.h"
42 #include "base/database.h"
43 #include "base/image.h"
44 #include "base/point2d.h"
45 #include "base/point3d.h"
46 #include "base/track.h"
47 #include "util/alignment.h"
48 #include "util/types.h"
49
50 namespace colmap {
51
52 struct PlyPoint;
53 struct RANSACOptions;
54 class DatabaseCache;
55 class CorrespondenceGraph;
56 class SimilarityTransform3;
57
58 // Reconstruction class holds all information about a single reconstructed
59 // model. It is used by the mapping and bundle adjustment classes and can be
60 // written to and read from disk.
61 class Reconstruction {
62 public:
63 struct ImagePairStat {
64 // The number of triangulated correspondences between two images.
65 size_t num_tri_corrs = 0;
66 // The number of total correspondences/matches between two images.
67 size_t num_total_corrs = 0;
68 };
69
70 Reconstruction();
71
72 // Get number of objects.
73 inline size_t NumCameras() const;
74 inline size_t NumImages() const;
75 inline size_t NumRegImages() const;
76 inline size_t NumPoints3D() const;
77 inline size_t NumImagePairs() const;
78
79 // Get const objects.
80 inline const class Camera& Camera(const camera_t camera_id) const;
81 inline const class Image& Image(const image_t image_id) const;
82 inline const class Point3D& Point3D(const point3D_t point3D_id) const;
83 inline const ImagePairStat& ImagePair(const image_pair_t pair_id) const;
84 inline ImagePairStat& ImagePair(const image_t image_id1,
85 const image_t image_id2);
86
87 // Get mutable objects.
88 inline class Camera& Camera(const camera_t camera_id);
89 inline class Image& Image(const image_t image_id);
90 inline class Point3D& Point3D(const point3D_t point3D_id);
91 inline ImagePairStat& ImagePair(const image_pair_t pair_id);
92 inline const ImagePairStat& ImagePair(const image_t image_id1,
93 const image_t image_id2) const;
94
95 // Get reference to all objects.
96 inline const EIGEN_STL_UMAP(camera_t, class Camera) & Cameras() const;
97 inline const EIGEN_STL_UMAP(image_t, class Image) & Images() const;
98 inline const std::vector<image_t>& RegImageIds() const;
99 inline const EIGEN_STL_UMAP(point3D_t, class Point3D) & Points3D() const;
100 inline const std::unordered_map<image_pair_t, ImagePairStat>& ImagePairs()
101 const;
102
103 // Identifiers of all 3D points.
104 std::unordered_set<point3D_t> Point3DIds() const;
105
106 // Check whether specific object exists.
107 inline bool ExistsCamera(const camera_t camera_id) const;
108 inline bool ExistsImage(const image_t image_id) const;
109 inline bool ExistsPoint3D(const point3D_t point3D_id) const;
110 inline bool ExistsImagePair(const image_pair_t pair_id) const;
111
112 // Load data from given `DatabaseCache`.
113 void Load(const DatabaseCache& database_cache);
114
115 // Setup all relevant data structures before reconstruction. Note the
116 // correspondence graph object must live until `TearDown` is called.
117 void SetUp(const CorrespondenceGraph* correspondence_graph);
118
119 // Finalize the Reconstruction after the reconstruction has finished.
120 //
121 // Once a scene has been finalized, it cannot be used for reconstruction.
122 //
123 // This removes all not yet registered images and unused cameras, in order to
124 // save memory.
125 void TearDown();
126
127 // Add new camera. There is only one camera per image, while multiple images
128 // might be taken by the same camera.
129 void AddCamera(const class Camera& camera);
130
131 // Add new image.
132 void AddImage(const class Image& image);
133
134 // Add new 3D object, and return its unique ID.
135 point3D_t AddPoint3D(
136 const Eigen::Vector3d& xyz, const Track& track,
137 const Eigen::Vector3ub& color = Eigen::Vector3ub::Zero());
138
139 // Add observation to existing 3D point.
140 void AddObservation(const point3D_t point3D_id, const TrackElement& track_el);
141
142 // Merge two 3D points and return new identifier of new 3D point.
143 // The location of the merged 3D point is a weighted average of the two
144 // original 3D point's locations according to their track lengths.
145 point3D_t MergePoints3D(const point3D_t point3D_id1,
146 const point3D_t point3D_id2);
147
148 // Delete a 3D point, and all its references in the observed images.
149 void DeletePoint3D(const point3D_t point3D_id);
150
151 // Delete one observation from an image and the corresponding 3D point.
152 // Note that this deletes the entire 3D point, if the track has two elements
153 // prior to calling this method.
154 void DeleteObservation(const image_t image_id, const point2D_t point2D_idx);
155
156 // Delete all 2D points of all images and all 3D points.
157 void DeleteAllPoints2DAndPoints3D();
158
159 // Register an existing image.
160 void RegisterImage(const image_t image_id);
161
162 // De-register an existing image, and all its references.
163 void DeRegisterImage(const image_t image_id);
164
165 // Check if image is registered.
166 inline bool IsImageRegistered(const image_t image_id) const;
167
168 // Normalize scene by scaling and translation to avoid degenerate
169 // visualization after bundle adjustment and to improve numerical
170 // stability of algorithms.
171 //
172 // Translates scene such that the mean of the camera centers or point
173 // locations are at the origin of the coordinate system.
174 //
175 // Scales scene such that the minimum and maximum camera centers are at the
176 // given `extent`, whereas `p0` and `p1` determine the minimum and
177 // maximum percentiles of the camera centers considered.
178 void Normalize(const double extent = 10.0, const double p0 = 0.1,
179 const double p1 = 0.9, const bool use_images = true);
180
181 // Apply the 3D similarity transformation to all images and points.
182 void Transform(const SimilarityTransform3& tform);
183
184 // Merge the given reconstruction into this reconstruction by registering the
185 // images registered in the given but not in this reconstruction and by
186 // merging the two clouds and their tracks. The coordinate frames of the two
187 // reconstructions are aligned using the projection centers of common
188 // registered images. Return true if the two reconstructions could be merged.
189 bool Merge(const Reconstruction& reconstruction,
190 const double max_reproj_error);
191
192 // Align the given reconstruction with a set of pre-defined camera positions.
193 // Assuming that locations[i] gives the 3D coordinates of the center
194 // of projection of the image with name image_names[i].
195 bool Align(const std::vector<std::string>& image_names,
196 const std::vector<Eigen::Vector3d>& locations,
197 const int min_common_images);
198
199 // Robust alignment using RANSAC.
200 bool AlignRobust(const std::vector<std::string>& image_names,
201 const std::vector<Eigen::Vector3d>& locations,
202 const int min_common_images,
203 const RANSACOptions& ransac_options);
204
205 // Find specific image by name. Note that this uses linear search.
206 const class Image* FindImageWithName(const std::string& name) const;
207
208 // Find images that are both present in this and the given reconstruction.
209 std::vector<image_t> FindCommonRegImageIds(
210 const Reconstruction& reconstruction) const;
211
212 // Update the image identifiers to match the ones in the database by matching
213 // the names of the images.
214 void TranscribeImageIdsToDatabase(const Database& database);
215
216 // Filter 3D points with large reprojection error, negative depth, or
217 // insufficient triangulation angle.
218 //
219 // @param max_reproj_error The maximum reprojection error.
220 // @param min_tri_angle The minimum triangulation angle.
221 // @param point3D_ids The points to be filtered.
222 //
223 // @return The number of filtered observations.
224 size_t FilterPoints3D(const double max_reproj_error,
225 const double min_tri_angle,
226 const std::unordered_set<point3D_t>& point3D_ids);
227 size_t FilterPoints3DInImages(const double max_reproj_error,
228 const double min_tri_angle,
229 const std::unordered_set<image_t>& image_ids);
230 size_t FilterAllPoints3D(const double max_reproj_error,
231 const double min_tri_angle);
232
233 // Filter observations that have negative depth.
234 //
235 // @return The number of filtered observations.
236 size_t FilterObservationsWithNegativeDepth();
237
238 // Filter images without observations or bogus camera parameters.
239 //
240 // @return The identifiers of the filtered images.
241 std::vector<image_t> FilterImages(const double min_focal_length_ratio,
242 const double max_focal_length_ratio,
243 const double max_extra_param);
244
245 // Compute statistics for scene.
246 size_t ComputeNumObservations() const;
247 double ComputeMeanTrackLength() const;
248 double ComputeMeanObservationsPerRegImage() const;
249 double ComputeMeanReprojectionError() const;
250
251 // Read data from text or binary file. Prefer binary data if it exists.
252 void Read(const std::string& path);
253 void Write(const std::string& path) const;
254
255 // Read data from binary/text file.
256 void ReadText(const std::string& path);
257 void ReadBinary(const std::string& path);
258
259 // Write data from binary/text file.
260 void WriteText(const std::string& path) const;
261 void WriteBinary(const std::string& path) const;
262
263 // Convert 3D points in reconstruction to PLY point cloud.
264 std::vector<PlyPoint> ConvertToPLY() const;
265
266 // Import from other data formats. Note that these import functions are
267 // only intended for visualization of data and usable for reconstruction.
268 void ImportPLY(const std::string& path);
269
270 // Export to other data formats.
271 bool ExportNVM(const std::string& path) const;
272 bool ExportBundler(const std::string& path,
273 const std::string& list_path) const;
274 void ExportPLY(const std::string& path) const;
275 void ExportVRML(const std::string& images_path,
276 const std::string& points3D_path, const double image_scale,
277 const Eigen::Vector3d& image_rgb) const;
278
279 // Extract colors for 3D points of given image. Colors will be extracted
280 // only for 3D points which are completely black.
281 //
282 // @param image_id Identifier of the image for which to extract colors.
283 // @param path Absolute or relative path to root folder of image.
284 // The image path is determined by concatenating the
285 // root path and the name of the image.
286 //
287 // @return True if image could be read at given path.
288 bool ExtractColorsForImage(const image_t image_id, const std::string& path);
289
290 // Extract colors for all 3D points by computing the mean color of all images.
291 //
292 // @param path Absolute or relative path to root folder of image.
293 // The image path is determined by concatenating the
294 // root path and the name of the image.
295 void ExtractColorsForAllImages(const std::string& path);
296
297 // Create all image sub-directories in the given path.
298 void CreateImageDirs(const std::string& path) const;
299
300 private:
301 size_t FilterPoints3DWithSmallTriangulationAngle(
302 const double min_tri_angle,
303 const std::unordered_set<point3D_t>& point3D_ids);
304 size_t FilterPoints3DWithLargeReprojectionError(
305 const double max_reproj_error,
306 const std::unordered_set<point3D_t>& point3D_ids);
307
308 void ReadCamerasText(const std::string& path);
309 void ReadImagesText(const std::string& path);
310 void ReadPoints3DText(const std::string& path);
311 void ReadCamerasBinary(const std::string& path);
312 void ReadImagesBinary(const std::string& path);
313 void ReadPoints3DBinary(const std::string& path);
314
315 void WriteCamerasText(const std::string& path) const;
316 void WriteImagesText(const std::string& path) const;
317 void WritePoints3DText(const std::string& path) const;
318 void WriteCamerasBinary(const std::string& path) const;
319 void WriteImagesBinary(const std::string& path) const;
320 void WritePoints3DBinary(const std::string& path) const;
321
322 void SetObservationAsTriangulated(const image_t image_id,
323 const point2D_t point2D_idx,
324 const bool is_continued_point3D);
325 void ResetTriObservations(const image_t image_id, const point2D_t point2D_idx,
326 const bool is_deleted_point3D);
327
328 const CorrespondenceGraph* correspondence_graph_;
329
330 EIGEN_STL_UMAP(camera_t, class Camera) cameras_;
331 EIGEN_STL_UMAP(image_t, class Image) images_;
332 EIGEN_STL_UMAP(point3D_t, class Point3D) points3D_;
333
334 std::unordered_map<image_pair_t, ImagePairStat> image_pair_stats_;
335
336 // { image_id, ... } where `images_.at(image_id).registered == true`.
337 std::vector<image_t> reg_image_ids_;
338
339 // Total number of added 3D points, used to generate unique identifiers.
340 point3D_t num_added_points3D_;
341 };
342
343 ////////////////////////////////////////////////////////////////////////////////
344 // Implementation
345 ////////////////////////////////////////////////////////////////////////////////
346
NumCameras()347 size_t Reconstruction::NumCameras() const { return cameras_.size(); }
348
NumImages()349 size_t Reconstruction::NumImages() const { return images_.size(); }
350
NumRegImages()351 size_t Reconstruction::NumRegImages() const { return reg_image_ids_.size(); }
352
NumPoints3D()353 size_t Reconstruction::NumPoints3D() const { return points3D_.size(); }
354
NumImagePairs()355 size_t Reconstruction::NumImagePairs() const {
356 return image_pair_stats_.size();
357 }
358
Camera(const camera_t camera_id)359 const class Camera& Reconstruction::Camera(const camera_t camera_id) const {
360 return cameras_.at(camera_id);
361 }
362
Image(const image_t image_id)363 const class Image& Reconstruction::Image(const image_t image_id) const {
364 return images_.at(image_id);
365 }
366
Point3D(const point3D_t point3D_id)367 const class Point3D& Reconstruction::Point3D(const point3D_t point3D_id) const {
368 return points3D_.at(point3D_id);
369 }
370
ImagePair(const image_pair_t pair_id)371 const Reconstruction::ImagePairStat& Reconstruction::ImagePair(
372 const image_pair_t pair_id) const {
373 return image_pair_stats_.at(pair_id);
374 }
375
ImagePair(const image_t image_id1,const image_t image_id2)376 const Reconstruction::ImagePairStat& Reconstruction::ImagePair(
377 const image_t image_id1, const image_t image_id2) const {
378 const auto pair_id = Database::ImagePairToPairId(image_id1, image_id2);
379 return image_pair_stats_.at(pair_id);
380 }
381
Camera(const camera_t camera_id)382 class Camera& Reconstruction::Camera(const camera_t camera_id) {
383 return cameras_.at(camera_id);
384 }
385
Image(const image_t image_id)386 class Image& Reconstruction::Image(const image_t image_id) {
387 return images_.at(image_id);
388 }
389
Point3D(const point3D_t point3D_id)390 class Point3D& Reconstruction::Point3D(const point3D_t point3D_id) {
391 return points3D_.at(point3D_id);
392 }
393
ImagePair(const image_pair_t pair_id)394 Reconstruction::ImagePairStat& Reconstruction::ImagePair(
395 const image_pair_t pair_id) {
396 return image_pair_stats_.at(pair_id);
397 }
398
ImagePair(const image_t image_id1,const image_t image_id2)399 Reconstruction::ImagePairStat& Reconstruction::ImagePair(
400 const image_t image_id1, const image_t image_id2) {
401 const auto pair_id = Database::ImagePairToPairId(image_id1, image_id2);
402 return image_pair_stats_.at(pair_id);
403 }
404
EIGEN_STL_UMAP(camera_t,Camera)405 const EIGEN_STL_UMAP(camera_t, Camera) & Reconstruction::Cameras() const {
406 return cameras_;
407 }
408
EIGEN_STL_UMAP(image_t,class Image)409 const EIGEN_STL_UMAP(image_t, class Image) & Reconstruction::Images() const {
410 return images_;
411 }
412
RegImageIds()413 const std::vector<image_t>& Reconstruction::RegImageIds() const {
414 return reg_image_ids_;
415 }
416
EIGEN_STL_UMAP(point3D_t,Point3D)417 const EIGEN_STL_UMAP(point3D_t, Point3D) & Reconstruction::Points3D() const {
418 return points3D_;
419 }
420
421 const std::unordered_map<image_pair_t, Reconstruction::ImagePairStat>&
ImagePairs()422 Reconstruction::ImagePairs() const {
423 return image_pair_stats_;
424 }
425
ExistsCamera(const camera_t camera_id)426 bool Reconstruction::ExistsCamera(const camera_t camera_id) const {
427 return cameras_.find(camera_id) != cameras_.end();
428 }
429
ExistsImage(const image_t image_id)430 bool Reconstruction::ExistsImage(const image_t image_id) const {
431 return images_.find(image_id) != images_.end();
432 }
433
ExistsPoint3D(const point3D_t point3D_id)434 bool Reconstruction::ExistsPoint3D(const point3D_t point3D_id) const {
435 return points3D_.find(point3D_id) != points3D_.end();
436 }
437
ExistsImagePair(const image_pair_t pair_id)438 bool Reconstruction::ExistsImagePair(const image_pair_t pair_id) const {
439 return image_pair_stats_.find(pair_id) != image_pair_stats_.end();
440 }
441
IsImageRegistered(const image_t image_id)442 bool Reconstruction::IsImageRegistered(const image_t image_id) const {
443 return Image(image_id).IsRegistered();
444 }
445
446 } // namespace colmap
447
448 #endif // COLMAP_SRC_BASE_RECONSTRUCTION_H_
449