抗锯齿：确定最大频率的首选方法？

Question

我一直在阅读一些关于消除锯齿的问题，它似乎有道理，但有一点我不太确定。您究竟如何找到信号的最大频率（在图形方面）。

我意识到有多个案例，所以我假设有多个答案。但首先让我说出一个简单的算法，我认为这个算法会代表最大频率，所以有人可以告诉我，如果我将其概念化为错误的方式。

假设这是针对1维，有限和灰度图像（以像素为单位）。我是否正确地假设您可以简单地扫描整个像素线（在空间域中）寻找一个最小振荡，并且最小振荡的倒数是最大频率？

防爆值{23,26,28,22,48,49,51,49}

频率：用于修饰设置{}

（1/2）= 0.5：{28， 22}

（1/4）= 0.25：{22,48,49,51}

所以将0.5是最高频率？

什么是理想的方式来计算一个像上面那样的像素线？

并且在更理论上说明，如果您的采样输入是无限的（更像现实世界）呢？一个有效的过程是这样的：

Predetermine a decent interval for point sampling 
Determine max frequency from point sampling 
while(2*maxFrequency > pointSamplingInterval) 
{ 
pointSamplingInterval*=2 
Redetermine maxFrequency from point sampling (with new interval) 
} 

我知道这些算法充满效率低下，所以什么是一些首选的方法？ （不寻找一些疯狂优化，只是从根本上更好的概念）

Answer 1

接近正确的方法是使用傅立叶变换（在实践中，FFT，或快速傅里叶变换）

理论的工作原理如下：如果你有一个镶有彩色/灰度像素，那么我们可以说图像由“空间域”中的像素表示;也就是说，每个单独的数字指定特定空间位置处的图像。

但是，我们真正想要的是在“频域”中表示图像。每个数字代替指定每个像素的每个单独数字，代表整个图像中特定频率的幅度。

从“空间域”转换到“频率域”的工具是傅里叶变换。FT的输出将是一系列数字，指定不同频率的相对贡献。

为了找到最大频率，您可以执行FT，并查看您获得的高频振幅 - 然后它只是从最高频率向下搜索，直到您达到“最低显着性幅度“阈值。

您可以编写自己的FFT，但在实践中更容易使用预打包的库如FFTW

Answer 2

我认为你需要的是傅立叶分析（http://en.wikipedia.org/wiki/Fourier_analysis）的应用。我已经研究过这个，但是从来没有用过它，所以把它用一小撮盐，但我相信，如果你正确地将它应用到你的数字集，你会得到一系列频率，这是该系列的组成部分，然后你可以选择最高的一个。

我不能指出你这样做的一段代码，但我确定它会在某处。

Answer 3

我认为这篇文章来自O'Reilly网站可能对您也有用...... http://www.onlamp.com/pub/a/python/2001/01/31/numerically.html ...在那里他们指的是声音文件的频率分析，但是它给了你这个想法。

Answer 4

你不扫描的最高频率的信号，然后选择您的采样频率：你选择一个足够高的采样频率来捕捉你想捕捉的东西，然后你过滤器的信号到删除高频率。你在之前丢掉一切高于采样率一半的采样率。

上午我假设你可以 简单地扫描整个像素线（在 空间域），寻找一个为 最小的振荡和 逆是最小的振荡 将是最大频率是否正确？

如果你有一行像素，那么采样已经完成。应用抗混叠滤波器已经太晚了。可能出现的最高频率是采样频率的一半（我想是“1/2px”）。

而且在更多的理论注意，如果有什么 您的采样输入是无限 （更像是真正的世界）？

是的，那是当你使用过滤器。首先，你有一个连续的功能，就像一个真实的图像（无限采样率）。然后过滤掉fs/2以上的所有内容，然后在fs处对其进行采样（将图像数字化为像素）。相机实际上并没有任何过滤，这就是为什么你Moire patterns当你的照片砖块等

如果你抗锯齿计算机图形，你不得不认为理想的连续数学的功能首先，并考虑如何过滤它并将其数字化以在屏幕上生成输出。例如，如果你想用计算机产生方波，你不能在最大值和最小值之间天真地交替。这就像抽样一个真实的生活信号而不先过滤。高次谐波回到基带，并导致频谱中出现大量虚假尖峰。您需要生成点，就好像它们是从已过滤的连续数学函数中采样一样：