
\chapter{Compresión progresiva de vídeo}
\label{cha:capitulo2}
%\chaptermark{Comp. de Vídeo basada en la Trans. Wavelet}
%\sectionmark{}
\section{La transformada wavelet discreta}
\label{sec:DWT}
%{{{ 

La atención que han recibido las transformadas wavelets en los últimos años
es sencillamente abrumadora. Esto ha generado, tanto a nivel teórico
como de aplicación (especialmente en el procesamiento y compresión de
señales) una línea de investigación muy importante.

Como muchas de las transformadas usadas en compresión, su función es
calcular un conjunto de coeficientes que indican la correlación que
existe entre la señal a transformar y una serie de funciones base que
forman un espacio ortogonal, tratando así de acumular en el mínimo
número de coeficientes la máxima cantidad de información
(energía), y si es posible, disminuir además la entropía de los
datos \cite{Said.S+P:96}.

Sin pérdida de generalidad, trataremos sólo por ahora el caso
unidimensional. Sea \hbox{$f[x], x=0,1,\cdots, 2^n-1$} el vector de
muestras a transformar. Para encontrar una representación que cumpla
el objetivo propuesto, vamos a emplear un modelo espacial como
predictor, pero en lugar de usarlo de forma secuencial, procesando el
vector desde un extremo a otro vamos usar dicho modelo para calcular
primero una versión reducida de tamaño mitad de $f[x]$ a la que
llamaremos $l[x], x=0,1,\cdots, 2^{n-1}-1$. La idea es usar $l[x]$
para generar un vector $\hat{f}[x]$ que sea tan parecido a $f[x]$ como
sea posible. De esta forma, el vector residuo $$h[x]=f[x]-\hat{f}[x]$$
contendrá la información que el modelo no es capaz de predecir.

Si el modelo de predicción es adecuado, las entropías de $h[x]$ y de
$l[x]$ son inferiores a la de $f[x]$.\footnote{Los elementos de $h[x]$
  tienden a ser cero y en $l[x]$ el número de símbolos usados tiende
  a disminuir.} Por ejemplo, sea $f[]=\{1,3,2,1\}$. Una posible forma
de encontrar $l[]$ consiste en calcular la media de cada dos muestras:
$l[]=\{2,1.5\}$.  A partir de este vector, una predicción que podemos
hacer a cerca de $f[]$ es $\hat{f}[]=\{2,2,1.5,1.5\}$, resultando un
vector residuo $h[]=\{-1,1,0.5,-0.5\}$. Nótese que $h[]$ está
formado por coeficientes que de dos en dos sólo se diferencian en el
signo.

Como hemos visto, una forma de construir $l[x]$ es calcular la media
de cada dos muestras de $f[x]$, es decir
\begin{equation}
l[x] = \frac{f[2x]+f[2x+1]}{2}, x=0,1,\cdots,2^{n-1}-1.
\label{eq:Haar_d1}
\end{equation}
Si para generar $\hat{f}[x]$ usamos cada muestra de $l[x]$ dos veces
de forma consecutiva, entonces sólo se necesitan la mitad de las
muestras (las pares o las impares) de $h[x]$ para reconstruir $f[x]$.
De hecho, $h[x]$ puede calcularse también usando
\begin{equation}
h[x] = \frac{f[2x+1]-f[2x]}{2}, x=0,1,\cdots,2^{n-1}-1.
\label{eq:Haar_d2}
\end{equation}
En dicha transformada, se obtiene una representación alternativa para $f[x]$
formada por dos vectores de tamaño mitad: $l[x]$ y $h[x]$, que ocupan
en conjunto el mismo espacio que $f[x]$. El vector $l[x]$ almacena la
media de cada dos muestras de $f[x]$ y $h[x]$ almacena la diferencia
entre cada par de muestras dividida entre dos.

Desde el punto de vista del procesamiento de
señales~\cite{Woods.SBC}, el proceso descrito coincide con la
descomposición de una señal en dos bandas de
frecuencia~\cite{Tran.LPPRFB}. Una de ellas ($l[x]$) contiene la banda de
baja frecuencia y la otra ($h[x]$) la banda de alta frecuencia. Esta
descomposición puede ser aplicada de forma recursiva a la banda de
baja frecuencia, generándose así lo que se conoce como transformada
wavelet discreta o DWT (Discrete Wavelet Transform).
%}}}


Para terminar la descripción de la DWT, sólo queda
decir que es muy rápida. Como es conocido~\cite{C-DSP,Rabiner}, el
filtrado de una señal $f[x]$ puede realizarse convolucionando dicha
señal con la respuesta del filtro al impulso unitario y este cálculo
es de complejidad lineal $O(N)$ (donde $N=2^n$) y proporcional a la
longitud del filtro.


\section{La transformada S}
\label{sec:ST}
%{{{ 
La transformada S (ST: Sequential Transform)~\cite{Said.S+P:93,Said.S+P:96} también llamada
transformada de interpolación (1,1) evita la división en punto
flotante (ver Ecuaciones~(\ref{eq:Haar_d1}) y (\ref{eq:Haar_d2})) lo
cual es fundamental si se desea que la transformada sea totalmente
reversible.  Sólo de esta forma, la transformación inversa recupera
siempre la señal original.

La transformada S directa para $2^n$ puntos se calcula aplicando los
filtros de análisis
\begin{equation}
  l[i] = \displaystyle\Bigg\lfloor\frac{f[2i]+f[2i+1]}{2}\displaystyle\Bigg\rfloor
  \label{eq:ST_d1}
\end{equation}
y
\begin{equation}
  h[i] = f[2i]-f[2i+1].
  \label{eq:ST_d2}
\end{equation}
donde $\lfloor\cdot\rfloor$ representa al operador ``el mayor entero
menor que''.

Los filtros de síntesis usados en la transformada inversa se
encuentran fácilmente a partir de las Ecuaciones~(\ref{eq:ST_d1}) y
(\ref{eq:ST_d2}), resultando

\begin{equation}
  f[2i] = l[i] + \displaystyle\Bigg\lfloor\frac{h[i]+1}{2}\displaystyle\Bigg\rfloor 
  \label{eq:ST_i1}
\end{equation}

y

\begin{equation}
  f[2i+1] = f[2i] - h[i].
  \label{eq:ST_i2}
\end{equation}

Nótese que la banda de baja frecuencia almacena la media de la señal
y la banda de alta frecuencia representa los errores que resultan de
predecir que las muestras impares son iguales a las pares, dos a
dos. Por ejemplo, $h[0]$ sería igual a 0 si las dos primeras muestras
de $f[i]$ fueran idénticas.

\section{La transformada 5/3}

La transformada 5/3 también llamada transformada de interpolación
(2,2) hace la suposición de que la señal está compuesta por funciones
lineales. Utiliza dos puntos para predecir una muestra. Para ello
supone que las muestras impares $s[2i+1]$ están a mitad de camino
entre la muestra anterior $s[2i]$ y la siguiente muestra
$s[2i+2]$. Por esa razón, la transformada 5/3 se calcula aplicando los
filtros de análisis

\begin{equation}
  h[i]=s[2i+1]-\displaystyle\Bigg\lfloor\frac{s[2i]+s[2i+2]}{2}\displaystyle\Bigg\rfloor,~i=0,\cdots,\frac{N}{2}-1
  \label{eq:LT_A-HPF}
\end{equation}
y

\begin{equation}
  l[i]=s[2i]+\displaystyle\Bigg\lfloor\frac{h[i]+h[i-1]}{4}+\frac{1}{2}\displaystyle\Bigg\rfloor,~i=0,\cdots,\frac{N}{2}-1.
  \label{eq:LT_A-LPF}
\end{equation}


Tenemos que contemplar los siguientes casos especiales:

\begin{enumerate}
\item Si el número $N$ de muestras de $s$ es impar, entonces la expresión (\ref{eq:LT_A-HPF}) es definitiva. Nótese que la longitud de la secuencia de muestras será $\frac{N}{2}-1$.
\item Si $N$ es par, la muestra $s[2i+2]$ para $i=\frac{N}{2}-1$ no existe y debemos usar
\begin{equation}
  h[i] = s[N-1] - s[N-2].
  \label{eq:LT_A-HPF_even}
\end{equation}
Nótese que esto es el resultado de suponer que la muestra
$s[N]=s[N-2]$. En este caso, la 5/3 es idéntica a la ST.
\end{enumerate}

Los filtros de síntesis utilizados en la transformada inversa son los siguientes

\begin{equation}
  s[2i]=l[i]+\displaystyle\Bigg\lfloor\frac{h[i-1]+h[i]}{4}+\frac{1}{2}\displaystyle\Bigg\rfloor,~i=1,\cdots,\frac{N}{2}-1
  \label{eq:LT_S-LPF}
\end{equation}

y 

\begin{equation}
  s[2i+1]=h[i]+\displaystyle\Bigg\lfloor\frac{s[2i]+s[2i+2]}{2}\displaystyle\Bigg\rfloor,~i=0,\cdots,\frac{N}{2}-1.
  \label{eq:LT_S-HPF}
\end{equation}

Con los casos especiales:

\begin{enumerate}
\item Para $i=0$
\begin{equation}
  s[0] = l[0] + \displaystyle\Bigg\lfloor\frac{h[0]}{2}+\frac{1}{2}\displaystyle\Bigg\rfloor.
  \label{eq:LT_S-LPF_cero}
\end{equation}
\item Si $N$ es impar entonces
  \begin{equation}
    s[N-1] = l[0] + \displaystyle\Bigg\lfloor\frac{h[i-1]}{2}+\frac{1}{2}\displaystyle\Bigg\rfloor.
    \label{eq:LT_S-LPF_N2}
  \end{equation}
\end{enumerate}

\section{La transformada 13/7-T}

La transformada 13/7-T también llamada transformada de interpolación
(4,4) es la versión entera de la transformada 13/7 que es en punto
flotante. La transformada 13/7-T incrementa a cuatro el número de
puntos usados para predecir una muestra y esto produce unas
aproximaciones más suaves. Los filtros de análisis de la transformada
son los siguientes

\begin{equation}
  \begin{array}{rcl}
    h[i] & = & s[2i+1] - \lfloor\frac{9}{16}(s[2i]+s[2i+2]) - \frac{1}{16}(s[2i-2]+s[2i+4]) + \frac{1}{2}\rfloor \\
    l[i] & = & s[2i] + \lfloor\frac{9}{32}(h[i-1]+h[i]) - \frac{1}{32}(h[i-2]+h[i+1]) + \frac{1}{2}\rfloor \\
    \\
         &   & \textrm{con } i = 0,\ldots,N/2-1.\\
  \end{array}
  \label{eq:13/7-T}
\end{equation}

De forma similar, la transformada 13/7-T inversa se obtiene aplicando

\begin{equation}
  \begin{array}{rcl}
    s[2i] & = & l[i] - \lfloor\frac{9}{32}(h[i-1]+h[i]) - \frac{1}{32}(h[i-2]+h[i+1]) + \frac{1}{2}\rfloor \\
    s[2i+1] & = & h[i] + \lfloor\frac{9}{16}(s[2i]+s[2i+2]) - \frac{1}{16}(s[2i-2]+s[2i+4]) + \frac{1}{2}\rfloor \\
    \\
         &   & \textrm{con } i = 0,\ldots,N/2-1.\\
  \end{array}
  \label{eq:inverse_13/7-T}
\end{equation}

La transformada utilizada en el desarrollo del proyecto es la
transformada 13/7-T, junto con la 5/3 y la ST cuando es necesario
predecir algunas muestras cercanas a los límites de la señal.

\section{La transformada wavelet discreta 3D}

La transformada wavelet es separable. La transformada de más de una
dimensión se obtiene aplicando la transformada unidimensional a cada
una de las dimensiones del GOP. El filtro se aplica recursivamente
sobre la banda de baja frecuencia tantas veces como se pueda en
función del tamaño de cada una de las dimensiones del volumen. La
Figura \ref{fig:descomposicionDWT3D} muestra el cálculo de la DWT-3D.

\begin{figure}
\centering
\epsfig{file=figuras/eps/descomposicionDWT3D,width=8cm}
\caption[Cálculo de la DWT-3D]
{Cálculo de la DWT-3D. En este ejemplo se han aplicado dos niveles de
descomposición.}
\label{fig:descomposicionDWT3D}
\end{figure}



Para transmitir los coeficientes de máxima potencia es necesario
transmitir los coeficientes de bajas frecuencias antes que los de
altas frecuencias a igualdad de potencia. De esta forma, se tiende a
enviar primero los coeficientes situados en la esquina superior
izquierda que son los que representan a las bandas de baja
frecuencia. Para ello, las distintas bandas se ponderan por un factor,
consiguiendo que la transformada sea unitaria (una transformación
unitaria posee la propiedad de que la norma Euclídea es invariante,
esto es, una medida de distorsión efectuada sobre el dominio
transformado es equivalente a realizarla sobre el dominio
original\cite{SPIHT:96}) y en consecuencia, ahora se cumple que el
MSE (entre la imagen original y la imagen transmitida) se minimiza con
la transmisión de los coeficientes atendiendo a su magnitud.


%\begin{figure}
%\centering
%\epsfig{file=figuras/eps/ponderacionDWT3D,width=8cm}
%\caption[Factores de ponderación en la DWT-3D]
%{Factores de ponderación usados en la DWT-3D.}
%\label{fig:ponderacionDWT3D}
%\end{figure}


%\section{Características de los coeficientes wavelets}

También indicar que la representación de los coeficientes se hace con
aritmética entera, lo que permite que la compresión y descompresión de
cualquier señal sea totalmente reversible. Los coeficientes más
importantes (visualmente hablando) son los que tienen mayor potencia,
pues contienen mayor cantidad de información. Como ya hemos indicado,
dichos coeficientes tienden a agruparse sobre las bandas de baja
frecuencia, que son los que primero se transmiten.

\section{Compresión de los planos de bits}

La transmisión incremental de imágenes puede ser mejorada si en lugar
de enviar los coeficientes completos se transmiten por planos de
bits. Si $p$ es la posición que ocupa el bit más significativo de
los coeficientes más grandes, la idea es transmitir primero todos los
bits que están en la posición p de todos los coeficientes. A
continuación se envían todos los bits que están en la posición $p-1$ y así sucesivamente hasta enviar todos los planos. Éste es un
razonamiento lógico si se tiene en cuenta que es más importante
indicar al receptor los bit más significativos de los coeficientes
menores que los bits menos significativos de los coeficientes mayores.

La clave para determinar un método efectivo de codificación de los
planos de bits está en darse cuenta de que existe una cierta
dependencia entre los coeficientes dentro del espacio wavelet.  Esta
correlación entre coeficientes puede expresarse diciendo que si un
coeficiente es significativo en una octava de frecuencia\footnote{Modelo de descomposición en bandas de frecuencia donde cada
banda tiene el doble de coeficientes espectrales que la de frecuencia
inmediatamente menor.} inferior, entonces los 8 coeficientes que
ocupan la misma posición relativa dentro de la siguiente octava
tienden a ser significativos, y viceversa.

La relación espacio-temporal exacta entre un coeficiente de
coordenadas\footnote{Las coordenadas se expresan como (fila, columna,
tiempo).} $(i,j,k)$ y sus ocho hijos (si es que existen), es que estos
se encuentran en las coordenadas absolutas

\begin{eqnarray}
\mathcal{O}(i,j,k)=\big\{(2i,2j,2k),(2i,2j+1,2k),(2i+1,2j,2k), \nonumber\\
(2i+1,2j+1,2k),(2i,2j,2k+1),(2i+1,2j,2k+1), \nonumber\\
(2i,2j+1,2k+1),(2i+1,2j+1,2k+1)\big\},
\label{eq:AOE}
\end{eqnarray}

y esta relación se propaga de forma recursiva entre todos los
coeficientes wavelet. Por lo tanto, un nodo $(i,j,k)$ del árbol tiene
8 hijos agrupados en bloques de $2 \times 2 \times 2$ o no tiene
ninguno, lo que ocurre en el nivel más bajo de la descomposición. La
Figura~\ref{fig:trees-DWT-3D} muestra un ejemplo de la dependencia
espacio-temporal de los coeficientes en el nivel más alto. A cada
árbol diseñado usando la Expresión~\ref{eq:AOE} se le llama
``árbol de orientación espacial'' (AOE).

\begin{figure}
\centering
\epsfig{file=figuras/eps/Spiht3d,width=7cm}
\caption[Árboles creados en la DWT-3D]
{Algunos ejemplos de árboles creados en la DWT-3D.}
\label{fig:trees-DWT-3D}
\end{figure}

A todos los descendientes de $(i,j,k)$ (hijos, nietos, etc.) los
denotaremos por $\mathcal{D}(i,j,k)$. El número total de
descendientes es 0 o una potencia de 8 cuyo exponente depende del
nivel de la descomposición wavelet. Nótese que
$\mathcal{D}(i,j,k)+(i,j,k)$ forman un AOE completo. Cuando un AOE
está formado sólo por ceros decimos que se trata de un zerotree.

La relación estadística entre un elemento $(i,j,k)$ y sus
descendientes $\mathcal{D}(i,j,k)$ es que si $(i,j,k)$ es 1 entonces
al menos uno de sus descendientes es probablemente 1. Por el
contrario, si $(i,j,k)$ es 0, lo más probable es que todos sus
descendientes sean 0. Esta es una de las principales razones por la que podemos
diseñar compresores a partir del espacio wavelet.

%\section{Un codec de vídeo progresivo de coeficientes wavelet: SPIHT-3D}
\section{El algoritmo SPIHT-3D}
\label{sec:SPIHT-3D}
%{{{ 

Una vez presentada el tipo de redundancia que es posible explotar en
el dominio wavelet cuando los coeficientes son transmitidos por
planos de bits, vamos a analizar uno de los compresores progresivos
más eficientes que se conocen: SPIHT (Set Partitioning In
Hierarchical Trees)~\cite{SPIHT:93,SPIHT:96}, en su implementación en
tres dimensiones.

\begin{figure}
\centering
\epsfig{file=figuras/eps/sistema_spiht,width=13cm}
\caption[Esquema de un PVC que utiliza el algoritmo SPIHT-3D]
{Muestra el esquema de un PVC que utiliza el algoritmo SPIHT-3D.}
\label{fig:sistema_spiht}
\end{figure}


SPIHT fue ideado por Said y Pearlman en 1996 y extendido a su versión
en tres dimensiones por Chen y Pearlman ese mismo año. Muestra un
efectivo y computacionalmente simple codec de vídeo sin
compensación de movimiento que obtiene unos excelentes resultados
numéricos y visuales.

El algoritmo tiene las siguientes características:

\begin{itemize}
\item La información visualmente más importante es transmitida primero.
\item Explota la redundancia entre las diferentes escalas espacio-temporales.
\item El code-stream está comprimido y es completamente seccionable proporcionando calidad progresiva de forma que permite al algoritmo ser detenido en cualquier instante ó hasta que se obtenga una reconstrucción sin perdida.
\item Permite la visualización a diferentes frames por segundo y con distintos tamaños de frame usando el mismo code-stream codificado gracias a la transformada wavelet. 

\end{itemize}

La Figura \ref{fig:sistema_spiht} muestra el diagrama de un codec de vídeo que utiliza el algoritmo SPIHT-3D. Está formado por los siguientes componentes:

\begin{itemize}
\item DWT-3D directa: A este bloque llega la secuencia original a la que se le aplica la transformada directa obteniendo de esta forma la secuencia transformada.
\item Codificador SPIHT-3D: Una vez que se genera la secuencia transformada, la codificamos usando el algoritmo SPIHT-3D. De esta forma obtenemos una secuencia transformada y comprimida de forma óptima para enviar al canal de comunicación. Esta secuencia cumple con las características del algoritmo.
\item Descodificador SPIHT-3D: Desde el canal va llegando la secuencia transformada y comprimida, se le aplica la descodificación y obtenemos la secuencia transformada. 
\item DWT-3D inversa: A la secuencia transformada se le aplica la transformada inversa obteniendo la secuencia original o una aproximación en función de que haya procesado la secuencia completa o una parte de ella.
\end{itemize}

%\subsection{El algoritmo SPIHT-3D}
%{{{ 

El codificador SPIHT-3D codifica eficientemente los volúmenes de
significancia, aprovechando la similaridad o semejanza que existe
entre las diferentes octavas.

%(volumen donde cada coeficiente se representa con un
%único bit, indicando que empieza a ser significativo),
%aunque no explota la redundancia que pueda existir entre las tres
%bandas de una misma escala.


Lo primero que hace es transmitir el plano de bits más significativo
(los coeficientes se tratan en forma signo-magnitud). Después entra
en un bucle que itera tantas veces como planos de bits tienen que
transmitirse. En la emisión de cada plano de bits se diferencia entre
los bits de significancia (indican que coeficientes comienzan a ser
significativos en el volumen actualmente transmitido -- que son
comprimidos) y los bits de refinamiento (están formados por los bits
de los coeficientes que ya son significativos en un plano superior,
afinando el valor real del coeficiente wavelet -- que no son
comprimidos). Los bits de signo son también transmitidos sin
comprimir.

SPIHT-3D trabaja particionando los AOEs de forma que tiende a mantener
coeficientes no significativos en grandes conjuntos y comunica con un
único bit si alguno de los elementos de un conjunto es significativo
o no (es un zerotree). 

Las decisiones de particionamiento son decisiones binarias, que son
transmitidas al descodificador e indican los planos de
significancia. Por lo tanto, SPIHT-3D en lugar de transmitir las
coordenadas de los coeficientes significativos en el plano actual,
transmite los resultados de las comparaciones que han provocado la
determinación (por parte del codificador) de todos los zerotrees que
forman dicho plano. 


El descodificador ejecuta exactamente el mismo
algoritmo que el codificador y como no dispone de los coeficientes
wavelet para saber si son significativos o no, usa los resultados de
las comparaciones que le llegan en el code-stream. De esta forma la
traza de instrucciones es idéntica.

SPIHT-3D transmite los planos de significancia y de refinamiento en dos
fases independientes llamadas de ordenación y de refinamiento,
respectivamente. El nombre de la fase de refinamiento es obvio. Sin
embargo la fase de ordenación se llama así porque lo que el
codificador hace es ordenar los coeficientes atendiendo a su valor
absoluto y luego enviarlos según ha resultado dicho orden. Pero
nótese que la ordenación que se produce es muy suave ya que no es
necesario ordenar todos los coeficientes que son significativos en el
plano que se transmite, sólo debemos encontrar qué coeficientes van
antes que otros porque son significativos en un plano superior.

\subsubsection{La fase de ordenación}
%{{{ 

Como ya hemos indicado, SPIHT-3D es eficiente porque realiza un número
mínimo de comparaciones casi equiprobables. La clave está en saber cómo
formular dichas comparaciones, que se construyen usando un algoritmo
de particionamiento de los AOEs.

El codificador y el descodificador manejan conceptualmente dos listas
de coeficientes representados por sus coordenadas espaciales. En una
se almacenan todos los coeficientes que son significativos en el
plano actual de transmisión $p$. Todos estos coeficientes $c$
verifican que
\begin{equation}
  |c|\ge 2^p.
\end{equation}

La otra lista almacena el resto de coeficientes que no son
significativos. Inicialmente esta lista contiene todos los
coeficientes (tantos como puntos existen en el GOP) y la lista de
coeficientes significativos está vacía. Notaremos con LIC (List
  of Insignificant Coefficients) a la lista de coeficientes no
significativos y con LSC (List of Significant Coefficients) a la
de coeficientes significativos.

SPIHT-3D realiza una partición inicial
\begin{eqnarray}
(0,0,0), (0,1,0), (1,0,0), (1,1,0), (0,0,1), \nonumber\\
(1,0,1), (0,1,1), (1,1,1), \mathcal{D}(0,1,0), \mathcal{D}(1,0,0), \nonumber\\
\mathcal{D}(1,1,0), \mathcal{D}(0,0,1), \mathcal{D}(1,0,1), \mathcal{D}(0,1,1), \mathcal{D}(1,1,1),
\end{eqnarray}
donde como ya sabemos, $\mathcal{D}(i,j,k)$ representa a todos los
coeficientes descendientes de $(i,j,k)$ que se determinan aplicando la
Ecuación~(\ref{eq:AOE}) recursivamente.

SPIHT-3D averigua qué elementos de esta partición son significativos.
Más formalmente, evalúa la función
\begin{equation}
  S_p(\mathcal{T})=\left\{
    \begin{array}{ll}
      1 & \mathrm{si~alg\acute{u}n~coeficiente~} |c|\in \mathcal{T}\ge 2^p\\
      0 & \mathrm{en~caso~contrario},
    \end{array}
  \right.
  \label{eq:S_p}
\end{equation}
donde $\mathcal{T}$ puede ser un único coeficiente o un conjunto de
coeficientes.

En la codificación del primer plano de bits, las 8 raíces
$$
\big\{(0,0,0), (0,1,0), (1,0,0), (1,1,0), (0,0,1), (1,0,1), (0,1,1), (1,1,1)\big\}
$$ tienen un 50\% de posibilidades de ser
significativas y a sus descendientes
$$\big\{\mathcal{D}(0,1,0), \mathcal{D}(1,0,0), \nonumber\\
\mathcal{D}(1,1,0), \mathcal{D}(0,0,1), \mathcal{D}(1,0,1), \mathcal{D}(0,1,1), \mathcal{D}(1,1,1)\big\}$$
($(0,0,0)$ no tiene descendientes) les ocurre lo mismo; tienen una
probabilidad igual a 0,5 (aproximadamente) de ser un zerotree. SPIHT-3D
realiza todas estas comparaciones y emite los bits de código
correspondientes.

Para gestionar las particiones, SPIHT-3D usa realmente 3 listas: LIC, LSC
y LIS (List of Insignificant Sets) o lista de conjuntos no
significativos, porque es una forma sencilla de distinguir entre
coeficientes y conjuntos de coeficientes. Por lo tanto, el contenido
inicial de dichas listas es:
\begin{displaymath}
  \begin{array}{rcl}
    \mathrm{LSC}&\leftarrow&\varnothing\\
    \mathrm{LIC}&\leftarrow&\big\{(0,0,0),(0,1,0),(1,0,0),(1,1,0),(0,0,1),(1,0,1),(0,1,1),(1,1,1)\big\}\\
    \mathrm{LIS}&\leftarrow&\big\{(0,1,0),(1,0,0),(1,1,0),(0,0,1),(1,0,1),(0,1,1),(1,1,1)\big\}\\
  \end{array}
\end{displaymath}

Cuando un coeficiente de LIC no es significativo, no ocurre nada en
las listas, pero si lo es, se mueve desde LIC a LSC, para
posteriormente ser refinado. De forma similar, si un coeficiente de
LIS no es significativo (es un zerotree) no ocurre nada en las listas,
pero si es significativo, debe ser particionado en subconjuntos que
tengan tantas posibilidades de ser zerotrees como de no serlo.

SPIHT-3D particiona un $\mathcal{D}(i,j,k)$ en
\begin{displaymath}
  \big\{(k,l,m)\in \mathcal{O}(i,j,k), \mathcal{L}(i,j,k)\big\},
\end{displaymath}
donde $$\mathcal{L}(i,j,k)=\mathcal{D}(i,j,k)-\mathcal{O}(i,j,k).$$ Cada
$\mathcal{D}(i,j,k)$ se descompone en 9 partes: los 8 nodos hijo de
$(i,j,k)$ y el resto de descendientes.

Los $(k,l,m)\in \mathcal{O}(i,j,k)$ se insertan en LIC o en LSC
dependiendo de si son significativos o no. En el caso de viajar a LIC
la inserción debe realizarse al final de la lista para que los
coeficientes sean evaluados en la pasada actual. Los $\mathcal{L}(i,j,k)$
se insertan en LIS para ser más tarde evaluados.

En LIS podemos encontrar, por tanto, 2 tipos de conjuntos:
$\mathcal{D}(i,j,k)$ y $\mathcal{L}(i,j,k)$, que tienen un número
diferente de elementos. SPIHT-3D los diferencia diciendo que los
$\mathcal{D}(i,j,k)$ son de tipo A mientras que los
$\mathcal{L}(i,j,k)$ son de tipo B\footnote{Recuérdese que tanto los
AOEs como los coeficientes individuales se representan por una terna de
coordenadas.}.

El particionado de un $\mathcal{L}(i,j,k)$ es distinto, por tanto, al de
un $\mathcal{D}(i,j,k)$. Si un $\mathcal{L}(i,j,k)$ es significativo
entonces se particiona en 8 conjuntos
\begin{displaymath}
  \big\{\mathcal{D}(k,l,m)\in \mathcal{O}(i,j,k)\big\},
\end{displaymath}
es decir, en los 8 árboles hijos de $(i,j,k)$ que se vuelven a insertar
al final de LIS. Finalmente $\mathcal{L}(i,j,k)$ desaparece de LIS
porque este AOE ha sido particionado en sus 8 subárboles.

%}}}

\subsubsection{La fase de refinamiento}
%{{{ 

Entre cada fase de ordenación se realiza otra de refinamiento. Si $p$
es el plano de bits a transmitir, en esta fase se emite el $p$-ésimo
bit más significativo de cada coeficiente almacenado en LSC. Cuando
un coeficiente ha sido totalmente enviado (recuérdese que 7/8 de los
coeficientes están ponderados por una potencia de 2 y por tanto sus
bits menos significativos son cero forzosamente) se elimina de LSC.

En este punto existen dos alternativas de implementación. Si $O_p$
representa los bits emitidos durante la fase de ordenación de la
capa $p$ y $R_p$ a los bits de refinamiento, una posibilidad de
construcción del code-stream es
\begin{equation}
  O_pR_pO_{p-1}R_{p-1}O_{p-2}\cdots.
  \label{eq:ref_antes}
\end{equation}

Sin embargo, los autores del algoritmo recomiendan que los bits de
ordenación del plano $p-1$ antecedan a los bits de refinamiento del
plano $p$, es decir
\begin{equation}
  O_pO_{p-1}R_pO_{p-2}R_{p-1}\cdots.
  \label{eq:ref_despues}
\end{equation}

Este procedimiento tiene sentido porque de esta forma primero se
envían los bits que definen nuevos coeficientes distintos de 0 y a
continuación se refinan los coeficientes que ya eran significativos.

Las dos alternativas han sido evaluadas y sus rendimientos son muy
similares~\cite{Vruiz.Tesis}. En la exposición del pseudo-código que expone el codec,
por sencillez, se usará la primera opción a la que llamaremos
genéricamente ``refinar antes'' frente a la segunda que será
referenciada por ``refinar después''.

%}}}

\subsubsection{La fase de cuantificación}
La fase de cuantificación se usa para decrementar el umbral de
significancia que en SPIHT-3D son siempre potencias de dos. De esta
forma se seleccionan los planos de bits de los coeficientes wavelet en
el orden correcto.

\subsubsection{El codificador}
%{{{ 

Se presenta sólo el algoritmo del compresor ya que el descompresor es
prácticamente idéntico.

\begin{enumerate}
\item {\bf Fase de inicialización}.
  \begin{enumerate}
  \item Emitir el índice del plano más significativo. Sea este valor
    $p$.
  \item $\mathrm{LSC}\leftarrow\varnothing$.
                                %  \item $\mathrm{LSC*}\leftarrow\varnothing$ (lista LSC temporal).
  \item $\mathrm{LIC}\leftarrow\big\{(0,0,0),(0,1,0),(1,0,0),(1,1,0),(0,0,1),(1,0,1),(0,1,1),(1,1,1)\big\}$.
  \item $\mathrm{LIS}\leftarrow\big\{(0,1,0),(1,0,0),(1,1,0),(0,0,1),(1,0,1),(0,1,1),(1,1,1)\big\}$.
  \end{enumerate}
\item Mientras $p\ge 0$:
  \begin{enumerate}
  \item {\bf Fase de refinamiento}.
    \begin{enumerate}
    \item Para cada $(i,j,k)\in\mathrm{LSC}$:
      \begin{enumerate}
      \item Emitir el $p$-ésimo bit del coeficiente $(i,j,k)$.
      \item Si $(i,j,k)$ ha sido totalmente enviado borrarlo de LSC.
      \end{enumerate}
                                %\item Concatenar la lista LSC* al final de LSC.
                                %\item $\mathsf{LSC*}\leftarrow\varnothing$.
    \end{enumerate}
  \item {\bf Fase de ordenación}.
    \begin{enumerate}
    \item Para cada $(i,j,k)\in\mathrm{LIC}$:
      \begin{enumerate}
      \item Emitir $S_p(i,j,k)$.
      \item Si $S_p(i,j,k)=1$ entonces:
        \begin{itemize}
        \item Mover $(i,j,k)$ desde LIC a LSC.
        \item Emitir el signo de $(i,j,k)$.
        \end{itemize}
      \end{enumerate}
    \item Para cada $(i,j,k)\in\mathrm{LIS}$:
      \begin{enumerate}
      \item Si $(i,j,k)$ es de tipo A entonces:
        \begin{itemize}
        \item Emitir $S_p(\mathcal{D}(i,j,k))$.
        \item Si $S_p(\mathcal{D}(i,j,k))=1$ entonces:
          \begin{itemize}
          \item Para cada $(k,l,m)\in \mathcal{O}(i,j,k)$:\newline
            $\star$ Emitir $S_p(k,l,m)$.\newline
            $\star$ Si $S_p(k,l,m)=1$ entonces:\newline
            \indent$~~\cdot$ Añadir $(k,l,m)$ a LSC.\newline
            \indent$~~\cdot$ Emitir el signo de $(k,l,m)$.\newline
            $\star$ Si no:\newline
            \indent$~~\cdot$ Añadir $(k,l,m)$ al final de LIC.
          \item Si $\mathcal{L}(i,j,k)\ne\varnothing$ (tiene al menos
            nietos) entonces:\newline
            $\star$ Mover $(i,j,k)$ al final de LIS como de tipo B.
          \item Si no:\newline
            $\star$ Borrar $(i,j,k)$ de LIS.
          \end{itemize}
        \end{itemize}
      \item Si no (es de tipo B):
        \begin{itemize}
        \item Emitir $S_p(\mathcal{L}(i,j,k))$ (si alguno de los nietos
          de $(i,j,k)$ es significativo).
        \item Si $S_p(\mathcal{L}(i,j,k))=1$ entonces:
          \begin{itemize}
          \item Añadir cada hijo $(k,l,m)\in \mathcal{O}(i,j,k)$ al
            final de LIS como de tipo A.
          \item Borrar $(i,j,k)$ de LIS.
          \end{itemize}
        \end{itemize}
      \end{enumerate}
    \end{enumerate}
  \item {\bf Fase de cuantificación}.
    \begin{enumerate}
    \item $p\leftarrow p-1$.
    \end{enumerate}
  \end{enumerate}
\end{enumerate}

%}}}

\subsubsection{El descodificador}
%{{{ 

Para encontrar el algoritmo de descodificación debe tenerse presente
que todas las instrucciones de salto condicional están controladas
por el valor devuelto por $S_p(\cdot)$ (ver Ecuación~(\ref{eq:S_p})),
los cuales forman el code-stream generado durante la fase de
ordenación y que por lo tanto son conocidos por el descodificador.
Éste puede realizar exactamente la misma traza de instrucciones si el
algoritmo que ejecuta es idéntico al del codificador excepto porque
donde aparece ``emitir'' ahora debe poner ``recibir''. Ya que se trata
del mismo algoritmo, las tres listas LSC, LIC y LIS van a generarse
exactamente de la misma forma a como se generaron en el codificador,
gracias a lo cual, la reconstrucción del plano es trivial y además,
las complejidades del codificador y del descodificador son idénticas.

Sin embargo, si SPIHT-3D va a ser usado como transmisor progresivo, el
descodificador debe realizar una tarea extra para ajustar los
coeficientes reconstruidos a partir del intervalo de incertidumbre
durante la fase de ordenación. Cuando una coordenada se mueve a LSC,
se sabe que el valor del coeficiente $c$ cumple que
\begin{equation}
  2^p\le|c|<2^{p+1},
\end{equation}
donde $p$ es el plano de bit transmitido. El descodificador utiliza
esta información (más el bit de signo que llega a continuación),
para ajustar el valor reconstruido a la mitad del intervalo
$[2^p,2^{p+1}-1]$ ya que de esta forma el error con respecto al valor
real del coeficiente será la mitad en promedio. Por ejemplo, si
$p=15$, se sabe que el coeficiente es mayor que 32768 y menor que
65535. Si sólo hacemos que el bit 15 sea 1 estaremos reconstruyendo
el coeficiente con el valor mínimo que puede realmente tener. La
solución es hacer
\begin{equation}
  \hat{|c|}=1.5\times 2^p=3\times 2^{p-1},
\end{equation}
que es el valor que divide al intervalo de incertidumbre en dos
mitades iguales. En nuestro ejemplo, el valor de reconstrucción
sería $3\times 2^{15-1}=49152$.

De forma similar, durante la fase de refinamiento, cuando el
descodificador conoce el valor real del bit $(p-1)$-ésimo, resulta
otro intervalo de incertidumbre. Si el bit recibido es un 1, entonces
el bit $(p-1)$-ésimo ya es correcto, pero debemos hacer el bit
$(p-2)$-ésimo igual a 1 para ajustar a la mitad del nuevo intervalo
de incertidumbre. Si el bit recibido es un 0, entonces el bit
$(p-1)$-ésimo está equivocado y debe ser puesto a 0. El bit
$(p-2)$-ésimo debe hacerse 1 para ajustar el valor reconstruido a la
mitad del intervalo de incertidumbre. Por lo tanto, en cualquier caso,
cuando estamos refinando, colocamos el bit recibido a su valor
adecuado y el siguiente bit menos significativo se hace 1.


%\subsection{SPIHT sobre imágenes con cualquier tamaño}
%{{{ 

%Tal y como ha sido definido, SPIHT-3D no puede ser usado sobre un
%volumen con alguna dimensión distinta de una potencia de dos. El
%problema es que los AOEs no pueden crearse, al menos, tal y como han
%sido definidos en la Expresión~(\ref{eq:AOE}).

%\begin{figure}
%  \centering
%  \epsfig{file=transmision_imagenes/ejemplo_SPIHT_no_cuadrado,width=12cm}
%  \caption[Ejemplo de descomposición {\sl wavelet} 2D de lado cualquiera]
%  {Ejemplo de descomposición {\sl wavelet} de una imagen de
%    dimensiones $12\times 10$ (izq). Mapeo de la transformación sobre
%    una matriz de $16\times 16$ coeficientes (der).}
%  \label{fig:ejemplo_SPIHT_no_cuadrado}
%\end{figure}

%Una forma muy aproximada de crear una estructura de datos como ésta
%consiste en usar un volumen nulo con dimensiones extendidas a una
%potencia de dos en la que se ha insertado el volumen a comprimir,
%ajustándose al extremo superior izquierda. Tras aplicar la
%transformada {\sl wavelet} se obtiene dicha descomposición en la que
%podemos encontrar, en varios niveles, coeficientes que son siempre
%cero.

%SPIHT puede ser usado directamente sobre dicha descomposición porque
%los coeficientes que son cero debido a que la imagen no es de lado
%$2^l$ (donde $l$ es el número de niveles) forman {\sl zerotrees} y
%son identificados como tales en niveles superiores de la
%descomposición.
