Operadores de reconstrucción y esquemas de subdivisión asociados

XX Congreso de Ecuaciones Diferenciales y Aplicaciones X Congreso de Matem´ atica Aplicada Sevilla, 24-28 septiembre 2007 (pp. 1–6) Operadores de reconstrucci´on y esquemas de subdivisi´on asociados. S. Amat1, R. Donat2,J.C. Trillo1 1Dpto. Matem´atica Aplicada y Estad´ıstica, Universidad Polit´ecnica de Cartagena, Campus de Alfonso XIII, Edif. Civil y Naval, 30203 Cartagena. E-mails: [email protected], [email protected]. 2Dpto. de Matem´atica Aplicada, Universidad de Valencia, C/ Dr. Moliner,50, 46100 Burjassot , Valencia. E-mail: [email protected] . Palabras clave: esquemas de subdivisi´on, reconstrucciones, convexidad, monoton´ıa Resumen Los esquemas de subdivisi´on son unas herramientas muy usadas en el dise˜no de curvas y superficies, y tienen tambi´en relaci´on con otras aplicaciones interesantes en tratamiento digital de im´agenes o en la resoluci´on de ecuaciones diferenciales. Estos esquemas est´an basados en un conjunto de reglas, las c´uales aplicadas recursivamente permiten un refinamiento sucesivo de un conjunto inicial de puntos llamado puntos de control. Una propiedad importante a verificar en estos esquemas es la de preservaci´on de la convexidad y de la monoton´ıa. Una manera de abordar estas cuestiones se basa en la estrecha relaci´on entre esquemas de subdivisi´on y operadores de reconstrucci´on. Estos operadores de reconstrucci´on conectan datos discretos con un cierto espacio funcional, que depender´a de las aplicaciones en concreto. Nuestro objetivo es presentar ciertos operadores de reconstrucci´on y sus esquemas de subdivisi´on asociados, verificando si conservan la convexidad y la monoton´ıa. 1. Esquemas de subdivisi´on Comenzando con un conjunto discreto de datos, los esquemas de subdivisi´on generan nuevos datos siguiendo un conjunto de reglas bien establecidas, consiguiendo as´ı un nuevo conjunto de datos m´as ‘denso’ que el anterior, el cual ser´a a su vez refinado. Una manera de obtener esquemas de subdivisi´on surge de considerar los operadores de discretizaci´on Dk, que actuan entre un cierto espacio funcional Fy un nivel discreto de resoluci´on Vk(k mayor indica mayor resoluci´on), y los operadores de reconstrucci´on Rk, 1 S. Amat, R. Donat , J.C. Trillo los cuales conectan los diferentes niveles discretos de resoluci´on con el espacio funcional. El ´unico requerimiento es que la composici´on DkRk=IVk. Un esquema de subdivisi´on S puede definirse entonces como una aplicaci´on S:Vk→Vk+1 tal que Sfk=Dk+1Rkfk. Al operador Pk+1 k:= Dk+1Rkse le denota operador predicci´on y conecta dos escalas sucesivas de resoluci´on. 1.1. Esquemas de subdivisi´on interpolatorios Consideremos en Rel conjunto de mallas anidadas: Xk={xk j}j∈Z, xk j=jhk, hk= 2−k,(1) y el operador de discretizaci´on por valores puntuales Dk:(CB(R)→Vk f7→ fk= (fk j)j∈Z= (f(xk j))j∈Z,(2) donde Vkes el espacio de secuencias reales relacionado con la malla XkyCB(R) el conjunto de funciones continuas y acotadas R. Un operador reconstrucci´on Rkasociado a esta discretizaci´on es cualquier operador inverso por la derecha de Dk, lo que significa que para todo fk∈Vk,Rkfk∈CB(R) y (Rkfk)(xk j) = fk j=f(xk j).(3) El operador predicci´on, es decir, Dk+1Rk:Vk→Vk+1, define un esquema de subdivisi´on. La relaci´on (3) implica que el esquema de subdivisi´on es interpolatorio. Si Rkes un operador no lineal entonces el correspondiente esquema de subdivisi´on es tambi´en no lineal. Los esquemas de subdivisi´on interpolatorios pueden ser descritos de la siguiente forma: Sfk=Dk+1Rkfk=(fk+1 2j+1 = (Rkfk)(xk+1 2j+1), fk+1 2j= (Rkfk)(xk+1 2j) = fk j.(4) Debido a la propiedad de interpolaci´on, s´olo se necesita calcular las componentes impares de la nueva secuencia. Normalmente los operadores de reconstrucci´on utilizados son construidos a trozos, es decir, se construyen en cada intervalo [xk j, xk j+1] bajo las restricciones (Rkfk)(xk j) = fk jy (Rkfk)(xk j+1) = fk j+1. 1.2. Esquemas de subdivisi´on basados en discretizaci´on por medias en celda Este tipo de esquemas de subdivisi´on vienen generados por una discretizaci´on por medias en celda, es decir Dk:   L1(R)→Vk f7→ (¯ fj)j∈Z= ( 1 hkRxk j xk j−1 f(x)dx)j∈Z,(5) 2 Operadores de reconstrucci´on y esquemas de subdivisi´on asociados donde L1(R) representa a las funciones absolutamente integrables y {Xk}es la secuencia de mallas anidadas (1). Un operador de reconstrucci´on para esta discretizaci´on es cualquier operador Rkque satisfaga Rk:Vk−→ L1(R), (DkRk¯ fk)j=1 hkZxk j xk j−1 (Rk¯ fk)(x)dx =¯ fk j.(6) Por tanto Rk¯ fk(x) tiene que ser una funci´on en L1(R) cuyo valor medio en la celda (j)- ´esima coincida con ¯ fk jpara todo j. Tambi´en en este entorno de medias en celda es habitual construir los operadores de reconstrucci´on a trav´es de funciones polin´omicas a trozos. Para cada intervalo [xk−1 j−1, xk−1 j] se construye un trozo polin´omico pj(x) = pj(x, ¯ fk−1) que satisfaga (6), es decir 1 hk−1Zxk−1 j xk−1 j−1 pj(x)dx =¯ fk−1 j.(7) Una manera de conseguir esto es a partir de la funci´on primitiva F(x) := Rx −∞ f(x)dx. Se debe observar que el conjunto de datos {¯ fk−1 l}l∈Zse puede relacionar con Fk−1 l:= F(xk−1 l), l ∈Z, como sigue: Fk−1 l=hk−1X s ¯ fk−1 s,(8) ¯ fk−1 l=Fk−1 l−Fk−1 l−1 hk−1 .(9) El trozo polin´omico pj(x) se construye entonces como pj(x) = d dxqj(x, F k−1),(10) donde qj(x, F k−1) es un polinomio construido a partir de {Fk−1 l}l∈Zcon las restricciones qj(xk−1 j−1, F k−1) = Fk−1 j−1yqj(xk−1 j, F k−1) = Fk−1 j. Es s´olo una cuesti´on de algunas operaciones algebraicas el comprobar que se satisface (7). La predicci´on para ¯ fk 2j−1queda ¯ fk 2j−1=1 hk (qj(xk 2j−1)−qj(xk 2j−2)) = 1 hk (qj(xk 2j−1)−Fk−1 j−1). Y por tanto la predicci´on para los pares ser´a ¯ fk 2j−2= 2 ¯ fk−1 j−1−¯ fk 2j−1. 2. Un caso de esquemas de subdivisi´on no lineales: PPH En [1],[9] se presenta un nuevo operador de reconstrucci´on al cual los autores nombran PPH (piecewise polynomial harmonic). Un trozo polin´omico de este operador viene dado 3 S. Amat, R. Donat , J.C. Trillo por ˜qjdefinido para cada intervalo [xk j, xk j+1] como el ´unico polinomio de grado 3 que satisface ciertas condiciones. Definamos Dfk i=fk i−1−2fk i+fk i+1 2h2 k . Entonces, para el caso en que |Dfk j| ≤ |Dfk j+1|(este es el caso cuando una discontinuidad se encuentra en [xk j+1, xk j+2]) las condiciones son ˜qj(xk l) = fk l,para j−1≤l≤j+ 1, ˜qj(xk j+2) = ˜ fk j+2, con ˜ fk j+2 =fk j+1 +fk j−fk j−1+ 4 ˜ Dk jh2 k, ˜ Dk j=(2Dfk jDfk j+1 Dfk j+Dfk j+1 si Dfk jDfk j+1 >0, 0 en otro caso, Sino, ˜qjse determina por las condiciones ˜qj(xk j−1) = ˜ fk j−1, ˜qj(xk l) = fk l,para j≤l≤j+ 2 con ˜ fk j−1=fk j+1 +fk j−fk j+2 + 4 ˜ Dk jh2 k. A partir de este operador de reconstrucci´on se construye el esquema de subdivisi´on interpolatorio dado por (Sfk)2j=fk j, (Sfk)2j+1 =   fk j+1+fk j 2−1 4 D(f)k jD(f)k j+1 D(f)k j+D(f)k j+1 if D(f)k jD(f)k j+1 >0, fk j+1+fk j 2en otro caso, con D(f)k i=fk i+1 −2fk i+fk i−1. Utilizando entonces la t´ecnica de la funci´on primitiva se construye el operador de reconstrucci´on para el caso de discretizaci´on por medias en celda, es decir ˜pj(x) = d dxqj(x, F k), y tambi´en su esquema de subdivisi´on asociado, que resulta ser: (S¯ fk)2j+1 =¯ fk j−1 4 2δ(¯ f)k jδ(¯ f)k j+1 δ(¯ f)k j+δ(¯ f)k j+1 , (S¯ fk)2j+2 =¯ fk j+1 4 2δ(¯ f)k jδ(¯ f)k j+1 δ(¯ f)k j+δ(¯ f)k j+1 , con δ(¯ f)k i=¯ fk i−¯ fk i−1. 4 Operadores de reconstrucci´on y esquemas de subdivisi´on asociados 3. Conservaci´on de la monoton´ıa del esquema de subdivisi´on PPH En [9] se prueba que tanto el operador de reconstrucci´on PPH como su esquema de subdivisi´on tienen propiedades de conservaci´on de la convexidad en el caso interpolatorio. En este trabajo nosotros probamos resultados an´alogos respecto de la monoton´ıa para la reconstrucci´on PPH y para su esquema de subdivisi´on asociado en el entorno de las medias en celda. Definamos primero que se entiende por preservaci´on de la convexidad y de la monoton´ıa. Definici´on 1 El conjunto de datos {fj}, asociado a un mallado uniforme, se dice estrictamente convexo si y s´olo si D(f)j>0∀j, donde D(f)j=fj−1−2fj+fj+1. Definici´on 2 Un esquema de subdivisi´on sobre un mallado uniforme se dice que conserva la convexidad si y s´olo si el conjunto de datos {fk j}es estrictamente convexo para todos los niveles kde subdivisi´on. Definici´on 3 El conjunto de datos {¯ fj}, asociado a un mallado uniforme, se dice estrictamente mon´otono si y s´olo si δ(¯ f)j>0∀j, donde δ(¯ f)j=δ(¯ fj)−δ(¯ fj−1). Definici´on 4 Un esquema de subdivisi´on sobre un mallado uniforme se dice que conserva la monoton´ıa si y s´olo si el conjunto de datos {¯ fk j}es estrictamente mon´otono para todos los niveles kde subdivisi´on. Los dos principales resultados son los siguientes: Teorema 1 Sea ˜pj(x)el polinomio correspondiente a la reconstrucci´on PPH en el intervalo [xj, xj+1]dentro del entorno de medias en celda. Este polinomio ˜pj(x)satisface lo siguiente: si δ(¯ f)j>0yδ(¯ f)j+1 >0, entonces ˜p0 j(x)>0∀x∈(xj−1 2 , xj+3 2), es decir, es mon´otono en ese intervalo. Teorema 2 El esquema de subdivisi´on PPH para medias en celda conserva la monoton´ıa. Tambi´en como en el caso de la convexidad para valores puntuales es posible probar el Teorema 2 mediante una conexi´on entre las propiedades del operador de reconstrucci´on y las del esquema de subdivisi´on asociado. Referencias [1] S. Amat, R. Donat, J. Liandrat, and J.C. Trillo.Analysis of a new nonlinear subdivision scheme. Applications in image processing. Foundations of Computational Mathematics, (2006), 6(2), 193226. [2] F.Ar`andiga and R.Donat. Nonlinear Multi-scale Decompositions: The Approach of A.Harten, Numerical Algorithms (2000), 23, 175-216. [3] A. Cohen, N. Dyn and B. Matei. Quasilinear subdivision schemes with applications to ENO interpolation. Appl. Comp. Harm. Anal., (2003), 15, 89-116. 5 S. Amat, R. Donat , J.C. Trillo [4] G. Delauries, and S. Dubuc. Symmetric Iterative Interpolation Processes. Constr. Approx, (1989), 5, 49-68. [5] N. Dyn, A. Gregori, and D. Levin. A 4-point interpolatory subdivision scheme for curve design. Comput. Aided. Geom. Design., (1987), 4, 257-268. [6] N. Dyn, F. Kuijt, D. Levin, and R. van Damme. Convexity preservation of the four-point interpolatory subdivision scheme. Computer Aided Geometric Design, (1999), 16(8), 789-792. [7] M.S. Floater and C.A. Micchelli. Nonlinear stationary subdivision. Approximation theory: in memory of A.K. Varna, edt: Govil N.K, Mohapatra N., Nashed Z., Sharma A., Szabados J., (1998), 209-224. [8] F. Kuijt and R. van Damme. Convexity preserving interpolatory subdivision schemes. Const. Approx., (1998), 14, 609-630. [9] J.C. Trillo, PHD thesis: Nonlinear multiresolution and its applications in image processing, Univ. de Valencia, (2006). 6