How do I collect the center of the blobs in chessboard order?

Question

I'm using opencv in python to calibrate the lens. I took a photo in different angles and locations like this:

Then, I ran the blob detector in opencv.

import cv2
import numpy
img = cv2.imread('./image.png', cv2.IMREAD_GRAYSCALE)

params = cv2.SimpleBlobDetector_Params()
params.minThreshold = 50
params.maxThreshold = 255
params.filterByArea = True
params.minArea = 0
params.maxArea = 80
params.filterByColor = True
params.blobColor = 255
params.filterByCircularity = False
params.filterByConvexity = False
params.filterByInertia = False

detector = cv2.SimpleBlobDetector_create(params)

keypoints = detector.detect(img)

The detected blobs are shown in red circles like this.

The object keypoints contains the center location of the detected blobs. I collected the center location like this:

ips = []
for keypoint in keypoints: ips.append((keypoint.pt[0], keypoint.pt[1]))
ips = np.array(ips, np.float32) # image points.

What I want is, I want to store the center location of those red circles in order like cv2. findChessboardCorners.

So I defined a function that sorting along the horizontal axis first and then vertical axis.

def index_sorting_to_checkerboard(arr, shrinker):

    ind1 = arr[:,1].argsort()
    arr = arr[ind1]
    floored = np.floor(arr).astype(int)
    floored_shrinked = np.zeros_like(floored)
    std = floored[0,0]
    for i, (x,y) in enumerate(floored):
        if abs(y-std) <= shrinker: floored_shrinked[i] = (x, std)
        else: 
            std = y
            floored_shrinked[i] = (x, y)

    # sort by the second col, then the first column.
    ind2 = np.lexsort((floored_shrinked[:,0], floored_shrinked[:,1]))
    ret = floored_shrinked[ind2]
    ind3 = ind1[ind2] # An accumulation of all argument changes.

    return ret, ind3

shk, ind = index_sorting_to_checkerboard(ips, 30)
ips = ips[ind]

This function works when the image is low-tilted. However, when the image is tilted a lot like:

it does not works well. That's because the vertical order of the blobs in the upper line can be lower than those in the next line. That is, the vertical location of the blob 13 (upper right) can be lower than blob 14 (below the blob 0) when the images are tilted a lot. So I have to change the value of 'shrinker' manually every time the new images are taken.

Can you suggest me better algorithm to sort in chessboard order that works regardless of the inclination? I think it is possible because cv2.findChessboardCorners always returns the location in this order, but I don't know how it does that.

Answer 1

Since your pattern is elongated, you can estimate the approximate directions of the two axes of the grid (e.g. with PCA).

Based on the estimated direction and the distance between points, you'll be able to search which point is next to a point. So, it seems that the order of the points can be recognized.