// Ceres Solver - A fast non-linear least squares minimizer
// Copyright 2010, 2011, 2012 Google Inc. All rights reserved.
// http://code.google.com/p/ceres-solver/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
// * Neither the name of Google Inc. nor the names of its contributors may be
// used to endorse or promote products derived from this software without
// specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
//
// Author: David Gallup (dgallup@google.com)
// Sameer Agarwal (sameeragarwal@google.com)
#include "ceres/canonical_views_clustering.h"
#include "ceres/collections_port.h"
#include "ceres/graph.h"
#include "ceres/internal/macros.h"
#include "ceres/map_util.h"
#include "glog/logging.h"
namespace ceres {
namespace internal {
typedef HashMap<int, int> IntMap;
typedef HashSet<int> IntSet;
class CanonicalViewsClustering {
public:
CanonicalViewsClustering() {}
// Compute the canonical views clustering of the vertices of the
// graph. centers will contain the vertices that are the identified
// as the canonical views/cluster centers, and membership is a map
// from vertices to cluster_ids. The i^th cluster center corresponds
// to the i^th cluster. It is possible depending on the
// configuration of the clustering algorithm that some of the
// vertices may not be assigned to any cluster. In this case they
// are assigned to a cluster with id = kInvalidClusterId.
void ComputeClustering(const Graph<int>& graph,
const CanonicalViewsClusteringOptions& options,
vector<int>* centers,
IntMap* membership);
private:
void FindValidViews(IntSet* valid_views) const;
double ComputeClusteringQualityDifference(const int candidate,
const vector<int>& centers) const;
void UpdateCanonicalViewAssignments(const int canonical_view);
void ComputeClusterMembership(const vector<int>& centers,
IntMap* membership) const;
CanonicalViewsClusteringOptions options_;
const Graph<int>* graph_;
// Maps a view to its representative canonical view (its cluster
// center).
IntMap view_to_canonical_view_;
// Maps a view to its similarity to its current cluster center.
HashMap<int, double> view_to_canonical_view_similarity_;
CERES_DISALLOW_COPY_AND_ASSIGN(CanonicalViewsClustering);
};
void ComputeCanonicalViewsClustering(
const Graph<int>& graph,
const CanonicalViewsClusteringOptions& options,
vector<int>* centers,
IntMap* membership) {
time_t start_time = time(NULL);
CanonicalViewsClustering cv;
cv.ComputeClustering(graph, options, centers, membership);
VLOG(2) << "Canonical views clustering time (secs): "
<< time(NULL) - start_time;
}
// Implementation of CanonicalViewsClustering
void CanonicalViewsClustering::ComputeClustering(
const Graph<int>& graph,
const CanonicalViewsClusteringOptions& options,
vector<int>* centers,
IntMap* membership) {
options_ = options;
CHECK_NOTNULL(centers)->clear();
CHECK_NOTNULL(membership)->clear();
graph_ = &graph;
IntSet valid_views;
FindValidViews(&valid_views);
while (valid_views.size() > 0) {
// Find the next best canonical view.
double best_difference = -std::numeric_limits<double>::max();
int best_view = 0;
// TODO(sameeragarwal): Make this loop multi-threaded.
for (IntSet::const_iterator view = valid_views.begin();
view != valid_views.end();
++view) {
const double difference =
ComputeClusteringQualityDifference(*view, *centers);
if (difference > best_difference) {
best_difference = difference;
best_view = *view;
}
}
CHECK_GT(best_difference, -std::numeric_limits<double>::max());
// Add canonical view if quality improves, or if minimum is not
// yet met, otherwise break.
if ((best_difference <= 0) &&
(centers->size() >= options_.min_views)) {
break;
}
centers->push_back(best_view);
valid_views.erase(best_view);
UpdateCanonicalViewAssignments(best_view);
}
ComputeClusterMembership(*centers, membership);
}
// Return the set of vertices of the graph which have valid vertex
// weights.
void CanonicalViewsClustering::FindValidViews(
IntSet* valid_views) const {
const IntSet& views = graph_->vertices();
for (IntSet::const_iterator view = views.begin();
view != views.end();
++view) {
if (graph_->VertexWeight(*view) != Graph<int>::InvalidWeight()) {
valid_views->insert(*view);
}
}
}
// Computes the difference in the quality score if 'candidate' were
// added to the set of canonical views.
double CanonicalViewsClustering::ComputeClusteringQualityDifference(
const int candidate,
const vector<int>& centers) const {
// View score.
double difference =
options_.view_score_weight * graph_->VertexWeight(candidate);
// Compute how much the quality score changes if the candidate view
// was added to the list of canonical views and its nearest
// neighbors became members of its cluster.
const IntSet& neighbors = graph_->Neighbors(candidate);
for (IntSet::const_iterator neighbor = neighbors.begin();
neighbor != neighbors.end();
++neighbor) {
const double old_similarity =
FindWithDefault(view_to_canonical_view_similarity_, *neighbor, 0.0);
const double new_similarity = graph_->EdgeWeight(*neighbor, candidate);
if (new_similarity > old_similarity) {
difference += new_similarity - old_similarity;
}
}
// Number of views penalty.
difference -= options_.size_penalty_weight;
// Orthogonality.
for (int i = 0; i < centers.size(); ++i) {
difference -= options_.similarity_penalty_weight *
graph_->EdgeWeight(centers[i], candidate);
}
return difference;
}
// Reassign views if they're more similar to the new canonical view.
void CanonicalViewsClustering::UpdateCanonicalViewAssignments(
const int canonical_view) {
const IntSet& neighbors = graph_->Neighbors(canonical_view);
for (IntSet::const_iterator neighbor = neighbors.begin();
neighbor != neighbors.end();
++neighbor) {
const double old_similarity =
FindWithDefault(view_to_canonical_view_similarity_, *neighbor, 0.0);
const double new_similarity =
graph_->EdgeWeight(*neighbor, canonical_view);
if (new_similarity > old_similarity) {
view_to_canonical_view_[*neighbor] = canonical_view;
view_to_canonical_view_similarity_[*neighbor] = new_similarity;
}
}
}
// Assign a cluster id to each view.
void CanonicalViewsClustering::ComputeClusterMembership(
const vector<int>& centers,
IntMap* membership) const {
CHECK_NOTNULL(membership)->clear();
// The i^th cluster has cluster id i.
IntMap center_to_cluster_id;
for (int i = 0; i < centers.size(); ++i) {
center_to_cluster_id[centers[i]] = i;
}
static const int kInvalidClusterId = -1;
const IntSet& views = graph_->vertices();
for (IntSet::const_iterator view = views.begin();
view != views.end();
++view) {
IntMap::const_iterator it =
view_to_canonical_view_.find(*view);
int cluster_id = kInvalidClusterId;
if (it != view_to_canonical_view_.end()) {
cluster_id = FindOrDie(center_to_cluster_id, it->second);
}
InsertOrDie(membership, *view, cluster_id);
}
}
} // namespace internal
} // namespace ceres