ArmNN
 24.08
DetectionPostProcess.cpp
Go to the documentation of this file.
1 //
2 // Copyright © 2017, 2024 Arm Ltd. All rights reserved.
3 // SPDX-License-Identifier: MIT
4 //
5 
7 
9 
10 #include <algorithm>
11 #include <numeric>
12 
13 namespace armnn
14 {
15 
16 std::vector<unsigned int> GenerateRangeK(unsigned int k)
17 {
18  std::vector<unsigned int> range(k);
19  std::iota(range.begin(), range.end(), 0);
20  return range;
21 }
22 
23 void TopKSort(unsigned int k, unsigned int* indices, const float* values, unsigned int numElement)
24 {
25  std::partial_sort(indices, indices + k, indices + numElement,
26  [&values](unsigned int i, unsigned int j) { return values[i] > values[j]; });
27 }
28 
29 float IntersectionOverUnion(const float* boxI, const float* boxJ)
30 {
31  // Box-corner format: ymin, xmin, ymax, xmax.
32  const int yMin = 0;
33  const int xMin = 1;
34  const int yMax = 2;
35  const int xMax = 3;
36  float areaI = (boxI[yMax] - boxI[yMin]) * (boxI[xMax] - boxI[xMin]);
37  float areaJ = (boxJ[yMax] - boxJ[yMin]) * (boxJ[xMax] - boxJ[xMin]);
38  float yMinIntersection = std::max(boxI[yMin], boxJ[yMin]);
39  float xMinIntersection = std::max(boxI[xMin], boxJ[xMin]);
40  float yMaxIntersection = std::min(boxI[yMax], boxJ[yMax]);
41  float xMaxIntersection = std::min(boxI[xMax], boxJ[xMax]);
42  float areaIntersection = std::max(yMaxIntersection - yMinIntersection, 0.0f) *
43  std::max(xMaxIntersection - xMinIntersection, 0.0f);
44  float areaUnion = areaI + areaJ - areaIntersection;
45  return areaIntersection / areaUnion;
46 }
47 
48 std::vector<unsigned int> NonMaxSuppression(unsigned int numBoxes,
49  const std::vector<float>& boxCorners,
50  const std::vector<float>& scores,
51  float nmsScoreThreshold,
52  unsigned int maxDetection,
53  float nmsIouThreshold)
54 {
55  // Select boxes that have scores above a given threshold.
56  std::vector<float> scoresAboveThreshold;
57  std::vector<unsigned int> indicesAboveThreshold;
58  for (unsigned int i = 0; i < numBoxes; ++i)
59  {
60  if (scores[i] >= nmsScoreThreshold)
61  {
62  scoresAboveThreshold.push_back(scores[i]);
63  indicesAboveThreshold.push_back(i);
64  }
65  }
66 
67  // Sort the indices based on scores.
68  unsigned int numAboveThreshold = armnn::numeric_cast<unsigned int>(scoresAboveThreshold.size());
69  std::vector<unsigned int> sortedIndices = GenerateRangeK(numAboveThreshold);
70  TopKSort(numAboveThreshold, sortedIndices.data(), scoresAboveThreshold.data(), numAboveThreshold);
71 
72  // Number of output cannot be more than max detections specified in the option.
73  unsigned int numOutput = std::min(maxDetection, numAboveThreshold);
74  std::vector<unsigned int> outputIndices;
75  std::vector<bool> visited(numAboveThreshold, false);
76 
77  // Prune out the boxes with high intersection over union by keeping the box with higher score.
78  for (unsigned int i = 0; i < numAboveThreshold; ++i)
79  {
80  if (outputIndices.size() >= numOutput)
81  {
82  break;
83  }
84  if (!visited[sortedIndices[i]])
85  {
86  outputIndices.push_back(indicesAboveThreshold[sortedIndices[i]]);
87  for (unsigned int j = i + 1; j < numAboveThreshold; ++j)
88  {
89  unsigned int iIndex = indicesAboveThreshold[sortedIndices[i]] * 4;
90  unsigned int jIndex = indicesAboveThreshold[sortedIndices[j]] * 4;
91  if (IntersectionOverUnion(&boxCorners[iIndex], &boxCorners[jIndex]) > nmsIouThreshold)
92  {
93  visited[sortedIndices[j]] = true;
94  }
95  }
96  }
97  }
98  return outputIndices;
99 }
100 
101 void AllocateOutputData(unsigned int numOutput,
102  unsigned int numSelected,
103  const std::vector<float>& boxCorners,
104  const std::vector<unsigned int>& outputIndices,
105  const std::vector<unsigned int>& selectedBoxes,
106  const std::vector<unsigned int>& selectedClasses,
107  const std::vector<float>& selectedScores,
108  float* detectionBoxes,
109  float* detectionScores,
110  float* detectionClasses,
111  float* numDetections)
112 {
113  for (unsigned int i = 0; i < numOutput; ++i)
114  {
115  unsigned int boxIndex = i * 4;
116  if (i < numSelected)
117  {
118  unsigned int boxCornorIndex = selectedBoxes[outputIndices[i]] * 4;
119  detectionScores[i] = selectedScores[outputIndices[i]];
120  detectionClasses[i] = armnn::numeric_cast<float>(selectedClasses[outputIndices[i]]);
121  detectionBoxes[boxIndex] = boxCorners[boxCornorIndex];
122  detectionBoxes[boxIndex + 1] = boxCorners[boxCornorIndex + 1];
123  detectionBoxes[boxIndex + 2] = boxCorners[boxCornorIndex + 2];
124  detectionBoxes[boxIndex + 3] = boxCorners[boxCornorIndex + 3];
125  }
126  else
127  {
128  detectionScores[i] = 0.0f;
129  detectionClasses[i] = 0.0f;
130  detectionBoxes[boxIndex] = 0.0f;
131  detectionBoxes[boxIndex + 1] = 0.0f;
132  detectionBoxes[boxIndex + 2] = 0.0f;
133  detectionBoxes[boxIndex + 3] = 0.0f;
134  }
135  }
136  numDetections[0] = armnn::numeric_cast<float>(numSelected);
137 }
138 
139 void DetectionPostProcess(const TensorInfo& boxEncodingsInfo,
140  const TensorInfo& scoresInfo,
141  const TensorInfo&,
142  const TensorInfo& detectionBoxesInfo,
143  const TensorInfo&,
144  const TensorInfo&,
145  const TensorInfo&,
146  const DetectionPostProcessDescriptor& desc,
147  Decoder<float>& boxEncodings,
148  Decoder<float>& scores,
149  Decoder<float>& anchors,
150  float* detectionBoxes,
151  float* detectionClasses,
152  float* detectionScores,
153  float* numDetections)
154 {
155 
156  // Transform center-size format which is (ycenter, xcenter, height, width) to box-corner format,
157  // which represents the lower left corner and the upper right corner (ymin, xmin, ymax, xmax)
158  std::vector<float> boxCorners(boxEncodingsInfo.GetNumElements());
159 
160  const unsigned int numBoxes = boxEncodingsInfo.GetShape()[1];
161  const unsigned int numScores = scoresInfo.GetNumElements();
162 
163  for (unsigned int i = 0; i < numBoxes; ++i)
164  {
165  // Y
166  float boxEncodingY = boxEncodings.Get();
167  float anchorY = anchors.Get();
168 
169  ++boxEncodings;
170  ++anchors;
171 
172  // X
173  float boxEncodingX = boxEncodings.Get();
174  float anchorX = anchors.Get();
175 
176  ++boxEncodings;
177  ++anchors;
178 
179  // H
180  float boxEncodingH = boxEncodings.Get();
181  float anchorH = anchors.Get();
182 
183  ++boxEncodings;
184  ++anchors;
185 
186  // W
187  float boxEncodingW = boxEncodings.Get();
188  float anchorW = anchors.Get();
189 
190  ++boxEncodings;
191  ++anchors;
192 
193  float yCentre = boxEncodingY / desc.m_ScaleY * anchorH + anchorY;
194  float xCentre = boxEncodingX / desc.m_ScaleX * anchorW + anchorX;
195 
196  float halfH = 0.5f * expf(boxEncodingH / desc.m_ScaleH) * anchorH;
197  float halfW = 0.5f * expf(boxEncodingW / desc.m_ScaleW) * anchorW;
198 
199  unsigned int indexY = i * 4;
200  unsigned int indexX = indexY + 1;
201  unsigned int indexH = indexX + 1;
202  unsigned int indexW = indexH + 1;
203 
204  // ymin
205  boxCorners[indexY] = yCentre - halfH;
206  // xmin
207  boxCorners[indexX] = xCentre - halfW;
208  // ymax
209  boxCorners[indexH] = yCentre + halfH;
210  // xmax
211  boxCorners[indexW] = xCentre + halfW;
212  }
213 
214  unsigned int numClassesWithBg = desc.m_NumClasses + 1;
215 
216  // Decode scores
217  std::vector<float> decodedScores;
218  decodedScores.reserve(numScores);
219 
220  for (unsigned int i = 0u; i < numScores; ++i)
221  {
222  decodedScores.emplace_back(scores.Get());
223  ++scores;
224  }
225 
226  // Perform Non Max Suppression.
227  if (desc.m_UseRegularNms)
228  {
229  // Perform Regular NMS.
230  // For each class, perform NMS and select max detection numbers of the highest score across all classes.
231  std::vector<float> classScores(numBoxes);
232 
233  std::vector<unsigned int> selectedBoxesAfterNms;
234  selectedBoxesAfterNms.reserve(numBoxes);
235 
236  std::vector<float> selectedScoresAfterNms;
237  selectedBoxesAfterNms.reserve(numScores);
238 
239  std::vector<unsigned int> selectedClasses;
240 
241  for (unsigned int c = 0; c < desc.m_NumClasses; ++c)
242  {
243  // For each boxes, get scores of the boxes for the class c.
244  for (unsigned int i = 0; i < numBoxes; ++i)
245  {
246  classScores[i] = decodedScores[i * numClassesWithBg + c + 1];
247  }
248  std::vector<unsigned int> selectedIndices = NonMaxSuppression(numBoxes,
249  boxCorners,
250  classScores,
251  desc.m_NmsScoreThreshold,
253  desc.m_NmsIouThreshold);
254 
255  for (unsigned int i = 0; i < selectedIndices.size(); ++i)
256  {
257  selectedBoxesAfterNms.push_back(selectedIndices[i]);
258  selectedScoresAfterNms.push_back(classScores[selectedIndices[i]]);
259  selectedClasses.push_back(c);
260  }
261  }
262 
263  // Select max detection numbers of the highest score across all classes
264  unsigned int numSelected = armnn::numeric_cast<unsigned int>(selectedBoxesAfterNms.size());
265  unsigned int numOutput = std::min(desc.m_MaxDetections, numSelected);
266 
267  // Sort the max scores among the selected indices.
268  std::vector<unsigned int> outputIndices = GenerateRangeK(numSelected);
269  TopKSort(numOutput, outputIndices.data(), selectedScoresAfterNms.data(), numSelected);
270 
271  AllocateOutputData(detectionBoxesInfo.GetShape()[1], numOutput, boxCorners, outputIndices,
272  selectedBoxesAfterNms, selectedClasses, selectedScoresAfterNms,
273  detectionBoxes, detectionScores, detectionClasses, numDetections);
274  }
275  else
276  {
277  // Perform Fast NMS.
278  // Select max scores of boxes and perform NMS on max scores,
279  // select max detection numbers of the highest score
280  unsigned int numClassesPerBox = std::min(desc.m_MaxClassesPerDetection, desc.m_NumClasses);
281  std::vector<float> maxScores;
282  std::vector<unsigned int>boxIndices;
283  std::vector<unsigned int>maxScoreClasses;
284 
285  for (unsigned int box = 0; box < numBoxes; ++box)
286  {
287  unsigned int scoreIndex = box * numClassesWithBg + 1;
288 
289  // Get the max scores of the box.
290  std::vector<unsigned int> maxScoreIndices = GenerateRangeK(desc.m_NumClasses);
291  TopKSort(numClassesPerBox, maxScoreIndices.data(),
292  decodedScores.data() + scoreIndex, desc.m_NumClasses);
293 
294  for (unsigned int i = 0; i < numClassesPerBox; ++i)
295  {
296  maxScores.push_back(decodedScores[scoreIndex + maxScoreIndices[i]]);
297  maxScoreClasses.push_back(maxScoreIndices[i]);
298  boxIndices.push_back(box);
299  }
300  }
301 
302  // Perform NMS on max scores
303  std::vector<unsigned int> selectedIndices = NonMaxSuppression(numBoxes, boxCorners, maxScores,
304  desc.m_NmsScoreThreshold,
305  desc.m_MaxDetections,
306  desc.m_NmsIouThreshold);
307 
308  unsigned int numSelected = armnn::numeric_cast<unsigned int>(selectedIndices.size());
309  unsigned int numOutput = std::min(desc.m_MaxDetections, numSelected);
310 
311  AllocateOutputData(detectionBoxesInfo.GetShape()[1], numOutput, boxCorners, selectedIndices,
312  boxIndices, maxScoreClasses, maxScores,
313  detectionBoxes, detectionScores, detectionClasses, numDetections);
314  }
315 }
316 
317 } // namespace armnn
armnn::Decoder< float >
armnn::TensorInfo::GetNumElements
unsigned int GetNumElements() const
Definition: Tensor.hpp:198
armnn::GenerateRangeK
std::vector< unsigned int > GenerateRangeK(unsigned int k)
Definition: DetectionPostProcess.cpp:16
armnn::DetectionPostProcessDescriptor::m_NmsScoreThreshold
float m_NmsScoreThreshold
NMS score threshold.
Definition: Descriptors.hpp:751
armnn::DetectionPostProcessDescriptor::m_ScaleX
float m_ScaleX
Center size encoding scale x.
Definition: Descriptors.hpp:759
armnn::DetectionPostProcessDescriptor::m_ScaleY
float m_ScaleY
Center size encoding scale y.
Definition: Descriptors.hpp:761
armnn::DetectionPostProcessDescriptor::m_MaxDetections
uint32_t m_MaxDetections
Maximum numbers of detections.
Definition: Descriptors.hpp:745
armnn::TensorInfo
Definition: Tensor.hpp:152
armnn::AllocateOutputData
void AllocateOutputData(unsigned int numOutput, unsigned int numSelected, const std::vector< float > &boxCorners, const std::vector< unsigned int > &outputIndices, const std::vector< unsigned int > &selectedBoxes, const std::vector< unsigned int > &selectedClasses, const std::vector< float > &selectedScores, float *detectionBoxes, float *detectionScores, float *detectionClasses, float *numDetections)
Definition: DetectionPostProcess.cpp:101
armnn::DetectionPostProcessDescriptor::m_ScaleW
float m_ScaleW
Center size encoding scale weight.
Definition: Descriptors.hpp:763
armnn::DetectionPostProcessDescriptor::m_MaxClassesPerDetection
uint32_t m_MaxClassesPerDetection
Maximum numbers of classes per detection, used in Fast NMS.
Definition: Descriptors.hpp:747
NumericCast.hpp
armnn::IntersectionOverUnion
float IntersectionOverUnion(const float *boxI, const float *boxJ)
Definition: DetectionPostProcess.cpp:29
armnn::DetectionPostProcessDescriptor::m_NumClasses
uint32_t m_NumClasses
Number of classes.
Definition: Descriptors.hpp:755
armnn::DetectionPostProcessDescriptor::m_NmsIouThreshold
float m_NmsIouThreshold
Intersection over union threshold.
Definition: Descriptors.hpp:753
armnn::DetectionPostProcessDescriptor::m_DetectionsPerClass
uint32_t m_DetectionsPerClass
Detections per classes, used in Regular NMS.
Definition: Descriptors.hpp:749
armnn::DetectionPostProcessDescriptor::m_ScaleH
float m_ScaleH
Center size encoding scale height.
Definition: Descriptors.hpp:765
armnn::Decoder::Get
virtual IType Get() const =0
armnn::TensorInfo::GetShape
const TensorShape & GetShape() const
Definition: Tensor.hpp:193
armnn
Copyright (c) 2021 ARM Limited and Contributors.
Definition: 01_00_quick_start.dox:6
armnn::TopKSort
void TopKSort(unsigned int k, unsigned int *indices, const float *values, unsigned int numElement)
Definition: DetectionPostProcess.cpp:23
armnn::DetectionPostProcessDescriptor::m_UseRegularNms
bool m_UseRegularNms
Use Regular NMS.
Definition: Descriptors.hpp:757
armnn::NonMaxSuppression
std::vector< unsigned int > NonMaxSuppression(unsigned int numBoxes, const std::vector< float > &boxCorners, const std::vector< float > &scores, float nmsScoreThreshold, unsigned int maxDetection, float nmsIouThreshold)
Definition: DetectionPostProcess.cpp:48
armnn::DetectionPostProcessDescriptor
Definition: Descriptors.hpp:713
DetectionPostProcess.hpp
armnn::DetectionPostProcess
void DetectionPostProcess(const TensorInfo &boxEncodingsInfo, const TensorInfo &scoresInfo, const TensorInfo &, const TensorInfo &detectionBoxesInfo, const TensorInfo &, const TensorInfo &, const TensorInfo &, const DetectionPostProcessDescriptor &desc, Decoder< float > &boxEncodings, Decoder< float > &scores, Decoder< float > &anchors, float *detectionBoxes, float *detectionClasses, float *detectionScores, float *numDetections)
Definition: DetectionPostProcess.cpp:139