Connect the ends of the founded contours

Question

I have the next binary mask:

As you can see, there are small gaps between the ends of curves. How can I connect them, without connecting contours that just near/parallel?

I ended up with code:

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)

This code almost perfectly solves the problem but does not take into account whether the points are the ends of the curves.

Answer 1

After many attempts, I came to find the contour points with the sharpest angles between the nearest points. Alas, a universal solution did not work and you need to select the level of smoothing.

def angle_between(v1, v2):
  """ Returns the angle in radians between vectors 'v1' and 'v2'::
    from https://stackoverflow.com/questions/2827393/#13849249
  """
  v1_u = v1 / np.linalg.norm(v1)
  v2_u = v2 / np.linalg.norm(v2)
  return np.arccos(np.clip(np.dot(v1_u, v2_u), -1.0, 1.0))

def extractCorners(contour, smoothing, maxAngle=np.deg2rad(60)):
  pts = [pt for [pt] in cv2.approxPolyDP(contour, smoothing, True)]
  # close contour
  pts.append(pts[0])
  pts.append(pts[1])

  # angle between AB and CB
  angles = sorted(
    filter(
      lambda x: x[3] <= maxAngle,
      ( (b, a, c, angle_between(a - b, c - b)) for a, b, c in zip(pts[:-2], pts[1:-1], pts[2:]) )
    ),
    key=lambda x: x[3]
  )
  
  return angles

I applied this function to the image as follows:

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))

Then I group the points into clusters (optional step, this speed up the processing):

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)

Finally, I introduced the following algorithm for selecting pairs of points in groups:

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)

Next is the task of checking the compatibility of the contours, so that the small balls do not stick together, which does not apply to the original question.

I hope this solution helps someone else.