In this paper, we apply a mutation operation based on a multivariate Cauchy distribution to fast evolutionary programming and analyze its effect in terms of various function optimizations. The conventional fast evolutionary programming in-cooperates the univariate Cauchy mutation in order to overcome the slow convergence rate of the canonical Gaussian mutation. For a mutation of n variables, while the conventional method utilizes n independent random variables from a univariate Cauchy distribution, the proposed method adopts n mutually dependent random variables that satisfy a multivariate Cauchy distribution. The multivariate Cauchy distribution naturally has higher probabilities of generating random variables in inter-variable regions than the univariate Cauchy distribution due to the mutual dependence among variables. This implies that the multivariate Cauchy random variable enhances the search capability especially for a large number of correlated variables, and, as a result, is more appropriate for optimization schemes characterized by interdependence among variables. In this sense, the proposed mutation possesses the advantage of both the univariate Cauchy and Gaussian mutations. The proposed mutation is tested against various types of real-valued function optimizations. We empirically find that the proposed mutation outperformed the conventional Cauchy and Gaussian mutations in the optimization of functions having correlations among variables, whereas the conventional mutations showed better performance in functions of uncorrelated variables.
Keiichi MIZUTANI Zhou LAN Hiroshi HARADA
Demand for wireless communication is increasing significantly, but the frequency resources available for wireless communication are quite limited. Currently, various countries are prompting the use of TV white spaces (TVWS). IEEE 802.11 Working Group (WG) has started a Task Group (TG), namely IEEE 802.11af, to develop an international standard for Wireless local Area Networks (WLANs) in TVWS. In order to increase maximum throughput, a channel aggregation mechanism is introduced in the draft standard. In Japan, ISDB-T based area-one-segment broadcasting system (Area-1seg) which is a digital TV broadcast service in limited areas has been permitted to offer actual TVWS services since April 2012. The operation of the IEEE 802.11af system shall not jeopardize the Area-1seg system due to the common operating frequency band. If the Area-1seg partially overlaps with the IEEE 802.11af in some frequency, the IEEE 802.11af cannot use the channel aggregation mechanism due to a lack of channels. As a result, the throughput of the IEEE 802.11af deteriorates. In this paper, the physical layer of IEEE 802.11af D4.0 is introduced briefly, and a partial subcarrier system for IEEE 802.11af is proposed to efficiently use the TVWS spectrum. The IEEE 802.11af co-exist with the Area-1seg by using null subcarriers. Computer simulation shows up to around 70% throughput gain is achieved with the proposed mechanism.
Hongliang XU Fei ZHOU Fan YANG Qingmin LIAO
We propose a parameterized multisurface fitting method for multi-frame super-resolution (SR) processing. A parameter assumed for the unknown high-resolution (HR) pixel is used for multisurface fitting. Each surface fitted at each low-resolution (LR) pixel is an expression of the parameter. Final SR result is obtained by fusing the sampling values from these surfaces in the maximum a posteriori fashion. Experimental results demonstrate the superiority of the proposed method.
Junjun GUO Jianjun MU Xiaopeng JIAO Guiping LI
In this letter, we present a new scheme to find small fundamental instantons (SFIs) of regular low-density parity-check (LDPC) codes for the linear programming (LP) decoding over the binary symmetric channel (BSC). Based on the fact that each instanton-induced graph (IIG) contains at least one short cycle, we determine potential instantons by constructing possible IIGs which contain short cycles and additional paths connected to the cycles. Then we identify actual instantons from potential ones under the LP decoding. Simulation results on some typical LDPC codes show that our scheme is effective, and more instantons can be obtained by the proposed scheme when compared with the existing instanton search method.
The Discrete Memory Machine (DMM) and the Unified Memory Machine (UMM) are theoretical parallel computing models that capture the essence of the shared memory and the global memory of GPUs. It is assumed that warps (or groups of threads) on the DMM and the UMM work synchronously in a round-robin manner. However, warps work asynchronously in real GPUs, in the sense that they are randomly (or arbitrarily) dispatched for execution. The first contribution of this paper is to introduce asynchronous versions of these models in which warps are arbitrarily dispatched. In addition, we assume that threads can execute the “syncthreads” instruction for barrier synchronization. Since the barrier synchronization operation may be costly, we should evaluate and minimize the number of barrier synchronization operations executed by parallel algorithms. The second contribution of this paper is to show a parallel algorithm to the sum of n numbers in optimal computing time and few barrier synchronization steps. Our parallel algorithm computes the sum of n numbers in O(n/w+llog n) time units and O(log l/log w+log log w) barrier synchronization steps using wl threads on the asynchronous UMM with width w and latency l. Since the computation of the sum takes at least Ω(n/w+llog n) time units, this algorithm is time optimal. Finally, we show that the prefix-sums of n numbers can also be computed in O(n/w+llog n) time units and O(log l/log w+log log w) barrier synchronization steps using wl threads.
Methods for in-network joins of sensing data with tuples, in partitioned condition tables stored in sensor nodes, have been studied for efficient event detection. A recently proposed method performs the join operation after distributing the tuples of a condition table evenly among homogeneous sensor nodes with the same storage capacity. In the method, the condition table is horizontally partitioned, and each partition is allocated to the corresponding node, along the path from the highest level to the leaf level. If the path length is larger than the number of partitions, the second round distribution of the partitions resumes from the node at the next level, and so on. Thus, the last node at each round can be assigned the partition that is smaller than the others, which would otherwise cause wasted internal fragmentation. Further, little research has been conducted on methods for the cases of heterogeneous sensor nodes with different available spaces, as well as the vertical partitioning of condition table. In this study, we propose a method of partitioning a condition table that utilizes the internal fragmentation, by treating the tuples of a condition table as a circular list. The proposed method is applicable to the case in which nodes have different available spaces. Furthermore, a new method for vertically partitioning a condition table is suggested. Experiments verify the reduction in the data transmission amount offered by the proposed methods, as compared to existing methods.
Masaki KAWABATA Takao NISHIZEKI
Let G be a graph with a single source w, assigned a positive integer called the supply. Every vertex other than w is a sink, assigned a nonnegative integer called the demand. Every edge is assigned a positive integer called the capacity. Then a spanning tree T of G is called a spanning distribution tree if the capacity constraint holds when, for every sink v, an amount of flow, equal to the demand of v, is sent from w to v along the path in T between them. The spanning distribution tree problem asks whether a given graph has a spanning distribution tree or not. In the paper, we first observe that the problem is NP-complete even for series-parallel graphs, and then give a pseudo-polynomial time algorithm to solve the problem for a given series-parallel graph G. The computation time is bounded by a polynomial in n and D, where n is the number of vertices in G and D is the sum of all demands in G.
Ying WANG Weidong ZHANG Peilong LI Ping ZHANG
This paper investigates interference coordination for 3-dimension (3D) antenna array systems in multicell multiple-input multiple-output (MIMO) and orthogonal frequency division multiple-access (OFDMA) wireless networks. Cell-center user and cell-edge user specific downtilts are accordingly partitioned through dynamic vertical beamforming in the 3D MIMO-OFDM communication systems. Taking these user specific downtilts into consideration, the objective of our proposed interference coordination scheme is to maximize both the cell-edge users' and cell-center users' throughput, subject to per base-station (BS) power, cell-center user and cell-edge user specific downtilt constraints. Here, two coordination techniques, consisting of the fractional frequency reuse (FFR) scheme and partial joint process (JP) coordinated multiple point (COMP) transmission mode, are introduced in this paper. To solve the interference coordination problem, two resource block (RB) partitioning schemes are proposed for the above-mentioned coordination techniques accordingly. Based on such RB partitioning, JP CoMP-based dual decomposition method (JC-DDM) and FFR-based dual decomposition method (FDDM) are proposed, where RB assignment, power allocation (RAPA) and downtilts adjustment are jointly optimized. To simplify the computation complexity, a suboptimal algorithm (SOA) is presented to decouple the optimization problem into three subproblems by using FFR scheme. Simulation results show that all of our proposed algorithms outperform the interference coordination scheme with fixed downtilts. JC-DDM and FDDM find the local optimal throughput with different transmission techniques, while SOA iteratively optimize the downtilts and RAPA which shows close-to-optimal performance with much lower computation complexity.
Li ZENG Xiongwei ZHANG Liang CHEN Weiwei YANG
Presented is a new measuring and reconstruction framework of Compressed Sensing (CS), aiming at reducing the measurements required to ensure faithful reconstruction. A sparse vector is segmented into sparser vectors. These new ones are then randomly sensed. For recovery, we reconstruct these vectors individually and assemble them to obtain the original signal. We show that the proposed scheme, referred to as SegOMP, yields higher probability of exact recovery in theory. It is finished with much smaller number of measurements to achieve a same reconstruction quality when compared to the canonical greedy algorithms. Extensive experiments verify the validity of the SegOMP and demonstrate its potentials.
Takahiro ITO Daisuke ANZAI Jianqing WANG
Tracking capsule endoscope location is one of the promising applications offered by implant body area networks (BANs). When tracking the capsule endoscope location, i.e., continuously localize it, it is effective to take the weighted sum of its past locations to its present location, in other words, to low-pass filter its past locations. Furthermore, creating an exact mathematical model of location transition will improve tracking performance. Therefore, in this paper, we investigate two tracking methods with received signal strength indicator (RSSI)-based localization in order to solve the capsule endoscope location tracking problem. One of the two tracking methods is finite impulse response (FIR) filter-based tracking, which tracks the capsule endoscope location by averaging its past locations. The other one is particle filter-based tracking in order to deal with a nonlinear transition model on the capsule endoscope. However, the particle filter requires that the particle weight is calculated according to its condition (namely, its likelihood value), while the transition model on capsule endoscope location has some model parameters which cannot be estimated from the received wireless signal. Therefore, for the purpose of applying the particle filter to capsule endoscope tracking, this paper makes some modifications in the resampling step of the particle filter algorithm. Our computer simulation results demonstrate that the two tracking methods can improve the performance as compared with the conventional maximum likelihood (ML) localization. Furthermore, we confirm that the particle filter-based tracking outperforms the conventional FIR filter-based tracking by taking the realistic capsule endoscope transition model into consideration.
Jingjie YAN Wenming ZHENG Minhai XIN Jingwei YAN
In this letter, we research the method of using face and gesture image sequences to deal with the video-based bimodal emotion recognition problem, in which both Harris plus cuboids spatio-temporal feature (HST) and sparse canonical correlation analysis (SCCA) fusion method are applied to this end. To efficaciously pick up the spatio-temporal features, we adopt the Harris 3D feature detector proposed by Laptev and Lindeberg to find the points from both face and gesture videos, and then apply the cuboids feature descriptor to extract the facial expression and gesture emotion features [1],[2]. To further extract the common emotion features from both facial expression feature set and gesture feature set, the SCCA method is applied and the extracted emotion features are used for the biomodal emotion classification, where the K-nearest neighbor classifier and the SVM classifier are respectively used for this purpose. We test this method on the biomodal face and body gesture (FABO) database and the experimental results demonstrate the better recognition accuracy compared with other methods.
Yuan TAO Yangdong DENG Shuai MU Zhenzhong ZHANG Mingfa ZHU Limin XIAO Li RUAN
The sparse matrix operation, y ← y+AtAx, where A is a sparse matrix and x and y are dense vectors, is a widely used computing pattern in High Performance Computing (HPC) applications. The pattern poses challenge to efficient solutions because both a matrix and its transposed version are involved. An efficient sparse matrix format, Compressed Sparse Blocks (CSB), has been proposed to provide nearly the same performance for both Ax and Atx. We develop a multithreaded implementation for the CSB format and apply it to solve y ← y+AtAx. Experiments show that our technique outperforms the Compressed Sparse Row (CSR) based solution in POSKI by up to 2.5 fold on over 70% of benchmarking matrices.
Seiichiro NAITO Ryo SHOHARA Makoto KATSUMURA
We investigated the filling-in (FI) of line segments at the Artificial Scotoma (AS) created by Motion Induced Blindness (MIB). The FI sensations for line segments were fairly similar to that of the natural Blind Spots (BS), though the geometrical configurations and luminance conditions on stimuli were substantially limited. The 2.5 degree thick black line segment was filled in after 6.5 degree diameter disk was disappeared by MIB. The thin lines, however, didn't fill in. We also obtained the pro and con evidences for the historical FI theory. The disappearance of the uniformly filled circles followed the general FI theory. On the other hand we found it controversial with the FI accounts that the concentric circles disappeared altogether. In the conventional MIB, the target figure disappears and re-appears in a stochastic and spontaneous manner. We devised the novel inducer for MIB so as to yield the synchronization of dis- and re-appearance of the targets with the motion of the inducers. The two stationary disks disappeared in an alternating manner by MIB effects. The subjects observed the background color after disappearance. The alternating disappearance of the two white disks provided the observers with the sensation of the Apparent Motion (AM) of the single disk which would be perceived as jumping up and down. The significant question was raised; did MIB precede AM? When the AM sensation was the case, the percept was not the disappearance but the motion of the single entity. The sensation of the motion provided the almost equivalent conditions to the motion stimuli over the natural BS. We summarized the issue whether the FI at AS by MIB was intrinsically equivalent to the phenomena on BS. The hierarchy of underlying mechanisms of AM and MIB was yet unknown, however, we rather proposed yet another high level motion perception mechanism.
Shenchuan LIU Wannida SAE-TANG Masaaki FUJIYOSHI Hitoshi KIYA
This letter proposes an efficient compression scheme for the copyright- and privacy-protected image trading system. The proposed scheme multiplies pseudo random signs to amplitude components of discrete cosine transformed coefficients before the inverse transformation is applied. The proposed scheme efficiently compresses amplitude-only image which is the inversely transformed amplitude components, and the scheme simultaneously improves the compression efficiency of phase-only image which is the inversely transformed phase components, in comparison with the conventional systems.
Hirokatsu KATAOKA Kimimasa TAMURA Kenji IWATA Yutaka SATOH Yasuhiro MATSUI Yoshimitsu AOKI
The percentage of pedestrian deaths in traffic accidents is on the rise in Japan. In recent years, there have been calls for measures to be introduced to protect vulnerable road users such as pedestrians and cyclists. In this study, a method to detect and track pedestrians using an in-vehicle camera is presented. We improve the technology of detecting pedestrians by using the highly accurate images obtained with a monocular camera. In the detection step, we employ ECoHOG as the feature descriptor; it accumulates the integrated gradient intensities. In the tracking step, we apply an effective motion model using optical flow and the proposed feature descriptor ECoHOG in a tracking-by-detection framework. These techniques were verified using images captured on real roads.
Arthur D.D. LIMA Carlos A. BARROS Luiz Felipe Q. SILVEIRA Samuel XAVIER-DE-SOUZA Carlos A. VALDERRAMA
The evolution of wireless communication systems leads to Dynamic Spectrum Allocation for Cognitive Radio, which requires reliable spectrum sensing techniques. Among the spectrum sensing methods proposed in the literature, those that exploit cyclostationary characteristics of radio signals are particularly suitable for communication environments with low signal-to-noise ratios, or with non-stationary noise. However, such methods have high computational complexity that directly raises the power consumption of devices which often have very stringent low-power requirements. We propose a strategy for cyclostationary spectrum sensing with reduced energy consumption. This strategy is based on the principle that p processors working at slower frequencies consume less power than a single processor for the same execution time. We devise a strict relation between the energy savings and common parallel system metrics. The results of simulations show that our strategy promises very significant savings in actual devices.
Lane detection plays an important role in Driver Assistance Systems and Autonomous Vehicle System. In this paper, we propose a parallel-snake model combined with balloon force for lane detection. Parallel-snake is defined as two open active contours with parallel constrain. The lane boundaries on the left and right sides are assumed as parallel curves, parallel-snake is deformed to estimate these two boundaries. As lane regions between left and right boundaries usually have low gradient, snake will lose external force on these regions. Furthermore, inspired by balloon active contour model, the balloon force is introduced into parallel-snake to expand two parallel curves from center of road to the left and right lane boundaries. Different from closed active contour, stretching force is adopted to prevent the head and tail of snake from converging together. The experimental results on three different datasets show that parallel-snake model can work well on images with shadows and handle the lane with broken boundaries as the parallel property.
Miao ZHANG Jiro HIROKAWA Makoto ANDO
As a promising lamination-loss-free fabrication technique, diffusion bonding of etched thin metal plates is used to realize double-layer waveguide slot antennas. Alternating-phase feed is adopted in this paper to reduce the number of laminated plates to simplify fabrication as well as to reduce cost. A 20 × 20-element double-layer waveguide slot antenna with a bottom partially-corporate feed circuit is designed for 39GHz band operation as an example. The adjacent radiating waveguides as well as the 2 × 2 sub-arrays fed in an alternating-phase manner eliminate the need for complete electrical contact in the top layer. However, the feed circuit in the bottom layer has to be completely diffusion-bonded. These two layers are simply assembled by screws. An antenna laminated by only diffusion bonding is also fabricated and evaluated for comparison. The comparison proved that the simply fabricated antenna is comparable in performance to the fully diffusion-bonded one.
Kazunori URUMA Katsumi KONISHI Tomohiro TAKAHASHI Toshihiro FURUKAWA
This letter deals with a sparse signal recovery problem and proposes a new algorithm based on the iterative reweighted least squares (IRLS) algorithm. We assume that the non-zero values of a sparse signal is always greater than a given constant and modify the IRLS algorithm to satisfy this assumption. Numerical results show that the proposed algorithm recovers a sparse vector efficiently.
Chia-Shao HUNG Shanq-Jang RUAN
Image binarization refers to convert gray-level images into binary ones, and many binarization algorithms have been developed. The related algorithms can be classified as either high quality computation or high speed performance. This letter presents an algorithm that ensures both benefits at the same time. The proposed algorithm intelligently segments input images into several sub-image, after which the sub-image binarization is performed independently. Experimental results reveal that our algorithm provides the appropriate quality with the medium speed.