In this paper, we propose a novel decomposition method to segment multiple object regions simultaneously in cluttered videos. This method formulates object regions segmentation as a labeling problem in which we assign object IDs to the superpixels in a sequence of video frames so that the unary color matching cost is low, the assignment induces compact segments, and the superpixel labeling is consistent through time. Multi-object segmentation in a video is a combinatorial problem. We propose a binary linear formulation. Since the integer linear programming is hard to solve directly, we relax it and further decompose the relaxation into a sequence of much simpler max-flow problems. The proposed method is guaranteed to converge in a finite number of steps to the global optimum of the relaxation. It also has a high chance to obtain all integer solution and therefore achieves the global optimum. The rounding of the relaxation result gives an N-approximation solution, where N is the number of objects. Comparing to directly solving the integer program, the novel decomposition method speeds up the computation by orders of magnitude. Our experiments show that the proposed method is robust against object pose variation, occlusion and is more accurate than the competing methods while at the same time maintains the efficiency.
Xueqi ZHANG Wei WU Baoyun WANG Jian LIU
This letter investigates transmit optimization in multi-user multi-input multi-output (MIMO) wiretap channels. In particular, we address the transmit covariance optimization for an artificial-noise (AN)-aided secrecy rate maximization (SRM) when subject to individual harvested energy and average transmit power. Owing to the inefficiency of the conventional interior-point solvers in handling our formulated SRM problem, a custom-designed algorithm based on penalty function (PF) and projected gradient (PG) is proposed, which results in semi-closed form solutions. The proposed algorithm achieves about two orders of magnitude reduction of running time with nearly the same performance comparing to the existing interior-point solvers. In addition, the proposed algorithm can be extended to other power-limited transmit design problems. Simulation results demonstrate the excellent performance and high efficiency of the algorithm.
Ahmed AWAD Atsushi TAKAHASHI Chikaaki KODAMA
With being pushed into sub-16nm regime, advanced technology nodes printing in optical micro-lithography relies heavily on aggressive Optical Proximity Correction (OPC) in the foreseeable future. Although acceptable pattern fidelity is utilized under process variations, mask design time and mask manufacturability form crucial parameters whose tackling in the OPC recipe is highly demanded by the industry. In this paper, we propose an intensity based OPC algorithm to find a highly manufacturable mask solution for a target pattern with acceptable pattern fidelity under process variations within a short computation time. This is achieved through utilizing a fast intensity estimation model in which intensity is numerically correlated with local mask density and kernel type to estimate the intensity in a short time and with acceptable estimation accuracy. This estimated intensity is used to guide feature shifting, alignment, and concatenation following linearly interpolated variational intensity error model to achieve high mask manufacturability with preserving acceptable pattern fidelity under process variations. Experimental results show the effectiveness of our proposed algorithm on the public benchmarks.
Bei ZHAO Chen CHENG Zhenguo MA Feng YU
Cross correlation is a general way to estimate time delay of arrival (TDOA), with a computational complexity of O(n log n) using fast Fourier transform. However, since only one spike is required for time delay estimation, complexity can be further reduced. Guided by Chinese Remainder Theorem (CRT), this paper presents a new approach called Co-prime Aliased Sparse FFT (CASFFT) in O(n1-1/d log n) multiplications and O(mn) additions, where m is smooth factor and d is stage number. By adjusting these parameters, it can achieve a balance between runtime and noise robustness. Furthermore, it has clear advantage in parallelism and runtime for a large range of signal-to-noise ratio (SNR) conditions. The accuracy and feasibility of this algorithm is analyzed in theory and verified by experiment.
Let G be a graph and K be a set of target vertices of G. Assume that all vertices of G, except the vertices in K, may fail with given probabilities. The K-terminal reliability of G is the probability that all vertices in K are mutually connected. This reliability problem is known to be #P-complete for general graphs. This work develops the first polynomial-time algorithm for computing the K-terminal reliability of circular-arc graphs.
Yuki KOIZUMI Suhwuk KIM Yuki URATA Toru HASEGAWA
This paper proposes an NDN-based message delivery protocol over a cellular network in disasters. Collaborative communication among cellular devices is integrated into the protocol so that power consumed by battery-operated base stations (BSs) is reduced when a blackout occurs. A key idea is to reduce consumed radio resources by making cellular devices of which radio propagation quality are better forward messages of neighboring devices. The radio resource reduction contributes to reducing power consumed by a battery-operated BS. We empirically and analytically evaluate how the proposed message delivery protocol reduces the power consumption of a BS assuming a densely populated shelter.
In the field of computer science, the network reliability problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph G, the network failure probability is the probability that edge failures (i.e., edge erasures) make G unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erd
Tomohiro NAKAO Jun-nosuke TERAMAE Naoki WAKAMIYA
Due to rapid increases in the number of users and diversity of devices, temporal fluctuation of traffic on information communication network is becoming large and rapid recently. Especially, sudden traffic changes such as flash crowds often cause serious congestion on the network and result in nearly fatal slow down of date-communication speed. In order to keep communication quality high on the network, routing protocols that are scalable and able to quickly respond to rapid, and often unexpected, traffic fluctuation are highly desired. One of the promising approaches is the distributed routing protocol, which works without referring global information of the whole network but requires only limited informatin of it to realize route selection. These approaches include biologically inspired routing protocols based on the Adaptive Response by Attractor Selection model (ARAS), in which routing tables are updated along with only a scalar value reflecting communication quality measured on each router without evaluating communication quality over the whole network. However, the lack of global knowledge of the current status of the network often makes it difficult to respond promptly to traffic changes on the network that occurs at outside of the local scope of the protocol and causes inefficient use of network resources. In order to solve the essential problem of the local scope, we extend ARAS and propose a routing protocol with active and stochastic route exploration. The proposed protocol can obtain current communication quality of the network beyond its local scope and promptly responds to traffic changes occur on the network by utilizing the route exploration. In order to compensate destabilization of routing itself due to the active and stochastic exploration, we also introduce a short-term memory to the dynamics of the proposed attractor selection model. We conform by numerical simulations that the proposed protocol successfully balances rapid exploration with reliable routing owning to the memory term.
Takashi KUNIMOTO Yoshiko FUJITA Hiroshi OKURA
A continuous flow reactor equipped with a low-loss flow channel and a microwave cavity was developed for synthesizing nanophosphors. A continuous solution synthesis of YVO4:Eu,Bi nanophosphor was succeeded through the rapid hydrothermal method using this equipment. Internal quantum efficiency of YVO4:Eu,Bi nanophosphor obtained by 20 minutes microwave heating is about 30% at 320 nm as high as that obtained by 6 hours hydrothermal treatment in autoclave.
Sun-Mi PARK Ku-Young CHANG Dowon HONG Changho SEO
We propose subquadratic space complexity multipliers for any finite field $mathbb{F}_{q^n}$ over the base field $mathbb{F}_q$ using the Dickson basis, where q is a prime power. It is shown that a field multiplication in $mathbb{F}_{q^n}$ based on the Dickson basis results in computations of Toeplitz matrix vector products (TMVPs). Therefore, an efficient computation of a TMVP yields an efficient multiplier. In order to derive efficient $mathbb{F}_{q^n}$ multipliers, we develop computational schemes for a TMVP over $mathbb{F}_{q}$. As a result, the $mathbb{F}_{2^n}$ multipliers, as special cases of the proposed $mathbb{F}_{q^n}$ multipliers, have lower time complexities as well as space complexities compared with existing results. For example, in the case that n is a power of 3, the proposed $mathbb{F}_{2^n}$ multiplier for an irreducible Dickson trinomial has about 14% reduced space complexity and lower time complexity compared with the best known results.
Tran Thi Thao NGUYEN Leonardo LANANTE Yuhei NAGAO Hiroshi OCHI
Wireless channel emulators are used for the performance evaluation of wireless systems when actual wireless environment test is infeasible. The main contribution of this paper is the design of a MU-MIMO channel emulator capable of sending channel feedback automatically to the access point from the generated channel coefficients after the programmable time duration. This function is used for MU beamforming features of IEEE 802.11ac. The second contribution is the low complexity design of MIMO channel emulator with a single path implementation for all MIMO channel taps. A single path design allows all elements of the MIMO channel matrix to use only one Gaussian noise generator, Doppler filter, spatial correlation channel and Rician fading emulator to minimize the hardware complexity. In addition, single path implementation allows the addition of the feedback channel output with only a few additional non-sequential elements which would otherwise double in a parallel implementation. To demonstrate the functionality of our MU-MIMO channel emulator, we present actual hardware emulator results of MU-BF receive signal constellation on oscilloscope.
Takahiro SUZUKI Takeshi IKENAGA
Recently, cloud systems have started to be utilized for services which analyze user's data in the field of computer vision. In these services, keypoints are extracted from images or videos, and the data is identified by machine learning with a large database in the cloud. To reduce the number of keypoints which are sent to the cloud, Keypoints of Interest (KOI) extraction has been proposed. However, since its computational complexity is large, hardware implementation is required for real-time processing. Moreover, the hardware resource must be low because it is embedded in devices of users. This paper proposes a hardware-friendly KOI algorithm with low amount of computations and its real-time hardware implementation based on dual threshold keypoint detection by gradient histogram and parallelization of connectivity of adjacent keypoint-utilizing register counters. The algorithm utilizes dual-histogram based detection and keypoint-matching based calculation of motion information and dense-clustering based keypoint smoothing. The hardware architecture is composed of a detection module utilizing descriptor, and grid-region-parallelization based density clustering. Finally, the evaluation results of hardware implementation show that the implemented hardware achieves Full-HD (1920x1080)-60 fps spatio-temporal keypoint extraction. Further, it is 47 times faster than low complexity keypoint extraction on software and 12 times faster than spatio-temporal keypoint extraction on software, and the hardware resources are almost the same as SIFT hardware implementation, maintaining accuracy.
Yuma KINOSHITA Sayaka SHIOTA Masahiro IWAHASHI Hitoshi KIYA
A number of successful tone mapping operators (TMOs) for contrast compression have been proposed due to the need to visualize high dynamic range (HDR) images on low dynamic range devices. This paper proposes a novel inverse tone mapping (TM) operation and a new remapping framework with the operation. Existing inverse TM operations require either the store of some parameters calculated in forward TM, or data-depended operations. The proposed inverse TM operation enables to estimate HDR images from LDR ones mapped by the Reinhard's global operator, not only without keeping any parameters but also without any data-depended calculation. The proposed remapping framework with the inverse operation consists of two TM operations. The first TM operation is carried out by the Reinhard's global operator, and then the generated LDR one is stored. When we want different quality LDR ones, the proposed inverse TM operation is applied to the stored LDR one to generate an HDR one, and the second TM operation is applied to the HDR one to generate an LDR one with desirable quality, by using an arbitrary TMO. This framework allows not only to visualize an HDR image on low dynamic range devices at low computing cost, but also to efficiently store an HDR one as an LDR one. In simulations, it is shown that the proposed inverse TM operation has low computational cost, compared to the conventional ones. Furthermore, it is confirmed that the proposed framework allows to remap the stored LDR one to another LDR one whose quality is the same as that of the LDR one remapped by the conventional inverse TMO with parameters.
A method of color scheme is proposed considering contrast of luminance between adjacent regions and design property. This method aims at setting the contrast of luminance high, in order to make the image understandable to visually handicapped people. This method also realizes preferable color design for visually normal people by assigning color components from color combination samples. Interactive evolutionary computing is adopted to design the luminance and the color, so that the luminance and color components are assigned to each region appropriately on the basis of human subjective criteria. Here, the luminance is designed first, and then color components are assigned, keeping the luminance unchanged. Since samples of fine color combinations are applied, the obtained color design is also fine and harmonic. Computer simulations verify the high performance of this system.
Shi BAO Go TANAKA Hakaru TAMUKOH Noriaki SUETAKE
Protanopes and deuteranopes are difficult to distinguish some color pairs. In this letter, a new lightness modification method which considers the Craik-O'Brien effect is proposed. The lightness modification is performed at parts which are difficult to distinguish in the protanopia or deuteranopia. Experiments show the validity of the proposed method.
Keita KOBAYASHI Hiroyuki TSUJI Tomoaki KIMURA
In this paper, we propose a digital image enlargement method based on a fuzzy technique that improves half-pixel generation, especially for convex and concave signals. The proposed method is a modified version of the image enlargement scheme previously proposed by the authors, which achieves accurate half-pixel interpolation and enlarges the original image by convolution with the Lanczos function. However, the method causes impulse-like artifacts in the enlarged image. In this paper, therefore, we introduce a fuzzy set and fuzzy rule for generating half-pixels to improve the interpolation of convex and concave signals. Experimental results demonstrate that, in terms of image quality, the proposed method shows superior performance compared to bicubic interpolation and our previous method.
Hiroki KURODA Masao YAMAGISHI Isao YAMADA
For the nonlinear acoustic echo cancellation, we present an algorithm to estimate the threshold of the clipping effect and the room impulse response vector by suppressing their time-varying cost function. A common way to suppress the time-varying cost function of a pair of parameters is to alternatingly minimize the function with respect to each parameter while keeping the other fixed, which we refer to as adaptive alternating minimization. However, since the cost function for the threshold is nonconvex, the conventional methods approximate the exact minimizations by gradient descent updates, which causes serious degradation of the estimation accuracy in some occasions. In this paper, by exploring the fact that the cost function for the threshold becomes piecewise quadratic, we propose to exactly minimize the cost function for the threshold in a closed form while suppressing the cost function for the impulse response vector in an online manner, which we call exact-online adaptive alternating minimization. The proposed method is expected to approximate more efficiently the adaptive alternating minimization strategy than the conventional methods. Numerical experiments demonstrate the efficacy of the proposed method.
Dijian CHEN Kenji FUJIMOTO Tatsuya SUZUKI
This paper develops the generating function method for the discrete-time nonlinear optimal control problem. This method can analytically give the optimal input as state feedforward control in terms of the generating functions. Since the generating functions are nonlinear, we also develop numerical implementations to find their Taylor series expressions. This finally gives optimal solutions expressed only in terms of the pre-computed generating function coefficients and state boundary conditions, such that it is useful for the on-demand optimal solution generation for different boundary conditions. Examples demonstrate the effectiveness of the developed method.
To resist algebraic and fast algebraic attacks, Boolean functions used in stream ciphers should have optimal algebraic immunity and good fast algebraic immunity. One challenge of cryptographic Boolean functions is to determine their ability to resist fast algebraic attacks, which can be measured by their fast algebraic immunities. In this letter, we determine the exact values of fast algebraic immunity of the majority function of 2m and 2m+1 variables. This is the first time that the exact values of the fast algebraic immunity of an infinite class of symmetric Boolean functions with optimal algebraic immunity are determined.
Lijing MA Huihui BAI Mengmeng ZHANG Yao ZHAO
In this paper, a novel scheme of the adaptive sampling of block compressive sensing is proposed for natural images. In view of the contents of images, the edge proportion in a block can be used to represent its sparsity. Furthermore, according to the edge proportion, the adaptive sampling rate can be adaptively allocated for better compressive sensing recovery. Given that there are too many blocks in an image, it may lead to a overhead cost for recording the ratio of measurement of each block. Therefore, K-means method is applied to classify the blocks into clusters and for each cluster a kind of ratio of measurement can be allocated. In addition, we design an iterative termination condition to reduce time-consuming in the iteration of compressive sensing recovery. The experimental results show that compared with the corresponding methods, the proposed scheme can acquire a better reconstructed image at the same sampling rate.