View Full Version : [C] Implementazione algoritmo compressione
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?
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? :D
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
13-10-2008, 10:15
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. ;)
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? :D
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?showtopic=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.
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
13-10-2008, 11:13
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).
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.
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.
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
13-10-2008, 11:34
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.
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.
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.
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.
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.... :D :D :D
esistono delle librerie già implementate?
Perchè io già a caricare flussi di file in C non sono tanto buono.... :D :D :D
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
13-10-2008, 11:47
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" :D 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/tesi/binaries/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
13-10-2008, 11:48
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 :(
:rotfl: A dimostrazione di quanto ho già detto. Grazie per l'illuminante esempio. :)
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.
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!
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.
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.
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.
carino, quando scrivi il paper ce lo fai vedere? almeno una bozza... ma lavori per qualche università?
si esatto! Dipartimento di Matematica Unimi!
Verrà pubblicato un paper tutto precisino per gennaio/febbraio, ma comunque appena pronto metterò qualcosa online!
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.
Il fatto che non si perda qualità ormai l'ho ribaduto piu volte e l'ho dimostrato matematicamente.
Poi credete quello che volete credere.
Comunque se qualcuno ne conosce di C e ha voglia di aiutarmi ad implementare l'algoritmo mi mandi pure un pm!
Il fatto che non si perda qualità ormai l'ho ribaduto piu volte e l'ho dimostrato matematicamente.
Poi credete quello che volete credere.
Se per non perdere di qualita' intendi che l'algoritmo non e' lossy, allora non potrai scendere sotto quanto enunciato dal primo teorema di Shannon
http://it.wikipedia.org/wiki/Primo_teorema_di_Shannon
che per dati mediamente casuali risulta tendere al N LOG2 N.
Dimostrare matematicamente invece che un algoritmo lossy non perde di qualita' non e' per nulla semplice. Occorre definire cos'e' questa qualita', e dato che per definizione la partenza e l'arrivo non sono uguali, allora a seconda del modo che utilizzi per calcolare la distanza puoi avere che lo stesso risultato e' ottimo oppure pessimo.
L'unico vero metro di misura per gli algoritmi lossy e' il parere degli sperimentatori umani. Se su 100 presone 60 dicono che e' buono, allora sara' abbastanza buono...
Ma perche' proprio in C?
L'unico vero metro di misura per gli algoritmi lossy e' il parere degli sperimentatori umani. Se su 100 presone 60 dicono che e' buono, allora sara' abbastanza buono...
Come ho gia' detto, uso la definizione standard usata in IT: Presa una matrice in ingresso A, e presa la sua perturbata dA, allora la norma (in base 2) di A-dA sulla norma di dA e' piu piccola del piu piccolo float 32 bit rappresentabile dalla macchina
Ma perche' proprio in C?
Eh beh l'algoritmo e' in C.... Boh... Pulizia?
C non e' proprio sinonimo di pulizia, anzi.
E neppure tanto di maneggiabilita'.
Se per te il C# puo' essere preso in considerazione, ecco un pezzo, sicuramente non ottimizzato ne proprio pulito.
Ma e' stato scritto in 10 minuti...
e funziona (penso)
Accetta in input il nome di un file immagine in true color (quindi 16 o 24 bit direi)
Ne prende alcuni metadati, prende i dati e li tratta come matrice
Al posto che comprimere Inverte specularmente l'immagine su asseY e salva
L'opposto ovviamente torna indietro, salvando un BMP true color 24bit.
Poiche' il file finale che ho testato e' identico all'originale, ne consegue che dovrebbe funzionare.
class Program
{
static void Main(string[] args)
{
CompDecomp.FromFileToCompressed(@"C:\temp\Replica.bmp");
CompDecomp.FromCompressedToFile(@"C:\temp\Replica.comp",@"C:\temp\ReplicaOrig.bmp");
}
public static class CompDecomp
{
public static void FromFileToCompressed(string FileName)
{
Bitmap bp = new Bitmap(FileName);
int dimy = bp.Height;
int dimx = bp.Width;
Color[,] nc = new Color[dimy, dimx];
for (int y = 0; y < dimy; y++)
{
for (int x = 0; x < dimx; x++)
{
nc[y, x] = bp.GetPixel(x,y);
}
}
// Qui effettuare la compressione leggendo nc, ovvero la matrice di Color
// e ottenere un qualcosa (byte[],int[],float[] oppure di nuovo Color[]) da salvare
// Qui Esempio: la traformata semplicemente effettua una inversione speculare asse Y e non comprime nulla
// Mantengo quindi una matrice di colori, ma potrebbe non soddisfare l'esigenza.
Color[,] finale = new Color[dimy, dimx];
for (int y = 0; y < dimy; y++)
{
for (int x = 0; x < dimx; x++)
{
finale[y, x] = nc[y, dimx - x-1];
}
}
// Qui Salvare
//Salvo dimensioni.
string FPath = Path.GetDirectoryName(FileName);
string FName = Path.GetFileNameWithoutExtension(FileName);
FName=FName+".comp";
string NewFileName = Path.Combine(FPath, FName);
FileStream fs = File.OpenWrite(NewFileName);
BinaryWriter bw = new BinaryWriter(fs);
bw.Write(dimy);
bw.Write(dimx);
//bw.Write il flusso compresso, a seconda di cosa si e' deciso di usare
//Qui salvo quindi la matrice di colori su creata dopo la trasformazione
for (int y = 0; y < dimy; y++)
{
for (int x = 0; x < dimx; x++)
{
Color tosave=finale[y, x];
bw.Write(tosave.R);
bw.Write(tosave.G);
bw.Write(tosave.B);
}
}
bw.Close();
fs.Close();
}
public static void FromCompressedToFile(string Filename, string OutputFileName)
{
// Leggo
FileStream fr = File.OpenRead(Filename);
BinaryReader br = new BinaryReader(fr);
int dimy = br.ReadInt32();
int dimx = br.ReadInt32();
//Leggo e i restanti dati nel formato che mi serve byte[], Color[], float[], int[] etc.
//Qui e' di nuovo una matrice di colori
Color[,] comp = new Color[dimy, dimx];
for (int y = 0; y < dimy; y++)
{
for (int x = 0; x < dimx; x++)
{
byte r = br.ReadByte();
byte g = br.ReadByte();
byte b = br.ReadByte();
comp[y, x] = Color.FromArgb(r, g, b);
}
}
br.Close();
fr.Close();
Color[,] orig=new Color[dimy,dimx];
//Uso i dati e li scomprimo , riempiendo di nuovo la matrice colore
// Qui di nuovo inverto speculare Y
for (int y = 0; y < dimy; y++)
{
for (int x = 0; x < dimx; x++)
{
orig[y, x] = comp[y, dimx - x-1];
}
}
//Creo la bitmap per salvarla
Bitmap bt = new Bitmap(dimx, dimy, PixelFormat.Format24bppRgb);
for (int y = 0; y < dimy; y++)
{
for (int x = 0; x < dimx; x++)
{
// Qui decido che colore del pixel
Color tobeused = orig[y, x];
bt.SetPixel(x, y, tobeused);
}
}
//Salvo
bt.Save(OutputFileName, ImageFormat.Bmp);
}
}
}
cdimauro
13-10-2008, 13:34
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!
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.
Facciamo una cosa. Supponiamo che ti dia in input un file di n byte. Se il tuo algoritmo non perde nulla, allora applicalo m volte (con m < n ovviamente) fino a quando non otterrai un file di 1 solo byte.
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.
Lui dice che la precisione viene preservata. :)
Io dico che, viste le eccezionali proprietà di cui è dotato, applicando il suo algoritmo un certo numero di volte avremo trovato la soluzione a tutti i problemi di spazio passati, presenti e futuri. :O
Facciamo una cosa. Supponiamo che ti dia in input un file di n byte. Se il tuo algoritmo non perde nulla, allora applicalo m volte (con m < n ovviamente) fino a quando non otterrai un file di 1 solo byte.
Ciao,
applicando l'algoritmo 2 volte si perde la stabilita' numerica (o meglio, l'errore va come il quadrato invece di essere lineare), applicando l'algoritmo n volte invece le risorse richieste saranno un intorno di infinito per n sufficentemente grande.
X Gugo:
grazie ma mi sono dimenticato di dirvi che uso linux quindi non credo il c# si possa usare...
In compenso ho trovato sul sito di matlab (dietro indirizzo del mio prof) che esiste una funzione imread, imwrite per leggere e scrivere file BMP o TIFF come se fossero normali matrici.
Ho dei dubbi pero':
The return value A is an array containing the image data. If the file contains a grayscale image, A is an M-by-N array. If the file contains a truecolor image, A is an M-by-N-by-3 array. For TIFF files containing color images that use the CMYK color space, A is an M-by-N-by-4 array. See TIFF in the Format-Specific Information section for more information.
http://www.mathworks.com/access/helpdesk/help/techdoc/index.html?/access/helpdesk/help/techdoc/ref/imformats.html&http://www.mathworks.com/access/helpdesk/help/techdoc/ref/imread.html
Quindi io mi prendo una immagine TIFF CMYK per aumentare al massimo la complessita' del problema.... solo che cos'e' un array M-by-N-by-4? Mo vado in laboratorio e provo....
Dove posso trovare delle immagini campione difficili da comprimere? (o qualunque cosa questo possa voler dire)
cdimauro
13-10-2008, 13:54
In buona sostanza lo si applica una sola volta.
Bene, a questo punto passa alla prova sperimentale con un'immagine e vediamo se l'intera informazione viene preservata. ;)
In buona sostanza lo si applica una sola volta.
Bene, a questo punto passa alla prova sperimentale con un'immagine e vediamo se l'intera informazione viene preservata. ;)
Al momento non ho un computer con scheda geforce... quindi devo programmare in emulazione. Ma ho ordinato un desktop da 800 euro (solo il desk, da mettere in cantina e usare in remoto con SSH) e arrivera' domani da eprice. Vi prometto che per lunedi vi posto qualcosa. Il problema e' che non ho abbastanza soldi per prendermi una scheda grafica figa, quindi nel frattempo, se qualcuno ha matlab (magari con jacket) e una scheda geforce carina, potrebbe (se vuole) aiutarmi a testare il codice.
Per ora giochiamo con le immaginette... l'idea e' di comprimere file video in real time per permettere un miglior uso della banda.
Ciao,
X Gugo:
grazie ma mi sono dimenticato di dirvi che uso linux quindi non credo il c# si possa usare...
Per testare l'algoritmo un qualunque linguaggio decente va bene.
M by N by 4 dovrebbe voler dire una matrice tridimensionale, oppure se vuoi una matrice bidimensionale la cui cella e' a sua volta un vettore di 4 valori.
Ovviamente non potrai usare la imwrite per salvare il tuo dato compresso, proprio perche' non e' un'immagine ma e' una rappresentazione che solo il tuo algoritmo sa riconoscere.
Esattamente come ho fatto io li' sopra in C#.
Dovrai quindi studiarti com salvare file binari normali.
(E poi come leggerli, per il duale della decompressione)
Al momento non ho un computer con scheda geforce... quindi devo programmare in emulazione. Ma ho ordinato un desktop da 800 euro (solo il desk, da mettere in cantina e usare in remoto con SSH) e arrivera' domani da eprice. Vi prometto che per lunedi vi posto qualcosa. Il problema e' che non ho abbastanza soldi per prendermi una scheda grafica figa, quindi nel frattempo, se qualcuno ha matlab (magari con jacket) e una scheda geforce carina, potrebbe (se vuole) aiutarmi a testare il codice.
Per ora giochiamo con le immaginette... l'idea e' di comprimere file video in real time per permettere un miglior uso della banda.
Non capisco cosa centri la scheda grafica.
L'algoritmo matematico non ha bisogno di alcuna scheda grafica per funzionare no? Puoi scriverlo in qualsiasi linguaggio.
Per testare l'algoritmo un qualunque linguaggio decente va bene.
M by N by 4 dovrebbe voler dire una matrice tridimensionale, oppure se vuoi una matrice bidimensionale la cui cella e' a sua volta un vettore di 4 valori.
Ovviamente non potrai usare la imwrite per salvare il tuo dato compresso, proprio perche' non e' un'immagine ma e' una rappresentazione che solo il tuo algoritmo sa riconoscere.
Esattamente come ho fatto io li' sopra in C#.
Dovrai quindi studiarti com salvare file binari normali.
(E poi come leggerli, per il duale della decompressione)
Ciao: prendo il file, lo leggo, lo comprimo, lo decomprimo, lo scrivo e poi pubblico sul forum i risultati.
Lo sto facendo or ora.
Non capisco cosa centri la scheda grafica.
L'algoritmo matematico non ha bisogno di alcuna scheda grafica per funzionare no? Puoi scriverlo in qualsiasi linguaggio.
Sono frettoloso scusa: la magagna e' che l'algoritmo e' computazionalmente intenso e quindi per girare bene e' scritto in parallelo per architettura GPGPU CUDA.
problema: Matlab mi legge degli interi, ma poi il mio algoritmo lavora sui float. Questo puo causare un po di problemi.
Non esiste un formato che sia float 32 nativo?
cdimauro
13-10-2008, 14:57
Non dovrebbe bastare moltiplicare tutti gli interi letti per 1.0?
SerMagnus
13-10-2008, 15:17
chissà come andrà a finire :D
cdimauro
13-10-2008, 16:11
Una cosa è sicura: ne resterà soltanto uno. :D
Non dovrebbe bastare moltiplicare tutti gli interi letti per 1.0?
ciao,
si si potrebbe fare un cast prima a float in compressione e poi a int in decompressione, pero' l'errore sarebbe nell'ordine di 1 invece che di 10 alla -32....
che dati viaggiano su flussi float? gli mp3?
ciao,
si si potrebbe fare un cast prima a float in compressione e poi a int in decompressione, pero' l'errore sarebbe nell'ordine di 1 invece che di 10 alla -32....
che dati viaggiano su flussi float? gli mp3?
No, che mi risulti niente.
Sono tutti quantizzati su interi.
comunque se ho capito bene, a te dovrebbe bastare dividere ogni componente di colore per 256.
Ovvero moltiplicare per 0.00390625
(se ho capito bene hai bisogno di partire con valori compresi tra 0 e 1)
Oppure in alternativa puoi prendere i 3 valori RGB, tenerli impacchettati come sono (e hai quindi un intero tra 0 e 16 milioni e passa) e farci il reciproco.
Hai di nuovo un valore tra 0 e 1, ma sono tutti insieme...
ovvio che qui quando e se ci dovesse essere un errore potrebbe andare a cadere di piu' su una componente piuttosto che distribuirsi tra tutte, ma se l'algoritmo di compressione e' non-lossy non ci dovrebbero essere problemi.
Perché lavori su floating point a 32 bit e non usi quelli a 80 bit ?
No, che mi risulti niente.
Sono tutti quantizzati su interi.
comunque se ho capito bene, a te dovrebbe bastare dividere ogni componente di colore per 256.
Ovvero moltiplicare per 0.00390625
(se ho capito bene hai bisogno di partire con valori compresi tra 0 e 1)
ciao,
no no, a me va bene qualsiasi floating point rappresentabile sulla macchina, da 0 a 7 miliardi di milioni e via... solo che uno dei primissimi passi dell'algoritmo e' quello di dividere due elementi della matrice tra di loro.... quindi tipo se divito 17 per 13 (sparo un caso) poi casto a float e poi casto a int chissa che cosa succede alla stabilità numerica.... di sicuro va a puttane...
certo è che magari l'algoritmo ottiene dei risultati decenti lo stesso....
Da qualche parte avevo letto che esisteva un metodo numericamente stabile per rappresentare sequenze di Int come un float... qualcuno ne sa qualcosa? boh...
Oppure in alternativa puoi prendere i 3 valori RGB, tenerli impacchettati come sono (e hai quindi un intero tra 0 e 16 milioni e passa) e farci il reciproco.
Hai di nuovo un valore tra 0 e 1, ma sono tutti insieme...
ovvio che qui quando e se ci dovesse essere un errore potrebbe andare a cadere di piu' su una componente piuttosto che distribuirsi tra tutte, ma se l'algoritmo di compressione e' non-lossy non ci dovrebbero essere problemi.
si ma io ho bisogno di poter lavorare su ogni singolo floating point.... come faccio a distinguerli poi???
E se casti subito a float tutto dall'inizio e tieni in virgola mobile fino alla fine?
si ma io ho bisogno di poter lavorare su ogni singolo floating point.... come faccio a distinguerli poi???
Non dovrebbe cambiare nulla. L'importante e' che l'algoritmo sia senza perdita.
Se e' davvero senza perdita, quando scomprimerai otterrai di nuovo 3 cose impacchettate, ma che si potranno separare semplicemente alla fine di tutto.
Perché lavori su floating point a 32 bit e non usi quelli a 80 bit ?
80 bit??? esistono floating cosi grandi????
ehehheh comunque perchè scrivo su piattaforma GPGPU, e li si ha il picco delle performance a 32 bit
80 bit??? esistono floating cosi grandi????
Se è per questo li puoi fare grandi a piacere lavorandoci un po'.
Su Matlab credo che siano di default a 64 o 80 bit.
Se è per questo li puoi fare grandi a piacere lavorandoci un po'.
Gia'.
tutta un'immagine potrebbe stare su un unico floating point.
Anche compreso tra 0 e 1 se serve...
0 virgola tutti i bit dell'immagine.
E se casti subito a float tutto dall'inizio e tieni in virgola mobile fino alla fine?
Ciao,
a pagina 165 di Numerical Linear Algebra (http://www.amazon.com/Numerical-Linear-Algebra-Lloyd-Trefethen/dp/0898713617) trovi l'esempio di una matrice patologica il cui errore cresce come 2^p, dove p è la lunghezza di un vettore colonna (n in una matrice n*n) con l'algoritmo dell'eliminazione di gauss, perchè lui tratta gli int e le frazioni come floating.... :(
Se è per questo li puoi fare grandi a piacere lavorandoci un po'.
Su Matlab credo che siano di default a 64 o 80 bit.
eheheh si lo so il problema è la moltiplicazione. Metti che io abbia [122 233 245] che diventa 0.122233245 e [211 322 254] che diventa 0.211322254 e voglia moltiplicarli tra di loro... come faccio in un modo numericamente stabile? moltiplico solo alcune cifre? computazionalmente costa troppo moltiplicare solo alcune cifre...
Sì, è il classico problema dell'accumulazione degli errori di rappresentazione.
eheheh si lo so il problema è la moltiplicazione. Metti che io abbia [122 233 245] che diventa 0.122233245 e [211 322 254] che diventa 0.211322254 e voglia moltiplicarli tra di loro... come faccio in un modo numericamente stabile? moltiplico solo alcune cifre? computazionalmente costa troppo moltiplicare solo alcune cifre...
Lavora su interi ;) Lavori su interi grandi a piacere (esistono librerie per farlo e credo che matlab lo permetta già di suo).
La conversione in float la fai solo dopo.
raga do un bacetto a chi mi trova un formato multimediale con wrapper per c incluso che usi flussi di dati in floating e che non sia troppo complicato...
Lavora su interi ;) Lavori su interi grandi a piacere (esistono librerie per farlo e credo che matlab lo permetta già di suo).
La conversione in float la fai solo dopo.
si ma se voglio dividere due interi?
E comunque CUDA lavora bene solo con gli FP :( non è mica un vero super computer... solo la brutta copia :(
raga do un bacetto a chi mi trova un formato multimediale con wrapper per c incluso che usi flussi di dati in floating e che non sia troppo complicato...
Ma ti ho gia' proposto di prendere l'immagine, e considerare ciascuna componente di colore non come un numero che va da 0 a 256, ma come un numero che va da 0 a 1, prendendo il reciproco di ciascun numero (oppure dividendo ciascun valore originale per 256)
Non va bene?
Ma ti ho gia' proposto di prendere l'immagine, e considerare ciascuna componente di colore non come un numero che va da 0 a 256, ma come un numero che va da 0 a 1, prendendo il reciproco di ciascun numero (oppure dividendo ciascun valore originale per 256)
Non va bene?
è vero.... Sei un grande. Sai che non avevo capito?
Sei davvero un grande!
Mercoledi che ho il laboratorio tutto per me lo provo!
edit: mi sono accorto facendo due calcoli che seppur funzioni, si perde l'enorme guadagno... perchè 8 bit vengono rappresentati usandone 32.... boh mo provo e vedo....
Non esiste un formato che invece di 8 bit usi 16 o 32 bit?
Le immagini HDR hanno 32 per ogni canale di colore, forse possono andare bene per le tuo prove.
cdimauro
13-10-2008, 19:30
ciao,
si si potrebbe fare un cast prima a float in compressione e poi a int in decompressione, pero' l'errore sarebbe nell'ordine di 1 invece che di 10 alla -32....
Non vedo perché: se lavori sempre in floating point e soltanto alla fine di tutta l'elaborazione fai un truncate/arrotondamento a intero, hai perso il minimo. Al contrario, se passi spesso da float a intero e viceversa gli errori "esploderanno".
ciao,
no no, a me va bene qualsiasi floating point rappresentabile sulla macchina, da 0 a 7 miliardi di milioni e via... solo che uno dei primissimi passi dell'algoritmo e' quello di dividere due elementi della matrice tra di loro.... quindi tipo se divito 17 per 13 (sparo un caso) poi casto a float e poi casto a int chissa che cosa succede alla stabilità numerica.... di sicuro va a puttane...
certo è che magari l'algoritmo ottiene dei risultati decenti lo stesso....
Come vedi ti stai già scontrando coi problemi tipici che hanno i calcolatori quando si tratta di rappresentare valori in virgola mobile. Te l'avevo detto prima. ;)
Intanto, come dicevo sopra, potresti lavorare sempre in floating e soltanto alla fine convertire i valori in interi, in modo da ridurre al minimo gli errori dovuti alle continue conversioni.
Da qualche parte avevo letto che esisteva un metodo numericamente stabile per rappresentare sequenze di Int come un float... qualcuno ne sa qualcosa? boh...
Se converti un intero a float non hai nessuna perdita, posto che l'intero rientri nel range di valori rappresentabili senza, appunto, perdere alcunché. Questo dipende strettamente dalla dimensione della mantissa dei float.
Gia'.
tutta un'immagine potrebbe stare su un unico floating point.
Anche compreso tra 0 e 1 se serve...
0 virgola tutti i bit dell'immagine.
:asd:
Ciao,
a pagina 165 di Numerical Linear Algebra (http://www.amazon.com/Numerical-Linear-Algebra-Lloyd-Trefethen/dp/0898713617) trovi l'esempio di una matrice patologica il cui errore cresce come 2^p, dove p è la lunghezza di un vettore colonna (n in una matrice n*n) con l'algoritmo dell'eliminazione di gauss, perchè lui tratta gli int e le frazioni come floating.... :(
Potresti utilizzare... le frazioni: http://docs.python.org/whatsnew/2.6.html#the-fractions-module
To fill out the hierarchy of numeric types, the fractions module provides a rational-number class. Rational numbers store their values as a numerator and denominator forming a fraction, and can exactly represent numbers such as 2/3 that floating-point numbers can only approximate.
The Fraction constructor takes two Integral values that will be the numerator and denominator of the resulting fraction.
>>> from fractions import Fraction
>>> a = Fraction(2, 3)
>>> b = Fraction(2, 5)
>>> float(a), float(b)
(0.66666666666666663, 0.40000000000000002)
>>> a+b
Fraction(16, 15)
>>> a/b
Fraction(5, 3)
For converting floating-point numbers to rationals, the float type now has an as_integer_ratio() method that returns the numerator and denominator for a fraction that evaluates to the same floating-point value:
>>> (2.5) .as_integer_ratio()
(5, 2)
>>> (3.1415) .as_integer_ratio()
(7074029114692207L, 2251799813685248L)
>>> (1./3) .as_integer_ratio()
(6004799503160661L, 18014398509481984L)
Note that values that can only be approximated by floating-point numbers, such as 1./3, are not simplified to the number being approximated; the fraction attempts to match the floating-point value exactly.
:cool:
Sì, è il classico problema dell'accumulazione degli errori di rappresentazione.
Esattamente.
E comunque CUDA lavora bene solo con gli FP :( non è mica un vero super computer... solo la brutta copia :(
Non è una brutta copia: il suo lavoro lo fa bene. Anzi, le GPU ormai fanno molto di più di quello per cui sono state progettate, per cui... tanto di cappello. :p
Le immagini HDR hanno 32 per ogni canale di colore, forse possono andare bene per le tuo prove.
Dipende da come viene implementato l'HDR. Non c'è uno standard preciso. Tutte e 3 le componenti del colore, ad esempio, si potrebbero impacchettare in un solo valore a 32 bit. ;)
raga do un bacetto a chi mi trova un formato multimediale con wrapper per c incluso che usi flussi di dati in floating e che non sia troppo complicato...
Ma poi non ti basta creare uno stream di chesso', 50.000 valori floating point casuali?
Provi a comprimere, provi a scomprimere e vedi cosa succede.
cdimauro
13-10-2008, 21:03
:rotfl: Mi fai morire!!! Stasera finisce che mi ribalto e sveglio tutti col botto. :p
Ma poi non ti basta creare uno stream di chesso', 50.000 valori floating point casuali?
Provi a comprimere, provi a scomprimere e vedi cosa succede.
si si quello si puo' tranquillamente fare!
la questione e' che alla gente vedere una serie di floating point gliene frega poco... vedere le immagini prima e dopo invece fanno ohhhhhhhhhhhhhh
eheheheh
cdimauro
13-10-2008, 21:39
Quella di "gugo" non era esattamente una battuta, eh!
E' un degno "figlio" di Shannon. :p
wingman87
13-10-2008, 21:53
si si quello si puo' tranquillamente fare!
la questione e' che alla gente vedere una serie di floating point gliene frega poco... vedere le immagini prima e dopo invece fanno ohhhhhhhhhhhhhh
eheheheh
A me piacerebbe molto vederlo, mi sembra un argomento molto interessante
blackskop
13-10-2008, 23:09
Questa discussione è l'unica che mi ha preso da quando sono iscritto :D Attendo inviluppi :mc:
Ma poi non ti basta creare uno stream di chesso', 50.000 valori floating point casuali?
Provi a comprimere, provi a scomprimere e vedi cosa succede.
shannon, mcmillan e compagnia cantante si staranno rivoltando nella tomba leggendo questo thread :p
ragazzi mi e' appena arrivato il pc nuovo... non posso usarlo ancora perche' non ho la tastiera...
Lo sto montando... Q6600 4 gb di ram, geforce 8400 e una tesla in prestito (deve ancora arrivare).
Comunque oggi ho caricato il mio algoritmo sul supercomputer del dipartimento, e ho scoperto che non funziona molto bene (ho potuto usarlo su una gran quantita di matrici). In compenso ne ho parlato con alcuni prof e so come metterlo apposto...
Notevole la frase di un prof: Non ci credo che il tuo algoritmo funzioni ma non riesco a trovare un motivo per cui non debba funzionare
ehehhehe
cdimauro
14-10-2008, 20:02
Allora aspettiamo i risultati dei tuoi esperimenti.
Mi raccomando: oltre al test con un'immagine reale, prova anche con una avente tutti i pixel generati con valori cromatici casuali, similmente a quanto suggeriva gugo. :)
Mattyfog
14-10-2008, 20:35
vorrei fare una domanda da ignorante quattordicenne:
ma perchè se gente comune inventa cose del genere noi usiamo gli zip?
Allora aspettiamo i risultati dei tuoi esperimenti.
Mi raccomando: oltre al test con un'immagine reale, prova anche con una avente tutti i pixel generati con valori cromatici casuali, similmente a quanto suggeriva gugo. :)
come ho detto sono partito testandolo su matrici casuali!!! Volevo delle immagini tanto per far vedere le applicazioni
vorrei fare una domanda da ignorante quattordicenne:
ma perchè se gente comune inventa cose del genere noi usiamo gli zip?
Perche' il mio algoritmo ha un errore piccolissimo, mentre zip ha un errore nullo.
E poi perche' il mio algoritmo e' cosi pesante che e' impensabile usarlo in seriale su un normale x86 (almeno secondo l'attuale tecnologia)
ragazzi comunque se volete finanziare la ricerca universitaria italiana potreste comprarmi (o finanziarmi) una scheda tesla!!! o almeno una GTX260....
programmare in emulazione ha un casino di magagne... e poi e' LENTISSIMO....
cdimauro
14-10-2008, 21:25
vorrei fare una domanda da ignorante quattordicenne:
ma perchè se gente comune inventa cose del genere noi usiamo gli zip?
Per lo stesso motivo per cui si usa Zip e non 7-Zip, JPEG e non JPEG 2000, e così via: per abitudine e perché un certo formato è diventato LO standard di fatto.
come ho detto sono partito testandolo su matrici casuali!!! Volevo delle immagini tanto per far vedere le applicazioni
OK, ma puoi provarlo (quando avrai il codice "finale") anche con matrici casuali?
Perche' il mio algoritmo ha un errore piccolissimo, mentre zip ha un errore nullo.
Se l'errore fosse realmente piccolo e "perfettamente riproducibile" si potrebbe pensare di memorizzare il risultato della tua trasformata e la differenza coi dati originali in modo da poterli ricostruire esattamente. ;)
E poi perche' il mio algoritmo e' cosi pesante che e' impensabile usarlo in seriale su un normale x86 (almeno secondo l'attuale tecnologia)
Intanto implementalo correttamente, che a velocizzarlo c'è tempo per pensarci. :cool:
ragazzi comunque se volete finanziare la ricerca universitaria italiana potreste comprarmi (o finanziarmi) una scheda tesla!!! o almeno una GTX260....
programmare in emulazione ha un casino di magagne... e poi e' LENTISSIMO....
Prova con piccoli dati prima.
Intanto implementalo correttamente, che a velocizzarlo c'è tempo per pensarci. :cool:
Prova con piccoli dati prima.
Quoto. Prova anche solo con un paio di KB all'inizio. Poi ad ottimizzare se non ti viene in mente nulla ti diamo una mano noi.
E mi raccomando di fare le cose per bene, ovvero di scrivere e distinguere bene i 2 algoritmi e di fare quindi 2 programmi, uno per la compressione e uno per la decompressione.
Ovviamente l'informazione che esce dalla parte di compressione (possibilmente salvato su disco) deve essere l'unico input per il programma di decompressione.
Non ho ancora capito se e' senza perdita o se e' con perdita. Ho letto un paio di interventi dove ho capito che l'errore e' piu' basso del piu' piccolo float rappresentabile, e sarebbe quindi senza perdita essendo che per la macchina l'originale e lo scompresso sarebbero identici.
Altre volte invece ho letto che non si potrebbe applicare ripetutamente perche' gli errori divergerebbero.
Comunque pensa, un'immagine 1000x1000 si potrebbe comprimere in 2KB
E un immagine 3000x3000 in 6KB.
E un film HD di 25fotogrammi secondo 1000x1000 starebbe in 2KB*25*3600 = 180MB. Altro che BlueRay, ne fai stare 4 su un CD vecchio.
Certo che gli altri matematici finora hanno dormito un po' tutti.
Altro che BlueRay, ne fai stare 4 su un CD vecchio
Se ragioni per spazio e non per frame: un Blueray da 25 GB in 317 KB :eek:
Secondo me alla fine l'errore di rappresentazione è tutt'altro che piccolo. Mi spiego: è vero che hai un errore piccolo per ogni float, però hai un errore che si ripete per ogni float...moltiplicato per ogni float l'errore totale mi sembra altino.
L'errore di rappresentazione di un floating point a 32 bit può essere anche davvero alto, considerando la mantissa a soli 22 bit con l'esponente valorizzato a 1.
cdimauro
15-10-2008, 09:23
Mah. Già questo http://www.hwupgrade.it/forum/showpost.php?p=24545003&postcount=28 e questo http://www.hwupgrade.it/forum/showpost.php?p=24545003&postcount=29 uniti a questo http://www.hwupgrade.it/forum/showpost.php?p=24551965&postcount=56 lasciano intuire dovremo si andrà a finire. :O
Comunque... attendiamo. :p
rеpne scasb
15-10-2008, 11:23
■
cdimauro
15-10-2008, 19:52
programmare in emulazione ha un casino di magagne... e poi e' LENTISSIMO....
Quoto. Prova anche solo con un paio di KB all'inizio.
* ;)
Se ti serve una libreria per la single value decomposition ne dovrei avere una in C++
44 Pentium in fila per 3 col resto di 1.9999458374...
ciao ragazzi non sono scomparso, mangio due cose veloci e poi vi aggiorno
ok.
Iniziamo con le notizie cattive:
1) l'errore non è piu piccolo del piu piccolo float rappresentabile. Ad esserlo è ||dA||/||A|| cioè la norma dello scarto sulla norma della matrice.
2) Per ora l'algoritmo funziona per le matrici 2*2. Sto lavorando per farlo crescere di dimensione.
Il fatto è che piu la dimensione della matrice cresce, piu l'errore cresce, dovrei fare alcune stime ma penso che 32 bit di precisione bastano al massimo per matrici 3*3.
Comunque con precisione arbitraria possiamo avere matrici grandi a piacere....
Comprimere matrici 3*3 in vettori di lunghezza 6 vuol dire un rapporto di 3/2, cioè 30 mb diventano venti.
Vi sembra comunque un buon risultato? vale la pena di lavorarci su?
Ah mi sono dimenticato la cosa positiva: essendo le matrici cosi piccole l'algoritmo si puo applicare 2 volte ALMENO.
variabilepippo
16-10-2008, 18:21
Comprimere matrici 3*3 in vettori di lunghezza 6 vuol dire un rapporto di 3/2, cioè 30 mb diventano venti.
Vi sembra comunque un buon risultato? vale la pena di lavorarci su?
Su MaximumCompression (http://www.maximumcompression.com/index.html#MFC) trovi un confronto tra algoritmi di compressione loseless applicati a dati reali (nello specifico un "paniere" di 510 files per un totale di 310MB) e non a matrici di piccole dimensioni, i migliori hanno un rapporto di compressione dell'80%, i 310MB iniziali diventano 62MB, senza perdite, i peggiori ottengono un rapporto di compressione del 50%.
beh dati reali sono solo molte matrici vicine... dovrei di sicuro applicarlo piu e piu volte...
grazie per il link comunque, sapere che esistono algoritmi cosi efficenti...
comunque stavo controllando la mia mail ,e il mio prof mi ha mandato un consiglio per stabilizzare l'algoritmo, magari riusciamo ad aumentare la dimensione massima....
ok.
Iniziamo con le notizie cattive:
....
ci riprovo, parafrasando quanto detto qualche giorno fa da cesare.
NON E' POSSIBILE che un algoritmo di compressione SENZA PERDITA possa funzionare sempre (ovvero comprimendo con addirittura una ratio ben specifica) indipendentemente dalla qualita' e distribuzione dei dati in ingresso.
Se cosi' fosse, applicando piu' volte lo stesso algoritmo di compressione ai dati appena compressi (anch'essi dati, ne piu' ne meno nobili che gli originali), allora arriveresti a compressione totale, e in particolare potresti fare stare tutto su una sola Word (unita' singola di informazione). Ovviamente la cosa non ha senso.
Quindi non si puo' dire che 32bit bastino per le matrici 3x3. Se bastassero potresti continuare ricorsivamente.
Riesci a fare un esempio numerico a mano con una matrice 3x3, anche senza parlare di bit, anche facendo solo i calcoli e scrivendo le formule e le matrici, facendoci vedere i passaggi?
3*3 è lunghissimo, lo faccio 2*2.
COMPRESSIONE:
Prendo la matrice A 2*2. La scompongo usando l'SVD.
Ottengo due vettori normali (matrice U), gli svd (2 valori lungo la matrice diagonale S) e altri due vettori normali (la matrice V).
so che A*V=U*S
A=U*S*V'
mi registro un vettore di U u1 e la diagonale di S.
DECOMPRESSIONE:
Prendo u1. Cerco i vettori normali, ne ho 2: scelgo quello il cui angolo con u1 in senso orario è piu piccolo. (questa è la parte difficile da applicare sopra la dimensione 2, difficile ma fattibile).
Applico la trasformazione lineare alla matrice calcolata U=[u1; normale di u1] e ottengo V. Traspongo V e calcolo U*S*V'=A
Dai, fallo in modo numerico, prenditi una matrice originale decente e prova a mettere giu' 2 calcoli.
Ti faccio notare che la 2x2 non guadagna nulla, in quanto per la diagonale e il vettore hai di nuovo bisogno di 4 valori (quindi non comprimi).
Ti tocca farlo per forza almeno per la 3x3
Usa Matlab...
ok.
Modifche all'algoritmo: Invece di conservare 2 vettori di lunghezza n, ne conserviamo 3. Uno per gli SVD e due per le basi di U e V. In questo modo la stabilità aumenta enormemente e il giochino si può applicare per matrici fino a ordine 8.
Ok prendiamo una classe di matrici che mal sopporta il mio algoritmo.
A=magic(3);
[u, s, v]=svd(A);
u1=u(1,:,:);
v1=v(1,:,:);
Ecco la compressione è finita, salviamo u1, v1, s1 e ripartiamo.
u2=u1*rot2;
u3=u1*rot3;
u=[u1;u2;u3];
Allora rot1 e rot3 sono due matrici 3*3 che fanno ruotare il vettore intorno all'asse y (rot2) o z (rot3) di 90°. Capite benissimo che si possono calcolare da voi:
http://en.wikipedia.org/wiki/Rotation_matrix
applichiamo lo stesso giochetto a v
v2=....
...
...
A1=u*diag(s)*v';
||A-A1||/||A||
L'ultima riga non è commentata perchè cosi facendo vi stampa l'errore. Dovrebbe venirvi un bello zero.
A=magic(3);
[u, s, v]=svd(A);
u1=u(1,:,:);
v1=v(1,:,:);
Salvo A, v1, u1, s
u2=u1*rot2;
u3=u1*rot3;
u=[u1;u2;u3];
v2=v1*rot5;
v3=u1*rot6;
v=[v1;v2;v3];
A1=u*diag(s)*v';
||A-A1||/||A||
Non ho specificato il calcolo delle matrici rot(i) perchè esistono due matrici: quella positiva e quella negativa. Una fa ruotare il vettore di 90°, l'altra di 270° (-90°). Per ora non mi viene in mente un modo intelligente di applicarlo a matlab (mente in c ho una funzione già scritta) per cui tocca a voi calcolarvela usando le regole trovate su wikipedia, e vedendo quale delle due è giusta.
Per questo vi dicevo che il metodo a 3 dimensioni ancora lo stavo studiando... in 2 dimensioni basta il proiettore di householder:
p=I-2*u1*u1'
Se qualcuno si chiede perchè è diventato 3n invece di 2n ecco la risposta:
http://en.wikipedia.org/wiki/Singular_value_decomposition#Geometric_meaning
Dovrei prendere la sfera, calcolarmi la rotazione in base allo span di U, mapparla e trovare l'iperellisse, calcolarmi la rotazione in base allo span di V, e rimappare u*s.
Insomma non banale da fare su due piedi e soprattutto, numericamente poco stabile.
Bene, e' un passo avanti.
Pero' ti proporrei di fare veramente i calcoli anche solo per un esempio. Uno solo.
Chesso', prendi la matrice
[1,2,3]
[4,5,6]
[7,8,9]
E calcola in modo geometrico le varie parti.
Intendo, dove ci fosse un "Radice di 2", lascia pure radice di 2, non svilupparlo numericamente.
Agli errori ci si pensa alla fine, quando si passa a quantizzare sui bit.
Giusto per vedere i contributi necessari.
Insomma, una 3X3, fatta a mano o con l'ausilio di qualsiasi mezzo, giusto per tastare con mano che alla fine i conti tornano.
Mi ricordo che a suo tempo Jordanizzavo, invertivo, trovavo autovalori, su matrici ben piu' grandi delle 3x3.
Non ho mai fatto a mano una singular value decomposition, ma non penso che sia una cosa fuori dal mondo per una 3x3.
Come stimolo pensa che se mai dovesse funzionare, ti aiuto a progettare un microprocessore che sviluppa solo quello, e lo montiamo su computer di mezzo mondo.
E' una proposta.
Insomma, anche noi, prima di scrivere un algoritmo, proviamo sempre con 4 dati in croce se per caso i risultati vengono. (Guarda i vari contest)
Addirittura i test vengono fatti cosi'. Prima scrivi l'input e l'output attesi, e l'algoritmo dovra' verificarli a priori.
Ciao scusa non ho capito bene cosa intendi, se fai andare il mio algoritmo trovi che l'errore come definito è nullo.
Vuoi che ti dia i valori delle matrici di rotazione?
Ti prometto che per martedi mi faccio aiutare dal mio prof e scrivo un algoritmo che calcoli la matrice di rotazione ALMENO per il caso 3 e 4.
Ciao scusa non ho capito bene cosa intendi, se fai andare il mio algoritmo trovi che l'errore come definito è nullo.
Vuoi che ti dia i valori delle matrici di rotazione?
Ti prometto che per martedi mi faccio aiutare dal mio prof e scrivo un algoritmo che calcoli la matrice di rotazione ALMENO per il caso 3 e 4.
No, intendo che mi piacerebbe vedere i passaggi per una matrice nota, data come input.
Non le formule numeriche, proprio i risultati di ciascun passaggio, dato come input p.es. la matrice di cui sopra.
Cosi' da toccare con mano:
Questi sono i 3 valori del vettore u1
Questi sono i 3 valori della matrice S
E poi la decompressione, con i vari passaggi matematici applicati ai valori appena trovati.
La generalizzazione delle formula la si fa dopo.
P.es. io non mi sono mai sognato di scrivere l'algoritmo per la diagonalizzazione secondo Jordan, e non ci voglio nemmeno pensare.
Pero' a mano, data una matrice ben specifica, facevo i calcoli e diagonalizzavo...
A=magic(3);
[u, s, v]=svd(A);
u1=u(1,:,:);
v1=v(1,:,:);
A =
8 1 6
3 5 7
4 9 2
u1 =
-0.5774 0.7071 0.4082
v1 =
-0.5774 0.4082 0.7071
u2=u1*rot2;
u3=u1*rot3;
u=[u1;u2;u3];
v2=v1*rot5;
v3=u1*rot6;
v=[v1;v2;v3];
A1=u*diag(s)*v';
norm(A-A1)/norm(A)
metodo veloce per calcolarsi le matrici di rotazione (cosi generalizziamo rispetto al singolo caso)
ua=[u1; u1*(u1\u2); u1*(u1\u3)]
ua è la matrice u ricostruita, u1\ui è un modo di barare per calcolarsi la matrice di rotazione.
Stessa cosa per v.
quindi AA=ua*s*va'
norm(AA-A)/norm(A)
ans =
4.894059581559813e-15
Questo perchè abbiamo barato nel calcolare la matrice di rotazione. Avessimo usato le vere matrici di rotazione che sono... [il resto a tra poco]
cade il castello di carte:
Le rotazioni sono un sottogruppo orgonale SO(3)... il problema è che salvando i vettori u1, s e v1 noi andiamo ad usare n*n locazioni di memoria...
l'inghippo è che non esiste un metodo numericamente stabile per ricavare V da U .... :( :( :(
adesso ci vorrebbe qualcuno molto piu bravo di me che trovi un metodo... o magari lo potrei fare io lungo la mia carriera...
:(:(:(
cdimauro
17-10-2008, 08:06
In decine d'anni di studi non c'è riuscito nessuno: mettiti il cuore in pace.
Il problema è, come abbiamo cercato di farti capire fin dall'inizio, legato strettamente alla natura dell'informazione. Non puoi giocare coi dati come vuoi pretendendo di conservarla.
Di Shannon esiste un TEOREMA in proposito, e da buon matematico dovresti conoscere molto bene il significato di questa parola e dell'altra a esso legata: DIMOSTRAZIONE.
I tuoi studi invaliderebbero di colpo le tesi di questo teorema, poiché permetteresti di allocare una frazione infima di spazio a fronte di tutta l'informazione.
Il che è ovviamente impossibile non soltanto per il teorema di cui sopra, ma anche per un po' di sano buon senso.
Esempio (ma non solo :D) pratico (visto che siamo informatici, e agli informatici servono gli esempi, come suol ripetere il mitico prof. Nicolosi del dipmat di Catania :p).
Supponiamo di essere riusciti a trovare un sistema di compressione eccezionale che permette di comprimere qualunque tipo di dati occupando la metà dello spazio. L'algoritmo è garantito essere stabile e perfettamente funzionante se usato soltanto la prima volta. Ma, come ricordava gugo, non c'è niente al mondo che m'impedisca di riutilizzare i dati generati dalla prima applicazione anche a una seconda, e poi ancora a una terza, e così via. Questo perché... SEMPRE DI DATI si tratta.
Forte di ciò posso ripetere questo processo fino a quando non avrò ottenuto un solo byte, e qui mi posso anche fermare. Per memorizzare i risultati di questo processo però dovrò far ricorso a due byte: il primo che mi dice quante volte ho dovuto applicare l'operazione e il secondo col risultato vero e proprio. Non penso sia una gran perdita utilizzare un "prezioso" altro byte, no? :D
In questo modo posso comprimere file che vanno da 0 a 2^255 byte: penso sia più che sufficiente anche per conservare i dati dell'LHC. :D
Veniamo alla pratica. Usare un solo byte per condensare tutta l'informazione equivale a 2^8 = 256 possibili valori. Ma dobbiamo tener conto anche del numero di volte che è stato applicato l'algoritmo, per cui abbiamo altre 2^8 = 256 possibilità. Mettendo assieme questi risultati possiamo dire che sono sufficienti 256 * 256 = 65536 combinazioni per memorizzare l'informazione presente in QUALUNQUE file di dimensione variabile da 0 a 2^255 byte.
A questo punto possiamo decidere di buttare chiavette USB, BluRay, sistemi di memorizzazione olografici, nastri magnetici, ecc. ecc. Basta tenere a mente un numero di 5 cifre massimo per "portarsi dietro" miliardi di miliardi di miliardi di miliardi di... ecc. ecc. di dati. :p
OK, penso che basti. Sei ancora convinto di procedere coi tuoi studi? ;)
RaouL_BennetH
17-10-2008, 08:22
In decine d'anni di studi non c'è riuscito nessuno: mettiti il cuore in pace.
Il problema è, come abbiamo cercato di farti capire fin dall'inizio, legato strettamente alla natura dell'informazione. Non puoi giocare coi dati come vuoi pretendendo di conservarla.
Di Shannon esiste un TEOREMA in proposito, e da buon matematico dovresti conoscere molto bene il significato di questa parola e dell'altra a esso legata: DIMOSTRAZIONE.
I tuoi studi invaliderebbero di colpo le tesi di questo teorema, poiché permetteresti di allocare una frazione infima di spazio a fronte di tutta l'informazione.
Il che è ovviamente impossibile non soltanto per il teorema di cui sopra, ma anche per un po' di sano buon senso.
Esempio (ma non solo :D) pratico (visto che siamo informatici, e agli informatici servono gli esempi, come suol ripetere il mitico prof. Nicolosi del dipmat di Catania :p).
Supponiamo di essere riusciti a trovare un sistema di compressione eccezionale che permette di comprimere qualunque tipo di dati occupando la metà dello spazio. L'algoritmo è garantito essere stabile e perfettamente funzionante se usato soltanto la prima volta. Ma, come ricordava gugo, non c'è niente al mondo che m'impedisca di riutilizzare i dati generati dalla prima applicazione anche a una seconda, e poi ancora a una terza, e così via. Questo perché... SEMPRE DI DATI si tratta.
Forte di ciò posso ripetere questo processo fino a quando non avrò ottenuto un solo byte, e qui mi posso anche fermare. Per memorizzare i risultati di questo processo però dovrò far ricorso a due byte: il primo che mi dice quante volte ho dovuto applicare l'operazione e il secondo col risultato vero e proprio. Non penso sia una gran perdita utilizzare un "prezioso" altro byte, no? :D
In questo modo posso comprimere file che vanno da 0 a 2^255 byte: penso sia più che sufficiente anche per conservare i dati dell'LHC. :D
Veniamo alla pratica. Usare un solo byte per condensare tutta l'informazione equivale a 2^8 = 256 possibili valori. Ma dobbiamo tener conto anche del numero di volte che è stato applicato l'algoritmo, per cui abbiamo altre 2^8 = 256 possibilità. Mettendo assieme questi risultati possiamo dire che sono sufficienti 256 * 256 = 65536 combinazioni per memorizzare l'informazione presente in QUALUNQUE file di dimensione variabile da 0 a 2^255 byte.
A questo punto possiamo decidere di buttare chiavette USB, BluRay, sistemi di memorizzazione olografici, nastri magnetici, ecc. ecc. Basta tenere a mente un numero di 5 cifre massimo per "portarsi dietro" miliardi di miliardi di miliardi di miliardi di... ecc. ecc. di dati. :p
OK, penso che basti. Sei ancora convinto di procedere coi tuoi studi? ;)
Ciao Cesare :)
Come sai, io non sono ne un matematico ne un informatico, ma sono un curioso e un ficcanaso irrecuperabile :cool:
Volevo solo fare una piccolissima considerazione che, n.b., va aldilà di questo caso specifico.
Proprio la storia della matematica e della scienza in generale, secondo il mio parere, ci 'dimostra' sempre un'unica cosa:
Che tutta la conoscenza acquisita e 'dimostrata' nel presente, può di colpo cambiare perchè nasce una nuova teoria che invalida tutte le precedenti, altrimenti non ci sarebbero mai state ne evoluzioni, ne rivoluzioni scientifiche.
Molti matematici e scienziati in passato venivano scoraggiati dai propri colleghi, inseguendo ricerche che parevano impossibili da portare a termine.
Credo sia un bene che alcuni di quelli, non si siano lasciati scoraggiare, aldilà del risultato raggiunto.
Il supporto che tu e molti altri come te, con una preparazione che è davvero fenomenale (per la quale nutro una sincera e piacevole invidia) è preziosissimo per tanti di noi, però... cercate di non arrabbiarvi troppo quando magari non si coglie il vostro suggerimento sin dall'inizio :) Certe volte ognuno deve sbattere il grugno sul muro da solo prima di poter dire:
"Cavolo, se gli avessi dato retta avrei speso il mio tempo in maniera migliore " :p
Sono comunque consapevolissimo che sulla quasi totalità delle cose i vostri non sono atti di scoraggiamento, ma, dato che avete affrontato prima sulla vostra pelle questi problemi, vorreste evitare agli altri inutili mal di testa :)
RaouL.
cade il castello di carte:
Le rotazioni sono un sottogruppo orgonale SO(3)... il problema è che salvando i vettori u1, s e v1 noi andiamo ad usare n*n locazioni di memoria...
l'inghippo è che non esiste un metodo numericamente stabile per ricavare V da U .... :( :( :(
adesso ci vorrebbe qualcuno molto piu bravo di me che trovi un metodo... o magari lo potrei fare io lungo la mia carriera...
:(:(:(
Ciao, cosa intendi per numericamente stabile qui? Fai conto di avere precisione infinita. Esiste un modo per passare da u a v senza utilizzare alcuna altra informazione?
Io comunque asserisco che non e' possibile far funzionare il tutto neppure se ti portassi dietro sia U che V che la diagonale.
Questo perche' dalla dimensione 4 in poi, accadrebbe che sarebbe sufficente memorizzare i 3 vettori (anche la diagonale e' un vettore), con quindi una quantita' di informazione pari a 3*4 = 12 elementi, per ricostruire ipoteticamente tutte le matrici da 4*4 = 16 elementi.
E piu' si dovesse salire di rango e piu' il gioco varrebbe la candela.
Quindi, sei sicuro che avendo i 2 vettori e la diagonale tutto funzionerebbe?
Prova numericamente con una 4*4, anche cosi' se funzionasse ci sarebbe da guadagnare tantissimo, soprattutto su dimensioni molto alte.
Per il resto sono d'accordo con Raoul. Io mi ci sono messo davvero tante volte a sbattere la testa. Diciamo che "si sente" se si sta sbattendo la testa contro qualcosa di duro oppure qualcosa che si puo' rompere.
E questa volta la vedo proprio dura, altrimenti il ragionamento di Cesare implicherebbe assurdi logici insuperabili.
Anche se e' vero che talvolta le regole del gioco vengono ribaltate da nuove idee, resta che alcuni assunti non si riescono proprio ribaltare.
cdimauro
17-10-2008, 13:27
Ciao "RaouL" :)
Concordo con gugo. Poi non è che ci arrabbiamo, eh! :) Semplicemente penso che se una persona ha accumulato un po' di esperienza in un certo settore possa far da "guida" a chi si avventura, cercando di non fargli perdere tempo.
Io mi sono appassionato per anni al campo della compressione, e ho studiato, ho fatto ricerca (ho sviluppato una serie di algoritmi particolari), ho sviluppato applicazioni, ecc. E se c'è qualcosa che non va, che non mi "suona bene", lo capto ed espongo le mie "riserve", cercando di essere utile.
Tutto qui. :)
OK, penso che basti. Sei ancora convinto di procedere coi tuoi studi? ;)
Ciao,
un paio di cose:
A) Hai ragione sul teorema di shannon, ma esso richiede determinate ipotesi. Come ad esempio la volontà di mappare biunivocamente i dati, che a me non interessa.
B) L'algoritmo si può applicare piu volte, è vero, ma si può perdere la stabilità numerica nel ricostruirlo. Esistono modelli di compressione che usano una sola parola per comprimere una quantità di dati anche infinita: si chiamano qubit, o rappresentazione quantistica dell'informazione.
C) Esiste già un caso in cui la pratica ha violato i teoremi: guarda il quicksort che in teoria è asintoticamente l'algoritmo migliore di sorting, che nella pratica però viene battuto dal radix sort. Proprio perchè, come dicevo prima, si violano le ipotesi per sfuggire alla tesi.
Quindi, sei sicuro che avendo i 2 vettori e la diagonale tutto funzionerebbe?
Prova numericamente con una 4*4, anche cosi' se funzionasse ci sarebbe da guadagnare tantissimo, soprattutto su dimensioni molto alte.
CIao,
avendo precisione infinita basterebbe tenersi u1 e s.
Per ricostruire V devi usare U e s, ma il problema è che i valori di s diventano molto vicini allo zero molto in fretta.
Generando casualmente 1 miliardo di matrici 5*5, solo il 12% aveva il quinto SVD piu grande del piu piccolo FP32.
Magari lavorando a 80 bit si salvava il quinto valore... però il fatto che aumentando il numero di bit si aumenta anche lo spazio occupato...
ps.: numericamente stabile vuol dire che introducendo un piccolo errore (come è normale nella rappresentazione a n finiti bit) il risultato varia di poco.
pps: Autovalori a valori singolari sono molto simili. Calcolare gli SVD di M equivale a calcolare gli autovalori di M*M, da qui il motivo per cui la fattorizzazione SVD esiste per tutte le matrici.
CIao,
avendo precisione infinita basterebbe tenersi u1 e s.
Per ricostruire V devi usare U e s, ma il problema è che i valori di s diventano molto vicini allo zero molto in fretta.
Generando casualmente 1 miliardo di matrici 5*5, solo il 12% aveva il quinto SVD piu grande del piu piccolo FP32.
Magari lavorando a 80 bit si salvava il quinto valore... però il fatto che aumentando il numero di bit si aumenta anche lo spazio occupato...
Non solo, io asserisco che non funziona senza perdita neppure se ti salvi tutti e 3 i vettori da 4 elementi per ricostruire una matrice 4x4.
Parti pure presupponendo di avere sia U che V che una matrice diagonale.
In pratica staresti cercando di compattare R^16 in R^12,
ovvero che ciascun singolo risultato di una matrice compattata sara' il riusultato di circa R^4 altre matrici sorgente.
e ovviamente la biunivocita' non puo' essere assicurata.
Se invece non stai cercando la biunivocita', allora dovrai ammettere che l'algoritmo non potra' avere un errore piu' piccolo del piu' piccolo float.
Resta che se riesci ad avere un errore basso decente per la 4x4, allora comunque hai guadagnato parecchio in modo deterministico. Soprattutto se ci si alza di dimensione.
Prova a fare i conti portandoti dietro sia U che V che la diagonale su un esempio numerico di una 4x4
Non solo, io asserisco che non funziona senza perdita neppure se ti salvi tutti e 3 i vettori da 4 elementi per ricostruire una matrice 4x4.
Parti pure presupponendo di avere sia U che V che una matrice diagonale.
In pratica staresti cercando di compattare R^16 in R^12,
ovvero che ciascun singolo risultato di una matrice compattata sara' il riusultato di circa R^4 altre matrici sorgente.
e ovviamente la biunivocita' non puo' essere assicurata.
Se invece non stai cercando la biunivocita', allora dovrai ammettere che l'algoritmo non potra' avere un errore piu' piccolo del piu' piccolo float.
Resta che se riesci ad avere un errore basso decente per la 4x4, allora comunque hai guadagnato parecchio in modo deterministico. Soprattutto se ci si alza di dimensione.
Prova a fare i conti portandoti dietro sia U che V che la diagonale su un esempio numerico di una 4x4
ok,
adesso però è venerdi pomeriggio... giornata dedicata allo svacco! eheheheh
ok,
adesso però è venerdi pomeriggio... giornata dedicata allo svacco! eheheheh
Ma certo, ci mancherebbe.
Beato te.
cdimauro
17-10-2008, 20:48
Ciao,
un paio di cose:
A) Hai ragione sul teorema di shannon, ma esso richiede determinate ipotesi. Come ad esempio la volontà di mappare biunivocamente i dati, che a me non interessa.
Ma interessa se vuoi comprimere e poi decomprimere. Altrimenti non ha senso parlare di compressione, ma di trasformazione.
B) L'algoritmo si può applicare piu volte, è vero, ma si può perdere la stabilità numerica nel ricostruirlo.
Si perde sicuramente perché, come ti dicevo, non puoi comprimere l'informazione oltre un certo livello senza necessariamente perderla.
Inoltre ti faccio notare ancora una volta che il risultato di una prima applicazione del tuo algoritmo produce dei DATI. Poiché il tuo algoritmo lavora su qualunque dato (addirittura su dati casuali), si dovrebbero poter passare i dati della prima elaborazione per processarli nuovamente senza perdere la stabilità di cui parli.
In soldoni: se applichi il tuo algoritmo su QUALUNQUE dato una sola volta e affermi che la ricostruzione è "stabile", allora logica alla mano la stessa proprietà deve continuare a valore anche applicandolo a dati già processati.
Esistono modelli di compressione che usano una sola parola per comprimere una quantità di dati anche infinita: si chiamano qubit, o rappresentazione quantistica dell'informazione.
Che non è il nostro caso mi pare: i modelli di compressione che servono attualmente e ai quali stai lavorando si applicano al funzionamento dei calcolatori non quantistici.
C) Esiste già un caso in cui la pratica ha violato i teoremi: guarda il quicksort che in teoria è asintoticamente l'algoritmo migliore di sorting, che nella pratica però viene battuto dal radix sort. Proprio perchè, come dicevo prima, si violano le ipotesi per sfuggire alla tesi.
Vero, ma non è questo il caso. Qui è l'informazione che è in gioco, e non puoi giocare a nascondino.
Inoltre ti faccio notare ancora una volta che il risultato di una prima applicazione del tuo algoritmo produce dei DATI. Poiché il tuo algoritmo lavora su qualunque dato (addirittura su dati casuali), si dovrebbero poter passare i dati della prima elaborazione per processarli nuovamente senza perdere la stabilità di cui parli.
In soldoni: se applichi il tuo algoritmo su QUALUNQUE dato una sola volta e affermi che la ricostruzione è "stabile", allora logica alla mano la stessa proprietà deve continuare a valore anche applicandolo a dati già processati.
Si ma se la stabilità numerica non è una relazione transitiva: Se A è stabile con B, e B con C, non è detto che A sia stabile con C
Vero, ma non è questo il caso. Qui è l'informazione che è in gioco, e non puoi giocare a nascondino.
shannon ci dice che ci sarà errore... non quanto....
DanieleC88
18-10-2008, 14:40
Si ma se la stabilità numerica non è una relazione transitiva: Se A è stabile con B, e B con C, non è detto che A sia stabile con C
Se l'algoritmo di compressione è valido, comprimi A in B. Poi prendi B e lo comprimi in C. Se funziona, devi essere in grado di decomprimere da C a B e poi ancora da B ad A. Perché no? :)
Se l'algoritmo di compressione è valido, comprimi A in B. Poi prendi B e lo comprimi in C. Se funziona, devi essere in grado di decomprimere da C a B e poi ancora da B ad A. Perché no? :)
stai facendo un po di confusione tra algoritmi che comprimono attraverso scambi di bit, e algoritmi che funzionano attraverso operazioni sui floating point.
DanieleC88
18-10-2008, 20:42
stai facendo un po di confusione tra algoritmi che comprimono attraverso scambi di bit, e algoritmi che funzionano attraverso operazioni sui floating point.
Quasi certamente è così, di compressione ci capisco ben poco. Ma mi pare di capire che i risultati non siano univoci ma possano essere ambigui, e sono abituato a pensare alle compressioni in modo che non siano ambigue, tutto qui. :)
Alkaiser
18-10-2008, 23:51
interessantissimo:D
mi iscrivo così leggo;)
cdimauro
19-10-2008, 14:59
Si ma se la stabilità numerica non è una relazione transitiva: Se A è stabile con B, e B con C, non è detto che A sia stabile con C
Non è questo il punto. Il punto è che se A è una matrice di dati QUALSIASI, come hai sostenuto finora, allora se prendiamo il risultato di una prima applicazione del tuo algoritmo anche il suo risultato è una matrice di dati qualsiasi e, quindi, abbiamo tutto il diritto di darla in pasto nuovamente al tuo codice.
Mi sembra che la logica non faccia una grinza, no?
Oppure vogliamo ammettere una buona volta che il risultato della computazione dipende fortemente dai dati in ingresso e pertanto il tuo NON è un algoritmo "generalizzabile"? :O
shannon ci dice che ci sarà errore... non quanto....
Indubbiamente, ma non pecco di presunzione se affermo che più informazione distruggi e più possibilità ci sono che l'errore commesso sia grande. :fagiano:
Non è questo il punto. Il punto è che se A è una matrice di dati QUALSIASI, come hai sostenuto finora, allora se prendiamo il risultato di una prima applicazione del tuo algoritmo anche il suo risultato è una matrice di dati qualsiasi e, quindi, abbiamo tutto il diritto di darla in pasto nuovamente al tuo codice.
Mi sembra che la logica non faccia una grinza, no?
Oppure vogliamo ammettere una buona volta che il risultato della computazione dipende fortemente dai dati in ingresso e pertanto il tuo NON è un algoritmo "generalizzabile"? :O
Provo a farti un esempio.
Io ho un algoritmo A (Output=input+1), che preso in input I mi restituisce l'output O. Facciamo che io lavoro su una macchina fuffa, il cui minimo errore rappresentabile sia 1 (lavora quindi sui interi) ma con il rounding error compensation (basta usare la normale notazione fisica delle cifre significative) diventa 0.49.
Ora io metto I1=1 e ricevo O1=2.3=2
Inserisco I2=2.3 e ricevo O2=3.51=4
Come vedi i passaggi sono numericamente stabili, ma la stabilità non è transitiva.
cdimauro
19-10-2008, 15:40
Rispondi a questa domanda: i dati in input al tuo algoritmo possono essere di QUALUNQUE tipo?
Così tagliamo la testa al toro una volta per tutte.
Rispondi a questa domanda: i dati in input al tuo algoritmo possono essere di QUALUNQUE tipo?
Così tagliamo la testa al toro una volta per tutte.
Si.
cdimauro
19-10-2008, 17:08
In tal caso il tuo algoritmo lo si può applicare quante volte lo si vuole. Con tutte le conseguenze del caso di cui abbiamo già parlato.
Provo a farti un esempio.
Io ho un algoritmo A (Output=input+1), che preso in input I mi restituisce l'output O. Facciamo che io lavoro su una macchina fuffa, il cui minimo errore rappresentabile sia 1 (lavora quindi sui interi) ma con il rounding error compensation (basta usare la normale notazione fisica delle cifre significative) diventa 0.49.
Ora io metto I1=1 e ricevo O1=2.3=2
Inserisco I2=2.3 e ricevo O2=3.51=4
Come vedi i passaggi sono numericamente stabili, ma la stabilità non è transitiva.
Ciao wlog, provo a riassumere i dubbi.
Questo algoritmo e' chiaramente con perdita.
Quando leggi 2, non saprai se scompresso e' 1 oppure 0
Proprio come quando leggi 4 non saprai se scompresso e' 3 oppure 2
In altre parole invece.
se il primo passaggio fosse senza perdita, ovvero se si riuscisse a tornare esattamente ai dati di partenza, allora lo sarebbero anche eventuali passaggi successivi.
Sei riuscito a tirare giu' un esempio numerico 4x4, ammettendo di avere sia U che V che la diagonale per svolgere l'inversa?
In tal caso il tuo algoritmo lo si può applicare quante volte lo si vuole. Con tutte le conseguenze del caso di cui abbiamo già parlato.
No, perché lui non dice che non c'è perdita di informazione. Riapplicandolo si perde informazione quindi si può riapplicare, ma diventa chiaro che l'informazione persa sarà maggiore e le implicazioni sulla qualità dei dati iniziali potrebbero anche essere imprevedibili.
Chiaro che non potrà mai esistere un algoritmo senza perdita che comprime sempre e comunque N dati in M, con N > M.
cdimauro
19-10-2008, 18:42
D'accordissimo, ma lui prima ha affermato che il suo algoritmo può lavorare con qualunque dato, quindi sulla carta anche con quelli provenienti da una prima applicazione dello stesso.
Se ci sono problemi con le applicazioni successive allora non è vero che può operare con qualunque dato, ma il suo sarà quindi un sistema condizionato.
Quindi vale quanto dicevo prima:
il risultato della computazione dipende fortemente dai dati in ingresso e pertanto l'algoritmo non è "generalizzabile"
Se ci sono problemi con le applicazioni successive allora non è vero che può operare con qualunque dato, ma il suo sarà quindi un sistema condizionato.
Il problema è che l'errore cresce! Come con qualsiasi operazione floating point!
Ti faccio un esempio: Se io parto con dei dati esatti alla 16a cifra decimale, la prima compressione potrà ricostruirli perdendo AL massimo la 16a cifra, quindi con 15 cifre esatte. Una ulteriore compressione però porterà dati esatti alla 2a cifra decimale, perchè l'errore passa da O(1) a O(n^4)...
cdimauro
19-10-2008, 19:32
Ma guarda che l'ho capito. Il punto rimane lo stesso: il tuo algoritmo NON può operare con QUALUNQUE dato, altrimenti si applicherebbe quanto ho già detto.
Non se ne esce fuori, logica alla mano. C'è poco da fare.
Ciao wlog, provo a riassumere i dubbi.
Questo algoritmo e' chiaramente con perdita.
si ma la perdita è piu piccola del piccolo float rappresentabile
Quando leggi 2, non saprai se scompresso e' 1 oppure 0
Proprio come quando leggi 4 non saprai se scompresso e' 3 oppure 2
e quindi devi approssimare, come nella realtà.
Ovviamente il mio esempio è grossolano, ma ti assicuro che vale anche per numeri ben piu piccoli.
In altre parole invece.
se il primo passaggio fosse senza perdita, ovvero se si riuscisse a tornare esattamente ai dati di partenza, allora lo sarebbero anche eventuali passaggi successivi.
la perdita ci sarebbe, ma sarebbe anche molto piccola.
Sei riuscito a tirare giu' un esempio numerico 4x4, ammettendo di avere sia U che V che la diagonale per svolgere l'inversa?
Ho un piccolo problema: dovrei trovare una matrice dei gruppi rotazionali SO(4) formulata in base ad una direzione di un asse generico ed ad un angolo generico. Il problema è che non sono riuscito a trovarla ne tra i miei libri, ne tra le risorse online. Domani provo in biblioteca.
Ma guarda che l'ho capito. Il punto rimane lo stesso: il tuo algoritmo NON può operare con QUALUNQUE dato, altrimenti si applicherebbe quanto ho già detto.
Non se ne esce fuori, logica alla mano. C'è poco da fare.
Scusa ma anche l'algoritmo output=input+1 non si può applicare a qualunque dato?
cdimauro
19-10-2008, 19:41
Non sempre: dipende dall'algoritmo, appunto.
Poi continui ad affermare che l'errore è più piccolo del più piccolo float rappresentabile, e ciò informaticamente parlando equivale a NESSUNA perdita.
Quindi potrei dare in pasto al tuo algoritmo anche un file zip compresso: sulla carta dovrebbe riuscire a digerirlo tranquillamente e a "sputare fuori" un file molto più piccolo. Il che farebbe ribaltare Shannon nella tomba. :p
Una consiglio ragazzi: Se devo scrivere l'algoritmo (questo o uno qualsiasi), è meglio farlo prima in Matlab e poi portarlo in C+MPI/CUDA, oppure scriverlo direttamente senza portarlo?
variabilepippo
19-10-2008, 19:51
Con Matlab puoi implementare velocemente il prototipo al fine di verificare che la tua idea funzioni, poi puoi ottimizzarlo riscrivendolo in C. Comunque, vedendo ciò che scrivi nell'altro post, credo che tu debba studiare un po' meglio il C prima di poterlo usare per l'ottimizzazione del codice.
si ma la perdita è piu piccola del piccolo float rappresentabile
I casi sono 2:
- Algoritmo di compressione lossy --> la versione decompressa non coincide con l'originale
- Algoritmo di compressione loseless --> la versione decompressa coincide esattamente con l'originale
Se l'algoritmo è loseless puoi applicarlo quante volte vuoi fornendo in ingresso l'output dell'iterazione precedente, ovviamente ad un certo punto ti scontrerai con il teorema di Shannon. :)
la perdita ci sarebbe, ma sarebbe anche molto piccola.
Quindi si tratta di una compressione lossy...
Non sempre: dipende dall'algoritmo, appunto.
e come fai a distinguere il mio algoritmo che non hai mai visto dall'algoritmo sopra citato?
Poi continui ad affermare che l'errore è più piccolo del più piccolo float rappresentabile, e ciò informaticamente parlando equivale a NESSUNA perdita.
Qua ci vuole una precisazione dovuta. L'ho omessa all'inizio perchè mi sembrava solo una inutile complicazione, ma dato che tu mi sembri interessato all'argomento mi dilungo un attimo:
Seguendo le definizioni formali dell'algebra lineare numerica abbiamo che forward stable vuol dire che
||dX||/||X||=O(Emachine)
Cioè vuol dire che la norma della variazione normalizzata rispetto all'input è definitivamente inferiore dell'Epsilon macchina.
Tu capisci che non è pratico dire questa frase tutte le volte, quindi a tutti i corsi sentirai dire:
L'errore è O di Epsilon macchina. Oppure: l'errore è piu piccolo del piu piccolo float rappresentabile (definizione di Epsilon macchina).
In realtà si nascondono diverse insidie:
a) Attraverso alcuni accorgimenti si possono rappresentare numeri piu piccoli di Em
b) Dire "definitivamente inferiore" è diverso dal dire "è piu piccolo di", anche se erroneamente vengono usati come sinonimi per comodita.
Qui vi potrete schiarire i vostri dubbi:
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic3/
http://www.nist.gov/dads/HTML/bigOnotation.html
c) Intuitivamente quello che dici tu sembra essere giusto. Ma tu stai chiedendo qualcosa di più: la backward stability. Una condizione molto forte che non sempre può essere soddisfatta.
Eccoti qualcosa per saziare la tua sete di sapere:
[edit: di questo non sono riuscito a trovare una fonte decente online mi spiace]
http://www.google.it/url?sa=t&source=web&ct=res&cd=1&url=http%3A%2F%2Fwww-math.mit.edu%2F~persson%2F18.335%2Flec10handout2pp.pdf&ei=AYT7SLCWJJLO0gWXpKSNDw&usg=AFQjCNFFySVIsTCLC2UWV1bU2o6hUdeWqw&sig2=wLD5c5L7bbdrV5HWnqfgyg
Con Matlab puoi implementare velocemente il prototipo al fine di verificare che la tua idea funzioni, poi puoi ottimizzarlo riscrivendolo in C. Comunque, vedendo ciò che scrivi nell'altro post, credo che tu debba studiare un po' meglio il C prima di poterlo usare per l'ottimizzazione del codice.
Si hai ragione è che non programmo da un pò in c, mi sono dedicato soprattutto a java/M...
Mi sono rimesso a fare i miei vecchi esercizi :)
Quindi si tratta di una compressione lossy...
Come qualsiasi operazione sui floating point, è impensabile essere lossyless. Altrimenti sarebbe semplicemente un algoritmo di scambio sui bit, e non sui FP.
cdimauro
19-10-2008, 20:05
Una consiglio ragazzi: Se devo scrivere l'algoritmo (questo o uno qualsiasi), è meglio farlo prima in Matlab e poi portarlo in C+MPI/CUDA, oppure scriverlo direttamente senza portarlo?
Puoi realizzarlo in Python che fai prima. Ed eventualmente con psyco puoi accelerare (anche notevolmente) i calcoli, visto che converte il bytecode delle funzioni in codice x86. :cool:
cdimauro
19-10-2008, 20:10
e come fai a distinguere il mio algoritmo che non hai mai visto dall'algoritmo sopra citato?
Mi baso sulle tue affermazioni che hai fatto finora.
Qua ci vuole una precisazione dovuta. L'ho omessa all'inizio perchè mi sembrava solo una inutile complicazione, ma dato che tu mi sembri interessato all'argomento mi dilungo un attimo:
Seguendo le definizioni formali dell'algebra lineare numerica abbiamo che forward stable vuol dire che
||dX||/||X||=O(Emachine)
Cioè vuol dire che la norma della variazione normalizzata rispetto all'input è definitivamente inferiore dell'Epsilon macchina.
Tu capisci che non è pratico dire questa frase tutte le volte, quindi a tutti i corsi sentirai dire:
L'errore è O di Epsilon macchina. Oppure: l'errore è piu piccolo del piu piccolo float rappresentabile (definizione di Epsilon macchina).
In realtà si nascondono diverse insidie:
a) Attraverso alcuni accorgimenti si possono rappresentare numeri piu piccoli di Em
b) Dire "definitivamente inferiore" è diverso dal dire "è piu piccolo di", anche se erroneamente vengono usati come sinonimi per comodita.
Qui vi potrete schiarire i vostri dubbi:
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic3/
http://www.nist.gov/dads/HTML/bigOnotation.html
c) Intuitivamente quello che dici tu sembra essere giusto. Ma tu stai chiedendo qualcosa di più: la backwar stability. Una condizione molto forte che non sempre può essere soddisfatta.
Eccoti qualcosa per saziare la tua sete di sapere:
[edit: di questo non sono riuscito a trovare una fonte decente online mi spiace]
http://www.google.it/url?sa=t&source=web&ct=res&cd=1&url=http%3A%2F%2Fwww-math.mit.edu%2F~persson%2F18.335%2Flec10handout2pp.pdf&ei=AYT7SLCWJJLO0gWXpKSNDw&usg=AFQjCNFFySVIsTCLC2UWV1bU2o6hUdeWqw&sig2=wLD5c5L7bbdrV5HWnqfgyg
OK, me li smazzo appena ho un po' di tempo.
OK, me li smazzo appena ho un po' di tempo.
Si si, volevo solo sottilnearti che hai ragione a fare quelle obiezioni, ma nascono da mie imprecisioni nel linguaggio, dovute alla pigrizia, più che a veri errori formali, dovuti alla (mia) ignoranza.
variabilepippo
19-10-2008, 20:15
Come qualsiasi operazione sui floating point, è impensabile essere lossyless. Altrimenti sarebbe semplicemente un algoritmo di scambio sui bit, e non sui FP.
Dunque il tuo algoritmo è lossy o lossless? :rolleyes:
Dunque il tuo algoritmo è lossy o loseless? :rolleyes:
Lossy.
Non esistono algoritmi FP lossless.
variabilepippo
19-10-2008, 20:27
Lossy.
Originariamente inviato da cdimauro:
Appunto. Il tuo è un algoritmo lossy, com'era intuibile.
La tua risposta è stata:
come ti ho detto, non viene perso nessun bit significativo.
Applicando un numero N di volte il tuo algoritmo all'output dell'iterazione precedente si ottiene comunque una compressione?
Originariamente inviato da cdimauro:
Appunto. Il tuo è un algoritmo lossy, com'era intuibile.
La tua risposta è stata:
come ti ho detto, non viene perso nessun bit significativo.
Applicando un numero N di volte il tuo algoritmo all'output dell'iterazione precedente si ottiene comunque una compressione?
da compressione a decompressione non si perde nessuna cifra significativa (ho presupposto che non si perda neanche nessun bit significativo, ma in realtà intendevo cifra), però nella pagina precedente ho già provato a spiegare a tutti gli altri perchè non si può applicare 2 volte.
variabilepippo
19-10-2008, 20:50
da compressione a decompressione non si perde nessuna cifra significativa (ho presupposto che non si perda neanche nessun bit significativo, ma in realtà intendevo cifra), però nella pagina precedente ho già provato a spiegare a tutti gli altri perchè non si può applicare 2 volte.
Se da compressione a decompressione non si perde alcuna informazione allora l'algoritmo è, per definizione, lossless e se l'algoritmo è lossless puoi applicarlo quante volte vuoi (senza avere però la pretesa di comprimere all'infinito, ovviamente).
Se cade una delle 2 ipotesi:
1) La compressione/decompressione comporta perdite di informazione
2) Non è possibile applicare più volte lo stesso algoritmo
allora l'algoritmo PERDE informazione per strada, c'è poco da fare...
Non sono un grande fan di Wikipedia, ma per concetti di base va più che bene:
Lossy compression formats suffer from generation loss: repeatedly compressing and decompressing the file will cause it to progressively lose quality. This is in contrast with lossless data compression.
cdimauro
19-10-2008, 20:51
Esattamente. E arriviamo ai paradossi di cui abbiamo parlato in precedenza.
Non si scappa.
Se da compressione a decompressione non si perde alcuna informazione allora l'algoritmo è, per definizione, lossless e se l'algoritmo è lossless puoi applicarlo quante volte vuoi (senza avere però la pretesa di comprimere all'infinito, ovviamente).
Dire
||dX||/||X!!=O(Em)
che vuol dire anche senza perdita di cifre significative seguendo l'IEEE standard, non vuol dire esatto!!!
Fidati di me, Ci vorrebbero lezioni e lezioni di algebra lineare numerica per dimostrare questo concetto rigorosamente!
Esattamente. E arriviamo ai paradossi di cui abbiamo parlato in precedenza.
Non si scappa.
tu chiedi la backward stability, io ti offro al massimo la forward stability. Che è già un ottimo risultato di per se.
cdimauro
19-10-2008, 20:58
Rispondi a questa domanda allora: se decomprimo i dati compressi una volta col tuo algoritmo, ottengo (SEMPRE) ESATTAMENTE gli stessi dati di origine?
Rispondi a questa domanda allora: se decomprimo i dati compressi una volta col tuo algoritmo, ottengo (SEMPRE) ESATTAMENTE gli stessi dati di origine?
ottieni dei dati tali per cui
||dX||/||X||=O(Emacchina)
che è il miglior risultato che una FPU può ottenere.
variabilepippo
19-10-2008, 21:02
Dire
||dX||/||X!!=O(Em)
che vuol dire anche senza perdita di cifre significative seguendo l'IEEE standard, non vuol dire esatto!!!
Fidati di me, Ci vorrebbero lezioni e lezioni di algebra lineare numerica per dimostrare questo concetto rigorosamente!
L'algebra mi ha sempre affascinato, ma in questo caso sono interessato a sapere se il tuo algoritmo perda o non perda informazioni per strada. Ci sono ottimi algoritmi lossless che ottengono compressioni medie dell'80%, se stai sviluppando un algoritmo lossy che richiede una potenza di calcolo esagerata per fornire un livello di compressione del 33% (se non ricordo male) allora forse stai seguendo una strada sbagliata...
Comprimere matrici 3*3 in vettori di lunghezza 6 vuol dire un rapporto di 3/2, cioè 30 mb diventano venti.
Vi sembra comunque un buon risultato? vale la pena di lavorarci su?
ottieni dei dati tali per cui
||dX||/||X||=O(Emacchina)
che è il miglior risultato che una FPU può ottenere.
Quindi la risposta alla domanda di cdimauro è no? In altri termini: se comprimo un file, il checksum (es. calcolato con l'algoritmo SHA-1) del file decompresso coinciderà con quello del file di partenza?
L'algebra mi ha sempre affascinato, ma in questo caso sono interessato a sapere se il tuo algoritmo perda o non perda informazioni per strada. Ci sono ottimi algoritmi lossless che ottengono compressioni medie dell'80%, se stai sviluppando un algoritmo lossy che richiede una potenza di calcolo esagerata per fornire un livello di compressione del 33% (se non ricordo male) allora forse stai seguendo una strada sbagliata...
Ma qua nessuno ha detto che voglio inventare l'algoritmo del nuovo millennio... voglio solo presentare un algoritmo di compressione facilmente parallelizzabile, dato che fin'ora ne ho visti ben pochi (nessuno?)
Quindi la risposta alla domanda di cdimauro è no? In altri termini: se comprimo un file, il checksum (es. calcolato con l'algoritmo SHA-1) del file decompresso coinciderà con quello del file di partenza?
Non so se SHA-1 darebbe lo stesso risultato... dando una veloce lettura del suo contenuto potrebbe non darlo... ma provando con GIMP a comprimere e decomprimere la stessa immagine usando il jpeg mi fa vedere che lo SHA-1 non viene rispettato.
ma non ti fidare! Se SHA-1 usa le tabelle di hash come immagino allora avrà di sicuro collisioni, cioè file diversi potranno avere lo stesso SHA-1
variabilepippo
19-10-2008, 21:32
Ma qua nessuno ha detto che voglio inventare l'algoritmo del nuovo millennio... voglio solo presentare un algoritmo di compressione facilmente parallelizzabile, dato che fin'ora ne ho visti ben pochi (nessuno?)
Hai creato il thread affermando:
"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."
Un algoritmo del genere sarebbe non quello del millennio, ma quello che stravolgerebbe l'informatica, la teoria dell'informazione, l'elettronica di consumo e non solo!
ma provando con GIMP a comprimere e decomprimere la stessa immagine usando il jpeg mi fa vedere che lo SHA-1 non viene rispettato.
Mi sembra ovvio, jpeg è un algoritmo lossy.
ma non ti fidare! Se SHA-1 usa le tabelle di hash come immagino allora avrà di sicuro collisioni, cioè file diversi potranno avere lo stesso SHA-1
E quindi? Qui si sta parlando di altro, ovvero di usare un algoritmo di hashing per verificare se l'operazione di decompressione introduca o meno degli errori. E considerando che si stima una collisione ogni 590295810358705651712 operazioni (confrontalo con la probabilità di vincere al SuperEnalotto) SHA-1, mi sembra improbabile che te ne capitino 2 di seguito su altrettanti controlli... :D
Secondo me hai le idee molto confuse su diversi concetti informatici.
cdimauro
19-10-2008, 21:40
ottieni dei dati tali per cui
||dX||/||X||=O(Emacchina)
che è il miglior risultato che una FPU può ottenere.
Non mi hai risposto. A me bastava un sì o un no.
Per il resto mi allineo a quanto detto da variabilepippo.
Hai creato il thread affermando:
"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."
Un algoritmo del genere sarebbe non quello del millennio, ma quello che stravolgerebbe l'informatica, la teoria dell'informazione, l'elettronica di consumo e non solo!
Al momento lo applicavo a matrici 2*2 sperando di poterlo allargare. Il problema è che mi sono accorto che già alla dimensione 4 il quarto valore singolare andava a zero. Il fatto è che io so che in realtà non è 0, ma se viene salvato come zero vuol dire che ha 0 cifre decimali esatte. E di conseguenza la decompressione potrà garantire 0 cifre decimali esatte. Un pessimo risultato non trovi?
Non mi hai risposto. A me bastava un sì o un no.
Per il resto mi allineo a quanto detto da variabilepippo.
Si che ti ho risposto: ottengo dei risultati sbagliati, ma il cui sbaglio è piccolo, ed è quantificato con l'espressione di cui sopra.
cdimauro
19-10-2008, 22:21
Quindi è lossy, al contrario di quello che affermavi all'inizio della discussione.
E' già un bel passo avanti.
Quindi è lossy, al contrario di quello che affermavi all'inizio della discussione.
E' già un bel passo avanti.
Scusami ma dove ho affermato che è lossless? Ti ricordo comunque che il mio algoritmo ottiene il miglior risultato che una FPU possa mai raggiungere: non perdere cifre significative.
variabilepippo
19-10-2008, 22:29
Ed aggiungo che secondo me implementare un algoritmo lossy che "perde poco" non è una cosa propriamente geniale: si rinuncia ai vantaggi degli algoritmi con perdite, senza ottenere quelli degli algoritmi lossless. :rolleyes: Se proprio deve perdere è meglio che perda la massima quantità di informazione "inutile"...
Ti ricordo comunque che il mio algoritmo ottiene il miglior risultato che una FPU possa mai raggiungere: non perdere cifre significative.
Secondo me è concettualmente sbagliato concentrarsi tanto su dettagli implementativi in questa fase, per il momento dovresti affinare l'algoritmo, all'implementazione ci si pensa in un secondo momento.
cdimauro
19-10-2008, 22:37
Scusami ma dove ho affermato che è lossless?
http://www.hwupgrade.it/forum/showpost.php?p=24542286&postcount=5
http://www.hwupgrade.it/forum/showpost.php?p=24542571&postcount=7
Ti ricordo comunque che il mio algoritmo ottiene il miglior risultato che una FPU possa mai raggiungere: non perdere cifre significative.
Significative per cosa?
Significative per cosa?
http://en.wikipedia.org/wiki/Significant_figures :)
variabilepippo
19-10-2008, 22:44
http://en.wikipedia.org/wiki/Significant_figures
La domanda non era "cosa sono le cifre significative", ma per cosa sono significative nel tuo algoritmo... :)
Abbiamo assodato che si tratta di un algoritmo lossy o sbaglio?
In tal caso vale quanto scritto prima:
"Ed aggiungo che secondo me implementare un algoritmo lossy che "perde poco" non è una cosa propriamente geniale: si rinuncia ai vantaggi degli algoritmi con perdite, senza ottenere quelli degli algoritmi lossless. Se proprio deve perdere è meglio che perda la massima quantità di informazione "inutile"..."
La domanda non era "cosa sono le cifre significative", ma per cosa sono significative nel tuo algoritmo... :)
Tutto si basa sul fatto che l'nesimo valore SVD sia abbastanza grande, cioè che la matrice di partenza abbia un growth factor (max(SVD)/min(SVD)) abbastanza piccolo
Abbiamo assodato che si tratta di un algoritmo lossy o sbaglio?
In tal caso vale quanto scritto prima:
"Ed aggiungo che secondo me implementare un algoritmo lossy che "perde poco" non è una cosa propriamente geniale: si rinuncia ai vantaggi degli algoritmi con perdite, senza ottenere quelli degli algoritmi lossless. Se proprio deve perdere è meglio che perda la massima quantità di informazione "inutile"..."
Si è lossy, comunque vorrei farti notare che il mio è un progetto puramente didattico di uno studente. Magari non uscirà l'algoritmo del domani, ma di sicuro avrò imparato una cifra di cose, che è sempre utile.
Basta guardare quanto ho imparato in questo forum!
Ecco, ho provato a cercare se c'era una qualche implementazione della SVD in C#, e ne avevo trovata una. Pensavo...
Mi ero detto, scrivendo in C# dovrebbe essere abbastanza pulita.
E invece no. Mannaggia ai tuoi colleghi matematici
public static bool rmatrixbdsvd(ref double[] d,
double[] e,
int n,
bool isupper,
bool isfractionalaccuracyrequired,
ref double[,] u,
int nru,
ref double[,] c,
int ncc,
ref double[,] vt,
int ncvt)
{
bool result = new bool();
double[] d1 = new double[0];
double[] e1 = new double[0];
int i_ = 0;
int i1_ = 0;
...
...
Ma si puo' fare una funzione con 11 parametri, dei quali 4 per riferimento (che poi forse non sanno bene cosa vuol dire in quel caso), i cui nomi sono senza senso ed iniziando la funzione con una sfilza di dichiarazioni di variabili di nuovo con nomi senza senso?
E poi una variabile che si chiama i_
ma neppure in sql avevo mai visto campi che finivano con _
Vabbe'.
ahaha gugo mi hai fatto ridere... adesso capisci perchè io programmo in matalb? ehehhehe
Comunque sono andato a dare un occhio alle reference. Tu hai scelto un algoritmo particolare che lavora su matrici rettangolari e che usano un particolare metodo di precondizionamento per velocizzare l'algoritmo. Una scelta un po complicata, se vuoi piu info l'ideatore è questo:
http://www.stanford.edu/class/cme324/chan.pdf
(Chan è uno di quei grandi matematici che riescono a prendere anni di teoria e a dargli un bel significato pratico)
Comunque noi lavoriamo su matrici quadrate, quindi ti basta questo:
http://www.alglib.net/matrixops/general/svd.php
Ecco. Alla fine ho trovato una libreria fatta bene.
Ecco quanto avuto
| 6.000 9.000 1.000 3.000 |
| 8.000 4.000 5.000 3.000 |
| 7.000 5.000 8.000 9.000 |
| 2.000 10.000 7.000 6.000 |
-- U --
| -0.420 -0.578 -0.572 -0.403 |
| -0.415 0.350 -0.516 0.663 |
| -0.598 0.578 0.214 -0.512 |
| -0.543 -0.457 0.600 0.369 |
-- V --
| -0.468 0.363 -0.805 0.017 |
| -0.584 -0.808 -0.023 0.072 |
| -0.467 0.383 0.458 0.652 |
| -0.470 0.262 0.376 -0.755 |
-- VH --
| -0.468 -0.584 -0.467 -0.470 |
| 0.363 -0.808 0.383 0.262 |
| -0.805 -0.023 0.458 0.376 |
| 0.017 0.072 0.652 -0.755 |
-- S --
| 23.705 0.000 0.000 0.000 |
| 0.000 6.786 0.000 0.000 |
| 0.000 0.000 6.035 0.000 |
| 0.000 0.000 0.000 2.142 |
-- sv --
| 23.705 6.786 6.035 2.142 |
-- Succ:True --
-- Prova --
| 6.000 9.000 1.000 3.000 |
| 8.000 4.000 5.000 3.000 |
| 7.000 5.000 8.000 9.000 |
| 2.000 10.000 7.000 6.000 |
Partito da una matrice casuale, ho ricavato
U, V, la S diagonale
E poi ho fatto la prova moltiplicando U*S*VH e viene.
Ora, come penseresti di compattare p.es. la U (e poi la V) in un solo vettore?
Sono sufficienti degli angoli penso, ma non mi viene in mente come.
Partito da una matrice casuale, ho ricavato
U, V, la S diagonale
E poi ho fatto la prova moltiplicando U*S*VH e viene.
Ora, come penseresti di compattare p.es. la U (e poi la V) in un solo vettore?
Sono sufficienti degli angoli penso, ma non mi viene in mente come.
Tutto giace nel fatto che U e V sono ortonormali. Devi solo trovare gli assi giusti in base al quale da U1 puoi rimappare l'intera matrice.
Siccome l'algoritmo dell'SVD da un certo ordine alle cose, ti basta muoverti di 90° in senso antiorario verso l'asse piu vicino per calcolare il successivo vettore.
Come farlo però è tutto un altro paio di maniche.
A me è venuto in mente un modo piu semplice però: possiamo trovare un modo di mappare la sfera (o ipersfera) sulla retta. Ovviamente non sarà una mappatura precisa, ma scegliendo in modo intelligente l'algoritmo si potrebbero ottenere ottimi risultati. Io ci sto lavorando, e per ora sembra la via piu promettente (ci sto lavorando proprio ora)
Una matrice 4*4 diventerebbe lunga 12, e probabilmente l'algoritmo si potrebbe applicare 3 volte. Sempre che si scelga la piu intelligente delle mappe possibili-
Cioe' vorresti mappare la ipersuperficie sferica della ipersfera di raggio 1 in una funzione parametrica ad un parametro solo?
In pratica associare ogni punto della retta con quello della superficie ipersferica?
Ma scusa, ma l'altro modo (se funziona) non e' piu' facile?
Fai il prodotto scalare con tutti i versori notevoli, e trovi tutti i coseni dell'angolo.
L'angolo piu' piccolo lo trovi quindi in fretta.
E per ruotare di 90 gradi in quella direzione sai che il tuo vettore corrente e il versore trovato identificano un piano, la cui normale e' il vettore di definizione del piano stesso.
fai quindi il prodotto vettoriale tra il tuo vettore originale e la normale e dovresti aver ruotato di 90 gradi...
Ciao,
scusami adesso sono stanco e domattina mi devo svegliare alle 7,30 quindi non ho molto tempo per risponderti, però fidati che con questo nuovo metodo è molto meglio. Domani ti spiego perchè.
Vorrei ragazzi che mi risolveste un dubbio: Se io prendessi un float a 32 bit, e usasso i 32 bit per mappare un insieme di 2^32 elementi, e poi riutilizzassi quel nuovo float per dei calcoli, potrei incorrere in qualche problema?
C'è qualche parte del float che non si può scrivere per bit? Secondo me si può anche disegnare una funzione float che mappa la retta sulla discretizzazione dell'ipersfersa... però è sbatti da pensare...
Soprattutto: quali parti del float è meglio tenere a 0 per evitare di trovarmi numeri ENORMI?
Domani ho 3 ore di tempo macchina per giocare col cluster dell'uni... ci sarà da divertirsi :D:D:D:D:D
Ciao,
scusami adesso sono stanco e domattina mi devo svegliare alle 7,30 quindi non ho molto tempo per risponderti, però fidati che con questo nuovo metodo è molto meglio. Domani ti spiego perchè.
Vorrei ragazzi che mi risolveste un dubbio: Se io prendessi un float a 32 bit, e usasso i 32 bit per mappare un insieme di 2^32 elementi, e poi riutilizzassi quel nuovo float per dei calcoli, potrei incorrere in qualche problema?
C'è qualche parte del float che non si può scrivere per bit? Secondo me si può anche disegnare una funzione float che mappa la retta sulla discretizzazione dell'ipersfersa... però è sbatti da pensare...
Soprattutto: quali parti del float è meglio tenere a 0 per evitare di trovarmi numeri ENORMI?
Domani ho 3 ore di tempo macchina per giocare col cluster dell'uni... ci sarà da divertirsi :D:D:D:D:D
Ovviamente in 2^32 diversi valori mappano i numeri reali tra -10E+38 e +10E+38, ovviamente discretizzati.
Sono piu' concentrati tra -1 e 1 (meta' dei 2^32 sono proprio li' in mezzo), e via via si diradano di piu'.
Vedila come una funzione logaritmica, con densita' molto alta vicino allo 0 e via via piu' rada man mano che ci si avvicina a 10E+38
Tirando i bit a caso ovviamente otterresti un numero valido compreso in quell'intervallo, e seguiresti la stessa distribuzione di cui sopra. Tranne alcuni casi particolare che dovrai evitare, descritti dopo.
Per vedere il significato dei singoli bit nei float 32 bit ti rimando a
http://it.wikipedia.org/wiki/IEEE_754
E quindi per evitare di avere valori molto alti dovrai concentrarti sull'esponente. L'esponente ha un BIAS di 127, ovvero per ottenere il vero esponente occorre prendere i bit tra 30 e 23 e considerarli come un numero 8 bit con valori possibili quindi tra 0 e 255
i valori 0 e 255 sono riservati, e quindi non dovrai usarli mai (mappano eccezioni, -inf, +inf e simili)
si sottrae 127 a tale valore e si ottiene l'esponente.
Il numero float rappresentato e' quindi
segno (primo bit) * mantissa (bit tra 22 e 0) * 2^Esponente
Ma guarda che l'ho capito. Il punto rimane lo stesso: il tuo algoritmo NON può operare con QUALUNQUE dato, altrimenti si applicherebbe quanto ho già detto.
Non se ne esce fuori, logica alla mano. C'è poco da fare.
Ma allora anche il JPEG non è applicabile su qualsiasi dato ;) Se lo riapplichi su un JPEG già compresso perdi troppa informazione.
DanieleC88
20-10-2008, 09:50
Ma allora anche il JPEG non è applicabile su qualsiasi dato ;) Se lo riapplichi su un JPEG già compresso perdi troppa informazione.
Be':
Lossy compression throws away some data which cannot be restored. Ideally, when its use is appropriate, lossy compression would only be done once, at a carefully planned spot (namely, at the end of the workflow involving the file, ideally after all required changes have been made). Repeated applications of lossy compression and decompression causes generation loss. Some lossy compression algorithms are much worse than others in this regard. Generation loss caused by lossy compression can be made worse if the parameters used are not consistent across generations. For example, with JPEG, changing the quality setting will cause different quantization constants to be used, causing a lot of extra loss.
Be':
Era un esempio per affermare che è una situazione normale. L'algoritmo del JPEG può comunque essere applicato su qualunque foto, a definire se la quantità di informazioni persa è accettabile è la natura e l'uso della foto stessa.
Stessa cosa per l'algoritmo in questione, può essere applicato su qualunque dato, è la natura dei dati a stabilire se la quantità di informazione persa è accettabile o meno. Ma in qualsiasi caso, non solo nella riapplicazione consecutiva dell'algoritmo stesso ;)
DanieleC88
20-10-2008, 12:43
Era un esempio per affermare che è una situazione normale. L'algoritmo del JPEG può comunque essere applicato su qualunque foto, a definire se la quantità di informazioni persa è accettabile è la natura e l'uso della foto stessa.
Ah ok, scusa, avevo interpretato male il messaggio di prima. ;)
Be':
Quel pezzo di wikipedia cerca di farti capire grosso modo il concetto di backward stabile...
Una domanda ragazzi, lo so che vi sembrerà banale: ma un floating point può rappresentare "solo" 2^32 entità diverse? A guardare i FP avrei giurato di più...
Comunque oggi ho giocato una cifra con matlab e il supercalcolatore. Ho davvero imparato molte molte cose in questi giorni, sono davvero contento.
Ho anche analizzato meglio il mio algoritmo, e mi sono accordo che forse l'SVD non è prettamente necessario: a noi serve solo una base ortonormale, e potrei usare un mio algoritmo... Però ho davvero dormito poco quindi adesso mangio e poi vado a nanna... domani vi posto le mie scoperte con relativi grafici...
Una domanda ragazzi, lo so che vi sembrerà banale: ma un floating point può rappresentare "solo" 2^32 entità diverse? A guardare i FP avrei giurato di più...
Sui FP a 32 bit come puoi rappresentare più di 2^32 entità diverse ? E' un po' un controsenso non trovi ?
La codifica IEEE754 ci dice il formato di rappresentazione dei numeri fp a 32 bit. E' quindi normale che esistano al massimo 2^32 rappresentazioni distinte di numeri, proprio perché stanno in un numero binario a 32 bit.
DanieleC88
20-10-2008, 17:24
Una domanda ragazzi, lo so che vi sembrerà banale: ma un floating point può rappresentare "solo" 2^32 entità diverse? A guardare i FP avrei giurato di più...
Un qualsiasi codice con un alfabeto di 2 simboli e parole di lunghezza n può generare soltanto 2^n parole diverse tra di loro (in modo che non ci siano ambiguità). A questo punto direi che dipende dal grado di precisione che vuoi usare per i numeri a virgola mobile (single, double, magari extended). :)
Sui FP a 32 bit come puoi rappresentare più di 2^32 entità diverse ? E' un po' un controsenso non trovi ?
La codifica IEEE754 ci dice il formato di rappresentazione dei numeri fp a 32 bit. E' quindi normale che esistano al massimo 2^32 rappresentazioni distinte di numeri, proprio perché stanno in un numero binario a 32 bit.
Mi sono spiegato male: Il solo era ironico, in realtà vi chiedevo se non ci fosse qualche bit usato non per rappresentare numeri, come ad esempio le flag NaN, 0, inf, ....
ragazzi siete tutti molto gentili, vi prometto che vi citerò tutti nel paper ehehehhe... anche se nessuno lo leggerà :(:( :P
NaN, 0, inf sono rappresentati con particolari combinazioni di mantissa ed esponente.
Mi sono spiegato male: Il solo era ironico, in realtà vi chiedevo se non ci fosse qualche bit usato non per rappresentare numeri, come ad esempio le flag NaN, 0, inf, ....
Certo, come ti avevo messo su.
Tutti quelli il cui esponente e' 00000000 o 11111111
Ci sono anche i float 64 bit se serve calcolare con piu' precisione.
Certo, come ti avevo messo su.
Tutti quelli il cui esponente e' 00000000 o 11111111
Ci sono anche i float 64 bit se serve calcolare con piu' precisione.
eheheh scusami ma non avevo visto. Quindi effettivamente si possono rappresentare meno di 2^32 numeri....
I double sono piu precisi è vero, ma usano piu memoria e non vanno bene per l'architettura CUDA...
A meno che qualcuno non mi regali una scheda tesla :P
A meno che qualcuno non mi regali una scheda tesla :P
Per dimostrare che l'algoritmo funziona non hai necessità di una scheda tesla. La precisione a 64 bit ce l'hanno tutte le CPU da 486 in poi.
Per dimostrare che l'algoritmo funziona non hai necessità di una scheda tesla. La precisione a 64 bit ce l'hanno tutte le CPU da 486 in poi.
si si sto scherzando ovvio!
Comunque se facessi un algoritmo a 32 bit invece di 64 fallirei il mio compito siccome ho promesso al mio prof di fare qualcosa su CUDA
Per dimostrare che l'algoritmo funziona non hai necessità di una scheda tesla. La precisione a 64 bit ce l'hanno tutte le CPU da 486 in poi.
Nono Cionci. Mi cadi sulla Storia dell'Informatica (che presto proporranno nei corsi di Laurea)
il vecchio 8087, primo coprocessore matematico della serie 8086, aveva praticamente gia' tutto quello che usiamo oggi, compresi gli estesi 80bit.
Vabbe'.
Considerazione inutile (ed e' pure una FPU, non CPU, quindi potresti avere anche ragione)
si si sto scherzando ovvio!
Comunque se facessi un algoritmo a 32 bit invece di 64 fallirei il mio compito siccome ho promesso al mio prof di fare qualcosa su CUDA
Ah, comunque la libreria che ho trovato ieri fa la SVN su matrici 20x20 in pochi decimi di secondo...
di piu' non sono andato.
Considerazione inutile (ed e' pure una FPU, non CPU, quindi potresti avere anche ragione)
Infatti non consideravo le FPU esterne ;)
Ah, comunque la libreria che ho trovato ieri fa la SVN su matrici 20x20 in pochi decimi di secondo...
di piu' non sono andato.
beh calcola quanto è grande una immagine (o flusso video) normalmente e capirai che anche se ci mette 10 ms è inaccettabile.
Io voglio compressiore real time on the fly da 1 gb a 1 mb senza sforzo. ehhehehheeh scherzo
(o flusso video)
La compressione di un flusso video è assolutamente cosa diversa dalla compressione di dati raw ;)
Nel caso di flussi video, la compressione frame per frame presi singolarmente è inaccettabile. Poi in generale, discorso a parte video/audio realtime, la compressione di video/audio o foto è il passo su cui si può anche perdere qualche ms in più, l'importante è che sia veloce la decompressione.
La compressione di un flusso video è assolutamente cosa diversa dalla compressione di dati raw ;)
Nel caso di flussi video, la compressione frame per frame presi singolarmente è inaccettabile. Poi in generale, discorso a parte video/audio realtime, la compressione di video/audio o foto è il passo su cui si può anche perdere qualche ms in più, l'importante è che sia veloce la decompressione.
Perchè frame per frame è inaccettabile? userei un paradigma simile a quello dei videogiochi, usando una scheda video.
Comunque considera che sono un 20enne universitario, quindi muoversi fuori dalle righe per me è uno stile di vita, basta guardare i miei scritti di analisi! ehehheeh
Una cosa: sono molto vicino ad una relase del codice usando matlab. Vorrei pubblicare il mio algoritmo sotto licenza GPL, posso farlo anche se uso delle funzioni di matlab?
Chiunque voglia essere inserito nel body del copyright mi mandi pure un PM :D
Perchè frame per frame è inaccettabile? userei un paradigma simile a quello dei videogiochi, usando una scheda video.
Il problema è quanto riesci a comprimere un singolo frame e come riesci ad effettuare la decompressione.
Gli algoritmi attuali riescono a comprimere molto i dati in quanto "accorpano" i dati in comune tra più frame, cosa che tu non saresti in grado di fare lavorando sul singolo frame. Inoltre ho i dubbi sull'efficienza di una decompressione frame per frame piuttosto che "incrementale".
Il problema è quanto riesci a comprimere un singolo frame e come riesci ad effettuare la decompressione.
Gli algoritmi attuali riescono a comprimere molto i dati in quanto "accorpano" i dati in comune tra più frame, cosa che tu non saresti in grado di fare lavorando sul singolo frame. Inoltre ho i dubbi sull'efficienza di una decompressione frame per frame piuttosto che "incrementale".
E' questa l'idea di base del mio algoritmo: dimenticarsi completamente dell'incremento per rendere il software completamente parallelo e scalabile.
Ma non ti sembra di correre un po' troppo?
Non hai ancora trovato il modo di comprimere una matrice ortonormale NXN in un solo vettore N... senza di quello non comprimi nulla no?
E' questa l'idea di base del mio algoritmo: dimenticarsi completamente dell'incremento per rendere il software completamente parallelo e scalabile.
Ok. Non sono però molto convinto che possa essere davvero efficiente. L'incrementalità serve per aumentare la parte in comune tra i vari frames. Certamente perdi molto in termini di parallelizzabilità, però guadagni moltissimo in termine di dimensioni finali e di velocità di decompressione. Insomma non mi pare che il gioco valga la candela.
Comunque tienici aggiornati sugli sviluppi.
Ma non ti sembra di correre un po' troppo?
Non hai ancora trovato il modo di comprimere una matrice ortonormale NXN in un solo vettore N... senza di quello non comprimi nulla no?
Ho radicalmente modificato l'algoritmo, abbandonando l'SVD e usando solo il concetto di vettori ortonormali. Comprime per ora 9 float (3*3) in un 6 float (2*n) con un pò di errore. Ma ho anche dimostrato che la migliore applicazione possibile dovrebbe essere O(Em).
Mi servono ancora un paio di giorni per studiarmi la distribuzione di probabilità degli angoli dei coseni direttori dei vettori, per fare in modo che usi piu precisione laddove la distribuzione sia piu densa (sto cioè cercando di migliorare il caso medio a scapito dei casi piu rari, come avviene nella realtà con gli FP).
Ci puoi fare vedere un paio di esempi numerici, sempre partendo dalla solita matrice 4x4?
Ok. Non sono però molto convinto che possa essere davvero efficiente. L'incrementalità serve per aumentare la parte in comune tra i vari frames. Certamente perdi molto in termini di parallelizzabilità, però guadagni moltissimo in termine di dimensioni finali e di velocità di decompressione. Insomma non mi pare che il gioco valga la candela.
Comunque tienici aggiornati sugli sviluppi.
Ciao,
come detto prima sono un universitario e per di più matematico, quindi mi interessa poco la reale applicabilità e molto l'interesse didattico :D:D:D
magari il mio non sarà un buon algoritmo, ma qualche altro studente zappaterra dopo di me potrebbe leggerlo per farsi venire in mente qualche buona idea :D
Se riuscirò a scrivere un paper decente al quale altri utenti/studenti potranno ispirarsi, anche solo per capire come NON si deve programmare, sarà un ottimo risultato :D
Ci puoi fare vedere un paio di esempi numerici, sempre partendo dalla solita matrice 4x4?
purtroppo no :( il codice ha ancora troppo errore perchè è una primissima revisione, TI PROMETTO che sarai il primo a venire informato. Ti spiego brevemente la mia nuova idea:
A) prendo una matrice 3*3
B) Normalizzo lungo le righe (o lungo le colonne) e mi salvo il vettore 3*1 con le norme.
C) A questo punto mi trovo in una situazione simile al caso di prima, ma computazionalmente meno intensa da raggiungere e INFINITAMENTE più stabile (è pure backward stabile!). Ho una matrice U quasi-ortonormale moltiplicata per una matrice che assomiglia alla S di prima.
D) La matrice U contiene tre versori centrati in 0. A questo punto attraverso una tecnica geometrica un pò complicata (perdonami se non la scrivo in questo sparuto editor) mappo la superficie della sfera sulla retta, ridistribuendo le densità di distribuzione degli angoli seguendo la densità di probabilità osservata sperimentalmente. Su questa parte si basa il mio algoritmo, ed in effetti ci sono AMPI margini di miglioramento.
Avendo mappato ogni singolo versore sulla retta, mi prendo il floating point che rappresenta il punto della retta e me lo salvo. 3 versori 3 norme = 6 = 2*n
La tecnica è allargabile alle dimensioni superiori, ma come detto meglio partire dai casi semplici prima!
Una compressione del 33% quindi, non è moltissimo. In ogni caso niente vieta di applicare una compressione lossless dopo il tuo algoritmo, quindi la cosa potrebbe diventare interessante, soprattutto se la distribuzione dei simboli fosse particolarmente "clemente". Ad esempio Huffman, LZ77 o LZ78.
Riguardo ai video: come già detto si cerca appunto di lavorare su più frame contemporaneamente cercando di evitare di replicare nei dati compressi zone del video che variano poco. Riguardo al fatto che una compressione frame per frame sia inaccettabile basta guardare il Motion JPEG, che ha un fattore qualità/spazio occupato molto più basso degli altri formati lossy dedicati ai video.
Trovare un algoritmo per la compressione di dati "casuali" è un bel modo per diventare straricco in questo settore.
khelidan1980
24-10-2008, 21:00
news sull'algoritmo?? :)
news sull'algoritmo?? :)
Sono scomparso?
No che non sono scomparso.... Purtroppo però l'hard disk con i dati sopra ha fallito (era un raptor da 32 gb... vecchissimo quindi) e con lui sono andati via tutti i dati. Mi è stato dato un altro raptor usato da 32 gb.... però ci hanno messo un pò.
Al momento sono impegnato a dare alcuni esami (ho gli orali l'11 e il 17) ma dopo vi prometto che mi dedicherò a voi. D'altronde una descrizione intuitiva dell'algoritmo l'ho messa, nel caso in cui qualcuno abbia qualche dubbio mi contatti pure.
A quest'ora non sono riuscito a leggere tutto che son tante pagine, quindi se già l'avete detto considerate che non abbia detto nulla, e tra l'altro la compressione non è il mio campo, non ne so quasi nulla però mi domandavo se avesse senso fare un algoritmo lossy che non perde niente. Non si usano i lossy in modo da poter sacrificare l'informazione?
A quest'ora non sono riuscito a leggere tutto che son tante pagine, quindi se già l'avete detto considerate che non abbia detto nulla, e tra l'altro la compressione non è il mio campo, non ne so quasi nulla però mi domandavo se avesse senso fare un algoritmo lossy che non perde niente. Non si usano i lossy in modo da poter sacrificare l'informazione?
Ma informazione la sacrifichi. Tutto sta nel sacrificare quella giusta, cioè quella ridondante ;)
Ma informazione la sacrifichi. Tutto sta nel sacrificare quella giusta, cioè quella ridondante ;)
Sì, in generale sì, mi chiedevo in questo caso perché lui parla di errore quasi nullo.
Sì, in generale sì, mi chiedevo in questo caso perché lui parla di errore quasi nullo.
Sì, però che diverge riapplicando l'algoritmo ;) Quindi non è nullo. Ed il limite è proprio quello. Se alla fine dei calcoli di decompressione ottengo valori come 248.56 ed avevo compresso 249, sei d'accordo che ho avuto una perdita di informazione ? Arrotondo ed ho ottenuto il valore iniziale ;) L'inghippo è appunto spalmare più informazione su un float a 32 bit cercando di riottenere un intero con un'incertezza < 0.50 (ovviamente il discorso deve valere per tutti gli interi che ci ho "spalmato").
capito :sisi:
cmq interessante discussione, messa fra i preferiti. :sisi:
Io sto continuando a lavorarci, adesso gradirei però una mano da voi:
Il mio problema si è ridotto a mappare una sfera sulla retta. Vi spiego: ogni punto della superficie della sfera, può essere individuato usando 2 coseni direttori, e cioè gli angoli che forma con l'asse delle x e delle y. Si può anche pensare come se spalmassimo la sfera sul piano, usando solo due coordinate per individuare ogni punto della sfera, oppure ancora se pensassimo le coordinate come (x, y, norm(x, y) ). Spalmare la sfera sul piano però porta deformazioni, sfruttando anche il fatto che i FP sono discreti, allora io ho pensato di mappare 2^32 punti sulla sfera usando un floating point.
Per ora lo faccio nel modo piu stupido possibile, cioè ho preso una matrice con 2^16 * 2^16 entrate, e in ogni entrata ho messo un angolo. Uso poi i bit del floating point come coordinate per individuare i due angoli e quindi ricostruire il punto sulla sfera.
In questo modo però ho due problemi:
A) uso anche i bit dell'esponente, e quindi a volte i bit riconvertiti in floating point mi danno un reale ENORME che rende difficile applicare di nuovo l'algoritmo
B) Quanto è preciso?
io ho notato che gli angoli formati dai vettori non si dispongono in modo casuale, bensi esistono alcuni angoli piu probabili di altri. Io ho pensato che prima di convertire un set di matrici (che potrei vedere provenienti da una immagine) potrei calcolarmi la distribuzione degli angoli, e poi interporarla con un polinomio. A questo punto userei il polinomio per spalmare gli angoli sulla matrice, in modo da avere piu angoli e quindi piu precisione laddove gli angoli sono piu distribuiti, e meno angoli dove sono piu sparsi. Esattamente come i floating point sono piu precisi tra 0 e 1 che tra 10^10 e 1+10^10.
Ok però tra il dire e il fare c'è di mezzo il mare. Qualche consiglio su come fare ciò in pratica?
cdimauro
07-11-2008, 07:34
Mi sembra ovvio: limita il range dei numeri che ti servono considerando la dimensione della mantissa, e non abusare degli esponenti proprio perché ti fanno variare troppo i dati.
I float non sono numeri reali, ma un piccolo sottoinsieme nemmeno uniforme di numeri razionali, come hai potuto notare.
Dalle tue parole mi viene da pensare che non ti serva necessariamente un floating pint.
Questi 2^16 + 2^16 bit posizionali in un intero a 32 bit ;) Alla fine la quantità di informazione rappresentabile è esattamente al stessa.
Dalle tue parole mi viene da pensare che non ti serva necessariamente un floating pint.
Questi 2^16 + 2^16 bit posizionali in un intero a 32 bit ;) Alla fine la quantità di informazione rappresentabile è esattamente al stessa.
Gia'.
Scegli 4 miliardi di punti della tua sfera, e li numeri a partire da 0 fino appunto a 4miliardi.
Gia'.
Scegli 4 miliardi di punti della tua sfera, e li numeri a partire da 0 fino appunto a 4miliardi.
Ne ha già scelti 4 miliardi ;)
Dalle tue parole mi viene da pensare che non ti serva necessariamente un floating pint.
Questi 2^16 + 2^16 bit posizionali in un intero a 32 bit ;) Alla fine la quantità di informazione rappresentabile è esattamente al stessa.
l'idea è che da un float ottengo un altro float cosi riapplico l'algoritmo
Gia'.
Scegli 4 miliardi di punti della tua sfera, e li numeri a partire da 0 fino appunto a 4miliardi.
il problema è come distribuirli....
l'idea è che da un float ottengo un altro float cosi riapplico l'algoritmo
Ma non hai detto che se lo riapplichi diverge ?
Ma non hai detto che se lo riapplichi diverge ?
di quanto? poco tanto? non lo so. Io ci provo e poi vedo. Anche perchè usando quel trucchetto della sfera nel caso degli angoli piu comuni dovrei riportarmi alla condizione ideale di non perdere nessuna cifra significativa.
edit: ha risposto lui sopra, ho detto cavolata :asd:
Gia'.
Scegli 4 miliardi di punti della tua sfera, e li numeri a partire da 0 fino appunto a 4miliardi.
eh no così sono 4 miliardi e uno :read: :O
:asd:
sembra una discussione interessante anche se non ho ben capito la sua reale utilità pratica :fagiano:
come'on boys.... sono sicuro che tra tutte le menti brillanti qua dentro ci sarà qualcuno a cui può venire in mente una buona idea...
Secondo me non è nemmeno corretto mappare una sfera su un retta misurata linearmente. Questo perché la distribuzione dei numeri floating point a 32 bit su una retta non è lineare. Dovresti studiarti qualcosa sulle distribuzioni del tipo dei numeri floating point e magari trovare una formula matematica che la linearizza in modo da poter fare un mapping intero 32 bit <-> floating point a 32 bit.
Così in questo modo fai un mapping della sfera su un segmento di retta suddivisa in 2^32 sezioni. Poi puoi ottenere con il mapping intero 32 bit <-> floating point 32 bit il numero floating point corrispondente.
Fare il mapping non sarebbe nemmeno difficile, basta enumerare tutti i floating point, però serve un bel po' di memoria per fare una tabella statica ;)
Fare un mapping dinamico ed efficiente è tutt'altra cosa.
Ovviamente il mapping deve essere ordinato ;) Mantenere la stessa rappresentazione binaria fra int32 e fp32 non è un mapping ordinato.
Se ho un intero a e un intero a+1, non corrisponde alla rappresentazione binaria di due numeri fp32 "vicini".
Ma di nuovo, perche' non fai uno studio serio?
Fai finta di avere solo 8 bit.
Scegli quindi 2^8 = 256 diverse coordinate della sfera a tuo piacimento, scrivi la parte di compressione e di decompressione e poi decidi se vale la pena scalare verso l'alto con piu' bit.
Ti basta quindi una tabella di 256 entry, alla quale corrisponderanno le 2 coordinate per identificare un punto della sfera.
E poi, alla fine, penserai a come giocare con floating point o qualsiasi altra soluzione ti possa venire in mente.
Fare il mapping non sarebbe nemmeno difficile, basta enumerare tutti i floating point, però serve un bel po' di memoria per fare una tabella statica ;)
Fare un mapping dinamico ed efficiente è tutt'altra cosa.
Ciao, sintetizzo siccome ho poco tempo: i problemi sopra elencati da te li ho già risolti, anzi, ho abbandonato il modello lineare per usare un modello in cui la distribuzione rappresenta la vera distribuzione del set di matrici che sto andando a comprimere.
Mi spiego: l'angolo A compare 2 volte piu frequentemente dell'angolo B, allora preso un intorno abbastanza piccolo di raggio Epsilon avrò che la cardinalità dell'insieme A=[A-E, A+E] è doppia rispetto a quella dell'insieme B.
Ok detto questo, la mia domanda è: come fare il mapping dinamico? In particolare se io ho le distribuzioni di probabilità dei due angoli, come faccio a fare il mapping dinamico basandomi su queste due funzioni?
E' un problema davvero non banale... ma risolverlo permetterebbe di riportare il caso medio al caso ideale: cioè comprimo una matrice N*N in un vettore 2*N senza perdita di cifre significative (sempre tenendo in mente le considerazioni di http://www.hwupgrade.it/forum/showpost.php?p=24638304&postcount=119questo post).
E' vero che varrebbe solo per n=3, ma è anche vero che potrei applicare l'algoritmo 2 volte, o 3 volte per vedere cosa succede.
La mia ipotesi è che alla seconda iterazione la distribuzione degli angoli è simile a quella della prima. Se è vero vorrebbe dire che l'algoritmo si potrebbe applicare molte volte.
Di sicuro però non è vero per tutti i set di matrici possibili, anzi potremmo costruire un set di matrici che vanificherà la nostra ipotesi, il fatto è che si può presupporre una regolarità sulle distribuzioni, o la si può anche imporre costruendo una particolare mappa.
Scusate uso il forum come se fossero appunti personali :P
Ma di nuovo, perche' non fai uno studio serio?
Fai finta di avere solo 8 bit.
Scegli quindi 2^8 = 256 diverse coordinate della sfera a tuo piacimento, scrivi la parte di compressione e di decompressione e poi decidi se vale la pena scalare verso l'alto con piu' bit.
Ti basta quindi una tabella di 256 entry, alla quale corrisponderanno le 2 coordinate per identificare un punto della sfera.
E poi, alla fine, penserai a come giocare con floating point o qualsiasi altra soluzione ti possa venire in mente.
Stesso discorso del post sopra: non è importante quante coordinate scelgo, è importante come le distribuisco.
Ho già una versione del codice che distribuisce linearmente su 32 bit senza applicare due volte, e i risultati sono molto soddisfacenti (l'errore è sempre zero, ma ricordiamoci che sto mappando 8 bit delle tiff usandone 32 dei floating point, quindi la versione finale è piu grande di quella iniziale), scritta in matlab. Adesso vorrei risolvere questo problema della mappa e poi lo porterei in C.
Ciao, sintetizzo siccome ho poco tempo: i problemi sopra elencati da te li ho già risolti, anzi, ho abbandonato il modello lineare per usare un modello in cui la distribuzione rappresenta la vera distribuzione del set di matrici che sto andando a comprimere.
Non mi sembra che stiamo parlando delle stesse cosa, mi sembrava che tu fossi riuscito a mappare una sfera su un segmento di retta, il problema che ti ho posto è ancora successivo a questo ;)
Non mi sembra che stiamo parlando delle stesse cosa, mi sembrava che tu fossi riuscito a mappare una sfera su un segmento di retta, il problema che ti ho posto è ancora successivo a questo ;)
mi sto perdendo.... Io ho mappato la sfera sulla retta. La retta però sono floating point e quindi anche la mappatura è discreta. E fin qui ci siamo.
Decidere come vadano distribuiti i punti sulla sfera per poi collegarli ai floating point è il mio problema.
Io ho una distribuzione di probabilità per decidere le coordinate X dei punti sulla sfera, stessa cosa per Y. Una volta che l'ho mappata devo collegare questi punti alla retta dei floating point, facendo in modo che i valori molto grandi in floating siano poco probabili.
Il fatto è che la distribuzione di probabilità può essere uguale, ma potrei anche volerla cambiare... cambiando quindi la mappatura... è questo il dynamic mapping di cui parlavi, o sbaglio?
mi sto perdendo.... Io ho mappato la sfera sulla retta. La retta però sono floating point e quindi anche la mappatura è discreta. E fin qui ci siamo.
No è qui che non ci siamo. Tu mi immagino abbia mappato una sfera su un segmento di retta assegnando il massimo ed il minimo floating point rappresentabile ai due estremi.
Ma questo non va bene, perché la distribuzione dei floating point la "distanza" fra due floating point successivi rappresentabili non è costante.
Per questo devi lavorare sugli interi in questa porzione di algoritmo. Assegnando il massimo ed il minimo intero rappresentabile agli estremi della retta ottieni appunto un distribuzione di elementi sulla retta in cui la distanza fra due elementi è fissa.
Se non lo facessi l'errore di rappresentazione schizzerebbe alle stelle in quanto rischieresti di ottenere con probabilità molto bassa alcuni floating point la cui distribuzione sulla retta è molto densa e di ottenere con probabilità molto alta floating point molto distanti fra loro.
A questo punto dagli interi puoi passare ai floating point facendo un mapping 1 a 1 di un intero in un floating. Qui però non puoi convertire un intero in floating point semplicemente assegnando ad un fp32 la stessa rappresentazione binaria di un int32, questo perché la conversione non mantiene l'ordine. Devi quindi fare un'enumerazione ordinata dei numeri floating point ed usare questa enumerazione per ottenere la rappresentazione floating point corrispondente.
Decidere come vadano distribuiti sulla sfera a questo punto è un altro problema, anche di più facile risoluzione, se conti che di fatto le rappresentazioni floating point ora sono distribuite di fatto sulla retta in modo regolare. Ora il problema equivale realmente a mappare un segmento di retta su una sfera, prima sicuramente non lo era.
No è qui che non ci siamo. Tu mi immagino abbia mappato una sfera su un segmento di retta assegnando il massimo ed il minimo floating point rappresentabile ai due estremi.
No ho usato un approccio un po diverso:
Ho preso un floating point, ho letto i bit e ho diviso in due: mantissa ed esponente. Ho preso la mantissa e lo divisa in due secondi i bit: 12 bit per x, 11 bit +1 del segno per y. A questo punto ho scelto 2^12*2^12 punti e li ho mappati semplicemente numerandoli, ovviamente con una espressione sintetica (non è che ho costruito una matriciona con tutti i valori e i corrispettivi)....
Solo che cosi non va bene perchè:
A) Non uso 8 bit di informazione
B) E' computazionalmente intenso. Io vorrei se si potesse fare, una espressione che mi trasforma i due angoli subito in un floating point, però usando tutta la precisione possibile. Boh.
Non usando 8 bit di informazione è impossibile realizzare ciè che vuoi ;)
Prova a cercare di seguire il discorso che ho fatto, si riduce a mappare 2^32 interi su una sfera, direi che è molto più semplice e sfrutti anche il resto dei bit.
Sono sicuro che il mapping da intero a float è facilissimo pensandoci un po'.
Ad esempio il primo modo che mi viene in mente è usando il modulo. Prendi il segno e lo metti da parte come primo bit delfloat. Prendi l'intero a 32 bit in valore assoluto, lo dividi per 2^23 ed ottieni l'esponente. Fai il modulo per 2^23 ed ottieni la mantissa. Dovrebbe funzionare, probabilmente c'è qualche incongruenza per qualche valore particolare (ad esempio per i numeri con divisibili per 2^23), ma penso che tu la possa risolvere senza problemi.
Ad esempio il primo modo che mi viene in mente è usando il modulo.
Si si ed infatti l'ho realizzato cosi!
Solo che non uso l'esponente perchè sennò magari l'esponente va a 11111... rendendo il numero enorme, e quindi impedendomi di applicare due volte l'algoritmo... in questo senso dico che non uso 8 bit:
1 bit di segno + 23 bit di mantissa + 8 bit di esponente.
Non riesco neanche a capire dove parta l'esponente: ho provato sia a scrivere solo i primi 4 bit che gli ultimi 4 bit eppure l'esponente cresce come se stessi modificando per prima le cifre piu significative! (tipo potrei fare 000111=14 oppure 111000=112, io provo a fare 14, ma mi viene in modo casuale 112 o 14)
L'esponente è memorizzato in eccesso 127: http://it.wikipedia.org/wiki/IEEE_754
Ma tu non dovresti avere problemi con numeri grandissimi, almeno mi pare di capire.
Ma tu non dovresti avere problemi con numeri grandissimi, almeno mi pare di capire.
quello che voglio evitare io è un rapporto molto grande. Facciamo un esempio:
il vettore [1 1 10^20] è un pessimo vettore, anche se è possibile che mi arrivi, perchè una volta normalizzato il computer lo confonde con [0 0 1] facendomi perdere molta informazione.
Se la mia mappa mi restituisce molte volte un vettore di quel tipo per me sarà impossibile riapplicare l'algoritmo, e quindi è una condizione che vorrei il piu possibile evitare.
Se la mia mappa mi restituisce molte volte un vettore di quel tipo per me sarà impossibile riapplicare l'algoritmo, e quindi è una condizione che vorrei il piu possibile evitare.
Ma non la puoi evitare perché a quel punto dovresti mappare 2^32 bit, anche temporaneamente in un insieme di cardinalità minore, facendoti perdere informazione. Perché da quanto mi pare di capire, anche i risultati intermedi li devi memorizzare su fp32.
Ma non la puoi evitare perché a quel punto dovresti mappare 2^32 bit, anche temporaneamente in un insieme di cardinalità minore, facendoti perdere informazione. Perché da quanto mi pare di capire, anche i risultati intermedi li devi memorizzare su fp32.
lo so che non posso evitarlo. Però con il dinamic mapping vorrei attribuire i 3 bit rappresentanti le cifre piu significative dell'esponente agli angoli meno probabili, usando il dynamic mapping.
Secondo i miei calcoli dovrei riuscire a farci finire zero angoli su 10 mb in ingresso.
lo so che non posso evitarlo. Però con il dinamic mapping vorrei attribuire i 3 bit rappresentanti le cifre piu significative dell'esponente agli angoli meno probabili, usando il dynamic mapping.
Secondo i miei calcoli dovrei riuscire a farci finire zero angoli su 10 mb in ingresso.
Se vuoi mantenere un'errore basso imho il mapping deve essere equiprobabile, altrimenti perdi troppa informazione.
Se vuoi mantenere un'errore basso imho il mapping deve essere equiprobabile, altrimenti perdi troppa informazione.
si ma se io ho dei dati che sono piu probabili di altri, è meglio concentrare su di loro piu bit di informazione....
ti ricordo che la distribuzione di probabilità viene calcolata in base all'imput...
The_ouroboros
11-11-2008, 14:56
novità?
ragazzi siete tutti molto gentili, vi prometto che vi citerò tutti nel paper ehehehhe... anche se nessuno lo leggerà :(:( :P
Novita'?
In un'altra discussione hai detto di avere pubblicato qualcosa in merito a questo tema.
(Dicendo poco elegantemente che io non ci avrei capito nulla)
Ci sono aggiornamenti?
blackskop
15-02-2009, 20:55
News?
cdimauro
16-02-2009, 07:56
Nessuna, perché wlog è troppo impegnato a flammare in S.P.A. :asd:
~FullSyst3m~
16-02-2009, 08:24
Nessuna, perché wlog è troppo impegnato a flammare in S.P.A. :asd:
Società per azioni?? :asd:
cdimauro
16-02-2009, 08:26
http://www.hwupgrade.it/forum/forumdisplay.php?f=88 ;)
banryu79
16-02-2009, 11:37
Nessuna, perché wlog è troppo impegnato a flammare in S.P.A. :asd:
Talmente impegnato che deve avere combinato qualcosa: sul suo profilo risulta bannato...
||ElChE||88
16-02-2009, 12:16
Talmente impegnato che deve avere combinato qualcosa: sul suo profilo risulta bannato...
Bannato 2 settimane per dose eccessiva di cazzate:
http://www.hwupgrade.it/forum/showthread.php?p=26260531#post26260531
:asd:
cdimauro
16-02-2009, 12:52
:rotfl: Per fortuna è da un pezzo che non leggo più i commenti di News e Articoli. :p
banryu79
16-02-2009, 13:41
Bannato 2 settimane per dose eccessiva di cazzate:
http://www.hwupgrade.it/forum/showthread.php?p=26260531#post26260531
:asd:
Però, certo che sono severi i Moderatori di quella sezione...
Mmm, magari nelle prossime 2 settimane si metterà sotto con il suo algoritmo.
Mo la smetto che sono OT :D
blackskop
25-05-2009, 21:43
News?
cdimauro
26-05-2009, 07:04
Non ci possono essere novità su una cosa che è dimostrato essere impossibile da realizzare.
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.