Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 1 | /* |
Matthew Bentham | 6d76e4d | 2020-06-01 15:53:21 +0100 | [diff] [blame] | 2 | * Copyright (c) 2019-2020 ARM Limited. |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 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" |
| 27 | #include "tests/validation/Helpers.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 | |
Pablo Tello | 6e61794 | 2019-02-27 13:32:51 +0000 | [diff] [blame] | 56 | // returns a pair (minX, minY) |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 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 | } |
Pablo Tello | 6e61794 | 2019-02-27 13:32:51 +0000 | [diff] [blame] | 63 | // returns a pair (maxX, maxY) |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 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 | { |
Isabella Gottardi | 883bad7 | 2019-07-15 17:33:07 +0100 | [diff] [blame] | 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, |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 80 | b1_max.second) |
| 81 | - std::max<float>(b0_min.second, b1_min.second), |
Isabella Gottardi | 883bad7 | 2019-07-15 17:33:07 +0100 | [diff] [blame] | 82 | 0.0f); |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 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 | { |
Pablo Tello | 6e61794 | 2019-02-27 13:32:51 +0000 | [diff] [blame] | 100 | const float box_weight = compute_intersection(b0_min, b0_max, b1_min, b1_max, b0_size, b1_size); |
| 101 | return box_weight > threshold; |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 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 | { |
Isabella Gottardi | 883bad7 | 2019-07-15 17:33:07 +0100 | [diff] [blame] | 110 | if(scores[i] >= threshold) |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 111 | { |
| 112 | const auto cb = CandidateBox({ i, scores[i] }); |
| 113 | candidates_vector.push_back(cb); |
| 114 | } |
| 115 | } |
Pablo Tello | 6e61794 | 2019-02-27 13:32:51 +0000 | [diff] [blame] | 116 | std::stable_sort(candidates_vector.begin(), candidates_vector.end(), [](const CandidateBox bb0, const CandidateBox bb1) |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 117 | { |
Isabella Gottardi | 883bad7 | 2019-07-15 17:33:07 +0100 | [diff] [blame] | 118 | return bb0.second > bb1.second; |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 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 | { |
Pablo Tello | 6e61794 | 2019-02-27 13:32:51 +0000 | [diff] [blame] | 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) |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 131 | { |
| 132 | return false; |
| 133 | } |
| 134 | } |
| 135 | return true; |
| 136 | } |
| 137 | } // namespace |
| 138 | |
| 139 | SimpleTensor<int> non_max_suppression(const SimpleTensor<float> &bboxes, const SimpleTensor<float> &scores, SimpleTensor<int> &indices, |
| 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; |
Matthew Bentham | 6d76e4d | 2020-06-01 15:53:21 +0100 | [diff] [blame] | 146 | for(const auto &c : candidates_vector) |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 147 | { |
Pablo Tello | 6e61794 | 2019-02-27 13:32:51 +0000 | [diff] [blame] | 148 | if(selected.size() == output_size) |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 149 | { |
Pablo Tello | 6e61794 | 2019-02-27 13:32:51 +0000 | [diff] [blame] | 150 | break; |
| 151 | } |
| 152 | if(is_box_selected(c, bboxes, selected, nms_threshold)) |
| 153 | { |
| 154 | selected.push_back(c.first); |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 155 | } |
| 156 | } |
| 157 | std::copy_n(selected.begin(), selected.size(), indices.data()); |
Isabella Gottardi | 883bad7 | 2019-07-15 17:33:07 +0100 | [diff] [blame] | 158 | |
| 159 | for(unsigned int i = selected.size(); i < max_output_size; ++i) |
| 160 | { |
| 161 | indices[i] = -1; |
| 162 | } |
| 163 | |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 164 | return indices; |
| 165 | } |
Pablo Tello | e96e4f0 | 2018-12-21 16:47:23 +0000 | [diff] [blame] | 166 | } // namespace reference |
| 167 | } // namespace validation |
| 168 | } // namespace test |
| 169 | } // namespace arm_compute |