nms.py

"""

Fast non-maximum suppression numpy port

from:
http://quantombone.blogspot.com/2011/08/blazing-fast-nmsm-from-exemplar-svm.html

"""
import numpy as np

def nms(boxes, overlap):
    """
    original code: http://github.com/quantombone/exemplarsvm/internal/esvm_nms.m
    
    """
    if boxes.size==0: return []
    
    x1 = boxes[:,0]
    y1 = boxes[:,1]
    x2 = boxes[:,2]
    y2 = boxes[:,3]
    s = boxes[:,-1]
    
    area = (x2-x1+1) * (y2-y1+1)

    I = np.argsort(s)
    
    pick = np.zeros(s.size, dtype=np.int)
    counter = 0

    while I.size > 0:
        last = I.size-1
        i = I[-1]
        pick[counter] = i
        counter += 1
        
        xx1 = np.maximum(x1[i], x1[I[:-1]])
        yy1 = np.maximum(y1[i], y1[I[:-1]])
        xx2 = np.minimum(x2[i], x2[I[:-1]])
        yy2 = np.minimum(y2[i], y2[I[:-1]])

        w = np.maximum(0.0, xx2 - xx1 + 1)
        h = np.maximum(0.0, yy2 - yy1 + 1)

        o = w*h / area[I[:-1]]

        I = np.delete(I, np.concatenate([[last], np.nonzero(o > overlap)[0]]))
        
    pick = pick[:counter]
    top = boxes[pick,:]
    
    return top
    
def test_nms():
    """
    returns
    """
    return (nms(np.array([
                                    [0, 0, 10, 10, 0.5],
                                    [1, 1, 10, 10, 0.4],
                                    [20, 20, 40, 40, 0.3],
                                    [20, 20, 40, 30, 0.4],
                                    [15, 20, 40, 40, 0.1]
                        ]), 0.4) == np.array([ [0, 0, 10, 10, 0.5], [20, 20, 40, 30, 0.4] ])).all()
    
if __name__ == "__main__":
    assert(test_nms())