第六章 - 图像变换 - 卷积和离散傅里叶变换DFT(cvDFT)

时间:2022-11-23 23:30:41

利用DFT可以大大加快卷积运算的速度,因为卷积定理说明空间域的卷积运算可以转换为频域的乘法运算。

-------------------------------------------------------------------------------

GetOptimalDFTSize

GetOptimalDFTSize
对于给定的矢量尺寸返回最优DFT尺寸

int cvGetOptimalDFTSize( int size0 );
size0
矢量长度.
函数 cvGetOptimalDFTSize 返回最小值 N that is greater to equal to size0, such that DFT of a vector of size N can be computed fast. In the current implementation N=2p×3q×5r for some p, q, r.

The function returns a negative number if size0 is too large (very close to INT_MAX)

 

GetSubRect

GetSubRect
返回输入的图像或矩阵的矩形数组子集的矩阵头

CvMat* cvGetSubRect( const CvArr* arr, CvMat* submat, CvRect rect );
arr
输入数组。
submat
指向矩形数组子集矩阵头的指针。
rect
以0坐标为基准的ROI。
函数 cvGetSubRect 根据指定的数组矩形返回矩阵头,换句话说,函数允许像处理一个独立数组一样处理输入数组的一个指定子矩形。函数在处理时要考虑进输入数组的ROI,因此数组的ROI是实际上被提取的。

 

DFT

DFT
执行一维或者二维浮点数组的离散傅立叶正变换或者离散傅立叶逆变换

#define CV_DXT_FORWARD 0
#define CV_DXT_INVERSE 1
#define CV_DXT_SCALE:2
#define CV_DXT_ROWS: 4
#define CV_DXT_INV_SCALE (CV_DXT_SCALE|CV_DXT_INVERSE)
#define CV_DXT_INVERSE_SCALE CV_DXT_INV_SCALE
void cvDFT( const CvArr* src, CvArr* dst, int flags );
src
输入数组, 实数或者复数.
dst
输出数组,和输入数组有相同的类型和大小。
flags
变换标志, 下面的值的组合:
CV_DXT_FORWARD - 正向 1D 或者 2D 变换. 结果不被缩放.
CV_DXT_INVERSE - 逆向 1D 或者 2D 变换. 结果不被缩放.当然 CV_DXT_FORWARD 和 CV_DXT_INVERSE 是互斥的.
CV_DXT_SCALE - 对结果进行缩放: 用数组元素除以它. 通常, 它和 CV_DXT_INVERSE 组合在一起,可以使用缩写 CV_DXT_INV_SCALE.
CV_DXT_ROWS - 输入矩阵的每个独立的行进行整型或者逆向变换。这个标志允许用户同时变换多个向量,减少开销(它往往比处理它自己要快好几倍), 进行 3D 和高维的变换等等。
函数 cvDFT 执行一维或者二维浮点数组的离散傅立叶正变换或者离散傅立叶逆变换:

N 元一维向量的正向傅立叶变换:
y = F(N)?x, 这里 F(N)jk=exp(-i?2Pi?j?k/N), i=sqrt(-1)
N 元一维向量的逆向傅立叶变换:
x'= (F(N))-1?y = conj(F(N))?y
x = (1/N)?x
M×N 元二维向量的正向傅立叶变换:
Y = F(M)?X?F(N)
M×N 元二维向量的逆向傅立叶变换:
X'= conj(F(M))?Y?conj(F(N))
X = (1/(M?N))?X'
假设时实数数据 (单通道) ,从 IPL 借鉴过来的压缩格式被用来表现一个正向傅立叶变换的结果或者逆向傅立叶变换的输入:

Re Y0,0: Re Y0,1:Im Y0,1:Re Y0,2: Im Y0,2 ... Re Y0,N/2-1 Im Y0,N/2-1 Re Y0,N/2
Re Y1,0: Re Y1,1:Im Y1,1:Re Y1,2: Im Y1,2 ... Re Y1,N/2-1 Im Y1,N/2-1 Re Y1,N/2
Im Y1,0: Re Y2,1:Im Y2,1:Re Y2,2: Im Y2,2 ... Re Y2,N/2-1 Im Y2,N/2-1 Im Y2,N/2
............................................................................................
Re YM/2-1,0 Re YM-3,1 Im YM-3,1 Re YM-3,2 Im YM-3,2 ... Re YM-3,N/2-1 Im YM-3,N/2-1 Re YM-3,N/2
Im YM/2-1,0 Re YM-2,1 Im YM-2,1 Re YM-2,2 Im YM-2,2 ... Re YM-2,N/2-1 Im YM-2,N/2-1 Im YM-2,N/2
Re YM/2,0:Re YM-1,1 Im YM-1,1 Re YM-1,2 Im YM-1,2 ... Re YM-1,N/2-1 Im YM-1,N/2-1 Im YM-1,N/2
注意:如果 N 时偶数最后一列存在(is present), 如果 M 时偶数最后一行(is present).

如果是一维实数的变换结果就像上面矩阵的第一行的形式。利用DFT求解二维卷积

CvMat* A = cvCreateMat( M1, N1, CV_32F );
CvMat* B = cvCreateMat( M2, N2, A->type );

 -------------------------------------------------------------------------------

/*code*/

#include <highgui.h>
#include <cv.h>

int main(int argc, char** argv)
{
int M1 = 2, M2 = 2, N1 = 2, N2 = 2;
CvMat* A = cvCreateMat( M1, N1, CV_32F ); //创建2行2列的32位浮点矩阵
CvMat* B = cvCreateMat( M2, N2, A->type );

//创建矩阵存放卷积结果have only abs(M2-M1)+1×abs(N2-N1)+1 part of the full convolution result
CvMat* convolution = cvCreateMat( A -> rows + B -> rows - 1,
A -> cols + B -> cols - 1, A -> type );
int dft_M = cvGetOptimalDFTSize( A -> rows + B -> rows - 1 ); //对于给定的矢量尺寸返回最优DFT尺寸
int dft_N = cvGetOptimalDFTSize( A -> cols + B -> cols - 1 );
CvMat* dft_A = cvCreateMat( dft_M, dft_N, A -> type );
CvMat* dft_B = cvCreateMat( dft_M, dft_N, B -> type );
CvMat tmp;

// copy A to dft_A and pad dft_A with zeros
cvGetSubRect( dft_A, &tmp, cvRect( 0, 0, A -> cols, A -> rows ) ); //返回输入的图像或矩阵的矩形数组子集的矩阵头
cvCopy( A, &tmp );
cvGetSubRect( dft_A, &tmp, cvRect( A -> cols, 0, dft_A -> cols - A -> cols, A -> rows ) );
cvZero( &tmp );

// no need to pad bottom part of dft_A with zeros because of
// use nonzero_rows parameter in cvDFT() call below
cvDFT( dft_A, dft_A, CV_DXT_FORWARD, A -> rows ); //执行一维或者二维浮点数组的离散傅立叶正变换或者离散傅立叶逆变换

// repeat the same with the second array B
//
cvGetSubRect( dft_B, &tmp, cvRect( 0, 0, B -> cols, B -> rows ) ); //返回输入的图像或矩阵的矩形数组子集的矩阵头
cvCopy( B, &tmp );
cvGetSubRect( dft_B, &tmp, cvRect( B -> cols, 0, dft_B -> cols - B -> cols, B -> rows ) );
cvZero( &tmp );
cvDFT( dft_B, dft_B, CV_DXT_FORWARD, B -> rows );

cvMulSpectrums( dft_A, dft_B, dft_A, 0 ); //两个傅立叶频谱的每个元素的乘法

cvDFT( dft_A, dft_A, CV_DXT_INV_SCALE, convolution -> rows );
cvGetSubRect( dft_A, &tmp, cvRect( 0, 0, convolution -> cols, convolution -> rows ) );
cvCopy( &tmp, convolution );

cvReleaseMat( &dft_A );
cvReleaseMat( &dft_B );

return 0;
}