Efficient implementation of Non-Maximum Suppression

Question

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.

Answer 1

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.

Answer 2

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.