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_FEATURE_MATCHING_H_ 33 #define COLMAP_SRC_FEATURE_MATCHING_H_ 34 35 #include <array> 36 #include <string> 37 #include <vector> 38 39 #include "base/database.h" 40 #include "feature/sift.h" 41 #include "util/alignment.h" 42 #include "util/cache.h" 43 #include "util/opengl_utils.h" 44 #include "util/threading.h" 45 #include "util/timer.h" 46 47 namespace colmap { 48 49 struct ExhaustiveMatchingOptions { 50 // Block size, i.e. number of images to simultaneously load into memory. 51 int block_size = 50; 52 53 bool Check() const; 54 }; 55 56 struct SequentialMatchingOptions { 57 // Number of overlapping image pairs. 58 int overlap = 10; 59 60 // Whether to match images against their quadratic neighbors. 61 bool quadratic_overlap = true; 62 63 // Whether to enable vocabulary tree based loop detection. 64 bool loop_detection = false; 65 66 // Loop detection is invoked every `loop_detection_period` images. 67 int loop_detection_period = 10; 68 69 // The number of images to retrieve in loop detection. This number should 70 // be significantly bigger than the sequential matching overlap. 71 int loop_detection_num_images = 50; 72 73 // Number of nearest neighbors to retrieve per query feature. 74 int loop_detection_num_nearest_neighbors = 1; 75 76 // Number of nearest-neighbor checks to use in retrieval. 77 int loop_detection_num_checks = 256; 78 79 // How many images to return after spatial verification. Set to 0 to turn off 80 // spatial verification. 81 int loop_detection_num_images_after_verification = 0; 82 83 // The maximum number of features to use for indexing an image. If an 84 // image has more features, only the largest-scale features will be indexed. 85 int loop_detection_max_num_features = -1; 86 87 // Path to the vocabulary tree. 88 std::string vocab_tree_path = ""; 89 90 bool Check() const; 91 }; 92 93 struct VocabTreeMatchingOptions { 94 // Number of images to retrieve for each query image. 95 int num_images = 100; 96 97 // Number of nearest neighbors to retrieve per query feature. 98 int num_nearest_neighbors = 5; 99 100 // Number of nearest-neighbor checks to use in retrieval. 101 int num_checks = 256; 102 103 // How many images to return after spatial verification. Set to 0 to turn off 104 // spatial verification. 105 int num_images_after_verification = 0; 106 107 // The maximum number of features to use for indexing an image. If an 108 // image has more features, only the largest-scale features will be indexed. 109 int max_num_features = -1; 110 111 // Path to the vocabulary tree. 112 std::string vocab_tree_path = ""; 113 114 // Optional path to file with specific image names to match. 115 std::string match_list_path = ""; 116 117 bool Check() const; 118 }; 119 120 struct SpatialMatchingOptions { 121 // Whether the location priors in the database are GPS coordinates in 122 // the form of longitude and latitude coordinates in degrees. 123 bool is_gps = true; 124 125 // Whether to ignore the Z-component of the location prior. 126 bool ignore_z = true; 127 128 // The maximum number of nearest neighbors to match. 129 int max_num_neighbors = 50; 130 131 // The maximum distance between the query and nearest neighbor. For GPS 132 // coordinates the unit is Euclidean distance in meters. 133 double max_distance = 100; 134 135 bool Check() const; 136 }; 137 138 struct TransitiveMatchingOptions { 139 // The maximum number of image pairs to process in one batch. 140 int batch_size = 1000; 141 142 // The number of transitive closure iterations. 143 int num_iterations = 3; 144 145 bool Check() const; 146 }; 147 148 struct ImagePairsMatchingOptions { 149 // Number of image pairs to match in one batch. 150 int block_size = 1225; 151 152 // Path to the file with the matches. 153 std::string match_list_path = ""; 154 155 bool Check() const; 156 }; 157 158 struct FeaturePairsMatchingOptions { 159 // Whether to geometrically verify the given matches. 160 bool verify_matches = true; 161 162 // Path to the file with the matches. 163 std::string match_list_path = ""; 164 165 bool Check() const; 166 }; 167 168 namespace internal { 169 170 struct FeatureMatcherData { 171 image_t image_id1 = kInvalidImageId; 172 image_t image_id2 = kInvalidImageId; 173 FeatureMatches matches; 174 TwoViewGeometry two_view_geometry; 175 }; 176 177 } // namespace internal 178 179 // Cache for feature matching to minimize database access during matching. 180 class FeatureMatcherCache { 181 public: 182 FeatureMatcherCache(const size_t cache_size, const Database* database); 183 184 void Setup(); 185 186 const Camera& GetCamera(const camera_t camera_id) const; 187 const Image& GetImage(const image_t image_id) const; 188 const FeatureKeypoints& GetKeypoints(const image_t image_id); 189 const FeatureDescriptors& GetDescriptors(const image_t image_id); 190 FeatureMatches GetMatches(const image_t image_id1, const image_t image_id2); 191 std::vector<image_t> GetImageIds() const; 192 193 bool ExistsMatches(const image_t image_id1, const image_t image_id2); 194 bool ExistsInlierMatches(const image_t image_id1, const image_t image_id2); 195 196 void WriteMatches(const image_t image_id1, const image_t image_id2, 197 const FeatureMatches& matches); 198 void WriteTwoViewGeometry(const image_t image_id1, const image_t image_id2, 199 const TwoViewGeometry& two_view_geometry); 200 201 void DeleteMatches(const image_t image_id1, const image_t image_id2); 202 void DeleteInlierMatches(const image_t image_id1, const image_t image_id2); 203 204 private: 205 const size_t cache_size_; 206 const Database* database_; 207 std::mutex database_mutex_; 208 EIGEN_STL_UMAP(camera_t, Camera) cameras_cache_; 209 EIGEN_STL_UMAP(image_t, Image) images_cache_; 210 std::unique_ptr<LRUCache<image_t, FeatureKeypoints>> keypoints_cache_; 211 std::unique_ptr<LRUCache<image_t, FeatureDescriptors>> descriptors_cache_; 212 }; 213 214 class FeatureMatcherThread : public Thread { 215 public: 216 FeatureMatcherThread(const SiftMatchingOptions& options, 217 FeatureMatcherCache* cache); 218 219 void SetMaxNumMatches(const int max_num_matches); 220 221 protected: 222 SiftMatchingOptions options_; 223 FeatureMatcherCache* cache_; 224 }; 225 226 class SiftCPUFeatureMatcher : public FeatureMatcherThread { 227 public: 228 typedef internal::FeatureMatcherData Input; 229 typedef internal::FeatureMatcherData Output; 230 231 SiftCPUFeatureMatcher(const SiftMatchingOptions& options, 232 FeatureMatcherCache* cache, 233 JobQueue<Input>* input_queue, 234 JobQueue<Output>* output_queue); 235 236 protected: 237 void Run() override; 238 239 JobQueue<Input>* input_queue_; 240 JobQueue<Output>* output_queue_; 241 }; 242 243 class SiftGPUFeatureMatcher : public FeatureMatcherThread { 244 public: 245 typedef internal::FeatureMatcherData Input; 246 typedef internal::FeatureMatcherData Output; 247 248 SiftGPUFeatureMatcher(const SiftMatchingOptions& options, 249 FeatureMatcherCache* cache, 250 JobQueue<Input>* input_queue, 251 JobQueue<Output>* output_queue); 252 253 protected: 254 void Run() override; 255 256 void GetDescriptorData(const int index, const image_t image_id, 257 const FeatureDescriptors** descriptors_ptr); 258 259 JobQueue<Input>* input_queue_; 260 JobQueue<Output>* output_queue_; 261 262 std::unique_ptr<OpenGLContextManager> opengl_context_; 263 264 // The previously uploaded images to the GPU. 265 std::array<image_t, 2> prev_uploaded_image_ids_; 266 std::array<FeatureDescriptors, 2> prev_uploaded_descriptors_; 267 }; 268 269 class GuidedSiftCPUFeatureMatcher : public FeatureMatcherThread { 270 public: 271 typedef internal::FeatureMatcherData Input; 272 typedef internal::FeatureMatcherData Output; 273 274 GuidedSiftCPUFeatureMatcher(const SiftMatchingOptions& options, 275 FeatureMatcherCache* cache, 276 JobQueue<Input>* input_queue, 277 JobQueue<Output>* output_queue); 278 279 private: 280 void Run() override; 281 282 JobQueue<Input>* input_queue_; 283 JobQueue<Output>* output_queue_; 284 }; 285 286 class GuidedSiftGPUFeatureMatcher : public FeatureMatcherThread { 287 public: 288 typedef internal::FeatureMatcherData Input; 289 typedef internal::FeatureMatcherData Output; 290 291 GuidedSiftGPUFeatureMatcher(const SiftMatchingOptions& options, 292 FeatureMatcherCache* cache, 293 JobQueue<Input>* input_queue, 294 JobQueue<Output>* output_queue); 295 296 private: 297 void Run() override; 298 299 void GetFeatureData(const int index, const image_t image_id, 300 const FeatureKeypoints** keypoints_ptr, 301 const FeatureDescriptors** descriptors_ptr); 302 303 JobQueue<Input>* input_queue_; 304 JobQueue<Output>* output_queue_; 305 306 std::unique_ptr<OpenGLContextManager> opengl_context_; 307 308 // The previously uploaded images to the GPU. 309 std::array<image_t, 2> prev_uploaded_image_ids_; 310 std::array<FeatureKeypoints, 2> prev_uploaded_keypoints_; 311 std::array<FeatureDescriptors, 2> prev_uploaded_descriptors_; 312 }; 313 314 class TwoViewGeometryVerifier : public Thread { 315 public: 316 typedef internal::FeatureMatcherData Input; 317 typedef internal::FeatureMatcherData Output; 318 319 TwoViewGeometryVerifier(const SiftMatchingOptions& options, 320 FeatureMatcherCache* cache, 321 JobQueue<Input>* input_queue, 322 JobQueue<Output>* output_queue); 323 324 protected: 325 void Run() override; 326 327 const SiftMatchingOptions options_; 328 TwoViewGeometry::Options two_view_geometry_options_; 329 FeatureMatcherCache* cache_; 330 JobQueue<Input>* input_queue_; 331 JobQueue<Output>* output_queue_; 332 }; 333 334 // Multi-threaded and multi-GPU SIFT feature matcher, which writes the computed 335 // results to the database and skips already matched image pairs. To improve 336 // performance of the matching by taking advantage of caching and database 337 // transactions, pass multiple images to the `Match` function. Note that the 338 // database should be in an active transaction while calling `Match`. 339 class SiftFeatureMatcher { 340 public: 341 SiftFeatureMatcher(const SiftMatchingOptions& options, Database* database, 342 FeatureMatcherCache* cache); 343 344 ~SiftFeatureMatcher(); 345 346 // Setup the matchers and return if successful. 347 bool Setup(); 348 349 // Match one batch of multiple image pairs. 350 void Match(const std::vector<std::pair<image_t, image_t>>& image_pairs); 351 352 private: 353 SiftMatchingOptions options_; 354 Database* database_; 355 FeatureMatcherCache* cache_; 356 357 bool is_setup_; 358 359 std::vector<std::unique_ptr<FeatureMatcherThread>> matchers_; 360 std::vector<std::unique_ptr<FeatureMatcherThread>> guided_matchers_; 361 std::vector<std::unique_ptr<Thread>> verifiers_; 362 std::unique_ptr<ThreadPool> thread_pool_; 363 364 JobQueue<internal::FeatureMatcherData> matcher_queue_; 365 JobQueue<internal::FeatureMatcherData> verifier_queue_; 366 JobQueue<internal::FeatureMatcherData> guided_matcher_queue_; 367 JobQueue<internal::FeatureMatcherData> output_queue_; 368 }; 369 370 // Exhaustively match images by processing each block in the exhaustive match 371 // matrix in one batch: 372 // 373 // +----+----+-----------------> images[i] 374 // |#000|0000| 375 // |1#00|1000| <- Above the main diagonal, the block diagonal is not matched 376 // |11#0|1100| ^ 377 // |111#|1110| | 378 // +----+----+ | 379 // |1000|#000|\ | 380 // |1100|1#00| \ One block | 381 // |1110|11#0| / of image pairs | 382 // |1111|111#|/ | 383 // +----+----+ | 384 // | ^ | 385 // | | | 386 // | Below the main diagonal, the block diagonal is matched <--------------+ 387 // | 388 // v 389 // images[i] 390 // 391 // Pairs will only be matched if 1, to avoid duplicate pairs. Pairs with # 392 // are on the main diagonal and denote pairs of the same image. 393 class ExhaustiveFeatureMatcher : public Thread { 394 public: 395 ExhaustiveFeatureMatcher(const ExhaustiveMatchingOptions& options, 396 const SiftMatchingOptions& match_options, 397 const std::string& database_path); 398 399 private: 400 void Run() override; 401 402 const ExhaustiveMatchingOptions options_; 403 const SiftMatchingOptions match_options_; 404 Database database_; 405 FeatureMatcherCache cache_; 406 SiftFeatureMatcher matcher_; 407 }; 408 409 // Sequentially match images within neighborhood: 410 // 411 // +-------------------------------+-----------------------> images[i] 412 // ^ | ^ 413 // | Current image[i] | 414 // | | | 415 // +----------+-----------+ 416 // | 417 // Match image_i against 418 // 419 // image_[i - o, i + o] with o = [1 .. overlap] 420 // image_[i - 2^o, i + 2^o] (for quadratic overlap) 421 // 422 // Sequential order is determined based on the image names in ascending order. 423 // 424 // Invoke loop detection if `(i mod loop_detection_period) == 0`, retrieve 425 // most similar `loop_detection_num_images` images from vocabulary tree, 426 // and perform matching and verification. 427 class SequentialFeatureMatcher : public Thread { 428 public: 429 SequentialFeatureMatcher(const SequentialMatchingOptions& options, 430 const SiftMatchingOptions& match_options, 431 const std::string& database_path); 432 433 private: 434 void Run() override; 435 436 std::vector<image_t> GetOrderedImageIds() const; 437 void RunSequentialMatching(const std::vector<image_t>& image_ids); 438 void RunLoopDetection(const std::vector<image_t>& image_ids); 439 440 const SequentialMatchingOptions options_; 441 const SiftMatchingOptions match_options_; 442 Database database_; 443 FeatureMatcherCache cache_; 444 SiftFeatureMatcher matcher_; 445 }; 446 447 // Match each image against its nearest neighbors using a vocabulary tree. 448 class VocabTreeFeatureMatcher : public Thread { 449 public: 450 VocabTreeFeatureMatcher(const VocabTreeMatchingOptions& options, 451 const SiftMatchingOptions& match_options, 452 const std::string& database_path); 453 454 private: 455 void Run() override; 456 457 const VocabTreeMatchingOptions options_; 458 const SiftMatchingOptions match_options_; 459 Database database_; 460 FeatureMatcherCache cache_; 461 SiftFeatureMatcher matcher_; 462 }; 463 464 // Match images against spatial nearest neighbors using prior location 465 // information, e.g. provided manually or extracted from EXIF. 466 class SpatialFeatureMatcher : public Thread { 467 public: 468 SpatialFeatureMatcher(const SpatialMatchingOptions& options, 469 const SiftMatchingOptions& match_options, 470 const std::string& database_path); 471 472 private: 473 void Run() override; 474 475 const SpatialMatchingOptions options_; 476 const SiftMatchingOptions match_options_; 477 Database database_; 478 FeatureMatcherCache cache_; 479 SiftFeatureMatcher matcher_; 480 }; 481 482 // Match transitive image pairs in a database with existing feature matches. 483 // This matcher transitively closes loops. For example, if image pairs A-B and 484 // B-C match but A-C has not been matched, then this matcher attempts to match 485 // A-C. This procedure is performed for multiple iterations. 486 class TransitiveFeatureMatcher : public Thread { 487 public: 488 TransitiveFeatureMatcher(const TransitiveMatchingOptions& options, 489 const SiftMatchingOptions& match_options, 490 const std::string& database_path); 491 492 private: 493 void Run() override; 494 495 const TransitiveMatchingOptions options_; 496 const SiftMatchingOptions match_options_; 497 Database database_; 498 FeatureMatcherCache cache_; 499 SiftFeatureMatcher matcher_; 500 }; 501 502 // Match images manually specified in a list of image pairs. 503 // 504 // Read matches file with the following format: 505 // 506 // image_name1 image_name2 507 // image_name1 image_name3 508 // image_name2 image_name3 509 // ... 510 // 511 class ImagePairsFeatureMatcher : public Thread { 512 public: 513 ImagePairsFeatureMatcher(const ImagePairsMatchingOptions& options, 514 const SiftMatchingOptions& match_options, 515 const std::string& database_path); 516 517 private: 518 void Run() override; 519 520 const ImagePairsMatchingOptions options_; 521 const SiftMatchingOptions match_options_; 522 Database database_; 523 FeatureMatcherCache cache_; 524 SiftFeatureMatcher matcher_; 525 }; 526 527 // Import feature matches from a text file. 528 // 529 // Read matches file with the following format: 530 // 531 // image_name1 image_name2 532 // 0 1 533 // 1 2 534 // 2 3 535 // <empty line> 536 // image_name1 image_name3 537 // 0 1 538 // 1 2 539 // 2 3 540 // ... 541 // 542 class FeaturePairsFeatureMatcher : public Thread { 543 public: 544 FeaturePairsFeatureMatcher(const FeaturePairsMatchingOptions& options, 545 const SiftMatchingOptions& match_options, 546 const std::string& database_path); 547 548 private: 549 const static size_t kCacheSize = 100; 550 551 void Run() override; 552 553 const FeaturePairsMatchingOptions options_; 554 const SiftMatchingOptions match_options_; 555 Database database_; 556 FeatureMatcherCache cache_; 557 }; 558 559 } // namespace colmap 560 561 #endif // COLMAP_SRC_FEATURE_MATCHING_H_ 562