universidad de chile facultad de ciencias...

UNIVERSIDAD DE CHILE

FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS

DEPARTAMENTO DE CIENCIAS DE LA COMPUTACION

PARALELIZACION Y COMPARACION ENTRE ALGORITMOS PARA EL CALCULODE DISTRIBUCION DE TAMANOS DE BURBUJAS VIA ANALISIS DE IMAGENES

MEMORIA PARA OPTAR AL TITULO DE INGENIERO CIVIL EN COMPUTACION

FELIPE ANDRES GARRIDO RODRIGUEZ

PROFESOR GUIA:WILLY KRACHT GAJARDO

MIEMBROS DE LA COMISION:NANCY HITSCHFELD KAHLER

JOSE MIGUEL PIQUER GARDNER

SANTIAGO DE CHILEDICIEMBRE 2011

Resumen

La flotacion es un proceso ampliamente utilizado en la concentracion de minerales sul-furados de cobre. Este se caracteriza por la separacion selectiva de minerales en funcion desu hidrofobicidad. Para esto, partıculas suspendidas en agua se ponen en contacto con bur-bujas de aire. Las partıculas hidrofobicas -sulfuros de cobre- se adhieren a las burbujas yascienden junto con ellas, separandose del resto de los minerales. El desempeno del procesoesta fuertemente relacionado con la distribucion de tamanos de burbujas disponible para laseparacion.

El objetivo de este trabajo es comparar dos alternativas de analisis de imagen para ladeterminacion de distribuciones de tamanos de burbujas. El primero de ellos corresponde almetodo clasico o tradicional, el cual se basa en algoritmos de segmentacion para la identi-ficacion y caracterizacion de objetos en la imagen. El segundo corresponde a la aplicacionde herramientas estadısticas que permiten realizar el analisis sin necesidad de recurrir a laidentificacion de objetos individuales.

Para comparar la calidad de la respuesta se utilizo cuatro estadısticos. Los dos primerosson la media y la varianza no centrada de la distribucion. El tercer estadıstico utilizado esel momento de tercer orden. El cuarto, y de mayor interes, es el diametro de Sauter, el cualrelaciona el volumen de una burbuja con su superficie y es utilizado en los modelos quedescriben la flotacion.

Para implementar los metodos se utilizo el lenguaje de programacion Python, con lalibrerıas Scipy y Numpy. Tambien se utilizo codigo en C para mejorar los tiempos de algunastareas. El procesamiento paralelo utilizado fue multiproceso y fue implementado solo para elmetodo estocastico. El metodo tradicional no se pudo paralelizar, pues las tareas intensivas enuso de recursos fueron implementadas en C, y la programacion concurrente en este lenguajehubiese requerido mas tiempo del que se disponıa.

Los resultados indican que el metodo estocastico mantiene su error acotado cuando au-menta el tamano de las burbujas, a diferencia del metodo clasico, el cual comienza a ser maserratico. En particular, el diametro de Sauter estimado por el metodo estocastico tiene unerror menor al obtenido con el metodo clasico. La velocidad, adaptatividad y estabilidad delmetodo estocastico, sumado a los buenos resultados al estimar el diametro de Sauter, haceque sea muy atractivo a la hora de implementar soluciones con el.

1

Indice general

1. Introduccion 1

1.1. Justificacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2. Objetivo General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3. Objetivos Especıficos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4. Metodologıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.5. Contenido de la Memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2. Antecedentes 6

2.1. Procesamiento y Analisis de Imagenes y Senales . . . . . . . . . . . . . . . . 6

2.1.1. Manipulacion Curvas de Colores . . . . . . . . . . . . . . . . . . . . . 6

2.1.2. Cuantizacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.3. Operaciones Morfologicas . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.4. Mapa de Distancias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.5. Watershed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.6. Filtros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.7. Espacios de Escala . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

i

2.2. Modelo Booleano Estacionario . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3. Doubling Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3. Procesamiento previo de las imagenes 17

3.1. Eliminacion de ruido del dispositivo de captura . . . . . . . . . . . . . . . . 18

3.2. Cuantizacion y Binarizacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.3. Rellenado de burbujas y eliminacion de ruido . . . . . . . . . . . . . . . . . 22

4. Procesamiento Clasico 26

4.1. Transformacion a escala de grises . . . . . . . . . . . . . . . . . . . . . . . . 27

4.2. Watershed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.3. Calculo de metricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.4. Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.4.1. Procesamiento paralelo . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5. Procesamiento estocastico 35

5.1. Calculo del Avoiding Functional . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.2. Estimacion de los momentos . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.3. Estimacion de θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.4. Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.4.1. Procesamiento paralelo . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6. Resultados Obtenidos 56

ii

6.1. Calidad de respuesta, tiempo de ejecucion y uso de memoria v/s tamano dela imagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6.2. Python v/s C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6.3. Uso de recursos al utilizar procesamiento paralelo en metodo clasico . . . . . 62

6.4. Uso de recursos al utilizar procesamiento paralelo en metodo estocastico . . . 63

6.5. Dependencia de submuestreo en la calidad de la respuesta . . . . . . . . . . 64

6.6. Efectos de la cantidad de burbujas en la estimacion . . . . . . . . . . . . . . 65

6.7. Experimento principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

7. Conclusiones 71

A. Tablas 74

iii

Indice de figuras

1.1. Ejemplo de Watershed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.1. Ejemplo de transformacion sobre canal azul . . . . . . . . . . . . . . . . . . 7

2.2. Ejemplo de Histograma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3. Ejemplo de cuantizacion de colores . . . . . . . . . . . . . . . . . . . . . . . 8

2.4. Ejemplo de dilatacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.5. Ejemplo de erosion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.6. Ejemplo de opening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.7. Ejemplo de closing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.8. Ejemplo de deteccion de bordes . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.9. Vecindades comunmente utilizadas para detectar bordes . . . . . . . . . . . . 11

2.10. Ejemplo de Mapas de Distancias con respecto al fondo de la imagen, conp = (p1, . . . , pn) y q = (q1, . . . , qn). . . . . . . . . . . . . . . . . . . . . . . . . 12

2.11. Ejemplo de etapas en la inundacion simulada por Watershed . . . . . . . . . 13

2.12. Ejemplo de doubling search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.1. Ejemplo burbujas no rellenas tras la binarizacion . . . . . . . . . . . . . . . 17

3.2. Ejemplo de ruido producidos por el dispositivo de captura . . . . . . . . . . 19

iv

3.3. Ejemplo de imagen transformada (Eliminacion del ruido del dispositivo decaptura) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.4. Ejemplo de la cuantizacion sobre el borde de una burbuja . . . . . . . . . . . 22

3.5. Ejemplo del primer metodo de rellenado de burbujas . . . . . . . . . . . . . 23

3.6. Ejemplo del segundo metodo de rellenado de burbujas . . . . . . . . . . . . . 24

3.7. Ejemplo del tercer metodo de rellenado de burbujas . . . . . . . . . . . . . . 25

3.8. Ejemplo de error y solucion para encontrar fondo de la imagen . . . . . . . . 25

4.1. Ejemplo del transformada de distancia por fuerza bruta . . . . . . . . . . . . 28

4.2. Ejemplo de escenarios en la revision del algoritmo Watershed . . . . . . . . . 30

4.3. Diagrama de Watershed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.1. Conjunto K y ejemplos para avoiding functional . . . . . . . . . . . . . . . . 37

5.2. Numeracion posible de pıxeles, para barrido completo . . . . . . . . . . . . . 37

5.3. Estimacion del avoiding functional usando un barrido completo, filas y colum-nas, y muestreo sobre filas y columnas . . . . . . . . . . . . . . . . . . . . . 38

5.4. Demostracion del procedimiento para calculo de avoiding functional . . . . . 39

5.5. Ejemplo de muestreo sobre filas y columnas . . . . . . . . . . . . . . . . . . 40

5.6. Proceso de redimensionado y slicing para obtener matriz con filas muestreadas 41

5.7. Ejemplo de Ψ′′(h) original . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.8. Curva suavizada y estimacion del cero para la curva . . . . . . . . . . . . . . 47

5.9. θ · (1− F (a)): Curva teorica y curva real . . . . . . . . . . . . . . . . . . . . 49

5.10. Ejemplo de la estimacion de los puntos que corresponden a la meseta . . . . 50

5.11. Estimador de θ utilizando una regresion lineal . . . . . . . . . . . . . . . . . 50

v

5.12. Ejemplo de la sucesion θσ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.13. Diferencia entre maximos locales consecutivos . . . . . . . . . . . . . . . . . 53

6.1. Calidad de la respuesta, tiempo de ejecucion y memoria utilizada, para metodoclasico y metodo estocastico. . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.2. Dilatacion: Grafico de Tiempo v/s Tamano del elemento estructural. . . . . . 59

6.3. Dilatacion: Grafico de Tiempo v/s Tamano de la imagen para Dilatacion. . . 59

6.4. Transformada de distancia: Grafico de Tiempo v/s Tamano de la imagen. . . 60

6.5. Watershed: Grafico de Tiempo v/s Tamano de la imagen. . . . . . . . . . . . 61

6.6. Comparacion de tiempos de ejecucion y uso de memoria para el metodo clasico 62

6.7. Comparacion de tiempos de ejecucion y uso de memoria para metodo estocastico 63

6.8. Comparacion de tiempos de ejecucion y desviacion estandar para estimacionde T (K) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

6.9. Diametro promedio y error porcentual v/s cantidad de burbujas en la imagen 65

6.10. Tiempo de calculo v/s cantidad de burbujas en la imagen . . . . . . . . . . . 66

6.11. Resultados para metodo clasico . . . . . . . . . . . . . . . . . . . . . . . . . 69

6.12. Resultados para metodo estocastico . . . . . . . . . . . . . . . . . . . . . . . 70

6.13. Uso de recursos para metodo clasico y estocastico. . . . . . . . . . . . . . . . 70

vi

Indice de tablas

6.1. Tabla de tiempo de ejecucion v/s tamano del elemento estructural, para dilat-acion en Python y C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6.2. Tabla de tiempo de ejecucion v/s tamano de la imagen, para dilatacion enPython y C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.3. Tabla de tiempo de ejecucion v/s tamano de la imagen, para transformada dedistancia en Python y C con fuerza bruta, y propagacion en C . . . . . . . . 60

6.4. Tabla de tiempo de ejecucion v/s tamano de la imagen, para Watershed enPython y C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6.5. Resultados test pre-eliminar . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

A.1. Error absoluto v/s tamano de la imagen. El error esta medido en funcion dela imagen original de 127x84.6 (AutoCAD) . . . . . . . . . . . . . . . . . . . 74

A.2. Tiempo de calculo v/s tamano de la imagen . . . . . . . . . . . . . . . . . . 75

A.3. Memoria utilizada v/s tamano de la imagen . . . . . . . . . . . . . . . . . . 75

A.4. Tabla de tiempo de calculo y uso de memoria v/s cantidad de threads paralelosen metodo estocastico, para imagenes de 1500x1000 pıxeles . . . . . . . . . . 75

A.5. Tabla de tiempo de calculo y uso de memoria v/s cantidad de threads paralelosen metodo estocastico, para imagenes de 1500x1000 pıxeles . . . . . . . . . . 76

A.6. Tabla de tiempo de ejecucion v/s tamano del muestreo para avoiding func-tional, para imagenes de 1500x1000 pıxeles . . . . . . . . . . . . . . . . . . . 76

vii

A.7. Tabla de desviacion estandar del resultado v/s tamano del muestreo paraavoiding functional, para imagenes de 1500x1000 pıxeles . . . . . . . . . . . 77

A.8. Resultado obtenido para imagenes con distintas cantidades de burbujas, paraimagenes de 1500x1000 pıxeles . . . . . . . . . . . . . . . . . . . . . . . . . . 77

A.9. Tiempo de calculo para imagenes con distintas cantidades de burbujas, paraimagenes de 1500x1000 pıxeles . . . . . . . . . . . . . . . . . . . . . . . . . . 78

A.10.Mınimo, promedio y maximo de las estimaciones de µ1 para Watershed v/stamano del grupo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78



A.13.Mınimo, promedio y maximo de las estimaciones de d32 para Watershed v/stamano del grupo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

A.14.Mınimo, promedio y maximo de las estimaciones de µ1 para metodo estocasticov/s tamano del grupo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79



A.17.Mınimo, promedio y maximo de las estimaciones de d32 para metodo estocasti-co v/s tamano del grupo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

viii

Indice de Algoritmos

3.1. Calculo de coeficientes de spline cubica natural . . . . . . . . . . . . . . . . 203.2. Pintado de un area seleccionada . . . . . . . . . . . . . . . . . . . . . . . . . 234.1. Watershed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.1. Obtencion del muestreo aleatorio . . . . . . . . . . . . . . . . . . . . . . . . 425.2. Estimacion de los momentos de orden k . . . . . . . . . . . . . . . . . . . . . 46

ix

Capıtulo 1

Introduccion

Un problema tıpico que se intenta resolver en el area de analisis de imagenes, es identi-ficar objetos para obtener cierta informacion acerca de los mismos. Dentro de este problema,existen, a la vez, varios casos con sus respectivas dificultades; una de las cuales es separarestos objetos cuando aparecen agrupados en una imagen (clusteres). La solucion mas uti-lizada para resolver este problema asume objetos de formas basicas, principalmente porquecuando este se presenta, la forma de los objetos suele ser simple. La formacion de clusteresgeneralmente ocurre cuando existen muchos objetos en una imagen, por lo cual, la caracter-izacion detallada de cada objeto de manera individual no es tan relevante. En este contexto,se privilegian metricas sobre el conjunto completo, como la distribucion de objetos segunalguna caracterıstica, media y varianza de la distribucion, o cantidad de objetos. En el Labo-ratorio Avanzado para la geoestadıstica y supercomputo (ALGES, por su sigla en ingles), sedesarrollo un algoritmo que permite, por medio de tecnicas estadısticas avanzadas, identificarla distribucion de objetos por tamano. El algoritmo, en adelante llamado metodo estocastico,fue creado con la intencion de caracterizar una distribucion de burbujas como las que seencuentran en la flotacion, sin embargo, este resuelve el problema para cualquier objeto deforma circular. Este nuevo algoritmo se comparo con la tecnica para desagrupar objetos porantonomasia, es decir, el algoritmo clasico, basado en Watershed[1].

El metodo clasico utiliza una imagen en escala de grises, la cual se interpreta como unmapa topografico, donde la intensidad del gris es la altura del relieve. El metodo simula unainundacion, la cual comienza en los mınimos locales y termina cuando se cubre todo el mapa.La idea es encontrar la frontera donde las aguas, provenientes de dos o mas fuentes distintas,se encuentran, pues esta sera la separacion entre los objetos. Para poder utilizar esta tecnicase calcula un mapa de distancias sobre la imagen en blanco y negro, donde, para cada pıxelde cada uno de los objetos, se calcula la distancia mınima a un pıxel perteneciente al fondode la imagen. Posteriormente, se simula la inundacion, se separan los clusteres de objetosy, finalmente, se calcula el radio de cada objeto. Para obtener el radio del objeto se calculael mapa de distancias sobre la imagen resultante de la inundacion. Calculado el mapa dedistancias, el punto con el valor maximo en cada objeto, corresponde al centro del objeto, yel valor en dicho punto corresponde al radio del objeto, tal como se observa en la Figura 1.1.

1

(a) Imagen binaria (b) Mapa de distancias

(c) Imagen desagrupada (d) Imagen final

Figura 1.1: Ejemplo de Watershed

El metodo estocastico[4] considera un proceso de Poisson por medio del cual se obtiene unconjunto de puntos en el plano, estas posiciones corresponden a la ubicacion de los objetos.Adicionalmente se define una familia de objetos con ciertas caracterısticas como compaci-dad, independencia y que se distribuyen de una manera particular. Esta familia de objetoscorresponde a los objetos en estudio y esta relacionada biunıvocamente con las posiciones an-teriormente descritas. Con estos elementos se puede definir un modelo booleano estacionariocomo la familia de objetos ubicados en sus posiciones respectivas y, al resto del plano comoel complemento. Se define tambien un conjunto K, elegido arbitrariamente segun la forma delos objetos de la imagen. Una vez definidos el modelo booleano estacionario y este conjuntoK se puede calcular la probabilidad de que dicho conjunto K no este contenido en el modelobooleano estacionario, es decir, este totalmente contenido en el complemento. Esta probabili-dad permite, por medio del calculo numerico, y basandose en la teorıa geoestadıstica, obtenerla distribucion de tamanos para la familia de objetos.

Las diferencias entre los metodos saltan a la vista, pues el primero se centra en la iden-tificacion de los objetos y su posterior caracterizacion de forma individual. A diferencia delmetodo estocastico, el cual, en base a las frecuencias calculadas experimentalmente, obtienela distribucion del conjunto completo. El metodo clasico tiene una serie de desventajas, yaque introduce varias fuentes de sesgo, como no tomar en cuenta las burbujas cortadas enlos bordes de la imagen, las burbujas ocultas tras otras de mayor tamano, o bien las burbu-jas que se obtienen de la separacion de los clusteres, las cuales quedan levemente cortadas.El metodo estocastico, a su vez, puede presentar problemas en caso de existir anisotropıaen alguna direccion, lo cual no respetarıa que las posiciones se obtienen por un proceso dePoisson, sin embargo, no existe motivo, a priori, para suponer que se de dicha anisotropıa.

2

1.1. Justificacion

La aplicacion que motivo el desarrollo del algoritmo estocastico anteriormente descrito,es obtener la distribucion de burbujas por tamanos, basados en una fotografıa obtenida enuna celda de flotacion. En este proceso de identificar la distribucion de burbujas por tamano,generalmente se eliminan los clusteres de la imagen, lo cual produce un sesgo. Dicho sesgo seve mitigado levemente por el uso del algoritmo clasico. Sin embargo, esto requiere un costocomputacional relativamente alto, ademas de que contribuye con el sesgo que inducen lasburbujas cortadas producto de la separacion.

La flotacion es el proceso de concentracion de minerales sulfurados de cobre mas utilizadoen la actualidad. Este proceso se basa en la separacion selectiva de minerales en base adiferencias de hidrofobicidad, la cual puede ser modificada mediante un control quımicodel sistema[7]. En el proceso de flotacion el mineral, finamente molido, se mezcla con aguapara formar una mezcla conocida como pulpa, en la que se inyecta aire en forma de burbujas.Aquellas partıculas de caracter hidrofobico tienden a evitar el contacto con agua, adhiriendosea las burbujas y ascendiendo con ellas para ser colectadas, posteriormente, como concentrado.La cantidad de concentrado y la velocidad con que se produce esta ıntimamente relacionadacon la cantidad y tamano de las burbujas disponibles para que ocurra el proceso. Esto hacenecesario contar con herramientas que permitan, determinar la distribucion de tamanos deburbujas, sin los sesgos anteriormente descritos y en un tiempo aceptable.

Ademas de la aplicacion anterior, el problema de caracterizar conjuntos de objetos en unaimagen se encuentra en distintas areas de la ciencia. Este problema se presenta en el area dela medicina, donde existe la necesitad de contar ciertos tipos de celulas, como por ejemplo,eritrocitos en la sangre. Tambien se presenta en el campo de la astronomıa donde se puedeutilizar para separar estrellas en un cluster de estrellas. Las aplicaciones posibles son muchas,por lo cual comparar ambos metodos es muy util, sobre todo para poder presentar el metodoestocastico como una alternativa sobre el algoritmo clasico.

De entre las metricas que se pueden calcular para comparar los metodos anteriormentedescritos, se eligieron tres, por ser las de mayor interes al problema particular que motivo estamemoria. Las metricas calculadas seran los momentos de primer, segundo y tercer orden. Losdos primeros por ser los estadısticos clasicos de una distribucion. El momento de tercer ordense calculara para poder obtener un estadıstico llamado d32, el cual corresponde al diametrode Sauter, el cual corresponde a al momento de tercer orden dividido por el momento desegundo orden. Esta metrica posee una relacion directa con la velocidad a la que ocurre elproceso de flotacion.

La comparacion se hizo en base a tres aspectos, siendo los dos primeros los mas impor-tantes. El primer aspecto es la calidad en la respuesta. Para esto se comparo los resultadosobtenidos con los valores reales. Para esto se conto con la cantidad y tamanos reales de lasburbujas en las imagenes analizadas. El segundo aspecto, muy importante a nivel practico,es el tiempo de ejecucion. El tiempo de ejecucion no incluyo el procesamiento previo de lasimagenes, es decir, se midio el tiempo partiendo con las imagenes en blanco y negro. El tercer

3

y ultimo aspecto es la memoria utilizada, lo cual, teoricamente, no deberıa ser muy relevantedebido a que la estructura de mayor tamano, en ambos metodos, es la matriz de valores querepresenta la imagen, por lo que la diferencia entre ellos no debiera ser mucha. Sin embargo,se incluyo para verificar dicha intuicion y ver las diferencias a nivel de las constantes. Estaultima prueba permite ademas tener una comparacion en todos los niveles importantes anivel computacional.

1.2. Objetivo General

El objetivo general de esta memoria es paralelizar y comparar el metodo tradicional basa-do en la tecnica de Watershed y el metodo estocastico actualmente disenado en el laboratorioALGES.

1.3. Objetivos Especıficos

Para llevar a cabo el objetivo principal anteriormente descrito, es necesario lograr lossiguientes objetivos especıficos:

1. Analizar y evaluar el comportamiento secuencial del metodo basado en Watershed y elmetodo estocastico.

2. Implementar y mejorar el rendimiento de los metodos por medio de procesamiento enparalelo utilizando multiproceso.

3. Mejorar el preprocesamiento a las imagenes.

4. Realizar comparaciones y analisis en cuanto a calidad de la respuesta, tiempo de eje-cucion y memoria utilizada.

1.4. Metodologıa

Dado que el trabajo consistio en realizar una comparacion entre dos metodos, no secreo una aplicacion como tal, pues quedaba fuera del alcance de esta memoria. Para larealizacion de las pruebas se creo una aplicacion que interactua directamente con la librerıaque se extendio en este trabajo, por lo tanto, su estructura es equivalente a la de la librerıa.

La librerıa consta de dos modulos. En el primer modulo se agrupo los algoritmos para elpreprocesamiento y aquellos utilizados por el metodo tradicional. El segundo modulo incluye

4

las operaciones que componen el metodo estocastico. Estos modulos fueron desarrollados enPython utilizando la librerıa de calculo numerico Numpy y la librerıa cientıfica Scipy. Ademas,se incluyo algunas piezas de codigo C, las cuales resuelven problemas que en Python requierenmucho tiempo. Para incluir el codigo C en Python se utilizo la API que este ultimo poseepara estos efectos.

Las operaciones que se utilizan para el preprocesamiento y para el metodo clasico fueronimplementadas como funciones. Estas se encuentran se encuentran totalmente desacopladas,pues son operaciones bastante utiles y estandar para el analisis de imagenes. El metodoestocastico por su lado fue desarrollado en base a clases, debido a que en el transcurso deltrabajo surgieron varias alternativas para realizar las diferentes tareas. Esta multiplicidad dealternativas fue gestionada por medio de los patrones Strategy y Template Method.

La implementacion de los algoritmos fue hecha en base a los resultados esperados. Lametodologıa fue bastante parecida a lo que es Test Driven Developement, sin embargo, losresultados esperados no son exactos, sino que corresponden a que los resultados tengan ciertascaracterısticas, como por ejemplo que las burbujas esten rellenas, para lo cual la verificaciondebe ser visual. Como los resultados obtenidos no son exactos, no se puede escribir un testque cumpla o no. Lo que se hizo fue que los tests mostraran el resultado, ya sea por mediode imagenes, graficos o estadısticos, para, posteriormente realizar una verificacion visual.

Los experimentos para realizar la comparacion fueron disenados una vez terminada laimplementacion de ambos metodos. Para esta tarea se debio ser cuidadoso con la validez enterminos estadısticos que debe cumplir el experimento. Ademas de estos se diseno experi-mentos para comprobar intuiciones producto de la comprension acabada de los algoritmos.

1.5. Contenido de la Memoria

En el Capıtulo 2 se presentan los antecedentes acerca de los terminos empleados y lastecnicas utilizadas durante el presente trabajo. Esta descripcion se hace desde un punto devista mas bien teorico. En los Capıtulos 3, 4 y 5 se detalla como se realizo cada parte dela memoria, si es necesario explicar la implementacion de alguna de las tecnicas comentadasanteriormente, se hace en este capıtulo. En el Capıtulo 6 se muestran los resultados obtenidosproducto de la comparacion realizada. En este capıtulo se incluyen graficos para los exper-imentos efectuados y tablas cuando es necesario complementar el grafico correspondiente.El resto de las tablas con los datos utilizados en los graficos se incluyen en los anexos. Fi-nalmente, en el Capıtulo 7 se presenta las conclusiones, basadas en el analisis hecho a losresultados obtenidos, intentando buscar comportamientos caracterısticos en ciertos escenar-ios y tratando de comprender el por que de dichas particularidades y las consecuencias deestas.

5

Capıtulo 2

Antecedentes

En este capıtulo se exponen distintas tecnicas, algoritmos y definiciones estudiadas du-rante la memoria, los cuales permiten una mejor comprension del trabajo realizado. La may-orıa de las tecnicas y algoritmos fueron implementados, sin embargo, los que no lo fueron,sirvieron como base para desarrollar soluciones similares o fueron el primer acercamiento ala solucion, siendo posteriormente cambiados.

2.1. Procesamiento y Analisis de Imagenes y Senales

2.1.1. Manipulacion Curvas de Colores

La manipulacion de las curvas de colores es un herramienta ampliamente utilizada en elarea de procesamiento de imagenes[6, 8]. Esta tecnica consiste en aplicar una transforma-cion del tipo f : [0, 1] → [0, 1] a los valores de los pıxeles. Existen varias transformacionesconocidas- las cuales vienen incluidas en la mayorıa de los software disponibles- tales comoinvertir los colores, aumentar o disminuir el brillo y/o contraste, realzar colores (ver Figura2.1), entre otros. Estas transformaciones suelen necesitar cierta informacion adicional acercade la imagen sobre la cual se aplicara. Para ello, se utilizan los llamados histogramas de col-ores, los cuales muestran, para cada canal, la cantidad de pıxeles en cada uno de los nivelesde intensidad (ver Figura 2.2). Estos histogramas pueden tambien utilizarse para obtenerotras caracterısticas de la imagen, como el valor y la luminosidad. Los histogramas de col-ores aportan informacion estadıstica importante sobre la imagen, la cual permite construiruna transformacion que maximice el efecto esperado o bien, se amolde a las necesidadesparticulares en un contexto dado.

6

(a) Imagen original (b) Histograma de la imagen original y fun-cion de transformacion

(c) Imagen transformada (d) Histograma de la imagen transformada

Figura 2.1: Ejemplo de transformacion sobre canal azul

(a) Imagen (b) Histograma

Figura 2.2: Ejemplo de Histograma

2.1.2. Cuantizacion

La cuantizacion es una herramienta cuyo objetivo es reducir la cantidad de colores en unaimagen. En el proceso de cuantizacion la imagen pierde calidad, sin embargo, se pretende queesta perdida en calidad no afecte la semantica de la imagen, es decir, si la imagen originalmuestra un tigre, al cuantizar aun se pueda distinguir dicho tigre (Ver Figura 2.3). Para

7

conseguir la cuantizacion se debe solucionar un problema de clasificacion, el cual se resuelve,generalmente, utilizando tecnicas de clusterizacion para obtener clases de equivalencia yluego reemplazar los pıxeles en una clase por su representante. La calidad de la cuantizacionobtenida, como es de esperarse, depende de la imagen y de la cantidad de colores que sedesea obtener, sin embargo, el algoritmo de clasificacion es tambien un factor, debido a quela clasificacion es un problema cuya respuesta no es unica, por lo tanto dos metodos distintosno necesariamente entregan el mismo resultado, lo cual afecta el resultado de la cuantizacion.

(a) Imagen original, 52673colores

(b) Imagen cuantizada, 27colores

Figura 2.3: Ejemplo de cuantizacion de colores

2.1.3. Operaciones Morfologicas

La morfologıa matematica es un area cuyo objetivo es el reconocimiento de ciertas carac-terısticas estructurales de las formas que aparecen en una imagen y por medio de las cualesse pueden describir dichos objetos. Estas caracterısticas permiten producir no tan solo unaimagen nueva, sino tambien obtener atributos sobre la imagen, lo cual permite extraer ciertainformacion sobre lo que ella contiene. La morfologıa matematica esta basada en la teorıade conjuntos. Estos conjuntos representan los objetos que aparecen en la imagen, de estamanera una imagen binaria es un conjunto de puntos {(x, y) ∈ Z2 | I(x, y) = 1} asumiendoque los puntos pertenecientes a un objeto tienen valor 1. Es necesario hacer dos definicionesadicionales. La primera es la reflexion A = {x |x = −a ∀a ∈ A} que, como su nombreindica, corresponde a una reflexion respecto al origen. La segunda es la traslacion de unconjunto A por un vector z = (z1, z2) la cual se define como (A)z = {x |x = a+ z ∀a ∈ A}.Existe una gran cantidad de operaciones morfologicas, la mayorıa de ellas basadas en dosoperaciones basicas: Dilatacion y Erosion. El resto de las operaciones, en general, se reducea una combinacion de estas operaciones basicas y algebra de conjuntos como interseccion,union, diferencia y complemento.

Dilatacion

Sean A y B dos conjuntos en Z2. Se define dilatacion de A por B de la siguiente manera:

A⊕B = {z | (B)z ∩ A 6= ∅}

8

Para entender esta operacion se puede considerar el elemento estructural B como el pincelde un software de dibujo. El nuevo conjunto son todos los puntos que pueden ser pintadospor el pincel, restringiendo el origen del pincel a estar dentro del conjunto A. Un ejemplo sepuede ver en la Figura 2.4

(a) Conjunto A (gris oscuro) y patron B (grisclaro, en rojo el origen del patron)

(b) A⊕B

Figura 2.4: Ejemplo de dilatacion

Erosion

Sean A y B dos conjuntos en Z2. Se define erosion de A por B de la siguiente manera:

AB = {z | (B)z ⊆ A}

Siguiendo con el ejemplo del pincel, para esta operacion, se debe considerar que solo el origendel pincel pinta. El conjunto AB corresponde a todos los puntos que pueden ser pintadoscon origen del pincel, con la restriccion de que el pincel debe estar dentro del conjunto A talcomo se muestra en la Figura 2.5.


(b) AB

Figura 2.5: Ejemplo de erosion

9

Opening

Sean A y B dos conjuntos en Z2. Se define opening de A por B de la siguiente manera:

A ◦B = (AB)⊕B

Intuitivamente y utilizando la analogıa del pincel, mencionada en las operaciones de dilataciony erosion, el conjunto generado por opening corresponde a todos los puntos que pueden serpintados por el pincel sin que este salga del conjunto A. En la Figura 2.6 se puede ver unejemplo de lo anterior.


(b) A ◦B

Figura 2.6: Ejemplo de opening

Closing

Sean A y B dos conjuntos en Z2. Se define closing de A por B de la siguiente manera:

A •B = (A⊕B)B

Para entender esta operacion se utiliza nuevamente la analogıa del pincel. Esta operacionequivale a tomar el complemento del resultado de aplicar opening sobre el complemento delconjunto A, es decir, el nuevo conjunto son todos los puntos que no pueden ser pintados porel pincel, restringiendo el pincel a no entrar al conjunto A. La Figura 2.7 muestra un ejemplode lo anterior.

Deteccion de bordes

Para detectar bordes se utiliza erosion y la diferencia entre conjuntos de la siguientemanera

β(A) = A− (AB)

10


(b) A •B

Figura 2.7: Ejemplo de closing

donde A es el conjunto original y B es el elemento estructural. Esta manera de obtener elborde de los objetos permite extraer fronteras de distinto tipo, segun la forma del elementoestructural utilizado (ver Figura 2.8). Los elementos mas utilizados son los de la Figura 2.9.

(a) Conjunto A (gris oscuro) y pa-tronB (gris claro, en rojo el origendel patron)

(b) AB (c) β(A) = A− (AB)

Figura 2.8: Ejemplo de deteccion de bordes

(a) Vecindad 4-conectada (N4) (b) Vecindad 8-conectada (N8)

Figura 2.9: Vecindades comunmente utilizadas para detectar bordes

2.1.4. Mapa de Distancias

La transformada de distancia, o mapa de distancias, es un operador con el cual se obtiene,para cada pıxel, la distancia mınima a cierta zona de interes en la imagen. Este operador

11

permite la utilizacion de cualquier distancia, siendo la distancia euclidiana la mas utilizadapor su aplicabilidad a problemas donde interviene la nocion humana de distancia. La formulageneral es

DT (p) = mınq∈I

(d(p, q)|q ∈ C)

donde I corresponde a la imagen, C corresponde a la region de interes en la imagen y d(·, ·)corresponde a la distancia elegida.

(a) Imagen original (b) Usando d1(p, q) =∑‖pi − qi‖

(c) Usando d2(p, q) =√∑

(pi − qi)2 (d) Usando d∞(p, q) = max{‖pi − qi‖}

Figura 2.10: Ejemplo de Mapas de Distancias con respecto al fondo de la imagen, conp = (p1, . . . , pn) y q = (q1, . . . , qn).

2.1.5. Watershed

El algoritmo Watershed es una herramienta que permite separar objetos que aparecenjuntos en una imagen[1]. La imagen resultante de este algoritmo es, basicamente, la imagenoriginal con las lıneas que separan los objetos que aparecen pegados. Estas lıneas, en lamayoria de los caso, no coinciden con el contorno de ninguna de las figuras que se separa,pues el algoritmo no considera las formas que puedan tener los objetos de la imagen.

Para utilizar el algoritmo se necesita una imagen en escala de grises, la cual se interpretacomo un mapa topografico. Al interpretar la imagen como un relieve se puede simular unainundacion de este, comenzando en el mınimo global, pasando por los mınimos locales, hastacubrir toda la imagen. El algoritmo asigna a cada uno de los mınimos locales una etiqueta,de manera que cada uno de estos mınimos se interprete como una fuente de agua diferente(Figura 2.11(b)). Cuando en un punto se juntan aguas provenientes de dos fuentes distintasse debe construir una pared que las separe (Figura 2.11(c)), dichas paredes se convierten,posteriormente, en las lineas que separan los objetos.

Un problema con esta tecnica, como ya se dijo, es que distorsiona los bordes reales delos objetos, pues no toma en cuenta esa caracterıstica de la figura. Existe ademas otro in-

12

(a) Mapa de altura, imagen original (b) Mapa de altura, cada mınimo es unafuente representada por un color

(c) Mapa de altura, se crea una pared queimpide que se junten las fuentes

Figura 2.11: Ejemplo de etapas en la inundacion simulada por Watershed

conveniente en este algoritmo: este no separa figuras cuando la union de ellas no presentauna concavidad, es mas, no separa si la concavidad no induce varios mınimos. Es difıcil en-contrar casos en que la union de dos figuras no posea concavidades, exceptuando el caso deuna superposicion total. Sin embargo, es muy recurrente encontrar casos en que, a pesar deque exista alguna concavidad, la figura no tenga multiples mınimos. Analogamente, se tieneel inconveniente de las figuras que por naturaleza son concavas, las cuales pueden presentarmas de un mınimo y, por lo tanto, ser cortada en varias partes.

2.1.6. Filtros

Un filtro es una operacion definida basicamente por un kernel, el cual se convolucionacon una senal para obtener una nueva con ciertas caracterısticas. Sea una senal S(x) en eldominio espacial de largo l, luego un kernel se define como un vector K(x) de largo n = 2d+1para d > 0 y n� l. La convolucion entre S(x) y K(x) queda definida como

S ′(x) = S(x) ? K(x) =n−1∑i=0

S(x− (d− i))K(i)

La convolucion entre una senal S(x) y un kernel K(x) tambien se puede obtener por mediode la convolucion aplicada en el espacio de frecuencias, utilizando el teorema de convolucion,

13

es decirFS ′(t) = FS(t) · FK(t)

donde F es la transformada de Fourier

Ff(t) =

∫ ∞−∞

f(x)e−2πitxdx

En el caso de valores discretos se utiliza la transformada discreta de Fourier la cual esta defini-da como

Fxk =N∑n=1

xne−2πik n−1

N 0 < k ≤ N

Todo lo anterior es extensible a 2D para ser utilizado en imagenes. Las llamadas mediasmoviles o filtros de difusion son un conjunto de filtros los cuales son utilizados para eliminarel ruido de las mediciones, dentro de este conjunto destacan los filtros gausianos.

2.1.7. Espacios de Escala

Como ya se menciono, los filtros, especıficamente los de difusion o medias moviles, cumplenla funcion de eliminar parte del ruido de una senal o imagen. Sin embargo, no es posible de-terminar a priori que parametros, y en consecuencia que nivel de escala, se necesita parapoder extraer la informacion que se esta buscando. En estas condiciones es donde los espa-cios de escala son sumamente utiles. Estos consisten en una representacion de una imagen enmultiples niveles, cada uno con un grado mayor de difusion. En general, un espacio de escalase define como

Ik(x, y) =

{I(x, y) k = 0Fk(I(x, y)) k > 0

donde Fk para k > 0 es un banco de filtros, el cual debe cumplir con la recursividad

Fi+j(I(x, y)) = Fi(Fj(I(x, y))) ∀i, j > 0

Como se explica en [3], los espacios de escala se basan en ecuaciones provenientes de losprocesos de difusion fısica, como la ecuacion de difusion

∂I(x, y, t)

∂t= ∇ · (D∇I(x, y, t))

I(x, y, 0) = f(x, y)

donde D es una matriz definida positiva y simetrica llamada tensor de difusion.

Para el caso de la ecuacion del calor, el tensor de difusion es un ponderador g llamadodifusividad termica, de esta manera el sistema anterior se transforma en

∂I(x, y, t)

∂t= g∇2I(x, y, t))

14

I(x, y, 0) = I(x, y)

la cual tiene una solucion conocida. Dicha solucion genera el siguiente espacio de escala

It(x, y) =

{I(x, y) t = 0K√2gt(x, y) ? I(x, y) t > 0

donde

Kσ(x, y) =1

2πσ2e−

x2+y2

2σ2

Este espacio de escala, el cual utiliza filtros de difusion lineal, es el mas estudiado y utilizadopor ser el mas simple y ser suficientemente bueno en la mayorıa de los casos. Existen tambienotros espacios mas complejos los cuales se detallan en la literatura [3].

2.2. Modelo Booleano Estacionario

Sea un proceso puntual de Poisson {xi | i ∈ N} en R2 con una intensidad θ ∈ R+ y{Ai | i ∈ N} una coleccion de subconjuntos de R2 compactos, independientes y distribuidoscomo un objeto de referencia A, llamado grano primario o grano tıpico. El conjunto booleanose define como

Ξ =⋃i

xi + Ai

el cual corresponde a la union de cada objeto Ai ubicado en la posicion xi correspondiente.El conjunto se puede caracterizar por su avoiding functional el cual esta definido para todoK subconjunto de R2 de la siguiente manera

T (K) = P(Ξ ∩K = ∅)

Si se consideran dos puntos a una distancia h como conjunto K, tal como aparece en [4]se tendra que

Ψ(h) = ln(T (K)) = −2θE(|A|) + θκA(h)

donde h es la distancia que separa los puntos y κA(h) es el covariograma geometrico del granoprimario A. Este valor κA(h) es equivalente a la superficie que se traslapa A consigo mismotrasladado en una distancia h. El covariograma geometrico κA(h) es de gran importancia,pues como se muestra en [4], con este valor se puede obtener

1− F (a) =2

π

∫ ∞a

κ′′A(h)dh√h2 − a2

ecuacion que permite calcular el valor de F (a) que, para el caso de interes de este estudio,corresponde a la distribucion acumulada de los objetos circulares por diametro. El covari-ograma geometrico tambien permite obtener los momentos de la distribucion por medio dela siguiente formula

µk =Γ(k

2)

√πΓ(k+1

2)

∫ ∞0

hk−1κ′′A(h)dh

15

El covariograma geometrico del grano primario es difıcil de obtener, sin embargo, ambasformulas utilizan la segunda derivada de este. Para obtener dicha segunda derivada se utilizaΨ(h), expresion que contiene κA(h), y cuya segunda derivada es Ψ′′(h) = θ · κ′′A(h). Ergo,como θ es una constante, las expresiones utilizadas para obtener F (a) y µk se ponderan porθ y se puede utilizar Ψ′′(h) en lugar de κ′′A(h). Realizar este cambio genera la necesidad deobtener θ, para ası poder despejar los valores deseados.

2.3. Doubling Search

Doubling search es un algoritmo utilizado para resolver el problema llamado unboundedsearch. Este problema consiste en buscar un elemento en una estructura ordenada, pero queno se conoce su largo. Al no conocer el largo de la estructura no se puede realizar unabusqueda binaria, la cual es optima. Sin embargo, este algoritmo lo que hace es encontrar unintervalo donde esta pueda ser utilizada.

El algoritmo se compone de dos partes, la primera es encontrar un intervalo donde poderaplicar la busqueda binaria; y la segunda, aplicarla. La busqueda del intervalo se hace re-visando las posiciones que son potencias de un numero k. En la i-esima iteracion se revisa laposicion ki−1, donde se tiene 3 opciones. El mejor caso es que en esa posicion este el elementobuscado, luego, se retorna el elemento y termina la ejecucion. El segundo escenario es cuandoel elemento en dicha posicion es menor que el que se esta buscando, en cuyo caso se debebuscar a la derecha del elemento, por lo tanto aun no se puede aplicar la busqueda binariay se debe seguir iterando. El caso interesante es cuando el elemento revisado es mayor queel que se esta buscando, pues en este caso el elemento de interes esta a la izquierda. Estoultimo significa que el elemento esta entre la potencia anterior y la que se esta revisando, esdecir, entre las posiciones ki−2 y ki−1, ergo se puede realizar una busqueda binaria en dichointervalo.

Figura 2.12: Ejemplo de doubling search

En la Figura 2.12 se muestra un ejemplo de como funciona doubling search. Las flechasverdes corresponden a la busqueda utilizando potencias de 2, las flechas azules correspondena la busqueda binaria.

16

Capıtulo 3

Procesamiento previo de las imagenes

El procesamiento previo que se debe hacer a las imagenes fue, en su mayorıa, un trabajoque se hizo con anterioridad, sin embargo, se debio volver a trabajar en ello para permitirpintar sin eliminar las burbujas que estan en el borde de la imagen. Sin considerar la correcionde algunos errores en la implementacion, el resto de las funcionalidades las fueron realizadosfuera de la memoria, sin embargo, son parte importante del futuro del proyecto, cuando estetrabajo se extienda para crear un prototipo.

En este capıtulo se detalla el pipeline por el que la imagen debe pasar. El proceso consisteen una primera etapa de eliminacion de ruido, proveniente de distorsiones causada por loslentes del dispositivo de captura, mediante transformaciones sobre las curvas de colores.Posteriormente, se reduce la cantidad de colores por medio de cuantizacion para, finalmente,obtener una imagen binaria a partir de la imagen transformada.

Por efectos de la luz, las burbujas suelen aparecer solo representadas por el borde de estas,por lo cual se deben rellenar las burbujas, pues ambos metodos consideran las burbujas comodiscos rellenos. En la Figura 3.1 se puede ver el resultado de la binarizacion, donde se puedeobservar que los cırculos no estan rellenos.

(a) Imagen original (b) Resultado dela binarizacion, loscırculos no estanrellenos

(c) Resultado espera-do

Figura 3.1: Ejemplo burbujas no rellenas tras la binarizacion

17

El siguiente paso consiste en una segunda fase de eliminacion de ruido, por medio delcual se pretende eliminar rugosidades en los bordes de las burbujas y borrar burbujas muypequenas que puedan ser confundidas con otras partıculas, imperfecciones en la pared trans-parente del equipo utilizado para medir tamanos de burbuja, entre otras situaciones.

Finalmente, existe un paso, el cual solo se aplica para imagenes que seran procesadas conel metodo clasico, que consiste en la eliminacion de las burbujas que aparecen en los bordesde la imagen, las cuales suelen estar cortadas e inducen un sesgo hacia las burbujas pequenas.

3.1. Eliminacion de ruido del dispositivo de captura

Un fenomeno que da cuenta del ruido generado por el dispositivo de captura es quese pueden reconocer zonas, donde mientras mas al centro de la imagen se observa mayorintensidad de los colores, y menos intensidad hacia los extremos. Este efecto se observaprincipalmente en la direccion del lado mas largo de la imagen. Estas zonas se pueden observaral momento de reducir el numero de colores, pues cada zona tiene un color distinto (ver Figura3.2(b)), sin embargo, en la imagen original se puede ver el mismo efecto en su version continua.La diferencia en los colores no es tan notoria, pues el aumento gradual de la intensidad enganaal ojo humano (ver Figura 3.2(a)), mas al analizar dos zonas, por medio de un histogramade colores, se puede ver que tienen peaks en intensidades distintas (ver Figura 3.2(c)), lo cualevidencia el efecto descrito.

El efecto anteriormente descrito se produce principalmente por dos razones. La primerade ellas tiene relacion con la curvatura del lente, que genera una distorsion sobre los ex-tremos de la imagen. La segunda razon es la luz, la cual ilumina con mayor intensidad ciertazona, generalmente al centro de la imagen. Sin embargo este efecto aporta bastante poco encomparacion con el problema del lente. El problema del lente es difıcilmente corregible, noobstante es posible aminorar los efectos considerablemente.

Eliminar el ruido producido con el dispositivo de captura, utilizando herramientas cono-cidas de procesamiento de imagenes, es en general bastante facil. En la imagen existen dosrangos casi disjuntos de los cuales uno representa las burbujas y el otro rango representael fondo de la imagen. El rango que corresponde al fondo de la imagen puede ser bastanteamplio, por lo que, al reducir el numero de colores, puede que este intervalo se separe envarios colores, lo que puede generar problemas al segmentar las burbujas.

La solucion a este problema consiste en disminuir lo mas posible el tamano de ese rango,para lo cual se utilizan transformaciones sobre los pıxeles de la imagen, es decir, se aplicauna funcion f : [0, 1] → [0, 1] a cada pıxel. Esta funcion tiene como objetivo agrupar lospıxeles del fondo en un intervalo mas pequeno, de manera de obtener solo un color para elfondo de la imagen al cuantizarla. La forma de la funcion es la que determina que tipo detransformacion se obtiene. Para obtener un resultado como el esperado (Ver Figura 3.3(b)),se debe utilizar una tranformacion similar a la que se muestra en la Figura 3.3(a).

18

(a) Imagen original, con dos zonas selec-cionadas

(b) Imagen cuantizada

(c) Histograma para las zonas selec-cionadas en la imagen original

Figura 3.2: Ejemplo de ruido producidos por el dispositivo de captura

En un principio, la transformacion se implemento utilizando splines cubicas, para lascuales solo se utilizo Numpy para el manejo de matrices, pues en ese momento se pretendıausar solo dicha librerıa en todos los desarrollos del laboratorio. Para implementar las splinesse necesita una cierto numero n de puntos, los cuales definen n−1 intervalos y, para cada unode ellos, un polinomio de grado tres. Estos polinomios deben ser continuos, tanto el polinomiocomo su primera y segunda derivada. Con estas condiciones se puede calcular los coeficentespara cada uno de los polinomios.

Sin embargo, debido a la necesidad de herramientas para calculo cientıfico, en el labora-torio se opto por utilizar Scipy si era necesario. Frente a esta situacion se comparo la nuevaalternativa contra el desarrollo hecho anteriormente, resultando, de manera sorpresiva, unpoco mas rapida la implementacion inicial que utilizar la spline cubica de Scipy.

El uso de splines cubicas, por sobre otras alternativas, se debe a la capacidad de estasde interpolar manteniendo una continuidad hasta la segunda derivada de manera simple.Ademas permite que las transformaciones sean modificables de manera intuitiva por mediode la incorporacion de nuevos puntos o la modificacion de los ya existentes. El desarrollo deestas splines se hizo pensando en splines cubicas naturales, donde la segunda derivada en losextremos de la curva es 0, y splines cubicas sujetas, donde se impone valores a la derivadaen los extremos de la curva. En el Algoritmo 3.1 se puede ver el pseudocodigo del calculo delas splines cubicas naturales.

19

Algoritmo 3.1 Calculo de coeficientes de spline cubica natural

spline(controlPoints)beginf ← |controlPoints|h← zeros(f − 1)d← zeros(f − 1)u← zeros(f)for i = 0..(f − 1) doh[i]← controlPoints[i+ 1]x − controPoints[i]xd[i]← (controlPoints[i+ 1]y − controPoints[i]y)/h[i]if i > 0 thenu[i]← 3 ∗ (d[i]− d[i− 1])

end ifend foru[0]← 0u[f − 1]← 0A = zeros(f, f)for i = 1..(f − 1) doA[i, i]← 2 ∗ (h[i− 1] + h[i])A[i, i+ 1]← h[i]A[i+ 1, i]← h[i]

end forA[0, 0]← 1A[f − 1, f − 1]← 1A[f − 1, f − 2]← 0A[1, 0]← h[0]X ← A−1ucoef ← zeros(f − 1, 4)for i = 0..(f − 1) do

// polinomios de la forma coef [i, 0]x3 + coef [i, 1]x2 + coef [i, 2]x+ coef [i, 3] = 0coef [i, 0]← (X[i+ 1]−X[i])/(3 ∗ h[i])coef [i, 1]← X[i]coef [i, 2]← d[i]− (h[i] ∗ (2 ∗m[i] +m[i+ 1]))/3coef [i, 3]← controlPoints[i]y

end forreturn coef

end

20

(a) Transformacion aplicada sobre la im-agen original

(b) Imagen transformada, con dos zonasseleccionadas

(c) Imagen cuantizada (d) Histograma para las zonas selec-cionadas en la imagen transformada

Figura 3.3: Ejemplo de imagen transformada (Eliminacion del ruido del dispositivo de cap-tura)

3.2. Cuantizacion y Binarizacion

La cuantizacion, dentro de la secuencia de operaciones que se debe llevar a cabo paraobtener una imagen binaria, no es un paso fundamental, puesto que la imagen obtenida porel paso anterior es una imagen en escala de grises y, como ya se menciono, esta imagen fuemodificada para que el fondo sea mas uniforme. Esto quiere decir que el color del fondo esaltamente identificable, sin embargo, existe alrededor de las burbujas una zona en la que elcolor caracterıstico de estas se degrada hasta tomar el color del fondo. Este fenomeno impideencontrar un lımite claro que permita diferenciar el fondo de la imagen de las burbujas.

Esta situacion requiere una inspeccion visual para determinar el mejor umbral que separeuna burbuja del fondo. La imagen tiene un degradado que hace que sea difıcil identificarde manera rapida el umbral mencionado anteriormente (ver Figura 3.4(a)). Al aplicar unacuantizacion sobre la imagen, imponiendo una cantidad pequena de colores, se elimina eldegradado que dificulta la deteccion del umbral buscado. En la Figura 3.4(b) se puede ver,la cuantizacion a 3 colores aplicada sobre la imagen. Una vez realizada la cuantizacion existesolo dos opciones: que la franja color gris oscuro, sea parte o no de la burbuja.

El algoritmo de cuantizacion ya estaba implementado en la librerıa que se extendio. El

21

(a) Imagen orig-inal

(b) imagencuantizada

Figura 3.4: Ejemplo de la cuantizacion sobre el borde de una burbuja

algoritmo utilizado se denomina NeuQuant y opera con post-clustering, es decir, primeroencuentra los colores a utilizar y luego se revisa que color toma cada pıxel. El nombre deeste algoritmo proviene del metodo por el cual se eligen los colores a utilizar, pues se usa unmapa de Kohonen, el cual es una red neuronal auto-organizada. El detalle de este algoritmose muestra en [2].

Una vez realizada la cuantizacion, se elige un umbral con el cual se separa el fondo y lasburbujas. Es comun que, al final de este proceso, las burbujas no esten rellenas.

3.3. Rellenado de burbujas y eliminacion de ruido

Para realizar el rellenado de las burbujas existen diversas tecnicas, las cuales tienen ven-tajas segun las condiciones del problema. Todas las tecnicas estudiadas estan basadas en lamorfologıa matematica o conceptos provenientes de esta disciplina.

La primera opcion fue el rellenado de una superficie mediante propagacion. Este algorit-mo utiliza la misma idea detras de la herramienta de relleno de los software de edicion deimagenes. El algoritmo rellena con el color seleccionado un area seleccionada. Esta ultimaesta definida por la conectividad entre los pıxeles.

El algoritmo implementado recibe 4 parametros. El primero de ellos es el punto P , desdedonde comienza la recursion que se explica mas adelante. Los dos siguientes parametroscorresponden al color inicial Ci y al color final Cf . El ultimo parametro es la matriz N quedefine la vecindad para un punto. Este ultimo parametro admite dos valores, la vecindad4-conectada y 8-conectada, las cuales se pueden ver en la Figura 2.9 de los Antecedentes.

El algoritmo comienza en el punto P , y se propaga utilizando la nocion de vecindad quedefine la matriz N . El algoritmo verifica que el color en el pıxel seleccionado sea Ci, en cuyocaso cambia su valor a Cf y recursivamente revisa a los vecinos de dicho pıxel. En caso deque el pıxel no sea de color Ci la recursion termina. Luego, este algoritmo comienza pintandoel punto P de color Cf y procede de igual manera con sus vecinos. Cuando el color de unpıxel no es Ci es porque este no esta dentro de la zona que se desea pintar, por lo tanto no sedebe pintar ni revisar sus vecinos. En el Algoritmo 3.2 se muestra como opera el algoritmo

22

anterior.

Algoritmo 3.2 Pintado de un area seleccionada

paint(P,Ci, Cf , N)begin

if color(P ) == Ci thencolor(P )← Cfvecinos← obtenerV ecinos(P,N)for V ∈ vecinos dopaint(V,Ci, Cf , N)

end forend if

end

Para optimizar la ejecucion se puede aplicar la recursividad solo sobre los vecinos cuyocolor es Ci y ası no sobrecargar el stack de ejecucion con llamadas recursivas innecesarias.La implementacion final fue iterativa, utilizando una cola para almacenar los vecinos. Parautilizar esta tecnica se debe conocer el punto P , el cual debe pertenecer a la zona que sequiere rellenar, por lo tanto, es necesario conocer a lo menos un punto del centro de lasburbujas. Esta tarea no es difıcil, sin embargo, es un costo mas que no esta presente en otrosmetodos.

(a) Imagen original (b) Punto de partidade la recursion

(c) Imagen interme-dia

(d) Imagen final

Figura 3.5: Ejemplo del primer metodo de rellenado de burbujas

La segunda opcion estudiada utiliza erosion y dilatacion para rellenar las burbujas. Elmetodo consiste en dilatar los objetos un numero fijo de veces y luego aplicar erosion lamisma cantidad de veces. El numero de veces que se debe aplicar es un problema de estasolucion y se discutira mas adelante. La idea detras del procedimiento explicado es lograr quepor medio de la dilatacion los espacios dentro de la burbuja se llenen, y luego, aplicando laerosion, volver el objeto a su tamano original. Si la cantidad de veces que se aplica la dilat-acion y, posteriormente, la erosion, es suficiente, los huecos en las burbujas seran rellenadoscompletamente y la evidencia de aquel agujero desaparecera. Ası, al no quedar rastro delhueco, la erosion no podra reconstruirlo, quedando la burbuja rellena. (ver Figura 3.6).

La diferencia entre esta tecnica y closing es que para este ultimo el elemento estructurales muy relevante, a diferencia del primero donde lo relevante es la cantidad de repeticiones.Closing, como se explico en los antecedentes, se puede entender como deslizar un elementoestructural por el fondo de la imagen, luego si el espacio dentro de la burbuja es suficien-temente grande el elemento estructural puede deslizarse por el interior de la burbuja y, en

23

consecuencia, este espacio no se rellenara. Ademas closing tiene un inconveniente adicionalque es unir objetos que estan separados por un espacio por donde no se puede deslizar elelemento estructural. Estas diferencias hacen que closing no sea alternativa, a diferencia delmetodo explicado anteriormente. El rellenado vıa dilatacion y erosion es bastante simple, sinembargo, presenta varios inconvenientes. El primero de ellos es que la cantidad de dilata-ciones, y posteriores erosiones, no es conocida a priori, por lo que encontrar dicho numero esun trabajo adicional, ademas este valor depende de cada burbuja, lo que significa, revisarlastodas. Otro inconveniente, el mas relevante por afectar la calidad de la respuesta, es que alaplicar esta tecnica las formas en la imagen se distorsionan, tomando la forma del elementoestructural, lo cual es altamente perjudicial para el analisis posterior.

La implementacion de dilatacion y erosion, son algorıtmicamente similares a aplicar unfiltro sobre una imagen, donde el elemento estructural es el equivalente al kernel del filtro.De esta similitud se puede extraer dos cosas, la primera es que la complejidad del algoritmoaumenta con el tamano de la imagen y el tamano del elemento estructural. La segunda,identificada a partir de la experimentacion, es que aplicar un filtro en Python es poco eficiente,al igual que muchas operaciones iterativas en este lenguaje. La API de C para Python esbastante poderosa, permitiendo utilizar clases desarrolladas ıntegramente en C dentro dePython, sin embargo, el uso que se le dio fue mas bien basico. La solucion a este problemafue la implementacion de funciones en C, las cuales efectuan el recorrido sobre la imagenrealizando la operacion morfologica correspondiente.

(a) Imagen original (b) Despues de la di-latacion

(c) Imagen final, de-spues de la erosion

Figura 3.6: Ejemplo del segundo metodo de rellenado de burbujas

La tercera opcion estudiada, la cual finalmente se utilizo, es una que emplea la primeraopcion detallada y operaciones logicas. Esta tecnica consiste en pintar el fondo de la imagendel color de las burbujas, pero solo el que esta fuera de las burbujas, no los agujeros en ellas.Como se esta trabajando con imagenes binarias, el fondo inicialmente con valor 0, se cambiapor valor 1, al igual que las burbujas. Como los espacios dentro de las burbujas no estanconectados con el fondo, no se cambian. Posteriormente, se toma la negacion de lo obtenido,es decir, el fondo y las burbujas, actualmente con valor 1, se cambian a 0 y los espaciosinteriores de las burbujas se cambian a 1, pues estaban inicialmente en 0. Finalmente, setoma la disyuncion entre esta imagen y la original, de esta manera se tiene que el fondo de laimagen tendra valor 0, los bordes de la burbuja tendran valor 1 y los agujeros de las burbujastambien tendran valor 1 (ver Figura 3.7). A diferencia del primer metodo, esta manera depintar solo necesita un punto en el fondo, y no puntos en cada uno de los agujeros en lasburbujas.

24

(a) Imagen original (b) Imagen con fondopintado

(c) Negacion de (b) (d) Imagen final,disyuncion entre (a)y (c)

Figura 3.7: Ejemplo del tercer metodo de rellenado de burbujas

Para obtener el punto perteneciente al fondo existen dos formas, segun el metodo que seuse en el analisis posterior. En el caso del metodo clasico, el cual no considera las burbujasen los bordes, se eliminan dichas burbujas y luego se toma cualquier punto del borde pues,por construccion, pertenece al fondo de la imagen. Para eliminar las burbujas se recorre elborde buscando burbujas y se pintan del color del fondo. En el caso del metodo estocasticose busca en el borde un espacio entre dos burbujas distintas, luego se toma un punto en eseintervalo. Para encontrar un punto en el fondo es necesario conseguir, en los bordes de laimagen, un punto que este entre dos burbujas distintas o dos clusteres distintos. Dado que lasburbujas en los bordes pueden tener hoyos no se puede asumir que un punto del fondo es unoque esta entre dos extremos de burbujas, pues estos extremos pueden pertenecer a la mismaburbuja y, por ende, el punto pertenecer al interior de una y no al fondo. La solucion a esteproblema consistio en identificar previamente cada burbuja con un valor, luego cuando dosextremos de burbujas tengan distintos valores los puntos entre dichos extremos perteneceranal fondo (Ver Figura 3.8). Para encontrar las regiones conectadas, en este caso las burbujas,se recorrio la imagen en cualquier orden, pintando con un identificador nuevo cada zonaconectada.

(a) Punto naranjo indica punto malescogido como el fondo

(b) Punto verde indica punto bienescogido como el fondo

Figura 3.8: Ejemplo de error y solucion para encontrar fondo de la imagen

El ultimo paso de esta seccion corresponde a aplicar el operador opening sobre la imagencon las burbujas rellenas. El objetivo de esto es eliminar irregularidades en los bordes de lasburbujas, ademas permiten limitar el tamano mınimo de burbujas al tamano del elementoestructural.

25

Capıtulo 4

Procesamiento Clasico

Watershed es una tecnica que es ampliamente utilizada en la segmentacion de imagenes.Este metodo no trabaja sobre imagenes binarias, pues requiere para su funcionamiento unrango de valores numericos, para poder encontrar los mınimos locales que necesita. Estalimitante explicito la necesidad transformar la imagen binaria en una imagen en escala degrises. Dada la naturaleza del algoritmo, se utilizo la transformada de distancia, la cual generauna imagen con las distancias mınimas de cada punto de las burbujas al fondo.

El algoritmo se utiliza, generalmente, con supervision, es decir, con interaccion de unusuario, y por ende, no del todo automatico. La supervision tıpica para este algoritmo consisteen la asignacion de los identificadores a cada zona que constituira un nuevo objeto, en otraspalabras, se identifican los objetos y se deja al algoritmo definir las fronteras entre ellos.

La implementacion hecha sigue siendo supervisada, sin embargo, la supervision es bastantemenos fuerte. Las modificaciones hechas al algoritmo permiten que la identificacion de losobjetos sea automatica, mas el algoritmo requiere que el usuario ingrese dos parametros. Elprimero de ellos es el tamano mınimo de burbuja permitido, el que determina que cualquierobjeto de tamano menor sea eliminado, pues corresponde a ruido en la captura de la imageny no a una burbuja. El segundo parametro corresponde a la desviacion estandar (σ) para unfiltro de difusion gausiano. Estos parametros solo se ingresan una vez, al inicio del proceso.

La implementacion fue realizada antes comenzar con la memoria, sin embargo, se tuvoque corregir errores de implementacion que quedaron pendientes en el algoritmo Watershed,Tambien se tuvo que implementar la parte final, correspondiente al calculo de las metricas.En la busqueda de optimizar el algoritmo se cambio la estrategia para el calculo de la trans-formada de distancia, lo cual tambien corresponde a trabajo realizado durante la memoria.Todo el resto fue implementado fuera de ella.

El pipeline en esta seccion comienza con la imagen binarizada, con las burbujas rellenas.Posteriormente se aplica la transformada de distancia sobre la imagen, obteniendo una imagen

26

en 2,5D la cual sirve de entrada al algoritmo Watershed. Este ultimo separa las burbujas quese encuentran clusterizadas, para, posteriormente identificarlas y obtener la distribucion deburbujas por diametro.

4.1. Transformacion a escala de grises

Como se explico, Watershed trabaja sobre una imagen en escala de grises, utilizandolos mınimos locales para obtener la separacion. Dado el procesamiento previo que se hizo,la imagen debe ser transformada, nuevamente, a una en escala de grises. Si bien la imagenoriginalmente era en escala de grises, esta no era una imagen apropiada para aplicarle elalgoritmo. En primer lugar, la imagen original no se puede procesar sin manipulacion previaporque la intensidad del gris no obedece a cuan dentro de la burbuja esta el punto, sino quea un efecto de la luz, por lo que no necesariamente se obtendra una buena segmentacion. Elsegundo motivo es que las burbujas inicialmente se encuentran sin rellenar, lo cual impideaplicar el algoritmo en estas condiciones para obtener una separacion de clusteres de buenacalidad.

La transformacion a escala de grises debe tener la propiedad de reproducir de algunamanera la geometrıa de las burbujas. Suponiendo que el plano de la imagen corta todaslas burbujas en el ecuador, la transformacion debe intentar reproducir las semiesferas quequedan sobre el plano de la imagen. Esta suposicion es valida, pues es una proyeccion en2D de objetos en 3D. Por este motivo se utiliza la transformada de distancia, la cual noreproduce la curvatura real de las burbujas, sin embargo, preserva la condicion de que lospuntos mas al interior tienen intensidades mayores. En estricto rigor, esta transformada nogenera una imagen en escala de grises, sino mas bien un mapa en 2,5D, pues el color dependedel canal que se utilice. La diferencia entre un mapa en 2,5D y una imagen en escala degrises es el recorrido. Una imagen en escala de grises corresponde a una matriz donde cadacelda almacena un valor entero entre 0 y 255, a diferencia del mapa en 2,5D donde el valoralmacenado puede ser cualquier real.

La primera implementacion que se hizo fue basada en el algoritmo de fuerza bruta, pues enprincipio se querıa verificar que la transformada servıa para resolver el problema. El algoritmode fuerza bruta es facilmente extraıble de la definicion de la transformada de distancia: “ladistancia mınima de cada punto de una burbuja al fondo”. El algoritmo de fuerza brutaconsiste en tomar cada punto de las burbujas y calcular la distancia a cada uno de los puntosdel fondo y luego quedarse con el menor (Ver Figura 4.1(a)). Esta opcion es claramenteineficiente, sin embargo, puede mejorar bastante reduciendo el conjunto de pıxeles de fondo.La primera mejora que se aplico fue calcular la distancia desde los puntos pertenecientes alas burbujas, hacia los puntos del fondo que estan en contacto con estas (Ver Figura 4.1(b)),dado que los puntos que no estan en contacto con una burbuja son mayores que alguno de losque sı lo estan, por lo tanto, pueden ser descartados. La segunda mejora consistio en realizarel proceso por cada region conectada, de esta manera, si se esta procesando una burbujab solo seran candidatos a mınimo los pıxeles del fondo que estan en contacto con b (Ver

27

Figura 4.1(c)). Con estas mejoras se descarta todos los puntos que se sabe a priori que noson candidatos sin necesidad de calcular la distancia, lo cual es el mayor costo del algoritmo,luego lo unico restante es elegir la distancia mınima de entre los candidatos no descartados.

La diferencia entre estas variantes se puede observar a traves de su complejidad. El algo-ritmo de fuerza bruta es de orden O(nb ·nf ), donde nb es la cantidad de pıxeles pertenecientesa las burbujas y nf es la cantidad de pıxeles pertenecientes al fondo, pues para cada pıxel delas burbujas se calcula la distancia a todos los puntos del fondo. La variante que solo utilizalos pıxeles del fondo en contacto con las burbujas es de orden O(n

3/2b ), pues dado que se

trabaja con burbujas, por lo tanto cırculos, el perımetro pb = O(√nb), luego la complejidad

es la indicada anteriomente, pues para cada pıxel de las burbujas se debe calcular la distaciaa todos los puntos del perımetro. En el caso de la variante que utiliza cada burbuja conlos pıxeles que la rodean, la complejidad es similar a la anterior, mas aplicada para cadaburbuja, es decir nb

3/2i , donde nbi es la cantidad de pıxeles de cada burbuja. Ergo, como esta

complejidad se obtiene para cada burbuja, la complejidad total es O(∑nb

3/2i ). Esta ultima

es menor que O(n3/2b ), pues es facil ver que

∑n3/2k < (

∑nk)

3/2 para nk > 1.

(a) Calculo de distanciacon todo el fondo

(b) Calculo de distanciacon el fondo que toca lasburbujas

(c) Calculo de distanciacon el fondo que toca laburbuja donde perteneceel punto

Figura 4.1: Ejemplo del transformada de distancia por fuerza bruta

La implementacion desarrollada en Python resulto ser demasiado lenta por lo cual sehizo una implementacion usando el lenguaje C, obteniendo una mejora de dos ordenes demagnitud, no obstante, aun se podıa mejorar mas.

La segunda implementacion se baso en tecnica de propagacion, utilizando las ideas de[5]. Como lo dice su nombre, esta tecnica utiliza la analogıa de una quema de un pastizal,donde el fuego se propaga desde afuera hacia adentro. Esta logica fue traspasada al algoritmodesarrollado, donde la idea es calcular desde afuera hacia adentro, utilizando los valores delos vecinos ya calculados. El algoritmo recorre cada pıxel buscando si uno de sus vecinos yatiene su valor calculado. Cuando se calcula la distancia mınima de un pıxel se almacena porseparado las componentes X e Y , de manera de que los vecinos ocupen esta informacion.Para cada punto se revisa cuales de sus vecinos ya tienen calculada su distancia mınima,luego calculan la distancia correspondiente utilizando la informacion de dichos vecinos.

Por ejemplo, sea un punto P = (x, y), y un vecino Q = (x− 1, y − 1) cuyas distancia enx e y son dx y dy respectivamente, luego la distancia correspondiente para P utilizando la

28

informacion de Q es dP =√

(1 + dx)2 + (1 + dy)2. Basicamente lo que se hace es asumir queel punto del fondo con el cual se obtiene el mınimo para Q, sera tambien el mınimo para P .En caso de que esta suposicion sea erronea, al tomar el mınimo, este vecino sera descartado.

La intuicion tras esto es que el mınimo para P es el mınimo de alguno de sus vecinos,sin embargo, esto es cierto en la gran mayorıa de los casos, pero no en todos. En [5] sedetalla casos en que este metodo no da el valor real, sin embargo, no es tan relevante dadoque la diferencia es casi imperceptible, ademas se aplica un filtro gausiano para suavizar elresultado obtenido, lo cual atenua mas aun este error. El filtro se aplica porque existe unruido bastante molesto que genera separaciones en lugares que no deberıa haberla. Con laaplicacion del filtro desaparece este ruido y la separacion es, en general, bastante buena. Esteruido aparece tambien con el algoritmo de fuerza bruta, por lo que se descarta que sea unefecto propio del algoritmo de propagacion.

El algoritmo anterior solo se implemento utilizando C, pues Python demostro no ser buenaalternativa para realizar calculos de manera iterativa, ergo, el algoritmo necesariamente setendrıa que implementar en C. Esto hace que realizar una implementacion en Python nohubiera sido una buena idea. La implementacion hecha en C, para el caso del algoritmo defuerza bruta modificado, es la misma que en Python, la unica diferencia es que se tuvo queproveer de estructuras de datos que Python incluye por defecto y C no.

4.2. Watershed

Esta tecnica, como ya se menciono, trabaja sobre una imagen 2,5D, la cual se interpretacomo la elevacion de un terreno. Esta imagen contiene una serie de montes, cada uno de loscuales representa una burbuja. Cuando dos burbujas se traslapan, estos montes se tiendena fusionar, pues las faldas de ambos montes se juntan y se genera una quebrada, siguiendocon la analogıa geografica. Dicha quebrada es la frontera entre las burbujas, sin embargo,buscarla por medio de la verificacion de ciertas caracterısticas es difıcil.

Existe una serie de dificultades como tener una malla discreta y la direccion de la quebra-da, lo cual genera que la condicion que debe cumplir un punto en la quebrada sea bastantecompleja. Esta condicion se debe evaluar para todos los puntos de las burbujas, por lo tanto esun procedimiento bastante pesado. El algoritmo Watershed, por medio de un procesamientomas simple, descarta los puntos que no corresponden a una frontera.

Intuitivamente, la imagen en 2,5D representa la profundidad de un hoyo. Con esta in-terpretacion se simula una inundacion, que equivale a hacer un barrido desde las zonas masprofundas a las zonas mas altas. En cada profundidad, sube el nivel del agua y se marca conun identificador especial cuando dos fuentes de aguas se juntan. Los pıxeles marcados condicho identificador corresponden a las fronteras entre burbujas (Ver Figura 2.11).

29

(a) Imagen original (b) Transformada de distancia

(c) Caso 1: Existe solo una eti-queta distinta entre los vecinosdel punto

(d) Caso 2: Los vecinos delpunto no estan etiquetados

(e) Caso 3: Existe mas de unaetiqueta distinta entre los veci-nos del punto

(f) Algoritmo finalizado

(g) Imagen resultante

Figura 4.2: Ejemplo de escenarios en la revision del algoritmo Watershed

La implementacion contemplo una dificultad adicional, pues el algoritmo que se nece-sitaba debıa detectar los mınimos locales y asignar a dichos mınimos un identificador. Estacondicion en principio se penso que incorporarıa una cantidad de calculo pesado, lo que harıaal algoritmo mas lento, sin embargo, se diseno un algoritmo bastante eficiente que ubicadichos mınimos en lınea. La idea del algoritmo es procesar la imagen por profundidad, par-tiendo de la mayor hasta llegar a la superficie. El primer paso es seleccionar todos los puntosa una profundidad h dada. Puesto que el algoritmo comienza en la mayor profundidad, siun punto P de la lista tiene un vecino con profundidad mayor a h, entonces ese vecino yafue procesado, y por ende ya esta asociado a un identificador. La idea consiste en iterar estalista, revisando para cada punto sus vecinos, encontrando tres casos.

30

El primer caso es que los vecinos del punto aun no estan asociados a ningun identificador.En esta situacion no se hace nada con el (ver Figura 4.2(d)). El segundo caso es cuandoentre los vecinos del punto existen mas de un identificador diferente, por ende, se le asigna elidentificador especial que se utiliza para la frontera, pues se esta frente a dos fuentes distintas,luego, se deben separar (ver Figura 4.2(e)). El tercer y ultimo caso es cuando el punto poseeuno o mas vecinos que comparten el mismo identificador, luego se le asigna dicho identificador,pues el punto corresponde a la fuente asociada al identificador (ver Figura 4.2(c)).

Tras realizar lo anterior sobre la lista se pueden dar tres situaciones. La primera situaciones que la lista queda vacıa, en cuyo caso termina el proceso para la profundidad h. Lasegunda situacion es que la lista haya disminuido su tamano, luego, algunos de los puntosfueron asociados a algun identificador, por lo tanto, se debe volver a aplicar el mismo proceso.La razon es que puede ocurrir que alguno de los puntos ya identificados sea vecino de algunode los que quedo en la lista. Esta situacion hace que cada vez que la lista disminuye sutamano se debe volver a iterar. El tercer caso es cuando la lista no sufre ningun cambio,lo que quiere decir que ninguno de los puntos en la lista tiene un vecino identificado. Estasituacion da cuenta de que la propagacion de los identificadores termino, por ende, los puntosque quedaron en la lista, o algunos de ellos, son mınimos locales, pues ninguno de sus vecinostiene una profundidad mayor.

Es importante ver que, para un pıxel ya identificado, revisar sus vecinos y asignarles elmismo identificador es un error, pues se esta dejando de lado el objetivo del algoritmo, esdecir, encontrar una separacion entre las burbujas. De proceder como se menciono, marcandolos vecinos de un pıxel ya identificado, no se esta verificando si dicho vecino corresponde a lafrontera, y por ende, no se encontrara la separacion buscada.

La primera idea fue tomar los puntos y asociarles un nuevo identificador a cada uno, sinembargo, es un error, ya que no necesariamente son todos son mınimos distintos, pues unconjunto de pıxeles vecinos pueden formar parte de un mismo mınimo. Ası mismo, tampocoes solucion asignarles a todos el mismo identificador, pues tampoco son necesariamente elmismo mınimo ya que pueden existir varios conjuntos como el explicado anteriormente. Lasolucion utilizada fue tomar el primero de la lista, asignarle un nuevo identificador y volvera realizar la revision inicial. Con esto, si todos los puntos corresponden al mismo mınimo,por medio de la propagacion de los identificadores, se consumira la lista completa. En casocontrario, la lista corresponde a dos o mas minimos locales. De ser esta la situacion se procedede la misma manera, sin embargo, esta vez no se consumira toda la lista, sino que se volvera apresentar la situacion anterior, pero con una lista mas pequena. Este procedimiento se aplicahasta consumir toda la lista.

En teorıa, el algoritmo puede realizar infinitas iteraciones sobre los mismos puntos unay otra vez. En la practica esta lista de puntos debiese ser procesada en una sola iteracion,sin embargo, puede ocurrir que el orden en que se revisa los puntos no sea el mejor y, enconsecuencia, se requiera una segunda pasada para procesarlos todos. En la Figura 4.3 semuestra un diagrama con el proceso a que se somete en cada profundidad y en el Algoritmo4.1 se muestra el algoritmo completo.

31

El algoritmo Watershed solo trabaja con los pıxeles que pertenecen a las burbujas, porlo que su complejidad solo depende de este valor. El algoritmo en sı recorre a lo mas 2 vecescada pıxel, sin embargo, para obtener los pıxeles en el orden dado por la profundidad, serequiere ordenarlos previamente, o bien, utilizar un heap para almacenarlos y extraerlos enorden. La primera opcion es de orden O(nblog(nb)), al igual que insertar nb elementos en unheap. Luego, el algoritmo Watershed es de orden O(nblog(nb)).

Algoritmo 4.1 Watershed

Watershed(M)beginlabel← 1bubblePoints← pixelesEnBurbujas(M)H ← crearHeap(bubblePoints)while H 6= ∅ dol← pixelesMaximaProfundidad(H)aux← {∅}while l 6= ∅ do

for e ∈ l dovec← vecinosP ixel(e)labels← cantidadEtiquetasDistintas(vec)if labels == 0 thenaux← aux ∪ {e}

else if labels == 1 thenM [e]← label(vec)

elseM [e]← specialLabel

end ifend forif |l| == |aux| // No hubo cambios then

breakend if

end whileif l 6= ∅ // asignar nueva etiqueta thenM [l[0]]← labellabel + +

elsebreak

end ifend while

end

El algoritmo Watershed tambien se implemento en C, de manera de hacerlo mas rapido.El algoritmo Watershed genera una nueva imagen con los objetos separados. En este punto yaes posible obtener la informacion relevante de la imagen y desechar el resto. Esta informacioncorresponde a los diametros de las burbujas que aparecen en la imagen, las cuales ya fueron,dentro de lo posible, separadas. Para lo anterior se identifico las zonas conectadas de laimagen, las cuales corresponden a cada una de las burbujas. Una vez identificadas, se calculo la

32

Figura 4.3: Diagrama de Watershed

transformada de distancia sobre cada una de ellas, donde es posible identificar el valor masalto, el que corresponde al centro de la burbuja y dicho valor es el radio de la burbuja medidaen pıxeles. Estos diametros son recopilados en una lista, y la imagen es, finalmente, desechada.

4.3. Calculo de metricas

El ultimo paso del procesamiento clasico corresponde al calculo de las metricas sobre ladistribucion de las burbujas. Como ya se menciono, este metodo se basa en la identificacionde cada burbuja y, posteriormente, se obtienen metricas sobre cada una.

Como ya se menciono el algoritmo Watershed genera una nueva imagen, con las burbujasseparadas. Con esta imagen se obtiene una lista de los diametros de las burbujas. Con estalista se calculo los momentos de orden 1, 2 y 3 de la distribucion. La formula utilizada paracalcular los momentos fue

µk =1

n

n∑i=1

Xki

33

donde k ∈ {1, 2, 3} y Xi es el diametro de la i-esima burbuja.

En el Capıtulo X se muestran graficos que dan cuenta del comportamiento de este metodo,ademas se hace un analisis respecto a sus ventajas y desventajas.

4.4. Algoritmo

Como ya se explico, el metodo tradicional lo que hace es obtener una imagen nueva dondese separa los objetos circulares que aparecen aglomerados en la imagen original. Para eso seutiliza Watershed, el cual necesita que la imagen sea un mapa en 2,5D, es decir, una matrizcon valores reales, los cuales son interpretados como un relieve. Posteriormente, se calculael diametro para cada burbuja y, finalmente, se calcula los momentos sobre la lista de losdiametros obtenidos. La validacion del algoritmo se realiza en el Capıtulo 6.

4.4.1. Procesamiento paralelo

Los algoritmos explicados, es decir, Watershed y la transformada de distancia, no fueronimplementados para procesamiento paralelo. La razon es que estas operaciones son suma-mente lentas de ejecutar en Python (Ver resultados en el seccion 6.2), por lo que se imple-mentaron en C, utilizando la API que provee el lenguaje para estos efectos. Realizar unaimplementacion en paralelo en C es bastante complejo por el bajo nivel del lenguaje, lo cualhace que sea prohibitivo por el tema del tiempo que requiere y el tiempo que se dispone paraeste trabajo. La opcion de realizar el procesamiento paralelo en Python no es viable, porun tema de expectativas. La aplicacion que pretende generar este trabajo esta pensada paracomputadores normales, no para supercomputadores, por lo cual, la cantidad de procesadorespodrıan disminuir el tiempo de calculo, en el mejor de los casos, en un orden de magnitud.A pesar de esta mejora en el tiempo, la utilizacion de C sigue teniendo mejores resultados.

Existe una parte del procedimiento, bastante pequena, que pudo ser implementada parautilizar procesamiento paralelo. Cuando los elementos de la imagen son separados, se vuelvea calcular la transformada de distancia para obtener ası el radio. La identificacion de lasburbujas y la busqueda de su radio fue hecho en paralelo. Esta operacion es bastante pequenadentro del proceso completo, sin embargo, se pudo reducir unos pocos segundos el tiempototal (ver seccion 6.3).

34

Capıtulo 5

Procesamiento estocastico

Esta tecnica utiliza un enfoque totalmente distinto al anterior. La idea de este algoritmo esutilizar la informacion estadıstica de la imagen para estimar los momentos de la distribucion.En este metodo las burbujas individuales ya no son la informacion relevante, sino que pasana formar parte de una probabilidad, la cual se utiliza en la estimacion.

El metodo estocastico asume que la imagen se comporta como un modelo booleano esta-cionario (seccion 2.2). Esto quiere decir que existe una coneccion entre la imagen y el modelo.El modelo booleano, descrito en la seccion 2.2, esta compuesto por un conjunto de puntosxi ∈ R2 el cual corresponde a las posiciones de los centros de las burbujas en la imagen, luegola intensidad del proceso de Poisson que genera estos puntos, es decir θ, es la cantidad decentros de burbujas por pıxel. Este parametro corresponde a la cantidad de burbujas cuyoscentros estan en dentro de los lımites de la imagen, dividido por la dimension en pıxeles dela imagen. El conjunto de los Ai ⊂ R2 corresponden a las burbujas, por ende una imagencorresponde a una realizacion del modelo booleano, donde el modelo en sı (Ξ) es el conjuntode las burbujas en sus posiciones respectivas.

A priori, el modelo booleano no tiene restricciones sobre la forma que deben tener losobjetos, en este caso, las burbujas. Sin embargo, solo con entender una imagen como unmodelo booleano no es suficiente. Para poder utilizar esta forma de modelar una imagenen la obtencion la distribucion de los objetos por tamanos, es necesario imponer ciertascondiciones. Como se explico en la seccion 2.2, el modelo booleano puede ser descrito porsu avoiding functional. Este corresponde a la probabilidad de que un conjunto K ⊂ R2 nose intersecte con el modelo booleano, es decir, que la interseccion entre K y las burbujassea vacıo. Esto ultimo no pone restricciones sobre el conjunto K, mas la eleccion de esteconjunto es la que hace la diferencia entre poder o no aplicarlo en la practica. Mas adelantese explica como el conjunto K elegido condiciona la forma de los objetos a cırculos y comoeste condicionamiento permite un calculo simple.

Las metricas que se desea calcular corresponden a momentos de la distribucion. Para

35

obtenerlas existe una formula explicada en [4], la cual utiliza la informacion recopilada en elavoiding functional. El problema de esta formula es que los valores utilizados (expresionesderivadas del avoiding functional), poseen mucho ruido, por lo cual se tuvo que idear unmecanismo para minimizar los efectos de ese ruido. Dicho mecanismo se explica en detallemas adelante. Ademas de lo anterior, la formula utilizada es teorica y, en consecuencia, comose explica en el ultimo parrafo de la seccion 2.2, al reemplazar valores teoricos (κ′′A(h)) poruna estimacion (Ψ′′(h)/θ) la formula queda dependiente de θ, lo cual genera la necesidad deestimarlo. La estimacion de θ tambien posee una gran cantidad de ruido, por ende, tambiense tuvo que crear un mecanismo para minimizar sus efectos.

5.1. Calculo del Avoiding Functional

El primer paso en el metodo estocastico es transformar la informacion de la imagen eninformacion estadıstica util. Como se menciono anteriorente, una forma de describir el modelobooleano es el avoiding functional. Al asumir que una imagen es una realizacion de estemodelo, este puede ser estimado a partir de la imagen. Como se explico en los antecedentes,el avoiding functional coresponde a

T (K) = P(Ξ ∩K = ∅)

para todo conjunto K. El conjunto K elegido para encontrar la probabilidad son dos puntosa una distancia h. Con dicho conjunto el avoiding functional es la probabilidad de que dospuntos a una distancia h no se intersecten con el modelo booleano, es decir, con las burbujasde la imagen. Esto equivale a decir que es la probabilidad de que dichos puntos pertenezcan,simultaneamente, al fondo de la imagen. Esta probabilidad, como es de esperarse, es estimadapor medio de la frecuencia empırica. En la Figura 5.1 se muestra el conjunto K, ademasse muestran ejemplos de casos favorables y desfavorables para el avoiding functional. Laprobabilidad se debe obtener para todos los valores posibles de h, luego la frecuencia debeser calculada de la misma manera.

La primera idea para calcular la frecuencia empırica fue realizar un barrido completopara cada punto. Esto significa que para cada punto pi se calcula la distancia a cada pj coni ≤ j ≤ n, luego se revisa si son un caso favorable, es decir, si ambos estan en el fondo. Elorden en que se tomen los puntos no es relevante, pues cualquiera sea el orden se tendra todaslas parejas; lo importante es que al hacer el barrido para un punto, este no vuelva a serconsiderado, de esta manera no se repiten las parejas. Utilizando la numeracion de la imagenen la Figura 5.2, el barrido completo tomarıa todas las parejas {(i, j) | 1 ≤ i ≤ 48 ∧ i < j ≤49}. Para cada una de estas parejas se calcula su distancia, luego se ve si es un caso favorableo no y, finalmente, se actualiza la frecuencia para dicha distancia, es decir, se actualizan loscasos totales y los casos favorables, si corresponde. Por ejemplo, el par de pıxeles (1, 11) estana distancia

√17 y ambos son parte del fondo, luego se debe agregar un caso favorable y un

caso total a la frecuencia para h =√

17. En el caso de el par (1, 18) la distancia es 2√

5 yuno de los pıxeles pertenece a una burbuja, luego en la frecuencia para h = 2

√5 se debe

actualizar solo los casos totales.

36

(a) Conjunto K conh = 10

(b) Ejemplo de caso favor-able K ∪ Ξ = ∅

(c) Ejemplo de caso desfa-vorable K ∪ Ξ 6= ∅

(d) Ejemplo de caso desfa-vorable K ∪ Ξ 6= ∅

Figura 5.1: Conjunto K y ejemplos para avoiding functional

Figura 5.2: Numeracion posible de pıxeles, para barrido completo

La intuicion dice que mientras mas grande sea la muestra la estimacion debiera ser mejor.En este caso no ocurre, pues si se utiliza la muestra mas grande posible, es decir todoslos pares posibles, la estimacion contiene una gran cantidad de ruido. El ruido se producepor la discretizacion propia de la imagen, ademas del sobreajuste para distancias grandes,pues entre dos enteros existe muchos valores intermedios. El problema de las direccionesdiagonales es que para estas se percibe de mayor manera que las burbujas no son realmenteredondas. A su vez, el sobreajuste se produce por estas direcciones diagonales, las cualesgeneran distancias irracionales y, en consecuencia, que entre dos enteros existan mas deun valor para la curva estimada. Por ejemplo, entre 12 y 13,

√144 y

√169 respectivamente,

existe nueve puntos entre ellos (√

145,√

146,√

148,√

149,√

153,√

157,√

160,√

162,√

164). Estospuntos intermedios provienen de las direcciones diagonales y sus valores fluctuan bastante,generando mucho ruido.

Como los objetos de estudio son discos, estos son uniformes en todas direcciones, y porlo tanto el muestreo es isotropo, es decir, las variaciones siguen el mismo patron en todas

37

las direcciones, o dicho de otra manera, no hay direcciones preferenciales. Esta caracterısticahizo que la solucion elegida pasara por no tomar todas las direcciones, sino que solo toma lavertical y la horizontal. Este muestreo aprovecha que la imagen es una matriz y utiliza sugeometrıa para calcular inteligentemente la frecuencia.

El procedimiento utilizado para calcular la frecuencia empırica para el muestreo explicadoel parrafo anterior toma una copia de la matriz de pıxeles y elimina las primeras h columnas(ver Figura 5.4(b)), toma tambien otra copia y elimina las ultimas h columnas (ver Figura5.4(c)). Estas matrices tienen la caracterıstica que si se toman dos pıxeles, uno en cadamatriz y ambos en la misma coordenada, dichos pıxeles estan a una distancia h. Por ejemplo,si se toma el pıxel (0, 0) de cada una de las matrices anteriores, estos corresponden a lospıxeles (0, 0) y (h, 0) de la matriz original, los cuales estan a distancia h. Por otro lado, siambos puntos pertenecen al fondo es lo mismo que decir que ambos tienen valor falso, enconsecuencia, equivale a la expresion ¬(p ∨ q). Luego, para calcular la frecuencia empıricase debe aplicar dicha expresion elemento por elemento a los valores en las matrices. Estaoperacion ya esta implementada eficientemente en Numpy, ademas existe una funcion quepermite sumar todos los valores en una matriz, con la cual se puede sumar todos los casosfavorables. Los casos totales es el tamano de la matriz, con lo que se puede obtener, finalmente,la frecuencia. Este procedimiento se efectua analogamente en la direccion vertical.

Figura 5.3: Estimacion del avoiding functional usando un barrido completo, filas y columnas,y muestreo sobre filas y columnas

El tiempo de calculo bajo de horas a segundos al disminuir el muestreo utilizado, es decir,aproximadamente tres ordenes de magnitud. Se podrıa haber intentado optimizar el barridocompleto, sin embargo, el ruido de la curva es inherente a utilizar las direcciones diagonales, ya las distancias discretas que existen en la imagen. Otro motivo que hizo descartar esta opciones que mas adelante el algoritmo necesita un espaciado regular para realizar algunos calculos,lo cual solo es posible utilizando distancias enteras. A pesar de no buscar optimizaciones

38

para el algoritmo, existen razones para pensar que los tiempos alcanzados hubiesen sidopeores que los obtenidos con el muestreo horizontal y vertical. El principal motivo es que lacantidad de parejas que procesa el barrido completo es demasiado grande en comparacioncon la nueva alternativa que no utiliza direcciones oblicuas. Esto se puede ver por medio desus complejidades. En el caso del barrido completo el orden es de O(N2 ·M2), donde N y Mson las dimensiones de la matriz, pues para cada pıxel se calcula la probabilidad con todos losdemas. A su vez el orden de calcular el avoiding functional sobre las direcciones horizontal yvertical es O(N ·M · (N +M)), pues para cada pıxel solo se calcula la probabilidad para sufila y para su columna. Tambien se debe considerar que el muestreo que utiliza la direccionhorizontal y la vertical para obtener la frecuencia, aprovecha muy bien la geometrıa de este,agrupando para un h todos los puntos a dicha distancia sin necesidad de calcular la distanciapropiamente tal, a diferencia del barrido completo, el cual debe calcular la distancia para cadapareja y realizar una busqueda para actualizar correctamente la frecuencia para la distanciacorrespondiente.

(a) Imagen original (b) En rojo la columnas eliminadas al ini-cio

(c) En rojo la columnas eliminadas al final (d) Negacion de la disyuncion en-tre (b) y (c), las formas no impor-tan, solo el total

Figura 5.4: Demostracion del procedimiento para calculo de avoiding functional

El disminuir el tamano de la muestra, en este caso particular, ayudo a eliminar datos queintroducen ruido. Pero, en general, al disminuir el muestreo se produce un trade-off entre lacalidad de la respuesta y la cantidad de informacion necesaria o, en aplicaciones como esta,el tiempo de calculo de la calidad de la respuesta. Al utilizar filas y columnas se disminuyo eltamano de la muestra, sin embargo, se considero que aun podıa ser mas pequena.

39

La muestra debe ser aleatoria, por lo tanto disminuir la muestra, no es tan simple comoelegir un subconjunto fijo. Con el fin de dar aleatoriedad a la muestra que se toma se tuvoque disenar un estrategia. La idea tras esta fue utilizar solamente las filas que esten separadaspor una distancia fija. Por ejemplo: la primera, la cuarta, la septima, y ası sucesivamente.Sin embargo, partir arbitrariamente de la primera fila hace que esta estrategia no genere unmuestreo aleatorio. Para darle aleatoriedad al muestreo, cuando se elige cual es el numero defilas que habra entre las seleccionadas, se elige cual sera el punto de partida. Por ejemplo,si se elige que la separacion sera de 5 filas, se toma un numero al azar entre la primera y laquinta, la cual sera el punto de partida. En la Figura 5.5 se puede ver el ejemplo anterior. Seas la cantidad de filas que separan a las que se toman como muestra, luego o sera un numeroentre 0 y s. Luego, las filas que formaran parte de la muestra seran aquellas cuyo resto dela division por s sea o, es decir F = {x |xmod s = o } o F = {x |x = i ∗ s + o }. El procesoes analogo con las columnas, mas se vuelve a obtener o, de esta manera se introduce masaleatoriedad, anadiendo mas casos posibles a la eleccion de la muestra.

(a) Todas las filas y columnas (b) Muestreo utilizando s = 5,of = 3 y oc = 2

Figura 5.5: Ejemplo de muestreo sobre filas y columnas

Para poder implementar lo anterior se tuvo que modificar la geometrıa de la matriz depıxeles, de manera de poder seguir utilizando el algoritmo anterior, el cual aplica operacioneslogicas punto a punto sobre la matrices truncadas. La idea es eliminar las filas que no seranparte del muestreo, para lo cual se utiliza slices. Estas slices permiten obtener porcionesrectangulares de una matriz.

En esta parte se recomienda seguir la lectura junto con las imagenes de la Figura 5.6donde se muestra un ejemplo del proceso que se explicara a continuacion. En la Figura 5.6(c)aparecen marcadas las filas que se tomaran como muestra, estas filas (1,4,7 y 10) correspondena F = {x |x = 3 · i+ 1 }, es decir s = 3 y o = 1. El primer paso es eliminar las filas anterioresa la que se escogio como primera (ver Figura 5.6(d)), lo cual equivale a trabajar con lasfilas desde la o en adelante, en otras palabras, utilizar desde la fila uno en adelante, lo queequivale a eliminar la fila 0. Posteriormente, se cambiara las dimensiones de la matriz, para loque tambien existe una herramienta en Numpy, sin embargo, se debe hacer algunos ajustes,pues al hacer la redistribucion puede que se necesite mas elementos. En otras palabras, si lamultiplicacion de las dimensiones originales no es igual a la multiplicacion de las dimensionesfinales no se podra resdistribuir, pues no se tiene la cantidad necesaria de elementos. Porejemplo, si se tiene una matriz de 3x3, esta no puede transformarse en una matriz de 2x5,pues solo se tiene 9 elementos y una matriz de 2x5 requiere tener 10.

40

(a) Imagen original (b) Imagen con pıxeles nu-merados

(c) Imagen con el muestreoelegido en verde

(d) Filas anteriores a o elimi-nadas

(e) Se agregan filas dummypara poder redimensionar

(f) Se redimensiona la matriz de puntos

(g) Se rescata las filas de-seadas

Figura 5.6: Proceso de redimensionado y slicing para obtener matriz con filas muestreadas

La idea de realizar la redistribucion de los elementos de la matriz es que queden contiguaslas filas que son parte del muestreo. Sea (f, c) la cantidad de filas y columnas, despues deeliminar las anteriores a la o y antes de la redistribucion (Figura 5.6(d)), se define (f ′, c′) comola nueva cantidad de filas y columnas, donde f ′ = df/se, es decir, la cantidad de filas quepertenecen al muestreo, y c′ = c ∗ s (ver Figura 5.6(f)). Ası la primera fila queda compuestapor la primera fila de interes e, inmediatamente despues, las filas intermedias que se quiereeliminar; la segunda fila queda con la segunda fila de interes seguida de las filas que se quieredesechar, y ası con todas las demas.

Para solucionar el problema de que las dimensiones calcen se calculo la cantidad f ′ de filasque son parte del muestreo, y luego se multiplico por el tamano s del salto. Las dimensionesde la nueva matriz son (f ′ ∗ s, c), es decir (12, 12). Esta matriz puede tener mas filas delas necesarias (ver Figura 5.6(e)), las cuales tendran valores dummy, es decir, que no sonde interes, pues estos valores rellenan posiciones que posteriormente se desechan y solo seagregan para poder redimensionar. El resto de la matriz se rellena con los valores de lamatriz original. En el ejemplo de la Figura 5.6(d) f = 11 y c = 12, luego f ′ = d11/3e = 4y c′ = 12 ∗ 3 = 36. Se crea una matriz de 12x12 y el las primeras filas se copian las filas dela matriz original. Esta nueva matriz (ver Figura 5.6(e)) tiene 144 elementos, al igual que la

41

matriz redimensionada 5.6(f), por lo tanto se puede redimensionar sin problemas. Finalmente,de la matriz redimensionada se toman las c primeras columnas, las cuales contienen las filasmarcadas en la Figura 5.6(f), que son las filas que se utilizaran como muestreo para calcularel avoiding functional.

En el Algoritmo 5.1 se muestra el algoritmo para obtener el submuestreo para filas.Ademas se muestra como se utilizan las slice de Python.

Con este proceso, se obtiene un conjunto mas pequeno, el cual solo sirve para obtener elavoiding functional en la direccion horizontal. Para realizar el mismo calculo en la direccionvertical se debe hacer el proceso analogo, utilizando las filas en lugar de las columnas. Estadisminucion en el muestreo no induce una mejora en la complejidad del algoritmo, pues solose pondera la complejidad del algortimo original en un factor s−1.

Algoritmo 5.1 Obtencion del muestreo aleatorio

obtenerMuestreo(M, s)begino← random(0, s)M ′ ←M [o :][:]f ← rows(M ′)c← columns(M ′)f ′ ← df/cec′ ← c · sN ← matrix(f ′ ∗ s, c)N [: f ][:]←M ′

N ← resize(N, f ′, c′)return N [:][: s]

end

// slices// A[: i]→ elementos desde el primero hasta el i-esimo (no incluido)// A[i :]→ elementos desde i-esimo hasta ultimo// A[:]→ todos los elementos de A

5.2. Estimacion de los momentos

Como se menciono anteriormente, existe una formula por medio de la cual es posibleobtener una estimacion de los momentos de orden k (µk). La formula mencionada dependede κ′′A(h), cuyo valor es dificil de encontrar empıricamente, sin embargo, como se explico enla seccion 2.2,

Ψ′′(h) = θ · κ′′A(h)

dondeΨ(h) = ln(T (k))

42

Al realizar el reemplazo mencionado el parrafo anterior, se obtiene una formula paracalcular θ · µk, por lo cual, posteriormente se debe obtener una estimacion de θ para poderdespejar el valor de µk, lo cual se detalla en la proxima seccion.

Para utilizar la formula

θµk =nΓ(k

2)

√πΓ(k+1

2)

∫ +∞

0

hk−1Ψ′′(h)dh

se requiere, como primer paso, obtener numericamente Ψ′′(h), utilizando la formula de los 5puntos. Una vez obtenido este se dispone de todos los valores para poder calcular numerica-mente la integral, sin embargo, esta se puede aproximar dada la naturaleza de los datos conque se trabaja.

La primera aproximacion corresponde a escribir la integral como la suma de integralesmas pequenas. A primera vista esto parece una igualdad, mas Ψ′′(h) esta definida para henteros entre 1 y hmax, por lo que la suma de integrales no parte desde cero. Luego la integralqueda definida como ∫ +∞

0

hn−1Ψ′′(h)dh ≈hmax∑i=1

∫ i+ 12

i− 12

hn−1Ψ′′(h)dh

Como se dijo Ψ′′(h) esta definida solo para h enteros, luego Ψ′′(h) es constante en elintervalo [i − 1/2, i + 1/2] por lo tanto sale de la integral y el resto, es decir hn−1 se puedeintegrar analıticamente, quedando la formula inicial transformada en

θµk =nΓ(k

2)

√πΓ(k+1

2)

hmax∑i=1

Ψ′′(h)

[hk

n

]i+1/2

i−1/2

El valor obtenido al realizar el calculo fue negativo, lo cual no es posible dado que estevalor, por definicion es mayor o igual a cero, pues es la suma de cuadrados, por lo tanto, lasuma de valores positivos o nulos. Despues de analizarlo, se llego a la conclusion que el errorprovenıa del ruido de Ψ′′(h). En la Figura 5.7 se puede ver dicha curva, la cual es bastanteruidosa.

Teoricamente, esta curva parte desde cero, es creciente durante un tramo y luego decrecehasta llegar nuevamente a cero, desde ese punto en adelante es nula. La curva obtenida nomostraba este comportamiento, principalmente por la cantidad de ruido que contenıa. Sinembargo, al aplicar un filtro de difusion, el comportamiento teorico comenzo a vislumbrarselevemente.

La curva teorica tiene una forma caracterıstica, no obstante, todas las estructuras identi-ficables tienen una dependencia de los valores que se obtienen de la imagen, exceptuando elcero al inicio y al final de la zona de decrecimiento. La idea fue encontrar el segundo punto

43

Figura 5.7: Ejemplo de Ψ′′(h) original

donde la curva se anula, aquel donde la curva termina su decrecimiento para anularse com-pletamente. De esta manera se puede cambiar el lımite superior de la sumatoria con la cual seaproxima la integral, y ası no sumar terminos que debiesen ser cero y que no lo son productodel ruido propio de una medicion. Sobre el punto que se pretende encontrar se sabe que esta ala derecha del maximo global, pues la curva comienza en cero, sube hasta el maximo globaly, finalmente, decrece hasta anularse.

Al aplicar filtros de difusion sobre una senal, ademas de poder identificar de mejor maneralas estructuras que componen la senal, tambien se observa un desplazamiento en el eje X. Estohace que la operacion a realizar para encontrar el punto donde se anula la senal, no sea tansimple como aplicar un filtro fuerte e identificar el punto. De aplicar un filtro suficientementefuerte es probable que se pueda obtener una forma similar a la teorica, sin embargo, el puntobuscado se desplazarıa tanto que ya no serıa util. Es por este motivo que se debe intentareste punto sin llegar al extremo de aplicar filtros demasiado fuertes.

Para poder estimar el valor donde se anula la senal es necesario que exista una ciertaestabilidad en torno al cero para la parte final de esta. Con este fin se impuso que el filtro autilizar debe generar una senal que tenga cierta cantidad de mınimos globales bajo el cero y ala derecha del maximo global (ver Figura 5.8(a)). La cantidad de mınimos debe ser ingresadapor el usuario. Esta cantidad no puede ser pequena, pues decantarıa en el caso de un filtrofuerte, el cual desplaza mucho el punto que se quiere estimar. Esta cantidad tampoco puedeser muy grande, pues el ruido afectarıa demasiado la estimacion de este. La cantidad demınimos a utilizar no es un valor dependiente de la imagen en particular, sino que dependede las dimensiones de la imagen y la resolucion de esta, por lo que basta una imagen parapoder definir dicho valor.

44

Para obtener la senal con una cantidad de mınimos especıfica se creo una variante dedoubling search. La idea original de este algoritmo se explica en la seccion 2.3. La varianteconsistio en definir lımites para la cantidad de mınimos. Lo que pretende encontrar estavariante es un filtro que genere una senal cuya cantidad de mınimos negativos este entrelos lımites impuestos. Para esto lo que hace realmente es buscar dicha senal variando ladesviacion estandar σ del filtro de difusion.

A medida que el filtro es mas fuerte, se tendra menos mınimos negativos. Luego, la primeraparte del algoritmo incrementa exponencialmente σ hasta que se llega a una cantidad demınimos locales negativos, menor que el lımite superior impuesto. Si la cantidad es mayorque el lımite inferior, se esta dentro del rango, luego se encontro la senal deseada. En casocontrario, se comienza una busqueda binaria sobre los valores de σ.

Si la cantidad de mınimos locales negativos es menor que el lımite inferior, esto quieredecir que la iteracion anterior genero una senal con una cantidad mayor de mınimos que ellımite superior definido. Esto ultimo porque, de no ser ası, no se hubiera iterado una vez mas,pues la condicion para parar de iterar se hubiese cumplido. Luego, se tiene σsup que generauna senal con una cantidad de mınimos mayor que la deseada, y σinf que genera una senalcon menos mınimos que los deseados. Con estas dos cotas, se puede realizar una busquedabinaria sobre los valores de σ hasta encontrar una senal con la cantidad de mınimos localesnegativos entre los lımites.

El siguiente paso, despues de encontrar la senal con la cantidad de mınimos deseada, esestimar el punto donde se alcanza el cero. Para esto se barajaron dos opciones: la primeracalculando el cero para una recta entre el primer mınimo global bajo el cero y el maximoglobal (ver Figura 5.8(b)), y la segunda, una busqueda punto a punto desde el primer mınimolocal bajo el cero hacia el maximo global. Los resultados fueron muy similares, por lo cual seopto por utilizar la primera, pues su tiempo de calculo es menor.

Una vez definido el valor donde la curva se anula, se calculo nuevamente los momentos,esta vez limitando la sumatoria al valor donde la curva se anula, obteniendo valores coherentesy muy cercanos a los reales. Para esta operacion no se pudo obtener la complejidad, pues noes posible determinar que factores influyen en la forma de la senal, y por consiguiente, no sepuede relacionar la cantidad de iteraciones necesarias con alguna caracterıstica de la imageno de la senal.

En el Algoritmo 5.2 se puede ver el procedimiento realizado para obtener la estimacionde los momentos. Este procedimiento muestra la variante de doubling search disenada pararealizar la busqueda de la curva con las caracterısticas deseadas.

45

Algoritmo 5.2 Estimacion de los momentos de orden k

obtenerMomentos(T, k,min,max)begin

Ψ← log(T )i← 0imin← 0imax← 0f ← filtroGausiano(0)minimosNegativos← obtenerMinimosNegativos(Ψ′′)while minimosNegativos > max dosigma← 2i

imin← imaximax← sigmaf ← filtroGausiano(sigma)minimosNegativos← obtenerMinimosNegativos(f(Ψ′′))

end whileif minimosNegativos < min then

while true dosigma← (imin+ imax)/2f ← filtroGausiano(sigma)minimosNegativos← obtenerMinimosNegativos(f(Ψ′′))if minimosNegativos < min thenimax← sigma

else if minimosNegativos > max thenimin← sigma

elsebreak

end ifend while

end iflimite← obtenerCero(f(Ψ′′))return formulaMomentos(Ψ′′, k, limite)

end

46

(a) Ψ′′(h) despues de aplicar filtro gausiano con σ = 24

(b) Estimacion del cero de la curva

Figura 5.8: Curva suavizada y estimacion del cero para la curva

5.3. Estimacion de θ

La formula utilizada en la seccion anterior para calcular los momentos de orden k esdependiente de θ, por lo que es necesario estimar este ultimo. El valor de θ, como se men-ciono en la seccion 2.2, corresponde a la intensidad del proceso de Poisson definido en elmodelo booleano. Empıricamente, este valor corresponde a la cantidad de centros de burbu-jas por pıxel, por lo tanto, es equivalente a la cantidad de burbujas en la imagen, divididopor la cantidad de pıxeles que la componen.

Para obtener una estimacion de θ se trabaja sobre la curva θ · (1− F (a)) donde F (a) es

47

la distribucion acumulada de burbujas por tamano (en pıxeles). Esta curva proviene de laformula

(1− F (a)) =2

π

∫ +∞

0

κA(h)dh√h2 − a2

la cual se muestra en los antecedente. En dicha formula se debe utilizar, nuevamente, Ψ′′(h)/θpara estimar el valor de κ′′A(h) con lo cual se obtiene la siguiente expresion, con la cual setrabajo finalmente

θ · (1− F (a)) =2

π

∫ +∞

0

Ψ′′(h)dh√h2 − a2

Para la integral de la expresion anterior existe una aproximacion numerica, la cual seexplica en [4] y se muestra a continuacion∫ +∞

0

Ψ′′(h)dh√h2 − a2

≈ 2

hmax−q−1∑i=1/2

Ψ′′((q + i)ε)[ln(2√h− a+ 2

√h+ a)]

(q+i+0,5)ε(q+i−0,5)ε

donde q ∈ [12, 32, . . . , hmax − 3

2], a = qε con ε = 1, pues es la menor distancia con la que se

cuenta.

Teoricamente, la funcion θ · (1−F (a)) deberıa ser decreciente (Ver Figura 5.9(a)), pues ladistribucion acumulada es una funcion creciente. Ademas, dado que θ pondera a la expresion(1− F (a)), cuyo valor maximo es 1, la expresion completa debe tener como maximo el valorθ, el cual se alcanza en los primeros valores, donde F (a) = 0. La distribucion acumulada esnula mientras no se alcance un diametro igual o mayor que el de la burbuja mas pequena, porlo tanto, existira una meseta en los primeros valores. Adicionalmente, la expresion completase anula cuando F (a) = 1, es decir, cuando se supera el diametro de la burbuja mas grande.En la practica, θ · (1− F (a)) tiene una forma similar a la que se espera (Ver Figura 5.9(b)),donde se puede vislumbrar la meseta, posteriormente se puede ver que la funcion tiende adecrecer (existe un ruido que no permite decir que es realmente decreciente), y finalmente,tiende a anularse para diametros grandes. En resumen, la expresion obtenida tiene una formasimilar a la esperada, sin embargo, es el ruido el que impide identificar de manera clara losvalores que se quiere encontrar.

La estrategia para estimar θ fue encontrar la meseta que se extiende desde el comienzohasta el diametro de la burbuja mas pequena. En una primera aproximacion se tomo elprimer valor, sin embargo, el ruido es bastante mas intenso en los primeros valores dadoque para diametros pequenos las burbujas no parecen burbujas, sino mas bien cuadrados.Para solucionar este inconveniente simplemente se elimina una cierta cantidad de puntos alinicio. Esto no afecta cuando la burbuja mas pequena es mas grande que los diametros quese desechan. La justificacion detras de la eliminacion de dichos puntos es que existe unameseta y que no es indispensable utilizar esos puntos para encontrarla. Sin embargo, el valorobtenido seguıa siendo bastante erratico, por lo cual esta opcion fue desechada en busca deun mejor estimador.

La teorıa dice que la meseta debiera ser constante, mas esto en la practica no es cierto. Sinembargo, identificando los puntos que deberıan pertenecer a esta meseta se puede intentar

48

(a) Curva teorica

(b) Curva real obtenida sobre una imagen de 1500x1000 pıxeles

Figura 5.9: θ · (1− F (a)): Curva teorica y curva real

estimar el valor de θ, en funcion de estos. Con esta idea en mente se ideo una nueva estrategia.Para encontrar los puntos que pertenecen a la meseta se busca el ultimo punto que sea mayoro igual al primero (ver Figura 5.10). En caso que el primer punto sea el mas alto se descartay se repite el proceso. A esta busqueda se le pone un lımite para que no se recorra zonas queno corresponda. Por ejemplo, cuando la curva sea realmente decreciente se desecharan todospuntos que se deberıa considerar. Ademas la busqueda continuarıa hasta llegar a la partefinal de la curva, donde esta se anula y, en consecuencia, se encontrarıa una meseta que no loes. La idea de este lımite es evitar la segunda situacion, es decir, que no se busque al final dela curva. Cuando este lımite es traspasado se dira que no existe el estimador. Mas adelantese vera la utilidad de que no exista el estimador.

49

Figura 5.10: Ejemplo de la estimacion de los puntos que corresponden a la meseta

Cuando los puntos pertenecientes a la meseta son encontrados se debe estimar el valor dela meseta. Para hacerlo se implementaron dos metodos: el primero fue calcular el promediode los puntos, y el segundo, realizar una regresion lineal con ellos y tomar como estimadorel corte con el eje Y (ver Figura 5.11). En terminos generales, ambos funcionaron bien, sinembargo, se opto por la segunda alternativa, pues es menos sensible a valores extremos,ademas este estimador sigue la tendencia de los datos.

Figura 5.11: Estimador de θ utilizando una regresion lineal

50

Al realizar pruebas con el estimador anterior se comenzo a notar problemas en algunoscasos. El principal problema fue que habıa mucha diferencia entre dos ejecuciones, lo quedisminuye la confianza en el valor obtenido. Para subsanar este problema se penso en aplicarun suavizado, utilizando un filtro gausiano, mas no se sabıa cuan fuerte debıa ser el filtro, yencontrarlo puede ser un problema en sı mismo.

La solucion que se intento fue utilizar un espacio de escalas, es decir, una representacionen varios niveles, donde en cada uno de estos la senal tiene un nivel de suavizado distinto.Estos espacios son muy utiles en circunstancias donde no se sabe el grado de suavizado quese necesita, por lo cual se toma un rango que incluya el nivel necesario. Una vez construidaesta estructura se pueden utilizar los distintos niveles para obtener un resultado que recojala informacion en cada nivel y, si es posible, dandole mas importancia a los cercanos al niveloptimo.

Al intentar aplicar estos espacios de escala al problema de la estimacion de θ, surgio elproblema de elegir el intervalo que contuviese el nivel de suavizado que se buscaba. Paraencontrar este intervalo se comenzo a probar la herramienta con distintas curvas, de manerade descubrir, empıricamente, los lımites que definieran el rango con el que se trabajarıa. Estabusqueda fue bastante a ciegas, pues tampoco era claro el comportamiento que deberıa tenerla curva al aplicarle el filtro adecuado.

Para poder inferir el rango correcto para el espacio de escalas, lo que se intento fue que elvalor real de θ en la imagen estuviera dentro del intervalo donde se movıan las estimacionesen cada uno de los niveles. En otras palabras, sea θ(σ) la estimacion de θ para la curvasuavizada con un filtro gausiano con desviacion estandar σ y sea θreal el valor real, obtenidode la imagen. Luego, el rango [σinf , σsup] debe cumplir que θ(σinf ) ≤ θreal ≤ θ(σsup).

Para esto lo que se hizo fue fijar σinf = 0 e incrementar σsup hasta que se cumpla la condi-cion mencionada el parrafo anterior. Para esto fue necesario hacer el calculo manualmentea un conjunto de imagenes. θ, al ser la intensidad del proceso de Poisson segun el cual serige el modelo booleano estacionario, es equivalente a la cantidad de centros de burbujas porpıxel, por ende θ es igual a la cantidad de centros de burbujas en la imagen, dividido por elnumero de pıxeles.

Al comenzar a extender el rango de busqueda se pudo observar que la sucesion de losvalores de θ calculados para cada nivel, comenzaba a acercarse a un valor. Este compor-tamiento se observo en todas las repeticiones de todas las imagenes utilizadas. En algunoscasos se podıa observar que la sucesion demoraba un poco en estabilizarse, sin embargo, laconvergencia existıa en todas las curvas probadas.

La convergencia de la curva tiene un comportamiento bastante extrano, pues constan-temente aparecen unos saltos en el valor de la estimacion (ver Figura 5.12). Este compor-tamiento se atribuyo, en un principio, a un problema de aproximacion, pues se trabaja convalores bastante pequenos. Sin embargo, a pesar de ser pequenos, no se acercan aun a lazona donde ocurren ese tipo de problemas. Otra observacion que permite descartar la teorıa

51

anterior es que el comportamiento que se genera cuando hay problemas de aproximacionpor punto flotante es bastante mas erratico, a diferencia del comportamiento mostrado porla sucesion de estimadores, el cual es sumamente regular. La teorıa que mejor explica este“efecto serrucho” dice que al suavizar la curva con filtros cada vez mas fuertes, se deja detomar en cuenta puntos que, para filtros mas suaves, hacıan mas negativa la pendiente, y enconsecuencia, que el estimador fuera mas alto.

Si se considera un conjunto de puntos x1, . . . , xn los cuales forman parte de la mesetapara un σ fijo. El punto xn, a medida que σ es mas grande, empieza a disminuir su valor,por lo cual comienza a provocar una disminucion de la pendiente de la recta que se utilizapara estimar. Cuando un punto xn es mas pequeno que el primer punto de la curva, este dejade considerarse para la estimacion, por lo cual toda la influencia que tuvo sobre la recta sepierde y, en consecuencia, la pendiente de la recta aumenta su valor y el valor de la estimacionbaja, generando un salto. Para evitar los problemas que pueden acarrear estos salto en laestimacion se utilizo la sucesion de los maximos locales.

Figura 5.12: Ejemplo de la sucesion θσ

Al estabilizarse el comportamiento utilizando la sucesion de los maximos locales, labusqueda se enfoco en encontrar el valor al que converge dicha sucesion. Este problemaa simple vista es bastante similar al anterior, pues se debe buscar la desviacion estandar σpara el cual la curva alcanza un valor suficientemente cerca del valor al que converge. Sinembargo, existe una diferencia fundamental, pues en el caso de la busqueda del intervalo paradefinir un espacio de escala, el criterio venıa dado por el resultado real, a diferencia de labusqueda de θσ, donde se tiene varias caracterısticas que guıan la busqueda.

Como se menciono, el estimador de θ se basa en encontrar un conjunto de puntos quecomponen la meseta. Esta no necesariamente existe, pues puede ocurrir que la sucesionse torne monotonamente decreciente por efecto del suavizado, en cuyo caso se descarta el

52

primer punto sucesivamente hasta llegar al lımite definido previamente, con lo cual se decideque la meseta no existe y, en consecuencia, no se puede estimar θ. Este comportamientose observo cuando la desviacion estandar del filtro era mayor que un σ0, donde, segun losgraficos obtenidos, la sucesion termina. En estricto rigor, esta no acaba, pero se pudo observarque la diferencia entre los maximos locales consecutivos era suficientemente pequena. En lasimagenes utilizadas, θ era del orden de 10−6 y las diferencias encontradas fueron del ordende 10−9, lo cual, en terminos practicos, significa que la diferencia al estimar la cantidad deburbujas en la imagen es del orden de 0, 01 burbujas tal como se muestra en la Figura 5.13.

Figura 5.13: Diferencia entre maximos locales consecutivos

El unico problema restante fue como acercarse a ese punto, dado que no se sabe realmentecuan lejos esta. Este problema se puede resolver utilizando doubling search, tal como sehizo para la estimacion de los momentos. En este caso esta en presencia de una estructuraordenada, mas se puede modificar utilizando la informacion que nos da la estimacion de θ.Existen dos hechos empıricos que permitieron la creacion de un algortimo basado de doublingsearch para resolver el problema. El primero de ellos es que la sucesion de los maximos localesconverge, por lo tanto, la diferencia es cada vez menor y se puede imponer un ε como criteriode parada. El segundo hecho es que el estimador no existe a la derecha del σ para el cual sealcanza la convergencia.

La primera parte de esta variante de doubling search consistio en utilizar σ = 2i e intentarestimar θ hasta que no se pueda porque el estimador no exista. Se sabe que entre el valordonde ya no existe estimacion para θ y la potencia de 2 anterior se encuentra el valor quese busca. Luego, la segunda parte corresponde a una busqueda binaria en dicho rango. Elcriterio de parada fue que la diferencia entre dos valores consecutivos de la sucesion fueramenor a ε. Esta condicion se puede cumplir en ambas partes.

El valor obtenido con este algoritmo no es el mejor, pues siempre para algun σ intermedio

53

se obtiene el valor real, sin embargo, no es posible encontrar una caracterıstica que permitaidentificar aquel σ. A pesar de no ser el valor real, este se encuentra muy cerca, del valor real.

Es importante tambien mencionar que la implementacion de los filtros se hizo en el do-minio de la frecuencia, es decir, utilizando el teorema de convolucion, debido a que en eldominio espacial al tomar dos σ bastante cercanos no se puede obtener kernels distintos,esto por efectos de la discretizacion. Ergo, no se puede trabajar adecuadamente valores deσ cercanos. Ademas, en el dominio espacial, la convolucion depende de las dimensiones dela imagen y del kernel, por ende, para valores de σ grandes (el tamano del kernel aumentaa medida que aumenta la deviacion estandar σ del filtro gausiano) el rendimiento empeoraconsiderablemente, a diferencia de la convolucion en el dominio de la frecuencia donde elcosto de la convolucion no varıa con el valor de σ.

Al igual que con la estimacion de los momentos, no se puede determinar la complejidaddel algoritmo, pues no se pudo relacionar la forma de la curva o la velocidad de covergenciacon elementos caracterısticos, luego, no se sabe de que elementos depende la cantidad deiteraciones que se realizan para obtener el estimador.

5.4. Algoritmo

El metodo estocastico consta de tres parte. La primera de ellas es rescatar estadısticasutiles a partir de la imagen, esto consiste en obtener el avoiding functional. Esta etapa esla unica que necesita de la imagen, y, al trabajar con ella es costosa en tiempo y en uso dememoria. La segunda etapa consiste en obtener θ ·µk. En esta etapa se debe suavizar la curvaΨ′′(h) utilizando filtros gausianos para ası poder obtener buenos resultados. La tercera partecorresponde a la estimacion de θ, parametro necesario para poder despejas µk del resultadoque se obtiene al estimar los momentos. La primera etapa es necesaria para las dos siguientes,por lo tanto debe ser resuelta en primer lugar.

5.4.1. Procesamiento paralelo

El procesamiento paralelo en el metodo estocastico se utiliza solo en la primera tarea,es decir, para recoger las estadısticas que se necesitan de la imagen. En la seccion 5.1 seexplico como calcular el avoiding functional para cada distancia h utilizando las slices dePython.

Es importante destacar que los procesos livianos (threads) de Python se ejecutan secuen-cialmente, esto ocurre porque el interprete de Python serializa la ejecucion. Esto quiere decirque si se tiene una serie de threads, estos se reparten el tiempo que el sistema operativo leotorgo a Python, por lo tanto, no existe un paralelismo real. Sin embargo, existe el modulomultiprocessing de Python permite utilizar procesos pesados como si fueran procesos livianos,

54

es decir, el modulo provee una interfaz similar a la de los threads, pero por debajo, este modu-lo realiza la duplicacion del proceso, matar los procesos una vez terminada la ejecucion, entreotras operaciones. Los procesos pesados tienen la desventaja de no compartir memoria, sinembargo, existen mecanismos mediante los cuales se puede compartir memoria. El modulomultiprocessing provee tambien esta funcionalidad.

Para paralelizar la obtencion del avoiding functional lo que se hizo fue separar el calculopara cada h. Lo que se hizo fue crear una lista con los h que se deben calcular y se divide enpartes iguales, una para cada hilo. Cada hilo calcula el avoiding functional para los h que seles asignaron. La idea original fue crear un pool de procesos donde cada tarea, en este casoel calculo para cada h, tomara un procesador, ejecutara su tarea y, finalmente, devolvierael proceso al pool. Sin embargo, esta estrategia no puede ser utilizada cuando se necesitamemoria compartida.

55

Capıtulo 6

Resultados Obtenidos

En este capıtulo se muestran los resultados obtenidos para los experimentos que se re-alizaron. Los resultados se muestran por medio de graficos para hacer mas facil su com-prension. En caso de ser necesario se incluyen las tablas con las cuales se confeccionaron losgraficos, y ası complementar el analisis. El resto de las tablas se incluyen en los anexos.

El computador utilizado fue un laptop con un procesador Intel Core 2 Duo T7250 con dosprocesadores de 2 Ghz y 2 Gb de memoria RAM. El sistema operativo instalado es Ubuntu11.04 de 32 bits con el kernel 2.6.38.

6.1. Calidad de respuesta, tiempo de ejecucion y uso

de memoria v/s tamano de la imagen

Uno de los resultados interesantes que se puede obtener es la dependencia que existe entrela calidad de la respuesta, el tiempo de calculo y la memoria utilizada, respecto al tamano dela imagen de entrada. Para cada imagen se genero 10 imagenes con distintos tamanos. Lostamanos utilizados fueron multiplos de 150 en el lado mas largo y manteniendo la proporcionde 3:2 en el lado corto, es decir, 150x100, 300x200, 450x300 y ası hasta llegar a 1500x1000.Para cada imagen se obtuvo la estimacion y, posteriormente, se pondero por el factor deescala para esa imagen y ası tener todos los resultados en la misma resolucion para que lacomparacion tenga sentido. Por ejemplo, si se tiene una imagen im1 y otra im2, las dosprovenientes de la misma imagen original, donde im1 es de la mitad del tamano de im2.En ese caso los resultados no son comparables, pues el resultado depende del tamano dela imagen. Sin embargo, el factor de escala para ir de una otra es 2, ergo, si la estimacionobtenida de la imagen im1 se pondera por 2, este valor si puede compararse con el obtenido deim2. En este experimento solo se comparo el diametro, pues las 4 metricas que se comparanse comoportan de igual manera frente al cambio de resolucion. Se escogio el diametro por ser

56

la magnitud mas facil de ver.

El tamano original de la imagen es de 127x84.6 y es un archivo de autoCAD, con lasburbujas descritas por su centro y su radio. El diametro promedio para las burbujas de laimagen es de 35.382 pıxeles.

(a) Calidad de la respuesta: Error abso-luto v/s Tamano de la imagen.

(b) Tiempo de ejecucion: Tiempo v/sTamano de la imagen.

(c) Uso de memoria: Memoria utilizadav/s Tamano de la imagen.

Figura 6.1: Calidad de la respuesta, tiempo de ejecucion y memoria utilizada, para metodoclasico y metodo estocastico.

Los resultados desplegados en la Figura 6.1(a) muestran el error absoluto entre el diametroreal y la estimacion de este obtenida para ambos metodos. Lo primero que se puede observares que el metodo clasico tiene un error menor, ademas de ser mas estable. Esto se puede vercon las imagenes pequenas, para las cuales el error es alto, principalmente porque los tamanosse ven distorsionados por la baja resolucion, sin embargo, a medida que la imagen aumentade tamano este efecto comienza a disminuir y se estabiliza bastante rapido. En el caso delmetodo estocastico se tiene que el error siempre es mayor y cuesta mas que se estabilice. Estecomportamiento es producto de que al tener una imagen de mejor resolucion las estadısticascambian lo cual lleva a una estimacion distinta, ademas se debe considerar la fluctuacionestadıstica. Sin embargo, una diferencia de 3 pıxeles es un error del 10 % por lo cual siguesiendo un resultado satisfactorio.

Para el caso de los recursos utilizados, la Figura 6.1(b) muestra que la dependencia enel caso del metodo clasico es lineal respecto a la cantidad de pıxeles, lo cual es esperable,

57

pues para cada punto Watershed trabaja con los pıxeles vecinos. A diferencia de este ultimo,el metodo estocastico debe calcular el avoiding funcional, por lo tanto, debe revisar muchospıxeles y no solo con la vecindad inmediata de los puntos, de ahı su comportamiento super-lineal. La Figura 6.1(c) muestra el uso de memoria, cuyo comportamiento es similar paraambos casos, pues en ambos el gasto principal es tener la imagen en memoria. Es importantedestacar que esta prueba fue hecha sin utilizar procesamiento paralelo ni submuestreo en elcaso del metodo estocastico.

6.2. Python v/s C

Uno de los resultados importantes que se pudo obtener del trabajo realizado es la com-paracion entre Python y C, puesto que se menciono en varias ocasiones que incorporar piezasde codigo en C mejora el rendimiento. La comparacion se hizo para las tres situaciones quese explicito durante el trabajo, es decir, para la aplicacion de operaciones morfologicas, parala transformada de distancia y para Watershed.

Para las operaciones morfologicas se realizo dos pruebas. La operacion utilizada fue dilat-acion, aunque la erosion es muy similar y tambien hubiese podido ser utilizada. Las demasoperaciones se construyen en base a estas, por lo cual, el analisis sobre la dilatacion es ex-tensible a ellas. En la primera prueba se incremento el tamano del elemento estructuralpara poder establecer alguna dependencia con el tiempo de calculo. La imagen empleadafue de 1500x1000 pıxeles y los elementos estructurales usados fueron cırculo cuyos radioseran 3,6,9,12,15 y 18. En la segunda prueba se cambio el tamano de la imagen, dejando eltamano del elemento estructural fijo en 6 pıxeles. Los tamanos de las imagenes a las que seles aplico dilatacion fueron 150x100, 300x200, 450x300, 600x400, 750x500 y 900x600 pıxeles.

Tabla 6.1: Tabla de tiempo de ejecucion v/s tamano del elemento estructural, para dilatacionen Python y C

Tiempo [s]Radio elemento estructural [pıxeles] Python C

3 255.7 0.26 837.1 0.89 1737.5 1.712 2979.2 3.115 4562.0 4.718 6517.7 6.8

La Figura 6.2 muestra una diferencia de 3 ordenes de magnitud entre la implementacionhecha en Python y la hecha en C para la tecnica de dilatacion cuando se varıa el tamanodel elemento estructural, ademas se puede ver el comportamiento superlineal de esta op-eracion. En el caso de dilatacion cuando se varıa el tamano de la imagen, en la Figura 6.3,se puede ver que existe una diferencia de aproximadamente 3 ordenes de magnitud entre las

58

(a) Tiempo v/s Tamano del elemento estructuralen Python

(b) Tiempo v/s Tamano del elemento estructuralen C

Figura 6.2: Dilatacion: Grafico de Tiempo v/s Tamano del elemento estructural.

Tabla 6.2: Tabla de tiempo de ejecucion v/s tamano de la imagen, para dilatacion en Pythony C

Tiempo [s]Tamano imagen [pıxeles] Python C

150x100 9.951 0.011300x200 39.866 0.042450x300 90.460 0.094600x400 161.223 0.166750x500 251.921 0.262900x600 367.021 0.377

(a) Tiempo v/s Tamano de la imagen en Python (b) Tiempo v/s Tamano de la imagen en C

Figura 6.3: Dilatacion: Grafico de Tiempo v/s Tamano de la imagen para Dilatacion.

59

implementaciones en Python y C, en cuyo caso el crecimiento sigue una tendencia lineal.

El experimento para la transformada de distancia y para Watershed consistio en variar eltamano de la imagen. En ambos experimentos las dimensiones de lasimagenes fueron 150x100,300x200, 450x300, 600x400, 750x500 y 900x600 pıxeles.

Tabla 6.3: Tabla de tiempo de ejecucion v/s tamano de la imagen, para transformada dedistancia en Python y C con fuerza bruta, y propagacion en C

Tiempo [s]Tamano imagen [pıxeles] Python C fuerza bruta C propagacion

150x100 20.412 0.160 0.021300x200 99.863 0.988 0.135450x300 260.763 2.134 0.404600x400 533.815 4.320 0.909750x500 946.462 7.389 1.700900x600 1516.322 11.606 2.857

(a) Tiempo v/s Tamano de la imagen para Python (b) Tiempo v/s Tamano de la imagen para C

Figura 6.4: Transformada de distancia: Grafico de Tiempo v/s Tamano de la imagen.

Las implementaciones en C de la transformada de distancia presentan una mejora en unfactor 130, aproximadamente, frente a la implementacion en Python utilizando fuerza bruta,como se ve en la Figura 6.4. De los tiempos para las implementaciones en C, presentadosen la misma Figura se puede ver que ambas mantienen la tendencia levemente superlineal,siendo la implementacion utilizando la idea de propagacion la que tiene un tiempo 5 vecesmejor, sin embargo, esta diferencia es pequena en comparacion con la diferencia entre lasimplementaciones en C y la implementacion en Python.

Watershed tambien presenta mejoras las que se pueden ver en la Figura 6.5. En esta Figurase puede ver que el comportamiento es en ambos casos levemente superlineal. Ademas, lacurva obtenida con implementacion en Python tiene una curvatura mayor que la obtenidacon la implementacion en C, sin embargo, sigue siendo superlineal y la mejora sigue siendo

60

Tabla 6.4: Tabla de tiempo de ejecucion v/s tamano de la imagen, para Watershed en Pythony C

Tiempo [s]Tamano imagen [pıxeles] Python C

150x100 7.019 0.013300x200 91.306 0.048450x300 447.735 0.120600x400 1387.598 0.242750x500 3362.557 0.411900x600 6915.607 0.635

(a) Tiempo v/s Tamano de la imagen para Python (b) Tiempo v/s Tamano de la imagen para C

Figura 6.5: Watershed: Grafico de Tiempo v/s Tamano de la imagen.

a nivel de las constantes y no del orden del algoritmo. La razon de esta diferencia es que lasestructuras en C fueron hechas ad-hoc, a diferencia de Python donde se utilizo las estructurasgenericas que provee el lenguaje. Las estructuras de Python, al ser genericas, deben tenerciertos comportamientos, realizar operaciones o verificar condiciones que no son necesariasen el caso particular. Este costo adicional no existe en las estructuras ad-hoc creadas en C.

El mejor desempeno obedece a la eficiencia del lenguaje y en ningun caso a reduccionesen el orden de los algoritmos. Como es de esperarse, la implementacion en C es mucho maseficiente que la implementacion en Python, principalmente por ser un lenguaje mas cercanoal lenguaje de maquina, sin embargo, tiene una serie de desventajas a nivel practico. Algunasde estas desventajas son: tener que preocuparse de la memoria, pues el lenguaje no cuentacon mecanismos de recoleccion de basura y la gran cantidad de tiempo necesaria para losdesarrollos debido al bajo nivel.

61

6.3. Uso de recursos al utilizar procesamiento paralelo

en metodo clasico

Como se dijo menciono en la seccion 4.4, no se utilizo procesamiento paralelo para laseparacion de las burbujas, pues los algoritmos que la componen fueron implementados en C,y hacer una implementacion para multiprocesos en este lenguaje hubiese requerido bastantetiempo debido a su bajo nivel. La etapa siguiente, es decir, identificar las burbujas y calcularsu diametro sı fue hecha en paralelo. Esta tarea es muy pequena dentro del metodo, por locual es solo un apice de lo que se podrıa lograr. Sin embargo, fue implementada de todasmaneras, por lo que tambien se incluye un breve analisis al respecto.

(a) Grafico de Tiempo v/s cantidad dethreads para metodo clasico

(b) Grafico del uso de memoria v/s can-tidad de threads para metodo clasico

Figura 6.6: Comparacion de tiempos de ejecucion y uso de memoria para el metodo clasico

Los graficos de las Figuras 6.6(a) y 6.6(b) muestran los resultados obtenidos en el ex-perimento, en los cuales se puede ver una mejora, sin embargo, esta mejora es notoria soloal pasar de 1 thread a 2 threads, en adelante es imperceptible, incluso llegando a empeorara medida que aumenta la cantidad de procesos. La explicacion de este comportamiento, esque el tiempo utilizado en la coordinacion de los threads pasa a ser mayor que las mejo-ras obtenidas. El uso de memoria tiene el comportamiento esperado, pues se trabaja conprocesos pesados, ergo existe una serie de estructuras que deben replicarse, y, por lo tanto,ser mayor cuando hay mas procesos. Ademas, de la misma figura se puede observar que eluso de memoria aumenta solo en un 50 %, lo cual indica que no todo se duplica, es decir,los mecanismos utilizados para tener memoria compartida con procesos pesados realmentecomparten memoria y no es solo una interfaz.

62

6.4. Uso de recursos al utilizar procesamiento paralelo

en metodo estocastico

Dentro del metodo estocastico, especıficamente en el muestreo sobre la imagen, se separael calculo de T (K) para cada h, de esta manera cada thread realiza una parte del calculode forma paralela. Como se dijo anteriormente, el interprete de Python serializa los procesoslivianos, luego para utilizar tener procesamiento paralelo real se utiliza procesos pesados, locual afecta de la cantidad de memoria que utiliza el metodo. El experimento consistio en variarla cantidad de threads, de manera de poder observar como mejora el tiempo de ejecucion ycomo aumenta el uso de memoria.

(a) Grafico de Tiempo v/s cantidad dethreads para metodo metodo estocastico

(b) Grafico del uso de memoria v/s can-tidad de threads para metodo estocasti-co

Figura 6.7: Comparacion de tiempos de ejecucion y uso de memoria para metodo estocastico

Los resultados obtenidos se pueden ver en la Figura 6.7(a). Estos muestran el compor-tamiento esperado, es decir, que el tiempo disminuya, siendo cada vez menor el tiempo ahor-rado a medida que se agrega un threads mas. Este comportamiento es bueno, sin embargo,como se dijo recientemente, al utilizar procesos pesados se debe replicar varias estructurasen memoria, lo cual hace utilizar mayor cantidad de esta, tal como se aprecia en la Figura6.7(b). Por efectos del metodo utilizado para calcular el uso de memoria no se puede observaruna tendencia clara, sin embargo, lo que sı es claro es que a mayor cantidad de procesos,mayor cantidad de memoria utilizada. Como el tiempo de calculo es asintotico se opto porutilizar solo dos procesos, pues en adelante no es perceptible la mejora en tiempo y el usode memoria sube, se cree que con una tendencia lineal, pues existe ciertas estructuras quedeben ser replicadas a todos los procesos.

63

6.5. Dependencia de submuestreo en la calidad de la

respuesta

Como se menciono, en el metodo estocastico se utilizo un submuestreo sobre la imagenpara poder mejorar los tiempos de calculo, esto genera que el resultado no sea necesariamenteel mismo para dos ejecuciones con la misma imagen. A medida que el submuestreo utilizamenos datos se puede obtener resultados no tan buenos por la aleatoriedad del muestreo,sin embargo, esto no genera grandes cambios en el promedio, el cual se mantiene muy cercadel resultado utilizando toda la imagen. Durante el desarrollo del trabajo se noto el efectoanterior, a medida que el muestreo se hace mas pequeno el promedio no cambia, sin embargola varianza aumenta.

(a) Grafico de Tiempo v/s Tamano delsalto para estimacion de T (K)

(b) Grafico de la desviacion estandardel resultado final v/s Tamano del saltopara estimacion de T (K)

Figura 6.8: Comparacion de tiempos de ejecucion y desviacion estandar para estimacion deT (K)

En la Figura 6.8(a) se muestra como el tiempo de calculo disminuye ante la disminucionen el tamano del muestreo. El comportamiento es bastante esperable, pues pasar de nosaltarse ninguna fila a tomar fila por medio implica descartar la mitad de las filas y el tiempodisminuye considerablemente. Para valores mas grandes las diferencias son mucho menoresporque la diferencia relativa entre dos valores consecutivos no es tan perceptible como el losprimeros valores. Esto explica el comportamiento asintotico que presentan ambas curvas.

Para el caso de la varianza, en la Figura 6.8(b) se ve que esta aumenta de manera sublineal,este comportamiento es bastante bueno, pues permite utilizar saltos mayores sin un mayorcastigo, sin embargo, como se vio el la Figura 6.8(a), a medida que aumenta el tamano delsalto es menor la mejora en el tiempo de calculo.

64

6.6. Efectos de la cantidad de burbujas en la estimacion

Analizando los algoritmos se puede observar que el procesamiento hecho por el metodoclasico se aplica solo sobre las burbujas, por lo tanto, el tiempo que demore el algoritmodebe estar ligado a este factor. Con el objetivo de analizar este efecto se creo 14 conjuntos deimagenes, donde en cada uno se agruparon 10 imagenes que tienen una cantidad similar deburbujas. Cada uno de estos conjuntos fueron utilizados como entrada para ambos algoritmos.

El experimento arrojo dos resultados interesantes. El primero de ellos es el que se observaen la Figura 6.9, el cual muestra que a medida que aumenta la cantidad de burbujas, el sesgohacia las burbujas pequenas comienza a aumentar en el caso del metodo clasico. En dichaFigura se puede observar, con color rojo, el diametro promedio calculado directamente sobre laimagen para cada conjunto. El diametro obtenido por el metodo clasico corresponde a la curvade color azul, la cual se ve que comienza a subestimar cada vez mas el diametro promedio. Elmetodo estocastico, en color verde, sobreestima el diametro promedio, sin embargo, el error semantiene acotado. Este comportamiento tiene su origen en que a mayor cantidad de burbujas,la probabilidad de que se generen clusteres es mayor. Como se menciono en su momento, alseparar las burbujas con Watershed se genera una lınea, la cual no necesariamente coincidecon el borde real de la burbuja, y en consecuencia, la distancia entre el fondo y el pıxelcentral de la burbuja disminuye, subestimando ası el diametro de esta. El segundo resultadode interes, el cual se puede observar en la Figura 6.10, es la dependencia que existe entre elnumero de burbujas y el tiempo de calculo para el metodo clasico. Este comportamiento seexplica por la forma en que operan los algoritmos usados en el metodo clasico, pues estosrealizan un barrido sobre los pıxeles pertenecientes a las burbujas, por lo tanto, al aumentarla cantidad de burbujas en la imagen, estos barridos demoran mas.

(a) Diametro promedio v/s cantidad deBurbujas

(b) Error porcentual v/s cantidad deBurbujas

Figura 6.9: Diametro promedio y error porcentual v/s cantidad de burbujas en la imagen

65

Figura 6.10: Tiempo de calculo v/s cantidad de burbujas en la imagen

6.7. Experimento principal

El experimento disenado para comparar la calidad de la respuesta consistio en realizarun procesamiento individual sobre las imagenes dispuestas para esto. El objetivo de esteexperimento fue medir el error que comete cada uno de los metodos, para lo cual se dispusode la distribucion de burbujas por tamano.

Las imagenes utilizadas para este experimento corresponden a un conjunto de fotografıastomadas con bastante anterioridad al desarrollo de este trabajo. Estas imagenes fueron proce-sadas manualmente en autoCAD, donde se superpuso cırculos sobre las burbujas, de manerade poder obtener la distribucion de tamano por medio de los parametros de cada uno dedichos cırculos. Posteriormente, para cada imagen, la distribucion de cırculos fue dibujadaen un archivo JPEG, utilizando una librerıa incluida en los paquetes basicos de Python quepermite dibujar figuras geometricas y guardarlas en un archivo.

Para obtener el tiempo de calculo de ambos metodos se hace de la manera usual: seobtiene la diferencia entre el tiempo final y el tiempo inicial. Como este valor puede servariable por efecto de los otros procesos que se corren en el computador, se toma el promediode un numero fijo de ejecuciones. Para minimizar estos efectos tambien se utilizo el nivel deejecucion 2, es decir, el sistema operativo no utiliza servidor grafico ni tiene soporte de red,con esto disminuye la cantidad de procesos y, en consecuencia, la cantidad de interrupcionesa la ejecucion de las pruebas.

66

Para obtener la memoria utilizada por los metodos, se tuvo que hacer un proceso unpoco mas complicado. Se creo un monitor de memoria, el cual va registrando el tiempo delsistema y la cantidad de memoria utilizada. Este monitor se ejecuta antes de empezar y sedetiene despues de finalizar la ejecucion de las pruebas. Dentro de la prueba se registra eltiempo justo antes de comenzar y despues de finalizar su ejecucion. Con los tiempos de inicioy termino registrados, se busca en el archivo generado por el monitor de memoria, luego,el gasto de memoria es la diferencia entre los valores extremos del intervalo. Se intento uti-lizar herramientas de profiling, pero estas no arrojaban valores coherentes, pues los valoresobtenidos eran claramente menores que el tamano de la imagen, elemento mınimo necesariopara la operacion de ambos metodos. Al igual que con el tiempo de calculo, se calculo elpromedio de una serie de ejecuciones para aminorar los efectos de los demas programas quecorren en el computador.

Los resultados obtenidos (ver Tabla 6.5) en las pruebas realizadas con estos conjuntos defotos fueron bastante coherentes, sin embargo, existen dos aspectos que merecen ser analiza-dos. El primero de ellos es lo distintas que pueden llegar a ser dos mediciones (imagenes), esdecir, para ambos conjuntos (cada uno corresponde a una poblacion de burbujas distinta) setiene una diferencia de un 15 % entre el valor mas bajo y el mas alto. La segunda observacionsolo afecta al metodo estocastico, el cual, en general, presenta una tendencia al promedio,lo cual indica que al utilizar criterios estadısticos para estimar el diametro promedio, seconsidera la poblacion entera y no la muestra en particular.

Tabla 6.5: Resultados test pre-eliminarPrimer Conjunto Segundo Conjunto

Imagen Diametro promedio [pıxeles] Diametro promedio [pıxeles]Real Clasico Estocastico Real Clasico Estocastico

imagen 01 77.05 72.00 76.44 107.91 103.73 118.95imagen 02 78.06 77.46 78.81 106.27 91.12 116.18imagen 03 76.22 75.00 73.75 125.94 106.15 117.99imagen 04 78.46 77.51 84.57 119.36 105.01 128.96imagen 05 77.34 74.63 71.36 115.06 98.28 127.47imagen 06 71.89 69.86 72.30 112.99 76.96 127.18imagen 07 74.97 73.03 73.31 117.57 86.66 143.26imagen 08 68.70 67.17 69.75 105.74 96.66 102.34imagen 09 73.68 73.95 67.51 106.82 101.88 87.79imagen 10 68.72 69.16 65.77 117.22 111.09 110.33promedio 74.51 72.98 73.36 113.49 97.75 118.04

Las grandes variaciones que presentan ambos metodos podrıa ser atribuido a que losmetodos en realidad no son del todo buenos, sin embargo, a pesar de no poder descartar apriori esta opcion, la poca regularidad en las imagenes utilizadas desvıa la atencion haciaun problema de muestreo mas que un problema inherente a los metodos. Por este motivo sedecidio utilizar un muestreo mayor, es decir, realizar un procesamiento sobre varias imagenespara obtener las metricas y no sobre una imagen individual. De esta manera se busca tenerun mayor porcentaje de confianza sobre el valor considerado real.

67

El valor real que se utilizo para la comparacion con los metodos fueron las metricascalculadas sobre la lista de todas las burbujas en las imagenes, con este se tendra el valormas estable posible. Para el caso de los metodos, se analizara primero de cuantas imagenesdebe ser el muestreo para obtener estabilidad. Sin embargo, la informacion con la que secuenta no es suficiente para encontrar intervalos y porcentajes de confianza, por lo cual lamejor opcion que se tiene para intentar tener la misma seguridad en el resultado es hacerbuscar la cantidad de imagenes necesarias para que el resultado sea estable.

Las imagenes utilizadas en el experimento final fueron obtenidas en un laboratorio por otromemorista, cuyo trabajo consiste en buscar las condiciones que permitan obtener imagenesque cumplan los supuestos en los que se basa el metodo estocastico. Estas imagenes fueronsometidas al mismo trata

Para el experimento final se conto con un conjunto de 50 imagenes, con las cuales sehicieron grupos de 1, 2, 5, 10, 25 y 50 imagenes. Luego, sobre estos grupos se realizo unprocesamiento conjunto. En el caso del metodo clasico el proceso fue juntar las listas deburbujas para cada imagen y sobre esta nueva lista calcular los momentos. Para el metodoestocastico se obtuvo el avoiding functional para cada imagen y se calculo un promedio.La razon de realizar el promedio sobre el avoiding functional fue porque posteriormente secalcula el logaritmo de este, el cual distorsiona el error, pues no es un operador lineal.

Para el experimento se utilizo el metodo clasico con el procesamiento paralelo implementa-do, es decir, en la identificacion y la obtencion del diametro. En el caso del metodo estocasticose utilizo, procesamiento paralelo usando 2 procesos. Ademas se utilizo un submuestreo, elcual considero un quinto de la informacion disponible.

Los resultados obtenidos de realizar el procesamiento con el metodo clasico y el metodoestocastico se comaparon con los resultados obtenidos por el procesamiento manual hecho enautoCAD.

En las Figuras 6.11 y 6.12 se puede ver que las estimaciones, a medida que el grupocontiene mas imagenes, comienzan a ser mas certeras en el sentido que la diferencia entretodos los valores obtenidos no es tan grande como en los grupos pequenos. Sin embargo,existe un sesgo, el cual en el caso del metodo clasico corresponde a la separacion que serealiza sobre los clusteres. Esta separacion genera burbujas truncadas y, en consecuencia, suradio se ve disminuido. En el caso del metodo estocastico, los resultados sugieren que el sesgoproviene de que alguno de los supuestos no se cumple cabalmente. El supuesto que no puedeser verificado es el que dice que las posiciones de las burbujas se generaron con un procesode Poisson.

En cuanto al valor promedio obtenido, el metodo clasico muestra una leve superioridad,pues el error relativo es de aproximadamente un 5 %, la mitad del que muestra el metodoestocastico, el cual es de aproximadamente un 10 %. Sin embargo, el metodo estocastico aunse mantiene dentro de margenes aceptables. Ademas, se puede ver que para el d32, el error esmuy pequeno en comparacion a las otras metricas. Este resultado es sumamente bueno, pues

68

(a) Momento de orden 1 (b) Momento de orden 2

(c) Momento de orden 3 (d) d32

Figura 6.11: Resultados para metodo clasico

es esta metrica la que se utiliza en los modelos para la velocidad y eficiencia en la flotacion.Los resultados obtenidos para el d32 indican que la estimacion para θ no es buena, pues el d32es el cuociente entre el momento de tercer orden y el de segundo orden, luego θ no participadel resultado y por este motivo su error es menor.

Con respecto al tiempo, en la Figura 6.13(a) se ve que el metodo estocastico es mas rapido,pues utiliza aproximadamente un quinto del tiempo utilizado por el metodo clasico. Estediferencia se explica, en primera instancia, por el uso de procesamiento paralelo en el metodoestocastico, el cual se utiliza en una de las tarea mas intensiva. No ocurre ası con el metodoclasico, donde el procesamiento en paralelo es muy poco y en una tarea no muy intensivaen uso de recursos. Ademas de lo anterior, el metodo estocastico utilizo un submuestreo elcual afecta levemente la calidad de a respuesta, pero genera una mejora considerable. El usode memoria (ver Figura 6.13(b)) tambien se ve mejorado por el submuestreo utilizado en elmetodo estocastico, sin embargo, la diferencia no es tan notoria como en el caso del tiempode calculo.

69

(a) Momento de orden 1 (b) Momento de orden 2

(c) Momento de orden 3 (d) d32

Figura 6.12: Resultados para metodo estocastico

(a) Tiempo de calculo para metodoclasico y estocastico

(b) Memoria utilizada para metodoclasico y estocastico

Figura 6.13: Uso de recursos para metodo clasico y estocastico.

70

Capıtulo 7

Conclusiones

El trabajo desarrollado consistio en implementar el metodo estocastico. Este metodo,junto con el metodo clasico, el cual fue implementado anteriormente, se sometieron a ex-perimentos con el objetivo de realizar una comparacion entre ellos. Estos metodos recibencomo entrada una imagen en blanco y negro con objetos circulares, en este caso burbujas,cuyo interior debe estar relleno. La salida de estos algoritmos son los momentos de primer,segundo y tercer orden de la distribucion de burbujas por diametro.

La comparacion entre estos metodos consistio en 3 aspectos. El primero corresponde a lacalidad de la respuesta. Para esto se comparo los momentos de orden 1, 2, 3 y el diametrode Sauter, el cual relaciona el volumen de una burbuja con el area de su superficie. Esteindicador esta ligado directamente con la velocidad y eficiencia de la flotacion, un procesode gran interes en el area de la metalurgia extractiva y que motivo este trabajo. El segundoaspecto de la comparacion entre los metodos mencionados fue el tiempo de calculo y el tercerofue la memoria utilizada. Ademas se realizaron experimentos adicionales para verificar ciertoscomportamientos que se infirieron durante el trabajo realizado.

Entre los aspectos que no fueron abordadosen esta memoria esta paralelizar la seg-mentacion en el metodo clasico. La segmentacion en el metodo tradicional fue implementadaen C y paralelizarla hubiese tomado mucho tiempo. Como se sabe, C es un lenguaje de bajonivel, por lo cual la programacion concurrente es bastante mas compleja que en otros lengua-jes y por lo tanto requiere mas tiempo. Las ideas que no se lograron desarrollar quedaroncomo propuestos, sin embargo, estas escapaban del alcance de este trabajo.

Los resultados mostraron que ambos metodos obtienen buenos estimadores para lasimagenes de prueba, obtenidas en condiciones de laboratorio. Siendo mas especıfico, parael metodo clasico se obtuvo un error relativo menor al 5 % para los momentos de primer, se-gundo y tercer orden, que es aproximadamente el doble del que obtuvo el metodo estocastico,el cual se mantuvo aproximadamente en un 10 %. Sin embargo, el resultado obtenido con elmetodo clasico depende de la cantidad de burbujas en la imagen. Esto ocurre porque a medi-

71

da que la imagen tiene mas burbujas la probabilidad de que estas formen clusteres es mayory, en consecuencia, los efectos de la separacion de los clusteres comienza a notarse cada vezmas. Es importante resaltar que el error relativo en la estimacion del diametro de Sauter esde aproximadamente un 4 % en el peor caso para ambos metodos.

Para el tiempo de calculo, los resultados obtenidos mostraron una gran diferencia entre losmetodos, siendo el tiempo de calculo para el metodo estocastico un quinto del utilizado por elmetodo clasico. Esto se debe a que el metodo estocastico usa procesamiento paralelo, ademasse puede reducir la cantidad de informacion que se utiliza para obtener las estadısticas, locual tambien impacta, favorablemente, el tiempo de calculo.

El uso de memoria es bastante similar en ambos metodos, lo cual se debe a que mantenerla imagen en memoria es el gasto mas importante. La diferencia a favor del metodo estocasticose debe a que este utiliza la imagen solo para obtener las estadısticas y en el resto de lasoperaciones trabaja con vectores, lo cual requiere menos memoria.

El analisis global de las tres aristas que comprendio la comparacion muestra que el metodoestocastico, a pesar de generar una estimacion con un error mayor, es mas estable frente ala cantidad de burbujas en la imagen, lo cual lo hace mas confiable que el metodo clasico.Ademas de lo anterior, el metodo estocastico permite realizar una estimacion con menosinformacion de la disponible en las imagenes, lo cual hace que el tiempo de calculo y el usode memoria se pueda disminuir en caso de ser necesario. Es importante tambien destacar quela estimacion del diametro de Sauter hecha por el metodo estocastico tiene un error menoral 5 %, a diferencia de lo que ocurre con los momentos de primer, segundo y tercer orden porseparado, los cuales estan cerca del 10 %. Esto ultimo, junto con la posibilidad de disminuirel tiempo y uso de memoria en funcion de los recursos disponibles, es de gran utilidad decara al desarrollo de herramientas computacionales de apoyo al proceso de flotacion.

Un hecho conocido es el impacto que tiene la expresividad de un lenguaje sobre elrendimiento de este. Este impacto genera que el tiempo de calculo para Python sea bas-tante mayor que el obtenido en C, incluso en operaciones basicas. La expresividad de unlenguaje de alto nivel se transforma en un conjunto de instrucciones de maquina mucho may-or que el que genera un lenguaje de bajo nivel. Sin embargo, es importante resaltar que laposibilidad de ejecutar piezas de codigo en C, permite disminuir la perdida en rendimiento.Esto hace que Python, a pesar de su eleccion hacia la expresividad por sobre el rendimiento,pueda ser utilizado en aplicaciones cientıficas pesadas, pues la alternativa antes mencionadaminimiza el impacto.

las lıneas de trabao que se desprenden de esta memoria son dos. La primera de ellas, la demayor envergadura, es buscar mejorar los algoritmos de estimacion del tamano de burbujay el uso de recursos de estos por medio de tecnicas estadısticas mas elaboradas, como porejemplo: obtener sub-imagenes desde la imagen original para tener un muestreo mas pequeno,superponer imagenes para disminuir la cantidad de calculos sin perder demasiada informaciono rotar y superponer imagenes para eliminar sesgos espaciales. La segunda lınea es paralelizarla segmentacion del metodo clasico.

72

Bibliografıa

[1] Beucher, S. The watershed transformation applied to image segmentation. In ScanningMicroscopy International (1991), pp. 299–314.

[2] Dekker, A. H. Kohonen neural networks for optimal colour quantization. Network:Computation in Neural Systems 5, 3 (1994), 351–367.

[3] Egana, A. Diffusion-based filtering. Tech. rep., ALGES, Dec. 2010.

[4] Emery, X., Kracht, W., Egana, A., and Garrido, F. Using two-point set statisticsto estimate the diameter distribution in boolean models with circular grains. ImageAnalysis & Stereology, submitted. (2011).

[5] Fabbri, R., Costa, L. D. F., Torelli, J. C., and Bruno, O. M. 2d euclideandistance transform algorithms: A comparative survey. ACM Comput. Surv. 40 (February2008), 2:1–2:44.

[6] Gonzalez, R. C., and Woods, R. E. Digital Image Processing (3rd Edition). Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 2006.

[7] Kracht, W. Apuntes del curso concentracion de minerales (mi52e), 2010-02.

[8] Russ, J. C. Image Processing Handbook, Fourth Edition. CRC Press, Inc., Boca Raton,FL, USA, 2002.

73

Anexos A

Tablas

Tabla A.1: Error absoluto v/s tamano de la imagen. El error esta medido en funcion de laimagen original de 127x84.6 (AutoCAD)

Error absoluto [pıxeles] Error absoluto [pıxeles]Watershed Estocastico

Tamano de la imagen [pıxeles] Imagen 1 Imagen 2 Imagen 1 Imagen 2

100x150 0.268 0.161 - -200x300 0.264 0.229 - -300x450 0.135 0.060 2.559 -400x600 0.090 0.048 2.922 3.030500x750 0.068 0.021 3.066 3.025600x900 0.050 0.014 3.130 3.010700x1050 0.049 0.007 3.006 2.956800x1200 0.045 0.001 2.968 2.821900x1350 0.030 0.006 2.962 2.8061000x1500 0.035 0.016 2.851 2.8551100x1650 0.041 0.008 2.750 2.8501200x1800 0.044 0.028 2.687 2.8901300x1950 0.038 0.035 2.683 2.8661400x2100 0.042 0.006 2.703 2.9181500x2250 0.035 0.007 2.755 2.9251600x2400 0.040 0.033 2.727 2.9631700x2550 0.039 0.036 2.749 2.884

74

Tabla A.2: Tiempo de calculo v/s tamano de la imagenTiempo [s]

Tamano de la imagen [pıxeles] Watershed Estocastico

100x150 0.016 0.179200x300 0.084 0.342300x450 0.265 0.746400x600 0.517 1.510500x750 0.870 2.352600x900 1.334 3.825700x1050 1.918 6.221800x1200 2.637 8.910900x1350 3.517 12.3261000x1500 4.580 16.166

Tabla A.3: Memoria utilizada v/s tamano de la imagenMemoria utilizada [MB]

Tamano de la imagen [pıxeles] Watershed Estocastico

500x750 4.286 7.459600x900 7.483 11.270700x1050 13.336 15.815800x1200 16.961 21.563900x1350 22.975 27.3001000x1500 28.295 34.5071100x1650 34.608 42.2331200x1800 42.066 50.6761300x1950 49.607 59.4111400x2100 59.375 69.366

Tabla A.4: Tabla de tiempo de calculo y uso de memoria v/s cantidad de threads paralelosen metodo estocastico, para imagenes de 1500x1000 pıxeles

Cantidad de threads Tiempo [s] Memoria utilizada [MB]

1 6.765 46.6152 5.497 78.5473 5.483 104.3834 5.483 130.9005 5.521 165.7896 5.517 186.4357 5.557 221.5828 5.546 262.8689 5.569 279.94710 5.612 311.172

75

Tabla A.5: Tabla de tiempo de calculo y uso de memoria v/s cantidad de threads paralelosen metodo estocastico, para imagenes de 1500x1000 pıxeles

Cantidad de threads Tiempo [s] Memoria utilizada [MB]

1 10.119 24.4022 8.290 29.2083 7.738 36.8804 7.451 39.0895 7.281 40.2806 7.158 45.6337 7.088 49.0638 7.028 59.9869 6.984 70.37110 6.949 72.226

Tabla A.6: Tabla de tiempo de ejecucion v/s tamano del muestreo para avoiding functional,para imagenes de 1500x1000 pıxeles

Tiempo [s]Tamano del salto [pıxeles] 1 proceso 2 procesos

1 57.406 43.2102 45.858 20.4573 34.027 13.5554 26.740 10.2465 14.593 8.2866 12.075 6.9417 10.482 5.9848 9.095 5.2379 7.953 4.70610 7.299 4.21911 6.576 3.93212 5.875 3.54813 5.493 3.30314 5.103 3.05915 4.706 2.85216 4.403 2.70417 4.051 2.55518 3.791 2.44619 3.487 2.31220 3.429 2.207

76

Tabla A.7: Tabla de desviacion estandar del resultado v/s tamano del muestreo para avoidingfunctional, para imagenes de 1500x1000 pıxeles

Tamano del salto [pıxeles] Desviacion Estandar [pıxeles]

1 0.0002 0.7773 0.9144 1.1125 1.0746 1.0337 1.2188 1.3309 1.33110 1.34211 1.42812 1.45313 1.49814 1.60015 1.66916 1.67217 1.70118 1.69419 1.74820 1.768

Tabla A.8: Resultado obtenido para imagenes con distintas cantidades de burbujas, paraimagenes de 1500x1000 pıxeles

Cantidad promedio Diametro [pıxeles]de burbujas Real Watershed Estocastico

34,9 78,48 71,99 84,6444,3 79,84 74,46 84,9952,7 80,32 74,32 86,3962,0 80,19 72,07 86,2370,8 79,31 71,63 86,5177,5 79,88 71,13 82,9286,3 79,54 69,88 86,8697,9 79,89 71,07 87,17106,4 79,96 70,64 83,27115,9 79,20 69,47 83,01123,6 80,70 68,88 86,20133,1 79,84 69,89 87,16143,3 79,25 68,57 83,79149,2 79,73 67,09 82,98

77

Tabla A.9: Tiempo de calculo para imagenes con distintas cantidades de burbujas, paraimagenes de 1500x1000 pıxeles

Cantidad promedio Tiempo [s]de burbujas Watershed Estocastico

34.9 8.20 10.2844.3 10.75 9.9552.7 12.94 10.8062.0 15.43 9.7770.8 17.51 10.2777.5 19.16 10.8886.3 24.14 9.9997.9 26.40 9.11106.4 30.51 9.89115.9 35.85 9.35123.6 37.03 10.34133.1 41.51 10.82143.3 43.29 9.49149.2 47.41 9.40

Tabla A.10: Mınimo, promedio y maximo de las estimaciones de µ1 para Watershed v/stamano del grupo

Tamano de Momento de orden 1 (Watershed)los grupos Mınimo [pıxeles] Promedio [pıxeles] Maximo [pıxeles]

1 47.15 51.97 58.422 47.78 51.99 55.965 49.67 51.88 53.4610 50.23 51.87 53.1225 50.92 51.89 52.8650 51.86 51.86 51.86


Tamano de Momento de orden 2 (Watershed)los grupos Mınimo [pıxeles2] Promedio [pıxeles2] Maximo [pıxeles2]

1 2422.00 3026.35 3931.202 2534.31 3029.25 3537.445 2830.01 3017.47 3209.8010 2849.75 3015.55 3124.9625 2898.96 3018.04 3137.1150 3014.45 3014.45 3014.45

78


Tamano de Momento de orden 3 (Watershed)los grupos Mınimo [pıxeles3] Promedio [pıxeles3] Maximo [pıxeles3]

1 133957.67 195051.10 299430.892 149580.19 195267.77 250921.635 177890.82 194125.43 213904.4410 180620.74 193871.12 208614.2725 182067.79 194228.54 206389.2950 193862.29 193862.29 193862.29

Tabla A.13: Mınimo, promedio y maximo de las estimaciones de d32 para Watershed v/stamano del grupo

Tamano de d32 (Watershed)los grupos Mınimo [pıxeles3/2] Promedio [pıxeles3/2] Maximo [pıxeles3/2]

1 133957.67 195051.10 299430.892 149580.19 195267.77 250921.635 177890.82 194125.43 213904.4410 180620.74 193871.12 208614.2725 182067.79 194228.54 206389.2950 193862.29 193862.29 193862.29

Tabla A.14: Mınimo, promedio y maximo de las estimaciones de µ1 para metodo estocasticov/s tamano del grupo

Tamano de Momento de orden 1 (Estocastico)los grupos Mınimo [pıxeles] Promedio [pıxeles] Maximo [pıxeles]

1 46.55 58.21 69.432 53.66 57.35 68.925 53.47 57.89 64.0810 55.88 57.67 60.1925 58.28 58.93 59.5850 57.38 57.38 57.38

79


Tamano de Momento de orden 2 (Estocastico)los grupos Mınimo [pıxeles2] Promedio [pıxeles2] Maximo [pıxeles2]

1 2544.70 3538.00 4995.592 2889.13 3480.97 4717.155 2995.13 3428.32 4071.8810 3284.34 3454.21 3602.3225 3507.94 3530.42 3552.9150 3459.37 3459.37 3459.37


Tamano de Momento de orden 3 (Estocastico)los grupos Mınimo [pıxeles3] Promedio [pıxeles3] Maximo [pıxeles3]

1 131709.85 230088.55 428116.772 158847.34 228891.26 347293.415 167014.09 218308.55 281814.2610 195729.22 223696.94 247575.5325 213468.44 223385.32 233302.1950 226091.24 226091.24 226091.24

Tabla A.17: Mınimo, promedio y maximo de las estimaciones de d32 para metodo estocasticov/s tamano del grupo

Tamano de d32 (Estocastico)los grupos Mınimo [pıxeles3/2] Promedio [pıxeles3/2] Maximo [pıxeles3/2]

1 50.63 62.10 86.392 55.56 63.07 79.575 57.59 62.75 74.9610 58.42 64.19 72.3725 61.29 64.37 67.4550 65.79 65.79 65.79

80

universidad de chile facultad de ciencias...

Documents