HPC - Mappatura livelli di grigio

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-12-05

Consideriamo una immagine bitmap a toni di grigio di \(M\) righe e \(N\) colonne, in cui il colore di ogni pixel sia codificata con un intero da 0 (nero) a 255 (bianco). Dati due valori interi low, high con \(0 \leq \mathit{low} < \mathit{high} \leq 255\), la funzione map_levels(img, low, high) modifica l'immagine img rendendo neri tutti i pixel il cui livello di grigio è minore di low, bianchi tutti quelli il cui livello di grigio è maggiore di high, e mappando i rimanenti nell'intervallo \([0, 255]\). Più in dettaglio, detto \(p\) il livello di grigio di un pixel, la funzione deve calcolare il nuovo livello \(p'\) come:

\[ p' = \begin{cases} 0 & \text{se}\ p < \mathit{low}\\ \alpha \times (p - \mathit{low}) & \text{se}\ \mathit{low} \leq p \leq \mathit{high}\\ 255 & \text{se}\ p > \mathit{high} \end{cases} \]

dove \(\alpha = 255 / (\mathit{high} - \mathit{low})\). La Figura 1 mostra un esempio.

Figura 1: Esempio di mappatura di livelli
Figura 1: Esempio di mappatura di livelli

Come esempio di applicazione reale, viene fornita l'immagine C1648109 ripresa dalla sonda Voyager 1 l'8 marzo 1979, che mostra Io, uno dei quattro satelliti Galileiani di Giove. L'ingegnera di volo Linda Morabito era interessata ad evidenziare le stelle sullo sfondo per ottenere la posizione precisa della sonda. A tale scopo ha rimappato i livello di grigio, facendo una delle scoperte più importanti della missione. Provate ad applicare il programma simd-map-levels.c all'immagine ponendo low = 10 e high = 30, e osservate cosa compare a ore dieci accanto al disco di Io...

Figura 2: Immagine C1648109 di Io ripresa da Voyager 1 (fonte)
Figura 2: Immagine C1648109 di Io ripresa da Voyager 1 (fonte)

Il file simd-map-levels.c contiene una implementazione seriale dell'operatore per rimappare i livelli di grigio. Scopo di questo esercizio è svilupparne una versione SIMD utilizzando i vector datatype del compilatore GCC. Poiché ogni pixel dell'immagine è codificato da un valore di tipo unsigned char, è possibile rappresentare i valori di 16 pixel in un vettore SIMD. Definiamo quindi un tipo v16uc per rappresentare un vettore SIMD composto da 16 elementi unsigned char:

typedef unsigned char v16uc __attribute__((vector_size(16)));
#define VLEN (sizeof(v16uc)/sizeof(unsigned char))

L'idea è di elaborare l'immagine a blocchi di 16 pixel adiacenti. L'unica difficoltà consiste nella struttura condizionale necessaria per determinare il nuovo colore di un pixel.

Il blocco di codice:

unsigned char *pixel = bmp + i*width + j;
if (*pixel < low)
    *pixel = BLACK;
else if (*pixel > high)
    *pixel = WHITE;
else
    *pixel = (*pixel - low) * alpha;

deve essere modificato utilizzando la tecnica di "selection and masking" vista a lezione, in modo da eliminare la condizione e poter usare solo operazioni SIMD.

Nota. Il codice seriale fornito non è corretto, perché l'uso del tipo unsigned char anziché int causa errori di overflow durante le operazioni aritmetiche necessarie per mappare il livello di grigio nell'intervallo \([\mathit{low}, \mathit{high}]\). Questo problema è facilmente risolvibile rappresentando i pixel con valori interi anziché unsigned char.

Definiamo pixels come puntatore ad un array SIMD contenente 16 pixel adiacenti. L'espressione mask_black = (*pixels < low) produce come risultato un nuovo array SIMD i cui elementi valgono -1 in corrispondenza dei pixel con valore minore alla soglia, e 0 per gli altri pixel. La struttura condizionale di cui sopra può essere quindi riscritta come:

v16uc *pixels = (v16uc*)(bmp + i*width + j);
const v16uc mask_black = (*pixels < low);
const v16uc mask_white = (*pixels > high);
const v16uc mask_map = ???; /* completare */
*pixels = ( (mask_black & BLACK) |
        (mask_white & WHITE) |
        (mask_map && ???) );

Si noti che BLACK e WHITE vengono automaticamente promossi dal compilatore ad array SIMD i cui elementi valgono BLACK e WHITE, rispettivamente.

L'espressione (mask_black & BLACK) ha come risultato un vettore SIMD i cui elementi sono tutti zero (perché?), quindi il frammento di codice precedente può essere ulteriormente semplificato.

Per funzionare correttamente la versione SIMD richiede che:

  1. La bitmap sia allocata a partire da un indirizzo di memoria multiplo di 16;

  2. La larghezza dell'immagine sia multipla dell'ampiezza di un registro SIMD (16, nel nostro caso)

Entrambe le condizioni sono soddisfatte nel programma e nelle immagini fornite.

Compilare con:

    gcc -std=c99 -Wall -Wpedantic -O2 -march=native simd-map-levels.c -o simd-map-levels

Eseguire con:

    ./simd-map-levels low high < input_file > output_file

dove \(0 \leq \mathit{low} < \mathit{high} \leq 255\).

Esempio:

    ./simd-map-levels 10 30 < C1648109.pgm > C1648109-map.pgm

File