如何匹配 2D 框的几何模板以适合另一组 2D 框
How to match a geometric template of 2D boxes to fit another set of 2D boxes
我正在尝试在一组坐标为 (A) 的二维框（来自具有已知大小和框之间距离的模板）与另一组坐标为 (B) 的二维框（可能包含比 A) 更多的框。它们应该匹配 A 中的每个盒子对应于 B 中的单个盒子。A 中的盒子一起形成一个“邮票”，它至少在一个维度上是不对称的。
Illustration of problem
说明：图中的“Stanz”是A组的一个盒子
人们甚至可能认为 A 组只是 2D 点（盒子的中心点）以使其更简单。
最后的结果就是知道哪个A框对应哪个B框
我只能想到非常具体的方法，针对特定的盒子布局量身定制，是否有任何已知的通用方法来处理这种形式的 matching/search 问题，它们叫什么？
编辑：可能的解决方案
我想出了一个可能的解决方案，为集合 A 中的单个框寻找每个可能的 B 中心位置的所有可能旋转。在这里，A 中的所有点都将被旋转并与到的距离进行比较B中心。不确定这是不是一个好方法。
Looking for the possible rotations at each B centerpoint- solution
这与其说是一个答案，不如说是一个想法，但对于评论来说太长了。我在上面的评论中问了一些额外的问题，但答案可能不是特别相关，所以我会继续并同时提供一些想法。
如您所知，点匹配是其自身的问题领域，如果您搜索 'point matching algorithm'，您将找到各种文章、论文和其他资源。似乎一个特别的解决方案在这里可能是合适的（一个比可用的更通用算法更简单的解决方案）。
我假设输入点集只能旋转，不能翻转。如果这个想法可行，它也应该适用于翻转 - 你只需要 运行 每个翻转配置单独的算法。
在您的示例图像中，您已将集合 A 中的一个点与集合 B 中的一个点进行匹配，以便它们重合。将此共享点称为 'anchor' 点。您需要对集合 A 中的一个点和集合 B 中的一个点的每个组合执行此操作，直到找到匹配项或用尽可能性。接下来的问题是确定是否可以在给定这些匹配点对之一的情况下进行匹配。
似乎对于给定的锚点，匹配的必要但不充分条件是可以找到集合A中的点和集合B中的点与锚点的距离大致相同。 （'approximately' 的含义取决于输入，并且需要适当调整，因为您使用的是整数。）示例图像中满足此条件，因为每个点集的中心点是（大约) 与锚点的距离相同。 （请注意，可能有多对点满足此条件，在这种情况下，您必须依次检查每一对。）
一旦你有了这样的一对——你的例子中的中心点——你就可以使用一些简单的三角学和线性代数来旋转集合 A，使这对中的点重合，之后这两个点集被锁定在一起在两点而不只是一点。在您的图片中，A 组顺时针旋转约 135 度。然后你检查集合 B 中的每个点是否在集合 A 中有一个点与其重合，在某个阈值内。如果是这样，你就有了匹配。
在您的示例中，这当然会失败，因为旋转实际上并不匹配。但最终，如果匹配，您将找到测试成功的锚点对。
我知道用一些图表会更容易解释，但恐怕目前这种书面解释就足够了。我不认为这会奏效——这只是一个想法。也许更通用的算法会更好。但是，如果这确实有效，它可能具有实施起来相当简单的优势。
[编辑：也许我应该补充一点，这与您的解决方案类似，除了额外的步骤以允许仅测试可能旋转的子集。]
[编辑：我认为这里可以进一步完善。如果在选择锚点后，可以通过旋转进行匹配，那么对于 B 中的每个 p 点，A 中都有一个点（大约）与锚点为 p。同样，这是一个必要但不充分的条件，但它可以让您快速排除无法通过轮换进行匹配的情况。]
在您的示例中，模板与其在 B 中的存在之间的转换可以完全由两个匹配点定义（实际上是过度定义）。
所以这里有一个简单的方法，有点性能。首先，将 B 中的所有点放入 kD 树中。现在，在 A 中选择一个规范的“第一”点，并假设它与 B 中的每个点匹配。要检查它是否与 B 中的特定点匹配，请在 A 中选择一个规范的“第二”点并测量它到“第一”点。然后，使用标准的 kD 邻近边界查询来查找 B 中的所有点，这些点与 B 中假设的匹配“第一个”点的距离大致相同。对于其中的每一个，确定 A 和 B 之间的转换，并为每个A中的其他点，确定A中是否有一个点大致在正确的位置（再次使用kD-tree），与第一个不匹配的点一起提前出局。
最坏情况下的性能在病态情况下可能会变得非常糟糕（我认为 O(n^3 log n)），但总的来说，对于具有低阈值的表现良好的数据，我预计大约 O(n log n)。请注意，阈值有点粗略，结果可能取决于您选择的“第一”和“第二”点。
下面是在 python 中完成的解决方案，没有 kD 树，也没有早期郊游候选者。更好的方法是根据 Sneftel 自己进行实施，但如果您需要任何快速且有情节的东西，这可能会有用。
绘图显示了不同的步骤，开始时仅将模板作为连接线的集合。然后它被翻译到 B 中的一个点，其中 A 点和 B 点之间的距离最适合。终于旋转了。
在这个例子中，匹配哪个模板位置与哪个边界框位置匹配也很重要，所以它最后是一个额外的步骤。与上面的大纲相比，代码中可能存在一些偏差。
import numpy as np
import random
import math
import matplotlib.pyplot as plt
def to_polar(pos_array):
x = pos_array[:, 0]
y = pos_array[:, 1]
length = np.sqrt(x ** 2 + y ** 2)
t = np.arctan2(y, x)
zip_list = list(zip(length, t))
array_polar = np.array(zip_list)
return array_polar
def to_cartesian(pos):
# first element radius
# second is angle(theta)
# Converting polar to cartesian coordinates
radius = pos[0]
theta = pos[1]
x = radius * math.cos(theta)
y = radius * math.sin(theta)
return x,y
def calculate_distance_points(p1,p2):
return np.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
def find_closest_point_inx(point, neighbour_set):
shortest_dist = None
closest_index = -1
# Find the point in the secondary array that is the closest
for index,curr_neighbour in enumerate(neighbour_set):
distance = calculate_distance_points(point, curr_neighbour)
if shortest_dist is None or distance < shortest_dist:
shortest_dist = distance
closest_index = index
return closest_index
# Find the sum of distances between each point in primary to the closest one in secondary
def calculate_agg_distance_arrs(primary,secondary):
total_distance = 0
for point in primary:
closest_inx = find_closest_point_inx(point, secondary)
dist = calculate_distance_points(point, secondary[closest_inx])
total_distance += dist
return total_distance
# returns a set of <primary_index,neighbour_index>
def pair_neighbours_by_distance(primary_set, neighbour_set, distance_limit):
pairs = {}
for num, point in enumerate(primary_set):
closest_inx = find_closest_point_inx(point, neighbour_set)
if calculate_distance_points(neighbour_set[closest_inx], point) > distance_limit:
closest_inx = None
pairs[num]=closest_inx
return pairs
def rotate_array(array, angle,rot_origin=None):
if rot_origin is not None:
array = np.subtract(array,rot_origin)
# clockwise rotation
theta = np.radians(angle)
c, s = np.cos(theta), np.sin(theta)
R = np.array(((c, -s), (s, c)))
rotated = np.matmul(array, R)
if rot_origin is not None:
rotated = np.add(rotated,rot_origin)
return rotated
# Finds out a point in B_set and a rotation where the points in SetA have the best alignment towards SetB.
def find_stamp_rotation(A_set, B_set):
# Step 1
anchor_point_A = A_set[0]
# Step 2. Convert all points to polar coordinates with anchor as origin
A_anchor_origin = A_set - anchor_point_A
anchor_A_polar = to_polar(A_anchor_origin)
print(anchor_A_polar)
# Step 3 for each point in B
score_tuples = []
for num_anchor, B_anchor_point_try in enumerate(B_set):
# Step 3.1
B_origin_rel_point = B_set-B_anchor_point_try
B_polar_rp_origin = to_polar(B_origin_rel_point)
# Step 3.3 select arbitrary point q from Ap
point_Aq = anchor_A_polar[1]
# Step 3.4 test each rotation, where pointAq is rotated to each B-point (except the B anchor point)
for try_rot_point_B in [B_rot_point for num_rot, B_rot_point in enumerate(B_polar_rp_origin) if num_rot != num_anchor]:
# positive rotation is clockwise
# Step 4.1 Rotate Ap by the angle between q and n
angle_to_try = try_rot_point_B[1]-point_Aq[1]
rot_try_arr = np.copy(anchor_A_polar)
rot_try_arr[:,1]+=angle_to_try
cart_rot_try_arr = [to_cartesian(e) for e in rot_try_arr]
cart_B_rp_origin = [to_cartesian(e) for e in B_polar_rp_origin]
distance_score = calculate_agg_distance_arrs(cart_rot_try_arr, cart_B_rp_origin)
score_tuples.append((B_anchor_point_try,angle_to_try,distance_score))
# Step 4.3
lowest=None
for b_point,angle,distance in score_tuples:
print("point:{} angle(rad):{} distance(sum):{}".format(b_point,360*(angle/(2*math.pi)),distance))
if lowest is None or distance < lowest[2]:
lowest = b_point, 360*angle/(2*math.pi), distance
return lowest
def test_example():
ax = plt.subplot()
ax.grid(True)
plt.title('Fit Template to BBoxes by translation and rotation')
plt.xlim(-20, 20)
plt.ylim(-20, 20)
ax.set_xticks(range(-20,20), minor=True)
ax.set_yticks(range(-20,20), minor=True)
template = np.array([[-10,-10],[-10,10],[0,0],[10,-10],[10,10], [0,20]])
# Test Bboxes are Rotated 40 degree, translated 2,2
rotated = rotate_array(template,40)
rotated = np.subtract(rotated,[2,2])
# Adds some extra bounding boxes as noise
for i in range(8):
rotated = np.append(rotated,[[random.randrange(-20,20), random.randrange(-20,20)]],axis=0)
# Scramble entries in array and return the position change.
rnd_rotated = rotated.copy()
np.random.shuffle(rnd_rotated)
element_positions = []
# After shuffling, looks at which index the "A"-marks has ended up at. For later comparison to see that the algo found the correct answer.
# This is to represent the actual case, where I will get a bunch of unordered bboxes.
rnd_map = {}
indexes_translation = [num2 for num,point in enumerate(rnd_rotated) for num2,point2 in enumerate(rotated) if point[0]==point2[0] and point[1]==point2[1]]
for num,inx in enumerate(indexes_translation):
rnd_map[num]=inx
# algo part 1/3
b_point,angle,_ = find_stamp_rotation(template,rnd_rotated)
# Plot for visualization
legend_list = np.empty((0,2))
leg_template = plt.plot(template[:,0],template[:,1],c='r')
legend_list = np.append(legend_list,[[leg_template[0],'1. template-pattern']],axis=0)
leg_bboxes = plt.scatter(rnd_rotated[:,0],rnd_rotated[:,1],c='b',label="scatter")
legend_list = np.append(legend_list,[[leg_bboxes,'2. bounding boxes']],axis=0)
leg_anchor = plt.scatter(b_point[0],b_point[1],c='y')
legend_list = np.append(legend_list,[[leg_anchor,'3. Discovered bbox anchor point']],axis=0)
# algo part 2/3
# Superimpose A onto B by A[0] to b_point
offset = b_point - template[0]
super_imposed_A = template + offset
# Plot superimposed, but not yet rotated
leg_s_imposed = plt.plot(super_imposed_A[:,0],super_imposed_A[:,1],c='k')
#plt.legend(rubberduckz, "superimposed template on anchor")
legend_list = np.append(legend_list,[[leg_s_imposed[0],'4. Templ superimposed on Bbox']],axis=0)
print("Superimposed A on B by A[0] to {}".format(b_point))
print(super_imposed_A)
# Rotate, now the template should match pattern of bboxes
# algo part 3/4
super_imposed_rotated_A = rotate_array(super_imposed_A,-angle,rot_origin=super_imposed_A[0])
# Show the beautiful match in a last plot
leg_s_imp_rot = plt.plot(super_imposed_rotated_A[:,0],super_imposed_rotated_A[:,1],c='g')
legend_list = np.append(legend_list,[[leg_s_imp_rot[0],'5. final fit']],axis=0)
plt.legend(legend_list[:,0], legend_list[:,1],loc="upper left")
plt.show()
# algo part 4/4
pairs = pair_neighbours_by_distance(super_imposed_rotated_A, rnd_rotated, 10)
print(pairs)
for inx in range(len(pairs)):
bbox_num = pairs[inx]
print("template id:{}".format(inx))
print("bbox#id:{}".format(bbox_num))
#print("original_bbox:{}".format(rnd_map[bbox_num]))
if __name__ == "__main__":
test_example()
带有边界框的实际图像的结果。在这里可以看出缩放比例不正确，这使得模板有点偏离，但它仍然能够配对，这就是我想要的最终结果。
我正在尝试在一组坐标为 (A) 的二维框（来自具有已知大小和框之间距离的模板）与另一组坐标为 (B) 的二维框（可能包含比 A) 更多的框。它们应该匹配 A 中的每个盒子对应于 B 中的单个盒子。A 中的盒子一起形成一个“邮票”，它至少在一个维度上是不对称的。
Illustration of problem
说明：图中的“Stanz”是A组的一个盒子
人们甚至可能认为 A 组只是 2D 点（盒子的中心点）以使其更简单。
最后的结果就是知道哪个A框对应哪个B框
我只能想到非常具体的方法，针对特定的盒子布局量身定制，是否有任何已知的通用方法来处理这种形式的 matching/search 问题，它们叫什么？
编辑：可能的解决方案
我想出了一个可能的解决方案，为集合 A 中的单个框寻找每个可能的 B 中心位置的所有可能旋转。在这里，A 中的所有点都将被旋转并与到的距离进行比较B中心。不确定这是不是一个好方法。
Looking for the possible rotations at each B centerpoint- solution
这与其说是一个答案，不如说是一个想法，但对于评论来说太长了。我在上面的评论中问了一些额外的问题，但答案可能不是特别相关，所以我会继续并同时提供一些想法。
如您所知，点匹配是其自身的问题领域，如果您搜索 'point matching algorithm'，您将找到各种文章、论文和其他资源。似乎一个特别的解决方案在这里可能是合适的（一个比可用的更通用算法更简单的解决方案）。
我假设输入点集只能旋转，不能翻转。如果这个想法可行，它也应该适用于翻转 - 你只需要 运行 每个翻转配置单独的算法。
在您的示例图像中，您已将集合 A 中的一个点与集合 B 中的一个点进行匹配，以便它们重合。将此共享点称为 'anchor' 点。您需要对集合 A 中的一个点和集合 B 中的一个点的每个组合执行此操作，直到找到匹配项或用尽可能性。接下来的问题是确定是否可以在给定这些匹配点对之一的情况下进行匹配。
似乎对于给定的锚点，匹配的必要但不充分条件是可以找到集合A中的点和集合B中的点与锚点的距离大致相同。 （'approximately' 的含义取决于输入，并且需要适当调整，因为您使用的是整数。）示例图像中满足此条件，因为每个点集的中心点是（大约) 与锚点的距离相同。 （请注意，可能有多对点满足此条件，在这种情况下，您必须依次检查每一对。）
一旦你有了这样的一对——你的例子中的中心点——你就可以使用一些简单的三角学和线性代数来旋转集合 A，使这对中的点重合，之后这两个点集被锁定在一起在两点而不只是一点。在您的图片中，A 组顺时针旋转约 135 度。然后你检查集合 B 中的每个点是否在集合 A 中有一个点与其重合，在某个阈值内。如果是这样，你就有了匹配。
在您的示例中，这当然会失败，因为旋转实际上并不匹配。但最终，如果匹配，您将找到测试成功的锚点对。
我知道用一些图表会更容易解释，但恐怕目前这种书面解释就足够了。我不认为这会奏效——这只是一个想法。也许更通用的算法会更好。但是，如果这确实有效，它可能具有实施起来相当简单的优势。
[编辑：也许我应该补充一点，这与您的解决方案类似，除了额外的步骤以允许仅测试可能旋转的子集。]
[编辑：我认为这里可以进一步完善。如果在选择锚点后，可以通过旋转进行匹配，那么对于 B 中的每个 p 点，A 中都有一个点（大约）与锚点为 p。同样，这是一个必要但不充分的条件，但它可以让您快速排除无法通过轮换进行匹配的情况。]
在您的示例中，模板与其在 B 中的存在之间的转换可以完全由两个匹配点定义（实际上是过度定义）。
所以这里有一个简单的方法，有点性能。首先，将 B 中的所有点放入 kD 树中。现在，在 A 中选择一个规范的“第一”点，并假设它与 B 中的每个点匹配。要检查它是否与 B 中的特定点匹配，请在 A 中选择一个规范的“第二”点并测量它到“第一”点。然后，使用标准的 kD 邻近边界查询来查找 B 中的所有点，这些点与 B 中假设的匹配“第一个”点的距离大致相同。对于其中的每一个，确定 A 和 B 之间的转换，并为每个A中的其他点，确定A中是否有一个点大致在正确的位置（再次使用kD-tree），与第一个不匹配的点一起提前出局。
最坏情况下的性能在病态情况下可能会变得非常糟糕（我认为 O(n^3 log n)），但总的来说，对于具有低阈值的表现良好的数据，我预计大约 O(n log n)。请注意，阈值有点粗略，结果可能取决于您选择的“第一”和“第二”点。
下面是在 python 中完成的解决方案，没有 kD 树，也没有早期郊游候选者。更好的方法是根据 Sneftel 自己进行实施，但如果您需要任何快速且有情节的东西，这可能会有用。
绘图显示了不同的步骤，开始时仅将模板作为连接线的集合。然后它被翻译到 B 中的一个点，其中 A 点和 B 点之间的距离最适合。终于旋转了。
在这个例子中，匹配哪个模板位置与哪个边界框位置匹配也很重要，所以它最后是一个额外的步骤。与上面的大纲相比，代码中可能存在一些偏差。
import numpy as np
import random
import math
import matplotlib.pyplot as plt
def to_polar(pos_array):
x = pos_array[:, 0]
y = pos_array[:, 1]
length = np.sqrt(x ** 2 + y ** 2)
t = np.arctan2(y, x)
zip_list = list(zip(length, t))
array_polar = np.array(zip_list)
return array_polar
def to_cartesian(pos):
# first element radius
# second is angle(theta)
# Converting polar to cartesian coordinates
radius = pos[0]
theta = pos[1]
x = radius * math.cos(theta)
y = radius * math.sin(theta)
return x,y
def calculate_distance_points(p1,p2):
return np.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
def find_closest_point_inx(point, neighbour_set):
shortest_dist = None
closest_index = -1
# Find the point in the secondary array that is the closest
for index,curr_neighbour in enumerate(neighbour_set):
distance = calculate_distance_points(point, curr_neighbour)
if shortest_dist is None or distance < shortest_dist:
shortest_dist = distance
closest_index = index
return closest_index
# Find the sum of distances between each point in primary to the closest one in secondary
def calculate_agg_distance_arrs(primary,secondary):
total_distance = 0
for point in primary:
closest_inx = find_closest_point_inx(point, secondary)
dist = calculate_distance_points(point, secondary[closest_inx])
total_distance += dist
return total_distance
# returns a set of <primary_index,neighbour_index>
def pair_neighbours_by_distance(primary_set, neighbour_set, distance_limit):
pairs = {}
for num, point in enumerate(primary_set):
closest_inx = find_closest_point_inx(point, neighbour_set)
if calculate_distance_points(neighbour_set[closest_inx], point) > distance_limit:
closest_inx = None
pairs[num]=closest_inx
return pairs
def rotate_array(array, angle,rot_origin=None):
if rot_origin is not None:
array = np.subtract(array,rot_origin)
# clockwise rotation
theta = np.radians(angle)
c, s = np.cos(theta), np.sin(theta)
R = np.array(((c, -s), (s, c)))
rotated = np.matmul(array, R)
if rot_origin is not None:
rotated = np.add(rotated,rot_origin)
return rotated
# Finds out a point in B_set and a rotation where the points in SetA have the best alignment towards SetB.
def find_stamp_rotation(A_set, B_set):
# Step 1
anchor_point_A = A_set[0]
# Step 2. Convert all points to polar coordinates with anchor as origin
A_anchor_origin = A_set - anchor_point_A
anchor_A_polar = to_polar(A_anchor_origin)
print(anchor_A_polar)
# Step 3 for each point in B
score_tuples = []
for num_anchor, B_anchor_point_try in enumerate(B_set):
# Step 3.1
B_origin_rel_point = B_set-B_anchor_point_try
B_polar_rp_origin = to_polar(B_origin_rel_point)
# Step 3.3 select arbitrary point q from Ap
point_Aq = anchor_A_polar[1]
# Step 3.4 test each rotation, where pointAq is rotated to each B-point (except the B anchor point)
for try_rot_point_B in [B_rot_point for num_rot, B_rot_point in enumerate(B_polar_rp_origin) if num_rot != num_anchor]:
# positive rotation is clockwise
# Step 4.1 Rotate Ap by the angle between q and n
angle_to_try = try_rot_point_B[1]-point_Aq[1]
rot_try_arr = np.copy(anchor_A_polar)
rot_try_arr[:,1]+=angle_to_try
cart_rot_try_arr = [to_cartesian(e) for e in rot_try_arr]
cart_B_rp_origin = [to_cartesian(e) for e in B_polar_rp_origin]
distance_score = calculate_agg_distance_arrs(cart_rot_try_arr, cart_B_rp_origin)
score_tuples.append((B_anchor_point_try,angle_to_try,distance_score))
# Step 4.3
lowest=None
for b_point,angle,distance in score_tuples:
print("point:{} angle(rad):{} distance(sum):{}".format(b_point,360*(angle/(2*math.pi)),distance))
if lowest is None or distance < lowest[2]:
lowest = b_point, 360*angle/(2*math.pi), distance
return lowest
def test_example():
ax = plt.subplot()
ax.grid(True)
plt.title('Fit Template to BBoxes by translation and rotation')
plt.xlim(-20, 20)
plt.ylim(-20, 20)
ax.set_xticks(range(-20,20), minor=True)
ax.set_yticks(range(-20,20), minor=True)
template = np.array([[-10,-10],[-10,10],[0,0],[10,-10],[10,10], [0,20]])
# Test Bboxes are Rotated 40 degree, translated 2,2
rotated = rotate_array(template,40)
rotated = np.subtract(rotated,[2,2])
# Adds some extra bounding boxes as noise
for i in range(8):
rotated = np.append(rotated,[[random.randrange(-20,20), random.randrange(-20,20)]],axis=0)
# Scramble entries in array and return the position change.
rnd_rotated = rotated.copy()
np.random.shuffle(rnd_rotated)
element_positions = []
# After shuffling, looks at which index the "A"-marks has ended up at. For later comparison to see that the algo found the correct answer.
# This is to represent the actual case, where I will get a bunch of unordered bboxes.
rnd_map = {}
indexes_translation = [num2 for num,point in enumerate(rnd_rotated) for num2,point2 in enumerate(rotated) if point[0]==point2[0] and point[1]==point2[1]]
for num,inx in enumerate(indexes_translation):
rnd_map[num]=inx
# algo part 1/3
b_point,angle,_ = find_stamp_rotation(template,rnd_rotated)
# Plot for visualization
legend_list = np.empty((0,2))
leg_template = plt.plot(template[:,0],template[:,1],c='r')
legend_list = np.append(legend_list,[[leg_template[0],'1. template-pattern']],axis=0)
leg_bboxes = plt.scatter(rnd_rotated[:,0],rnd_rotated[:,1],c='b',label="scatter")
legend_list = np.append(legend_list,[[leg_bboxes,'2. bounding boxes']],axis=0)
leg_anchor = plt.scatter(b_point[0],b_point[1],c='y')
legend_list = np.append(legend_list,[[leg_anchor,'3. Discovered bbox anchor point']],axis=0)
# algo part 2/3
# Superimpose A onto B by A[0] to b_point
offset = b_point - template[0]
super_imposed_A = template + offset
# Plot superimposed, but not yet rotated
leg_s_imposed = plt.plot(super_imposed_A[:,0],super_imposed_A[:,1],c='k')
#plt.legend(rubberduckz, "superimposed template on anchor")
legend_list = np.append(legend_list,[[leg_s_imposed[0],'4. Templ superimposed on Bbox']],axis=0)
print("Superimposed A on B by A[0] to {}".format(b_point))
print(super_imposed_A)
# Rotate, now the template should match pattern of bboxes
# algo part 3/4
super_imposed_rotated_A = rotate_array(super_imposed_A,-angle,rot_origin=super_imposed_A[0])
# Show the beautiful match in a last plot
leg_s_imp_rot = plt.plot(super_imposed_rotated_A[:,0],super_imposed_rotated_A[:,1],c='g')
legend_list = np.append(legend_list,[[leg_s_imp_rot[0],'5. final fit']],axis=0)
plt.legend(legend_list[:,0], legend_list[:,1],loc="upper left")
plt.show()
# algo part 4/4
pairs = pair_neighbours_by_distance(super_imposed_rotated_A, rnd_rotated, 10)
print(pairs)
for inx in range(len(pairs)):
bbox_num = pairs[inx]
print("template id:{}".format(inx))
print("bbox#id:{}".format(bbox_num))
#print("original_bbox:{}".format(rnd_map[bbox_num]))
if __name__ == "__main__":
test_example()