Sheqin DONG Xianlong HONG Song CHEN Xin QI Ruijie WANG Jun GU
Solution space smoothing allows a local search heuristic to escape from a poor, local minimum. In this paper, we propose a technique that can smooth the rugged terrain surface of the solution space of a placement problem. We test the smoothing heuristics for MCNC benchmarks, and for VLSI placement with pre-placed modules and placement with consideration of congestion. Experiment results demonstrated that solution space smoothing is very efficient for VLSI module placement, and it can be applied to all floorplanning representations proposed so far.
Jaemin KIM Moongoo KANG Seongwon CHO
This article describes a new method for converting an arbitrary topology mesh into one having subdivision connectivity. First, a base mesh is produced by applying a sequence of edge collapse operations to the original mesh with irregular connectivity. Then, the base mesh is iteratively subdivided. Each subdivided mesh is optimized to reduce its distance from the original mesh and to improve its global smoothness and compactness. A set of corresponding point pairs, which is required to compute the distance from the original mesh to the subdivided mesh, is determined by combining the initial parameterization and the multi-resolution projection. Experimental results show that the proposed method yields good performance in terms of global smoothness, small distortion, and good compactness, compared with conventional methods.
Yih-Ching SU Chu-Sing YANG Chen-Wei LEE Chin-Shun HSU
In this paper, a new Hierarchical Sum of Double Difference metric, HSDD, is introduced. It is shown, as opposed to conventional Sum of Absolute Difference (SAD) metric, how this zerotree coding aware metric can jointly constrain the motion vector searching for both temporal and spatial (quad-tree) directions under multiresolution motion estimation framework. The reward from the temporal-spatial co-optimization concept of HSDD is that fewer bits are spent later for describing the isolated zeros. The embedded wavelet video coder using HSDD metric was tested with a set of video sequences and the compression performance seems to be promising.
The objective of this study was to explore suitable spatial filters for inverse estimation of cortical potentials from the scalp electroencephalogram. The effect of incorporating noise covariance into inverse procedures was examined by computer simulations. The parametric projection filter, which allows inverse estimation with the presence of information on the noise covariance, was applied to an inhomogeneous three-concentric-sphere model under various noise conditions in order to estimate the cortical potentials from the scalp potentials. The present simulation results suggest that incorporation of information on the noise covariance allows better estimation of cortical potentials, than inverse solutions without knowledge about the noise covariance, when the correlation between the signal and noise is low. The method for determining the optimum regularization parameter, which can be applied for parametric inverse techniques, is also discussed.
Finding DC operating points of nonlinear circuits is an important and difficult task. The Newton-Raphson method adopted in the SPICE-like simulators often fails to converge to a solution. To overcome this convergence problem, homotopy methods have been studied from various viewpoints. For the global convergence of homotopy methods, it is a necessary condition that a given initial solution is the unique solution to the homotopy equation. According to the conventional criterion, such an initial solution, however, is restricted in some very narrow region. In this paper, considering the circuit interpretation of homotopy equations, we prove theorems on the uniqueness of an initial solution for globally convergent homotopy methods. These theorems give new criteria extending the region wherein any desired initial solution satisfies the uniqueness condition.
Huadong MENG Xiqin WANG Hao ZHANG Yingning PENG
The high-resolution frequency estimators most commonly used, such as Least Square (LS) method based on AR model, MVSE, MUSIC and ESPRIT, determine estimates of the sinusoidal frequencies from the sample noise-corrupted data. In this paper, a new frequency estimation method named Pole-Placement Least Square (PPLS) is presented, which is a modified LS method with a certain number of model poles restricted to the unit circle. The statistical performance of PPLS is studied numerically, and compared with the Cramer-Rao bound as well as the statistical performance corresponding to the LS methods. PPLS is shown to have higher resolution than the conventional LS method. The relationship between poles location and its resolution is also discussed in detail.
Yasuhiko TAMURA Junichi NAKAYAMA
A new formula on the Hermite expansion is presented in an explicit form. An application of the formula is given to a random boundary value problem: a plane wave reflection from a flat plane, of which position is randomly distributed in the normal direction, is presented. Several numerical results are given for a verification of the formula and for a discussion of the exact behavior of the fluctuation part of the reflection power.
The existing methods for the reconstruction of a super-resolution image from a sequence of undersampled and subpixel shifted images have to solve a large ill-condition equation group by approximately finding the pseudo-inverse matrix or performing many iterations to approach the solution. The former leads to a big burden of computation, and the latter causes the artifacts or noise to be stressed. In order to solve these problems, in this paper, we consider applying pyramid structure to the super-resolution of the image sequence and present a suitable pyramid framework, called Super-Resolution Image Pyramid (SRIP). Based on the imaging process of the image sequence, the proposed method divides a big back-projection into a series of different levels of small back-projections, thereby avoiding the above problems. As an example, the Iterative Back-Projection (IBP) suggested by Peleg is included in this pyramid framework. Computer simulations and error analyses are conducted and the effectiveness of the proposed framework is demonstrated. The image resolution can be improved better even in the case of severely undersampled images. In addition, the other general super-resolution methods can be easily included in this framework and done in parallel so as to meet the need of real-time processing.
Yih-Ching SU Chu-Sing YANG Chen-Wei LEE Chun-Wei TSENG Yao-Jei ZHENG
Adapting to the structure of 2-D H-Transform, this paper proposes a novel wavelet domain half-pixel motion compensation algorithm HMRME (Half-pixel Multi-Resolution Motion Estimation). The primary objective of this study is the reduction of the aliasing effect caused by the down-sampling in the wavelet transform under the complexity constraints. The conventional multi-resolution motion estimation scheme can be combined with the half-pixel interpolation method to generate a new high-performance wavelet video codec. The preliminary results show that the performance of HMRME rises above its counterparts, the Multi-Resolution Motion Estimation (MRME) and the Adaptive Multi-Resolution Motion Estimation (AMRME).
Tosiyasu L. KUNII Masumi IBUSUKI Galina PASKO Alexander PASKO Daisuke TERASAKI Hiroshi HANAIZUMI
Recent advances of Web information systems such as e-commerce and e-learning have created very large but hidden demands on conceptual multiresolution analysis for more generalized information analysis, cognition and modeling. To meet the demands in a general way, its modeling is formulated based on modern algebraic topology. To be specific, the modeling formulation is worked out in an incrementally modular abstraction hierarchy with emphasis on the two levels of the hierarchy appropriate for conceptual modeling: the adjunction space level and the cellular structured space level. Examples are shown to demonstrate the usefulness of the presented model as well as an implementation of a flower structure case.
We consider the classification problem as a problem of approximation of a given training set. This approximation is constructed in a multiresolution framework, and organized in a tree-structure. It allows efficient training and query, both in constant time per training point. The proposed method is efficient for low-dimensional classification and regression estimation problems with large data sets.
Hiroki SAKURAI Yasuhiro SUGIMOTO
This paper describes the design of a 2.7 V operational, 200 MS/s, 14-bit CMOS D/A converter (DAC). The DAC consists of 63 current cells in matrix form for an upper 6-bit sub-DAC, and 8 current cells and R-2R ladder resistors for a lower 8-bit sub-DAC. A source degeneration resistor, for which a transistor in the triode operational region is used, is connected to the source of a MOS current source transistor in a current cell in order to reduce the influence of threshold voltage (Vth) variation and to satisfy the differential nonlinearity error specification as a 14-bit DAC. In conventional high-speed and high-resolution DACs that have the same design specifications described here, spurious-free dynamic range (SFDR) characteristics commonly deteriorate drastically as the frequency of the reconstructed waveform increases. The causes of this deterioration were carefully examined in the present study, finding that the deterioration is caused in part by the input-data-dependent time-constant change at the output terminal. Unexpected current flow in parasitic capacitors associated with current sources causes the change in the output current depending on the input data, resulting in time-constant change. In order to solve this problem, we propose a new output circuit to fix the voltage at the node where the outputs of the current sources are combined. SPICE circuit simulation demonstrates that 63 dB of SFDR characteristics for the 90 MHz reconstructed waveform at the output can be realizable when the supply voltage is 2.7 V, the clock rate is 200 MS/s, and the power dissipation is estimated to be 300 mW.
The Another Solution Problem (ASP) of a problem is the following problem: for a given instance x of and a solution s to it, find a solution to x other than s. The notion of ASP as a new class of problems was first introduced by Ueda and Nagao. They also pointed out that parsimonious reductions which allow polynomial-time transformation of solutions can derive the NP-completeness of ASP of a certain problem from that of ASP of another. In this paper we consider n-ASP, the problem to find another solution when n solutions are given, and formalize it to investigate its characteristics. In particular we consider ASP-completeness, the completeness with respect to the reductions satisfying the properties mentioned above. The complexity of ASPs has a relation with the difficulty of designing puzzles. We prove the ASP-completeness of three popular puzzles: Slither Link, Cross Sum, and Number Place. Since ASP-completeness implies NP-completeness, these results can be regarded as new results of NP-completeness proof of puzzles.
In this paper we present a new post enhancement method for single look complex (SLC) SAR imagery, which is based on phase-extension inverse filtering. To obtain a high-quality SAR image, the proposed method improves the mainlobe resolution as well as efficiently suppresses the sidelobes with low computational complexity. The proposed method extends the effective signal band up to the maximum-bandwidth allowed by a SAR system. The band-extension is achieved by adjusting the magnitude level of matched filtered SAR spectrum. Because the proposed method preserves the phase components of the spectrum unlike other super-resolution techniques and deconvolution techniques, it enhances a SAR image without causing any displacement. To verify the efficacy of the proposed method we apply it to a simulated SAR image and a real ERS-1 SAR image. The result images show that the proposed method improves the mainlobe resolution with low sidelobe levels.
Takao YAMAMOTO Kenya JIN'NO Haruo HIROSE
In a previous study about a combinatorial optimization problem solver using neural networks, since the Hopfield method, convergence to the optimum solution sooner and with more certainty is regarded as important. Namely, only static states are considered as the information. However, from a biological point of view, dynamical systems have attracted attention recently. Therefore, we propose a "dynamical" combinatorial optimization problem solver using hysteresis neural networks. In this paper, the proposed system is evaluated by the N-Queen problem.
Kiyotaka YAMAMURA Osamu NAKAMURA
An efficient algorithm is proposed for finding all solutions of piecewise-linear resistive circuits containing bipolar transistors. This algorithm is based on a powerful test (termed the LP test) for nonexistence of a solution in a given region using linear programming (LP). In the LP test, an LP problem is formulated by surrounding the exponential functions in the Ebers-Moll model by right-angled triangles, and it is solved by LP, for example, by the simplex method. In this paper, it is shown that the LP test can be performed by the dual simplex method, which makes the number of pivotings much smaller. Effectiveness of the proposed technique is confirmed by numerical examples.
In this paper, we consider two types of promises for (k-)CNF formulas which can help to find a satisfying assignment of a given formula. The first promise is the Hamming distance between truth assignments. Namely, we know in advance that a k-CNF formula with n variables, if satisfiable, has a satisfying assignment with at most pn variables set to 1. Then we ask whether or not the formula is satisfiable. It is shown that for k 3 and (i) when p=nc (-1 < c 0), the problem is NP-hard; and (ii) when p=log n/n, there exists a polynomial-time deterministic algorithm. The algorithm is based on the exponential-time algorithm recently presented by Schoning. It is also applied for coloring k-uniform hypergraphs. The other promise is the number of satisfying assignments. For a CNF formula having 2n/2nε (0 ε < 1) satisfying assignments, we present a subexponential-time deterministic algorithm based on the inclusion-exclusion formula.
The existing methods for reconstruction of a super-resolution image from undersampled and shubpixel shifted image sequence have two disadvantages. One is that most of them have to perform a lot of computations which lead to taking a lot of time and cannot meet the need of realtime processing. Another is that they cannot achieve satisfactory results in the case that the undersampling rate is too low. This paper considers applying a pyramid structure method to the super-resolution of the image sequence since it has some iterative optimization and parallel processing abilities. Based on the Iterative Back-Projection proposed by Peleg, a practical implementation, called Pyramid Iterative Back-Projection, is presented. The experiments and the error analysis show the effectiveness of this method. The image resolution can be improved better even in the case of severely undersampled images. In addition, the proposed method can be done in parallel and meet the need of real-time processing. The implementation framework of the method can be easily extended to the other general super-resolution methods.
Keiji SAWADA Hiroaki NAKAMURA Hirotomo KAMBE Toshiharu SAIKI
Using the finite-difference time-domain method, we evaluated the performance of apertured near-field fiber probes with a double-tapered structure, which have exhibited, in recent experiments, a much higher collection efficiency of localized light in comparison with single-tapered probes. We clarified that this high collection efficiency could be attributed to the shortening of the cutoff region, and the efficient coupling to the guiding mode of the optical fiber. By reproducing the experimental results in terms of the spatial resolution and the collection efficiency as a function of the aperture diameter, our calculation was confirmed to be valid and useful for the design of probes in a variety of applications.
Kouki TOTSUKA Haruhiko ITO Motoichi OHTSU
We introduce stepwise resonant excitation by two-color optical near fields in order to detect Rb atoms with a slit-type detector. Blue fluorescence of the second D2 line is monitored for background-free detection. Feasibility of the method is shown from an experiment with a Rb vapor cell, where a sub-Doppler spectrum with the FWHM of 80 MHz is obtained. The detection efficiency is estimated at about 3% for cold Rb atoms.