Locating local maximums

I have used:

result = cv2.matchTemplate(frame, template, cv2.TM_CCORR_NORMED)

to generate this output from a video source:

Screen Shot 2021-02-13 at 09.19.08

What I need now is to get a single (x, y) pair at each local maximum (i.e. at each white dot in the image). What’s the best approach in cv2 to do this? I know the minimum possible distance between a pair of maximums, which should speed the computation.

OpenCV deserves a few routines for non-maximum suppression, in particular for raster data like you have. the “usual” case is that someone has a bunch of bounding boxes that overlap… and that’s a silly situation to get into because half the time they come from raster data as well!

anyway, there’s a simple but tricky way to get NMS using morphological operations.

  1. dilate (grayscale) your accumulator array, use whatever structuring element (None is a 3x3 box kernel) and number of iterations that suit you
  2. pick those locations that are equal between original and this (a mask)

logic: the dilation spreads local maxima. everywhere you’ll know what the maximum within some distance is.

you still have to pick out true/non-zero from that mask but that’s np.nonzero or cv.findNonzero

there are local maxima that aren’t peaks but more like plateaus. if you want to select for a peak shape in addition to that, you could try a median filter and check if the peak is sufficiently above that.

im = cv.imread("76b0dde62ebda812d35d3acfdf8750e55a955705.jpeg", cv.IMREAD_GRAYSCALE)

maxima = cv.dilate(im, None, iterations=20)
med = cv.medianBlur(im, ksize=19)

maxmask = (im == maxima)
medmask = (im.astype(np.int16) >= med.astype(np.int16) + 20) # peak property. avoiding unsigned difference.

mask = maxmask & medmask

canvas = cv.cvtColor(im, cv.COLOR_GRAY2BGR)
#mask = cv.dilate(mask.astype(np.uint8), None, iterations=3) # purely for display

y,x = np.nonzero(mask)
canvas[y,x] = (0,0,255)

cv.imshow("canvas", canvas)

this can and will give you maxima adjacent/nearby to each other if they’re the exact same value.

if they’re really adjacent, you can ignore that if you run findContours or connectedComponents (instead of simply using the x and y from nonzero). if they aren’t… you’d have to deal with it.

possible approach: take a kernel that looks like a filled arc (or box) centered on the pixel, and it covers everything to the top (half) and left (row), but nothing to the bottom (half) and right (row), or something of similar construction. I believe the condition is that the filter, rotated 180 degrees (i.e. flipped along x and y) and laid over itself, must be a partition (apart from the center value which is an implementation choice), i.e. everything covered with no overlap.

function to use would be filter2D

def funnykernel(radius):
    kernel = np.zeros((2*radius+1, 2*radius+1), np.bool)
    kernel[0:radius] = True # top half
    kernel[radius, 0:radius] = True # left half of row
    # center remains False
    # kernel only reacts if there are nearby ones
    return kernel
# use astype(np.uint8) if needed
# multiply by np.uint8(255) if needed

dst = cv.filter2D(...)
mask &= (dst == 0) # nonzero results indicate nearby peak -> suppress

if the applied filter sees not just the mask pixel itself but others in that area (check resulting value), it’s dominated and gets ignored. the kernel shape is important and tricky to get right for consistent results. if it’s wrong, you could be removing both of two points where just one should be removed.

You correctly anticipated my use case! The call to templateMatch()is the first step to a canonical “locate and track” video system, and of course a plethora of overlapping bounding boxes slows things down immensely.

Your answer has been super helpful in introducing me to more OpenCV techniques. What I ended up doing was using findContours() on the thresholded image:

# read in color image and create a grayscale copy
im = cv.imread("image.png")
img = cv.cvtColor(im, cv.COLOR_BGR2GRAY)

# apply thresholding
ret, im2 = cv.threshold(img, args.threshold, 255, cv.THRESH_BINARY)
# dilate the thresholded peaks to eliminate "pinholes"
im3 = cv.dilate(im2, None, iterations=2)

contours, hier = cv.findContours(im3, cv.RETR_TREE, cv.CHAIN_APPROX_SIMPLE)
print('found', len(contours), 'contours')
# draw a bounding box around each contour
for contour in contours:
    x,y,w,h = cv.boundingRect(contour)
    cv.rectangle(im, (x,y), (x+w,y+h), (255,0,0), 2)

cv.imshow('Contours', im)

which gave me what I was looking for: