在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];
}
开始时判断是否在表中,如果在的话迭代搜索,速度很快.....
