Bir segment üzerinde kendi okumalarıyla belirtilen ayrı bir sinyalin spektral temsilinin özelliklerini araştırıyoruz.
, sırasıyla zaman zaman alınır
; toplam örnek sayısı
(- örnekleme aralığı).

Bu tür ayrık sinyalleri inceleme tekniği, ortaya çıkan referans değerleri örneğinin zihinsel olarak sonsuz sayıda tekrarlanmasıdır. Sonuç olarak sinyal periyodik hale gelir.

Belirli bir matematiksel modeli böyle bir sinyalle ilişkilendirerek Fourier serisi açılımını kullanabilir ve karşılık gelen genlik katsayılarını bulabilirsiniz. Bu katsayıların birleşimi ayrı bir periyodik sinyalin spektrumunu oluşturur.

Modeli bir dizi delta darbesi biçiminde kullanalım. Daha sonra ilk titreşim aşağıdaki formülle ifade edilecektir:

(5.1)

Nerede
– analog sinyalin örnek değerleri.

- ayrık Fourier dönüşümü (DFT) (5.4)

DFT'nin temel özellikleri

1. DFT - doğrusal dönüşüm yani. sinyallerin toplamı DFT'lerinin toplamına karşılık gelir

2. Farklı katsayıların sayısı
formül (5.4) kullanılarak hesaplanan, periyot başına N sayısına eşittir; katsayıda

3. Katsayı (sabit bileşen) tüm okumaların ortalama değeridir:

5. Referans değerlerine izin verin - gerçek sayılar. Daha sonra sayıları /2'ye göre simetrik olarak yerleştirilen DFT katsayıları eşlenik çiftler oluşturur:

Ayrık spektral analiz sorunu başka bir şekilde formüle edilebilir. Katsayıların olduğunu varsayalım. DFT'yi oluşturan , verilmiştir. (5.2) formülünü koyalım
ve orijinal sinyalin spektrumunda yer alan harmoniklere karşılık gelen serinin yalnızca sonlu sayıda teriminin toplandığını dikkate alın.

Böylece referans değerlerini hesaplamak için bir formül elde ederiz

(5.5)

Açıkçası, (5.5) ters ayrık Fourier dönüşümü (IDFT) formülüdür.

11 Hızlı Fourier dönüşümü algoritması. Hesaplamalı işlemlerin sayısı. Ayrık ve hızlı Fourier dönüşümlerinin karşılaştırılması.

=0, 1, 2,…,( /2)-1 (5.7)

Giriş dizisinin çift ve tek bölümleriyle ilgili katsayı dizilerinin N/2 periyoduyla periyodik olduğunu dikkate alalım:

Ayrıca formül (5.7)'de yer alan faktör
şu şekilde dönüştürülebilir:

Buradan DFT katsayıları kümesinin ikinci yarısına ilişkin ifadeyi buluyoruz

(5.8)

Formüller (5.7) ve (5.8) FFT algoritmasının temelini oluşturur. Daha sonra hesaplamalar yinelemeli prensibe göre gerçekleştirilir: çift ve tek sayılı örnek dizileri yine iki bölüme ayrılır. Tek bir elemandan oluşan bir dizi elde edilene kadar işleme devam edilir. Bu elemanın DFT'si kendisiyle çakışmaktadır.

FFT'yi hesaplamak için gereken işlem sayısı şu şekilde tahmin edilir:
.

Giriş dizilerinin yeterli uzunlukta olması durumunda, geleneksel DFT'ye kıyasla hesaplama hızındaki artış yüzlerce, hatta binlerce kişiye ulaşır.

12.. Z - dönüşüm ve özellikleri. Başvuru Z - dönüşümler.

Ayrık ve dijital cihazların analizinde ve sentezinde Z dönüşümü, sürekli sinyallere göre Fourier integral dönüşümleriyle aynı rolü oynar.

İzin vermek
– belirli bir sinyalin referans değerlerini içeren, sonlu veya sonsuz bir sayısal dizi. Bunu serinin toplamı ile benzersiz bir şekilde eşleştirelim. negatif güçler karmaşık değişken Z:

(5.9)

Bu toplam dizinin Z dönüşümü olarak adlandırılır.
. Ayrık sayı dizilerinin özellikleri, geleneksel matematiksel analiz yöntemleri kullanılarak Z-dönüşümleri incelenerek incelenebilir.

Bu ifade |Z|> olduğunda anlamlıdır. .

Ters Z dönüşümü

x(z), Z karmaşık değişkeninin bir fonksiyonu olsun. Z-dönüşümünün dikkate değer bir özelliği, x(z) fonksiyonunun sonsuz örnek kümesinin tamamını tanımlamasıdır (
).

Aslında serinin her iki tarafını da (5.9) faktörüyle çarpalım.
:

m numaralı terim hariç, sağ taraftaki tüm terimlerin integralleri sıfır olacaktır, dolayısıyla:

(5.11)

Bu ifadeye ters Z dönüşümü denir.

En önemli özellikler Z -dönüşümler:

1. Doğrusallık. Eğer
Ve
- bazı ayrık sinyaller ve karşılık gelen Z-dönüşümleri x(z) ve y(z) biliniyorsa, o zaman sinyal
herhangi bir sabitin dönüşümüne karşılık gelecektir Ve . İspat, toplamın formül (5.9)'da yerine konulmasıyla gerçekleştirilir.

2. Z-kaydırılan sinyalin dönüştürülmesi. Hadi düşünelim ayrık sinyal
ayrı bir sinyalden kaynaklanan
gecikmeye doğru bir konum kaydırarak, yani. Ne zaman
. Z-dönüşümünü doğrudan hesaplayarak aşağıdaki sonucu elde ederiz:

Yani sembol
Z alanında bir birim gecikme operatörü (örnekleme aralığı başına) görevi görür.

3. Z-evrişim dönüşümü. x(z) ve y(z), evrişimin tanımlandığı sürekli sinyaller olsun:

(5.13)

Ayrık sinyallerle ilgili olarak, (5.13)'e benzer şekilde, aşağıdakileri tanıtmak gelenekseldir: ayrık evrişim
– ortak terimi şu şekilde olan bir sayı dizisi:

Böyle ayrık bir evrişime doğrusal denir

Ayrık evrişimin Z-dönüşümünü hesaplayalım:

(5.15)

Dolayısıyla, iki ayrı sinyalin evrişimi Z-dönüşümlerinin çarpımına karşılık gelir.

Doğrusal filtreleme Görüntüler hem mekânsal hem de mekânsal olarak gerçekleştirilebilir. frekans alanı. "Düşük" uzamsal frekansların görüntünün ana içeriğine - arka plan ve büyük boyutlu nesnelere ve "yüksek" uzamsal frekanslara - küçük boyutlu nesnelere, büyük şekillerin küçük ayrıntılarına ve gürültü bileşenine karşılık geldiğine inanılmaktadır.

Geleneksel olarak, uzaysal frekanslar alanına geçmek için $\textit(Fourier dönüşümü)$'ye dayalı yöntemler kullanılır. İÇİNDE son yıllar Tüm daha fazla uygulama$\textit(wavelet-transform)$'a dayalı yöntemler de bulunur.

Fourier dönüşümü.

Fourier dönüşümü, hemen hemen her işlevi veya veri kümesini bunların bir kombinasyonu olarak temsil etmenize olanak tanır. trigonometrik fonksiyonlar sinüs ve kosinüs gibi, verilerdeki periyodik bileşenleri tanımlamanıza ve bunların orijinal verilerin yapısına veya fonksiyonun biçimine katkılarını değerlendirmenize olanak tanır. Geleneksel olarak Fourier dönüşümünün üç ana biçimi vardır: integral Fourier dönüşümü, Fourier serisi ve ayrık Fourier dönüşümü.

Fourier integral dönüşümü, gerçek bir fonksiyonu bir çift gerçek fonksiyona veya bir karmaşık fonksiyonu diğerine dönüştürür.

$f(x)$ gerçek fonksiyonu, trigonometrik fonksiyonlardan oluşan ortogonal bir sistemde genişletilebilir, yani şu şekilde temsil edilir:

$$ f\left(x \right)=\int\limits_0^\infty (A\left(\omega \right)) \cos \left((2\pi \omega x) \right)d\omega -\ int\limits_0^\infty (B\left(\omega \right)) \sin \left((2\pi \omega x) \right)d\omega , $$

burada $A(\omega)$ ve $B(\omega)$ integral kosinüs ve sinüs dönüşümleri olarak adlandırılır:

$$ A\left(\omega \sağ)=2\int\limits_(-\infty )^(+\infty ) (f\left(x \right)) \cos \left((2\pi \omega x) ) \sağ)dx; \quad B\left(\omega \right)=2\int\limits_(-\infty )^(+\infty ) (f\left(x \right)) \sin \left((2\pi \omega x) )\sağ)dx. $$

Fourier serisi, sinüs ve kosinüs cinsinden sonsuz bir seri olarak $$ aralığında tanımlanan periyodik bir $f(x)$ fonksiyonunu temsil eder. Yani, $f(x)$ periyodik fonksiyonu sonsuz bir Fourier katsayıları dizisiyle ilişkilidir.

$$ f\left(x \right)=\frac(A_0 )(2)+\sum\limits_(n=1)^\infty (A_n ) \cos \left((\frac(2\pi xn)( b-a)) \right)+\sum\limits_(n=1)^\infty (B_n \sin \left((\frac(2\pi xn)(b-a)) \right)) , $$

$$ A_n =\frac(2)(b-a)\int\limits_a^b (f\left(x \right)) \cos \left((\frac(2\pi nx)(b-a)) \right)dx ; \quad B_n =\frac(2)(b-a)\int\limits_a^b (f\left(x \right)) \sin \left((\frac(2\pi nx)(b-a)) \right)dx . $$

Ayrık Fourier dönüşümü sonlu bir diziyi dönüştürür gerçek sayılar Fourier katsayılarının sonlu bir dizisine dönüştürülür.

$\left\( (x_i ) \right\), i= 0,\ldots, N-1 $ - gerçek sayıların bir dizisi - örneğin, bir görüntü çizgisi boyunca piksel parlaklığı sayımı olsun. Bu dizi bir kombinasyon olarak temsil edilebilir nihai miktarlar tür

$$ x_i =a_0 +\sum\limits_(n=1)^(N/2) (a_n ) \cos \left((\frac(2\pi ni)(N)) \right)+\sum\limits_ (n=1)^(N/2) (b_n \sin \left((\frac(2\pi ni)(N)) \right)) , $$

$$ a_0 =\frac(1)(N)\sum\limits_(i=0)^(N-1) (x_i ) , \quad a_(N/2) =\frac(1)(N)\sum \limits_(i=0)^(N-1) (x_i ) \left((-1) \right)^i, \quad a_k =\frac(2)(N)\sum\limits_(i=0) ^(N-1) (x_i \cos \left((\frac(2\pi ik)(N)) \right))), $$

$$ b_k =\frac(2)(N)\sum\limits_(i=0)^(N-1) (x_i \sin \left((\frac(2\pi ik)(N)) \right) ), \quad i\le k

Fourier dönüşümünün üç biçimi arasındaki temel fark, eğer integral Fourier dönüşümü $f(x)$ fonksiyonunun tüm tanım alanı boyunca tanımlanmışsa, seri ve ayrık Fourier dönüşümünün yalnızca ayrık bir küme üzerinde tanımlanmasıdır. Fourier serisi için sonsuz ve ayrık dönüşümler için sonlu noktalar.

Fourier dönüşümünün tanımlarından da görülebileceği gibi, ayrık Fourier dönüşümü, dijital sinyal işleme sistemleri için büyük ilgi görmektedir. Dijital ortamdan veya bilgi kaynaklarından alınan veriler, vektörler veya matrisler biçiminde yazılan sıralı sayı kümeleridir.

Ayrık bir dönüşüm için giriş verilerinin genellikle $\Delta $ adımına sahip tekdüze bir örnek olduğu ve $T=N\Delta $ değerine kayıt uzunluğu veya temel periyot adı verildiği varsayılır. Temel frekans 1 $/T$'dır. Böylece ayrık Fourier dönüşümü, giriş verilerini temel frekansın tam katı olan frekanslara ayrıştırır. Giriş verilerinin boyutuna göre belirlenen maksimum frekans $1/2 \Delta $'a eşittir ve $\it(Nyquist frekansı)$ olarak adlandırılır. Ayrık dönüşüm kullanılırken Nyquist frekansının dikkate alınması önemlidir. Giriş verileri, Nyquist frekansından daha yüksek frekanslara sahip periyodik bileşenlere sahipse, ayrık Fourier dönüşümü, yüksek frekanslı verileri daha düşük bir frekansla değiştirecektir ve bu, ayrık dönüşümün sonuçlarının yorumlanmasında hatalara yol açabilir.

$\it(enerji spektrumu)$ aynı zamanda veri analizi için de önemli bir araçtır. $\omega $ frekansındaki sinyal gücü aşağıdaki şekilde belirlenir:

$$ P \left(\omega \sağ)=\frac(1)(2)\left((A \left(\omega \sağ)^2+B \left(\omega \sağ)^2) \right ). $$

Bu miktar genellikle $\omega $ frekansında $\it(sinyal enerjisi)$ olarak adlandırılır. Parseval teoremine göre giriş sinyalinin toplam enerjisi, tüm frekanslardaki enerjilerin toplamına eşittir.

$$ E=\sum\limits_(i=0)^(N-1) (x_i^2 ) =\sum\limits_(i=0)^(N/2) (P \left((\omega _i ) \Sağ)) . $$

Güç-frekans grafiğine enerji spektrumu veya güç spektrumu denir. Enerji spektrumu, giriş verilerindeki gizli periyodiklikleri tanımlamaya ve belirli frekans bileşenlerinin giriş verilerinin yapısına katkısını değerlendirmeye olanak tanır.

Fourier dönüşümünün karmaşık gösterimi.

Ayrık Fourier dönüşümünü yazmanın trigonometrik biçimine ek olarak, $\it(karmaşık gösterim)$ yaygın olarak kullanılır. Fourier dönüşümünü kaydetmenin karmaşık biçimi, çok boyutlu analizde ve özellikle görüntü işlemede yaygın olarak kullanılır.

Trigonometrik formdan karmaşık forma geçiş Euler formülüne göre gerçekleştirilir.

$$ e^(j\omega t)=\cos \omega t+j\sin \omega t, \quad j=\sqrt (-1) . $$

Giriş dizisi $N$ karmaşık sayılar ise, o zaman onun ayrık Fourier dönüşümü şöyle olacaktır:

$$ G_m =\frac(1)(N)\sum\limits_(n=1)^(N-1) (x_n ) e^(\frac(-2\pi jmn)(N))), $$

ve ters dönüşüm

$$ x_m =\sum\limits_(n=1)^(N-1) (G_n ) e^(\frac(2\pi jmn)(N)). $$

Giriş dizisi bir gerçek sayılar dizisi ise, o zaman bunun için hem karmaşık hem de ayrık bir sinüs-kosinüs dönüşümü vardır. Bu fikirler arasındaki ilişki şu şekilde ifade edilir:

$$ a_0 =G_0 , \quad G_k =\left((a_k -jb_k ) \right)/2, \quad 1\le k\le N/2; $$

geri kalan $N/2$ dönüşüm değerleri karmaşık eşleniklerdir ve ek bilgi taşımazlar. Bu nedenle, ayrık Fourier dönüşümünün güç spektrumu grafiği $N/2$'ya göre simetriktir.

Hızlı Fourier dönüşümü.

Ayrık Fourier dönüşümünü (DFT) hesaplamanın en basit yolu, her katsayı üzerinde $N$ işlemleriyle sonuçlanan doğrudan toplamadır. Toplam katsayılar $N$ olduğundan toplam karmaşıklık $O\left((N^2) \right)$ olur. Bu yaklaşım pratik açıdan ilgi çekici değildir, çünkü DFT'yi hesaplamanın $O (N\log N)$ karmaşıklığına sahip hızlı Fourier dönüşümü (FFT) adı verilen çok daha etkili yolları vardır. FFT yalnızca uzunluğu (öğe sayısı) 2'nin üssü olan diziler için geçerlidir. FFT algoritmasının arkasındaki en genel prensip, giriş dizisini iki yarım uzunlukta diziye bölmektir. İlk sıra çift sayılı verilerle, ikincisi ise tek sayılı verilerle doldurulur. Bu, $N/2$ boyutunun iki dönüşümü aracılığıyla DFT katsayılarının hesaplanmasını mümkün kılar.

$\omega _m =e^(\frac(2\pi j)(m))$'yi gösterelim, sonra $G_m =\sum\limits_(n=1)^((N/2)-1) (x_ (2n ) ) \omega _(N/2)^(mn) +\sum\limits_(n=1)^((N/2)-1) (x_(2n+1) ) \omega _(N/ 2) ^(mn)\omega _N^m $.

Milyon dolar için< N/2$ тогда можно записать $G_m =G_{\textrm{even}} \left(m \right)+G_{\textrm{odd}} \left(m \right)\omega _N^m $. Учитывая, что элементы ДПФ с индексом б ольшим, чем $N/2$, являются комплексно сопряженными к элементам с индексами меньшими $N/2$, можно записать $G_{m+(N/2)} =G_{\textrm{even}} \left(m \right)-G_{\textrm{odd}} \left(m \right)\omega _N^m $. Таким образом, можно вычислить БПФ длиной $N$, используя два ДПФ длиной $N/2$. Полный алгоритм БПФ заключается в рекурсивном выполнении вышеописанной процедуры, начиная с объединения одиночных элементов в пары, затем в четверки и так до полного охвата исходного массива данных.

İki boyutlu Fourier dönüşümü.

$M\times N$ boyutunda iki boyutlu bir sayı dizisi için ayrık Fourier dönüşümü aşağıdaki gibi tanımlanır:

$$ G_(uw) =\frac(1)(NM)\sum\limits_(n=1)^(N-1) (\sum\limits_(m=1)^(M-1) (x_(mn ) ) ) e^((-2\pi j\left[ (\frac(mu)(M)+\frac(nw)(N)) \right]) ), $$

ve ters dönüşüm

$$ x_(mn) =\sum\limits_(u=1)^(N-1) (\sum\limits_(w=1)^(M-1) (G_(uw) ) ) e^( (2 \pi j\left[ (\frac(mu)(M)+\frac(nw)(N)) \right]) ). $$

Görüntü işleme durumunda, iki boyutlu Fourier dönüşümünün bileşenlerine $\textit(uzaysal frekanslar)$ adı verilir.

İki boyutlu Fourier dönüşümünün önemli bir özelliği, onu tek boyutlu FFT prosedürünü kullanarak hesaplama yeteneğidir:

$$ G_(uw) =\frac(1)(N)\sum\limits_(n=1)^(N-1) ( \left[ (\frac(1)(M)\sum\limits_(m= 0)^(M-1) (x_(mn) e^(\frac(-2\pi jmw)(M)))) ) \right] ) e^(\frac(-2\pi jnu)(N) ), $$

Burada köşeli parantez içindeki ifade, veri matrisinin bir satırının tek boyutlu FFT ile gerçekleştirilebilen tek boyutlu dönüşümüdür. Bu nedenle, iki boyutlu bir Fourier dönüşümü elde etmek için öncelikle tek boyutlu satır dönüşümlerinin hesaplanması, sonuçların orijinal matrise yazılması ve elde edilen matrisin sütunları için tek boyutlu dönüşümlerin hesaplanması gerekir. İki boyutlu Fourier dönüşümünü hesaplarken, düşük frekanslar matrisin köşelerinde yoğunlaşacaktır ve bu, alınan bilginin daha fazla işlenmesi için pek uygun değildir. Düşük frekansların matrisin merkezinde yoğunlaştığı bir 2D Fourier dönüşümü temsilini elde etmek amacıyla çeviri yapmak için gerçekleştirilebilecek basit bir prosedür, orijinal verileri $-1^(m+n)$ ile çarpmaktır.

İncirde. Şekil 16 orijinal görüntüyü ve onun Fourier dönüşümünü göstermektedir.

Yarım ton görüntüsü ve Fourier dönüşümü (LabVIEW'da elde edilen görüntüler)

Fourier dönüşümü kullanılarak evrişim.

$s(t)$ ve $r(t)$ fonksiyonlarının evrişimi şu şekilde tanımlanır:

$$ s\ast r\cong r\ast s\cong \int\limits_(-\infty )^(+\infty ) (s(\tau)) r(t-\tau)d\tau . $$

Pratikte, sürekli fonksiyonların tek tip bir ızgaranın düğümlerindeki değer kümeleriyle değiştirildiği ayrık evrişimle uğraşmak zorundayız (genellikle bir tamsayı ızgara alınır):

$$ (r\ast s)_j \cong \sum\limits_(k=-N)^P (s_(j-k) r_k ). $$

Burada $-N$ ve $P$, $r(t) = 0$'ın ötesindeki aralığı tanımlar.

Fourier dönüşümünü kullanarak evrişimi hesaplarken, frekans alanındaki fonksiyonların görüntülerinin çarpımının bu fonksiyonların zaman alanındaki evrişimine eşdeğer olduğu Fourier dönüşümünün özelliği kullanılır.

Uzlaştırmayı hesaplamak için, orijinal verileri frekans alanına dönüştürmek, yani Fourier dönüşümünü hesaplamak, dönüşümün sonuçlarını çarpmak ve orijinal gösterimi geri yükleyerek ters Fourier dönüşümünü gerçekleştirmek gerekir.

Algoritmanın işleyişindeki tek incelik, ayrık bir Fourier dönüşümü durumunda (sürekli olanın aksine), iki periyodik fonksiyonun kıvrımlı olması, yani değer kümelerimizin tam olarak Bu fonksiyonların periyotları ve yalnızca eksenin ayrı bir bölümündeki değerler değil. Yani, algoritma $x_(N )$ noktasının ardından sıfırın değil, bir daire içinde $x_(0)$ noktasının geldiğine ve bu şekilde devam ettiğine inanır. Bu nedenle evrişimin doğru hesaplanabilmesi için sinyale yeterince uzun bir sıfır dizisi atamak gerekir.

Görüntülerin frekans alanında filtrelenmesi.

Doğrusal filtreleme yöntemleri, hızlı evrişim algoritmalarına ve spektral analize dayalı verimli hesaplama şemalarının geliştirildiği iyi yapılandırılmış yöntemler arasındadır. Genel olarak doğrusal filtreleme algoritmaları formun dönüşümünü gerçekleştirir

$$ f"(x,y) = \int\int f(\zeta -x, \eta -y)K (\zeta , \eta) d \zeta d \eta , $$

burada $K(\zeta ,\eta)$ doğrusal dönüşümün çekirdeğidir.

Sinyalin ayrık bir temsiliyle, bu formüldeki integral, belirli bir açıklık içindeki orijinal görüntünün örneklerinin ağırlıklı toplamına dönüşür. Bu durumda, $K(\zeta ,\eta)$ çekirdeğinin bir veya başka bir optimallik kriterine göre seçilmesi, bir dizi yararlı özelliğe yol açabilir (bir görüntünün sayısal farklılaşması problemini düzenlerken Gauss yumuşatma, vb.) .

Doğrusal işleme yöntemleri en etkili şekilde frekans alanında uygulanır.

Filtreleme işlemlerini gerçekleştirmek için bir görüntünün Fourier dönüşümünün kullanılması, öncelikle bu tür işlemlerin daha yüksek performansından kaynaklanmaktadır. Tipik olarak ileri ve ters 2D Fourier dönüşümlerini gerçekleştirmek ve filtrenin Fourier görüntüsünün katsayılarıyla çarpmak, orijinal görüntüde 2D evrişim gerçekleştirmekten daha az zaman alır.

Frekans alanı filtreleme algoritmaları evrişim teoremine dayanmaktadır. 2 boyutlu durumda, evrişim dönüşümü şöyle görünür:

$$ G\left((u,v) \right)=H\left((u,v) \right)F\left((u,v) \right), $$

burada $G$ evrişim sonucunun Fourier dönüşümüdür, $H$ filtrenin Fourier dönüşümüdür ve $F$ orijinal görüntünün Fourier dönüşümüdür. Yani, frekans alanında, iki boyutlu evrişimin yerini, orijinal görüntünün ve karşılık gelen filtrenin görüntülerinin öğe bazında çoğaltılması alır.

Evrişimi gerçekleştirmek için aşağıdakileri yapmanız gerekir:

1. Fourier görüntüsünü ortalamak için orijinal görüntünün öğelerini $-1^(m+n)$ ile çarpın.
2. $F(u,v)$'nin Fourier görüntüsünü FFT kullanarak hesaplayın.
3. Fourier görüntüsünü $F(u,v)$ frekans filtresi fonksiyonu $H(u,v)$ ile çarpın.
4. Ters Fourier dönüşümünü hesaplayın.
5. Ters dönüşümün gerçek kısmını $-1^(m+n)$ ile çarpın.

Frekans alanındaki filtre fonksiyonu ile uzaysal alan arasındaki ilişki, evrişim teoremi kullanılarak belirlenebilir.

$$ \Phi \left[ (f\left((x,y) \right)\ast h(x,y)) \right]=F\left((u,v) \right)H\left(( u,v) \sağ), $$

$$ \Phi \left[ (f\left((x,y) \right)h(x,y)) \right]=F\left((u,v) \right)\ast H\left(( u,v)\sağ). $$

Bir fonksiyonun dürtü fonksiyonuna sahip evrişimi şu şekilde temsil edilebilir:

$$ \sum\limits_(x=0)^M (\sum\limits_(y=0)^N (s\left((x,y) \right)) ) \delta \left((x-x_0 , y-y_0 )\sağ)=s(x_0 ,y_0). $$

Darbe fonksiyonunun Fourier dönüşümü

$$ F\left((u,v) \right)=\frac(1)(MN)\sum\limits_(x=0)^M (\sum\limits_(y=0)^N (\delta \ left((x,y) \right) ) ) e^( (-2\pi j\left((\frac(ux)(M)+\frac(vy)(N)) \right)) ) =\ frac(1)(MN). $$

$f(x,y) = \delta (x,y)$ olsun, sonra evrişim

$$ f\left((x,y) \right)\ast h(x,y)=\frac(1)(MN)h\left((x,y) \right), $$

$$ \Phi \left[ (\delta \left((x,y) \right)\ast h(x,y)) \right]=\Phi \left[ (\delta \left((x,y) \right)) \right]H\left((u,v) \right)=\frac(1)(MN)H\left((u,v) \right). $$

Bu ifadelerden, frekans ve uzaysal alanlardaki filtre fonksiyonlarının Fourier dönüşümü yoluyla birbiriyle ilişkili olduğu açıktır. Frekans alanındaki belirli bir filtre fonksiyonu için, ters Fourier dönüşümünü uygulayarak uzaysal alanda karşılık gelen bir filtreyi bulmak her zaman mümkündür. Aynı durum ters durum için de geçerlidir. Bu ilişkiyi kullanarak, uzaysal doğrusal filtreleri sentezlemek için bir prosedür tanımlanabilir.

1. Filtrenin gerekli özelliklerini (şeklini) frekans alanında belirliyoruz.
2. Ters Fourier dönüşümünü gerçekleştiriyoruz.
3. Ortaya çıkan filtre, uzaysal evrişim için bir maske olarak kullanılabilir ve maskenin boyutu, orijinal filtrenin boyutuna kıyasla azaltılabilir.

($\textit(İdeal alçak geçiren filtre)$) $H(u,v)$ şu şekle sahiptir: $$H(u,v) = 1, \quad \mbox(if )D(u,v)< D_0 ,$$ $$H(u,v) = 0, \quad \mbox{если }D(u,v) \ge D_0 ,$$ где $D\left({u,v} \right)=\sqrt {\left({u-\frac{M}{2}} \right)^2+\left({v-\frac{N}{2}} \right)^2}$ - расстояние от центра частотной плоскости.

($\textit(İdeal yüksek geçiş filtresi)$), ideal alçak geçiş filtresinin ters çevrilmesiyle elde edilir:

$$ H"(u,v) = 1-H(u,v). $$

Burada düşük frekanslı bileşenler tamamen bastırılırken yüksek frekanslı bileşenler korunur. Bununla birlikte, ideal bir alçak geçişli filtre durumunda olduğu gibi, bunun kullanımı da önemli ölçüde distorsiyon görünümüyle doludur.

Filtreleri minimum bozulmayla sentezlemek için çeşitli yaklaşımlar kullanılır. Bunlardan biri üstel tabanlı filtre sentezidir. Bu tür filtreler, ortaya çıkan görüntüye minimum düzeyde bozulma katar ve frekans alanında sentez için uygundur.

Gerçek Gauss fonksiyonuna dayanan bir filtre ailesi, görüntü işlemede yaygın olarak kullanılmaktadır.

$\textit(Alçak geçiren Gauss filtresi)$ şu şekle sahiptir:

$$ h\left(x \right)=\sqrt (2\pi ) \sigma Ae^(-2\left((\pi \sigma x) \right)^2) \mbox( ve ) H\left( u \right)=Ae^(-\frac(u^2)(2\sigma ^2)) $$

Frekans alanındaki filtre profili ne kadar darsa ($\sigma $ ne kadar büyükse), uzaysal alanda o kadar geniştir.

($\textit(Yüksek geçişli Gauss filtresi)$) şu şekle sahiptir:

$$ h\left(x \sağ)=\sqrt (2\pi ) \sigma _A Ae^(-2\left((\pi \sigma _A x) \sağ)^2)-\sqrt (2\pi ) \sigma _B Be^(-2\left((\pi \sigma _B x) \right)^2 ), $$

$$ H\left(u \right)=Ae^(-\frac(u^2)(2\sigma _A^2 ))-Be^(-\frac(u^2)(2\sigma _B^2 )). $$

İki boyutlu durumda ($\it(alçak geçiş)$), Gauss filtresi şuna benzer:

$$ H\left((u,v) \right)=e^(-\frac(D^2\left((u,v) \right))(2D_0^2 )). $$

($\it(Yüksek Geçiş)$) Gauss filtresi şu şekildedir:

$$ H\left((u,v) \right)=1-e^(-\frac(D^2\left((u,v) \right))(2D_0^2 )). $$

Frekans alanında (Şekil 17 - 22) bir görüntü filtreleme örneğini (Şekil 1) ele alalım. Bir görüntünün frekans filtrelemesinin hem yumuşatma ($\textit(alçak geçişli filtreleme)$) hem de konturları ve küçük boyutlu nesneleri vurgulama ($\textit(yüksek geçişli filtreleme)$) anlamına gelebileceğini unutmayın.

Olarak Şekil l'de görülebilir. Şekil 17, 19'da, görüntünün düşük frekanslı bileşeninde filtreleme "gücü" arttıkça, görüntünün "görünür odak dışılığının" veya $\it(blur)$ etkisi giderek daha belirgin hale gelir. Aynı zamanda, görüntünün bilgi içeriğinin çoğu, başlangıçta yalnızca nesnelerin dış hatlarının gözlemlendiği yüksek frekanslı bileşene yavaş yavaş geçer (Şekil 18, 20 - 22).

Şimdi görüntüdeki toplam Gauss gürültüsünün (Şekil 7) varlığında yüksek geçişli ve alçak geçişli filtrelerin (Şekil 23 - 28) davranışını ele alalım.

Olarak Şekil l'de görülebilir. Şekil 23, 25'e göre, düşük frekanslı filtrelerin ilave rastgele gürültüyü bastırma özellikleri, daha önce dikkate alınan doğrusal filtrelerin özelliklerine benzer - yeterli filtre gücüyle gürültü bastırılır, ancak bunun bedeli, konturların güçlü bir şekilde bulanıklaştırılması ve "odaklanmanın bozulmasıdır" ” resmin tamamının. Gürültülü bir görüntünün yüksek frekanslı bileşeni bilgilendirici olmaktan çıkar, çünkü kontur ve nesne bilgilerine ek olarak gürültü bileşeni de artık orada tamamen mevcuttur (Şekil 27, 28).

Gürültü prosesinin istatistiksel modelinin ve/veya görüntü iletim kanalının optik transfer fonksiyonunun bilindiği durumda frekans yöntemlerinin kullanılması en uygunudur. Yeniden yapılandırma filtresi olarak aşağıdaki formun genelleştirilmiş kontrollü filtresini ($\sigma$ ve $\mu$ parametrelerine göre) seçerek bu tür önsel verileri hesaba katmak uygundur:

$$ F(w_1,w_2)= \left[ ( \frac (1) (P(w_1,w_2)) )\right] \cdot \left[ (\frac ((\vert P(w_1,w_2) \vert) )^2) (\vert P(w_1,w_2) \vert ^2 + \alpha \vert Q(w_1,w_2) \vert ^2) )\right]. $$

nerede 0$< \sigma < 1$, $0 < \mu < 1$ - назначаемые параметры фильтра, $P(w_{1}$, $w_{2})$ - передаточная функция системы, $Q(w_{1}$, $w_{2})$ - стабилизатор фильтра, согласованный с энергетическим спектром фона. Выбор параметров $\sigma = 1$, $\mu = 0$ приводит к чисто инверсной фильтрации, $\sigma =\mu = 1$ к \it{винеровской фильтрации}, что позволяет получить изображение, близкое к истинному в смысле минимума СКО при условии, что спектры плотности мощности изображения и его шумовой компоненты априорно известны. Для дальнейшего улучшения эффекта сглаживания в алгоритм линейной (винеровской) фильтрации вводят адаптацию, основанную на оценке локальных статистик: математического ожидания $M(P)$ и дисперсии $\sigma (P)$. Этот алгоритм эффективно фильтрует засоренные однородные поверхности (области) фона. Однако при попадании в скользящее окно обработки неоднородных участков фона импульсная характеристика фильтра сужается ввиду резкого изменения локальных статистик, и эти неоднородности (контуры, пятна) передаются практически без расфокусировки, свойственной неадаптивным методам линейной фильтрации.

Doğrusal filtreleme yöntemlerinin avantajları arasında açık fiziksel anlamları ve sonuçların analiz kolaylığı yer alır. Bununla birlikte, sinyal-gürültü oranındaki keskin bir bozulma, alan gürültüsünün olası değişkenleri ve yüksek genlikli darbe gürültüsünün varlığı ile doğrusal ön işleme yöntemleri yetersiz olabilir. Bu durumda doğrusal olmayan yöntemler çok daha güçlüdür.

giriiş

Laboratuvar dersi sırasında ayrık trigonometrik dönüşümün (DTP) olanakları aşağıdaki bakış açılarından incelenmiştir:

1. Verilen kazanın geri döndürülebilirlik özelliğini kontrol ettik.

2. Önerilen kazanın doğrusallığı araştırıldı.

3. Test edilen kazanın tekrar spektrumunun özelliklerini inceledik.

4. Bir kazada spektrumun simetrik yansımasının varlığını belirledik, yani

4.1. merkezi simetrinin varlığı,

4.2. eksenel (dikey) simetrinin varlığı.

5. Sinyaldeki faz kaymalarının ortaya çıkan kaza üzerindeki etkisini değerlendirdik.

6. Verilen dönüşüm için benzerlik özelliğinin varlığı kontrol edildi.

7. Belirli bir kazayı kullanarak sinyalleri filtreleme olasılığını araştırdık.

8. Çalışmaya konu olan trafik kazasında enerjinin korunumunu deneysel olarak test ettik.

9. Bu kaza ile ayrık Fourier dönüşümü arasında bir bağlantı keşfettik.

Daha temsili bir analiz için çeşitli giriş sinyalleri de dikkate alındı.

Ayrık fonksiyonel dönüşümler arasında en ünlüsü ayrık Fourier dönüşümüdür (DFT)

Ayrık Fourier dönüşümü

Ayrık Fourier dönüşümü, zamanın ayrıklaştırılmış bir periyodik fonksiyonunun çizgi spektrumunu belirler. Ters ayrık Fourier dönüşümü, zaman fonksiyonunu spektrumundan yeniden yapılandırmanıza olanak tanır. Bu dönüşümler genellikle sırasıyla DFT ve ODFT olarak kısaltılır.

DFT periyodik fonksiyonları analiz etmek için kullanılır ve Fourier serisi teorisinden elde edilebilir. x0(t), periyodu P ve frekansı f0 = 1/P olan sürekli bir periyodik fonksiyon olsun;

x0(t) fonksiyonu bir Fourier serisine genişletilebilir:

burada genleşme katsayıları X0(n) formülle verilir

Genellikle x0(t) gerçek bir fonksiyondur ve bu durumda X0(n) karmaşıktır (ancak bu kısıtlama gerekli değildir). x0'ı zamanın bir fonksiyonu olarak ele aldığımız için, X0(n), x0(t)'nin karmaşık spektrumu olarak adlandırılabilir. X0(n)'nin gerçek ve sanal kısımlarını kullanarak, x0(t) salınımını oluşturan bileşenlerin genliği ve fazı bulunabilir.

Periyodik fonksiyon x0(t)'nin ayrıklaştırılmasını ele alalım. Bu fonksiyonun benzersiz bir şekilde ayrıklaştırılabilmesi için spektrumunun belirli bir f1 frekansından daha yüksek frekansa sahip bileşenler içermemesi gerekir;

burada n1, f1 frekansını belirten n'nin tamsayı değeridir.

İncirde. Şekil 1, bu kadar sınırlı bir spektrumu ve buna karşılık gelen titreşimi göstermektedir.

örnekleme aralığı T eşittir

yani dönem başına örnek sayısı

İncir. 1. Sınırlı frekans bandı ve spektrumu X0(n) olan periyodik fonksiyon x0(t).

1 Ayrıklaştırmanın bir sonucu olarak, formun T'sine göre normalleştirilmiş bir periyodik salınım elde ederiz.

Bu salınım, periyoduna eşit bir aralıkta tanımlanır;

x(t/T) periyodik bir fonksiyon olduğundan Fourier serisinin katsayılarını hesaplamak için ilişki (2) kullanılır.

(Bölende P'nin /V ile değiştirilmesi ve integralin sınırları normalleştirilmiş bir değişkene geçişe karşılık gelir.) İfadeyi (3) değiştirerek şunu elde ederiz:

biliniyor ki

Son olarak, tanım gereği şu gerçeği dikkate alarak

X(k)'yi X(n)'ye bağlayan ilişki, eğer t=kT'yi değiştirirsek ve x0(t) fonksiyonunun spektrumunun sınırlı bir genişliği ile toplamın sınırlı sayıda terim içerir. Bu yüzden,

x(k)'nin periyodik bir fonksiyon olduğu unutulmamalıdır.

ve benzer şekilde

Spektrumun periyodik olması, herhangi bir ayrıklaştırılmış fonksiyonun spektrumunun periyodikliği ile açıklanır ve ayrık doğası, ayrıklaştırılmış fonksiyonun kendisinin de periyodik olması gerçeğinden kaynaklanmaktadır.

Dolayısıyla, bir x0(t) periyodik fonksiyonunu ayrıklaştırırken, ilişki (4), x0(t) örneklerinin kullanılmasına izin vererek 0 ≤ n ≤ N - 1 aralığında X0 spektrumuna tam olarak eşit olan X(n) spektrumunu bulmaya izin verir. (n) orijinal periyodik fonksiyonun. X(k) fonksiyonu ve spektrumu Şekil 2'de grafiksel olarak sunulmaktadır. 2. İlişki (5.4) örnekleme teoremi temel alınarak elde edildiğinden, orijinal integral ilişkinin (2) doğru ve ekonomik (hesaplamalarda) eşdeğeridir ve bilgisayarda genleşme katsayılarını hesaplamak için kullanılabilir. (4) ve (5) bağıntılarına sırasıyla ayrık Fourier dönüşümü (DFT) ve ters ayrık Fourier dönüşümü (IDFT) adını vereceğiz. Burada n değişkeninin sıfırdan N-1'e kadar değiştiğini unutmayın. Ortaya çıkan spektrum aşağıdaki gibi yorumlanabilir. İlk (N/2-1) noktalar X(n), Şekil 2'de gösterildiği gibi pozitif frekanslarda (N/2 - 1) spektral çizgiler X0(n)'e karşılık gelir. 5.3 ve son (N/2-1) noktalar X(n), negatif frekanslardaki (N/2-1) spektral çizgilere karşılık gelir.

(4) ve (5) bağıntılarıyla verilen dönüşüm çifti başka bir biçimde de ortaya çıkar. Örneğin çarpan 1/N ve üssün eksi işareti hem direkt hem de ters dönüşümle yazılabilir, genel anlamı değişmez.

Doğal olarak, bu durumda spektrum, formül (2) ile tanımlanan spektrumla doğrudan tanımlanamaz. Bazen her iki dönüşüm de aynı (1 / N)1/2 çarpanlarıyla verilir.

İncir. 2. Ayrıklaştırılmış periyodik fonksiyon x(k) ve periyodik spektrumu X(n).

İncir. 3. Fourier serisinin katsayıları ile DFT arasındaki ilişki.

DFT'nin Özellikleri

DFT'nin bazı özellikleri sinyal işlemenin pratik konularında önemli bir rol oynamaktadır.

Doğrusallık

Eğer xp(n) ve ur(n) periyodik dizilerse (her biri N örnek periyoduna sahip) ve Xp(k) ve Yp(k) bunların DFT'leriyse, o zaman xp(n) + dizisinin ayrık Fourier dönüşümü + ur(n ) eşittir Хр(k) + Yp(k). Bu aynı zamanda sonlu uzunluktaki diziler için de geçerlidir.

Vardiya

Eğer xp(n) dizisi N örnek periyoduyla periyodikse ve DFT'si Xp(k)'ye eşitse, xp(n-n0) biçimindeki bir periyodik dizinin DFT'si eşit olacaktır.

İncir. 4. Kaydırılmış bir dizinin DFT'sinin tanımına doğru.

Sonlu uzunluktaki dizileri analiz ederken dizinin zaman kaymasının özel doğasını hesaba katmak gerekir. Yani ŞEKİL 2'de. Şekil 4'te a, N numune uzunluğuna sahip sonlu bir x(n) dizisini göstermektedir. Aynı yerde, çarpılar x(n) ile aynı DFT'ye sahip olan eşdeğer periyodik dizi xp(n)'nin örneklerini göstermektedir. Kaydırılan x(n - n0) ve n0 dizisinin DFT'sini bulmak için< N, следует рассмотреть сдвинутую периодическую последовательность Хр(n - n0) и в качестве эквивалентной сдвинутой конечной последовательности (имеющей ДПФ j принять отрезок последовательности хр(n - n0) в интервале 0 ≤ n ≤ N - 1. Таким образом, с точки зрения ДПФ последовательность х(n – n0) получается путем кругового сдвига элементов последовательности х(n) на n0 отсчетов

Simetrinin özellikleri

Eğer v/V örnekleri periyoduna sahip periyodik bir xp(n) dizisi gerçekse, bu durumda onun DFT xp(k)'si aşağıdaki simetri koşullarını karşılar:

Benzer eşitlikler, N-noktalı DFT X(k)'ye sahip sonlu bir gerçek dizi x(n) için geçerlidir. Eğer xp(n) dizisi için ek bir simetri koşulu getirirsek, yani şunu varsayalım:

o zaman Xp(k)'nin yalnızca gerçek olabileceği ortaya çıkıyor.

Çoğu zaman gerçek dizilerle uğraşmak zorunda olduğumuz için, bir DFT'yi hesaplayarak simetri özelliklerini kullanarak iki dizinin DFT'sini elde edebiliriz (6). Sırasıyla N örnek periyotları ve N noktalı DFT'ler xp(k) ve Yp(k) ile gerçek periyodik xp(n) ve yp(n) dizilerini ele alalım. Formdaki zp(n) karmaşık dizisini tanıtalım

DFT'si şuna eşittir:

Eşitliğin gerçek ve sanal kısımlarını (10) ayırarak şunu elde ederiz:

Gerçek kısımlar Xp(k) ve Yp(k) simetriktir ve sanal kısımlar antisimetriktir, dolayısıyla toplama ve çıkarma işlemleri kullanılarak kolayca ayrılabilirler:

Yani, bir N-noktalı DFT'yi hesaplayarak, N uzunluğundaki numunelerin iki gerçek dizisini aynı anda dönüştürmek mümkündür. Bu diziler aynı zamanda simetrikse, DFT'yi elde etmek için gereken işlem sayısı daha da azaltılabilir.

İlgili bilgi.

Mevcut görüntüyü bir standartla karşılaştırmaya yönelik geleneksel "giriş seviyesi" tekniği, görüntülerin parlaklığın iki boyutlu işlevleri (ayrı iki boyutlu yoğunluk matrisleri) olarak görüntülenmesine dayanır. Bu durumda ya görüntüler arasındaki mesafe ya da yakınlığın ölçüsü ölçülür.

Kural olarak, görüntüler arasındaki mesafeyi hesaplamak için yoğunluk farklarının modüllerinin veya karelerinin toplamı olan bir formül kullanılır:

d(X,Y) = TOPLA (X - Y)^2

Hesaplama sayısını önemli ölçüde azaltabilen yöntemlerden biri, aralarında farklı uzaklıklarda bulunan iki görüntünün çakışma ölçüsünü hesaplamak için Fourier dönüşümlerinin ve ayrık Fourier dönüşümlerinin kullanılmasıdır. Bu durumda, hesaplamalar birbirine göre görüntü kaymalarının çeşitli kombinasyonları için eş zamanlı olarak gerçekleştirilir.

Fourier dönüşümlerini (her türlü hızlı versiyonda) uygulayan çok sayıda kütüphanenin varlığı, görüntü karşılaştırma algoritmalarının uygulanmasını çok zor bir programlama görevi olmaktan çıkarır.

Sorunun formülasyonu

• İki görüntü X ve Y verilsin - bir görüntü ve bir örnek, boyutları sırasıyla (N1,N2) ve (M1,M2) ve Ni > Mi

resimde

Görüntüler arasında bir ölçü olarak korelasyon

iki fonksiyon F ve G'ye miktar denir:

Bu miktar, matematik ve geometri derslerinden iyi bilinmektedir. doğrusal uzaylar burada skaler çarpım denir. Formülü resimler arasında ölçü olarak kullanacağız:

m(X,Y) = TOPLA (X * Y) / (SQRT (TOPLAM X ^2) * SQRT (TOPLA Y ^2))

veya

m(X,Y) = /(KARE( ) * KARE ( ))

Bu miktar, vektörlerin skaler çarpımının işleminden elde edilir (görüntülerin çok boyutlu bir uzayda vektörler olduğu düşünüldüğünde). Ve daha da fazlası - aynı formül standarttır istatistiksel formül iki olasılık dağılımının çakışması hipotezi için kriter.

Not:
Görüntü parçaları arasındaki korelasyonu hesaplarken, eğer bir görüntü diğerinden küçükse, yalnızca kesişen parçaların normlarının değerine böleceğiz.

İki fonksiyonun evrişimi

Tanıma göre, iki F ve G fonksiyonunun evrişimine FxG fonksiyonu denir:

G'(t) = G(-t) ve F'(t) = F(-t) olsun, o zaman eşitliklerin geçerliliği açıktır:

• FхF’(0) = TOPLA F(i)^2 – skaler çarpım F vektörü kendi üzerine
• GxG’(0) = TOPLA G(j)^2 – G vektörünün ve kendisinin skaler çarpımı
• FхG’(0) = TOPLA F(i)*G(i) – iki F ve G vektörünün skaler çarpımı

FxG'(t)'nin, bir vektörün diğerine göre t adımı kadar kaydırılması sonucunda elde edilen korelasyona eşit olduğu da açıktır (bu, değerlerin korelasyon formülüne açıkça yerleştirilmesiyle kolayca doğrulanabilir).

Fourier dönüşümü (ℱ), gerçek bir değişkenin bir fonksiyonunu başka bir fonksiyonla, yine bir gerçek değişkenle ilişkilendiren bir işlemdir. Bu yeni özellik orijinal fonksiyonu temel bileşenlere ayırırken katsayıları (“genlikler”) tanımlar - harmonik titreşimler farklı frekanslarla.

Gerçek değişkenli bir f fonksiyonunun Fourier dönüşümü integraldir ve aşağıdaki formülle verilir:

Farklı kaynaklarda integralin önündeki katsayı seçiminde, üstelik üslerdeki “-” işaretinin seçiminde yukarıdakilerden farklı tanımlar verilebilir. Ancak bazı formüllerin görünümü değişse de tüm özellikler aynı olacaktır.

Ayrıca bu kavramın çeşitli genellemeleri de mevcuttur.

Çok boyutlu Fourier dönüşümü

ℝ^n uzayında tanımlanan fonksiyonların Fourier dönüşümü aşağıdaki formülle belirlenir:

Bu durumda ters dönüşüm aşağıdaki formülle verilir:

Daha önce olduğu gibi, farklı kaynaklarçok boyutlu bir Fourier dönüşümünün tanımları, integralden önceki sabitin seçiminde farklılık gösterebilir.

Ayrık Fourier dönüşümü

Ayrık Fourier Dönüşümü (İngiliz literatüründe DFT, Ayrık Fourier Dönüşümü), dijital sinyal işleme algoritmalarında yaygın olarak kullanılan Fourier dönüşümlerinden biridir (modifikasyonları MP3'te ses sıkıştırmada, JPEG'de görüntü sıkıştırmada vb. kullanılır) ve ayrıca ayrık (örneğin sayısallaştırılmış analog) bir sinyaldeki frekansların analizi ile ilgili diğer alanlar. Ayrık Fourier dönüşümü girdi olarak gerektirir ayrık fonksiyon. Bu tür işlevler genellikle örnekleme yoluyla oluşturulur (değerlerin örneklenmesi) sürekli fonksiyonlar). Ayrık Fourier dönüşümleri çözüme yardımcı olur diferansiyel denklemler Kısmi türevlerde ve evrişim gibi işlemleri gerçekleştirir. Ayrık Fourier dönüşümleri istatistikte, zaman serilerinin analizinde de aktif olarak kullanılmaktadır. Çok boyutlu ayrık Fourier dönüşümleri vardır.

Ayrık dönüşüm formülleri

Doğrudan dönüşüm:

Ters dönüşüm:

Ayrık Fourier dönüşümü, zaman örneklerinin bir vektörünü aynı uzunluktaki spektral örneklerin bir vektörüne dönüştüren doğrusal bir dönüşümdür. Böylece dönüşüm simetrik çarpma olarak uygulanabilir. Kare matris vektöre:

Evrişimi hesaplamak için Fourier dönüşümleri

Biri dikkat çekici özellikler Fourier dönüşümleri, tanımlanan iki fonksiyonun korelasyonunu gerçek bir argüman üzerinde (kullanırken) hızlı bir şekilde hesaplama yeteneğidir. klasik formül) veya sonlu bir halka üzerinde (ayrık dönüşümler kullanıldığında).

Ve buna rağmen benzer özellikler birçoğunun doğasında var doğrusal dönüşümler pratik kullanım için, evrişim işlemini hesaplamak için tanımımıza göre formül kullanılır

Nerede

• FFT – operasyon doğrudan dönüşüm Fourier
• BFT – ters Fourier dönüşümü işlemi

Eşitliğin doğruluğunu kontrol etmek oldukça kolaydır - Fourier dönüşümlerini formüllere açıkça koyarak ve elde edilen formülleri azaltarak

Korelasyonu hesaplamak için Fourier dönüşümleri

İzin vermek (t), bir vektörün diğerine göre t adımı kadar kaydırılması sonucunda elde edilen korelasyona eşittir
Daha sonra, daha önce gösterildiği gibi,

(t) = FхG'(t) = BFT (FFT(F)*FFT(G'))

Fourier dönüşüm algoritmasının uygulamaları aşağıdakiler aracılığıyla kullanılırsa: Karışık sayılar o zaman bu tür dönüşümlerin dikkat çekici başka bir özelliği daha vardır:

FFT(G') = EŞLEŞİK (FFT(G))

KONJÜGAT (FFT(G)) FFT(G) matrisinin eşlenik elemanlarından oluşan bir matristir
Böylece elde ederiz

(t) = BFT (FFT(F)*EŞLEŞİK (FFT(G)))

Problemin çözümü için Fourier dönüşümleri

m(X,Y) (i,j) = (i,j) / (|X|(i,j)) * |Y|(i,j))

bunu anladık

• = XxY’
• |X|^2 = = XxX’xE’ = BFT (FFT(X) * KOJÜGAT (FFT(X)) * KONFÜGAT (FFT(E)))
• |Y|^2 = = YxY’xE’ = BFT (FFT(Y) * EŞLEŞEN (FFT(Y)) * EŞLEŞİK (FFT(E)))

Nerede

• |X|(i,j) – (i,j) kaydırması altındaki X görüntüsünün genel kısmının normu
• |Y|(i,j) – (i,j) kaydırması altındaki Y görüntüsünün genel kısmının normu

Sorunu çözmek için formüllerin basitleştirilmesi

Bir örnek bulma problemini çözerken, örneğin ilave normalizasyonu gereksizdir ve ortak kısım için normun hesaplanması, bu ortak kısımdaki piksellerin parlaklıklarının toplamı veya karelerinin toplamı ile değiştirilebilir. bu ortak kısımdaki parlaklık
Birbirine göre (i,j) kaydırıldığında görüntüler arasındaki mesafeyi tahmin etmek için formülü kullanırken

m(X,Y) (i,j) = (i,j) / |X|^2(i,j),

bunu anladık

• = BFT (FFT(X) * EŞLEŞİK (FFT(Y)))
• = BFT (KAREBÜYÜKLÜĞÜ(FFT(X)) * EŞLEŞİK (FFT(E)))

Nerede

• (i,j) – X ve Y görüntülerinin birbirine göre kaydırılmasıyla elde edilen iki görüntünün skaler çarpımı
• E - X ve Y'nin minimum boyutlarına eşit boyutta ve tek değerlerle doldurulmuş bir görüntü (yani, X ve Y'nin karşılaştırıldığı bir "kare")
• (i,j) – kaydırmalı X görüntüsünün genel kısmının normu (piksel parlaklıklarının toplamı) (i,j)
• FFT - doğrudan iki boyutlu ayrık Fourier dönüşümünün çalışması
• BFT - ters iki boyutlu ayrık Fourier dönüşümü işlemi
• BİRLEŞİK – eşlenik elemanların matrisini hesaplama işlemi
• SQUAREMAGNITUDE – elemanların kare genliklerinin matrisini hesaplama işlemi

Tam görüntüde bir parçayı aramak için algoritma

• İki görüntü X ve Y verilsin - bir görüntü ve bir örnek, boyutları sırasıyla (N1,N2) ve (M1,M2) ve Ni > Mi
• Y örneğinin koordinatlarını bulmanız gerekir. tam resim X'i bulun ve tahmini değeri hesaplayın - bir yakınlık ölçüsü.

1. Y görüntüsünü sıfırlarla doldurarak (N1,N2) boyutuna genişletin
2. Boyut birimlerinden (M1,M2) E görüntüsünü oluşturun ve sıfırlarla doldurarak boyuta (N1,N2) genişletin
3. Hesaplamak = BFT (FFT(X) * EŞLEŞİK (FFT(Y)))
4. Hesaplamak = BFT (KAREBÜYÜKLÜĞÜ(FFT(X)) * EŞLEŞİK (FFT(E)))
5. M'yi hesaplayın = (f + )/(f + )
6. M matrisinde aşağıdaki elemanı bulun: maksimum değer– bu elemanın koordinatları, numunenin tam görüntüdeki istenen konumudur ve değer, karşılaştırma ölçüsünün tahminine eşittir.

Not:
Ayrık Fourier dönüşümü kullanıldığında, M matrisi ayrıca görüntülerin kendi aralarındaki döngüsel kaymasından elde edilen öğeleri de içerir. Bu nedenle, döngüsel çerçeve kaymasını analiz etmenize gerek yoksa, o zaman maksimum eleman M matrisindeki (0,0)-(N1-M1, N2-M2) bölgesi ile sınırlı olmalıdır.

Uygulama örnekleri

Uygulanan algoritmalar açık kaynak FFTTools kütüphanesinin bir parçasıdır. İnternet adresi: github.com/dprotopopov/FFTTools

Kullanılan yazılım

• Microsoft Visual Studio 2013 C# - ortam ve programlama dili
• EmguCV/OpenCV – Görüntü işlemeye yönelik yapı ve algoritmalardan oluşan C++ kitaplığı
• FFTWSharp/FFTW – Hızlı ayrık Fourier dönüşüm algoritmalarını uygulayan C++ kitaplığı

///

/// Değerler matrisiözel Matris Yakala(Resim resim) ( const double f = 1,0; int uzunluk = image.Data.Length; int n0 = image.Data.GetLength(0); int n1 = image.Data.GetLength(1); int n2 = image.Data.GetLength (2); Debug.Assert(n2 == 1); // FFTW yapılarını tahsis edin giriş = new fftw_complexarray(uzunluk); var çıktı = new fftw_complexarray(giriş, çıkış, fftw_direction.Forward, fftw_flags.Estimate); fftw_plan geriye = fftw_plan.dft_3d(n0, n1, n2, giriş, çıkış, fftw_direction.Backward, fftw_flags.Estimate); (n0, n1); double[,] modelVeri = _patternImage.Data; double[,] imageData = resim.Veri; double[,] veri = matris.Veri; var çiftler = yeni çiftler; // Bölen Kopyasını hesapla(patternData, data); Buffer.BlockCopy(veri, 0, doubles, 0, uzunluk*sizeof (double)); input.SetData(doubles.Select(x => new Complex(x, 0)).ToArray()); forward.Execute(); Karmaşık karmaşık = çıktı.GetData_Complex(); Buffer.BlockCopy(imageData, 0, doubles, 0, uzunluk*sizeof (double)); input.SetData(doubles.Select(x => new Complex(x, 0)).ToArray()); forward.Execute(); input.SetData(output.GetData_Complex().Zip(karmaşık, (x, y) => doubles1 = çıktı.GetData_Complex().Select(x => x.Büyüklük); if (_fastMode) ( // Fast Result Buffer.BlockCopy(doubles1.ToArray(), 0, data, 0, uzunluk*sizeof (double)); dönüş matrisi; ) // Bölücüyü (diğer adıyla Güç) hesapla input.SetData(doubles) .Select(x => new Complex(x*x, 0)).ToArray()); forward.Execute(); karmaşık = çıktı.GetData_Complex(); CopyAndReplace(_patternImage.Data, data); Buffer.BlockCopy(veri, 0, doubles, 0, uzunluk*sizeof (double)); input.SetData(doubles.Select(x => new Complex(x, 0)).ToArray()); forward.Execute(); input.SetData(complex.Zip(output.GetData_Complex(), (x, y) => x*Complex.Conjugate(y)).ToArray()); geriye doğru.Execute(); ISayılandırılabilir doubles2 = çıktı.GetData_Complex().Select(x => x.Büyüklük); // Result Buffer.BlockCopy(doubles1.Zip(doubles2, (x, y) => (f + x*x)/(f + y))).ToArray(), 0, data, 0, uzunluk*sizeof (double) )); dönüş matrisi; )
///

/// 3B diziyi 2B diziye kopyalayın (boyutlar farklı olabilir) /// Kopyalanan verileri çevirin /// Son boyutu azaltın ///

/// Giriş dizisi /// Çıkış dizisiözel statik void Copy(double[,] giriş, double[,] çıkış) ( int n0 = çıktı.GetLength(0); int n1 = çıktı.GetLength(1); int m0 ​​= Math.Min(n0, giriş) .GetLength (0)); int m1 = Math.Min(n1, input.GetLength(1)); int m2 = input.GetLength(2);< m0; i++) for (int j = 0; j < m1; j++) output = input; for (int k = 1; k < m2; k++) for (int i = 0; i < m0; i++) for (int j = 0; j < m1; j++) output += input; } ///

/// 3B diziyi 2B diziye kopyalayın (boyutlar farklı olabilir) /// Değere göre kopyalanan öğeleri değiştirin /// Kopyalanan verileri çevirin /// Son boyutu azaltın ///

/// Giriş dizisi /// Çıkış dizisi /// Kopyalanan verilerin değiştirileceği değerözel statik void CopyAndReplace(double[,] giriş, double[,] çıktı, double değer = 1,0) ( int n0 = çıktı.GetLength(0); int n1 = çıktı.GetLength(1); int m0 ​​= Matematik. Min( n0, input.GetLength(0)); int m1 = Math.Min(n1, input.GetLength(1)); int m2 = input.GetLength(2);< m0; i++) for (int j = 0; j < m1; j++) output = value; } ///

/// Matriste maksimum bir eleman bulun ///

/// Değerler matrisi /// Maksimum öğe dizini /// Maksimum öğe dizini /// Maksimum elemanın değeri genel geçersiz Max(Matris matris, out int x, out int y, out double değer) ( double[,] veri = matris.Veri; int n0 = veri.GetLength(0); int n1 = veri.GetLength(1); değer = veri ; x = y = 0; for (int i = 0; i< n0; i++) { for (int j = 0; j < n1; j++) { if (data < value) continue; value = data; x = j; y = i; } } } ///

/// En Hızlı Fourier Dönüşümü ile desen bitmap'ini yakalayın ///

/// Değer dizisi genel Matris Catch(Bitmap bitmap) ( kullanarak (var image = new Image) (bitmap)) return Catch(image); )

ısırma yakaladım

Edebiyat

1. A.L. Dmitriev. Optik yöntemler bilgi işlem. öğretici. St.Petersburg SPGUITMO 2005. 46 s.
2. A.A.Akaev, S.A. Mayorov “Optik bilgi işleme yöntemleri” M .: 1988
3. J. Goodman “Fourier optiğine giriş” M.: Mir 1970

Sürekli sinyallerin örneklenmesiyle ilgili önceki bölümden, gerçek sinyallerin hem spektral hem de zaman alanındaki örneklerle tanımlanabileceği anlaşılmaktadır. Hem ayrık spektrum hem de ayrık sinyal, orijinal sürekli (sürekli) sinyali tamamen tanımlar. Bununla birlikte, belirli bir ayrık sinyalden ayrık bir spektrum bulmak için zaman alıcı hesaplamalar yapmak gerekir: ilk olarak, ayrık sinyalden yeniden yapılandırma sürekli sinyal, daha sonra sürekli bir spektrum bulmak için Fourier dönüşümünü kullanın ve ardından onu ayrıklaştırın. Ters dönüşüm için de benzer bir prosedür izlenmelidir. Ayrık bir Fourier dönüşümü kullanılarak ayrık bir sinyalden ayrık bir spektruma ve tam tersi doğrudan geçiş mümkündür.

Serbestlik derecesi sayısı eşit olan sonlu süreli sürekli bir sinyali ele alalım. Bu sinyal için genişlemeyi bir Kotelnikov serisinde yazabiliriz:

Kullanarak normal dönüşüm Bu sinyalin Fourier spektrumunu bulalım:

Bu formüldeki integralin doğrudan hesaplanması emek yoğun bir işlemdir. Ancak bunu başka bir şekilde yapmak zor değil.

İfadeyle belirlenen spektrumu düşünün

Ters Fourier dönüşümünü ona uyguladığımızda, bunun zaman fonksiyonuna karşılık geldiğini buluruz.

Açıkçası, ters ilişki de doğrudur

Gecikme teoremini kullanarak şunu yazabiliriz:

(3.2)'yi (3.1)'e değiştirerek spektrum için son ifadeyi elde ederiz.

Ayrık Fourier dönüşümüne gitmek için, ifade (3.3)'teki spektrum değerlerinin tüm frekans değerleri için değil, ayrık (örneklenmiş) olanlar için hesaplanması gerekir:

Sonuç olarak ayrık Fourier dönüşümü için son formülü elde ederiz.

Ayrık Fourier dönüşümünün özellikleri birçok yönden geleneksel Fourier dönüşümünün özelliklerine benzer. Yalnızca belirli bir özelliği not edelim;

ayrık Fourier dönüşümünün periyodikliği olarak adlandırılabilir.

Tam sayının nerede olduğu için formül (3.4) ile belirlenen değeri düşünün:

Böylece, ayrık Fourier dönüşümü şu şekildedir: periyodik fonksiyon periyodu eşit olan frekans Bu özellik, Bölüm'de tartışılan örneklenen sinyal spektrumunun periyodiklik özelliğine benzer. 2.

Şimdi spektrum örneklerinden sinyal örneklerini belirlememizi sağlayan ters ayrık Fourier dönüşümünün türetilmesine geçelim. Bunu yapmak için her zamanki ters Fourier dönüşümünü kullanıyoruz.

Sinyalin spektral yoğunluğunu Kotelnikov serisi şeklinde yazıyoruz

ve ters Fourier dönüşümünün integralinin yerine koyun

İfadedeki integral daha önce hesaplanan integrale (3.2) benzer. Bu benzetmeyi kullanarak şunu yazıyoruz:

(3.6)'yı (3.5)'e değiştirerek, zaman fonksiyonu için bir ifade elde ederiz.

İlişkiyi varsayarsak, ayrık bir sinyalin değerlerini belirlemek için bir formül elde ederiz, yani ters ayrık Fourier dönüşümüne ulaşırız

A'nın 0'dan 0'a kadar değerleri aldığı yer

Bazen, notasyon kolaylığı açısından, ayrık Fourier dönüşümünün periyodiklik özelliği kullanılarak, (3.8) ifadesindeki toplamanın sınırları değiştirilir ve ters ayrık Fourier dönüşümü şu şekilde yazılır:

Örneklemek için, ayrık Fourier dönüşümünü örneklenmiş bir üçgen darbeye uygulayın (Şekil 2'de beş örnek değerle tanımlanır).

Ayrık sinyal için bu ifadeyi ayrık Fourier dönüşümü formülünde (3.4) değiştirelim.

Karşılaştırma için bulalım spektral yoğunluk ilk üçgen darbe:

Ayrık spektrumun (3.11) üçgen darbenin (3.12) spektral yoğunluğunu doğru bir şekilde tanımlamadığını görmek kolaydır. Değerler, üçgen darbe spektrumunun karşılık gelen değerlerinden biraz farklıdır (Şekil 3.1, b).

Şimdi spektrumun ayrık değerlerini (3.11) ters ayrık Fourier dönüşümü (3.8) ifadesine koyalım:

Ayrık spektrumun değerleri ile sürekli spektrumun değerleri arasındaki farklılığa rağmen elde edilen sonuç, orijinal ayrık sinyalin formülüyle (3.11) tamamen örtüşmektedir.

Ele alınan örnek, ayrık Fourier dönüşümünün, tıpkı orijinal sürekli sinyalin spektrumunu her zaman doğru bir şekilde tanımlamadığını göstermektedir.

Pirinç. 3.1. Örneklenmiş bir üçgen darbenin ayrık Fourier dönüşümü

örneklenen sinyal her zaman orijinal sürekli sinyali doğru şekilde tanımlamaz. Bununla birlikte, ayrık bir sinyal ile onun ayrık Fourier dönüşümü arasındaki ilişki her zaman bire birdir ve doğrudan ve ters Fourier dönüşümlerinin formülü herhangi bir sayı için katıdır. ayrık değerler. Bu nedenle, ayrık Fourier dönüşümlerinin aparatı bağımsız bir öneme sahiptir ve herhangi bir sayısal diziye uygulanabilir.

Bu durumda ayrık Fourier dönüşümü formüllerinin biraz değiştirilmesi gerekir, çünkü soyut için sayı dizisiÖrnekleme aralığı ve sinyal süresi değerleri anlamsızdır. Bu nedenle formül (3.4)'te toplamın önündeki katsayı atlanır, yerine sinyal ve spektrumun referans değerleri gelir, ile gösterilir ve ayrık Fourier dönüşümü formülü şu şekilde yazılır:

Bu durumda ters ayrık Fourier dönüşümü şu şekildedir:

Formül (3.14) kullanılarak hesaplanan değerler, sürekli salınım spektrumunun örnek değerlerinden bir faktör kadar farklıdır. Örnek değerleri belirlemek için, formül (3.14) kullanılarak hesaplanan değerleri zaman örnekleme aralığının değeriyle çarpmanız gerekir:

(3.14), (3.15) dönüşümlerinin karşılıklı olarak ters olduğunu gösterelim. Bunu yapmak için, ayrık Fourier dönüşümünü (3.14) kullanarak rastgele bir sayısal dizi alın, diziyi bulun ve ona ters ayrık dönüşümü uygulayın.

Fourier (3.15). Ortaya çıkan diziyi belirtiyoruz

Toplamanın sırasını değiştirelim ve bu ifadeyi biraz dönüştürelim:

(3.16) ifadesinin iç toplamı if'e eşit, if'e eşittir. Dolayısıyla sayı dizileri birbiriyle çakıştığında. Böylece herhangi bir sayısal diziye doğrudan ve ters ayrık Fourier dönüşümü art arda uygulandığında sonuç aynı dizi olur.

Bu konuyu en basit örneklerle açıklayalım.

1. a'ya eşit bir örnek değerden oluşan en basit ayrık sinyali düşünün. Bu en basit diziyi ayrık Fourier dönüşümü formülüne (3.14) koyarak, şunu elde ederiz: Bir bireyin ayrık Fourier dönüşümü Sayısal değer aynı değere eşittir.

Ayrık Fourier dönüşümünün bir diğer önemli uygulaması, bir filtrenin çıkışındaki sinyalin belirli bir frekans yanıtıyla hesaplanmasıdır. Bir giriş sinyali verilirse, bunun için ayrık bir Fourier dönüşümü hesaplanabilir. Şimdi filtrenin frekans yanıtıyla çarparsak, çıkış sinyalinin ayrık Fourier dönüşümünü elde ederiz: Bundan sonra ters ayrık Fourier dönüşümünü kullanarak. filtre çıkışında sinyali bulabiliriz.

Giriş sinyalinin süresi uzunsa, parçalar halinde ayrık Fourier dönüşümü kullanılarak işlenebilir. Bunu yapmak için, giriş sinyalinin ilk N örneğini alın, bunların ayrık Fourier dönüşümünü hesaplayın ve filtrenin frekans yanıtıyla çarptıktan sonra, çıkış sinyalinin ilk N örneğini hesaplamak için ters ayrık Fourier dönüşümünü kullanın. Bundan sonra, giriş sinyalinin sonraki N örneği benzer şekilde işlenir, vb. Sinyal işlemenin doğruluğunu arttırmak için, işlenen örnek serileri kısmen üst üste gelebilir.

Bu sinyal işleme yönteminin avantajı, filtrenin frekans tepkisi tipi üzerinde herhangi bir kısıtlamanın bulunmamasıdır. Örneğin frekans tepkisi, geleneksel filtreler kullanılarak elde edilemeyen mükemmel bir dikdörtgen şekil olabilir.

Ayrık Fourier dönüşümü kullanan sinyal işleme, dijital filtreleme olarak adlandırılamaz. Her anlamda kelimeler. Gerçek zamanlı olarak çalışan geleneksel dijital filtreler, sinyali geldiği anda sürekli olarak işler ve ayrık bir Fourier dönüşümü kullanılarak çıkış sinyalinin hesaplanması, yalnızca giriş sinyalinin tamamı veya en azından N numunenin ilk serisi bilindikten sonra yapılabilir. Bu nedenle, ayrık Fourier dönüşümü kullanıldığında çıkış sinyali yalnızca belirli bir değerle elde edilebilir.

giriş sinyaline göre gecikme. Ancak bir sayıda pratik uygulamalarçıkış sinyalindeki bu tür bir gecikme önemli bir rol oynamaz ve daha sonra ayrık Fourier dönüşümü kullanılarak sinyal işlemenin uygun olduğu ortaya çıkar.