2009-10-10 150 views
3

我必須在許多圖像的每一行應用卷積過濾器。經典的是360像素的1024x1024像素。在我的使用情況下,它是720圖像560x600像素。最快的方法來計算卷積

問題是,我的代碼比文章中公佈的要慢得多。

我已經實現了樸素的卷積,它需要2m 30s。然後我使用fftw切換到FFT。我使用了複雜的2複數,在每次轉換中過濾兩行。我現在大約20多歲。

事情是文章廣告大約10s甚至更少的經典條件。 所以我想問這裏的專家是否有更快的方法來計算卷積。

數字配方建議避免在dft中完成排序並相應地調整頻域濾波器功能。但是沒有代碼例子說明如何做到這一點。

也許我會在複製數據上失去時間。通過真正的2實數變換,我不必將數據複製到複數值中。不過無論如何我必須填充0。

編輯:請參閱我自己的回答下面的進度反饋和解決此問題的進一步信息。

問(精確再形成):

我正在尋找算法或一段代碼到一個非常快速卷積應用於離散的非周期函數(512至2048的值)。顯然,離散時間傅里葉變換是一條路。儘管如此,我想避免將數據複製和轉換複雜化,並避免重新排序。

+0

什麼編程語言?什麼廣告文章? – 2009-10-10 19:45:17

+0

C或C++。文章「使用GPU硬件的快速錐束CT圖像重建 」,嚴國瑞,田潔,朱壽平,戴亞康,秦成虎,X射線科學與技術雜誌16(2008)225,IOS Press [http: //www.3dmed.net/paper/YanGR_XRay_Fast%20cone-beam%20CT%20image%20reconstruction%20using%20GPU%20hardware.pdf。在8800GTX(8MP)上播放的360張圖像的播放時間爲5.9秒,在512^3上播放,我使用的是280GTX(30MP)。 – chmike 2009-10-11 07:56:44

+0

你的意思是你應用了2D圖像上的一維內核?內核的大小是多少? – Royi 2017-08-04 22:01:11

回答

6

FFT是已知的用於卷積信號的最快技術,並且FFTW是用於計算FFT的最快的免費庫。

獲得最佳性能(硬件之外... GPU是一個好建議)的關鍵是將信號填充到2的冪。使用FFTW時,請在創建計劃時使用「患者」設置以獲得最佳性能。你不太可能會比FFTW提供更快的實現(忘記N.R.)。還要確保使用前向一維FFT的真實版本,而不是複雜版本;如果可以的話,只使用單點(浮點)精度。

如果FFTW沒有爲您降價,那麼我會考慮英特爾(非常實惠)的IPP庫。英特爾處理器針對不同位深度的圖像進行了優化,具有手動調整的FFT。

保羅
CenterSpace軟件您使用的

+4

FFT對於大圖像和大內核非常有用。但是,對於大圖像和小內核,直接(非FFT)卷積通常更快。 – solvingPuzzles 2012-09-25 05:53:36

1

您可能想要將圖像處理添加爲標記。

但是,這篇文章可能是有趣的,尤其是假設圖像是功率或2。您還可以看到他們在哪裏優化FFT。我期望你看到的文章做了一些假設,然後優化了這些方程。

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

如果你想走得快,你可能需要使用GPU來實際做的工作。

這本書可能對你有所幫助,如果你去與GPU: http://www.springerlink.com/content/kd6qm361pq8mmlx2/

+1

非常有趣的閱讀。我應該補充說,FFT計算與GPU卡中的其他處理並行執行。在這個領域中通常的做法是在CPU上執行FFT,因爲據說它比在GPU上執行的處理快得多。不幸的是,在我目前的情況下,FFT濾波較慢。 GPU處理花費約15秒,FFT濾波約20秒。 – chmike 2009-10-11 07:09:47

0

這個答案是收集關於這一問題的進展報告反饋。

編輯10月11日:

我測量並不反映FFT的有效時間的執行時間。我注意到,當我的程序結束時,CPU在系統時間內仍然忙於高達42%10秒。當我等到CPU回到0%時,在重新啓動我的程序之前,我會得到來自GPU處理的15.35s執行時間。如果我註釋掉FFT濾波,我會得到同樣的結果。因此,FFT現在實際上比GPU更快,並且僅僅受到競爭系統任務的阻礙。我還不知道這個系統的任務是什麼。我懷疑它是由於分配一個巨大的堆塊而導致的,我在將它寫入磁盤之前複製處理結果。對於輸入數據我使用內存映射。

我現在將更改我的代碼,以獲得FFT處理時間的準確度量。使其更快速仍然是現實,因爲有優化GPU處理的空間,例如通過流水線傳輸數據進行處理。