푸리에 변환 부동 소수점 문제

Question

나는 이미지를 위해 푸리에 변환을 분리하여 기존의 (즉 이 아니며이 아님을 의미합니다.) 구현하고 있습니다. 부동 소수점에서 동등 간격의 샘플에서 sin 또는 cos의 한주기에 대한 합계가 이 아니고이 아니며 이것이 빠른 것보다 일반적인 변환에 더 문제가 있다는 것을 알고 있습니다.

알고리즘은 2D 이중 배열과 함께 작동하며 정확합니다. 역변환은 내부에서 이루어지며 (이중 기호 플래그와 비대칭 수식을 사용할 때 조건부 검사를 통해), 접합을 사용하지 않고 수행됩니다. 결과는 거의 100 % 예상과 비슷하므로 세부 사항에 대한 질문은

입니다. 순방향 변환을 수행 할 때 로그와 크기 및 각도를 이미지에 저장하고 다시로드 한 다음 역변환을 수행하면 여러 가지 반올림 오류가 발생합니다 구현 화학식 다른 유형 :

1. F (U, V) = SUM (X = 0 -> M-1)의 합 (Y = 0 -> N-1) F (X, Y) * f (x, y) = 1/M * N * N * 2 * pi * v * y/N * (상기와 같이)

2. F (U, V) = 1/SQRT (M ​​* N) * (상기와 같은)

   F (X, Y) = * (상기와 같은) 1/SQRT (M ​​* N)

첫 번째 것은 비대칭 변환 쌍이고 두 번째는 대칭입니다. 비대칭 쌍을 사용하면 반올림 오류가 이미지의 밝은 부분에서 더 많이 발생합니다 (일부 픽셀은 값 범위 (예 : 256)에서 약간 벗어났습니다). 대칭 쌍을 사용하면 이미지의 일정한 중간 범위 영역에서 오류가 더 많이 발생합니다 (아니요 값 범위를 초과했습니다!). 전체적으로 볼 때 대칭 쌍은 더 많은 반올림 오류를 생성합니다.

다음은 또한 입력에 따라 달라집니다. [0,255]에 저장된 이미지의 반올림 오류가 [0,1]에있을 때와 다릅니다.

그럼 내 질문 : 최적의 정확한 알고리즘을 구현하는 방법 (이론적으로 코드 없음) : 비대칭/대칭 쌍? [0,255] 또는 [0,1]의 입력 값 범위는 무엇입니까? logarithmed 값을 파일에 저장하기 전에 선형 업 스케일링 결과가 얼마나됩니까?

편집 :

이

내 알고리즘은 간단하게 분리 된 비대칭이나 대칭 DFT 공식을 계산합니다. 요인은, 오일러의 ID를 사용하여 실제와 허수 부분으로 분해 확대 실수 부와 허수 부분으로 별도로 sumed됩니다

sum_re += f_re * cos(-mode*pi*((2.0*v*y)/N)) - // mode = 1 for forward, -1 
      f_im * sin(-mode*pi*((2.0*v*y)/N)); // for inverse transform 
// sum_im permutated in the known way and + instead of - 

내 눈에 가장 낮은 반올림 오류를 제공해야 indside 왜냐하면 죄를 그룹화이 값은 (비교 예 : cos(-mode*2*pi*v*y/N)). 왜냐하면 중대한 거짓 둥근 트랜치 멘탈 파이를 여러 번 곱하기/나누기가 아니라 한 번만 나누기 때문입니다. 그렇지 않니?

스케일 팩터 1/M*N1/sqrt(M*N) 또는 각각 분리 최 외측 합 후에 개별적으로 적용된다. 더 좋은데? 아니면 두 분리가 끝날 때 완전히 결합 되었습니까?

좀 더 심오한 분석을 위해 은 직접 input->transform->save-to-file->read-from-file->transform^-1->output 워크 플로를 종료하고 배정도로 직접 비교하도록 선택했습니다. 여기

실제 704x528 8 비트 화상 (델타 입력과 출력의 실수 부 간의 = 최대 절대 차)에 대한 결과 [0,1] 내부로 입력

• 비대칭 수식 : 델타 = 2.6609e-13 ([0,255] 범위에 대해 6.785295e-11에 해당).
• 및 대칭 수식 : delta = 2.65232e-13 ([0,255] 범위의 경우 6.763416e-11에 해당).
• 내부에 [0,255]와 비대칭 공식 : delta = 6.74731e-11이 있습니다.
• [0,255] 안에 대칭 수식 인 delta = 6.7871e-11이 입력되어 있습니다.

이러한 것들은 실제적인 차이점이 없지만, 비대칭 형 변환을 사용한 전체 원거리 입력이 가장 잘 수행됩니다. 나는 값이 16 비트 입력으로 악화 될 수 있다고 생각한다.

일반적으로 실제 변형 반올림 오류보다 파일 저장 (또는 반전) 반올림 오류가 발생하기 전에 크기 조정이 더 많아서 경험이 풍부한 문제가 더 많습니다.

그러나 궁금합니다. 푸리에 변환의 가장 많이 사용되는 구현은 무엇입니까? 대칭 또는 비대칭? 입력 값으로 일반적으로 사용되는 값 범위는 다음과 같습니다. [0,1] 또는 [0,255]? 그리고 로그 스케일에서 보통 보이는 스펙트럼 : [0, 1] 입력의 비대칭 변환 후의 [0, M * N]은 [0,255]로 직접 로그 스케일되거나 [0,255 * M * N]으로 선형 스케일링되기 전에?

Answer 1

신고하신 오류는 작고 일반적이며 일반적으로 무시할 수 있습니다. 결과의 크기를 조정하고 목표 간격 밖의 결과를 끝점에 고정하기 만하면됩니다.

FFT의 라이브러리 구현 (즉, 단일 응용 프로그램 용으로 설계된 것이 아닌 다양한 응용 프로그램에서 일반적으로 사용하도록 작성된 FFT 루틴)에서는 스케일링에 대해 거의 고려하지 않습니다. 루틴은 종종 스케일을 조정하는 데 사용되는 추가 곱셈 연산없이 자연스럽게 산술에 의해 스케일 된 데이터를 리턴합니다. 스케일은 어플리케이션과 관련이없는 경우가 많기 때문에 (예 : 스케일이 무엇이든 상관없이 가장 큰 에너지를 가진 주파수를 찾는 것) 스케일을 곱하기 연산과 한 번만 수행 할 수 있습니다 (예 : 스케일링 대신에) 순방향 변환 및 역변환에서 응용 프로그램은 명시 적으로 한 번만 스케일링하여 동일한 효과를 얻을 수 있습니다). 따라서 스케일링은 종종 필요하지 않기 때문에 라이브러리 루틴에 스케일링을 포함시킬 필요가 없습니다.

데이터가 조정되는 대상 간격은 응용 프로그램에 따라 다릅니다.

스펙트럼을 표시하기 위해 (대수 또는 선형) 어떤 변환을 사용해야하는지에 관해서는 조언 할 수 없습니다. 나는 스펙트럼을 시각화하는 데는 효과가 없다.

Answer 2

스케일링은 반올림 오류를 발생시킵니다. 따라서 솔루션 1 (한 번 확장)은 솔루션 2 (두 번 수행)보다 낫습니다. 마찬가지로, 합계 후에 한 번 스케일링하는 것은 합계 전에 모든 것을 스케일링하는 것보다 낫습니다.

는 2*N에 0에서 y을 실행하거나 +N- -N에서합니까? 수학적으로는 같지만 후자의 경우 정밀도가 약간 더 높습니다.

알아두기, mode 뭐하는거야 cos(-mode * stuff)?