Išnagrinėjame diskretiško signalo, kuris segmente nurodomas jo paties rodmenimis, spektrinio vaizdavimo ypatybes.
, paimtas atitinkamai kartais
; bendras mėginių skaičius
(- mėginių ėmimo intervalas).

Tokių diskrečių signalų tyrimo metodas yra toks, kad gautas atskaitos verčių pavyzdys mintyse kartojamas begalinį skaičių kartų. Dėl to signalas tampa periodiškas.

Susiejus tam tikrą matematinį modelį su tokiu signalu, galite naudoti Furjė serijos išplėtimą ir rasti atitinkamus amplitudės koeficientus. Šių koeficientų derinys sudaro diskretiško periodinio signalo spektrą.

Naudokime modelį delta impulsų sekos forma. Tada pradinė vibracija bus išreikšta formule:

(5.1)

Kur
– analoginio signalo imties reikšmės.

- diskretinė Furjė transformacija (DFT) (5.4)

Pagrindinės DFT savybės

1. DFT – tiesinė transformacija t.y. signalų suma atitinka jų DFT sumą

2. Skirtingų koeficientų skaičius
, apskaičiuotas pagal (5.4) formulę, yra lygus skaičiui N per laikotarpį; pagal koeficientą

3. Koeficientas (pastovus komponentas) yra vidutinė visų rodmenų vertė:

5. Tegul pamatinės vertės – realūs skaičiai. Tada DFT koeficientai, kurių skaičiai yra simetriškai /2 atžvilgiu, sudaro konjuguotas poras:

Diskrečiosios spektrinės analizės problemą galima suformuluoti ir kitaip. Tarkime, kad koeficientai , sudarantys DFT, pateikiami. Įdėkime į formulę (5.2)
ir atsižvelgti į tai, kad sumuojamas tik baigtinis skaičius serijos narių, atitinkančių harmonikas, esančias pradinio signalo spektre.

Taigi gauname pamatinių verčių apskaičiavimo formulę

(5.5)

Akivaizdu, kad (5.5) yra atvirkštinė diskrečioji Furjė transformacijos (IDFT) formulė.

11 Greitosios Furjė transformacijos algoritmas. Skaičiavimo operacijų skaičius. Diskrečiųjų ir greitųjų Furjė transformacijų palyginimas.

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

Atsižvelkime į tai, kad koeficientų sekos, susijusios su lyginėmis ir nelyginėmis įvesties masyvo dalimis, yra periodinės su N/2 periodu:

Be to, koeficientas, įtrauktas į formulę (5.7) at
galima konvertuoti taip:

Iš čia randame DFT koeficientų rinkinio antrosios pusės išraišką

(5.8)

Formulės (5.7) ir (5.8) sudaro FFT algoritmo pagrindą. Tolesni skaičiavimai atliekami iteraciniu principu: imčių su lyginiais ir nelyginiais skaičiais sekos vėl suskirstomos į dvi dalis. Procesas tęsiamas tol, kol gaunama seka, susidedanti iš vieno elemento. Šio elemento DFT sutampa su pačiu savimi.

Operacijų, reikalingų FFT apskaičiuoti, skaičius įvertintas kaip
.

Skaičiavimo greičio padidėjimas, palyginti su tradiciniu DFT, siekia šimtus ir net tūkstančius, jei įvesties masyvai yra pakankamai ilgi.

12.. Z - transformacija ir jos savybės. Taikymas Z - transformacijos.

Analizuojant ir sintezuojant diskrečius ir skaitmeninius įrenginius, Z transformacija atlieka tą patį vaidmenį kaip Furjė integralinės transformacijos nenutrūkstamų signalų atžvilgiu.

Leiskite
– skaitinė seka, baigtinė arba begalinė, turinti tam tikro signalo atskaitos reikšmes. Sudėkime jį į unikalų atitikmenį su serijos suma neigiamų galių sudėtingas kintamasis Z:

(5.9)

Ši suma vadinama sekos Z transformacija
. Diskrečių skaičių sekų savybes galima tirti tiriant jų Z transformacijas taikant įprastinius matematinės analizės metodus.

Ši išraiška prasminga, kai |Z|> .

Atvirkštinė Z transformacija

Tegul x(z) yra kompleksinio kintamojo Z funkcija. Nepaprasta Z transformacijos savybė yra ta, kad funkcija x(z) apibrėžia visą begalinę imčių rinkinį (
).

Iš tiesų, padauginkime abi eilutės puses (5.9) iš koeficiento
:

Visų terminų integralai dešinėje pusėje išnyks, išskyrus terminą su skaičiumi m, todėl:

(5.11)

Ši išraiška vadinama atvirkštine Z transformacija.

Svarbiausios savybės Z – konversijos:

1. Tiesiškumas. Jeigu
Ir
- žinomi kai kurie diskretieji signalai ir atitinkamos Z transformacijos x(z) ir y(z), tada signalas
atitiks bet kurios konstantos transformaciją Ir . Įrodymas atliekamas sumą pakeičiant į (5.9) formulę.

2. Z-paslinkusio signalo konvertavimas. Pasvarstykime diskretiškas signalas
, atsirandantis dėl atskiro signalo
perkeliant viena pozicija link delsos, t.y. Kada
. Tiesiogiai apskaičiuodami Z transformaciją, gauname tokį rezultatą:

Taigi simbolis
veikia kaip vieneto delsos operatorius (vienam atrankos intervalui) Z domene.

3. Z-konvoliucijos transformacija. Tegul x(z) ir y(z) yra nuolatiniai signalai, kurių konvoliucija yra apibrėžta:

(5.13)

Kalbant apie atskirus signalus, pagal analogiją su (5.13) įprasta įvesti diskretiška konvoliucija
– skaičių seka, kurios bendras terminas yra:

Tokia diskreti konvoliucija vadinama tiesine

Apskaičiuokime diskrečiosios konvoliucijos Z transformaciją:

(5.15)

Taigi dviejų diskrečiųjų signalų konvoliucija atitinka Z transformacijų sandaugą.

Linijinis filtravimas vaizdai gali būti atliekami tiek erdviniuose, tiek dažnio sritis. Manoma, kad „žemi“ erdviniai dažniai atitinka pagrindinį vaizdo turinį – foną ir didelio dydžio objektus, o „aukšti“ erdviniai dažniai – mažo dydžio objektus, smulkias didelių formų detales ir triukšmo komponentą.

Tradiciškai, norint pereiti į erdvinių dažnių sritį, naudojami metodai, pagrįsti $\textit(Fourier transform)$. IN pastaraisiais metais Visi didesnis pritaikymas Taip pat randami metodai, pagrįsti $\textit(wavelet-transform)$.

Furjė transformacija.

Furjė transformacija leidžia pavaizduoti beveik bet kurią funkciją ar duomenų rinkinį kaip jų derinį trigonometrinės funkcijos, kaip sinusas ir kosinusas, leidžiantis identifikuoti periodinius duomenų komponentus ir įvertinti jų indėlį į pradinių duomenų struktūrą ar funkcijos formą. Tradiciškai yra trys pagrindinės Furjė transformacijos formos: integrali Furjė transformacija, Furjė serija ir diskretinė Furjė transformacija.

Furjė integralas transformuoja realią funkciją į realių funkcijų porą arba vieną sudėtingą funkciją į kitą.

Tikroji funkcija $f(x)$ gali būti išplėsta stačiakampėje trigonometrinių funkcijų sistemoje, ty pavaizduota forma

$$ 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 , $$

kur $A(\omega)$ ir $B(\omega)$ vadinamos integraliomis kosinuso ir sinuso transformacijomis:

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

Furjė serija reiškia periodinę funkciją $f(x)$, apibrėžtą intervale $$, kaip begalinę sinusų ir kosinusų eilutę. Tai reiškia, kad periodinė funkcija $f(x)$ yra susieta su begaline Furjė koeficientų seka

$$ 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 . $$

Diskreti Furjė transformacija paverčia baigtinę seką realūs skaičiaiį baigtinę Furjė koeficientų seką.

Tegul $\left\( (x_i ) \right\), i= 0,\ldots, N-1 $ – realiųjų skaičių seka – pavyzdžiui, pikselių šviesumas skaičiuojamas išilgai vaizdo linijos. Šią seką galima pavaizduoti kaip derinį galutinės sumos malonus

$$ 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

Pagrindinis skirtumas tarp trijų Furjė transformacijos formų yra tas, kad jei integrali Furjė transformacija yra apibrėžta visoje funkcijos $f(x)$ apibrėžimo srityje, tai serija ir diskrečioji Furjė transformacija apibrėžiami tik diskrečioje aibėje. taškų, begalinis Furjė serijai ir baigtinis diskrečiųjų vienetų transformacijoms.

Kaip matyti iš Furjė transformacijos apibrėžimų, diskrečioji Furjė transformacija labiausiai domina skaitmeninių signalų apdorojimo sistemas. Duomenys, gauti iš skaitmeninių laikmenų ar informacijos šaltinių, yra sutvarkyti skaičių rinkiniai, parašyti vektorių arba matricų pavidalu.

Paprastai daroma prielaida, kad diskrečios transformacijos įvesties duomenys yra vienodas pavyzdys su $\Delta $ žingsniu, o reikšmė $T=N\Delta $ vadinama įrašo ilgiu arba pagrindiniu periodu. Pagrindinis dažnis yra $1/T$. Taigi, diskrečioji Furjė transformacija išskaido įvesties duomenis į dažnius, kurie yra sveikieji pagrindinio dažnio kartotiniai. Didžiausias dažnis, nustatytas pagal įvesties duomenų matmenį, yra lygus $1/2 \Delta $ ir vadinamas $\it(Nyquist dažnis)$. Naudojant diskrečiąją transformaciją, svarbu atsižvelgti į Nyquist dažnį. Jei įvesties duomenys turi periodinius komponentus, kurių dažniai yra aukštesni už Nyquist dažnį, tada diskretinė Furjė transformacija pakeis aukšto dažnio duomenis žemesniu dažniu, o tai gali sukelti klaidų interpretuojant diskrečiosios transformacijos rezultatus.

$\it(energy spectrum)$ taip pat yra svarbi duomenų analizės priemonė. Signalo galia dažniu $\omega $ nustatoma taip:

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

Šis dydis dažnai vadinamas $\it(signalo energija)$ dažniu $\omega $. Pagal Parsevalio teoremą, bendra įvesties signalo energija yra lygi visų dažnių energijų sumai.

$$ E=\sum\limits_(i=0)^(N-1) (x_i^2 ) =\sum\limits_(i=0)^(N/2) (P \left((\omega _i ) \dešinėje)). $$

Galios ir dažnio grafikas vadinamas energijos spektru arba galios spektru. Energijos spektras leidžia identifikuoti paslėptus įvesties duomenų periodiškumus ir įvertinti tam tikrų dažnių komponentų indėlį į įvesties duomenų struktūrą.

Sudėtingas Furjė transformacijos vaizdavimas.

Be trigonometrinės diskrečios Furjė transformacijos rašymo formos, plačiai naudojamas $\it(kompleksinis vaizdavimas)$. Sudėtinga Furjė transformacijos įrašymo forma plačiai naudojama daugiamatėje analizėje ir ypač vaizdo apdorojime.

Perėjimas nuo trigonometrinės prie sudėtingos formos atliekamas pagal Eilerio formulę

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

Jei įvesties seka yra $N$ kompleksiniai skaičiai, tada jos diskrečioji Furjė transformacija bus tokios formos

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

ir atvirkštinė transformacija

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

Jei įvesties seka yra realiųjų skaičių masyvas, tada jai yra ir kompleksinė, ir diskretinė sinuso-kosinuso transformacija. Ryšys tarp šių idėjų išreiškiamas taip:

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

Likusios $N/2$ transformacijos vertės yra sudėtingi konjugatai ir neturi papildomos informacijos. Todėl diskrečiosios Furjė transformacijos galios spektro grafikas yra simetriškas $N/2$ atžvilgiu.

Greitoji Furjė transformacija.

Paprasčiausias būdas apskaičiuoti diskrečiąją Furjė transformaciją (DFT) yra tiesioginis sumavimas, dėl kurio kiekvienam koeficientui atliekamos $N$ operacijos. Bendri koeficientai yra $N$, taigi bendras sudėtingumas yra $O\left((N^2)\right)$. Šis metodas nėra praktiškai įdomus, nes yra daug efektyvesnių būdų apskaičiuoti DFT, vadinamą greitąja Furjė transformacija (FFT), kurios sudėtingumas yra $O (N\log N)$. FFT taikoma tik sekoms, kurių ilgis (elementų skaičius) yra 2 laipsnis. Bendriausias FFT algoritmo principas yra padalinti įvesties seką į dvi pusės ilgio sekas. Pirmoji seka užpildoma poriniais duomenimis, o antroji – neporiniais. Tai leidžia apskaičiuoti DFT koeficientus dviem $N/2$ matmenų transformacijomis.

Pažymime $\omega _m =e^(\frac(2\pi j)(m))$, tada $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 $.

Už mln< 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$. Полный алгоритм БПФ заключается в рекурсивном выполнении вышеописанной процедуры, начиная с объединения одиночных элементов в пары, затем в четверки и так до полного охвата исходного массива данных.

Dvimatė Furjė transformacija.

Diskreti Furjė transformacija, skirta dvimačiai skaičių masyvei, kurių dydis $M\times N$, apibrėžiamas taip:

$$ 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]) ), $$

ir atvirkštinė transformacija

$$ 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]) ). $$

Vaizdo apdorojimo atveju dvimatės Furjė transformacijos komponentai vadinami $\textit(spatial frequencies)$.

Svarbi dvimatės Furjė transformacijos savybė yra galimybė ją apskaičiuoti naudojant vienmatę FFT procedūrą:

$$ 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) ), $$

Čia išraiška laužtiniuose skliaustuose yra vienmatė duomenų matricos eilutės transformacija, kurią galima atlikti naudojant vienmatę FFT. Taigi, norint gauti dvimatę Furjė transformaciją, pirmiausia reikia apskaičiuoti vienmates eilučių transformacijas, surašyti rezultatus į pradinę matricą ir apskaičiuoti gautos matricos stulpelių vienmates transformacijas. Skaičiuojant dvimatę Furjė transformaciją matricos kampuose bus sutelkti žemi dažniai, o tai nėra labai patogu tolesniam gautos informacijos apdorojimui. Norint išversti ir gauti 2D Furjė transformacijos vaizdą, kuriame žemi dažniai sutelkti matricos centre, paprasta procedūra, kurią galima atlikti, yra padauginti pradinius duomenis iš $-1^(m+n)$.

Fig. 16 paveiksle parodytas originalus vaizdas ir jo Furjė transformacija.

Pustonių vaizdas ir jo Furjė transformacija (vaizdai gauti LabVIEW sistemoje)

Konvoliucija naudojant Furjė transformaciją.

Funkcijų $s(t)$ ir $r(t)$ konvoliucija apibrėžiama kaip

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

Praktiškai turime susidoroti su diskrečiąja konvoliucija, kai tolydžios funkcijos pakeičiamos verčių rinkiniais vienodo tinklelio mazguose (dažniausiai imamas sveikųjų skaičių tinklelis):

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

Čia $-N$ ir $P$ apibrėžia diapazoną, už kurio $r(t) = 0$.

Skaičiuojant konvoliuciją naudojant Furjė transformaciją, naudojama Furjė transformacijos savybė, pagal kurią funkcijų vaizdų sandauga dažnių srityje yra lygiavertė šių funkcijų konvoliucijai laiko srityje.

Norint apskaičiuoti suderinimą, reikia transformuoti pradinius duomenis į dažnių sritį, tai yra apskaičiuoti jos Furjė transformaciją, padauginti transformacijos rezultatus ir atlikti atvirkštinę Furjė transformaciją, atkuriant pirminį vaizdą.

Vienintelis algoritmo veikimo subtilumas yra susijęs su tuo, kad diskrečios Furjė transformacijos atveju (priešingai nei tolydžios) sujungiamos dvi periodinės funkcijos, tai yra, mūsų reikšmių rinkiniai tiksliai nurodo šių funkcijų periodus, o ne tik reikšmes tam tikroje atskiroje ašies dalyje. Tai yra, algoritmas mano, kad po taško $x_(N )$ seka ne nulis, o taškas $x_(0)$ ir taip toliau apskritime. Todėl, norint teisingai apskaičiuoti konvoliuciją, signalui reikia priskirti pakankamai ilgą nulių seką.

Vaizdų filtravimas dažnio srityje.

Tiesinio filtravimo metodai yra vieni iš gerai struktūrizuotų metodų, kuriems buvo sukurtos efektyvios skaičiavimo schemos, pagrįstos greitos konvoliucijos algoritmais ir spektrine analize. Paprastai linijiniai filtravimo algoritmai atlieka formos transformaciją

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

kur $K(\zeta ,\eta)$ yra tiesinės transformacijos branduolys.

Atskirai atvaizduojant signalą, integralas šioje formulėje išsigimsta į svertinę pradinio vaizdo pavyzdžių sumą tam tikroje diafragmoje. Šiuo atveju branduolio $K(\zeta ,\eta)$ parinkimas pagal vieną ar kitą optimalumo kriterijų gali lemti daugybę naudingų savybių (Gauso išlyginimas sureguliuojant vaizdo skaitinės diferenciacijos problemą ir pan.) .

Tiesinio apdorojimo metodai efektyviausiai įgyvendinami dažnių srityje.

Vaizdo Furjė transformacijos naudojimas filtravimo operacijoms atlikti visų pirma yra dėl didesnio tokių operacijų našumo. Paprastai tiesioginės ir atvirkštinės 2D Furjė transformacijos ir padauginimas iš filtro Furjė vaizdo koeficientų užtrunka mažiau laiko nei atliekant 2D konvoliuciją pradiniame vaizde.

Dažnio srities filtravimo algoritmai yra pagrįsti konvoliucijos teorema. 2D atveju konvoliucijos transformacija atrodo taip:

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

kur $G$ yra konvoliucijos rezultato Furjė transformacija, $H$ yra filtro Furjė transformacija, o $F$ yra pradinio vaizdo Furjė transformacija. Tai yra, dažnio srityje dvimatė konvoliucija pakeičiama pradinio vaizdo ir atitinkamo filtro vaizdų padauginimu iš elementų.

Norėdami atlikti konvoliuciją, turite atlikti šiuos veiksmus:

1. Padauginkite pradinio vaizdo elementus iš $-1^(m+n)$, kad Furjė vaizdas būtų centre.
2. Apskaičiuokite $F(u,v)$ Furjė vaizdą naudodami FFT.
3. Furjė vaizdą $F(u,v)$ padauginkite iš dažnio filtro funkcijos $H(u,v)$.
4. Apskaičiuokite atvirkštinę Furjė transformaciją.
5. Padauginkite realiąją atvirkštinės transformacijos dalį iš $-1^(m+n)$.

Ryšys tarp filtro funkcijos dažnio srityje ir erdvinės srities gali būti nustatytas naudojant konvoliucijos teoremą

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

$$ \Phi \left[ (f\left((x,y) \right)h(x,y)) \right]=F\left((u,v) \right)\ast H\left(( u,v)\dešinė). $$

Funkcijos su impulsine funkcija konvoliuciją galima pavaizduoti taip:

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

Impulsinės funkcijos Furjė transformacija

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

Tegul $f(x,y) = \delta (x,y)$, tada konvoliucija

$$ 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). $$

Iš šių išraiškų aišku, kad filtro funkcijos dažnio ir erdvinėse srityse yra tarpusavyje susijusios per Furjė transformaciją. Tam tikrai filtro funkcijai dažnių srityje visada galima rasti atitinkamą filtrą erdvinėje srityje, taikant atvirkštinę Furjė transformaciją. Tas pats pasakytina ir apie atvirkštinį atvejį. Naudojant šį ryšį, galima apibrėžti erdvinių tiesinių filtrų sintezės procedūrą.

1. Nustatome reikiamas filtro charakteristikas (formą) dažnių srityje.
2. Atliekame atvirkštinę Furjė transformaciją.
3. Gautas filtras gali būti naudojamas kaip kaukė erdvinei konvoliucijai, o kaukės dydis gali būti sumažintas, palyginti su pradinio filtro dydžiu.

($\textit(idealus žemųjų dažnių filtras)$) $H(u,v)$ yra $$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(Idealus aukšto dažnio filtras)$) gaunamas apverčiant idealų žemųjų dažnių filtrą:

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

Čia žemo dažnio komponentai yra visiškai slopinami, o aukšto dažnio komponentai išsaugomi. Tačiau, kaip ir idealaus žemųjų dažnių filtro atveju, jo naudojimas yra kupinas didelių iškraipymų.

Norint susintetinti filtrus su minimaliais iškraipymais, naudojami įvairūs metodai. Viena iš jų – eksponentinė filtrų sintezė. Tokie filtrai sukuria minimalų vaizdo iškraipymą ir yra patogūs sintezei dažnių srityje.

Vaizdo apdorojimui plačiai naudojama filtrų šeima, pagrįsta tikra Gauso funkcija.

$\textit(žemo dažnio Gauso filtras)$ turi formą

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

Kuo siauresnis filtro profilis dažnio srityje (kuo didesnis $\sigma $), tuo jis platesnis erdviniame domene.

($\textit(aukštojo dažnio Gauso filtras)$) turi formą

$$ h\left(x \right)=\sqrt (2\pi ) \sigma _A Ae^(-2\left((\pi \sigma _A x) \right)^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 )). $$

Dviejų dimensijų atveju ($\it(low-pass)$) Gauso filtras atrodo taip:

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

($\it(High Pass)$) Gauso filtras turi tokią formą

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

Panagrinėkime vaizdo filtravimo pavyzdį (1 pav.) dažnių srityje (17 - 22 pav.). Atminkite, kad vaizdo dažnio filtravimas gali turėti ir išlyginimo ($\textit(low-pass filtering)$), ir kontūrų bei mažo dydžio objektų paryškinimo ($\textit(high-pass filtering)$) reikšmę.

Kaip matyti iš fig. 17, 19, didėjant filtravimo „galiai“ žemo dažnio vaizdo komponente, vaizdo „akivaizdus defokusavimas“ arba $\it(blur)$ tampa vis ryškesnis. Tuo pačiu metu didžioji vaizdo informacijos turinio dalis palaipsniui pereina į aukšto dažnio komponentą, kur pradžioje stebimi tik objektų kontūrai (18, 20 - 22 pav.).

Dabar panagrinėkime aukštųjų ir žemųjų dažnių filtrų elgseną (23 - 28 pav.), kai vaizde yra papildomas Gauso triukšmas (7 pav.).

Kaip matyti iš fig. 23, 25, žemo dažnio filtrų, skirtų papildomam atsitiktiniam triukšmui slopinti, savybės yra panašios į anksčiau svarstytų linijinių filtrų savybes - esant pakankamai filtro galiai, triukšmas slopinamas, tačiau kaina už tai yra stiprus kontūrų susiliejimas ir „defokusavimas“. “ viso vaizdo. Triukšmingo vaizdo aukšto dažnio komponentas nustoja būti informatyvus, nes, be kontūro ir objekto informacijos, dabar pilnai yra ir triukšmo komponentas (27, 28 pav.).

Dažnio metodų naudojimas yra tinkamiausias tuo atveju, kai yra žinomas statistinis triukšmo proceso modelis ir (arba) vaizdo perdavimo kanalo optinio perdavimo funkcija. Patogu atsižvelgti į tokius a priori duomenis, kaip rekonstrukcijos filtrą pasirenkant apibendrintą valdomą filtrą (pagal parametrus $\sigma$ ir $\mu$):

$$ 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]. $$

kur 0 USD< \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)$. Этот алгоритм эффективно фильтрует засоренные однородные поверхности (области) фона. Однако при попадании в скользящее окно обработки неоднородных участков фона импульсная характеристика фильтра сужается ввиду резкого изменения локальных статистик, и эти неоднородности (контуры, пятна) передаются практически без расфокусировки, свойственной неадаптивным методам линейной фильтрации.

Linijinio filtravimo metodų pranašumai yra jų aiški fizinė prasmė ir rezultatų analizės paprastumas. Tačiau smarkiai pablogėjus signalo ir triukšmo santykiui, esant galimiems ploto triukšmo variantams ir esant didelės amplitudės impulsų triukšmui, linijinio išankstinio apdorojimo metodų gali nepakakti. Šioje situacijoje netiesiniai metodai yra daug galingesni.

Įvadas

Laboratorinės pamokos metu buvo tiriamos diskrečios trigonometrinės transformacijos (DTP) galimybės šiais požiūriais:

1. Patikrinome nurodytos avarijos grįžtamumo savybę.

2. Ištirtas siūlomos avarijos tiesiškumas.

3. Ištyrėme išbandytos avarijos pasikartojimo spektro ypatybes.

4. Nustatėme simetriško spektro atspindžio buvimą avarijos metu, ty

4.1. centrinės simetrijos buvimas,

4.2. ašinės (vertikalios) simetrijos buvimas.

5. Išnagrinėjome signalo fazių poslinkių įtaką susidariusiai avarijai.

6. Patikrintas nurodytos transformacijos panašumo savybės buvimas.

7. Ištyrėme signalų filtravimo galimybę naudojant tam tikrą avariją.

8. Eksperimentiškai išbandėme energijos taupymą tiriamame eismo įvykyje.

9. Mes atradome ryšį tarp šios avarijos ir diskrečiosios Furjė transformacijos.

Reprezentatyvesnei analizei taip pat buvo atsižvelgta į įvairius įvesties signalus.

Garsiausia tarp diskrečiųjų funkcinių transformacijų yra diskretinė Furjė transformacija (DFT).

Diskretinė Furjė transformacija

Diskretioji Furjė transformacija nustato diskretuotos periodinės laiko funkcijos linijų spektrą. Atvirkštinė diskreti Furjė transformacija leidžia atkurti laiko funkciją pagal jos spektrą. Šios transformacijos paprastai vadinamos atitinkamai DFT ir ODFT.

DFT naudojamas periodinėms funkcijoms analizuoti ir gali būti gautas iš Furjė eilučių teorijos. Tegu x0(t) yra nuolatinė periodinė funkcija, kurios periodas P ir dažnis f0 = 1/P, kad

Funkciją x0(t) galima išplėsti į Furjė eilutę:

kur plėtimosi koeficientai X0(n) pateikti pagal formulę

Paprastai x0(t) yra reali funkcija, o tada X0(n) yra sudėtinga (tačiau šis apribojimas nėra būtinas). Kadangi x0 laikome laiko funkcija, X0(n) gali būti vadinamas kompleksiniu x0(t) spektru. Naudojant realiąją ir įsivaizduojamą X0(n) dalis, galima rasti komponentų, sudarančių virpesį x0(t), amplitudę ir fazę.

Panagrinėkime periodinės funkcijos x0(t) diskretizaciją. Kad ši funkcija būtų vienareikšmiškai diskretizuota, jos spektre neturėtų būti komponentų, kurių dažnis didesnis už tam tikrą dažnį f1, t.y.

kur n1 yra sveikasis skaičius n, nurodantis dažnį f1.

Fig. 1 parodytas toks ribotas spektras ir vibracija, kurią jis atitinka.

atrankos intervalas T lygus

taigi mėginių skaičius per laikotarpį bus toks

Fig. 1. Periodinė funkcija x0(t) su ribota dažnių juosta ir jos spektras X0(n).

1Dėl diskretizacijos gauname periodinį svyravimą, normalizuojamą formos T atžvilgiu

Šis svyravimas apibrėžiamas per intervalą, lygų jo periodui, t.y.

Kadangi x(t/T) yra periodinė funkcija, Furjė eilutės koeficientams apskaičiuoti naudojamas santykis (2).

(P pakeitimas /V daliklyje ir integravimo ribos atitinka perėjimą prie normalizuoto kintamojo.) Pakeitę išraišką (3), gauname

Yra žinoma, kad

Galiausiai, atsižvelgiant į tai, kad pagal apibrėžimą

Ryšį, jungiantį x(k) su X(n), galima gauti tiesiogiai iš (1) formulės, jei pakeisime t=kT ir atsižvelgsime į tai, kad esant ribotam funkcijos x0(t) spektrui, suma yra ribotas skaičius terminų. Taigi,

Pažymėtina, kad x(k) yra periodinė funkcija, t.y.

ir panašiai

Tai, kad spektras yra periodinis, paaiškinama bet kurios diskretuotos funkcijos spektro periodiškumu, o jo diskretiškumą lemia tai, kad pati diskretizuota funkcija taip pat yra periodinė.

Taigi, diskretuojant periodinę funkciją x0(t), santykis (4) leidžia naudojant imtį x0(t) rasti spektrą X(n), kuris intervale 0 ≤ n ≤ N - 1 yra tiksliai lygus spektrui X0 n) pradinės periodinės funkcijos. Funkcija x(k) ir jos spektras grafiškai pateikti pav. 2. Kadangi santykis (5.4) gaunamas remiantis atrankos teorema, jis yra tikslus ir ekonomiškas (skaičiuojant) pirminio integralinio ryšio (2) atitikmuo ir gali būti naudojamas skaičiuojant plėtimosi koeficientus kompiuteryje. Santykius (4) ir (5) vadinsime atitinkamai diskrečiąja Furjė transformacija (DFT) ir atvirkštine diskrečiąja Furjė transformacija (IDFT). Atkreipkite dėmesį, kad kintamasis n čia skiriasi nuo nulio iki N-1. Gautas spektras gali būti interpretuojamas taip. Pirmieji (N/2-1) taškai X(n) atitinka (N/2 - 1) spektrines linijas X0(n) esant teigiamam dažniui, kaip parodyta pav. 5.3, o paskutiniai (N/2-1) taškai X(n) atitinka (N/2-1) spektro linijas esant neigiamiems dažniams.

Santykių (4) ir (5) duota transformacijų pora pasitaiko ir kita forma. Pavyzdžiui, daugiklis 1 / N ir eksponento minuso ženklas gali būti parašyti tiek tiesiogine, tiek atvirkštine transformacija, bendroji reikšmė nesikeičia.

Natūralu, kad spektras šiuo atveju negali būti tiesiogiai tapatinamas su apibrėžtu (2) formule. Kartais abi transformacijos pateikiamos tais pačiais koeficientais (1 / N)1/2.

Fig. 2. Diskretizuota periodinė funkcija x(k) ir jos periodinis spektras X(n).

Fig. 3. Furjė eilutės ir DFT koeficientų ryšys.

DFT savybės

Kai kurios DFT savybės vaidina svarbų vaidmenį sprendžiant praktinius signalų apdorojimo klausimus.

Tiesiškumas

Jei xp(n) ir ur(n) yra periodinės sekos (kiekviena turi N imčių periodą), o Xp(k) ir Yp(k) yra jų DFT, tai sekos xp(n) + diskrečioji Furjė transformacija. + ur(n ) yra lygus Хр(k) + Yp(k). Tai pasakytina ir apie baigtinio ilgio sekas.

Shift

Jei seka xp(n) yra periodinė su N imčių periodu, o jos DFT lygi Xp(k), tai xp(n-n0) formos periodinės sekos DFT bus lygi.

Fig. 4. Pasislinkusios sekos DFT apibrėžimo link.

Analizuojant baigtinio ilgio sekas, būtina atsižvelgti į specifinį sekos laiko poslinkio pobūdį. Taigi, Fig. 4, a rodo baigtinę seką x(n), kurios ilgis yra N imčių. Ten kryžiai taip pat rodo lygiavertės periodinės sekos xp(n), kurios DFT yra toks pat kaip x(n), pavyzdžius. Norėdami rasti pasislinkusios sekos DFT x(n - n0), ir n0< N, следует рассмотреть сдвинутую периодическую последовательность Хр(n - n0) и в качестве эквивалентной сдвинутой конечной последовательности (имеющей ДПФ j принять отрезок последовательности хр(n - n0) в интервале 0 ≤ n ≤ N - 1. Таким образом, с точки зрения ДПФ последовательность х(n – n0) получается путем кругового сдвига элементов последовательности х(n) на n0 отсчетов

Simetrijos savybės

Jei periodinė seka xp(n) su v/V imčių periodu yra reali, tai jos DFT xp(k) tenkina šias simetrijos sąlygas:

Panašios lygybės galioja ir baigtinei realiajai sekai x(n), turinčiai N taško DFT X(k). Jei sekai xp(n) įvesime papildomą simetrijos sąlygą, t.y., tarkime

tada paaiškėja, kad Xp(k) gali būti tik tikras.

Kadangi dažniausiai tenka susidurti su realiomis sekomis, skaičiuojant vieną DFT, galime gauti dviejų sekų DFT naudojant simetrijos savybes (6). Panagrinėkime realias periodines sekas xp(n) ir yp(n) su atitinkamai N imčių ir N taškų DFT xp(k) ir Yp(k) periodais. Įveskime sudėtingą formos seką zp(n).

Jo DFT yra lygus

Išskirdami tikrąją ir įsivaizduojamą lygybės (10) dalis, gauname

Tikrosios dalys Xp(k) ir Yp(k) yra simetriškos, o įsivaizduojamos dalys yra antisimetriškos, todėl jas galima lengvai atskirti naudojant sudėjimo ir atimties operacijas:

Taigi, apskaičiavus vieną N taško DFT, galima vienu metu transformuoti dvi realias N ilgio imčių sekas. Jei šios sekos taip pat yra simetriškos, operacijų, reikalingų jų DFT gauti, skaičius gali būti dar labiau sumažintas.

Susijusi informacija.

Tradicinė „pradžios lygio“ dabartinio vaizdo palyginimo su standartu technika pagrįsta vaizdų žiūrėjimu kaip dvimatėmis ryškumo funkcijomis (diskrečiomis dvimačio intensyvumo matricomis). Šiuo atveju matuojamas atstumas tarp vaizdų arba jų artumo matas.

Paprastai atstumams tarp vaizdų apskaičiuoti naudojama formulė, kuri yra intensyvumo skirtumų modulių arba kvadratų suma:

d(X,Y) = SUMMA (X – Y)^2

Vienas iš metodų, galinčių žymiai sumažinti skaičiavimų skaičių, yra Furjė transformacijų ir diskrečiųjų Furjė transformacijų naudojimas apskaičiuojant dviejų vaizdų sutapimo matą skirtingais poslinkiais tarp jų. Šiuo atveju skaičiavimai atliekami vienu metu įvairiems vaizdo poslinkių deriniams vienas kito atžvilgiu.

Kadangi yra daug bibliotekų, kurios įgyvendina Furjė transformacijas (visose greitosiose versijose), vaizdų palyginimo algoritmų įgyvendinimas nėra labai sudėtingas programavimo uždavinys.

Problemos pareiškimas

• Tegu pateikiami du vaizdai X ir Y – vaizdas ir pavyzdys, atitinkamai (N1,N2) ir (M1,M2) dydžiai ir Ni > Mi

paveikslėlyje

Koreliacija kaip matas tarp vaizdų

dvi funkcijos F ir G vadinamos dydžiu:

Šis dydis yra gerai žinomas iš matematikos ir geometrijos kurso tiesinės erdvės, kur jis vadinamas skaliariniu sandauga. Formulę naudosime kaip matą tarp vaizdų:

m(X,Y) = SUMMA (X * Y) / (SQRT (SUM X ^2) * SQRT (SUM Y ^2))

arba

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

Šis dydis gaunamas veikiant vektorių skaliarinei sandaugai (atvaizdus laikant vektoriais daugiamatėje erdvėje). Ir dar daugiau – ta pati formulė yra standartas statistinė formulė dviejų tikimybių skirstinių sutapimo hipotezės kriterijus.

Pastaba:
Skaičiuodami koreliaciją tarp vaizdo fragmentų, jei vienas vaizdas mažesnis už kitą, dalinsime tik iš susikertančių dalių normų reikšmės.

Dviejų funkcijų konvoliucija

Pagal apibrėžimą dviejų funkcijų F ir G konvoliucija vadinama funkcija FxG:

Tegu G’(t) = G(-t) ir F’(t) = F(-t), tada lygybių galiojimas yra akivaizdus:

• FхF’(0) = SUM F(i)^2 – taškinis produktas vektorius F į save
• GxG’(0) = SUM G(j)^2 – vektoriaus G ir jo paties skaliarinė sandauga
• FхG’(0) = SUM F(i)*G(i) – dviejų vektorių F ir G skaliarinė sandauga

Taip pat akivaizdu, kad FxG’(t) yra lygi koreliacijai, gautai vieną vektorių perslinkus kito atžvilgiu žingsniu t (tai galima lengvai patikrinti, aiškiai pakeičiant reikšmes į koreliacijos formulę).

Furjė transformacija (ℱ) yra operacija, kuri susieja vieną tikrojo kintamojo funkciją su kita funkcija, taip pat realiuoju kintamuoju. Tai nauja funkcija aprašo koeficientus („amplitudes“), kai pradinė funkcija skaidoma į elementarius komponentus - harmonines vibracijas su skirtingais dažniais.

Realiojo kintamojo funkcijos f Furjė transformacija yra integrali ir pateikiama pagal šią formulę:

Skirtingi šaltiniai gali pateikti apibrėžimus, kurie skiriasi nuo pirmiau pateiktų, pasirenkant koeficientą prieš integralą, taip pat „-“ ženklą eksponente. Tačiau visos savybės bus tos pačios, nors kai kurių formulių išvaizda gali pasikeisti.

Be to, yra įvairių šios sąvokos apibendrinimų.

Daugiamatė Furjė transformacija

Funkcijų Furjė transformacija, apibrėžta erdvėje ℝ^n, nustatoma pagal formulę:

Atvirkštinė transformacija šiuo atveju pateikiama pagal formulę:

Kaip ir anksčiau, į skirtingų šaltinių daugiamatės Furjė transformacijos apibrėžimai gali skirtis pasirenkant konstantą prieš integralą.

Diskretinė Furjė transformacija

Diskretinė Furjė transformacija (anglų literatūroje DFT, Discrete Fourier Transform) yra viena iš Furjė transformacijų, plačiai naudojamų skaitmeninių signalų apdorojimo algoritmuose (jo modifikacijos naudojamos garso suspaudimui MP3 formatu, vaizdo glaudinimui JPEG formatu ir kt.), taip pat kitos sritys, susijusios su dažnių analize diskretiniame (pavyzdžiui, skaitmeniniame analoginiame) signale. Atskirai Furjė transformacijai reikalinga įvestis diskreti funkcija. Tokios funkcijos dažnai sukuriamos atrankos būdu (verčių atranka iš nuolatinės funkcijos). Diskrečiosios Furjė transformacijos padeda išspręsti diferencialines lygtis dalinėse išvestinėse ir atlikti tokias operacijas kaip konvoliucija. Diskrečiosios Furjė transformacijos taip pat aktyviai naudojamos statistikoje, analizuojant laiko eilutes. Yra daugiamačių diskrečių Furjė transformacijų.

Diskrečiosios transformacijos formulės

Tiesioginis konvertavimas:

Atvirkštinis konvertavimas:

Diskrečioji Furjė transformacija yra tiesinė transformacija, kuri paverčia laiko imčių vektorių į tokio pat ilgio spektrinių imčių vektorių. Taigi transformaciją galima įgyvendinti kaip simetrišką daugybą kvadratinė matricaį vektorių:

Furjė transformacijos konvoliucijai apskaičiuoti

Vienas iš nepaprastų savybių Furjė transformacijos – tai galimybė greitai apskaičiuoti dviejų apibrėžtų funkcijų koreliaciją naudojant tikrąjį argumentą (kai klasikinė formulė), arba ant baigtinio žiedo (kai naudojamos diskrečios transformacijos).

Ir nors panašių savybių būdingas daugeliui tiesinės transformacijos, praktiniam naudojimui, konvoliucijos operacijai apskaičiuoti, pagal mūsų apibrėžimą, naudojama formulė

Kur

• FFT – operacija tiesioginis konvertavimas Furjė
• BFT – atvirkštinė Furjė transformacijos operacija

Patikrinti lygybės teisingumą yra gana paprasta – aiškiai pakeičiant Furjė transformacijas į formules ir sumažinant gautas formules

Furjė transformacijos koreliacijai apskaičiuoti

Leiskite (t) yra lygi koreliacijai, gautai vieną vektorių perslinkus kito atžvilgiu žingsniu t
Tada, kaip parodyta anksčiau,

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

Jei Furjė transformacijos algoritmo įgyvendinimai naudojami per kompleksiniai skaičiai, tada tokios transformacijos turi dar vieną nepaprastą savybę:

FFT(G') = KONJUGATAS (FFT(G))

Kur CONJUGATE (FFT(G)) yra matrica, sudaryta iš konjuguotų matricos FFT(G) elementų
Taigi, mes gauname

(t) = BFT (FFT(F)*KONJUGATAS (FFT(G)))

Furjė transformacijos uždaviniui išspręsti

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

mes tai gauname

• = XxY'
• |X|^2 = = XxX’xE’ = BFT (FFT(X) * KONJUGATAS (FFT(X)) * KONJUGATAS (FFT(E)))
• |Y|^2 = = YxY’xE’ = BFT (FFT(Y) * KONJUGATAS (FFT(Y)) * KONJUGATAS (FFT(E)))

Kur

• |X|(i,j) – vaizdo bendrosios dalies norma X esant poslinkiui (i,j)
• |Y|(i,j) – bendros vaizdo Y dalies norma poslinkio (i,j) metu

Problemos sprendimo formulių supaprastinimas

Sprendžiant vienos imties suradimo problemą, papildomas imties normalizavimas yra nereikalingas, o bendrosios dalies normos skaičiavimas gali būti pakeistas šios bendrosios dalies pikselių ryškumo suma arba kvadratų suma. ryškumas šioje bendroje dalyje
Naudojant formulę, skirtą įvertinti atstumą tarp vaizdų, kai jie paslinkti (i, j) vienas kito atžvilgiu

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

mes tai gauname

• = BFT (FFT(X) * KONJUGATAS (FFT(Y)))
• = BFT (Kvadratinio dydžio (FFT(X)) * KONJUGATAS (FFT(E)))

Kur

• (i,j) – dviejų vaizdų, gautų perkeliant (i,j) vaizdus X ir Y vienas kito atžvilgiu, skaliarinė sandauga
• E – vaizdas, kurio dydis lygus minimaliems X ir Y matmenims ir užpildytas atskiromis reikšmėmis (tai yra „rėmas“, kuriame lyginami X ir Y)
• (i,j) – bendros vaizdo dalies X su poslinkiu (i,j) norma (pikselių ryškumo suma)
• FFT – tiesioginės dvimatės diskrečios Furjė transformacijos veikimas
• BFT – atvirkštinė dvimatė diskretinė Furjė transformacijos operacija
• CONJUGATE – konjuguotų elementų matricos skaičiavimo operacija
• SQUAREMAGNITUDE – elementų kvadratinių amplitudių matricos skaičiavimo operacija

Fragmento paieškos visame vaizde algoritmas

• Tegu pateikiami du vaizdai X ir Y – vaizdas ir pavyzdys, atitinkamai (N1,N2) ir (M1,M2) dydžiai ir Ni > Mi
• Turite rasti pavyzdžio Y koordinates pilnas vaizdas X ir apskaičiuokite numatomą reikšmę – artumo matą.

1. Išskleiskite vaizdą Y iki dydžio (N1, N2), užpildydami jį nuliais
2. Suformuokite vaizdą E iš dydžio vienetų (M1, M2) ir išskleiskite iki dydžio (N1, N2), užpildydami jį nuliais
3. Apskaičiuokite = BFT (FFT(X) * KONJUGATAS (FFT(Y)))
4. Apskaičiuokite = BFT (Kvadratinio dydžio (FFT(X)) * KONJUGATAS (FFT(E)))
5. Apskaičiuokite M = (f + )/(f + )
6. Matricoje M raskite elementą su maksimali vertė– šio elemento koordinatės yra norima imties padėtis visame vaizde, o reikšmė lygi palyginimo mato įverčiui.

Pastaba:
Naudojant diskrečiąją Furjė transformaciją, matricoje M taip pat yra elementų iš vaizdų ciklinio poslinkio tarpusavyje. Todėl, jei jums nereikia analizuoti ciklinio kadro poslinkio, ieškokite maksimalus elementas matricoje M turi apsiriboti sritimi (0,0)-(N1-M1, N2-M2).

Įgyvendinimo pavyzdžiai

Įdiegti algoritmai yra atvirojo kodo FFTTools bibliotekos dalis. Interneto adresas: github.com/dprotopopov/FFTTools

Naudota programinė įranga

• Microsoft Visual Studio 2013 C# – aplinka ir programavimo kalba
• EmguCV/OpenCV – C++ vaizdų apdorojimo struktūrų ir algoritmų biblioteka
• FFTWSharp/FFTW – C++ biblioteka, įgyvendinanti greitus diskrečius Furjė transformacijos algoritmus

///

/// Vertybių matrica privati ​​Matrica Catch(Paveikslėlis vaizdas) ( const double f = 1,0; int ilgis = vaizdas.Data.Length; int n0 = vaizdas.Data.GetLength(0); int n1 = vaizdas.Data.GetLength(1); int n2 = vaizdas.Data.GetLength (2); fftw_plan backward = fftw_plan.dft_3d(n0, n1, n2, įvestis, išvestis, fftw_direction.Backward, fftw_flags.Estimate); (n0, n1); double[,] patternData = _patternImage.Data; doubles2 = output.GetData_Complex().Select(x => x.Magnitude);
///

// Rezultatas Buffer.BlockCopy(doubles1.Zip(doubles2, (x, y) => (f + x*x)/(f + y)).ToArray(), 0, duomenys, 0, ilgis* dydis (double ));

/// grąžinimo matrica; /// )/// Kopijuoti 3D masyvą į 2D masyvą (dydžiai gali skirtis) /// Apversti nukopijuotus duomenis /// Sumažinti paskutinį matmenį ///< 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; } ///

Įvesties masyvas

/// grąžinimo matrica; /// ) /// Išvesties masyvas privatus statinis void Kopijuoti(dvigubas[,] įvestis, dvigubas[,] išvestis) ( int n0 = išvestis.GetLength(0); int n1 = output.GetLength(1); int m0 ​​​​= Math.Min(n0, input) .GetLength (0)); int m1 = Math.Min(n1, input.GetLength(1));< m0; i++) for (int j = 0; j < m1; j++) output = value; } ///

/// Kopijuoti 3D masyvą į 2D masyvą (dydžiai gali skirtis) /// Pakeiskite nukopijuotus elementus pagal vertę /// Apverskite nukopijuotus duomenis /// Sumažinti paskutinį matmenį ///

/// Vertybių matrica /// Reikšmė pakeisti nukopijuotus duomenis /// Reikšmė pakeisti nukopijuotus duomenis /// privati ​​statinė void CopyAndReplace(double[,] įvestis, double[,] išvestis, dviguba reikšmė = 1,0) ( int n0 = išvestis.GetLength(0); int n1 = output.GetLength(1); int m0 ​​​​= Math. Min( n0, input.GetLength(0)); int m1 = Math.Min(n1, input.GetLength(1));/// Rasti maksimalų elementą matricoje /// Didžiausio elemento indeksas< n0; i++) { for (int j = 0; j < n1; j++) { if (data < value) continue; value = data; x = j; y = i; } } } ///

Didžiausio elemento vertė

/// public void Max(Matrix matrica, out int x, out int y, out dviguba reikšmė) (double[,] data = matrica.Data; int n0 = duomenys.GetLength(0); int n1 = duomenys.GetLength(1); vertė = duomenys x = y = 0 (int i = 0; i /// Užfiksuokite šablono taškinę schemą naudodami greičiausią Furjė transformaciją /// Vertybių masyvas

viešoji Matrica

Literatūra

1. Catch(Bitmap bitmap) ( naudojant (var image = new Image (bitmap)) return Catch(image);) Įkando A.L. Dmitrijevas.
2. Optiniai metodai
3. informacijos apdorojimas.

Pamoka . Sankt Peterburgas SPGUITMO 2005. 46 p., tada naudokite Furjė transformaciją, kad rastumėte ištisinį spektrą, tada jį diskretuokite. Panaši procedūra turi būti atliekama ir atvirkštiniam konvertavimui. Naudojant diskrečiąją Furjė transformaciją, galimas tiesioginis perėjimas nuo diskretinio signalo prie diskretiško spektro ir atvirkščiai.

Panagrinėkime nuolatinį baigtinės trukmės signalą, kurio laisvės laipsnių skaičius lygus Šiam signalui išplėtimą galime užrašyti Kotelnikovo serijoje:

Naudojant normalus konvertavimas Raskime šio signalo Furjė spektrą:

Tiesioginis integralo apskaičiavimas šioje formulėje yra daug darbo reikalaujanti procedūra. Tačiau tai nesunku padaryti kitu būdu.

Apsvarstykite spektrą, kurį nustato išraiška

Pritaikę jai atvirkštinę Furjė transformaciją, nustatome, kad ji atitinka laiko funkciją

Akivaizdu, kad atvirkštinis ryšys taip pat yra teisingas

Naudodamiesi delsos teorema, galime rašyti

Pakeitę (3.2) į (3.1), gauname galutinę spektro išraišką

Norint pereiti prie diskrečiosios Furjė transformacijos, spektro reikšmės išraiškoje (3.3) turi būti apskaičiuojamos ne visoms dažnio reikšmėms, o diskrečiosioms (atrinktoms):

Dėl to gauname galutinę diskrečiosios Furjė transformacijos formulę

Diskrečiosios Furjė transformacijos savybės daugeliu atžvilgių yra panašios į įprastos Furjė transformacijos savybes. Pažymėkime tik vieną konkrečią savybę, kuri

galima pavadinti diskrečiosios Furjė transformacijos periodiškumu.

Apsvarstykite vertę, nustatytą pagal formulę (3.4), kur yra sveikas skaičius:

Taigi diskretinė Furjė transformacija yra periodinė funkcija dažnis, kurio periodas lygus Ši savybė yra panaši į atrinktų signalų spektro periodiškumo savybę, kuri buvo aptarta skyriuje. 2.

Dabar pereikime prie atvirkštinės diskrečiosios Furjė transformacijos išvedimo, kuri leidžia mums nustatyti signalo pavyzdžius iš spektro pavyzdžių. Norėdami tai padaryti, naudojame įprastą atvirkštinę Furjė transformaciją

Signalo spektrinį tankį užrašome Kotelnikovo serijos forma

ir pakeiskite į atvirkštinės Furjė transformacijos integralą

Integralas išraiškoje yra panašus į anksčiau apskaičiuotą integralą (3.2). Remdamiesi šia analogija, rašome

Pakeitę (3.6) į (3.5), gauname laiko funkcijos išraišką

Darant prielaidą, kad sąryšyje gauname formulę, skirtą diskrečiojo signalo reikšmėms nustatyti, t. y. gauname atvirkštinę diskrečiąją Furjė transformaciją

kur A reikšmes nuo 0 iki

Kartais dėl žymėjimo patogumo, naudojant diskrečiosios Furjė transformacijos periodiškumo savybę, sumavimo ribos išraiškoje (3.8) pakeičiamos ir atvirkštinė diskretinė Furjė transformacija įrašoma forma.

Norėdami iliustruoti, taikykite diskrečiąją Furjė transformaciją atrinktam trikampiam impulsui (apibūdintam penkiomis imties reikšmėmis Fig.

Pakeiskime šią išraišką diskrečiu signalu į diskrečiosios Furjė transformacijos formulę (3.4)

Palyginimui, suraskime spektrinis tankis pradinis trikampis impulsas:

Nesunku pastebėti, kad diskrečiasis spektras (3.11) netiksliai apibūdina trikampio impulso (3.12) spektrinį tankį. Reikšmės šiek tiek skiriasi nuo atitinkamų trikampio impulsų spektro verčių (3.1 pav., b).

Dabar pakeiskime diskrečiąsias spektro reikšmes (3.11) į atvirkštinės diskrečiosios Furjė transformacijos (3.8) išraišką:

Nepaisant skirtumo tarp diskretinio spektro ir nuolatinio spektro verčių, gautas rezultatas visiškai sutampa su pradinio diskretinio signalo formule (3.11).

Nagrinėjamas pavyzdys rodo, kad diskrečioji Furjė transformacija ne visada tiksliai apibūdina pradinio nuolatinio signalo spektrą, kaip

Ryžiai. 3.1. Atrinkto trikampio impulso diskretinė Furjė transformacija

atrinktas signalas ne visada tiksliai apibūdina pradinį nuolatinį signalą. Tačiau ryšys tarp diskretinio signalo ir jo diskrečiosios Furjė transformacijos visada yra vienas su vienu, o tiesioginės ir atvirkštinės Furjė transformacijos formulė yra griežta bet kuriam skaičiui. diskrečiųjų vertybių. Todėl diskrečiųjų Furjė transformacijų aparatas turi nepriklausomą reikšmę ir gali būti taikomas bet kurioms skaitinėms sekoms.

Šiuo atveju diskrečios Furjė transformacijos formulės turi būti šiek tiek pakeistos, nes abstrakčiai skaičių seka Atrankos intervalo ir signalo trukmės reikšmės yra beprasmės. Todėl (3.4) formulėje esantis koeficientas prieš sumą praleidžiamas, pakeičiamas signalo ir spektro etaloninėmis reikšmėmis, pažymėtomis ir diskrečios Furjė transformacijos formulė parašyta forma

Šiuo atveju atvirkštinė diskretinė Furjė transformacija turi formą

Vertės, apskaičiuotos pagal formulę (3.14), skiriasi nuo nuolatinio virpesių spektro imties verčių koeficientu. Norėdami nustatyti imties vertes, turite padauginti reikšmes, apskaičiuotas pagal formulę (3.14), iš laiko atrankos intervalo vertės:

Parodykime, kad transformacijos (3.14), (3.15) yra tarpusavyje atvirkštinės. Norėdami tai padaryti, paimkite savavališką skaitinę seką naudodami diskrečiąją Furjė transformaciją (3.14), suraskite seką ir pritaikykite jai atvirkštinę diskrečiąją transformaciją

Furjė (3,15). Mes pažymime gautą seką

Pakeiskime sumavimo tvarką ir šiek tiek pakeiskime šią išraišką:

Vidinė išraiškos suma (3.16) lygi nuliui jei ir lygi if Todėl kai t.y. skaičių sekos sutampa viena su kita. Taigi, nuosekliai pritaikius bet kuriai skaitinei sekai, tiesioginės ir atvirkštinės diskrečios Furjė transformacijos sukuria tą pačią seką.

Iliustruosime šį klausimą paprasčiausiais pavyzdžiais.

1. Apsvarstykite paprasčiausią diskrečiąjį signalą, sudarytą iš vienos imties reikšmės, lygios a. Pakeitę šią paprasčiausią seką į diskrečiąją Furjė transformacijos formulę (3.14), gauname individo diskrečiąją Furjė transformaciją skaitinė reikšmė lygi tai pačiai vertei.

Kitas svarbus diskrečiosios Furjė transformacijos pritaikymas yra signalo apskaičiavimas filtro išvestyje su tam tikru dažnio atsaku. Jei duotas įvesties signalas, tai jam galima apskaičiuoti diskrečiąją Furjė transformaciją Jei dabar padauginsime iš filtro dažnio atsako, gausime diskrečiąją išėjimo signalo Furjė transformaciją: Po to, naudojant atvirkštinę diskrečiąją Furjė transformaciją. , galime rasti signalą filtro išvestyje.

Jei įvesties signalas yra ilgas, jį galima apdoroti naudojant atskirą Furjė transformaciją dalimis. Norėdami tai padaryti, paimkite pirmuosius N įvesties signalo pavyzdžius, apskaičiuokite jų diskrečiąją Furjė transformaciją ir, padauginus iš filtro dažnio atsako, naudokite atvirkštinę diskrečiąją Furjė transformaciją, kad apskaičiuotumėte pirmuosius N išėjimo signalo pavyzdžius. Po to panašiu būdu apdorojami kiti N įvesties signalo pavyzdžiai ir tt Siekiant padidinti signalo apdorojimo tikslumą, apdorotos mėginių serijos gali iš dalies sutapti.

Šio signalo apdorojimo metodo pranašumas yra tai, kad nėra jokių filtro dažnio atsako tipo apribojimų. Pavyzdžiui, dažnio atsakas gali būti tobulos stačiakampio formos, ko negalima pasiekti naudojant įprastus filtrus.

Signalo apdorojimas naudojant diskrečiąją Furjė transformaciją negali būti vadinamas skaitmeniniu filtravimu visomis prasmėmisžodžius. Įprasti skaitmeniniai filtrai, veikiantys realiu laiku, nuolat apdoroja signalą, kai jis gaunamas, o išėjimo signalo skaičiavimas naudojant diskrečiąją Furjė transformaciją gali būti atliktas tik tada, kai yra žinomas visas įvesties signalas arba bent pirmoji N pavyzdžių serija. Todėl, naudojant diskrečiąją Furjė transformaciją, išėjimo signalą galima gauti tik su tam tikru

delsa, palyginti su įvesties signalu. Tačiau daugelyje praktiniai pritaikymai toks išėjimo signalo delsimas nevaidina reikšmingo vaidmens, o tada signalo apdorojimas naudojant diskrečiąją Furjė transformaciją pasirodo tinkamas.