您的瀏覽器不支援JavaScript語法，網站的部份功能在JavaScript沒有啟用的狀態下無法正常使用。

Institute of Information Science, Academia Sinica

Library

Print

Press Ctrl+P to print from browser

2004 Technical Report

Code

Subject / Author / Abstract

View

Code

TR-IIS-04-001

Subject / Author / Abstract

Nonlinear Boost
Chu-Song Chen*, Chang-Ming Tsai, Jiun-Hung Chen, and Chia-Ping Chen

In this paper, we propose the post-classification scheme that is useful for improving weak-hypothesis combination of AdaBoost. The post-classification scheme allows the weak hypotheses to be combined nonlinearly, and can be shown to have a generally better performance than the original linear-combination approach in either theory or practice. The post-classification scheme provides a general perspective on combining weak hypotheses, in which many existing boosting methods can be treated as its sub-cases. By using support vector machine (SVM) as post-classifier, we have shown that AdaBoost and SVM can be effectively combined in the post-classification scheme to achieve an effective classification algorithm. Experiment results show that the proposed nonlinear boost approach can significantly improve the performance of AdaBoost.

View

Code

TR-IIS-04-002

Subject / Author / Abstract

A nested invocation suppression mechanism for active replication fault-tolerant CORBA
Deron Liang and Chen-Liang Fang

Active replication is a common approach to building highly available and reliable distributed software applications. The redundant nested invocation (RNI) problem arises when servers in a replicated group issues nested invocations to other server groups in response to a client invocation. Automatic suppression of RNI is always a desirable solution, yet it is usually a difficult design issue. If the system has multi-threading (MT) support, the difficulties of implementation increase dramatically. One can design a deterministic thread execution control mechanism, but there is a drawback of this. Commonly, modern operating systems implement thread scheduler on kernel level for execution fairness. Unfortunately, in this case, modification on the thread scheduler implies modifying the operating system kernel. This approach loses system portability which is one of the important requirements of CORBA and other middleware. In this work, we propose a mechanism to perform auto-suppression of redundant nested invocation in an active replication fault-tolerant (FT) CORBA system. Besides the mechanism design, we discuss the design correctness semantic and the correctness proof of our design.

View

Code

TR-IIS-04-003

Subject / Author / Abstract

The complete interface definition of fault tolerant web service via WSDL and OMG IDL
Chen-Liang Fang, Deron Liang, and Fengyi Lin

This article present the interface definitions of the fault-tolerance SOAP (or FT-SOAP) in OMG IDL and its IDL mapping to the WSDL 1.1. This article is a supplement document for a previously published document under the same topic, TR-IIS-03-013. The purpose of this article is to illustrate the mapping between the human readable FT-SOAP (in OMG IDL) and machine readable form in WSDL.

View

Code

TR-IIS-04-004

Subject / Author / Abstract

Real-Time Frame-Dependent Wartermarking in MPEG-2 Video
Chun-Shien Lu, Jan-Ru Chen, and Kuo-Chin Fan

Digital watermarking is a helpful technology for providing copyright protection for valuable multimedia data. In particular, video watermarking deals with several issues that are unique to various types of media watermarking. In this paper, these issues, including compressed domain watermarking, real-time detection, bit-rate control, and resistance to watermark estimation attacks, will be addressed. Since video sequences are usually compressed before they are transmitted over networks, we first describe how watermark signals can be embedded into compressed video while keeping the desired bit-rate nearly unchanged. In the embedding process, our algorithm is designed to operate directly in the variable length codeword (VLC) domain to satisfy the requirement of real-time detection. We describe how suitable positions in the VLC domain can be selected for embedding transparent watermarks. Second, in addition to typical attacks, the peculiar attacks that video sequences encounter are investigated. In particular, in order to deal with both collusion and copy attacks that are fatal to video watermarking, the video frame-dependent watermark (VFDW) is presented. Extensive experimental results verify the excellent performance of the proposed compressed video watermarking system in addressing the aforementioned issues.

View

Code

TR-IIS-04-005

Subject / Author / Abstract

A Bayesian Approach to Video Object Segmentation via Merging 3D Watershed Volumes
Yu-Pao Tsai, Chih-Chuan Lai, Yi-Ping Hung, and Zen-Chung Shih

In this paper, we propose a Bayesian approach to video object segmentation. Our method consists of two stages. In the first stage, we partition the video data into a set of 3D watershed volumes, where each watershed volume is a series of corresponding 2D image regions. These 2D image regions are obtained by applying to each image frame the marker-controlled watershed segmentation, where the markers are extracted by first generating a set of initial markers via temporal tracking and then refining the markers with two shrinking schemes: the iterative adaptive erosion and the verification against a pre-simplified watershed segmentation. Next, in the second stage, we use a Markov random field to model the spatio-temporal relationship among the 3D watershed volumes that are obtained from the first stage. Then, the desired video objects can be extracted by merging watershed volumes having similar motion characteristics within a Bayesian framework. A major advantage of this method is that it can take into account the global motion information contained in each watershed volume. Our experiments have shown that the proposed method has potential for extracting moving objects from a video sequence.

View

Code

TR-IIS-04-006

Subject / Author / Abstract

Learning Face Recognition Classifiers by Incorporating Human Perceptions
Chu-Song Chen, Shih-Liang Yeh, and Chang-Ming Tsai

We propose a novel approach that employs human perception to improve the learning for face-recognition. By considering that the training examples are finite samples on the face manifold, we introduce the concept of appearance morphing curve that contains significant information for identifying facial images of different persons. By employing this concept, an effective method is introduced to increase automatic face recognition performances.

View

Code

TR-IIS-04-007

Subject / Author / Abstract

Geometric Distortion-Resilient Image Hashing Scheme and its Applications on Copy Detection and Authentication
Chun-Shien Lu and Chao-Yong Hsu

Media hashing is an alternative approach to many applications previously accomplished with watermarking. The major disadvantage of the existing media hashing technologies is their poor resistance to geometric attacks. In this paper, a novel geometric distortion-invariant image hashing scheme which can be employed to perform copy detection and content authentication of digital images, is proposed. Our major contributions are threefold: (i) mesh-based robust hashing function is proposed; (ii) sophisticated hash database for error-resilient and fast matching is constructed; and (iii) the application scalability of our scheme for content copy tracing and authentication is studied. In addition, we further investigate several media hashing issues, including robustness and discrimination, error analysis, and complexity, for the proposed image hashing system. Exhaustive experimental results obtained from benchmark attacks confirm the excellent performance of the proposed method.

View

Code

TR-IIS-04-008

Subject / Author / Abstract

Experiences in Implementing a Java Collaborative IDE over the Internet
Chien-Min Wang, Shun-Te Wang, Shyh-Fong Hong, and Hsi-Min Chen

A collaborative computing environment supports groups of people as they cooperate to achieve their goals. This report presents a system architecture to support the application areas in collaborative authoring and editing. An experimental platform, called the i-Code system, has been developed. It is a Java collaborative integrated development environment (IDE) tool designed to help collaboratively build Java applications for collaborative computing. Not only the IDE itself, but also the Java applications, are collaborative. Furthermore, in a computer-supported cooperative work (CSCW) environment, event broadcasting is a common operation in an object-oriented software system to solve many issues. In a multi-user case in particular, due to scalability, such operations are expected to be more quickly and reliably executed. In this report, we provide a study of issues related to event broadcasting in a Java collaborative computing environment over the Internet. We address how these issues happen and propose solutions for them.

View

Code

TR-IIS-04-009

Subject / Author / Abstract

A Dual-mode Exerciser for a Collaborative Computing Environment
Chien-Min Wang, Shyh-Fong Hong, Shun-Te Wang, and Hsi-Min Chen

Computer-supported cooperative work (CSCW) supports groups with communication and coordination during the execution of their activities. It allows physically dispersed teams to engage in a common task by providing an interface to a shared workspace. A variety of synchronous applications are playing a major role in distance education, joint program development, cooperative publishing, etc. As these applications are usually platform-dependent, groupware programmers have to develop new applications for each groupware platform. In this paper, we present a collaborative application developing environment called CollabRunJava, which allows the groupware developers to concentrate only on application-specific details. CollabRunJava supports 2 modes for developing applications. In the instant-develop mode, user can immediately execute and test the classes, which are also developed by our system. In the dynamic modify-observe mode, user can observe application behavior, debug applications and change the running applications codes without re-execution. Our system can be further enhanced by using plug-in components with the above mechanisms. For example, with the aid of visualization components, our system can help users explore program behavior. This also makes it helpful for distant learning and program testing.

View

Code

TR-IIS-04-010

Subject / Author / Abstract

A Tree-Structured Persistence Server for Archiving Java Run-Time States
Chien-Min Wang, Hsi-Min Chen, Shun-Te Wang, and Shyh-Fong Hong

The persistence problem of collaborative applications is a significant issue in the research of computer-supported collaborative work. A collaborative computing environment requires a simple and transparent persistence layer to deal with complex object accesses. Therefore, in this paper, we propose an object persistence mechanism and implement a persistence server, called Tree-Structured Persistence Server (TSPS), to support collaborative applications that store and retrieve application states. The server allows states of collaborative applications to be stored in a tree fashion beside tables. In addition to accommodating basic operations to access persistent objects, the TSPS offers advanced functions to manage sessions, states and versions of a collaborative application. By accessing these services, users can archive the run-time states of Java-based applications with transparency and simplicity. The TSPS was originally developed to serve as a persistence layer to support a project of computer-supported collaborative work. We intend to develop our persistence mechanism for universal use so that it can be applied in more application areas.

View

Code

TR-IIS-04-011

Subject / Author / Abstract

Data Reduction Methods for Pattern Recognition
Fu Chang, Chin-Chin Lin and Wen-Hsiung Lin

In this paper we present a series of data-reduction methods for classifying an unknown object as one member of a large set of possible patterns. The first reduction method is a learning algorithm that reduces a gigantic set of training samples into a condensed set of templates, each represented in vector form. When used in a testing process, these templates hold target patterns within the nearest K templates for almost all unknown objects, where K is a small number. The second reduction method exploits the nature of templates and classification trees to form a fast tree-retrieval mechanism. Experiment results show that this retrieval mechanism is a lot more effective than the K-means clustering method in meeting the same objective. The third method is a disambiguation method that supplies a condensed set of confusing pairs. This method exploits an effective binary classification technique to re-evaluate all the confusing pairs that appear in the nearest K templates for each unknown object, and thus improves the accuracy rate of the final classification decision.

View

Code

TR-IIS-04-012

Subject / Author / Abstract

Web-Based Collaborative Problem Solving Environment Part I: Knowledge Management
Gen-Cher Lee, Ming-Yu Chen, Yao-Wen Huang, Jyh-Da Wei, Chien-Min Wang and D. T. Lee

This work is part of the integrated project “ShareTone”, which aims to build a web-based collaborative problem-solving environment for scientific collaboration. The whole plan is composed of three main portions, i.e., (a) a knowledge management mechanism, (b) a tele-conferencing system, and (c) a computer supported collaborative work (CSCW) system. This paper involves the first part of the whole plan. Accompanying papers will cover the other two parts. In this paper, we propose an efficient knowledge management mechanism. We integrate clustering and mirroring features into the Zope/Plone shareware, and extend it to support different levels of collaboration, i.e., data sharing, software warehousing, application sharing, and workflow. The ShareTone tele-conferencing and CSCW systems can also be plugged in this framework. Therefore, it is developed not only as an excellent knowledge management portal, but also as online communication and synchronous collaboration vehicles.

View

Code

TR-IIS-04-013

Subject / Author / Abstract

Web-Based Collaborative Problem Solving Environment Part II: Tele-Conferencing System
Li-Chun Sung, Meng-Chang Chen, Ming-Yu Chen, Gen-Cher Lee, Jyh-Da Wei, Chien-Min Wang and D. T. Lee

The ShareTone project we proposed is to build a web-based collaborative problem-solving environment for scientific collaboration. This project is composed of three modules, i.e., (a) a knowledge management system, (b) a tele-conferencing system, and (c) a computer supported collaborative work (CSCW) system. This paper elucidates the second part of the whole plan. Accompanying papers will cover the other two parts. In this paper, we propose a tele-conferencing system including videoconference and the Internet Relay Chat (IRC) packages. They both are under client-server architectures. To make them the most broadly available, we develop the clients using Java language, and devise a means to transmit data streams through firewalls. We also demonstrate how to plug these client-side applications into our knowledge management system as content types for knowledge sharing.

View

Code

TR-IIS-04-014

Subject / Author / Abstract

Web-Based Collaborative Problem Solving Environment Part III: CSCW System
Chien-Min Wang, Shun-Te Wang, Gen-Cher Lee, Hsi-Min Chen, Shiang-Heng Chen, Shyh-Fong Hong, Jeng-Hung Huang, Shun-Wen Huang, Jyh-Da Wei and D. T. Lee

We propose an integrated project called ShareTone (http://www.sharetone.org/) to build a web-based collaborative problem-solving environment, which facilitates collaboration among researchers and practitioners over the Internet. This project is composed of three main portions, i.e., (a) a knowledge management system, (b) a tele-conferencing system, and (c) a computer supported collaborative work (CSCW) system. This paper focuses on the third part of this project. The ShareTone CSCW system includes system components and applications. The reusable components facilitate user authentication, file sharing, long-term persistence, and event-driven collaboration control. The applications demonstrate how to fabricate the above components to develop complicated collaborative utilities and enrich collaborative features that may support information sharing, distance learning, online demonstration and collaborative design.

View

Code

TR-IIS-04-015

Subject / Author / Abstract

Predicting Travel Time through a Congested Road Segment using Regression in Time-Space Diagram
Wen-Yao Chen, Wen-Liang Hwang, and Ching-Yi Wu

Travel time estimation is a basic component in many applications of an intelligent transportation system (ITS). We consider the travel time estimation of passing through a congested road segment and present a novel travel time prediction algorithm. The dynamic nature of our congestion model can be characterized by the propagation of its head and tail boundaries, which are determined by shock wave equations. We show that the propagation of the tail boundary can be effectively approximated if the inflow to the congestion is given, while the head boundary can be approximated as a line in a time-space diagram. We demonstrate the effectiveness of our algorithm by measuring its performance using the Nagel-Schreckenberg (CA) model. Simulation results from varying the probe car density are also given.

View

Code

TR-IIS-04-016

Subject / Author / Abstract

A Hybrid Method for Multiclass Classification and Its Application to handwritten Character Recognition
Fu Chang, Chin-Chin Lin and Chun-Jen Chen

The support vector machine (SVM) is an effective pattern classification method. However, solving N(N-1)/2 binary classifications in the training phase makes it too costly to use SVM in applications with a high number N of class types. In this paper, we propose a new prototype classification method that can be combined with SVM for pattern recognition. This hybrid method has the following merits. First, the learning algorithm for constructing prototypes determines both the number and the location of the prototypes. This algorithm not only terminates within a finite number of iterations, but also assures that each training sample matches in class type with the nearest prototype. Second, SVM can be used to process the top-rank candidates obtained by the prototype classification method, which saves time in both the training and testing processes. We apply our method to recognizing handwritten numerals and handwritten Chi-nese/Hiragana characters. Experiment results show that the hybrid method saves a great deal of training and testing time in large scale tasks and achieves comparable accuracy to that achieved by using SVM solely. Our results also show that the hybrid method performs better than the nearest neighbour method.

View

Code

TR-IIS-04-017

Subject / Author / Abstract

Appointed BrOadcast (ABO): Reducing Routing Overhead in IEEE 802.11 Mobile Ad Hoc Networks
Chun-Yen Hsu and Shun-Te Wang

In this report, we propose the Appointed BrOadcast (ABO) method to achieve packet overhearing to reduce the routing overhead in the IEEE 802.11 mobile ad hoc networks (MANETs). Using the ABO method, IEEE 802.11 frames are modified in such a way that the Intended Receiver Address (IRA) is appended to the frame body. These ABO frames are broadcasted to enable packet overhearing while keeping the transmission to specific node reliable. How ABO-enhanced and standard IEEE 802.11 nodes can coexist in a MANET is also discussed.

View

Code

TR-IIS-04-018

Subject / Author / Abstract

Background Modeling Using Phase Space for Day and Night Video Surveillance Systems
Yu-Ming Liang, Arthur Chun-Chieh Shih, Hsiao-Rong Tyan, and Hong-Yuan Mark Liao

This paper presents a novel background modeling approach for day and night video surveillance. A great number of background models have been proposed to represent the background scene for video surveillance. In this paper, we propose a novel background modeling approach by using the phase space trajectory to represent the change of intensity over time for each pixel. If the intensity of a pixel which originally belongs to the background deviates from the original trajectory in phase space, then it is considered a foreground object pixel. In this manner, we are able to separate the foreground object from the background scene easily. The experimental results show the feasibility of the proposed background model.

View

Code

TR-IIS-04-019

Subject / Author / Abstract

Palindrome-like Patterns in Genomes
Arthur Chun-Chieh Shih, D. T. Lee, Chi-Fang Chin, Hong-Yuan Mark Liao, and Wen-Hsiung Li

Motivation: It has been of great interest to know whether some simple nucleotide-level patterns or permutation structures can give rise to genome-wide general properties. In this study, we wish to find such patterns or structures. For this purpose, we develop a representation method different from those used to detect long range correlations (LRCs) in genomes. Specifically, we propose a set of crystalline-like walking spaces in which DNA sequences can be coded into a set of 3D curves by following a set of walking rules. Results: Our representation method reveals that genomic DNA sequences in both prokaryotes and eukaryotes have linear trends and discernable orientations in the walking spaces. Some palindrome-like sequences are then found to have the trends and orientations similar to those found in genomic DNA sequences. After a series of verifications and simulations, we speculate that these patterns may be derived from a very old ancestral genome and some of the patterns might still possess certain functions in present-day genomes. These patterns may explain the existence of LRCs in genomes and why Chargaff's second parity rule holds approximately in many genomic regions.

View

Code

TR-IIS-04-020

Subject / Author / Abstract

OHVPA: An On-Line Hose-Model VPN Provisioning Algorithm
Yu-Liang Liu, Yeali S. Sun, Meng Chang Chen

Virtual private networks (VPNs) provide customers with a secure and low-cost communication environment. The allocation of bandwidth for VPNs to meet the requirements specified by customers is now one of the most important research issues in the field of traffic engineering. A VPN resource provisioning model called hose model was developed to provide customers with flexible and convenient ways to specify the bandwidth requirement of a VPN. Several hose-model VPN provisioning algorithms have already been proposed. They focus on the bandwidth efficiency issue in the case of establishing a single hose-mode VPN. However, these algorithms cannot achieve a satisfactory rejection ratio of VPN setup requests (rejection ratio) when: (1) the residual bandwidths on links of the network backbone are finite and (2) multiple VPN setup requests are handled on-line. In this paper, we propose a new hose-model VPN provisioning algorithm called OHVPA to address the issue. OHVPA can process multiple VPN setup requests rapidly and reduce the rejection ratio effectively. Theoretical upper bounds of rejection ratios achieved by several VPN provisioning algorithms are also derived. The experiments verify that OHVPA performs better in rejection ratio than other provisioning algorithms

View