Соединяем концы найденных контуров

Question

У меня следующая двоичная маска:

Как видите, между концами кривых есть небольшие промежутки. Как я могу их соединить, не соединяя контуры, которые просто близки / параллельны?

Я получил код:

import cv2
import numpy as np
import random

def pointDist(a, b):
  return np.linalg.norm(np.subtract(a, b))

img = cv2.imread('mask.png')
img = cv2.cvtColor(gray, cv2.COLOR_GRAY2BGR)
 
contours, _ = cv2.findContours(gray, cv2.RETR_LIST, cv2.CHAIN_APPROX_SIMPLE)
 
contours = list( map(lambda c: cv2.approxPolyDP(c, 4, True), contours) )
points = [ (i, tuple(pt)) for i, c in enumerate(contours) for [pt] in c ]
 
nearestContoursPoints = []
checkedContours = set()
for i, c in enumerate(contours):
  checkedContours.add(i)
   
  color = (random.randint(120, 255), random.randint(120, 255), random.randint(120, 255))
  cv2.drawContours(img, [c], -1, color, 2)
   
  pts = [pt[1] for pt in points if pt[0] not in checkedContours]
  if not pts: break
   
  for [pt] in c:
    nearest = min(pts, key=lambda b: pointDist(pt, b))
    if pointDist(pt, nearest) <= 15:
      cv2.line(img, tuple(pt), tuple(nearest), (0, 0, 255), 3)
 
cv2.imshow('', img)

Этот код почти идеально решает проблему, но не учитывает точки - концы кривых.

Answer 1

После многих попыток я пришел к тому, чтобы найти точки контура с наиболее острыми углами между ближайшими точками. Увы, универсального решения не получилось и нужно выбрать уровень сглаживания.

Я применил эту функцию к изображению следующим образом:

for c in contours:
  for x, a, b, angle in extractCorners(c, smoothing=7, maxAngle=np.deg2rad(60)):
    cv2.circle(img, tuple(x), 2, (255, 0, 255), 3)
    v = x - ((a + b) / 2)
    p2 = x + (v / np.linalg.norm(v)) * 20
    cv2.line(img, tuple(x), tuple(p2.astype(np.int)), (255, 0, 0))

Затем я группирую точки в кластеры (необязательный шаг, это ускоряет обработку):

contoursCorners = [
  (cid, pt) for cid, contour in enumerate(contours) for pt in extractCorners(contour, smoothing=7, maxAngle=np.deg2rad(60))
]

maxDist = 20
neighborsGroups = []
while 0 < len(contoursCorners):
  p = contoursCorners[-1]
  group = [p]
  del contoursCorners[-1]
  
  unchecked = [p[1]]
  while 0 < len(unchecked):
    p = unchecked[-1]
    del unchecked[-1]
    
    neighbors = [
      (ind, pt) for ind, pt in enumerate(contoursCorners) if pointDist(p[0], pt[1][0]) <= maxDist
    ]
    for ind, pt in reversed(neighbors):
      unchecked.append(pt[1])
      group.append(pt)
      del contoursCorners[ind]
  # end while
  if 2 <= len(group):
    # we can't connect corners of the same contour
    if not all( x[0] == group[0][0] for x in group ):
      neighborsGroups.append(group)
# end while

for group in neighborsGroups:
  print(len(group))
  color = (random.randint(120, 255), random.randint(120, 255), random.randint(120, 255))
  for cid, (x, a, b, angle) in group:
    cv2.circle(img, tuple(x), 2, color, 3)

Наконец, я представил следующий алгоритм выбора пар точек в группы:

def pointFromLineDist(p1, p2, pt):
  return np.abs(np.cross(p2 - p1, p1 - pt) / np.linalg.norm(p2 - p1))
  
def cornerConnectionCost(a, b):
  # must be from different contours
  if a[0] == b[0]: return math.inf
  
  aP, aA, aB = a[1][:3]
  bP, bA, bB = b[1][:3]
  
  d = pointDist(aP, bP)
  # max distance
  if 20 < d: return math.inf
  
  dl = min((
    pointFromLineDist(aA, aP, bP),
    pointFromLineDist(aB, aP, bP),
    pointFromLineDist((aA + aB) / 2, aP, bP),
  ))
  return d * dl

def connectedCorners(group, costF, maxCost=math.inf):
  # cost may be NOT symmetrical
  costMatrix = np.array([[costF(a, b) for b in group] for a in group])
  
  infRow = np.array([math.inf] * len(group))
  while True:
    x, y = np.unravel_index(costMatrix.argmin(axis=None), costMatrix.shape)
    if maxCost <= costMatrix[x, y]: break
    #
    costMatrix[x, :] = infRow
    costMatrix[y, :] = infRow
    costMatrix[:, x] = infRow
    costMatrix[:, y] = infRow
    #
    yield (group[x], group[y])
    pass
  return

for group in neighborsGroups:
  for A, B in connectedCorners(group, costF=cornerConnectionCost):
    color = (0, 0, 255)
    cv2.line(img, tuple(A[1][0]), tuple(B[1][0]), color, 4)

Далее стоит задача проверки совместимости контуров, чтобы маленькие шарики не слипались, что не относится к исходному вопросу.

Надеюсь, это решение поможет кому-то другому .