kwimage.algo

mkinit ~/code/kwimage/kwimage/algo/__init__.py -w –relative

Package Contents

Functions

available_nms_impls() List available values for the impl kwarg of non_max_supression
daq_spatial_nms(tlbr, scores, diameter, thresh, max_depth=6, stop_size=2048, recsize=2048, impl=’auto’, device_id=None) Divide and conquor speedup non-max-supression algorithm for when bboxes
non_max_supression(tlbr, scores, thresh, bias=0.0, classes=None, impl=’auto’, device_id=None) Non-Maximum Suppression - remove redundant bounding boxes
kwimage.algo.available_nms_impls()

List available values for the impl kwarg of non_max_supression

CommandLine:
xdoctest -m kwimage.algo.algo_nms available_nms_impls

Example

>>> impls = available_nms_impls()
>>> assert 'numpy' in impls
>>> print('impls = {!r}'.format(impls))
kwimage.algo.daq_spatial_nms(tlbr, scores, diameter, thresh, max_depth=6, stop_size=2048, recsize=2048, impl='auto', device_id=None)

Divide and conquor speedup non-max-supression algorithm for when bboxes have a known max size

Parameters:
  • tlbr (ndarray) – boxes in (tlx, tly, brx, bry) format
  • scores (ndarray) – scores of each box
  • diameter (int or Tuple[int, int]) – Distance from split point to consider rectification. If specified as an integer, then number is used for both height and width. If specified as a tuple, then dims are assumed to be in [height, width] format.
  • thresh (float) – iou threshold. Boxes are removed if they overlap greater than this threshold. 0 is the most strict, resulting in the fewest boxes, and 1 is the most permissive resulting in the most.
  • max_depth (int) – maximum number of times we can divide and conquor
  • stop_size (int) – number of boxes that triggers full NMS computation
  • recsize (int) – number of boxes that triggers full NMS recombination
  • impl (str) – algorithm to use
LookInfo:

# Didn’t read yet but it seems similar http://www.cyberneum.de/fileadmin/user_upload/files/publications/CVPR2010-Lampert_[0].pdf

https://www.researchgate.net/publication/220929789_Efficient_Non-Maximum_Suppression

# This seems very similar https://projet.liris.cnrs.fr/m2disco/pub/Congres/2006-ICPR/DATA/C03_0406.PDF

Example

>>> import kwimage
>>> # Make a bunch of boxes with the same width and height
>>> #boxes = kwimage.Boxes.random(230397, scale=1000, format='cxywh')
>>> boxes = kwimage.Boxes.random(237, scale=1000, format='cxywh')
>>> boxes.data.T[2] = 10
>>> boxes.data.T[3] = 10
>>> #
>>> tlbr = boxes.to_tlbr().data.astype(np.float32)
>>> scores = np.arange(0, len(tlbr)).astype(np.float32)
>>> #
>>> n_megabytes = (tlbr.size * tlbr.dtype.itemsize) / (2 ** 20)
>>> print('n_megabytes = {!r}'.format(n_megabytes))
>>> #
>>> thresh = iou_thresh = 0.01
>>> impl = 'auto'
>>> max_depth = 20
>>> diameter = 10
>>> stop_size = 2000
>>> recsize = 500
>>> #
>>> import ubelt as ub
>>> #
>>> with ub.Timer(label='daq'):
>>>     keep1 = daq_spatial_nms(tlbr, scores,
>>>         diameter=diameter, thresh=thresh, max_depth=max_depth,
>>>         stop_size=stop_size, recsize=recsize, impl=impl)
>>> #
>>> with ub.Timer(label='full'):
>>>     keep2 = non_max_supression(tlbr, scores,
>>>         thresh=thresh, impl=impl)
>>> #
>>> # Due to the greedy nature of the algorithm, there will be slight
>>> # differences in results, but they will be mostly similar.
>>> similarity = len(set(keep1) & set(keep2)) / len(set(keep1) | set(keep2))
>>> print('similarity = {!r}'.format(similarity))
kwimage.algo.non_max_supression(tlbr, scores, thresh, bias=0.0, classes=None, impl='auto', device_id=None)

Non-Maximum Suppression - remove redundant bounding boxes

Parameters:
  • tlbr (ndarray[float32]) – Nx4 boxes in tlbr format
  • scores (ndarray[float32]) – score for each bbox
  • thresh (float) – iou threshold. Boxes are removed if they overlap greater than this threshold (i.e. Boxes are removed if iou > threshold). Thresh = 0 is the most strict, resulting in the fewest boxes, and 1 is the most permissive resulting in the most.
  • bias (float) – bias for iou computation either 0 or 1
  • classes (ndarray[int64] or None) – integer classes. If specified NMS is done on a perclass basis.
  • impl (str) – implementation can be auto, python, cython_cpu, or gpu
  • device_id (int) – used if impl is gpu, device id to work on. If not specified torch.cuda.current_device() is used.

Notes

Using impl=’cython_gpu’ may result in an CUDA memory error that is not exposed to the python processes. In other words your program will hard crash if impl=’cython_gpu’, and you feed it too many bounding boxes. Ideally this will be fixed in the future.

References

https://github.com/facebookresearch/Detectron/blob/master/detectron/utils/cython_nms.pyx https://www.pyimagesearch.com/2015/02/16/faster-non-maximum-suppression-python/ https://github.com/bharatsingh430/soft-nms/blob/master/lib/nms/cpu_nms.pyx <- TODO

CommandLine:
xdoctest -m ~/code/kwimage/kwimage/algo/algo_nms.py non_max_supression

Example

>>> from kwimage.algo.algo_nms import *
>>> from kwimage.algo.algo_nms import _impls
>>> tlbr = np.array([
>>>     [0, 0, 100, 100],
>>>     [100, 100, 10, 10],
>>>     [10, 10, 100, 100],
>>>     [50, 50, 100, 100],
>>> ], dtype=np.float32)
>>> scores = np.array([.1, .5, .9, .1])
>>> keep = non_max_supression(tlbr, scores, thresh=0.5, impl='numpy')
>>> print('keep = {!r}'.format(keep))
>>> assert keep == [2, 1, 3]
>>> thresh = 0.0
>>> non_max_supression(tlbr, scores, thresh, impl='numpy')
>>> if 'numpy' in available_nms_impls():
>>>     keep = non_max_supression(tlbr, scores, thresh, impl='numpy')
>>>     assert list(keep) == [2, 1]
>>> if 'cython_cpu' in available_nms_impls():
>>>     keep = non_max_supression(tlbr, scores, thresh, impl='cython_cpu')
>>>     assert list(keep) == [2, 1]
>>> if 'cython_gpu' in available_nms_impls():
>>>     keep = non_max_supression(tlbr, scores, thresh, impl='cython_gpu')
>>>     assert list(keep) == [2, 1]
>>> if 'torch' in available_nms_impls():
>>>     keep = non_max_supression(tlbr, scores, thresh, impl='torch')
>>>     assert set(keep.tolist()) == {2, 1}
>>> if 'torchvision' in available_nms_impls():
>>>     keep = non_max_supression(tlbr, scores, thresh, impl='torchvision')  # note torchvision has no bias
>>>     assert list(keep) == [2]
>>> thresh = 1.0
>>> if 'numpy' in available_nms_impls():
>>>     keep = non_max_supression(tlbr, scores, thresh, impl='numpy')
>>>     assert list(keep) == [2, 1, 3, 0]
>>> if 'cython_cpu' in available_nms_impls():
>>>     keep = non_max_supression(tlbr, scores, thresh, impl='cython_cpu')
>>>     assert list(keep) == [2, 1, 3, 0]
>>> if 'cython_gpu' in available_nms_impls():
>>>     keep = non_max_supression(tlbr, scores, thresh, impl='cython_gpu')
>>>     assert list(keep) == [2, 1, 3, 0]
>>> if 'torch' in available_nms_impls():
>>>     keep = non_max_supression(tlbr, scores, thresh, impl='torch')
>>>     assert set(keep.tolist()) == {2, 1, 3, 0}
>>> if 'torchvision' in available_nms_impls():
>>>     keep = non_max_supression(tlbr, scores, thresh, impl='torchvision')  # note torchvision has no bias
>>>     assert set(kwarray.ArrayAPI.tolist(keep)) == {2, 1, 3, 0}

Example

>>> import ubelt as ub
>>> tlbr = np.array([
>>>     [0, 0, 100, 100],
>>>     [100, 100, 10, 10],
>>>     [10, 10, 100, 100],
>>>     [50, 50, 100, 100],
>>>     [100, 100, 150, 101],
>>>     [120, 100, 180, 101],
>>>     [150, 100, 200, 101],
>>> ], dtype=np.float32)
>>> scores = np.linspace(0, 1, len(tlbr))
>>> thresh = .2
>>> solutions = {}
>>> if not _impls._funcs:
>>>     _impls._lazy_init()
>>> for impl in _impls._funcs:
>>>     keep = non_max_supression(tlbr, scores, thresh, impl=impl)
>>>     solutions[impl] = sorted(keep)
>>> assert 'numpy' in solutions
>>> print('solutions = {}'.format(ub.repr2(solutions, nl=1)))
>>> assert ub.allsame(solutions.values())
CommandLine:
xdoctest -m ~/code/kwimage/kwimage/algo/algo_nms.py non_max_supression

Example

>>> import ubelt as ub
>>> # Check that zero-area boxes are ok
>>> tlbr = np.array([
>>>     [0, 0, 0, 0],
>>>     [0, 0, 0, 0],
>>>     [10, 10, 10, 10],
>>> ], dtype=np.float32)
>>> scores = np.array([1, 2, 3], dtype=np.float32)
>>> thresh = .2
>>> solutions = {}
>>> if not _impls._funcs:
>>>     _impls._lazy_init()
>>> for impl in _impls._funcs:
>>>     keep = non_max_supression(tlbr, scores, thresh, impl=impl)
>>>     solutions[impl] = sorted(keep)
>>> assert 'numpy' in solutions
>>> print('solutions = {}'.format(ub.repr2(solutions, nl=1)))
>>> assert ub.allsame(solutions.values())