[java] effettuare dct su una matrice

[antedesk]

Salve a tutti!
ho un problema un pò più serio questa volta, dovrei effettuare il calcolo della trasformata discreta del coseno(dct) su una matrice di interi, che rappresenta l'immagine.
il codice per il calcolo della dct è una semplice formula matematica che ho trovato in rete e riconvertita in codice java. Il problema è che così su immagini molto grandi di mette un eternità, tempo che non sono disposto ad aspettare
Studiando un pò di materiale sulla compressione jpeg dove viene utilizzata la dct e dove:

"Ogni matrice saràsuccessivamente divisa in blocchi di dimensione 8x8, ovvero ogni blocco conterrà 64 pixel dell’immagine originale. Quindi se M o N non risultano multipli di 8, sono aggiunte delle copie dell’ultima riga o dell’ultima colonna alla matrice dell’immagine originale, sino a che la dimensione della nuova matrice non diventi un multiplo di 8.
Ad ogni blocco è applicata la trasformata DCT bidimensionale, che restituisce ancora un bloccodi dimensioni 8x8."

il problema è che nono so proprio dove mettere le mani per suddividere la matrice in blocchetti 8x8 e di aggiungere una riga qualora non dovesse essere un multiplo di 8

potete aiutarmi? se serve posso postare il codice della funzione dct.

Grazie a tutti, spero di avere risposta

[desa]

Non conosco l'algoritmo DCT (anche se forse dovrei, dai "bei" tempi di Analisi in università) ma, basandomi su quello che mi sembra di capire, vedo due strade possibili:
1) L'algoritmo lavora sulla (unica) istanza dell'immagine (la matrice di int) presente in memoria, ricevendo in ingresso gli indici di partenza, sia della riga che della colonna;
2) L'algoritmo lavora sugli blocchi 8x8, ricevendo quindi come parametro, volta per volta, delle COPIE delle sottomatrici da elaborare.

Il primo metodo è (probabilmente) più efficiente, ma è di difficile utilizzo se l'elaborazione DCT implica la modifica dei valori nella matrice, il secondo è (probabilmente) più lento e di più facile sviluppo.

Prova a valutare queste due soluzioni sulla base di ciò che devi realizzare, in caso di problemi scrivi pure qua sul forum

[antedesk]

Originariamente inviato da desa
Non conosco l'algoritmo DCT (anche se forse dovrei, dai "bei" tempi di Analisi in università) ma, basandomi su quello che mi sembra di capire, vedo due strade possibili:
1) L'algoritmo lavora sulla (unica) istanza dell'immagine (la matrice di int) presente in memoria, ricevendo in ingresso gli indici di partenza, sia della riga che della colonna;
2) L'algoritmo lavora sugli blocchi 8x8, ricevendo quindi come parametro, volta per volta, delle COPIE delle sottomatrici da elaborare.

Il primo metodo è (probabilmente) più efficiente, ma è di difficile utilizzo se l'elaborazione DCT implica la modifica dei valori nella matrice, il secondo è (probabilmente) più lento e di più facile sviluppo.

Prova a valutare queste due soluzioni sulla base di ciò che devi realizzare, in caso di problemi scrivi pure qua sul forum

ciao!
prima di tutto GRAZIE
e ora veniamo a noi con una piccola premessa.
in realtà devo applicare questo algoritmo non a tutta l'immagine ma bensi alla sua componente Y delle luminanze (nel caso in cui non dovessi saperlo, sto parlando dello spazio colore YUV) che ho estratto dall'immagine dopo aver fatto la conversione da rgb a yuv.
Quindi leggendo la tua risposta mi è venuto in mente che potrei fare un metodo di appoggio che esegue il calcolo della dct, ed il metodo vero e proprio che la ingloba dove scorro la matrice riga per riga (senza andare a vedere ogni singolo elemento) e memorizzo il risultato in una matrice che mi sono creato al di fuori del for.

per intenderci l'algoritmo della dct è il seguente

 
public double[][] DCT(double[] g) {
		int M = g.length;
		double s = Math.sqrt(2.0 / M); //common scale factor
		double[] G = gG;
		for (int m = 0; m < M; m++) {
			double cm;
			if (m == 0)
				cm = 1.0 / Math.sqrt(2);
			else
				cm = 1.0;
			double sum = 0;
			for (int u = 0; u < M; u++) {
				double Phi = (Math.PI * (2 * u + 1) * m) / (2.0 * M);
				sum += g[u] * cm * Math.cos(Phi);
			}
			G[m] = s * sum;
		}
		return G;
	}

la cui formula la puoi vedere riscritta qui:
http://www.cs.cf.ac.uk/Dave/Multimedia/node231.html

secondo te potrebbe funzionare come metodo? provo ad implementarlo nel mentre

[desa]

Riesco a seguirti in merito a questioni tecniche sulla realizzazione dell'algoritmo, ma non sono molto fondato relativamente alla teoria dietro l'elaborazione delle immagini e mi perdo un po' sul tuo discorso...

Mi sembra comunque che il tuo approccio possa andare bene, ma non ho capito come mai nel codice che hai postato lavori su array quando si è sempre parlato di matrici (l'immagine o le 8x8). Oltretutto il valore di ritorno del metodo DCT è una matrice di double, mentre G è dichiarato come un array...

[antedesk]

Perdonami, probabilmente mi sono espresso male
il codice che ho postato è l'algoritmo per il calcolo della dct che avevo scritto al volo e che purtroppo conteneva errori come il tipo di ritorno e il parametro passato. Ho provato ad implementare la soluzione che ti ho descritto nel precedente post, ma sinceramente sto cercando di capire come testarlo, poichè neanche io sono molto informato in modo approfondito al riguardo.

riporto il codice della soluzione che ho ideato, anche se ripeto(finchè non la testo) non penso sia corretta per quanto riguarda i valori che dovrei ottenere.

public double[][] dct_trasform(int[][] ym){
		
		int h= ym.length;
		int w= ym[0].length;
		Dct1d d= new Dct1d();
		double[][]ydct=new double[h][w];
		
		for(int i=0;i<ydct.length;i++){
			ydct[i]=d.DCT(ym[i]);
		}
		
		return ydct;
	}

public double[] DCT(int[] g) {
		int M = g.length;
		double s = Math.sqrt(2.0 / M); //common scale factor
		double[] G=new double[M];
		for (int m = 0; m < M; m++) {
			double cm;
			if (m == 0)
				cm = 1.0 / Math.sqrt(2);
			else
				cm = 1.0;
			double sum = 0;
			for (int u = 0; u < M; u++) {
				double Phi = (Math.PI * (2 * u + 1) * m) / (2.0 * M);
				sum += g[u] * cm * Math.cos(Phi);
			}
			G[m] = s * sum;
		}
		return G;
	}

provo a testarla...

Senti ma secondo te per suddividere la matrice in blocchetti 8x8 applicando su questi l'algoritmo per il calcolo della DCT?
ah! la chicca della dct è che pone nell'angolo in alto a sinistra le basse frequenze e in quello in basso a destra le altre frequenze.

comunque Grazie per la disponibilità sei stato molto gentile

[antedesk]

fichissimo... l'ho provato, eseguendo tutto l'algoritmo che dovevo fare, e... l'immagine(ricostruita riunendola alle matrici u e v) esce tutta rovinata sulle colonne sinistra ( ), ergo i valori della dct non sono stati allocati opportunamente.
devo elaborare un altra strategia.(non posto l'immagine perchè sinceramente mi vergogno del risultato )