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: sameeragarwal@google.com (Sameer Agarwal) 30// 31// An implementation of the Canonical Views clustering algorithm from 32// "Scene Summarization for Online Image Collections", Ian Simon, Noah 33// Snavely, Steven M. Seitz, ICCV 2007. 34// 35// More details can be found at 36// http://grail.cs.washington.edu/projects/canonview/ 37// 38// Ceres uses this algorithm to perform view clustering for 39// constructing visibility based preconditioners. 40 41#ifndef CERES_INTERNAL_CANONICAL_VIEWS_CLUSTERING_H_ 42#define CERES_INTERNAL_CANONICAL_VIEWS_CLUSTERING_H_ 43 44// This include must come before any #ifndef check on Ceres compile options. 45#include "ceres/internal/port.h" 46 47#ifndef CERES_NO_SUITESPARSE 48 49#include <vector> 50 51#include "ceres/collections_port.h" 52#include "ceres/graph.h" 53 54namespace ceres { 55namespace internal { 56 57struct CanonicalViewsClusteringOptions; 58 59// Compute a partitioning of the vertices of the graph using the 60// canonical views clustering algorithm. 61// 62// In the following we will use the terms vertices and views 63// interchangably. Given a weighted Graph G(V,E), the canonical views 64// of G are the the set of vertices that best "summarize" the content 65// of the graph. If w_ij i s the weight connecting the vertex i to 66// vertex j, and C is the set of canonical views. Then the objective 67// of the canonical views algorithm is 68// 69// E[C] = sum_[i in V] max_[j in C] w_ij 70// - size_penalty_weight * |C| 71// - similarity_penalty_weight * sum_[i in C, j in C, j > i] w_ij 72// 73// alpha is the size penalty that penalizes large number of canonical 74// views. 75// 76// beta is the similarity penalty that penalizes canonical views that 77// are too similar to other canonical views. 78// 79// Thus the canonical views algorithm tries to find a canonical view 80// for each vertex in the graph which best explains it, while trying 81// to minimize the number of canonical views and the overlap between 82// them. 83// 84// We further augment the above objective function by allowing for per 85// vertex weights, higher weights indicating a higher preference for 86// being chosen as a canonical view. Thus if w_i is the vertex weight 87// for vertex i, the objective function is then 88// 89// E[C] = sum_[i in V] max_[j in C] w_ij 90// - size_penalty_weight * |C| 91// - similarity_penalty_weight * sum_[i in C, j in C, j > i] w_ij 92// + view_score_weight * sum_[i in C] w_i 93// 94// centers will contain the vertices that are the identified 95// as the canonical views/cluster centers, and membership is a map 96// from vertices to cluster_ids. The i^th cluster center corresponds 97// to the i^th cluster. 98// 99// It is possible depending on the configuration of the clustering 100// algorithm that some of the vertices may not be assigned to any 101// cluster. In this case they are assigned to a cluster with id = -1; 102void ComputeCanonicalViewsClustering( 103 const CanonicalViewsClusteringOptions& options, 104 const Graph<int>& graph, 105 vector<int>* centers, 106 HashMap<int, int>* membership); 107 108struct CanonicalViewsClusteringOptions { 109 CanonicalViewsClusteringOptions() 110 : min_views(3), 111 size_penalty_weight(5.75), 112 similarity_penalty_weight(100.0), 113 view_score_weight(0.0) { 114 } 115 // The minimum number of canonical views to compute. 116 int min_views; 117 118 // Penalty weight for the number of canonical views. A higher 119 // number will result in fewer canonical views. 120 double size_penalty_weight; 121 122 // Penalty weight for the diversity (orthogonality) of the 123 // canonical views. A higher number will encourage less similar 124 // canonical views. 125 double similarity_penalty_weight; 126 127 // Weight for per-view scores. Lower weight places less 128 // confidence in the view scores. 129 double view_score_weight; 130}; 131 132} // namespace internal 133} // namespace ceres 134 135#endif // CERES_NO_SUITESPARSE 136#endif // CERES_INTERNAL_CANONICAL_VIEWS_CLUSTERING_H_ 137