1 /*
2 * Copyright (c) 2017-2019 Arm Limited.
3 *
4 * SPDX-License-Identifier: MIT
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to
8 * deal in the Software without restriction, including without limitation the
9 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10 * sell copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24 #include "FastCorners.h"
25
26 #include "Utils.h"
27 #include "tests/validation/Helpers.h"
28 #include "tests/validation/reference/NonMaximaSuppression.h"
29
30 #include "tests/framework/Asserts.h"
31 #include <iomanip>
32
33 namespace arm_compute
34 {
35 namespace test
36 {
37 namespace validation
38 {
39 namespace reference
40 {
41 namespace
42 {
43 constexpr unsigned int bresenham_radius = 3;
44 constexpr unsigned int bresenham_count = 16;
45
46 /*
47 Offsets of the 16 pixels in the Bresenham circle of radius 3 centered on P
48 . . . . . . . . .
49 . . . F 0 1 . . .
50 . . E . . . 2 . .
51 . D . . . . . 3 .
52 . C . . P . . 4 .
53 . B . . . . . 5 .
54 . . A . . . 6 . .
55 . . . 9 8 7 . . .
56 . . . . . . . . .
57 */
58 const std::array<std::array<int, 2>, 16> circle_offsets =
59 {
60 {
61 { { 0, -3 } }, // 0 - pixel #1
62 { { 1, -3 } }, // 1 - pixel #2
63 { { 2, -2 } }, // 2 - pixel #3
64 { { 3, -1 } }, // 3 - pixel #4
65 { { 3, 0 } }, // 4 - pixel #5
66 { { 3, 1 } }, // 5 - pixel #6
67 { { 2, 2 } }, // 6 - pixel #7
68 { { 1, 3 } }, // 7 - pixel #8
69 { { 0, 3 } }, // 8 - pixel #9
70 { { -1, 3 } }, // 9 - pixel #10
71 { { -2, 2 } }, // A - pixel #11
72 { { -3, 1 } }, // B - pixel #12
73 { { -3, 0 } }, // C - pixel #13
74 { { -3, -1 } }, // D - pixel #14
75 { { -2, -2 } }, // E - pixel #15
76 { { -1, -3 } } // F - pixel #16
77 }
78 };
79
80 /*
81 FAST-9 bit masks for consecutive points surrounding a corner candidate
82 Rejection of non-corners is expedited by checking pixels 1, 9, then 5, 13...
83 */
84 const std::array<uint16_t, 16> fast9_masks =
85 {
86 {
87 0x01FF, // 0000 0001 1111 1111
88 0x03FE, // 0000 0011 1111 1110
89 0x07FC, // 0000 0111 1111 1100
90 0x0FF8, // 0000 1111 1111 1000
91 0x1FF0, // 0001 1111 1111 0000
92 0x3FE0, // 0011 1111 1110 0000
93 0x7FC0, // 0111 1111 1100 0000
94 0xFF80, // 1111 1111 1000 0000
95 0xFF01, // 1111 1111 0000 0001
96 0xFE03, // 1111 1110 0000 0011
97 0xFC07, // 1111 1100 0000 0111
98 0xF80F, // 1111 1000 0000 1111
99 0xF01F, // 1111 0000 0001 1111
100 0xE03F, // 1110 0000 0011 1111
101 0xC07F, // 1100 0000 0111 1111
102 0x80FF // 1000 0000 1111 1111
103 }
104 };
105
in_range(const uint8_t low,const uint8_t high,const uint8_t val)106 inline bool in_range(const uint8_t low, const uint8_t high, const uint8_t val)
107 {
108 return low <= val && val <= high;
109 }
110
111 template <typename T, typename F>
is_a_corner(const Coordinates & candidate,const SimpleTensor<T> & src,uint8_t threshold,BorderMode border_mode,T constant_border_value,F intensity_at)112 bool is_a_corner(const Coordinates &candidate, const SimpleTensor<T> &src, uint8_t threshold, BorderMode border_mode, T constant_border_value, F intensity_at)
113 {
114 const auto intensity_p = tensor_elem_at(src, candidate, border_mode, constant_border_value);
115 const auto thresh_bright = intensity_p + threshold;
116 const auto thresh_dark = intensity_p - threshold;
117
118 // Quicker rejection of non-corner points by checking pixels 1, 9 then 5, 13 around the candidate
119 const auto p1 = intensity_at(candidate, 0);
120 const auto p9 = intensity_at(candidate, 8);
121 const auto p5 = intensity_at(candidate, 4);
122 const auto p13 = intensity_at(candidate, 12);
123
124 if((in_range(thresh_dark, thresh_bright, p1) && in_range(thresh_dark, thresh_bright, p9))
125 || (in_range(thresh_dark, thresh_bright, p5) && in_range(thresh_dark, thresh_bright, p13)))
126 {
127 return false;
128 }
129
130 uint16_t mask_bright = 0;
131 uint16_t mask_dark = 0;
132
133 // Set bits of the brighter/darker pixels mask accordingly
134 for(unsigned int n = 0; n < bresenham_count; ++n)
135 {
136 T intensity_n = intensity_at(candidate, n);
137 mask_bright |= (intensity_n > thresh_bright) << n;
138 mask_dark |= (intensity_n < thresh_dark) << n;
139 }
140
141 // Mark as corner candidate if brighter/darker pixel sequence satisfies any one of the FAST-9 masks
142 const auto found = std::find_if(fast9_masks.begin(), fast9_masks.end(), [&](decltype(fast9_masks[0]) mask)
143 {
144 return (mask_bright & mask) == mask || (mask_dark & mask) == mask;
145 });
146
147 return found != fast9_masks.end();
148 }
149 } // namespace
150
151 template <typename T>
fast_corners(const SimpleTensor<T> & src,float input_thresh,bool suppress_nonmax,BorderMode border_mode,T constant_border_value)152 std::vector<KeyPoint> fast_corners(const SimpleTensor<T> &src, float input_thresh, bool suppress_nonmax, BorderMode border_mode, T constant_border_value)
153 {
154 // Get intensity of pixel at given index on the Bresenham circle around a candidate point
155 const auto intensity_at = [&](const Coordinates & point, const unsigned int idx)
156 {
157 const auto offset = circle_offsets[idx];
158 Coordinates px{ point.x() + offset[0], point.y() + offset[1] };
159 return tensor_elem_at(src, px, border_mode, constant_border_value);
160 };
161
162 const auto threshold = static_cast<uint8_t>(input_thresh);
163 std::vector<KeyPoint> corners;
164
165 // 1. Detect potential corners (the segment test)
166 std::vector<Coordinates> corner_candidates;
167 SimpleTensor<uint8_t> scores(src.shape(), DataType::U8);
168 ValidRegion valid_region = shape_to_valid_region(src.shape(), BorderMode::UNDEFINED == border_mode, BorderSize(bresenham_radius));
169
170 const uint32_t num_elements = src.num_elements();
171 for(uint32_t i = 0; i < num_elements; ++i)
172 {
173 Coordinates candidate = index2coord(src.shape(), i);
174 scores[i] = 0;
175 if(!is_in_valid_region(valid_region, candidate))
176 {
177 continue;
178 }
179
180 if(is_a_corner(candidate, src, threshold, border_mode, constant_border_value, intensity_at))
181 {
182 corner_candidates.emplace_back(candidate);
183 scores[i] = 1;
184 }
185 }
186
187 // 2. Calculate corner scores if necessary
188 if(suppress_nonmax)
189 {
190 for(const auto &candidate : corner_candidates)
191 {
192 const auto index = coord2index(scores.shape(), candidate);
193 uint8_t thresh_max = UINT8_MAX;
194 uint8_t thresh_min = threshold;
195 uint8_t response = (thresh_min + thresh_max) / 2;
196
197 // Corner score (response) is the largest threshold for which the pixel remains a corner
198 while(thresh_max - thresh_min > 1)
199 {
200 response = (thresh_min + thresh_max) / 2;
201 if(is_a_corner(candidate, src, response, border_mode, constant_border_value, intensity_at))
202 {
203 thresh_min = response; // raise threshold
204 }
205 else
206 {
207 thresh_max = response; // lower threshold
208 }
209 }
210 scores[index] = thresh_min;
211 }
212
213 scores = non_maxima_suppression(scores, border_mode, constant_border_value);
214 valid_region = shape_to_valid_region(scores.shape(), BorderMode::UNDEFINED == border_mode, BorderSize(bresenham_radius + 1));
215 }
216
217 for(const auto &candidate : corner_candidates)
218 {
219 const auto index = coord2index(scores.shape(), candidate);
220 if(scores[index] > 0.f && is_in_valid_region(valid_region, candidate))
221 {
222 KeyPoint corner;
223 corner.x = candidate.x();
224 corner.y = candidate.y();
225 corner.strength = scores[index];
226 corner.tracking_status = 1;
227 corner.scale = 0.f;
228 corner.orientation = 0.f;
229 corner.error = 0.f;
230 corners.emplace_back(corner);
231 }
232 }
233
234 return corners;
235 }
236
237 template std::vector<KeyPoint> fast_corners(const SimpleTensor<uint8_t> &src, float threshold, bool suppress_nonmax, BorderMode border_mode, uint8_t constant_border_value);
238 } // namespace reference
239 } // namespace validation
240 } // namespace test
241 } // namespace arm_compute
242