Home | History | Annotate | Download | only in ceres
      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 // 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 
     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 CanonicalViewsClusteringOptions& options,
    104     const Graph<int>& graph,
    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