Compute Library
 21.08
NonMaxSuppression.cpp
Go to the documentation of this file.
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 "NonMaxSuppression.h"
25 
26 #include "arm_compute/core/Types.h"
28 
29 namespace arm_compute
30 {
31 namespace test
32 {
33 namespace validation
34 {
35 namespace reference
36 {
37 namespace
38 {
39 using CandidateBox = std::pair<int /* index */, float /* score */>;
40 using Box = std::tuple<float, float, float, float>;
41 
42 inline float get_elem_by_coordinate(const SimpleTensor<float> &tensor, Coordinates coord)
43 {
44  return *static_cast<const float *>(tensor(coord));
45 }
46 
47 inline Box get_box(const SimpleTensor<float> &boxes, size_t id)
48 {
49  return std::make_tuple(
50  get_elem_by_coordinate(boxes, Coordinates(0, id)),
51  get_elem_by_coordinate(boxes, Coordinates(1, id)),
52  get_elem_by_coordinate(boxes, Coordinates(2, id)),
53  get_elem_by_coordinate(boxes, Coordinates(3, id)));
54 }
55 
56 // returns a pair (minX, minY)
57 inline std::pair<float, float> get_min_yx(Box b)
58 {
59  return std::make_pair(
60  std::min<float>(std::get<0>(b), std::get<2>(b)),
61  std::min<float>(std::get<1>(b), std::get<3>(b)));
62 }
63 // returns a pair (maxX, maxY)
64 inline std::pair<float, float> get_max_yx(Box b)
65 {
66  return std::make_pair(
67  std::max<float>(std::get<0>(b), std::get<2>(b)),
68  std::max<float>(std::get<1>(b), std::get<3>(b)));
69 }
70 
71 inline float compute_size(const std::pair<float, float> &min, const std::pair<float, float> &max)
72 {
73  return (max.first - min.first) * (max.second - min.second);
74 }
75 
76 inline float compute_intersection(const std::pair<float, float> &b0_min, const std::pair<float, float> &b0_max,
77  const std::pair<float, float> &b1_min, const std::pair<float, float> &b1_max, float b0_size, float b1_size)
78 {
79  const float inter = std::max<float>(std::min<float>(b0_max.first, b1_max.first) - std::max<float>(b0_min.first, b1_min.first), 0.0f) * std::max<float>(std::min<float>(b0_max.second,
80  b1_max.second)
81  - std::max<float>(b0_min.second, b1_min.second),
82  0.0f);
83  return inter / (b0_size + b1_size - inter);
84 }
85 
86 inline bool reject_box(Box b0, Box b1, float threshold)
87 {
88  const auto b0_min = get_min_yx(b0);
89  const auto b0_max = get_max_yx(b0);
90  const auto b1_min = get_min_yx(b1);
91  const auto b1_max = get_max_yx(b1);
92  const float b0_size = compute_size(b0_min, b0_max);
93  const float b1_size = compute_size(b1_min, b1_max);
94  if(b0_size <= 0.f || b1_size <= 0.f)
95  {
96  return false;
97  }
98  else
99  {
100  const float box_weight = compute_intersection(b0_min, b0_max, b1_min, b1_max, b0_size, b1_size);
101  return box_weight > threshold;
102  }
103 }
104 
105 inline std::vector<CandidateBox> get_candidates(const SimpleTensor<float> &scores, float threshold)
106 {
107  std::vector<CandidateBox> candidates_vector;
108  for(int i = 0; i < scores.num_elements(); ++i)
109  {
110  if(scores[i] >= threshold)
111  {
112  const auto cb = CandidateBox({ i, scores[i] });
113  candidates_vector.push_back(cb);
114  }
115  }
116  std::stable_sort(candidates_vector.begin(), candidates_vector.end(), [](const CandidateBox bb0, const CandidateBox bb1)
117  {
118  return bb0.second > bb1.second;
119  });
120  return candidates_vector;
121 }
122 
123 inline bool is_box_selected(const CandidateBox &cb, const SimpleTensor<float> &bboxes, std::vector<int> &selected_boxes, float threshold)
124 {
125  for(int j = selected_boxes.size() - 1; j >= 0; --j)
126  {
127  const auto selected_box_jth = get_box(bboxes, selected_boxes[j]);
128  const auto candidate_box = get_box(bboxes, cb.first);
129  const bool candidate_rejected = reject_box(candidate_box, selected_box_jth, threshold);
130  if(candidate_rejected)
131  {
132  return false;
133  }
134  }
135  return true;
136 }
137 } // namespace
138 
140  unsigned int max_output_size, float score_threshold, float nms_threshold)
141 {
142  const size_t num_boxes = bboxes.shape().y();
143  const size_t output_size = std::min(static_cast<size_t>(max_output_size), num_boxes);
144  const std::vector<CandidateBox> candidates_vector = get_candidates(scores, score_threshold);
145  std::vector<int> selected;
146  for(const auto &c : candidates_vector)
147  {
148  if(selected.size() == output_size)
149  {
150  break;
151  }
152  if(is_box_selected(c, bboxes, selected, nms_threshold))
153  {
154  selected.push_back(c.first);
155  }
156  }
157  std::copy_n(selected.begin(), selected.size(), indices.data());
158 
159  for(unsigned int i = selected.size(); i < max_output_size; ++i)
160  {
161  indices[i] = -1;
162  }
163 
164  return indices;
165 }
166 } // namespace reference
167 } // namespace validation
168 } // namespace test
169 } // namespace arm_compute
SimpleTensor< float > b
Definition: DFT.cpp:157
TensorShape shape() const override
Shape of the tensor.
Definition: SimpleTensor.h:320
Copyright (c) 2017-2021 Arm Limited.
Simple tensor object that stores elements in a consecutive chunk of memory.
Definition: SimpleTensor.h:58
SimpleTensor< int > non_max_suppression(const SimpleTensor< float > &bboxes, const SimpleTensor< float > &scores, SimpleTensor< int > &indices, unsigned int max_output_size, float score_threshold, float nms_threshold)
const T * data() const
Constant pointer to the underlying buffer.
Definition: SimpleTensor.h:418