A novel combinatorial optimization algorithm called 2-stage discrete optimization method (2DOM) is proposed for the largest common subgraph problem (LCSP) in this paper. Given two graphs G=(V₁, E₁) and H=(V₂, E₂), the goal of LCSP is to find a subgraph G'=(V₁', E₁') of G and a subgraph H'=(V₂', E₂') of H such that G' and H' are not only isomorphic to each other but also their number of edges is maximized. The two graphs G' and H' are isomorphic when |V₁'|=|V₂'| and |E₁'|=|E₂'|, and there exists one-to-one vertex correspondence f: V₁' V₂' such that {u, v} E₁' if and only if{f(u), f(v)} E₂'. LCSP is known to be NP-complete in general. The 2DOM consists of a construction stage and a refinement stage to achieve the high solution quality and the short computation time for large size difficult combinatorial optimization problems. The construction stage creates a feasible initial solution with considerable quality, based on a greedy heuristic method. The refinement stage improves it keeping the feasibility, based on a random discrete descent method. The performance is evaluated by solving two types of randomly generated 1200 LCSP instances with a maximum of 500 vertices for G and 1000 vertices for H. The simulation result shows the superiority of 2DOM to the simulated annealing in terms of the solution quality and the computation time.

Modern micro-architectures employ superscalar techniques to enhance system performance. Since the superscalar microprocessors must fetch at least one instruction cache line at a time to support high issue rate and large amount speculative executions. There are cases that multiple branches are often encountered in one cycle. And in practical implementation this would cause serious problem while there are variable number of instruction addresses that look up the Branch Target Buffer simultaneously. In this paper, we propose a Range Associative Branch Target Buffer (RABTB) that can recognize and predict multiple branches in the same instruction cache line for a wide-issue micro-architecture. Several configurations of the RABTB are simulated and compared using the SPECint95 benchmarks. We show that with a reasonable size of prediction scope, branch prediction can be improved by supporting multiple / up to 8 branch predictions in one cache line in one cycle. Our simulation results show that the optimal RABTB should be 2048 entry, 8-column range-associate and 8-entry modified ring buffer architecture using PAs prediction algorithm. It has an average 5.2 IPC_f and branch penalty per branch of 0.54 cycles. This is almost two times better than a mechanism that makes prediction only on the first encountered branch.

Technical advances in the development of portable computers and wireless communications enable users to take part in distributed computing even while moving. The resulting environment is subject to be constrained by the mobility of users and the nature of the cordless medium. In this paper we propose a commit protocol for providing low-powered mobile hosts with two phase commit service which is a powerful technique to implement atomic actions in distributed systems, with some important aspects such as low power consumption, efficient mobility management, subject oriented service binding and effective disconnection handling to well adapt to a mobile computing environment.

We propose a query processing method for amalgamated knowledge bases. Our query processing method is an extension of the magic sets technique for query processing in amalgamated knowledge bases, augmented with the capabilities of handling amalgamated atoms. Through rewriting rules in a given amalgamated knowledge base, our method offers the advantages associated with top-down as well as bottom-up evaluation. We discuss how to handle amalgamated atoms, consider how to check whether an amalgamated atom is satisfiable in a fact set and how to extend a fact set by inserting an amalgamated atom. We also give the transformation procedures for amalgamated knowledge databases and show the correctness of our method.

In this paper, we study a new hybrid speech coder which employs a modified version of the harmonic sinusoidal analysis to encode the periodic contents of speech waveform and to split the speech spectrum into two frequency regions of harmonic and random components. A reliable fundamental frequency is estimated for the harmonic region using both speech and its linear predictive (LP) residual spectrum. The peak envelope of speech spectrum is encoded in terms of the coefficients of an all-pole spectrum. A harmonic tracking algorithm appropriately interpolates the sinusoidal parameters to achieve a smooth transition between the parameter update points and to reconstruct an essential level of periodicity in the synthetic voiced speech. The random part of spectrum and unvoiced speech are coded using the conventional CELP algorithm. The individual components are then combined at the decoder to obtain the synthetic speech. The proposed hybrid coder which combines the powerful features of the sinusoidal and CELP coding algorithms yeilds a high quality synthetic speech at 4.05 kbps.

An image edge sharpening technique with phase correction for digital image is presented. In this paper the point spread functions of a typical standard single focal lens and zoom lens are investigated with a several different apertures. And from this investigation the Fourier phase figure pattern of the point-spread function is identified. The technique here includes a traditional one (a Laplacian operator) and phase-only synthesis with the corrected Fourier phase. The Fourier phase of the original non-blurred image is estimated recursively and it is utilized for implementation of the phase-only synthesis, which is powerful for image edge sharpening. A human visual property is also introduced as a weight function in order to maintain the natural smoothness in the gray level of the resulting processed image. Simulation examples show that the proposed technique is superior to the traditional one.

A global motion parameter estimation method is proposed. The method can be used to segment an image sequence into regions of different moving objects. For any two pixels belonging to the same moving object, their associated global motion components have a fixed relationship from the projection geometry of camera imaging. Therefore, by examining the measured motion vectors we are able to group pixels into objects and, at the same time, identify some global motion information. In the presence of camera zoom, the object shape is distorted and conventional translational motion estimation may not yield accurate motion modeling. A deformable block motion estimation scheme is thus proposed to estimate the local motion of an object in this situation. Some simulation results are reported. For an artificially generated sequence containing only zoom activity, we find that the maximum estimation error in the zoom factor is about 2. 8 %. Rather good moving object segmentation results are obtained using the proposed object local motion estimation method after zoom extraction. The deformable block motion compensation is also seen to outperform conventional translational block motion compensation for video material containing zoom activity.

We have developed an experimental 4 K 2 K pixel progressive scan color camera system. This new camera system has a data rate of 297 MHz pixel/sec and 60 frame/sec and we are sure that horizontal and vertical limiting resolution of 1500 TVL (TV lines) can be achieved on a color monitor. Instead of the previous approach of improving resolution simply by increasing the pixel count in a imager, a novel four-sensor pickup method with 2/3 inch 2 million pixel CMD (Charge Modulation Device) imagers is used in this system. These sensors have 1920 (H) 1035 (V) pixels within a 16:9 wide aspect image area and are successfully driven at 148 M pixel/sec in the progressive scan mode. In the four-sensor pickup method, two sensors are used for green and the rest are for red and blue. A spatial offset imaging method in the diagonal direction was applied to the two green sensors to improve the horizontal and vertical resolution effectively. The horizontal and vertical resolution of the red and blue signals become half that of the green signal, because only one 2 M-pixel imager is used for each signal. The resolution of this system, however, is not degraded so much because the luminance signal is mainly composed of green signals.

Texture has been investigated as a cue for reconstructing 3-D structure. There are various textures in a natural scene. In this paper, the regularity of alignment of texture elements was manipulated to investigate its effect on human perception. The results show that the regularity affects human perception when only the texel density gradient is given as cue or the density cue is inconsistent with the compression cue. We introduce a model based on a MAP estimation to account for the result from a viewpoint of an integration of 3-D cues. The model simultaneously estimates texture properties and 3-D surface orientation by using prior knowledge about texture and 3-D surface. The performance of the model accounts for the experimental result well.