Tarskian Set Constraints

We investigate set constraints over set expressions with Tarskian functional and relational operations. Unlike the Herbrand constructor symbols used in recent set constraint formalisms, the meaning of a Tarskian function symbol is interpreted in an arbitrary first order structure. We show that satisfiability of Tarskian set constraints is decidable in nondeterministic doubly exponential time. We also give complexity results and open problems for various extensions and restrictions of the language.     

Encoding Linear Logic with Interaction Combinators

The purpose of this paper is to demonstrate how Lafont's interaction combinators, a system of three symbols and six interaction rules, can be used to encode linear logic. Specifically, we give a translation of the multiplicative, exponential, and additive fragments of linear logic together with a strategy for cut-elimination which can be faithfully simulated. Finally, we show briefly how this encoding can be used for evaluating λ-terms. In addition to offering a very simple, perhaps the simplest, system of rewriting for linear logic and the λ-calculus, the interaction net implementation that we present has been shown by experimental testing to offer a good level of sharing in terms of the number of cut-elimination steps (resp. β-reduction steps). In particular it performs better than all extant finite systems of interaction nets.     

Support Function Representation of Convex Bodies, Its Application in Geometric Computing, and Some Related Representations

The importance of thesupport functionin representation, manipulation, and analysis of convex bodies can indeed be compared with that of the Fourier transform in signal processing. The support function, in intuitive terms, is the signed distance of a supporting plane of a convex body from the origin point. In this paper we show that, just as simple multiplication in the Fourier transform domain turns out to be the convolution of two signals, similarly simple algebraic operations on support functions result in a variety of geometric operations on the corresponding geometric objects. In fact, since the support function is areal-valuedfunction, these simple algebraic operations are nothing but arithmetic operations such as addition, subtraction, reciprocal, and max–min, which give rise to geometric operations such as Minkowski addition (dilation), Minkowski decomposition (erosion), polar duality, and union–intersection. Furthermore, it has been shown in this paper that a number of representation schemes (such as the Legendre transformation, the extended Gaussian image, slope diagram representation, the normal transform, and slope transforms), which appear to be very disparate at first sight, belong to the same class of the support function representation. Finally, we indicate some algebraic manipulations of support functions that lead to new and unsuspected geometric operations. Support function like representations for nonconvex objects are also indicated.     

A Probabilistic Model for Recovering Camera Translation

This paper describes the mathematical basis and application of a probabilistic model for recovering the direction of camera translation (heading) from optical flow. According to the theorem that heading cannot lie between two converging points in a stationary environment, one can compute the posterior probability distribution of heading across the image and choose the heading with maximum a posteriori (MAP). The model requires very simple computation, provides confidence level of the judgments, applies to both linear and curved trajectories, functions in the presence of camera rotations, and exhibited high accuracy up to 0.1°–0.2° in random dot simulations.     

Reduction of Permutation-Invariant Polynomials: A Noncommutative Case Study

Let R be a commutative ring with 1, let RX₁,…,X_n/I be the polynomial algebra in the n≥4 noncommuting variables X₁,…,X_n over R modulo the set of commutator relations I={(X₁+···+X_n)*X_i=X_i*(X₁+···+X_n)|1≤i≤n}. Furthermore, let G be an arbitrary group of permutations operating on the indeterminates X₁,…,X_n, and let RX₁,…,X_n/I^G be the R-algebra of G-invariant polynomials in RX₁,…,X_n/I. The first part of this paper is about an algorithm, which computes a representation for any fRX₁,…,X_n/I^G as a polynomial in multilinear G-invariant polynomials, i.e., the maximal variable degree of the generators of RX₁,…,X_n/I^G is at most 1. The algorithm works for any ring R and for any permutation group G. In addition, we present a bound for the number of necessary generators for the representation of all G-invariant polynomials in RX₁,…,X_n/I^G with a total degree of at most d. The second part contains a first but promising analysis of G-invariant polynomials of solvable polynomial rings.     

3-D Reconstruction of Urban Scenes from Aerial Stereo Imagery: A Focusing Strategy

A contribution to the automatic 3-D reconstruction of complex urban scenes from aerial stereo pairs is proposed. It consists of segmenting the scene into two different kinds of components: the ground and the above-ground objects. The above-ground objects are classified either as buildings or as vegetation. The idea is to define appropriate regions of interest in order to achieve a relevant 3-D reconstruction. For that purpose, a digital elevation model of the scene is first computed and segmented into above-ground regions using a Markov random field model. Then a radiometric analysis is used to classify above-ground regions as building or vegetation, leading to the determination of the final above-ground objects. The originality of the method is its ability to cope with extended above-ground areas, even in case of a sloping ground surface. This characteristic is necessary in a urban environment. Results are very robust to image and scene variability, and they enable the utilization of appropriate local 3-D reconstruction algorithms.     

Computation of Approximate Polynomial GCDs and an Extension

Computation of approximate polynomial greatest common divisors (GCDs) is important both theoretically and due to its applications to control linear systems, network theory, and computer-aided design. We study two approaches to the solution so far omitted by the researchers, despite intensive recent work in this area. Correlation to numerical Padé approximation enabled us to improve computations for both problems (GCDs and Padé). Reduction to the approximation of polynomial zeros enabled us to obtain a new insight into the GCD problem and to devise effective solution algorithms. In particular, unlike the known algorithms, we estimate the degree of approximate GCDs at a low computational cost, and this enables us to obtain certified correct solution for a large class of input polynomials. We also restate the problem in terms of the norm of the perturbation of the zeros (rather than the coefficients) of the input polynomials, which leads us to the fast certified solution for any pair of input polynomials via the computation of their roots and the maximum matchings or connected components in the associated bipartite graph.     

A Framework for Recognizing the Simultaneous Aspects of American Sign Language

The major challenge that faces American Sign Language (ASL) recognition now is developing methods that will scale well with increasing vocabulary size. Unlike in spoken languages, phonemes can occur simultaneously in ASL. The number of possible combinations of phonemes is approximately 1.5×10⁹, which cannot be tackled by conventional hidden Markov model-based methods. Gesture recognition, which is less constrained than ASL recognition, suffers from the same problem. In this paper we present a novel framework to ASL recognition that aspires to being a solution to the scalability problems. It is based on breaking down the signs into their phonemes and modeling them with parallel hidden Markov models. These model the simultaneous aspects of ASL independently. Thus, they can be trained independently, and do not require consideration of the different combinations at training time. We show in experiments with a 22-sign-vocabulary how to apply this framework in practice. We also show that parallel hidden Markov models outperform conventional hidden Markov models.     

Face Detection: A Survey

In this paper we present a comprehensive and critical survey of face detection algorithms. Face detection is a necessary first-step in face recognition systems, with the purpose of localizing and extracting the face region from the background. It also has several applications in areas such as content-based image retrieval, video coding, video conferencing, crowd surveillance, and intelligent human–computer interfaces. However, it was not until recently that the face detection problem received considerable attention among researchers. The human face is a dynamic object and has a high degree of variability in its apperance, which makes face detection a difficult problem in computer vision. A wide variety of techniques have been proposed, ranging from simple edge-based algorithms to composite high-level approaches utilizing advanced pattern recognition methods. The algorithms presented in this paper are classified as either feature-based or image-based and are discussed in terms of their technical approach and performance. Due to the lack of standardized tests, we do not provide a comprehensive comparative evaluation, but in cases where results are reported on common datasets, comparisons are presented. We also give a presentation of some proposed applications and possible application areas.     

Efficient Computation of the Euclidean Distance Transform

We present a simple algorithm for the Euclidean distance transform of a binary image that runs more efficiently than other algorithms in the literature. We show that our algorithm runs in optimal time for many architectures and has optimal cost for the RAM and EREW PRAM.     

A Fully Syntactic AC-RPO

We present the first fully syntactic (i.e., non-interpretation-based) AC-compatible recursive path ordering (RPO). It is simple, and hence easy to implement, and its behaviour is intuitive as in the standard RPO. The ordering is AC-total and defined uniformly for both ground and nonground terms, as well as for partial precedences. More important, it is the first one that can deal incrementally with partial precedences, an aspect that is essential, together with its intuitive behaviour, for interactive applications such as Knuth–Bendix completion.     

Rollback-Dependency Trackability: A Minimal Characterization and Its Protocol

Considering a checkpoint and communication pattern, the rollback-dependency trackability (RDT) property stipulates that there is no hidden dependency between local checkpoints. In other words, if there is a dependency between two checkpoints due to a noncausal sequence of messages (Z-path), then there exists a causal sequence of messages (C-path) that doubles the noncausal one and that establishes the same dependency.This paper introduces the notion of RDT-compliance. A property defined on Z-paths is RDT-compliant if the causal doubling of Z-paths having this property is sufficient to ensure RDT. Based on this notion, the paper provides examples of such properties. Moreover, these properties are visible, i.e., they can be tested on the fly. One of these properties is shown to be minimal with respect to visible and RDT-compliant properties. In other words, this property defines a minimal visible set of Z-paths that have to be doubled for the RDT property to be satisfied.Then, a family of communication-induced checkpointing protocols that ensure on-the-fly RDT properties is considered. Assuming processes take local checkpoints independently (called basic checkpoints), protocols of this family direct them to take on-the-fly additional local checkpoints (called forced checkpoints) in order that the resulting checkpoint and communication pattern satisfies the RDT property. The second contribution of this paper is a new communication-induced checkpointing protocol . This protocol, based on a condition derived from the previous characterization, tracks a minimal set of Z-paths and breaks those not perceived as being doubled. Finally, a set of communication-induced checkpointing protocols are derived from . Each of these derivations considers a particular weakening of the general condition used by . It is interesting to note that some of these derivations produce communication-induced checkpointing protocols that have already been proposed in the literature.     

A Real-Time Approach to the Spotting, Representation, and Recognition of Hand Gestures for Human–Computer Interaction

Aiming at the use of hand gestures for human–computer interaction, this paper presents a real-time approach to the spotting, representation, and recognition of hand gestures from a video stream. The approach exploits multiple cues including skin color, hand motion, and shape. Skin color analysis and coarse image motion detection are joined to perform reliable hand gesture spotting. At a higher level, a compact spatiotemporal representation is proposed for modeling appearance changes in image sequences containing hand gestures. The representation is extracted by combining robust parameterized image motion regression and shape features of a segmented hand. For efficient recognition of gestures made at varying rates, a linear resampling technique for eliminating the temporal variation (time normalization) while maintaining the essential information of the original gesture representations is developed. The gesture is then classified according to a training set of gestures. In experiments with a library of 12 gestures, the recognition rate was over 90%. Through the development of a prototype gesture-controlled panoramic map browser, we demonstrate that a vocabulary of predefined hand gestures can be used to interact successfully with applications running on an off-the-shelf personal computer equipped with a home video camera.     

An Algebra of Discrete Channels That Involve Combinations of Three Basic Error Types

Recently, the author introduced a nonprobabilistic mathematical model of discrete channels, the BEE channels, that involve the error-types substitution, insertion, and deletion. This paper defines an important class of BEE channels, the SID channels, which include channels that permit a bounded number of scattered errors and, possibly at the same time, a bounded burst of errors in any segment of predefined length of a message. A formal syntax is defined for generating channel expressions, and appropriate semantics is provided for interpreting a given channel expression as a communication channel (SID channel) that permits combinations of substitutions, insertions, and deletions of symbols. Our framework permits one to generalize notions such as error correction and unique decodability, and express statements of the form “The code K can correct all errors of type ξ” and “it is decidable whether the code K is uniquely decodable for the channel described by ξ”, where ξ is any SID channel expression.     

A Region-Based Scheme Using RKLT and Predictive Classified Vector Quantization

This paper proposes a compression scheme for face profile images based on three stages, modelling, transformation, and the partially predictive classified vector quantization (CVQ) stage. The modelling stage employs deformable templates in the localisation of salient features of face images and in the normalization of the image content. The second stage uses a dictionary of feature-bases trained for profile face images to diagonalize the image blocks. At this stage, all normalized training and test images are spatially clustered (objectively) into four subregions according to their energy content, and the residuals of the most important clusters are further clustered (subjectively) in the spectral domain, to exploit spectral redundancies. The feature-basis functions are established with the region-based Karhunen–Loeve transform (RKLT) of clustered image blocks. Each image block is matched with a representative of near-best basis functions. A predictive approach is employed for mid-energy clusters, in both stages of search for a basis and for a codeword from the range of its cluster. The proposed scheme employs one stage of a cascaded region-based KLT-SVD and CVQ complex, followed by residual VQ stages for subjectively important regions. The first dictionary of feature-bases is dedicated to the main content of the image and the second is dedicated to the residuals. The proposed scheme is experimented in a set of human face images.     

Optimal Computing the Chessboard Distance Transform on Parallel Processing Systems

Thedistance transform(DT) is an image computation tool which can be used to extract the information about the shape and the position of the foreground pixels relative to each other. It converts a binary image into a grey-level image, where each pixel has a value corresponding to the distance to the nearest foreground pixel. The time complexity for computing the distance transform is fully dependent on the different distance metrics. Especially, the more exact the distance transform is, the worse execution time reached will be. Nowadays, quite often thousands of images are processed in a limited time. It seems quite impossible for a sequential computer to do such a computation for the distance transform in real time. In order to provide efficient distance transform computation, it is considerably desirable to develop a parallel algorithm for this operation. In this paper, based on the diagonal propagation approach, we first provide anO(N²) time sequential algorithm to compute thechessboard distance transform(CDT) of anN×Nimage, which is a DT using the chessboard distance metrics. Based on the proposed sequential algorithm, the CDT of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. Following the mapping as proposed by Lee and Horng, the algorithm for the medial axis transform is also efficiently derived. The medial axis transform of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. The proposed parallel algorithms are composed of a set of prefix operations. In each prefix operation phase, only increase (add-one) operation and minimum operation are employed. So, the algorithms are especially efficient in practical applications.     

Guaranteeing the Diversity of Number Generators

A major problem in using iterative number generators of the form x_i=f(x_i−1) is that they can enter unexpectedly short cycles. This is hard to analyze when the generator is designed, hard to detect in real time when the generator is used, and can have devastating cryptanalytic implications. In this paper we define a measure of security, called sequence diversity, which generalizes the notion of cycle-length for noniterative generators. We then introduce the class of counter-assisted generators and show how to turn any iterative generator (even a bad one designed or seeded by an adversary) into a counter-assisted generator with a provably high diversity, without reducing the quality of generators which are already cryptographically strong.     

A Continuous Probabilistic Framework for Image Matching

In this paper we describe a probabilistic image matching scheme in which the image representation is continuous and the similarity measure and distance computation are also defined in the continuous domain. Each image is first represented as a Gaussian mixture distribution and images are compared and matched via a probabilistic measure of similarity between distributions. A common probabilistic and continuous framework is applied to the representation as well as the matching process, ensuring an overall system that is theoretically appealing. Matching results are investigated and the application to an image retrieval system is demonstrated.     

The Complexity of the Exponential Output Size Problem for Top-Down and Bottom-Up Tree Transducers,

The exponential output size problem is to determine whether the size of output trees of a tree transducer grows exponentially in the size of input trees. In this paper the complexity of this problem is studied. It is shown to be NL-complete for total top-down tree transducers, DEXPTIME-complete for general top-down tree transducers, and P-complete for bottom-up tree transducers.