在DFT中,可以使用FFT來加速,但是如果選個長度很坑爹如某個素數,那FFT就慘了,直接發揮不了作用,這個時候就可以對原始的數據長度進行擴展,最好是2^x(<--一般書上都這樣寫`不是一般性`我們假設長度是2^n,每次我都看的很郁悶),但是發現1,2,4,....中間的跨度很大,如果我的序列長度是 2^n+1 那就得選得2^(n+1)對內存來說是巨大的浪費,OpenCV中選擇的是2^x*3^y*5^z,這樣子選擇256+1時可以選擇270(3^3*2*5),沒必要一下子選擇512,來浪費內存.
當然在OpenCV中是維護了一張表optimalDFTSizeTab,屬于空間換時間的方法,沒有使用如下的方法
int getMultipliers( int n, int *n1, int * n2) { int multiplier, i; if (n == 1 ) { *n1 = 1 ; *n2 = 1 ; return FFT_ERROR; // n = 1 } multiplier = n / 2 ; for (i = multiplier; i >= 2 ; i-- ) { if (n % i == 0 ) { *n1 = i; *n2 = n / i; return FFT_OK; // n = n1 * n2 } } *n1 = 1 ; *n2 = n; return FFT_ERROR; // n - prime number }
當然其實上面的代碼也是在OpenCV中的.
建立表后就可以查找值了.
查找使用傳說中的二分法.
int cv::getOptimalDFTSize( int size0 ) { int a = 0 , b = sizeof (optimalDFTSizeTab)/ sizeof (optimalDFTSizeTab[ 0 ]) - 1 ; if ( (unsigned)size0 >= (unsigned)optimalDFTSizeTab[b] ) return - 1 ; while ( a < b ) { int c = (a + b) >> 1 ; if ( size0 <= optimalDFTSizeTab[c] ) b = c; else a = c+ 1 ; } return optimalDFTSizeTab[b]; }
開始時判斷是否在表中,如果在的話迭代搜索,速度很快.....
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
