在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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元

