--- a/doc/memoria.tex Sun Nov 25 19:43:48 2007 +0100
+++ b/doc/memoria.tex Sun Dec 02 17:10:30 2007 +0100
@@ -8,12 +8,13 @@
\usepackage{amssymb}
\usepackage{subfigure}
\usepackage{icomma}
+\usepackage{paralist} % compact enumerations
\usepackage{url}
-\usepackage{makeidx}%,showidx} % This latter shows the indexed in the margin
+%\usepackage{makeidx}%,showidx} % This latter shows the indexed in the margin
\usepackage[margin=1cm,font=footnotesize]{caption}
%\usepackage{a4wide}
-%\usepackage{natbib}
-\bibliographystyle{plain}
+%\usepackage{natbib} No volem referències que no siguin números.
+\bibliographystyle{caplain}
\title{Restauració d'imatges JPEG}
\author{Lluís Batlle}
@@ -48,13 +49,14 @@
\maketitle
\tableofcontents
+% TODO: Remove subsections
+% TODO: Add Bibliography
\chapter{Planetjament del problema}
\section{La codificació JPEG}
-\revisar{Això ve de la Wikipedia. Cal citar-la? Ja la referencio un altre cop
-més tard, pels dibuixos}
+\revisar{Això ve de la Viquipèdia. Cal trobar una font millor.}
El 1986 es va crear un comitè per establir un estàndard de codificació
d'imatges de to-continu (continous tone), per exemple, fotografies. Aquest
comitè tenia el nom de Joint Photographic Experts Group, i el 1992 va aprovar
@@ -64,8 +66,9 @@
(JIF - JPEG Interchange Format).
Aquest primer JIF tenia algunes mancances que al llarg de la història s'han
suplit amb nous formats, com JFIF i EXIF. La majoria de gent sol anomenar-los
-indistintament "Fitxers JPEG", o bé amb la reducció a tres lletres obligada sota
-sistemes MS-DOS, "Fitxers JPG".
+indistintament ``Fitxers JPEG'',
+o bé amb la reducció a tres lletres obligada sota
+sistemes MS-DOS, ``Fitxers JPG''.
Dins l'estàndard s'hi inclouen dues formes diferents de codificar la imatge: amb
pèrdues (\emph{lossy}) o sense (\emph{lossless}). Aquesta última no ha
@@ -78,7 +81,7 @@
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
element}) ens defineix el color en aquell lloc de la quadrícula. Si tenim una
-quadricula de punts suficientment densa, el nostre ull no la distingirà,
+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 --
sobretot
en el cas de que la imatge sigui d'orígen fotogràfic, en comptes de generada
@@ -91,7 +94,8 @@
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
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, l'ull humà mitjà en prou
+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.
En el procés de codificació (o compressió) JPEG, es llença part de la informació
@@ -101,12 +105,14 @@
les implementacions populars de descodificadors JPEG que hem vist
\cite{libjpeg}, la invenció d'informació és molt simple, i no sempre encertada,
considerant que cal obtenir una imatge el més semblant possible a l'original
-d'acord amb els criteris de l'ull humà. En aquest treball analitzarem
+d'acord amb els criteris del nostre sistema visual.
+En aquest treball analitzarem
tècniques que pretenen aprofitar millor la informació del JPEG per a reconstruir
una versió més agradable de la imatge original codificada.
\section{Popularitat}
+\marginpar{Cal fer que es vegi més això de la Popularitat}
Des de l'establiment de l'estàndard JPEG com a norma ISO (10918-1) el 1994, i de
la donació al domini públic de la implementació coneguda amb el nom de
\texttt{libjpeg} \cite{libjpeg}, en versió 5 el mateix any, aquesta codificació
@@ -170,16 +176,15 @@
\section{Les pèrdues al JPEG}
\label{sec:perdues}
-% TODO: mal sangrat
-\revisar{mal sagnat}
+\revisar{mal sagnat?}
El process de codificació segueix els següents passos:
-\revisar{Cal una enumeració compacta}
-\begin{enumerate}
+\begin{compactenum}
\item Dividir la imatge en plans de color.
\item Delmar alguns plans, si d'ells acceptem menys detall. Aquí tenim la
primera perdua d'informació important.
\item Dividir cada pla resultant en blocs de 8x8 pícsels.
-\item Fem la transformada DCT de dues dimensions a cada bloc, i així n'obtenim
+\item Fem la transformada DCT (Apèndix \ref{sec:dct}) de
+dues dimensions a cada bloc, i així n'obtenim
la seva respresentació freqüencial en 64 coeficients.
\item Quantitzem els coeficients. Aquí hi ha la segona pèrdua d'informació
important.
@@ -189,10 +194,10 @@
\item Col·loquem el paquet de dades en un fitxer a part (mitjançant JIF, JFIF,
EXIF, etc.), o bé dins el contenidor que creiem convenient (Postscript, PDF,
DJVU, etc.).
-\end{enumerate}
+\end{compactenum}
\noindent La descodificació, anàlogament:
-\begin{enumerate}
+\begin{compactenum}
\item S'obté el paquet de dades JPEG del seu contenidor.
\item Recuperem els valors dels coeficients quantitzats del paquet (que havíem
guardat sense pèrdues).
@@ -201,12 +206,12 @@
decisions, inventar, el millor possible)
\item Fem la transformada inversa DCT dels coeficients obtinguts, per
arribar a la representació en blocs de mapa de bits de 8x8 pícsels.
-\item Els blocs constitueixen la informació espacial dels plans, i cal reescalar
-
-els plans delmats a la seva dimensió original. (Aquí el descodificador també ha
+\item Els blocs constitueixen la informació espacial dels plans, i cal
+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.
-\end{enumerate}
+\end{compactenum}
\subsection{Plans de color i delmat}
@@ -297,11 +302,11 @@
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 molesties visuals precisament a les vores entre blocs,
-on la informació pertany a dos blocs considerats completmaent independents pel
+on la informació pertany a dos blocs considerats completament independents pel
codificador.
Dels 64 punts d'intensitat de color que determinen cada bloc de 8x8 pícsels
-obtenim 64 coeficients mitjançant la transformada DCT 2D.
+obtenim 64 coeficients mitjançant la transformada DCT 2D (\ref{sec:dct}).
Aquests es solen ordenar en
freqüències de menor a major, utilitzant l'ordre de Zig Zag
(Figura \ref{fig:jpeg-coeficients}) definit a l'estàndard de JPEG.
@@ -347,9 +352,12 @@
\end{table}
La quantització dels coeficients consisteix en conservar només el valor enter
-resultat d'arrodonir la divisió pel quantitzador. Per cada un dels 64
-coeficients reals provinents de la transformada DCT 2D obtenim un enter:
-\[ \hat y_i = \left[ \frac{y_i}{Q_i}\right] , \, i \in 1..64 \]
+resultat d'arrodonir la divisió pel quantitzador. El primer coeficient (la
+component DC) no es quantitza independentment com els altres, sino 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:
+\[ \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
\cite{jpegspec}, consisteix en multiplicar pel
@@ -372,9 +380,10 @@
marca l'ordre de Zig Zag de JPEG. Es poden apreciar els intervals de
quantització, i la pèrdua d'informació sobretot a les freqüències més altes.}
-A la pèrdua d'informació deguda a la quantització se l'anomena
+A la pèrdua d'informació deguda a la quantització dels coeficients, un cop se'ls
+ha aplicat la transformada DCT 2D inversa, se l'anomena
\emph{soroll de quantització}. Té diverses conseqüències visibles a la imatge
-descodificada de manera convencional, i en podem veure una classificació a
+descodificada de manera convencional i en podem veure una classificació a
la Figura \ref{fig:quant-problems}.
\revisar{Cal comentar l'efecte de \emph{suavitzat} del senyal? (menyspreu
d'altes freqüències)}
@@ -387,7 +396,7 @@
(\index{ringing}\emph{ringing})
als blocs que tenen un canvi brusc d'intensitat pel mig,
\subcite{b}d'escala (\index{staircase}\emph{staircase}) i
-\subcite{c}de blocs \index{blocking}\emph{blocking}, entre blocs a les
+\subcite{c}de blocs (\index{blocking}\emph{blocking}), entre blocs a les
superfícies de lluminositat similar. Al mig, el mateix tall de la imatge
original, per comparar.}
@@ -395,7 +404,7 @@
En aquest treball ens proposem millorar la descompressió d'imatges JPEG. Per
tant, cal que definim la qualitat de la imatge resultant d'una manera
-quantitzatble, mesurable.
+quantitzable, mesurable.
Una mesura molt utilitzada,
simplement pel fet de ser purament de teoria del senyal,
@@ -526,9 +535,13 @@
convencional. Si al recodificar el pla amb
les mateixes taules de quantització obtenim la mateixa versió codificada
que de l'original,
-vol dir que hem aplicat una descodificació \emph{no destructiva}.
-Els mètodes de \emph{post-processat} això no poden garantir-ho, ja que
-per començar desconeixen les taules de quantització.\revisar{Citar-ne alguns,
+vol dir que hem aplicat una descodificació \emph{no destructiva}. Els
+coeficients que hem restaurat podrien ben ser de la imatge original, ja que són
+coherents amb la informació del JPEG. Ara bé, com podem veure a la Figura
+\ref{fig:qcs-margins} el marge pot ser bastant gran segons les taules de
+quantització.
+Els mètodes de \emph{post-processat} no poden garantir aquesta coherència amb el
+JPEG ja que desconeixen les taules de quantització. \revisar{Citar-ne alguns,
perquè fan falta.}
Alguns mètodes de descodificació basen la seva estimació d'imatge en
@@ -700,6 +713,8 @@
d'intensitat del pla de lluminositat.
\chapter{Programari}
+% TODO: Add program captures: cadena de descodificació, algunes imatges
+% analitzades
Com hem vist a l'apartat anterior, trobem nombrosos articles sobre la millora de
la descompressió JPEG. Malauradament, no trobem els algorismes implementats en
@@ -986,6 +1001,7 @@
utilitzessin altres configuracions de color.
\chapter{Anàlisi dels mètodes implementats}
+% TODO: one or two draws (logos), taken from webs. Real cases.
Al programa hem donat uns noms als algorismes que hem implementat. A la Taula
\ref{tab:algnames} els teniu tots llistats, i permetran seguir millor els
@@ -1188,11 +1204,53 @@
\section{Difícil parametrització}
\chapter{Conclusions i treball futur}
+% Parlar amb els dels articles
+% Acompliment d'objectius
+% Usuaris contents
+% Futures millores al programa
+% - Publicació, Linux, Mac, Windows
+% - Traducció
+% - Manteniment
+% - Vincles de col·laboració
+% - Atendre recomanacions d'usuaris
\appendix
\chapter{Algorismes en detall}
+\section{Transformada DCT}
+
+\label{sec:dct}
+
+Al codificar els blocs de 8x8 pícsels de cada pla de la imatge, els apliquem una
+transformada que es coneix amb el nom de FDCT (\emph{Forward Discrete Cosine
+Transform}). Donats els 64 valors d'intensitat de cada pícsel, obtenim 64 nous
+valors del domini DCT. El primer d'aquests nous 64 valors l'anomenem el
+coeficient DC (de freqüència zero, component contínua), i els 63 restants
+coeficients AC (de freqüència diferent de zero). Mitjançant la transformada
+IDCT (\emph{Inverse DCT}) podem tornar a recuperar els valors dels pícsels,
+donats els 64 valors del domini DCT. Per a un bloc de pícsels $s_{xy}$
+($x,y=0,1,\ldots,7$), la FDCT està establerta com:
+\[
+S_{uv} = \frac{1}{4} C_u C_v \sum_{x=0}^7 \sum_{y=0}^7 s_{xy}
+\cos \frac{(2x+1)u\pi}{16}
+\cos \frac{(2y+1)v\pi}{16}
+\]
+donant els 64 valors del domini freqüencial $S_{uv}$
+($u,v=0,1,\ldots,7$) i la IDCT com:
+\[
+s_{xy} = \frac{1}{4} C_u C_v S_{uv} \sum_{x=0}^7 \sum_{y=0}^7
+\cos \frac{(2x+1)u\pi}{16}
+\cos \frac{(2y+1)v\pi}{16}
+\]
+on
+\[
+C_m = \begin{cases}
+ \frac{1}{\sqrt{2}} & \text{si} \, m = 0 \\
+ 1 & \text{altrament}
+ \end{cases}
+\]
+
\section{Manteniment de textures}
\label{sec:hcontrast} La majoria dels mètodes de millora de pla estudiats
@@ -1323,7 +1381,7 @@
de lluminostiat més propers), fem la ponderació per aconseguir $Y_o$, aquest copsegons un
paràmetre $\epsilon_v$ també configurable per l'usuari.
-\printindex
+%\printindex
\bibliography{cited}