# bbNms

## PURPOSE

Bounding box (bb) non-maximal suppression (nms).

## SYNOPSIS

function bbs = bbNms( bbs, varargin )

## DESCRIPTION

     Bounding box (bb) non-maximal suppression (nms).

     type=='max': nms of bbs using area of overlap criteria. For each pair of
     bbs, if their overlap, defined by:
      overlap(bb1,bb2) = area(intersect(bb1,bb2))/area(union(bb1,bb2))
     is greater than overlap, then the bb with the lower score is suppressed.
     In the Pascal critieria two bbs are considered a match if overlap>=.5. If
     ovrDnm='min', the 'union' in the above formula is replaced with 'min'.

     type=='maxg': Similar to 'max', except performs the nms in a greedy
     fashion. Bbs are processed in order of decreasing score, and, unlike in
     'max' nms, once a bb is suppressed it can no longer suppress other bbs.

     type='cover': Perform nms by attempting to choose the smallest subset of
     the bbs such that each remaining bb is within overlap of one of the
     chosen bbs. The above reduces to the weighted set cover problem which is
     NP but greedy optimization yields provably good solutions. The score of
     each bb is set to the sum of the scores of the bbs it covers (the max can
     also be used). In practice similar to 'maxg'.

     type=='ms': Mean shift nms of bbs with a variable width kernel. radii is
     a 4 element vector (x,y,w,h) that controls the amount of suppression
     along each dim. Typically the first two elements should be the same, as
     should the last two. Distance between w/h are computed in log2 space (ie
     w and w*2 are 1 unit apart), and the radii should be set accordingly.
     radii may need to change depending on spatial and scale stride of bbs.

     Although efficient, this function is O(n^2). To speed things up for large
     n, can divide data randomly into two sets, run nms on each, combine and
     run nms on the result. If maxn is specified, will split the set if
     n>maxn. Note that this is a heuristic and can change the results of nms.

     Finally, the bbs are optionally resized before performing nms. The
     resizing is important as some detectors return bbs that are padded. For
     example, if a detector returns a bounding box of size 128x64 around
     objects of size 100x43 (as is typical for some pedestrian detectors on
     the INRIA pedestrian database), the resize parameters should be {100/128,
     43/64, 0}, see bbApply>resize() for more info.

     USAGE
      bbs = bbNms( bbs, [varargin] )

     INPUTS
      bbs        - original bbs (must be of form [x y w h wt])
      varargin   - additional params (struct or name/value pairs)
       .type       - ['max'] 'max', 'maxg', 'ms', 'cover', or 'none'
       .thr        - [-inf] threshold below which to discard (0 for 'ms')
       .maxn       - [500] if n>maxn split and run recursively (see above)
       .radii      - [.15 .15 1 1] supression radii ('ms' only, see above)
       .overlap    - [.5] area of overlap for bbs
       .ovrDnm     - ['union'] area of overlap denominator ('union' or 'min')
       .resize     - {} parameters for bbApply('resize')

     OUTPUTS
      bbs      - suppressed bbs

     EXAMPLE
      bbs=[0 0 1 1 1; .1 .1 1 1 1.1; 2 2 1 1 1];
      bbs1 = bbNms(bbs, 'type','max' )
      bbs2 = bbNms(bbs, 'thr',.5, 'type','ms')

     See also bbApply, nonMaxSuprList

     Piotr's Image&Video Toolbox      Version 2.42
     Copyright 2010 Piotr Dollar.  [pdollar-at-caltech.edu]
     Please email me if you find bugs, or have suggestions or questions!
     Licensed under the Lesser GPL [see external/lgpl.txt]

## CROSS-REFERENCE INFORMATION

This function calls:

- bbApply Functions for manipulating bounding boxes (bb).
- nonMaxSuprList Applies nonmaximal suppression to a list.
- c clc - clear command window.
- getPrmDflt Helper to set default values (if not already set) of parameter struct.

This function is called by:

- bbGt Bounding box (bb) annotations struct, evaluation and sampling routines.