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

Institute of Information Science, Academia Sinica

Library

Print

Press Ctrl+P to print from browser

1996 Technical Report

:::

Code
Subject / Author / Abstract
View

Code

TR-IIS-96-001

Subject / Author / Abstract

IN-KERNEL POLICY INTERPRETATION FOR APPLICATION-SPECIFIC MEMORY CACHING MANAGEMENT
PAUL C. H. LEE, MENG CHANG CHEN AND RUEI-CHUAN CHANG.

Traditional operating systems manage the page frame pool with the LRU-like policies which cannot properly serve all types of memory access patterns of various applications. As a result, many memory-intensive applications induce excessive page faults and page replacements when running with access behaviors other than the LRU-like patterns. This paper presents a high performance external virtual memory caching mechanism (hipec) to allow user applications to run with their own specific page frame management policies. The user applications inform the operating system of their specific management policies by loading a set of macro-like commands to the kernel. When page faults or page replacements happen, the operating system will interpret the commands and perform the corresponding specific management policies. The empirical evaluations show that the hipec mechanism induces little overhead and significantly increase the application and system performance.

View

Fulltext

Code

TR-IIS-96-002

Subject / Author / Abstract

CFART : A NEW MULTI-RESOLUTIONAL ADAPTIVE RESONANCE SYSTEM FOR OBJECT RECOGNITION
Hong-Yuan Mark Liao, Hai-Lung Hung, Chwan-Jye Sze, Shing-Jong Lin, Wei-Chung Lin and Kuo-Chin Fan

ln this report, we propose a cascade fuzzy ART (CFART) neural network which can function as an extensible database in a model-based object recognition system. The proposed CFART network contains multiple layers. It preserves the prominent characteristics of a fuzzy ART network and extends fuzzy ART's capability toward hierarchical representation of input patterns. The learning process of the proposed network is unsupervised and self-organizing, and includes a top-down searching process and a bottom-up learning process. The top-down and bottom-up learning processes interact with each other in a closely coupled manner. Basically, the top-down searching guides the bottom-up learning whereas the bottom-up learning influences the top-down searching by changing its searching fuzzy boundary. In addition, a global searching tree is built to speed up the learning and recognition processes. The proposed CFART can accept both binary and analog inputs. With fast learning and categorization capabilities, the proposed network is able to function like an extensible database and to provide an efficient multi-resolutional representation capability for 3D objects. Experimental results, using both synthetic and real 3D data, prove that the proposed method is indeed an efficient and powerful representation scheme.

View

Fulltext

Code

TR-IIS-96-003

Subject / Author / Abstract

CASCADE FUZZY ADAPTIVE HAMMING NET : A COARSE-TO-FINE REPRESENTATION SCHEME FOR OBJECT RECOGNITION
Hong-Yuan Mark Liao, Hai-Lung Hung, Chwen-Jye Sze, Shing-Jong Lin, Wei-Chung Lin and Kuo-Chin Fan

In this report, we propose a cascade fuzzy adaptive Hamming net (CFAHN) which can function as an extensible database in a model-based object recognition system. The proposed CFAHN can accept both binary and analog inputs. The architecture of a CFAHN not only preserves the prominent characteristics of the FAHN (i.e., parallel pattern matching, fast learning and stable categorization), but also extends its capability to the hierarchical class representation of input patterns. The developed CFAHN is an unsupervised learning neural network, which can be used to store new object categories in an extensible manner. Moreover, every path in the database reveals a coarse-to-fine representation of an input pattern.

View

Fulltext

Code

TR-IIS-96-004

Subject / Author / Abstract

軟體暨物品管理系統
許秀琴,王秋鳳.

View

Fulltext

Code

TR-IIS-96-005

Subject / Author / Abstract

AN OBJECT TRANSACTION SERVICE IN CORBA
DERON LIANG, Y. M. KAO AND S. M. YUAN.

The concept of transactions is not only indispensable in database applications, but also useful in building robust software for mission-critical applications. This paper presents an implementation of the Object Transaction Service (OTS) based on CORBA specification. Transactional applications developed with the support of our OTS implementation are able to assure the ACID properties even in the presence of node crashes, software system failures and process hangs. The preliminary results obtained from the experiments on Sun workstations with Orbix 1.3 show that the overhead due to the OTS service is satisfactory for most applications.

View

Fulltext

Code

TR-IIS-96-006

Subject / Author / Abstract

ACCURACY ANALYSIS ON THE ESTIMATION OF CAMERA PARAMETERS FOR ACTIVE VISION SYSTEMS
SHENG-WEN SHIH, YI-PING HUNG AND WEI-SONG LIN.

In camera calibration, due to the correlations between certain camera parameters, e.g, the correlation between the image center and the camera orientation, an estimate of a set of camera parameters which minimizes a given criterion does not guarantee that the physical camera parameter estimates are themselves accurate. This problem has not drawn much attention from our computer vision society because most computer vision applications require only accurate 3D measurements and do not care much about the values of the physical parameters as long as their composite effect is satisfactory. However, in calibrating an active vision system where the cameras are motorized such that their parameters can be adapted to the environment, accuracy of the physical parameters is very critical because we need accuracy to establish the relation between the motor positions and the camera parameters (both intrinsic and extrinsic). The contribution of this work is mainly in error analysis of camera calibration , especially in the accuracy of the physical camera parameters themselves, for four different types of calibration problems. The first type is estimation of all the camera parameters simultaneously. The second type is estimation of all the other camera parameters given the image center. The third type is estimation of the extrinsic parameters given the intrinsic parameters. The last one is estimation of the intrinsic parameters given the extrinsic parameters. For each type of calibration problem, we derive (i) the covariance matrices of the estimated camera parameters and (ii) the sensitivity matrices of the estimated parameters with respect to the error of the given parameters. Factors that affect calibration accuracy are found to be the focal length, the area and resolution of the image sensor, the average object distance, the relative object depth, the 2D observation noise and the number of calibration points. Our theoretical analysis has been verified by computer simulations. With our error analysis, the most suitable camera calibration technique and calibration configuration for providing accurate camera parameters can be determined. Also, the accuracy of the estimated physical parameters can be predicted by using our analysis results.

View

Fulltext

Code

TR-IIS-96-007

Subject / Author / Abstract

CALIBRATION OF AN ACTIVE BINOCULAR HEAD
SHENG-WEN SHIH, YI-PING HUNG AND WEI-SONG LIN.

In this paper, we show how an active binocular head, the IIS head, can be easily calibrated with very high accuracy. Our calibration method can also be applied to many other binocular heads. In addition to the proposal and demonstration of a four-stage calibration process, there are three major contributions in this paper. First, we propose a MFL (Motorized-Focus Lens) camera model which assumes constant nominal extrinsic parameters. The advantage of having constant extrinsic parameters is to have a simple head/eye relation. Second, a calibration method for the MFL camera model is proposed in this paper, which separates the estimation of the image center and effective focal length from the estimation of the camera orientation and position. This separation has been proved to be crucial; otherwise, the estimates of camera parameters would be very noise-sensitive. Thirdly, we show that, once the parameters of the MFL camera model is calibrated, a nonlinear recursive least-square estimator can be used to refine all the 39 {\em kinematic} parameters. Real experiments have shown that the proposed method can achieve accuracy of one pixel prediction error and 0.2 pixel epipolar error, even when all the joints, including the left and right focus motors, are moved simultaneously. This accuracy is good enough for many 3D vision applications, such as 3D navigation, 3D object tracking, and even 3D reconstruction.

View

Fulltext

Code

TR-IIS-96-008

Subject / Author / Abstract

ADAPTIVE EARLY JUMP-OUT TECHNIQUE FOR FAST MOTION ESTIMATION IN VIDEO CODING
HO-CHAO HUANG, YI-PING HUNG AND WEN-LIANG HWANG.

An adaptive early jump-out technique for speeding up the block-based motion estimation is proposed. By using the new technique, we can speed up the full range search several times without losing the picture quality significantly. The proposed technique can also be embedded into almost all the existing fast motion estimation algorithms to speed up the computation further. Since the proposed technique can be embedded into the existing motion estimation algorithms, it can be applied to almost all the standard video codecs, such as the MPEG coder, and improve the coding speed of such codecs significantly. Our technique has been tested on the H.261 and the MPEG-I codecs, and the coding speed does improve significantly.

View

Fulltext

Code

TR-IIS-96-009

Subject / Author / Abstract

PHOINIX : A FAULT-TOLERANT OBJECT SERVICE IN OMA
DERON LIANG, S. C. CHOU AND S. M. YUAN.

The Object Management Architecture (OMA) has been recognized as a de facto standard in the development of object services in distributed computing environment. In a distributed system, the provision for failure-recovery is always a vital design issue. However, the fault-tolerant service has not been extensively considered in the current OMA framework, despite the fact that a increasing number of useful common services and common facilities have been adopted in OMA. In this paper, we propose a fault-tolerance developing environment, called Phoinix, which is compatible to the OMA framework. In Phoinix, object services can be developed with embedded fault-tolerance capability to tolerate both hardware and software failures. The fault-tolerance capability in Phoinix is classified into three levels: restart, rollback-recovery and replication; where the fault-tolerance capability enhances as the level increases. Currently, Phoinix is ported on Orbix 3.0 and on SunOS 4.2. Object services provided in the current version of Phoinix are able to tolerate hardware failures with capability up to the level two fault-tolerance, i.e., the level of rollback-recovery. We plan to continue the development of Phoinix so that object services can tolerate not only hardware failures but also software failures, such as process hangs, with all three levels of fault-tolerance.

View

Fulltext

Code

TR-IIS-96-010

Subject / Author / Abstract

OPTIMAL AUGMENTATION FOR BIPARTITE COMPONENTWISE BICONNECTIVITY IN LINEAR TIME
TSAN-SHENG HSU AND MING-YANG KAO.

A graph is componentwise fully biconnected if every connected component either is an isolated vertex or is biconnected. We consider the problem of adding the smallest number of edges to make a bipartite graph componentwise fully biconnected while preserving its bipartiteness. This problem has important applications to protecting sensitive information in cross tabulated tables. In this paper, we present a linear time algorithm for this problem.

View

Fulltext

Code

TR-IIS-96-011

Subject / Author / Abstract

OPTIMAL BI-LEVEL AUGMENTATION FOR SELECTIVELY ENHANCING GRAPH CONNECTIVITY WITH APPLICATIONS
TSAN-SHENG HSU AND MING-YANG KAO.

Our main problem is abstracted from several optimization problems for protecting information in cross tabulated tables and for improving the reliability of communication networks. Given an undirected graph $G$ and two vertex subsets $H_1$ and $H_2$, the {\it smallest bi-level augmentation problem} is that of adding to $G$ the smallest number of edges such that $G$ contains two internally vertex-disjoint paths between every pair of vertices in $H_1$ and two edge-disjoint paths between every pair of vertices in $H_2$. We give a data structure to represent essential connectivity information of $H_1$ and $H_2$ simultaneously. Using this data structure, we solve the bi-level augmentation problem in $O(n+m)$ time, where $n$ and $m$ are the numbers of vertices and edges in $G$. Our algorithm can be parallelized to run in $O(\log^2 n)$ time using $n+m$ processors on an EREW PRAM. By properly setting $G$, $H_1$ and $H_2$, our augmentation algorithm also subsumes several existing optimal algorithms for graph augmentation.

View

Fulltext

Code

TR-IIS-96-012

Subject / Author / Abstract

PANORAMIC STEREO IMAGING WITH COMPLETE-FOCUS VIEWS FOR VIRTUAL REALITY
HO-CHAO HUANG, YI-PING HUNG AND SHENG-WEN SHIH.

An image-based virtual reality (VR) system, the panoramic stereo imaging (PSI) system, is proposed in this paper. Traditional image-based VR systems can not to produce stereo views and dos not give the viewer the feel of realistic 3D depth. The proposed PSI system uses a stereo camera set to capture the stereo image pairs simultaneously, and produces the stereo panoramic images by using the camera parameters obtained from camera calibration. Furthermore, our PSI system can construct the clear stereo views from the complete-focus images. With both the stereo and complete-focus features, our PSI system provides more realistic and clearer views images than other image-based VR systems do.

View

Fulltext

Code

TR-IIS-96-013

Subject / Author / Abstract

THE BOUNDED LOSS RATE(BLR) PROBLEMS IN MULTICAST NETWORKS : PART I : PROBLEM FORMULATION
DERON LIANG AND DA-WEI WANG.

In this report, we consider the problem of the multicast routing in high speed networks. By multicasting we mean that to transmit data to multiple destinations simultaneously to avoid redundancy, therefore saving network bandwidth, and it is important for high bandwidth applications such as video conferencing, video on demand, etc. Previous works have focused on the issue of efficient bandwidth allocation. As the new applications emerge, in particular, the multimedia applications, the guarantee of the quality of service (QoS) becomes a major concerns in designing new generation of routing algorithms. In this report, we propose a new problem, called Bounded Loss Rate problem, where end-to-end total cell loss rate of each point-to-point connection is taken into consideration when routing a multicast stream in the network. We study the computational complexity for several variants of Bounded Loss Rate problem. We also review several related works in this report.

View

Fulltext

Code

TR-IIS-96-014

Subject / Author / Abstract

ERROR ANALYSIS ON CLOSED-FORM SOLUTIONS FOR KINEMATIC CALIBRATION
SHENG-WEN SHIH, YI-PING HUNG AND WEI-SONG LIN.

Many closed-form solutions have been developed for calibrating robot kinematic parameters. The existing closed-form solutions for kinematic calibration can be classfied into two categories according to the information they used. Methods estimating kinematic parameters by using pose measurements are referred to as the pose methods. While there is only one closed-form solution referred to as the point method using 3D point measurements for calibrating robot kinematic parameters. Relatively less work has been devoted to the error analysis on the calibration methods. Error analysis results are very useful to serve as a guideline for selecting calibration techniques, for determining the calibration condition and even for designing a robot head or a robot arm when considering the calibration task. In this paper, we derived the expressions of variances of the kinematic parameters estimated by using the point method or the pose method, respectively. The derived error variances for the point method are functions of the calibration range, number of measurements, amount of measurement noise and amount of joint value noise. Furthermore, if the joint under calibration is revolute, then the error variances are also functions of the distance between the calibration point and the revolute joint axis and length of the link corresponding to the joint under calibration. The derived error variances for a pose method are functions of the calibration range, number of measurements, amount of measurement noise, amount of the joint value noise and length of the link corresponding to the joint under calibration.

View

Fulltext

Code

TR-IIS-96-015

Subject / Author / Abstract

SHAPE FROM TEXTURE: DIRECT ESTIMATION OF PLANAR SURFACE ORIENTATIONS USING CONTINUOUS WAVELET TRANSFORM
WEN L. HWANG, CHUN-SHIEN LU AND PAU-CHOO CHUNG.

In this paper, we propose a new method to estimate the orientations of a planar surface under perspective projection. Texture variations are characterized by the ridges of continuous wavelet transform. The ridges of a continuous wavelet transform mark the places in the spatial frequency where the energy of an image is mostly concentrated. We demonstrate that the ridges contain crucial information in determining the planar surface orientations. %under the perspective projected model. An algorithm to determine the ridge points of a textured image is presented. The ridge points are organized into disjoint ridge surfaces. We show that textural information giving the perception of surface orientations can be characterized from a ridge surface of the textured image. The scale in the ridge surface is a parabolic function of the tilt and slant angles. This provides a closed-form solution to determine %an efficient way in determining the surface orientations directly with information only from the restriction of the wavelet transform to the ridge surface. We have used our algorithm on several textured real-world images in noise-free and noisy environments. The resultant estimation of the tilt and slant angles is accurate up to a $3^{\circ}$ average error even in low $SNR$ environments.

View

Fulltext

Code

TR-IIS-96-016

Subject / Author / Abstract

MULTISCALE EDGE DETECTION IN RANGE IMAGES VIA NORMAL CHANGES
Chwen-Jye Sze, Hong-Yuan Mark Liao, Hai-Lung Hung, Kuo-Chin Fan and Shing-Jong Lin

A new edge detection technique based on detecting normal changes is proposed. Most of the existing range-image-based edge detection algorithms base their detection criterion on depth or curvature changes. However, depth or curvature changes do not have keen sensitivity on detecting roof ( or crease ) edges. Using normal changes as a detecting criterion, on the contrary, can easily detect the existence of a roof edge even the change across a boundary is slight. Experimental results using both synthetic and real images demonstrate that the proposed method is indeed superb in detecting roof ( or crease ) edges.

View

Fulltext