Newsgroup: it.comp.software.divx
Titolo: algoritmi di scaling

salve.
come ho scritto ieri in alcuni post, mi sono deciso a fare qualche test
per mettere in risalto qualche caratteristica dei vari algoritmi di
scaling; di questi ne esistono molti e pare che ognuno presenti pregi e
difetti e che alcuni siano preferibili in alcune circostanze, e altri
in altre... quindi i miei test sono tutt'altro che completi...
l'idea e' molto semplice: dato che il confronto a occhio nudo dei
risultati di un'applicazione degli algoritmi non e' facile, l'idea e'
quella di "amplificare" gli sbilanciamenti, reiterando le applicazioni;
in questo modo, ad esempio, se un algoritmo ha una leggera tendenza a
modificare le caratteristiche cromatiche, l'effetto viene amplificato
e diventa chiaramente visibile a occhio nudo.
gli algoritmi che ho considerato sono noti con questi nomi:
 - nearest_neighbour
 - fast_bilinear
 - bilinear
 - bicubic
 - lanczos
 - area
 - luma_bicubic
 - gauss
 - sincR
 - bicubic_spline
(in realta', alcuni di essi sarebbero parametrizzabili, ma ho usato
impostazioni standard)
a questi ho aggiunto un mio algoritmo (che ho indicato con il termine
"full").
quello che ho scoperto e' che:
- il mio algoritmo commette degli errori di approssimazione, che vengono
  evidenziati dall'applicazione reiterata; questo mi e' stato utilissimo
  perche' mi permettera' di migliorarlo (perche' non ci avevo pensato
  prima?);
- tutti gli algoritmi hanno una tendenza a modificare i colori (eccetto
  il mio e "nearest neighbour", che e' un caso particolare);
- i migliori algoritmi, a mio parere, sono: lanczos, bicubic spline,
  luma bicubic, e bicubic (secondo me, questi 4 danno risultati abbastanza
  simili, perlomeno negli esempi che ho considerato);
qui potete vedere una immagine riassuntiva che mette a confronto i
risultati di una tipica applicazione reiterata:
http://fsinapsi.altervista.org/code/umacmp.jpg
il frame originale (estratto dal DVD Pulp Fiction) e' "uma.jpg"
(appare allungato verso l'alto, perche' l'AR e' 16:9);
le singole immagini sono dentro questo zip:
http://fsinapsi.altervista.org/code/umacmp.zip
se avete idee, o altri tipi di test che vi piacerebbe fare, ecc. fatemi
sapere.

   prima?);
come sopra... mi piacerebbe molto provarlo.



Si il tuo risultato e' quello che piu' si avvicina ai colori
originali.
Tienici aggiornati.

 lanczos)?
che ne so? :-)
se mi dai spiegazioni, saro' felice di testarlo.
come ho scritto ieri, le mie conoscenze di ottica e percezioni di
colori sono assai scarse: l'idea di base del mio algoritmo e' la piu'
OVVIA che possa venire in mente a un informatico, e sarei molto
meravigliato se questo algoritmo non fosse gia' noto da un bel po': si
tratta di un banale resampling lineare! se ti interessa e se la
documentazione che ti ho indicato non ti aiuta a capire, dimmelo e ti
spiego per bene come funziona (e' semplice!)

 sapere.
Io, sinceramente, non vedo tutta questa importanza nella tenuta del colore
perchè non viene mai applicato più di due volte un resize (e già due volte
è un evento raro). In un algoritmo di resize la cosa più importante è il
mantenimento dei dettagli. Io il migliore che ho provato è il lanczos.
Ciò non toglie che se riuscissi a scrivere un algoritmo ottimo (prendendo
come riferimento un certo bitrate) e che mantenga anche il colore allora
quello diventerebbe il "mio" algoritmo di resize.
Io non ci capisco nulla di algoritmi di resize e quindi non ti posso
aiutare, però un'occhiata al tuo algoritmo la dò, nel caso mi venga in
mente qualcosa (possibilità alquanto remota) te lo faccio sapere.
bye
-- 
HomePage e FAQ: 
http://giubbe.altervista.org
Inutile scrivere in privato, non ricevo le email

 aiutare, però un'occhiata al tuo algoritmo la dò,
cerco di esporre l'idea di base, che e' facilissima:
immagina una scacchiera;
una scacchiera ha 64 caselle (8x8: chiamiamola "risoluzione"), e
queste sono quadrate;
se la scacchiera e' di gomma, puoi immaginare di allargarla: in questo
modo le caselle diventano rettangolari; volendo, la puoi allungare,
invece di allargarla...
adesso immagina due scacchiere che abbiano risoluzioni qualsiasi
(diverse tra loro); le scacchiere sono trasparenti, ma le linee che
delimitano le caselle sono colorate; diciamo che la prima ha linee
rosse e la seconda blu;
ora immagina di sovrapporre le due diverse scacchiere; dato che hanno
dimensioni diverse, la sovrapposizione e' imprecisa, pero'...
siccome sono di materiale flessibile, una delle due la puoi allungare
e/o accorciare lungo le due direzioni in modo che la sovrapposizione
sia perfetta; mi hai seguito? :-)
a questo punto, cosa vedi?
vedi delle linee rosse e delle linee blu che si incrociano;
se scegli una casella a caso della seconda scacchiera, guardando le
linee che la delimitano puoi individuare un insieme ben preciso di
caselle della prima scacchiera, che sono solo quelle necessarie per
coprire interamente la sua area...
puo' darsi che tale insieme comprenda una sola casella, oppure due,
oppure 4 (3 non e' possibile), oppure 6, 8, e cosi' via;
ciascuna di tali caselle concorre a coprire l'area della casella
considerata di una certa percentuale; la somma di tutte le percentuali
e' ovviamente 100;
ecco, la mia (banale) idea e' quella di definire il colore di tale
casella come la combinazione lineare dei colori delle caselle
dell'insieme che ho detto sopra, dove ciascun coefficiente e' il
corrispondente valore percentuale...
questa spiegazione che ho scritto qua sopra e' la piu' semplice che
posso dare; naturalmente l'algoritmo e' un po' piu' difficile da
capire perche' il calcolo degli insiemi e dei coefficienti non e'
proprio immediato.
l'algoritmo e' semplice e carino, ma c'e' un piccolo problema
dovuto al fatto che le combinazioni lineari vanno poi approssimate
con valori interi... ed e' qui che c'e' una perdita di informazione
che e' responsabile del fatto che, applicando l'algoritmo
all'indietro (cioe' tornando dalla seconda scacchiera alla prima)
non si ottiene esattamente l'immagine iniziale; ovviamente cio'
dovrebbe accadere solo in caso di "upscaling" (cioe', se siamo
passati a un numero maggiore di caselle); in caso di "downscaling"
una perdita di informazione e' gia' messa in conto (una qualsiasi
funzione che mappa un insieme finito in un insieme avente un
minor numero di elementi non puo' essere iniettiva; in parole piu'
semplici, due immagini diverse, ma aventi la stessa risoluzione,
verranno scalate alla stessa immagine, avente minore risoluzione);
a suo tempo feci varie prove, e in caso di "upsampling" riottenni
esattamente l'immagine di partenza (oppure una immagine che
differiva in alcuni pixel, al massimo di una unita' per ciascuna
componente di colore; avevo interpretato questa cosa come
"fisiologica", nel senso che era dovuta al fatto che i tre livelli
di colore calcolati dovrebbero restare razionali, e invece vengono
arrotondati all'intero piu' vicino...); adesso pero', l'applicazione
iterata dell'algoritmo ha messo in luce una perdita di informazione
che non mi aspettavo... avro' modo ci pensarci..
per stasera e' tutto :-)

 spiego per bene come funziona (e' semplice!)
non sono un esperto di algoritmi per il resize e non mi serve capire come
funziona. Mi interessano i risultati. 
Visto che i risultati del tuo test evidenziano le buone caratteristiche del
tuo resize sotto il punto di vista cromatico, mi interessava capire come
sono le altre caratteristiche. 

Ti ho letto con interesse, come sempre, del resto. Però adesso sono stanco
e non mi fa voglia di risponderti. Lo farò quanto prima, scusami.
Bye


 e non mi fa voglia di risponderti. Lo farò quanto prima, scusami.
non c'e' bisogno di scusarti, non c'e' nessun obbligo, per fortuna :-)
anch'io vorrei fare un numero pazzesco di cose, ma poi finisco per
dover scegliere...

 interessava capire come sono le altre caratteristiche.
anche a me :-)
se mi aiuti a fare tali test te ne saro' molto grato
ciao

 se mi aiuti a fare tali test te ne saro' molto grato
io i test li farei volentieri (appena ho un po' di tempo) il problema è che
non so come utilizzare il tuo algoritmo assieme alla codifica di un dvd.
Bisognerebbe creare un filtro di avisynth, ma non ho idea se la cosa è
fattibile oppure è troppo complicata.
Ciao

 per stasera e' tutto :-)
Grande! Me lo sono salvato. Non avevo mai pensato ad un algoritmo di resize
in questo modo.
Ora vò a fare qualche prova con diversi filri di avisynth e poi vi dico i
risultati.
Bye


 accorgersi delle differenze!)
ma se non e' facile accorgersi delle differenze, allora vanno bene
entrambi :-)
insomma, io la penso cosi':
- se ho due possibilita', entrambe richiedono lo stesso tempo, ma una
  da' risultati che mi piacciono di piu', allora scelgo quella;
- se una richiede molto piu' tempo, devo valutare "quanto" mi piacciono
  di piu' i risultati; se non e' facile valutare le differenze, allora
  preferisco quello che ci mette molto meno...
ciao
volevo aggiungere solo una curiosita'.
io credo che il "mio" algoritmo, vista la semplicita', debba per forza
essere arcinoto da decenni nell'ambito della "computer graphics", e
quindi sto cercando di individuare qualcosa che gli assomigli...
poco fa mi sono imbattuto in questo articolo pubblicato nel 1988:
www.ldv.ei.tum.de/media/files/dvi/vorlesung/z03_reconstruction_filters.pdf
Mitchell D.P. and Netravali A.N., "Reconstruction Filters in Computer
Graphics", Computer Graphics, 22(4):221-228, August 1988. 
nella seconda colonna della terza pagina c'e' una funzione (8)... e' lui!!
non il mio, ma "bicubic"! e' la funzione che viene usata per calcolare (per
convoluzione) i pixel dell'immagine scalata nel filtro "bicubic";
forse, allora, l'origine del "bicubic" e' proprio in quell'articolo,
anche perche' il filtro viene anche chiamato "Mitchell-Netravali" (gli
autori dell'articolo);
ah, un'altra curiosita':
sono andato a guardare come funziona lo scaling in una libreria che si
chiama "gdk-pixbuf", e questa offre le seguenti possibilita':
        GDK_INTERP_NEAREST,
        GDK_INTERP_TILES,
        GDK_INTERP_BILINEAR,
        GDK_INTERP_HYPER
l'ultimo viene descritto cosi':
This is the slowest and highest quality reconstruction function. It is
derived from the hyperbolic filters in Wolberg's "Digital Image Warping", and
is formally defined as the hyperbolic-filter sampling the ideal
hyperbolic-filter interpolated image (the filter is designed to be idempotent
for 1:1 pixel mapping).
e questo chi e'?!
qualcuno lo conosce?

 risultati.
bene.
mi sapresti dire dove posso avere dettagli su come venga effettuato il
"test di compressione" di Gordian Knot?

 "test di compressione" di Gordian Knot?
Sinceramente no. E' un test che non mi è mai garbato e non l'ho mai usato.
Però, se conosci il Perl, puoi studuarti i sorgenti di un programma
migliore: enc (
http://jonny.leffe.dnsalias.com/
)
bye


 qualcuno lo conosce?
guarda, io conosco a mala pena i 3 filtri di resize di avisynth e quindi
non posso aiutarti.
Ciao

 migliore: enc (
http://jonny.leffe.dnsalias.com/
)
grazie. ho visto che il codice e' commentato in italiano :-)

 Se vi mette 5 ore al posto di 4 non mi cambia nulla :-)
ah, allora hai ragione :-)
ciao



Eh, so Jonny è Italiano! 


 allo stesso tempo una soluzione comoda; almeno, per me e' cosi'
Questo in linea generale è vero. Se il divx lo fai per te e non ti
interessa molto dello spazio che ti andrà ad occupare puoi benissimo farlo
in un unica passata a q costante = 2. Risparmi tempo e ottieni un risultato
ottimo.
Se però entri nell'ottica che poi il film che rippi lo andrai a condividere
con altre persone tramite il p2p allora dovrai tenere in considerazione due
cose:
1) che meno spazio occupa il film prima lo si scarica... quindi occorre
ottimizzare il rapporto tra compressione e qualità delle immagini
2) non tutti hanno il masterizzatore dvd e per convenzione ormai tutti i
lavori che si mettono in condivisione devono essere multipli di un cd (700
MB). Quindi se è possibile Si fa il film su un cd da 700 MB con audio mp3,
altrimenti se il film proprio non ci sta su un cd oppure il film è davvero
bello che merità la massima qualità, allora si passa a 2 cd (1400 MB) e
molto probabilmente ci sta dentro anche l'aludio AC3 e la seconda traccia
audio mp3 della lingua originale.
Questo è il motivo per cui il test di compressione va sempre fatto, perchè
si vuole creare un lavoro grande esattamente un cd o 2 cd sfruttando al
meglio lo spazio a disposizione.
Ripeto, questo solo se poi lo si vuole condividere. Se uno lo fa per se è
liberissimo di utilizzare tutto lo spazio che ritiene necessario.