Manipulación de imágenes con Javascript. Parte 2

08 Nov 2016

Introducción

En el artículo anterior, aprendimos los conceptos básicos para manipular imágenes de forma prográmatica con Javascript. Repasamos cómo cargar un fichero en memoria a través del elemento ‘canvas‘, cómo leer sus datos a nivel de píxel, y cómo modificar esta información utilizando algoritmos. Elaboramos un ejemplo de aplicación sencilla con la que podíamos aplicar varios filtros además de guardar nuestros resultados.

En esta segunda parte vamos a investigar cómo mejorar el rendimiento cuando trabajamos con imágenes grandes o con filtros más complejos.

Mejorando el rendimiento

Hasta ahora, todo el proceso de cálculo que requerimos para cada filtro lo hemos realizado mediante fuerza bruta, píxel a píxel. Eso implica un coste alto en cuanto a cómputo por parte del intérprete que, como sabemos, independientemente de la máquina donde se ejecute, trabaja en monohilo.

Javascript es un entorno de subproceso único, es decir, que no se pueden ejecutar varias secuencias de comandos al mismo tiempo.


HTML5Rocks, Introducción a los Web Workers

Esta limitación supone de entrada un aspecto delicado cuando trabajamos con imágenes: la relación entre su tamaño, la memoria necesaria y el tiempo de cómputo que supone una modificación de cada uno de sus píxeles.

Relación tamaño / memeoria de una imagen

Como vimos en el artículo anterior, la memoria necesaria para trabajar con una imagen es directamente proporcional a sus dimensiones. El cálculo se realiza mediante la siguiente fórmula:

LENGTH = width * height * 4

Hay que recordar que a cada píxel de la imagen (el resultado de multiplicar su anchura por altura), le corresponden cuatro elementos según sus valores RGBA. De ahí que la longitud final de su matriz sea la descrita la fórmula anterior.

rgba-pixel-model

Esquema RGBA para cada píxel tomado de aquí

Baste como ejemplo tomar las medidas de una imagen en Full HD para hacernos una idea de la longitud de su matriz de valores:

SIZE = 1920 * 1080 * 4 = 8.294.400

El array que contiene la información de una imagen en alta definición posee una longitud de más 8 millones de elementos. Si queremos además manipularla, tenemos que asumir el coste de aplicar una fórmula (un algoritmo) sobre cada uno de esos elementos mientras recorremos la matriz.

Por lo general, ese coste es inasumible ya que, mientras los cálculos se están procesando, el flujo de nuestro programa se interrumpe a la espera de concluir las operaciones necesarias. Es en este escenario cuando el navegador muestra un mensaje de error del siguiente tipo:

unresponsive-script

La aplicación tarda tanto en finalizar sus cálculos que el navegador nos advierte de un posible problema

La estrategia a seguir en estos casos es la del célebre ‘Divide et impera‘ (divide y vencerás) o, de forma más ajustada, ‘Divide y acabarás antes’…

En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución del problema principal se construye con las soluciones encontradas.

Wikipedia, Algoritmo divide y vencerás

Este paradigma, cuando trabajamos en un entorno SIMD (single instruction multiple data), se aplica a través del concepto de la paralelización. Y éste, a su vez, se implementa en Javascript mediante los Web Workers.

Web Workers

Gracias a la API Web Workers, vamos a conseguir exactamente la idea anterior: paralelismo; dividir nuestro trabajo en partes más pequeñas para conseguir un mejor tiempo final de cálculo.

El paralelismo es una forma de computación en la cual varios cálculos pueden realizarse simultáneamente, basado en el principio de dividir los problemas grandes para obtener varios problemas pequeños, que son posteriormente solucionados en paralelo.

Wikipedia Paralelismo (informática)

Implementar el poder de los Web Workers en nuestra aplicación implica extraer parte del código anterior a un fichero externo e independiente. Vamos con ello.

Los filtros

La carga importante de cálculo que tiene que soportar nuestra aplicación es la que realizan los filtros y son por tanto estos fragmentos los que tenemos que extraer.

Tomemos por ejemplo un par de ellos: el filtro para pasar una imagen a escala de grises y el de inversión de color. Sacamos ambos de nuestra aplicación y creamos con ellos un nuevo archivo al que llamaremos ‘filters.js‘:

// filters.js
var filterBW = ( pixels, numPixels ) => {
    for ( let i = 0; i < numPixels; i++ ) {
        let grey = (
            pixels[ i * 4 ] +       // r
            pixels[ i * 4 + 1 ] +   // g
            pixels[ i * 4 + 2 ]     // b
        ) / 3;
 
        pixels[ i * 4 ] = grey;
        pixels[ i * 4 + 1 ] = grey;
        pixels[ i * 4 + 2 ] = grey;
    }
};
 
var filterInvert = ( pixels, numPixels ) => {
    for ( let i = 0; i < numPixels; i++ ) {
        pixels[ i * 4 ] = 255 - pixels[ i * 4 ];
        pixels[ i * 4 + 1 ] = 255 - pixels[ i * 4 + 1 ];
        pixels[ i * 4 + 2 ] = 255 - pixels[ i * 4 + 2 ];
    }
};

NOTA: Para este artículo, sí utilizaremos la notación moderna ES5. No obstante, recordamos que usamos ‘var’ en lugar de ‘const‘ únicamente con fines prácticos para este artículo. El usuario, es libre de cambiar esta declaración de variables por su forma ‘const’ más correcta.

Con esto extraemos nuestros filtros y lo preparamos para la paralelización. Para evitar duplicidad, nuestras funciones ahora reciben por parámetro el array de píxeles (pixels) y su longitud (numPixels). Más adelante veremos cómo hacemos llegar esos datos.

Modificando la aplicación para que funcione con Web Workers

Debemos ahora cambiar el fichero original para que se beneficie de este nueva estructura. La idea aquí es crear N número de procesos para que cada uno se encargue de trabajar una porción de la imagen (el ‘divide’).

Una vez concluye todo este trabajo en paralelo, se utiliza el método Window.postMessage a modo de callback para devolver el resultado al script principal, quien reconstruye nuestra imagen a partir de los nuevos fragmentos computados (el ‘vencerás’).

El código, general quedaría como sigue. Aprovechamos también este paso para sanearlo y actualizarlo con respecto al artículo anterior:

var app = ( () => {
 
    let canvas = document.getElementById( 'canvas' ),
        context = canvas.getContext( '2d' ),
        numPixels = canvas.width * canvas.height * 4,
 
        // API
        public = {};
 
    // Web Workers
    let workersCount = 4,
        segmentLength = numPixels / workersCount, // This is the length of array sent to the worker
        blockSize = canvas.height / workersCount; // Height of the picture chunck for every worker
 
    // Function called when a job is finished
    let onWorkEnded = e => {
        let imageData = e.data.result,
            index = e.data.index;
 
        // Copying back canvas data to canvas
        // If the first webworker (index 0) returns data, apply it at pixel (0, 0) onwards
        // If the second webworker (index 1) returns data, apply it at pixel (0, canvas.height/4) onwards, and so on
        context.putImageData( imageData, 0, blockSize * index );
    };
 
    // --------------------------------------------------------------------
 
    // Public methods goes here...
    public.loadPicture = () => {
        let imageObj = new Image();
        imageObj.src = 'entropy.jpg';
 
        imageObj.onload = () => context.drawImage( imageObj, 0, 0 );
    };
 
 
    public.launchWorker = () => {
        // Launching every worker
        for ( let index = 0, worker, imageData; index < workersCount; index++ ) {
            worker = new Worker( 'imgProcessor.js' );
            worker.onmessage = onWorkEnded;
 
            // Getting the picture
            imageData = context.getImageData( 0, blockSize * index, canvas.width, blockSize );
 
            // Sending canvas data to the worker using a copy memory operation
            worker.postMessage( { data: imageData, index: index, length: segmentLength } );
        }
    };
 
    return public;
} ) ();

NOTA: Este código está inspirado en un viejo artículo de David Catuhe que podemos ver aquí.

El código está comentado para que resulte autoexplicativo, pero diseccionamos las partes clave:

// Web Workers
let workersCount = 4,
    segmentLength = numPixels / workersCount,
    blockSize = canvas.height / workersCount;

Con estas líneas preparatorias, establecemos el número de procesos en el que vamos a dividir nuestro trabajo. Más adelante, profundizaremos en esto, pero de entrada, fijamos 4 procesos. Con ese dato, podemos ya conocer la longitud del array que enviaremos a cada uno de los hilos y su correspondiente porción de la imagen.

let onWorkEnded = e => {
    /* ... */
};

Esta función recoge los datos ya computados por cada hilo externo. Su cometido es reconstruir la imagen con cada porción que le es devuelta.

public.launchWorker = ( ) => {
    for ( let index = 0, worker, imageData; index < workersCount; index++ ) {
        worker = new Worker( 'imgProcessor.js' );
        worker.onmessage = onWorkEnded;
 
        imageData = context.getImageData( 0, blockSize * index, canvas.width, blockSize );
 
        worker.postMessage( { data: imageData, index: index, length: segmentLength } );
    }
};

Este es el corazón de la nueva aplicación. El bucle se encarga de lanzar tantos procesos como hayamos establecidos previamente, llamando al Worker ‘imgProcessor.js‘ que definiremos a continuación.

A cada nuevo hilo, se le asigna una porción de la imagen y se añaden un par de argumentos útiles como son el índice (index) y su longitud (segmentLength). Estos valores se envían al worker utilizando postMessage.

Fichero Procesador

Para procesar las imágenes con los filtros anteriores, necesitamos un nuevo fichero. Éste, muy sencillo, lo llamaremos (como hemos referenciado arriba) ‘imgProcessor.js‘:

// imgProcessor.js
importScripts( 'filters.js' );
 
self.onmessage = e => {
    let imageData = e.data.data,
    	pixels = imageData.data,
    	numPixels = e.data.length,
    	index = e.data.index;
 
    // Filters goes here...
    filterInvert( pixels, numPixels );
 
    self.postMessage( {
    	result: imageData,
    	index: index
    } );
};

Este pequeño script es el encargado de cargar los filtros y lanzar el que corresponda utilizando como argumentos los datos que ha recibido desde el general. Una vez finalizado el cómputo, devuelve un objeto utilizando de nuevo ‘postMessage‘. Por último, observamos que es desde este fichero desde donde se importa el archivo que contiene nuestros filtros (filters.js) a través del método importScripts.

Como no es el objeto de este artículo, hemos incluido el filtro que queremos ejecutar directamente a fuego en el fragmento anterior, aportándole los parámetros necesarios que establecimos como necesarios en ‘filters.js‘. En una aplicación real, la ejecución de uno u otro filtro se realizaría de forma programática, salvo en el caso de que siempre queramos correr el mismo (uno o varios) sobre una imagen dada.

Con todo ya en su sitio, para lanzar nuestro nuevo lote de procesos, utilizamos nuestra API actualizada desde la consola:

app.launchWorker();

El flujo de nuestra aplicación, de forma esquematizada, sería el siguiente:

  • Se crean 4 workers para procesar nuestra imagen en paralelo.
  • Los datos de la imagen se fraccionan en un número igual a los workers tenemos (4).
  • Cada worker recibe una porción de la imagen (debidamente parametrizada) para calcular sobre ésta el algoritmo correspondiente (nuestro filtro).
  • Una vez cada hilo concluye su cómputo, se envía un mensaje vía postMessage con los datos obtenidos al script general.
  • Con cada lote calculado, correspondiente a una porción de la imagen original, se va construyendo la nueva imagen modificada.

Esto supone que hemos repartido el trabajo que antes se realizaba en un solo hilo en cuatro paralelos, consiguiendo con esto una mejora significativa en el rendimiento además de un mejor aprovechamiento del hardware disponible.

Double buffering

Como no estamos utilizando ningún búfer de datos ad hoc, un ojo bien entrenado podría advertir cómo nuestra imagen no se reconstruye en bloque, sino a partir de trozos según éstos van llegando desde sus distintos procesos.

invert-partial

Instante en que el trozo 2 es recogido e inmediatamente volcado a la imagen. Los otros aún estarían en proceso.

Si quisieramos corregir esto y esperar a tener todas las porciones listas antes de redibujar nuestra imágen, tendríamos que recurrir a técnicas similares al double buffering, muy estudiada en Javascript gracias a su importante papel para el desarrollo de vídeo juegos HTML5 basados en canvas.

Límite en hilos

Hemos visto que 4 hilos suponen una mejora de rendimiento, pero ¿y si ponemos 40? ¿mejora el global o existe un límite?

Pues en teoría no hay límite. Según la especificación del W3C (Working Draft 24 September 2015) no estamos limitados a un número concreto de hilos simultáneos. Sin embargo conviene no abusar e ir experimentado ya que la práctica demuestra que un número desproporcionado de hilos pueden suponer una caída radical del rendimiento no ser capaz el sistema de manejar un alto número de concurrencias.

Lo recomendable es utilizar workers cuando el cómputo por cada hilo se prevé mayor a los 100ms de cálculo. Tiempos menores comienzan a penalizar en lugar de ofrecer una mejora.

De nuevo, lo recomendable es experimentar. Una solución inteligente puede ser lanzar un número de procesos proporcional al tamaño de la imagen, habiendo definidos estos de antemano. Por ejemplo:

Ancho Alto Workers
640 360 1
800 600 1
1024 768 2
1280 720 2
1920 1080 4 – 6

De este modo, podemos ir encontrando el mejor compromiso entre hilos y tiempos totales de post procesado.

Concepto de aplicación experimental

Los Web Workers permiten comunicarse con un servidor a través de XMLHttpRequest o la nueva API Fetch, lo cual nos permitiría en teoría un post procesado remoto de imágenes a través de una API pública dedicada.

NOTA: Para consultar todas las funciones y clases disponibles con los workers, podemos consultar esta tabla creada por Mozilla.

Desafortunadamente, no he encontrado ningún servicio que preste a día de hoy esa funcionalidad (noviembre, 2016), por lo que podría ser una herramienta interesante a desarrollar.

La idea con esto sería crear una API pública capaz de recibir una matriz de datos de imagen (nuestro array de píxeles) y que contase con un catálogo de filtros que podríamos aplicar sobre los mismos. La API retornaría el resultado (imagen o porción de imagen) una vez calculado dejando a nuestra aplicación la responsabilidad de reconstruir la imagen final.

Conclusión

En esta segunda parte sobre la manipulación de imágenes con Javascript, hemos abordado el problema del rendimiento con imágenes grandes o filtros complejos utilizando la paralelización.

Gracias a los Web Workers, podemos dividir un problema en partes más pequeñas para trabajarlas de forma independiente y paralela. Con esto, conseguimos una mejora general siempre y cuando se consiga un balance correcto entre sub procesos y cálculos.

Más:

{3} Comentarios.

  1. Miguel Jiménez

    Hasta donde sé, los ArrayBuffers pasan por valor (y no por referencia) a los web workers. Esto quiere decir que para cada WebWorker, estás creando 3x el tamaño del chunk que pasas (el original + el que pasa al worker + el que vuelve del worker); por lo que una imagen de 8 Mb requiere (en el pico) 24 Mb.

    postMessage acepta un segundo argumento para proporcionar aquellos objetos que deben pasar por referencia. Esto, que en teoría evitaría las copias múltiples, tampoco sirve, porque lo que hace es transferir el control del objeto; y hasta que el worker correspondiente no lo libera, no puedes volver a utilizarlo. Es decir, pederías el beneficio de la paralelización.

    Lo que yo haría es usar un SharedArrayBuffer, específicamente diseñados para esto; copiando entonces de un ArrayBuffer (ImageData.data) a un SharedArrayBuffer y posteriormente recreando el objeto ImageData. Esto tiene varios beneficios:

    * Todos los trozos pasan por referencia (no hay duplicados)
    * La memoria necesitada es únicamente de 8 Mb
    * Los workers trabajan mucho más rápido (no hay copias al llamar a postMessage)

    Referencias:
    https://developer.mozilla.org/en-US/docs/Web/API/Web_Workers_API/Using_web_workers#Passing_data_by_transferring_ownership_(transferable_objects)
    https://developer.mozilla.org/es/docs/Web/JavaScript/Reference/Global_Objects/SharedArrayBuffer

    • Carlos Benítez

      Hola Miguel;
      excelente comentario del que podemos aprender mucho!

      Solo matizar algo: si una imagen pesa 8MB, el pico requerido no sería de 24MB. Me explico (esto requiere de pruebas y alguna gráfica, por lo que es posible que me ponga con ellas en cuanto pueda): a cada worker, la información que se le envía es la que le corresponde tras trocear la imagen (siguiendo la estructura lógica del artículo). Si hemos iniciado 4 workers, a cada uno le llega un cuarto (1/4). La información se duplica, como bien comentas para afrontar la paralelización (valor en crudo, no referencia), pero tras cada cómputo, y su consecuente retorno, la memoria se libera (en ES6, el recolector de basura libera el sistema una vez concluido/cerrado el worker).

      Como cada worker trabaja de forma independiente, la memoria se asigna y libera bajo demanda, por lo que no se requiere para el total la suma de memoria que requiere cada parte. Digamos que esos 24MB necesarios serían necesarios en el caso de que todos los procesos se realizaran de forma perfectamente simultánea (todos reciben los datos, los computan y devuelven en los mismos ciclos de reloj)… una paralelización perfecta.

      Ese escenario teórico dudo que pueda darse en la práctica (de hecho, sería imposible en uno donde los workers trabajaran con servidor a través de Fetch o XMLHttpRequest). Es más razonable pensar que la memoria exigida fluctuará en alrededor del doble del tamaño de la imagen original en un supuesto pico para igualarse rápidamente con esta.

      Pero… sí, hay un pero. Actualmente, la implementación de los Workers en los navegadores no es aún perfecta; se han reportado problemas con la gestión de memoria en Firefox y Chrome, quedando por ahora Edge como el único que ha hecho sus deberes.

      De todos modos, es un caso muy interesante que habría que estudiar con código.

      Muchas gracias por tu aporte;
      saludos!

  2. Miguel Jiménez Esún

    El problema principal que veo a lo que expones es el que asume que el GC va a correr a cada instrucción o por cada worker; cuando más bien corre “cuando quiere”. Eso es lo que lleva a que en los picos exista 3x memoria ocupada, aunque efectivamente, en todo momento únicamente retienes dos referencias a dos ArrayBuffer idénticos, por lo que el tamaño total serían 16 y no 24 Mb para una imagen de 8 Mb (que sigue siendo más que en el caso del SharedArrayBuffer).

    Por otra parte, hay varios procesos que son costosos, y no sólamente en espacio, sino en tiempo (que al final, también la cosa va de reducir el tiempo). Estos son los que se me ocurren, de menos relevante a más relevante:

    * La copia de buffers: cuando blink transfiere buffers lo hace mediante memcpy (poco glamuroso, lo sé :D). La implementación (aunque depende del compilador) suele copiar de 8 en 8 bytes (no se suelen usan registros SSE o MMX). Esta copia se realiza 2 veces (una al ir, y otra al volver) en vez de una (con el SharedArrayBuffer).

    * La asignación y liberación de memoria (los malloc y los free). Se hacen 2 * workersCount llamadas, en vez de una (con el SharedArrayBuffer).

    * La presión adicional al GC: tiene que alocar referencias enter objetos que luego se destruyen (y los GCs no suelen brillar por su velocidad) :).

    Y ya, a modo de curiosidad, es posible bajar aún más el tiempo de procesamiento usando ciertos trucos. Por ejemplo, negativizar una imagen se puede hacer con un XOR y una máscara de 0xFFFFFF00, para extraer el máximo de performance 😀

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *