从左上到右下的排序坐标 [英] Ordering coordinates from top left to bottom right

问题描述

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

我考虑过的方法是:

• 计算每个点到图像左上角的距离(毕达哥拉斯定理)，但对 Y 坐标施加某种加权，以尝试对同一' row '例如距离= SQRT((x * x)+(加权*(y * y)))

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

部分困难在于，我不知道图像中将出现多少行和多少列以及点阵列的不规则性.任何建议将不胜感激.

解决方案

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

该算法非常简单，基于

How can I go about trying to order the points of an irregular array from top left to bottom right, such as in the image below?

Methods I've considered are:

• calculate the distance of each point from the top left of the image (Pythagoras's theorem) but apply some kind of weighting to the Y coordinate in an attempt to prioritise points on the same 'row' e.g. distance = SQRT((x * x) + (weighting * (y * y)))

• sort the points into logical rows, then sort each row.

Part of the difficulty is that I do not know how many rows and columns will be present in the image coupled with the irregularity of the array of points. Any advice would be greatly appreciated.

解决方案

Even though the question is a bit older, I recently had a similar problem when calibrating a camera.

The algorithm is quite simple and based on this paper:

• Find the top left point: min(x+y)
• Find the top right point: max(x-y)
• Create a straight line from the points.
• Calculate the distance of all points to the line
  • If it is smaller than the radius of the circle (or a threshold): point is in the top line.
  • Otherwise: point is in the rest of the block.
• Sort points of the top line by x value and save.
• Repeat until there are no points left.

My python implementation looks like this:

#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

这篇关于从左上到右下的排序坐标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！