--- a/doc/memoria.tex Tue Apr 08 22:24:24 2008 +0200
+++ b/doc/memoria.tex Thu Nov 27 19:14:32 2008 +0000
@@ -27,7 +27,8 @@
\newcommand{\decimal}[1]{\sepnum{,\!}{.}{}{#1}}
-\newcommand{\revisar}[1]{\marginpar{\scriptsize #1}}
+%\newcommand{\revisar}[1]{\marginpar{\scriptsize #1}}
+\newcommand{\revisar}[1]{}
\newcommand{\figura}[2]{
\begin{figure}[!htp]
@@ -57,10 +58,10 @@
La codificació d'imatges JPEG ofereix unes imatges bastant fidels amb molt pocs
bits per pícsel, reduint en bona mesura la mida dels fitxers d'imatge i els
-seus temps de transferència per Internet. Per això ha estat molt popular en la publicació d'imatges
+seus temps de transferència per xarxa. Per això ha estat molt popular en la publicació d'imatges
per Internet, i ho continua sent en l'ambient domèstic degut a les càmeres
-digitals. Per
-tant, qualsevol esforç a millorar la descodificació d'aquestes imatges té molt
+\revisar{sent o essent?}
+digitals. Així doncs, creiem que qualsevol esforç a millorar la descodificació d'aquestes imatges té molt
valor.
Ens hem decidit a analitzar i recopilar les nombroses tècniques
@@ -98,14 +99,14 @@
també es va decidir un
format de fitxer que contindria la informació codificada
(JFIF - JPEG File Interchange Format), ja que en informàtica sovint convé
-conservar informació en fitxers. Aquest format de fitxer permetia especificar-hi
+conservar informació en fitxers. Aquest format de fitxer permetia especificari
diferents espais de
-color al JPEG, i el delmat d'alguns dels plans.
+color pel JPEG, i el delmat d'alguns dels plans.
Amb les càmeres digitals que directament
conservaven les fotografies en JPEG i en fitxers, es va creure que la informació
que permetia conservar el JFIF no era suficient. Va aparèixer l'EXIF, que
-permet conservar molta més informació de les circumstàncies de la fotografia
-(estat de la càmera, sensors, etc.). La majoria de gent sol anomenar els
+permet conservar en un fitxer molta més informació de les circumstàncies de la fotografia
+(estat de la càmera, sensors, etc.), a més de la codificació JPEG. Molta gent sol anomenar els
contenidors JFIF i EXIF indistintament ``Fitxers JPEG'',
o bé amb la reducció a tres lletres obligada sota sistemes MS-DOS,
``Fitxers JPG''.
@@ -119,10 +120,12 @@
La imatge original, prèvia a codificar, la trobem definida amb un mapa de
bits. Això significa que tenim la imatge dividida en espai, amb una malla
-quadriculada de punts de color. Cada punt (pícsel, píxel, pel, de \emph{picture
+\revisar{exemple de mapa de bits?}
+quadriculada de punts de color. Cada punt (pícsel, píxel, pel, de l'anglès
+\emph{picture
element}) ens defineix el color en aquell lloc de la quadrícula. Si tenim una
-quadricula de punts suficientment densa, a ull nu no podrem distingir-la.
-i el conjunt li semblarà una imatge de color contínua o de to continu --
+quadricula de punts suficientment densa, a ull nu no podrem distingir-la
+i el conjunt semblarà una imatge de color contínua o de to continu --
sobretot
en el cas de que la imatge sigui d'origen fotogràfic, en comptes de generada
artificialment.
@@ -132,11 +135,12 @@
no fidel, de la original. Si tenim la imatge codificada amb els plans de color
Vermell-Verd-Blau (RGB), amb 8 bits per punt i component, tenim una densitat
d'informació de 24 bits per punt (bpp). Amb la compressió JPEG podem arribar a
-relacions de 1,5 bpp sense escatimar en qualitat d'imatge. En el cas de tenir el
+relacions de 1,5 bpp sense escatimar gaire en qualitat d'imatge. En el cas de tenir el
mapa de bits a partir d'una fotografia, almenys a una densitat de pícsels de 72
ppi (72 pícsels per polzada) en horitzontal i vertical, el nostre sistema
de visió en prou
feines pot distingir la pèrdua de definició del JPEG a 1,5 bpp.
+\revisar{exemple d'aquestes poques pèrdues}
En el procés de codificació (o compressió) JPEG, es llença part de la informació
del mapa de bits original. Això vol dir que en el procés de descodificació
@@ -167,7 +171,7 @@
banda dels primers anys de l'Internet popular, van fer que la gent publiqués les
seves fotografies en aquest format. Els límits en espai d'emmagatzematge també
van causar que la gent conservés les fotografies només en aquest format. Aquesta
-corrent continua fins ara, tot i que els amples de banda i l'espai per
+corrent continua fins ara. Tot i que els amples de banda i l'espai per
emmagatzemar informació han augmentat, la quantitat de fotografies
intercanviades i conservades també ha augmentat. Amb l'arribada dels escànners i
les càmeres digitals a l'ús domèstic, el públic adquireix cada vegada més
@@ -178,12 +182,13 @@
artificials, que no són de to continu, simplement pel costum de veure les
sigles JPEG arreu associades a imatges i a alta densitat d'informació.
-El comitè de JPEG a l'any 2000 va crear un nou format d'imatge que pretén oferir
+El comitè de JPEG l'any 2000 va crear un nou format d'imatge que pretén oferir
millor densitat d'informació que el JPEG, però malgrat que han passat set anys
-des de la seva definició, no ha guanyat popularitat. Parlant exclusivament de la
-codificació d'imatges de to continu, el comitè garanteix que no està subjecte a
-patents. Però la seva implementació lliure més popular,
-\texttt{jasper}\footnote{\url{http://www.ece.uvic.ca/~mdadams/jasper/}}
+des de la seva definició, no ha guanyat prou popularitat com per substituir el
+JPEG de 1992. Parlant exclusivament de la
+codificació d'imatges de to continu, el comitè garanteix que el JPEG 2000 no està subjecte a
+patents, però la seva implementació lliure més popular,
+\texttt{jasper}\footnote{\url{http://www.ece.uvic.ca/~mdadams/jasper/}},
conté molt de càlcul i ús de memòria, fins i tot pels ordinadors
personals actuals. Tampoc hi ha implementacions en maquinari per part dels
fabricants de càmeres digitals. Tanmateix, per posar un exemple popular, el
@@ -191,17 +196,18 @@
programari Adobe Acrobat\reg des de la versió 6 suporta la
codificació JPEG2000 dins
el seu format PDF 1.5. La majoria d'aplicacions d'Adobe, en la seva versió
-actual, suporten el format. D'acord amb experts en el camp de fotografia, per
-això, per a densitats d'informació similars, opinen que JPEG encara els dóna
+actual, suporten el format. D'acord amb alguns experts en el camp de fotografia,
+per això, per a densitats d'informació similars, opinen que el JPEG original
+encara els dóna
una versió de la imatge més agradable, especialment en zones de textures d'alta
freqüència.
Així doncs, ara per ara trobem arreu imatges codificades en JPEG. És probable
que d'una fotografia digital que ens interessa, només tinguem accés a la seva
-codificació JPEG. Això els el que ha motivat aquest treball, i per això
+codificació JPEG. Això és el que ha motivat aquest treball, i per això
perseguim la millor descodificació JPEG possible. Ja des dels inicis de l'ús del
JPEG que s'han proposat mètodes per a descodificar millor les imatges; mètodes
-complexes computacionalment, però que oferien resultats millors que la
+complexes computacionalment, però que ofereixen resultats millors que la
descodificació convencional. De tota manera, pràcticament cap d'aquests mètodes
s'ha popularitzat, i en prou feines n'existeix alguna aplicació més enllà de
l'article publicat en una revista científica. En aquest treball hem procurat
@@ -216,12 +222,12 @@
\section{Les pèrdues al JPEG}
\label{sec:perdues}
-El procés de codificació segueix els següents passos:
+El procés de codificació segueix els següents passos, que més endavant expliquem amb més detall:
\begin{compactenum}
-\item Dividir la imatge en plans de color.
-\item Delmar alguns plans, si d'ells acceptem menys detall. Aquí tenim la
+\item Dividim la imatge en plans de color.
+\item Delmem alguns plans, si d'ells acceptem menys detall. Aquí tenim la
primera pèrdua d'informació important.
-\item Dividir cada pla resultant en blocs de 8x8 pícsels.
+\item Dividim cada pla resultant en blocs de 8x8 pícsels.
\item Fem la transformada DCT (Apèndix \ref{sec:dct}) de
dues dimensions a cada bloc, i així n'obtenim
la seva representació freqüencial en 64 coeficients.
@@ -235,9 +241,9 @@
DJVU, etc.).
\end{compactenum}
-\noindent La descodificació, anàlogament:
+\noindent La descodificació, anàlogament, podem dividir-la en aquests passos:
\begin{compactenum}
-\item S'obté el paquet de dades JPEG del seu contenidor.
+\item Obtenim el paquet de dades JPEG del seu contenidor.
\item Recuperem els valors dels coeficients quantitzats del paquet (que havíem
guardat sense pèrdues).
\item Desquantitzem els coeficients, decidint-ne un valor concret dins de
@@ -249,7 +255,7 @@
reescalar els plans delmats a la seva dimensió original.
(Aquí el descodificador també ha
d'inventar els nous punts al escalar la imatge)
-\item Ja tenim una versió dels tres plans que determinaven la imatge.
+\item Ja tenim una versió dels tres plans que determinaven la imatge, i podem entregar-la a qui l'hagi demanada.
\end{compactenum}
@@ -257,38 +263,35 @@
\label{sec:plans-color}
Les nostres pantalles solen utilitzar tres plans per a determinar la imatge a
-mostrar en color: vermell, verd i blau. El nostre ull és bastant sensible a
-qualsevol variació en aquests plans - precisament són els colors que els nostres
-cons distingeixen millor. Les freqüències de llum concretes s'avenen amb les de
-màxima sensibilitat pels nostres tres cons, de manera que amb la pantalla es
+mostrar en color: vermell, verd i blau. No generen qualsevol color de l'espectre, sino només punts d'aquests tres colors, cadascun amb intensitat variable.
+Les freqüències de llum dels tres colors s'avenen amb les de
+màxima sensibilitat dels nostres tres cons més importants,
+de manera que la pantalla
produeix, pràcticament, l'excitació independent dels nostres cons, donant la
sensació d'un espai de color continu (\cite{eyeandbrain}).
Un color groc, per exemple, degut a les
respostes freqüencials dels cons, excita parcialment el con vermell
i el con verd.
-La pantalla enganya els cons, excitant concretament una mica els vermell,
-i també una mica els verd.
+La pantalla enganya els cons, excitant concretament una mica els del vermell,
+i també una mica els del verd. Els colors de blanc a negre es produeixen amb igual intensitat de llum vermella, verda i blava.
+\revisar{Imatge de la resposta dels cons}
-El nostre ull distingeix variacions d'intensitat de llum millor que variacions
-de color.
-Defectes en els plans RGB portarien a variacions d'intensitat
-de llum fàcilment distingibles, ja que el nostre cervell considera, amb
-suficient il·luminació, la intensitat de llum una mitjana de l'excitació de cons.
-En canvi, el cervell no distingeix gaire bé variacions de color en espai. Per
-això, típicament els plans RGB es converteixen mitjançant unes regles
-matemàtiques a tres nous plans que defineixen igualment la imatge: intensitat de
-llum, blavor i vermellor (YCbCr)\index{YCbCr}.
+En el cas d'imatges en blanc i negre, d'un únic pla, l'etapa dels plans de color no participa en la codificació. En canvi, les imatges en color consisteixen en múltiples plans, com els de les pantalles, que les següents etapes tractaran de manera indepedent.
+El JPEG consisteix en una compressió d'imatges amb pèrdues, que introduirà defectes a les imatges que codifiquem. Volem que el sistema nerviós humà distingeixi poc
+aquests defectes, i veurem com una reorganització de la informació dels plans ens pot ajudar a aquest efecte.
+El nostre sistema nerviós distingeix variacions d'intensitat de llum millor que variacions
+de color, i en els plans RGB cada un porta una mica d'informació de la intensitat de llum. Hauríem d'introduir pocs defectes a cada pla, per a que el cervell en prou feines els distingís.
+De tota manera, hi ha una transformació de color que ens ajuda a distribuir la informació de la imatge en plans més útils. Els plans RGB es poden convertir mitjançant unes regles matemàtiques a tres nous plans que defineixen igualment la imatge: intensitat de
+llum, blavor i vermellor (YCbCr)\index{YCbCr}. Així tenim la informació separada en plans que el nostre cervell considera de manera diferent. Ara podem llençar molta informació dels plans de color (Cb i Cr), més que no pas podríem llençar dels plans RGB originals, si ho comparem en termes de percepció visual.
\figura{rapids-nens-rgb2ycc.pdf}{
\label{fig:cb-rgb2ycc} Plans RGB, i els anàlogs en YCbCr}
Quan parlem d'imatges amb formes reconeixedores, aquestes formes són molt
-importants a l'hora d'avaluar la percepció de la imatge. En bona part les formes
-vindran determinades per la lluminositat general, i per això l'ull humà el
-considerem
-menys sensible a defectes als plans Cb i Cr (\cite{eyeandbrain}). Per tant, en
-la majoria de codificadors JPEG veurem que aquests plans es delmen i
-es quantitzen a menys qualitat. La majoria
+importants a l'hora d'avaluar la percepció de la imatge. Sovint les formes
+venen molt determinades per la lluminositat general (pla Y), i segurament per això l'ull humà es comporta més sensible als defectes del pla Y que als dels plans Cb i Cr (\cite{eyeandbrain}). En
+la majoria de codificadors JPEG veurem que els plans de color Cb i Cr es delmen i
+les següents etapes els quantitzen a menys qualitat. La majoria
de càmeres digitals delmen per maquinari a 2:1 només en horitzontal, mentre que
molts codificadors per programari delmen a 2:1 tant en horitzontal com en
vertical.
@@ -342,13 +345,12 @@
\subsection{Blocs i quantització dels coeficients}
-La imatge es parteix en blocs de 8x8 pícsels, i cada bloc es codifica de manera
-independent. La informació que es llença s'escull exclusivament en
-relació al bloc i això vol dir que no es té en compte la conservació de
-propietats dels entorns locals dels punts. Degut a això, sovint podem
-distingir molèsties visuals precisament a les vores entre blocs,
-on la informació pertany a dos blocs considerats completament independents pel
-codificador.
+Cada pla de la imatge es parteix en blocs de 8x8 pícsels, i cada bloc es
+codifica de manera independent. La informació es llença per bloc,
+independentment de la informació dels blocs veïns. Degut a això, sovint podem
+distingir molèsties visuals precisament a les vores entre blocs, on la
+informació pertany a dos blocs que el codificador ha considerat
+independentment.
Dels 64 punts d'intensitat de color que determinen cada bloc de 8x8 pícsels
obtenim 64 coeficients mitjançant la transformada DCT 2D (\ref{sec:dct}).
@@ -360,16 +362,16 @@
per cada un dels 64 coeficients. Es sol utilitzar una taula de quantització
diferent per cada pla del JPEG. S'han dut a terme nombrosos experiments per a
decidir quins coeficients són més importants per a degradar mínimament la
-imatge, establint un grau d'importància entre ells.
-En la majoria d'aplicacions que codifiquen imatges en JPEG
-l'usuari té l'opció d'escollir la densitat de la informació codificada.
-No tots els codificadors utilitzen els mateixos patrons de taules de
-quantització. Les càmeres digitals tenen limitacions als algorismes en maquinari,
-els programes de manipulació fotogràfica professionals poden tenir els seus
-propis estudis de les taules de coeficients, i la \texttt{libjpeg}
-\cite{libjpeg} simplement segueix les taules recomanades a
-l'estàndard (\cite{jpegspec}). Podem veure un exemple de quantitzadors
-a la Taula \ref{tab:example-qtable}.
+imatge, establint un grau d'importància entre ells. En la majoria
+d'aplicacions que codifiquen imatges en JPEG l'usuari té l'opció d'escollir la
+densitat de la informació codificada, que consisteix en quantitzar els
+coeficients més o menys, mantenint el grau d'importància entre ells. No tots
+els codificadors utilitzen els mateixos patrons de taules de quantització. Les
+càmeres digitals tenen limitacions als algorismes en maquinari, els programes
+de manipulació fotogràfica professionals poden tenir els seus propis estudis de
+les taules de coeficients, i la \texttt{libjpeg} \cite{libjpeg} simplement
+segueix les taules recomanades a l'estàndard (\cite{jpegspec}). Podem veure un
+exemple de quantitzadors a la Taula \ref{tab:example-qtable}.
\figuraw{13cm}{jpeg-coeficients.pdf}{
\label{fig:jpeg-coeficients} A l'esquerra, funció base de cada
@@ -402,14 +404,14 @@
resultat d'arrodonir la divisió pel quantitzador. El primer coeficient (la
component DC) no es quantitza independentment com els altres, sinó que es
quantitza la diferència amb el primer coeficient del bloc anterior. Per cada un dels 63
-coeficients reals provinents de la transformada DCT 2D ($i = 2,3,\ldots,64$) i
-per la diferència amb la component DC anterior ($i = 1$) obtenim un enter:
+coeficients reals provinents de la transformada DCT 2D ($y_i$, on $i = 2,3,\ldots,64$) i
+per la diferència amb la component DC anterior ($y_1$) obtenim un enter arrodonint:
\[ \hat y_i = \left[ \frac{y_i}{Q_i}\right] , \, i = 1,2,\ldots,64 \]
-La recuperació convencional del coeficient, especificada a l'estàndard
+La recuperació convencional de cada coeficient, especificada a l'estàndard
\cite{jpegspec}, consisteix en multiplicar pel
quantitzador, $ z_i = \hat y_i Q_i $. Podem veure un exemple dels coeficients
-d'un bloc a la Figura \ref{fig:quant-intervals}.De tota manera, a la
+d'un bloc a la Figura \ref{fig:quant-intervals}. De tota manera, a la
descodificació, del coeficient original només sabem que es troba dins
l'\emph{interval de quantització}:
\begin{equation}
@@ -497,7 +499,7 @@
\emph{Mean Opinion Score}).
La literatura de processat d'imatge ens proposa molts mètodes per a determinar
-la fidelitat d'una imatge.
+la fidelitat d'una imatge recodificada.
A \cite{mse2006} podem trobar una bona explicació de
perquè la PSNR encara s'utilitza tant en mesures de qualitat, i una discussió
sobre perquè la PSNR no és adequada per a mesurar la \emph{fidelitat del senyal
@@ -553,11 +555,12 @@
llavors en la majoria dels casos $1 < S < 10$.
\end{itemize}
-El programari vinculat a aquest informe, tot i que ofereix mesures matemàtiques,
-fonamentalment serveix per a permetre comparar imatges a ull nu. Tenim diferents
-mesures per avaluar les restauracions d'imatges JPEG, i per tant ens
-interessa proveir a l'usuari d'un entorn on ell pugui avaluar les imatges segons
-el seu criteri, que segurament serà el més adequat a les seves circumstàncies.
+El programari vinculat a aquest informe, tot i que ofereix algunes de les
+esures matemàtiques presentades (GBIM i PSNR), fonamentalment
+permet comparar còmodament imatges a ull nu. Hem vist que hi ha moltes mesures per
+avaluar les restauracions d'imatges JPEG, i per això no hem dedicat gaire temps
+a implementar-les, prioritzant que l'usuari pugui avaluar les imatges segons el
+seu criteri, que segurament serà el més adequat a les seves circumstàncies.
\chapter{Tècniques}
@@ -573,13 +576,15 @@
\section{Projecció sobre l'espai de quantització}
\label{sec:qcsproject}
-Aquesta tècnica no millora les imatges en si, però sí que la utilitzen a molts
-mètodes. Podem diferenciar els mètodes en dos grans grups: els de \emph{dins la
-cadena de descodificació}, i els de {post-processat}. Els primers consideren
-tota la informació del JPEG, i els segons treballen exclusivament a partir de la
-imatge obtinguda després d'una descodificació convencional. Els primers tenen
-un avantatge clar sobre els altres, ja que poden accedir als intervals de
-quantització, als plans abans de reescalar-los i a la codificació del color.
+
+Aquesta tècnica no millora les imatges en si, però l'expliquem a part perquè
+forma part de molts dels mètodes analitzats. Podem diferenciar els mètodes en
+dos grans grups: els de \emph{dins la cadena de descodificació}, i els de
+{post-processat}. Els primers consideren tota la informació del JPEG, i els
+segons treballen exclusivament a partir de la imatge obtinguda després d'una
+descodificació convencional. Els primers tenen un avantatge clar sobre els
+altres, ja que poden accedir als intervals de quantització, als plans abans de
+reescalar-los i a la codificació del color.
Considerem la descodificació d'un pla del JPEG, no necessàriament amb el mètode
convencional. Si al recodificar el pla amb
@@ -652,7 +657,7 @@
La descodificació convencional d'agafar el punt mig de l'interval de
quantització per cada coeficient compleix la \emph{no destrucció}. Aquest cas
resulta de considerar l'interval com una variable aleatòria
-uniforme. En aquest cas el punt mig és el millor estimador de
+uniforme, on el punt mig és el millor estimador de
la variable.
Alguns articles suggereixen altres distribucions de probabilitat. Per exemple,
@@ -767,7 +772,7 @@
\[ \hat z = \min_{z \in Z} P(z) \]
Essent $P(z)$ derivable \revisar{condicions?},
-podem trobar una funció gradient per acostar-nos a la minimització. A
+podem trobar una funció gradient per acostar-nos al valor mínim . A
\cite{orourke1995} i a \cite{robertson2004} utilitzen un model de camp
aleatori de Huber-Màrkov. A \cite{froment2005} utilitzen una versió adaptada
de la norma de Variació Total (TV).