We propose the "Two-Step Search scheme with Linear search based Second step (TSS-LS)" by improving the conventional "Two-Step Search scheme with Bit reversal search based Second step (TSS-BS)" for reliable as well as rapid acquisition of Ultra Wide Band (UWB) signals in multipath channels. The proposed TSS-LS utilizes two different thresholds and search windows to achieve fast acquisition. Furthermore, unlike the TSS-BS in which the bit reversal algorithm is applied in both steps, the linear search is adopted for the second step in the proposed TSS-LS to correctly find the starting point in the range of effective delay spread of the multipath channels, and to obtain reliable bit error rate performance of the UWB systems.

We propose a recursive clustering and order restriction (R-CORE) method for learning large-scale Bayesian networks. The proposed method considers a reduced search space for directed acyclic graph (DAG) structures in scoring-based Bayesian network learning. The candidate DAG structures are restricted by clustering variables and determining the intercluster directionality. The proposed method considers cycles on only cmax(«n) variables rather than on all n variables for DAG structures. The R-CORE method could be a useful tool in very large problems where only a very small amount of training data is available.

The realization of k-nearest-matches search capability in fully-parallel mixed digital-analog associative memories by a sequential autonomous search mode is reported. The proposed concept and circuit implementation can be applied with all types of distance measures such as Hamming, Manhattan or Euclidean distance search, and the k value can be freely selected during operation. A test chip for concept verification has been designed in 0.35 µm CMOS technology with two-poly, three-metal layers, realizes k-nearest-matches Euclidean distance search and consumes 5.12 mm2 of the chip area for 64 reference patterns each with 16 units of 5-bit.

In this paper, we propose a stochastic dynamic local search (SDLS) method for Multiple-Valued Logic (MVL) learning by introducing stochastic dynamics into the traditional local search method. The proposed learning network maintains some trends of quick descent to either global minimum or a local minimum, and at the same time has some chance of escaping from local minima by permitting temporary error increases during learning. Thus the network may eventually reach the global minimum state or its best approximation with very high probability. Simulation results show that the proposed algorithm has the superior abilities to find the global minimum for the MVL network learning within reasonable number of iterations.

To drastically reduce the power dissipation (P) of an absolute difference accumulation (ADA) circuit for H.26x/MPEG4 motion estimation, a fast block-matching (BM) algorithm called the Multiple Block-matching Step (MBS) algorithm has been developed. The MBS algorithm can drastically improve the block matching speed, while achieving the same visual quality as that of a full search (FS) BM algorithm. Power dissipation (P) of a 0.18-µm CMOS absolute difference accumulator (ADA) circuit employing the MBS algorithm is significantly reduced to the range of about 0.3% to 12% that of the same ADA circuit adopting FS.

In this paper we focus on building a large scale keyword search service over structured Peer-to-Peer (P2P) networks. Current state-of-the-art keyword search approaches for structured P2P systems are based on inverted list intersection. However, the biggest challenge in those approaches is that when the indices are distributed over peers, a simple query may cause a large amount of data to be transmitted over the network. We propose in this paper a new P2P keyword search scheme, called "Proof," which aims to reduce the network traffic generated during the intersection process. We applied three main ideas in Proof to reduce network traffic, including (1) using a sorted query flow, (2) storing content summaries in the inverted lists, and (3) setting a stop condition for the checking of content summaries. We also discuss the advantages and limitations of Proof, and conducted extensive experiments to evaluate the search performance and the quality of search results. Our simulation results showed that, compared with previous solutions, Proof can dramatically reduce network traffic while providing 100% precision and high recall of search results, at some additional storage overhead.

We present the use of a Modified Generalized Hough Transform (MGHT) and deformable contours for image data retrieval where a given contour, gray-scale, or color template image can be detected in the target image, irrespective of its position, size, rotation, and smooth deformation transformations. Potential template positions are found in the target image using our novel modified Generalized Hough Transform method that takes measurements from the template features by extending a line from each edge contour point in its gradient direction to the other end of the object. The gradient difference is used to create a relationship with the orientation and length of this line segment. Potential matching positions in the target image are then searched by also extending a line from each target edge point to another end along the normal, then looking up the measurements data from the template image. Positions with high votes become candidate positions. Each candidate position is used to find a match by allowing the template to undergo a contour transformation. The deformed template contour is matched with the target by measuring the similarity in contour tangent direction and the smoothness of the matching vector. The deformation parameters are then updated via a Bayesian algorithm to find the best match. To avoid getting stuck in a local minimum solution, a novel coarse-and-fine model for contour matching is included. Results are presented for real images of several kinds including bin picking and fingerprint identification.

Recently, cars are equipped with a lot of sensors for safety driving. We have been trying to store the driving-scene video with such sensor data and to detect the change of scenery of streets. Detection results can be used for building historical database of town scenery, automatic landmark updating of maps, and so forth. In order to compare images to detect changes, image retrieval taken at nearly identical locations is required as the first step. Since Global Positioning System (GPS) data essentially contain some noises, we cannot rely only on GPS data for our image retrieval. Therefore, we have developed an image retrieval algorithm employing edge-histogram-based image features in conjunction with hierarchical search. By using edge histograms projected onto the vertical and horizontal axes, the retrieval has been made robust to image variation due to weather change, clouds, obstacles, and so on. In addition, matching cost has been made small by limiting the matching candidates employing the hierarchical search. Experimental results have demonstrated that the mean retrieval accuracy has been improved from 65% to 76% for the front-view images and from 34% to 53% for the side-view images.

In this paper, the interpolation line search (ILS) algorithm to find the desirable step length in a numerical optimization method is investigated to determine the optimal saturation limits with non-smooth nonlinearities. The simple steepest descent algorithm is used to illustrate that the ILS algorithm can provide adequate reductions in an objective function at minimal cost with fast convergence. The power system stabilizer (PSS) with output limits is used as an example for a nonlinear controller to be tuned. The efficient computation to implement the ILS algorithm in the steepest descent method is available by using the hybrid system model with the differential-algebraic-impulsive-switched (DAIS) structure. The simulation results are given to show the performance improved by the ILS algorithm.

In this paper, we propose a high speed Preamble Searcher suitable for the RACH (Random Access Channel) structure in WCDMA reverse link receivers. Unlike IS-95, WCDMA system uses the AISMA (Acquisition Indication Sense Multiple Access) scheme. Because of the time limit between RACH preamble transmission and AI (Acquisition Indicators), and the restriction on the number of RACH signatures assigned to RACH preamble, fast acquisition is required for efficient operation. The Preamble Searcher proposed in this paper is designed for 2-antenna systems; it adopts the FHT (Fast Hadamard Transform) algorithm that has the radix-2 16 point FFT (Fast Fourier Transform) structure. The acquisition speed using FHT is 32 times faster than the conventional method that correlates each signature. Based on this fast acquisition scheme, we improved the acquisition performance by calculating correlation up to 4096 chips of the total preamble length.

Multipath search based instantaneous root-mean-squared (RMS) delay spread (RDS) estimators mainly depend on path detection or multipath search. This paper proposes a novel method for multipath search through Minimum Descriptive Length (MDL) criterion, and hence a novel instantaneous RDS estimation method for wireless OFDM systems. compared with the conventional multipath search based instantaneous RDS estimators, the proposed estimator doesn't need any a priori information about the noise variance and the channel power delay profile (PDP) while the performance is improved. Simulation results demonstrate that the proposed estimator is also insensitive to the variance of SNR and robust against the frequency selectivity, as well as the vehicle speed.

We consider the reliability-based heuristic search methods for maximum likelihood decoding, which generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Some studies have proposed methods for reducing the space complexity of these algorithms, which is crucially large for long block codes at medium to low signal to noise ratios of the channel. In this paper, we propose a new method for reducing the time complexity of generating candidate codewords by storing some already generated candidate codewords. Simulation results show that the increase of memory size is small.

This paper proposes a fast motion estimation algorithm for variable block-sizes by utilizing motion vector bottom-up procedure for H.264. The refined motion vectors of adjacent small blocks are merged to predict the motion vectors of larger blocks for reducing the computation. Experimental results show that our proposed method has lower computational complexity than full search, fast full search and fast motion estimation of the H.264 reference software JM93 with slight quality decrease and little bit-rate increase.

An improved algorithm of Guided Local Search called objective function adjustment algorithm is proposed for combinatorial optimization problems. The performance of Guided Local Search is improved by objective function adjustment algorithm using multipliers which can be adjusted during the search process. Moreover, the idea of Tabu Search is introduced into the objective function adjustment algorithm to further improve the performance. The simulation results based on some TSPLIB benchmark problems showed that the objective function adjustment algorithm could find better solutions than Local Search, Guided Local Search and Tabu Search.

This letter proposes a fast k nearest neighbors search algorithm based on the wavelet transform. This technique exploits the important information of the approximation coefficients of the transform coefficient vector, from which we obtain two crucial inequalities that can be used to reject those vectors for which it is impossible to be k nearest neighbors. The computational complexity for searching for k nearest neighbors can be largely reduced. Experimental results on texture classification verify the effectiveness of our algorithm.

Arranging n points as uniformly as possible is a frequently occurring problem. It is equivalent to packing n equal and non-overlapping circles in a unit square. In this paper we generalize this problem in such a way that points are inserted one by one with uniformity preserved at every instance. Our criterion for uniformity is to minimize the gap ratio (which is the maximum gap over the minimum gap) at every point insertion. We present a linear time algorithm for finding an optimal n-point sequence with the maximum gap ratio bounded by in the 1-dimensional case. We describe how hard the same problem is for a point set in the plane and propose a local search heuristics for finding a good solution.

An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio for an arbitrarily positive constant c, where N denotes the number of men in an input.

In this letter, a method estimating the intercell carrier frequency-offset (CFO) in orthogonal frequency division multiplexing (OFDM)-based cellular systems is proposed for the user's equipment (UE), especially at the cell boundary, in downlink channels. After describing a new method of deriving the intercell CFO from the signals received by adjacent base stations (BSs), we propose a cell-searching method using the estimated CFOs. It is shown by computer simulation that the proposed methods can uniquely estimate the intercell CFOs and identify the target BS with a high detection probability at the UE.

The hand posture estimation system by searching a similar image from a vast database, such as our previous research, may cause the increase of processing time, and prevent realtime controlling of a robot. In this study, the authors proposed a new estimation method of human hand posture by rearranging a large-scale database with the Self-Organizing Map including self-reproduction and self-annihilation, which enables two-step searches of similar image with short period of processing time, within small errors, and without deviation of search time. The experimental results showed that our system exhibited good performance with high accuracy within processing time above 50 fps for each image input with a 2.8 GHz CPU PC.

This paper proposes a low power scan test scheme and formulates a problem based on this scheme. In this scheme the flip-flops are grouped into N scan chains. At any time, only one scan chain is active during scan test. Therefore, both average power and peak power are reduced compared with conventional full scan test methodology. This paper also proposes a tabu search-based approach to minimize test application time. In this approach we handle the information during deterministic test efficiently. Experimental results demonstrate that this approach drastically reduces both average power and peak power dissipation at a little longer test application time on various benchmark circuits.