[C] Implementazione algoritmo compressione

[wlog]

Salve ragazzi,

ho scritto un algoritmo in CUDA (estensione per programmazione SIMD su schede grafiche) in grado di comprimere n^2 bit in input in 2*n bit (1 Gb diventa 2 Mb) con un errore che in norma è O(Emacchina), cioè piu piccolo del piu piccolo floating point a 32 bit che la macchina riesce a rappresentare.

Per ora gira dentro matlab: Matlab genera una matrice di dati, chiama la funzione CUDA, e restituisce il vettore rappresentante la compressione.

Siccome è un progetto universitario con tesina finale, vorrei implementare la cosa in modo pratico, ad esempio gestendo un flusso multimediale (audio? immagini? video?).
Io purtroppo sono un matematico e non un programmatore, e quindi non ho tutte le conoscenze di C necessarie: Come immaginate, devo comprimere solo i dati multimediali, e non eventuali overhead del formato, e quindi non posso passare brutalmente il file al codice CUDA.

Esiste un modo FACILE per implementare questo algoritmo su un flusso multimediale?

[Furla]

Originariamente inviato da wlog

in grado di comprimere n^2 bit in input in 2*n bit (1 Gb diventa 2 Mb) con un errore che in norma è O(Emacchina), cioè piu piccolo del piu piccolo floating point a 32 bit che la macchina riesce a rappresentare.

secondo i miei calcoli se n^2 = 1 Gb = 2^32 b => 2n = 2*2^16 b = 128 Kb
poi mi spieghi come funziona più o meno?

io credo che anche un semplice programma di archiviazione, se è solo a scopo dimostrativo, potrebbe andare bene...
se vorrai usarlo su file multimediali spero per te che esistano delle librerie apposite

[cdimauro]

Non funziona per qualunque tipo di dato, ovviamente. Ad esempio se prendi un file JPEG, Zip, o altro, sarà impossibile ottenere gli stessi livelli di compressione.

Per chi fosse interessato, nella FAQ della mailing list che parla di compressione c'è una dimostrazione a riguardo.

[wlog]

Originariamente inviato da Furla

secondo i miei calcoli se n^2 = 1 Gb = 2^32 b => 2n = 2*2^16 b = 128 Kb
poi mi spieghi come funziona più o meno?

io credo che anche un semplice programma di archiviazione, se è solo a scopo dimostrativo, potrebbe andare bene...
se vorrai usarlo su file multimediali spero per te che esistano delle librerie apposite

Pubblicherò un paper tutto precisino, ma ecco una spiegazione:

http://forums.nvidia.com/index.php?s...ic=77912&st=0#

(sono mascarpone)

sul calcolo hai ragione scusa, avevo fatto 10^10 bit (10 Gb) = 10^5 bit, ma la stanchezza mi ha tradito.

Originariamente inviato da cdimauro

Non funziona per qualunque tipo di dato, ovviamente. Ad esempio se prendi un file JPEG, Zip, o altro, sarà impossibile ottenere gli stessi livelli di compressione.

Per chi fosse interessato, nella FAQ della mailing list che parla di compressione c'è una dimostrazione a riguardo.

Perchè sarà impossibile scusa?

Sui zip non funziona perchè c'è bisogno che i dati siano esatti (mentre i miei hanno un, seppur piccolissimo, errore), ma su ogni formato in cui non sia richiesta l'esattezza dovrebbe funzionare.

[cdimauro]

Appunto. Il tuo è un algoritmo lossy, com'era intuibile.

Comunque si tratta di una notevole perdita di informazione: non credo che funzionerà per qualunque tipologia di dati (audio e video, ad esempio, hanno algoritmi di compressione lossy molto diversi: non li puoi gestire allo stesso modo).

[gugoXX]

Originariamente inviato da wlog

Perchè sarà impossibile scusa?

Sui zip non funziona perchè c'è bisogno che i dati siano esatti (mentre i miei hanno un, seppur piccolissimo, errore), ma su ogni formato in cui non sia richiesta l'esattezza dovrebbe funzionare.

Ciao.
Attenzione che anche i JPEG (e qualsiasi altro formato) hanno una parte che non deve essere distrutta, e che se anche eventualmente ulteriormente ricompressa deve poi essere assolutamente identica all'originale una volta riscompressa (Intestazioni, code, tabelle varie, etc.)

Comunque poni anche molta attenzione all'algoritmo di decompressione non solo a quello di compressione.
Anche io una volta mi ero illuso di aver trovato un algoritmo di compressione incredibile, che sembrava al di la' di ogni misura logaritmica.
Il dato finale era effettivamente molto molto compresso.
Peccato che pero' per la scompressione avessi bisogno di una chiave suppletiva (tipo spero non la tua matrice), senza la quale non potevo scomprimere un bel nulla, e che andava in pratica allegata al file compresso, altrimenti il file compresso risultava inutilizzabile.
Inutile dire che se sommavo insieme lo spazio del dato compresso e quello della matrice ottenevo un file che sembrava tutto tranne che piu' piccolo di uno zip.

[wlog]

Originariamente inviato da cdimauro

Appunto. Il tuo è un algoritmo lossy, com'era intuibile.

Comunque si tratta di una notevole perdita di informazione: non credo che funzionerà per qualunque tipologia di dati (audio e video, ad esempio, hanno algoritmi di compressione lossy molto diversi: non li puoi gestire allo stesso modo).

come ti ho detto, non viene perso nessun bit significativo.

[wlog]

Originariamente inviato da gugoXX

Ciao.
Attenzione che anche i JPEG (e qualsiasi altro formato) hanno una parte che non deve essere distrutta, e che se anche eventualmente ulteriormente ricompressa deve poi essere assolutamente identica all'originale una volta riscompressa (Intestazioni, code, tabelle varie, etc.)

Comunque poni anche molta attenzione all'algoritmo di decompressione non solo a quello di compressione.
Anche io una volta mi ero illuso di aver trovato un algoritmo di compressione incredibile, che sembrava al di la' di ogni misura logaritmica.
Il dato finale era effettivamente molto molto compresso.
Peccato che pero' per la scompressione avessi bisogno di una chiave suppletiva (tipo spero non la tua matrice), senza la quale non potevo scomprimere un bel nulla, e che andava in pratica allegata al file compresso, altrimenti il file compresso risultava inutilizzabile.
Inutile dire che se sommavo insieme lo spazio del dato compresso e quello della matrice ottenevo un file che sembrava tutto tranne che piu' piccolo di uno zip.

L'algoritmo già funziona, ora e adesso su Matlab. Devo solo effettuare il porting, solo che io non so riconoscere i dati intoccabili da quelli comprimibili

[cdimauro]

Originariamente inviato da wlog

come ti ho detto, non viene perso nessun bit significativo.

Con quegli ordini di grandezza in gioco l'informazione viene inevitabilmente persa.

Fidati, che ho lavorato per parecchio nel campo della compressione.

Originariamente inviato da wlog

L'algoritmo già funziona, ora e adesso su Matlab. Devo solo effettuare il porting, solo che io non so riconoscere i dati intoccabili da quelli comprimibili

Non ne verrai fuori: non puoi classificarli a priori senza conoscere nulla del contenuto che vai a comprimere.

E ribadisco: livelli di compressione così elevati implicano necessariamente una forte perdita di informazione, con le conseguenze del caso.

[wlog]

Non vorrei tirarmela, ma sono un matematico applicato, so di quello di cui parlo. Se vuoi avere piu informazioni ho postato un link in cui spiego l'algoritmo.

[gugoXX]

Originariamente inviato da wlog

L'algoritmo già funziona, ora e adesso su Matlab. Devo solo effettuare il porting, solo che io non so riconoscere i dati intoccabili da quelli comprimibili

Prova ad applicarlo ad una BMP non compressa.
Il formato della BMP non compressa e' davvero semplice. In pratica ci sono un paio di strutture iniziali, una tabella di colore e poi partono i dati dei pixel.
Fai prima un programmino che legge un BMP e ne carica la struttura,
e che salvi poi i dati delle strutture cosi' come sono e invece i dati dei pixel compressi.

Per la scompressione poi agisci al contrario.

[wlog]

Originariamente inviato da gugoXX

Prova ad applicarlo ad una BMP non compressa.
Il formato della BMP non compressa e' davvero semplice. In pratica ci sono un paio di strutture iniziali, una tabella di colore e poi partono i dati dei pixel.
Fai prima un programmino che legge un BMP e ne carica la struttura,
e che salvi poi i dati delle strutture cosi' come sono e invece i dati dei pixel compressi.

Per la scompressione poi agisci al contrario.

esistono delle librerie già implementate?

Perchè io già a caricare flussi di file in C non sono tanto buono....

[gugoXX]

Originariamente inviato da wlog

esistono delle librerie già implementate?

Perchè io già a caricare flussi di file in C non sono tanto buono....

Penso proprio di si'.
A suo tempo in C++ ne scrissi una per il TIFF non compresso.
Comunque tra leggere un file in C e interpretarne 2-3 valori e migrare un algoritmo di compressione da Matlab al C, direi che la seconda parte e' molto piu' lunga e complessa. (Se ti senti pronto per questa, la prima parte e' banale)

Comunque anche io ho un algoritmo lossy buonissimo. Si chiama media di colore. Prende un'immagine, fa la media pesata di tutti i colori e ne tira fuori uno solo. 1 byte.
decidere se il risultato di un algoritmo lossy e' buono o no e' una questione abbastanza soggettiva, ma non ho trovato nessuno che abbia dato un buon voto a questo mio ottimo risultato

[cdimauro]

Originariamente inviato da wlog

Non vorrei tirarmela, ma sono un matematico applicato, so di quello di cui parlo. Se vuoi avere piu informazioni ho postato un link in cui spiego l'algoritmo.

Non vorrei tirarmela pure io, ma sono un informatico "applicato" che ha studiato e lavorato per un po' di anni nel campo della compressione, in particolare delle immagini.

Leggi qui: http://profs.sci.univr.it/~quaglia/t...aries/cap3.pdf

Esiste una vasta gamma di trasformate ortogonali reversibili che sono adatte a scopi di
codifica e compressione. Sebbene in via teorica la trasformata migliore per le immagini sia
la trasformata di Karhunen-Loewe discreta, la più popolare in termini di sistemi
attualmente implementati e di standard stabiliti o proposti è la trasformata coseno discreta
(DCT) usata anche nello standard JPEG.

Ti assicuro che ci sono fior di matematici che hanno lavorato in questo campo e che sono arrivati alle conclusioni di cui sopra. Se cerchi con Google vedrai che di materiale in merito ne troverai a josa.

Il tuo algoritmo l'ho letto, ma prova a passare dalla carta al codice, e ti scontrerai con le limitazioni tipiche di un calcolatore coi tipi di dato in virgola mobile.

[cdimauro]

Originariamente inviato da gugoXX

Comunque anche io ho un algoritmo lossy buonissimo. Si chiama media di colore. Prende un'immagine, fa la media pesata di tutti i colori e ne tira fuori uno solo. 1 byte.
decidere se il risultato di un algoritmo lossy e' buono o no e' una questione abbastanza soggettiva, ma non ho trovato nessuno che abbia dato un buon voto a questo mio ottimo risultato

A dimostrazione di quanto ho già detto. Grazie per l'illuminante esempio.

[wlog]

Originariamente inviato da gugoXX

Penso proprio di si'.
A suo tempo in C++ ne scrissi una per il TIFF non compresso.
Comunque tra leggere un file in C e interpretarne 2-3 valori e migrare un algoritmo di compressione da Matlab al C, direi che la seconda parte e' molto piu' lunga e complessa. (Se ti senti pronto per questa, la prima parte e' banale)

Comunque anche io ho un algoritmo lossy buonissimo. Si chiama media di colore. Prende un'immagine, fa la media pesata di tutti i colori e ne tira fuori uno solo. 1 byte.
decidere se il risultato di un algoritmo lossy e' buono o no e' una questione abbastanza soggettiva, ma non ho trovato nessuno che abbia dato un buon voto a questo mio ottimo risultato

Ciao,

l'algoritmo usa matlab per gestire i dati, la compressione/decompressione è già scritta in cuda. Matlab insomma fa solo da interfaccia.

[wlog]

Originariamente inviato da cdimauro

Il tuo algoritmo l'ho letto, ma prova a passare dalla carta al codice, e ti scontrerai con le limitazioni tipiche di un calcolatore coi tipi di dato in virgola mobile.

Ragazzi come vi ho detto l'algoritmo è già scritto e funziona. Vi ripeto poi sulla qualità:

a) NON SI PERDE NESSUN BIT SIGNIFICATIVO

cioè

b) E' NUMERICAMENTE STABILE, LA NORMA DELLO SCARTO E' PIU PICCOLA DEL PIU PICCOLO FLOAT


Il fatto che quello sai l'algoritmo piu usato non me ne frega nulla, ho un algoritmo migliore e amen.


Poi ragazzi se non mi credete non mi offendo eh! Mica tutti devono credere ad una dimostrazione matematica! Si può anche credere alla magia nera se uno vuole!

[gugoXX]

Originariamente inviato da cdimauro

Il tuo algoritmo l'ho letto, ma prova a passare dalla carta al codice, e ti scontrerai con le limitazioni tipiche di un calcolatore coi tipi di dato in virgola mobile.

Per esempio, c'e' un algoritmo di compressione incredibile, che si basa su un teorema di rappresentazione frattale.
Per ciascuna immagine, qualsiasi essa sia, c'e' una formula di generazione frattale ed una coordinata tali per cui andando a sviluppare il frattale in quelle coordinate compare l'immagine originale. Senza perdita.
Perfetto. Basta quindi la descrizione della formula e le 2 coordinate.
La prima e' tipicamente una stringhetta, le altre 2 coordinate...
Peccato che per avere quanto serve le coordinate devono essere precisissime, e guarda caso la precisione necessaria e' talmente alta che la lunghezza della rappresentazione in base 2 delle 2 coordinate supera la dimensione dell'immagine originale.

[wlog]

sono contento che siate increduli, almeno so di avere un buon algoritmo tra le mani.


Comunque vi stupisco ancora di piu: all'inizio l'algoritmo comprimeva n*n dati in n+1 dati, solo che si perdeva la stabilità numerica nella decompressione.

[gugoXX]

Originariamente inviato da wlog

sono contento che siate increduli, almeno so di avere un buon algoritmo tra le mani.


Comunque vi stupisco ancora di piu: all'inizio l'algoritmo comprimeva n*n dati in n+1 dati, solo che si perdeva la stabilità numerica nella decompressione.

Guarda che non sono affatto stupito ne incredulo.
Come detto un algoritmo lossy puo' comprimere a piacere, quello che conta e' la quantita' di informazione persa e la similitudine soggettiva con l'originale.

Comunque ti consiglio di riscrivere anche la parte da CUDA ad un linguaggio utilizzabile per la produzione di un eseguibile normale, proprio per i fini di test.