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 (at) 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 #include <vector> 45 46 #include <glog/logging.h> 47 #include "ceres/collections_port.h" 48 #include "ceres/graph.h" 49 #include "ceres/map_util.h" 50 #include "ceres/internal/macros.h" 51 52 namespace ceres { 53 namespace internal { 54 55 struct CanonicalViewsClusteringOptions; 56 57 // Compute a partitioning of the vertices of the graph using the 58 // canonical views clustering algorithm. 59 // 60 // In the following we will use the terms vertices and views 61 // interchangably. Given a weighted Graph G(V,E), the canonical views 62 // of G are the the set of vertices that best "summarize" the content 63 // of the graph. If w_ij i s the weight connecting the vertex i to 64 // vertex j, and C is the set of canonical views. Then the objective 65 // of the canonical views algorithm is 66 // 67 // E[C] = sum_[i in V] max_[j in C] w_ij 68 // - size_penalty_weight * |C| 69 // - similarity_penalty_weight * sum_[i in C, j in C, j > i] w_ij 70 // 71 // alpha is the size penalty that penalizes large number of canonical 72 // views. 73 // 74 // beta is the similarity penalty that penalizes canonical views that 75 // are too similar to other canonical views. 76 // 77 // Thus the canonical views algorithm tries to find a canonical view 78 // for each vertex in the graph which best explains it, while trying 79 // to minimize the number of canonical views and the overlap between 80 // them. 81 // 82 // We further augment the above objective function by allowing for per 83 // vertex weights, higher weights indicating a higher preference for 84 // being chosen as a canonical view. Thus if w_i is the vertex weight 85 // for vertex i, the objective function is then 86 // 87 // E[C] = sum_[i in V] max_[j in C] w_ij 88 // - size_penalty_weight * |C| 89 // - similarity_penalty_weight * sum_[i in C, j in C, j > i] w_ij 90 // + view_score_weight * sum_[i in C] w_i 91 // 92 // centers will contain the vertices that are the identified 93 // as the canonical views/cluster centers, and membership is a map 94 // from vertices to cluster_ids. The i^th cluster center corresponds 95 // to the i^th cluster. 96 // 97 // It is possible depending on the configuration of the clustering 98 // algorithm that some of the vertices may not be assigned to any 99 // cluster. In this case they are assigned to a cluster with id = -1; 100 void ComputeCanonicalViewsClustering( 101 const Graph<int>& graph, 102 const CanonicalViewsClusteringOptions& options, 103 vector<int>* centers, 104 HashMap<int, int>* membership); 105 106 struct CanonicalViewsClusteringOptions { 107 CanonicalViewsClusteringOptions() 108 : min_views(3), 109 size_penalty_weight(5.75), 110 similarity_penalty_weight(100.0), 111 view_score_weight(0.0) { 112 } 113 // The minimum number of canonical views to compute. 114 int min_views; 115 116 // Penalty weight for the number of canonical views. A higher 117 // number will result in fewer canonical views. 118 double size_penalty_weight; 119 120 // Penalty weight for the diversity (orthogonality) of the 121 // canonical views. A higher number will encourage less similar 122 // canonical views. 123 double similarity_penalty_weight; 124 125 // Weight for per-view scores. Lower weight places less 126 // confidence in the view scores. 127 double view_score_weight; 128 }; 129 130 } // namespace internal 131 } // namespace ceres 132 133 #endif // CERES_INTERNAL_CANONICAL_VIEWS_CLUSTERING_H_ 134
