:py:mod:`kwimage.algo` ====================== .. py:module:: kwimage.algo .. autoapi-nested-parse:: mkinit ~/code/kwimage/kwimage/algo/__init__.py -w --relative Subpackages ----------- .. toctree:: :titlesonly: :maxdepth: 3 _nms_backend/index.rst Submodules ---------- .. toctree:: :titlesonly: :maxdepth: 1 algo_nms/index.rst Package Contents ---------------- Functions ~~~~~~~~~ .. autoapisummary:: kwimage.algo.available_nms_impls kwimage.algo.daq_spatial_nms kwimage.algo.non_max_supression .. py:function:: available_nms_impls() List available values for the `impl` kwarg of `non_max_supression` CommandLine: xdoctest -m kwimage.algo.algo_nms available_nms_impls .. rubric:: Example >>> impls = available_nms_impls() >>> assert 'numpy' in impls >>> print('impls = {!r}'.format(impls)) .. py:function:: daq_spatial_nms(ltrb, 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: * **ltrb** (*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 .. rubric:: 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 >>> # >>> ltrb = boxes.to_ltrb().data.astype(np.float32) >>> scores = np.arange(0, len(ltrb)).astype(np.float32) >>> # >>> n_megabytes = (ltrb.size * ltrb.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(ltrb, 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(ltrb, 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)) .. py:function:: non_max_supression(ltrb, scores, thresh, bias=0.0, classes=None, impl='auto', device_id=None) Non-Maximum Suppression - remove redundant bounding boxes :Parameters: * **ltrb** (*ndarray[float32]*) -- Nx4 boxes in ltrb 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", "gpu", "torch", or "torchvision". * **device_id** (*int*) -- used if impl is gpu, device id to work on. If not specified `torch.cuda.current_device()` is used. .. rubric:: 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. .. rubric:: 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 .. rubric:: Example >>> from kwimage.algo.algo_nms import * >>> from kwimage.algo.algo_nms import _impls >>> ltrb = 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(ltrb, scores, thresh=0.5, impl='numpy') >>> print('keep = {!r}'.format(keep)) >>> assert keep == [2, 1, 3] >>> thresh = 0.0 >>> non_max_supression(ltrb, scores, thresh, impl='numpy') >>> if 'numpy' in available_nms_impls(): >>> keep = non_max_supression(ltrb, scores, thresh, impl='numpy') >>> assert list(keep) == [2, 1] >>> if 'cython_cpu' in available_nms_impls(): >>> keep = non_max_supression(ltrb, scores, thresh, impl='cython_cpu') >>> assert list(keep) == [2, 1] >>> if 'cython_gpu' in available_nms_impls(): >>> keep = non_max_supression(ltrb, scores, thresh, impl='cython_gpu') >>> assert list(keep) == [2, 1] >>> if 'torch' in available_nms_impls(): >>> keep = non_max_supression(ltrb, scores, thresh, impl='torch') >>> assert set(keep.tolist()) == {2, 1} >>> if 'torchvision' in available_nms_impls(): >>> keep = non_max_supression(ltrb, 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(ltrb, scores, thresh, impl='numpy') >>> assert list(keep) == [2, 1, 3, 0] >>> if 'cython_cpu' in available_nms_impls(): >>> keep = non_max_supression(ltrb, scores, thresh, impl='cython_cpu') >>> assert list(keep) == [2, 1, 3, 0] >>> if 'cython_gpu' in available_nms_impls(): >>> keep = non_max_supression(ltrb, scores, thresh, impl='cython_gpu') >>> assert list(keep) == [2, 1, 3, 0] >>> if 'torch' in available_nms_impls(): >>> keep = non_max_supression(ltrb, scores, thresh, impl='torch') >>> assert set(keep.tolist()) == {2, 1, 3, 0} >>> if 'torchvision' in available_nms_impls(): >>> keep = non_max_supression(ltrb, scores, thresh, impl='torchvision') # note torchvision has no bias >>> assert set(kwarray.ArrayAPI.tolist(keep)) == {2, 1, 3, 0} .. rubric:: Example >>> import ubelt as ub >>> ltrb = 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(ltrb)) >>> thresh = .2 >>> solutions = {} >>> if not _impls._funcs: >>> _impls._lazy_init() >>> for impl in _impls._funcs: >>> keep = non_max_supression(ltrb, 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 .. rubric:: Example >>> import ubelt as ub >>> # Check that zero-area boxes are ok >>> ltrb = 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(ltrb, 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())