Newsgroup: it.comp.software.divx
Titolo: indice SSIM

ho letto l'articolo segnalatomi da Giubbe ("Image Quality Assessment:
From Error Visibility to Structural Similarity") e nei prossimi giorni,
tempo permettendo, volevo divertirmi a implementarlo e a testarlo.
qui riassumo velocemente l'articolo: l'obiettivo che si sono posti gli
autori e' quello di definire un metodo oggettivo di analisi della
qualita' di immagini, diverso dai metodi piu' comuni: il loro approccio
tenta di quantificare le differenze nelle immagini in termini
"strutturali" ("SSIM" sta per "Structural SIMilarity"). In estrema
sintesi, secondo loro, questo dovrebbe essere un modello piu' accurato
dei processi visivi umani, che tiene conto anche di "influenze
top-down" (mentre i metodi tradizionali simulerebbero solo i processi
"bottom-up" dei primissimi stadi della visione); ad ogni modo, anche il
loro approccio e' di tipo "full-reference" (vuol dire che permette di
valutare la bonta' di un'immagine, non a se' stante, ma in riferimento
a un'altra immagine; in pratica, una delle due immagini e' quella che
consideriamo "perfetta", mentre l'altra, che e' quella di cui vogliamo
valutare la qualita', e' ottenuta da qualche processo di compressione,
e tipicamente presentera' qualche degradazione). Gli autori passano
quindi a descrivere il metodo di calcolo dell'indice SSIM, a partire
dalle due immagini da confrontare; va detto che il metodo non e'
complicato...
la scorsa settimana Giubbe aveva calcolato l'indice SSIM di alcuni
filmati (ottenuti usando diversi valori di "max key int"); mi aveva
accennato di aver usato un programma (PSNR qualcosa...) che usa un filtro
avisynth... ora vorrei sapere come aveva ottenuto quei valori finali...
erano la media aritmetica degli indici SSIM calcolati su ogni coppia di
frame? in altre parole:
- prendo un filmato di partenza (diciamo un segmento mpeg-2 di un DVD);
- lo codifico in divx usando un certo "max key int";
- prendo una coppia di frame, uno dal filmato di partenza e l'altro
  dal filmato codificato (nella stessa posizione) e ne calcolo l'indice
  SSIM
- faccio la media aritmetica di tutti gli indici di tutte le coppie
funziona in questo modo o sbaglio qualcosa?
avrei un'altra domanda ma semmai la faro' in seguito :-)

 - faccio la media aritmetica di tutti gli indici di tutte le coppie
Il programma si chiama psnrCreator. Il valore che ho riportato è la media
del confronto di tutte le coppie
bye
-- 
HomePage e FAQ: 
http://giubbe.altervista.org
Inutile scrivere in privato, non ricevo le email

 del confronto di tutte le coppie
perfetto, grazie.
mi sembra di avere capito, dalle tue prove, che gli I-frame sono risultati
un po' piu' accurati dei P-frame (e questi dei B-frame), nel senso che
ottengono un indice SSIM piu' elevato (non risultava in modo esplicito, ma
segue dal fatto che, aumentando il numero di keyframe, nella codifica a
qualita' costante, veniva fuori un indice SSIM un po' piu' alto)...
ho scaricato questo file: ssim_25_dll_20030914.zip
dovrebbe essere il filtro Avisynth dell'indice SSIM di cui parlavi;
in testa al codice sorgente c'e' questo commento:
--------------------------
the equivalent of Zhou Wang's SSIM matlab code from
http://www.cns.nyu.edu/~zwang/files/research/ssim/index.html
with K1 = 0.01, K2 = 0.03 and windows = ones(8) since this enables a fast
implementation using summed area tables.
the measure is described in "Image quality assessment: From error
measurement to structural similarity"
was originally adapted from the matlab code for the universal image
quality index
--------------------------
non ho Matlab, pero' ho una versione vecchia di Octave, che credo sia
un suo clone, quindi ho battuto:
--------------------------
octave:1> ones(8)
ans =
  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1
octave:2> fspecial('gaussian', 11, 1.5 )
error: `fspecial' undefined near line 2 column 1
error: evaluating index expression near line 2, column 1
--------------------------
purtroppo, la mia versione di Octave non calcola la matrice
gaussiana... come dicevo all'inizio, se qualcuno ce l'ha me la mandi
(altrimenti dovro' calcolarla...)
come si vede, la matrice ones(8) e' una matrice 8x8 i cui elementi
sono tutti pari a 1 (in realta', viene usata la matrice normalizzata,
cioe' ones(8)/sum(sum(ones(8))), cioe' la matrice 8x8 i cui elementi
sono tutti pari a 0.015625, in modo tale che la somma di tutti gli
elementi sia pari a 1); l'articolo pero' sconsiglia di usare tale
matrice:
--------------------------
In [6] and [7], the local statistics , and are computed within a local
8x8 square window, which moves pixel-by-pixel over the entire image. At
each step, the local statistics and SSIM index are calculated within the
local window. One problem with this method is that the resulting SSIM
index map often exhibits undesirable "blocking" artifacts. In this paper,
we use an 11x11 circular-symmetric Gaussian weighting function, with
standard deviation of 1.5 samples, normalized to unit sum. The
estimates of local statistics ..., and ... are then modified accordingly
as (14) (15) (16). With such a windowing approach, the quality maps
exhibit a locally isotropic property. Throughout this paper, the SSIM
measure uses the following  parameter settings:
[...]
--------------------------
a questo punto ho implementato la funzione: per il momento ho usato
anch'io una matrice di pesi uniformi, ma provero' se una distribuzione
gaussiana cambia qualcosa nei risultati.
per il resto mi sono attenuto abbastanza fedelmente all'articolo, con
questa particolarita': le immagini da confrontare sono codificate nello
spazio di colori rgb24, cosi' le ho considerate come 3 immagini a 256
livelli di grigi, ho calcolato separatamente gli indici SSIM e infine
ne ho fatto la media pesata; i pesi sono 0.299, 0.587, 0.114
(rispettivamente per le componenti R, G, B).
poi ho scritto un programmino di prova, "test-ssim", che prende due
immagini in ingresso (devono essere a colori, e devono avere la stessa
risoluzione, possono essere in formato PNG, PPM, JPG) e stampa
l'indice calcolato nel modo che ho descritto.
ad esempio, passando la stessa immagine per entrambi gli argomenti,
si ottiene 1; modificando leggermente i colori di un'immagine e
confrontandola con l'originale, ottengo: 0.995908
la mia versione e' abbastanza piu' lenta rispetto a quella del
filtro Avisynth, perche' l'ho scritta generalizzata a matrici di
pesi arbitrarie; ad esempio, la misura della luminosita' l'ho
scritta cosi':
    for ( i = 0 ; i < s->win_h ; i++ ) {
        map1 = s->map1 + ( s->x + ( s->y + i ) * s->w ) * 3;
        map2 = s->map2 + ( s->x + ( s->y + i ) * s->w ) * 3;
        for ( j = 0 ; j < s->win_w ; j++ ) {
            s->mur1 += *weights * (double)( *map1++ );
            s->mur2 += *weights * (double)( *map2++ );
            s->mug1 += *weights * (double)( *map1++ );
            s->mug2 += *weights * (double)( *map2++ );
            s->mub1 += *weights * (double)( *map1++ );
            s->mub2 += *weights * (double)( *map2++ );
            weights++;
        }
    }
questo calcolo viene eseguito tante volte quante sono le "finestre"
8x8 all'interno delle immagini; ad esempio, se la risoluzione delle
immagini e' 640x480, il numero delle finestre e'
(640-7)*(480-7)= 299,409
in tutto vengono fatte 6*299,409=1,796,454 moltiplicazioni (e
altrettante somme);
invece, nella versione Avisynth, siccome il tizio ha assunto che i
pesi sono tutti uguali, tutte le moltiplicazioni spariscono (basta
dividere il totale, alla fine, per 299,409)
se qualcuno e' interessato a fare qualche prova, me lo faccia
sapere, in tal caso preparero' un file da scaricare...

 altrettante somme);
in realta' ho dimenticato un fattore: il numero di moltiplicazioni
effettivo e':
64*6*299,409 = 114,973,056
a queste vanno sommate altrettante moltiplicazioni necessarie per
misurare il contrasto, e altre per le correlazioni strutturali...
se, invece di usare finestre 8x8, si usano finestre 11x11, il numero
di moltiplicazioni (per la sola luminosita') diventa:
(11^2)*6*(640-(11-1))*(480-(11-1)) = 214,968,600
praticamente raddoppia...
ho calcolato la matrice gaussiana 11x11 (con deviazione standard 1.5)
e normalizzata in modo che la somma dei coefficienti sia 1;
a me risulta essere questa, a meno che non abbia fatto errori:
--------------------------------------------
    0.000001, 0.000007, 0.000037, 0.000112, 0.000219, 0.000273, 0.000219,
0.000112, 0.000037, 0.000007, 0.000001,
    0.000007, 0.000057, 0.000273, 0.000831, 0.001618, 0.002021, 0.001618,
0.000831, 0.000273, 0.000057, 0.000007,
    0.000037, 0.000273, 0.001296, 0.003937, 0.007668, 0.009576, 0.007668,
0.003937, 0.001296, 0.000273, 0.000037,
    0.000112, 0.000831, 0.003937, 0.011959, 0.023294, 0.029091, 0.023294,
0.011959, 0.003937, 0.000831, 0.000112,
    0.000219, 0.001618, 0.007668, 0.023294, 0.045371, 0.056661, 0.045371,
0.023294, 0.007668, 0.001618, 0.000219,
    0.000273, 0.002021, 0.009576, 0.029091, 0.056661, 0.070762, 0.056661,
0.029091, 0.009576, 0.002021, 0.000273,
    0.000219, 0.001618, 0.007668, 0.023294, 0.045371, 0.056661, 0.045371,
0.023294, 0.007668, 0.001618, 0.000219,
    0.000112, 0.000831, 0.003937, 0.011959, 0.023294, 0.029091, 0.023294,
0.011959, 0.003937, 0.000831, 0.000112,
    0.000037, 0.000273, 0.001296, 0.003937, 0.007668, 0.009576, 0.007668,
0.003937, 0.001296, 0.000273, 0.000037,
    0.000007, 0.000057, 0.000273, 0.000831, 0.001618, 0.002021, 0.001618,
0.000831, 0.000273, 0.000057, 0.000007,
    0.000001, 0.000007, 0.000037, 0.000112, 0.000219, 0.000273, 0.000219,
0.000112, 0.000037, 0.000007, 0.000001
--------------------------------------------
ho ricalcolato l'indice usando questa matrice sulle stesse due immagini
del post precedente e il risultato e' questo:
0.995818
con la matrice 8x8 uniforme era venuto:
0.995908
su questo esempio e' quasi uguale...
ho fatto un altro esempio, convertendo un'immagine a colori in bianco
e nero (anzi, a livelli di grigi) e salvandola come ppm...
questi i risultati:
0.975407 (8x8 uniforme)
0.978862 (11x11 gaussiana)
in questo caso, e' piu' alto il secondo...
prossimamente scrivero' una utility che confronta due filmati (facendo
la media dell'indice calcolato su ogni coppia di frames)... (piu' che
altro mi interessa confrontare i risultati ottenuti da XviD e dal codec
mpeg4 di libavcodec...)

 sapere, in tal caso preparero' un file da scaricare...
Io, desidero fare un confronto tra il tuo algoritmo e quello di avisymrth,
mi incuriosisce il fatto delle moltiplicazioni mancanti.
Solo una piccola nota, io ho usato il filtro SSIM fornito con psnrcreator,
non so che versione esso sia (a parte il numero 0.23).


 mpeg4 di libavcodec...)
Bellissima questa cosa, cosě abbiamo un confronto anche sotto linux!
Bye


 non so che versione esso sia (a parte il numero 0.23).
in quello che ho scaricato io, c'e' questo:
fprintf(log2,"SSIM: Structural Similarity Index Metric 0.23\n");
il numero 0.23 coincide quindi potrebbe essere lo stesso.
sto pensando a un modo per velocizzare il calcolo, altrimenti sara'
impossibile calcolare l'indice di un intero filmato; bisognera' limitarsi
a poche migliaia di frames (e richiedera' comunque molti minuti).
il problema e' se la matrice 11x11 gaussiana dia effettivamente risultati
piu' accurati di quella uniforme, come dicono gli autori...
se optassi per la sola matrice uniforme, potrei velocizzare parecchio...
non so se hai presente l'articolo... la misura della luminosita' viene
stimata come l'intensita' media: si sommano tutti i pixel e si divide il
totale per il numero dei pixel; ma se la somma e' pesata e i pesi sono
diversi, occorre moltiplicare *ogni* pixel per il peso corrispondente, e
sommarne i risultati... e' questo che porta via la maggior parte del
tempo...
il calcolo dell'indice non viene fatto su tutta l'immagine, ma localmente,
su una "finestra" di piccole dimensioni; tale finestra viene spostata,
pixel per pixel, su tutta l'immagine; alla fine si fa la media degli indici
ottenuti per ciascuna finestra.
ad esempio, se la risoluzione delle immagini da confrontare e' 640x480 e
usiamo una finestra 11x11, il numero di tutti i possibili modi di
posizionare la finestra sulle immagini e' il numero di tutte le sottomatrici
11x11 di una matrice 640x480, cioe': (640-10)*(480-10)
la matrice dei pesi usati per le misure statistiche delle immagini ha la
risoluzione di una finestra.
se i pesi sono diversi, non c'e' nessun calcolo che venga fatto per una
finestra che io possa riciclare per una finestra adiacente...
pero' un'ottimizzazione importante posso farla, sfruttando il fatto che
la matrice e' a simmetria centrale (vuol dire che il valore di un
elemento dipende solo dalla sua distanza dall'elemento centrale):
posso vedere la matrice come composta da otto "spicchi", cosi':
  *****************
  **      *      **
  * *     *     * *
  *  *    *    *  *
  *   *   *   *   *
  *    *  *  *    *
  *     * * *     *
  *      ***      *
  *****************
  *      ***      *
  *     * * *     *
  *    *  *  *    *
  *   *   *   *   *
  *  *    *    *  *
  * *     *     * *
  **      *      **
  *****************
i coefficienti che si trovano sulle diagonali si ripetono 4 volte,
tutti gli altri 8 volte;
questo fatto puo' essere sfruttato per "mettere in evidenza" ogni
peso, effettuando prima la somma degli elementi corrispondenti e
dopo cavarsela con un'unica moltiplicazione...
in questo modo dovrei velocizzare un po'...
tra l'altro non sono ancora sicuro al 100% di avere calcolato bene
la matrice gaussiana che dicono loro; a me viene fuori un coefficente
centrale (il valore massimo) pari a 0.070762, mentre i minimi sono
ai quattro angoli e valgono 0.000001
mi pare che ci sia troppa differenza... forse ho sbagliato, usando
un valore di deviazione standard troppo piccolo... con un valore
piu' alto, i valori dovrebbero essere piu' uniformi (la gaussiana
si "schiaccia"); devo controllare con qualcuno che ha matlab...
quando otterro' un programmino usabile, lo rendero' scaricabile e
ti faro' sapere...

 in questo modo dovrei velocizzare un po'...
dovrei aumentare la velocita' di circa 4-5 volte.
considerando una matrice n x n (con n dispari), i suoi n^2 elementi
possono essere ripartiti in:
- un elemento centrale
- 2*(n-1) sulle due diagonali (escluso il centro)
- 2*(n-1) sulla colonna e sulla riga di mezzo (escluso il centro)
- n^2-4*n+3 sono i restanti
si verifica (per induzione) che n^2-4*n+3 e' proprio un multiplo di 8
(per n dispari)
quindi, il numero di moltiplicazioni necessarie (per ogni finestra)
passa da n^2 a 1+(n-1)+(n^2-4*n+3)/8
per n=11 (il nostro caso), si passa quindi da 121 a 21
moltiplicazioni (poco piu' di un sesto)...

 On 09-Jul-05 Frank Sinapsi wrote:
Non sai con che sentimento di ammirazione misto ad invidia che sto
seguendo questo thread... ;)
-- 
Saluti, Kap - ICQ 19857429 - ¥'s Fan #01 - 
www.lordkap.it
 - VCC
Nessun grande artista vede mai le cose così come sono. Altrimenti non
sarebbe più un artista. - Oscar Wilde