Optimization of Pattern Matching Algorithms for Multi- and Many-Core Platforms

Image and video compression play a major role in the world today, allowing the storage and transmission of large multimedia content volumes. However, the processing of this information requires high computational resources, hence the improvement of the computational performance of these compression algorithms is very important. The Multidimensional Multiscale Parser (MMP) is a pattern-matching-based compression algorithm for multimedia contents, namely images, achieving high compression ratios, maintaining good image quality, Rodrigues et al. [2008]. However, in comparison with other existing algorithms, this algorithm takes some time to execute. Therefore, two parallel implementations for GPUs were proposed by Ribeiro [2016] and Silva [2015] in CUDA and OpenCL-GPU, respectively. In this dissertation, to complement the referred work, we propose two parallel versions that run the MMP algorithm in CPU: one resorting to OpenMP and another that converts the existing OpenCL-GPU into OpenCL-CPU. The proposed solutions are able to improve the computational performance of MMP by 3 and 2:7 , respectively. The High Efficiency Video Coding (HEVC/H.265) is the most recent standard for compression of image and video. Its impressive compression performance, makes it a target for many adaptations, particularly for holoscopic image/video processing (or light field). Some of the proposed modifications to encode this new multimedia content are based on geometry-based disparity compensations (SS), developed by Conti et al. [2014], and a Geometric Transformations (GT) module, proposed by Monteiro et al. [2015]. These compression algorithms for holoscopic images based on HEVC present an implementation of specific search for similar micro-images that is more efficient than the one performed by HEVC, but its implementation is considerably slower than HEVC. In order to enable better execution times, we choose to use the OpenCL API as the GPU enabling language in order to increase the module performance. With its most costly setting, we are able to reduce the GT module execution time from 6.9 days to less then 4 hours, effectively attaining a speedup of 45 .

Pankkitoiminnan riskienhallinta ja riskienhallintaraportointi Puolassa

Tutkimuksessa tarkastellaan julkisesti noteerattujen pankkien riskienhallintaraportoinnin nykykäytäntöä Puolassa. Tutkimus jakaantuu kahteen osaan: Tutkimuksen ensimmäisessä osassa esitellään pankkitoimintaa, pankkitoiminnan riskejä ja riskienhallintaa. Pankkitoiminnan riskejä ovat luotto- ja markkinariskit, lisäksi puhutaan operatiivisista ja ympäristöriskeistä. Tutkimuksen toisessa osassa selvitetään ja kuvataan sitä, millaista on tutkimuksen kohdeyritysten riskienhallinta ja riskienhallintaraportointi, tutkimuksen tarkoituksena on myös verrata pankkien riskienhallintaraportointia keskenään. Tutkimuksen kohteena on 13 Varsovan pörssissä listattua pankkia. Tutkimusaineistona käytetään näiden pankkien vuoden 2005 vuosikertomuksia. Kysymyksessä on laadullinen tapaustutkimus, jolle on tyypillistä kuvaileva ja selittävä tutkimusote. Aineiston analyysimenetelmänä on käytetty pattern matchingiä, jonka avulla tutkitaan aineistosta löytyviä riskienhallintaraportoinnin osatekijöitä/indikaattoreita ja verrataan niitä oletettuihin malleihin. Tutkittujen riskienhallintaraporttien perusteella voidaan todeta, että pankkitoiminnan ydinriskeistä: luotto-, korko-, valuutta- ja likviditeettiriskeistä raportoidaan hyvin. Sen sijaan puutteita löytyy operatiivisten ja ympäristöriskien raportoinnista. Suurin osa pankeista raportoi operatiivisista riskeistä, mutta raportointi on pintapuolista ja analysointi puuttuu. Ympäristöriskeistä raportointi ei ole yleistä. Raportoinnin laajuus ja informatiivisuus vaihtelevat pankkien kesken: Suuret, kansainväliset pankkikonsernit raportoivat riskeistään laajasti ja informatiivisesti, kun taas pienemmillä, kansallisilla pankeilla raportointi jää usean pankin kohdalla suppeaksi. Syitä raportoinnin eroille on monia: Yksi syistä on IFRS-standardien vakiintumaton käyttö pienimmillä, kansallisilla pankeilla verrattuna kansainvälisiin pankkikonserneihin. Kansainvälisillä pankkikonserneilla on paremmat valmiudet raportoida riskienhallinnastaan verrattuna pienimpiin pankkeihin, jotka julkaisivat tilinpäätöksensä ensimmäistä kertaa IFRS-standardien mukaisesti vuonna 2005. Yhtenä selittävänä tekijänäraportoinnin eroille voidaan myös mainita omistuspohja: sijoittajainformaation merkitys on korostunut erityisesti organisaatioissa, joissa on laaja, kansainvälinen omistuspohja. Sen sijaan valtio-omisteisessa yrityksessä sijoittajainformaation merkitys on vähäisempi. Myös yrityskulttuuri vaikuttaa siihen, missä laajuudessa, ja mitä tietoa yritys antaa julkisuuteen. Pankit ovat myös tarkkoja maineestaan, mitä tietoa voidaan julkaista ja mitä vaikutuksia tiedon julkaisemisellaon yrityskuvaan. Sen sijaan pankin koolla ei välttämättä ole vaikutusta riskienhallintaraportoinnin laajuuteen ja informatiivisuuteen.

Ridge-based fingerprint matching using hough transform

Despite the efficacy of minutia-based fingerprint matching techniques for good-quality images captured by optical sensors, minutia-based techniques do not often perform so well on poor-quality images or fingerprint images captured by small solid-state sensors. Solid-state fingerprint sensors are being increasingly deployed in a wide range of applications for user authentication purposes. Therefore, it is necessary to develop new fingerprint-matching techniques that utilize other features to deal with fingerprint images captured by solid-state sensors. This paper presents a new fingerprint matching technique based on fingerprint ridge features. This technique was assessed on the MSU-VERIDICOM database, which consists of fingerprint impressions obtained from 160 users (4 impressions per finger) using a solid-state sensor. The combination of ridge-based matching scores computed by the proposed ridge-based technique with minutia-based matching scores leads to a reduction of the false non-match rate by approximately 1.7% at a false match rate of 0.1%. © 2005 IEEE.

Methodologies for visual correspondence

Visual correspondence is a key computer vision task that aims at identifying projections of the same 3D point into images taken either from different viewpoints or at different time instances. This task has been the subject of intense research activities in the last years in scenarios such as object recognition, motion detection, stereo vision, pattern matching, image registration. The approaches proposed in literature typically aim at improving the state of the art by increasing the reliability, the accuracy or the computational efficiency of visual correspondence algorithms. The research work carried out during the Ph.D. course and presented in this dissertation deals with three specific visual correspondence problems: fast pattern matching, stereo correspondence and robust image matching. The dissertation presents original contributions to the theory of visual correspondence, as well as applications dealing with 3D reconstruction and multi-view video surveillance.

A Bayesian changepoint analysis on spatio-temporal point processes

Changepoint analysis is a well established area of statistical research, but in the context of spatio-temporal point processes it is as yet relatively unexplored. Some substantial differences with regard to standard changepoint analysis have to be taken into account: firstly, at every time point the datum is an irregular pattern of points; secondly, in real situations issues of spatial dependence between points and temporal dependence within time segments raise. Our motivating example consists of data concerning the monitoring and recovery of radioactive particles from Sandside beach, North of Scotland; there have been two major changes in the equipment used to detect the particles, representing known potential changepoints in the number of retrieved particles. In addition, offshore particle retrieval campaigns are believed may reduce the particle intensity onshore with an unknown temporal lag; in this latter case, the problem concerns multiple unknown changepoints. We therefore propose a Bayesian approach for detecting multiple changepoints in the intensity function of a spatio-temporal point process, allowing for spatial and temporal dependence within segments. We use Log-Gaussian Cox Processes, a very flexible class of models suitable for environmental applications that can be implemented using integrated nested Laplace approximation (INLA), a computationally efficient alternative to Monte Carlo Markov Chain methods for approximating the posterior distribution of the parameters. Once the posterior curve is obtained, we propose a few methods for detecting significant change points. We present a simulation study, which consists in generating spatio-temporal point pattern series under several scenarios; the performance of the methods is assessed in terms of type I and II errors, detected changepoint locations and accuracy of the segment intensity estimates. We finally apply the above methods to the motivating dataset and find good and sensible results about the presence and quality of changes in the process.

Age determination and stable oxygen isotope record of ODP Hole 167-1017E

Oxygen isotopic (d18O) climatic stratigraphy and radiocarbon chronology, at high resolution, have been used to establish an age model for Ocean Drilling Program Hole 1017E, a continuous 25-m sequence of hemipelagic sediments from the continental slope (956 m water depth), east of Point Arguella, Southern California. The upper part of Hole 1017E from ~33 ka (7.445 mbsf) was dated using 13 calendar-corrected radiocarbon ages of mixed planktonic foraminiferal assemblages. Benthic oxygen isotopic stratigraphy records a continuous 130-k.y. sequence ranging from marine isotope Stage 6 to the present day. The benthic d18O curve, representing the last two interglacial and glacial cycles, closely resembles the well-dated, deep-sea reference sequence, providing a detailed chronologic framework. Sedimentation rates remained relatively constant throughout the sequence at ~18 cm/k.y. and were sufficiently rapid to provide considerable potential for high-resolution paleoceanographic/paleoclimatic investigations. Planktonic foraminiferal oxygen isotopic stratigraphy based on the surface-dwelling form Globigerina bulloides defines an almost complete sequence of interstadial/stadial oscillations (Dansgaard/Oeschger cycles [D/O]). Combined use of radiocarbon chronology, deep-sea oxygen isotopic datums, and visual pattern matching has enabled us to identify the sequence of D/O cycles as described for the Greenland (GRIP2) ice core. This has strengthened the stratigraphic framework for the last 60 k.y. in the sequence as a basis for further paleoenvironmental investigations.

Fine spatial pattern of an epiphytic lichen species is affected by habitat conditions in two forest types in the Iberian Mediterranean region

Persistence and abundance of species is determined by habitat availability and the ability to disperse and colonize habitats at contrasting spatial scales. Favourable habitat fragments are also heterogeneous in quality, providing differing opportunities for establishment and affecting the population dynamics of a species. Based on these principles, we suggest that the presence and abundance of epiphytes may reflect their dispersal ability, which is primarily determined by the spatial structure of host trees, but also by host quality. To our knowledge there has been no explicit test of the importance of host tree spatial pattern for epiphytes in Mediterranean forests. We hypothesized that performance and host occupancy in a favourable habitat depend on the spatial pattern of host trees, because this pattern affects the dispersal ability of each epiphyte and it also determines the availability of suitable sites for establishment. We tested this hypothesis using new point pattern analysis tools and generalized linear mixed models to investigate the spatial distribution and performance of the epiphytic lichen Lobaria pulmonaria, which inhabits two types of host trees (beeches and Iberian oaks). We tested the effects on L. pulmonaria distribution of tree size, spatial configuration, and host tree identity. We built a model including tree size, stand structure, and several neighbourhood predictors to understand the effect of host tree on L. pulmonaria. We also investigated the relative importance of spatial patterning on the presence and abundance of the species, independently of the host tree configuration. L. pulmonaria distribution was highly dependent on habitat quality for successful establishment, i.e., tree species identity, tree diameter, and several forest stand structure surrogates. For beech trees, tree diameter was the main factor influencing presence and cover of the lichen, although larger lichen-colonized trees were located close to focal trees, i.e., young trees. However, oak diameter was not an important factor, suggesting that bark roughness at all diameters favoured lichen establishment. Our results indicate that L. pulmonaria dispersal is not spatially restricted, but it is dependent on habitat quality. Furthermore, new spatial analysis tools suggested that L. pulmonaria cover exhibits a distinct pattern, although the spatial pattern of tree position and size was random.

Fine spatial pattern of an epiphytic lichen species is affected by habitat conditions in two forest types in the Iberian Mediterranean region

Persistence and abundance of species is determined by habitat availability and the ability to disperse and colonize habitats at contrasting spatial scales. Favourable habitat fragments are also heterogeneous in quality, providing differing opportunities for establishment and affecting the population dynamics of a species. Based on these principles, we suggest that the presence and abundance of epiphytes may reflect their dispersal ability, which is primarily determined by the spatial structure of host trees, but also by host quality. To our knowledge there has been no explicit test of the importance of host tree spatial pattern for epiphytes in Mediterranean forests. We hypothesized that performance and host occupancy in a favourable habitat depend on the spatial pattern of host trees, because this pattern affects the dispersal ability of each epiphyte and it also determines the availability of suitable sites for establishment. We tested this hypothesis using new point pattern analysis tools and generalized linear mixed models to investigate the spatial distribution and performance of the epiphytic lichen Lobaria pulmonaria, which inhabits two types of host trees (beeches and Iberian oaks). We tested the effects on L. pulmonaria distribution of tree size, spatial configuration, and host tree identity. We built a model including tree size, stand structure, and several neighbourhood predictors to understand the effect of host tree on L. pulmonaria. We also investigated the relative importance of spatial patterning on the presence and abundance of the species, independently of the host tree configuration. L. pulmonaria distribution was highly dependent on habitat quality for successful establishment, i.e., tree species identity, tree diameter, and several forest stand structure surrogates. For beech trees, tree diameter was the main factor influencing presence and cover of the lichen, although larger lichen-colonized trees were located close to focal trees, i.e., young trees. However, oak diameter was not an important factor, suggesting that bark roughness at all diameters favoured lichen establishment. Our results indicate that L. pulmonaria dispersal is not spatially restricted, but it is dependent on habitat quality. Furthermore, new spatial analysis tools suggested that L. pulmonaria cover exhibits a distinct pattern, although the spatial pattern of tree position and size was random.

Knowledge-based spatiotemporal linear abstraction

We present a theoretical framework and a case study for reusing the same conceptual and computational methodology for both temporal abstraction and linear (unidimensional) space abstraction, in a domain (evaluation of traffic-control actions) significantly different from the one (clinical medicine) in which the method was originally used. The method, known as knowledge-based temporal abstraction, abstracts high-level concepts and patterns from time-stamped raw data using a formal theory of domain-specific temporal-abstraction knowledge. We applied this method, originally used to interpret time-oriented clinical data, to the domain of traffic control, in which the monitoring task requires linear pattern matching along both space and time. First, we reused the method for creation of unidimensional spatial abstractions over highways, given sensor measurements along each highway measured at the same time point. Second, we reused the method to create temporal abstractions of the traffic behavior, for the same space segments, but during consecutive time points. We defined the corresponding temporal-abstraction and spatial-abstraction domain-specific knowledge. Our results suggest that (1) the knowledge-based temporal-abstraction method is reusable over time and unidimensional space as well as over significantly different domains; (2) the method can be generalized into a knowledge-based linear-abstraction method, which solves tasks requiring abstraction of data along any linear distance measure; and (3) a spatiotemporal-abstraction method can be assembled from two copies of the generalized method and a spatial-decomposition mechanism, and is applicable to tasks requiring abstraction of time-oriented data into meaningful spatiotemporal patterns over a linear, decomposable space, such as traffic over a set of highways.

Changes in spatial point patterns of pioneer woody plants across a large tropical landslide

We assessed whether the relative importance of positive and negative interactions in early successional communities varied across a large landslide on Casita Volcano (Nicaragua). We tested several hypotheses concerning the signatures of these processes in the spatial patterns of woody pioneer plants, as well as those of mortality and recruitment events, in several zones of the landslide differing in substrate stability and fertility, over a period of two years (2001 and 2002). We identified all woody individuals with a diameter >1 cm and mapped them in 28 plots measuring 10 × 10-m. On these maps, we performed a spatial point pattern analysis using univariate and bivariate pair-correlation functions; g (r) and g12 (r), and pairwise differences of univariate and bivariate functions. Spatial signatures of positive and negative interactions among woody plants were more prevalent in the most and least stressful zones of the landslide, respectively. Natural and human-induced disturbances such as the occurrence of fire, removal of newly colonizing plants through erosion and clearcutting of pioneer trees were also identified as potentially important pattern-creating processes. These results are in agreement with the stress-gradient hypothesis, which states that the relative importance of facilitation and competition varies inversely across gradients of abiotic stress. Our findings also indicate that the assembly of early successional plant communities in large heterogeneous landslides might be driven by a much larger array of processes than previously thought.

Public scientific communication on Twitter:visual analytic approach

Purpose - The purpose of this paper is to assess high-dimensional visualisation, combined with pattern matching, as an approach to observing dynamic changes in the ways people tweet about science topics. Design/methodology/approach - The high-dimensional visualisation approach was applied to three scientific topics to test its effectiveness for longitudinal analysis of message framing on Twitter over two disjoint periods in time. The paper uses coding frames to drive categorisation and visual analytics of tweets discussing the science topics. Findings - The findings point to the potential of this mixed methods approach, as it allows sufficiently high sensitivity to recognise and support the analysis of non-trending as well as trending topics on Twitter. Research limitations/implications - Three topics are studied and these illustrate a range of frames, but results may not be representative of all scientific topics. Social implications - Funding bodies increasingly encourage scientists to participate in public engagement. As social media provides an avenue actively utilised for public communication, understanding the nature of the dialog on this medium is important for the scientific community and the public at large. Originality/value - This study differs from standard approaches to the analysis of microblog data, which tend to focus on machine driven analysis large-scale datasets. It provides evidence that this approach enables practical and effective analysis of the content of midsize to large collections of microposts.

Mapping cortical change in Alzheimer's disease, brain development, and schizophrenia

This paper describes algorithms that can identify patterns of brain structure and function associated with Alzheimer's disease, schizophrenia, normal aging, and abnormal brain development based on imaging data collected in large human populations. Extraordinary information can be discovered with these techniques: dynamic brain maps reveal how the brain grows in childhood, how it changes in disease, and how it responds to medication. Genetic brain maps can reveal genetic influences on brain structure, shedding light on the nature-nurture debate, and the mechanisms underlying inherited neurobehavioral disorders. Recently, we created time-lapse movies of brain structure for a variety of diseases. These identify complex, shifting patterns of brain structural deficits, revealing where, and at what rate, the path of brain deterioration in illness deviates from normal. Statistical criteria can then identify situations in which these changes are abnormally accelerated, or when medication or other interventions slow them. In this paper, we focus on describing our approaches to map structural changes in the cortex. These methods have already been used to reveal the profile of brain anomalies in studies of dementia, epilepsy, depression, childhood and adult-onset schizophrenia, bipolar disorder, attention-deficit/ hyperactivity disorder, fetal alcohol syndrome, Tourette syndrome, Williams syndrome, and in methamphetamine abusers. Specifically, we describe an image analysis pipeline known as cortical pattern matching that helps compare and pool cortical data over time and across subjects. Statistics are then defined to identify brain structural differences between groups, including localized alterations in cortical thickness, gray matter density (GMD), and asymmetries in cortical organization. Subtle features, not seen in individual brain scans, often emerge when population-based brain data are averaged in this way. Illustrative examples are presented to show the profound effects of development and various diseases on the human cortex. Dynamically spreading waves of gray matter loss are tracked in dementia and schizophrenia, and these sequences are related to normally occurring changes in healthy subjects of various ages. (C) 2004 Published by Elsevier Inc.