How to determine regions out of a list of coordinates?

Question

I'm struggling with object detection with OpenCv for python : I use a matchTemplate method to detect an image, but the result end with multiple coordinates of the same object.

[(798, 540), (799, 540), (800, 540), (798, 541), (799, 541), (800, 541), (798, 542), (799, 542), (800, 542), (798, 543), (799, 543), (800, 543), (798, 544), (799, 544), (800, 544)]

I want only one coordinates for each image detected so i applied an average of all the coordinates and the result is great (red dot on image) : (799, 542)

The issue is that sometimes there is two images detected in the same frame and it doesn't work with the average method (gives the middle of the two coordinates).

Do you have any (non naïve) ideas of how to do this for 2,3,4... detected images ?

Thanks :)

Answer 1

My code is neither perfect nor optimal; But it might be good to start :)

import matplotlib.pyplot as plt
import numpy as np
import random
import math

# 'o': without cluster
# '*': first cluster
# '^': second cluster
pts = [
    [6.0, 4.0, 'o'], [1.0, 2.0, 'o'], [2.0, 1.0, 'o'], [2.0, 2.0, 'o'],
    [6.0, 6.0, 'o'], [6.0, 5.0, 'o'], [5.0, 6.0, 'o'], [5.0, 5.0, 'o']
]

def distance(pt1, pt2):
    return math.hypot(pt1[0] - pt2[0], pt1[1] - pt2[1])

def getRandomPoint():
    rnd = random.randint(0, len(pts)-1)
    return [pts[rnd][0], pts[rnd][1]]

def plotClusterCenter(c='o'):
    s = []
    for p in pts:
        if p[2] == c:
            s.append(p)
    print(s)
    cx, cy = np.mean([d[0] for d in s]), np.mean([d[1] for d in s])
    plt.plot(cx, cy, c, c=(1, .5, 0))


x, y, c = [d[0] for d in pts], [d[1] for d in pts], [d[2] for d in pts]
A, B = getRandomPoint(), getRandomPoint()


for _ in range(0, len(pts)//2):
    for i in range(0, len(x)):
        if c[i] == "*":
            A = [(A[0] + x[i]) / 2, (A[1] + y[i]) / 2]
        else:
            B = [(B[0] + x[i]) / 2, (B[1] + y[i]) / 2]
        pt = (x[i], y[i])
        c[i] = "*" if distance(A, pt) < distance(B, pt) else "^"
        pts[i][2]=c[i]

for i in range(0, len(x)):
    plt.plot(x[i], y[i], c[i], c=(0, 0, 0))

plotClusterCenter('*')
plotClusterCenter('^')
plt.show()

This code can not solve the problem of the number of clusters and I think it is currently useful if you know the number of clusters.

---

Update:

After reading the comments (especially the complete description of @Christoph Rackwitz); I came to the conclusion that the method I proposed was probably not the right one.

---

Update:

I thought more about explanations and discussions. I think if you have a mask from points, it might not be the worst idea if you try something like this:

import sys
import cv2
import numpy as np

org = cv2.imread(sys.path[0]+'/mask.png')
im = org.copy()
H, W = org.shape[:2]

gry = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY)
gry = cv2.erode(gry, np.ones((31, 31)))

cnts, _ = cv2.findContours(gry, cv2.RETR_TREE, cv2.CHAIN_APPROX_NONE)
for cnt in cnts:
    x, y, w, h = cv2.boundingRect(cnt)
    if w < W:
        cv2.rectangle(im, (x, y), (x+w, y+h), (50, 250, 10), 2)
        cv2.circle(im,  (x+w//2, y+h//2),3, (240, 20, 100), 3)

cv2.imwrite(sys.path[0]+'/output.png', np.hstack((org, im)))

In this case you can find the clusters, their range as well as the approximate center of each. In the next step, you can examine the range of each cluster in more detail.