컨볼루션을 계산하는 가장 빠른 방법

Question

많은 이미지의 각 행에 컨볼루션 필터를 적용해야 합니다.클래식은 1024x1024 픽셀의 360 이미지입니다.내 사용 사례에서는 720개 이미지 560x600픽셀입니다.

문제는 내 코드가 기사에 광고된 것보다 훨씬 느리다는 것입니다.

저는 순진한 컨볼루션을 구현했으며 2분 30초가 걸립니다.그런 다음 fftw를 사용하여 FFT로 전환했습니다.저는 각 변환에서 두 개의 행을 필터링하여 complex 2 complex를 사용했습니다.저는 이제 20대쯤 됐어요.

문제는 기사가 약 10초 정도 광고하고 있으며 클래식 상태에 대해서는 그보다 더 적은 광고가 있다는 것입니다.그래서 저는 여기 전문가들에게 컨볼루션을 계산하는 더 빠른 방법이 있는지 물어보고 싶습니다.

수치적 방법은 dft에서 정렬을 피하고 이에 따라 주파수 영역 필터 기능을 적용하는 것을 제안합니다.그러나 이를 수행하는 방법에 대한 코드 예제는 없습니다.

어쩌면 데이터를 복사하는 데 시간을 낭비할 수도 있습니다.실수 2 실수 변환을 사용하면 데이터를 복소수 값으로 복사할 필요가 없습니다.하지만 어쨌든 0으로 채워야 합니다.

편집하다:진행 상황 피드백과 이 문제 해결에 대한 추가 정보는 아래 내 답변을 참조하세요.

질문(정확한 재구성):

저는 이산 비주기 함수(512~2048 값)에 매우 빠른 컨볼루션을 적용하는 알고리즘이나 코드 조각을 찾고 있습니다.분명히 이산 시간 푸리에 변환이 갈 길입니다.하지만 데이터 복사 및 컴플렉스로의 변환, 나비 재정렬은 피하고 싶습니다.

Answer 1

FFT는 신호를 연락하는 것으로 알려진 가장 빠른 기술이며 FFTW는 FFT를 컴퓨팅하는 데 사용할 수있는 가장 빠른 무료 라이브러리입니다.

최대 성능을 얻는 핵심 (하드웨어 외부 ... GPU는 좋은 제안입니다)은 신호를 2의 전력으로 채우는 것입니다. FFTW를 사용할 때는 최고의 성능을 얻기 위해 계획을 작성할 때 '환자'설정을 사용하십시오. FFTW가 제공하는 것보다 더 빠른 구현을 손으로 돌릴 가능성은 거의 없습니다 (NR은 잊어 버리십시오). 또한 복잡한 버전이 아닌 전방 1D FFT의 실제 버전을 사용해야합니다. 가능하면 단일 (부동 소수점) 정밀도 만 사용하십시오.

FFTW가 당신을 위해 그것을 자르지 않는다면, 나는 Intel의 (매우 저렴한) IPP 라이브러리를 살펴볼 것입니다. 다양한 비트 깊이의 이미지에 최적화 된 인텔 프로세서 용으로 손을 조정했습니다.

폴
센터 공간 소프트웨어

Answer 2

이미지 처리를 태그로 추가 할 수 있습니다.

그러나이 기사는 이미지가 전원 또는 2라고 가정하면 FFT를 최적화하는 위치를 확인할 수 있습니다. 나는 당신이보고있는 기사가 몇 가지 가정을했고 그에 대한 방정식을 최적화 할 것으로 기대합니다.

http://www.gamasutra.com/view/feature/3993/sponsored_feature_implementation_.php

더 빨리 가고 싶다면 GPU를 사용하여 실제로 작업을 수행 할 수 있습니다.

이 책은 GPU를 사용하면 도움이 될 수 있습니다.http://www.springerlink.com/content/kd6qm361pq8mmlx2/

Answer 3

이 답변은 이 문제에 대한 진행 보고서 피드백을 수집하기 위한 것입니다.

10월 11일 수정:

측정한 실행 시간이 FFT의 유효 시간을 반영하지 않습니다.내 프로그램이 종료될 때 CPU가 시스템 시간 동안 10초 동안 최대 42%까지 여전히 사용 중이라는 것을 알았습니다.CPU가 0%로 돌아갈 때까지 기다렸다가 프로그램을 다시 시작하면 GPU 처리에서 발생하는 실행 시간이 15.35초가 됩니다.FFT 필터링을 주석 처리하면 동일한 시간을 얻습니다.

따라서 FFT는 실제로 현재 GPU보다 빠르며 단순히 경쟁 시스템 작업으로 인해 방해를 받았습니다.이 시스템 작업이 무엇인지 아직 모르겠습니다.처리 결과를 디스크에 쓰기 전에 복사하는 거대한 힙 블록 할당으로 인해 발생하는 것으로 의심됩니다.입력 데이터에는 메모리 맵을 사용합니다.

이제 FFT 처리 시간을 정확하게 측정하기 위해 코드를 변경하겠습니다.예를 들어 데이터를 처리할 파이프라인으로 전송하는 등 GPU 처리를 최적화할 여지가 있기 때문에 더 빠르게 만드는 것은 여전히 ​​현실입니다.