BU-CE-0801: PDF
Counteracting Free Riding in Pure Peer-to-Peer Networks (Ph. D. Thesis)
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: PDF
Understanding Human Motion: Recognition and Retrieval of Human Activities (Ph. D. Thesis)
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: PDF
Animated Mesh Simplification Based on Saliency Metrics (M. Sc. Thesis)
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: PDF
Real-Time Parameterized Locomotion Generation (M. Sc. Thesis)
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: PDF
Modeling and Populating Virtual Cities: Automatic Production of Building Models and Emergency Crowd Simulation (M. Sc. Thesis)
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: PDF
Query Processing for an MPEG-7 Compliant Video Database (M. Sc. Thesis)
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: PDF
Predicting Risk of Mortality in Patients Undergoing Cardiovascular Surgery (M. Sc. Thesis)
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: PDF
Integrated Segmentation and Recognition of Connected Ottoman Script (M. Sc. Thesis)
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).
BU-CE-0809: PDF
Qualitative Test-Cost Sensitive Classification (M. Sc. Thesis)
Decision making is a procedure for selecting the best action among several alternatives. In many real-world problems, decision has to be taken under the circumstances in which one has to pay to acquire information. In this thesis, we propose a new framework for test-cost sensitive classification that considers the misclassification cost together with the cost of feature extraction, which arises from the effort of acquiring features. This proposed framework introduces two new concepts to test-cost sensitive learning for better modeling the real-world problems: qualitativeness and consistency.First, this framework introduces the incorporation of qualitative costs into the problem formulation. This incorporation becomes important for many real world problems, from finance to medical diagnosis, since the relation between the misclassification cost and the cost of feature extraction could be expressed only roughly and typically in terms of ordinal relations for these problems. For example, in cancer diagnosis, it could be expressed that the cost of misdiagnosis is larger than the cost of a medical test. However, in the test-cost sensitive classification literature, the misclassification cost and the cost of feature extraction are combined quantitatively to obtain a single loss/utility value, which requires expressing the relation between these costs as a precise quantitative number.
Second, it considers the consistency between the current information and the information after feature extraction to decide which features to extract. For example, it does not extract a new feature if it brings no new information but just confirms the current one; in other words, if the new feature is totally consistent with the current information. By doing so, the proposed framework could significantly decrease the cost of feature extraction, and hence, the overall cost without decreasing the classification accuracy. Such consistency behavior has not been considered in the previous test-cost sensitive literature.
We conduct our experiments on three medical data sets and the results demonstrate that the proposed framework significantly decreases the feature extraction cost without decreasing the classification accuracy.
Keywords: Cost-sensitive learning, qualitative decision theory, feature extraction cost, feature selection, decision theory.