Technical Reports Published in 2008



BU-CE-0801

TITLE: Counteracting Free Riding in Pure Peer-to-Peer Networks
AUTHOR: K. Murat Karakaya

ABSTRACT: The peer-to-peer (P2P) network paradigm has attracted a significant amount of interest as a popular and successful alternative to traditional client-server model for resource sharing and content distribution. However, researchers have observed the existence of high degrees of free riding in P2P networks which poses a serious threat to effectiveness and efficient operation of these networks, and hence to their future. Therefore, eliminating or reducing the impact of free riding on P2P networks has become an important issue to investigate and a considerable amount of research has been conducted on it.

In this thesis, we propose two novel solutions to reduce the adverse effects of free riding on P2P networks and to motivate peers to contribute to P2P networks. These solutions are also intended to lead to performance gains for contributing peers and to penalize free riders. As the first solution, we propose a distributed and localized scheme, called Detect and Punish Method (DPM), which depends on detection and punishment of free riders. Our second solution to the free riding problem is a connection-time protocol, called P2P Connection Management Protocol (PCMP), which is based on controlling and managing link establishments among peers according to their contributions.

To evaluate the proposed solutions and compare them with other alternatives, we developed a new P2P network simulator and conducted extensive simulation experiments. Our simulation results show that employing our solutions in a P2P network considerably reduces the adverse effects of free riding and improves the overall performance of the network. Furthermore, we observed that P2P networks utilizing the proposed solutions become more robust and scalable.

Keywords: Free riding, Peer-to-Peer networks, distributed computing, performance evaluation.


BU-CE-0802

TITLE: Understanding Human Motion: Recognition and Retrieval of Human Activities
AUTHOR: Nazli Ikizler

ABSTRACT: Within the ever-growing video archives is a vast amount of interesting information regarding human action/activities. In this thesis, we approach the problem of extracting this information and understanding human motion from a computer vision perspective. We propose solutions for two distinct scenarios, ordered from simple to complex. In the first scenario, we deal with the problem of single action recognition in relatively simple settings. We believe that human pose encapsulates many useful clues for recognizing the ongoing action, and we can represent this shape information for 2D single actions in very compact forms, before going into details of complex modeling. We show that high-accuracy single human action recognition is possible 1) using spatial oriented histograms of rectangular regions when the silhouette is extractable, 2) using the distribution of boundary-fitted lines when the silhouette information is missing. We demonstrate that, inside videos, we can further improve recognition accuracy by means of adding local and global motion information. We also show that within a discriminative framework, shape information is quite useful even in the case of human action recognition in still images.

Our second scenario involves recognition and retrieval of complex human activities within more complicated settings, like the presence of changing background and viewpoints. We describe a method of representing human activities in 3D that allows a collection of motions to be queried without examples, using a simple and effective query language. Our approach is based on units of activity at segments of the body, that can be composed across time and across the body to produce complex queries. The presence of search units is inferred automatically by tracking the body, lifting the tracks to 3D and comparing to models trained using motion capture data. Our models of short time scale limb behaviour are built using labelled motion capture set. Our query language makes use of finite state automata and requires simple text encoding and no visual examples. We show results for a large range of queries applied to a collection of complex motion and activity. We compare with discriminative methods applied to tracker data; our method offers significantly improved performance. We show experimental evidence that our method is robust to view direction and is unaffected by some important changes of clothing.

Keywords: Human motion, action recognition, activity recognition, activity retrieval, image and video processing, classification.


BU-CE-0803

TITLE: Animated Mesh Simplification Based on Saliency Metrics
AUTHOR: Ahmet Tolgay

ABSTRACT: Mesh saliency identifies the visually important parts of a mesh. Mesh simplification algorithms using mesh saliency as simplification criterion preserve the salient features of a static 3D model. In this thesis, we propose a saliency measure that will be used to simplify animated 3D models. This saliency measure uses the acceleration and deceleration information about a dynamic 3D mesh in addition to the saliency information for static meshes. This provides the preservation of sharp features and visually important cues during animation. Since oscillating motions are also important in determining saliency, we propose a technique to detect oscillating motions and incorporate it into the saliency based animated model simplification algorithm. The proposed technique is experimented on animated models making oscillating motions and promising visual results are obtained.

Keywords: Simplification, animation, mesh saliency, deformation.


BU-CE-0804

TITLE: Real-Time Parameterized Locomotion Generation
AUTHOR: Muzaffer Akbay

ABSTRACT: Reuse and blending of captured motions for creating realistic motions of human body is considered as one of the challenging problems in animation and computer graphics. Locomotion (walking, running and jogging) is one of the most common types of daily human motion. Based on blending of multiple motions, we propose a two-stage approach for generating locomotion according to user-specified parameters, such as linear and angular velocities. Starting from a large dataset of various motions, we construct a motion graph of similar short motion segments. This process includes the selection of motions according to a set of predefined criteria, the correction of errors on foot positioning, pre-adjustments, motion synchronization, and transition partitioning. In the second stage, we generate an animation according to the specified parameters by following a path on the graph during run-time, which can be performed in real-time. Two different blending techniques are used at this step depending on the number of the input motions: blending based on scattered data interpolation and blending based on linear interpolation. Our approach provides an expandable and efficient motion generation system, which can be used for real time applications.

Keywords: Animation, data scattered interpolation, blending, locomotion.


BU-CE-0805

TITLE: Modeling and Populating Virtual Cities: Automatic Production of Building Models and Emergency Crowd Simulation
AUTHOR: Oguzcan Oguz

ABSTRACT: In this thesis, we present an automatic building generation method based on procedural modeling approach, and a crowd animation system that simulates a crowd of pedestrians inside a city. While modeling the buildings, to achieve complex and consistent geometries we use shape grammars. The derivation process incorporates randomness so the produced models have the desired variation. The end shapes of the building models could be defined in a certain extent by the derivation rules. The behavior of human crowds inside a city is affected by the simulation scenario. In this thesis, we specifically intend to simulate the virtual crowds in emergency situations caused by an incident, such as a fire, an explosion, or a terrorist attack. We prefer to use a continuum dynamics-based approach to simulate the escaping crowd, which produces more efficient simulations than the agent-based approaches. Only the close proximity of the incident region, which includes the crowd affected by the incident, is simulated. In order to speed up the animation and visualization of the resulting simulation, we employ an offline occlusion culling technique. During runtime, we animate and render a pedestrian model only if it is visible to the user. In the pre-processing stage, the navigable area of the scene is decomposed into a grid of cells and the from-region visibility of these cells is computed with the help of hardware occlusion queries.

Keywords: Procedural modeling, emergency, crowd simulation, crowd animation, occlusion culling, from-region visibility.


BU-CE-0806

TITLE: Query Processing for an MPEG-7 Compliant Video Database
AUTHOR: Hayati Çam

ABSTRACT: Based on the recent advancements in multimedia, communication, and storage technologies, the amount of audio-visual content stored is increased dramatically. The need to organize and access the growing multimedia content led researchers to develop multimedia database management systems. However, each system has its own way of describing the multimedia content that disables interoperability among other systems. To overcome this problem and to be able to standardize the description of audio-visual content stored in those databases, MPEG-7 standard has been developed by MPEG (Moving Picture Experts Group).

In this thesis, a query language and a query processor for an MPEG-7 compliant video database system is proposed. The query processor consists of three main modules: query parsing module, query execution module, and result fusion module. The query parsing module parses the XML based query and divides it into subqueries. Each sub-query is then executed with related query execution module and the final result is obtained by fusing the results of the sub-queries according to user defined weights. The prototype video database system BilVideo v2.0, which is formed as a result of this thesis work, supports spatio-temporal and low level feature queries that contain any weighted combination of keyword, temporal, spatial, trajectory, and low level visual feature (color, shape and texture) queries. Compatibility with MPEG-7, low-level visual query support, and weighted result fusion feature are the major factors that highly differentiate between BilVideo v2.0 and its predecessor, BilVideo.

Keywords: MPEG-7, XML databases, video databases, multimedia databases, query processing, content-based retrieval, video query languages.


BU-CE-0807

TITLE: Predicting Risk of Mortality in Patients Undergoing Cardiovascular Surgery
AUTHOR: Aysen Tunca

ABSTRACT: It is very important to inform the patients and their relatives about the risk of mortality before a cardiovascular operation. For this respect, a model called EuroSCORE (The European System for Cardiac Operative Risk Evaluation) has been developed by European cardiovascular surgeons. This system gives the risk of mortality during or 30 days after the operation, based on the values of some parameters measured before the operation. The model used by EuroSCORE has been developed by statistical data gathered from large number of operations performed in Europe.

Even though due to the surgical techniques that have been developed recently and the risk of mortality has been reduced in a large extent, predicting that risk as accurately as possible is still primary concern for the patients and their relatives in cardiovascular operations. The risk of operation also essentially tells the surgeon how a patient with similar comorbidity would be expected to fare based on a standard care. The risk of patient is also important for the health insurance companies, both public or private. In the context of this project, a model that can be used for mortality is developed.

In this research project, a database system for storing data about cardiovascular operations performed in Turkish hospitals, a web application for gathering data, and a machine learning system on this database to learn a risk model, similar to EuroSCORE, are developed. This thesis proposes a risk estimation system for predicting the risk of mortality in patients undergoing cardiovascular operations by maximizing the Area under the Receiver Operating Characteristic (ROC) Curve (AUC).

When the genetic characteristics and life styles of Turkish patients are taken into consideration, it is highly probable that the mortality risks of Turkish patients may be dierent than European patients. This thesis also intends to investigate this issue.

Keywords: Machine learning, ROC, AUC, risk estimation, cardiovascular operation, data mining.


BU-CE-0808

TITLE: Integrated Segmentation and Recognition of Connected Ottoman Script
AUTHOR: Ismet Zeki Yalniz

ABSTRACT: In this thesis, a novel context-sensitive segmentation and recognition method for connected letters in Ottoman script is proposed. This method first extracts a set of possible segments from a connected script and determines the candidate letters to which extracted segments are most similar. Next, a function is defined for scoring each different syntactically correct sequence of these candidate letters. To find the candidate letter sequence that maximizes the score function, a directed acyclic graph is constructed. The letters are finally recognized by computing the longest path in this graph. Experiments using a collection of printed Ottoman documents reveal that the proposed method provides very high precision and recall figures in terms of character recognition. In a further set of experiments we also demonstrate that the framework can be used as a building block for an information retrieval system for digital Ottoman archives.

Keywords: Optical character recognition (OCR), segmentation and recognition of connected scripts, connected scripts, information retrieval (IR).