O implementare a transformării rapide Fourier (FFT) în C# [închis] (Programare, C#, Prelucrarea Semnalelor, Fft)

AnnaR a intrebat.

Unde pot găsi o implementare gratuită, foarte rapidă și fiabilă a FFT în C#?

Care poate fi folosită într-un produs? Sau există vreo restricție?

9 răspunsuri
torial

AForge.net este o bibliotecă gratuită (open-source) cu suport pentru Fast Fourier Transform. (A se vedea Sources/Imaging/ComplexImage.cs pentru utilizare, Sources/Math/FourierTransform.cs pentru implementare)

Mike Bethany

Tipul care a făcut AForge a făcut o treabă destul de bună, dar nu este de calitate comercială. Este foarte bun pentru a învăța de la el, dar se vede că și el învăța, așa că are câteva greșeli destul de grave, cum ar fi presupunerea dimensiunii unei imagini în loc să folosească corect numărul de biți pe pixel.

Nu îl bat pe tip, îl respect enorm pentru că a învățat toate astea și ne arată cum să facem asta. Cred că acum este doctor în științe sau cel puțin este pe cale să devină, așa că este foarte inteligent, doar că nu este o bibliotecă utilizabilă comercial.

Biblioteca Math.Net are propriile ciudățenii atunci când lucrează cu transformări Fourier și imagini/numere complexe. Cum ar fi, dacă nu mă înșel, scoate transformata Fourier în format vizibil pentru oameni, ceea ce este bine pentru oameni dacă vrei să te uiți la o imagine a transformării, dar nu este atât de bine atunci când te aștepți ca datele să fie într-un anumit format (formatul normal). S-ar putea să mă înșel, dar îmi amintesc doar că au existat unele ciudățenii, așa că am trecut la codul original pe care l-au folosit pentru chestiile Fourier și a funcționat mult mai bine. (ExocortexDSP v1.2 http://www.exocortex.org/dsp/)

Math.net avea și alte ciudățenii care nu-mi plăceau atunci când se prelucrau datele din FFT, nu-mi amintesc ce era, dar știu doar că a fost mult mai ușor să obțin ceea ce am vrut de la biblioteca ExoCortex DSP. Totuși, nu sunt matematician sau inginer; pentru acei tipi s-ar putea să fie perfect logic.

Deci! Folosesc codul FFT smuls din ExoCortex, pe care se bazează Math.Net, fără nimic altceva și funcționează foarte bine.

Și, în sfârșit, știu că nu este C#, dar am început să mă uit la utilizarea FFTW (http://www.fftw.org/). Și acest tip a făcut deja un wrapper C#, așa că am vrut să îl verific, dar nu l-am folosit încă. (http://www.sdss.jhu.edu/~tamas/bytes/fftwcsharp.html)

OH! Nu știu dacă faci acest lucru pentru școală sau pentru muncă, dar oricum există o serie de conferințe gratuite GRELE ținute de un profesor de la Stanford pe iTunes University.

https://podcasts.apple.com/us/podcast/the-fourier-transforms-and-its-applications/id384232849

Comentarii

  • Aș fi interesat de mai multe detalii despre ciudățeniile din implementarea fft-ului Math.NET Iridium – ca să le putem repara! ;). Are legătură cu modul în care sunt tratate numerele complexe? Totuși, nu am idee la ce vă referiți cu „formatul vizibil pentru oameni”. Mostre: mathnet.opensourcedotnet.info/doc/IridiumFFT.ashx –  > Por Christoph Rüegg.
  • fftw are un fel de licență problematică; verificați asta: „Sunt disponibile și licențe non-libere pentru FFTW care permit condiții de utilizare diferite de cele ale GPL.” –  > Por Daniel Mošmondor.
  • Aceasta este o întrebare adresată lui Mike Bethany. Încerc să învăț cum să convertesc datele din domeniul timpului în domeniul frecvenței. Este legătura dvs. cu exocortex modul corect de a face acest lucru? –  > Por T o n y.
  • exo cortext aruncă excepția system out of range fără informații suplimentare pe.net4 . nu funcționează. –  > Por bh_earth0.
Jacob

Math.NET’s Iridium library oferă o colecție rapidă, actualizată în mod regulat, de funcții legate de matematică, inclusiv FFT. Este licențiată sub LGPL, astfel încât sunteți liber să o utilizați în produse comerciale.

Comentarii

  • +1. Math.NET Iridium este excelentă pentru traducerea codului Java (care utilizează Apache commons-math) în .NET datorită corespondenței strânse dintre clasele și metodele fiecăruia. În 95% din timp, tot ce trebuie să faceți este să schimbați numele claselor și metodelor și totul va funcționa. –  > Por finnw.
Gerry Beauregard

Văd că acesta este un subiect vechi, dar pentru ceea ce merită, iată o implementare gratuită (licență MIT) a FFT 1-D power-of-2-length-only C# pe care am scris-o în 2010.

Nu am comparat performanța sa cu alte implementări FFT C#. Am scris-o în principal pentru a compara performanțele Flash/ActionScript și Silverlight/C#. Aceasta din urmă este mult mai rapidă, cel puțin pentru calculul numerelor.

/**
 * 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;
    }

}

Comentarii

  • Acest răspuns este acum complet inutil din cauza linkului care nu duce nicăieri… –  > Por InDieTasten.
  • Îmi pare rău pentru asta. Mi-am eliminat blogul acum câțiva ani, deoarece atrăgea prea mult spam. Din păcate, codul este un pic prea mare pentru a fi pus într-un comentariu aici. Trimiteți-mi un mesaj la g.<mysurname>@ieee.org și voi fi bucuros să vă trimit codul. –  > Por Gerry Beauregard.
  • Puteți actualiza răspunsul, adăugați codul și eliminați link-ul mort. Împărtășirea codului dvs. prin canale private ar fi împotriva spiritului Stack Overflow. –  > Por InDieTasten.
  • S-a făcut. Am încercat să o pun într-un comentariu acum câteva zile, dar era prea mare. Nu mi-a trecut prin cap că limita de mărime ar fi diferită pentru comentarii decât pentru răspunsuri. –  > Por Gerry Beauregard.

http://www.exocortex.org/dsp/ este o bibliotecă de matematică C# cu sursă deschisă, cu algoritmi FFT.

Comentarii

  • Limitată doar la câteva dimensiuni de transformări. –  > Por J D.
Hugh

Iată încă una; un port C# al Ooura FFT. Este rezonabil de rapid. Pachetul include, de asemenea, suprapunerea / adăugarea convoluției și alte câteva chestii DSP, sub licența MIT.

https://github.com/hughpyle/inguz-DSPUtil/blob/master/Fourier.cs

Steve Hageman

O întrebare veche, dar care încă apare în rezultatele Google…

O bibliotecă C# / .NET cu licență MIT foarte puțin restrictivă poate fi găsită la,

https://www.codeproject.com/articles/1107480/dsplib-fft-dft-fourier-transform-library-for-net

Această bibliotecă este rapidă, deoarece are fire paralele pe mai multe nuclee și este foarte completă și gata de utilizare.

Curt

Site-ul Numerical Recipes (http://www.nr.com/) are o FFT, dacă nu vă deranjează să o introduceți. Lucrez la un proiect de conversie a unui program Labview în C# 2008, .NET 3.5 pentru a achiziționa date și apoi a analiza spectrul de frecvențe. Din păcate, Math.Net folosește ultimul framework .NET, așa că nu am putut folosi acea FFT. Am încercat-o pe cea de la Exocortex – a funcționat, dar rezultatele să se potrivească cu cele din Labview și nu cunosc suficientă teorie FFT pentru a ști care este cauza problemei. Așa că am încercat FFT-ul de pe site-ul rețetelor numerice și a funcționat! Am reușit, de asemenea, să programez fereastra Labview cu lobi laterali mici (și a trebuit să introduc un factor de scalare).

Puteți citi capitolul din cartea Numerical Recipes ca invitat pe site-ul lor, dar cartea este atât de utilă încât vă recomand cu căldură să o cumpărați. Chiar dacă veți ajunge să folosiți FFT Math.NET.

Comentarii

  • Aveți grijă cu orice cod pe care îl folosiți din Numerical Recipes. Nu este nimic în neregulă cu codul, problema este licența. Trebuie să plătiți pentru a utiliza codul și nu există excepții pentru aplicații necomerciale sau științifice. Vedeți acest lucru link pentru mai multe informații. –  > Por Bob Bryan.
Paul

Pentru o implementare multi-threaded adaptată pentru procesoarele Intel, aș verifica biblioteca MKL de la Intel. Nu este gratuită, dar este accesibilă (mai puțin de 100 de dolari) și foarte rapidă – dar va trebui să apelați dll-urile C prin P/Invokes. Proiectul Exocortex a încetat să mai fie dezvoltat acum 6 ani, așa că aș fi atent dacă l-aș folosi dacă acesta este un proiect important.

Comentarii