Matrici e immagini digitali

Dirce Uesu Pesco e Humberto José Bortolossi.
Le immagini che si vedono sulle pagine internet e le foto che si fanno con il cellulare sono esempi di immagini digitali. É possibile rappresentare questo tipo di immagine usando le matrici. Per esempio, la piccola immagine di Felix il Gatto (sulla sinistra) può essere rappresentata da una matrice 35 \times 35 i cui elementi sono i numeri 0 e 1. Questi numeri specificano il colore di ciascun pixel (un pixel è il più piccolo elemento grafico di un immagine matriciale, che può assumere solo un colore per volta): il numero 0 indica il nero e il numero 1 indica il bianco. Le immagini digitali che usano solo due colori sono chiamate immagini binarie o booleane.

Figura 1: La matrice corrispondente a Felix il Gatto

Anche le immagini in scala di grigi possono essere rappresentate da matrici. Ogni elemento della matrice determina l’intensità del pixel corrispondente. Per convenienza, la maggior parte degli attuali file digitali usano numeri interi compresi tra 0 (per indicare il nero, il colore con intensità minima) e 255 (per indicare il bianco, il colore con la massima intensità), per un totale di 256 = 2^8 diverse gradazioni di grigio (Un tale numero di gradazioni è ragionevole per lavorare con le immagini delle pagine WEB. Tuttavia, esistono alcune applicazioni specifiche che hanno bisogno di più gradazioni di grigio per riprodurre l’immagine più dettagliata ed evitare gli errori di arrotondamento nei calcoli numerici, come nel caso delle immagini ad uso medico).

Le immagini a colori, a loro volta, possono essere rappresentate da tre matrici. Ogni matrici specifica la quantità di rosso, verde e blu che compone l’immagine. Questo sistema di colori è noto come RGB (Esistono molti altri sistemi di colori che vengono usati a seconda dell’applicazione in questione: CMYK (per stampare), Y’IQ (per la trasmissione analogica TV in NTSC), ecc). Gli elementi di queste matrici sono numeri interi compresi tra 0 e 255 e determinano l’intensità del pixel relativamente al colore della matrice. Quindi, nel sistema RGB, è possibile rappresentare 256^3 = 2^{24} = 16777216 colori diversi.

Figura 2: Immagine originale, componenti rosse, verdi e blu

Trattamento di un’immagine digitale e operazioni con le matrici

Una volta che un’immagine digitale può essere rappresentata con delle matrici, possiamo chiederci come le operazioni sui loro elementi influenzino l’immagine corrispondente. Per esempio, se consideriamo l’immagine binaria A in Figura 3 come una matrice, sia A = (a_{i,j}) allora l’immagine corrisponde l’immagine B corrisponde alla matrice trasposta di A, ossia B = (b_{i, j}) = (a_{j, i}) = A^{T}. L’immagine H, a sua volta, corrisponde alla matrice (a_{j, 35 - i + 1}). Prova a scoprire le relazioni matriciali tra l’immagine A e le altre immagini!

Figura 3: Le trasformazioni della matrice

Un altro esempio: se consideriamo la media aritmetica standard delle matrici R, G e B che compongono un’immagine a colori A, otterremo una versione in scala di grigi dell’immagine (i valori non-interi vengono arrotondati all’intero più vicino):

Figura 4: Media aritmetica delle matrici componenti

Un ulteriore esempio: usando le operazioni di moltiplicazione per uno scalare e della somma di matrici, è possibile creare un’effetto di transizione comunemente usato, per esempio, nelle presentazioni PowerPoint{}^{\copyright} e di slide. Più precisamente, consideriamo due immagini in scala di grigi della stessa grandezza, rappresentate dalla matrici A e Z. Per ogni scalare (numero reale) t nell’intervallo [0, 1], si definisca la matrice

    \[M(t) = (1 - t) A + t Z.\]

Si osservi che M(0) = A, M(1) = Z e per ogni t compreso tra 0 e 1, gli elementi della matrice M(t) sono compresi tra gli elementi delle matrici A e Z. Perciò, quando t varia da 0 a 1, la matriceare M(t) varia da A a Z. Nel caso di un’immagine a colori, la trasformazione (1) deve essere applicata alle matrici R, G e B che determinano ogni immagine.

Figura 5: M(0) = A, M(0.13), M(0.25), M(0.38), M(0.50), M(0.63), M(0.75), M(0.88), M(1)=Z

Anche la moltiplicazione di matrici ha applicazioni nel trattamento di un’immagine digitale. Sebbene il nostro prossimo esempio sarà più elaborato, (con un ragionamento basato su tecniche matematiche più avanzate solitamente studiate solo ai corsi universitari di Algebra Lineare), crediamo che possa essere comunque interessante per il lettore, poiché quest’ultimo avrà l’opportunità di apprezzare una sorprendente applicazione dovuta al fatto che siamo in grado di scomporre una matrice come prodotto di matrici aventi strutture speciali. I dettagli omessi potranno essere trovati nei riferimenti bibliografici [Lay, 2011] e [Poole, 2005]. Si consideri, dunque, una scomposizione a valori singolari (SVD), che consiste in scrivere una matrice come il prodotto di tre
matrici:

    \[A_{m \times n}^{\vphantom{T}} = U_{m \times m}^{\vphantom{T}} S_{m \times n}^{\vphantom{T}} V_{n \times n}^{T},\]

Qui di seguito è riportato un esempio della decomposizione SVD:

    \[A = \left[\begin{array}{rrr}    -1 & 1 & 0 \\     0 & -1 & 1 \end{array}\right] = U S V^{T}\]

    \[= \left[ \begin{array}{rr} \displaystyle -\frac{\sqrt{2}}{2} & \displaystyle \frac{\sqrt{2}}{2} \vspace*{0.5ex} \\ \displaystyle \frac{\sqrt{2}}{2} & \displaystyle \frac{\sqrt{2}}{2} \end{array} \right] \left[ \begin{array}{rrr} \sqrt{3} & 0 & 0 \\  0 & 1 & 0 \end{array} \right] \left[ \begin{array}{rrr} \displaystyle \frac{\sqrt{6}}{6} & \displaystyle -\frac{\sqrt{2}}{2} & \displaystyle \frac{\sqrt{3}}{3} \vspace*{0.5ex} \\ \displaystyle -\frac{\sqrt{6}}{3} & 0 & \displaystyle \frac{\sqrt{3}}{3} \vspace*{0.5ex} \\ \displaystyle \frac{\sqrt{6}}{6} & \displaystyle \frac{\sqrt{2}}{2} & \displaystyle \frac{\sqrt{3}}{3} \end{array} \right]^{T}. $ } }\]

Può essere dimostrato che ogni matrice ammette una decomposizione SVD ([Lay, 2011],[Poole, 2005]). In più, esistono algoritmi che ci permettono di calcolare questo tipo di decomposizioni usando un computer. Il punto chiave del nostro esempio è osservare che se \textbf{u}_{1}, \textbf{u}_{2}, \ldots, \textbf{u}_{m} sono le colonne della matrice U e \textbf{v}_{1}, \textbf{v}_{2}, \ldots, \textbf{v}_{n} sono le colonne della matrice V, allora

    \[A = USV^{T} =  s_{1, 1} \textbf{u}_{1} \textbf{v}_{1}^{T} + s_{2, 2} \textbf{u}_{2} \textbf{v}_{2}^{T} + \cdots + s_{k, k} \textbf{u}_{k} \textbf{v}_{k}^{T}.\]

Perché questo? Supponiamo che A, un’ immagine in scala di grigio di dimensioni 1000 \times 1000, debba essere trasmessa da un satellite a un laboratorio sulla Terra. In linea di principio, il satellite dovrebbe mandare 1 milione di numeri (uno per ciascun pixel). Tipicamente, poiché, sono significativi solo i primi s_{i, i} elementi della matrice S della decomposizione SVD per A (gli altri sono “piccoli”), è, quindi, sufficiente che il satellite mandi, diciamo, le prime 20 colonne di U e di V e i primi 20 numeri s_{i, i} (per un totale di soli 20 \cdot 1000 + 20 \cdot 1000 + 20 = 40020 numeri che devono essere inviati). Alla ricezione di questi dati, il laboratorio sulla Terra calcola la matrice s_{1, 1} \textbf{u}_{1} \textbf{v}_{1}^{T} + s_{2, 2} \textbf{u}_{2} \textbf{v}_{2}^{T} + \cdots + s_{20, 20} \textbf{u}_{20} \textbf{v}_{20}^{T} che darà un’approssimazione dell’immagine originaria.

Vediamo un esempio: la Figura 6 del matematico Christian Felix Klein (1849-1925) ha 720 \times 524 = 377 280 pixel.

Figura 6: Felix Klein

Dalla decomposizione SVD della matrice corrispondente di questa immagine, possiamo calcolare le matrici s_{1, 1} \textbf{u}_{1} \textbf{v}_{1}^{T} + s_{2, 2} \textbf{u}_{2} \textbf{v}_{2}^{T} + \cdots + s_{r, r} \textbf{u}_{r} \textbf{v}_{r}^{T} per r = 1, 5, 10 e 20. Queste matrici generano approssimazioni dell’immagine originaria, come illustrato nella Figura 7. Notiamo che l’immagine originaria corrisponde al caso r = 524. È piuttosto notevole, non credete?

Figura 7: casi r = 1, 5, 10 e 20

Altre applicazioni

L’elaborazione delle immagini digitali ha molte applicazioni, come il telerilevamento, la trasmissione di dati, la medicina, la robotica, la computer vision, l’industria dei film, ecc. Nel telerilevamento, per esempio, le immagini acquisite dai satelliti sono utili per il monitoraggio di risorse naturali, per la mappatura geografica, per l’analisi della crescita urbana e per molte altre applicazioni ambientali. Nella trasmissione delle immagini, abbiamo comunicazioni via fax, reti, internet e TV a circuito chiuso per il monitoraggio e la sicurezza. Nelle applicazioni mediche, abbiamo elaborazione delle immagini ai raggi X, immagini di proiezione di tomografie transassiali, la radiologia, la risonanza magnetica nucleare (RNM) e la scansione a ultrasuoni. Alcuni metodi di acquisizione e di trasmissione possono generare imperfezioni in un’immagine. Il filtro mediano è una tecnica dell’elaborazione dell’ immagine usata per rimuoverle o per ridurre i loro effetti: per ogni elemento della matrice che rappresenta l’immagine, osserviamo i suoi elementi periferici e, poi, li disponiamo in un vettore ordinato. Il filtro mediano consiste nello scegliere l’elemento centrale di questo vettore e nel sostituire con esso l’elemento centrale della matrice (Figura 8).

Figura 8: Il filtro mediano

Figura 9: immagine disturbata e immagine col filtro mediano

Nell’elaborazione di immagini, esistono molte altre tecniche con obiettivi diversi. Le immagini in Figura 10 illustrano esempi di aggiustamento di contrasto, di rilevamento e di soglia del bordo.

Figura 10: immagine originaria e la stessa immagine con l’aggiustamento di contrasto, con il rilevamento del bordo e con il valore di soglia

Commento finale

Il nostro obiettivo, con questo articolo, è di presentare agli insegnanti e agli studenti della scuola media superiore un’ applicazione delle matrici poco conosciuta: l’elaborazione delle immagini digitali. È importante notare che gli strumenti matematici collegati a questo argomento vanno ben al di là delle matrici. Il soggetto è vasto, ricco e moderno. Sfortunatamente, il limite di poche pagine a disposizione per questo articolo non ci permette di fornire ulteriori dettagli. Come punto di partenza per il lettore motivato a saperne di più, raccomandiamo i libri [Gonzalez e Woods, 2007] e [Gomes e Velho, 2008].

Su questo sito web (or at its mirror)), è presente una serie di applet interattive che permettono di esplorare le relazioni tra le matrici e le immagini digitali presentate in questo testo. Potrete trovare, inoltre, un file DOC con suggerimenti di esercizi da proporre in classe.

Qui sotto sono presenti i riferimenti citati nel testo.

Riferimenti bibliografici

Gomes, J.; Velho, L. Image Processing for Computer Graphics and Vision. Springer-Verlag, 2008.

Gonzalez, R. C.; Woods, R. E. Digital Image Processing. Third Edition. Prentice Hall, 2007.

Lay, D. Linear Algebra and Its Applications. Forth Edition. Addison Wesley, 2011.

Poole, D. Linear Algebra: A Modern Introduction. Second Edition. Brooks Cole, 2005.

The photo of the Mona Liza in LEGO is a property of Marco Pece Udronotto, who kindly granted permission to use it in this work.

Questo post è disponibile in: Inglese, Francese, Tedesco, Arabo, Khmer

This entry was posted in Vignettes. Bookmark the permalink.

  1. Sonia Cafieri says:

    Voici une traduction.
    L’exemple est sympa en effet pour des étudiants.

    ——-
    “Matrices et images numériques”

    Les images qu’on voit sur les pages web et les photos qu’on prend avec le téléphone portable sont des exemples d’images numériques.
    Il est possible de représenter ce type d’image en utilisant des matrices. Par exemple, la petite image de Felix le Cat (à gauche) peut être représentée par une matrice 35 \times 35 dont les éléments sont les nombres 0 et 1.
    Ces nombres indiquent la couleur de chaque pixel (un pixel est le plus petit élément graphique d’une image matricielle, ce qui peut prendre une seule couleur à la fois): le nombre 0 indique le noir et le 1 indique le blanche. Les images numériques qui utilisent seulement deux couleurs sont appelées “images binaires” ou “booléennes”.
    ——

Leave a Reply

Your email address will not be published. Required fields are marked *