Fast NMS algorithm suppresses boxes without overlap

Question

I'm testing out the Fast NMS algorithm by Malisiewicz et al. I noticed while running through examples that in one case, if I input two particular boxes that have no overlap, with an IoU threshold below approximately 0.75, one box is suppressed anyway.

Am I misunderstanding NMS? I thought that no boxes should be dropped if there's zero overlap between them, regardless of where the IoU threshold is set.

Example:

import numpy as np

def non_max_suppression_fast(boxes, overlapThresh):

    # if there are no boxes, return an empty list
    if len(boxes) == 0:
        return []

    # initialize the list of picked indexes
    pick = []

    # grab the coordinates of the bounding boxes
    x1 = boxes[:,0]
    y1 = boxes[:,1]
    x2 = boxes[:,2]
    y2 = boxes[:,3]

    # compute the area of the bounding boxes and sort the bounding
    # boxes by the bottom-right y-coordinate of the bounding box
    area = (x2 - x1 + 1) * (y2 - y1 + 1)

    idxs = np.argsort(y2)

    # keep looping while some indexes still remain in the indexes
    # list
    while len(idxs) > 0:
        # grab the last index in the indexes list and add the
        # index value to the list of picked indexes
        last = len(idxs) - 1
        i = idxs[last]
        pick.append(i)

        # find the largest (x, y) coordinates for the start of
        # the bounding box and the smallest (x, y) coordinates
        # for the end of the bounding box
        xx1 = np.maximum(x1[i], x1[idxs[:last]])
        yy1 = np.maximum(y1[i], y1[idxs[:last]])
        xx2 = np.minimum(x2[i], x2[idxs[:last]])
        yy2 = np.minimum(y2[i], y2[idxs[:last]])

        # compute the width and height of the bounding box
        w = np.maximum(0, xx2 - xx1 + 1)
        h = np.maximum(0, yy2 - yy1 + 1)

        # compute the ratio of overlap
        overlap = (w * h) / area[idxs[:last]]

        # delete all indexes from the index list that have
        idxs = np.delete(idxs, np.concatenate(([last],
            np.where(overlap > overlapThresh)[0])))

    # return only the bounding boxes that were picked
    return boxes[pick]


# Two test boxes
                   #xmin,ymin,xmax,ymax
boxes = np.vstack([[0.3, 0.2, 0.4, 0.5], 
                  [0.1, 0.1, 0.2, 0.2]])


# no box suppression
print(non_max_suppression_fast(boxes, overlapThresh=.75))

# one box is suppressed
print(non_max_suppression_fast(boxes, overlapThresh=.74))

Answer 1

your input test case is not legal, argument boxes expect boxes coordinates in absolute format, e.g. in pixel coordinates.

you can notice that when calculating area of all boxes, it is

area = (x2 - x1 + 1) * (y2 - y1 + 1)

the +1 is an added pixel, making sure area is actual number of pixels the box occupies.

try this:

boxes = np.vstack([[3, 2, 4, 5], 
              [1, 1, 2, 2]])