TDX/TDR - Departament de Matemàtica Aplicada

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

Fri, 03 Feb 2012 11:56:24 GMT

Learning multiresolution: Transformaciones Multiescala derivadas de la teoría estadística de aprendizaje y aplicaciones Yáñez Avendaño, Dionisio F. 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.

Técnicas de interpolación weno y su aplicación al procesamiento de imágenes

Thu, 06 Oct 2011 12:21:00 GMT

Técnicas de interpolación weno y su aplicación al procesamiento de imágenes Belda García, Ana María Un problema común en la teoría de aproximación es la reconstrucción de una función a partir de un conjunto de valores discretos de datos que dan información sobre la función misma. Esta información por lo general viene dada como valores puntuales o medias en celda de la función sobre un conjunto finito de puntos o celdas, respectivamente. La función es aproximada por un interpolante, es decir, por otra función cuyos valores puntuales o medias en celda coinciden con los de la función original. Este interpolante puede ser construido por interpolación lineal. En este caso la exactitud de la aproximación cerca de una singularidad está limitada y depende del orden de la singularidad, de modo que si construimos el polinomio interpolador basándonos en un stencil que cruza la singularidad obtendremos una aproximación insatisfactoria. Esto significa que aumentar el grado del polinomio producirá regiones más grandes de mala aproximación alrededor de las singularidades. Para aumentar la exactitud la solución es escoger los puntos de forma que el stencil quede dentro de la parte suave de la función, siempre que esto sea posible. Esta es la idea que hay detrás de la técnica de interpolación ENO (Esencialmente No Oscilatoria), introducida por Harten et al., que es un procedimiento no lineal con el que la región de poca exactitud queda reducida al intervalo que contiene la singularidad, siempre y cuando las singularidades estén suficientemente bien separadas. Liu et al. introdujeron una mejora sobre la técnica ENO, llamada weighted ENO (ENO ponderado), que consiste en reconstruir un polinomio que interpola los valores puntuales de la solución de una ley de conservación hiperbólica a partir de las medias en celda de la solución débil. En la interpolación WENO se asignan a cada celda todos los stencils que la contienen, y el polinomio interpolador se calcula como combinación lineal convexa de todos los polinomios correspondientes a estos stencils. La clave es asignar los pesos más convenientes a la combinación. Estos pesos deben ser elegidos de forma que en la combinación los polinomios interpoladores en los stencils que cruzan una singularidad tengan una contribución casi nula. En las regiones suaves se utiliza la información proporcionada por todas las celdas contenidas en los stencils del proceso de selección ENO, y el resultado es un mayor orden de exactitud. En este trabajo se ha integrado la técnica WENO en el entorno de multirresolución de Harten, y se ha adaptado a los contextos de medias en celda y valores puntuales. En ambos casos se proponen nuevas medidas para la suavidad de una función. Además, en el contexto de valores puntuales se propone una modificación en la definición de los pesos WENO, que mejora el orden de la aproximación en presencia de singularidades. En la definición de los pesos WENO se introduce un ε positivo para evitar que el denominador se anule y se suele tomar ε constante. En esta tesis se propone tomar ε=h2, lo que permite demostrar que si la función es suave en al menos r+1 puntos y tiene una discontinuidad dentro del stencil de 2r puntos, entonces obtenemos al menos una aproximación de orden r+1, es decir, como mínimo obtenemos el mismo orden que el interpolante ENO, y en las zonas suaves de la función el orden de la aproximación es óptimo incluso en presencia de puntos críticos en los que se anulen las dos primeras derivadas. Las técnicas de interpolación WENO se comparan, mediante diferentes experimentos numéricos, con las técnicas de interpolación lineal, ENO y ENO-SR, para poder concluir qué método proporciona la mayor exactitud en cada caso.; A common problem in approximation theory is to reconstruct a function from a discrete set of data which gives information on the function itself. This information will usually come in the form of point-values or cell-averages of the function, which is then approximated by an interpolant, that is, another function whose values at a given set of points or cell-averages are equal to those of the original one. This interpolant can be built through linear interpolation, but in this case the accuracy of the approximation in the presence of a singularity is limited by the order of the singularity, so that any stencil crossing it will result in a poor approximation. In order to improve the accuracy of the approximation we need to choose stencils that avoid crossing singularities, whenever this is possible. That is the idea behind the ENO (essentially non-oscillatory) technique, introduced by Harten et al. WENO (weighted ENO) was introduced by Liu et al. as an improvement upon ENO. The idea is to assign to each subinterval all the stencils containing it, and construct the interpolating polynomial as a linear convex combination of the corresponding polynomials. In this way we use all the information provided by the nodes contained in the candidate stencils in the ENO selection process, and this should give a higher order of accuracy in smooth regions of the function. The key point is the assignment of weights to the convex combination. In this work we have incorporated WENO to Harten's multiresolution framework, and adapted it to the context of cell-averages and point-values. Moreover, for point-values we propose a modification in the definition of the weights, producing a higher order of accuracy in the presence of singularities. We also compare the WENO technique with other interpolation techniques through numerical experimentation.

Modelos de deconvolución ciega fraccionaria. Aplicaciones a la restauración de obras pictóricas.

Tue, 12 Apr 2011 19:11:03 GMT

Modelos de deconvolución ciega fraccionaria. Aplicaciones a la restauración de obras pictóricas. Romero Sánchez, Pantaleón David

High Resolution Schemes for Conservation Laws With Source Terms.

Tue, 12 Apr 2011 19:11:02 GMT

High Resolution Schemes for Conservation Laws With Source Terms. Martínez i Gavara, Anna This memoir is devoted to the study of the numerical treatment of
source terms in hyperbolic conservation laws and systems. In particular,
we study two types of situations that are particularly delicate from
the point of view of their numerical approximation: The case of balance
laws, with the shallow water system as the main example, and the case of
hyperbolic equations with stiff source terms.
In this work, we concentrate on the theoretical foundations of highresolution
total variation diminishing (TVD) schemes for homogeneous
scalar conservation laws, firmly established. We analyze the properties
of a second order, flux-limited version of the Lax-Wendroff scheme which
avoids oscillations around discontinuities, while preserving steady states.
When applied to homogeneous conservation laws, TVD schemes prevent
an increase in the total variation of the numerical solution, hence guaranteeing
the absence of numerically generated oscillations. They are successfully
implemented in the form of flux-limiters or slope limiters for
scalar conservation laws and systems. Our technique is based on a flux
limiting procedure applied only to those terms related to the physical
flow derivative/Jacobian. We also extend the technique developed by Chiavassa
and Donat to hyperbolic conservation laws with source terms and
apply the multilevel technique to the shallow water system.
With respect to the numerical treatment of stiff source terms, we take
the simple model problem considered by LeVeque and Yee. We study
the properties of the numerical solution obtained with different numerical
techniques. We are able to identify the delay factor, which is responsible
for the anomalous speed of propagation of the numerical solution
on coarse grids. The delay is due to the introduction of non equilibrium values through numerical dissipation, and can only be controlled
by adequately reducing the spatial resolution of the simulation.
Explicit schemes suffer from the same numerical pathology, even after reducing
the time step so that the stability requirements imposed by the
fastest scales are satisfied. We study the behavior of Implicit-Explicit
(IMEX) numerical techniques, as a tool to obtain high resolution simulations
that incorporate the stiff source term in an implicit, systematic,
manner.

High order accurate shock capturing schemes for hyperbolic conservation laws based on a new class of limiters.

Tue, 12 Apr 2011 19:11:01 GMT

High order accurate shock capturing schemes for hyperbolic conservation laws based on a new class of limiters. Serna Salichs, Susana

La ecuación de Ince-Hill

Tue, 12 Apr 2011 19:11:00 GMT

La ecuación de Ince-Hill Sastre Sendra, Joaquin

Un modelo sistémico de evolución social dual.

Tue, 12 Apr 2011 19:10:59 GMT

Un modelo sistémico de evolución social dual. Nemiche, Mohamed En previos Modelos de Evolución Social desarrollados en la unidad de investigación de Teoría de Sistemas del Departamento de Matemática Aplicada de la Universitat de València se generaba una evolución uniforme, en la que los sistemas sociales pasaban por una serie unívoca de fases, pero no diferentes caminos de la misma.
Éramos conscientes de que dichos modelos no describían satisfactoriamente la Evolución real de la humanidad sobre el planeta tierra, donde se han desarrollado líneas de evolución diferenciadas. Siguiendo a Maurice Godelier podríamos describir dos líneas de evolución: una de ellas que podríamos llamar occidental, habría pasado por las fases de esclavitud, feudalismo y capitalismo. En la segunda línea evolutiva (oriental) el sentido de la colectividad ha primado en las distintas fases comenzando por lo que se llamó modo de producción asiático y posteriormente un tipo de feudalismo diferenciado, y más tarde lo que se ha llamado socialismo real o socialismo de estado. Solamente a finales del siglo pasado las dos líneas abarcaron lo que se ha llamado Globalización capitalista.
En la primera parte de la memoria hemos desarrollado un modelo matemático construido a partir de una Teoría de Aprendizaje y formulado en términos de la Teoría General de Sistemas. Hemos conseguido una representación satisfactoria de la evolución dual entre occidente y oriente introduciendo la oposición Gregarismo/Individualismo en los distintos comportamientos sociales y cambiando la modelación de algunos componentes de los modelos anteriores (sistema natural, sistema de represión, sistema impacto, y la posibilidad técnica de satisfacción).
En la segunda parte hemos realizado un estudio estadístico cualitativo y cuantitativo mediante métodos estocásticos para analizar la sensibilidad del modelo; también hemos estudiado el fenómeno del "efecto revuelta" en otro capítulo así como la evolución del consuno en satisfacción y represión de algunos comportamientos sociales.
La memoria se cierra con un capítulo que apunta nuevas direcciones de trabajo.; With previos Model Rafael Pla-López and Vicent Castellar-Busó have studied:
the processes that produce repressive social behaviors in the real world, the relationships that provoke these social behaviors among the population's elements, their influence on the environment and the necessary conditions to be able to overcome the repression with less repressive and more satisfactory social behaviors.
This model showed a general social evolution through one only way: in each set of all possible state (dimension) there were an only ideal behavior, which tended univocally to predominate. Thus, there were a correspondence between the successive dimensions and the successive predominant behaviors. Perhaps a dimension were overcome before its ideal behavior arrived to predominate, but it did not alter the linearity of the social evolution.
Nevertheless, in the real history of the humanity a clear dualism between Orient and Occident appears. If Godelier (Godelier 1970) already showed that the occidental evolution from slavery to capitalism were singular and not general, the experience of the bureaucratic regimens of Orient shows other singularity which cannot be embedded in the Engels' scheme (Engels 1884), but it have not either been a such ephemeral phenomenon to be explained by our Revolt Effect (Pla-López 1996b).
In this work we modelize, with an abstract mathematical model by computer simulation, the processes that have made to appear in the world a strong duality between orient and occident, by combining changes in conditions of initialisation, natural system and the opposition gregarious/individualism of the social behaviors.
Finally we present a statistical study of the influence of the repression adaptability, resignation and recycling on the ecological destruction and social evolution.
This model can help us to analyze if the current capitalist globalization can be stopped, changed or regulated, and if it is possible to overcome it toward a Free Scientific Society.

Avances en la multiresolución de Harten y aplicaciones

Tue, 12 Apr 2011 19:10:58 GMT

Avances en la multiresolución de Harten y aplicaciones Amat Plata, Sergio