将 2d 点排序为矩阵

Question

我有以下问题：

给出了一个图像，我正在做一些斑点检测。作为限制，假设我最多有 16 个 blob，并且从每个 blob 我计算质心（x，y 位置）。如果没有发生失真，这些质心会排列在等距的 4x4 网格中，但它们可能会非常扭曲。假设它们或多或少保持网格形式，但它们可能真的很扭曲。

我需要对 blob 进行排序，以便我知道哪个是最近的左、右、上和下。所以最好的办法是将这些 blob 写入矩阵。

如果这还不够，我可能会检测到少于 16 个，然后我还需要将它们排序为一个矩阵。

有谁知道如何在 Matlab 中有效地解决这个问题？

谢谢。

[更新1：]

我上传了一张图片，红色数字是我的斑点检测算法分配给每个斑点的数字。

生成的矩阵应如下所示：

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

例如，我从 blob 11 开始，最近的正确数字是 12，依此类推

[更新2：]

发布的解决方案看起来很不错。实际上，它可能会发生，缺少一个或两个外部点......我知道这会让一切变得更加复杂，我只是想感受一下是否值得花时间。

如果您使用 shack-hartmann 波前传感器分析波前并且想要增加动态范围，则会出现这些问题:-) 斑点可能确实扭曲，使得分界线不再正交。

也许有人知道分类算法的好文献。

最好的解决方案是一个，它可以毫不费力地在 FPGA 上实现，但这在现阶段并不是那么重要。

Answer 1

只要斑点形成正方形并且相对有序，这就会起作用：

图像：

代码：

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)));

输出：

 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

只是好奇，您是否使用它通过棋盘格或其他方式自动校准相机？

更新：对于倾斜的图像

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

输出：

 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

对于旋转图像：

bw = imrotate(bw,20);

输出：

 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