算法将跟随方向的点集进行分组。

注意：由于我最擅长MATLAB和Python这两种语言，所以我将这个问题放在了MATLAB和Python标签下。然而，我欢迎用任何语言给出解决方案。

问题前言：

我使用鱼眼镜头拍摄了一张图像。这张图像由一系列方形物体的图案组成。我想要做的是检测每个方形的质心，然后使用这些点来进行图像的去畸变处理，具体而言，我正在寻找正确的畸变模型参数。需要注意的是，并不需要检测所有的方形。只要大部分方形被检测到，那就完全可以。但这并不是我发布这个问题的重点。我已经编写了参数估计算法，但问题是它需要在图像中出现共线的点。

我想要问的基本问题是，给定这些点，如何最好地将它们分组，使得每个分组都由一条水平线或者垂直线组成？

我的问题背景：

关于我提出问题的背景并不重要，但如果你想知道我从哪里获取的数据，以及进一步了解我提出的问题，请阅读下文。如果你对此不感兴趣，那么你可以直接跳到下面的"问题设置"部分。

我处理的一个示例图像如下所示：

这是一张960 x 960像素的图像。该图像原本分辨率更高，但我对图像进行了子采样，以便加快处理速度。如你所见，图像中有一堆分散在图像中的方形图案。另外，我计算的质心是相对于上述子采样图像的。

我设置的检测质心的流程如下：

1. 进行Canny边缘检测

2. 确定感兴趣区域，以最小化误报。该感兴趣区域基本上是没有任何覆盖其中一侧的黑色胶带的方形。

3. 找到所有独立的封闭轮廓

4. 对于每个独立的封闭轮廓：

a. 进行Harris角点检测

b. 确定结果是否有4个角点

c. 如果有，说明该轮廓属于一个方形，找到该形状的质心

d. 如果没有，跳过该形状

5. 将步骤4中检测到的所有质心放入矩阵中进行进一步的检查。

下面是使用上述图像的示例结果。每个检测到的方形都有四个颜色编码的点，表示其相对于方形本身的位置。对于每个我检测到的质心，我在图像本身的该质心处写上ID。

对于上述图像，检测到了37个方形。

问题设置：

假设我有一些图像像素点存储在一个N x 3的矩阵中。前两列是图像坐标空间中的x（水平）和y（垂直）坐标，其中y坐标是“倒置”的，也就是说正的y向下移动。第三列是与该点关联的ID。

这是在MATLAB中使用这些点绘制一个2D网格并用矩阵的第三列为每个点标记的一些代码。如果你读了上面的背景，这些就是通过上面概述的算法检测到的点。

类似地，在Python中使用numpy和matplotlib，我们有：

我们得到：

回到问题：

你可以看到，这些点或多或少地呈网格状分布，可以看到我们可以在这些点之间形成线条。具体来说，可以看到可以形成水平线和垂直线。

例如，如果你参考我问题背景部分的图像，我们可以看到有5组点可以水平分组。例如，点23、26、29、31、33、34、35、37和36形成一组。点19、21、24、28、30和32形成另一组，依此类推。类似地，在垂直方向上，我们可以看到点26、19、12和3形成一组，点29、21、13和5形成另一组，依此类推。

要问的问题是：在给定点可以是任何方向的情况下，有什么方法可以成功地将点分为水平分组和垂直分组？

条件：

1. 每条线上必须至少有三个点。如果少于这个数量，那么这就不能算作一条线段。因此，点36和10不符合垂直线的要求，同样孤立的点23也不符合垂直线的要求，但它属于第一个水平分组。

2. 上述校准图案可以是任何方向。然而，对于我正在处理的情况，你所看到的背景部分的方向是最差的情况。

预期输出：

输出将是一对列表，其中第一个列表的每个元素给出了形成一条水平线的点的序列。类似地，第二个列表的每个元素给出了形成一条垂直线的点的序列。

因此，水平序列的预期输出将类似于：

MATLAB：horiz_list = {[23, 26, 29, 31, 33, 34, 35, 37, 36], [19, 21, 24, 28, 30, 32], ...}

Python：horiz_list = [[23, 26, 29, 31, 33, 34, 35, 37, 36], [19, 21, 24, 28, 30, 32], ...]

垂直序列的预期输出将类似于：

MATLAB：vert_list = {[26, 19, 12, 3], [29, 21, 13, 5], ....}

Python：vert_list = [[26, 19, 12, 3], [29, 21, 13, 5], ...]

我尝试过的方法：

从算法上讲，我尝试了撤消这些点所经历的旋转。我进行了主成分分析，并尝试根据计算得到的正交基向量将点投影到基向量上，以使点大致处于一个直角矩形网格上。

一旦我做到了这一点，就只是简单地根据水平或垂直坐标的差异来进行一些扫描线处理。你可以根据x或y的值对坐标进行排序，然后检查这些排序后的坐标，并寻找较大的变化。一旦遇到这种变化，就可以将两个变化之间的点分组在一起，形成线条。在每个维度上执行此操作将为您提供水平或垂直分组。

关于主成分分析，这是我在MATLAB和Python中的做法：

MATLAB：

% Step #1 - Get just the data - no IDs
data_raw = data(:,1:2);
% Decentralize mean
data_nomean = bsxfun(@minus, data_raw, mean(data_raw,1));
% Step #2 - Determine covariance matrix
% This already decentralizes the mean
cov_data = cov(data_raw);
% Step #3 - Determine right singular vectors
[~,~,V] = svd(cov_data);
% Step #4 - Transform data with respect to basis
F = V.'*data_nomean.';
% Visualize both the original data points and transformed data
figure;
plot(F(1,:), F(2,:), 'b.', 'MarkerSize', 14);
axis ij;
hold on;
plot(data(:,1), data(:,2), 'r.', 'MarkerSize', 14);

Python：

import numpy as np
import matplotlib.pyplot as plt
# Step #1 and Step #2 - Decentralize mean
centroids_raw = data[:,:2]
mean_data = np.mean(centroids_raw, axis=0)
# Transpose for covariance calculation
data_nomean = (centroids_raw - mean_data).T
# Step #3 - Determine covariance matrix
# Doesn't matter if you do this on the decentralized result
# or the normal result - cov subtracts the mean off anyway
cov_data = np.cov(data_nomean)
# Step #4 - Determine right singular vectors via SVD
# Note - This is already V^T, so there's no need to transpose
_,_,V = np.linalg.svd(cov_data)
# Step #5 - Transform data with respect to basis
data_transform = np.dot(V, data_nomean).T
plt.figure()
plt.gca().invert_yaxis()
plt.plot(data[:,0], data[:,1], 'b.', markersize=14)
plt.plot(data_transform[:,0], data_transform[:,1], 'r.', markersize=14)
plt.show()

以上代码不仅重新投影了数据，还在一个图中同时绘制了原始点和投影后的点。然而，当我尝试重新投影我的数据时，得到的图是这样的：

红色的点是原始图像坐标，蓝色的点是重新投影到基向量上的点，以尝试消除旋转。但它仍然不能完全解决问题。相对于点的位置仍然存在一些方向性，因此如果我尝试进行扫描线算法，位于下方的线或位于侧方的线的点会被错误地分组，这是不正确的。

也许我过于复杂地考虑了这个问题，但是对于你对此问题的任何见解，我都非常感谢。如果答案确实很好，我会倾向于给出很高的奖励，因为我已经在这个问题上卡了很长时间。

我希望这个问题没有太啰嗦。如果你对如何解决这个问题没有想法，那么无论如何，我都感谢你阅读我的问题。

期待你可能有的任何见解。非常感谢！