algorithm - 将 2d 点排序为矩阵

Question

我有以下问题:

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

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

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

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

谢谢。

[更新 1:]

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

结果矩阵应该是这样的，包含这些数字:

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

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

[更新 2:]

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

如果您使用 shack-hartmann 波前传感器分析波前并且想要增加动态范围，就会出现这些问题 :-)这些 Blob 可能真的扭曲了，以至于分界线不再正交。

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

最好的解决方案是一个可以在 FPGA 上实现而不需要太多努力的解决方案，但在现阶段这不是那么重要。

Answer 1

只要 Blob 形成一个正方形并且相对有序，这就会起作用:

图片:

代码:

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