c++ - 检测黑白半色调屏幕的角度

Question

以 1 位黑白半色调图像作为输入，我需要提取用于定位点的角度，如下例所示:

我的目的是识别低于特定阈值的所有孤立区域(我可以假设所有点都在 20x20 区域中)并列出这些点的所有中心点。第二步是对这些特定点运行霍夫变换以找到有趣的角度。主要问题是，这似乎会生成相当多的点，使得霍夫变换(i)变慢并且(ii)给出误报，需要依次过滤掉。

我不禁有一种感觉，我把事情变得过于复杂了，而且我忽略了解决这个问题的一个简单而优雅的解决方案。我可能忽略了任何想法或方法吗？

Answer 1

FFT

尝试对图像运行傅立叶变换。屏幕会产生非常尖锐的频率峰值。有了这些峰值，即使从嘈杂的图像中，您也可以相当准确地获得屏幕频率和角度。

我刚刚将您的图像转换回灰度图像:

然后我对其运行 2D fft:

(20,27) 处的亮点及其镜像位置是非常强的峰值，比图像中的其他任何位置都强几个数量级。该曲线显示第 20 行的功率谱:

因此，y 方向上的屏幕频率约为 193/20 = 9.7 像素(图像高度 193)，x 方向上的屏幕频率约为 263/27 = 9.7 像素。这是每个方向上的点间距离，通常需要一些三角学来计算轴。如果需要，可以使用峰值周围的区域从傅里叶功率谱更准确地插值峰值位置。峰也可以相互折叠以减少噪音。

性能？

FFT 是一种计算速度相当快的变换(至少与 Hough 等人相比)，但对于大图像，它需要大量的空间和时间。您可以在几个较小的区域(例如 10 个点)上使用它，这也可以在屏幕不均匀的情况下为您提供帮助。至少在那种情况下它会很快。在我的计算机上运行 128x128 像素 2D FFT 需要 418 us。

FFT 注释

不熟悉傅里叶变换的读者应该意识到我在上面和评论中使用了一些草率的语言。变换本身就是“傅里叶变换”，FFT 只是执行离散傅里叶变换 (DFT) 的一种算法(事实上图像处理标准)。

在计算 FFT 并将结果与​​文献进行比较时，容易让人困惑的一件事是图像中零频率的位置。在大多数教科书中，零频率(实际上是图像像素值的总和)位于图像的中心。大多数 FFT 库将零频率放在左上角(如我的示例所示)。

因此，在教科书中，零频率分量通常靠近变换图像的中心。对于大多数 FFT 库，低频靠近图像的每个角。 (通常有一些名称如 fftshift 的函数可以在这两种表示形式之间进行转换。)

FT 是一个复杂的转换。如果对实值信号(例如单个图像)进行变换，则生成的变换图像将具有很多对称性。这通常不是很重要，但有时它可以用来加快速度或节省一些内存。

单维 FFT 的复杂度为 O(n log n)。在二维情况下，首先对每列运行 FFT，然后对每行运行，因此为 O(x y log y + y x log x) = O(x y (log x + log y)) 或 O(n^2 log n) 对于方形图像。现代计算机的 FFT 速度非常快(并且可以通过使用 GPU 进一步提升)，但每个方向都有数千个点的大型 FFT 是使用错误算法的警告信号。