# Efficient implementation of Non-Maximum Suppression

I would like to know is there is a way to do this:

oneInter[{keep_, rest_, threshold_}] :=
Module[{rest1, keep1},
keep1 = Prepend[keep, rest[[1]]];
rest1 = Delete[rest, 1];
{keep1,
Select[
rest1,
checkCond[First@keep1[[1]], #[[1]]] < threshold &],
threshold}];

result = NestWhile[oneInter, {keep, rest, threshold}, Length @ #[[2]] > 0 &]


in a faster way. Here are some examples on the input

rest = {{{113.562, 132.359, 36.1574, 92.3191, 92.8595},
0.999996}, {{114.71, 107.947, 39.064, 89.5065, 92.5914},
0.999995}, {{67.1904, 125.644, 30.7171, 94.6351, 90.7846},
0.999992}, {{118.388, 104.597, 38.9507, 90.4049, 92.5298},
0.999991}, {{70.6357, 109.998, 33.0017, 107.651, 94.0905},
0.999991}};
threshold = 0.5


As you can see, the rest list is sorted by the second axis. Basically, the rest list contains the coordinates of the rectangles and checkCond computes the intersection area between the pairs of the rectangles. The real size of rest List is 6000 and the final order of the elements in keep does not matter.

Every evaluation of the checkCond takes about 1e-4 and the function is compilable.

I will appreciate any help.

• I think it would be easier to help if you provide an example of the data this operates over and the kind of checkCond you will use. Aug 13, 2018 at 12:28
• A description in words can't hurt either :) Aug 13, 2018 at 12:38
• What is checkCond? Aug 14, 2018 at 23:38
• I second the request for representative examples. We need to know whether rest list is packable? Is it sorted in any way? How many elements does it have? Does order, in which elements in final keep list end-up, matter? Is checkCond compilable? Is it fast compared to other operations in iteration? checkCond[First@keep1[[1]], #[[1]]] < threshold & code seems to give a relation on rest, is this relation transitive? All above details can greatly affect performance. Aug 16, 2018 at 9:16
• I think there is ample info here to work with, so asking people not to close this. Aug 17, 2018 at 15:35

One can do this in a procedural manner. A direct version did not give much (it was about the same speed as the original code). Instead I'll show a method that works only with the list of first (5-tuple) elements. The benefit is one can use Compile and that gives a quite measurable speed gain.

I use a dummy function for the checkCondC. If the max value of the difference of two 5-tuples is less than some threshold, we say the condition fails and do not add the second arg to the list under construction.

This version constructs the list of keepers, and for every new 5-tuple in the original list, tests against keepers before determining whether to add the new on or move on. It is an O(n^2) algorithm but does not have excessive costs from creating/destroying intermediate lists. We simply create an output of the same dimensions as the input, and replace dummy elements by keepers while maintaining a caount of how many keepers we have at any step.

checkCondC =
Compile[{{ll1, _Real, 1}, {ll2, _Real, 1}}, Max[Abs[ll1 - ll2]]];

maxNonintersectingC = Compile[{{ll, _Real, 2}, {eps, _Real}}, Module[
{res = ConstantArray[0., Dimensions[ll]], next, max = 1, good},
res[[1]] = ll[[1]];
Do[
next = ll[[j]];
good =
Catch[Do[
If[checkCondC[res[[k]], next] < eps,
Throw[False]]
, {k, max}];
True];
If[good, max++; res[[max]] = next];
, {j, Length[ll]}];
Take[res, max]
], CompilationOptions -> {"InlineCompiledFunctions" -> True},
CompilationTarget -> "C"];


Now we take a large example.

m = 8000;
inlist = Map[{{1, 1, 1/3, 1, 1}*Most[#], 1/120*Last[#]} &,
RandomReal[{80, 120}, {m, 6}]];


Check that these look a bit like the elements in the original post.

In[282]:= inlist[[1 ;; 3]]

(* Out[282]= {{{114.210179264, 94.9872032272, 30.742668711,
83.7376433634, 119.920328664},
0.928968044627}, {{104.641626332, 92.2701423248, 29.4891773984,
114.993318079, 80.4115524547},
0.960390210004}, {{90.6277601511, 98.6345852935, 30.8461476176,
85.7636679809, 111.535125216}, 0.868401515828}} *)


Timing:

Timing[
mx = Reverse[maxNonintersectingC[inlist[[All, 1]], eps]];]
Length[mx]

(* Out[283]= {0.096, Null}

Out[284]= 512 *)


If we do not compile to C it is still fairly fast, at around 0.27 seconds. By contrast, my pedestrian non-compiled version took around 6.3 seconds.

It is not too difficult to add support for retaining those second elements in the lists. One way would be to feed them in as a separate vark 1 list of reals, Append the jth such element to the jth list when that list is a keeper, and appropriately restructuring after the compiled part is finished.

I think that any gains in performance will have to be squeezed out from the checkCond function-which is not available at the moment. A marginally-if at any-better version of oneInter, that I can think of, is

With[{threshold = 0.5},
selectQ = checkCond[#1, #2] < threshold &
];
select = With[{sel = #2}, Select[#1, selectQ[sel, #] &]] &;
oneInter[{keep_, rest_}] := With[{first = rest[[1]]},
{Flatten[{{first}, keep}, 1], select[Drop[rest, 1], first[[1]]]}]


The differences are more of style than of essence: I've pulled threshold out of the list that NestWhile operates on; I've split the functionality associated with Select into a part that performs the selection (select) and a part that tests for what to select (selectQ); finally, I've disposed of the 'calls' to Prepend and Delete that seemed (to me) superfluous.