--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/memoria.tex	Tue Oct 23 16:56:19 2007 +0200
@@ -0,0 +1,217 @@
+\documentclass[catalan,a4paper,titlepage]{article}
+\usepackage{graphicx}
+\usepackage{ucs}
+\usepackage[utf8x]{inputenc}
+\usepackage{babel}
+\usepackage{units}
+\usepackage{amsmath}
+\usepackage{subfigure}
+
+\title{Restauració d'imatges JPEG}
+\author{Lluís Batlle}
+\date{\today}
+
+\begin{document}
+
+\maketitle
+
+\section{Planetjament del problema}
+
+% Wikipedia
+\subsection{La codificació JPEG}
+El 1986 es va crear un comitè per a 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
+l'estàndard conegut arreu amb el nom de JPEG. Va decidir tant la
+codificació de la imatge, efectivament amb les sigles del grup, i també un
+format fitxer que contindria la informació (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".
+
+Dins l'estàndard s'hi inclouen dues formes diferents de codificar la imatge: amb
+pèrdues ({\em lossy}) o sense ({\em lossless}). Aquesta última no ha esdevingut
+popular, i segurament qualsevol imatge JPEG que trobem haurà estat codificada
+amb pèrdues. D'ara en endavant parlarem exclusivament de la compressió amb
+pèrdues.
+
+La imatge original, prèvia a codificar-la, 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 {\em 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à,
+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
+artificialment.
+
+La codificació JPEG, mitjançant les pèrdues i diversos sistemes de compressió de
+dades, permet convertir el mapa de bits a una representació més densa, tot i que
+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 per 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
+mapa de bits a partir d'una fotografia, almenys a una densitat de pícsels de 72
+ppi (72 pícsels per pulgada) en horitzontal i vertical, l'ull humà 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ó
+del mapa de bits original. Això vol dir que en el procés de decodificació
+tindrem només part de la informació de la original, i que per a construir una
+nova imatge sencera, el decodificador s'ha d'inventar la part que falta. En
+totes les implementacions populars de decodificadors JPEG que hem vist (ref
+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
+tècniques que pretenen aprofitar millor la informació del JPEG per a reconstruir
+una versió més agradable de la imatge original codificada.
+
+\subsection{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} (ref libjpeg), en versió 5 el mateix any, aquesta codificació
+ha esdevingut molt popular. Als inicis d'internet, JPEG oferia la major densitat
+d'informació per a transmetre fotografies. La publicació de l'estàndard va
+alliberar l'ús de qualsevol restricció per patents, i la velocitat de procés de
+la \texttt{libjpeg} va permetre introduir suport pel format en moltíssimes
+aplicacions dedicades al processament d'imatges, fins i tot en els ordinadors
+personals.
+
+L'alta densitat de la informació JPEG, junt amb les restriccions d'ample de
+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
+emmagatzemar informació han augmentat, la quantitat de fotografies
+intercanviades i conservades també ha augmentat. Amb l'arribada dels escàners i
+les càmeres digitals a l'ús domèstic, el públic adquireix cada vegada més
+imatges, i més grans (més punts al mapa de bits). Des de fa temps hi ha
+implementacions de la codificació JPEG en maquinari, i per exemple la majoria
+de càmeres digitals donen els seus resultats en format JPEG. Fins i tot, per
+desconeixènça, prou gent utilitza aquest format per a guardar imatges
+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 preten 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} (ref
+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
+% ref http://lists.brouhaha.com/pipermail/tumble-devel/2004q4/000007.html
+programari Adobe Acrobat 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
+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ò
+perseguim la millor decodificació JPEG possible. Ja des dels inicis de l'ús del
+JPEG que s'han proposat mètodes per a decodificar millor les imatges; mètodes
+complexes computacionalment, però que oferien resultats millors que la
+decodificació 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
+donar una visió global sobre l'estat de l'art en el camp de la decodificació
+JPEG, així com implementar uns quants mètodes convincents, i fer-los públics en
+forma d'una aplicació informàtica. Amb això pretenem fer disponibles els millors
+resultats d'anys de recerca acadèmica als nombrosos usuaris de JPEG. Si bé
+aquesta aplicació ha estat pensada per a versats en el camp de la imatge, hem
+procurat que l'usuari no necessiti coneixements experts de JPEG o de programació
+per a dur a terme les decodificacions.
+
+\subsection{Les pèrdues al JPEG}
+
+El process de codificació segueix els següents passos:
+\begin{enumerate}
+\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
+la seva respresentació freqüencial en 64 coeficients.
+\item Quantitzem els coeficients. Aquí hi ha la segona pèrdua d'informació
+important.
+\item Codifiquem els coeficients quantitzats mitjançant tècniques sense pèrdues,
+i els guardem en un sol paquet de dades. Aquest serà el resultat de la
+codificació JPEG.
+\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}
+
+La decodificació, anàlogament:
+\begin{enumerate}
+\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).
+\item Desquantitzem els coeficients, decidint-ne un valor concret dins de
+l'interval de quantització corresponent. (Aquí el descodificador ha de prendre
+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ó espaial 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}
+
+
+\subsubsection{Plans de color i delmat}
+
+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 a la pantalla es
+produeix, pràcticament, l'excitació independent dels nostres cons, donant la
+sensació d'un espai de color continu. Un color groc, per exemple, degut a les
+responstes freqüencials dels cons, excita parcialment el con blau i el con verd.
+La pantalla enganya els cons, excitant concretament una mica el blau, i també
+una mica el verd. (ref ?)
+
+El nostre ull distingeix variacions d'intensitat de llum millor que variacions
+de color (ref ?). 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 un promig 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).
+
+L'ull humà és menys sensible a defectes als plans Cb i Cr (ref ?), per tant, en
+la majoria de codificadors JPEG veurem que aquests plans es delmen. La majoria
+de càmeres digitals delmen per maquinari a 1:2 només en horitzontal, mentre que
+molts codificadors per programari delmen a 1:2 tant en horitzontal com en
+vertical.
+
+En la decodificació, cal reescalar els plans delmats a la seva mida original,
+mitjançant interpolacions o altres tècniques. Convencionalment (per defecte a
+\texttt{libjpeg}) es fa una interpolació lineal.  I per a suplir la imatge final a la pantalla, cal invertir el canvi de plans de YCbCr a RGB.
+
+\subsubsection{Quantització dels coeficients}
+
+Dels 64 punts d'intensitat de color que determinen cada bloc de 8x8 pícsels
+obtenim 64 coeficients. Aquests es solen ordenar en components relatius en
+freqüències de menor a major. Més o menys, perquè hi ha freqüències de senyal
+verticals i horitzontals en aquesta transformació de dues dimensions.
+
+Les taules de quantització determinen la quantitat d'informació que es llença
+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 establir un grau d'importància
+entre ells. I alhora, s'han establert diferents taules de quantització relatives
+a la densitat d'informació que desitja l'usuari. En els taules de quantització
+sí que difereixen una mica les càmeres digitals, els programes de manipulació
+fotogràfica professionals, i la \texttt{libjpeg} (segons la seva última versió
+de 1998).
+
+En la decodificació 
+
+\end{document}