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