BU-CE-1201: PDF
Hypergraph-Partitioning-Based Models and Methods for Exploiting Cache Locality in Sparse-Matrix Vector Multiplication
The sparse matrix-vector multiplication (SpMxV) is a kernel operation widely used in iterative linearsolvers. The same sparse matrix is multiplied by a dense vector repeatedly in these solvers. Matrices with irregular sparsity patterns make it difficult to utilize cache locality effectively in SpMxV computations. In this work, we investigate single- and multiple-SpMxV frameworks for exploiting cache locality in SpMxV computations. For the single-SpMxV framework, we propose two cache-size-aware top-down row/column-reordering methods based on 1D and 2D sparse matrix partitioning by utilizing the column-net and enhancing the row-column-net hypergraph models of sparse matrices. The multiple-SpMxV framework depends on splitting a given matrix into a sum of multiple nonzero-disjoint matrices so that the SpMxV operation is performed as a sequence of multiple input- and output-dependent SpMxV operations. For an effective matrix splitting required in this framework, we propose a cache-size-aware top-down approach based on 2D sparse matrix partitioning by utilizing the row-column-net hypergraph model. For this framework, we also propose two methods for effective ordering of individual SpMxV operations. The primary objective in all of the three methods is to maximize the exploitation of temporal locality. We evaluate the validity of our models and methods on a wide range of sparse matrices using both cache-miss simulations and actual runs by using the OSKI. Experimental results show that proposed methods and models outperform state-of-the-art schemes.Keywords: cache locality, sparse matrices, matrix-vector multiplication, matrix reordering, computational hypergraph model, hypergraph partitioning, traveling salesman problem.
BU-CE-1202: PDF
Multilevel Segmentation of Histopathological Images using Cooccurrence of Tissue Objects: Supplementary Material
Digital pathology is becoming an increasingly important tool for automated biopsy analysis. Automated analysis of histopathological tissue images not only increases throughput but also improves reproducibility. The first step of this analysis usually involves the segmentation of a tissue into its homogeneous regions. This technical report contains the supplementary material for the multilevel segmentation algorithm that we developed for the purpose of histopathological tissue image segmentation.Keywords: Histopathological image analysis, multilevel segmentation, segmentation ensemble, texture, image segmentation
BU-CE-1203: PDF
rpPaToH: Replicated Partitioning Tool for Hypergraphs
Hypergraphs are widely used to model various problems from different domains. With respect to modeled problem domain, the utilized hypergraph partitioning models can either be directed or undirected. The quality of the partitions obtained using hypergraph partitioning can further be improved by using vertex or net replication. The replication in directional hypergraph partitioning models is a well investigated subject in VLSI domain supported by various algorithms and tools. However, replication in undirectional hypergraph partitioning models is an immature research area. To fill this gap, we propose novel algorithms for performing vertex replication in undirectional hypergraph partitioning models. Our approach is one-phase, i.e., replication is performed simultaneously with the partitioning. This is achieved by using an extension of the FM heuristic, called replicated FM (rFM), that support replication and unreplication operations in addition to move operations.This algorithm is used as the main refinement heuristic in the multilevel framework. Later, rFM is utilized in a recursive bipartitioning framework to obtain K-way partitions. Pin selection algorithms are proposed to compute the final cutsize values. These algorithms and methods are realized in a tool called rpPaToH that performs vertex replication in undirected hypergraphs. This technical report describes the replicated hypergraph partitioning in short and gives detailed information about how to use the rpPaToH tool.
Keywords: Replication, hypergraph, undirected, hypergraph partitioning, replicated hypergraph partitioning, iterative improvement heuristic, recursive bipartitioning.
BU-CE-1204: PDF
Visual Attention Models and Applications to 3D Computer Graphics (Ph. D. Thesis)
3D computer graphics, with the increasing technological and computational opportunities, have advanced to very high levels that it is possible to generate very realistic computer-generated scenes in real-time for games and other interactive environments. However, we cannot claim that computer graphics research has reached to its limits. Rendering photo-realistic scenes still cannot be achieved in real-time; and improving visual quality and decreasing computational costs are still research areas of great interest.Recent efforts in computer graphics have been directed towards exploiting principles of human visual perception to increase visual quality of rendering. This is natural since in computer graphics, the main source of evaluation is the judgment of people, which is based on their perception. In this thesis, our aim is to extend the use of perceptual principles in computer graphics. Our contribution is two-fold: First, we present several models to determine the visually important, salient, regions in a 3D scene. Secondly, we contribute to use of defnition of saliency metrics in computer graphics.
Human visual attention is composed of two components, the first component is the stimuli-oriented, bottom-up, visual attention; and the second component is task-oriented, top-down visual attention. The main difference between these components is the role of the user. In the top-down component, viewer's intention and task affect perception of the visual scene as opposed to the bottom-up component. We mostly investigate the bottom-up component where saliency resides.
We define saliency computation metrics for two types of graphical contents. Our first metric is applicable to 3D mesh models that are possibly animating, and it extracts saliency values for each vertex of the mesh models. The second metric we propose is applicable to animating objects and finds visually important objects due to their motion behaviours. In a third model, we present how to adapt the second metric for the animated 3D meshes.
Along with the metrics of saliency, we also present possible application areas and a perceptual method to accelerate stereoscopic rendering, which is based on binocular vision principles and makes use of saliency information in a stereoscopic rendering scene.
Each of the proposed models are evaluated with formal experiments. The proposed saliency metrics are evaluated via eye-tracker based experiments and the computationally salient regions are found to attract more attention in practice too. For the stereoscopic optimization part, we have performed a detailed experiment and verified our model of optimization.
In conclusion, this thesis extends the use of human visual system principles in 3D computer graphics, especially in terms of saliency.
Keywords: Computer Graphics, Visual Perception, Saliency, Visual Attention, Binocular Vision, Stereoscopy, Motion Perception.
BU-CE-1205: PDF
Psychological Parameters for Crowd Simulation: From Audiences to Mobs
In the social psychology literature, crowds are classified as audiences and mobs. Audiences are passive crowds, whereas mobs are active crowds with emotional, irrational and seemingly homogeneous behavior. In this study, we parameterize the common properties of mobs to create collective misbehavior. Because mobs are characterized by emotionality, we describe a framework that associates psychological components with individual agents comprising a crowd and yields emergent behaviors in the crowd as a whole. We demonstrate and evaluate two scenarios that realize the behavior of distinct mob types.Keywords: Crowd simulation, autonomous agents, simulation of affect, crowd taxonomy, mob behavior.
BU-CE-1206: PDF
On the Numerical Solution of Kronecker-based Infinite Level-Dependent QBD Processes
Infinite level-dependent quasi-birth-and-death (LDQBD) processes can be used to model Markovian systems with countably infinite multidimensional state spaces. Recently it has been shown that sums of Kronecker products can be used to represent the nonzero blocks of the transition rate matrix underlying an LDQBD process for models from stochastic chemical kinetics. This paper extends the form of the transition rates used recently so that a larger class of models including those of call centers can be analyzed for their steady-state. The challenge in the matrix analytic solution then is to compute conditional expected sojourn time matrices of the LDQBD model under low memory and time requirements after truncating its countably infinite state space judiciously. Results of numerical experiments are presented using a Kronecker-based matrix-analytic solution on models with two or more countably infinite dimensions and rules of thumb regarding better implementations are derived. In doing this, a more recent approach that reduces memory requirements further by enabling the computation of steady-state expectations without having to obtain the steady-state distribution is also considered.Keywords: Markov chain, level-dependent QBD process, Kronecker product, matrix analytic method, steady-state expectation, call center, stochastic chemical kinetics
BU-CE-1207: PDF
An Actuated Flexible Spinal Mechanism for a Bounding Quadrupedal Robot
Evolution and experience based learning have given animals body structures and motion capabilities to survive in the nature by achieving many complicated tasks. Among these animals, legged vertebrates use their musculoskeletal bodies up to the limits to achieve actions involving high speeds and agile maneuvers. Moreover the flexible spine plays a very important role in providing auxiliary power and dexterity for such dynamic behaviors. Robotics research tries to imitate such dynamic abilities on mechanical platforms. However, most existing robots performing these dynamic motions does not include such a flexible spine architecture. In this thesis we investigate how quadrupedal bounding can be achieved with the help of an actuated flexible spine. Depending upon biological correspondences we first present a novel quadruped robot model with an actuated spine and relate it with our proposed new bounding gait controller model. By optimizing our model and a standard stiff backed model via repetitive parametric methods, we investigate the role of spinal actuation on the performance enhancements of the flexible model. By achieving higher ground speeds and hopping heights we discuss the relations between flexible body structure and stride properties of a dynamic bounding gait. Furthermore, we present an analytical model of the proposed robot structure along with the spinal architecture and analyze the dynamics and active forces on the overall system. By gathering simulation results we question how such a flexible spine system can be improved to achieve higher performances during dynamic gaits.Keywords: Bio-inspired robotics, Legged robots, Dynamic locomotion, Quadrupedal bounding, Spinal actuation, Gait optimization
BU-CE-1208: PDF
Representation, Editing and Real-time Visualization of Complex 3D Terrains
Terrain rendering is a crucial part of many real-time computer graphics applications such as video games and visual simulations. It provides the main frame-of-reference for the observer and constitutes the basis of an imaginary or simulated world that encases the observer. Storing and rendering terrain models in real-time applications usually require a specialized approach due to the sheer magnitude of data available and the level of detail demanded. The easiest way to process and visualize such large amounts of data in real-time is to constrain the terrain model in several ways. This process of regularization decreases the amount of data to be processed and also the amount of processing power needed at the cost of expressivity and the ability to create interesting terrains.The most popular terrain representation, by far, used by modern real-time graphics applications is a regular 2D grid where the vertices are displaced in a third dimension by a displacement map, conventionally called a height map. It is the simplest and fastest possible terrain representation, but it is not possible to represent complex terrain models that include interesting terrain features such as caves, overhangs, cliffs and arches using a simple 2D grid and a height map. We propose a novel terrain representation combining the voxel and height map approaches that is expressive enough to allow creating complex terrains with caves, overhangs, cliffs and arches, and efficient enough to allow terrain editing, deformations and rendering in real-time. We also explore how to apply lighting, texturing, shadowing and level-of-detail to the proposed terrain representation.
Keywords: Terrain representation, terrain visualization, caves, overhangs, clis, voxel terrain, height map terrain.