Technical Reports Published in 2003

BU-CE-0301: PDF

Maximizing Benefit of Classifications Using Feature Intervals

Nazlı Ikizler and H. Altay Güvenir

There is a great need for classification methods that can properly handle asymmetric cost and benefit constraints of classifications. In this study, we aim to emphasize the importance of classification benefits by means of a new classification algorithm, Benefit Maximizing classifier with Feature Intervals (BMFI) that uses feature projection based knowledge representation. Empirical results show that BMFI has promising performance compared to recent cost-sensitive algorithms in terms of benefit gained.

BU-CE-0302: PDF

Extraction of 3D Navigation Space In Virtual Urban Environments

Türker Yılmaz and Uğur Güdükbay

Urban scenes are one class of complex geometrical environments in computer graphics. In order to develop navigation systems for urban sceneries, extraction and cellulization of navigation space is one of the most commonly used technique providing a suitable structure for visibility computations. Surprisingly, there is not much work done for the extraction of the navigable area automatically. Urban models, except the ones where the building footprints are used to generate the model, generally lack of navigation space information. Because of this, it is hard to extract and discretize the navigable area for complex urban scenery. In this paper, we propose an algorithm for the extraction of navigation space for urban scenes in three-dimensions (3D). Our navigation space extraction algorithm works for scenes, where the buildings are in high complexity and the virtual scene is constructed by populating these buildings without making any assumptions. The building models may have pillars or holes where seeing through them is also possible. Besides, for the urban data acquired from different sources which may contain errors, our approach provides a simple and efficient way of discretizing both navigable space and the model itself. Furthermore, terrain height field information can be extracted from the resultant structure, hence providing a way to implement urban navigation systems including terrains.

Keywords: Urban visualization, occlusion culling, cellulization, 3D navigation, view-cells.

BU-CE-0304: PDF

Feature Dependency in Benefit Maximization: A Case Study in the Evaluation of Bank Loan Applications

Nazlı Ikizler and H. Altay Güvenir

In most of the real-world domains, benefit and costs of classifications can be dependent on the characteristics of individual examples. In such cases, there is no static benefit matrix available in the domain and each classification benefit is calculated separately. This situation, called feature dependency, is evaluated in the framework of our newly proposed classification algorithm Benefit Maximizing classifier with Feature Intervals (BMFI) that uses feature projection based knowledge representation. This new approach has been evaluated over bank loan applications and experimental results are presented.

Keywords: Machine learning, classification, cost-sensitivity, feature projections.

BU-CE-0305: PDF

Feature Projection Based Rule Classification

Tolga Aydın and H. Altay Güvenir

Due to the increase in data mining research and applications, selection of interesting rules among a huge number of learned rules is an important task in data mining applications. In this paper, the metrics for the interestingness of a rule is investigated and an algorithm that can classify the learned rules according to their interestingness is developed. Classification algorithms were designed to maximize the number of correctly classified instances, given a set of unseen test cases. Furthermore, feature projection based classification algorithms were tested and shown to be successful in large number of real domains. So, in this work, a feature projection based classification algorithm (VFI, Voting Feature Intervals) is adapted to the rule interestingness problem, and FPRC (Feature Projection Based Rule Classification) algorithm is developed.

Keywords: Rule classification, interestingness, voting, feature projection.

BU-CE-0306: PDF

Realistic Rendering of a Multi-Layered Human Body Model (M. Sc. Thesis)

Mehmet Şahin Yeşil

In this thesis study, a framework is proposed and implemented for the realistic rendering of a multi-layered human body model while it is moving. The proposed human body model is composed of three layers: a skeleton layer, a muscle layer, and a skin layer. The skeleton layer, represented by a set of joints and bones, controls the animation of the human body model using inverse kinematics. Muscles are represented by action lines, which are defined by a set of control points. The action line expresses the force produced by a muscle on the bones and on the skin mesh. The skin layer is modeled in a 3D modeler and deformed during animation by binding the skin layer to both the skeleton layer and the muscle layer. The skin is deformed by a two-step algorithm according to the current state of the skeleton and muscle layers. In the first step, the skin is deformed by a variant of the skinning algorithm, which deforms the skin based on the motion of the skeleton. In the second step, the skin is deformed by the underlying muscular layer. Visual results produced by the implementation is also presented. Performance experiments show that it is possible to obtain real-time frame rates for a moderately complex human model containing approximately 33,000 triangles on the skin layer.

Keywords: Human body modeling and animation, multi-layered modeling, articulated figure, kinematics, inverse kinematics, action line, skinning, deformation.

BU-CE-0307: PDF

Human Motion Control Using Inverse Kinematics (M. Sc. Thesis)

Aydemir Memişoğlu

Articulated figure animation receives particular attention of the computer graphics society. The techniques for animation of articulated figures range from simple interpolation between keyframes methods to motion-capture techniques. One of these techniques, inverse kinematics, which is adopted from robotics, provides the animator the ability to specify a large quantity of motion parameters that results with realistic animations. This study presents an interactive hierarchical motion control system used for the animation of human figure locomotion. We aimed to develop an articulated figure animation system that creates movements using motion control techniques at different levels, like goal-directed motion and walking. Inverse Kinematics using Analytical Methods (IKAN) software, which was developed at the University of Pennsylvania, is utilized for controlling the motion of the articulated body using inverse kinematics.

Keywords: kinematics, inverse kinematics, articulated figure, motion control, spline, gait.

BU-CE-0308: PDF

Benefit Maximization in Classification on Feature Projections

H. Altay Güvenir

In some domains, the cost of a wrong classification may be different for all pairs of predicted and actual classes. Also the benefit of a correct prediction is different for each class. In this paper, a new classification algorithm, called BCFP (for Benefit Maximizing Classifier on Feature Projections), is presented. The BCFP classifier learns a set of classification rules that will predict the class of a new instance with maximum benefit or minimum cost. BCFP represents a concept in the form of feature projections on each feature dimension separately. Classification in the BCFP algorithm is based on a voting among the individual predictions made on each feature. A genetic algorithm is used to select the relevant features. The performance of the BCFP algorithm is evaluated in terms of accuracy. As a case study, the BCFP algorithm is applied to the problem of diagnosis of gastric carcinoma. A lesion can be an indicator of one of nine different levels of gastric carcinoma. The benefit of correct classification of early levels is much more than that of late cases. Also, the cost of wrong classifications is different for all classes.

Keywords: Machine learning, feature projection, voting, benefit maximization.

BU-CE-0309: PDF

Learning Translation Templates for Closely Related Languages

Kemal Altıntaş and H. Altay Güvenir

Many researchers have worked on example-based machine translation and different techniques have been investigated in the area. In literature, a method of using translation templates learned from bilingual example pairs was proposed. The paper investigates the possibility of applying the same idea for close languages where word order is preserved. In addition to applying the original algorithm for example pairs, we believe that the similarities between the translated sentences may always be learned as atomic translations. Since the word order is almost always preserved, there is no need to have any previous knowledge to identify the corresponding differences. The paper concludes that applying this method for close languages may improve the performance of the system.

BU-CE-0310: PDF

Vision Based Handwritten Character Recognition (M. Sc. Thesis)

Özcan Öksüz

Onine automatic recognition of handwritten text has been an onoing research problem for four decades. It is used in automated postal address and ZIP code and form reading, data acquisition in bank checks, processing of archived institutional records, automatic validation of passports, etc. It has been gaining more interest lately due to the increasing popularity of handeld computers, digital notebooks and advanced cellular phones. Traditionally, human-machine communication has been based on keyboard and pointing devices. Onine handwriting recognition promises to provide a dynamic means of communication with computers through a pen like stylus, not just an ordinary keyboard. This seems to be a more natural way of entering data into computers.

In this thesis, we develop a character recognition system that combines the advantage of both on-line and off-line systems. Using an USB CCD Camera, positions of the pen-tip between frames are detected as they are written on a sheet of regular paper. Then, these positions are used for calculation of directional information. Finally, handwritten character is characterized by a sequence of writing directions between consecutive frames. The directional information of the pen movement points is used for character pre-classification and positional information is used for fine classification. After characters are recognized they are passed to LaTeX code generation subroutine. Supported LaTeX environments are array construction, citation, section, itemization, equation, verbatim and normal text environments. During experiments a recognition rate of 90% was achieved. The main recognition errors were due to the abnormal writing and ambiguity among similar shaped characters.

Keywords: pattern recognition, character Recognition, on-line recognition systems, LaTeX.

BU-CE-0311: PDF

Using a Data Mining approach for Prediction of User Movements in Mobile Environments (M. Sc. Thesis)

Gökhan Yavaş

Mobility prediction is one of the most essential issues that need to be explored for mobility management in mobile computing systems. In this thesis, we propose a new algorithm for predicting the next inter-cell movement of a mobile user in a Personal Communication Systems network. In the first phase of our three-phase algorithm, user mobility patterns are mined from the history of mobile user trajectories. In the second phase, mobility rules are extracted from these patterns, and in the last phase, mobility predictions are accomplished by using these rules. The performance of the proposed algorithm is evaluated through simulation as compared to two other prediction methods. The performance results obtained in terms of Precision and Recall indicate that our method can make more accurate predictions than the other methods.

Keywords: Location prediction, data mining, mobile computing, mobility patterns, mobility prediction.