3.3: Compresión de imagen

Las imágenes digitales, como las fotografías tomadas en su teléfono, se muestran como una matriz rectangular de píxeles. Por ejemplo, la fotografía de la Figura 3.3.1 tiene 1440 píxeles de ancho y 1468 píxeles de alto. Si tuviéramos que acercar la fotografía, podríamos ver píxeles individuales, como los que se muestran a la derecha.

Figura 3.3.1. Una imagen almacenada como una\(1440\times1468\) matriz de píxeles junto con un primer plano de una\(8\times8\) matriz más pequeña.

Se requieren muchos datos para mostrar esta imagen. Una cantidad de datos digitales se mide frecuentemente en bytes, donde un byte es la cantidad de almacenamiento necesario para registrar un número entero entre 0 y 255. Como veremos en breve, cada píxel requiere tres bytes para registrar el color de ese píxel. Esto significa que la cantidad de datos requeridos para mostrar esta imagen es de\(3\times1440\times1468 = 6,341,760\) bytes o de aproximadamente 6.3 megabytes.

Por supuesto, nos gustaría almacenar esta imagen en un teléfono o computadora y tal vez transmitirla a través de nuestro plan de datos para compartirla con otros. Si es posible, nos gustaría encontrar una manera de representar esta imagen utilizando una menor cantidad de datos para que no nos quedemos sin memoria en nuestro teléfono y agotemos rápidamente nuestro plan de datos.

Como veremos en esta sección, el algoritmo de compresión JPEG proporciona un medio para hacer precisamente eso. Esta imagen, cuando se almacena en formato JPEG, requiere sólo 467,359 bytes de datos, lo que equivale aproximadamente al 7% de los 6.3 megabytes requeridos para mostrar la imagen. Es decir, cuando mostramos esta imagen, la estamos reconstruyendo a partir de sólo el 7% de los datos originales. Esto no es demasiado decepcionante ya que hay bastante redundancia en la imagen; la mitad izquierda de la imagen es casi uniformemente azul. El algoritmo JPEG detecta esta redundancia al representar los datos utilizando bases apropiadas.

Vista previa Actividad 3.3.1.

Ya que estaremos utilizando diversas bases y los sistemas de coordenadas que definen, revisemos cómo traducimos entre sistemas de coordenadas.

1. Supongamos que tenemos una base\(\bcal=\{\mathbf v_1,\mathbf v_2,\ldots,\mathbf v_m\}\) para\(\mathbb R^m\text{.}\) Explicar a qué nos referimos con la representación\(\coords{\mathbf x}{\bcal}\) de un vector\(\mathbf x\) en el sistema de coordenadas definido por\(\bcal\text{.}\)
2. Si se nos da la representación\(\coords{\mathbf x}{\bcal}\text{,}\) cómo podemos recuperar el vector\(\mathbf x\text{?}\)
3. Si se nos da el vector\(\mathbf x\text{,}\) como podemos encontrar\(\coords{\mathbf x}{\bcal}\text{?}\)
4. Supongamos que
   \ comenzar {ecuación*}\ bcal=\ izquierda\ {\ dovec {1} {3},\ dovec {1} {1}\ derecha\}\ final {ecuación*}

   es una base para\(\mathbb R^2\text{.}\) Si\(\coords{\mathbf x}{\bcal} = \twovec{1}{-2}\text{,}\) encuentra el vector\(\mathbf x\text{.}\)
5. Si\(\mathbf x=\twovec{2}{-4}\text{,}\) encuentra\(\coords{\mathbf x}{\bcal}\text{.}\)

Modelos de color

Un color es representado digitalmente por un vector en\(\mathbb R^3\text{.}\) Hay diferentes formas en las que podemos representar colores, sin embargo, dependiendo de si una computadora o un humano estará procesando el color. Describiremos dos de estas representaciones, llamadas modelos de color, y demostraremos cómo se usan en el algoritmo de compresión JPEG.

Las pantallas digitales suelen crear colores combinando varias cantidades de rojo, verde y azul. Por lo tanto, podemos describir un color poniendo sus cantidades constituyentes de rojo, verde y azul en un vector\(\threevec{R}{G}{B}\text{.}\) Las cantidades\(R\text{,}\)\(G\text{,}\) y\(B\) se almacenan con un byte de información por lo que se les permite variar entre 0 y 255. A esto se le llama el modelo\(RGB\) de color.

Definimos una base\(\bcal=\{\mathbf v_1,\mathbf v_2,\mathbf v_3\}\) donde

\ begin {ecuación*}\ mathbf v_1 =\ left [\ begin {array} {r} 1\\ 1\ end {array}\ right],\ mathbf v_2 =\ left [\ begin {array} {r} 0\\ -0.34413\\ 1.77200\ end {array}\ derecha],\ mathbf v_3 =\ left [\ begin {array} r} 1.40200\\ -0.71414\\ 0\ end {array}\ derecha]\ end {ecuación*}

para definir un nuevo sistema de coordenadas con coordenadas denotamos\(Y\text{,}\)\(C_b\text{,}\) y\(C_r\text{:}\)

\ begin {ecuación*}\ coords {\ threevec {R} {G} {B}} {\ bcal} =\ tresevec {Y} {c_b} {C_r}\ text {.} \ end {ecuación*}

La coordenada\(Y\) se llama luminancia while\(C_b\) y\(C_r\) se llaman crominancia azul y roja, respectivamente. En este sistema de coordenadas, la luminancia variará de 0 a 255, mientras que las crominancias varían entre -127.5 y 127.5. Esto se conoce como el modelo\(YC_bC_r\) de color. (Para ser completamente precisos, debemos agregar 127.5 a los valores de crominancia para que se encuentren entre 0 y 255, pero aquí no nos preocuparemos por eso).

Actividad 3.3.2.

En esta actividad, exploraremos la diferencia entre estos dos sistemas de coordenadas.

1. Primero, exploraremos el modelo\(RGB\) de color. El siguiente diagrama le permite crear colores usando varias cantidades de rojo, verde y azul. Para cada una de estas tres cantidades, el deslizador varía entre 0 y 255.
   Tu navegador no es compatible con HTML5 Canvas.
   1. ¿Qué sucede cuando\(G=0\text{,}\)\(B=0\) (empujado todo el camino hacia la izquierda), y\(R\) se le permite variar?
   2. ¿Qué sucede cuando\(R=0\text{,}\)\(G=0\text{,}\) y\(B\) se permite variar?
   3. ¿Cómo se puede crear el negro en este modelo de color?
   4. ¿Cómo se puede crear el blanco?
2. A continuación, exploraremos el modelo\(YC_bC_r\) de color. El siguiente diagrama le permite crear colores usando varias cantidades de luminancia\(Y\), crominancia\(C_b\) azul y crominancia roja\(C_r\). El deslizador de lumninance se mueve entre 0 y 255 mientras que los deslizadores de crominancia se mueven entre -127.5 y 127.5.
   Tu navegador no es compatible con HTML5 Canvas.
   1. ¿Qué sucede cuando\(C_b=0\) y\(C_r=0\) (se mantiene en el centro) y\(Y\) se permite variar?
   2. ¿Qué sucede cuando\(Y=0\) (empujado hacia la izquierda),\(C_r=0\) (se mantiene en el centro), y\(C_b\) se permite aumentar entre 0 y 127.5?
   3. ¿Qué sucede cuando\(Y=0\text{,}\)\(C_b=0\text{,}\) y\(C_r\) se permite aumentar entre 0 y 127.5?
   4. ¿Cómo se puede crear el negro en este modelo de color?
   5. ¿Cómo se puede crear el blanco?
3. Verificar que\(\bcal\) sea una base para\(\mathbb R^3\text{.}\)
4. Encuentra la matriz\(C_{\bcal}\) que convierte de\(\threevec{Y}{C_b}{C_r}\) coordenadas en\(\threevec{R}{G}{B}\) coordenadas. Después encuentra la matriz\(C_{\bcal}^{-1}\) que convierte de\(\threevec{R}{G}{B}\) coordenadas de nuevo en\(\threevec{Y}{C_b}{C_r}\) coordenadas.
5. Encuentra las\(\threevec{Y}{C_b}{C_r}\) coordenadas para los siguientes colores y comprueba, usando los diagramas anteriores, que las dos representaciones están de acuerdo.
   1. El rojo puro es\(\threevec{R}{G}{B}= \threevec{255}{0}{0}\text{.}\)
   2. El verde puro es\(\threevec{R}{G}{B}= \threevec{0}{255}{0}\text{.}\)
   3. El azul puro es\(\threevec{R}{G}{B}= \threevec{0}{0}{255}\text{.}\)
   4. El blanco puro es\(\threevec{R}{G}{B}= \threevec{255}{255}{255}\text{.}\)
   5. El negro puro es\(\threevec{R}{G}{B}= \threevec{0}{0}{0}\text{.}\)
6. Encuentra las\(\threevec{R}{G}{B}\) coordenadas para los siguientes colores y comprueba, usando los diagramas anteriores, que las dos representaciones están de acuerdo.
   1. \(\threevec{Y}{C_b}{C_r}=\threevec{128}{0}{0}\text{.}\)
   2. \(\threevec{Y}{C_b}{C_r}=\threevec{128}{60}{0}\text{.}\)
   3. \(\threevec{Y}{C_b}{C_r}=\threevec{128}{0}{60}\text{.}\)
7. Escribe una expresión para
   1. La luminancia\(Y\) ya que depende de\(R\text{,}\)\(G\text{,}\) y\(B\text{.}\)
   2. La crominancia azul\(C_b\) ya que depende de\(R\text{,}\)\(G\text{,}\) y\(B\text{.}\)
   3. La crominancia roja\(C_r\) ya que depende de\(R\text{,}\)\(G\text{,}\) y\(B\text{.}\)

   Explique cómo estas cantidades pueden interpretarse de manera aproximada afirmando que

   1. la luminancia representa el brillo del color.
   2. la crominancia azul mide la cantidad de azul en el color.
   3. la crominancia roja mide la cantidad de rojo en el color.

Estos dos modelos de color nos proporcionan dos formas de representar los colores, cada una de las cuales es útil en un contexto determinado. Las pantallas digitales, como las de teléfonos y monitores de computadora, crean colores combinando diferentes cantidades de rojo, verde y azul. Por lo tanto, el\(RGB\) modelo es más relevante en aplicaciones digitales.

Por el contrario, el modelo de\(YC_bC_r\) color fue creado a partir de la investigación sobre la visión humana y tiene como objetivo concentrar los datos más importantes visualmente en una sola coordenada, la luminancia, a la que nuestros ojos son más sensibles. Por supuesto, cualquier base de\(\mathbb R^3\) debe tener tres vectores así que necesitamos dos coordenadas más, crominancia azul y roja, si queremos representar todos los colores.

Para ver esto explícitamente, se muestra en la Figura 3.3.2 la imagen original y la imagen como renderizada con solo la luminancia. Es decir, a la derecha, el color de cada píxel está representado por solo byte, que es la luminancia. Esta imagen esencialmente parece una versión en escala de grises de la imagen original con todo su detalle visual. De hecho, antes de que la televisión digital se convirtiera en el estándar, las señales de televisión se emitían\(YC_bC_r\) utilizando el modelo a Cuando se mostraba una señal en un televisor en blanco y negro, se mostraba la luminancia y los dos valores de crominancia simplemente se ignoraban.

Figura 3.3.2. La imagen original renderizada solo con los valores de luminancia.

A modo de comparación, en la Figura 3.3.3 se muestran las imágenes correspondientes creadas utilizando únicamente la crominancia azul y la crominancia roja. Observe que la cantidad de detalle visual es considerablemente menor en estas imágenes.

Figura 3.3.3. La imagen original se renderizó, a la izquierda, con solo crominancia azul y, a la derecha, con solo crominancia roja.

En el algoritmo de compresión JPEG, nos interesa representar una imagen utilizando la menor cantidad de datos posible. Al convertir del modelo de\(RGB\) color al modelo de\(YC_bC_r\) color, estamos concentrando los datos más importantes visualmente en una sola cantidad. Esto es útil porque podemos ignorar con seguridad algunos de los datos en los valores de crominancia ya que esos datos no son tan importantes visualmente.

El algoritmo de compresión JPEG

La clave para representar la imagen usando una menor cantidad de datos es detectar redundancias en los datos. Por esta razón, vamos a romper la imagen, que está compuesta por\(1440\times 1468\) píxeles, en pequeños\(8\times8\) bloques de píxeles. Por ejemplo, consideraremos el\(8\times8\) bloque de píxeles delineado en verde en la imagen original, que se muestra a la izquierda de la Figura 3.3.4. La imagen de la derecha acerca el bloque.

Figura 3.3.4. Un\(8\times8\) bloque de píxeles delineados en verde en la imagen original de la izquierda. Vemos el mismo bloque a menor escala a la derecha.

Observe que este bloque, como se ve en la imagen original, es muy pequeño. Si cambiáramos ligeramente algunos de los colores de este bloque, nuestros ojos probablemente no se darían cuenta.

Aquí vemos un primer Plano de la cuadra. El punto importante aquí es que los colores no cambian demasiado a lo largo de este bloque. De hecho, esperamos que esto sea cierto para la mayoría de los bloques. Habrá, por supuesto, algunos bloques que contengan cambios dramáticos, como dónde se cruzan el cielo y la roca, pero serán la excepción.

Figura 3.3.5. Un primer plano del\(8\times8\) bloque que estamos considerando.

Siguiendo nuestro trabajo anterior, cambiaremos la representación de los colores del modelo de\(RGB\) color al\(YC_bC_r\) modelo. Esto separa los colores en valores de luminancia y crominancia que consideraremos por separado. En la Figura 3.3.6, vemos los valores de luminancia de este bloque. Nuevamente, observe cómo estos valores no varían significativamente a lo largo del bloque.

Figura 3.3.6. Los valores de luminancia en este bloque.

Nuestra estrategia en el algoritmo de compresión es realizar un cambio de base para aprovechar que los valores de luminancia no cambian significativamente sobre el bloque. En lugar de registrar la luminancia de cada uno de los píxeles, este cambio de base nos permitirá registrar la luminancia promedio junto con alguna información sobre cómo varían los colores individuales del promedio.

Veamos la primera columna de valores de luminancia, que es un vector en\(\mathbb R^8\text{:}\)

\ begin {ecuación*}\ mathbf x =\ left [\ begin {array} {c} 176\\ 181\\ 165\\ vdots\\ 150\\ end {array}\ derecha]\ text {.} \ end {ecuación*}

Realizaremos un cambio de base para que podamos describir este vector por el promedio de los valores de luminancia e información sobre variaciones del promedio.

El algoritmo de compresión JPEG utiliza la Transformada Discreta de Fourier, que se define usando la base\(\ccal\) cuyos vectores base son

\ begin {ecuación*}\ begin {alineado}\ mathbf v_0 =\ left [\ begin {array} {c}\ cos\ left (\ frac {(2\ cdot0+1)\ cdot0\ pi} {16}\ derecha)\\ cos\ izquierda (\ frac {(2\ cdot1+1)\ cdot0\ pi} {16}\ derecha)\\ cos\ izquierda (\ frac {(2\ cdot2+1)\ cdot0\ pi} {16}\ derecha)\\\ vdots\\ cos\ izquierda (\ frac {(2\ cdot7+1)\ cdot0\ pi} {16}\ derecha)\\ end {array}\ derecha], & \ mathbf v_1 =\ izquierda [\ begin {array} {c}\ cos\ izquierda (\ frac {(2\ cdot0+1)\ cdot1\ pi} {16}\ derecha)\\ cos\ izquierda (\ frac {(2\ cdot1+1)\ cdot1\ pi} {16}\ derecha)\\ cos\ izquierda (\ frac {(2\ cdot2+1)\ cdot1\ pi} {16}\ derecha)\\\ vdots\\ cos\ izquierda (\ frac {(2\ cdot7+1)\ cdot1\ pi} {16}\ derecha)\\ end {array}\ derecha],\\\\ ldots,\ mathbf v_6 =\ izquierda [\ begin {array} {c}\ cos\ izquierda (\ frac {(2\ cdot0+1)\ cdot6\ pi} {16}\ derecha)\\ cos\ izquierda (\ frac {(2\ cdot1+1)\ cdot6\ pi} {16}\ derecha)\\ cos\ izquierda (\ frac {(2\ cdot2+1)\ cdot6\ pi} {16}\ derecha)\\\ vdots\\ cos\ izquierda (\ frac {(2\ cdot7+1)\ cdot6\ pi} {16}\ derecha)\\ end {array}\ derecha], &\ mathbf v_7 =\ left [\ begin {array} {c}\ cos\ left (\ frac { (2\ cdot0+1)\ cdot7\ pi} {16}\ derecha)\\\ cos\ izquierda (\ frac {(2\ cdot1+1)\ cdot7\ pi} {16}\ derecha)\\ cos\ izquierda (\ frac {(2\ cdot2+1)\ cdot7\ pi} {16}\ derecha)\\ vdots\ cos\ izquierda (\ frac {(2\ cdot7+1)\ cdot7\ pi} {16}\ derecha)\\ final {matriz}\ derecha]\ texto {.}\\\ final {alineado}\ final {ecuación*}

A primera vista, esto probablemente parezca intimidante, pero podemos darle sentido al mirar estos vectores gráficamente. En la Figura 3.3.7 se muestran cuatro de estos vectores base. Observe que\(\mathbf v_0\) es constantemente 1,\(\mathbf v_1\) varía relativamente lentamente,\(\mathbf v_2\) varía un poco más rápidamente, y\(\mathbf v_7\) varía bastante rápido. Esta es la observación principal: los vectores base varían a diferentes velocidades con los primeros vectores variando relativamente lentamente.

Figura 3.3.7. Cuatro de los vectores base\(\mathbf v_0\text{,}\)\(\mathbf v_1\text{,}\)\(\mathbf v_2\text{,}\) y\(\mathbf v_7\text{.}\)

Estos vectores forman la base\(\ccal\) para\(\mathbb R^8\text{.}\) Recordar que\(\mathbf x\) es el vector de valores de luminancia en la primera columna como se ve a la derecha. Escribiremos\(\mathbf x\) en las nuevas coordenadas

\ begin {ecuación*}\ coords {\ mathbf x} {\ ccal} =\ left [\ begin {array} {c} F_0\\ F_1\\ F_2\\\ vdots\\ F_7\ end {array}\ right]\ text {.} \ end {ecuación*}

Las coordenadas\(F_j\) se llaman los coeficientes de Fourier del vector\(\mathbf x\text{.}\)

Actividad 3.3.3.

Exploraremos la influencia que los coeficientes de Fourier tienen sobre el vector\(\mathbf x\text{.}\)

El siguiente diagrama le permite variar tres de los coeficientes de Fourier\(F_0\)\(F_3\),,\(F_7\) y observar el efecto sobre\({\mathbf x}\).

Tu navegador no es compatible con HTML5 Canvas.

1. Describe el efecto sobre el vector\(\mathbf x\) cuando varías\(F_0\text{.}\)
2. Ahora observa el efecto sobre\(\mathbf x\) cuándo\(F_3\) y\(F_7\) son variados. Comparar el efecto de\(F_0\text{,}\)\(F_3\text{,}\) y\(F_7\text{.}\)
3. Si el vector\(\mathbf x\) muestra solo pequeñas variaciones, ¿qué esperaría que fuera cierto de los coeficientes de Fourier?\(F_j\text{?}\)
4. La célula de Sage a continuación construirá el vector\(C_{\bcal}\text{,}\) que se denota C, y su inverso\(C_{\bcal}^{-1}\text{,}\) que se denota Cinv. Evalúa esta celda de Sage y observa que imprime la matriz\(C_{\bcal}^{-1}\text{.}\)
   Ahora mira la forma de\(C_{\bcal}^{-1}\) y explica por qué\(F_0\) es el promedio de los valores de luminancia en el vector\(\mathbf x\text{.}\)
5. La celda de Sage a continuación define el vector\(\mathbf x\text{,}\) que es el vector de valores de luminancia en la primera columna, como se ve en la Figura 3.3.6. Usa la celda de abajo para encontrar el vector\(\mathbf f\) de coeficientes de Fourier\(F_0,F_1,\ldots,F_7\text{.}\) Si has evaluado la celda anterior, aún podrás hacer referencia a C y Cinv en esta celda.
   Escriba los coeficientes de Fourier y discuta los tamaños relativos de los coeficientes.
6. Vemos que los coeficientes\(F_6\) y\(F_7\text{,}\) que corresponden a variaciones rápidas en los valores de luminancia, son bastante pequeños. Veamos qué pasa cuando los ignoramos. Formar un nuevo vector de coeficientes de Fourier redondeando los coeficientes al entero más cercano y estableciendo\(F_6\) y\(F_7\) a cero. Esta es una aproximación\(\mathbf f\text{,}\) al vector de coeficientes de Fourier. Utilice la aproximación\(\mathbf f\) para formar una aproximación del vector\(\mathbf x\text{.}\)
   ¿Cuánto difiere tu aproximación del vector real?\(\mathbf x\text{?}\)
7. Cuando ignoramos los coeficientes de Fourier correspondientes a elementos básicos que varían rápidamente, vemos\(\mathbf x\) que el vector que reconstruimos está muy cerca del original. De hecho, los valores de luminancia en la aproximación difieren como máximo en uno o dos de los valores de luminancia reales. Nuestros ojos no son lo suficientemente sensibles como para detectar esta diferencia.

   Hasta el momento, nos hemos concentrado en una sola columna en nuestro\(8\times8\) bloque de valores de luminancia. Consideremos ahora todas las columnas. La siguiente celda Sage define una matriz llamada luminancia, que es la\(8\times8\) matriz de valores de luminancia. Encuentra la\(8\times8\) matriz\(F\) cuyas columnas son los coeficientes de Fourier de las columnas de valores de luminancia.
8. Observe que la primera fila de esta matriz consiste en el coeficiente de Fourier\(F_0\) para cada una de las columnas. Tal como vimos antes, las entradas en esta fila no cambian significativamente a medida que nos movemos a través de la fila. En la celda de Sage a continuación, escribe estas entradas en el vector\(\yvec\) y encuentra los coeficientes de Fourier correspondientes.

Hasta este punto, hemos estado trabajando con los valores de luminancia en un\(8\times8\) bloque de nuestra imagen. Formamos los coeficientes de Fourier para cada una de las columnas de este bloque. Una vez que notamos que los coeficientes de Fourier a través de una fila son relativamente constantes, parece razonable encontrar los coeficientes de Fourier de las filas de la matriz de coeficientes de Fourier. Hacerlo lleva a la matriz

\ begin {ecuación*}\ left [\ begin {array} {rrrrrrrr} 160.6 & -4.0 & -4.8 & -1.7 & 0.0 & 0.9 & 0.8 & 0.3\\ 2.7 & 14.7 & 3.8 & 1.1 & -1.6 & -0.3 & -0.3 & -0.4\\ 3.8 & 7.0 & 2.1 & 2.9 & 0.8 & -0.2 & -0.3 & -0.3\\ - 2.4 y -3.9 y -1.9 y 0.1 & 1.2 y 1.2 & 0.7 & 0.1\\ -0.6 & -1.4 & -1.5 & -0.9 & 0.2 & -0.2 & -0.2 & -0.5\\ -0.7 & -1.6 & 0.0 & -1.1 & 0.0 & 0.3 & -0.1 & -0.2\\ -0.0 & -1.4 & 0.4 & 0.9 & 0.1 & -0.5 & 0.0 & 0.5\\ 0.0 & 0.2 & 0.3 & 0.3 & 0.0 & -0.0 & -0.0 & -0.2 & 0.0\\ end {array}\ derecho]\ text {.} \ end {ecuación*}

Si tuviéramos que mirar dentro de un archivo de imagen JPEG, veríamos muchas matrices como esta. Para cada\(8\times 8\) bloque, habría tres matrices de coeficientes de Fourier de las filas de coeficientes de Fourier, una matriz para cada uno de los valores de luminancia, crominancia azul y crominancia roja. Sin embargo, almacenamos estos coeficientes de Fourier como enteros dentro del archivo JPEG por lo que necesitamos redondear los coeficientes al entero más cercano, como se muestra aquí:

\ begin {ecuación*}\ left [\ begin {array} {rrrrrrrr} 161 & -4 & -5 & -2 & 0 & 1 & 1 & 0 & 0\ 3 & 15 & 4 & 1 & -2 & 0 & 0 & 0 & 0 & 7 & 2 & 3 & 1 & 0 & 0 & 0 & 0 & 0\ -2 & 0 & 2 & 0 & 0 & 1 & 1 & 0\\ -1 & -1 & -1 & -1 & 0 & 0 & 1 & 0 & 0 & 0\\ -1 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & -1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ end {array}\ derecho]\ texto {.} \ end {ecuación*}

Hay muchos ceros en esta matriz, y esta observación es donde podemos ahorrar espacio al crear un archivo de imagen JPEG: solo registraremos los coeficientes de Fourier distintos de cero.

De hecho, cuando se crea un archivo JPEG, hay un parámetro de “calidad” que se puede establecer, como el que se muestra en la Figura 3.3.8. Cuando el parámetro de calidad es alto, almacenaremos muchos de los coeficientes de Fourier; cuando sea bajo, ignoraremos más de ellos.

Figura 3.3.8. Al crear un archivo JPEG, elegimos un valor del parámetro “quality”.

Para ver cómo funciona esto, supongamos que el ajuste de calidad es relativamente alto. Después de redondear los coeficientes de Fourier, estableceremos todos los coeficientes cuyo valor absoluto es menor que 2 a cero, lo que crea la matriz:

\ begin {ecuación*}\ left [\ begin {array} {rrrrrrrr} 161 & -4 & -5 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ end {array}\ right]\ text {.} \ end {ecuación*}

Observe que hay 12 coeficientes de Fourier, de 64, que necesitamos registrar. En consecuencia, solo registramos\(12/64 \approx 19\%\) los datos.

Si en cambio, el ajuste de calidad es relativamente bajo, establecemos todos los coeficientes de Fourier cuyo valor absoluto es menor que 4 a cero, creando la matriz:

\ begin {ecuación*}\ left [\ begin {array} {rrrrrrrr} 161 & -4 & -5 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & amp; 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ end {array}\ derecha]\ text {.} \ end {ecuación*}

Observe que solo hay 5 coeficientes de Fourier distintos de cero que necesitamos registrar ahora, es decir, registramos solo\(5/64\approx 8\%\) de los datos. Esto dará como resultado un archivo JPEG más pequeño que describe la imagen.

Con un ajuste de menor calidad, hemos desechado más información sobre los coeficientes de Fourier para que la imagen no se reconstruya con la misma precisión. Para ver esto, podemos reconstruir los valores de luminancia a partir de los coeficientes de Fourier convirtiendo de nuevo en el sistema de coordenadas estándar. En lugar de mostrar los propios valores de luminancia, mostraremos la diferencia en los valores de luminancia originales y los valores de luminancia reconstruidos. Cuando el ajuste de calidad era alto y almacenamos 12 coeficientes de Fourier, encontramos que esta diferencia es

\ begin {ecuación*}\ left [\ begin {array} {rrrrrrrr} -7 & -7 & -1 & 3 & -2 & -1 & 0 & -1 & -1\\ 4 & 4 & 4 & -1 & -3 & 0 & -1 & -3\\ 1 & 3 & 0 & -7 & -3 & 1 & 3 & 3 & 3 & 3 & 3 & 3 & 1 & -5 y -2 & 1 & 2\\ 0 & -3 & 4 & 4 & -1 & -1 & -1 & -1 & -2\\ 2 & -5 & 3 & 1 & 1 & -1 & -1 & 1 & 1 & -2 & 4 & 3 & -4 & -6 & 2 & 3\\ 0 & -1 & 1 & -1 & -1 & -1 & -1 & 5\\\ end { array}\ derecho]\ texto {.} \ end {ecuación*}

Cuando el ajuste de calidad es menor y almacenamos solo 5 coeficientes de Fourier, la diferencia es

\ begin {ecuación*}\ left [\ begin {array} {rrrrrrrr} 3 & -3 & -2 & 0 & 0 & 7 & 10 & 10 & 10\ 14 & 11 & 6 & -1 & -1 & 3 & 4 & 4\\ 7 & 10 & 5 & -5 & -3 & -1 & 2 & 3\\ -10 & -3 & 5 & 2 & -8 & - 7 & -3 & -1\\ -12 & -11 & 2 & 2 & -5 & -7 & -6 & -6\\ -11 & -15 & -2 & -2 & -2 & -4 & -5 & -2 & -2 & -2\\ -3 & -6 & 2 & 3 & -2 & -5 & -4 & -1\\ 6 & 3 & 4 & 5 & 4 & 4 & 0 & -1 & ; 0\\\ end {array}\ derecha]\ text {.} \ end {ecuación*}

Esto demuestra la compensación. Con un ajuste de alta calidad, requerimos más almacenamiento para guardar más datos, pero la imagen reconstruida está más cerca de la original. Con el ajuste de menor calidad, requerimos menos almacenamiento, pero la imagen reconstruida difiere más de la original.

Si recordamos que la información visual almacenada por los valores de crominancia azul y rojo no es tan importante como la contenida en los valores de luminancia, nos sentimos más seguros al descartar más de los coeficientes de Fourier para los valores de crominancia resultando en un mayor ahorro.

En la Figura 3.3.9 se muestra la imagen original comparada con una versión almacenada con un ajuste de muy baja calidad. Si miras con atención, puedes\(8\times8\) bloques individuales.

Figura 3.3.9. La imagen original y el resultado de almacenar la imagen con un ajuste de baja calidad.

Esta descripción del algoritmo de compresión JPEG pretende transmitir las ideas que subyacen a su construcción. Hay algunos detalles, sobre todo sobre el redondeo de los coeficientes de Fourier, que no son estrictamente precisos. La implementación real es un poco más complicada, pero la presentación aquí transmite el espíritu del algoritmo.

Hemos descrito el algoritmo de compresión JPEG, que nos permite almacenar archivos de imagen usando solo una fracción de los datos. Ideas similares se utilizan para almacenar de manera eficiente archivos de música y video digitales.

Resumen

Esta sección ha explorado cómo los cambios apropiados en las bases nos ayudan a reconstruir una imagen usando solo una fracción de sus datos. Esto se conoce como compresión de imagen.

• Hay varias formas de representar colores, todas las cuales utilizan vectores en\(\mathbb R^3\text{.}\) Exploramos el modelo de\(RGB\) color, que es apropiado en aplicaciones digitales, y el\(YC_bC_r\) modelo, en el que la información visual más importante es transmitida por la\(Y\) coordenada, conocida como lumninance.
• También exploramos un cambio de base llamado Transformada Discreta de Fourier. En el sistema de coordenadas que resulta, la primera coordenada mide el promedio de los componentes de un vector. Los componentes subsiguientes miden las desviaciones del promedio.
• Ponemos ambas ideas a usar para demostrar el algoritmo de compresión JPEG. Una imagen se divide en\(8\times8\) bloques y los colores en luminancia, crominancia azul y crominancia roja. La aplicación de la Transformada Discreta de Fourier nos permitió reconstruir una buena aproximación de la imagen utilizando solo un pequeño número de coeficientes de Fourier.

Ejercicios 3.3.4Ejercicios

1

Considera el vector\(\mathbf x=\left[\begin{array}{r} 103 \\ 94 \\ 91 \\ 92 \\ 103 \\ 105 \\ 105 \\ 108 \end{array}\right] \text{.}\)

1. En la celda de Sage a continuación hay una copia del cambio de matrices de base que definen la transformada de Fourier. Encuentra los coeficientes de Fourier de\(\mathbf x\text{.}\)
2. Ahora formaremos el vector\(\yvec\text{,}\) que es una aproximación de\(\mathbf x\text{.}\) Para ello, redondea todos los coeficientes de Fourier de\(\mathbf x\) al entero más cercano para obtener\(\coords{\yvec}{\ccal}\text{.}\) Si un coeficiente tiene un valor absoluto menor que uno, ponlo igual a cero. Ahora encuentra el vector\(\yvec\) y compara esta aproximación con\(\mathbf x\text{.}\) ¿Cuál es el error en esta aproximación?
3. Repita la última parte de este problema, pero establezca los coeficientes redondeados de Fourier en cero si tienen un valor absoluto menor a cinco. Úsalo para crear una segunda aproximación de\(\mathbf x\text{.}\) ¿Cuál es el error en esta aproximación?
4. Compara el número de coeficientes de Fourier distintos de cero que tienes en las dos aproximaciones y compara la precisión de las aproximaciones. Usando algunas frases, discuta las comparaciones que encuentres.

2

Hay varios pasos para el algoritmo de compresión JPEG. Las siguientes preguntas examinan la motivación detrás de algunas de ellas.

1. ¿Cuál es el objetivo general del algoritmo de compresión JPEG?
2. ¿Por qué convertimos colores del modelo de\(RGB\) color al\(YC_bC_r\) modelo?
3. ¿Por qué descomponemos la imagen en una colección de\(8\times8\) matrices de píxeles?
4. ¿Qué papel juega la Transformada Discreta de Fourier en el algoritmo de compresión JPEG?
5. ¿Por qué la información transmitida por los coeficientes de Fourier de variación rápida, en términos generales, es menos importante que los coeficientes de variación lenta?

3

La transformada de Fourier que usamos en esta sección a menudo se llama Transformada Discreta de Coseno de Fourier porque se define usando una base\(\ccal\) que consiste en funciones coseno. También hay una Transformada Sinusoidal de Fourier definida usando una base\(\scal\) que consiste en funciones sinusoidales. Por ejemplo, en\(\mathbb R^4\text{,}\) los vectores base de\(\scal\) son

\ begin {ecuation*}\ begin {aligned}\ mathbf v_1 =\ left [\ begin {array} {c}\ sin\ left (\ frac {1\ cdot1\ pi} {8}\ derecha)\\\ sin\ izquierda (\ frac {3\ cdot1\ pi} {8}\ derecha)\\ sin\ izquierda (\ frac {5\ cdot1\ pi} {8}\ derecha)\\\ sin\ izquierda (\ frac {7\ cdot1\ pi} {8}\ derecha)\\ end {array}\ derecha], &\ mathbf v_2 =\ left [\ begin {array} {c}\ sin\ left (\ frac {1\ cdot2\ pi} {8}\ derecha)\\ sin\ izquierda (\ frac {3\ cdot2\ pi} {8}\ derecha)\\\ sin\ izquierda (\ frac {5\ cdot2\ pi} {8}\ derecha)\\\ sin\ izquierda (\ frac {7\ cdot2\ pi} {8}\ derecha)\\ final {array}\ derecha],\\\\ mathbf v_3 =\ izquierda [\ begin {array} {c}\ sin\ izquierda (\ frac {1\ cdot3\ pi} {8}\ derecha)\\\ sin\ izquierda (\ frac {3\ cdot3\ pi} {8}\ derecha)\\\ sin\ izquierda (\ frac {5\ cdot3\ pi} {8}\ derecha)\\\ sin\ izquierda (\ frac {7\ cdot3\ pi} {8}\ derecha)\\ end {array}\ derecha], &\ mathbf v_4 =\ izquierda [\ begin {array} {c}\ sin\ izquierda (\ frac {1\ cdot4\ pi} {8}\ derecha)\\ sin\ izquierda (\ frac {3\ cdot4\ pi} {8}\ derecha)\\\ sin\ izquierda (\ frac {5\ cdot4\ pi} {8}\ derecha)\\\ sin\ izquierda (\ frac {7\ cdot4\ pi} {8}\ derecha)\\ end {array}\ derecha]\ texto {.}\\\ final {alineado}\ final {ecuación*}

Podemos pensar en estos vectores gráficamente, como se muestra en la Figura 3.3.10.

Figura 3.3.10. Los vectores\(\mathbf v_1,\mathbf v_2,\mathbf v_3,\mathbf v_4\) que forman la base\(\scal\text{.}\)

1. La celda de Sage a continuación define la matriz S cuyas columnas son los vectores en la base así\(\scal\) como la matriz C cuyas columnas forman la base\(\ccal\) utilizada en la Transformada de Coseno de Fourier.

   En el\(8\times8\) bloque de valores de luminancia que consideramos en esta sección, la primera columna comienza con las cuatro entradas 176, 181, 165 y 139, como se ve en la Figura 3.3.6. Estos forman el vector\(\mathbf x=\fourvec{176}{181}{165}{139}\text{.}\) Encuentra ambos\(\coords{\mathbf x}{\scal}\) y\(\coords{\mathbf x}{\ccal}\text{.}\)

2. Escribir una oración o dos comparando los valores de los coeficientes del seno de Fourier\(\coords{\mathbf x}{\scal}\) y los coeficientes del coseno de Fourier\(\coords{\mathbf x}{\ccal}\text{.}\)
3. Supongamos ahora que\(\mathbf x=\fourvec{100}{100}{100}{100}\text{.}\) Encuentra los coeficientes del seno de Fourier\(\coords{\mathbf x}{\scal}\) y los coeficientes del coseno de Fourie\(\coords{\mathbf x}{\ccal}\text{.}\)
4. Escribe algunas frases explicando por qué usamos la Transformada de Coseno de Fourier en el algoritmo de compresión JPEG en lugar de la Transformada Senoidal de Fourier.

4

En el Ejemplo 3.2.7, miramos una base para\(\mathbb R^4\) eso que llamamos la base de ondículas de Haar. Los vectores base son

\ begin {ecuación*}\ mathbf v_1=\ fourvec {1} {1} {1} {1},\ mathbf v_2=\ fourvec {1} {1} {-1} {-1},\ mathbf v_3=\ fourvec {1} {-1} {0} {0},\ mathbf v_4=\ fourvec {0} 0} {1} {-1}\ texto {,}\ final {ecuación*}

que puede entenderse gráficamente como en la Figura 3.3.11. Vamos a denotar esta base por\(\wcal\text{.}\)

Figura 3.3.11. La base de ondículas de Haar se representó gráficamente.

El cambio de coordenadas de un vector\(\mathbf x\) en\(\mathbb R^4\) a\(\coords{\mathbf x}{\wcal}\) se llama la transformada de wavelet Haar y escribimos

\ begin {ecuación*}\ coords {\ mathbf x} {\ wcal} =\ fourvec {H_1} {H_2} {H_3} {H_4}\ text {.} \ end {ecuación*}

Los coeficientes\(H_1,H_2,H_3,H_4\) se denominan coeficientes de ondícula.

Trabajemos con el\(4\times4\) bloque de valores de luminancia en la esquina superior izquierda de nuestro\(8\times8\) bloque más grande:

\ begin {ecuation*}\ left [\ begin {array} {rrrr} 176 & 170 & 170 & 169\\ 181 & 179 & 175 & 167\\ 165 & 170 & 169 & 161\\ 139 & 150 & 164 & 166\ end {array}\ right]\ text {.} \ end {ecuación*}

1. La siguiente celda Sage define la matriz W cuyas columnas son los vectores base en\(\wcal\text{.}\) Si\(\mathbf x\) es la primera columna de valores de luminancia en el\(4\times4\) bloque anterior, encuentra los coeficientes de wavelet\(\coords{\mathbf x}{\wcal}\text{.}\)
2. Observe que\(H_1\) da el valor promedio de los componentes de\(\mathbf x\) y\(H_2\) describe cómo los promedios de los dos primeros y dos últimos componentes difieren del promedio general. Los coeficientes\(H_3\) y\(H_4\) describen variaciones a pequeña escala entre los dos primeros componentes y los dos últimos componentes, respectivamente.

   Si establecemos los últimos coeficientes de wavelet\(H_3=0\) y\(H_4=0\text{,}\) obtenemos los coeficientes wavelet\(\coords{\yvec}{\wcal}\) para un vector\(\yvec\) que se aproxima\(\mathbf x\text{.}\) Encuentra el vector\(\yvec\) y lo comparamos con el vector original\(\mathbf x\text{.}\)

3. ¿Qué impacto tiene el hecho de que\(H_3=0\) y\(H_4=0\) tienen en la forma del vector\(\yvec\text{?}\) Explicar cómo establecer estos coeficientes a cero ignora el comportamiento de\(\mathbf x\) a pequeña escala.
4. En el algoritmo de compresión JPEG, observamos los coeficientes de Fourier de todas las columnas de valores de luminancia y luego realizamos una transformada de Fourier en las filas. La celda de Sage a continuación realizará la misma operación usando la transformada wavelet; es decir, primero encontrará los coeficientes wavelet de cada una de las columnas y luego realizará la transformada wavelet en las filas. Solo es necesario evaluar la celda para encontrar los coeficientes wavelet obtenidos de esta manera.
5. Ahora establece todos los coeficientes de wavelet iguales a cero excepto los del\(2\times2\) bloque superior izquierdo y úsalos para definir los coeffs de la matriz en la celda de Sage a continuación. Esto tiene el efecto de ignorar todas las diferencias a pequeña escala. Al evaluar esta celda se recuperarán los valores aproximados de luminancia.
6. Explique cómo la transformada wavelet y esta aproximación se pueden utilizar para crear una versión de menor resolución de la imagen.

Este tipo de transformada wavelet es la base del algoritmo de compresión JPEG 2000, que es una alternativa al algoritmo JPEG habitual.

5

En esta sección, nos fijamos en los modelos\(RGB\) y\(YC_bC_r\) color. En este ejercicio, veremos el modelo de\(HSV\) color donde\(H\) está el matiz,\(S\) es la saturación, y\(V\) es el valor del color. Las tres cantidades varían entre 0 y 255.

El siguiente diagrama le permite variar los tres parámetros\(H\),\(S\), y\(V\) en el modelo\(HSV\) de color.

Tu navegador no es compatible con HTML5 Canvas.

1. Si te vas\(S\) y\(V\) en algunos valores fijos, ¿qué sucede cuando cambias el valor de\(H\text{?}\)
2. Mueva el valor\(V\) a la derecha y manténgalo fijo. Describe lo que sucede cuando varías la saturación\(S\) usando un tono\(H\) y un valor fijos\(V\text{.}\)
3. Describir lo que sucede cuando\(H\) y\(S\) son fijos y\(V\) varían.
4. ¿Cómo se puede crear el blanco en este modelo de color?
5. ¿Cómo se puede crear el negro en este modelo de color?
6. Encuentra un rango aproximado de tonalidades que corresponden al azul.
7. Encuentra un rango aproximado de tonalidades que corresponden al verde.

El modelo de\(YC_bC_r\) color concentra la información visual más importante en la coordenada de luminancia, que mide aproximadamente el brillo del color. Las otras dos coordenadas describen la tonalidad del color. Por el contrario, el modelo de\(HSV\) color concentra toda la información sobre el matiz en la\(H\) coordenada.

Esto es útil en aplicaciones de visión por computador. Por ejemplo, si queremos que un robot detecte una bola azul en su campo de visión, podemos especificar un rango de valores de tono para buscar. Si la iluminación cambia en la habitación, la saturación y el valor pueden cambiar, pero el tono no lo hará. Esto aumenta la probabilidad de que el robot aún detecte la bola azul en una amplia gama de condiciones de iluminación.