Parametric Sequence Alignment with Constraints

Approximate matching techniques based on string alignment are important tools for investigating similarities between strings, such as those representing DNA and protein sequences. We propose a constraint based approach for parametric sequence alignment which allows for more general string alignment queries where the alignment cost can itself be parameterized as a query with some initial constraints. Thus, the costs need not be fixed in a parametric alignment query unlike the case in normal alignment. The basic dynamic programming string edit distance algorithm is generalized to a naive algorithm which uses inequalities to represent the alignment score. The naive algorithm is rather costly and the remainder of the paper develops an improvement which prunes alternatives where it can and approximates the alternatives otherwise. This reduces the number of inequalities significantly and strengthens the constraint representation with equalities. We present some preliminary results using parametric alignment on some general alignment queries.     

A Simultaneous Search Problem

We introduce a new search problem motivated by computational metrology. The problem is as follows: we would like to locate two unknown numbers x,y ∈ [0,1] with as little uncertainty as possible, using some given number k of probes. Each probe is specified by a real number r∈ [0,1] . After a probe at r , we are told whether x≤ r or x \geq r , and whether y≤ r or y\geq r . We derive the optimal strategy and prove that the asymptotic behavior of the total uncertainty after k probes is 13/7 2 ^-(k+1)/2 for odd k and 13/10 2 ^-k/2 for even k . Received November 11, 1996; revised October 2, 1997, and July 13, 1998.     

An Effective Technique for Subpixel Image Registration Under Noisy Conditions

This paper proposes an effective higher order statistics method to address subpixel image registration. Conventional power spectrum-based techniques employ second-order statistics to estimate subpixel translation between two images. They are, however, susceptible to noise, thereby leading to significant performance deterioration in low signal-to-noise ratio environments or in the presence of cross-correlated channel noise. In view of this, we propose a bispectrum-based approach to alleviate this difficulty. The new method utilizes the characteristics of bispectrum to suppress Gaussian noise. It develops a phase relationship between the image pair and estimates the subpixel translation by solving a set of nonlinear equations. Experimental results show that the proposed technique provides performance improvement over conventional power-spectrum-based methods under different noise levels and conditions.     

Subband Synthesis for Color Filter Array Demosaicking

This paper presents a new algorithm for demosaicking images captured through a color filter array (CFA). The objective of the CFA demosaicking is to render a full color image from the mosaicked image. This is commonly achieved by estimating the missing color information from the surrounding observed pixels. In this paper, we integrate the observation that color images have a strong intrachannel spatial correlation in low-frequency components and a dominant interchannel correlation in the high- frequency components. A new framework is proposed to utilize this information where the missing pixels in each color channel are estimated from the wavelet subbands. A modified median-filtering operation is then applied in the subband domain. The algorithm is adaptive and produces superior full-resolution images when compared with other methods.     

Projecting CLPR constraints

The presentation of constraints in a usable form is an essential aspect of Constraint Logic Programming (CLP) systems. It is needed both in the output of constraints, as well as in the production of an internal representation of constraints for meta-level manipulation. Typically, only a small subset \(\tilde x\) of the variables in constraints is of interest, and so an informal statement of the problem at hand is: given a conjunction \(c(\tilde x,\tilde y)\) of constraints, express the projection \(\exists \tilde y c(\tilde x,\tilde y)\) ofc onto \(\tilde x\) in the simplest form. In this paper, we consider the constraints of the CLP(R) system and describe the essential features of its projection module. One main part focuses on the well-known problem of projection inlinear arithmetic constraints. We start with a classical algorithm and augment it with a procedure for eliminating redundant constraints generated by the algorithm. A second part discusses projection of the other object-level constraints: equations over trees and nonlinear equations. The final part deals with producing a manipulable form of the constraints, which complicates the projection problem.     

Nodal Superconvergence of SDFEM for Singularly Perturbed Problems

In this paper, we analyze the streamline diffusion finite element method for one dimensional singularly perturbed convection-diffusion-reaction problems. Local error estimates on a subdomain where the solution is smooth are established. We prove that for a special group of exact solutions, the nodal error converges at a superconvergence rate of order (ln ε ⁻¹/N)^2k (or (ln N/N)^2k ) on a Shishkin mesh. Here ε is the singular perturbation parameter and 2N denotes the number of mesh elements. Numerical results illustrating the sharpness of our theoretical findings are displayed.     

Graph-based shape indexing

Graphs have become growingly important in representing shapes in computer vision. Given a query graph, it is essential to retrieve similar database graphs efficiently from a large database. In this paper, we present a graph-based indexing technique which overcomes significant drawbacks of the previous work (Demirci et al. in Comput Vis Image Underst 110(3):312–325, 2008) using a recently developed theorem from the domain of matrix analysis. Our technique starts by representing the topological structure of a graph in a vector space. As done in the previous work, the topological structure of a graph is constructed using its Laplacian spectra. However, unlike the previous approach, which represents all sugraphs of a database graph in the vector space to account for local similarity, a database graph in the proposed framework is represented as a single vector. By performing a range search around the query, the proposed indexing technique returns a set with both partial and global similarity. Empirical evaluation of the algorithm on an extensive set of retrieval trials including a comparison with the previous approach in both 2D and 3D demonstrates the effectiveness, efficiency, and robustness of the overall approach.     

A stochastic neighborhood search approach for airport gate assignment problem

An appropriate and efficient gate assignment is of great importance in airports since it plays a major role in the revenue obtained from the airport operations. In this study, we have focused mainly on maximum gate employment, or in other words minimize the total duration of un-gated flights. Here, we propose a method that combines the benefits of heuristic approaches with some stochastic approach instead of using a purely probabilistic approach to top-down solution of the problem. The heuristic approaches are usually used in order to provide a fast solution of the problem and later stochastic searches are used in order to ameliorate the previous results of the heuristic approach whenever possible. The proposed method generates an assignment order for the whole planes that corresponds to assignment priority. The ordering process is followed by the allocation step. Since, in practice, each airport has its own physical architecture, there have been arisen many constraints mainly concerning airplane types and parking lots in this step. Sequentially handling the plane ordering and allocation phases provides us great modularity in handling the constraints. The effectiveness of the proposed methodology has been tried to be illustrated firstly on fictively generated flight schedule data and secondly on the real world data obtained from a real world application developed for ?stanbul Atatürk Airport.     

Experimental investigation of steel fiber reinforced concrete box beams under bending

Reduction of dead weight of a reinforced-concrete (RC) structure without too much concession in its load carrying capacity has always been an attractive study subject because it engenders (1) a decrease in dimensions of the members, (2) a decrease in the reinforcement steel, and (3) a decrease in lateral inertia forces during severe earthquakes. In this study, nine RC beams of outer dimensions of 300 × 300 × 2000 mm, six of which are box beams, designed and produced using a C20 class steel fiber concrete, (SFRC) with the commonly used steel fiber type of Dramix-RC-80/0.60-BN at a dosage of 30 kg/m³, are tested under bending. The mechanical behaviours of all these nine beams under bending are recorded from the beginning of the test till the ultimate failure of the tensile reinforcement in a two-point beam-loading setup. The proportions of (1) loss in ultimate load versus reduction in dead weight and (2) (ultimate experimental load)/(ultimate theoretical load) of the SFRC box beams are determined for two different box thicknesses. Dimensionless behaviour relationships of all the SFRC beams are determined, and the experimentally obtained relationship between the ratio of (actual ultimate load)/(theoretical ultimate load) and the ratio of (wall thickness)/(beam height) for the SFRC box beams is expressed diagrammatically.     

Growth morphology and phase analysis of titanium-based coating produced by thermochemical method

In the present study, high-speed tool steel was used to coat titanium by pack cementation technique. Coatings show a growth morphology similar to that of the chemical vapor deposition method. Time and temperature of the coating affects its growth morphology. Coating obtained at low temperature (900 °C) yields morphology with growth of tiny particles while coating produced at high temperature (1000 °C) has a morphology with coarser particles. Phase structure of the layers also varies depending on the process time and temperature. Short coating duration yields TiC_0.3N_0.7 phase structure, whose composition is close to TiN whereas long coating duration combined with high temperature yields TiC_0.7N_0.3, whose composition is close to TiC. Mechanical properties such as hardness and resistance to abrasion also reflect changes in phase structures of different types of coating.