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 #ifndef CERES_NO_SUITESPARSE 45 46 #include <vector> 47 48 #include "ceres/collections_port.h" 49 #include "ceres/graph.h" 50 #include "ceres/internal/macros.h" 51 #include "ceres/map_util.h" 52 #include "glog/logging.h" 53 54 namespace ceres { 55 namespace internal { 56 57 struct 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; 102 void ComputeCanonicalViewsClustering( 103 const Graph<int>& graph, 104 const CanonicalViewsClusteringOptions& options, 105 vector<int>* centers, 106 HashMap<int, int>* membership); 107 108 struct 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
