Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.6k views
in Technique[技术] by (71.8m points)

sorting - Ordering coordinates from top left to bottom right

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?

Points ordered top left to bottom right

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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

Uppermost line Numerated points


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...