TIFO - Filtrage - partie 2

Signal

Representation Mathematiques d'un phenomene physique

Traitement du signal

• Elaboration, detection et interpretation des signaux

Classification des signaux

• Morphologique: continu/discret
• Spectrale: Bande de frequence BF/HF
• Energie: Energie finie/Puissance moyenne finie
• Typologie: deterministe/aleatoire
• Periodicite: non peridique/
  $x(t)=x(t+T)$

Energie

• Energie
  $w_x$ d'un signal
  $x$

$$W_x={\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}|x(t){|}^{2}dt$$

• Les signaux a energie finie verifient la condition:

$$W_x={\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}|x(t){|}^2<+\mathrm{\infty }$$

• Les signaux a support borne (cad duree limitee) sont a ernegie finie

Puissance

• Puissance moyenne
  $P$ du signal
  $x$

$$P_x=\underset{T\to +\mathrm{\infty }}{lim}\frac{1}{T}{\int }_{-\frac{T}{2}}^{\frac{T}{2}}|x(t{|}^{2}dt)$$

• Energie finie
  $\Rightarrow$ puissance moyenne nulle

$$W_x<+\mathrm{\infty }\Rightarrow P_x=0$$

• Puissance moyenne finie
  $\Rightarrow$ energie infinie

$$0<P_x<+\mathrm{\infty }\Rightarrow W_x\to +\mathrm{\infty }$$

Ex: les signaux periodiques

Signaux classiques

Porte

$${\mathrm{\Pi }}_{\frac{T}{2}}=\{\begin{array}{ll}1& \text{si }t\in [-\frac{T}{2};\frac{T}{2}]\\ 0& \text{ailleurs}\end{array}$$

Echelon d'Heavyside

$$u(t)=\{\begin{array}{ll}0& \text{si }t<0\\ 1& \text{si }t\ge 0\end{array}$$

Signe

$$sgn(t)=\{\begin{array}{ll}-1& \text{si }t<0\\ 0& \text{si }t=0\\ 1& \text{si }t>0\end{array}$$

Triangulaire

$${\mathrm{△}}_T(t)=\{\begin{array}{ll}\frac{1-|T|}{T}& \text{si }|t|T\\ 0& \text{ailleurs}\end{array}$$

Gaussienne

$$g(t)=\frac{1}{\delta \sqrt{2\pi }}{e}^{-\frac{t^2}{2{\delta }^2}}$$

Sinus cardinal

$$sinc(t)=\frac{sin(t)}{t}$$

Series de Fourier

• On consider les fonctions
  $g_n(t)$

$$g_n(t)=e^{2j\pi \frac{nt}{T}}$$

• Que vaut

$$<g_n(t),g_m(t)>=\frac{1}{T}{\int }_T{g}_n(t)g_m^{\ast }(t)dt=\{\begin{array}{ll}0& \text{si }n\ne m\\ 1& \text{si }n=m\end{array}$$

avec

$g_m^{\ast }$ le conjugue dans les complexe

• Soit
  $f(t)$ periodique de periode
  $T(T>0)$. Un signal 1D periodique peut etre vu comme une somme de sinusoides

$$f(t)=\sum _{n=-\mathrm{\infty }}^{+\mathrm{\infty }}{C}_n{g}_n(t)$$

Comment trouver

$C_i$ ?

$$\begin{array}{rl}\frac{1}{T}\int f(t)g_i^{\ast }(t)dt& =\frac{1}{T}\int (\sum C_n{g}_n(t))\int g_i^{\ast }(t)dt\\ & =\frac{1}{T}\int (...+C_{i-1}{g}_{i-1}(t)+C_i{g}_i(t)+C_{i+1}{g}_{i+1}(t)+...)g_i^{\ast }(t)dt\\ & =\frac{1}{T}\int (...+C_{i-1}{g}_{i-1}(t)g_i^{\ast }(t)+C_i{g}_i(t)g_i^{\ast }(t)+C_{i+1}{g}_{i+1}(t)g_i^{\ast }(t)+...)dt\\ & =...+\frac{1}{T}\int C_{i-1}{g}_{i-1}(t)g_i^{\ast }(t)dt+\frac{1}{T}\int C_i{g}_i(t)g_i^{\ast }(t)+\\ & \frac{1}{T}\int C_{i-1}{g}_{i-1}(t)g_i^{\ast }(t)dt+...\\ & =...+C_{i-1}\underset{=0\text{ car }i-1\ne i}{\underbrace{\frac{1}{T}\int g_{i-1}(t)g_i^{\ast }(t)}}+C_i\underset{=1}{\underbrace{\frac{1}{T}\int g_i(t)g_i^{\ast }(t)}}+C_{i+1}\underset{=0\text{ car }i+1\ne i}{\underbrace{\frac{1}{T}\int g_{i+1}(t)g_i^{\ast }(t)}}\\ & =C_i\end{array}$$

Harmoniques

$C_n$: harmoniques

On les sommes pour obtenir la sinusoides resultat

• $C_0$: frequence continue
• $C_1$: frequence fondamentale
• …
• $C_n$:
  $n^{ieme}$ harmonique
• f reel
  $\Rightarrow$
  $C_n=C_{-n}^{\ast }(f(t)=f^{\ast }(t))$

Frequences

• Basses frequences
  • Lentes variations
  • Zones presque uniformes
• Hautes frequences
  • Variations rapides
  • Contours/coins

Se retrouve dans les images

Quand des details apparaissent, on monte dans les frequences

Series et transformees de Fourier

Spectre

• D'amplitude:
  $|C_n|$
• De phase
  $Arg(C_n)=arctg(-\frac{b_n}{a_n})$
• De puissance
  $|C_n{|}^2$
• $f(t)$ reel
  $\Rightarrow$ spectre d'amplitude symetrique

Relation de PARSEVAL: Il y a conservation de la puissance de la representation temporelle a la representation frequentielle.

On ne perde pas d'information lorsqu'on passe de l'un a l'autre.

Signaux

On considere jusqu'a present des signaux periodiques

• On peut generaliser en prenant
  $T\to +\mathrm{\infty }$

On defini

$TF\{x(t)\}$

$$X(f)={\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}x(t)e^{-2j\pi ft}dt$$

On defini

$T{F}^{-1}\{x(t)\}$

$$x(t)={\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}X(f)e^{+2j\pi ft}df$$

Toutes les infos contenues dans le signal sont contenues dans le spectre

Transformee usuelles

Porte

Transformee de Fourier: Sinus cardinal

Constante

Transformee de Fourier: Fondamentale

Peigne de Dirac

Transformee de Fourier: un autre Peigne de Dirac

Existence de la transformee de

$f(t)$

• $f(t)$ bornee
• Integrale de
  $f(t)dt$ existe
• Les discontinuires de
  $f(t)$ sont en nombre limite

On s'autorisera systematiquement a faire la transformee de Fourier de l'image

Proprietes

• Linearite

$$Kf(t)+g(t)\iff KF(t)+G(t)K\text{ complexe}$$

• Similitude: Une dilatation dans le domaine temporel correspond a une contraction dans le domaine frequentiel
  • $f(at)\iff \frac{1}{|a|}F(\frac{f}{a})$ (a reel)
• Derivee:
  • $\frac{dx(t)}{dt}\iff 2i\mathrm{\Pi }fX(f)$
  • $\frac{dx(f)}{df}\iff -2i\mathrm{\Pi }fX(t)$

Dans notre cas:

• Signal borne et echantillone

Soit le pic de Dirac

$\delta (t)$:

Soit le pic de Dirac

$\delta (t_0)$:

$$\begin{gathered} \delta (t_0)=\delta (t-t_0) \\ f(t)\delta (t_0)=f(t_0) \end{gathered}$$

Soit le peigne de Dirac

$Ш(t)$:

$$\sum _{n=-\mathrm{\infty }}^{+\mathrm{\infty }}\delta (t-nT)$$

$f(t).Ш(t_0)=$

Une fonction echantillonee, c'est une fonction multipliee par un peigne de Dirac.

Transformee de Fourier

Dans notre cas:

• Signal discret (echnatillonne) + support borne
  • Transformee de Fourier Discrete

$$\begin{array}{rlr}& X(f)={\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}x(t)e^{-2j\pi ft}dt& X(f)=\sum _{t=-\mathrm{\infty }}^{+\mathrm{\infty }}x(t)e^{-2j\pi ft}\end{array}$$

$$X(l)=\sum _{k=0}^{N-1}x(k{T}_e)e^{-2j\pi l{f}_{e}k{T}_e}$$

$$\begin{array}{rlr}& X(l)=\sum _{k=0}^{N-1}x(t)e^{\frac{-2j\pi }{N}kl}& X(k)=\sum _{k=0}^{N-1}x(t)e^{\frac{2j\pi }{N}lk}\end{array}$$

Notes

$F_e$ frequence d'echantillonnage

• $X(0)\to -2F_e(/0)$
• $X(N-1)\to +2F_e(/+4F_e)$
• Pas en frequence:
  $F_e/N$

Calcul rapide de la TFD

Fast Fourier Transform (1965 - Cooley et Tukey

$$\begin{array}{rl}X(l)& =\sum _{k=0}^{N-1}x(k)e^{-\frac{2j\pi kl}{N}}\\ & =\sum _{k=0}^{\frac{N}{2}-1}x(2k)e^{-\frac{2j\pi 2kl}{N}}+\sum _{k=0}^{\frac{N}{2}-1}x(2k+1)e^{-\frac{2j\pi 2(k+1)l}{N}}\\ & =\sum _{k=0}^{\frac{N}{2}-1}x(2k)e^{-\frac{2j\pi 2kl}{N}}+e^{-\frac{2j\pi l}{N}}\sum _{k=0}^{\frac{N}{2}-1}x(2k+1)e^{-\frac{2j\pi 2kl}{N}}\end{array}$$

Pour calculer la TFD sur un signal de taille

$N$, on calcul la transformee de Fourier sur les coeeficients pairs

$(\frac{N}{2})$ et la transformee de Fourier sur les coefficients impairs

$(\frac{N}{2})$… et recursivement

Dans notre cas (Image)

• Signal 2D: TF2D (Transformee de Fourier a 2 dimensions)

Visualisation du spectre:

On peut aller de

$-2F_e$ a

$2F_e$

Representation pas pratique car le max d'information se retrouve dispatche aux differents angles.

On interverti les cadrants. Les basses frequences se retrouvent au centre

Resultat:

La convolution

Reponse impulsionnelle ?
Reponse a une impulsion

$\delta (t)$, cad envoyer un pic de Dirac unitqire et recupere la reponse impulsionnelle du filtre h(t).

Cela caracterise le filtre.

On peut en deduire pour n'importe quel signal la sortie du filtre.

La reponse du filtre est donnee par un produit de convolution

$$y(t)=x(t)\times h(t)={\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}x(u)h(t-u)du$$

Reponse impulsionnelle

Si le signal est une serie d'impulsions ?

1. On calcule la reponse du filtre a la 1
   ${}^{ere}$ impulsion
2. On calcule la reponse de la seconde impulsion
3. De meme pour la 3
   ${}^{eme}$

Par le principe de supperposition, les reponses s'additionnent

C'est ce qu'on fait lors du produit de convolution.

Proprietes

• Commutative:
  $f(t)\ast g(t)=g(t)\ast f(t)$
• Distributive:
  $(x(t)+y(t))\ast g(t)=x(t)\ast g(t)+y(t)\ast g(t)$
• Associative:
  $(x(t)\ast y(t))\ast z(t)=x(t)\ast (y(t)\ast z(t))$

Theoreme de Plancherel

Temps	Frequences
Convolution $\ast$	Multiplication $.$
Multiplication $.$	Convolution $\ast$

Autre propriete

$$f^{\prime }\ast g=f\ast g^{\prime }=(f\ast g{)}^{\prime }$$

Consequences du lien convolution

$\leftrightarrow$ multiplication

• Spectre d'un signal echantillonee
• Revisite du filtrage
  • Passe haut
  • Passe bas
  • Passe Bande
  • Rejecteur
• Deconvolution

Autres consequences:

• DoG - Difference de gaussiennes
• LoG - Laplacien d'une gaussienne

Spectre d'un signal echantillonne:

$f(t)Ш(t_0)=$

Dans le domaine frequentiel:

La TF du peigne de Dirac est un autre peigne de Dirac plus espace

Le signal se repete a l'infini, on n'a besoin de connaitre qu'un espace

Revisite du filtrage

Passe haut / Passe Bas/ Passe Bande / Rejecteur

1. On a un signal qu'on veut filtrer pour enlever le bruit
2. On passe en frequenciel et on a le spectre du signal
   • Les hautes frequences sont du bruit
3. On defini un signal pour les enlever
   • 1 sur toutes les basses frequences
   • 0 partout ailleurs
   • On multiplie les 2
4. On obtient le spectre supprime de toutes les bases frequences
5. On fait l'inverse de la TF et on obtient le signal sans les hautes frequences

En pratique, est-ce qu'on fait tout ca ?
Non.

On peut faire l'inverse

1. Prendre le filtre defini
2. Faire l'inverse et de le passer en temporel
   • en temporel, la porte devient un sinus cardinal
3. Convoluer le filtre avec le signal
4. On obtient notre signal filtre

Autre consequence

Convolution

• $f^{\prime }=f\ast h\Rightarrow F\times H=F^{\prime }$

Deconvolution

• $\frac{F^{\prime }}{H}=F\to$ domaine temporel
  • Tres difficile si on ne connait pas le filtre initial
  • Probleme des 0 (ou des valeurs tres petites dans
    $H$)

Si on floute le visage de quelqu'un pour anonymat avec un filtre gaussien, on peut arriver a deconvoluer et retrouver le visage d'origine (tres difficile en pratique)

Il faudrait mettre un gros carre noir et non flouter le visage

Detection de bord

• (
  $f\ast$ gauss)'
  $\to f\ast$guass' (la derivee de la gaussien est connue formellement)
  • Realise a la fois le lissage et la derivee

LoG

• Laplacient d'une gaussienne

Dog

• Difference de gaussienne

Filtrage

• Passe Bas
  • Description
    • Coef central superieur ou egal aux autres
    • Autres coefs positifs
  • Effet
    • Pixel central devient une moyenne ponderee des voisins
    • Les regions homogenes sont peut changees
    • Les frontieres sont etalees
    • Reduit le bruit
• Passe Haut
  • Description
    • Coef central positif et eleve
    • Autres coefs petits, negatifs ou nuls
    • La somme des coefficients est nulle
  • Effet
    • Zones homogenes: perte de la notion d'intensite
    • Frontieres sont renforcees

Proprietes de la TF2D

Le module de l'image ne change pas

Le module change mais la phase est invariante a la rotation

Impact du flou

Cela veut dire que les hautes frequences sont reduites/degradees.

Si on bouge, on a un flou directionnel, cad on a preserve l'information dans un sens et perdu dans l'autre.

Skew estimation

Application:
On a un document qui passe dans un scanner, il n'est pas forcement droit et on veut corriger l'orientation.

On voit la rotation dans le spectre et on refait une transformee de Fourier.

On peut estimer l'orientation du fichier d'origine.

Autres transformations

• Short Term Fourier Transform
• Discret Cosinus Transform
• Ondelettes
• Radon
• Wigner
• Hilbert
• …

Transformee en cosinus discrete

On fait la transformee de Fourier sur une base de sinusoide reel (utilise en JPEG)

Probleme

• definiton varie d'un ouvrage a un autre
• Pour le JPEG, l'encodeur et le decodeur peuvent utiliser une transformee differente

Short Term Fourier Transform

• probleme:
  • FT: soit le temps, soit la frequence
• Solution: ne considerer que des petits intervalles

$$X(f,t^{\prime })={\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}x(t)w^c(t-t^{\prime })e^{-2j\pi t}dt$$

• Impact de la taille de w
  • W etroit
    $\Rightarrow$ localisation temporelle correcte mais mauvaise resolution frequentielle
  • W large
    $\Rightarrow$ localisation temporelle imprecise mais bonne resolution frequentielle

Transformee en ondelettes

• Avantages:
  • FT: soit le temps, soit la frequence
  • STFT: diffculte de regler la taille de w et taille fixee une fois pour toutes
  • Transformee en ondelette:
    • Representation temps-frequence
      • la frequence avec sa position spatiale
    • Adaptation de la resolution en fonction de la frequence
      • Basses frequence
        $\to$ Privilegie la resolution frequentielle
      • Hautes frequence
        $\to$ Privilegie la resolution temporelle
    • analyse des signaux non stationnaires

Definition:

$$\begin{gathered} {\mathrm{\Psi }}_x^{\psi }(\tau ,s)=\frac{1}{\sqrt{|s|}}\int x(t){\psi }^c(\frac{t-\tau }{s})dt \\ {\mathrm{\Psi }}_x^{\psi }(\tau ,s)=\int x(t{\psi }_{\tau ,s}^c)(t)dt \\ {\psi }_{(\tau ,s)}=\frac{1}{\sqrt{|s|}}\psi (\frac{t-\tau }{s}) \end{gathered}$$

Exemples

• Haar
• Mexican Hat
• Morlet

Usage

• Compression
• Filtrage
• Approximation
• …