从左上到右下的排序坐标

Question

我该如何尝试从左上到右下对不规则数组的点进行排序，如下图所示？

我考虑过的方法是：

• 计算每个点到图像左上角的距离（毕达哥拉斯定理），但对Y坐标应用某种加权，以尝试对同一' row' 上的点进行优先排序distance = SQRT((x * x) + (weighting * (y * y)))

• 将点排序为逻辑行，然后对每一行进行排序。

困难的部分原因是我不知道图像中会出现多少行和多少列以及点阵列的不规则性。任何建议将不胜感激。

Answer 1

尽管这个问题有点老，但我最近在校准相机时遇到了类似的问题。

该算法非常简单，基于本文：

• 找到左上点：min(x+y)
• 找到右上角的点：max(xy)
• 从这些点创建一条直线。
• 计算所有点到直线的距离
  • 如果它小于圆的半径（或阈值）：点在顶线上。
  • 否则：点位于块的其余部分。
• 按 x 值对顶行的点进行排序并保存。
• 重复直到没有剩余点。

我的 python 实现如下所示：

#detect the keypoints
detector = cv2.SimpleBlobDetector_create(params)
keypoints = detector.detect(img)
img_with_keypoints = cv2.drawKeypoints(img, keypoints, np.array([]), (0, 0, 255), 
cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)

points = []
keypoints_to_search = keypoints[:]
while len(keypoints_to_search) > 0:
    a = sorted(keypoints_to_search, key=lambda p: (p.pt[0]) + (p.pt[1]))[0]  # find upper left point
    b = sorted(keypoints_to_search, key=lambda p: (p.pt[0]) - (p.pt[1]))[-1]  # find upper right point

    cv2.line(img_with_keypoints, (int(a.pt[0]), int(a.pt[1])), (int(b.pt[0]), int(b.pt[1])), (255, 0, 0), 1)

    # convert opencv keypoint to numpy 3d point
    a = np.array([a.pt[0], a.pt[1], 0])
    b = np.array([b.pt[0], b.pt[1], 0])

    row_points = []
    remaining_points = []
    for k in keypoints_to_search:
        p = np.array([k.pt[0], k.pt[1], 0])
        d = k.size  # diameter of the keypoint (might be a theshold)
        dist = np.linalg.norm(np.cross(np.subtract(p, a), np.subtract(b, a))) / np.linalg.norm(b)   # distance between keypoint and line a->b
        if d/2 > dist:
            row_points.append(k)
        else:
            remaining_points.append(k)

    points.extend(sorted(row_points, key=lambda h: h.pt[0]))
    keypoints_to_search = remaining_points