Fast object recognition using dynamic programming from combination of salient line groups

This paper presents a new method of grouping and matching line segments to recognize objects. We propose a dynamic programming-based formulation extracting salient line patterns by defining a robust and stable geometric representation that is based on perceptual organizations. As the endpoint proximity, we detect several junctions from image lines. We then search for junction groups by using the collinear constraint between the junctions. Junction groups similar to the model are searched in the scene, based on a local comparison. A DP-based search algorithm reduces the time complexity for the search of the model lines in the scene. The system is able to find reasonable line groups in a short time.     

On-line cursive hangul recognition that uses DP matching to detect key segmentation points

As a means to perform on-line recognition of cursive Korean characters, called hanguls, we describe a structural analysis type algorithm that searches globally for key points of segmentation on a character unit level and can cope with large variations in stroke shape and position. This “segmentation points search” is systematically performed by a two-level dynamic programming (DP) matching algorithm in conjunction with syntax control of hangul composition characteristics. Fine discrimination for phonemes and characters is effectively realized using mutual information among strokes. Experiments demonstrate computational feasibility and that the proposed approach provides high recognition and segmentation ability.     

On-line signature recognition based on VQ-DTW

This paper studies some pattern recognition algorithms for on-line signature recognition: vector quantization (VQ), nearest neighbor (NN), dynamic time warping (DTW) and hidden Markov models (HMM). We have used a database of 330 users which includes 25 skilled forgeries performed by five different impostors. This database is larger than the typical ones found in the literature.Experimental results reveal that our first proposed combination of VQ and DTW (by means of score fusion) outperforms the other algorithms (DTW, HMM) and achieves a minimum detection cost function (DCF) value equal to 1.37% for random forgeries and 5.42% for skilled forgeries. In addition, we present another combined DTW-VQ scheme which enables improvement of privacy for remote authentication systems, avoiding the submission of the whole original dynamical signature information (using codewords, instead of feature vectors). This system achieves similar performance than DTW.     

3D model retrieval using principal plane analysis and dynamic programming

Three dimensional models play an important role in many applications; the problem is how to select the appropriate models from a 3D database rapidly and accurately. In recent years, a variety of shape representations, statistical methods, and geometric algorithms have been proposed for matching 3D shapes or models. In this paper, we propose a 3D shape representation scheme based on a combination of principal plane analysis and dynamic programming. The proposed 3D shape representation scheme consists of three steps. First, a 3D model is transformed into a 2D image by projecting the vertices of the model onto its principal plane. Second, the convex hall of the 2D shape of the model is further segmented into multiple disjoint triangles using dynamic programming. Finally, for each triangle, a projection score histogram and moments are extracted as the feature vectors for similarity searching. Experimental results showed the robustness of the proposed scheme, which resists translation, rotation, scaling, noise, and destructive attacks. The proposed 3D model retrieval method performs fairly well in retrieving models having similar characteristics from a database of 3D models.     

Efficient dynamic time warping for 3D handwriting recognition using gyroscope equipped smartphones

Handwriting character recognition from three-dimensional (3D) accelerometer data has emerged as a popular technique for natural human computer interaction. In this paper, we propose a 3D gyroscope-based handwriting recognition system that uses stepwise lower-bounded dynamic time warping, instead of conventional 3D accelerometer data. The results of experiments conducted indicate that our proposed method is more effective and efficient than conventional methods for user-independent recognition of the 26 lowercase letters in the English alphabet.     

Articulatory feature recognition using dynamic Bayesian networks

We describe a dynamic Bayesian network for articulatory feature recognition. The model is intended to be a component of a speech recognizer that avoids the problems of conventional “beads-on-a-string” phoneme-based models. We demonstrate that the model gives superior recognition of articulatory features from the speech signal compared with a state-of-the-art neural network system. We also introduce a training algorithm that offers two major advances: it does not require time-aligned feature labels and it allows the model to learn a set of asynchronous feature changes in a data-driven manner.     

Solution of the input-constrained LQR problem using dynamic programming

The input-constrained LQR problem is addressed in this paper; i.e., the problem of finding the optimal control law for a linear system such that a quadratic cost functional is minimised over a horizon of length N subject to the satisfaction of input constraints. A global solution (i.e., valid in the entire state space) for this problem, and for arbitrary horizon N, is derived analytically by using dynamic programming. The scalar input case is considered in this paper. Solutions to this problem (and to more general problems: state constraints, multiple inputs) have been reported recently in the literature, for example, approaches that use the geometric structure of the underlying quadratic programming problem and approaches that use multi-parametric quadratic programming techniques. The solution by dynamic programming proposed in the present paper coincides with the ones obtained by the aforementioned approaches. However, being derived using a different approach that exploits the dynamic nature of the constrained optimisation problem to obtain an analytical solution, the present result complements the previous methods and reveals additional insights into the intrinsic structure of the optimal solution.     

Efficient contrast invariant stereo correspondence using dynamic programming with vertical constraint

In this paper, we propose a dense stereo algorithm based on the census transform and improved dynamic programming (DP). Traditional scanline-based DP algorithms are the most efficient ones among global algorithms, but are well-known to be affected by the streak effect. To solve this problem, we improve the traditional three-state DP algorithm by taking advantage of an extended version of sequential vertical consistency constraint. Using this method, we increase the accuracy of the disparity map greatly. Optimizations have been made so that the computational cost is only increased by about 20%, and the additional memory needed for the improvement is negligible. Experimental results show that our algorithm outperforms many state-of-the-art algorithms with similar efficiency on Middlebury College’s stereo Web site. Besides, the algorithm is robust enough for image pairs with utterly different contrasts by using of census transform as the basic match metric.     

Road lane segmentation using dynamic programming for active safety vehicles

Vision-based systems for finding road lanes have to operate robustly under a wide variety of environmental conditions including large amount of scene clutters. This paper presents a method to find the lane boundaries by combining a local line extraction method and dynamic programming. The line extractor obtains an initial position of road lane boundaries from the noisy edge fragments. Then, dynamic programming improves the initial approximation to an accurate configuration of lane boundaries. Input image frame is divided into sub-regions along the vertical direction. The local line extractor extracts candidate lines of road lanes in the sub-region. Most prominent lines are found among candidate lines by dynamic programming that minimizes the functional which measures the deviation from a virtual straight line. The search framework based on DP method reduces computational cost. Experimental results using images of real road scenes demonstrate the feasibility of the proposed algorithm.