Institute of Information Science, Academia Sinica

Library

Print

Press Ctrl+P to print from browser

1998 Technical Report

Code

Subject / Author / Abstract

View

Code

TR-IIS-98-001

Subject / Author / Abstract

WHY A STATISTICS-BASED FACE RECOGNITION SYSTEM SHOULD BASE ITS RECOGNITION ON THE PURE FACE PORTION : A PROBABILISTIC DECISION-BASED PROOF
Chen, Li-Fen. Liao, Hong-Yuan Mark. Han, Chin-Chuan. Lin, Ja-Chen.

Face recognition, by definition, should be a recognition process in which recognition is based on the content of a face. The problem is: what is a "face"? Goudail et al. [1] and Swets and Weng [2] have recently proposed state-of-the-art statistics-based face recognition systems. However, they used "face" images that included hair, shoulders, face and background. Our intuition tells us that only a recognition process based on a "pure" face portion can be called face recognition. The mixture of irrelevant data may result in an incorrect set of decision boundaries. In this paper, we propose a statistics-based technique to quantitatively prove our assertion. For the purpose of evaluating how the different portions of a face image will influence the recognition results, two hypothesis testing models are proposed. We then implement the two above mentioned face recognition systems and use the proposed hypothesis testing models to evaluate the systems. Experimental results reflected that the influence of the "real" face portion is much less than that of the nonface portion. This outcome confirms quantitatively that a statistics-based face recognition system should base its recognition solely on the "pure" face portion.

View

Code

TR-IIS-98-002

Subject / Author / Abstract

PROTOTYPING SPARSE FORTRAN 90 ARRAY INTRINSICS WITH STANDARD ML MODULE SYSTEM
TYNG-RUEY CHUANG.

We report work-in-progress of using the Standard ML module system to prototype sparse Fortran 90 array intrinsic functions. We illustrate type-related issues in a high-level, source-to-source mapping of Fortran 90 array intrinsics to Standard ML. The prototype sparse library is parameterized by array compression schemes. Various issues involved in using Standard ML as a prototyping language are also discussed.

View

Code

TR-IIS-98-003

Subject / Author / Abstract

FLASH MEMORY MANAGEMENT FOR LIGHTWEIGHT STORAGE SYSTEMS
MEI-LING CHIANG, PAUL C. H. LEE AND RUEI-CHUAN CHANG.

This report describes a management scheme for flash memory-based storage systems. This scheme will be implemented into a flash memory-based FAT file system in the Ramos project running in the Institute of Information Science (IIS). Ramos project targets on building software components for real time and multimedia applications that most of the consumer electronic products can be easily constructed by these software components. The flash memory-based file system is especially important to those products because flash memory is lightweight, shock-resistant, nonvolatile, power-efficient and is wildly used in these products. Flash memory has many advantages. However, the specific erase-operations before writing into flash memory are slow and power-wasted, which usually decrease system performance and consume the limited battery power. In addition to that, the number of flash memory erase cycles is also limited. In order to reduce the number of erase operations needed and to evenly wear flash memory, a new flash memory management scheme is proposed in this report. A new cleaning policy is also introduced to reduce the number of erase operations. Performance evaluations show that erase operations can be reduced by 55%.

View

Code

TR-IIS-98-004

Subject / Author / Abstract

TOWARD AUTOMATIC RECONSTRUCTION OF 3D ENVIRONMENT WITH AN ACTIVE BINOCULAR HEAD
CHUNG-YI LIN, SHENG-WEN SHIH AND YI-PING HUNG.

In this paper, we propose a new automatic approach to reconstructing a model for the 3D environment by use of an active binocular head. To efficiently store and access the depth estimates, we propose the use of the inverse polar octree which can transform both the unbounded estimate and the unbounded estimation error into a bounded 3D space with appropriate resolution. The depth estimates are computed by using the asymptotic Bayesian estimation method, which includes the use of Markov random fields. In order to apply this method, the active binocular head (the IIS head) has been calibrated with very high accuracy. The path of the local motion required by the asymptotic Bayesian method is determined online automatically to reduce the ambiguity of stereo matching. Some 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 have shown that the proposed approach is very promising for automatic generation of 3D models which can be used for rendering a 3D scene in a virtual reality system.

View

Code

TR-IIS-98-005

Subject / Author / Abstract

CLEANING POLICIES IN MOBILE COMPUTERS USING FLASH MEMORY
MEI-LING CHIANG, PAUL C. H. LEE AND RUEI-CHUAN CHANG.

Flash memory shows promise for use in storage devices for mobile computers. However, flash memory cannot be overwritten unless erased in advance. Erase operations are slow that usually decrease system performance, and consume power. For power conservation, better system performance, and longer flash memory lifetime, system support for erasure management is necessary. In this report, a non-update-in-place scheme is proposed to implement a flash memory server. A new cleaning policy is used to reduce the number of erase operations and to evenly wear out flash memory. The policy uses a fine-grained method to effectively cluster hot data and cold data in order to reduce cleaning overhead. Performance evaluations show that erase operations are significantly reduced and flash memory is evenly worn.

View

Code

TR-IIS-98-006

Subject / Author / Abstract

AN INTEGRATED CORE-WORK FOR FAST INFORMATION-APPLIANCE BUILDUP
PAUL C. H. LEE, CHI-WEI YANG AND RUEI-CHUAN CHANG.

The advances in digital technologies have given birth to many applications, which were hard to image in the past decade but are real in current time. For the versatile but specialized applications, general system software in tradition does not perform well to serve their specific demanding requests, because the general approach is designed to concern with most of the general cases. Besides, there exists complex dependency among software components in a traditional system, such that to modify or to reuse software components is not easy for application designers. In this report, the specialized applications that can be benefited from configurable and customized system components are termed as information-appliances. A framework for building up information-appliances efficiently is the body of this report. All the low-level core components that relate to hardware specifications are designed from scratch. The current version is dedicated for Intel 386 or newer processors. The contributions of this report can be illustrated as follows. First, our work supplies a research and development (R&D) platform. Through our work, researchers and designers can build their information-appliance prototypes efficiently that they do not need to implement so many low-level components first just for trying one tiny idea. Second, all the core components are designed modularly and well documented in exported and imported interface. Information-appliance performance can be benefited from this design by dropping any components that are not used by them. In addition, our work supply higher chances for specific management since each component is isolated and independent to others. Application designers can have more controls in behavior of each component. Third, our work includes a wrapper-socket for incorporating Linux X86 device drivers. This specific core component, the wrapper-socket, enables our work to make reuse of the biggest device driver source pool in the world directly. Any new patches or versions about the Linux device driver sources can patch to our framework directly, just with very minor modifications to the wrapper-socket implementation. Finally, the whole core-work is evaluated via empirical measurements. From these experimental results, the experiences about the system buildup, discussions about the device driver architecture impacts to real-time applications are also presented.

View

Code

TR-IIS-98-007

Subject / Author / Abstract

A STABLE NEURO-FUZZY CONTROLLER FOR OUTPUT TRACKING IN COMPOSITE NONLINEAR SYSTEMS
Tsai, Chih-Hsin. Liu, Jing-Sin. Tseng, Kuo-Bin. Lin, Wei-Song.

In this paper, a learnable neuro-fuzzy controller is proposed for on-line implementing a decoupling control action for uncertain composite affine nonlinear plants to track a prescribed trajectory. In structure, the controller is composed of decentralized fuzzy systems with embedded two-stages rule credit assignments mechanism cascaded with an interconnections compensating associative memory network and a nonsingularity supervisor. In analytical form, the controller can be parametrized by a set of linear parameters, which represent a combination of of the credits of rules, locations and shape factors of membership functions. The parameters are tuned by a deadzone adaptation algorithm to compensate for uncertainties. It is shown that the incorporation of deadzone in controller guarantees the stability of adaptation in the neuro-fuzzy system and moreover, a given level of attenuation for tracking error in the presence of unknown but bounded interconnections and disturbances. Simulation results of SISO plant, an inverted pendulum, and MIMO plant, a two-link planar robot manipulator, are given to demonstrate the effectiveness and robustness of the neuro-fuzzy controller for output tracking in composite nonlinear systems.

View

Code

TR-IIS-98-008

Subject / Author / Abstract

MULTIRESOLUTION HADAMARD REPRESENTATION AND ITS APPLICATIONS TO DOCUMENT IMAGE ANALYSIS
Liang, Kung-Hao. Chang, Fu. Tan, Tzu-Ming. Hwang, Wen-Liang.

Document image analysis is a critical technology in the construction of modern digital libraries. In document image analysis, a priori knowledge of the structure of signals (i.e. strokes) is required. In this paper, a special class of the wavelet transform, referred to as the multiresolution Hadamard representation (MHR), is proposed. The basis of MHR provides a stroke model, by which the strokes in a Chinese character can be extracted easily. This multiresolution analysis provides a means to reveal the size/scale of a character. Applications on the extraction of half-tone pictures, the determination of scales for characters and the dynamic binarization of images using the multiresolution Hadamard representation are also presented.

View

Code

TR-IIS-98-009

Subject / Author / Abstract

ITERATIVE REFINEMENT AND CONDENSATION FOR STATE-GRAPH CONSTRUCTION
FARN WANG AND PAO-ANN HSIUNG.

The traditional technique to generate a global state-graph representation for a concurrent system is to calculate the product of state-graph representations of the local processes. We develop new techniques, and prove their correctness, to help condensing intermediate state-graphs in the iterative product-calculation. Experiments with Fischer's timed mutual exclusion protocol have been carried out to justify the approach.

View

Code

TR-IIS-98-010

Subject / Author / Abstract

A SIMPLE MODEL OF DISTRIBUTED FUNCTIONAL DATA STRUCTURES AND ITS IMPLEMENTATION
TYNG-RUEY CHUANG.

We report results from experimenting with a parallel functional programming environment based on distributed data structures. The main results are: 1) A distribution model to support efficient fold/unfold operations over data structures. The distribution model is simple yet general, and easy to implement. 2) A novel programming environment assembled from currently available hardware/software systems. Functional programs execute in SPMD (Single Program Multiple Data) style under this environment and exhibit good speedup.

View

Code

TR-IIS-98-011

Subject / Author / Abstract

USING DATA CLUSTERING TO IMPROVE CLEANING PERFORMANCE FOR FLASH MEMORY
MEI-LING CHIANG, PAUL C. H. LEE AND RUEI-CHUAN CHANG.

Flash memory offers attractive features for storage of data, such as non-volatility, shock resistance, fast access speed, and low power consumption. However, it requires erasing before it can be overwritten. The erase operations are slow and consume comparatively a great deal of power. Furthermore, flash memory can only be erased a limited number of times. To manage flash memory effectively, we propose in this paper a new approach to reduce the number of erase operations performed. Via the accessing frequency of data, data is dynamically classified and clustered together to reduce the amount of data copied and the number of erase-operations. In addition, an adaptive cleaning manager is designed to dynamically adjust cleaning policies in response to the variations of data access behavior. Performance evaluations through real implementation on a flash memory server and trace-driven simulation show that the number of erase operations was reduced by 16~22.6%, the number of blocks copied was reduced by 20.1~28.4%, and throughput was improved by 19.5~25.2%. Even wearing is also ensured.

View

Code

TR-IIS-98-012

Subject / Author / Abstract

WAVELET KEYHOLE METHOD: AN APPLICATION OF WAVELET TRANSFORM IN DYNAMIC MRI
WEN L. HWANG AND HONG N. YEUNG.

We consider the processing of dynamic keyhole MRI using the wavelet-based approach. We propsosed two wavelet-based algorithms, together with careful analysis. The first algorithm embeds the conventional keyhole method as a special case in which corresponding wavelet is the Shannon wavelet while the other algorithm was proposed for the removals of the artifacts of the first method. We demonstrate that the artifacts of our method may decay faster than those of the conventional keyhole method. Our approach is fast and easy to implement. The results of several experiments are employed to access the comparative performance of both methods on a simulated phantom and clinical image.

View

Code

TR-IIS-98-013

Subject / Author / Abstract

TRAFFIC-SMOOTHING FOR DELIVERY OF ONLINE VBR MEDIA STREAMS BY A DYNAMIC WINDOW-BASED APPROACH
Chang, Ray-I. Chen, Meng-Chang. Ho, Jan-Ming. Ko, Ming-Tat.

Traffic smoothing for delivery of online VBR media streams is one of the most important problems in designing multimedia systems. Given the available client buffer and the sliding smooth window, conventional approaches try to minimize bandwidth allocated in each window. However, they can not lead to the minimization of bandwidth allocated for transmitting the entire stream. Although a sliding-window approach is introduced by Rexford et al. in 1997 to further reduce the bandwidth allocated, it is time-consuming. To resolve these drawbacks, in this paper, an effective and efficient online traffic-smoothing scheme is proposed. Different from conventional constant-sized approaches, our approach can automatically decide the suitable sliding sizes to online smooth the burst VBR traffic. By examining various media streams, our approach is shown to have higher bandwidth utilization (or called bandwidth-occupancy in conventional approaches) and requires smaller bandwidth than conventional approaches. Considering the online transmission of a Star War movie, our obtained result is over 13% smaller in the required network bandwidth and over 4% smaller in the obtained network idle rate than conventional approaches. In this paper, a feedback control method is introduced to resolve the latency- and quality-tolerance applications. Besides, the relations between the characteristic of input traffic and the behavior of obtained scheduling results are also discussed.

View

Code

TR-IIS-98-014

Subject / Author / Abstract

SCHEDULING SYSTEM VERIFICATION
PAO-ANN HSIUNG, FARN WANG AND YUE-SUN KUO.

A theoretical framework is proposed for the verification of complex real-time systems, modeled as client-server scheduling systems, using the popular model-checking approach. Model-checking is often restricted by the large state-space of complex real-time systems. The scheduling of tasks in such systems can be taken advantage of for model-checking. Our implementation and experiments corroborate the feasibility of such an approach. Wide-applicability, significant state-space reduction, and several scheduling semantics are some of the important features in our theory and implementation.

View

Code

TR-IIS-98-015

Subject / Author / Abstract

EDGE AND NODE SEARCHING PROBLEMS ON TREES
Peng, Sheng-Lung. Ho, Chin-Wen. Hsu, Tsan-sheng. Ko, Ming-Tat. Tang, Chuan Yi.

In this paper, we consider the edge searching and node searching problems on trees. Given a tree, we show a transformation from an optimal node-search strategy to an optimal edge-search strategy. Using our transformation, we simplify a previous linear-time algorithm for determining the edge-search number of a tree, and improve the running time of a previous algorithm for constructing an optimal edge-search strategy of an n-vertex tree from O(n log n) to O(n). We also improve the running time of a previous algorithm for constructing an optimal min-cut linear layout of an n-vertex tree with the maximum degree three from O(n log n) to O(n).

View

Code

TR-IIS-98-016

Subject / Author / Abstract

ESTIMATION OF 2-D NOISY FRACTIONAL BROWNIAN MOTION AND APPLICATIONS ON COASTLINE DETECTION AND TEXTURE SEGMENTATION
JEN-CHANG LIU, WEN L. HWANG AND MING-SYAN CHEN.

The 2-D fractional Brownian motion (fBm) model is useful in describing natural scenes and textures. Most fractal estimation algorithms for 2-D isotropic fBm images are simple extensions of the 1-D fBm estimation method. This method does not perform well when the image size is small (say 128x128). We propose a new algorithm that estimates the fractal parameter from the decay of the variance of the wavelet coefficients across scales. Our method places no restriction on the wavelets. Also, it provides a robust parameter estimation for small noisy fractal images. For image denoising, a Wiener filter is constructed by our algorithm using the estimated parameters and then applied to the noisy wavelet coefficients at each scale. We show that the averaged power spectrum of the denoised image is isotropic and is a near 1/f process. Numerical simulation shows the performance for our algorithm in both the fractal parameter and image estimation. Applications on coastline detection and texture segmentation in noisy environment are also demonstrated.

View

Code

TR-IIS-98-017

Subject / Author / Abstract

EXPERIENCES IN TUNING A SOFTWARE MPEG PLAYER
PAUL C. H. LEE.

An MPEG audio/video player in software is implemented on a commercial operating system and is detailed evaluated. The primary purpose of this work is to explore new system technologies in QoS management for advanced multimedia applications. Here, we address the performance analysis of this software-MPEG-II player and report the experiences in performance tuning and QoS enhancements via empirical experiments

View

Code

TR-IIS-98-018

Subject / Author / Abstract

THE RECOGNITION OF THE AOSP DIGRAPHS
HSIN-HUNG CHOU AND DE-RON LIANG.

A computation task running in distributed systems can be represented as a directed graph, called as a task graph. In such graph, vertices represent modules and arcs represent precendence constraints. And the arguments are passing among the modules. In the past, people study such subjects on edge series-parallel(ESP) digraph. In an ESP digraph, the precedence relation among the arcs joining to a vertex defaults to be OR-relation. In this paper, we extend the precedence relation to being a factorable formulas. Such digraphs are called and-or series-parallel(AOSP) digraph. And we present a polynomial time algorithm to recognize the class of the AOSP digraphs

View

Code

TR-IIS-98-019

Subject / Author / Abstract

VERIFICATION OF DYNAMIC LINEAR LISTS FOR ALL NUMBERS OF PROCESSES
FARN WANG.

In real-world design and verification of concurrent systems with many identical processes, the number of processes is never a factor in the system correctness. This paper embodies such an engineering reasoning to propose an almost automatic method to safely verify safety properties of such systems. The central idea is to construct a finite collective quotient structure (CQS) which collapses state-space representations for all system implementations with all numbers of processes. The problem is presented as safety bound problem which ask if the number of processes satisfying a certain property exceeds a given bound. Our method can be applied to systems with dynamic linear lists of unknown number of processes. Processes can be deleted from or inserted at any position of the linear list during transitions. We have used our method to develop CQS constructing algorithms for two classes of concurrent systems : (1) untimed systems with a global waiting queue and (2) dense-time systems with one local timer per process. We show that our method is both sound and complete in verifying the first class of systems.The verification problem for the second class systems is undecidable even with only one global binary variable. However, our method can still automatically generate a CQS of size no more than 1512 nodes to verify that an algorithm in the class: Fischer's timed algorithm indeed preserves mutual exclusion for any number of processes.

View

Code

TR-IIS-98-020

Subject / Author / Abstract

LYRA : A SYSTEM FRAMEWORK IN SUPPORTING MULTIMEDIA APPLICATIONS
PAUL C. H. LEE.

Current systems, such as UNIX, lack necessary scheduling and resource management mechanisms in supporting specific timing requirements, thus multimedia applications cannot run smoothly on top of them. Aim on solving these problems, in this paper we propose a system framework, the Lyra, for supplying multimedia applications with sophisticate timing controls. Lyra enhances conventional systems in supplying firewall protections among multimedia applications, while also considering I/O interference, and aims on processing digital data on time. Empirical evaluations show that Lyra not only practically provides better QoS supports than conventional systems, but also performs better than several works that aim on similar problems.

View