1 /*M/////////////////////////////////////////////////////////////////////////////////////// 2 // 3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 4 // 5 // By downloading, copying, installing or using the software you agree to this license. 6 // If you do not agree to this license, do not download, install, 7 // copy or use the software. 8 // 9 // 10 // License Agreement 11 // For Open Source Computer Vision Library 12 // 13 // Copyright (C) 2008, Willow Garage Inc., all rights reserved. 14 // Third party copyrights are property of their respective owners. 15 // 16 // Redistribution and use in source and binary forms, with or without modification, 17 // are permitted provided that the following conditions are met: 18 // 19 // * Redistribution's of source code must retain the above copyright notice, 20 // this list of conditions and the following disclaimer. 21 // 22 // * Redistribution's in binary form must reproduce the above copyright notice, 23 // this list of conditions and the following disclaimer in the documentation 24 // and/or other materials provided with the distribution. 25 // 26 // * The name of Intel Corporation may not be used to endorse or promote products 27 // derived from this software without specific prior written permission. 28 // 29 // This software is provided by the copyright holders and contributors "as is" and 30 // any express or implied warranties, including, but not limited to, the implied 31 // warranties of merchantability and fitness for a particular purpose are disclaimed. 32 // In no event shall the Intel Corporation or contributors be liable for any direct, 33 // indirect, incidental, special, exemplary, or consequential damages 34 // (including, but not limited to, procurement of substitute goods or services; 35 // loss of use, data, or profits; or business interruption) however caused 36 // and on any theory of liability, whether in contract, strict liability, 37 // or tort (including negligence or otherwise) arising in any way out of 38 // the use of this software, even if advised of the possibility of such damage. 39 // 40 //M*/ 41 42 #include "precomp.hpp" 43 44 namespace cv 45 { 46 47 struct KeypointResponseGreaterThanThreshold 48 { 49 KeypointResponseGreaterThanThreshold(float _value) : 50 value(_value) 51 { 52 } 53 inline bool operator()(const KeyPoint& kpt) const 54 { 55 return kpt.response >= value; 56 } 57 float value; 58 }; 59 60 struct KeypointResponseGreater 61 { 62 inline bool operator()(const KeyPoint& kp1, const KeyPoint& kp2) const 63 { 64 return kp1.response > kp2.response; 65 } 66 }; 67 68 // takes keypoints and culls them by the response 69 void KeyPointsFilter::retainBest(std::vector<KeyPoint>& keypoints, int n_points) 70 { 71 //this is only necessary if the keypoints size is greater than the number of desired points. 72 if( n_points >= 0 && keypoints.size() > (size_t)n_points ) 73 { 74 if (n_points==0) 75 { 76 keypoints.clear(); 77 return; 78 } 79 //first use nth element to partition the keypoints into the best and worst. 80 std::nth_element(keypoints.begin(), keypoints.begin() + n_points, keypoints.end(), KeypointResponseGreater()); 81 //this is the boundary response, and in the case of FAST may be ambigous 82 float ambiguous_response = keypoints[n_points - 1].response; 83 //use std::partition to grab all of the keypoints with the boundary response. 84 std::vector<KeyPoint>::const_iterator new_end = 85 std::partition(keypoints.begin() + n_points, keypoints.end(), 86 KeypointResponseGreaterThanThreshold(ambiguous_response)); 87 //resize the keypoints, given this new end point. nth_element and partition reordered the points inplace 88 keypoints.resize(new_end - keypoints.begin()); 89 } 90 } 91 92 struct RoiPredicate 93 { 94 RoiPredicate( const Rect& _r ) : r(_r) 95 {} 96 97 bool operator()( const KeyPoint& keyPt ) const 98 { 99 return !r.contains( keyPt.pt ); 100 } 101 102 Rect r; 103 }; 104 105 void KeyPointsFilter::runByImageBorder( std::vector<KeyPoint>& keypoints, Size imageSize, int borderSize ) 106 { 107 if( borderSize > 0) 108 { 109 if (imageSize.height <= borderSize * 2 || imageSize.width <= borderSize * 2) 110 keypoints.clear(); 111 else 112 keypoints.erase( std::remove_if(keypoints.begin(), keypoints.end(), 113 RoiPredicate(Rect(Point(borderSize, borderSize), 114 Point(imageSize.width - borderSize, imageSize.height - borderSize)))), 115 keypoints.end() ); 116 } 117 } 118 119 struct SizePredicate 120 { 121 SizePredicate( float _minSize, float _maxSize ) : minSize(_minSize), maxSize(_maxSize) 122 {} 123 124 bool operator()( const KeyPoint& keyPt ) const 125 { 126 float size = keyPt.size; 127 return (size < minSize) || (size > maxSize); 128 } 129 130 float minSize, maxSize; 131 }; 132 133 void KeyPointsFilter::runByKeypointSize( std::vector<KeyPoint>& keypoints, float minSize, float maxSize ) 134 { 135 CV_Assert( minSize >= 0 ); 136 CV_Assert( maxSize >= 0); 137 CV_Assert( minSize <= maxSize ); 138 139 keypoints.erase( std::remove_if(keypoints.begin(), keypoints.end(), SizePredicate(minSize, maxSize)), 140 keypoints.end() ); 141 } 142 143 class MaskPredicate 144 { 145 public: 146 MaskPredicate( const Mat& _mask ) : mask(_mask) {} 147 bool operator() (const KeyPoint& key_pt) const 148 { 149 return mask.at<uchar>( (int)(key_pt.pt.y + 0.5f), (int)(key_pt.pt.x + 0.5f) ) == 0; 150 } 151 152 private: 153 const Mat mask; 154 MaskPredicate& operator=(const MaskPredicate&); 155 }; 156 157 void KeyPointsFilter::runByPixelsMask( std::vector<KeyPoint>& keypoints, const Mat& mask ) 158 { 159 if( mask.empty() ) 160 return; 161 162 keypoints.erase(std::remove_if(keypoints.begin(), keypoints.end(), MaskPredicate(mask)), keypoints.end()); 163 } 164 165 struct KeyPoint_LessThan 166 { 167 KeyPoint_LessThan(const std::vector<KeyPoint>& _kp) : kp(&_kp) {} 168 bool operator()(int i, int j) const 169 { 170 const KeyPoint& kp1 = (*kp)[i]; 171 const KeyPoint& kp2 = (*kp)[j]; 172 if( kp1.pt.x != kp2.pt.x ) 173 return kp1.pt.x < kp2.pt.x; 174 if( kp1.pt.y != kp2.pt.y ) 175 return kp1.pt.y < kp2.pt.y; 176 if( kp1.size != kp2.size ) 177 return kp1.size > kp2.size; 178 if( kp1.angle != kp2.angle ) 179 return kp1.angle < kp2.angle; 180 if( kp1.response != kp2.response ) 181 return kp1.response > kp2.response; 182 if( kp1.octave != kp2.octave ) 183 return kp1.octave > kp2.octave; 184 if( kp1.class_id != kp2.class_id ) 185 return kp1.class_id > kp2.class_id; 186 187 return i < j; 188 } 189 const std::vector<KeyPoint>* kp; 190 }; 191 192 void KeyPointsFilter::removeDuplicated( std::vector<KeyPoint>& keypoints ) 193 { 194 int i, j, n = (int)keypoints.size(); 195 std::vector<int> kpidx(n); 196 std::vector<uchar> mask(n, (uchar)1); 197 198 for( i = 0; i < n; i++ ) 199 kpidx[i] = i; 200 std::sort(kpidx.begin(), kpidx.end(), KeyPoint_LessThan(keypoints)); 201 for( i = 1, j = 0; i < n; i++ ) 202 { 203 KeyPoint& kp1 = keypoints[kpidx[i]]; 204 KeyPoint& kp2 = keypoints[kpidx[j]]; 205 if( kp1.pt.x != kp2.pt.x || kp1.pt.y != kp2.pt.y || 206 kp1.size != kp2.size || kp1.angle != kp2.angle ) 207 j = i; 208 else 209 mask[kpidx[i]] = 0; 210 } 211 212 for( i = j = 0; i < n; i++ ) 213 { 214 if( mask[i] ) 215 { 216 if( i != j ) 217 keypoints[j] = keypoints[i]; 218 j++; 219 } 220 } 221 keypoints.resize(j); 222 } 223 224 } 225
