This thesis presents a parallel, dynamic programming based model which is deployed on the GPU of a system to accelerate the solving of optimisation problems. This is achieved by simultaneously running GPU based computations, and memory transactions, allowing computation to never pause, and overcoming the memory constraints of solving large problem instances. Due to this some optimisation problems, which are currently not solved in an exact manner for real world sized instances due to their complexity, are moved into the solvable realm. The model is implemented to solve, a range of different test problems, where artificially constructed test data is used to ensure good performance even in the worst cases. Through this extensive testing, we can be confident the model will perform well when used to solve real world test cases. Testing of the model was carried out using a range of different implementation parameters in relation to deployment on the GPU, in order to identify both optimal implementation parameters, and how the model will operate when running on different systems. All problems, when implemented in parallel using the model, show run-time improvements compared to the sequential implementations, in some instances up to hundreds of times faster, but more importantly also show high efficiency metrics for the utilisation of GPU resources. Throughout testing emphasis has been placed on GPU based metrics to ensure the wider generic applicability of the model. Finally, the parallel model allows for new problems to be defined through the use of a simple file format, enabling wider usage of the model.

Storytelling has been used throughout the ages as means of communication, conveying and transmitting knowledge from one person to another and from one generation to the next. In various domains, formulating of messages, ideas, or findings into a story has proven its efficiency in making them comprehensible, memorable, and engaging. Information Visualization as an academic field also utilises the power of storytelling to make visualizations more understandable and interesting for a variety of audiences. Although storytelling has been a a topic of interest in information visualization for some time, little or no empirical evaluations exist to compare different approaches to storytelling through information visualization. There is also a need for work that addresses in depth some criteria and techniques of storytelling such as transition types in visual stories in general and data-driven stories in particular. Two sets of experiments were conducted to explore how two different models of information visualization delivery influence narratives constructed by audiences. The first model involves direct narrative by a speaker using visualization software to tell a data-story, while the second involves constructing a story by interactively exploring the visualization software. The first set of experiments is a within-subject experiment with 13 participants, and the second set of experiments is a between-subject experiment with 32 participants. In both rounds, an open-ended questionnaire was used in controlled laboratory settings in which the primary goal was to collect a number of written data-stories derived from the two models. The data-stories and answers written by the participants were all analysed and coded using data-driven and pre-set themes. The themes include reported impressions about the story, insight types reported, narrative structures, curiosity about the data, and ease of telling a story after experimenting with each model. The findings show that while the delivery model has no effect on how easy or difficult the participants found telling a data story to be, it does have an effect on the tendency to identify and use outliers' insights in the data story if they are not distracted by direct narration. It also affects the narrative structure and depth of the data story. Examining some more mature domains of visual storytelling, such as films and comics, can be highly beneficial to this new sub-field of data visualization. In the research in hand, a taxonomy of panel-to-panel transitions in comics has been used. The definitions of the components of this taxonomy have been refined to reflect the nature of data-stories in information visualization, and the taxonomy has then been used in coding a number of VAST Challenge videos. The transitions used in each video have been represented graphically with a diagram that shows how the information was added incrementally in order to tell a story that answers a particular question. A number of issues have been taken into account when coding transitions in each video and when designing and creating the visual diagram, such as nested transitions, the use of sub-topics, and delayed transitions. The major contribution of this part of the research is the provision of a taxonomy and description of transition types in the context of narrative visualization, an explanation of how this taxonomy can be used to code transitions in narrative visualization, and a visual summary as a means of summarising that coding. The approaches to data analysis and different storytelling axes, both in the experimental work and in proposing and applying the framework of transition types used, can be usefully applied to other studies and comparisons of storytelling approaches.

In the modern world of mobile computing and ubiquitous technology, society is able to interact with technology in new and fascinating ways. To help provide an improved user experience, mobile software should be able to adapt itself to suit the user. By monitoring context information based on the environment and user, the application can better meet the dynamic requirements of the user. Similarly, it is noticeable that programs can require different static changes to suit static requirements. This program commonality and variability can benefit from the use of Software Product Line Engineering, reusing artefacts over a set of similar programs, called a Software Product Line (SPL). Historically, SPLs are limited to handling static compile time adaptations. Dynamic Software Product Lines (DSPL) however, allow for the program configuration to change at runtime, allow for compile time and runtime adaptation to be developed in a single unified approach. While currently DSPLs provide methods for dealing with program logic adaptations, variability in the Graphical User Interface (GUI) has largely been neglected. Due to this, depending on the intended time to apply GUI adaptation, different approaches are required. The main goal of this work is to extend a unified representation of variability to the GUI, whereby GUI adaptation can be applied at compile time and at runtime. In this thesis, an approach to handling GUI adaptation within DSPLs, providing a unified representation of GUI variability is presented. The approach is based on Feature-Oriented Programming (FOP), enabling developers to implement GUI adaptation along with program logic in feature modules. This approach is applied to Document- Oriented GUIs, also known as GUI description languages. In addition to GUI unification, we present an approach to unifying context and feature modelling, and handling context dynamically at runtime, as features of the DSPL. This unification can allow for more dynamic and self-aware context acquisition. To validate our approach, we implemented tool support and middleware prototypes. These different artefacts are then tested using a combination of scenarios and scalability tests. This combination first helps demonstrate the versatility and its relevance of the different approach aspects. It further brings insight into how the approach scales with DSPL size.

In the last decade graphics processors (GPUs) have been extensively used to solve computationally intensive problems. A variety of GPU architectures by different hardware manufacturers have been shipped in a few years. OpenCL has been introduced as the standard cross-vendor programming framework for GPU computing. Writing and optimising OpenCL applications is a challenging task, the programmer has to take care of several low level details. This is even harder when the goal is to improve performance on a wide range of devices: OpenCL does not guarantee performance portability. In this thesis we focus on the analysis and the portability of compiler optimisations. We describe the implementation of a portable compiler transformation: thread-coarsening. The transformation increases the amount of work carried out by a single thread running on the GPU. The goal is to reduce the amount of redundant instructions executed by the parallel application. The first contribution is a technique to analyse performance improvements and degradations given by the compiler transformation, we study the changes of hardware performance counters when applying coarsening. In this way we identify the root causes of execution time variations due to coarsening. As second contribution, we study the relative performance of coarsening over multiple input sizes. We show that the speedups given by coarsening are stable for problem sizes larger than a threshold that we call saturation point. We exploit the existence of the saturation point to speedup iterative compilation. The last contribution of the work is the development of a machine learning technique that automatically selects a coarsening configuration that improves performance. The technique is based on an iterative model built using a neural network. The network is trained once for a GPU model and used for several programs. To prove the flexibility of our techniques, all our experiments have been deployed on multiple GPU models by different vendors.

The use of accelerator technology, particularly Graphics Processing Units (GPUs), for scientific computing has increased greatly over the last decade. While this technology allows larger and more complicated problems to be solved faster than before it also presents another opportunity: the real-time and interactive solution of problems. This work aims to investigate the progress that GPU technology has made towards allowing fluid-structure interaction (FSI) problems to be solved in real-time, and to facilitate user interaction with such a solver. A mesoscopic scale fluid flow solver is implemented on third generation nVidia ‘Kepler’ GPUs in two and three dimensions, and its performance studied and compared with existing literature. Following careful optimisation the solvers are found to be at least as efficient as existing work, reaching peak efficiencies of 93% compared with theoretical values. These solvers are then coupled with a novel immersed boundary method, allowing boundaries defined at arbitrary coordinates to interact with the structured fluid domain through a set of singular forces. The limiting factor of the performance of this method is found to be the integration of forces and velocities over the fluid and boundaries; the arbitrary location of boundary markers makes the memory accesses during these integrations largely random, leading to poor utilisation of the available memory bandwidth. In sample cases, the efficiency of the method is found to be as low as 2.7%, although in most scenarios this inefficiency is masked by the fact that the time taken to evolve the fluid flow dominates the overall execution time of the solver. Finally, techniques to visualise the fluid flow in-situ are implemented, and used to allow user interaction with the solvers. Initially this is achieved via keyboard and mouse to control the fluid properties and create boundaries within the fluid, and later by using an image based depth sensor to import real world geometry into the fluid. The work concludes that, for 2D problems, real-time interactive FSI solvers can be implemented on a single laptop-based GPU. In 3D the memory (both size and bandwidth) of the GPU limits the solver to relatively simple cases. Recommendations for future work to allow larger and more complicated test cases to be solved in real-time are then made to complete the work.

Ahierarchical version of the particle swarm optimization (PSO) metaheuristic is introduced in this paper. In the new method called H-PSO, the particles are arranged in a dynamic hierarchy that is used to define a neighborhood structure. Depending on the quality of their so-far best-found solution, the particles move up or down the hierarchy. This gives good particles that move up in the hierarchy a larger influence on the swarm. We introduce a variant of H-PSO, in which the shape of the hierarchy is dynamically adapted during the execution of the algorithm. Another variant is to assign different behavior to the individual particles with respect to their level in the hierarchy. H-PSO and its variants are tested on a commonly used set of optimization functions and are compared to PSO using different standard neighborhood schemes.

The rapid growth of digital video content in recent years has imposed the need for the development of technologies with the capability to produce condensed but semantically rich versions of the input video stream in an effective manner. Consequently, the topic of Video Summarisation is becoming increasingly popular in multimedia community and numerous video abstraction approaches have been proposed accordingly. These recommended techniques can be divided into two major categories of automatic and semi-automatic in accordance with the required level of human intervention in summarisation process. The fully-automated methods mainly adopt the low-level visual, aural and textual features alongside the mathematical and statistical algorithms in furtherance to extract the most significant segments of original video. However, the effectiveness of this type of techniques is restricted by a number of factors such as domain-dependency, computational expenses and the inability to understand the semantics of videos from low-level features. The second category of techniques however, attempts to alleviate the quality of summaries by involving humans in the abstraction process to bridge the semantic gap. Nonetheless, a single user’s subjectivity and other external contributing factors such as distraction will potentially deteriorate the performance of this group of approaches. Accordingly, in this thesis we have focused on the development of three user-centred effective video summarisation techniques that could be applied to different video categories and generate satisfactory results. According to our first proposed approach, a novel mechanism for a user-centred video summarisation has been presented for the scenarios in which multiple actors are employed in the video summarisation process in order to minimise the negative effects of sole user adoption. Based on our recommended algorithm, the video frames were initially scored by a group of video annotators ‘on the fly’. This was followed by averaging these assigned scores in order to generate a singular saliency score for each video frame and, finally, the highest scored video frames alongside the corresponding audio and textual contents were extracted to be included into the final summary. The effectiveness of our approach has been assessed by comparing the video summaries generated based on our approach against the results obtained from three existing automatic summarisation tools that adopt different modalities for abstraction purposes. The experimental results indicated that our proposed method is capable of delivering remarkable outcomes in terms of Overall Satisfaction and Precision with an acceptable Recall rate, indicating the usefulness of involving user input in the video summarisation process. In an attempt to provide a better user experience, we have proposed our personalised video summarisation method with an ability to customise the generated summaries in accordance with the viewers’ preferences. Accordingly, the end-user’s priority levels towards different video scenes were captured and utilised for updating the average scores previously assigned by the video annotators. Finally, our earlier proposed summarisation method was adopted to extract the most significant audio-visual content of the video. Experimental results indicated the capability of this approach to deliver superior outcomes compared with our previously proposed method and the three other automatic summarisation tools. Finally, we have attempted to reduce the required level of audience involvement for personalisation purposes by proposing a new method for producing personalised video summaries. Accordingly, SIFT visual features were adopted to identify the video scenes’ semantic categories. Fusing this retrieved data with pre-built users’ profiles, personalised video abstracts can be created. Experimental results showed the effectiveness of this method in delivering superior outcomes comparing to our previously recommended algorithm and the three other automatic summarisation techniques.

The recent advances in sensor and display technologies have brought upon the High Dynamic Range (HDR) imaging capability. The modern multiple exposure HDR sensors can achieve the dynamic range of 100-120 dB and LED and OLED display devices have contrast ratios of 10^5:1 to 10^6:1. Despite the above advances in technology the image/video compression algorithms and associated hardware are yet based on Standard Dynamic Range (SDR) technology, i.e. they operate within an effective dynamic range of up to 70 dB for 8 bit gamma corrected images. Further the existing infrastructure for content distribution is also designed for SDR, which creates interoperability problems with true HDR capture and display equipment. The current solutions for the above problem include tone mapping the HDR content to fit SDR. However this approach leads to image quality associated problems, when strong dynamic range compression is applied. Even though some HDR-only solutions have been proposed in literature, they are not interoperable with current SDR infrastructure and are thus typically used in closed systems. Given the above observations a research gap was identified in the need for efficient algorithms for the compression of still images and video, which are capable of storing full dynamic range and colour gamut of HDR images and at the same time backward compatible with existing SDR infrastructure. To improve the usability of SDR content it is vital that any such algorithms should accommodate different tone mapping operators, including those that are spatially non-uniform. In the course of the research presented in this thesis a novel two layer CODEC architecture is introduced for both HDR image and video coding. Further a universal and computationally efficient approximation of the tone mapping operator is developed and presented. It is shown that the use of perceptually uniform colourspaces for internal representation of pixel data enables improved compression efficiency of the algorithms. Further proposed novel approaches to the compression of metadata for the tone mapping operator is shown to improve compression performance for low bitrate video content. Multiple compression algorithms are designed, implemented and compared and quality-complexity trade-offs are identified. Finally practical aspects of implementing the developed algorithms are explored by automating the design space exploration flow and integrating the high level systems design framework with domain specific tools for synthesis and simulation of multiprocessor systems. The directions for further work are also presented.

Nous abordons le problème de la mise en correspondance de points dans des images pour calculer la pose d'une caméra par l'algorithme Perspective-n-Point (PnP). Nous calculons la carte 3D, c'est-à-dire les coordonnées 3D et les caractéristiques visuelles de quelques points dans l'environnement grâce à une procédure d'apprentissage hors ligne utilisant un ensemble d'images d'apprentissage. Étant donné une nouvelle image nous utilisons PnP à partir des coordonnées 2D dans l'image de points 3D détectés à l'aide de la carte 3D. Pendant la phase d'apprentissage nous groupons les descripteurs SIFT extraits des images d'apprentissage pour obtenir des collections de positions 2D dans ces images de quelques-uns des points 3D dans l'environnement. Le calcul de SFM (Structure From Motion) est effectué pour obtenir les coordonnées des points correspondants 3D. Pendant la phase de test, les descripteurs SIFT associés aux points 2D projection d'un point 3D de la carte sont utilisés pour reconnaître le point 3D dans une image donnée. Le cadre de travail est semblable à celui des mots visuels utilisés dans différents domaines de la vision par ordinateur. Pendant l'apprentissage, la formation des mots visuelle est effectuée via l'identification de groupes et pendant les tests des points 3D sont identifiés grâce à la reconnaissance des mots visuels. Nous menons des expériences avec des méthodes de formation différentes (k-means et mean-shift) et proposons un nouveau schéma pour la formation des mots visuels pour la phase d'apprentissage. Nous utilisons différentes règles de mise en correspondance, y compris quelques-unes des méthodes standards de classification supervisée pour effectuer la reconnaissance des mots visuels pendant la phase de test. Nous évaluons ces différentes stratégies dans les deux étapes. Afin d'assurer la robustesse aux variations de pose entre images d'apprentissage et images de test, nous explorons différentes façons d'intégrer les descripteurs SIFT extraits de vues synthétiques générées à partir des images d'apprentissage. Nous proposons également une stratégie d'accélération exacte pour l'algorithme mean-shift / We address the problem of establishing point correspondences in images for computing camera pose through Perspective-n-Point (PnP) algorithm. We compute the 3D map i.e. 3D coordinates and visual characteristics of some of the points in the environment through an offline training stage using a set of training images. Given a new test image we apply PnP using the 2D coordinates of 3D points in the image detected by using the 3D map. During the training stage we cluster the SIFT descriptors extracted from training images to obtain 2D-tracks of some of the 3D points in the environment. Each 2D-track consists of a set of 2D image coordinates of a single 3D point in different training images. SfM (Structure from Motion) is performed on these 2D-tracks to obtain the coordinates of the corresponding 3D points. During the test stage, the SIFT descriptors associated the 2D-track of a 3D point is used to recognize the 3D point in a given image. The overall process is similar to visual word framework used in different fields of computer vision. During training, visual word formation is performed through clustering and during testing 3D points are identified through visual word recognition. We experiment with different clustering schemes (k-means and mean-shift) and propose a novel scheme for visual word formation for training stage. We use different matching rules including some of the popular supervised pattern classification methods to perform visual word recognition during test stage. We evaluate these various matching strategies in both stages. In order to achieve robustness against pose variation between train and test images, we explore different ways of incorporating SIFT descriptors extracted from synthetic views generated from the training images. We also propose an exact acceleration strategy for mean-shift computation

Shadows are ubiquitous in image and video, and their removal is of interest in both Computer Vision and Graphics. In this thesis, four methods for interactive shadow removal from single images are presented. Their improvements are made in user interaction, quality and robustness of shadow removal. We also show our state-of-the-art ground truth data set with variable scene categories for shadow removal and applications for shadow editing and its extension to video data processing.