chap2.tex 17.6 KB
Newer Older
1 2 3 4 5 6 7
\documentclass[main.tex]{subfiles}

\begin{document}
\newcommand{\Y}{\mathcal{Y}}
\newcommand{\X}{\mathcal{X}}
\section{Introduction}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
\begin{defin}
  \begin{itemize}
  \item La \emph{quantification} est une génération non réversible qui permet à
    une source $X$ à valeur dans $\X$ d'associer un index $I\in\{0,...M-1\}$ ou
    $M$ est le nombre de cellule de quantification. La
  \item \emph{quantification inverse} consiste à associer une estimée $\hat{X}$ de $X$ à valeur dans $\X$ à un index $I$.
  \item
Pour cela on introduit une fonction de quantification :

\[
  q :\X \to \{0,...,M-1\}
\]
et des fonction de quantification inverse:
\[
  r :\{0,...,M-1\} \to \X
\]
\item Pour une réalisation $x$ de $\X$,$i = q(x)$ est l'index de quantification.
  \[
    \hat{x}= r(q(x)) = Q(x)
  \]
  est la valeur reconstruite/quantifiée.
  \end{itemize}
\end{defin}
\begin{rem}
  Si $\X = \N $ ou $\Z$ ou $\R$ on réalise une quantification vectorielle. Si $\X =\R^n$ on réalise une quantification vectorielle.
\end{rem}
34

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
35
Les quantifications sont optimisées de manière à obtenir un débit minimale sous contrainte de distortion ou bien une distortion minimale sous contrainte de débit. La distorsion étant une mesure de l'erreur entre $X$ et $\hat{X}$.
36

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
37
Un quantificateur est défini par des intervalles de quantification $b_0 < b_1 < ... < b_n$ et par des valeurs de reconstitution $y_1,...,y_n$ : si on a $x \in[b_{i-1} ; b_i[$ alors $Q(x) = y_i$.
38
Dans la suite, on va voir comment régler de façon efficace les $b_i$ et les $y_i$.
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
39 40 41 42 43 44 45 46 47 48 49 50 51 52
\section{Distorsion et mesure de distorsion}
\begin{defin}

  On introduit une mesure de distorsion pour les performances d'un quantificateur qui toute les bonnes propriétés d'une distance symétrique, définie positive). Les principales mesures considérées sont:
  \begin{itemize}
  \item la mesure de distorsion en valeur absolue, $d(x,y) = |x-y|$
  \item la mesure de distorsion quadratique, $d(x,y) = (x-y)^2$
  \item le mesure de distorsion de Hamming, $d(x,y) =
    \begin{cases}
      0 & \text{ si } x=y \\
      1 & \text{ sinon}
    \end{cases}$
  \end{itemize}
\end{defin}
53 54

Pour une source $X$ décrite par une distribution de probabilité $f_X(x)$, la distorsion introduite par un quantificateur $Q(x)$, est la moyenne de la mesure de la distorsion:
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
55
\[D = \int_{-\infty}^{\infty} d(x,Q(x))f_X(x) dx  = E(d(X,Y))\]
56 57 58
Pour la mesure de distorsion quadratique, on a:
\[D = \int_{-\infty}^{\infty} (x-Q(x))^2f_X(x) dx \]

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
59 60
\section{Quantification scalaire}
\subsection{Quantification uniforme d'une source uniforme}
61 62 63 64

On considère une source $X$ uniformément distribuée sur $[-X_{max} ; X_{max}]$. On considère aussi un quantificateur uniforme, c'est à dire que les intervalles de quantification sont tous de même taille, à M niveaux de sortie, situés au milieux des intervalles de quantification.
Prenons par exemple, un quantificateur à 4 niveaux de quantification:
%\img{0.5}{2/1/2.png}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
\begin{center}
  \begin{tikzpicture}
    \begin{axis}
      [axis lines =middle,
      xmin=-3,xmax=3,
      ymin=-2,ymax=2,
      xtick={-2,-1,1,2},
      ytick={0.5,1.5},
      xticklabels={$-X_m$,$-\frac{X_m}{2}$,$\frac{X_m}{2}$,$X_m$},
      yticklabels={$\frac{X_m}{4}$,$\frac{3X_m}{4}$},
      ]
      \addplot[black] plot coordinates {(-2,-1.5) (-1,-1.5)};
      \addplot[black] plot coordinates {(-1,-0.5) (0,-0.5)};
      \addplot[black] plot coordinates {(0,0.5) (1,0.5)};
      \addplot[black] plot coordinates {(1,1.5) (2,1.5)};
80

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
      \addplot[black,dashed] plot coordinates {(-1,-1.5) (-1,-0.5)};
      \addplot[black,dashed] plot coordinates {(1,0.5) (1,1.5)};
    \end{axis}
  \end{tikzpicture}%
  \begin{tikzpicture}
    \begin{axis}
      [axis lines =middle,
      xmin=-3,xmax=3,
      ymin=-0.7,ymax=0.7,
      xtick={-2,-1,1,2},
      ytick={0.5},
      xticklabels={$-X_m$,$-\frac{X_m}{2}$,$\frac{X_m}{2}$,$X_m$},
      yticklabels={$\frac{X_m}{4}$},
      ]
      \addplot[black] plot coordinates {(-2,-0.5) (-1,0.5)};
      \addplot[black] plot coordinates {(-1,-0.5) (0,0.5)};
      \addplot[black] plot coordinates {(0,-0.5) (1,0.5)};
      \addplot[black] plot coordinates {(1,-0.5) (2,0.5)};
      \addplot[black,dashed] plot coordinates {(-1,-0.5) (-1,0.5)};
      \addplot[black,dashed] plot coordinates {(1,-0.5) (1,0.5)};

    \end{axis}
  \end{tikzpicture}
\end{center}
105 106 107
On note $\Delta$ l'intervalle de quantification, dans ce cas, $\Delta = \frac{2 X_{max}}{M}$.\\

Pour déterminer la distorsion qui va être introduite par le quantificateur, on calcule simplement:
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
108

109 110 111
\begin{align*}
D &= \int_{-X_{max}}^{X_{max}}\frac{1}{2X_{max}}(x-Q(x))^2 dx
\intertext{Comme $Q(x)$ est connu et constant sur un intervalle de quantification, on découpe simplement l'intervalle en sous-intervalles de quantification:}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
112
D &= \sum_{i=0}^{(M-1)} \int_{i\Delta}^{(i+1)\Delta} \frac{1}{2X_{max}}(x-(i+\frac{1}{2})\Delta)^2 dx
113
\intertext{On calcule}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
114 115
    I & = \int_{i\Delta}^{(i+1)\Delta} (x-(i+\frac{1}{2})\Delta)^2  \frac{1}{2X_{max}} dx \\
  \intertext{on pose $u = x+X_{max}-(x+\frac{1}{2})\Delta)$}
116 117 118
& = \int_{-\Delta/2}^{\Delta/2} \frac{u^2}{2X_{max}} du \\
I & = \frac{\Delta^3}{24X_{max}} = \frac{X_{max}^2}{3M^3}
\end{align*}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
119

120 121 122 123 124 125 126 127 128
Dans $D$, on a $M$ intégrales égales à $I$ donc \[ D = \frac{X_{max}^2}{3M^2}\]

L'énergie de la source est mesurée par sa variance
\begin{align*}
\sigma^2 & = \int_{-\infty}^{+\infty} x^2 f(x) dx \\
& = \int_{-X_{max}}^{X_{max}} \frac{x^2}{2X_{max}} dx \\
\sigma^2 & = \frac{X_{max}^2}{3}
\end{align*}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
129 130 131
On obtient donc $D = \frac{\sigma^2}{M^2}$.
\begin{prop}
Sans codage entropique, le nombre de bits nécessaires pour représenter un niveau de reconstruction est $R = \lceil \log_2 M \rceil $, d'où
132 133
\[ \boxed{ D = \sigma^2 2^{-2R} } \]

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
134
\end{prop}
135 136 137 138 139 140 141 142 143 144 145 146 147 148
La distorsion maximale est égale à l'énergie de la source, et diminue très rapidement quand on augmente le nombre de bits du quantificateur.

\begin{rem}
Dans certains cas (source non uniforme), un codage entropique peut permettre de réduire le débit.
\end{rem}

Rapport signal à bruit :
\begin{align*}
RSB & = \frac{\sigma^2}{D} = 2^{2R} \\
RSB_{dB} & = 10\log_{10}(2^{2R}) = 6.02R \text{decibel}
\end{align*}

Le $RSB$ est utilisé comme mesure de qualité en audio, image...

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
149 150 151 152 153 154 155 156 157 158 159 160
\begin{center}
  \begin{tikzpicture}
    \begin{axis}
      [axis lines = middle,
      xmin=0,xmax=5,ymin = 0,ymax=8,
      xlabel=$R$(bits),
      ylabel=$\sigma_x^2$,
      ytick={0.5,2,8},
      yticklabels={$D/16$,$D/4$,$D$},
      ]
      \addplot[red,mark=+,samples at={0,1,2,3,4,5}] {2^(-2*(x-1.5)};
      \addplot[gray, dashed,no marks,xcomb,samples at={0,1,2,3,4,5}] {2^(-2*(x-1.5)};
161

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
162 163 164 165
    \end{axis}
  \end{tikzpicture}
\end{center}
La pente a l'origine est de $-2\ln(2)\sigma_x^2$. La distorsion décroit très vite avec $R$
166

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
167
On peux aussi tracer la courbe distortion- débit (R= f(D))
168 169


Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
170
\subsection{Quantification uniforme d'une source quelconque}
171

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
172
On considère une source $X$ décrite par sa ddp $f_X(x)$, quantifiée par un quantificateur uniforme à $M$ niveaux de pas $\Delta$. Si $M$ est fini on peux considérer deux type de quantificateur:
173

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
\begin{figure}[H]
  \centering
  \begin{subfigure}{0.5\textwidth}
  \begin{tikzpicture}
    \begin{axis}
      [axis lines =middle,
      xmin=-3,xmax=3,
      ymin=-3,ymax=3,
      xtick={-2,-1,1,2},
      ytick={-1.5,-0.5,0.5,1.5},
      xticklabels={$-2\Delta$,$-\Delta$,$\Delta$,$2\Delta$},
      yticklabels={$-3\frac{\Delta}{2}$,$\frac{\Delta}{2}$,$\frac{\Delta}{2}$,$3\frac{\Delta}{2}$},
      ]
      \addplot[black, jump mark left]coordinates {(-2,-1.5)
        %(-1,-1.5)
      (-1,-0.5)
      (0,0.5)
      (1,1.5) (3,1.5)};
    \end{axis}
  \end{tikzpicture}
  \subcaption{Quantificateur sans zone morte}
\end{subfigure}%
  \begin{subfigure}{0.5\textwidth}
  \begin{tikzpicture}
    \begin{axis}
      [axis lines =middle,
      xmin=-3,xmax=3,
      ymin=-3,ymax=3,
      xtick={-3,-2,-1,1,2,3},
      ytick={-2.5,-1.5,1.5,2.5},
      xticklabels={$-d-2\Delta$,$-d-\Delta$,$-d$,$d$,$d+\Delta$,$d+2\Delta$},
      yticklabels={$-d-3\frac{\Delta}{2}$,$-d-\frac{\Delta}{2}$,$d+\frac{\Delta}{2}$,$d+3\frac{\Delta}{2}$},
      x tick label style={yshift={mod(\ticknum,2)*1.5em}},
      y tick label style={xshift={3em}}
      ]
      \addplot[black,thick, jump mark left]coordinates {(-3,-2.5)
        %(-1,-1.5)
        (-2,-1.5)
        (-1,0)
      (1,0.5)
      (2,1.5) (3,2.5)};
    \end{axis}
  \end{tikzpicture}
  \subcaption{Quantificateur avec zone morte}
\end{subfigure}
\end{figure}
220

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
221 222

On considère une source $X$ discrète décrite par une ddp $f_X(x)$. On cherche le quantificateur non-uniforme à $M$ niveaux de sortie qui minimise la distorsion de quantification pour une norme de distorsion quadratique.\\
223 224

On cherche à minimiser la distorsion
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
225 226 227 228 229 230 231 232 233 234 235 236
\[ D = \int_{-\infty}^{+\infty} (x-Q(x))^2f_X(x)dx \]

\begin{align*}
D &= \underbracket{\int_{-\infty}^{(-M/2+1)\Delta} (x-Q(x))^2f_X(x)dx }_{\text{distorsion de surcharge}}\\
  &+ \underbracket{\sum_{i=1}^{M-2} \int_{-\frac{M}{2}\Delta+i\Delta}^{-\frac{M}{2}\Delta+(i+1)\Delta}}_{\text{distorsion de granularité}} (x-Q(x))^2f_X(x)dx \\
  &+\underbracket{\int_{(\frac{M}{2}-1)\Delta}^{+\infty} (x-Q(x))^2f_X(x)dx}_{\text{distorsion de surcharge}}\\
\end{align*}

Pour M fixé on a :



237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426

Les conditions nécessaires pour avoir $D$ minimale sont :
\begin{itemize}
\item $\derivp[D]{y_i} = 0, \forall i=1\dots M$
\item $\derivp[D]{b_i} = 0, \forall i = 0\dots M$
\end{itemize}

\begin{align*}
\intertext{1ère condition d'optimalité}
\derivp[D]{y_i} & = \derivp{}{y_i} \int_{b_{i-1}}^{b_i} (x-y_i)^2 f_X(x) dx \\
& = - 2 \int_{b_{i-1}}^{b_i} (x-y_i) f_X(x) dx
\intertext{Ainsi,}
\derivp[D]{y_i} = 0 & \Leftrightarrow \int_{b_{i-1}}^{b_i} xf_X(x)dx = y_i \int_{b_{i-1}}^{b_i} f_X(x)dx \\
& \Rightarrow y_i = \frac{\int_{b_{i-1}}^{b_i} xf_X(x)dx}{\int_{b_{i-1}}^{b_i} f_X(x)dx}, \quad i = 1 \dots M
\intertext{2ème condition d'optimalité}
\derivp[D]{b_i} & = \derivp{}{b_i} \int_{b_i}^{b_{i+1}} (x-y_{i+1})^2f_X(x)dx + \derivp{}{b_i}\int_{b_{i-1}}^{b_i} (x-y_i)^2 f_X(x)dx \\
& = -(b_i-y_{i+1})^2 f_X(b_i) + (b_i-y_i)^2 f_X(b_i)
\intertext{Ainsi, }
\derivp[D]{b_i} = 0 & \Leftrightarrow -(b_i-y_{i+1})^2 + (b_i-y_i)^2 = 0 \\
& \Leftrightarrow (y_{i+1}-y_i)(b_i-y_{i+1}+b_i-y_i) = 0 \\
& \Leftrightarrow b_i = \frac{y_i+y_{i+1}}{2}, \quad i=1 \dots M-1
\end{align*}

\newpage
\subsection*{Algorithme de Lloyd -Max}
\begin{enumerate}
\item Initialisation : $b_0^{(0)} < b_1^{(0)} < \dots < b_n^{(0)}$ choisis arbitrairement, $k=1$.
\item $y_i^{(k)}$ obtenus à partir des $b_i^{(k-1)}, i=0 \dots M$ en utilisant la 1ère condition d'optimalité
\item $b_i^{(k)}$ obtenus à partir des $y_i^{(k)},i=1 \dots M$ en utilisant la 2ème condition d'optimalité
\item $k=k+1$
\item tant qu'il y a des variations des $y_i$ ou des $b_i$, aller en 2.
\end{enumerate}

\begin{rem}
Essayer d'implémenter l'algorithme de Lloyd-Max à l'aide de Matlab, C ou Python pour les fétichistes. Pour Matlab, utiliser la fonction \texttt{quad} afin de calculer les intégrales. Prendre une ddp gaussienne.

Essayer de retrouver ceci pour $M=4$ et $\sigma = 1$
\begin{center}
\begin{tabular}{ccc}
$i$ & $b_i$ & $y_i$ \\ \hline
1 & -0.98 & -1.51 \\
2 & 0 & -0.45 \\
3 & 0.98 & 0.45 \\
4 & $+\infty$ & 1.51 \\
\end{tabular}
\end{center}

Prendre l'infini égal à 10.
\end{rem}

\begin{rem}
On ne quantifie jamais sur le domaine des pixels, car les ddp y sont immondes. On effectue des transformées, et ensuite les ddp sont sympa (gaussiennes, laplaciennes), ce qui permet d'avoir des algorithmes efficaces.

La plupart du temps, les quantifications sont uniformes (JPEG, JPEG200, H264...). On n'utilise des quantifications non uniformes que dans le cas d'applications très précises, où le gain de 2 ou 3 dB sur le $RSB$ est vraiment nécessaire.
\end{rem}

\newpage
\section{Comportement asymptotique}
Pour étudier le comportement asymptotique d'un quantificateur, on suppose $M$ grand (les intervalles de quantification seront petits), $f_X(x) \approx f_X(y_i)$ sur $[b_{i-1},b_i]$. On note $\Delta_i = b_i - b_{i-1}$.\\

On a \[P_i = Pr(X\in[b_{i-1},b_i]) \approx f_X(y_i)\Delta_i\]

\begin{align*}
D & = \sum_{i=1}^M \int_{b_{i-1}}^{b_i} (x-y_i)^2 f_X(x) dx \\
D & = \sum_{i=1}^M f_X(y_i) \int_{b_{i-1}}^{b_i} (x-y_i)^2dx
\intertext{On suppose que $y_i$ est au milieu de l'intervalle $[b_{i-1},b_i]$}
\int_{b_{i-1}}^{b_i} (x-y_i)^2 dx & = \int_{-\Delta_i/2}^{\Delta_i/2} u^2 du = [\frac{u^3}{3}]_{-\Delta_i/2}^{\Delta_i/2} = \frac{2}{3} \frac{\Delta_i^2}{8} = \frac{\Delta_i^3}{12}
\intertext{En réinjectant dans $D$, on a}
D & = \sum_{i=1}^M f_X(y_i) \frac{\Delta_i^3}{12}
\intertext{On pose $\alpha_i^3  = f_X(y_i)\Delta_i^3$}
D & = \frac{1}{12} \sum_{i=1}^M \alpha_i^3
\intertext{Si on calcule}
\sum_{i=1}^M \alpha_i & = \sum_{i=1}^M (f_X(y_i))^{1/3} \Delta_i \approx \int_{-\infty}^{+\infty} (f_X(x))^{1/3} dx = cste
\intertext{On doit trouver les $\Delta_i$ et les $\alpha_i$ qui minimisent $D$ sous la contrainte $\sum_{i=1}^M \alpha_i = C$. On introduit donc le Lagrangien du problème :}
L(\alpha_1,\dots\alpha_M,\lambda) & = \frac{1}{12}\sum_{i=1}^M\alpha_i^3 + \lambda (\sum_{i=1}^M \alpha_i - C)
\intertext{Condition d'optimalité :}
\derivp[L]{\alpha_i} = 0 & \Rightarrow \frac{1}{4}\alpha_i^2 + \lambda = 0, \quad i = 1 \dots M \\
& \Rightarrow \alpha_i^2 = -4\lambda
\intertext{Les $\alpha_i$ sont donc tous égaux, d'où}
\alpha_i & = \frac{1}{M} \int_{-\infty}^{+\infty} (f_X(x))^{1/3} dx
\end{align*}
\newpage
On avait $\alpha_i^3 = f_X(y_i) \Delta_i^3$. Ainsi, si $f_X(y_i)$ est grand, $\Delta_i$ est petit, et inversement.

%\img{0.5}{2/2/1}

On peut donc calculer la distorsion :
\begin{align*}
D & = \frac{1}{12} \sum_{i=1}^M \frac{1}{M^3}(\int_{-\infty}^{+\infty} (f_X(x))^{1/3}dx)^3 \\
& = \frac{1}{12} (\int_{-\infty}^{+\infty} (f_X(x))^{1/3}dx)^3.\frac{1}{M^2}
\intertext{Or, $M=2^R$ d'où}
D & = \frac{1}{12}(\int_{-\infty}^{+\infty} (f_X(x))^{1/3}dx)^3.2^{-2R}
\end{align*}

\begin{rem}
Comme pour la quantification uniforme, on a une décroissance en $2^{-2R}$ de la distorsion en fonction du débit. Ici, il y a un facteur multiplicatif qui dépend de la ddp de la source.

Pour une source quelconque, le comportement débit / distorsion sera :
\[ \boxed{ D(R) = \epsilon_X \sigma_X^2 2^{-2R} \text{ avec } \epsilon_X = \frac{1}{12\sigma_X^2}(\int_{-\infty}^{+\infty} (f_X(x))^{1/3}dx)^3 } \]
\end{rem}

\section{Quantification vectorielle - Algorithme de Linde-Buzo-Gray}

Avec une quantification vectorielle on considère des vecteurs de $N$ échantillons de la source que l'on va représenter à l'aide d'un index de quantification.

%\img{0.5}{2/2/2}

Pour un couple (poids, taille), on peut :
\begin{itemize}
\item quantifier indépendamment le poids et la taille avec deux quantificateurs scalaires
\item les quantifier simultanément avec une quantification vectorielle
\end{itemize}

\subsection*{Algorithme de Linde-Buzo-Gray}

\newcommand{\x}{\underline{x}}
Cet algorithme permet de fabriquer une quantification vectorielle optimale (optimum local) pour un ensemble de $K$ points de $\R^N$ : $\x_1 \dots \x_K$ et quantifiés sur $M$ niveaux.

\newcommand{\y}{\underline{y}}
Pour cela, on introduit la mesure de distorsion $d(\x,\y) = \frac{1}{N}||\x-\y||^2$.

Le quantificateur va minimiser la distorsion.\\

Initialisation :
\begin{itemize}
\item On sélectionne $M$ points $\y_1^{(0)},\dots,y_M^{(0)}$ parmi les $\x_1,\dots,\x_K$ au hasard.
\item $l=0, D_l = + \infty$
\end{itemize}

\begin{enumerate}
\item On réalise une quantification de $\x_1,\dots,\x_K$ en se servant de $\y_1^{(l)},\dots,\y_M^{(l)}$.
\[ q(\x_i) = \y_j \text{ ssi } ||\x_i-\y_j^{(l)}||^2 \leq ||\x_i-\y_k^{(l)}||^2, \quad \forall k\neq j\]

\newcommand{\Cc}{\mathcal{C}}

On obtient une partition de l'espace en cellules de quantification $\Cc_j^{(l)},j=1,\dots,M$ appelées cellules de Voronoï.

%\img{0.5}{2/3/1}

\item On calcule la distorsion :
\[ D^{(l+1)} = \frac{1}{K} \sum_{i=1}^K ||\x_i-q(\x_i)||^2 \]

\item Actualisation des valeurs de reconstruction. On considère l'ensemble des points appartenant à \[\Cc_j^{(l)} = \{ \x_1^{(l)},\dots, \x_{K_l}^{(l)} \}, \quad j = 1,\dots,M\]

On calcule le barycentre des points de $\Cc_j^{(l)}$ qui constitue la nouvelle valeur de reconstruction.

\[\y_j^{(l+1)} = \frac{1}{K_l} \sum_{i=1}^{K_l} \x_i^{(l)} \]

\item $l=l+1$

\item Aller en 1 tant que $D^{l-1} - D^l > \epsilon$

\end{enumerate}

L'algorithme LBG converge vers une minimum local de la distorsion.

\newcommand{\Cc}{\mathcal{C}}
En pratique :
\begin{itemize}
\item on transmet pour chaque $\x_i$ l'index $j$ de la cellule de Voronoi  $\Cc_j$ auquel il appartient.
\item il faut transmettre au récepteur l'ensemble des points de reconstruction $\y_1^{(\overline{l})},\dots,\y_M^{(\overline{l})}$$\overline{l}$ est l'index final des itérations.
\item la phase de réglage du quantificateur peut se faire sur seulement $L<<K$ points si on a beaucoup de points.
\end{itemize}

\newpage
\section{Quantification scalable}

L'objectif est de permettre une flexibilité en terme de compression débit-distorsion. Une possibilité est d'avoir recours à un quantificateur scalable.\\

On considère une source uniforme sur $[-X_{max};X_{max}]$ quantifiée sur 8 niveaux.

%\img{0.5}{2/3/2}

Si on a $K$ échantillons à quantifier, on obtient $3K$ bits.\\

Les $K$ bits de poids fort sont placés dans un premier paquet.

Les $K$ bits de poids intermédiaire sont placés dans un second paquet.

Les $K$ bits de poids faible sont placés dans un troisième paquet.\\

Des utilisateurs disposant d'un mauvais canal recevront le premier paquet : la distorsion sera élevée.

Des utilisateurs disposant d'un excellent canal recevront les 3 paquets et auront une distorsion faible.\\

\begin{rem}
Cette méthode permet de réaliser une quantification sans avoir à connaître l'état du canal.
\end{rem}

\end{document}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
427 428 429 430 431

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% End: