Run-length, il primo algoritmo della storia per la compressione delle immagini

L’algoritmo Run-length è il primo algoritmo di compressione per le immagini. Si tratta di un metodo di tipo lossless (senza perdita di dati) che riduce la ripetizione di elementi uguali all’interno del file. Per ogni elementi trovato uguale, l’algoritmo sostituisce un RUN, ovvero un insieme di 3 caratteri: il primo indica il codice identificativo del RUN, il secondo il carattere sostituito, ed infine il terzo il numero di volte che il carattere deve essere ripetuto.

Run-length, il primo algoritmo di compressione immagini della storia

Dove Sc indica il carattere speciale per l’identificazione dell’inizio del RUN, X il carattere che viene ripetuto e C il numero di volte che il carattere viene ripetuto.

Es. aaaaeuuuuuuutt
Se '@' è il carattere di RUN, avremo:
@a4e@u7@t2

Se abbiamo un’immagine da comprimere, supponiamo che la prima riga dell’immagine contenga 100 pixel neri, l’algoritmo memorizzerà solo il pixel nero e il numero delle sue ripetizioni, il risparmio di dati è notevole!

Questo algoritmo funziona bene con testi ed immagini con pochi elementi (buone prestazioni si hanno se il RUN è più grande di 3 elementi), se gli elementi sono molti si rischierebbe di creare di occupare più spazio e di creare un inutile carico di lavoro per la riconversione dei file.

Questo algoritmo è stato molto utilizzato nei fax, dove ogni carattere era identificato in base al numero di pixel bianchi e pixel neri su ogni riga, generando un notevole risparmio nell’invio delle informazioni. Attualmente questo metodo ha fatto spazio alle elaborazioni grafiche al computer.

Pubblicato in Informatica, Programmazione Taggato con: , , , , , , ,

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

*