C# での無料で非常に高速で信頼性の高い FFT の実装はどこにありますか?
それは製品に使用できますか?それとも制限はありますか?
AForgeをやった男はかなり良い仕事をしましたが、それは商業的な品質ではありません。学ぶのは素晴らしいことですが、彼も学んでいたことがわかるので、ピクセルあたりの正しいビットを使用する代わりに、画像のサイズを想定するなど、かなり深刻な間違いがあります。
私はその男をノックしているのではありません。私はそのすべてを学んだことで彼を尊敬し、その方法を教えてくれます。彼は現在博士号を取得している、または少なくとももうすぐ博士号を取得する予定なので、彼は本当に賢く、商業的に使用できるライブラリではありません。
Math.Netライブラリには、フーリエ変換や複雑な画像/数値を操作するときに独自の奇妙さがあります。たとえば、私が間違っていない場合は、フーリエ変換を人間が表示できる形式で出力します。これは、変換の画像を見たい場合は人間にとっては便利ですが、データが特定の場所にあることを期待している場合はあまり良くありません。 format(通常のフォーマット)。私はそれについて誤解される可能性がありますが、いくつかの奇妙なことがあったことを覚えているので、実際にフーリエのものに使用された元のコードに行きました、そしてそれははるかにうまくいきました。(ExocortexDSP v1.2 http://www.exocortex.org/dsp/)
Math.netには、FFTからのデータを処理するときに気に入らなかった他のファンキーさもありました。それが何であったかを思い出せません。ただ、ExoCortexDSPライブラリから必要なものを取得する方がはるかに簡単であることがわかりました。私は数学者でもエンジニアでもありません。それらの人にとって、それは完全に理にかなっているかもしれません。
それで!Math.NetのベースとなっているExoCortexからヤンクされたFFTコードを他に何も使用せずに使用しており、うまく機能しています。
そして最後に、C#ではないことはわかっていますが、FFTW(http://www.fftw.org/)の使用を検討し始めました。そして、この男はすでにC#ラッパーを作成しているので、私はそれをチェックするつもりでしたが、実際にはまだ使用していません。(http://www.sdss.jhu.edu/~tamas/bytes/fftwcsharp.html)
ああ!あなたが学校でこれをしているのか仕事でこれをしているのかはわかりませんが、どちらにしても、iTunesUniversityのスタンフォード大学の教授による素晴らしい無料の講義シリーズがあります。
https://podcasts.apple.com/us/podcast/the-fourier-transforms-and-its-applications/id384232849
AForge.netは、高速フーリエ変換をサポートする無料 (オープンソース) ライブラリです。(使用法については Sources/Imaging/ ComplexImage.cs 、実装については Sources/Math/ FourierTransform.csを参照してください)
Math.NET のIridium ライブラリは、高速で定期的に更新される、FFT を含む数学関連関数のコレクションを提供します。LGPL の下でライセンスされているため、商用製品で自由に使用できます。
これは古いスレッドだと思いますが、価値のあるものとして、2010 年に私が書いた無料の (MIT ライセンス) 1 次元の 2 のべき乗長のみの C# FFT 実装を示します。
そのパフォーマンスを他の C# FFT 実装と比較したことはありません。主に Flash/ActionScript と Silverlight/C# のパフォーマンスを比較するために書きました。後者は、少なくとも数値計算でははるかに高速です。
/**
* Performs an in-place complex FFT.
*
* Released under the MIT License
*
* Copyright (c) 2010 Gerald T. Beauregard
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to
* deal in the Software without restriction, including without limitation the
* rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
* sell copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
* IN THE SOFTWARE.
*/
public class FFT2
{
// Element for linked list in which we store the
// input/output data. We use a linked list because
// for sequential access it's faster than array index.
class FFTElement
{
public double re = 0.0; // Real component
public double im = 0.0; // Imaginary component
public FFTElement next; // Next element in linked list
public uint revTgt; // Target position post bit-reversal
}
private uint m_logN = 0; // log2 of FFT size
private uint m_N = 0; // FFT size
private FFTElement[] m_X; // Vector of linked list elements
/**
*
*/
public FFT2()
{
}
/**
* Initialize class to perform FFT of specified size.
*
* @param logN Log2 of FFT length. e.g. for 512 pt FFT, logN = 9.
*/
public void init(
uint logN )
{
m_logN = logN;
m_N = (uint)(1 << (int)m_logN);
// Allocate elements for linked list of complex numbers.
m_X = new FFTElement[m_N];
for (uint k = 0; k < m_N; k++)
m_X[k] = new FFTElement();
// Set up "next" pointers.
for (uint k = 0; k < m_N-1; k++)
m_X[k].next = m_X[k+1];
// Specify target for bit reversal re-ordering.
for (uint k = 0; k < m_N; k++ )
m_X[k].revTgt = BitReverse(k,logN);
}
/**
* Performs in-place complex FFT.
*
* @param xRe Real part of input/output
* @param xIm Imaginary part of input/output
* @param inverse If true, do an inverse FFT
*/
public void run(
double[] xRe,
double[] xIm,
bool inverse = false )
{
uint numFlies = m_N >> 1; // Number of butterflies per sub-FFT
uint span = m_N >> 1; // Width of the butterfly
uint spacing = m_N; // Distance between start of sub-FFTs
uint wIndexStep = 1; // Increment for twiddle table index
// Copy data into linked complex number objects
// If it's an IFFT, we divide by N while we're at it
FFTElement x = m_X[0];
uint k = 0;
double scale = inverse ? 1.0/m_N : 1.0;
while (x != null)
{
x.re = scale*xRe[k];
x.im = scale*xIm[k];
x = x.next;
k++;
}
// For each stage of the FFT
for (uint stage = 0; stage < m_logN; stage++)
{
// Compute a multiplier factor for the "twiddle factors".
// The twiddle factors are complex unit vectors spaced at
// regular angular intervals. The angle by which the twiddle
// factor advances depends on the FFT stage. In many FFT
// implementations the twiddle factors are cached, but because
// array lookup is relatively slow in C#, it's just
// as fast to compute them on the fly.
double wAngleInc = wIndexStep * 2.0*Math.PI/m_N;
if (inverse == false)
wAngleInc *= -1;
double wMulRe = Math.Cos(wAngleInc);
double wMulIm = Math.Sin(wAngleInc);
for (uint start = 0; start < m_N; start += spacing)
{
FFTElement xTop = m_X[start];
FFTElement xBot = m_X[start+span];
double wRe = 1.0;
double wIm = 0.0;
// For each butterfly in this stage
for (uint flyCount = 0; flyCount < numFlies; ++flyCount)
{
// Get the top & bottom values
double xTopRe = xTop.re;
double xTopIm = xTop.im;
double xBotRe = xBot.re;
double xBotIm = xBot.im;
// Top branch of butterfly has addition
xTop.re = xTopRe + xBotRe;
xTop.im = xTopIm + xBotIm;
// Bottom branch of butterly has subtraction,
// followed by multiplication by twiddle factor
xBotRe = xTopRe - xBotRe;
xBotIm = xTopIm - xBotIm;
xBot.re = xBotRe*wRe - xBotIm*wIm;
xBot.im = xBotRe*wIm + xBotIm*wRe;
// Advance butterfly to next top & bottom positions
xTop = xTop.next;
xBot = xBot.next;
// Update the twiddle factor, via complex multiply
// by unit vector with the appropriate angle
// (wRe + j wIm) = (wRe + j wIm) x (wMulRe + j wMulIm)
double tRe = wRe;
wRe = wRe*wMulRe - wIm*wMulIm;
wIm = tRe*wMulIm + wIm*wMulRe;
}
}
numFlies >>= 1; // Divide by 2 by right shift
span >>= 1;
spacing >>= 1;
wIndexStep <<= 1; // Multiply by 2 by left shift
}
// The algorithm leaves the result in a scrambled order.
// Unscramble while copying values from the complex
// linked list elements back to the input/output vectors.
x = m_X[0];
while (x != null)
{
uint target = x.revTgt;
xRe[target] = x.re;
xIm[target] = x.im;
x = x.next;
}
}
/**
* Do bit reversal of specified number of places of an int
* For example, 1101 bit-reversed is 1011
*
* @param x Number to be bit-reverse.
* @param numBits Number of bits in the number.
*/
private uint BitReverse(
uint x,
uint numBits)
{
uint y = 0;
for (uint i = 0; i < numBits; i++)
{
y <<= 1;
y |= x & 0x0001;
x >>= 1;
}
return y;
}
}
http://www.exocortex.org/dsp/は、FFT アルゴリズムを備えたオープンソースの C# 数学ライブラリです。
ここに別のものがあります。Ooura FFT の C# ポート。それはかなり速いです。このパッケージには、MIT ライセンスの下で、オーバーラップ/追加畳み込みおよびその他の DSP も含まれています。
https://github.com/hughpyle/inguz-DSPUtil/blob/master/Fourier.cs
古い質問ですが、まだ Google の結果に表示されます...
非常に制限のない MIT ライセンスの C# / .NET ライブラリは、
https://www.codeproject.com/articles/1107480/dsplib-fft-dft-fourier-transform-library-for-net
このライブラリは、複数のコアでスレッドを並列化するため高速であり、非常に完全ですぐに使用できます。
Numerical Recipes の Web サイト (http://www.nr.com/) には FFT がありますが、入力しても問題ありません。Labview プログラムを C# 2008、.NET 3.5 に変換してデータを取得し、次に、周波数スペクトルを見てください。残念ながら、Math.Net は最新の .NET フレームワークを使用しているため、その FFT を使用できませんでした。私は Exocortex を試してみました - それは機能しましたが、結果は Labview の結果と一致し、問題の原因を知るのに十分な FFT 理論を知りません。そこで数値レシピのサイトでFFTをやってみたらうまくいきました!また、Labview の低サイドローブ ウィンドウをプログラムすることもできました (スケーリング係数を導入する必要がありました)。
Numerical Recipes の章をゲストとしてサイトで読むことができますが、この本は非常に役立つので、購入することを強くお勧めします。Math.NET FFT を使用することになったとしても。
Intelプロセッサ用に調整されたマルチスレッド実装については、IntelのMKLライブラリを確認します。これは無料ではありませんが、魅力的で(100ドル未満)、非常に高速です。ただし、P/Invokesを介してCdllと呼ぶ必要があります。Exocortexプロジェクトは6年前に開発を停止したので、これが重要なプロジェクトである場合は慎重に使用します。