Applied Graph Theory in Computer Vision and Pattern Recognition

This book will serve as a foundation for a variety of useful applications of graph theory to computer vision, pattern recognition, and related areas. It covers a representative set of novel graph-theoretic methods for complex computer vision and pattern recognition tasks. The first part of the book presents the application of graph theory to low-level processing of digital images such as a new method for partitioning a given image into a hierarchy of homogeneous areas using graph pyramids, or a study of the relationship between graph theory and digital topology. Part II presents graph-theoretic learning algorithms for high-level computer vision and pattern recognition applications, including a survey of graph based methodologies for pattern recognition and computer vision, a presentation of a series of computationally efficient algorithms for testing graph isomorphism and related graph matching tasks in pattern recognition and a new graph distance measure to be used for solving graph matching problems. Finally, Part III provides detailed descriptions of several applications of graph-based methods to real-world pattern recognition tasks. It includes a critical review of the main graph-based and structural methods for fingerprint classification, a new method to visualize time series of graphs, and potential applications in computer network monitoring and abnormal event detection.

Fabrication and characterization of room temperature operating single electron transistors using focused ion beam technologies

The single electron transistor (SET) is a Coulomb blockade device, whose operation is based on the controlled manipulation of individual electrons. Single electron transistors show immense potential to be used in future ultra lowpower devices, high density memory and also in high precision electrometry. Most SET devices operate at cryogenic temperatures, because the charging energy is much smaller than the thermal oscillations. The room temperature operation of these devices is possible with sub- 10nm nano-islands due to the inverse dependance of charging energy on the radius of the conducting nano-island. The fabrication of sub-10nm features with existing lithographic techniques is a technological challenge. Here we present the results for the first room temperature operating SET device fabricated using Focused Ion Beam deposition technology. The SET device, incorporates an array of tungsten nano-islands with an average diameter of 8nm. The SET devices shows clear Coulomb blockade for different gate voltages at room temperature. The charging energy of the device was calculated to be 160.0 meV; the capacitance per junction was found to be 0.94 atto F; and the tunnel resistance per junction was calculated to be 1.26 G Ω. The tunnel resistance is five orders of magnitude larger than the quantum of resistance (26 k Ω) and allows for the localization of electrons on the tungsten nano-island. The lower capacitance of the device combined with the high tunnel resistance, allows for the Coulomb blockade effects observed at room temperature. Different device configurations, minimizing the total capacitance of the device have been explored. The effect of the geometry of the nano electrodes on the device characteristics has been presented. Simulated device characteristics, based on the soliton model have been discussed. The first application of SET device as a gas sensor has been demonstrated.

EXPERIMENTAL AND COMPUTATIONAL STUDIES OF ELECTROMAGNETIC CLOAKING AT MICROWAVES

An invisibility cloak is a device that can hide the target by enclosing it from the incident radiation. This intriguing device has attracted a lot of attention since it was first implemented at a microwave frequency in 2006. However, the problems of existing cloak designs prevent them from being widely applied in practice. In this dissertation, we try to remove or alleviate the three constraints for practical applications imposed by loosy cloaking media, high implementation complexity, and small size of hidden objects compared to the incident wavelength. To facilitate cloaking design and experimental characterization, several devices and relevant techniques for measuring the complex permittivity of dielectric materials at microwave frequencies are developed. In particular, a unique parallel plate waveguide chamber has been set up to automatically map the electromagnetic (EM) field distribution for wave propagation through the resonator arrays and cloaking structures. The total scattering cross section of the cloaking structures was derived based on the measured scattering field by using this apparatus. To overcome the adverse effects of lossy cloaking media, microwave cloaks composed of identical dielectric resonators made of low loss ceramic materials are designed and implemented. The effective permeability dispersion was provided by tailoring dielectric resonator filling fractions. The cloak performances had been verified by full-wave simulation of true multi-resonator structures and experimental measurements of the fabricated prototypes. With the aim to reduce the implementation complexity caused by metamaterials employment for cloaking, we proposed to design 2-D cylindrical cloaks and 3-D spherical cloaks by using multi-layer ordinary dielectric material (εr>1) coating. Genetic algorithm was employed to optimize the dielectric profiles of the cloaking shells to provide the minimum scattering cross sections of the cloaked targets. The designed cloaks can be easily scaled to various operating frequencies. The simulation results show that the multi-layer cylindrical cloak essentially outperforms the similarly sized metamaterials-based cloak designed by using the transformation optics-based reduced parameters. For the designed spherical cloak, the simulated scattering pattern shows that the total scattering cross section is greatly reduced. In addition, the scattering in specific directions could be significantly reduced. It is shown that the cloaking efficiency for larger targets could be improved by employing lossy materials in the shell. At last, we propose to hide a target inside a waveguide structure filled with only epsilon near zero materials, which are easy to implement in practice. The cloaking efficiency of this method, which was found to increase for large targets, has been confirmed both theoretically and by simulations.

ANALYSIS AND VISUALIZATION OF FLOW FIELDS USING INFORMATION-THEORETIC TECHNIQUES AND GRAPH-BASED REPRESENTATIONS

Three-dimensional flow visualization plays an essential role in many areas of science and engineering, such as aero- and hydro-dynamical systems which dominate various physical and natural phenomena. For popular methods such as the streamline visualization to be effective, they should capture the underlying flow features while facilitating user observation and understanding of the flow field in a clear manner. My research mainly focuses on the analysis and visualization of flow fields using various techniques, e.g. information-theoretic techniques and graph-based representations. Since the streamline visualization is a popular technique in flow field visualization, how to select good streamlines to capture flow patterns and how to pick good viewpoints to observe flow fields become critical. We treat streamline selection and viewpoint selection as symmetric problems and solve them simultaneously using the dual information channel [81]. To the best of my knowledge, this is the first attempt in flow visualization to combine these two selection problems in a unified approach. This work selects streamline in a view-independent manner and the selected streamlines will not change for all viewpoints. My another work [56] uses an information-theoretic approach to evaluate the importance of each streamline under various sample viewpoints and presents a solution for view-dependent streamline selection that guarantees coherent streamline update when the view changes gradually. When projecting 3D streamlines to 2D images for viewing, occlusion and clutter become inevitable. To address this challenge, we design FlowGraph [57, 58], a novel compound graph representation that organizes field line clusters and spatiotemporal regions hierarchically for occlusion-free and controllable visual exploration. We enable observation and exploration of the relationships among field line clusters, spatiotemporal regions and their interconnection in the transformed space. Most viewpoint selection methods only consider the external viewpoints outside of the flow field. This will not convey a clear observation when the flow field is clutter on the boundary side. Therefore, we propose a new way to explore flow fields by selecting several internal viewpoints around the flow features inside of the flow field and then generating a B-Spline curve path traversing these viewpoints to provide users with closeup views of the flow field for detailed observation of hidden or occluded internal flow features [54]. This work is also extended to deal with unsteady flow fields. Besides flow field visualization, some other topics relevant to visualization also attract my attention. In iGraph [31], we leverage a distributed system along with a tiled display wall to provide users with high-resolution visual analytics of big image and text collections in real time. Developing pedagogical visualization tools forms my other research focus. Since most cryptography algorithms use sophisticated mathematics, it is difficult for beginners to understand both what the algorithm does and how the algorithm does that. Therefore, we develop a set of visualization tools to provide users with an intuitive way to learn and understand these algorithms.

A virtual environment for the assessment and the rehabilitation of the visuo-constructional ability in dementia patients

This study proposes a VE that offers a reliable diagnosis of the stage of cognitive decline in dementia patients and assists the delay of this decline in terms of the visuo-constructional ability. The proposed VE, in the case of the assessment, presents a visuo-constructional completion task, which requires spatial perception, motor memory and the perception of the target object. In the case of the rehabilitation the VE uses sound as audio-feedback that, with the aid of the music perception, tends to develop an enhancement in the visuo-construction ability of the dementia patients that can be generalized even outside of the VE. The study examined 30 subjects that were normal controls (N), 30 patients suffering from memory disorders (Age-Associated Memory Impairment--AAMI) and 30 suffering from Alzheimer's Disease (AD). The results showed that there is a significant correlation between the performance in the visuo-constructional task and the dementia diagnosis. It also seems that the visuo-constructional ability of the (AD) patients can be statistically improved by the audio experience in the VE. The empirical results of this study offer an alternative diagnosis and treatment of dementia patients and could share some light in the brain sub-systems that are responsible for the visuo-constructional ability. Further studies are required in order to investigate the nature of this phenomenon more.

Enhanced memory ability: insights from synaesthesia

People with synaesthesia show an enhanced memory relative to demographically matched controls. The most obvious explanation for this is that the ‘extra’ perceptual experiences lead to richer encoding and retrieval opportunities of stimuli which induce synaesthesia (typically verbal stimuli). Although there is some evidence for this, it is unlikely to be the whole explanation. For instance, not all stimuli which trigger synaesthesia are better remembered (e.g., digit span) and some stimuli which do not trigger synaesthesia are better remembered. In fact, synaesthetes tend to have better visual memory than verbal memory. We suggest that enhanced memory in synaesthesia is linked to wider changes in cognitive systems at the interface of perception and memory and link this to recent findings in the neuroscience of memory.

Mood and Memory: Mood congruity effects in absence of mood

Themood-congruity effect refers to facilitated processing of information when the affective valence of this information is congruent with the subject’s mood. In this paper we argue that mood may be a sufficient but not a necessary condition to produce the mood-congruity effect of selective learning. Two experiments are presented in which subjects learned lists of words with neutral, positive, and negative affective valences. In the learning task the subjects were instructed to behave as if they were depressed or happy. The mood-congruity effect was indeed obtained. The effect was stronger with subjects who “predicted” the relationship between mood and affective word valence than with subjects who were unaware of this relationship. The results are not simply attributed to task demands, but are interpreted in terms of a model of cognitive processes and people’s knowledge about mood states.

The role of controlled attention and selective encoding for kindergarteners' learning

Selectivity in encoding, aspects of attentional control and their contribution to learning performance were explored in a sample of preschoolers. While the children are performing a learning task, their encoding of relevant and attention towards irrelevant information was recorded through an eye-tracking device. Recognition of target items was used as measure of learning outcome, and individual differences in resistance to interference and inhibition of attention to task-irrelevant stimuli (i.e. distractibility) were used as measures of executive control of attention. Results indicated well-developed selectivity during encoding in young children. Recognition performance was related to selective encoding and aspects of attentional control, explaining individual differences in learning. Copyright © 2011 John Wiley & Sons, Ltd.

Do Cognitive and behavioral assessments of executive functions measure the same concept in children born very preterm?

Aims: This study investigated whether children aged between 8 - 12 years born very preterm (VPT) and/or at very low birth weight (VLBW) performed lower than same-aged term-born controls in cognitive and behavioral aspects of three executive functions: inhibition, working memory, and shifting. Special attention was given to sex differences. Methods: Fifty-two VPT/VLBW children (26 girls) born in the cohort of 1998–2003 at the Children’s University Hospital in Bern, Switzerland, and 36 same-aged term-born controls (18 girls) were recruited. As cognitive measures, children completed tasks of inhibition (Colour-Word Interference Test, D-KEFS), working memory (digit span backwards, WISC-IV) and shifting (Trail Making Test, number-letter switching, D-KEFS). As behavioral measures, mothers completed the Behavior Rating Inventory of Executive Function (BRIEF), assessing executive functions in everyday life.

Relations among fluid intelligence, sensory discrimination and working memory in middle to late childhood – A latent variable approach

Two factors that have been suggested as key in explaining individual differences in fluid intelligence are working memory and sensory discrimination ability. A latent variable approach was used to explore the relative contributions of these two variables to individual differences in fluid intelligence in middle to late childhood. A sample of 263 children aged 7–12 years was examined. Correlational analyses showed that general discrimination ability (GDA)and working memory (WM) were related to each other and to fluid intelligence. Structural equation modeling showed that within both younger and older age groups and the sample as a whole, the relation between GDA and fluid intelligence could be accounted for by WM. While WM was able to predict variance in fluid intelligence above and beyond GDA, GDA was not able to explain significant amounts of variance in fluid intelligence, either in the whole sample or within the younger or older age group. We concluded that compared to GDA, WM should be considered the better predictor of individual differences in fluid intelligence in childhood. WM and fluid intelligence, while not being separable in middle childhood, develop at different rates, becoming more separable with age.

Nonverbal social communication and gesture control in schizophrenia

Schizophrenia patients are severely impaired in nonverbal communication, including social perception and gesture production. However, the impact of nonverbal social perception on gestural behavior remains unknown, as is the contribution of negative symptoms, working memory, and abnormal motor behavior. Thus, the study tested whether poor nonverbal social perception was related to impaired gesture performance, gestural knowledge, or motor abnormalities. Forty-six patients with schizophrenia (80%), schizophreniform (15%), or schizoaffective disorder (5%) and 44 healthy controls matched for age, gender, and education were included. Participants completed 4 tasks on nonverbal communication including nonverbal social perception, gesture performance, gesture recognition, and tool use. In addition, they underwent comprehensive clinical and motor assessments. Patients presented impaired nonverbal communication in all tasks compared with controls. Furthermore, in contrast to controls, performance in patients was highly correlated between tasks, not explained by supramodal cognitive deficits such as working memory. Schizophrenia patients with impaired gesture performance also demonstrated poor nonverbal social perception, gestural knowledge, and tool use. Importantly, motor/frontal abnormalities negatively mediated the strong association between nonverbal social perception and gesture performance. The factors negative symptoms and antipsychotic dosage were unrelated to the nonverbal tasks. The study confirmed a generalized nonverbal communication deficit in schizophrenia. Specifically, the findings suggested that nonverbal social perception in schizophrenia has a relevant impact on gestural impairment beyond the negative influence of motor/frontal abnormalities.

Prospective memory, executive functions, and metacognition are already differentiated in young elementary school children: Evidence from latent factor modelling

This study investigated the empirical differentiation of prospective memory, executive functions, and metacognition and their structural relationships in 119 elementary school children (M = 95 months, SD = 4.8 months). These cognitive abilities share many characteristics on the theoretical level and are all highly relevant in many everyday contexts when intentions must be executed. Nevertheless, their empirical relationships have not been examined on the latent level, although an empirical approach would contribute to our knowledge concerning the differentiation of cognitive abilities during childhood. We administered a computerized event-based prospective memory task, three executive function tasks (updating, inhibition, shifting), and a metacognitive control task in the context of spelling. Confirmatory factor analysis revealed that the three cognitive abilities are already empirically differentiable in young elementary school children. At the same time, prospective memory and executive functions were found to be strongly related, and there was also a close link between prospective memory and metacognitive control. Furthermore, executive functions and metacognitive control were marginally significantly related. The findings are discussed within a framework of developmental differentiation and conceptual similarities and differences.

Working memory training in children: Effectiveness depends on temperament

Studies revealing transfer effects of working memory (WM) training on non-trained cognitive performance of children hold promising implications for scholastic learning. However, the results of existing training studies are not consistent and provoke debates about the potential and limitations of cognitive enhancement. To examine the influence of individual differences on training outcomes is a promising approach for finding causes for such inconsistencies. In this study, we implemented WM training in an elementary school setting. The aim was to investigate near and far transfer effects on cognitive abilities and academic achievement and to examine the moderating effects of a dispositional and a regulative temperament factor, neuroticism and effortful control. Ninetynine second-graders were randomly assigned to 20 sessions of computer-based adaptiveWMtraining, computer-based reading training, or a no-contact control group. For the WM training group, our analyses reveal near transfer on a visual WM task, far transfer on a vocabulary task as a proxy for crystallized intelligence, and increased academic achievement in reading and math by trend. Considering individual differences in temperament, we found that effortful control predicts larger training mean and gain scores and that there is a moderation effect of both temperament factors on post-training improvement: WM training condition predicted higher post-training gains compared to both control conditions only in children with high effortful control or low neuroticism. Our results suggest that a short but intensive WM training program can enhance cognitive abilities in children, but that sufficient selfregulative abilities and emotional stability are necessary for WM training to be effective.

Differential effectiveness of integrated cognitive remediation therapy for schizophrenbia outpatients: The impact oft he duration of illness

Background Nowadays there is extensive evidence available showing the efficacy of cognitive remediation (CR). To date, only limited evidence is available about the impact of the duration of illness on CR effects. The Integrated Neurocognitive Therapy (INT) represents a new developed CR approach. It is a manualized group therapy targeting all 11 NIMH-MATRICS domains. Methods In an international multicenter study, 166 schizophrenia outpatients (DSM-IV-TR) were randomly assigned either to INT or to Treatment-As-Usual (TAU). 60 patients were defined as Early Course group (EC) characterized by less than 5 years of illness, 40 patients were in the Long-Term group (LT) characterized by more than 15 years of illness, and 76 patients were in the Medium-Long-Term group (MLT) characterized by an illness of 5-15 years. Treatment comprised of 15 biweekly sessions. Assessments were conducted before and after treatment and at follow up (1 year). Multivariate General Linear Models (GLM) examined our hypothesis, whether EC, LT, and MLT groups differ under INT and TAU from each other in outcome. Results First of all, the attendance rate of 65% was significantly lower and the drop out rate of 18.5% during therapy was higher in the EC group compared to the other groups. Interaction effects regarding proximal outcome showed that the duration of illness has a strong impact on neurocognitive functioning in speed of processing (F>2.4) and attention (F>2.8). But INT intervention compared to TAU only had a significant effect in more chronically ill patients of MLT and LT, but not in younger patients in EC. In social cognitive domains, only the EC group showed a significant change in attribution (hostility; F>2.5), LT and MLT groups did not. However, no differences between the 3 groups were evident in memory, problem solving, and emotion perception. Regarding more distal outcome, LT patients had more symptoms compared to EC (F>4.4). Finally, EC patients showed higher improvements in psychosocial functioning compared to LT and MLT (F=1.8). Conclusions Against common expectations, long-term, more chronically ill patients showed higher effects in basal cognitive functions compared to younger patients and patients without any active therapy (TAU). On the other hand, early-course patients had a greater potential to change in attribution, symptoms and psychosocial functioning. Consequently, more integrated therapy offers are also recommended for long-term course schizophrenia patients.

Internal and external effects on cognition: Evidence from memory training in very preterm-born children and cognition in patients with carotid artery stenosis before and after treatment

The present synopsis aims to integrate one study about memory training in very preterm-born children and two studies about cognition in patients with carotid artery stenosis before and after treatments. Preterm-born children are at increased risk of cognitive deficits and behavioural problems compared with peers born at term. This thesis determined whether memory training would improve cognitive functions in school-age very preterm-born children. Memory strategy training produced significant improvements in trained and non-trained cognitive functions; a core working memory training revealed significant effects on short-term memory and working memory tasks. Six months after training, children in both training groups showed better working memory performance than children in the waiting control group. This is evidence that memory training – an external influence on cognition – induces plastic changes in very preterm-born children. Patients with carotid artery stenosis are known to be at increased risk of cognitive impairment. We showed that patients with symptomatic or asymptomatic carotid artery stenosis were at higher risk for cognitive deficits than expected in a normative sample. This thesis seeks to link cognitive plasticity to internal factors like carotid stenosis. An external factor, which influences blood flow to the brain is the nature of the carotid artery stenosis treatment. Research on the effects of carotid artery stenosis treatment on cognition has produced inconsistent results. We found significant improvement in frontal lobe functions, visual memory and motor speed one year after treatment independent of the treatment type (best medical treatment, carotid artery stenting, carotid artery endarterectomy); providing evidence for ‘treatment-induced’ cognitive plasticity. Baseline performance was negatively associated with improvement in various cognitive functions after training in very preterm-born children and after treatment in patients with carotid artery stenosis. The present synopsis aims to integrate these findings into the current and relevant literature, and discuss consequences as well as methodological considerations resulting from the studies constituting the thesis at hand.