Self-organizing cultured neural networks: Image analysis techniques for longitudinal tracking and modeling of the underlying network structure

Esta tesis estudia la evolución estructural de conjuntos de neuronas como la capacidad de auto-organización desde conjuntos de neuronas separadas hasta que forman una red (clusterizada) compleja. Esta tesis contribuye con el diseño e implementación de un algoritmo no supervisado de segmentación basado en grafos con un coste computacional muy bajo. Este algoritmo proporciona de forma automática la estructura completa de la red a partir de imágenes de cultivos neuronales tomadas con microscopios de fase con una resolución muy alta. La estructura de la red es representada mediante un objeto matemático (matriz) cuyos nodos representan a las neuronas o grupos de neuronas y los enlaces son las conexiones reconstruidas entre ellos. Este algoritmo extrae también otras medidas morfológicas importantes que caracterizan a las neuronas y a las neuritas. A diferencia de otros algoritmos hasta el momento, que necesitan de fluorescencia y técnicas inmunocitoquímicas, el algoritmo propuesto permite el estudio longitudinal de forma no invasiva posibilitando el estudio durante la formación de un cultivo. Además, esta tesis, estudia de forma sistemática un grupo de variables topológicas que garantizan la posibilidad de cuantificar e investigar la progresión de las características principales durante el proceso de auto-organización del cultivo. Nuestros resultados muestran la existencia de un estado concreto correspondiente a redes con configuracin small-world y la emergencia de propiedades a micro- y meso-escala de la estructura de la red. Finalmente, identificamos los procesos físicos principales que guían las transformaciones morfológicas de los cultivos y proponemos un modelo de crecimiento de red que reproduce el comportamiento cuantitativamente de las observaciones experimentales. ABSTRACT The thesis analyzes the morphological evolution of assemblies of living neurons, as they self-organize from collections of separated cells into elaborated, clustered, networks. In particular, it contributes with the design and implementation of a graph-based unsupervised segmentation algorithm, having an associated very low computational cost. The processing automatically retrieves the whole network structure from large scale phase-contrast images taken at high resolution throughout the entire life of a cultured neuronal network. The network structure is represented by a mathematical object (a matrix) in which nodes are identified neurons or neurons clusters, and links are the reconstructed connections between them. The algorithm is also able to extract any other relevant morphological information characterizing neurons and neurites. More importantly, and at variance with other segmentation methods that require fluorescence imaging from immunocyto- chemistry techniques, our measures are non invasive and entitle us to carry out a fully longitudinal analysis during the maturation of a single culture. In turn, a systematic statistical analysis of a group of topological observables grants us the possibility of quantifying and tracking the progression of the main networks characteristics during the self-organization process of the culture. Our results point to the existence of a particular state corresponding to a small-world network configuration, in which several relevant graphs micro- and meso-scale properties emerge. Finally, we identify the main physical processes taking place during the cultures morphological transformations, and embed them into a simplified growth model that quantitatively reproduces the overall set of experimental observations.

Self-organizing cultured neural networks: Image analysis techniques for longitudinal tracking and modeling of the underlying network structure (versión actualizada)

Esta tesis estudia la evolución estructural de conjuntos de neuronas como la capacidad de auto-organización desde conjuntos de neuronas separadas hasta que forman una red (clusterizada) compleja. Esta tesis contribuye con el diseño e implementación de un algoritmo no supervisado de segmentación basado en grafos con un coste computacional muy bajo. Este algoritmo proporciona de forma automática la estructura completa de la red a partir de imágenes de cultivos neuronales tomadas con microscopios de fase con una resolución muy alta. La estructura de la red es representada mediante un objeto matemático (matriz) cuyos nodos representan a las neuronas o grupos de neuronas y los enlaces son las conexiones reconstruidas entre ellos. Este algoritmo extrae también otras medidas morfológicas importantes que caracterizan a las neuronas y a las neuritas. A diferencia de otros algoritmos hasta el momento, que necesitan de fluorescencia y técnicas inmunocitoquímicas, el algoritmo propuesto permite el estudio longitudinal de forma no invasiva posibilitando el estudio durante la formación de un cultivo. Además, esta tesis, estudia de forma sistemática un grupo de variables topológicas que garantizan la posibilidad de cuantificar e investigar la progresión de las características principales durante el proceso de auto-organización del cultivo. Nuestros resultados muestran la existencia de un estado concreto correspondiente a redes con configuracin small-world y la emergencia de propiedades a micro- y meso-escala de la estructura de la red. Finalmente, identificamos los procesos físicos principales que guían las transformaciones morfológicas de los cultivos y proponemos un modelo de crecimiento de red que reproduce el comportamiento cuantitativamente de las observaciones experimentales. ABSTRACT The thesis analyzes the morphological evolution of assemblies of living neurons, as they self-organize from collections of separated cells into elaborated, clustered, networks. In particular, it contributes with the design and implementation of a graph-based unsupervised segmentation algorithm, having an associated very low computational cost. The processing automatically retrieves the whole network structure from large scale phase-contrast images taken at high resolution throughout the entire life of a cultured neuronal network. The network structure is represented by a mathematical object (a matrix) in which nodes are identified neurons or neurons clusters, and links are the reconstructed connections between them. The algorithm is also able to extract any other relevant morphological information characterizing neurons and neurites. More importantly, and at variance with other segmentation methods that require fluorescence imaging from immunocyto- chemistry techniques, our measures are non invasive and entitle us to carry out a fully longitudinal analysis during the maturation of a single culture. In turn, a systematic statistical analysis of a group of topological observables grants us the possibility of quantifying and tracking the progression of the main networks characteristics during the self-organization process of the culture. Our results point to the existence of a particular state corresponding to a small-world network configuration, in which several relevant graphs micro- and meso-scale properties emerge. Finally, we identify the main physical processes taking place during the cultures morphological transformations, and embed them into a simplified growth model that quantitatively reproduces the overall set of experimental observations.

Identificación de áreas prioritarias para la conservación de razas de maíz en la sierra de Ecuador

En Ecuador el maíz es el cultivo más importante en superficie y es base de la alimentación para la población rural que vive en los Andes. A diferencia de lo que sucede en la Costa, en la región Sierra todavía se cultivan numerosas variedades tradicionales que se agrupan en veinticuatro razas. Mantener esta diversidad es, pues, de gran importancia no solo para la seguridad alimentaria, sino también como fuente de genes para tolerancia a factores abióticos que podrían ser incorporados a las variedades modernas. Si bien parte de esta diversidad fue recolectada a mediados del siglo pasado y está siendo conservada en distintos bancos de germoplasma, es deseable que su conservación in situ también esté asegurada, entre otras razones, porque de esta manera el cultivo puede seguir evolucionando. Para poder implementar un plan de conservación en finca que contribuya a preservar este patrimonio, resulta imprescindible identificar áreas idóneas donde concentrar los recursos y conocer las características y tipologías de los agricultores que manejan la diversidad actual. Generar esta información es el objetivo principal de esta investigación y para lograrlo se han llevado a cabo cuatro estudios: (1) Análisis de la diversidad a nivel de razas e identificación de áreas de alta riqueza de razas, alta diversidad morfológica y/o alta diversidad ecogeográfica en la Sierra de Ecuador, (2) Identificación del perfil y las características de los agricultores que conservan y manejan las variedades tradicionales de maíz en la Sierra de Ecuador, (3) Análisis del conocimiento local, manejo y usos de variedades tradicionales de maíz en la Sierra de Ecuador, y (4) Identificación de áreas de alta diversidad y bajo riesgo de pérdida para la conservación en finca de maíz en la Sierra de Ecuador. Para el primer estudio se visitaron 303 fincas distribuidas a lo largo de la Sierra y se recolectaron 636 muestras que fueron caracterizadas morfológicamente mediante 14 variables: 8 relacionadas con la mazorca (forma, longitud y diámetro de la mazorca, color y diámetro de olote y número y disposición de hileras) y 7 referidas el grano (número total de granos, color, forma, longitud, anchura y grosor de grano y tipo de endospermo). Adicionalmente, las fincas donde se tomaron las muestras fueron caracterizadas ecogeográficamente mediante 5 variables climáticas (temperatura media estacional, rango de temperatura media anual, temperatura mínima de diciembre, precipitación estacional y precipitación de octubre), 2 geofísicas (altitud y pendiente) y 5 edáficas (textura principal del suelo, profundidad a roca, pH, contenido en materia orgánica y fertilidad). A partir de esta información y mediante técnicas de sistemas de información geográfica (SIG), se generaron mapas de distribución por raza en formato vectorial y un mapa de riqueza de razas, un mapa de diversidad morfológica y un mapa de diversidad ecogeográfica en formato ráster con celdas de 10 km x 10 km. Los resultados permitieron constatar que, en los últimos 60 años, no se ha perdido ninguna raza. Sin embargo, Canguil, Chaucho y Clavito han dejado de cultivarse en algunas provincias con la consiguiente erosión genética del cultivo. La caracterización morfológica detectó diferencias en el grado de variabilidad intra-raza, siendo Patillo Ecuatoriano, Racimo de Uva y Uchima las razas más heterogéneas tanto para los caracteres cualitativos como cuantitativos. A nivel climático y geofísico, también se detectaron diferencias en el grado de variación intra-raza; Cuzco Ecuatoriano, Kcello Ecuatoriano y Montaña Ecuatoriana fueron las razas que en promedio presentaron mayores rangos y coeficientes de variación para estas variables ecogeográficas. En cuanto a las condiciones edáficas todas las razas, excepto Cónico Dentado, presentaron una gran heterogeneidad, pudiendo crecer tanto en suelos ricos como pobres, con valores de pH entre ácido y moderadamente alcalino. La comparación entre razas reveló diferencias significativas en los rangos ambientales de algunas razas como Cónico Dentado, que tiende a cultivarse a menor altitud y, por tanto, en ambientes menos fríos y de mayor precipitación que Blanco Blandito, Patillo Ecuatoriano, Sabanero Ecuatoriano, Uchima y Zhima. Para la mayoría de las razas se encontraron materiales potencialmente adaptados a condiciones de estrés (precipitación estacional inferior a 500 mm y suelos con pH entre 4.5 y 5.5). Finalmente, los mapas de riqueza, de diversidad morfológica y de diversidad ecogeográfica mostraron 36 celdas de alta diversidad repartidas en las 10 provincias de la Sierra: 11 celdas en las provincias del norte, 11 en las provincias del centro y 14 en las provincias del sur. Para la caracterización e identificación de las tipologías de los agricultores que cultivan maíz en la Sierra de Ecuador y el análisis de los posibles factores de riesgo de pérdida de diversidad, se realizaron entrevistas individuales y semiestructuradas a los agricultores dueños de las fincas donde se recolectaron las muestras para el estudio de diversidad (254 en total). Las preguntas que se formularon (11 abiertas y 5 cerradas) estuvieron organizadas en seis bloques: datos del agricultor, características de la finca, diversidad y conocimiento del cultivo, manejo del cultivo, usos y flujo de semillas. Los resultados indicaron que la diversidad de maíz que hay en la Sierra de Ecuador es manejada mayoritariamente por agricultores mestizos, de entre 30 y 55 años, que cultivan una o dos variedades tradicionales para autoconsumo, en parcelas de menos de 0.5 ha y en asocio con fréjol. El análisis de segmentación mediante el algoritmo Chi-square automatic interaction detection (CHAID) permitió identificar un pequeño grupo de agricultores indígenas con parcelas medianas (entre 0.5 ha y 1.5 ha) que conservan un mayor número de variedades tradicionales por finca que el agricultor promedio. Los análisis estadísticos no detectaron diferencias significativas entre etnias (mestizo vs. indígena), géneros (hombre vs. mujer) y grupos de edad (jóvenes menores de 30 años, adultos entre 30 y 55 años y adultos mayores de 55 años) en lo que respecta al conocimiento del cultivo (criterios de reconocimiento y razones de preferencia) y manejo (tipo de cultivo), pero sí detectaron diferencias entre regiones, principalmente en el modo de cultivar el maíz; mientras que en el norte y sur tienden a sembrarlo en asocio y con un mayor número de especies, en el centro acostumbran a cultivarlo preferentemente solo. En cuanto a los usos, se recopilaron hasta 39 modos diferentes de consumir maíz, siendo Kcello Ecuatoriano y Zhima las razas para las que se registró un mayor número de usos. La comparación del número medio de usos por variedad entre etnias evidenció que los agricultores mestizos utilizan sus variedades tradicionales de forma más variada que los indígenas. Entre los factores de riesgo que se analizaron, el bajo porcentaje de jóvenes agricultores que se ocupan de las fincas podría suponer una amenaza a medio plazo por falta de relevo generacional. Adicionalmente, las numerosas sinonimias y homonimias que se detectaron y el bajo intercambio de semillas también podrían ser causa de pérdida de diversidad, bien por reemplazo o por envejecimiento de la semilla. Finalmente, se concluyó que las razas Chaucho, Complejo Chillo-Huandango, Complejo Mishca-Huandango, Cónico Dentado, Montaña Ecuatoriana y Sabanero Ecuatoriano son particularmente vulnerables, no solo por su baja presencia, sino también por el color de grano que tienen (los mismos que la mayoría de las razas más comunes) y carecer de nombres y usos específicos. Finalmente, para la priorización de áreas de conservación en finca para maíz en la Sierra de Ecuador, se utilizaron 13 criterios de diferente naturaleza: 2 ecogeográficos (precipitación, diversidad ecogeográfica), 6 biológicos (grado de presencia del cultivo, riqueza de razas, diversidad morfológica, presencia de mezclas, presencia de razas locales y riesgo de erosión genética), 3 culturales (abundancia de variedades por finca, diversidad de usos y frecuencia de intercambio) y 2 demográficos (tamaño de la población y distancia a núcleos urbanos). Mediante técnicas SIG y de evaluación multicriterio, los valores originales de las capas-criterio fueron transformados a una escala de 0 a 100. Posteriormente, las capas-criterio normalizadas fueron sumadas utilizando tres métodos de ponderación: (1) mismo peso, (2) diferente peso según la puntuación otorgada por 72 expertos, y (3) diferente peso según el método de comparación entre pares de criterios. Los resultados permitieron identificar ocho celdas de 10 km x 10 km con alta puntuación (> 65): tres celdas en el norte (una en cada una de las provincias), una celda en el centro (en la provincia de Cotopaxi), y cuatro celdas en la región sur (dos en Azuay y otras dos en Loja). ABSTRACT In Ecuador, the maize is the most important cultivation in surface and it is a base of the feeding for the rural population who lives in the Andes. In contrast to what it happens on the Coast, in the Sierra region still there are cultivated numerous traditional varieties that are grouped into twenty-four races. Maintaining this diversity is, therefore, of great importance not only for food security, but also as a source of genes for tolerance to abiotic factors could be incorporated into modern varieties. Although part of this diversity was collected in the middle of the last century and is still preserved in various germplasm banks, it is desirable for the in situ conservation also is assured, among other reasons, because in this way the crop can continue to evolve. To be able to implement a conservation plan on farm that contribute to preserving this heritage, it is essential to identify suitable areas where to concentrate resources and know the characteristics and typology of farmer who managed the current diversity. To generate this information is the main target of this investigation and to achieve this, four studies have been carried out: (1) Analysis of the diversity at races and identification of areas of high richness of races, high morphological diversity and / or ecogeographical high diversity in the Sierra of Ecuador, (2) Identification of the profile and characteristics of farmers who conserve and manage traditional varieties of maize in the Sierra of Ecuador, (3) Analysis of local knowledge, management and use of traditional varieties of maize in the Sierra of Ecuador, and (4) Identification of areas of high diversity and low risk of loss for the conservation of maize in the Sierra of Ecuador. For the first study were visited 303 farms distributed along the Sierra and collected 636 samples that were characterized morphologically by 14 variables: 8 related to the ear (shape, length and diameter of the cob, colour, and diameter of cob and number and arrangement of rows) and 7 referred to the grain (total number of grain, colour, shape, length, width, and thickness and type of grain endosperm). In addition, the farms where the samples were taken were characterized ecogeographically through 5 climatic variables (seasonal average temperature, range of average annual temperature, minimum temperature for December, seasonal precipitation and precipitation of October), 2 geophysical (altitude and slope) and edaphic 5 (main texture of the soil, deep rock, pH, content of organic matter and fertility). From this information and techniques of geographic information systems (GIS), maps were generated for distribution by race in vector format and a map of richness of races, a map of morphological diversity and a map of ecogeographical diversity in raster format with cells of 10 km x 10 km. The results allowed observing that, over the past 60 years, it has not lost any race. Nevertheless, Canguil, Chaucho and Clavito have stopped being cultivated in some provinces with the consequent genetic erosion of the cultivation. The morphological characterization detected differences in the degree of variability intra-race, being Patillo Ecuatoriano, Racimo de Uva and Uchima races more heterogeneous both for the qualitative and quantitative characters. At climate and geophysical level, also detected differences in the degree of variation intra-race; Cuzco Ecuatoriano, Kcello Ecuatoriano and Montaña Ecuatoriana were races that, on average, showed higher ranges and coefficients of variation for these geographical characters. In terms of the edaphic conditions, all races, except Cónico Dentado, showed a great heterogeneity, and can grow both in rich and poor soils, with pH values between acid and moderately alkaline. The comparison between races revealed significant differences in the environmental ranges in some races as Cónico Dentado, which tends to be grown at lower elevations and, therefore, in environments less cold and greater precipitation than Blanco Blandito, Patillo Ecuatoriano, Sabanero Ecuatoriano, Uchima and Zhima. For most of the races were found materials potentially adapted to stress conditions (seasonal precipitation less than 500 mm and soil with a pH between 4.5 and 5.5). Finally, the maps of richness, morphologic diversity and ecogeographical diversity showed 36 cells high diversity distributed in 10 provinces of the Sierra: 11 cells in the northern provinces, 11 in the central provinces and 14 in the southern provinces. For the characterization and identification of the typology of the farmers who cultivate corn in the Sierra of Ecuador and the analysis of the possible factors of risk of loss of diversity, there were realized interviews individual and semistructured to the farmers’ owners of the farms where the samples were gathered for the study of diversity (254 in whole). The questions that were formulated (11 opened ones and 5 closed ones) were organized in six blocks: data of the farmer, characteristics of the farm, diversity and knowledge of the crop, crop management, uses and seed flow. The results indicated that the maize diversity that exist in the Sierra of Ecuador is managed mainly by mestizo farmers, aged between 30 and 55, who cultivate one or two traditional varieties for self-consumption, on plots of less than 0.5 has and in associated with beans. The segmentation analysis algorithm using the Chi-square automatic interaction detection (CHAID technique), allowed to identify a small group of indigenous farmers with medium-sized plots (between 0.5 there is and 1.5 it is) that a major number of traditional varieties preserves for farm that the average farmer. The statistical analysis did not detect significant differences between ethnic groups (mestizos vs. indigenous), genres (man vs. women) and age groups (young people under 30 years of age, adults between 30 and 55 years and adults over 55 years old) in regards to the knowledge of the cultivation (recognition criteria and reasons of preference) and management (type of crop), but if detected differences between regions, mainly on the mode of cultivating the maize; while in the north and south they tend to sow in associate and with a greater number of species, in the center accustomed to cultivate it preferably only. In regards to the uses, they were compiled up to 39 different ways of consuming maize, being Kcello Ecuatoriano and Zhima the races for which a major number of uses registered. The comparison of the average number of uses per variety between ethnic groups showed that the mestizo farmers used their traditional varieties of form more varied than the indigenous people. Between the factors of risk that were analyzed, the low percentage of young farmers who deal with the farms might suppose a medium-term threat for lack of generational relief. In addition, the numerous synonyms and homonyms that were detected and the low seed exchange could also be a cause of loss of diversity, either by replacement or by aging of the seed. Finally, it was concluded that the races Chaucho, Complex Chillo-Huandango, Complex Mishca-Huandango, Cónico Dentado, Montaña Ecuatoriana and Sabanero Ecuatoriano are particularly vulnerable, not only because of their low presence, but also by the grain color they have (the same as the majority of races more common) and lack of names and specific uses. Finally, for the prioritization of maize conservation areas on farm in the Sierra of Ecuador, used 13 criteria of different nature: 2 ecogeographic (precipitation, diversity ecogeographical), 6 biological (degree of presence of the crop, races richness, morphological diversity, the presence of mixtures, presence of local races and risk of genetic erosion), 3 cultural (abundance of varieties per farm, diversity of uses and frequency of exchange) and 2 demographic (population size and distance to urban centers). Using GIS techniques and multicriteria evaluation, the original values of the layers-criterion were transformed to a scale of 0 to 100. Later, the normalized layers - criteria were added using three weighting methods: (1) the same weight, (2) different weight according to the score given by 72 experts, and (3) different weight according to the method of comparison between pairs of criteria. The results allowed to identify eight 10 km cells x 10 km with high punctuation (> 65): three cells in the north (one in each of the provinces), a cell in the center (in the Cotopaxi province), and four cells in the south region (two in Azuay and other two in Loja).

Identification of pore spaces in 3D CT soil images using a PFCM partitional clustering

Recent advances in non-destructive imaging techniques, such as X-ray computed tomography (CT), make it possible to analyse pore space features from the direct visualisation from soil structures. A quantitative characterisation of the three-dimensional solid-pore architecture is important to understand soil mechanics, as they relate to the control of biological, chemical, and physical processes across scales. This analysis technique therefore offers an opportunity to better interpret soil strata, as new and relevant information can be obtained. In this work, we propose an approach to automatically identify the pore structure of a set of 200-2D images that represent slices of an original 3D CT image of a soil sample, which can be accomplished through non-linear enhancement of the pixel grey levels and an image segmentation based on a PFCM (Possibilistic Fuzzy C-Means) algorithm. Once the solids and pore spaces have been identified, the set of 200-2D images is then used to reconstruct an approximation of the soil sample by projecting only the pore spaces. This reconstruction shows the structure of the soil and its pores, which become more bounded, less bounded, or unbounded with changes in depth. If the soil sample image quality is sufficiently favourable in terms of contrast, noise and sharpness, the pore identification is less complicated, and the PFCM clustering algorithm can be used without additional processing; otherwise, images require pre-processing before using this algorithm. Promising results were obtained with four soil samples, the first of which was used to show the algorithm validity and the additional three were used to demonstrate the robustness of our proposal. The methodology we present here can better detect the solid soil and pore spaces on CT images, enabling the generation of better 2D?3D representations of pore structures from segmented 2D images.

Improving parameters selection of a seeded region growing method for multiband image segmentation

In the last decade, Object Based Image Analysis (OBIA) has been accepted as an effective method for processing high spatial resolution multiband images. This image analysis method is an approach that starts with the segmentation of the image. Image segmentation in general is a procedure to partition an image into homogenous groups (segments). In practice, visual interpretation is often used to assess the quality of segmentation and the analysis relies on the experience of an analyst. In an effort to address the issue, in this study, we evaluate several seed selection strategies for an automatic image segmentation methodology based on a seeded region growing-merging approach. In order to evaluate the segmentation quality, segments were subjected to spatial autocorrelation analysis using Moran's I index and intra-segment variance analysis. We apply the algorithm to image segmentation using an aerial multiband image.

Contributions to the Resilience Management in the Internet of Things

El auge del "Internet de las Cosas" (IoT, "Internet of Things") y sus tecnologías asociadas han permitido su aplicación en diversos dominios de la aplicación, entre los que se encuentran la monitorización de ecosistemas forestales, la gestión de catástrofes y emergencias, la domótica, la automatización industrial, los servicios para ciudades inteligentes, la eficiencia energética de edificios, la detección de intrusos, la gestión de desastres y emergencias o la monitorización de señales corporales, entre muchas otras. La desventaja de una red IoT es que una vez desplegada, ésta queda desatendida, es decir queda sujeta, entre otras cosas, a condiciones climáticas cambiantes y expuestas a catástrofes naturales, fallos de software o hardware, o ataques maliciosos de terceros, por lo que se puede considerar que dichas redes son propensas a fallos. El principal requisito de los nodos constituyentes de una red IoT es que estos deben ser capaces de seguir funcionando a pesar de sufrir errores en el propio sistema. La capacidad de la red para recuperarse ante fallos internos y externos inesperados es lo que se conoce actualmente como "Resiliencia" de la red. Por tanto, a la hora de diseñar y desplegar aplicaciones o servicios para IoT, se espera que la red sea tolerante a fallos, que sea auto-configurable, auto-adaptable, auto-optimizable con respecto a nuevas condiciones que puedan aparecer durante su ejecución. Esto lleva al análisis de un problema fundamental en el estudio de las redes IoT, el problema de la "Conectividad". Se dice que una red está conectada si todo par de nodos en la red son capaces de encontrar al menos un camino de comunicación entre ambos. Sin embargo, la red puede desconectarse debido a varias razones, como que se agote la batería, que un nodo sea destruido, etc. Por tanto, se hace necesario gestionar la resiliencia de la red con el objeto de mantener la conectividad entre sus nodos, de tal manera que cada nodo IoT sea capaz de proveer servicios continuos, a otros nodos, a otras redes o, a otros servicios y aplicaciones. En este contexto, el objetivo principal de esta tesis doctoral se centra en el estudio del problema de conectividad IoT, más concretamente en el desarrollo de modelos para el análisis y gestión de la Resiliencia, llevado a la práctica a través de las redes WSN, con el fin de mejorar la capacidad la tolerancia a fallos de los nodos que componen la red. Este reto se aborda teniendo en cuenta dos enfoques distintos, por una parte, a diferencia de otro tipo de redes de dispositivos convencionales, los nodos en una red IoT son propensos a perder la conexión, debido a que se despliegan en entornos aislados, o en entornos con condiciones extremas; por otra parte, los nodos suelen ser recursos con bajas capacidades en términos de procesamiento, almacenamiento y batería, entre otros, por lo que requiere que el diseño de la gestión de su resiliencia sea ligero, distribuido y energéticamente eficiente. En este sentido, esta tesis desarrolla técnicas auto-adaptativas que permiten a una red IoT, desde la perspectiva del control de su topología, ser resiliente ante fallos en sus nodos. Para ello, se utilizan técnicas basadas en lógica difusa y técnicas de control proporcional, integral y derivativa (PID - "proportional-integral-derivative"), con el objeto de mejorar la conectividad de la red, teniendo en cuenta que el consumo de energía debe preservarse tanto como sea posible. De igual manera, se ha tenido en cuenta que el algoritmo de control debe ser distribuido debido a que, en general, los enfoques centralizados no suelen ser factibles a despliegues a gran escala. El presente trabajo de tesis implica varios retos que conciernen a la conectividad de red, entre los que se incluyen: la creación y el análisis de modelos matemáticos que describan la red, una propuesta de sistema de control auto-adaptativo en respuesta a fallos en los nodos, la optimización de los parámetros del sistema de control, la validación mediante una implementación siguiendo un enfoque de ingeniería del software y finalmente la evaluación en una aplicación real. Atendiendo a los retos anteriormente mencionados, el presente trabajo justifica, mediante una análisis matemático, la relación existente entre el "grado de un nodo" (definido como el número de nodos en la vecindad del nodo en cuestión) y la conectividad de la red, y prueba la eficacia de varios tipos de controladores que permiten ajustar la potencia de trasmisión de los nodos de red en respuesta a eventuales fallos, teniendo en cuenta el consumo de energía como parte de los objetivos de control. Así mismo, este trabajo realiza una evaluación y comparación con otros algoritmos representativos; en donde se demuestra que el enfoque desarrollado es más tolerante a fallos aleatorios en los nodos de la red, así como en su eficiencia energética. Adicionalmente, el uso de algoritmos bioinspirados ha permitido la optimización de los parámetros de control de redes dinámicas de gran tamaño. Con respecto a la implementación en un sistema real, se han integrado las propuestas de esta tesis en un modelo de programación OSGi ("Open Services Gateway Initiative") con el objeto de crear un middleware auto-adaptativo que mejore la gestión de la resiliencia, especialmente la reconfiguración en tiempo de ejecución de componentes software cuando se ha producido un fallo. Como conclusión, los resultados de esta tesis doctoral contribuyen a la investigación teórica y, a la aplicación práctica del control resiliente de la topología en redes distribuidas de gran tamaño. Los diseños y algoritmos presentados pueden ser vistos como una prueba novedosa de algunas técnicas para la próxima era de IoT. A continuación, se enuncian de forma resumida las principales contribuciones de esta tesis: (1) Se han analizado matemáticamente propiedades relacionadas con la conectividad de la red. Se estudia, por ejemplo, cómo varía la probabilidad de conexión de la red al modificar el alcance de comunicación de los nodos, así como cuál es el mínimo número de nodos que hay que añadir al sistema desconectado para su re-conexión. (2) Se han propuesto sistemas de control basados en lógica difusa para alcanzar el grado de los nodos deseado, manteniendo la conectividad completa de la red. Se han evaluado diferentes tipos de controladores basados en lógica difusa mediante simulaciones, y los resultados se han comparado con otros algoritmos representativos. (3) Se ha investigado más a fondo, dando un enfoque más simple y aplicable, el sistema de control de doble bucle, y sus parámetros de control se han optimizado empleando algoritmos heurísticos como el método de la entropía cruzada (CE, "Cross Entropy"), la optimización por enjambre de partículas (PSO, "Particle Swarm Optimization"), y la evolución diferencial (DE, "Differential Evolution"). (4) Se han evaluado mediante simulación, la mayoría de los diseños aquí presentados; además, parte de los trabajos se han implementado y validado en una aplicación real combinando técnicas de software auto-adaptativo, como por ejemplo las de una arquitectura orientada a servicios (SOA, "Service-Oriented Architecture"). ABSTRACT The advent of the Internet of Things (IoT) enables a tremendous number of applications, such as forest monitoring, disaster management, home automation, factory automation, smart city, etc. However, various kinds of unexpected disturbances may cause node failure in the IoT, for example battery depletion, software/hardware malfunction issues and malicious attacks. So, it can be considered that the IoT is prone to failure. The ability of the network to recover from unexpected internal and external failures is known as "resilience" of the network. Resilience usually serves as an important non-functional requirement when designing IoT, which can further be broken down into "self-*" properties, such as self-adaptive, self-healing, self-configuring, self-optimization, etc. One of the consequences that node failure brings to the IoT is that some nodes may be disconnected from others, such that they are not capable of providing continuous services for other nodes, networks, and applications. In this sense, the main objective of this dissertation focuses on the IoT connectivity problem. A network is regarded as connected if any pair of different nodes can communicate with each other either directly or via a limited number of intermediate nodes. More specifically, this thesis focuses on the development of models for analysis and management of resilience, implemented through the Wireless Sensor Networks (WSNs), which is a challenging task. On the one hand, unlike other conventional network devices, nodes in the IoT are more likely to be disconnected from each other due to their deployment in a hostile or isolated environment. On the other hand, nodes are resource-constrained in terms of limited processing capability, storage and battery capacity, which requires that the design of the resilience management for IoT has to be lightweight, distributed and energy-efficient. In this context, the thesis presents self-adaptive techniques for IoT, with the aim of making the IoT resilient against node failures from the network topology control point of view. The fuzzy-logic and proportional-integral-derivative (PID) control techniques are leveraged to improve the network connectivity of the IoT in response to node failures, meanwhile taking into consideration that energy consumption must be preserved as much as possible. The control algorithm itself is designed to be distributed, because the centralized approaches are usually not feasible in large scale IoT deployments. The thesis involves various aspects concerning network connectivity, including: creation and analysis of mathematical models describing the network, proposing self-adaptive control systems in response to node failures, control system parameter optimization, implementation using the software engineering approach, and evaluation in a real application. This thesis also justifies the relations between the "node degree" (the number of neighbor(s) of a node) and network connectivity through mathematic analysis, and proves the effectiveness of various types of controllers that can adjust power transmission of the IoT nodes in response to node failures. The controllers also take into consideration the energy consumption as part of the control goals. The evaluation is performed and comparison is made with other representative algorithms. The simulation results show that the proposals in this thesis can tolerate more random node failures and save more energy when compared with those representative algorithms. Additionally, the simulations demonstrate that the use of the bio-inspired algorithms allows optimizing the parameters of the controller. With respect to the implementation in a real system, the programming model called OSGi (Open Service Gateway Initiative) is integrated with the proposals in order to create a self-adaptive middleware, especially reconfiguring the software components at runtime when failures occur. The outcomes of this thesis contribute to theoretic research and practical applications of resilient topology control for large and distributed networks. The presented controller designs and optimization algorithms can be viewed as novel trials of the control and optimization techniques for the coming era of the IoT. The contributions of this thesis can be summarized as follows: (1) Mathematically, the fault-tolerant probability of a large-scale stochastic network is analyzed. It is studied how the probability of network connectivity depends on the communication range of the nodes, and what is the minimum number of neighbors to be added for network re-connection. (2) A fuzzy-logic control system is proposed, which obtains the desired node degree and in turn maintains the network connectivity when it is subject to node failures. There are different types of fuzzy-logic controllers evaluated by simulations, and the results demonstrate the improvement of fault-tolerant capability as compared to some other representative algorithms. (3) A simpler but more applicable approach, the two-loop control system is further investigated, and its control parameters are optimized by using some heuristic algorithms such as Cross Entropy (CE), Particle Swarm Optimization (PSO), and Differential Evolution (DE). (4) Most of the designs are evaluated by means of simulations, but part of the proposals are implemented and tested in a real-world application by combining the self-adaptive software technique and the control algorithms which are presented in this thesis.

Foreground segmentation in depth imagery using depth and spatial dynamic models for video surveillance applications

Low-cost systems that can obtain a high-quality foreground segmentation almostindependently of the existing illumination conditions for indoor environments are verydesirable, especially for security and surveillance applications. In this paper, a novelforeground segmentation algorithm that uses only a Kinect depth sensor is proposedto satisfy the aforementioned system characteristics. This is achieved by combininga mixture of Gaussians-based background subtraction algorithm with a new Bayesiannetwork that robustly predicts the foreground/background regions between consecutivetime steps. The Bayesian network explicitly exploits the intrinsic characteristics ofthe depth data by means of two dynamic models that estimate the spatial and depthevolution of the foreground/background regions. The most remarkable contribution is thedepth-based dynamic model that predicts the changes in the foreground depth distributionbetween consecutive time steps. This is a key difference with regard to visible imagery,where the color/gray distribution of the foreground is typically assumed to be constant.Experiments carried out on two different depth-based databases demonstrate that theproposed combination of algorithms is able to obtain a more accurate segmentation of theforeground/background than other state-of-the art approaches.

Using the Cross-Entropy Method for Control Optimization: A Case Study of See-and-Avoid on Unmanned Aerial Vehicles

This paper presents an adaptation of the Cross-Entropy (CE) method to optimize fuzzy logic controllers. The CE is a recently developed optimization method based on a general Monte-Carlo approach to combinatorial and continuous multi-extremal optimization and importance sampling. This work shows the application of this optimization method to optimize the inputs gains, the location and size of the different membership functions' sets of each variable, as well as the weight of each rule from the rule's base of a fuzzy logic controller (FLC). The control system approach presented in this work was designed to command the orientation of an unmanned aerial vehicle (UAV) to modify its trajectory for avoiding collisions. An onboard looking forward camera was used to sense the environment of the UAV. The information extracted by the image processing algorithm is the only input of the fuzzy control approach to avoid the collision with a predefined object. Real tests with a quadrotor have been done to corroborate the improved behavior of the optimized controllers at different stages of the optimization process.

Extending the expressiveness of fuzzy logic languages

En el trabajo que aquí presentamos se incluye la base teórica (sintaxis y semántica) y una implementación de un framework para codificar el razonamiento de la representación difusa o borrosa del mundo (tal y como nosotros, seres humanos, entendemos éste). El interés en la realización de éste trabajo parte de dos fuentes: eliminar la complejidad existente cuando se realiza una implementación con un lenguaje de programación de los llamados de propósito general y proporcionar una herramienta lo suficientemente inteligente para dar respuestas de forma constructiva a consultas difusas o borrosas. El framework, RFuzzy, permite codificar reglas y consultas en una sintaxis muy cercana al lenguaje natural usado por los seres humanos para expresar sus pensamientos, pero es bastante más que eso. Permite representar conceptos muy interesantes, como fuzzificaciones (funciones usadas para convertir conceptos no difusos en difusos), valores por defecto (que se usan para devolver resultados un poco menos válidos que los que devolveríamos si tuviésemos la información necesaria para calcular los más válidos), similaridad entre atributos (característica que utilizamos para buscar aquellos individuos en la base de datos con una característica similar a la buscada), sinónimos o antónimos y, además, nos permite extender el numero de conectivas y modificadores (incluyendo modificadores de negación) que podemos usar en las reglas y consultas. La personalización de la definición de conceptos difusos (muy útil para lidiar con el carácter subjetivo de los conceptos borrosos, donde nos encontramos con que cualificar a alguien de “alto” depende de la altura de la persona que cualifica) es otra de las facilidades incluida. Además, RFuzzy implementa la semántica multi-adjunta. El interés en esta reside en que introduce la posibilidad de obtener la credibilidad de una regla a partir de un conjunto de datos y una regla dada y no solo el grado de satisfacción de una regla a partir de el universo modelado en nuestro programa. De esa forma podemos obtener automáticamente la credibilidad de una regla para una determinada situación. Aún cuando la contribución teórica de la tesis es interesante en si misma, especialmente la inclusión del modificador de negacion, sus multiples usos practicos lo son también. Entre los diferentes usos que se han dado al framework destacamos el reconocimiento de emociones, el control de robots, el control granular en computacion paralela/distribuída y las busquedas difusas o borrosas en bases de datos. ABSTRACT In this work we provide a theoretical basis (syntax and semantics) and a practical implementation of a framework for encoding the reasoning and the fuzzy representation of the world (as human beings understand it). The interest for this work comes from two sources: removing the existing complexity when doing it with a general purpose programming language (one developed without focusing in providing special constructions for representing fuzzy information) and providing a tool intelligent enough to answer, in a constructive way, expressive queries over conventional data. The framework, RFuzzy, allows to encode rules and queries in a syntax very close to the natural language used by human beings to express their thoughts, but it is more than that. It allows to encode very interesting concepts, as fuzzifications (functions to easily fuzzify crisp concepts), default values (used for providing results less adequate but still valid when the information needed to provide results is missing), similarity between attributes (used to search for individuals with a characteristic similar to the one we are looking for), synonyms or antonyms and it allows to extend the number of connectives and modifiers (even negation) we can use in the rules. The personalization of the definition of fuzzy concepts (very useful for dealing with the subjective character of fuzziness, in which a concept like tall depends on the height of the person performing the query) is another of the facilities included. Besides, RFuzzy implements the multi-adjoint semantics. The interest in them is that in addition to obtaining the grade of satisfaction of a consequent from a rule, its credibility and the grade of satisfaction of the antecedents we can determine from a set of data how much credibility we must assign to a rule to model the behaviour of the set of data. So, we can determine automatically the credibility of a rule for a particular situation. Although the theoretical contribution is interesting by itself, specially the inclusion of the negation modifier, the practical usage of it is equally important. Between the different uses given to the framework we highlight emotion recognition, robocup control, granularity control in parallel/distributed computing and flexible searches in databases.

Pulmonary Artery-Vein Segmentation in Real and Synthetic CT Images = Segmentación Arteria-Vena Pulmonares en Imágenes de CT Reales y Sintéticas

La tomografía axial computerizada (TAC) es la modalidad de imagen médica preferente para el estudio de enfermedades pulmonares y el análisis de su vasculatura. La segmentación general de vasos en pulmón ha sido abordada en profundidad a lo largo de los últimos años por la comunidad científica que trabaja en el campo de procesamiento de imagen; sin embargo, la diferenciación entre irrigaciones arterial y venosa es aún un problema abierto. De hecho, la separación automática de arterias y venas está considerado como uno de los grandes retos futuros del procesamiento de imágenes biomédicas. La segmentación arteria-vena (AV) permitiría el estudio de ambas irrigaciones por separado, lo cual tendría importantes consecuencias en diferentes escenarios médicos y múltiples enfermedades pulmonares o estados patológicos. Características como la densidad, geometría, topología y tamaño de los vasos sanguíneos podrían ser analizados en enfermedades que conllevan remodelación de la vasculatura pulmonar, haciendo incluso posible el descubrimiento de nuevos biomarcadores específicos que aún hoy en dípermanecen ocultos. Esta diferenciación entre arterias y venas también podría ayudar a la mejora y el desarrollo de métodos de procesamiento de las distintas estructuras pulmonares. Sin embargo, el estudio del efecto de las enfermedades en los árboles arterial y venoso ha sido inviable hasta ahora a pesar de su indudable utilidad. La extrema complejidad de los árboles vasculares del pulmón hace inabordable una separación manual de ambas estructuras en un tiempo realista, fomentando aún más la necesidad de diseñar herramientas automáticas o semiautomáticas para tal objetivo. Pero la ausencia de casos correctamente segmentados y etiquetados conlleva múltiples limitaciones en el desarrollo de sistemas de separación AV, en los cuales son necesarias imágenes de referencia tanto para entrenar como para validar los algoritmos. Por ello, el diseño de imágenes sintéticas de TAC pulmonar podría superar estas dificultades ofreciendo la posibilidad de acceso a una base de datos de casos pseudoreales bajo un entorno restringido y controlado donde cada parte de la imagen (incluyendo arterias y venas) está unívocamente diferenciada. En esta Tesis Doctoral abordamos ambos problemas, los cuales están fuertemente interrelacionados. Primero se describe el diseño de una estrategia para generar, automáticamente, fantomas computacionales de TAC de pulmón en humanos. Partiendo de conocimientos a priori, tanto biológicos como de características de imagen de CT, acerca de la topología y relación entre las distintas estructuras pulmonares, el sistema desarrollado es capaz de generar vías aéreas, arterias y venas pulmonares sintéticas usando métodos de crecimiento iterativo, que posteriormente se unen para formar un pulmón simulado con características realistas. Estos casos sintéticos, junto a imágenes reales de TAC sin contraste, han sido usados en el desarrollo de un método completamente automático de segmentación/separación AV. La estrategia comprende una primera extracción genérica de vasos pulmonares usando partículas espacio-escala, y una posterior clasificación AV de tales partículas mediante el uso de Graph-Cuts (GC) basados en la similitud con arteria o vena (obtenida con algoritmos de aprendizaje automático) y la inclusión de información de conectividad entre partículas. La validación de los fantomas pulmonares se ha llevado a cabo mediante inspección visual y medidas cuantitativas relacionadas con las distribuciones de intensidad, dispersión de estructuras y relación entre arterias y vías aéreas, los cuales muestran una buena correspondencia entre los pulmones reales y los generados sintéticamente. La evaluación del algoritmo de segmentación AV está basada en distintas estrategias de comprobación de la exactitud en la clasificación de vasos, las cuales revelan una adecuada diferenciación entre arterias y venas tanto en los casos reales como en los sintéticos, abriendo así un amplio abanico de posibilidades en el estudio clínico de enfermedades cardiopulmonares y en el desarrollo de metodologías y nuevos algoritmos para el análisis de imágenes pulmonares. ABSTRACT Computed tomography (CT) is the reference image modality for the study of lung diseases and pulmonary vasculature. Lung vessel segmentation has been widely explored by the biomedical image processing community, however, differentiation of arterial from venous irrigations is still an open problem. Indeed, automatic separation of arterial and venous trees has been considered during last years as one of the main future challenges in the field. Artery-Vein (AV) segmentation would be useful in different medical scenarios and multiple pulmonary diseases or pathological states, allowing the study of arterial and venous irrigations separately. Features such as density, geometry, topology and size of vessels could be analyzed in diseases that imply vasculature remodeling, making even possible the discovery of new specific biomarkers that remain hidden nowadays. Differentiation between arteries and veins could also enhance or improve methods processing pulmonary structures. Nevertheless, AV segmentation has been unfeasible until now in clinical routine despite its objective usefulness. The huge complexity of pulmonary vascular trees makes a manual segmentation of both structures unfeasible in realistic time, encouraging the design of automatic or semiautomatic tools to perform the task. However, this lack of proper labeled cases seriously limits in the development of AV segmentation systems, where reference standards are necessary in both algorithm training and validation stages. For that reason, the design of synthetic CT images of the lung could overcome these difficulties by providing a database of pseudorealistic cases in a constrained and controlled scenario where each part of the image (including arteries and veins) is differentiated unequivocally. In this Ph.D. Thesis we address both interrelated problems. First, the design of a complete framework to automatically generate computational CT phantoms of the human lung is described. Starting from biological and imagebased knowledge about the topology and relationships between structures, the system is able to generate synthetic pulmonary arteries, veins, and airways using iterative growth methods that can be merged into a final simulated lung with realistic features. These synthetic cases, together with labeled real CT datasets, have been used as reference for the development of a fully automatic pulmonary AV segmentation/separation method. The approach comprises a vessel extraction stage using scale-space particles and their posterior artery-vein classification using Graph-Cuts (GC) based on arterial/venous similarity scores obtained with a Machine Learning (ML) pre-classification step and particle connectivity information. Validation of pulmonary phantoms from visual examination and quantitative measurements of intensity distributions, dispersion of structures and relationships between pulmonary air and blood flow systems, show good correspondence between real and synthetic lungs. The evaluation of the Artery-Vein (AV) segmentation algorithm, based on different strategies to assess the accuracy of vessel particles classification, reveal accurate differentiation between arteries and vein in both real and synthetic cases that open a huge range of possibilities in the clinical study of cardiopulmonary diseases and the development of methodological approaches for the analysis of pulmonary images.

Superpixel-based roughness measure for multispectral satellite image segmentation

The new generation of artificial satellites is providing a huge amount of Earth observation images whose exploitation can report invaluable benefits, both economical and environmental. However, only a small fraction of this data volume has been analyzed, mainly due to the large human resources needed for that task. In this sense, the development of unsupervised methodologies for the analysis of these images is a priority. In this work, a new unsupervised segmentation algorithm for satellite images is proposed. This algorithm is based on the rough-set theory, and it is inspired by a previous segmentation algorithm defined in the RGB color domain. The main contributions of the new algorithm are: (i) extending the original algorithm to four spectral bands; (ii) the concept of the superpixel is used in order to define the neighborhood similarity of a pixel adapted to the local characteristics of each image; (iii) and two new region merged strategies are proposed and evaluated in order to establish the final number of regions in the segmented image. The experimental results show that the proposed approach improves the results provided by the original method when both are applied to satellite images with different spectral and spatial resolutions.

Adaptive fuzzy knowledge-based systems for control metabots' mobility on virtual environments

The confluence of three-dimensional (3D) virtual worlds with social networks imposes on software agents, in addition to conversational functions, the same behaviours as those common to human-driven avatars. In this paper, we explore the possibilities of the use of metabots (metaverse robots) with motion capabilities in complex virtual 3D worlds and we put forward a learning model based on the techniques used in evolutionary computation for optimizing the fuzzy controllers which will subsequently be used by metabots for moving around a virtual environment.

Security devices based on liquid crystals doped with a colour dye

Liquid crystal properties make them useful for the development of security devices in applications of authentication and detection of fakes. Induced orientation of liquid crystal molecules and birefringence are the two main properties used in security devices. Employing liquid crystal and dichroic colorants, we have developed devices that show, with the aid of a polarizer, multiple images on each side of the device. Rubbed polyimide is used as alignment layer on each substrate of the LC cell. By rubbing the polyimide in different directions in each substrate it is possible to create any kind of symbols, drawings or motifs with a greyscale; the more complex the created device is, the more difficult is to fake it. To identify the motifs it is necessary to use polarized light. Depending on whether the polarizer is located in front of the LC cell or behind it, different motifs from one or the other substrate are shown. The effect arises from the dopant colour dye added to the liquid crystal, the induced orientation and the twist structure. In practice, a grazing reflection on a dielectric surface is polarized enough to see the effect. Any LC flat panel display can obviously be used as backlight as well.

The water footprint of olives and olive oil in Spain

This paper evaluates the water footprint of Spanish olives and olive oil over the period 1997-2008. In particular, it analyses the three colour components of the water footprint: green (rainwater stored in the soil), blue (surface and groundwater) and grey (freshwater required to assimilate load of pollutants). Apparent water productivity and virtual water embedded in olive oil exports have also been studied. Results show more than 99.5% of the water footprint of one liter of bottled olive oil is related to the olive production, whereas less than 0.5% is due to the other components such as bottle, cap and label. Over the studied period, the green water footprint in absolute terms of Spanish olive oil production represents about 72% in rainfed systems and just 12% in irrigated olive orchards. Blue and grey water footprints represent 6% and 10% of the national water footprint, respectively. It is shown that olive production is concentrated in regions with the smallest water footprint per unit of product. However, the increase of groundwater consumption in the main olive producing region (Andalusia), from 98 to 378 Mm3 between 1997 and 2008, has added significant pressure in the upstream Guadalquivir basin. This raises questions about the sustainability of irrigated olive orchards for export from the region. Finally, the virtual water related to olive oil exports illustrate the importance of green water footprint of rainfed olives amounting to about 77% of the total virtual water exports.

A new DSATUR-based algorithm for exact vertex coloring

This paper describes a new exact algorithm PASS for the vertex coloring problem based on the well known DSATUR algorithm. At each step DSATUR maximizes saturation degree to select a new candidate vertex to color, breaking ties by maximum degree w.r.t. uncolored vertices. Later Sewell introduced a new tiebreaking strategy, which evaluated available colors for each vertex explicitly. PASS differs from Sewell in that it restricts its application to a particular set of vertices. Overall performance is improved when the new strategy is applied selectively instead of at every step. The paper also reports systematic experiments over 1500 random graphs and a subset of the DIMACS color benchmark.