Nous explorons les caractéristiques de la représentation spectrale d'un signal discret, qui est spécifié sur un segment par ses propres lectures 
, pris respectivement à des moments 
; nombre total d'échantillons 
(
- intervalle d'échantillonnage).
La technique pour étudier de tels signaux discrets consiste à répéter mentalement l'échantillon résultant de valeurs de référence un nombre infini de fois. Le signal devient alors périodique.
En associant un certain modèle mathématique à un tel signal, vous pouvez utiliser le développement en série de Fourier et trouver les coefficients d'amplitude correspondants. La combinaison de ces coefficients forme le spectre d'un signal périodique discret.
Utilisons le modèle sous la forme d'une séquence d'impulsions delta. Alors la vibration initiale sera exprimée par la formule :
(5.1)
Où 
– des exemples de valeurs du signal analogique.
- transformée de Fourier discrète (TFD) (5.4)
Propriétés de base de DFT
1. DFT - transformation linéaire, c'est-à-dire la somme des signaux correspond à la somme de leurs DFT
2. Nombre de coefficients différents 
, calculé selon la formule (5.4), est égal au nombre N par période ; au coefficient 
3. Coefficient 
(composante constante) est la valeur moyenne de toutes les lectures :
5. Laissez les valeurs de référence 
- nombres réels. Alors les coefficients DFT, dont les nombres sont situés symétriquement par rapport à /2, forment des couples conjugués :
Le problème de l’analyse spectrale discrète peut être formulé d’une autre manière. Supposons que les coefficients 
, formant la DFT, sont donnés. Mettons dans la formule (5.2) 
et tenir compte du fait que seul un nombre fini de termes de la série sont sommés, qui correspondent aux harmoniques contenues dans le spectre du signal original.
Ainsi, on obtient une formule de calcul des valeurs de référence
(5.5)
Évidemment, (5.5) est la formule de transformée de Fourier discrète inverse (IDFT).
11 Algorithme de transformée de Fourier rapide. Nombre d'opérations de calcul. Comparaison des transformées de Fourier discrètes et rapides.
=0,
1, 2,…,( /2)-1
(5.7)
Prenons en compte que les séquences de coefficients liées aux parties paires et impaires du tableau d'entrée sont périodiques avec une période de N/2 :
De plus, le facteur inclus dans la formule (5.7) à 
peut être converti comme ceci :
De là, nous trouvons l'expression de la seconde moitié de l'ensemble des coefficients DFT
(5.8)
Les formules (5.7) et (5.8) constituent la base de l'algorithme FFT. Ensuite, les calculs sont effectués selon le principe itératif : les séquences d'échantillons de nombres pairs et impairs sont à nouveau divisées en deux parties. Le processus se poursuit jusqu'à ce qu'une séquence composée d'un seul élément soit obtenue. La DFT de cet élément coïncide avec elle-même.
Le nombre d'opérations nécessaires pour calculer la FFT est estimé comme suit : 
.
Le gain en vitesse de calcul par rapport à la DFT traditionnelle atteint des centaines, voire des milliers si les tableaux d'entrée sont de longueur suffisante.
12.. Z - la transformation et ses propriétés. Application Z - transformations.
Dans l'analyse et la synthèse de dispositifs discrets et numériques, la transformée en Z joue le même rôle que les transformées intégrales de Fourier par rapport aux signaux continus.
Laisser 
– une séquence numérique, finie ou infinie, contenant les valeurs de référence d'un certain signal. Mettons-le dans une correspondance unique avec la somme des séries dans pouvoirs négatifs variable complexe Z :
(5.9)
Cette somme est appelée la transformée en Z de la séquence 
. Les propriétés des séquences discrètes de nombres peuvent être étudiées en étudiant leurs transformations Z à l'aide de méthodes conventionnelles d'analyse mathématique.
Cette expression a du sens lorsque |Z|> 
.
Transformation Z inverse
Soit x(z) une fonction de la variable complexe Z. Une propriété remarquable de la transformée en Z est que la fonction x(z) définit l'ensemble infini d'échantillons ( 
).
En effet, multiplions les deux membres de la série (5,9) par le facteur 
:
Les intégrales de tous les termes du côté droit disparaîtront, à l'exception du terme de numéro m, donc :
(5.11)
Cette expression est appelée transformation Z inverse.
Les propriétés les plus importantes Z -conversions :
1. Linéarité. Si 
Et 
- certains signaux discrets, et les transformées Z correspondantes x(z) et y(z) sont connus, alors le signal 
correspondra à la transformation pour toute constante 
Et 
. La preuve s'effectue en substituant la somme dans la formule (5.9).
2.
Z-conversion du signal décalé. Considérons signal discret
, résultant d'un signal discret 
en déplaçant d'une position vers le retard, c'est-à-dire Quand 
. En calculant directement la transformée en Z, on obtient le résultat suivant :
Donc le symbole 
sert d'opérateur de retard unitaire (par intervalle d'échantillonnage) dans le domaine Z.
3. Z-transformation par convolution. Soit x(z) et y(z) des signaux continus pour lesquels la convolution est définie :
(5.13)
En ce qui concerne les signaux discrets, par analogie avec (5.13), il est d'usage d'introduire convolution discrète
– une suite de nombres dont le terme commun est :
Une telle convolution discrète est appelée linéaire
Calculons la transformée en Z de convolution discrète :
(5.15)
Ainsi, la convolution de deux signaux discrets correspond au produit des transformées en Z.
Filtrage linéaire les images peuvent être réalisées à la fois dans l’espace et domaine fréquentiel. On pense que les fréquences spatiales « basses » correspondent au contenu principal de l'image - l'arrière-plan et les objets de grande taille, et les fréquences spatiales « élevées » - les objets de petite taille, les petits détails de grandes formes et la composante de bruit.
Traditionnellement, pour passer au domaine des fréquences spatiales, on utilise des méthodes basées sur la $\textit(Fourier transform)$. DANS dernières années Tous une plus grande application Des méthodes basées sur $\textit(wavelet-transform)$ sont également trouvées.
Transformée de Fourier.
La transformée de Fourier vous permet de représenter presque n'importe quelle fonction ou ensemble de données comme une combinaison de ces éléments. fonctions trigonométriques, comme le sinus et le cosinus, qui permet d'identifier les composantes périodiques des données et d'évaluer leur contribution à la structure des données d'origine ou à la forme de la fonction. Traditionnellement, il existe trois formes principales de transformée de Fourier : la transformée de Fourier intégrale, la série de Fourier et la transformée de Fourier discrète.
La transformée intégrale de Fourier transforme une fonction réelle en une paire de fonctions réelles ou une fonction complexe en une autre.
La fonction réelle $f(x)$ peut être développée dans un système orthogonal de fonctions trigonométriques, c'est-à-dire représenté sous la forme
$$ 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 , $$
où $A(\omega)$ et $B(\omega)$ sont appelés transformations intégrales cosinus et sinus :
$$ 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 )\droite)dx. $$
La série de Fourier représente une fonction périodique $f(x)$, définie sur l'intervalle $$, comme une série infinie en sinus et cosinus. Autrement dit, la fonction périodique $f(x)$ est associée à une séquence infinie de coefficients de Fourier
$$ 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 . $$
La transformée de Fourier discrète transforme une séquence finie nombres réels en une suite finie de coefficients de Fourier.
Soit $\left\( (x_i ) \right\), i= 0,\ldots, N-1 $ - une séquence de nombres réels - par exemple, la luminosité des pixels compte le long d'une ligne d'image. Cette séquence peut être représentée comme une combinaison montants finaux gentil
$$ 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 La principale différence entre les trois formes de transformée de Fourier est que si la transformée de Fourier intégrale est définie sur tout le domaine de définition de la fonction $f(x)$, alors la série et la transformée de Fourier discrète ne sont définies que sur un ensemble discret de points, infini pour la série de Fourier et fini pour les transformations discrètes. Comme le montrent les définitions de la transformée de Fourier, la transformée de Fourier discrète présente le plus grand intérêt pour les systèmes de traitement du signal numérique. Les données reçues des médias numériques ou des sources d'information sont des ensembles ordonnés de nombres écrits sous forme de vecteurs ou de matrices. On suppose généralement que les données d'entrée d'une transformation discrète sont un échantillon uniforme avec un pas de $\Delta $, la valeur $T=N\Delta $ étant appelée la longueur d'enregistrement ou la période fondamentale. La fréquence fondamentale est de 1 $/T$. Ainsi, la transformée de Fourier discrète décompose les données d'entrée en fréquences qui sont un multiple entier de la fréquence fondamentale. La fréquence maximale, déterminée par la dimension des données d'entrée, est égale à $1/2 \Delta $ et est appelée $\it(Fréquence de Nyquist)$. La prise en compte de la fréquence de Nyquist est importante lors de l'utilisation d'une transformation discrète. Si les données d'entrée comportent des composantes périodiques avec des fréquences supérieures à la fréquence de Nyquist, alors la transformée de Fourier discrète remplacera les données haute fréquence par une fréquence inférieure, ce qui peut conduire à des erreurs dans l'interprétation des résultats de la transformée discrète. $\it(spectre énergétique)$ est également un outil important pour l'analyse des données. La puissance du signal à la fréquence $\omega $ est déterminée comme suit : $$ P \left(\omega \right)=\frac(1)(2)\left((A \left(\omega \right)^2+B \left(\omega \right)^2) \right ) . $$ Cette quantité est souvent appelée $\it(énergie du signal)$ à la fréquence $\omega $. Selon le théorème de Parseval, l'énergie totale du signal d'entrée est égale à la somme des énergies à toutes les fréquences. $$ E=\sum\limits_(i=0)^(N-1) (x_i^2 ) =\sum\limits_(i=0)^(N/2) (P \left((\omega _i ) \droite)) . $$ Un graphique de la puissance en fonction de la fréquence est appelé spectre d'énergie ou spectre de puissance. Le spectre énergétique permet d'identifier les périodicités cachées dans les données d'entrée et d'évaluer la contribution de certaines composantes de fréquence à la structure des données d'entrée. En plus de la forme trigonométrique d'enregistrement de la transformée de Fourier discrète, $\it(représentation complexe)$ est largement utilisée. La forme complexe d'enregistrement de la transformée de Fourier est largement utilisée en analyse multidimensionnelle et notamment en traitement d'images. Le passage de la forme trigonométrique à la forme complexe s'effectue sur la base de la formule d'Euler $$ e^(j\omega t)=\cos \omega t+j\sin \omega t, \quad j=\sqrt (-1) . $$ Si la séquence d'entrée est constituée de nombres complexes $N$, alors sa transformée de Fourier discrète sera $$ G_m =\frac(1)(N)\sum\limits_(n=1)^(N-1) (x_n ) e^(\frac(-2\pi jmn)(N)), $$ et la transformation inverse $$ x_m =\sum\limits_(n=1)^(N-1) (G_n ) e^(\frac(2\pi jmn)(N)). $$ Si la séquence d'entrée est un tableau de nombres réels, alors il existe à la fois une transformation sinus-cosinus complexe et discrète. La relation entre ces idées s’exprime comme suit : $$ a_0 =G_0 , \quad G_k =\left((a_k -jb_k ) \right)/2, \quad 1\le k\le N/2; $$ les valeurs de transformation $N/2$ restantes sont des conjugués complexes et ne contiennent pas d'informations supplémentaires. Par conséquent, le tracé du spectre de puissance de la transformée de Fourier discrète est symétrique par rapport à $N/2$. La façon la plus simple de calculer la transformée de Fourier discrète (TFD) est la sommation directe, qui aboutit à des opérations $N$ sur chaque coefficient. Les coefficients totaux sont $N$, donc la complexité totale est $O\left((N^2) \right)$. Cette approche n'a pas d'intérêt pratique, car il existe des moyens beaucoup plus efficaces de calculer la TFD, appelée transformation de Fourier rapide (FFT), qui a une complexité de $O (N\log N)$. FFT s'applique uniquement aux séquences dont la longueur (nombre d'éléments) est une puissance de 2. Le principe le plus général de l'algorithme FFT est de diviser la séquence d'entrée en deux séquences de demi-longueur. La première séquence est remplie de données paires et la seconde de données impaires. Cela permet de calculer les coefficients DFT à travers deux transformations de dimension $N/2$. Notons $\omega _m =e^(\frac(2\pi j)(m))$, alors $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)\oméga _N^m $. Pour millions de dollars< 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$. Полный алгоритм БПФ заключается в рекурсивном
выполнении вышеописанной процедуры, начиная с объединения одиночных элементов в пары,
затем в четверки и так до полного охвата исходного массива данных. La transformée de Fourier discrète pour un tableau bidimensionnel de nombres de taille $M\times N$ est définie comme suit : $$ 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]) ), $$ et la transformation inverse $$ 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]) ). $$ Dans le cas du traitement d'images, les composantes de la transformée de Fourier bidimensionnelle sont appelées $\textit(fréquences spatiales)$. Une propriété importante de la transformée de Fourier bidimensionnelle est la possibilité de la calculer à l'aide de la procédure FFT unidimensionnelle : $$ 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) ), $$ Ici, l'expression entre crochets est une transformation unidimensionnelle d'une ligne de la matrice de données, qui peut être effectuée avec une FFT unidimensionnelle. Ainsi, pour obtenir une transformée de Fourier bidimensionnelle, il faut d'abord calculer des transformations de lignes unidimensionnelles, écrire les résultats dans la matrice d'origine et calculer des transformations unidimensionnelles pour les colonnes de la matrice résultante. Lors du calcul de la transformée de Fourier bidimensionnelle, les basses fréquences seront concentrées dans les coins de la matrice, ce qui n'est pas très pratique pour un traitement ultérieur des informations reçues. Pour traduire afin d'obtenir une représentation de transformée de Fourier 2D dans laquelle les basses fréquences sont concentrées au centre de la matrice, une procédure simple qui peut être effectuée consiste à multiplier les données d'origine par $-1^(m+n)$. En figue. La figure 16 montre l'image originale et sa transformée de Fourier. Image en demi-teinte et sa transformée de Fourier (images obtenues dans LabVIEW) La convolution des fonctions $s(t)$ et $r(t)$ est définie comme $$ s\ast r\cong r\ast s\cong \int\limits_(-\infty )^(+\infty ) (s(\tau)) r(t-\tau)d\tau . $$ En pratique, nous devons faire face à une convolution discrète, dans laquelle les fonctions continues sont remplacées par des ensembles de valeurs aux nœuds d'une grille uniforme (généralement une grille entière est prise) : $$ (r\ast s)_j \cong \sum\limits_(k=-N)^P (s_(j-k) r_k ). $$ Ici $-N$ et $P$ définissent la plage au-delà de laquelle $r(t) = 0$. Lors du calcul de convolution à l'aide de la transformée de Fourier, la propriété de la transformée de Fourier est utilisée, selon laquelle le produit des images de fonctions dans le domaine fréquentiel est équivalent à la convolution de ces fonctions dans le domaine temporel. Pour calculer le rapprochement, il est nécessaire de transformer les données originales dans le domaine fréquentiel, c'est-à-dire de calculer sa transformée de Fourier, de multiplier les résultats de la transformation et d'effectuer la transformée de Fourier inverse, en restaurant la représentation originale. La seule subtilité dans le fonctionnement de l'algorithme est due au fait que dans le cas d'une transformée de Fourier discrète (par opposition à une transformée continue), deux fonctions périodiques sont alambiquées, c'est-à-dire que nos ensembles de valeurs précisent exactement la périodes de ces fonctions, et pas seulement les valeurs sur une section distincte de l'axe. Autrement dit, l'algorithme estime que le point $x_(N )$ n'est pas suivi de zéro, mais du point $x_(0)$, et ainsi de suite dans un cercle. Par conséquent, pour que la convolution soit calculée correctement, il est nécessaire d'attribuer une séquence de zéros suffisamment longue au signal. Les méthodes de filtrage linéaire font partie des méthodes bien structurées pour lesquelles des schémas de calcul efficaces basés sur des algorithmes de convolution rapide et une analyse spectrale ont été développés. En général, les algorithmes de filtrage linéaire effectuent une transformation de la forme $$ f"(x,y) = \int\int f(\zeta -x, \eta -y)K (\zeta , \eta) d \zeta d \eta , $$ où $K(\zeta ,\eta)$ est le noyau de la transformation linéaire. Avec une représentation discrète du signal, l'intégrale de cette formule dégénère en une somme pondérée d'échantillons de l'image originale dans une certaine ouverture. Dans ce cas, le choix du noyau $K(\zeta ,\eta)$ selon l'un ou l'autre critère d'optimalité peut conduire à un certain nombre de propriétés utiles (lissage gaussien lors de la régularisation du problème de différenciation numérique d'une image, etc.) . Les méthodes de traitement linéaire sont mises en œuvre le plus efficacement dans le domaine fréquentiel. L'utilisation de la transformée de Fourier d'une image pour effectuer des opérations de filtrage est principalement due aux performances plus élevées de ces opérations. En règle générale, effectuer des transformations de Fourier 2D avant et inverse et multiplier par les coefficients de l'image de Fourier du filtre prend moins de temps que d'effectuer une convolution 2D sur l'image d'origine. Les algorithmes de filtrage du domaine fréquentiel sont basés sur le théorème de convolution. Dans le cas 2D, la transformation par convolution ressemble à ceci : $$ G\left((u,v) \right)=H\left((u,v) \right)F\left((u,v) \right), $$ où $G$ est la transformée de Fourier du résultat de convolution, $H$ est la transformée de Fourier du filtre et $F$ est la transformée de Fourier de l'image originale. Autrement dit, dans le domaine fréquentiel, la convolution bidimensionnelle est remplacée par une multiplication élément par élément des images de l'image originale et du filtre correspondant. Pour effectuer une convolution, vous devez procéder comme suit : La relation entre la fonction de filtre dans le domaine fréquentiel et le domaine spatial peut être déterminée à l'aide du théorème de convolution $$ \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)\droite). $$ La convolution d'une fonction avec une fonction impulsionnelle peut être représentée comme suit : $$ \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). $$ Transformée de Fourier de la fonction d'impulsion $$ F\left((u,v) \right)=\frac(1)(MN)\sum\limits_(x=0)^M (\sum\limits_(y=0)^N (\delta \ gauche((x,y) \right) ) ) e^( (-2\pi j\left((\frac(ux)(M)+\frac(vy)(N)) \right)) ) =\ frac(1)(MN). $$ Soit $f(x,y) = \delta (x,y)$, puis convolution $$ 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). $$ À partir de ces expressions, il est clair que les fonctions de filtre dans les domaines fréquentiel et spatial sont interdépendantes via la transformée de Fourier. Pour une fonction de filtre donnée dans le domaine fréquentiel, il est toujours possible de trouver un filtre correspondant dans le domaine spatial en appliquant la transformée de Fourier inverse. Il en va de même pour le cas inverse. En utilisant cette relation, une procédure de synthèse de filtres linéaires spatiaux peut être définie. ($\textit(Filtre passe-bas idéal)$) $H(u,v)$ a la forme $$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(Filtre passe-haut idéal)$) est obtenu en inversant le filtre passe-bas idéal : $$ H"(u,v) = 1-H(u,v). $$ Ici, les composantes basses fréquences sont complètement supprimées tandis que les composantes hautes fréquences sont préservées. Cependant, comme dans le cas d'un filtre passe-bas idéal, son utilisation se heurte à l'apparition d'une distorsion importante. Diverses approches sont utilisées pour synthétiser des filtres avec une distorsion minimale. L’un d’eux est la synthèse de filtres exponentiels. De tels filtres introduisent une distorsion minimale dans l’image résultante et conviennent à la synthèse dans le domaine fréquentiel. Une famille de filtres basés sur la fonction gaussienne réelle est largement utilisée en traitement d'images. $\textit(Filtre gaussien passe-bas)$ a la forme $$ h\left(x \right)=\sqrt (2\pi ) \sigma Ae^(-2\left((\pi \sigma x) \right)^2) \mbox( et ) H\left( u \right)=Ae^(-\frac(u^2)(2\sigma ^2)) $$ Plus le profil du filtre dans le domaine fréquentiel est étroit (plus $\sigma $ est grand), plus il est large dans le domaine spatial. ($\textit(Filtre gaussien passe-haut)$) a la forme $$ 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 )). $$ Dans le cas bidimensionnel ($\it(passe-bas)$), le filtre gaussien ressemble à ceci : $$ H\left((u,v) \right)=e^(-\frac(D^2\left((u,v) \right))(2D_0^2 )). $$ ($\it(High Pass)$) Le filtre gaussien a la forme $$ H\left((u,v) \right)=1-e^(-\frac(D^2\left((u,v) \right))(2D_0^2 )). $$ Considérons un exemple de filtrage d'image (Fig. 1) dans le domaine fréquentiel (Fig. 17 - 22). Notez que le filtrage fréquentiel d'une image peut avoir le sens à la fois de lissage ($\textit(filtrage passe-bas)$) et de mise en évidence des contours et des objets de petite taille ($\textit(filtrage passe-haut)$). Comme on peut le voir sur la Fig. 17, 19, à mesure que la « puissance » de filtrage augmente dans la composante basse fréquence de l’image, l’effet de « défocalisation apparente » ou $\it(flou)$ de l’image devient de plus en plus prononcé. Dans le même temps, la majeure partie du contenu informatif de l'image passe progressivement dans la composante haute fréquence, où au début seuls les contours des objets sont observés (Fig. 18, 20 - 22). Considérons maintenant le comportement des filtres passe-haut et passe-bas (Fig. 23 - 28) en présence de bruit gaussien additif dans l'image (Fig. 7). Comme on peut le voir sur la Fig. 23, 25, les propriétés des filtres basse fréquence pour supprimer le bruit aléatoire additif sont similaires aux propriétés des filtres linéaires précédemment considérés - avec une puissance de filtrage suffisante, le bruit est supprimé, mais le prix en est un fort flou des contours et une « défocalisation » » de l’image entière. La composante haute fréquence d'une image bruitée cesse d'être informative, car en plus des informations sur les contours et les objets, la composante bruit est désormais également pleinement présente (Fig. 27, 28). L'utilisation de méthodes fréquentielles est la plus appropriée dans le cas où le modèle statistique du processus de bruit et/ou la fonction de transfert optique du canal de transmission d'images sont connus. Il est commode de prendre en compte de telles données a priori en choisissant comme filtre de reconstruction un filtre contrôlé généralisé (par paramètres $\sigma$ et $\mu$) de la forme suivante : $$ 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]. $$ où 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)$. Этот алгоритм эффективно фильтрует
засоренные однородные поверхности (области) фона. Однако при попадании в
скользящее окно обработки неоднородных участков фона импульсная
характеристика фильтра сужается ввиду резкого изменения локальных статистик,
и эти неоднородности (контуры, пятна) передаются практически без
расфокусировки, свойственной неадаптивным методам линейной фильтрации. Les avantages des méthodes de filtrage linéaire incluent leur signification physique claire et leur facilité d'analyse des résultats. Cependant, avec une forte détérioration du rapport signal sur bruit, avec d'éventuelles variantes de bruit de zone et la présence de bruit impulsionnel de haute amplitude, les méthodes de prétraitement linéaire peuvent s'avérer insuffisantes. Dans cette situation, les méthodes non linéaires sont beaucoup plus puissantes. Introduction Au cours du cours de laboratoire, les possibilités de transformation trigonométrique discrète (PDP) ont été étudiées des points de vue suivants : 1. Nous avons vérifié la propriété de réversibilité de l’accident donné. 2. La linéarité de l'accident proposé a été étudiée. 3. Nous avons étudié les caractéristiques du spectre de répétition de l'accident testé. 4. Nous avons déterminé la présence d'une réflexion symétrique du spectre lors d'un accident, à savoir 4.1. présence de symétrie centrale, 4.2. la présence d'une symétrie axiale (verticale). 5. Nous avons considéré l'influence des déphasages du signal sur l'accident qui en résulte. 6. Vérification de la présence de la propriété de similarité pour la transformation donnée. 7. Nous avons étudié la possibilité de filtrer les signaux à partir d'un accident donné. 8. Nous avons testé expérimentalement la conservation de l’énergie dans l’accident routier étudié. 9. Nous avons découvert un lien entre cet accident et la transformée de Fourier discrète. Divers signaux d’entrée ont également été pris en compte pour une analyse plus représentative. La plus célèbre des transformations fonctionnelles discrètes est la transformée de Fourier discrète (TFD) Transformée de Fourier discrète La transformée de Fourier discrète détermine le spectre de raies d'une fonction périodique discrétisée du temps. La transformée de Fourier discrète inverse permet de reconstruire la fonction temps à partir de son spectre. Ces transformations sont généralement abrégées respectivement en DFT et ODFT. La DFT est utilisée pour analyser les fonctions périodiques et peut être obtenue à partir de la théorie des séries de Fourier. Soit x0(t) une fonction périodique continue de période P et de fréquence f0 = 1/P telle que La fonction x0(t) peut être développée en une série de Fourier : où les coefficients de dilatation X0(n) sont donnés par la formule Habituellement, x0(t) est une fonction réelle, et alors X0(n) est complexe (mais cette restriction n'est pas nécessaire). Puisque nous considérons x0 en fonction du temps, X0(n) peut être appelé le spectre complexe de x0(t). En utilisant les parties réelles et imaginaires de X0(n), on peut trouver l’amplitude et la phase des composantes qui forment l’oscillation x0(t). Considérons la discrétisation de la fonction périodique x0(t). Pour que cette fonction soit discrétisée de manière unique, son spectre ne doit pas contenir de composantes de fréquence supérieure à une certaine fréquence f1, c'est-à-dire où n1 est une valeur entière de n spécifiant la fréquence f1. En figue. La figure 1 montre par exemple un spectre limité et la vibration à laquelle il correspond. l'intervalle d'échantillonnage T est égal à donc le nombre d'échantillons par période sera Figue. 1. Fonction périodique x0(t) avec une bande de fréquence limitée et son spectre X0(n). 1Grâce à la discrétisation, on obtient une oscillation périodique normalisée par rapport à T de la forme Cette oscillation est définie sur un intervalle égal à sa période, soit Puisque x(t/T) est une fonction périodique, la relation (2) est utilisée pour calculer les coefficients de la série de Fourier (Remplacer P par /V dans le diviseur et les limites d'intégration correspond au passage à une variable normalisée.) En remplaçant l'expression (3), on obtient Il est connu que Enfin, compte tenu du fait que par définition La relation reliant x(k) à X(n) peut être obtenue directement à partir de la formule (1), si l'on substitue t=kT et prenons en compte qu'avec une largeur limitée du spectre de la fonction x0(t), la somme contient un nombre fini de termes. Donc, Il convient de noter que x(k) est une fonction périodique, c'est-à-dire et de même Le fait que le spectre soit périodique s'explique par la périodicité du spectre de toute fonction discrétisée, et sa nature discrète est due au fait que la fonction discrétisée elle-même est également périodique. Ainsi, lors de la discrétisation d'une fonction périodique x0(t), la relation (4) permet d'utiliser des échantillons x0(t) pour trouver le spectre X(n), qui dans l'intervalle 0 ≤ n ≤ N - 1 est exactement égal au spectre X0 (n) de la fonction périodique d’origine. La fonction x(k) et son spectre sont présentés graphiquement sur la Fig. 2. Puisque la relation (5.4) est obtenue sur la base du théorème d'échantillonnage, elle constitue un équivalent précis et économique (en termes de calculs) de la relation intégrale originale (2) et peut être utilisée pour calculer les coefficients de dilatation sur un ordinateur. Nous appellerons respectivement les relations (4) et (5) la transformée de Fourier discrète (DFT) et la transformée de Fourier discrète inverse (IDFT). Notons que la variable n varie ici de zéro à N-1. Le spectre résultant peut être interprété comme suit. Les (N/2-1) premiers points X(n) correspondent à (N/2 - 1) raies spectrales X0(n) à des fréquences positives, comme le montre la Fig. 5.3, et les (N/2-1) derniers points X(n) correspondent à (N/2-1) raies spectrales aux fréquences négatives. La paire de transformations donnée par les relations (4) et (5) se présente également sous une autre forme. Par exemple, le multiplicateur 1/N et le signe moins de l'exposant peuvent être écrits aussi bien en transformation directe qu'inverse, le sens général ne change pas. Bien entendu, le spectre dans ce cas ne peut pas être directement identifié avec celui défini par la formule (2). Parfois, les deux transformations sont données avec les mêmes facteurs (1 / N)1/2. Figue. 2. Fonction périodique discrétisée x(k) et son spectre périodique X(n). Figue. 3. La relation entre les coefficients de la série de Fourier et la DFT. Propriétés du DFT Certaines propriétés de la DFT jouent un rôle important dans les problèmes pratiques du traitement du signal. Linéarité Si xp(n) et ur(n) sont des séquences périodiques (avec une période de N échantillons chacune), et Xp(k) et Yp(k) sont leurs TFD, alors la transformée de Fourier discrète de la séquence xp(n) + + ur(n ) est égal à Хр(k) + Yp(k). Cela est également vrai pour les séquences de longueur finie. Changement Si la séquence xp(n) est périodique de période de N échantillons, et que sa DFT est égale à Xp(k), alors la DFT d'une séquence périodique de la forme xp(n-n0) sera égale. Figue. 4. Vers la définition de la DFT d'une séquence décalée. Lors de l'analyse de séquences de longueur finie, il est nécessaire de prendre en compte la nature spécifique du décalage temporel de la séquence. Ainsi, sur la Fig. 4, a montre une séquence finie x(n) de longueur N échantillons. Au même endroit, des croix représentent des échantillons de la séquence périodique équivalente xp(n), qui a la même DFT que x(n). Pour trouver la DFT de la séquence décalée x(n - n0) et n0< N, следует рассмотреть сдвинутую периодическую последовательность Хр(n - n0) и в качестве эквивалентной сдвинутой конечной последовательности (имеющей ДПФ j принять отрезок последовательности хр(n - n0) в интервале 0 ≤ n ≤ N - 1. Таким образом, с точки зрения ДПФ последовательность х(n – n0) получается путем кругового сдвига элементов последовательности х(n) на n0 отсчетов Propriétés de symétrie Si une séquence périodique xp(n) avec une période d'échantillons v/V est réelle, alors sa DFT xp(k) satisfait les conditions de symétrie suivantes : Des égalités similaires sont valables pour une séquence réelle finie x(n) ayant une DFT à N points X(k). Si nous introduisons une condition de symétrie supplémentaire pour la séquence xp(n), c'est-à-dire supposons que alors il s'avère que Xp(k) ne peut être que réel. Comme on a le plus souvent affaire à des séquences réelles, en calculant une TFD, on peut obtenir la TFD de deux séquences en utilisant les propriétés de symétrie (6). Considérons des séquences périodiques réelles xp(n) et yp(n) avec des périodes de N échantillons et des DFT à N points xp(k) et Yp(k), respectivement. Introduisons une suite complexe zp(n) de la forme Sa DFT est égale à En isolant les parties réelle et imaginaire de l'égalité (10), on obtient Les parties réelles Xp(k) et Yp(k) sont symétriques et les parties imaginaires sont antisymétriques, elles peuvent donc être facilement séparées à l'aide d'opérations d'addition et de soustraction : Ainsi, en calculant une DFT à N points, il est possible de transformer simultanément deux séquences réelles de longueur N échantillons. Si ces séquences sont également symétriques, alors le nombre d'opérations nécessaires pour obtenir leur DFT peut être encore réduit. Informations connexes. La technique traditionnelle « d’entrée de gamme » consistant à comparer l’image actuelle à une norme est basée sur la visualisation des images comme des fonctions bidimensionnelles de luminosité (matrices d’intensité bidimensionnelles discrètes). Dans ce cas, on mesure soit la distance entre les images, soit une mesure de leur proximité. En règle générale, pour calculer les distances entre les images, on utilise une formule qui est la somme des modules ou carrés des différences d'intensité : L'une des méthodes permettant de réduire considérablement le nombre de calculs est l'utilisation de transformées de Fourier et de transformées de Fourier discrètes pour calculer la mesure de coïncidence de deux images à différents décalages entre elles. Dans ce cas, les calculs sont effectués simultanément pour diverses combinaisons de décalages d'images les uns par rapport aux autres. La présence d'un grand nombre de bibliothèques implémentant les transformées de Fourier (dans toutes sortes de versions rapides) fait de la mise en œuvre d'algorithmes de comparaison d'images une tâche de programmation peu difficile. Note: La transformée de Fourier (ℱ) est une opération qui associe une fonction d'une variable réelle à une autre fonction, également variable réelle. Ce nouvelle fonctionnalité décrit les coefficients (« amplitudes ») lors de la décomposition de la fonction originale en composants élémentaires - vibrations harmoniques avec des fréquences différentes. La transformée de Fourier d'une fonction f d'une variable réelle est intégrale et est donnée par la formule suivante : Différentes sources peuvent donner des définitions qui diffèrent de celles ci-dessus par le choix du coefficient devant l'intégrale, ainsi que par le signe « - » dans l'exposant. Mais toutes les propriétés seront les mêmes, même si l'apparence de certaines formules peut changer. De plus, il existe diverses généralisations de ce concept. La transformation inverse dans ce cas est donnée par la formule : Comme auparavant, dans différentes sources les définitions d'une transformée de Fourier multidimensionnelle peuvent différer dans le choix de la constante avant l'intégrale. Conversion inversée : La transformée de Fourier discrète est une transformation linéaire qui transforme un vecteur d'échantillons temporels en un vecteur d'échantillons spectraux de même longueur. Ainsi la transformation peut être implémentée comme une multiplication symétrique Matrice Carrée au vecteur: Et bien que propriétés similaires inhérent à beaucoup transformations linéaires, pour une utilisation pratique, pour calculer l'opération de convolution, selon notre définition, la formule est utilisée Laisser Logiciel utilisé De la section précédente sur l'échantillonnage des signaux continus, il s'ensuit que les signaux réels peuvent être décrits par des échantillons dans les domaines spectral et temporel. Le spectre discret et le signal discret décrivent complètement le signal continu (continu) d'origine. Cependant, afin de trouver un spectre discret à partir d'un signal discret donné, il est nécessaire d'effectuer des calculs fastidieux : d'abord, reconstruire à partir du signal discret signal continu, puis utilisez la transformée de Fourier pour trouver un spectre continu, puis discrétisez-le. Une procédure similaire doit être suivie pour la conversion inverse. La transition directe d'un signal discret à un spectre discret et vice versa est possible à l'aide d'une transformée de Fourier discrète. Considérons un signal continu de durée finie avec un nombre de degrés de liberté égal à Pour ce signal on peut écrire le développement en série de Kotelnikov : En utilisant conversion normale Trouvons le spectre de Fourier de ce signal : Le calcul direct de l'intégrale dans cette formule est une procédure à forte intensité de main-d'œuvre. Cependant, cela n’est pas difficile à réaliser d’une autre manière. Considérons le spectre qui est déterminé par l'expression En lui appliquant la transformée de Fourier inverse, on constate qu'elle correspond à la fonction temps Évidemment, la relation inverse est également vraie En utilisant le théorème du retard, on peut écrire En remplaçant (3.2) dans (3.1), on obtient l'expression finale du spectre Pour accéder à la transformée de Fourier discrète, les valeurs du spectre dans l'expression (3.3) doivent être calculées non pas pour toutes les valeurs de fréquence, mais pour les valeurs discrètes (échantillonnées) : En conséquence, nous obtenons la formule finale de la transformée de Fourier discrète Les propriétés de la transformée de Fourier discrète sont à bien des égards similaires aux propriétés de la transformée de Fourier conventionnelle. Notons seulement une propriété spécifique, qui peut être appelée la périodicité de la transformée de Fourier discrète. Considérons la valeur déterminée par la formule (3.4) pour où est un entier : Ainsi, la transformée de Fourier discrète est fonction périodique fréquence avec une période égale à Cette propriété est similaire à la propriété de périodicité du spectre des signaux échantillonnés, qui a été discutée au chapitre. 2. Passons maintenant à la dérivation de la transformée de Fourier discrète inverse, qui nous permet de déterminer des échantillons de signal à partir d'échantillons de spectre. Pour ce faire, nous utilisons la transformée de Fourier inverse habituelle On écrit la densité spectrale du signal sous la forme d'une série de Kotelnikov et substituer à l'intégrale de la transformée de Fourier inverse L'intégrale dans l'expression est similaire à l'intégrale calculée précédemment (3.2). En utilisant cette analogie, nous écrivons En remplaçant (3.6) dans (3.5), nous obtenons une expression pour la fonction temps En supposant dans la relation, nous obtenons une formule pour déterminer les valeurs d'un signal discret, c'est-à-dire que nous arrivons à la transformée de Fourier discrète inverse où A prend les valeurs de 0 à Parfois, pour faciliter la notation, en utilisant la propriété de périodicité de la transformée de Fourier discrète, les limites de sommation dans l'expression (3.8) sont modifiées et la transformée de Fourier discrète inverse est écrite sous la forme Pour illustrer, appliquez la transformée de Fourier discrète à une impulsion triangulaire échantillonnée (décrite par cinq valeurs d'échantillon sur la Fig. Remplaçons cette expression du signal discret dans la formule de la transformée de Fourier discrète (3.4) A titre de comparaison, trouvons densité spectrale impulsion triangulaire initiale : Il est facile de voir que le spectre discret (3.11) ne décrit pas avec précision la densité spectrale de l'impulsion triangulaire (3.12). Les valeurs diffèrent légèrement des valeurs correspondantes du spectre d'impulsions triangulaires (Fig. 3.1, b). Remplaçons maintenant les valeurs discrètes du spectre (3.11) dans l'expression de la transformée de Fourier discrète inverse (3.8) : Malgré la différence entre les valeurs du spectre discret et les valeurs du spectre continu, le résultat obtenu coïncide complètement avec la formule du signal discret original (3.11). L'exemple considéré montre que la transformée de Fourier discrète ne décrit pas toujours avec précision le spectre du signal continu d'origine, tout comme Riz. 3.1. Transformée de Fourier discrète d'une impulsion triangulaire échantillonnée le signal échantillonné ne décrit pas toujours avec précision le signal continu d'origine. Cependant, la relation entre un signal discret et sa transformée de Fourier discrète est toujours biunivoque et la formule des transformées de Fourier directe et inverse est stricte pour tout nombre. valeurs discrètes. Par conséquent, l’appareil des transformées de Fourier discrètes a une signification indépendante et peut être appliqué à n’importe quelle séquence numérique. Dans ce cas, les formules de la transformée de Fourier discrète doivent être légèrement modifiées, car pour l'abstrait séquence de nombres Les valeurs de l'intervalle d'échantillonnage et de la durée du signal n'ont aucun sens. Par conséquent, le coefficient devant la somme dans la formule (3.4) est omis, remplacé par les valeurs de référence du signal et du spectre, notées par et la formule de la transformée de Fourier discrète s'écrit sous la forme Dans ce cas, la transformée de Fourier discrète inverse a la forme Les valeurs calculées à l'aide de la formule (3.14) diffèrent d'un facteur des valeurs d'échantillon du spectre d'oscillation continue. Pour déterminer les valeurs d'échantillonnage, vous devez multiplier les valeurs calculées à l'aide de la formule (3.14) par la valeur de l'intervalle d'échantillonnage temporel : Montrons que les transformations (3.14), (3.15) sont mutuellement inverses. Pour ce faire, prenez une séquence numérique arbitraire à l'aide de la transformée de Fourier discrète (3.14), trouvez la séquence et appliquez-lui la transformée discrète inverse Fourier (3.15). Nous notons la séquence résultante Changeons l'ordre de sommation et transformons légèrement cette expression : La somme interne de l'expression (3.16) est égale à zéro si et est égale à si Par conséquent, lorsque c'est-à-dire que les suites de nombres coïncident les unes avec les autres. Ainsi, en appliquant successivement la transformée de Fourier discrète directe et inverse à n'importe quelle séquence numérique, le résultat est la même séquence. Illustrons ce point avec les exemples les plus simples. 1. Considérons le signal discret le plus simple, constitué d'une valeur d'échantillon égale à a. En substituant cette séquence la plus simple à la formule de transformée de Fourier discrète (3.14), nous obtenons ainsi la transformée de Fourier discrète d'un individu valeur numériqueégal à la même valeur. Une autre application importante de la transformée de Fourier discrète est le calcul du signal à la sortie d'un filtre avec une réponse en fréquence donnée. Si un signal d'entrée est donné, alors une transformée de Fourier discrète peut être calculée pour celui-ci. Si nous multiplions maintenant par la réponse en fréquence du filtre, nous obtenons une transformée de Fourier discrète du signal de sortie : après cela, en utilisant la transformée de Fourier discrète inverse. , on peut retrouver le signal en sortie du filtre. Si le signal d'entrée a une longue durée, il peut être traité en utilisant la transformée de Fourier discrète par parties. Pour ce faire, prélevez les N premiers échantillons du signal d'entrée, calculez leur transformée de Fourier discrète et, après multiplication par la réponse en fréquence du filtre, utilisez la transformée de Fourier discrète inverse pour calculer les N premiers échantillons du signal de sortie. Après cela, les N échantillons suivants du signal d'entrée sont traités de la même manière, etc. Pour augmenter la précision du traitement du signal, les séries d'échantillons traitées peuvent se chevaucher partiellement. L'avantage de cette méthode de traitement du signal est l'absence de toute restriction sur le type de réponse en fréquence du filtre. Par exemple, la réponse en fréquence peut avoir une forme rectangulaire parfaite, ce qui ne peut être obtenu avec des filtres conventionnels. Le traitement du signal utilisant la transformée de Fourier discrète ne peut pas être appelé filtrage numérique dans dans tous les sens mots. Les filtres numériques conventionnels fonctionnant en temps réel traitent le signal en continu à mesure qu'il arrive, et le calcul du signal de sortie à l'aide d'une transformée de Fourier discrète ne peut être effectué qu'une fois que l'intégralité du signal d'entrée ou au moins la première série de N échantillons est connue. Par conséquent, lors de l'utilisation de la transformée de Fourier discrète, le signal de sortie ne peut être obtenu qu'avec un certain retard par rapport au signal d’entrée. Cependant, dans un certain nombre Applications pratiques un tel retard du signal de sortie ne joue pas un rôle significatif, et alors le traitement du signal utilisant la transformée de Fourier discrète s'avère approprié.Représentation complexe de la transformée de Fourier.
Transformée de Fourier Rapide.
Transformée de Fourier bidimensionnelle.
Convolution par transformée de Fourier.
Filtrage des images dans le domaine fréquentiel.
d(X,Y) = SOMME (X - Y)^2
Si, en plus d'une simple comparaison de deux images, il faut résoudre le problème de la détection de la position d'un fragment d'une image dans une autre, alors la méthode classique « d'entrée de gamme », qui consiste à énumérer toutes les coordonnées et à calculer en règle générale, la distance utilisant la formule spécifiée échoue dans la pratique en raison du grand nombre de calculs requis. Formulation du problème
Par exemple, recherchez : à l'image
La corrélation comme mesure entre les images
Selon la définition, corrélation
Cette grandeur est bien connue du cours de mathématiques et de géométrie consacré à espaces linéaires, où on l'appelle le produit scalaire. Nous utiliserons la formule comme mesure entre les images : m(X,Y) = SOMME (X * Y) / (SQRT (SOMME X ^2) * SQRT (SOMME Y ^2))
ou m(X,Oui) =
Cette quantité est obtenue à partir de l'opération du produit scalaire de vecteurs (en considérant les images comme des vecteurs dans un espace multidimensionnel). Et plus encore : la même formule est la norme formule statistique critère pour l'hypothèse de la coïncidence de deux distributions de probabilité.
Lors du calcul de la corrélation entre les fragments d'image, si une image est plus petite que l'autre, nous diviserons uniquement par la valeur des normes des parties qui se croisent.Convolution de deux fonctions
D'après la définition, la convolution de deux fonctions F et G est appelée fonction FxG :
Soit G’(t) = G(-t) et F’(t) = F(-t), alors la validité des égalités est évidente :
Il est également évident que FxG'(t) est égal à la corrélation obtenue en déplaçant un vecteur par rapport à un autre par l'étape t (cela peut être facilement vérifié en substituant explicitement les valeurs dans la formule de corrélation). 
Transformée de Fourier multidimensionnelle
La transformée de Fourier des fonctions définies sur l'espace ℝ^n est déterminée par la formule : 
Transformée de Fourier discrète
La transformée de Fourier discrète (dans la littérature anglaise DFT, Discrete Fourier Transform) est l'une des transformées de Fourier largement utilisées dans les algorithmes de traitement du signal numérique (ses modifications sont utilisées en compression audio en MP3, compression d'image en JPEG, etc.), ainsi que dans d'autres domaines liés à l'analyse des fréquences dans un signal discret (par exemple, analogique numérisé). La transformée de Fourier discrète nécessite en entrée fonction discrète. De telles fonctions sont souvent créées par échantillonnage (valeurs d'échantillonnage de fonctions continues). Les transformées de Fourier discrètes aident à résoudre équations différentielles en dérivées partielles et effectuer des opérations telles que la convolution. Les transformées de Fourier discrètes sont également activement utilisées en statistiques, dans l'analyse de séries chronologiques. Il existe des transformées de Fourier discrètes multidimensionnelles. Formules de transformation discrète
Conversion directe : 
Transformations de Fourier pour calculer la convolution
Un des propriétés remarquables La transformée de Fourier est la capacité de calculer rapidement la corrélation de deux fonctions définies, soit sur un argument réel (en utilisant formule classique), ou sur un anneau fini (lors de l'utilisation de transformations discrètes).
Où
Il est assez facile de vérifier l'exactitude de l'égalité - en substituant explicitement les transformées de Fourier dans les formules et en réduisant les formules résultantes Transformations de Fourier pour calculer la corrélation
Puis, comme montré précédemment,
Si les implémentations de l'algorithme de transformation de Fourier sont utilisées via nombres complexes, alors de telles transformations ont une autre propriété remarquable : FFT(G’) = CONJUGUÉ (FFT(G))
Où CONJUGATE (FFT(G)) est une matrice composée d'éléments conjugués de la matrice FFT(G)
Ainsi, nous obtenons Transformations de Fourier pour résoudre le problème
m(X,Y) (je,j) =
nous comprenons ça
Où Simplification des formules pour résoudre le problème
Lors de la résolution du problème de recherche d'un échantillon, une normalisation supplémentaire de l'échantillon n'est pas nécessaire et le calcul de la norme pour la partie commune peut être remplacé par la somme de la luminosité des pixels de cette partie commune ou la somme des carrés de la luminosité dans cette partie commune
Lors de l'utilisation de la formule pour estimer la distance entre les images lorsqu'elles sont décalées (i, j) les unes par rapport aux autres m(X,Y) (je,j) =
nous comprenons ça
Où Algorithme de recherche d'un fragment dans une image complète
Note:
Lorsqu'on utilise la transformée de Fourier discrète, la matrice M contient également des éléments issus du décalage cyclique des images entre elles. Par conséquent, si vous n'avez pas besoin d'analyser le décalage de trame cyclique, recherchez élément maximum dans la matrice M doit être limité à la région (0,0)-(N1-M1, N2-M2). Exemples de mise en œuvre
Les algorithmes implémentés font partie de la bibliothèque open source FFTTools. Adresse Internet : github.com/dprotopopov/FFTTools
///
/// Je t'ai mordu
Littérature
