Institute of Information Science, Academia Sinica

Library

Print

Press Ctrl+P to print from browser

2005 Technical Report

Code

Subject / Author / Abstract

View

Code

TR-IIS-05-001

Subject / Author / Abstract

A Block-Based SNR Scalable Wavelet Video Codec with Sub-pixel Motion Vectors and R-D Optimization
Cho-Chun Cheng and Wen-Liang Hwang

We propose a block-based wavelet codec in which motion vector estimation and motion residual encoding are performed within a wavelet domain. By interpolation on dyadic wavelet transform, we show that motion vector estimation in the wavelet domain can achieve sub-pixel precision. To improve PSNR performance at low bit rates, we propose a bit-plane-based rate-distortion (R-D) optimization algorithm. This algorithm allocates an optimal number of bit-planes to each macroblock. Our codec is SNR scalable and our bit-stream syntax is fully compatible with that of H.263. Experiments show that our block-based wavelet codec outperforms a framebased wavelet codec. Also, compared with H.263 baseline results, our wavelet codec is competitive at low bit rates, and is superior at higher bit rates.

View

Code

TR-IIS-05-002

Subject / Author / Abstract

Media Hash-dependent Image Watermarking Resilient Against Both Geometric Attacks and Estimation Attacks Based on False Positive-Oriented Detection
Chun-Shien Lu, Shih-Wei Sun, Chao-Yong Hsu, and Pao-Chi Chang

The major disadvantage of existing watermarking methods is their limited resistance to extensive geometric attacks. In addition, we have found that the weakness of multiple watermark embedding methods that were initially designed to resist geometric attacks is their inability to withstand the watermark-estimation attacks (WEAs), leading to reduce resistance to geometric attacks. In view of these facts, this paper proposes a robust image watermarking scheme that can withstand geometric distortions and WEAs simultaneously. Our scheme is mainly composed of two components: (i) mesh generation and embedding to resist geometric distortions; and (ii) construction of media hash-based content-dependent watermark (CDW) to resist WEAs. Furthermore, we propose a false positive-oriented watermark detection mechanism, which can be used to determine the existence of a watermark so as to achieve a trade-off between correct detection and false detection. Extensive experimental results obtained using the standard benchmark and WEAs, and comparisons with relevant watermarking methods confirm the excellent performance of our method in improving robustness. To our knowledge, such a thorough evaluation has not been reported in the literature before.

View

Code

TR-IIS-05-003

Subject / Author / Abstract

Proving∀µ -Calculus Properties with SAT-Based Model Checking
Bow-Yaw Wang

In this paper, we present a complete bounded model checking algorithm for the universal fragment of µ-calculus. The new algorithm checks the completeness of bounded proof of each property on the fly and does not depend on prior knowledge of the completeness thresholds. The key is to combine both local and bounded model checking techniques and use SAT solvers to perform local model checking on finite Kripke structures. Our proof-theoretic approach works for any property in the pecification logic and is more general than previous work on specific properties. We report experimental results to compare our algorithm with the conventional BDD-based algorithm.

View

Code

TR-IIS-05-004

Subject / Author / Abstract

Queuing Delay Propagation Model (QDPM)-based Queuing Region Determination for Available Bandwidth Estimation of Multimedia QoS
Yu-Chen Huang, Chun-Shien Lu, Hsiao-Kuang Wu

Available bandwidth is an important factor that can be used to adapt the sending rate to network conditions, so that packet loss, caused by congestion, can be significantly reduced before error control mechanisms are employed. To this end, we propose an active probing-based queuing delay propagation model (QDPM)-based scheme for available bandwidth estimation. Common assumptions, including use of the fluid traffic model and restriction to the single-hop network model, that have been made in the literature are relaxed in this study. Unlike the increasing trend of one-way delays that is widely used in probe rate model-based methods, in the proposed method, we exploit the magnitude relationship among the input gap, output gap, and queuing delay to define the types of queuing regions for each packet pair. In addition, we quantify the captured traffic ratio (CTR), which is defined as the total output gaps of joint queuing regions per total input gaps, and use it to derive the relationship between probing rate and available bandwidth. To justify the performance of our method, we further investigate how the estimation resolution and the probing noise ratio are related to the accuracy of available bandwidth estimation. Extensive simulations have been conducted and comparisons with other methods have been made to verify the effectiveness of our method for accurate and smooth estimation, no matter whether single-hop or multi-hop environments are considered.

View

Code

TR-IIS-05-005

Subject / Author / Abstract

SinicView: A Visualization Environment for Comparisons of Multiple Sequence Alignment Tools
Arthur Chun-Chieh Shih, D.T. Lee, Laurent Lin, Chin-Lin Peng, Shiang-Heng Chen, Chun-Yi Wong, Meng-Yuan Chou, and Tze-Chang Shiao

Motivation: Deluged by completed genomic sequences, the need to align longer sequences becomes more urgent, and many more tools have thus become available. In the initial stage of sequence analysis, a biologist usually faces with the questions about how to choose the best tool to align sequences of interest and how to analyze and visualize the alignment results, and then with the question about whether unaligned regions produced by the tool are indeed not homologous or are just results due to inappropriate alignment tools or scoring systems used. Although several systematic evaluations of multiple sequence alignment programs have been proposed, they may not provide a standard-bearer for most biologists because those unaligned regions in these evaluations are never discussed. Thus, a tool that allows cross comparison of the alignment results obtained by different tools could help a biologist evaluate their correctness and accuracy. Results: In this paper, we present a versatile alignment visualization system, called SinicView, (for Sequence-aligning INnovative and Interactive Comparison VIEWer), which allows the user to efficiently compare and evaluate assorted alignment results obtained by different tools. SinicView calculates similarity of the alignment outputs under a sliding window using the sum-of-pairs method and provides scoring profiles of each set of aligned sequences. The user can visually compare alignment results either in graphic scoring profiles or in plain text format of the aligned nucleotides along with the annotations information. With SinicView, users can use their own data sequences to compare various alignment tools or scoring systems and select the most suitable one to perform alignment and sequence analysis. We illustrate the capabilities of our visualization system by comparing alignment results obtained by ClustalW, MLAGAN, MAVID, and MULTIZ, respectively.

View

Code

TR-IIS-05-006

Subject / Author / Abstract

Enhanced Bulk Scheduling for Supporting End-to-End Delay Requirements
Yung-Cheng Tu, Meng Chang Chen, Yeali S. Sun and Wei-Kuan Shih

Providing end-to-end delay guarantees for delay sensitive applications is an important packet scheduling issue of routers. In this paper, to support end-to-end delay requirements, we propose a novel network scheduling scheme, called the Bulk Scheduling Scheme (BSS), built on top of existing schedulers of intermediate nodes without modifying transmission protocols on both sender and receiver sides. By inserting TED packets into packet flows at the ingress router periodically, the BSS schedulers of the intermediate nodes can dynamically allocate the necessary bandwidth to each flow to enforce the end-to-end delay, according to the information in TED packets. The introduction of TED packets incurs a lower overhead than the per-packet marking approaches. Three flow bandwidth estimation methods are presented and their performance properties are analyzed. BSS also provides a dropping policy to discard late packets and a feedback mechanism to discover and resolve the bottlenecks. The simulation results show that BSS performs efficiently as expected

View

Code

TR-IIS-05-007

Subject / Author / Abstract

User Scenarios and Designs of Smart Pantry, Object Locator and Walker’s Buddy: Consumer Electronicsfor the Elderly
Jane W. S. Liu ... [et al.]

In the recent decade, declining birth rate and increasing average life span have led to significant growth in the over-60 fraction of population in developed and developing countries. One can easily deduce from this trend the growing need and business opportunity for consumer electronic appliances and services designed to improve the quality of life and safety of the elderly. Representative devices of this kind include smart pantry, object locater and walker’s buddy. A smart pantry holds household supplies, inventories its own contents, and automates the purchasing and delivery of the supplies stored in it. An object locater can help its user find personal and household items such as keys, glasses and remote control. A walker’s buddy scans pavement and alerts the user of steps and obstacles ahead. While such devices are motivated by the needs and desires of the elderly, busy and absent-minded people of all ages can also enjoy their services. The report describes typical user scenarios of these devices. It also describes and evaluates alternative designs. The designs using only today’s technologies are less than ideal in usability and robustness. The advances needed to significantly improve the devices are in near horizon. The report identifies the shortfalls in technology for each of the devices.

View

Code

TR-IIS-05-008

Subject / Author / Abstract

A General Model for Medication Scheduling
P. C. Hsiu, H. C. Yeh, P. H. Tsai, C. S. Shih, D. H. Burkhardt, T. W. Kuo, J. W. S. Liu and T. Y. Huang

We describe here a general model, called the GMS (General Medication Schedule) model, for specifying requirements and constraints of medication schedules. A specification based on the model captures limits in dosage and timing given by medication directions in general and guidelines and preferences specific to the user. The controller of a smart dispenser can compute schedules of dispenser commands based on the specification. By executing the commands according to the schedules, the dispenser deliveries reminders and dispenses medications in conformance with directions. The rules embedded in the specification provide the dispenser with criteria needed for compliance monitoring and enforcement.

View

Code

TR-IIS-05-009

Subject / Author / Abstract

Automatic Verification of a Model Checker in Rewriting Logic
Bow-Yaw Wang

In this paper, we use the reflection of rewriting logic to analyze a bounded local model checker for infinite-state systems formally. We introduce three-valued logic in a local model checking algorithm to formalize aborted verification. To improve its efficiency, several optimizations are introduced in the algorithm. We show how to exploit the reflection of rewriting logic and model check our bounded local model checker in rewriting logic formally.

View

Code

TR-IIS-05-010

Subject / Author / Abstract

AgentToolboxVersion 2 User Manual
Author: Siek Harianto; Reviewer: Chunnan Hsu

View

Code

TR-IIS-05-011

Subject / Author / Abstract

Estimation of Skew Angles for Scanned Documents Based on Piecewise Covering by Parallelograms
Fu Chang, Chien-Hsing Chou, and Shih-Yu Chu

We propose a fast and robust skew estimation method for scanned documents that estimates skew angles based on piecewise covering of objects, such as textlines, figures or tables. The method first divides a document image into a number of non-overlapping slabs in which each object is covered by parallelograms. It then estimates the skew angle based on these parallelograms or, equivalently, their complementary regions. Putting this method to a systematic test and comparing it with a few alternatives, we find favorable results for our method in terms of accuracy rates, sensitivity to non-textual objects, effectiveness in dealing with documents of unspecified reading order, and computational efficiency. Some work is also conducted to find an effective way to further shorten its computation time at the expense of an extremely small loss of accuracy.

View

Code

TR-IIS-05-012

Subject / Author / Abstract

An Application-layer Security Control for Real-time Video Streaming
Chia-Hui Wang, Jan-Ming Ho

In the shared Internet, real-time video streaming service is now prevalent and popular. Real-time video streaming services such as video conferencing, surveillance videos and live videos may preserve privacy and commercial values. Thus, it’s very important to secure real-time video streaming services from potential eavesdropper. However, security has been aware of inadequacy for real-time video streaming applications because it contends for lots of resources. In this paper, we propose an effective application-level security control to protect the real-time video streaming. This method will economically transpose the data block in the sender’s buffer by a given secrete key of database through a receiver’s buffer occupancy feedback control. Authenticated receiver can restore the scrambled video data from the receiver’s buffer by the secrete key to playback the original video. However, without the secrete keys to restore the data, eavesdropper will not be able to playback the video. It’s hard to break the encryption even if eavesdropper tries to store the scrambled video data for processing later. We evaluate the proposed scheme’s effect to the playback QoS of real-time video streaming and secure ability through theoretical analysis and some experimental data. Furthermore, this method will be applied on a test-bed of Internet video surveillance services to demonstrate the resource-saving and highly secure capabilities.

View

Code

TR-IIS-05-013

Subject / Author / Abstract

Active Feedback for Effective Web Search
Ray-I Chang, Jan-Ming Ho

Current search engines with arrays of servers can provide efficient web content services. However, as their returned results are usually enormous mass, finding target information is still time-consuming. To increase the correctness of returned results, different page ranking methods were introduced. Some of them also try to use users’ feedback to increase their precision in ranking. However, as the traditional approaches are passive in feedback and greedy in search, experiments show that the average error ratio is over 20%. Their returned results are usually too large to satisfy users’ needs. In this paper, an active feedback technology is introduced. It bases on the concept of balanced tree to present some critical questions for guiding users to have the proper feedback in further searching. The same idea can be applied to assist either distributed or P2P (peer-to-peer) search engines to balance workloads and speed responses.

View

Code

TR-IIS-05-014

Subject / Author / Abstract

Video Delivery on Content Networks
Ray-I Chang, Jan-Ming Ho

Abstract. Behaviors of Internet services are changing from computation sharing to content sharing. Due to these changes, the weakness of conventional network architecture and its inadequate in service support are apparent. To resolve these problems, content networks are introduced. A content network tries to reorganize the Internet by a content-centric way to improve the system's scalability and to protect the system from distributed denial-of-service attacks. It was taken into one of the most important platform of network applications (such as e-commerce) in the future. In this paper, we investigate some key technology issues of content delivery of streaming multimedia, which has both the biggest challenge and opportunity. Different from small-sized hypertext and image, the growing-popular multimedia content has huge size. It is impractical to be cached entirely and requires to be partitioned into small portions for delivery from multi-servers. As a multimedia content is VBR (variable-bit-rate) and requires guaranteed QoS (quality-of-service), each serving-peer needs a good delivery schedule for real-time streaming. In this paper, we focus only on the multi-servers caching/streaming problem of multimedia delivery. Without addressing content indexing and routing, the proposed method can be applied for different content networks.

View

Code

TR-IIS-05-015

Subject / Author / Abstract

Design and Implementation of Domain-Based Proxy Prefetching
Ray-I Chang, Jan-Ming Ho

Users are usually interested in some specific domains while surfing the Internet. Based on such domain-preferential browse-behavior, the Domain-Top (DT) proxy prefetching method is proposed. DT uses the popular pages in the same popular domain to model users’ future demands. If there is a request for any one of the pages in the popular domain, the popular pages in the same domain are considered as its future demands and will be prefetched. The development of DT prefetching is based on a hypothesis that the browse-behavior is always domain-preferential. However, clients may explore the Internet aimlessly and will aceess different domains in the near future. Analyzing proxy logs without considering diverse browse-behavior may acquire wrong anticipation in prefetching. This paper proposes the DTC (DT prefetching with Classification) method that tries to improve DT prefetching by removing unreliable logs. DTC adopts the concept of entropy to discriminate the browse-behavior from "domain mode" and "exploratory mode". Only access logs in domain mode are considered in calculating the popular domains. Different from DT that considers a constant number of popular pages in prefetching, we ssign each domain a suitable number of popular pages. Experiments on real traces show that the proposed DTC method can achieve higher hit ratio than that of the DT method. As DTC utilizes only the historical logs to offline decide the popular pages and the popular domains for prefetching, only few function modules on the present proxy need to be revised. It imposes small burden and can be easily implemented in Squid -- the most famous open source proxy server.

View

Code

TR-IIS-05-016

Subject / Author / Abstract

Improving End-to-End Performance of RED
Chin-Fu Ku, Ray-I Chang, Jan-Ming Ho, Sao-Jie Chen

Congestion control mechanisms play a important role in today’s Internet, since network environments are geting more and more complicated. Besides, new applications request diverse services delivered by the network. Random Early Detection (RED) provides an efficient and low-overhead mechanism to effectively control congestion. Nevertheless, RED would slow down TCP senders’ reaction to change of network condition, in particular the bottleneck link with long propagation delay or RED with a smaller weighted factor. Thus, we proposed a better way to drop/mark packets not just based on queue occupancy. In this paper, an enhancement intending to improve the performance in terms of delay, delay jitter and packet loss ratio is proposed. The basis idea is to react quickly to major changes in network conditions so as to shorten the time it takes for a sender to gather signals, e.g., round-trip time and lost packets from networks. The simulation results show the enhancement could effectively raise the performance in terms of delay, delay jitter and packet loss ratio.

View

Code

TR-IIS-05-017

Subject / Author / Abstract

Aggressive Traffic Smoothing for Online Delivery
Jeng-Wei Lin, Ray-I Chang, Jan-Ming Ho, Feipei Lai

Traffic smoothing is an efficient means to reduce the bandwidth requirement for transmitting a VBR video. Several traffic smoothing algorithms have been presented to offline compute the transmission schedule for a prerecorded video. For live video applications, Sen et al. present an online algorithm referred to as SLWIN(k) to compute the transmission schedule on the fly. SLWIN(k) looks ahead W frames to compute the transmission schedule for the next k frametimes, where k≤W. Note that W is upper bounded by the initial delay of the transmission schedule. The time complexity of SLWIN(k) is O(W*N/k) for an N frame live video. In this paper, we present an O(N) online traffic smoothing algorithm denoted as ATS (Aggressive Traffic Smoothing). ATS aggressively works ahead to transmit more data as early as possible for reducing the peak rate of the bandwidth requirement. We compare the performance of our algorithm with SLWIN(k) based on several benchmark video clips. Experiments show that ATS further reduces the bandwidth requirement, especially for interactive applications in which the initial delays are small.

View

Code

TR-IIS-05-019

Subject / Author / Abstract

數位典藏國家型科技計畫 - 數位權利管理技術簡介
Jen-Hao Hsiao, Lee-Feng Chien, Chu-Song Chen

View

Code

TR-IIS-05-020

Subject / Author / Abstract

Coalition Formation for Resource Co-allocation Using BDI Assignment Agents
Kiam Tian Seow, Kwang Mong Sim and Yuan Chia Kwek

A new distributed agent algorithm for resource coallocation to different tasks is proposed. The algorithm extends a BDI assignment algorithm with resource capability reasoning. It enables resource agents to form coalitions via iterative BDI reasoning and negotiation given the limited capabilities of the resources vis-`a-vis task requirements, without directly limiting the coalition size. In the worst case analysis, the number of negotiation rounds required by the algorithm is shown to be of a polynomial order in the number of agents. Empirical evidence from simulations shows that the algorithm yields favorable results in terms of the number of effective coalitions formed for different tasks. Fundamental differences between the proposed algorithm and related work are also discussed.

View

Code

TR-IIS-05-021

Subject / Author / Abstract

Generalized Edge Coloring for Channel Assignment in Wireless Networks
Chun-Chen Hsu, Pangfeng Liu, Da-Wei Wang, Jan-Jan Wu

This paper introduces a new graph theory problem called generalized edge coloring (g.e.c). g.e.c is similar to traditional edge coloring, with the difference that a vertex can be adjacent to up to k edges that share the same color. g.e.c. can be used to formulate the channel assignment problem in multi-channel multi-interface wireless networks. We provide theoretical analysis for this problem. Our theoretical findings can be useful for system developers of wireless networks. We show that when k = 3, there is no optimal solution. When k = 2 and the maximum degree of the graph is no more than 4, or is a power of 2, we derive optimal algorithms to find a g.e.c. Furthermore, if given one extra color, we can find a g.e.c. that uses minimum number of edge colors for each vertex.

View

Code

TR-IIS-05-022

Subject / Author / Abstract

A Micro-Matching Foundation of Neutral Technical Progress
Been-Lon Chen, Jie-Ping Mo, Ping Wang

We develop a general two-sided micro-matching framework with heterogeneous workers and machines that permits a complete analysis of neutral technical progress commonly used in neoclassical production theory, without a priori restrictions on the functional forms of the production technology. We use the concept of “production core” to determine stable task assignments and the corresponding factor-return distributions, and then examine how these equilibrium outcomes respond to neutral technical progress pertaining to a particular worker or to all factors. Technical progress that is uniform in all factors will not alter quilibrium micro-matching. Technical progress of the labor-augmenting type may (i) cause a “turnover” by destroying existing stable task assignments and creating new stable task assignments, (ii) generate a factor-return redistribution similar to Harrod-neutral technical progress in neoclassical theory, and (iii) create “spillover” effects from the innovating worker to his/her potential matching machines and his/her directly and indirectly competing workers. The possibility of turnovers and the extent to which factor returns are redistributed depend on the value of the current matches, the extent of outside threats from latent technologies, and the size of technical progress.

View

Code

TR-IIS-05-023

Subject / Author / Abstract

Real-Time Scheduling by Cascading
Ray-I Chang, Ruei-Chuan Chang, Jan-Ming Ho

Real-time scheduling is important for modern computer systems to support increasingly popular multimedia applications. In this paper, we consider a simple video server that receives the commands from clients and sends the video data without error occurred. In the video server, there is one parent thread for dealing with the arrival video tasks. After receiving a new video task from a client, a new child thread is created to determinate the real-time requirements for disk access. Based on the results of traffic smoothing and the sizes of disk blocks, the child thread sends real-time disk requests to the system. Then, a multi-segment cascade scheme is applied to implement the real-time disk scheduling routine on UnixWare operating systems. Both the simulation results and the implementation results are presented for comparisons. The same idea may be extended to handle the real-time scheduling problem with both video server and video proxy [30].

View

Code

TR-IIS-05-024

Subject / Author / Abstract

An Adaptive Prototype Classification Method with Applications to Genetic Marker Selection
Ke-Shiuan Lynn, Chin-Chin Lin, Wen-Harn Pan, and Fu Chang

Motivation: Ethnic origin is a complex trait that can be affected via multiple genetic factors. The traditional method, based on studying one gene or a few genes at a time, is not effective in profiling such a complex nature. Due to the advancement in high throughput genotyping, massive polymorphism (marker) information becomes available. Polymorphisms contain information on individuals’ inherited traits including disease susceptibility, physical appearance, ethnic origins, etc. However, typing multiple genetic markers can still be costly, and constructing an appropriate ethnic classifier may involve heavy computation. To cope ith these problems, we propose a new method that can accomplish two things at a low computational cost: finding a minimum number of genetic markers and constructing an ethnic classifier based on this minimum set of markers. Results: We present the following three types of results: (1) By testing on artificial datasets with specified degrees of separation, our results suggest that, when population groups have distinguished ethnic origins, the number of prototypes and the test accuracy of the classifier constructed by APL are nearly constant with respect to n, as long as n exceeds a threshold. On the other hand, when the groups are of high admixture, both the number of prototypes and the test accuracy of the constructed classifier 2 become unstable. (2) The proposed adaptive prototype learning (APL) method has much lower training cost and comparable test accuracy to two other methods, STRUCTURE and Support Vector Machines (SVM). (3) In the largest dataset consisting of 661 individuals, we are able to achieve 98.8% accuracy at top-36 markers chosen from 431 STRP markers, and 99.4% accuracy at top-48 markers chosen from the same set 431 markers. This is a rather favorable result in comparison with two former studies that achieve lower accuracy rates at higher number of markers.

View