All technical report files are in compressed (gzip) postscript format.
The file names are of the sort BU-CE-YYXX.pdf
BU-CE-0701
TITLE:
Obtaining Triangular Diagonal Blocks in Sparse Matrices Using Cutsets
AUTHORS: Tugrul Dayar
ABSTRACT:
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
TITLE:
Modeling Spatial Relationships in Images
AUTHORS: R. Gokberk Cinbis, Selim Aksoy
ABSTRACT:
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
TITLE:
A Hybrid Hair Model Using Three Dimensional Fuzzy Textures
AUTHORS: M. Erol Aran
ABSTRACT:
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
TITLE:
Online Text Categorization Using Genetic Algorithms
AUTHORS: I. Emre Sahin
ABSTRACT:
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
TITLE:
Kronecker Representation and Decompositional Analysis of
Closed Queueing Networks with Phase-type Service Distributions
and Arbitrary Buffer Sizes
AUTHORS: Akin Meric
ABSTRACT:
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
TITLE:
Visualization of Urban Environments
AUTHORS: Turker Yilmaz
ABSTRACT:
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
TITLE:
A link-based storage scheme for efficient aggregate query processing
on clustered road networks
AUTHORS: Engin Demir, Cevdet Aykanat, B. Barla Cambazoglu
ABSTRACT:
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
TITLE:
A Scenario-Based Video Surveillance Data Modeling and Querying System
AUTHORS: Ediz Saykol, Ugur Gudukbay, Ozgur Ulusoy
ABSTRACT:
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
TITLE:
Combined Filtering and Keyframe Reduction For Motion Capture Data
AUTHOR: Onur Önder
ABSTRACT:
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.