Operaciones con el histograma

A nivel de programación podemos ver el histograma de un conjunto de valores como un array donde se asocia a cada posible valor del conjunto a un indice donde se almanacena el número de veces que aparece ese valor en el conjunto de datos. Es habitual usarlos con imágenes. Así que vamos a usarlo como ejemplo, pero estos cálculos son aplicables para cualquier histograma.

Empezando por el caso más simple, el de una imagen en escala de grises con 8 bits de profundidad. Su histograma es el número de pixeles que hay de cada valor (0-255). Se calcula con un procedimiento tan simple como recorrer la imagen e ir contando el número de pixels de cada intensidad .

Histograma de un solo canal (escala de grises)
var histograma = [];
for(var i = 0; i < pixels.length; i++){
  histograma[pixels[i]] = histograma[pixels[i]]+1 || 0;
}

Para el caso de una imagen RGB lo que habitualmente se hace es calcular un histograma por cada canal, por lo que tendremos tres histogramas. Se podria hacer un histograma contando cada una de las posibles combinaciones que hay de los tres canales RGB, pero son mas de dieciséis millones y quedaba un histograma demasiado grande para ser manejable

Histograma RGB.

Vale, ya sabemos que es y como se calcula ¿Para qué demonios sirve? Para conocer la distribución de las distintas intensidades en la imagen. Por ejemplo, si la mayoría de los pixeles están en los valores bajos la imagen será oscura y posiblemente estará subexpuesta. Por el contrario si se concentran en los valores altos la imagen será luminosa y podría estar sobreexpuesta.

El histograma normalizado es un histograma cuyos valores se han ajustado para que la suma de todos sus valores sea 1. Se calcula dividiendo cada valor del histograma entre el número total de píxeles que tiene la imagen. Resulta útil para trabajar con histogramas que procedan de distintas fuentes ya que el número de píxeles puede no ser equivalente. Lo que indica es la proporción de píxeles sobre el total. Hay que recordar que el total de píxeles de la imagen es igual a la suma de los valores de todo el histograma

var total = 0;
for(var i = 0; i < histograma.lentgh; i++)}
  total += histograma[i];
}
var normalizado = [];
for(var i = 0; i < histograma.lentgh; i++)}
  normalizado[i] = histograma[i]/total;
}

El histograma acumulado indica cuantos píxeles tienen un valor igual o inferior a uno dado. Se calcula sumando a cada posición del histograma la suma de las anteriores.

var acumulado = [];
acumulado[0] = histograma[0];
for(var i = 1; i < histograma.lentgh; i++)}
  acumulado[i] = acumulado[i-1]+histograma[i];
}

Estadística

El histograma facilita los cálculos estadísticos sobre los valores de la imagen.

La media aritmética:

var media = total/histograma.lentgh;

La varianza:

var varianza = 0;
for(var i = 1; i < histograma.lentgh; i++)}
  varianza += Math.pow(histograma[i], 2);
}
varianza /= histograma.lentgh;
varianza -= Math.pow(media, 2);

La desviación tipica:

var desviacion = Math.sqrt(varianza)

La moda:

var moda = 0;
for(var i = 0; i < histograma.lentgh; i++)}
    if(histograma[i] &gt; histograma[moda]){
        moda = i;
    }
}

La mediana:

var suma = 0;
for(var i = 0; i < histogram.lentgh; i++)}
    suma = histograma[i];
    if(suma &gt; total/2){
        return i;
    }
}

Probabilidad

Para la probabilidad usaremos el histograma normalizado. Que representa como de probable es que un pixel cogido al azar tenga el valor indicado por el indice (0-255). Es decir normalizado[3] es la probabilidad que de que un pixel elegido al azar tenga valor 3

Probabilidad de que el pixel elegido al azar tenga un valor x:

var probabilidad = normalizado[x];

Probabilidad de que el pixel elegido al azar tenga un valor x, y o z:

var probabilidad = normalizado[x] + normalizado[y] + normalizado[z];

Probabilidad de que un pixel elegido al azar tenga un valor que sea distinto de x, y o z:

var probabilidad = 1 - (normalizado[x] + normalizado[y] + normalizado[z]);

Para calcular la probabilidad acumulada podemos calcular el histograma acumulado del histograma normalizado:

var acumuladoNormalizado = [];
acumuladoNormalizado[0] = normalizado[0];
for(var i = 1; i < normalizado.lentgh; i++)}
  acumuladoNormalizado[i] = acumuladoNormalizado[i-1]+normalizado[i];
}

Ahora pasa saber la probabilidad de que un pixel tomado al azar sea menor o igual que un valor x:

var probabilidad = acumuladoNormalizado[x];

Si queremos calcular que sea mayor que el valor x:

var probabilidad = 1 - acumuladoNormalizado[x];

Todos estos casos en lugar de como probabilidad se pueden interpretar como “porcentaje de pixeles de la imagen”. Por ejemplo: “Porcentaje de pixeles de la imagen que son mayores que 100” Seria:

var probabilidad = 1 - acumuladoNormalizado[100];

Unir histogramas

Una de las ventajas del histograma es que su cálculo es fácilmente paralelizable. Se puede dividir la imagen en varias partes y calcular el histograma de cada una de ellas en paralelo. Luego esos histogramas se pueden unir en uno solo de forma fácil. Simplemente basta con sumar cada uno de los indices del histograma:

var union = [];
 for(var i = 0; i < histograma1.lentgh; i++)}
   union[i] = histograma1[i]+histograma2[i]
 }

En el caso del histograma normalizado hay que sumar y dividir entre 2 para conservar al propiedad de que sume 1 en total.

var union = [];
 for(var i = 0; i < normalizado1.lentgh; i++)}
   union[i] = (normalizado1[i]+normalizado2[i])/2
 }

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.

Imagen integral

La imagen integral es una técnica para acelerar el calculo de operaciones que incluyan la suma del valor de los pixeles de un área. Para calcular la imagen integral hay que reemplazar cada píxel por la suma de todos pixeles contenidos en un rectángulo cuya esquina superior izquierda es el vértice 0,0 de la imagen . Y cuya esquina inferior derecha es el propio pixel.

Veamoslo con un ejemplo, partimos de una imagen de 4×4 con lo siguientes pixeles:

1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

La forma más intuitiva de verlos es como un proceso en dos iteraciones. en la primera se suman todas las celdas de cada fila de izquierda a derecha:

1 1+1=2 2+1=3 3+1=4
2 2+2=4 4+2=6 6+2=8
3 3+3=6 6+3=9 9+3=12
4 4+4=8 8+4=12 12+4=16
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16

Luego sumamos las columnas de arriba hacia abajo:

1 2 3 4
2+1=3 4+2=6 6+3=9 8+4=12
3+3=6 6+6=12 9+9=18 12+12=24
4+6=10 8+12=20 12+18=30 16++24=40

El resultado:

1 2 3 4
3 6 9 12
6 12 18 24
10 20 30 40

Vale, tenemos una imagen con la suma de los valores de los pixeles. ¿Para qué nos sirve?. Para obtener con solo cuatro operaciones el total de la suma de de todos los pixeles de cualquier rectángulo de la imagen. Su uso es muy sencillo. Tomamos las cuatro esquinas A-B-C-D. El valor del pixel D en la imagen integral es el valor del área desde la esquina superior izquierda hasta el punto D. Le restamos el valor del área C (valor del punto C en la imagen integral) y el valor del área B (valor del punto B en la imagen integral). El problema es que ahora hemos restado una parte dos veces, por fortuna esa parte corresponde con el valor del área de A (seguro que ya sabes lo que va en estos paréntesis) solo hay que sumarlo. En resumen:

Valor del área ABCD = D – C – B + A

 

ABCD BD BD 4
CD D D 12
CD D D 24
10 20 30 40

¿Para qué sirve esto?. Se usa generalmente cuando tenemos algoritmos de ventana deslizante que necesitan calcular el valor de la suma del área comprendida por la ventana. Por ejemplo que necesiten el valor medio de un área o algún otro valor estadístico. No es necesario que lo que se sume sea el valor del pixel puede ser su cuadrado o simplemente 0 y 1 si es blanco o negro.

Es una herramienta útil para reducir los cálculos de distintos algoritmos, sobre todo de los que usan ventana deslizante.

Ventana deslizante y pirámide de imágenes

Se llama venta deslizante a seleccionar un rectángulo dentro de la imagen (la ventana) aplicar sobre él un conjunto de operaciones y luego desplazar (deslizar) la ventana un pixel y repetir el proceso, cuando llega al final de la linea se vuelve al principio y se baja una fila de pixels. Con un ejemplo se ve fácilmente, siendo los cuadros rojos la ventana seleccionada.

* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *

Se usa principalmente para la búsqueda de características. O para aplicar algoritmos que solo tiene en cuenta la vecindad. La convolución seria un ejemplo.

Es habitual su uso con una pirámide de imágenes que no es más que usar la misma imagen pero escalandola en cada paso para reducir su tamaño. Se usa cuando el algoritmo que se aplica en la ventana deslizante es dependiente de la escala, por ejemplo un histograma no lo es, pero un detector de caras si que lo es (no se lo mismo que la ventana abarque toda la cara que que abarque solo media cara). Cada iteración de la pirámide la imagen se reduce en un porcentaje pequeño y sobre la imagen resultante se aplica la ventana deslizante.

Una explicación más visual, con una reducción del 50% (generalmente es más pequeña)

8×8

* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *

4×4

* * * *
* * * *
* * * *
* * * *

2×2

* *
* *

Estos algoritmos suelen ser buenos candidatos a ser optimizados usando una o varias imágenes integrales.

Capturar vídeo de la cámara del dispositivo en HTML5

Para dotar a nuestro agente de ojos debemos poder acceder a las cámaras del dispositivo. Para ellos nuestra web va a necesitar un elemento vídeo y otro canvas. Enlazamos el vídeo con la webcam del dispositivo y cada cierto tiempo tomamos una captura que copiaremos sobre el canvas para poder acceder a los pixels y aplicar nuestros algoritmos de visión por computador.
Empecemos por incluir una etiqueta vídeo y una canvas en nuestra web:



Las funciones que nos da HTML5 para acceder al vídeo se basan en la API navigator.mediaDevices. En versiones antiguas de los navegadores pierdes encontrarte el problema de que los nombres no están unificados y cada uno lo llamaba de una manera. Actualmente ya lo están. Algo parecido nos pasa con la API window.URL que vamos a usar para poder conectar la webcam a nuestro elemento vídeo. Para que no haya problemas entre navegadores usaremos:

window.URL = window.URL
|| window.webkitURL
|| window.mozURL
|| window.msURL;

Nos hace falta acceder a cada uno de los elementos. El vídeo, el canvas y el contexto del canvas del cual leeremos la imagen capturada del vídeo. Para ello usaremos el id del tag.

video = document.getElementById(videoId);
canvas = document.getElementById(canvasId);
context = canvas.getContext('2d');

Para enlazar la webcam con el elemento vídeo antes hay que saber que webcam es ya que un dispositivo puede tener varias, por ejemplo un móvil tiene frontal y trasera. Para saber que dispositivos hay puedes usar la API navigator.mediaDevices.enumerateDevices . Una vez seleccionado el dispositivo que quieras usar se emplea el metodo getUserMedia() pasandole una estructura del tipo MediaStreamConstraints donde describes los requisitos que necesitas que tenga el dispositivo.  En nuestro caso va ser mas simple vamos a contemplar solo la cámara frontal, la trasera y la por defecto.

//Cámara frontal
device.video = {facingMode: "user", deviceId: ""};
//Cámara trasera
device.video = {facingMode: "environment", deviceId: ""};
//Cámara por defecto (frontal en los móviles)
device.video = {deviceId: "default"};

También podemos desear ajustar la resolución:

device.video.width = 320;
device.video.height = 240;

y el framerate.

this.configuration.framerate = 25;

Hay que decir que realmente estas condiciones no obligan que devolver un dispositivo que las cumpla, solo aconsejan que lo sea, así que no puedes confiar que la resolución sea la deseada y debes de verificarlos.

navigator.mediaDevices.getUserMedia(device)
.then(
  function(stream) { ...}
).catch(...)

Una vez conectada a la webcam hemos de conectar esta con el elemento vídeo de la web para ello usamos window.URL.createObjectURL :

navigator.mediaDevices.getUserMedia(device)
.then(
  function(stream) {
    var src = window.URL.createObjectURL(stream);
    video.src = src;
  }
).catch(
  function(e) { console.log("Video error: "+e); }
);

Y por ultimo cada cierto tiempo hemos de capturar el frame que se esta mostrando en el video y volcarlo al canvas, desde donde podremos acceder a todos sus pixeles. El proceso es muy sencillo, tan sencillo como copiarla al canvas usando el método drawimage

canvas.width = video.videoWidth;
canvas.height = video.videoHeight;
canvas.context.drawImage(video, 0, 0, this.video.videoWidth, this.video.videoHeight);

Lo mismo con videoToCanvas

Para hacer todo esto más sencillo se ha creado la librería videoToCanvas

//id del tag canvas y video
var v2c = new VideoToCanvas("canvas", "video");
//por defecto es 320x240
v2c.configuration.width=640;
v2c.configuration.height=480;
v2c.webcam();

Para realizar la captura al canvas es tan simple como:

v2c.snap();

Ademas cuenta con gran cantidad de funciones para controlar la reproducción del vídeo de la cámara o para cargar en su lugar un vídeo (útil para pruebas).

Acceder a los pixels de un canvas

Con esto tenemos ya el primer paso dado. Capturar la imagen. Antes de empezar a manipular los datos de un canvas tenemos que ver cómo trabajar con ellos.
Para recuperar los datos del canvas usamos la función getImageData del contexto

var imageData = canvas.context.getImageData(0, 0, width, height);
var data = imageData.data;

getImageData nos permite recuperar solo parte de la imagen indicando las coordenadas X e Y de la esquina superior izquierda del rectángulo de la imagen a recuperar y el ancho y el alto. En caso de que con las medidas especificadas recuperemos parte de de fuera de la imagen se devolverán pixels negros transparentes

Usando videoToCanvas tienes dos métodos getImageData(x, y, width, height) y getBoxes(rows, cols). el primero actúa igual que el getimageData del canvas.context y devuelve un ImageData. El segundo divide la imagen en rows*cols partes y devuelve un array de ImageData. Este método es útil cuando se va a trabajar en paralelo sobre distintas partes de la imagen.

En el ImageData devuelto encontramos las siguientes propiedades:

  • ImageData.height Alto de la imagen
  • ImageData.width Ancho de la imagen
  • ImageData.data Un array de bytes que contiene los pixels de la imagen en formato RGBA

Los píxels de la imagen se recuperan en formato RGBA. Que significa que cada píxel ocupa 4 bytes. Los 3 primeros se dedican a los componentes de color: rojo, verde y azul. El cuarto al nivel de transparencia, también llamado alpha. De esa forma data[0] corresponde al valor de la componente roja del primer píxel, data[1] a la verde, data[2] a la azul y data[3] a la alpha. Después repetimos esa misma distribución con data[4], data[5], data[6] y data[7]. Y así una y otra vez durante toda el array.

Los valores de cada pixel varían entre 0 y 255 e indican la intensidad de ese color en el pixel. Una ventaja del tipo de datos Uint8ClampedArray es que no hace falta comprobar los límites al asignarle un valor, todo valor menor que 0 se convierte a 0 y todo valor mayor de 255 se convierte a 255. Su mayor problema es que es un tipo bastante lento para operar con él así que vamos a tratar de reducir el número de operaciones sobre el mismo.

Convertir de escala de grises a RGB/RGBA

Nos va a pasar que en muchos casos tras aplicar varios algoritmos a una imagen terminamos con una versión en escala de grises con un canal de 8 bits por pixel. Pero para visualizarla hemos de convertirla en RGB o en RGBA. ¿Como hacemos para que se siga viendo el mismo nivel de gris? Afortunadamente la respuesta es muy sencilla, damos a los tres canales RGB el valor del único canal de escala de grises.

//Red
r = gs;
//Green
g = gs;
//Blue
b = gs;
//Alpha
a = 0;

Vista Introducción

La vista es uno de los sentidos más difíciles de imitar. La capacidad del ser humano para reconocer objetos es por ahora inimitable. La cantidad de objetos distintos que reconocemos de forma casi instantánea abrumaría a cualquier máquina que tratara de imitarnos. Pero no sólo eso, nuestra capacidad de clasificar objetos nunca vistos o incluso de deducir su función a partir de su forma es un sueño húmedo para cualquier desarrollador de visión por computador. Nuestra capacidad de abstracción es eficaz hasta tal punto que con solo ver un garabato medianamente bien hecho no tenemos problemas en saber de que objeto se trata (lo de medianamente bien hecho es importante como cualquier jugador de Pictionary sabrá)

Por si eso fuera poco humillante para cualquier máquina también les ganamos con sus propios ojos. En cualquier foto o vídeo tomada por una cámara nuestras capacidades se ven menos afectadas por la presencia de ruido o la mala calidad de imagen que cualquier sistema de visión por computador. Cierto que en este campo el procesado de imágenes para mejorar su calidad está logrando grandes avances pero generalmente estas técnicas son demasiado costosas en tiempo para aplicarlas en tiempo real y rara vez dan buenos resultados para todo tipo de imagen. Aun con todas estas limitaciones, y alguna más que veremos, Vamos a intentar que Chispas pueda usar la visión por computador de forma medianamente útil.

Nos vamos a centrar en que sea capaz de detectar diferentes características de la imagen:

  • Movimiento: detectaremos cambios en la imagen que, en caso de que la cámara está estática, indicará que algo se ha movido.
  • Detección de objetos: nos centraremos en detectar caras y manos para permitir al usuario interactuar con gestos con nuestro agente
  • Detección de colores: La usaremos para reconocer marcas o ayudarnos a seguir indicadores en ciertos casos
  • Reconocimiento de caracteres: Útil para leer textos de carteles y fotos
  • Reconocimiento de códigos QR
  • Nivel de luz ambiente

Hay que tener en cuenta las limitaciones del entorno donde se va a ejecutar nuestro agente. La velocidad va a primar sobre la exactitud (hasta un punto razonable, a ver si va a ser muy rápido y no va a dar una).

Otro punto que vamos a intentar alcanzar es la autosuficiencia. Muchos algoritmos necesitan que se introduzcan valores para funcionar correctamente. Muchos de esos valores se ajustan con el engorroso método de prueba y error. Generalmente estos valores dependen mucho del tipo de imagen y su contexto. Por ello vamos a preferir aquellos que tengan métodos para ajustar los valores automáticamente.

No hemos empezado y ya nos hemos rodeado de un montón de complicaciones, así será más divertido….espero.