sorting 2d points into a matrix

Question

I have the following problem:

An image is given and I am doing some blob detection. As a limit, lets say I have a max of 16 blobs and from each blob I calculate the centroid (x,y position). If no distorion happends, these centroids are arranged in an equidistant 4x4 grid but they could be really much distorted. The assumption is that they keep more or less the grid form but they could be really much warped.

I need to sort the blobs such that I know which one is the nearest left, right, up and down. So the best would be to write these blobs into a matrix.

If this is not enough, it could happen that I detect less then 16 and then I also need to sort them into a matrix.

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

Thanks.

[update 1:]

I uploaded an image and the red numbers are the numbers which my blob detection algorithm assign each blob.

The resulting matrix should look like this with these numbers:

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

e.g. I start with blob 11 and the nearest right number is 12 and so on

[update 2:]

The posted solution looks quite nice. In reality it could happen, that one of the outer spots is missing or maybe two ... I know that this makes everything much more complicated and I just want to get a feeling if this is worth spending time.

These problems arise if you analyze a wavefront with a shack-hartmann wavefront sensor and you want to increase the dynamic range :-) The spots could be really warped such that the dividing lines are not orthogonal any more.

Maybe someone knows a good literature for classification algorithms.

Best solution would be one, which could be implemented on a FPGA without to much effort but this is at this stage not so much important.

Answer 1

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

Image:

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 curious, are you using this to automate camera calibration through a checkerboard or something?

---

UPDATE: For skewed 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 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