Sort 2d points into matrix

Question

I have the following problem:

The image is given and I am doing some blob detection. As a limit, let's say I have a maximum of 16 drops, and from each blob I calculate the centroid (position x, y). If no distortion occurs, these centroids are located in a 4x4 equidistant grid, but they can be very distorted. It is assumed that they retain more or less the shape of the grid, but they can be severely distorted.

I need to sort the drops so that I know which one is the closest on the left, right, up and down. Therefore, it would be best to write these drops into a matrix.

If this is not enough, it may happen that I find less than 16, and then I also need to sort them in the matrix.

Does anyone know how this could be effectively solved in Matlab?

Thanks.

[update 1:]

I uploaded the image, and the red numbers are the numbers that my blob detection algorithm assigns to each blob.

The resulting matrix should look like this:

1 2 4 3 6 5 7 8 9 10 11 12 13 16 14 15 

eg. I start with blob 11 and the closest to the right is 12, etc.

[update 2:]

The published solution looks good. In fact, it can happen that one of the outer spots is missing or maybe two ... I know that it makes everything a lot more complicated, and I just want to get an idea if it's worth the time.

These problems arise if you analyze the wavefront with a shack-hartmann wavefront sensor and want to increase the dynamic range :-) The points can really be distorted so that the dividing lines are no longer orthogonal.

Maybe someone knows good literature for classification algorithms.

The best solution is one that can be implemented on the FPGA without much effort, but at this stage it is not so important.

Answer 1

This will work as long as the drops form a square and are relatively ordered:

Picture

code:

 bw = imread('blob.jpg'); bw = im2bw(bw); rp = regionprops(bw,'Centroid'); % Must be a square side = sqrt(length(rp)); centroids = vertcat(rp.Centroid); centroid_labels = cellstr(num2str([1:length(rp)]')); figure(1); imshow(bw); hold on; text(centroids(:,1),centroids(:,2),centroid_labels,'Color','r','FontSize',60); hold off; % Find topleft element - minimum distance from origin [~,topleft_idx] = min(sqrt(centroids(:,1).^2+centroids(:,2).^2)); % Find bottomright element - maximum distance from origin [~,bottomright_idx] = max(sqrt(centroids(:,1).^2+centroids(:,2).^2)); % Find bottom left element - maximum normal distance from line formed by % topleft and bottom right blob A = centroids(bottomright_idx,2)-centroids(topleft_idx,2); B = centroids(topleft_idx,1)-centroids(bottomright_idx,1); C = -B*centroids(topleft_idx,2)-A*centroids(topleft_idx,1); [~,bottomleft_idx] = max(abs(A*centroids(:,1)+B*centroids(:,2)+C)/sqrt(A^2+B^2)); % Sort blobs based on distance from line formed by topleft and bottomleft % blob A = centroids(bottomleft_idx,2)-centroids(topleft_idx,2); B = centroids(topleft_idx,1)-centroids(bottomleft_idx,1); C = -B*centroids(topleft_idx,2)-A*centroids(topleft_idx,1); [~,leftsort_idx] = sort(abs(A*centroids(:,1)+B*centroids(:,2)+C)/sqrt(A^2+B^2)); % Reorder centroids and redetermine bottomright_idx and bottomleft_idx centroids = centroids(leftsort_idx,:); bottomright_idx = find(leftsort_idx == bottomright_idx); bottomleft_idx = find(leftsort_idx == bottomleft_idx); % Sort blobs based on distance from line formed by bottomleft and % bottomright blob A = centroids(bottomright_idx,2)-centroids(bottomleft_idx,2); B = centroids(bottomleft_idx,1)-centroids(bottomright_idx,1); C = -B*centroids(bottomleft_idx,2)-A*centroids(bottomleft_idx,1); [~,bottomsort_idx] = sort(abs(A*reshape(centroids(:,1),side,side)+B*reshape(centroids(:,2),side,side)+C)/sqrt(A^2+B^2),'descend'); disp(leftsort_idx(bsxfun(@plus,bottomsort_idx,0:side:side^2-1))); 

Output:

  2 12 13 20 25 31 4 11 15 19 26 32 1 7 14 21 27 33 3 8 16 22 28 34 6 9 17 24 29 35 5 10 18 23 30 36 

Just wondering if you use this to automate camera calibration through a chessboard or something like that?

---

UPDATE: For a distorted image

 tform = maketform('affine',[1 0 0; .5 1 0; 0 0 1]); bw = imtransform(bw,tform); 

Output:

  1 4 8 16 21 25 2 5 10 18 23 26 3 6 13 19 27 29 7 9 17 24 30 32 11 14 20 28 33 35 12 15 22 31 34 36 

For a rotated image:

 bw = imrotate(bw,20); 

Output:

  1 4 10 17 22 25 2 5 12 18 24 28 3 6 14 21 26 31 7 9 16 23 30 32 8 13 19 27 33 35 11 15 20 29 34 36