UNIVERSIDAD DE CHILEFACULTAD DE CIENCIAS FISICAS Y MATEMATICASDEPARTAMENTO DE CIENCIAS DE LA COMPUTACION

ADAPTACION DE ALGORITMO DE SINTESIS DE TEXTURAS PARA SIMULACIONGEOESTADISTICA DE MULTIPLES PUNTOS CONDICIONADA

TESIS PARA OPTAR AL GRADO DE MAGISTER EN CIENCIAS,MENCION COMPUTACION

ALVARO JOAQUIN PARRA BUSTOS

2011

UNIVERSIDAD DE CHILEFACULTAD DE CIENCIAS FISICAS Y MATEMATICASDEPARTAMENTO DE CIENCIAS DE LA COMPUTACION

ADAPTACION DE ALGORITMO DE SINTESIS DE TEXTURAS PARA SIMULACIONGEOESTADISTICA DE MULTIPLES PUNTOS CONDICIONADA

TESIS PARA OPTAR AL GRADO DE MAGISTER EN CIENCIAS,MENCION COMPUTACION

ALVARO JOAQUIN PARRA BUSTOS

PROFESORES GUIAS:NANCY HITSCHFELD KAHLER

JULIAN ORTIZ CABRERA

MIEMBROS DE LA COMISION:MARIA CECILIA RIVARA ZUNIGAPATRICIO INOSTROZA FAJARDIN

DOMINGO MERY QUIROZ

SANTIAGO DE CHILEABRIL 2011

RESUMEN

La geoestadıstica es una rama de la estadıstica que se encarga del estudio de variablesgeo-referenciadas. El estudio de la geoestadıstica es realizado principalmente en minerıa, dondesus tecnicas permiten estimar la calidad, cantidad y ubicacion de recursos minerales. Estudiar laincertidumbre de una variable de interes, por ejemplo la ley de un mineral, es de gran valor almomento de tomar decisiones que involucran grandes recursos monetarios. La incertidumbre esestudiada simulando escenarios igualmente probables de la variable en estudio. Los algoritmosde simulacion utilizados suelen ser relativamente costosos en tiempo y difıciles de paralelizar. Aesto se suma que para un estudio es necesario obtener, por lo general, cientos de escenarios sobredominios de millones o decenas de millones de puntos. Es por estas razones que el desarrollode algoritmos de simulacion es un problema importante y desafiante, donde la utilizacion detecnicas del area de las ciencias de la computacion posee un rol primordial.

La simulacion geoestadıstica de multiples puntos obtiene resultados que consideran la re-lacion espacial de mas de dos puntos a la vez, a diferencia de los metodos convencionales quesolo consideran la relacion de dos puntos, siendo incapaces de reproducir estructuras complejas.El objetivo principal de esta tesis consiste en disenar e implementar un algoritmo de simula-cion geoestadıstica de multiples puntos condicionada, es decir, que los resultados respeten unconjunto de puntos conocidos.

En esta tesis se desarrollo e implemento un algoritmo de simulacion geoestadıstica demultiples puntos para variables categoricas. Ademas, se investigo su aplicacion al uso de varia-bles continuas. El algoritmo fue probado simulando estructuras complejas, donde mostro un buencomportamiento tanto visual como estadıstico. Para el caso de variables continuas se realizo unejemplo exploratorio que muestra su posible uso. Las pruebas realizadas muestran que el algorit-mo es relativamente eficiente, tomando menos de 15 minutos en la obtencion de 100 resultadoscondicionados sobre un dominio de 100 por 100 puntos. Por otro lado, la estructura de datosdesarrollada para el almacenamiento de patrones ahorra consumo de memoria RAM y aceleralas busquedas, siendo posible trabajar con patrones de mas de 225 puntos.

Dentro de los aportes de este trabajo se muestra que tecnicas de computacion grafica pue-den servir de gran manera para el desarrollo de algoritmos de simulacion geoestadıstica. El algo-ritmo desarrollado es una adaptacion de un algoritmo de sıntesis de texturas que utiliza patronesde igual configuracion geometrica y recorre los puntos a simular en un orden preestablecido, evi-tando incurrir en el problema de busqueda de los vecinos mas cercanos para el punto a simular.Aunque se desarrolla una estructura de datos para abordar el problema de la busqueda de patro-nes, hay un gran campo a explorar en relacion a este problema. Finalmente, como trabajo futuro,se propone una metodologıa de paralelizacion del algoritmo, lo cual aumentarıa la eficiencia dela tecnica desarrollada.

AGRADECIMIENTOS

Agradezco en especial a mis padres, Hilda y Sarmiento, y a mihermano Ogan por todo lo entregado, su carino y apoyo incondi-cional; a mi abuela Marıa Eumenia, quien ya no nos acompana,por querer siempre lo mejor para mi familia; a mi Tata y tıa Ma-ruja por su preocupacion y apoyo.

Gracias Carola por tu amor, preocupacion y los momentos com-partidos durante todo este tiempo.

Muchas gracias Julian por todos tus comentarios, correcciones y,sobre todo, por las ensenanzas que van mas alla de lo academico.Agradezco tambien a quienes trabajan en ALGES. Han sido unosexcelentes companeros durante todo este tiempo, en especial: Al-varo E., Exequiel S., Felipe G., Felipe M., Felipe L., Fabian S.,Ingrid O. y Willy K.

Agradezco a mi profesora guıa Nancy H. por su buena disposiciony valiosos comentarios y correcciones.

Agradezco a mi amigo Alejandro L. y a mis amigos computinesy pseudo-computines: Pamela C., Oscar P., Raul A., Mauricio C.,Daniel (DBL) y Luis (LS), por sus consejos, apoyo, carretes y bue-nos momentos vividos.

Indice general

Indice de figuras VIII

Indice de algoritmos XII

1. Introduccion 1

1.1. Simulacion Geoestadıstica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2. Sıntesis de texturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.1. Objetivo general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.2. Objetivos especıficos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4. Contenido de la tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5. Aporte de la tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2. Antecedentes 8

2.1. Terminologıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.1. Template . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.2. Subtemplate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

III

2.1.3. Data-event . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.4. Patron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2. Conceptos basicos de geoestadıstica . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1. Fenomeno regionalizado . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.2. Variable regionalizada . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.3. Variable aleatoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.4. Funcion aleatoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2.5. Estacionaridad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2.6. Variograma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2.7. Kriging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3. Estudio de variabilidad local . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.1. Funcion de distribucion multi-Gaussiana . . . . . . . . . . . . . . . . . 19

2.3.2. Funcion de distribucion de indicadores . . . . . . . . . . . . . . . . . . 21

2.3.3. Simulacion Gaussiana . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3.4. Simulacion de variables categoricas . . . . . . . . . . . . . . . . . . . . 24

2.3.5. Simulacion multi-punto . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.3.6. Markov random fields . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.4. Sıntesis de texturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.4.1. Nocion de textura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.4.2. Analisis de texturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.4.3. Algoritmos de sıntesis de texturas . . . . . . . . . . . . . . . . . . . . . 39

IV

3. Algoritmo CUTSIM 47

3.1. Camino unilateral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.2. Template causal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.3. Obtencion de patrones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.3.1. Utilizacion de ruido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.3.2. Reduccion de dimensionalidad . . . . . . . . . . . . . . . . . . . . . . . 50

3.3.3. Uso de sub-templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.4. Distancia de patrones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.5. Condicionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.5.1. Asignacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.6. Pseudocodigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4. Algoritmo continuo 57

4.1. Metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.2. Obtencion de distribucion del indicador . . . . . . . . . . . . . . . . . . . . . . 58

5. Aceleracion 61

5.1. Listas enlazadas vs. arreglos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.2. Estructura de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.3. Recuperacion de patrones causales . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.4. Recuperacion de patrones con informacion no causal . . . . . . . . . . . . . . . 64

5.5. Recuperacion de subpatrones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.6. Modelo de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

V

5.6.1. Representacion de la informacion . . . . . . . . . . . . . . . . . . . . . 65

5.6.2. Representacion de la grilla . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.6.3. Representacion de los data-events . . . . . . . . . . . . . . . . . . . . . 69

6. Paralelizacion 72

6.1. Paralelizacion en simulacion discreta . . . . . . . . . . . . . . . . . . . . . . . . 72

6.2. Paralelizacion en simulacion continua . . . . . . . . . . . . . . . . . . . . . . . 73

7. Pruebas y resultados 74

7.1. Ejecucion del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

7.1.1. Paso de INPUTS por parametros . . . . . . . . . . . . . . . . . . . . . . 74

7.1.2. Paso de INPUTS por archivo . . . . . . . . . . . . . . . . . . . . . . . . 75

7.1.3. Uso de scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

7.2. Simulacion discreta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

7.2.1. Pruebas exploratorias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

7.2.2. Pruebas de canales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

7.3. Simulacion continua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

7.3.1. Lineas verticales continuas . . . . . . . . . . . . . . . . . . . . . . . . . 97

7.4. Simulacion 3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

8. Conclusiones 106

8.1. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

8.1.1. Paralelizacion del camino unilateral . . . . . . . . . . . . . . . . . . . . 107

VI

8.1.2. Busqueda de patrones . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

Bibliografıa 109

VII

Indice de figuras

1.1. Testigos y sondajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2. Visualizacion de un modelo de bloques. . . . . . . . . . . . . . . . . . . . . . . 3

1.3. Ejemplo de sıntesis de texturas. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.1. Ilustracion de un template y representacion de un patron categorico. . . . . . . . 8

2.2. Ejemplos variograma experimental y modelos de variogramas. . . . . . . . . . . 14

2.3. Ejemplo de realizaciones con el mismo variograma pero con diferentes carac-terısticas de conectividad espacial. . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4. Ejemplo de simulacion secuencial de indicadores. . . . . . . . . . . . . . . . . . 24

2.5. Umbrales de corte para 4 categorıas con igual proporcion. . . . . . . . . . . . . . 25

2.6. Ejemplos de simulacion Gaussiana truncada. . . . . . . . . . . . . . . . . . . . . 27

2.7. Ejemplos de realizaciones plurigaussianas para diferentes banderas. . . . . . . . 28

2.8. Espectro de texturas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.9. Ejemplo de kernel Gaussiano con σ = 1. . . . . . . . . . . . . . . . . . . . . . . 37

2.10. Ejemplo de aplicar distintos filtros para kernels de tamano 7× 7 pixeles. . . . . . 38

2.11. Ejemplo de piramide de multi-resolucion. . . . . . . . . . . . . . . . . . . . . . 39

2.12. Ejemplo de template causal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

VIII

2.13. Realizaciones utilizando algoritmo de Popat y Picard. . . . . . . . . . . . . . . . 44

2.14. Sıntesis de textura a resolucion unica. . . . . . . . . . . . . . . . . . . . . . . . 45

2.15. Ejemplos de realizaciones utilizando algoritmo de Wey y Levoy. . . . . . . . . . 46

3.1. Camino unilateral. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.2. Ejemplo de template causal y no-causal. . . . . . . . . . . . . . . . . . . . . . . 48

3.3. Subtemplates para template con 5 nodos de lado. . . . . . . . . . . . . . . . . . 51

3.4. Region degradada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.5. Visualizacion de simulacion de Monte Carlo. . . . . . . . . . . . . . . . . . . . 55

4.1. Distribucion continua construida mediante interpolacion y extrapolacion. . . . . 59

4.2. Extrapolacion de la cola inferior y superior. . . . . . . . . . . . . . . . . . . . . 60

5.1. Representacion de un arreglo y una lista enlazada. . . . . . . . . . . . . . . . . . 62

5.2. Representacion de la estructura de datos utilizada. . . . . . . . . . . . . . . . . . 63

5.3. Diagrama de clases para las clases genericas encargadas de representan la infor-macion: Pattern y CondData. . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.4. Diagrama de clases para una grilla. . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.5. Diagrama de clases para un data-event. . . . . . . . . . . . . . . . . . . . . . . . 71

7.1. Codigos de colores utilizados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

7.2. Imagenes de entrenamiento exploratorias de tamano 100 × 100 pixeles y doscategorıas (rojo y azul). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

7.3. Templates de tamano 3 × 3, 5 × 5, y 7 × 7 pixeles. Los nodos demarcados conlineas punteadas corresponden a los no-causales. . . . . . . . . . . . . . . . . . 80

7.4. Realizaciones para las distintas configuraciones de lıneas horizontales . . . . . . 81IX

7.5. Realizaciones para las distintas configuraciones de lıneas verticales . . . . . . . . 82

7.6. Realizaciones para los distintas variantes de “tablero de ajedrez” . . . . . . . . . 83

7.7. Imagen de entrenamiento de canales ondulantes de tamano 100× 100 pixeles. . . 84

7.8. Realizacion no condicionada de canales de tamano 500× 500 pixeles utilizandotemplate de tamano 11× 11 pixeles. . . . . . . . . . . . . . . . . . . . . . . . . 85

7.9. Variogramas experimentales de la realizacion mostrada en la fig. 7.8 . . . . . . . 86

7.10. Tiempos totales de simulacion. . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

7.11. Realizaciones no condicionadas para templates de tamano 5× 5, 9× 9 y 11× 11pixeles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7.12. Variogramas experimentales de las realizaciones de la fig. 7.11 para distintostamanos de template. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

7.13. Realizaciones condicionadas a franjas con zonas de canal y no-canal, de tamano100× 100 pixeles y generadas utilizando un template de tamano 11× 11 pixeles. 92

7.14. Variogramas experimentales para las realizaciones condicionadas de la fig. 7.13. . 93

7.15. Realizaciones condicionadas a 16 puntos aleatorios. . . . . . . . . . . . . . . . . 95

7.16. Variogramas experimentales de las realizaciones condicionadas mostradas en lafig. 7.15. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

7.17. Imagen de entrenamiento continua de 100× 100 pixeles formada utilizando fun-cion sinusoidal con valor mınimo 0 y maximo 1. . . . . . . . . . . . . . . . . . . 97

7.18. Realizaciones de simulacion continua de la imagen de entrenamiento 7.17 utili-zando un patron de tamano 5× 19 pixeles . . . . . . . . . . . . . . . . . . . . . 99

7.19. Realizaciones de simulacion continua de la imagen de entrenamiento 7.17 utili-zando un patron de tamano 5× 31 pixeles . . . . . . . . . . . . . . . . . . . . . 100

7.20. Variogramas experimentales para las realizaciones condicionadas de la figs. 7.18y 7.19, obtenidas utilizando templates de tamano 5× 19 y 5× 31 pixeles. . . . . 101

7.21. Grilla de entrenamiento 3D de tamano 256× 256× 128 y de 5 categorıas . . . . 103

X

7.22. Realizacion 3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

7.23. Variogramas experimentales de la realizacion 3D. . . . . . . . . . . . . . . . . . 105

8.1. Ilustracion de una simulacion paralela. . . . . . . . . . . . . . . . . . . . . . . . 108

XI

Indice de algoritmos

1. Pseudocodigo de CUTSIM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

XII

Capıtulo 1

Introduccion

1.1. Simulacion Geoestadıstica

La geoestadıstica es la rama aplicada de la estadıstica que se encarga del estudio de va-riables espacialmente distribuidas en un contexto geologico, tales como la ley de un mineral yla permeabilidad de la roca en un reservorio de petroleo. Es utilizada principalmente en minerıapara la evaluacion de yacimientos minerales. Nace como una ciencia a partir de los trabajos de H.Sichel [Sic52] y D. G. Krige [Kri51] en los anos 50 y es formalizada por G. Matheron [Mat62],[Mat63] durante los anos 60.

Durante la evaluacion de un yacimiento, el principal objetivo es la determinacion de lacalidad y cantidad de recursos, esto es, de la ley y el tonelaje esperable. Para este proposito sonobtenidas muestras geo-referenciadas (testigos) mediante sondajes, como los mostrados en la fig.1.1. Los sondajes, que suelen tener un alto costo, por si solos no son suficientes para predecirlos recursos disponibles, siendo necesario utilizar tecnicas de la geoestadıstica para pasar de lasmuestras a un modelo de bloques, que corresponde a una discretizacion 3D del yacimiento, dondecada bloque esta caracterizado por ciertos atributos, como por ejemplo ley, densidad, dureza,proporciones mineralogicas, litologıa, etc. En la fig. 1.2. es ilustrado un modelo de bloques.Ademas de la estimacion, la evaluacion de la incertidumbre de los recursos es muy importante,tanto por razones financieras como para la elaboracion de planes de extraccion. Para el estudiode la incertidumbre son utilizados algoritmos de simulacion geoestadısticos.

Para obtener estimaciones se utiliza un grupo de tecnicas geoestadısticas conocidas comokriging las cuales obtienen el valor a estimar mediante interpolacion insesgada y minimizando elerror cuadratico medio. Dado que kriging es un algoritmo de interpolacion, produce estimacionessuavizadas, no logrando reproducir grandes discontinuidades e irregularidades, fenomenos que

1

(a) (b)

(c)

Figura 1.1: Testigos obtenidos en un muestreo exploratorio (a-b). Sondajes 3D de leyes para unyacimiento (d).

2

Figura 1.2: Visualizacion de un modelo de bloques.

son de interes geologico y que pueden tener un gran impacto economico durante la fase futurade explotacion.

La simulacion geoestadıstica se encarga de generar distintos escenarios igualmente pro-bables que reproduzcan los fenomenos geologicos en estudio. Cada uno de estos escenarios,obtenido a traves de una imagen simulada, es conocido como una realizacion. Luego, medianteestas realizaciones, que respetan los datos muestrales y reproducen aspectos de la dependenciaespacial, es posible modelar la incerteza de las variables en estudio [Goo97]. La simulacion con-vencional se basa en la utilizacion del variograma, funcion que cuantifica la continuidad espacialde pares de puntos en una cierta direccion en funcion de su distancia, lo que no permite repro-ducir estructuras complejas, dado que solo se preserva la relacion espacial de pares de puntos[GS93, Str02]. Esta incapacidad es resuelta mediante los algoritmos de simulacion de multiplespuntos, los cuales utilizan la relacion de mas de dos puntos a la vez para que las realizacioneslogren reproducir informacion estructural mas compleja.

En [GS93] es propuesto un notable algoritmo para imponer la reproduccion de estadısti-cos de multiples puntos, tales como distribuciones trivariadas y multivariadas [And58, GS93],sobre imagenes simuladas; obteniendo imagenes que proporcionan informacion mas precisa delos problemas en estudio. Esta tecnica se basa en el uso de patrones obtenidos desde una ima-gen de entrenamiento caracterıstica del fenomeno en estudio. De esta forma, los estadısticos sonobtenidos directamente desde la imagen de entrenamiento, al contrario de kriging y simulacionconvencional, donde la heterogeneidad espacial es modelada mediante el variograma. En [Str02]es mejorada la metodologıa que infiere estadısticos a partir de imagenes de entrenamiento querepresentan los patrones esperados para los distintos fenomenos geologicos, mediante la incor-

3

poracion de un arbol de busqueda que guarda las frecuencias de patrones durante un pre-proceso,acelerando la busqueda durante el proceso de sıntesis. Estos algoritmos tienen la ventaja de serno-iterativos, por lo que no existen problemas de convergencia; no requieren de un modelo deestadısticos de multiples puntos ni de covarianza. Sin embargo, tienen la desventaja de ser al-tamente demandantes de CPU y de memoria RAM, consumo que aumenta drasticamente al au-mentar la dimensionalidad de los patrones que son empleados para la inferencia de las relacionesentre mas de dos puntos, ademas de depender mucho de la imagen de entrenamiento utilizada.

La simulacion de multiples puntos es un area en pleno desarrollo dentro de la geoestadısti-ca, en particular lo son los algoritmos que realizan inferencias a partir de patrones obtenidosdesde una o varias imagenes de entrenamiento representativas del fenomeno a estudiar. El traba-jo a realizar se encuentra dentro de este ultimo grupo de algoritmos.

Si bien, los algoritmos de simulacion tienen como finalidad resolver problemas mineros, elfoco de este trabajo de tesis es avanzar en el desarrollo de tecnicas de simulacion y no de resolverun problema de la minerıa en particular, en donde la aplicacion de la tecnica desarrollada podrıaser de utilidad.

1.2. Sıntesis de texturas

En computacion grafica existe un problema que guarda cierta relacion con simulacion geo-estadıstica, la sıntesis de texturas. Consiste en construir una imagen de cualquier tamano a partirde una textura representada por una imagen de entrenamiento que captura la esencia de la imagena producir. La imagen construida debe reflejar las mismas caracterısticas de la textura utilizada,es decir, bajo la percepcion humana debera parecer ser generada bajo el mismo fenomeno sub-yacente a la imagen de entrenamiento. Ademas de ello, se puede verificar estadısticamente lacalidad de la reproduccion de las estadısticas de patrones. En la fig. 1.3 es mostrado un ejemplode sıntesis de texturas.

Figura 1.3: Ejemplo de sıntesis de texturas. Extraıdo de [Wei01] pag. 3.

El algoritmo propuesto en [Wei01] desarrolla un procedimiento de sıntesis que no necesitala determinacion explıcita de probabilidades y muestreos. Esta basado en tecnicas de modela-

4

miento conocidas como Markov Random Field (MRF, por sus siglas en ingles). Los metodosde MRF modelan una textura como una realizacion de procesos locales y estacionarios, esto es,cada pıxel de una textura es caracterizado por una vecindad pequena de pixeles. La nueva texturaes generada pıxel por pıxel, los cuales son determinados de modo que la similitud local es pre-servada entre la imagen de entrenamiento y la imagen generada. El algoritmo puede funcionarbajo resolucion multiple y bajo resolucion unica. En el primer caso es necesario la utilizacionde una piramide de multi-resolucion (por ejemplo una piramide Gaussiana, como la utilizada en[Wei01]).

El algoritmo de sıntesis de texturas propuesto en [Wei01] es interesante por la rapidez yla calidad de las imagenes que son obtenidas. Esta tesis desarrolla un algoritmo de simulacionde multiples puntos condicionado tomando como base el trabajo de [Wei01]. Hay que tener pre-sente que la adaptacion no es directa, principalmente porque son problemas diferentes. La sınte-sis de texturas busca obtener resultados visualmente correctos a partir de texturas homogeneas,mientras que en geoestadıstica la calidad es medida mediante relaciones estadısticas entre lasrealizaciones y la imagen de entrenamiento, que ademas, puede asociarse a una textura aleato-ria, complicando el problema. El condicionamiento, es decir, respetar el valor de la variable enciertos puntos conocidos, es una de las principales dificultades que enfrenta la simulacion geo-estadıstica, problema que no esta presente en sıntesis de texturas. Otra diferencia importante, esla naturaleza del problema. En computacion grafica el resultado de un algoritmo de sıntesis detexturas es una imagen, mientras que en simulacion geoestadıstica, es el valor de una variablecategorizada o continua, en una region del espacio.

Aunque el algoritmo propuesto en [Wei01] usa imagenes (representacion visual de objetos)la implementacion que se propone desarrollar en esta tesis estara enfocada a datos espacialmentedistribuidos, que no necesariamente tendran una representacion visual.

1.3. Objetivos

1.3.1. Objetivo general

El objetivo general es disenar e implementar un algoritmo eficiente de simulacion geo-estadıstica de multiples puntos condicionada para datos categoricos y continuos en 2D y 3Dutilizando tecnicas de sıntesis de texturas.

5

1.3.2. Objetivos especıficos

Los objetivos especıficos son:

1. Estudiar el algoritmo de sıntesis de texturas desarrollado en [Wei01].

2. Desarrollar una metodologıa de condicionamiento para el algoritmo de sıntesis de texturasdesarrollado en [Wei01].

3. Mejoramiento de la biblioteca (base de datos de patrones) desarrollada en [Par08].

4. Desarrollar e implementar algoritmo de simulacion condicionado para multiples categorıasen 2D y en 3D.

5. Extender el algoritmo desarrollado para realizar simulacion continua mediante simulacionde indicadores.

6. Estudiar y evaluar la escalabilidad del algoritmo y las bibliotecas desarrolladas para serutilizadas en un cluster.

1.4. Contenido de la tesis

El segundo capıtulo, de antecedentes, muestra las metodologıas y conceptos basicos tantode geoestadıstica como de computacion grafica. En dicho capıtulo se presenta el problema de va-riabilidad local, en donde son explicados los principales algoritmos de simulacion geoestadıstica.Se presenta tambien el problema de sıntesis de texturas y los algoritmos estudiados.

El tercer capıtulo, Algoritmo CUTSIM, presenta el algoritmo desarrollado e implementa-do.

El cuarto capıtulo, Algoritmo Continuo, explica la metodologıa desarrollada para simula-cion continua mediante simulacion de indicadores por medio de CUTSIM.

En el quinto capıtulo, Aceleracion, se muestra la estructura de datos empleada para larecuperacion de estadısticos.

El sexto capıtulo, Paralelizacion, son mostradas las estrategias de paralelizacion seguidas.

En el septimo capıtulo, de pruebas y resultados, primero se muestra como ejecutar el algo-ritmo, luego, son dados a conocer los resultados obtenidos.

6

Finalmente, en el octavo capıtulo, son presentadas las conclusiones sobre la investigaciony los resultados obtenidos como consecuencia del trabajo realizado.

1.5. Aporte de la tesis

El principal aporte de esta tesis es el algoritmo desarrollado y la vision dada por este, en elsentido de mostrar como problemas de computacion grafica pueden ser utilizados para resolverproblemas de otras areas. En esta tesis es mostrado que simulacion geoestadıstica y sıntesis detexturas no son problemas tan distantes, aunque de naturaleza distinta. En cuanto a desafıos, elprincipal fue proponer y probar un metodo de condicionamiento para el algoritmo (CUTSIM)desarrollado e implementado. Si bien, se resuelven problemas y se de desarrolla un algoritmo,se abren nuevas posibilidades a explorar, de especial interes lo es la estrategia de paralelizacionpropuesta como trabajo futuro. Otro aporte es la utilizacion de estructura de datos en problemasde geoestadıstica, en donde, si bien recientemente se ha trabajado en ello, hay un gran campo porexplorar, por ejemplo, en lo que se refiere a busqueda de patrones.

Las publicaciones: “Conditional Multiple-Point Simulation with a Texture Synthesis Al-gorithm” [PO09], “Multiple-Point Conditional Unilateral Simulation for Categorical Variables”[PO10b] y “Conditional Multiple Point Simulation with Texture Synthesis” [PO10a], han sidorealizadas en gran medida con los resultados obtenidos de esta tesis.

7

Capıtulo 2

Antecedentes

A continuacion se muestran conceptos basicos y metodologıas tanto de geoestadıstica co-mo de computacion grafica, de utilidad para la lectura de esta tesis.

2.1. Terminologıa

(a) (b)

Figura 2.1: (a) Ilustracion de un template. (b) Representacion de un patron de tres categorıas(blanco, gris y negro) con geometrıa definida por el template en (a).

2.1.1. Template

Para el condicionamiento de una variable aleatoria los algoritmos suelen restringir la vecin-dad a un conjunto de posiciones relativas al nodo visitado. Este conjunto de posiciones relativases denominado template. Un template τn de dimension n es definido como:

τn = {hα, α = 1, . . . , n} (2.1)

8

2.1.2. Subtemplate

Un subtemplate τn′ de τn es un template constituido por un subconjunto de vectores de τn,con n′ < n.

2.1.3. Data-event

Un data-event dn de tamano n corresponde a un conjunto de datos capturados desde unagrilla utilizando un template τn centrado en el nodo visitado u. Formalmente, un data-eventcentrado en u corresponde a:

dn = {Z(u + hα), hα ∈ τn} (2.2)

y se dice que el data-event dn esta asociado con el template τn si es que las n posiciones tienenun valor asignado.

2.1.4. Patron

Un patron patτ corresponde a un vector en que cada componente patτ (α), α = 1. . . . , nes igual al valor del data-event dn centrado en u en la posicion (u + hα), con hα pertenecienteal template τn asociado a dn. Un patron es el vector formado por los valores rescatados me-diante un data-event en que todas las posiciones del template τn tiene un valor informado. Unarepresentacion de un patron para tres categorıas es mostrada en la fig. 2.1.

2.2. Conceptos basicos de geoestadıstica

En geoestadıstica se estudian metodos determinısticos y, sobre todo, estadısticos para en-tender y modelar la variabilidad espacial de fenomenos regionalizados.

2.2.1. Fenomeno regionalizado

Se entiende por fenomenos regionalizados a aquellos que se desarrollan en el espaciogeografico y presentan una cierta continuidad. Un ejemplo de fenomeno regionalizado es el

9

conjunto de fenomenos fısicos y quımicos que producen una mineralizacion y el transporte departıculas que generan depositacion de un contaminante en un sitio.

2.2.2. Variable regionalizada

Para estudiar un fenomeno regionalizado este es descrito por una o varias funcionesnumericas denominadas variables regionalizadas, las que miden propiedades o atributos delfenomeno, por ejemplo:

la ley de un mineral;

la porosidad y la permeabilidad de la roca en un reservorio de petroleo;

el numero de arboles y su diametro promedio en areas de observacion de un bosque.

La variable regionalizada es estudiada dentro de un dominio finito A. El fenomeno regio-nalizado es caracterizado por la distribucion espacial de una o varias variables regionalizadasz(u), correspondiendo al valor de la variable z en el punto del espacio u.

2.2.3. Variable aleatoria

Para modelar la variable regionalizada z en un dominio finito A, cualquier valor descono-cido z(u), u ∈ A es representado como una variable aleatoria Z(u) para luego encontrar unadistribucion de probabilidad que permita modelar la incerteza de z.

La aplicacion directa de estadıstica clasica no tiene mucha aplicacion en el modelamientoy estudio de fenomenos regionalizados. La estadıstica clasica considera los datos como realiza-ciones independientes e identicamente distribuidos (i.i.d.) de una misma variable aleatoria, esdecir, supone que los datos no estan relacionados entre sı y que siguen la misma funcion de pro-babilidad. Cuando los datos en estudio tienen una componente espacial, estos supuestos no dancabida ya que en la realidad se observa que los datos cercanos tienen valores parecidos mientrasque los lejanos tienen una menor relacion entre ellos.

Las variables aleatorias pueden representar tanto fenomenos categoricos como continuos.Algunos ejemplos de fenomenos que pueden ser modelados por funciones aleatorias continuasson propiedades petrofısicas como: porosidad, permeabilidad, concentraciones de metal o con-taminante; y propiedades geograficas como: elevaciones topograficas, densidades de poblacion.

10

Algunos ejemplos de variables categorizadas son propiedades geologicas tales como tipos deroca, tambien lo son el conteo de insectos o especies fosiles.

La funcion de distribucion de probabilidad acumulativa (cpdf) de una variable aleatoriacontinua es denotada como:

F (u; z) = Prob {Z(u) ≤ z} (2.3)

Cuando la cpdf es condicionada por un una vecindad de n valores se usa la notacion “con-dicional a (n)”, lo que define una funcion de distribucion acumulativa condicional (ccpdf):

F (u; z | (n)) = Prob {Z(u) ≤ z | (n)} (2.4)

Se conoce como variable aleatoria categorizada Z(u) a una variable aleatoria que solopuede tomar uno de losK diferentes valores sk, donde, k = 1, . . . , K. Su funcion de distribucionde probabilidad condicional corresponde a:

F (u; k | (n)) = Prob {Z(u) = sk | (n)} (2.5)

Es importante notar que la ccdf F (u; k | (n)) depende de la posicion u, del tamano delconjunto de muestras, la configuracion geometrica de estas (posicion de los datos uα, α =1, . . . , n) y de los n valores z(uα).

2.2.4. Funcion aleatoria

Dado que las variables aleatorias de fenomenos regionalizados no son independientes, estosfenomenos son modelados mediante funciones aleatorias. Una funcion aleatoria se define comoel conjunto de variables aleatorias en el campo A, es decir,

Z = {Z(u), u ∈ A} (2.6)

De esta forma, la variable regionalizada z = {z(u), u ∈ A} es una realizacion de unafuncion aleatoria Z. A diferencia de la estadıstica clasica, las variables aleatorias, definidas comocomponentes de una funcion aleatoria, no son independientes; por el contrario, existe correlacionentre ellas que refleja la continuidad de la variable regionalizada [Eme07a].

De la misma forma que una variable aleatoria es representada por su cpdf, una funcionaleatoria es representada por un conjunto deK cpdf’s, para cualquier numeroK y para cualquier

11

eleccion de las K posiciones uα, α = 1, . . . , K:

F (u1, . . . ,uK ; z1, . . . , zK) = Prob {Z(u1) ≤ z1, . . . , Z(uK) ≤ zK} (2.7)

Del mismo modo que la cpdf univariada de una variable aleatoria es utilizada para mode-lar la incerteza del valor z(u), la cpdf multivariada (2.7) es utilizada para modelar la incertezaconjunta de los K valores z(u1), . . . , z(uK).

Un caso importante en geoestadıstica son las cpdf’s bivariadas (K = 2) las cuales utilizan2 variables aleatorias: Z(u) y Z(u′):

F (u,u′; z, z′) = Prob {Z(u) ≤ z, Z(u′) ≤ z′} (2.8)

2.2.5. Estacionaridad

La inferencia de un estadıstico, como por ejemplo la inferencia de una cpdf, requiere deun muestreo repetitivo. Por ejemplo, para estimar F (u; z) = Prob {Z(u) ≤ z} es necesariorealizar un muestreo sobre la variable z(u). El problema que se presenta es que la mayorıa delas veces se tiene conocimiento de la variable en estudio z(u) solo en algunas posiciones. Parasobrepasar esta dificultad se debe inferir el estadıstico utilizando informacion de otras posicionesdentro del mismo campo. Para manejar esto es necesario asumir la hipotesis de estacionaridad.

Se dice que una funcion aleatoria Z(u),u ∈ A es estacionaria dentro de un campo A, sisu cpdf multivariada es invariante ante cualquier traslacion de los K vectores de coordenadasuα, α = 1 . . . , K, es decir, si se cumple que:

F (u1, . . . ,uK ; z1, . . . , zK) = F (u1 + l, . . . ,uK + l; z1, . . . , zK) (2.9)

donde l es el vector que representa la traslacion.

La invariancia sobre la cpdf multivariada implica invariancia sobre las cpdf’s de menororden incluyendo las cpdf’s bivariadas y univariadas, como tambien todos sus momentos.

La hipotesis de estacionaridad permite la inferencia. Por ejemplo la cpdf

F (z) = F (u, z),∀u ∈ A (2.10)

puede ser inferida a traves de un histograma acumulativo muestral de los valores de la variable zpresentes en las distintas posiciones del campo A.

Bajo la hipotesis de estacionaridad, la continuidad espacial no depende de la posicion de12

las variables en estudio sino que de la configuracion entre ellas. De esta forma, la covarianzapuede ser calculada como:

C(h) = E {Z(u + h)Z(u)} − [E {Z(u)}]2 ∀u, u + h ∈ A (2.11)

En la ecuacion 2.11 se aprecia que la covarianza de dos puntos solo depende de la separa-cion (dada por el vector h) entre los puntos, y no de su posicion en el campo.

2.2.6. Variograma

El variograma es una medida de la variabilidad espacial y es la clave de cualquier estudiogeoestadıstico ([DJ92], pag. 43). El variograma mide la desemejanza entre dos puntos en elespacio.

Bajo el supuesto de estacionaridad, el variograma se define como:

γ(h) =1

2V ar {Z(u + h)− Z(u)} (2.12)

y se puede mostrar queγ(h) = C(0)− C(h),∀u (2.13)

El variograma es utilizado en geoestadıstica para modelar la variabilidad espacial por loque es usado como INPUT en muchos algoritmos de simulacion. Existe una equivalencia entrela utilizacion del variograma y la covarianza la cual puede ser inferida a partir de un modelo devariograma.

Algunos modelos utilizados de variograma son:

Esferico Definido por un alcance a y un valor positivo de contribucion de varianza c (conocidocomo meseta).

γ(h) =

c ·

[1,5

h

a− 0,5

(h

a

)3]

si h ≤ a

c si h > a

(2.14)

Exponencial Definido por un alcance a y un valor positivo de contribucion de varianza c.

γ(h) = c ·[1− exp

(−3h

a

)](2.15)

13

Gaussiano Definido por un alcance a y un valor positivo de contribucion de varianza c

γ(h) = c ·

[1− exp

(−(3h)2

a2

)](2.16)

En la figura 2.2 se muestra un ejemplo de un variograma experimental, es decir obteni-do directamente desde los datos; y variogramas modelados mediante un modelo exponencial yesferico.

(a) Variograma experimental (b) Diferentes modelos de variogramas (exponencialy esferico)

Figura 2.2: Ejemplos variograma experimental (a) y modelos de variogramas (b) extraıdos de[Cla79].

El variograma solo provee una caracterizacion parcial de la funcion aleatoria por lo quecaracterısticas como la conectividad espacial de valores no estan descritas por esta herramienta([Eme07a], pag. 48). Estas caracterısticas solo pueden ser estudiadas bajo modelos que involu-cren mas de dos puntos a la vez (estadısticos de multiples puntos) como por ejemplo distribucio-nes multivariables. En la fig. 2.3 se muestran diferentes realizaciones que comparten el mismovariograma, sin embargo, difieren en caracterısticas como conectividad, ademas de ser visible-mente diferentes.

2.2.7. Kriging

El problema de estimacion del valor de una variable Z en una posicion u del espacio, esuno de los mas importantes de la geoestadıstica. Para su resolucion es necesaria la existencia deun modelo de dependencia espacial de Z [Goo97, pag. 125]. Dado este modelo, la forma con-vencional de resolver este problema es mediante kriging, metodologıa que se basa en minimizar

14

(a) (b) (c)

Figura 2.3: Ejemplo de realizaciones con el mismo variograma pero con diferentes caracterısticasde conectividad espacial. Extraıdo de [Eme07a].

el error cuadratico medio tomando en cuenta unicamente datos relacionados con la variable a serestimada.

Kriging resuelve el problema de estimar el valor de una variable continuaZ en una posicionu, en donde este valor es desconocido, usando valores de Z conocidos sobre el area de estudioA. En la practica solo los n(u) datos mas cercanos a u son considerados:

U = {uα : α = 1, . . . , n(u)} (2.17)

Se usan las siguientes notaciones:

Zα = Z (uα) La variable aleatoriamα = m (uα) Esperanza de Z (uα)

σ2α = σ2

uα Varianza de Z(uα)

σαβ = σ (uα,uβ) Covarianza entre Z (uα) y Z (uβ)

con lo que se cumple que σαα = σ2α.

Kriging simple (SK, por sus siglas en ingles), una de las variantes de kriging, calcula elestimador lineal Z∗ utilizando las variables aleatorias Zα, α = 1, . . . , n(u) y asumiendo lasesperanzas m0 y mα, α = 1, . . . , n(u) conocidas e iguales. Z∗ se calcula como:

Z∗ =∑α

λαZα + λ0 (2.18)

Los valores de λ0 y λα, α = 1, . . . , n(u) se consiguen de minimizar el error cuadratico medio[CD99] que puede ser escrito como:

E{

(Z∗ − Z)2}

= V ar {Z∗ − Z}+ E {Z∗ − Z}2 (2.19)

15

Para minimizar el error cuadratico medio se debe minimizar V ar {Z∗ − Z}. AdemasE {Z∗ − Z} debe ser cero, con lo que se impone la condicion de insesgo:

E {Z∗} = E {Z} (2.20)

Reemplazando Z∗ en la ecuacion 2.20 por el lado derecho de la ecuacion 2.18 y, dado que E {Z}es un valor conocido con valor m, se tiene que:

E

{∑α

λαZα + λ0

}= E {Z} (2.21)∑

α

λαmα + λ0 = m (2.22)

λ0 = m−∑α

λαmα (2.23)

Luego, reemplazando λ0 en la ecuacion 2.18, Z∗ puede ser calculado como:

Z∗ = m+∑α

λα (Zα −mα) (2.24)

Definiendo la variable aleatoria con esperanza cero R(u) = Z(u)−m(u) , se calcula su estima-dor R∗ utilizando la ecuacion 2.24 como:

R∗ =∑α

λαRα (2.25)

Del resultado anterior se concluye que la estimacion de una variable aleatoria con esperan-za conocida es equivalente a la estimacion de una variable aleatoria con m = 0 y λ0 = 0. Dadaesta equivalencia, en adelante se asume que Z(u) tiene esperanza igual a cero.

Resta calcular los valores de λα α = 1, . . . , n(u), los que se obtienen minimizando lavarianza del error:

σ2E = V ar{Z − Z∗} (2.26)

16

Se tiene entonces que:

σ2E = V ar

{Z −

∑α

λαZα

}(2.27)

= E

(Z −

∑α

λαZα

)2− E

{Z −

∑α

λαZα

}2

(2.28)

= E

(Z −

∑α

λαZα

)2 (2.29)

= E

{Z2 − 2

∑α

λαZZα +∑α,β

λαλβZαZβ

}(2.30)

= E{Z2}− 2

∑α

λαE {ZZα}+∑α,β

λαλβE {ZαZβ} (2.31)

= σ2 − 2∑α

λασ0α +∑α,β

λαλβσαβ (2.32)

Derivando con respecto a λα para todo α = 1, . . . , n(u) se obtiene el siguiente sistema deecuaciones conocido como sistema de ecuaciones normales:

σ0α =∑β

λβσαβ ∀α = 1, . . . , n(u) (2.33)

Bajo el supuesto de estacionaridad, la covarianza entre dos puntos σαβ solo depende de ladistancia entre estos, es decir:

σαβ = C(h), en donde h = uα − uβ (2.34)

Contando con un modelo de covarianzas C(h), que puede ser inferido a partir de un va-riograma que represente la variabilidad espacial de la variable en estudio, es posible resolver elsistema de ecuaciones inferido a partir de la ecuacion 2.33 obteniendo ası los valores de λα conlos que se construye el estimador.

17

Finalmente, la varianza de kriging se obtiene de reemplazar la ecuacion 2.33 en 2.32:

σ2E = σ2 − 2

∑α

λασ0α +∑α

λα∑β

λβσαβ (2.35)

σ2E = σ2 − 2

∑α

λασ0α +∑α

λασ0α (2.36)

σ2E = σ2 −

∑α

λασ0α (2.37)

Los resultados mostrados corresponden a kriging simple (SK). Existen otras variantes quese diferencian por la forma en que se modela m(u) [Goo97], estas son kriging ordinario (OK) ykriging con un modelo de tendencia (KT).

2.3. Estudio de variabilidad local

Otro problema interesante en geoestadıstica es la modelacion de la variabilidad del atributoen puntos donde este es desconocido [Goo97]. Contar con un modelo de incerteza local permiteevaluar los riesgos involucrados al momento de tomar decisiones.

Para modelar la incerteza, Z(u) puede ser estudiada de dos formas:

1. Obteniendo el intervalo de confianza local de Z(u) mediante la varianza de kriging σ2E .

2. Modelando la distribucion de probabilidad de la variable aleatoria Z(u).

Utilizando la varianza de kriging resulta sencillo construir un intervalo de confianza, porejemplo, el intervalo de 95 % de confianza [Goo97, pag. 261]:

Prob {Z(u) ∈ [z∗(u)− 2σE(u), z∗(u) + 2σE(u)]} = 0, 95 (2.38)

El estudio de la incerteza mediante el establecimiento de un intervalo de confianza es sen-cillo y solo necesita de una medida de la correlacion espacial de la variable. Sin embargo, suponelas dos siguientes hipotesis:

1. La estimacion del error (z∗(u)− z(u)) sigue una distribucion Gaussiana.

2. La varianza del error σ2E(u) es independiente del valor de los datos, es decir, solo depende

de la configuracion de las variables.18

Ademas, solo entrega incerteza local. Muchas veces es de interes la incerteza conjuntade varios puntos simultaneamente. Dada las limitaciones de la construccion de intervalos deconfianza utilizando la varianza de kriging, un enfoque mas preciso para estudiar la variabilidades modelar la distribucion de probabilidad de variable aleatoria Z(u) mediante alguna funcionde distribucion

F (u; z | (n)) = Prob {Z(u) ≤ z | (n)} (2.39)

El intervalo de confianza puede ser construido a partir de la funcion de distribucion como:

Prob {Z(u) ∈ (a, b] | (n)} = F (u; b | (n))− F (u; a | (n)) (2.40)

A diferencia de la varianza de kriging, el intervalo de confianza obtenido a partir de lafuncion de probabilidad es independiente de cualquier estimacion z∗(u) del valor desconocidoz(u). Por otro lado, la distribucion ahora depende tanto de los valores como de la configuracionde los datos condicionantes (n).

2.3.1. Funcion de distribucion multi-Gaussiana

La forma mas facil de obtener funciones de distribucion acumulativas para cada variablealeatoria Z(u), u ∈ A, es asumiendo un modelo de distribucion multivariado para la funcionaleatoria Z(u) [Goo97, pag. 265]. Cada funcion de distribucion F (u; z | (n)), ∀u ∈ A de-be tener la misma expresion analıtica y ser completamente especificada con pocos parametrosde modo que el problema de encontrar tal distribucion se reduce a estimar dichos parametros;esperanza y varianza. El modelo multi-Gaussiano de funcion aleatoria es el mas usado, princi-palmente por lo sencillo que resulta la inferencia de sus parametros.

El modelo Gaussiano de funcion aleatoria es unico en estadıstica por su extrema simplici-dad analıtica y por ser la distribucion lımite de varios teoremas conocidos como “teoremas dellımite central”. Si un fenomeno espacialmente continuo Z(u),u ∈ A es generado por la sumade un numero (no muy grande) de fuentes independientes yk(u),u ∈ A, k = 1 . . . K, con dis-tribuciones espaciales similares, entonces, su distribucion espacial puede ser modelada por unmodelo Gaussiano multivariado:

Z(u) =K∑k=1

Yk(u) ≈ Gaussiano (2.41)

19

La mayor restriccion es la hipotesis de independencia de las funciones aleatorias Yk(u) yaque en los procesos geologicos, que han generado los fenomenos en estudio, raramente son in-dependientes entre sı. A pesar de que la hipotesis de independencia no es respetada, los modelosGaussianos son los preferidos para modelar variables continuas dada las muchas bondades queestos modelos poseen.

Un modelo de funcion aleatoria multivariado puede ser definido en termino de sus pro-piedades, la funcion aleatoria Y (u) = {Y (u), u ∈ A} sigue una distribucion multivariadaGaussiana si y solo si:

1. Todos los subconjuntos de la funcion aleatoria, por ejemplo, {Y (u),u ∈ B ⊂ A}, tambienson multi-Gaussianos.

2. Todas las combinaciones lineales de los valores aleatorios Y (u) son normalmente distri-buidas, es decir, X =

∑nα=1 λαY (uα) es normalmente distribuida, ∀n,∀λα,uα ∈ A.

3. Covarianza cero implica completa independencia. Si Cov{Y (u), Y (u′) = 0}, las dos va-riables aleatorias, Y (u) e Y (u′), no son solo no correlacionadas sino que tambien inde-pendientes.

4. Todas las distribuciones condicionales de cualquier subconjunto de la funcion aleatoriaY (u), dada realizaciones de cualquier otro subconjunto, son normales multivariadas.

Para el caso K = 1, en que la variable aleatoria Y (u) modela algun valor y(u), la ccdf deY (u), dado n datos yα, α = 1, . . . , n, es normal y completamente caracterizada por:

su esperanza condicional, estimada a partir de la esperanza de SK de y(u), y∗SK(u);

su varianza condicional, estimada con la varianza de SK, σ2SK(u).

De este modo, la funcion de distribucion condicional acumulativa es modelada como:

[G(u; y|(n))]∗SK = G

(y − y∗SK(u)

σSK(u)

)(2.42)

Transformacion Cuantil a Cuantil

La primera condicion que debe cumplirse para que una funcion aleatoria estacionaria Y (u)sea multi-Gaussiana es que su funcion de distribucion acumulativa univariada sea normal, esdecir,

Prob {Y (u) ≤ y} = G(y), ∀y (2.43)20

donde G(·) es la funcion de distribucion acumulativa Gaussiana estandar (esperanza cero y va-rianza uno) e Y (u) se encuentra en forma estandar.

Lamentablemente, variables geologicas, tales como la ley de un elemento de interes, nopresentan histogramas simetricos Gaussianos, lo que no es un problema mayor dado que se puedeemplear una transformacion no lineal, conocida como Normal Score Transform, para transformarla distribucion presente a otra normal. Dada la variable aleatoria Z se puede obtener, medianteuna transformacion cuantil a cuantil Y = ϕ(Z), la variable aleatoria Y que cumple con estaprimera restriccion. Para mas detalles sobre la transformacion ver [DJ92, pag. 141] [Goo97, pag.266].

2.3.2. Funcion de distribucion de indicadores

El enfoque multi-Gaussiano supone fuertes suposiciones acerca de la ditribucion multi-punto de los datos. Bajo un enfoque multi-Gaussiano, valores extremadamente grandes y pe-quenos son espacialmente no correlacionados, imposibilitando modelar, por ejemplo, la conecti-vidad de valores extremos.

Existe un segundo enfoque, no parametrico, que no requiere del supuesto de Gaussianidaddel modelo. Este enfoque no asume ninguna forma en particular de la distribucion condicional.En lugar de basarse en un modelo analıtico, F (u; z | (n)) es modelado a traves de una serie deK umbrales zk discretizando el rango de variacion de z.

F (u; zk | (n)) = Prob {Z(u) ≤ zk | (n)} k = 1, . . . , K (2.44)

La distribucion final es obtenida mediante interpolaciones para cada clase (zk, zk+1] y ex-trapolaciones para aquellos puntos mas alla de los extremos z1 y zK .

La funcion de distribucion de indicadores se basa en la interpretacion de la probabilidadcondicional (2.44) como la esperanza condicional de un indicador I(u; zk), dada la informacioncondicional (n).

F (u; zk | (n)) = E {I(u; zk)|(n)} (2.45)

con

I(u; zk) =

{1 si Z(u) ≤ zk;0 en otro caso

21

Kriging de indicadores

El uso de indicadores permite que diferentes tipos de informacion sean usados en conjunto.El estimador de kriging del indicador i(u; zk) puede ser usado como modelo para la funcion dedistribucion acumulativa condicional de Z(u) para un valor umbral zk dado:

[F (u; zk | (n))]∗ = [i(u; zk)]∗krig. (2.46)

Se obtiene el estimador mediante kriging usando el valor del indicador i(u; zk) para cualquierposicion u expresado en SK:

[I(u; zk)]∗ = E {I(u; zk)}+

n(u)∑α=1

λα(u; zk)[I(u; zk)− E {I(uα; zk)}] (2.47)

Kriging Simple de Indicadores (SIK, por sus siglas en ingles), asume la media del indicadorconocida y constante a traves de A:

E {I(u; zk)} = F (zk), conocida ∀u ∈ A (2.48)

luego el estimador es escrito como:

[F (u; sk | (n))]∗SIK = [I(u; sk)]∗SIK (2.49)

= F (zk) +

n(u)∑α=1

λSKα (u; zk)[I(uα; zk)− F (zk)] (2.50)

=

n(u)∑α=1

λSKα (u; zk)I(uα; zk) + λSKm F (zk) (2.51)

donde:

λSKm = 1−n(u)∑α=1

λSKα (u; zk) (2.52)

Los pesos de SIK son obtenidos del siguiente sistema:

n(u)∑β=1

λSKβ (u; zk)CI(uα − uβ; zk) = CI(uα − u; zk) α = 1, . . . , n(u) (2.53)

donde CI(h; zk) es la funcion de covarianza del indicador I(u; zk) para el umbral zk.

22

2.3.3. Simulacion Gaussiana

La simulacion multi-Gaussiana condicional permite obtener realizaciones de igual proba-bilidad de una funcion aleatoria. Cada variable es simulada secuencialmente de acuerdo a succpdf completamente caracterizada por los estimadores de esperanza y varianza de kriging. Lainformacion condicionante consiste en todos los datos muestrales mas todos los valores previa-mente simulados encontrados en la vecindad del valor a ser simulado, lo que se conoce comosimulacion secuencial. De esta forma, es posible reproducir variabilidad entre valores simulados.

El algoritmo de simulacion condicional de una variable aleatoria continua Z(u) modeladapor una funcion aleatoria Gaussiana Z(u) es el siguiente:

1. Encontrar la ccpdf univariada F (u; z) representativa del area completa de estudio.

2. Utilizando la ccpdf F (u; z), realizar la transformacion cuantil a cuantil (Normal ScoreTransform) sobre los datos z(u) para obtener los nuevos datos y(u) que siguen una ccpdfnormal estandar.

3. Comprobar la normalidad bivariada de Y , es decir, que la cpdf bivariada de cualquier parde valores Y (u), Y (u + h),∀u, ∀h es normal. En [DJ92, pag. 142], se muestran formasde realizar esta comprobacion.

4. Si una funcion aleatoria multi-Gaussiana puede ser adoptada para la variable Y (u), esdecir se cumple la condicion anterior, entonces:

Calcular y modelar su variograma.

Definir un camino aleatorio para visitar cada nodo a ser simulado solo una vez.

Utilizar SK con el modelo de variograma para determinar la esperanza y la varianzade la ccpdf de la funcion aleatoria Y (u) en la posicion u.

Obtener un valor simulado y(l)(u) a partir de la ccpdf establecida.

Anadir el valor simulado a los datos. Pasa a formar parte de la informacion condicio-nante.

Proceder en la posicion siguiente, e iterar hasta que todas las posiciones hayan sidosimuladas.

5. Transformar los valores simulados {y(l)(u),u ∈ A} en valores simulados de la variableoriginal {z(l)(u) = ϕ−1(y(l)(u)),u ∈ A}.

La coleccion de software geoestadıstico GSLIB1 cuenta con una implementacion de estealgoritmo llamada sgsim.

1Disponible en http://www.statios.com/Quick/gslib.html.23

2.3.4. Simulacion de variables categoricas

Se presentan las metodologıas mas utilizadas para la simulacion de variables categoricas, esdecir, una variable aleatoria Z(u) cuyas realizaciones pueden tomar uno de K diferentes valoress1, . . . , sk.

Simulacion secuencial de indicadores

La metodologıa consiste en determinar mediante indicadores la presencia o ausencia decada una de las K categorıas en el punto u, bajo la restriccion de que al punto u se le puede asig-nar solo una categorıa. Un ejemplo de una realizacion para 3 categorıas con iguales proporcionespero diferentes variogramas es mostrado en la fig. 2.4.

Figura 2.4: Ejemplo de simulacion secuencial de indicadores. Las tres categorıas tienen la mismaproporcion pero diferente variograma.

El primer paso es asignar a cada punto muestreado un vector de K indicadores en que suvalor K-esimo indique la presencia o ausencia de la K-esima categorıa, de esta forma se defineel indicador como:

Ik(u; sk) =

{1 si sk esta presente en u0 si sk no esta presente en u (2.54)

Se define el variograma del indicador para sk como:

γI =1

2n(h)

∑n(h)

[I(u; sk)− I(u + h; sk)]2 (2.55)

24

Cabe senalar que para el caso de dos variables, los variogramas de indicadores son identi-cos.

Utilizando SIK se estima la probabilidad de que en un punto determinado ocurra una ciertacategorıa. Se puede crear una funcion de distribucion acumulativa a partir de las estimacionespara las K categorıas. Finalmente se determina el valor del punto a asignar mediante una simu-lacion de Monte Carlo.

Los pasos de la metodologıa son los mismos que simulacion Gaussiana, con la salvedad deque los datos muestrales deben ser mapeados a indicadores y que la distribucion de probabilidadacumulativa debe ser construida de la forma anteriormente senalada.

Simulacion Gaussiana truncada

Consiste en obtener una realizacion categorica a partir de la truncacion de una realizacionde una funcion aleatoria Gaussiana Y , segun diferentes umbrales de corte. Dadas K categorıas ysus medias pi; i = 1, . . . , K se definen los umbrales para cada categorıa como:

yi = G−1

(i∑

j=1

pj

)i = 1, . . . , K − 1. (2.56)

Figura 2.5: Umbrales de corte para 4 categorıas con igual proporcion. Los umbrales correspondena G−1(0, 25) = −0, 6745, G−1(0) = 0 y G−1(0, 75) = 0, 6745.

En la fig. 2.5 es ilustrada una distribucion con los umbrales de corte para 4 categorıascon igual proporcion. Luego, la variable categorica I(u; y1, . . . , yK−1) se obtiene de truncar lafuncion aleatoria continua Y :

I(u; y1, . . . , yK−1) =

categorıa 1 si y < y1categorıa k si yk−1 < y < ykcategorıa K − 1 si y > yk−1

(2.57)

25

La aplicacion de esta tecnica para mas de 2 categorıas se torna complicada, ya que surgeel problema de la jerarquizacion de las variables, es decir, el ordenamiento de estas variables. Ladefinicion de la funcion categorica I deja de ser unica para mas de 2 categorıas y se hace necesa-rio definir los contactos de cada variable. Dada esta dificultad, esta metodologıa es generalmenteusada para 2 categorıas.

El variograma de la variable Gaussiana γ(h) y el de la variable de indicadores γI,y(h) estanrelacionados de la siguiente forma:

γI,y(h) = G(y) [1−G(y)]− 1

2π

∫ arcsen(1−γ(h))

0

exp

(− y2

1 + senθ

)dθ. (2.58)

Utilizando la relacion anterior se obtiene el variograma Gaussiano γ(h) luego de haberobtenido el variograma de indicadores γI,y(h) a partir de datos muestrales. Finalmente, las reali-zaciones se obtienen de truncar las realizaciones Gaussianas obtenidas utilizando el variogramaγ(h).

En la fig. 2.6 son mostrados dos ejemplos de simulacion Gaussiana para dos categorıas.

Simulacion plurigaussiana

Esta metodologıa es una generalizacion de la simulacion Gaussiana truncada, la idea ahoraes truncar una distribucion multi-Gaussiana. Se introduce la idea de “bandera” que sirve paradefinir los contactos de modo de tener categorıas concordantes entre sı y otras discordantes. Enla fig. 2.7 se muestran diferentes realizaciones para diferentes definiciones de banderas.

La metodologıa puede ser resumida en los siguientes pasos:

1. Inferir los parametros a partir de los datos del modelo, esto es: tipo de bandera, umbrales,variograma de las Gaussianas.

2. Simular los valores de las Gaussianas en los puntos de muestreo, condicionados por losdatos categoricos.

3. Simular los valores de las Gaussianas en todo el espacio.

4. Obtener la realizacion categorica mediante truncaciones.

26

Figura 2.6: Ejemplos de simulacion Gaussiana truncada. Extraıdos de [Eme07b].

27

Figura 2.7: Ejemplos de realizaciones plurigaussianas para diferentes banderas. Extraıdos de[Eme07b].

2.3.5. Simulacion multi-punto

Estos algoritmos de simulacion van mas alla de la simple reproduccion de informacionestadıstica bivariada (por ejemplo: modelo de covarianzas o variograma). Intentan reproducirinformacion a partir de la relacion de mas de dos puntos a la vez, a diferencia de los metodosconvencionales (Gaussianos) de simulacion que solo utilizan la relacion entre dos puntos (a travesde la covarianza). Estadısticos de mayor orden, como covarianzas de multiples puntos obtenidas,por ejemplo, desde imagenes de entrenamiento, pueden mejorar considerablemente realizacionesde imagenes estocasticas [GS93]. La simulacion multi-punto busca la reproduccion explıcita deestadısticos de mayor orden generando realizaciones que caracterizan espacialmente el fenomenosubyacente mas precisamente.

En [GS93] se desarrolla una notable metodologıa que extiende el kriging simple de in-dicadores. Se caracteriza por su simpleza ya que no necesita contar a priori con un modelo decovarianzas. Esta metodologıa permite la generacion de realizaciones de funciones aleatoriasdiscretizadas que respetan cualquier numero de covarianzas de indicadores de multiples puntos.Esta tecnica es aplicada a la reproduccion estocastica de imagenes de fenomenos de estructurascomplejas que no pueden ser representadas por estadısticos de dos puntos.

En las metodologıas convencionales, la estructura espacial es impuesta a partir de algunamedida de correlacion entre Z(u) y Z(uα). En simulacion multi-punto esto se realiza conside-

28

rando de manera conjunta la covarianza entre Z(u) y los n datos condicionantes dn denominadosdata-event. Por lo tanto, se necesita una covarianza de (n+ 1) puntos para medir la dependenciade Z(u) con dn.

Sean zk, k = 1, . . . , K los K estados que puede tomar la variable aleatoria Z(u). Se defineel indicador Aα asociado a la ocurrencia del estado zk en la posicion u como:

Ak =

{1 si Z(u) = zk0 si no (2.59)

y el indicador D, variable aleatoria asociada a la ocurrencia de dn, formado por n datos condi-cionantes S(uα) = zkα , α = 1, . . . , n considerados de forma conjunta, como:

D =

{1 si Z(uα) = zkα ∀α = 1, . . . , n0 si no (2.60)

La probabilidad condicional del evento Ak dado los n eventos Aα, α = 1, . . . , n es igual ala esperanza condicional del indicador Ak:

Prob {Ak = 1|Aα, α = 1, . . . , n} = E {Ak | D = 1} (2.61)≡ [Ak]

∗SIK = E {Ak}+ λ[1− E {D}] (2.62)

en donde [Ak]∗SIK es el estimador de Ak dado por kriging simple de indicadores para el indicador

unico de eventos D =∏n

α=1Aα con D = 1.

El sistema normal de ecuaciones se reduce a una unica ecuacion normal (single normalequation) [Jou93]:

λVar {D} = Cov {Ak, D} (2.63)

Se cumple que:

E {D} = Prob {D = 1} (2.64)Var {D} = E {D}[1− E {D}] (2.65)

Cov {Ak, D} = E {AkD} − E {Ak}E {D} (2.66)E {AkD} = Prob {Ak = 1, D = 1} (2.67)

luego, reemplazando la expresion de λ obtenida de (2.63) en (2.62):

E {Ak | D = 1} = E {Ak}+Cov {A,D}

Var {D}(1− E {D}) (2.68)

29

reemplazando Var {D} por (2.65):

E {Ak | D = 1} = E {Ak}+Cov {A,D}

E {D}(2.69)

y finalmente reemplazando Cov {A,D} por (2.66) se obtiene:

E {Ak | D = 1} =E {Ak}E {D}

=P{Ak = 1, D = 1}

Prob {D = 1}(2.70)

que corresponde al resultado del teorema de Bayes. Por lo tanto, el problema de encontrar unafuncion de distribucion condicionada a n datos, tomando en cuenta tanto su configuracion es-pacial como los valores de cada evento en forma conjunta, se traduce al problema de estimarel numerador y el denominador de (2.70) mediante conteo de frecuencias de aparicion en unaimagen de entrenamiento, sin la necesidad de contar con una medida de covarianzas. Definiendock(dn) y c(dn) como el numerador y el denominador de la ecuacion (2.70), respectivamente, lafuncion de distribucion se obtiene como sigue:

F (u; zk | (n)) = Prob {Ak = 1 | D = 1} ' ck(dn)

c(dn)(2.71)

Algoritmo ENESIM

Del resultado de la ecuacion 2.70 y de la obtencion de las probabilidades a traves delconteo de patrones, en [GS93] se propone el algoritmo ENESIM (Extended Normal EquationSIMulation, por sus siglas en ingles). Los pasos de este algoritmo son los siguientes:

1. Definir un camino aleatorio que recorra todos las posiciones ui ∈ A con valores descono-cidos.

2. En cada posicion ui obtener n (n = 16 en los ejemplos de [GS93]) datos codificadoscomo indicadores, restringidos a obtener n/4 indicadores en cada cuadrante con centro enui. Buscar en la imagen de entrenamiento las frecuencias del numerador y denominadorde (2.70). La probabilidad es estimada solo si existe un mınimo (fijado en 20 en [GS93])de patrones. De lo contrario, el nodo mas lejano del patron es eliminado y la busqueda esrepetida hasta satisfacer el mınimo numero de apariciones requeridas.

3. A partir de la probabilidad condicional de la ecuacion 2.70, obtener un valor simulado parala posicion actual ui. Este valor simulado pasa a formar ahora parte del conjunto de datosy es usado para condicionar otras posiciones en las siguientes iteraciones del algoritmo(principio de simulacion secuencial).

30

4. Moverse a la siguiente posicion ui+1, segun el camino determinado en el paso 1, y repetirlos pasos 2 y 3 hasta que todas las posiciones hayan sido visitadas.

Si una nueva realizacion es requerida repetir el algoritmo completo.

Algoritmo SNESIM

En [Str02] la tecnica es mejorada. Se incorpora la utilizacion de una estructura de datosllamada arbol binario que es usada para construir una base de datos de patrones para la busquedade frecuencias de aparicion. De esta forma, la obtencion de la frecuencia de aparicion de patronesdeja de ser realizada directamente desde la imagen de entrenamiento con lo que el procedimientoes acelerado.

La distribucion de probabilidad condicional a un data-event dn′ , asociado a un subtemplateτn′ de τn (n′ ≤ n), puede ser recuperada de la funcion de distribucion condicional a dn asociadoa τn, para el cual dn′ es subconjunto, de la siguiente forma:

c(dn′) =∑

dn asoc. con τndn′ ⊂ dn

c(dn) (2.72)

De forma analoga para ck(dn′):

ck(dn′) =∑

dn asoc. con τndn′ ⊂ dn

ck(dn) (2.73)

Utilizando el resultado de la propiedad anterior, se define un template maximo utilizadopara almacenar en la estructura de datos las frecuencias recuperadas a partir de la imagen deentrenamiento.

2.3.6. Markov random fields

En [DK07] es mostrado que los algoritmos secuenciales pueden ser vistos como MarkovRandom Fields (MRF). MRF asume que la distribucion condicional de probabilidad de las cate-gorıas para Z(u), dado todos los otros nodos de A denotados por z(u), es igual a la distribucion

31

condicional de Z(u) dada una vecindad mucho mas pequena dn(u), es decir,

F (Z(u); z | z(y)) = F (Z(u); z | dn(u)) (2.74)

MRF tiene como inconveniente que es difıcil lidiar con problemas de inferencia estadıstica,los algoritmos necesitan ser iterativos y la convergencia es por lo general lenta [DK07].

El enfoque de simulacion secuencial esta basado en la siguiente identidad probabilıstica:

P{Z1, . . . , ZN} = P{Z1}P{Z2 | Z1}P{Z3 | Z1, Z2} . . . P{ZN | Z1, . . . , ZN} (2.75)

donde, Zα = Z(uα).

Esto sugiere que primero se simula un nodo u1, luego otro u2 dado u1 y ası sucesivamente,hasta que todos los nodos son asignados. Para evitar la dependencia de una vecindad demasiadogrande, usualmente se toma un camino aleatorio y se aproxima la distribucion condicionante asu-miendo que las dependencia es solamente dada a partir de una vecindad del punto a ser simulado.Es decir, la ecuacion 2.75 es reemplazada por:

P{Z1, . . . , ZN} = P{Z1 | dZ1}P{Z2 | dZ2} . . . P{ZN | dZN} =N∏i=1

P{Zi | dZi} (2.76)

en donde dZ es el conjunto mas pequeno de puntos que estan dentro de la vecindad de busqueda.Notar que esta formulacion es verdadera incluso para el metodo secuencial en el cual un caminoaleatorio es usado o en el caso donde un camino predefinido es seguido. Por ejemplo, un caminounilateral, definido como aquel que recorre la realizacion moviendose primero segun la coorde-nada X , luego segun la Y y finalmente segun la Z. En caso de seguir un camino unilateral, dz esalgun subconjunto de puntos previamente simulados. Estas pequenas distribuciones condicionan-tes pueden ser tomadas desde una distribucion analıtica o desde una imagen de entrenamiento.

Los miembros de dz son denominados como los padres de z. Los puntos que son simuladosdespues de z, para los cuales z es su padre, son denominados hijos de z.

El algoritmo secuencial puede ser reescrito como un MRF [Dal05] y la distribucion condi-cional es de la forma:

P{Zi | Zi} ∝∏

{j:i∈dj o j=i}

P{Zj | dZj} (2.77)

Por lo tanto, la probabilidad condicional depende de los padres, hijos y padres de hijos delpunto ui.

32

Este enfoque muestra la mayor diferencia entre la eleccion de un camino aleatorio ver-sus uno unilateral. La distribucion condicional del metodo unilateral es la misma para todos lasposiciones llevando al metodo unilateral a un MRF estacionario. Por otro lado, un camino alea-torio produce un conjunto diferente de padres en cada posicion. Esto significa que la distribucioncondicional cambia en cada punto de modo de reproducir un MRF no estacionario.

2.4. Sıntesis de texturas

Sıntesis de texturas se refiere al problema de construir una imagen texturizada a partirde una textura de muestra representada por una imagen, por lo general, de menor tamano. Esteproblema ha sido estudiado por varios anos en vision computacional, donde la sıntesis de texturases usada para segmentacion y clasificacion; y en computacion grafica, con aplicaciones comorendering, compresion y edicion de imagenes. Una buena recopilacion sobre analisis de texturaspuede ser encontrado en [MXS08].

2.4.1. Nocion de textura

Resulta difıcil e impreciso dar una definicion exacta de textura, por ende, existen variosintentos de definiciones que varıan dependiendo del area de estudio. Como en muchas cosas,es mas facil nombrar las propiedades de algo que encontrar su definicion. Textura usualmentese entiende como la percepcion de una superficie ante el tacto. Esta definicion da cuenta de lacomposicion 3D de la superficie de un objeto aparentemente liso, ampliando nuestra percepcionsensorial del objeto a algo mas que puramente visual. Esta caracterizacion es percibida comoalgo comun, repetible, presente en distintas posiciones del objeto, es decir, es una caracterısti-ca estacionaria. Esta forma de caracterizar una superficie, se refiere entonces, a la variabilidadespacial de algo aparentemente liso. Se podrıa luego decir que conocemos una textura cuandopodemos crear un modelo que permite reproducir dicha textura o variabilidad.

La nocion anterior de textura, como algo puramente tactil, permite dar una definicion detextura valida y aceptada en computacion grafica, definiendola como una propiedad de la imagenmas que como una propiedad de la superficie del objeto. Segun esta definicion, una textura esuna imagen formada de patrones repetidos. Esta definicion puede ser llevada mas alla que algopuramente visual, modelando la variabilidad espacial mediante la reproduccion de patrones.

Ahora bien, una textura es una mezcla de aleatoriedad y periodicidad. Si una variaciones perfectamente periodica el fenomeno es mejor descrito como un “patron periodico”, por elcontrario, si un patron es completamente aleatorio entonces es mejor descrito como un “patronde ruido” que como una textura. Sin embargo, si un patron tiene tanto aleatoriedad como re-

33

gularidad, este sera descrito como una textura [MXS08, pag. 4]. Hay que notar que esta ultimadefinicion de textura, es algo mas bien perceptual y no del todo relevante a los algoritmos deanalisis y sıntesis de texturas.

Entendiendo una textura como un conjunto de patrones que se repiten estacionariamente,no resuelve el problema de segmentacion de texturas ni de interpolacion. Encontrar funciones dedistribucion aleatoria de estos patrones que permitan diferenciar estadısticamente entre diferentespatrones es un problema abierto y no trivial. Diferentes metodologıas han sido estudiadas parala representacion de texturas, por ejemplo: matrices de co-ocurrencias, uso de variados filtrosmediante convoluciones, analisis de componentes principales, medidas basadas en fractales yMRF.

2.4.2. Analisis de texturas

Existen casos donde la textura puede ser modelada estructuralmente, por ejemplo, en untablero de ajedrez. Por el contrario, existen otros casos donde resulta mas real la representa-cion mediante un modelo estocastico, por ejemplo, si se intenta modelar la textura de la arenaen una playa. En [LHW+04] se da una clasificacion de texturas dependiendo de su regularidad,espectro que abarca desde las texturas completamente regulares hasta las estocasticas. Las textu-ras regulares son simplemente patrones periodicamente repetidos en intervalos, por el contrario,las texturas estocasticas se asemejan mas a ruido. Hay un espectro de texturas entre estos dosextremos tal como se muestra en la fig. 2.8.

La representacion, el aprendizaje y la computacion eficiente de estos patrones visuales sonproblemas fundamentales en vision computacional.

Figura 2.8: Espectro de texturas en que las texturas estan ordenadas de acuerdo a la regularidadde su variacion estructural. Imagen tomada de [LHW+04].

34

Los metodos para analisis de texturas pueden ser resumidos en las siguientes clases[MXS08, pag. 36] [Pag99]:

Metodos estadısticos Las texturas son representadas a partir de un conjunto de caracterısticas,como por ejemplo, matrices de co-ocurrencia [HDS73, Har79]. Estas caracterısticas nopermiten la reconstruccion de la textura, por lo que estos metodos son generalmente utili-zados para clasificacion.

Metodos espectrales Realizan analisis mediante las distribuciones obtenidas de aplicar un con-junto de filtros. Estos metodos son utiles para clasificacion y segmentacion.

Metodos estructurales Estos metodos se basan en modelar las texturas a traves de un conjuntode primitivas o subpatrones llamados textons. La correcta identificacion de estas primitivases difıcil. Es posible la construccion de texturas conociendo las reglas de posicionamien-to de estos subpatrones. Una buena revision de estos metodos puede ser encontrada en[Har79].

Metodos estocasticos Se asume que la textura es el resultado de un proceso estocastico que esregulado por un conjunto de parametros. El analisis consiste en definir el modelo a utilizary en estimar sus parametros.

Aunque existen diferentes metodologıas, el problema continua siendo el mismo: encontrarun modelo que sea capaz de caracterizar completamente la textura. Si mediante este modelo esposible lograr su reproduccion, el modelo habra captado la esencia de la textura.

Tratamiento multi-resolucion

El uso de multi-resolucion, o tratamiento multi-escalar, apunta al concepto de escala. Deforma similar al termino utilizado en cartografıa, se refiere a la medida de “alejamiento” delobjeto que esta en proporcion con la perspectiva que se tome para observarlo. De esta forma,a mayor escala se pueden distinguir detalles, pero se pierde la visualizacion global, y viceversa[Vie01].

Al utilizar patrones muy grandes, para capturar grandes estructuras, los algoritmos de si-mulacion o de sıntesis se ven drasticamente afectados en terminos de rendimiento. Para lidiarcon esta problematica se desea representar la imagen en una menor escala, reduciendo su dimen-sionalidad.

35

Convolucion

Formalmente, una convolucion es una operacion entre 2 funciones f y g, produciendo unatercera funcion que es vista como una version modificada de una de las funciones originales. Laconvolucion de f y g es denotada como f ∗ g y es definida como la integral del producto de dosfunciones despues de que una es invertida y desplazada una distancia τ , es decir,

(f ∗ g)(t) =∫∞−∞ f(τ)g(t− τ)dτ

=∫∞−∞ f(t− τ)g(τ)dτ

(2.78)

A medida que t cambia se enfatizan diferentes partes de la funcion de input.

Convolucion discreta

La convolucion discreta de dos funciones f y g es definida como:

(f ∗ g)(n) =∑∞

m=−∞ f(m)g(n−m)=

∑∞m=−∞ f(n−m)g(m)

(2.79)

En el caso de datos en 2 dimensiones, por ejemplo en matrices o imagenes, se define laconvolucion de matrices, en donde se obtiene una matriz C como resultado de convolucionar lamatriz A con la matriz B.

El tamano de C en cada dimension es igual a la suma de los tamanos de las matrices Ay B en las dimensiones correspondientes, menos uno. Si se desea obtener una matriz de igualdimensionalidad que A es posible tomar los elementos centrales de C con la dimensionalidaddeseada. La manera de calcular la convolucion de una funcion c que depende de dos variablesdiscretas, m y n, es

c(m,n) =∞∑

i=−∞

∞∑j=−∞

a(i, j)b(m− i, n− j) (2.80)

Filtros

Se denomina filtro al resultado de generar una nueva imagen, pıxel por pıxel, a partir dela convolucion entre un vector llamado kernel y un vector formado por la concatenacion delos pixeles extraıdos de la vecindad del pıxel a asignar. Dependiendo del kernel utilizado segeneraran distintos tipos de filtros, siendo las mas utilizadas los Gaussianos y Laplacianos.

36

Los filtros son utilizados para resaltar ciertas caracterısticas de la imagen, por ejemplo,los filtros Gaussianos sirven para suavizar una imagen, reducir el ruido y reducir detalles. Otrosfiltros como el filtro promedio y el filtro mediana, son tambien utilizados para producir suaviza-miento.

Filtro Gaussiano La idea es reemplazar cada pıxel por un promedio ponderado de sus vecinos.Al aplicar un filtro Gaussiano los vecinos mas cercanos toman mas importancia para el resultadoobtenido. En la fig. 2.10 se pueden ver resultados de aplicar un filtro Gaussiano vs. un filtropromedio.

0, 003 0, 013 0, 022 0, 013 0, 0030, 013 0, 059 0, 097 0, 059 0, 0130, 022 0, 097 0, 159 0, 097 0, 0220, 013 0, 059 0, 097 0, 059 0, 0130, 003 0, 013 0, 022 0, 013 0, 003

Figura 2.9: Ejemplo de kernel Gaussiano con σ = 1.

Piramides de multi-resolucion

A partir de una imagen es posible generar una piramide de multi-resolucion, que es una pilade imagenes ordenadas de acuerdo a niveles de resolucion (ver fig. 2.11). La base de la piramidecorresponde a la imagen de mas alta resolucion. A medida que se asciende por la piramideson obtenidas las imagenes de mas baja resolucion, las cuales son utilizadas para representarestructuras de gran escala de forma mas compacta.

Una piramide P de n niveles es construida jerarquicamente, comenzando desde el nivelinferior, el que se asigna a la imagen original (P0 = I). Los niveles superiores son obtenidosmediante submuestreo sobre la imagen inmediatamente inferior luego de aplicar un filtro, dondesubmuestreo se define como:

S↓(I)(x, y) = I(2x, 2y) (2.81)

De esta forma, cada imagen Pi(P) de la piramide, es obtenido como:

Pi(I) = S↓(G ∗Pi−1(I)) (2.82)

donde G es el kernel Gaussiano.

37

(a) Imagen original (b) Filtro promedio

(c) Filtro Gaussiano, σ = 1 (d) Filtro Gaussiano, σ = 3

Figura 2.10: Ejemplo de aplicar distintos filtros para kernels de tamano 7× 7 pixeles.

38

Figura 2.11: Ejemplo de piramide de multi-resolucion. Fuente: Wikimedia(http://upload.wikimedia.org/wikipedia/fr/d/da/Pyramide Image exemple.png).

.

2.4.3. Algoritmos de sıntesis de texturas

La sıntesis de texturas es usada para construir imagenes sinteticas, especialmente encomputacion grafica, en donde generalmente se requieren imagenes realistas, de cualquier for-ma o tamano. El proposito de sıntesis de texturas es, a partir de una textura de muestra, crearuna nueva textura que, ante la percepcion humana, parezca ser generada por el mismo procesosubyacente.

Se debera, por lo tanto, contar con un modelo de la textura que permita su reproduccion,problema que continua siendo abierto. No existe claridad de que realmente es una textura, porlo que determinar lo que la hace unica es un problema no resuelto. Sin embargo, se puede medirque tan bueno (o malo) resulta ser un modelo en el sentido si logra reproducir la textura queintenta representar.

Existen diversas metodologıas para la sıntesis de texturas, cuya calidad depende del algo-ritmo y tambien de la naturaleza de la textura a reproducir. Un buen resumen de dichos metodospuede ser encontrado en [MXS08, pag. 37]. Estas metodologıas son divididas en dos grupos.El primero es compuesto por metodologıas que capturan una unica caracterıstica de la textu-ra. Algunos ejemplos son: modelos de fractales, modelos autorregresivos, modelos de mediamovil, modelos autoregresivos de media movil, Derin-Elliott, Insing y log-SAR. El segundo

39

grupo esta formado por modelos que toman en consideracion caracterısticas mas estructurales yutilizan multi-resolucion basandose principalmente en la respuesta a un conjunto definido de fil-tros de multi-resolucion. El exito de estos modelos depende de la correcta eleccion de los filtrosa utilizar.

Popat y Picard [PP93] y Paget y Longstaff[PL98] lograron resultados satisfactorios uti-lizando modelos de alto orden, no-parametricos y de multi-escala basados en MRF, los cualestiene exito capturando estructuras de gran escala presentes en texturas naturales. Resultan seraltamente efectivos en sıntesis de texturas, sin embargo, no lo son en segmentacion y clasifica-cion. Wei y Levoy [WL00] aceleraron la metodologıa desarrollada por Popat y Picard [PP93] nogenerando explıcitamente una funcion de distribucion.

Modelo de Popat y Picard

El modelo de Popat y Picard se basa en el modelamiento de funciones de distribucion paravectores de alta dimensionalidad. El modelo se obtiene de combinar estimacion de kernel conagrupamiento. El objetivo es obtener una funcion de probabilidad semi-parametrica que resumela imagen de entrenamiento.

La estimacion y el uso de modelos probabilısticos para datos vectoriales tiene inconve-nientes no presentes en el caso escalar. Por ejemplo, para estimar el histograma de una funcionde distribucion de probabilidad de datos de 10 dimensiones con 256 intervalos, el numero to-tal de vectores posibles es realmente alto: 25610 ≈ 1, 2 × 1024 [PP93, pag. 1]. Esto causa dosproblemas:

1. No se puede obtener suficientes datos de entrenamiento para asignar al histograma hasta elpunto de obtener una estimacion confiable de la funcion de distribucion de probabilidad.

2. No se puede contar con suficiente memoria RAM para guardar el resultado.

Dado que en la practica no se contaran con suficientes datos de entrenamiento para com-pletar el histograma, la mayorıa de las frecuencias seran nulas. Resulta esencial para el modeloasignar valores confiables a todos los datos del dominio del histograma, incluyendo aquellos confrecuencia experimental nula. Para lograr estimar el valor de los valores no informados del his-tograma se utiliza el estimador de Parzen [Par62], el cual realiza supuestos sobre la suavidad dela funcion de distribucion de modo que pequenos cambios en el vector causen pequenos cambiosen la funcion de distribucion de probabilidad.

El modelo de Popat y Picard se basa en la obtencion de una funcion de distribucion deprobabilidad basado en agrupamiento. Sea x = [x1, . . . , xN ] un vector aleatorio discreto que

40

sigue una funcion de distribucion de probabilidad p(x). Los elementos xi del vector compartenun alfabeto de K letras, por lo que el alfabeto tiene un total de KN palabras. El metodo obtieneun estimador de p(x) desde un conjunto limitado de vectores X1, . . . ,XL utilizando la regla dela cadena:

p(x) = p(x1, . . . , xN) (2.83)= p(x1)p(x2 | x1)p(x3 | x1, x2) · · · p(xN | x1, . . . , xN−1) (2.84)

La metodologıa combina estimacion de kernel con agrupamiento. El primer paso es agruparlos datos de entrenamiento mediante el algoritmo estandar LGB. La distribucion deseada q(x)es modelada como una suma ponderada de M distribuciones. El numero M es un parametro yesta relacionado tanto con la precision y la complejidad computacional del modelo. Luego,

q(x) =M∑m=1

wmqm(x) (2.85)

donde wm > 0 ∀m,∑M

m=1wm = 1.

Para facilitar la factorizacion de q(x), como en 2.84, se impone que qm, para todo m, seaseparable. Es decir, que se pueda escribir de la forma

qm(x) =N∏n=1

fm,n(xn), (2.86)

donde cada fm,n es una distribucion unidimensional.

Una gran cantidad de elecciones son posibles para los valores de fm,n. Se hace el supuestode que en general la densidad de los puntos de entrenamiento alcanzan peaks en los centros de losclusters y disminuyen de forma suave y monotona desde dichos centros. Por lo tanto, se utilizauna funcion Gaussiana discretizada, es decir,

fm,n(x) = Km,ne−(xn−µm,n)2/(2σ2

m,n) (2.87)

donde Km,n debe permitir que ∑todo x

fm,n(x) = 1 (2.88)

Los parametros µm,n y σm,n son obtenidos tomando la esperanza muestral y la desviacionestandar desde los datos muestrales para cada cluster. El peso wm es obtenido como el numero depuntos dentro del cluster m dividido por el numero total de puntos. Combinando los resultados

41

anteriores finalmente se obtiene que:

q(x) =M∑m=1

wm

N∏n=1

Km,ne−(xn−µm,n)2/(2σ2

m,n) (2.89)

Si xn es el punto a estimar, es necesario obtener q(xn | x1, x2, . . . , xN−1). Se asume queX1, . . . , Xn−1 estan disponibles para ser usados en la obtencion de q(xn | X1, . . . , X −N − 1).Luego el valor deXn es obtenido de procesar q(xn | X1, . . . , X−N − 1). Sea I = {i1, . . . , iN ′},donde N ′ ≤ N , se puede mostrar que:

q(xi1 , . . . , xiN′ ) =M∑m=1

wm∏n∈I

fm,n(xn) (2.90)

es decir, el estimador se puede obtener ignorando las dimensiones no deseadas. Luego, usandoesta propiedad, se obtiene

q(x1) =

∑Mm=1wmfm,1(x1)

C1

q(x2 | X1) =

∑Mm=1[wmfm,1(X1)]fm,2(x2)

C2

q(x3 | X1, X2) =

∑Mm=1[wmfm,1(X1)fm,2(X2)]fm,3(x3)

C3...etc.

(2.91)

en donde Cn es la suma del numerador correspondiente sobre todos los valores de xn. El es-timador puede ser obtenido recursivamente por medio de la variable rm,n que reemplaza lasexpresiones en parentesis cuadrados del resultado anterior. Luego rm,n se define como

rm,n =

{wm si n = 0C ′rm,n−1fm,n(Xn) si 1 ≤ n ≤ N

(2.92)

donde C ′n es definida de modo que∑M

m=1 rm,n = 1, con lo que el estimador buscado se puedeescribir como:

q(xn | X1, . . . , Xn−1) =M∑m=1

rm,n−1fm,n(xn). (2.93)

42

Algoritmo de sıntesis de Popat y Picard

Contando ya con el modelo de distribucion de probabilidad, que permite inferir la proba-bilidad de xn contando con los valores X1, . . . , Xn−1, es posible realizar el proceso de sıntesis.Popat y Picard realizan este proceso siguiendo un camino unilateral. Cada pıxel de la realizaciones asignado de acuerdo a la funcion de distribucion obtenida para el pıxel segun el modelo dePopat y Picard, donde los valores vecinos son valores pre-asignados. La distribucion es obtenidasobre el vector formado por los pixeles de la vecindad obtenidos mediante un template causal,como el mostrado en la fig. 2.12.

El procedimiento consiste entonces en obtener la distribucion para cada pıxel a simularen un orden unilateral utilizando los valores de la vecindad dada por un template causal. Luegoasignar un valor utilizando la distribucion. Antes de comenzar con el proceso de simulaciones necesario entrenar el modelo. El primer paso es obtener la secuencia de vectores muestralesdesde la imagen de entrenamiento. Por cada pıxel en la imagen de entrenamiento, los pixeles dela vecindad y el visitado son concatenados en un vector en que el ultimo pıxel es el visitado. Elmodelo basado en cluster es entrenado utilizando estos vectores. El parametro M es escogidode acuerdo a la capacidad computacional y a la calidad de la realizacion deseada y toma porlo general un valor entre 32 y 2048. Luego las ecuaciones 2.92 y 2.93 son utilizadas para laconstruccion de la distribucion con la que se genera pseudo-aleatoriamente el valor de cada pıxelde la realizacion. En caso de no contar con valores conocidos, para pixeles en los bordes, seasume el valor 128.

El algoritmo es mejorado mediante multi-resolucion. (ver [PP93, pag. 6]). Resultados delalgoritmo utilizando multi-resolucion son mostrados en la fig. 2.13, donde se muestran 8 rea-lizaciones sobre la coleccion de Brodatz de texturas. Para cada textura, la imagen del mediocorresponde al resultado utilizando multiresolucion, mientras que la de la derecha es obtenidamediante una variacion del algoritmo que usa interpolacion.

Figura 2.12: Ejemplo de template causal.

Algoritmo de Wei y Levoy

Wei y Levoy [WL00] [Wei01] desarrollaron un algoritmo de sıntesis de texturas que des-taca por la calidad de sus realizaciones y, sobre todo, por su eficiencia. Si bien la calidad de

43

Figura 2.13: Realizaciones utilizando algoritmo de Popat y Picard. [PP93, pag. 8].

las realizaciones es comparable con otras metodologıas, por ejemplo, la de Popat y Picard, losresultados son obtenidos en tiempos dos ordenes de magnitud menores. Esto es logrado debidoa que no es necesario generar un modelo de probabilidad explıcito, ademas, es posible aumen-tar su eficiencia utilizando un arbol estructural de cuantizacion vectorial (tree-structured vectorquantization) como modelo de los datos. Esta metodologıa tiene otras caracterısticas adicionales:produce realizaciones enlosables, es decir, que se pueden adjuntar sin notar discontinuidades; ycuenta con mınimos parametros que ajustar, solo el tamano del template para la version no ace-lerada y con resolucion unica.

La metodologıa evita el muestreo y la construccion explıcita de distribuciones con lo quese reduce el procesamiento computacional. Se basa en la utilizacion de MRF como modelo paralas texturas. Mediante MRF se modela una textura como una realizacion de un proceso aleatoriolocal y estacionario. Es decir, cada pıxel de una realizacion es caracterizado por un conjuntopequeno de pixeles vecinos y esta caracterizacion es la misma para todos los pixeles.

La textura es generada pıxel por pıxel, y cada pıxel es determinado de modo que la similitudlocal es preservada entre la textura de muestra (imagen de entrenamiento) y la imagen resultante.Este proceso es completamente determinıstico y no necesita la construccion explıcita de unafuncion de distribucion de probabilidad.

44

Figura 2.14: Sıntesis de textura a resolucion unica. (a) Textura de entrenamiento. (b) - (e) Dife-rentes estados de la sıntesis. Fuente: [Wei01, pag. 14.]

El algoritmo propuesto por Wei y Levoy en su version de resolucion unica y sin acelera-cion es muy simple. Se comienza con una textura de muestra Ia y una imagen con ruido Is. Elalgoritmo fuerza a la imagen con ruido Is a parecerse a Ia mediante transformaciones de suspixeles los que son elegidos segun un camino en que primero se recorren sus filas y luego suscolumnas. Para determinar el valor del pıxel p en Is, su vecindad espacial N(p), region en formade “L” (ver fig. 2.14) es comparada contra todos las posibles vecindades N(pi) de Ia. El pıxelpi con la vecindad N(pi) mas similar es asignado a p. Para determinar esta similitud es usadala norma L2 (suma de la diferencia de los cuadrados). El objetivo de este proceso de sıntesis esasegurar que el nuevo pıxel p asignado conservara tanta similitud local entre Ia e Is como seaposible. El mismo proceso es repetido para cada pıxel de Is de modo de que todos los pixelessean determinados.

Para lograr imagenes sinteticas de texturas de gran alcance es necesario utilizar templa-tes mas grandes lo que involucra mas gasto computacional. El algoritmo de sıntesis de Wei yLevoy utiliza piramides de multi-resolucion para manejar esta dificultad. El problema es resultoutilizando templates mas pequenos provenientes de un nivel de baja resolucion de la piramide.

El algoritmo de resolucion multiple construye dos piramides Gaussianas Ga y Gs a partirde Ia e Is, respectivamente. Luego, el algoritmo transforma Gs desde las resoluciones mas bajashasta las mas altas, de modo que cada nivel de resolucion es construido a partir de los nivelesde mas baja resolucion. En cada nivel Gs(L) de la piramide de salida, los pixeles son asignadosen forma similar al algoritmo de resolucion unica. La unica modificacion en el algoritmo es queen el caso de resolucion multiple, cada vecindad N(p) contiene tanto pixeles de la resolucionactual como de niveles de menos resolucion. La similitud entre dos vecindades de resolucionmultiple es medida computando la suma de los cuadrados de la distancia de todos los pixelesdentro de ellas. Los pixeles de menor resolucion restringen el proceso de sıntesis de modo quelas caracterısticas de alta frecuencia que seran anadidas seran consistentes con las estructuras debaja frecuencia.

En la fig. 2.15 son mostrados ejemplos de la utilizacion del algoritmo de Wey y Levoy.Para cada textura de 128× 128 pixeles se muestra una realizacion de tamano 200× 200 pixelesutilizando una piramide Gaussiana de 4 niveles. Para cada nivel de la piramide se considero lavecindad de tamano 3 × 3, 5 × 5, 7 × 7 y 9 × 9, desde el nivel de baja hasta el de mas alta

45

resolucion.

Figura 2.15: Ejemplos de realizaciones utilizando algoritmo de Wey y Levoy [Wei01, pag. 24-25]. Se utiliza una piramide Gaussiana de 4 niveles. Para cada nivel se considera la vecindad detamano 3× 3, 5× 5, 7× 7 y 9× 9.

46

Capıtulo 3

Algoritmo CUTSIM

El algoritmo de simulacion categorica desarrollado es denominado CUTSIM (ConditionalUnilateral Texture SIMulation). Se basa en la asignacion de valores a los nodos de una grilla Gsiguiendo un camino determinıstico. El valor asignado es determinado por medio de informacionrecuperada desde una imagen de entrenamiento representativa del fenomeno en estudio y escondicionado a valores muestrales conocidos a priori.

3.1. Camino unilateral

Cada nodo de la grilla G es identificado por su posicion u = (ux, uy, uz). Para obteneruna realizacion re cada nodo re(u) ∈ G debe ser asignado en un cierto orden. Se define elcamino unilateral pathG como el vector de posiciones u1, . . . ,u|G| en que los nodos de la grillaprimero son recorridos segun la coordenadaX , luego segun la coordenada Y y, finalmente, segunla coordenada Z (ver fig. 3.1). Este camino es arbitrario por lo que puede ser redefinido, siendonecesario tambien redefinir los templates a utilizar.

3.2. Template causal

Un template causal es un template que asegura que los data-events obtenidos, siguiendoel camino unilateral, contengan solo nodos pre-asignados. Esta ligado con el camino unilateral,debido a que recorriendo los nodos segun este orden se garantiza que la vecindad del nodo asimular, representada por el template, solo contiene datos pre-asignados. A su vez, un patroncuya geometrıa es definida mediante un template causal es denominado patron causal.

47

Figura 3.1: Camino unilateral. A la izquierda se muestra un ejemplo de malla 3D y a la derechase indica el orden en que son recorridos sus nodos: primero aumentando la coordenada X , luegola Y y finalmente la Z.

Dado un template τ , definido por un paralepıpedo de dimension cx × cy × cz, la posiciondel nodo central se define como:

c = (bcx2c, bcy

2c, bcz

2c) (3.1)

y el template causal π se define como:

π = {τ(u), uz < cz}⋃{τ(u), uz = cz, uy < cy}

⋃{τ(u), uz = cz, uy = cy, ux < cx}

(3.2)

La forma del patron causal cambia con respecto a la utilizada en [Wei01] debido al nuevoorden de simulacion a considerar. La geometrıa del template puede ser apreciada en la fig. 3.2.

(a) (b) (c)

Figura 3.2: Ejemplo de template causal y no-causal. (a) Region completa, incluyendo nodo cen-tral. (b) Template causal representado por la zona demarcada. (c) Template no-causal.

El template no causal ρ es definido por el complemento de τ menos el nodo central.

48

3.3. Obtencion de patrones

El primer paso a desarrollar, para la ejecucion del algoritmo, luego de la definicion deltemplate causal τ a utilizar, es determinar como obtener los patrones desde la imagen de entrena-miento y como almacenar la informacion estadıstica relacionada a dichos patrones de modo quesea rapido y escalable realizar busquedas de estadısticos de patrones durante la fase de simula-cion.

El problema radica en que los data-events no siempre estaran completamente informados.Este hecho se debe a que los data-events rescatados desde nodos cercanos a los bordes de la reali-zacion, pueden contener nodos no informados si la posicion relativa, de dichos nodos, no capturaposiciones de G. Por ejemplo, el data-event centrado en el primer nodo a asignar contendra todossus nodos sin informar.

Para resolver este problema se puede reducir la dimensionalidad de τn a n′, con n′ < n,en los casos que sea necesario, de tal forma de no rescatar data-events con nodos no informa-dos. Otra estrategia, similar a la utilizada por el algoritmo de sıntesis de texturas propuesto en[Wei01], es agregar fuera de los bordes nodos informados con ruido, permitiendo siempre laobtencion de patrones asociados a τn.

3.3.1. Utilizacion de ruido

Diferentes estrategias pueden ser estudiadas para la asignacion del ruido inicial; una pri-mera estrategia es asignarlo aleatoriamente respetando la probabilidad a priori de las categorıasen la imagen de entrenamiento. Si bien el algoritmo de sıntesis de texturas comienza con ruido,esta metodologıa no es buena para el problema que se desea resolver. La razon de esto radicaen que el algoritmo de sıntesis de texturas produce imagenes enlosables utilizado un enfoquetoroidal, es decir, ve la realizacion como una grilla sin bordes. Bajo este enfoque basta utilizarpoco ruido y solo al comienzo de la simulacion, ya que al finalizar el proceso sera sobreescritopor informacion mucho mas relacionada con la imagen de entrenamiento.

Debido a que el problema de simulacion no busca realizaciones enlosables, el enfoquetoroidal no es utilizado, siendo necesario agregar el ruido fuera de la zona de simulacion. Con-siderar un borde extra provoca que los nodos cercanos al borde reproduzcan de peor manera lacontinuidad que los mas alejados. Este comportamiento puede ser mejorado creando una zonade buffer consistente en una zona de ruido mayor a la estrictamente necesaria. Utilizar ruido fa-cilita la implementacion del algoritmo, ya que solo patrones definidos por un solo template sonrescatados, simplificando tanto la obtencion como su almacenamiento, por otro lado, al mejorarla calidad de las realizaciones mediante la zona de buffer, aumenta el numero de nodos a simular.

49

3.3.2. Reduccion de dimensionalidad

Debido a los inconvenientes anteriores, un primer acercamiento es reducir la dimensionde los data-events que condicionan la simulacion de los nodos cercanos a los bordes de re. Estaestrategia tambien tiene sus dificultades: es necesario manejar relaciones para distintos templatesencareciendo la etapa de obtencion y pudiendo aumentar drasticamente el uso de memoria RAM.

El numero de templates a considerar esta dado por los subtemplates de τn asociados a lospatrones obtenidos durante la simulacion a partir de data-events asociados al template τn. Porejemplo, para un template de 5 nodos de lado, se obtendran 12 subtemplates, tal como se muestaen la fig. 3.3, donde dichos sub-templates son demarcados con borde verde. El circulo con unacruz roja en su interior representa el nodo a simular. El primer subtemplate es el subtemplatevacıo.

Considerando una grilla de dimension hx × hy, la region causal de esta grilla puede serdividida en 2 regiones: la formada por todos los nodos inferiores del nodo central (region A) y laformada por los nodos a la izquierda en la misma fila que el nodo central (region B). Se asumeque hx ≤ nx y bhy/2c+1 ≤ ny, donde nx y ny son la dimensionalidad enX e Y de la realizaciona obtener, respectivamente. Al comenzar la simulacion no habran nodos simulados, por lo que secomenzara con el template vacıo. Luego, al simular el segundo nodo, ya se contara con un nodosimulado, el de la izquierda, por lo que el template tendra un nodo en la region B, de este modo,al llegar al borde derecho de la realizacion se habran utilizado tantos templates como nodosen la region B mas el template vacıo. Luego, cuando se simule una fila superior, se generaransubtemplates de quitar columnas tanto a la izquierda de la columna del nodo a simular como ala derecha de este, mas el caso en que no sea necesario quitar columnas (cuando no se este enun borde), en total hx posibles casos. Dado que estamos pensando en una fila cualquiera hay quemultiplicar hx por el numero de filas que puede tener la region A dado por bhy/2c, ya que porcada fila que se agregue al subtemplate se tendran los mismos hx casos. Por lo tanto, el numerode subtemplates esta dado por:

1 + bhx2c+ hxb

hy2c (3.3)

Este resultado puede ser extendido para un template en 3D, obteniendo el siguiente resul-tado:

1 + bhx2c+ hxb

hy2c+ hxhyb

hz2c (3.4)

50

Figura 3.3: Subtemplates para template con 5 nodos de lado. Se muestran los 12 subtemplatesnecesarios a considerar durante la simulacion para un template causal en 2D limitado por uncuadrado de 5 nodos de lado.

3.3.3. Uso de sub-templates

Los patrones y la frecuencia del valor de la variable en la posicion central, obtenidos apartir de una imagen de entrenamiento, son llevados a una estructura de datos que facilite laconsulta de frecuencias durante la simulacion, ya que hacerlo directamente desde la imagen deentrenamiento resulta mucho mas lento.

Por otro lado, guardar en memoria todas las estadısticas asociadas a los patrones rescatadoscon todas las geometrıas que aparecen durante el proceso de simulacion puede ocupar demasiadamemoria, sobre todo al utilizar templates grandes. Se puede relajar el problema solo guardandoestadısticos para el template causal y restringiendo la busqueda de patrones asociados a sub-templates.

Al extraer los patrones desde la imagen de entrenamiento, se guardan todas las configura-ciones de variables dadas segun la geometrıa definida por un template τn. Debido a problemasen los bordes, es necesario conocer relaciones que involucren menos nodos que los presentesen los patrones obtenidos utilizando τn, es decir, se necesitan estadısticos de subpatrones. Esposible obtener estos estadısticos a partir de los estadısticos de los patrones, asumiendo una po-sible perdida de informacion, dependiendo del sub-template, para aquellos nodos de la imagende entrenamiento cercanos a los bordes.

51

Dado un template τn, la region degradada de una imagen de entrenamiento ti es aquellaregion formada por los pixeles cuyas posiciones pueden ser el nodo central de un data-eventasociado a τn. Es decir, no pertenecen a esta region aquellos pixeles de ti que por estar muycerca de los bordes no pueden ser el centro de un data-event con todos sus nodos informados.En la fig. 3.4 se muestra la zona degradada de una grilla para el template ilustrado. La regiondegradada determina la region que contiene los pixeles que se asegura seran tomados en cuenta alobtener estadısticos utilizando subpatrones. Lo anterior no quiere decir que mediante estadısticosde sub-patrones, obtenidos a partir de estadısticos de patrones, no se consideren pixeles fuera deesta zona, dependiendo del template utilizado, pixeles fuera de la region degradada pueden serutilizados. Lo que sı se asegura es que los estadısticos de sub-patrones siempre consideraran lospixeles de la region degradada.

(a) Template (b) Region degradada

Figura 3.4: Region degradada.

Asumiendo lo anterior, se cumplen las siguientes propiedades.

La funcion de distribucion de probabilidad condicional al data-event dn′ , asociado con elsub-template τn′ de τn, en que n′ < n, puede ser obtenida a partir de las funciones de distribucionde probabilidad condicionales a los data-events dn asociado con τn que cumplan que dn′ seasubconjunto de dn. De esta forma el numero de ocurrencias de dn′ en la imagen de entrenamientocorresponde a:

c(dn′) =∑

dn asociado con τndn′ ⊂ dn

c(dn) (3.5)

52

Analogamente, el numero de ocurrencias de dn′ con valor central igual a sk corresponde a:

ck(dn′) =∑

dn asociado con τndn′ ⊂ dn

ck(dn) (3.6)

Luego, basandose en el supuesto de estacionaridad y en que la region degradada es repre-sentativa del fenomeno, es una buena estrategia rescatar los estadısticos para los subtemplates enbase a las dos propiedades anteriores. Con esto ademas, se simplifica la creacion de la estructurade datos y se reduce el total de memoria RAM involucrada.

3.4. Distancia de patrones

Se define la distancia de dos patrones, patkτ y patk′τ , mediante un vector de pesos w, en

que cada componentew(α), α = 1, . . . , n corresponde al castigo asociado a la desigualdad entrelos componentes patkτ (α) y patk′τ (α). Los componentes de w son normalizados a uno, de modoque la distancia de dos patrones completamente distintos es 1.

Formalmente, la distancia entre dos patrones asociados al template τ , se define como:

d〈patkT,patk′

T〉 =n∑

α=1

I{patkT(α), patk′

T(α)}w(α) (3.7)

donde

I{patkT(α), patk′

T(α)} =

{0 si patkT(α) = patk

′T(α)

1 si patkT(α) 6= patk′

T(α)(3.8)

3.5. Condicionamiento

Siguiendo el camino unilateral, a cada nodo no informado re(u) se le debe asignar una delas K categorıas sk. Para cada nodo visitado re(u) se rescata la siguiente informacion a partir delos nodos ya simulados y los datos muestrales:

1. El data-event causal dπ, es decir, asociado al template causal π. Condiciona el valor delnodo a asignar Z(u) a la vecindad ya simulada; y

53

2. El data-event no-causal dρ, es decir, asociado al template no-causal ρ, que condiciona elvalor de Z(u) a los datos muestrales.

La base para realizar la asignacion es construir una funcion de distribucion de probabilidadcondicional para Z(u) utilizando los datos de la vecindad de u, funcion que puede ser estimadaa traves de conteo de patrones, mediante:

p(u; sk | (n)) ' ck(dn)

c(dn), ∀k, k = 1 . . . , K (3.9)

donde: dn = dπ⋃dρ; c(dn) es la frecuencia de aparicion en la imagen de entrenamiento del

patron formado por los datos de dn; y ck(dn), la frecuencia del patron formado a partir de dn masel nodo central de valor sk.

El condicionamiento se traduce a encontrar, dado dn, las frecuencias c(dn) y ck(dn). Notarque, dependiendo de los nodos condicionantes que puedan aparecer en dρ, los patrones obtenidosa partir de dn pueden estar asociados a una gran variedad de templates. Por lo general, se esperaque los nodos condicionantes sean mucho menor que el tamano de la realizacion. Debido aestos motivos resulta conveniente, durante la adquisicion de patrones, almacenar las frecuenciaspara los patrones asociados a π y asociar a estos patrones la frecuencia considerando los datosobtenidos por medio de ρ.

Considerar el conjunto C que contiene todos los patrones a distancia mınima de d∗π:

C = argmind∗π⊂ti

d〈dπ, d∗π〉 (3.10)

Notar que este conjunto de patrones siempre es no vacıo y que el patron a mınima distanciano es necesariamente unico. Se crea un nuevo conjunto de patrones concatenando los patronesde C con los nodos condicionantes de dρ:

S = {dπ ∪ dρ | dπ ∈ C} (3.11)

Dado que se busca el conjunto de patrones a distancia mınima, cada una de las frecuenciasck(dn) y c(dn) es estimada de la suma sobre todos los patrones del conjunto S, es decir, elresultado de la fraccion de la ecuacion 3.9 es estimado como:

ck(dn)

c(d)'∑

dn∈S ck(dn)∑dn∈S c(dn)

≡ ckc

(3.12)

54

En el caso de que c = 0 es necesario reducir la dimensionalidad de los patrones hastaque las frecuencias sean distintas de cero. Esto es realizado eliminando de los patrones el nodormax que pertenece a dρ a mayor distancia, tomando como distancia la definida por el vector wutilizado por la funcion de distancia:

rmax = argmaxr∈dρ

w(r) (3.13)

3.5.1. Asignacion

La funcion de distribucion acumulativa se construye como:

p(u; sk | (n)) ' ckc

(3.14)

y es la base del proceso de sıntesis. La asignacion es realizada recorriendo, segun el camino uni-lateral, los nodos no informados de la realizacion y obteniendo, para cada nodo la distribucionanterior, mediante conteo de patrones. Finalmente, la asignacion es realizada mediante una simu-lacion de Monte Carlo utilizando la distribucion obtenida. En la fig. 3.5 se muestra un ejemplode como la simulacion de Monte Carlo actua. El metodo consiste en encontrar un valor aleatorior para una funcion aleatoria que sigue una distribucion uniforme entre 0 y 1. Luego se eligela categorıa asociando r con la menor frecuencia acumulada que es mayor o igual a r. En elejemplo, dada la funcion de distribucion de probabilidad acumulativa para las categorıas: azul(10 %), rojo (10 %), verde (60 %) y amarillo (60 %), se elige un valor aleatorio r (0,76) segununa distribucion uniforme entre 0 y 1. Finalmente, la categorıa elejida es la verde.

Figura 3.5: Visualizacion de simulacion de Monte Carlo.

55

3.6. Pseudocodigo

El algoritmo es resumido en el siguiente pseudocodigo:

Algoritmo 1 Pseudocodigo de CUTSIM.Require: imagen de entrenamiento tiRequire: conjunto D de puntos muestralesRequire: tamano nx × ny × nz de la realizacionRequire: template causal π y no causal ρ con π ∩ ρ = ∅. Se define τ = π ∪ ρRequire: vector de pesos w para τEnsure: realizacion de tamano nx × ny × nz

1: Crear grilla re de nx × ny × nz nodos2: for all punto u tal que z(u) ∈ D do3: re(u)← z(u)4: end for5: k ← 06: while re tiene nodos sin asignar do7: u← posicion k del camino unilateral8: dπ ←data-event causal centrado en u9: dρ ←data-event no-causal centrado en u

10: C ← conjunto con los patrones a distancia mınima de dπ11: S ← {dπ ∪ dρ | dπ ∈ C}12: c←

∑d∈S c(d)

13: while c = 0 do14: rmax ← argmaxr∈dρ w(r)15: dρ ← dρ − {rmax}16: S ← {dπ ∪ dρ | dπ ∈ C}17: c←

∑d∈S c(d)

18: end while19: ck ←

∑d∈S ck(d)

20: re(u)← Valor obtenido mediante metodo de Monte Carlo utilizando las frecuencias ck yc

21: k ← k + 122: end while23: return re

56

Capıtulo 4

Algoritmo continuo

En este capıtulo se explica la metodologıa desarrollada para simulacion de variables con-tinuas mediante simulacion de indicadores, por medio del algoritmo CUTSIM, descrito en elcapıtulo anterior.

4.1. Metodo

CUTSIM es un algoritmo de simulacion para variables categoricas. Sin embargo, puedeser utilizado para simular una variable continua Z(u), mediante el uso del indicador i(u; zk)definido como:

i(u; zk) =

{1 si z(u) ≤ zk0 si z(u) > zk

(4.1)

para K valores de corte zk, k = 1, . . . , K ordenados ascendentemente, es decir, zi < zj si i < jcon i, j ∈ [1, K].

Empleando el indicador sobre cada pıxel de la imagen de entrenamiento se generan Kimagenes de entrenamiento binarias tik, desde donde seran extraıdos los estadısticos para estimarla variable aleatoria del indicador I(u; zk).

El estimador de i(u; zk) corresponde al estimador que minimiza el error cuadratico mediode la funcion de distribucion acumulativa en el valor de corte zk, tal como se muestra a continua-

57

cion:

[i(u; zk)]∗ = E {I(u; zk | (n))}∗ (4.2)

= Prob ∗{Z(u) ≤ zk | (n)} (4.3)= F ∗(u; zk | (n)) (4.4)

donde (n) es un data-event que condiciona a Z(u).

Luego, dado los K valores de corte, es posible construir una funcion de distribucion deprobabilidad acumulativa en base a las estimaciones de F ∗(u; zk | (n)), k = 1, . . . , K, estiman-do la esperanza condicional del indicador para losK valores de corte. Se obtiene ası, una funcionde distribucion discreta que puede ser llevada a una funcion de distribucion continua medianteinterpolacion y extrapolacion para los valores fuera del rango [z1, zK ].

Utilizando la distribucion construida, es posible realizar simulaciones mediante Monte Car-lo, tal cual lo realiza CUTSIM, las que condicionan los nodos siguientes en una simulacion se-cuencial siguiendo un camino unilateral.

4.2. Obtencion de distribucion del indicador

El problema radica en estimar E {I(u; zk | (n))} y ası obtener un estimador de F (u; zk |(n)). Se tiene que:

E {I(u; zk | (n))} = 1 · Prob {I(u; zk | (n)) = 1}+ 0 · Prob {I(u; zk | (n)) = 0} (4.5)= Prob {I(u; zk | (n)) = 1} (4.6)

Luego, se obtiene la funcion de distribucion estimando la probabilidad del indicador como:

Prob {I(u; zk | (n)) = 1} ' c1(dn,k)

c(dn,k)(4.7)

donde dn,k corresponde al data-event de dimension n obtenido desde la imagen de entrenamientotik. Las frecuencias c1(dn,k) y c(dn,k) son obtenidas de la misma forma que el algoritmo paravariables categoricas, utilizando como imagen de entrenamiento tik. Finalmente se tiene que:

F (u; zk | (n)) ' c1(dn,k)

c(dn,k)(4.8)

Obteniendo la funcion de distribucion discreta F (u; zk | (n)), es posible construir una

58

Figura 4.1: Distribucion continua construida mediante interpolacion y extrapolacion.

distribucion continua en base a interpolacion, si z pertenece al intervalo [z1, zK ]; y extrapolacion,para los valores fuera del intervalo. Los rangos a extrapolar son: la cola inferior, si z perteneceal intervalo [zmin, z1); y la cola superior, si z esta dentro de (zK ,+∞). En la fig. 4.1 es mostradauna ilustracion de una distribucion formada a partir de interpolacion y extrapolacion para tresvalores estimados a partir de tres valores de corte.

Se estima F (u; z | (n)) para z en (zk, zk+1) mediante interpolacion lineal, de modo que:

F (u; z | (n)) = F ∗(u; zk | (n)) + (z − zk)F ∗(u; zk+1 | (n))− F ∗(u; zk | (n))

zk+1 − zk(4.9)

Para la cola inferior se extrapola usando un modelo de potencias con parametro ω > 0.Ası se tiene que para el intervalo (zmin, z1) la distribucion se calcula como:

Fω(u; z | (n)) =

[z − zminz1 − zmin

]ωF ∗(u; z1 | (n)) (4.10)

Para la cola superior se extrapola mediante un modelo hiperbolico con parametro de ajusteω > 1

Fω(u; z | (n)) = 1− zωK(1− F ∗(u; zK | (n)))

zω(4.11)

En la fig. 4.2 se muestran distintas curvas de extrapolacion para la cola inferior y superiorobtenidas para distintos valores del parametro ω.

59

0

F(Zmin)

F(Z1)

Zmin Z1

0,1

0,25

0,5

1,0

2,5

5,0

1,5

(a) Extrapolacion cola inferior.

15,0

1,0

Zn

F(Zn)

0

(b) Extrapolacion cola superior.

Figura 4.2: Extrapolacion de (a) cola inferior y (b) cola superior. Se muestran diferentes curvaspara distintos valores de ω.

60

Capıtulo 5

Aceleracion

Si bien, el algoritmo desarrollado, CUTSIM, utiliza informacion obtenida desde una ima-gen de entrenamiento, con el fin de hacerlo eficiente, no recupera dicha informacion directamentedesde la imagen, sino que lo hace desde estadısticos de patrones previamente capturados desdela imagen de entrenamiento. Obtener las K frecuencias ck(dπ ∪ dρ) directamente desde la ima-gen de entrenamiento, cada vez que un nodo sea simulado, encarece enormemente el proceso desimulacion.

Algunas estructuras de datos han sido propuestas para almacenar, en una fase inicial, lasfrecuencias de patrones obtenidas desde la imagen de entrenamiento. Las estructuras utilizadasson principalmente arboles de busqueda [Str02] [Rob97] y arreglos de patrones para un ciertotemplate [SWF+08]. Los arboles de busqueda permiten recuperar estadısticos de patrones enmenor tiempo que, por ejemplo, arreglos, pero son lentos de crear y mas demandantes de me-moria que los arreglos de patrones, lo que se hace extremadamente notorio para patrones de altadimensionalidad. Por otro lado, los arreglos de patrones son paralelizables, por lo que podrıanser mas rapidos que los arboles si la busqueda es realizada en paralelo.

5.1. Listas enlazadas vs. arreglos

Los arreglos (fig. 5.1a) son una estructura de datos en que cada elemento es indexadomediante un numero entero, es la analogıa del concepto matematico vector. Los arreglos permitenacceder a un elemento en tiempo constante Θ(1), es decir, no hay diferencias de costo entreacceder al primer, al ultimo o a cualquier elemento del arreglo. La desventaja es que es necesariodefinir a priori su tamano, lo que es un gran problema ya que no es claro cuantos patrones seranrescatados desde la imagen de entrenamiento.

61

Las listas enlazadas (fig. 5.1b) tienen tiempo lineal Θ(n) de acceso pero se crean dinamica-mente, es decir, es posible insertar elementos en cualquier posicion de la lista en tiempo constanteΘ(1).

(a) (b)

Figura 5.1: Representacion de (a) un arreglo y (b) una lista enlazada.

A pesar de tener tiempo lineal de acceso, utilizar listas enlazadas no resta eficiencia alalgoritmo, debido a que se necesita recorrer en orden todos los elementos. Este recorrido tomaorden Θ(n), ya que acceder de un nodo al siguiente toma orden Θ(1). En la siguiente tabla semuestra una comparacion de tiempos entre una lista enlazada y un arreglo.

Arreglo Lista enlazada

Acceso Θ(1) Θ(n)Insercion/borrado al final - Θ(1)Insercion/borrado en la mitad - Θ(1)

Para CUTSIM se desarrollo una estructura en que las frecuencias de los patrones son al-macenadas en una lista enlazada, de forma similar a un arreglo de patrones. Si bien acceder aelementos de un arreglo es mas rapido, es menos flexible que una lista enlazada. Por otro lado,para el algoritmo, no es prioritario una velocidad de acceso rapida; lo que interesa es que recorrerla estructura lo sea.

5.2. Estructura de datos

La estructura de datos desarrollada, para almacenar la frecuencia de cada uno de los Kvalores de la variable z, asociada a los patrones de la imagen de entrenamiento, es una listaenlazada en que cada nodo contiene un patron causal y un arreglo con sus frecuencias para lasK categorıas. A su vez, cada nodo contiene una tabla hash, como se muestra en la fig. 5.2, quees una estructura de datos que asocia llaves con valores. De esta forma, las llaves de la tabla dehash corresponden a patrones no-causales; y los valores, a las frecuencias para el patron formadode la concatenacion del patron causal con el no causal correspondiente.

62

Figura 5.2: Representacion de la estructura de datos utilizada. Cada nodo de la lista enlazadaesta identificada por un patron causal y almacena las frecuencias ci, i = 1, . . . , K del patroncausal para los K posibles nodos centrales. Cada nodo tiene asociado una tabla hash en que susllaves son los patrones no-causales. El valor almacenado por la tabla de hash corresponden a lasfrecuencias del nodo central del patron formado por la concatenacion del patron causal con el nocausal.

63

5.3. Recuperacion de patrones causales

Dado que, por lo general, la informacion condicionante es mucho menor que el numero denodos de la grilla de la realizacion, la mayorıa de las veces solo se necesitara recuperar informa-cion asociada al patron causal, es decir, no se considerara informacion condicionante. De ser ası,las frecuencias se obtienen directamente desde los nodos de la lista enlazada.

La busqueda a realizar es, dado un data-event dπ, obtener un conjunto de patrones C aso-ciados a π tales que la distancia entre dπ y cada uno de los patrones de C sea mınima. Paraobtener C se recorre completamente la lista enlazada obteniendo la distancia entre cada patronvisitado y dπ. Si se encuentra un patron, tal que su distancia con dπ es cero, la busqueda se de-tiene y se entrega como resultado la informacion de dicho nodo. De lo contrario, se entrega elconjunto de nodos que estan a mınima distancia de dπ.

5.4. Recuperacion de patrones con informacion no causal

Para una busqueda en donde se proporciona tanto un data-event causal dπ como informa-cion condicionante dada por un data-event no causal dρ, con dρ distinto de vacıo, las frecuenciasson obtenidas de la informacion almacenada en las tablas hash de los patrones del conjunto Cformado por los nodos asociados a los patrones causales recuperados utilizando el data-eventcausal dπ, es decir, tal cual se harıa para el caso de no contar con informacion condicionante.

Contando con el conjunto de nodos de mınima distancia, las frecuencias son obtenidas dela suma, para cada una de las K frecuencias, de los registros de las tablas de hash de todos losnodos del conjunto tales que, dρ es subconjunto del patron correspondiente a la llave del registro.

5.5. Recuperacion de subpatrones

Considerar un data-event d compuesto de una parte causal dπ′ y otra no causal dρ, en quedπ′ esta asociado al template π′ tal que π′ es subtemplate de π. Es posible obtener las frecuenciasde este data-event desde la estructura de datos considerando todos los nodos de la lista enlazadatales que dπ′ es un subconjunto del patron del nodo. Obteniendo un conjunto de todos los nodosen los que se cumple la propiedad anterior, las frecuencias finales se calculan tal como el casode recuperacion de informacion no causal luego de obtener el conjunto de nodos con patronescausales con distancia mınima.

64

5.6. Modelo de datos

A continuacion se dan detalles del modelo de datos empleado para representar la infor-macion y utilizado en la estructura de datos. Tanto la informacion obtenida desde la imagen deentrenamiento y los datos condicionantes como las diferentes definiciones son representadas poreste modelo de datos.

5.6.1. Representacion de la informacion

La informacion de INPUT proveniente desde la imagen de entrenamiento y de los datoscondicionantes, es representada mediante instancias de diferentes clases del modelo de datos. Laimagen de entrenamiento es convertida en patrones y los datos condicionantes son llevados a unmapa que relaciona la informacion con su posicion. Las estructuras son genericas, es decir, pue-den almacenar datos de cualquier tipo (o clase). Los conceptos de categorıa, posicion, templatey dimension son tambien modelados mediante clases que se presentan a continuacion.

Facie

Representacion de una categorıa. El nombre es tomado del contexto geologico, en que“facie” se refiere a un conjunto de rocas con determinadas caracterısticas.

En la fig. 5.3 es mostrado un diagrama de clases en que los datos son del tipo Facie. Cadacategorıa es identificada por un ındice y, optativamente, un nombre. Las instancias de esta clasecorresponden a cada una de las categorıas a las cuales puede pertenecer la variable en estudio. Elmodelo no se ve limitado al uso de esta clase, si se desease utilizar este modelo para almacenarvalores continuos, instancias de la clase Double podrıan ser empleadas.

Puntos

Las posiciones son representadas mediante instancias de la clase Point, compuesta por unındice entero para cada coordenada. La clase Point posee el metodo plus que permite sumardos puntos generando un tercero y el metodo magnitude que permite conocer la magnitud delvector. Los metodos compareTo y equals permiten comparar puntos y conocer si dos puntostienen la misma posicion. La comparacion es realizada primero segun la coordenada Z, luegosegun Y y finalmente segun X .

65

Dimension

Otra clase utilizada dentro del modelo de datos es Dimension, que corresponde al tamanodado por nx × ny × nz. Posee los metodos:

size Entrega la dimension, es decir, nx × ny × nz.

equals Determina si dos objetos Dimension son iguales.

Template

La clase Template contiene una coleccion de instancias de Point, que la definen. Poseelos metodos:

size El numero de puntos del template.

getIndex Devuelve un ındice dentro del template asociado al punto dado.

makeTemplate, makeCausal, makeNonCausal Permiten crear diferentes tipos detemplates.

equals Determina si dos templates poseen la misma geometrıa.

contains Determina si el template posee el punto dado.

Patrones

Una instancia de Pattern contiene una coleccion elementos, por ejemplo de tipo Facie,y ademas, una configuracion geometrica para dichos elementos dado un template. La clasePattern es iterable, es decir, es posible obtener un iterador para recorrer cada uno de suselementos. Posee ademas los siguientes metodos:

size Entrega el numero de elementos del patron.

get Obtiene el elemento del patron para una posicion determinada.

getTemplate Obtiene el template del patron.

equals Determina si un patron es igual a otro.

66

Datos condicionantes

La informacion condicionante es almacenada en una instancia de CondData, que corres-ponde a un mapa de valores: posicion y dato condicionante. Al igual que Pattern, es unaclase generica, por lo que el dato almacenado puede ser de cualquier tipo, por ejemplo Facie.Ademas es iterable y posee los siguientes metodos:

get Obtiene el elemento del mapa dada una posicion.

set Agrega al mapa un par (posicion, elemento).

<<interface>>

Iterable<Facie>

iterator: Iterator<Facie>

Pattern<Facie>

equals(pattern: Pattern): booleangetTemplate: Templateget(p: Point): Faciesize: int

Facieid: intname: Stringequals(f: Facie): boolean

<<interface>>

Iterable<Point>

iterator: Iterator<Point>

CondData<Facie>map: Map <Point, T> set(p: Point, facie: Facie): voidget(p: Point): Facie

<<interface>>

Iterable<Point>

iterator: Iterator<Point>

Template

size: intgetIndex(p: Point): intmakeTemplate(dim: Dimension): TemplatemakeCausal(dim: Dimension): TemplatemakeNonCausal(dim: Dimension): Templateequals(tpl: Template): booleancontains(p: Point): boolean

Pointx: inty: intz: intequals(p: Point): booleancompareTo(p: Point): intmagnitude: doubleplus(p: Point): Point

Dimensionnx: intny: intnz: intsize: intequals(dim: Dimension): boolean

Como ejemplo se uso la claseFacie pero se puede crear tantoun Pattern como un CondDatapara cualquier objeto.

1 0..*

0..*

1

1

1

1 0..* 1..* 1

Figura 5.3: Diagrama de clases para las clases genericas encargadas de representan la infor-macion: Pattern y CondData. Ademas se muestra la interaccion con las clases Point,Dimension, Template y Facie.

67

5.6.2. Representacion de la grilla

Una grilla es representada por una instancia de la clase Grid, compuesta por una colec-cion de nodos que son instancias de la clase GridNode (ver fig. 5.4). Existe una tercera clase,NodeFunction, que es abstracta y tiene por objetivo ser extendida para poder definir opera-ciones nodo a nodo sobre la grilla, de tal forma de modificar la informacion de un objeto Grid.

La clase Grid es generica e iterable sobre sus nodos. Tiene como subclases a TImage yRealization, abstracciones de imagen de entrenamiento y de realizacion, respectivamente.Posee los siguientes metodos:

idx Retorna el ındice dentro de la grilla.

set Asigna un dato en una posicion dada de la grilla.

unset Desasigna el valor de la grilla para la posicion dada.

get Obtiene el nodo de la grilla en la posicion dada.

containPoint Determina si la grilla contiene informacion en la posicion dada.

retrieveCondEvent Recupera informacion condicionante para una posicion y un template dado.

retrieveDataEvent Recupera un data-event en una posicion especıfica empleando un templatedado.

save Guarda los datos de la grilla en un archivo con formato GSLIB.

map Aplica una operacion definida en un objeto NodeFunction a cada nodo de la grilla.

Cada nodo de una grilla corresponde a un objeto GridNode que posee un DataType yun dato que puede ser de cualquier tipo, por ejemplo un objeto Facie. DataType correspondea una enumeracion de la naturaleza del dato almacenado en el nodo, que puede ser uno de los si-guientes tipos: NOT INFORMED, CONDITIONAL, SIMULATED y KNOWED. GridNode poseelos siguientes metodos:

set Asigna un dato y su tipo: simulado o condicionante.

getData Obtiene el dato.

getDataType Obtiene el tipo del dato, por ejemplo: Double, Facie, Integer.

68

Grid<T>Dimension: dimidx(p: Point): intset(p: Point, data: T, type: DataType): voidunset(p: Point): voidget(p: Point): GridNode<T>containPoint(p: Point): booleanretrieveCondEvent(p: Point, t: Template): CondEvent<T>retrieveDataEvent(p: Point, t: Template): DataEvent<T>save(f: File): voidmap(fnc: NodeFunction<T>): void

TImage Realization

< <interface> >

Iterable<GridNode<T>>

iterator: Iterator< GridNode<T> >

GridNode<T>type: DataTypedata: Tset(data: DataType, type: T): voidgetData: TgetDataType: DataType

NodeFunction<T>apply(node: GridNode<T>): void

1 0..*

Figura 5.4: Diagrama de clases para una grilla representada por la clase Grid. TImage yRealization son subclases de Grid.

5.6.3. Representacion de los data-events

Los data-events son representados mediante objetos genericos DataEvent que estancompuestos por una coleccion de objetos GridNode (ver fig. 5.5). Un objeto DataEventcontiene un template y los siguientes metodos:

set Asigna un GridNode en una posicion dada.

get Obtiene el GridNode de una posicion dada.

makePattern Construye un patron, instancia de Pattern, a partir del data-event.

getNodes Obtiene una coleccion con los nodos del data-event.

areAllNodesInformed Determina si todos los nodos del data-event estan informados o no.

retrievePatternTemplate Obtiene el template asociado a los nodos informados deldata-event.

map Aplica la operacion apply de una instancia de NodeFunction sobre todos los nodosdel data-event.

69

Los datos rescatados mediante data-events son convertidos a patrones o bien almacena-dos como instancias de CondEvent. El ultimo caso ocurre cuando los datos corresponden ainformacion dentro del template no-causal. Cada instancia de CondEvent posee un templatey una lista enlazada formada por nodos de la clase CondEventNode. CondEvent posee lossiguientes metodos:

map Aplica el metodo apply de una instancia de CondNodeFunction a todos sus nodos.

size Obtiene el numero de nodos que forman el CondEvent.

addCondEventNode Agrega un CondEventNode.

equals Determina si dos objetos CondEvent son iguales o no.

isEmpty Determina si CondEvent no tiene nodos.

isSubSet Determina si un CondEvent es subconjunto de otro.

remove Elimina un nodo de un objeto CondEvent.

Un objeto CondEventNode esta formado por un punto de la clase Point y un no-do de la clase GridNode, ademas posee el metodo equals que determina si dos nodosCondEventNode son iguales.

70

< <interface> >

Iterable<GridNode<T>>

iterator: Iterator<GridNode<T»

DataEvent<T>template: Templateset(p: Point, node: GridNode<T>): voidget(Point p): GridNode<T>makePattern: Pattern<T>getNodes: ArrayList<GridNode <T> >areAllNodesInformed: booleanretrievePatternTemplate: Templatemap(function: NodeFunction<T>): void

GridNode<T>type: DataTypedata: Tset(data: DataType, type: T): voidgetData: TgetDataType: DataType

CondEventNode<T>point: PointgNode: GridNode<T>equals(cevn: CondEventNode<T>): boolean

CondEvent<T>template: Templatemap(function: CondNodeFunction<T>): voidsize: intaddCondEventNode(p: Point, g: GridNode<T>): voidequals(cev: CondEvent<T>): booleanisEmpty(): booleanisSubSet(cev: CondEvent<T>): booleanremove(idx: int): void

PatDB

scanTImage: void

Pattern<Facie>

equals(pattern: Pattern): booleangetTemplate: Templateget(p: Point): Faciesize: int

NodeFunction<T>apply(node: GridNode<T>): void

CondNodeFunction<T>apply(node: CondEventNode<T>): void

0..* 1

1

0..*

0..1

0..*

0..* 1

1

0..*

Figura 5.5: Diagrama de clases para un data-event representado por las clase DataEvent yCondEvent. Esta ultima clase es utilizada para manejar la informacion condicionante rescatadautilizando un template no-causal.

71

Capıtulo 6

Paralelizacion

Para hacer el algoritmo mas eficiente, es necesario paralelizarlo, de modo que el procesa-miento pueda ser repartido en multiples procesos dentro de un computador, o bien, distribuidoen un cluster, es decir, en un arreglo de computadores. Otra posibilidad es una mezcla entre lasdos opciones anteriores. Independiente de la solucion escogida, para poder elegir alguna, es ne-cesario paralelizar el algoritmo, es decir, modificar su diseno para que dos o mas tareas puedanser realizadas concurrentemente.

Existen dos estrategias para paralelizar el algoritmo. La primera consiste en paralelizar anivel de realizaciones, es decir, calcular cada realizacion deseada en un proceso distinto, evitandocualquier comunicacion entre estos procesos. La segunda manera, y la mas desafiante, es para-lelizar a nivel del camino en que se recorre la realizacion, de modo de simular cada realizacionusando multiples procesos. El primer enfoque es relativamente facil de implementar, pero muyutil para el problema de simulacion, donde por lo general muchas (cientos) realizaciones sonrequeridas para posteriores estudios, por ejemplo, para estimar la variabilidad de una estimacion.Las paralelizaciones implementadas en el algoritmo CUTSIM dentro de esta primera categorıason detalladas en este capıtulo. Un metodo que sigue el segundo enfoque es propuesto comotrabajo futuro de esta tesis, en el capıtulo de conclusiones, dicha metodologıa puede resultar demucha utilidad sobre todo en modelos 3D.

6.1. Paralelizacion en simulacion discreta

La estrategia de paralelizacion en este caso es trivial, y hace uso del numero de CPUs dis-ponibles en la maquina de calculo. Para las pruebas realizadas, el procedimiento es el siguiente:

72

1. Se replica la base de datos de patrones nDB veces, donde nDB se define como el mınimoentre el numero de realizaciones deseadas y el numero de CPUs disponibles.

2. Se crea un pool de threads de tamano igual al numero de CPUs disponibles.

3. Cada thread del pool realiza una simulacion de forma independiente, utilizando una replicade la base de datos de patrones en forma exclusiva.

6.2. Paralelizacion en simulacion continua

El algoritmo continuo es paralelizable mediante procesos que determinen el valor de ladistribucion para cada valor de corte. De esta forma, es posible mantener un numero de procesosen paralelo igual al numero de valores de corte predefinidos, obteniendo la distribucion en formaparalela y la asignacion en forma lineal. El procedimiento es el siguiente:

1. Se crea un pool de threads igual al mınimo entre e numero de CPUs disponibles y elnumero de valores de corte ingresado como parametro del algoritmo.

2. Para cada nodo a simular, la estimacion de la funcion de distribucion es realizada en pa-ralelo, de este modo, cada thread obtiene en forma concurrente el valor de la funcion dedistribucion para cada valor de corte.

3. Luego que es obtenida la funcion de distribucion, el proceso es repetido para el siguientenodo a simular.

73

Capıtulo 7

Pruebas y resultados

En este capıtulo se muestran los resultados obtenidos en diferentes experimentos disenadospara probar el algoritmo. Las pruebas fueron realizadas en un nodo de un cluster 1, el que cuentacon 2 procesadores Intel Xeon Quad Core (16 cores) y 8 GB de memoria RAM.

7.1. Ejecucion del algoritmo

El algoritmo puede ser ejecutado tanto local como remotamente. Todo el software se en-cuentra contenido en el archivo JAR mps.jar que permite ejecutar los algoritmos ccutsim y dcut-sim, para simulacion categorica y continua, respectivamente. El software puede ser ejecutado dedos formas: pasando los argumentos como parametros o pasando como parametro un archivo enel cual se especifican los distintos INPUTS del algoritmo.

7.1.1. Paso de INPUTS por parametros

La primera forma de ejecucion es la siguiente:

java -jar mps.jar COMMAND ARGS

en que COMMAND se refiere al algoritmo y ARGS a la lista de argumentos necesarios para elalgoritmo elegido.

1Cluster del laboratorio ALGES: IBM BladeCenter 8852

74

COMMAND puede corresponder a:

ccutsim para simulacion continua y

dcutsim para simulacion discreta.

La lista necesaria de argumentos ARGS para cada algoritmos es la siguiente:

ccutsim -ti -tidim -rdim -tpdim -n -cv

dcutsim -ti -tidim -rdim -tpdim -n -facies -colors

El valor de cada argumento es pasado luego de la identificacion de este, separado por unespacio. La descripcion de cada argumento, de los listados anteriormente, es senalada a conti-nuacion.

-ti <path> Ruta de la imagen de entrenamiento.

-tidim <dim> dimension de la imagen de entrenamiento. Por ejemplo “100× 100× 1”.

-rdim <dim> Dimension de la realizacion.

-tpdim <dim> Dimension del template.

-n <int> numero de realizaciones.

-cv <list> Lista de valores de corte. Por ejemplo “0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9”

-facies <list> Lista de categorıas. Por ejemplo “0:no channel 1:channel”

-colors <list> Lista de colores para cada categorıa. Por ejemplo: “0 7”. Los codigos delos colores son mostrados en la fig. 7.1.

7.1.2. Paso de INPUTS por archivo

La otra opcion, y la mas recomendable, es pasar un archivo como parametro, el cual con-tiene las distintas especificaciones del algoritmo. La ejecucion se realiza entonces de la siguienteforma:

75

2

3

4

5

6

8

9

11

12

13

14

1510

7

1 red

orange

yellow

light green

green

light blue

dark blue

violet

white

black

purble

brown

pink

intermediate green

gray

Figura 7.1: Codigos de colores utilizados.

java -jar COMMAND mps.jar experiment.properties

El archivo de parametros 7.1 es autoexplicativo. Cada parametro es editado pudiendo co-mentar las opciones no deseadas con un “#”.

Codigo 7.1: Archivo de parametros.1 #imagen de entrenamiento2 TI="../textsynth/ti/image.dat" #channels34 #dimension de la imagen de entrenamiento5 TI_DIM="100x100x1"67 #dimensi n de la realizacion8 R_DIM="100x100x1"9

10 #dimension del template11 TP_DIM="11x11x1"1213 #datos condicionantes14 #CD="" #sin condicionamiento15 CD="../textsynth/facieCondData.dat"1617 #valores de corte18 CV=".1 .2 .3 .4 .5 .6 .7 .8 .9"1920 #facies

76

21 FACIES="0:no_channel 1:channel"2223 #codigos de colores para cada facie24 COLORS="7 1"2526 # numero de realizaciones27 N="20"

7.1.3. Uso de scripts

Para facilitar el uso se recomienda utilizar un script en el que se indiquen las opciones dela maquina virtual de Java y el archivo con la informacion de INPUT, tal como se muestra en elscript 7.1. Al final del script se ejecuta el comando con las opciones ingresadas.

Codigo 7.2: Script de lanzamiento del algoritmo.1 #!/bin/sh2 #export LD_LIBRARY_PATH=/home/aparra/yjp-8.0.19/bin/linux-x86-6434 LOG_FILE="mps.log"56 PAR_FILE="experiment.properties"78 # virtual machine options9 VM_OPT="-Xms8G -Xmx14G -server "

1011 JAR_FILE="mps.jar"1213 rm $LOG_FILE1415 java $VM_OPT -jar $JAR_FILE $PAR_FILE

7.2. Simulacion discreta

7.2.1. Pruebas exploratorias

Las primeras pruebas a realizar corresponden a simulaciones no condicionadas utilizandotemplates de tamano 3× 3, 5× 5 y 7× 7 (ver fig. 7.3) y como imagenes de entrenamiento a las

77

mostradas en la fig. 7.2 que corresponden a imagenes de dos categorıas, rojo y azul, construidasde diferentes configuraciones de lıneas verticales, horizontales y configuraciones de pixeles tipo“tableros de ajedrez”. Las imagenes 7.2a, 7.2b y 7.2c corresponden a lıneas horizontales de 2 pi-xeles de grosor para la primera imagen y 4 para las ultimas. A su vez, las lıneas estan separadas adistancias de 2, 10 y 15 piexeles, respectivamente. Las imagenes 7.2d, 7.2e y 7.2f estan formadaspor lıneas verticales con la misma configuracion que las horizontales anteriormente senaladas.Por ultimo, las imagenes 7.2g, 7.2h y 7.2i representan distintas configuraciones de tableros deajedrez, que varıan segun el lado de los cuadrados que lo forman. El tamano del lado para cadatablero corresponde a 1, 2 y 4 pixeles, respectivamente.

Para cada caso se obtuvieron 20 realizaciones, siendo mostrada la primera da cada una deellas en la fig. 7.4. La primera fila de la fig. 7.4 muestra las imagenes de entrenamiento utilizadas.La siguiente fila, imagenes 7.4d, 7.4e y7.4f, corresponden a realizaciones obtenidas de utilizarun template de tamano 3 × 3 pixeles. Del mismo modo, para los resultados de la penultima fila(imagenes 7.4g, 7.4h y 7.4i) y ultima fila (imagenes 7.4j, 7.4k y 7.4l), un template de tamano5 × 5 y 7 × 7 pixeles fue utilizado, respectivamente. Se puede apreciar como, para la primeraimagen de entrenamiento, un template de 5 × 5 pixeles permite reproducir la estructura de laimagen de entrenamiento. Del mismo modo, se obtienen mejores resultados para las dos ultimasimagenes de entrenamiento utilizando el template mas grande, es decir, se obtiene lo esperado: selogra reproducir de mejor forma la estructura de la imagen de entrenamiento cuando el templatees lo suficientemente grande como para capturar dicha estructura.

Analogamente, en la fig. 7.5 se muestran las primeras realizaciones obtenidas al utilizarcomo imagenes de entrenamiento las compuestas por lıneas verticales. Para las imagenes de lasegunda fila (7.5d,7.5e y 7.5f) se utilizo un template de tamano 3× 3 pixeles, mientras que paralas imagenes de la penultima (7.5g,7.5h y 7.5i) y ultima fila (7.5j, 7.5k y 7.5l), templates detamano 5 × 5 y 7 × 7 pixeles fueron utilizados. Se obtiene el mismo comportamiento que losresultados mostrados en la fig. 7.4.

Las realizaciones correspondientes para las tres variantes de tablero de ajedrez (7.2g, 7.2h y7.2i) son mostradas en la fig. 7.6. Las imagenes de la segunda fila () corresponden a realizacionespara un template de tamano 3 × 3 pixeles. Para la penultima (7.6g, 7.6h y 7.6i) y ultima fila(7.6j, 7.6k y 7.6l), templates de tamano 5 × 5 y 7 × 7 pixeles fueron utilizados. Se apreciancomportamientos interesantes. Las realizaciones de la primera columna (7.6d, 7.6g y 7.6j) nopresentan variacion y son iguales a la imagen de entrenamiento, por lo que se muestra que untemplate de tamano 3 × 3 logra caracterizar el tablero de ajedrez de cuadrados de lado 1. Parael segundo tablero se ve como el comportamiento anterior se da a partir del template de tamano5 × 5 pixeles. Por ultimo, para el tablero de ajedrez de celdas de tamano 5 pixeles. se apreciaque aunque las realizaciones mejoran al aumentar el tamano del template, todavıa un templatede tamano 7× 7 no logra capturar su estructura.

78

(a) (b) (c)

(d) (e) (f)

(g) (h) (i)

Figura 7.2: Imagenes de entrenamiento exploratorias de tamano 100 × 100 pixeles y dos cate-gorıas (rojo y azul).

79

Figura 7.3: Templates de tamano 3× 3, 5× 5, y 7× 7 pixeles. Los nodos demarcados con lineaspunteadas corresponden a los no-causales.

80

(a) (b) (c)

(d) (e) (f)

(g) (h) (i)

(j) (k) (l)

Figura 7.4: Realizaciones de tamano 100×100 pixeles para las distintas configuraciones de lıneashorizontales. La primera fila muestra las imagenes de entrenamiento utilizadas. Las siguientesfilas corresponden a realizaciones de la imagen de entrenamiento localizada en misma columna.

81

(a) (b) (c)

(d) (e) (f)

(g) (h) (i)

(j) (k) (l)

Figura 7.5: Realizaciones de tamano 100 × 100 pixeles para las distintas configuraciones delıneas verticales. Las imagenes de la primera fila corresponden a las imagenes de entrenamientoutilizadas. Las siguientes filas son realizaciones para un template de tamano 3× 3, 5× 5 y 7× 7pixeles, respectivamente.

82

(a) (b) (c)

(d) (e) (f)

(g) (h) (i)

(j) (k) (l)

Figura 7.6: Realizaciones de tamano 100× 100 pixeles para las distintas variantes de “tablero deajedrez”. Las imagenes de la primera fila son las imagenes de entrenamiento utilizadas; las delas demas filas, realizaciones para templates de tamano 3× 3, 5× 5 y 7× 7 pixeles.

83

7.2.2. Pruebas de canales

A continuacion se muestran los resultados para simulaciones que utilizan como imagen deentrenamiento la mostrada en la fig. 7.7, correspondiente a canales ondulatorios que se puedenintersectar y que recorren la imagen horizontalmente.

Figura 7.7: Imagen de entrenamiento de canales ondulantes de tamano 100× 100 pixeles.

84

Ejemplo no condicionado

La siguiente prueba corresponde a la simulacion sin condicionar sobre una grilla de tamano500 × 500 pixeles. El resultado es mostrado en la fig. 7.8. En ella se aprecia claramente laformacion de canales que se intersectan y que conectan ambos extremos de la imagen, tal comoen la imagen de entrenamiento. Se obtienen los dos variogramas mostrados en la fig. 7.9 segun ladireccion del eje X , para el primero, y del eje Y , para el segundo. En ellos se aprecia una buenareproduccion, en ambas direcciones, de la variabilidad espacial segun la relacion espacial de dospuntos a la vez.

El tiempo de pre-proceso, que se refiere a la creacion de la base de datos de patrones, y eltiempo de simulacion son mostrados en la siguiente tabla.

Tiempos

Pre-proceso 0,568sSimulacion 10m 6,522sTotal 10m 7,090s

Figura 7.8: Realizacion no condicionada de canales de tamano 500 × 500 pixeles utilizandotemplate de tamano 11× 11 pixeles.

85

(a) Horizontal (b) Vertical

Figura 7.9: Variogramas experimentales segun el eje X e Y de la realizacion mostrada en la fig.7.8. Los variogramas de color rojo corresponden a los de la imagen de entrenamiento (fig. 7.7) ylos negros a los de la realizacion.

86

Ejemplos no condicionados variando tamano de template

Esta prueba consistio en generar 100 realizaciones no condicionadas de tamano 100× 100pixeles para templates de tamano 5× 5, 7× 7, 9× 9, 11× 11, 13× 13, 15× 15 y 17× 17 pixeles.En la fig. 7.11 son mostradas las cuatro primeras realizaciones para cada tamano de template. Seaprecia como las imagenes simuladas se tornan mas limpias a medida que el tamano del templateaumenta. Las realizaciones de la ultima fila son notoriamente superiores que la de la primera; loscanales no pierden continuidad y son de un grosor mas constante. Por otro lado, dentro de lasrealizaciones de una misma fila, se aprecia un nivel similar de calidad.

En la fig. 7.12 son mostrados los variogramas experimentales en direccion horizontal (ejeX) y vertical (eje Y ) de las realizaciones no condicionadas segun los diferentes tamanos de tem-plate de la fig. 7.11. En general, no se observan mejoras en el ajuste del variograma al aumentarel tamano del template. Esto es esperable ya que el variograma es generado a partir de la relacionde dos puntos a la vez lo cual debiese ser reproducido utilizando cualquier tamano de template.

Los tiempos de simulacion, son mostrados en la siguiente tabla y graficodos segun el ta-mano del template en la fig. 7.10.

Tamano template

5× 5 7× 7 9× 9 11× 11 13× 13 15× 15 17× 17

Pre-proceso 0,859s 1,547s 2,409s 3,446s 4,749s 6,122s 8,977sSimulacion 2,633s 16,909s 1m 0,004s 8m 0,385s 25m 21,118s 42m 39,471s 1h 0m 37,290sSimulacion por realizacion 0,026s 0,169s 1,000s 5,123s 15,211s 25,594s 47,172sTotal 3,492s 18,456s 1m 0,413s 8m 3,831s 25m 0,867s 42m 3,593s 1h 0m 46,267sTotal por realizacion 0,034s 0,184s 1,024s 5,158s 15,258s 25,655s 47,262s

En el grafico (fig. 7.10) se aprecia como los tiempos varıan drasticamente al aumentar ladimensionalidad del template; tomando tan solo 3.492 segundos para 100 realizaciones utilizan-do un template de dimension 5× 5 pixeles, hasta alcanzar mas de una hora 46 segundos para untemplate de dimension 17× 17 pixeles.

87

Figura 7.10: Tiempos totales de simulacion.

88

Realizacion 1 Realizacion 2 Realizacion 3 Realizacion 4 Realizacion 55×5

7×7

9×9

11×11

13×13

15×15

17×17

Figura 7.11: Realizaciones no condicionadas de tamano 100×100 pixeles para distintos tamanosde template.

89

Horizontal Vertical Horizontal Vertical

5×

5

13×

13

7×

7

15×

15

9×

9

17×

17

11×

11

Figura 7.12: Variogramas experimentales de las realizaciones de la fig. 7.11 para distintos ta-manos de template. Las curvas de color rojo corresponden al variograma de la imagen de entre-namiento (fig. 7.7).

90

Ejemplos condicionados mediante fijacion de canales

Para estas realizaciones se impuso que en ciertas posiciones debiese pasar un canal yen otras no. En la fig. 7.13a se grafican estos puntos que corresponden a dos franjas vertica-les de un pıxel de grosor, ubicadas arbitrariamente sobre las columnas X = 26 y X = 81.Cada franja contiene zonas de canal de 8 pixeles de ancho. La primera franja contiene 4 zo-nas de canal mientras que la segunda 5 zonas. Esta configuracion tiene el proposito de ponera prueba el algoritmo y ver como resuelve que por la segunda franja pasen mas canales quepor la primera. Los canales sobre la primera franja corresponden a las columnas dentro de losintervalos[17, 24], [37, 44], [57, 64], [77, 84] y, los de la segunda, a las columnas dentro de losintervalos [12, 19], [28, 35], [44, 51], [60, 67] y [76, 83].

El experimento consistio en simular 100 realizaciones de tamano 100 × 100 pixeles uti-lizando el condicionamiento recientemente indicado y un template de tamano 11 × 11 pixeles.En la fig. 7.13 seis realizaciones son mostradas y son demarcadas con lıneas amarillas las zonascondicionadas. Se obtuvo ademas un mapa de probabilidades mostrado en la fig. 7.13b, que co-rresponde al promedio de todas las realizaciones. De las realizaciones se aprecia que el algoritmoresuelve de buena forma el problema, no generando discontinuidades en puntos cercanos a losdatos condicionantes. En el mapa de probabilidades se aprecian las zonas con mas probabili-dad por donde pueda pasar un canal y por las cuales no. En dicho mapa se observa continuidaden esas zonas. Los variogramas, tanto horizontales como verticales, mostrados en la fig. 7.14,muestran un buen ajuste a pesar del condicionamiento. Las 100 realizaciones se obtuvieron en15 minutos 13 segundos, un 88,6 % mas que el experimento sin condicionamiento para el mismotamano de template. La siguiente tabla resume el tiempo tomado por el algoritmo.

Tiempos

Pre-proceso 3,487sSimulacion 15m 8,807sSimulacion por realizacion 9,388sTotal 15m 12,294sTotal por realizacion 9,422s

91

(a) (b)

(c) (d) (e)

(f) (g) (h)

Figura 7.13: Realizaciones condicionadas a franjas con zonas de canal y no-canal, de tamano100 × 100 pixeles y generadas utilizando un template de tamano 11 × 11 pixeles. (a) Condicio-namiento utilizado. (b) Mapa de probabilidades. (c) - (h) Algunas realizaciones obtenidas.

92

(a) Horizontal (b) Vertical

Figura 7.14: Variogramas experimentales para las realizaciones condicionadas de la fig. 7.13. En(a) son mostrados los variogramas experimentales segun la direccion del eje X y en (b), segun eleje Y .

93

Ejemplos condicionados a puntos aleatorios

En esta prueba se genero aleatoriamente un conjunto de 16 puntos repartidos en igualnumero dentro de las categorıas canal y no-canal. Este conjunto de puntos es mostrado en la fig.7.15a y es utilizado como condicionamiento en la generacion de 100 realizaciones de tamano100 × 100 pixeles mediante un template de tamano 11 × 11 pixeles. Cuatro realizaciones sonmostradas en las fig. 7.15 las que muestran que a parte de ser respetado el condicionamiento, nose generan discontinuidades en torno a los puntos condicionantes. La fig. 7.15b muestra el mapade probabilidades generado.

Los variogramas mostrados en la fig. 7.15 muestran un buen ajuste tanto en la direccionhorizontal como vertical. El ajuste mejora con respecto al experimento de imposicion de canalesdel ejemplo anterior (fig. 7.14), lo que puede ser explicado por el menor numero de puntos arespetar.

El experimento tomo aproximadamente 14 minutos 5 segundos, lo que representa un74,72 % mas que el experimento que no considera condicionamiento. Los tiempos tomados porel algoritmo son mostrados en la siguiente tabla.

Tiempos

Pre-proceso 3,444sSimulacion 14m 1,898sSimulacion por realizacion 8.698sTotal 14m 5,342sTotal por realizacion 8,733s

94

(a) (b)

(c) (d)

(e) (f)

Figura 7.15: Realizaciones de tamano 100 × 100 pixeles condicionadas a 16 puntos aleatoriosgeneradas utilizando un template de tamano 11×11 pixeles. (a) Puntos condicionantes. (b) Mapade probabilidades. (c) - (f) Algunas realizaciones. Las posiciones muestrales son demarcadas porun cırculo de color verde para la categorıa canal y amarillo para el caso contrario.

95

(a) Horizontal (b) Vertical

Figura 7.16: Variogramas experimentales de las realizaciones condicionadas mostradas en la fig.7.15. En (a) son mostrados los variogramas experimentales segun la direccion del eje X y en (b),segun el eje Y .

96

7.3. Simulacion continua

7.3.1. Lineas verticales continuas

Para la simulacion continua se realiza a modo exploratorio la siguiente prueba. Se utilizacomo imagen de entrenamiento una imagen de lıneas verticales con valores continuos, mostradaen la fig. 7.17. Esta imagen fue construida sinteticamente a partir de una funcion sinusoidal convalor mınimo 0 y maximo 1.

East

Nort

h

0.0 100.000

0.0

100.000

0.0

0.1000

0.2000

0.3000

0.4000

0.5000

0.6000

0.7000

0.8000

0.900

1.000

Figura 7.17: Imagen de entrenamiento continua de 100×100 pixeles formada utilizando funcionsinusoidal con valor mınimo 0 y maximo 1.

Las realizaciones fueron obtenidas utilizando 100 valores de corte equidistantes entre 0, 01y 1. En las figs. 7.18 y 7.19 se muestran las cuatro primeras realizaciones de tamano 20 × 100pixeles, de un total de 100 realizaciones, utilizando un template de tamano 5×19 y 5×31, respec-tivamente. Los variogramas experimentales, horizontales y verticales, para las 10 realizacionesobtenidas utilizando ambos tamanos de template, son mostrados en la fig. 7.20.

En la siguiente tabla se muestran los tiempos tomados en obtener las realizaciones paraambos tamanos de template.

97

Tamano template

5× 19 5× 31

Pre-proceso 4,940s 7,461sSimulacion 3m 0,337s 4m 1.589sSimulacion por realizacion 1,863s 2,855sTotal 3m 2,277s 4m 1,050sTotal por realizacion 1,912s 2,930s

Los resultados de las figs. 7.18 y 7.19 no muestran resultados del todo satisfactorios, posi-blemente debido a la dificultad de la prueba. Si bien, al aumentar la dimensionalidad del templatelos resultados mejoran, tampoco dejan de mostrar irregularidades, tales como grandes saltos en-tre colores extremos, es decir, se pasa de una tonalidad roja a una azul sin pasar por valoresintermedios. Mas aun, el utilizar grandes templates para obtener mejores resultados, puede so-breajustar las realizaciones. Notar que los cambios de tonalidades solo se producen al comienzode cada fila. Esto debido a que en estas posiciones solo los pixeles inferiores, segun el eje Y ,condicionan el valor a asignar, de modo que, el algoritmo puede elegir un valor con una mayordiferencia de tonalidad.

Los variogramas horizontales, 7.20a y 7.20d, muestran lo esperado, es decir, que no hayvariacion segun el eje X . Por otro lado, los variogramas verticales, 7.20b y 7.20c, muestran unbuen ajuste, sobre todo, al utilizar patrones de mayor dimensionalidad. Por ende, estas realizacio-nes logran reproducir relaciones de dos puntos aunque muestran imperfecciones en los valoresextremos.

98

(a) (b)

(c) (d)

Figura 7.18: Realizaciones de simulacion continua de la imagen de entrenamiento 7.17 de tamano100 × 100 pixeles. Las realizaciones fueron obtenidas utilizando un patron de tamano 5 × 19pixeles.

99

(a) (b)

(c) (d)

Figura 7.19: Realizaciones de simulacion continua de la imagen de entrenamiento 7.17 de tamano100 × 100 pixeles. Las realizaciones fueron obtenidas utilizando un patron de tamano 5 × 31pixeles.

100

(a) horizontales (b) verticales

(c) horizontales (d) verticales

Figura 7.20: Variogramas experimentales segun la direccion del eje X y del eje Y para las reali-zaciones condicionadas de la figs. 7.18 y 7.19, obtenidas utilizando templates de tamano 5× 19pixeles, graficos (a) y (b), y 5 × 31 pixeles, graficos (c) y (d). Los variogramas de color rojocorresponden a los variogramas de la imagen de entrenamiento de la fig. 7.17.

101

7.4. Simulacion 3D

El algoritmo fue probado en la obtencion de una realizacion de tres dimensiones no condi-cionada, utilizando como imagen de entrenamiento la grilla mostrada en la fig. 7.21, que contem-pla cinco categorıas con ındices: 0, 1, 2, 4 y 5. La primera imagen de dicha figura corresponde auna visualizacion en que las categorıas con ındices 0 a 2 son mostradas transparentes. Las demasimagenes corresponden a distintos cortes en el plano XY para Z con valores 25, 50, 75 y 100.

Para la recuperacion de los patrones se utilizo un template de tamano 5× 5× 3 pixeles, loque se traduce en la utilizacion de patrones causales de 37 nodos. La grilla utilizada como imagende entrenamiento es de tamano 256×256×128 pixeles, es decir, un total de 8.388.608 de nodos, locual es una cantidad bastante grande a considerar. Dado el tamano de la imagen de entrenamiento,se modifico el algoritmo para obtener una sola realizacion, realizando las busquedas de patronesen paralelo sobre la estructura de datos. La paralelizacion se obtuvo repartiendo la busquedade patrones mas cercanos en distintos segmentos de la estructura de datos basada en una listaenlazada. Se utilizo un numero de procesos igual al doble de CPUs disponibles en cada busqueda,es decir 16 procesos. Los tiempos de este experimento se resumen en la siguiente tabla.

Tiempos

Pre-proceso 5m 04,537sSimulacion 8h 2m 20,142sTotal 8h 7m 49,679s

La realizacion obtenida, de tamano 100 × 100 × 25 pixeles, es mostrada en la fig. 7.22,donde la primera imagen corresponde a una visualizacion 3D de la realizacion y la segunda auna visualizacion transparente en que se resaltan las categorıa 4 y 5. Las demas imagenes dela fig. 7.22 son distintos cortes del plano XY para los valores de de Z: 0, 4, 9, 13, 19 y 24.Los distintos cortes de la realizacion muestran una cierta reproduccion de las estructuras de laimagen de entrenamiento. Esta reproduccion podrıa ser mejorada utilizando templates de mayordimensionalidad, dado que las estructuras que se intentan reproducir son a gran escala. Usartemplates mas grandes se dificulta debido al tamano de la imagen de entrenamiento.

Los variogramas experimentales de la imagen de entrenamiento (curva roja) y los de larealizacion (curva negra) para las cinco categorıas y en las direcciones del eje X y el eje Y sonmostrados en la fig. 7.23. Se aprecia un mejor ajuste para las categorıas 1, 4 y 5 que para el resto.

102

(a)

(b) z = 25 (c) z = 50

(d) z = 75 (e) z = 100

Figura 7.21: Grilla de entrenamiento 3D de tamano 256×256×128 y de 5 categorıas. La primeraimagen (a) corresponde a una visualizacion en que las categorıas con ındices 0 a 2 son mostradastransparentes. Las demas imagenes corresponden a distintos cortes en el plano XY .

103

(a) (b)

(c) z = 0 (d) z = 4 (e) z = 9

(f) z = 13 (g) z = 19 (h) z = 24

Figura 7.22: Realizacion 3D. La imagen (a) corresponde a una visualizacion 3D de la realizacionobtenida. La imagen (b) es una visualizacion transparente salvo para las categorıas 4 y 5. Lasimagenes (c) hasta la (h) corresponden a distintos cortes del plano XY .

104

Horizontal Vertical

Cat

egor

ıa0

Cat

egor

ıa1

Cat

egor

ıa2

Cat

egor

ıa4

Cat

egor

ıa5

Figura 7.23: Variogramas experimentales de la realizacion 3D.

105

Capıtulo 8

Conclusiones

Como resultado de la investigacion, desarrollo y pruebas se mostro que es posible simulardiferentes escenarios de igual probabilidad para una variable aleatoria georeferenciada, respe-tando la continuidad y el condicionamiento dado por un conjunto de puntos conocidos a priori.Se mostro ademas que el problema de sıntesis de texturas no dista tanto del problema de simu-lacion geoestadıstica, por lo que tecnicas de computacion grafica pueden servir como base paraalgoritmos de simulacion de multiples puntos. La principal diferencia entre estas dos areas es elcondicionamiento, presente en los problemas de simulacion geoestadıstica, lo que fue resueltopor el algoritmo desarrollado CUTSIM.

Por otro lado, el trabajo realizado sirvio para el desarrollo de las siguientes publicaciones:“Conditional Multiple-Point Simulation with a Texture Synthesis Algorithm” [PO09], “Multiple-Point Conditional Unilateral Simulation for Categorical Variables” [PO10b] y “Conditional Mul-tiple Point Simulation with Texture Synthesis” [PO10a], que han sido realizadas en gran medidacon los resultados obtenidos de esta tesis.

Los resultados de esta tesis se resumen a continuacion:

Se desarrollo e implemento el algoritmo CUTSIM [PO09] [PO10b] para simulacion ca-tegorica, tanto en 2 como en 3 dimensiones, tomando como base el algoritmo de sıntesisde texturas desarrollado por [Wei01]. Mediante este algoritmo y simulacion de indicadores,se desarrollo una metodologıa para simulaciones de variables continuas.

Se extendio y mejoro biblioteca de patrones desarrollada como parte de la memoria deingenierıa civil en computacion del autor [Par08].

Se realizo la implementacion paralela del algoritmo de simulacion continua, ejecutando demanera concurrente los procesos que calculan la estimacion de la distribucion para cada

106

valor de corte.

Se realizaron pruebas en 2D que muestran que la variabilidad espacial es reproducida yque el condicionamiento es respetado.

Se realizaron pruebas en 3D con el el fin de probar la implementacion.

Se logro adaptar la metodologıa de sıntesis de texturas propuesta en [Wei01] para producirun algoritmo de simulacion geoestadıstica, mostrando que es posible utilizar el camino unilateralen simulacion secuencial, permitiendo realizar simulaciones de forma mas eficientes debido, porejemplo, a que no es necesario realizar la busqueda de los vecinos mas cercanos. Uno de lospuntos crıticos del algoritmo es el condicionamiento, resuelto mediante la incorporacion de untemplate no-causal que permite modificar la distribucion de la variable a simular y, de este modo,respetar la informacion condicionante. El algoritmo es eficiente, debido a la utilizacion de unaestructura de datos en base a una lista enlazada que ahorra consumo de memoria RAM y aceleralas busquedas.

Las pruebas realizadas muestran que el algoritmo desarrollado es rapido, tomando alre-dedor de 15 minutos para ejemplos condicionados utilizando un template de 11 × 11 pixe-les.Ademas, es capaz de trabajar con mas de 225 dimensiones, debido a que la utilizacion deuna estructura de datos en base a una lista enlazada ahorra consumo de memoria RAM.

8.1. Trabajo futuro

Si bien la metodologıa fue probada y se obtuvo una implementacion del algoritmo facilde usar y modificar, mas pruebas a realizar, sobe todo en 3D y simulacion continua, serıan deutilidad. Por otro lado, nuevas ideas surgieron al final de este trabajo que son interesantes deexplorar, en particular con lo que ha paralelizacion se refiere, que se sugiere como trabajo futuro.A continuacion se describe la metodologıa de paralelizacion propuesta.

8.1.1. Paralelizacion del camino unilateral

Es posible acelerar la metodologıa paralelizando el algoritmo y simulando varios puntosdentro de un camino unilateral. Para ello, el campo a ser simulado es dividido en regiones, demodo que en cada region, uno o mas nodos puedan ser simulados simultaneamente y sin pro-blemas de comunicacion entre procesos. Dado que el camino en que los nodos son recorridos esconocido, tambien lo son los nodos condicionantes requeridos para la simulacion de posicionesespecıficas.

107

La paralelizacion es lograda paralelizando la simulacion de filas (fig. 8.1). El algoritmono-paralelo comienza la asignacion desde el primer nodo de la fila de mas abajo de la grilla de larealizacion. Dependiendo del template causal, es posible definir cuantos nodos r deben ser simu-lados antes de que se empiece a simular un segundo nodo en la segunda fila. Cuando r nodos hansido simulados en la primera fila, un segundo proceso puede comenzar a simular el primer nodode la segunda fila, ya que la informacion condicionante requerida ya se encuentra disponible (yaha sido simulada). Concurrentemente, el nodo r+ 1 de la primera fila estara siendo simulado porel primer proceso. Esta estrategia puede ser repetida de modo de alcanzar un maximo de procesosconcurrentes predefinido. El speed up de esta estrategia dependera del numero de procesadoresdisponibles, el tamano del template y de la grilla.

(a) Template (b) Simulacion

Figura 8.1: Ilustracion de una simulacion paralela. La zona amarilla representa a los nodos simu-lados, los cuatro nodos marcados seran simulados al mismo tiempo.

8.1.2. Busqueda de patrones

La busqueda de patrones es uno de los factores crıticos del algoritmo, y uno de los puntoscentrales para hacerlo eficiente. Si bien el uso de estructuras de datos es de utilidad, otras estra-tegias podrıan ser probadas, por ejemplo, probar heurısticas de busquedas aproximadas, tecnicasde agrupamiento de patrones, reduccion de dimensionalidad, etc. Serıa interesante probar algunaestrategia para acelerar la busqueda, sobre todo para obtener menores tiempos en simulaciones3D.

108

Bibliografıa

[And58] T.W. Anderson. An introduction to multivariate statistical analysis. Wiley-Interscience, 1958.

[CD99] Jean-Paul Chiles and Pierre Delfiner. Geostatistics: Modeling Spatial Uncertainty.Wiley, 1999.

[Cla79] Isobel Clark. Practical Geostatistics. Applied Science Publishers, 1979.

[Dal05] C. Daly. Higher order models using entropy, Markov random fields and sequentialsimulation. Geostatistics Banff 2004, pages 215–224, 2005.

[DJ92] Clayton Deutsch and Andre Journel. GSLIB: Geostatistical Software Library andUser’s Guide. Oxford University Press, Inc., 1992.

[DK07] C. Daly and C. Knudby. Multipoint statistics in reservoir modelling and in computervision. Petroleum Geostatistics 2007, Cascais, Portugal, 2007.

[Eme07a] Xavier Emery. Apunte de geoestadıstica, Septiembre 2007.

[Eme07b] Xavier Emery. Presentaciones catedra: Topicos avanzados en evaluacion de yaci-mientos, universidad de chile. 2007.

[Goo97] Pierre Goovaerts. Geostatistics for Natural Resources Evaluation. Applied Geoes-tatistics Series. Oxford University Press, Reading, Massachusetts, 1997.

[GS93] Felipe B. Guardiano and R. Mohan Srivastava. Multivariate geostatistics: Beyondbivariate moments. Geostatistics-Troia, 1:133–144, 1993.

[Har79] RM Haralick. Statistical and structural approaches to texture. Proceedings of theIEEE, 67(5):786–804, 1979.

[HDS73] R.M. Haralick, I. Dinstein, and K. Shanmugam. Textural features for image classi-fication. IEEE Transactions on systems, man, and cybernetics, 3(6):610–621, 1973.

[Jou93] A.G. Journel. Geostatistics: roadblocks and challenges. Geostatistics Troia, 92:213–224, 1993.

109

[Kri51] DG Krige. A statistical approach to some mine valuations and allied problems atthe Witwatersrand. Master’s thesis, University of Witwatersrand, 1951.

[LHW+04] Wen-Chieh Lin, James H. Hays, Chenyu Wu, Vivek Kwatra, and Yanxi Liu. Acomparison study of four texture synthesis algorithms on regular and near-regulartextures. SIGGRAPH 2004 Poster, 2004.

[Mat62] G. Matheron. Traite de Geostatistique Appliquee, Tome I. Memoires du Bureau deRecherches Geologiques et Minieres, 14, 1962.

[Mat63] G. Matheron. Traite de geostatistique appliquee, tome II. Editions Techniques, Paris,1963.

[MXS08] Majid Mirmehdi, Xianghua Xie, and Jasjit Suri. Handbook of Texture Analysis.Imperial College Press, 2008.

[Pag99] Rupert D. Paget. Nonparametric Markov Random Field Models for Natural TextureImages. PhD thesis, The University of Queensland, February 1999.

[Par62] E. Parzen. On estimation of a probability density function and mode. The annals ofmathematical statistics, 33(3):1065–1076, 1962.

[Par08] Alvaro Parra Bustos. Extraccion de patrones desde imagenes de entrenamiento parasimulacion geoestadıstica. Memoria de Ingenierıa Civil en Computacion, Universi-dad de Chile, 2008.

[PL98] R. Paget and I.D. Longstaff. Texture synthesis via a noncausal nonparametric multis-cale Markov random field. IEEE Transactions on Image Processing, 7(6):925–931,1998.

[PO09] Alvaro Parra Bustos and Julian Ortiz C. Conditional multiple-point simulation witha texture synthesis algorithm. IAMG 09 Conference, Stanford University, 2009.

[PO10a] Alvaro Parra Bustos and Julian Ortiz C. Conditional multiple point simulation withtexture synthesis. Geoenv 2010, 8th International Conference on Geostatistics forEnvironmental Applications, pages 13–15, September 2010.

[PO10b] Alvaro Parra Bustos and Julian Ortiz C. Multi-point conditional unilateral simula-tion for categorical variables. MININ 2010—III Conference on Mining Innovation,June 2010.

[PP93] K. Popat and R.W. Picard. Novel cluster-based probability model for texture synt-hesis, classification, and compression. In Society of Photo-Optical InstrumentationEngineers (SPIE) Conference Series, volume 2094, pages 756–768. Citeseer, 1993.

[Rob97] E. Roberts. Programming abstractions in C: a second course in computer science,pages 537–596. Addison Wesley, 1997.

110

[Sic52] HS Sichel. New methods in the statistical evaluation of mine sampling data. Tran-sactions of the Institution of Mining and Metallurgy, 1952.

[Str02] Sebastien Strebelle. Conditional simulation of complex geological structures usingmultiple-point statistics. Mathematical Geology, 2002.

[SWF+08] J. STRAUBHAAR, A. WALGENWITZ, R. FROIDEVAUX, P. RENARD, andO. BESSON. OPTIMISATION ISSUES IN 3D MULTIPLE–POINT STATISTICSSIMULATION. In GEOSTATS 2008, December 2008.

[Vie01] Alvaro Egana Viedma. Busqueda en bases de datos de imagenes. Memoria deIngenierıa Civil en Computacion, Universidad de Chile, 2001.

[Wei01] L.Y. Wei. Texture synthesis by fixed neighborhood searching. PhD thesis, StanfordUniversity, 2001.

[WL00] L.Y. Wei and M. Levoy. Fast texture synthesis using tree-structured vector quan-tization. In Proceedings of the 27th annual conference on Computer graphics andinteractive techniques, pages 479–488. ACM Press/Addison-Wesley Publishing Co.New York, NY, USA, 2000.

111