排序2D点为矩阵 [英] sorting 2d points into a matrix
问题描述
我有以下问题：
这是图像，并给出我做了一些斑点检测。作为一个限制，可以说我有一个最大的16斑点，并且从每个斑点我计算出质心（X，Y位置）。 如果没有distorion happends，这些质心等距离放置，4x4网格，但他们可能是非常多的扭曲。 的假设是，他们保持或多或少的坐标格，但他们可能是非常多的扭曲。
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.
如果这还不够，它可能发生，我发现小于16，然后我还需要将其整理成一个矩阵。
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.
有谁知道这可能在Matlab中有效解决呢？
Does anyone know how this could be efficiently solved in Matlab?
感谢。
[更新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
例如。我开始与斑点11，最近的权数为12等
e.g. I start with blob 11 and the nearest right number is 12 and so on
[更新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.
这些问题，如果你分析一个窝棚-Hartmann波前传感器波前出现，并要增加动态范围:-) 这些点可能是非常扭曲，使得分割线不是正交了。
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.
最好的解决办法是一个，这可能是在FPGA中实现，但无大的力气，但是这是在这个阶段没有那么多重要的。
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.
推荐答案
这将只要斑点形成一个正方形和相对有序的工作：
This will work as long as the blobs form a square and are relatively ordered:
图片：
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)));
输出：
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);
输出：
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
这篇关于排序2D点为矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
