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 {
KeypointResponseGreaterThanThresholdcv::KeypointResponseGreaterThanThreshold49 KeypointResponseGreaterThanThreshold(float _value) :
50 value(_value)
51 {
52 }
operator ()cv::KeypointResponseGreaterThanThreshold53 inline bool operator()(const KeyPoint& kpt) const
54 {
55 return kpt.response >= value;
56 }
57 float value;
58 };
59
60 struct KeypointResponseGreater
61 {
operator ()cv::KeypointResponseGreater62 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
retainBest(std::vector<KeyPoint> & keypoints,int n_points)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 {
RoiPredicatecv::RoiPredicate94 RoiPredicate( const Rect& _r ) : r(_r)
95 {}
96
operator ()cv::RoiPredicate97 bool operator()( const KeyPoint& keyPt ) const
98 {
99 return !r.contains( keyPt.pt );
100 }
101
102 Rect r;
103 };
104
runByImageBorder(std::vector<KeyPoint> & keypoints,Size imageSize,int borderSize)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 {
SizePredicatecv::SizePredicate121 SizePredicate( float _minSize, float _maxSize ) : minSize(_minSize), maxSize(_maxSize)
122 {}
123
operator ()cv::SizePredicate124 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
runByKeypointSize(std::vector<KeyPoint> & keypoints,float minSize,float maxSize)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:
MaskPredicate(const Mat & _mask)146 MaskPredicate( const Mat& _mask ) : mask(_mask) {}
operator ()(const KeyPoint & key_pt) const147 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
runByPixelsMask(std::vector<KeyPoint> & keypoints,const Mat & mask)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 {
KeyPoint_LessThancv::KeyPoint_LessThan167 KeyPoint_LessThan(const std::vector<KeyPoint>& _kp) : kp(&_kp) {}
operator ()cv::KeyPoint_LessThan168 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
removeDuplicated(std::vector<KeyPoint> & keypoints)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