BU-CE-0701: PDF
Obtaining Triangular Diagonal Blocks in Sparse Matrices Using Cutsets
The paper proposes an algorithm which computes a (2 x 2) block partition of an irreducible, sparse matrix with a zero-free diagonal so that one of the diagonal blocks is triangular. The algorithm works by computing a cutset of the directed graph associated with the off-diagonal part of the matrix and is linear in the number of nonzeros therein. The proposed algorithm is then extended to reducible, sparse matrices with a zero-free diagonal. Experiments on benchmark unsymmetric matrices show that, in many cases the order of the triangular block can be increased by using another algorithm for computing cutsets from the literature, which is based on a greedy randomized adaptive search procedure; however, this is not efficient timewise unless the matrix is relatively small. A block iterative solver based on the partition returned by the proposed algorithm is compared with an industrial strength direct solver for time, space, and accuracy. Results indicate that there are cases in which it is advantageous to compute and use block partitions based on cutsets.Keywords: Sparse matrices, triangular blocks, cutsets
BU-CE-0702: PDF
Modeling Spatial Relationships in Images
Spatial information is a crucial aspect of image understanding for modeling context as well as resolving the uncertainties caused by the ambiguities in low-level features. We describe flexible, intuitive and efficient methods for modeling pairwise directional spatial relationships and the ternary between relation using fuzzy mathematical morphology. First, a fuzzy landscape is constructed where each point is assigned a value that quantifies its relative position according to the reference object(s) and the type of relationship. Then, the degree of satisfaction of this relation by a target object is computed by integrating the corresponding landscape over the support of the target region. Our models support sensitivity to visibility to handle areas that are partially enclosed by objects and are not visible from image points along the direction of interest. They can also cope with the cases where one object is significantly spatially extended relative to others. Experiments using synthetic and real images show that our models produce more intuitive results than other techniques.Keywords: Spatial relationships, mathematical morphology, fuzzy sets, relative position
BU-CE-0703: PDF
A Hybrid Hair Model Using Three Dimensional Fuzzy Textures (M. Sc. Thesis)
Human hair modeling and rendering have always been a challenging topic in computer graphics. The techniques for human hair modeling consist of explicit geometric models as well as volume density models. Recently, hybrid cluster models have also been successful in this subject. In this study, we present a novel three dimensional texture model called 3D Fuzzy Textures and algorithms to generate them. Then, we use the developed model along with a cluster model to give human hair complex hairstyles such as curly and wavy styles. Our model requires little user effort to model curly and wavy hair styles. With this study, we aim at eliminating the drawbacks of the volume density model and the cluster hair model with 3D fuzzy textures. A three dimensional cylindrical texture mapping function is introduced for mapping purposes. Current generation graphics hardware is utilized in the design of rendering system enabling high performance rendering.Keywords: Hair modeling, hair rendering, curly hair, wavy hair, cluster hair model, volume density model, 3D texture, 3D texture mapping
BU-CE-0704: PDF
Online Text Categorization Using Genetic Algorithms
Genetic Algorithms can be used to classify documents by building chromosomes from document features. This paper demonstrates to use word lists as chromosomes and updating them as new documents are retrieved. The scheme uses a voting procedure to determine the membership of a document to a category and update the chromosomes with crossover and mutation.Keywords: Genetic Algorithms, Text Classification, Voting.
BU-CE-0705: PDF
Kronecker Representation and Decompositional Analysis of Closed Queueing Networks with Phase-type Service Distributions and Arbitrary Buffer Sizes (M. Sc. Thesis)
This thesis extends two approximative fixed-point iterative methods based on decomposition for closed queueing networks (QNs) with Coxian service distributions and arbitrary buffer sizes from the literature to include phase-type service distributions. It shows how the irreducible Markov chain associated with each subnetwork in the decomposition can be represented hierarchically using Kronecker products. The proposed methods are implemented in a software tool, which is capable of computing the steadyby a multilevel method at each fixedcompared with others, one being the multilevel method for the closed QN itself, for accuracy and efficiency on a number of examples using the tool, and their convergence properties are discussed. Numerical results indicate that there is a niche among the problems considered which is filled by the two approximative fixed point iterative methods.Keywords: Closed queueing networks, Phase-type service distributions, Kronecker representations, Network decomposition, Fixed-point iteration, Multilevel methods.
BU-CE-0706: PDF
Visualization of Urban Environments (Ph. D. Thesis)
Modeling and visualization of large geometric environments is a popular research area in computer graphics. In this dissertation, a framework for modeling and stereoscopic visualization of large and complex urban environments is presented. The occlusion culling and view-frustum culling is performed to eliminate most of the geometry that do not contribute to the user.s final view. For the occlusion culling process, the shrinking method is employed but performed using a novel Minkowski-difference-based approach. In order to represent partial visibility, a novel building representation method, called the slice-wise representation is developed. This method is able to represent the preprocessed partial visibility with huge reductions in the storage requirement. The resultant visibility list is rendered using a graphics-processing-unit-based algorithm, which perfectly fits into the proposed slice-wise representation. The stereoscopic visualization depends on the calculated eye positions during walkthrough and the visibility lists for both eyes are determined using the preprocessed occlusion information. The view-frustum culling operation is performed once instead of two for both eyes. The proposed algorithms were implemented on personal computers. Performance experiments show that, the proposed occlusion culling method and the usage of the slice-wise representation increase the frame rate performance by 81%; the graphics-processing-unit-based display algorithm increases it by an additional 315% and decrease the storage requirement by 97% as compared to occlusion culling using building-level granularity and not using the graphics hardware. We show that, a smooth and real-time visualization of large and complex urban environments can be achieved by using the proposed framework.Keywords: Stereoscopic visualization, slice-wise representation, space subdivision, octree, occlusion culling, occluder shrinking, Minkowski difference, fromregion visibility, urban visualization, visibility processing.
BU-CE-0707: PDF
A link-based storage scheme for efficient aggregate query processing on clustered road networks
The need to have efficient storage schemes for spatial networks is apparent when the volume of query processing in some road networks (e.g., the navigation systems) is considered. Specifically, under the assumption that the road network is stored in a central server, the adjacent data elements in the network must be clustered on the disk in such a way that the number of disk page accesses is kept minimal during the processing of network queries. In this work, we introduce the link-based storage scheme for clustered road networks and compare it with the previously proposed junction-based storage scheme. In order to investigate the performance of aggregate network queries in clustered spatial networks, we extend our recently proposed clustering hypergraph model from junction-based storage to link-based storage. We propose techniques for additional storage savings in bidirectional networks that make the link-based storage scheme even more preferable in terms of the storage efficiency. We evaluate the performance of our link-based storage scheme against the junction-based storage scheme both theoretically and empirically. The results of the experiments conducted on a wide range of road network datasets show that the link-based storage scheme is preferable in terms of both storage and query processing efficiency.Keywords: Storage management, spatial databases and GIS, clustering, hypergraphs.
BU-CE-0708: PDF
A Scenario-Based Video Surveillance Data Modeling and Querying System
Automated video surveillance has emerged as a trendy application domain in recent years, and accessing the semantic content of surveillance video has become a challenging research area. The results of a considerable amount of research dealing with automated access to video surveillance have appeared in the literature. However, event models and content-based access to surveillance video have significant semantic gaps remaining unfilled. In this paper, we propose a scenario-based querying and retrieval model for video surveillance archives. In our model, a scenario is specified as a sequence of event predicates, that can be enriched with object-based low-level features. Our model also provides support for inverse querying, which can be considered as a tool for after-the-fact type of activity analysis. We have devised a visual query specification interface to ease the scenario-based query specification process. It is shown through performance experiments that our system has an effective expressive power and satisfactory retrieval accuracy in video surveillance.Keywords: video surveillance, scenario-based querying and retrieval, event annotation, object classification.
BU-CE-0709: PDF
Combined Filtering and Keyframe Reduction For Motion Capture Data (M. Sc. Thesis)
Two new methods for combined filtering and key-frame reduction of motion capture data are proposed. Filtering of motion capture data is necessary to eliminate any jitter introduced by a motion capture system. Although jitter removal is needed to obtain a more realistic animation, it may result in an over-smoothed motion data if it is not done properly. Key-frame reduction, on the other hand, allows animators to easily edit motion data by representing animation curves with a significantly smaller number of key frames. One of the proposed techniques achieves key frame reduction and jitter removal simultaneously by fitting a Hermite curve to motion capture data using dynamic programming. Another method is to use curve simplification algorithms on the motion capture data until the desired reduction is reached. In this research, the results of these algorithms are evaluated and compared. Both subjective and objective results are presented.Keywords: Motion capture, keyframe reduction, curve fitting, curve simplification, noise filtering.