FFT 와 DFT 성능 분석

알고리즘을 성능분석을 하는데는 여러가지 방법이 있겠지만 그중 시간복잡도를 이용해 성능을 분석해 볼 것이다.
앞서 말했듯이 DFT는 2중 반복문으로 구성되어있기 때문에 시간 복잡도가 O(N^2)가 나오는 반면,
FFT는 재귀로 함수를 계속 이분할하여 (Divide and Conquer) 시간복잡도가 O(logN)이 나오는 것 까지 알게되었다.
이번엔 직관적인 시간 측정을 통하여 성능이 어느 정도 차이나는지 확인해 볼 것이다.

source code
Python 소스코드 파일첨부 | 음원: NF - The search
run
전체 : 4.54s , FFT : 4.03 , DFT : immeasurable

Data, Moduls Loading and Config

Data Loading

import numpy as np 
import pygame as pg # pygame 이용해서 그래프 그림
import wave # 음원 분석 라이브러리
import time # 시간 측정 라이브러리
from FFT import * # 앞서 만든 FFT
from DFT import dft # 앞서 만든 DFT

# 음원 불러오기 (음원 파일 같이 첨부)
filename = "search.wav"

Basic Exploration

Read its basic properties

# WAV 파일을 'rb'(읽기전용) 모드로 실행
music = wave.open(filename, 'rb')

# 오디오가 모노인지 스테레오인지 확인한다
channels = music.getnchannels()

# 오디오의 샘플당 용량을 확인한다 (1비트 = 8비트, 2바이트 = 16비트)
width = music.getsampwidth()

# 오디오의 초당 샘플 갯수(샘플링 레이트)를 확인한다
rate = music.getframerate()

# 오디오파일의 전체 샘플 수 확인한다
frames = music.getnframes()

# 오디오를 한번에 불러올 샘플 개수 설정한다
chunk_size = 1024

주피터 노트북으로 확인결과

• 오디오가 16비트이다 (output = 2)
• 오디오가 스테레오타입이다 (output = 2)
• 총 샘플 개수는 44100개이다.

The diffence betten Mono and Stereo

WAV 파일에서 Mono와 Stereo 처리 과정에 중요하다

• Mono : 좌우 구분 없음 (Channels = 1)
• Stereo : 왼쪽(L), 오른쪽(R) 2개의 트랙으로 나뉜다 (Channels = 2)

ex> mono = [x0, x1, x2, x3, …] , stereo = [L0, R0, L1, R1, L2, R2, …]
만약 Stereo일 경우 바로 Fourier Transfrom을 할 경우 정상적인 값이 안나온다
따라서 한쪽 채널만 추출해서 처리한다 (x = x[::2])

Fourier Transfrom

Audio Preeprocsssing

# 10초 분량의 음원만 사용 (처리 오래걸림) 
duration_seconds = 10

# 10초 * 초당 샘플수 를 통해 읽을 샘플량을 저장
frames = rate * duration_seconds

# 10초 분량의 데이터를 읽는다(raw binary) -> 숫자아님
data = music.readframes(frames)

music.close()

# 음원이 16비트일 경우 (부호 존재)
if width == 2:
    # 부호의 존재로 인해 부호있는 정수형으로 바꾼다
    audio_data = np.frombuffer(data, dtype=np.int16)

# 음원이 8비트일 경우 (부호 없음)
elif width == 1:
    # 부호가 없기 때문에 부호 없는 정수 (uint8)로 바꾼다
    audio_data = np.frombuffer(data, dtype=np.uint8)
else:
    raise ValueError("파일 값 오류")

# 스테레오 일 경우 한쪽 음원만 사용한다
if channels == 2:
    audio_data = audio_data[::2]  # 2의 배수만 사용

# 전체 코드 시간 측정
start = time.time()

Discrete Fourier Transform

# 푸리에 변환 부분 따로 측정
ft_start = time.time()

dft_transfrom = dft(audio_data)

ft_end = time.time()

Fast Fourier Transform

ft_start = time.time()

fft_transfrom = FFT(audio_data)

ft_end = time.time()

Visualization

Normalization

# 일부 주파수만 시각화 한다
magnitude = np.abs(fft_transfrom)[:400]

# ft 절댓값이 너무 크면 가독성이 떨어지기 때문에 0~1 비율 맞춰줌
magnitude = magnitude / np.max(magnitude) * 180 

Drawing Audio Spectrum

pg.init()
WIDTH, HEIGHT = 800, 400
screen = pg.display.set_mode((WIDTH, HEIGHT))

screen.fill((20, 10, 30)) 
bar_color = (255, 102, 255) 

# 그래프는 화면 중앙에 상하 대칭으로 그린다
for i, mag in enumerate(magnitude):
    x = i * 2
    y_center = HEIGHT // 2
    pg.draw.rect(screen, bar_color, (x, y_center - mag, 1, mag))
    pg.draw.rect(screen, bar_color, (x, y_center, 1, mag))

pg.display.flip()
end = time.time()

print(end - start)
print(ft_end - ft_start)

running = True
while running:
    for event in pg.event.get():
        if event.type == pg.QUIT:
            running = False

pg.quit()

Output:

위 : 전체 코드 , 아래 : fft 시간

Conclusion

• 위에 시간 결과값은 FFT알고리즘의 시간 측정이다
• DFT는 시간을 1초까지 줄였는데도 오래걸려서 측정 불가
• 샘플수가 40000개가 넘어가서 더 많이 차이나는 것으로 보임

Source Code

import numpy as np
import pygame as pg
import wave
import time
from FFT import *
from DFT import dft

filename = "search.wav"
music = wave.open(filename, 'rb')
channels = music.getnchannels()
width = music.getsampwidth()
rate = music.getframerate()
frames = music.getnframes()
chunk_size = 1024

duration_seconds = 10
frames = rate * duration_seconds
data = music.readframes(frames)
music.close()

if width == 2:
    audio_data = np.frombuffer(data, dtype=np.int16)

elif width == 1:
    audio_data = np.frombuffer(data, dtype=np.uint8)
else:
    raise ValueError("파일 값 오류")

if channels == 2:
    audio_data = audio_data[::2]

start = time.time()

ft_start = time.time()
fft_transfrom = FFT(audio_data)
ft_end = time.time()

magnitude = np.abs(fft_transfrom)[:400] 
magnitude = magnitude / np.max(magnitude) * 180

pg.init()
WIDTH, HEIGHT = 800, 400
screen = pg.display.set_mode((WIDTH, HEIGHT))

screen.fill((20, 10, 30)) 
bar_color = (255, 102, 255) 

for i, mag in enumerate(magnitude):
    x = i * 2
    y_center = HEIGHT // 2
    pg.draw.rect(screen, bar_color, (x, y_center - mag, 1, mag))  # 위
    pg.draw.rect(screen, bar_color, (x, y_center, 1, mag))        # 아래

pg.display.flip()
end = time.time()

print(end - start)
print(ft_end - ft_start)

running = True
while running:
    for event in pg.event.get():
        if event.type == pg.QUIT:
            running = False

pg.quit()

추가 : 실시간 오디오 스펙트럼

음악 전체의 오디오 스펙트럼을 표현하는 것 뿐만 아닌 실시간으로 표현할 수 있다

Data Loading

import pygame as pg
import numpy as np
import wave
import sys
from FFT import *
from DFT import *

filename = "search.wav"
music = wave.open(filename, 'rb')
channels = music.getnchannels()
width = music.getsampwidth()
rate = music.getframerate()
frames = music.getnframes()
chunk_size = 1024

Play a audio file

pg.mixer.init(frequency=rate)
pg.mixer.music.load(filename)
pg.mixer.music.play()

Pygame init

pg.init()
screen = pg.display.set_mode((800, 400))
clock = pg.time.Clock()

Audio preprocessing

running = True
while running and music.tell() < frames:
    data = music.readframes(chunk_size)
    if width == 2:
        audio_data = np.frombuffer(data, dtype=np.int16)
    else:
        audio_data = np.frombuffer(data, dtype=np.uint8)
    if channels == 2:
        audio_data = audio_data[::2] 

• 음악이 실행되고 프레임이 끝날때 까지 반복

Fourier Transfrom

    fft_result = FFT(audio_data)
    magnitude = np.abs(fft_result)[:200]
    if np.max(magnitude) > 0:
        magnitude = magnitude / np.max(magnitude) * 300 

Visualization

    screen.fill((20, 10, 30)) 
    bar_color = (255, 102, 255)
    for event in pg.event.get():
        if event.type == pg.QUIT:
            running = False

    for i, mag in enumerate(magnitude):
        x = i * 4
        y_center = 200 
        height = mag

        pg.draw.rect(screen, bar_color, (x, y_center - height, 3, height))
        pg.draw.rect(screen, bar_color, (x, y_center, 3, height))

    pg.display.flip()
    clock.tick(60)

music.close()
pg.quit()

전체 코드

import pygame as pg
import numpy as np
import wave
import sys
from FFT import *
from DFT import *

filename = "search.wav"
music = wave.open(filename, 'rb')
channels = music.getnchannels()
width = music.getsampwidth()
rate = music.getframerate()
frames = music.getnframes()
chunk_size = 1024

pg.mixer.init(frequency=rate)
pg.mixer.music.load(filename)
pg.mixer.music.play()

pg.init()
screen = pg.display.set_mode((800, 400))
clock = pg.time.Clock()

running = True
while running and music.tell() < frames:
    data = music.readframes(chunk_size)
    if width == 2:
        audio_data = np.frombuffer(data, dtype=np.int16)
    else:
        audio_data = np.frombuffer(data, dtype=np.uint8)
    if channels == 2:
        audio_data = audio_data[::2]

    fft_result = FFT(audio_data)
    magnitude = np.abs(fft_result)[:200]
    if np.max(magnitude) > 0:
        magnitude = magnitude / np.max(magnitude) * 300 


    screen.fill((20, 10, 30))
    bar_color = (255, 102, 255)
    for event in pg.event.get():
        if event.type == pg.QUIT:
            running = False

    for i, mag in enumerate(magnitude):
        x = i * 4
        y_center = 200
        height = mag

        pg.draw.rect(screen, bar_color, (x, y_center - height, 3, height))
        pg.draw.rect(screen, bar_color, (x, y_center, 3, height))

    pg.display.flip()
    clock.tick(60)

music.close()
pg.quit()