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

Institute of Information Science, Academia Sinica

Library

Print

Press Ctrl+P to print from browser

2000 Technical Report

:::

Code
Subject / Author / Abstract
View

Code

TR-IIS-00-001

Subject / Author / Abstract

REGION ENCODING DIAGRAM FOR FULLY SYMBOLIC VERIFICATION OF REAL-TIME SYSTEMS
FARN WANG

RED (Region Encoding Diagram), first reported in TACAS'2000, is a BDD-like data-structure for fully symbolic verification of symmetric real-time systems with single clock per process We propose to extend RED for asymmetric real-time systems with unrestricted number of global or local clocks. Unlike in DBM which records differences between pairs of clock readings, we records the ordering among fractional parts of clock readings into integer sequences encoded in RED's. Like BDD, the new RED is also a minimal canonical form for its target system state-space representations. The number of variables used in RED is $O(|X|\log |X|)$ when $X$ is the clock set in the input system description. Experiment has been carried out to show the possible verification efficiency through the intense data-sharing nature of RED.

View

Fulltext

Code

TR-IIS-00-002

Subject / Author / Abstract

MULTIPURPOSE WATERMARKING FOR IMAGE AUTHENTICATION AND PROTECTION
CHUN-SHIEN LU AND HONG-YUAN MARK LIAO

We propose a novel multipurpose watermarking scheme, in which robust and fragile watermarks are simultaneously embedded, for copyright protection and content authentication. By quantizing a host image's wavelet coefficients as masking threshold units (MTUs), two complementary watermarks are embedded using cocktail watermarking and they can be blindly extracted without access to the host image. For the purpose of image protection, the new scheme guarantees that, no matter what kind of attack is encountered, at least one watermark can survive well. On the other hand, for the purpose of image authentication, our approach can locate the part of the image that has been changed and tolerate some incidental processes that have been executed. Experimental results show that the performance of our multipurpose watermarking scheme is indeed superb in terms of robustness and fragility.

View

Fulltext

Code

TR-IIS-00-003

Subject / Author / Abstract

PROGRAMMING GRAPHICAL USER INTERFACES IN CHINESE WITH EASE
CHUAN-CHIEH JUNG ... [ET AL.]

View

not for public 原文請洽圖書室或郭譽申老師

Code

TR-IIS-00-004

Subject / Author / Abstract

SIMPLIFIED GRAPH FORMULATION AND ALGORITHMS FOR MULTI-WAY DATAFLOW CONSTRAINTS
CHUAN-CHIEH JUNG

View

not for public 原文請洽圖書室或郭譽申老師

Code

TR-IIS-00-005

Subject / Author / Abstract

ON RECOGNITION OF AND-OR SERIES-PARALLEL DIGRAPHS
JICHIANG TSAI, DE-RON LIANG AND HSIN-HUNG CHOU

View

Fulltext

Code

TR-IIS-00-006

Subject / Author / Abstract

RETRIEVING INFORMATION FROM DOCUMENT IMAGES: PROBLEMS AND SOLUTIONS
FU CHANG

An information retrieval system that captures both visual and textual contents from paper documents can derive maximal benefits out of DAR techniques while demanding little human assistance for achieving its goals. This article discusses the technical problems, solution methods and integration of them into a well-performing system. Focus of the discussion is on very hard applications, for example, to Chinese and Japanese documents. In addition to large group of potential readers, the latter types of documents create many technical issues that deserve experts’attention. The complicated Chinese or Kanji characters, for example, impose serious problem for image binarization. The coexistence of vertical and horizontal textlines on the same page renders document segmentation difficult. The large number of characters also challenges the way textual contents are recognized and retrieved. Problems discussed in this article will be centered on these issues. Solution methods will also be highlighted , with the emphasis placed upon some new ideas, including window-based binarization using scale measures, document layout analysis as solving multiple constraint problem, and full-text searching technique capable of evading machine recognition errors.

View

Fulltext

Code

TR-IIS-00-007

Subject / Author / Abstract

ROBUST EZW IMAGE COMPRESSION USING RATE-DISTORTION ANALYSIS
Jen-Chang Liu, Wen-Liang Hwang, Wen-Jyi Hwang, and Ming-Syan Chen

The EZW(Embedded Zerotree Wavelet)-like image compression algorithms lack the error-resilience ability in noisy transmission environments. We propose the channel- optimized source coding scheme to improve the robustness of them. First, a block-based method is adopted to localize the error effects. Then we assign bits to each block by applying dynamic bit allocation to the block-based EZW algorithm based on the rate- distortion functions computed from the channel noise models. The performance of our method was evaluated on both the binary symmetric channel and burst noise channel models.

View

Fulltext

Code

TR-IIS-00-008

Subject / Author / Abstract

ELLIPSOIDAL MODELING FOR ARTICULATED ROBOT MANIPULATORS FOR INTERACTIVE MOTION PLANNING
Ming-Yi Ju, Jing-Sin Liu and Kao-Shing Hwang

The report presents an enclosing and enclosed ellipsoids based solid modeling technique for serial links of articulated robot manipulators. This modeling allows the collision detection for interactive robot motion planning in a graphical simulation environment or in a telerobotic simulator be performed efficiently and precisely. A systematic way of determining the kinematic transformation matrices between links and its associated ellipsoids model is presented. An example, a PUMA560 manipulator, is shown in details to demonstrate the proposed modeling technique.

View

Fulltext

Code

TR-IIS-00-009

Subject / Author / Abstract

MATCHING PURSUIT LOW-BIT RATE VIDEO CODING WITH DICTIONARY OPTIMIZED BY SHAPE-GAIN VECTOR QUANTIZER
Yao-Tang Chou, Wen-Liang Hwang, Chung-Lin Huang

We show that the techniques of the shape-gain product vector quantizer(VQ) can be used to optimize the dictionary of the matching pursuit codec and produce good results. We start with an initial dictionary and obtain a dictionary that is wellz adapted to the training sequences. The performance is evaluated based on a comparison of our method with other methods.

View

Fulltext

Code

TR-IIS-00-010

Subject / Author / Abstract

SINGULARITY DETECTION AND CHARACTERIZATION WITH COMPLEX-VALUED WAVELETS AND THEIR APPLICATIONS
Chun-Liang Du and Wen-Liang Hwang

We prove that the wavelet modulus maxima with a complex-valued wavelet can detect and characterize singularities. This can be regarded as an extension of the previous wavelet modulus work with a real wavelet. The ridges of wavelet transforms are the places in the time-frequency plane where the local energies of a signal are mostly concentrated. We show that based on the ridges of the wavelet transforms, the osciallating singularities are better located and their oscillating components are better characterized than they are based on the general maxima of real-valued wavelet transforms. We demonstrate potential applications of these techniques.

View

Fulltext

Code

TR-IIS-00-011

Subject / Author / Abstract

FAST AND ACCURATE COLLISION DETECTION BASED ON ENCLOSED ELLIPSOID
Ming-Yi Ju*,**, Jing-Sin Liu*, Shen-Po Shiang*, Yuh-Ren Chien*, Kao-Shing Hwang** and Wan-Chi Lee *

A fast and accurate method for detecting the collisions of convex polyhedra in a graphical simulation environment based on a newly developed method of distance estimate is presented. By the use of the enclosing and the enclosed ellipsoids of convex polyhedra, potential collisions can be detected more accurate than those methods using only bounding volume for object representation, and more efficient than the polyhedral methods. An approach for computing the enclosed ellipsoid of a convex polyhedron by compressing, stretching and scaling operations on its best-fit enclosing ellipsoid is introduced. Graphical simulations of moving objects in three-dimensional space and multiple robot arm system applications are conducted to demonstrate the accuracy of the proposed algorithm for collision detection and minimum separating distance computation.

View

Fulltext

Code

TR-IIS-00-012

Subject / Author / Abstract

MEAN QUANTIZATION-BASED FRAGILE WATERMARKING FOR IMAGE AUTHENTICATION
Gwo-Jong Yu*, Chun-Shien Lu**, Hong-Yuan Mark Liao**

The existing digital image editing tools have made the authentication of digital images an important issue. The objective of this paper is to propose an image authentication scheme, which is able to detect malicious tampering while tolerating some incidental distortions. By modeling the magnitude changes caused by incidental distortion and malicious tampering as Gaussian distributions with small and large variances, respectively, we propose to embed a watermark by using a mean quantization technique in the wavelet domain. The proposed scheme is superior to the conventional quantization- based approaches in terms of the credibility of authentication. Statistical analysis is conducted to show that the probabilities of watermark errors caused by malicious tampering and incidental distortion will be, respectively, maximized and minimized when our new scheme is applied. Experimental results demonstrate that the credibility of our method is superior to that of the conventional quantization-based methods under malicious attack followed by an incidental modification, such as JPEG compression, sharpening or blurring.

View

Fulltext

Code

TR-IIS-00-013

Subject / Author / Abstract

STRUCTURAL DIGITAL SIGNATURE FOR IMAGE AUTHENTICATION: AN INCIDENTAL DISTORTION RESISTANT SCHEME
Chun-Shien Lu and Hong-Yuan Mark Liao

The existing digital data verification methods are able to detect regions that have been tampered with, but are too fragile to resist incidental manipulations. This paper proposes a new digital signature scheme which makes use of an image's contents (in the wavelet transform domain) to construct a structural digital signature (SDS) for image authentication. The characteristic of the SDS is that it can tolerate content-preserving modifications while detecting content-changing modifications. Many incidental manipulations, which were detected as malicious modifications in the previous digital signature verification or fragile watermarking schemes, can be bypassed in the proposed scheme. Performance analysis is conducted and experimental results show that the new scheme is indeed superb for image authentication.

View

Fulltext

Code

TR-IIS-00-014

Subject / Author / Abstract

OPTIMAL PROCESSOR MAPPING FOR LINEAR-COMPLEMENT COMMUNICATION ON HYPERCUBES AND THEIR VARIATIONS
Yomin Hou, Chien-Min Wang, Chiu-Yu Ku, Lih-Hsing Hsu

In this technical report, we address the problem of minimizing channel contention of linear-complement communication on wormhole-routed hypercubes. Our research reveals that, for traditional routing algorithms, the degree of channel contention of a linear- complement communication can be quite large. To solve this problem, we propose an alternative approach, which applies processor mapping at compile time. In this compiler approach, processors are logically reordered according to the given communication(s) so that the new communication(s) can be efficiently realized on the hypercube network. It is proved that, for any linear-complement communication, there exists a reordering mapping such that the new communication has minimum channel contention. An O(n3) algorithm is proposed to find such a mapping for an n-dimensional hypercube. An algorithm based on dynamic programming is also proposed to find an optimal reordering mapping for a set of linear-complement communications. Several computer simulations have been conducted, and the results clearly show the advantage of the proposed approach.

View

Fulltext

Code

TR-IIS-00-015

Subject / Author / Abstract

OSC: OPTIMAL SELECTIVE CACHING FOR VIDEO TRANSMISSION WITH PROXY SERVERS
Ray-I Chang, Shin-Hung Chang, Jan-Ming Ho

Proxylib servers have been successfully used in reducing playback latency and network bandwidth required for delivering VBR videos. By storing portions of video programs in local video proxies and the rests in remote servers, the peak and variability of network bandwidth requirements can be reduced. Regarding to which portion of video frames should be cached at higher priority, let's consider an MPEG video in which an I-frame is referenced by all the other frames in the same GOP. Obviously, losing a packet belonging to an I-frame makes it difficult to recover all the frames of the same GOP. In this paper, based on the video proxy problem introduced by [1], we present the Optimal Caching (OC) algorithm to minimize cache size required for delivering a specific video program subject to network bandwidth and client buffer size constraints, and the Optimal Selective Caching (OSC) algorithm to further select the most appropriate portions of a video program for caching in the video proxy. In our experiments, it is shown that our algorithm is more effective than the previous algorithm. Our OC and OSC algorithms reduce cache size by 50% as compared with the algorithm presented in [1]. Furthermore, the ratio of I-frames cached in the video proxy is 5 times larger than the result of applying the algorithm presented by [1]

View

Fulltext

Code

IM-IIS-00-001

Subject / Author / Abstract

WRAPPER AGENT KERNEL(SHOPBOT TOOLKIT) VERSION 0.1 The manual
CHUN-NAN HSU, HUNG-HSUAN HUANG, ELAN HUNG, CHIAN-CHI CHANG

View

not for public 原文請洽圖書室