1// Ceres Solver - A fast non-linear least squares minimizer
2// Copyright 2010, 2011, 2012 Google Inc. All rights reserved.
3// http://code.google.com/p/ceres-solver/
4//
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions are met:
7//
8// * Redistributions of source code must retain the above copyright notice,
9//   this list of conditions and the following disclaimer.
10// * Redistributions in binary form must reproduce the above copyright notice,
11//   this list of conditions and the following disclaimer in the documentation
12//   and/or other materials provided with the distribution.
13// * Neither the name of Google Inc. nor the names of its contributors may be
14//   used to endorse or promote products derived from this software without
15//   specific prior written permission.
16//
17// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27// POSSIBILITY OF SUCH DAMAGE.
28//
29// Author: David Gallup (dgallup@google.com)
30//         Sameer Agarwal (sameeragarwal@google.com)
31
32#ifndef CERES_NO_SUITESPARSE
33
34#include "ceres/canonical_views_clustering.h"
35
36#include "ceres/collections_port.h"
37#include "ceres/graph.h"
38#include "ceres/internal/macros.h"
39#include "ceres/map_util.h"
40#include "glog/logging.h"
41
42namespace ceres {
43namespace internal {
44
45typedef HashMap<int, int> IntMap;
46typedef HashSet<int> IntSet;
47
48class CanonicalViewsClustering {
49 public:
50  CanonicalViewsClustering() {}
51
52  // Compute the canonical views clustering of the vertices of the
53  // graph. centers will contain the vertices that are the identified
54  // as the canonical views/cluster centers, and membership is a map
55  // from vertices to cluster_ids. The i^th cluster center corresponds
56  // to the i^th cluster. It is possible depending on the
57  // configuration of the clustering algorithm that some of the
58  // vertices may not be assigned to any cluster. In this case they
59  // are assigned to a cluster with id = kInvalidClusterId.
60  void ComputeClustering(const Graph<int>& graph,
61                         const CanonicalViewsClusteringOptions& options,
62                         vector<int>* centers,
63                         IntMap* membership);
64
65 private:
66  void FindValidViews(IntSet* valid_views) const;
67  double ComputeClusteringQualityDifference(const int candidate,
68                                            const vector<int>& centers) const;
69  void UpdateCanonicalViewAssignments(const int canonical_view);
70  void ComputeClusterMembership(const vector<int>& centers,
71                                IntMap* membership) const;
72
73  CanonicalViewsClusteringOptions options_;
74  const Graph<int>* graph_;
75  // Maps a view to its representative canonical view (its cluster
76  // center).
77  IntMap view_to_canonical_view_;
78  // Maps a view to its similarity to its current cluster center.
79  HashMap<int, double> view_to_canonical_view_similarity_;
80  CERES_DISALLOW_COPY_AND_ASSIGN(CanonicalViewsClustering);
81};
82
83void ComputeCanonicalViewsClustering(
84    const Graph<int>& graph,
85    const CanonicalViewsClusteringOptions& options,
86    vector<int>* centers,
87    IntMap* membership) {
88  time_t start_time = time(NULL);
89  CanonicalViewsClustering cv;
90  cv.ComputeClustering(graph, options, centers, membership);
91  VLOG(2) << "Canonical views clustering time (secs): "
92          << time(NULL) - start_time;
93}
94
95// Implementation of CanonicalViewsClustering
96void CanonicalViewsClustering::ComputeClustering(
97    const Graph<int>& graph,
98    const CanonicalViewsClusteringOptions& options,
99    vector<int>* centers,
100    IntMap* membership) {
101  options_ = options;
102  CHECK_NOTNULL(centers)->clear();
103  CHECK_NOTNULL(membership)->clear();
104  graph_ = &graph;
105
106  IntSet valid_views;
107  FindValidViews(&valid_views);
108  while (valid_views.size() > 0) {
109    // Find the next best canonical view.
110    double best_difference = -std::numeric_limits<double>::max();
111    int best_view = 0;
112
113    // TODO(sameeragarwal): Make this loop multi-threaded.
114    for (IntSet::const_iterator view = valid_views.begin();
115         view != valid_views.end();
116         ++view) {
117      const double difference =
118          ComputeClusteringQualityDifference(*view, *centers);
119      if (difference > best_difference) {
120        best_difference = difference;
121        best_view = *view;
122      }
123    }
124
125    CHECK_GT(best_difference, -std::numeric_limits<double>::max());
126
127    // Add canonical view if quality improves, or if minimum is not
128    // yet met, otherwise break.
129    if ((best_difference <= 0) &&
130        (centers->size() >= options_.min_views)) {
131      break;
132    }
133
134    centers->push_back(best_view);
135    valid_views.erase(best_view);
136    UpdateCanonicalViewAssignments(best_view);
137  }
138
139  ComputeClusterMembership(*centers, membership);
140}
141
142// Return the set of vertices of the graph which have valid vertex
143// weights.
144void CanonicalViewsClustering::FindValidViews(
145    IntSet* valid_views) const {
146  const IntSet& views = graph_->vertices();
147  for (IntSet::const_iterator view = views.begin();
148       view != views.end();
149       ++view) {
150    if (graph_->VertexWeight(*view) != Graph<int>::InvalidWeight()) {
151      valid_views->insert(*view);
152    }
153  }
154}
155
156// Computes the difference in the quality score if 'candidate' were
157// added to the set of canonical views.
158double CanonicalViewsClustering::ComputeClusteringQualityDifference(
159    const int candidate,
160    const vector<int>& centers) const {
161  // View score.
162  double difference =
163      options_.view_score_weight * graph_->VertexWeight(candidate);
164
165  // Compute how much the quality score changes if the candidate view
166  // was added to the list of canonical views and its nearest
167  // neighbors became members of its cluster.
168  const IntSet& neighbors = graph_->Neighbors(candidate);
169  for (IntSet::const_iterator neighbor = neighbors.begin();
170       neighbor != neighbors.end();
171       ++neighbor) {
172    const double old_similarity =
173        FindWithDefault(view_to_canonical_view_similarity_, *neighbor, 0.0);
174    const double new_similarity = graph_->EdgeWeight(*neighbor, candidate);
175    if (new_similarity > old_similarity) {
176      difference += new_similarity - old_similarity;
177    }
178  }
179
180  // Number of views penalty.
181  difference -= options_.size_penalty_weight;
182
183  // Orthogonality.
184  for (int i = 0; i < centers.size(); ++i) {
185    difference -= options_.similarity_penalty_weight *
186        graph_->EdgeWeight(centers[i], candidate);
187  }
188
189  return difference;
190}
191
192// Reassign views if they're more similar to the new canonical view.
193void CanonicalViewsClustering::UpdateCanonicalViewAssignments(
194    const int canonical_view) {
195  const IntSet& neighbors = graph_->Neighbors(canonical_view);
196  for (IntSet::const_iterator neighbor = neighbors.begin();
197       neighbor != neighbors.end();
198       ++neighbor) {
199    const double old_similarity =
200        FindWithDefault(view_to_canonical_view_similarity_, *neighbor, 0.0);
201    const double new_similarity =
202        graph_->EdgeWeight(*neighbor, canonical_view);
203    if (new_similarity > old_similarity) {
204      view_to_canonical_view_[*neighbor] = canonical_view;
205      view_to_canonical_view_similarity_[*neighbor] = new_similarity;
206    }
207  }
208}
209
210// Assign a cluster id to each view.
211void CanonicalViewsClustering::ComputeClusterMembership(
212    const vector<int>& centers,
213    IntMap* membership) const {
214  CHECK_NOTNULL(membership)->clear();
215
216  // The i^th cluster has cluster id i.
217  IntMap center_to_cluster_id;
218  for (int i = 0; i < centers.size(); ++i) {
219    center_to_cluster_id[centers[i]] = i;
220  }
221
222  static const int kInvalidClusterId = -1;
223
224  const IntSet& views = graph_->vertices();
225  for (IntSet::const_iterator view = views.begin();
226       view != views.end();
227       ++view) {
228    IntMap::const_iterator it =
229        view_to_canonical_view_.find(*view);
230    int cluster_id = kInvalidClusterId;
231    if (it != view_to_canonical_view_.end()) {
232      cluster_id = FindOrDie(center_to_cluster_id, it->second);
233    }
234
235    InsertOrDie(membership, *view, cluster_id);
236  }
237}
238
239}  // namespace internal
240}  // namespace ceres
241
242#endif  // CERES_NO_SUITESPARSE
243