Lih-Shyang CHEN Young-Jinn LAY Je-Bin HUANG Yan-De CHEN Ku-Yaw CHANG Shao-Jer CHEN
Although the Marching Cube (MC) algorithm is very popular for displaying images of voxel-based objects, its slow surface extraction process is usually considered to be one of its major disadvantages. It was pointed out that for the original MC algorithm, we can limit vertex calculations to once per vertex to speed up the surface extraction process, however, it did not mention how this process could be done efficiently. Neither was the reuse of these MC vertices looked into seriously in the literature. In this paper, we propose a “Group Marching Cube” (GMC) algorithm, to reduce the time needed for the vertex identification process, which is part of the surface extraction process. Since most of the triangle-vertices of an iso-surface are shared by many MC triangles, the vertex identification process can avoid the duplication of the vertices in the vertex array of the resultant triangle data. The MC algorithm is usually done through a hash table mechanism proposed in the literature and used by many software systems. Our proposed GMC algorithm considers a group of voxels simultaneously for the application of the MC algorithm to explore interesting features of the original MC algorithm that have not been discussed in the literature. Based on our experiments, for an object with more than 1 million vertices, the GMC algorithm is 3 to more than 10 times faster than the algorithm using a hash table. Another significant advantage of GMC is its compatibility with other algorithms that accelerate the MC algorithm. Together, the overall performance of the original MC algorithm is promoted even further.
Yasuyuki NOGAMI Kenta NEKADO Tetsumi TOYOTA Naoto HONGO Yoshitaka MORIKAWA
A lot of improvements and optimizations for the hardware implementation of SubBytes of Rijndael, in detail inversion in F28 have been reported. Instead of the Rijndael original F28, it is known that its isomorphic tower field F((22)2)2 has a more efficient inversion. Then, some conversion matrices are also needed for connecting these isomorphic binary fields. According to the previous works, it is said that the number of 1's in the conversion matrices is preferred to be small; however, they have not focused on the Hamming weights of the row vectors of the matrices. It plays an important role for the calculation architecture, in detail critical path delays. This paper shows the existence of efficient conversion matrices whose row vectors all have the Hamming weights less than or equal to 4. They are introduced as quite rare cases. Then, it is pointed out that such efficient conversion matrices can connect the Rijndael original F28 to some less efficient inversions in F((22)2)2 but not to the most efficient ones. In order to overcome these inconveniences, this paper next proposes a technique called mixed bases. For the towerings, most of previous works have used several kinds of bases such as polynomial and normal bases in mixture. Different from them, this paper proposes another mixture of bases that contributes to the reduction of the critical path delay of SubBytes. Then, it is shown that the proposed mixture contributes to the efficiencies of not only inversion in F((22)2)2 but also conversion matrices between the isomorphic fields F28 and F((22)2)2.
Railway operators adjust timetables, and accordingly reschedule rolling stock circulation and crew duties, when the train operations are disrupted by accidents or adverse weather conditions. This paper discusses the problem of rescheduling driver assignment to freight trains after timetable adjustment has been completed. We construct a network from the disrupted situation, and model the problem as an integer programming problem with set-covering constraints combined with set-partitioning constraints. The integer program is solved by column generation in which we reduce the column generation subproblem to a shortest path problem and such paths by utilizing data parallelism. Numerical experiments using a real timetable, driver scheduling plan and major disruption data in the highest-frequency freight train operation area in Japan reveal that our method provides a quality driver rescheduling solution within 25 seconds.
In (k,n) threshold scheme, Tompa and Woll considered a problem of cheaters who try to make another participant reconstruct an invalid secret. Later, some models of such cheating were formalized and lower bounds of the size of share were shown in the situation of fixing the maximum successful cheating probability to ε. Some efficient schemes in which size of share is equal to the lower bound were also proposed. Let |S| be the field size of the secret. Under the assumption that cheaters do not know the distributed secret, these sizes of share of previous schemes which can work for ε > 1/|S| are somewhat larger than the bound. In this paper, we show the bound for this case is really tight by constructing a new scheme. When distributing uniform secret, the bit length of share in the proposed scheme is only 1 bit longer than the known bound. Further, we show a tighter bound of the size of share in case of ε < 1/|S|.
Naoto YANAI Eikoh CHIDA Masahiro MAMBO
Verifying the signing order is sometimes very important in multisignature schemes. A multisignature scheme in which the signing order can be verified is called structured multisignature scheme and many such schemes have been proposed so far. However, there are not many structured multisignature schemes utilizing an algebraic structure of underlying algebraic operation. Ohmori, Chida, Shizuya and Nishizeki have proposed a structured multisignature scheme by utilizing a non-commutative ring homomorphism. Since their scheme does not fully reflect the structure of signers and its rigorous security analysis is not provided, we construct an improved structured multisignature scheme overcoming these problems by utilizing the non-commutative ring homomorphism in a different way and discuss its rigorous security against various attacks, including signer structure forgery, rogue key attack and attack-0 under the discrete logarithm assumption. As far as we know, the scheme in [30], which does not use non-commutative ring homomorphism, guarantees the most rigorous security but the number of signers is restricted in order to prevent attack-0. In contrast, our scheme overcomes attack-0 by virtue of a ring homomorphism and no restriction is imposed on the number of signers.
Toshiya NAKAKURA Yasuyuki SUMI Toyoaki NISHIDA
This paper proposes a system called Neary that detects conversational fields based on similarity of auditory situation among users. The similarity of auditory situation between each pair of the users is measured by the similarity of frequency property of sound captured by head-worn microphones of the individual users. Neary is implemented with a simple algorithm and runs on portable PCs. Experimental result shows Neary can successfully distinguish groups of conversations and track dynamic changes of them. This paper also presents two examples of Neary deployment to detect user contexts during experience sharing in touring at the zoo and attending an academic conference.
In ubiquitous sensor networks, extra energy savings can be achieved by selecting the filtering solution to counter the attack. This adaptive selection process employs a fuzzy rule-based system for selecting the best solution, as there is uncertainty in the reasoning processes as well as imprecision in the data. In order to maximize the performance of the fuzzy system the membership functions should be optimized. However, the efforts required to perform this optimization manually can be impractical for commonly used applications. This paper presents a GA-based membership function optimizer for fuzzy adaptive filtering (GAOFF) in ubiquitous sensor networks, in which the efficiency of the membership functions is measured based on simulation results and optimized by GA. The proposed optimization consists of three units; the first performs a simulation using a set of membership functions, the second evaluates the performance of the membership functions based on the simulation results, and the third constructs a population representing the membership functions by GA. The proposed method can optimize the membership functions automatically while utilizing minimal human expertise.
Naoki KANAYAMA Tadanori TERUYA Eiji OKAMOTO
In the present paper, we propose elliptic curve scalar multiplication methods on pairing-friendly elliptic curves. The proposed method is efficient on elliptic curves on which Atei pairing or optimal pairing is efficiently computed.
Hideyuki TOKUDA Jin NAKAZAWA Takuro YONEZAWA
Ubiquitous computing and communication are the key technology for achieving economic growth, sustainable development, safe and secure community towards a ubiquitous network society. Although the technology alone cannot solve the emerging problems, it is important to deploy services everywhere and reach real people with sensor enabled smart phones or devices. Using these devices and wireless sensor networks, we have been creating various types of ubiquitous services which support our everyday life. In this paper, we describe ubiquitous services based on a HOT-SPA model and discuss challenges in creating new ubiquitous services with smart enablers such as smart phones, wireless sensor nodes, social media, and cloud services. We first classify various types of ubiquitous service and introduce the HOT-SPA model which is aimed at modeling ubiquitous services. Several ubiquitous services, such as DIY smart object services, Twitthings, Airy Notes, and SensingCloud, are described. We then address the challenges in creating advanced ubiquitous services by enhancing coupling between a cyber and a physical space.
JeaHoon PARK GyoYong SOHN SangJae MOON
This paper presents a simplifying method of the two previous fault attacks to pairing and the Miller algorithms based on a practical fault assumption. Our experimental result shows that the assumption is feasible and easy to implement.
Takushi HASHIDA Yuuki ARAGA Makoto NAGATA
A diagnosis testbench of analog IP cores characterizes their coupling strengths against on-chip environmental disturbances, specifically with regard to substrate voltage variations. The testbench incorporates multi-tone digital noise generators and a precision waveform capture with multiple probing channels. A prototype test bench fabricated in a 90-nm CMOS technology demonstrates the diagnosis of substrate coupling up to 400 MHz with dynamic range of more than 60 dB. The coefficients of noise propagation as well as noise coupling on a silicon substrate are quantitatively derived for analog IP cores processed in a target technology, and further linked with noise awared EDA tooling for the successful adoption of such IP cores in SoC integration.
Most document clustering methods are a challenging issue for improving clustering performance. Document clustering based on semantic features is highly efficient. However, the method sometimes did not successfully cluster some documents, such as highly articulated documents. In order to improve the clustering success of complex documents using semantic features, this paper proposes a document clustering method that uses terms of the condensing document clusters and fuzzy association to efficiently cluster specific documents into meaningful topics based on the document set. The proposed method improves the quality of document clustering because it can extract documents from the perspective of the terms of the cluster topics using semantic features and synonyms, which can also better represent the inherent structure of the document in connection with the document cluster topics. The experimental results demonstrate that the proposed method can achieve better document clustering performance than other methods.
Hasan S.M. AL-KHAFFAF Abdullah Z. TALIB Rosalina ABDUL SALAM
Many factors, such as noise level in the original image and the noise-removal methods that clean the image prior to performing a vectorization, may play an important role in affecting the line detection of raster-to-vector conversion methods. In this paper, we propose an empirical performance evaluation methodology that is coupled with a robust statistical analysis method to study many factors that may affect the quality of line detection. Three factors are studied: noise level, noise-removal method, and the raster-to-vector conversion method. Eleven mechanical engineering drawings, three salt-and-pepper noise levels, six noise-removal methods, and three commercial vectorization methods were used in the experiment. The Vector Recovery Index (VRI) of the detected vectors was the criterion used for the quality of line detection. A repeated measure ANOVA analyzed the VRI scores. The statistical analysis shows that all the studied factors affected the quality of line detection. It also shows that two-way interactions between the studied factors affected line detection.
Yu TAKASE Osamu MUTA Yoshihiko AKAIWA
A major drawback in OFDM systems is that the transmit-signal exhibits a high Peak-to-Average Power Ratio (PAPR) which causes nonlinear distortion at the output of power amplifier. To achieve high efficiency in OFDM systems, it is important to suppress PAPR of the transmit signal. In IEEE802.16e (mobile WiMAX) based systems, it is desirable to employ a simple PAPR reduction method such as clipping & filtering (C&F) or peak windowing (PW). The purpose of this paper is to evaluate PAPR reduction performance of C&F and PW and compare them in an IEEE802.16e based OFDM system. In addition, we also show a repeated PW method which reduces PAPR by repeatedly applying a smooth window function to the transmit signal. Computer simulation results show that the repeated PW can achieve almost the same PAPR reduction performance as that of the repeated C&F with significantly lower computational complexity.
SangWoo LEE Seon-Ho SHIN MyungKeun YOON
A new network measurement primitive was recently proposed, known as long duration flows (LDF). LDF deserves special attention for network management and security monitoring. This kind of traffic appears periodically and persistently through a long period, but its total amount of traffic is not necessarily large. This feature makes detection difficult especially when the resources of detection system are limited or the detection should cover high-speed networks. In this paper, we propose a new lightweight data structure and streaming algorithm to detect such traffic.
Toshifusa SEKIZAWA Takashi TOYOSHIMA Koichi TAKAHASHI Kazuko TAKAHASHI
Probabilistic model checking is an emerging technology for analyzing systems which exhibit stochastic behaviors. The verification of a larger system using probabilistic model checking faces the same state explosion problem as ordinary model checking. Probabilistic symmetry reduction is a technique to tackle this problem. In this paper, we study probabilistic symmetry reduction for a system with a ring buffer which can describe various applications. A key of probabilistic symmetry reduction is identifying symmetry of states with respect to the structure of the target system. We introduce two functions; Shiftδ and Reverse to clarify such symmetry. Using these functions, we also present pseudo code to construct a quotient model. Then, we show two practical case studies; the one-dimensional Ising model and the Automatic Identification System (AIS). Behaviors of them were verified, but suffered from the state explosion problem. Through the case studies, we show that probabilistic symmetry reduction takes advantage of reducing the size of state space.
Tetsuya YAMAMOTO Kazuki TAKEDA KyeSan LEE Fumiyuki ADACHI
Recently, assuming ideal brick-wall transmit filtering, we proposed a frequency-domain block signal detection (FDBD) with maximum likelihood detection employing QR decomposition and M-algorithm (called QRM-MLD) for the reception of single-carrier (SC) signals transmitted over a frequency-selective fading channel. QR decomposition (QRD) is applied to a concatenation of the propagation channel and discrete Fourier transform (DFT). However, a large number of surviving paths is required in the M-algorithm to achieve sufficiently improved bit error rate (BER) performance. The introduction of filtering can achieve improved BER performance due to larger frequency diversity gain while keeping a lower peak-to-average power ratio (PAPR) than orthogonal frequency division multiplexing (OFDM). In this paper, we develop FDBD with QRM-MLD for filtered SC signal reception. QRD is applied to a concatenation of transmit filter, propagation channel, and DFT. We evaluate BER and throughput performances by computer simulation. From performance evaluation, we discuss how the filter roll-off factor affects the achievable BER and throughput performances and show that as the filter roll-off factor increases, the required number of surviving paths in the M-algorithm can be reduced.
Akira OTAKE Keita YAMAGUCHI Katsumasa KAMIYA Yasuteru SHIGETA Kenji SHIRAISHI
Due to the aggressive scaling of non-volatile memories, “charge-trap memories” such as MONOS-type memories become one of the most important targets. One of the merits of such MONOS-type memories is that they can trap charges inside atomic-scale defect sites in SiN layers. At the same time, however, charge traps with atomistic scale tend to induce additional large structural changes. Hydrogen has attracted a great attention as an important heteroatom in MONOS-type memories. We theoretically investigate the basic characteristics of hydrogen-defects in SiN layer in MONOS-type memories on the basis of the first-principles calculations. We find that SiN structures with a hydrogen impurity tend to reveal reversible structural change during program/erase operation.
Norimasa NAKASHIMA Mitsuo TATEIBA
This paper presents various types of iterative progressive numerical methods (IPNMs) for the computation of electromagnetic (EM) wave scattering from many objects and reports comparatively the performance of these methods. The original IPNM is similar to the Jacobi method which is one of the classical linear iterative solvers. Then the modified IPNMs are based on other classical solvers like the Gauss-Seidel (GS), the relaxed Jacobi, the successive overrelaxation (SOR), and the symmetric SOR (SSOR) methods. In the original and modified IPNMs, we repeatedly solve linear systems of equations by using a nonstationary iterative solver. An initial guess and a stopping criterion are discussed in order to realize a fast computation. We treat EM wave scattering from 27 perfectly electric conducting (PEC) spheres and evaluate the performance of the IPNMs. However, the SOR- and SSOR-type IPNMs are not subject to the above numerical test in this paper because an optimal relaxation parameter is not possible to determine in advance. The evaluation reveals that the IPNMs converge much faster than a standard BEM computation. The relaxed Jacobi-type IPNM is better than the other types in terms of the net computation time and the application range for the distance between objects.
Haruo HATANAKA Shimpei FUKUMOTO Haruhiko MURATA Hiroshi KANO Kunihiro CHIHARA
In this article, we present a new image-stabilization technology for still images based on blind deconvolution and introduce it to a consumer digital still camera. This technology consists of three features: (1)double-exposure-based PSF detection, (2)efficient image deblurring filter, and (3)edge-based ringing reduction. Without deteriorating the deblurring performance, the new technology allows us to reduce processing time and ringing artifacts, both of which are common problems in image deconvolution.