《第四讲傅里叶变换》由会员分享，可在线阅读，更多相关《第四讲傅里叶变换（93页珍藏版）》请在金锄头文库上搜索。
1、Digital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理第四讲傅里叶变换7/30/20241JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换傅里叶变换主要内容n图像变换基础图像变换基础n傅里叶变换定义傅里叶变换定义n傅里叶变换的性质傅里叶变换的性质n快速傅里叶变换快速傅里叶变换7/30/20242JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础什么是图像变换？为了有效地和快速的对图像进行
2、处理和分析，为了有效地和快速的对图像进行处理和分析，常常需要常常需要将原定义在图像空间的图像将原定义在图像空间的图像以某种形式以某种形式转换到另外一些空间转换到另外一些空间，并利用这些空间的特有性，并利用这些空间的特有性质方便地进行一定的加工，最后再转换回图像空质方便地进行一定的加工，最后再转换回图像空间以得到所需的效果。这些转换方法称为图像变间以得到所需的效果。这些转换方法称为图像变换技术。换技术。本讲着重介绍和讨论的本讲着重介绍和讨论的傅里叶变换傅里叶变换，就是一种，就是一种广泛应用的图像变换技术。广泛应用的图像变换技术。7/30/20243JINAN UniversityDigital
3、Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础为什么要学习图像变换？从某种意义来说，从某种意义来说，使用不同的空间来描述图像，就好比使用不同的空间来描述图像，就好比使用不同的语言来表达观点使用不同的语言来表达观点。能讲两种语言的人常常会发。能讲两种语言的人常常会发现，在表达某些观点时，一种语言会比另一种语言优越。现，在表达某些观点时，一种语言会比另一种语言优越。类似的，图像处理的分析者在解决某一问题时会在不同类似的，图像处理的分析者在解决某一问题时会在不同的空间来回切换。的空间来回切换。掌握图像变换技术，就可以在不同的空掌握图像变换技术，就可以
4、在不同的空间下思考问题，并利用不同空间的优越性解决问题间下思考问题，并利用不同空间的优越性解决问题，这种，这种能力是非常有用的。能力是非常有用的。傅里叶变换也被喻为描述图像的第二种语言。傅里叶变换也被喻为描述图像的第二种语言。7/30/20244JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础“傅里叶变换”将图像变成怎样的空间？我们之前所讨论的、大家所熟悉的图像空间为我们之前所讨论的、大家所熟悉的图像空间为“空域空域”空间。经过傅里叶变换，则可获得图像空间。经过傅里叶变换，则可获得图像的的“频域频域
5、”空间。空间。那么什么是那么什么是“频域频域”呢？呢？这个就要从这个就要从信号的分解信号的分解开始说起。开始说起。（所谓信号，就是带有信息的物理量。对于灰度图像，像（所谓信号，就是带有信息的物理量。对于灰度图像，像素点的灰度值就是其携带的信号。因此，图像本质上是一素点的灰度值就是其携带的信号。因此，图像本质上是一个二维信号的集合。）个二维信号的集合。）7/30/20245JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础信号分解概述信号分解是利用信号分解是利用“化繁为简、化整为零化繁为简、化整为零”的
6、思的思路，将一个复杂信号分解为一系列路，将一个复杂信号分解为一系列“简单简单”信号信号（或称基元信号）的（或称基元信号）的特定组合（叠加）特定组合（叠加）。问题问题1 1：怎样的信号是我们需要的怎样的信号是我们需要的“简单简单”信号信号？问题问题2 2：它们遵循什么样的组合规律？它们遵循什么样的组合规律？7/30/20246JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础信号分解 “简单”信号如果一组信号彼此如果一组信号彼此完全不相似完全不相似，它们，它们互相不包互相不包含对方的分量含对方的分量，则
7、这组信号就是我们需要的简单，则这组信号就是我们需要的简单信号。信号。在数学上，有个专门的术语描述这种性质，叫在数学上，有个专门的术语描述这种性质，叫“正交正交”性。性。（信号是物理术语，在数学世界，信号等价于函数）（信号是物理术语，在数学世界，信号等价于函数）7/30/20247JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础“正交”函数的数学描述两个函数正交的充要条件是：它们的两个函数正交的充要条件是：它们的内积为内积为0（内积描述相似性）。（内积描述相似性）。函数函数f1(t)和函数和函数f2(
8、t)在区间在区间(t1,t2)上的内积：上的内积：函数集函数集gn(t),1nN的在区间的在区间(t1,t2)上正交的条件：上正交的条件：7/30/20248JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础哪些函数集是“正交”的呢？（1）在实函数中，有一组自然、和谐的函数非常）在实函数中，有一组自然、和谐的函数非常适合作为正交函数集适合作为正交函数集正、余弦函数正、余弦函数。对于任何的：对于任何的：在一个周期以内在一个周期以内的面积相加起来总是零。的面积相加起来总是零。7/30/20249JINAN
9、 UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础正余弦函数集的“正交”性实例7/30/202410JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础哪些函数集是“正交”的呢？（2）在复变函数中，可以证明，）在复变函数中，可以证明，复指数函数复指数函数集集也是一个完备的正交函数集。也是一个完备的正交函数集。从某种意义上来讲，从某种意义上来讲，复指数函数与三角函数复指数函数与三角函数在本质上是一致的在本质上是一致的，欧拉
10、公式欧拉公式揭示了二者之间的揭示了二者之间的关系：关系：7/30/202411JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础信号分解概述信号分解是利用信号分解是利用“化繁为简、化整为零化繁为简、化整为零”的思的思路，将一个复杂信号分解为一系列路，将一个复杂信号分解为一系列“简单简单”信号信号（或称基元信号）的（或称基元信号）的特定组合（叠加）特定组合（叠加）。问题问题1：怎样的信号是我们需要的怎样的信号是我们需要的“简单简单”信号信号？问题问题2：它们遵循什么样的组合规律？它们遵循什么样的组合规律
11、？正交信号正交信号正、余弦三角函数正、余弦三角函数复指数函数复指数函数7/30/202412JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础信号分解为三角函数周期为周期为T的信号的信号f(t)，可以展开成三角函数（信号）的叠，可以展开成三角函数（信号）的叠加：加：即：即：上述展开式称为上述展开式称为三角形式的傅里叶级数三角形式的傅里叶级数。其中，。其中，=2/T是信号的角频率，是信号的角频率，an和和bn为傅里叶系数。为傅里叶系数。已知已知f(t)，傅傅里叶系数里叶系数a0、an、bn如何确定呢？如
12、何确定呢？7/30/202413JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础傅里叶系数的确定如求如求ai，只需在展开式两边乘上，只需在展开式两边乘上cos(it)，然后周期区间然后周期区间内求积分，由于内求积分，由于三角函数集的正交性三角函数集的正交性，可以发现，等式的，可以发现，等式的右边除了右边除了aicos(it) cos(it)这一项不为零，其它项均为零，这一项不为零，其它项均为零，从而能够求出系数从而能够求出系数ai。=0=0仅当仅当n=i时不为时不为07/30/202414JINAN
13、 UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础傅里叶系数的确定（续）根据上述方法，可求得三角傅里叶系数：根据上述方法，可求得三角傅里叶系数：（2）余弦分量系数：）余弦分量系数：（3）正弦分量系数：）正弦分量系数：（1）直流分量系数（零频系数）：）直流分量系数（零频系数）：7/30/202415JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础信号分解为复指数函数傅里叶系数傅里叶系数Fn确可以按以下公式求得：确可以按
14、以下公式求得：若选用复指数正交函数集来进行傅里叶级数展开，若选用复指数正交函数集来进行傅里叶级数展开，则周期函数（信号）的展开形式为：则周期函数（信号）的展开形式为：7/30/202416JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础“傅里叶变换”将图像变成怎样的空间？我们之前所讨论的、大家所熟悉的图像空间我们之前所讨论的、大家所熟悉的图像空间为为“空域空域”空间。经过傅里叶变换，则可获得图空间。经过傅里叶变换，则可获得图像的像的“频域频域”空间。空间。那么什么是那么什么是“频域频域”呢？呢？这个
15、就要从这个就要从信号的分解信号的分解开始说起。开始说起。一个信号可以用许多简单的信号一个信号可以用许多简单的信号“加起来加起来”来表示来表示如何用所谓的如何用所谓的“正交性正交性”来找出这些简单信号来找出这些简单信号如何计算叠加的系数如何计算叠加的系数7/30/202417JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础“频域”空间举例假设有这样的一个信号假设有这样的一个信号f (t)，它可以用下列正弦波表示：它可以用下列正弦波表示：有幅度有幅度A、频率、频率四组对：四组对：我们可以认为这四组数对唯
16、一确定了信号我们可以认为这四组数对唯一确定了信号f (t)，也就也就是说，这四组数对是信号是说，这四组数对是信号f (t)的另一种表达方式。它们所的另一种表达方式。它们所构成的空间就是构成的空间就是“频域频域”空间，与时（空）域空间完全等空间，与时（空）域空间完全等价。价。7/30/202418JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理图像变换基础图像变换基础“频域”空间（续）tf时域空间时域空间A频域空间频域空间7/30/202419JINAN UniversityDigital Image Processing制
17、作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换傅里叶变换主要内容n图像变换基础图像变换基础n傅里叶变换定义傅里叶变换定义n傅里叶变换的性质傅里叶变换的性质n快速傅里叶变换快速傅里叶变换7/30/202420JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义一维连续傅里叶变换及反变换单变量连续函数单变量连续函数f (x)的傅里叶变换的傅里叶变换F()定义为：定义为：其中其中x为为时域时域变量，变量，为为频域频域变量，变量，j2=-1给定给定F()，通过傅里叶反变换可以得到通过傅里叶反变换可以得到f
18、 (x)：7/30/202421JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义说明傅傅立立叶叶变变换换中中的的变变量量通通常常称称为为频频率率变变量量，这这个名称源于个名称源于欧拉公式欧拉公式中的指数项：中的指数项：如如果果把把傅傅立立叶叶变变换换的的积积分分解解释释为为离离散散项项的的和和，则则易易推推出出F()是是一一组组sin和和cos函函数数项项的的无无限限和和，其中其中的每个值决定了其相应的每个值决定了其相应cos、sin函数的频率函数的频率。7/30/202422JINAN Uni
19、versityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义幅度、相位、能量（功率）谱由上公式可以看出，傅里叶变换结果是一个由上公式可以看出，傅里叶变换结果是一个复数表达复数表达式式，设，设F()的实部为的实部为R()，虚部为，虚部为I()，则：，则：复指数形式：复指数形式：幅度谱：幅度谱：相位谱相位谱：能量谱能量谱：7/30/202423JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义二维连续傅里叶变换及反变换二维连续函数二
20、维连续函数f (x, y)的傅里叶变换的傅里叶变换F(,)定义为：定义为：其中其中x,y为时域变量，为时域变量，,为频域变量，为频域变量，j2=-1给定给定F(,)，通过傅里叶反变换可以得到通过傅里叶反变换可以得到f (x, y)：7/30/202424JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义幅度、相位、能量（功率）谱幅度谱：幅度谱：相位谱相位谱：能量谱能量谱：二维傅里叶变换结果的复指数形式：二维傅里叶变换结果的复指数形式：7/30/202425JINAN UniversityDigit
21、al Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义一维离散傅里叶变换（DFT）及反变换单变量离散函数单变量离散函数f (x)(x = 0, 1, , M-1)的傅里的傅里叶变换叶变换F()定义为：定义为：给定给定F()，通过傅里叶反变换可以得到通过傅里叶反变换可以得到f(x)： = 0, 1, , M-1x = 0, 1, , M-17/30/202426JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义二维离散傅里叶变换及反变换（数字图像）
22、图像尺寸为图像尺寸为MN的函数的函数f (x,y)的的DFT为：为：给定给定F(,)，通过反通过反DFT变换可以得到变换可以得到f (x,y)： = 0, 1, , M-1， = 0, 1, , N-1x = 0, 1, , M-1， y = 0, 1, , N-17/30/202427JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义离散傅里叶变换DFT的计算DFT的计算的计算例例：一一维维函函数数的的四四个个采采样样值值为为f(0)=2, f(1)=3, f(2)=f(3)=4。x012123
23、437/30/202428JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义离散傅里叶变换DFT的计算（续）7/30/202429JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义离散傅里叶变换DFT的计算（续）函函数数f(x,y)的的傅傅立立叶叶变变换换是是f(x,y)积积分分（对对于于离离散散而而言言，则则是是累累加加和和）的的函函数数，因因此此，计计算算每每一一个个傅傅立立叶叶变变换换值值，原原
24、函函数数f(x,y)的的每每一一个个点点都都需需要要参与参与。 f(x,y)全部值对全部值对DFT都产生影响；反之，全部变都产生影响；反之，全部变换系数对反变换也产生影响。换系数对反变换也产生影响。7/30/202430JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义二维离散傅里叶变换DFT的显示将将二二维维频频率率空空间间的的每每个个点点的的幅幅值值（实实部部和和虚虚部部平平方方和和的的平平方方根根）规规格格化化为为显显示示灰灰度度级级（0-255），产产生生的的图图像像为为傅里叶傅里叶频谱幅
25、度图像频谱幅度图像。（频谱相位图像暂不考虑）。（频谱相位图像暂不考虑）7/30/202431JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义二维离散傅里叶变换DFT的显示（续）通通常常，在在显显示示傅傅里里叶叶频频谱谱幅幅度度图图像像需需要要将将原原点点平平移移到到图图像像的的中中心心（让让图像能量集中到图像中心位置），以便能清楚地分析变换谱的情况。图像能量集中到图像中心位置），以便能清楚地分析变换谱的情况。注意注意：频谱图上的各点与图像上各点：频谱图上的各点与图像上各点不存在对应的关系不存在对
26、应的关系！越越靠靠近近中中心心的的点点，对对应应的频率越低。的频率越低。亮亮度度越越大大表表示示该该点点对对应应频频率率的的幅幅值值越大。越大。7/30/202432JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换定义傅里叶变换定义图像 “频域”空间的物理意义图图像像的的频频率率是是表表征征图图像像中中灰灰度度变变化化剧剧烈烈程程度度（梯梯度度）。如如大大面面积积的的沙沙漠漠在在图图像像中中是是一一片片灰灰度度变变化化缓缓慢慢的的区区域域,对对应应的的频频率率值值很很低低;而而对对于于地地表表变变化化剧剧烈烈的的
27、边边缘缘区区域域在在图图像像中是一片灰度变化剧烈的区域中是一片灰度变化剧烈的区域,对应的频率值较高。对应的频率值较高。傅傅立立叶叶变变换换的的物物理理意意义义是是将将图图像像的的灰灰度度分分布布函函数数变变换换为频率分布函数为频率分布函数。举例：绘画举例：绘画频率的频率的幅值表示该频率成分对原来图像信息（能量）幅值表示该频率成分对原来图像信息（能量）的贡献的贡献。7/30/202433JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换傅里叶变换主要内容n图像变换基础图像变换基础n傅里叶变换定义傅里叶变换定义n傅里叶
28、变换的性质傅里叶变换的性质n快速傅里叶变换快速傅里叶变换7/30/202434JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换傅里叶变换傅里叶变换的性质可分离性可分离性均值性均值性能量守恒定理能量守恒定理平移性质平移性质分配律分配律比例变换比例变换旋转性旋转性周期性和共轭对称性周期性和共轭对称性卷积卷积相关相关7/30/202435JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质可分离性图像尺寸为图像尺寸为MN
29、的函数的函数f (x,y)的的DFT可以为如下形式：可以为如下形式：F(x,)是沿着是沿着f (x,y)的一列所进行的傅里叶变换。当的一列所进行的傅里叶变换。当x=0,1,M-1，沿着，沿着f (x,y)的所有列计算傅里叶变换。的所有列计算傅里叶变换。上式说明：上式说明：二维二维DFT可分离为两次一维可分离为两次一维DFT7/30/202436JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质可分离性二维傅里叶变换的全过程行变换行变换N-1M-1F(,v)(0,0)vN-1M-1F(x,v)(
30、0,0)vxN-1M-1f(x,y)(0,0)yx列变换列变换先通过沿输入图像的每一列计算一维变换先通过沿输入图像的每一列计算一维变换再沿中间结果的每一行计算一维变换再沿中间结果的每一行计算一维变换可以改变上述顺序，即先行后列可以改变上述顺序，即先行后列7/30/202437JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质可分离性（续）上述相似的过程也可以计算二维傅里叶反变换：上述相似的过程也可以计算二维傅里叶反变换：7/30/202438JINAN UniversityDigital Im
31、age Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质均值性由二维傅里叶变换的定义：由二维傅里叶变换的定义：而，而，上式说明：上式说明：在原点的傅里叶变换即等于图像的在原点的傅里叶变换即等于图像的平均灰度值平均灰度值。7/30/202439JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质能量守恒定理能量守恒定理也称帕斯韦尔（能量守恒定理也称帕斯韦尔（Parseval）定理：）定理：上式说明：上式说明：傅里叶变换前后能量守恒傅里叶变换前后能量守恒。
32、7/30/202440JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质平移性质DFT平移特性如下：平移特性如下： 第一个公式表明将第一个公式表明将F(,)与一个指数项相乘就相当与一个指数项相乘就相当于把其变换后的空域中心移动到新的位置。于把其变换后的空域中心移动到新的位置。 第二个公式表明将第二个公式表明将f (x, y)与一个指数项相乘就相当与一个指数项相乘就相当于把其变换后的频域中心移动到新的位置。于把其变换后的频域中心移动到新的位置。7/30/202441JINAN Universit
33、yDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质平移性质（续）由以上公式可知：由以上公式可知：空间域中图像的平移不影响频谱幅度空间域中图像的平移不影响频谱幅度（幅值不变）（幅值不变），仅对应于频域的相移（只改变了相位谱，仅对应于频域的相移（只改变了相位谱）原图像原图像X轴平移图像轴平移图像Y轴平移图像轴平移图像7/30/202442JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质平移性质（续）上式表明：如果要将图像的上
34、式表明：如果要将图像的频谱原点移到图像中心，频谱原点移到图像中心，只要将只要将f (x, y)乘上因子乘上因子，再进行，再进行DFT变换即可变换即可。将将DFT频谱的原点移动到矩阵频谱的原点移动到矩阵MN的中心，这样只要的中心，这样只要设：设：7/30/202443JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质平移性质（续）方块图像方块图像原点平移前的原点平移前的频谱幅度图像频谱幅度图像原点平移后的原点平移后的频谱幅度图像频谱幅度图像7/30/202444JINAN UniversityD
35、igital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质分配律根据傅里叶变换的定义，可以得到：根据傅里叶变换的定义，可以得到：上式表明：上式表明：傅里叶变换对加法满足分配律傅里叶变换对加法满足分配律。但。但对乘法则不满足：对乘法则不满足：7/30/202445Digital Image Processing制作：刘晓翔JINAN University暨南大学珠海学院数字图像处理分配律实例分配律实例+=空空域域频频域域7/30/202446JINAN UniversityDigital Image Processing制作：刘晓翔暨南
36、大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质比例变换（尺度变换）给定给定2个标量个标量和和，可以证明对傅里叶变换下，可以证明对傅里叶变换下列列2个公式成立：个公式成立：第二个式子表明：第二个式子表明：对对f (x, y)在空间尺度的放缩在空间尺度的放缩导致其傅立叶导致其傅立叶变换变换F(,)在频域尺度方面相反放缩。在频域尺度方面相反放缩。7/30/202447Digital Image Processing制作：刘晓翔JINAN University暨南大学珠海学院数字图像处理尺寸缩放实例尺寸缩放实例646432321616空空域域频频域域7/30/202448JINAN Univ
37、ersityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质旋转性引入极坐标引入极坐标x=rcos, y=rsin, =kcos, =ksin，将，将f (x, y) 和和F(,)转换为转换为f (r,)和和F(k,)，将它们带入傅里，将它们带入傅里叶变化对：叶变化对：上式表明：上式表明：对对f (x, y)旋转旋转0 ，对应于其傅里叶变换，对应于其傅里叶变换F(,)也旋转也旋转0。类似地，类似地，对对F(,)旋转旋转0也对应于其傅里也对应于其傅里叶反变换旋转叶反变换旋转0。7/30/202449Digital Image
38、 Processing制作：刘晓翔JINAN University暨南大学珠海学院数字图像处理旋转性实例旋转性实例旋转旋转300原始图像原始图像旋转旋转450空空域域频频域域7/30/202450JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质周期性图像尺寸为图像尺寸为MN的函数的函数f (x, y)的的DFT具有周期性：具有周期性：上式表明：上式表明：只需一个周期里的变换就可将只需一个周期里的变换就可将F(,) 在频域里完全确定。在频域里完全确定。7/30/202451JINAN Univ
39、ersityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质共轭对称性如果如果f (x, y) 是实函数，则它的傅里叶变换具是实函数，则它的傅里叶变换具有共轭对称性：有共轭对称性：复习复习：当两个复数实部相等，虚部互为相反数时，这两：当两个复数实部相等，虚部互为相反数时，这两个复数叫做互为共轭复数。个复数叫做互为共轭复数。为为的复共轭。的复共轭。7/30/202452JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质卷积卷
40、积的定义（连续的情况）卷积的定义（连续的情况）离散一维卷积离散一维卷积离散二维卷积离散二维卷积傅里叶变换的卷积定理傅里叶变换的卷积定理7/30/202453JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质卷积卷积关于卷积卷积运算卷积运算是信号处理领域中最重要的运算之是信号处理领域中最重要的运算之一，在语音识别、地震勘探、超声诊断、光学成一，在语音识别、地震勘探、超声诊断、光学成像、系统辨识及其他诸多信号处理领域中，可以像、系统辨识及其他诸多信号处理领域中，可以说卷积与反卷积的问题无处不在说卷
41、积与反卷积的问题无处不在。在数字图像处理中，通过在数字图像处理中，通过卷积模板卷积模板操作，可操作，可实现图像锐化、图像平滑、高斯模糊等功能。实现图像锐化、图像平滑、高斯模糊等功能。7/30/202454JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质卷积卷积卷积的定义对于连续一维函数对于连续一维函数f1(x)与函数与函数f2(x)，它们的它们的卷积定义为：卷积定义为：对于连续二维函数对于连续二维函数f1(x,y)与函数与函数f2(x,y)，卷积，卷积定义为：定义为：7/30/202455J
42、INAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质卷积卷积离散一维卷积对于离散序列对于离散序列f1(0), f1(1), f1(A-1)与离散序列与离散序列f2(0), f2(1), f2(B-1)，它们的卷积运算要复杂一些，它们的卷积运算要复杂一些，必须对必须对f1(x)与与f2(x)的的定义域进行扩展定义域进行扩展，以，以防止卷积后产防止卷积后产生交叠误差生交叠误差（Wrap-aroundError）。）。假设假设f1(x)与与f2(x)具有周期具有周期M，则卷积结果具有相同的，则卷积结果具
43、有相同的周期。可以证明，只有当周期。可以证明，只有当MA+B-1时卷积周期不会重叠，时卷积周期不会重叠，才不会产生交叠误差。当才不会产生交叠误差。当M=A+B-1时，卷积周期是相邻接时，卷积周期是相邻接的。的。7/30/202456JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质卷积卷积离散一维卷积（续）x = 0, 1, , M-1，M=A+B-1定义域扩展：定义域扩展：离散一维卷积公式：离散一维卷积公式：7/30/202457JINAN UniversityDigital Image P
44、rocessing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质卷积卷积离散二维卷积和和和和和和和和x = 0, 1, , M-1，y = 0, 1, , N-1图像尺寸为图像尺寸为AB的函数的函数f 1(x, y)与与尺寸为尺寸为CD的函数的函数f 2(x, y)做卷积。做卷积。离散二维卷积公式：离散二维卷积公式：7/30/202458JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质卷积卷积傅里叶变换的卷积定理卷积是空间域滤波和频域滤波之间的纽带卷积是空间域滤波和
45、频域滤波之间的纽带对于连续和离散卷积都有下列定理成立：对于连续和离散卷积都有下列定理成立：7/30/202459JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质相关相关连续函数相关对于连续一维函数对于连续一维函数f1(x)与函数与函数f2(x)，它们的它们的相关定义为：相关定义为：为为的复共轭。的复共轭。对于连续二维函数对于连续二维函数f1(x,y)与函数与函数f2(x,y)，它们，它们的相关定义为：的相关定义为：7/30/202460JINAN UniversityDigital Imag
46、e Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质相关相关离散相关参照前面离散卷积的定义，可如下定义一维离参照前面离散卷积的定义，可如下定义一维离散相关：散相关：二维离散相关定义为：二维离散相关定义为：x = 0, 1, , M-1，y = 0, 1, , N-1x = 0, 1, , M-17/30/202461JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换的性质傅里叶变换的性质相关相关傅里叶变换的相关定理对于连续和离散相关都有下列定理成立：对于连续和离散相关都有
47、下列定理成立：（在图像处理中，相关的重要应用在于图像在图像处理中，相关的重要应用在于图像匹配：确定是否有感兴趣的区域。）匹配：确定是否有感兴趣的区域。）7/30/202462JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理傅里叶变换傅里叶变换主要内容n图像变换基础图像变换基础n傅里叶变换定义傅里叶变换定义n傅里叶变换的性质傅里叶变换的性质n快速傅里叶变换快速傅里叶变换（只考虑一维的情况，根据傅里叶变换的分离性可知，（只考虑一维的情况，根据傅里叶变换的分离性可知，二维傅里叶变换可由连续二维傅里叶变换可由连续2次一维傅里叶变换
48、得到）次一维傅里叶变换得到）7/30/202463JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）为什么需要快速傅里叶变换？ = 0, 1, , M-1对对M个值中的每一个都需进行个值中的每一个都需进行M次复数乘法（将次复数乘法（将f(x)与与相乘）和相乘）和M-1次加法，即复数乘法和加法的次数都正比于次加法，即复数乘法和加法的次数都正比于M2。快速傅里叶变换（快速傅里叶变换（FFT）则只需要）则只需要Mlog2M次运算。次运算。FFT算法与原始算法的计算量之比是算法与原始算法的计算
49、量之比是(log2M)/M，如，如M=1024103，则原始变换算法需要，则原始变换算法需要106次计算，而次计算，而FFT需需要要104次计算，次计算，FFT与原始变换算法之比是与原始变换算法之比是1:100。7/30/202464JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法基本思想FFT算法基于一个叫做算法基于一个叫做逐次加倍逐次加倍的方法。通过推导将的方法。通过推导将原始原始M个点的傅里叶变换转换成两个递推公式：个点的傅里叶变换转换成两个递推公式：其中其中K=M/
50、2，Feven()、Fodd()是是K个点的傅里叶变个点的傅里叶变换值。换值。 = 0, 1, , K-17/30/202465JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法推导为方便起见用下式表达离散傅里叶变换公式：为方便起见用下式表达离散傅里叶变换公式：这里这里是一个常数。是一个常数。7/30/202466JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FF
51、T算法推导假设假设M的形式是：的形式是：n为正整数，因此为正整数，因此M可以表示为：可以表示为：将将M=2K代入上式代入上式7/30/202467JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法推导因为：因为：所以：所以：带入上式有：带入上式有：7/30/202468JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法推导定义两个符号：定义两个符号： = 0
52、, 1, , K-1得到得到FFT的第一个公式：的第一个公式：该公式说明：该公式说明：F()可以通过奇数部和偶数部之可以通过奇数部和偶数部之和来计算和来计算。7/30/202469JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法推导7/30/202470JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法推导7/30/202471JINAN Universi
53、tyDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法推导得到得到FFT的第二个公式：的第二个公式：该公式说明：该公式说明：F(+K)可以通过奇数部和偶数部可以通过奇数部和偶数部之差来计算。之差来计算。7/30/202472JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）分析最后得到的两个公式的特性分析以上两个表达式，得到如下一些有趣的特性：分析以上两个表达式，得到如下一些有趣的特性：一个一个M点
54、的变换，能够通过将原始表达式分成两个部分来点的变换，能够通过将原始表达式分成两个部分来计算。计算。通过计算两个通过计算两个M/2个点的变换，得到个点的变换，得到Feven()和和Fodd()。奇数部分与偶数部分之和得到奇数部分与偶数部分之和得到F()的前的前M/2个值，奇数部个值，奇数部分与偶数部分之差得到分与偶数部分之差得到F()的后的后M/2个值。个值。 = 0, 1, , K-1，K=M/27/30/202473JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法举例有函
55、数有函数f (x)，M=23=8，K=4f(0), f(1), f(2), f(3), f(4), f(5), f(6), f(7)计算：计算：F(0), F(1), F(2), F(3), F(4), F(5), F(6), F(7)7/30/202474JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法举例（续）首先分成奇偶两组：首先分成奇偶两组：f(0), f(2), f(4), f(6)f(1), f(3), f(5), f(7)f (x)7/30/202475JIN
56、AN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法举例（续） 对对继续进行奇偶分组：继续进行奇偶分组：f(0), f(2), f(4), f(6) f(0), f(4) f(2), f(6) 7/30/202476JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法举例（续） 对对继续进行奇偶分组：继续进行奇偶分组：f(1), f(3), f(5), f(7) f(
57、1), f(5) f(3), f(7) 7/30/202477JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）FFT算法举例（续） 都已经是都已经是2点的点的DFT，它们可以由原始数据直接求出：，它们可以由原始数据直接求出：f(0), f(4) f(2), f(6) f(1), f(5) f(3), f(7) 7/30/202478JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（F
58、FT）蝶形运算单元FFT中的两个递推公式可以用中的两个递推公式可以用“蝶形运算蝶形运算”单元来表单元来表示，例如：示，例如：单元左方两个节点为输入点，代表输入数值；右方两单元左方两个节点为输入点，代表输入数值；右方两个节点为输出节点，表示输入数值的叠加。运算由左向右个节点为输出节点，表示输入数值的叠加。运算由左向右进行。线旁的进行。线旁的、为加权系数。为加权系数。7/30/202479JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）8点FFT蝶形流图（码位倒序输出）f(0)f(1)f
59、(3)f(4)f(2)f(7)f(5)f(6)F(0)F(4)F(6)F(1)F(2)F(7)F(5)F(3)7/30/202480JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）8点FFT蝶形流图(码位倒序输入)f(0)f(4)f(6)f(1)f(2)f(7)f(5)f(3)F(0)F(1)F(3)F(4)F(2)F(7)F(5)F(6)7/30/202481JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速
60、傅里叶变换（快速傅里叶变换（FFT）码位倒序排列算法十进制数十进制数二进制数二进制数码位倒序码位倒序倒序后的十进制数倒序后的十进制数00000000100110042010010230111106410000115101101561100113711111177/30/202482JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换（快速傅里叶变换（FFT）反变换不需要额外编写代码，我们只需要对正变换的输入一不需要额外编写代码，我们只需要对正变换的输入一点小小的修改就可用于反变换。点小小的修改就可用于反变换。对上
61、式取复共轭，再在两边同除以对上式取复共轭，再在两边同除以M得到：得到：上式右边对应一个正变换，把上式右边对应一个正变换，把F*()输入一个正变换输入一个正变换算法将得到算法将得到f*(x)/M，因此对上式求复共轭并乘以，因此对上式求复共轭并乘以M就得到就得到所需的反变换所需的反变换f (x)。（注：实数的共轭就是其本身）（注：实数的共轭就是其本身）。7/30/202483JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理离散傅里叶变换FFT的计算FFT的计算的计算例例：一一维维函函数数的的四四个个采采样样值值为为f(0)=2
62、, f(1)=3, f(2)=f(3)=4。x01212343快速傅里叶变换（快速傅里叶变换（FFT）7/30/202484JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换FFT的计算（计算）首先分成奇偶两组：首先分成奇偶两组：f(0), f(2)f(1), f(3)f (x)FFT递推公式：递推公式：快速傅里叶变换（快速傅里叶变换（FFT）7/30/202485JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换FFT的计算（
63、续）计算计算：计算两个点的计算两个点的FT快速傅里叶变换（快速傅里叶变换（FFT）7/30/202486JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理快速傅里叶变换FFT的计算（续） 将将和和代入代入计算计算4个点的个点的FT快速傅里叶变换（快速傅里叶变换（FFT）7/30/202487JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理本讲小结本讲小结需要掌握的知识点n什么是什么是频域空间频域空间？（信号分解、正交信号）？（信号分解、正交信号）nDFT
64、及反变换的及反变换的定义定义n图像频域空间的图像频域空间的物理意义物理意义nDFT的的性质性质需要掌握的技能n编程实现编程实现FFT及其逆变换算法（课程设计）及其逆变换算法（课程设计）n编程实现频谱图的显示编程实现频谱图的显示7/30/202488JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理关于关于FFT编程编程在C+中使用复数#includeusingnamespacestd;C+标准库中提供了复数运算的库函数。在文件开头加上标准库中提供了复数运算的库函数。在文件开头加上以下语句即可使用：以下语句即可使用：标准标准C
65、+库中的所有组件都是在一个被称为库中的所有组件都是在一个被称为std的名字空的名字空间中声明和定义的。间中声明和定义的。中声明的函数对象和类中声明的函数对象和类模板都被声明在名字空间模板都被声明在名字空间std中。所以必须用中。所以必须用using声明声明使程序中用到的名字空间使程序中用到的名字空间std的成员可见。的成员可见。7/30/202489JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理关于关于FFT编程编程时域与频域空间的表示用数组表示时域与频域空间：用数组表示时域与频域空间：complex*TD-指向时域数组
66、的指针指向时域数组的指针complex*FD-指向频域数组的指针指向频域数组的指针分配内存：分配内存：newcomplexcount;count为需要计算的为需要计算的FT点数，即图像的长度点数，即图像的长度或宽度或宽度注意：注意：count必须为必须为2的的r次方次方，否则不能使用，否则不能使用FFT算法，算法，r为为FFT计算的迭代次数。计算的迭代次数。7/30/202490JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理关于关于FFT编程编程计算FFT中的加权系数W用数组表示加权系数用数组表示加权系数：分配内存：分配
67、内存：complex*W=newcomplexcount/2;计算加权系数：计算加权系数：for(i=0;icount/2;i+)angle=-i*PI*2/count;Wi=complex(cos(angle),sin(angle);7/30/202491JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理关于关于FFT编程编程蝶形算法for(k=0;kr;k+)for(j=0;j1k;j+)size=1(r-k);for(i=0;isize/2;i+)p=j*size;X2i+p=X1i+p+X1i+p+size/2;X2
68、i+p+size/2=(X1i+p-X1i+p+size/2)*Wi*(1k);temp=X1;X1=X2;X2=temp;FFT算法的第一个递推算法的第一个递推公式公式FFT算法的第二个递推算法的第二个递推公式公式X1=newcomplexcount;X2=newcomplexcount;7/30/202492JINAN UniversityDigital Image Processing制作：刘晓翔暨南大学珠海学院数字图像处理关于关于FFT编程编程输出序列按码位倒序重新排列for(j=0;jcount;j+)p=0;for(i=0;ir;i+)if(j&(1i)p+=1(r-i-1);FDj=X1p;/从右至左依次取出从右至左依次取出j的二进制数的每一位的二进制数的每一位/倒序重新排列倒序重新排列7/30/202493
