API Reference¶
NMS¶
- lsnms.nms(boxes, scores, iou_threshold=0.5, score_threshold=0.0, class_ids=None, rtree_leaf_size=32, backend=Backend.RUST)[source]¶
Run the CPU-based sparse NMS algorithm.
The implementation uses rectangular tree (R-Tree) for efficient querying of overlapping boxes. Note that in the case of “natural” images (< 20 detected objects in the image) or very low redundancy in the detection, a naive algorithm will likely be faster (even more if GPU based).
This implementation becomes increasingly useful as the number of objects grows, as its complexity is O(n log n) rather than O(n**2) for vanilla NMS. Typical use cases are object detection algorithms ran in a sliding overlapping windows fashion. A vanilla NMS algorithm can be ran window-wise, but because windows do overlap (to accomodate for side effects), a final NMS pass is required. This is where sparse NMS shines.
Satellite aerial or microscopy images can easily produce hundreds of thousands of detected objects per image, making torch’s GPU implementation run out of memory, and torch’s CPU implementation very time consuming.
Note: the Rust and Numba backends do not provide the exact same algorithm. Rust is expected to be faster in most cases, on top of not requiring the JIT compilation that Numba does. Results shall match in both cases.
```python3 boxes = # array of boxes in format pascal VOC (x0, y0, x1, y1) scores = # one-dimensional array of confidence scores
keep = nms(boxes, scores, iou_threshold=0.5, score_threshold=0.) ``` or ```python3 boxes = # array of boxes in format pascal VOC (x0, y0, x1, y1) scores = # one-dimensional array of confidence scores class_ids = # one-dimensional array of class indicators (one per object)
keep = nms(boxes, scores, iou_threshold=0.5, score_threshold=0., class_ids=class_ids) ```
Note that this implementation could be further optimized: - Memory management is quite poor: several back and forth list-to-numpy conversions happen - Some multi treading could be injected when comparing far appart clusters
- Parameters:
boxes (np.array) – Array of boxes, in format (x0, y0, x1, y1) with x1 >= x0, y1 >= y0
scores (np.array) – One-dimensional array of confidence scores. Note that in the case of multiclass, this function must be applied class-wise.
iou_threshold (float, optional) – Threshold used to consider two boxes to be overlapping, by default 0.5
score_threshold (float, optional) – Threshold from which boxes are discarded, by default 0.0
class_ids (np.array, optional) – One-dimensional integer array indicating the respective classes of the bboxes. If this is not None, a class-wise NMS will be applied. If None, all boxes are considered of the same class.
rtree_leaf_size (int, optional) – The leaf size parameter of the underlying R-Tree built for box query.
backend (str|Backend, optional) – The backend to use for NMS computation. Can be one of ‘numba’ or ‘rust’. By default, ‘rust’.
- Returns:
Indices of boxes kept, in decreasing order of confidence score.
- Return type:
np.array
WBC¶
- lsnms.wbc(boxes, scores, iou_threshold=0.5, score_threshold=0.0, iou_reweight=False, cutoff_distance=None, tree=None)[source]¶
Sparse Weighted box clustering loosely inspired from https://arxiv.org/pdf/1811.08661.pdf. For a given bbox, instead of discarding all other overlapping bboxes with lower score, it aggregates them all (overlapping bboxes which have not already been aggregated) by averaging confidence scores and box coordinates.
It returns a tuple of: - the cluster boxes (pooled coordinates per cluster) - the cluster score (pooled score per cluster) - the cluster indices: for each cluster, a tuple containing:
index of the highest scoring box in the cluster
(the box onto which other boxes were pulled toward) - indices of all other boxes (including the highest one) pulled in the cluster
Note that this implementation could be further optimized: - Memory management is quite poor: several back and forth list-to-numpy conversions happen - Some multi treading could be injected when comparing far appart clusters
- Parameters:
boxes (np.array) – Array of boxes, in format (x0, y0, x1, y1) with x1 >= x0, y1 >= y0
scores (np.array) – One-dimensional array of confidence scores.
iou_threshold (float, optional) – Threshold from which boxes are considered to overlap, and end up aggregated, by default 0.5 The higher the lower the effect of this operation.
score_threshold (float, optional) – Score from which to discard instance based on this confidence score, by default 0.1
iou_reweight (bool, optional) – Enable IoU reweighting when computing instance consensus, by default False If set to true, for each box, the higher the IoU with the highest scoring box of the cluster, the higher it will contribute to the global (coordinates and scores) consensus.
cutoff_distance (int, optional) – DEPRECATED, used for compatibility with version 0.1.X. Since version 0.2.X, it is useless because overlapping boxes are queried using a R-Tree, which is parameter free.
tree (str, optional) – DEPRECATED, used for compatibility with version 0.1.X. Since version 0.2.X, the tree used is a R-Tree.
- Returns:
Pooled boxes, pooled scores, cluster indices
- Return type:
Tuple[np.array]
R-Tree¶
- class lsnms.rtree.RTree(*args, **kwargs)[source]¶
Main object for the R-Tree class: used to find in a log time-complexity the boxes overlapping with a given box.
` tree = RTree(existing_boxes) # Returns indices of relevant boxes and overlap area idxs, overlaps = tree.intersect(new_box) `- Parameters:
X (np.array) – 2-dimensional float64 numpy array of boxes to index
leaf_size (int) – Leaf size of the tree. Region size at which the space stops being sub-divised.
- class_type = jitclass.RTree#7f66b671bb10<_root:DeferredType#140079126216976,data:array(float64, 2d, A)>¶
- class lsnms.rtree.RNode(*args, **kwargs)[source]¶
Main object for the node class.
Note that the tree building process is peculiar: Since jit classes methods can not be recursive (node.method can not call node.method), the tree building process (recursive node splitting and children instanciation) can not be done inside the RNode.__init__ method (which is the natural way to do so). However, jit classes methods can call recursive functions: hence, the tree building process is delegated to an independant function (see build function). Consequently, this class must be used in the following way:
` # Instanciate the root node node = RNode(data) # Reccursively attach children to each node node.build() `For convenience, a wrapper RTree class was implemented, encapsulating this process:
` tree = RTree(data) # or tree.intersect(box_of_interest) `- class_type = jitclass.RNode#7f66b67180d0<data:array(float64, 2d, A),bbox:array(float64, 1d, A),axis:int64,dimensionality:int64,indices:OptionalType(array(int64, 1d, A)),is_leaf:bool,leaf_size:int64,left:OptionalType(DeferredType#140079126216976),right:OptionalType(DeferredType#140079126216976)>¶
Utilities¶
- lsnms.util.offset_bboxes(bboxes, class_ids)[source]¶
Function used to offset bboxes of different classes so that boxes of different classes do not overlap. This is the trick used in multiclass NMS standardly.
The only peculiarity here is that in a regular NMS setup, boxes can be offseted “diagonally”. i.e. all pushed along a diagonal, something like:
` max_offset = bboxes[2:].max() offset = class_id * max_offset `To create a “diagonal per block” aspect.Note that this would hurt performances because the underlying RTree that we would build on this would be suboptimal: many regions would actually be empty (because RTree builds rectangular regions) and the query time would be impacted.
Instead, here the boxes are offseted forming a “mosaic” of class-wise regions, see figures in readme.
Note that this function is completely dimensionality agnostic.
- Parameters:
bboxes (np.array) – Array of bboxes in VOC format
class_ids (np.array) – One-dimensional array of integers class identifiers.
- Returns:
New array of bounding boxes, offseted class-wise.
- Return type:
np.array