He fet un títol nou.
\documentclass[catalan,a4paper,titlepage,12pt]{book}
\usepackage{graphicx}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{babel}
\usepackage{units}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{subfigure}
\usepackage{icomma}
\usepackage{paralist} % compact enumerations
\usepackage{url}
%\usepackage{makeidx}%,showidx} % This latter shows the indexed in the margin
\usepackage[margin=1cm,font=footnotesize]{caption}
%\usepackage{a4wide}
%\usepackage{natbib} No volem referències que no siguin números.
\bibliographystyle{caplain}
\setcounter{tocdepth}{1}
% For in-paragraph lists of a), b), c).
\newcommand{\subcite}[1]{\emph{#1)}}
\newcommand{\decimal}[1]{\sepnum{,\!}{.}{}{#1}}
%\newcommand{\revisar}[1]{\marginpar{\scriptsize #1}}
\newcommand{\revisar}[1]{}
\newcommand{\figura}[2]{
\begin{figure}[!htp]
\centering
\includegraphics[width=13cm]{#1}
\caption{#2}
\end{figure}
}
\newcommand{\figuraw}[3]{
\begin{figure}[!htp]
\centering
\includegraphics[width=#1]{#2}
\caption{#3}
\end{figure}
}
\newcommand{\reg}{$^\text{\textregistered}$}
\makeindex
\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}
\begin{document}
\begin{titlepage}
\begin{center}
\textsc{\Large Universitat Politècnica de Catalunya}\\[2cm]
\textsc{\Large Escola Tècnica Superior d'Enginyeria de Telecomunicació de Barcelona}\\[2cm]
\textsc{\large Projecte de Fi de Carrera}\\[2cm]
\HRule\\[0.4cm]
{\huge \bfseries Restauració d'imatges JPEG}\\[0.4cm]
\HRule\\[3cm]
%% Author and supervisor
\begin{minipage}{0.4\textwidth}
\begin{flushleft} \large
\emph{Autor:}\\
Lluís \textsc{Batlle i \\ Rossell}
\end{flushleft}
\end{minipage}
\begin{minipage}{0.4\textwidth}
\begin{flushright} \large
\emph{Director:}\\
Dr. Josep M. \textsc{Aroca i \\ Farrerons}
\end{flushright}
\end{minipage}
\vfill
% Bottom of the page
{\large \today}
\end{center}
\end{titlepage}
\tableofcontents
% TODO: Remove subsections
\chapter*{Introducció}
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 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
\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
de restauració de JPEG aparegudes a diferents publicacions científiques. Alhora,
hem creat una aplicació informàtica lliure que implementa alguns dels algorismes
més interessants de la nostra cerca, a més d'establir una base per al
desenvolupament d'aquest tipus de tècniques.
Mitjançant aquest informe i el programa informàtic desenvolupat en paral·lel
introduïm al lector al món de la pèrdua d'informació JPEG, donem a conèixer
l'estat de l'art de la seva restauració, i proveïm als
manipuladors d'imatges (de centres fotogràfics, d'impressió, etc.) amb
les tècniques més prometedores d'aquest camp. Portem les idees de les
publicacions científiques de laboratori als
ordinadors personals de cases i centres de fotografia.
Al llarg del document trobarem vàries imatges exemplificant soroll i
restauracions, algunes d'elles difícils d'apreciar amb una impressora làser
convencional. Per això us remetem a la versió electrònica d'aquest document per
a poder apreciar les diferències entre imatges en detall.
\chapter{Plantejament del problema}
\section{La codificació JPEG}
\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 la ISO i el
CCITT van aprovar
l'estàndard conegut arreu amb el nom de JPEG (ISO/IEC IS 10918-1 - ITU-T
Recommendation T.81)\footnote{\url{http://www.jpeg.org/jpeg/index.html}}.
Van decidir tant la
codificació de la imatge, efectivament amb les sigles del grup, i en paral·lel
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 especificari
diferents espais de
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 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''.
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
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 trobem definida amb un mapa de
bits. Això significa que tenim la imatge dividida en espai, amb una malla
\revisar{exemple de mapa de bits?}
quadriculada de punts de color. Cada punt (pícsel, píxel, \emph{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 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.
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 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 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ó
tindrem només part de la informació original, i que per construir una
nova imatge sencera, el descodificador s'ha d'inventar la part que falta. A
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 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}
\revisar{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ó
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 moltes
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ànners 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
desconeixenç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 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 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
% ref http://lists.brouhaha.com/pipermail/tumble-devel/2004q4/000007.html
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 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ò é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 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
donar una visió global sobre l'estat de l'art en el camp de la descodificació
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 descodificacions.
\section{Les pèrdues al JPEG}
\label{sec:perdues}
El procés de codificació segueix els següents passos, que més endavant expliquem amb més detall:
\begin{compactenum}
\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 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.
\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{compactenum}
\noindent La descodificació, anàlogament, podem dividir-la en aquests passos:
\begin{compactenum}
\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
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ó espacial dels plans, i cal
interpolar 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, i podem entregar-la a qui l'hagi demanada.
\end{compactenum}
\subsection{Plans de color i delmat}
\label{sec:plans-color}
Les nostres pantalles solen utilitzar tres plans per a determinar la imatge a
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 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}
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{flors-rgb2ycc.pdf}{
\label{fig:cb-rgb2ycc} Plans RGB i YCbCr d'una imatge en color.}
Quan parlem d'imatges amb formes reconeixedores, aquestes formes són molt
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.
\figura{flors-cb-rescale.pdf}{\label{fig:cb-rescale}Delmat
2:1 en horitzontal i vertical del pla Cb, i posterior
interpolació lineal de la versió delmada.}
A la descodificació, cal interpolar els plans delmats a la seva mida original,
mitjançant interpolacions o altres tècniques. Convencionalment (per defecte a
la \texttt{libjpeg} \cite{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.
El delmat dels plans de color provoca una incomoditat visual sovint detectable a
les imatges JPEG descodificades: el \emph{vessament de color} (\emph{color
bleeding}). A la Figura \ref{fig:house-bleeding} podem veure'l.
\figura{house-bleeding.pdf}{
\label{fig:house-bleeding} A l'esquerra, l'original. Al mig, JPEG amb màxima
qualitat al pla de lluminositat, i qualitat 40 de \texttt{libjpeg} als plans de
color, amb delmat 2x2:1x1:1x1 (als dos plans de color la meitat de punts en
horitzontal i vertical que al pla de lluminositat). Es pot apreciar el vessament
de color sobre les finestres. A la dreta, JPEG amb la mateixa codificació per
plans, però sense delmar els plans de color. Ja no s'hi aprecia tant el
vessament.}
\begin{table}[!htp]
\centering
\begin{tabular}{|c|c|p{9cm}|}
%\hline
%{\bfseries 4:x:y} & {\bfseries Y,Cb,Cr} &
%{\bfseries Significat} \\
%\hline
\hline
4:4:4 & 1x1,1x1,1x1 & Igual resolució de lluminositat i color \\
\hline
4:2:2 & 2x1,1x1,1x1 & La meitat de punts de color en horitzontal \\
\hline
4:2:0 & 2x2,1x1,1x1 & La meitat de punts de color en horitzontal, i la meitat
en vertical \\
\hline
4:1:1 & 4x1,1x1,1x1 & Un quart de punts de color en horitzontal \\
\hline
\end{tabular}
\caption{\label{tab:notacions}Notacions pels delmats dels canals de color
per a les components YCbCr. La segona és típica de les càmeres digitals, i la
tercera, el delmat per defecte al guardar imatges a diversos programes
informàtics.}
\end{table}
\subsection{Blocs i quantització dels coeficients}
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 (Apèndix \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.
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 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, 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
coeficient de la DCT 2D. Al mig, contribució parcial dels coeficients de la DCT;
cada bloc s'ha reconstruït considerant nuls els coeficients de més altes
freqüències. A la dreta, la serialització dels coeficients en Zig
Zag (\cite{jpegspec}, 4.3). Les imatges primera i tercera les hem obtingut
de la Viquipèdia \cite{wiki:jpeg}.}
% Taula de quantització
\begin{table}[!htp]
\centering
{ \footnotesize
\begin{tabular}{ccccccccc}
80 & 55 & 50 & 80 & 120 & 200 & 255 & 305 \\
60 & 60 & 70 & 95 & 130 & 290 & 300 & 275 \\
70 & 65 & 80 & 120 & 200 & 285 & 345 & 280 \\
70 & 85 & 110 & 145 & 255 & 435 & 400 & 310 \\
90 & 110 & 185 & 280 & 340 & 545 & 515 & 385 \\
120 & 175 & 275 & 320 & 405 & 520 & 565 & 460 \\
245 & 320 & 390 & 435 & 515 & 605 & 600 & 505 \\
360 & 460 & 475 & 490 & 560 & 500 & 515 & 495
\end{tabular}
}
\caption{\label{tab:example-qtable} Taula de quantització pel pla d'intensitat
de llum segons la \texttt{libjpeg} \cite{libjpeg} a qualitat 30},
$Q_i , \, i = 1,2,\ldots,64$ segons l'ordre de Zig Zag.
\end{table}
La quantització dels coeficients consisteix en conservar només el valor enter
resultat d'arrodonir la divisió pel quantitzador. El primer coeficient (la
component contínua 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 AC 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 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
descodificació, del coeficient original només sabem que es troba dins
l'\emph{interval de quantització}:
\begin{equation}
\label{eqn:quant-intervals}
y_i \in Q_i \left[ \hat y_i - 0,5 \, , \,
\hat y_i + 0,5 \right]
\end{equation}
\figura{block16x16simple.pdf}{
\label{fig:quant-intervals} Coeficients del bloc situat a la fila 17,
columna 17, del pla de lluminositat de la Lena de 256x256,
amb una compressió a qualitat 30
segons la \texttt{libjpeg} \cite{libjpeg}. Estan ordenats de menor a
major freqüència, com
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ó 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
la Figura \ref{fig:quant-problems}.
\figura{lena-blocking.pdf}{
\label{fig:quant-problems} A l'esquerra, pla de lluminositat de la Lena de 256x256 pícsels, a
qualitat 40 segons la \texttt{libjpeg}. A la dreta, tall on podem veure els
efectes
\subcite{a}d'ones
(\index{ringing}\emph{ringing})
als blocs que tenen un canvi brusc d'intensitat pel mig,
\subcite{b}de blocs (\index{blocking}\emph{blocking}), entre blocs a les
superfícies de lluminositat similar, i
\subcite{c}d'escala (\index{staircase}\emph{staircase}), quan apareixen graons a
una zona de canvi d'intensitat. Al mig, el mateix tall de la imatge original, per comparar.}
\chapter{Qualitat de les imatges}
En aquest treball ens proposem millorar la descompressió d'imatges JPEG. Per
tant, cal que considerem quantificar la qualitat de la imatge resultant.
Una mesura molt utilitzada,
simplement pel fet de ser purament de teoria del senyal,
és l'\emph{error quadràtic mitjà}
(\index{MSE}~MSE - \emph{Mean Squared Error}, \cite{comphandbook_mse}). Aquesta mesura ens permet comparar imatges
descodificades amb la versió original.
Per cada pla de la imatge que ens interessi, considerem error la diferència
entre cada punt de la imatge original i el punt equivalent de la versió
descodificada. Així, per una imatge original de $M$ columnes i $N$ files,
\[ MSE = E \left[ (x - \hat x)^2 \right] = \frac{1}{M\,N} \sum_{m=1}^M \sum_{n=1}^N (x_{m,n} - \hat x_{m,n})^2
\]
on $x_{m,n}$ representa la intensitat d'un punt de la imatge original, i $\hat
x_{m,n}$ l'anàleg de la versió descodificada.
Als articles que fan referència a comparació d'imatges amb l'objectiu de mesurar
la similitud encara es fa servir més una funció de l'MSE, la \emph{relació senyal
soroll de pic} (PSNR \index{PNSR}\label{sec:psnr}
-- \emph{Peak Signal-to-Noise Ratio}),
que es sol expressar en decibels i es defineix així:
\[ PSNR = 10 \log_{10} \frac{255^2}{MSE} \]
A molts articles on proposen mètodes per millorar la descompressió JPEG
justifiquen les millores amb un augment de la PSNR respecte a la descodificació convencional.
A la pràctica,
la PSNR es considera una mesura adequada quan es comparen imatges
codificades a alta qualitat. En general, la PSNR mesura bé l'error percebut
quan no hi ha gaires diferències a zones d'altes freqüències. Concretament,
nosaltres no distingim gaire els desfasaments a altes freqüències, i en canvi la
PSNR és molt sensible a desfasaments. En podem veure un exemple a la Figura
\ref{fig:psnr-highfreq}.
\figuraw{5cm}{bwlines.pdf}{\label{fig:psnr-highfreq}Aquestes dues imatges
artificials les veiem molt semblants, però una està en contrafase amb
l'altra. En aquest cas, la mesura de PSNR ens donaria un valor molt baix.}
Per altra banda, la mesura de PSNR no es basa en peculiaritats del nostre
sistema de visió, i al cap i a la fi és aquest qui jutjarà les imatges.
Tot i que els judicis depenen de cada individu observador, sí que hi
ha uns patrons comuns al sistema de visió humà (\index{HVS}HVS
-- \emph{Human Vision
System}). Com que volem una mesura
calculable de la qualitat de la imatge, podem aprofitar els resultats de
diverses investigacions que s'han dut a terme sobre aquest tema. Hi ha
un procediment comú a tots els que hem analitzat:
trobar un model matemàtic que doni resultats correlats a
mitjanes d'opinions d'individus (\index{MOS}MOS -
\emph{Mean Opinion Score}).
La literatura de processat d'imatge ens proposa molts mètodes per a determinar
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
visual}.
A \cite{imgq2006} fan una bona revisió de mesures referencials (\index{FR}FR -
\emph{Full-reference}, que
comparen imatges distorsionades amb la seva original) existents,
i a més proposen un nou
\revisar{Cal dir aquí que això no ho hem implementat?}
mètode de mesura amb qualitats interessants sobre la PSNR: el \index{VIF}VIF
(\emph{Visual
Information Measure}). Aquest es basa en jutjar elements rellevants, considerant
estadístiques d'escenes naturals, mitjançant transformades Wavelet dels plans i
l'anàlisi de les subbandes a la imatge de referència i la distorsionada.
Per altra banda, el nostre sistema de visió pot distingir la influència d'una
distorsió
sovint sense haver de comparar amb la imatge original. En el cas concret de la
descodificació JPEG, hi ha diversos mètodes
No-Referencials (\index{NR}NR) proposats. Aquí en citem tres dels més
utilitzats als articles que hem analitzat:
\begin{itemize}
\item \index{MSDS}\emph{MSDS -- Mean Squared Difference of Slope}: proposat a
\cite{msds1995}, aquest mètode pretén mesurar l'efecte de blocs.
Es basa en analitzar les
pendents d'intensitat a les zones entre blocs i a la frontera dels
blocs adjacents. A imatges JPEG d'alta qualitat, el pendent d'intensitat
abans del
límit de bloc, i el d'entre blocs, serà similar. En canvi als JPEG de poca
qualitat, el pendent d'intensitat abans del canvi de bloc serà diferent al que
hi ha entre blocs. Aquestes diferències es sumen, tant les mesurades en
horitzontal com en vertical i en diagonal, per a donar un únic valor NR.
\item \index{GBIM}\emph{GBIM -- Generalized Block-edge Impairment Metric}:
a \cite{gbim1997} proposen mesurar les diferències d'intensitat dels
punts que estan al límit dels blocs consecutius, i comparar-los amb les
diferències d'intensitat de punts que no estan a límits de blocs. Comparteix
objectiu amb l'MSDS,
mesurar l'efecte de blocs, considerant que els canvis bruscs d'intensitat de la
fotografia original en general no coincidiran amb els límits blocs.
\item \emph{jpeg\_score}:
a \cite{jpegscore2002} proposen una mesura similar al \emph{GBIM}, però
que a més té en compte que la imatge ha de tenir \emph{detall} (altes
freqüències). Així doncs, contempla els canvis d'intensitat als punts entre
blocs $B$, els canvis d'intensitat als punts interiors dels blocs $A$, i els
canvis de sentit de la derivada de la intensitat $Z$, independentment dels punts
que tingui la imatge. Llavors, proposen la mesura $S$ amb la següent forma:
\[ S = \alpha + \beta B^{\gamma_1} A^{\gamma_2} Z^{\gamma_3} \]
on els paràmetres $\alpha = -245,9$, $\beta = 261,9$, $\gamma_1 = -0.0240$,
$\gamma_2 = 0.0160$ i $\gamma_3 = 0.0064$ són estimats a partir d'una
correlació entre $S$ i MOS sobre una estadística de 30 imatges originals, 90
versions comprimides i 53 individus. Les MOS estaven acotades entre 1 i 10,
llavors en la majoria dels casos $1 < S < 10$.
\end{itemize}
El programari vinculat a aquest informe, tot i que ofereix algunes de les
mesures 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}
a\label{sec:tecniques}
A l'apartat \ref{sec:perdues} hem explicat quines pèrdues de senyal
trobem al JPEG, i
quins són els marges de llibertat que tenim a l'hora d'intentar recuperar la
imatge original. Des de l'aparició de l'estàndard JPEG que s'han proposat
mètodes per a millorar la descodificació mitjançant algorismes més complexes que
el convencional. Hem procurat estudiar l'estat de l'art del JPEG, i classificar
els mètodes més interessants segons les tècniques en què es basen.
\section{Projecció sobre l'espai de quantització}
\label{sec:qcsproject}
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
d'interpolar-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
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
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ó. Per exemple, amb programes
informàtics
de retoc fotogràfic es sol utilitzar el filtrat
Gaussià selectiu per a eliminar
soroll, entre d'altres, de la descodificació JPEG convencional.
\begin{figure}[!htp]
\centering
\begin{tabular}{ccc}
\includegraphics[width=4cm]{images/lena-40-jpg.png} &
\includegraphics[width=4cm]{images/lenag-40-lowfreq.png} &
\includegraphics[width=4cm]{images/lenag-40-highfreq.png} \\
a) & b) & c)
\end{tabular}
\caption{\label{fig:qcs-margins}\subcite{a}Imatge Lena
codificada a qualitat 40 amb
la \texttt{libqjpeg}, \subcite{b}Descodificació segons els valors absoluts més
baixos dins dels intervals de quantització, \subcite{c}Descodificació segons els
valors absoluts més alts.
}
\end{figure}
Alguns mètodes de descodificació basen la seva estimació d'imatge en
filtres espacials, a vegades fins i tot en
processos iteratius. Per assegurar-se que la seva imatge no divergeix de la
informació del JPEG, duen a terme el que anomenem \emph{projeccions sobre
l'espai de quantització}.
Quan tenen el nou pla espacial estimat, li fan la transformada DCT per blocs de
8x8, com a la codificació JPEG. Els coeficients obtinguts $z_i$ els comparen
amb els
intervals de quantització (eq. \ref{eqn:quant-intervals}), i si se'n surten,
els consideren al límit de
l'interval.
\begin{equation}
z'_i = \begin{cases}
(\hat y_i - 0.5) Q_i & \text{si} \, z_i < (\hat y_i - 0.5) Q_i \\
(\hat y_i + 0.5) Q_i & \text{si} \, z_i > (\hat y_i + 0.5) Q_i \\
z_i & \text{altrament}
\end{cases}
\end{equation}
Aquest mètode també es coneix a la literatura amb el nom de
\index{QCS}\emph{projection to QCS}
(Quantization Constraint Set)\revisar{Hauríem d'introduir QCS abans?} o
\emph{projection to the constraint space},
i s'utilitza als mètodes \cite{froment2005}, \cite{orourke1995},
\cite{robertson2004}, i en general a qualsevol mètode iteratiu dels que hem
vist. \revisar{Per
garantir convergència? Evitar divergència?}
Alguns articles proposen projectar sobre \index{NQCS}NQCS
(\emph{Narrow Quantization
Constraint Set}), que consisteix en agafar un marge més estret que el de $[-0,5,
0,5]$ al voltant del centre de l'interval de quantització. A \cite{liew2004},
per exemple, consideren millors els resultats amb un marge de $[-0,3, 0,3]$.
\section{Coeficients com a variables aleatòries}
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, on el punt mig és el millor estimador de
la variable.
Alguns articles suggereixen altres distribucions de probabilitat. Per exemple,
a \cite{trianta2003} proposen utilitzar una v.a. exponencial, de
mitjana a determinar segons la imatge (veieu la Figura \ref{fig:fexp}).
A \cite{robertson2004},
\cite{trianta2002} i a
\cite{queiroz1998}
mencionen utilitzar una v.a. Laplaciana. El primer, basant-la amb la imatge a
descodificar. El segon, basant-la amb estadístiques d'altres
imatges.\revisar{Com ho fa exactament el primer?}
\begin{figure}[!htp]
\centering
\begin{tabular}{ccc}
\includegraphics[width=4cm]{images/lena.png} &
\includegraphics[width=4cm]{images/lena-40-jpg.png} &
\includegraphics[width=4cm]{images/lenag-40-fexp-1.png} \\
a) & b) & c)
\end{tabular}
\caption{\label{fig:fexp}\subcite{a}Imatge Lena
original, \subcite{b}Descodificació convencional de qualitat 40 segons la
\texttt{libjpeg}, considerant els
intervals com v.a. uniformes, \subcite{c}descodificació de la mateixa imatge
considerant v.a. exponencials de mitjana $\mu = 1$.
}
\end{figure}
\section{Segmentació i suavitzat}
Un dels efectes que més es distingeixen a les imatges codificades amb una
relació de compressió alta (més denses) és el de blocs. A les zones de baixes
freqüències, on en prou feines s'haurien de distingir canvis de lluminositat,
apareixen discontinuïtats segons el patró de blocs del JPEG. El cas més extrem
el trobem quan a zones amb freqüències baixes es conserva només el
coeficient de component contínua (el primer, en ordre Zig Zag).
\revisar{Ho il·lustrem?}
Aquest tipus d'efecte de blocs es pot arreglar amb un simple suavitzat, per
exemple amb un filtre de Gauss. Així, el que fan alguns algorismes
consisteix en distingir les zones de baixes freqüències,
i aplicar-los el suavitzat. A \cite{chen2001},
\cite{alfahoum2001}, \cite{pham2005}, \cite{trianta2003},
utilitzen filtres 2D simples; a \cite{lee1998},
\cite{kim1999} i \cite{queiroz1998} fan servir filtres adaptatius 2D;
a \cite{gao2002} i a \cite{liew2004}
fan servir filtres 1D; i a \cite{liu2002}
fan servir interpolació lineal sobre la component contínua.
Alguns algorismes més complexos suggereixen distingir i processar també
les zones d'altes
freqüències. A \cite{chen2001} i
\cite{liu2002} fan servir un filtre amb molt
poc pes dels punts del voltant; i a \cite{alfahoum2001}, \cite{pham2005} i
\cite{trianta2003} fan servir filtres direccionals.
\section{\index{POCS}POCS - Projecció sobre conjunts convexos}
Els mètodes basats en POCS solen donar molts bons resultats, i apareixen a la
literatura des dels inicis de l'ús del JPEG. Malauradament l'algorisme és
bastant més lent que altres,
ja que consisteix en dur a terme passos iteratius.
Referint-me a l'explicació de POCS de \cite{yang1993}, assumim que
les imatges $f$, representades amb un vector, són elements d'un
espai de Hilbert $H$. Llavors, per qualsevol $f \in H$, la seva projecció $Pf$
en un conjunt tancat convex $C \subset H$ es defineix com l'element més proper a
$f$ dins $C$. Això és:
\[ \| f - Pf \| = \min_{g \in C} \| f - g \| \]
Considerem que la projecció $Pf$ ve determinada exclusivament per $f$ i $C$; o
sigui, per a cada conjunt tancat convex, tenim el seu projector.
Si tenim diversos $C_i \subset H$, $i = 1, 2, \cdots, m$, i igual nombre de
projectors $P_i$ sobre $C_i$, podem veure que per qualsevol imatge inicial $f_0$
podem obtenir una seqüència d'imatges $\{f_k\}$,
\[ f_{k+1} = T_m T_{m-1} \cdots T_1 f_k \]
on $T_i = I + \lambda_i ( P_i - I ), 0 < \lambda_i < 2, i = 1, 2, \cdots, m$.
Aquesta seqüència convergeix al punt
\[ f^* \in C_0 \triangleq \bigcap_{i=1}^{m} C_i . \]
Relacionant POCS amb la millora d'imatges, el que ens cal fer és tenir un
conjunt tancat convex $C_i$ (i el seu projector $P_i$) per cada característica
de la imatge. Llavors, per a $m$ característiques diferents, podem trobar la
imatge $f^*$ que millor les compleix. Iterativament, apliquem tots els
projectors, partint de la primera aproximació $f_0$
a la imatge desitjada. Sovint
aquesta primera aproximació consisteix de la descodificació convencional
\revisar{fer referència a la dec. convencional?} de JPEG.
Els mètodes basats en POCS solen tenir el QCS \revisar{fer-hi referència?} com a
conjunt tancat convex involucrat $C_1$,
i solen presentar només un altre conjunt que els
distingeix dels altres mètodes ($m=2$). A \cite{yang1993} intenten reduir les
discontinuïtats dels punts entre blocs amb $C_2$ i a \cite{weer2002}
utilitzen un $C_2$ basat amb prèvia classificació dels punts en regions
homogènies de la imatge. En canvi, \cite{yang1997} incorpora
fins a sis conjunts per eliminar \emph{l'efecte de blocs} i amb especial
incís \emph{l'efecte d'ones}.
\section{\index{MAP}Maximum A Posteriori}
Aquesta tècnica és similar a la de POCS en els aspectes de que és iterativa, i té projeccions
sobre conjunts convexes. Estrictament, a POCS els mètodes venen
definits pels conjunts convexes involucrats. Amb la tècnica de MAP el que es
busca és la maximització d'una funció determinada, considerant la informació que sabem
de la imatge. Aquesta funció avalua les imatges segons diferents mesures preses de la imatge, i hauria de donar un valor alt per mesures que considerem d'imatge més correcta, i un valor baix per mesures que considerem d'imatge incorrecta. Per exemple, podem establir una mesura de si hi ha poques o moltes diferències entre el color dels pícsels entre blocs. Com més diferències hi hagi entre aquests pícsels, més baix és el valor que retorna la funció.
En el cas del JPEG, l'objectiu és maximitzar la funció sempre i quan mantenim els
coeficients dins els intervals de quantització. Si $\hat z$ és la nostra imatge
estimada a la descodificació, $Z$ és el conjunt d'imatges amb coeficients dins
el QCS, i $P(z)$ una funció que mesura la imatge tal com hem explicat abans:
\[ \hat z = \max_{z \in Z} P(z) \]
Els mètodes que hem vist utilitzen funcions $P(z)$ dues vegades derivables, i
minimitzen mitjançant el \emph{mètode del gradient}. A \cite{orourke1995} i a
\cite{robertson2004} utilitzen com a funció un model de camp aleatori de Huber-Màrkov. A
\cite{froment2005} utilitzen una versió adaptada de la norma de Variació Total
(TV).
\section{Altres mètodes de recuperació de plans}
Alguns mètodes (\cite{jung1998}, \cite{kwon2002})
utilitzen transformacions d'ondetes, ja que aquestes aporten
informació freqüencial i espacial. Amb la primera poden distingir zones de més i
menys textures per aplicar \emph{segmentació}, i amb la segona poden tractar els
efectes de bloc, que estan determinats en espai.
A \cite{nosratinia2002} i \cite{hp2004} utilitzen la recompressió JPEG de
versions desplaçades de la imatge descodificada de manera convencional, fent una
mitjana de les múltiples versions de les imatges desplaçades descodificades.
\section{Recuperació del color basada en lluminositat}
Tal com hem vist a l'apartat \ref{sec:plans-color},
el JPEG aïlla tota la informació de tonalitat de color en dos
plans que es codifiquen a menys qualitat que el de lluminositat. Totes les
tècniques que hem presentat fins ara es poden utilitzar per recuperar qualsevol
dels plans del JPEG, però a la literatura també trobem tècniques que utilitzen
la correlació entre lluminositat i color per a recuperar millor els plans
cromàtics, sovint delmats fins i tot.
A \cite{coudoux2004} detecten les cantonades del pla de lluminositat, i les
utilitzen amb un algorisme adaptatiu
per corregir els vessaments de color deguts a l'escalat. A \cite{sugita2006}
ponderen els canvis d'intensitat dels plans de color d'acord amb els canvis
d'intensitat del pla de lluminositat, per a imatges YUV en general. Aquest l'últim l'hem adaptat
al delmat del JPEG, explicat en detall a l'Apèndix \ref{sec:colorponderat}.
\chapter{Programari}
Com hem vist a l'apartat anterior, trobem nombrosos articles sobre la millora de
la descompressió JPEG. Malauradament, no trobem els algorismes implementats en
cap aplicació popular. GIMP i Adobe
Photoshop\reg, possiblement els processadors de mapes de bits més populars,
només suporten la descodificació convencional. A la última versió (6b) de la
\texttt{libjpeg} tampoc hi trobem res d'especial. A la seva documentació
hi trobem una declaració d'intencions per incorporar mètodes de restauració a la
versió 7, però sembla que el desenvolupament d'aquesta llibreria es va aturar
precisament a la 6b el 1998.
Així doncs hem trobat oportú construir una aplicació informàtica que ofereixi
als professionals de la imatge accés relativament fàcil als algorismes de
restauració més destacats. Com explicàvem al primer apartat d'aquest document,
la codificació JPEG es continua utilitzant activament, i per tant molts usuaris
es poden beneficiar d'una iniciativa com aquesta.
Quan hem buscat implementacions dels algorismes de restauració analitzats,
n'hem trobat molt poques,
i la majoria d'aquestes poques estaven escrites en Matlab. Els intèrprets de
Matlab els trobem pràcticament només a les universitats o dins departaments
d'investigació d'empreses, però la majoria de professionals de la imatge ni els
posseiran ni els sabran utilitzar. Nosaltres hem desenvolupat tota l'aplicació i
els algorismes en C i C++, ja que ens semblen els llenguatges més populars i a
l'abast de qualsevol gràcies a diversos compiladors i enllaçadors lliures
disponibles. Aquí tenim un llistat de les principals característiques
del programa:
\begin{itemize}
\item Només permet manipular una imatge JPEG alhora, junt amb versions
restaurades o que teníem guardades a disc.
\item Tot el procés i emmagatzematge intern de la informació de les imatges
es realitza en coma flotant de 32 bits (\texttt{float} en C), per evitar masses
pèrdues per arrodoniment als càlculs.
\item El programa requereix que l'usuari entengui la part de descodificació JPEG
que hem explicat al primer apartat, ja que és ell qui determinarà com es realitzaran diversos
passos d'aquesta descodificació.
\end{itemize}
L'aplicació inclou implementacions dels algorismes de
restauració que ens han semblat més prometedors, i també permet comparar
còmodament diferents versions d'una imatge, bé a ull nu, bé amb mesures
matemàtiques. A l'hora d'escollir els algorismes, ens hem regit pels següents
criteris:
\begin{itemize}
\item No ens importa la complexitat de l'algorisme en temps de computació o
memòria. No tractarem vídeo, sinó imatges estàtiques. Alguns articles presenten
novetats exclusivament en el camp de la restauració ràpida, tot i que no
aconsegueixen recuperacions tan bones com alguns algorismes més lents.
\item Hem considerat que els exemples d'imatge presentats al mateix article
ofereixen una bona idea del millor resultat que l'algorisme permet assolir.
Creiem que
alguns articles presenten molt poca millora (valorant subjectivament a ull nu)
com per a tenir-los en compte a la nostra implementació.
\item L'algorisme ha de permetre millorar imatges en general. Alguns només
milloren determinades zones de molt baixes freqüències, o fins i tot només
serveixen per a dibuixos artificials en comptes de fotografies.
\item L'efecte de l'algorisme s'ha de caracteritzar per pocs paràmetres, i
aquests han de tenir una relació monòtona amb els seus efectes.
En la majoria de casos l'usuari no
entendrà algorisme, i en variarà intuïtivament els paràmetres. Si
l'usuari no pot entendre l'efecte que té cada paràmetre, segurament refusarà
manipular-ne aquests paràmetres, o fins i tot no el tindrà en compte a l'hora de restaurar.
\end{itemize}
Podem classificar els algorismes segons la seva funció. A la nostra aplicació
distingim:
\begin{itemize}
\item Mesures no-referencials. Per exemple, GBIM.
\item Mesures referencials (comparació). Per exemple, la PSNR.
\item Elements de la cadena de descodificació.
\end{itemize}
A qualsevol imatge que hàgim carregat dins de l'aplicació li podem aplicar els
algorismes de mesura, i obtindrem els resultats en un nou quadre flotant de
text. Per a les mesures referencials haurem d'escollir les dues imatges a
comparar, en comptes de només una.
\section{La cadena de descodificació}
Un cop l'usuari hagi determinat quina imatge JPEG vol recuperar, li caldrà
decidir com es descodificarà. L'aplicació li donarà un esquema de la
\emph{cadena de descodificació} amb les baules buides, similar al de la Figura
\ref{fig:cadena}. Segons on es troben de la cadena, les baules fan referència
a una part o altra del procés de descodificació. A cada tipus de baula li
correspon un tipus d'algorisme. Considerem només aquests quatre tipus:
\begin{itemize}
\item Desquantització i transformada inversa de cada pla.
\item Restaurador de pla
\item Escalador dels plans
\item Canvi de plans de color. Per exemple, de YCbCr a RGB.
\end{itemize}
\figura{cadena.pdf}{\label{fig:cadena}Cadena de descodificació d'un JPEG amb
tres plans de color, amb les
baules (amb el contorn més gruixut) on hi podem col·locar diversos
algorismes. Les línies de punts separen els diferents tipus d'algorismes
acceptats. D'esquerra a dreta: \emph{desquantitzador i IDCT2D},
\emph{restauradors de pla}, \emph{escalador}, \emph{canvis de plans de color}.}
L'aplicació posarà a disposició de l'usuari uns quants algorismes de cada
tipus, i aquest podrà col·locar els que cregui adients a la cadena, com si es
tractessin de baules.
Alguns dels algorismes que col·locarem a les baules són configurables.
Això vol dir que el resultat que donin dependrà tant de l'entrada de
l'algorisme (provinent de la baula anterior) com de la configuració dels seus
paràmetres interns. Podem veure l'aspecte de l'aplicació mentre intentem
restaurar un JPEG de poca qualitat de la imatge Lena a la Figura
\ref{fig:qjpeg-screenshot}. Per entendre els noms d'algorismes que s'hi
distingeixen, podem consultar la Taula \ref{tab:algnames}, pàg.
\pageref{tab:algnames}.
\figura{images/projecteui.png}{\label{fig:qjpeg-screenshot}Mostra de les
principals finestres del programa. La principal, amb versions de la imatge a
restaurar. A sota, la cadena de descodificació. A dalt a la dreta, de fons, la
configuració de la baula de Froment. A l'esquerra, configuració de la baula
HContrast.}
\section{Desquantització i IDCT 2D de cada pla}
\begin{description}
\item[entrada] els intervals de quantització d'un pla de la imatge codificada
\item[sortida] una imatge d'intensitat espacial del pla
\end{description}
Aquest element té una doble funció: escollir quins punts de l'interval de
quantització determinaran els coeficients freqüencials concrets, i dur a terme
la transformada DCT 2D inversa.
A l'hora d'escriure aquest document, a l'aplicació hi ha dos algorismes
disponibles d'aquest tipus. El primer coincideix amb la descodificació
convencional de JPEG escollint el punt mig dels intervals. I el segon considera
la informació dels coeficients AC (tots menys la component contínua DC, el
primer coeficient de cada bloc) com variables aleatòries exponencials d'igual
mitjana, com a \cite{trianta2003}. L'usuari pot configurar-ne la mitjana.
\section{Restaurador de pla}
\begin{description}
\item[entrada] els intervals de quantització d'un pla de la imatge codificada
\item[entrada] una imatge d'intensitat espacial del pla (imatge de partida)
\item[sortida] una imatge d'intensitat espacial del pla (imatge millorada)
\end{description}
La majoria d'algorismes de restauració de JPEGs que hem trobat encaixen dins
aquesta categoria. Partint d'un pla inicial (als articles sol ser una
descodificació convencional) utilitzen diverses tècniques per obtenir una versió
millor del mateix pla. A l'apartat \ref{sec:tecniques} ja hem parlat d'aquest
tipus d'algorismes.
Cal destacar que als articles utilitzen imatges d'escala de grisos ja que
exclusivament intenten millorar un pla de la imatge. A la nostra aplicació podem
utilitzar aquests algorismes a qualsevol dels plans del JPEG. Igualment, podem
encadenar tants algorismes d'aquests tipus com vulguem, on cada un determinarà
la imatge inicial del seu successor.
Quan escrivim aquestes línies, l'aplicació dóna implementacions de
\cite{orourke1995}, \cite{froment2005}, \cite{robertson2004},
\cite{trianta2003}, \cite{nosratinia2002} i \cite{hp2004}. No tots aquests
algorismes utilitzen la \emph{projecció a l'espai de quantització} per assegurar
el compliment de la informació del JPEG, així que també hem inclòs aquesta
projecció com a algorisme independent. A part de les
propostes d'articles, inclou un
senzill algorisme de millora de les zones amb textura desenvolupat per nosaltres
mateixos que aprofita la naturalesa del programa: combinar i encadenar
tècniques. L'explicarem més endavant a l'Apèndix \ref{sec:hcontrast}.
Finalment, la implementació actual també inclou uns mòduls especials
que ens permeten alterar els
plans mitjançant una altra aplicació informàtica. Són els següents:
\begin{itemize}
\item \emph{salvar pla a disc}. Si l'usuari col·loca aquesta funció dins
d'una baula de
restauració de pla, al aplicar la descodificació definida per la cadena, el pla
d'entrada de la baula s'escriurà a disc. Llavors l'usuari pot utilitzar el seu
programa preferit de manipulació fotogràfica aplicant les tècniques que cregui
convenients al pla, i guardar els canvis per a reincorporar-los a la cadena amb
la funció que descrivim a continuació.
\item \emph{carregar pla de disc}. El pla d'entrada d'aquest algorisme
s'ignorarà completament, i el pla de sortida vindrà determinat per un fitxer
guardat a disc.
\end{itemize}
Aquestes dues funcions les hem utilitzat a la pràctica per millorar els plans
amb un filtre del GIMP\footnote{GNU Image Manipulation Program
\url{http://www.gimp.org/}}:, el suavitzat Gaussià sel·lectiu.
Aquesta tècnica també la utilitzen
combinada amb altres a \cite{queiroz1998} i \cite{kim1999}, i alguns manuals de
GIMP la recomanen per eliminar part del soroll d'algunes imatges JPEG.
Si utilitzem les funcions de \emph{salvar el
pla}, apliquem el filtre amb el GIMP, \emph{el carreguem a la cadena}, i després
hi apliquem una \emph{projecció sobre l'espai de quantització}, obtenim
resultats competitius amb altres algorismes, segons el tipus d'imatge i el
tipus de codificació JPEG.
\section{Escalador dels plans}
\begin{description}
\item[entrada] $n$ plans independents, possiblement alguns delmats
\item[sortida] $n$ plans, tots de la mateixa mida
\end{description}
Tal com hem explicat a l'apartat \ref{sec:plans-color}, alguns dels plans de
color de la imatge poden haver estat delmats abans de codificar-los independentment
(DCT 2D i quantització). La imatge final descodificada ha de tenir
tots els plans de color de la mateixa mida. Per això al descodificar ens cal
interpolar dels punts dels plans delmats, de manera que obtinguem les seves
dimensions originals. Cal recordar que el codificador delmarà els plans
dividint les dimensions originals per un número enter, i els delmats més comuns
són 4:2:2 i 4:2:0.
Al programa hem implementat tres tipus d'escaladors. El primer simplement
duplica els punts per aconseguir les dimensions desitjades. Per exemple, si
tenim els valors per punt en una fila $1,5,3,2,6$, i ens cal doblar la seva
mida horitzontal, l'algorisme ens donarà $1,1,5,5,3,3,2,2,6,6$. La
\texttt{libjpeg} també inclou una implementació d'aquest escalador.
El segon escalador, provinent també de la \texttt{libjpeg}
(on l'anomenen \emph{fancy upsampler}), interpola
linealment els punts del pla final a partir de la versió delmada
descodificada, tot i que
només funciona pels delmats 4:2:2 i 4:2:0. \revisar{Cal citar on explico la
notació 4:x:y?}
En el cas de 4:2:2, interpola cada punt final amb els dos punts
més propers del pla delmat. Hem de recordar que segons l'especificació JFIF
\cite{jfif}, els plans
delmats a la meitat en horitzontal, no tindran punts coincidents amb els del pla
final. Així doncs, obtenim els punts de color per les posicions dels punts de
lluminositat de la següent manera:
\[ \hat p_o = \frac{3}{4} p_1 + \frac{1}{4} p_2 \]
on $\hat p_o$ és el valor d'un punt d'una fila final,
$p_1$ és el del punt de la fila delmada més proper a
$\hat p_o$, i $p_2$ el del segon punt més proper. La Figura
\ref{fig:fancy422} representa visualment el procés.
\figuraw{10cm}{escalat422fancy.pdf}{\label{fig:fancy422}Reescalat d'una fila
de la component de color de delmat 4:2:2 (a dalt)
a la mida final determinada per la lluminositat (a baix), mitjançant
interpolació dels dos punts més propers.}
En el cas 4:2:0 el segon escalador interpola cada punt final mitjançant
els quatre punts més propers:
\[ \hat p_o = \frac{9}{16} p_1 + \frac{3}{16} (p_2 + p_3) + \frac{1}{16} p_4 \]
on $\hat p_o$ és el valor d'un punt del pla final, $p_2$ i $p_3$
són els dels altres dos punts més propers, i finalment $p_4$ el valor del punt
menys proper dels quatre. Podem veure-ho gràficament a la Figura
\ref{fig:fancy420}.
\figuraw{10cm}{escalat420fancy.pdf}{\label{fig:fancy420}Reescalat d'una porció
de la component de color de delmat 4:2:0 (en forma de creu dreta)
a la mida final determinada per la lluminositat (en forma de cercles),
mitjançant interpolació lineal entre els quatre punts més propers.}
Finalment, hem implementat un tercer escalador, basat en \cite{sugita2006},
on utilitzem una tècnica similar a la interpolació lineal,
però a més d'obtenir el
color de cada punt final basant-nos amb els quatre punts de color més propers,
ho ponderem segons les variacions de llum del pla de lluminositat (quan no ha
estat delmat). A
l'Apèndix \ref{sec:colorponderat} expliquem l'algorisme en detall.
Tot i que fins ara hem parlat del cas general de que les imatges JPEG tenen
unes mides múltiples de la mida de bloc (8 pícsels), en realitat aquesta
condició no s'exigeix a les imatges a codificar. La mida original de la imatge
està escrita al contenidor del JPEG, i l'escalador del descodificador és
l'encarregat de retallar
els últims blocs en horitzontal i vertical per a aconseguir la imatge final de
la mida que toca. Així, si una imatge mesura 124 pícsels d'amplada,
s'haurà codificat amb 16 blocs de 8 columnes, però de l'últim
bloc de cada fila (codificada d'esquerra a dreta)
només tindrem en compte la meitat esquerra descodificada
de 4 columnes d'amplada.
\section{Canvi de plans de color}
\begin{description}
\item[entrada] $n>1$ plans de color
\item[sortida] $n>1$ plans de color
\end{description}
Aquests algorismes transformen els plans de color codificats del JPEG als plans
exigits pel sistema gràfic del nostre ordinador. La nostra aplicació ara mateix
necessita que les imatges finals tinguin \subcite{a}un
pla de lluminositat o \subcite{b}tres plans vermell-verd-blau.
Segurament la majoria dels
nostres JPEG a color estaran codificats amb lluminositat-blavor-vermellor, i per
tant, per a mostrar-los correctament a l'aplicació,
necessitarem un algorisme convertidor de YCbCr a RGB.
Les extensions JFIF permeten anotar en quins plans de color s'ha codificat la
imatge. A la \texttt{libjpeg} per defecte es codifica amb YCbCr,
però també s'hi poden indicar codificacions RGB o CMYK. Nosaltres només hem
implementat el convertidor YCbCr a RGB, ja que no ens hem trobat imatges que
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
comentaris dels seus resultats.
\begin{table}[!htp]
\centering
\begin{tabular}{|ll|}
\hline
IDCTFloat & Descodificació convencional per a un pla \\
IDCTFExp & Coeficients com v.a. exponencials, de \cite{trianta2003} \\
Froment & \cite{froment2005} \\
O'Rourke & \cite{orourke1995} \\
Robertson & \cite{robertson2004} \\
Trianta & \cite{trianta2003} \\
Nosratinia & \cite{nosratinia2002} \\
HP & \cite{hp2004} \\
QCS Projection & Apartat \ref{sec:qcsproject} \\
HContrast & Apèndix \ref{sec:hcontrast} \\
% QCSKeepHF & XXXXXXXXXXXXXX \\ % Val més que no fem cas d'aquest mètode
LoadPlane & Carregar el pla de disc \\
SavePlane & Salvar el pla a disc \\
IntScaler & Escalador que duplica el valor dels punts delmats \\
FancyScaler & Escalador interpolador lineal \\
LumScaler & \cite{sugita2006}, Apèndix \ref{sec:colorponderat} \\
\hline
\end{tabular}
\caption{\label{tab:algnames}Noms curts dels mètodes
implementats al programa amb l'algorisme corresponent.}
\end{table}
En aquest anàlisi no ens hem basat gaire amb mesures matemàtiques, ja que
precisament un dels objectius que ens havíem proposat a l'hora de fer aquest
programari consisteix en permetre a l'usuari comparar resultats a ull nu, variant
paràmetres manualment. L'usuari dels algorismes, en aquest cas, provarà
d'aplicar diversos mètodes i a anar variant els seus paràmetres, fins a obtenir
una imatge que l'acontenti pel seu objectiu.
Els articles ofereixen mesures objectives dels
resultats de diversos algorismes, i no sempre hi ha una correspondència clara
entre aquestes mesures i l'opinió d'individuals. A l'avaluació hi
prenen part almenys: el contingut de la imatge (persones, dibuixos,
paisatges), la
resolució (de quina distància es miraran els punts de la imatge), i
l'objectiu de la restauració (impressió, postprocessat). Les mesures objectives
que hem vist no tenen en consideració tots aquests paràmetres, i per tant no ens
semblen suficients per avaluar prou útilment els resultats dels algorismes. En
aquest apartat, quan comparem algorismes, ens referirem a les opinions
d'uns pocs individus després d'haver escollit manualment tant els algorismes com
els paràmetres de la cadena de descodificació.
\section{Plans a molt poca qualitat}
Aquest tipus d'imatges (qualitat$<40$ a \texttt{libjpeg})
es caracteritzen per efectes de bloc molt importants
i poc detall de textures.
Partint d'una descodificació convencional, els algorismes iteratius
no-adaptatius de \emph{Froment}, \emph{O'Rourke},
i \emph{Robertson} són els que ens han donat millors resultats.
El de Trianta, com que funciona de manera
adaptativa segons informació espacial, no distingeix bé els blocs del JPEG
de blocs de cantonades reals de la imatge. Els de \emph{Nosratinia} i
\emph{HP} suavitzen excessivament la
imatge, comparant amb els tres primers que hem mencionat. Podeu veure un exemple
d'aquestes imatges a baixa qualitat a la Figura \ref{fig:lena40g}.
\begin{figure}[!htp]
\centering
\begin{tabular}{cc}
\includegraphics[width=6cm]{images/lena.png} &
\includegraphics[width=6cm]{images/lena-40-jpg.png} \\
a) & b) \\
\includegraphics[width=6cm]{images/lena-40-froment-8-1-f-sharp30.png} &
\includegraphics[width=6cm]{images/lena-40-jp2.png} \\
c) & d)
\end{tabular}
\caption{\label{fig:lena40g}Codificació/descodificació de la imatge Lena de 256x256
pícsels:
\subcite{a}original,
\subcite{b}JPEG qualitat 40 - PSNR 44,09 dB,
\subcite{c}descodificació amb
\emph{Froment} \cite{froment2005} (pesos de Froment, 8 iteracions,
mida inicial de pas 1) i posterior esmolat amb GIMP
(Filtre ``afila'', amb afilament 30) - PSNR 44,99 dB, i
\subcite{d}versió JPEG2000 (amb \texttt{jasper} versió 1.701.0) amb la mateixa
relació de compressió que la JPEG - PSNR 68,89 dB.}
\end{figure}
L'algorisme de \emph{Trianta}, però, si l'encadenem després d'algun dels altres
algorismes que suavitzen la imatge, permet recuperar bé moltes cantonades
accentuant-les. Cal mencionar que aquest algorisme no manté els coeficients dins
l'espai de quantització, i per això després d'aplicar-lo, recomanem una
\emph{projecció sobre el QCS}. Podeu veure un exemple del seu ús en compressió a molt baixa
qualitat a la Figura \ref{fig:lena10g}.
\begin{figure}[!htp]
\centering
\begin{tabular}{cc}
\includegraphics[width=6cm]{images/lena.png} &
\includegraphics[width=6cm]{images/lena-10-jpg.png} \\
a) & b) \\
\includegraphics[width=6cm]{images/lena-10-froment-12-1-f.png} &
\includegraphics[width=6cm]{images/lena-10-froment-12-1-f-trianta-2-2,5-1-5-500-qcs.png} \\
c) & d)
\end{tabular}
\caption{\label{fig:lena10g}Codificació/descodificació de la imatge Lena de
256x256 pícsels a molt baixa qualitat:
\subcite{a}original,
\subcite{b}JPEG qualitat 10 - PSNR 26,04 dB,
\subcite{c}descodificació amb
\emph{Froment} \cite{froment2005} (pesos de Froment, 12 iteracions,
mida inicial de pas 1) - PSNR 28,92 dB, i
\subcite{d}descodificació amb \emph{Froment} (com abans) seguit de
\emph{Trianta} \cite{trianta2002}
($\sigma_{lf}=2, \sigma_{hf}=2,5, \sigma_{\text{WSMM}}=1, \mu = 5, T=500$) i
\emph{projecció sobre QCS} - PSNR 27,90 dB}
\end{figure}
Respecte als plans de color, que en el cas de poca qualitat segurament hauran
estat delmats i codificats amb unes taules de quantització de valors molt alts,
donaran grans blocs diferenciats de color a la imatge. El que ens ha semblat més
correcte ha estat utilitzar algorismes que suavitzin molt, com els de
\emph{Nosratinia} i \emph{HP}.
Utilitzant l'escalador ponderat per lluminositat ens disminuirà
els vessaments de color importants que podem trobar en un cas com aquest.
Si l'ús excessiu d'algorismes suavitzants ens ha reduït el contrast de la
imatge, podem arreglar-ho a la imatge final mitjançant un programa de retoc
fotogràfic.
\section{Efecte d'ones superior al de blocs}
Quan els plans es codifiquen a la qualitat sovint oferta per defecte als
programes de manipulació gràfica ($75$ a la \texttt{libjpeg}), els
efectes d'ones sovint superen els de blocs. En aquests casos,
\emph{Nosratinia} i \emph{HP} no
els eliminen del tot, i els algorismes iteratius de \emph{Froment},
\emph{O'Rourke} i
\emph{Robertson} ofereixen bons resultats, tot i que amb masses iteracions o passos
per iteració massa grans (més de
10) suavitzarem la imatge més del compte. Per exemple, quan apliquem
excessivament \emph{O'Rourke} o \emph{Robertson} (molt similars), els gradients d'intensitat
de la imatge sofriran una mena de reducció de color. Les petites diferències de
tonalitat desapareixeran, deixant només les cantonades més marcades.
També hem comprovat l'efectivitat de restaurar el pla de lluminositat amb el
\emph{filtre Gaussià selectiu} del GIMP, i involucrar el resultat al mig de la
cadena de descodificació. Si es tracta d'una codificació d'alta qualitat (amb
intervals de quantització prou petits), aquest algorisme no ens suavitzarà zones
d'altes freqüències. Això sí, caldrà aplicar una projecció sobre el QCS abans de
l'escalador per a obtenir una versió més fidel a la codificació
original.
Respecte als plans de color, l'escalador de color que pondera segons la
lluminositat ens dóna els millors resultats dels tres que hi ha implementats en
totes les imatges que hem provat, també en el cas de JPEG d'alta qualitat si és que hi
ha delmat de color. Podem veure un exemple a la Figura \ref{fig:nenufar75}
\begin{figure}[!htp]
\centering
\begin{tabular}{cc}
\includegraphics[width=6cm]{images/nenufar.png} &
\includegraphics[width=6cm]{images/nenufar-75.png} \\
a) & b) \\
\includegraphics[width=6cm]{images/nenufar-75-froment-6-fancy.png} &
\includegraphics[width=6cm]{images/nenufar-75-froment-6-lumscaler.png} \\
c) & d)
\end{tabular}
\caption{\label{fig:nenufar75}Codificació/descodificació d'una fotografia d'un
nenúfar de 256x256 pícsels, amb la qualitat per defecte de la \texttt{libjpeg}.
\subcite{a}original,
\subcite{b}JPEG qualitat 75, delmat 4:2:0 - PSNR R/G/B 38,47/47,33/33,87 dB,
\subcite{c}descodificació amb
\emph{Froment} \cite{froment2005} (pesos de Froment, 6 iteracions,
mida inicial de pas 1) i escalador \emph{Fancy} - PSNR R/G/B 41,26/46,43/37,52 dB, i
\subcite{d}descodificació amb \emph{Froment} (com abans) seguit de
l'escalador \emph{LumScale} - PSNR R/G/B 42,12/47,92/39,82 dB}
\end{figure}
En el cas de que algunes textures es perdin massa pel suavitzat d'alguns
algorismes, podem utilitzar l'algorisme \emph{HContrast} (Apèndix \ref{sec:hcontrast})
per a intentar recuperar-les. Podem veure un exemple del seu ús a la Figura
\ref{fig:masxa}. A la mateixa figura també hi podem distingir clarament les
millores de color gràcies a l'algorisme \emph{O'Rourke} i el \emph{LumScaler}.
\begin{figure}[!htp]
\centering
\begin{tabular}{cc}
\includegraphics[width=6cm]{images/masxa-crop-jpg.png} &
\includegraphics[width=6cm]{images/masxa-crop-froment-5.png} \\
a) & b) \\
\includegraphics[width=6cm]{images/masxa-crop-froment-5-orourke-lum.png} &
\includegraphics[width=6cm]{images/masxa-crop-froment-5-orourke-lum-hcontrast-0,5.png} \\
c) & d)
\end{tabular}
\caption{\label{fig:masxa}Descodificació d'una fotografia
publicada a Internet, de 256x256 pícsels.
\subcite{a}publicació original,
\subcite{b}descodificació amb Froment \cite{froment2005} (pesos de Froment, 5 iteracions, mida
inicial de pas 1),
\subcite{c}descodificació amb Froment com abans, més O'Rourke \cite{orourke1995}
(10 iteracions, $T=0,1$, mida inical de pas 1) als canals de color, i
l'escalador LumScaler ($\sigma_h = \sigma_v = 0,25$,
Apèndix \ref{sec:colorponderat}).
\subcite{d}descodificació amb Froment i O'Rourke com abans, amb HContrast
(Llindar 0,05 i finestra de 7x7), i LumScaler també com abans.}
\end{figure}
\section{Dibuixos}
Tot i que la codificació JPEG va ser pensada per a fotografies, hi ha gent que
l'ha utilitzat per a conservar i distribuir imatges artificials com dibuixos o
logotips. En aquests casos el soroll ocasionat per la pèrdua d'informació pot
ser més molest que en una fotografia codificada amb els mateixos paràmetres.
Fins el 1996 els dibuixos artificials a través d'Internet estaven dominats pel
format GIF, ja que fins el 1995 aquest format va ser de lliure ús. Des de
llavors, l'empresa Unisys va decidir fer respectar la patent inherent en el GIF. A
més, el format GIF limitava la imatge a 256 colors d'una paleta de 24 bits, amb
un dels colors representant la transparència (útil en la composició d'imatges
en una web). Quan Internet es va popularitzar, poc programari suportava el
format PNG, sobretot els navegadors web\footnote{Per exemple,
el Microsoft Internet Explorer
suporta PNGs només des de la versió 5, i el canal alfa de transparència del PNG
des de la versió 7.}. Llavors, bé pel límit de colors, bé per costum, molta gent
ha conservat imatges artificials en JPEG.
Els algorismes de recuperació analitzats donen resultats especialment bons en
aquest tipus d'imatges. Ens referim a imatges amb un contrast molt alt,
amb pocs colors i les cantonades molt ben marcades. Precisament això fa que ens
trobem més vessaments de color, i un acusat efecte d'ones.
Els mètodes iteratius,
especialment \emph{O'Rourke} i \emph{Robertson}, combinats amb l'escalador
ponderat per lluminositat, ofereixen recuperacions
excel·lents en aquestes condicions. En podem veure un exemple a les Figures
\ref{fig:dibuix-logo} i \ref{fig:dibuix-stimpy}.
\urldef{\logocopamon}\url{http://www.futsalcat.com/seleccioabsoluta/copamon/LOGO%20COPA%20DEL%20MON%202007.jpg}
\urldef{\stimpy}\url{http://www.tvacres.com/images/stimpy.jpg}
\begin{figure}[!htp]
\centering
\begin{tabular}{ccc}
\includegraphics[width=6cm]{images/logo-copa-mon-jpg.png} &
\includegraphics[width=6cm]{images/logo-copa-mon-3orourke-7s-lum.png} \\
a) & b)
\end{tabular}
\caption{\label{fig:dibuix-logo}\subcite{a}Logotip d'un campionat del món
codificat amb JPEG, agafat d'Internet
(\logocopamon). \subcite{b}Recuperació segons una baula
d'\emph{O'Rourke} (7 passos, mida de pas de 1, $T=0,1$) per canal, i
\emph{LumScaler}.
}
\end{figure}
\begin{figure}[!htp]
\centering
\begin{tabular}{ccc}
\includegraphics[width=4cm]{images/stimpy-jpg.png} &
\includegraphics[width=4cm]{images/stimpy-3orourke-5steps.png} \\
a) & b)
\end{tabular}
\caption{\label{fig:dibuix-stimpy}\subcite{a}Personatge dibuixat
(Stimpy, de John Kricfalusi)
codificat amb JPEG, agafat d'Internet
(\stimpy). \subcite{b}Recuperació segons una baula
d'\emph{O'Rourke} (5 passos, mida de pas de 1, $T=0,1$) per canal, i
\emph{LumScaler}.
}
\end{figure}
\chapter{Conclusions i treball futur}
La popularitat de la codificació JPEG va ser el principal
motiu per a preocupar-nos per la seva descodificació. Moltes fotografies
ens són accessibles únicament en aquest format. L'evidència de que el procés de
descodificació es podia millorar, i que en prou feines existissin eines
informàtiques a aquest efecte, ens semblen motius suficients per a dedicar
aquest projecte al desenvolupament d'un descodificador JPEG interactiu com el
que hem presentat. En el procés d'investigació de les tècniques disponibles, hem
recopilat prou informació com per oferir un resum prou complet del camp de la
restauració d'imatges JPEG, i hem implementat alguns dels algorismes més
interessants dins aquest descodificador interactiu.
En aquest document presentem tant els problemes de la codificació JPEG com
l'estat de l'art de la seva descodificació, convertint-se en el document ideal
pels catalano-parlants que vulguin introduir-se en aquest camp.
El programa informàtic representa una
plataforma còmoda per acostar les investigacions en aquest camp a
públic més profà. Nosaltres hem decidit aturar el desenvolupament de
l'aplicació de manera que ens permetés elaborar aquesta investigació, i alhora
usuaris ja se'n poguessin beneficiar. A partir d'aquest punt hem considerat
aquest projecte acabat, i hem publicat l'aplicació a Internet. Això no vol dir
que el programa no es pugui millorar, ni que deixem de treballar en ell;
ara altres programadors poden afegir-hi els seus algorismes, i a més podem
considerar la resposta dels usuaris.
Hem publicat l'aplicació amb C++ sota la llicència GPL versió
2\footnote{\url{http://www.gnu.org/licenses/old-licenses/gpl-2.0.html}}; en part
perquè volem que la seva evolució continuï lliure i pública, i en part perquè
utilitzem
la llibreria Qt\footnote{\url{http://trolltech.com/}, que ens exigeix seguir
la llicència GPLv2.}
per a la interfície
gràfica. Aquesta tecnologia ens permet publicar una base de codi única per a
Linux/X-Windows, Macintosh OS X i Microsoft Windows. A més el programa està
preparat per a ser traduït a diferents idiomes, havent publicat de moment
la interfície en català, esperanto i anglès.
Abans de la publicació del programa, l'hem mostrat a un petit nombre
d'individus que ens han corroborat consideracions del seu disseny: els
interessava més comparar les diferents restauracions a cop d'ull, independent
de qualsevol mesura matemàtica. I diferents usuaris (amb les seves
circumstàncies) solen arribar a diferents restauracions, cadascú preferint la
seva. Entre els comentaris dels usuaris i alguns investigadors hi preval el de
sorpresa i alegria de que per fi existeixi un programa com aquest. Per tant,
considerem que hem assolit els objectius de fer arribar tecnologia de
restauració JPEG recent dels laboratoris als usuaris, i hem recopilat l'estat
de l'art d'aquest camp amb la plusvàlua de resultats pràctics gràcies a les
pròpies implementacions d'algorismes.
% 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{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 (\cite{kou1995}):
\[
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}
\]
Podem veure gràficament les bases de la transformada per coeficient, i la
influència gradual de les freqüències més altes a la Figura
\ref{fig:jpeg-coeficients}, pàg. \pageref{fig:jpeg-coeficients}.
\chapter{Algorismes en detall}
\section{Manteniment de textures}
\label{sec:hcontrast} La majoria dels mètodes de millora de pla estudiats
utilitzen alguna mena de suavitzat per eliminar, entre altres, els efectes de
bloc. Si aquest suavitzat s'aplica a zones on hi ha textures d'alta freqüència,
el resultat pot empitjorar respecte a una descodificació convencional. En la
majoria de casos això es traduirà en un augment de la PSNR, però ja hem explicat
a l'apartat \ref{sec:psnr} com la PSNR no ens serveix com a mesura de qualitat
en zones d'altes freqüències.
És per això que hem proposat un mètode adaptatiu per a no empitjorar
aquest tipus de zones. Ens basem en que si suavitzem una
zona d'altes freqüències, el seu contrast es veurà reduït. Per cada punt de la
imatge, considerem que si hem
reduït molt el contrast local respecte la descodificació convencional,
val més utilitzar el valor del pícsel d'aquesta última.
Avaluem tota la imatge segons el contrast local per cada punt $i,j$ de la imatge.
El contrast el valorem segons
Michelson: \revisar{Ho he tret de la Viquipèdia. Crec que és prou conegut com per
no citar-ne cap font.}
\newcommand{\Itext}[1]{I_{\text{#1}}}
\[ C(i,j) = \frac{\Itext{max}(i,j) - \Itext{min}(i,j)}{\Itext{max}(i,j)
+ \Itext{min}(i,j)} \]
A l'entorn local:
\begin{align}
\Itext{max}(i,j) &= \max_{k,l \in S} y(k,l) \\
\Itext{min}(i,j) &= \min_{k,l \in S} y(k,l) \\
\end{align}
on $y(k,l)$ és el valor associat al punt $k,l$ de la imatge, i $S$ el conjunt
de punts d'una finestra quadrada de 3x3, 5x5, 7x7, \ldots a l'entorn de $i,j$.
Calculem doncs el contrast local al pla restaurat $C(i,j)$, i
al pla descodificat de manera convencional $C'(i,j)$ per cada $i,j$ de la
imatge. Llavors, si $y_1(i,j)$ fa referència a un punt del pla restaurat, i
$y_c(i,j)$ a un del pla convencional, el nou punt restaurat $y_2(i,j)$
ve determinat per:
\[ y_2(i,j) = \begin{cases}
y_1(i,j) & \text{si} \, C'(i,j) - C(i,j) > \epsilon \\
y_c(i,j) & \text{altrament}
\end{cases}
\]
L'usuari pot escollir tant el llindar $\epsilon$ com la mida de la finestra de
$S$.
\section{Escalat dels plans de color ponderats amb la lluminositat}
\label{sec:colorponderat}A l'article \cite{sugita2006} proposen el ponderat
per a imatges que tenen els
plans de color delmats co-situats (\emph{cosited}). Això vol dir que els punts
del pla de color delmat coincideixen amb la posició de punts del pla sense
delmar. A les imatges JPEG, tal com diu l'especificació del JFIF \cite{jfif},
els plans delmats tenen els
punts inter-situats (\emph{intersited}) respecte al pla més gran (vegeu la
Figura \ref{fig:co-inter-situats422}. Això fa una
mica més complexes els algorismes.
\figuraw{7cm}{co-inter-situats422.pdf}{\label{fig:co-inter-situats422}Diferència entre
un pla de color delmat co-situat i un d'inter-situat pel cas 4:2:2.}
\subsection{Delmat 4:2:2}
En el cas 4:2:2 el valor de croma del pla delmat, a la
codificació, ha estat calculat segons la mitjana aritmètica dels dos punts
originals més propers.
Aquest algorisme proposa fer el mateix amb el pla de
lluminositat, com si el delméssim.
Del pla delmat anomenem $Y_1$ al punt més proper al nostre punt d'interès,
i $Y_2$ al segon més proper. Com que el pla de lluminositat el tenim també
sense delmar, sabem el valor del punt d'interès $Y_o$. Llavors, podem utilitzar
la relació
$\tfrac{Y_o-Y_1}{Y_2-Y_1}$ per a ponderar el pla de color. Podem veure-ho
gràficament a la Figura \ref{fig:lumscaler422}
\figura{lumscaler422.pdf}{\label{fig:lumscaler422}Escalat de color de 4:2:2 a
4:4:4 amb ponderació per lluminositat. Calculem la versió delmada de la
lluminositat, i obtenim $Y_1$ i $Y_2$, on $Y_1$ és el punt delmat més proper a
$Y_o$, i $Y_2$ el segon més proper. Veiem que la interpolació lineal entre $Y_1$
i $Y_2$ ens donaria un punt inferior a $Y_o$ - i aquesta és la correcció que es
fa palesa al pla de color. Les creus dretes ens mostren la versió delmada, i
ponderant el pla de color amb $\tfrac{Y_o-Y_1}{Y_2-Y_1}$ aconseguim també
l'anàleg a $Y_o$ més alt que si utilitzéssim interpolació lineal.}
Ara podem reescriure l'algorisme en funció de cada punt de la imatge (delmat i
sense delmar), i limitar la ponderació segons un paràmetre $\epsilon_h$.
En general, per cada fila tenim $1..N$ columnes de pla de color
i $1..2N$ columnes de pla
de lluminositat. Llavors, per cada punt $i$ del pla de color obtenim:
\begin{align}
Y(2i) &= C(i) + (C(i+1) - C(i)) \, w(Y(2i), Y_m(2i-1), Y_m(2i+1) \\
Y(2i+1) &= C(i+1) + (C(i) - C(i+1)) \, w(Y(2i+1), Y_m(2i+1), Y_m(2i-1))
\end{align}
on el pes $w(p,n,f)$ i el delmat de lluminositat $Y_m(j)$ els definim així:
\begin{align}
w(p,n,f) &= \begin{cases}
0,25 + \epsilon_h & \text{si} \, w'(p,n,f) > 0,25 + \epsilon_h \\
0,25 - \epsilon_h & \text{si} \, w'(p,n,f) < 0,25 - \epsilon_h \\
w'(p,n,f) & \text{altrament}
\end{cases} \\
w'(p,n,f) &= \frac{p - n}{f-n} \\
Y_m(j) &= \frac{Y(j) + Y(j+1)}{2}
\end{align}
on l'usuari pot escollir $\epsilon_h$.
\subsection{Delmat 4:2:0}
L'algorisme de 4:2:2 involucra dos punts $Y_1$ i $Y_2$ per cada punt de la
imatge final. En canvi, en el cas 4:2:0 tenim quatre punts involucrats, i ens
cal adaptar l'algorisme a aquests quatre punts. Com bé sabem, tenim tant delmat
horitzontal com vertical. Així, la nostra adaptació consisteix en primer
considerar el cas horitzontal i després el vertical, per cada punt de la imatge.
\figuraw{8cm}{lumscaler420.pdf}{\label{fig:lumscaler420}Escalat de color 4:2:0 a
4:4:4 ponderant segons la lluminositat.}
Seguint l'esquema de la Figura \ref{fig:lumscaler420}, i amb l'objectiu de
determinar el color al punt $Y_o$, considerem els punts
$Y_{1\ldots4}$ com els punts ordenats segons el més proper,
el segon més proper en
horitzontal, el tercer més proper en vertical, i el quart més proper. Utilitzant
la tècnica del cas de 4:2:2, considerem el punt temporal $Y_{o1}$
i en calculem la
croma ponderada segons $Y_1$ i $Y_2$ (amb els càlculs pertinents de la
lluminositat) i $\epsilon_h$.
Fem el mateix amb el punt $Y_{o2}$, $Y_3$, $Y_4$, i la mateixa $\epsilon_h$.
Finalment, a partir d'aquestes noves cromes dels punts $Y_{o1}$ i $Y_{o2}$, i d'unes
versions de la lluminositat de $Y_{o1}$
i $Y_{o2}$ (segons la mitjana dels seus punts
de lluminositat més propers), fem la ponderació per aconseguir $Y_o$, aquest cop segons un
paràmetre $\epsilon_v$ també configurable per l'usuari.
%\printindex
\bibliography{cited}
\end{document}