Witam.
Mam do dyspozycji sygnał analogowy z mikrofonu w postaci tablicy 1000 liczb INT.
Jak obliczyć najczęściej występującą częstotliwość w danej próbce? Piszę stroik do gitary na odtwarzacz mp4. Nie mogę uwzględnić żadnych skomplikowanych bibliotek, potrzebuje jak najprostszy algorytm.
Ktoś pomoże?
Zaokrąglij ilość próbek do najbliższej potęgi dwójki wypełniając lukę zerami (jeżeli ich ilość wzrosła). Zrób FFT i znajdź indeks najwyższej magnitudy. Częstotliwość o najwyższej energii obliczysz mnożąc znaleziony indeks przez połowę częstotliwości próbkowania podzieloną przez ilość magnitud zwróconych z FFT.
Co do algorytmu, to może zacznij od How to FFT
EDIT: ... podzieloną nie przez ilość próbek, tylko przez ilość danych zwróconych z transformaty minus jeden. Dla typowej transformaty real(czyli float)->complex(czyli 2float) ich ilość to (ilość_próbek /2 +1).
Gdy zaokrąglisz 1000 do 1024, to otrzymasz 513 liczb kompleksowych z transformaty (513 par po dwa floaty), więc dzielisz połowę częstotliwości próbkowania przez 512.
Magnitudę każdej takiej pary obliczysz pierwiastkując sumę kwadratów sqr(aa + b*b), zaczynając od indeksu 1, który jako pierwszy niesie informację o niezerowej częstotliwości.
I tak jak kolega poniżej napisał - zmień double na float. Double jako nośnik danych w PC wprowadza mniejsze od floata straty podczas przenoszenia danych między pamięcią a procesorem, dlatego tak chętnie jest używany.
Tablicę próbek zmień we floaty w miejscu, albo zmodyfikuj FFT tak, żeby przyjmowało integery zamiast float. Jedna z tych metod na pewno będzie wydajniejsza.
struct complex{float a,b;};
int próbki[1024];
// int2float(próbki,1024);
// hanningwindow(próbki,1024)
complex out[513]; // 513 = 1024/2+1
fft(próbki, out, 1024);
float fmax=cabs(&out[1]); // pierwiastek sumy kwadratów
int imax = 1;
for (i=2; i<=512; i++)
{
float moc = cabs(&out[i]);
// fmax przechowuje aktualne maksimum
if (moc>fmax) {fmax=moc; imax=i;}
}
// tutaj imax jest indeksem częstotliwości o najwyższej energii. Oblicz dominującą częstotliwość
float freqmax = imax * ((samplerate/2)/512);
Gdyby program zbytnio lagował, to może sięgnij po algorytm goertzel'a gdzie obliczasz poziom mocy tylko wybranych częstotliwości, zamiast - jak powyżej - aż 513.
mógłbyś mi to łopatologicznie przedstawić? Mój kompilator nie obsługuje danych typu Double. Obsługuje tylko Float. Dlatego większość algorytmów z sieci mi nie pomaga bo bazują na danych typu Double.
Mam dane w postaci wartości Signed INT. Od czego zacząć?
Sorry za głupie pytania, ale po prostu nie moge załapać tego całego algorytmu.
mozesz wyciagnanc z wykresu fft (widma) czestotliwosc o najwiekszej amplitudzie, aby to zrobic w prosty sposob potrzebujesz bufora z n-probkami gdzie n to wielokrotnosc liczby 2, np: 256, 512, 1024 itd. Zastosuj algorytm fft, maksymalna czestotliwosc jaka zostanie przedstawiona na widmie to = f/2 gdzie f to czestotliwosc probkowania.
przed implementacja fft mozesz poznac dft (discrete fourier transform) - jest proste do napisania, co do doubli to nie musisz sie martiwc bo na floatach tez bedzie dzialac :P
a... dane z fft to siano, zeby otrzymac koncowy wykres musisz okienkowac dane - wiecej na googlach :P
Stokrotnie dzięki za odzew.
Poszperałem trochę i znalazłem taką bibliotekę:
http://sourceforge.net/projects/kissfft/
Podobno to najprostszy i najbardziej skrócony algorytm FFT. Kompilacja przebiegła ok, tylko jeszcze nie wiem jak tego użyć.
Z dokumentacji wyczytałem że obsługuje integerki jako typ danych. Tylko nie wiem jak to wszystko połączyć. I jak ustawić funkcje tak by nie bazowała na DOUBLE tylko na INTEGER.
Czy ktoś pomógłby mi użyć tej biblioteki? Konkretnie jak przygotować dane, jak się odwołać, czy zwolnić pamięć? Bo ta biblioteka wydaje się nie sprowadzać do prostego użycia funkcji FFT(x, y, z);
Mam 1000 sampli audio SIGNED INT Data[1000]. Nie wiem czemu akurat tyle próbek dostarcza system, ale być może zwiększe tą wartość do 1024, jeśli się nie uda to okroje do 512.
BTW. Kompilator przyjmuje Double w kodzie, tylko w trakcie wykonywania kodu okazuje się że nie ma różnicy od Float-a i ma jego ograniczenia.
I jak ustawić funkcje tak by nie bazowała na DOUBLE tylko na INTEGER.
A dlaczego nie na float, przecież masz możliwość użycia tego typu?
PS. myślę, że na google code search znajdziesz prostsze implementacje algorytmu FFT.
Wydawało mi się że bezpieczniej będzie użyć takiej formy w jakiej mam dostępny dźwięk. Poza tym, typ float nie ma jasnych przedziałów maksymalnych i minimalnych wartości. Jak powinienem to skonwertować? int 0 na 0.00000float, -32767int na -1.00000float? Tak to ma wyglądać?
W sumie to mi obojętne, po prostu nie potrafię właściwie użyć tej biblioteki.
Jak powinienem to skonwertować? int 0 na 0.00000float, -32767int na -1.00000float?
Oj panie flasher86, przecież to matematyka na poziomie podstawówki/gimnazjum. Przez ile musisz pomnożyć* -32767.0 żeby w wyniku dało -1.0?
Oj panie, 666, jak tak masz mi pomagać to dziękuje...
Nie pytam jak to pomnożyć (masz mnie za idiote?), tylko czy to taki ma być właśnie wynik. Czy -32767 ma we floatcie być wartością -1. a 32767 1. Czy przedział PCM we floatcie to -1 do 1? O TO SIE PYTAM.
To nie jest istotne w tym projekcie, szukasz tylko indeksu najwyższej wartości by zapewne przedstawić go jako wychylenie lub punkt na panelu czołowym. Gdy znormalizujesz próbki z +-32767 do +-1, to znajdziesz ten sam indeks, tyle że jego wartość będzie 32767 razy mniejsza od wartości bez skalowania próbek.
Dopiero gdybyś chciał wyświetlić widomo częstotliwości, to wtedy istnieje potrzeba znormalizowania wartości próbek do zakiego zakresu, by wynik transformaty zawierał się w założonym zakresie, by sygnał periodyczny o konkretnym "napięciu" podłączony do skalera, po wyjściu z FFT był widoczny na wyświetlaczu jako odcinek o konkretnej długości. Równie dobrze można zeskalować wyjście transformaty. Logarytmiczne, a nawet liniowe przedstawienie wyniku zawsze wymaga punktu odniesienia - w logarytmicznej skali oblicza się logarytm ilorazu dwóch wartości - jedno znasz, to wartość cabs(out[x]), a drugie jest wartością odniesienia - cabs najwyższej możliwej wartości którą może zwrócić transformata w założonym zakresie wartości próbek wejściowych.
A tak nawiasem - co z Ciebie za matematyk? Co stoi na przeszkodzie by samemu przeprowadzić eksperyment podając na wejście FFT sygnał sinusoidalny o "napięciu" N oraz 2N? Jak zmieni się "sygnał" z wyjścia FFT? Dla ułatwienia masz matlaba, audacity i wiele innych programów.
To naturalne, że biblioteka działa na liczbach zmiennoprzecinkowych, transformata tyczy się liczb rzeczywistych (najczęściej).
A jak Ty masz dane w int'ach to nic nie szkodzi, zwykłe rzutowanie i gotowe. Nie ma co normalizować, maksimum i tak będzie w tym samym miejscu.
Co stoi na przeszkodzie by samemu przeprowadzić eksperyment podając na wejście FFT
na przeszkodzie stoi główny problem opisany w tym temacie. Pisałem tu przecież że jeszcze nie uruchomiłem FFT, bo miałem z tym problemy, więc eksperymentować mogę póki co sobie w głowie.
co z Ciebie za matematyk?
Żaden, studiuje anglistykę. A w liceum z matmy miałem 4+, choć nie pamiętam z lekcji typowych wartości próbek PCM w typach danych FLOAT.
Pomimo niektórych tutaj ludzi którzy gardzą moją wiedzą z zakresu matematyki, a nie umieją czytać i zrozumieć mojego problemu... dziękuję za pomoc.
flasher86 napisał(a)
choć nie pamiętam z lekcji typowych wartości próbek PCM w typach danych FLOAT.
do fft podajesz dwie tablice - pierwsza to tablica z "probkami" czyli czesc rzeczywista, do drugiej tablicy wrzucasz same 0.0 i to jest czesc urojona. w wyniku tez otrzymasz dwie tablice - aby je polaczyc zrob tak jak pisze sapero sqrt(real * real + imag * imag) dla kazdego elementu - otrzymasz "widmo", mozesz to przeskalowac znajdujac najwieksza wartosc w tej tablicy (de facto jest to czestotliwosc o najwiekszej amplitudzie).
co do float i integer to pcm dostajesz w integer i zwyczajnie wstaw to jako wartosci tablicy real do fft
edit: jak chcesz zobaczyc czy wszystko dziala ok, zamiast pcm z karty dzwiekowej wstaw wygenerowane dane np: sinusoide o danej czestotliwosci, jezeli wszystko bedzie poprawnie otrzymasz wykres z jedna pionowa linia i lekko opadajacymi harmonicznymi