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

Institute of Information Science, Academia Sinica

Library

Print

Press Ctrl+P to print from browser

2001 Technical Report

Code

Subject / Author / Abstract

View

Code

TR-IIS-01-001

Subject / Author / Abstract

On Recognition of Replicated and-or Series-Parallel Digraphs
Jichiang Tsai and De-Ron Liang

The computation task of a distributed processing system usually can be partitioned into a set of modules and then modeled as a directed graph, called the task digraph. In the task digraph, vertices represent modules and arcs represent message passing links between two modules. Particularly, according to the logical structures and precedence relationships among modules, a large class of task digraphs can be modeled as And-Or Series-Parallel (AOSP) digraphs. For this type of digraph, we can calculate its task reliability and task response time in linear time; whereas these problems are known to be NP-hard for general digraphs. Hence, it becomes a useful work for evaluating comptation tasks to examine if a task digraph is an AOSP digraph. A polynomial time algorithm of recognizing AOSP digraphs has been proposed in [1] earlier. In this paper, we consider the fault-tolerant variants of AOSP digraphs, named Replicated And-Or Series-Parallel (RAOSP) digraphs, which are obtained from AOSP digraphs by adding replications to each vertex and adding proper arcs between two vertices. For RAOSP digraphs, we can also calculate its task reliability and task response time in linear time with the similar methods of AOSP digraphs. So it is another important work to recognize RAOSP digraphs. The existing polynomial time recognition algorithm for AOSP digraphs does not apply here since it can be shown that RAOSP digraphs are not AOSP digraphs. To make up this deficiency, we will propose a polynomial time algorithm for recognizing RAOSP digraphs in the context. Moreover, it will be first described how to recognize a special subclass of RAOSP digraphs, Replicated Edge Series-Parallel (RESP) digraphs, in polynomial time as a preliminary step.

View

Code

TR-IIS-01-002

Subject / Author / Abstract

Clock Restriction Diagram: Yet Another Data-Structure for Fully Symbolic Verification of Timed Automata
Far Wang

Modern model-checkers for real-time systems are usually built around symbolic manipulation pro-cedures of zones, which mean behavior-equivalent dense-time state subspaces and are represented by sets of clock difference constraints. We propose CRD (Clock Restriction Diagram), which is a BDD-like data-structure for recording sets of zones, with related set-oriented operations for fully symbolic verifica- tion of realt-time systems. CRD with zones in reduced from (or reduced CRD in short), which contains minimal number of clock inequalities to characterize a zone, are defined and can be used as a canonical representation for state space. Reduced CRD is more space-efficient than former proposal like DBM, NDD, CDD, and RED. We develop an algorithm that converts given CRDs to reduced CRDs without first computing its closure from(which records the shortest path distance between every pair of clocks) in some representations. We implemented CRD in a new version of our verifier red for timed automata and compare its performance with Kronos's and UPPAAL's against several benchmarks.

View

Code

TR-IIS-01-003

Subject / Author / Abstract

Parametric Optimization of Open Real-Time Systems
Farn Wang

For controllable timed automata, a general parametric optimization framework based on automata- theory is proposed. The framework is general enough to incorporate both the parametric analysis problem and the controller synthesis problem of computer systems. We propose an algorithm for the construction of the characterization of the parameter constraints and controller synthesis, which in turn yields a linear programming solution to parametric optimization.

View

Code

TR-IIS-01-004

Subject / Author / Abstract

Denoising and Copy Attacks Resilient Watermarking by Exploiting Prior Knowledge at Detector
Chun-Shien Lu, Hong-Yuan Mark Liao, and Martin Kutter

Watermarking with both oblivious detection and high robustness capabilities is still a challenging problem. The existing methods are either robust or oblivious, but it is difficult to achieve both goals simultaneously. In this paper, we tackle the above-mentioned problem. Our basic design methodology is to exploit prior knowledge available at the detector side and then use it to design a ``non-blind'' embedder. We prove that the proposed scheme can resist two famous denoising-based attacks, which have successfully cracked many existing watermarking schemes. False negative and false positive analyses are conducted to verify the performance of our scheme. The experimental results show that the new method is indeed powerful.

View

Code

TR-IIS-01-005

Subject / Author / Abstract

Generic Validation of Structural Content with Parametric Modules
Tyng-Ruey Chuang

In this paper, we demonstrate a natural mapping from element types of XML to module expressions of ML-like programming languages. The mapping is inductive, and the definitions of common XML operations can be derived as the module expressions are constructed. We show how to derive, in a generic way, the validation function, which checks an XML document for conformance to the content model specified by its DTD (Document Type Definition). One can view the validation function as giving types to XML elements, and the validation procedure a pre-requirement for typeful XML programming in ML. Our mapping of XML element types to ML module expressions uses the parametric module facility of ML in some contrived way. For example, in validating WML (WAP Markup Language) documents, we need to use 36-ary type constructors, as well as higher-order modules that take in as many as 17 modules as input. That one can systematically model XML DTD at the module level suggests ML-like languages are suitable for type-safe prototyping of DTD-aware XML applications.

View

Code

TR-IIS-01-006

Subject / Author / Abstract

Wavalet-based Active Contour Model for Object Segmentation and Tracking in Video Sequences
Jen-Chang Liu , Wen-Liang Hwang , Ming-Syan Chen , Jin-Wu Tsai , and Chi-Hung Lin

We propose an integrated wavelet-based framework of the active contour model (snake) for segmentation and motion tracking of deformable objects in video sequences. The input image frame is represented by means of wavelet transform. First, the moduli of wavelet transform coefficients are used in a multi-resolution motion estimation process to find the initial snake contour in the current frame. The presented multi-resolution motion estimation methods allow a larger movement of the tracked object than does traditional image-based motion estimation. Secondly, the wavelet transform modulus at each scale is considered in the energy function of the snake model. The snake computation is based on a coarse-to-fine scale continuation method. Application of the proposed methods to biological cell tracking is demonstrated in experiments.

View

Code

TR-IIS-01-007

Subject / Author / Abstract

A Control-Theoretic Method of Rate-Based Flow Control of Multimedia Communication
Wang, Chia-Hui, Jan-Ming Ho, Ray-I Chang, and Shun-Chin Hsu

In this paper, based on the feedback of buffer occupancy (BO), a new control-theoretic flow control mechanism is proposed. Our mechanism applies feedback control to keep BO running to a given level to increase the time available for packet recovery without violating real-time requirements. It tightly couples gap-based loss detection and packet retransmission to provide effective and efficient error control. Therefore, reliable communications and optimized playback QoS can be achieved at a minimal cost. Moreover, our implicit prediction and prevention for buffer underflow and overflow can help clients with a limited buffer (such as set-top box, PDA and cellular phone) to achieve acceptable playback QoS. We have deployed the proposed mechanism into a true VOD service in an ADSL trial. Experiments show that the proposed mechanism outperforms the previous mechanisms. The proposed mechanism contributes an innovative way to resist the network uncertainty with minimal overhead.

View

Code

TR-IIS-01-008

Subject / Author / Abstract

A Feedback-Controlled EDF Scheduling Algorithm for Real-time Multimedia Transmission
Wang, Chia-Hui, Jan-Ming Ho, Ray-I Chang, and Shun-Chin Hsu

Real-time communication is important for time-critical multimedia applications. However, conventional real-time schedulers such as EDF (Earliest Deadline First) and RM (Rate Monotonic) are designed for task sets with sophisticated characteristics. They can perform well in the idea network with precise workloads. But, in a realistic network with shared bandwidth and unpredictable workloads, their performances may be poor. In this paper, a control-theoretical approach of EDF called BC-EDF (Buffer-Controlled EDF) is proposed to resolve the real-time scheduling problem in multimedia communications. Based on the feedback control ideas (that have been used successfully in systems with unpredictable workloads), BC-EDF utilizes the feedback of buffer-occupancy to prevent packet loss from buffer's overflow/underflow (whether its occupancy is prevented to run above/below the watermark). It can tolerate diverse system behaviors to provide reliable multimedia communications and playback quality. Experiments show that BC-EDF outperforms other schedule mechanisms that don't reflect on the changes of buffer-occupancy.

View

Code

TR-IIS-01-009

Subject / Author / Abstract

A New Approach to Automatic Reconstruction of a 3-D World Using Active Stereo Vision
Chung-Yi Lin, Sheng-Wen Shih, Yi-Ping Hung, and Gregory Y. Tang

In this paper, we propose a new automatic approach for reconstructing 3-D environments using an active binocular head. To efficiently store and access the depth estimates, we propose to use an inverse polar octree which can transform both unbounded depth estimates and unbounded estimation errors into a bounded 3-D space with appropriate resolution. The depth estimates are computed by using the asymptotic Bayesian estimation method. Estimated depth values are then smoothed by using discontinuity-preserving Markov random fields. The path of the local motion required by the asymptotic Bayesian method is determined online automatically to reduce the ambiguity of stereo matching. Rules for checking the consistency between the new observation and the previous observations have been developed to properly update the inverse polar octree. Experimental results showed that the proposed approach is very promising for automatic generation of 3-D models which can be used for rendering a 3-D scene in a virtual reality system.

View

Code

TR-IIS-01-010

Subject / Author / Abstract

On-Line Posture Generation of Redundant Manipulator for Collision Avoidance in Dynamic Environment
Jin-Liang Chen and Jing-Sin Liu

The redundant manipulator has the advantage to generate the same configuration of the end-effector with infinite number of joint motion, which increases dexterity and versatility for performing multi-task at the end-effector and self-motion of robotic body. In this report, we propose a principle useful for on-line globally planning postures of the redundant manipulator. For obstacle avoidance, a technique is proposed to on-line generate collision-free joint velocities for self-motion of robotic body based on the incorporation of the principle and the pseudoinverse control. Simulations were implemented in the 2D static and dynamic environments in which obstacles were represented as convex polygons, which verify the good performances of collision avoidance using the proposed technique.

View

Code

TR-IIS-01-011

Subject / Author / Abstract

A Purely Image-Based Approach to Augmenting Panoramas with Object Movies
Yi-Ping Hung, Chu-Song Chen, Gregory Y. Tang, Yu-Pao Tsai, Chen-Fu Huang, Szu-Wei Lin, Chih-Han Yu

In this paper, we propose an easy-to-use approach to augmenting a panorama with object movies, in such a way that the inserted foreground objects remain visually coherent with the panoramic background. The proposed method is purely image-based in the sense that it does not have to reconstruct the 3D geometric model of the real object to be inserted in the panorama. Based on the proposed method, we have implemented a system for authoring and for browsing augmented panoramas. Experimental results have shown that the composite images rendered by our user-friendly system is visually plausible.

View

Code

TR-IIS-01-012

Subject / Author / Abstract

An Effective approach to Video Staging in Streaming Applications
Shin-Hung Chang, Ray-I Chang, Jan-Ming Ho, and Yen-Jen Oyang

Due to advances of network technologies, it has become practical to stream the stored video over Internet. Because the video stream is in a compressed format, it is naturally with the variable bit rate (VBR) property and the stream traffic is highly burst. By installing the video proxy between the access network (e.g. local area network, LAN) and the backbone network (e.g. wide area network, WAN), Video Staging is proposed to cache part of a video into the video proxy closed to clients. In this manner, the video can be streamed using a constant-bit-rate (CBR) network service across the backbone WAN and the WAN bandwidth requirement can be significantly reduced. In this paper, we proposed a new approach, called the caching selected after smoothing (CSAS), to handling Video Staging. The aim of this approach is to integrate the OC algorithm and the video smoothing technique so as to enhance the effectiveness of reducing the WAN bandwidth. The algorithm we proposed is superior to the conventional algorithms in two ways. Our method use less proxy storage to provide video streaming services if the WAN allocated bandwidth is same. With the same proxy storage, our method can also use less WAN bandwidth to provide video streaming services, especially in videos with high variety of bit rate. From the basis of experimental results on several benchmark videos, we conclude that our proposed algorithm is more effective than conventional one by several evaluation indices, including the small proxy storage requirement, the small WAN bandwidth requirement, and the high WAN bandwidth utilization.

View

Code

TR-IIS-01-013

Subject / Author / Abstract

Geometric Interpretation and Comparisons of Enhancements of GJK Algorithm for Computing Euclidean Distance between Convex Polyhedra
Jing-Sin Liu, Yuh-Ren Chien, Shen-Po Shiang and Wan-Chi Lee

The computation of Euclidean distance between two convex polyhedra is an important problem in robotics, computer graphics and real-time animation. An efficient and reliable distance computation procedure for a pair of convex sets is developed by Gilbert, Johnson and Keerthi (GJK) in 1988. GJK¡¦s convex set-theoretic approach is general and suitable for iterative numerical computation, however the GJK algorithm has the drawback of lack geometric intuition, especially in pairwise distance computation of convex polyhedra defined by the convex hull of its vertices in Euclidean 2D and 3D space. This paper investigates the steps of GJK algorithm from a geometric but intuitive point of view. By geometric reasoning, we present an improvement of the Euclidean distance computation algorithm made by GJK. Some comparative simulations for both the static and tracking cases, in particular, collision-free motion planning of redundant robots, are shown to verify the algorithmic improvement in the process of distance computation. In addition, our work provides a simple and efficient algorithm for finding out the information where the closest point of a convex polyhedron to a reference point is: on the face, the edge, or on one vertex of the polyhedron.

View

Code

TR-IIS-01-014

Subject / Author / Abstract

使用可擴展標示語言製作台灣社會地圖（初步報告） An XML-based Taiwan Social Map (Preliminary Report)
張藝鴻，莊庭瑞 / Yi-Hong Chang, Tyng-Ruey Chuang

本文件描述有關「台灣社會地圖」（Taiwan Social Map）系統建置之經驗。「台灣社會地圖」為一套使用「可擴展標示語言」來整理、標示、處理、以及呈現有關台灣的社經統計資料，並採用數位地圖的介面，讓使用者以互動與視覺化的方式探索社經資料和其地域關連之系統。此計畫之主要目的包括：一、檢驗XML技術規範以及其搭配的軟體工具，二、實際使用1990年的全國戶宅普查資料（近兩千萬筆資料），搭配詳細的行政區域劃分圖（七千餘村里）來進行系統製作，最終目標在於發展並累積以XML為底的「複雜資料集」（complex datasets）的處理技術。這個系統並藉由將統計資料透過XML標示與視覺化呈現等工作，使台灣社經統計資料得被方便地交換、再利用與探索。本文件描述了建置「台灣社會地圖」之過程、遭遇的問題與我們的解決方案，並且對於有關各種資料集取得與交換之議題，進行了簡短的討論。關鍵詞：人口資料，戶宅普查，數位地圖製作，人文地理，複雜資料集，全球資訊網，可擴展標示語言。　 An XML-based Taiwan Social Map (Preliminary Report) Yi-Hong Chang, Tyng-Ruey Chuang Institute of Information Science, Academia Sinica Nankang, Taipei 115, Taiwan, R.O.C. Abstract We report our experience in building Taiwan Social Map: An XML-based Web system for interactive exploration of Taiwan population datasets. Our motivation in building such a system is to evaluate the feasibility of using XML technologies, with currently available free software tools and systems, to prepare, markup, process, and visualize socioeconomic datasets about Taiwan population. The goal is to cultivate our technological expertise in processing complex datasets, and to build a system that is actually useful to social science researchers. The Taiwan Social Map system currently combines the 1990 national census dataset (about 20,000,000 survey records) with a detailed administration boundary map (with more than 7,000 contours of villages and precincts). It allows interactive visualization of summary statistics of the census data on the administration map, and is very easy to use. We report here the problems we encountered in building the system and the solutions we adapted. We also briefly discuss issues related to datasets acquisition and exchange.

View

Code

TR-IIS-01-015

Subject / Author / Abstract

Fast Method for Robust Template Matching
Jiun-Hung Chen, Chu-Song Chen, and Yong-Sheng Chen

In this paper, we propose a fast algorithm for speeding up the process of template matching that uses M-estimators for dealing with outliers. We propose a particular image hierarchy called the p-pyramid that can be exploited to generate a list of ascending lower bounds of the minimal matching errors when a non-decreasing robust error measure is adopted. Then, the set of lower bounds can be used to prune the search of the p-pyramid, and a fast algorithm is thereby developed in this paper. This fast algorithm ensures finding the global minimum of the robust template matching problem in which a non-decreasing M-estimator serves as an error measure. Experimental results demonstrate the effectiveness of our method.

View