Tablas de consulta (lookup table)

Más que un algoritmo de visión por computador es una forma de acelerar los cálculos. La idea es reemplazar todos los cálculos aplicados a un pixel por un simple acceso a memoria. Suena bien ¿verdad?. Se puede ganar bastante velocidad pero por desgracia está limitado y solo sirve para operaciones que afecten a un solo canal del pixel. Si el resultado se ve influido por algo más como la posición, el valor de los vecinos o del resto de los canales este método no sirve. Aun con estas limitaciones resulta útil para optimizar operaciones como el umbral, el ajuste de brillo y/o contraste o corrección del color.
Empecemos por la idea básica. A partir de ahora cuando hable de pixel me refiero a un pixel de un solo canal en escala de grises, para el caso de color RGB seria en realidad uno de los canales de color. Y habría que tener una tabla de consulta por cada canal.
Un pixel tiene un número limitado de valores, de 0 a 255. Eso significa que podemos precalcular esos 256 valores en una tabla y luego simplemente consultar el valor del pixel en esta en lugar de repetir los calculos para cada pixel.
Por tanto necesitamos generar una tabla con indices de 0 a 255. Calculamos el resultado para cada uno de los 256 posibles valores de un pixel. Cada resultado se almacenará en la posición correspondiente al valor original del pixel. Por ejemplo si nuestra funcion suma diez al valor del pixel, la tabla seria:
T[0]=10;
T[1]=11;

T[254]=255;
T[255]=255;
Si os fijais hay un detalle a tener en cuenta. Los valores de la tabla no pueden ser mayores de 255 que es el valor máximo de un pixel, tampoco pueden ser menores de 0, que es el valor mínimo.
Vale, ya tenemos los 256 valores posibles. Para usar esta tabla solo hemos de recorrer la imagen leyendo el valor de cada pixel y remplazarlo el valor que tenga la tabla para ese índice. Por ejemplo, para un pixel P con valor I y una tabla de consulta T
Image[P] = T[I]
Pero esto no es todo, puedes combinar varias de estas tablas en una sola tabla y calcular varias operaciones con un coste en tiempo ridiculo. Vamos a ver cómo.
Cuando operamos varias veces sobre un pixel de valor p realmente lo que estamos haciendo es.
funN(…func2(func1(p)))
Para cada cada pixel solo hay 256 valores posibles (del 0 al 255), eso quiere decir para cada función habra como mucho 256 resultados distintos. Si ademas limitamos que cada una de esas funciones solo pueda devolver valores entre 0 y 255. Podemos usar el resultado de una función como entrada de la siguiente. Por lo tanto podriamos precalcular esos 256 valores y convertir todas esas funciones en una sola que relacione cada valor del pixel con su resultado…efectivamente eso es lo mismo que hacer un array con los 256 resultados y usar el valor original como indice.
Repito, esto solo se cumple cuando sobre la función que aplicamos solo influye el valor del propio pixel y los valores que devuelve están comprendidos entre 0 y 255.

Si tenemos dos tablas de T1 y T2 calcular una tabla T3 que combine ambas en una sola operación es muy sencillo:

i = 0..255
T3[i]=T2[T1[i]];

Se pueden combinar tantas tablas como se quiera.

Aunque en los procesadores actuales resulta casi igual de rápido realizar un par de operaciones simples que recurrir a estas tablas, cuando se acumulan varias funciones en una sola tabla el aumento de rendimiento es más que apreciable.