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: kushalav (at) google.com (Avanish Kushal)
     30 //         sameeragarwal (at) google.com (Sameer Agarwal)
     31 
     32 #include "ceres/visibility.h"
     33 
     34 #include <set>
     35 #include <vector>
     36 #include "ceres/block_structure.h"
     37 #include "ceres/graph.h"
     38 #include "ceres/internal/scoped_ptr.h"
     39 #include "glog/logging.h"
     40 #include "gtest/gtest.h"
     41 
     42 namespace ceres {
     43 namespace internal {
     44 
     45 class VisibilityTest : public ::testing::Test {
     46 };
     47 
     48 TEST(VisibilityTest, SimpleMatrix) {
     49   //   A = [1 0 0 0 0 1
     50   //        1 0 0 1 0 0
     51   //        0 1 1 0 0 0
     52   //        0 1 0 0 1 0]
     53 
     54   int num_cols = 6;
     55   int num_eliminate_blocks = 2;
     56   CompressedRowBlockStructure bs;
     57 
     58   // Row 1
     59   {
     60     bs.rows.push_back(CompressedRow());
     61     CompressedRow& row = bs.rows.back();
     62     row.block.size = 2;
     63     row.block.position = 0;
     64     row.cells.push_back(Cell(0, 0));
     65     row.cells.push_back(Cell(5, 0));
     66   }
     67 
     68   // Row 2
     69   {
     70     bs.rows.push_back(CompressedRow());
     71     CompressedRow& row = bs.rows.back();
     72     row.block.size = 2;
     73     row.block.position = 2;
     74     row.cells.push_back(Cell(0, 1));
     75     row.cells.push_back(Cell(3, 1));
     76   }
     77 
     78   // Row 3
     79   {
     80     bs.rows.push_back(CompressedRow());
     81     CompressedRow& row = bs.rows.back();
     82     row.block.size = 2;
     83     row.block.position = 4;
     84     row.cells.push_back(Cell(1, 2));
     85     row.cells.push_back(Cell(2, 2));
     86   }
     87 
     88   // Row 4
     89   {
     90     bs.rows.push_back(CompressedRow());
     91     CompressedRow& row = bs.rows.back();
     92     row.block.size = 2;
     93     row.block.position = 6;
     94     row.cells.push_back(Cell(1, 3));
     95     row.cells.push_back(Cell(4, 3));
     96   }
     97   bs.cols.resize(num_cols);
     98 
     99   vector< set<int> > visibility;
    100   ComputeVisibility(bs, num_eliminate_blocks, &visibility);
    101   ASSERT_EQ(visibility.size(), num_cols - num_eliminate_blocks);
    102   for (int i = 0; i < visibility.size(); ++i) {
    103     ASSERT_EQ(visibility[i].size(), 1);
    104   }
    105 
    106   scoped_ptr<Graph<int> > graph(CreateSchurComplementGraph(visibility));
    107   EXPECT_EQ(graph->vertices().size(), visibility.size());
    108   for (int i = 0; i < visibility.size(); ++i) {
    109     EXPECT_EQ(graph->VertexWeight(i), 1.0);
    110   }
    111 
    112   for (int i = 0; i < visibility.size(); ++i) {
    113     for (int j = i; j < visibility.size(); ++j) {
    114       double edge_weight = 0.0;
    115       if ((i == 1 && j == 3) || (i == 0 && j == 2) || (i == j)) {
    116         edge_weight = 1.0;
    117       }
    118 
    119       EXPECT_EQ(graph->EdgeWeight(i, j), edge_weight)
    120           << "Edge: " << i << " " << j
    121           << " weight: " << graph->EdgeWeight(i, j)
    122           << " expected weight: " << edge_weight;
    123     }
    124   }
    125 }
    126 
    127 
    128 TEST(VisibilityTest, NoEBlocks) {
    129   //   A = [1 0 0 0 0 0
    130   //        1 0 0 0 0 0
    131   //        0 1 0 0 0 0
    132   //        0 1 0 0 0 0]
    133 
    134   int num_cols = 6;
    135   int num_eliminate_blocks = 2;
    136   CompressedRowBlockStructure bs;
    137 
    138   // Row 1
    139   {
    140     bs.rows.push_back(CompressedRow());
    141     CompressedRow& row = bs.rows.back();
    142     row.block.size = 2;
    143     row.block.position = 0;
    144     row.cells.push_back(Cell(0, 0));
    145   }
    146 
    147   // Row 2
    148   {
    149     bs.rows.push_back(CompressedRow());
    150     CompressedRow& row = bs.rows.back();
    151     row.block.size = 2;
    152     row.block.position = 2;
    153     row.cells.push_back(Cell(0, 1));
    154   }
    155 
    156   // Row 3
    157   {
    158     bs.rows.push_back(CompressedRow());
    159     CompressedRow& row = bs.rows.back();
    160     row.block.size = 2;
    161     row.block.position = 4;
    162     row.cells.push_back(Cell(1, 2));
    163   }
    164 
    165   // Row 4
    166   {
    167     bs.rows.push_back(CompressedRow());
    168     CompressedRow& row = bs.rows.back();
    169     row.block.size = 2;
    170     row.block.position = 6;
    171     row.cells.push_back(Cell(1, 3));
    172   }
    173   bs.cols.resize(num_cols);
    174 
    175   vector<set<int> > visibility;
    176   ComputeVisibility(bs, num_eliminate_blocks, &visibility);
    177   ASSERT_EQ(visibility.size(), num_cols - num_eliminate_blocks);
    178   for (int i = 0; i < visibility.size(); ++i) {
    179     ASSERT_EQ(visibility[i].size(), 0);
    180   }
    181 
    182   scoped_ptr<Graph<int> > graph(CreateSchurComplementGraph(visibility));
    183   EXPECT_EQ(graph->vertices().size(), visibility.size());
    184   for (int i = 0; i < visibility.size(); ++i) {
    185     EXPECT_EQ(graph->VertexWeight(i), 1.0);
    186   }
    187 
    188   for (int i = 0; i < visibility.size(); ++i) {
    189     for (int j = i; j < visibility.size(); ++j) {
    190       double edge_weight = 0.0;
    191       if (i == j) {
    192         edge_weight = 1.0;
    193       }
    194       EXPECT_EQ(graph->EdgeWeight(i, j), edge_weight)
    195           << "Edge: " << i << " " << j
    196           << " weight: " << graph->EdgeWeight(i, j)
    197           << " expected weight: " << edge_weight;
    198     }
    199   }
    200 }
    201 
    202 }  // namespace internal
    203 }  // namespace ceres
    204