132 lines
5.5 KiB
Python
132 lines
5.5 KiB
Python
from scipy.spatial import ConvexHull
|
|
import numpy
|
|
from collections import defaultdict
|
|
|
|
|
|
def distance(x, y):
|
|
"""returns eucledean distance between two points from `find_corner_circles`."""
|
|
return numpy.sqrt(
|
|
sum(
|
|
(v - w) ** 2
|
|
for v, w in zip(x.pt, y.pt)
|
|
)
|
|
)
|
|
|
|
def find_neighbors(keypoints, size_factor=1.5):
|
|
"""Returns keypoints sorted by x-index and determines for each index
|
|
in this sorted list of kepoints, what keypoints are close by, defines
|
|
as closer than `size_factor` times the size of both keypoints."""
|
|
keypoints = sorted(keypoints, key=lambda x: x.pt[0])
|
|
neighbors = [set() for _ in range(len(keypoints))]
|
|
for i, x in enumerate(keypoints):
|
|
for j, y in enumerate(keypoints[i+1:], start=i+1):
|
|
if y.pt[0] - x.pt[0] > 2 * size_factor * y.size:
|
|
break
|
|
if distance(x, y) < 1.5 * (x.size + y.size):
|
|
neighbors[i].add(j)
|
|
neighbors[j].add(i)
|
|
return keypoints, neighbors
|
|
|
|
|
|
def cluster_circles_per_corner(keypoints, distance_factor=1.5):
|
|
"""Clusters circles that are close by (1.5 times the sum of both sizes)
|
|
into a group of keypoints. Returns the keypoints soerted w.r.t. x-coordinate
|
|
and returns a set of tuple, each tuple containing indices of keypoints
|
|
in the sorted array. One cluster is represented by one tuple."""
|
|
keypoints, neighbors = find_neighbors(keypoints, size_factor=distance_factor)
|
|
shapes = []
|
|
left = set(range(len(keypoints)))
|
|
|
|
def find_shape(shape, left):
|
|
nonlocal neighbors
|
|
def f(left):
|
|
nonlocal shape
|
|
if left == 0:
|
|
return True
|
|
|
|
lastIndex = shape[-1];
|
|
for index in neighbors[lastIndex]:
|
|
if index in shape:
|
|
continue
|
|
shape.append(index)
|
|
if f(left - 1):
|
|
return True
|
|
shape = shape[:-1]
|
|
|
|
return False
|
|
if f(left):
|
|
return shape
|
|
else:
|
|
return None
|
|
|
|
while len(left) > 0:
|
|
shape = find_shape([left.pop()], 7 - 1)
|
|
if shape:
|
|
shapes.append(shape)
|
|
left -= set(shape)
|
|
return keypoints, shapes
|
|
|
|
def separate_lines(keypoints, shape, cosine_threshold=0.00137046524): # accept approx 3 degrees from straight
|
|
"""Find points that lie on a line using cosine similarity for triples of points, e.g. the cosine similarity
|
|
between vectors from A to B and C to B for points A, B and C. If 1-abs(cosine similarity) is smaller than
|
|
`cosine_threshold`, the points lie on a line with at most cos(cosine_threshold) angle deviation. Those
|
|
points are grouped together. This method should yet be improved in two ways:
|
|
- assure that iff (i,j,k) meets the threshold, so do all permutations (not true now due to numerical
|
|
errors and assymetry of the cosine function for angle 0 and angle pi corners.
|
|
- only group points iff for (i, j, k) and (p, q, r) at least two of the indices match. This way circles
|
|
can form a (straingt) corner and hence lie on two lines, without grouping the points of these two
|
|
perpendicular lines together.
|
|
Both could be solved brutally, since shape will in general only hold few shapes.
|
|
|
|
Returns a set of tuple, each tuple refering to indices of keypoints and being a subset of `shape`."""
|
|
groups = defaultdict(set)
|
|
|
|
# n x 2 matrix with points
|
|
P = numpy.array([keypoints[i].pt for i in shape])
|
|
|
|
# n x n x 2 tensor with vectors between two points
|
|
V = (P[:,None] - P[None])
|
|
|
|
# n x n tensor squared lengths of each vector
|
|
L = (V * V).sum(2)
|
|
|
|
# n x n x n tensor between each vector with a matching point in P
|
|
D = (V[None] * V[:, :, None]).sum(3)
|
|
|
|
# n x n x n tensor with cosine similarity between vectors with a matching point
|
|
S = (1e-15 + D) / (1e-15 + numpy.sqrt(L[None] * L[:, :, None]))
|
|
|
|
# We want to test whether the cosine similarity isclose to 1 or -1 (angle 0° or 180°)
|
|
S = numpy.abs(S)
|
|
for i, j, k in zip(*numpy.where(1 - S < cosine_threshold)):
|
|
if i!=j and j!=k and k!=i:
|
|
groups[i] = groups[i] | {i, j, k}
|
|
return set(map(tuple, groups.values()))
|
|
|
|
def find_line_coefficients_per_corner(keypoints, corner_circles, cosine_threshold=0.00137046524):
|
|
"""Linearly fits lines on keypoints that are part of one line as returned by `separate_lines`. Returns
|
|
a list of 2-sized lists with tuples of coefficients (a,b) representing a line a*x + b."""
|
|
lines = []
|
|
for shape in corner_circles:
|
|
lines.append([])
|
|
for piece in separate_lines(keypoints, shape, cosine_threshold):
|
|
a, b = numpy.polyfit(*zip(*[keypoints[shape[p]].pt for p in piece]), 1)
|
|
lines[-1].append((a,b))
|
|
if len(lines[-1]) != 2:
|
|
print("Warning, did not find two lines for a shape: {}".format(lines))
|
|
lines.pop()
|
|
# assert len(lines[-1]) == 2, "Did not find two lines for a shape: {}".format(lines)
|
|
return lines
|
|
|
|
def intersection_per_corner(line_coefficients):
|
|
"""For each two lines as returned by `fit_linear` find the intersection. Returns the corners
|
|
in the order of line_oefficients, but also returns the order in which they form a simple
|
|
polygon in counter-clockwise orientation."""
|
|
corners = [
|
|
(x, a * x + b)
|
|
for (a, b), (c, d) in line_coefficients
|
|
for x in [(d - b) / (a - c)] # alias
|
|
]
|
|
return corners, ConvexHull(corners).vertices
|
|
|