Learning multiresolution: Transformaciones Multiescala derivadas de la teoría estadística de aprendizaje y aplicaciones

Author

Yáñez Avendaño, Dionisio F.

Director

Aràndiga, Francesc

Date of defense

2010-12-15

ISBN

9788437080789

Legal Deposit

V-4127-2011

Pages

240 p.



Department/Institute

Universitat de València. Departament de Matemàtica Aplicada

Abstract

Signal and image processing has become an essential and ubiquitous part of contemporary scienti¯c and technological activity, and the signals and images that need to be processed appear in most sectors of modern life. Signal processing is used in telecommunications, in the transmission of satellite images, and in medical imaging like echography, tomography, and nuclear magnetic resonance. Also it used in applications in Physics, Mechanics and other important issues that nowadays we know and that we will know in the future. Multiscale representations of signals into wavelets bases have been suc- cessfully used in applications such as compression and denoising. In these applications, one essentially takes advantage of the sparsity of the repre- sentation of the image. Harten designed a general multiscale framework only based in interpola- tion techniques. What is the Harten's idea? Firstly, he considered that given a set of discrete values in a resolution level k, fk, these values are the dis- cretization of a continuous functions depending on their 'nature'. Therefore he de¯ned the discretization operator Dk. In order to re¯ne the resolution of a set of discrete data Harten de¯ned the reconstruction operator, Rk to make up the original continuos function and with these two functions he de¯ned two operators that connect consecutive resolution levels: Dk¡1 k = Dk¡1Rk; Pk k¡1 = DkRk¡1: In this thesis we propose new reconstruction operators Rk. In the ¯rst part of the thesis we present a non linear Hermite interpolant which preserves the monotonicity. We use non-linear methods like ENO [B. Engquist et al., J. Comput. Phys., 71 (1987), pp. 231{303] and WENO [F. Arµandiga, A. Belda, P. Mulet, Jour. Scien. Comp., 43 (2010), pp. 158{182] to aproximate the derivarives. In multiresolution of Harten we have the \consistence condition": if we decimate Pk k¡1fk¡1 we have to obtain the original data fk¡1, i. e. Dk¡1 k Pk k¡1fk¡1 = fk¡1: Since most of the prediction operators that we obtain in this thesis do not satisfy this property we present a new strategy (AY) which will let us to use non-consistent prediction operators in a way that conserves its properties. We use approximation based on kernel methods [C. Loader, Springer, (1999)] to design new recontruction oparators. These consist on approximating a value, f(xk° ) by ^z(xk° ) where: ^z(x) = argm¶³n z(x)2K Xn j=1 K¸(xk° ; xk¡1 j )L(fk¡1 j ; z(xk¡1 j )): K is a class of functions where we minimize the functional; ¸ is the bandwidth, we only consider the values contained in the interval [xk° ¡ ¸; xk° + ¸]; K¸(xk° ; xk¡1 j ) is the kernel which assigns a weight to the each value in the level k ¡ 1; and L(x; y) is a loss function which measures the distance between the approximation and the real values, fk¡1. This method generalizes the interpolation methods introducing some ad- vantages. In an approximation problem using kernel methods there are some variables. We study the possibilities and the advantages and disad- vantages depending on these variables. Finally, we observe that in multiresolution context we know the original signal. Therefore, why don't we use this information to obtain a prediction operator? We answer this question using Statistical Learning Theory (see e.g. [T. Hastie, R. Tibshirani, J. Friedman, Springer, (2001)]) as follow: Given the values in the level k ffk j gj2Mk we solve ^ Pk k¡1 = argm¶³n g2K X j2Mk L(fk j ; g(Sr;s((Dk¡1 k fk)j))); where K is a class of functions and Sr;s((Dk¡1 k fk)j) are the function values in the level k ¡ 1 chosen to approximate each value in the level k. We adapt the classical de¯nitions of the Harten multiresolution to this new type of multiresolution and we design a prediction operator adapted to the edges of the image obtaining high compression rate. We analyze the theoretical properties for the two new methods, we com- pare them with traditional methods and we show their results.


El tratamiento de se~nales digitales se ha convertido en los ¶ultimos a~nos en una de las tareas m¶as interesantes y de mayor recorrido para la investigaci¶on matem¶atica. Hay aplicaciones directas en el campo de la Inform¶atica, redes de comunicaci¶on, tratamientos m¶edicos, tratamientos de recuperaci¶on de obras de arte, de fotograf¶³as. Aplicaciones en F¶³sica, Mec¶anica, desarrollos en pel¶³culas animadas y otras muchas que se conocen y que se conocer¶an a lo largo del tiempo. El tratamiento de se~nales podemos decir que comienza en la ¶epoca de Fourier (1807), su aplicaci¶on en funciones 2¼-peri¶odicas y su transformada para se~nales discretas es utilizada a¶un hoy con ¶exito para la compresi¶on y eliminaci¶on de ruido. Sin embargo la transformada de Fourier est¶a deslo- calizada en tiempo frecuencia (tan s¶olo nos ofrece la frecuencia) lo que provoc¶o en los a~nos 80 el desarrollo de las primeras bases wavelets. Estas bases tienen una localizaci¶on tiempo frecuencia y gracias a los ¯ltros que podemos obtener de ellas se pueden utilizar en el tratamiento de se~nales. Los esquemas de subdivisi¶on interpolatorios son reglas que nos permiten re¯nar un conjunto de datos interpolando los valores intermedios a los puntos dados utilizando combinaciones lineales de los valores vecinos. Estas dos ideas junto a la resoluci¶on de ecuaciones en derivadas parciales es lo que indujo a Harten a elaborar un marco general de multiresoluci¶on [A. Harten, J. Appl. Numer. Math., 12 (1993), pp. 153{192] que permite por medio de dos operadores fundamentales: decimaci¶on, Dk¡1 k y predicci¶on, Pk k¡1 establecer una conexi¶on entre dos niveles de resoluci¶on. La idea de Harten es sencilla pero a su vez est¶a cargada de grandes posibilidades pues generaliza las bases wavelets permitiendo la introducci¶on de elementos no lineales en sus operadores. >En qu¶e consiste la idea de Harten? En primer lugar, se dio cuenta de que si tenemos un conjunto de valores discretos en un determinado nivel de resoluci¶on k, fk, ¶estos poseen una naturaleza, es decir, proced¶³an de una cierta funci¶on continua f y hab¶³an sido discretizados dependiendo de la naturaleza de los datos, as¶³ pues gener¶o un operador discretizaci¶on Dk. Por otra parte si deseamos tener mayor resoluci¶on, es decir determinar m¶as puntos, necesitamos reconstruir primero esa se~nal continua que \perdimos" en la decimaci¶on por medio de un operador que llam¶o reconstrucci¶on, Rk y con estos operadores de¯ni¶o los ya mencionados, as¶³: Dk¡1 k = Dk¡1Rk; Pk k¡1 = DkRk¡1: Es en el operador Rk donde se introduce toda la teor¶³a interpolatoria (ver p. ej. [A. Harten, SIAM J. Numer. Anal., 71 (1996), pp. 231{303]) y donde podemos utilizar interpolaci¶on no lineal como los m¶etodos presenta- dos en el contexto de soluci¶on de ecuaciones diferenciales para capturar las discontinuidades, m¶etodos ENO (ver p. ej. [B. Engquist et al. J. Comput. Phys., 71 (1987), pp. 231{303]) y WENO (ver p. ej. [F. Arµandiga, A. Belda, P. Mulet, Jour. Scien. Comp., 43 (2010), pp. 158{182]). Harten impone una serie de condiciones a estos operadores, la primera de ellas es que el operador Dk¡1 k sea lineal y sobreyectivo, para ello pro- pone las distintas potencias de la funci¶on de Haar !0(x) = Â[0;1]. En la literatura sobre multiresoluci¶on podemos encontrar otros operadores de- cimaci¶on no splines. Nosotros no trabajaremos en este sentido, ¯jaremos varios operadores decimaci¶on y trabajaremos con ellos. La segunda es que estos operadores cumplan una condici¶on de consistencia: si tenemos una se~nal fk¡1 y mejoramos su resoluci¶on, es decir, predecimos estos datos Pk k¡1fk¡1 y despu¶es decimamos esta predicci¶on entonces recuperaremos los datos iniciales, i. e. Dk¡1 k Pk k¡1fk¡1 = fk¡1: Sin embargo en algunas aplicaciones (como compresi¶on de im¶agenes di- gitales) no necesitamos esta propiedad, en esta memoria se presenta una alternativa para trabajar con operadores no consistentes que ofrece buenos resultados y que conserva las propiedades. Por tanto omitimos esta segunda propiedad que Harten se~nal¶o en su marco general. En esta memoria introducimos otra alternativa al operador reconstrucci¶on. En lugar de utilizar elementos ¶unicamente interpolatorios usamos aproxi- maci¶on por medio de m¶etodos de n¶ucleo [C. Loader, Springer, (1999)]. Consisten en aproximar a un cierto valor dependiendo de la cercan¶³a (o lejan¶³a) de los valores de su entorno. Este m¶etodo generaliza los m¶etodos interpolatorios introduciendo posibles ventajas al poder utilizar gran can- tidad de puntos sin subir el grado del polinomio interpolador. Son muchas las variables que componen un problema de aproximaci¶on por m¶etodos de n¶ucleo. En esta memoria estudiamos algunas posibilidades y las ventajas y desventajas que suscitan. Nos planteamos la siguiente pregunta: conociendo la se~nal original, >por qu¶e no utilizar esta informaci¶on para generar un operador predictor m¶as adaptativo? Respondemos a ¶esta utilizando t¶ecnicas estad¶³sticas de apren- dizaje (ver p.ej. [T. Hastie, R. Tibshirani, J. Friedman, Springer, (2001)]) y generamos predictores que se adaptan a los contornos de la imagen y al nivel de resoluci¶on que tenemos. Este tipo de multiresoluci¶on nos induce a rede¯nir algunos conceptos que aparecen en el contexto de multiresoluci¶on y que debemos redise~nar para este tipo espec¶³¯co de multiresoluci¶on. Para ambas v¶³as, tanto para multiresoluci¶on utilizando m¶etodos de n¶ucleo como para multiresoluci¶on de aprendizaje analizamos las distintas propieda- des que tienen, las comparamos con los m¶etodos cl¶asicos y mostramos sus resultados. Esta memoria presenta de manera sencilla dos operadores predicci¶on de multiresoluci¶on distintos que abren las puertas a otro gran n¶umero de apli- caciones. Durante la realizaci¶on de estos m¶etodos han surgido diversos pro- blemas. El desarrollo de esta tesis es la soluci¶on a dichos problemas.

Subjects

51 - Mathematics

Knowledge Area

Facultat de Matemàtiques

Documents

yañez.pdf

6.461Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)