Takashi HISAMORI Toru ARIKAWA Gosuke OHASHI
In previous studies, the retrieval accuracy of large image databases has been improved as a result of reducing the semantic gap by combining the input sketch with relevance feedback. A further improvement of retrieval accuracy is expected by combining each stroke, and its order, of the input sketch with the relevance feedback. However, this leaves as a problem the fact that the effect of the relevance feedback substantially depends on the stroke order in the input sketch. Although it is theoretically possible to consider all the possible stroke orders, that would cause a realistic problem of creating an enormous amount of data. Consequently, the technique introduced in this paper intends to improve retrieval efficiency by effectively using the relevance feedback by means of conducting data mining of the sketch considering the similarity in the order of strokes. To ascertain the effectiveness of this technique, a retrieval experiment was conducted using 20,000 images of a collection, the Corel Photo Gallery, and the experiment was able to confirm an improvement in the retrieval efficiency.
Sopon PHUMEECHANYA Charnchai PLUEMPITIWIRIYAWEJ Saowapak THONGVIGITMANEE
In this paper, we propose a novel active contour method for image segmentation using a local regional information on extendable search line. We call it the LRES active contour. Our active contour uses the intensity values along a set of search lines that are perpendicular to the contour front. These search lines are used to inform the contour front toward which direction to move in order to find the object's boundary. Unlike other methods, none of these search lines have a predetermined length. Instead, their length increases gradually until a boundary of the object is found. We compare the performance of our LRES active contour to other existing active contours, both edge-based and region-based. The results show that our method provides more desirable segmentation outcomes, particularly on some images where other methods may fail. Not only is our method robust to noise and able to reach into a deep concave shape, it also has a large capture range and performs well in segmenting heterogeneous textured objects.
Md. Rakib HASSAN Md. Monirul ISLAM Kazuyuki MURASE
Ant Colony Optimization (ACO) algorithms are a new branch of swarm intelligence. They have been applied to solve different combinatorial optimization problems successfully. Their performance is very promising when they solve small problem instances. However, the algorithms' time complexity increase and solution quality decrease for large problem instances. So, it is crucial to reduce the time requirement and at the same time to increase the solution quality for solving large combinatorial optimization problems by the ACO algorithms. This paper introduces a Local Search based ACO algorithm (LSACO), a new algorithm to solve large combinatorial optimization problems. The basis of LSACO is to apply an adaptive local search method to improve the solution quality. This local search automatically determines the number of edges to exchange during the execution of the algorithm. LSACO also applies pheromone updating rule and constructs solutions in a new way so as to decrease the convergence time. The performance of LSACO has been evaluated on a number of benchmark combinatorial optimization problems and results are compared with several existing ACO algorithms. Experimental results show that LSACO is able to produce good quality solutions with a higher rate of convergence for most of the problems.
Wen Tao ZHU Robert H. DENG Jianying ZHOU Feng BAO
The access privileges in distributed systems can be effectively organized as a partial-order hierarchy that consists of distinct security classes, and the access rights are often designated with certain temporal restrictions. The time-bound hierarchical key assignment problem is to assign distinct cryptographic keys to distinct security classes according to their privileges so that users from a higher class can use their class key to derive the keys of lower classes, and these keys are time-variant with respect to sequentially allocated temporal units called time slots. In this paper, we present the involved principle, survey the state of the art, and particularly, look into two representative approaches to time-bound hierarchical key assignment for in-depth case studies.
Ki-Ho LEE Hyun-Ho CHOI Dong-Ho CHO
Hierarchical constellations offer a different property of robustness to the multiple bits that construct a symbol according to channel errors. We apply the characteristics of hierarchical constellations to a multi-user cellular system that has limited modulation levels, in order to improve cell capacity. We propose an adaptive resource allocation scheme based on the hierarchical constellation in which a symbol is shared by multiple users and each bit in a symbol is allocated adaptively according to the channel condition of each user. The numerical results show that the proposed resource allocation scheme provides mobile users with higher modulation levels so that the cell capacity is improved.
An improved bidirectional search algorithm for computing the weight spectrum of convolutional codes is presented. This algorithm does not employ the column distance function of a code which plays an important role in the original bidirectional search algorithm. We show the proposed algorithm can reduce computaion time for obtaining the weigth spectrum of convolutional codes significantly compared with that of the bidirectional search algorithm.
Keita IMADA Katsuhiko NAKAMURA
This paper describes recent improvements to Synapse system for incremental learning of general context-free grammars (CFGs) and definite clause grammars (DCGs) from positive and negative sample strings. An important feature of our approach is incremental learning, which is realized by a rule generation mechanism called "bridging" based on bottom-up parsing for positive samples and the search for rule sets. The sizes of rule sets and the computation time depend on the search strategies. In addition to the global search for synthesizing minimal rule sets and serial search, another method for synthesizing semi-optimum rule sets, we incorporate beam search to the system for synthesizing semi-minimal rule sets. The paper shows several experimental results on learning CFGs and DCGs, and we analyze the sizes of rule sets and the computation time.
Hyuntae PARK Hyunjin KIM Hong-Sik KIM Sungho KANG
This letter proposes a fast IP address lookup algorithm based on search space reduction. Prefixes are classified into three types according to the nesting relationship and a large forwarding table is partitioned into multiple small trees. As a result, the search space is reduced. The results of analyses and experiments show that the proposed method offers higher lookup and updating speeds along with reduced memory requirements.
Shigeto TAJIMA Nobuo FUNABIKI Teruo HIGASHINO
Wireless mesh networks have been extensively studied as expandable, flexible, and inexpensive access networks to the Internet. This paper focuses on one composed of multiple access points (APs) connected through multihop wireless communications mainly by the wireless distribution system (WDS). For scalability, the proper partition of APs into multiple WDS clusters is essential, because the number of APs in one cluster is limited due to the increasing radio interference and control packets. In this paper, we formulate this WDS clustering problem and prove the NP-completeness of its decision version through reduction from a known NP-complete problem. Then, we propose its heuristic algorithm, using a greedy method and a variable depth search method, to satisfy the complex constraints while optimizing the cost function. We verify the effectiveness of our algorithm through extensive simulations, where the results confirm its superiority to the existing algorithm in terms of throughput.
Shinpei HAYASHI Yasuyuki TSUDA Motoshi SAEKI
This paper proposes a technique for detecting the occurrences of refactoring from source code revisions. In a real software development process, a refactoring operation may sometimes be performed together with other modifications at the same revision. This means that detecting refactorings from the differences between two versions stored in a software version archive is not usually an easy process. In order to detect these impure refactorings, we model the detection within a graph search. Our technique considers a version of a program as a state and a refactoring as a transition between two states. It then searches for the path that approaches from the initial to the final state. To improve the efficiency of the search, we use the source code differences between the current and the final state for choosing the candidates of refactoring to be applied next and estimating the heuristic distance to the final state. Through case studies, we show that our approach is feasible to detect combinations of refactorings.
Jian WENG Min-Rong CHEN Kefei CHEN Robert H. DENG
Hierarchical Identity-Based Encryption (HIBE) is a generalization of identity-based encryption that mirrors an organizational hierarchy, and allows the root Private Key Generator (PKG) to distribute the workload of key generations to lower-level PKGs. In Indocrypt'08, Ren and Gu proposed a new HIBE scheme, and claimed that their scheme is fully chosen-ciphertext secure in the standard model. However, by giving a concrete attack, we show that Ren-Gu's HIBE is even not chosen-plaintext secure.
Sangho YOON Hanho LEE Kihoon LEE
This paper presents a high-speed Forward Error Correction (FEC) architecture based on concatenated Bose-Chaudhuri-Hocquenghem (BCH) for 100-Gb/s optical communication systems. The concatenated BCH code consists of BCH(3860, 3824) and BCH(2040, 1930), which provides 7.98 dB net coding gain at 10-12 corrected bit error rate. The proposed BCH decoder features a low-complexity key equation solver using an error-locator computation RiBM (ECRiBM) algorithm and its architecture. The proposed concatenated BCH-based Super-FEC architecture has been implemented in 90-nm CMOS standard cell technology with a supply voltage of 1.1 V. The implementation results show that the proposed architecture can operate at a clock frequency of 400 MHz and has a throughput of 102.4-Gb/s for 90-nm CMOS technology.
Shuang ZHAO Wenqing LU Xiaofang ZHOU Dian ZHOU Gerald E. SOBELMAN
MIMO-OFDM systems aim to improve transmission quality and/or throughput but require significant signal processing capability and flexibility at reasonable cost. This paper proposes a reconfigurable architecture and associated algorithm optimizations for these types of systems based on the IEEE 802.11n and IEEE 802.16e standards. In particular, we describe the implementation of two key computations onto this architecture, namely Fast Fourier Transform (FFT) and Space-Time Block Decoding (STBD). The design is post-layout using a UMC 0.18 micron technology at a clock rate of 100 MHz. Performance comparisons with other optimization methods and hardware implementations are given.
Ithipan METHASATE Thanaruk THEERAMUNKONG
Finding a kernel mapping function for support vector machines (SVMs) is a key step towards construction of a high-performanced SVM-based classifier. While some recent methods exploited an evolutional approach to construct a suitable multifunction kernel, most of them searched randomly and diversely. In this paper, the concept of a family of identical-structured kernel trees is proposed to enable exploration of structure space using genetic programming whereas to pursue investigation of parameter space on a certain tree using evolution strategy. To control balance between structure and parameter search towards an optimal kernel, simulated annealing is introduced. By experiments on a number of benchmark datasets in the UCI and text classification collection, the proposed method is shown to be able to find a better optimal solution than other search methods, including grid search and gradient search.
Set-partitioning in hierarchical trees (SPIHT) is one of the well-known image compression schemes. SPIHT offers an agreeable compression ratio and produces an embedded bit-stream for progressive transmission. However, the major disadvantage of SPIHT is its large memory requirement. In this paper, we propose a memory efficient SPIHT image coder and its parallel implantation. The memory requirement is reduced without sacrificing image quality. All bit-planes are concurrently encoded in order to speed up the entire coding flow. The result shows that the proposed algorithm is roughly 6 times faster than the original SPIHT. For a 512512 image, the memory requirement is reduced from 5.83 Mb to 491 Kb. The proposed algorithm is also realized on FPGA. With pipeline design, the circuit can run at 110 MHz, which can encode a 512512 image in 1.438 ms. Thus, the circuit achieves very high throughput, 182 MPixels/sec, and can be applied to high performance image compression applications.
This paper introduces a packet forwarding scheme based on interworking architecture that can provide quite a good QoS by minimizing processing delay which is the major part of the timeliness factor in New Generation IP-based networks. Based on path and resource reservation mechanism, the POSIA makes routers on the packet forwarding path synchronize with each other and then forward packets. We have shown that the POSIA outperforms the existing packet forwarding schemes like IntServ, DiffServ and MPLS through computer simulations using OPNET.
To increase both the capacity and the processing speed for input-queued (IQ) switches, we proposed a fair scalable scheduling architecture (FSSA). By employing FSSA comprised of several cascaded sub-schedulers, a large-scale high performance switches or routers can be realized without the capacity limitation of monolithic device. In this paper, we present a fair scheduling algorithm named FSSA_DI based on an improved FSSA where a distributed iteration scheme is employed, the scheduler performance can be improved and the processing time can be reduced as well. Simulation results show that FSSA_DI achieves better performance on average delay and throughput under heavy loads compared to other existing algorithms. Moreover, a practical 64 64 FSSA using FSSA_DI algorithm is implemented by four Xilinx Vertex-4 FPGAs. Measurement results show that the data rates of our solution can be up to 800 Mbps and the tradeoff between performance and hardware complexity has been solved peacefully.
Fast Fourier Transform (FFT) is an important algorithm in many digital signal processing applications, and it often requires parallel implementation for high throughput. In this paper, we first present the SmartCell coarse-grained reconfigurable architecture targeted for stream processing. A SmartCell prototype integrates 64 processing elements, configurable interconnections, and dedicated instruction and data memories into a single chip, which is able to provide high performance parallel processing while maintaining post-fabrication flexibility. Subsequently, we present a parallel FFT architecture targeted for multi-core platforms computing systems. This algorithm provides an optimized data flow pattern that reduces both communication and configuration overheads. The proposed parallel FFT algorithm is then mapped onto the SmartCell prototype device. Results show that the parallel FFT implementation on SmartCell is about 14.9 and 2.7 times faster than network-on-chip (NoC) and MorphoSys implementations, respectively. SmartCell also achieves the energy efficiency gains of 2.1 and 28.9 when compared with FPGA and DSP implementations.
Marcus BRUNNER Henrik ABRAMOWICZ Norbert NIEBERT Luis M. CORREIA
In this paper, we describe several approaches to address the challenges of the network of the future. Our main hypothesis is that the Future Internet must be designed for the environment of applications and transport media of the 21st century, vastly different from the initial Internet's life space. One major requirement is the inherent support for mobile and wireless usage. A Future Internet should allow for the fast creation of diverse network designs and paradigms and must also support their co-existence at run-time. We detail the technical and business scenarios that lead the development in the EU FP7 4WARD project towards a framework for the Future Internet.
Network virtualization has become a common research topic that many researchers consider a basis for defining a new generation network architectures. In this paper, we attempt to clarify the concept of network virtualization with its brief history, to introduce the benefit of network virtualization for the future network, to posit our strong belief in that the future network should adopt a form of a meta-architecture that accommodates multiple competing multiple architectures, and to identify challenges to achieving this architecture.