Towards subject independent continuous sign language recognition: A segment and merge approach

This paper presents a segment-based probabilistic approach to robustly recognize continuous sign language sentences. The recognition strategy is based on a two-layer conditional random field (CRF) model, where the lower layer processes the component channels and provides outputs to the upper layer for sign recognition. The continuously signed sentences are first segmented, and the sub-segments are labeled SIGN or ME (movement epenthesis) by a Bayesian network (BN) which fuses the outputs of independent CRF and support vector machine (SVM) classifiers. The sub-segments labeled as ME are discarded and the remaining SIGN sub-segments are merged and recognized by the two-layer CRF classifier; for this we have proposed a new algorithm based on the semi-Markov CRF decoding scheme. With eight signers, we obtained a recall rate of 95.7% and a precision of 96.6% for unseen samples from seen signers, and a recall rate of 86.6% and a precision of 89.9% for unseen signers.     

Coarse-to-fine dynamic programming

We introduce an extension of dynamic programming, we call "coarse-to-fine dynamic programming" (CFDP), ideally suited to DP problems with large state space. CFDP uses dynamic programming to solve a sequence of coarse approximations which are lower bounds to the original DP problem. These approximations are developed by merging states in the original graph into "superstates" in a coarser graph which uses an optimistic arc cost between superstates. The approximations are designed so that CFDP terminates when the optimal path through the original state graph has been found. CFDP leads to significant decreases in the amount of computation necessary to solve many DP problems and can, in some instances, make otherwise infeasible computations possible. CFDP generalizes to DP problems with continuous state space and we offer a convergence result for this extension. We demonstrate applications of this technique to optimization of functions and boundary estimation in mine recognition     

Test sequencing algorithms with unreliable tests

In this paper, we consider imperfect test sequencing problems under a single fault assumption. This is a partially observed Markov decision problem (POMDP), a sequential multistage decision problem wherein a failure source must be identified using the results of imperfect tests at each stage. The optimal solution for this problem can be obtained by applying a continuous-state dynamic programming (DP) recursion. However, the DP recursion is computationally very expensive owing to the continuous nature of the state vector comprising the probabilities of faults. In order to alleviate this computational explosion, we present an efficient implementation of the DP recursion. We also consider various problems with special structure (parallel systems) and derive closed form solutions/index-rules without having to resort to DP. Finally, we present various top-down graph search algorithms for problems with no special structure, including multistep DP, multistep information heuristics, and certainty equivalence algorithms     

具有不同数目状态结点的HMMs在中国手语识别中的应用

中国手语是中国聋人使用的语言,主要通过手势动作来表达一定的含义。因而,手语识别问题是动态连续信号的识别问题。目前大部分手语识别系统采用HMMs(hidden Markov models)作为系统的识别系统。由于各个词包含的基本手势数不同,若所有模型都由同样数目的状态结点构成会影响识别率。而由人为每个词设置状态数又很难达到完全准确,所述系统使用一种基于动态规划的估计状态结点数的办法,并实现了基于具有不同状态数目的HMM的训练及识别过程,实验结果表明,该系统在手语的识别速度和识别精度方面都有所提高。     

基于Kinect的手势特征提取的改进算法研究

在手语识别系统的应用背景下,基于微软的Kinect平台对使用者的手部主要特征进行提取。在算法CLTree和Integrating Boosting的基础上进行算法改进,提出新的算法DoubleMixing对提取的特征进行处理．得到一系列能够让计算机进行识别的手语手型特征信息,为后续的手语识别工作打下实验性的基础。     

Sign Language Spotting with a Threshold Model Based on Conditional Random Fields

Sign language spotting is the task of detecting and recognizing signs in a signed utterance, in a set vocabulary. The difficulty of sign language spotting is that instances of signs vary in both motion and appearance. Moreover, signs appear within a continuous gesture stream, interspersed with transitional movements between signs in a vocabulary and nonsign patterns (which include out-of-vocabulary signs, epentheses, and other movements that do not correspond to signs). In this paper, a novel method for designing threshold models in a conditional random field (CRF) model is proposed which performs an adaptive threshold for distinguishing between signs in a vocabulary and nonsign patterns. A short-sign detector, a hand appearance-based sign verification method, and a subsign reasoning method are included to further improve sign language spotting accuracy. Experiments demonstrate that our system can spot signs from continuous data with an 87.0 percent spotting rate and can recognize signs from isolated data with a 93.5 percent recognition rate versus 73.5 percent and 85.4 percent, respectively, for CRFs without a threshold model, short-sign detection, subsign reasoning, and hand appearance-based sign verification. Our system can also achieve a 15.0 percent sign error rate (SER) from continuous data and a 6.4 percent SER from isolated data versus 76.2 percent and 14.5 percent, respectively, for conventional CRFs.     

Combinatorial approaches to gene recognition

Recognition of genes via exon assembly approaches leads naturally to the use of dynamic programming. We consider the general graph-theoretical formulation of the exon assembly problem and analyze in detail some specific variants: multicriterial optimization in the case of non-linear gene-scoring functions; context-dependent schemes for scoring exons and related procedures for exon filtering; and highly specific recognition of arbitrary gene segments, oligonucleotide probes and polymerase chain reaction (PCR) primers.³     

基于条件随机域的上下文人类动作识别

提出一种新的基于条件随机域和隐马尔可夫模型（HMM）的人类动作识别方法——HMCRF。目前已有的动作识别方法均使用隐马尔可夫模型及其变型,这些模型一个最突出的不足就是要求观察值相互独立。条件模型很容易表示上下文相关性,且可使用动态规划做到有效且精确的推论,它的参数可以通过凸函数优化训练得到。把条件图形模型应用于动作识别之上,并通过大量的实验表明,所提出的方法在识别正确率方面明显优于一般线性结构的CRF和HMM。     

基于条件随机场的连续运动识别技术

在体育运动识别中,过渡姿势的复杂多变性容易导致识别错误。针对此问题,本文提出一种基于条件随机场CRF和条件概率密度传播Condensation的连续运动识别算法。该算法采用"分段识别"的思想,首先利用Condensation估计动作边界,然后分割出片段输入到CRF对其进行识别。实验结果表明,本文算法能减少过渡姿势对识别正确性的不良影响,比传统单纯使用CRF算法具有更好的稳定性和识别正确率。     

Hidden Markov model for human to computer interaction: a study on human hand gesture recognition

Human hand recognition plays an important role in a wide range of applications ranging from sign language translators, gesture recognition, augmented reality, surveillance and medical image processing to various Human Computer Interaction (HCI) domains. Human hand is a complex articulated object consisting of many connected parts and joints. Therefore, for applications that involve HCI one can find many challenges to establish a system with high detection and recognition accuracy for hand posture and/or gesture. Hand posture is defined as a static hand configuration without any movement involved. Meanwhile, hand gesture is a sequence of hand postures connected by continuous motions. During the past decades, many approaches have been presented for hand posture and/or gesture recognition. In this paper, we provide a survey on approaches which are based on Hidden Markov Models (HMM) for hand posture and gesture recognition for HCI applications.     

IMPROVED CONVERGENCE THROUGH DYNAMIC PROGRAMMING APPROACH

New hybrid methods for solving the multiplayer perceptron optimization problem are proposed which use the computation capabilities of Bellman's dynamic programming (DP) method. To solve the neural network optimization problem, we consider the case of output neurons differently from that of hidden neurons. For the neurons of the output layer we apply the conventional DP and for the hidden neurons we apply a method based on gradient approach. Computer simulation shows that the new hybrid methods outperform the gradient-based optimization methods in converging speed and avoiding the local minimum.     

Coupled grouping and matching for sign and gesture recognition

Matching an image sequence to a model is a core problem in gesture or sign recognition. In this paper, we consider such a matching problem, without requiring a perfect segmentation of the scene. Instead of requiring that low- and mid-level processes produce near-perfect segmentation, we take into account that such processes can only produce uncertain information and use an intermediate grouping module to generate multiple candidates. From the set of low-level image primitives, such as constant color region patches found in each image, a ranked set of salient, overlapping, groups of these primitives are formed, based on low-level cues such as region shape, proximity, or color. These groups corresponds to underlying object parts of interest, such as the hands. The sequence of these frame-wise group hypotheses are then matched to a model by casting it into a minimization problem. We show the coupling of these hypotheses with both non-statistical matching (match to sample-based modeling of signs) and statistical matching (match to HMM models) are possible. Our algorithm not only produces a matching score, but also selects the best group in each image frame, i.e. recognition and final segmentation of the scene are coupled. In addition, there is no need for tracking of features across sequences, which is known to be a hard task. We demonstrate our method using data from sign language recognition and gesture recognition, we compare our results with the ground truth hand groups, and achieved less than 5% performance loss for both two models. We also tested our algorithm on a sports video dataset that has moving background.     

Computational performance of basic state reduction based dynamic programming algorithms for bi-objective 0–1 knapsack problems

This paper studies a group of basic state reduction based dynamic programming (DP) algorithms for the multi-objective 0–1 knapsack problem (MKP), which are related to the backward reduced-state DP space (BRDS) and forward reduced-state DP space (FRDS). The BRDS is widely ignored in the literature because it imposes disadvantage for the single objective knapsack problem (KP) in terms of memory requirements. The FRDS based DP algorithm in a general sense is related to state dominance checking, which can be time consuming for the MKP while it can be done efficiently for the KP. Consequently, no algorithm purely based on the FRDS with state dominance checking has ever been developed for the MKP. In this paper, we attempt to get some insights into the state reduction techniques efficient to the MKP. We first propose an FRDS based algorithm with a local state dominance checking for the MKP. Then we evaluate the relative advantage of the BRDS and FRDS based algorithms by analyzing their computational time and memory requirements for the MKP. Finally different combinations of the BRDS and FRDS based algorithms are developed on this basis. Numerical experiments based on the bi-objective KP instances are conducted to compare systematically between these algorithms and the recently developed BRDS based DP algorithm as well as the existing FRDS based DP algorithm without state dominance checking.     

手写中文速记符中音符的动态规划识别方法

本文在分析英文速记识别技术以及中文速记特点的基础上，提出了中文速记符的自动识别策略，并且以“人群速记”体系为研究对象，详细描述了用于识别速记符中297个音符的动态规划识别过程。通过采用局部平滑预处理，以及基于速记符形状特征和结构特征的粗分类措施，大大提高了动态规划识别速度和正确识别率。初步实验表明，对特定人书写的297个人群速记音符用动态规划法进行识别，正确识别率能达到93％以上。     

Minimization of squared deviation of completion times about a common due date

We discuss a non-preemptive single-machine job sequencing problem where the objective is to minimize the sum of squared deviation of completion times of jobs from a common due date. There are three versions of the problem—tightly restricted, restricted and unrestricted. Separate dynamic programming formulations have already been suggested for each of these versions, but no unified approach is available. We have proposed a pseudo-polynomial DP solution and a polynomial heuristic for general instance. Computational results show that tightly restricted instances of up to 600 jobs can be solved in less than 6 s. General instances of up to 80 jobs take less than 2 s.Statement of scope and purposeIn this paper, we have considered an NP-complete single-machine scheduling problem arising in JIT environment, a field of great importance in manufacturing industry. The objective of the problem is to schedule a set of given jobs to minimize the sum of squared deviation of their completion times from a common due date. This paper presents a number of precedence rules, a polynomial heuristic and more importantly a unified pseudo-polynomial dynamic programming formulation. Empirical results show that the dynamic programming formulation performs better than the existing approaches.     

Parallel dynamic programming on clusters of workstations

The standard DP (dynamic programming) algorithms are limited by the substantial computational demands they put on contemporary serial computers. In this work, the theory behind the solution to serial monadic dynamic programming problems highlights the theory and application of parallel dynamic programming on a general-purpose architecture (cluster or network of workstations). A simple and well-known technique, message passing, is considered. Several parallel serial monadic DP algorithms are proposed, based on the parallelization in the state variables and the parallelization in the decision variables. Algorithms with no interpolation are also proposed. It is demonstrated how constraints introduce load unbalance which affect scalability and how this problem is inherent to DP.     

Bi-dimensional knapsack problems with one soft constraint

In this paper, we consider bi-dimensional knapsack problems with a soft constraint, i.e., a constraint for which the right-hand side is not precisely fixed or uncertain. We reformulate these problems as bi-objective knapsack problems, where the soft constraint is relaxed and interpreted as an additional objective function. In this way, a sensitivity analysis for the bi-dimensional knapsack problem can be performed: The trade-off between constraint satisfaction, on the one hand, and the original objective value, on the other hand, can be analyzed. It is shown that a dynamic programming based solution approach for the bi-objective knapsack problem can be adapted in such a way that a representation of the nondominated set is obtained at moderate extra cost. In this context, we are particularly interested in representations of that part of the nondominated set that is in a certain sense close to the constrained optimum in the objective space. We discuss strategies for bound computations and for handling negative cost coefficients, which occur through the transformation. Numerical results comparing the bi-dimensional and bi-objective approaches are presented.     

Large margin cost-sensitive learning of conditional random fields

We tackle the structured output classification problem using the Conditional Random Fields (CRFs). Unlike the standard 0/1 loss case, we consider a cost-sensitive learning setting where we are given a non-0/1 misclassification cost matrix at the individual output level. Although the task of cost-sensitive classification has many interesting practical applications that retain domain-specific scales in the output space (e.g., hierarchical or ordinal scale), most CRF learning algorithms are unable to effectively deal with the cost-sensitive scenarios as they merely assume a nominal scale (hence 0/1 loss) in the output space. In this paper, we incorporate the cost-sensitive loss into the large margin learning framework. By large margin learning, the proposed algorithm inherits most benefits from the SVM-like margin-based classifiers, such as the provable generalization error bounds. Moreover, the soft-max approximation employed in our approach yields a convex optimization similar to the standard CRF learning with only slight modification in the potential functions. We also provide the theoretical cost-sensitive generalization error bound. We demonstrate the improved prediction performance of the proposed method over the existing approaches in a diverse set of sequence/image structured prediction problems that often arise in pattern recognition and computer vision domains.     

On the existence of optimal strategies in the control problem for a stochastic discrete time system with respect to the probability criterion

We study a control problem for a stochastic system with discrete time. The optimality criterion is the probability of the event that the terminal state function does not exceed a given limit. To solve the problem, we use dynamic programming. The loss function is assumed to be lower semicontinuous with respect to the terminal state vector, and the transition function from the current state to the next is assumed to be continuous with respect to all its arguments. We establish that the dynamic programming algorithm lets one in this case find optimal positional control strategies that turn out to be measurable. As an example we consider a two-step problem of security portfolio construction. We establish that in this special case the future loss function on the second step turns out to be continuous everywhere except one point.     

Discriminative Learning for Dynamic State Prediction

We consider the problem of predicting a sequence of real-valued multivariate states that are correlated by some unknown dynamics, from a given measurement sequence. Although dynamic systems such as the State-Space Models are popular probabilistic models for the problem, their joint modeling of states and observations, as well as the traditional generative learning by maximizing a joint likelihood may not be optimal for the ultimate prediction goal. In this paper, we suggest two novel discriminative approaches to the dynamic state prediction: 1) learning generative state-space models with discriminative objectives and 2) developing an undirected conditional model. These approaches are motivated by the success of recent discriminative approaches to the structured output classification in discrete-state domains, namely, discriminative training of Hidden Markov Models and Conditional Random Fields (CRFs). Extending CRFs to real multivariate state domains generally entails imposing density integrability constraints on the CRF parameter space, which can make the parameter learning difficult. We introduce an efficient convex learning algorithm to handle this task. Experiments on several problem domains, including human motion and robot-arm state estimation, indicate that the proposed approaches yield high prediction accuracy comparable to or better than state-of-the-art methods.