Point Cloud Library (PCL)
1.7.0
|
00001 /* 00002 * Software License Agreement (BSD License) 00003 * 00004 * Point Cloud Library (PCL) - www.pointclouds.org 00005 * Copyright (c) 2009, Willow Garage, Inc. 00006 * Copyright (c) 2012-, Open Perception, Inc. 00007 * 00008 * All rights reserved. 00009 * 00010 * Redistribution and use in source and binary forms, with or without 00011 * modification, are permitted provided that the following conditions 00012 * are met: 00013 * 00014 * * Redistributions of source code must retain the above copyright 00015 * notice, this list of conditions and the following disclaimer. 00016 * * Redistributions in binary form must reproduce the above 00017 * copyright notice, this list of conditions and the following 00018 * disclaimer in the documentation and/or other materials provided 00019 * with the distribution. 00020 * * Neither the name of the copyright holder(s) nor the names of its 00021 * contributors may be used to endorse or promote products derived 00022 * from this software without specific prior written permission. 00023 * 00024 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 00025 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 00026 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 00027 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 00028 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 00029 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 00030 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 00031 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 00032 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00033 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 00034 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 00035 * POSSIBILITY OF SUCH DAMAGE. 00036 * 00037 * $Id$ 00038 * 00039 */ 00040 00041 #ifndef PCL_SAMPLE_CONSENSUS_IMPL_RMSAC_H_ 00042 #define PCL_SAMPLE_CONSENSUS_IMPL_RMSAC_H_ 00043 00044 #include <pcl/sample_consensus/rmsac.h> 00045 00046 ////////////////////////////////////////////////////////////////////////// 00047 template <typename PointT> bool 00048 pcl::RandomizedMEstimatorSampleConsensus<PointT>::computeModel (int debug_verbosity_level) 00049 { 00050 // Warn and exit if no threshold was set 00051 if (threshold_ == std::numeric_limits<double>::max()) 00052 { 00053 PCL_ERROR ("[pcl::RandomizedMEstimatorSampleConsensus::computeModel] No threshold set!\n"); 00054 return (false); 00055 } 00056 00057 iterations_ = 0; 00058 double d_best_penalty = std::numeric_limits<double>::max(); 00059 double k = 1.0; 00060 00061 std::vector<int> best_model; 00062 std::vector<int> selection; 00063 Eigen::VectorXf model_coefficients; 00064 std::vector<double> distances; 00065 std::set<int> indices_subset; 00066 00067 int n_inliers_count = 0; 00068 unsigned skipped_count = 0; 00069 // supress infinite loops by just allowing 10 x maximum allowed iterations for invalid model parameters! 00070 const unsigned max_skip = max_iterations_ * 10; 00071 00072 // Number of samples to try randomly 00073 size_t fraction_nr_points = pcl_lrint (static_cast<double>(sac_model_->getIndices ()->size ()) * fraction_nr_pretest_ / 100.0); 00074 00075 // Iterate 00076 while (iterations_ < k && skipped_count < max_skip) 00077 { 00078 // Get X samples which satisfy the model criteria 00079 sac_model_->getSamples (iterations_, selection); 00080 00081 if (selection.empty ()) break; 00082 00083 // Search for inliers in the point cloud for the current plane model M 00084 if (!sac_model_->computeModelCoefficients (selection, model_coefficients)) 00085 { 00086 //iterations_++; 00087 ++ skipped_count; 00088 continue; 00089 } 00090 00091 // RMSAC addon: verify a random fraction of the data 00092 // Get X random samples which satisfy the model criterion 00093 this->getRandomSamples (sac_model_->getIndices (), fraction_nr_points, indices_subset); 00094 00095 if (!sac_model_->doSamplesVerifyModel (indices_subset, model_coefficients, threshold_)) 00096 { 00097 // Unfortunately we cannot "continue" after the first iteration, because k might not be set, while iterations gets incremented 00098 if (k != 1.0) 00099 { 00100 ++iterations_; 00101 continue; 00102 } 00103 } 00104 00105 double d_cur_penalty = 0; 00106 // Iterate through the 3d points and calculate the distances from them to the model 00107 sac_model_->getDistancesToModel (model_coefficients, distances); 00108 00109 if (distances.empty () && k > 1.0) 00110 continue; 00111 00112 for (size_t i = 0; i < distances.size (); ++i) 00113 d_cur_penalty += (std::min) (distances[i], threshold_); 00114 00115 // Better match ? 00116 if (d_cur_penalty < d_best_penalty) 00117 { 00118 d_best_penalty = d_cur_penalty; 00119 00120 // Save the current model/coefficients selection as being the best so far 00121 model_ = selection; 00122 model_coefficients_ = model_coefficients; 00123 00124 n_inliers_count = 0; 00125 // Need to compute the number of inliers for this model to adapt k 00126 for (size_t i = 0; i < distances.size (); ++i) 00127 if (distances[i] <= threshold_) 00128 n_inliers_count++; 00129 00130 // Compute the k parameter (k=log(z)/log(1-w^n)) 00131 double w = static_cast<double> (n_inliers_count) / static_cast<double>(sac_model_->getIndices ()->size ()); 00132 double p_no_outliers = 1 - pow (w, static_cast<double> (selection.size ())); 00133 p_no_outliers = (std::max) (std::numeric_limits<double>::epsilon (), p_no_outliers); // Avoid division by -Inf 00134 p_no_outliers = (std::min) (1 - std::numeric_limits<double>::epsilon (), p_no_outliers); // Avoid division by 0. 00135 k = log (1 - probability_) / log (p_no_outliers); 00136 } 00137 00138 ++iterations_; 00139 if (debug_verbosity_level > 1) 00140 PCL_DEBUG ("[pcl::RandomizedMEstimatorSampleConsensus::computeModel] Trial %d out of %d. Best penalty is %f.\n", iterations_, static_cast<int> (ceil (k)), d_best_penalty); 00141 if (iterations_ > max_iterations_) 00142 { 00143 if (debug_verbosity_level > 0) 00144 PCL_DEBUG ("[pcl::RandomizedMEstimatorSampleConsensus::computeModel] MSAC reached the maximum number of trials.\n"); 00145 break; 00146 } 00147 } 00148 00149 if (model_.empty ()) 00150 { 00151 if (debug_verbosity_level > 0) 00152 PCL_DEBUG ("[pcl::RandomizedMEstimatorSampleConsensus::computeModel] Unable to find a solution!\n"); 00153 return (false); 00154 } 00155 00156 // Iterate through the 3d points and calculate the distances from them to the model again 00157 sac_model_->getDistancesToModel (model_coefficients_, distances); 00158 std::vector<int> &indices = *sac_model_->getIndices (); 00159 if (distances.size () != indices.size ()) 00160 { 00161 PCL_ERROR ("[pcl::RandomizedMEstimatorSampleConsensus::computeModel] Estimated distances (%zu) differs than the normal of indices (%zu).\n", distances.size (), indices.size ()); 00162 return (false); 00163 } 00164 00165 inliers_.resize (distances.size ()); 00166 // Get the inliers for the best model found 00167 n_inliers_count = 0; 00168 for (size_t i = 0; i < distances.size (); ++i) 00169 if (distances[i] <= threshold_) 00170 inliers_[n_inliers_count++] = indices[i]; 00171 00172 // Resize the inliers vector 00173 inliers_.resize (n_inliers_count); 00174 00175 if (debug_verbosity_level > 0) 00176 PCL_DEBUG ("[pcl::RandomizedMEstimatorSampleConsensus::computeModel] Model: %zu size, %d inliers.\n", model_.size (), n_inliers_count); 00177 00178 return (true); 00179 } 00180 00181 #define PCL_INSTANTIATE_RandomizedMEstimatorSampleConsensus(T) template class PCL_EXPORTS pcl::RandomizedMEstimatorSampleConsensus<T>; 00182 00183 #endif // PCL_SAMPLE_CONSENSUS_IMPL_RMSAC_H_ 00184