ACloudViewer  3.9.4
A Modern Library for 3D Data Processing
scene_clustering_test.cc
Go to the documentation of this file.
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 #define TEST_NAME "base/scene_clustering"
33 #include "util/testing.h"
34 
35 #include <set>
36 
37 #include "base/database.h"
38 #include "base/scene_clustering.h"
39 
40 using namespace colmap;
41 
42 BOOST_AUTO_TEST_CASE(TestEmpty) {
43  const std::vector<std::pair<image_t, image_t>> image_pairs;
44  const std::vector<int> num_inliers;
45  SceneClustering::Options options;
46  options.branching = 2;
47  options.image_overlap = 0;
48  options.leaf_max_num_images = 2;
49  SceneClustering scene_clustering(options);
50  BOOST_CHECK(scene_clustering.GetRootCluster() == nullptr);
51  scene_clustering.Partition(image_pairs, num_inliers);
52  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids.size(), 0);
53  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->child_clusters.size(),
54  0);
55  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters().size(), 1);
56 }
57 
58 BOOST_AUTO_TEST_CASE(TestOneLevel) {
59  const std::vector<std::pair<image_t, image_t>> image_pairs = {{0, 1}};
60  const std::vector<int> num_inliers = {10};
61  SceneClustering::Options options;
62  options.branching = 2;
63  options.image_overlap = 0;
64  options.leaf_max_num_images = 2;
65  SceneClustering scene_clustering(options);
66  BOOST_CHECK(scene_clustering.GetRootCluster() == nullptr);
67  scene_clustering.Partition(image_pairs, num_inliers);
68  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids.size(), 2);
69  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[0], 0);
70  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[1], 1);
71  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->child_clusters.size(),
72  0);
73  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters().size(), 1);
74  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster(),
75  scene_clustering.GetLeafClusters()[0]);
76 }
77 
78 BOOST_AUTO_TEST_CASE(TestTwoLevels) {
79  const std::vector<std::pair<image_t, image_t>> image_pairs = {{0, 1}};
80  const std::vector<int> num_inliers = {10};
81  SceneClustering::Options options;
82  options.branching = 2;
83  options.image_overlap = 0;
84  options.leaf_max_num_images = 1;
85  SceneClustering scene_clustering(options);
86  BOOST_CHECK(scene_clustering.GetRootCluster() == nullptr);
87  scene_clustering.Partition(image_pairs, num_inliers);
88  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids.size(), 2);
89  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[0], 0);
90  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[1], 1);
91  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->child_clusters.size(),
92  2);
93  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters().size(), 2);
94  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[0]->image_ids[0], 1);
95  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[1]->image_ids[0], 0);
96 }
97 
98 BOOST_AUTO_TEST_CASE(TestThreeLevels) {
99  const std::vector<std::pair<image_t, image_t>> image_pairs = {{0, 1}, {0, 2}};
100  const std::vector<int> num_inliers = {10, 11};
101  SceneClustering::Options options;
102  options.branching = 2;
103  options.image_overlap = 0;
104  options.leaf_max_num_images = 1;
105  SceneClustering scene_clustering(options);
106  BOOST_CHECK(scene_clustering.GetRootCluster() == nullptr);
107  scene_clustering.Partition(image_pairs, num_inliers);
108  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids.size(), 3);
109  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[0], 0);
110  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[1], 1);
111  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[2], 2);
112  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters().size(), 3);
113  std::set<int> image_ids;
114  image_ids.insert(scene_clustering.GetLeafClusters()[0]->image_ids[0]);
115  image_ids.insert(scene_clustering.GetLeafClusters()[1]->image_ids[0]);
116  image_ids.insert(scene_clustering.GetLeafClusters()[2]->image_ids[0]);
117  BOOST_CHECK_EQUAL(image_ids.size(), 3);
118  BOOST_CHECK(image_ids.count(0));
119  BOOST_CHECK(image_ids.count(1));
120  BOOST_CHECK(image_ids.count(2));
121 }
122 
123 BOOST_AUTO_TEST_CASE(TestThreeLevelsMultipleImages) {
124  const std::vector<std::pair<image_t, image_t>> image_pairs = {{0, 1}, {0, 2}};
125  const std::vector<int> num_inliers = {10, 11};
126  SceneClustering::Options options;
127  options.branching = 2;
128  options.image_overlap = 0;
129  options.leaf_max_num_images = 2;
130  SceneClustering scene_clustering(options);
131  BOOST_CHECK(scene_clustering.GetRootCluster() == nullptr);
132  scene_clustering.Partition(image_pairs, num_inliers);
133  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids.size(), 3);
134  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[0], 0);
135  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[1], 1);
136  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[2], 2);
137  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters().size(), 2);
138  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[0]->image_ids.size(), 1);
139  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[1]->image_ids.size(), 2);
140  std::set<int> image_ids;
141  image_ids.insert(scene_clustering.GetLeafClusters()[0]->image_ids[0]);
142  image_ids.insert(scene_clustering.GetLeafClusters()[1]->image_ids[0]);
143  image_ids.insert(scene_clustering.GetLeafClusters()[1]->image_ids[1]);
144  BOOST_CHECK_EQUAL(image_ids.size(), 3);
145  BOOST_CHECK(image_ids.count(0));
146  BOOST_CHECK(image_ids.count(1));
147  BOOST_CHECK(image_ids.count(2));
148 }
149 
150 BOOST_AUTO_TEST_CASE(TestOneOverlap) {
151  const std::vector<std::pair<image_t, image_t>> image_pairs = {
152  {0, 1}, {0, 2}, {1, 2}, {0, 3}, {1, 3}, {2, 3}};
153  const std::vector<int> num_inliers = {10, 11, 12, 13, 14, 15};
154  SceneClustering::Options options;
155  options.branching = 2;
156  options.image_overlap = 1;
157  options.leaf_max_num_images = 3;
158  SceneClustering scene_clustering(options);
159  BOOST_CHECK(scene_clustering.GetRootCluster() == nullptr);
160  scene_clustering.Partition(image_pairs, num_inliers);
161  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids.size(), 4);
162  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[0], 0);
163  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[1], 1);
164  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[2], 2);
165  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[3], 3);
166  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters().size(), 2);
167  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[0]->image_ids.size(), 3);
168  const std::set<image_t> image_ids0(
169  scene_clustering.GetLeafClusters()[0]->image_ids.begin(),
170  scene_clustering.GetLeafClusters()[0]->image_ids.end());
171  BOOST_CHECK(image_ids0.count(0));
172  BOOST_CHECK(image_ids0.count(1) || image_ids0.count(2));
173  BOOST_CHECK(image_ids0.count(3));
174  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[1]->image_ids.size(), 3);
175  const std::set<image_t> image_ids1(
176  scene_clustering.GetLeafClusters()[1]->image_ids.begin(),
177  scene_clustering.GetLeafClusters()[1]->image_ids.end());
178  BOOST_CHECK(image_ids1.count(1));
179  BOOST_CHECK(image_ids0.count(0) || image_ids0.count(2));
180  BOOST_CHECK(image_ids1.count(3));
181 }
182 
183 BOOST_AUTO_TEST_CASE(TestTwoOverlap) {
184  const std::vector<std::pair<image_t, image_t>> image_pairs = {
185  {0, 1}, {0, 2}, {1, 2}, {0, 3}, {1, 3}, {2, 3}};
186  const std::vector<int> num_inliers = {10, 11, 12, 13, 14, 15};
187  SceneClustering::Options options;
188  options.branching = 2;
189  options.image_overlap = 2;
190  options.leaf_max_num_images = 2;
191  SceneClustering scene_clustering(options);
192  BOOST_CHECK(scene_clustering.GetRootCluster() == nullptr);
193  scene_clustering.Partition(image_pairs, num_inliers);
194  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids.size(), 4);
195  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[0], 0);
196  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[1], 1);
197  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[2], 2);
198  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[3], 3);
199  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters().size(), 2);
200  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[0]->image_ids.size(), 4);
201  const std::set<image_t> image_ids0(
202  scene_clustering.GetLeafClusters()[0]->image_ids.begin(),
203  scene_clustering.GetLeafClusters()[0]->image_ids.end());
204  BOOST_CHECK(image_ids0.count(0));
205  BOOST_CHECK(image_ids0.count(1));
206  BOOST_CHECK(image_ids0.count(2));
207  BOOST_CHECK(image_ids0.count(3));
208  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[1]->image_ids.size(), 4);
209  const std::set<image_t> image_ids1(
210  scene_clustering.GetLeafClusters()[1]->image_ids.begin(),
211  scene_clustering.GetLeafClusters()[1]->image_ids.end());
212  BOOST_CHECK(image_ids1.count(0));
213  BOOST_CHECK(image_ids1.count(1));
214  BOOST_CHECK(image_ids1.count(2));
215  BOOST_CHECK(image_ids1.count(3));
216 }
217 
218 BOOST_AUTO_TEST_CASE(TestThreeFlatClusters) {
219  const std::vector<std::pair<image_t, image_t>> image_pairs = {
220  {0, 1}, {2, 3}, {4, 5}, {1, 2}, {3, 4}, {5, 0}, {0, 3}, {2, 5}, {4, 1}};
221  const std::vector<int> num_inliers = {100, 100, 100, 10, 10, 10, 1, 1, 1};
222  SceneClustering::Options options;
223  options.branching = 3;
224  options.image_overlap = 0;
225  options.branching = 3;
226  options.is_hierarchical = false;
227  SceneClustering scene_clustering(options);
228  BOOST_CHECK(scene_clustering.GetRootCluster() == nullptr);
229  scene_clustering.Partition(image_pairs, num_inliers);
230  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids.size(), 6);
231  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[0], 0);
232  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[1], 1);
233  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[2], 2);
234  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[3], 3);
235  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[4], 4);
236  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[5], 5);
237  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters().size(), 3);
238  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[0]->image_ids.size(), 2);
239  const std::set<image_t> image_ids0(
240  scene_clustering.GetLeafClusters()[0]->image_ids.begin(),
241  scene_clustering.GetLeafClusters()[0]->image_ids.end());
242  BOOST_CHECK(image_ids0.count(0));
243  BOOST_CHECK(image_ids0.count(1));
244  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[1]->image_ids.size(), 2);
245  const std::set<image_t> image_ids1(
246  scene_clustering.GetLeafClusters()[1]->image_ids.begin(),
247  scene_clustering.GetLeafClusters()[1]->image_ids.end());
248  BOOST_CHECK(image_ids1.count(2));
249  BOOST_CHECK(image_ids1.count(3));
250  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[2]->image_ids.size(), 2);
251  const std::set<image_t> image_ids2(
252  scene_clustering.GetLeafClusters()[2]->image_ids.begin(),
253  scene_clustering.GetLeafClusters()[2]->image_ids.end());
254  BOOST_CHECK(image_ids2.count(4));
255  BOOST_CHECK(image_ids2.count(5));
256 }
257 
258 BOOST_AUTO_TEST_CASE(TestThreeFlatClustersTwoOverlap) {
259  const std::vector<std::pair<image_t, image_t>> image_pairs = {
260  {0, 1}, {2, 3}, {4, 5}, {1, 2}, {3, 4}, {5, 0}, {0, 3}, {2, 5}, {4, 1}};
261  const std::vector<int> num_inliers = {100, 100, 100, 10, 10, 10, 1, 1, 1};
262  SceneClustering::Options options;
263  options.branching = 3;
264  options.image_overlap = 2;
265  options.branching = 3;
266  options.is_hierarchical = false;
267  SceneClustering scene_clustering(options);
268  BOOST_CHECK(scene_clustering.GetRootCluster() == nullptr);
269  scene_clustering.Partition(image_pairs, num_inliers);
270  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids.size(), 6);
271  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[0], 0);
272  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[1], 1);
273  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[2], 2);
274  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[3], 3);
275  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[4], 4);
276  BOOST_CHECK_EQUAL(scene_clustering.GetRootCluster()->image_ids[5], 5);
277  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters().size(), 3);
278  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[0]->image_ids.size(), 4);
279  const std::set<image_t> image_ids0(
280  scene_clustering.GetLeafClusters()[0]->image_ids.begin(),
281  scene_clustering.GetLeafClusters()[0]->image_ids.end());
282  BOOST_CHECK(image_ids0.count(0));
283  BOOST_CHECK(image_ids0.count(1));
284  BOOST_CHECK(image_ids0.count(2));
285  BOOST_CHECK(image_ids0.count(5));
286  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[1]->image_ids.size(), 4);
287  const std::set<image_t> image_ids1(
288  scene_clustering.GetLeafClusters()[1]->image_ids.begin(),
289  scene_clustering.GetLeafClusters()[1]->image_ids.end());
290  BOOST_CHECK(image_ids1.count(1));
291  BOOST_CHECK(image_ids1.count(2));
292  BOOST_CHECK(image_ids1.count(3));
293  BOOST_CHECK(image_ids1.count(4));
294  BOOST_CHECK_EQUAL(scene_clustering.GetLeafClusters()[2]->image_ids.size(), 4);
295  const std::set<image_t> image_ids2(
296  scene_clustering.GetLeafClusters()[2]->image_ids.begin(),
297  scene_clustering.GetLeafClusters()[2]->image_ids.end());
298  BOOST_CHECK(image_ids2.count(0));
299  BOOST_CHECK(image_ids2.count(3));
300  BOOST_CHECK(image_ids2.count(4));
301  BOOST_CHECK(image_ids2.count(5));
302 }
colmap::SceneClustering::GetRootCluster
const Cluster * GetRootCluster() const
Definition: scene_clustering.cc:250
colmap::SceneClustering::Partition
void Partition(const std::vector< std::pair< image_t, image_t >> &image_pairs, const std::vector< int > &num_inliers)
Definition: scene_clustering.cc:51
colmap::SceneClustering::GetLeafClusters
std::vector< const Cluster * > GetLeafClusters() const
Definition: scene_clustering.cc:254
scene_clustering.h
BOOST_AUTO_TEST_CASE
BOOST_AUTO_TEST_CASE(TestEmpty)
Definition: scene_clustering_test.cc:42
colmap::SceneClustering::Cluster::image_ids
std::vector< image_t > image_ids
Definition: scene_clustering.h:46
colmap::SceneClustering::Cluster::child_clusters
std::vector< Cluster > child_clusters
Definition: scene_clustering.h:47