$K = $ 7
La première étape consiste à décomposer chaque bloc dans la base cosinus :
\[ G_{p,q}[n,m] = \lambda_p \lambda_q \frac{1}{4} \cos\left(\frac{\pi p}{8}\left(n+\frac{1}{2}\right)\right) \cos\left(\frac{\pi q}{8}\left(m+\frac{1}{2}\right)\right). \]Lemme : Cette famille forme une base orthonormale de $\mathbb{R}^{8\times 8}$.
$$\begin{align*} \langle G_{p, q}, G_{p', q'} \rangle &= \frac{\lambda_p\lambda_q\lambda_{p'}\lambda_{q'}}{16}\sum_{n=0}^7 \sum_{m=0}^7 G_{p, q}[n, m]G_{p', q'}[n, m] \\ &=\frac{\lambda_p\lambda_q\lambda_{p'}\lambda_{q'}}{16} \underbrace{\left(\sum_{n=0}^7 \cos\!\left(\frac{\pi p}{8}\!\left(n + \tfrac{1}{2}\right) \right)\cos\!\left( \frac{\pi p'}{8}\!\left(n + \tfrac{1}{2}\right)\right)\right)}_{\gamma_{p, p'}} \\ &\quad \times \left(\sum_{m=0}^7 \cos\!\left(\frac{\pi q}{8}\!\left(m + \tfrac{1}{2}\right) \right)\cos\!\left( \frac{\pi q'}{8}\!\left(m + \tfrac{1}{2}\right)\right)\right) \end{align*}$$Montrons maintenant que $\gamma_{p, p'}=\delta_{p, p'}$. On pose $d_- = p-p'$ et $d_+=p+p'$.
$$ \gamma_{p, p'} = \frac{1}{2} \sum_{n=0}^7 \left[ \cos\left(\frac{\pi d_+}{8}(n+\frac{1}{2})\right)+ \cos\left(\frac{\pi d_-}{8}(n+\frac{1}{2})\right) \right] = S(d^+) + S(d^{-}) $$Avec
$$\begin{align*} S(d^+)&=\frac{1}{2} \mathcal{R}\left( \sum_{n=0}^{7}\exp\left(i\frac{\pi d^+}{8}(n + \frac{1}{2})\right) \right) \\ &= \frac{1}{2}\mathcal{R}\left( e^{i\pi d^+/16} \frac{1 - (-1)^{d^+}}{1 - e^{i\pi d^+ /8}} \right) \end{align*}$$Si $d^+=0$ ($p=p'=0$) alors $S(d^+)=4$ et $d^-=0$ donc $S(d^-)=4$. Si $d^+$ est pair non nul alors $S(d^+)=0$ et si $d^+$ est impair :
$$\begin{align*} S(d^+)&= \frac{1}{2}\mathcal{R}\left( e^{i\pi d^+/16} \frac{2}{1 - e^{i\pi d^+ /8}} \right) \\ &= \frac{1}{2}\mathcal{R}\left( \frac{1}{i \sin\left(\frac{\pi d^+}{16}\right)} \right) \\ &= 0 \end{align*}$$On en conclu que $S(d^+)= 4\delta_{p, 0}\delta_{p', 0}$. Par les même calculs, on en vient à $S(d^-)=4\delta_{p, p'}$. D'où :
$$\begin{align*} \langle G_{p, q}, G_{p', q'}\rangle &=\frac{\lambda_p\lambda_q\lambda_{p'}\lambda_{q'}}{16} \gamma_{p, p'} \cdot \gamma_{q, q'} \\ &=\lambda_p\lambda_q\lambda_{p'}\lambda_{q'} (\delta_{p, 0}\delta_{p', 0} + \delta_{p, p'})(\delta_{q, 0}\delta_{q', 0} + \delta_{q, q'}) \\ &= \begin{cases} 0 \quad\text{si}\quad p \neq p' \\ 1 \quad\text{si}\quad p = p' \neq 0 \\ \left(\frac{1}{\sqrt{2}}\right)^2\cdot2\cdot2 = 1 \quad\text{si}\quad p = p' = 0 \end{cases} \end{align*}$$Ceci prouve que la famille $\left(G_{p, q}\right)_{0 \leq p, q \leq 7}$ est bien une famille orthonormale de $\mathbb{R}^{8 \times 8}$.
$$\blacksquare$$On obtient ainsi la décomposition suivante :
$$\begin{align*} \mathbf{F}^{(i)}[n,m] &= \sum_{p=0}^{7} \sum_{q=0}^{7} C_{p,q}^{(i)}\, G_{p,q}[n,m] \\ \end{align*}$$ Avec $0 \leq n, m \leq 7$. Les coefficients peuvent être simplement obtenus par orthonormalité : $$ C_{p, q}^{(i)}=\langle \mathbf{F}^{(i)}, G_{p,q} \rangle = \sum_{n=0}^{7} \sum_{m=0}^{7} \mathbf{F}^{(i)}[n,m]\, G_{p,q}[n,m] = g_p \cdot F^{(i)} \cdot g_q^\top $$La notation matricielle va permettre, en posant $G = \left( g_0 | \cdots | g_7 \right)^\top$ de calculer: $$ C^{(i)} = G\cdot F^{(i)} \cdot G^\top $$
Comme nous l'avons brièvement vu en introduction, l'idée est ensuite de reconstruire $\mathbf{F}[n, m]$ en utilisant qu'une sous partie des coéfficients $C_{p, q}$ calculés. Pour intuiter cela, on pose: On choisit $K$ couples $(p, q)$ aléatoirement (le même ensemble pour chaque bloc) et on reconstruit : $$ \mathbf{F}^{(i)}_K[n, m] = \sum_{(p,q) \in S_K} C^{(i)}_{p, q}\, G_{p, q}[n, m] $$ où $S_K$ est un ensemble de $K$ couples tirés aléatoirement, avec $(0,0)$ toujours inclus en premier. Pour $K=0$ l'image est nulle, pour $K=64$ on retrouve l'image originale.
On vient en fait de retrouver l'égalité de Perseval. L'énergie de l'image dans l'espace est la même que dans les fréquence
Donc maintenant si l'on compresse $\mathbf{F}^{(i)}$ à l'aide d'une certaine fonction de décision $b$ que l'on cherche à déterminer on obtient: $$ \mathbf{F}_c^{(i)} = \sum_{p, q} \tilde{C}_{p, q}^{(i)} G_{p, q} \quad\text{avec}\quad \tilde{C}_{p, q}^{(i)}= \begin{cases} C_{p,q}^{(i)} &\quad\text{si}\quad b(p, q)\\ 0 &\quad\text{sinon} \end{cases} $$ Avec cette définition, $$ \lVert \mathbf{F}^{(i)} - \mathbf{F}_c^{(i)} \rVert^2 = \sum_{p, q} | C_{p,q}^{(i)} - \tilde{C}_{p, q}^{(i)}|^2 = \sum_{p, q | \neg b(p, q)} | C_{p, q}^{(i)} |^2 $$Alors la perte est d'autant plus grande que les coéfficients que l'on a pas gardé. On veut donc supprimer les plus petits coefficients ou encore garder les plus grands. Il est évidemment impensable de trier les $C_{p, q}^{(i)}$ mais peut-être (ça nous arrangerais vraiment bien) que ceux-ci sont monotones de $p$ et $q$...
On va essayer de voir que $C^{(i)}_{p, q}$ est une suite décroissante de $p$ et $q$. On peut dans un premier temps tracer $G_{p, q}(x, y)$ pour $0 \leq x, y \leq 7$. Une autre remarque que cet graphe permet de faire est que l'on voit bien que $p$ controle les oscillations horizontales et $q$ les oscillations verticales comme dans une série de Fourier 2D classique. Ça explique également les artefacts en "lignes" que l'on pouvait voir si l'essais de compression précédent.Intuitivement, lorsque l'on va multiplier le signal par ces fonctions, plus les oscillations seront rapides plus le signal sera absorbé par les zéros.
Lemme: Décroissance spectrale Soit $f=(f_0, \dots, f_{N-1})$ un signal. On note: $$ T_p = \sum_{n=0}^{N-1} f_n \cos \phi_n \quad\text{avec}\quad \phi_n = \frac{p\pi}{N}\left(n + \frac{1}{2}\right) $$ De sorte que $C_p = \sqrt{\frac{2}{N}} T_p$. On va réaliser une sommation d'Abel, on cherche donc $K_n$ tel que $\Delta K_n = \cos \phi_n$. On va partir de l'ansatz $K_n = A\cos(\omega n) + B\sin(\omega n)$ de tel sorte que: $$ \Delta K_n = -2A\sin \left( \omega (n + \frac{1}{2}) \right)\sin\left(\frac{\omega}{2}\right) + 2B \cos \left( \omega (n + \frac{1}{2})\right)\sin\left(\frac{\omega}{2}\right) $$ Ce qui mène à $A=0$, $\omega = \frac{p \pi}{N}$ et $B = 1/(2\sin(\frac{p\pi}{2N}))$ d'où: $$ K_n = \frac{\sin\left(n\frac{\pi p}{N}\right)}{2\sin\left(\frac{\pi p}{2N}\right)} = \frac{\sin(n\omega)}{\alpha} $$ avec $\omega = \pi p/N$ et $\alpha = 2 \sin \left( \frac{\omega}{2} \right)$. On a maintenant, en remarquant que $K_0=K_N=0$, $$ \begin{align*} T_p &= \sum_{n=0}^{N-1} f_n \Delta K_n \\ &= \sum_{n=0}^{N-1} f_n K_{n+1} - \sum_{n=0}^{N-1} f_n K_{n} \\ &= \sum_{n=1}^{N} f_{n-1} K_{n} - \sum_{n=0}^{N-1} f_n K_{n} \\ &= \underbrace{\left(f_{N-1}K_{N} - f_0 K_0\right)}_{=0} - \sum_{n=1}^{N-1} \Delta f_{n} K_n \end{align*} $$ La volonté de répéter cette opération plusieurs fois nous invite à chercher une série $H$ telle que: $\Delta H^{(k+1)}_n = H^{(k)}_n$. On remarque que en posant: $$ H_n{(k)} = \frac{e^{iw(n+\frac{1}{2})}}{\eta^k} \quad\text{avec}\quad \eta = e^{iw} - 1 $$ On obtient bien: $$ \Delta H_n^{(k+1)} = \frac{1}{\eta^{k+1}} \left( e^{iw(n+\frac{1}{2}+1)} - e^{iw(n+\frac{1}{2})}\right) = \frac{e^{iw(n+\frac{1}{2})}}{\eta^{k+1}}(e^{iw} - 1) = H_n^{(k)} $$ Par ailleurs, puisque $\eta = 2i \sin \left( \frac{\omega}{2} \right) e^{i \omega/2} = 2\sin\left( \frac{\omega}{2} \right) e^{i/2 \left( \omega + \pi\right)}$, on obtient: $$ H_n^{(k)} = \frac{\exp [i\left( w(n+\frac{1-k}{2}) - \frac{k \pi}{2} \right)]}{2^k \sin^k \left( \frac{\omega}{2}\right)} \quad\text{donc}\quad K_n^{(k)} = \frac{\cos \left( w(n-\frac{1-k}{2}) - \frac{k \pi}{2} \right)}{2^k \sin^k \left( \frac{\omega}{2}\right)} $$ On a déphasé $H_n^{(k)}$ de $\omega/2$ de manière à avoir $K_n^{(0)} = \cos \phi_n$. On peut montrer par récurrence la formule suivante que correspond à faire k fois une somation d'Abel. Je ne vais pas la démontrer ici car c'est très calculatoire et pas intéressant. $$ T_p = \sum_{i=1}^{k} (-1)^{i+1} \left( [\Delta^{i-1}f]_{N-1} K_N^{(i)} - [\Delta^{i-1}f]_{i-1}K_{i-1}^{(i)} \right) + (-1)^{k} \sum_{n=k}^{N-1} [\Delta^k f]_n K_n^{(k)} $$ On peut cependant remarquer que pour $k=0$, on retrouve la forme initiale de $T_p$ et pour $k=1$, on retrouve exactement le calcul trouvé lors de la première applications de la sommation par parties. Par ailleurs, pour tout $n \in \mathbb{Z}$, $$ |K_n^{(k)}| \leq \lVert K^{(k)} \rVert_{\infty} \leq \frac{1}{2^k |\sin \frac{\omega}{2}|^k} \leq \left( \frac{N}{2p}\right)^k $$ On a ici utilisé l'inégalité de Jordan vrai car $0 \leq \omega/2 \leq \pi/2$ Ainsi, $$ \begin{align*} |T_p| &\leq \sum_{i=1}^{k} \left( |[\Delta^{i-1}f]_{N-1}| + |[\Delta^{i-1}f]_{i-1}| \right) \lVert K^{(i)} \rVert_{\infty} + \lVert \Delta^k f \rVert_1 \cdot \lVert K^{(k)} \rVert_{\infty} \\ &\leq \sum_{i=1}^{k} \left( \frac{N}{2p} \right)^i \left( |[\Delta^{i-1}f]_{N-1}| + |[\Delta^{i-1}f]_{i-1}| \right) + \left( \frac{N}{2p} \right)^k \lVert \Delta^k f \rVert_1 \end{align*} $$Il est maintenant l'heure de faire un hypothèse très forte qui explique beaucoup sur les artefacts que l'on peut observer lors de la compression. On fait ici l'hypothèse que le signal est periodique et pair à toute les periodes. Ceci revient à supposer (si l'on revient à une image) que la transition entre 2 blocs $8 \times 8$ consécutifs est continue. Sous cette hypothèse, on peut montrer que les $\Delta^{i} f$ pour $i < k$ s'annulent.
On obtient alors: $$ \boxed{ \forall k \in \mathbb{N}, |C_p| \leq \sqrt{\frac{2}{N}} \left( \frac{N}{2p} \right)^k \| \Delta^k f \|_1 = O\left(\frac{1}{p^k}\right) } $$ $$\blacksquare$$ On a maintenant, en ramenant notre DCT-2D en 2 DCT-1D, que: $ C_{p, q}^{(i)} = O\left( \frac{1}{p^kq^k}\right) $. Ceci justifie que dans l'objectif de conserver les coéfficients les plus grands, on a intérêts à choisir ceux tel que $p$ et $q$ sont les plus petits. On va poser $ C_L = \left\{ (p, q) : p + q \leq L \right\} $ et considérer la reconstruction: $$ F^{(i)}[n, m] = \sum_{p, q \in C_L} C_{p, q}^{(i)} G_{p, q}[n, m] $$ Ceci revient à choisir les coéfficients qui sont en distance de Manhattan à une distance inférieur à $L$ du coin inférieur gauche.La figure de droite représente l'image ainsi compressée. La figure de gauche représente C[i, j]. Le point est rouge si le coeffcieint est éliminé et vert sinon. On remarque que à taux de compression équivalent, cette méthode de selection des coéfficients génère, comme on l'a prouvé, moins d'artefacts.
