1 /*
2 * Copyright (c) 2019-2020 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 "arm_compute/core/CPP/kernels/CPPNonMaximumSuppressionKernel.h"
25
26 #include "arm_compute/core/Helpers.h"
27 #include "arm_compute/core/Validate.h"
28
29 #include "src/core/helpers/AutoConfiguration.h"
30 #include "src/core/helpers/WindowHelpers.h"
31
32 #include <algorithm>
33
34 namespace arm_compute
35 {
36 namespace
37 {
validate_arguments(const ITensorInfo * bboxes,const ITensorInfo * scores,const ITensorInfo * output_indices,unsigned int max_output_size,const float score_threshold,const float iou_threshold)38 Status validate_arguments(const ITensorInfo *bboxes, const ITensorInfo *scores, const ITensorInfo *output_indices, unsigned int max_output_size,
39 const float score_threshold, const float iou_threshold)
40 {
41 ARM_COMPUTE_RETURN_ERROR_ON_NULLPTR(bboxes, scores, output_indices);
42 ARM_COMPUTE_RETURN_ERROR_ON_DATA_TYPE_CHANNEL_NOT_IN(bboxes, 1, DataType::F32);
43 ARM_COMPUTE_RETURN_ERROR_ON_DATA_TYPE_CHANNEL_NOT_IN(output_indices, 1, DataType::S32);
44 ARM_COMPUTE_RETURN_ERROR_ON_MSG(bboxes->num_dimensions() > 2, "The bboxes tensor must be a 2-D float tensor of shape [4, num_boxes].");
45 ARM_COMPUTE_RETURN_ERROR_ON_MSG(scores->num_dimensions() > 1, "The scores tensor must be a 1-D float tensor of shape [num_boxes].");
46 ARM_COMPUTE_RETURN_ERROR_ON_MSG(output_indices->num_dimensions() > 1, "The indices must be 1-D integer tensor of shape [M], where max_output_size <= M");
47 ARM_COMPUTE_RETURN_ERROR_ON_MISMATCHING_DATA_TYPES(bboxes, scores);
48 ARM_COMPUTE_RETURN_ERROR_ON_MSG(output_indices->dimension(0) == 0, "Indices tensor must be bigger than 0");
49 ARM_COMPUTE_RETURN_ERROR_ON_MSG(max_output_size == 0, "Max size cannot be 0");
50 ARM_COMPUTE_RETURN_ERROR_ON_MSG(iou_threshold < 0.f || iou_threshold > 1.f, "IOU threshold must be in [0,1]");
51 ARM_COMPUTE_RETURN_ERROR_ON_MSG(score_threshold < 0.f || score_threshold > 1.f, "Score threshold must be in [0,1]");
52
53 return Status{};
54 }
55 } // namespace
56
CPPNonMaximumSuppressionKernel()57 CPPNonMaximumSuppressionKernel::CPPNonMaximumSuppressionKernel()
58 : _input_bboxes(nullptr), _input_scores(nullptr), _output_indices(nullptr), _max_output_size(0), _score_threshold(0.f), _iou_threshold(0.f), _num_boxes(0)
59 {
60 }
61
configure(const ITensor * input_bboxes,const ITensor * input_scores,ITensor * output_indices,unsigned int max_output_size,const float score_threshold,const float iou_threshold)62 void CPPNonMaximumSuppressionKernel::configure(const ITensor *input_bboxes, const ITensor *input_scores, ITensor *output_indices,
63 unsigned int max_output_size, const float score_threshold, const float iou_threshold)
64 {
65 ARM_COMPUTE_ERROR_ON_NULLPTR(input_bboxes, input_scores, output_indices);
66 ARM_COMPUTE_ERROR_THROW_ON(validate_arguments(input_bboxes->info(), input_scores->info(), output_indices->info(), max_output_size, score_threshold, iou_threshold));
67
68 auto_init_if_empty(*output_indices->info(), TensorShape(max_output_size), 1, DataType::U8, QuantizationInfo());
69
70 _input_bboxes = input_bboxes;
71 _input_scores = input_scores;
72 _output_indices = output_indices;
73 _score_threshold = score_threshold;
74 _iou_threshold = iou_threshold;
75 _max_output_size = max_output_size;
76 _num_boxes = input_scores->info()->dimension(0);
77
78 // Configure kernel window
79 Window win = calculate_max_window(*output_indices->info(), Steps());
80
81 // The CPPNonMaximumSuppressionKernel doesn't need padding so update_window_and_padding() can be skipped
82 ICPPKernel::configure(win);
83 }
84
validate(const ITensorInfo * bboxes,const ITensorInfo * scores,const ITensorInfo * output_indices,unsigned int max_output_size,const float score_threshold,const float iou_threshold)85 Status CPPNonMaximumSuppressionKernel::validate(const ITensorInfo *bboxes, const ITensorInfo *scores, const ITensorInfo *output_indices,
86 unsigned int max_output_size, const float score_threshold, const float iou_threshold)
87 {
88 ARM_COMPUTE_RETURN_ON_ERROR(validate_arguments(bboxes, scores, output_indices, max_output_size, score_threshold, iou_threshold));
89 return Status{};
90 }
91
run(const Window & window,const ThreadInfo & info)92 void CPPNonMaximumSuppressionKernel::run(const Window &window, const ThreadInfo &info)
93 {
94 ARM_COMPUTE_UNUSED(info);
95 ARM_COMPUTE_UNUSED(window);
96 ARM_COMPUTE_ERROR_ON_UNCONFIGURED_KERNEL(this);
97 ARM_COMPUTE_ERROR_ON_INVALID_SUBWINDOW(ICPPKernel::window(), window);
98
99 // Auxiliary tensors
100 std::vector<int> indices_above_thd;
101 std::vector<float> scores_above_thd;
102 for(unsigned int i = 0; i < _num_boxes; ++i)
103 {
104 const float score_i = *(reinterpret_cast<float *>(_input_scores->ptr_to_element(Coordinates(i))));
105 if(score_i >= _score_threshold)
106 {
107 scores_above_thd.emplace_back(score_i);
108 indices_above_thd.emplace_back(i);
109 }
110 }
111
112 // Sort selected indices based on scores
113 const unsigned int num_above_thd = indices_above_thd.size();
114 std::vector<unsigned int> sorted_indices;
115 sorted_indices.resize(num_above_thd);
116 std::iota(sorted_indices.data(), sorted_indices.data() + num_above_thd, 0);
117 std::sort(std::begin(sorted_indices),
118 std::end(sorted_indices),
119 [&](unsigned int first, unsigned int second)
120 {
121 return scores_above_thd[first] > scores_above_thd[second];
122 });
123
124 // Number of output is the minimum between max_detection and the scores above the threshold
125 const unsigned int num_output = std::min(_max_output_size, num_above_thd);
126 unsigned int output_idx = 0;
127 std::vector<bool> visited(num_above_thd, false);
128
129 // Keep only boxes with small IoU
130 for(unsigned int i = 0; i < num_above_thd; ++i)
131 {
132 // Check if the output is full
133 if(output_idx >= num_output)
134 {
135 break;
136 }
137
138 // Check if it was already visited, if not add it to the output and update the indices counter
139 if(!visited[sorted_indices[i]])
140 {
141 *(reinterpret_cast<int *>(_output_indices->ptr_to_element(Coordinates(output_idx)))) = indices_above_thd[sorted_indices[i]];
142 visited[sorted_indices[i]] = true;
143 ++output_idx;
144 }
145 else
146 {
147 continue;
148 }
149
150 // Once added one element at the output check if the next ones overlap and can be skipped
151 for(unsigned int j = i + 1; j < num_above_thd; ++j)
152 {
153 if(!visited[sorted_indices[j]])
154 {
155 // Calculate IoU
156 const unsigned int i_index = indices_above_thd[sorted_indices[i]];
157 const unsigned int j_index = indices_above_thd[sorted_indices[j]];
158 // Box-corner format: xmin, ymin, xmax, ymax
159 const auto box_i_xmin = *(reinterpret_cast<float *>(_input_bboxes->ptr_to_element(Coordinates(0, i_index))));
160 const auto box_i_ymin = *(reinterpret_cast<float *>(_input_bboxes->ptr_to_element(Coordinates(1, i_index))));
161 const auto box_i_xmax = *(reinterpret_cast<float *>(_input_bboxes->ptr_to_element(Coordinates(2, i_index))));
162 const auto box_i_ymax = *(reinterpret_cast<float *>(_input_bboxes->ptr_to_element(Coordinates(3, i_index))));
163
164 const auto box_j_xmin = *(reinterpret_cast<float *>(_input_bboxes->ptr_to_element(Coordinates(0, j_index))));
165 const auto box_j_ymin = *(reinterpret_cast<float *>(_input_bboxes->ptr_to_element(Coordinates(1, j_index))));
166 const auto box_j_xmax = *(reinterpret_cast<float *>(_input_bboxes->ptr_to_element(Coordinates(2, j_index))));
167 const auto box_j_ymax = *(reinterpret_cast<float *>(_input_bboxes->ptr_to_element(Coordinates(3, j_index))));
168
169 const float area_i = (box_i_xmax - box_i_xmin) * (box_i_ymax - box_i_ymin);
170 const float area_j = (box_j_xmax - box_j_xmin) * (box_j_ymax - box_j_ymin);
171 float overlap;
172 if(area_i <= 0 || area_j <= 0)
173 {
174 overlap = 0.0f;
175 }
176 else
177 {
178 const auto y_min_intersection = std::max<float>(box_i_ymin, box_j_ymin);
179 const auto x_min_intersection = std::max<float>(box_i_xmin, box_j_xmin);
180 const auto y_max_intersection = std::min<float>(box_i_ymax, box_j_ymax);
181 const auto x_max_intersection = std::min<float>(box_i_xmax, box_j_xmax);
182 const auto area_intersection = std::max<float>(y_max_intersection - y_min_intersection, 0.0f) * std::max<float>(x_max_intersection - x_min_intersection, 0.0f);
183 overlap = area_intersection / (area_i + area_j - area_intersection);
184 }
185
186 if(overlap > _iou_threshold)
187 {
188 visited[sorted_indices[j]] = true;
189 }
190 }
191 }
192 }
193 // The output could be full but not the output indices tensor
194 // Instead return values not valid we put -1
195 for(; output_idx < _max_output_size; ++output_idx)
196 {
197 *(reinterpret_cast<int *>(_output_indices->ptr_to_element(Coordinates(output_idx)))) = -1;
198 }
199 }
200 } // namespace arm_compute
201