Transformación de cuantificación media sucesiva optimizada

El algoritmo de transformación de cuantificación media sucesiva (SMQT) es una transformación no lineal que revela la organización o estructura de los datos y elimina propiedades como la ganancia y el sesgo. En un documento titulado La transformación de cuantificación media sucesiva, SMQT se "aplica en el procesamiento del habla y el procesamiento de imágenes". El algoritmo, cuando se aplica a las imágenes, "puede verse como un enfoque progresivo en los detalles de una imagen".

Según otro documento titulado Operadores de mapeo de tonos basados ​​en SMQT para imágenes de alto rango dinámico, producirá una "imagen con detalles mejorados". El documento describe dos técnicas para aplicar esta transformación a una imagen.

1. Aplicar SMQT en la luminancia de cada píxel: describe la fórmula para obtener la luminancia del RGB de cada píxel.

2. Aplique SMQT en cada canal de RGB por separado, para los canales R, G y B individualmente.

La siguiente imagen muestra el resultado de las dos técnicas:

Al aplicar la segunda técnica a una imagen del Teatro Bruin por la noche, podemos ver cómo el algoritmo amplía progresivamente los detalles de la imagen y revela detalles que originalmente estaban ocultos por la oscuridad:

En este artículo, veremos más de cerca cómo funciona este algoritmo y exploraremos una optimización simple que permite que el algoritmo sea mucho más eficaz en aplicaciones prácticas de procesamiento de imágenes.

El algoritmo SMQT

En el artículo original, el algoritmo se describe de manera abstracta. Para comprender mejor SMQT, veremos algunos ejemplos simples.

Supongamos que tenemos el siguiente vector (puede pensar en él como una matriz):

En el caso de una imagen en color, podemos pensar en ella como tres vectores separados, cada uno de los cuales representa un canal de color particular (RGB) y cada elemento del vector representa la intensidad del píxel correspondiente.

Los pasos involucrados en la aplicación del algoritmo SMQT son:

1. Calcula la media del vector, que en este caso es 29,58.

2. Divida el vector en dos, dejando los números menores o iguales a 29,58 en la mitad izquierda y los números mayores en la mitad derecha:

   15	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	1	1	1	1	1	1	1

   La segunda fila es el código que crearemos para cada valor. Los valores menores o iguales a 29.58 obtienen un 0 en su código, y los números mayores a 29.58 obtienen un 1 (esto es binario).

3. Ahora ambos vectores resultantes se dividen individualmente, de forma recursiva, siguiendo la misma regla. En nuestro ejemplo, la media del primer vector es (15 + 4 + 0 + 5 + 18) / 5 = 8,4, y la media del segundo vector es (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48,7. Cada uno de esos dos vectores se divide en dos vectores más, y se agrega un segundo bit de código a cada uno dependiendo de su comparación con la media. Este es el resultado:

   4	0	5	15	18	32	47	31	48	60	64	59
   00	00	00	01	01	10	10	10	11	11	11	11

   Tenga en cuenta que se agregó un 0 nuevamente para los números menores o iguales a la media (para cada vector) y un 1 para los números mayores que la media.

4. Este algoritmo se repite recursivamente:

   0	4	5	15	18	32	31	47	48	60	64	59
   000	001	001	010	011	100	100	101	110	111	111	111

   0	4	5	15	18	31	32	47	48	60	59	64
   0000	0010	0011	0100	0110	1000	1001	1010	1100	1110	1110	1111

   0	4	5	15	18	31	32	47	48	59	60	64
   00000	00100	00110	01000	01100	10000	10010	10100	11000	11100	11101	11110

   En este punto, cada vector tiene un solo elemento. Entonces, para cada paso sucesivo, se agregará un 0, ya que el número siempre será igual a sí mismo (la condición para un 0 es que el número debe ser menor o igual que la media, que es él mismo).

Hasta ahora tenemos un nivel de cuantificación de L=5. Si fuéramos a usar L=8, debemos agregar tres 0 a cada código. El resultado de convertir cada código de binario a entero (para L=8) sería:

El vector final se ordena en orden creciente. Para obtener el vector de salida, debemos sustituir el valor original del vector de entrada por su código.

Observe que en el vector resultante:

• Se eliminó la ganancia. El original tenía una ganancia baja, con un rango de 0 a 64. Ahora su ganancia va de 0 a 240, que es casi todo el rango de 8 bits. Se dice que se elimina la ganancia porque no importa si multiplicamos todos los elementos del vector original por un número, como 2, o si dividimos todo por 2, el vector de salida sería aproximadamente el mismo. Su rango sería aproximadamente el rango completo del vector de destino (8 bits para L=8). Si multiplicamos el vector de entrada por dos, en realidad el vector de salida será el mismo, porque en cada paso los mismos números que estaban por debajo o por encima de la media seguirán estando por debajo o por encima de ella, y sumaremos los mismos 0 o 1 a la salida. Solo si lo dividimos el resultado sería más o menos el mismo, y no exactamente el mismo, porque los números impares como el 15 habrá que redondearlos y los cálculos pueden variar entonces. Pasamos de una imagen oscura a una imagen con píxeles que van desde colores oscuros (0) hasta colores más claros (240), utilizando todo el rango.
• Se elimina el sesgo, aunque no podemos observarlo del todo en este ejemplo. Esto se debe a que no tenemos un sesgo ya que nuestro valor más bajo es 0. Si realmente tuviéramos un sesgo, se habría eliminado. Si tomamos cualquier número 'K' y lo agregamos a cada elemento del vector de entrada, el cálculo de los números por encima y por debajo de la media en cada paso no variará. La salida seguirá siendo la misma. Esto también haría que las imágenes que son demasiado brillantes se conviertan en imágenes que varían de colores oscuros a claros.
• Tenemos una imagen con detalles mejorados. Tenga en cuenta cómo para cada paso recursivo que tomamos, en realidad estamos ampliando los detalles y construyendo la salida al revelar esos detalles tanto como sea posible. Y como aplicaremos esta técnica a cada canal RGB, revelaremos la mayor cantidad de detalles posibles, aunque perdiendo información sobre los tonos originales de cada color.

Dada una imagen como un vector de píxeles RGB, cada punto tiene 8 bits para R, 8 para G y 8 para B; podemos extraer tres vectores de él, uno para cada color, y aplicar el algoritmo a cada vector. Luego volvemos a formar el vector RGB a partir de esos tres vectores de salida y tenemos la imagen procesada SMQT, como se hizo con la del Teatro Bruin.

Complejidad

El algoritmo requiere que para cada nivel de cuantificación (L), N elementos deben ser inspeccionados en un primer paso para encontrar la media de cada vector, y luego en un segundo paso, cada uno de esos N elementos debe ser comparado con la media correspondiente en para dividir cada vector a su vez. Finalmente, los N elementos deben ser sustituidos por sus códigos. Por lo tanto, la complejidad del algoritmo es O((L*2*N) + N) = O((2*L + 1)*N), que es O(L*N).

El gráfico extraído del artículo es consistente con la complejidad O(L*N). Cuanto menor sea la L, más rápido será el procesamiento de forma aproximadamente lineal (mayor número de fotogramas por segundo). Para mejorar la velocidad de procesamiento, el documento sugiere reducir los valores de L: "seleccionar un nivel L más bajo puede ser una forma directa de reducir la velocidad de procesamiento pero con una calidad de imagen reducida".

Mejora

Aquí encontraremos una manera de mejorar la velocidad sin reducir la calidad de la imagen. analizaremos el proceso de transformación y encontraremos un algoritmo más rápido. Para tener una perspectiva más completa de esto, veamos un ejemplo con números repetidos:

Los vectores ya no se pueden dividir y se deben agregar ceros hasta que lleguemos a la L deseada.

Por simplicidad, supongamos que la entrada puede ir de 0 a 31, y la salida de 0 a 7 (L=3), como se puede ver en el ejemplo.

Tenga en cuenta que calcular la media del primer vector (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 da el mismo resultado que calcular la media de todo el último vector, ya que es simplemente el mismo vector con los elementos en diferente orden: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

En el segundo paso, debemos calcular cada vector recursivamente. Entonces calculamos la media de las entradas en gris, que son los primeros 6 elementos ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8), y la media de la entrada en blanco, que son los últimos 4 elementos ((25 + 31 + 31 + 25) / 4 = 28):

Nótese nuevamente que si usamos el último vector, el que está completamente ordenado, los resultados son los mismos. Para los primeros 6 elementos tenemos: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8), y para los últimos 4 elementos: ((25 + 25 + 31 + 31) / 4 = 28) . Como es solo una adición, el orden de los sumandos no importa.

Lo mismo aplica para el siguiente paso:

Los cálculos son los mismos que con el último vector: ((7 + 1 + 1 + 7) / 4 = 4) será igual a ((1 + 1 + 7 + 7) / 4 = 4).

Y lo mismo ocurrirá con el resto de vectores y pasos.

El cálculo de la media es simplemente la suma de los valores de los elementos en el intervalo, dividida por el número de elementos en el intervalo. Esto significa que podemos precalcular todos esos valores y evitar repetir este cálculo L veces.

Veamos los pasos para aplicar lo que llamaremos algoritmo FastSMQT a nuestro ejemplo:

1. Crea una tabla con 32 columnas y 3 filas como puedes ver a continuación. La primera fila de la tabla representa el índice de la tabla (0 a 31) y no es necesario incluirla al codificar la tabla. Pero se muestra explícitamente para que el ejemplo sea más fácil de seguir.

2. Iterar los N elementos una vez contando la frecuencia de cada valor. En nuestro ejemplo, los elementos 1, 7, 16, 25 y 31 tienen una frecuencia de 2. Todos los demás elementos tienen una frecuencia de 0. Este paso tiene una complejidad de O(N).

3. Ahora que el vector de frecuencia está lleno, necesitamos iterar ese vector (el vector de frecuencias, no el vector de entrada). Ya no iteramos N elementos, sino R (R está en el rango: 2^L), que en este caso es 32 (0 a 31). Al procesar píxeles, N puede ser muchos millones (megapíxeles), pero R suele ser 256 (un vector para cada color). En nuestro ejemplo es 32. Completaremos las siguientes dos filas de la tabla al mismo tiempo. La primera de esas filas (la segunda de la tabla) tendrá la suma de las frecuencias hasta el momento. El segundo (el tercero de la tabla) tendrá la suma del valor de todos los elementos que aparecieron hasta el momento.

   En nuestro ejemplo, cuando llegamos a 1, ponemos un 2 en la segunda fila de la tabla porque hasta ahora han aparecido dos 1. Y también ponemos un 2 en la tercera fila de la tabla, porque 1 + 1 = 2. Seguimos escribiendo esos dos valores en cada una de las siguientes posiciones hasta llegar al 7. Como el número 7 aparece dos veces, sumamos 2 al acumulador de la segunda fila, porque ahora aparecieron 4 números hasta ahora (1, 1, 7, 7). Y le sumamos 7 + 7 = 14 a la tercera fila, resultando 2 + 14 = 16, porque 1 + 1 + 7 + 7 = 16. Seguimos con este algoritmo hasta terminar de iterar esos elementos. La complejidad de este paso es O(2^L), que en nuestro caso es O(32), y cuando se trabaja con píxeles RGB es O(256).

   I	0	1	2	...	6	7	8	...	15	dieciséis	17	...	24	25	26	...	30	31
   norte	0	2	0	...	0	2	0	...	0	2	0	...	0	2	0	...	0	2
   n-acumulativo	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
   suma	0	2	2	...	2	dieciséis	dieciséis	...	dieciséis	48	48	...	48	98	98	...	98	160

4. El siguiente paso es eliminar de la tabla las columnas con elementos que tienen una frecuencia de 0, y para ver el ejemplo más claro también eliminaremos la segunda fila ya que ya no es relevante, como verás.

   I	1	7	dieciséis	25	31
   norte	2	4	6	8	10
   suma	2	dieciséis	48	98	160

5. Recuerda que podríamos usar el último vector (completamente ordenado) para hacer los cálculos de cada paso y los resultados seguirán siendo los mismos. Tenga en cuenta que aquí, en esta tabla, tenemos el último vector con todos los cálculos previos ya realizados.

   Básicamente necesitamos hacer el algoritmo SMQT en este pequeño vector, pero a diferencia de hacerlo en el vector original con el que comenzamos, este será mucho más fácil.

   Primero necesitamos calcular la media de todas las muestras. Podemos encontrarlo fácilmente por: sum[31] / n[31] = 160 / 10 = 16. Entonces dividimos la tabla en dos vectores y comenzamos a escribir el código binario para cada uno:

   I	1	7	dieciséis	25	31
   norte	2	4	6	8	10
   suma	2	dieciséis	48	98	160
   código	0	0	0	1	1

   Ahora volvemos a dividir cada vector. La media del primer vector es: sum[16] / n[16] = 48 / 6 = 8. Y la media del segundo vector es: (sum[31] – sum[16]) / (n[31] – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   I	1	7	dieciséis	25	31
   norte	2	4	6	8	10
   suma	2	dieciséis	48	98	160
   código	00	00	01	10	11

   Solo queda un vector por dividir. La media es: suma[7] / n[7] = 16 / 4 = 4.

   I	1	7	dieciséis	25	31
   norte	2	4	6	8	10
   suma	2	dieciséis	48	98	160
   código	000	001	010	100	110

   Como puede ver, el código para cada elemento es el mismo si hubiéramos seguido el algoritmo original. E hicimos el SMQT en un vector mucho más pequeño que el que tiene N elementos y también hemos calculado previamente todos los valores que necesitamos para encontrar la media, por lo que es sencillo y rápido calcular el vector resultante.

   La complejidad de este paso es O(L*(2^L)), que para L=8, y en necesidades prácticas de procesamiento de imágenes, es O(8*(256)) = O(2048) = constante.

6. El paso final es iterar N elementos una vez más reemplazando el elemento por su código para cada elemento: elemento[i] = código[i]. La complejidad es O(N). La complejidad de FastSMQT es O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)) .

Paralelismo

Ambos algoritmos se pueden paralelizar, aunque es más eficiente ejecutar un algoritmo por núcleo si se deben transformar varios vectores. Por ejemplo, al procesar imágenes, podemos procesar cada canal RGB en un núcleo diferente en lugar de paralelizar cada uno de esos tres cálculos.

Para paralelizar el algoritmo SMQT, cuando dividimos un vector en dos, podemos procesar cada subvector en un nuevo núcleo si hay un núcleo disponible (en realidad, un subvector en el núcleo actual y el otro en un nuevo núcleo). Esto se puede hacer de forma recursiva hasta llegar al número total de núcleos disponibles. Los reemplazos de valores por códigos también se pueden hacer en paralelo.

El algoritmo FastSMQT también se puede paralelizar. En el primer paso, el vector de entrada debe dividirse en el número de núcleos disponibles (C). Se debe crear un vector de conteo de frecuencia para cada una de esas partes y se debe llenar en paralelo. Luego sumamos los valores de esos vectores en un vector resultante de frecuencias. El siguiente paso que se puede paralelizar es el último, cuando estamos sustituyendo los valores por sus códigos. Esto se puede hacer en un paralelo para.

Comparación de complejidad

La complejidad total del algoritmo SMQT original es O((2*L + 1)*N), que es O(L*N).

La complejidad de FastSMQT es O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)).

Dado un L fijo, la complejidad se convierte en O(N) para ambos. Pero la constante que multiplica N es mucho más pequeña para FastSMQT y, como veremos, hace una gran diferencia en el tiempo de procesamiento.

El siguiente gráfico compara el rendimiento de los algoritmos SMQT y FastSMQT para L=8, que es el caso del procesamiento de imágenes. El gráfico muestra el tiempo (en milisegundos) que se tarda en procesar N elementos. Tenga en cuenta que la complejidad (con constantes) de SMQT para L=8 es O(17*N), mientras que para FastSMQT es O(2*N + 2304).

Cuanto mayor sea la N, más tardará SMQT en procesar la imagen. Para FastSMQT, por otro lado, el crecimiento es mucho más lento.

Para valores de N aún mayores, la diferencia de rendimiento es mucho más evidente:

Aquí, SMQT tarda varios segundos en procesar ciertas imágenes, mientras que FastSMQT aún se encuentra dentro de la zona de "pocos milisegundos".

Incluso con varios núcleos (dos, en este caso), FastSMQT sigue siendo claramente superior a solo SMQT:

FastSMQT no depende de L. SMQT, por otro lado, depende linealmente del valor de L. Por ejemplo, con N = 67108864, el tiempo de ejecución de SMQT aumenta al aumentar el valor de L, mientras que FastSMQT no:

Conclusión

No todas las técnicas de optimización son aplicables para todos los algoritmos, y la clave para mejorar el rendimiento de un algoritmo a menudo se oculta dentro de una idea de cómo funciona el algoritmo. Este algoritmo FastSMQT aprovecha las posibilidades de precalcular valores y la naturaleza de los cálculos medios. Como resultado, permite un procesamiento más rápido que el SMQT original. La velocidad no se ve afectada por el incremento de L, aunque L no puede ser mucho mayor que los 8 habituales porque el uso de memoria es 2^L, que para 8 es un 256 aceptable (número de columnas en nuestra tabla de frecuencia), pero la ganancia de rendimiento tiene beneficios prácticos obvios.

Esta mejora en la velocidad permitió a MiddleMatter implementar el algoritmo en una aplicación de iOS (y una aplicación de Android) que mejora las imágenes y los videos capturados en condiciones de poca luz. Con esta mejora, fue posible realizar el procesamiento de video en la aplicación, que de otro modo sería demasiado lento para los dispositivos iOS.

El código C++ para los algoritmos SMQT y FastSMQT está disponible en GitHub.