将2D点排序为矩阵

Question

将2D点排序为矩阵

5

我有以下问题：

给定一张图像，我正在进行一些斑点检测。作为一个限制条件，假设我最多有16个斑点，并且从每个斑点中计算质心（x,y位置）。如果没有畸变发生，这些质心会按照等距4x4网格排列，但它们可能非常扭曲。假设它们保持更或少的网格形式，但它们可能非常扭曲。

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

如果这还不够，可能会检测到少于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上实现而不需要太多努力，但在这个阶段这并不是很重要。

- steffenmauch

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JustinBlaber · Accepted Answer

只要这些 blob 形成了一个正方形并且相对有序，这个方法就可以奏效：

图片：

enter image description here

代码：

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

输出：

enter image description here

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

enter image description here

输出：

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

enter image description here

输出：

 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